🥇QEMU.js: nyní vážně a s WASM

Kdysi dávno jsem se pro smích rozhodl dokázat návratnost procesu a naučit se generovat JavaScript (přesněji řečeno Asm.js) z strojového kódu. Pro experimentaci byl vybrán QEMU, po nějaké době byl napsán článek na Habr. V komentářích mi doporučili přepsat projekt na WebAssembly, a tak jsem nechtěl opustit skoro dokončený projekt... Práce šla, ale velmi pomalu, a nedávno se v tom článku objevil komentář nápad „Tak a čím to všechno skončilo?“. Na mou podrobnou odpověď jsem slyšel „To je na článek“. Takže, když je to na článek, tak bude článek. Možná to někomu pomůže. Z něj se čtenář dozví některé fakta o uspořádání backendů pro generování kódu v QEMU, a také jak napsat Just-in-Time kompilátor pro webovou aplikaci.

Úkoly

Jelikož jsem se „nějak“ naučil portovat QEMU na JavaScript, bylo tentokrát rozhodnuto dělat to pořádně a neopakovat staré chyby.

Chyba číslo jedna: odchýlit se od point release

Mou první chybou bylo odchýlit svou verzi od upstream verze 2.4.1. Tenkrát mi to připadalo jako dobrý nápad: pokud existuje point release, pak je pravděpodobně stabilnější než prostá 2.4, a už vůbec ne branch master. A protože jsem plánoval přidat slušné množství vlastních chyb, ty cizí mi nebyly vůbec potřeba. Celé to asi tak dopadlo. Ale potíž byla v tom, že QEMU se neposunulo, a v určitém okamžiku tam dokonce oznámili optimalizaci generovaného kódu o 10 procent. „Aha, teď to zkombinuji“ pomyslel jsem si a zklamal se. Tady je třeba udělat odbočku: vzhledem k jedno-vláknovému charakteru QEMU.js a tomu, že původní QEMU nepočítá s absencí víc-vláknovosti (to znamená, že je kritické mít možnost současné práce s několika nesouvisejícími code path, a ne jednoduše „použít všechny jádra“), hlavní funkce vláken musely být „vydány“ pro možnost volání zvenčí. To vytvářelo nějaké přirozené problémy při sloučení. Nicméně skutečnost, že část změn z branch master, se kterými jsem se snažil sloučit svůj kód, byly také cherry picked do point release (což znamená, že i do mé větve) by pravděpodobně také pohodlí nepřidala.

Celkově jsem se rozhodl, že prototyp má smysl vyhodit, rozebrat na součásti a postavit novou verzi od nuly na základě něčeho novějšího a teď už master.

Chyba číslo dvě: TLP metodologie

V zásadě to není chyba, ale spíše zvláštnost tvorby projektu v podmínkách naprostého nepochopení, jak "kam a jak se pohybovat?", a vůbec "dostaneme se tam?". Za těchto podmínek programování na koleně bylo opodstatněnou variantou, ale samozřejmě bych to nechtěl opakovat bez nutnosti. Tentokrát jsem chtěl udělat věci správně: atomární commity, uvědomělé změny kódu (a ne "sestavování náhodných znaků, dokud to nekompiluje (s varováním)", jak o někom jednou řekl Linus Torvalds, pokud věřit Wikiquote) atd.

Chyba číslo tři: nevědět, co dělám, skákat do vody

Od toho jsem se ani teď zcela neosvobodil, ale nyní jsem se rozhodl jít ne cestou nejmenšího odporu a udělat to "dospěle", a to tak, že napíšu svůj backend TCG od základů, abych potom neříkal, že "Ano, je to samozřejmě pomalé, ale nemůžu to všechno kontrolovat — takhle to napsal TCI…". Kromě toho to zpočátku vypadalo jako očividné řešení, protože vygeneruji binární kód.Jak se říká, "Složil Gent,u, ale ne ten správný": kód je sice binární, ale ovládání na něj takhle přenést nelze — musí se explicitně dostat do prohlížeče na kompilaci, přičemž výsledek je nějaký objekt ze světa JS, který je pak třeba někam uložit. Nicméně na normálních RISC architekturách je, jak chápu, typickou situací potřeba výslovně vyprázdnit cache instrukcí pro znovu vygenerovaný kód — pokud to není zrovna to, co potřebujeme, je to v každém případě blízko. Kromě toho jsem ze své předchozí pokusy pochopil, že ovládání do středu bloku transformace jakoby nepřechází, takže bytecode interpretovaný z jakéhokoli posunutí nám zvlášť nepotřebuje, a můžeme jednoduše generovat podle funkce na TB.

