Seqlocks: Optimistic Reading Without Blocking the Writer

A reader-writer lock charges every reader for the privilege of excluding writers: a counter increment on entry, a decrement on exit, and a shared cache line that moves with each one. A seqlock charges the reader nothing on the fast path. Readers do not register at all. They read a version number, copy the data, and read the version again; if the number changed or is odd, the copy is discarded and the whole read is repeated. Writers increment the version, modify the data, and increment again. No reader can block a writer, and no writer can block a reader.

The version number is the entire protocol

The counter has two meanings packed into one integer. An odd value means a writer is in the middle of an update. An even value is a generation number. A writer’s critical section is bounded by two increments, so the sequence of values a reader can observe is even, odd, even, and a successful read requires that both observations be equal and even.

#include <stdatomic.h>

struct config {
    unsigned generation;        /* even: stable, odd: write in progress */
    int a, b, c;
};

static struct config cfg;
static atomic_uint seq;         /* the seqlock counter, separate from data */

static void writer_update(int a, int b, int c)
{
    unsigned g = atomic_load_explicit(&seq, memory_order_relaxed);
    atomic_store_explicit(&seq, g + 1, memory_order_relaxed);   /* odd: begin */
    atomic_thread_fence(memory_order_release);

    cfg.a = a;
    cfg.b = b;
    cfg.c = c;
    cfg.generation = g + 2;

    atomic_thread_fence(memory_order_release);
    atomic_store_explicit(&seq, g + 2, memory_order_relaxed);   /* even: end */
}

static int reader_copy(struct config *out)
{
    for (;;) {
        unsigned before = atomic_load_explicit(&seq, memory_order_acquire);
        if (before & 1)
            continue;                       /* writer inside, do not copy */

        *out = cfg;                         /* plain, possibly torn copy */

        atomic_thread_fence(memory_order_acquire);
        unsigned after = atomic_load_explicit(&seq, memory_order_relaxed);
        if (before == after)
            return 1;
        /* otherwise retry: the copy may mix two versions */
    }
}

The writer does not need to hold a lock at all if it is the only writer. Serializing writers requires a separate mutex around the whole update, which is why the Linux implementation is documented as two pieces: a sequence counter that orders readers against writers, and a spinlock that orders writers against each other. The counter alone gives readers a consistency check, not mutual exclusion among writers.

The reader’s copy is deliberately unsynchronized. A plain struct assignment compiles to a sequence of loads that can interleave with the writer’s stores, producing a value that never existed, a mixture of the old and new fields. That is acceptable because the version check will reject it. It is not acceptable to use the copied value before the check succeeds, and it is not acceptable to copy a pointer and dereference it during the copy, because the pointer may be freed between the two version reads.

It should be said plainly that this pattern is a data race under the C11 and C++11 memory models, which give no meaning to a non-atomic access that overlaps a write. The kernel implementations work because the load of each field is written so that the compiler cannot assume the value is stable: READ_ONCE forbids it from reloading, splitting, or hoisting the access, and the translation unit is compiled with a compiler whose behaviour at that point is known rather than with an arbitrary one. That is an arrangement between the code and the compiler, not a guarantee of the language. A user-space seqlock written with plain fields and relying on the standard’s atomics alone is relying on behaviour the standard does not define, and a compiler is entitled to break it — an optimiser that sees the copy result compared only by a check on a separate counter may simply drop the copy entirely and call the read consistent, because in a race-free execution the copy could not have changed. The portable construction makes the payload an array of relaxed atomic words and copies it word by word; the copy may still mix two generations, and the version comparison still rejects it, but no access is undefined and the compiler must perform every load in the order the fences require.

Two further constraints follow from that construction. The payload must be trivially copyable, since a copy that runs a constructor or a virtual dispatch is doing more than the protocol can protect. And the writer must not reuse a buffer that a reader may still be copying, which is why the double-buffer form — a writer filling one copy while readers use the other — needs the reader’s generation to be re-checked after the copy and the buffers to be swapped only on the writer’s own critical path; a single buffer that the writer overwrites in place is relying on the reader finishing before the next update starts, which is exactly what the protocol does not provide.

Why the fences sit where they do

The naive argument is that a reader who sees the same even version before and after the copy must have read a consistent snapshot. That argument is false on a weakly ordered machine without fences, and the reason is the store buffer again.

Suppose the writer stores the new fields and then stores the final even version. The reader on another core can observe the final version before it observes the field stores, because the field stores are still queued. The reader then loads the fields, which are served from its own cache in the old state, and sees the same version before and after. The check passes and the data is stale. The release fence after the final version store and the fences on the reader side prevent exactly this. The writer’s release fence orders the field stores before the counter store. On the reader side, the acquire on the first counter load keeps the field loads from being hoisted above it, and the acquire fence before the second counter load keeps that load from being hoisted above the field loads; the pair is what makes the version number meaningful.

