The Journey to RCU

RCU

Causality

Read Copy Update HOWTO

Structure

What is RCU?
What is RCU? – “Read, Copy, Update”
A Tour Through RCU’s Requirements

History

As of March 2013: Simplifying RCU
RCU dissertation.2004.07

Classic RCU

commit c17ef45342cc033fdf7bdd5b28615e0090f8d2e7
Author: Paul E. McKenney paulmck@linux.vnet.ibm.com
Date: Tue Jun 23 17:12:47 2009 -0700
rcu: Remove Classic RCU
Brief Overview of Classic RCU Implementation
Linux2.6.11版本:classic RCU的实现

Grace period

Documentation/RCU/rcu.txt
URCU: any period of time during which each reader thread resides in at least one quiescent state is called a grace period.
Start a New Grace Period
… after each CPU has passed through at least one quiescent state, the RCU grace period ends.

Quiescent state

… after all the CPUs in the system have gone through at least one “quiescent” state (such as context switch, idle loop, or user code)
URCU: Any line of code not in an RCU read-side critical section is termed a quiescent state
The rcu and rcu_bh flavors of RCU have different sets of quiescent states.
Using Quiescent States to Reclaim Memory

granularity of waiting

The great advantage of RCU … without having to explicitly track each and every one of them
In RCU’s case, the things waited on are called “RCU read-side critical sections”. ditto.

Preemptiable RCU

The 1st: Read-copy-update for realtime Papper
The design of preemptible read-copy-update
The RCU implementation for the -rt patchset is unusual in that it permits read-side critical sections to be preempted and to be blocked waiting for locks. However, it does not handle general blocking (for example, via the wait_event() primitive): if you need that, you should instead use SRCU.
Realtime RCU
RCU-preempt: What happens on a context switch

Implementation

+#define RCU_READ_UNLOCK_NEED_QS (1 << 2) /* RCU core needs CPU response. */
f41d911f8c49a5d65c86504c19e8204bb605c4fd
need_qs
1d082fd061884a587c490c4fc8a2056ce1e47624

SRCU

Sleepable RCU

Tasks RCU

The RCU-tasks subsystem

Tiny RCU / RCU: The Bloatwatch Edition

RCU: The Bloatwatch Edition
rcu: Add a TINY_PREEMPT_RCU
rcu: Remove TINY_PREEMPT_RCU

Tree RCU / Hierarchical RCU

Hierarchical RCU
Tree RCU Grace Period Memory Ordering Components
A Tour Through TREE_RCU’s Data Structures
A Tour Through TREE_RCU’s Expedited Grace Periods
Tree preempt RCU: 3.0 and RCU: what went wrong

RCU bh

Questions on rcu-bh design

Priority-Boosting RCU

Priority-Boosting RCU Read-Side Critical Sections
CONFIG_RCU_BOOST

RCU API

RCU part 3: the RCU API, 2008 edition
The RCU API, 2010 Edition
The RCU API, 2014 Edition
The RCU API, 2019 edition

RCU stalls

Decoding Those Inscrutable RCU CPU Stall Warnings
update_process_times->rcu_check_callbacks->rcu_pending->__rcu_pending->check_cpu_stall->print_other_cpu_stall
Documentation/RCU/stallwarn.txt