How Does the ABA Problem Arise in Compare-and-Swap?

The ABA problem is a concurrency anomaly that occurs in lock-free algorithms using compare-and-swap operations when a shared memory location changes from value A to value B and then back to value A between a thread's read and its atomic update. Because compare-and-swap only checks whether the current value matches the expected value A, the thread mistakenly concludes that nothing has changed and proceeds with an operation that may corrupt the data structure.

Understanding Compare-and-Swap

Compare-and-swap (CAS) is an atomic hardware instruction that forms the foundation of many lock-free data structures, such as stacks, queues, and linked lists. It takes three arguments: a memory address \(M\), an expected old value \(E\), and a new value \(N\).

\[\text{CAS}(M, E, N)\]

Atomically, the processor checks whether the value currently stored at \(M\) equals \(E\). If it does, the processor writes \(N\) to \(M\) and returns true. Otherwise, it leaves \(M\) unchanged and returns false.

In a typical lock-free algorithm, a thread reads the current state from \(M\) into a local variable \(E\), computes a new state \(N\) based on \(E\), and then attempts \(\text{CAS}(M, E, N)\). If the CAS fails, another thread modified \(M\) in the meantime, so the thread retries.

How Memory Reuse Triggers the ABA Problem

The core limitation of CAS is that it tests for value equality, not history. It cannot distinguish between a memory location that has never changed and one that was modified and later restored to its original value.

Consider a lock-free stack implemented as a singly linked list with a shared top pointer. Suppose the stack initially contains nodes \(A \rightarrow B \rightarrow C\), where top points to \(A\).

  1. Thread 1 begins a pop operation. It reads top (which is \(A\)) and reads A.next (which is \(B\)). Before Thread 1 can execute \(\text{CAS}(\text{top}, A, B)\), the operating system preempts it.
  2. Thread 2 runs and pops \(A\) from the stack, leaving top pointing to \(B\).
  3. Thread 2 then pops \(B\) from the stack, leaving top pointing to \(C\).
  4. Thread 2 frees the memory for node \(A\) (or returns it to a memory pool) and later allocates a new node, which happens to reuse the exact same memory address \(A\).
  5. Thread 2 pushes this reused node \(A\) back onto the stack, so the stack is now \(A \rightarrow C\), and top points to \(A\) again.
  6. Thread 1 resumes and executes \(\text{CAS}(\text{top}, A, B)\). Because top currently holds the address \(A\), the CAS succeeds!

As a result, top is updated to \(B\), even though \(B\) was already popped and potentially freed. The stack is now corrupted, pointing to invalid or reclaimed memory, and node \(C\) is lost.

Why It Matters in Classical Computing

In garbage-collected languages, a node cannot be freed and reused while Thread 1 still holds a reference to \(A\), which prevents address reuse from causing this specific pointer-based failure. However, in languages with manual memory management like C and C++, or in systems using custom memory allocators and object pools, freed memory addresses are frequently recycled for performance.

The ABA problem can also occur without pointers. If a shared integer counter wraps around or is incremented and decremented back to its original value \(A\), a CAS checking only that integer will still succeed.

Common Mitigations

Several techniques exist to prevent the ABA problem:

  • Tagged Pointers (Version Counters): Pair the pointer with a monotonically increasing version number or tag, often packed into unused bits of a 64-bit pointer or using a double-width CAS (\(\text{DCAS}\)). Each modification increments the tag, turning \((A, v_1)\) into \((B, v_2)\) and then \((A, v_3)\), so \(\text{CAS}\) against \((A, v_1)\) fails.
  • Hazard Pointers: Threads publish the memory addresses they are currently reading in a shared list. A thread cannot free or reuse a node while its address appears in any thread's hazard pointer list.
  • Epoch-Based Reclamation (EBR): Memory reclamation is deferred until all threads that were active during the epoch in which the node was removed have finished their operations.