QEMU.js: вече сериозно и с WASM

Едно време реших за забавление доказват обратимостта на процеса и научете как да генерирате JavaScript (по-точно Asm.js) от машинен код. За експеримента беше избран QEMU и известно време по-късно беше написана статия на Habr. В коментарите ме посъветваха да преправя проекта в WebAssembly и дори да се откажа почти завършен Някак си не исках проекта... Работата вървеше, но много бавно и сега, наскоро в тази статия се появи коментар по темата „И как свърши всичко?“ В отговор на моя подробен отговор чух „Това звучи като статия“. Е, ако може, ще има статия. Може би някой ще го намери за полезно. От него читателят ще научи някои факти за дизайна на бекенда за генериране на код QEMU, както и как да напише компилатор Just-in-Time за уеб приложение.

задачи

Тъй като вече бях научил как да „по някакъв начин“ пренасям QEMU към JavaScript, този път беше решено да го направя разумно и да не повтарям стари грешки.

Грешка номер едно: разклоняване от освобождаване на точка

Първата ми грешка беше да разклоня моята версия от горната версия 2.4.1. Тогава ми се стори добра идея: ако точковото освобождаване съществува, то вероятно е по-стабилно от простото 2.4 и още повече от клона master. И тъй като планирах да добавя доста мои собствени грешки, изобщо нямах нужда от чужди. Сигурно така се е получило. Но ето нещо: QEMU не стои на едно място и в някакъв момент дори обявиха оптимизация на генерирания код с 10 процента.„Да, сега ще замръзна“, помислих си и се счупих. Тук трябва да направим едно отклонение: поради еднонишковия характер на QEMU.js и факта, че оригиналният QEMU не предполага липсата на многопоточност (т.е. възможността за едновременно управление на няколко несвързани кодови пътеки, и не само „използване на всички ядра“) е критично за него, основните функции на нишките, които трябваше да „изключа“, за да мога да извикам отвън. Това създаде някои естествени проблеми по време на сливането. Въпреки това, фактът, че някои от промените от бранша master, с които се опитах да обединя кода си, също бяха избрани като череша в освобождаването на точката (и следователно в моя клон) също вероятно нямаше да добавят удобство.

Като цяло реших, че все още има смисъл да изхвърля прототипа, да го разглобя на части и да създам нова версия от нулата на базата на нещо по-свежо и сега от master.

Грешка номер две: TLP методология

По същество това не е грешка, като цяло това е просто характеристика на създаване на проект в условията на пълно неразбиране както на „къде и как да се движим?“, И като цяло „ще стигнем ли там?“ В тези условия тромаво програмиране беше оправдан вариант, но, естествено, не исках да го повтарям излишно. Този път исках да го направя мъдро: атомни ангажименти, съзнателни промени в кода (а не „низване на произволни символи заедно, докато се компилира (с предупреждения)“, както Линус Торвалдс веднъж каза за някого, според Wikiquote) и т.н.

Грешка номер три: да влезеш във водата, без да знаеш брода

Все още не съм се отървал напълно от това, но сега реших изобщо да не следвам пътя на най-малкото съпротивление и да го направя „като възрастен“, а именно да напиша своя TCG бекенд от нулата, за да не за да трябва да кажа по-късно: „Да, това е, разбира се, бавно, но не мога да контролирам всичко - така се пише TCI...“ Освен това първоначално това изглеждаше като очевидно решение, тъй като Генерирам двоичен код. Както се казва, „Гент се събрау, но не и този”: кодът, разбира се, е двоичен, но контролът не може просто да бъде прехвърлен към него - той трябва изрично да бъде поставен в браузъра за компилация, което води до определен обект от света на JS, който все още трябва да да бъдат запазени някъде. Въпреки това, при нормални RISC архитектури, доколкото разбирам, типична ситуация е необходимостта от изрично нулиране на кеша на инструкциите за регенериран код - ако това не е това, от което се нуждаем, тогава във всеки случай е близо. В допълнение, от последния ми опит научих, че контролът изглежда не се прехвърля в средата на блока за превод, така че всъщност не се нуждаем от байткод, интерпретиран от всяко отместване, и можем просто да го генерираме от функцията на TB .

