Lock-free data structures: the Treiber stack

A mutex is the right default for shared data. But a lock has a failure mode no amount of care removes: if the thread holding it is descheduled, preempted by a higher-priority thread, or stuck in a page fault, everyone else waits. Lock-free structures replace "take the lock, change things, release" with "prepare a change, then publish it with one atomic compare-exchange — and retry if someone beat you". The classic first example is R. Kent Treiber's stack (1986). It fits in thirty lines, and it shows every hard problem in the field: retry loops, memory ordering, ABA, and above all memory reclamation.

1. Progress guarantees

"No mutex" is not the definition. The non-blocking guarantees are about who is promised progress:

A spin lock made of std::atomic<bool> uses no mutex and is still blocking: if the owner is preempted, the spinners spin. Lock-free means the system as a whole can't get stuck, whatever the scheduler does. It does not mean faster — under heavy contention a good mutex often wins.

2. The stack: one atomic pointer

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

Push builds the node privately, points it at the current head, and swings head_ to it — but only if head_ is still what it read:

void push(T value) {
    Node* n = new Node{std::move(value)};
    n->next = head_.load(std::memory_order_relaxed);
    while (!head_.compare_exchange_weak(n->next, n,
                                        std::memory_order_release,
                                        std::memory_order_relaxed)) {
    }
}

compare_exchange_weak(expected, desired) atomically does: if head_ == expected, set it to desired and return true; otherwise copy the current value into expected and return false. Passing n->next as expected means a failed attempt refreshes n->next with the new head — so the loop body is empty. weak may also fail spuriously (on LL/SC machines like AArch64), which the loop handles for free.

Why not just load then store? Two pushers both load head H, both point their node at H, and the second store overwrites the first: a node vanishes. Each operation was atomic; the read-modify-write wasn't.

Worked example

Eight threads push 1000 values each, then one thread drains the stack. Every value must come out exactly once:

#include <atomic>
#include <barrier>
#include <print>
#include <thread>
#include <utility>
#include <vector>

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

public:
    ~Stack() {
        for (Node* n = head_.load(); n;) {
            Node* next = n->next;
            delete n;
            n = next;
        }
    }

    void push(T value) {
        Node* n = new Node{std::move(value)};
        n->next = head_.load(std::memory_order_relaxed);
        while (!head_.compare_exchange_weak(n->next, n, std::memory_order_release,
                                            std::memory_order_relaxed)) {
        }
    }

    // Single-threaded drain only: freeing here is safe because nobody else runs.
    bool pop_unsynchronised(T& out) {
        Node* n = head_.load(std::memory_order_acquire);
        if (!n) return false;
        head_.store(n->next, std::memory_order_relaxed);
        out = std::move(n->value);
        delete n;
        return true;
    }
};

int main() {
    constexpr int threads = 8, per = 1000;
    Stack<int> s;
    {
        std::barrier start(threads);
        std::vector<std::jthread> ts;
        for (int t = 0; t < threads; ++t)
            ts.emplace_back([&, t] {
                start.arrive_and_wait();
                for (int i = 0; i < per; ++i) s.push(t * per + i);
            });
    }   // jthreads join here
    std::vector<int> seen(threads * per, 0);
    int v;
    while (s.pop_unsynchronised(v)) ++seen[static_cast<std::size_t>(v)];
    int ok = 0;
    for (int c : seen) ok += c == 1;
    std::println("{} of {} values seen exactly once", ok, threads * per);
}

The barrier starts all pushers at once so they really contend. Joining the threads before draining is what makes the single-threaded pop safe.

3. Pop, and ordering

Pop swings head_ from the top node to its successor:

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;
// we own old now

Check old before every old->next — on an empty stack it is nullptr.

The orderings pair up: push's successful CAS is release, pop's loads are acquire. When a popper reads a pointer that a pusher released, everything the pusher wrote before the CAS — the node's value and next — happens-before the popper's reads. With relaxed instead, those plain reads race with the pusher's writes: undefined behaviour, which ThreadSanitizer reports even on x86, where the hardware happens to keep stores in order.

