The ABA Problem in Treiber Stacks

A Treiber stack is the smallest interesting lock-free structure: a singly linked list with a single atomic head pointer, pushed and popped by compare-and-swap against that pointer. The push is straightforward and, with a correctly re-read expected value, hard to get wrong. The pop is where the trouble is, and the trouble is not in the compare-and-swap. It is in what the compare-and-swap is unable to distinguish.

The push, and why it is easy

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

static _Atomic(node_t *) head;

void push(node_t *n)
{
    node_t *old = atomic_load_explicit(&head, memory_order_relaxed);
    do {
        n->next = old;
    } while (!atomic_compare_exchange_weak_explicit(&head, &old, n,
                 memory_order_release, memory_order_relaxed));
}

The new node is not reachable from head until the compare-and-swap succeeds, so no other thread can observe a partially linked node. The release ordering makes the write to n->next visible before the node becomes reachable. The only way this fails is if the caller frees n or mutates it after the push, which is a lifetime question rather than a structure question.

Push never removes anything, so the ABA problem cannot arise: the value stored in head is compared against, and if it matches, the node it points to is the same node that was there when the caller read it. Nothing was removed and reinstalled.

The pop, and where the window opens

node_t *pop(void)
{
    node_t *old = atomic_load_explicit(&head, memory_order_acquire);
    while (old) {
        node_t *next = old->next;                   /* read before the CAS */
        if (atomic_compare_exchange_weak_explicit(&head, &old, next,
                memory_order_acq_rel, memory_order_acquire))
            return old;
    }
    return NULL;
}

The read of old->next happens before the compare-and-swap, and the compare-and-swap only verifies that head still equals old. Between those two points, other threads may act. The dangerous interleaving has three steps:

Thread A reads head and gets node X, and reads X->next and gets Y. Thread A is then suspended. Thread B pops X and Y, and pushes X again. Now head is X once more, and X->next is whatever it was set to during the push, which may be Z rather than Y. Thread A resumes, its compare-and-swap sees head == X, succeeds, and installs X->next as the new head. If X->next is Z, the stack now skips Y and whatever Y pointed to. If thread B freed Y in the meantime, thread A has installed a dangling pointer.

The compare-and-swap did exactly what it promised. The value at head was X when A checked it. The problem is that the identity of X was not preserved: the same address now hosts the same node in a different state. The pointer comparison cannot tell “still the same node, unchanged” from “same node, removed and reinstalled”.

The window is between the load of old->next and the compare-and-swap. Making that window smaller by reordering the instructions is not a fix, because the compiler and the processor are both free to move the load later. Only a mechanism that either prevents removal during the window or makes the comparison sensitive to removal closes it.

Version tags

The classical remedy is to widen the compared word so that it includes a counter that increments on every successful modification. The compare-and-swap then compares the pair, and a node that was removed and reinstalled produces a different counter value even though the address matches.

typedef struct { node_t *ptr; unsigned long tag; } tagged_t;

Implementing this requires a double-width compare-and-swap. On x86-64 that is cmpxchg16b, which requires 16-byte alignment and operates on a 128-bit word. On 64-bit targets the tag is necessarily smaller than the pointer, so it can wrap: a tag that has wrapped to the same value while a thread held a stale observation reintroduces the ABA window, though at a rate that is negligible in practice. On 32-bit targets the same construction fits in an 8-byte compare-and-swap and the tag is proportionally wider, but the underlying problem is the same.

A variant packs the tag into unused bits of the pointer itself. Heap pointers on most 64-bit systems have alignment guarantees that leave the low three or four bits free, and some address spaces leave the high bits unused. That gives a small tag without a double-width operation, at the cost of depending on properties of the allocator and the virtual address layout that the language does not guarantee.

The tag approach has a second benefit beyond correctness: it converts the structure from lock-free-with-ABA into a genuinely correct lock-free structure, at the cost of a wider atomic and an alignment requirement that propagates to every allocation site. The double-width instruction and its alignment fault are covered in Compare-and-Swap and Why the Retry Loop Must Re-read. It does not solve reclamation, which is a separate problem: a tagged pointer still refers to memory that someone must eventually free.

Reclamation versus ABA

The two problems are often conflated because both are triggered by a node being removed and its storage being reused. They differ in what goes wrong.

ABA is a logical error: the structure ends up in a state that is inconsistent with the operations that were supposed to have happened, and the corruption is visible in the data. Reclamation is a memory-safety error: a thread dereferences or installs a pointer to storage that has been freed. A program can avoid ABA with tags and still have a use-after-free, and it can avoid use-after-free with hazard pointers and still suffer ABA if a node’s storage is not reused but its links are rearranged.

In the Treiber stack, a fully correct implementation needs both. Hazard pointers, epochs, and reference counting keep the memory alive, and they also prevent the specific reuse that produces ABA in most cases: if a node cannot be freed and reallocated while any thread holds a hazard on it, then the address-to-object mapping stays stable for the duration of the hazard, and the ABA interleaving cannot occur. That is why hazard pointers are often described as solving ABA as a side effect, and why a tagged implementation still needs a reclamation scheme. The full set of options is covered in Memory Reclamation for Lock-Free Structures.

Detecting ABA instead of preventing it

A different family of solutions accepts ABA and detects it. If the stack tracks the set of nodes that were removed, a pop that observes a change in that set can retry. This requires extra atomic state and tends to reintroduce contention on the tracking word.

A simpler practical mitigation applies when the popped node’s contents are not used after the compare-and-swap. If the caller only needs the head to advance and does not care which node it removed, the interleaving above is harmless: the structure remains a valid stack of the nodes that were present, and the popped node is whichever one the compare-and-swap actually removed. This is rarely true for a general-purpose container, but it is true for a stack used as a free list, where the exact node returned does not matter. That distinction, between a structure whose elements are interchangeable and one whose elements are not, is often the real question: an ABA-resistant design is not needed when the elements are indistinguishable.

Ordering on the pop’s two outcomes

The compare-and-swap in pop carries memory_order_acq_rel on success and memory_order_acquire on failure. The success ordering is both: the acquire half prevents the caller’s later use of the returned node from being hoisted above the exchange, and the release half publishes the write to head so that another thread popping next observes a consistent link.

The failure ordering cannot be relaxed here, which distinguishes this loop from the push. On failure the operation has loaded the current head value into old, and the loop then dereferences old->next. That dereference must not be hoisted above the load that produced the pointer, or the thread would read a link from a node it has not yet observed as the head. memory_order_acquire on failure supplies that ordering.

Why the stack is the standard example

The Treiber stack is the canonical demonstration because it isolates the problem in six lines. The same pattern appears in every lock-free structure that reads a link before verifying the node it came from: a queue whose dequeue reads the head’s next pointer, a list whose insertion reads a predecessor’s link, a hash table whose bucket walk follows pointers read before the bucket head was validated. In each case the verification is against an address, and the address is a weaker witness than the algorithm assumes.

The general statement of the constraint is that compare-and-swap provides a linearization point but not a snapshot. It can atomically verify one word, and any structure whose correctness depends on two words being consistent at that instant must either compress them into one word or provide a separate mechanism that makes the second word stable. The Treiber stack’s pop depends on head and head->next being consistent, and no single-word instruction can express that. Every remedy above is a way of making the second word stable or making the comparison sensitive to its change, and there is no third option.