Introduction to RCU
The best introduction to RCU is my
Linux Weekly News three-part series, with update:
- What is RCU, Fundamentally? with Jonathan Walpole
(bibtex).
- What is RCU? Part 2: Usage
(bibtex).
- RCU part 3: the RCU API
(bibtex).
- The RCU API, 2010 Edition.
These expand on the older
“What is RCU?” introduction.
The Wikipedia article
also has some good information, as does the
ACM Queue
article.
In addition, Linux Weekly News
has a long
list of RCU-related articles.
There is also some
research
on the general family of algorithms of which RCU is a member
(bibtex)
and an annotated bibliography.
Alexey Gotsman, Noam Rinetzky, and Hongseok Yang have produced a
formalization of RCU based on separation logic.
Implementing RCU
The following papers describe how to implement RCU, in roughly
increasing order of accessibility:
- Lockdep-RCU.
- RCU: The Bloatwatch
Edition (optimized for uniprocessor operation)
(bibtex).
- Sleepable
Read-Copy Update (SRCU), revision of
Linux Weekly News
article
(bibtex).
- The classic PDF revision of
PDCS'98 paper on DYNIX/ptx's RCU implementation
(bibtex).
- The February 2012
IEEE TPDS paper
(bibtex)
is the best source of information on what RCU is, how to
implement it in userspace, and how it performs.
The pre-publication accepted version of this paper may be found
here (main paper) and
here (supplementary materials).
Some of the material in this paper came from
Mathieu Desnoyers's Ph.D.
dissertation
(bibtex).
- Using Promela and Spin
to verify parallel algorithms at Linux Weekly News
(bibtex).
Includes description of QRCU implementation.
- My Ph.D. dissertation
on RCU, which includes descriptions of a number of early
implementations
(bibtex).
- The design of preemptable
read-copy update (Linux Weekly News article)
(bibtex).
Please be warned: this is a detailed design document of the
most complex known RCU implementation. This implementation has
since been replaced by a faster, simpler, and more scalable
implementation, and an update of the documentation is pending.
There is an
RCU to-do list that is updated sporadically.
Read-Copy Update (RCU) Publications
A more-complete list in reverse chronological order:
- March 2018
Verification of Tree-Based Hierarchical Read-Copy Update
in the Linux Kernel,
with Lihao Liang, Daniel Kroening, and Tom Melham
(University of Oxford),
Design, Automation, & Test in Europe (DATE18).
- February 2018
P0750R1: Consume, with JF Bastien (lead author).
ISO SC22 WG21 (C++ Language).
- February 2018
P0566R4: Proposed Wording for Concurrent Data Structures: Hazard Pointer and Read-Copy-Update (RCU),
with Michael Wong (overall lead author), Maged M. Michael
(lead author for Hazard Pointers), Geoffrey Romer, Andrew
Hunter, Arthur O'Dwyer, David S. Hollman, JF Bastien, Hans Boehm,
and David Goldblatt. I am lead author for RCU.
ISO SC22 WG21 (C++ Language).
- February 2018
P0868R1: Selected RCU Litmus Tests,
with Alan Stern, Andrew Hunter, Jade Alglave, and Luc Maranget.
ISO SC22 WG21 (C++ Language).
- January 2018
Can RCU and CPU Hotplug Survive
the Attack of the Killer Virtual Environments?,
linux.conf.au.
- January 2018
Decoding Those Inscrutable
RCU CPU Stall Warnings: They are for your own good! Honest!!!",
linux.conf.au Kernel Minisummit.
- November 2017
P0868R0: Selected RCU Litmus Tests,
with Alan Stern and Andrew Hunter.
ISO SC22 WG21 (C++ Language).
- October 2017
P0566R3: Proposed Wording for Concurrent Data Structures: Hazard Pointer and Read-Copy-Update (RCU),
with Michael Wong (overall lead author), Maged M. Michael
(lead author for Hazard Pointers), Geoffrey Romer, Andrew
Hunter, and Arthur O'Dwyer. I am lead author for RCU.
ISO SC22 WG21 (C++ Language).
- October 2017
P0461R2 Proposed RCU C++ API,
with Maged Michael, Michael Wong, Isabella Muerte, Arthur O'Dwyer,
David Hollman, Andrew Hunter, Georey Romer, and Lance Roy.
ISO SC22 WG21 (C++ Language).
- October 2017
P0233R6: Hazard Pointers: Safe Reclamation for Optimistic Concurrency,
with Maged M. Michael (lead author), Michael Wong, Arthur O'Dwyer,
David Hollman, Geoffrey Romer, and Andrew Hunter.
ISO SC22 WG21 (C++ Language).
- October 2017
What Is RCU?,
guest lecture to Carnegie Mellon University
(Prof. Dave Eckhardt).
- September 2017
What Is RCU?,
guest lecture to the Indian Institute of Science
(Prof. K. Gopinath).
- September 2017
Decoding Those Inscrutable RCU CPU Stall Warnings
“They are for your own good! Honest!!!”,
Open Source Summit North America.
- September 2017
Beyond the Issaquah Challenge:
High-Performance Scalable Complex Updates
at Silicon Valley Linux Users Group.
- July 2017
P0566R2: Proposed Wording for Concurrent Data Structures: Hazard Pointer and Read-Copy-Update (RCU),
with Michael Wong (overall lead author), Maged M. Michael
(lead author for Hazard Pointers), Geoffrey Romer, and Andrew
Hunter. I am lead author for RCU.
ISO SC22 WG21 (C++ Language).
- July 2017
P0233R5: Hazard Pointers: Safe Reclamation for Optimistic Concurrency,
with Maged M. Michael (lead author), Michael Wong, Arthur O'Dwyer,
David Hollman, Geoffrey Romer, and Andrew Hunter.
ISO SC22 WG21 (C++ Language).
- June 2017
P0190R4: Proposal for New memory_order_consume Definition,
with Michael Wong, Hans Boehm, Jens Maurer, Jeffrey Yasskin,
and JF Bastien.
ISO SC22 WG21 (C++ Language).
- June 2017
P0566R1: Proposed Wording for Concurrent Data Structures: Hazard Pointer and Read-Copy-Update (RCU),
with Michael Wong (overall lead author), Maged M. Michael
(lead author for Hazard Pointers), Geoffrey Romer, and Andrew
Hunter. I am lead author for RCU.
ISO SC22 WG21 (C++ Language).
- June 2017
P0233R4: Hazard Pointers: Safe Reclamation for Optimistic Concurrency,
with Maged M. Michael (lead author), Michael Wong, Arthur O'Dwyer,
David Hollman, Geoffrey Romer, and Andrew Hunter.
ISO SC22 WG21 (C++ Language).
- March 2017
Applying Mutation Analysis On Kernel Test Suites: An Experience Report
with Iftekhar Ahmed, Rahul Gopinath, Carlos Jensen, and Alex Groce
at
12th International Workshop on Mutation Analysis.
- February 2017
Does RCU Really Work?
And if so, how do we know?
at
Multicore World
(extended presentation).
- February 2017
P0566R0: Proposed Wording for Concurrent Data Structures: Hazard Pointer and Read-Copy-Update (RCU),
with Michael Wong (lead author) and
Maged M. Michael (lead author for Hazard Pointers).
I am lead author for RCU.
ISO SC22 WG21 (C++ Language).
- February 2017
P0233R3: Hazard Pointers: Safe Reclamation for Optimistic Concurrency,
with Maged M. Michael (lead author), Michael Wong, Arthur O'Dwyer,
and David Hollman.
ISO SC22 WG21 (C++ Language).
- February 2017
P0462R1: Marking memory_order_consume Dependency Chains,
with Torvald Riegel, Jeff Preshing, Hans Boehm, Clark Nelson,
Olivier Giroux, Lawrence Crowl, JF Bastien, and Micheal Wong.
ISO SC22 WG21 (C++ Language).
- February 2017
P0461R1: Proposed RCU C++ API,
with Maged Michael, Michael Wong, Isabella Muerte, Arthur O'Dwyer,
and David Hollman.
ISO SC22 WG21 (C++ Language).
- February 2017
P0190R3: Proposal for New memory_order_consume Definition,
with Michael Wong, Hans Boehm, Jens Maurer, Jeffrey Yasskin,
and JF Bastien.
ISO SC22 WG21 (C++ Language).
- January 2017
Does RCU Really Work?
And if so, how do we know?
at the linux.conf.au Kernel minisummit.
- February 2017
P0233R2: Hazard Pointers: Safe Reclamation for Optimistic Concurrency,
with Maged M. Michael (lead author), Michael Wong, and Arthur O'Dwyer.
ISO SC22 WG21 (C++ Language).
- October 2016
P0461R0: Proposed RCU C++ API,
with Maged Michael, Michael Wong, Isabella Muerte, and Arthur O'Dwyer.
ISO SC22 WG21 (C++ Language).
- October 2016
P0279R1: Read-Copy Update (RCU) for C++,
ISO SC22 WG21 (C++ Language).
- October 2016
P0098R1: Towards Implementation and Use of memory order consume,
with Torvald Riegel, Jeff Preshing, Hans Boehm, Clark Nelson,
Olivier Giroux, and Lawrence Crowl.
ISO SC22 WG21 (C++ Language).
- October 2016
Tracing and Linux-Kernel RCU
at Tracing Summit
(video).
- September 2016
A lock-free concurrency toolkit for deferred reclamation and optimistic
speculation
at CPPCON, with Michael Wong and Maged Michael
(video).
- September 2016
RCU and C++
at CPPCON
(video).
- September 2016
Beyond the Issaquah Challenge:
High-Performance Scalable Complex Updates
at CPPCON.
- June 2016
High-Performance and
Scalable Updates: The Issaquah Challenge,
at ACM Applicative Conference.
- May 2016
P0190R2: Proposal for New memory_order_consume Definition,
with Michael Wong, Hans Boehm, Jens Maurer, Jeffrey Yasskin,
and JF Bastien.
ISO SC22 WG21 (C++ Language).
- March 2016
P0190R1: Proposal for New memory_order_consume Definition,
with Michael Wong, Hans Boehm, and Jens Maurer.
ISO SC22 WG21 (C++ Language).
- February 2016
What Happens When 4096 Cores All
Do synchronize_rcu_expedited()?,
at linux.conf.au.
- February 2016
P0279R0: Read-Copy Update (RCU) for C++,
ISO SC22 WG21 (C++ Language).
- February 2016
P0232R0: A Concurrency ToolKit for Structured Deferral/Optimistic Speculation,
with Michael Wong (lead author) and Maged Michael.
ISO SC22 WG21 (C++ Language).
- February 2016
P0190R0: Proposal for New memory_order_consume Definition,
with Michael Wong, Hans Boehm, and Jens Maurer.
ISO SC22 WG21 (C++ Language).
- February 2016
Mutation Testing and RCU,
at linux.conf.au Kernel Miniconf.
- November 2015
How Verified is My Code? Falsification-Driven Verification
with Alex Groce, Iftekhar Ahmed, and Carlos Jensen
at the 30th IEEE/ACM International Conference on Automated Software
Engineering (ASE).
- September 2015
P0098R0: Towards Implementation and Use of memory_order_consume,
ISO SC22 WG21 (C++ Language).
- September 2015
C++ Atomics: The Sad Story of memory_order_consume
A Happy Ending At Last?
at CPPCON.
- July-August 2015
Requirements for RCU part 1: the fundamentals,
RCU requirements part 2 — parallelism and software engineering,
and
RCU requirements part 3,
Linux Weekly News.
- May 2015 Dagstuhl Seminar 15191 “Compositional Verification
Methods for Next-Generation Concurrency”:
- Formal Verification and Linux-Kernel Concurrency
- Linearizability: Who Really Needs It?
- Some Examples of Kernel-Hacker Informal Correctness Reasoning
Blog post.
- April 2015
N4483: Read-copy-update,
ISO SC22 WG21 (C++ Language).
- November 2014
Recent read-mostly research, Linux Weekly News.
- November 2014
Read-Copy Update (RCU)
Validation and Verification for Linux
Galois Tech Talk.
- September 2014
C++ Memory Model Meets High-Update-Rate Data Structures
CPPCON.
- September 2014
The RCU API, 2014 Edition,
Linux Weekly News.
- May 2014
Towards Implementation and Use of memory_order_consume
ISO SC22 WG21 (C++ Language) Official version:
(N4036)
(revised N4215 2014-10-05,
revised N4321 2014-11-20).
- May 2014
Non-Transactional Implementation of Atomic Tree Move (4037)
ISO SC22 WG21 (C++ Language).
- May 2014
What Is RCU?,
presented to TU Dresden Distributed OS class (Instructor Carsten
Weinhold).
- November 2013
User-space RCU,
Linux Weekly News, with Mathieu Desnoyers, Lai Jiangshan, and
Josh Triplett.
Subparts of this article are:
URCU-protected hash tables,
The URCU hash table API,
URCU-protected queues and stacks,
The URCU stack/queue API,
User-space RCU: Atomic-operation and utility API,
User-space RCU: Memory-barrier menagerie,
The user-space RCU API,
The RCU-protected list API,
The RCU-barrier menagerie,
- November 2013
What Is RCU?,
guest lecture to University of Cambridge
(Prof. Peter Sewell).
- October 2013
Introduction to RCU Concepts: Liberal application of procrastination
for accommodation of the laws of physics — for more than two
decades,
LinuxCon Europe 2013 (part of Mathieu Desnoyers's Hands-On
Tutorial on Scalability with Userspace RCU).
- May 2013
What Is RCU?,
presented to TU Dresden Distributed OS class (Prof. Hermann Härtig).
- May 2013
What Is RCU?
(video),
presented to Indian Institute of Science (IISc) (Prof. K. Gopinath).
- May 2013
Structured Deferral: Synchronization via Procrastination,
ACM Queue.
- January 2013
What is RCU?,
The SIGPLAN Programming Languages Mentoring Workshop.
- August 2012
Real-Time Response on Multicore Systems:
It Is Bigger Than You Think,
Scaling Microconference, Linux Plumbers Conference.
- May 2012
What Is RCU?
presented to TU Dresden Distributed OS class (Prof. Hermann Härtig).
- February 2012
Making RCU Safe For Battery-Powered Devices
presented to the Embedded Linux Conference.
- February 2012
User-Level Implementations of Read-Copy Update
(bibtex) covering
what RCU is, how to implement it in userspace, and how it performs.
The pre-publication accepted version of this paper may be found
here (main paper) and
here (supplementary materials).
- July 2011
3.0 and RCU: what went wrong.
- December 2010
The RCU API, 2010 Edition.
- August 2010
Scalable Concurrent Hash Tables via Relativistic Programming
(bibtex).
- February 2010
Lockdep-RCU
describing software-engineering enhancements to the Linux-kernel
RCU implementations
(bibtex).
- January 2010
Simplicity Through Optimization
(presentation)
(bibtex).
- January 2009
Using a Malicious User-Level
RCU to Torture RCU-Based Algorithms,
at linux.conf.au
(bibtex).
Describes several user-level RCU implementations, and describes
how they can be used to validate kernel-level code using RCU.
- November 2008
Hierarchical
RCU, in Linux Weekly News
(bibtex).
Describes a Linux-kernel RCU implementation designed to scale
to thousands of CPUs.
- July 2008
Introducing technology into the Linux kernel: a case study
in ACM SIGOPS Operating System Review, with Jon Walpole
(updated to include
RCU changes through the 2.6.36 Linux kernel)
(bibtex).
- May 2008
The read-copy-update mechanism for supporting real-time
applications on shared-memory multiprocessor systems with Linux
in IBM Systems Journal,
with Dinakar Guniguntala, Josh Triplett, and Jon Walpole
(bibtex).
- February 2008
Introducing Technology
into Linux
(bibtex),
or "Introducing your technology into Linux will
require intoducing a LOT of Linux into your technology!!!"
at the 2008 Linux Developer Symposium - China (revised).
(Chinese translation
of original.)
- January 2008
RCU part 3: the RCU API
at Linux Weekly News
(bibtex).
- December 2007
What is RCU? Part 2: Usage
at Linux Weekly News
(bibtex).
- December 2007
What is RCU, Fundamentally?
at Linux Weekly News with Jonathan Walpole
(bibtex).
- December 2007
Performance of Memory Reclamation for Lockless Synchronization
in the Journal of Parallel and Distributed Computing, with
Tom Hart, Angela Demke Brown, and Jonathan Walpole
(bibtex).
(Journal version of the IPDPS'06 paper.)
- October 2007
The design of preemptable
read-copy update at Linux Weekly News
(bibtex).
- August 2007
Using Promela and Spin
to verify parallel algorithms at Linux Weekly News
(bibtex).
Includes proof of correctness for QRCU.
- February 2007
"Priority-Boosting RCU Read-Side Critical Sections",
revision of earlier
Linux Weekly News
version
(bibtex).
- October 2006
"Sleepable Read-Copy Update", revision of earlier
Linux Weekly News
version
(bibtex).
- July 2006
"Extending RCU for Realtime and Embedded Workloads"
with Dipankar Sarma, Ingo Molnar, and Suparna Bhattacharya
at OLS'2006
(bibtex),
and corresponding
presentation.
- April 2006
"Making Lockless Synchronization Fast: Performance Implications
of Memory Reclamation", with Tom Hart and Angela Demke.
IPDPS 2006 Best Paper.
Paper
(bibtex).
Presentation.
- July 2005
Abstraction, Reality Checks,
and RCU presented at University of Toronto's "Cider Seminar"
series (abstract).
- April 2005
paper (revised) and
presentation
describing
Linux realtime and yet more modifications to RCU to enable
even more aggressive realtime response
(bibtex).
Presented at the 2005 linux.conf.au.
- January 2005
RCU Semantics: A
First Attempt with Jon Walpole
(bibtex).
Technical report: engineering math meets RCU semantics.
- December 2004
James Morris's
Recent Developments in SELinux Kernel Performance
paper describes how RCU helped scalability of the SELinux
audit vector cache (AVC).
(I didn't have any involvement in creating this paper, but
believe that it is well worth bringing to your attention.)
- June 2004 paper describing
modifications to the Linux RCU implementation to make it safe
for realtime use
(bibtex).
- May 2004
dissertation and
presentation from Ph.D.
defense
(bibtex).
Also some advice
for others who are embarking on a part-time Ph.D. program,
and the
announcement.
- January 2004 paper and
presentation
for RCU performance on different CPUs
at linux.conf.au in Adelaide, Australia
(bibtex).
- January 2004
Scaling dcache with RCU
(bibtex).
- October 2003
Linux Journal introduction to RCU
(bibtex).
- PDF revision of FREENIX'03 paper
(focusing on use of RCU in Linux's System-V IPC implementation)
and corresponding
presentation
(bibtex).
-
Enabling Autonomic Behavior in Systems Software With Hot Swapping
(bibtex): describes how a RCU
(AKA "generations") is used in K42 to enable hot-swapping of
implementations of kernel algorithms.
- PDF revision of OLS'02 paper
(focusing on Linux-kernel infrastructure) and corresponding
presentation
(bibtex).
- PDF revision of OLS'01 paper
(oriented to Linux kernel) and corresponding
presentation
(bibtex).
- PDF revision of RPE paper
(more theoretical).
- PDF revision of PDCS'98 paper
(DYNIX/ptx)
(bibtex).
- Read-Copy Update:
Using Execution History to Implement Low-Overhead Solutions
to Concurrency Problems.
Introduction to read-copy update.
- (slightly outdated)
HTML version.
Linux RCU Work
The best summary of Linux RCU work is graphical, and may be found
here.
Some selected RCU patches:
- RCU was
accepted into the Linux 2.5.43 kernel. Patches to RCU were
applied to the 2.5.44 and 2.5.45 kernels. RCU was thus fully
functional in 2.5.45 and later Linux kernels, just in time for
the Halloween functionality freeze. ;-)
- Patch to the System V IPC implementation using RCU was
accepted into the Linux 2.5.46 kernel.
- Patch providing a lock-free IPv4 route cache was
accepted into the Linux 2.5.53 kernel.
- Patch providing lock-free handler traversal for IPMI handling,
added to the
Linux 2.5.58 kernel.
- Patch providing lock-free lookup of directory entries in the
dcache subsystem, added to the
Linux 2.5.62 kernel.
- Patches to replace many uses of brlock with RCU
in the
2.5.69 kernel,
with brlock being entirely eliminated in the
2.5.70 kernel.
- NMI handling for oprofile uses RCU in the
2.5.73 kernel.
- Fix ppc64 {pte,pmd}_free vs. hash_page race with RCU in the
2.6.2 kernel.
- Additional patches to the Linux kernel apply
RCU to FD-set management, task-list traversal, and i_shared_sem
contention reduction.
- Yet more patches change RCU's API to conserve memory and stack
space.
- Another patch to
monitor RCU grace period.
- Another patch to apply
RCU to fasync_lock,
perhaps for the 2.7 timeframe.
- Another set of patches apply modifications to the RCU infrastructure
to make it safe for soft-realtime use
(0/2,
1/2,
2/2).
- The Reiser4
filesystem uses RCU to defer freeing of jnodes.
- An
auditing patch uses RCU to guard the lists of auditing
rules.
- An SELinux scalability patch
uses RCU to guard the audit vector cache, with 500x improvement
in write() throughput on 32 CPUs, and about 50% improvement on
2 CPUs.
K42 RCU Work
- K42 is a research
OS at IBM that uses RCU pervasively as an existence lock.
K42 developed RCU independently, as described in the
Gamsa paper.
- K42 also uses RCU as a basis for hot-swapping:
overview
and infrastructure, and
implementation details and results.