What is the ABA problem in lock-free data structures, why does it break a naive CAS free list or queue, and how do hazard pointers or epochs solve it?

A strong answer

compare_exchange_weak(expected, desired) checks only whether the target atomic variable still holds the bit pattern expected (A), not whether the object at address A was destroyed and recycled in between.

Suppose Thread 1 wants to pop from a lock-free stack or queue where head points to node A, and A->next is B:

1. Thread 1 reads head (A) and next (B), then gets preempted right before executing head.compare_exchange_weak(A, B).
2. While Thread 1 is paused, Thread 2 pops A, pops B, frees both, and pushes a brand-new node that the allocator happens to place at the exact same memory address A, now with A->next = C (while B is freed or reallocated elsewhere!).
3. Thread 1 wakes up and runs head.compare_exchange_weak(A, B). Because head once again equals the address A, the CAS succeeds and sets head = B—pointing the structure at a freed, dangling node B!

Even before the CAS runs, if Thread 2 frees and unmaps A before Thread 1 reads A->next, Thread 1 suffers an immediate use-after-free segfault. Two standard reclamation schemes prevent a node from being freed or recycled while any thread still holds a local reference to it:

• Hazard pointers: Each reader publishes the node pointer it is currently inspecting into a thread-local hazard slot before validating that head hasn't changed; a retiring thread scans active hazard slots before freeing a node.
• Epoch-based reclamation (EBR): Threads enter a critical epoch before accessing the structure and exit afterward; retired nodes are placed in the current epoch's limbo bag and freed only once all active threads have advanced past that epoch.

What the interviewer is listening for

• Traces a concrete 3-step ABA interleaving (A -> B becomes A -> C while B is freed, yet CAS on A succeeds and installs dangling B).
• Distinguishes the two problems: ABA pointer recycling (which version tags can detect if memory stays mapped in a fixed pool) and use-after-free on A->next dereference (which requires safe memory reclamation).
• Contrasts hazard pointers (bounded memory, per-read memory barrier overhead) with epoch-based reclamation (very fast reads, but a single stalled thread delays reclamation for an entire epoch).

Common mistakes

• Calling delete node; immediately after popping a node in a lock-free queue, which races with concurrent threads reading node->next.
• Assuming std::shared_ptr<Node> is automatically lock-free and wait-free (standard shared_ptr control block operations are atomic, but swapping a shared shared_ptr head without std::atomic<std::shared_ptr<T>> is a data race, and many atomic<shared_ptr> implementations use internal spinlocks).