Lock-Free Reclamation: ABA, Tagged Pointers, and Hazard Pointers

A lock-free stack push is easy: allocate a node, set its next pointer to the current head, and compare-and-swap the head from the old value to the new node. A lock-free pop is harder than it looks, and the difficulty is not the exchange. It is the moment after the exchange, when the popped node must be freed. Freeing it immediately can hand its memory to another thread that is still reading it; freeing it later requires knowing when later is safe. Between those two lies a correctness problem that no amount of care with the compare-and-swap itself can solve.

The pop that succeeds against a ghost

Consider the textbook pop, written with a compare-and-swap on the head:

#include <stdatomic.h>

struct node { int value; struct node *next; };

static _Atomic(struct node *) head;

struct node *pop(void)
{
    struct node *old = atomic_load_explicit(&head, memory_order_acquire);
    while (old != NULL) {
        struct node *next = old->next;      /* may read a node being freed */
        if (atomic_compare_exchange_weak_explicit(&head, &old, next,
                memory_order_acquire, memory_order_relaxed))
            return old;                     /* caller frees old */
        /* the exchange reloaded old from head; try again */
    }
    return NULL;
}

Two threads, T1 and T2, both pop. T1 reads the head, which is node A, and reads A’s next, which is B. T2 also reads the head as A and A’s next as B. T1’s compare-and-swap succeeds, the head becomes B, and T1 frees A. T2’s compare-and-swap then runs and fails, since the head is no longer A. T2 retries, reads the head as B, and proceeds. Nothing has gone wrong yet, provided T2 does not touch A after T1 freed it. But T2 already read A->next before its compare-and-swap, and that read happened while A was still allocated only if the timing was lucky. If T2’s read of A->next is delayed until after T1’s free, T2 reads freed memory, which may have been reallocated as something else entirely.

The ABA problem is a different shape and is often confused with this one. Suppose T1 reads the head as A, reads A’s next as B, and is preempted. T2 pops A, pops B, and then pushes A back. The head is now A again, and A’s next now points to whatever was the head before the push, which may be a different node or NULL. T1 resumes and its compare-and-swap succeeds, because the head still holds the value A. T1 sets the head to B, which is the node it read before T2 changed anything. B may have been freed in the meantime. The stack now points at freed memory, and the compare-and-swap reported success.

The distinction matters because the remedies differ. Reading a freed node is a lifetime problem that any reclamation scheme solves. ABA is a value-identity problem: the compare-and-swap cannot tell “unchanged” from “changed and changed back”, and a scheme that merely delays reclamation does not fix it if the same address is legitimately reused while the operation is in flight.

Tagged pointers and the width they need

The direct fix for ABA is to widen the compared value so that a return to the same pointer also changes the accompanying tag. A 64-bit pointer leaves no room on x86-64 for a counter, since the address space already uses most of the word. The standard trick is a double-width compare-and-swap: on x86-64, CMPXCHG16B operates on 16 bytes atomically, so a pointer and a 64-bit version counter can be updated together. The counter increments on every successful modification, and a pop that observes a stale counter fails even though the pointer matches.

struct tagged_ptr {
    struct node *ptr;
    unsigned long tag;
};

/* A 16-byte atomic value: needs 16-byte alignment, CMPXCHG16B on x86-64. */
static _Atomic(struct tagged_ptr) head;

static void push(struct node *n)
{
    struct tagged_ptr old = atomic_load(&head);
    struct tagged_ptr new;

    do {
        n->next = old.ptr;
        new.ptr = n;
        new.tag = old.tag + 1;              /* a new generation of the head */
    } while (!atomic_compare_exchange_weak(&head, &old, new));
}

The scheme has costs that are easy to underestimate. The counter can wrap, and a wrap at exactly the wrong moment reintroduces ABA; 64 bits of counter makes that impossible in practice but not in principle. The 16-byte access requires 16-byte alignment, which constrains the layout of the containing structure. Not every architecture has a 128-bit atomic compare-and-swap: 32-bit x86 has CMPXCHG8B for 8 bytes, which allows a 32-bit pointer plus a 32-bit tag, and the tag then wraps after about four billion operations. Some architectures provide a load-linked/store-conditional pair instead, and the pair does not need tagging at all for ABA, since the conditional store fails if the line was written, but it does not solve the lifetime problem.

Tagging also interacts badly with reclamation in a way that is worth stating: it detects that the pointer returned to the same value, but it does not tell the popper whether the node it read is still the node it will get. A successful compare-and-swap with a matching tag is a genuine success, because the tag proves no modification occurred in between. A successful compare-and-swap with a matching pointer and a mismatched tag is the ABA case, and failing it is correct.

