== Shotgun: The Rubinius VM

Rubinius consists of a mixture of both Ruby and C code. While the goal is to
develop as much of Rubinius as possible in Ruby, some low-level C code is
nonetheless required. Currently, all core and library classes are written
almost entirely in Ruby, which is then compiled down to bytecode (by a compiler
which is also written in Ruby) which in turn is run by Shotgun, the Rubinius
virtual machine. Shotgun is currently written in hand-coded C.

In future, the Rubinius virtual machine is intended to be re-written in a
Ruby-like language known as Garnet. Garnet will be a minimal Ruby dialect that
can be used to generate C-code directly, much as Slang (a Smalltalk subset
language) was used to build Squeak, (a Smalltalk virtual machine).

=== Shotgun Design Features

Shotgun borrows significantly from the design and implementation of
Smalltalk-80, as described in the {blue
book}[http://stephane.ducasse.free.fr/FreeBooks/BlueBook/], as well as various
other "crazy computer science papers". Some of the more interesting and/or
noteworthy features of Shotgun are described below.

==== Stack-based Virtual Machine

Shotgun is a stack-based virtual machine, which means that bytecode
instructions operate on an operand stack. Most opcodes therefore consume and/or
produce values that are held on a stack, with the last item added (pushed)
being the first item removed (popped).

All Ruby values in Shotgun (and hence, all values on the stack) are defined in
terms of object-oriented pointers (OOPs), which are always a uniform size
(currently 4-bytes on both 32-bit and 64-bit platforms). This in turn makes the
stack simple (and fast) to operate on.

The two least significant bits of an OOP define its meaning:

00::
  The OOP is a reference (pointer) to a memory location (which is always
  aligned to a 4-byte boundary).
01::
  The OOP is a fixnum (integer) value, with the actual value consisting of a
  sign bit followed by 29 bits representing the number.
10::
  The OOP is a literal reference in a literals tuple of a method context.
11::
  The OOP is a data reference, where the data type is given by the next bit:
  0::
    The data reference is a reference to a symbol, with the index of the symbol
    in the symbol table given by the 29 significant bits.
  1::
    The data reference is a reference to a custom data type.

==== Generational Garbage Collection

Shotgun implements a generational garbage collector, consisting of a Baker
collector for the young generation, and a mark-sweep collector for the old
generation.

Objects are typically tenured into the old generation after surviving seven
collections in the young generation, although very large objects may be
instantiated directly in the old generation to avoid the copy overhead of the
Baker algorithm.

==== Spaghetti Stack

Shotgun runs Rubinius bytecode using a stack-less design. This may sound
strange, given the Rubinius virtual machine is a stack-based bytecode machine;
however, it refers to the avoidance of C stack frames when dispatching Ruby
methods. At any point during the execution of a Ruby program on Shotgun, there
will be exactly three C stack frames that appear in a C stack trace: +main+,
+machine_start+, and +cpu_run+.

Instead, Rubinius uses what is termed a "spaghetti stack", whereby execution
context is maintained on the heap in first-class objects such as MethodContext
and BlockContext. These execution contexts contain all the information that is
normally found on the C stack, such as the method chain to this point, local
variables, etc. However, because they are first-class data structures residing
on the heap, they can be manipulated, passed around, re-ordered etc. This in
turn makes it relatively simple for Rubinius to support green threads,
continuations (essentially a snapshot of an execution context at a point in
time) and debugging.

==== Direct Threading

Shotgun implements {direct
threading}[http://www.complang.tuwien.ac.at/forth/threaded-code.html], which is
a technique used to minimise the overhead associated with dispatching to the
low-level C code that implements each VM op code. Instead of a large switch
statement consisting of cases for each op code, the byte code is modified after
load, with the byte codes for each op code replaced with the actual address of
the code that implements the op code. The VM then executes each op code by
simply jumping directly to the address indicated where each byte code used to
be.

