Tri-Color Marking & Write Barriers

Basic mark-and-sweep is a stop-the-world collector — the program halts while the GC runs. For interactive applications, this causes noticeable pauses. Tri-color marking enables incremental collection, spreading GC work across multiple small steps.

The Three Colors

Every object is in one of three states:

• White: not yet visited — potentially garbage
• Gray: marked as reachable but its children have not been traced yet
• Black: fully traced — reachable, and all referenced objects are also marked

The Algorithm

1. Initially: all objects are white
2. Mark roots gray (add to gray worklist)
3. While gray worklist is not empty:
   a. Pop a gray object
   b. Trace its references — mark white children gray
   c. Color the object black
4. All remaining white objects are garbage → sweep them

The key invariant: no black object may reference a white object. If we maintain this, all reachable objects will eventually be marked.

Why Tri-Color Enables Incrementality

With tri-color, we can pause marking at any point and resume later — the gray worklist tells us exactly where to continue. We can do a fixed amount of work per allocation:

allocate():
    markSteps(STEPS_PER_ALLOC)   // do a few marking steps
    return malloc(...)

This interleaves GC work with program execution, keeping pause times short.

The Write Barrier Problem

If the program modifies an object while the GC is marking, it can break the invariant. Consider:

1. GC marks object A black (fully traced)
2. Program sets A.child = B (B is white)
3. GC never visits B because A is already black
4. Sweep frees B → dangling pointer!

Write Barriers

A write barrier is code that runs whenever an object reference is written. It restores the invariant:

Snapshot-at-the-beginning (Dijkstra)

When a black object gets a new reference to a white object, mark the white object gray:

writeBarrier(object, newRef):
    if object.color == BLACK and newRef.color == WHITE:
        newRef.color = GRAY
        grayStack.push(newRef)

Incremental Update (Steele)

When a black object gets a new reference, mark the black object gray again (re-traverse it):

writeBarrier(object, newRef):
    if object.color == BLACK:
        object.color = GRAY
        grayStack.push(object)

How Lua Handles This

Lua uses an incremental GC with tri-color marking and a back-barrier (Steele variant). Objects that get mutated during marking are added back to the gray list.

Your Task

Implement tri-color marking with a gray worklist, incremental marking steps, and a write barrier to maintain the tri-color invariant.