1. INTRODUCTION

The object diagram of the pal-vm shows selected runtime data structures.  It is
important to note that this is an object diagram, certainly not a class diagram
(and not any other sort of UML diagram either).  Many pointers have been
omitted for clarity though often a few representative pointers have been
inserted for clarity.

2. OUTSIDE THE HEAP

Most objects are found inside the garbage-collector managed heap.  This keeps
things simple in many ways.  It is intended that memory outside the heap should
only be allocated in very limited ways.  In the VM itself there should be no
memory freed (only allocated) which should allow a very simple malloc
implementation to be used.  The zlib code is probably an exception to this.
Another exception to this may be code called with the external call mechanism
from within byte code programs.

2.1 Heap::theHeap

Outside the heap we find a global pointer to the heap, Heap::theHeap.  In the
current implementation the heap is a generational mark-sweep-compact heap,
though a copying collector is still in the code base (probably not functional).
The Heap::theHeap pointer is at the top left of the diagram.

2.2. Universals

Since objects on the heap can move a garbage collection occurs we need to be
very careful with the way we use them from C++ code.  C++ does not expect
obejcts to move once they are created, yet C++ code accesses objects on the
heap.  A garbage collection can only occur when a new object is allocated or an
existing object is expanded (stacks, hash maps, etc.).  In fact objects are
never expanded, but merely replaced with bigger versions.

A single special pointer from the C++ world is known by the garbage collector.
This is a pointer to an Array object, called the universals.  The universals
are shown on the left of the heap in the diagram.  If the universals move then
the Universe::Universals pointer is updated by the garbage collector.  The C++
code can use pointers from the universals array, but must reload them from the
array after any operation that may allocate on the heap (causing a garbage
collection).

The universals array contains pointers to most of the basic objects in the
VM.  For example the symbols used by the interpreter, nil/null, true and
false are all referenced from the universals.  In addition most of the basic
class objects are referenced from universals, for example the class objects
for the Object, Symbol, String, Integer, Integer32 classes etc.

2.3. Handles

When implementing the VM in C++ it can be necessary to have pointers to heap
objects in local variables on the C++ stack.  This is no problem unless an
operation that may allocate a new object is performed.  In this case the
garbage collector has to know about the local variables so that it can update
them.  This update of local variables is accomplished by using Handle
structures on the stack.  For every class that is known by the C++ code there
is a corresponding Handle class (structure).  The corresponding handle objects
are normally placed on the C++ stack in the form of local variables.  They are
placed in a chain, using their next pointer.  This chain is shown on the left
of the diagram.  Each handle object has space for one pointer into the heap.
When the garbage collector has moved objects it can use the handle chain to
find the pointers and update them to the new locations of the heap objects.

The process of placing the handles in a chain and removing them again is
handled by C++ constructors and destructors.  In C++ a destructor is called on
a stack allocated object when it goes out of scope (ie when program flow passes
the relevant '}' symbol).  The constructors and destructors thus maintain a
chain, starting with the currentHandle variable, and ending with a null next
pointer.  Since the C++ code implementing the VM is largely single threaded it
suffices to have one chain of handles.  It is important that the parts of the
C++ that run in other threads (those to do with Native Futures) do not make use
of handles.

2.4 The Dispatch Cache

The interpreter maintains an array known as the dispatch cache.  This contains
a mapping from class-symbol pairs to methods.  It allows the interpreter to
very quickly determine the correct method to call when it is presented with a
method name (symbol) and a receiver object (with a particular class).  In order
to do this it contains many direct pointers from outside the heap to objects
(classes, methods, symbols) inside the heap.  In addition it uses the addresses
of objects in order to implement a very fast hashing mechanism on the class
and method names.

For both these reasons the dispatch cache needs to be rebuilt whenever objects
have been moved on the heap.  This is done by clearing the dispatch cache
completely on every garbage collection and allowing it to be rebuilt on demand
by the interpreter when it runs.  In the generational collector it may be
possible to determine sometimes that no symbols, methods or classes have
been moved, in which case the dispatch cache need not be cleared.  This
analysis is not performed at the moment.  The dispatch cache is shown on
the bottom left of the diagram, though most of its references into the heap
have been omitted for clarity.

3. The Garbage Collected Heap

On the heap we find objects that are always a multiple of 4 bytes in size.
(The VM is designed for a 32 bit CPU.)  The smallest objects are 4 bytes in
size (exepting small integers which take up no space at all).

