In three-colour marking (white unreached, grey reached but unscanned, black scanned), why may no black object reference a white one?

## What the colours record A tracing collector starts from the **roots** — the references a program can reach without going through the heap — and follows references outward. The three-colour abstraction is bookkeeping over that traversal: - **White** — not yet reached. Every object starts white when a cycle begins. - **Grey** — reached, but its own reference fields have not been scanned yet. The grey objects are the marker's pending work. - **Black** — reached *and* scanned. Every reference it holds has already been followed, and the marker has no further business with it. Scanning one grey object means walking its reference fields, shading each white target grey, and only then painting the object itself black. The order matters: shade first, blacken second. The trace is finished when the grey set is empty — there is no pending work left, so nothing further can be reached, and every object still white is unreachable and may be reclaimed. (Objects created while the cycle is running need a colouring rule of their own; that rule is a separate matter from the invariant.) ## Why black-to-white is the fatal shape Black is the colour of *done*. A black object is off the work list, and nothing in the algorithm schedules another visit to its fields. A reference from a black object to a white object is therefore a live edge the trace has no way of discovering. If it is the only remaining route to that white object, the object stays white to the end of the cycle and is reclaimed while the program can still reach it — a freed object sitting under a live reference, which surfaces later as arbitrary corruption a long way from the collector's own code. This cannot arise while the program is stopped for the whole trace: the graph does not change, and the marker's shade-then-blacken order guarantees a target is grey before its source turns black. It becomes possible the moment the program keeps running, because the program can move a reference out of a place the marker has not reached yet and into a place the marker has already finished with. ### The hazard, one step at a time Picture a small graph on a chalkboard mid-mark. `B` is black, already scanned. `G` is grey — reached, not yet scanned. `W` is white, and the only reference to it is the field `G.next`. 1. The marker has finished `B` and has not yet scanned `G`. 2. The program copies `G.next` into `B.field`. A black object now references a white one. 3. The program clears `G.next`. The pending side's route to `W` is gone. 4. The marker scans `G`, finds nothing, and blackens it. The grey set drains while `W` is still white. `W` is reachable — through `B` — and about to be freed. ## The invariant, stated The **strong tri-colour invariant** is the rule that forbids the state reached in step 2 from surviving: *no black object holds a reference to a white object*. While it holds continuously, the grey set is a frontier separating black from white, so every path from an already-scanned object to an unreached one passes through pending work. When that frontier drains, no such path can exist, and "still white" once again means "unreachable". ## What it costs to keep Enforcing the invariant against a running program costs a **write barrier**: a small hook the runtime executes on reference stores while a cycle is in progress. Two families exist, and they intercept different heap events: | Family | Fires when | What it shades grey | |---|---|---| | Insertion (incremental update, after Dijkstra) | a reference is installed into an object | the newly stored target; some variants re-shade the storing object instead | | Deletion (snapshot at the beginning, after Yuasa) | a reference is overwritten or dropped | the *old* target, before it disappears | Both hand the marker something grey to walk from, and both are deliberately imprecise: they act on the shape of the event, not on any proof that the object involved is still needed. ## What the invariant does and does not promise - It promises that nothing reachable is left white at the end of a cycle. That is a safety property, and it is the whole point. - It does **not** promise that everything black is live: an object marked early can die later in the same cycle and survive as floating garbage until a later trace reclaims it. - It says nothing about how expensive marking is, or how long the cycle takes; those are separate budgets. - It is a property of the reference graph alone. A write to a non-reference field can neither create nor destroy an edge, which is why barriers sit on reference stores rather than on all memory writes. - Making the barrier's own bookkeeping visible to the marker in the right order is a further concern, separate from the invariant it exists to preserve.