Когда-то давно я смеха ради решил доказать обратимость процесса и научиться генерировать JavaScript (а точнее, Asm.js) из машинного кода. Для эксперимента был выбран QEMU, некоторое время спустя была написана статья на Хабр. В комментариях мне посоветовали переделать проект на WebAssembly, да и самому бросать почти законченный проект как-то не хотелось… Работа шла, но уж очень медленно, и вот, недавно в той статье появился комментарий на тему «Так и чем всё закончилось?». На мой развёрнутый ответ я услышал «Это тянет на статью». Ну, раз тянет, то будет статья. Может, кому пригодится. Из неё читатель узнает некоторые факты про устройство бекендов кодогенерации QEMU, а также как написать Just-in-Time компилятор для веб-приложения.

Задачи

Поскольку «кое-как» портировать QEMU на JavaScript я уже научился, в этот раз было решено делать по уму и не повторять старых ошибок.

Ошибка номер раз: ответвиться от point release

Первой моей ошибкой было ответвить свою версию от upstream-версии 2.4.1. Тогда мне казалось это хорошей идеей: если point release существует, значит он, наверное, стабильнее простого 2.4, а уж тем более ветки master. А поскольку я планировал добавить изрядное количество своих багов, то чужие мне были ну вообще не нужны. Так оно, наверное, и получилось. Но вот незадача: QEMU не стоит на месте, а в какой-то момент там даже анонсировали оптимизацию генерируемого кода процентов на 10. «Ага, сейчас вмёржу» подумал я и обломался. Тут надо сделать отступление: в связи с однопоточным характером QEMU.js и тем, что оригинальный QEMU не предполагает отсутствия многопоточности (то есть для него критична возможность одновременной работы нескольких несвязанных code path, а не просто «заюзать все ядра»), главные функции потоков пришлось «вывернуть» для возможности вызова снаружи. Это создало некие естественные проблемы при слиянии. Однако тот факт, что часть изменений из ветки master, с которой я пытался слить свой код, также были cherry picked в point release (а значит, и в мою ветку) тоже, вероятно, удобства бы не добавил.

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

Ошибка номер два: ТЛП-методология

В сущности, это и не ошибка, в общем-то — просто особенность создания проекта в условиях полного непонимания как «куда и как двигаться?», так и вообще «а дойдём ли?». В этих условиях тяп-ляп программирование было оправданным вариантом, но, естественно, совершенно не хотелось это повторять без необходимости. В этот раз хотелось сделать по уму: атомарные коммиты, осознанные изменения кода (а не «stringing random characters together until it compiles (with warnings)», как про кого-то однажды сказал Линус Торвальдс, если верить Викицитатнику) и т.д.

Ошибка номер три: не зная броду лезть в воду

От этого я и сейчас до конца не избавился, но теперь решил идти не по пути совсем уж наименьшего сопротивления, и сделать «по взрослому», а именно, написать свой TCG backend с нуля, чтобы потом не говорить, мол «Да, это, конечно, медленно, но я же не могу всё контролировать — TCI так написан...». Кроме того, изначально это казалось очевидным решением, поскольку я же бинарный код генерирую. Как говорится, «Собрал Генту, да не ту»: код-то, конечно, бинарный, но управление на него просто так не передать — его нужно явным образом запихнуть в браузер на компиляцию, получив в результате некий объект из мира JS, который ещё нужно куда-то сохранить. Впрочем, на нормальныхRISC-архитектурах, насколько я понимаю, типичной ситуацией является необходимость явно сбросить кеш инструкций для перегенерированного кода — если это и не то, что нам нужно, то, во всяком случае, близко. Кроме того, из прошлой своей попытки я усвоил, что управление на середину блока трансляции вроде как не передаётся, поэтому байткод, интерпретируемый с любого смещения, нам особо и не нужен, и можно просто генерировать по функции на TB.

Пришли и пнули

