README

   1 Acogc (accurate cooperative garbage collector) is the garbage collector used for the MaLa extension langauge.
   2
   3 Features:
   4     * simple optimized mark is sweep (stop&copy without copying)
   5     * can coexist with other allocation strategies, implemented on top of malloc/free
   6     * main goal is beeing small and embeddable, not performance
   7     * accurate collection (not conservative), might ideally lead
   8       to better performance (not proofed) but does never keep garbagge around
   9     * cooperative, the user has to supply custom marker functions for his objects
  10     * NOT intrusive the GC descriptor is opaqe, it's blocks are before the user data
  11     * swept objects are not destroyed and pooled in free-queue and for faster reallocation,
  12       real freeing is done on utilization policies.
  13     * supports weak references
  14     * weak references to swept but not yet freed objects can be reinstantiated
  15       for efficent caching strategies
  16     * non-collectable objects can coexist with garbage collected objects
  17     * collects statistics and let the GC tune itself dynamically
  18     * Proactive collection, the user can provide callback functions which invalidate
  19       referenced objects at collect time if they are not useful anymore
  20
  21
  22 Algorithm:
  23
  24 Marking is Sweeping or Stop&Copy without copying
  25
  26 marking moves objects to a live objects list,
  27 dead objects are left in a freelist so we don't need an explicit
  28 sweep cycle and the algorithm runs in O(LifeObjects) instead in O(AllObjects)
  29
  30 Cells:
  31
  32     * all cells are kept in double linked lists.
  33     * we use a monotonic incrementing counter as mark value (with some values reserved at the beginning for special marks)
  34
  35 Global:
  36
  37     * we have a list for root objects
  38     * a list of live objects
  39     * a list of free objects
  40     * a global mark counter
  41
  42 Allocation:
  43
  44     * if there is a object in the freelist then move it to the live list
  45     * if not malloc() a new object and/or do a collection
  46
  47 Collection:
  48
  49     * Increment the global mark counter value
  50     * resnap all objects of the live list to a temporary list
  51     * for all root objects mark their referenced objects recursively, by setting their mark to the new counter value and moving them to the live list.
  52     * when finished all remaining objects in the temporary are free and append them to the freelist.
  53
  54 Caution:
  55
  56     * we need to reset all marks in all objects before the counter overflows and then reinitialize the counter
  57
  58  Future:
  59
  60     * implement block pooling which keeps some objects in biggier blocks
  61     * since we have this counting mark we can easily extend the scheme to a generational algorithm