[linuxkernelnewbies] Paul E. McKenney: Read-Copy Update (RCU)

Tue, 07 Oct 2008 22:32:30 -0700

http://www.rdrop.com/users/paulmck/RCU/

Introduction to RCU

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

  1. What is RCU, Fundamentally? with Jonathan Walpole.
  2. What is RCU? Part 2: Usage
  3. RCU part 3: the RCU API

These expand on the older “What is RCU?” introduction.

There is also some research on the general family of algorithms of which RCU is a member.

How much is RCU used in the Linux kernel?

Implementing RCU

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

  1. “Sleepable Read-Copy Update” (SRCU), revision of Linux Weekly News article.
  2. The classic PDF revision of PDCS'98 paper on DYNIX/ptx's RCU implementation.
  3. Using Promela and Spin to verify parallel algorithms at Linux Weekly News. Includes description of QRCU implementation.
  4. The design of preemptable read-copy update (Linux Weekly News article).
  5. My Ph.D. dissertation on RCU, which includes descriptions of a number of early implementations.

Read-Copy Update (RCU) Papers

A more-complete list in reverse chronological order:
  1. July 2008 Introducing technology into the Linux kernel: a case study in ACM SIGOPS Operating System Review, with Jon Walpole.
  2. 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.
  3. February 2008 Introducing Technology into Linux, 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.)
  4. January 2008 RCU part 3: the RCU API at Linux Weekly News.
  5. December 2007 What is RCU? Part 2: Usage at Linux Weekly News.
  6. December 2007 What is RCU, Fundamentally? at Linux Weekly News with Jonathan Walpole.
  7. 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. (Journal version of the IPDPS'06 paper.)
  8. October 2007 The design of preemptable read-copy update at Linux Weekly News.
  9. August 2007 Using Promela and Spin to verify parallel algorithms at Linux Weekly News. Includes proof of correctness for QRCU.
  10. February 2007 "Priority-Boosting RCU Read-Side Critical Sections" at Linux Weekly News (revised).
  11. October 2006 "Sleepable Read-Copy Update" at Linux Weekly News (revised).
  12. July 2006 "Extending RCU for Realtime and Embedded Workloads" with Dipankar Sarma, Ingo Molnar, and Suparna Bhattacharya at OLS'2006, and corresponding presentation.
  13. April 2006 "Making Lockless Synchronization Fast: Performance Implications of Memory Reclamation", with Tom Hart and Angela Demke. IPDPS 2006 Best Paper. Paper. Presentation.
  14. July 2005 Abstraction, Reality Checks, and RCU presented at University of Toronto's "Cider Seminar" series (abstract).
  15. 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.
  16. January 2005 RCU Semantics: A First Attempt with Jon Walpole. Technical report: engineering math meets RCU semantics.
  17. 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.)
  18. June 2004 paper describing modifications to the Linux RCU implementation to make it safe for realtime use (bibtex).
  19. 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.
  20. January 2004 paper and presentation for RCU performance on different CPUs at linux.conf.au in Adelaide, Australia (bibtex).
  21. January 2004 Scaling dcache with RCU (bibtex).
  22. October 2003 Linux Journal introduction to RCU (bibtex).
  23. PDF revision of FREENIX'03 paper (focusing on use of RCU in Linux's System-V IPC implementation) and corresponding presentation (bibtex).
  24. 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.
  25. PDF revision of OLS'02 paper (focusing on Linux-kernel infrastructure) and corresponding presentation (bibtex).
  26. PDF revision of OLS'01 paper (oriented to Linux kernel) and corresponding presentation (bibtex).
  27. PDF revision of RPE paper (more theoretical).
  28. PDF revision of PDCS'98 paper (DYNIX/ptx) (bibtex).
  29. Read-Copy Update: Using Execution History to Implement Low-Overhead Solutions to Concurrency Problems. Introduction to read-copy update.
  30. (slightly outdated) HTML version.
  31. Annotated bibliography.

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.

Reply via email to