Хотя переписывать код я начал ещё в июле, но волшебный пендель подкрался незаметно: обычно письма с GitHub приходят как уведомления об ответах на Issues и Pull requests, а тут, внезапно упоминание в треде Binaryen as a qemu backend в контексте, «Вот он что-то подобное делал, может скажет что-нибудь». Речь шла об использовании родственной Emscripten-у библиотеки Binaryen для создания WASM JIT. Ну я и сказал, что у вас там лицензия Apache 2.0, а QEMU как единое целое распространяется под GPLv2, и они не очень совместимые. Внезапно оказалось, что лицензию можно как-то поправить (не знаю: может, поменять, может, двойное лицензирование, может, ещё что-то...). Это меня, конечно, обрадовало, потому что я уже несколько раз к тому времени присматривался к бинарному формату WebAssembly, и мне было как-то грустно и непонятно. Здесь же была библиотека, которая и базовые блоки с графом переходов сожрёт, и байткод выдаст, и даже сама его запустит в интерпретаторе, если потребуется.

Потом ещё было письмо в списке рассылки QEMU, но это уже скорее к вопросу, «А кому оно вообще надо?». А оно, внезапно, оказалось надо. Как минимум, можно наскрести такие возможности использования, если оно будет более-менее шустро работать:

• запуск чего-нибудь обучающего вообще без установки
• виртуализация на iOS, где по слухам единственное приложение, имеющее право на кодогенерацию на лету — это JS-движок (а правда ли это?)
• демонстрация мини-ОС — однодискетные, встроенные, всякие прошивки и т.д...

Особенности браузерной среды выполнения

Как я уже говорил, QEMU завязан на многопоточность, а в браузере её нет. Ну, то есть как нет… Сначала её не было вообще, потом появились WebWorkers — насколько я понимаю, это многопоточность, основанная на передаче сообщений без совместно изменяемых переменных. Естественно, это создаёт значительные проблемы при портировании существующего кода, основанного на shared memory модели. Потом под давлением общественности была реализована и она под названием SharedArrayBuffers. Её постепенно ввели, отпраздновали её запуск в разных браузерах, потом отпраздновали новый год, а потом Meltdown… После чего пришли к выводу, что загрубляй-не загрубляй измерение времени, а с помощью shared memory и потока, инкрементирующего счётчик, всё равно довольно точно получится. Так и отключили многопоточность с общей памятью. Вроде бы, её потом включали обратно, но, как стало понятно из первого эксперимента, и без неё жизнь есть, а раз так, то попробуем сделать, не закладываясь на многопоточность.

Вторая особенность заключается в невозможности низкоуровневых манипуляций со стеком: нельзя просто взять, сохранить текущий контекст и переключиться на новый с новым стеком. Стек вызовов управляется виртуальной машиной JS. Казалось бы, в чём проблема, раз уж мы всё равно решили управляться с бывшими потоками полностью вручную? Дело в том, что блочный ввод-вывод в QEMU реализован через корутины, и вот тут бы нам и пригодились низкоуровневые манипуляции стеком. К счастью, Emscipten уже содержит механизм для асинхронных операций, даже два: Asyncify и Emterpreter. Первый работает через значительное раздувание генерируемого JavaScript-кода и уже не поддерживается. Второй является текущим «правильным способом» и работает через генерацию байткода для собственного интерпретатора. Работает, конечно, медленно, но зато не раздувает код. Правда, поддержку корутин для этого механизма пришлось контрибутить самостоятельно (там уже были корутины, написанные под Asyncify и была реализация приблизительно того же API для Emterpreter, нужно было просто их соединить).

На данный момент я ещё не успел разделить код на компилируемый в WASM и интерпретируемый с помощью Emterpreter, поэтому блочные устройства ещё не работают (смотрите в следующих сериях, как говорится...). То есть, в итоге должно получиться вот такое забавное слоистое нечто:

• интерпретируемый блочный ввод-вывод. Ну а что, вы правда ожидали эмулируемый NVMe с нативной производительностью? :)
• статически скомпилированный основной код QEMU (транслятор, остальные эмулируемые устройства и т.д.)
• динамически компилируемый в WASM гостевой код

Особенности исходников QEMU

Как вы, наверное, уже догадались, код эмуляции гостевых архитектур и код генерации хостовых машинных инструкций у QEMU разделён. На самом деле, там даже ещё чуть хитрее:

• есть гостевые архитектуры
• есть акселераторы, а именно, KVM для аппаратной виртуализации на Linux (для совместимых между собой гостевых и хостовых систем), TCG для JIT-кодогенерации где попало. Начиная с QEMU 2.9 появилась поддержка стандарта аппаратной виртуализации HAXM на Windows (подробности)
• если используется TCG, а не аппаратная виртуализация, то у него есть отдельная поддержка кодогенерации под каждую хостовую архитектуру, а также под универсальный интерпретатор
• … а вокруг всего этого — эмулируемая периферия, пользовательский интерфейс, миграция, record-replay, и т.д.