Дойдоха и ритаха

Въпреки че започнах да пренаписвам кода още през юли, незабелязано се прокрадна магически удар: обикновено писмата от GitHub пристигат като известия за отговори на проблеми и заявки за изтегляне, но тук, внезапно споменаване в темата Binaryen като бекенд на qemu в контекста "Той направи нещо подобно, може би ще каже нещо." Говорихме за използване на свързаната библиотека на Emscripten Бинариен за създаване на WASM JIT. Е, казах, че там имате лиценз за Apache 2.0 и QEMU като цяло се разпространява под GPLv2 и не са много съвместими. Изведнъж се оказа, че лиценз може да бъде оправи го някак (Не знам: може би го променя, може би двойно лицензиране, може би нещо друго...). Това, разбира се, ме зарадва, защото по това време вече се бях вгледал внимателно двоичен формат WebAssembly и ми стана някак тъжно и неразбираемо. Имаше и библиотека, която поглъщаше основните блокове с графиката на прехода, произвеждаше байт кода и дори го изпълняваше в самия интерпретатор, ако е необходимо.

Тогава имаше още писмо в пощенския списък на QEMU, но това е повече за въпроса „Кой изобщо има нужда от това?“ И това е внезапно, оказа се, че е необходимо. Като минимум можете да съберете следните възможности за използване, ако работи повече или по-малко бързо:

• стартиране на нещо образователно без никаква инсталация
• виртуализация на iOS, където според слуховете единственото приложение, което има право да генерира код в движение, е JS двигател (вярно ли е?)
• демонстрация на мини-ОС - еднофлопи, вградена, всякакъв фърмуер и др...

Функции за изпълнение на браузъра

Както вече казах, QEMU е обвързан с многопоточност, но браузърът го няма. Е, това е, не... Първоначално изобщо не съществуваше, след това се появиха WebWorkers - доколкото разбирам, това е многопоточност, базирана на предаване на съобщения без споделени променливи. Естествено, това създава значителни проблеми при пренасяне на съществуващ код, базиран на модела на споделена памет. След това, под обществен натиск, беше реализиран и под името SharedArrayBuffers. Той беше въведен постепенно, отпразнуваха стартирането му в различни браузъри, след това празнуваха Нова година, а след това Meltdown... След което стигнаха до извода, че грубо или грубо измерването на времето, но с помощта на споделена памет и нишка, увеличаваща брояча, всичко е същото ще се получи доста точно. Така че деактивирахме многопоточността със споделена памет. Изглежда, че по-късно са го включили отново, но както стана ясно от първия експеримент, има живот и без него и ако е така, ще се опитаме да го направим, без да разчитаме на многопоточност.

Втората характеристика е невъзможността за манипулации на ниско ниво със стека: не можете просто да вземете, запазите текущия контекст и да превключите към нов с нов стек. Стекът за повиквания се управлява от JS виртуалната машина. Изглежда, какъв е проблемът, след като все пак решихме да управляваме предишните потоци напълно ръчно? Факт е, че блок I/O в QEMU се изпълнява чрез съпрограми и това е мястото, където манипулациите на стека на ниско ниво биха били полезни. За щастие, Emscipten вече съдържа механизъм за асинхронни операции, дори два: Асинцифицирайте и Emterpreter. Първият работи чрез значително раздуване на генерирания JavaScript код и вече не се поддържа. Вторият е текущият "правилен начин" и работи чрез генериране на байт код за родния интерпретатор. Работи, разбира се, бавно, но не раздува кода. Вярно е, че поддръжката на съпрограми за този механизъм трябваше да бъде предоставена независимо (вече имаше съпрограми, написани за Asyncify и имаше имплементация на приблизително същия API за Emterpreter, просто трябваше да ги свържете).

В момента все още не съм успял да разделя кода на един, компилиран в WASM и интерпретиран с помощта на Emterpreter, така че блоковите устройства все още не работят (вижте в следващата серия, както се казва...). Тоест, в крайна сметка трябва да получите нещо като това смешно многослойно нещо:

• интерпретиран блок I/O. Е, наистина ли очаквахте емулирана NVMe с естествена производителност? 🙂
• статично компилиран основен QEMU код (преводач, други емулирани устройства и т.н.)
• динамично компилиран гост код в WASM

