Memory Reclamation for Lock-Free Structures

Removing a node from a lock-free structure is a single compare-and-swap. Freeing it is the hard part. Some other thread may have read a pointer to that node just before the removal and may be about to dereference it. Nothing in the structure records that intention, so there is no way to ask whether the node is still in use. Reclamation schemes exist to answer that question, and every one of them answers it by making the reader declare something.

The declaration is the entire design space. What the reader declares, how much it costs, and how the collector learns about it determine the latency, the throughput, and the memory footprint. The three families below are the ones that see real use.

The problem stated precisely

A thread executing a traversal holds a pointer it read from shared memory. Between the read and the dereference, another thread may unlink that node and free it. The dereference then touches freed memory. In C this is undefined behaviour; in a managed runtime it is prevented by the collector, which is why lock-free algorithms are much easier to write in a language with a tracing collector.

The requirement for a solution is a guarantee of the form: if a reader has observed a pointer P and has not yet finished using the object it refers to, then the object at P is not freed. Any scheme satisfying that guarantee is safe. The schemes differ in how they identify “has not yet finished”.

There is a second requirement, less often stated: the guarantee must not be achieved by never freeing anything. A structure that leaks every removed node is safe and useless. Bounded memory is the practical constraint, and the bound is what separates the schemes.

Hazard pointers

A hazard pointer is a per-thread slot, published in shared memory, in which a reader records the address it is about to use. The protocol is a sequence of steps with a re-check.

1. The reader loads the pointer from shared memory into a local variable.
2. The reader stores that value into its hazard slot with release ordering.
3. The reader re-reads the shared location. If it has changed, the pointer may have been unlinked before the hazard was published, so the reader returns to step 1.
4. The reader dereferences the pointer. It is now guaranteed that the object will not be freed, because any collector must scan the hazard slots and will see this one.

The re-check in step 3 is what makes the protocol correct. Publishing a hazard on a stale pointer protects nothing, since the object may already be on the collector’s list. The re-read confirms that the pointer was still current after the hazard became visible. The load, store, re-read sequence is exactly the pattern that Compare-and-Swap and Why the Retry Loop Must Re-read analyses for a different purpose: a value observed before an atomic step has to be re-validated after it.

Removal has two phases. The remover unlinks the node with a compare-and-swap, which makes it unreachable to new readers. It does not free the node; it appends it to a per-thread retired list. When the retired list reaches a threshold, the thread scans all hazard slots, collects the set of addresses currently protected, and frees every retired node not in that set.

The threshold is the knob. A small threshold frees memory promptly and makes the scan happen often; a large threshold amortises the scan over more retirements and holds more memory. A common choice is a threshold on the order of the number of hazard slots, which keeps the scan cost linear in the number of threads while bounding retained memory.

/* sketch of the retire step; hp is the thread's hazard record */
void retire(node_t *n, hp_record_t *hp)
{
    hp->retired[hp->count++] = n;
    if (hp->count >= hp->threshold) {
        scan_and_free(hp);              /* reads every thread's published hazard */
        hp->count = 0;
    }
}

The read-side cost is the interesting part. A reader that publishes and re-checks performs one store to its own hazard slot, which is a line it owns exclusively and therefore does not transfer, plus one additional load of the shared pointer. The extra load is the price of the guarantee, and it doubles the number of shared-memory reads on the traversal’s critical path.

Hazard pointers tolerate arbitrary reader delays. A thread that publishes a hazard and then sleeps for a second holds the object for a second, and no other thread can free it. That is a correctness property and a memory hazard: a stalled thread can pin an unbounded amount of memory. Schemes that rely on time rather than on declaration do not have this problem, which is why kernels prefer them.

Epoch-based reclamation

Epoch schemes replace the per-object declaration with a per-thread statement of which period the thread is in. Each thread publishes an epoch number when it enters a critical section and clears it when it leaves. A retired object is tagged with the epoch in which it was unlinked, and it becomes free once every thread has either advanced past that epoch or is not in a critical section at all.

