The ABA Problem & Tagged Pointers
ABA: thread A reads pointer P (= A); thread B pops A and pushes a new node at the same address; thread A's CAS succeeds even though the structure changed. Solutions: tagged pointers (pack version counter), hazard pointers (announce in-use), epoch-based reclamation, GC.
What ABA actually is
The name comes from the pattern of values that a memory location takes: it holds A, changes to B, then changes back to A. A thread that reads it before and after sees the same A both times and assumes nothing happened in between. But something did happen, and the thread is about to act on stale information.
The classic case is a lock-free stack written in a manual-memory language like C or C++. A typical pop reads the head pointer, reads head.next to compute the new head, then uses CAS to install the new head if the old head is still the same. The CAS check is "is stack.head still the pointer I read?". If the answer is yes, the pop swaps in the new head and is done.
This looks fine. The trouble is what can happen between the read and the CAS.
A picture of the bug
The stack starts with three nodes: head → A → B → C. Thread 1 starts a pop, reads the head, reads A.next, and is about to CAS. Then Thread 2 runs through several operations on the same stack before Thread 1's CAS happens.
Thread 1's CAS saw the same pointer value before and after, so it concluded "nothing changed". The pointer value really did not change. What changed was the meaning behind it: the node at that address used to be the original A, then got freed, and a different node was put at the same address by the allocator. The CAS happily installed B as the new head, even though B had been popped and freed in the meantime. The next thread that touches the stack reads from freed memory.
That is ABA.
Why GC languages usually sidestep this
In Java and Go, as long as Thread 1 is still holding a reference to the popped A node, the garbage collector keeps that node alive. The allocator cannot put a different object at the same address while any reference exists. So when Thread 2 allocates Z, the allocator hands out a fresh, unused address. Thread 1's CAS now sees a different pointer than it read at the start, the CAS fails, and the loop retries cleanly. The reference Thread 1 was holding acted as a kind of hazard pointer for free.
The contrast lines up like this:
| Step | Java / Go | C / C++ |
|---|---|---|
| Thread 1 holds the popped node as | a managed reference | a raw pointer |
| Garbage collector says | "A is reachable, do not free" | (no GC, manual memory) |
What free / re-allocation does | impossible while a reference exists | allocator may reuse A's address immediately |
| Thread 2 allocates a new node at | a fresh address | possibly the same address as the old A |
| Thread 1's CAS compares pointers and | sees a different pointer, fails, retries (correct) | sees the same pointer, succeeds (wrong) |
Where ABA sneaks back into GC languages
Object pools. Using sync.Pool in Go or any hand-rolled object recycler in Java (common in allocation-sensitive code: HFT, game engines, hot RPC paths) bypasses the garbage collector's address-reuse protection. The pool deliberately gives the same node back at the same address to avoid allocation. That is exactly the condition ABA needs. Be careful.
The four solutions, ranked
| Solution | Memory cost | Implementation cost | Notes |
|---|---|---|---|
| GC | Standard | Free | Java/Go default. Best for general use. |
| Tagged pointers | Pointer-size (no extra mem) | Low (AtomicStampedReference) | Java's standard solution. |
| Hazard pointers | ~1 pointer per thread per op | Medium | Used by JCTools, Folly. |
| Epoch-based | Per-thread epoch counter | Medium-high | Linux RCU. Best throughput, complex. |
When ABA actually needs thought
Writing lock-free code in:
- C/C++: every CAS on a pointer needs ABA protection.
- Java with object pools: bypasses GC protection.
- Go with
sync.Pool: same. - Anywhere with manual memory management.
For idiomatic Java/Go without pooling: usually safe to ignore ABA. The GC handles it.
The interview signal
What senior interviewers want
Knowing ABA exists. Recognizing when it applies (not always; only with manual memory or recycling). Naming the standard solutions. Knowing Java's AtomicStampedReference exists for exactly this case.
Junior signal: "ABA, just retry the CAS." (Wrong, retry doesn't help; the CAS already succeeded falsely.) Senior signal: "ABA matters when memory can be recycled at the same address. In GC languages, GC sidesteps it. With pools, use stamped references or hazard pointers."
Implementations
In Java, this code is safe. A popped node remains in memory until no references exist (GC). In C/C++, the popped node could be freed and immediately re-allocated at the same address, fooling CAS.
1 // Java, GC prevents address reuse, so this is safe:
2 class TreiberStack<T> {
3 static class Node<T> {
4 T value;
5 Node<T> next;
6 }
7 private final AtomicReference<Node<T>> head = new AtomicReference<>();
8
9 public void push(T item) {
10 Node<T> newNode = new Node<>();
11 newNode.value = item;
12 while (true) {
13 Node<T> oldHead = head.get();
14 newNode.next = oldHead;
15 if (head.compareAndSet(oldHead, newNode)) return;
16 }
17 }
18
19 public T pop() {
20 while (true) {
21 Node<T> oldHead = head.get();
22 if (oldHead == null) return null;
23 Node<T> newHead = oldHead.next;
24 if (head.compareAndSet(oldHead, newHead)) {
25 return oldHead.value;
26 }
27 }
28 }
29 }Java's AtomicStampedReference packs an int "stamp" (version counter) with the reference. CAS succeeds only if BOTH the reference AND stamp match, defeats ABA even without GC.
1 import java.util.concurrent.atomic.AtomicStampedReference;
2
3 class StackWithStamp<T> {
4 static class Node<T> { T value; Node<T> next; }
5
6 private final AtomicStampedReference<Node<T>> head =
7 new AtomicStampedReference<>(null, 0);
8
9 public T pop() {
10 int[] stamp = new int[1];
11 while (true) {
12 Node<T> oldHead = head.get(stamp);
13 int oldStamp = stamp[0];
14 if (oldHead == null) return null;
15 Node<T> newHead = oldHead.next;
16 // Bump stamp on every successful CAS, even if reference happens to match
17 if (head.compareAndSet(oldHead, newHead, oldStamp, oldStamp + 1)) {
18 return oldHead.value;
19 }
20 }
21 }
22 }Key points
- •Pure CAS is unsafe when the same address can be reused (typical in C/C++ with manual memory)
- •Java/Go avoid ABA via GC, freed memory not reused while references exist
- •Tagged pointers: pack a version counter into unused pointer bits (low 3 bits typically)
- •Hazard pointers: each thread declares pointers it's actively using; readers don't free those
- •Epoch-based reclamation: defer free until all threads have moved past the freeing epoch
Follow-up questions
▸What's a 'hazard pointer'?
▸What's epoch-based reclamation?
▸Tagged pointer, how does a counter fit in a pointer?
▸Does Java really not have ABA?
Gotchas
- !Reusing nodes from a pool reintroduces ABA even in GC languages
- !AtomicStampedReference adds overhead, use only when ABA is a real risk
- !Tagged pointers fail on architectures with 64-bit virtual addresses (some ARM)
- !Hazard pointers add 1 cache line per thread per concurrent operation, memory cost