Tricolor Abstraction: Foundations of Concurrent Garbage Collection

Automatic memory management systems often rely on tracing garbage collectors (GC) to reclaim unused heap memory. A naive implementation of a tracing collector—such as classical Mark and Sweep—requires pausing all program execution while the collector traverses the reference graph from the root set. This interruption is known as a Stop-the-World (STW) pause.

While simple and correct, STW garbage collection degrades tail latency and limits overall application throughput. To build modern, high-performance runtimes, collectors must execute concurrently alongside application threads (often called mutators). Doing so safely requires a formal framework to prevent live memory from being reclaimed while references mutate under the collector’s feet. This foundation is the Tri-color Abstraction.

---

The Limitation of Stop-the-World Tracing

In a standard depth-first search (DFS) Mark-and-Sweep implementation, the collector operates in two distinct phases:

1. Mark Phase: Traverse the object reference graph starting from the roots (thread stacks, global variables, registers). Every reachable node is flagged as alive.
2. Sweep Phase: Iterate through the entire heap linearly. Any node that remains unmarked is dead (unreachable) and has its storage reclaimed.

Heap Memory Graph Traversal (Traditional STW DFS):

[Roots] ---> (Object A) ---> (Object B)       (Object D - Unreachable)
                  |                                 |
                  v                                 v
             (Object C)                       (Object E)

If the application continues running while this graph traversal occurs, the application can modify pointers. For example, if a background GC thread passes Object A without visiting its children, and the application suddenly rewires an unvisited child to an already-processed object, the unvisited child might never be marked. When the sweep phase executes, that reachable child will be freed, corrupting runtime memory.

To prevent this memory corruption, traditional runtimes halt all mutator threads during marking. As heap sizes grow into tens or hundreds of gigabytes, STW pause times scale proportionally, making real-time or low-latency systems impractical.

---

The Tri-Color Abstraction

Formulated by Edsger Dijkstra, Leslie Lamport, and collaborators in their seminal 1976/1978 work on “On-the-fly Garbage Collection”, the tri-color abstraction maps object states during tracing into three mutually exclusive sets:

Color	Set Meaning	Traversal Status	Direct Outgoing References
White	Unvisited / Candidate Garbage	Not yet encountered by the collector.	Unknown.
Gray	Visited / Processing	Visited by the collector, but its children have not yet been scanned.	May point to White, Gray, or Black nodes.
Black	Visited / Live	Visited, and all its direct references have been discovered and pushed to Gray.	Guaranteed never to point directly to a White node.

stateDiagram-v2
    direction LR
    [*] --> White: Object Allocated
    White --> Gray: Reached via Roots or Gray Parent
    Gray --> Black: All Outgoing Pointers Inspected
    White --> [*]: Swept at GC Completion
    Black --> [*]: Retained (Reset to White for next cycle)

The Lifecycle of an Object During Marking

1. Initial State (All White): At the beginning of the garbage collection cycle, all objects in the heap are placed in the White set.
2. Root Seeding (White $\to$ Gray): Root references (stack frames, globals) are scanned. The immediate objects they reference transition from White to Gray.
3. Scanning Frontier (Gray $\to$ Black): A collector thread dequeues an object from the Gray set. It inspects all outgoing pointers of that object:
   • Any child object that is currently White is moved to the Gray set.
   • Once all outgoing edges of the current object are accounted for, the current object moves into the Black set.
4. Termination: The mark phase terminates when the Gray set is completely empty.
5. Reclamation: Objects remaining in the White set were never reached from any root or gray frontier. They are provably dead and can be safely reclaimed.

---

The Wavefront Analogy

You can visualize the tri-color abstraction as a wavefront of gray nodes sweeping across the object graph:

[ Roots ]
   |
   v
[ BLACK NODES ]  <--- Completely processed & preserved live objects
   |
   v
[  GRAY WAVE  ]  <--- The active frontier separating Black from White
   |
   v
[ WHITE NODES ]  <--- Unvisited candidates (Live objects + Garbage)

Behind the gray wave lies an expanding sea of black nodes (known live objects whose subgraphs are actively being explored). Ahead of the gray wave lies the white nodes. The wave expands forward until no reachable white nodes remain, leaving only isolated, unreachable white islands behind to be swept.

