Day63 - Seqlock and RCU Motivation¶

Learning Objectives¶

Understand the scalability limitations of reader-writer locks.
Learn the design and operation of sequence locks (seqlock).
Explore lockless reader synchronization.
Understand writer serialization in seqlock.
Learn why RCU was introduced in the Linux kernel.
Review memory ordering requirements in seqlock implementations.

What I Learned¶

Reader-Writer Lock Scalability¶

Reader-writer locks allow multiple concurrent readers and a single writer.

While this improves read throughput compared to a mutex, new readers may still be blocked when a writer is waiting or active.

In highly read-dominated workloads, rwlock contention may become a scalability bottleneck.

Examples:

Routing tables
Process lists
Filesystem metadata
Network connection lookups

Sequence Lock (Seqlock)¶

Seqlock is designed for:

Very frequent reads
Rare writes
Small data snapshots

Core idea:

Readers never acquire a lock.
Writers serialize updates.
Readers validate snapshots using a sequence counter.

Sequence states:

Even = stable data

Odd = writer active

Writer update flow:

seq++

update data

seq++

Reader flow:

start_seq

read data

end_seq

validate

A snapshot is valid when:

start_seq == end_seq

and

sequence is even

Otherwise, the reader retries.

Lockless Readers¶

Readers never modify shared synchronization state.

Unlike rwlock:

rwlock reader:
    reader_count++

seqlock reader:
    read only

This eliminates reader-side contention.

Writer Serialization¶

Multiple writers cannot update the protected data simultaneously.

In the mini seqlock implementation:

Writers acquire ownership using CAS.
Sequence transitions from even to odd.
Other writers wait until the sequence becomes even.

Observed statistics:

Writer busy retries
CAS acquisition failures

This demonstrated that seqlock is lockless only for readers.

Writers must still be serialized.

Memory Ordering¶

The implementation was migrated from implicit sequential consistency to explicit memory ordering.

Key concepts:

Writer begin
    acquire ownership

Writer end
    release updated data

Reader begin
    acquire sequence state

Reader retry
    acquire sequence state

This matches the publish-and-observe synchronization pattern.

RCU Motivation¶

Seqlock solves:

Data consistency

but does not solve:

Object lifetime management

When shared objects can be dynamically allocated and freed, retrying a read cannot prevent use-after-free situations.

This limitation motivates the need for RCU.

Lab Summary¶

Lab1 - Version Counter Demonstration¶

Implemented a simple sequence counter.

Observed:

Odd sequence while writer is active
Even sequence when data is stable

Lab2 - Broken Reader Demonstration¶

Removed snapshot validation.

Observed:

Inconsistent data snapshots
Reader accepting partially updated data

Lab3 - Mini Seqlock Implementation¶

Implemented:

mini_seqlock_read_begin()
mini_seqlock_read_retry()
mini_seqlock_write_begin()
mini_seqlock_write_end()

Validated:

Consistent snapshots
Reader retry behavior

Lab4 - Multi-Writer Contention and Memory Ordering¶

Added:

Multiple readers
Multiple writers
Writer contention statistics

Observed:

Writer busy retries
CAS acquisition failures
Increased reader retries with longer writer critical sections

Key Takeaways¶

Seqlock provides lockless readers.
Readers validate snapshots instead of blocking writers.
Writer critical section length directly affects reader retry rate.
Multiple writers still require serialization.
Seqlock improves read scalability but is not suitable for pointer lifetime management.
RCU extends lockless read techniques to safely manage object lifetimes.

Next Steps¶

Learn RCU fundamentals.
Understand grace periods.
Study rcu_read_lock() and rcu_read_unlock().
Explore deferred reclamation.
Compare Seqlock and RCU design tradeoffs.

Status¶

Completed Day63.

Topics completed:

Seqlock fundamentals
Lockless reader design
Writer serialization
Memory ordering review
RCU motivation