Introduction to RCU

The best introduction to RCU is my Linux Weekly News three-part series, with update:

  1. What is RCU, Fundamentally? with Jonathan Walpole (bibtex).
  2. What is RCU? Part 2: Usage (bibtex).
  3. RCU part 3: the RCU API (bibtex).
  4. 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.

How much is RCU used in the Linux kernel?

Implementing RCU

The following papers describe how to implement RCU, in roughly increasing order of accessibility:

  1. Lockdep-RCU.
  2. RCU: The Bloatwatch Edition (optimized for uniprocessor operation) (bibtex).
  3. Sleepable Read-Copy Update (SRCU), revision of Linux Weekly News article (bibtex).
  4. The classic PDF revision of PDCS'98 paper on DYNIX/ptx's RCU implementation (bibtex).
  5. 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).
  6. Using Promela and Spin to verify parallel algorithms at Linux Weekly News (bibtex). Includes description of QRCU implementation.
  7. My Ph.D. dissertation on RCU, which includes descriptions of a number of early implementations (bibtex).
  8. 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) Papers

A more-complete list in reverse chronological order:

  1. September 2016 RCU and C++ at CPPCON.
  2. September 2016 Beyond the Issaquah Challenge: High-Performance Scalable Complex Updates at CPPCON.
  3. June 2016 High-Performance and Scalable Updates: The Issaquah Challenge, at ACM Applicative Conference.
  4. February 2016 What Happens When 4096 Cores All Do synchronize_rcu_expedited()?, at linux.conf.au.
  5. February 2016 Mutation Testing and RCU, at linux.conf.au Kernel Miniconf.
  6. 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.
  7. May 2015 Dagstuhl Seminar 15191 “Compositional Verification Methods for Next-Generation Concurrency”:
    1. Formal Verification and Linux-Kernel Concurrency
    2. Linearizability: Who Really Needs It?
    3. Some Examples of Kernel-Hacker Informal Correctness Reasoning
    Blog post.
  8. November 2014 Recent read-mostly research, Linux Weekly News.
  9. November 2014 Read-Copy Update (RCU) Validation and Verification for Linux Galois Tech Talk.
  10. September 2014 C++ Memory Model Meets High-Update-Rate Data Structures CPPCON.
  11. September 2014 The RCU API, 2014 Edition, Linux Weekly News.
  12. 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).
  13. May 2014 Non-Transactional Implementation of Atomic Tree Move (4037) ISO SC22 WG21 (C++ Language).
  14. May 2014 What Is RCU?, presented to TU Dresden Distributed OS class (Instructor Carsten Weinhold).
  15. 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,
  16. November 2013 What Is RCU?, guest lecture to University of Cambridge (Prof. Peter Sewell).
  17. 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).
  18. May 2013 What Is RCU?, presented to TU Dresden Distributed OS class (Prof. Hermann Härtig).
  19. May 2013 What Is RCU? (video), presented to Indian Institute of Science (IISc) (Prof. K. Gopinath).
  20. May 2013 Structured Deferral: Synchronization via Procrastination, ACM Queue.
  21. January 2013 What is RCU?, The SIGPLAN Programming Languages Mentoring Workshop.
  22. August 2012 Real-Time Response on Multicore Systems: It Is Bigger Than You Think, Scaling Microconference, Linux Plumbers Conference.
  23. May 2012 What Is RCU? presented to TU Dresden Distributed OS class (Prof. Hermann Härtig).
  24. February 2012 Making RCU Safe For Battery-Powered Devices presented to the Embedded Linux Conference.
  25. 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).
  26. July 2011 3.0 and RCU: what went wrong.
  27. December 2010 The RCU API, 2010 Edition.
  28. August 2010 Scalable Concurrent Hash Tables via Relativistic Programming (bibtex).
  29. February 2010 Lockdep-RCU describing software-engineering enhancements to the Linux-kernel RCU implementations (bibtex).
  30. January 2010 Simplicity Through Optimization (presentation) (bibtex).
  31. 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.
  32. November 2008 Hierarchical RCU, in Linux Weekly News (bibtex). Describes a Linux-kernel RCU implementation designed to scale to thousands of CPUs.
  33. 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).
  34. 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).
  35. 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.)
  36. January 2008 RCU part 3: the RCU API at Linux Weekly News (bibtex).
  37. December 2007 What is RCU? Part 2: Usage at Linux Weekly News (bibtex).
  38. December 2007 What is RCU, Fundamentally? at Linux Weekly News with Jonathan Walpole (bibtex).
  39. 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.)
  40. October 2007 The design of preemptable read-copy update at Linux Weekly News (bibtex).
  41. August 2007 Using Promela and Spin to verify parallel algorithms at Linux Weekly News (bibtex). Includes proof of correctness for QRCU.
  42. February 2007 "Priority-Boosting RCU Read-Side Critical Sections", revision of earlier Linux Weekly News version (bibtex).
  43. October 2006 "Sleepable Read-Copy Update", revision of earlier Linux Weekly News version (bibtex).
  44. July 2006 "Extending RCU for Realtime and Embedded Workloads" with Dipankar Sarma, Ingo Molnar, and Suparna Bhattacharya at OLS'2006 (bibtex), and corresponding presentation.
  45. April 2006 "Making Lockless Synchronization Fast: Performance Implications of Memory Reclamation", with Tom Hart and Angela Demke. IPDPS 2006 Best Paper. Paper (bibtex). Presentation.
  46. July 2005 Abstraction, Reality Checks, and RCU presented at University of Toronto's "Cider Seminar" series (abstract).
  47. 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.
  48. January 2005 RCU Semantics: A First Attempt with Jon Walpole (bibtex). Technical report: engineering math meets RCU semantics.
  49. 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.)
  50. June 2004 paper describing modifications to the Linux RCU implementation to make it safe for realtime use (bibtex).
  51. 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.
  52. January 2004 paper and presentation for RCU performance on different CPUs at linux.conf.au in Adelaide, Australia (bibtex).
  53. January 2004 Scaling dcache with RCU (bibtex).
  54. October 2003 Linux Journal introduction to RCU (bibtex).
  55. PDF revision of FREENIX'03 paper (focusing on use of RCU in Linux's System-V IPC implementation) and corresponding presentation (bibtex).
  56. 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.
  57. PDF revision of OLS'02 paper (focusing on Linux-kernel infrastructure) and corresponding presentation (bibtex).
  58. PDF revision of OLS'01 paper (oriented to Linux kernel) and corresponding presentation (bibtex).
  59. PDF revision of RPE paper (more theoretical).
  60. PDF revision of PDCS'98 paper (DYNIX/ptx) (bibtex).
  61. Read-Copy Update: Using Execution History to Implement Low-Overhead Solutions to Concurrency Problems. Introduction to read-copy update.
  62. (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:

  1. 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. ;-)
  2. Patch to the System V IPC implementation using RCU was accepted into the Linux 2.5.46 kernel.
  3. Patch providing a lock-free IPv4 route cache was accepted into the Linux 2.5.53 kernel.
  4. Patch providing lock-free handler traversal for IPMI handling, added to the Linux 2.5.58 kernel.
  5. Patch providing lock-free lookup of directory entries in the dcache subsystem, added to the Linux 2.5.62 kernel.
  6. 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.
  7. NMI handling for oprofile uses RCU in the 2.5.73 kernel.
  8. Fix ppc64 {pte,pmd}_free vs. hash_page race with RCU in the 2.6.2 kernel.
  9. Additional patches to the Linux kernel apply RCU to FD-set management, task-list traversal, and i_shared_sem contention reduction.
  10. Yet more patches change RCU's API to conserve memory and stack space.
  11. Another patch to monitor RCU grace period.
  12. Another patch to apply RCU to fasync_lock, perhaps for the 2.7 timeframe.
  13. Another set of patches apply modifications to the RCU infrastructure to make it safe for soft-realtime use (0/2, 1/2, 2/2).
  14. The Reiser4 filesystem uses RCU to defer freeing of jnodes.
  15. An auditing patch uses RCU to guard the lists of auditing rules.
  16. 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

  1. 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.
  2. K42 also uses RCU as a basis for hot-swapping: overview and infrastructure, and implementation details and results.