Tricolor Concurrent Mark-Sweep Garbage Collection

Tricolor Concurrent Mark-Sweep Garbage Collector

Objects get marked white, gray, or black.

At first, all objects are white. Then we scan from goroutine stacks and global variables. When we see an object, we mark it gray. When all references from an object get marked, we make it black.

Marking

Stop the running program. In the dependency graph, find objects that processes still reference and mark them. Objects that don’t get marked become unreachable garbage.

BFS marking algorithm:

Start from root nodes in a directed graph (or linked list). BFS marks first layer black, second layer gray. Then gray layers with references get painted black. Third layer gets painted gray. Keep going until no new references appear. What’s left white becomes what we clear.

Problem: If we handle this concurrently, the graph keeps adding references. How do we prevent wrong clearing?

1. If it’s a new referenced object, paint it gray
2. If it’s a pointer reference change: insert a gray-painting function at assignment expression spots

Scanning

At first, all elements are white. This means GC hasn’t started work yet. When GC starts, all root elements get painted gray. Then each time GC starts scanning gray elements, it scans one and paints it black. Then it paints that element’s children gray.

Runtime Functions

runtime.SetGCPercent runtime.GC runtime.FreeOSMemory