3.1. The Object Header

The first word (4 bytes) of a heap object is always taken up with a pointer
to a class object that determines the runtime class of the object.  This
pointer is not updated after the object has been created.

These class pointers are not shown on the diagram.  Since our VM does not
allow the programmer to find a hash code on an arbitrary object or lock an
arbitrary object we do not have to jump through hoops to find space for hash
codes or lock data in the header.  Since class objects are always aligned
on 4-byte boundaries (like all other objects) the last two bits of the header
are always zero.  The garbage collector may use these bits while it runs
(currently only the copying semispace collector does so) as long as they are
zeroed again when the program continues to run.

3.2 The Object Body

In addition to the class pointer (header) the objects may have a number
of properties (declared in their .hpp files) which are arranged immediately
after the header.  Classes (such as programmer-defined classes) that do not
have a corresponding .hpp file do not have properties (unless they inherit
from classes with properties).

After the properties come the instance fields, defined in the component
(.prc) files.  Only objects with regular layout can have instance fields.

3.2 The Class Objects

For each of the classes in the system there is a class object.  These are the
objects that are linked to from the headers of other objects.  They contain a
layout field which is used by the garbage collector to determine how to scan
the object for pointers.  (Since pointers and integers are tagged this is
actually fairly simple - the only tricky objects are those with byte arrays in
them.)

Some of the basic class objects are depicted near the top of the diagram, left
of centre.  Each class has a super pointer that points to the superclass of the
class.  The 'Object' class points to itself to indicate that it is the root of
the inheritance tree.  The classes near the top of the diagram are all basic
system classes so there is a reference to each of them from the Universals
array.  These references are used in the implementation of primitives and of
the interpreter.

A class that is defined by the programmer will not have such references from
the universals array.  Two such classes are shown in the diagram (MyClass and
MySybclass) in the bottom centre of the diagram.

Each class is part of a component.  Two components are shown in the diagram.
One is the special base component with the important system classes such as
'Object' in it.  The other has been defined by the programmer and is called
myComponent.  Each component has (in addition to its name and other
information) an array which contains references to the classes in the
component.

Each class has an array of methods.  This array is only shown for a few of the
classes in the diagram.  These are the methods that are defined on a class.
The methods that are inherited from superclasses are not present in the method
array of a class (they are present in the method array of a superclass).

3.3 Method Objects

In the method object we find the name and other metadata needed to execute
the method.  In the 'Release' version of the VM there is no link back to 
the class that defines the method.  This is to save space although it
complicates the generation of stack traces.  The name is in the form of a
Symbol (which is canonicalized).

The actual byte codes are attached to the end of the method object.  This
means the method class has a special layout (the byte codes need not be
scanned by the VM since they do not contain pointers).  This arrangement
is both faster and more compact than the straightforward solution (having
the byte codes in a separate byte array that is referenced from the method
object.)  A sample method is shown attached to the Object class object at the
top of the diagram, slightly right of centre.

Each method has an array of object references called the literals array.  This
array is not inlined in the method object, though it would probably make sense
to do so.  In order to save space, some methods share a literal array.

3.4 Symbols

Symbols are very similar to Strings.  They are immutable Unicode character
sequences.  In contrast with Strings, however, they are canonicalized.  That
is, there cannot be two distinct Symbols containing the same charater sequence.
Symbols are stored in UTF-8 bytes rather than 16-bit Unicode so they are
optimized for predominantly ASCII (7-bit) characters.  Symbols are currently
not accessible from pal-j compiled code.

In order to guarantee that Symbols are canonicalized there is a single, large
symbol table.  This is an array containing a reference to each symbol.  The
placement of the symbols in the symbol table is determined by the hash code of
the symbol.  This is an open addressed hash table (not a chained table) so
special care must be taken when deleting elements.

The symbol table and a sample symbol are shown in the bottom right of the
diagram.  The other symbol in the diagram ('some symbol' near the bottom, left
of centre) is also referred to by the symbol table, but this is not shown in
the diagram.

When collecting garbage, the symbol table is treated specially.  It is scanned
last, and any symbols in it that were not already marked as being live are
declared dead and deleted from the symbol table.  This works best when
performing a full heap collection (less well in generational collections).  The
effect is that the symbol table references are 'weak' and will not keep a
symbol alive that would otherwise be garbage.

