Concurrent garbage collectors describe objects as white, gray, or black while tracing. Define each colour, and explain what the collector has established once no gray objects remain.

## What marking actually is Tracing collection answers one question: which objects are reachable from the roots? That is a graph reachability problem, and marking is a graph traversal. The tri-colour abstraction (due to Dijkstra and colleagues) is the standard way to describe the state of that traversal at any instant. ## The three colours **White** - the collector has not proven this object reachable. All objects start white. At the end of marking, still-white means garbage. **Gray** - the object is known reachable, but the collector has not yet looked at what *it* points to. The gray set is the traversal frontier, in practice a mark stack or work queue. **Black** - the object is known reachable and all its reference fields have already been scanned, so its children are at least gray. The colours are not usually literal per-object fields of three values. Typically a **mark bitmap** records marked-or-not, and the mark stack or work queue implicitly holds the gray set: marked and on the queue is gray, marked and off the queue is black. Some collectors keep two bitmaps (previous and next marking cycle). The abstraction is what matters, not the encoding. ## The algorithm 1. **Root scan.** Scan the roots - thread stacks and registers, static fields of loaded classes, JNI global references, and similar - and colour everything they directly reference gray. This part is usually done at a safepoint, because thread stacks are hard to scan while the owning thread is running. 2. **Drain.** Repeatedly pop a gray object, examine each reference field, colour any white referent gray (push it), then colour the object black. 3. **Terminate** when the gray set is empty. Colours are monotonic: white -> gray -> black, never backwards within one cycle. That monotonicity is what guarantees the traversal terminates - each object is pushed at most once, so the work is bounded by the live set, not the heap size. This is the reason tracing collection cost scales with **live data**, not with garbage. ## Why the empty gray set proves completeness When no gray objects remain, consider any black object: by definition, all of its fields were scanned, so every referent was coloured at least gray at that time; since nothing is gray now, every one of those referents is black. So the black set is closed under following references. The roots are all black. Therefore the black set contains everything reachable from the roots, and any still-white object cannot be reached. That is the correctness argument for reclaiming white objects. Said as an invariant: **at termination, there must be no reference from a black object to a white object.** That single sentence is the whole safety condition, and it is what the rest of concurrent-marking machinery exists to defend. ## Where the difficulty comes from If the world is stopped for the whole traversal, the argument above is airtight because the graph does not change. The point of **concurrent** marking is to run this traversal while application threads ("mutators") keep executing and rewriting references. A mutator can take a reference out of an object the collector has not scanned yet and store it into an object the collector has already finished with. Now a black object points to a white object, and no gray object leads there any more - the collector will terminate believing that object is garbage while it is genuinely live. Reclaiming it corrupts the heap. That is the **lost-object problem**, and it is why concurrent collectors install write barriers: small pieces of code on reference stores that notice such mutations and restore the invariant, either by re-graying something or by remembering the overwritten reference. ## Practical notes - The gray set being a *set* rather than a strict stack matters for parallelism: multiple marking threads drain shared or per-thread queues with work stealing, and termination requires a distributed termination protocol, not just "my queue is empty". - Marking cost is proportional to the live set, which is why a heap full of short-lived garbage is cheap to collect and a heap holding a huge live graph is expensive regardless of allocation rate. - "White at the end is garbage" is why objects allocated *during* concurrent marking must be handled deliberately - most collectors treat them as implicitly live (allocated black or above a top-at-mark-start pointer) rather than risk sweeping them.