Garbage collection sounds like housekeeping.

It is not.

At the center of a tracing collector is a theorem about reachability. Start from the roots. Follow pointers. Anything you can reach must survive. Anything you cannot reach may be reclaimed.

That theorem is simple when the program is stopped.

It becomes slippery when the program keeps running.

The heap is a graph, and the program is allowed to change the graph while the collector is traversing it. A pointer can be installed after the collector has already scanned the source object. Another pointer can be deleted before the collector reaches the old path. A live object can slip between two moments of the traversal.

That is why a write barrier exists.

Not for performance, at least not first.

A write barrier remembers the mutation that would otherwise make the collector’s proof false.

First, the Easy Story

The classic tracing abstraction has two phases:

mark:  start from roots and mark everything reachable
sweep: reclaim everything unmarked

Wilson’s survey organizes garbage collectors around this kind of traversal: reference counting, mark-sweep, mark-compact, copying, incremental, and generational variants.1 The point is not that every production runtime is literally this simple. The point is that tracing collectors all have to answer the same question:

Which objects must not be freed?

Stop-the-world collectors buy a clean answer by pausing the mutator, the program that mutates the heap. Incremental and concurrent collectors try to avoid long pauses by interleaving collector work with mutator work.

Dijkstra, Lamport, Martin, Scholten, and Steffens framed this as cooperation between processes with weak synchronization: the collector operates while the computation keeps manipulating a shared data space.2 Lamport’s later note about the paper is charmingly sobering: a convincing proof still hid a serious error until another proof attempt exposed it.3

That is the right emotional posture for garbage collection.

It is a graph algorithm with a hostile scheduler.

Colors Are the Collector’s Proof Notes

Tri-color marking is the clean mental model:

white: not yet reached by the collector
gray:  reached, but outgoing pointers not scanned yet
black: reached, and outgoing pointers already scanned

At the end, white objects are swept.

The dangerous state is a black object pointing to a white object that is still live. The collector will not scan the black object again. If no gray object can lead to that white object, the white object may be freed while the program still has a path to it.

So the invariant is not merely “eventually visit all objects.” It is more like:

Do not let black objects hide white reachable objects.

Write barriers maintain that invariant when the mutator stores pointers during collection.

A Tiny Heap Race

The lab below uses a fixed object graph. The collector begins by scanning root object A, making it black. Then the mutator gets a turn.

The dangerous mutation is:

A gets a pointer to D.
B drops its old pointer to D.

Now D is live through black object A, but the collector has already scanned A. Without a barrier, D and E remain white and would be swept.

The collector always scans root object A first. Then the mutator acts. The sweep would reclaim every object left white at the end.

Start with No barrier and Hide a white live object. The lab ends with A -> D as a black-to-white edge. D and E are reachable now, but still white. A sweep would free live data.

Now switch to Incremental-update barrier.

This barrier notices the new pointer from a black object to a white object. It shades D gray, which gives the collector a chance to scan D and then mark E. The key event is not the store itself. It is the collector being told:

The graph changed in a way your old scan did not cover.

Now switch to Snapshot-at-beginning barrier.

This style preserves the object that was overwritten. When B drops its old pointer to D, the barrier shades the old referent. The collector completes a safe approximation of the heap as it existed when collection began. It may keep objects that died during the cycle, but it will not free objects that were live in the snapshot.

Try Delete a subtree with Snapshot-at-beginning barrier. D and E are no longer reachable by the end, but they are kept as floating garbage. That is not a correctness bug. It is the price of a conservative snapshot. The next collection can reclaim them.

The Barrier’s Contract

There are several families of write barriers. Wilson’s survey describes snapshot-at-beginning barriers, incremental-update barriers, read barriers, and implementation tricks such as coarse page-level dirty bits.1

The names can feel like compiler trivia. The contract is simpler:

If the mutator invalidates the collector's partial graph traversal,
record enough information to repair the traversal.

The information can be “the new target should be marked” or “the old target should be remembered.” In generational collection, it can be “this old object now points into the young generation.” Ungar’s Generation Scavenging exploited the observation that many young objects die young, but it still had to maintain remembered sets for old-to-new references as a side effect of stores.4

The write barrier is small because it runs on ordinary pointer writes. But it is semantically large. Remove it, or make it conditional in the wrong way, and the collector can become unsound.

Short Pauses Need Memory

Baker’s real-time list-processing collector was motivated by bounded operations: ordinary list operations should not suddenly take time proportional to the heap because allocation triggered a full collection.5 Modern runtimes inherit that desire for shorter pauses, but the design space is broader than pause time:

  1. Does the collector move objects or leave them in place?
  2. Does it trace the whole heap or only a young generation?
  3. Does it preserve the beginning snapshot or update the traversal as the heap changes?
  4. Does it require read barriers, write barriers, page protection, remembered sets, compiler cooperation, or hardware help?
  5. What work is allowed on the hot path of pointer stores?
  6. What garbage is allowed to float until the next cycle?

The lab is tiny, but the production lesson is not:

Garbage collection is reachability under mutation.

A stop-the-world collector makes mutation stop.

An incremental or concurrent collector lets mutation continue, and then pays for memory of the mutations.

That memory is the write barrier.

Works Cited

  1. Paul R. Wilson, “Uniprocessor Garbage Collection Techniques”, International Workshop on Memory Management, 1992. ↩ ↩2

  2. Edsger W. Dijkstra, Leslie Lamport, A. J. Martin, C. S. Scholten, and E. F. M. Steffens, “On-the-Fly Garbage Collection: An Exercise in Cooperation”, Communications of the ACM, 1978. ↩

  3. Leslie Lamport, “On-the-fly Garbage Collection: an Exercise in Cooperation”, Microsoft Research publication note. ↩

  4. David Ungar, “Generation Scavenging: A Non-disruptive High Performance Storage Reclamation Algorithm”, ACM SIGSOFT/SIGPLAN Symposium on Practical Software Development Environments, 1984. ↩

  5. Henry G. Baker Jr., “List Processing in Real Time on a Serial Computer”, Communications of the ACM, 1978. ↩