Поиск ошибки в архитектуре процессора Xbox 360

https://randomascii.wordpress.com/2018/01/07/finding-a-cpu-design-bug-in-the-xbox-360/
  • Перевод
Вашему вниманию предлагается перевод свежей статьи Брюса Доусона – разработчика, сегодня работающего в Google над Chrome для Windows.

Недавнее открытие уязвимостей Meltdown и Spectre напомнило мне о том случае, как однажды я обнаружил подобную уязвимость в процессоре Xbox 360. Её причиной была недавно добавленная в процессор инструкция, само существование которой представляло собой опасность.

В 2005 году я занимался процессором Xbox 360. Я жил и дышал исключительно этим чипом. У меня на стене до сих пор висят полупроводниковая пластина процессора диаметром в 30 см и полутораметровый постер с архитектурой этого CPU. Я потратил так много времени на то, чтобы понять, как работают вычислительные конвейеры процессора, что, когда меня попросили выяснить причину загадочных падений, я смог интуитивно догадаться о том, что к их появлению могла привести ошибка в дизайне процессора.

Однако, прежде чем перейти к самой проблеме, сначала немного теории.

imageПроцессор Xbox 360 представляет собой трехъядерный чип PowerPC, изготовленный IBM. Каждое из трех ядер располагается в отдельном квадранте, а четвертый квадрант отведён под 1 MB L2 кэш – вы можете увидеть всё это на изображении рядом. У каждого ядра есть кэш инструкций в 32 KB и кэш данных в 32 KB.

Факт: Ядро 0 было физически расположено к L2 кэшу ближе всего, и поэтому имеет значительно меньшее время задержки при обращении к L2 кэшу.

У процессора Xbox 360 для всего были большие задержки (high latencies), в частности плохими были задержки памяти (memory latencies). К тому же, 1 MB L2 кэш (а это всё, что смогло влезть в процессор) был маловат для трех-ядерного CPU. Поэтому важно было экономить место в L2 кэше для того, чтобы минимизировать промахи кэша.

Как известно, кэши процессора улучшают производительность за счет пространственной локальности (spatial locality) и временной локальности (temporal locality). Пространственная локализация обозначает следующее: если вы использовали один байт данных, то вы возможно вскоре используете другие расположенные рядом байты данных; временная – если вы использовали какую-то память, то возможно вы используете ее снова в ближайшем будущем.
Причем, иногда временная локальность на самом деле не происходит. Если вы обрабатываете большой массив данных once-per-frame, тогда можно тривиально доказать, что он уйдет из L2 кэша к тому моменту, когда он потребуется вам снова. Вы все еще будете хотеть, чтобы данные лежали в L1 кэше, чтобы вы могли получить пользу от пространственной локальности — но если эти данные продолжат оставаться в L2 кэше, то они вытеснят другие данные, что в результате может замедлить работу двух других ядер.

Обычно это является неизбежным. Механизм когерентности памяти нашего процессора PowerPC требовал того, чтобы все данные из L1 кэшей также находились в L2 кэше. Протокол MESI, который был использован для когерентности памяти, требовал того, чтобы когда одно ядро пишет в кэш-линию, которую любое другое ядро с копией той же линии кэш-линии должно отбросить – и L2 кэш должен отвечать за отслеживание того, какие из L1-кэшей занимались кэшированием каких адресов.

Однако, процессор предназначался для видеоигровой консоли, и главным приоритетом считалась производительность, поэтому в CPU была добавлена новая инструкция – xdcbt. Обычная инструкция PowerPC, dcbt, была типичной инструкцией для выполнения предварительной выборки (prefetch). Инструкция xdcbt была расширенной инструкцией для выполнения prefetch, которая позволяла получать данные из памяти сразу в L1 кэш данных, минуя L2-кэш. Это означало то, что когерентность памяти больше не гарантировалась — но вы же знаете игровых разработчиков: мы знаем, что мы делаем, всё будет ОК!

Упс…

Я написал часто используемую функцию для копирования памяти в Xbox 360, которая опционально использовала xdcbt. Предварительная выборка исходных данных (prefetching) было ключевым для производительности и обычно использовала dcbt, но при передаче флага PREFETCH_EX она выполняла выборку с xdcbt. Увы, как показала практика, это оказалось непродуманным решением.

Игровой разработчик, который пользовался этой функцией, регулярно рассказывал о странных крешах — происходило повреждение кучи, но структура кучи в дампах памяти выглядела нормально. Порядком насмотревшись на дампы крешей, я наконец понял, где сделал ошибку.

Память, которая была выбрана с помощью xdcbt, была «токсичной». Если её записало другое ядро перед тем, как она была сброшена из L1-кэша, то два других ядра имели другой взгляд на память — и не было никакой гарантии того, что их взгляды когда-либо совпадут. Кэш-линии на Xbox 360 составляли 128 байт, и моя функция копирования проходила прямо до конца исходной памяти – в итоге xdcbt применялась к кэш-линиям, последние части которых представляли собой части смежных структур данных. Обычно это были метаданные кучи – по крайней мере, именно там мы наблюдали креши. Некогерентное ядро видело устаревшие данные (невзирая на осторожное использование блокировок) и падало, но дамп креша выдавал фактическое содержание RAM, поэтому мы не могли увидеть, что происходило на самом деле.