4. The reclamation problem

Here is the trap. After winning the CAS, it is tempting to delete old:

Unlinking A from head_ does not stop threads that loaded A earlier from dereferencing it. Thread 1's read is a use-after-free. No memory ordering fixes this: thread 1's load was perfectly legal when it happened.

ABA

It gets worse if the allocator recycles A's address:

The compare-exchange compares addresses, and A → B → A looks like "nothing changed". That's the ABA problem. The aba-output exercise replays this interleaving step by step.

5. Ways out

Deferred reclamation is what you'll build: popped nodes go onto a second lock-free list, retired_, and the destructor frees them. Because addresses are never reused while the stack lives, it also rules out ABA. One subtlety: link retired nodes through a separate field. Other poppers may still be reading a popped node's next; writing it to build the retired list is a data race.

What about the tools the standard library offers?

#include <atomic>
#include <cstdint>
#include <memory>
#include <print>

struct Node;
struct Tagged {
    Node* ptr;
    std::uintptr_t tag;
};

int main() {
    std::println("atomic<Node*>:              {}", std::atomic<Node*>{}.is_lock_free());
    std::println("atomic<Tagged> (16 bytes):  {}", std::atomic<Tagged>{}.is_lock_free());
    std::println("atomic<shared_ptr<int>>:    {}", std::atomic<std::shared_ptr<int>>{}.is_lock_free());
}

On GCC 16 / x86-64 only the plain pointer is lock-free. x86-64 does have cmpxchg16b, but GCC sends 16-byte atomics through libatomic (there's no lock-free 16-byte load), so tagged-pointer stacks usually steal unused pointer bits instead. And std::atomic<std::shared_ptr> is implemented with a lock in libstdc++ — correct and convenient, but not a lock-free building block.

Faded example

Write retire(Node* n): push n onto retired_, linking through retired_next. It is the same pattern as push.

void retire(Node* n) {
    n->retired_next = /* ??? */;
    while (!retired_.compare_exchange_weak(/* ??? */, n,
                                           std::memory_order_release,
                                           std::memory_order_relaxed)) {
    }
}

6. Measuring contention

A CAS loop's cost is its retries. Count them:

#include <atomic>
#include <barrier>
#include <print>
#include <thread>
#include <vector>

int main() {
    for (int threads : {1, 4, 8}) {
        std::atomic<long> counter{0}, retries{0};
        std::barrier start(threads);
        {
            std::vector<std::jthread> ts;
            for (int t = 0; t < threads; ++t)
                ts.emplace_back([&] {
                    start.arrive_and_wait();
                    for (int i = 0; i < 2000; ++i) {
                        long cur = counter.load(std::memory_order_relaxed);
                        while (!counter.compare_exchange_weak(cur, cur + 1, std::memory_order_relaxed)) {
                            retries.fetch_add(1, std::memory_order_relaxed);
                        }
                    }
                });
        }
        std::println("{} thread(s): {} increments, {} failed CAS attempts", threads, counter.load(),
                     retries.load());
    }
}

The count is always right (lock-free!), but failed attempts climb with the thread count: every failure is wasted work and a cache line bouncing between cores. That's why lock-free structures keep the CAS window tiny, back off under contention, or avoid a single hot word altogether (per-thread or sharded structures).

Summary

• Lock-free = some thread always makes progress; not "no mutex", not "faster".
• Push and pop are compare-exchange loops on head_; a load-then-store loses updates.
• Publish with release, consume with acquire, or reading the node is a data race.
• A popped node can't be freed immediately: other threads may still read it (use-after-free), and recycled addresses cause ABA.
• Fix it with a reclamation scheme: deferred until destruction (simplest), hazard pointers, epochs, or tagged/counted pointers.
• std::atomic<16-byte struct> and std::atomic<std::shared_ptr> are not lock-free with libstdc++ — check is_lock_free().