1Read the F-ing Papers! 2 3 4This document describes RCU-related publications, and is followed by 5the corresponding bibtex entries. A number of the publications may 6be found at http://www.rdrop.com/users/paulmck/RCU/. 7 8The first thing resembling RCU was published in 1980, when Kung and Lehman 9[Kung80] recommended use of a garbage collector to defer destruction 10of nodes in a parallel binary search tree in order to simplify its 11implementation. This works well in environments that have garbage 12collectors, but current production garbage collectors incur significant 13read-side overhead. 14 15In 1982, Manber and Ladner [Manber82,Manber84] recommended deferring 16destruction until all threads running at that time have terminated, again 17for a parallel binary search tree. This approach works well in systems 18with short-lived threads, such as the K42 research operating system. 19However, Linux has long-lived tasks, so more is needed. 20 21In 1986, Hennessy, Osisek, and Seigh [Hennessy89] introduced passive 22serialization, which is an RCU-like mechanism that relies on the presence 23of "quiescent states" in the VM/XA hypervisor that are guaranteed not 24to be referencing the data structure. However, this mechanism was not 25optimized for modern computer systems, which is not surprising given 26that these overheads were not so expensive in the mid-80s. Nonetheless, 27passive serialization appears to be the first deferred-destruction 28mechanism to be used in production. Furthermore, the relevant patent has 29lapsed, so this approach may be used in non-GPL software, if desired. 30(In contrast, use of RCU is permitted only in software licensed under 31GPL. Sorry!!!) 32 33In 1990, Pugh [Pugh90] noted that explicitly tracking which threads 34were reading a given data structure permitted deferred free to operate 35in the presence of non-terminating threads. However, this explicit 36tracking imposes significant read-side overhead, which is undesirable 37in read-mostly situations. This algorithm does take pains to avoid 38write-side contention and parallelize the other write-side overheads by 39providing a fine-grained locking design, however, it would be interesting 40to see how much of the performance advantage reported in 1990 remains 41in 2004. 42 43At about this same time, Adams [Adams91] described ``chaotic relaxation'', 44where the normal barriers between successive iterations of convergent 45numerical algorithms are relaxed, so that iteration $n$ might use 46data from iteration $n-1$ or even $n-2$. This introduces error, 47which typically slows convergence and thus increases the number of 48iterations required. However, this increase is sometimes more than made 49up for by a reduction in the number of expensive barrier operations, 50which are otherwise required to synchronize the threads at the end 51of each iteration. Unfortunately, chaotic relaxation requires highly 52structured data, such as the matrices used in scientific programs, and 53is thus inapplicable to most data structures in operating-system kernels. 54 55In 1993, Jacobson [Jacobson93] verbally described what is perhaps the 56simplest deferred-free technique: simply waiting a fixed amount of time 57before freeing blocks awaiting deferred free. Jacobson did not describe 58any write-side changes he might have made in this work using SGI's Irix 59kernel. Aju John published a similar technique in 1995 [AjuJohn95]. 60This works well if there is a well-defined upper bound on the length of 61time that reading threads can hold references, as there might well be in 62hard real-time systems. However, if this time is exceeded, perhaps due 63to preemption, excessive interrupts, or larger-than-anticipated load, 64memory corruption can ensue, with no reasonable means of diagnosis. 65Jacobson's technique is therefore inappropriate for use in production 66operating-system kernels, except when such kernels can provide hard 67real-time response guarantees for all operations. 68 69Also in 1995, Pu et al. [Pu95a] applied a technique similar to that of Pugh's 70read-side-tracking to permit replugging of algorithms within a commercial 71Unix operating system. However, this replugging permitted only a single 72reader at a time. The following year, this same group of researchers 73extended their technique to allow for multiple readers [Cowan96a]. 74Their approach requires memory barriers (and thus pipeline stalls), 75but reduces memory latency, contention, and locking overheads. 76 771995 also saw the first publication of DYNIX/ptx's RCU mechanism 78[Slingwine95], which was optimized for modern CPU architectures, 79and was successfully applied to a number of situations within the 80DYNIX/ptx kernel. The corresponding conference paper appeared in 1998 81[McKenney98]. 82 83In 1999, the Tornado and K42 groups described their "generations" 84mechanism, which quite similar to RCU [Gamsa99]. These operating systems 85made pervasive use of RCU in place of "existence locks", which greatly 86simplifies locking hierarchies. 87 882001 saw the first RCU presentation involving Linux [McKenney01a] 89at OLS. The resulting abundance of RCU patches was presented the 90following year [McKenney02a], and use of RCU in dcache was first 91described that same year [Linder02a]. 92 93Also in 2002, Michael [Michael02b,Michael02a] presented "hazard-pointer" 94techniques that defer the destruction of data structures to simplify 95non-blocking synchronization (wait-free synchronization, lock-free 96synchronization, and obstruction-free synchronization are all examples of 97non-blocking synchronization). In particular, this technique eliminates 98locking, reduces contention, reduces memory latency for readers, and 99parallelizes pipeline stalls and memory latency for writers. However, 100these techniques still impose significant read-side overhead in the 101form of memory barriers. Researchers at Sun worked along similar lines 102in the same timeframe [HerlihyLM02,HerlihyLMS03]. These techniques 103can be thought of as inside-out reference counts, where the count is 104represented by the number of hazard pointers referencing a given data 105structure (rather than the more conventional counter field within the 106data structure itself). 107 108In 2003, the K42 group described how RCU could be used to create 109hot-pluggable implementations of operating-system functions. Later that 110year saw a paper describing an RCU implementation of System V IPC 111[Arcangeli03], and an introduction to RCU in Linux Journal [McKenney03a]. 112 1132004 has seen a Linux-Journal article on use of RCU in dcache 114[McKenney04a], a performance comparison of locking to RCU on several 115different CPUs [McKenney04b], a dissertation describing use of RCU in a 116number of operating-system kernels [PaulEdwardMcKenneyPhD], a paper 117describing how to make RCU safe for soft-realtime applications [Sarma04c], 118and a paper describing SELinux performance with RCU [JamesMorris04b]. 119 1202005 has seen further adaptation of RCU to realtime use, permitting 121preemption of RCU realtime critical sections [PaulMcKenney05a, 122PaulMcKenney05b]. 123 124Bibtex Entries 125 126@article{Kung80 127,author="H. T. Kung and Q. Lehman" 128,title="Concurrent Maintenance of Binary Search Trees" 129,Year="1980" 130,Month="September" 131,journal="ACM Transactions on Database Systems" 132,volume="5" 133,number="3" 134,pages="354-382" 135} 136 137@techreport{Manber82 138,author="Udi Manber and Richard E. Ladner" 139,title="Concurrency Control in a Dynamic Search Structure" 140,institution="Department of Computer Science, University of Washington" 141,address="Seattle, Washington" 142,year="1982" 143,number="82-01-01" 144,month="January" 145,pages="28" 146} 147 148@article{Manber84 149,author="Udi Manber and Richard E. Ladner" 150,title="Concurrency Control in a Dynamic Search Structure" 151,Year="1984" 152,Month="September" 153,journal="ACM Transactions on Database Systems" 154,volume="9" 155,number="3" 156,pages="439-455" 157} 158 159@techreport{Hennessy89 160,author="James P. Hennessy and Damian L. Osisek and Joseph W. {Seigh II}" 161,title="Passive Serialization in a Multitasking Environment" 162,institution="US Patent and Trademark Office" 163,address="Washington, DC" 164,year="1989" 165,number="US Patent 4,809,168 (lapsed)" 166,month="February" 167,pages="11" 168} 169 170@techreport{Pugh90 171,author="William Pugh" 172,title="Concurrent Maintenance of Skip Lists" 173,institution="Institute of Advanced Computer Science Studies, Department of Computer Science, University of Maryland" 174,address="College Park, Maryland" 175,year="1990" 176,number="CS-TR-2222.1" 177,month="June" 178} 179 180@Book{Adams91 181,Author="Gregory R. Adams" 182,title="Concurrent Programming, Principles, and Practices" 183,Publisher="Benjamin Cummins" 184,Year="1991" 185} 186 187@unpublished{Jacobson93 188,author="Van Jacobson" 189,title="Avoid Read-Side Locking Via Delayed Free" 190,year="1993" 191,month="September" 192,note="Verbal discussion" 193} 194 195@Conference{AjuJohn95 196,Author="Aju John" 197,Title="Dynamic vnodes -- Design and Implementation" 198,Booktitle="{USENIX Winter 1995}" 199,Publisher="USENIX Association" 200,Month="January" 201,Year="1995" 202,pages="11-23" 203,Address="New Orleans, LA" 204} 205 206@techreport{Slingwine95 207,author="John D. Slingwine and Paul E. McKenney" 208,title="Apparatus and Method for Achieving Reduced Overhead Mutual 209Exclusion and Maintaining Coherency in a Multiprocessor System 210Utilizing Execution History and Thread Monitoring" 211,institution="US Patent and Trademark Office" 212,address="Washington, DC" 213,year="1995" 214,number="US Patent 5,442,758 (contributed under GPL)" 215,month="August" 216} 217 218@techreport{Slingwine97 219,author="John D. Slingwine and Paul E. McKenney" 220,title="Method for maintaining data coherency using thread 221activity summaries in a multicomputer system" 222,institution="US Patent and Trademark Office" 223,address="Washington, DC" 224,year="1997" 225,number="US Patent 5,608,893 (contributed under GPL)" 226,month="March" 227} 228 229@techreport{Slingwine98 230,author="John D. Slingwine and Paul E. McKenney" 231,title="Apparatus and method for achieving reduced overhead 232mutual exclusion and maintaining coherency in a multiprocessor 233system utilizing execution history and thread monitoring" 234,institution="US Patent and Trademark Office" 235,address="Washington, DC" 236,year="1998" 237,number="US Patent 5,727,209 (contributed under GPL)" 238,month="March" 239} 240 241@Conference{McKenney98 242,Author="Paul E. McKenney and John D. Slingwine" 243,Title="Read-Copy Update: Using Execution History to Solve Concurrency 244Problems" 245,Booktitle="{Parallel and Distributed Computing and Systems}" 246,Month="October" 247,Year="1998" 248,pages="509-518" 249,Address="Las Vegas, NV" 250} 251 252@Conference{Gamsa99 253,Author="Ben Gamsa and Orran Krieger and Jonathan Appavoo and Michael Stumm" 254,Title="Tornado: Maximizing Locality and Concurrency in a Shared Memory 255Multiprocessor Operating System" 256,Booktitle="{Proceedings of the 3\textsuperscript{rd} Symposium on 257Operating System Design and Implementation}" 258,Month="February" 259,Year="1999" 260,pages="87-100" 261,Address="New Orleans, LA" 262} 263 264@techreport{Slingwine01 265,author="John D. Slingwine and Paul E. McKenney" 266,title="Apparatus and method for achieving reduced overhead 267mutual exclusion and maintaining coherency in a multiprocessor 268system utilizing execution history and thread monitoring" 269,institution="US Patent and Trademark Office" 270,address="Washington, DC" 271,year="2001" 272,number="US Patent 5,219,690 (contributed under GPL)" 273,month="April" 274} 275 276@Conference{McKenney01a 277,Author="Paul E. McKenney and Jonathan Appavoo and Andi Kleen and 278Orran Krieger and Rusty Russell and Dipankar Sarma and Maneesh Soni" 279,Title="Read-Copy Update" 280,Booktitle="{Ottawa Linux Symposium}" 281,Month="July" 282,Year="2001" 283,note="Available: 284\url{http://www.linuxsymposium.org/2001/abstracts/readcopy.php} 285\url{http://www.rdrop.com/users/paulmck/rclock/rclock_OLS.2001.05.01c.pdf} 286[Viewed June 23, 2004]" 287annotation=" 288Described RCU, and presented some patches implementing and using it in 289the Linux kernel. 290" 291} 292 293@Conference{Linder02a 294,Author="Hanna Linder and Dipankar Sarma and Maneesh Soni" 295,Title="Scalability of the Directory Entry Cache" 296,Booktitle="{Ottawa Linux Symposium}" 297,Month="June" 298,Year="2002" 299,pages="289-300" 300} 301 302@Conference{McKenney02a 303,Author="Paul E. McKenney and Dipankar Sarma and 304Andrea Arcangeli and Andi Kleen and Orran Krieger and Rusty Russell" 305,Title="Read-Copy Update" 306,Booktitle="{Ottawa Linux Symposium}" 307,Month="June" 308,Year="2002" 309,pages="338-367" 310,note="Available: 311\url{http://www.linux.org.uk/~ajh/ols2002_proceedings.pdf.gz} 312[Viewed June 23, 2004]" 313} 314 315@article{Appavoo03a 316,author="J. Appavoo and K. Hui and C. A. N. Soules and R. W. Wisniewski and 317D. M. {Da Silva} and O. Krieger and M. A. Auslander and D. J. Edelsohn and 318B. Gamsa and G. R. Ganger and P. McKenney and M. Ostrowski and 319B. Rosenburg and M. Stumm and J. Xenidis" 320,title="Enabling Autonomic Behavior in Systems Software With Hot Swapping" 321,Year="2003" 322,Month="January" 323,journal="IBM Systems Journal" 324,volume="42" 325,number="1" 326,pages="60-76" 327} 328 329@Conference{Arcangeli03 330,Author="Andrea Arcangeli and Mingming Cao and Paul E. McKenney and 331Dipankar Sarma" 332,Title="Using Read-Copy Update Techniques for {System V IPC} in the 333{Linux} 2.5 Kernel" 334,Booktitle="Proceedings of the 2003 USENIX Annual Technical Conference 335(FREENIX Track)" 336,Publisher="USENIX Association" 337,year="2003" 338,month="June" 339,pages="297-310" 340} 341 342@article{McKenney03a 343,author="Paul E. McKenney" 344,title="Using {RCU} in the {Linux} 2.5 Kernel" 345,Year="2003" 346,Month="October" 347,journal="Linux Journal" 348,volume="1" 349,number="114" 350,pages="18-26" 351} 352 353@techreport{Friedberg03a 354,author="Stuart A. Friedberg" 355,title="Lock-Free Wild Card Search Data Structure and Method" 356,institution="US Patent and Trademark Office" 357,address="Washington, DC" 358,year="2003" 359,number="US Patent 6,662,184 (contributed under GPL)" 360,month="December" 361,pages="112" 362} 363 364@article{McKenney04a 365,author="Paul E. McKenney and Dipankar Sarma and Maneesh Soni" 366,title="Scaling dcache with {RCU}" 367,Year="2004" 368,Month="January" 369,journal="Linux Journal" 370,volume="1" 371,number="118" 372,pages="38-46" 373} 374 375@Conference{McKenney04b 376,Author="Paul E. McKenney" 377,Title="{RCU} vs. Locking Performance on Different {CPUs}" 378,Booktitle="{linux.conf.au}" 379,Month="January" 380,Year="2004" 381,Address="Adelaide, Australia" 382,note="Available: 383\url{http://www.linux.org.au/conf/2004/abstracts.html#90} 384\url{http://www.rdrop.com/users/paulmck/rclock/lockperf.2004.01.17a.pdf} 385[Viewed June 23, 2004]" 386} 387 388@phdthesis{PaulEdwardMcKenneyPhD 389,author="Paul E. McKenney" 390,title="Exploiting Deferred Destruction: 391An Analysis of Read-Copy-Update Techniques 392in Operating System Kernels" 393,school="OGI School of Science and Engineering at 394Oregon Health and Sciences University" 395,year="2004" 396,note="Available: 397\url{http://www.rdrop.com/users/paulmck/RCU/RCUdissertation.2004.07.14e1.pdf} 398[Viewed October 15, 2004]" 399} 400 401@Conference{Sarma04c 402,Author="Dipankar Sarma and Paul E. McKenney" 403,Title="Making RCU Safe for Deep Sub-Millisecond Response Realtime Applications" 404,Booktitle="Proceedings of the 2004 USENIX Annual Technical Conference 405(FREENIX Track)" 406,Publisher="USENIX Association" 407,year="2004" 408,month="June" 409,pages="182-191" 410} 411 412@unpublished{JamesMorris04b 413,Author="James Morris" 414,Title="Recent Developments in {SELinux} Kernel Performance" 415,month="December" 416,year="2004" 417,note="Available: 418\url{http://www.livejournal.com/users/james_morris/2153.html} 419[Viewed December 10, 2004]" 420} 421 422@unpublished{PaulMcKenney05a 423,Author="Paul E. McKenney" 424,Title="{[RFC]} {RCU} and {CONFIG\_PREEMPT\_RT} progress" 425,month="May" 426,year="2005" 427,note="Available: 428\url{http://lkml.org/lkml/2005/5/9/185} 429[Viewed May 13, 2005]" 430,annotation=" 431 First publication of working lock-based deferred free patches 432 for the CONFIG_PREEMPT_RT environment. 433" 434} 435 436@conference{PaulMcKenney05b 437,Author="Paul E. McKenney and Dipankar Sarma" 438,Title="Towards Hard Realtime Response from the Linux Kernel on SMP Hardware" 439,Booktitle="linux.conf.au 2005" 440,month="April" 441,year="2005" 442,address="Canberra, Australia" 443,note="Available: 444\url{http://www.rdrop.com/users/paulmck/RCU/realtimeRCU.2005.04.23a.pdf} 445[Viewed May 13, 2005]" 446,annotation=" 447 Realtime turns into making RCU yet more realtime friendly. 448" 449} 450