Итого, единственным безопасным способом использования xdcbt было крайней осторожное выполнение предварительных выборок, чтобы в нее не попадал даже единственный байт после конца буфера. Я исправил свою функцию копирования памяти, чтобы она не «забегала» так далеко, но оказалось, что не дождавшись моего багфикса, игровой разработчик просто перестал пользоваться флагом PREFETCH_EX, и проблема ушла сама собой.

Настоящий баг


Вроде бы и всё, верно? Игровой разработчик играл с огнем, слишком близко подлетел к солнцу, и выпуск игровой консоли чуть не пропустил Рождество. Но мы вовремя нашли эту проблему, решили ее, и теперь были готовы к выпуску консоли и игр — а также беззаботно уйти домой

И тут эта игра начала крешиться снова.

Симптомы были идентичными — за исключением того, что игра больше не использовала инструкцию xdcbt. Я мог выполнить отладку кода по шагам, и видел, что это было действительно так. Похоже, мы действительно столкнулись с серьезной проблемой.

Мне пришлось прибегнуть к древнейшему способу отладки – я очистил свое сознание, позволил вычислительным конвейерам заполнить моё подсознание — и внезапно до меня дошло, в чем могла быть проблема. Я быстро написал email в IBM, и мои опасения насчет одной тонкости внутреннего устройства процессоров, о которой я никогда раньше не задумывался, подтвердились. Злодей был тем же, что и в случае с Meltdown и Spectre.

Процессор Xbox 360 выполняет инструкции по порядку (in-order execution). На самом деле, этот процессор устроен достаточно просто, и для достижения высокой производительности полагается на свою высокую частоту (пусть и не такую высокую, как ожидалось). Однако, в него входит предсказатель переходов – он является вынужденной необходимостью из-за очень длинных вычислительных конвейеров. Вот диаграмма, иллюстрирующая устройство конвейеров CPU, на которой показаны все конвейеры (если вы хотите знать больше деталей, то не пропустите эту ссылку):

image


На этой диаграмме вы можете видеть и предсказатель переходов, и то, что конвейеры очень длинные (широкие на диаграмме) – достаточно длинные для того, чтобы ошибочно предсказанные инструкции (mispredicted instructions) могли угнаться за остальными, невзирая на выполнение команд по порядку.

Итак, предсказатель переходов делает предсказание, и предсказанные инструкции выбираются, декодируются и выполняются – но не удаляются до тех пор, пока не станет известно, является ли предcказание корректным. Звучит знакомо? Открытие, которое я для себя сделал – раньше я об этом не задумывался – состояло в том, что на самом деле происходило при спекулятивном выполнении предварительной выборки. Поскольку задержки были большими, было важно получить транзакцию предварительной выборки на шину максимально быстро, и как только выборка стартовала, не было никакой возможности отменить её. Поэтому спекулятивно выполненный xdcbt был идентичен реальному xdcbt! (Спекулятивно выполненная команда загрузки была всего лишь предварительной выборкой)

В этом-то и была проблема. Предсказатель переходов иногда приводил к спекулятивному выполнению команд xdcbt, и это было настолько же плохо, как и их реальное выполнение. Одна из моих коллег предложила интересный способ проверить эту теорию – заменить каждый вызов xdcbt в игре брейкпоинтом. Это позволило добиться следующего результата:

  • Брейкпоинты больше не срабатывали, что доказывало тот факт, что игра не выполняла инструкции xdcbt;
  • Креши исчезли.

Для меня это было ожидаемым результатом, но это всё равно было очень впечатляюще. Даже годы спустя, когда я читал про Meltdown, было по-прежнему круто видеть как инструкции, которые не были выполнены, становились причинами крешей.

Мое озарение насчет предсказателя переходов сделало ясным следующее – эта инструкция была слишком опасной, чтобы включать ее в каком-либо сегменте кода любой из игр – контролирование того, когда инструкция может быть «спекулятивно» выполнена, оказалось слишком сложным. В теории, предсказатель переходов мог предсказать любой адрес, поэтому безопасного места для размещения инструкции xdcbt не было. Риски можно было уменьшить, но не убрать полностью, да и усилия того не стоили. Несмотря на то, что обсуждения архитектуры Xbox 360 продолжают упоминать эту инструкцию, я сомневаюсь, что хоть одна игра, использующая ее, дошла до релиза.

Как-то раз во время собеседования в ответ на классический вопрос «опишите самый сложный баг, с которым вам приходилось сталкиваться» я рассказал про этот случай. Реакцией интервьюера было «Да, мы сталкивались с чем-то подобным на процессорах DEC Alpha”.

