Lock-Free Structures and Lock Hierarchy¶

“Lock-free” is one of the most seductive and misunderstood words in systems programming. It doesn’t mean “no synchronization.” It means “no thread can be blocked indefinitely by another thread being suspended” — a specific progress guarantee. In practice, lock-free code uses atomic instructions (compare-and-swap, fetch-and-add) as its synchronization primitive instead of a mutex.

This file has two purposes. First, teach you one lock-free structure end-to-end — the single-producer single-consumer (SPSC) ring buffer — because it’s the one lock-free structure that’s simultaneously (a) genuinely useful in real code, (b) simple enough to prove correct on paper, and (c) shows up in every audio/video/networking pipeline you’ll ever touch. Second, teach you the discipline of lock ordering, which is the actual technique that keeps large concurrent codebases free of deadlocks.

The vocabulary¶

Blocking — a thread waiting on a mutex is blocked. If the mutex holder is suspended (by the OS scheduler, a page fault, whatever), the waiter waits.
Lock-free — at least one thread makes progress at any moment. If one thread is suspended mid-operation, other threads can still complete theirs.
Wait-free — every thread completes its operation in a bounded number of its own steps, regardless of other threads. Strongest guarantee, rarely achieved.

Real production code is almost entirely blocking (locks), with lock-free pockets in specific hot paths. Wait-free is mostly a research toy.

SPSC ring buffer — the useful one¶

Constraint: exactly one producer thread, exactly one consumer thread. No more. This constraint is what makes it tractable: only one writer to each index variable.

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

#define CAP 1024               // must be power of two
#define MASK (CAP - 1)

typedef struct {
    _Atomic uint32_t head;     // written by producer, read by both
    _Atomic uint32_t tail;     // written by consumer, read by both
    void *buf[CAP];
} spsc_t;

// producer
bool spsc_push(spsc_t *q, void *v) {
    uint32_t h = atomic_load_explicit(&q->head, memory_order_relaxed);
    uint32_t t = atomic_load_explicit(&q->tail, memory_order_acquire);
    if (h - t >= CAP) return false;                    // full
    q->buf[h & MASK] = v;
    atomic_store_explicit(&q->head, h + 1, memory_order_release);
    return true;
}

// consumer
bool spsc_pop(spsc_t *q, void **out) {
    uint32_t t = atomic_load_explicit(&q->tail, memory_order_relaxed);
    uint32_t h = atomic_load_explicit(&q->head, memory_order_acquire);
    if (h == t) return false;                          // empty
    *out = q->buf[t & MASK];
    atomic_store_explicit(&q->tail, t + 1, memory_order_release);
    return true;
}

Read it slowly. Then read it again. Notice:

head is only written by producer, tail only by consumer. No CAS needed. Each is a plain atomic store from its owner and an atomic load from the other side.
The release-store on head in push pairs with the acquire-load on head in pop. This is what guarantees the consumer sees buf[h & MASK] = v after loading the new head — it’s the acquire-release publish pattern from file 02.
Same for tail (release from consumer pairs with acquire from producer).
Indices are unsigned and allowed to wrap. The subtraction h - t in unsigned arithmetic still gives the right occupancy count even after wrap, as long as capacity is a power of two and less than 2^31. This is a standard trick; drill it in once and you’ll recognize it forever.
Capacity is a power of two so & MASK replaces % CAP (faster and simpler to reason about).

Padding note: in production, put head and tail in separate cache lines to avoid false sharing between producer and consumer:

typedef struct {
    alignas(64) _Atomic uint32_t head;
    alignas(64) _Atomic uint32_t tail;
    void *buf[CAP];
} spsc_t;

Real-world examples of SPSC ring buffers:

Audio callbacks writing samples to a mixer thread (DAW pipelines, JACK, PortAudio).
DPDK / kernel bypass networking (per-CPU rings).
The Linux kernel’s kfifo.
CUDA host-to-device staging in some ML pipelines.

Beyond SPSC — MPMC (multi-producer multi-consumer) queues exist but are significantly harder. Two names to know: Dmitry Vyukov’s bounded MPMC queue (widely copied), and moodycamel’s ConcurrentQueue (C++, but the algorithm translates). Do not attempt MPMC lock-free from scratch in this phase.

The ABA problem¶

The classic pitfall in CAS-based lock-free code. Consider a stack popping the head:

// pop pseudocode
do {
    old_head = atomic_load(&head);
    if (!old_head) return NULL;
    new_head = old_head->next;
} while (!atomic_compare_exchange_weak(&head, &old_head, new_head));
return old_head;

Looks correct. But suppose:

Thread T1 reads old_head = A, computes new_head = A->next = B, then gets suspended.
Thread T2 pops A. Now head = B.
Thread T2 pops B. Now head = NULL.
Thread T2 pushes A back (perhaps freeing and reallocating; same address).
T1 resumes. CAS: is head == A? Yes. Set head = B. But B was freed!

The pointer was “A”, then “not A”, then “A again” — the CAS can’t tell the difference. That’s ABA.

Fixes (all imperfect):

