QEMU.js: nu seriös och med WASM

En gång i tiden bestämde jag mig för skojs skull bevisa processens reversibilitet och lär dig hur du genererar JavaScript (mer exakt, Asm.js) från maskinkod. QEMU valdes för experimentet, och en tid senare skrevs en artikel om Habr. I kommentarerna fick jag rådet att göra om projektet i WebAssembly och till och med sluta själv nästan färdig Jag ville på något sätt inte ha projektet... Arbetet pågick, men väldigt långsamt, och nu, nyligen dök det upp i den artikeln kommentar på ämnet "Så hur slutade det hela?" Som svar på mitt detaljerade svar hörde jag "Det här låter som en artikel." Tja, om du kan, kommer det att finnas en artikel. Kanske någon kommer att ha nytta av det. Från den kommer läsaren att lära sig lite fakta om designen av QEMU-kodgenereringsbackends, samt hur man skriver en Just-in-Time-kompilator för en webbapplikation.

uppgifter

Eftersom jag redan hade lärt mig hur man "på något sätt" porterar QEMU till JavaScript, beslutades den här gången att göra det klokt och inte upprepa gamla misstag.

Fel nummer ett: förgrena sig från punktsläpp

Mitt första misstag var att dela min version från uppströmsversionen 2.4.1. Då tyckte jag att det var en bra idé: om punktutgivning finns, så är den förmodligen mer stabil än enkel 2.4, och ännu mer så grenen master. Och eftersom jag planerade att lägga till en hel del av mina egna buggar, behövde jag inte någon annans alls. Det var nog så det blev. Men här är grejen: QEMU står inte stilla, och vid något tillfälle tillkännagav de till och med optimering av den genererade koden med 10 procent. "Ja, nu ska jag frysa", tänkte jag och bröt ihop. Här måste vi göra en avvikelse: på grund av QEMU.js entrådiga natur och det faktum att den ursprungliga QEMU inte innebär frånvaron av multi-threading (det vill säga möjligheten att samtidigt använda flera orelaterade kodvägar, och inte bara "använd alla kärnor") är avgörande för det, huvudfunktionerna i trådar var jag tvungen att "vända ut" för att kunna anropa utifrån. Detta skapade en del naturliga problem under sammanslagningen. Men det faktum att några av förändringarna från grenen master, som jag försökte slå ihop min kod med, var också körsbärsplockade i punktutgåvan (och därför i min gren) också förmodligen inte skulle ha lagt till bekvämlighet.

I allmänhet bestämde jag mig för att det fortfarande är vettigt att kasta ut prototypen, plocka isär den för delar och bygga en ny version från grunden baserad på något fräschare och nu från master.

Misstag nummer två: TLP-metodik

I grund och botten är detta inte ett misstag, i allmänhet är det bara en funktion för att skapa ett projekt under förhållanden av fullständigt missförstånd av både "vart och hur man ska flytta?" och i allmänhet "kommer vi dit?" Under dessa förhållanden klumpig programmering var ett motiverat alternativ, men jag ville naturligtvis inte upprepa det i onödan. Den här gången ville jag göra det klokt: atomic commits, medvetna kodändringar (och inte "stränga ihop slumpmässiga tecken tills det kompileras (med varningar)", som Linus Torvalds en gång sa om någon, enligt Wikiquote), etc.

Misstag nummer tre: att komma i vattnet utan att känna till vadstället

Jag har fortfarande inte helt blivit av med detta, men nu har jag bestämt mig för att inte följa minsta motståndets väg alls, och att göra det "som vuxen", nämligen skriva min TCG-backend från grunden, för att inte att behöva säga senare, "Ja, det här går naturligtvis långsamt, men jag kan inte kontrollera allt - det är så TCI skrivs..." Dessutom verkade detta initialt vara en självklar lösning, eftersom Jag genererar binär kod. Som de säger, "Gent samladesу, men inte den”: koden är naturligtvis binär, men kontrollen kan inte bara överföras till den - den måste explicit tryckas in i webbläsaren för kompilering, vilket resulterar i ett visst objekt från JS-världen, som fortfarande måste sparas någonstans. Men på normala RISC-arkitekturer, så vitt jag förstår, är en typisk situation behovet av att explicit återställa instruktionscachen för regenererad kod - om detta inte är vad vi behöver, så är det i alla fall nära. Dessutom, från mitt senaste försök, lärde jag mig att kontrollen inte verkar överföras till mitten av översättningsblocket, så vi behöver egentligen inte bytekod tolkad från någon offset, och vi kan helt enkelt generera den från funktionen på TB .

