7 ms·

Writing a register based VM in less than 125 lines of C code

291 points by nomemory 5y ago

nomemory 5y ago
The article is in early draft, so there might be some errors and/or bugs.
- Zababa 5y ago
  I haven't read the whole article yet, I just want to report what seems to be a small error: > The code is written in C11, and it will probably compile on most operating systems. The repo can be found here, and the exact source code is vm.c: The link on "here" is broken, it's https://github.com/,nomemory/lc3-vm https://github.com/,nomemory/lc3-vm (with a comma before your github username) instead of (I think) https://github.com/nomemory/lc3-vm https://github.com/nomemory/lc3-vm.
  - nomemory 5y ago
    Thanks for spotting this. I will fix it as soon as I am back to my personal computer.
garbagecoder 5y ago
This looks like a fun thing to mess with and lose sleep while I play with! Thank you!
- nomemory 5y ago
  Next step is to compile brainfuck to this.
emmanueloga_ 5y ago
Skimmed over this... nice write up so far! Notes: * Would be nice to have a TOC for such a long article. * I never implemented a register based VM but I think I remember one of the trickiest things is to allocate the registers when compiling from a higher level language [1], which I don't think is mentioned in the article? I think the article doesn't concern with this since the sample program just uses the bytecode directly. * Random: been thinking of a DSL that would be able to express a VM logic without having to deal with all the micro details of C... Just found a few academic papers on a quick search investigating the idea, fwiw. [2] [3] 1: https://en.wikipedia.org/wiki/Register_allocation https://en.wikipedia.org/wiki/Register_allocation 2: https://link.springer.com/chapter/10.1007/978-3-540-25935-0_12 https://link.springer.com/chapter/10.1007/978-3-540-25935-0_... 3: https://dl.acm.org/doi/10.1002/spe.434 https://dl.acm.org/doi/10.1002/spe.434
- nomemory 5y ago
  Thanks for the feedback, I appreciate it. You are right about the TOC, my other long articles have them, but for this one I simply forgot to generate one. I will generate it tomorrow. There's no compiler, and yes you are right managing a limited set of registers is hard when compiling from higher level languages. But there are a few compilers for LC3, so it's not impossible to write them even for such a limiting number of registers. But this is not my area of expertise, so someone more knowledgeable can comment on that.
  - userbinator 5y ago
    If 8 registers is "limiting", I don't know what you'd call something like a PIC which has a single accumulator... and yet, C compilers exist for those too. On the bright side, it really reduces the number of choices for register allocation.
    - andi999 5y ago
      I call it painful.
- Joker_vD 5y ago
  Register allocation is not that hard, especially if you don't do it via graph coloring and have more than 2 general-purpose registers available. Build SSA form, remove critical edges, spill temporaries until the number of simultaneously live temporaries is strictly less than the number of available registers, assign registers in a straightforward manner, move out of SSA (that's where that one unused register may come in handy). See [0] and its bibliography for more details. [0] https://hal-lara.archives-ouvertes.fr/hal-02102286/file/RR2006-13.pdf https://hal-lara.archives-ouvertes.fr/hal-02102286/file/RR20...
beanjuiceII 5y ago
so this is what people mean by a blog! very nice
- deleted 5y ago
  [deleted]