Přišli a kopli

Ačkoli jsem začal přepisovat kód už v červenci, kouzelný kopanec přišel nečekaně: obvykle maily z GitHubu přicházejí jako oznámení o odpovědích na Issues a Pull requests, ale tady, náhle zmínka v threadu Binaryen jako backend qemu v kontextu "Tady to dělalo něco podobného, možná řekne něco nového". Šlo o využití příbuzné knihovny k Emscriptenu Binaryen pro vytváření WASM JIT. Tak jsem řekl, že máte licenci Apache 2.0, a QEMU jako celek je distribuováno pod GPLv2, což nejsou právě kompatibilní. Najednou se ukázalo, že licenci lze nějak upravit. (nevím: možná změnit, možná dual licensing, možná něco jiného…). To mě samozřejmě potěšilo, protože jsem se již několikrát do té doby díval na binární formát WebAssembly, a bylo mi to nějak smutné a nejasné. Tady byla knihovna, která sníží i základní bloky s grafem přechodů, vydá bytkód a dokonce ho sama spustí v interpretátoru, pokud bude potřeba.

Pak bylo ještě dopisu na mailing listu QEMU, ale to už spíše k otázce, „A kdo to vůbec potřebuje?“. A přitom se náhle, ukázalo, že to potřeba je. Minimálně se dají nazbírat takové možnosti použití, pokud to bude víceméně svižně fungovat:

spuštění něčeho výukového naprosto bez instalace
virtualizace na iOS, kde se říká, že jediné aplikace, které mají právo na generaci kódu za běhu — je JS engine (ale je to pravda?)
prezentace mini-OS — jednodisketové, vestavěné, různé firmvér atd…

Vlastnosti prohlížečového běhového prostředí

Jak jsem už říkal, QEMU je zavázané k multithreadingu, a v prohlížeči žádný není. No, jako není… Nejprve vůbec nebyl, potom se objevily WebWorkery — pokud to chápu správně, tohle je multithreading založený na přenosu zpráv bez společně měnitelných proměnných. Přirozeně to vytváří značné problémy při portování existujícího kódu, který je založen na modelu sdílené paměti. Poté, pod tlakem veřejnosti, byla implementována a to pod názvem SharedArrayBuffers. Ta byla postupně zavedena, oslavili její spuštění v různých prohlížečích, pak oslavili Nový rok, a pak Meltdown… Po čemž dospěli k závěru, že ať už měření času podezíráte, nebo ne, pomocí sdílené paměti a vlákna, které inkrementuje čítač, se to stejně docela přesně udělá. Takto vypnuli multithreading se sdílenou pamětí. Zdálo se, že to pak zase zapnuli, ale jak se ukázalo z prvního experimentu, a bez něj život je, a když je to tak, zkusíme to udělat, aniž bychom počítali s multithreadingem.

Druhým rysem je nemožnost nízkoúrovňových manipulací se zásobníkem: nelze jednoduše vzít aktuální kontext, uložit ho a přepnout se na nový s novým zásobníkem. Zásobník volání je řízen virtuální stroj JS. Může se zdát, co je na tom problém, když se stejně chystáme řídit bývalými vlákny úplně ručně? Jde o to, že blokové I/O v QEMU je implementováno prostřednictvím korutin, a právě zde bychom potřebovali nízkoúrovňové manipulace se zásobníkem. Naštěstí Emscripten již obsahuje mechanismus pro asynchronní operace, dokonce dva: Asyncify a Emterpreter. První funguje prostřednictvím výrazného zvětšení generovaného JavaScriptového kódu a již není podporován. Druhý je aktuální „správný způsob“ a funguje prostřednictvím generování bajtkódu pro vlastní interpreter. Funguje to samozřejmě pomalu, ale aspoň to nezvětšuje kód. Pravda, podporu korutin pro tento mechanismus bylo nutné přispět samo (už tam byly korutiny napsané pro Asyncify a byla implementace přibližně toho samého API pro Emterpreter, bylo jen potřeba je spojit).

V tuto chvíli jsem ještě neměl čas rozdělit kód na ten, který se kompiluje do WASM a na ten, který se interpretuje pomocí Emterpreter, takže bloková zařízení zatím nefungují (pokud se podíváte na další díly, jak se říká…). Tedy, nakonec by to mělo dopadnout takové zábavné vrstvené cosi:

interpretovaný blokový vstup-výstup. No a co, opravdu jste očekávali emulovaný NVMe s nativním výkonem? 🙂
staticky zkompilovaný hlavní kód QEMU (translátor, ostatní emulované zařízení atd.)
dynamicky kompilovaný do WASM hostitelský kód

