Поиск ошибки в архитектуре процессора 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”.

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

Подробнее
Реклама
Комментарии 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!»

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