Failures and antipatterns · Intermediate

The ABA problem

Trace intervening state changes when a value returns to A, separating CAS comparison from reference lifetime and safe reclamation.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Equality does not prove an unchanged state
  2. A stack head that returns to A
  3. Comparison and object lifetime are separate
  4. Choose a remedy for the actual invariant
  5. Ask Logeia about this articleCheck your understanding

Equality does not prove an unchanged state

The ABA problem occurs when a value changes from A to another state and later becomes A again. A compare-and-swap operation can then succeed even though an assumption made by the algorithm has become false. The primitive has not malfunctioned: it compared the specified current value and performed its update atomically. The mistake is treating equality as evidence that no relevant transition occurred. This distinction matters when a data structure depends on membership, generation, or object lifetime rather than on a scalar value alone.

A stack head that returns to A

Consider a linked stack A → B → C. Thread T1 reads the head A and saves B as its successor, then pauses. Thread T2 removes both A and B and pushes A back, leaving A → C. A later CAS by T1 from A to its saved B may succeed because the current head is again A. However, B is no longer a member of the stack. Installing it violates the structural invariant. This is an illustrative schedule, not executable code with a complete memory-reclamation protocol.

Comparison and object lifetime are separate

In C and C++, an allocator can also reuse the numerical address of a freed object. Reading that freed object is a lifetime error, while accepting a stale logical state is an ABA error; the two issues can interact without being identical. A review should ask both whether a pointer remains safe to dereference and whether the node may have been removed and reinserted. Automatic garbage collection can prevent some reclamation hazards, but does not in general prove that a logically reused reference represents an unchanged state.

Choose a remedy for the actual invariant

An atomic pair consisting of a reference and a generation can distinguish A at generation 7 from A at generation 9. Java offers AtomicStampedReference for a reference with an integer stamp. A design must still address stamp wraparound and ensure every relevant update changes the stamp consistently. Reclamation schemes such as hazard pointers need to be evaluated with the algorithm’s reuse rules; they are not interchangeable magic fixes. For a small structure, protecting the full invariant with an ordinary lock may be easier to verify and maintain.

Reading and practice are recorded separately in this browser, for each language.

Choose a learning path