A collector relocates a live object while the program runs. How does a thread still holding the old address avoid using the stale copy?
answer
- copy first, then leave a pointer behind
- forwarding word installed atomically
- loads are intercepted, not writes
- the barrier repairs the slot it read
- old space held until references are fixed
basics
~20 sThe old location keeps a forwarding record pointing at the copy, and a read barrier on reference loads detects it, follows it, and writes the corrected reference back into the slot it came from, so the program only ever works on the current copy.
solid answer
~50 sRelocation happens in two steps: the collector copies the object, then installs a **forwarding word** at the old address naming the new one, usually with an atomic compare-and-set so exactly one thread wins the copy race and everybody agrees on the winner. Correctness then rests on a **read barrier** compiled into reference loads. When a load produces a reference into a region being evacuated, the barrier resolves it - following the forwarding word, or performing the copy itself if nobody has yet - and stores the corrected reference back into the field it was read from, so the repair is paid once per slot rather than on every use. The result is an invariant the program cannot violate: any reference a thread actually dereferences names the current copy. The old memory stays readable until every surviving reference to it has been repaired.
code
pseudocode · 16 linesfunction load_reference(holder, field):
r = raw_read(holder, field)
if r = null:
return r
if not in_evacuating_region(r):
return r # fast path: nothing to do
if has_forwarding_word(r):
current = forwarding_target(r)
else:
copy = allocate_and_copy(r)
current = install_forwarding(r, copy) # compare-and-set; loser gets winner
compare_and_set(holder, field, r, current) # repair the slot, once
return currentgo deeper
The essential picture: when an object is moved, something is left behind at the old address that says where it went, and the runtime checks for that on the way to the object.
Be able to separate the two mechanisms - the forwarding record installed atomically at the old address, and the load-side barrier that follows it and repairs the reference it just read.
Show what it costs in production: a test on every reference load, a thread charged for a copy it did not cause, and both copies committed until surviving references have been repaired.
Judge whether concurrent compaction is worth it at all: constant barrier tax and a footprint premium on every service, against removing a stop that scales with how much has to move.
## Moving an object out from under a running program Compaction moves live objects so that free space becomes contiguous. Done inside a stop-the-world pause the problem is easy: nothing is reading the heap while objects move, so the collector copies everything and rewrites every reference before letting the program resume. A collector that wants to avoid a long stop cannot do that. It has to copy objects while application threads are loading, dereferencing and storing references to those same objects, which creates one hazard above all others: a thread holding a reference to the old location could read or, far worse, **write** to a copy that is no longer the real object. A write lost in an abandoned copy is silent data corruption, not a performance problem. Two mechanisms together close that hazard. ## The forwarding record When the collector evacuates an object it copies the bytes to a new address and then leaves a **forwarding word** at the old address holding the new one. Three properties matter: - It is installed with an **atomic compare-and-set**, so when the collector and an application thread try to evacuate the same object at the same time, exactly one copy wins and both parties then agree which address is current. - It is self-describing: a reader can tell a forwarding word from ordinary object contents, usually by a tag or a header bit. - It keeps the old memory **occupied**. The block cannot be handed back for reuse while anything might still arrive at that address looking for the record. ## The read barrier A forwarding record on its own only helps whoever bothers to look. The looking is done by a **read barrier**: a short sequence the compiler emits around every load of a reference from the heap. Its fast path is a cheap test - is this reference into a region currently being evacuated? For the overwhelming majority of loads the test fails and the reference is returned unchanged. On the slow path the barrier resolves the reference: follows the forwarding word if one is present, or copies the object itself if it has not been copied yet, and then writes the resolved reference **back into the field it was loaded from**. That write-back is why the scheme is affordable: each reference slot is repaired at most once, and after repair its loads take the fast path forever. The invariant established is narrow and strong: a reference a thread can actually dereference names the current copy. The program may still *hold* stale references in registers or in unrepaired fields, but it cannot use one without the barrier having resolved it first. ## Which barrier does which job | Barrier | Fires on | Job while objects move | |---|---|---| | Read barrier | Loading a reference from the heap | Resolve a possibly stale reference to the current copy and repair the slot | | Write barrier | Storing a reference into the heap | Report the new edge so a concurrent trace does not miss it | The distinction is worth keeping straight because the two solve different problems. A write barrier alone cannot make relocation safe: it says nothing about a thread that merely *reads* through a reference it obtained before the move. Concurrent relocation is the case where a read barrier earns its cost. ## When the old memory can be released The old copy's memory is not free the instant the copy exists. Repair is lazy - it happens when a slot is next read - so surviving references to the old address can be scattered across the heap and across thread stacks. Before the space can be reused, the collector must reach a point where no reference to the old address can still be produced. Collectors get there in one of two ways: 1. Run a pass that walks the references that could still point into the evacuated area and updates them, then release the space. 2. Keep the forwarding information alive until the next cycle's trace has visited and repaired everything anyway, and release the space then. Either way, evacuation costs a period during which both the old and the new memory are committed. That is the footprint premium of moving while the program runs, and it is why such collectors need visible headroom rather than a heap sized to the live set. ## What it costs - **Every** reference load carries the barrier's fast-path test, so straight-line code that chases pointers gets slower even when no collection is running. - The slow path can make an ordinary field read do a copy, so a thread can be charged for work it did not cause. - Compare-and-set on forwarding installation means the program and the collector contend on the same words when both touch a hot object. - Old and new copies coexist, so peak footprint exceeds the live set for the duration of the evacuation. What is bought is a heap that can be defragmented without a stop proportional to how much has to move. For a service whose tail budget is a small number of milliseconds, that is usually the only way to have compaction at all.
- Why is a write barrier alone not enough to make relocation safe?A write barrier fires when the program stores a reference, which is the wrong moment. The danger is a thread that already holds a reference obtained before the move and simply reads or writes through it - no store of a reference happens at all. Only intercepting the load lets the runtime redirect that thread to the current copy before it touches anything.
- What happens if two threads try to evacuate the same object at the same instant?Both may copy it, but the forwarding word is installed with a compare-and-set, so only one installation succeeds. The loser sees the winner's address returned by its failed attempt and abandons its own copy, which is unreachable and reclaimed later. The cost is a wasted copy, never two live versions of one object.
- Why does the barrier write the resolved reference back into the field it read from?To make the repair permanent. Without the write-back, every future load of that field would take the slow path again, and a hot field would pay the resolution cost repeatedly. Storing the current reference means the slot is fixed once and all later loads hit the cheap test.
Someone moves flat and leaves a change-of-address card at the old door. Letters still arrive there and get redirected, and each sender who is told the new address updates their address book, so the redirection is needed only once per sender - and the old flat cannot be re-let until nobody is still writing to it.
saying these in an interview costs you the question
- Thinks every reference is rewritten at the moment the object is copied
- Believes a write barrier alone makes concurrent relocation safe
- Says both copies stay valid and are kept in sync
- Assumes the old block can be reused as soon as the copy exists
- Treats the barrier as free because its fast path is short
- Thinks the program is briefly stopped for each object moved