Lock-free data structures rely on atomic Compare-And-Swap (CAS) as their primitive synchronization operation. CAS takes three operands — a memory location, an expected value, and a desired value — and atomically performs:
// Conceptual model of CAS
bool CAS(std::atomic<T>& location, T& expected, T desired) {
if (location.load() == expected) {
location.store(desired);
return true;
}
expected = location.load();
return false;
}In C++ this is std::atomic<T>::compare_exchange_weak / compare_exchange_strong. The foundational assumption of CAS-based algorithms is: if the value at a location is still what I last read, then the world-state I reasoned about is still valid, and my update is safe. The ABA problem is a precise, surgical violation of this assumption.
ABA occurs when a thread reads value A from a shared location, is preempted, and during that preemption another thread (or threads) transforms the location A → B → A. When the original thread resumes and executes CAS(expected=A, desired=X), the CAS succeeds — because the raw value matches — but the success is semantically incorrect. The location looks the same but the underlying world-state has changed in ways the algorithm depended upon being stable.
The critical insight is that CAS is value-blind: it has no notion of identity or history, only bitwise equality of the current value against the expected value.
The canonical illustration uses a lock-free stack (Treiber stack):
struct Node {
int data;
Node* next;
};
std::atomic<Node*> top{nullptr};
void push(int val) {
Node* node = new Node{val, nullptr};
Node* old_top;
do {
old_top = top.load(std::memory_order_acquire);
node->next = old_top;
} while (!top.compare_exchange_weak(old_top, node,
std::memory_order_release,
std::memory_order_relaxed));
}
Node* pop() {
Node* old_top;
Node* new_top;
do {
old_top = top.load(std::memory_order_acquire);
if (!old_top) return nullptr;
new_top = old_top->next; // (*)
} while (!top.compare_exchange_weak(old_top, new_top,
std::memory_order_release,
std::memory_order_relaxed));
return old_top;
}The ABA scenario:
| Time | Thread 1 | Thread 2 |
|---|---|---|
| t1 | Reads top = A (A→B→C), snapshots new_top = B at line (*), then preempted |
— |
| t2 | — | Pops A, pops B (B is freed/recycled), pushes a new node that happens to be allocated at address A, pushes A again |
| t3 | Resumes. CAS(expected=A, desired=B) succeeds | — |
| t4 | Stack top is now B — a freed/recycled pointer | — |
The stack is now corrupted. Thread 1's CAS succeeded because the address of the top node is still A, but node B has been freed and is dangling. This is a use-after-free that no sanitizer at the language level will prevent, because the ABA problem lives at the algorithm level.
Several properties of C++ exacerbate the problem:
- Memory reuse.
operator newis free to return the same address for a newly allocated object. This makes the A→B→A transition trivially reproducible under allocator pressure. - No GC. Languages with garbage collection prevent node reclamation while any reference exists, which structurally prevents ABA in many (though not all) cases. C++ has no such guarantee.
- Wide atomics are expensive or unavailable. The most natural solution (tagging, described below) requires double-word CAS (DWCAS), which maps to
cmpxchg16bon x86-64 — available, but with significant throughput cost, and not universally supported (e.g., 32-bit ARM without LPAE). std::atomicof a pointer is just a pointer. There is no built-in versioning or provenance tracking.
The most classical mitigation. Each pointer is paired with a monotonically increasing tag. CAS operates on the pair, so even if the pointer cycles back to A, the tag A' ≠ A, and the CAS fails.
struct alignas(16) TaggedPtr {
Node* ptr;
uint64_t tag; // monotone counter, never wraps in practice
};
std::atomic<TaggedPtr> top{{nullptr, 0}};
void push(Node* node) {
TaggedPtr old_top, new_top;
do {
old_top = top.load(std::memory_order_acquire);
node->next = old_top.ptr;
new_top = {node, old_top.tag + 1};
} while (!top.compare_exchange_weak(old_top, new_top,
std::memory_order_release,
std::memory_order_relaxed));
}This requires 128-bit atomic CAS (std::atomic<TaggedPtr> with is_always_lock_free ideally true, requiring -mcx16 on x86-64). The tag counter can theoretically wrap, but a 64-bit counter at nanosecond-frequency operations would take ~585 years to wrap.
On platforms where 128-bit atomics are lock-free, this is the gold standard. On platforms where they are not, the runtime falls back to a lock, which defeats the purpose.
A common space optimization embeds the tag in the unused low bits of the pointer (alignment guarantee) or high bits (on x86-64, where only 48 bits of a 64-bit pointer are currently used by the OS). This keeps the pair in a single 64-bit word and enables true 64-bit CAS:
// Exploiting 16-bit tag in upper bits (x86-64 canonical form)
constexpr uintptr_t TAG_MASK = 0xFFFF'000000000000ULL;
constexpr uintptr_t PTR_MASK = ~TAG_MASK;
uintptr_t make_tagged(Node* p, uint16_t tag) {
return (static_cast<uintptr_t>(tag) << 48) |
(reinterpret_cast<uintptr_t>(p) & PTR_MASK);
}This is fragile and non-portable, but widely used in high-performance production code.
Proposed by Maged Michael (2004) and now standardized in C++26 (std::hazard_pointer). Each thread publishes a hazard record — a pointer to any node it is currently reading. Before a thread may reclaim a node, it must verify that no hazard record points to it.
// C++26 API sketch
std::hazard_pointer hp = std::make_hazard_pointer();
Node* pop() {
while (true) {
Node* old_top = top.load(std::memory_order_relaxed);
if (!old_top) return nullptr;
hp.protect(old_top, top); // publish hazard, then re-validate
if (top.load(std::memory_order_acquire) != old_top)
continue; // lost the race; retry
Node* new_top = old_top->next;
if (top.compare_exchange_strong(old_top, new_top,
std::memory_order_release,
std::memory_order_relaxed)) {
hp.reset_protection();
// Defer reclamation: check all hazard records before delete
retire(old_top);
return old_top;
}
}
}Properties:
- O(P) space overhead (P = number of threads) for hazard records.
- Reclamation is deferred: a retiring thread scans all hazard records, and only frees nodes not referenced by any of them. In the worst case, reclamation is delayed until the next
retire()call by any thread. - No ABA: a node cannot be reallocated at the same address while any thread holds a hazard to it, breaking the A→B→A cycle.
- Works on any platform with single-pointer-width atomics.
Threads operate in epochs (a global monotone counter). A node is only reclaimed when all threads have passed through at least one full epoch since the node was retired. Epochs advance when threads check in (call a quiescence function).
// Conceptual sketch
thread_local uint64_t local_epoch;
std::atomic<uint64_t> global_epoch{0};
void enter_critical() {
local_epoch = global_epoch.load(std::memory_order_acquire);
}
void exit_critical() {
local_epoch = INACTIVE;
}
void try_advance_epoch() {
// If all active threads are in current epoch, increment global
}
void retire(Node* p) {
// Add p to retired list for current epoch
// Reclaim nodes from epochs that all threads have passed
}Properties:
- Very low overhead in the common (fast) path — just a single store to
local_epoch. - Reclamation can stall indefinitely if a thread stalls inside a critical section.
- Used by practical systems: crossbeam-epoch (Rust), Folly's hazptr, libcds.
A specialization of EBR used heavily in the Linux kernel and in userspace RCU libraries. Threads report quiescent states (points where they hold no references to shared data). Reclamation proceeds after all threads have reported a quiescent state since a node was retired.
In userspace C++, liburcu provides this. The key tradeoff: quiescent states must be inserted explicitly by the programmer, but the fast path overhead is essentially zero (no per-object instrumentation).
On architectures providing LL/SC (ARM, RISC-V, PowerPC), ABA is structurally absent: SC fails if any write to the location occurred since the matching LL, regardless of whether the value returned to A. This is a hardware solution.
In C++, compare_exchange_weak may be implemented with LL/SC on such platforms, which means on ARM/RISC-V the Treiber stack without any additional mitigation is already ABA-safe at the hardware level — though C++ offers no portable guarantee of this, and spurious failures still require retry loops.
| Mitigation | ABA Prevention | Reclamation | Overhead | Portability |
|---|---|---|---|---|
| Tagged pointers | ✅ Prevents value recycling | Immediate | DWCAS cost or bit tricks | Platform-dependent |
| Hazard pointers | ✅ Prevents memory recycling | Deferred, bounded | O(P) scan per retire | Universal |
| Epoch-based (EBR) | ✅ Prevents memory recycling | Deferred, epoch-gated | Very low fast path | Universal |
| QSBR / RCU | ✅ Prevents memory recycling | Deferred, quiescent | Near-zero fast path | Universal |
| LL/SC hardware | ✅ Structural prevention | Immediate | None | ARM/RISC-V/PPC only |
The ABA problem is a manifestation of a fundamental tension in lock-free design: CAS provides value identity, but correct concurrent algorithms often require temporal identity — the guarantee that no intervening mutation occurred, not merely that the current value matches a snapshot. Every mitigation strategy above is, at its core, a mechanism for bridging this gap: either by making the value encode temporal information (tagged pointers), or by preventing the memory-level recycling that makes temporal and value identity diverge (safe memory reclamation schemes).
Note
Generated by Claude.ai
Model: Sonet 4.6
Prompt: Provide a thorough description of the ABA problem in the context of lock-free structures implemented in C++. This description is intended for a computer science expert. Explain how this problem can be mitigated.