De kom och sparkade

Även om jag började skriva om koden redan i juli, smög en magisk kick fram obemärkt: vanligtvis kommer brev från GitHub som meddelanden om svar på problem och Pull-förfrågningar, men här, plötsligt nämna i tråden Binaryen som en qemu-backend i sammanhanget, "Han gjorde något sådant, han kanske säger något." Vi pratade om att använda Emscriptens relaterade bibliotek Binaryen för att skapa WASM JIT. Jo, jag sa att du har en Apache 2.0-licens där, och QEMU som helhet distribueras under GPLv2, och de är inte särskilt kompatibla. Plötsligt visade det sig att en licens kan vara fixa det på något sätt (Jag vet inte: kanske ändra det, kanske dubbla licenser, kanske något annat...). Detta gjorde mig såklart glad, för vid det laget hade jag redan tittat noga på binärt format WebAssembly, och jag var på något sätt ledsen och oförstående. Det fanns också ett bibliotek som skulle sluka de grundläggande blocken med övergångsgrafen, producera bytekoden och till och med köra den i själva tolken, om det skulle behövas.

Sedan var det mer ett brev på QEMU:s sändlista, men det här handlar mer om frågan "Vem behöver det egentligen?" Och det är plötsligt, det visade sig att det var nödvändigt. Som ett minimum kan du skrapa ihop sådana användningsmöjligheter om det fungerar mer eller mindre snabbt:

• lanserar något pedagogiskt utan någon installation alls
• virtualisering på iOS, där, enligt rykten, den enda applikationen som har rätt till kodgenerering i farten är en JS-motor (stämmer detta?)
• demonstration av mini-OS - en diskett, inbyggd, alla typer av firmware, etc...

Webbläsarens körtidsfunktioner

Som jag redan sa är QEMU knuten till multithreading, men webbläsaren har det inte. Tja, det vill säga nej... Först fanns det inte alls, sedan dök WebWorkers upp - så vitt jag förstår är detta multitrådning baserat på meddelandeförmedling utan delade variabler. Naturligtvis skapar detta betydande problem vid portering av befintlig kod baserad på modellen med delat minne. Sedan, under påtryckningar från allmänheten, genomfördes det också under namnet SharedArrayBuffers. Det introducerades gradvis, man firade lanseringen i olika webbläsare, sedan firade man nyår, och sedan Meltdown... Varefter man kom fram till att grova eller grova tidsmätningen, men med hjälp av delat minne och en tråd som ökar räknaren, det är likadant det kommer att fungera ganska exakt. Så vi inaktiverade multithreading med delat minne. Det verkar som att de senare slog på det igen, men som det blev klart från det första experimentet finns det liv utan det, och i så fall kommer vi att försöka göra det utan att förlita oss på multithreading.

Den andra funktionen är omöjligheten av lågnivåmanipulationer med stacken: du kan inte bara ta, spara det aktuella sammanhanget och byta till en ny med en ny stack. Anropsstacken hanteras av den virtuella JS-maskinen. Det verkar, vad är problemet, eftersom vi ändå bestämde oss för att hantera de tidigare flödena helt manuellt? Faktum är att block I/O i QEMU implementeras genom coroutines, och det är här lågnivåstackmanipulationer skulle komma till nytta. Lyckligtvis innehåller Emscipten redan en mekanism för asynkrona operationer, till och med två: Asynkronisera и Emperpreter. Den första fungerar genom betydande uppsvällning i den genererade JavaScript-koden och stöds inte längre. Det andra är det nuvarande "korrekta sättet" och fungerar genom bytekodgenerering för den ursprungliga tolken. Det fungerar, naturligtvis, långsamt, men det sväller inte koden. Det är sant att stöd för koroutiner för denna mekanism måste bidra oberoende (det fanns redan koroutiner skrivna för Asyncify och det fanns en implementering av ungefär samma API för Emterpreter, du behövde bara koppla dem).

För tillfället har jag ännu inte lyckats dela upp koden till en kompilerad i WASM och tolkad med Emterpreter, så blockenheter fungerar inte än (se i nästa serie, som man säger...). Det vill säga, i slutändan borde du få något i stil med denna roliga skiktade sak:

• tolkat block I/O. Tja, förväntade du dig verkligen emulerat NVMe med inbyggd prestanda? 🙂
• statiskt kompilerad QEMU-huvudkod (översättare, andra emulerade enheter, etc.)
• dynamiskt kompilerad gästkod till WASM

