QEMU.js: jetzt ernsthaft und mit WASM

Vor langer Zeit entschied ich mich zum Spaß, die Umkehrbarkeit des Prozesses zu beweisen und zu lernen, JavaScript (genauer gesagt, Asm.js) aus Maschinencode zu generieren. Für das Experiment wurde QEMU ausgewählt, und einige Zeit später schrieb ich einen Artikel auf Habr. In den Kommentaren wurde mir geraten, das Projekt auf WebAssembly umzustellen, und selbst aufzugeben, das fast abgeschlossene Projekt wollte ich irgendwie nicht aufgeben... Die Arbeit ging voran, aber sehr langsam, und kürzlich erschien unter dem Artikel die Frage Kommentar zum Thema „Wie ist alles ausgegangen?“. Auf meine ausführliche Antwort hörte ich: „Das könnte einen Artikel füllen“. Nun, wenn es so ist, wird es also einen Artikel geben. Vielleicht ist es für jemanden nützlich. Der Leser wird einige Fakten über die Struktur der Backend-Codegenerierung von QEMU erfahren sowie darüber, wie man einen Just-in-Time-Compiler für eine Webanwendung schreibt.

Aufgaben

Da ich gelernt hatte, QEMU irgendwie nach JavaScript zu portieren, wurde diesmal beschlossen, es vernünftig zu machen und alte Fehler nicht zu wiederholen.

Fehler Nummer eins: von der Point-Release abzweigen

Mein erster Fehler war, meine Version von der Upstream-Version 2.4.1 abzuzweigen. Das schien mir damals eine gute Idee: wenn ein Point-Release existiert, ist es wahrscheinlich stabiler als das einfachere 2.4, geschweige denn der Branch master. Da ich plante, eine beträchtliche Anzahl von eigenen Fehlern hinzuzufügen, waren mir die fremden einfach völlig egal. So kam es wahrscheinlich auch. Aber hier ist das Problem: QEMU bleibt nicht stehen, und irgendwann wurde sogar eine Optimierung des generierten Codes um 10 % angekündigt. „Aha, jetzt mache ich es rein“, dachte ich und scheiterte. An dieser Stelle muss ich eine Bemerkung machen: Aufgrund des einsträngigen Charakters von QEMU.js und der Tatsache, dass das ursprüngliche QEMU keine Abwesenheit von Multithreading vorsieht (d.h. für es ist die Möglichkeit des gleichzeitigen Betriebs mehrerer unverbundener Codepfade wichtig, nicht einfach „alle Kerne zu nutzen“), mussten die Hauptfunktionen der Threads „umgedreht“ werden, um einen externen Aufruf zu ermöglichen. Das führte zu einigen natürlichen Problemen beim Zusammenführen. Allerdings würde die Tatsache, dass einige Änderungen aus dem Branch master, mit dem ich versuchte, meinen Code zusammenzuführen, ebenfalls in das Point-Release „cherry-picked“ wurden (und somit auch in meinen Branch), auch wahrscheinlich nicht zu einer Erleichterung beigetragen haben.

Insgesamt entschied ich, dass es trotzdem sinnvoll ist, den Prototypen zu verwerfen, ihn in Einzelteile zu zerlegen und eine neue Version von Grund auf auf der Basis von etwas Neuem zu erstellen und jetzt mit master.

Fehler Nummer zwei: TPL-Methodologie

Im Grunde genommen ist das nicht einmal ein Fehler, sondern eher eine Besonderheit bei der Erstellung des Projekts unter Bedingungen vollständiger Unkenntnis darüber, „wohin und wie es gehen soll?“ sowie „werden wir das überhaupt erreichen?“. Unter diesen Bedingungen Flickwerk-Programmierung war eine gerechtfertigte Option, aber natürlich wollte ich das nicht ohne Not wiederholen. Diesmal wollte ich es richtig machen: atomare Commits, bewusste Codeänderungen (und nicht „Zufällige Zeichenfolgen zusammenstellen, bis es kompiliert (mit Warnungen)“, wie Linus Torvalds einmal über jemanden gesagt hat, wenn man den Wiki-Zitat-Quellen glauben kann), usw.

Fehler Nummer drei: Nicht wissen, wo man hineingeht, aber trotzdem ins Wasser springen

