Хабрахабр

QEMU.js: теперь по-серьёзному и с WASM

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

Задачи

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

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

4. Первой моей ошибкой было ответвить свою версию от upstream-версии 2. Тогда мне казалось это хорошей идеей: если point release существует, значит он, наверное, стабильнее простого 2. 1. А поскольку я планировал добавить изрядное количество своих багов, то чужие мне были ну вообще не нужны. 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 так написан...». Впрочем, на нормальныхRISC-архитектурах, насколько я понимаю, типичной ситуацией является необходимость явно сбросить кеш инструкций для перегенерированного кода — если это и не то, что нам нужно, то, во всяком случае, близко. Как говорится, «Собрал Генту, да не ту»: код-то, конечно, бинарный, но управление на него просто так не передать — его нужно явным образом запихнуть в браузер на компиляцию, получив в результате некий объект из мира JS, который ещё нужно куда-то сохранить. Кроме того, из прошлой своей попытки я усвоил, что управление на середину блока трансляции вроде как не передаётся, поэтому байткод, интерпретируемый с любого смещения, нам особо и не нужен, и можно просто генерировать по функции на TB.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

WebAssembly

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

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

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

TCG (Tiny Code Generator)

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

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

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

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

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

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

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

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

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

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

Потом вы создаёте функцию, в качестве тела которой нужно указать выражение. Вообще говоря, Binaryen предоставляет простой C-API: вы создаёте модуль, в нём создаёте выражения — унарные, бинарные, блоки из других выражений, control flow и т.д. Насколько я понимаю, использовать высокоуровневое управление потоком выполнения в блоке можно, покуда оно не выходит за пределы блока — то есть сделать внутреннее ветвление fast path / slow path внутри встроенного кода обработки TLB-кеша можно, но вмешиваться в «наружный» поток управления — нет. Если у вас, как и у меня, есть низкоуровневый граф переходов — вам поможет компонент relooper. Когда вы освобождаете 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( ); // и вот уже у вас есть instance!
}, buf, sz);

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

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

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

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

По-админски

Вопрос только в том, сколько будет занято: 1 или 2 Gb. Я это в итоге не тестировал, но первая мысль была «А что, если поставить 32-битный Linux?» Тогда верхняя часть адресного пространства будет занята ядром.

По-программистски (вариант для практиков)

Я сам не понимаю, почему оно работает — там же уже должен быть стек. Надуем пузырь в верхней части адресного пространства. Но «мы практики: у нас всё работает, но никто не знает почему...».

// 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));
}

… с Valgrind-ом, правда, не совместимо, но, к счастью, Valgrind сам очень эффективно оттуда всех вытесняет 🙂

Возможно, кто-то даст лучшее объяснение, как работает этот мой код...

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть