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