Cu mult timp în urmă, am decis, pentru distracție, să demonstrez reversibilitatea procesului și să învăț să genereze JavaScript (mai exact, Asm.js) din codul mașinii. Pentru experiment, am ales QEMU, iar după o vreme, am scris un articol pe Habr. În comentarii, cineva m-a sfătuit să reproiectez aplicația pe WebAssembly, dar să renunț la un proiect aproape finalizat nu era deloc plăcut... Munca continua, dar mergea foarte încet, și recent în acel articol a apărut întrebarea „Și cum a fost totul?” La răspunsul meu detaliat, am primit „Asta merită un articol”. Așa că, dacă merită, va fi un articol. Poate va fi de folos cuiva. Din el, cititorul va afla câteva fapte despre arhitectura backend-ului pentru generarea de coduri QEMU, precum și cum să scrie un compilator Just-in-Time pentru aplicații web.
Sarcini
Deoarece am învățat deja să portez QEMU pe JavaScript într-un mod „cumpărat”, de data aceasta am decis să fac lucrurile cum trebuie și să nu repet greșelile anterioare.
Greșeala numărul unu: a mă abate de la versiunea point release
Prima mea greșeală a fost să îmi ramific versiunea de la versiunea upstream 2.4.1. Atunci părea o idee bună: dacă există o versiune point release, înseamnă că, probabil, este mai stabilă decât versiunea simplă 2.4, cu atât mai mult decât ramura master. Și cum plănuiam să adaug un număr considerabil de erori proprii, erorile străine nu îmi erau necesare. Așa a fost, probabil. Dar iată neplăcerea: QEMU nu stă pe loc, iar la un moment dat au și anunțat o optimizare a codului generat cu aproximativ 10%. „Ah, îl voi integra imediat” am gândit și m-am descurajat. Aici trebuie să fac o pauză: datorită caracterului monoplu al QEMU.js și faptului că QEMU original nu presupune lipsa multiprocesării (adică pentru el este critică posibilitatea de a avea mai multe căi de cod nelegate în același timp, nu doar „să folosesc toate nucleele”), funcțiile principale ale thread-urilor au trebuit „extrase” pentru a putea fi apelate din exterior. Aceasta a creat probleme naturale în procesul de fuziune. Totuși, faptul că o parte din modificările din ramura master, din care am încercat să îmbin codul meu, au fost de asemenea cherry picked în versiunile point release (așa că, și în ramura mea) probabil nu a ajutat la confort.
În general, am decis că oricum prototipul merită să fie distrus și să construiesc o nouă versiune de la zero pe baza a ceva mai recent și acum din master.
Greșeala numărul doi: metodologia TLP
Practic vorbind, aceasta nu este o eroare, de fapt — ci doar o caracteristică a creării proiectului în condiții de neînțelegere totală atât a "unde și cum să ne îndreptăm?", cât și în general "vom ajunge oare?". În aceste condiții, programarea pe genunchi a fost o opțiune justificată, dar, desigur, nu îmi doream să repet asta fără necesitate. De data aceasta, voiam să fac lucrurile cum trebuie: angajamente atomice, modificări conștiente ale codului (nu "strângerea de caractere aleatorii până când compilarea reușește (cu avertismente)", cum a spus cineva despre altcineva odată Linus Torvalds, dacă e să credem Wikiquote) etc.
Eroarea numărul trei: a intra în apă fără a cunoaște adâncimea
De aceea, acum nu am scăpat complet de acest lucru, dar am decis să nu mai urmez calea cea mai ușoară, și să fac lucrurile "ca un profesionist", adică, să scriu backend-ul meu TCG de la zero, pentru a nu mai spune că "Da, desigur, e lent, dar nu pot controla totul – așa a fost scris TCI...". În plus, inițial părea o soluție evidentă, deoarece eu generează cod binar. Așa cum se spune, "Am adunat Gentu, dar nu pe cel corect": codul este, desigur, binar, dar nu poți să-i transferezi controlul așa, trebuie să fie introdus în mod explicit în browser pentru compilare, rezultând un obiect din lumea JS, care trebuie să fie salvat undeva. Cu toate acestea, pe arhitecturi RISC normale, cât înțeleg, o situație tipică este necesitatea de a reseta explicit cache-ul instrucțiunilor pentru codul re-generate – dacă asta nu este ceea ce ne dorim, atunci, cu siguranță, este aproape. În plus, din încercarea mea anterioară, am învățat că controlul nu se transferă în mijlocul unui bloc de translație, așa că bytecode-ul, interpretat de orice offset, nu ne este deosebit de necesar și putem genera pur și simplu funcții pe TB.
Am venit și am dat o lovitură
Deși am început să rescriu codul încă din iulie, impulsul magic s-a strecurat neobservat: în general, e-mailurile de la GitHub vin ca notificări pentru răspunsuri la Issues și Pull requests, iar acum, brusc menționarea într-un fir în contextul, "Uite, el a făcut ceva similar, poate va spune ceva". Vorbea despre utilizarea unei biblioteci înrudiți cu Emscripten pentru crearea WASM JIT. Așa că am spus că aveți licența Apache 2.0, iar QEMU ca un întreg este distribuit sub GPLv2, și nu sunt foarte compatibile. Dintr-o dată, s-a dovedit că licența poate fi modificată în vreun fel (nu știu: poate, să schimb, poate, licențiere dublă, poate, altceva…). M-a bucurat, desigur, pentru că mă uitam la WebAssembly, și mi se părea trist și neclar. Aici era o bibliotecă care va consuma atât blocurile de bază cu grafurile de tranziție, cât și va genera bytecode, și chiar îl va rula în interpret, dacă este necesar.
Apoi a mai fost pe lista de discuții QEMU, dar asta mai degrabă răspunde la întrebarea, „Cui îi pasă de ea?” Și totuși, brusc, s-a dovedit că este necesară. Cel puțin, se pot aduna astfel de oportunități de utilizare, dacă va funcționa mai mult sau mai puțin rapid:
- rularea a ceva educativ fără nicio instalare
- virtualizare pe iOS, unde se știe că singura aplicație care are dreptul la generarea de cod dinamic este motorul JS (dar este adevărat?)
- demonstrarea unui mini-OS - dischete simple, integrate, diferite firmware-uri, etc...
Particularitățile mediului de execuție în browser
Așa cum am menționat, QEMU este legat de multithreading, iar în browser nu există. Adică, din păcate... La început nu era deloc, apoi au apărut WebWorkers - din câte înțeleg, acesta este un tip de multithreading bazat pe transferul de mesaje fără variabile partajate. Evident, acest lucru creează probleme semnificative la portarea codului existent bazat pe modelul de memorie partajată. Apoi, sub presiunea opiniei publice, aceasta a fost implementată și a fost denumită SharedArrayBuffers. A fost introdusă treptat, sărbătorind lansarea sa în diferite browsere, apoi sărbătorind noul an, iar apoi Meltdown... După care s-a ajuns la concluzia că, indiferent de modul în care măsurăm timpul, cu ajutorul memoriei partajate și al unui thread care incrementează un contor, totuși . Așa că s-a dezactivat multithreadingul cu memorie partajată. Se pare că au reactivat-o ulterior, dar, după cum s-a făcut clar din primul experiment, și fără ea există viață, așa că hai să încercăm să facem fără a ne baza pe multithreading.
A doua caracteristică constă în imposibilitatea manipulărilor de nivel inferior cu stiva: nu poți pur și simplu să salvezi contextul curent și să comuți pe unul nou cu o nouă stivă. Stiva de apeluri este gestionată de mașina virtuală JS. Ar părea că nu este nicio problemă, având în vedere că am decis să gestionăm fluxurile anterioare complet manual? Problema este că intrarea/ieșirea blocantă în QEMU este implementată prin corutine, iar aici ar fi fost utile manipulările scăzute ale stivei. Din fericire, Emscripten conține deja un mecanism pentru operațiile asincrone, chiar două: și . Primul funcționează printr-o creștere semnificativă a codului JavaScript generat și nu mai este susținut. Al doilea este „modul corect” curent și funcționează prin generarea de bytecode pentru propriul interpret. Funcționează, desigur, încet, dar nu umflă codul. Adevărul este că suportul pentru corutine pentru acest mecanism a trebuit să fie contribuit de mine (acolo existau deja corutine scrise pentru Asyncify și o implementare aproximativă a aceluiași API pentru Emterpreter, doar trebuia să le conectez).
Până în prezent, nu am reușit să separ codul în cel compilabil în WASM și cel interpretat prin Emterpreter, așa că dispozitivele blocante încă nu funcționează (rămâneți pe recepție pentru următoarele episoade, cum se zice…). Deci, în final ar trebui să obținem un așa-zis stratificat amestec:
- intrare/ieșire blocantă interpretată. Dar ce, chiar te-așteptai la un NVMe emulat cu performanță nativă? 🙂
- codul principal QEMU compilat static (translater, celelalte dispozitive emulate etc.)
- codul oaspeților compilat dinamic în WASM
Particularitățile surselor QEMU
Așa cum probabil ați ghicit deja, codul de emulare a arhitecturilor oaspeților și codul de generare a instrucțiunilor mașinii gazdă în QEMU sunt separate. De fapt, acolo este chiar puțin mai complicat:
- există arhitecturi oaspete
- are acceleratoare, și anume, KVM pentru virtualizarea hardware pe Linux (pentru sisteme oaspete și gazde compatibile), TCG pentru generarea JIT de cod oriunde. Începând cu QEMU 2.9, a fost introdus suportul pentru standardul de virtualizare hardware HAXM pe Windows ()
- dacă se folosește TCG, nu virtualizare hardware, atunci are suport separat pentru generarea de cod pentru fiecare arhitectură de gazdă, precum și pentru interpretatorul universal
- … iar în jurul tuturor acestor lucruri — periferice emulate, interfața utilizatorului, migrarea, record-replay etc.
Apropo, știați că: QEMU poate emula nu doar un întreg computer, ci și un procesor pentru un anumit proces utilizator în nucleul gazdă, lucru folosit, de exemplu, de fuzzerele AFL pentru instrumentarea binarelor. Poate că cineva ar dori să portareze acest mod de funcționare al QEMU pe JS? 😉
Ca și cele mai multe programe libere existente de mult timp, QEMU se compilează printr-un apel configure și make. Presupunând că ați decis să adăugați ceva: backend TCG, implementarea firelor, ceva în plus. Nu vă grăbiți să vă bucurați/să vă speriați (subiectul necesar) de perspectiva de a comunica cu Autoconf — de fapt, configure QEMU, de fapt, are un generator personalizat și nu este generat din nimic.
WebAssembly
Atunci, ce este WebAssembly (cunoscut și ca WASM)? Este o înlocuire pentru Asm.js, care acum nu mai pretinde a fi un cod JavaScript valid. Dimpotrivă, este strict binar și optimizat și chiar și simpla scriere a unui întreg număr în el nu este foarte simplă: este stocat într-un format .
Poate ați auzit despre algoritmul de reluare pentru Asm.js — este recuperarea instrucțiunilor de control al fluxului de execuție `high-level` (adică if-then-else, bucle etc.), pentru care sunt optimizate motoarele JS, din IR LLVM de nivel inferior, mai aproape de codul mașină executat de procesor. Evident, reprezentarea intermediară QEMU este mai aproape de a doua. Ar părea că iată-l, bytecode, sfârșitul chinurilor… Și aici blocuri, if-then-else și bucle!..
Și în aceasta constă un alt motiv pentru care Binaryen este util: el poate accepta, desigur, blocuri de nivel înalt, apropiate de ceea ce va fi salvat în WASM. Dar poate, de asemenea, să emită cod din graficele blocurilor fundamentale și tranzițiilor între ele. De asemenea, am menționat că ascunde un format convenabil de stocare a WebAssembly prin API C/C++.
TCG (Tiny Code Generator)
TCG un backend pentru compilatorul C. Apoi, se pare că nu a rezistat competiției cu GCC, dar în cele din urmă și-a găsit locul în cadrul QEMU ca mecanism de generare a codului pentru platforma gazdă. De asemenea, există și un backend TCG, care generează un cod binar abstract ce este imediat executat de un interpret, dar am decis să evit utilizarea acestuia de data aceasta. Totuși, faptul că QEMU are deja posibilitatea de a comuta la TB generat prin funcția tcg_qemu_tb_exec, s-a dovedit foarte util pentru mine.
Pentru a adăuga un nou backend TCG în QEMU, trebuie să creezi un subdirector tcg/ (în acest caz, tcg/binaryen), iar în acesta două fișiere: tcg-target.h și tcg-target.inc.c și toate acestea în configure. Poți pune acolo și alte fișiere, dar, așa cum se poate deduce din numele celor două, ambele vor fi incluse undeva: unul ca un fișier header obișnuit (este inclus în tcg/tcg.h, iar celălalt în alte fișiere din directoarele tcg, accel și nu numai), celălalt - doar ca un snippet de cod în tcg/tcg.c, dar are acces la funcțiile sale statice.
Decizând că voi petrece prea mult timp pe detaliile modului în care este structurat, am copiat pur și simplu „scheletele” acestor două fișiere dintr-o altă implementare a backend-ului, menționând corect acest lucru în antetul licenței.
Fișier tcg-target.h cuprinde predominant configurații sub formă de #define-uri:
- câte registre și ce lățime au pe arhitectura țintă (la noi - câte vrem, atâtea sunt - întrebarea este mai degrabă ce va genera cod eficient browser-ul pe o arhitectură „total țintită”...)
- alinierea instrucțiunilor gazdă: pe x86, și în TCI, instrucțiunile nu sunt practic aliniate, eu intenționez să stochez în buffer codul și nu instrucțiuni deloc, ci pointeri la structurile bibliotecii Binaryen, așa că voi spune: 4 bytes
- ce instrucțiuni opționale poate genera backend-ul - includem tot ce găsim în Binaryen, restul să fie descompus de accelerator în instrucțiuni mai simple.
- care este dimensiunea aproximativă a cache-ului TLB solicitat de backend. Problema este că în QEMU totul este foarte serioz: deși există funcții de asistență care efectuează load/store având în vedere MMU-ul guest (și unde fără el?), însă cache-ul de traducere este păstrat sub formă de structură, a cărei procesare este convenabil de integrat direct în blocurile de traducere. Întrebarea este care offset din această structură este procesat cel mai eficient printr-o succesiune mică și rapidă de instrucțiuni.
- aici se poate ajusta destinația unuia sau două registre rezervate, se poate activa apelul TB printr-o funcție și opțional se pot descrie câteva detalii minore.
inline- funcții de genulflush_icache_range(dar aceasta nu este situația noastră)
Fișier tcg-target.inc.c, desigur, este de obicei mult mai mare ca dimensiune și conține câteva funcții obligatorii:
- inițializare, care indică, printre altele, restricțiile asupra instrucțiunii ce poate lucra cu anumite operanzi. A fost copiat blatant de mine din alt backend.
- funcția care primește o instrucțiune de bytecode intern
- aici pot fi incluse funcții auxiliare, de asemenea, pot fi utilizate funcții statice din
tcg/tcg.c
Pentru mine, am ales următoarea strategie: în primele cuvinte ale blocului curent de traducere, am înregistrat patru pointeri: eticheta de început (o anumită valoare în jurul 0xFFFFFFFF, din care era determinat starea curentă a TB), contextul, modul generat și un număr magic pentru depanare. La început, eticheta era setată la 0xFFFFFFFF - n, unde n — un număr pozitiv mic, și la fiecare execuție prin interpretator creștea cu 1. Când ajungea la 0xFFFFFFFE, avea loc compilarea, modul era salvat în tabelul funcțiilor, importat într-un mic „launcher”, din care respectiva execuție ieșea tcg_qemu_tb_exec, iar modul era eliminat din memoria QEMU.
Parafrazând un clasic, „Cârtița, ce mult s-a împletit în acest sunet pentru inima programatorului…”. Cu toate acestea, memoria se evaporase undeva. Și era vorba de memoria gestionată de QEMU! Aveam un cod care, la scrierea unei noi instrucțiuni (adică, pointerului), elimina pe cea la care se făcea referire pe acest loc anterior, dar acest lucru nu ajuta. De fapt, în cazul cel mai simplu, QEMU alocă memorie la start și scrie acolo codul generat. Când bufferul se termină, codul este eliminat, și următorul începe să fie scris în locul său.
După ce am studiat codul, am realizat că soluția cu numărul magic permitea să nu se șteargă heap-ul atunci când se elibera ceva greșit pe un buffer neinițializat în prima trecere. Dar cine modifică buffer-ul în afara funcției mele ulterior? Așa cum sugerează dezvoltatorii Emscripten, confruntându-mă cu problema, am portat codul rezultat înapoi la o aplicație nativă și am folosit Mozilla Record-Replay... În general, la final, am înțeles un lucru simplu: pentru fiecare bloc se alocă struct TranslationBlock cu descrierea sa. Ghiciți unde... Corect, chiar înainte de blocul din buffer. Realizând asta, am decis să renunț la soluțiile temporare (cel puțin la unele), și pur și simplu am eliminat numărul magic, iar cuvintele rămase le-am mutat în struct TranslationBlock, creând o listă simplu înlănțuită, prin care se poate trece rapid atunci când se resetează cache-ul de traducere, eliberând astfel memorie.
Unii sprijini temporari au rămas: de exemplu, pointerele marcate din buffer-ul de cod — parte din ele sunt doar BinaryenExpressionRef, adică ele se referă la expresiile care trebuie plasate linear în blocul de bază generat, parte — condiția de tranziție între blocurile de bază, parte — destinația tranziției. De asemenea, există blocuri pregătite pentru Relooper, care trebuie conectate în funcție de condiții. Pentru a le distinge, se folosește presupunerea că toate sunt aliniate cel puțin pe patru octeți, iar astfel se pot folosi liniștit ultimele două biți pentru etichete, fiind important să nu se uite să fie eliminate atunci când este necesar. Apropo, astfel de etichete sunt deja utilizate în QEMU pentru a indica motivul ieșirii din bucla TCG.
Utilizarea Binaryen
Modulele din WebAssembly conțin funcții, fiecare conținând un corp ce reprezintă o expresie. Expresiile sunt operații unare și binare, blocuri formate din liste de alte expresii, controlul fluxului etc. Așa cum am spus deja, controlul fluxului este organizat exact ca ramificări de nivel înalt, bucle, apeluri de funcții etc. Argumentele funcțiilor sunt transmise nu pe stivă, ci explicit, la fel ca în JS. Există și variabile globale, dar eu nu le-am folosit, așa că nu voi vorbi despre ele.
Funcțiile au variabile locale numerotate de la zero, având tipul: int32 / int64 / float / double. Primele n variabile locale sunt argumentele transmise funcției. Rețineți că, deși aici nu este complet la un nivel foarte scăzut în ceea ce privește fluxul de control, numerele întregi nu conțin un indiciu de „semnificat/nesemnificat”: comportamentul unui număr depinde de codul de operație.
În general, Binaryen oferă : creați un modul, în care creați expresii — unare, binare, blocuri din alte expresii, flux de control etc. Apoi creați o funcție, al cărei corp trebuie să fie o expresie. Dacă aveți, ca și mine, un grafic de tranziție de nivel scăzut - componenta relooper vă va ajuta. Din câte înțeleg, utilizarea controlului de flux de nivel înalt într-un bloc este posibilă atâta timp cât nu depășește limitele blocului — adică se poate face ramificarea internă fast path / slow path în codul încorporat de gestionare a memoriei TLB, dar nu se poate interveni în fluxul de control „extern”. Când eliberați relooperul, blocurile sale sunt eliberate, iar când eliberați modulul - expresiile, funcțiile etc. alocate în arena sa.
Totuși, dacă doriți să interpretați codul în timp real fără a crea și distruge excesiv instanțe ale interpretatorului, ar putea avea sens să extrageți această logică într-un fișier C++ și să gestionați direct întregul API C++ al bibliotecii, evitând wrapper-urile gata făcute.
Astfel, pentru a genera cod, trebuie
// настроить глобальные параметры (можно поменять потом)
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);… dacă am uitat ceva - îmi pare rău, asta este doar pentru a aprecia dimensiunile, iar detaliile - sunt în documentație.
Și acum începe crux-fex-pex, cam așa:
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,
// ...
}
);
// și iată că aveți deja instanța!
}, buf, sz);Pentru a lega cumva lumea QEMU de JS și pentru a accesa rapid funcțiile compilate, a fost creat un array (tabel de funcții pentru import în launcher), în care au fost plasate funcțiile generate. Pentru a calcula rapid indicele, inițial s-a folosit indicele cuvântului zero din blocul de traducere, dar apoi indicele, calculat conform unei formule, a fost pur și simplu înregistrat în câmpul în struct TranslationBlock.
Apropo, (deocamdată cu o licență neclară) funcționează corect doar în Firefox. Dezvoltatorii Chrome au fost cumva nepregătiți pentru faptul că cineva ar dori să creeze mai mult de o mie de instanțe de module WebAssembly, așa că au alocat pur și simplu câte un gigabyte de spațiu adresabil virtual pe fiecare…
Deocamdată, aceasta este tot. Poate va mai fi un articol, dacă pe cineva interesează. Aici rămâne de făcut cel puțin doar să facem să funcționeze dispozitivele bloc. Poate ar fi de sens să facem, de asemenea, compilarea modulelor WebAssembly asincronă, așa cum este obișnuit în lumea JS, având în vedere că există deja un interpretator care poate executa totul în timp ce modul nativ nu este pregătit.
În cele din urmă, o ghicitoare: ai compilat un binar pe o arhitectură de 32 de biți, dar codul prin operațiile cu memoria ajunge din Binaryen, undeva pe stivă sau în alte 2 GB superioare ale spațiului adresabil de 32 de biți. Problema este că, din perspectiva Binaryen, această accesare este la o adresă rezultat prea mare. Cum poți ocoli asta?
Din perspectiva de administrator
Eu, în cele din urmă, nu am testat asta, dar prima mea idee a fost „Ce ar fi dacă am pune un Linux de 32 de biți?” Atunci partea superioară a spațiului adresabil va fi ocupată de kernel. Întrebarea este doar câte va fi ocupat: 1 sau 2 GB.
Din perspectiva de programator (varianta pentru practicieni)
Vom umfla un bule în partea superioară a spațiului adresabil. Nici eu nu înțeleg de ce funcționează - acolo ar trebui să fie este deja stiva. Dar „noi suntem practicieni: la noi totul funcționează, dar nimeni nu știe de ce…”.
// 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));
}… incompatibil cu Valgrind, dar, din fericire, Valgrind în mod foarte eficient îi elimină pe toți de acolo 🙂
Poate cineva va oferi o explicație mai bună despre cum funcționează acest cod al meu…
Sursa: habr.com
