Comment écrire une machine virtuelle (2022)

• Pour comprendre le fonctionnement interne des ordinateurs et la manière dont les langages de programmation s’exécutent, l’auteur a implémenté lui-même une VM en C d’environ 250 lignes qui exécute des programmes assembleur sur l’architecture pédagogique LC-3
• La cible de l’implémentation est un petit modèle d’ordinateur avec 65 536 emplacements mémoire de 16 bits, 10 registres, 16 opcodes, des drapeaux de condition, des trap routines et des registres mappés en mémoire
• La boucle d’exécution fonctionne selon une structure fetch-decode-execute : elle lit l’instruction pointée par PC, l’incrémente, interprète l’opcode, puis exécute des instructions comme ADD, LDI, BR, JMP ou TRAP
• Le chargement d’un programme lit l’origin 16 bits au début du fichier objet pour le placer en mémoire, puis effectue un byte swap afin d’adapter le format big-endian de LC-3 au format little-endian utilisé par la plupart des ordinateurs modernes
• Les entrées clavier et la sortie console sont gérées par les trap routines et les registres mappés en mémoire KBSR/KBDR, avec du code différent selon Unix/macOS et Windows pour la mise en tampon des entrées du terminal

---

Objectifs et prérequis du tutoriel

• Le tutoriel suit la mise en œuvre d’une machine virtuelle LC-3 permettant d’exécuter des programmes en langage assembleur
• Le code final fait environ 250 lignes en C, avec un fichier lc3.c pour Unix et lc3-win.c pour Windows
• Les prérequis sont la lecture de C ou C++ de base et l’arithmétique binaire
• Le code complet se trouve dans le repo GitHub, et le tutoriel lui-même est au format literate program : les blocs de code sont assemblés pour produire la source finale

Ce que fait une machine virtuelle

• Une VM est un programme qui se comporte comme un CPU et certains composants matériels
  • Elle effectue des opérations arithmétiques
  • Elle lit et écrit en mémoire
  • Elle interagit avec des périphériques d’E/S
  • Elle comprend son propre langage machine et exécute des programmes
• Selon son objectif, une VM peut reproduire fidèlement du matériel réel ou proposer une nouvelle architecture virtuelle pour faciliter le développement logiciel
• La JVM est un exemple représentatif de VM fournissant une plateforme d’exécution standard ; sur les appareils où la JVM est implémentée, les programmes Java, Kotlin et Clojure peuvent s’exécuter sans modification
• L’exécution isolée est aussi un usage important des VM
  • Dans le garbage collection, la VM peut observer la pile et les références mémoire en dehors du programme en cours d’exécution
  • Les smart contracts Ethereum s’exécutent dans une VM qui n’a pas accès au système de fichiers, au réseau ni au disque

Composition de l’architecture LC-3

• La cible de l’implémentation est LC-3, utilisé dans l’enseignement universitaire de l’architecture des ordinateurs et de l’assembleur
• La mémoire LC-3 comporte 65 536 emplacements, chacun stockant une valeur de 16 bits
  • La capacité totale est de 128 Ko
  • Dans l’implémentation C, elle est représentée par le tableau uint16_t memory[MEMORY_MAX]
• Il y a 10 registres au total
  • R0 à R7 : 8 registres généraux
  • PC : l’adresse mémoire de la prochaine instruction à exécuter
  • COND : le drapeau de condition du dernier résultat calculé
• Toutes les instructions LC-3 font 16 bits, et les 4 bits de gauche correspondent à l’opcode
  • 16 opcodes sont définis
  • Ils incluent OP_BR, OP_ADD, OP_LD, OP_ST, OP_JSR, OP_AND, OP_LDR, OP_STR, OP_RTI, OP_NOT, OP_LDI, OP_STI, OP_JMP, OP_RES, OP_LEA et OP_TRAP
• Les drapeaux de condition indiquent le signe du dernier résultat calculé
  • FL_POS : positif
  • FL_ZRO : zéro
  • FL_NEG : négatif

Assembleur et langage machine