Вот уж действительно, всё новое — хорошо забытое старое.
Поделиться публикацией
Ой, у вас баннер убежал!

Ну. И что?
Реклама
Комментарии 18
  • +1
    Это, конечно, перевод. И в английском это, конечно, design. Но на русский design надо переводить. У нас «дизайн» имеет совсем другой смысл. Так же как и control и многое другое. Тут design — это конструкция, проект, архитектура и т.д.

    Это как в одной статье (тоже переводной) про лунный модуль было написано «главный дизайнер программы» а по факту это был главный или ведущий конструктор.
    • +2
      Читаю переводы (в том числе на этом сайте), и постоянно спотыкаюсь об этих дизайнеров, которые на самом деле конструкторы. Пора уже что-то делать — или начинать «официально» и внешний вид и устройство дизайном называть, или начинать народ активно просвещать, как с историей про тся/ться.
      Накипело)
      • +1
        Или таки добавить, наконец, Ctrl+Enter.
        • 0
          А также про отличие силиконовой и кремниевой долины, и что это 2 разных места.
        • +3
          Спасибо за комментарий! Лично я с вашей позицией полностью согласен. Всегда переводил «design» в зависимости от контекста.

          Но сегодня погуглил и задумался — некоторые электронные СМИ теперь действительно пишут «дизайн процессора», подразумевая именно что архитектуру. На официальном сайте AMD про Ryzen 7 написано «прекрасно сбалансированный дизайн», и речь там вроде как идёт не про внешние качества. Такими темпами, «дизайн» вскоре может закрепиться и стать неологизмом, пусть и не очень удобным.

          В статье речь действительно идёт про архитектуру процессора, поэтому для ясности поменял заголовок.
          • 0
            Да нет, не неологизмом. Возможно, просто наш смысл сравняется с изначальным. У нас дизайнер — художник, у них — разработчик. А вот как тогда будут называть дизайнеров, которые художники — это вопрос.

            А на переводных сайтах тексты пишут не инженеры, а переводчики. И хорошо, если они хоть немного в теме. А то всякое видел. Даже на сайтах крупных компаний.
            • 0
              А вот как тогда будут называть дизайнеров, которые художники — это вопрос.
              Артистами?
              • 0

                Слово «арт» уже укоренилось, так что остался всего лишь шаг.

        • +1

          Хех! Что там реальные процы. Я такое видел на эмуляторе проца прошлой осенью. При этом ошибка как бы происходила на еще не выполненной инструкции (ошибка, характерная для той специфической команды). А рс каждый раз указывал на разные адреса до той инструкции. Потом догнали, что дело именно в префетч.
          Но что интересно, так это четкая логика эмулятора — он рубил на корню доступ в запрещенную область, даже при префетче, не то, что железные процы. Правда рубил ценой крэша.

          • 0
            Здорово!
            Тоже сталкивался и теперь я знаю, что это было и как я тупил… Давно, когда я учился и писал на ассемблере под голое железо, не мог понять почему код вылетал на не выполняемых инструкциях (даже после явного перескока этих инструкций с помощью jmp). Как только я убирал те строки всё становилось ОК. Тогда я тоже пришёл к выводу, что они выполняются, но почему и как я не додумался. На вопросы знатоки объясняли, что кэш с предсказателем только кэширует наперёд и ничего выполнять не может. Поверил в кривой код и свои ошибки, а дело то было в железе и недостатке знаний… =)
          • +2
            Когда GPU умели делать ветвление только через умножение на 0 результата одной ветви, умножением на 1 результата другой и сложением, то код:
            If(d[0]==0) r = cos(d[1]);
            else r = log(d[1]);
            всегда выдавал NaN, если d[1]<=0, потому что любая операция с NaN, дает NaN
            • 0
              «полупроводниковая пластина процессора диаметром в 30 см и» — WTF???
              • +4
                Вполне нормальный перевод оригинального «30-cm CPU wafer». Кристаллы делают на круглых листах кремния, и 300мм — очень популярный в индустрии диаметр.
                • 0
                  Тут на самом деле тяжело подобрать адекватный перевод. В таком переводе фраза звучит как будто на стене висит некая деталь процессорА(ну или сам процессор) с диаметром в 30см.
                  • 0
                    Кремниевая пластина с процессорами, диаметром 30см?
              • +1
                Я правильно понял из статьи, что инструкцию xdcbt исключили методом
                if(никогда_не_использовать_инструкцию_xdcbt)
                {
                xdcbt;
                }
                • 0
                  Предполагаю, там было
                  if( данные выровнены по 128 )
                  {
                  xdcbt;
                  }
                • –1
                  Подозреваю, что текст «Поэтому спекулятивно выполненный xdcbt был идентичен реальному xdcbt!» следует читать как «Поэтому спекулятивно выполненный dcbt был идентичен реальному xdcbt!»

                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                  Самое читаемое