Колись давно я заради сміху вирішив довести оборотність процесу та навчитися генерувати 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, а тут, раптово згадка у треді у контексті, «Ось він щось подібне робив, може скаже щось». Йшлося про використання спорідненої Emscripten бібліотеки до створення WASM JIT. Ну я й сказав, що у вас там ліцензія Apache 2.0, а QEMU як єдине ціле розповсюджується під GPLv2 і вони не дуже сумісні. Раптом виявилось, що ліцензію можна якось виправити (Не знаю: може, поміняти, може, подвійне ліцензування, може, ще щось…). Це мене, звичайно, втішило, бо я вже кілька разів на той час придивлявся до WebAssembly, і мені було якось сумно і незрозуміло. Тут була бібліотека, яка і базові блоки з графом переходів зжере, і байткод видасть, і навіть сама його запустить в інтерпретаторі, якщо буде потрібно.
Потім ще було у списку розсилки QEMU, але це вже скоріше до питання, «А кому воно взагалі треба?». А воно, раптово, Виявилося треба. Як мінімум, можна наскрести такі можливості використання, якщо воно більш-менш спритно працюватиме:
- запуск чогось навчального взагалі без встановлення
- віртуалізація на iOS, де за чутками єдина програма, що має право на кодогенерацію на льоту - це JS-движок (а чи правда це?)
- демонстрація міні-ОС - однодискетні, вбудовані, всякі прошивки і т.д.
Особливості браузерного середовища виконання
Як я вже казав, QEMU зав'язаний на багатопоточність, а в браузері її немає. Ну, тобто як ні… Спочатку її не було взагалі, потім з'явилися WebWorkers — наскільки я розумію, це багатопоточність, яка базується на передачі повідомлень без змінних, що змінюються спільно. Звичайно, це створює значні проблеми при портуванні існуючого коду, заснованого на shared memory моделі. Потім під тиском громадськості було реалізовано і воно під назвою SharedArrayBuffers. Її поступово ввели, відсвяткували її запуск у різних браузерах, потім відсвяткували новий рік, а потім Meltdown… Після чого дійшли висновку, що загрубуй-не загрублюй вимір часу, а за допомогою shared memory та потоку, що інкрементує лічильник, все одно . Так і відключили багатопоточність із загальною пам'яттю. Начебто її потім включали назад, але, як стало зрозуміло з першого експерименту, і без неї життя є, а раз так, то спробуємо зробити, не закладаючись на багатопоточність.
Друга особливість полягає у неможливості низькорівневих маніпуляцій зі стеком: не можна просто взяти, зберегти поточний контекст і перейти на новий з новим стеком. Стек дзвінків керується віртуальною машиною JS. Здавалося б, у чому проблема, якщо ми все одно вирішили справлятися з колишніми потоками повністю вручну? Справа в тому, що блокове введення-виведення в QEMU реалізовано через корутини, і ось тут би нам і стали в нагоді низькорівневі маніпуляції стеком. На щастя, Emscipten вже містить механізм для асинхронних операцій, навіть два: и . Перший працює через значне роздування 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 кодом. Навпаки, воно суто бінарне і оптимізоване, і навіть просто записати в нього ціле число не дуже просто: воно для компактності зберігається у форматі .
Можливо, ви чули про алгоритм 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
Модулі в WebAsembly містять функції, кожна з яких містить тіло, що представляє собою вираз. Вирази - це унарні та бінарні операції, блоки, що складаються зі списків інших виразів, control flow і т.д. Як я вже казав, control flow тут організується саме як високорівневі розгалуження, цикли, виклики функцій тощо. Аргументи функцій передаються не так на стеку, а явно, як і в JS. Є й глобальні змінні, але я їх не використав, тож про них не розповім.
Також у функцій є нумеровані з нуля локальні змінні, що мають тип: int32/int64/float/double. У цьому перші n локальних змінних — це передані функції аргументи. Зверніть увагу, що хоч тут все і не зовсім низькорівневе в плані потоку управління, але цілі числа все ж таки не несуть у собі ознаку «знакове/беззнакове»: як поводитиметься число, залежить від коду операції.
Взагалі кажучи, Binaryen надає : ви створюєте модуль, в ньому створюєте вирази - унарні, бінарні, блоки з інших виразів, 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 це звернення за надто великою результуючою адресою. Як це оминути?
Адмінськи
Я це не тестував, але перша думка була «А що, якщо поставити 32-бітний Linux?» Тоді верхня частина адресного простору буде зайнята ядром. Питання тільки в тому, скільки буде зайнято: 1 або 2 Гб.
По-програмістськи (варіант для практиків)
Надує міхур у верхній частині адресного простору. Я сам не розумію, чому воно працює — там же вже має бути стек. Але «ми практики: у нас все працює, але ніхто не знає, чому…».
// 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 сам дуже ефективно звідти всіх витісняє 🙂
Можливо, хтось дасть найкраще пояснення, як працює цей мій код.
Джерело: habr.com