Charakteristiky zdrojového kódu QEMU

Jak už asi tušíte, kód emulace hostitelských architektur a kód generování hostitelských strojových instrukcí u QEMU je rozdělen. Ve skutečnosti je tam dokonce ještě o něco složitější:

existují hostitelské architektury
položka „Přesunout karty“. Kromě toho akcelerátory, a to konkrétně KVM pro hardwarovou virtualizaci na Linuxu (pro vzájemně kompatibilní hostitelské a hostitelské systémy), TCG pro JIT generaci kódu kdekoliv. Od QEMU 2.9 byla zavedena podpora standardu hardwarové virtualizace HAXM na Windows (podrobnosti)
pokud se používá TCG a ne hardwarová virtualizace, má podporu generování kódu pro každou hostitelskou architekturu a také pro univerzální interpret.
… a kolem toho všeho – emulovaná periferie, uživatelské rozhraní, migrace, záznam-a-přehrávání atd.

Mimochodem, věděli jste, že: QEMU může emulovat nejen celý počítač, ale také procesor pro jednotlivý uživatelský proces v hostitelském jádře, což využívá například fuzzer AFL pro instrumentaci binárních souborů. Možná by někdo chtěl portovat tento režim QEMU na JS? 😉

Jako většina dlouho existujících open source programů se QEMU sestavuje pomocí volání konfigurovat a make. Předpokládejme, že jste se rozhodli něco přidat: TCG backend, implementaci vláken, něco ještě. Neuspěchejte se radovat/hroutit (vyberte si, co je potřeba) z vyhlídky na komunikaci s Autoconf – ve skutečnosti, konfigurovat u QEMU je zjevně vlastní a není z ničeho generováno.

WebAssembly

Co je to tedy WebAssembly (také známý jako WASM)? Je to náhrada za Asm.js, nyní už neprojevující se jako platný JavaScriptový kód. Naopak, je to čistě binární a optimalizované, a dokonce je docela složité do něj napsat celé číslo: ukládá se ve formátu LEB128.

Možná jste slyšeli o algoritmu relooping pro Asm.js – to je obnova „vysokolevelových“ instrukcí řízení toku (tj. if-then-else, smyčky atd.), které navrhují JS enginy, z nízkolevelového LLVM IR, které je blíž k strojovému kódu vykonávanému procesorem. Přirozeně, mezivrstvené zastoupení QEMU je blíž k tomu druhému. Připadalo by se, že tady je bytecode, konec trápení… A tady bloky, if-then-else a smyčky!.

A v tom je ještě jeden důvod, proč je Binaryen užitečný: samozřejmě může přijímat vysokolevelové bloky, blízké tomu, co bude uloženo v WASM. Ale také může generovat kód z grafu základních bloků a přechodů mezi nimi. Co se týče toho, co skrývá za pohodlným C/C++ API formát ukládání WebAssembly, už jsem zmínil.

TCG (Tiny Code Generator)

TCG byl původně backend pro překladač C. Poté zřejmě nedokázal obstát v konkurenci s GCC, ale nakonec si našel své místo v QEMU jako mechanismus generování kódu pro hostitelskou platformu. Existuje také TCG backend, který generuje jakýsi abstraktní bajtkód, který pak interpretuje okamžitě, ale od jeho použití jsem se tentokrát rozhodl vzdát. Nicméně, skutečnost, že QEMU již umožňuje přechod na generovaný TB prostřednictvím funkce tcg_qemu_tb_exec, mi přišla velmi vhod.

Aby bylo možné přidat nový TCG backend do QEMU, je třeba vytvořit podadresář tcg/ (v tomto případě, tcg/binaryen), a v něm dva soubory: tcg-target.h a tcg-target.inc.c a zapsat to vše do konfigurovat. Můžete tam umístit i další soubory, ale jak vyplývá z názvů těchto dvou, oba budou někde zahrnuty: jeden jako běžný hlavičkový soubor (ten se zahrnuje do tcg/tcg.h, a ten už do jiných souborů v adresářích tcg, accel a nejen), druhý pouze jako kódový úryvek do tcg/tcg.c, ale má přístup k jeho statickým funkcím.

Poté, co jsem usoudil, že bych strávil příliš mnoho času podrobným prozkoumáváním, jak to funguje, jednoduše jsem zkopíroval „kostry“ těchto dvou souborů z jiné implementace backendu a poctivě to uvedl v hlavičce licence.

Soubor tcg-target.h obsahuje převážně nastavení ve formě #define-ů:

