The ABA Problem in C Lock-Free Stacks and Queues

The ABA problem is one of the most critical concurrency pitfalls encountered when developing lock-free data structures like stacks and queues in C. This article explores the mechanics of the ABA problem, why manual memory management in C exacerbates it, how it causes silent state corruption during atomic Compare-And-Swap (CAS) operations, and the standard strategies engineers use to resolve it.

Understanding the ABA Phenomenon

The ABA problem occurs during multithreaded execution when an atomic operation relies on memory state comparison to determine if a structure has changed. The sequence unfolds as follows:

  1. Thread 1 reads memory location \(V\), observing value A.
  2. Thread 1 is suspended or interrupted before completing its update.
  3. Thread 2 modifies location \(V\) from A to B.
  4. Thread 2 (or another thread) modifies location \(V\) back from B to A.
  5. Thread 1 resumes, performs a Compare-And-Swap (CAS) expecting A, and succeeds because the pointer value matches.

Although the value is indeed A, the underlying structural state, node topology, or linked references may have fundamentally shifted. Thread 1 executes its operation under the false assumption that nothing changed between reading and writing.

Why C Makes the ABA Problem Particularly Dangerous

In managed languages with automatic garbage collection (such as Java or Go), a node referenced by an active thread is kept alive, preventing its address from being immediately recycled. In C, however, developers manage memory manually using malloc and free.

When a thread pops a node from a lock-free structure and frees it, the system memory allocator frequently reuses that exact virtual address for subsequent allocations. Consequently, a new node can easily be assigned the same pointer address as a recently freed node. A pointer-based CAS checking for equality cannot distinguish between the original node and a newly allocated node that happens to share the same address.

Failure Case: The Treiber Stack

To illustrate the danger, consider a classic lock-free Treiber stack:

typedef struct Node {
    void *data;
    struct Node *next;
} Node;

Node *top;

A thread attempts to pop an item using the following logic:

Node *old_top;
Node *new_top;
do {
    old_top = top;
    if (old_top == NULL) return NULL;
    new_top = old_top->next;
} while (!atomic_compare_exchange_weak(&top, &old_top, new_top));

If Thread 1 reads top as node A and determines new_top to be B (A->next), it may pause before executing the CAS.

While Thread 1 is paused:

  1. Thread 2 pops A and frees it.
  2. Thread 2 pops B and frees it.
  3. Thread 2 pushes a new item, which malloc allocates at the same memory address where A previously resided.
  4. The stack now consists of the new A pointing to an entirely different node C.

When Thread 1 wakes up, it compares top against old_top (address A). Because the memory address matches, the CAS succeeds and sets top to new_top (address B). However, node B has already been freed and may contain garbage or be reallocated elsewhere. The stack's head pointer is now corrupted, pointing to invalid memory and inevitably leading to segmentation faults or undefined behavior.

Solutions in C

Resolving the ABA problem requires separating the identity of an address from its historical state:

  • Tagged Pointers (Double-Word CAS): Augment each pointer with an integer version counter. On 64-bit systems, a 128-bit atomic compare-and-swap (such as cmpxchg16b via atomic_compare_exchange_strong with __int128) updates both the pointer and the counter simultaneously. Even if memory is reused at address A, the counter differs, causing the CAS to safely fail.
  • Hazard Pointers: Active threads register the pointers they are currently reading into a globally visible hazard pointer array. A thread that removes a node cannot call free() on it until no other thread has that address registered as a hazard pointer.
  • Epoch-Based Reclamation (EBR): Memory reclamation is deferred across logical time intervals (epochs). Nodes removed in epoch \(N\) are only freed when all threads have progressed past epoch \(N\), guaranteeing that no thread holds a stale pointer to the freed node.