How does attaching a version counter to a shared pointer — a stamped or tagged reference updated by a single wide compare-and-swap — prevent the ABA problem, and what are the limits of that technique?

middleshould knowfreq 32%

answer

(pointer, version) as one atomic unit
version increments on every successful update
double-width CAS / stolen alignment bits / boxed pair
wraparound is the residual hole
detects change; does NOT make freeing safe

basics

~20 s

You compare-and-swap the pointer and a counter as one unit, bumping the counter on every update. A value that leaves and returns comes back with a different stamp, so the compare-and-swap fails and the thread retries. Limits: it needs a wide atomic, the counter can wrap, and it does not make freeing memory safe.

solid answer

~60 s

Requirements and limits:

You need one atomic wide enough for both. Either a double-width compare-and-swap, or spare bits stolen from an aligned pointer (alignment guarantees a few low zero bits), or an indirection object that is itself replaced atomically — which allocates on every update.
Counters wrap. With only a handful of stolen bits, a thread stalled long enough can see the counter return to its old value; wide counters make this unreachable in practice rather than impossible in theory.
It solves detection, not lifetime. Tagging tells you the world moved. It does not make it safe to have dereferenced the freed node while reading its next. Without garbage collection you still need hazard pointers, epochs, or read-copy-update on top.

ABA needs the compared value to recur. Tagging removes recurrence: the atomic word holds (pointer, version), every successful update increments the version, so (A, 7) and (A, 9) are distinguishable even though the pointer is identical. A thread that read (A, 7) will fail its compare-and-swap and retry with fresh state. Requirements and limits: - **You need one atomic wide enough for both.** Either a double-width compare-and-swap, or spare bits stolen from an aligned pointer (alignment guarantees a few low zero bits), or an indirection object that is itself replaced atomically — which allocates on every update. - **Counters wrap.** With only a handful of stolen bits, a thread stalled long enough can see the counter return to its old value; wide counters make this unreachable in practice rather than impossible in theory. - **It solves detection, not lifetime.** Tagging tells you the world moved. It does not make it safe to have dereferenced the freed node while reading its `next`. Without garbage collection you still need hazard pointers, epochs, or read-copy-update on top.

code

text · 7 lines

text

push(node):
  loop:
    (head, ver) = cell.load()
    node.next = head
    if CAS(cell, expect=(head, ver), new=(node, ver+1)):
      return
    # any intervening update bumped ver -> we fail and re-read

go deeper

for a junior

Know the shape: pointer plus counter compared together, counter bumped on every write, so a returning value looks different.

for a middle

Explain why the pair must move in one atomic operation, and name at least one packing mechanism (double-width compare-and-swap or stolen alignment bits).

for a senior

Separate detection from lifetime: tagging fixes the false success, reclamation fixes the unsafe dereference. Discuss wraparound risk with narrow counters.

for a principal

Argue for designing recurrence out (monotonic sequence numbers, non-recycled indices) versus paying for tagging plus reclamation, and weigh portability of wide atomics across target architectures.

The idea

The ABA problem exists because a compared value can recur. A version tag makes recurrence impossible by widening the compared value with a counter that only goes up. The shared cell holds a pair — (pointer, version) — and every successful update writes (newPointer, version + 1) in a single atomic operation. Now the compare-and-swap's value equality test coincides with the property the algorithm actually needs: nothing has been installed here since I looked.

cell = (A, 7)
T1: reads (A, 7), computes newHead = B
T2: pops A  -> (B, 8) ; pops B -> (C, 9) ; pushes A -> (A, 10)
T1: CAS(cell, expected=(A,7), new=(B,8))  ->  FAILS, cell is (A,10)
T1: retries from a fresh read

The algorithm is unchanged apart from carrying the stamp; the retry loop it already had absorbs the failure.

How the pair is made atomic

Three common mechanisms, all doing the same job:

