Recipe

The ABA problem

The ABA problem is one of the oldest hazards in lock-free programming. A thread reads a value A, sleeps, and wakes to see A again — but in between, the value briefly became Band then was reset. A naive compare-and-swap fires successfully even though the underlying state has shifted, corrupting the data structure.

1What goes wrong

Consider a treiber stack. Thread T1 reads the head pointer (call it A), is preempted, then T2 pops A, pops the next node, and pushes A back. When T1 resumes, its CAS on head succeeds, but the second node it expected has been freed. The stack now points into freed memory.

2The classic CAS trap

The pseudocode below shows the buggy pop. The CAS sees the same pointer value and assumes nothing changed.

Node* pop() {
  Node* old_head;
  do {
    old_head = head.load();
    if (!old_head) return nullptr;
    Node* next = old_head->next;   // UNSAFE: old_head may be freed
  } while (!head.compare_exchange_weak(
      old_head, next));            // ABA: old_head value reused
  return old_head;
}

3Standard mitigations

•Tagged pointers. Pack a monotonic version counter into the high bits and CAS the composite word so a recycled address still fails.
•Hazard pointers. Each thread publishes pointers it is reading; reclamation waits until no hazard reference remains.
•Epoch-based reclamation. Defer free until every thread has advanced past the epoch in which the node was unlinked.