# Lock-free programming and ABA

> Lock-free code replaces mutual exclusion with compare-and-swap retry loops, which buys a progress guarantee and costs you memory reclamation. This page builds the Treiber stack, shows how the ABA problem and use-after-free break it, and surveys tagged pointers, hazard pointers, RCU and atomic shared_ptr as fixes.

- **Source:** C++ Atlas (https://cppatlas.com/topics/lock-free-programming-and-aba)
- **Track:** Concurrency
- **Estimated reading time:** 15 minutes
- **ISO C++ clauses:** [intro.progress] (https://eel.is/c++draft/intro.progress), [intro.races] (https://eel.is/c++draft/intro.races), [atomics.lockfree] (https://eel.is/c++draft/atomics.lockfree), [atomics.order] (https://eel.is/c++draft/atomics.order), [atomics.types.operations] (https://eel.is/c++draft/atomics.types.operations), [atomics.flag] (https://eel.is/c++draft/atomics.flag), [util.smartptr.atomic] (https://eel.is/c++draft/util.smartptr.atomic)
- **cppreference links:** [std::atomic<T>::compare_exchange_weak, compare_exchange_strong](https://en.cppreference.com/w/cpp/atomic/atomic/compare_exchange), [std::atomic<T>::is_always_lock_free](https://en.cppreference.com/w/cpp/atomic/atomic/is_always_lock_free), [std::atomic<T>::is_lock_free](https://en.cppreference.com/w/cpp/atomic/atomic/is_lock_free), [std::atomic_flag](https://en.cppreference.com/w/cpp/atomic/atomic_flag), [std::atomic<std::shared_ptr>](https://en.cppreference.com/w/cpp/memory/shared_ptr/atomic2), [std::memory_order](https://en.cppreference.com/w/cpp/atomic/memory_order), [std::hardware_destructive_interference_size](https://en.cppreference.com/w/cpp/thread/hardware_destructive_interference_size)
- **Prerequisites:** atomics-and-memory-ordering, mutexes-and-locks, smart-pointers

## The one idea

A lock-free data structure never makes one thread wait for another to leave a critical section. Instead, every thread reads the shared state, computes the new state privately, and tries to install it with a single compare-and-swap. If another thread got there first, the swap fails and the thread starts over. That one change gives a real progress guarantee, because a preempted thread can no longer stall everyone else. It also creates the hardest problem in the field: a thread that read a pointer can be stopped for an arbitrary time, and by the time it uses the pointer, the node may have been freed, reused, and put back.

> **Mental model.** A CAS loop is optimistic concurrency on one word. It proves only that the word holds the same bits it held when you read it, not that nothing happened in between. Everything else in lock-free programming, including ABA defences and memory reclamation schemes, exists to close that gap.

This page builds on atomics-and-memory-ordering, which covers `compare_exchange_weak` versus `compare_exchange_strong` and what each memory order means.

## Progress guarantees

Four levels of progress are usually distinguished:

- **Blocking**: a thread can be prevented from making progress indefinitely by another thread that is not running, for example one holding a mutex while preempted.
- **Obstruction-free**: a thread that runs in isolation, with all others paused, finishes in a bounded number of steps. Contention can cause livelock.
- **Lock-free**: whenever threads are running the operation, at least one of them finishes in a bounded number of steps. Individual threads can starve, but the system as a whole progresses.
- **Wait-free**: every thread finishes in a bounded number of its own steps, regardless of the others.

A Treiber stack's push is lock-free but not wait-free: a CAS only fails because some other thread's CAS succeeded, so someone always progresses, but an unlucky thread can lose every race. A `fetch_add` on hardware with an atomic add instruction, such as Arm's LSE `ldadd` or x86's `lock xadd`, is wait-free.

> **Standardese.** [intro.progress] calls executions of lock-free atomic functions lock-free executions, but it only *requires* the obstruction-free property: if only one thread is not blocked in a library function, its lock-free execution shall complete. That at least one of several concurrent lock-free executions completes is a *should*, because load-linked and store-conditional hardware can, in principle, make threads keep invalidating each other.

Whether a given `std::atomic<T>` is lock-free is up to the implementation. `is_always_lock_free` answers at compile time, `is_lock_free()` at run time, and only `std::atomic_flag` is guaranteed lock-free; C++20 added the aliases `std::atomic_signed_lock_free` and `std::atomic_unsigned_lock_free` for integer types that are. Results vary even on one machine. For a 16-byte struct on this page's arm64 test machine, Clang 21 reported `std::atomic` as always lock-free, while GCC 16 reported it as not lock-free and routed it through libatomic.

## CAS loops and the Treiber stack

The Treiber stack is a singly linked list whose head is an atomic pointer. Push links a new node in front of the current head and tries to swing the head to it. Pop reads the head and tries to swing it to the head's successor.

```cpp
#include <atomic>
#include <optional>
#include <utility>

template <class T>
class TreiberStack {
  struct Node { T value; Node* next; };
  std::atomic<Node*> head_{nullptr};

public:
  void push(T v) {
    Node* n = new Node{std::move(v), head_.load(std::memory_order_relaxed)};
    // On failure, n->next is overwritten with the current head and we retry.
    while (!head_.compare_exchange_weak(n->next, n,
                                        std::memory_order_release,
                                        std::memory_order_relaxed)) {
    }
  }

  std::optional<T> pop() {            // broken under concurrency: see below
    Node* old = head_.load(std::memory_order_acquire);
    while (old && !head_.compare_exchange_weak(old, old->next,
                                               std::memory_order_acquire,
                                               std::memory_order_acquire)) {
    }
    if (!old) return std::nullopt;
    T v = std::move(old->value);
    delete old;                       // another popper may still be reading old->next
    return v;
  }
};
```

Push is correct as written. The node is private until the CAS publishes it, so the plain writes to `value` and `next` cannot race, and passing `n->next` as the expected value means a failed CAS refreshes it for free. Using `compare_exchange_weak` is right because the loop recomputes everything anyway, so a spurious failure costs one more iteration.

Pop is not correct, and the bug is not subtle once you look at the line that reads `old->next`. Between loading `old` and reading its `next` field, another thread can pop the same node and delete it. The first thread then reads freed memory, which is undefined behavior whether or not its CAS would later fail.

## The ABA problem

Even if nodes are never freed but are recycled through a free list, pop can corrupt the stack. The CAS compares only the pointer value, and a pointer value can come back.

```text
head -> A -> B -> C

T1: old = A, next = B          (then T1 is preempted)
T2: pop A, pop B, push A       (A is reused; B is gone)
    head -> A -> C
T1: CAS(head, A -> B) succeeds, because head is A again
    head -> B                  (B is not in the stack any more; C is lost)
```

This is the ABA problem: the value went from A to B and back to A, and a single-word CAS cannot tell. With node recycling there is also a data race, because T2's push writes `A->next` while T1 reads it, so the program has undefined behavior before the CAS even runs, unless `next` is itself atomic.

> **Pitfall.** ABA and unsafe reclamation are two different problems that happen to share a cause. A version tag stops the wrong CAS from succeeding, but it does nothing about T1 dereferencing a node that has already been returned to the allocator. Most real fixes solve reclamation, and ABA disappears with it because a node cannot be reused while anyone can still see it.

## Safe memory reclamation

**Tagged pointers.** Pair the pointer with a counter in one atomic word and increment the counter on every successful update. The CAS now fails if anything happened in between, even if the pointer came back. On 64-bit targets this needs a double-width CAS, such as `cmpxchg16b` on x86-64 or `casp` on Armv8.1, or spare pointer bits; whether `std::atomic` of a 16-byte struct is lock-free is implementation-specific. Tags only solve ABA, so the nodes must live in memory that is never returned to the operating system.

```cpp
#include <atomic>
#include <cstdint>

struct Node { int value; Node* next; };
struct Tagged { Node* ptr; std::uintptr_t tag; };   // 16 bytes on a 64-bit target

std::atomic<Tagged> head{Tagged{nullptr, 0}};

Node* pop() {
  Tagged old = head.load(std::memory_order_acquire);
  while (old.ptr) {
    Tagged desired{old.ptr->next, old.tag + 1};      // every successful pop bumps the tag
    if (head.compare_exchange_weak(old, desired, std::memory_order_acquire,
                                   std::memory_order_acquire))
      return old.ptr;                                // caller must not free it to the OS
  }
  return nullptr;
}
```

**Hazard pointers.** Before dereferencing a shared pointer, a thread publishes it in a per-thread slot that every other thread can read, then re-reads the source to confirm it has not changed. A thread that unlinks a node does not delete it; it retires it, and retired nodes are freed only once no hazard slot holds their address. The publish and the re-check need sequentially consistent ordering, or an equivalent fence, so that the retiring thread is guaranteed to see the hazard.

**RCU and epochs.** Readers announce only that they are inside a read-side critical section, which can be almost free. A writer unlinks the old version and waits for a grace period, after which every reader that could have seen it has left, and then frees it. Epoch-based reclamation is the same idea with explicit global epoch counters. Reads become very cheap; the cost is that one stalled reader delays all reclamation.

C++26 standardizes both of the last two in `<hazard_pointer>` and `<rcu>`, covered in hazard-pointers-and-rcu.

**`std::atomic<std::shared_ptr<T>>`.** Since C++20 the reference count itself solves reclamation: a popper holding a `shared_ptr` copy of the head keeps that node alive, so it cannot be freed or reused underneath it, and ABA cannot occur.

```cpp
#include <atomic>
#include <memory>
#include <optional>

template <class T>
class SharedStack {
  struct Node { T value; std::shared_ptr<Node> next; };
  std::atomic<std::shared_ptr<Node>> head_;

public:
  void push(T v) {
    auto n = std::make_shared<Node>(std::move(v), head_.load());
    while (!head_.compare_exchange_weak(n->next, n)) {}
  }
  std::optional<T> pop() {
    std::shared_ptr<Node> old = head_.load();       // our reference keeps *old alive
    while (old && !head_.compare_exchange_weak(old, old->next)) {}
    if (!old) return std::nullopt;
    return std::move(old->value);
  }
};
```

It is simple and correct, but not necessarily lock-free: libstdc++ in GCC 16 reports `is_lock_free()` as false, and Clang 21's libc++ does not yet provide the specialization at all. Destroying a long chain of such nodes is also recursive and can overflow the stack.

## Memory orders in a CAS loop

A CAS takes two orders: one for success, when it is a read-modify-write, and one for failure, when it is only a load. Pick each by asking what the thread does next with what it read.

In push, success must be `release`, so that a popper's acquire sees the node's contents; failure can be `relaxed`, because the reloaded head is only stored into the private node. In pop, success needs `acquire` to read the value that push published. Failure also needs `acquire`, because the loop immediately dereferences the reloaded pointer to read `next`. Writing `relaxed` there is a classic bug that works on x86 and fails on Arm.

The failure order may not be `release` or `acq_rel`, since a failed CAS writes nothing; violating that precondition is undefined behavior. Until C++17 it also could not be stronger than the success order. P0418 removed that restriction, so success `relaxed` with failure `acquire` is valid today. If you pass only one order, the failure order is derived from it: `acq_rel` becomes `acquire`, `release` becomes `relaxed`, and the others stay as they are.

> **Pitfall.** GCC 16 still warns with `-Winvalid-memory-model` that a failure order "cannot be stronger than success". The warning reflects the pre-C++17 rule. The program is valid; the warning is a reason to check your orders, not proof of a bug.

## Contention, false sharing and linearizability

Lock-free is a progress property, not a speed property. Under heavy contention every thread hammers the same cache line, each failed CAS still has to take the line exclusively, and throughput can collapse below that of a mutex, which lets one thread run a batch of operations while the others sleep. Node-based structures also allocate on every push, and the reclamation scheme adds work to every access: a hazard pointer costs a sequentially consistent store per dereference. A sharded design, a per-thread buffer, or a plain `std::mutex` around a `std::vector` often wins.

False sharing makes it worse. Two atomics that are logically independent but share a cache line, such as a queue's head and tail indices, interfere as if they were one variable. This is a performance problem, not a correctness one: separate objects are separate memory locations and never race. Pad hot atomics apart with `alignas(std::hardware_destructive_interference_size)`, as described in atomics-and-memory-ordering.

The correctness criterion for a concurrent object is usually **linearizability**: every operation appears to take effect at a single instant between its call and its return, so the history is equivalent to some sequential history that respects real-time order. For the Treiber stack, the linearization point of a successful push or pop is its successful CAS, and of a pop that finds the stack empty, the load that read null. The C++ standard does not define linearizability. It gives you happens-before and the single total order of `seq_cst` operations, and a linearizability argument is built on top of those.

## What to remember

- Lock-free means some thread always progresses; wait-free means every thread does. CAS retry loops are lock-free, not wait-free.
- The standard requires only obstruction-freedom from lock-free atomics and merely encourages more; only `atomic_flag` is guaranteed lock-free.
- In a Treiber pop, reading `old->next` after another thread freed `old` is undefined behavior before ABA even arises.
- ABA is a CAS succeeding because a value came back; version tags fix ABA but not reclamation.
- Hazard pointers, RCU and epochs fix reclamation by delaying frees until no reader can hold the pointer; C++26 standardizes the first two.
- `atomic<shared_ptr>` avoids ABA through reference counting but is not lock-free in libstdc++.
- Choose the failure order by what you do with the reloaded value; it may not be `release` or `acq_rel`, and since C++17 it may be stronger than the success order.
- Lock-free structures can be slower than a mutex under contention; pad independent hot atomics to avoid false sharing.

## Concept Map Outline

- **Lock-free programming:** Replace locks with CAS retry loops; pay for it with ABA and memory reclamation.
  - **Progress guarantees:** Blocking, obstruction-free, lock-free and wait-free, from weakest to strongest.
    - **Lock-free:** Some thread always finishes; an individual thread may starve.
    - **Wait-free:** Every thread finishes in a bounded number of its own steps.
    - **What the standard requires:** [intro.progress] requires obstruction-freedom and only encourages lock-freedom.
    - **atomic_flag:** The only type guaranteed lock-free; ask is_always_lock_free for others.
  - **Treiber stack:** A linked list with an atomic head, updated by CAS loops.
    - **Push:** Link the private node to the head, CAS the head to it; a failed CAS refreshes next.
    - **Pop:** CAS the head to head->next; reading next of a freed node is UB.
    - **compare_exchange_weak:** Right inside a retry loop, since spurious failure costs one iteration.
  - **ABA problem:** A CAS succeeds because the pointer value came back, though the structure changed.
    - **Recycled node:** Pop A, pop B, push A again: a stale CAS installs the removed B.
    - **Tagged pointers:** A counter beside the pointer, updated by double-width CAS, defeats ABA.
    - **Not reclamation:** Tags stop the wrong CAS but not a dereference of freed memory.
  - **Safe reclamation:** Delay freeing a node until no thread can still hold a pointer to it.
    - **Hazard pointers:** Publish the pointer before use; retired nodes are freed when no slot holds them.
    - **RCU and epochs:** Cheap readers; writers wait for a grace period before freeing.
    - **atomic<shared_ptr>:** C++20; reference counts prevent reuse, but libstdc++'s is not lock-free.
    - **C++26 support:** <hazard_pointer> and <rcu> standardize the first two schemes.
  - **Memory orders in CAS:** Choose success and failure orders by what the thread does with the value.
    - **Push orders:** Success release to publish the node; failure relaxed.
    - **Pop orders:** Acquire on success and failure, because the reloaded pointer is dereferenced.
    - **Failure restrictions:** Never release or acq_rel; since C++17 it may be stronger than success.
  - **Performance:** Lock-free is a progress property, not a speed guarantee.
    - **Contention:** Every failed CAS still takes the cache line; a mutex can win.
    - **False sharing:** Independent atomics on one cache line slow each other but never race.
    - **Linearizability:** Each operation appears atomic at one point; for Treiber, the successful CAS.

## Standardese Quiz Questions

### Question 1 [warmup] ([atomics.types.operations])

What is the behavior of calling `try_set`?

```cpp
#include <atomic>

std::atomic<int> a{0};

bool try_set(int expected) {
  return a.compare_exchange_strong(expected, 1,
                                   std::memory_order_acq_rel,
                                   std::memory_order_release);
}
```

A. Well-defined: the failure order is silently strengthened to `acquire`
B. Ill-formed: the compiler must reject the failure order
C. Undefined behavior: the failure order may not be `release` or `acq_rel`
D. Well-defined: a failed CAS performs a release store of the old value

**Answer (C):** Undefined behavior: the failure order may not be `release` or `acq_rel`

**Why:** A failed compare-exchange is just a load, so a release failure order makes no sense, and the standard makes `failure` being `release` or `acq_rel` a precondition violation, which is undefined behavior. It is not ill-formed: the orders are ordinary function arguments, and GCC only warns with `-Winvalid-memory-model`. Some implementations happen to strengthen the order, but nothing guarantees it.

### Question 2 [warmup] ([atomics.flag], [atomics.lockfree])

Which of these types does the standard guarantee to be lock-free on every implementation?

A. `std::atomic<bool>`
B. `std::atomic_flag`
C. `std::atomic<int>`
D. `std::atomic<void*>`

**Answer (B):** `std::atomic_flag`

**Why:** `std::atomic_flag` is the only one of these guaranteed lock-free; it is the primitive from which an implementation can build locks for everything else. `std::atomic<int>`, `std::atomic<bool>` and `std::atomic<void*>` are lock-free on every mainstream platform, but the standard leaves it to the implementation, which is why `is_always_lock_free` and the `ATOMIC_..._LOCK_FREE` macros exist. C++20's `atomic_signed_lock_free` aliases are the other guaranteed option.

### Question 3 [warmup] ([atomics.types.operations])

Nodes are recycled through a free list instead of deleted, and `next` is atomic so that reusing a node is not a data race. Thread T1 runs `pop` on the stack `A -> B -> C`, reads `old = A` and `old->next == B`, and is preempted before its CAS. Thread T2 pops A, pops B, then pushes the recycled A, so the stack is `A -> C`. What happens when T1 resumes and its CAS runs?

```cpp
#include <atomic>

struct Node { int value; std::atomic<Node*> next; };
std::atomic<Node*> head;

Node* pop() {                              // assumes the stack is not empty
  Node* old = head.load(std::memory_order_acquire);
  Node* next = old->next.load();           // T1 is preempted here
  head.compare_exchange_strong(old, next);
  return old;
}
```

A. The CAS fails because the stack changed, and T1 retries
B. The CAS succeeds and makes the removed node B the head, losing C
C. The CAS succeeds and correctly leaves `C` as the head
D. The CAS blocks until T2's operations are complete

**Answer (B):** The CAS succeeds and makes the removed node B the head, losing C

**Why:** A compare-and-swap compares only the bits of the head pointer, and the head holds A again, so T1's CAS succeeds and installs its stale `next`, B, as the new head. B was popped and C is no longer reachable. This is the ABA problem: the value went from A to something else and back to A, and the CAS cannot tell. A version tag or a reclamation scheme that prevents reuse is needed to fix it.

### Question 4 [tricky] ([intro.memory], [intro.races])

Two threads run at the same time, one calling `left()` and the other `right()`, with no synchronization. What does the standard say?

```cpp
struct Counters {
  int a = 0;
  int b = 0;    // almost certainly on the same cache line as a
};

Counters c;

void left()  { for (int i = 0; i < 1000000; ++i) ++c.a; }
void right() { for (int i = 0; i < 1000000; ++i) ++c.b; }
```

A. It is a data race, so the behavior is undefined
B. It is not a data race, but each counter may lose increments to the other thread
C. It is not a data race; sharing a cache line can only affect performance
D. It is implementation-defined, depending on the cache line size

**Answer (C):** It is not a data race; sharing a cache line can only affect performance

**Why:** `a` and `b` are separate memory locations, so the two threads never access the same location and there is no data race. Each thread's counter ends at exactly one million. Sharing a cache line causes false sharing, which can make both loops much slower, but the memory model is defined in terms of memory locations, not cache lines. Adjacent bit-fields would be different, because they share one memory location.

### Question 5 [tricky] ([atomics.types.operations])

In C++17 and later, is this call well-defined?

```cpp
#include <atomic>

std::atomic<int> state{0};

bool claim(int expected) {
  return state.compare_exchange_strong(expected, 1,
                                       std::memory_order_relaxed,
                                       std::memory_order_acquire);
}
```

A. Yes: since C++17 the failure order may be stronger than the success order
B. No: the failure order may never be stronger than the success order
C. No: `relaxed` is not allowed as a success order for compare-exchange
D. It is well-defined only for `compare_exchange_weak`

**Answer (A):** Yes: since C++17 the failure order may be stronger than the success order

**Why:** Before C++17, the failure order could not be stronger than the success order. P0418, adopted for C++17, removed that rule, so the only remaining restriction is that failure is not `release` or `acq_rel`. GCC 16 still emits a `-Winvalid-memory-model` warning that reflects the old rule, which makes the second option tempting, but the call is valid.

### Question 6 [tricky] ([intro.progress])

Assuming `std::atomic<Node*>` is lock-free and only `push` and `pop` operations that each succeed with one CAS touch `head`, which progress guarantee does this `push` provide?

```cpp
#include <atomic>

struct Node { int value; Node* next; };
std::atomic<Node*> head{nullptr};

void push(Node* n) {
  n->next = head.load(std::memory_order_relaxed);
  while (!head.compare_exchange_strong(n->next, n,
                                       std::memory_order_release,
                                       std::memory_order_relaxed)) {
  }
}
```

A. Wait-free: every call finishes in a bounded number of steps
B. Blocking: a preempted thread can stop all others
C. Lock-free but not wait-free: some thread always finishes, but one thread can keep losing
D. Not even obstruction-free

**Answer (C):** Lock-free but not wait-free: some thread always finishes, but one thread can keep losing

**Why:** A strong CAS fails only because another thread changed `head`, which means another push or pop succeeded, so the system as a whole always makes progress. Nothing bounds how often one particular thread loses, so a thread can starve, which rules out wait-free. No thread ever waits for another to release anything, so it is not blocking. Whether the hardware CAS itself always lets someone win is the implementation's lock-free promise, which the standard only encourages.

### Question 7 [standardese] ([intro.progress])

What does [intro.progress] *require* of executions of lock-free atomic operations?

A. Every lock-free execution completes in a bounded number of steps
B. If only one thread is not blocked in a standard library function, its lock-free execution completes; that one of several concurrent executions completes is only encouraged
C. At least one of several concurrent lock-free executions must complete
D. Nothing: lock-freedom is a non-normative note

**Answer (B):** If only one thread is not blocked in a standard library function, its lock-free execution completes; that one of several concurrent executions completes is only encouraged

**Why:** The normative requirement is the obstruction-free property: a lock-free execution in the only thread that is not blocked shall complete. The stronger property that at least one of several concurrent lock-free executions completes is stated with *should*, because load-linked and store-conditional hardware can let threads repeatedly invalidate each other. The first option is wait-freedom, which the standard never promises.

### Question 8 [standardese] ([atomics.types.operations])

`ok` is `false` after this call. What does the standard guarantee about `e`?

```cpp
#include <atomic>

std::atomic<int> a{5};

void f() {
  int e = 5;
  bool ok = a.compare_exchange_weak(e, 6);
  (void)ok;
}
```

A. `e` is unchanged, because a failed CAS writes nothing
B. `e` holds the value read from `a`, which may still be 5 if the failure was spurious
C. `e` holds a value different from 5
D. `e` is indeterminate

**Answer (B):** `e` holds the value read from `a`, which may still be 5 if the failure was spurious

**Why:** On failure, compare-exchange atomically loads the current value into `expected`. `compare_exchange_weak` may also fail spuriously even when the values were equal, so `e` can still be 5. Only `compare_exchange_strong` guarantees that a failure means the values really differed, which is what the third option assumes. That is why `weak` belongs inside a retry loop.
