MerceMay.Technical Library

Data Structures · Linked Structures

Lock-Free Linked Lists and the Reclamation Problem

Compare-and-swap can insert and delete on a singly linked list without locks, but freeing a removed node requires hazard pointers or epoch tracking to stop reuse.

Archive date September 11, 2026 · 9 min read · advanced

A linked list is the natural first target for a lock-free algorithm, because its updates are single pointer writes and a single write can be made atomic. That intuition is correct up to the point where a thread frees a node, at which moment the algorithm’s correctness depends on knowing whether any other thread still holds a reference. Solving that second problem is harder than the first, and it is where most of the design effort goes.

The insert that works

Insertion into a sorted singly linked list needs two pointers: the node to modify and the value it must point to. A compare-and-swap on the predecessor’s next field does the update atomically, provided the field still holds the successor that was observed.

#include <stdatomic.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>

struct lnode {
    int value;
    _Atomic(struct lnode *) next;
};

/* Insert v after prev, provided prev->next is still expected. */
bool insert_after(struct lnode *prev, struct lnode *expected, struct lnode *fresh) {
    fresh->next = expected;
    return atomic_compare_exchange_strong(&prev->next, &expected, fresh);
}

atomic_compare_exchange_strong takes the expected value by pointer and, on failure, writes the actual value back into it. A caller that fails can retry with the updated expectation, which is the standard optimistic loop. The _strong variant is required here rather than _weak, because a spurious failure would be indistinguishable from a real conflict and the retry logic would not know whether to re-read.

Insertion is this simple because it publishes exactly one pointer and the new node is fully initialised before the CAS. The release semantics of the CAS ensure that a thread which observes the new pointer also observes the initialised fields, on any architecture whose atomics map to the C11 model.

The delete that needs a mark bit

Deletion cannot be done by a single CAS in the same way. Removing node n requires changing the predecessor’s next from n to n’s successor, and the predecessor is not known without a search. A thread that searches, finds n, and then CASes is racing with any other thread that modifies the predecessor. Worse, two concurrent deletions of adjacent nodes can each succeed in a way that leaves the list inconsistent: thread A removes n and thread B removes n’s successor, and the two CASes can interleave so that the predecessor points to a node whose successor link was already changed.

Harris’s solution is logical deletion by marking. The low bit of the next pointer is reserved as a deletion flag, and a node is removed in two phases: first CAS its next field to set the mark, then CAS the predecessor’s next to bypass it.

Phase 1:  n->next:  s        ->  s | 1        (mark: logically deleted)
Phase 2:  p->next:  n        ->  s            (unlink: physically removed)

Because nodes are at least 4-byte aligned under the usual allocator guarantees, the low bit is free. A traversal that encounters a marked pointer treats the node as absent and continues to the successor with the bit cleared. The two phases mean that a deletion is observable as a single atomic step (the mark) before it changes the list’s shape, which is what allows other threads to make progress without a lock.

The mark also fixes the adjacent-deletion race. A thread that observes a marked successor knows another thread has claimed that node and can help by completing the unlink, rather than attempting its own deletion and creating a window in which two predecessors both point past each other.

A practical implementation needs a second CAS in phase two that checks the predecessor still points at n with the mark set, and it must retry the whole search if the check fails. Michael’s algorithm refines this into a two-pass traversal that locates the predecessor and successor of a marked node and unlinks it, which is the version most implementations follow because it makes progress under contention rather than livelocking.

The ABA problem

The mark bit solves one hazard and leaves another. Consider a thread that reads p->next as n, is descheduled, and resumes after another thread has removed n and the allocator has handed the same address back for a new node inserted at the same position. The CAS on p->next succeeds because the value matches, but the node at that address is a different object with different contents. The algorithm proceeds on stale data.

This is ABA, and it is the reason lock-free code cannot simply trust pointer equality. Three mitigations exist, each with a cost.

Tagged pointers. Widen the compared value to include a counter that increments on every reuse. The CAS then compares pointer and tag together, so a recycled address fails the comparison. The counter must fit in the spare bits of the pointer; on a 64-bit target that leaves at most 16 bits if the top half of the address space is unused, and often fewer once the mark bit and any alignment bits are accounted for, so the tag wraps after tens of thousands of reuses. That is enough for a short window and not enough for a long one.

Hazard pointers. Each thread publishes the addresses it is currently reading in a small array of hazard slots. Before a node is freed, the freeing thread scans all hazard slots and skips any node that appears in one. The scan is O(threads × hazards) per reclamation, which is expensive per free but bounded, and the number of deferred nodes is bounded by the reclamation policy rather than by the number of threads: each thread can retire one node at a time, but those it has retired behind a hazard held by another thread accumulate until that hazard is released. The same deferred-free discipline appears in allocator free lists, where a block cannot be reused until no thread holds a pointer into it, as described in Free Lists.

Epoch-based reclamation. Threads announce their presence in a global epoch. A node retired in epoch e can be freed once every thread has either left the critical section or advanced past e. The check is cheap (a per-thread counter) and the deferred memory is bounded by the number of threads times the number of retired nodes per critical section. The failure mode is that a thread stalled inside a critical section prevents all reclamation, so the technique is unsuitable when a thread can block while holding a reference.