Double-width compare-and-swap. Many architectures offer a compare-and-swap over two adjacent machine words, so a 64-bit pointer plus a 64-bit counter is one atomic unit. This is the cleanest form and gives a counter so wide that wraparound is not a practical concern.
Bit stealing. Objects aligned to 8 or 16 bytes leave the low pointer bits always zero, and on many 64-bit systems the top bits of a virtual address are unused. Packing a small counter into those bits keeps everything in one ordinary word, at the cost of a very small counter (often 8–16 bits) and portability assumptions about address layout.
Immutable pair object. Allocate a small record holding the pointer and stamp, and compare-and-swap the reference to that record. Conceptually simplest and portable, but every update allocates — and the record itself now has a lifetime question, which garbage-collected runtimes answer for free and manual-memory languages do not.

What tagging does and does not buy

Buys: detection of intervening modification. A stamped compare-and-swap succeeding is a genuine proof that no update landed on that cell since the read, which restores the reasoning the optimistic algorithm depends on.

Does not buy: safe memory reclamation. Consider the stack pop again. The thread reads head = A, then dereferences A.next. If A was popped and freed in the meantime, that dereference is a use-after-free — it may crash, or read arbitrary reused bytes — and it happens before the compare-and-swap ever runs. Tagging makes the compare-and-swap fail afterwards, which is too late; the illegal read already occurred. In a garbage-collected runtime the node is kept alive by the thread's own reference, so the dereference is merely stale rather than illegal, and tagging alone is sufficient. In manual-memory code you also need a scheme that defers freeing until no thread can still be looking: hazard pointers, epoch-based reclamation, or read-copy-update.

Costs: wraparound is the theoretical hole — a thread stalled for 2^k updates with a k-bit counter can be fooled again, so small stolen-bit counters are a real risk under heavy update rates while 64-bit counters are not. Double-width compare-and-swap is also somewhat more expensive than a single-word one and is not universally available; on load-linked/store-conditional machines it is often unnecessary, because store-conditional fails on any intervening write to the reservation, giving ABA immunity for free at that granularity.

Another cost is spurious retries. The tag turns benign coincidences into failures. If the pointer legitimately returns to A and installing B is still the correct action, a tagged compare-and-swap will fail and force a retry that a plain compare-and-swap would have skipped. That is a correctness-for-throughput trade you accept, not a defect.

Design alternative worth naming

Often the best fix is to remove recurrence from the design instead of stamping it away: hand out slot indices that never recycle, use monotonic sequence numbers as the compare-and-swap subject (the basis of ring-buffer designs), or restrict the structure so that only one thread ever removes nodes. Tagging is the general fallback when the value genuinely must repeat.