---

The Tri-Color Invariant and Correctness

The fundamental correctness guarantee of any concurrent tracing garbage collector depends on enforcing a single critical rule:

$\text{No Black object may directly reference a White object.}$

$\mathbf{Black} \not\to \mathbf{White}$

Why Violating the Invariant Causes Collector Failure

Consider the scenario where the mutator runs concurrently with the collector without any barriers:

1. Collector marks node $A$ as Black (it has visited all of $A$‘s original children).
2. Collector marks node $B$ as Gray (queued to be scanned). Node $B$ currently holds a reference to a White node $C$.
3. The application mutator executes concurrently and performs two operations:
   • It writes a pointer to $C$ into $A$ ($A \to C$).
   • It deletes the pointer to $C$ from $B$ ($B \not\to C$).
4. The collector resumes scanning $B$. Node $B$ no longer points to $C$, so the collector finishes scanning $B$ and turns $B$ Black.
5. Because $A$ is already Black, the collector will never re-examine $A$‘s outgoing pointers.
6. Node $C$ remains White until the end of the collection cycle despite being referenced by live object $A$.
7. The sweep phase frees $C$, resulting in a dangling pointer and heap corruption.

Because of the Tri-color Invariant, runtime environments can eliminate this race condition. If a program attempts to introduce a reference from a Black object to a White object, the runtime intervenes (typically using a Write Barrier) to keep the invariant intact—either by turning the target White node Gray or by regressing the Black node back to Gray.

---

Algorithmic Tracing Flow

def concurrent_mark(roots, heap):
    # Step 1: Initialize all heap objects as White
    white_set = set(heap.all_objects())
    gray_set = set()
    black_set = set()

    # Step 2: Seed the gray frontier with objects directly referenced by roots
    for root in roots:
        target = root.dereference()
        if target in white_set:
            white_set.remove(target)
            gray_set.add(target)

    # Step 3: Process the gray set incrementally / concurrently
    while len(gray_set) > 0:
        current = gray_set.pop()

        for child in current.outgoing_references():
            if child in white_set:
                white_set.remove(child)
                gray_set.add(child)

        # All direct children inspected; transition node to black
        black_set.add(current)

    # Step 4: Any node remaining in white_set is unreachable garbage
    return white_set

---

Enabling Concurrency: Reactive and Multi-Threaded GC

Re-architecting graph traversal into explicit White, Gray, and Black sets changes GC from a monolithic, single-threaded batch job into a concurrent, reactive pipeline:

1. Multi-Threaded Mark Workers

Because the Gray set acts as a thread-safe worklist or task queue, multiple garbage collection worker threads can operate in parallel. On an 8-core or 16-core CPU, several background threads can pull items from the gray set concurrently, scan outgoing references, and append discovered white objects back into the gray frontier without halting the universe.

2. Reactive, Incremental Execution

Rather than executing full scans periodically, the runtime can process objects reactively. When the gray frontier exceeds a specific threshold (e.g., thousands of pending references), background threads can consume a batch of gray objects, incrementally amortizing GC costs across program execution.

3. Mutator Cooperation (“On-the-Fly” GC)

In an “on-the-fly” model, mutator threads (application threads executing user logic) actively assist the collector. When application threads allocate new memory or modify reference pointers on the heap, they participate in coloring actions. By cooperating through write barriers, mutators ensure that newly established relationships are tracked in real-time, reducing STW pause times to near-zero synchronization points.

---

Summary of Key Takeaways

• Stop-the-World Limitations: Classical mark-and-sweep stops program execution to guarantee that the pointer graph does not mutate while being traversed.
• Three-Color Semantics:
  • White: Unseen candidates for collection.
  • Gray: Reachable frontier nodes awaiting child inspection.
  • Black: Live objects whose direct references have been fully traversed.
• The Tri-Color Invariant: A Black node must never hold a direct reference to a White node. Maintaining this invariant prevents live objects from being collected during concurrent execution.
• Foundation of Modern Collectors: The tri-color abstraction is the theoretical engine driving low-latency and concurrent collectors across modern platforms (such as the Go runtime collector, Java ZGC/Shenandoah, and modern V8 implementations).