Fil's Unbelievable Garbage Collector
Fil-C uses a parallel concurrent on-the-fly grey-stack Dijkstra accurate non-moving garbage collector called FUGC (Fil's Unbelievable Garbage Collector). You can find the source code for the collector itself in fugc.c, though be warned, that code cannot possibly work without lots of support logic in the rest of the runtime and in the compiler.
Let's break down FUGC's features:
Parallel: marking and sweeping happen in multiple threads, in parallel. The more cores you have, the faster the collector finishes.
Concurrent: marking and sweeping happen on some threads other than the mutator threads (i.e. your program's threads). Mutator threads don't have to stop and wait for the collector. The interaction between the collector thread and mutator threads is mostly non-blocking (locking is only used on allocation slow paths).
On-the-fly: there is no global stop-the-world, but instead we use "soft handshakes" (aka "ragged safepoints"). This means that the GC may ask threads to do some work (like scan stack), but threads do this asynchronously, on their own time, without waiting for the collector or other threads. The only "pause" threads experience is the callback executed in response to the soft handshake, which does work bounded by that thread's stack height. That "pause" is usually shorter than the slowest path you might take through a typical malloc implementation.
Grey-stack: the collector assumes it must rescan thread stacks to fixpoint. That is, GC starts with a soft handshake to scan stack, and then marks in a loop. If this loop runs out of work, then FUGC does another soft handshake. If that reveals more objects, then concurrent marking resumes. This prevents us from having a load barrier (no instrumentation runs when loading a pointer from the heap into a local variable). Only a store barrier is necessary, and that barrier is very simple. This fixpoint converges super quickly because all newly allocated objects during GC are pre-marked.
Dijkstra: storing a pointer field in an object that's in the heap or in a global variable while FUGC is in its marking phase causes the newly pointed-to object to get marked. This is called a Dijkstra barrier and it is a kind of store barrier. Due to the grey stack, there is no load barrier like in the classic Dijkstra collector. The FUGC store barrier uses a compare-and-swap with relaxed memory ordering on the slowest path (if the GC is running and the object being stored was not already marked).
Accurate: the GC accurately (aka precisely, aka exactly) finds all pointers to objects, nothing more, nothing less. llvm::FilPizlonator ensures that the runtime always knows where the root pointers are on the stack and in globals. The Fil-C runtime has a clever API and Ruby code generator for tracking pointers in low-level code that interacts with pizlonated code. All objects know where their outgoing pointers are - they can only be in the InvisiCap auxiliary allocation.
Non-moving: the GC doesn't move objects. This makes concurrency easy to implement and avoids a lot of synchronization between mutator and collector. However, FUGC will "move" pointers to free objects (it will repoint the capability pointer to the free singleton so it doesn't have to mark the freed allocation).
... continue reading