Concurrent & Lock-Free Lists

July 2026 · 26 min read

Every routine so far assumed a single thread. Add a second and every one of them is broken: two push_fronts can read the same head, both build a node pointing at it, and one silently overwrites the other. This post climbs the ladder of solutions — from a mutex a first-year can write to a lock-free list that took researchers a decade to get right — and, just as importantly, tells you where to stop climbing, because the top rung is almost never where you want to stand.

Rung 1: One Big Lock

The correct baseline is a single mutex guarding the entire list. Every operation takes it, does its work, and releases it. It is trivially correct because operations never interleave — the lock serialises them into a sequential order — and you should reach for it first, always.

#include <mutex>

template <class T>
class CoarseList {
    struct Node { T val; Node* next; };
    Node* head_ = nullptr;
    std::mutex m_;
public:
    void push_front(const T& v) {
        std::lock_guard<std::mutex> lk(m_);
        head_ = new Node{ v, head_ };
    }
    bool contains(const T& v) {
        std::lock_guard<std::mutex> lk(m_);
        for (Node* p = head_; p; p = p->next)
            if (p->val == v) return true;
        return false;
    }
};

The flaw is not correctness but scalability: the lock serialises everything, so a hundred threads reading a million-node list take turns as if there were one. A long contains blocks every writer for its whole traversal. Everything below is an attempt to let non-conflicting operations proceed in parallel — and every attempt costs correctness reasoning you did not previously owe.

Rung 2: Hand-Over-Hand Locking

Instead of one lock for the list, give every node its own lock and walk them like climbing a rope: hold node i, grab node i+1, only then release i. This lock coupling lets two threads operate on different regions of the list at once, because a thread only ever holds two adjacent locks.

template <class T>
struct FNode { T val; FNode* next; std::mutex m; };

// Remove the first node equal to v from a sorted list, using lock coupling.
template <class T>
bool remove(FNode<T>* head, const T& v) {
    FNode<T>* pred = head;
    pred->m.lock();
    FNode<T>* curr = pred->next;
    if (curr) curr->m.lock();
    while (curr) {
        if (curr->val == v) {
            pred->next = curr->next;   // unlink while holding BOTH locks
            curr->m.unlock();
            pred->m.unlock();
            delete curr;              // reclamation glossed over for now
            return true;
        }
        pred->m.unlock();            // release the trailing lock ...
        pred = curr;                 // ... only after the next one is held
        curr = curr->next;
        if (curr) curr->m.lock();
    }
    pred->m.unlock();
    return false;
}

Two rules make this safe. First, every thread locks in the same direction — front to back — so a cycle of "A waits for B while B waits for A" can never form; a global lock order is the standard deadlock-avoidance discipline. Second, never release pred before curr is locked: if you let go of pred first, another thread can splice or delete a node into the gap you are standing over, and your pred->next = curr->next corrupts the list. The overlap is the invariant.

Rung 3: Optimistic and Lazy Synchronisation

The expensive part above was locking every node you merely walked past. Optimistic synchronisation bets that traversal is contention-free: walk the list with no locks at all, and only once you arrive lock the two nodes you intend to modify — then validate that they are still adjacent and reachable before committing. If validation fails (someone changed the neighbourhood while you walked), you retry. You have traded guaranteed-correct-but-slow locking for usually-right-and-cheap traversal plus a re-check.

The lazy list refines this with a marked bit that separates logical deletion from physical unlinking. To remove a node you first set its marked flag (it is now logically gone), then unlink it. Validation becomes a two-field check, and the payoff is enormous: contains needs no locks and no retries at all — it walks the list and reports whether it found an unmarked matching node. That makes membership queries wait-free, the strongest progress guarantee there is.

struct LNode {
    int              key;
    std::atomic<bool> marked{false};   // logically deleted?
    LNode*           next;
    std::mutex       m;
};

// Wait-free: no locks, no retries, just a scan.
bool contains(LNode* head, int key) {
    LNode* curr = head;
    while (curr && curr->key < key)
        curr = curr->next;
    return curr && curr->key == key &&
           !curr->marked.load(std::memory_order_acquire);
}

This is the design behind Java's ConcurrentSkipListMap and most production lock-based concurrent sets: lock only to mutate, never to read.

Rung 4: Lock-Free with Compare-and-Swap