RCU is the read-mostly variant of the same idea, with readers that take no atomic operation and no lock, and a grace period that waits for all pre-existing readers before reclaiming. It is the standard mechanism for linked structures in the Linux kernel precisely because reader overhead is the thing being optimised.

Why the doubly linked version is much harder

A doubly linked node has two fields that must change together, and a CAS only covers one. Removing n requires setting n->prev->next = n->next and n->next->prev = n->prev, and between the two writes the list is inconsistent. A reader traversing backward through the second link can observe a state that no sequential execution produces.

The usual answer is to avoid the second link in the concurrent structure. A lock-free ordered set can be built as a singly linked Harris list, and a doubly linked structure is reserved for cases where backward traversal is needed but concurrency is handled by a different mechanism, such as a reader-writer lock or a per-node lock. This is why Doubly Linked Lists and the Sentinel Header describes a layout that is excellent for single-threaded splicing and poor for lock-free update: the branch-free unlink is branch-free only because it assumes exclusive access to both neighbours.

There are doubly linked lock-free designs, and they rely on making the two updates logically atomic through a versioned or marked pair of fields, or on a helping protocol where any thread that observes an intermediate state completes it. All of them cost more than the singly linked version and none is a drop-in replacement.

Progress guarantees, stated precisely

Lock-free means that some thread always makes progress, not that every thread does. An insert loop that retries on CAS failure is lock-free: the failing thread’s work is wasted, but the succeeding thread’s CAS is the progress. A deletion that must complete another thread’s phase two is also lock-free, and it is helping: the thread that observes a marked node does work on behalf of the thread that marked it.

Obstruction-free is weaker (a thread makes progress only when run in isolation), and wait-free is stronger (every thread completes in a bounded number of steps). A Harris list is lock-free and not wait-free; under adversarial scheduling, one thread can be starved indefinitely while others succeed. That is usually acceptable, and it is worth stating plainly rather than claiming stronger progress than the algorithm provides.

The cost of lock-freedom is paid in two places. The first is the retry loop, which burns CPU when contention is high; a lock would instead put the loser to sleep. The second is reclamation, which needs either a scan or a global counter, both of which touch shared state that a lock-free fast path otherwise avoids.

A minimal correct skeleton

The following is a complete sorted-set insert for a Harris list with a mark bit, omitting reclamation, which is the part that must be supplied by the surrounding system.

#define MARK 1

static struct lnode *unmarked(struct lnode *p) {
    return (struct lnode *)((uintptr_t)p & ~(uintptr_t)MARK);
}

bool set_insert(struct lnode *head, int v) {
    struct lnode *prev, *cur, *next;
    for (;;) {
        prev = head;
        cur = atomic_load(&head->next);
        for (;;) {
            if (cur == NULL) break;
            next = atomic_load(&cur->next);
            if ((uintptr_t)next & MARK) {         /* cur logically deleted */
                struct lnode *succ = unmarked(next);
                /* help: unlink cur if prev still points at it */
                atomic_compare_exchange_strong(&prev->next, &cur, succ);
                cur = atomic_load(&prev->next);
                continue;
            }
            if (cur->value >= v) break;
            prev = cur;
            cur = next;
        }
        if (cur && cur->value == v) return false;  /* already present */
        struct lnode *fresh = malloc(sizeof *fresh);
        if (!fresh) return false;
        fresh->value = v;
        fresh->next = cur;
        if (atomic_compare_exchange_strong(&prev->next, &cur, fresh)) return true;
        free(fresh);                               /* lost the race; retry */
    }
}

Three details carry the correctness. The free(fresh) on failure is safe because the node was never published. The help step CASes prev->next from cur to succ, which is the same transition a concurrent thread would perform on that field, so it cannot leave a state that no sequential execution produces. And the loop re-reads cur after helping, because the CAS may have failed, in which case prev->next now holds something other than cur and the traversal must continue from there.

The omission is deliberate: the delete path retires nodes, and retiring them requires the reclamation scheme. Without one, the algorithm is correct but leaks every removed node.

What the structure is good for

The lock-free list is appropriate when reads dominate and updates are rare, because the read path takes no atomic write and no lock, and a reader that encounters a marked node simply skips it. It is also appropriate when a thread cannot afford to wait, as in a latency-sensitive task, since a lock-free update cannot deadlock and cannot be preempted while holding a lock. Signal and interrupt handlers are a weaker case: the algorithm is lock-free with respect to other threads, but a handler that interrupts a thread mid-update can still observe a marked node, and malloc is not async-signal-safe on every platform.

It is a poor choice for a write-heavy workload, where the retry traffic costs more than a lock’s contention, and for a structure that needs backward traversal, where the doubly linked layout cannot be made lock-free without substantial extra machinery. The honest summary is that lock-free lists are a specialised tool for read-mostly, latency-sensitive sets, and that their complexity is dominated by reclamation rather than by the list operations themselves.

References

  1. A Pragmatic Implementation of Non-Blocking Linked-Lists — Timothy L. Harris; DISC 2001
  2. High Performance Dynamic Lock-Free Hash Tables and List-Based Sets — Maged M. Michael; SPAA 2002
  3. Read-Copy Update: Using Execution History to Solve Concurrency Problems — McKenney & Slingwine; PDCS 1998
  4. ISO/IEC 9899:2011 — Programming languages — C — ISO/IEC