Turbofan
Введение
В этом долгожданном посте мы расскажем о компиляторе V8. Мы рассмотрим общий дизайн, его реализацию в коде, средства отладки и многое другое. Как я уже упоминал ранее, именно этот компонент в V8 подвергается наибольшему контролю. Несмотря на то, что эксплуатация V8 — это гораздо больше, это та область, о которой обычно говорят.Turbofan получает информацию от Ignition или Liftoff об исходном коде, а затем преобразует ее в высокооптимизированный машинный код для конкретной архитектуры. Помните, что этот процесс происходит только тогда, когда функция или другой участок кода становится «hot» или запускается несколько раз. Затем V8 использует замену в стеке для выполнения оптимизированного кода во время выполнения.
Примечание. В этом посте я буду говорить о компиляции JavaScript, пока игнорируя WebAssembly.
Дизайн компилятора
Turbofan использует структуру Sea of Nodes , хорошо известную в теории компиляторов и слегка модифицированную для целей V8. На очень высоком уровне компилятор берет Abstract Syntax Tree (AST), которое уже было сгенерировано Ignition, и выполняет ряд оптимизаций, чтобы уменьшить граф и превратить его в машинный код. Эти узлы могут объединяться, разделяться или изменять имена в дереве на этапах оптимизации. На каждом этапе используется определенный visitor class для прохождения узлов и применения изменений, специфичных для узла. Мы собираемся начать наш анализ оптимизации с обсуждения этого промежуточного представления (IR) между исходным кодом JavaScript и окончательным JIT-кодом.
Деоптимизация
Я знаю, что мы еще даже не добрались до оптимизации, но некоторые из первых вещей, упомянутых в разговоре о IR, — это призывы к deopt, поэтому нам нужно сделать небольшой обход. В то время как решение об оптимизации принимается за пределами Turbofan, деоптимизация — это то, что вызывается из JIT-кода, создаваемого Turbofan. В V8 есть два вида деоптимизации: активная и ленивая.Eager deopt — это когда «исполняемый в данный момент код нуждается в деоптимизации». ( источник ) В приведенном ниже коде функция f() будет деоптирован, если он будет вызван снова с аргументом, который не является числом.
JavaScript:
function f(x) {
return x + 1;
}
// optimize for integer argument
for (i = 0; i < 1000000; i++) {
f(i);
}
// now deoptimize when called with string as argument
f("1");В этом случае вызов f() со строкой делает недействительным предположение, что параметр является целым числом. V8 проверяет предположения, помещая проверки в код JIT, которые мы увидим в разделе IR. Если эти проверки не пройдены, мы немедленно вернемся к интерпретатору .
Lazy deopt — это когда «выполняемый в данный момент код делает недействительным какой-то другой код». ( источник ) Таким образом, если наш оптимизированный код влияет на какой другой оптимизированный код, нам нужно деоптимизировать этот другой код, потому что мы могли нарушить некоторые из его предположений. V8 использовался для отслеживания дерева эффектов, деоптимизируя его по ходу дела. Однако теперь он заменяет код других функций вызовами деоптимизации. Поскольку деоптимизация произойдет позже, всякий раз, когда запускается этот другой код, поэтому называется ленивым . Работу для ленивого деопта можно найти в аннотации этой internship on lazyness.
Нам может понадобиться обратиться к интерпретатору, если что-то пойдет не так в нашей функции, и вы можете увидеть все причины в src/deoptimize-reason.h. Используя d8, мы можем увидеть, какие функции были деоптимизированы с помощью флага --trace-deopt.
На этот раз я, наконец, резюмировал основные моменты чего-то, не просто ссылаясь на ссылку. При этом, если вам нужна полная презентация о деоптимизации от команды Google, ее можно найти здесь .
Промежуточное представление
Поскольку Turbofan оптимизируется в несколько циклов, имеет смысл иметь некоторую промежуточную структуру для медленной оптимизации. Есть две отличные презентации, которые должны послужить отправной точкой для изучения и справочными материалами для дальнейшего использования: Turbofan IR и Turbofan JIT Design . Если вы понимаете и то, и другое, то дальнейшие сообщения будут намного легче понять. Позже в этом посте мы узнаем, как смотреть на графики для нашего собственного кода JavaScript.
Typing
Как только мы поместим весь наш JavaScript в дерево, мы можем начать включать информацию о каждом узле, чтобы лучше свернуть его. Часть этой информации может включать побочные эффекты или актуальность потока управления, а также тип узла и диапазон возможных значений. Типизация — это процесс определения возможного, ну… типа узла и его возможных значений. Например, узел может представлять целое число с возможным диапазоном от 5 до 10, как в случае с x в приведенном ниже коде.
JavaScript:
var x = 5;
if (y == 10) {
x = 10;
}Следующий код может быть полезной информацией для оптимизации, как в этом примере:
JavaScript:
var x = 5;
if (y == 10) {
x = 10;
}
if (x < 5) {
// unreachable, "if" statement can be eliminated
}Компилятор может удалить блок кода оператора «if», поскольку он знает, что сравнение целого числа с возможным диапазоном от 5 до 10 никогда не будет меньше 5. Однако также важно помнить, что не весь код в файле JavaScript оптимизирован. В данном случае таких предположений сделать нельзя:
JavaScript:
function example(x, y) {
if (y == 10) {
x = 10;
}
if (x < 5) {
// compiler wouldn't know that this is unreachable because it is only optimizing within the function scope
}
}
// optimize
for (i = 0; i < 1000000; i++) {
example(i, 0);
}
// "if" statement would be unnecessary in this case
var z1 = 5;
var z2 = 10;
example(z1, z2);Типизация — один из наиболее важных аспектов работы компилятора, который необходимо понять, поскольку многие эксплойты были разработаны с использованием преимуществ того, что компилятор предполагает о коде, по сравнению с тем, что на самом деле происходит во время выполнения. Эта концепция немного сбивает с толку, но мы углубимся в нее в рамках наших тематических исследований (и несколько примеров уже доступны в нашем разделе ресурсов).
То types.h файл невероятно полезен для понимания того, как V8 выполняет набор текста. Он не только включает в себя все различные существующие «типы», но также содержит множество комментариев, чтобы понять смысл вещей. По сути, существует битовый массив, описывающий тип каждого узла. Битовые флаги объединяются, чтобы показать все возможные типы узла. Обратите особое внимание на то, что NaN и MinusZero имеют свои собственные значения и сколько различных представлений существует для чисел. Когда мы посмотрим на дерево IR, мы увидим, как отслеживается информация о типе узла и возможных диапазонах значений.
Массивы
Одна вещь, которая не сразу бросается в глаза при взгляде на types.h заключается в том, что на самом деле существуют разные типы массивов. Это потому, что мы хотим эффективно хранить значения массива, а для разных типов массивов существуют разные оптимизации. Например, взгляните на этот код:
JavaScript:
let arr1 = [0, 1, 2];
let arr2 = new Array(1000);
arr2[0] = 0;
arr2[999] = 999;За arr1 в приведенном выше примере имеет смысл выделить 3 блока непрерывной памяти для хранения наших значений. Однако для arr2, мы можем просто захотеть сохранить 2 значения с их индексами, 0 и 999. Это в основном разница между «упакованными» и «дырявыми» массивами. Можно еще многое сказать о типизации массивов, и мы рассмотрим это в моем следующем посте.
Операции
Когда узлы коллапсируют, их значения могут быть объединены. Вот краткий обзор терминов, которые часто встречаются в коде:
union - объединить все возможные значения обоих входов.
intersect — объединить только совпадающие значения обоих входов.
phi — компиляторам нужен какой-то способ отслеживать переменные на разных возможных путях выполнения. Это требует присвоения одной и той же переменной разных промежуточных идентификаторов ( пояснение ). Когда пути выполнения сливаются, мы объединяем возможные значения переменной из обоих путей.
is - node.Is(arg) Узел «является» переданным ему аргументом, если он является подмножеством аргумента, переданного функции.
maybe - node.Maybe(arg) Узел «может быть» является аргументом, если аргумент является подмножеством всех типов узла.
См . презентацию Saelo
Инструменты отладки
d8 флаги
Вызов d8 с --helpflag выводит огромный список опций. Несмотря на то, что есть варианты включения/отключения многих функций V8, мы сосредоточимся на флаге --trace-turbo, который выведет json-файл для просмотра IR оптимизированных функций в нашем скрипте. --trace-turbo-filteroption укажет функцию для трассировки, которая может избавиться от лишних файлов, если ваш цикл for будет оптимизирован или что-то в этом роде. Еще одно быстрое замечание, --print-opt-code --print-code-verbose --code-comments можно использовать для получения дополнительной информации о машинном коде, создаваемом Turbofan. Если вы просто хотите увидеть, когда функция оптимизируется, и причину, вы можете использовать --trace-opt.
Я видел 3 способа оптимизации функций для тестирования эксплойтов. Не существует «правильного» пути, но я хочу упомянуть об этом, потому что, когда вы играете с POC предыдущих ошибок, важно знать, что не все пути оптимизации сразу же будут представлять ошибки одинаковым образом. Как я упоминал в предыдущем посте из этой серии, --allow-natives-syntax флаг позволяет нам использовать определенные встроенные функции, которые понимает V8.
Цикл for с достаточным количеством итераций для запуска оптимизации
JavaScript:
function test() {
// some code here to optimize
}
for (var i=0; i < 1000000; i++) {
test();
}
// ./d8 test.js --allow-natives-syntax --trace-turbo --trace-turbo-path turbo_out --trace-turbo-filter testВызов нативной функции OptimizeFunctionOnNextCall
JavaScript:
function test() {
// some code here to optimize
}
%OptimizeFunctionOnNextCall(test);
test();
// ./d8 test.js --allow-natives-syntax --trace-turbo --trace-turbo-path turbo_out --trace-turbo-filter testИспользование собственных функций PrepareFunctionForOptimization, а затем OptimizeFunctionOnNextCall
JavaScript:
function test() {
// some code here to optimize
}
%PrepareFunctionForOptimization(test);
test();
%OptimizeFunctionOnNextCall(test);
test();
// ./d8 test.js --allow-natives-syntax --trace-turbo --trace-turbo-path turbo_out --trace-turbo-filter testTurbolizer
Теперь, когда у нас есть файл json, мы можем просмотреть его в браузере с помощью Turbolizer, который включен в репозиторий V8. Вы можете получить доступ к общедоступной версии здесь .
Вот инструкции, по его локальной настройке:
- tools/turbolizer в каталоге установки V8
- npm i
- также можно запустить npm audit fix
- npm run-script build
- В любое время, когда вы хотите использовать turbolizer, вам просто нужно иметь веб-сервер для этого каталога, простой способ сделать это, запустив python3 -m http.server
- Перейдите к порту 8000 (или любому другому порту, который вы определили) в своем браузере и загрузите файл json (в указанный вами выходной каталог), используя значок облака в правом верхнем углу.
Вы можете распечатать исходный байт-код Ignition с помощью флага --print-bytecode.
Нет лучшего способа понять IR, чем посмотреть на него в Turbolizer. Создайте несколько простых сценариев, которые оптимизируют некоторые функции, возможно, попробовав три разных метода, описанных выше, и посмотрите, как узлы изменяются на разных этапах оптимизации. Некоторые имена узлов не будут иметь особого смысла, но это нормально.
Мы собираемся углубиться в отслеживание пути оптимизации.
Где Code?
В моем последнем посте я сказал, что было бы неплохо освоиться с кодовой базой. Это пригодится сейчас, когда вы посмотрите на этапы оптимизации, как они фактически выполняются в C++. Это также будет полезно, когда какая-либо из этих сведений изменится в будущем.Я хочу выделить текущую статью для изучения эксплуатации Turbolize. Jeremy Fetiveau много писал на эту тему, и вы можете найти его вступительную статью здесь . Он дает список некоторых важных мест в пределах src/compiler и рассказывает об этапах оптимизации. Эта статья отлично подходит для получения общего обзора с некоторой подробной информацией. Я определенно рекомендую начать с этого, а затем просмотреть этот пост Сакуры в блоге , в котором очень подробно рассказывается о конвейере оптимизации. Я стараюсь не вдаваться в подробности, поскольку кодовая база изменится, но я обнаружил, что большая часть анализа Сакуры по-прежнему верна. Тем не менее, вся эта информация, вероятно, потребует некоторого времени для понимания, и, вероятно, лучше попрактиковаться, просмотрев прошлую ошибку, чтобы получить некоторое представление, прежде чем пытаться полностью понять все аспекты временной шкалы.
Мой личный процесс понимания заключается в том, чтобы заглянуть в Turbolizer и просмотреть различные этапы оптимизации. Затем я пытаюсь сопоставить имя фазы с соответствующим файлом в src/compiler, или просмотрите ссылки, которые я упомянул, а затем найдите в файле имена узлов, которые я просматриваю. Как правило, узлы имеют определенную функцию для каждой фазы, которая может выполнять определенную оптимизацию. Некоторые фазы не могут уменьшить некоторые узлы, и они останутся без изменений. Иногда фазы просто меняют имя узла. Выяснение переходов требует времени, но использование Turbolizer и исходного кода помогает. Как я упоминал в предыдущем посте, вы можете использовать VSCode для быстрого поиска ссылок между функциями, чтобы лучше понять поток управления. Однако во многих случаях отчеты об ошибках содержат подробную информацию о том, где находится уязвимый код, и вы можете просто пропустить его. Однако лучшее понимание всего процесса значительно упрощает понимание отчетов (и поиск собственных ошибок!).
Nodes and Operators
node.h имеет много комментариев, которые детализируют Nodestruct, которая играет центральную роль в понимании оптимизации. Эта структура содержит идентификатор, информацию о типе, смежные узлы и некоторые другие сведения, составляющие узел в IR. Важно знать, где искать элементы этой структуры, потому что некоторые имена не сразу понятны. Некоторые более угадываемы, например, node->InputAt(0) относится к соседнему узлу, который предоставляет входные данные для текущего узла (хотя я часто вижу, что это обернуто как Operand(node, i)).Еще немного информации из комментариев:
Узел — это базовый примитив графов. . Узлы связаны между собой цепочками ввода/использования, но по умолчанию содержат только идентификационный номер, который конкретные приложения графов и узлов могут использовать для индексации вспомогательных данных вне линии, особенно переходных данных. Кроме того, узлы содержат только мутабельный Оператор, который может меняться во время компиляции, например, во время проходов опускания. Другая информация, которая должна быть связана с узлами во время компиляции, должна храниться вне строки, индексируемая по id узла.
Operator.h содержит определение, как вы догадались, структуры Operator. Узлы, которые "работают" над другими значениями (подумайте о "+"), также содержат информацию о том, какие зависимости они создают, сколько значений они принимают и т.д. Доступ к этой информации осуществляется через node->op().
Еще немного комментариев:
Оператор представляет собой описание "вычисления" узла в компиляторе IR. Вычисление принимает значения (т.е. данные) в качестве входных и производит ноль или более значений в качестве выходных. Побочные эффекты вычислений должны быть отражены дополнительными зависимостями управления и данных, которые являются частью графа IR.
Операторы неизменяемы и описывают статически известные части вычислений. Поэтому они могут безопасно использоваться многими различными узлами в IR-графе или даже глобально между графами. Операторы могут иметь "статические параметры", которые являются постоянными параметрами оператора во время компиляции, например, имя для доступа к именованному полю, идентификатор функции времени выполнения и т.д.
Статические параметры являются частными для оператора и семантически значимы только для самого оператора.
Заключение
Есть еще много вопросов, на которые нужно ответить, например, «как мы находим ошибки в этой огромной кодовой базе?», «как вы попрактикуетесь в понимании этого?», «это Turbofan или TurboFan?». К счастью, информации об этом больше, чем о большинстве других частей V8. Моя цель состояла в том, чтобы включить много базовой информации и ссылок для чтения о Turbofan, прежде чем перейти к эксплуатации.
Кроме того, статья Цуро об эксплуатации V8 — отличная презентация, в которой резюмируется большая часть того, о чем я говорил, и есть несколько примеров эксплуатации.
Перевод этой статьи.