Day63 - Seqlock and RCU Motivation¶

Overview¶

This lab explores the motivation behind seqlock and RCU by implementing a minimal userspace seqlock.

The experiments demonstrate:

Sequence counter design
Reader snapshot validation
Lockless reader synchronization
Writer serialization
Memory ordering considerations
Why RCU is needed beyond seqlock

Lab1 - Version Counter Demonstration¶

Objective¶

Understand the basic sequence counter mechanism.

Shared Data¶

struct shared_data {
    atomic_uint seq;
    uint32_t x;
    uint32_t y;
};

Writer Flow¶

seq++

update x

update y

seq++

Reader Flow¶

start_seq

read x
read y

end_seq

validate

Observation¶

Readers never accepted inconsistent data when sequence validation was enabled.

Lab2 - Broken Reader Demonstration¶

Objective¶

Observe what happens when snapshot validation is removed.

Reader Logic¶

Snapshot validation was intentionally removed.

Observation¶

The reader frequently observed partially updated data.

Example:

x = 1
y = 0

This demonstrated that the sequence counter alone does not protect data consistency.

Reader-side validation is required.

Lab3 - Mini Seqlock Implementation¶

Objective¶

Implement a minimal seqlock abstraction.

Implemented APIs¶

int mini_seqlock_init(...);

unsigned int mini_seqlock_read_begin(...);

bool mini_seqlock_read_retry(...);

int mini_seqlock_write_begin(...);

int mini_seqlock_write_end(...);

Reader Algorithm¶

read_begin()

read shared data

read_retry()

retry if necessary

Writer Algorithm¶

wait for even sequence

CAS:
    even -> odd

update data

odd -> even

Observation¶

Readers successfully obtained consistent snapshots without acquiring locks.

Lab4 - Multi-Writer Contention and Memory Ordering¶

Objective¶

Observe writer serialization and reader retry behavior under contention.

Test Configuration¶

Readers : 3
Writers : 2
Loops   : 500

Writer Statistics¶

Added:

writer_busy_count
writer_cas_fail_count

Definitions:

writer_busy_count
    Writer observed an active writer
    (sequence was odd)

writer_cas_fail_count
    CAS acquisition failed
    due to concurrent writer competition

Example Result¶

[MAIN] seq=2004
w_busy=659905
w_cas_fail=34

Analysis¶

Sequence value:

2 writers

500 updates each

1 final stop update each

Total transactions:

(500 + 1) * 2 = 1002

Sequence increments twice per transaction

1002 * 2 = 2004

Writer contention was successfully observed.

Reader retries increased significantly when writer critical sections were extended using:

usleep(1);

inside the write section.

Memory Ordering Discussion¶

Initial Version¶

The implementation used implicit sequential consistency.

atomic_load(...)
atomic_fetch_add(...)
atomic_compare_exchange_weak(...)

Explicit Version¶

The implementation was later migrated to:

Reader:
    memory_order_acquire

Writer Begin:
    memory_order_acquire

Writer End:
    memory_order_release

Key Insight¶

Writer begin acquires ownership.

Writer end publishes updated data.

Reader acquire operations observe published state.

Seqlock Limitations¶

Seqlock guarantees:

Consistent snapshots

Seqlock does not guarantee:

Object lifetime safety

Example:

Reader:
    ptr = global_ptr

Writer:
    free(ptr)

Retry cannot recover from use-after-free situations.

This limitation motivates the introduction of RCU.

Conclusion¶

This lab demonstrated:

Version counter synchronization
Lockless readers
Reader retry validation
Writer serialization
Multi-writer contention
Memory ordering requirements
RCU motivation

The mini seqlock implementation successfully reproduced the fundamental behavior of Linux kernel sequence locks.