Seqlock, in depth: proving the retry protocol, the ordering it needs, and a version legal under the C++ memory model

The problem a seqlock solves

Consider a clock that a timer interrupt updates a thousand times a second and that every thread reads constantly, or a market-data snapshot of a few prices that one feed handler updates and dozens of strategy threads read. A mutex serialises the readers. A reader-writer lock lets readers run in parallel, but every reader still writes the lock word to register itself, so the cache line holding it bounces between cores on every read. On a many-core machine that bouncing, not the critical section, becomes the cost.

A seqlock removes reader writes entirely. Shared state is a sequence counter plus the protected data. The writer makes the counter odd, writes the data, then makes it even again. A reader records the counter, copies the data, and reads the counter again. If both reads saw the same even value, no write overlapped the copy and the copy is consistent. Otherwise the reader retries. Readers only ever load shared memory, so the counter's cache line stays shared across all their cores until a write happens.

The trade is explicit: readers are optimistic and may waste work, writers never wait for readers, and the scheme only works when the data can be copied cheaply and a half-updated copy can be safely discarded.

The protocol

Written out, the writer and reader are four steps each. The writer must be the only writer; if several threads can write, they first take an ordinary spinlock or mutex among themselves (the Linux seqlock_t is exactly a sequence counter plus such a spinlock).

writer (exclusive):                 reader (any number, concurrently):
  seq = seq + 1      # now odd        repeat:
  data.a = new_a                        s1 = seq
  data.b = new_b                        copy_a = data.a
  seq = seq + 1      # even again       copy_b = data.b
                                        s2 = seq
                                      until s1 is even and s1 == s2
                                      # odd s1: a write was in progress
                                      use (copy_a, copy_b)        # only now

Two facts make this work. The counter is odd exactly while a write is in progress, so a reader that starts during a write knows immediately. And every write moves the counter forward by two, so if any write began or finished between the two counter reads, s1 != s2. The figure shows a reader whose copy straddles a write and is rejected, and a later reader whose copy fits in a quiet window.

Proving it by enumerating every schedule

Arguments like the one above are easy to get subtly wrong, so it is worth checking them mechanically. The model below has a writer performing two complete updates (values 1, then 2) to a pair of fields, and a reader making one attempt. It enumerates every interleaving of the reader's four steps with the writer's eight, and counts how many attempts the reader accepts and how many of those accepted copies are torn (fields from different writes).

from itertools import combinations

def explore(writer, check_odd=True):
    reader = ["s1", "ra", "rb", "s2"]
    n = len(writer) + len(reader)
    total = accepted = torn = 0
    for slots in combinations(range(n), len(reader)):   # where the reader steps go
        mem, reg, wi, ri = {"seq": 0, "a": 0, "b": 0}, {}, 0, 0
        for t in range(n):
            if t in slots:
                op = reader[ri]; ri += 1
                src = "seq" if op in ("s1", "s2") else op[1]
                reg[op] = mem[src]
            else:
                field, value = writer[wi]; wi += 1
                mem[field] = mem["seq"] + 1 if field == "seq" else value
        total += 1
        if reg["s1"] == reg["s2"] and (not check_odd or reg["s1"] % 2 == 0):
            accepted += 1
            torn += reg["ra"] != reg["rb"]
    return total, accepted, torn

bump = ("seq", None)
correct = [bump, ("a", 1), ("b", 1), bump, bump, ("a", 2), ("b", 2), bump]
late    = [("a", 1), ("b", 1), bump, bump, ("a", 2), ("b", 2), bump, bump]
print(explore(correct))                   # (495, 3, 0)
print(explore(correct, check_odd=False))  # (495, 33, 10)
print(explore(late))                      # (495, 31, 10)

There are 495 schedules. The correct protocol accepts the reader in exactly 3 of them (the reader runs entirely before, between or after the two writes) and none of those copies is torn. Drop the odd check and the reader accepts 33 schedules, 10 of them torn: a reader that starts mid-write and finishes before the write ends sees the same odd value twice. Keep the odd check but have the writer bump the counter only after the data, and 31 are accepted with 10 torn, because nothing marks a write as in progress. Each step earns its place.

Notice also how few schedules succeed. With a writer this busy relative to the reader, the reader mostly retries. That is the seqlock's real performance contract: reads are nearly free when writes are rare and degrade into spinning when they are not.

The model is sequentially consistent: every step happens in one global order. That proves the protocol logic, not that a given program is correct on real hardware, which is the next problem.

What real hardware adds: ordering

Compilers and CPUs reorder memory operations that look independent. Three orderings must be preserved. On the writer side, the first counter increment must become visible before any data store, and every data store before the final increment. On the reader side, the first counter load must happen before the data loads, and the data loads before the second counter load. That last one is the easy one to miss: nothing in a load-load sequence naturally stops the CPU from satisfying the second counter read early.

The Linux kernel expresses this with smp_wmb() between writer steps and smp_rmb() between reader steps, hidden inside its API. On x86, stores are not reordered with other stores and loads not with other loads, so those barriers compile to compiler-only fences there; on Arm and POWER they emit real barrier instructions. Portable code should not rely on the x86 behaviour.

Making it legal in C and C++