• Ce que la VM LC-3 exécute réellement n’est pas l’assembleur lisible par un humain, mais un tableau d’instructions machine 16 bits
• L’assembleur convertit l’assembleur LC-3 écrit en texte en instructions binaires 16 bits
• L’exemple Hello World suit le déroulé suivant
  • .ORIG x3000 : indique l’adresse mémoire où le programme sera chargé
  • LEA R0, HELLO_STR : charge l’adresse de la chaîne dans R0
  • PUTS : affiche la chaîne pointée par R0
  • HALT : arrête le programme
  • .STRINGZ "Hello World!" : stocke les données de la chaîne dans le programme
• .ORIG et .STRINGZ ne sont pas des instructions CPU, mais des directives de l’assembleur
• Les conditions et les boucles sont implémentées avec des instructions de branchement proches d’un goto, comme BRn LOOP

Procédure centrale de la boucle d’exécution

• L’exécution de la VM répète la même procédure
  • Lire l’instruction à l’adresse du registre PC
  • Incrémenter PC
  • Obtenir l’opcode depuis les 4 bits de poids fort de l’instruction
  • Exécuter le code correspondant à l’opcode
  • Lire à nouveau l’instruction suivante
• L’adresse de départ par défaut est 0x3000
• Certaines instructions modifient directement PC pour faire sauter le flux d’exécution
  • Grâce aux instructions de branchement et de saut, les boucles et l’exécution conditionnelle restent possibles même avec une structure qui se contente sinon d’incrémenter PC
• La boucle main appelle le code de traitement propre à chaque opcode via switch (op)
  • Elle traite OP_ADD, OP_AND, OP_NOT, OP_BR, OP_JMP, OP_JSR, OP_LD, OP_LDI, OP_LDR, OP_LEA, OP_ST, OP_STI, OP_STR et OP_TRAP
  • OP_RES et OP_RTI sont des opcodes inutilisés et peuvent être gérés par abort()

Mode d’implémentation des instructions

• ADD additionne deux valeurs, stocke le résultat dans le registre de destination et met à jour les drapeaux de condition
• ADD a deux modes
  • Mode registre : le second opérande est lu depuis un autre registre
  • Mode immédiat : le second opérande est lu depuis les 5 bits de poids faible imm5 de l’instruction
• Les valeurs plus courtes que 16 bits, comme imm5, doivent être étendues en valeur 16 bits par extension de signe
  • Les valeurs positives sont complétées par des 0
  • Les valeurs négatives sont complétées par des 1 afin de préserver la valeur d’origine
• Les instructions qui écrivent une valeur dans un registre mettent à jour R_COND avec update_flags
  • Si la valeur vaut 0 : FL_ZRO
  • Si le bit de poids fort vaut 1 : FL_NEG
  • Sinon : FL_POS
• LDI est l’instruction « load indirect »
  • Elle applique une extension de signe au PCoffset9 de l’instruction
  • Elle l’ajoute au PC courant pour obtenir une adresse mémoire
  • Elle utilise ensuite la valeur stockée à cet emplacement comme adresse pour lire la donnée finale
  • Elle stocke la valeur lue dans le registre de destination et met à jour les drapeaux de condition

Jeu d’instructions principal

• Arithmétique et opérations bit à bit
  • ADD : addition
  • AND : AND bit à bit
  • NOT : NOT bit à bit
• Flux de contrôle
  • BR : déplace PC en comparant les drapeaux de condition aux bits de condition de l’instruction
  • JMP : définit PC à la valeur du registre indiqué
  • RET : mot-clé séparé dans la spécification, mais cas particulier de JMP
  • JSR, JSRR : stockent le PC courant dans R7 et sautent à l’emplacement de la sous-routine
• Lecture mémoire
  • LD : lit à l’adresse offset relative à PC
  • LDI : suit une adresse indirecte supplémentaire avant de lire
  • LDR : lit à l’adresse calculée avec un registre de base et un offset
  • LEA : stocke l’adresse effective elle-même dans un registre
• Écriture mémoire
  • ST : stocke à l’adresse offset relative à PC
  • STI : stocke en suivant une adresse indirecte
  • STR : stocke à l’adresse calculée avec un registre de base et un offset

Trap routines et E/S