The symbols themselves are stored with the UTF-8 bytes stored at the end of the
symbol object.  This means symbols have variable size and must be treated
specially by the garbage collector.  Like in the case of methods this is done
to space space and time.  A zero byte is always stored after the data.  This
means that debugging routines and gdb can treat symbols as conventional C-style
zero-terminated byte strings.  For this purpose the method 'asCharStar()' is
provided.  In addition to the terminating zero byte (which is not part of the
symbol) the symbol may contain embedded zeros (though this is very rarely
used).

3.5 Strings

Strings have their characters stored in a separate array.  It would save space
to have a special character array type with 16 bits per character.  It would
save even more space to append the characters to the end of the string object.

3.6 Coroutines and Stacks

Each Coroutine or Thread has a stack.  An example is show in the upper right of the diagram.  The stack is used only for byte code execution, never for external calls or primitives.  At the start of each method the stack is checked to see whether it will be large enough.  This is possible because a method can only use a bounded and pre-calculated amount of space on the stack.  If the stack is too small then it can be replaced by a larger one.  The only link to the stack is found in the coroutine object.

The exact layout of the stack frames is described in Stack.hpp.

3.7 HashMaps

The HashMap is an implementation of a chained hash map that is used both for
the implementation of internals in the VM and also as the basis for the HashMap
Smalltalk class on which other collections are based.

The HashMap has a property (called contents).  For small HashMaps this is a
link to a single chain of buckets.  For larger HashMaps the contents property
contains a reference to an array.  The array has a power-of-two size and the
hash code of the key is used to determine which array element points to the
chain of buckets with the given key in.

(fixed width font needed for following diagram)

 HashMap (small)
|--------|
|fullness|             HashEntry
|contents|----------->|-------|              HashEntryWithHash
|--------|            | next  |------------>|-------|
                      | key   |             | next  |----------->nil
                      | value |             | key   |
                      |-------|             | value |
                                            | hash  |
                                            |-------|

 HashMap (larger)
|--------|
|fullness|             Array
|contents|----------->|-------| 
|--------|            | length|                      HashEntry
                      | elt0  |-------------------->|-------|
                      | elt1  |-----...             | next  |----------->nil
                      | elt2  |-----...             | key   |
                      | elt3  |-----|               | value |
                      |-------|     |     HashEntry |-------|
                                    -----|-------|             HashEntryWithHash
                                         | next  |----------->|-------|
                                         | key   |            | next  |-----...
                                         | value |            | key   |
                                         |-------|            | value |
                                                              | hash  |
                                                              |-------|
                                                             


In the situations where the HashMap is used from C++ code, the keys have a hash
code method implemented in C++ and their equality test is simply the test for
object identity.  Classes where the objects fulfill these requirements include
Symbol, Integer, Class, Boolean, Nil.  Such keys are called 'simple' and there
is a primitive in the HashMap class to test an arbitrary object for simpleness.
In this case the chain buckets can be implemented using the HashEntry class.
All operations on HashMaps using simple keys are implemented using a single
primitive (adding, removing, testing for key presence, etc.) 

For non-simple keys, the hashCode method is implemented in byte code, and the =
method is not identity-based and is also implemented in byte code.  In this
case all operations must be performed by byte code, since the VM does not have
the ability to call byte code from C++ code (except one place, the entry point
to the interpreter).

The code that handles simple keys can mostly ignore the non-simple keys.  They
do not test equal for object identity.  However, when the the HashMap moves to
a larger array size (or from the small configuration to the array-based
configuration) it needs to know the hash code of the non-simple key.
Therefore there is a special bucket class for the non-simple keys, where the
hash code is stored along with the key and value pair.  This is the purpose
of the HashEntryWithHash class.

In addition to the HashMap class there is a superclass called ReadableHashMap.
This has the property that it is immutable from byte code (lacking the
primitives to modify it).  It is used to implement the VM.

3.8 Arrays and ByteArrays.

Arrays are non-resizable sequences of objects (including Integers).  They are
arranged with the array elements stored in extension of the properties declared
in the Array.hpp file, and are treated specially by the garbage collector.

ByteArrays are similar to arrays, but can only store 8 bit integers.  They are
correspondingly compact.

A superclass of the Array class, ReadableArray, is similar to ReadableHashMap
in that it is immutable from the byte code level.  ReadableArrays and
ReadableHashMaps can be embedded in Smalltalk source code with special syntax
and are used by the pal-j compiler to generate Java code.
