Heap Manager and Garbage Collection

Currently we support a simple mark & sweep algorithm. With this the mark phase must not be interrupted, while sweeping can be done piecewise. Lists with free blocks are kept by the class Heap. Adresses of free blocks are simple integer values.

At startup the roots of all loaded classes are collected. Roots are static references to objects. An Integer array with this size is allocated and filled with the addresses of the roots. This array and also the array with the free lists are roots themselves. The array with the free lists will be marked in the mark phase which precludes sweeping but its entries will not be followed because it is an Integer array. Following would be wrong anyway.
At the beginning the whole free heap will be entered as a single free block.

There are 8 lists with block sizes of (Bytes) 16, 32, 48, 64, 80, 96, 112 and >= 128. At the very beginning there is no array with these lists. Therefore the allocation must be done “by hand”. Only after the class constructor of the class Heap is executed the rest of the heap can be entered as a free block.
To be able to follow the free blocks (when searching a new block or when sweeping) the structure below is used:

List with free blocks

The field size holds the size of the block, next gives the address of the next free block. There is no java class for these free blocks. The reason for this is that free and used blocks must be efficiently changed into each other.

Free Block

When allocating a new block a check is made for the free heap space. If this free space falls below a certain limit a garbage collection is started.

Starting with the roots, all used blocks are marked. Objects may contain fields which are references. These references must be followed as well. The type descriptors contain the information about which fields are references.

During the sweep phase the whole heap is traversed block by block. Each block, whether free, marked or no longer used has to include information about its size. Free blocks and blocks which contain actual objects have this information at the start of the block. With arrays this information has to be retrieved with the aid of the type descriptor.

Sweep

The sweep phase could be easily made interruptible (using a task or doing only a part). Currently, this is not implemented.
Important If a certain block is no longer used (the last reference to it is deleted) it might take two mark & sweep in order to list it as a free block. The reason for this is as follows: the block was allocated and marked as used. After the reference to this block is deleted. Mark & sweep causes the mark to be removed. Only a second mark & sweep adds the block to the free list. The situation is different when the block was allocated and mark & sweep has been running several time after this. As long as the block is referenced, the mark bit will be set when marking and will be cleared when sweeping. If the reference to the block is lost, the next mark & sweep already causes the block to be added to the free list.

Strings are handled like regular objects.
Constant strings are marked as well, although they are placed in the constant block of a class. This could be problematic, if the block is placed into a flash and the flash denies write access. Usually this is no problem. When sweeping they cannot be collected. For this, the compiler has to set the mark bit already.