The dangerous thing about a pointer is that it looks like a name.

It is not a name. It is an address. Addresses can be reused. Sometimes the same node can even leave and come back. A compare-and-swap instruction only sees the word you ask it to compare. If that word is equal, it does not tell you where it has been.

This is the ABA problem:

T1 sees A
T2 changes A -> B -> A
T1 sees A again
T1 assumes nothing changed

The second A is not evidence that time stood still. It is evidence that the same visible value is back in the shared location.

That distinction is enough to break a lock-free stack.

A Pop With One Bad Nap

The classic Treiber stack is beautifully small: a singly linked list with an atomic top pointer.1 Its pop operation has the shape below:

Node *old;
Node *next;

do {
  old = top;
  if (old == NULL) return EMPTY;
  next = old->next;
} while (!CAS(&top, old, next));

return old->value;

The linearization point is supposed to be the successful CAS. If top still equals old, swing the stack to next and return the old top. This is exactly the kind of tiny code that makes lock-free programming feel plausible.

Now start with:

top -> A -> B -> C

Thread T1 begins a pop:

old  = A
next = B

Then T1 pauses.

Thread T2 runs:

pop A        top -> B -> C
pop B        top -> C
push D@A     top -> D -> C

The last line is the evil one. D@A means a new node D lives at the same address that used to hold A. To a pointer-only CAS, the top address is back to A.

T1 wakes up and asks:

is top still 0xA0?

Yes.

So it writes the stale next it saved before the nap:

top := B

But B was already popped. The stack head now points at a retired node, and the live node D is no longer reachable. Nothing in the final pointer comparison said “two other pops happened here.”

That is the bug. Not a crash yet. Not necessarily a failing test. A data structure whose public face just accepted an impossible private history.

The Lab

The simulator below runs that exact interleaving. It compares four lanes:

  • Pointer-only CAS compares only the address stored in top.
  • Tagged head compares (address, version), so 0xA0, v0 differs from 0xA0, v3.
  • Hazard pointer lets T1 publish “I may still touch A,” which prevents the allocator from recycling A’s address while the hazard is active.
  • Tag + hazard uses both: one mechanism for history, one for safe reuse.

Change “what comes back on top.” The default is allocator address reuse. The “same A node returns” option is deliberately sharper: it shows why memory reclamation and logical history are different promises.

With the default settings, the lab audit checks 15 invariants. The pointer-only lane succeeds at the stale CAS and ends in a corrupt state: reachable retired B and live D is unreachable. The tagged lane rejects the same CAS because the head version has advanced to v3: pop A, pop B, push D. The hazard-pointer lane also rejects in the default scenario because A’s address is protected, so D is allocated fresh instead of at 0xA0.

The punchline is not “always add every defense.” It is: know which assumption you are defending.

A Tag Changes The Second A

The usual tagged-pointer repair stores a counter with the pointer:

head = (ptr, count)

Each successful head change increments count. T1 no longer compares only 0xA0; it compares (0xA0, 0). After T2’s three head changes, the visible address may be 0xA0 again, but the state is (0xA0, 3).

That is not ABA. It is ABA’:

(A, 0) -> (B, 1) -> (C, 2) -> (A, 3)

The address came back, but the state did not.

This is why many non-blocking algorithms use double-width CAS, pointer tagging, or an equivalent state word when a single pointer is not enough. The Michael and Scott queue pseudocode, for example, represents head and tail as a pointer plus an unsigned count.2 The Rochester synchronization notes also call out double-width CAS as a way to avoid ABA in related dual-stack and dual-queue algorithms.3

Tags are not magic. A small counter can wrap. A platform may not give you a cheap double-width CAS for the shape of pointer you want. Pointer low-bit tricks depend on alignment and address layout. But conceptually the fix is clean: compare enough state that “the pointer came back” is not confused with “nothing happened.”

A Hazard Pointer Makes A Stay Put

A tagged head defends the comparison. A hazard pointer defends memory reuse.

