Engang besluttede jeg mig for sjov bevise reversibiliteten af processen og lær, hvordan du genererer JavaScript (mere præcist, Asm.js) fra maskinkode. QEMU blev valgt til forsøget, og noget tid senere blev der skrevet en artikel om Habr. I kommentarerne blev jeg rådet til at lave om på projektet i WebAssembly og endda selv afslutte næsten færdig Jeg ville på en eller anden måde ikke have projektet ... Arbejdet var i gang, men meget langsomt, og nu, for nylig i den artikel dukkede op om emnet "Så hvordan endte det hele?" Som svar på mit detaljerede svar hørte jeg "Dette lyder som en artikel." Nå, hvis du kan, vil der være en artikel. Måske vil nogen finde det nyttigt. Fra den vil læseren lære nogle fakta om designet af QEMU-kodegenererings-backends, samt hvordan man skriver en Just-in-Time compiler til en webapplikation.
opgaver
Da jeg allerede havde lært, hvordan man "på en eller anden måde" porterer QEMU til JavaScript, blev det denne gang besluttet at gøre det klogt og ikke gentage gamle fejl.
Fejl nummer et: forgrening fra punktudgivelse
Min første fejl var at dele min version fra upstream-versionen 2.4.1. Så forekom det mig en god idé: hvis der findes punktudløsning, så er den nok mere stabil end simpel 2.4, og endnu mere grenen master. Og da jeg planlagde at tilføje en hel del af mine egne fejl, havde jeg slet ikke brug for andres. Sådan blev det nok. Men her er sagen: QEMU står ikke stille, og på et tidspunkt annoncerede de endda optimering af den genererede kode med 10 procent."Ja, nu fryser jeg," tænkte jeg og brød sammen. Her er vi nødt til at lave en digression: på grund af den enkelt-trådede karakter af QEMU.js og det faktum, at den oprindelige QEMU ikke indebærer fravær af multi-threading (det vil sige evnen til samtidig at betjene flere urelaterede kodestier, og ikke bare "brug alle kerner") er afgørende for det, hovedfunktionerne i tråde var jeg nødt til at "slå det ud" for at kunne kalde udefra. Det skabte nogle naturlige problemer under fusionen. Men det faktum, at nogle af ændringerne fra filialen master, som jeg forsøgte at flette min kode med, blev også plukket cherry i punktudgivelsen (og derfor i min filial) og ville sandsynligvis ikke have tilføjet bekvemmelighed.
Generelt besluttede jeg, at det stadig giver mening at smide prototypen ud, skille den ad for dele og bygge en ny version fra bunden baseret på noget friskere og nu fra master.
Fejl nummer to: TLP-metoden
I bund og grund er dette ikke en fejl, generelt er det bare en funktion ved at skabe et projekt under forhold med fuldstændig misforståelse af både "hvor og hvordan man flytter?" og generelt "vil vi nå dertil?" Under disse forhold klodset programmering var en berettiget mulighed, men jeg ønskede naturligvis ikke at gentage det unødigt. Denne gang ville jeg gøre det klogt: atomar begåelser, bevidste kodeændringer (og ikke "strenge tilfældige tegn sammen, indtil det kompileres (med advarsler)", som Linus Torvalds engang sagde om nogen, ifølge Wikiquote), osv.
Fejl nummer tre: at komme i vandet uden at kende vadestedet
Det er jeg stadig ikke helt sluppet af med, men nu har jeg besluttet slet ikke at følge den mindste modstands vej, og at gøre det “som voksen”, nemlig at skrive min TCG-backend fra bunden, for ikke at at skulle sige senere: "Ja, det er selvfølgelig langsomt, men jeg kan ikke kontrollere alt - det er sådan TCI er skrevet..." Desuden virkede dette oprindeligt som en oplagt løsning, da Jeg genererer binær kode. Som de siger: "Gent samledesу, men ikke den”: koden er selvfølgelig binær, men kontrol kan ikke bare overføres til den - den skal eksplicit skubbes ind i browseren til kompilering, hvilket resulterer i et bestemt objekt fra JS-verdenen, som stadig skal blive gemt et sted. Men på normale RISC-arkitekturer, så vidt jeg forstår, er en typisk situation behovet for eksplicit at nulstille instruktionscachen for regenereret kode - hvis det ikke er det, vi har brug for, så er det under alle omstændigheder tæt på. Derudover lærte jeg fra mit sidste forsøg, at kontrol ikke ser ud til at blive overført til midten af oversættelsesblokken, så vi behøver ikke rigtig bytekode fortolket fra nogen offset, og vi kan simpelthen generere den fra funktionen på TB .
De kom og sparkede
Selvom jeg begyndte at omskrive koden tilbage i juli, sneg der sig et magisk kick frem ubemærket: normalt ankommer breve fra GitHub som meddelelser om svar på problemer og pull-anmodninger, men her, pludselig nævnes i tråden i sammenhængen, "Han gjorde sådan noget, måske vil han sige noget." Vi talte om at bruge Emscriptens relaterede bibliotek at skabe WASM JIT. Nå, jeg sagde, at du har en Apache 2.0-licens der, og QEMU som helhed er distribueret under GPLv2, og de er ikke særlig kompatible. Pludselig viste det sig, at en licens kan være ordne det på en eller anden måde (Jeg ved det ikke: måske ændre det, måske dobbelt licens, måske noget andet...). Dette gjorde mig selvfølgelig glad, for på det tidspunkt havde jeg allerede set nøje på WebAssembly, og jeg var på en eller anden måde trist og uforståelig. Der var også et bibliotek, der ville fortære de grundlæggende blokke med overgangsgrafen, producere bytekoden og endda køre den i selve fortolkeren, hvis det var nødvendigt.
Så var der mere på QEMU-mailinglisten, men dette handler mere om spørgsmålet "Hvem har brug for det?" Og det er pludselig, viste det sig, at det var nødvendigt. Du kan som minimum skrabe følgende anvendelsesmuligheder sammen, hvis det virker mere eller mindre hurtigt:
- lancere noget lærerigt uden nogen installation overhovedet
- virtualisering på iOS, hvor, ifølge rygter, den eneste applikation, der har ret til kodegenerering i farten, er en JS-motor (er dette sandt?)
- demonstration af mini-OS - single-floppy, indbygget, alle former for firmware osv...
Browser Runtime-funktioner
Som jeg allerede har sagt, er QEMU bundet til multithreading, men det har browseren ikke. Nå, det vil sige nej... Først eksisterede det slet ikke, så dukkede WebWorkers op - så vidt jeg forstår, er dette multithreading baseret på meddelelser uden fælles variable. Dette skaber naturligvis betydelige problemer ved portering af eksisterende kode baseret på den delte hukommelsesmodel. Så blev det under offentligt pres også implementeret under navnet SharedArrayBuffers. Det blev gradvist indført, de fejrede dens lancering i forskellige browsere, så fejrede de nytår, og derefter Meltdown... Hvorefter de kom til den konklusion, at groft eller groft tidsmålingen, men ved hjælp af fælles hukommelse og en tråd, der øger tælleren, det er det samme . Så vi deaktiverede multithreading med delt hukommelse. Det ser ud til, at de senere tændte det igen, men som det blev klart fra det første eksperiment, er der liv uden det, og hvis det er tilfældet, vil vi prøve at gøre det uden at stole på multithreading.
Den anden funktion er umuligheden af manipulationer på lavt niveau med stakken: du kan ikke bare tage, gemme den aktuelle kontekst og skifte til en ny med en ny stak. Opkaldsstakken administreres af den virtuelle JS-maskine. Det ser ud til, hvad er problemet, da vi stadig besluttede at styre de tidligere flows helt manuelt? Faktum er, at blok I/O i QEMU er implementeret gennem coroutines, og det er her, lav-niveau stack manipulationer ville være nyttige. Heldigvis indeholder Emscipten allerede en mekanisme til asynkrone operationer, endda to: и . Den første virker gennem et betydeligt opsvulmning i den genererede JavaScript-kode og understøttes ikke længere. Den anden er den nuværende "korrekte måde" og fungerer gennem bytekodegenerering for den oprindelige fortolker. Det virker selvfølgelig langsomt, men det blæser ikke koden op. Det er sandt, at understøttelse af coroutiner til denne mekanisme skulle bidrages uafhængigt (der var allerede skrevet coroutiner til Asyncify, og der var en implementering af omtrent det samme API til Emterpreter, du skulle bare forbinde dem).
I øjeblikket er det endnu ikke lykkedes mig at dele koden op i en kompileret i WASM og tolket ved hjælp af Emterpreter, så blokenheder virker ikke endnu (se i næste serie, som man siger...). Det vil sige, i sidste ende skulle du få noget som denne sjove lagdelte ting:
- fortolket blok I/O. Nå, forventede du virkelig emuleret NVMe med indbygget ydeevne? 🙂
- statisk kompileret hoved-QEMU-kode (oversætter, andre emulerede enheder osv.)
- dynamisk kompileret gæstekode i WASM
Funktioner af QEMU-kilder
Som du sikkert allerede har gættet, er koden til at emulere gæstearkitekturer og koden til generering af værtsmaskininstruktioner adskilt i QEMU. Faktisk er det endnu lidt vanskeligere:
- der er gæstearkitekturer
- Der er acceleratorer, nemlig KVM til hardwarevirtualisering på Linux (til gæste- og værtssystemer, der er kompatible med hinanden), TCG til generering af JIT-kode hvor som helst. Startende med QEMU 2.9 dukkede understøttelse af HAXM hardwarevirtualiseringsstandarden på Windows op ()
- hvis TCG bruges i stedet for hardwarevirtualisering, så har den separat kodegenereringsunderstøttelse for hver værtsarkitektur såvel som for den universelle fortolker
- ... og omkring alt dette - emuleret periferiudstyr, brugergrænseflade, migrering, optag-genafspilning osv.
Vidste du forresten: QEMU kan emulere ikke kun hele computeren, men også processoren til en separat brugerproces i værtskernen, som f.eks. bruges af AFL fuzzer til binær instrumentering. Måske nogen vil overføre denne funktionsmåde for QEMU til JS? 😉
Som de fleste mangeårige gratis software er QEMU bygget gennem opkaldet configure и make. Lad os sige, at du beslutter dig for at tilføje noget: en TCG-backend, trådimplementering, noget andet. Skynd dig ikke at være glad/forskrækket (understreg efter behov) ved udsigten til at kommunikere med Autoconf - faktisk, configure QEMU'er er tilsyneladende selvskrevne og er ikke genereret ud fra noget.
WebAssembly
Så hvad hedder denne ting WebAssembly (alias WASM)? Dette er en erstatning for Asm.js, der ikke længere foregiver at være gyldig JavaScript-kode. Tværtimod er det rent binært og optimeret, og selv blot at skrive et heltal ind i det er ikke særlig simpelt: for kompakthed er det gemt i formatet .
Du har måske hørt om relooping-algoritmen til Asm.js - dette er gendannelsen af "high-level" flowkontrolinstruktioner (det vil sige hvis-så-andet, loops osv.), som JS-motorer er designet til, fra lav-niveau LLVM IR, tættere på maskinkoden, der udføres af processoren. Naturligvis er mellemrepræsentationen af QEMU tættere på den anden. Det ser ud til, at her er det, bytecode, slutningen på plagen... Og så er der blokke, hvis-så-andet og loops!..
Og dette er en anden grund til, at Binaryen er nyttig: den kan naturligvis acceptere højniveaublokke tæt på, hvad der ville blive gemt i WASM. Men det kan også producere kode fra en graf af grundlæggende blokke og overgange mellem dem. Nå, jeg har allerede sagt, at det skjuler WebAssembly-lagringsformatet bag den praktiske C/C++ API.
TCG (Tiny Code Generator)
TCG backend til C-kompileren. Så kunne den tilsyneladende ikke modstå konkurrencen med GCC, men i sidste ende fandt den sin plads i QEMU som en kodegenereringsmekanisme til værtsplatformen. Der er også en TCG-backend, der genererer noget abstrakt bytekode, som straks udføres af tolken, men jeg besluttede at undgå at bruge det denne gang. Men det faktum, at det i QEMU allerede er muligt at muliggøre overgangen til den genererede TB gennem funktionen tcg_qemu_tb_exec, det 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 den indeholder to filer: tcg-target.h и tcg-target.inc.c и det handler om configure. Du kan lægge andre filer der, men som du kan gætte ud fra navnene på disse to, vil de begge blive inkluderet et sted: en som en almindelig header-fil (den er inkluderet i tcg/tcg.h, og at man allerede er i andre filer i mapperne tcg, accel og ikke kun), den anden - kun som et kodestykke ind tcg/tcg.c, men den har adgang til sine statiske funktioner.
Da jeg besluttede, at jeg ville bruge for meget tid på detaljerede undersøgelser af, hvordan det fungerer, kopierede jeg simpelthen "skeletterne" af disse to filer fra en anden backend-implementering, hvilket ærligt indikerede dette i licensoverskriften.
fil tcg-target.h indeholder hovedsageligt indstillinger i formularen #define-s:
- hvor mange registre og hvilken bredde er der på målarkitekturen (vi har så mange vi vil have, så mange vi vil - spørgsmålet er mere om, hvad der vil blive genereret til mere effektiv kode af browseren på "fuldstændig mål"-arkitekturen ...)
- justering af værtsinstruktioner: på x86, og endda i TCI, er instruktioner slet ikke justeret, men jeg vil ikke lægge instruktioner i kodebufferen overhovedet, men pointere til Binaryen biblioteksstrukturer, så jeg vil sige: 4 bytes
- hvilke valgfri instruktioner backend kan generere - vi inkluderer alt, hvad vi finder i Binaryen, lad acceleratoren dele resten op i enklere selv
- Hvad er den omtrentlige størrelse af den TLB-cache, der anmodes om af backend. Faktum er, at i QEMU er alt seriøst: selvom der er hjælpefunktioner, der udfører load/store under hensyntagen til gæste-MMU'en (hvor ville vi være uden den nu?), gemmer de deres oversættelsescache i form af en struktur, behandling, som er praktisk at integrere direkte i broadcast-blokke. Spørgsmålet er, hvilken offset i denne struktur behandles mest effektivt af en lille og hurtig sekvens af kommandoer?
- her kan du justere formålet med et eller to reserverede registre, aktivere opkald til TB gennem en funktion og eventuelt beskrive et par små
inline-funktioner somflush_icache_range(men det er ikke vores tilfælde)
fil tcg-target.inc.c, selvfølgelig, er normalt meget større i størrelse og indeholder flere obligatoriske funktioner:
- initialisering, herunder begrænsninger for, hvilke instruktioner der kan fungere på hvilke operander. Åbenbart kopieret af mig fra en anden backend
- funktion, der tager en intern bytekode-instruktion
- Du kan også lægge hjælpefunktioner her, og du kan også bruge statiske funktioner fra
tcg/tcg.c
For mig selv valgte jeg følgende strategi: i de første ord i den næste oversættelsesblok skrev jeg fire pointer ned: et startmærke (en vis værdi i nærheden 0xFFFFFFFF, som bestemte den aktuelle tilstand af TB), kontekst, genereret modul og magisk tal til fejlretning. Først blev mærket sat ind 0xFFFFFFFF - nHvor n - et lille positivt tal, og hver gang det blev udført gennem tolken steg det med 1. Når det nåede 0xFFFFFFFE, kompilering fandt sted, modulet blev gemt i funktionstabellen, importeret til en lille "launcher", hvori udførelsen gik fra tcg_qemu_tb_exec, og modulet blev fjernet fra QEMU-hukommelsen.
For at omskrive klassikerne, "Crutch, how much is intertwined in this sound for proger's heart...". Men hukommelsen læk et sted. Desuden var det hukommelse styret af QEMU! Jeg havde en kode, der, da jeg skrev den næste instruktion (nå, altså en pointer), slettede den, hvis link var på dette sted tidligere, men det hjalp ikke. Faktisk, i det enkleste tilfælde, allokerer QEMU hukommelse ved opstart og skriver den genererede kode der. Når bufferen løber tør, bliver koden smidt ud, og den næste begynder at blive skrevet på sin plads.
Efter at have studeret koden, indså jeg, at tricket med det magiske nummer tillod mig ikke at fejle på heap-ødelæggelse ved at frigive noget forkert på en uinitialiseret buffer ved det første gennemløb. Men hvem omskriver bufferen for at omgå min funktion senere? Som Emscripten-udviklerne rådgiver, da jeg løb ind i et problem, porterede jeg den resulterende kode tilbage til den oprindelige applikation, satte Mozilla Record-Replay på den... Generelt indså jeg til sidst en simpel ting: for hver blok, -en struct TranslationBlock med dens beskrivelse. Gæt hvor... Det er rigtigt, lige før blokken lige i bufferen. Da jeg indså dette, besluttede jeg at holde op med at bruge krykker (i hvert fald nogle), og smed simpelthen det magiske tal ud og overførte de resterende ord til struct TranslationBlock, opretter en enkelt-linket liste, der hurtigt kan gennemløbes, når oversættelsescachen nulstilles, og frigør hukommelse.
Nogle krykker forbliver: for eksempel markerede pointere i kodebufferen - nogle af dem er simpelthen BinaryenExpressionRef, det vil sige, de ser på de udtryk, der skal sættes lineært ind i den genererede basisblok, del er betingelsen for overgang mellem BB'er, del er, hvor man skal hen. Nå, der er allerede forberedte blokke til Relooper, der skal tilsluttes efter forholdene. For at skelne dem, bruges den antagelse, at de alle er justeret med mindst fire bytes, så du kan trygt bruge de mindst signifikante to bits til etiketten, du skal blot huske at fjerne den, hvis det er nødvendigt. Sådanne mærker bruges i øvrigt allerede i QEMU for at angive årsagen til at forlade TCG-løkken.
Brug af Binaryen
Moduler i WebAssembly indeholder funktioner, som hver indeholder en krop, som er et udtryk. Udtryk er unære og binære operationer, blokke bestående af lister over andre udtryk, kontrolflow osv. Som jeg allerede har sagt, er kontrolflowet her organiseret præcist som forgreninger på højt niveau, loops, funktionskald 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å dem vil jeg ikke fortælle dig om.
Funktioner har også lokale variable, nummereret fra nul, af typen: int32 / int64 / float / double. I dette tilfælde er de første n lokale variable de argumenter, der sendes til funktionen. Bemærk venligst, at selvom alt her ikke er helt lavt niveau med hensyn til kontrolflow, bærer heltal stadig ikke "signed/unsigned" attributten: hvordan tallet opfører sig afhænger af operationskoden.
Generelt giver Binaryen : du opretter et modul, i ham skabe udtryk - unære, binære, blokke fra andre udtryk, kontrolflow osv. Så laver man en funktion med et udtryk som sin krop. Hvis du, ligesom jeg, har en overgangsgraf på lavt niveau, vil relooper-komponenten hjælpe dig. Så vidt jeg forstår, er det muligt at bruge højniveaustyring af udførelsesflowet i en blok, så længe det ikke går ud over blokkens grænser - det vil sige, at det er muligt at lave intern hurtig vej / langsom stiforgrening inde i den indbyggede TLB-cache-behandlingskode, men ikke for at forstyrre det "eksterne" kontrolflow. Når du frigør en relooper, frigøres dens blokke, når du frigør et modul, forsvinder de udtryk, funktioner osv., der er allokeret til det. arena.
Men hvis du vil fortolke kode i farten uden unødvendig oprettelse og sletning af en fortolkerinstans, kan det give mening at lægge denne logik ind i en C++ fil og derfra direkte administrere hele bibliotekets C++ API, uden at klar- lavet indpakninger.
Så for at generere den kode, du har brug for
// настроить глобальные параметры (можно поменять потом)
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 har glemt noget, undskyld, dette er kun for at repræsentere skalaen, og detaljerne er i dokumentationen.
Og nu begynder crack-fex-pex, noget som dette:
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);For på en eller anden måde at forbinde QEMU og JS verdener og samtidig få adgang til de kompilerede funktioner hurtigt, blev der oprettet et array (en tabel med funktioner til import til launcheren), og de genererede funktioner blev placeret der. For hurtigt at beregne indekset blev indekset for nulordsoversættelsesblokken oprindeligt brugt som det, men derefter begyndte indekset beregnet ved hjælp af denne formel simpelthen at passe ind i feltet i struct TranslationBlock.
Af den måde, (p.t. med en mørk licens) fungerer kun fint i Firefox. Chrome-udviklere var på en eller anden måde ikke klar til det faktum, at nogen ville ønske at oprette mere end tusind forekomster af WebAssembly-moduler, så de tildelte simpelthen en gigabyte virtuel adresseplads til hver...
Det er alt for nu. Måske kommer der en anden artikel, hvis nogen er interesseret. Der er nemlig i hvert fald tilbage kun få blokenheder til at fungere. Det kan også være fornuftigt at gøre kompileringen af WebAssembly-moduler asynkron, som det er kutyme i JS-verdenen, da der stadig er en tolk, der kan alt dette, indtil det native modul er klar.
Til sidst en gåde: du har kompileret en binær på en 32-bit arkitektur, men koden, gennem hukommelsesoperationer, klatrer fra Binaryen, et sted på stakken eller et andet sted i de øverste 2 GB af 32-bit adresserummet. Problemet er, at fra Binaryens synspunkt er dette at få adgang til en for stor resulterende adresse. Hvordan kommer man uden om dette?
På admins måde
Jeg endte ikke med at teste dette, men min første tanke var "Hvad nu hvis jeg installerede 32-bit Linux?" Så vil den øverste del af adresserummet blive optaget af kernen. Spørgsmålet er bare, hvor meget der vil blive besat: 1 eller 2 Gb.
På en programmør måde (mulighed for praktikere)
Lad os blæse en boble i toppen af adressefeltet. Jeg forstår ikke selv, hvorfor det virker - der allerede der skal være en stak. Men "vi er praktikere: alt virker for os, men ingen ved hvorfor..."
// 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 er rigtigt, at det ikke er kompatibelt med Valgrind, men heldigvis skubber Valgrind selv meget effektivt alle derfra :)
Måske vil nogen give en bedre forklaring på, hvordan min kode fungerer...
Kilde: www.habr.com