• LC-3 fournit des trap routines pour les tâches communes et l’accès aux périphériques d’E/S
• Une trap routine peut être vue comme le système d’exploitation ou l’API de LC-3
• Les trap codes sont définis comme suit
  • TRAP_GETC = 0x20 : saisie d’un caractère au clavier, sans écho dans le terminal
  • TRAP_OUT = 0x21 : sortie d’un caractère
  • TRAP_PUTS = 0x22 : sortie d’une word string
  • TRAP_IN = 0x23 : saisie d’un caractère puis écho dans le terminal
  • TRAP_PUTSP = 0x24 : sortie d’une byte string
  • TRAP_HALT = 0x25 : arrêt du programme
• Dans le simulateur LC-3 officiel, les trap routines sont écrites en assembleur, mais dans cette VM elles sont implémentées sous forme de fonctions C
• PUTS affiche les caractères depuis l’adresse stockée dans R0 jusqu’à rencontrer x0000
  • Les chaînes LC-3 ne stockent pas un caractère par octet comme les chaînes C, mais un caractère par emplacement mémoire
  • Chaque emplacement mémoire faisant 16 bits, il est converti en char lors de la sortie en C
• Le trap HALT affiche "HALT", puis met le drapeau d’exécution à 0 pour quitter la boucle de la VM

Chargement d’une image de programme

• Convertir un programme assembleur LC-3 en langage machine produit un fichier contenant un tableau d’instructions et de données
• Les premiers 16 bits du fichier objet sont l’origin, qui indique où placer le programme en mémoire
• Le loader lit d’abord l’origin, puis copie le reste des données en mémoire à partir de cette adresse
• Les programmes LC-3 sont au format big-endian
  • La plupart des ordinateurs modernes étant little-endian, swap16 est appliqué à chaque uint16_t chargé
  • Sur les ordinateurs big-endian, comme les anciens Mac PPC, il ne faut pas effectuer ce swap
• read_image ouvre le fichier en mode binaire, appelle read_image_file, puis ferme le fichier

Registres mappés en mémoire

• Les registres spéciaux auxquels on n’accède pas via la table classique des registres sont mappés à des adresses mémoire spécifiques
• Dans LC-3, deux registres mappés en mémoire doivent être implémentés
  • MR_KBSR = 0xFE00 : keyboard status register
  • MR_KBDR = 0xFE02 : keyboard data register
• KBSR indique si une touche a été pressée, et KBDR stocke la touche pressée
• GETC bloque l’exécution jusqu’à recevoir une entrée, mais KBSR et KBDR interrogent l’état du périphérique par polling, ce qui permet au programme de continuer à réagir pendant l’attente d’entrée
• Les lectures mémoire passent par mem_read au lieu de lire directement le tableau
  • Si l’adresse est MR_KBSR, l’état du clavier est vérifié avec check_key()
  • S’il y a une touche, le bit de poids fort de KBSR est activé et la valeur de getchar() est stockée dans KBDR
  • S’il n’y a pas de touche, KBSR est réglé à 0

Gestion du terminal selon la plateforme

• Pour gérer correctement les entrées clavier et le comportement du terminal, il faut configurer la mise en tampon des entrées selon la plateforme
• L’implémentation Linux/macOS/UNIX utilise termios, select, etc.
  • Elle désactive le mode canonique et l’écho
  • Elle vérifie la disponibilité d’une entrée avec select
• L’implémentation Windows utilise GetStdHandle, GetConsoleMode, SetConsoleMode, _kbhit, etc.
  • Elle ajuste l’écho et la saisie ligne par ligne
  • Elle vérifie les frappes avec WaitForSingleObject et _kbhit
• Au démarrage du programme, disable_input_buffering() est appelé, puis restore_input_buffering() à la fin
• À la réception de SIGINT, le programme restaure les paramètres du terminal, affiche un saut de ligne, puis se termine

Exécution et débogage de la VM

• Exemple de build de la VM

gcc lc3.c -o lc3-vm

• Pour l’exécuter, il faut passer en argument le fichier objet LC-3 assemblé

lc3-vm path/to/2048.obj