Davon bin ich bis jetzt nicht ganz losgekommen, aber jetzt habe ich beschlossen, nicht den Weg des geringsten Widerstands zu gehen und es „wie ein Erwachsener“ zu machen, nämlich meinen eigenen TCG-Backend von Grund auf neu zu schreiben, damit ich später nicht sagen kann: „Ja, es ist natürlich langsam, aber ich kann ja nicht alles kontrollieren – so ist TCI geschrieben ...“. Außerdem schien mir das von Anfang an eine offensichtliche Lösung zu sein, da ich ja Binärcode generiere. Wie das Sprichwort sagt: „Ich sammelte Gent,arbeiten, aber nicht das Richtige“: Der Code ist zwar binär, aber die Steuerung kann nicht einfach so übertragen werden – man muss sie ausdrücklich im Browser zur Kompilierung einfügen und erhält als Ergebnis ein Objekt aus der Welt von JS, das irgendwo gespeichert werden muss. Jedenfalls ist es, soweit ich verstehe, auf normalen RISC-Architekturen eine typische Situation, dass man den Instruktionscache für den regenerierten Code explizit zurücksetzen muss – wenn das nicht genau das ist, was wir brauchen, ist es jedenfalls nahe dran. Außerdem habe ich aus meinem letzten Versuch gelernt, dass die Steuerung mitten im Translationsblock irgendwie nicht übergeben wird, daher brauchen wir den Bytecode, der von jeder Offset-Position interpretiert wird, nicht besonders, und man kann einfach eine Funktion auf dem TB generieren.

Sie kamen und traten hinein

Obwohl ich mit dem Umschreiben des Codes bereits im Juli begonnen hatte, schlich sich der magische Tritt unbemerkt ein: Normalerweise kommen die E-Mails von GitHub als Benachrichtigungen zu Antworten auf Probleme und Pull-Anfragen, und hier, plötzlich eine Erwähnung im Thread Binaryen als ein QEMU-Backend im Kontext: „Er hat etwas Ähnliches gemacht, vielleicht sagt er etwas dazu“. Es ging um die Verwendung einer verwandten Bibliothek von Emscripten, Binaryen zur Erstellung von WASM JIT. Nun, ich sagte, dass ihr dort die Lizenz Apache 2.0 habt, während QEMU als Ganzes unter GPLv2 vertrieben wird, und dass diese beiden nicht wirklich kompatibel sind. Plötzlich stellte sich heraus, dass man die Lizenz irgendwie anpassen kann (ich weiß nicht: vielleicht ändern, vielleicht doppelte Lizenzierung, vielleicht etwas anderes…). Das hat mich natürlich gefreut, denn ich hatte mir schon mehrere Male bis zu diesem Zeitpunkt angesehen, das binäre Format WebAssembly, und ich fand es irgendwie traurig und unverständlich. Hier gab es jedoch eine Bibliothek, die sowohl die grundlegenden Blöcke mit dem Übergangsgraphen verarbeiten als auch Bytecode ausgeben konnte und sogar, wenn nötig, ihn im Interpreter ausführen würde.

Später gab es noch eine E-Mail in der QEMU-Mailingliste, aber das war schon eher die Frage: „Braucht das überhaupt jemand?“ Und es stellte sich heraus, plötzlich, dass es gebraucht wurde. Mindestens kann man solche Anwendungsfälle sammeln, wenn es mehr oder weniger schnell funktioniert:

• das Starten von etwas Lernbarem ganz ohne Installation
• Virtualisierung auf iOS, wo es Gerüchten zufolge die einzige Anwendung gibt, die das Recht auf dynamische Codegenerierung hat – nämlich die JS-Engine (stimmt das wirklich?)
• eine Mini-OS-Demonstration – Ein-Disketten-Software, eingebettete Firmware usw.…

Merkmale der Browser-Ausführungsumgebung

Wie ich bereits sagte, ist QEMU multithreading-fähig, und im Browser gibt es das nicht. Nun, das heißt, es gab es anfangs überhaupt nicht, dann kamen WebWorker – soweit ich verstehe, ist das Multithreading, das auf Nachrichtenübertragung basiert, ohne gemeinsam veränderbare Variablen. Natürlich bringt das erhebliche Probleme beim Portieren vorhandenen Codes, der auf dem shared memory-Modell basiert. Dann wurde unter dem Druck der Öffentlichkeit auch dieses implementiert, unter dem Namen SharedArrayBuffers. Es wurde schrittweise eingeführt, der Start in verschiedenen Browsern wurde gefeiert, dann feierte man das neue Jahr, und danach kam Meltdown… Danach kam man zu dem Schluss, dass man egal wie die Zeit misst, ob man es vergleicht oder nicht, es trotzdem ziemlich genau funktionieren würde. So wurde das Multithreading mit gemeinsamem Speicher deaktiviert. Soweit ich weiß, wurde es später wieder aktiviert, aber wie aus dem ersten Experiment klar wurde, gibt es auch ohne es ein Leben, und da es so ist, versuchen wir es ohne Multithreading.

