1Read the Fscking 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/. For others, browsers 7and search engines will usually find what you are looking for. 8 9The first thing resembling RCU was published in 1980, when Kung and Lehman 10[Kung80] recommended use of a garbage collector to defer destruction 11of nodes in a parallel binary search tree in order to simplify its 12implementation. This works well in environments that have garbage 13collectors, but most production garbage collectors incur significant 14overhead. 15 16In 1982, Manber and Ladner [Manber82,Manber84] recommended deferring 17destruction until all threads running at that time have terminated, again 18for a parallel binary search tree. This approach works well in systems 19with short-lived threads, such as the K42 research operating system. 20However, Linux has long-lived tasks, so more is needed. 21 22In 1986, Hennessy, Osisek, and Seigh [Hennessy89] introduced passive 23serialization, which is an RCU-like mechanism that relies on the presence 24of "quiescent states" in the VM/XA hypervisor that are guaranteed not 25to be referencing the data structure. However, this mechanism was not 26optimized for modern computer systems, which is not surprising given 27that these overheads were not so expensive in the mid-80s. Nonetheless, 28passive serialization appears to be the first deferred-destruction 29mechanism to be used in production. Furthermore, the relevant patent 30has lapsed, so this approach may be used in non-GPL software, if desired. 31(In contrast, implementation of RCU is permitted only in software licensed 32under either GPL or LGPL. Sorry!!!) 33 34In 1990, Pugh [Pugh90] noted that explicitly tracking which threads 35were reading a given data structure permitted deferred free to operate 36in the presence of non-terminating threads. However, this explicit 37tracking imposes significant read-side overhead, which is undesirable 38in read-mostly situations. This algorithm does take pains to avoid 39write-side contention and parallelize the other write-side overheads by 40providing a fine-grained locking design, however, it would be interesting 41to see how much of the performance advantage reported in 1990 remains 42in 2004. 43 44At about this same time, Adams [Adams91] described ``chaotic relaxation'', 45where the normal barriers between successive iterations of convergent 46numerical algorithms are relaxed, so that iteration $n$ might use 47data from iteration $n-1$ or even $n-2$. This introduces error, 48which typically slows convergence and thus increases the number of 49iterations required. However, this increase is sometimes more than made 50up for by a reduction in the number of expensive barrier operations, 51which are otherwise required to synchronize the threads at the end 52of each iteration. Unfortunately, chaotic relaxation requires highly 53structured data, such as the matrices used in scientific programs, and 54is thus inapplicable to most data structures in operating-system kernels. 55 56In 1992, Henry (now Alexia) Massalin completed a dissertation advising 57parallel programmers to defer processing when feasible to simplify 58synchronization. RCU makes extremely heavy use of this advice. 59 60In 1993, Jacobson [Jacobson93] verbally described what is perhaps the 61simplest deferred-free technique: simply waiting a fixed amount of time 62before freeing blocks awaiting deferred free. Jacobson did not describe 63any write-side changes he might have made in this work using SGI's Irix 64kernel. Aju John published a similar technique in 1995 [AjuJohn95]. 65This works well if there is a well-defined upper bound on the length of 66time that reading threads can hold references, as there might well be in 67hard real-time systems. However, if this time is exceeded, perhaps due 68to preemption, excessive interrupts, or larger-than-anticipated load, 69memory corruption can ensue, with no reasonable means of diagnosis. 70Jacobson's technique is therefore inappropriate for use in production 71operating-system kernels, except when such kernels can provide hard 72real-time response guarantees for all operations. 73 74Also in 1995, Pu et al. [Pu95a] applied a technique similar to that of Pugh's 75read-side-tracking to permit replugging of algorithms within a commercial 76Unix operating system. However, this replugging permitted only a single 77reader at a time. The following year, this same group of researchers 78extended their technique to allow for multiple readers [Cowan96a]. 79Their approach requires memory barriers (and thus pipeline stalls), 80but reduces memory latency, contention, and locking overheads. 81 821995 also saw the first publication of DYNIX/ptx's RCU mechanism 83[Slingwine95], which was optimized for modern CPU architectures, 84and was successfully applied to a number of situations within the 85DYNIX/ptx kernel. The corresponding conference paper appeared in 1998 86[McKenney98]. 87 88In 1999, the Tornado and K42 groups described their "generations" 89mechanism, which quite similar to RCU [Gamsa99]. These operating systems 90made pervasive use of RCU in place of "existence locks", which greatly 91simplifies locking hierarchies. 92 932001 saw the first RCU presentation involving Linux [McKenney01a] 94at OLS. The resulting abundance of RCU patches was presented the 95following year [McKenney02a], and use of RCU in dcache was first 96described that same year [Linder02a]. 97 98Also in 2002, Michael [Michael02b,Michael02a] presented "hazard-pointer" 99techniques that defer the destruction of data structures to simplify 100non-blocking synchronization (wait-free synchronization, lock-free 101synchronization, and obstruction-free synchronization are all examples of 102non-blocking synchronization). In particular, this technique eliminates 103locking, reduces contention, reduces memory latency for readers, and 104parallelizes pipeline stalls and memory latency for writers. However, 105these techniques still impose significant read-side overhead in the 106form of memory barriers. Researchers at Sun worked along similar lines 107in the same timeframe [HerlihyLM02]. These techniques can be thought 108of as inside-out reference counts, where the count is represented by the 109number of hazard pointers referencing a given data structure (rather than 110the more conventional counter field within the data structure itself). 111 112By the same token, RCU can be thought of as a "bulk reference count", 113where some form of reference counter covers all reference by a given CPU 114or thread during a set timeframe. This timeframe is related to, but 115not necessarily exactly the same as, an RCU grace period. In classic 116RCU, the reference counter is the per-CPU bit in the "bitmask" field, 117and each such bit covers all references that might have been made by 118the corresponding CPU during the prior grace period. Of course, RCU 119can be thought of in other terms as well. 120 121In 2003, the K42 group described how RCU could be used to create 122hot-pluggable implementations of operating-system functions [Appavoo03a]. 123Later that year saw a paper describing an RCU implementation of System 124V IPC [Arcangeli03], and an introduction to RCU in Linux Journal 125[McKenney03a]. 126 1272004 has seen a Linux-Journal article on use of RCU in dcache 128[McKenney04a], a performance comparison of locking to RCU on several 129different CPUs [McKenney04b], a dissertation describing use of RCU in a 130number of operating-system kernels [PaulEdwardMcKenneyPhD], a paper 131describing how to make RCU safe for soft-realtime applications [Sarma04c], 132and a paper describing SELinux performance with RCU [JamesMorris04b]. 133 1342005 brought further adaptation of RCU to realtime use, permitting 135preemption of RCU realtime critical sections [PaulMcKenney05a, 136PaulMcKenney05b]. 137 1382006 saw the first best-paper award for an RCU paper [ThomasEHart2006a], 139as well as further work on efficient implementations of preemptible 140RCU [PaulEMcKenney2006b], but priority-boosting of RCU read-side critical 141sections proved elusive. An RCU implementation permitting general 142blocking in read-side critical sections appeared [PaulEMcKenney2006c], 143Robert Olsson described an RCU-protected trie-hash combination 144[RobertOlsson2006a]. 145 1462007 saw the journal version of the award-winning RCU paper from 2006 147[ThomasEHart2007a], as well as a paper demonstrating use of Promela 148and Spin to mechanically verify an optimization to Oleg Nesterov's 149QRCU [PaulEMcKenney2007QRCUspin], a design document describing 150preemptible RCU [PaulEMcKenney2007PreemptibleRCU], and the three-part 151LWN "What is RCU?" series [PaulEMcKenney2007WhatIsRCUFundamentally, 152PaulEMcKenney2008WhatIsRCUUsage, and PaulEMcKenney2008WhatIsRCUAPI]. 153 1542008 saw a journal paper on real-time RCU [DinakarGuniguntala2008IBMSysJ], 155a history of how Linux changed RCU more than RCU changed Linux 156[PaulEMcKenney2008RCUOSR], and a design overview of hierarchical RCU 157[PaulEMcKenney2008HierarchicalRCU]. 158 1592009 introduced user-level RCU algorithms [PaulEMcKenney2009MaliciousURCU], 160which Mathieu Desnoyers is now maintaining [MathieuDesnoyers2009URCU] 161[MathieuDesnoyersPhD]. TINY_RCU [PaulEMcKenney2009BloatWatchRCU] made 162its appearance, as did expedited RCU [PaulEMcKenney2009expeditedRCU]. 163The problem of resizeable RCU-protected hash tables may now be on a path 164to a solution [JoshTriplett2009RPHash]. A few academic researchers are now 165using RCU to solve their parallel problems [HariKannan2009DynamicAnalysisRCU]. 166 1672010 produced a simpler preemptible-RCU implementation 168based on TREE_RCU [PaulEMcKenney2010SimpleOptRCU], lockdep-RCU 169[PaulEMcKenney2010LockdepRCU], another resizeable RCU-protected hash 170table [HerbertXu2010RCUResizeHash] (this one consuming more memory, 171but allowing arbitrary changes in hash function, as required for DoS 172avoidance in the networking code), realization of the 2009 RCU-protected 173hash table with atomic node move [JoshTriplett2010RPHash], an update on 174the RCU API [PaulEMcKenney2010RCUAPI]. 175 1762011 marked the inclusion of Nick Piggin's fully lockless dentry search 177[LinusTorvalds2011Linux2:6:38:rc1:NPigginVFS], an RCU-protected red-black 178tree using software transactional memory to protect concurrent updates 179(strange, but true!) [PhilHoward2011RCUTMRBTree], yet another variant of 180RCU-protected resizeable hash tables [Triplett:2011:RPHash], the 3.0 RCU 181trainwreck [PaulEMcKenney2011RCU3.0trainwreck], and Neil Brown's "Meet the 182Lockers" LWN article [NeilBrown2011MeetTheLockers]. 183 184 185Bibtex Entries 186 187@article{Kung80 188,author="H. T. Kung and Q. Lehman" 189,title="Concurrent Manipulation of Binary Search Trees" 190,Year="1980" 191,Month="September" 192,journal="ACM Transactions on Database Systems" 193,volume="5" 194,number="3" 195,pages="354-382" 196,note="Available: 197\url{http://portal.acm.org/citation.cfm?id=320619&dl=GUIDE,} 198[Viewed December 3, 2007]" 199,annotation={ 200 Use garbage collector to clean up data after everyone is done with it. 201 . 202 Oldest use of something vaguely resembling RCU that I have found. 203} 204} 205 206@techreport{Manber82 207,author="Udi Manber and Richard E. Ladner" 208,title="Concurrency Control in a Dynamic Search Structure" 209,institution="Department of Computer Science, University of Washington" 210,address="Seattle, Washington" 211,year="1982" 212,number="82-01-01" 213,month="January" 214,pages="28" 215,annotation={ 216 . 217 Superseded by Manber84. 218 . 219 Describes concurrent AVL tree implementation. Uses a 220 garbage-collection mechanism to handle concurrent use and deletion 221 of nodes in the tree, but lacks the summary-of-execution-history 222 concept of read-copy locking. 223 . 224 Keeps full list of processes that were active when a given 225 node was to be deleted, and waits until all such processes have 226 -terminated- before allowing this node to be reused. This is 227 not described in great detail -- one could imagine using process 228 IDs for this if the ID space was large enough that overlapping 229 never occurred. 230 . 231 This restriction makes this algorithm unsuitable for use in 232 systems comprised of long-lived processes. It also produces 233 completely unacceptable overhead in systems with large numbers 234 of processes. Finally, it is specific to AVL trees. 235 . 236 Cites Kung80, so not an independent invention, but the first 237 RCU-like usage that does not rely on an automatic garbage 238 collector. 239} 240} 241 242@article{Manber84 243,author="Udi Manber and Richard E. Ladner" 244,title="Concurrency Control in a Dynamic Search Structure" 245,Year="1984" 246,Month="September" 247,journal="ACM Transactions on Database Systems" 248,volume="9" 249,number="3" 250,pages="439-455" 251,annotation={ 252 Describes concurrent AVL tree implementation. Uses a 253 garbage-collection mechanism to handle concurrent use and deletion 254 of nodes in the tree, but lacks the summary-of-execution-history 255 concept of read-copy locking. 256 . 257 Keeps full list of processes that were active when a given 258 node was to be deleted, and waits until all such processes have 259 -terminated- before allowing this node to be reused. This is 260 not described in great detail -- one could imagine using process 261 IDs for this if the ID space was large enough that overlapping 262 never occurred. 263 . 264 This restriction makes this algorithm unsuitable for use in 265 systems comprised of long-lived processes. It also produces 266 completely unacceptable overhead in systems with large numbers 267 of processes. Finally, it is specific to AVL trees. 268} 269} 270 271@Conference{RichardRashid87a 272,Author="Richard Rashid and Avadis Tevanian and Michael Young and 273David Golub and Robert Baron and David Black and William Bolosky and 274Jonathan Chew" 275,Title="Machine-Independent Virtual Memory Management for Paged 276Uniprocessor and Multiprocessor Architectures" 277,Booktitle="{2\textsuperscript{nd} Symposium on Architectural Support 278for Programming Languages and Operating Systems}" 279,Publisher="Association for Computing Machinery" 280,Month="October" 281,Year="1987" 282,pages="31-39" 283,Address="Palo Alto, CA" 284,note="Available: 285\url{http://www.cse.ucsc.edu/~randal/221/rashid-machvm.pdf} 286[Viewed February 17, 2005]" 287,annotation={ 288 Describes lazy TLB flush, where one waits for each CPU to pass 289 through a scheduling-clock interrupt before reusing a given range 290 of virtual address. Does not describe how one determines that 291 all CPUs have in fact taken such an interrupt, though there are 292 no shortage of straightforward methods for accomplishing this. 293 . 294 Note that it does not make sense to just wait a fixed amount of 295 time, since a given CPU might have interrupts disabled for an 296 extended amount of time. 297} 298} 299 300@article{BarbaraLiskov1988ArgusCACM 301,author = {Barbara Liskov} 302,title = {Distributed programming in {Argus}} 303,journal = {Commun. ACM} 304,volume = {31} 305,number = {3} 306,year = {1988} 307,issn = {0001-0782} 308,pages = {300--312} 309,doi = {http://doi.acm.org/10.1145/42392.42399} 310,publisher = {ACM} 311,address = {New York, NY, USA} 312,annotation= { 313 At the top of page 307: "Conflicts with deposits and withdrawals 314 are necessary if the reported total is to be up to date. They 315 could be avoided by having total return a sum that is slightly 316 out of date." Relies on semantics -- approximate numerical 317 values sometimes OK. 318} 319} 320 321@techreport{Hennessy89 322,author="James P. Hennessy and Damian L. Osisek and Joseph W. {Seigh II}" 323,title="Passive Serialization in a Multitasking Environment" 324,institution="US Patent and Trademark Office" 325,address="Washington, DC" 326,year="1989" 327,number="US Patent 4,809,168 (lapsed)" 328,month="February" 329,pages="11" 330} 331 332@techreport{Pugh90 333,author="William Pugh" 334,title="Concurrent Maintenance of Skip Lists" 335,institution="Institute of Advanced Computer Science Studies, Department of Computer Science, University of Maryland" 336,address="College Park, Maryland" 337,year="1990" 338,number="CS-TR-2222.1" 339,month="June" 340,annotation={ 341 Concurrent access to skip lists. Has both weak and strong search. 342 Uses concept of ``garbage queue'', but has no real way of cleaning 343 the garbage efficiently. 344 . 345 Appears to be an independent invention of an RCU-like mechanism. 346} 347} 348 349@Book{Adams91 350,Author="Gregory R. Adams" 351,title="Concurrent Programming, Principles, and Practices" 352,Publisher="Benjamin Cummins" 353,Year="1991" 354,annotation={ 355 Has a few paragraphs describing ``chaotic relaxation'', a 356 numerical analysis technique that allows multiprocessors to 357 avoid synchronization overhead by using possibly-stale data. 358 . 359 Seems like this is descended from yet another independent 360 invention of RCU-like function -- but this is restricted 361 in that reclamation is not necessary. 362} 363} 364 365@unpublished{Jacobson93 366,author="Van Jacobson" 367,title="Avoid Read-Side Locking Via Delayed Free" 368,year="1993" 369,month="September" 370,note="private communication" 371,annotation={ 372 Use fixed time delay to approximate grace period. Very simple, 373 but subject to random memory corruption under heavy load. 374 . 375 Independent invention of RCU-like mechanism. 376} 377} 378 379@Conference{AjuJohn95 380,Author="Aju John" 381,Title="Dynamic vnodes -- Design and Implementation" 382,Booktitle="{USENIX Winter 1995}" 383,Publisher="USENIX Association" 384,Month="January" 385,Year="1995" 386,pages="11-23" 387,Address="New Orleans, LA" 388,note="Available: 389\url{https://www.usenix.org/publications/library/proceedings/neworl/full_papers/john.a} 390[Viewed October 1, 2010]" 391,annotation={ 392 Age vnodes out of the cache, and have a fixed time set by a kernel 393 parameter. Not clear that all races were in fact correctly handled. 394 Used a 20-minute time by default, which would most definitely not 395 be suitable during DoS attacks or virus scans. 396 . 397 Apparently independent invention of RCU-like mechanism. 398} 399} 400 401@conference{Pu95a, 402Author = "Calton Pu and Tito Autrey and Andrew Black and Charles Consel and 403Crispin Cowan and Jon Inouye and Lakshmi Kethana and Jonathan Walpole and 404Ke Zhang", 405Title = "Optimistic Incremental Specialization: Streamlining a Commercial 406Operating System", 407Booktitle = "15\textsuperscript{th} ACM Symposium on 408Operating Systems Principles (SOSP'95)", 409address = "Copper Mountain, CO", 410month="December", 411year="1995", 412pages="314-321", 413annotation=" 414 Uses a replugger, but with a flag to signal when people are 415 using the resource at hand. Only one reader at a time. 416" 417} 418 419@conference{Cowan96a, 420Author = "Crispin Cowan and Tito Autrey and Charles Krasic and 421Calton Pu and Jonathan Walpole", 422Title = "Fast Concurrent Dynamic Linking for an Adaptive Operating System", 423Booktitle = "International Conference on Configurable Distributed Systems 424(ICCDS'96)", 425address = "Annapolis, MD", 426month="May", 427year="1996", 428pages="108", 429isbn="0-8186-7395-8", 430annotation=" 431 Uses a replugger, but with a counter to signal when people are 432 using the resource at hand. Allows multiple readers. 433" 434} 435 436@techreport{Slingwine95 437,author="John D. Slingwine and Paul E. McKenney" 438,title="Apparatus and Method for Achieving Reduced Overhead Mutual 439Exclusion and Maintaining Coherency in a Multiprocessor System 440Utilizing Execution History and Thread Monitoring" 441,institution="US Patent and Trademark Office" 442,address="Washington, DC" 443,year="1995" 444,number="US Patent 5,442,758" 445,month="August" 446,annotation={ 447 Describes the parallel RCU infrastructure. Includes NUMA aspect 448 (structure of bitmap can reflect bus structure of computer system). 449 . 450 Another independent invention of an RCU-like mechanism, but the 451 "real" RCU this time! 452} 453} 454 455@techreport{Slingwine97 456,author="John D. Slingwine and Paul E. McKenney" 457,title="Method for Maintaining Data Coherency Using Thread Activity 458Summaries in a Multicomputer System" 459,institution="US Patent and Trademark Office" 460,address="Washington, DC" 461,year="1997" 462,number="US Patent 5,608,893" 463,month="March" 464,pages="19" 465,annotation={ 466 Describes use of RCU to synchronize data between a pair of 467 SMP/NUMA computer systems. 468} 469} 470 471@techreport{Slingwine98 472,author="John D. Slingwine and Paul E. McKenney" 473,title="Apparatus and Method for Achieving Reduced Overhead Mutual 474Exclusion and Maintaining Coherency in a Multiprocessor System 475Utilizing Execution History and Thread Monitoring" 476,institution="US Patent and Trademark Office" 477,address="Washington, DC" 478,year="1998" 479,number="US Patent 5,727,209" 480,month="March" 481,annotation={ 482 Describes doing an atomic update by copying the data item and 483 then substituting it into the data structure. 484} 485} 486 487@Conference{McKenney98 488,Author="Paul E. McKenney and John D. Slingwine" 489,Title="Read-Copy Update: Using Execution History to Solve Concurrency 490Problems" 491,Booktitle="{Parallel and Distributed Computing and Systems}" 492,Month="October" 493,Year="1998" 494,pages="509-518" 495,Address="Las Vegas, NV" 496,note="Available: 497\url{http://www.rdrop.com/users/paulmck/RCU/rclockpdcsproof.pdf} 498[Viewed December 3, 2007]" 499,annotation={ 500 Describes and analyzes RCU mechanism in DYNIX/ptx. Describes 501 application to linked list update and log-buffer flushing. 502 Defines 'quiescent state'. Includes both measured and analytic 503 evaluation. 504} 505} 506 507@Conference{Gamsa99 508,Author="Ben Gamsa and Orran Krieger and Jonathan Appavoo and Michael Stumm" 509,Title="Tornado: Maximizing Locality and Concurrency in a Shared Memory 510Multiprocessor Operating System" 511,Booktitle="{Proceedings of the 3\textsuperscript{rd} Symposium on 512Operating System Design and Implementation}" 513,Month="February" 514,Year="1999" 515,pages="87-100" 516,Address="New Orleans, LA" 517,note="Available: 518\url{http://www.usenix.org/events/osdi99/full_papers/gamsa/gamsa.pdf} 519[Viewed August 30, 2006]" 520,annotation={ 521 Use of RCU-like facility in K42/Tornado. Another independent 522 invention of RCU. 523 See especially pages 7-9 (Section 5). 524} 525} 526 527@unpublished{RustyRussell2000a 528,Author="Rusty Russell" 529,Title="Re: modular net drivers" 530,month="June" 531,year="2000" 532,day="23" 533,note="Available: 534\url{http://oss.sgi.com/projects/netdev/archive/2000-06/msg00250.html} 535[Viewed April 10, 2006]" 536,annotation={ 537 Proto-RCU proposal from Phil Rumpf and Rusty Russell. 538 Yet another independent invention of RCU. 539 Outline of algorithm to unload modules... 540 . 541 Appeared on net-dev mailing list. 542} 543} 544 545@unpublished{RustyRussell2000b 546,Author="Rusty Russell" 547,Title="Re: modular net drivers" 548,month="June" 549,year="2000" 550,day="24" 551,note="Available: 552\url{http://oss.sgi.com/projects/netdev/archive/2000-06/msg00254.html} 553[Viewed April 10, 2006]" 554,annotation={ 555 Proto-RCU proposal from Phil Rumpf and Rusty Russell. 556 . 557 Appeared on net-dev mailing list. 558} 559} 560 561@unpublished{McKenney01b 562,Author="Paul E. McKenney and Dipankar Sarma" 563,Title="Read-Copy Update Mutual Exclusion in {Linux}" 564,month="February" 565,year="2001" 566,note="Available: 567\url{http://lse.sourceforge.net/locking/rcu/rcupdate_doc.html} 568[Viewed October 18, 2004]" 569,annotation={ 570 Prototypical Linux documentation for RCU. 571} 572} 573 574@techreport{Slingwine01 575,author="John D. Slingwine and Paul E. McKenney" 576,title="Apparatus and Method for Achieving Reduced Overhead Mutual 577Exclusion and Maintaining Coherency in a Multiprocessor System 578Utilizing Execution History and Thread Monitoring" 579,institution="US Patent and Trademark Office" 580,address="Washington, DC" 581,year="2001" 582,number="US Patent 6,219,690" 583,month="April" 584,annotation={ 585 'Change in mode' aspect of RCU. Can be thought of as a lazy barrier. 586} 587} 588 589@Conference{McKenney01a 590,Author="Paul E. McKenney and Jonathan Appavoo and Andi Kleen and 591Orran Krieger and Rusty Russell and Dipankar Sarma and Maneesh Soni" 592,Title="Read-Copy Update" 593,Booktitle="{Ottawa Linux Symposium}" 594,Month="July" 595,Year="2001" 596,note="Available: 597\url{http://www.linuxsymposium.org/2001/abstracts/readcopy.php} 598\url{http://www.rdrop.com/users/paulmck/RCU/rclock_OLS.2001.05.01c.pdf} 599[Viewed June 23, 2004]" 600,annotation={ 601 Described RCU, and presented some patches implementing and using 602 it in the Linux kernel. 603} 604} 605 606@unpublished{McKenney01f 607,Author="Paul E. McKenney" 608,Title="{RFC:} patch to allow lock-free traversal of lists with insertion" 609,month="October" 610,year="2001" 611,note="Available: 612\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=100259266316456&w=2} 613[Viewed June 23, 2004]" 614,annotation=" 615 Memory-barrier and Alpha thread. 100 messages, not too bad... 616" 617} 618 619@unpublished{Spraul01 620,Author="Manfred Spraul" 621,Title="Re: {RFC:} patch to allow lock-free traversal of lists with insertion" 622,month="October" 623,year="2001" 624,note="Available: 625\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=100264675012867&w=2} 626[Viewed June 23, 2004]" 627,annotation=" 628 Suggested burying memory barriers in Linux's list-manipulation 629 primitives. 630" 631} 632 633@unpublished{LinusTorvalds2001a 634,Author="Linus Torvalds" 635,Title="{Re:} {[Lse-tech]} {Re:} {RFC:} patch to allow lock-free traversal of lists with insertion" 636,month="October" 637,year="2001" 638,note="Available: 639\url{http://lkml.org/lkml/2001/10/13/105} 640[Viewed August 21, 2004]" 641} 642 643@unpublished{Blanchard02a 644,Author="Anton Blanchard" 645,Title="some RCU dcache and ratcache results" 646,month="March" 647,year="2002" 648,note="Available: 649\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=101637107412972&w=2} 650[Viewed October 18, 2004]" 651} 652 653@Conference{Linder02a 654,Author="Hanna Linder and Dipankar Sarma and Maneesh Soni" 655,Title="Scalability of the Directory Entry Cache" 656,Booktitle="{Ottawa Linux Symposium}" 657,Month="June" 658,Year="2002" 659,pages="289-300" 660,annotation=" 661 Measured scalability of Linux 2.4 kernel's directory-entry cache 662 (dcache), and measured some scalability enhancements. 663" 664} 665 666@Conference{McKenney02a 667,Author="Paul E. McKenney and Dipankar Sarma and 668Andrea Arcangeli and Andi Kleen and Orran Krieger and Rusty Russell" 669,Title="Read-Copy Update" 670,Booktitle="{Ottawa Linux Symposium}" 671,Month="June" 672,Year="2002" 673,pages="338-367" 674,note="Available: 675\url{http://www.linux.org.uk/~ajh/ols2002_proceedings.pdf.gz} 676[Viewed June 23, 2004]" 677,annotation=" 678 Presented and compared a number of RCU implementations for the 679 Linux kernel. 680" 681} 682 683@unpublished{Sarma02a 684,Author="Dipankar Sarma" 685,Title="specweb99: dcache scalability results" 686,month="July" 687,year="2002" 688,note="Available: 689\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=102645767914212&w=2} 690[Viewed June 23, 2004]" 691,annotation=" 692 Compare fastwalk and RCU for dcache. RCU won. 693" 694} 695 696@unpublished{Barbieri02 697,Author="Luca Barbieri" 698,Title="Re: {[PATCH]} Initial support for struct {vfs\_cred}" 699,month="August" 700,year="2002" 701,note="Available: 702\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=103082050621241&w=2} 703[Viewed: June 23, 2004]" 704,annotation=" 705 Suggested RCU for vfs\_shared\_cred. 706" 707} 708 709@unpublished{Dickins02a 710,author="Hugh Dickins" 711,title="Use RCU for System-V IPC" 712,year="2002" 713,month="October" 714,note="private communication" 715} 716 717@unpublished{Sarma02b 718,Author="Dipankar Sarma" 719,Title="Some dcache\_rcu benchmark numbers" 720,month="October" 721,year="2002" 722,note="Available: 723\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=103462075416638&w=2} 724[Viewed June 23, 2004]" 725,annotation=" 726 Performance of dcache RCU on kernbench for 16x NUMA-Q and 1x, 727 2x, and 4x systems. RCU does no harm, and helps on 16x. 728" 729} 730 731@unpublished{LinusTorvalds2003a 732,Author="Linus Torvalds" 733,Title="Re: {[PATCH]} small fixes in brlock.h" 734,month="March" 735,year="2003" 736,note="Available: 737\url{http://lkml.org/lkml/2003/3/9/205} 738[Viewed March 13, 2006]" 739,annotation=" 740 Linus suggests replacing brlock with RCU and/or seqlocks: 741 . 742 'It's entirely possible that the current user could be replaced 743 by RCU and/or seqlocks, and we could get rid of brlocks entirely.' 744 . 745 Steve Hemminger responds by replacing them with RCU. 746" 747} 748 749@article{Appavoo03a 750,author="J. Appavoo and K. Hui and C. A. N. Soules and R. W. Wisniewski and 751D. M. {Da Silva} and O. Krieger and M. A. Auslander and D. J. Edelsohn and 752B. Gamsa and G. R. Ganger and P. McKenney and M. Ostrowski and 753B. Rosenburg and M. Stumm and J. Xenidis" 754,title="Enabling Autonomic Behavior in Systems Software With Hot Swapping" 755,Year="2003" 756,Month="January" 757,journal="IBM Systems Journal" 758,volume="42" 759,number="1" 760,pages="60-76" 761,annotation=" 762 Use of RCU to enable hot-swapping for autonomic behavior in K42. 763" 764} 765 766@unpublished{Seigh03 767,author="Joseph W. {Seigh II}" 768,title="Read Copy Update" 769,Year="2003" 770,Month="March" 771,note="email correspondence" 772,annotation=" 773 Described the relationship of the VM/XA passive serialization to RCU. 774" 775} 776 777@Conference{Arcangeli03 778,Author="Andrea Arcangeli and Mingming Cao and Paul E. McKenney and 779Dipankar Sarma" 780,Title="Using Read-Copy Update Techniques for {System V IPC} in the 781{Linux} 2.5 Kernel" 782,Booktitle="Proceedings of the 2003 USENIX Annual Technical Conference 783(FREENIX Track)" 784,Publisher="USENIX Association" 785,year="2003" 786,month="June" 787,pages="297-310" 788,note="Available: 789\url{http://www.rdrop.com/users/paulmck/RCU/rcu.FREENIX.2003.06.14.pdf} 790[Viewed November 21, 2007]" 791,annotation=" 792 Compared updated RCU implementations for the Linux kernel, and 793 described System V IPC use of RCU, including order-of-magnitude 794 performance improvements. 795" 796} 797 798@Conference{Soules03a 799,Author="Craig A. N. Soules and Jonathan Appavoo and Kevin Hui and 800Dilma {Da Silva} and Gregory R. Ganger and Orran Krieger and 801Michael Stumm and Robert W. Wisniewski and Marc Auslander and 802Michal Ostrowski and Bryan Rosenburg and Jimi Xenidis" 803,Title="System Support for Online Reconfiguration" 804,Booktitle="Proceedings of the 2003 USENIX Annual Technical Conference" 805,Publisher="USENIX Association" 806,year="2003" 807,month="June" 808,pages="141-154" 809} 810 811@article{McKenney03a 812,author="Paul E. McKenney" 813,title="Using {RCU} in the {Linux} 2.5 Kernel" 814,Year="2003" 815,Month="October" 816,journal="Linux Journal" 817,volume="1" 818,number="114" 819,pages="18-26" 820,note="Available: 821\url{http://www.linuxjournal.com/article/6993} 822[Viewed November 14, 2007]" 823,annotation=" 824 Reader-friendly intro to RCU, with the infamous old-man-and-brat 825 cartoon. 826" 827} 828 829@unpublished{Sarma03a 830,Author="Dipankar Sarma" 831,Title="RCU low latency patches" 832,month="December" 833,year="2003" 834,note="Message ID: 20031222180114.GA2248@in.ibm.com" 835,annotation="dipankar/ct.2004.03.27/RCUll.2003.12.22.patch" 836} 837 838@techreport{Friedberg03a 839,author="Stuart A. Friedberg" 840,title="Lock-Free Wild Card Search Data Structure and Method" 841,institution="US Patent and Trademark Office" 842,address="Washington, DC" 843,year="2003" 844,number="US Patent 6,662,184" 845,month="December" 846,pages="112" 847,annotation=" 848 Applies RCU to a wildcard-search Patricia tree in order to permit 849 synchronization-free lookup. RCU is used to retain removed nodes 850 for a grace period before freeing them. 851" 852} 853 854@article{McKenney04a 855,author="Paul E. McKenney and Dipankar Sarma and Maneesh Soni" 856,title="Scaling dcache with {RCU}" 857,Year="2004" 858,Month="January" 859,journal="Linux Journal" 860,volume="1" 861,number="118" 862,pages="38-46" 863,note="Available: 864\url{http://www.linuxjournal.com/node/7124} 865[Viewed December 26, 2010]" 866,annotation=" 867 Reader friendly intro to dcache and RCU. 868" 869} 870 871@Conference{McKenney04b 872,Author="Paul E. McKenney" 873,Title="{RCU} vs. Locking Performance on Different {CPUs}" 874,Booktitle="{linux.conf.au}" 875,Month="January" 876,Year="2004" 877,Address="Adelaide, Australia" 878,note="Available: 879\url{http://www.linux.org.au/conf/2004/abstracts.html#90} 880\url{http://www.rdrop.com/users/paulmck/RCU/lockperf.2004.01.17a.pdf} 881[Viewed June 23, 2004]" 882,annotation=" 883 Compares performance of RCU to that of other locking primitives 884 over a number of CPUs (x86, Opteron, Itanium, and PPC). 885" 886} 887 888@unpublished{Sarma04a 889,Author="Dipankar Sarma" 890,Title="{[PATCH]} {RCU} for low latency (experimental)" 891,month="March" 892,year="2004" 893,note="\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=108003746402892&w=2}" 894,annotation="Head of thread: dipankar/2004.03.23/rcu-low-lat.1.patch" 895} 896 897@unpublished{Sarma04b 898,Author="Dipankar Sarma" 899,Title="Re: {[PATCH]} {RCU} for low latency (experimental)" 900,month="March" 901,year="2004" 902,note="\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=108016474829546&w=2}" 903,annotation="dipankar/rcuth.2004.03.24/rcu-throttle.patch" 904} 905 906@unpublished{Spraul04a 907,Author="Manfred Spraul" 908,Title="[RFC] 0/5 rcu lock update" 909,month="May" 910,year="2004" 911,note="Available: 912\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=108546407726602&w=2} 913[Viewed June 23, 2004]" 914,annotation=" 915 Hierarchical-bitmap patch for RCU infrastructure. 916" 917} 918 919@unpublished{Steiner04a 920,Author="Jack Steiner" 921,Title="Re: [Lse-tech] [RFC, PATCH] 1/5 rcu lock update: 922Add per-cpu batch counter" 923,month="May" 924,year="2004" 925,note="Available: 926\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=108551764515332&w=2} 927[Viewed June 23, 2004]" 928,annotation={ 929 RCU runs reasonably on a 512-CPU SGI using Manfred Spraul's patches, 930 which may be found at: 931 https://lkml.org/lkml/2004/5/20/49 (split vars into cachelines) 932 https://lkml.org/lkml/2004/5/22/114 (cpu_quiet() patch) 933 https://lkml.org/lkml/2004/5/25/24 (0/5) 934 https://lkml.org/lkml/2004/5/25/23 (1/5) 935 https://lkml.org/lkml/2004/5/25/265 (works for Jack) 936 https://lkml.org/lkml/2004/5/25/20 (2/5) 937 https://lkml.org/lkml/2004/5/25/22 (3/5) 938 https://lkml.org/lkml/2004/5/25/19 (4/5) 939 https://lkml.org/lkml/2004/5/25/21 (5/5) 940} 941} 942 943@Conference{Sarma04c 944,Author="Dipankar Sarma and Paul E. McKenney" 945,Title="Making {RCU} Safe for Deep Sub-Millisecond Response 946Realtime Applications" 947,Booktitle="Proceedings of the 2004 USENIX Annual Technical Conference 948(FREENIX Track)" 949,Publisher="USENIX Association" 950,year="2004" 951,month="June" 952,pages="182-191" 953,annotation=" 954 Describes and compares a number of modifications to the Linux RCU 955 implementation that make it friendly to realtime applications. 956" 957} 958 959@phdthesis{PaulEdwardMcKenneyPhD 960,author="Paul E. McKenney" 961,title="Exploiting Deferred Destruction: 962An Analysis of Read-Copy-Update Techniques 963in Operating System Kernels" 964,school="OGI School of Science and Engineering at 965Oregon Health and Sciences University" 966,year="2004" 967,note="Available: 968\url{http://www.rdrop.com/users/paulmck/RCU/RCUdissertation.2004.07.14e1.pdf} 969[Viewed October 15, 2004]" 970,annotation=" 971 Describes RCU implementations and presents design patterns 972 corresponding to common uses of RCU in several operating-system 973 kernels. 974" 975} 976 977@unpublished{PaulEMcKenney2004rcu:dereference 978,Author="Dipankar Sarma" 979,Title="{Re: RCU : Abstracted RCU dereferencing [5/5]}" 980,month="August" 981,year="2004" 982,note="Available: 983\url{http://lkml.org/lkml/2004/8/6/237} 984[Viewed June 8, 2010]" 985,annotation=" 986 Introduce rcu_dereference(). 987" 988} 989 990@unpublished{JimHouston04a 991,Author="Jim Houston" 992,Title="{[RFC\&PATCH] Alternative {RCU} implementation}" 993,month="August" 994,year="2004" 995,note="Available: 996\url{http://lkml.org/lkml/2004/8/30/87} 997[Viewed February 17, 2005]" 998,annotation=" 999 Uses active code in rcu_read_lock() and rcu_read_unlock() to 1000 make RCU happen, allowing RCU to function on CPUs that do not 1001 receive a scheduling-clock interrupt. 1002" 1003} 1004 1005@unpublished{TomHart04a 1006,Author="Thomas E. Hart" 1007,Title="Master's Thesis: Applying Lock-free Techniques to the {Linux} Kernel" 1008,month="October" 1009,year="2004" 1010,note="Available: 1011\url{http://www.cs.toronto.edu/~tomhart/masters_thesis.html} 1012[Viewed October 15, 2004]" 1013,annotation=" 1014 Proposes comparing RCU to lock-free methods for the Linux kernel. 1015" 1016} 1017 1018@unpublished{Vaddagiri04a 1019,Author="Srivatsa Vaddagiri" 1020,Title="Subject: [RFC] Use RCU for tcp\_ehash lookup" 1021,month="October" 1022,year="2004" 1023,note="Available: 1024\url{http://marc.theaimsgroup.com/?t=109395731700004&r=1&w=2} 1025[Viewed October 18, 2004]" 1026,annotation=" 1027 Srivatsa's RCU patch for tcp_ehash lookup. 1028" 1029} 1030 1031@unpublished{Thirumalai04a 1032,Author="Ravikiran Thirumalai" 1033,Title="Subject: [patchset] Lockfree fd lookup 0 of 5" 1034,month="October" 1035,year="2004" 1036,note="Available: 1037\url{http://marc.theaimsgroup.com/?t=109144217400003&r=1&w=2} 1038[Viewed October 18, 2004]" 1039,annotation=" 1040 Ravikiran's lockfree FD patch. 1041" 1042} 1043 1044@unpublished{Thirumalai04b 1045,Author="Ravikiran Thirumalai" 1046,Title="Subject: Re: [patchset] Lockfree fd lookup 0 of 5" 1047,month="October" 1048,year="2004" 1049,note="Available: 1050\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=109152521410459&w=2} 1051[Viewed October 18, 2004]" 1052,annotation=" 1053 Ravikiran's lockfree FD patch. 1054" 1055} 1056 1057@unpublished{PaulEMcKenney2004rcu:assign:pointer 1058,Author="Paul E. McKenney" 1059,Title="{[PATCH 1/3] RCU: \url{rcu_assign_pointer()} removal of memory barriers}" 1060,month="October" 1061,year="2004" 1062,note="Available: 1063\url{http://lkml.org/lkml/2004/10/23/241} 1064[Viewed June 8, 2010]" 1065,annotation=" 1066 Introduce rcu_assign_pointer(). 1067" 1068} 1069 1070@unpublished{JamesMorris04a 1071,Author="James Morris" 1072,Title="{[PATCH 2/3] SELinux} scalability - convert {AVC} to {RCU}" 1073,day="15" 1074,month="November" 1075,year="2004" 1076,note="Available: 1077\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=110054979416004&w=2} 1078[Viewed December 10, 2004]" 1079,annotation=" 1080 James Morris posts Kaigai Kohei's patch to LKML. 1081" 1082} 1083 1084@unpublished{JamesMorris04b 1085,Author="James Morris" 1086,Title="Recent Developments in {SELinux} Kernel Performance" 1087,month="December" 1088,year="2004" 1089,note="Available: 1090\url{http://www.livejournal.com/users/james_morris/2153.html} 1091[Viewed December 10, 2004]" 1092,annotation=" 1093 RCU helps SELinux performance. ;-) Made LWN. 1094" 1095} 1096 1097@unpublished{PaulMcKenney2005RCUSemantics 1098,Author="Paul E. McKenney and Jonathan Walpole" 1099,Title="{RCU} Semantics: A First Attempt" 1100,month="January" 1101,year="2005" 1102,day="30" 1103,note="Available: 1104\url{http://www.rdrop.com/users/paulmck/RCU/rcu-semantics.2005.01.30a.pdf} 1105[Viewed December 6, 2009]" 1106,annotation=" 1107 Early derivation of RCU semantics. 1108" 1109} 1110 1111@unpublished{PaulMcKenney2005e 1112,Author="Paul E. McKenney" 1113,Title="Real-Time Preemption and {RCU}" 1114,month="March" 1115,year="2005" 1116,day="17" 1117,note="Available: 1118\url{http://lkml.org/lkml/2005/3/17/199} 1119[Viewed September 5, 2005]" 1120,annotation=" 1121 First posting showing how RCU can be safely adapted for 1122 preemptable RCU read side critical sections. 1123" 1124} 1125 1126@unpublished{EsbenNeilsen2005a 1127,Author="Esben Neilsen" 1128,Title="Re: Real-Time Preemption and {RCU}" 1129,month="March" 1130,year="2005" 1131,day="18" 1132,note="Available: 1133\url{http://lkml.org/lkml/2005/3/18/122} 1134[Viewed March 30, 2006]" 1135,annotation=" 1136 Esben Neilsen suggests read-side suppression of grace-period 1137 processing for crude-but-workable realtime RCU. The downside 1138 is indefinite grace periods...But this is OK for experimentation 1139 and testing. 1140" 1141} 1142 1143@unpublished{TomHart05a 1144,Author="Thomas E. Hart and Paul E. McKenney and Angela Demke Brown" 1145,Title="Efficient Memory Reclamation is Necessary for Fast Lock-Free 1146Data Structures" 1147,month="March" 1148,year="2005" 1149,note="Available: 1150\url{ftp://ftp.cs.toronto.edu/csrg-technical-reports/515/} 1151[Viewed March 4, 2005]" 1152,annotation=" 1153 Comparison of RCU, QBSR, and EBSR. RCU wins for read-mostly 1154 workloads. ;-) 1155" 1156} 1157 1158@unpublished{JonCorbet2005DeprecateSyncKernel 1159,Author="Jonathan Corbet" 1160,Title="API change: synchronize_kernel() deprecated" 1161,month="May" 1162,day="3" 1163,year="2005" 1164,note="Available: 1165\url{http://lwn.net/Articles/134484/} 1166[Viewed May 3, 2005]" 1167,annotation=" 1168 Jon Corbet describes deprecation of synchronize_kernel() 1169 in favor of synchronize_rcu() and synchronize_sched(). 1170" 1171} 1172 1173@unpublished{PaulMcKenney05a 1174,Author="Paul E. McKenney" 1175,Title="{[RFC]} {RCU} and {CONFIG\_PREEMPT\_RT} progress" 1176,month="May" 1177,year="2005" 1178,note="Available: 1179\url{http://lkml.org/lkml/2005/5/9/185} 1180[Viewed May 13, 2005]" 1181,annotation=" 1182 First publication of working lock-based deferred free patches 1183 for the CONFIG_PREEMPT_RT environment. 1184" 1185} 1186 1187@conference{PaulMcKenney05b 1188,Author="Paul E. McKenney and Dipankar Sarma" 1189,Title="Towards Hard Realtime Response from the {Linux} Kernel on {SMP} Hardware" 1190,Booktitle="linux.conf.au 2005" 1191,month="April" 1192,year="2005" 1193,address="Canberra, Australia" 1194,note="Available: 1195\url{http://www.rdrop.com/users/paulmck/RCU/realtimeRCU.2005.04.23a.pdf} 1196[Viewed May 13, 2005]" 1197,annotation=" 1198 Realtime turns into making RCU yet more realtime friendly. 1199 http://lca2005.linux.org.au/Papers/Paul%20McKenney/Towards%20Hard%20Realtime%20Response%20from%20the%20Linux%20Kernel/LKS.2005.04.22a.pdf 1200" 1201} 1202 1203@unpublished{PaulEMcKenneyHomePage 1204,Author="Paul E. McKenney" 1205,Title="{Paul} {E.} {McKenney}" 1206,month="May" 1207,year="2005" 1208,note="Available: 1209\url{http://www.rdrop.com/users/paulmck/} 1210[Viewed May 25, 2005]" 1211,annotation=" 1212 Paul McKenney's home page. 1213" 1214} 1215 1216@unpublished{PaulEMcKenneyRCUPage 1217,Author="Paul E. McKenney" 1218,Title="Read-Copy Update {(RCU)}" 1219,month="May" 1220,year="2005" 1221,note="Available: 1222\url{http://www.rdrop.com/users/paulmck/RCU} 1223[Viewed May 25, 2005]" 1224,annotation=" 1225 Paul McKenney's RCU page. 1226" 1227} 1228 1229@unpublished{JosephSeigh2005a 1230,Author="Joseph Seigh" 1231,Title="{RCU}+{SMR} (hazard pointers)" 1232,month="July" 1233,year="2005" 1234,note="Personal communication" 1235,annotation=" 1236 Joe Seigh announcing his atomic-ptr-plus project. 1237 http://sourceforge.net/projects/atomic-ptr-plus/ 1238" 1239} 1240 1241@unpublished{JosephSeigh2005b 1242,Author="Joseph Seigh" 1243,Title="Lock-free synchronization primitives" 1244,month="July" 1245,day="6" 1246,year="2005" 1247,note="Available: 1248\url{http://sourceforge.net/projects/atomic-ptr-plus/} 1249[Viewed August 8, 2005]" 1250,annotation=" 1251 Joe Seigh's atomic-ptr-plus project. 1252" 1253} 1254 1255@unpublished{PaulMcKenney2005c 1256,Author="Paul E.McKenney" 1257,Title="{[RFC,PATCH] RCU} and {CONFIG\_PREEMPT\_RT} sane patch" 1258,month="August" 1259,day="1" 1260,year="2005" 1261,note="Available: 1262\url{http://lkml.org/lkml/2005/8/1/155} 1263[Viewed March 14, 2006]" 1264,annotation=" 1265 First operating counter-based realtime RCU patch posted to LKML. 1266" 1267} 1268 1269@unpublished{PaulMcKenney2005d 1270,Author="Paul E. McKenney" 1271,Title="Re: [Fwd: Re: [patch] Real-Time Preemption, -RT-2.6.13-rc4-V0.7.52-01]" 1272,month="August" 1273,day="8" 1274,year="2005" 1275,note="Available: 1276\url{http://lkml.org/lkml/2005/8/8/108} 1277[Viewed March 14, 2006]" 1278,annotation=" 1279 First operating counter-based realtime RCU patch posted to LKML, 1280 but fixed so that various unusual combinations of configuration 1281 parameters all function properly. 1282" 1283} 1284 1285@unpublished{PaulMcKenney2005rcutorture 1286,Author="Paul E. McKenney" 1287,Title="{[PATCH]} {RCU} torture testing" 1288,month="October" 1289,day="1" 1290,year="2005" 1291,note="Available: 1292\url{http://lkml.org/lkml/2005/10/1/70} 1293[Viewed March 14, 2006]" 1294,annotation=" 1295 First rcutorture patch. 1296" 1297} 1298 1299@conference{ThomasEHart2006a 1300,Author="Thomas E. Hart and Paul E. McKenney and Angela Demke Brown" 1301,Title="Making Lockless Synchronization Fast: Performance Implications 1302of Memory Reclamation" 1303,Booktitle="20\textsuperscript{th} {IEEE} International Parallel and 1304Distributed Processing Symposium" 1305,month="April" 1306,year="2006" 1307,day="25-29" 1308,address="Rhodes, Greece" 1309,note="Available: 1310\url{http://www.rdrop.com/users/paulmck/RCU/hart_ipdps06.pdf} 1311[Viewed April 28, 2008]" 1312,annotation=" 1313 Compares QSBR, HPBR, EBR, and lock-free reference counting. 1314 http://www.cs.toronto.edu/~tomhart/perflab/ipdps06.tgz 1315" 1316} 1317 1318@unpublished{NickPiggin2006radixtree 1319,Author="Nick Piggin" 1320,Title="[patch 3/3] radix-tree: {RCU} lockless readside" 1321,month="June" 1322,day="20" 1323,year="2006" 1324,note="Available: 1325\url{http://lkml.org/lkml/2006/6/20/238} 1326[Viewed March 25, 2008]" 1327,annotation=" 1328 RCU-protected radix tree. 1329" 1330} 1331 1332@Conference{PaulEMcKenney2006b 1333,Author="Paul E. McKenney and Dipankar Sarma and Ingo Molnar and 1334Suparna Bhattacharya" 1335,Title="Extending {RCU} for Realtime and Embedded Workloads" 1336,Booktitle="{Ottawa Linux Symposium}" 1337,Month="July" 1338,Year="2006" 1339,pages="v2 123-138" 1340,note="Available: 1341\url{http://www.linuxsymposium.org/2006/view_abstract.php?content_key=184} 1342\url{http://www.rdrop.com/users/paulmck/RCU/OLSrtRCU.2006.08.11a.pdf} 1343[Viewed January 1, 2007]" 1344,annotation=" 1345 Described how to improve the -rt implementation of realtime RCU. 1346" 1347} 1348 1349@unpublished{WikipediaRCU 1350,Author="Paul E. McKenney and Chris Purcell and Algae and Ben Schumin and 1351Gaius Cornelius and Qwertyus and Neil Conway and Sbw and Blainster and 1352Canis Rufus and Zoicon5 and Anome and Hal Eisen" 1353,Title="Read-Copy Update" 1354,month="July" 1355,day="8" 1356,year="2006" 1357,note="Available: 1358\url{http://en.wikipedia.org/wiki/Read-copy-update} 1359[Viewed August 21, 2006]" 1360,annotation=" 1361 Wikipedia RCU page as of July 8 2006. 1362" 1363} 1364 1365@Conference{NickPiggin2006LocklessPageCache 1366,Author="Nick Piggin" 1367,Title="A Lockless Pagecache in Linux---Introduction, Progress, Performance" 1368,Booktitle="{Ottawa Linux Symposium}" 1369,Month="July" 1370,Year="2006" 1371,pages="v2 249-254" 1372,note="Available: 1373\url{http://www.linuxsymposium.org/2006/view_abstract.php?content_key=184} 1374[Viewed January 11, 2009]" 1375,annotation=" 1376 Uses RCU-protected radix tree for a lockless page cache. 1377" 1378} 1379 1380@unpublished{PaulEMcKenney2006c 1381,Author="Paul E. McKenney" 1382,Title="Sleepable {RCU}" 1383,month="October" 1384,day="9" 1385,year="2006" 1386,note="Available: 1387\url{http://lwn.net/Articles/202847/} 1388Revised: 1389\url{http://www.rdrop.com/users/paulmck/RCU/srcu.2007.01.14a.pdf} 1390[Viewed August 21, 2006]" 1391,annotation=" 1392 LWN article introducing SRCU. 1393" 1394} 1395 1396@unpublished{RobertOlsson2006a 1397,Author="Robert Olsson and Stefan Nilsson" 1398,Title="{TRASH}: A dynamic {LC}-trie and hash data structure" 1399,month="August" 1400,day="18" 1401,year="2006" 1402,note="Available: 1403\url{http://www.nada.kth.se/~snilsson/publications/TRASH/trash.pdf} 1404[Viewed March 4, 2011]" 1405,annotation=" 1406 RCU-protected dynamic trie-hash combination. 1407" 1408} 1409 1410@unpublished{ChristophHellwig2006RCU2SRCU 1411,Author="Christoph Hellwig" 1412,Title="Re: {[-mm PATCH 1/4]} {RCU}: split classic rcu" 1413,month="September" 1414,day="28" 1415,year="2006" 1416,note="Available: 1417\url{http://lkml.org/lkml/2006/9/28/160} 1418[Viewed March 27, 2008]" 1419} 1420 1421@unpublished{PaulEMcKenneyRCUusagePage 1422,Author="Paul E. McKenney" 1423,Title="{RCU} {Linux} Usage" 1424,month="October" 1425,year="2006" 1426,note="Available: 1427\url{http://www.rdrop.com/users/paulmck/RCU/linuxusage.html} 1428[Viewed January 14, 2007]" 1429,annotation=" 1430 Paul McKenney's RCU page showing graphs plotting Linux-kernel 1431 usage of RCU. 1432" 1433} 1434 1435@unpublished{PaulEMcKenneyRCUusageRawDataPage 1436,Author="Paul E. McKenney" 1437,Title="Read-Copy Update {(RCU)} Usage in {Linux} Kernel" 1438,month="October" 1439,year="2006" 1440,note="Available: 1441\url{http://www.rdrop.com/users/paulmck/RCU/linuxusage/rculocktab.html} 1442[Viewed January 14, 2007]" 1443,annotation=" 1444 Paul McKenney's RCU page showing Linux usage of RCU in tabular 1445 form, with links to corresponding cscope databases. 1446" 1447} 1448 1449@unpublished{GauthamShenoy2006RCUrwlock 1450,Author="Gautham R. Shenoy" 1451,Title="[PATCH 4/5] lock\_cpu\_hotplug: Redesign - Lightweight implementation of lock\_cpu\_hotplug" 1452,month="October" 1453,year="2006" 1454,day=26 1455,note="Available: 1456\url{http://lkml.org/lkml/2006/10/26/73} 1457[Viewed January 26, 2009]" 1458,annotation=" 1459 RCU-based reader-writer lock that allows readers to proceed with 1460 no memory barriers or atomic instruction in absence of writers. 1461 If writer do show up, readers must of course wait as required by 1462 the semantics of reader-writer locking. This is a recursive 1463 lock. 1464" 1465} 1466 1467@unpublished{JensAxboe2006SlowSRCU 1468,Author="Jens Axboe" 1469,Title="Re: [patch] cpufreq: mark \url{cpufreq_tsc()} as 1470\url{core_initcall_sync}" 1471,month="November" 1472,year="2006" 1473,day=17 1474,note="Available: 1475\url{http://lkml.org/lkml/2006/11/17/56} 1476[Viewed May 28, 2007]" 1477,annotation=" 1478 SRCU's grace periods are too slow for Jens, even after a 1479 factor-of-three speedup. 1480 Sped-up version of SRCU at http://lkml.org/lkml/2006/11/17/359. 1481" 1482} 1483 1484@unpublished{OlegNesterov2006QRCU 1485,Author="Oleg Nesterov" 1486,Title="Re: [patch] cpufreq: mark {\tt cpufreq\_tsc()} as 1487{\tt core\_initcall\_sync}" 1488,month="November" 1489,year="2006" 1490,day=19 1491,note="Available: 1492\url{http://lkml.org/lkml/2006/11/19/69} 1493[Viewed May 28, 2007]" 1494,annotation=" 1495 First cut of QRCU. Expanded/corrected versions followed. 1496 Used to be OlegNesterov2007QRCU, now time-corrected. 1497" 1498} 1499 1500@unpublished{OlegNesterov2006aQRCU 1501,Author="Oleg Nesterov" 1502,Title="Re: [RFC, PATCH 1/2] qrcu: {"quick"} srcu implementation" 1503,month="November" 1504,year="2006" 1505,day=30 1506,note="Available: 1507\url{http://lkml.org/lkml/2006/11/29/330} 1508[Viewed November 26, 2008]" 1509,annotation=" 1510 Expanded/corrected version of QRCU. 1511 Used to be OlegNesterov2007aQRCU, now time-corrected. 1512" 1513} 1514 1515@unpublished{EvgeniyPolyakov2006RCUslowdown 1516,Author="Evgeniy Polyakov" 1517,Title="Badness in postponing work" 1518,month="December" 1519,year="2006" 1520,day=05 1521,note="Available: 1522\url{http://www.ioremap.net/node/41} 1523[Viewed October 28, 2008]" 1524,annotation=" 1525 Using RCU as a pure delay leads to a 2.5x slowdown in skbs in 1526 the Linux kernel. 1527" 1528} 1529 1530@inproceedings{ChrisMatthews2006ClusteredObjectsRCU 1531,author = {Matthews, Chris and Coady, Yvonne and Appavoo, Jonathan} 1532,title = {Portability events: a programming model for scalable system infrastructures} 1533,booktitle = {PLOS '06: Proceedings of the 3rd workshop on Programming languages and operating systems} 1534,year = {2006} 1535,isbn = {1-59593-577-0} 1536,pages = {11} 1537,location = {San Jose, California} 1538,doi = {http://doi.acm.org/10.1145/1215995.1216006} 1539,publisher = {ACM} 1540,address = {New York, NY, USA} 1541,annotation={ 1542 Uses K42's RCU-like functionality to manage clustered-object 1543 lifetimes. 1544}} 1545 1546@article{DilmaDaSilva2006K42 1547,author = {Silva, Dilma Da and Krieger, Orran and Wisniewski, Robert W. and Waterland, Amos and Tam, David and Baumann, Andrew} 1548,title = {K42: an infrastructure for operating system research} 1549,journal = {SIGOPS Oper. Syst. Rev.} 1550,volume = {40} 1551,number = {2} 1552,year = {2006} 1553,issn = {0163-5980} 1554,pages = {34--42} 1555,doi = {http://doi.acm.org/10.1145/1131322.1131333} 1556,publisher = {ACM} 1557,address = {New York, NY, USA} 1558,annotation={ 1559 Describes relationship of K42 generations to RCU. 1560}} 1561 1562# CoreyMinyard2007list_splice_rcu 1563@unpublished{CoreyMinyard2007list:splice:rcu 1564,Author="Corey Minyard and Paul E. McKenney" 1565,Title="{[PATCH]} add an {RCU} version of list splicing" 1566,month="January" 1567,year="2007" 1568,day=3 1569,note="Available: 1570\url{http://lkml.org/lkml/2007/1/3/112} 1571[Viewed May 28, 2007]" 1572,annotation=" 1573 Patch for list_splice_rcu(). 1574" 1575} 1576 1577@unpublished{PaulEMcKenney2007rcubarrier 1578,Author="Paul E. McKenney" 1579,Title="{RCU} and Unloadable Modules" 1580,month="January" 1581,day="14" 1582,year="2007" 1583,note="Available: 1584\url{http://lwn.net/Articles/217484/} 1585[Viewed November 22, 2007]" 1586,annotation=" 1587 LWN article introducing the rcu_barrier() primitive. 1588" 1589} 1590 1591@unpublished{PeterZijlstra2007SyncBarrier 1592,Author="Peter Zijlstra and Ingo Molnar" 1593,Title="{[PATCH 3/7]} barrier: a scalable synchonisation barrier" 1594,month="January" 1595,year="2007" 1596,day=28 1597,note="Available: 1598\url{http://lkml.org/lkml/2007/1/28/34} 1599[Viewed March 27, 2008]" 1600,annotation=" 1601 RCU-like implementation for frequent updaters and rare readers(!). 1602 Subsumed into QRCU. Maybe... 1603" 1604} 1605 1606@unpublished{PaulEMcKenney2007BoostRCU 1607,Author="Paul E. McKenney" 1608,Title="Priority-Boosting {RCU} Read-Side Critical Sections" 1609,month="February" 1610,day="5" 1611,year="2007" 1612,note="Available: 1613\url{http://lwn.net/Articles/220677/} 1614Revised: 1615\url{http://www.rdrop.com/users/paulmck/RCU/RCUbooststate.2007.04.16a.pdf} 1616[Viewed September 7, 2007]" 1617,annotation=" 1618 LWN article introducing RCU priority boosting. 1619" 1620} 1621 1622@unpublished{PaulMcKenney2007QRCUpatch 1623,Author="Paul E. McKenney" 1624,Title="{[PATCH]} {QRCU} with lockless fastpath" 1625,month="February" 1626,year="2007" 1627,day=24 1628,note="Available: 1629\url{http://lkml.org/lkml/2007/2/25/18} 1630[Viewed March 27, 2008]" 1631,annotation=" 1632 Patch for QRCU supplying lock-free fast path. 1633" 1634} 1635 1636@article{JonathanAppavoo2007K42RCU 1637,author = {Appavoo, Jonathan and Silva, Dilma Da and Krieger, Orran and Auslander, Marc and Ostrowski, Michal and Rosenburg, Bryan and Waterland, Amos and Wisniewski, Robert W. and Xenidis, Jimi and Stumm, Michael and Soares, Livio} 1638,title = {Experience distributing objects in an SMMP OS} 1639,journal = {ACM Trans. Comput. Syst.} 1640,volume = {25} 1641,number = {3} 1642,year = {2007} 1643,issn = {0734-2071} 1644,pages = {6/1--6/52} 1645,doi = {http://doi.acm.org/10.1145/1275517.1275518} 1646,publisher = {ACM} 1647,address = {New York, NY, USA} 1648,annotation={ 1649 Role of RCU in K42. 1650}} 1651 1652@conference{RobertOlsson2007Trash 1653,Author="Robert Olsson and Stefan Nilsson" 1654,Title="{TRASH}: A dynamic {LC}-trie and hash data structure" 1655,booktitle="Workshop on High Performance Switching and Routing (HPSR'07)" 1656,month="May" 1657,year="2007" 1658,note="Available: 1659\url{http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4281239} 1660[Viewed October 1, 2010]" 1661,annotation=" 1662 RCU-protected dynamic trie-hash combination. 1663" 1664} 1665 1666@conference{PeterZijlstra2007ConcurrentPagecacheRCU 1667,Author="Peter Zijlstra" 1668,Title="Concurrent Pagecache" 1669,Booktitle="Linux Symposium" 1670,month="June" 1671,year="2007" 1672,address="Ottawa, Canada" 1673,note="Available: 1674\url{http://ols.108.redhat.com/2007/Reprints/zijlstra-Reprint.pdf} 1675[Viewed April 14, 2008]" 1676,annotation=" 1677 Page-cache modifications permitting RCU readers and concurrent 1678 updates. 1679" 1680} 1681 1682@unpublished{PaulEMcKenney2007whatisRCU 1683,Author="Paul E. McKenney" 1684,Title="What is {RCU}?" 1685,year="2007" 1686,month="07" 1687,note="Available: 1688\url{http://www.rdrop.com/users/paulmck/RCU/whatisRCU.html} 1689[Viewed July 6, 2007]" 1690,annotation={ 1691 Describes RCU in Linux kernel. 1692} 1693} 1694 1695@unpublished{PaulEMcKenney2007QRCUspin 1696,Author="Paul E. McKenney" 1697,Title="Using {Promela} and {Spin} to verify parallel algorithms" 1698,month="August" 1699,day="1" 1700,year="2007" 1701,note="Available: 1702\url{http://lwn.net/Articles/243851/} 1703[Viewed September 8, 2007]" 1704,annotation=" 1705 LWN article describing Promela and spin, and also using Oleg 1706 Nesterov's QRCU as an example (with Paul McKenney's fastpath). 1707 Merged patch at: http://lkml.org/lkml/2007/2/25/18 1708" 1709} 1710 1711@unpublished{PaulEMcKenney2007WG21DDOatomics 1712,Author="Paul E. McKenney and Hans-J. Boehm and Lawrence Crowl" 1713,Title="C++ Data-Dependency Ordering: Atomics and Memory Model" 1714,month="August" 1715,day="3" 1716,year="2007" 1717,note="Preprint: 1718\url{http://open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2664.htm} 1719[Viewed December 7, 2009]" 1720,annotation=" 1721 RCU for C++, parts 1 and 2. 1722" 1723} 1724 1725@unpublished{PaulEMcKenney2007WG21DDOannotation 1726,Author="Paul E. McKenney and Lawrence Crowl" 1727,Title="C++ Data-Dependency Ordering: Function Annotation" 1728,month="September" 1729,day="18" 1730,year="2008" 1731,note="Preprint: 1732\url{http://open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2782.htm} 1733[Viewed December 7, 2009]" 1734,annotation=" 1735 RCU for C++, part 2, updated many times. 1736" 1737} 1738 1739@unpublished{PaulEMcKenney2007PreemptibleRCUPatch 1740,Author="Paul E. McKenney" 1741,Title="[PATCH RFC 0/9] {RCU}: Preemptible {RCU}" 1742,month="September" 1743,day="10" 1744,year="2007" 1745,note="Available: 1746\url{http://lkml.org/lkml/2007/9/10/213} 1747[Viewed October 25, 2007]" 1748,annotation=" 1749 Final patch for preemptable RCU to -rt. (Later patches were 1750 to mainline, eventually incorporated.) 1751" 1752} 1753 1754@unpublished{PaulEMcKenney2007PreemptibleRCU 1755,Author="Paul E. McKenney" 1756,Title="The design of preemptible read-copy-update" 1757,month="October" 1758,day="8" 1759,year="2007" 1760,note="Available: 1761\url{http://lwn.net/Articles/253651/} 1762[Viewed October 25, 2007]" 1763,annotation=" 1764 LWN article describing the design of preemptible RCU. 1765" 1766} 1767 1768@article{ThomasEHart2007a 1769,Author="Thomas E. Hart and Paul E. McKenney and Angela Demke Brown and Jonathan Walpole" 1770,Title="Performance of memory reclamation for lockless synchronization" 1771,journal="J. Parallel Distrib. Comput." 1772,volume={67} 1773,number="12" 1774,year="2007" 1775,issn="0743-7315" 1776,pages="1270--1285" 1777,doi="http://dx.doi.org/10.1016/j.jpdc.2007.04.010" 1778,publisher="Academic Press, Inc." 1779,address="Orlando, FL, USA" 1780,annotation={ 1781 Compares QSBR, HPBR, EBR, and lock-free reference counting. 1782 Journal version of ThomasEHart2006a. 1783} 1784} 1785 1786@unpublished{MathieuDesnoyers2007call:rcu:schedNeeded 1787,Author="Mathieu Desnoyers" 1788,Title="Re: [patch 1/2] {Linux} Kernel Markers - Support Multiple Probes" 1789,month="December" 1790,day="20" 1791,year="2007" 1792,note="Available: 1793\url{http://lkml.org/lkml/2007/12/20/244} 1794[Viewed March 27, 2008]" 1795,annotation=" 1796 Request for call_rcu_sched() and rcu_barrier_sched(). 1797" 1798} 1799 1800 1801######################################################################## 1802# 1803# "What is RCU?" LWN series. 1804# 1805# http://lwn.net/Articles/262464/ (What is RCU, Fundamentally?) 1806# http://lwn.net/Articles/263130/ (What is RCU's Usage?) 1807# http://lwn.net/Articles/264090/ (What is RCU's API?) 1808 1809@unpublished{PaulEMcKenney2007WhatIsRCUFundamentally 1810,Author="Paul E. McKenney and Jonathan Walpole" 1811,Title="What is {RCU}, Fundamentally?" 1812,month="December" 1813,day="17" 1814,year="2007" 1815,note="Available: 1816\url{http://lwn.net/Articles/262464/} 1817[Viewed December 27, 2007]" 1818,annotation=" 1819 Lays out the three basic components of RCU: (1) publish-subscribe, 1820 (2) wait for pre-existing readers to complete, and (2) maintain 1821 multiple versions. 1822" 1823} 1824 1825@unpublished{PaulEMcKenney2008WhatIsRCUUsage 1826,Author="Paul E. McKenney" 1827,Title="What is {RCU}? Part 2: Usage" 1828,month="January" 1829,day="4" 1830,year="2008" 1831,note="Available: 1832\url{http://lwn.net/Articles/263130/} 1833[Viewed January 4, 2008]" 1834,annotation=" 1835 Lays out six uses of RCU: 1836 1. RCU is a Reader-Writer Lock Replacement 1837 2. RCU is a Restricted Reference-Counting Mechanism 1838 3. RCU is a Bulk Reference-Counting Mechanism 1839 4. RCU is a Poor Man's Garbage Collector 1840 5. RCU is a Way of Providing Existence Guarantees 1841 6. RCU is a Way of Waiting for Things to Finish 1842" 1843} 1844 1845@unpublished{PaulEMcKenney2008WhatIsRCUAPI 1846,Author="Paul E. McKenney" 1847,Title="{RCU} part 3: the {RCU} {API}" 1848,month="January" 1849,day="17" 1850,year="2008" 1851,note="Available: 1852\url{http://lwn.net/Articles/264090/} 1853[Viewed January 10, 2008]" 1854,annotation=" 1855 Gives an overview of the Linux-kernel RCU API and a brief annotated RCU 1856 bibliography. 1857" 1858} 1859 1860# 1861# "What is RCU?" LWN series. 1862# 1863######################################################################## 1864 1865 1866@unpublished{SteveRostedt2008dyntickRCUpatch 1867,Author="Steven Rostedt and Paul E. McKenney" 1868,Title="{[PATCH]} add support for dynamic ticks and preempt rcu" 1869,month="January" 1870,day="29" 1871,year="2008" 1872,note="Available: 1873\url{http://lkml.org/lkml/2008/1/29/208} 1874[Viewed March 27, 2008]" 1875,annotation=" 1876 Patch that prevents preemptible RCU from unnecessarily waking 1877 up dynticks-idle CPUs. 1878" 1879} 1880 1881@unpublished{PaulEMcKenney2008LKMLDependencyOrdering 1882,Author="Paul E. McKenney" 1883,Title="Re: [PATCH 02/22 -v7] Add basic support for gcc profiler instrumentation" 1884,month="February" 1885,day="1" 1886,year="2008" 1887,note="Available: 1888\url{http://lkml.org/lkml/2008/2/2/255} 1889[Viewed October 18, 2008]" 1890,annotation=" 1891 Explanation of compilers violating dependency ordering. 1892" 1893} 1894 1895@Conference{PaulEMcKenney2008Beijing 1896,Author="Paul E. McKenney" 1897,Title="Introducing Technology Into {Linux} Or: 1898Introducing your technology Into {Linux} will require introducing a 1899lot of {Linux} into your technology!!!" 1900,Booktitle="2008 Linux Developer Symposium - China" 1901,Publisher="OSS China" 1902,Month="February" 1903,Year="2008" 1904,Address="Beijing, China" 1905,note="Available: 1906\url{http://www.rdrop.com/users/paulmck/RCU/TechIntroLinux.2008.02.19a.pdf} 1907[Viewed August 12, 2008]" 1908} 1909 1910@unpublished{PaulEMcKenney2008dynticksRCU 1911,Author="Paul E. McKenney and Steven Rostedt" 1912,Title="Integrating and Validating dynticks and Preemptable RCU" 1913,month="April" 1914,day="24" 1915,year="2008" 1916,note="Available: 1917\url{http://lwn.net/Articles/279077/} 1918[Viewed April 24, 2008]" 1919,annotation=" 1920 Describes use of Promela and Spin to validate (and fix!) the 1921 dynticks/RCU interface. 1922" 1923} 1924 1925@article{DinakarGuniguntala2008IBMSysJ 1926,author="D. Guniguntala and P. E. McKenney and J. Triplett and J. Walpole" 1927,title="The read-copy-update mechanism for supporting real-time applications on shared-memory multiprocessor systems with {Linux}" 1928,Year="2008" 1929,Month="April-June" 1930,journal="IBM Systems Journal" 1931,volume="47" 1932,number="2" 1933,pages="221-236" 1934,annotation=" 1935 RCU, realtime RCU, sleepable RCU, performance. 1936" 1937} 1938 1939@unpublished{LaiJiangshan2008NewClassicAlgorithm 1940,Author="Lai Jiangshan" 1941,Title="[{RFC}][{PATCH}] rcu classic: new algorithm for callbacks-processing" 1942,month="June" 1943,day="3" 1944,year="2008" 1945,note="Available: 1946\url{http://lkml.org/lkml/2008/6/2/539} 1947[Viewed December 10, 2008]" 1948,annotation=" 1949 Updated RCU classic algorithm. Introduced multi-tailed list 1950 for RCU callbacks and also pulling common code into 1951 __call_rcu(). 1952" 1953} 1954 1955@article{PaulEMcKenney2008RCUOSR 1956,author="Paul E. McKenney and Jonathan Walpole" 1957,title="Introducing technology into the {Linux} kernel: a case study" 1958,Year="2008" 1959,journal="SIGOPS Oper. Syst. Rev." 1960,volume="42" 1961,number="5" 1962,pages="4--17" 1963,issn="0163-5980" 1964,doi={http://doi.acm.org/10.1145/1400097.1400099} 1965,publisher="ACM" 1966,address="New York, NY, USA" 1967,annotation={ 1968 Linux changed RCU to a far greater degree than RCU has changed Linux. 1969} 1970} 1971 1972@unpublished{ManfredSpraul2008StateMachineRCU 1973,Author="Manfred Spraul" 1974,Title="[{RFC}, {PATCH}] state machine based rcu" 1975,month="August" 1976,day="21" 1977,year="2008" 1978,note="Available: 1979\url{http://lkml.org/lkml/2008/8/21/336} 1980[Viewed December 8, 2008]" 1981,annotation=" 1982 State-based RCU. One key thing that this patch does is to 1983 separate the dynticks handling of NMIs and IRQs. 1984" 1985} 1986 1987@unpublished{ManfredSpraul2008dyntickIRQNMI 1988,Author="Manfred Spraul" 1989,Title="Re: [{RFC}, {PATCH}] v4 scalable classic {RCU} implementation" 1990,month="September" 1991,day="6" 1992,year="2008" 1993,note="Available: 1994\url{http://lkml.org/lkml/2008/9/6/86} 1995[Viewed December 8, 2008]" 1996,annotation=" 1997 Manfred notes a fix required to my attempt to separate irq 1998 and NMI processing for hierarchical RCU's dynticks interface. 1999" 2000} 2001 2002@techreport{PaulEMcKenney2008cyclicRCU 2003,author="Paul E. McKenney" 2004,title="Efficient Support of Consistent Cyclic Search With Read-Copy Update" 2005,institution="US Patent and Trademark Office" 2006,address="Washington, DC" 2007,year="2008" 2008,number="US Patent 7,426,511" 2009,month="September" 2010,pages="23" 2011,annotation=" 2012 Maintains an additional level of indirection to allow 2013 readers to confine themselves to the desired snapshot of the 2014 data structure. Only permits one update at a time. 2015" 2016} 2017 2018@unpublished{PaulEMcKenney2008HierarchicalRCU 2019,Author="Paul E. McKenney" 2020,Title="Hierarchical {RCU}" 2021,month="November" 2022,day="3" 2023,year="2008" 2024,note="Available: 2025\url{http://lwn.net/Articles/305782/} 2026[Viewed November 6, 2008]" 2027,annotation=" 2028 RCU with combining-tree-based grace-period detection, 2029 permitting it to handle thousands of CPUs. 2030" 2031} 2032 2033@unpublished{PaulEMcKenney2009BloatwatchRCU 2034,Author="Paul E. McKenney" 2035,Title="Re: [PATCH fyi] RCU: the bloatwatch edition" 2036,month="January" 2037,day="14" 2038,year="2009" 2039,note="Available: 2040\url{http://lkml.org/lkml/2009/1/14/449} 2041[Viewed January 15, 2009]" 2042,annotation=" 2043 Small-footprint implementation of RCU for uniprocessor 2044 embedded applications -- and also for exposition purposes. 2045" 2046} 2047 2048@conference{PaulEMcKenney2009MaliciousURCU 2049,Author="Paul E. McKenney" 2050,Title="Using a Malicious User-Level {RCU} to Torture {RCU}-Based Algorithms" 2051,Booktitle="linux.conf.au 2009" 2052,month="January" 2053,year="2009" 2054,address="Hobart, Australia" 2055,note="Available: 2056\url{http://www.rdrop.com/users/paulmck/RCU/urcutorture.2009.01.22a.pdf} 2057[Viewed February 2, 2009]" 2058,annotation=" 2059 Realtime RCU and torture-testing RCU uses. 2060" 2061} 2062 2063@unpublished{MathieuDesnoyers2009URCU 2064,Author="Mathieu Desnoyers" 2065,Title="[{RFC} git tree] Userspace {RCU} (urcu) for {Linux}" 2066,month="February" 2067,day="5" 2068,year="2009" 2069,note="Available: 2070\url{http://lkml.org/lkml/2009/2/5/572} 2071\url{http://lttng.org/urcu} 2072[Viewed February 20, 2009]" 2073,annotation=" 2074 Mathieu Desnoyers's user-space RCU implementation. 2075 git://lttng.org/userspace-rcu.git 2076 http://lttng.org/cgi-bin/gitweb.cgi?p=userspace-rcu.git 2077 http://lttng.org/urcu 2078" 2079} 2080 2081@unpublished{PaulEMcKenney2009LWNBloatWatchRCU 2082,Author="Paul E. McKenney" 2083,Title="{RCU}: The {Bloatwatch} Edition" 2084,month="March" 2085,day="17" 2086,year="2009" 2087,note="Available: 2088\url{http://lwn.net/Articles/323929/} 2089[Viewed March 20, 2009]" 2090,annotation=" 2091 Uniprocessor assumptions allow simplified RCU implementation. 2092" 2093} 2094 2095@unpublished{PaulEMcKenney2009expeditedRCU 2096,Author="Paul E. McKenney" 2097,Title="[{PATCH} -tip 0/3] expedited 'big hammer' {RCU} grace periods" 2098,month="June" 2099,day="25" 2100,year="2009" 2101,note="Available: 2102\url{http://lkml.org/lkml/2009/6/25/306} 2103[Viewed August 16, 2009]" 2104,annotation=" 2105 First posting of expedited RCU to be accepted into -tip. 2106" 2107} 2108 2109@unpublished{PaulEMcKenney2009fastRTRCU 2110,Author="Paul E. McKenney" 2111,Title="[{PATCH} {RFC} -tip 0/4] {RCU} cleanups and simplified preemptable {RCU}" 2112,month="July" 2113,day="23" 2114,year="2009" 2115,note="Available: 2116\url{http://lkml.org/lkml/2009/7/23/294} 2117[Viewed August 15, 2009]" 2118,annotation=" 2119 First posting of simple and fast preemptable RCU. 2120" 2121} 2122 2123@InProceedings{JoshTriplett2009RPHash 2124,Author="Josh Triplett" 2125,Title="Scalable concurrent hash tables via relativistic programming" 2126,month="September" 2127,year="2009" 2128,booktitle="Linux Plumbers Conference 2009" 2129,annotation=" 2130 RP fun with hash tables. 2131 See also JoshTriplett2010RPHash 2132" 2133} 2134 2135@phdthesis{MathieuDesnoyersPhD 2136, title = "Low-Impact Operating System Tracing" 2137, author = "Mathieu Desnoyers" 2138, school = "Ecole Polytechnique de Montr\'{e}al" 2139, month = "December" 2140, year = 2009 2141,note="Available: 2142\url{http://www.lttng.org/pub/thesis/desnoyers-dissertation-2009-12.pdf} 2143[Viewed December 9, 2009]" 2144,annotation={ 2145 Chapter 6 (page 97) covers user-level RCU. 2146} 2147} 2148 2149@unpublished{RelativisticProgrammingWiki 2150,Author="Josh Triplett and Paul E. McKenney and Jonathan Walpole" 2151,Title="Relativistic Programming" 2152,month="September" 2153,year="2009" 2154,note="Available: 2155\url{http://wiki.cs.pdx.edu/rp/} 2156[Viewed December 9, 2009]" 2157,annotation=" 2158 Main Relativistic Programming Wiki. 2159" 2160} 2161 2162@conference{PaulEMcKenney2009DeterministicRCU 2163,Author="Paul E. McKenney" 2164,Title="Deterministic Synchronization in Multicore Systems: the Role of {RCU}" 2165,Booktitle="Eleventh Real Time Linux Workshop" 2166,month="September" 2167,year="2009" 2168,address="Dresden, Germany" 2169,note="Available: 2170\url{http://www.rdrop.com/users/paulmck/realtime/paper/DetSyncRCU.2009.08.18a.pdf} 2171[Viewed January 14, 2009]" 2172} 2173 2174@unpublished{PaulEMcKenney2009HuntingHeisenbugs 2175,Author="Paul E. McKenney" 2176,Title="Hunting Heisenbugs" 2177,month="November" 2178,year="2009" 2179,day="1" 2180,note="Available: 2181\url{http://paulmck.livejournal.com/14639.html} 2182[Viewed June 4, 2010]" 2183,annotation=" 2184 Day-one bug in Tree RCU that took forever to track down. 2185" 2186} 2187 2188@unpublished{MathieuDesnoyers2009defer:rcu 2189,Author="Mathieu Desnoyers" 2190,Title="Kernel RCU: shrink the size of the struct rcu\_head" 2191,month="December" 2192,year="2009" 2193,note="Available: 2194\url{http://lkml.org/lkml/2009/10/18/129} 2195[Viewed December 29, 2009]" 2196,annotation=" 2197 Mathieu proposed defer_rcu() with fixed-size per-thread pool 2198 of RCU callbacks. 2199" 2200} 2201 2202@unpublished{MathieuDesnoyers2009VerifPrePub 2203,Author="Mathieu Desnoyers and Paul E. McKenney and Michel R. Dagenais" 2204,Title="Multi-Core Systems Modeling for Formal Verification of Parallel Algorithms" 2205,month="December" 2206,year="2009" 2207,note="Submitted to IEEE TPDS" 2208,annotation=" 2209 OOMem model for Mathieu's user-level RCU mechanical proof of 2210 correctness. 2211" 2212} 2213 2214@unpublished{MathieuDesnoyers2009URCUPrePub 2215,Author="Mathieu Desnoyers and Paul E. McKenney and Alan Stern and Michel R. Dagenais and Jonathan Walpole" 2216,Title="User-Level Implementations of Read-Copy Update" 2217,month="December" 2218,year="2010" 2219,url=\url{http://www.computer.org/csdl/trans/td/2012/02/ttd2012020375-abs.html} 2220,annotation=" 2221 RCU overview, desiderata, semi-formal semantics, user-level RCU 2222 usage scenarios, three classes of RCU implementation, wait-free 2223 RCU updates, RCU grace-period batching, update overhead, 2224 http://www.rdrop.com/users/paulmck/RCU/urcu-main-accepted.2011.08.30a.pdf 2225 http://www.rdrop.com/users/paulmck/RCU/urcu-supp-accepted.2011.08.30a.pdf 2226 Superseded by MathieuDesnoyers2012URCU. 2227" 2228} 2229 2230@inproceedings{HariKannan2009DynamicAnalysisRCU 2231,author = {Kannan, Hari} 2232,title = {Ordering decoupled metadata accesses in multiprocessors} 2233,booktitle = {MICRO 42: Proceedings of the 42nd Annual IEEE/ACM International Symposium on Microarchitecture} 2234,year = {2009} 2235,isbn = {978-1-60558-798-1} 2236,pages = {381--390} 2237,location = {New York, New York} 2238,doi = {http://doi.acm.org/10.1145/1669112.1669161} 2239,publisher = {ACM} 2240,address = {New York, NY, USA} 2241,annotation={ 2242 Uses RCU to protect metadata used in dynamic analysis. 2243}} 2244 2245@conference{PaulEMcKenney2010SimpleOptRCU 2246,Author="Paul E. McKenney" 2247,Title="Simplicity Through Optimization" 2248,Booktitle="linux.conf.au 2010" 2249,month="January" 2250,year="2010" 2251,address="Wellington, New Zealand" 2252,note="Available: 2253\url{http://www.rdrop.com/users/paulmck/RCU/SimplicityThruOptimization.2010.01.21f.pdf} 2254[Viewed October 10, 2010]" 2255,annotation=" 2256 TREE_PREEMPT_RCU optimizations greatly simplified the old 2257 PREEMPT_RCU implementation. 2258" 2259} 2260 2261@unpublished{PaulEMcKenney2010LockdepRCU 2262,Author="Paul E. McKenney" 2263,Title="Lockdep-{RCU}" 2264,month="February" 2265,year="2010" 2266,day="1" 2267,note="Available: 2268\url{https://lwn.net/Articles/371986/} 2269[Viewed June 4, 2010]" 2270,annotation=" 2271 CONFIG_PROVE_RCU, or at least an early version. 2272" 2273} 2274 2275@unpublished{AviKivity2010KVM2RCU 2276,Author="Avi Kivity" 2277,Title="[{PATCH} 37/40] {KVM}: Bump maximum vcpu count to 64" 2278,month="February" 2279,year="2010" 2280,note="Available: 2281\url{http://www.mail-archive.com/kvm@vger.kernel.org/msg28640.html} 2282[Viewed March 20, 2010]" 2283,annotation=" 2284 Use of RCU permits KVM to increase the size of guest OSes from 2285 16 CPUs to 64 CPUs. 2286" 2287} 2288 2289@unpublished{HerbertXu2010RCUResizeHash 2290,Author="Herbert Xu" 2291,Title="bridge: Add core IGMP snooping support" 2292,month="February" 2293,year="2010" 2294,note="Available: 2295\url{http://kerneltrap.com/mailarchive/linux-netdev/2010/2/26/6270589} 2296[Viewed March 20, 2011]" 2297,annotation={ 2298 Use a pair of list_head structures to support RCU-protected 2299 resizable hash tables. 2300}} 2301 2302@article{JoshTriplett2010RPHash 2303,author="Josh Triplett and Paul E. McKenney and Jonathan Walpole" 2304,title="Scalable Concurrent Hash Tables via Relativistic Programming" 2305,journal="ACM Operating Systems Review" 2306,year=2010 2307,volume=44 2308,number=3 2309,month="July" 2310,annotation={ 2311 RP fun with hash tables. 2312 http://portal.acm.org/citation.cfm?id=1842733.1842750 2313}} 2314 2315@unpublished{PaulEMcKenney2010RCUAPI 2316,Author="Paul E. McKenney" 2317,Title="The {RCU} {API}, 2010 Edition" 2318,month="December" 2319,day="8" 2320,year="2010" 2321,note="Available: 2322\url{http://lwn.net/Articles/418853/} 2323[Viewed December 8, 2010]" 2324,annotation=" 2325 Includes updated software-engineering features. 2326" 2327} 2328 2329@mastersthesis{AndrejPodzimek2010masters 2330,author="Andrej Podzimek" 2331,title="Read-Copy-Update for OpenSolaris" 2332,school="Charles University in Prague" 2333,year="2010" 2334,note="Available: 2335\url{https://andrej.podzimek.org/thesis.pdf} 2336[Viewed January 31, 2011]" 2337,annotation={ 2338 Reviews RCU implementations and creates a few for OpenSolaris. 2339 Drives quiescent-state detection from RCU read-side primitives, 2340 in a manner roughly similar to that of Jim Houston. 2341}} 2342 2343@unpublished{LinusTorvalds2011Linux2:6:38:rc1:NPigginVFS 2344,Author="Linus Torvalds" 2345,Title="Linux 2.6.38-rc1" 2346,month="January" 2347,year="2011" 2348,note="Available: 2349\url{https://lkml.org/lkml/2011/1/18/322} 2350[Viewed March 4, 2011]" 2351,annotation={ 2352 "The RCU-based name lookup is at the other end of the spectrum - the 2353 absolute anti-gimmick. It's some seriously good stuff, and gets rid of 2354 the last main global lock that really tends to hurt some kernel loads. 2355 The dentry lock is no longer a big serializing issue. What's really 2356 nice about it is that it actually improves performance a lot even for 2357 single-threaded loads (on an SMP kernel), because it gets rid of some 2358 of the most expensive parts of path component lookup, which was the 2359 d_lock on every component lookup. So I'm seeing improvements of 30-50% 2360 on some seriously pathname-lookup intensive loads." 2361}} 2362 2363@techreport{JoshTriplett2011RPScalableCorrectOrdering 2364,author = {Josh Triplett and Philip W. Howard and Paul E. McKenney and Jonathan Walpole} 2365,title = {Scalable Correct Memory Ordering via Relativistic Programming} 2366,year = {2011} 2367,number = {11-03} 2368,institution = {Portland State University} 2369,note = {\url{http://www.cs.pdx.edu/pdfs/tr1103.pdf}} 2370} 2371 2372@inproceedings{PhilHoward2011RCUTMRBTree 2373,author = {Philip W. Howard and Jonathan Walpole} 2374,title = {A Relativistic Enhancement to Software Transactional Memory} 2375,booktitle = {Proceedings of the 3rd USENIX conference on Hot topics in parallelism} 2376,series = {HotPar'11} 2377,year = {2011} 2378,location = {Berkeley, CA} 2379,pages = {1--6} 2380,numpages = {6} 2381,url = {http://www.usenix.org/event/hotpar11/tech/final_files/Howard.pdf} 2382,publisher = {USENIX Association} 2383,address = {Berkeley, CA, USA} 2384} 2385 2386@techreport{PaulEMcKenney2011cyclicparallelRCU 2387,author="Paul E. McKenney and Jonathan Walpole" 2388,title="Efficient Support of Consistent Cyclic Search With Read-Copy Update and Parallel Updates" 2389,institution="US Patent and Trademark Office" 2390,address="Washington, DC" 2391,year="2011" 2392,number="US Patent 7,953,778" 2393,month="May" 2394,pages="34" 2395,annotation=" 2396 Maintains an array of generation numbers to track in-flight 2397 updates and keeps an additional level of indirection to allow 2398 readers to confine themselves to the desired snapshot of the 2399 data structure. 2400" 2401} 2402 2403@inproceedings{Triplett:2011:RPHash 2404,author = {Triplett, Josh and McKenney, Paul E. and Walpole, Jonathan} 2405,title = {Resizable, Scalable, Concurrent Hash Tables via Relativistic Programming} 2406,booktitle = {Proceedings of the 2011 USENIX Annual Technical Conference} 2407,month = {June} 2408,year = {2011} 2409,pages = {145--158} 2410,numpages = {14} 2411,url={http://www.usenix.org/event/atc11/tech/final_files/atc11_proceedings.pdf} 2412,publisher = {The USENIX Association} 2413,address = {Portland, OR USA} 2414} 2415 2416@unpublished{PaulEMcKenney2011RCU3.0trainwreck 2417,Author="Paul E. McKenney" 2418,Title="3.0 and {RCU:} what went wrong" 2419,month="July" 2420,day="27" 2421,year="2011" 2422,note="Available: 2423\url{http://lwn.net/Articles/453002/} 2424[Viewed July 27, 2011]" 2425,annotation=" 2426 Analysis of the RCU trainwreck in Linux kernel 3.0. 2427" 2428} 2429 2430@unpublished{NeilBrown2011MeetTheLockers 2431,Author="Neil Brown" 2432,Title="Meet the Lockers" 2433,month="August" 2434,day="3" 2435,year="2011" 2436,note="Available: 2437\url{http://lwn.net/Articles/453685/} 2438[Viewed September 2, 2011]" 2439,annotation=" 2440 The Locker family as an analogy for locking, reference counting, 2441 RCU, and seqlock. 2442" 2443} 2444 2445@article{MathieuDesnoyers2012URCU 2446,Author="Mathieu Desnoyers and Paul E. McKenney and Alan Stern and Michel R. Dagenais and Jonathan Walpole" 2447,Title="User-Level Implementations of Read-Copy Update" 2448,journal="IEEE Transactions on Parallel and Distributed Systems" 2449,volume={23} 2450,year="2012" 2451,issn="1045-9219" 2452,pages="375-382" 2453,doi="http://doi.ieeecomputersociety.org/10.1109/TPDS.2011.159" 2454,publisher="IEEE Computer Society" 2455,address="Los Alamitos, CA, USA" 2456,annotation={ 2457 RCU overview, desiderata, semi-formal semantics, user-level RCU 2458 usage scenarios, three classes of RCU implementation, wait-free 2459 RCU updates, RCU grace-period batching, update overhead, 2460 http://www.rdrop.com/users/paulmck/RCU/urcu-main-accepted.2011.08.30a.pdf 2461 http://www.rdrop.com/users/paulmck/RCU/urcu-supp-accepted.2011.08.30a.pdf 2462} 2463} 2464