Building a Java Virtual Machine in Rust: A Deep Dive

[00:00:00]I have written jvm in Rust Andre you son of a I'm in all right lately I've been spending quite a bit of time learning rust and as any sane person would do after writing a few hundred lines of programs or a few hundred lines programs I've decided to take on something a little bit more ambitious I have written a Java virtual machine in Rust yeah with a lot of originality and called it rjvm the code is available on GitHub oh dear oh oh yes oh yes oh I want all of this I want to stress that this is my toy jvm built for learning uh purposes and not serious implementation in particular it does not support generics threads Reflections annotations IO just in time compiler string and turning pretty good okay still pretty good however there are quite a few non-trivial things to implement control flow statements yep uh primitive and object Creations a virtual and static method invocation exceptions garbage collection Class A resolution from a jar file this last one is insane effing jar files effing class resolution effing Java for example the following uh is part of a test Suite class stack Trace printing public static void main all right throw a ball new exception stack elements get all these ones okay print all these things okay yeah print step okay it uses a real rt.jar containing the class from open jdk7 thus in the example above the Java Lang stack Trace element comes from the real jdk I'm very happy oh my goodness I'm very happy with what I've learned about Ruston about how to implement a virtual machine in particular I'm super happy about having implemented a real working garbage collector it's quite mediocre but it's mine and I love it I love this mentality by the way this guy is just a champ Andre champ status right here given that I have achieved what I have set out to do originally I've decided to stop the project here I know there are bugs but I do not plan to fix them love it I love everything I'm hearing about I love everything here in this post I will give you an overview of how my jvm Works in further articles I will go into more detail about some of the aspects discussed here okay code organization uh the code is a standard rust project I've split into three crates a reader which reads the dot class files okay VM which contains the virtual machine that can execute code as a library nice and Vim CLE which contains the very simple command line launcher for the uh to run the VM in the spirit of java executable okay good I'm considering extracting the reader crate in a separate repository and Publishing it on crates i o since it could actually be useful to someone else yeah it could be parsing a class file interesting as you know Java's compiled language the Java C compile takes your dot Java source and produces uh various dot class files uh generally distributed in a DOT jar file which is just a zip oh really jar is just zip I thought I knew that I feel like I knew that thus the first thing to do is execute some Java code is to load the dot class file containing the byte code generated by the compiler a class file contains the various things metadata about the class such as its name or the source file name the super class name what the hell is a super class name I know what a superclass is uh and the implementing interfaces the implemented interfaces the fields along with their types and annotations methods with their descriptor which is a string representing the type of each parameter and the method's return metadata such as the throw Clauses annotations generic information is the byte code along with some extra metadata such as exception Handler table and the line numbers table as mentioned above for rjvm I have created a separate crate named reader which can parse the class file and return a rust struct that models the class and all of its content let's look at that struct really quickly look at that look at that look at that beauty oh yeah nice job using format nice job I like it oh this is great this is great uh maybe toss in like an into I think an into could be pretty cool right here so that way you could take like maybe a path buff and just call into and you could just into I love those kind of things personally it makes me feel pretty happy you know what I mean have you ever had have you ever done those they always make me really happy uh in twos I don't know why this is good well done well done beautiful um pretty good pretty pretty code all right executing a methods the main API of the VM crate is VM invoke which is used to execute a method it takes a call stack which contains the various call frame one for each method being executed for executing main the call stack will initially be empty and a new frame will be created to run it okay then each function invocation will add a new frame to the call stack okay cool when a method's execution completes its corresponding frame will be dropped and then removed from the call stack awesome uh most methods will be implemented in Java and thus their bytecode will be executed however rjvm all supports native methods IE methods that are implemented directly by the jvm and not in the Java byte code oh there's quite a few of them in the lower parts of the Java API where the interaction of the operating system for example to do i o or the support runtime if Nest or is necessary some examples of let's say of the latter you might have seen included in this okay this makes sense array copy yeah yeah yeah okay that all makes sense these are implemented by the rust by rust functions oh cool okay cool this is actually really interesting uh the jvm is a stack based virtual machine I.E the bytecode instructions operate mainly on value stack there is also a set of local variables identified by index that can be used to store values and pass arguments to methods these are associated with each call frame okay that makes sense you have all your variables all the information you need per call frame to do this okay modeling values and objects the value of models and possibly value of the local variable stack element or object Fields is also implemented as follows uh we got a nice enum value uninitialized I love the named I love these all named abstract objects nice null classic ethanol nice if you look here we have uninitialized and we have null it's almost like we have undefined and null this is fantastic okay but it should never be on there okay I see that how long can I use this in Microsoft soon soon you'll be able to finally run rust with jvm everybody's favorite thing ever as an aside this is one place where a some type such as Russ enum is a wonderful abstraction it is great for expressing the fact that a value might be of multiple different types absolutely heterogeneous lists are just like so common in programming I'm shocked that we still use what we use today for storing objects and their values I initially used a simple struct object containing a reference to the class the object or the model uh to model the object's type and a VEC value for storing the field however when I implemented the garbage collector I modified this to use lower level implementation with a ton of pointers and casts quite C style in the current implementation and Abstract object with models a real object or an array is simply a pointer to an array of bytes which contains a couple headers words and then the field values beautiful oh I love this oh that's fantastic that's kind of similar to how JavaScript core used to do it I'm not sure what they do now but there was something very very similar to this right it's just like in the end it's just like a little array buffer underneath the hood in which you put a bunch of stuff into and you just offset into it to read these fields right that's all it really is in the end is this ruscript no this is Java in Rust uh you're gonna do you gotta have Java but instead of having the a different run time you have you have a rust run time so why would you want that well it's written in Rust primary feature okay executing instructions executing a method means executing its bytecode instructions one at a time the jvm has a wide list of instructions over 200 encoded uh by one byte in the byte code many instructions are followed by arguments and some have the variable length this is modeled in the code uh type of instruction okay standard stuff right that makes all sense uh you just have all these instructions come in each thing has to do something it's just a big I mean it's just a loop with a switch in it effectively uh the execution the method will keep as mentioned above a stack and an array of local variables referred by the instruction by their index it will also initialize a program counter to zero that is the address of the next instruction to execute the instruction will be processed in the program counter updated okay beautiful this is awesome generally Advanced by one uh and various jump instructions can move to different locations remember if you did if you did Advent of code I think it was like 2019 Maybe in 2019 um 2019 did this exact thing right where uh in Advent of code where you did like an INT computer you built like a really sweet in computer okay everyone is saying there's something amazing how to get sued by Oracle and the rust Foundation at the same time this is a great name I will consider it how to get sued by Oracle and the rust Foundation at the same time this is beautiful um a special family of instructions uh is made of those that can invoke another method there are various ways of resolving which method should be invoked virtual or static look up uh are the main ones but there are others after resolving the correct instructions rjvm will add a new frame to the call stack and start the methods execution the methods return value will be pushed onto the uh stack unless the uh it is void yep okay so if you're not familiar with the call frame this sounds like just like what a call frame would do you have to make memory for both the return value and the return uh address all that kind of stuff the Java byte code format is quite interesting and I plan to dedicate a post okay cool exceptions exceptions are quite complex beasts to implement since they break normal control flow geez that's weird so they're both hard to program and hard to make shocking shocking that crazy ass control flow is hard to make and might return early from a method and propagate on the call stack I'm pretty happy with the way I've implemented them though and I'm going to show you some of the relevant code the first thing you know is that any catch block corresponds to an entry of the methods exception table each entry contains a range of covered program counters the address for the first instruction in the catch block the exceptions class name which the block catches oh very interesting so the signature call frame execute instructions as follows okay because yeah that's right because you can catch only specific kind of Errors so you may not like your first catch may not catch everything so you may need to go to the next catch Wild Wild just absolutely wild all right this is great this is great uh and the standard rest result type is this perfect thus let's see executing an instruction can result in four possible States the instruction was executed successfully in the execution of the current method can continue the ins the instruction was executed successfully and its return instruction thus the current method should return with potentially a return value okay instruction uh could not be executed because some internal VM error happened or the instruction could not execute because the standard Java exception was thrown the code that executes a method thus follows all right we got a call frame do this Loop let instruction okay there's our little program counter new addresses uh let's see let this thing oh my goodness VM error look at this beautiful look at that beauty instruction new address okay debug status print instruction move the program counter to the next instruction before executing it since we want to go to to override this absolutely go to would be like a break statement with a name a continue something like that because that's all those things are they're just named go-to's uh instruction result self uh oh I would do this okay I mean all this looks great I'm sorry or congratulations wait is this Java without garbage collection no this is Java with garbage collection it's just that the the VM is written in Rust it's actually how to get sued by Oracle and rust Foundation at the same time a menage a12 lawyering uh I know that there are quite a few implementation details in this code but I hope it gives you an idea of how rust result and pattern matching Maps really well to the description Behavior above yeah it's good code especially since he's only a few hundred lines into rust he must this guy must be pretty familiar with pattern matching and stuff like that to go this far this fast all right so this is the part that I'm really excited about right here garbage collection the final milestone in rjvm has been implementing the garbage collector the algorithm I have chosen is a stop the world which is trivially follows from not having threads uh let's see semi space uh copying collector I have implemented a poor variant of Cheney's algorithm but I really should go and implement the real thing the idea is to split the available memory into two parts called semi-spaces one will be active and used to allocate objects and the other will be unused when full uh when full a garbage collection will be triggered all of the alive objects will be copied into a another semi space okay then all references to the objects will be updated so that they point to new copies holy cow expensive finally the role of the two will be swapped similar to how blue green deployments work yep GC root so if you don't know there's these objects called GC root objects that's how you start the tree and so there's like a bunch of them and so it has to go through all of the roots and follow the tree everywhere and once it finds everything that it can touch then it's like great and so then those are the ones that stay copy pasta phase yep see there's this okay get them all in there for references boom and then you can get rid of that swap rolls there you go this algorithm has the following characteristic obviously it wastes a lot of memory yep allocations are super fast bumping a pointer absolutely copying and compacting objects means it does not have to deal with memory fragmentation absolutely so that's really good because memory fragmentation is super hard compacting objects can improve performance due to better cache line utilization okay real Java VMS are far more sophisticated algorithms generally a generational garbage collectors yep such as G1 or the parallel GC which uses evolutions of the copying strategy very cool yeah conclusions uh writing rjvm I learned a lot and I have a lot of fun I can't ask for more of a from a side project but maybe next time I'll pick something a bit less ambitious to learn new programming language I'm actually shocked honestly can we all agree that the real W here is that you wrote an excessively complicated program in Rust after just maybe a thousand two thousand lines of code wow beautiful like that's incredible well done and aside I want to say that I had a lot of fun with rust I think is generally a great language as I've written let's see have I written before I really enjoyed using it for implementing my jvm if you're interested in further details all right go check it out he'll have some more posts coming I'll make sure I link this article it is fantastic well done beautiful stuff he uses rust by the way his jvm uses rust by the way the name is jar is actually just a zip file again