Go GC: tricolor marking, concurrent and correct

The motivation: automatic reclamation without stopping the world for long. A Go program allocates constantly and never frees by hand, so the runtime must find garbage on its own. The naive way is to stop everything, walk every reachable object, and free the rest, but a long stop is a latency spike in a long-running service. Go therefore marks concurrently while the program keeps running, and the whole design exists to keep that concurrent marking correct.

Tricolor: unvisited, half-visited, fully visited. Every object starts white, meaning unvisited and a candidate for reclamation. Roots (globals, stack pointers, registers) are shaded grey first. Grey means visited but its children not yet scanned; black means visited and all its children scanned. Marking proceeds by taking a grey object, shading its children grey, and turning it black, until no grey object remains. Whatever is still white at that point is unreachable and therefore garbage. White, grey, black map exactly to unvisited, half-visited, fully visited.

The tricolor invariant, and how concurrency breaks it. The strong invariant says: a black object never points directly to a white object. If it held while marking ran concurrently, no live object could be missed. But the program keeps mutating pointers during marking, and two mutations together break it: a black object gains a new pointer to a white object, while the white object's only other path is deleted. The white object is still live, but nothing grey leads to it anymore, so marking finishes without ever visiting it, and it gets freed while still in use. That is the fatal failure the rest of the design prevents. The weaker form is worth knowing too: a black object may point to a white object only if that white object is also reachable through some grey object, so a grey protector still leads marking to it. The barrier's job is to keep at least the weak form true at all times.

The write barrier: shade on write. The barrier runs on every pointer write during marking. The insertion barrier shades a white target grey when a black object gains a pointer to it. The deletion barrier shades the old target grey when a pointer is overwritten or deleted, in case that was the last path to it. Go uses a hybrid of the two: heap writes go through the barrier, while stacks are not barriered and are instead rescanned during the terminating stop. The barrier's job is one sentence: no white object that is still reachable may survive marking unvisited.

Stop-the-world happens at both ends, and only there. Marking starts with a short stop: enable the write barrier and shade the roots grey. Then marking runs concurrently with the program. Marking ends with a second stop: rescan the roots and stacks, disable the barrier, and compute the next trigger. Those two stops are the only pauses; everything between them runs alongside the program. Their length is where latency spikes in a long-running service come from.

After marking: sweep. White objects are reclaimed and their memory returned for reuse. Sweeping itself can run concurrently with the program, so reclamation does not need another stop.

GOGC: the trigger, not the algorithm. GOGC sets how much the heap may grow after a collection before the next one starts: next trigger equals live heap after the last collection times one plus GOGC over one hundred. The default 100 means the heap may double before the next collection. Larger GOGC means fewer collections and more memory; smaller means more frequent collections and less memory. It trades collection frequency against memory, nothing else. A soft memory ceiling, GOMEMLIMIT, can be set alongside it.

Marking shares the P. Marking work runs on the P's workers, and a goroutine that allocates too fast while marking lags is drafted into mark assist: it does some marking work itself before its allocation proceeds. Allocation pays for marking, which keeps marking from falling behind allocation.

Production note. In a long-running backend, GC latency spikes trace back to the two stops and to marking falling behind allocation. The usual levers are GOGC and GOMEMLIMIT, reducing allocation, and avoiding very large heaps, in that order.