Une JVM écrite en Rust

 (andreabergia.com)
3 points par GN⁺ 2023-07-22 | 1 commentaires | Partager sur WhatsApp
  • rjvm, un projet annexe créé pour apprendre Rust, est une JVM jouet à but pédagogique, mais elle va jusqu'à lire de vrais fichiers .class et jar et à exécuter du bytecode Java
  • Les fonctionnalités non prises en charge sont les threads, la réflexion, les annotations, les E/S, le compilateur JIT et l'interning des chaînes, mais elle inclut le contrôle de flux, la création d'objets, les appels de méthodes, les exceptions et le garbage collection
  • Les exemples utilisent le véritable rt.jar d'OpenJDK 7, ce qui permet de charger depuis le vrai JDK des classes comme java.lang.StackTraceElement
  • Le code est divisé en trois crates Rust, reader, vm et vm_cli, qui couvrent l'analyse des .class, la pile d'appels, les méthodes natives ainsi que la modélisation des valeurs et des objets
  • Le dernier jalon a été un stop-the-world semispace copying collector et, l'objectif atteint, le projet est arrêté sans correctifs prévus pour les bugs connus

rjvm, une JVM Rust à but pédagogique

  • rjvm est une machine virtuelle Java jouet créée pour apprendre Rust
  • Le code est disponible sur GitHub
  • Il s'agit moins d'une implémentation sérieuse de JVM que d'un projet d'apprentissage, et les fonctionnalités suivantes ne sont donc pas prises en charge
    • threads
    • réflexion
    • annotations
    • E/S
    • compilateur JIT
    • interning des chaînes
  • Les génériques figuraient au départ dans la liste des fonctionnalités non prises en charge, mais ils fonctionnent en réalité

Jusqu'où l'implémentation va-t-elle ?

  • rjvm ne se limite pas à un simple parseur et implémente directement plusieurs comportements de la JVM
    • le contrôle de flux comme if et for
    • les types primitifs et la création d'objets
    • les appels de méthodes virtuelles et statiques
    • la gestion des exceptions
    • le garbage collection
    • la résolution de classes à partir de fichiers jar
  • Le code de test inclut des exemples utilisant Throwable, Exception et StackTraceElement
  • Comme il n'y a pas de véritables E/S, une méthode native appelée tempPrint est utilisée à la place de System.out.println
  • Les exemples s'appuient sur le véritable rt.jar d'OpenJDK 7 et java.lang.StackTraceElement est lui aussi récupéré depuis le vrai JDK

Trois crates Rust

  • Le projet suit la structure standard d'un projet Rust et se compose de trois crates
    • reader : contient les types qui lisent les fichiers .class et modélisent leur contenu
    • vm : fournit sous forme de bibliothèque une machine virtuelle capable d'exécuter le code
    • vm_cli : contient un lanceur en ligne de commande simple, comparable à l'exécutable java
  • La possibilité de séparer la crate reader dans un dépôt distinct pour la publier sur crates.io est à l'étude

Analyse des fichiers .class

  • Le code Java est compilé par javac en fichiers .class, puis généralement distribué dans des fichiers .jar, qui sont au format zip
  • Pour exécuter du code Java, il faut d'abord charger les fichiers .class contenant le bytecode produit par le compilateur
  • Les fichiers de classe embarquent aussi les informations nécessaires à l'exécution et à la résolution des types
    • des métadonnées comme le nom de la classe et celui du fichier source
    • le nom de la superclasse
    • les interfaces implémentées
    • les champs, leurs types et les annotations
    • les descripteurs de méthode, les clauses throws, les annotations et les informations génériques
    • le bytecode, la table des gestionnaires d'exception et la table des numéros de ligne
  • La crate reader analyse les fichiers de classe et renvoie une struct Rust qui modélise la classe et son contenu