Das zweite Merkmal besteht darin, dass niedrigstufige Manipulationen mit dem Stack nicht möglich sind: Man kann nicht einfach den aktuellen Kontext speichern und zu einem neuen mit einem neuen Stack wechseln. Der Aufruf-Stack wird von der JS-virtuellen Maschine verwaltet. Man könnte denken, wo ist das Problem, wenn wir uns ohnehin entschieden haben, mit den ehemaligen Threads vollständig manuell umzugehen? Das Problem liegt darin, dass die blockweise Ein- und Ausgabe in QEMU über Koroutinen implementiert ist, und genau hier wären uns niedrigstufige Stack-Manipulationen von Nutzen. Glücklicherweise enthält Emscripten bereits einen Mechanismus für asynchrone Operationen, sogar zwei: Asyncify und Emterpreter. Der erste funktioniert durch erhebliche Aufblähung des generierten JavaScript-Codes und wird nicht mehr unterstützt. Der zweite ist der aktuelle „richtige Weg“ und funktioniert durch die Generierung von Bytecode für den eigenen Interpreter. Es funktioniert, natürlich, langsam, bläht aber den Code nicht auf. Allerdings musste die Unterstützung für Koroutinen in diesem Mechanismus selbst beigesteuert werden (dort gab es bereits Koroutinen, die für Asyncify geschrieben wurden und eine Implementierung eines ähnlichen APIs für Emterpreter, sie mussten nur verbunden werden).

Momentan habe ich noch nicht den Code in WASM-kompilierbaren und von Emterpreter interpretierbaren Code unterteilt, weshalb blockbasierte Geräte noch nicht funktionieren (sehen Sie sich die nächsten Folgen an, wie man so sagt …). Das heißt, letztendlich soll so etwas Amüsantes wie folgt entstehen:

• interpreter-basierten blockweisen I/O. Und was, habt ihr wirklich ein emuliertes NVMe mit nativer Leistung erwartet? 🙂
• statisch kompilierten Hauptcode von QEMU (Übersetzer, andere emulierte Geräte usw.)
• dynamisch in WASM kompilierten Gastcode

Besonderheiten des QEMU-Quellcodes

Wie Sie wahrscheinlich schon erraten haben, ist der Code zur Emulation von Gastarchitekturen und der Code zur Generierung von Host-Maschinenanweisungen in QEMU getrennt. Tatsächlich ist es sogar noch etwas raffinierter:

• es gibt Gastarchitekturen
• einen Beschleuniger, nämlich KVM für Hardwarevirtualisierung unter Linux (für miteinander kompatible Gast- und Hostsystseme), TCG für JIT-Codegenerierung überall. Seit QEMU 2.9 gibt es Unterstützung für den Hardwarevirtualisierungsstandard HAXM unter Windows (Details)
• Wenn TCG und keine hardwarebasierte Virtualisierung verwendet wird, dann gibt es eine separate Unterstützung für die Codegenerierung für jede Host-Architektur sowie für den universellen Interpreter.
• … und rund um all das — emulierte Peripherie, Benutzeroberfläche, Migration, Record-Replay usw.

Übrigens, wussten Sie: QEMU kann nicht nur einen gesamten Computer emulieren, sondern auch einen Prozessor für einen einzelnen Benutzerprozess im Host-Kernel, was beispielsweise von AFL-Fuzzer zur Instrumentierung von Binärdateien verwendet wird. Vielleicht möchte jemand diesen Betriebsmodus von QEMU nach JS portieren? 😉

Wie die meisten seit langem bestehenden freien Programme wird QEMU über einen Aufruf kompiliert. configure und makeAngenommen, Sie haben entschieden, etwas hinzuzufügen: TCG-Backend, Implementierung von Threads, etwas anderes. Freuen Sie sich nicht zu früh über die Aussicht, mit Autoconf zu kommunizieren — tatsächlich configure scheint QEMU einen eigenständigen Code zu haben, der aus nichts generiert wird.

WebAssembly

Was ist das also — WebAssembly (auch WASM genannt)? Es ist ein Ersatz für Asm.js, das sich nun nicht mehr als gültiger JavaScript-Code ausgibt. Im Gegenteil, es ist rein binär und optimiert, und es ist nicht sehr einfach, darin eine ganze Zahl zu speichern: es wird zur Kompaktheit im Format LEB128.

Vielleicht haben Sie von dem Relooping-Algorithmus für Asm.js gehört — das ist die Wiederherstellung von "hochgradigen" Steuerflussanweisungen (also if-then-else, Schleifen usw.), auf die JS-Engines optimiert sind, aus niedriggradigem LLVM IR, das näher am Maschinenkode ist, der vom Prozessor ausgeführt wird. Offensichtlich ist das Zwischenformat von QEMU näher am zweiten. Es scheint also, dass hier der Bytecode ist, das Ende der Qualen… Und dann kommen die Blöcke, if-then-else und Schleifen!...

