Memory Management

Store records can be moved in memory by the operating system, when the store is inactive. To compensate for this, as mentioned in the previous section, pointers need to be updated. This requires the VM to be able to tell the difference between a pointer and scalar data at any point where a pointer adjustment may take place. Otherwise, say, an int could be misinterpreted as a pointer and would thus be modified after an object (or a record) was moved in memory - leading at best to an erroneous computation.

Being able to tell exactly which values are pointers and which are scalars is referred to as exactness or type accuracy. It can be achieved by:

• keeping separate reference maps indicating pointer locations,
• directly tagging each individual value with at least one bit of type information.

The Spotless VM's memory management identifies a heap cell's type by analyzing the class of the object that the cell belongs to. Thus an object's class stores which fields contain pointer data and which scaler data. To identify a stack cell's type, the VM keeps a parallel stack containing the required type information. The secondary stack is called a tag stack, as it keeps a tag corresponding to each stack value and whither its a pointer or not. Each time the execution stack is modified, the tag stack is updated accordingly.

The garbage collector consists of a mark-sweep algorithm with sliding compaction that uses a break table to update pointers to moved objects [Jones and Lins, 1996]. Although this algorithm is relatively slow, it has two crucial advantages:

1.

It does not need any extra space during the compaction/update phase. The break table is built in space that moved objects leave. This is important, as on a very memory limited device, there may not be enough additional memory available for many other garbage collection algorithms.

2.

It can adjust pointers ``into'' any part of objects, not only pointers to the beginning of objects. We inherited this requirement from the original design of the Spotless VM, which features some pointers ``into'' objects for performance reasons (e.g., a method is directly referenced from a stack frame when executed, but it is not represented by its own heap object; instead, it is part of a method table heap object).

The current garbage collection algorithm does not move objects between heap segments. Although it is a compacting collector, this means there is still some fragmentation. Furthermore, when a computation is suspended, the VM will almost never find an empty segment that could be returned to the operating system. We have considered alterations to the algorithm to make it ``multi-segmented'', but would suggest that later implementations should instead take advantage of the segmentation and implement a generational collector.