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