Характеристики на източниците на QEMU

Както вероятно вече се досещате, кодът за емулиране на гост архитектури и кодът за генериране на инструкции за хост машина са разделени в QEMU. Всъщност дори е малко по-сложно:

• има архитектури за гости
• има ускорители, а именно KVM за хардуерна виртуализация на Linux (за гост и хост системи, съвместими една с друга), TCG за генериране на JIT код навсякъде. Започвайки с QEMU 2.9, се появи поддръжка за стандарта за хардуерна виртуализация HAXM в Windows (детайлите)
• ако се използва TCG, а не хардуерна виртуализация, тогава той има отделна поддръжка за генериране на код за всяка хост архитектура, както и за универсалния интерпретатор
• ... и около всичко това - емулирани периферни устройства, потребителски интерфейс, миграция, запис-повтаряне и т.н.

Между другото, знаете ли: QEMU може да емулира не само целия компютър, но и процесора за отделен потребителски процес в ядрото на хоста, който се използва например от AFL fuzzer за двоично оборудване. Може би някой би искал да пренесе този режим на работа на QEMU към JS? 😉

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

WebAssembly

И така, какво е това нещо, наречено WebAssembly (известен още като WASM)? Това е заместител на Asm.js, който вече не се представя за валиден JavaScript код. Напротив, той е чисто двоичен и оптимизиран и дори простото записване на цяло число в него не е много просто: за компактност то се съхранява във формат LEB128.

Може да сте чували за алгоритъма за повторен цикъл за Asm.js - това е възстановяването на инструкции за контрол на потока от „високо ниво“ (т.е. if-then-else, цикли и т.н.), за които са проектирани JS двигателите, от LLVM IR на ниско ниво, по-близо до машинния код, изпълняван от процесора. Естествено, междинното представяне на QEMU е по-близо до второто. Изглежда, че тук е байткодът, краят на мъките... И тогава има блокове, if-then-else и цикли!..

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

TCG (генератор на малки кодове)

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 и не само), другият - само като кодов фрагмент в tcg/tcg.c, но има достъп до статичните си функции.

Решавайки, че ще отделя твърде много време за подробни проучвания за това как работи, аз просто копирах „скелетите“ на тези два файла от друга имплементация на бекенда, честно посочвайки това в заглавката на лиценза.

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

• колко регистри и каква ширина има на целевата архитектура (имаме колкото искаме, колкото искаме - въпросът е повече за това какво ще бъде генерирано в по-ефективен код от браузъра на „напълно целевата“ архитектура ...)
• подравняване на инструкциите на хоста: на x86 и дори в TCI, инструкциите изобщо не са подравнени, но аз ще поставя в кодовия буфер не инструкции изобщо, а указатели към библиотечните структури на Binaryen, така че ще кажа: 4 байтове
• какви незадължителни инструкции може да генерира бекендът - ние включваме всичко, което намерим в Binaryen, оставяме ускорителя сам да раздели останалите на по-прости
• Какъв е приблизителният размер на TLB кеша, поискан от бекенда. Факт е, че в QEMU всичко е сериозно: въпреки че има помощни функции, които извършват зареждане/съхраняване, като вземат предвид гост 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 заделя памет при стартиране и записва генерирания код там. Когато буферът свърши, кодът се изхвърля и на негово място започва да се записва следващият.

След като проучих кода, разбрах, че трикът с магическото число ми позволява да не се проваля при унищожаване на купчина чрез освобождаване на нещо грешно в неинициализиран буфер при първото преминаване. Но кой пренаписва буфера, за да заобиколи моята функция по-късно? Както съветват разработчиците на Emscripten, когато се натъкнах на проблем, пренесох получения код обратно в родното приложение, зададох Mozilla Record-Replay върху него... Като цяло, в крайна сметка разбрах едно просто нещо: за всеки блок, а struct TranslationBlock с неговото описание. Познайте къде... Точно така, точно преди блока точно в буфера. Осъзнавайки това, реших да спра да използвам патерици (поне някои) и просто изхвърлих магическото число и прехвърлих останалите думи на struct TranslationBlock, създавайки единично свързан списък, който може бързо да бъде обходен, когато кешът за превод се нулира, и освобождаване на памет.

