vault

Sequence Locks and seqlock

13 min read

Sequence Locks and seqlock

A sequence lock (seqlock_t) and its lock-free core, the sequence counter (seqcount_t), implement a reader-retry consistency mechanism for data that is read constantly but written rarely, where readers must never block writers. The kernel header describes it precisely: “a reader-writer consistency mechanism with lockless readers (read-only retry loops), and no writer starvation” (per include/linux/seqlock.h v6.12). A writer bumps a counter on entry and again on exit; an odd counter means “a write is in progress.” A reader samples the counter before reading, reads the data, then re-checks the counter — and if it is odd or has changed, the read was potentially torn and the reader simply loops and tries again. The classic customer is kernel timekeeping: clock_gettime readers fly through the counter while the timer interrupt updates xtime without ever being blocked by them (LWN, Big reader and seqlocks-era discussion notes seqlocks “were originally designed… to control access to system time variables — jiffies_64 and xtime”).

This note pins to the 6.12 long-term-support (LTS) kernel (released 2024-11-17). Parent map: Linux Kernel Synchronization MOC.

Mental Model

A seqlock is the mirror image of a reader-writer lock. A reader-writer lock makes readers pay (they take a lock, which writers must wait for). A seqlock makes the reader do the optimistic work and bear the cost of retrying if it loses a race — the writer never waits for readers at all. The trade you are making: readers become cheap and never block the writer, but readers may have to repeat their work, and they can transiently observe torn, inconsistent data mid-write. The retry is what saves correctness — as long as the reader does not act on the data until the retry confirms the read was clean.

flowchart TB
    subgraph Writer
      W1["seq++ (now ODD)<br/>smp_wmb()"]
      W2["modify protected data"]
      W3["smp_wmb()<br/>seq++ (now EVEN)"]
      W1 --> W2 --> W3
    end
    subgraph Reader
      R1["seq0 = read_seqbegin()<br/>spin while seq is ODD"]
      R2["smp_rmb implicit<br/>read protected data"]
      R3{"read_seqretry():<br/>seq changed<br/>or odd?"}
      R1 --> R2 --> R3
      R3 -->|"yes — torn"| R1
      R3 -->|"no — clean"| R4["use data"]
    end

The two halves of a seqlock. What it shows: the writer brackets its update with two counter increments (entering makes the count odd, leaving makes it even again) separated by write barriers; the reader brackets its read with read_seqbegin() (which spins past any odd count) and read_seqretry(), looping back to the start if the count moved. The insight to take: the reader and writer never wait for each other — the only synchronization is the comparison of two counter samples. The cost of a collision is a wasted read, paid by the reader, never by the writer.

Mechanical Walk-through

The counter and its odd/even discipline

seqcount_t is just an unsigned sequence counter. The write side increments it twice. From include/linux/seqlock.h v6.12:

static inline void do_raw_write_seqcount_begin(seqcount_t *s)
{
	kcsan_nestable_atomic_begin();
	s->sequence++;
	smp_wmb();
}
 
static inline void do_raw_write_seqcount_end(seqcount_t *s)
{
	smp_wmb();
	s->sequence++;
	kcsan_nestable_atomic_end();
}

do_raw_write_seqcount_begin() increments sequence (making it odd if it was even) and then issues smp_wmb() — a write memory barrier — so that the counter increment becomes visible before any of the data stores that follow. do_raw_write_seqcount_end() mirrors it: an smp_wmb() first (so all the data stores are visible before the counter goes even), then the second increment (making it even again). The kcsan_* calls bracket the region for the Kernel Concurrency Sanitizer so it does not flag the intentional data races. The doc spells out the invariant: “After starting the critical section the sequence count is odd and indicates to the readers that an update is in progress. At the end of the write side critical section the sequence count becomes even again which lets readers make progress” (per Documentation/locking/seqlock.rst v6.12).

The reader’s begin: spin past an in-progress write

#define __read_seqcount_begin(s)					\
({									\
	unsigned __seq;							\
									\
	while ((__seq = seqprop_sequence(s)) & 1)			\
		cpu_relax();						\
									\
	kcsan_atomic_next(KCSAN_SEQLOCK_REGION_MAX);			\
	__seq;								\
})