Tagged pointers — bundle a version counter into the low or high bits of the pointer. Incremented on every operation. CAS on the (pointer, tag) tuple. Requires double-word CAS (__int128 on x86-64) or reserved bits.
Hazard pointers — each thread publishes what it’s currently accessing; frees are deferred until no one hazards the pointer. Notorious to get right.
RCU / epoch-based reclamation — the reader marks that it’s in a read region; frees wait for all readers to leave the region. Beautiful when applicable.

The honest takeaway: if you’re seriously considering writing a general lock-free stack or queue, use an existing library (folly’s concurrent structures, Concurrency Kit libck, Dmitry Vyukov’s public code). Don’t reinvent this.

Why lock-free is often slower than a well-designed locked structure¶

This is the counterintuitive part they don’t tell you in “here’s a wait-free queue” blog posts.

Contention is the enemy, not locks. A mutex around a 20-instruction critical section, under contention, is dominated by cache-line ping-pong between cores — exactly the same as a spinning CAS loop.
Uncontended mutex cost is ~20-30 ns (a single atomic op plus function call). Lock-free ops have the same cache/atomic costs per operation, and often more of them per logical operation.
Lock-free algorithms are harder to design efficiently. A locked queue can batch operations under one lock acquisition; a lock-free queue often does per-item CAS retries.
CAS retries under contention are catastrophic. N threads racing, N-1 retry, cache line ping-pongs N times per successful op. A mutex serializes them politely; lock-free thrashes.

Anthony Williams-tier benchmarks and Cliff Click’s talks (“A JVM Does That?”) repeatedly show that a well-implemented lock-free structure wins by 2-5× in the best case, and loses by 10× when the workload doesn’t match its design.

Rule of thumb: SPSC is almost always worth it (dead simple, real gains, no contention by design). Anything MPMC lock-free needs a benchmark on your actual workload, not on a synthetic one.

Lock hierarchy — the technique that actually prevents deadlocks¶

Deadlocks happen when threads acquire multiple locks in different orders. Classic case:

// thread A                  // thread B
lock(m1); lock(m2);          lock(m2); lock(m1);   // deadlock

The prevention is disciplinary, not technical: impose a total order on locks and always acquire them in that order. In a codebase you assign each lock a level number (a “rank”), and enforce that a thread holding a lock at level N can only acquire locks at level > N.

In practice you might:

Assign locks numeric ranks in a comment or a macro.
In debug builds, use PTHREAD_MUTEX_ERRORCHECK and instrument lock acquisition to track ranks per-thread; assert on violation.
Split locks so their natural order is obvious (e.g., “parent before child” in a tree).

If two locks must sometimes be acquired in either order, use pthread_mutex_trylock and back off on failure to break potential cycles:

for (;;) {
    pthread_mutex_lock(&m1);
    if (pthread_mutex_trylock(&m2) == 0) break;    // got both
    pthread_mutex_unlock(&m1);
    sched_yield();
}

Helgrind and ThreadSanitizer (file 09) detect lock-order inversions automatically at runtime, provided you exercise both paths in tests. This is your safety net; run TSan on every concurrent codebase.

Practical rules to live by¶

Default to mutexes. Only reach for atomics/lock-free when a benchmark shows the mutex is the bottleneck.
If you must go lock-free, use SPSC or a proven library. Do not hand-roll MPMC.
Establish and document lock order. Even in a 500-line program.
Any function that acquires locks should document which locks it acquires, in what order, and which locks the caller must NOT hold. In a comment above the function.
Run TSan. Not “sometimes.” Every test run, every CI job.

What most people get wrong about this¶

They read a blog post titled “Lock-free queues are 10× faster” and rewrite their production task queue in lock-free code they don’t fully understand. Six months later they’re chasing a bug that only reproduces under load on Tuesdays. The mutex-based version they replaced was fine. Lock-free is a specialist tool for hot paths, not a default. Even the Linux kernel — which pioneered RCU precisely because it needed lock-free — is mostly locks.

Practice this week¶

Type out and understand the SPSC ring buffer above. Add padding for false sharing. Benchmark push+pop throughput at 1M items with a producer and a consumer thread. Typical laptop: 50-200M ops/sec.
Compare against a mutex-based bounded queue (file 01’s example) for the same workload. In SPSC, lock-free typically wins 3-10×. Note the numbers.
Now run the mutex-based version with 4 producers and 4 consumers. Now try to imagine what a correct MPMC lock-free version would look like. Don’t write it. Appreciate the difficulty.
Introduce a lock-order inversion deliberately in a 3-thread program. Run under helgrind. Read the report. Fix it.
Read chapter 6 (“Partitioning and Synchronization Design”) of McKenney’s perfbook.

References¶

Paul McKenney, perfbook — chapters 5, 6, 14. Ch 14 covers the deep atomic and RCU material.
Dmitry Vyukov’s public writings on 1024cores.net — the canonical lock-free algorithm reference. Read the SPSC and MPMC pages.
Preshing on Programming: “A Look at How SPSC Queues Are Implemented” — clean walkthrough.
Cliff Click, “A JVM Does That?” (YouTube) — perspective on when lock-free wins and loses.

Return to README.md · Next: 04_thread_pools_and_work_queues.md