Tri-Color Incremental GC

After reading the book ガベージコレクションのアルゴリズムと実装, struggled through several decisions, I finally finished the alpha GC for my new language, spellbreak.

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 mallocs and frees with thread-cache ones.

Object Representation

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
struct Obj{
struct Tag {
uint8_t pad[6]; // pointer to next
uint8_t color; // 0:white, 2:black
int8_t storage;
};
union {
uint64_t p;
Tag tag;
} meta;
};

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:

  • -3: array, ArrayObj
  • -2: hash table, HashObj
  • -1: rb-tree table, TreeMapObj
  • 0: no type, for example, string
  • 1..127: tuple_like, TupleObj, for example, a struct

The GC

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.

Incremental

A GC cycle is separated into steps. A step can be:

  • init_step
  • mark_step
  • sweep_step

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

Comments