read_seqcount_begin() reads the sequence into __seq and loops with cpu_relax() (a pause hint) while the low bit is set — & 1 is the odd test. So a reader that arrives mid-write does not read torn data; it waits for the count to go even, samples it, and returns that even snapshot. (The raw_ form skips a lockdep check; read_seqcount_begin() adds seqcount_lockdep_reader_access() for validation.)

The reader’s retry and its memory barrier

static inline int do_read_seqcount_retry(const seqcount_t *s, unsigned start)
{
	smp_rmb();
	return do___read_seqcount_retry(s, start);
}

read_seqcount_retry(s, start) issues smp_rmb() — a read memory barrier — and then compares the current sequence against start (the value captured by read_seqcount_begin). It returns true (retry needed) if they differ. The barrier ordering is the entire correctness argument: the smp_wmb() on the writer side and the smp_rmb() on the reader side together guarantee that if the reader’s two counter samples match, then no write store could have landed in the middle of the reader’s data loads without also changing the counter. The header is explicit that the bare __read_seqcount_retry() omits this barrier — “Callers should ensure that smp_rmb() or equivalent ordering is provided before actually loading any of the variables that are to be protected in this critical section” (per v6.12 header). See Memory Barriers in the Linux Kernel for smp_wmb/smp_rmb semantics.

seqlock_t = seqcount_t + a spinlock for writers

A bare seqcount_t does not serialize writers against each other — it only coordinates readers vs. a single writer. seqlock_t bundles a spinlock to serialize multiple writers:

static inline void write_seqlock(seqlock_t *sl)
{
	spin_lock(&sl->lock);
	do_write_seqcount_begin(&sl->seqcount.seqcount);
}
static inline void write_sequnlock(seqlock_t *sl)
{
	do_write_seqcount_end(&sl->seqcount.seqcount);
	spin_unlock(&sl->lock);
}

write_seqlock() takes the embedded spinlock and opens the seqcount write section; write_sequnlock() closes both. The doc notes this “implicitly acquires the spinlock_t embedded inside that sequential lock. All seqlock_t write side sections are thus automatically serialized and non-preemptible” (per v6.12 header). If readers can run from hardirq/softirq context, the writer must use write_seqlock_irqsave/_bh so it cannot be interrupted by a reader on the same CPU and self-deadlock-style stall it.

The associated-lock seqcount variants

A plain seqcount_t cannot tell lockdep which lock serializes its writers, so the kernel offers typed variants — seqcount_spinlock_t, seqcount_raw_spinlock_t, seqcount_rwlock_t, seqcount_mutex_t, seqcount_ww_mutex_t — that “associate the lock used for writer serialization at initialization time, which enables lockdep to validate that the write side critical sections are properly serialized” (per seqlock.rst). For lock types that do not implicitly disable preemption, the write-side helpers disable it for you (a preempted writer that left the counter odd would stall every reader indefinitely).

The Latch Variant — Lock-Free Single-Writer Reads

The ordinary seqlock has a structural limit: a reader that interrupts a writer mid-update spins (or retries) until the writer finishes. If the “reader” is a Non-Maskable Interrupt (NMI) handler that interrupted the writer on the same CPU, that is a deadlock — the writer can never finish because the NMI will never yield. The latch sequence counter (seqcount_latch_t) solves this with multi-version concurrency control (MVCC): keep two copies of the data and use the counter’s low bit to point readers at whichever copy is currently not being written.

typedef struct {
	seqcount_t seqcount;
} seqcount_latch_t;
 
static __always_inline unsigned raw_read_seqcount_latch(const seqcount_latch_t *s)
{
	return READ_ONCE(s->seqcount.sequence);
}
 
static __always_inline int
raw_read_seqcount_latch_retry(const seqcount_latch_t *s, unsigned start)
{
	smp_rmb();
	return unlikely(READ_ONCE(s->seqcount.sequence) != start);
}
 
static inline void raw_write_seqcount_latch(seqcount_latch_t *s)
{
	smp_wmb();	/* prior stores before incrementing "sequence" */
	s->seqcount.sequence++;
	smp_wmb();      /* increment "sequence" before following stores */
}