Остават някои патерици: например маркирани указатели в кодовия буфер - някои от тях са просто BinaryenExpressionRef, тоест те разглеждат изразите, които трябва да бъдат линейно поставени в генерирания основен блок, част е условието за преход между BB, част е къде да отидете. Е, вече има готови блокове за Relooper, които трябва да бъдат свързани според условията. За да ги разграничим, се използва предположението, че всички те са подравнени с поне четири байта, така че можете безопасно да използвате най-малко значимите два бита за етикета, просто трябва да запомните да го премахнете, ако е необходимо. Между другото, такива етикети вече се използват в QEMU, за да посочат причината за излизане от цикъла TCG.

Използване на Binaryen

Модулите в WebAssembly съдържат функции, всяка от които съдържа тяло, което е израз. Изразите са унарни и двоични операции, блокове, състоящи се от списъци с други изрази, контролен поток и т.н. Както вече казах, контролният поток тук е организиран точно като разклонения на високо ниво, цикли, извиквания на функции и т.н. Аргументите към функциите не се предават в стека, а изрично, точно както в JS. Има и глобални променливи, но не съм ги използвал, така че няма да ви разказвам за тях.

Функциите също имат локални променливи, номерирани от нула, от тип: int32 / int64 / float / double. В този случай първите n локални променливи са аргументите, предадени на функцията. Моля, обърнете внимание, че въпреки че всичко тук не е съвсем на ниско ниво по отношение на контролния поток, целите числа все още не носят атрибута „подписан/неподписан“: как се държи числото зависи от кода на операцията.

Най-общо казано, Binaryen предоставя прост C-API: създавате модул, в него създаване на изрази - унарни, двоични, блокове от други изрази, контрол на потока и др. След това създавате функция с израз като тяло. Ако и вие като мен имате графика на преход от ниско ниво, компонентът relooper ще ви помогне. Доколкото разбирам, е възможно да се използва контрол на високо ниво на потока на изпълнение в блок, стига той да не излиза извън границите на блока - тоест възможно е да се направи вътрешен бърз път / бавен разклоняване на пътя вътре в кода за обработка на вградения 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);

... ако съм забравил нещо, съжалявам, това е само за представяне на мащаба, а подробностите са в документацията.

И сега започва crack-fex-pex, нещо като това:

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 и в същото време да се осъществява бърз достъп до компилираните функции, беше създаден масив (таблица с функции за импортиране в стартовия панел) и генерираните функции бяха поставени там. За бързо изчисляване на индекса първоначално беше използван индексът на блока за превод на нулева дума, но след това индексът, изчислен с помощта на тази формула, започна просто да се вписва в полето в struct TranslationBlock.

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

Това е всичко за сега. Може би ще има друга статия, ако някой се интересува. А именно остава поне само накарайте блоковите устройства да работят. Може също така да има смисъл компилирането на модулите на WebAssembly да бъде асинхронно, както е обичайно в света на JS, тъй като все още има интерпретатор, който може да направи всичко това, докато собственият модул не бъде готов.

И накрая една гатанка: сте компилирали двоичен файл на 32-битова архитектура, но кодът чрез операции с паметта се изкачва от Binaryen, някъде в стека или някъде другаде в горните 2 GB на 32-битовото адресно пространство. Проблемът е, че от гледна точка на Binaryen това е достъп до твърде голям резултатен адрес. Как да заобиколите това?

По админски начин

В крайна сметка не тествах това, но първата ми мисъл беше „Ами ако инсталирах 32-битов Linux?“ Тогава горната част на адресното пространство ще бъде заета от ядрото. Единственият въпрос е колко ще бъде заето: 1 или 2 Gb.

По начин на програмист (опция за практици)

Нека издухаме балон в горната част на адресното пространство. Аз самият не разбирам защо работи - там вече трябва да има стек. Но „ние сме практици: всичко работи за нас, но никой не знае защо...“

// 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 много ефективно изтласква всички оттам :)

Може би някой ще даде по-добро обяснение как работи този мой код...

Източник: www.habr.com