Und das ist ein weiterer Grund, warum Binaryen nützlich ist: es kann natürlich hochgradige Blöcke akzeptieren, die nahe dem sind, was in WASM gespeichert wird. Aber es kann auch Code aus dem Graphen von Basisblöcken und Übergängen zwischen ihnen ausgeben. Und was es hinter der benutzerfreundlichen C/C++ API für das Speichern von WebAssembly verbirgt, habe ich bereits gesagt.

TCG (Tiny Code Generator)

TCG wurde ursprünglich entwickelt eine Backend-Lösung für den C-Compiler. Danach konnte er anscheinend nicht mehr mit GCC konkurrieren, fand aber letztlich seinen Platz in QEMU als Mechanismus zur Code-Generierung für die Host-Plattform. Außerdem gibt es ein TCG-Backend, das eine Art abstrakten Bytecode erzeugt, der sofort vom Interpreter ausgeführt wird, aber ich habe mich diesmal entschieden, darauf zu verzichten. Dennoch kam mir der Fakt, dass QEMU bereits die Möglichkeit hat, den Übergang zu einem generierten TB über die Funktion tcg_qemu_tb_exec, sehr gelegen.

Um ein neues TCG-Backend in QEMU hinzuzufügen, muss ein Unterverzeichnis erstellt werden tcg/ (in diesem Fall, tcg/binaryen), in dem sich zwei Dateien befinden: tcg-target.h und tcg-target.inc.c und alles in darin eintragen. configureEs können auch andere Dateien dort abgelegt werden, aber wie man aus den Namen dieser beiden ableiten kann, werden sie beide irgendwo eingebunden: eine wie eine ganz normale Header-Datei (sie wird in tcg/tcg.heingeschlossen, und diese wiederum in andere Dateien in den Verzeichnissen tcg, accel und nicht nur), die andere nur als Code-Snippet in tcg/tcg.c, hat aber Zugang zu seinen statischen Funktionen.

Da ich beschloss, dass ich zu viel Zeit mit detaillierten Erklärungen verbringen würde, wie es funktioniert, habe ich einfach die „Gerüste“ dieser beiden Dateien aus einer anderen Backend-Implementierung kopiert und das ehrlich in der Lizenzüberschrift angegeben.

Die Datei tcg-target.h enthält hauptsächlich Einstellungen in Form von #define-en:

• wie viele Register und welche Breite auf der Zielarchitektur vorhanden sind (bei uns – so viele wir wollen, die Frage ist mehr, was in effizienten Code von dem Browser auf der „echten Zielarchitektur“ generiert wird…)
• Ausrichtung der Host-Instruktionen: auf x86, und auch im TCI, werden Instruktionen überhaupt nicht ausgerichtet, ich werde im Code-Puffer keine Instruktionen, sondern Zeiger auf die Datenstrukturen der Binaryen-Bibliothek ablegen, daher sage ich: 4 Bytes
• welche optionalen Instruktionen das Backend generieren kann – wir schalten alles ein, was wir in Binaryen finden, den Rest lassen wir den Beschleuniger in einfachere umwandeln.
• Welche ungefähre Größe des TLB-Caches fordert das Backend? Die Sache ist die, dass es in QEMU alles ernst gemeint ist: Zwar gibt es Hilfsfunktionen, die Load/Store unter Berücksichtigung des Gästemoduls (MMU) durchführen, aber ihren Übersetzungscache speichern sie in einer Struktur, deren Verarbeitung bequem direkt in die Übersetzungsblöcke integriert werden kann. Die Frage ist jedoch, welche Offset in dieser Struktur am effizientesten von einer kleinen und schnellen Befehlskette verarbeitet wird.
• Hier kann man die Zuordnung eines oder zweier reservierter Register anpassen, den Aufruf des TB über eine Funktion aktivieren und optional ein paar Kleinigkeiten beschreiben. inline-Funktionen wie flush_icache_range (aber das ist nicht unser Fall)

Die Datei tcg-target.inc.c, wie üblich normalerweise viel größer ist und mehrere Pflichtfunktionen enthält:

• Initialisierung, die unter anderem angibt, welche Anweisung mit welchen Operanden arbeiten kann. Dreist von mir aus einem anderen Backend kopiert.
• Eine Funktion, die eine Anweisung des internen Bytecodes entgegennimmt.
• Hier kann man auch Hilfsfunktionen hinzufügen, und zudem kann man statische Funktionen aus tcg/tcg.c

Für mich habe ich folgende Strategie gewählt: In den ersten Worten des nächsten Übersetzungsblocks habe ich vier Zeiger festgehalten: ein Startmarke (ein gewisser Wert in der Nähe von 0xFFFFFFFF, an dem der aktuelle Zustand des TB bestimmt wurde), den Kontext, das generierte Modul und eine magische Zahl zur Fehlersuche. Zuerst wurde das Markenfeld auf 0xFFFFFFFF - n

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

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,
          
          // ...
      }
  );
  // und jetzt haben Sie bereits eine Instanz!
}, buf, sz);

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