Under the C11 and C++11 memory models, a seqlock built with plain variables for the data has a data race: the reader's non-atomic loads can run concurrently with the writer's non-atomic stores, and a data race is undefined behaviour even if the reader discards what it read. Hans Boehm analysed this in his 2012 MSPC paper, Can Seqlocks Get Along With Programming Language Memory Models?. The practical fix it recommends is to make each data field an atomic accessed with relaxed ordering, and to use fences for the ordering the protocol needs:

#include <atomic>
#include <cstdint>

struct Quote { std::atomic<int64_t> bid{0}, ask{0}; };

class SeqQuote {
    alignas(64) std::atomic<uint64_t> seq_{0};
    Quote q_;
public:
    void write(int64_t bid, int64_t ask) {           // single writer only
        uint64_t s = seq_.load(std::memory_order_relaxed);
        seq_.store(s + 1, std::memory_order_relaxed);
        std::atomic_thread_fence(std::memory_order_release);
        q_.bid.store(bid, std::memory_order_relaxed);
        q_.ask.store(ask, std::memory_order_relaxed);
        seq_.store(s + 2, std::memory_order_release);
    }
    void read(int64_t& bid, int64_t& ask) const {
        uint64_t s1, s2;
        do {
            s1 = seq_.load(std::memory_order_acquire);
            bid = q_.bid.load(std::memory_order_relaxed);
            ask = q_.ask.load(std::memory_order_relaxed);
            std::atomic_thread_fence(std::memory_order_acquire);
            s2 = seq_.load(std::memory_order_relaxed);
        } while ((s1 & 1) || s1 != s2);
    }
};

The release fence after the first increment keeps the data stores from moving above it; the release store of the final value keeps them from moving below. On the reader side, the acquire load of s1 keeps the data loads after it, and the acquire fence keeps them before the second counter load. Relaxed atomic loads of 8-byte fields cost the same as plain loads on mainstream 64-bit hardware, so the legality is nearly free. For larger blobs, per-field atomics become awkward; Boehm's C++ proposal P1478 for a byte-wise atomic memcpy targets exactly this case, but check your toolchain before relying on it. Rust code faces the same rule: the data must be read through atomics or a primitive designed for racy reads, not through ordinary references.

Seqlocks in the Linux kernel

Linux is the largest production user. seqcount_t is the bare counter for callers that already serialise writers; seqlock_t bundles it with a spinlock. The read side is the idiom below; the write side is write_seqlock() and write_sequnlock().

unsigned int seq;
do {
        seq = read_seqbegin(&lock);
        snapshot = shared;            /* copy only; act on it after the loop */
} while (read_seqretry(&lock, seq));

Timekeeping is the canonical use: the clock state that clock_gettime() reads is published under a sequence counter, and the vDSO lets user space run the reader loop without a system call. The kernel also has a latch variant that keeps two copies of the data and steers readers to the copy not being written, so a reader that interrupts the writer on the same CPU (an NMI handler, for example) is not stuck waiting for a write that cannot finish.

Failure modes

• Acting on an unvalidated copy. Inside the loop the values may be torn. Dividing by a torn denominator, indexing an array with a torn length or following a torn pointer can fault before read_seqretry ever runs. Copy first, validate, then compute.
• Pointers in the protected data. A reader can copy a pointer to an object the writer frees a moment later. The seqlock protects the copy, not what it points to. Use RCU or hazard pointers for pointer-shaped data.
• Two writers without exclusion. Concurrent increments can leave the counter even while a write is in progress, which reopens the torn-read window the model above demonstrated.
• Writer preempted mid-write. Readers spin on an odd counter until it runs again. The kernel disables preemption inside the write section; user-space writers should be short and should never block or allocate there.
• Reader starvation. Frequent or long writes mean readers can retry indefinitely. Count retries; if they climb, the workload no longer suits a seqlock.
• False sharing. Putting the counter on a cache line that other hot data writes to brings back the bouncing the seqlock was meant to remove. Align it.

Operational guidance

• Use a seqlock only when the data is small (a few cache lines), plain values, read far more often than written, and cheap to copy twice.
• Wrap it in a type whose read method returns a validated copy, so callers cannot use the data inside the loop.
• Export a retry counter and alert on the retry ratio; it is the earliest sign the read-write mix has shifted.
• Test on a weakly ordered machine (Arm) as well as x86. ThreadSanitizer will flag the plain-variable version as racy, correctly, but a clean run on the atomic version does not validate the fences; review the ordering by hand.
• Keep writers bounded: no I/O, locks of other subsystems or memory allocation inside the odd window.

Trade-offs

The seqlock sits between a reader-writer lock and RCU. It beats both when the data is a few words, because there is no allocation and no lock word to bounce. It loses to RCU when the data is large or linked, and to a plain mutex when writes are frequent.

What to do next

1. Run the interleaving model above, then add your own broken variant (for example, a reader that skips the second counter read) and predict its counts before you run it.
2. List every shared structure in your service that is read on a hot path and written rarely; mark which ones hold only plain values.
3. For one candidate, write the atomic C++ version, add a retry counter, and benchmark it against your current lock at your real reader count.
4. Review the reader loop for any computation on unvalidated values and move it after the loop.
5. Read the memory model guide and the atomics guide for the acquire and release rules used here.
6. Compare with RCU for pointer-linked data and with the reader-writer lock for long read sections.