7.96 KB
Newer Older
# Mu Reference Implementation version 2
Kunshan Wang's avatar
Kunshan Wang committed

Kunshan Wang's avatar
Kunshan Wang committed
This project is the current reference implementation of Mu, the micro virtual
machine designed by [The Micro Virtual Machine Project](
Kunshan Wang's avatar
Kunshan Wang committed

Kunshan Wang's avatar
Kunshan Wang committed
6 7 8
Version 2.1.x implements the [master branch of the Mu
which uses the goto-with-values form.
9 10

This project is based on the previous works of
Kunshan Wang's avatar
Kunshan Wang committed
12 13
[microvm-refimpl]( is the
previous reference implementation.
Kunshan Wang's avatar
Kunshan Wang committed

## How to compile
Kunshan Wang's avatar
Kunshan Wang committed

Kunshan Wang's avatar
Kunshan Wang committed
17 18 19 20 21 22 23
**For the impatient**:

* If you use Mac, install [Homebrew](
* Install [Scala]( 2.11. If you use Mac and Homebrew,
  `brew install scala`.
* Install [sbt]( 0.13. If you use Mac and Homebrew,
  `brew install sbt`.
* Install [Scala IDE]( 4.x (Eclipse with pre-installed
Kunshan Wang's avatar
Kunshan Wang committed
25 26 27 28 29 30 31 32 33 34
  plugins for Scala).
* Clone this repository:

git clone

* In the directory `microvm-refimpl2`, do the following:

sbt update genSrc eclipse
Kunshan Wang's avatar
Kunshan Wang committed
36 37 38 39 40 41 42

* Open Scala IDE and import the generated project as "existing project into

**Detailed guide**:

43 44 45 46
You need [Scala]( 2.11 and
[sbt]( 0.13. It is recommended to install them using
the package manager of your operating system or distribution (including apt-get,
yum, pacman, etc. for GNU/Linux distributions and Homebrew for Mac OS X).
Kunshan Wang's avatar
Kunshan Wang committed

48 49
To download all dependencies from the Maven central repository, invoke `sbt
Kunshan Wang's avatar
Kunshan Wang committed

51 52
To generate the Mu IR parser from the Antlr grammar, invoke `sbt genSrc`. The
generated sources will be in the `target/scala-2.11/src_managed` directory.
Kunshan Wang's avatar
Kunshan Wang committed

To generate an Eclipse project, install the [sbt-eclipse
55 56 57 58 59 60
plugin]( and invoke `sbt eclipse`.
Make sure you generate the parser before creating the Eclipse project, so that
the generated sources will be on the Eclipse build path.

To compile, invoke `sbt compile`. This will also generate the Mu IR parser using
61 62 63

IntelliJ IDEA has plugins for Scala and SBT. Make sure you don't commit `.idea`
or generated project files into the repository.
Kunshan Wang's avatar
Kunshan Wang committed

## How to run
66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85

There is a sample factorial program (generously provided by @johnjiabinzhang) in
the `src/test` directory. To run the program with all dependencies on the
classpath, you need to run it with sbt. Invoke `sbt` to enter the interactive
shell. Then type:

set fork := true
test:runMain junks.FactorialFromRPython

or directly from the command line:

sbt 'set fork:=true' 'test:runMain junks.FactorialFromRPython'

`fork := true` tells sbt to run the program in a different process than the one
running sbt itself.

86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192
## Implementation details

This reference implementation aims to be easy to work with, but does not have
high performance. It may be used by client writers to evaluate the Mu micro VM,
and may also be used by Mu micro VM implementers as a reference to compare with.

The micro VM is implemented as an interpreter written in Scala. The main class
is `uvm.refimpl.MicroVM`, which implements the `MuVM` struct specified by the
but is more Scala-like. The client interacts with the micro VM via
`uvm.refimpl.MuCtx` instances created by the `MicroVM` instance, which
corresponds to the `MuCtx` struct in the spec. `uvm.refimpl.MuValue` and its
subclasses implement the `MuValue` handles, but has a real Scala type hierarchy
and does extra type checking when converting, which is not required by the spec.

The client can also be written in C or other languages that can interface with
C. (TODO: this part is under construction)

### Threading model

It uses green threads to execute multiple Mu threads and uses a round-robin
scheduler: the interpreter iterates over all active threads, executes one
instruction for each active thread, then repeat this process. However, the whole
Scala-based program itself is **not thread safe**. Do not run multiple JVM or
native threads. This means, you can still experiment with concurrent Mu
programs, but there are some corner cases that do not work in this refimpl. For

- Waiting for other Mu threads in the trap handler. The trap handler is executed
  by the same thread executing the Mu IR. During trap handler, no Mu program is
  executed. So if you want to use
  to wait for certain Mu thread to come to a certain rendezvous point (a common
  optimisation trick), you should either wait within Mu IR (not in trap
  handlers) or try the high-performance Mu implementation which is still being

- Synchronising with concurrent native programs via pointers, atomic memory
  access and futex. This is the realistic way for Mu to synchronise with
  native programs or foreign languages, but this refimpl implements atomic
  memory access as not-atomic (since it uses green thread) and implements futex
  in Scala (since it has its own scheduler).

The MicroVM instance will not start executing unless its `execute()` method is
called. This method is specific to this implementation, and is not defined in
the specification. This also means the *client cannot run concurrently with the
MicroVM*, i.e. once started, the client can only intervene in the execution in
**trap handlers**. So a common use pattern is:

val microVM = new MicroVM()

val uir = myCompiler.compile(sourceCode)
val ctx = microVM.newContext()

microVM.setTrapHandler(theTrapHandler)  // Set the trap handler so the client
                                        // can talk with the VM when trapped.

val stack = ctx.newStack(theMainFunction)
val thread = ctx.newThread(stack, Seq(params, to, the, main, function))

microVM.execute() // The current JVM thread will run on behalf of the MicroVM.
                  // This blocks until all Mu threads stop.
                  // However, MicroVM will call theTrapHandler.

Only the text-based IR and HAIL are implemented. The binary-based IR and HAIL
script do not have high priority at this point, because our current focus is to
implement a correct Mu VM and the text-based IR is easier for debugging. IR
parsing is also not yet known as the bottleneck.

### Garbage collection

This reference implementation has an exact tracing garbage collector with a
mark-region small object space and a mark-sweep large object space.

### IR implementation-specific details

- Many undefined behaviours in the specification will raise
  `UvmRuntimeException`, such as division by zero, going below the last frame of
  a stack, accessing a NULL reference, etc. But this behaviour is not

- `int<n>` for n = 1 to 64 are implemented. `vec<T n>` is implemented for all T
  that are int, float or double, and all n >= 1. However, only 8, 16, 32, 64-bit
  integers, float, double, `vec<int<32> 4>`, `vec<float 4>` and `vec<double 2>`
  can be loaded or stored from the memory.

- The tagged reference type `tagref64` is fully implemented.

- Out-of-memory errors will terminate the VM rather than letting the Mu IR
  handle such failures via the exception clauses.

### Native interface

This reference implementation assumes it is running on x86-64 on either Linux or
OSX. It implements the [AMD64 Unix Native
of the specification. It can call native functions from Mu IR and let native
programs call back to Mu IR. 

It does not support throwing Mu exceptions into native programs, or handing
C++-based exceptions.

## Author and Copyright
Kunshan Wang's avatar
Kunshan Wang committed
193 194 195 196 197 198

This project is created by Kunshan Wang, Yi Lin, Steve Blackburn, Antony
Hosking, Michael Norrish.

This project is released under the CC-BY-SA license. See `LICENSE`.

## Contact
Kunshan Wang's avatar
Kunshan Wang committed

201 202 203 204 205
Kunshan Wang <>

vim: tw=80