Kdysi dávno jsem se rozhodl pro zábavu prokázat reverzibilitu procesu a naučit se generovat JavaScript (přesněji Asm.js) ze strojového kódu. Pro experiment byla vybrána QEMU a o něco později byl napsán článek o Habrovi. V komentářích mi bylo doporučeno předělat projekt ve WebAssembly a dokonce i sám skončit téměř hotovo Nějak jsem ten projekt nechtěl... Práce probíhaly, ale velmi pomalu, a teď, nedávno, se v tom článku objevil na téma "Tak jak to všechno skončilo?" V reakci na mou podrobnou odpověď jsem slyšel "To zní jako článek." No, pokud můžete, bude článek. Možná se to někomu bude hodit. Z ní se čtenář dozví některá fakta o návrhu backendů pro generování kódu QEMU a také o tom, jak napsat Just-in-Time kompilátor pro webovou aplikaci.
úkoly
Vzhledem k tomu, že jsem se již naučil, jak „nějak“ přenést QEMU do JavaScriptu, bylo tentokrát rozhodnuto to udělat moudře a neopakovat staré chyby.
Chyba číslo jedna: větev z vydání bodu
Mojí první chybou bylo forkovat svou verzi z upstream verze 2.4.1. Pak se mi to zdálo jako dobrý nápad: pokud existuje bodové uvolnění, pak je pravděpodobně stabilnější než jednoduché 2.4 a ještě více větev master. A protože jsem plánoval přidat značné množství svých vlastních chyb, nepotřeboval jsem vůbec nikoho jiného. Tak to asi dopadlo. Ale jde o to: QEMU nestojí na místě a v určitém okamžiku dokonce oznámili optimalizaci generovaného kódu o 10 procent. "Jo, teď zamrznu," pomyslel jsem si a zlomil jsem se. Zde musíme udělat odbočku: kvůli jednovláknové povaze QEMU.js a skutečnosti, že původní QEMU neznamená absenci vícevláknového zpracování (tj. schopnost současně provozovat několik nesouvisejících kódových cest a nejen „použít všechna jádra“) je pro to kritické, hlavní funkce vláken jsem musel „vypnout“, abych mohl volat zvenčí. To způsobilo některé přirozené problémy během fúze. Nicméně skutečnost, že některé změny z větve master, se kterými jsem se pokusil sloučit svůj kód, byly také vybrány v bodovém vydání (a tedy v mé pobočce) také pravděpodobně nepřinesly větší pohodlí.
Obecně jsem se rozhodl, že stále má smysl prototyp vyhodit, rozebrat na díly a postavit novou verzi od nuly založenou na něčem čerstvějším a nyní z master.
Chyba číslo dvě: metodika TLP
V podstatě to není chyba, obecně je to jen rys vytváření projektu v podmínkách naprostého nepochopení jak „kam a jak se pohybovat?“ a obecně „dostaneme se tam?“ V těchto podmínkách nemotorné programování byla oprávněná možnost, ale přirozeně jsem ji nechtěl zbytečně opakovat. Tentokrát jsem to chtěl udělat moudře: atomické commity, vědomé změny kódu (a ne „spojování náhodných znaků, dokud se to nezkompiluje (s varováními)“, jak o někom jednou řekl Linus Torvalds, podle Wikicitátu) atd.
Chyba číslo tři: dostat se do vody bez znalosti brodu
Stále jsem se toho úplně nezbavil, ale teď jsem se rozhodl, že vůbec nepůjdu cestou nejmenšího odporu a udělám to „jako dospělý“, totiž napsat svůj TCG backend od začátku, abych abych později řekl: „Ano, je to samozřejmě pomalu, ale nemohu ovládat všechno – tak se píše TCI...“ Navíc to zpočátku vypadalo jako zřejmé řešení, protože Generuji binární kód. Jak se říká: „Ghent se shromáždilу, ale ne ten“: kód je samozřejmě binární, ale nelze do něj jednoduše přenést ovládání – musí se explicitně natlačit do prohlížeče ke kompilaci, čímž vznikne určitý objekt ze světa JS, který ještě potřebuje být někde uložen. Pokud však chápu, na normálních architekturách RISC je typická situace potřeba explicitně resetovat mezipaměť instrukcí pro regenerovaný kód - pokud to není to, co potřebujeme, pak je to v každém případě blízko. Navíc z mého posledního pokusu jsem se dozvěděl, že ovládání se nezdá být přeneseno doprostřed bloku překladu, takže vlastně nepotřebujeme bytecode interpretovaný z nějakého offsetu a můžeme ho jednoduše vygenerovat z funkce na TB .
Přišli a kopali
I když jsem kód začal přepisovat už v červenci, nepozorovaně se vloudil kouzelný kop: obvykle dopisy z GitHubu přicházejí jako upozornění na odpovědi na Issues a Pull requesty, ale tady, najednou zmínka ve vláknu v kontextu: "Udělal něco takového, možná něco řekne." Mluvili jsme o použití související knihovny Emscripten vytvořit WASM JIT. No, říkal jsem, že tam máš licenci Apache 2.0 a QEMU jako celek je distribuován pod GPLv2 a nejsou moc kompatibilní. Najednou se ukázalo, že licence může být nějak to opravit (Nevím: možná to změnit, možná duální licence, možná něco jiného...). To mě samozřejmě potěšilo, protože v té době už jsem si to pořádně prohlédl WebAssembly a byl jsem nějak smutný a nechápavý. Existovala také knihovna, která by hltala základní bloky s přechodovým grafem, produkovala bytekód a v případě potřeby jej dokonce spouštěla v samotném interpretu.
Pak toho bylo víc na mailing listu QEMU, ale toto je spíše otázka: „Kdo to vůbec potřebuje?“ A to je najednou, ukázalo se, že je to nutné. Minimálně můžete seškrábat následující možnosti použití, pokud to funguje více či méně rychle:
- spuštění něčeho vzdělávacího bez jakékoli instalace
- virtualizace na iOS, kde je podle pověstí jediná aplikace, která má právo generovat kód za běhu, JS engine (je to pravda?)
- ukázka mini-OS - jednodisketový, vestavěný, všechny druhy firmwaru atd...
Funkce prohlížeče Runtime
Jak jsem již řekl, QEMU je vázáno na multithreading, ale prohlížeč jej nemá. Tedy, ne... Nejprve to vůbec neexistovalo, pak se objevili WebWorkers - pokud jsem pochopil, jedná se o multithreading založený na předávání zpráv bez sdílených proměnných. To přirozeně vytváří značné problémy při portování existujícího kódu založeného na modelu sdílené paměti. Poté byla pod tlakem veřejnosti realizována také pod jménem SharedArrayBuffers. Postupně se zavádělo, slavili jeho spuštění v různých prohlížečích, pak oslavili Nový rok a pak Meltdown... Načež došli k závěru, že měření času je hrubé nebo hrubé, ale pomocí sdílené paměti a závit inkrementující počítadlo, je to všechno stejné . Takže jsme zakázali multithreading se sdílenou pamětí. Zdá se, že to později znovu zapnuli, ale jak se ukázalo z prvního experimentu, existuje život bez toho, a pokud ano, pokusíme se to udělat, aniž bychom se spoléhali na multithreading.
Druhou vlastností je nemožnost nízkoúrovňových manipulací se zásobníkem: nelze jednoduše vzít, uložit aktuální kontext a přepnout na nový s novým zásobníkem. Zásobník volání je spravován virtuálním počítačem JS. Zdálo by se, v čem je problém, když jsme se stále rozhodli řídit dřívější toky zcela ručně? Faktem je, že blokové I/O v QEMU je implementováno prostřednictvím korutin, a právě zde by se nízkoúrovňové manipulace se zásobníky hodily. Naštěstí Emscipten již obsahuje mechanismus pro asynchronní operace, dokonce dva: и . První funguje prostřednictvím značného nadýmání ve vygenerovaném kódu JavaScript a již není podporován. Druhý je současný „správný způsob“ a funguje prostřednictvím generování bytecode pro nativní interpret. Funguje to samozřejmě pomalu, ale nenadýmá kód. Pravda, podpora coroutin pro tento mechanismus se musela přispívat nezávisle (pro Asyncify již byly napsané coroutiny a pro Emterpreter existovala implementace přibližně stejného API, jen bylo potřeba je propojit).
Momentálně se mi ještě nepodařilo rozdělit kód na jeden zkompilovaný ve WASM a interpretovaný pomocí Emterpreteru, takže bloková zařízení zatím nefungují (viz v další sérii, jak se říká...). To znamená, že byste nakonec měli dostat něco jako tuto legrační vrstvenou věc:
- interpretovaný blok I/O. No, opravdu jste čekali emulované NVMe s nativním výkonem? 🙂
- staticky zkompilovaný hlavní kód QEMU (překladač, jiná emulovaná zařízení atd.)
- dynamicky kompilovaný kód hosta do WASM
Vlastnosti zdrojů QEMU
Jak jste pravděpodobně již uhodli, kód pro emulaci hostujících architektur a kód pro generování instrukcí hostitelského stroje jsou v QEMU odděleny. Ve skutečnosti je to ještě trochu složitější:
- existují hostující architektury
- je urychlovače, jmenovitě KVM pro hardwarovou virtualizaci na Linuxu (pro hostující a hostitelské systémy vzájemně kompatibilní), TCG pro generování kódu JIT kdekoli. Počínaje QEMU 2.9 se objevila podpora hardwarového virtualizačního standardu HAXM ve Windows ()
- pokud se používá TCG a ne hardwarová virtualizace, pak má samostatnou podporu generování kódu pro každou hostitelskou architekturu, stejně jako pro univerzální interpret
- ... a kolem toho všeho - emulované periferie, uživatelské rozhraní, migrace, přehrávání záznamu atd.
Mimochodem, věděli jste: QEMU umí emulovat nejen celý počítač, ale i procesor pro samostatný uživatelský proces v hostitelském jádře, což využívá například AFL fuzzer pro binární instrumentaci. Možná by někdo chtěl přenést tento režim provozu QEMU na JS? 😉
Jako většina dlouholetého svobodného softwaru je QEMU vytvořen prostřednictvím volání configure и make. Řekněme, že se rozhodnete něco přidat: backend TCG, implementaci vlákna, něco jiného. Nespěchejte, abyste byli šťastní/vyděšení (podtrhněte podle potřeby) při vyhlídce na komunikaci s Autoconf – ve skutečnosti, configure QEMU je zjevně napsáno samo a není generováno z ničeho.
WebAssembly
Jak se tedy tato věc nazývá WebAssembly (aka WASM)? Toto je náhrada za Asm.js, která již nepředstírá platný kód JavaScript. Naopak je čistě binární a optimalizovaný a ani pouhé zapsání celého čísla do něj není příliš jednoduché: pro kompaktnost je uloženo ve formátu .
Možná jste slyšeli o algoritmu relooping pro Asm.js – jedná se o obnovu instrukcí řízení toku „na vysoké úrovni“ (tedy if-then-else, smyček atd.), pro které jsou motory JS navrženy, od nízkoúrovňový LLVM IR, blíže ke strojovému kódu vykonávanému procesorem. Střední reprezentace QEMU je přirozeně blíže druhé. Zdálo by se, že je to tady, bytecode, konec trápení... A pak jsou tu bloky, když-tak-jinak a smyčky!..
A to je další důvod, proč je Binaryen užitečný: může přirozeně přijímat bloky vysoké úrovně blízké tomu, co by bylo uloženo ve WASM. Dokáže ale také vytvořit kód z grafu základních bloků a přechodů mezi nimi. No, už jsem řekl, že skrývá formát úložiště WebAssembly za pohodlné C/C++ API.
TCG (Tiny Code Generator)
TCG backend pro kompilátor C. Pak zřejmě nemohl odolat konkurenci s GCC, ale nakonec našel své místo v QEMU jako mechanismus generování kódu pro hostitelskou platformu. Existuje také backend TCG, který generuje nějaký abstraktní bajtkód, který je okamžitě proveden interpretem, ale rozhodl jsem se, že se ho tentokrát vyvaruji. Ovšem to, že v QEMU je již možné přes funkci umožnit přechod na vygenerovaný TB tcg_qemu_tb_exec, ukázalo se, že je to pro mě velmi užitečné.
Chcete-li přidat nový backend TCG do QEMU, musíte vytvořit podadresář tcg/<имя архитектуры> (v tomto případě, tcg/binaryen) a obsahuje dva soubory: tcg-target.h и tcg-target.inc.c и všechno je to o configure. Můžete tam umístit další soubory, ale jak můžete uhodnout z názvů těchto dvou, oba budou někde zahrnuty: jeden jako běžný hlavičkový soubor (je součástí tcg/tcg.h, a ten je již v jiných souborech v adresářích tcg, accel a nejen), druhý - pouze jako fragment kódu v tcg/tcg.c, ale má přístup ke svým statickým funkcím.
Rozhodl jsem se, že strávím příliš mnoho času podrobným zkoumáním toho, jak to funguje, a jednoduše jsem zkopíroval „kostry“ těchto dvou souborů z jiné implementace backendu, což jsem upřímně uvedl v záhlaví licence.
Soubor tcg-target.h obsahuje především nastavení ve formuláři #define-s:
- kolik registrů a jaká šířka je na cílové architektuře (máme kolik chceme, kolik chceme - otázka je spíše o tom, co vygeneruje do efektivnějšího kódu prohlížeč na „zcela cílové“ architektuře ...)
- zarovnání instrukcí hostitele: na x86 a dokonce ani v TCI nejsou instrukce zarovnány vůbec, ale do vyrovnávací paměti kódu vložím vůbec ne instrukce, ale ukazatele na struktury knihovny Binaryen, takže řeknu: 4 bajtů
- jaké volitelné instrukce může backend generovat - zahrneme vše, co najdeme v Binaryen, zbytek necháme akcelerátor rozdělit na jednodušší sám
- Jaká je přibližná velikost mezipaměti TLB požadovaná backendem. Faktem je, že v QEMU je vše vážné: ačkoli existují pomocné funkce, které provádějí načítání/ukládání s ohledem na hostující MMU (kde bychom teď bez něj byli?), ukládají svou překladovou mezipaměť ve formě struktury, jehož zpracování je vhodné vložit přímo do vysílacích bloků. Otázkou je, jaký offset v této struktuře je nejúčinněji zpracován malou a rychlou sekvencí příkazů?
- zde můžete vyladit účel jednoho nebo dvou rezervovaných registrů, povolit volání TB prostřednictvím funkce a volitelně popsat několik malých
inline- funkce jakoflush_icache_range(ale to není náš případ)
Soubor tcg-target.inc.c, je samozřejmě obvykle mnohem větší a obsahuje několik povinných funkcí:
- inicializace, včetně omezení toho, které instrukce mohou pracovat na kterých operandech. Okázale zkopírované mnou z jiného backendu
- funkce, která přebírá jednu interní instrukci bajtového kódu
- Můžete sem dát i pomocné funkce a můžete použít i statické funkce z
tcg/tcg.c
Pro sebe jsem zvolil následující strategii: v prvních slovech dalšího překladového bloku jsem si zapsal čtyři ukazatele: počáteční značku (určitá hodnota v okolí 0xFFFFFFFF, který určil aktuální stav TB), kontext, vygenerovaný modul a magické číslo pro ladění. Nejprve byla značka umístěna v 0xFFFFFFFF - nKde n - malé kladné číslo a pokaždé, když bylo provedeno přes tlumočník, se zvýšilo o 1. Když dosáhl 0xFFFFFFFE, proběhla kompilace, modul byl uložen do tabulky funkcí, naimportován do malého „spouštěče“, do kterého šlo spuštění z tcg_qemu_tb_execa modul byl odstraněn z paměti QEMU.
Abychom parafrázovali klasiku: „Crutchi, jak moc je v tomto zvuku propleteno progerovo srdce...“. Paměť však někde unikala. Navíc to byla paměť spravovaná QEMU! Měl jsem kód, který při psaní další instrukce (no, tedy ukazatel) smazal ten, jehož odkaz byl na tomto místě dříve, ale nepomohlo to. Ve skutečnosti v nejjednodušším případě QEMU alokuje paměť při spuštění a zapíše tam vygenerovaný kód. Když dojde buffer, kód se vyhodí a na jeho místo se začne psát další.
Po prostudování kódu jsem si uvědomil, že trik s magickým číslem mi umožnil neselhat při zničení haldy tím, že jsem při prvním průchodu uvolnil něco špatného na neinicializované vyrovnávací paměti. Ale kdo přepíše vyrovnávací paměť, aby později obešla moji funkci? Jak radí vývojáři Emscriptenu, když jsem narazil na problém, přeportoval jsem výsledný kód zpět do nativní aplikace, nastavil jsem na něm Mozilla Record-Replay... Obecně jsem si nakonec uvědomil jednoduchou věc: pro každý blok, A struct TranslationBlock s jeho popisem. Hádejte kde... Přesně tak, těsně před blokem přímo ve vyrovnávací paměti. Když jsem si to uvědomil, rozhodl jsem se přestat používat berle (alespoň některé), jednoduše jsem vyhodil magické číslo a zbývající slova jsem přenesl do struct TranslationBlock, čímž se vytvoří jednotlivě propojený seznam, který lze rychle procházet po resetování mezipaměti překladu a uvolnit paměť.
Některé berličky zůstávají: například označené ukazatele ve vyrovnávací paměti kódu - některé z nich prostě jsou BinaryenExpressionRef, to znamená, že se podívají na výrazy, které je potřeba lineárně vkládat do vygenerovaného základního bloku, část je podmínkou pro přechod mezi BB, část je kam jít. No a pro Relooper jsou již připravené bloky, které je potřeba zapojit podle podmínek. Pro jejich rozlišení se používá předpoklad, že jsou všechny zarovnány alespoň o čtyři bajty, takže pro štítek můžete klidně použít nejméně významné dva bity, jen je třeba pamatovat na jeho odstranění v případě potřeby. Mimochodem, takové štítky se již používají v QEMU k označení důvodu opuštění smyčky TCG.
Pomocí Binaryen
Moduly ve WebAssembly obsahují funkce, z nichž každá obsahuje tělo, což je výraz. Výrazy jsou unární a binární operace, bloky sestávající ze seznamů dalších výrazů, řídicí tok atd. Jak jsem již řekl, řídicí tok je zde organizován přesně jako větve na vysoké úrovni, smyčky, volání funkcí atd. Argumenty funkcí se nepředávají na zásobníku, ale explicitně, stejně jako v JS. Existují také globální proměnné, ale nepoužil jsem je, takže vám o nich neřeknu.
Funkce mají také lokální proměnné, číslované od nuly, typu: int32 / int64 / float / double. V tomto případě je prvních n lokálních proměnných argumenty předávané funkci. Vezměte prosím na vědomí, že i když zde není vše úplně na nízké úrovni, pokud jde o tok řízení, celá čísla stále nenesou atribut „signed/unsigned“: to, jak se číslo chová, závisí na operačním kódu.
Obecně řečeno, Binaryen poskytuje : vytvoříte modul, v něm vytvářet výrazy - unární, binární, bloky z jiných výrazů, řízení toku atd. Poté vytvoříte funkci s výrazem jako tělem. Pokud máte jako já nízkoúrovňový přechodový graf, pomůže vám komponenta relooper. Pokud jsem pochopil, je možné použít vysokoúrovňovou kontrolu toku provádění v bloku, pokud nepřekračuje hranice bloku - to znamená, že je možné provést interní rychlou cestu / pomalou větvení cesty uvnitř vestavěného kódu pro zpracování mezipaměti TLB, ale nezasahuje do „externího“ řídicího toku. Když uvolníte relooper, jeho bloky se uvolní; když uvolníte modul, zmizí mu přiřazené výrazy, funkce atd. aréna.
Pokud však chcete interpretovat kód za běhu bez zbytečného vytváření a mazání instance interpretu, může mít smysl vložit tuto logiku do souboru C++ a odtud přímo spravovat celé C++ API knihovny a obejít ready- vyrobené obaly.
Takže pro vygenerování kódu, který potřebujete
// настроить глобальные параметры (можно поменять потом)
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);... pokud jsem na něco zapomněl, omlouvám se, je to jen pro znázornění váhy a podrobnosti jsou v dokumentaci.
A teď začíná crack-fex-pex, něco jako toto:
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);Abychom nějak propojili světy QEMU a JS a zároveň rychle přistupovali ke kompilovaným funkcím, bylo vytvořeno pole (tabulka funkcí pro import do launcheru), tam byly umístěny vygenerované funkce. Pro rychlý výpočet indexu byl původně použit index překladového bloku nulových slov, ale pak index vypočítaný pomocí tohoto vzorce začal jednoduše zapadat do pole v struct TranslationBlock.
Mimochodem, (momentálně s temnou licencí) funguje dobře pouze ve Firefoxu. Vývojáři Chrome byli nějak není připraven na to, že by někdo chtěl vytvořit více než tisíc instancí modulů WebAssembly, tak prostě každému přidělil gigabajt virtuálního adresního prostoru...
To je prozatím vše. Snad bude další článek, kdyby to někoho zajímalo. Totiž, zbývá minimálně jen aby bloková zařízení fungovala. Také by mohlo mít smysl udělat kompilaci modulů WebAssembly asynchronní, jak je ve světě JS zvykem, protože stále existuje interpret, který to vše dokáže, dokud nebude připraven nativní modul.
Nakonec hádanka: zkompilovali jste binární soubor na 32bitové architektuře, ale kód prostřednictvím operací s pamětí leze z Binaryenu, někde v zásobníku nebo někde jinde v horních 2 GB 32bitového adresního prostoru. Problém je v tom, že z pohledu Binaryen je to přístup k příliš velké výsledné adrese. Jak to obejít?
Na způsob admina
Nakonec jsem to netestoval, ale moje první myšlenka byla „Co kdybych nainstaloval 32bitový Linux? Poté bude horní část adresního prostoru obsazena jádrem. Jedinou otázkou je, kolik bude obsazeno: 1 nebo 2 Gb.
Programátorským způsobem (možnost pro praktiky)
Nafoukneme bublinu v horní části adresního prostoru. Sám nechápu, proč to funguje - tam již musí tam být stoh. Ale „jsme praktikující: všechno nám funguje, ale nikdo neví proč...“
// 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));
}... je pravda, že to není kompatibilní s Valgrind, ale naštěstí Valgrind sám o sobě velmi efektivně všechny odtamtud vytlačí :)
Možná někdo lépe vysvětlí, jak tento můj kód funguje...
Zdroj: www.habr.com