Кстати, знаете ли вы: QEMU может эмулировать не только компьютер целиком, но и процессор для отдельного пользовательского процесса в хостовом ядре, чем пользуется, например, фаззер AFL для инструментации бинарников. Возможно, кто-то захочет портировать этот режим работы QEMU на JS? ;)

Как и большинство давно существующих свободных программ, QEMU собирается через вызов configure и make. Предположим, вы решили что-то добавить: TCG-бекенд, реализацию потоков, что-то ещё. Не спешите радоваться/ужасаться (нужное подчеркнуть) перспективе общения с Autoconf — на самом деле, configure у QEMU, по всей видимости, самописный и не из чего не генерируется.

WebAssembly

Так что же это за штука — WebAssembly (он же WASM)? Это замена Asm.js, теперь уже не прикидывающаяся валидным JavaScript кодом. Напротив, оно сугубо бинарное и оптимизированное, и даже просто записать в него целое число не очень-то и просто: оно для компактности хранится в формате LEB128.

Возможно, вы слышали об алгоритме relooping для Asm.js — это восстановление «высокоуровневых» инструкций управления потоком выполнения (то есть if-then-else, циклы и т.д.), под которые заточены JS-движки, из низкоуровневого LLVM IR, более близкого к машинному коду, выполняемому процессором. Естественно, промежуточное представление QEMU ближе ко второму. Казалось бы, вот он, байткод, конец мучений… И тут блоки, if-then-else и циклы!..

И в этом заключается ещё одна причина, почему полезен Binaryen: он, естественно, может принимать высокоуровневые блоки, близкие к тому, что будет сохранено в WASM. Но также он может выдавать код из графа базовых блоков и переходов между ними. Ну а о том, что он скрывает за удобным C/C++ API формат хранения WebAssembly, я уже сказал.

TCG (Tiny Code Generator)

TCG изначально был бекендом для компилятора C. Потом он, видимо, не выдержал конкуренции с GCC, но в итоге нашёл своё место в составе QEMU в качестве механизма кодогенерации под хостовую платформу. Также есть и TCG-бекенд, генерирующий некий абстрактный байткод, который тут же и исполняет интерпретатор, но от его использования я решил уйти в этот раз. Впрочем, тот факт, что в QEMU уже есть возможность включить переход на сгенерированный TB через функцию tcg_qemu_tb_exec, мне оказался очень кстати.

Чтобы добавить новый TCG-бекенд в QEMU, нужно создать подкаталог tcg/<имя архитектуры> (в данном случае, tcg/binaryen), а в нём два файла: tcg-target.h и tcg-target.inc.c и прописать всё это дело в configure. Можно положить туда и другие файлы, но, как можно догадаться из названий этих двух, они оба будут куда-то включаться: один как обычный заголовочный файл (он инклудится в tcg/tcg.h, а тот уже в другие файлы в каталогах tcg, accel и не только), другой — только как code snippet в tcg/tcg.c, зато он имеет доступ к его static-функциям.

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

Файл tcg-target.h содержит преимущественно настройки в виде #define-ов:

• сколько регистров и какой ширины есть на целевой архитектуре (у нас — сколько хотим, столько и есть — вопрос больше того, что будет генерироваться в более эффективный код браузером на «совсем целевой» архитектуре...)
• выравнивание хостовых инструкций: на x86, да и в TCI, инструкции вообще не выравниваются, я же собираюсь класть в буфер кода и не инструкции вовсе, а указатели на структуры библиотеки Binaryen, поэтому скажу: 4 байта
• какие опциональные инструкции может генерировать бекенд — включаем всё, что найдём в Binaryen, остальное пусть акселератор разбивает на более простые сам
• какой приблизительно размер TLB-кеша запрашивает бекенд. Дело в том, что в QEMU всё по-серьёзному: хотя и есть функции-помощники, осуществляющие load/store с учётом гостевого MMU (а куда сейчас без него?), но свой кеш трансляции они сохраняют в виде структуры, обработку которой удобно встраивать прямо в блоки трансляции. Вопрос же в том, какое смещение в этой структуре наиболее эффективно обрабатывается маленькой и быстрой последовательностью команд
• здесь же можно подкрутить назначение одного-двух зарезервированных регистров, включить вызов TB через функцию и опционально описать пару мелких inline-функций вроде flush_icache_range (но это не наш случай)