Maged Michael’s hazard-pointer paper starts from a blunt problem: in lock-free objects, one thread may remove a node while another thread still holds a private reference to it.4 With a lock, the remover often knows no one else can touch the node. Without a lock, that is exactly what you do not know.

The hazard-pointer protocol gives each participating thread a small number of published pointer slots. Before T1 dereferences A, it publishes A as hazardous, then validates that A is still the head. When T2 retires a node, it does not immediately hand that memory back for arbitrary reuse. It scans hazard pointers. If some hazard pointer still names the retired node, reuse is delayed.

In the default lab scenario, this is enough to stop the allocator from turning old A into new D@A while T1 is asleep. D gets a fresh address, the pointer CAS sees 0xD0 instead of 0xA0, and the stale CAS fails.

That is a memory-reclamation victory.

It is not the same thing as a history counter.

Switch the lab to “same A node returns.” In that scenario, the exact same node A is removed and later placed back on top. The hazard pointer can make A safe to read. It does not, by itself, make top == A mean “A never left.” The hazard lane is memory-safe but still accepts the stale pointer-only CAS; the tagged lane rejects it.

This caveat is where lock-free writing stops being folklore and becomes engineering. Hazard pointers are powerful. Michael’s paper shows how to use them for safe reclamation and ABA prevention under the method’s assumptions. But they are not a license to forget the data structure’s ownership and reuse rules. If your algorithm lets the same node leave and re-enter while another thread depends on an old next, you still need a proof that the comparison state is strong enough.

The Linearization Point Is Conditional

Herlihy and Wing’s linearizability condition says a concurrent operation should appear to take effect at some instant between call and return.5 In a Treiber pop, the successful CAS is the natural instant.

ABA is nasty because it forges the condition for that instant. The CAS succeeds, so the code believes it found a legal linearization point. But the private value next = B was read in an older stack epoch. By the time the CAS runs, assigning top := B no longer means “remove exactly the node I observed.” It means “write a pointer whose justification expired.”

That is why the bug is so compact. Every individual instruction is doing what it advertised. The failure lives in the assumption that a repeated word implies a repeated world.

What I Would Check In Real Code

If I were reviewing a lock-free stack, free list, pool, or intrusive queue, I would not start by asking whether it has CAS loops. CAS loops are the easy part. I would ask:

  • Can a node address be recycled while another thread may still hold it in a register?
  • Does every dereference of a possibly removed node have a reclamation discipline such as hazard pointers, epochs, reference counts, or a type-preserving allocator with clear lifetime bounds?
  • Does a successful CAS compare enough state to justify the update computed from earlier reads?
  • If the design permits nodes to move out and back in, what prevents the same-node ABA, not just allocator reuse?
  • Are the memory-ordering annotations part of the proof, or only part of the performance story?

That last question deserves its own article. ABA is not solved by sprinkling memory_order_seq_cst over stale logic. Ordering can make writes visible in a coherent way. It does not make a pointer remember the path it took.

The whole lesson fits in one sentence:

CAS validates equality, not biography.

If biography matters, put it in the state you compare, or make it impossible for the old biography to be reused.

  1. R. Kent Treiber, Systems Programming: Coping with Parallelism, IBM Almaden Research Center, Research Report RJ 5118, 1986. For an accessible reproduction of the stack pseudocode and the ABA replay, see Viktor Vafeiadis, “Shape-Value Abstraction for Verifying Linearizability”, VMCAI 2009. ↩

  2. Maged M. Michael and Michael L. Scott, “Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms”, PODC 1996 pseudocode page, which uses counted pointers for head and tail. ↩

  3. University of Rochester synchronization pseudocode notes, “Dual Data Structures”, noting double-width CAS as an ABA-avoidance requirement for the listed dual structures. ↩

  4. Maged M. Michael, “Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects”, IEEE Transactions on Parallel and Distributed Systems, 2004. ↩

  5. Maurice P. Herlihy and Jeannette M. Wing, “Linearizability: A Correctness Condition for Concurrent Objects”, ACM Transactions on Programming Languages and Systems, 1990. ↩