The ABA problem is a correctness hazard in lock-free code that uses compare-and-swap (CAS). CAS reads a value, does some work, then atomically updates the location only if it still holds the value you read — otherwise retrying. The assumption baked in is that a matching value means nothing changed. This is wrong: another thread can change the location from A to B and back to A between your read and your CAS, and CAS cannot tell the difference.

In C11, CAS is atomic_compare_exchange_strong. The operation looks safe:

_Atomic struct node *head;
struct node *old_head = atomic_load(&head);
atomic_compare_exchange_strong(&head, &old_head, old_head->next);
// succeeds if head == old_head — but what if head was changed and restored?

The problem surfaces concretely in a lock-free stack. Thread 1 reads head = A and is about to CAS head from A to A->next:

initial:   head -> A -> B -> C
thread 1 reads head=A, prepares to CAS head to A->next (=B)
  [preempted]
thread 2 pops A  ->  head -> B -> C
thread 2 pops B  ->  head -> C
thread 2 pushes A back (possibly reusing A's allocation)  ->  head -> A -> C
  [thread 1 resumes]
thread 1: CAS(head, A, B) succeeds — head is still A
head is now B, which was already freed

Thread 1's CAS succeeds and sets head to a freed node. The stack is corrupted. No data race in the formal sense occurred; every individual access was atomic. The bug is that CAS has no way to detect the intervening pop-and-push cycle.

Pair the pointer with a monotonically increasing version counter and make CAS operate on both together. Even if the pointer returns to A, the tag is strictly greater than before, so the combined value will not match.

struct tagged_ptr {
    struct node *ptr;
    uintptr_t    tag;
};
 
_Atomic struct tagged_ptr head;
 
struct tagged_ptr old = atomic_load(&head);
struct tagged_ptr new = { old.ptr->next, old.tag + 1 };
atomic_compare_exchange_strong(&head, &old, new);

This requires a double-width CAS (CMPXCHG16B on x86-64 for a 128-bit compare-and-swap). An alternative on 64-bit systems is to store the tag in the unused high bits of a pointer, which is valid on architectures with a 48-bit virtual address space.

Defer freeing until every thread has passed through a quiescent state. A node popped from the stack enters a pending-free list and stays there until all threads have acknowledged a new epoch. Because the node is never returned to the allocator while any thread could still hold a reference to it, the A-to-B-to-A cycle cannot form with the same pointer value.

Before dereferencing a pointer that will be used in a subsequent CAS, publish it in a per-thread hazard pointer slot. Memory reclamation scans all hazard pointers before freeing; any node still referenced by a live hazard pointer is deferred. The approach is used in production lock-free libraries (Java's java.util.concurrent, several C++ implementations) because it bounds the deferred-free backlog without requiring epoch coordination.