On x86 the store buffer drains in order, so a release fence between the data and the final counter is not strictly required for the fields to become visible in order. The reader still needs the acquire fence, because x86 permits a load to be satisfied before an older store to a different address has drained, and more importantly the compiler may move the field loads above the counter load. The release fence on the writer’s side buys a different guarantee there: on any machine it stops the compiler from sinking the field stores below the counter store, and on hardware it forbids a later load from being satisfied ahead of those stores. The second half matters because a writer typically does more than store fields; if it reads anything after publishing the new version — a statistic, a pointer, a lock word — that load could otherwise execute before the field stores drain, and the values it returns would belong to a state the counter has already declared complete. Arm needs both fences and gets them as DMB ISH or as acquire/release variants of the accesses.

There is a further subtlety about the first version read. It must be an acquire operation, not a relaxed load, or the field loads may be hoisted above it. Many implementations rely on the fact that the field loads are data-dependent on nothing, which is precisely why the barrier is explicit rather than implied.

The data types that cannot survive a retry

The protocol’s correctness depends on the reader being able to detect a torn read. That works when the reader copies a bounded, self-contained value. It fails in three situations that are common enough to be worth naming.

A copy that follows a pointer is not bounded. If the reader dereferences a pointer inside the protected structure and walks a linked list, a writer that removes a node can free it while the reader is walking, and the retry does not help because the reader has already touched freed memory. The version check detects an inconsistent snapshot after the fact; it cannot prevent a use-after-free during the copy.

A copy that is too large is unbounded in time. The reader’s window between the two version reads is the duration of the copy, and the longer that window, the more likely a writer completes inside it. For a structure of a few hundred bytes the retry is rare; for a structure of a megabyte the reader can livelock, retrying indefinitely while the writer keeps updating. The failure is not incorrectness but an unbounded delay, and it is not fixable by the lock, only by shrinking the copied region or by changing the mechanism.

A copy of a value that the reader cannot re-read safely is unbounded in another way. If the read has side effects, such as consuming from a device queue, the retry repeats them. The protocol assumes the read is idempotent and repeatable.

There is also a constraint on the writer’s side: the sequence counter must not be the same word as any field the reader copies. If the counter and a data field share a cache line, the writer’s increment invalidates the line for every reader and the scheme loses its traffic advantage. Implementations place the counter in its own cache line for this reason, and the reader’s copies touch only the data lines.

The variants that extend the idea

Several refinements exist because the basic protocol has a fixed cost profile.

A sequence counter without a writer lock, used where a single writer is guaranteed by construction, is the common case in kernel code: one thread updates a timestamp or a statistics block while many read it. The Linux API separates seqcount_t, which is the bare counter, from seqlock_t, which adds the writer spinlock, so a caller can choose.

Reader retry can be bounded by falling back to a locked read after a small number of failures. This converts an unbounded delay into a bounded one at the cost of a slow path that blocks. The bound is arbitrary, and choosing it requires knowing the writer’s update rate.

A version counter can also protect a structure whose fields are individually atomic, which allows a reader to detect a change without copying the whole thing. The pattern is used for timekeeping: a clock reading is composed from a base and an offset that are updated together, and the reader’s consistency check is a version comparison rather than a data copy. The Linux timekeeper uses this shape.

The most important extension is not a variant of the seqlock but a replacement for its read side. Read-copy-update removes the reader’s retry entirely by never modifying data in place: a writer builds a new version and publishes it with a single pointer store, and readers who already hold the old pointer continue to use it until they finish. The version check disappears, and so does the torn-copy problem, at the cost of deferred reclamation. That mechanism is described in read-copy-update and grace periods.

Where the primitive belongs

The seqlock is the right tool when writes are rare, reads are frequent, the protected value is small and self-contained, and readers can tolerate an occasional repeat. It is the wrong tool when any of those conditions fails, and the failure is usually invisible in testing because retries are rare until the machine is loaded.

Its diagnostic signature under load is a rise in reader CPU time with no corresponding rise in work completed, since the retries consume cycles without producing results. A reader-writer lock under the same load shows the opposite signature: readers spend their time waiting on the counter line rather than retrying, as described in reader-writer locks and their scaling limits. Neither is free; the choice is which resource to spend.

A seqlock also has an interaction with preemption worth noting. A reader that is preempted in the middle of its copy, after the first version read, resumes later and finds the version changed. It retries, correctly, but the retry may happen after several more updates. On a machine with many threads and few cores, the probability of a preemption inside the window rises, and the effective read cost rises with it. A design that is fast on an unloaded machine can be slower than a mutex on an oversubscribed one, for the same reason that optimistic concurrency in general degrades under contention.

For the atomic primitives that make the counter transitions safe, see atomic read-modify-write.