kolik registrů a jaké šířky je na cílové architektuře (u nás — kolik chceme, tolik máme — otázka je spíše, co bude generováno v efektivnějším kódu pro prohlížeč na „zcela cílové“ architektuře…)
vyrovnání hostitelských instrukcí: na x86, a i v TCI, instrukce se vůbec nevyrovnávají, já mám v plánu ukládat do kódu nejen instrukce, ale i ukazatele na struktury knihovny Binaryen, takže řeknu: 4 bajty
jaké volitelné instrukce může generovat backend — zapneme vše, co najdeme v Binaryen, zbytek ať akcelerátor rozbije na jednodušší sám.
jaká je přibližně velikost TLB cache, kterou backend vyžaduje. V QEMU to berou vážně: i když existují pomocné funkce, které provádějí load/store s ohledem na hostitelskou MMU (kam se bez toho teď podívat?), uchovávají si svou cache překladů ve formě struktury, jejíž zpracování je vhodné integrovat přímo do bloků překladu. Otázkou je, které posunutí v této struktuře se nejefektivněji zpracovává malou a rychlou sekvencí příkazů.
zde lze také upravit určení jednoho nebo dvou rezervovaných registrů, zapnout volání TB prostřednictvím funkce a volitelně popsat pár maličkostí. inline-funkcí jako flush_icache_range (ale to není náš případ).

Soubor tcg-target.inc.c, přirozeně, obvykle je mnohem větší a obsahuje několik povinných funkcí:

inicializace, která určuje také omezení na to, jaký příkaz může pracovat s jakými operandy. Bezostyšně zkopírováno z jiného backendu.
funkce, která přijímá jeden příkaz interního bajtkódu.
zde lze také umístit pomocné funkce, a navíc zde lze používat statické funkce z tcg/tcg.c

Pro sebe jsem zvolil následující strategii: na začátku každého bloku překladu jsem zapisoval čtyři ukazatele: označení začátku (nějaká hodnota v okolí 0xFFFFFFFF, podle které se určuje aktuální stav TB), kontext, vygenerovaný modul a magické číslo pro ladění. Nejdříve byla značka nastavena na 0xFFFFFFFF - n, kde n — malé kladné číslo a při každém provádění prostřednictvím interpretátora se zvyšovala o 1. Když dosáhla 0xFFFFFFFE, došlo k překladu, modul byl uložen do tabulky funkcí importované do malého „spouštěče“, do kterého probíhalo vykonávání z tcg_qemu_tb_exec, a modul byl odstraněn z paměti QEMU.

Parafrázujíc klasiku, „Prut, jak mnoho v tomto zvuku pro srdce programátora se spojilo…“. Nicméně, paměť někam unikala. A to byla paměť spravovaná QEMU! Měl jsem kód, který při zápisu dalšího příkazu (čili ukazatele) odstraňoval ten, na který byla odkazováno na tomto místě dříve, ale to nepomáhalo. V zásadě QEMU při spuštění vyčleňuje paměť a zapisuje do ní generovaný kód. Když buffer končí, kód se zahodí a na jeho místo se začíná zapisovat další.

Po prostudování kódu jsem pochopil, že workaround s magic number umožnil nezkolabovat při uvolnění paměti z neinitializovaného bufferu při prvním průchodu. Ale kdo pak přepisuje buffer obcházením mé funkce? Jak doporučují vývojáři Emscripten, když jsem narazil na problém, převedl jsem takto získaný kód zpět do nativní aplikace a nasměroval jsem ho na Mozilla Record-Replay… Nakonec jsem pochopil jednu jednoduchou věc: pro každý blok se alokuje struct TranslationBlock s jeho popisem. Uhodněte, kde… Správně, přímo před blokem v bufferu. Když jsem to pochopil, rozhodl jsem se skončit s workaroundy (alespoň některými) a prostě jsem odstranil magic number, a zbývající slova jsem přesunul do struct TranslationBlock, založil jsem jednoduše vázaný seznam, přes který lze rychle projít při resetování mezipaměti převodu a uvolnit paměť.

Některé workaroundy zůstaly: například označené ukazatele v kódu bufferu — část z nich představuje BinaryenExpressionRef, tedy ukazují na výrazy, které je třeba lineárně umístit do generovaného základního bloku, část je podmínkou přechodu mezi BB, část — kam se přechází. A také existují již připravené bloky pro Relooper, které je třeba spojit na základě podmínek. Abychom je odlišili, používá se předpoklad, že jsou všechny vyrovnány alespoň na čtyři bajty, a proto lze bez obav použít dvě nejnižší bity na značku; jen je potřeba je v případě potřeby odstranit. Mimochodem, takové značky se již používají v QEMU k označení důvodu výstupu z cyklu TCG.

