Il était une fois, pour rire, j'ai décidé de prouver la réversibilité du processus et d'apprendre à générer JavaScript (ou plutôt Asm.js) à partir du code machine. QEMU a été choisi pour l'expérience, quelque temps plus tard, un article a été écrit sur Habr. Dans les commentaires, on m'a conseillé de refaire le projet sur WebAssembly, et moi-même je n'avais pas envie de quitter le projet presque terminé moi-même ... Le travail a continué, mais très lentement, et maintenant, dans cet article, un commentaire est apparu sur le sujet "Alors, comment ça s'est terminé ?". Pour ma réponse détaillée, j'ai entendu "Cela tire sur un article." Eh bien, si ça tire, il y aura un article. Peut-être que quelqu'un vous sera utile. À partir de là, le lecteur apprend quelques faits sur la génération de code QEMU de backends de l'appareil, ainsi que sur la façon d'écrire un compilateur Just-in-Time pour une application Web.
Les tâches
Comme j'ai déjà appris à "porter" QEMU sur JavaScript, cette fois, il a été décidé de le faire judicieusement et de ne pas répéter les anciennes erreurs.
Nombre de fois d'erreur: branche à partir de la libération de points
Ma première erreur a été de dériver ma version de la version amont 2.4.1. Ensuite, cela m'a semblé une bonne idée: s'il existe une version ponctuelle, elle est probablement plus stable qu'une simple 2.4, et plus encore master branche master . Et comme je prévoyais d'ajouter une bonne quantité de mes bugs, je n'avais pas du tout besoin d'étrangers. Alors c'est probablement arrivé. Mais voici la malchance: QEMU ne reste pas immobile, et à un moment donné, ils ont même annoncé l'optimisation du code de pourcentage généré par 10. "Ouais, maintenant je gèle", je pensais et rompit . Ici, nous devons faire une digression: en raison de la nature à un seul thread de QEMU.js et du fait que le QEMU d'origine n'implique pas l'absence de multithreading (c'est-à-dire, il est essentiel qu'il puisse exploiter plusieurs chemins de code non liés en même temps, et pas seulement «brancher tous les noyaux»), les principales fonctions des threads a dû "tourner" pour la possibilité d'un appel de l'extérieur. Cela a créé des problèmes de fusion naturels. Cependant, le fait que certaines des modifications de la branche principale, avec lesquelles j'ai essayé de fusionner mon code, ont également été choisies dans la version ponctuelle (et, par conséquent, dans ma branche), n'ajouterait probablement pas la commodité.
En général, j'ai décidé que de toute façon le prototype avait du sens jeter démonter pour les pièces et construire une nouvelle version à partir de zéro basée sur quelque chose de plus frais et maintenant de master .
Erreur numéro deux: méthodologie TLP
En fait, ce n'est pas une erreur, en général - c'est juste une caractéristique de créer un projet dans des conditions de méconnaissance totale de "où et comment se déplacer?", Et en général "allons-nous y arriver?". Dans ces conditions, la programmation était une option justifiable, mais, bien sûr, je ne voulais absolument pas la répéter inutilement. Cette fois, je voulais le faire avec sagesse: commits atomiques, changements délibérés de code (et non «enchaîner des caractères aléatoires jusqu'à ce qu'il compile (avec des avertissements)», comme Linus Torvalds l'a dit un jour à propos de quelqu'un, si vous croyez Wikitatnik), etc.
Erreur numéro trois: ne pas savoir que le gué monte dans l'eau
Je ne me suis pas encore complètement débarrassé de cela, mais maintenant j'ai décidé de ne pas suivre le chemin de la moindre résistance, et de le faire "à la manière d'un adulte", à savoir, écrire mon backend TCG à partir de zéro afin de ne pas dire plus tard, "Oui, il Bien sûr, lentement, mais je ne peux pas tout contrôler - TCI est écrit comme ça ... ". De plus, au début, cela semblait être une solution évidente, car je générais du code binaire . Comme le dit le proverbe, "J'ai récupéré Gand, mais pas celui-là": le code est, bien sûr, binaire, mais le contrôle ne peut pas être transféré comme ça - il doit être explicitement poussé dans le navigateur pour la compilation, résultant en un certain objet du monde JS, qui encore besoin d'enregistrer quelque part. Cependant, le normal Pour les architectures RISC, si je comprends bien, une situation typique est la nécessité de vider explicitement le cache d'instructions pour le code régénéré - si ce n'est pas ce dont nous avons besoin, alors au moins c'est proche. De plus, lors de ma dernière tentative, j'ai appris que le contrôle ne semble pas être transféré au milieu du bloc de traduction, par conséquent, nous n'avons pas vraiment besoin que le bytecode soit interprété à partir de n'importe quel décalage, et nous pouvons simplement générer par fonction sur TB.
Entré et coups de pied
Bien que j'ai commencé à réécrire le code en juillet, le Pendel magique s'est glissé inaperçu: généralement des lettres de GitHub viennent comme des notifications de réponses aux problèmes et aux demandes Pull, puis, tout à coup , le Binaryen en tant que backend qemu dans le contexte dit : «Le voici - il a fait quelque chose comme ça, peut-être qu'il dira quelque chose. » Il s'agissait d'utiliser la bibliothèque Binaryen liée à Emscripten pour créer un WASM JIT. Eh bien, j'ai dit que vous disposez d'une licence Apache 2.0 et que QEMU dans son ensemble est distribué sous GPLv2, et ils ne sont pas très compatibles. Il s'est avéré que la licence pouvait être corrigée d'une manière ou d' une autre (je ne sais pas: peut-être, changer, peut-être doubler la licence, peut-être autre chose ...). Bien sûr, cela m'a fait plaisir, car j'avais déjà regardé le format binaire WebAssembly plusieurs fois à ce moment-là, et j'étais en quelque sorte triste et incompréhensible pour moi. Il y avait une bibliothèque ici qui engloutirait les blocs de base avec le graphe de transition, et émettrait le bytecode, et même le lancerait dans l'interpréteur si nécessaire.
Ensuite, il y avait aussi une lettre sur la liste de diffusion QEMU, mais celle-ci est plus susceptible de se poser la question: "Qui en a besoin?" Et cela, soudain , était nécessaire. Au minimum, vous pouvez regrouper de tels cas d'utilisation si cela fonctionne plus ou moins intelligemment:
- lancer quoi que ce soit d'enseignement sans aucune installation du tout
- virtualisation sur iOS, où selon les rumeurs la seule application qui a le droit de générer du code à la volée est le moteur JS (est-ce vrai?)
- démonstration mini-OS - un seul disque, intégré, toutes sortes de firmware, etc ...
Caractéristiques du runtime du navigateur
Comme je l'ai dit, QEMU est lié au multithreading, mais il n'est pas dans le navigateur. Eh bien, c'est comme si non ... Au début, ce n'était pas là du tout, puis les WebWorkers sont apparus - si je comprends bien, c'est du multithreading basé sur le passage de messages sans variables mutuellement variables . Naturellement, cela crée des problèmes importants lors du portage de code existant basé sur un modèle de mémoire partagée. Puis, sous la pression du public, il a été implémenté sous le nom SharedArrayBuffers . Ils l'ont progressivement introduit, ont célébré son lancement dans différents navigateurs, puis ont célébré la nouvelle année, puis Meltdown ... Après quoi ils sont arrivés à la conclusion que grossier, ne pas grossier la mesure du temps, mais avec l'aide de la mémoire partagée et d'un flux incrémentant le compteur, c'est toujours assez précis . Ils ont donc désactivé le multithreading avec la mémoire partagée. Il semble qu'ils l'ont réactivé plus tard, mais, comme il est devenu clair à partir de la première expérience, il y a de la vie sans elle, et si c'est le cas, nous essaierons de le faire sans compter sur le multithreading.
La deuxième caractéristique est l'impossibilité de manipulations de bas niveau avec la pile: vous ne pouvez pas simplement prendre, enregistrer le contexte actuel et passer à un nouveau avec une nouvelle pile. La pile d'appels est gérée par la machine virtuelle JS. Il semblerait, quel est le problème, puisque nous avons quand même décidé de gérer les anciens flux complètement manuellement? Le fait est que le bloc entrée-sortie dans QEMU est implémenté via des coroutines, et ici des manipulations de pile de bas niveau nous seraient utiles. Heureusement, Emscipten contient déjà un mécanisme pour les opérations asynchrones, même deux: Asyncify et Emterpreter . Le premier fonctionne grâce à un ballonnement important du code JavaScript généré et n'est plus pris en charge. La seconde est la "voie correcte" actuelle et fonctionne grâce à la génération de bytecode pour son propre interprète. Cela fonctionne, bien sûr, lentement, mais cela ne gonfle pas le code. Certes, la prise en charge de la coroutine pour ce mécanisme devait être attribuée seule (il y avait déjà des coroutines écrites sous Asyncify et il y avait une implémentation d'environ la même API pour Emterpreter, vous deviez simplement les connecter).
Pour le moment, je n'ai pas encore réussi à diviser le code en compilé dans WASM et interprété en utilisant Emterpreter, donc les périphériques de blocs ne fonctionnent pas encore (voir la prochaine série, comme on dit ...). Autrement dit, à la fin, vous devriez obtenir quelque chose de super drôle:
- E / S de bloc interprétées. Eh bien, qu'attendiez-vous vraiment d'un NVMe émulé avec des performances natives? :)
- code QEMU principal compilé statiquement (traducteur, autres périphériques émulés, etc.)
- Code invité WASM compilé dynamiquement
Caractéristiques des sources QEMU
Comme vous l'avez probablement déjà deviné, le code d'émulation pour les architectures invitées et le code pour générer des instructions de machine hôte à partir de QEMU sont séparés. En fait, il y a même un peu plus délicat:
- il y a des architectures invitées
- il existe des accélérateurs , à savoir KVM pour la virtualisation matérielle sous Linux (pour les systèmes hôtes et hôtes compatibles), TCG pour la génération de code JIT n'importe où. À partir de QEMU 2.9, la prise en charge de la norme de virtualisation matérielle HAXM sous Windows est apparue ( détails )
- si TCG est utilisé, et non la virtualisation matérielle, il prend en charge séparément la génération de code pour chaque architecture hôte, ainsi que pour un interpréteur universel
- ... et tout autour - périphériques émulés, interface utilisateur, migration, relecture d'enregistrement, etc.
Au fait, le saviez-vous: QEMU peut émuler non seulement l'ordinateur entier, mais aussi le processeur pour un processus utilisateur séparé dans le noyau hôte, qui est utilisé, par exemple, par le flou AFL pour l'instrumentation des binaires. Peut-être que quelqu'un veut porter ce mode de fonctionnement QEMU sur JS? ;)
Comme la plupart des programmes gratuits de longue date, QEMU est construit via un appel à configure et à make . Supposons que vous décidiez d'ajouter quelque chose: un backend TCG, une implémentation de thread, autre chose. Ne vous précipitez pas pour vous réjouir / être horrifié (souligner si nécessaire) la perspective de communiquer avec Autoconf - en fait, la configure à QEMU semble être auto-écrite et il n'y a rien à générer.
Webassembly
Alors, quelle est cette chose - WebAssembly (aka WASM)? Il s'agit d'un remplacement pour Asm.js, qui ne prétend plus être un code JavaScript valide. Au contraire, il est purement binaire et optimisé, et même simplement y écrire un entier n'est pas très simple: il est stocké au format LEB128 pour plus de compacité .
Vous avez peut-être entendu parler de l'algorithme de relooping pour Asm.js - restauration des instructions de contrôle de flux d'exécution «de haut niveau» (c'est-à-dire, si-alors-sinon, boucles, etc.) sous lesquelles les moteurs JS sont réglés à partir du LLVM IR de bas niveau, plus proche du code machine exécuté par le processeur. Naturellement, la représentation intermédiaire de QEMU est plus proche de la seconde. Il semblerait que le voici, bytecode, la fin du tourment ... Et puis les blocs, if-then-else et les boucles! ..
Et c'est une autre raison pour laquelle Binaryen est utile: il peut, bien sûr, accepter des blocs de haut niveau proches de ce qui sera stocké dans WASM. Mais il peut également produire du code à partir du graphe des blocs de base et des transitions entre eux. Eh bien, j'ai déjà dit qu'il cache le format de stockage WebAssembly derrière l'API C / C ++ pratique.
TCG (Générateur de code minuscule)
TCG était à l'origine un backend pour le compilateur C. Puis, apparemment, il ne pouvait pas supporter la concurrence de GCC, mais à la fin il a trouvé sa place dans QEMU en tant que mécanisme de génération de code pour la plate-forme hôte. Il y a aussi un backend TCG qui génère du bytecode abstrait, qui est immédiatement exécuté par l'interpréteur, mais j'ai décidé de quitter cette fois cette fois. Cependant, le fait que QEMU ait déjà la possibilité d'activer la transition vers la TB générée via la fonction tcg_qemu_tb_exec été très utile.
Pour ajouter un nouveau backend TCG à QEMU, vous devez créer un sous-répertoire tcg/< > (dans ce cas, tcg/binaryen ), et il tcg/binaryen deux fichiers: tcg-target.h et tcg-target.inc.c et tout enregistrer c'est configure . Vous pouvez y placer d'autres fichiers, mais, comme vous pouvez le deviner d'après les noms de ces deux, ils seront tous les deux inclus quelque part: l'un en tant que fichier d'en-tête normal (il sera inclus dans tcg/tcg.h , et celui-ci sera déjà dans d'autres fichiers dans les répertoires tcg , accel et pas seulement), l'autre uniquement comme extrait de code dans tcg/tcg.c , mais il a accès à ses fonctions statiques.
Ayant décidé que je passerais trop de temps sur les procédures détaillées, comment cela fonctionne, j'ai simplement copié les «squelettes» de ces deux fichiers à partir d'une autre implémentation backend, en l'indiquant honnêtement dans l'en-tête de la licence.
Le tcg-target.h contient principalement des paramètres sous la forme de #define s:
- combien de registres et quelle largeur sont sur l'architecture cible (nous en avons - autant que nous voulons, il y en a tellement - la question est plus que ce que le navigateur va générer dans un code plus efficace sur une architecture "complètement cible" ...)
- alignement des instructions de l'hôte: sur x86, et dans TCI, les instructions ne s'alignent pas du tout, je vais mettre dans le tampon de code pas des instructions du tout, mais des pointeurs sur les structures de la bibliothèque Binaryen, donc je dirai: 4 octets
- quelles instructions facultatives le backend peut générer - allumez tout ce que nous trouvons dans Binaryen, laissez l'accélérateur diviser le reste en plus simples
- quelle taille approximative du cache TLB est demandée par le backend. Le fait est que dans QEMU, tout est sérieux: bien qu'il existe des fonctions d'assistance qui se chargent / stockent en tenant compte de la MMU invitée (et où maintenant sans elle?), Ils enregistrent leur cache de traduction sous la forme d'une structure, dont le traitement est pratique à intégrer directement aux blocs de traduction. La question est de savoir quel décalage dans cette structure est géré le plus efficacement par une petite séquence de commandes rapide
- ici, vous pouvez tordre le but d'un ou deux registres réservés, activer l'appel de TB via une fonction et éventuellement décrire quelques petites fonctions en
inline comme flush_icache_range (mais ce n'est pas notre cas)
Le tcg-target.inc.c , bien sûr, est généralement beaucoup plus volumineux et contient plusieurs fonctions requises:
- initialisation, indiquant, entre autres, les restrictions quant à l'instruction avec laquelle les opérandes peuvent fonctionner. Insolemment copié par moi depuis un autre backend
- fonction acceptant une instruction de bytecode interne
- ici vous pouvez mettre des fonctions auxiliaires, et aussi ici vous pouvez utiliser des fonctions statiques de
tcg/tcg.c
Pour ma part, j'ai choisi la stratégie suivante: dans les premiers mots du bloc de traduction suivant, j'ai noté quatre pointeurs: la marque de départ (une certaine valeur au voisinage de 0xFFFFFFFF , qui a déterminé l'état actuel de TB), le contexte, le module généré et le nombre magique pour le débogage. Tout d'abord, le libellé a été défini sur 0xFFFFFFFF - n , où n est un petit nombre positif, et chaque fois via l'interpréteur, il a augmenté de 1. Lorsqu'il a atteint 0xFFFFFFFE , la compilation s'est produite, le module a été stocké dans la table de fonction, importé dans un petit "lanceur", dans lequel l'exécution a quitté tcg_qemu_tb_exec et le module a été supprimé de la mémoire QEMU.
Pour paraphraser les classiques, "Crutch, combien proger s'est entrelacé dans ce son pour le coeur ...". Cependant, la mémoire fuyait quelque part. Et c'était une mémoire gérée par QEMU! J'avais un code qui, lors de l'écriture de l'instruction suivante (enfin, c'est-à-dire un pointeur), a supprimé celui dont le lien était à cet endroit plus tôt, mais cela n'a pas aidé. En fait, dans le cas le plus simple, QEMU alloue de la mémoire au démarrage et y écrit le code généré. Lorsque le tampon se termine, le code est jeté et le suivant commence à être écrit à sa place.
Après avoir étudié le code, j'ai réalisé que la béquille avec nombre magique nous permettait de ne pas tomber sur la destruction du tas, libérant quelque chose de mal sur le tampon non initialisé lors du premier passage. Mais qui écrase le tampon en contournant ma fonction plus tard? Comme les développeurs d'Emscripten l'ont conseillé, après avoir rencontré un problème, j'ai porté le code résultant vers l'application native, défini Mozilla Record-Replay dessus ... En général, en conséquence, j'ai réalisé une chose simple: une struct TranslationBlock avec sa description est allouée à chaque bloc. Devinez où ... C'est vrai, juste en face du bloc juste dans le tampon. Après avoir réalisé cela, j'ai décidé de le lier avec des béquilles (au moins certaines), et j'ai simplement jeté le numéro magique et transféré les mots restants dans la struct TranslationBlock , créant une liste à lien unique que vous pouvez parcourir rapidement lors de la réinitialisation du cache de traduction et libérer de la mémoire.
Certaines béquilles sont restées: par exemple, des pointeurs marqués dans le tampon de code - certains d'entre eux sont simplement BinaryenExpressionRef , c'est-à-dire qu'ils examinent les expressions qui doivent être linéairement placées dans l'unité de base générée, partie - la condition de transition entre les WB, partie - où aller. Eh bien, il existe déjà des blocs préparés pour Relooper, qui doivent être connectés en fonction des conditions. Pour les distinguer, l'hypothèse est utilisée qu'ils sont tous alignés sur au moins quatre octets, de sorte que vous pouvez utiliser en toute sécurité les deux bits inférieurs de l'étiquette, il vous suffit de vous rappeler de le supprimer si nécessaire. Soit dit en passant, ces étiquettes sont déjà utilisées dans QEMU pour indiquer la raison de la sortie du cycle TCG.
Utilisation de Binaryen
Les modules de WebAssembly contiennent des fonctions, chacune contenant un corps représentant une expression. Les expressions sont des opérations unaires et binaires, des blocs constitués de listes d'autres expressions, un flux de contrôle, etc. Comme je l'ai déjà dit, le flux de contrôle est organisé précisément comme des branches de haut niveau, des boucles, des appels de fonction, etc. Les arguments des fonctions ne sont pas transmis sur la pile, mais explicitement, comme dans JS. Il y a des variables globales, mais je ne les ai pas utilisées, donc je n'en parlerai pas.
Les fonctions ont également des variables locales, numérotées à partir de zéro, du type: int32 / int64 / float / double. Les n premières variables locales sont les arguments passés à la fonction. Veuillez noter que bien que tout ici ne soit pas entièrement de bas niveau en termes de flux de contrôle, les entiers ne portent toujours pas le signe / signe sans signe: le comportement du nombre dépend du code d'opération.
De manière générale, Binaryen fournit une API C simple : vous créez un module, vous y créez des expressions - unaires, binaires, blocs à partir d'autres expressions, flux de contrôle, etc. Ensuite, vous créez une fonction, dont le corps dont vous avez besoin pour spécifier une expression. Si vous, comme moi, avez un graphe de transition de bas niveau, le composant relooper vous aidera. Pour autant que je comprends, il est possible d'utiliser un contrôle de haut niveau du flux d'exécution dans le bloc, tant qu'il ne dépasse pas les limites du bloc - c'est-à-dire qu'il est possible de créer une branche de chemin rapide / chemin lent interne à l'intérieur du code de traitement du cache TLB intégré, mais il n'y a aucun moyen d'interférer avec le flux de contrôle «externe» . Lorsque vous relâchez relooper, ses blocs sont libérés, lorsque vous libérez un module, les expressions, fonctions, etc., allouées dans son arène disparaissent.
Cependant, si vous souhaitez interpréter le code à la volée sans création et suppression inutiles de l'instance d'interpréteur, il peut être judicieux de transférer cette logique dans un fichier C ++, et de là contrôler directement la bibliothèque API C ++ entière, en contournant les wrappers finis.
Ainsi, pour générer le code, vous avez besoin
… — , , — .
--, :
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,
- QEMU JS , ( ), . , translation block, , struct TranslationBlock .
, ( ) Firefox. Chrome - , - WebAssembly, ...
. , , - . , . , WebAssembly , JS, , , .
: 32- , Binaryen, - - 2 32- . , Binaryen . ?
-, « , 32- Linux?» . , : 1 2 Gb.
- ( ). , — . « : , ...».
… Valgrind-, , , , , Valgrind :)
, - , ...