The read side is much cheaper than hazard pointers: a reader increments a per-thread counter and publishes the current global epoch, and the compiler is prevented from moving memory operations across those two points. No per-object store is needed, and no re-check is needed. Traversal code looks like ordinary pointer chasing with two bookkeeping operations around it.

The cost is deferred reclamation. Memory retired in epoch E cannot be freed until all threads have left E and advanced. If one thread stalls inside a critical section, every object retired after it entered that section is retained, and the retention is unbounded in the same way as hazard pointers but coarser: a single stalled thread pins everything retired during its section rather than the few objects it touched.

Epoch schemes also require a mechanism to advance the global epoch, which is a scan of per-thread states and a compare-and-swap. The scan frequency is a tuning parameter, and the trade is the same one as the hazard threshold: frequent advances free memory sooner and cost more coordination.

Reference counting and its failure mode

The obvious scheme is a per-object counter incremented when a pointer is acquired and decremented when it is released, with the object freed at zero. It has no re-check, no hazard slot, and no epoch, and it frees memory as soon as the last reference goes away.

Its problem is the increment. A reader that loads a pointer from shared memory and then increments the object’s counter is incrementing a counter on an object that may already have been freed, which is the same use-after-free the scheme was meant to prevent. The increment must happen while the object is known to be alive, and the only way to know that is to have a guarantee that the object is alive, which is the thing being established.

Some structures solve this by making the reference count part of the pointer itself, so that acquiring a reference is a compare-and-swap on the pointer rather than an increment on the object. That works when the pointer and the count fit in one word, and it turns every read into a read-modify-write, which is a heavy price for the read side. Where the count does not fit, the scheme fails.

Reference counting also suffers from cycles: two objects referring to each other keep both alive forever. Lock-free structures are usually trees or lists, so cycles are rare, but a structure that permits them cannot use pure counting.

What RCU does differently

Read-copy-update is the scheme that made the epoch idea mainstream, and its distinguishing feature is that the read side can be made essentially free.

A reader marks the start and end of a critical section, and the writer publishes a new version and defers freeing the old one until a grace period has elapsed. A grace period is a period during which every thread has passed through a quiescent state, meaning a point at which it holds no reference to the protected structure.

The reason the read side can be free is that the marking need not be an explicit operation on every platform. If the kernel controls preemption, a context switch is a quiescent state, so a thread that is not running cannot be inside a read-side critical section, and the scheduler’s own bookkeeping suffices. In user space, a library must use explicit markers or signals, and the read side is no longer free.

The consequence for the API is that RCU protects pointers to immutable snapshots. A reader that traverses a structure published by RCU sees a consistent version, and a writer never modifies a published version in place; it builds a new one and swaps the pointer. That restricts the data structures RCU applies to, and it is why RCU shows up for read-mostly configuration and routing tables rather than for general containers.

Choosing among them

The axes are read-side overhead, memory retention, and tolerance for thread delays.

Hazard pointers have moderate read overhead (a store, a fence, a re-check) and bounded retention per stalled thread, since a stalled thread pins only the objects it hazarded. They work in user space without kernel support and do not require that the protected data be immutable.

Epoch schemes have low read overhead and retention proportional to what a stalled thread’s critical section touched. They are simpler to use correctly than hazard pointers because there is no re-check to get wrong, and they require a global epoch advance, which is a coordination point.

Reference counting has no retention beyond the reference itself and pays a read-modify-write per acquisition, with the cycle problem as a structural limitation.

RCU has the lowest read overhead on a platform that can define quiescent states for free, and the strictest requirement on the data: published versions must be immutable.

None of the three is uniformly better. The choice is determined by whether readers can tolerate a store, whether a stalled thread is a realistic scenario, and whether the protected data can be replaced rather than modified. What is not negotiable is that the structure needs one of them: a lock-free structure that frees nodes without a reclamation scheme is a structure that will eventually hand a thread a pointer to freed memory, and the failure will be a corrupt read of whatever has since been allocated at that address. The ABA interleaving described in The ABA Problem in Treiber Stacks is the same window seen from a different angle.