Hazard pointers: announcing the pointers a thread dereferences

The alternative family does not change the compare-and-swap at all. It changes the reclamation. Each thread publishes the pointers it is currently dereferencing in a small per-thread array of hazard slots, and a thread that wants to free a node checks every slot first. If any slot holds the node’s address, the free is deferred; if none does, the node can be freed, because no thread that has announced a hazard can be inside the window between loading the pointer and finishing with it.

The protocol for a reader is: load the pointer, store it into a hazard slot with release semantics, then re-read the pointer and confirm it still matches. The re-read is the essential step. Without it, the following sequence is possible: the reader loads a pointer to A, a writer removes A and frees it, the reader stores A into its hazard slot, and then the reader dereferences freed memory. The writer’s scan saw no hazard because the reader had not yet published one. With the re-read, the reader notices that the pointer changed and retries before dereferencing.

The protocol for the writer is: after removing a node, put it on a private retired list; when that list reaches a threshold, scan all hazard slots and free every retired node not found in one. The threshold is what makes the scan amortized rather than per-free, and it is typically set so that the scan cost is bounded relative to the number of retired nodes.

The trade is precise. A reader pays a store and a load per pointer it protects, plus a fence in the general case. A writer pays a scan proportional to the number of threads times the number of hazard slots per thread, each scan amortized over the threshold. Memory is bounded: a node is freed at the first scan that finds no hazard pointing at it, so the retirement list holds at most the threshold plus one scan’s worth of nodes. No thread can be blocked by another, and no thread can be starved, because the protocol never waits.

The limits are that the number of hazard slots per thread must be a static bound, since a reader that needs more simultaneous hazards than it has slots must nest or copy, and that the scan cost grows with the thread count. A design with a thousand threads and four slots each scans four thousand words per reclamation round, which is cheap in absolute terms but not free.

Epochs: bounding the interval instead of the pointer

Epoch-based reclamation takes a different approach. The system maintains a global epoch number and a per-thread record of the epoch in which the thread last entered a critical section. A reader announces the current epoch on entry and clears it on exit. A writer that retires memory waits until every thread has either announced a newer epoch or is not in a critical section, and then frees everything retired in epochs older than the current one.

The reader’s cost is a load, a store, and a fence per critical section, and it is paid once per section rather than once per pointer. That is cheaper than hazard pointers when a section touches many nodes, which is common in a tree traversal. The writer’s cost is a wait rather than a scan: the free happens when the epoch advances, not when the last hazard disappears.

The failure mode is the one that makes epochs unsuitable for general-purpose code. A thread that is preempted inside a critical section, or that blocks inside one, prevents the epoch from advancing, and every retired object accumulates behind it. There is no bound on the memory used while that thread is stalled. The remedy is to evict a stalled thread from its epoch, which is only possible if the runtime can tell that the thread is not making progress, and that requires cooperation from the scheduler or a timeout. Hazard pointers have no such failure mode, because a stalled thread’s hazard protects only the nodes it names, not everything retired since it entered.

Epoch schemes are therefore a good fit for a runtime that controls its own threads and can guarantee that critical sections are short and non-blocking. They are a poor fit for a kernel or a library that cannot make that guarantee about its callers.

What the reclamation scheme cannot fix

None of these mechanisms makes an arbitrary data structure lock-free. Three constraints remain.

The compare-and-swap target must be a single word or a double word that the hardware can update atomically. A structure whose update touches three independent words cannot be updated with one compare-and-swap, and no reclamation scheme changes that; it needs a different algorithm, such as a descriptor-based one in which the operation itself is published and other threads help complete it.

Progress is not guaranteed for any particular thread. A lock-free algorithm guarantees that some thread makes progress, not that every thread does. A thread that repeatedly loses the compare-and-swap race can retry indefinitely, and the retry loop’s cost grows with contention. The formal guarantee is weaker than a lock’s, which is why lock-free structures are chosen for their fault tolerance rather than for their latency.

And the memory ordering is still the programmer’s responsibility. A compare-and-swap with acquire semantics on success and relaxed on failure is the usual choice for a pop, and a release on push. Getting those annotations wrong produces a structure that is atomic but incoherent, and the symptom is a node that appears in two lists at once or a value read from a node that was never fully initialized.

The narrower alternative for read-mostly data, where writers are rare and readers do not modify, is covered in read-copy-update and grace periods. The primitive that all of these schemes are built on is described in atomic read-modify-write. The case where the operation must be ordered against a scheduler decision rather than against another thread is the subject of priority inversion and inheritance.