Notes on Garbage Collector - HaxeFoundation/hashlink GitHub Wiki

The HashLink Garbage Collector is a mark-and-not-sweep collector. The implementation is available in src/alloc.

He allocates system pages multiple of GC_PAGE_SIZE (64 KB) aligned memory.

Pages are discriminated by a type consisting of:

  • some pages are of fixed size blocks, (the first GC_FIXED_PARTS of GC_SIZES), some other are of variable size blocks multiples of the other GC_SIZES
  • whether the blocks allocated are vdynamic compatible (MEM_KIND_DYNAMIC = 0)
  • whether the blocks are not vdynamic compatible but might still contain pointers (MEM_KIND_RAW = 1)
  • whether the blocks do not contains any pointers (MEM_KIND_NOPTR = 2)
  • whether the blocks contain a finalizer function callback (MEM_KIND_FINALIZER = 3, implies RAW and NOPTR)

Pages are looked up using the gc_pages static.

Blocks have a bitmap consisting of a single mark bit per block. gc_mark() will mark all reachable blocks by scanning the C stack and the roots.

Variable block size pages have an extra sizes field which is a unsigned byte which is the number of physical blocks used for each logical allocation. A size of 0 mean that we're inside a logical block or a not allocated one.

Allocation uses CPU bit counting functions to lookup the bitmap for either the first unset bit (fixed size pages, see gc_alloc_fixed) or the first K unset bits (variable size pages, see gc_alloc_var).

The GC is mostly precise so it's using information provided by the type system (mark_bits) to only lookup for pointers. This prevents some double or int to be mistaken as a valid pointer and create a leak.