The writer pattern is: raw_write_seqcount_latch() (flip the counter so readers switch to the other copy), modify(data[0]), raw_write_seqcount_latch() again, modify(data[1]). The reader picks its copy with idx = seq & 0x01 and validates with raw_read_seqcount_latch_retry(). The documentation’s worked example shows exactly this shape — reader side seq = raw_read_seqcount_latch(&latch->seq); idx = seq & 0x01; entry = data_query(latch->data[idx], ...); } while (raw_read_seqcount_latch_retry(&latch->seq, seq)); and writer side incrementing latch->seq.sequence++ between modify(latch->data[0], ...) and modify(latch->data[1], ...) (per seqlock.rst v6.12). The doc states the latch is for “when the write side sections cannot be protected from interruption by readers. This is typically the case when the read side can be invoked from NMI handlers.” The key property: at every instant one of the two copies is fully consistent, so an NMI reader that lands mid-update simply reads the other copy and never spins.

The Flagship User: Kernel Timekeeping

Seqlocks exist largely because of timekeeping. clock_gettime() and friends are among the hottest read paths in the kernel, called from every CPU constantly; the wall-clock and monotonic time bases are updated rarely, by the timer interrupt. Blocking those readers behind a lock — or letting them block the timer-interrupt writer — would be a disaster. The timekeeping core wraps the timekeeper in a seqcount (per kernel/time/timekeeping.c v6.12):

static struct {
	seqcount_raw_spinlock_t	seq;
	struct timekeeper	timekeeper;
} tk_core ____cacheline_aligned = {
	.seq = SEQCNT_RAW_SPINLOCK_ZERO(tk_core.seq, &timekeeper_lock),
};

The ____cacheline_aligned and the comment that “the most important data for readout fits into a single 64 byte cache line” are deliberate: a reader touching one cache line and a counter is the entire cost. A standard reader loops:

do {
	seq = read_seqcount_begin(&tk_core.seq);
	base = tk->tkr_mono.base;
	nsecs = timekeeping_get_ns(&tk->tkr_mono);
} while (read_seqcount_retry(&tk_core.seq, seq));

For the fast, NMI-safe paths (ktime_get_mono_fast_ns() and similar, used where even taking the standard seqcount could deadlock against an interrupted update), timekeeping uses the latch variant over a two-element array:

static void update_fast_timekeeper(const struct tk_read_base *tkr,
				   struct tk_fast *tkf)
{
	raw_write_seqcount_latch(&tkf->seq);
	memcpy(base, tkr, sizeof(*base));
	raw_write_seqcount_latch(&tkf->seq);
	memcpy(base + 1, base, sizeof(*base));
}

and the reader: seq = raw_read_seqcount_latch(&tkf->seq); tkr = tkf->base + (seq & 0x01); now = __timekeeping_get_ns(tkr); } while (raw_read_seqcount_latch_retry(&tkf->seq, seq));. The design rationale, paraphrasing the kernel’s own comment: if an NMI hits the update of base[0], the reader will use base[1], which is still consistent. This is why a process can call clock_gettime(CLOCK_MONOTONIC) from anywhere — even an NMI context profiler — and never block, and never block the timer interrupt that writes the time. See Linux Time and Timers MOC for the timekeeping subsystem.

Reducing Reader Starvation: read_seqbegin_or_lock

Under a sustained spike of writes, a pure-lockless reader could retry forever. The read_seqbegin_or_lock() pattern starts optimistic and promotes itself to taking the lock if it keeps losing:

int seq = 0;
do {
	read_seqbegin_or_lock(&foo_seqlock, &seq);
	/* read-side critical section */
} while (need_seqretry(&foo_seqlock, seq));
done_seqretry(&foo_seqlock, seq);

The first iteration reads locklessly; if it must retry, the next iteration acquires the writer spinlock (forcing the reader to wait but then guaranteeing a clean read). The doc explains this exists “to avoid lockless readers starvation (too much retry loops) in case of a sharp spike in write activity” (per seqlock.rst).