A lock-free structure uses no locks at all; threads coordinate with a single hardware primitive, compare-and-swap (CAS). std::atomic<T>::compare_exchange_weak(expected, desired) atomically checks whether the atomic still equals expected and, if so, sets it to desired; otherwise it loads the current value back into expected and reports failure. The universal pattern is "read, prepare, CAS; if it failed someone beat me, so retry with the fresh value". Lock-free means some thread always makes progress, so a thread suspended mid-operation can never block the others — the fatal weakness of every lock above.

The simplest complete example is the Treiber stack: push and pop are single-CAS loops on the head pointer.

#include <atomic>

template <class T>
class TreiberStack {
    struct Node { T val; Node* next; };
    std::atomic<Node*> head_{nullptr};
public:
    void push(const T& v) {
        Node* n = new Node{ v, head_.load(std::memory_order_relaxed) };
        while (!head_.compare_exchange_weak(
                   n->next, n,                       // expected = n->next, desired = n
                   std::memory_order_release,
                   std::memory_order_relaxed)) {
            // CAS failed: n->next was refreshed with the live head; loop and retry.
        }
    }
    bool pop(T& out) {
        Node* old = head_.load(std::memory_order_acquire);
        while (old && !head_.compare_exchange_weak(
                          old, old->next,
                          std::memory_order_acquire,
                          std::memory_order_relaxed)) {
            // old is refreshed on failure; retry.
        }
        if (!old) return false;
        out = old->val;
        // delete old;   // NOT SAFE yet — another thread may still read it. See reclamation.
        return true;
    }
};

The Michael–Scott queue is the two-lock-free-pointer workhorse behind most concurrent queues. It keeps a head_ and a tail_, plus a dummy sentinel node so the two never alias on an empty queue. Its signature move is helping: because linking a new node and advancing tail_ are two separate CAS operations, a thread can be suspended between them, leaving tail_ lagging one node behind. Any thread that notices this fixes it — it swings the stale tail forward before doing its own work — so no thread's stall can wedge the queue.

template <class T>
class MSQueue {
    struct Node {
        T val;
        std::atomic<Node*> next;
        Node() : val(), next(nullptr) {}
        explicit Node(const T& v) : val(v), next(nullptr) {}
    };
    std::atomic<Node*> head_, tail_;
public:
    MSQueue() {
        Node* dummy = new Node();      // sentinel: head and tail start here
        head_.store(dummy);
        tail_.store(dummy);
    }
    void enqueue(const T& v) {
        Node* n = new Node(v);
        for (;;) {
            Node* last = tail_.load(std::memory_order_acquire);
            Node* next = last->next.load(std::memory_order_acquire);
            if (last != tail_.load(std::memory_order_acquire)) continue;  // tail moved; reread
            if (next == nullptr) {
                if (last->next.compare_exchange_weak(next, n,             // link n after last
                        std::memory_order_release, std::memory_order_relaxed)) {
                    tail_.compare_exchange_strong(last, n,                // try to swing tail
                        std::memory_order_release, std::memory_order_relaxed);
                    return;                                              // (ok if this CAS fails)
                }
            } else {
                tail_.compare_exchange_strong(last, next,                // HELP a lagging tail
                    std::memory_order_release, std::memory_order_relaxed);
            }
        }
    }
    bool dequeue(T& out) {
        for (;;) {
            Node* first = head_.load(std::memory_order_acquire);
            Node* last  = tail_.load(std::memory_order_acquire);
            Node* next  = first->next.load(std::memory_order_acquire);
            if (first != head_.load(std::memory_order_acquire)) continue;
            if (first == last) {
                if (next == nullptr) return false;                       // empty
                tail_.compare_exchange_strong(last, next,                // help before retry
                    std::memory_order_release, std::memory_order_relaxed);
            } else {
                out = next->val;                                         // read value first
                if (head_.compare_exchange_weak(first, next,             // then unlink
                        std::memory_order_release, std::memory_order_relaxed)) {
                    // delete first;  // still unsafe — see reclamation
                    return true;
                }
            }
        }
    }
};

The acquire/release ordering is not decoration. The release on a successful link publishes the fully-constructed node; the matching acquire on the load guarantees a thread that sees the new pointer also sees the node's initialised fields. Drop them to relaxed and another core can observe the pointer before the value it points to — a data race that shows up only under load, only on weakly-ordered hardware, and never in your tests.

Watch the Enqueue Race