Exécution des méthodes et pile d'appels

  • L'API principale de la crate vm est Vm::invoke, utilisée pour exécuter des méthodes
  • Chaque méthode en cours d'exécution possède une CallFrame dans une CallStack
  • Lors de l'exécution de main, la pile d'appels est initialement vide, puis une nouvelle frame est créée pour lancer l'exécution
  • À chaque appel de fonction, une nouvelle frame est ajoutée à la pile d'appels, puis supprimée quand l'exécution de la méthode se termine
  • La plupart des méthodes sont implémentées en bytecode Java, mais rjvm prend aussi en charge les méthodes natives
    • une méthode native n'est pas implémentée en bytecode Java, mais directement par la JVM elle-même
    • on peut citer System::currentTimeMillis, System::arraycopy et Throwable::fillInStackTrace
    • dans rjvm, elles sont implémentées sous forme de fonctions Rust
  • La JVM est une machine virtuelle à pile, si bien que les instructions de bytecode opèrent principalement sur la pile de valeurs
  • Chaque frame d'appel est associée à une pile de valeurs et à un ensemble de variables locales identifiées par index

Modélisation des valeurs et des objets

  • Value modélise les valeurs pouvant être stockées dans les variables locales, les éléments de pile et les champs d'objet
  • Value est implémenté comme un enum Rust et comprend les états suivants
    • Uninitialized
    • Int(i32)
    • Long(i64)
    • Float(f32)
    • Double(f64)
    • Object(AbstractObject<'a>)
    • Null
  • Les types somme comme les enum de Rust conviennent bien pour représenter le fait qu'une valeur peut appartenir à plusieurs types possibles
  • Le stockage des objets a d'abord reposé sur une struct Object simple, fondée sur Vec<Value>, contenant une référence de classe et les valeurs des champs
  • Après l'implémentation du garbage collector, cela a évolué vers une implémentation de plus bas niveau qui utilise davantage de pointeurs et de cast
  • Actuellement, AbstractObject modélise un véritable objet ou un tableau, sous la forme d'un pointeur vers un tableau d'octets contenant quelques mots d'en-tête et les valeurs de champs

Exécution des instructions de bytecode

  • L'exécution d'une méthode consiste à traiter les instructions de bytecode une par une
  • La JVM compte plus de 200 instructions, encodées sur 1 octet dans le bytecode
  • Beaucoup d'instructions sont suivies d'arguments, et certaines ont une longueur variable
  • rjvm modélise les instructions de bytecode Java avec le type Instruction
  • Lors de l'exécution d'une méthode, la pile de valeurs et le tableau de variables locales sont maintenus, et le compteur ordinal indiquant l'adresse de la prochaine instruction à exécuter est initialisé à 0
  • En général, après l'exécution d'une instruction, le compteur ordinal avance vers l'instruction suivante, mais les instructions de saut peuvent le faire pointer ailleurs
  • Les instructions de saut servent à implémenter des structures de contrôle de flux comme if, for et while
  • Il existe aussi une famille distincte d'instructions pour appeler d'autres méthodes
    • le choix de la méthode à appeler peut reposer sur une résolution virtuelle ou statique, entre autres
    • après résolution de la méthode cible, une nouvelle frame est ajoutée à la pile d'appels et l'exécution démarre
    • si la valeur de retour n'est pas void, elle est push sur la pile et l'exécution reprend

Gestion des exceptions

  • Les exceptions cassent le flux de contrôle normal, provoquent un retour anticipé depuis une méthode et peuvent se propager le long de la pile d'appels, ce qui complique leur implémentation
  • Chaque bloc catch correspond à une entrée de la table des exceptions de la méthode
  • Une entrée de cette table contient les informations nécessaires pour trouver le gestionnaire adéquat
    • la plage de compteurs ordinaux à laquelle elle s'applique
    • l'adresse de la première instruction du bloc catch
    • le nom de la classe d'exception attrapée par ce bloc
  • CallFrame::execute_instruction utilise Result de Rust pour représenter le résultat d'exécution d'une instruction
  • Le résultat d'exécution d'une instruction se divise en quatre états
    • succès et poursuite de l'exécution de la méthode courante
    • succès avec instruction return, ce qui termine la méthode courante avec une valeur de retour
    • échec de l'exécution à cause d'une erreur interne de la VM
    • échec de l'exécution parce qu'une exception Java a été levée
  • La boucle d'exécution d'une méthode analyse l'instruction, avance le compteur ordinal vers l'adresse suivante, puis exécute l'instruction
  • En cas d'exception, elle cherche un gestionnaire adapté à la position de l'instruction courante
    • s'il n'y a pas de gestionnaire, l'exception est propagée à l'appelant
    • s'il y en a un, l'objet d'exception est de nouveau push sur la pile et l'exécution reprend à l'emplacement du gestionnaire catch
  • Result et le pattern matching de Rust se prêtent bien à la représentation de ce comportement dans la structure du code

Garbage collection

  • Le dernier grand jalon de rjvm a été l'implémentation du garbage collector
  • L'algorithme retenu est un stop-the-world semispace copying collector
  • En l'absence de threads, l'approche stop-the-world s'impose naturellement
  • L'implémentation est une variante plus simple de l'algorithme de Cheney, et le code se trouve dans gc.rs
  • Cette approche divise la mémoire disponible en deux semispaces
    • l'un sert de zone active pour allouer les objets
    • l'autre reste inutilisé
    • quand la zone active est pleine, les objets encore vivants sont copiés dans l'autre semispace
    • toutes les références d'objet sont mises à jour pour pointer vers les nouvelles copies
    • les rôles des deux semispaces sont ensuite échangés
  • Cette procédure est comparée à une logique semblable au blue-green deployment
  • Les avantages et inconvénients de l'algorithme sont très nets
    • il entraîne un gaspillage mémoire important, puisqu'on ne peut pas utiliser jusqu'à la moitié de la mémoire maximale
    • l'allocation est très rapide, car elle consiste à incrémenter un pointeur
    • comme il copie et compacte les objets, il n'a pas à gérer la fragmentation mémoire
    • la compaction des objets peut améliorer les performances grâce à une meilleure utilisation des lignes de cache
  • Les véritables VM Java utilisent généralement des garbage collectors générationnels plus sophistiqués, comme G1 ou parallel GC

Le point final du projet

  • La création de rjvm a permis d'apprendre beaucoup de choses sur Rust et sur l'implémentation de machines virtuelles, avec une satisfaction particulière d'avoir réalisé un garbage collector réellement fonctionnel
  • Le garbage collector n'est pas particulièrement abouti, mais il fonctionne réellement
  • L'objectif initial ayant été atteint, le projet s'arrête ici
  • Des bugs connus subsistent, mais il n'est pas prévu de les corriger
  • Rust a été un langage agréable à utiliser pour implémenter une JVM, et de futurs billets détailleront davantage l'implémentation de rjvm et le fonctionnement de la JVM

À lire aussi

1 commentaires

 
GN⁺ 2023-07-22
Commentaires sur Hacker News

  • La partie difficile de l’implémentation d’un ramasse-miettes consiste à vérifier que toutes les références sont correctement prises comme racines, surtout avec un collecteur compactant
    La méthode do_garbage_collection est marquée unsafe[1], mais il n’y a aucune explication sur ce que l’appelant doit garantir pour l’invoquer de manière sûre
    Je me demande comment est garanti le fait que toutes les références vers le tas sont bien prises comme racines, et ce n’est pas un problème anodin[2][3][4]
    J’ai aussi cloné le dépôt et exécuté cargo test, et tous les tests échouent avec l’erreur should be able to add entries to the classpath: InvalidEntry(".../vm/rt.jar") : vm/tests/integration/real_code_tests.rs:15:10
    [1] https://github.com/andreabergia/rjvm/blob/be9c54066c64a82879...
    [2] https://manishearth.github.io/blog/2021/04/05/a-tour-of-safe...
    [3] https://without.boats/blog/shifgrethor-iii/
    [4] https://coredumped.dev/2022/04/11/implementing-a-safe-garbag...

    • Cette VM maintient sa propre pile d’appels virtuelle au lieu d’utiliser la pile d’appels native, donc c’est assez direct
      On peut donc parcourir cette pile pour trouver les paramètres et les variables locales à utiliser comme racines
      Cette approche a un coût en performances, mais le traçage du ramasse-miettes devient bien plus simple, et cela facilite aussi l’implémentation de primitives de concurrence et de contrôle de flux comme les coroutines ou les continuations
    • Un ramasse-miettes, au fond, c’est surtout de la comptabilité rigoureuse, donc c’est plutôt simple ; mais dès qu’on se lance dans le ramasse-miettes concurrent, cela devient infernalement difficile

  • Beau projet, félicitations
    Cela dit, la partie « non pris en charge : génériques » me semble un peu étrange
    Je me demande dans quel sens la JVM devrait prendre en charge les génériques
    Au niveau du bytecode, à cause de l’effacement de types, ne peut-on pas simplement considérer que tout est Object, donc un type référence ? Ou bien s’agit-il du parseur de définition de classe ? Même dans ce cas, à part la syntaxe de base, il ne semble pas y avoir de logique qui vérifie la validité des fichiers de classe

    • Le même point a aussi été soulevé sur reddit à propos des génériques, et c’est juste
      En pratique, il suffit essentiellement de lire l’attribut Signature qui contient les informations génériques des classes, méthodes et champs (https://docs.oracle.com/javase/specs/jvms/se7/html/jvms-4.ht...)
      Je viens justement de tester, et le code ci-dessous fonctionne aussi :-)
      public class Generic { public static void main(String[] args) { List strings = new ArrayList(10); strings.add("hey"); strings.add("hackernews"); for (String s : strings) { tempPrint(s); } } private static native void tempPrint(String value); }
    • Il s’agit peut-être de l’opération checkcast : https://docs.oracle.com/javase/specs/jvms/se8/html/jvms-6.ht...
      Par exemple, elle est générée si on écrit du code comme final Main value = list.get(0);
      http://henrikeichenhardt.blogspot.com/2013/05/how-are-java-g...
    • C’est globalement exact. Les génériques ont parfois un effet sur la réflexion, mais la réflexion non plus n’est pas prise en charge, et de manière générale ils sont remplacés à la compilation par la classe ou l’interface la plus proche
      En revanche, l’absence d’internement des chaînes est très étrange. Son implémentation est plutôt triviale, et sans cela on a du mal à parler d’une JVM
      Le fait que les chaînes deviennent égales par référence est important, et cela fait partie du JLS
      L’absence de threads ramène l’ensemble de la tentative au niveau d’un projet jouet

  • Vraiment impressionnant. Quand j’ai rejoint le projet Java en 1992, il s’appelait encore Oak, et le groupe dans lequel j’étais envisageait d’écrire un système d’exploitation complet en Java
    L’idée était de réduire la surface d’attaque d’un système d’exploitation embarqué en ne laissant en « langage machine », c’est-à-dire en méthodes natives, que le strict minimum nécessaire
    À l’origine, Java visait à fonctionner sur des téléviseurs ou de l’électroménager, et à l’époque les méthodes natives étaient écrites en C, pas en Rust
    Un JVM écrit en Rust apporte une sécurité mémoire assez forte à l’ensemble du processus

    • Personnellement, je pense qu’Android a en partie atteint cet objectif
      Une grande partie de la logique de l’OS est écrite en Java ou Kotlin, tout en mélangeant aussi beaucoup de services système en code natif, reliés entre eux par le Binder IPC, célèbre ou tristement célèbre
    • Cette idée a clairement été tentée plusieurs fois [0, 1]
      [0] - https://en.wikipedia.org/wiki/Singularity_(operating_system)
      [1] - https://en.wikipedia.org/wiki/Midori_(operating_system)
    • Pendant un temps, il me semble qu’il y a eu JavaOS, même si ce n’était pas destiné aux utilisateurs : https://en.wikipedia.org/wiki/JavaOS
    • En plus des commentaires frères, il y a aussi SavageJE, microEJ, les runtimes Java bare metal de PTC et Aonix, ainsi que SquawkVM de SunSPOT

  • Il y a aussi une implémentation de JVM 17 écrite en Go qui vaut le détour : https://jacobin.org/

    • Il existe également un JVM implémenté en Scala, lui-même exécuté sur la JVM : https://github.com/lihaoyi/Metascala
    • C’est un nom assez intéressant pour un projet de programmation
      Les Jacobins étaient un club politique révolutionnaire de la Révolution française des années 1790, et c’est aussi le nom du magazine sur https://jacobin.com

  • Je me demande s’ils ont atteint une limite à cause du paramètre de durée de vie dans cette signature
    fn execute_instruction(&mut self, vm: &mut Vm<'a>, call_stack: &mut CallStack<'a>, instruction: Instruction) -> Result, MethodCallFailed<'a>>
    Si on ajoute une durée de vie à la variante Err de Result et que cette durée de vie est invariante, comme cela semble être le cas ici à cause de vm et call_stack, on ne peut généralement plus utiliser l’opérateur ? ni les retours anticipés[1]
    Le traitement des erreurs devient alors plus verbeux et plus difficile à lire ; je me demande si ça a été leur expérience en pratique
    [1] https://users.rust-lang.org/t/nll-and-early-return-not-allow...

  • C’est un excellent projet d’apprentissage, et c’est agréable de voir que l’auteur s’amuse
    Implémenter une VM from scratch est vraiment plaisant, et j’ai énormément appris en faisant ce genre de travail par le passé
    S’ils veulent essayer d’y ajouter un garbage collector, MMTk peut valoir le coup d’œil (https://www.mmtk.io/)
    Il propose des algorithmes de collecte de haute qualité conçus pour être branchés sur différentes VM, et il est écrit en Rust

    • À noter que MMTK est réservé au x86
      J’avais envisagé de l’utiliser pour un projet perso, puis j’ai abandonné parce que j’étais sur Mac

  • Très bien réalisé
    Construire une VM est toujours amusant, et combiné au système de types de Rust, cela a dû être une expérience d’apprentissage intéressante
    Si tu cherches un poste, tu peux me contacter sur Twitter, Mastodon ou via l’e-mail de mon entreprise. Avec l’ID utilisateur ici, tu devrais pouvoir me retrouver

  • Quand je vois ce genre de projet génial, je me sens complètement dépassé.
    J’aimerais bien que l’auteur explique comment commencer avec Rust et jusqu’à quel niveau il faut maîtriser les bases pour tenter quelque chose comme ça.

    • Je ressens la même chose.
      Sans vouloir trop partir hors sujet, je me bats pas mal avec ce sentiment en ce moment.
      Je travaille comme développeur logiciel professionnel depuis presque 10 ans, et vu mon poste actuel et ma capacité réelle à livrer des produits, je sais que je suis compétent et que je ne suis pas un faux développeur.
      Pourtant, quand je lis des blogs de développeurs ces temps-ci, je me sens submergé, comme si je n’en savais pas assez et que je n’étais pas un « vrai » développeur.
      J’ai l’impression que ce sentiment vient du fait que je me construis une image idéale du développeur et que je me compare à cet étalon imaginaire.
      J’admire les gens qui ont des connaissances profondes et qui s’expriment avec clarté et concision, mais ça me fait aussi me demander pourquoi je ne suis pas comme eux.
      Une fois la journée de travail finie et la famille prise en charge, il ne me reste presque plus d’énergie pour faire quoi que ce soit de plus, et même si je sais que la programmation ne fait pas tout, j’ai quand même envie d’apprendre davantage et de progresser.
      Je sais que ce n’est ni sain ni rationnel, mais c’est un sentiment dont j’ai du mal à me défaire en ce moment.
    • Honnêtement, à chaque fois que j’ouvre HN, je ressens à moitié le syndrome de l’imposteur.
      J’avais un peu d’expérience avec les VM avant, et j’ai même écrit une courte série d’articles sur mon blog il y a quelques années.
      Dans un emploi précédent, j’avais aussi un peu bricolé du bytecode JVM pour résoudre un problème très particulier chez un client.
      J’ai aussi lu l’excellent https://craftinginterpreters.com/ il y a quelques années, et ça m’a donné des idées.
      Mais ce projet était clairement gros et complexe.
      Ça a pris beaucoup de temps, et comme beaucoup de mes side projects, il a été laissé de côté plusieurs fois, mais je suis content de l’avoir terminé :-)
    • Je ne suis pas expert Rust et je ne suis pas non plus l’auteur d’origine, mais je peux prendre l’exemple d’une autre technologie, les sockets.
      Je m’y suis plongé récemment, et il y a encore deux semaines, je n’en avais qu’une compréhension de haut niveau, acquise en lisant rapidement des pages de manuel, de la documentation, des billets de blog, etc.
      Je voulais comprendre les bases du réseau, donc j’ai décidé de lire autant que possible et, une semaine plus tard, j’en avais appris assez pour écrire du code socket en Python et en C.
      Comme je connais déjà assez bien Python, le fait d’explorer le sujet en profondeur m’a ensuite permis de beaucoup mieux comprendre la bibliothèque sockets.
      Si vous voulez devenir meilleur dans la technologie A avec le langage X, je vous conseille de lire ou regarder autant de choses que possible sur la technologie A, puis de construire quelque chose avec le langage Y.
      Ensuite, quand vous revenez au langage X, vous êtes déjà bien familiarisé avec les concepts autour de la technologie A.
    • Il faut simplement découper le problème en petites parties.
      Une VM de langage simple aura sans doute une représentation des objets en mémoire, un interpréteur de bytecode, un ramasse-miettes simple et un chargeur.
      L’interpréteur de bytecode peut se voir comme une pile, une manière de représenter les fonctions sur cette pile, et une boucle qui interprète chaque bytecode et fait avancer le compteur ordinal.
    • Ce qui compte, c’est combien de temps vous passez à coder pendant votre temps libre. En moyenne, combien d’heures par semaine ?
      Si c’est 0 heure, ce n’est évidemment pas condamnable et vous avez sûrement d’autres priorités, mais il n’y a rien d’étonnant à ce qu’une personne qui consacre en moyenne 10 à 20 heures par semaine à des side projects pendant des années produise quelque chose d’impressionnant.

  • Puisque j’en suis à faire un peu de promo sans vergogne pour un projet similaire : https://github.com/tenaf0/rust-jvm3

  • Je suis en train de créer un système d’exploitation gratuit pour clone AT 386(486). C’est juste un hobby, rien d’aussi gros ni professionnel que gnu :-)

    • Il existe un tutoriel no-std pour écrire un noyau de démonstration en Rust : https://os.phil-opp.com
      osdev.org, sandpile.org, RBIL et freevga valent aussi le détour.
      Le plus gros casse-tête, c’est le support matériel.
      Il existe aussi beaucoup de bons vieux livres papier remplis de recettes sur des sujets comme les entrées/sorties par port fiables ou des astuces matérielles non documentées.
      Intel® 64 and IA-32 Architectures Software Developer’s Manual Combined Volumes: 1, 2A, 2B, 2C, 2D, 3A, 3B, 3C, 3D, and 4
      Microsoft MS-DOS Programmer's Reference, avec aussi les appels BIOS en mode réel
      PC Interrupts
      Undocumented PC
      PC Intern
      Programmer's Guide To The EGA, VGA, And Super VGA Cards
      Graphics Programming Black Book Special Edition
      Cela vaut aussi la peine d’expérimenter les progrès du développement des systèmes d’exploitation après l’ère des noyaux monolithiques, micro-noyaux et hybrides.
      Les structures fondées sur les capabilities comme seL4 ont plusieurs avantages intrinsèques en matière de performances et de sécurité, notamment les capabilities et un excellent IPC.
      Une couche de compatibilité POSIX est également importante. Même un système d’exploitation embarqué sans notion de threads ni de processus peut implémenter POSIX.
      Un hyperviseur est bien plus facile à ajouter si Intel VT-[xd] est disponible, et sinon on peut revenir à l’émulation. L’émulation par traduction est très performante.
      Il faut savoir généraliser et accélérer les gestionnaires d’interruptions, éviter les situations de concurrence et bien maîtriser les patterns lock-free.
      Il faut aussi réécrire ou intercepter les instructions non prises en charge, y compris x87 et MMX.
      Si le micro-noyau pur a échoué, c’est parce que la complexité de l’ordonnancement et de la gestion transactionnelle de multiples ressources a augmenté.
      L’architecture micro-noyau a en théorie de grands avantages en matière de sécurité et d’exploitation, mais elle ne s’est pas largement imposée sous sa forme pure.