• Les fichiers objets fournis en exemple sont 2048.obj et rogue.obj
• L’exemple 2048 se contrôle avec les touches WASD
• Si le programme ne fonctionne pas correctement, il est probable qu’une instruction soit mal implémentée
  • La méthode recommandée consiste à lire la source assembleur LC-3 et à exécuter pas à pas les instructions de la VM dans un débogueur
  • Si l’exécution n’arrive pas à l’instruction attendue, il faut revérifier la spécification et l’implémentation de cette instruction

Option : implémentation C++ basée sur les génériques

• Une implémentation C++ plus courte est également présentée en option
• Comme plusieurs instructions partagent des opérations répétées — extension de signe, offset relatif à PC, calcul d’adresse indirecte — l’exécution des instructions peut être vue comme un pipeline de petites étapes de traitement
• En utilisant des templates C++ et des drapeaux de bits, seules les étapes nécessaires à chaque opcode sont incluses à la compilation
• Cette approche réduit la duplication de code et se rapproche davantage de la manière dont le câblage matériel réel occupe de l’espace physique sur une puce
• L’émulateur NES de Bisqwit est mentionné comme source de l’idée

Ressources et contributions

• atul-g a contribué une reference card qui résume le fonctionnement de tout le système
• Les implémentations dans différents langages sont regroupées sous le topic GitHub lc3
  • C, C++, Go, Haskell, Java, JavaScript, Kotlin, Lua, OCaml, Python, Ruby, Rust, Swift, TypeScript, Zig, entre autres
• Pour faire apparaître sa propre implémentation dans la liste, il suffit d’ajouter le topic GitHub lc3
• La prise en charge de la plateforme Windows a été apportée par inkydragon
• Le projet comporte une good first issue liée aux tests d’intégration

[GN⁺]

Commentaires sur Hacker News

• Quand j’étais ado, dans un cours d’introduction à l’informatique dans un community college, nous avions conçu un simple jeu d’instructions CPU, puis créé nous-mêmes une machine virtuelle et un assembleur pour écrire et exécuter des programmes en assembleur.
  C’était étonnamment facile, et l’ordinateur m’a semblé beaucoup moins mystérieux.
  De la conception d’un vrai CPU pour FPGA jusqu’à l’écriture d’un petit système d’exploitation et des programmes qui tournent dessus, j’ai l’impression qu’on pourrait apprendre toutes les couches de l’informatique de cette manière.
  Si l’on met de côté les exigences de performance et de sécurité de l’informatique moderne, et que l’objectif est simplement « que ça fonctionne », ce domaine est étonnamment simple.

  • Ça ressemble à un cours amusant, et très proche de https://www.nand2tetris.org/ ou du livre Code de Charles Petzold.
  • Le moment où l’on passe d’un CPU imaginaire rudimentaire à un vrai CPU produit en série des débuts, comme le 80286, la complexité augmente brutalement.
    Si ma mémoire est bonne, il y a au minimum la segmentation mémoire, le mode protégé et une MMU.
  • Nous avions aussi un système de ce genre en cours de CS 101.
    C’était un petit ordinateur/assembleur écrit en BASIC sur PDP, et l’un des devoirs consistait à implémenter une multiplication simple en faisant des additions dans une boucle.
    Un ami a plutôt modifié le programme pour ajouter une nouvelle instruction MUL, et le professeur n’a pas du tout apprécié.
  • Les composants simples en eux-mêmes sont vraiment faciles, mais il y a des centaines de couches d’écart avant d’arriver à un résultat de niveau commercial que les vrais utilisateurs voient et manipulent sur un ordinateur.
    Quelqu’un de curieux et désireux d’apprendre peut facilement assimiler ces couches de base, mais ce n’est pas le cas de quelqu’un qui veut « gagner de l’argent rapidement et devenir employable le plus vite possible ».
  • Le cours nand2tetris semble faire exactement cela.

