Tri-Colour Marking and the Barriers That Keep It Honest

A marking collector that stops the world has an easy life: no pointer changes while it works, so the graph it traverses is the graph that existed when the roots were read. Move the marking to a separate thread and the graph changes underneath it. A pointer stored after its source object was scanned can lead to an object the marker has already passed, and that object will never be visited. The collector then frees memory the program can still reach, which is the one failure a garbage collector must never make.

Making marking concurrent therefore requires an invariant that the program itself helps maintain. The invariant is stated in terms of colours, and the colour abstraction is the clearest way to see why the barriers take the forms they do.

Three colours and one forbidden edge

At any moment during a concurrent mark, each object is in one of three states. White means not yet visited. Grey means visited but not yet scanned: the marker knows the object is live but has not examined its fields. Black means visited and scanned: all of its fields have been followed.

The marker maintains a single invariant: no black object holds a pointer to a white object. If that holds, then every white object reachable from a root is reachable through a path that ends at a grey object still awaiting scanning, and the marker will find it.

Colour is a state, not a field in the object header necessarily; implementations use mark bits, a mark stack, and sometimes a separate bitmap. But the three-state model is what the barrier design reasons about.

Two events can violate the invariant, and they are duals of each other:

• The mutator stores a pointer from a black object to a white object. Now a black object points at white, and the white object may be unreachable from any grey object.
• The mutator overwrites the last pointer from an object the marker has not yet scanned to a white object, before the marker reads that object’s fields. The white object loses its only path from the grey set and may never be found.

Both must be prevented, and the two standard barrier families each prevent one of them directly.

Insertion barriers: shade the new target

An insertion barrier, also called an incremental-update barrier, fires on the store and marks the newly stored value. If a black object is made to point at a white object, the barrier colours the white object grey and pushes it onto the mark stack. The invariant is restored: the target is no longer white.

/* Dijkstra-style insertion barrier: shade the value being stored.
   `container` is the object that owns `field`, known at the store site. */
static inline void store_with_barrier(struct obj *container, struct obj **field,
                                      struct obj *value, struct mark_state *ms) {
    *field = value;
    if (value && is_white(value) && is_black(container)) {
        shade_grey(value, ms);        /* white-to-grey, then push */
    }
}

Dijkstra’s 1978 formulation is the canonical one, and its cost is that every store of a reference must check the colour of the target and possibly push it. The check is cheap when the value is already black or grey, which is the common case for pointers to old, long-lived objects, but the barrier must still perform the colour read.

The advantage of shading the value is that the target is repaired directly rather than the source being re-scanned, so the object that needs another look is the one just stored. The cost is that the barrier must read the container’s colour, which the compiler can supply at the store site but which may require a reload if the container’s header was not already in a register. A second cost is that a program which repeatedly stores the same white-into-black pointer re-shades it, and the mark stack grows with redundant entries; implementations deduplicate by checking whether the object is already grey before pushing.

Deletion barriers: shade the old value or the container

A deletion barrier, or snapshot-at-the-beginning barrier, fires when a pointer is overwritten and preserves the old value. The idea is to compute the set of objects reachable at the moment marking started: any object that was reachable then must be treated as live for this cycle, even if the program drops its last reference during the cycle. That is a conservative approximation, and it is safe, because it can only retain objects, never free a live one.

/* Snapshot-at-the-beginning barrier: shade the overwritten value. */
static inline void store_satb(struct obj **field, struct obj *value,
                              struct mark_state *ms) {
    struct obj *old = *field;
    if (old && is_white(old)) shade_grey(old, ms);
    *field = value;
}

Yuasa’s barrier takes this form, and it has a property that matters in practice: it retains floating garbage. An object that became unreachable one instruction after marking began is still considered live, so it survives the cycle and is reclaimed at the next one. The amount of floating garbage is proportional to the mutation rate during the cycle, not to the heap, and for a cycle that lasts a few milliseconds over a heap of a few hundred megabytes it is usually a small fraction of the live set.

A hybrid form, used in several collectors, combines both: shade the old value on deletion, and shade the new value when the container is black. That closes both windows and also survives compiler optimizations that reorder or coalesce stores.

There is a third family, the sATB with card marking: instead of shading individual objects, the barrier dirties the card containing the field, and the marker rescans dirty cards at the end. This is cheaper on the store path but produces more work for the marker, and it is the same mechanism described in generational collection and write barriers applied to a different problem.

The re-scan and the termination condition

A concurrent marker is done when the mark stack is empty and no dirty cards remain. The second condition is what makes the termination check subtle: the mutator may dirty a card at any time, including immediately after the marker observes that the stack is empty. The collector must therefore stop the world briefly, re-scan the roots and the dirty structures, and confirm emptiness while the mutator is paused. That final pause is short but not zero, and its length is determined by the number of dirty cards and root slots rather than by the heap.

The pause is called a remark in some collectors, and its existence is the reason a “concurrent” collector still has a worst-case pause. The design goal is to keep the remark’s input small: barriers that shade individual objects rather than cards leave less to re-scan, and a marker that keeps up with the mutation rate leaves a short stack.

Read barriers and the alternative

Write barriers assume the mutator’s stores are the only source of change. A read barrier assumes the mutator’s loads may observe an object that has already been moved or marked, and forwards the access. Collectors that move objects concurrently need read barriers; collectors that only mark concurrently usually do not.

A read barrier is more expensive because it sits on the load path, which is far hotter than the store path in most programs. The classic formulation is Baker’s: every load of a reference checks whether the object is in the from-space and forwards it if so. That makes every pointer dereference cost a check, and it is why read-barrier collectors are chosen only when the pause requirement is strict enough to pay for it.

The cost of the barrier in a compiled program

In an interpreter, the barrier is a few extra instructions in the store opcode, and the cost is easy to account for. In a compiled program it is a sequence inserted at every reference store, and it interacts with optimization in ways that matter.

A barrier that reads a colour bit from the target object’s header prevents the compiler from keeping the target’s header in a register across the store, and it prevents certain dead-store eliminations, because the barrier’s effect is observable to the collector. Compilers mitigate this by making the barrier a call to a runtime routine with a fast path, by hoisting the colour check out of loops where the target does not change, and by using a per-region colour so that the check becomes a comparison against a region base rather than a memory load.

The most important mitigation is to make the common case free. In a region-based collector, the marker colours whole regions rather than individual objects; a store from a black region to a white region is rare, so the barrier’s conditional branch almost always falls through. The cost per store then reduces to one or two comparisons against constants, which the branch predictor handles well.

Correctness arguments that fail

Three plausible-sounding shortcuts are worth naming because all three are wrong.

The first is to assume that a store into a black object is safe if the object was black at the time of the store, on the grounds that the marker will not revisit it. That is exactly the case the barrier exists for, and skipping it loses the target.

The second is to rely on the marker’s traversal order: if the marker scans objects in reverse allocation order, and the program tends to store into recently allocated objects, the window seems small. It is not zero, and a single missed pointer is a use-after-free. Ordering heuristics can reduce the number of barrier hits but cannot replace the invariant.

The third, subtler error is to shade the container instead of the value. Shading the container means re-scanning it later, which is correct if the container is pushed back onto the mark stack and its fields are re-read. Some implementations do exactly this, and it works, but only if the re-scan happens after the store, which requires the barrier to guarantee ordering with respect to the store. An insertion barrier that pushes the container without re-reading its fields is not sufficient.

The machinery described here is what allows marking to proceed while the program runs. The next problem is what the marker is allowed to treat as a root when it cannot distinguish a pointer from an integer, which is the constraint that forces conservative stack scanning.