RCU¶

Overview¶

Read-Copy-Update (RCU) is a synchronization mechanism optimized for read-mostly workloads.

Unlike traditional locking primitives, RCU allows readers to access shared objects without acquiring locks.

RCU focuses on safe object publication and object lifetime management.

It is widely used throughout the Linux kernel in performance-critical read paths.

Motivation¶

Traditional synchronization mechanisms focus on protecting shared data.

Examples:

Mutex
RWLock
Seqlock

These mechanisms ensure data consistency.

However, another problem exists:

Object Lifetime Management

Consider:

struct device_entry *dev;

A writer may replace:

dev = new_dev;

while readers are still accessing:

old_dev

The challenge is determining when it is safe to free the old object.

Core Idea¶

RCU separates object updates into three phases:

Publication
        ↓
Grace Period
        ↓
Reclamation

Publication¶

Writers publish a new object.

Conceptually:

Old Object
        ↓
Publish New Object
        ↓
New Readers See New Object

Existing readers may still access the old object.

Grace Period¶

A grace period allows existing readers to complete.

During this period:

Old Readers
Continue Using Old Object

while:

New Readers
Use New Object

Reclamation¶

After the grace period:

All Old Readers Completed

the old object can be safely reclaimed.

free(old_object)

Reader Side¶

Readers enter an RCU read-side critical section.

Typical pattern:

rcu_read_lock();

obj = rcu_dereference(ptr);

/* access object */

rcu_read_unlock();

Readers do not block each other.

Readers do not acquire traditional locks.

This provides extremely low reader overhead.

Writer Side¶

Writers allocate a new object.

Example:

Copy
Modify
Publish

Typical flow:

new = kmalloc(...);

copy_old_data(new);

update_new_data(new);

rcu_assign_pointer(ptr, new);

The old object remains valid until the grace period completes.

Key RCU APIs¶

rcu_read_lock()¶

Marks the beginning of a read-side critical section.

rcu_read_lock();

rcu_read_unlock()¶

Marks the end of a read-side critical section.

rcu_read_unlock();

rcu_dereference()¶

Safely obtains a published pointer.

obj = rcu_dereference(ptr);

Provides the required memory-ordering guarantees for readers.

rcu_assign_pointer()¶

Publishes a new object.

rcu_assign_pointer(ptr, new_obj);

Provides the required memory-ordering guarantees for writers.

synchronize_rcu()¶

Waits for a grace period to complete.

synchronize_rcu();

After it returns:

All previous readers have completed.

call_rcu()¶

Schedules deferred reclamation.

call_rcu(&obj->rcu, free_callback);

The callback executes after the grace period completes.

This avoids blocking the writer.

synchronize_rcu() vs call_rcu()¶

synchronize_rcu()¶

Writer waits.

Example:

rcu_assign_pointer(ptr, new);

synchronize_rcu();

free(old);

call_rcu()¶

Writer continues immediately.

Example:

rcu_assign_pointer(ptr, new);

call_rcu(&old->rcu, free_callback);

The callback performs reclamation later.

Why Not Use RWLock?¶

RWLock allows multiple readers.

However:

Readers still acquire locks.

Every reader performs synchronization operations.

Reader overhead remains.

Why Not Use Seqlock?¶

Seqlock provides:

Consistent Snapshot

but does not solve:

Object Lifetime Management

Example:

Pointer Publication
Object Reclamation

remain unsafe with seqlock alone.

Quiescent State¶

A quiescent state (QS) represents a point where a CPU can no longer hold an old reader from the beginning of the current grace period.

Conceptually:

Grace Period Start
        ↓
CPU Progress
        ↓
Quiescent State

Once every relevant CPU reaches a quiescent state:

Grace Period Complete

Reader Counting vs Progress Tracking¶

Educational Mini RCU:

Count Readers
        ↓
reader_count == 0
        ↓
Grace Period Complete

Linux RCU:

Track CPU Progress
        ↓
Quiescent State Detection
        ↓
Grace Period Complete

Linux focuses on CPU progress rather than maintaining a global reader counter.

Tree RCU¶

Modern systems may contain:

64 CPUs
128 CPUs
256 CPUs

Tracking every CPU individually becomes expensive.

Linux aggregates CPU state hierarchically.

Conceptually:

                Root
               /    \
              /      \
          GroupA    GroupB
           /  \      /  \
        CPU0 CPU1 CPU2 CPU3

This design is known as Tree RCU.

Tree RCU enables scalable grace period detection on large systems.

Typical Use Cases¶

Routing Tables¶

Network stack

Device Lookup Tables¶

Kernel subsystems

Process and File Tables¶

Kernel core infrastructure

Read-Mostly Configuration Data¶

Rare updates
Frequent reads

Comparison¶

Primitive	Main Goal
Mutex	Mutual exclusion
RWLock	Multiple readers
Seqlock	Consistent snapshot
RCU	Object lifetime management

Summary¶

RCU is a synchronization mechanism designed for read-mostly workloads.

Its primary goal is safe object lifetime management with minimal reader overhead.

RCU achieves this through:

Publication
Grace Period
Reclamation

Linux extends this design using:

Quiescent State Tracking
Tree RCU

to provide scalable synchronization on modern multi-core systems.