Weak References, Finalization, and Ephemerons

Caching is the canonical use for a weak reference: keep the mapping from key to value, but do not keep the value alive on the cache’s account. If the only reference to the value is the cache entry, the entry should disappear and the memory should be reusable. Implementing that requires the collector to treat an edge as not contributing to reachability, and then, after the reachability computation is complete, to find the objects that survived only through such edges and clear them.

The machinery is not a single feature but a family of related ones, ordered by a notion of reachability that is finer than the binary live/dead of a plain tracing collector. Getting the ordering right is what separates a collector that supports weak references correctly from one that resurrects objects or crashes.

Strength is a property of the edge

A weak reference is an edge the collector traverses to check a target’s status but not to establish it. During marking, an object reachable only through weak edges is not marked. After marking, the collector visits every weak edge and clears those whose targets were not marked.

The important design consequence is that the collector must keep a list of all weak edges to process, and that list is itself part of the heap it is collecting. An implementation that stores weak edges in ordinary objects must be careful not to have those objects keep the targets alive: the registry entry holds the address of the referent, which is exactly the pointer that must not count.

The usual arrangement is a side structure, a table of weak references, scanned after the mark phase. Each entry records the address of the referent and a location to write the cleared value. Because the collector reads the referent’s mark bit, the referent must still be allocated at that moment; this is why weak processing happens before the sweep frees anything.

Reachability classes and their order

The Java platform documents an ordering of reachability strengths, and it is worth following because the same ladder appears in other runtimes.

An object is strongly reachable if it can be reached through strong edges only. It is softly reachable if it is not strongly reachable but can be reached through a soft reference, which the runtime may clear under memory pressure. It is weakly reachable if it is not softly reachable but can be reached through a weak reference. It is phantom reachable if it is not weakly reachable and is reachable through a phantom reference, which exists to be notified after finalization. Otherwise it is unreachable.

The ladder is ordered: soft is cleared only after strong reachability fails, weak only after soft, phantom only after weak. Clearing in the wrong order would either retain objects that should be freed or notify a program about an object that is still strongly reachable, which is the worse error.

An implementation can compute the classes with repeated marking passes: mark from strong roots, then mark from surviving soft references as if they were strong, then process weak, then phantom. Each pass is over the unmarked remainder rather than the whole heap, so the cost is proportional to the objects at each level.

Finalization is a reachability class, not a callback

A finalizer is a method the runtime invokes before reclaiming an object. The naive implementation, which runs the finalizer when the object is found unreachable, is wrong, because the finalizer is ordinary code that can store the object into a global and thereby resurrect it. The collector must therefore treat an object with a pending finalizer as reachable until the finalizer has run.

That produces the standard ordering: an object that is unreachable but has not been finalized is placed on a finalization queue, and the queue entry is a strong root for the next cycle. The finalizer runs, and the object becomes reclaimable only after the following collection. The object therefore survives at least one extra collection cycle, and if the finalizer resurrects it, it becomes strongly reachable again and the whole thing repeats, which is why runtimes impose a rule that an object is finalized at most once.

/* Collector side: separate unreachable-but-unfinalized objects. */
for (struct obj *o = heap_start; o < heap_end; o = next(o)) {
    if (!is_marked(o)) {
        if (has_finalizer(o) && !was_finalized(o))
            enqueue_finalizer(o);      /* strong root for the next cycle */
        else
            free_object(o);
    }
}

The consequences are visible to programmers as ordering guarantees that do not exist. Finalizers run on a runtime thread, at a time the collector chooses, in an order that is not specified and may differ between runs. An object’s finalizer may run while another object it refers to has already been finalized. The Java specification states explicitly that the order in which finalizers are invoked is unspecified, and that the thread on which they run is unspecified. Runtimes have moved away from finalization for these reasons: the mechanism provides no reliable point at which resources are released.

The finalizer problem, stated precisely

Three failures recur in systems that rely on finalizers.

The first is that a finalizer can be starved. If the finalization queue is processed by a low-priority thread and the allocation rate exceeds the queue’s drain rate, unfinalized objects accumulate and memory grows even though the objects are unreachable. The queue is a strong root, so the collector cannot free them.