Two threads enqueue onto the same Michael–Scott queue. Step through the CAS attempts — one succeeds, one fails and must retry — and watch the tail-helping step where the second thread advances a tail the first left lagging.

The ABA Problem

CAS checks whether a value is unchanged, but it can only see the value, not its history. Here is a concrete interleaving that breaks the Treiber stack. The stack is A → B → C.

The CAS saw head == A and concluded nothing had changed, but everything had: A was freed and its address recycled, and B is no longer in the stack. Head now points at reclaimed memory. This is ABA — a value read as A, changed to B, and changed back to A, fooling a CAS that only compares the final value.

Three families of fix exist. Tagged (versioned) pointers pack a monotonically increasing counter alongside the pointer — in the unused low bits of an aligned pointer, or in the high bits, or via a double-width CAS (cmpxchg16b) that swaps pointer-and-counter together. Because the counter always advances, the recycled A carries a different tag and the CAS correctly fails. Hazard pointers and epoch-based reclamation attack the root cause instead — they prevent the address from being reused while any thread still holds it — which is the subject of the next section.

The Hard Part: Safe Memory Reclamation

Every lock-free structure above left a comment where delete should go, because freeing is the genuinely hard problem. You unlinked a node, but you cannot prove no other thread is still reading it — a lock-free reader took no lock to announce itself. Free too early and you get use-after-free; never free and you leak. Three schemes resolve this.

The trade is always the same shape: cheaper reads buy longer reclamation latency and looser memory bounds. Hazard pointers give a hard cap on un-freed nodes at a per-read cost; RCU makes reads almost free but can pin memory for an entire grace period; epochs sit in between and are the usual default in modern C++ lock-free libraries.

Harris's Lock-Free Linked List

Deleting from a lock-free sorted list hides a subtle race. The naive removal is a single CAS: pred->next from curr to curr->next. But suppose that, at the same instant, another thread inserts a node after curr by CASing curr->next. Both CASes can succeed: pred now skips curr, but the freshly inserted node hangs off curr->next — off a node that is no longer in the list. The insertion is silently lost.

Harris's 2001 solution splits deletion into two atomic steps and steals a bit to coordinate them. Because nodes are aligned, the low bit of a next pointer is always zero and free to use as a mark:

1. Logical delete: CAS the mark bit into curr->next, tagging curr as deleted without unlinking it. Crucially, this changes the value of curr->next, so any concurrent insert that tries to CAS curr->next now fails — you cannot append to a marked node.
2. Physical delete: CAS pred->next to swing past curr. If it fails (the neighbourhood moved), re-traverse; a later search will finish the unlinking.

The reason a single CAS cannot do both jobs is exactly this: one CAS on pred->next unlinks curr but does nothing to stop a concurrent insertion after curr. Marking curr->next first is what makes such an insertion fail, so the mark-then-swing pair is irreducible. In C++ the mark rides in the pointer itself:

// low bit of an aligned Node* is always 0 -> use it as the "deleted" mark
inline Node* mark(Node* p)    { return reinterpret_cast<Node*>(
                                    reinterpret_cast<uintptr_t>(p) | 1); }
inline Node* unmark(Node* p)  { return reinterpret_cast<Node*>(
                                    reinterpret_cast<uintptr_t>(p) & ~uintptr_t(1)); }
inline bool  is_marked(Node* p){ return reinterpret_cast<uintptr_t>(p) & 1; }

Choosing a Rung

Check Yourself

Seven situations, in rough order of difficulty. Pick the statement that is actually true.

Practice

• Read Michael & Scott, Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms (PODC 1996). source implement the queue above and stress it with a ThreadSanitizer build.
• Read Harris, A Pragmatic Implementation of Non-Blocking Linked-Lists (DISC 2001). source implement mark-then-swing deletion and reproduce the lost-insertion race without the mark.
• Study Herlihy & Shavit, The Art of Multiprocessor Programming, ch. 9. reference build the lazy list and prove its contains is wait-free.
• Construct an ABA failure in the Treiber stack with three threads, then fix it with a tagged pointer and again with hazard pointers. aba compare the memory bounds.
• Benchmark a coarse mutex against your lock-free queue at 1, 4, 16, and 64 threads. reality find the crossover and note it is higher than folklore claims.
• LeetCode 622 — Design Circular Queue warm-up get the single-threaded logic airtight, then reason about which fields would need to be atomic.