Lock-Free Queues Done Right

The model in four sentences:

1. Within one thread, each operation is sequenced before the next.
2. A Release store (or stronger) synchronizes with an Acquire load (or stronger) that reads the value it wrote — or a later value in its release sequence, which, since C++20, only read-modify-writes extend.
3. Happens-before is the transitive closure of the two: if A is sequenced before a release store that synchronizes with an acquire load that is sequenced before B, then A happens before B.
4. Two accesses to the same non-atomic location, at least one a write, from different threads, not ordered by happens-before, are a data race — undefined behaviour in Rust, regardless of what the hardware would do.

The message-passing (MP) litmus test is the pattern behind every queue you will write:

// Thread 0                              // Thread 1
DATA = 42;                               if READY.load(Acquire) {
READY.store(true, Release);                  assert_eq!(DATA, 42); // guaranteed
                                         }

The guarantee comes from rule 2 and 3: the write to DATA is sequenced before the release store, which synchronizes with the acquire load that saw true, which is sequenced before the read. Weaken either side to Relaxed and the edge disappears; the read is now a data race even though "the flag was set".

data.store(1, Relaxed);
flag.store(1, Relaxed);

let r1 = flag.load(Relaxed);
let r2 = data.load(Relaxed);

The best way to make the four rules stick is to implement them. Tools like ThreadSanitizer and loom track happens-before with vector clocks: each thread keeps a counter per thread, recording how much of every other thread's history it is guaranteed to have seen.

• Each event ticks its own thread's entry.
• A release store remembers the storing thread's clock at that moment.
• An acquire load that reads from such a store takes the element-wise maximum of that remembered clock and its own.
• Event A (on thread t) happens before event B exactly when B's clock has caught up with A's tick: clock_B[t] >= clock_A[t].

The drill feeds you executions as lists of events with explicit reads-from edges (which store each load observed), including the classic broken variants: Relaxed everywhere, Release paired with a Relaxed load, an acquire that read the initial value, a chain through a relay thread, and a reader that saw a later Relaxed store rather than the Release one.

/// Orderings that are legal on a store (Relaxed, Release, SeqCst) or a load
/// (Relaxed, Acquire, SeqCst). The harness never builds an illegal pair.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum Mo {
    Relaxed,
    Release,
    Acquire,
    SeqCst,
}

#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum Op {
    /// Non-atomic write to plain memory location `loc`.
    Write(usize),
    /// Non-atomic read of plain memory location `loc`.
    Read(usize),
    /// Atomic store to atomic variable `var`.
    Store(usize, Mo),
    /// Atomic load of `var` that observed the value written by the event at
    /// index `rf` in the trace (`None` = it saw the initial value).
    Load(usize, Mo, Option<usize>),
}

#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub struct Ev {
    pub thread: usize,
    pub op: Op,
}

/// Happens-before for one execution. `events` are listed in an order that is
/// consistent with each thread's program order and with reads-from (a load
/// always comes after the store it read).
pub struct Trace {
    // Suggested: one vector clock per event, plus each event's thread.
    threads: Vec<usize>,
    stamps: Vec<Vec<u32>>,
}

impl Trace {
    /// Walk the events once, maintaining a vector clock per thread:
    ///   - every event ticks its own thread's entry;
    ///   - a Release/SeqCst store remembers its thread's clock;
    ///   - an Acquire/SeqCst load that read from such a store joins
    ///     (element-wise max) that remembered clock into its thread's clock.
    /// Only the store a load actually read from counts — there are no
    /// read-modify-writes here, so there are no release sequences to follow.
    pub fn analyze(events: &[Ev]) -> Trace {
        todo!()
    }

    /// Does event `a` happen-before event `b`?
    pub fn happens_before(&self, a: usize, b: usize) -> bool {
        todo!()
    }
}

/// Every pair `(i, j)`, `i < j`, of plain accesses (Write/Read) to the same
/// location, from different threads, at least one a Write, where neither
/// happens-before the other. Sorted by `(i, j)`.
pub fn data_races(events: &[Ev]) -> Vec<(usize, usize)> {
    todo!()
}

There are two reorderers between your source and memory: the compiler and the CPU. The memory model constrains both. What each CPU does on its own:

• x86-64 (TSO): loads are not reordered with other loads, stores are not reordered with other stores, and a store is not reordered with an earlier load. The one relaxation is that a load may complete before an earlier store to a different address, because stores sit in a store buffer before they reach L1. Consequence: on x86, Acquire loads and Release stores compile to plain movs. Only SeqCst stores cost something (xchg, or mov plus mfence).
• ARMv8 / AArch64: almost any reordering of independent accesses is allowed. Acquire loads become ldar, Release stores stlr (ARMv8.3 adds the cheaper ldapr for Acquire); Relaxed becomes plain ldr/str. Graviton servers and Apple Silicon laptops will show you bugs x86 never will.

So an x86 test suite cannot catch a missing Acquire — but the compiler still can, because Relaxed lets it move your data read above the flag check on any architecture. "It works on x86" is never evidence.

The store buffer is also why SeqCst exists. In the store-buffering (SB) test, each thread stores to its own flag and then loads the other's. With Release/Acquire (and on real x86 hardware, with plain moves) both threads can read 0: each load completes while the thread's own store is still in its store buffer. Only SeqCst on all four operations forbids that outcome. Dekker-style mutual exclusion and some shutdown handshakes need this; queues almost never do.

x.store(1, Relaxed);
let r1 = y.load(Relaxed);

y.store(1, Relaxed);
let r2 = x.load(Relaxed);

Your week 1 ring reads the other side's index on every operation: try_push loads tail, try_pop loads head. After week 4 those indices sit on separate lines, but every load of the remote index still has to fetch a line the other core keeps modifying. That is one coherence miss per item, tens of nanoseconds each.

Cached indices. The producer keeps a private copy of the consumer's tail, and only reloads the shared one when the cached value says the ring is full. The consumer does the same with head. When the ring is neither nearly full nor nearly empty, most operations touch only core-local data:

pub fn try_push(&mut self, v: T) -> Result<(), T> {
    let head = self.head_local;                      // only we write head
    if head - self.tail_cache == CAP {
        self.tail_cache = self.shared.tail.load(Acquire); // pay for the miss rarely
        if head - self.tail_cache == CAP {
            return Err(v);
        }
    }
    unsafe { self.shared.slot(head).write(v) };
    self.head_local = head + 1;
    self.shared.head.store(head + 1, Release);
    Ok(())
}

Note the &mut self: the producer handle now owns state, which is fine because there is exactly one producer, and the type system already says so.

Batching. Publishing head after every item means the consumer's next read of head misses for every item. Write N items, then publish once; read N items, then publish tail once. One line transfer now carries N items. The cost is latency for the first item in a batch, so batch what is already available rather than waiting to fill a batch: drain everything the consumer can see, process it, publish. This is the "smart batching" idea from the Mechanical Sympathy blog and the core of how the LMAX Disruptor amortizes its sequence reads.

Switch on cached indices, then batching, and compare the index-line transfers per item in the table; then move the two rates apart until the ring sits full (or empty) and watch one side go back to reloading the remote index on nearly every operation.

With several producers, head is no longer owned by one thread. Producers must claim a position, and two producers must never claim the same one. That claim is a compare-and-swap on the shared tail: read pos, try to swing tail from pos to pos + 1; if another producer got there first, the CAS fails and returns the current value to retry with.

Claiming is not publishing. Between a producer's successful CAS and its write of the value, the consumer must not read that slot. Vyukov's answer is a sequence number per slot:

• seq == pos — the slot is empty and ready for the producer that claims position pos.
• seq == pos + 1 — the slot is full with the value pushed at pos (published with Release).
• After the consumer reads it, it sets seq = pos + capacity: empty, ready for the next lap.

Details that matter:

• No ABA. Positions are monotonically increasing usizes; a 64-bit counter at a billion operations a second wraps after roughly 580 years.
• compare_exchange_weak in a loop. It may fail spuriously (on LL/SC machines such as ARM without LSE atomics) but compiles to a cheaper instruction sequence there; on x86 both versions are a lock cmpxchg.
• Relaxed CAS on the tail is enough. The CAS only arbitrates ownership of a position. The data is published by the slot's Release sequence store and observed by the consumer's Acquire load.
• Capacity of at least 2. With one slot, "full at position p" and "empty for position p + 1" are the same sequence number.
• It is not strictly lock-free. If a producer is preempted between claiming position p and publishing it, the consumer sees slot p as empty and cannot get past it, even if later positions are full. That is fine for an exchange where producers are pinned threads, and worth saying out loud in an interview.

