![[Перевод] Бесконечный цикл, которого не было: история бага Святого Грааля](https://habrastorage.org/getpro/habr/post_images/1b0/c85/547/1b0c8554787a8e54e1ac5c21c78d639c.png "[Перевод] Бесконечный цикл, которого не было: история бага Святого Грааля")
Но ведь это незаконно, правда?
Постойте-ка — если вы пытаетесь получить доступ к недействительной памяти, то игра просто должна вылететь, правильно? Должна произойти неразрешённая операция, segfault или какая-то ещё ошибка. Верно?
Ну… Как бы да. Но не совсем. По крайней мере, не на GBA.
В архитектуре процессоров ARM, которые использовались в GBA, это ошибочное состояние называется data abort и возникает только тогда, когда вы пытаетесь получить доступ к памяти, которой диспетчер памяти не назначил разрешение на считывание1. Когда происходит data abort, процессор завершает выполнение того, что делал, и переходит к вектору исключений, назначенному исключениям data abort. Затем операционная система может выбрать одно из решений: убить текущий процесс, назначить памяти page fault, позволить процессу справляться с ситуацией, как JIT некоторых эмуляторов делают это с «fastmem», или совершить какие-то другие действия.
Как же GBA обрабатывает data abort? Запись вектора исключений для data abort находится в загрузочном ROM консоли GBA (или как его ещё называют, в BIOS). Если GBA сталкивается с data abort, то она пытается перейти к обработчику DACS2, если он существует, а в противном случае происходит блокировка. Ни в одной коммерческой игре нет обработчиков DACS. Так почему же эта игра не зависает? Всё очень просто — GBA никогда не генерирует data abort. У неё нет диспетчера памяти (MMU) (или даже блока защиты памяти, как в DS), поэтому она просто продолжает работу и считывает недействительную память.
На сцену выходит шина памяти
Что вообще такое — недействительная память? Как она выглядит? В этом-то и заключается основная загвоздка. Это сложная ситуация: то, что считывает код, сильно зависит от того, что недавно делал ЦП, или, если точнее, что недавно делала шина памяти. Если объяснять вкратце, то при доступе к недействительной памяти ЦП считывает то, что было последним в шине памяти. Чтобы разобраться, что из этого следует, нужно немного узнать о шине памяти и о том, как она работает.
Шина памяти — это часть электронной схемы, соединяющая ЦП со всеми компонентами памяти платформы. На GBA к шине памяти подключено несколько устройств: рабочая ОЗУ, видеопамять и шина картриджа. Когда ЦП пытается получить доступ к памяти, он сообщает шине памяти, к какому адресу ему нужен доступ, после чего задействуется компонент, соответствующий этому адресу. Затем компонент помещает значение по этому адресу в шину, для чего может потребоваться несколько циклов3, а затем ЦП наконец может считать значение из шины. В случае GBA, если с адресом не связано никакое оборудование, то в шину не записывается значение, и ЦП считывает любое значение, помещённое в шину последним. Ситуация может различным образом варьироваться, например, если считывание было 16-битным, а ЦП пытается выполнить 32-битное считывание, но в целом это всегда будет значение из шины. Разработчики называют такую особенность «открытой шиной». Ранее я писал, как она влияет на другие игры.
Ну, вроде всё выглядит не так уж плохо… Верно?
То есть можно просто кэшировать последний доступ к памяти? А затем снова вернуть его? В общем случае, такой подход сработает, но существуют определённые трудности. Во-первых, нужно сделать так, чтобы все операции доступа к памяти находились в правильном порядке. Это сложнее, чем кажется, ведь ЦП выполняет доступы к памяти каждой инструкцией для получения следующей инструкции в конвейере. И на самом деле, в общем случае*, задержавшаяся в шине память — это последняя инструкция, которая была получена. Это упрощает процесс, ведь нужно получать только это последнее, предварительно выбранное значение. Но поскольку последнее предварительно выбранное значение зависит только от того, откуда мы в настоящий момент осуществляем выполнение в памяти, оно всегда должно быть одинаковым. Даже если получаемый адрес изменяется, пока он недействителен, вы всегда будете получать одинаковую память.
Эээ… Стоп. Но этот цикл существует, и из него нельзя выйти, если это значение является предварительно выбранным. Так что же происходит? Если он постоянно получает следующую инструкцию, то что случается между этими операциями? Я пытался запускать подобные бесконечные циклы на тестовых ROM-ах, чтобы проверить может ли, например, значение портиться. Это определённо может происходить, если значение недавно не обновлялось, но значение обновляется в каждой инструкции, поэтому у него нет времени испортиться. Мои тесты никогда не покидали цикла. Я делал что-то иначе, чем в этих играх, хотя в точности воссоздал цикл. Что же я делал не так?
Pokémon Emerald и ACE, возникающее только на железе
Перенесёмся вперед во времени, в январь 2020 года. Отчёту о баге в Sonic Pinball Party на этот момент исполнилось примерно три с половиной года. В других эмуляторах он был известен многие годы. У меня закончились рабочие теории. В конце этого месяца пользователь под ником merrp присоединился к Discord-сообществу эмулятора mGBA и сообщил, что в Pokémon Emerald есть новый глитч исполнения произвольного кода (arbitrary code execution, ACE), который работает только на железе. Более того, этот глитч скорее всего будет использоваться спидраннерами, которые могут захотеть попрактиковаться в эмуляторе. Очевидно, что этот баг стал привлекательной мишенью для исправления ошибки, хотя лучше бы я узнал о нём до версии 0.8.0. Я начал исследовать глитч и подтвердил наблюдение merrp о том, что он работает только на железе. Во всех испробованных мной эмуляторах игра зависала с чёрным экраном. Но merrp сообщил мне, что она зависает на чтении из недействительной памяти в цикле, и я понял, что скорее всего не смогу в ближайшее время исправить ошибку. Это опять тот же баг.
На этот раз изучение зациклившейся функции дало мне преимущество. Благодаря проекту декомпиляции pokeemerald я мог легко внести целевые изменения в функцию, чтобы попробовать разобраться, как ей удаётся выбраться из цикла. Упрощённая версия этого цикла выглядит примерно так:
uint16_t type = /* ... */;
for (int32_t i = 0; table[type][i] != 0xFFFF; ++i) {
uint16_t value = table[type][i] & 0xFE00;
if (value > 0x7E00) {
break;
}
/* ... */
}
Цикл выполняет довольно простую задачу. Существует двухмерная таблица значений. В каждой строке этой таблицы столбца type цикл сначала пытается определить, является ли значение определённым значением «sentinel». Если это так, цикл завершается. В противном случае он применяет к значению маску и проверяет, больше ли оно проверяемого значения. В противном случае он спускается ниже по циклу. В конкретном случае возникновения глитча значение type выходит за границы таблицы, что приводит к появлению недействительного указателя. Это означает, что при попытке доступа к i-тому элементу этого несуществующего столбца мы всегда будем выполнять доступ к недействительной памяти. Хотя смещение таблицы с каждой итерацией цикла увеличивается, прежде чем вернуться к действительной памяти, ему может понадобиться сотни миллионов повторений. Поэтому очевидно, что он этого не делает. Так как же программа выбирается из цикла?
Чтобы исследовать это я изменил цикл и посмотрел, что произойдёт, если я просто мгновенно вырвусь из цикла. Всё оказалось достаточно просто: в этот момент ACE сработало и на железе и в эмуляторе, и ничего не зависало. Поэтому вместо этого я попытался задать в качестве цвета экрана значение, которое программа считывает, когда выходит из цикла и зависает, чтобы цвет не менялся. Я повторно скомпилировал код и запустил его на реальной GBA. Спустя несколько секунд зависания на чёрном экране он стал великолепного синего оттенка.
ОЧЕНЬ СИНЕГО
Но эмулятор всё равно зависал на чёрном экране. Какое же значение он будет считывать, если считывал ранее полученное значение? Вместо этого он стал темновато-бирюзовым.
Фу
То есть программа, прежде чем ей удалось выбраться из цикла, совершенно точно по крайней мере один раз прошла его. Также оказалось, что время, необходимое на побег из цикла на железе, варьируется. Обычно это занимало от 2 до 30 секунд. Что же происходит?
Новая рабочая теория
Затем я заметил разницу между моим тестовым ROM и Pokémon Emerald при зависании. В Pokémon играла музыка. В Sonic Pinball Party тоже играла музыка. В Hello Kitty музыка не играла, но это дало мне идею. Что происходит, если возникает прерывание между предварительной выборкой и загрузкой данных? Начинает ли программа предварительную выборку вектора прерывания перед доступом к недействительной памяти? Я быстренько создал макет этой ситуации в mGBA, включил прерывания в тестовом ROM, и он конечно же выбрался из цикла. Затем я попробовал тот же тестовый ROM на железе и… он не выбрался из цикла. И так появилась теория. В конечном итоге я кое-что осознал. Я уверен, что выше вы заметили пометку-звёздочку, так что да, между предварительной выборкой и доступом к памяти может произойти одно событие, но только если между предварительной выборкой и доступом к недействительной памяти шине памяти посылает запрос не ЦП, а что-то другое.
Я говорил, что шина памяти управляется ЦП. По большей части это справедливо, но есть и другое важное оборудование, тоже имеющее доступ к шине памяти в обход процессора. Этот процесс называется прямым доступом к памяти (direct memory access). Я рассказывал о DMA в предыдущей статье, поэтому сейчас не буду вдаваться в принципы его работы. Если перечитаете статью, то можете заметить, что я сказал, что главный ЦП приостанавливает работу, пока работает DMA. Это означает, что пока работает DMA, значение в шине теперь будет последним доступом к памяти DMA. В основном это важно, если DMA выходит за пределы действительной памяти в недействительную область; при этом он дублирует последнее хорошее значение.
Уже давно известно, что если загрузить недействительную память в DMA, то вы получите последнее значение DMA, но я давно реализовал это в mGBA и уже забыл об этом. Когда я увидел это в коде доступа к недействительной памяти при изучении бага, в голове что-то щёлкнуло. Что, если значение DMA задержится в шине на одну инструкцию? Если первая инструкция после DMA завершает загрузку недействительной памяти до того, как получит следующее значение, то в теории это должно привести к повторной загрузке значения DMA. Более того, воспроизведение музыки в GBA обычно задействует DMA для передачи аудиоданных на выход. Для правильной реализации этого потребуется потактово точный эмулятор, который может блокировать ЦП посередине выполнения инструкции, между началом инструкции и доступом к памяти, а эмуляция консоли GBA в эмуляторе mGBA не потактово точная. И это мне кое о чём напоминает. К счастью, мне удалось обойти эту проблему. Решение неидеально, но я теперь могу сравнивать ожидаемый ЦП адрес для инструкции после DMA с текущим адресом ЦП при недействительной загрузке и использовать для этого одного адреса вместо предварительно выбранного значения значение DMA.
Долгожданное решение
Я включил операции DMA для H-blank в тестовом ROM и синхронизировал их с V-blank, чтобы тайминги были стабильными, запустил его на железе, и… на этот раз всё заработало! Тестовый ROM постоянно выходил из цикла после одинакового количества итераций, когда из шины считывалось значение DMA. Я оказался прав! Для правильной реализации этого в mGBA потребовалось несколько попыток, но теперь программа выходит из цикла с теми же результатами, что и на железе. Я наконец получил на mGBA оттенок синего. Hello Kitty загрузилась. Сохранение в Sonic Pinball Party заработало.
Я это сделал.
Наверно, это было самое долгое время, которое я тратил на единственный баг. На протяжении трёх лет я вложил в его отладку столько времени, что сбился со счёта, и я уверен, что другие разработчики тоже сталкивались с подобными ситуациями в своих эмуляторах. Без этого озарения мне мог потребоваться ещё один год, или даже больше, но чёрный экран, на котором ничего не происходило, кроме воспроизведения музыки, стал той костяшкой домино, которая привела к обрушению всей проблемы.
Теперь, когда решение найдено, его можно реализовать и в других эмуляторах GBA, положив конец этому багу. Баг будет исправлен в mGBA 0.9.0, который, как я надеюсь, выйдет в этом году, и уже исправлен в тестовых сборках. Вы наконец можете играть в Hello Kitty Collection: Miracle Fashion Maker. Если, конечно, пожелаете, не мне вас судить.
- В случае попытки выполнения памяти, которой не назначены разрешения на выполнение, это называется prefetch abort.
- DACS (сокращение от Debugging and Communication System) — это часть комплекта разработки GBA.
- Эти циклы простаивания во время чтения из шины иногда называют wait states.
