Вашему вниманию предлагается перевод свежей статьи Брюса Доусона – разработчика, сегодня работающего в Google над Chrome для Windows.
Недавнее открытие уязвимостей Meltdown и Spectre напомнило мне о том случае, как однажды я обнаружил подобную уязвимость в процессоре Xbox 360. Её причиной была недавно добавленная в процессор инструкция, само существование которой представляло собой опасность.
В 2005 году я занимался процессором Xbox 360. Я жил и дышал исключительно этим чипом. У меня на стене до сих пор висят полупроводниковая пластина процессора диаметром в 30 см и полутораметровый постер с архитектурой этого CPU. Я потратил так много времени на то, чтобы понять, как работают вычислительные конвейеры процессора, что, когда меня попросили выяснить причину загадочных падений, я смог интуитивно догадаться о том, что к их появлению могла привести ошибка в дизайне процессора.
Однако, прежде чем перейти к самой проблеме, сначала немного теории.
Процессор 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, на которой показаны все конвейеры (если вы хотите знать больше деталей, то не пропустите эту ссылку):
На этой диаграмме вы можете видеть и предсказатель переходов, и то, что конвейеры очень длинные (широкие на диаграмме) – достаточно длинные для того, чтобы ошибочно предсказанные инструкции (mispredicted instructions) могли угнаться за остальными, невзирая на выполнение команд по порядку.
Итак, предсказатель переходов делает предсказание, и предсказанные инструкции выбираются, декодируются и выполняются – но не удаляются до тех пор, пока не станет известно, является ли предcказание корректным. Звучит знакомо? Открытие, которое я для себя сделал – раньше я об этом не задумывался – состояло в том, что на самом деле происходило при спекулятивном выполнении предварительной выборки. Поскольку задержки были большими, было важно получить транзакцию предварительной выборки на шину максимально быстро, и как только выборка стартовала, не было никакой возможности отменить её. Поэтому спекулятивно выполненный xdcbt был идентичен реальному xdcbt! (Спекулятивно выполненная команда загрузки была всего лишь предварительной выборкой)
В этом-то и была проблема. Предсказатель переходов иногда приводил к спекулятивному выполнению команд xdcbt, и это было настолько же плохо, как и их реальное выполнение. Одна из моих коллег предложила интересный способ проверить эту теорию – заменить каждый вызов xdcbt в игре брейкпоинтом. Это позволило добиться следующего результата:
Для меня это было ожидаемым результатом, но это всё равно было очень впечатляюще. Даже годы спустя, когда я читал про Meltdown, было по-прежнему круто видеть как инструкции, которые не были выполнены, становились причинами крешей.
Мое озарение насчет предсказателя переходов сделало ясным следующее – эта инструкция была слишком опасной, чтобы включать ее в каком-либо сегменте кода любой из игр – контролирование того, когда инструкция может быть «спекулятивно» выполнена, оказалось слишком сложным. В теории, предсказатель переходов мог предсказать любой адрес, поэтому безопасного места для размещения инструкции xdcbt не было. Риски можно было уменьшить, но не убрать полностью, да и усилия того не стоили. Несмотря на то, что обсуждения архитектуры Xbox 360 продолжают упоминать эту инструкцию, я сомневаюсь, что хоть одна игра, использующая ее, дошла до релиза.
Как-то раз во время собеседования в ответ на классический вопрос «опишите самый сложный баг, с которым вам приходилось сталкиваться» я рассказал про этот случай. Реакцией интервьюера было «Да, мы сталкивались с чем-то подобным на процессорах DEC Alpha”.
Вот уж действительно, всё новое — хорошо забытое старое.
Недавнее открытие уязвимостей Meltdown и Spectre напомнило мне о том случае, как однажды я обнаружил подобную уязвимость в процессоре Xbox 360. Её причиной была недавно добавленная в процессор инструкция, само существование которой представляло собой опасность.
В 2005 году я занимался процессором Xbox 360. Я жил и дышал исключительно этим чипом. У меня на стене до сих пор висят полупроводниковая пластина процессора диаметром в 30 см и полутораметровый постер с архитектурой этого CPU. Я потратил так много времени на то, чтобы понять, как работают вычислительные конвейеры процессора, что, когда меня попросили выяснить причину загадочных падений, я смог интуитивно догадаться о том, что к их появлению могла привести ошибка в дизайне процессора.
Однако, прежде чем перейти к самой проблеме, сначала немного теории.
Процессор 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, на которой показаны все конвейеры (если вы хотите знать больше деталей, то не пропустите эту ссылку):
На этой диаграмме вы можете видеть и предсказатель переходов, и то, что конвейеры очень длинные (широкие на диаграмме) – достаточно длинные для того, чтобы ошибочно предсказанные инструкции (mispredicted instructions) могли угнаться за остальными, невзирая на выполнение команд по порядку.
Итак, предсказатель переходов делает предсказание, и предсказанные инструкции выбираются, декодируются и выполняются – но не удаляются до тех пор, пока не станет известно, является ли предcказание корректным. Звучит знакомо? Открытие, которое я для себя сделал – раньше я об этом не задумывался – состояло в том, что на самом деле происходило при спекулятивном выполнении предварительной выборки. Поскольку задержки были большими, было важно получить транзакцию предварительной выборки на шину максимально быстро, и как только выборка стартовала, не было никакой возможности отменить её. Поэтому спекулятивно выполненный xdcbt был идентичен реальному xdcbt! (Спекулятивно выполненная команда загрузки была всего лишь предварительной выборкой)
В этом-то и была проблема. Предсказатель переходов иногда приводил к спекулятивному выполнению команд xdcbt, и это было настолько же плохо, как и их реальное выполнение. Одна из моих коллег предложила интересный способ проверить эту теорию – заменить каждый вызов xdcbt в игре брейкпоинтом. Это позволило добиться следующего результата:
- Брейкпоинты больше не срабатывали, что доказывало тот факт, что игра не выполняла инструкции xdcbt;
- Креши исчезли.
Для меня это было ожидаемым результатом, но это всё равно было очень впечатляюще. Даже годы спустя, когда я читал про Meltdown, было по-прежнему круто видеть как инструкции, которые не были выполнены, становились причинами крешей.
Мое озарение насчет предсказателя переходов сделало ясным следующее – эта инструкция была слишком опасной, чтобы включать ее в каком-либо сегменте кода любой из игр – контролирование того, когда инструкция может быть «спекулятивно» выполнена, оказалось слишком сложным. В теории, предсказатель переходов мог предсказать любой адрес, поэтому безопасного места для размещения инструкции xdcbt не было. Риски можно было уменьшить, но не убрать полностью, да и усилия того не стоили. Несмотря на то, что обсуждения архитектуры Xbox 360 продолжают упоминать эту инструкцию, я сомневаюсь, что хоть одна игра, использующая ее, дошла до релиза.
Как-то раз во время собеседования в ответ на классический вопрос «опишите самый сложный баг, с которым вам приходилось сталкиваться» я рассказал про этот случай. Реакцией интервьюера было «Да, мы сталкивались с чем-то подобным на процессорах DEC Alpha”.
Вот уж действительно, всё новое — хорошо забытое старое.