use std::cell::UnsafeCell;
use std::mem::MaybeUninit;
use std::sync::atomic::{AtomicUsize, Ordering};
use std::sync::Arc;

struct Slot<T> {
    /// Vyukov sequence number. For position p (slot p & mask):
    ///   seq == p      → empty: a producer may claim position p
    ///   seq == p + 1  → full: holds the value pushed at position p
    seq: AtomicUsize,
    value: UnsafeCell<MaybeUninit<T>>,
}

struct Queue<T> {
    slots: Box<[Slot<T>]>,
    mask: usize,
    /// Next position a producer will claim (contended by all producers).
    tail: AtomicUsize,
    /// Next position the consumer reads (only the consumer touches it).
    head: AtomicUsize,
}

unsafe impl<T: Send> Send for Queue<T> {}
unsafe impl<T: Send> Sync for Queue<T> {}

/// Many producers: `Producer` is `Clone`.
pub struct Producer<T> {
    q: Arc<Queue<T>>,
}

/// One consumer: `Consumer` is not `Clone`, and `pop` takes `&mut self`.
pub struct Consumer<T> {
    q: Arc<Queue<T>>,
}

impl<T> Clone for Producer<T> {
    fn clone(&self) -> Self {
        Producer { q: Arc::clone(&self.q) }
    }
}

/// `cap` must be a power of two and at least 2 (with one slot, "full at
/// position p" and "empty at position p + 1" are the same sequence number).
pub fn mpsc<T: Send>(cap: usize) -> (Producer<T>, Consumer<T>) {
    assert!(cap >= 2 && cap.is_power_of_two(), "capacity must be a power of two ≥ 2");
    let slots = (0..cap)
        .map(|i| Slot { seq: AtomicUsize::new(i), value: UnsafeCell::new(MaybeUninit::uninit()) })
        .collect();
    let q = Arc::new(Queue { slots, mask: cap - 1, tail: AtomicUsize::new(0), head: AtomicUsize::new(0) });
    (Producer { q: Arc::clone(&q) }, Consumer { q })
}

impl<T: Send> Producer<T> {
    /// Push `value`, or hand it back if the queue is full.
    pub fn push(&self, value: T) -> Result<(), T> {
        // TODO (Vyukov). Loop:
        //   pos  = tail (Relaxed)
        //   seq  = slots[pos & mask].seq (Acquire)
        //   diff = seq as isize - pos as isize
        //   diff == 0 → claim pos with tail.compare_exchange_weak(pos, pos + 1, ..):
        //               on success write the value, then publish seq = pos + 1 (Release)
        //               on failure someone else claimed pos — retry
        //   diff  < 0 → the slot still holds last lap's value: full, Err(value)
        //   diff  > 0 → another producer already took pos: reload tail, retry
        todo!()
    }
}

impl<T: Send> Consumer<T> {
    /// Pop the oldest published value.
    pub fn pop(&mut self) -> Option<T> {
        // TODO: pos = head; if slots[pos & mask].seq (Acquire) == pos + 1,
        // move the value out, free the slot for the next lap
        // (seq = pos + cap, Release) and advance head. Otherwise None.
        todo!()
    }
}

impl<T> Drop for Queue<T> {
    fn drop(&mut self) {
        // Exclusive access (no other handle is alive): drop whatever is still
        // published so values are not leaked.
        let cap = self.mask + 1;
        let mut pos = *self.head.get_mut();
        loop {
            let slot = &mut self.slots[pos & self.mask];
            if *slot.seq.get_mut() != pos + 1 {
                break;
            }
            unsafe { slot.value.get_mut().assume_init_drop() };
            *slot.seq.get_mut() = pos + cap;
            pos += 1;
        }
    }
}

A lock-free queue that passes a million-iteration stress test on x86 has told you very little. Three tools give you real coverage:

• loom swaps std::sync::atomic and UnsafeCell for instrumented versions behind a cfg(loom) and explores interleavings exhaustively. Keep loom tests tiny (two or three threads, two or three operations each); the state space explodes fast.
• Miri (cargo +nightly miri test) interprets your code, detects data races and many kinds of undefined behaviour in unsafe, and emulates some weak-memory effects.
• A weakly ordered machine. Run the stress tests on AArch64 (a Graviton instance or an Apple Silicon laptop) as part of CI. It will catch ordering mistakes x86 hides.