• Livres recommandés :

  1. Virtual Machines: Versatile Platforms for Systems and Processes, de Smith et Nair — cela ressemble à un ouvrage qui fait un tour d’horizon assez complet du sujet.
  2. Virtual Machines, de Iain Craig — cela semble être un livre plus pratique sur les langages et les machines virtuelles.
  3. Virtual Machine Design and Implementation in C/C++, de Bill Blunden — cela ressemble à un manuel pratique centré sur l’implémentation.
     Si quelqu’un a lu ces livres et peut ajouter un commentaire, ce serait utile à tout le monde.
  • Je ne suis pas sûr que ce sujet soit assez étroit pour être survolé dans un seul livre.
    Un émulateur Nintendo, un hyperviseur utilisant VT-x, un système d’exploitation multitâche traditionnel, l’interpréteur d’un nouveau langage de script, un optimiseur de requêtes SQL, un moteur d’expressions régulières, un moniteur de sécurité qui exécute du code de joueurs non fiables sur un serveur de jeu : tout cela semble partager très peu de considérations, mais ce sont tous des machines virtuelles.
    Il existe même une machine virtuelle à pile dans le format terminfo qui spécifie les séquences d’échappement des terminaux en cellules de caractères.
    Si l’on regarde en profondeur, ce qui fait qu’un ordinateur est un ordinateur au sens actuel, ce sont les machines virtuelles, et l’article de Turing de 1936 sur l’Entscheidungsproblem reposait lui aussi sur le fait que des machines virtuelles peuvent s’imiter mutuellement.

• Après avoir regardé la série de Ben Eater sur un CPU sur breadboard, je n’ai plus qu’une envie : concevoir et émuler un CPU moi-même.
  J’aimerais trouver le temps de m’asseoir et de le concevoir.

• Je pense que les architectures pédagogiques comme Brookshear Machine ou Little Computer ne ressemblent absolument pas aux architectures réelles, au point d’être non seulement inutiles mais nuisibles.
  J’ai vu des étudiants ayant suivi des cours qui utilisaient ce genre de choses comprendre les ordinateurs de façon encore plus déformée que des personnes n’ayant suivi aucun cours.
  Pour la plupart des gens qui veulent simplement comprendre un peu comment fonctionne leur ordinateur, un cours sur les systèmes d’exploitation est plus utile, et si l’on n’a le temps que pour un court tutoriel, je recommanderais « Writing my own bootloader ».
  https://dev.to/frosnerd/writing-my-own-boot-loader-3mld
  Cela ne veut pas dire que le tutoriel « Write your own VM » est mauvais, mais, d’après mon expérience, la plupart des personnes qui le suivraient tireraient davantage profit d’un autre sujet.

  • Je viens justement de faire LC-3, et dans mon projet actuel je compte utiliser LC-3 comme machine cible inadéquate pour apprendre un peu la recompilation dynamique.
    Peux-tu expliquer davantage pourquoi LC-3 est mauvais pour étudier l’architecture des ordinateurs ?
    Je comprends que ce soit complètement différent du matériel réel et trop simplifié, mais je me demande si c’est aussi mauvais du point de vue de l’écriture d’un émulateur de CPU.
  • Cela me rappelle l’ancien MIX de Knuth.
    C’était une machine décimale qui aurait pu être construite dans les années 1960, mais que plus personne n’a construite après les années 1970.
    Ce type de système peut enseigner beaucoup de bases, mais les techniques de https://en.wikipedia.org/wiki/Hacker%27s_Delight reposent surtout sur les représentations numériques courantes, ce qui les rend difficiles à apprendre dans ce contexte.
  • Je me demande ce qui te déplaît particulièrement dans LC-3.
    Comme je ne connais pas bien, j’ai rapidement regardé Wikipédia ; vu la BD, je m’attendais à quelque chose d’étrange, mais au premier abord cela ne m’a pas paru si choquant.
    On dirait un mélange de s/360, d’un peu de x86, et d’un tout petit peu d’ARM ou d’une autre architecture de type RISC ; il y a beaucoup d’omissions et de bizarreries, mais l’objectif semble être d’arriver rapidement à une implémentation fonctionnelle.
    J’aimerais savoir ce qui te fait dire que c’est « non seulement inutile mais nuisible » pour l’enseignement.
  • Je recommanderais d’utiliser de vieilles architectures 8 bits comme le 6502 ou le Z80.
    Dans beaucoup de cours d’informatique en Inde, il semble qu’on utilise encore le 8086/8088.
  • LC-3 a des modes d’adressage assez particuliers.
    Il permet notamment de faire un chargement doublement indirect via un mot relatif au PC placé au milieu.
    Malgré cela, la soustraction doit être construite à partir de la négation, et la négation doit être construite avec NOT et ADD ,,#-1.
    Vu l’espace limité d’encodage des instructions, NOT d,s = XOR d,s,#-1 aurait probablement été un meilleur usage.

