doc/collect.doc

   1 /*************************** doc/collect.doc ***********************************
   2
   3         Copyright (c) 1997 A. Krall, R. Grafl, M. Gschwind, M. Probst
   4
   5         See file COPYRIGHT for information on usage and disclaimer of warranties
   6
   7         Enth"alt die Beschreibung des Garbage Collectors
   8
   9         Authors: Reinhard Grafl      EMAIL: cacao@complang.tuwien.ac.at
  10
  11         Last Change: 1996/11/14
  12
  13 *******************************************************************************/
  14
  15 Generell:
  16
  17 F"ur den CACAO habe ich einen recht einfachen Mark and Sweep - Collector
  18 implementiert, mit dem der Speicher immer dann ges"aubert wird, wenn
  19 eine Anforderung nicht zufriedenstellend durchgef"uhrt werden
  20 kann (im Klartext: der GC l"auft NICHT in einem eigenen Thread).
  21
  22 Der Heap ist ein einziger Speicherblock, der gleich zu Programmstart
  23 angelegt wird, und dessen Gr"osse sich nicht mehr "andern kann.
  24 (also immer gleich gen"ugend Speicher anlegen! Bei Maschinen mit
  25 virtuellem Speicher sollte das kein Problem sein)
  26
  27 Der Collector verschiebt keine Objekte im Speicher, und er kommt mit
  28 minimaler Information "uber die innere Struktur der Objekte aus
  29 (um es pr"aziser zu sagen: Der GC nimmt bei allen Daten einmal an,
  30 dass es sich dabei um Zeiger auf Objekte in den Heap handelt. Wenn
  31 irgendwelche Zahlen z"uf"allig einen g"ultigen Zeiger auf ein Objekt
  32 darstellen, dann wird dieses Objekt eben nicht freigeben.)
  33
  34 Der Heap ist in kleine unteilbare Einheiten aufgeteilt, die nur immer
  35 als ganzen vergeben werden k"onnen (Heap-Bl"ocke), deren Gr"osse
  36 auf jeden Fall die in Java n"otigen Alignment-Bedingungen erf"ullt.
  37
  38
  39 Notwendige zus"atzliche Datenstrukturen
  40 ---------------------------------------
  41
  42 Der GC muss auf jeden Fall wissen, wo im Heap g"ultige Objekte stehen
  43 (damit die Markierung mit m"oglicher- (aber nicht notwendigerweise)
  44 g"ultigen Zeigern richtig funktioniert).
  45
  46 Dazu verwaltet er ein Bitfeld ('startbits'), in dem f"ur jeden Heap-Block
  47 eintr"agt, ob an der Stelle ein Objekt anf"angt. Zu"atzlich werden auch
  48 alle FREIEN Speicherbereiche mit so einem Bit markiert.
  49
  50 Ein zweites Bitfeld ('referencebits') gibt an, ob in dem Objekt, das
  51 an der Stelle anf"angt, noch weitere Referenzen auf andere Objekte
  52 gespeichert sein k"onnen.
  53 (Damit die Markierungsphase fr"uhzeitig abgebrochen werden kann)
  54
  55 Beispiel:
  56
  57 Heap:          | Obj1 |  Obj2 |     frei     | Obj3 | Obj3 |  frei   |
  58                -------------------------------------------------------
  59
  60 startbits:     100000010000000100000000000000100000010000001000000000
  61
  62 referencebits: 100000000000000000000000000000100000000000000000000000
  63
  64
  65 (in obigem Beispiel k"onnten Obj1 und Obj3 noch weitere Referenzen
  66 enthalten)
  67
  68 Man beachte: Die Bitfelder werden nur soweit benutzt, als tats"achlich
  69 schon Platz am Heap vergeben worden ist (wird mit Hilfe einer globalen
  70 Variable 'topofheap' gehandhabt). Alle dar"uberhausgehenden Bits sind
  71 noch 0. Das letzte Objekte im Heap (oder der freie Speicherbereich)
  72 wird also nicht mit so einem 1-Bit abgeschlossen.
  73
  74
  75 Vorgangsweise beim Anlegen eines neuen Objektes
  76 -----------------------------------------------
  77
  78 In einer Freispeicherliste sind alle freien Bereiche eingetragen
  79 (die Freispeicherlisten verwenden dabei gleich den freien Speicher
  80 f"ur die notwendige Verkettung).
  81 Zuerst muss beliebiger passender Bereich gesucht werden.
  82
  83 1. Fall: Bereich hat genau die richtige Gr"osse
  84         - Aus der Freispeicherliste austragen
  85         - gegebenenfalls das zugeh"orige Bit im Feld 'referencebits'
  86           setzen
  87         - fertig
  88
  89 2. Fall: Bereich ist gr"osser als notwendig
  90         - Aus der Freispeicherliste austragen.
  91         - In Liste das Restst"uckchen eintragen
  92         - Ein Bit im Bitfeld 'startbits' eintragen, wo der neue freie
  93           Speicher anf"angt.
  94         - gegebenenfalls das dem neuen Objete zugeh"orige Bit im Feld
  95       'referencebits' setzen
  96         - fertig
  97
  98 3. Fall: Es ist kein freier Bereich mehr in der Freispeicherliste
  99         - das neue Objekte wird ganz oben am Heap angelegt
 100         - Bit im Bitfeld 'startbits' am der Stelle 'topofheap' eintragen.
 101         - den 'topofheap'-Z"ahler im die Objektel"ange erh"ohen
 102         - eventuell ein Bit in 'referencebits' setzen
 103         - fertig
 104
 105 4. Fall: Es ist zuwenig Speicher mehr oben im Heap "ubrig
 106         - Garbage Collection durchf"uhren
 107         - alles nocheinmal probieren
 108
 109
 110 Vorgangsweise zur Garbage Collection
 111 ------------------------------------
 112
 113 Ein drittes Bitfeld ('markbits') wird ben"otigt, das zuerst mit
 114 0 initialisiert wird.
 115
 116 In der Markierungsphase werden alle Objekte durchgegangen, die
 117 von irgendwo im Stack oder von globalen Variablen aus erreichbar
 118 sind.
 119 Ein Zeiger zeigt tats"achlich auf ein g"ultiges Objekt im Heap, wenn:
 120         - Der Zeiger in den Bereich des Heap zeigt
 121         - Der Zeiger richtiges Alignment hat (auf Blockgr"osse)
 122         - Das zugeh"orige Bit in 'startbits' gesetzt ist
 123
 124 Wenn das der Fall ist, und das Bit in 'markbits' noch nicht gesetzt ist,
 125 dann wird dieses Bit jetzt gesetzt, und wenn noch dazu das Bit in
 126 'referencebits' gesetzt ist, dann werden alle Referenzen vom Objekt
 127 rekuriv ebenfalls markiert.
 128 Die L"ange des Objektes erf"ahrt man aus dem 'startbits'-Feld. Man muss
 129 nur den n"achsten 1er suchen (oder vorher abbrechen, wenn man die
 130 Stelle 'topofheap' erreicht).
 131
 132
 133 Beispiel:
 134
 135 Heap:          | Obj1 |  Obj2 |     frei     | Obj3 | Obj4 |  frei   |
 136                -------------------------------------------------------
 137
 138 startbits:     100000010000000100000000000000100000010000001000000000
 139 markbits:      000000010000000000000000000000100000010000000000000000
 140
 141 referencebits: 100000000000000000000000000000100000000000000000000000
 142
 143 In dem Beispiel wurden nur mehr Obj2 und Obj3 als erreichbar erkannt,
 144 die anderen Objekte wurden nicht erreicht.
 145
 146 Anmerkung: Es k"onnte hier passieren, dass ein freier Speicherbereich
 147         irrt"umlich als Objekte markiert und f"ur den folgenden
 148         Sweep-Durchlauf blockiert wird. Das sollte aber nur SEHR selten
 149         vorkommen.
 150
 151
 152 Nach der Markierungsphase sieht man schon, dass einige Objekte
 153 weggeworfen werden sollen. Damit die zu diesen Objekte geh"orenden
 154 'referencebits' ebenfalls gel"oscht werden, braucht man nur
 155 ein logisches UND der beiden Bitfelder 'markbits' und 'referencebits'
 156 durchf"uhren, und das Ergebnis in 'referencebits' speichern.
 157
 158 Obiges Beispiel:
 159
 160 markbits:      000000010000000000000000000000100000010000000000000000
 161 referencebits: 100000000000000000000000000000100000000000000000000000
 162 ---------------------------------------------------------------------
 163          UND   000000000000000000000000000000100000000000000000000000
 164
 165
 166
 167
 168
 169 F"ur die Sweep-Phase wird der gesammte Bereich linear durchgegangen,
 170 und alle freien Bereiche in die Freispeicherliste eingeh"angt.
 171
 172 Dazu wird der Anfang des ersten freien Bereiches gesucht, und zwar indem
 173 nach der erste Stelle gesucht wird, an der ein startbit GESETZT ist,
 174 aber das markbit NICHT gesetzt ist.
 175 Das Ende des freien Bereiches findet man dort, wo das n"achste
 176 markbit GESETZT ist.
 177 (dabei werden auch automatisch hintereinanderliegenden Speicherst"ucke
 178 zusammengefasst)
 179 Den gesammten Bereich kann man jetzt in die Freispeicherliste einh"angen,
 180 und gleichzeitig muss noch ds markbit, an dem der Bereich anf"angt,
 181 gesetzt werden (wozu, das wird weiter unten erkl"art)
 182
 183 F"ur alle folgenden Bl"ocke geht man genauso vor, bis das Ende des
 184 Heaps erreicht ist.
 185 Die oben erw"ahnten Bit-Suche-Operationen gehen - wenn man sie gut
 186 implementiert - relativ rasch (z.B. mit 64-Bit-Operationen auf einer
 187 DEC-Alpha).
 188
 189
 190 Der Grund, warum man alle freien Bereiche mit einem zus"atzlichen
 191 Markierungsbit versieht ist der, dass jetzt zu Ende des Sweep in
 192 'markbits' genau diejenige Bits stehen, die eigentlich auch in
 193 'startbits' geh"oren, n"amlich eine Kennzeichnung aller lebenden
 194 Objekte und aller Freispeicherbereiche.
 195
 196
 197 Fortsetzung des obigen Beispiels:
 198
 199 Heap:          | frei |  Obj2 |     frei     | Obj3 |  frei          |
 200                -------------------------------------------------------
 201
 202 startbits:     100000010000000100000000000000100000010000001000000000
 203 markbits:      100000010000000100000000000000100000010000000000000000
 204
 205 referencebits: 000000000000000000000000000000100000000000000000000000
 206
 207
 208 Durch einfaches Umkopieren der 'markbits' auf die 'startbits'
 209 (oder noch besser: durch Austauschen der beiden Zeiger) ist der
 210 Garbage-Collection-Durchlauf abgeschlossen.
 211
 212