notes/GarbageCollection.txt

   1 The garbage collection algorithm is based on Joel Bartlett's mostly
   2 copying scheme.  Here's our setup:
   3
   4    (1)  Collectable and non-collectable heaps can coexists in our
   5         framework.  Both cross heap pointers and interior pointers are
   6         allowed.
   7    (2)  The collectable heap is partitioned into ``logical pages.''
   8         Logical pages are different than virtual member pages used
   9         by the OS.  Collectable objects can span multiple pages.
  10         However, when an object within a page is promoted, then
  11         the entire page is retained.
  12    (3)  Collectable objects must be derived from the class GCObject
  13         defined in the file <AD/gc/gcobject.h>.  The virtual method
  14
  15            void trace(GC *);
  16
  17         must be redefined in each subclass.  The rules for deriving
  18         a new trace method is as follows:
  19
  20         (a)  The trace method for a GCObject subclass Foo has the following
  21              form:
  22
  23              void Foo::trace(GC * gc)
  24              {
  25                 ...
  26              }
  27
  28          (b) If class Foo has a member pointer p to a collectable object, then
  29              it must be traced by adding a trace call of the following form
  30              to the body.
  31
  32                   gc->trace(p);
  33
  34          (c) If class Foo has a non-virtual baseclass Bar that is
  35              a GCObject subclass then add the call
  36
  37                    Foo::trace(gc);
  38
  39          (d) If class Foo has a collectable subobject x then add the call:
  40
  41                    x.trace(gc);
  42
  43    (4)  The algorithm operates in the following manner:
  44
  45         (a)  The registers, stack, static data area and the non-collectable
  46              heap areas are scanned conservatively for live objects.
  47              The pages on which these objects are located are promoted.
  48              Promoted pages will survive the current collection phase.
  49              These live objects will not be moved since they may be pointed
  50              from a actual pointer from a non-collectable heap.
  51         (b)  All promoted pages are now scanned linearly.  Non-promoted
  52              objects reachable from a live object will be moved
  53              by calling the method ``trace'' of the object.  The new objects
  54              are copied into a new area and compacted together.
  55         (c)  When all object are copied.  The unpromoted pages are returned
  56              to the heap manager.  They are reused in subsequent allocation.
  57