ted.neward@newardassociates.com | Blog: http://blogs.newardassociates.com | Github: tedneward | LinkedIn: tedneward
understanding a VM can come from building one
so let's build one!
and understand that there's limits to what we can do in a single session
an abstraction that defines a computing model (aka AbstractMachine)
an implementation of an AbstractMachine on top of hardware
state (data)
explicit (memory, registers, stack)
static
stack
dynamic
implicit (translated code, working areas, stateful I/O, ...)
execution (code)
definition (bytecode, native, etc)
loading/resolution
manipulation
libraries
services
automatic memory management
metadata access and manipulation
... others depending on VM intent
host/guest interaction (FFI)
Loader and dynamic linker
Loader pulls in application package
Loader extracts data structures (code and data)
constant pool: collection of constants
Dynamic linker resolves all referenced symbols
Execution engine
processor: fetch-decode-execute mechanism
call stack: function call frames
Memory manager
application data
virtual machine data ("overhead")
Thread scheduler
Language extension
Runtime services: platform access, etc
Language extension/access: FFI
typically unique Instruction Set Architecture (ISA)
loaded in from disk (or elsewhere?)
formats often optimized for easy reading
typically inaccessible (directly) to runtime code
usually we need to know where we are in here
"instruction pointer" or "program counter"
tracks the current location in code
indicative of the next instruction for execution
manipulated by flow-control instructions
collection of "activation frames" (procedure/method/function calls)
LIFO order--push and pop from one end, most recent at the top
contain parameters passed to the activation
provides space for local-allocated values
and space for any additional in-process work
"frame pointer" or "stack pointer"
pointer to the current activation frame
offset for any direct memory access of frame data
"static"
sequential memory locations
often allocated by the language/virtual machine (global variables)
"heap"
sequential memory locations
dynamically-allocated by running code
typically somewhat managed by VM for programmer simplicity
a software CPU
fetch-decode-execute cycle
fetch: get the next instruction (from IP)
decode: if the instruction is "packed"
execute: utilizing any operands required
fixed collection of values in memory
loaded along with code
values known to the VM ahead-of-time
string values
function locations
"magic constants"
stored globally for easy reference
an abstract instruction set
that is, not tied to hardware
usually simplified than CPU assembly
low-level
allowing for more complex construction
providing core/basic functionality
tied to the abstract machine executing it
stack vs register machine, for example
(not always: see LLVM)
constant values
stack manipulation (push, pop, etc)
arithmetic operations
flow-control operations (branch-if-true, branch-if-false, ...)
storage operations (store, load; global, local)
type conversion operations (int/float/object/etc to int/float/object/etc)
allocation/deallocation
(imperative) procedure invocation
direct or indirect (via address)
taking reference
(messaging) message-send, "super-send"
(object) method invocation
(functional) closure definition
(logic) backtrack manipulation
instructions are formed of two parts
operation code (opcode)
operation parameters (operands)
these will sometimes be supplemented by other things
directives (commands to the tools)
labels (symbolic names used)
some take none (NOP, HALT, pop, etc)
some take one (a constant value, etc)
some take two (add, subtract, etc)
some may take a varying number
multiple bytes/values
"packed" bytes/values
note that "raw" format and "programmer" format need not be identical
binary
assemblers (source-to-binary)
s-expressions ("lisp")
XML (s-expressions with angle brackets)
Registers will be special-purpose (IP, FP, SP, etc)
... but most operations will focus on the operations stack
all operands come from the stack
all results go back onto the stack
the stack must (eventually) balance out to zero
stack width is (usually) one "word"
32-bit or 64-bit, depending on abstract machine's choice
often not specified exactly, and assumed to hold one-of-anything
top-of-stack is usually identified by stack pointer (SP)
most abstract VMs don't ignore registers
register access is much faster than actual CPU stack
CPUs often have their own conventions to honor
... so the operation stack may not be entirely on the CPU stack
remember, "abstract" is usually a simplification, not a straitjacket
push (or const) op: push op onto the stack
pop: pop op off the stack
dup: duplicate (pop, push, push)
ldc ix: push constant (from constant pool index ix)
binary math operations (add, sub, mul, div, mod, pow)
pop sp1, sp2; sp1 (operate) sp2; push result
may specialize opcodes to precision (32-bit, 64-bit, int vs float, etc)
order is important! ((1 - 2) != (2 - 1), remember); left-to-right or right-to-left?
unary math operations (neg, abs, etc)
pop sp1; (operate) sp1; push result
may specialize opcodes to precision
shift or rotate operations (shiftl, shiftr, rotl, rotr)
pop sp1; (operate) sp1; push result
may specialize opcodes to precision
most of these are really just extensions of unary math operations
pop sp1, sp2
sp1 (compare) sp2?
if true, push 1/true
if false, push 0/false
equality, non-equality
greater-than, less-than
... and variations (greater-than-or-equal, less-than-or-equal, etc)
may specialize opcodes to precision or convenience (comparison-to-zero, for example)
must always have one operand: where to jump
typically an address in the bytecode
operand may be "direct" (embedded in the stored code)
operand may be "indirect" (we get the address from somewhere else)
operand may be "absolute" address (within all the code)
operand may be "relative" address (to our current location)
jump-if-zero, jump-if-not-zero the most common
depends on how the opcodes and operands are encoded
or how "wide" the ISA wants to be
these are often mirrored by underlying CPU opcodes
call typically implies a branch-and-return (ret) pair
conventions are critical
call conventions
parameters go onto the operations stack
order-sensitive
"left-to-right" (from callers' perspective)?
or "right-to-left" (from callers' perspective)?
typically assumes pass-by-value semantics (no immediate modifications)
return conventions
result goes onto operations stack
usually single-value results, but...
... nothing really stops us from having multiple results if we wished
... which could be one way pass-by-reference is implemented!
who cleans up the stack?
where is return-address stored?
general-purpose registers
integer-only registers
floating-point registers
string/data registers
note: there's still a program stack involved
making register VMs something of a superset to stack VMs
typically of "word" size (32 or 64 bits)
frequently of different sizes (for optimization purposes)
may or may not map to actual CPU registers
LOADRx: load value into register
constant value
from local or global memory
from other register
STORERx: store register
into local or global memory
into other register
push (or const) op or Rx: push op or the contents of Rx onto the stack
pop: pop op off the stack; pop Rx pops op off the stack into Rx
dup: duplicate (pop, push, push)
ldc ix: push constant (from constant pool index ix)
one/some registers are often specific to math (accumulator)
operands can often be
register
local memory
global memory
... and some machines restrict which from where
binary operations (add, sub, mul, div, mod)
three operands: src1, src2 and dest
unary operations (abs, pow, neg, shift, rotate, etc)
two operands (src, dest) or one operand (src and dest)
shift or rotate operations (shiftl, shiftr, rotl, rotr)
most of these are really just extensions of unary math operations
generally these will operate against a small set of registers
operand (compare) register?
if true, push 1/true
if false, push 0/false
equality, non-equality
greater-than, less-than
... and variations (greater-than-or-equal, less-than-or-equal, etc)
may specialize opcodes to precision or convenience (comparison-to-zero, for example)
must always have one operand: where to jump
typically an address in the bytecode
operand may be "direct" (embedded in the stored code)
operand may be "indirect" (we get the address from somewhere else)
operand may be "absolute" address (within all the code)
operand may be "relative" address (to our current location)
jump-if-zero, jump-if-not-zero the most common
depends on how the opcodes and operands are encoded
or how "wide" the ISA wants to be
these are often mirrored by underlying CPU opcodes
call typically implies a branch-and-return (ret) pair
conventions are critical
parameters can go into registers
typically size-sensitive
typically ordered
(some/remaining) parameters go onto the operations stack
order-sensitive
"left-to-right" (from callers' perspective)?
or "right-to-left" (from callers' perspective)?
typically assumes pass-by-value semantics (no immediate modifications)
result goes into register
who cleans up the stack?
where is return-address stored?
Basic architecture and scaffolding
Simple (no-operand) ops: NOP, HALT, DUMP
Simple stack ops: CONST, LDC, POP
Globals ops: GSTORE, GLOAD
Math ops: ADD, SUB, etc
Comparison ops: EQ, NE, GTE, etc
Branching ops: JMP, JT, JF, etc
Call ops: CALL, CALLI, RET
Locals ops: LSTORE, LLOAD
add other types beyond ints and functions
memories could be made smaller (blocks/chunks/etc) and demand-allocated
definitions for "structures"
new opcodes
optimize, optimize, optimize, ...
Production VM implementations
Java (OpenJDK), .NET (CoreCLR), Android (Dalvik, ART)
Javascript (V8, Chakra), WebAssembly
Python (CPython, JPython), Ruby, Smalltalk (Squeak, Pharo)
Erlang (BEAM)
SQLite
ScummVM
Academic VM implementations
Simple Object Machine (SOM)
"tiny Smalltalk"--entirely message-driven
http://som-st.github.io/
Self
message-driven, "high-level" but high-performance
https://selflanguage.org/
EM (from The Amsterdam Compiler Kit)
http://tack.sourceforge.net/olddocs.html
Web
C-- ("high-level assembly language")
https://www.cs.tufts.edu/~nr/c--/index.html
BEAM VM Wisdoms (by Dmytro Lytovchenko)
SCUMMVM Technical Reference
https://wiki.scummvm.org/index.php?title=SCUMM/Technical_Reference
Books
Language Implementation Patterns
Parr (Pragmatic Publishers)
Virtual Machines
Smith, Nair (Morgan Kaufman)
Advanced Design and Implementation of Virtual Machines
Li (CRC Press)
Architect, Engineering Manager/Leader, "force multiplier"
http://www.newardassociates.com
http://blogs.newardassociates.com
Sr Distinguished Engineer, Capital One
Educative (http://educative.io) Author
Performance Management for Engineering Managers
Books
Developer Relations Activity Patterns (w/Woodruff, et al; APress, forthcoming)
Professional F# 2.0 (w/Erickson, et al; Wrox, 2010)
Effective Enterprise Java (Addison-Wesley, 2004)
SSCLI Essentials (w/Stutz, et al; OReilly, 2003)
Server-Based Java Programming (Manning, 2000)