## The idea The ABA problem exists because a compared value can recur. A version tag makes recurrence impossible by widening the compared value with a counter that only goes up. The shared cell holds a pair — `(pointer, version)` — and every successful update writes `(newPointer, version + 1)` in a single atomic operation. Now the compare-and-swap's value equality test coincides with the property the algorithm actually needs: *nothing has been installed here since I looked*. ``` cell = (A, 7) T1: reads (A, 7), computes newHead = B T2: pops A -> (B, 8) ; pops B -> (C, 9) ; pushes A -> (A, 10) T1: CAS(cell, expected=(A,7), new=(B,8)) -> FAILS, cell is (A,10) T1: retries from a fresh read ``` The algorithm is unchanged apart from carrying the stamp; the retry loop it already had absorbs the failure. ## How the pair is made atomic Three common mechanisms, all doing the same job: 1. **Double-width compare-and-swap.** Many architectures offer a compare-and-swap over two adjacent machine words, so a 64-bit pointer plus a 64-bit counter is one atomic unit. This is the cleanest form and gives a counter so wide that wraparound is not a practical concern. 2. **Bit stealing.** Objects aligned to 8 or 16 bytes leave the low pointer bits always zero, and on many 64-bit systems the top bits of a virtual address are unused. Packing a small counter into those bits keeps everything in one ordinary word, at the cost of a very small counter (often 8–16 bits) and portability assumptions about address layout. 3. **Immutable pair object.** Allocate a small record holding the pointer and stamp, and compare-and-swap the reference to that record. Conceptually simplest and portable, but every update allocates — and the record itself now has a lifetime question, which garbage-collected runtimes answer for free and manual-memory languages do not. ## What tagging does and does not buy **Buys:** detection of intervening modification. A stamped compare-and-swap succeeding is a genuine proof that no update landed on that cell since the read, which restores the reasoning the optimistic algorithm depends on. **Does not buy:** safe memory reclamation. Consider the stack pop again. The thread reads `head = A`, then dereferences `A.next`. If A was popped and freed in the meantime, that dereference is a use-after-free — it may crash, or read arbitrary reused bytes — and it happens *before* the compare-and-swap ever runs. Tagging makes the compare-and-swap fail afterwards, which is too late; the illegal read already occurred. In a garbage-collected runtime the node is kept alive by the thread's own reference, so the dereference is merely stale rather than illegal, and tagging alone is sufficient. In manual-memory code you also need a scheme that defers freeing until no thread can still be looking: hazard pointers, epoch-based reclamation, or read-copy-update. **Costs:** wraparound is the theoretical hole — a thread stalled for 2^k updates with a k-bit counter can be fooled again, so small stolen-bit counters are a real risk under heavy update rates while 64-bit counters are not. Double-width compare-and-swap is also somewhat more expensive than a single-word one and is not universally available; on load-linked/store-conditional machines it is often unnecessary, because store-conditional fails on *any* intervening write to the reservation, giving ABA immunity for free at that granularity. **Another cost is spurious retries.** The tag turns benign coincidences into failures. If the pointer legitimately returns to A and installing B is still the correct action, a tagged compare-and-swap will fail and force a retry that a plain compare-and-swap would have skipped. That is a correctness-for-throughput trade you accept, not a defect. ## Design alternative worth naming Often the best fix is to remove recurrence from the design instead of stamping it away: hand out slot indices that never recycle, use monotonic sequence numbers as the compare-and-swap subject (the basis of ring-buffer designs), or restrict the structure so that only one thread ever removes nodes. Tagging is the general fallback when the value genuinely must repeat.

If a version tag stops ABA, why do lock-free structures in C++ still need hazard pointers or epochs?
Because the tag only makes the compare-and-swap fail; it cannot un-do the dereference the thread already performed on a node that may have been freed in the meantime. Reading a removed node's fields is undefined behaviour regardless of what the later compare-and-swap decides. Reclamation schemes delay the free until no thread can still hold a reference, which is a separate guarantee from change detection.
How large does the version counter need to be?
Large enough that wrapping around during a single thread's stall is unreachable. A 64-bit counter at a billion updates per second takes centuries to wrap, so it is effectively safe; an 8- or 16-bit counter stolen from pointer bits can wrap in milliseconds under heavy contention and reintroduces ABA. If you must use few bits, bound how long a thread can hold a stale read, or pick a different technique.

saying these in an interview costs you the question

Claiming a version tag makes it safe to free nodes immediately
Updating the pointer and the counter with two separate atomic operations
Ignoring counter wraparound with only a few stolen bits
Thinking the tag must be globally unique rather than per-cell monotonic
Saying tagging removes the retry loop — it makes retries more frequent, not fewer

How does attaching a version counter to a shared pointer — a stamped or tagged reference updated by a single wide compare-and-swap — prevent the ABA problem, and what are the limits of that technique?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~3 min

The idea

How the pair is made atomic

What tagging does and does not buy

Design alternative worth naming

▾common follow-ups2 questions

▾red flags5 flags

§ context

▾related questions6 questions

▾related topics4 topics

The idea

How the pair is made atomic

What tagging does and does not buy

Design alternative worth naming

answer

go deeper

context