Funktioner hos QEMU-källor

Som du förmodligen redan gissat är koden för att emulera gästarkitekturer och koden för att generera värdmaskininstruktioner separerade i QEMU. Faktum är att det är ännu lite knepigare:

• det finns gästarkitekturer
• finns acceleratorer, nämligen KVM för hårdvaruvirtualisering på Linux (för kompatibla gäst- och värdsystem), TCG för JIT-kodgenerering var som helst. Från och med QEMU 2.9 dök stöd för HAXM-hårdvaruvirtualiseringsstandarden upp på Windows (detaljerna)
• om TCG används och inte hårdvaruvirtualisering, har den separat kodgenereringsstöd för varje värdarkitektur, såväl som för den universella tolken
• ... och runt allt detta - emulerad kringutrustning, användargränssnitt, migrering, inspelningsrepris, etc.

Visste du förresten: QEMU kan emulera inte bara hela datorn utan även processorn för en separat användarprocess i värdkärnan, som till exempel används av AFL fuzzer för binär instrumentering. Kanske någon skulle vilja överföra detta funktionssätt för QEMU till JS? 😉

Som de flesta långvariga gratisprogram, byggs QEMU genom samtalet configure и make. Låt oss säga att du bestämmer dig för att lägga till något: en TCG-backend, trådimplementering, något annat. Skynda dig inte att vara glad/förskräckt (understryka vid behov) vid möjligheten att kommunicera med Autoconf - faktiskt, configure QEMU:s är tydligen självskrivna och genereras inte från någonting.

WebAssembly

Så vad heter den här saken WebAssembly (alias WASM)? Detta är en ersättning för Asm.js och utger sig inte längre för att vara giltig JavaScript-kod. Tvärtom, det är rent binärt och optimerat, och till och med bara att skriva ett heltal i det är inte särskilt enkelt: för kompakthet lagras det i formatet LEB128.

Du kanske har hört talas om relooping-algoritmen för Asm.js - det här är återställningen av "high-level" exekveringsflödeskontrollinstruktioner (det vill säga om-då-annat, loopar, etc.), för vilka JS-motorer är designade, från lågnivå LLVM IR, närmare maskinkoden som exekveras av processorn. Naturligtvis är den mellanliggande representationen av QEMU närmare den andra. Det verkar som att här är det, bytecode, slutet på plågan... Och så finns det block, if-then-else och loops!

Och detta är ytterligare en anledning till varför Binaryen är användbar: den kan naturligtvis acceptera högnivåblock nära det som skulle lagras i WASM. Men den kan också producera kod från en graf av grundläggande block och övergångar mellan dem. Tja, jag har redan sagt att det döljer WebAssembly-lagringsformatet bakom det bekväma C/C++ API.

TCG (Tiny Code Generator)

TCG var ursprungligen backend för C-kompilatorn. Sedan kunde den tydligen inte stå emot konkurrensen med GCC, men till slut hittade den sin plats i QEMU som en kodgenereringsmekanism för värdplattformen. Det finns också en TCG-backend som genererar en del abstrakt bytekod, som omedelbart exekveras av tolken, men jag bestämde mig för att undvika att använda den denna gång. Det faktum att det i QEMU redan är möjligt att möjliggöra övergången till den genererade TB genom funktionen tcg_qemu_tb_exec, det visade sig vara väldigt användbart för mig.

För att lägga till en ny TCG-backend till QEMU måste du skapa en underkatalog tcg/<имя архитектуры> (I detta fall, tcg/binaryen), och den innehåller två filer: tcg-target.h и tcg-target.inc.c и föreskriva allt handlar om configure. Du kan lägga andra filer där, men, som du kan gissa från namnen på dessa två, kommer de båda att inkluderas någonstans: en som en vanlig rubrikfil (den ingår i tcg/tcg.h, och den finns redan i andra filer i katalogerna tcg, accel och inte bara), den andra - bara som ett kodavsnitt i tcg/tcg.c, men den har tillgång till dess statiska funktioner.

När jag bestämde mig för att jag skulle spendera för mycket tid på detaljerade undersökningar av hur det fungerar, kopierade jag helt enkelt "skeletten" av dessa två filer från en annan backend-implementering, och indikerade ärligt detta i licenshuvudet.

fil tcg-target.h innehåller främst inställningar i formuläret #define-s:

• hur många register och vilken bredd finns det på målarkitekturen (vi har så många vi vill, så många vi vill - frågan är mer om vad som kommer att genereras till effektivare kod av webbläsaren på arkitekturen "helt mål" ...)
• justering av värdinstruktioner: på x86, och även i TCI, är instruktioner inte justerade alls, men jag ska inte lägga in instruktioner alls i kodbufferten, utan pekare till Binaryen-biblioteksstrukturer, så jag säger: 4 bytes
• vilka valfria instruktioner backend kan generera - vi inkluderar allt vi hittar i Binaryen, låt acceleratorn dela upp resten i enklare själv
• Vad är den ungefärliga storleken på TLB-cachen som begärs av backend. Faktum är att i QEMU är allt allvarligt: ​​även om det finns hjälpfunktioner som utför laddning/lagring med hänsyn till gäst-MMU (var skulle vi vara utan den nu?), sparar de sin översättningscache i form av en struktur, bearbetning som är bekväm att bädda in direkt i sändningsblock. Frågan är vilken offset i denna struktur som bearbetas mest effektivt av en liten och snabb sekvens av kommandon?
• här kan du justera syftet med ett eller två reserverade register, aktivera att ringa TB genom en funktion och eventuellt beskriva ett par små inline-funktioner som flush_icache_range (men detta är inte vårt fall)

fil tcg-target.inc.c, naturligtvis, är vanligtvis mycket större i storlek och innehåller flera obligatoriska funktioner:

• initiering, inklusive begränsningar för vilka instruktioner som kan fungera på vilka operander. Uppenbart kopierat av mig från en annan backend
• funktion som tar en intern bytekodinstruktion
• Du kan också lägga in hjälpfunktioner här, och du kan även använda statiska funktioner från tcg/tcg.c

För mig själv valde jag följande strategi: i de första orden i nästa översättningsblock skrev jag ner fyra pekare: ett startmärke (ett visst värde i närheten 0xFFFFFFFF, som bestämde det aktuella tillståndet för TB), kontext, genererad modul och magiskt nummer för felsökning. Först placerades märket in 0xFFFFFFFF - nvar n - ett litet positivt tal, och varje gång det utfördes via tolken ökade det med 1. När det nådde 0xFFFFFFFE, kompilering ägde rum, modulen sparades i funktionstabellen, importerades till en liten "startprogram", till vilken exekveringen gick från tcg_qemu_tb_exec, och modulen togs bort från QEMU-minnet.

För att parafrasera klassikerna, "Crutch, how much is intertwined in this sound for the proger's heart...". Men minnet läckte någonstans. Dessutom var det minne som hanterades av QEMU! Jag hade en kod som när jag skrev nästa instruktion (nåja, det vill säga en pekare) raderade den vars länk fanns på den här platsen tidigare, men det hjälpte inte. Faktiskt, i det enklaste fallet, allokerar QEMU minne vid start och skriver den genererade koden där. När bufferten tar slut kastas koden ut och nästa börjar skrivas på dess plats.

Efter att ha studerat koden insåg jag att tricket med det magiska numret tillät mig att inte misslyckas med högförstörelse genom att frigöra något fel på en oinitierad buffert vid första passet. Men vem skriver om bufferten för att kringgå min funktion senare? Som Emscripten-utvecklarna rekommenderar, när jag stötte på ett problem, portade jag den resulterande koden tillbaka till den ursprungliga applikationen, satte in Mozilla Record-Replay på den... I allmänhet insåg jag till slut en enkel sak: för varje block, a struct TranslationBlock med dess beskrivning. Gissa var... Just det, precis innan blocket precis i bufferten. När jag insåg detta bestämde jag mig för att sluta använda kryckor (åtminstone några), och kastade helt enkelt ut det magiska numret och överförde de återstående orden till struct TranslationBlock, skapa en enkellänkad lista som snabbt kan passeras när översättningscachen återställs, och frigöra minne.

Några kryckor finns kvar: till exempel markerade pekare i kodbufferten - några av dem är helt enkelt BinaryenExpressionRef, det vill säga, de tittar på de uttryck som måste läggas linjärt in i det genererade grundblocket, del är villkoret för övergång mellan BB, del är vart man ska gå. Jo, det finns redan förberedda block för Relooper som behöver kopplas in enligt förutsättningarna. För att särskilja dem används antagandet att de alla är justerade med minst fyra byte, så du kan säkert använda de minst signifikanta två bitarna för etiketten, du behöver bara komma ihåg att ta bort den om det behövs. Förresten, sådana etiketter används redan i QEMU för att indikera anledningen till att lämna TCG-slingan.

Använder Binaryen