Použití Binaryen

Moduly v WebAssembly obsahují funkce, z nichž každá obsahuje tělo, které představuje výraz. Výrazy zahrnují unární a binární operace, bloky skládající se ze seznamů dalších výrazů, řízení toku atd. Jak jsem již zmínil, řízení toku je zde organizováno jako vysoce úrovňové větvení, cykly, volání funkcí atd. Argumenty se funkcím předávají ne na zásobníku, ale explicitně, stejně jako v JS. Existují také globální proměnné, ale ty jsem nepoužíval, takže o nich nebudu hovořit.

Funkce mají také číslované lokální proměnné začínající na nule, které mají typ: int32 / int64 / float / double. Prvních n lokálních proměnných přitom představují předané argumenty funkci. Všimněte si, že ačkoli zde vše není úplně nízkoúrovňové z hlediska toku řízení, celá čísla přesto nenesou znak "znakové/bezzáporné": chování čísla závisí na kódu operace.

Obecně platí, že Binaryen poskytuje jednoduché C-API: vytváříte modul, v něm vytváříte výrazy — unární, binární, bloky z jiných výrazů, řízení toku atd. Poté vytváříte funkci, jejíž tělo by mělo obsahovat výraz. Pokud máte, jako já, nízkoúrovňový graf přechodů, komponenta relooper vám pomůže. Jak chápu, můžete používat vysokou úroveň řízení toku v bloku, dokud nepřesáhne hranice bloku — to znamená, že můžete provádět vnitřní větvení fast path / slow path uvnitř vloženého kódu pro zpracování TLB cache, ale zasahovat do "vnějšího" toku řízení — to ne. Když uvolníte relooper, uvolní se jeho bloky; když uvolníte modul — zmizí výrazy, funkce atd., které byly přiděleny v jeho aréně..

Pokud však chcete interpretovat kód za běhu bez zbytečného vytváření a mazání instance interpreteru, může mít smysl převést tuto logiku do souboru C++ a odtud přímo řídit celé C++ API knihovny, obcházející hotové obálky.

Takže abyste vygenerovali kód, 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, to bylo jen pro představu o rozsahu, a podrobnosti — ty jsou v dokumentaci.

A teď začíná kódek-féx-féx, přibližně takto:

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,
          // ...
      }
  );
  // a už máte instance!
}, buf, sz);

Aby nějak spojit svět QEMU a JS a zároveň rychle přistupovat ke zkompilovaným funkcím, byl vytvořen pole (tabulka funkcí pro import do spouštěče), do kterého se ukládaly generované funkce. Pro rychlé výpočty indexu byl původně použit index nulového slova translation block, ale pak se index vypočítaný podle této formule jednoduše zapsal do pole v struct TranslationBlock.

Mimochodem, demo (zatím s nejasnou licencí) funguje správně jen ve Firefoxu. Vývojáři Chrome byli nějak nepřipraveni na to, že by někdo chtěl vytvářet více než tisíc instancí modulů WebAssembly, takže jednoduše vyčlenili po gigabajtu virtuálního adresního prostoru na každou…

Na tomhle zatím všechno. Možná bude ještě jeden článek, pokud někoho zajímá. A konkrétně, zbývá minimálně jen donutit fungovat bloková zařízení. Možná má smysl také udělat kompilaci modulů WebAssembly asynchronní, jak je obvyklé ve světě JS, když máme interpreter, který to může všechno vykonávat, dokud není nativní modul připraven.

Nakonec hádanka: vy vytvoříte binární soubor na 32bitové architektuře, ale kód přes operace s pamětí leze z Binaryen, někam na zásobník nebo někam do horních 2 GB 32bitového adresního prostoru. Problém je, že z pohledu Binaryen se jedná o přístup na příliš velkou výslednou adresu. Jak to obejít?

Administrátorsky

To jsem nakonec netestoval, ale první myšlenka byla: „A co když nainstaluji 32bitový Linux?“ Potom bude horní část adresního prostoru obsazena jádrem. Otázka jen je, kolik bude obsazeno: 1 nebo 2 Gb.

Programátorsky (varianta pro praktikující)

Nafoukneme bublinu v horní části adresního prostoru. Sám nechápu, proč to funguje – tam přece již musí být zásobník. Ale „my praktikující: u nás vše 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));
}

… s Valgrindem, pravda, není kompatibilní, ale naštěstí Valgrind sám velmi efektivně vytlačuje všechny z tamtud 🙂

Možná někdo dá lepší vysvětlení, jak funguje tento můj kód…

Zdroj: habr.com