The second is that a finalizer can deadlock. It runs while holding no locks of its own, but it may call into code that takes a lock held by a thread that is waiting for the finalizer to complete. Runtimes mitigate this by running finalizers on a dedicated thread and by documenting that finalizers must not block, which is an obligation that cannot be enforced.

The third is that a finalizer can see a partially initialized object. If the constructor throws or is interrupted, the object may still become finalizable with fields that were never assigned, so the finalizer must be written defensively.

The alternative that has displaced finalization in most modern designs is deterministic cleanup: a scoped construct that the programmer invokes explicitly, with a finalizer retained only as a backstop that reports the leak. The backstop can be implemented with a phantom reference or a weak reference whose clearing triggers a diagnostic, which avoids running arbitrary code during collection.

Ephemerons and the fixed point

A weak-keyed map is the case that breaks the simple scheme. The map holds entries, each entry holds a key weakly and a value strongly. The intent is that the value lives exactly as long as the key. The naive implementation marks the value as strongly reachable from the entry, so the value keeps the key alive if the key is reachable from the value, which is common because values often refer back to their keys.

Hayes’ 1997 paper names the structure an ephemeron and gives the rule: an ephemeron’s value is reachable only if its key is reachable. That is a conditional reachability rule, and it cannot be evaluated in a single pass, because whether the key is reachable may depend on other ephemerons whose keys depend on this one.

The computation is a fixed point. Start with the set of objects reachable without using any ephemeron edge. Then repeatedly: for each ephemeron whose key is in the reachable set and whose value is not, add the value’s transitive closure to the reachable set. Repeat until no new object is added. Termination is guaranteed because the reachable set only grows and is bounded by the heap.

/* Fixed point over ephemeron entries after ordinary marking. */
static void trace_ephemerons(struct table *t) {
    int changed = 1;
    while (changed) {
        changed = 0;
        for (size_t i = 0; i < t->n; i++) {
            struct entry *e = &t->entries[i];
            if (e->key && is_marked(e->key) && e->value && !is_marked(e->value)) {
                mark_transitively(e->value);
                changed = 1;
            }
        }
    }
}

The cost is the repeated scan of the ephemeron table, which in the worst case is O(entries × iterations). Implementations reduce it by maintaining a queue of ephemerons whose keys have just become reachable, so each entry is examined once after its key is marked. That turns the fixed point into a worklist algorithm with the same asymptotic behaviour as ordinary marking.

A subtlety: if the key and value are in the same entry and the key is weak, the entry must not be treated as a strong edge from the table to the key. The table itself is strongly reachable, but the key slot is weak, and the value slot is strong-only-conditionally. A collector that marks the table’s slots uniformly gets the wrong answer in both directions.

Weak references and compaction

After the mark phase, a weak reference whose target survived must be updated if the target moved. That is why weak processing is interleaved with compaction rather than done before it: the forwarding information is available during compaction and may be discarded afterwards.

The ordering that works is: mark, compute the reachability classes, process weak references (clearing the dead and updating the live), compact, then update the remaining weak references through the forwarding information. Collectors that compact and clear weak references in the same pass must handle the case where a target was cleared and then would have moved.

Phantom references add one more turn: a phantom reference must not be cleared until after finalization, so the object must remain allocated with its phantom entry intact through the finalization cycle, and the entry is cleared only when the object is finally reclaimed. That requires the object’s storage to remain addressable after it is logically dead, which is why phantom-reachable objects occupy a separate list rather than being freed with the rest.

What the mechanism cannot provide

Weak references do not provide deterministic release. A weak reference is cleared at some collection after the referent becomes unreachable, and the interval depends on the collector’s pacing, the subject of heap growth and collection pacing. A program that depends on a weak reference being cleared promptly is depending on a scheduling property the runtime does not promise.

They also do not compose with conservative collection in the obvious way. A conservative collector can support weak references only if it can distinguish the weak edge from an ordinary pointer, which means the weak edge must be registered explicitly rather than found by scanning. That is possible, and conservative collectors do support it, but the registration must be maintained by the program rather than derived from type information.

The final limitation is that none of these mechanisms let the program observe the moment of death. The collector decides when to run, and the only notification is a callback after the fact. Systems that need a resource released at a known point must use explicit scoping; the collector’s machinery is for memory, and for memory only.