Documentation/RCU/RTFP.txt

   1 Read the Fscking Papers!
   2
   3
   4 This document describes RCU-related publications, and is followed by
   5 the corresponding bibtex entries.  A number of the publications may
   6 be found at http://www.rdrop.com/users/paulmck/RCU/.  For others, browsers
   7 and search engines will usually find what you are looking for.
   8
   9 The first thing resembling RCU was published in 1980, when Kung and Lehman
  10 [Kung80] recommended use of a garbage collector to defer destruction
  11 of nodes in a parallel binary search tree in order to simplify its
  12 implementation.  This works well in environments that have garbage
  13 collectors, but most production garbage collectors incur significant
  14 overhead.
  15
  16 In 1982, Manber and Ladner [Manber82,Manber84] recommended deferring
  17 destruction until all threads running at that time have terminated, again
  18 for a parallel binary search tree.  This approach works well in systems
  19 with short-lived threads, such as the K42 research operating system.
  20 However, Linux has long-lived tasks, so more is needed.
  21
  22 In 1986, Hennessy, Osisek, and Seigh [Hennessy89] introduced passive
  23 serialization, which is an RCU-like mechanism that relies on the presence
  24 of "quiescent states" in the VM/XA hypervisor that are guaranteed not
  25 to be referencing the data structure.  However, this mechanism was not
  26 optimized for modern computer systems, which is not surprising given
  27 that these overheads were not so expensive in the mid-80s.  Nonetheless,
  28 passive serialization appears to be the first deferred-destruction
  29 mechanism to be used in production.  Furthermore, the relevant patent
  30 has 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
  32 under either GPL or LGPL.  Sorry!!!)
  33
  34 In 1987, Rashid et al. described lazy TLB-flush [RichardRashid87a].
  35 At first glance, this has nothing to do with RCU, but nevertheless
  36 this paper helped inspire the update-side batching used in the later
  37 RCU implementation in DYNIX/ptx.  In 1988, Barbara Liskov published
  38 a description of Argus that noted that use of out-of-date values can
  39 be tolerated in some situations.  Thus, this paper provides some early
  40 theoretical justification for use of stale data.
  41
  42 In 1990, Pugh [Pugh90] noted that explicitly tracking which threads
  43 were reading a given data structure permitted deferred free to operate
  44 in the presence of non-terminating threads.  However, this explicit
  45 tracking imposes significant read-side overhead, which is undesirable
  46 in read-mostly situations.  This algorithm does take pains to avoid
  47 write-side contention and parallelize the other write-side overheads by
  48 providing a fine-grained locking design, however, it would be interesting
  49 to see how much of the performance advantage reported in 1990 remains
  50 today.
  51
  52 At about this same time, Andrews [Andrews91textbook] described ``chaotic
  53 relaxation'', where the normal barriers between successive iterations
  54 of convergent numerical algorithms are relaxed, so that iteration $n$
  55 might use data from iteration $n-1$ or even $n-2$.  This introduces
  56 error, which typically slows convergence and thus increases the number of
  57 iterations required.  However, this increase is sometimes more than made
  58 up for by a reduction in the number of expensive barrier operations,
  59 which are otherwise required to synchronize the threads at the end
  60 of each iteration.  Unfortunately, chaotic relaxation requires highly
  61 structured data, such as the matrices used in scientific programs, and
  62 is thus inapplicable to most data structures in operating-system kernels.
  63
  64 In 1992, Henry (now Alexia) Massalin completed a dissertation advising
  65 parallel programmers to defer processing when feasible to simplify
  66 synchronization [HMassalinPhD].  RCU makes extremely heavy use of
  67 this advice.
  68
  69 In 1993, Jacobson [Jacobson93] verbally described what is perhaps the
  70 simplest deferred-free technique: simply waiting a fixed amount of time
  71 before freeing blocks awaiting deferred free.  Jacobson did not describe
  72 any write-side changes he might have made in this work using SGI's Irix
  73 kernel.  Aju John published a similar technique in 1995 [AjuJohn95].
  74 This works well if there is a well-defined upper bound on the length of
  75 time that reading threads can hold references, as there might well be in
  76 hard real-time systems.  However, if this time is exceeded, perhaps due
  77 to preemption, excessive interrupts, or larger-than-anticipated load,
  78 memory corruption can ensue, with no reasonable means of diagnosis.
  79 Jacobson's technique is therefore inappropriate for use in production
  80 operating-system kernels, except when such kernels can provide hard
  81 real-time response guarantees for all operations.
  82
  83 Also in 1995, Pu et al. [Pu95a] applied a technique similar to that of Pugh's
  84 read-side-tracking to permit replugging of algorithms within a commercial
  85 Unix operating system.  However, this replugging permitted only a single
  86 reader at a time.  The following year, this same group of researchers
  87 extended their technique to allow for multiple readers [Cowan96a].
  88 Their approach requires memory barriers (and thus pipeline stalls),
  89 but reduces memory latency, contention, and locking overheads.
  90
  91 1995 also saw the first publication of DYNIX/ptx's RCU mechanism
  92 [Slingwine95], which was optimized for modern CPU architectures,
  93 and was successfully applied to a number of situations within the
  94 DYNIX/ptx kernel.  The corresponding conference paper appeared in 1998
  95 [McKenney98].
  96
  97 In 1999, the Tornado and K42 groups described their "generations"
  98 mechanism, which is quite similar to RCU [Gamsa99].  These operating
  99 systems made pervasive use of RCU in place of "existence locks", which
 100 greatly simplifies locking hierarchies and helps avoid deadlocks.
 101
 102 The year 2000 saw an email exchange that would likely have
 103 led to yet another independent invention of something like RCU
 104 [RustyRussell2000a,RustyRussell2000b].  Instead, 2001 saw the first
 105 RCU presentation involving Linux [McKenney01a] at OLS.  The resulting
 106 abundance of RCU patches was presented the following year [McKenney02a],
 107 and use of RCU in dcache was first described that same year [Linder02a].
 108
 109 Also in 2002, Michael [Michael02b,Michael02a] presented "hazard-pointer"
 110 techniques that defer the destruction of data structures to simplify
 111 non-blocking synchronization (wait-free synchronization, lock-free
 112 synchronization, and obstruction-free synchronization are all examples of
 113 non-blocking synchronization).  The corresponding journal article appeared
 114 in 2004 [MagedMichael04a].  This technique eliminates locking, reduces
 115 contention, reduces memory latency for readers, and parallelizes pipeline
 116 stalls and memory latency for writers.  However, these techniques still
 117 impose significant read-side overhead in the form of memory barriers.
 118 Researchers at Sun worked along similar lines in the same timeframe
 119 [HerlihyLM02].  These techniques can be thought of as inside-out reference
 120 counts, where the count is represented by the number of hazard pointers
 121 referencing a given data structure rather than the more conventional
 122 counter field within the data structure itself.  The key advantage
 123 of inside-out reference counts is that they can be stored in immortal
 124 variables, thus allowing races between access and deletion to be avoided.
 125
 126 By the same token, RCU can be thought of as a "bulk reference count",
 127 where some form of reference counter covers all reference by a given CPU
 128 or thread during a set timeframe.  This timeframe is related to, but
 129 not necessarily exactly the same as, an RCU grace period.  In classic
 130 RCU, the reference counter is the per-CPU bit in the "bitmask" field,
 131 and each such bit covers all references that might have been made by
 132 the corresponding CPU during the prior grace period.  Of course, RCU
 133 can be thought of in other terms as well.
 134
 135 In 2003, the K42 group described how RCU could be used to create
 136 hot-pluggable implementations of operating-system functions [Appavoo03a].
 137 Later that year saw a paper describing an RCU implementation
 138 of System V IPC [Arcangeli03] (following up on a suggestion by
 139 Hugh Dickins [Dickins02a] and an implementation by Mingming Cao
 140 [MingmingCao2002IPCRCU]), and an introduction to RCU in Linux Journal
 141 [McKenney03a].
 142
 143 2004 has seen a Linux-Journal article on use of RCU in dcache
 144 [McKenney04a], a performance comparison of locking to RCU on several
 145 different CPUs [McKenney04b], a dissertation describing use of RCU in a
 146 number of operating-system kernels [PaulEdwardMcKenneyPhD], a paper
 147 describing how to make RCU safe for soft-realtime applications [Sarma04c],
 148 and a paper describing SELinux performance with RCU [JamesMorris04b].
 149
 150 2005 brought further adaptation of RCU to realtime use, permitting
 151 preemption of RCU realtime critical sections [PaulMcKenney05a,
 152 PaulMcKenney05b].
 153
 154 2006 saw the first best-paper award for an RCU paper [ThomasEHart2006a],
 155 as well as further work on efficient implementations of preemptible
 156 RCU [PaulEMcKenney2006b], but priority-boosting of RCU read-side critical
 157 sections proved elusive.  An RCU implementation permitting general
 158 blocking in read-side critical sections appeared [PaulEMcKenney2006c],
 159 Robert Olsson described an RCU-protected trie-hash combination
 160 [RobertOlsson2006a].
 161
 162 2007 saw the journal version of the award-winning RCU paper from 2006
 163 [ThomasEHart2007a], as well as a paper demonstrating use of Promela
 164 and Spin to mechanically verify an optimization to Oleg Nesterov's
 165 QRCU [PaulEMcKenney2007QRCUspin], a design document describing
 166 preemptible RCU [PaulEMcKenney2007PreemptibleRCU], and the three-part
 167 LWN "What is RCU?" series [PaulEMcKenney2007WhatIsRCUFundamentally,
 168 PaulEMcKenney2008WhatIsRCUUsage, and PaulEMcKenney2008WhatIsRCUAPI].
 169
 170 2008 saw a journal paper on real-time RCU [DinakarGuniguntala2008IBMSysJ],
 171 a history of how Linux changed RCU more than RCU changed Linux
 172 [PaulEMcKenney2008RCUOSR], and a design overview of hierarchical RCU
 173 [PaulEMcKenney2008HierarchicalRCU].
 174
 175 2009 introduced user-level RCU algorithms [PaulEMcKenney2009MaliciousURCU],
 176 which Mathieu Desnoyers is now maintaining [MathieuDesnoyers2009URCU]
 177 [MathieuDesnoyersPhD].  TINY_RCU [PaulEMcKenney2009BloatWatchRCU] made
 178 its appearance, as did expedited RCU [PaulEMcKenney2009expeditedRCU].
 179 The problem of resizeable RCU-protected hash tables may now be on a path
 180 to a solution [JoshTriplett2009RPHash].  A few academic researchers are now
 181 using RCU to solve their parallel problems [HariKannan2009DynamicAnalysisRCU].
 182
 183 2010 produced a simpler preemptible-RCU implementation
 184 based on TREE_RCU [PaulEMcKenney2010SimpleOptRCU], lockdep-RCU
 185 [PaulEMcKenney2010LockdepRCU], another resizeable RCU-protected hash
 186 table [HerbertXu2010RCUResizeHash] (this one consuming more memory,
 187 but allowing arbitrary changes in hash function, as required for DoS
 188 avoidance in the networking code), realization of the 2009 RCU-protected
 189 hash table with atomic node move [JoshTriplett2010RPHash], an update on
 190 the RCU API [PaulEMcKenney2010RCUAPI].
 191
 192 2011 marked the inclusion of Nick Piggin's fully lockless dentry search
 193 [LinusTorvalds2011Linux2:6:38:rc1:NPigginVFS], an RCU-protected red-black
 194 tree using software transactional memory to protect concurrent updates
 195 (strange, but true!) [PhilHoward2011RCUTMRBTree], yet another variant of
 196 RCU-protected resizeable hash tables [Triplett:2011:RPHash], the 3.0 RCU
 197 trainwreck [PaulEMcKenney2011RCU3.0trainwreck], and Neil Brown's "Meet the
 198 Lockers" LWN article [NeilBrown2011MeetTheLockers].  Some academic
 199 work looked at debugging uses of RCU [Seyster:2011:RFA:2075416.2075425].
 200
 201 In 2012, Josh Triplett received his Ph.D. with his dissertation
 202 covering RCU-protected resizable hash tables and the relationship
 203 between memory barriers and read-side traversal order:  If the updater
 204 is making changes in the opposite direction from the read-side traveral
 205 order, the updater need only execute a memory-barrier instruction,
 206 but if in the same direction, the updater needs to wait for a grace
 207 period between the individual updates [JoshTriplettPhD].  Also in 2012,
 208 after seventeen years of attempts, an RCU paper made it into a top-flight
 209 academic journal, IEEE Transactions on Parallel and Distributed Systems
 210 [MathieuDesnoyers2012URCU].  A group of researchers in Spain applied
 211 user-level RCU to crowd simulation [GuillermoVigueras2012RCUCrowd], and
 212 another group of researchers in Europe produced a formal description of
 213 RCU based on separation logic [AlexeyGotsman2012VerifyGraceExtended],
 214 which was published in the 2013 European Symposium on Programming
 215 [AlexeyGotsman2013ESOPRCU].
 216
 217
 218
 219 Bibtex 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
 306 David Golub and Robert Baron and David Black and William Bolosky and
 307 Jonathan Chew"
 308 ,Title="Machine-Independent Virtual Memory Management for Paged
 309 Uniprocessor and Multiprocessor Architectures"
 310 ,Booktitle="{2\textsuperscript{nd} Symposium on Architectural Support
 311 for 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
 402 System 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
 452 Crispin Cowan and Jon Inouye and Lakshmi Kethana and Jonathan Walpole and
 453 Ke 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
 488 Exclusion and Maintaining Coherency in a Multiprocessor System
 489 Utilizing 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
 507 Summaries 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
 523 Exclusion and Maintaining Coherency in a Multiprocessor System
 524 Utilizing 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
 539 Problems"
 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
 558 Multiprocessor Operating System"
 559 ,Booktitle="{Proceedings of the 3\textsuperscript{rd} Symposium on
 560 Operating 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
 624 Exclusion and Maintaining Coherency in a Multiprocessor System
 625 Utilizing 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
 638 Orran 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{http://lkml.org/lkml/2001/10/13/105}
 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
 708 Symposium on Parallel
 709 Algorithms and Architecture}"
 710 ,pages="73-82"
 711 ,annotation={
 712 Like 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
 731 Andrea 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
 775 Reads and Writes"
 776 ,Year="2002"
 777 ,Month="August"
 778 ,booktitle="{Proceedings of the 21\textsuperscript{st} Annual ACM
 779 Symposium 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,
 801 Lock-Free Data Structures"
 802 ,booktitle={Proceedings of 16\textsuperscript{th} International
 803 Symposium 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://lkml.org/lkml/2002/10/24/262}
 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{http://lkml.org/lkml/2003/3/9/205}
 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         Steve 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
 856 D. M. {Da Silva} and O. Krieger and M. A. Auslander and D. J. Edelsohn and
 857 B. Gamsa and G. R. Ganger and P. McKenney and M. Ostrowski and
 858 B. 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
 884 Dipankar 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
 903 Dilma {Da Silva} and Gregory R. Ganger and Orran Krieger and
 904 Michael Stumm and Robert W. Wisniewski and Marc Auslander and
 905 Michal 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:
1030 Add 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://lkml.org/lkml/2004/5/20/49 (split vars into cachelines)
1040         https://lkml.org/lkml/2004/5/22/114 (cpu_quiet() patch)
1041         https://lkml.org/lkml/2004/5/25/24 (0/5)
1042         https://lkml.org/lkml/2004/5/25/23 (1/5)
1043                 https://lkml.org/lkml/2004/5/25/265 (works for Jack)
1044         https://lkml.org/lkml/2004/5/25/20 (2/5)
1045         https://lkml.org/lkml/2004/5/25/22 (3/5)
1046         https://lkml.org/lkml/2004/5/25/19 (4/5)
1047         https://lkml.org/lkml/2004/5/25/21 (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
1054 Realtime 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:
1089 An Analysis of Read-Copy-Update Techniques
1090 in Operating System Kernels"
1091 ,school="OGI School of Science and Engineering at
1092 Oregon 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{http://lkml.org/lkml/2004/8/6/237}
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{http://lkml.org/lkml/2004/8/30/87}
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{http://lkml.org/lkml/2004/10/23/241}
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://lkml.org/lkml/2004/9/27/52
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{http://lkml.org/lkml/2005/3/17/199}
1245 [Viewed September 5, 2005]"
1246 ,annotation={
1247         First posting showing how RCU can be safely adapted for
1248         preemptable 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{http://lkml.org/lkml/2005/3/18/122}
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
1272 Data 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{http://lkml.org/lkml/2005/5/9/185}
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{http://lkml.org/lkml/2005/8/1/155}
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{http://lkml.org/lkml/2005/8/8/108}
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{http://lkml.org/lkml/2005/10/1/70}
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://lkml.org/lkml/2006/1/7/22}
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
1444 of Memory Reclamation"
1445 ,Booktitle="20\textsuperscript{th} {IEEE} International Parallel and
1446 Distributed 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{http://lkml.org/lkml/2006/6/20/238}
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
1476 Suparna 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
1493 Gaius Cornelius and Qwertyus and Neil Conway and Sbw and Blainster and
1494 Canis 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/}
1529 Revised:
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{http://lkml.org/lkml/2006/9/28/160}
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{http://lkml.org/lkml/2006/10/26/73}
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{http://lkml.org/lkml/2006/11/17/56}
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 http://lkml.org/lkml/2006/11/17/359.
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{http://lkml.org/lkml/2006/11/19/69}
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{http://lkml.org/lkml/2006/11/29/330}
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{http://lkml.org/lkml/2007/1/3/112}
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{http://lkml.org/lkml/2007/1/28/34}
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{http://lkml.org/lkml/2007/2/25/18}
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: http://lkml.org/lkml/2007/2/25/18
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{http://lkml.org/lkml/2007/9/10/213}
1889 [Viewed October 25, 2007]"
1890 ,annotation={
1891         Final patch for preemptable 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{http://lkml.org/lkml/2007/12/20/244}
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{http://lkml.org/lkml/2008/1/29/208}
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{http://lkml.org/lkml/2008/2/2/255}
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:
2041 Introducing your technology Into {Linux} will require introducing a
2042 lot 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{http://lkml.org/lkml/2008/6/2/539}
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{http://lkml.org/lkml/2008/8/21/336}
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{http://lkml.org/lkml/2008/9/6/86}
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{http://lkml.org/lkml/2009/1/14/449}
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         http://lkml.org/lkml/2009/2/5/572
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{http://lkml.org/lkml/2009/6/25/306}
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{http://lkml.org/lkml/2009/7/23/294}
2276 [Viewed August 15, 2009]"
2277 ,annotation={
2278         First posting of simple and fast preemptable 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{http://lkml.org/lkml/2009/10/18/129}
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://lkml.org/lkml/2011/1/18/322}
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 traveral 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 }