Skip to content

RCU Fundamentals

Introduction

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

The primary goal of RCU is to allow readers to access shared data without blocking while still providing safe object lifetime management.

Unlike traditional locking mechanisms, RCU separates:

  • Object publication
  • Object reclamation

This separation enables highly scalable read-side performance.

Motivation

The Object Lifetime Problem

Consider a shared pointer:

struct object *g_ptr;

Reader:

ptr = g_ptr;
use(ptr);

Writer:

free(g_ptr);
g_ptr = NULL;

The reader may still hold a pointer to memory that has already been reclaimed.

This creates a use-after-free (UAF) condition.

Why Seqlock Is Not Enough

Seqlock guarantees data consistency.

Example:

seq = read_seqbegin();

read shared data

read_seqretry();

Readers can detect concurrent modifications and retry.

However, seqlock does not protect object lifetime.

Example:

ptr = g_ptr;

Even if the pointer value is read consistently, the referenced object may already have been freed.

Therefore:

Seqlock solves consistency.
RCU solves lifetime.

RCU Core Idea

Instead of modifying an object in place:

Old Object
     ↓
Modify

RCU uses:

Old Object
     ↓
Create New Object
     ↓
Publish New Object
     ↓
Wait Grace Period
     ↓
Free Old Object

Readers may continue accessing the old object while new readers observe the new object.

Read-Copy-Update

The name describes the update process.

Read

Readers access shared objects without blocking.

ptr = g_ptr;
use(ptr);

Copy

A new version of the object is created.

new = copy(old);

Update

The shared pointer is updated.

g_ptr = new;

Future readers observe the new object.

Grace Period

Definition

A grace period is the time required for all pre-existing readers to leave their read-side critical sections.

Only after the grace period ends can an old object be safely reclaimed.

Example

Initial state:

g_ptr
  |
  v
Object A

Reader:

ptr = A;

Writer:

Create B
Publish B

State:

g_ptr
  |
  v
Object B

Object A
^^
Reader still uses it

The writer must wait before reclaiming Object A.

End of Grace Period

Once all readers that could reference Object A have exited:

free(A);

becomes safe.

Deferred Reclamation

RCU delays object destruction until it is guaranteed that no reader can access the object.

This process is called deferred reclamation.

Key property:

Publication
!=
Reclamation

Publishing a replacement object does not imply that the old object can be immediately freed.

Mini RCU Model

A conceptual userspace implementation can be represented using a reader counter.

Reader:

reader_count++;
...
reader_count--;

Writer:

publish new object

while (reader_count != 0)
    wait

free(old);

This model captures the core idea of grace periods.

Reader Characteristics

RCU readers:

  • Do not block writers
  • Do not acquire mutexes
  • Do not acquire rwlocks
  • Typically execute extremely quickly

Readers may observe:

  • Old data
  • New data

Readers must never observe:

  • Freed data

Writer Characteristics

Writers:

  • Create replacement objects
  • Publish new versions
  • Wait for grace periods
  • Reclaim old objects

Writer operations are generally more expensive than reader operations.

This trade-off favors read-heavy workloads.

Comparison with Other Synchronization Mechanisms

Mechanism Reader Lockless Consistency Lifetime Protection Reader Retry
Mutex No Yes Yes No
RWLock No Yes Yes No
Seqlock Yes Yes No Yes
RCU Yes No* Yes No

* Readers are not guaranteed to observe the latest version of an object.

Common RCU Use Cases

RCU is commonly used in Linux kernel subsystems that are heavily read-oriented:

  • Process lists
  • Routing tables
  • Dentry cache
  • Inode cache
  • Network namespaces
  • Various kernel lookup structures

These workloads typically have:

Many readers
Few writers

which makes RCU highly effective.

Key Takeaways

  • RCU is primarily a lifetime management mechanism.
  • RCU separates publication from reclamation.
  • Grace periods enable safe object reclamation.
  • Readers may see old objects.
  • Readers must never see reclaimed objects.
  • RCU complements lockless read-side synchronization techniques such as seqlock.
  • RCU is optimized for read-mostly workloads.

Related Labs