Lock-Free Structures II: Seqlocks & Epochs

The seqlock idea in one paragraph. A sequence counter starts even. The writer increments it to an odd value, writes the data and increments it again to the next even value. A reader loads the counter. If it's odd, a write is in progress, so the reader retries. Otherwise it copies the data, loads the counter again, and if the counter hasn't changed, no write overlapped the copy and the snapshot is consistent. If it changed, the reader throws the copy away and retries.

The writer never waits. Readers never write. Each write invalidates the cache line in every reader's cache, so readers take one coherence miss per write (roughly 50–100 ns to pull a line from another core on the same socket, more across sockets) instead of one per read. When the book changes a million times a second and is read ten million times a second, that difference is the whole game.

The price is a set of hard constraints you have to respect:

1. One writer. Two writers would interleave their odd/even steps. If you need several, serialise them with a mutex or a CAS on the counter. Readers are unaffected.
2. The data must be plain bytes. A reader may copy a half-written value before it notices and retries. That's harmless for integers and fatal for pointers: if you dereference a torn pointer before the check, you've already crashed. Seqlock payloads are Copy, fixed-size and pointer-free.
3. Readers can starve. A writer that writes continuously makes every read retry. Top of book changes at most a few million times a second and a read takes nanoseconds, so this is fine. A seqlock over data that's rewritten in a tight loop isn't.
4. The copy must be cheap. Retry probability grows with copy time. A few cache lines is fine, but kilobytes of depth isn't (Day 3 has the answer for those).

There's a trap in the paragraph above. "The reader copies the data while the writer may be writing it" is a data race if the data is ordinary memory, and in Rust (as in C++) a data race is undefined behaviour even if you throw the result away. The compiler may assume non-atomic memory isn't concurrently modified and optimise accordingly. Many real seqlocks copy with ptr::read_volatile plus fences. That works on today's compilers but is UB by the letter of the memory model. A proposed atomic memcpy (RFC 3301, AtomicPerByte) would make it sound, but it isn't stable.

The sound version, from Hans Boehm's analysis, stores the payload in atomics accessed with Relaxed and puts all the ordering in the sequence number and two fences:

// writer (single)
let s = seq.load(Relaxed);
seq.store(s + 1, Relaxed);        // odd: write in progress
fence(Release);                   // (1) orders the odd store before the data stores
data.store(..., Relaxed) /* each word */;
seq.store(s + 2, Release);        // (2) publishes the data

// reader
let s1 = seq.load(Acquire);       // (3) pairs with (2): previous write's data is visible
if s1 is odd { retry }
let copy = data.load(Relaxed) /* each word */;
fence(Acquire);                   // (4) orders the data loads before the re-check
let s2 = seq.load(Relaxed);
if s1 != s2 { retry }

Why it works. Suppose the reader's relaxed copy picked up even one word from a write that started after s1 was read. That word was stored after the writer's release fence (1), and the reader's acquire fence (4) comes after the load that saw it. Fence-to-fence synchronisation then makes the writer's odd store happen-before the reader's s2 load, so s2 is at least that odd value and differs from s1, and the reader retries. Conversely, (2) and (3) form an ordinary release/acquire pair, so a reader that sees an even s1 sees all of that write's data.

On x86, all of this is nearly free. Relaxed and acquire loads are plain movs, release stores are plain movs, and acquire and release fences emit no instruction: they only stop the compiler from reordering. On ARM they become dmb barriers or acquire/release loads and stores. Write the orderings for the model, not for the machine you happen to test on.

Step Reader 1 in each variant: the correct reader throws the mixed copy away, and each broken one returns a crossed book that no write ever produced. Then run all three threads and raise the writer rate until readers start to starve.

The reader's protocol is the classic message-passing pattern: data first, then a flag, with release on the flag store and acquire on the flag load. Step through it below and find the weakest orderings that still forbid the reader seeing the flag without the data.

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

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

use std::sync::atomic::{fence, AtomicU64, Ordering};

/// Top of book: what market-data readers want, consistently.
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
pub struct Tob {
    pub bid_px: u64,
    pub bid_qty: u64,
    pub ask_px: u64,
    pub ask_qty: u64,
}

/// Single-writer seqlock. The payload lives in atomics accessed with
/// Relaxed ordering, so racing reads are not data races (no UB); the
/// sequence number tells the reader whether what it read is consistent.
/// Keep the field names: the harness pokes `seq` to simulate a writer
/// caught mid-update.
pub struct SeqLock {
    seq: AtomicU64,
    words: [AtomicU64; 4],
}

impl SeqLock {
    pub fn new(v: Tob) -> Self {
        todo!()
    }

    /// Single writer only. Never blocks, never waits for readers.
    pub fn write(&self, v: Tob) {
        todo!()
    }

    /// One attempt: Some(snapshot) if no write overlapped the read.
    pub fn try_read(&self) -> Option<Tob> {
        todo!()
    }