• À proprement parler, ce n’est pas une machine virtuelle, mais un émulateur.
  Au sens descriptif, le terme peut s’appliquer, et avant l’ère de la virtualisation matérielle il y avait une certaine ambiguïté, mais aujourd’hui l’usage de loin le plus courant de « Virtual Machine » désigne un environnement qui utilise des fonctions de virtualisation matérielle comme VT-x.

  • Je ne suis pas d’accord pour dire que cet usage est « de loin le plus courant », et je ne pense pas non plus que ce soit une distinction parfaitement juste.
    La JVM est largement déployée, l’Ethereum VM est appelée EVM, https://www.linuxfoundation.org/hubfs/LF%20Research/The_Stat... décrit à plusieurs reprises BPF et eBPF comme des « virtual machines », et https://webassembly.org/ commence par : « WebAssembly (abrégé Wasm) est un format d’instructions binaires pour une machine virtuelle à pile ».
    « Machine virtuelle » reste le terme le plus courant pour désigner une machine virtuelle.
    Personnellement, je préfère des expressions comme « fictive machine », « fictious machine », « imaginary computer » ou « fantastic automaton », mais elles ont peu de chances d’être adoptées.
    On ne peut pas toujours employer « émulateur » à la place de « machine virtuelle ».
    On peut peut-être appeler wasmtime un émulateur, mais qualifier WebAssembly lui-même d’émulateur n’est pas exact : WebAssembly est la machine virtuelle que wasmtime émule.
    Il est aussi courant d’appeler un émulateur une machine virtuelle, et une instance d’émulateur en cours d’exécution est également une machine virtuelle dans un autre sens.
    Il est aussi légitime d’appeler « machine virtuelle » un environnement de virtualisation matérielle, et ce dernier sens recoupe dans une certaine mesure le précédent.
    Dans le contexte actuel, cet usage peut être de loin le plus courant, mais ce n’est pas forcément le cas ailleurs.
  • Avec tout le respect dû, j’ai du mal à être d’accord.
    Au sens le plus pur, une machine virtuelle n’est rien d’autre qu’un ordinateur fabriqué de toutes pièces, sans impliquer à quoi il servira ni comment il fonctionne.
    L’article prend bien l’émulation de consoles classiques comme exemple, mais il est clair qu’au regard de la définition proposée, les machines virtuelles possibles sont bien plus nombreuses.
    Le point essentiel est qu’une machine virtuelle est un concept abstrait, et qu’il en existe de très nombreux types.
    Simulateurs, émulateurs, hyperviseurs, etc. sont tous des machines virtuelles, et il existe aussi des formes étranges de machines virtuelles qui n’ont pas encore reçu de nom.
    Je ne cherche pas à être désagréable ; au contraire, c’est par respect, et parce que je veux clarifier ce terme pour les personnes qui apprennent.
  • Je pense que la distinction que vous défendez n’existe pas vraiment.
    « Machine virtuelle » est couramment employé pour tout logiciel qui exécute du langage machine ou du bytecode, quelle qu’en soit la raison.
    Cela peut inclure la virtualisation, mais le terme est aussi souvent utilisé pour des runtimes de langage, comme la JVM de Java ou YARV de Ruby (Yet Another Ruby VM).
    Le domaine où l’on entend plutôt moins souvent ce terme est justement l’émulation, en partie parce que la plupart des émulateurs modernes tendent à recourir à la recompilation dynamique du logiciel cible plutôt qu’à émuler un système complet.
  • Ici, il s’agit d’une VM au sens de la JVM, c’est-à-dire la Java Virtual Machine.
    Java est sans doute suffisamment répandu pour relever de l’« usage de loin le plus courant ».