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.
answer
- White = unvisited, gray = frontier, black = scanned
- Gray set is the mark stack
- Termination = gray set empty
- Invariant: no black -> white reference at the end
- Cost scales with live data, not heap size
basics
~20 sWhite means not yet reached, gray means reached but its outgoing references not yet scanned, black means reached and fully scanned. When no gray objects remain, tracing is complete: everything reachable is black and every remaining white object is unreachable and can be reclaimed.
solid answer
~50 sThe tri-colour abstraction is bookkeeping for a graph traversal. - **White** - not yet proven reachable. Everything starts white. - **Gray** - proven reachable, but its outgoing references have not been scanned yet. Gray is the work queue, the frontier of the traversal. - **Black** - proven reachable *and* all its fields already scanned. Marking begins by colouring the roots gray (thread stacks, static fields, JNI handles). The collector repeatedly takes a gray object, colours each white object it references gray, and then colours the object itself black. Objects only move white -> gray -> black. **Termination is the empty gray set.** No gray means no unexplored frontier: every black object has been scanned and points only at gray or black objects, so no reachable object can still be white. The remaining white objects are unreachable, and the collector sweeps or evacuates accordingly. The abstraction matters because it states the invariant a concurrent collector must preserve while application threads keep mutating references.
go deeper
Recall the three colours and their meanings, and that when nothing is gray the traversal is done and white objects are garbage.
Add the invariant - no black-to-white reference at termination - and explain why monotonic colouring bounds the work by the live set.
Connect the abstraction to real machinery: bitmaps plus work queues, parallel marking with work stealing and termination protocols, and objects allocated during the cycle.
Use it as the correctness frame for evaluating collectors: every concurrent design is an answer to how it defends the black-to-white invariant, and at what mutator cost.
## 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.
- How are the three colours actually represented in a real collector?Usually as a mark bitmap plus a work queue rather than a three-valued field per object. A bit set in the bitmap means marked; if the object is still on a marking queue it is conceptually gray, and once popped and scanned it is black. Some collectors keep two bitmaps so the previous cycle's marks stay readable while the next cycle marks.
- What happens to objects allocated while concurrent marking is in progress?They cannot be traced from a snapshot taken before they existed, so collectors treat them as live for this cycle - either by allocating them already marked, or by tracking a top-at-mark-start boundary and treating everything above it as implicitly live. They are simply reconsidered in the next cycle, which is one source of floating garbage.
Searching a building for people: rooms you have not entered are white, rooms you entered but whose doors you have not opened yet are gray, rooms you entered and whose every door you already checked are black. When no gray rooms are left, everyone you could reach has been found.
saying these in an interview costs you the question
- Saying black means garbage and white means live - the colours are the other way round
- Thinking the colours are stored as a three-state field on every object
- Claiming marking cost scales with heap size rather than live-set size
- Believing an object can go back from black to white within one marking cycle
- Forgetting that the roots must be scanned before draining can begin