Файл tcg-target.inc.c, естественно, обычно намного больше по размеру и содержит несколько обязательных функций:

• инициализация, указывающая в том числе ограничения на то, какая инструкция с какими операндами может работать. Нагло скопирована мною из другого бекенда
• функция, принимающая одну инструкцию внутреннего байткода
• сюда же можно положить вспомогательные функции, а также здесь можно пользоваться статическими функциями из tcg/tcg.c

Для себя я избрал следующую стратегию: в первых словах очередного блока трансляции я записывал четыре указателя: метку начала (некое значение в окрестности 0xFFFFFFFF, по которому определялось текущее состояние TB), контекст, сгенерированный модуль, и magic number для отладки. Сначала метка выставлялась в 0xFFFFFFFF - n, где n — небольшое положительное число, и при каждом выполнении через интерпретатор увеличивалась на 1. Когда она доходила до 0xFFFFFFFE, происходила компиляция, модуль сохранялся в таблице функций, импортированной в небольшой «запускатор», в который и уходило выполнение из tcg_qemu_tb_exec, а модуль удалялся из памяти QEMU.

Перефразируя классику, «Костыль, как много в этом звуке для сердца прогера сплелось...». Тем не менее, память куда-то утекала. Причём это была память, управляемая QEMU! У меня был код, который при записи очередной инструкции (ну, то есть, указателя) удалял ту, ссылка на которую была на этом месте ранее, но это не помогало. Вообще-то, в простейшем случае QEMU выделяет при старте память и пишет туда генерируемый код. Когда буфер заканчивается, код выкидывается, и на его место начинает записываться следующий.

Поизучав код, я понял, что костыль с magic number позволял не упасть на разрушении кучи, освободив что-нибудь не то на неинициализированном буфере при первом проходе. Но кто переписывает буфер в обход моей функции потом? Как и советуют разработчики Emscripten, упёршись в проблему, я портировал получившийся код обратно в нативное приложение, натравил на него Mozilla Record-Replay… В общем, в итоге я понял простую вещь: для каждого блока выделяется struct TranslationBlock с его описанием. Угадайте, где… Правильно, непосредственно перед блоком прямо в буфере. Осознав это, я решил завязывать с костылями (хотя бы некоторыми), и просто выкинул magic number, а оставшиеся слова перенёс в struct TranslationBlock, заведя односвязный список, по которому можно быстро пройтись при сбросе кеша трансляции, и освободить память.

Некоторые костыли остались: например, помеченные указатели в буфере кода — часть из них просто являются BinaryenExpressionRef, то есть смотрят на выражения, которые нужно линейно положить в генерируемый базовый блок, часть — условие перехода между ББ, часть — куда переходить. Ну и есть уже подготовленные блоки для Relooper, которые нужно соединить по условиям. Чтобы их различать, используется предположение, что все они выровнены хотя бы на четыре байта, поэтому можно спокойно использовать младшие два бита под метку, нужно только не забывать её убирать при необходимости. Кстати, такие метки уже используются в QEMU для обозначения причины выхода из цикла TCG.

Использование Binaryen

Модули в WebAssembly содержат функции, каждая из которых содержит тело, представляющее из себя выражение. Выражения — это унарные и бинарные операции, блоки, состоящие из списков других выражений, control flow и т.д. Как я уже говорил, control flow здесь организуется именно как высокоуровневые ветвления, циклы, вызовы функций и т.д. Аргументы функциям передаются не на стеке, а явно, как и в JS. Есть и глобальные переменные, но я их не использовал, поэтому про них не расскажу.

Также у функций есть нумерованные с нуля локальные переменные, имеющие тип: int32 / int64 / float / double. При этом первые n локальных переменных — это переданные функции аргументы. Обратите внимание, что хоть здесь всё и не совсем низкоуровневое в плане потока управления, но целые числа всё же не несут в себе признак «знаковое/беззнаковое»: как будет вести себя число, зависит от кода операции.