Moduler i WebAssembly innehåller funktioner som var och en innehåller en body, vilket är ett uttryck. Uttryck är unära och binära operationer, block som består av listor med andra uttryck, kontrollflöde, etc. Som jag redan har sagt är kontrollflödet här organiserat precis som högnivågrenar, loopar, funktionsanrop, etc. Argument till funktioner skickas inte på stacken, utan explicit, precis som i JS. Det finns också globala variabler, men jag har inte använt dem, så jag kommer inte att berätta om dem.

Funktioner har också lokala variabler, numrerade från noll, av typen: int32 / int64 / float / double. I det här fallet är de första n lokala variablerna de argument som skickas till funktionen. Observera att även om allt här inte är helt på låg nivå när det gäller kontrollflöde, har heltal fortfarande inte attributet "signed/unsigned": hur numret beter sig beror på operationskoden.

Generellt sett tillhandahåller Binaryen enkel C-API: du skapar en modul, i honom skapa uttryck - unära, binära, block från andra uttryck, kontrollflöde, etc. Sedan skapar man en funktion med ett uttryck som sin kropp. Om du, som jag, har en övergångsgraf på låg nivå, kommer relooper-komponenten att hjälpa dig. Såvitt jag förstår är det möjligt att använda högnivåstyrning av exekveringsflödet i ett block, så länge det inte går utanför blockets gränser - det vill säga det är möjligt att göra intern snabb väg / långsam sökväg som förgrenas inuti den inbyggda TLB-cachebearbetningskoden, men inte för att störa det "externa" kontrollflödet . När du frigör en relooper frigörs dess block, när du frigör en modul försvinner uttrycken, funktionerna etc. som tilldelats den. arena.

Men om du vill tolka kod i farten utan att skapa och ta bort en tolkinstans i onödan, kan det vara vettigt att lägga in denna logik i en C++-fil, och därifrån direkt hantera hela C++-API:et i biblioteket, utan att klara- gjort omslag.

Så för att generera koden du behöver

// настроить глобальные параметры (можно поменять потом)
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);

... om jag har glömt något, förlåt, detta är bara för att representera skalan, och detaljerna finns i dokumentationen.

Och nu börjar crack-fex-pex, ungefär så här:

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);

För att på något sätt koppla ihop QEMU och JS världar och samtidigt snabbt komma åt de kompilerade funktionerna skapades en array (en funktionstabell för import till startprogrammet), och de genererade funktionerna placerades där. För att snabbt beräkna indexet användes indexet för nollordsöversättningsblocket initialt som det, men sedan började indexet som beräknades med denna formel helt enkelt passa in i fältet i struct TranslationBlock.

Förresten, demo (för närvarande med skum licens) fungerar bara bra i Firefox. Chrome-utvecklare var på något sätt inte redo till det faktum att någon skulle vilja skapa mer än tusen instanser av WebAssembly-moduler, så de tilldelade helt enkelt en gigabyte virtuellt adressutrymme för varje...

Det var allt tills vidare. Kanske kommer det en annan artikel om någon är intresserad. Det finns nämligen kvar åtminstone endast få blockenheter att fungera. Det kan också vara vettigt att göra kompileringen av WebAssembly-moduler asynkron, som är brukligt i JS-världen, eftersom det fortfarande finns en tolk som kan göra allt detta tills den inbyggda modulen är klar.

Till sist en gåta: du har kompilerat en binär på en 32-bitars arkitektur, men koden, genom minnesoperationer, klättrar från Binaryen, någonstans på stacken, eller någon annanstans i de övre 2 GB av 32-bitars adressutrymmet. Problemet är att från Binaryens synvinkel är detta att få tillgång till en för stor resulterande adress. Hur kommer man runt detta?

På administratörens sätt

Jag testade det inte till slut, men min första tanke var: "Vad händer om jag installerar 32-bitars?" Linux"Då kommer den övre delen av adressutrymmet att upptas av kärnan. Den enda frågan är hur mycket som kommer att upptas: 1 eller 2 GB."

På ett programmerings sätt (alternativ för utövare)

Låt oss blåsa en bubbla längst upp i adressutrymmet. Själv förstår jag inte varför det fungerar - där redan det måste finnas en stack. Men "vi är utövare: allt fungerar för oss, men ingen vet varför..."

// 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));
}

... det är sant att det inte är kompatibelt med Valgrind, men lyckligtvis driver Valgrind själv väldigt effektivt ut alla därifrån :)

Kanske kan någon ge en bättre förklaring av hur denna min kod fungerar...

Källa: will.com