RCU (Read-Copy-Update)

Coverage: RCU core mechanisms → grace period → rcu_read_lock/unlock → call_rcu/kfree_rcu → SRCU → Tasks RCU → RCU debugging Kernel version: 2.6 ~ 6.x

Overview

RCU is a synchronization mechanism that follows the principle of "wait until everyone is gone before reclaiming." It allows readers to access shared data without acquiring locks—readers only need rcu_read_lock() and rcu_read_unlock() (these operations have zero overhead in most configurations). Writers copy the data, modify the copy, and then reclaim the old data after all readers have finished accessing the old data.

RCU is the most unique synchronization primitive in Linux, widely used in core data structures such as VFS (dentries), networking (routing tables), file systems (inodes), cgroups, and more.

Core Idea

Reader (lock-free, non-blocking):
  rcu_read_lock();
  p = rcu_dereference(ptr);  // read pointer
  // ... use p ...
  rcu_read_unlock();

Writer:
  old = ptr;
  new = copy(old);           // copy
  modify(new);               // modify copy
  rcu_assign_pointer(ptr, new);  // atomic pointer switch
  synchronize_rcu();         // wait for all readers to leave (blocking)
  // or: call_rcu(&old->rcu, callback);  // asynchronous reclamation

Key constraint: Readers must not sleep between rcu_read_lock/unlock (rcu_read_lock disables preemption; sleeping implies other tasks might be in the critical section, breaking RCU guarantees).

Grace Period

Grace Period = Time window from rcu_assign_pointer until all previously existing readers have completed

CPU 0 (writer):  CPU 1 (reader):        CPU 2 (reader):
  rcu_assign_...                   
  |               rcu_read_lock()       
  |               |--- reader on old data ---|
  |                                          rcu_read_lock()
  |                                          |-- on new data --|
  |               rcu_read_unlock()
  |               // CPU 1 has left
  synchronize_rcu() returns
  // At this point: readers on any CPU no longer see old
  // → Safe to reclaim

Key invariant: During a grace period, all CPUs experience at least one context switch (quiescent state). RCU uses the scheduler's context switch as a signal that "the reader has left"—this is why rcu_read_lock must disable preemption.

Implementation

// kernel/rcu/tree.c
// Main implementation: Tree RCU (scales to thousands of CPUs)
// Organizes CPU quiescent state reports in a tree structure

// rcu_read_lock():
//   preempt_disable()  ← essentially the entire operation in most cases
//   Effectively: disabling preemption tells RCU "I am in a critical section"

// rcu_read_unlock():
//   preempt_enable()   ← if this is the last preempt_disable, RCU records a quiescent state

call_rcu / kfree_rcu

// include/linux/rcupdate.h
// Asynchronous reclamation: register callback, invoked after grace period
call_rcu(&p->rcu_head, my_callback);
// → RCU calls my_callback(p) after the grace period

// Common pattern: freeing objects
kfree_rcu(p, rcu_head);  // equivalent to call_rcu(..., (void(*)(void *))kfree)

synchronize_rcu

// Synchronous wait: blocks until all existing readers have left
synchronize_rcu();  // may sleep for hundreds of milliseconds!
// Cannot be called from interrupt context

RCU Variants

SRCU

// include/linux/srcu.h
// Readers can sleep (suitable for protecting RCU data while holding a mutex)
srcu_read_lock(&ss);
// ... can sleep ...
srcu_read_unlock(&ss, idx);

// Writer:
synchronize_srcu(&ss);
// Higher overhead than synchronize_rcu

Debugging

# RCU statistics
cat /sys/kernel/debug/rcu/rcu_expedited  # whether expedited grace periods are used
cat /sys/kernel/debug/rcu/rcugp          # grace period status

# RCU stall detection (CPU stuck in rcu_read_lock for too long)
#   → Kernel prints "INFO: rcu_sched detected stalls on CPUs/tasks"
#   → Indicates a CPU hasn't left the reader for a long time → possible infinite loop or prolonged preemption disable

# Timeout triggering stall detection
cat /sys/module/rcupdate/parameters/rcu_cpu_stall_timeout

References

• Kernel Documentation: Documentation/RCU/ directory (most comprehensive RCU documentation)
• LWN: "What is RCU?" series, "The RCU API"
• Source Code: kernel/rcu/tree.c, include/linux/rcupdate.h, kernel/rcu/srcutree.c

Keywords: RCU, grace period, rcu_read_lock, call_rcu, kfree_rcu, SRCU, quiescent state, rcu_dereference