Tempo fa, per divertimento, ho deciso di dimostrare la reversibilità del processo e imparare a generare JavaScript (per essere precisi, Asm.js) a partire dal codice macchina. Per l'esperimento ho scelto QEMU; poco dopo ho scritto un articolo su Habr. Nei commenti mi è stato suggerito di rifare il progetto in WebAssembly, e lasciarlo quasi completato non era proprio quello che volevo... Il lavoro andava avanti, ma molto lentamente, e così, recentemente, è apparso un commento sul tema "E alla fine come è andata?". Alla mia risposta dettagliata ho sentito: "Questo merita un articolo". Beh, se merita, allora ci sarà un articolo. Magari a qualcuno servirà. Da esso il lettore scoprirà alcuni fatti sull'architettura dei backend per la generazione di codice di QEMU, così come come scrivere un compilatore Just-in-Time per un'app web. Poiché avevo già imparato a "modificare" QEMU in JavaScript in modo approssimativo, questa volta ho deciso di fare le cose per bene e non ripetere vecchi errori.
Problemi
Errore numero uno: staccarsi dalla point release
Il mio primo errore è stato quello di staccare la mia versione dalla versione upstream 2.4.1. All'epoca sembrava una buona idea: se esiste una point release, deve essere più stabile della semplice 2.4, tanto più della sua branch.
E poiché pianificavo di aggiungere un numero considerevole di bug miei, quelli degli altri non mi servivano affatto. Probabilmente è andata così. Ma ecco il problema: QEMU non si ferma, e a un certo punto hanno persino annunciato un'ottimizzazione del codice generato di circa il 10%. "Aha, ora lo infilo" pensai, e mi sono bloccato. Qui bisogna fare una digressione: a causa della natura monocore di QEMU.js e del fatto che QEMU originale non prevede l'assenza di multithreading (cioè è critica la possibilità di lavorare simultaneamente su più code path non collegate e non semplicemente "usare tutti i core"), le funzioni principali dei thread hanno dovuto essere "invertite" per consentire chiamate dall'esterno. Questo ha creato alcune problematiche naturali nei merge. Tuttavia, il fatto che parte delle modifiche dalla branch master, da cui stavo cercando di unire il mio codice, fossero state anche cherry picked nella point release (e quindi anche nella mia branch) probabilmente non avrebbe reso le cose più facili. masterIn generale, ho deciso che comunque aveva senso scartare il prototipo, smontarlo e costruire una nuova versione da zero basata su qualcosa di più recente e ora già da
Errore numero due: metodologia TLP master.
Errore numero due: metodologia TLP
In sostanza, non è nemmeno un errore, anzi — è piuttosto una peculiarità nella creazione del progetto in condizioni di totale incomprensione riguardo a «dove e come procedere?» e in generale «ma arriveremo mai?». In queste condizioni programmazione improvvisata è stata una soluzione giustificabile, ma, ovviamente, non si voleva ripeterla senza necessità. Questa volta si voleva fare le cose per bene: commit atomici, cambiamenti del codice consapevoli (e non «stringere caratteri casuali fino a farlo compilare (con avvisi)», come una volta disse Linus Torvalds, se si crede a Wikiquote) e così via.
Errore numero tre: non sapere dove andare e tuffarsi in acqua
Da questo non mi sono ancora liberato completamente, ma ora ho deciso di non seguire la strada del minimo sforzo, e di fare le cose «come si deve», ovvero, scrivere il mio backend TCG da zero, per non dover poi dire, «Sì, è chiaro, è lento, ma non posso controllare tutto — TCI è così scritto...». Inoltre, inizialmente sembrava una soluzione ovvia, visto che genero codice binario. Come si dice, «Ho raccolto Gent, ma non quello giusto»: il codice è certamente binario, ma non è possibile trasferirne il controllo così semplicemente — deve essere esplicitamente inserito nel browser per la compilazione, ricevendo come risultato un certo oggetto dal mondo JS, che deve anche essere salvato da qualche parte. Tuttavia, su architetture RISC normali, per quanto ne so, la situazione tipica è la necessità di ripristinare esplicitamente la cache delle istruzioni per il codice rigenerato — se non è esattamente ciò di cui abbiamo bisogno, è comunque vicino. Inoltre, dalla mia precedente esperienza ho capito che il controllo non viene passato in mezzo al blocco di traduzione, quindi il bytecode, interpretato da qualsiasi offset, non è particolarmente utile e si può semplicemente generare tramite una funzione su TB.aSono arrivato e ho dato un calcio
Anche se ho iniziato a riscrivere il codice già a luglio, il magico stimolo si è presentato all'improvviso: di solito, le e-mail da GitHub arrivano come notifiche sulle risposte a Issues e Pull request, ma qui,
una menzione nel thread improvvisamente Binaryen come backend per qemu Binaryen in qualche modo correggere la licenza in qualche modo modificata (non so: magari cambiare, magari doppia licenza, magari qualcos'altro…). Questo ovviamente mi ha fatto piacere, perché già da un po' di tempo stavo osservando WebAssembly, e mi sentivo un po' triste e confuso. Qui c'era una libreria che inghiottiva sia i blocchi di base con il grafo delle transizioni, sia generava bytecode, e persino lo eseguiva nell'interprete, se necessario.
Poi c'è stata anche nella mailing list di QEMU, ma questo già rientra nella domanda, 'A chi serve realmente?'. E invece, improvvisamente, si è rivelato utile. Almeno, ci si possono inventare alcune opportunità di utilizzo, se funziona più o meno velocemente:
- eseguire qualcosa di formativo senza alcuna installazione
- virtualizzazione su iOS, dove si dice che l'unica applicazione autorizzata alla generazione di codice al volo è il motore JS (è vero?)
- dimostrazione di un mini-SO — monodisco, integrati, vari firmware, ecc…
Caratteristiche dell'ambiente di esecuzione del browser
Come ho già detto, QEMU è legato al multithreading, e nel browser non esiste. Cioè, non che non esista... Inizialmente non c'era affatto, poi sono arrivati i WebWorkers — per quanto ne so, è un multithreading basato sulla trasmissione di messaggi senza variabili condivise. Naturalmente, questo crea notevoli problemi nel porting di codice esistente basato sul modello di memoria condivisa. Poi, sotto la pressione dell'opinione pubblica, è stata implementata anche questa sotto il nome di SharedArrayBuffers. È stata gradualmente introdotta, festeggiata la sua introduzione in vari browser, poi celebrato il nuovo anno, e poi Meltdown… Dopo di che si è giunti alla conclusione che, limiti o non limiti, misurare il tempo con la memoria condivisa e un thread che incrementa il contatore funziona comunque . Così hanno disabilitato il multithreading con memoria condivisa. Sembra che poi l'abbiano riattivato, ma, come si è capito dal primo esperimento, anche senza di essa la vita esiste, e quindi proviamo a farlo senza pianificare il multithreading.
La seconda caratteristica è l'impossibilità di manipolazioni a basso livello dello stack: non si può semplicemente prendere, salvare il contesto attuale e passare a uno nuovo con un nuovo stack. Lo stack delle chiamate è gestito dalla macchina virtuale JS. A prima vista, qual è il problema, dato che abbiamo comunque deciso di gestire i flussi esistenti interamente a mano? Il fatto è che l'input/output a blocchi in QEMU è implementato tramite coroutine, ed è qui che ci servirebbero manipolazioni a basso livello dello stack. Fortunatamente, Emscripten già contiene un meccanismo per operazioni asincrone, addirittura due: e . Il primo funziona tramite un notevole gonfiaggio del codice JavaScript generato e non è più supportato. Il secondo è l'attuale "modo corretto" e funziona tramite la generazione di bytecode per un proprio interprete. Funziona, certo, lentamente, ma non gonfia il codice. Tuttavia, il supporto per le coroutine per questo meccanismo è stato necessario contribuirlo da soli (esistevano già coroutine scritte per Asyncify e c'era un'implementazione approssimativa dello stesso API per Emterpreter, bisognava solo unirle).
Attualmente non ho ancora avuto il tempo di separare il codice in compilabile in WASM e interpretabile tramite Emterpreter, quindi i dispositivi a blocchi non funzionano ancora (vedere nei prossimi episodi, come si suol dire…). Quindi, alla fine dovrebbe risultare una strana entità stratificata come questa:
- input/output a blocchi interpretabile. E che dire, ti aspettavi davvero un NVMe emulato con prestazioni native? 🙂
- codice principale QEMU staticamente compilato (traslittore, altri dispositivi emulati, ecc.)
- codice guest dinamicamente compilato in WASM
Caratteristiche del codice sorgente di QEMU
Come avrai già intuito, il codice di emulazione delle architetture guest e il codice di generazione delle istruzioni macchina host in QEMU sono separati. In realtà, è anche un po' più complicato:
- ci sono architetture guest
- c'è acceleratori, ossia, KVM per la virtualizzazione hardware su Linux (per sistemi guest e host compatibili), TCG per la generazione di codice JIT ovunque. Con QEMU 2.9 è stato introdotto il supporto per lo standard di virtualizzazione hardware HAXM su Windows ()
- se viene utilizzato TCG e non la virtualizzazione hardware, esso ha un supporto specifico per la generazione di codice per ciascuna architettura host, oltre a un interprete universale
- … e attorno a tutto questo – periferiche emulate, interfaccia utente, migrazione, record-replay, ecc.
A proposito, lo sapevate: QEMU può emulare non solo un intero computer, ma anche un processore per un singolo processo utente nel kernel host, cosa che viene sfruttata, ad esempio, da AFL per l' strumentazione di file binari. Forse qualcuno vorrà portare questa modalità di funzionamento di QEMU su JS? 😉
Come la maggior parte dei programmi open-source esistenti da tempo, QEMU si compila attraverso una chiamata configure e make. Supponiamo che tu abbia deciso di aggiungere qualcosa: un backend TCG, un'implementazione dei thread, qualcosa d'altro. Non ti affrettare a gioire/sgomentarti (sottolinea il necessario) all'idea di interagire con Autoconf — in realtà, configure sembra che QEMU sia di fatto scritto a mano e non generato da niente.
WebAssembly
Cos'è quindi WebAssembly (o WASM)? È un sostituto di Asm.js, non più travestito da codice JavaScript valido. Al contrario, è puramente binario e ottimizzato, e persino scrivere un numero intero al suo interno non è affatto semplice: esso viene memorizzato in un formato per compattezza .
Forse avrete sentito parlare dell'algoritmo di relooping per Asm.js: si tratta del recupero delle istruzioni di controllo del flusso di esecuzione 'high-level' (cioè if-then-else, loop, ecc.), per le quali sono ottimizzati i motori JS, da un IR LLVM a basso livello, più vicino al codice macchina eseguito dal processore. Naturalmente, la rappresentazione intermedia di QEMU è più vicina alla seconda. Sembrerebbe che ci sia il bytecode, la fine delle sofferenze... E qui ci sono blocchi, if-then-else e cicli!..
E questa è un'altra ragione per cui Binaryen è utile: può naturalmente accettare blocchi di alto livello, che si avvicinano a ciò che verrà memorizzato in WASM. Ma può anche generare codice da un grafo di blocchi e transizioni tra di essi. Ho già detto cosa nasconde dietro l'API C/C++ di facile utilizzo il formato di memorizzazione di WebAssembly.
TCG (Tiny Code Generator)
TCG un backend per il compilatore C. Poi, evidentemente, non ha retto la concorrenza con GCC, ma alla fine ha trovato il suo posto all'interno di QEMU come meccanismo di generazione di codice per la piattaforma host. C'è anche un backend TCG che genera un certo bytecode astratto, che viene immediatamente eseguito dall'interprete, ma ho deciso di evitarne l'uso questa volta. Tuttavia, il fatto che in QEMU ci sia già la possibilità di attivare il passaggio al TB generato tramite la funzione tcg_qemu_tb_exec, si è rivelato molto utile.
Per aggiungere un nuovo backend TCG in QEMU, è necessario creare una sottodirectory tcg/ (in questo caso, tcg/binaryen), e in essa due file: tcg-target.h e tcg-target.inc.c e tutto questo in configure. Si possono inserire anche altri file, ma, come si può intuire dai nomi di questi due, entrambi verranno inclusi da qualche parte: uno come file header normale (viene incluso in tcg/tcg.h, e quello già in altri file nelle directory tcg, accel e non solo), l'altro solo come code snippet in tcg/tcg.c, ma ha accesso alle sue funzioni statiche.
Decidendo che avrei speso troppo tempo a capire nei dettagli come fosse strutturato, ho semplicemente copiato i "scheletri" di questi due file da un'altra implementazione del backend, specificando onestamente questo nel titolo della licenza.
all'interno di ogni container per impostazione predefinita apparirà così: tcg-target.h contiene prevalentemente impostazioni sotto forma di #define-ov:
- quanti registri e di quale larghezza ci sono nell'architettura di destinazione (per noi - quanti ne vogliamo, la questione è più legata a quello che verrà generato in codice più efficace dal browser su un'architettura "totalmente targetizzata"...)
- l'allineamento delle istruzioni host: su x86, e anche in TCI, le istruzioni non sono allineate, io intendo inserire nel buffer del codice, e non istruzioni vere e proprie, ma puntatori alle strutture della libreria Binaryen, quindi dirò: 4 byte
- quali istruzioni opzionali può generare il backend - includiamo tutto ciò che troviamo in Binaryen, il resto lasciamo che l'acceleratore lo scomponga in istruzioni più semplici.
- quale dimensione approssimativa della cache TLB richiede il backend. Il fatto è che in QEMU tutto è fatto sul serio: sebbene ci siano funzioni di supporto che eseguono il load/store tenendo conto del MMU guest (e come si può fare senza?), la loro cache di traduzione viene mantenuta in una struttura che è comodo integrare direttamente nei blocchi di traduzione. La domanda è quale offset in questa struttura venga elaborato più efficacemente da una piccola e veloce sequenza di comandi
- qui si può anche regolare l'assegnazione di uno o due registri riservati, attivare la chiamata TB tramite funzione e opzionalmente descrivere un paio di piccole
inline-funzioni comeflush_icache_range(ma questo non è il nostro caso)
all'interno di ogni container per impostazione predefinita apparirà così: tcg-target.inc.c, ovviamente, di solito è molto più grande e contiene diverse funzioni obbligatorie:
- inizializzazione, che indica anche i vincoli su quali istruzioni possano lavorare con quali operandi. È stata copiato spudoratamente da un altro backend
- una funzione che riceve un'istruzione di bytecode interno
- qui si possono mettere anche funzioni ausiliarie, oltre a poter sfruttare funzioni statiche da
tcg/tcg.c
Per me ho scelto la seguente strategia: nelle prime parole di ogni blocco di traduzione registravo quattro puntatori: il marcatore di inizio (un certo valore nelle vicinanze di 0xFFFFFFFF, da cui si determinava lo stato attuale del TB), il contesto, il modulo generato e un numero magico per il debug. Inizialmente il marcatore veniva impostato a 0xFFFFFFFF - n, dove n — un piccolo numero positivo, e ad ogni esecuzione tramite l'interprete aumentava di 1. Quando arrivava a 0xFFFFFFFE, avveniva la compilazione, il modulo veniva conservato in una tabella di funzioni, importata in un piccolo "launcher", nel quale avveniva l'esecuzione da tcg_qemu_tb_exec, e il modulo veniva rimosso dalla memoria di QEMU.
Parafrasando un classico, "Una soluzione temporanea, quanto si intreccia questo suono per il cuore del programmatore...". Tuttavia, la memoria si stava dissipando. E questa era memoria gestita da QEMU! Avevo codice che, all'assegnazione di un'istruzione (cioè, di un puntatore), rimuoveva quello a cui si faceva riferimento in quel posto in precedenza, ma questo non aiutava. In effetti, nel caso più semplice QEMU alloca memoria all'avvio e scrive lì il codice generato. Quando il buffer finisce, il codice viene eliminato e al suo posto inizia a essere scritto il successivo.
Dopo aver esaminato il codice, ho capito che il workaround con il numero magico permetteva di evitare un crash durante la distruzione dell'heap, liberando qualcosa di errato su un buffer non inizializzato al primo passaggio. Ma chi scrive di nuovo il buffer aggirando la mia funzione poi? Come suggerito dagli sviluppatori di Emscripten, di fronte al problema, ho portato il codice risultante di nuovo in un'applicazione nativa, e l'ho testato con Mozilla Record-Replay… In sintesi, alla fine ho capito una cosa semplice: per ogni blocco viene allocato struct TranslationBlock con la sua descrizione. Indovinate dove… Esatto, direttamente prima del blocco nel buffer. Realizzando ciò, ho deciso di chiudere con i workaround (almeno alcuni), e ho semplicemente eliminato il numero magico, trasferendo le parole rimanenti in struct TranslationBlock, creando una lista collegata che permette di scorrere rapidamente durante il reset della cache di traduzione e liberare la memoria.
Alcuni workaround sono rimasti: ad esempio, i puntatori contrassegnati nel buffer di codice — parte di essi sono semplicemente BinaryenExpressionRef, cioè fanno riferimento a espressioni che devono essere collocate linearmente nel blocco base generato, parte — condizione di transizione tra i blocchi, parte — dove andare. Ci sono anche blocchi già preparati per il Relooper, che devono essere collegati in base a condizioni. Per distinguerli, si presume che siano tutti allineati almeno a quattro byte, quindi si possono utilizzare tranquillamente i due bit inferiori come etichetta, basta non dimenticare di rimuoverla quando necessario. A proposito, tali etichette sono già utilizzate in QEMU per indicare il motivo dell'uscita dal ciclo TCG.
Uso di Binaryen
I moduli in WebAssembly contengono funzioni, ciascuna delle quali ha un corpo che rappresenta un'espressione. Le espressioni sono operazioni unarie e binarie, blocchi composti da elenchi di altre espressioni, flusso di controllo, ecc. Come ho già detto, il flusso di controllo qui è organizzato come ramificazioni ad alto livello, cicli, chiamate di funzioni, ecc. Gli argomenti vengono passati alle funzioni non nello stack, ma esplicitamente, come in JS. Ci sono anche variabili globali, ma non le ho usate, quindi non ne parlerò.
Le funzioni hanno anche variabili locali numerate a partire da zero, di tipo: int32 / int64 / float / double. Inoltre, le prime n variabili locali sono gli argomenti passati alla funzione. Si noti che, anche se qui tutto ciò non è del tutto a basso livello in termini di controllo del flusso, i numeri interi non portano con sé il segno "positivo/negativo": il comportamento di un numero dipende dal codice dell'operazione.
In generale, Binaryen fornisce : si crea un modulo, in cui si creano espressioni: unarie, binarie, blocchi di altre espressioni, flusso di controllo, ecc. Poi si crea una funzione, il cui corpo deve essere un'espressione. Se anche voi, come me, avete un grafo di transizioni a basso livello, vi aiuterà il componente relooper. A quanto capisco, è possibile utilizzare un controllo del flusso di esecuzione di alto livello in un blocco fintanto che non esce dai limiti del blocco: in altre parole, è possibile eseguire un ramificazione interna fast path / slow path all'interno del codice incorporato che gestisce la cache TLB, ma non intervenire nel flusso di controllo "esterna". Quando si libera il relooper, si liberano i suoi blocchi; quando si libera il modulo, scompaiono le espressioni, le funzioni, ecc., allocate nella sua arena..
Tuttavia, se desiderate interpretare il codice al volo senza creare e distruggere un'istanza dell'interprete, potrebbe avere senso spostare questa logica in un file C++, e gestire direttamente tutto l'API C++ della libreria, bypassando le interfacce preconfezionate.
Pertanto, per generare codice, è necessario
// настроить глобальные параметры (можно поменять потом)
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);… se ho dimenticato qualcosa, scusate, è solo per illustrare le proporzioni, mentre i dettagli si trovano nella documentazione.
E ora inizia il krak-feks-peks, più o meno così:
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,
// ...
}
);
// e ora avete l'istanza!
}, buf, sz);Per collegare in qualche modo il mondo di QEMU e JS e per accedere rapidamente alle funzioni compilate, è stato creato un array (tabella delle funzioni da importare nel launcher), dove venivano inserite le funzioni generate. Per calcolare rapidamente l'indice, inizialmente si usava l'indice della parola zero del translation block, ma poi l'indice calcolato secondo questa formula è diventato semplicemente da inserire nel campo in struct TranslationBlock.
A proposito, (per ora con una licenza poco chiara) funziona correttamente solo su Firefox. Gli sviluppatori di Chrome erano in qualche modo non pronti a che qualcuno volesse creare più di mille istanze di moduli WebAssembly, quindi allocavano semplicemente un gigabyte di spazio di indirizzamento virtuale per ognuno...
Per ora è tutto. Potrebbe esserci un altro articolo, se a qualcuno interessa. In particolare, resta almeno solo far funzionare i dispositivi a blocchi. Potrebbe avere senso implementare anche la compilazione dei moduli WebAssembly in modo asincrono, come è consueto nel mondo JS, dal momento che c'è comunque un interprete che può eseguire tutto, finché il modulo nativo non è pronto.
Infine, una sfida: hai compilato il binario su un'architettura a 32 bit, ma il codice tramite operazioni di memoria accede a Binaryen, da qualche parte nello stack o in qualche altro posto nei 2 GB superiori dello spazio indirizzabile a 32 bit. Il problema è che, dal punto di vista di Binaryen, questo accesso avviene a un indirizzo risultante troppo grande. Come aggirarlo?
Dal punto di vista dell'amministratore
Non l'ho testato alla fine, ma il primo pensiero è stato «E se installassi un Linux a 32 bit?» Allora la parte superiore dello spazio indirizzabile sarà occupata dal kernel. La domanda è solo quanto sarà occupata: 1 o 2 Gb.
Dal punto di vista del programmatore (opzione per i praticanti)
Creiamo una bolla nella parte superiore dello spazio indirizzabile. Non capisco perché funzioni — lì dovrebbe esserci ha già lo stack. Ma «noi praticanti: tutto funziona, ma nessuno sa perché…».
// 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));
}… non è compatibile con Valgrind, ma per fortuna Valgrind stesso espelle molto efficacemente tutti da lì 🙂
Forse qualcuno potrà fornire una spiegazione migliore su come funziona questo mio codice…
Fonte: habr.com
