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