It's a tri-color mark and sweep GC, algorithm as described in wiki.
Multiple Free List
A free-list is implemented implicitly by tcmalloc. Tcmalloc means Thread Caching malloc. The cache is in fact a thread-local free-list. Linking with
-ltcmalloc will replace
frees with thread-cache ones.
A GC always has strong binding with object representation. Here is the very baby design of heap object header:
1 2 3 4 5 6 7 8 9 10 11 12
For simpleness, we assume pointers are 64 bit only. User level pointers have highest 16 bits free, so we can use these bits for coloring and storage information.
Object storage type can be:
-2: hash table,
-1: rb-tree table,
0: no type, for example, string
TupleObj, for example, a struct
Like lua GC, all allocated objects are linked in a list.
Here, a stack is used for gray objects. In single mark step, an object is popped, then its non-black children are pushed as gray.
A GC cycle is separated into steps. A step can be:
During init step, a snapshot is taken and the gray set is initialized.
A write barrier (
GC::mark()) is needed when object children changed during mutator.
TODO more details