What is RCU, Fundamentally?

If you can fill the unforgiving second
with sixty minutes worth of distance run,
“Highly scalable” your code will be reckoned,
And—which is more—you‘ll have parallel fun!

With apologies to Rudyard Kipling.

SMP Scalability Papers

1. , with Jade Alglave, Luc Maranget, Andrea Parri, and Alan Stern, Linux Kernel Summit Track. (Additional litmus tests .) November 2016.
2. , with Jade Alglave, Luc Maranget, Andrea Parri, and Alan Stern, LinuxCon EU. October 2016.
3. , guest lecture to the Distributed Operating Systems class at TU Dresden (), June 2016.
4.  at Beaver BarCamp, Corvallis, Oregon USA, April 2016.
5. , , April 2016.
6. , The Royal Society , “Verification in Industry” discussion, April 2016.
7. , guest lecture to the CS569 class at Oregon State University, June 2015.
8. , guest lecture to the CS362 class at Oregon State University, June 2015. (AKA “what would have to happen for me to add formal verification to Linux-kernel RCU‘s regression test suite?”)
9. , guest lecture to the Distributed Operating Systems class at TU Dresden (), June 2015.
10.  at Beaver BarCamp, Corvallis, Oregon USA, April 2015.
11. , in Linux Weekly News, August 2014.
12.  at linux.conf.au in Auckland, January 2015.
13.  at linux.conf.au in Auckland, January 2015.
14.  ISO SC22 WG21 (C++ Language), November 2014. ().
15.  ISO SC22 WG21 (C++ Language), November 2014. Official version:  ().
16. , in Linux Weekly News, August 2014.
17.  ISO SC22 WG21 (C++ Language), May 2014. Official version:  (, ).
18.  REORDER workshop in Vienna Summer of Logic, July 2014.
19.  Guest lecture to Portland State University CSE510 (Concurrency), Prof. Jonathan Walpole, June 2014.
20.  ISO SC22 WG21 (C++ Language), May 2014.
21.  at Beaver BarCamp, Corvallis, OR, USA, April 2014.
22.  at Linux Collaboration Summit, Napa, CA, USA, March 2014.
23.  at Linux Collaboration Summit, Napa, CA, USA, March 2014.
24.  at linux.conf.au in Perth, January 2014.
25.  at linux.conf.au in Perth, January 2014.
26.  at Linux Kernel Summit Scaling microconference October 2013.
27.  at Linux Plumbers Conference Scaling microconference, New Orleans, LA, USA. September 2013.
28.  at Linux Plumbers Conference, New Orleans, LA, USA. September 2013.
29.  at Linux Plumbers Conference, New Orleans, LA, USA. September 2013.
30.  at LinuxCon North America, New Orleans, LA, USA. September 2013.
31.  at Linux Foundation Enterprise End User Summit, May 2013.
32.  at Multicore World, February 2013. ( for Oregon State University BarCamp, April 2013.)
33. January 2013  at .
34.  (), at the Workshop on Relaxing Synchronization for Multicore and Manycore Software (RACES‘12), October 2012.
35. , at Scheduling Microconference, Linux Plumbers Conference, August 2012.
36. , in Linux Weekly News, August 2012.
37. , at Linux Collaboration Summit, San Francisco, CA, USA, April 2012.
38. , in Linux Weekly News, December 2011.
39. , at TU Dresden, Germany, October 2011.
40. , at the 2011 China Linux Kernel Developer Conference, Nanjing, China, October 2011. (Invited)
41. , at the 2011 Android System Developer Forum, Taipei, Taiwan, April 2011. (Invited)
42. ?, at Verification of Concurrent Data Structures (Verico), Austin, TX, USA, January 2011. (Invited)
43. , Linux Weekly News, January 2011.
44. , linux.conf.au January 2011.
45. , linux.conf.au January 2011.
46. , Dagstuhl workshop January 2011.
47.  with Blaine Garst (). ISO SC22 WG14 (C Language), November 2010.
48. , ISO SC22 WG21 (C++ Language), with Mark Batty, Clark Nelson, Hans Boehm, Anthony Williams, Scott Owens, Susmit Sarkar, Peter Sewell, Tjark Weber, Michael Wong, Lawrence Crowl, and Benjamin Kosnik. August 2010. ,
49. , August 2010, with Josh Triplett and Jonathan Walpole.
50. , August 2010, with Maged M. Michael, Josh Triplett, and Jonathan Walpole.
51. , Scuola Superiore Sant‘Anna, Pisa, Italy, July 2010.
52. . ISO SC22 WG14 (C Language), May 2010.
53. , complete with typo in title. ISO SC22 WG14 (C Language), May 2010.
54. . ISO SC22 WG14 (C Language), May 2010.
55. . ISO SC22 WG14 (C Language), April 2010. .
56. . ISO SC22 WG14 (C Language), April 2010. .
57. . ISO SC22 WG14 (C Language), April 2010.
58. . ISO SC22 WG21 (C++ Language) March 2010.
59. . ISO SC22 WG21 (C++ Language) February 2010. .
60. . ISO SC22 WG14 (C Language) November 2009.
61. . ISO SC22 WG14 (C Language) October 2009.
62.  short course for .
63. , presented at January 2009 linux.conf.au, along with .
64. , revision of . ISO SC22 WG21 (C++ Language) September 2008. This mapping was proven to be pointwise locally optimal in 2012 by of University of Cambridge. In other words, to improve on this mapping, it is necessary to consider successive atomic operations: Taken one at a time, each is optimal.
65.  at Linux Plumbers Conference Student Day, September 2008.
66.  at linux.conf.au 2008 Mel8ourne. February 2008.
67.  and  at PLOS 2007 with Maged Michael and Jon Walpole. October 2007. (.) (.)
68.  with Hans Boehm, August 2007.
69.  (),  (), and  (). August 2007. (Updated version of the May 2007 paper.)
70. . May 2007.
71. . Makes case for weakly ordered primitives in programming languages.  May 2007.
72. . January 2007.
73. , appearing in two parts in the  and  2005 Linux Journal (revised April 2009).
74.  in August 2004 Linux Journal.
75. . Presentation on scalability  and .
76.  OLS paper describing scalability, DoS, and realtime limitations of the Linux kernel at that time. With Dipankar Sarma.
77.  Bit-vector fair locking scheme for NUMA systems. Revision of paper that appeared in 2002 Parallel and Distributed Computing and Systems, with Swaninathan Sivasubramanian, Jack F. Vogel, and John Stultz. Of course, it is even better to design your software so that lock contention is low enough that fancy locking techniques don‘t help! We implemented a number of variations on this theme.
78.  (). The silver lining of the memory-latency dark cloud--programs whose run time is dominated by memory latency are often amenable to simple performance-estimation methods. Some of these methods are applicable at design time. Revision of PDCS‘99 paper.
79.  (). Revised version of the MASCOTS‘95 and the ‘99 SP&E papers.
80.  (). Revised version of the W‘93 USENIX and 2001 SP&E papers.
81.  (). Revised version of the PLoPD-II paper.
82.  (). Revised version of the October ‘96 CACM paper.
83.  (). Analytic comparison of a number of demultiplexing techniques. The winner is hashing.
84.  (). High-speed approximate implementation of Fair Queueing.
85.  (). Revised version of the ICPP‘89 paper.
86.  for other papers

    1. Introduction to RCU

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

       1.  with Jonathan Walpole ().
       2.  ().
       3.  ().
       4. .

       These expand on the older “” introduction. The  also has some good information, as does the  article. In addition,  has a long .

       There is also some  on the general family of algorithms of which RCU is a member () and an . Alexey Gotsman, Noam Rinetzky, and Hongseok Yang have produced a.

       Implementing RCU

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

       1. .
       2.  (optimized for uniprocessor operation) ().
       3.  (SRCU), revision of  article ().
       4. The classic  on DYNIX/ptx‘s RCU implementation ().
       5. The February 2012  () 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  and . Some of the material in this paper came from Mathieu Desnoyers‘s Ph.D.  ().
       6.  at Linux Weekly News (). Includes description of QRCU implementation.
       7. My Ph.D.  on RCU, which includes descriptions of a number of early implementations ().
       8.  (Linux Weekly News article) (). 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  that is updated sporadically.

       Read-Copy Update (RCU) Papers

       A more-complete list in reverse chronological order:

       1. October 2016  at Tracing Summit.
       2. September 2016  at CPPCON, with Michael Wong and Maged Michael ().
       3. September 2016  at CPPCON ().
       4. September 2016  at CPPCON.
       5. June 2016 , at ACM Applicative Conference.
       6. February 2016 , at linux.conf.au.
       7. February 2016 , at linux.conf.au Kernel Miniconf.
       8. September 2015 at CPPCON.
       9. July-August 2015 , , and , Linux Weekly News.
       10. May 2015 Dagstuhl Seminar 15191 “Compositional Verification Methods for Next-Generation Concurrency”:
           .
       11. November 2014 , Linux Weekly News.
       12. November 2014  Galois Tech Talk.
       13. September 2014  CPPCON.
       14. September 2014 , Linux Weekly News.
       15. May 2014  ISO SC22 WG21 (C++ Language) Official version: () (, ).
       16. May 2014  ISO SC22 WG21 (C++ Language).
       17. May 2014 , presented to TU Dresden Distributed OS class (Instructor Carsten Weinhold).
       18. November 2013 , Linux Weekly News, with Mathieu Desnoyers, Lai Jiangshan, and Josh Triplett. Subparts of this article are: , , , , , , , , ,
       19. November 2013 , guest lecture to University of Cambridge (Prof. Peter Sewell).
       20. October 2013 , LinuxCon Europe 2013 (part of Mathieu Desnoyers‘s Hands-On Tutorial on Scalability with Userspace RCU).
       21. May 2013 , presented to TU Dresden Distributed OS class (Prof. Hermann Härtig).
       22. May 2013  (), presented to Indian Institute of Science (IISc) (Prof. K. Gopinath).
       23. May 2013 , ACM Queue.
       24. January 2013 , .
       25. August 2012 , Scaling Microconference, Linux Plumbers Conference.
       26. May 2012  presented to TU Dresden Distributed OS class (Prof. Hermann Härtig).
       27. February 2012  presented to the Embedded Linux Conference.
       28. February 2012  () 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  and .
       29. July 2011 .
       30. December 2010 .
       31. August 2010  ().
       32. February 2010  describing software-engineering enhancements to the Linux-kernel RCU implementations ().
       33. January 2010  () ().
       34. January 2009 , at linux.conf.au (). Describes several user-level RCU implementations, and describes how they can be used to validate kernel-level code using RCU.
       35. November 2008 , in Linux Weekly News (). Describes a Linux-kernel RCU implementation designed to scale to thousands of CPUs.
       36. July 2008  in ACM SIGOPS Operating System Review, with Jon Walpole ( to include RCU changes through the 2.6.36 Linux kernel) ().
       37. May 2008  in IBM Systems Journal, with Dinakar Guniguntala, Josh Triplett, and Jon Walpole ().
       38. February 2008  (), or "Introducing your technology into Linux will require intoducing a LOT of Linux into your technology!!!" at the 2008 Linux Developer Symposium - China (revised). (.)
       39. January 2008 at Linux Weekly News ().
       40. December 2007 at Linux Weekly News ().
       41. December 2007 at Linux Weekly News with Jonathan Walpole ().
       42. December 2007  in the Journal of Parallel and Distributed Computing, with Tom Hart, Angela Demke Brown, and Jonathan Walpole (). (Journal version of the IPDPS‘06 paper.)
       43. October 2007  at Linux Weekly News ().
       44. August 2007  at Linux Weekly News (). Includes proof of correctness for QRCU.
       45. February 2007 , revision of earlier  version ().
       46. October 2006 , revision of earlier  version ().
       47. July 2006  with Dipankar Sarma, Ingo Molnar, and Suparna Bhattacharya at OLS‘2006 (), and corresponding .
       48. April 2006 , with Tom Hart and Angela Demke. .  (). .
       49. July 2005  presented at University of Toronto‘s "Cider Seminar" series (.
       50. April 2005  (revised) and  describing Linux realtime and yet more modifications to RCU to enable even more aggressive realtime response (). Presented at the 2005 linux.conf.au.
       51. January 2005  with Jon Walpole (). Technical report: engineering math meets RCU semantics.
       52. December 2004 James Morris‘s  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.)
       53. June 2004  describing modifications to the Linux RCU implementation to make it safe for realtime use ().
       54. May 2004  and  from Ph.D. defense (). Also some  for others who are embarking on a part-time Ph.D. program, and the .
       55. January 2004  and  for RCU performance on different CPUs at linux.conf.au in Adelaide, Australia ().
       56.  ().
       57.  ().
       58.  and corresponding  ().
       59.  (): describes how a RCU (AKA "generations") is used in K42 to enable hot-swapping of implementations of kernel algorithms.
       60.  and corresponding  ().
       61.  and corresponding  ().
       62. .
       63.  ().
       64. . Introduction to read-copy update.
       65. .

       Linux RCU Work

       The best summary of Linux RCU work is graphical, and may be found .

       Some selected RCU patches:

       1. RCU was  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 
       3. Patch providing a lock-free IPv4 route cache was 
       4. Patch providing lock-free handler traversal for IPMI handling, added to the 
       5. Patch providing lock-free lookup of directory entries in the dcache subsystem, added to the 
       6. Patches to replace many uses of brlock with RCU in the  with brlock being entirely eliminated in the 
       7. NMI handling for oprofile uses RCU in the 
       8. Fix ppc64 {pte,pmd}_free vs. hash_page race with RCU in the 
       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 .
       12. Another patch to apply , 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 (, , ).
       14. The  filesystem uses RCU to defer freeing of jnodes.
       15. An  uses RCU to guard the lists of auditing rules.
       16. An  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.  is a research OS at IBM that uses RCU pervasively as an existence lock. K42 developed RCU independently, as described in the .
       2. K42 also uses RCU as a basis for hot-swapping: , and .