    /// Retry until consistent. Readers never write shared memory.
    pub fn read(&self) -> Tob {
        todo!()
    }

    pub fn seq(&self) -> u64 {
        self.seq.load(Ordering::Acquire)
    }
}

Some shared state is too big to copy on every read: top-20 depth for the market-data publisher, the instrument reference table, the risk limits for every account. For those, flip the approach. The writer builds a complete new immutable snapshot off to the side and publishes it with one atomic pointer store:

let fresh = Box::into_raw(Box::new(build_snapshot(&state)));
let old = current.swap(fresh, AcqRel);   // readers now see `fresh`
// ... when can we free `old`?

Readers load(Acquire) the pointer and read through it. There's no retry, no copy and no torn data, because nothing a reader can reach is ever mutated. This is the read side of Linux's RCU (read-copy-update).

The entire difficulty is the last comment. A reader may have loaded old a nanosecond before the swap and still be reading it, so freeing it immediately is a use-after-free. The ways out, and why most don't suit a hot reader:

• Never free, or rotate a fixed pool of N snapshots. That assumes no reader is ever slower than N writes. "Ever" includes a reader descheduled for 10 ms, so it's a time bomb.
• Reference counting (Arc). Every read does an atomic increment and decrement on the snapshot's shared count. That's the RwLock cache-line problem again. There's also a subtle race: load the pointer, then increment the count, and the object can be freed in between. That's why AtomicPtr around an Arc doesn't just work, and why crates like arc-swap exist.
• Hazard pointers (Maged Michael, 2004). Each reader publishes the pointer it's about to use in a per-thread slot, then re-checks that it's still current. A reclaimer frees only objects that no slot mentions. Garbage stays bounded, but every protected load costs a store plus a full fence.
• Epoch-based reclamation. Readers announce when they're reading rather than what, and memory is freed only once every reader has moved past the epoch in which it was unlinked. A read costs almost nothing, and the bookkeeping is amortised across many operations. That's tomorrow.

Epoch-based reclamation (EBR), from Keir Fraser's thesis and implemented in Rust by crossbeam-epoch, has four operations:

• Pin. Before touching shared pointers, a thread copies the global epoch E into its own slot and marks itself active. It may then load and follow pointers freely until it unpins.
• Retire. When the writer unlinks an object (the old snapshot after a swap), it doesn't free it. It appends it to a garbage list tagged with the current epoch.
• Advance. The global epoch may move from E to E+1 only when every active thread's slot says E.
• Collect. Garbage tagged e is freed once the global epoch reaches e+2.

Why two? An object retired in epoch e might be held by a reader pinned in e. A reader still pinned in e−1 could also have loaded it before it was unlinked. Advancing to e+1 requires every active thread to be at e, so e−1 readers are gone. Advancing to e+2 requires every active thread to be at e+1, so e readers are gone too. Anyone pinned now started after the unlink and can't reach the object. Three epochs of garbage in rotation is the whole data structure.

The subtle part is the pin. The reader stores its epoch, then loads the shared pointer. The writer stores the new pointer, then loads the reader slots to decide whether it may advance. That's the store buffering pattern. With anything weaker than sequential consistency, both sides can read the old value: the reader loads the old pointer while the writer doesn't yet see the reader's pin, advances, and frees the snapshot under the reader. Each side needs a SeqCst fence (a full store-load barrier) between its store and its load. Try it below with every combination of orderings.

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

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

That fence is the one real cost of EBR. On x86 it's an mfence or a locked instruction, tens of cycles. crossbeam-epoch uses a locked read-modify-write on x86 because it's cheaper than mfence. So you pin once per batch (a burst of reads or one market-data publish cycle), not once per pointer load.

The failure mode to design against: a thread that stays pinned stops reclamation for everyone. A reader preempted while pinned, or one blocked on I/O inside a pinned section, freezes the global epoch, and garbage grows without bound. Pinned sections must be short, bounded and never block. Hazard pointers don't have this problem (garbage is bounded), which is their main argument. For an exchange, with a fixed set of pinned threads on isolated cores that pin for a few hundred nanoseconds at a time, EBR is the better fit.

compare_exchange checks that a word still holds the value you saw, not that nothing happened to it. If the value went A → B → A while you were preempted, your CAS succeeds against a world that no longer matches your assumptions. That's the ABA problem, and the textbook victim is the Treiber stack (R. Kent Treiber, IBM, 1986):

1. Thread 1 starts a pop. It reads head = A and A.next = B, and is preempted before its CAS.
2. Thread 2 pops A, pops B (and keeps using it), then pushes A back. The head is A again, but A.next is now C.
3. Thread 1 resumes. CAS(head, A → B) succeeds, because the head is A. The stack's head is now B, a node Thread 2 owns. The next pop hands B out twice.

