Learn Rust Series (#69) - Building a Lock-Free Queue (Michael-Scott)

scipio(71)

Published in

StemSocial

Words

3326

Reading

15 min

Listen

Play

12h

Learn Rust Series (#69) - Building a Lock-Free Queue (Michael-Scott)

What will I learn

You will build the Michael-Scott queue, the standard lock-free FIFO queue;
why a permanent dummy sentinel node makes head and tail never null and simplifies the code;
how enqueue links a node then advances the tail in two CAS steps, helping a lagging tail along;
how dequeue advances the head past the dummy and takes the first real value;
why safe memory reclamation is even more critical here than for the stack.

Requirements

A working modern computer running macOS, Windows or Ubuntu;
An installed Rust toolchain (via rustup, from rustup.rs);
The previous sixty-eight episodes, especially the Treiber stack, AtomicPtr, and raw pointers;
The ambition to learn systems programming from the ground up.

Difficulty

Advanced

Curriculum (of the `Learn Rust Series`):

Learn Rust Series (#69) - Building a Lock-Free Queue (Michael-Scott)

Last episode we built a lock-free stack, and a stack is the easy case: it only ever touches one end. Push and pop both fight over a single AtomicPtr, the head, and that is the whole battlefield. A queue is a different animal. It is FIFO -- first in, first out -- so you add at the tail and remove at the head, which means there are now two hot pointers instead of one, and threads can be hammering both ends at the same time. Coordinating two ends without a lock is where lock-free programming stops being a party trick and becomes real engineering. The Michael-Scott queue, from a 1996 paper by Maged Michael and Michael Scott, is the classic answer, and it is the algorithm sitting underneath most production lock-free queues you will ever meet. Its central trick is a permanent dummy node that always sits at the head, so the head and tail pointers are never null and the "queue is empty" case stops being a special little branch you have to handle everywhere. This is the hardest data structure in the whole series, and building it by hand is a genuine rite of passage ;-)

I want to be honest the same way I was last time. If the Treiber stack was the hardest thing we had built so far, the Michael-Scott queue is now that. The extra difficulty is not the code volume -- it is the number of moments where two threads can interleave and leave the structure in a half-updated state that the next thread has to notice and repair. So we will build up to it in careful steps: a lock-based version for contrast, the dummy-node idea on its own, the raw-ownership plumbing from episode 68, then the full algorithm -- and I will keep pointing back to episode 66 (atomics), episode 67 (memory ordering), and episode 68 (the stack) as we go, because every tool we forged there gets spent right here.

Solutions to Episode 68 Exercises

Episode 68 was the Treiber stack, so all three solutions live in the world of AtomicPtr, CAS loops, and raw nodes.

Exercise 1 asked for an is_empty(&self) -> bool on the stack that returns whether the head is null via a single Acquire load, with a note on why the answer can be stale the instant it is returned:

use std::sync::atomic::{AtomicPtr, Ordering};
use std::ptr;

struct Node { v: i32, next: *mut Node }
struct Stack { head: AtomicPtr<Node> }

impl Stack {
    fn new() -> Self { Stack { head: AtomicPtr::new(ptr::null_mut()) } }
    // The answer is a snapshot: another thread may push or pop the very next
    // instant, so `is_empty()` returning true never means "still empty by the
    // time you act on it". It is advisory only under concurrency.
    fn is_empty(&self) -> bool { self.head.load(Ordering::Acquire).is_null() }
    fn push(&self, v: i32) {
        let n = Box::into_raw(Box::new(Node { v, next: self.head.load(Ordering::Acquire) }));
        self.head.store(n, Ordering::Release);
    }
}

fn main() {
    let s = Stack::new();
    println!("{}", s.is_empty()); // true
    s.push(1);
    println!("{}", s.is_empty()); // false
}

The key insight: any query that returns a bool about shared state is a photograph, not a lease. It tells you how things looked, not how they will be.

Exercise 2 wanted a peek(&self) -> Option<i32> that copies the top value without popping it, plus a comment on why reading through the head is only safe under low contention:

use std::sync::atomic::{AtomicPtr, Ordering};
use std::ptr;

struct Node { v: i32, next: *mut Node }
struct Stack { head: AtomicPtr<Node> }

impl Stack {
    fn new() -> Self { Stack { head: AtomicPtr::new(ptr::null_mut()) } }
    fn push(&self, v: i32) {
        let n = Box::into_raw(Box::new(Node { v, next: self.head.load(Ordering::Acquire) }));
        self.head.store(n, Ordering::Release);
    }
    // Safe only under low contention: between the load and the deref, another
    // thread could pop the top node and free it, so `(*head).v` would read
    // freed memory. Defeating that needs the reclamation scheme discussed below.
    fn peek(&self) -> Option<i32> {
        let head = self.head.load(Ordering::Acquire);
        if head.is_null() { None } else { Some(unsafe { (*head).v }) }
    }
}

fn main() {
    let s = Stack::new();
    s.push(10);
    println!("{:?}", s.peek()); // Some(10)
}

Peeking is exactly the use-after-free window we warned about last episode, in miniature: you hold a raw pointer while someone else might free what it points at.

Exercise 3 asked for a stress test: push from four scoped threads, each pushing a range of numbers, join them, then pop everything on the main thread and assert the count equals the total pushed:

use std::sync::atomic::{AtomicPtr, Ordering};
use std::ptr;
use std::thread;

struct Node { v: i32, next: *mut Node }
struct Stack { head: AtomicPtr<Node> }

impl Stack {
    fn new() -> Self { Stack { head: AtomicPtr::new(ptr::null_mut()) } }
    fn push(&self, v: i32) {
        let node = Box::into_raw(Box::new(Node { v, next: ptr::null_mut() }));
        loop {
            let head = self.head.load(Ordering::Acquire);
            unsafe { (*node).next = head; }
            if self.head.compare_exchange(head, node, Ordering::Release, Ordering::Acquire).is_ok() {
                break;
            }
        }
    }
    fn pop(&self) -> Option<i32> {
        loop {
            let head = self.head.load(Ordering::Acquire);
            if head.is_null() { return None; }
            let next = unsafe { (*head).next };
            if self.head.compare_exchange(head, next, Ordering::Release, Ordering::Acquire).is_ok() {
                return Some(unsafe { Box::from_raw(head) }.v);
            }
        }
    }
}

fn main() {
    let stack = Stack::new();
    thread::scope(|s| {
        let sref = &stack;
        for base in 0..4 {
            s.spawn(move || {
                for i in 0..25 { sref.push(base * 25 + i); } // 4 x 25 = 100 pushes
            });
        }
    });
    let mut count = 0;
    while stack.pop().is_some() { count += 1; }
    assert_eq!(count, 100);
    println!("all {count} pushes accounted for"); // all 100 pushes accounted for
}

Four threads collide constantly on the same head pointer, every collision resolved by a CAS retry, and not a single one of the 100 values is lost or duplicated. That is the whole point of a lock-free structure holding up under real contention. Right -- homework cleared, now for the queue.

The lock-based version for contrast

As we did for the stack, let us start with the boring-but-correct baseline we could have written back in episode 65: a VecDeque behind a Mutex. It works perfectly, and for the overwhelming majority of programs it is the right choice. Everything below is about doing the same job without the lock, so that threads never have to take turns:

use std::collections::VecDeque;
use std::sync::Mutex;

struct LockedQueue<T> {
    inner: Mutex<VecDeque<T>>,
}

impl<T> LockedQueue<T> {
    fn new() -> Self { LockedQueue { inner: Mutex::new(VecDeque::new()) } }
    fn enqueue(&self, v: T) { self.inner.lock().unwrap().push_back(v); }
    fn dequeue(&self) -> Option<T> { self.inner.lock().unwrap().pop_front() }
}

fn main() {
    let q = LockedQueue::new();
    q.enqueue(1);
    q.enqueue(2);
    println!("{:?} {:?}", q.dequeue(), q.dequeue()); // Some(1) Some(2), FIFO
}

Note the ordering already, because it is the whole personality of a queue. A queue is FIFO -- the mirror of the stack's LIFO. On a stack, the last thing you push is the first thing you pop. On a queue, the first thing you enqueue is the first thing you dequeue. Here is that difference made unmistakable with a plain VecDeque, so the contrast with last episode is crystal clear:

use std::collections::VecDeque;

fn main() {
    let mut q: VecDeque<i32> = VecDeque::new();
    for i in 1..=3 { q.push_back(i); }
    // pop from the FRONT: the first element in is the first out
    let order: Vec<i32> = std::iter::from_fn(|| q.pop_front()).collect();
    println!("{order:?}"); // [1, 2, 3], not [3, 2, 1]
}

The lock-based version serialises every operation: only one thread can hold the Mutex at a time, so enqueues and dequeues queue up (pun very much intended) behind the single lock. The lock-free version removes that entirely -- an enqueue at the tail and a dequeue at the head can proceed genuinely in parallel, because they touch different pointers. Having said that, "lock-free" once again does not mean "free". It means the cost moves from waiting to retrying, and it means the memory management the VecDeque did for us silently is now our job to get exactly right.

The dummy node trick

Here is the idea that makes the whole algorithm tractable. In a naive linked queue, the empty state is horrible: the head is null, the tail is null, and every enqueue and dequeue has to branch on "is the queue empty right now?" -- and worse, that branch has to stay correct while two threads race through it. The Michael-Scott insight is to never let the list be truly empty. The queue always holds at least one node: a valueless dummy (a sentinel). Both head and tail start out pointing at that dummy. Because the pointers are never null, enqueue and dequeue no longer need a separate "empty queue" branch for the pointer bookkeeping -- the empty case is simply "head and tail both point at the dummy, and the dummy has no next":

// A node carries an Option (the dummy holds None) and an atomic next pointer.
struct Node {
    value: Option<i32>,
    next: std::sync::atomic::AtomicPtr<Node>,
}

fn main() {
    use std::ptr;
    let dummy = Node { value: None, next: std::sync::atomic::AtomicPtr::new(ptr::null_mut()) };
    // head and tail both point at this dummy when the queue is empty
    println!("dummy carries a value? {}", dummy.value.is_some()); // false
}

Why does a valueless placeholder simplify anything? Because it decouples the two ends. The head always points at the dummy, and the real front of the queue is whatever the dummy's next points at. Dequeue never removes the dummy itself; it advances the head to the first real node, takes that node's value, and the node it left behind becomes the new dummy. The tail always points at the last node (or is caught mid-update, as we will see). The two ends only ever meet at the dummy, and that shared point is exactly where "empty" is defined. It is a beautiful bit of indirection, and it is the single reason the algorithm reads as cleanly as it does.

The building block, revisited: raw ownership

Just like the stack, each node is heap-allocated and handed to a raw pointer with Box::into_raw, then reclaimed with Box::from_raw exactly once when it leaves the queue. This is the same accounting discipline from episode 68 and episode 41 -- an allocation that leaves through into_raw must return through from_raw precisely one time, or you get a leak (never returned) or a double-free (returned twice, undefined behaviour). Here is that round trip on a single node, in isolation:

use std::sync::atomic::AtomicPtr;
use std::ptr;

struct Node { value: Option<i32>, next: AtomicPtr<Node> }

fn main() {
    let node = Box::into_raw(Box::new(Node { value: Some(5), next: AtomicPtr::new(ptr::null_mut()) }));
    let value = unsafe { (*node).value }; // Option is Copy here, so this reads it out
    println!("{value:?}"); // Some(5)
    unsafe { drop(Box::from_raw(node)); } // reclaim ownership exactly once, no leak
}

Notice the one structural difference from the stack: here next is itself an AtomicPtr<Node>, not a plain *mut Node. On the stack, only the head was atomic -- each node's next was a plain raw pointer that only the owning thread ever touched. In the queue, a node's next is written by an enqueuing thread and read by every other thread walking toward the tail, so it must be atomic in its own right. Every link in the chain is now a synchronisation point.

Walking a node chain

Because each next is an AtomicPtr, the list is a chain of atomically-linked nodes, and reading along it is just repeated Acquire loads. This is the exact traversal both enqueue and dequeue perform, so it is worth seeing it on its own before it is buried inside a CAS loop:

use std::sync::atomic::{AtomicPtr, Ordering};
use std::ptr;

struct Node { value: i32, next: AtomicPtr<Node> }

fn main() {
    let b = Box::into_raw(Box::new(Node { value: 2, next: AtomicPtr::new(ptr::null_mut()) }));
    let a = Box::into_raw(Box::new(Node { value: 1, next: AtomicPtr::new(b) }));
    unsafe {
        let first = (*a).value;
        let second = (*(*a).next.load(Ordering::Acquire)).value;
        println!("{first} then {second}"); // 1 then 2
        drop(Box::from_raw(a));
        drop(Box::from_raw(b));
    }
}

The Acquire on each next.load is not decoration, exactly as in episode 67: it is the read half of the release/acquire handshake that guarantees the fields of the node we are about to dereference were fully written before the pointer to it became visible. Follow a pointer with a Relaxed load and you might see the address but not the node's contents. So every hop is an Acquire.

The Michael-Scott queue

Now the whole structure. Read it once top to bottom, then we will walk enqueue and dequeue slowly. The short version: enqueue reads the tail, and if the tail's next is null it CAS-links the new node there, then tries to swing the tail forward. If it finds the tail lagging (its next is not null), it knows another thread linked a node but has not advanced the tail yet, so it helps by advancing the tail first and retries. dequeue reads the head, moves it to the first real node, takes that node's value, and frees the old dummy:

use std::sync::atomic::{AtomicPtr, Ordering};
use std::ptr;
use std::thread;

struct Node<T> {
    value: Option<T>,
    next: AtomicPtr<Node<T>>,
}

pub struct Queue<T> {
    head: AtomicPtr<Node<T>>,
    tail: AtomicPtr<Node<T>>,
}

impl<T> Queue<T> {
    pub fn new() -> Self {
        let dummy = Box::into_raw(Box::new(Node { value: None, next: AtomicPtr::new(ptr::null_mut()) }));
        Queue { head: AtomicPtr::new(dummy), tail: AtomicPtr::new(dummy) }
    }

    pub fn enqueue(&self, value: T) {
        let node = Box::into_raw(Box::new(Node { value: Some(value), next: AtomicPtr::new(ptr::null_mut()) }));
        loop {
            let tail = self.tail.load(Ordering::Acquire);
            let next = unsafe { (*tail).next.load(Ordering::Acquire) };
            if next.is_null() {
                // The tail really is the last node: link our node after it.
                if unsafe { (*tail).next.compare_exchange(next, node, Ordering::Release, Ordering::Acquire) }.is_ok() {
                    // Linked. Now advance the tail; if this fails, another thread already helped.
                    let _ = self.tail.compare_exchange(tail, node, Ordering::Release, Ordering::Acquire);
                    return;
                }
            } else {
                // The tail was lagging behind a linked node: help it forward, then retry.
                let _ = self.tail.compare_exchange(tail, next, Ordering::Release, Ordering::Acquire);
            }
        }
    }

    pub fn dequeue(&self) -> Option<T> {
        loop {
            let head = self.head.load(Ordering::Acquire);
            let next = unsafe { (*head).next.load(Ordering::Acquire) };
            if next.is_null() {
                return None; // only the dummy remains: the queue is empty
            }
            if self.head.compare_exchange(head, next, Ordering::Release, Ordering::Acquire).is_ok() {
                let value = unsafe { (*next).value.take() }; // first real node becomes the new dummy
                unsafe { drop(Box::from_raw(head)); }        // free the old dummy
                return value;
            }
        }
    }
}

impl<T> Drop for Queue<T> {
    fn drop(&mut self) {
        while self.dequeue().is_some() {}
        let dummy = self.head.load(Ordering::Relaxed);
        if !dummy.is_null() {
            unsafe { drop(Box::from_raw(dummy)); } // free the final dummy
        }
    }
}

fn main() {
    let q: Queue<i32> = Queue::new();
    thread::scope(|s| {
        let qref = &q;
        for i in 0..6 {
            s.spawn(move || qref.enqueue(i)); // six producers enqueue concurrently, lock-free
        }
    });
    let mut count = 0;
    while q.dequeue().is_some() { count += 1; }
    println!("dequeued {count} items after concurrent enqueues"); // dequeued 6 items
}

Walking enqueue slowly

The enqueue is the trickier of the two, because it is a two-step update and threads can be caught between the steps. First we allocate our node with into_raw. Then the loop begins. We read the current tail, and we read that tail's next. Two things can be true.

If the tail's next is null, the tail genuinely is the last node in the chain. We attempt compare_exchange(next, node, ...) on the tail's next pointer: "if this node's next is still null, make it point at my node". If that CAS succeeds, our node is now linked into the queue -- it is logically enqueued. But the tail pointer still points at the old last node, one step behind reality. So we do a second CAS to swing the tail forward to our node. Crucially, we ignore whether that second CAS succeeds (let _ =), and that is deliberate: if it fails, it can only be because some other thread already advanced the tail for us. Either way the tail ends up correct.

If the tail's next is not null, we have caught the structure mid-update: another thread linked its node (step one) but has not yet advanced the tail (step two), or was suspended right between them. Rather than wait -- waiting is exactly what lock-free code refuses to do -- we help. We do that stalled thread's second step for it, advancing the tail forward with a CAS, then loop and try again from a fresh read. This helping mechanism is the beating heart of the algorithm: no thread's progress ever depends on another thread waking up to finish its own work, because any thread that trips over an unfinished update just completes it. That is what makes the queue lock-free rather than merely lockless.

Walking dequeue slowly, and a single-threaded sanity check

Dequeue is calmer. We read the head (which always points at the current dummy) and the head's next. If next is null, only the dummy is present, so the queue is empty and we return None. Otherwise next is the first real node. We compare_exchange the head forward from the old dummy to that node. On success, we are the unique thread that unlinked the old dummy -- so we, and only we, take() the value out of the new front node (leaving None behind, which turns it into the next dummy) and free the old dummy with from_raw. That uniqueness is what keeps the "exactly once" rule intact: the winning CAS is the instant ownership of the old dummy transfers cleanly to us. Here is a single-threaded run proving the FIFO order end to end, no threads in sight:

use std::sync::atomic::{AtomicPtr, Ordering};
use std::ptr;

struct Node<T> { value: Option<T>, next: AtomicPtr<Node<T>> }
struct Queue<T> { head: AtomicPtr<Node<T>>, tail: AtomicPtr<Node<T>> }

impl<T> Queue<T> {
    fn new() -> Self {
        let d = Box::into_raw(Box::new(Node { value: None, next: AtomicPtr::new(ptr::null_mut()) }));
        Queue { head: AtomicPtr::new(d), tail: AtomicPtr::new(d) }
    }
    fn enqueue(&self, value: T) {
        let node = Box::into_raw(Box::new(Node { value: Some(value), next: AtomicPtr::new(ptr::null_mut()) }));
        loop {
            let tail = self.tail.load(Ordering::Acquire);
            let next = unsafe { (*tail).next.load(Ordering::Acquire) };
            if next.is_null() {
                if unsafe { (*tail).next.compare_exchange(next, node, Ordering::Release, Ordering::Acquire) }.is_ok() {
                    let _ = self.tail.compare_exchange(tail, node, Ordering::Release, Ordering::Acquire);
                    return;
                }
            } else {
                let _ = self.tail.compare_exchange(tail, next, Ordering::Release, Ordering::Acquire);
            }
        }
    }
    fn dequeue(&self) -> Option<T> {
        loop {
            let head = self.head.load(Ordering::Acquire);
            let next = unsafe { (*head).next.load(Ordering::Acquire) };
            if next.is_null() { return None; }
            if self.head.compare_exchange(head, next, Ordering::Release, Ordering::Acquire).is_ok() {
                let value = unsafe { (*next).value.take() };
                unsafe { drop(Box::from_raw(head)); }
                return value;
            }
        }
    }
}

fn main() {
    let q: Queue<i32> = Queue::new();
    for i in 1..=3 { q.enqueue(i); }
    println!("{:?}", q.dequeue()); // Some(1), first in first out
    println!("{:?}", q.dequeue()); // Some(2)
    println!("{:?}", q.dequeue()); // Some(3)
    println!("{:?}", q.dequeue()); // None
}

Enqueue 1, 2, 3, dequeue them back as 1, 2, 3 -- the mirror image of the stack's 3, 2, 1. The concurrent main in the full listing above does the same thing under six producers at once, and drains all six values afterward with none lost. Note the Drop impl: it dequeues everything to free the real nodes, then frees the final leftover dummy by hand, so a dropped queue leaks nothing.

The reclamation problem, again

Our concurrent demo enqueues from many threads but dequeues on a single thread afterward, which is safe. Fully concurrent dequeue -- many threads popping at once -- reopens the exact wound we met on the stack, and arguably a nastier version of it. One thread frees the old dummy with Box::from_raw while another thread might still be holding a pointer to that same node (it read the head a microsecond earlier and is about to dereference it). That is a use-after-free, and downstream it becomes the ABA problem all over again: an address is freed, recycled by the allocator, and a stale compare_exchange cannot tell "never moved" from "moved away and came back". The Michael-Scott paper assumes a safe reclamation scheme sitting underneath the algorithm, and in real Rust that scheme is a crate: crossbeam-epoch (epoch-based reclamation, which defers freeing a node until every thread has provably moved past the danger window) or hazard pointers via something like haphazard. You do not roll your own.

And that is the honest takeaway of these two episodes, the one I most want you to keep. You have now built, by hand, the two data structures the entire lock-free world is assembled from -- the stack and the queue. Writing the algorithm turns out to be the easy half; you can reason your way through CAS loops and helping and dummy nodes with a clear head and some patience. Safe memory reclamation is the hard half, the dragon, and the mature move in production Rust is to delegate it to a vetted crate rather than hand-rolling the one part most likely to corrupt memory silently. Knowing precisely where that line sits -- what you can build yourself and what you should not -- is a large part of what separates someone who has read about lock-free code from someone who has actually written it. Next episode we leave hand-rolled concurrency behind entirely and let a library turn ordinary iterators into parallel ones for us, which after two episodes of raw pointers is going to feel like a holiday ;-)

Tot de volgende keer!

Building the Michael-Scott queue is one of those things that quietly changes how you read every other piece of concurrent code afterward. Once you have written the helping step by hand and watched threads repair each other's half-finished updates with no lock anywhere, "lock-free" stops being a scary label and becomes something you can reason about line by line. Try the exercises below, break the thing on purpose to see how it fails, and I will see you in the next one ;-)

Exercises

Add an is_empty(&self) -> bool to the queue that returns whether the dummy's next is null, using a single Acquire load. In a comment, explain why the result can be stale the instant it is returned under concurrency.
Enqueue from three scoped threads (each enqueuing a small range of numbers), join them, then drain the queue on the main thread and assert_eq! that the count matches the total number enqueued.
In a comment, explain why fully concurrent dequeue needs a safe memory reclamation scheme to be sound, and name one crate that provides one.

@scipio