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