Преди време реших за смях да докаже обратимостта на процеса и да науча как да генерирам JavaScript (по-точно, Asm.js) от машинен код. За експеримента беше избран QEMU, и известно време по-късно написах статия в Хабр. В коментарите ми предложиха да пренаправя проекта на WebAssembly, но не ми се искаше да изоставям практически завършения проект... Работата напредваше, но много бавно, и ето, наскоро в статията се появи въпросът «Какво стана с всичко това?». На моят подробен отговор получих «Това заслужава статия». Ами, щом заслужава, значи ще има статия. Може би на някого ще му бъде полезно. От нея читателят ще научи някои факти за устройството на бекенда за кодогенерация на QEMU, както и как да напише Just-in-Time компилатор за уеб приложение.
Задачи
Тъй като вече бях научил как да портна QEMU на JavaScript по-скоро по несръчен начин, този път реших да правя нещата по правилния начин и да не повтарям стари грешки.
Грешка номер едно: отклоняване от point release
Първата ми грешка беше да отклоня своята версия от upstream версия 2.4.1. Тогава ми се стори добра идея: ако точковото издание съществува, значи е вероятно по-стабилно от обикновеното 2.4 и особено от клоновете master. И тъй като планирах да добавя значително количество от собствените си грешки, чуждите наистина не ми бяха нужни. Така се получи, вероятно. Но проблемът е: QEMU не стои на място, и в някой момент дори анонсираха оптимизация на генерирания код с 10%. «Аха, сега ще внедря» помислих аз и се провалих. Тук трябва да направя отстъпление: във връзка с еднопоточния характер на QEMU.js и факта, че оригиналният QEMU не предвижда липса на многопоточност (т.е. е критично за него възможността за едновременно работа на няколко несвързани code path, а не просто «да се използват всичките ядра»), основните функции на потоките трябваше да бъдат «извънземни» за възможност за извикване от външни източници. Това създаде някои естествени проблеми при сливането. Обаче фактът, че част от промените от клона master, с който се опитах да слея своя код, също бяха cherry picked в точковото издание (а следователно и в моя клон), вероятно не би добавило удобство.
В крайна сметка реших, че все пак прототипът е смислено да бъде изхвърлен, да бъде разбран на части и да бъде построена нова версия от нулата, базирана на нещо по-ново и сега вече от master.
Грешка номер две: TLP методология
Всъщност това не е грешка, а по-скоро особеност на създаването на проект при условия на пълно непонимание как "къде и как да се движим?", а изобщо "дали изобщо ще стигнем до там?". При тези условия посредствено програмиране , беше оправдано, но, разбира се, не исках да го повтарям без нужда. Този път исках да го направя разумно: атомарни комити, осъзнати промени в кода (а не "свързване на произволни символи, докато заработи (с предупреждения)," както е казал Линус Торвалдс за някого, ако вярваме на Уикицитатника) и т.н.
Грешка номер три: да не знаеш до къде води, а да се хвърляш в дълбокото
От това не съм се отървал напълно и сега, но реших да не тръгвам по най-лесния път, а да действам "по-зряло", а именно да напиша свой TCG бекенд от нулата, за да не казвам после: "Да, разбира се, бавно е, но не мога всичко да контролирам - TCI е така написан...". Освен това, първоначално това изглеждаше като очевидно решение, тъй като аз генерирам бинарен код. Както се казва: "Събрах Генту, но не този": кодът е бинарен, но управлението му не може просто да се предаде - трябва да бъде явно интегрирано в браузъра за компилация, получавайки в резултат обект от света на JS, който трябва някъде да се запази. Въпреки това, на нормалните RISC архитектури, доколкото разбирам, типична ситуация е необходимостта явно да изчистиш кеша на инструкциите за прегенерирания код - ако това не е точно това, което ни трябва, е поне близо. Освен това, от предишния си опит научих, че управлението на средата на преводния блок не може да се предава, така че байт-кодът, който се интерпретира от всяко преместване, не е особено нужен, и можем просто да генерираме функции на TB.
Дойдоха и ритнаха
Въпреки че започнах да пренаписвам кода още през юли, магическият тласък дойде неусетно: обикновено писмата от GitHub идват като уведомления за отговори на въпроси и Pull requests, а тук, внезапно споменаване в темата , в контекста "Той правеше нещо подобно, може да каже нещо". Ставаше въпрос за използването на свързана с Emscripten библиотека за създаване на WASM JIT. И аз казах, че във вас има лиценз Apache 2.0, а QEMU е разпространен като едно цяло под GPLv2, и не са много съвместими. Изведнъж се оказа, че лицензът може по някакъв начин да бъде променен (не знам: може, да сменя, може, двойно лицензиране, може, нещо друго…). Това ме зарадва, защото вече няколко пъти бях погледнал към WebAssembly, и ми беше малко тъжно и неясно. Тук обаче имаше библиотека, която ще изяде основните блокове с графа на преходите, ще издаде байткод и дори ще го стартира в интерпретатора, ако е необходимо.
След това имаше в списъка за разпространение на QEMU, но това вече е по-скоро към въпроса, „А на кого му е нужно?“. А то внезапно, се оказа нужно. Най-малкото, може да се натрупат такива възможности за използване, ако ще работи по-или-иначе бързо:
- стартиране на нещо обучително наистина без инсталация
- виртуализация на iOS, където по слухове единственото приложение, разрешено да генерира код на момента — е JS-движокът (а вярно ли е това?)
- демонстрация на мини-ОС — еднодискови, вградени, всякакви фърмуери и т.н…
Характеристики на браузърната среда за изпълнение
Както вече споменах, QEMU е обвързан с многопоточност, а в браузъра няма такава. Ами, тоест, как да кажа, първоначално я нямаше изобщо, после се появиха WebWorkers — доколкото разбирам, това е многопоточност, основана на предаване на съобщения без съвместно променливи. Естествено, това създава значителни проблеми при преноса на съществуващ код, основан на модела на споделена памет. След това, под натиска на обществеността, беше реализирана и тя под името SharedArrayBuffers. Постепенно я въведоха, отпразнуваха старта ѝ в различни браузъри, после отпразнуваха новата година, а след това Meltdown… След което стигнаха до заключението, че каквито и мерки да вземат, измерването на времето с помощта на споделена памет и поток, инкрементиращ брояч, все пак . Така и изключиха многопоточността със споделена памет. Изглежда, че след това я включиха отново, но, както стана ясно от първия експеримент, и без нея животът продължава, и така, да опитаме да направим, без да разчитаме на многопоточност.
Втората особеност е да се прилагане на низкоуровневите манипулации със стека: не можете просто да вземете, съхраните текущия контекст и да преминете към нов с нов стек. Стекът на повикванията се управлява от виртуалната машина JS. Изглежда, че какъв е проблемът, след като все пак решихме да се справим с бившите потоци напълно ръчно? Проблемът е, че блоковият вход-изход в QEMU е реализиран чрез корутини, и точно тук биха ни свършили работа низкоуровневите манипулации със стека. За щастие, Emscripten вече съдържа механизъм за асинхронни операции, дори два: и . Първият работи чрез значително увеличаване на генерирания JavaScript код и вече не се поддържа. Вторият е текущият "правилен начин" и работи чрез генериране на байткод за собствен интерпретатор. Работи, разбира се, бавно, но всъщност не увеличава кода. Истината е, че поддръжката на корутини за този механизъм трябваше да бъде добавена ръчно (просто трябваше да ги свържем, тъй като вече имаше корутини, написани за Asyncify и имаше реализирана приблизително същата API за Emterpreter).
В момента все още не съм успял да разделя кода на компилируем в WASM и интерпретируем с Emterpreter, така че блоковите устройства все още не работят (вижте в следващите серии, както се казва…). Тоест, в крайна сметка трябва да се получи нещо като забавно слоесто нещо:
- интерпретируем блоков вход-изход. Но какво, наистина ли очаквахте емулиран NVMe с местна производителност? 🙂
- статически компилиран основен код на QEMU (транслятор, останалите емулирани устройства и т.н.)
- динамично компилиран в WASM гост код
Характеристики на изходния код на QEMU
Както вероятно вече се досещате, кодът за емирация на гост архитектури и кодът за генериране на хост машинни инструкции в QEMU са разделени. Всъщност там е дори малко по-сложно:
- има гост архитектури
- има ускорители, а именно KVM за хардуерна виртуализация на Linux (за съвместими помежду си гостови и хостови системи), TCG за JIT-кодогенерация където и да е. От QEMU 2.9 се появи поддръжка на стандарта за хардуерна виртуализация HAXM на Windows ()
- ако се използва TCG, а не хардуерна виртуализация, то той има отделна поддръжка за генериране на код за всяка хостинг архитектура, както и за универсален интерпретатор
- … а около всичко това — емулирана периферия, потребителски интерфейс, миграция, record-replay и т.н.
Между другото, знаете ли: QEMU може да емулира не само целия компютър, но и процесор за отделен потребителски процес в хост ядрото, което използва например fuzzing инструментът AFL за инструментализиране на бинарници. Възможно е някой да иска да портне този режим на работа на QEMU на JS? 😉
Както и повечето отдавна съществуващи свободни програми, QEMU се компилира чрез извикване конфигурирайте и , затова потребителите на Windows трябва да инсталират Cygwin или да се справят сами с Visual Studio и библиотеките.. Да предположим, че сте решили да добавите нещо: TCG бекенд, реализация на потоци, нещо още. Не бързайте да се радвате/ужасявате (нужното подчертаете) от перспективата за работа с Autoconf — всъщност, конфигурирайте в 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 и всичко това в конфигурирайте. Можете да поставите и други файлове там, но, как да се досетим от имената на тези два, и двата ще бъдат включени някъде: единият като обикновен заглавен файл (той се включва в tcg/tcg.h, а той вече в други файлове в директории tcg, accel и не само), другият — само като кодов фрагмент в tcg/tcg.c, но той има достъп до статичните функции на него.
Реших, че ще прекарам твърде много време в детайлно разглеждане как е устроено, затова просто копирах "скелетите" на тези два файла от друга реализация на бекенда, честно уточнявайки това в заглавието на лиценза.
файл 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), контекст, генериран модул и магическо число за отстраняване на грешки. Първоначално етикетът се поставяше на 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 предоставя : вие създавате модул, в него създавате изрази — унарни, бинарни, блокове от други изрази, контролен поток и т.н. След това създавате функция, за което трябва да посочите израза като тяло. Ако и вие, както и аз, имате ниско ниво граф на преходите — компонентът 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,
// ...
}
);
// и вече имате инстанция!
}, buf, sz);За да свържете света на QEMU и JS и за бързо влизане в скомпилираните функции, беше създаден масив (функционална таблица за импортиране в стартер), където се поставяха генерираните функции. Първоначално, за бързо изчисляване на индекса, се използваше индексът на нулевото слово от translation block, но впоследствие индексът, изчислен по такава формула, просто се вписваше в полето в struct TranslationBlock.
Между другото, (понастоящем с неясна лицензия) работи нормално само в Firefox. Разработчиците на Chrome бяха както че не бяха готови за факта, че някой би искал да създаде над хиляда инстанси на WebAssembly модули, затова просто заделяха по един гигабайт виртуално адресно пространство за всеки...
Засега това е всичко. Вероятно ще има още една статия, ако интересува някого. А именно, остава поне само да накарате блочните устройства да работят. Може би има смисъл също така да направим компилацията на WebAssembly модулите асинхронна, както е прието в света на JS, тъй като все пак има интерпретатор, който може да изпълнява всичко това, докато нативният модул не е готов.
Накрая загадка: събрали сте бинарник на 32-битна архитектура, но кодът чрез операции с памет излиза от Binaryen, някъде в стека или някъде другаде в горните 2 GB 32-битно адресно пространство. Проблемът е, че от гледна точка на Binaryen това обращение е по прекалено голям резултативен адрес. Как може да се избегне това?
По-админски
В крайна сметка не го тествал, но първата ми мисъл беше "А какво, ако инсталирам 32-битен Linux?" Тогава горната част на адресното пространство ще бъде заета от ядрото. Въпросът е само колко ще бъде заето: 1 или 2 GB.
По-програмистки (вариант за практици)
Надуваме балон в горната част на адресното пространство. Сам не разбирам защо работи — там би трябвало да има стек. Но "ние сме практици: всичко работи, но никой не знае защо...". вече … с Valgrind, въпреки че не е съвместим, но за щастие Valgrind много ефективно изтласква всички оттам 🙂
// 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));
}Възможно е, някой да даде по-добро обяснение как работи този мой код...
Преди много време на шега реших да докажа обратимостта на процеса и да се науча да генерирам JavaScript (по-точно, Asm.js) от машинен код.
Източник: habr.com
