For længe siden besluttede jeg mig for sjov at bevise reversibiliteten af processen og lære at generere JavaScript (mere præcist, Asm.js) fra maskinkode. For eksperimentet blev QEMU valgt, og kort tid efter blev der skrevet en artikel på Habr. I kommentarerne blev jeg rådet til at omarbejde projektet til WebAssembly, og det føltes ikke rart at opgive et næsten færdigt projekt… Arbejdet gik, men det gik bare utrolig langsomt, og for nylig dukkede der en op med spørgsmålet «Så hvordan endte det hele?» På mit udførlige svar hørte jeg «Det kunne blive til en artikel». Nå, hvis det kunne blive til en artikel, så skriver jeg en. Måske kan den bruges af nogen. Her vil læseren lære nogle fakta om arkitekturen bag QEMU's backend-kodegenerering, samt hvordan man skriver en Just-in-Time-kompilator til webapplikationer.
Opgaver
Da jeg allerede har lært at "slå" QEMU til JavaScript, blev det besluttet, at dette skulle gøres ordentligt og ikke gentage de samme fejl.
Fejl nummer et: forgrene sig fra point release
Min første fejl var at forgrene min version fra upstream-version 2.4.1. Dengang syntes det at være en god idé: hvis der findes en point release, så er den sikkert mere stabil end den almindelige 2.4, og slet ikke i forhold til grenen master. Og da jeg planlagde at tilføje en del egne fejl, havde jeg slet ikke brug for andres. Sådan blev det sikkert. Men her er problemet: QEMU står ikke stille, og på et tidspunkt annoncerede de endda optimeringen af den genererede kode med 10%. «Aha, nu skal jeg smelte det ind» tænkte jeg og blev skuffet. Her må jeg lave et tilbageblik: på grund af den enkelttrådede natur af QEMU.js og det faktum, at den originale QEMU ikke tillader fraværet af multitrådning (dvs. muligheden for samtidig udførelse af flere uafhængige code path er kritisk, ikke kun at "bruge alle kernerne"), blev de vigtigste funktioner i tråde "udtrukket" for at gøre dem kaldbare udefra. Dette skabte nogle naturlige problemer ved sammensmeltningen. Men det faktum, at nogle af ændringerne fra den gren master, som jeg forsøgte at smelte min kode ind i, også blev cherry picked ind i point release (og dermed også ind i min gren) ville heller ikke have gjort det lettere.
Generelt besluttede jeg, at prototypen stadig havde meningen at blive skrottet, nedbrudt i dele og bygget en ny version fra bunden baseret på noget nyere og nu allerede fra master.
Fejl nummer to: TLP-metodologi
I det væsentlige er det ikke en fejl — blot en særlig karakteristika ved at skabe et projekt under totale misforståelser som „hvordan og hvorhen skal vi bevæge os?“ og generelt „vil vi nå frem?“. Under disse omstændigheder sløset programmering var en berettiget løsning, men selvfølgelig ønskede jeg ikke at gentage det uden nødvendighed. Denne gang ønskede jeg at gøre det ordentligt: atomare commits, bevidste kodeændringer (og ikke „at stringe tilfældige tegn sammen indtil det kompilere (med advarsler)“, som Linus Torvalds en gang sagde om nogen, hvis man skal tro på Wikiquotes) osv.
Fejl nummer tre: at kaste sig ud i det uden at vide, hvor man skal hen
Derfor er jeg stadig ikke helt fri for det, men nu har jeg besluttet mig for ikke at tage den allermindste modstandsvej, og gøre det „som en voksen“, nemlig at skrive min egen TCG backend fra bunden, så jeg ikke senere kan sige „Ja, det er selvfølgelig langsomt, men jeg kan ikke kontrollere alt — TCI er skrevet sådan…“. Desuden så det oprindeligt ud til at være en ophavlig løsning, da jeg jo genererer binær kode. Som man siger, „Sammensatte Gent, men ikke den rigtige“: koden er selvfølgelig binær, men kontrollen kan ikke bare overføres — den skal eksplicit ind i browseren til kompilering, hvilket resulterer i et objekt fra JS-verdenen, som også skal gemmes et eller andet sted. Forresten, på normale RISC-arkitekturer, så vidt jeg forstår, er det typisk nødvendigt at nulstille cachet for instruktioner for den regenererede kode — hvis det ikke er helt præcist hvad vi har brug for, så er det i hvert fald tæt på. Derudover har jeg lært af mit tidligere forsøg, at kontrollen ikke overføres til midten af oversættelsesblokken, så vi har ikke rigtig brug for bytekode, der kan fortolkes fra enhver offset, og kan blot generere efter funktion på TB.afVi kom og sparkede
Selvom jeg begyndte at omskrive koden tilbage i juli, kom det magiske skub pludselig: normalt kommer mails fra GitHub som notifikationer om svar på Issues og Pull requests, men her,
pludselig nævnelse i tråden Binaryen som en QEMU backend Binaryen til at oprette WASM JIT. Nå, jeg sagde, at I har en Apache 2.0-licens, men QEMU som helhed distribueres under GPLv2, og de er ikke helt kompatible. Pludselig viste det sig, at licensen kunne at få det til at fungere på en eller anden måde (jeg ved ikke: måske ændre det, måske dobbeltlicensering, måske noget helt andet…). Det gjorde mig selvfølgelig glad, for jeg havde allerede flere gange set på WebAssembly, og jeg følte mig lidt trist og forvirret. Men her var der et bibliotek, der kunne håndtere grundlæggende byggesten med en overgangsgraf, generere bytekode, og endda køre det i en fortolker, hvis det var nødvendigt.
Senere var der også på QEMU-distributionlisten, men det er mere et spørgsmål om, "Hvem har overhovedet brug for det?". Og det viste sig, nævnelse i trådenat det var nødvendigt. I hvert fald kan man finde nogle anvendelsesmuligheder, hvis det fungerer nogenlunde hurtigt:
- køre noget læringsprogram uden installation
- virtualisering på iOS, hvor der efter sigende kun er én applikation, der har ret til at generere kode on-the-fly — det er JS-motoren (og er det sandt?)
- demonstration af et mini-OS — diskettedrev, indlejrede, forskellige firmware osv...
Særligheder ved browserens runtime-miljø
Som jeg allerede har nævnt, er QEMU afhængig af multitrådning, men der er ikke sådan noget i en browser. Nå, det vil sige, det var ikke der i starten… Først var der overhovedet ikke noget, så kom WebWorkers — så vidt jeg forstår, er det multitrådning baseret på beskedoverførsel uden fælles ændrede variabler. Naturligvis skaber dette betydelige problemer, når eksisterende kode, der er baseret på en delt hukommelsesmodel, skal overføres. Senere, under presset fra offentligheden, blev det implementeret som SharedArrayBuffers. Det blev gradvist introduceret, og lanceringen blev fejret i forskellige browsere, så blev nytåret fejret, og så kom Meltdown... Efterfølgende kom man til den konklusion, at uanset hvordan man måler tiden, ville det stadig være . Så de deaktiverede multitrådning med delt hukommelse. Det syntes at være blevet aktiveret igen senere, men som det blev tydeligt fra det første eksperiment, er livet muligt uden det, og derfor vil vi prøve at gøre det uden at stole på multitrådning.
Den anden funktion ligge i umuligheden af lave lavniveau-manipulationer med stakken: man kan ikke bare tage, gemme den nuværende kontekst og skifte til en ny med en ny stak. Stakopkald styres af JS's virtuelle maskine. Hvad er problemet, når vi alligevel har valgt at styre med de tidligere tråde helt manuelt? Problemet er, at blokering I/O i QEMU er implementeret via koroutiner, og det er her, vi ville have haft glæde af lavniveau-manipulationer af stakken. Heldigvis indeholder Emscripten allerede en mekanisme for asynkrone operationer, endda to: og . Den første virker gennem betydelig oppustning af den genererede JavaScript-kode og understøttes ikke længere. Den anden er den nuværende "rette måde" og fungerer gennem generering af bytekode til sin egen interpreter. Den fungerer, selvfølgelig, langsomt, men puster ikke koden op. Dog blev understøttelsen af koroutiner til denne mekanisme nødt til at blive bidraget af os selv (der var allerede koroutiner skrevet til Asyncify, og der var en implementering af omtrent det samme API til Emterpreter, det var bare nødvendigt at forbinde dem).
Indtil nu har jeg ikke haft tid til at opdele koden i den, der kan kompileres til WASM og den, der kan tolkes via Emterpreter, så blokenhederne virker endnu ikke (hold øje med de kommende episoder, som man siger…). Det vil sige, at det endelige resultat skal være sådan et sjovt lagdelt noget:
- tolket blokering I/O. Nå ja, forventede du virkelig en emuleret NVMe med native ydeevne? 🙂
- statiske kompileret hovedkode til QEMU (translator, andre emulerede enheder osv.)
- dynamisk kompilering til WASM gæstekode
Egenskaber ved QEMU-kildekoden
Som du sikkert allerede har gættet, er koden til emulering af gæstearkitekturer og koden til generering af værtens maskinkode i QEMU adskilt. Faktisk er det endda lidt mere indviklet:
- der er gæstearkitekturer
- er acceleratorer, nemlig KVM til hardwarevirtualisering på Linux (til kompatible gæste- og værtssystemer), TCG til JIT-kodet generering hvor som helst. Siden QEMU 2.9 er der blevet tilføjet understøttelse af standarden for hardwarevirtualisering HAXM på Windows ()
- hvis der bruges TCG i stedet for hardwarevirtualisering, så har det særskilt understøttelse af kodegenerering til hver værtarkitektur samt til en universel fortolker
- … og omkring dette - emuleret perifer udstyr, brugergrænseflade, migration, record-replay osv.
Forresten, vidste du: QEMU kan emulere ikke kun en hel computer, men også en processor for en separat brugerproces i værtskernen, hvilket for eksempel bruges af fuzzeren AFL til instrumentering af binære filer. Måske vil nogen gerne porte denne QEMU-arbejdsmetode til JS? 😉
Som med de fleste ældre frit tilgængelige programmer, bygges QEMU ved at kalde configure og make. Antag, at du besluttede at tilføje noget: TCG-backend, implementering af tråde, noget andet. Skynd dig ikke til at glæde/sørge (understrege det nødvendige) over udsigten til at interagere med Autoconf - faktisk, configure QEMU har tilsyneladende en egenudviklet løsning, der ikke genereres af noget.
WebAssembly
Hvad er så denne ting - WebAssembly (også kendt som WASM)? Det er en erstatning for Asm.js, som nu ikke længere forsøger at være gyldig JavaScript-kode. I modsætning hertil er det udelukkende binært og optimeret, og det er endda ikke særlig let blot at skrive et helt tal ind i det: det opbevares kompakt i formatet .
Måske har du hørt om relooping-algoritmen til Asm.js - det er genoprettelsen af 'højere niveau' kontrolinstrukser (det vil sige if-then-else, loops osv.), som JS-motorer er tilpasset til, fra lavere niveau LLVM IR, som er tættere på maskinkode, der udføres af processoren. Naturligvis er det mellemliggende repræsentation fra QEMU tættere på det andet. Det ser ud til, at her er bytekoden, slutningen på lidelserne... Og så if-then-else-blocke og loops!..
Og dette er endnu en grund til, at Binaryen er nyttig: den kan naturligvis tage høj-niveau blocke, der er tættere på det, der vil blive gemt i WASM. Men den kan også generere kode fra grafen over basale blokke og overgange mellem dem. Og hvad den skjuler bag det brugervenlige C/C++ API til lagringsformatet for WebAssembly, har jeg allerede nævnt.
TCG (Tiny Code Generator)
TCG backend til C-kompilatoren. Derefter kunne den tilsyneladende ikke konkurrere med GCC, men fandt til sidst sin plads i QEMU som en mekanisme til kodegenerering til værtplatformen. Der findes også en TCG-backend, der genererer en slags abstrakt bytekode, som straks udføres af en fortolker, men jeg besluttede at undgå at bruge den denne gang. Dog var det en fordel, at der allerede i QEMU er mulighed for at skifte til den genererede TB via funktionen tcg_qemu_tb_exec, hvilket viste sig at være meget nyttigt for mig.
For at tilføje en ny TCG-backend til QEMU skal du oprette en undermappe tcg/ (i dette tilfælde, tcg/binaryen), og i den skal der være to filer: tcg-target.h og tcg-target.inc.c og alt dette i configure. Du kan også lægge andre filer der, men som du kan gætte ud fra navnene på disse to, vil de begge blive inkluderet et eller andet sted: den ene som en almindelig header-fil (den inkluderes i tcg/tcg.h, og den anden i andre filer i mapperne tcg, accel og ikke kun), den anden — kun som en kode-snippet i tcg/tcg.c, men den har adgang til dens statiske funktioner.
Da jeg besluttede, at jeg ville bruge for lang tid på detaljeret at undersøge, hvordan det fungerede, kopierede jeg blot "skeletterne" af disse to filer fra en anden backend-implementering og angav ærligt dette i licensoverskriften.
Fil tcg-target.h indeholder hovedsageligt indstillinger i form af #define-er:
- hvor mange registre og hvilken bredde der er på den målrettede arkitektur (i vores tilfælde — hvor mange vi vil have, det er mere et spørgsmål om, hvad der vil blive genereret til mere effektiv kode i browseren på den "faktiske målrettede" arkitektur…)
- justering af værtinstruktionerne: på x86, og faktisk i TCI, justeres instruktionerne slet ikke, jeg planlægger at lægge i kodebufferen og ikke instruktionerne overhovedet, men præcist henvisninger til strukturerne i biblioteket Binaryen, så jeg siger: 4 byte
- hvilke valgfrie instruktioner backend kan generere — aktiver alt, hvad vi finder i Binaryen, lad resten blive opdelt i mere enkle af acceleratoren selv
- hvad er den omtrentlige størrelse på TLB-cachen, som backend anmoder om. Dit er, at i QEMU er alt alvorligt: selvom der er hjælpefunktioner, der udfører load/store under hensyntagen til gæste-MMU (hvor ville man være uden det?), gemmer deres eget oversættelsescache det som en struktur, hvis behandling er praktisk at integrere direkte i oversættelsesblokke. Spørgsmålet er, hvilket offset i denne struktur der mest effektivt behandles af en lille og hurtig sekvens af kommandoer.
- her kan man også justere tildelingen af en eller to reserverede registre, aktivere opkald til TB via funktion og valgfrit beskrive et par småting.
inline-funktioner somflush_icache_range(men det er ikke vores tilfælde)
Fil tcg-target.inc.c, naturligvis, er normalt meget større i størrelse og indeholder flere obligatoriske funktioner:
- initialisering, der angiver blandt andet begrænsningerne for, hvilken instruktion der kan arbejde med hvilke operander. Råkopieret af mig fra en anden backend.
- en funktion, der modtager en instruktion fra det interne bytecode
- til dette kan man også placere hjælpefunktioner, og her kan man bruge statiske funktioner fra
tcg/tcg.c
For mig valgte jeg følgende strategi: i de første ord i den næste oversættelsesblok indskrev jeg fire pegepunkter: startmærket (en værdi i nærheden af 0xFFFFFFFF, hvortil den nuværende tilstand af TB blev bestemt), konteksten, den genererede modul og magic number til fejlfinding. Først blev mærket sat til 0xFFFFFFFF - n, hvor n — et lille positivt tal, og ved hver udførelse gennem fortolkeren blev det øget med 1. Da det nåede til 0xFFFFFFFE, fandt kompileringen sted, og modulet blev gemt i en funktions tabel, der blev importeret til en lille "starter", hvor udførelsen gik hen til tcg_qemu_tb_exec, mens modulet blev fjernet fra QEMU's hukommelse.
For at parafrasere en klassiker, "Hæk, hvor meget der i denne lyd for programmørens hjerte er vævet...". Ikke desto mindre, så forsvandt hukommelsen et sted. Og det var hukommelse, der blev styret af QEMU! Jeg havde kode, der ved skrivning af den næste instruktion (altså, pegepind) fjernede den, som før var henvist til dette sted, men det hjalp ikke. Generelt set, i det simpleste tilfælde allokerer QEMU hukommelse ved opstart og skriver den genererede kode der. Når bufferen er fyldt, kasseres koden, og den næste begynder at blive skrevet på dens sted.
Efter at have studeret koden indså jeg, at hacken med magic number forhindrede nedbrud ved at frigive noget forkert i en uinitialiseret buffer ved første gennemgang. Men hvem skriver derefter bufferen udenom min funktion? Som Emscripten-udviklerne anbefaler, stødte jeg på problemet og portede koden tilbage til en native applikation, og trak Mozilla Record-Replay ind... Alt i alt indså jeg én enkel ting: for hver blok tildeles struct Oversættelsesblok med dens beskrivelse. Gæt hvor... Korrekt, direkte før blokken i bufferen. Da jeg indså dette, besluttede jeg at stoppe med hacks (i det mindste nogle), og smed simpelthen magic number væk, mens jeg flyttede de resterende ord over i struct Oversættelsesblok, og oprettede en enkeltkædet liste, som man hurtigt kan gå igennem, når caching af oversættelsen nulstilles, og dermed frigive hukommelse.
Nogle hacks er stadig tilbage: for eksempel mærkede pegepinde i kodebufferen - nogle af dem er blot BinaryenExpressionRef, dvs. de refererer til de udtryk, der skal placeres lineært i det genererede grundlæggende blok, mens nogle er betingelser for overgange mellem blokke, og nogle - hvor man skal gå hen. Og der er allerede forberedte blokke til Relooper, som skal forbindes efter betingelser. For at skelne dem bruges antagelsen om, at de alle er justeret på mindst fire bytes, så man trygt kan bruge de to laveste bits til mærker, man skal bare huske at fjerne dem, når det er nødvendigt. Forresten, sådanne mærker bruges allerede i QEMU for at indikere årsagen til udgangen fra TCG-cyklussen.
Brugen af Binaryen
Moduler i WebAssembly indeholder funktioner, hvor hver funktion har en kropp, der består af et udtryk. Udtryk er en- og to-parameter operationer, blokke der består af lister over andre udtryk, kontrolflytning osv. Som jeg allerede har nævnt, er kontrolflytning her organiseret som højniveaus forgreninger, sløjfer, funktionsopkald osv. Argumenter til funktioner sendes ikke på stakken, men eksplicit, ligesom i JS. Der er også globale variabler, men jeg har ikke brugt dem, så jeg vil ikke fortælle om dem.
Funktioner har også numrerede lokale variabler, der starter fra nul og har typen: int32 / int64 / float / double. De første n lokale variabler er argumenterne, der sendes til funktionen. Bemærk, at selvom dette ikke er helt lavniveau i forhold til kontrolflow, bærer hele tal ikke et tegn på "tegn/unsigned": hvordan et tal opfører sig, afhænger af operationens kode.
Generelt set tilbyder Binaryen : du opretter et modul, i hvilket du opretter udtryk — unære, binære, blokke af andre udtryk, kontrolflow osv. Derefter opretter du en funktion, hvor kroppen skal angive et udtryk. Hvis du, ligesom mig, har et lavniveau kontrolflowgraf — vil komponenten relooper hjælpe dig. Så vidt jeg forstår, kan højere niveau kontrolflow anvendes i blokken, så længe det ikke går ud over blokken — det vil sige, at indre forgreninger som fast path / slow path inden for den indbyggede TLB-cachebehandling er muligt, men at blande sig i det "ydre" kontrolflow er ikke tilladt. Når du frigiver relooper, frigives dens blokke; når du frigiver modulet, forsvinder udtrykene, funktionerne osv., der er tildelt dens arena..
Men hvis du ønsker at fortolke koden on-the-fly uden unødvendige oprettelser og sletninger af fortolkerinstanser, kan det give mening at flytte denne logik til en C++-fil og derfra direkte styre hele C++ API'et i biblioteket, uden at skulle bruge de færdige indpakninger.
Således, for at generere kode, er det nødvendigt
// настроить глобальные параметры (можно поменять потом)
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);… hvis jeg glemte noget — undskyld, det er blot for at give en idé om omfanget, og detaljerne findes i dokumentationen.
Og nu begynder kracks-feks-peks, omtrent sådan:
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,
// ...
}
);
// og nu har du allerede en instance!
}, buf, sz);For somehow linking the QEMU world with JS and quickly accessing compiled functions, an array (a function import table) was created, where generated functions were placed. Initially, the index of the first word of the translation block was used for quick indexing, but then the index calculated by such a formula started to simply fit into the field. struct Oversættelsesblok.
Forresten, (for now with a murky license) works fine only in Firefox. Chrome's developers were somehow unprepared for the fact that someone would want to create more than a thousand instances of WebAssembly modules, so they simply allocated one gigabyte of virtual address space for each…
That's it for now. There might be another article if anyone is interested. Specifically, there is at least just make block devices work. It might also make sense to make the compilation of WebAssembly modules asynchronous, as is customary in the JS world, since there is an interpreter that can execute everything while the native module is not ready.
Finally, a riddle: you compiled a binary for a 32-bit architecture, but the code via memory operations is spilling out from Binaryen, somewhere onto the stack or somewhere else in the upper 2 GB of the 32-bit address space. The problem is that from Binaryen's perspective this access is to a resulting address that is too large. How to overcome this?
From an admin's perspective
I ultimately didn’t test this, but my first thought was, 'What if I set up a 32-bit Linux?' Then the upper part of the address space will be occupied by the kernel. The only question is how much will be occupied: 1 or 2 Gb.
From a programmer's perspective (a practical option)
We will inflate a bubble in the upper part of the address space. I don't even understand why it works—there should be a stack there. But 'we are practitioners: everything works for us, but no one knows why...'. allerede … with Valgrind, though it is not compatible, but fortunately, Valgrind itself very effectively drives everyone out from there 🙂
// 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));
}Perhaps someone will provide a better explanation of how this code of mine works...
Qemu.js with JIT support: the minced meat can still be turned back
Kilde: habr.com