Failure Modes and the Hard Caveat

Acting on torn data — the cardinal sin. A reader will sometimes load half-old, half-new, or entirely garbage values mid-write. That is by design; the retry is what filters it out. The absolute rule: do nothing with the data until read_seqretry() confirms the read was clean. Concretely, never dereference a pointer read inside a seqlock critical section before the retry succeeds — the documentation is blunt: “This mechanism cannot be used if the protected data contains pointers, as the writer can invalidate a pointer that the reader is following” (per seqlock.rst v6.12). A torn pointer points anywhere; following it crashes before you ever reach the retry. Seqlocks protect values you copy out and validate, not structures you traverse. For pointer-following read-mostly structures, use RCU instead.

Writer that leaves the counter odd. If a writer is preempted or sleeps while the counter is odd, every reader spins or retries until it resumes. This is why write sides are non-preemptible (the typed variants disable preemption) and why you never sleep inside a seqcount write section.

Reader/writer on the same CPU via interrupt. If a reader runs in IRQ context and the writer can be interrupted by that IRQ, the interrupted writer (counter odd) and the IRQ reader (spinning for even) deadlock. The fix is write_seqlock_irqsave/_bh on the writer, or the latch variant for NMI readers.

Forgetting the barrier in the raw path. Using __read_seqcount_retry() (no smp_rmb()) without supplying your own barrier lets the compiler/CPU reorder the data loads after the counter re-check, defeating the whole scheme. Use the non-__ forms unless you know exactly why you need the bare one.

Alternatives and When to Choose Them

  • Reader-writer spinlock / rw_semaphore. Symmetric: readers and writers both take the lock; readers block writers. Use when readers must see a stable snapshot they will traverse (pointers), or when readers vastly outnumber writers but cannot tolerate retry. A seqlock wins when reads dominate, writes are rare and short, and readers can cheaply copy-and-retry.
  • RCU. The other read-mostly champion. RCU readers never retry and never spin — they read a stable published version with effectively zero overhead — and RCU can follow pointers safely (the publish/subscribe pattern with the grace period guaranteeing the old version stays valid). Choose RCU for pointer-rich linked structures (lists, trees, the dentry cache); choose seqlock for small, copy-out scalar/struct data (a timestamp, a set of counters) where keeping multiple versions around (RCU’s cost) is overkill. They are complementary, not interchangeable.
  • Plain spinlock. If reads are not actually dominant, a simple lock is cheaper than the retry machinery and far easier to reason about. Reach for a seqlock only when you have measured a read-mostly hot path.

Production Notes

Beyond timekeeping, seqlocks appear wherever a small piece of read-mostly state sits on a hot path: filesystem mount/statfs data, some cputime accounting, and per-task scheduler statistics have used seqcounts so that a frequent reader never serializes against the rare updater. The historical lineage is worth noting — LWN’s early coverage records that seqlocks “were originally designed… to control access to system time variables — jiffies_64 and xtime. Those variables are constantly being read, so that action should be fast” (LWN). The modern seqcount_LOCKNAME_t family (associating an explicit serialization lock for lockdep) and the seqcount_latch_t formalization were comparatively recent consolidations of patterns that timekeeping had open-coded for years.

Uncertain

Verify: the exact current set of in-kernel seqlock users beyond timekeeping in v6.12 (the filesystem/statfs, cputime, and per-task scheduler-stats examples above are stated from general kernel knowledge, not traced to specific v6.12 call sites in this task). Reason: not directly grepped against the v6.12 tree here. To resolve: git grep -l seqcount / git grep read_seqbegin against the v6.12 source and confirm the named subsystems still use it.

Uncertain

Verify: the precise verbatim text of the long latch-technique comment block above raw_write_seqcount_latch() in v6.12 seqlock.h. Reason: the fetch tool refused to reproduce the full multi-line comment due to its length, so the latch worked-example here is reconstructed from the shorter seqlock.rst example plus the update_fast_timekeeper() usage rather than quoted whole from the header comment. To resolve: read the header comment block directly in the v6.12 source to confirm the latch_modify/latch_query example matches.

See Also

Graph View

Backlinks