Tri-Color Marking — Garbage Collection

Overview

What this concept solves

Tri-color marking is a reformulation of mark & sweep that makes the marking phase interruptible — and that single property is what unlocks concurrent and incremental collection. Instead of one binary 'marked' bit, every object is one of three colors:

White — not yet reached. At the end of marking, white means garbage.
Gray — reached and known to be alive, but its outgoing pointers haven't been scanned yet. The 'work to do' set.
Black — reached and fully scanned; all its children are at least gray. Done.

Marking is just: move objects from white → gray → black. Start by graying the roots. Repeatedly take a gray object, gray each white object it points to, then blacken it. When no gray objects remain, the wavefront has swept the whole reachable graph — everything still white is unreachable and can be swept.

Why bother with three colors instead of one bit? Because the gray set is an explicit, resumable description of exactly how far marking has gotten. You can stop, let the program run, and pick up where you left off. A plain mark bit can't do that safely.

Mechanics

How it works

The invariant that makes it sound

The whole algorithm rests on one rule, the strong tri-color invariant: no black object may point to a white object. Intuitively: once you've declared an object fully scanned (black), you've promised the collector will never need to look at it again — so it had better not be the only thing keeping a white object alive. As long as the invariant holds, every reachable object eventually turns black.

Initialize. All objects white. Color the root-referenced objects gray and push them onto the gray queue.
Process a gray object. Pop it. For each object it points to that is white, color it gray and enqueue it. Then color the popped object black.
Repeat until the gray queue is empty.
Sweep. Every object still white is unreachable — reclaim it. Reset colors for the next cycle.

Why this matters: the concurrent hazard

If the collector runs while the program (the 'mutator') keeps running, the program can break the invariant. Picture a black object B and a white object D the collector hasn't reached. The program runs B.next = D — now a black object points to a white one. The collector, having already finished B, will never re-scan it; D stays white and gets swept. Later the program follows B.next into freed memory: use-after-free. This is the central problem every concurrent/incremental collector must solve.

Write barriers: insertion (Dijkstra) vs deletion (Yuasa)

The fix is a write barrier — a few instructions the runtime runs on every pointer store. Dijkstra's insertion barrier catches the store above: when a black object gets a pointer to a white one, it grays the target (or the source), restoring the strong invariant. Yuasa's deletion barrier (snapshot-at-the-beginning / SATB) takes the opposite tack: when a pointer is overwritten, it grays the old target, preserving the set of objects that were live when marking began — this maintains the weak invariant. Real collectors pick one or combine them; Go uses a hybrid Dijkstra+Yuasa barrier that drops worst-case stop-the-world pauses below 50µs.

Interactive prototype

Run it. Break it. Tune it.

Sandboxed simulation embedded right in the page. No setup, no install.

simulation › Tri-Color Marking

About this simulation

Tri-color marking colors every object white (unvisited), gray (reachable, but its pointers haven't been followed yet), or black (reachable and fully scanned). Marking pulls objects off the gray work queue until it's empty; whatever stays white is garbage. Pick a scenario and step through. Scenario 2 shows how a program mutating pointers during marking can break the algorithm; Scenario 3 shows the write barrier that fixes it.

Hands-on

Try these on your own

Open the prototype above, run each experiment, predict the answer, then verify.

try 01

Watch the wavefront advance

Run scenario 1 (Basic marking) and step through. Track the gray work queue: every step grays an object's white children, then blackens the object. Notice that the gray set is the boundary between fully-scanned black and untouched white — and that the strong invariant (no black→white pointer) holds at every single step.

try 02

Break it on purpose

Run scenario 2 (The concurrent bug). With no write barrier, watch the mutator run B.next = D after B is already black. Step to the end: D is swept while B still points to it. That's the use-after-free the invariant exists to prevent — see exactly which step plants the bug.

try 03

Let the barrier save it

Run scenario 3 (Write barrier saves the day). Same mutation, but now the Dijkstra barrier fires the instant B.next = D happens, graying D and re-adding it to the queue. Step through and confirm D ends up black — the collector traced a mutating heap correctly. This is how Go and G1 stay sound.

In practice

When to use it — and what you give up

Where it shows up

Any concurrent or incremental tracing collector — tri-color is the foundation. The colors are precisely the state you need to pause and resume marking safely.
Low-latency runtimes — Go, Java's G1 / ZGC / Shenandoah, and V8's concurrent marker all express their marking in tri-color terms.
When you must reason about correctness under mutation — the strong/weak invariants give you a precise, checkable property to preserve.

Real-world example

Go's garbage collector is a tri-color concurrent mark-sweep with a hybrid write barrier. Java's G1, ZGC, and Shenandoah collectors all mark concurrently using tri-color invariants (G1 and Shenandoah use SATB/Yuasa-style barriers). V8 does concurrent tri-color marking on background threads. In every case the white/gray/black abstraction plus a write barrier is what lets the collector trace a live, mutating heap without corrupting it.

Pros

Marking becomes pausable and resumable — the gray set captures exactly how far you've gotten.
Foundation for concurrent and incremental GC — lets the collector run alongside the program.
Correctness is a checkable invariant — 'no black → white pointer' is precise and easy to reason about.
Handles cycles — like all tracing, it's reachability-based.

Cons

Requires a write barrier under concurrency — every pointer store pays a small, constant cost.
Floating garbage — objects that die after being grayed/blackened survive this cycle (collected next time).
Extra per-object state — two bits of color (or color bitmaps) instead of one mark bit.
Barrier design is subtle — insertion vs deletion vs hybrid each have correctness and stack-rescanning trade-offs that are easy to get wrong.

Reference

Code & further reading

A minimal reference implementation and pointers worth bookmarking.

tri-color.ts

// Tri-color marking with a Dijkstra-style insertion write barrier.
type Color = "white" | "gray" | "black";
interface Obj { color: Color; refs: Obj[]; }

class TriColorMarker {
  private gray: Obj[] = []; // the work queue

  mark(roots: Obj[]): void {
    for (const r of roots) this.shade(r);  // gray the roots
    while (this.gray.length) {
      const obj = this.gray.pop()!;        // take a gray object
      for (const child of obj.refs) this.shade(child); // gray its white children
      obj.color = "black";                 // fully scanned
    }
    // anything still white is unreachable -> sweep it
  }

  /** white -> gray (and enqueue). Idempotent for gray/black. */
  private shade(o: Obj): void {
    if (o.color === "white") { o.color = "gray"; this.gray.push(o); }
  }

  /** Write barrier: run on every pointer store 'holder.field = target'.
   *  Dijkstra: graying the target restores "no black -> white". */
  writeBarrier(holder: Obj, target: Obj): void {
    this.shade(target);
    // (Yuasa/SATB variant would instead shade the *old* value being overwritten.)
  }
}

References & further reading

4 sources

Knowledge check

Did the prototype land?

Quick questions, answers revealed on submit. No scoring saved.

question 01 / 03

In tri-color marking, what does it mean for an object to be gray?

question 02 / 03

What is the strong tri-color invariant?

question 03 / 03

While the collector marks concurrently, the program runs `B.next = D`, where B is black and D is white. Why is a write barrier needed here?

0/3 answered