Nothing here needs free. Recycling nodes through a pool is enough, and the week 27 slabs recycle nodes constantly. With real deallocation it's worse: B may have been freed and reused for something else.

The fixes:

• Tagged pointers. Pair the pointer with a counter that every successful CAS increments, and compare both. A→B→A now changes the tag, so the stale CAS fails. Packing a 32-bit node index and a 32-bit tag into one u64 works on every platform. A full 64-bit pointer plus a tag needs a double-width CAS (cmpxchg16b on x86-64), which stable Rust doesn't expose portably. A 32-bit tag can wrap, so a thread stalled for exactly 2^32 operations on that word could still be fooled. That's astronomically unlikely, but know the bound.
• Safe reclamation. If a node can't be reused while any thread might still hold a reference (EBR, hazard pointers), A can't come back while Thread 1 holds it, and the problem disappears with the memory-reuse bug.
• LL/SC. ARM's load-exclusive/store-exclusive fails if the location was written at all, value aside. Rust's compare_exchange is defined by value, though, and compiles to a real CAS instruction on ARMv8.1+, so don't count on it.

In the drill you'll make the interleaving deterministic by splitting pop into prepare (read head and next) and commit (the CAS), so the harness can play two threads by hand. On the untagged stack, the test passes when the bug reproduces. Then the tags make the same script fail safely, and a 4-thread stress run checks that the tagged stack never hands one node to two owners.

use std::sync::atomic::{AtomicU32, AtomicU64, Ordering};

pub const NIL: u32 = u32::MAX;

/// Head word layout: low 32 bits = node index, high 32 bits = tag.
pub fn pack(idx: u32, tag: u32) -> u64 {
    todo!()
}

/// Returns (idx, tag).
pub fn unpack(word: u64) -> (u32, u32) {
    todo!()
}

/// What the first half of a pop observed.
#[derive(Clone, Copy, Debug)]
pub struct PopAttempt {
    pub head: u64,
    pub next: u32,
}

/// Treiber stack over a fixed pool of node indices (nodes are never freed,
/// only recycled, which is exactly how ABA bites).
pub struct Stack {
    head: AtomicU64,
    next: Vec<AtomicU32>,
    tagged: bool, // untagged: the tag is always 0; tagged: +1 on every successful CAS
}

impl Stack {
    /// Empty stack over nodes 0..capacity.
    pub fn new(capacity: usize, tagged: bool) -> Self {
        Stack {
            head: AtomicU64::new(pack(NIL, 0)),
            next: (0..capacity).map(|_| AtomicU32::new(NIL)).collect(),
            tagged,
        }
    }

    /// Push node `idx` (the caller owns it). CAS loop.
    pub fn push(&self, idx: u32) {
        todo!()
    }

    /// First half of pop: read the head and its successor. None if empty.
    pub fn pop_prepare(&self) -> Option<PopAttempt> {
        todo!()
    }

    /// Second half: one CAS from what we saw to the successor.
    /// Some(idx) on success, None if the head changed in between.
    pub fn pop_commit(&self, a: PopAttempt) -> Option<u32> {
        todo!()
    }

    pub fn pop(&self) -> Option<u32> {
        loop {
            let a = self.pop_prepare()?;
            if let Some(i) = self.pop_commit(a) {
                return Some(i);
            }
            std::hint::spin_loop();
        }
    }
}

Before you write code, settle three decisions:

How generic is the seqlock? A SeqLock<T> has to copy T through atomics. The sound approach is to require T: Copy, check that size_of::<T>() is a multiple of 8, and require no padding (padding bytes are uninitialised, and reading them as u64 is UB). Then copy word by word through [AtomicU64; N]. If that feels like too much unsafe for one week, make a concrete TopOfBookLock and say so in your notes. Both are defensible. A generic version that quietly uses read_volatile isn't.

The repo's reference takes the read_volatile route, though not quietly. SeqLock<T: Copy> copies into a MaybeUninit<T>, so a torn copy is never treated as a T, and calls assume_init only after the sequence check passes. Its module docs explain why: this is the mitigation Linux, crossbeam's AtomicCell and the seqlock crate use, and it remains a data race by the letter of the memory model. The atomic-word design above is the sound alternative.

Where does it sit in memory? Put the sequence word and the payload in the same cache line (8 + 32 bytes fits in 64), so a reader takes one miss per write, not two. Align the whole thing to 64 bytes so no neighbouring field shares its line (week 4's false sharing).

Who may pin, and for how long? For the snapshot cell, a fixed set of registered reader threads, each with its own cache-padded epoch slot, is simpler and faster than crossbeam's dynamic registration. The repo sits in between: cell.reader() registers a reader by taking a lock and allocating one cache-padded slot, once per reading thread, and a dropped reader's slot is pruned the next time the writer reclaims. Whichever you choose, write down the maximum pinned-section length and test it.