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

Das Feld size gibt an, wie gross der Block ist, in next steht die Adresse des nächsten freien Blocks. Es wurde darauf verzichtet eine Java-Klasse für diese freien Blöcke zu schaffen. Der Grund liegt darin, dass diese freien Blöcke in benutzte und umgekehrt umgewandelt werden müssen. Auch ist die direkte Programmierung effizienter.

Freier Block

Bei der Allokation wird geprüft, wie viel freier Platz auf dem Heap noch vorhanden ist. Wenn dieser freie Platz eine bestimmte Untergrenze unterschreitet, wird eine Garbage Collection ausgelöst.

Ausgehend von den Wurzeln werden alle benutzten Blöcke markiert. In allen Objekten muss auch den darin enthaltenen Referenzfeldern gefolgt werden. Dazu stehen im Typdescriptor die Offsets aller Referenzfelder.

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.