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 theses 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:

Liste mit freien Blöcken

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 ,ust be followed as well. The type descriptors contain the information about which fields are references.

In der Sweep-Phase muss der gesamte Heap durchlaufen werden. Dabei wird von Block zu Block vorangegangen. Jeder Block (ob frei, markiert oder nicht mehr benutzt) muss also auch die Information über seine Blockgrösse beinhalten. Dies ist bei freien Blöcken und bei normalen Objekten direkt im Blockanfang enthalten. Bei Arrays muss diese Information mit Hilfe des Typdescriptors gefunden werden.

Sweep

Grundsätzlich könnte die Sweep-Phase unterbrechbar gemacht werden (mit einem Task oder indem einfach ein Stück durchlaufen wird), im Moment ist das aber nicht so gelöst.
Achtung Wird ein bestimmter Block frei (d.h. die letzte Referenz darauf geht verloren), dann wird dieser Block unter Umständen erst nach zweimaligem Mark/Sweep als freier Block markiert. Begründung: Der Block wurde alloziert und wurde dabei gleichzeitig markiert. Dann wird die Referenz darauf entfernt. Mark / Sweep bewirkt nun erst, dass die Markierung entfernt wird. Erst ein ein zweites Mark / Sweep fügt den Block in die freie Liste ein. Anders verhält es sich, wenn ein Block alloziert wurde und zwischenzeitlich bereits ein oder mehrere Male Mark / Sweep aufgerufen wurde. Solange der Block referenziert wird, wird auch das Mark-Bit gesetzt und vom Sweep wieder gelöscht. Wird nun die Referenz entfernt, bewirkt bereits ein einmaliges Mark / Sweep dass der Block in die freie Liste kommt.

Strings werden wie normale Objekte behandelt. In der Mark-Phase werden auch konstante Strings markiert, obwohl sich diese im Konstantenblock einer Klasse befinden. Das könnte zu einem Problem führen, wenn sich dieser Block in einem Flash befindet und dieses keinen Schreibzugriff erlaubt. Das ist aber normalerweise nicht so. Natürlich werden konstante Strings beim Sweepen nicht eingesammelt, sie befinden sich ja gar nicht auf dem Heap.