Вообще говоря, Binaryen предоставляет простой C-API: вы создаёте модуль, в нём создаёте выражения — унарные, бинарные, блоки из других выражений, control flow и т.д. Потом вы создаёте функцию, в качестве тела которой нужно указать выражение. Если у вас, как и у меня, есть низкоуровневый граф переходов — вам поможет компонент relooper. Насколько я понимаю, использовать высокоуровневое управление потоком выполнения в блоке можно, покуда оно не выходит за пределы блока — то есть сделать внутреннее ветвление fast path / slow path внутри встроенного кода обработки TLB-кеша можно, но вмешиваться в «наружный» поток управления — нет. Когда вы освобождаете relooper, освобождаются его блоки, когда освобождаете модуль — исчезают выражения, функции и т.д., выделенные в его арене.

Впрочем, если вы хотите интерпретировать код на ходу без лишних созданий и удалений экземпляра интерпретатора, может иметь смысл вынести эту логику в файл на C++, и оттуда непосредственно управлять всем C++ API библиотеки, минуя готовые обёртки.

Таким образом, чтобы сгенерировать код, нужно

// настроить глобальные параметры (можно поменять потом)
BinaryenSetAPITracing(0);

BinaryenSetOptimizeLevel(3);
BinaryenSetShrinkLevel(2);

// создать модуль
BinaryenModuleRef MODULE = BinaryenModuleCreate();

// описать типы функций (как создаваемых, так и вызываемых)
helper_type  BinaryenAddFunctionType(MODULE, "helper-func", BinaryenTypeInt32(), int32_helper_args, ARRAY_SIZE(int32_helper_args));
// (int23_helper_args приоб^Wсоздаются отдельно)

// сконструировать супер-мега выражение
// ... ну тут уж вы как-нибудь сами :)

// потом создать функцию
BinaryenAddFunction(MODULE, "tb_fun", tb_func_type, func_locals, FUNC_LOCALS_COUNT, expr);
BinaryenAddFunctionExport(MODULE, "tb_fun", "tb_fun");
...
BinaryenSetMemory(MODULE, (1 << 15) - 1, -1, NULL, NULL, NULL, NULL, NULL, 0, 0);
BinaryenAddMemoryImport(MODULE, NULL, "env", "memory", 0);
BinaryenAddTableImport(MODULE, NULL, "env", "tb_funcs");

// запросить валидацию и оптимизацию при желании
assert (BinaryenModuleValidate(MODULE));
BinaryenModuleOptimize(MODULE);

… если что забыл — извините, это просто чтобы представлять масштабы, а подробности — они в документации.

А теперь начинается крекс-фекс-пекс, примерно такой:

static char buf[1 << 20];
BinaryenModuleOptimize(MODULE);
BinaryenSetMemory(MODULE, 0, -1, NULL, NULL, NULL, NULL, NULL, 0, 0);
int sz = BinaryenModuleWrite(MODULE, buf, sizeof(buf));
BinaryenModuleDispose(MODULE);
EM_ASM({
  var module = new WebAssembly.Module(new Uint8Array(wasmMemory.buffer, $0, $1));
  var fptr = $2;
  var instance = new WebAssembly.Instance(module, {
      'env': {
          'memory': wasmMemory,
          // ...
      }
  );
  // и вот уже у вас есть instance!
}, buf, sz);

Чтобы как-то связать между собой мир QEMU и JS и при этом заходить в скомпилированные функции быстро, был создан массив (таблица функций для импорта в запускатор), и туда клались сгенерированные функции. Чтобы быстро вычислять индекс, в качестве него изначально использовался индекс нулевого слова translation block, но потом индекс, вычисленный по такой формуле стал просто вписываться в поле в struct TranslationBlock.

Кстати, демо (пока что с мутной лицензией) работает нормально только в Firefox. Разработчики Chrome были как-то не готовы к тому, что кто-то захочет создавать более тысячи инстансов модулей WebAssembly, поэтому просто выделяли по гигабайту виртуального адресного пространства на каждый...

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

Напоследок загадка: вы собрали бинарник на 32-битной архитектуре, но код через операции с памятью лезет из Binaryen, куда-то на стек или ещё куда-то в верхние 2 Гб 32-битного адресного пространства. Проблема в том, что с точки зрения Binaryen это обращение по слишком большому результирующему адресу. Как это обойти?

// 2gbubble.c
// Usage: LD_PRELOAD=2gbubble.so <program>

#include <sys/mman.h>
#include <assert.h>

void __attribute__((constructor)) constr(void)
{
  assert(MAP_FAILED != mmap(1u >> 31, (1u >> 31) - (1u >> 20), PROT_NONE, MAP_ANONYMOUS | MAP_PRIVATE, -1, 0));
}