While a garbage collector traces the heap concurrently, application threads keep rewriting references. Describe the exact sequence of mutations that can cause a live object to be missed, and state the two conditions that must both hold for it to happen.
answer
- Condition 1: black gains a pointer to white
- Condition 2: all gray paths to that white object deleted
- Both needed - break either one for safety
- Incremental update breaks 1, SATB breaks 2
- Stacks have no write barrier -> final remark pause
basics
~20 sAn object is lost when a mutator stores a reference to an unscanned (white) object into an already-scanned (black) object, and then deletes every remaining path to it from unscanned objects. The collector never revisits the black object, finds no other route, and treats the live object as garbage.
solid answer
~60 sTwo conditions must hold simultaneously: 1. The mutator **writes a reference to a white object into a black object** - black is already scanned, so the collector will not look at that field again. 2. The mutator **destroys all remaining paths to that white object from gray objects** - so no unexplored frontier leads there either. Either one alone is harmless. If the object is still reachable from something gray, tracing will find it. If nobody planted it in a black object, the reference still lies somewhere the collector will scan. Concretely: the collector has scanned object `B` (black) and not yet scanned `G` (gray), which holds the only reference to `X` (white). A mutator copies `G.field` into `B.field`, then sets `G.field = null`. When the collector scans `G` it sees nothing; it never rescans `B`. Marking terminates with `X` still white, and `X` is reclaimed while `B` still points to it - a dangling reference and heap corruption. This is why concurrent collectors need write barriers on reference stores.
code
java · 6 lines// B is already scanned (black); G is queued but unscanned (gray); X is unreached (white)
Node x = g.next; // read the only reference to X, held by a gray object
b.next = x; // condition 1: a black object now references a white object
g.next = null; // condition 2: the last gray-reachable path to X is destroyed
// concurrent marking scans G, sees null, terminates - X stays white and is reclaimed
// while b.next still points at itgo deeper
Know that when the application moves references while the collector is tracing, a live object can be missed, and that write barriers exist to prevent it.
State both conditions precisely and walk through the three-line mutation sequence with the colours named.
Map each condition to the barrier family that breaks it, and explain why stacks still force a short final-mark pause.
Frame collector selection around this invariant: which condition the design breaks determines whether you pay re-scanning work or floating garbage, and that shows up as pause-time versus heap-headroom characteristics.
## Setting During concurrent marking the collector traverses a graph that the application is editing underneath it. Marking is safe as long as one invariant holds at termination: **no black object references a white object**. Black means "scanned, never to be revisited"; white at the end means "garbage". A black-to-white edge at termination is exactly a live object about to be freed. ## The two necessary conditions Wyk and Wegbreit's classic result: for a live object to be lost, both of these must occur. **Condition 1 - a black object gains a reference to a white object.** The mutator writes into a field of an object the collector has already finished scanning. The collector has no reason to look there again, so this new edge is invisible to the traversal. **Condition 2 - all paths from gray objects to that white object are destroyed.** The gray set is the remaining work list. If any gray object still leads to the white object, the traversal will reach it eventually and everything is fine. The loss requires the mutator to also sever every such route. Both are necessary. Breaking *either* one restores correctness - and that is precisely where the two barrier families come from. ## The canonical sequence Start with: - `B` - already scanned, black. - `G` - reachable, not yet scanned, gray. `G.f` holds the only reference to `X`. - `X` - not yet reached, white. Now the mutator runs: ``` X_ref = G.f; // read the only reference to X B.f = X_ref; // condition 1: black now points to white G.f = null; // condition 2: last gray path to X destroyed ``` The collector later pops `G`, scans its fields, finds `null`, and colours `G` black. Nothing else references `X`. The gray set drains and marking terminates. `X` is still white, so it is reclaimed - even though `B.f` points at it. The application then reads `B.f` and dereferences freed memory: silent corruption, a crash, or a wrong result, typically far from the cause and not reproducible. Note how ordinary the mutator code is. It is just moving a reference from one data structure to another - `list.remove()` followed by `other.add()`, a cache eviction, a queue hand-off. No unusual code is involved, which is why the problem cannot be avoided by convention and must be solved by the runtime. ## The two fixes, one per condition **Incremental update** attacks condition 1. A write barrier on the store `B.f = X_ref` notices that a reference is being written and records the *new* value (or re-greys the black target). Then `X` is discovered after all. This is the Dijkstra/Steele style barrier. **Snapshot-at-the-beginning (SATB)** attacks condition 2. A write barrier fires *before* the overwrite of `G.f = null` and records the **old** value `X_ref` into a satb queue, which is later treated as an additional root. Effectively the collector marks over a logical snapshot of the graph as it existed when marking began: anything reachable at that instant will be marked live, whatever happens afterwards. This is the Yuasa style barrier and is what G1 and Shenandoah use. Each costs something different. Incremental update needs a re-scan of things that were re-greyed, which can require more work in the final pause and in principle can chase a moving target. SATB never revisits and terminates predictably, but retains objects that died during the cycle - **floating garbage** collected only in the next cycle. ## Why a final pause still exists Even with barriers, a short stop-the-world **remark / final-mark** pause is normally required to drain the remaining barrier-recorded work and re-scan thread stacks, because stacks are mutated without any barrier - there is no write barrier on a local variable or register. Barriers cover *heap* reference stores; roots have to be handled at a safepoint. Collectors that also do concurrent stack scanning use additional mechanisms rather than plain write barriers. ## What to take away - The failure mode is not "the collector is slow"; it is a correctness bug that would free live memory in a language that promises that cannot happen. - The mutator behaviour that triggers it is completely ordinary reference movement. - Every concurrent collector must pick a barrier, and the choice of *which* condition to break drives its cost profile: extra re-scanning versus floating garbage.
- Why is breaking just one of the two conditions sufficient for correctness?Because both are necessary for the loss. If a black object gains a white referent but some gray object still leads to it, the traversal will reach it through that path. If every gray path is severed but no black object ever gained the reference, then the object is genuinely unreachable and reclaiming it is correct. A barrier only has to guarantee that the two never coincide unnoticed.
- Write barriers cover heap stores, so why is a stop-the-world remark pause still needed?Because references also live in thread stacks and registers, and putting a barrier on every local-variable assignment would be prohibitively expensive. Stacks are therefore scanned at a safepoint. The final pause also drains the barrier-produced queues so that marking can terminate against a consistent state.
- Does this problem also apply to reference reads, not just writes?Plain marking correctness turns on reference stores, so a write barrier suffices for tracing. Read (load) barriers appear for a different purpose - collectors that relocate objects concurrently need to intercept loads so mutators always see the current location. That is a relocation concern rather than the lost-object marking problem.
A librarian is checking shelves one aisle at a time. If a reader takes a book from an aisle not yet checked and slips it onto a shelf already checked, and it is now nowhere the librarian will look again, the book is recorded as missing even though it is right there on a shelf.
saying these in an interview costs you the question
- Claiming only one of the two conditions is enough to lose an object
- Thinking the problem requires unusual or buggy application code
- Believing synchronization such as volatile or locks in application code prevents it
- Confusing this with floating garbage - losing a live object is corruption, not waste
- Assuming write barriers alone remove the need for any stop-the-world pause