Heap mit Garbage Collection --------------------------- Vorteile: - Es werden keine Handles benötigt: ein Dereferenzierungs-Schritt weniger bei jedem Zugriff. - Keine Objekt-Freigabe nötig: kürzer, schneller. - Erleichtert die Implementierung von Exceptions. - Kein Belegungszähler nötig: kürzer, schneller. - keine Unterscheidung zw. gezählten und ungeschützten Referenzen. ('¢') - Zähler kann nicht überlaufen. - Implementierung für mehrere Threads leicht möglich. (Alle Daten werden als ein großer Struct angesehen.) - Arrays und Structs können auch außerhalb des Heaps liegen. - Arrays und Structs, die nicht verschoben werden, bleiben durchgehend (z.B. für Interrupt-Handler) benutzbar. Nachteile: - GC komplizierter - GC läuft länger - Alle Variablen mit Daten auf dem Heap müssen jederzeit auffindbar sein: globals, locals, array und struct items. - separater Stack (pro Thread) für Heap-Variablen (Pointer) - Pointer auf Daten innerhalb von Datenblöcken kann die GC nicht aktualisieren. => Immer Array plus Index benutzen! => Bei Zuweisungen die Adresse der Zielvariablen nach dem Wert berechnen! (RTL evaluation in operator =, += etc.) Vereinfachende Annahmen: - Kein Finalizer: Entsprechende Objekte, z.B. mit File-Handles, müssen selbst aufgeräumt werden. - Der Structdaten-Descriptor ist ein einfacher uint8-Array mit den Offsets der allocated Members, gerade die minimale Information für den GC, ohne Reflection, Inspection oder virtuellen Funktionen. Alle Daten werden als ein großer Struct angesehen: Eine root-Variable zeigt auf den Shadowstack, der als Array mit alloc. Items geflaggt ist. Die Länge steht evtl. normalerweise auf max. Shadowstack-Größe, wird aber für die GC entsprechend shadow_SP gekürzt. Bei mehreren Threads gibt es nicht einen Shadowstack sondern einen Array von Shadowstacks. Die globalen Variaben werden als ein Struct angesehen und als erste Variable auf den Shadowstack gepusht. Dazu müssen sie zusammen liegen und dürfen nicht über den ganzen Speicher verteilt sein. (uint8-Offsets.) Ggf. sind mehrere globale Variablen (z.B. eine je Modul) möglich. Bei mehreren Threads kommen die Globals mit in den Shadowstack-Array. Structdaten-Descriptor: Bei Structs wird eine Liste (Array) aller Offsets benötigt, an denen Data Members mit Heapdaten stehen. Diese Arrays müssen außerhalb des Heps, z.B. im Programmcode stehen. Daten, auf die auch während einer GC zugegriffen werden soll, dürfen durch die GC nicht verschoben werden. Das ergibt sich automatisch, wenn alle derartigen Variablen vor allen anderen angelegt und nie wieder gelöscht werden oder wenn sie außerhalb des Heaps angelegt werden. Speicheraufteilung: (Z80-SRAM-Board) $0000 Restart vectors and Interrupt entry $0080 System global data $0100 User program $3800 Shadow stack (bottom up) Stack (top down) $3F00 Heap (bottom up) $7F00 SIO buffers $8000 Eeprom (32k) System global data: .org $80 ds 2 ; my block.size globals: ds 2 ; -> my struct.offsets[] locals: ds 2 ; -> shadow stack heap_start: ds 2 ; start des normalen heaps heap_ptr: ds 2 ; ende des belegten bereichs (excl.) = start des freien bereichs im heap heap_end: ds 2 ; ende des heaps (excl.) (evtl. eine Konstante) gc_i: ds 1 ; during GC: index of current item in parent struct.offsets[] gc_bua ds 2 ; during GC: pointer to start of helper array bu[] gc_bue ds 2 ; during GC: pointer to end of helper array bu[] … Blöcke im Heap und anderswo: dw size -> db data[] Blöcke enthalten Structs und Arrays. Struct- und Array-Variablen enthalten nur einen Pointer auf block.data ihres Blocks. Mehrere Variablen können auf einen Block zeigen. (shared) Oder keine Variable zeigt auf einen Block. (unused, free) Variablen können auch $0 enthalten. (null-Pointer) !!! Blöcke dürfen nicht im Eeprom liegen, es sei denn, die GC-Routinen unterdrücken hier Schreibzugriffe auf Bit15. block.size enthält in Bit15, bit14 und evtl. in bit13 Flags. Diese Bits müssen beim Bestimmen der Blockgröße (z.B. für array.count()) maskiert werden. block.size.bit15: Dieses Bit wird von der GC gesetzt und gelöscht, um bei der Rekursion über alle Variablen eine mehrfache Bearbeitung von Variablen zu verhindern. Nach dem 1. Durchlauf ist das Bit in allen benutzten Blöcken gesetzt und kann so zum Erkennen von benutzten und unbenutzten Blöcken dienen. Normalerweise ist Bit15 immer 0. Während die GC läuft, kann Bit15 gesetzt sein. Das muss berücksichtigt werden, wenn Interrupt-Routinen auf Heap-Daten zugreifen dürfen. block.size.bit14: Dieses Bit zeigt an, dass dieser Block Daten enthält, die selbst wieder auf Blöcke (auf dem Heap) zeigen. block.size.bit13: Dieses Bit ist nur ein Flagbit, wenn Bit14 gesetzt ist. Dann zeigt es an, ob dieser Block ein Array (bit13=0) oder ein Struct (bit13=1) ist. Bei Arrays sind dann alle Array Items allocated Items. Bei Structs enthält block.data[0,1] einen Pointer auf einen uint8-Array, mit den Offsets aller allocated Items im Struct. Note: Structs ohne allocated Items werden wie Arrays ohne allocated Items angelegt und haben keine Offset-Tabelle. Daraus ergeben sich folgende Maximalgrößen: Flat Array ohne allocated Items: max.size = 0x3FFF. (bit15=0, bit14=0) => max.size = 16kB - 1 Flat Struct ohne alloc. Items: max.size = 0x3FFF. (bit15=0, bit14=0) Array mit allocated Items: max.size = 0x1FFF. (bit15=0, bit14=1, bit13=0) => max.size = 8kB-1; max.count = 4k-1 Struct mit allocated Items: max.size = 0x00FF. (bit15=0, bit14=1, bit13=1) 0> max. 0xFF wg. Offset-Tabelle Garbage Collection: 1. Rekursion über alle Variablen: in allen Heap-Variablen wird bit15 in block.size gesetzt. => Das Bit markiert dann benutzte Blöcke, ungenutzte haben bit15 danach nicht gesetzt. => Das Bit dient auch dazu, das mehrfache Durchlaufen des selben Arrays oder Structs zu unterbinden. 2. ein Hilfsarray bu[] von ca. 256 Bytes wird besorgt. idR. kann der auf dem Stack angelegt werden. Aber auch im verbliebenen Freiraum im Heap oder in einem SIO-Sendepuffer. 3. Schleife über alle Blöcke: Die Blöcke auf dem Heap werden durchlaufen. Jede Gruppe belegter Blöcke wird in bu[] mit Startadresse und Verschiebeweite vermerkt und der Bereich nach unten geschoben. Ende wenn das Heap-Ende erreicht ist oder bu[] voll ist. Ist bu[] voll, werden die verbliebenen Lücken in diesem Durchlauf nicht geschlossen! 4. Rekursion über alle Variablen: in allen Heap-Variablen wird bit15 in block.size gelöscht. => Zu jeder Variable wird in bu[] der zugehörige Offset gesucht. (sorted list search.) => Dieser Offset wird zur Variablen addiert. (kann 0 sein.) Diese zeigt somit wieder auf ihren Block. => danach kann auf den Block im Heap zugegriffen und bit15 gelöscht werden und ggf. die Rekursion durchlaufen werden. set_bit15: ( hl->var -- ) ld ix,fu ; ix -> fu fu: de = peek(hl) ; de -> block.data ret z ; var = null dec de ; de -> block.size.hi a = peek(de) ; block.size.hi if a.bit7 ret ; bit15 schon gesetzt set 7,(de) ; set bit15 if a.bit6==0 ret ; no allocated items handle_recursion: ( ix->fu, de->block.size.hi ) if (a.bit5==0) goto array; struct: push gc_i offsets = peekw(block+0); n = offsets.size a = offsets e = a + n while(a p) l = idx + 1; else return p; } return NULL; } addr bsearch_in_range ( addr key, addr base, uint nmemb, uint size ) { uint idx; uint l = 0; uint u = nmemb; addr p; while (l < u) { idx = (l + u) / 2; p = base + idx * size; if (key < *p) u = idx; // select lower half else l = idx; // select upper half } return p; } addr bsearch_in_range ( addr key, addr array, uint count ) { uint n = count; addr p = array p = p + n/2; // p-n/2 ... p ... p+(n+1)/2 // id n is odd then upper half is larger while (n > 1) { if (key < *p) { n = n/2; p = p - (n+1)/2; } // lower half else { n = (n+1)/2; p = p + n/2; } // upper half } return p; }