Seqlocks: Lock-Free Reads Using an Even/Odd Sequence Counter

The problem: readers that must never block

Consider a value read constantly but written rarely — the classic case is the kernel's monotonic clock, read on every gettimeofday() call across all CPUs. A plain mutex serializes readers against each other, destroying scalability. A reader-writer lock lets readers proceed in parallel, but it has two costs that hurt at scale: (1) each reader must perform an atomic read-modify-write to bump the shared reader count, so readers contend on the same cache line and ping-pong it between cores; and (2) writers can be starved indefinitely if readers keep arriving.

Seqlocks attack this by making the reader path read-only — it touches no shared cache line for writing, so N readers scale perfectly with no inter-reader contention. The cost is shifted onto the rare writer and onto readers that happen to race a writer: those readers simply retry. This is a form of optimistic concurrency control — assume no conflict, verify afterward, redo on failure.

• Readers never block and never starve writers.
• Writers never wait for readers.
• The data must be safely re-readable (idempotent reads) since a read may be discarded.

How it works: the even/odd counter and barriers

A seqlock pairs a sequence counter with a writer spinlock. The counter's parity is the whole protocol: even = stable, odd = write in progress.

Writer (mutually exclusive via the spinlock):

write_seqlock(sl):
  spin_lock(&sl.lock)
  sl.seq++            // even -> odd
  smp_wmb()           // publish odd BEFORE data stores
... writer mutates the protected data ...
write_sequnlock(sl):
  smp_wmb()           // finish data stores BEFORE bumping
  sl.seq++            // odd -> even
  spin_unlock(&sl.lock)

Reader (lock-free, retryable):

do:
  s = read_seqbegin(sl)   // spin while s is odd; smp_rmb()
  ... read the protected data into locals ...
while read_seqretry(sl, s) // smp_rmb(); return s != sl.seq

The two smp_wmb() barriers ensure the odd counter is visible before the data changes and the data changes are visible before the counter returns to even. The reader's smp_rmb() barriers stop the CPU/compiler from reordering the counter reads around the data reads. If the reader saw an odd start value, or the counter moved between begin and retry, a write overlapped its read, so it loops.

Complexity and a worked step trace

Reader: in the uncontended case, O(1) — two counter loads, the data reads, one comparison, zero atomic stores. Under a write rate that overlaps reads with probability p, the expected number of attempts is 1/(1−p), so amortized reads stay O(1) as long as writes are rare (read-mostly). Writer: O(1) beyond the data update, plus contention on the writer spinlock among writers only. Space: one machine word for the counter (plus the spinlock) — effectively O(1) overhead.

Step trace — reader R races writer W updating a (seconds, nanoseconds) timestamp, start seq = 4:

R: read_seqbegin -> s = 4 (even, ok)
R: load seconds = 100
W: write_seqlock -> seq = 5 (odd)
W: seconds = 101; nanos = 0
R: load nanos = 999_000_000   // TORN: 100s + 0.999s
W: write_sequnlock -> seq = 6 (even)
R: read_seqretry: 6 != 4  -> RETRY
R: read_seqbegin -> s = 6 (even)
R: seconds=101, nanos=0
R: read_seqretry: 6 == 6 -> COMMIT

The first pass produced a torn, inconsistent timestamp, but the counter change forces R to discard it. Only the second, consistent snapshot is returned.

Where seqlocks are used in real systems

Seqlocks originated in Linux and remain load-bearing there:

• Timekeeping / gettimeofday, clock_gettime: the canonical use. The vDSO exposes the timekeeper via a seqcount so user space reads the clock with no syscall and no lock. This is where Hemminger first deployed it (Linux 2.5.60, 2003), making the read path effectively lock-free for readers.
• jiffies: jiffies_64 is read under a seqlock on 32-bit systems so a 64-bit tick count is never read torn across its two 32-bit halves.
• dcache / VFS: rename_lock and per-dentry seqcounts support lockless pathname lookup (rcu-walk), retrying if a concurrent rename is detected.
• Networking & stats: u64_stats_sync protects 64-bit counters against torn reads on 32-bit CPUs.

Beyond the kernel, the pattern is reinvented in user space: DPDK ships rte_seqlock, high-frequency-trading and pro-audio engines use seqlock-style single-writer ring buffers to hand snapshots to real-time threads, and game engines use them to pass transform/physics state to render threads without stalls. Hans Boehm's work brought a correct C++-atomics formulation into the standards discussion.

Seqlock vs. rwlock vs. RCU: the tradeoff

All three serve read-mostly workloads, but they trade different things:

• vs. reader-writer lock: A seqlock reader does no shared write, so it scales with zero inter-reader cache-line bouncing and never starves the writer. An rwlock reader blocks writers and mutates lock state. Choose the rwlock when readers must be guaranteed to complete without retry, or when the critical section is large or does non-idempotent work.
• vs. RCU (Read-Copy-Update): RCU readers also never block, never retry, and never write — strictly cheaper on the read side. But RCU works by publishing a new copy and reclaiming the old one after a grace period, which fits pointer-linked structures (lists, trees). Seqlocks update data in place, so they shine for small, fixed-size values (a timestamp, a few counters) where copying and deferred reclamation would be overkill. Often they combine: rcu-walk uses RCU for the list plus a seqcount to catch renames.

Rule of thumb: tiny, read-mostly, in-place data with rare writers → seqlock; pointer-swappable structures → RCU; blocking-tolerant or write-heavy → rwlock/mutex.

Pitfalls, failure modes, and significance

Seqlocks are sharp-edged. The main hazards:

• Reads must be side-effect-free and idempotent. A discarded read may have seen a torn, inconsistent snapshot. Never dereference a pointer, index an array, or divide using values read speculatively before read_seqretry confirms — a torn value can crash. Read into locals; only commit after validation.
• Formal data race in C/C++. A reader may load a field while a writer stores it. Under the C11/C++ memory model that non-atomic conflict is undefined behavior. Correct user-space seqlocks must make the shared fields atomic with memory_order_relaxed loads/stores plus acquire/release on the counter — as Boehm formalized. Tools like C11Tester flag the naive version.
• Writer starves readers under write storms. If writers update continuously, the counter is odd or changing so often that readers retry forever (livelock-like). Seqlocks assume writes are rare.
• Missing/wrong barriers silently break on weakly-ordered CPUs (ARM, POWER) though they may pass on x86-TSO.

Significance: the seqlock is a textbook demonstration that shifting cost from the common path (reads) to the rare path (write-conflicted retries) can beat any mutual-exclusion scheme for read-mostly data — a principle echoed across lock-free programming, MVCC databases, and optimistic concurrency control.

Seqlock vs. common alternatives for read-mostly shared data

Primitive	Reader blocks?	Reader writes memory?	Writer starved by readers?	Best for
Seqlock	No (retries)	No	No	Small, read-mostly data (e.g. a timestamp)
Reader-writer lock (rwlock)	Yes	Yes (updates lock state)	Possible (reader preference)	Larger critical sections, blocking OK
RCU	No	No	No	Pointer-based structures, large/complex data
Plain spinlock/mutex	Yes	Yes	N/A (exclusive)	General mutual exclusion
Seqcount (bare counter)	No (retries)	No	No	Reads guarded by an external lock on writers