the_svd_doctor 5y ago
Nice. Note that I think there is a typo in the embedded link in "The repo can be found here", there is an extra comma "," in the URL.
saghm 5y ago
In my undergrad, we used an updated version of LC-3 (called LC-4, reasonably enough) for our intro architecture course. LC-4 came with a number of "quality of life" improvements. The simplest ones were just extra arithmetic and logical instructions; if I recall correctly, LC-3 only implemented implements an ADD instruction (as well as a variant for adding an immediate value, which meant doing multiplication required manually writing a loop. Additionally, in both ISAs, branching is done using a specialized "NZP" module, where sign result of the most recent operation (negative, zero, or positive) done by the ALU would be saved, and then branching would be done based on which conditions were expected (e.g. "branch if the last result was positive" or "branch if the last result was negative or zero" (which incidentally resulted in an instruction code identical to jumping but with one less bit available to specify the destination, as well as making the selection of the NOP binary representation easy). However, LC-4 added provided direct comparison instructions that wrote directly to the NZP module without having to write to a register, which helped avoid having to write to memory as much when doing an algorithm that requires more than just a few variables.
userbinator 5y ago
Our machine has W=UINT16_MAX words, of N=16 bits each Did the seemingly-off-by-one-error catch anyone else? A 16-bit integer has 65536 values, so you'll be going one past the end of the virtual RAM if you attempt to access address FFFFh. With this simple trick, we can avoid writing a switch statement with 16 (+1) cases Personally, I prefer having a switch since it's more obvious which opcode goes where. Probably makes the code a little shorter too (and is that another off-by-one, this time in the other direction?) Also, I understand the need to keep a "learning architecture" simple, but without byte-wide memory access, you'll quickly realise how annoying it is to work with actual bytes. For example, any string handling, unless you decide to use UTF-16 instead. I think a sweet spot is 16-bit address and 8-bit data, with register pairs for 16-bit operations, much like the popular Z80 and the 8080/8085 that preceded it. The DEC Alpha is a real architecture that made a similar mistake and later had to be extended to fix it: https://en.wikipedia.org/wiki/DEC_Alpha#Byte-Word_Extensions_(BWX) https://en.wikipedia.org/wiki/DEC_Alpha#Byte-Word_Extensions...
- bluetomcat 5y ago
  > Personally, I prefer having a switch since it's more obvious which opcode goes where. In practice, having a switch is not worse or can even be better for performance because any non-naive optimising compiler will emit a nicely ordered indexed jump table, whereas following function pointers involves more indirection through the addresses of the functions, and has the additional overhead of passing args and preparing/restoring the stack.
  - nomemory 5y ago
    I've thought of that, and to be honest I think it's worth mentioning in the article. But having set this arbitrary limit to 125 lines, before even starting to sketch things down, made me use the function tables. As a plus, article is intended for beginners, and it would be cool if they learn about function pointers from a practical example. But from a performance perspective, you are right!
  - WGH_ 5y ago
    There's also "computed gotos". It's not the same as function pointers, though. https://eli.thegreenplace.net/2012/07/12/computed-goto-for-efficient-dispatch-tables https://eli.thegreenplace.net/2012/07/12/computed-goto-for-e... - article about them being used in CPython
fjfaase 5y ago
This reminds me of the Gigatron, a minimal retro TTL-computer, which came as a kit. See: https://gigatron.io/ https://gigatron.io/ The C program for the emulator can be found at https://github.com/kervinck/gigatron-rom/blob/master/Docs/gtemu.c https://github.com/kervinck/gigatron-rom/blob/master/Docs/gt... which has 126 lines.
lionkor 5y ago
Really cool! I've never understood why modern software projects use names like `mw` or `mr`? What's wrong with `memory_read` / `memory_write`? Or `opcode_execute_fn opcode_executers[NOPS]` is magnitudes clearer than `op_ex_f op_ex[NOPS]`, and the only advantage of the latter is less time to write. You will spend at least twice as much time reading your code as writing it, just take the extra time. Nobody needs another `vsnprintf_s`. ETA: I have to repeat this is an insanely cool project idea, and very good execution
- lostdog 5y ago
  Same reason math uses letters rather than words. It's easier to pattern match strings that are short. Having one `mr`/`mw` is confusing, but taking up whole lines with long strings can obscure the logic of the code.
- bluetomcat 5y ago
  Since this code is dealing mostly with instruction mnemonics (br, jsr, lea), it makes sense for the rest of the code to comply with this style. The code has an inherently repetitive structure (implementing various opcodes) and therefore shorter global names contribute for its compactness. Mentioning "register_file" 30 times rather than "reg" wouldn't make it clearer when it is obvious that the short name serves the same purpose.
- retrac 5y ago
  On one hand, the abbreviations are extra mental work. On the other hand, when you start composing fairly complicated chains together, all those extra letters are also extra mental work. Neither is inherently right, but I do prefer something like the former here (just making up something emulatorish): mw(cpu.r[0], mr(mr(cpu.r[1]))); memory_write(processor.register[0], memory_read(memory_read(processor.register[1])));
  - nomemory 5y ago
    This was exactly my reason to shorten the name, even if most of the feedback I've received is related to the "weird" naming conventions. Initially mw was mem_write and mr was mem_read, and reg was registers, etc. But because I wanted to keep the functions as short as possible (to put them on the single line without making them totally unreadable), I've comeup with those names, which are confusing at first.
no_time 5y ago
Fascinating topic. I always wondered how can someone make the jump from understanding a VM like OP's post to something like vmprotect[0] which is orders of magnitude more complex and is designed to be as hard to reverse as possible. [0]: https://back.engineering/17/05/2021/ https://back.engineering/17/05/2021/
heywire 5y ago
I really enjoyed reading this! Thanks for taking the time to write it up!
comeonseriously 5y ago
This is really nice. Great job. It would be interesting to see how something like concurrency could be added.
musicale 5y ago
It is a virtual machine in the sense of the JVM (rather than say a VM image running on KVM.) I'd call it an interpreter/emulator for a simple instruction set and hardware interface.
cellularmitosis 5y ago
Ah the LC-3! I wrote an assembler for it a little while ago: https://github.com/pepaslabs/lc3as.py https://github.com/pepaslabs/lc3as.py I’ll definitely be digging into this article!

291 points by nomemory 5y ago

nomemory 5y ago

The article is in early draft, so there might be some errors and/or bugs.

Zababa 5y ago
I haven't read the whole article yet, I just want to report what seems to be a small error: > The code is written in C11, and it will probably compile on most operating systems. The repo can be found here, and the exact source code is vm.c: The link on "here" is broken, it's https://github.com/,nomemory/lc3-vm https://github.com/,nomemory/lc3-vm (with a comma before your github username) instead of (I think) https://github.com/nomemory/lc3-vm https://github.com/nomemory/lc3-vm.
- nomemory 5y ago
  Thanks for spotting this. I will fix it as soon as I am back to my personal computer.

garbagecoder 5y ago

This looks like a fun thing to mess with and lose sleep while I play with! Thank you!

nomemory 5y ago
Next step is to compile brainfuck to this.

emmanueloga_ 5y ago

Skimmed over this... nice write up so far! Notes: * Would be nice to have a TOC for such a long article. * I never implemented a register based VM but I think I remember one of the trickiest things is to allocate the registers when compiling from a higher level language [1], which I don't think is mentioned in the article? I think the article doesn't concern with this since the sample program just uses the bytecode directly. * Random: been thinking of a DSL that would be able to express a VM logic without having to deal with all the micro details of C... Just found a few academic papers on a quick search investigating the idea, fwiw. [2] [3] 1: https://en.wikipedia.org/wiki/Register_allocation https://en.wikipedia.org/wiki/Register_allocation 2: https://link.springer.com/chapter/10.1007/978-3-540-25935-0_12 https://link.springer.com/chapter/10.1007/978-3-540-25935-0_... 3: https://dl.acm.org/doi/10.1002/spe.434 https://dl.acm.org/doi/10.1002/spe.434

nomemory 5y ago
Thanks for the feedback, I appreciate it. You are right about the TOC, my other long articles have them, but for this one I simply forgot to generate one. I will generate it tomorrow. There's no compiler, and yes you are right managing a limited set of registers is hard when compiling from higher level languages. But there are a few compilers for LC3, so it's not impossible to write them even for such a limiting number of registers. But this is not my area of expertise, so someone more knowledgeable can comment on that.
- userbinator 5y ago
  If 8 registers is "limiting", I don't know what you'd call something like a PIC which has a single accumulator... and yet, C compilers exist for those too. On the bright side, it really reduces the number of choices for register allocation.
  - andi999 5y ago
    I call it painful.
Joker_vD 5y ago
Register allocation is not that hard, especially if you don't do it via graph coloring and have more than 2 general-purpose registers available. Build SSA form, remove critical edges, spill temporaries until the number of simultaneously live temporaries is strictly less than the number of available registers, assign registers in a straightforward manner, move out of SSA (that's where that one unused register may come in handy). See [0] and its bibliography for more details. [0] https://hal-lara.archives-ouvertes.fr/hal-02102286/file/RR2006-13.pdf https://hal-lara.archives-ouvertes.fr/hal-02102286/file/RR20...

beanjuiceII 5y ago

so this is what people mean by a blog! very nice

deleted 5y ago
[deleted]

the_svd_doctor 5y ago

Nice. Note that I think there is a typo in the embedded link in "The repo can be found here", there is an extra comma "," in the URL.

saghm 5y ago

In my undergrad, we used an updated version of LC-3 (called LC-4, reasonably enough) for our intro architecture course. LC-4 came with a number of "quality of life" improvements. The simplest ones were just extra arithmetic and logical instructions; if I recall correctly, LC-3 only implemented implements an ADD instruction (as well as a variant for adding an immediate value, which meant doing multiplication required manually writing a loop. Additionally, in both ISAs, branching is done using a specialized "NZP" module, where sign result of the most recent operation (negative, zero, or positive) done by the ALU would be saved, and then branching would be done based on which conditions were expected (e.g. "branch if the last result was positive" or "branch if the last result was negative or zero" (which incidentally resulted in an instruction code identical to jumping but with one less bit available to specify the destination, as well as making the selection of the NOP binary representation easy). However, LC-4 added provided direct comparison instructions that wrote directly to the NZP module without having to write to a register, which helped avoid having to write to memory as much when doing an algorithm that requires more than just a few variables.

userbinator 5y ago

Our machine has W=UINT16_MAX words, of N=16 bits each Did the seemingly-off-by-one-error catch anyone else? A 16-bit integer has 65536 values, so you'll be going one past the end of the virtual RAM if you attempt to access address FFFFh. With this simple trick, we can avoid writing a switch statement with 16 (+1) cases Personally, I prefer having a switch since it's more obvious which opcode goes where. Probably makes the code a little shorter too (and is that another off-by-one, this time in the other direction?) Also, I understand the need to keep a "learning architecture" simple, but without byte-wide memory access, you'll quickly realise how annoying it is to work with actual bytes. For example, any string handling, unless you decide to use UTF-16 instead. I think a sweet spot is 16-bit address and 8-bit data, with register pairs for 16-bit operations, much like the popular Z80 and the 8080/8085 that preceded it. The DEC Alpha is a real architecture that made a similar mistake and later had to be extended to fix it: https://en.wikipedia.org/wiki/DEC_Alpha#Byte-Word_Extensions_(BWX) https://en.wikipedia.org/wiki/DEC_Alpha#Byte-Word_Extensions...

bluetomcat 5y ago
> Personally, I prefer having a switch since it's more obvious which opcode goes where. In practice, having a switch is not worse or can even be better for performance because any non-naive optimising compiler will emit a nicely ordered indexed jump table, whereas following function pointers involves more indirection through the addresses of the functions, and has the additional overhead of passing args and preparing/restoring the stack.
- nomemory 5y ago
  I've thought of that, and to be honest I think it's worth mentioning in the article. But having set this arbitrary limit to 125 lines, before even starting to sketch things down, made me use the function tables. As a plus, article is intended for beginners, and it would be cool if they learn about function pointers from a practical example. But from a performance perspective, you are right!
- WGH_ 5y ago
  There's also "computed gotos". It's not the same as function pointers, though. https://eli.thegreenplace.net/2012/07/12/computed-goto-for-efficient-dispatch-tables https://eli.thegreenplace.net/2012/07/12/computed-goto-for-e... - article about them being used in CPython

fjfaase 5y ago

This reminds me of the Gigatron, a minimal retro TTL-computer, which came as a kit. See: https://gigatron.io/ https://gigatron.io/ The C program for the emulator can be found at https://github.com/kervinck/gigatron-rom/blob/master/Docs/gtemu.c https://github.com/kervinck/gigatron-rom/blob/master/Docs/gt... which has 126 lines.

lionkor 5y ago

Really cool! I've never understood why modern software projects use names like `mw` or `mr`? What's wrong with `memory_read` / `memory_write`? Or `opcode_execute_fn opcode_executers[NOPS]` is magnitudes clearer than `op_ex_f op_ex[NOPS]`, and the only advantage of the latter is less time to write. You will spend at least twice as much time reading your code as writing it, just take the extra time. Nobody needs another `vsnprintf_s`. ETA: I have to repeat this is an insanely cool project idea, and very good execution

lostdog 5y ago
Same reason math uses letters rather than words. It's easier to pattern match strings that are short. Having one `mr`/`mw` is confusing, but taking up whole lines with long strings can obscure the logic of the code.
bluetomcat 5y ago
Since this code is dealing mostly with instruction mnemonics (br, jsr, lea), it makes sense for the rest of the code to comply with this style. The code has an inherently repetitive structure (implementing various opcodes) and therefore shorter global names contribute for its compactness. Mentioning "register_file" 30 times rather than "reg" wouldn't make it clearer when it is obvious that the short name serves the same purpose.
retrac 5y ago
On one hand, the abbreviations are extra mental work. On the other hand, when you start composing fairly complicated chains together, all those extra letters are also extra mental work. Neither is inherently right, but I do prefer something like the former here (just making up something emulatorish): mw(cpu.r[0], mr(mr(cpu.r[1]))); memory_write(processor.register[0], memory_read(memory_read(processor.register[1])));
- nomemory 5y ago
  This was exactly my reason to shorten the name, even if most of the feedback I've received is related to the "weird" naming conventions. Initially mw was mem_write and mr was mem_read, and reg was registers, etc. But because I wanted to keep the functions as short as possible (to put them on the single line without making them totally unreadable), I've comeup with those names, which are confusing at first.

no_time 5y ago

Fascinating topic. I always wondered how can someone make the jump from understanding a VM like OP's post to something like vmprotect[0] which is orders of magnitude more complex and is designed to be as hard to reverse as possible. [0]: https://back.engineering/17/05/2021/ https://back.engineering/17/05/2021/

heywire 5y ago

I really enjoyed reading this! Thanks for taking the time to write it up!

comeonseriously 5y ago

This is really nice. Great job. It would be interesting to see how something like concurrency could be added.

musicale 5y ago

It is a virtual machine in the sense of the JVM (rather than say a VM image running on KVM.) I'd call it an interpreter/emulator for a simple instruction set and hardware interface.

cellularmitosis 5y ago

Ah the LC-3! I wrote an assembler for it a little while ago: https://github.com/pepaslabs/lc3as.py https://github.com/pepaslabs/lc3as.py I’ll definitely be digging into this article!