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) Publications

A more-complete list in reverse chronological order:

  1. 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).
  2. February 2018 P0750R1: Consume, with JF Bastien (lead author). ISO SC22 WG21 (C++ Language).
  3. 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).
  4. February 2018 P0868R1: Selected RCU Litmus Tests, with Alan Stern, Andrew Hunter, Jade Alglave, and Luc Maranget. ISO SC22 WG21 (C++ Language).
  5. January 2018 Can RCU and CPU Hotplug Survive the Attack of the Killer Virtual Environments?, linux.conf.au.
  6. January 2018 Decoding Those Inscrutable RCU CPU Stall Warnings: They are for your own good! Honest!!!", linux.conf.au Kernel Minisummit.
  7. November 2017 P0868R0: Selected RCU Litmus Tests, with Alan Stern and Andrew Hunter. ISO SC22 WG21 (C++ Language).
  8. 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).
  9. 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).
  10. 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).
  11. October 2017 What Is RCU?, guest lecture to Carnegie Mellon University (Prof. Dave Eckhardt).
  12. September 2017 What Is RCU?, guest lecture to the Indian Institute of Science (Prof. K. Gopinath).
  13. September 2017 Decoding Those Inscrutable RCU CPU Stall Warnings “They are for your own good! Honest!!!”, Open Source Summit North America.
  14. September 2017 Beyond the Issaquah Challenge: High-Performance Scalable Complex Updates at Silicon Valley Linux Users Group.
  15. 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).
  16. 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).
  17. 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).
  18. 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).
  19. 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).
  20. 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.
  21. February 2017 Does RCU Really Work? And if so, how do we know? at Multicore World (extended presentation).
  22. 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).
  23. 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).
  24. 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).
  25. 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).
  26. 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).
  27. January 2017 Does RCU Really Work? And if so, how do we know? at the linux.conf.au Kernel minisummit.
  28. 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).
  29. October 2016 P0461R0: Proposed RCU C++ API, with Maged Michael, Michael Wong, Isabella Muerte, and Arthur O'Dwyer. ISO SC22 WG21 (C++ Language).
  30. October 2016 P0279R1: Read-Copy Update (RCU) for C++, ISO SC22 WG21 (C++ Language).
  31. 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).
  32. October 2016 Tracing and Linux-Kernel RCU at Tracing Summit (video).
  33. September 2016 A lock-free concurrency toolkit for deferred reclamation and optimistic speculation at CPPCON, with Michael Wong and Maged Michael (video).
  34. September 2016 RCU and C++ at CPPCON (video).
  35. September 2016 Beyond the Issaquah Challenge: High-Performance Scalable Complex Updates at CPPCON.
  36. June 2016 High-Performance and Scalable Updates: The Issaquah Challenge, at ACM Applicative Conference.
  37. 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).
  38. March 2016 P0190R1: Proposal for New memory_order_consume Definition, with Michael Wong, Hans Boehm, and Jens Maurer. ISO SC22 WG21 (C++ Language).
  39. February 2016 What Happens When 4096 Cores All Do synchronize_rcu_expedited()?, at linux.conf.au.
  40. February 2016 P0279R0: Read-Copy Update (RCU) for C++, ISO SC22 WG21 (C++ Language).
  41. February 2016 P0232R0: A Concurrency ToolKit for Structured Deferral/Optimistic Speculation, with Michael Wong (lead author) and Maged Michael. ISO SC22 WG21 (C++ Language).
  42. February 2016 P0190R0: Proposal for New memory_order_consume Definition, with Michael Wong, Hans Boehm, and Jens Maurer. ISO SC22 WG21 (C++ Language).
  43. February 2016 Mutation Testing and RCU, at linux.conf.au Kernel Miniconf.
  44. 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).
  45. September 2015 P0098R0: Towards Implementation and Use of memory_order_consume, ISO SC22 WG21 (C++ Language).
  46. September 2015 C++ Atomics: The Sad Story of memory_order_consume A Happy Ending At Last? at CPPCON.
  47. 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.
  48. 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.
  49. April 2015 N4483: Read-copy-update, ISO SC22 WG21 (C++ Language).
  50. November 2014 Recent read-mostly research, Linux Weekly News.
  51. November 2014 Read-Copy Update (RCU) Validation and Verification for Linux Galois Tech Talk.
  52. September 2014 C++ Memory Model Meets High-Update-Rate Data Structures CPPCON.
  53. September 2014 The RCU API, 2014 Edition, Linux Weekly News.
  54. 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).
  55. May 2014 Non-Transactional Implementation of Atomic Tree Move (4037) ISO SC22 WG21 (C++ Language).
  56. May 2014 What Is RCU?, presented to TU Dresden Distributed OS class (Instructor Carsten Weinhold).
  57. 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,
  58. November 2013 What Is RCU?, guest lecture to University of Cambridge (Prof. Peter Sewell).
  59. 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).
  60. May 2013 What Is RCU?, presented to TU Dresden Distributed OS class (Prof. Hermann Härtig).
  61. May 2013 What Is RCU? (video), presented to Indian Institute of Science (IISc) (Prof. K. Gopinath).
  62. May 2013 Structured Deferral: Synchronization via Procrastination, ACM Queue.
  63. January 2013 What is RCU?, The SIGPLAN Programming Languages Mentoring Workshop.
  64. August 2012 Real-Time Response on Multicore Systems: It Is Bigger Than You Think, Scaling Microconference, Linux Plumbers Conference.
  65. May 2012 What Is RCU? presented to TU Dresden Distributed OS class (Prof. Hermann Härtig).
  66. February 2012 Making RCU Safe For Battery-Powered Devices presented to the Embedded Linux Conference.
  67. 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).
  68. July 2011 3.0 and RCU: what went wrong.
  69. December 2010 The RCU API, 2010 Edition.
  70. August 2010 Scalable Concurrent Hash Tables via Relativistic Programming (bibtex).
  71. February 2010 Lockdep-RCU describing software-engineering enhancements to the Linux-kernel RCU implementations (bibtex).
  72. January 2010 Simplicity Through Optimization (presentation) (bibtex).
  73. 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.
  74. November 2008 Hierarchical RCU, in Linux Weekly News (bibtex). Describes a Linux-kernel RCU implementation designed to scale to thousands of CPUs.
  75. 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).
  76. 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).
  77. 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.)
  78. January 2008 RCU part 3: the RCU API at Linux Weekly News (bibtex).
  79. December 2007 What is RCU? Part 2: Usage at Linux Weekly News (bibtex).
  80. December 2007 What is RCU, Fundamentally? at Linux Weekly News with Jonathan Walpole (bibtex).
  81. 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.)
  82. October 2007 The design of preemptable read-copy update at Linux Weekly News (bibtex).
  83. August 2007 Using Promela and Spin to verify parallel algorithms at Linux Weekly News (bibtex). Includes proof of correctness for QRCU.
  84. February 2007 "Priority-Boosting RCU Read-Side Critical Sections", revision of earlier Linux Weekly News version (bibtex).
  85. October 2006 "Sleepable Read-Copy Update", revision of earlier Linux Weekly News version (bibtex).
  86. July 2006 "Extending RCU for Realtime and Embedded Workloads" with Dipankar Sarma, Ingo Molnar, and Suparna Bhattacharya at OLS'2006 (bibtex), and corresponding presentation.
  87. April 2006 "Making Lockless Synchronization Fast: Performance Implications of Memory Reclamation", with Tom Hart and Angela Demke. IPDPS 2006 Best Paper. Paper (bibtex). Presentation.
  88. July 2005 Abstraction, Reality Checks, and RCU presented at University of Toronto's "Cider Seminar" series (abstract).
  89. 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.
  90. January 2005 RCU Semantics: A First Attempt with Jon Walpole (bibtex). Technical report: engineering math meets RCU semantics.
  91. 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.)
  92. June 2004 paper describing modifications to the Linux RCU implementation to make it safe for realtime use (bibtex).
  93. 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.
  94. January 2004 paper and presentation for RCU performance on different CPUs at linux.conf.au in Adelaide, Australia (bibtex).
  95. January 2004 Scaling dcache with RCU (bibtex).
  96. October 2003 Linux Journal introduction to RCU (bibtex).
  97. PDF revision of FREENIX'03 paper (focusing on use of RCU in Linux's System-V IPC implementation) and corresponding presentation (bibtex).
  98. 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.
  99. PDF revision of OLS'02 paper (focusing on Linux-kernel infrastructure) and corresponding presentation (bibtex).
  100. PDF revision of OLS'01 paper (oriented to Linux kernel) and corresponding presentation (bibtex).
  101. PDF revision of RPE paper (more theoretical).
  102. PDF revision of PDCS'98 paper (DYNIX/ptx) (bibtex).
  103. Read-Copy Update: Using Execution History to Implement Low-Overhead Solutions to Concurrency Problems. Introduction to read-copy update.
  104. (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.