Lock-Free Programming - Java (Part 7)
The ABA Problem — Lock-Free's Sneaky Villain
You've built a lock-free stack and a lock-free queue. Everything looks correct. CAS verifies the expected value before swapping. What could go wrong?
Enter the ABA problem: a subtle bug where CAS succeeds even though the value was changed and changed back. It's like checking that the book on your nightstand is "Harry Potter" — it is, but while you were away, someone borrowed it and returned a different copy with missing pages.
The Problem Explained
CAS checks: "Is the current value equal to what I expected?" But it doesn't check: "Has the value been the same the entire time since I read it?"
A Simple Analogy
ABA in a Lock-Free Stack
Let's see a concrete example with the Treiber Stack from Article 5.
The Setup
Stack: [A, B, C] (A is the top).
The ABA Scenario
What Went Wrong?
Thread 1's CAS checked that head == A — and it was! But the internal structure of the stack had completely changed. The node B that Thread 1 planned to make the new head had already been popped and was no longer part of the stack.
When Is ABA Actually Dangerous?
ABA is mostly a concern in languages without garbage collection (C, C++, Rust) where popped nodes can be freed and their memory reused. When a new node is allocated at the same memory address as a deleted one, CAS sees the same pointer value and succeeds incorrectly.
In Java, ABA Is Rare (But Not Impossible)
Java's garbage collector prevents memory reuse while any reference to an object exists. So in the Treiber Stack scenario above, as long as Thread 1 holds a reference to node A, the GC won't reclaim it.
However, ABA can still occur in Java when:
You reuse objects (e.g., object pools)
The logical meaning changes even though the reference is the same
You use integers (e.g.,
AtomicInteger) — the value5→3→5is classic ABA
Solution 1: AtomicStampedReference (Version Counter)
The most straightforward solution: pair each reference with a version number (stamp). The CAS checks both the reference AND the stamp.
import java.util.concurrent.atomic.AtomicStampedReference;
public class ABAFreeStack<T> {
private static class Node<T> {
final T value;
final Node<T> next;
Node(T value, Node<T> next) {
this.value = value;
this.next = next;
}
}
// Pair the head reference with a version stamp
private final AtomicStampedReference<Node<T>> head =
new AtomicStampedReference<>(null, 0);
public void push(T value) {
int[] stampHolder = new int[1];
Node<T> currentHead;
Node<T> newHead;
int newStamp;
do {
currentHead = head.get(stampHolder);
int currentStamp = stampHolder[0];
newHead = new Node<>(value, currentHead);
newStamp = currentStamp + 1;
} while (!head.compareAndSet(
currentHead, newHead,
stampHolder[0], newStamp // Must match BOTH ref and stamp
));
}
public T pop() {
int[] stampHolder = new int[1];
Node<T> currentHead;
Node<T> newHead;
do {
currentHead = head.get(stampHolder);
if (currentHead == null) {
return null;
}
newHead = currentHead.next;
} while (!head.compareAndSet(
currentHead, newHead,
stampHolder[0], stampHolder[0] + 1 // Increment stamp
));
return currentHead.value;
}
}
How It Defeats ABA
The stamp has changed from 0 to 3, so even though the reference is back to A, the CAS correctly detects that something changed.
Solution 2: AtomicMarkableReference
When you only need to know if something changed (not how many times), use AtomicMarkableReference with a boolean mark:
import java.util.concurrent.atomic.AtomicMarkableReference;
public class MarkableNode<T> {
T value;
AtomicMarkableReference<MarkableNode<T>> next;
MarkableNode(T value, MarkableNode<T> next) {
this.value = value;
this.next = new AtomicMarkableReference<>(next, false);
}
/**
* Mark this node as logically deleted.
* The node stays in the list but is "flagged."
*/
public boolean markDeleted() {
MarkableNode<T> nextNode = next.getReference();
return next.compareAndSet(nextNode, nextNode, false, true);
}
public boolean isDeleted() {
return next.isMarked();
}
}
This pattern is commonly used in lock-free linked lists (like the Harris list), where deletion is a two-step process: first mark the node (logical delete), then unlink it (physical remove).
Solution 3: Immutable Nodes (Java's Natural Defense)
In Java, the simplest defense against ABA is to never reuse nodes:
// Each push creates a NEW node — ABA is impossible
public void push(T value) {
Node<T> newNode = new Node<>(value, null); // Always fresh object
// ...
}
Since Java uses garbage collection and each new Node(...) creates a unique object on the heap, two different nodes will never have the same reference (identity). This makes ABA impossible for reference-based CAS in most Java code.
When Do You Need ABA Protection in Java?
| Scenario | ABA Risk | Solution |
|---|---|---|
AtomicReference with new nodes each time |
None | No protection needed |
AtomicReference with object pooling |
High | Use AtomicStampedReference |
AtomicInteger / AtomicLong counters |
Low | Usually fine (counters are monotonic) |
AtomicInteger with wrap-around state |
Medium | Use AtomicStampedReference or redesign |
| Lock-free linked list deletions | Medium | Use AtomicMarkableReference |
Decision Flowchart
Advanced: Hazard Pointers (C/C++ World)
For completeness, here's how non-GC languages handle ABA. This is NOT needed in Java, but understanding it deepens your appreciation for the complexity.
In C/C++, when you pop a node, you can't immediately free it — another thread might be in the middle of reading it. Hazard pointers are a mechanism where each thread publishes "I'm currently looking at this node — don't free it."
In Java, the GC does this automatically. Be grateful. 😄
Practical Example: ABA-Safe State Machine
Here's a real-world scenario where ABA matters — a state machine that can cycle through states:
import java.util.concurrent.atomic.AtomicStampedReference;
public class ConnectionState {
enum State { DISCONNECTED, CONNECTING, CONNECTED, DISCONNECTING }
// State can cycle: DISCONNECTED → CONNECTING → CONNECTED →
// DISCONNECTING → DISCONNECTED (ABA!)
private final AtomicStampedReference<State> state =
new AtomicStampedReference<>(State.DISCONNECTED, 0);
public boolean tryConnect() {
int[] stampHolder = new int[1];
State current = state.get(stampHolder);
if (current != State.DISCONNECTED) {
return false; // Can only connect from DISCONNECTED
}
// Without the stamp, another thread could cycle through
// all states back to DISCONNECTED, and our CAS would
// wrongly succeed without us knowing the context changed.
return state.compareAndSet(
State.DISCONNECTED, State.CONNECTING,
stampHolder[0], stampHolder[0] + 1
);
}
public boolean tryDisconnect() {
int[] stampHolder = new int[1];
State current = state.get(stampHolder);
if (current != State.CONNECTED) {
return false;
}
return state.compareAndSet(
State.CONNECTED, State.DISCONNECTING,
stampHolder[0], stampHolder[0] + 1
);
}
}
Key Takeaways
ABA occurs when a value changes from A → B → A, making CAS wrongly believe nothing changed
In Java with fresh objects, ABA is not a problem — GC ensures unique references
ABA is dangerous with object pools, integer states that cycle, or in C/C++
AtomicStampedReferencepairs a reference with a version counter — the most robust solutionAtomicMarkableReferencepairs a reference with a boolean — useful for logical deletion flagsWhen in doubt: use immutable objects + always allocate new nodes = ABA-free by design