The ABA Problem in C++ Lock-Free Programming

The ABA problem is a critical synchronization hazard in multithreaded environments where a memory location is read, modified to a new value, and then restored to its original value, causing an atomic Compare-And-Swap (CAS) operation to falsely conclude that no state changes occurred. This article explains the mechanics of the ABA problem within lock-free data structures, illustrates how it causes data corruption, and outlines the standard techniques used to address it in modern C++, including tagged pointers, hazard pointers, and atomic shared pointers.

Understanding the ABA Problem

Lock-free algorithms rely heavily on the Compare-And-Swap (CAS) primitive—represented in C++ by std::atomic::compare_exchange_weak and std::atomic::compare_exchange_strong. A CAS operation checks whether an atomic variable matches an expected value; if it does, it updates the variable to a new value.

The ABA sequence occurs when:

  1. Thread 1 reads memory location L, observing value A.
  2. Thread 1 is suspended before it can execute a CAS operation.
  3. Thread 2 modifies L from A to B.
  4. Thread 2 (or another thread) modifies L from B back to A.
  5. Thread 1 resumes and executes CAS(L, expected: A, desired: C).

Because the value at L is currently A, the CAS operation succeeds. However, the underlying system state may have changed dramatically between the initial read and the CAS, violating the algorithm's correctness guarantees.

The Problem in Practice: The Lock-Free Stack

The most common manifestation of the ABA problem occurs in pointer-based dynamic data structures, such as a lock-free Treiber stack.

Consider a stack with the layout: Top -> NodeA -> NodeB -> NodeC.

  1. Thread 1 prepares to pop a node. It reads Top as NodeA and determines the new top should be NodeA->next, which points to NodeB.
  2. Thread 1 is preempted before executing compare_exchange_strong(Top, NodeA, NodeB).
  3. Thread 2 pops NodeA and NodeB. The stack now has Top -> NodeC.
  4. NodeB is deleted.
  5. Thread 2 pushes a new node or reuses the allocated memory for NodeA, pushing it back onto the stack. The stack is now: Top -> NodeA -> NodeC.
  6. Thread 1 resumes. Its CAS checks if Top == NodeA. Since Top points to NodeA again, the CAS succeeds and sets Top to NodeB.

Because NodeB was already freed in step 4, Top now points to invalid, deallocated memory, leading to silent memory corruption, segmentation faults, or undefined behavior.

Mitigations in C++

Addressing the ABA problem requires ensuring that either the identity of a state cannot be duplicated inadvertently or that memory is not recycled while concurrent readers exist.

1. Tagged Pointers (Double-Word CAS)

The most common hardware-level solution is associating a monotonic sequence counter (tag or generation counter) with the pointer. Every time the pointer is modified, the counter increments.

In C++, this can be implemented by packing a pointer and an integer into a single 128-bit structure on 64-bit architectures, relying on double-word CAS instructions (such as CMPXCHG16B on x86-64):

struct TaggedPointer {
    Node* ptr;
    uintptr_t tag;
};

std::atomic<TaggedPointer> top;

Even if ptr changes from NodeA to NodeB and back to NodeA, tag will have advanced from N to N + 2. The CAS will compare both ptr and tag, detect the mismatch, and fail safely.

Alternatively, on 64-bit platforms where virtual address spaces only use 48 bits, the unused upper 16 bits of a pointer can store the version tag directly, fitting into a standard 64-bit std::atomic<uintptr_t>.

2. Hazard Pointers

Hazard pointers solve the problem at the memory reclamation layer. When a thread reads a pointer, it registers the address in a thread-local "hazard pointer" array visible to all threads.

Before any thread frees memory:

  1. It retires the node to a private reclamation list.
  2. It scans all threads' hazard pointers.
  3. If a retired node’s address matches an active hazard pointer, deallocation is postponed.

Because NodeA cannot be freed while Thread 1 retains a reference to it, its address cannot be recycled and pushed back to the stack during Thread 1's operation. Hazard pointers are integrated into the C++ standard library starting in C++26 via <hazard_pointer> (std::hazard_pointer), but can be implemented manually in earlier standards.

3. Epoch-Based Reclamation (EBR)

Similar to hazard pointers, Epoch-Based Reclamation defers memory deallocation. Global time is divided into logical epochs. Threads announce their arrival in the current epoch when entering a critical lock-free section.

A node is only deleted once all threads have advanced past the epoch in which that node was removed from the active data structure. This prevents rapid pointer recycling, ensuring that a memory address cannot be reused while an older thread is still attempting a CAS on it.

4. Atomic Shared Pointers (std::atomic<std::shared_ptr<T>>)

In C++20, std::atomic<std::shared_ptr<T>> provides atomic operations on reference-counted pointers.

std::atomic<std::shared_ptr<Node>> top;

When a thread reads top, the reference count increments. Even if another thread pops the node, the memory is not deleted because the reading thread still holds an active reference. Because memory cannot be recycled while a thread holds the pointer, the exact pointer identity cannot be reintroduced via memory reallocation, avoiding the ABA hazard entirely.