Documentation/RCU/RTFP.txt

   1 Read the F-ing 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/.
   7
   8 The first thing resembling RCU was published in 1980, when Kung and Lehman
   9 [Kung80] recommended use of a garbage collector to defer destruction
  10 of nodes in a parallel binary search tree in order to simplify its
  11 implementation.  This works well in environments that have garbage
  12 collectors, but current production garbage collectors incur significant
  13 read-side overhead.
  14
  15 In 1982, Manber and Ladner [Manber82,Manber84] recommended deferring
  16 destruction until all threads running at that time have terminated, again
  17 for a parallel binary search tree.  This approach works well in systems
  18 with short-lived threads, such as the K42 research operating system.
  19 However, Linux has long-lived tasks, so more is needed.
  20
  21 In 1986, Hennessy, Osisek, and Seigh [Hennessy89] introduced passive
  22 serialization, which is an RCU-like mechanism that relies on the presence
  23 of "quiescent states" in the VM/XA hypervisor that are guaranteed not
  24 to be referencing the data structure.  However, this mechanism was not
  25 optimized for modern computer systems, which is not surprising given
  26 that these overheads were not so expensive in the mid-80s.  Nonetheless,
  27 passive serialization appears to be the first deferred-destruction
  28 mechanism to be used in production.  Furthermore, the relevant patent has
  29 lapsed, so this approach may be used in non-GPL software, if desired.
  30 (In contrast, use of RCU is permitted only in software licensed under
  31 GPL.  Sorry!!!)
  32
  33 In 1990, Pugh [Pugh90] noted that explicitly tracking which threads
  34 were reading a given data structure permitted deferred free to operate
  35 in the presence of non-terminating threads.  However, this explicit
  36 tracking imposes significant read-side overhead, which is undesirable
  37 in read-mostly situations.  This algorithm does take pains to avoid
  38 write-side contention and parallelize the other write-side overheads by
  39 providing a fine-grained locking design, however, it would be interesting
  40 to see how much of the performance advantage reported in 1990 remains
  41 in 2004.
  42
  43 At about this same time, Adams [Adams91] described ``chaotic relaxation'',
  44 where the normal barriers between successive iterations of convergent
  45 numerical algorithms are relaxed, so that iteration $n$ might use
  46 data from iteration $n-1$ or even $n-2$.  This introduces error,
  47 which typically slows convergence and thus increases the number of
  48 iterations required.  However, this increase is sometimes more than made
  49 up for by a reduction in the number of expensive barrier operations,
  50 which are otherwise required to synchronize the threads at the end
  51 of each iteration.  Unfortunately, chaotic relaxation requires highly
  52 structured data, such as the matrices used in scientific programs, and
  53 is thus inapplicable to most data structures in operating-system kernels.
  54
  55 In 1993, Jacobson [Jacobson93] verbally described what is perhaps the
  56 simplest deferred-free technique: simply waiting a fixed amount of time
  57 before freeing blocks awaiting deferred free.  Jacobson did not describe
  58 any write-side changes he might have made in this work using SGI's Irix
  59 kernel.  Aju John published a similar technique in 1995 [AjuJohn95].
  60 This works well if there is a well-defined upper bound on the length of
  61 time that reading threads can hold references, as there might well be in
  62 hard real-time systems.  However, if this time is exceeded, perhaps due
  63 to preemption, excessive interrupts, or larger-than-anticipated load,
  64 memory corruption can ensue, with no reasonable means of diagnosis.
  65 Jacobson's technique is therefore inappropriate for use in production
  66 operating-system kernels, except when such kernels can provide hard
  67 real-time response guarantees for all operations.
  68
  69 Also in 1995, Pu et al. [Pu95a] applied a technique similar to that of Pugh's
  70 read-side-tracking to permit replugging of algorithms within a commercial
  71 Unix operating system.  However, this replugging permitted only a single
  72 reader at a time.  The following year, this same group of researchers
  73 extended their technique to allow for multiple readers [Cowan96a].
  74 Their approach requires memory barriers (and thus pipeline stalls),
  75 but reduces memory latency, contention, and locking overheads.
  76
  77 1995 also saw the first publication of DYNIX/ptx's RCU mechanism
  78 [Slingwine95], which was optimized for modern CPU architectures,
  79 and was successfully applied to a number of situations within the
  80 DYNIX/ptx kernel.  The corresponding conference paper appeared in 1998
  81 [McKenney98].
  82
  83 In 1999, the Tornado and K42 groups described their "generations"
  84 mechanism, which quite similar to RCU [Gamsa99].  These operating systems
  85 made pervasive use of RCU in place of "existence locks", which greatly
  86 simplifies locking hierarchies.
  87
  88 2001 saw the first RCU presentation involving Linux [McKenney01a]
  89 at OLS.  The resulting abundance of RCU patches was presented the
  90 following year [McKenney02a], and use of RCU in dcache was first
  91 described that same year [Linder02a].
  92
  93 Also in 2002, Michael [Michael02b,Michael02a] presented "hazard-pointer"
  94 techniques that defer the destruction of data structures to simplify
  95 non-blocking synchronization (wait-free synchronization, lock-free
  96 synchronization, and obstruction-free synchronization are all examples of
  97 non-blocking synchronization).  In particular, this technique eliminates
  98 locking, reduces contention, reduces memory latency for readers, and
  99 parallelizes pipeline stalls and memory latency for writers.  However,
 100 these techniques still impose significant read-side overhead in the
 101 form of memory barriers.  Researchers at Sun worked along similar lines
 102 in the same timeframe [HerlihyLM02,HerlihyLMS03].  These techniques
 103 can be thought of as inside-out reference counts, where the count is
 104 represented by the number of hazard pointers referencing a given data
 105 structure (rather than the more conventional counter field within the
 106 data structure itself).
 107
 108 In 2003, the K42 group described how RCU could be used to create
 109 hot-pluggable implementations of operating-system functions.  Later that
 110 year saw a paper describing an RCU implementation of System V IPC
 111 [Arcangeli03], and an introduction to RCU in Linux Journal [McKenney03a].
 112
 113 2004 has seen a Linux-Journal article on use of RCU in dcache
 114 [McKenney04a], a performance comparison of locking to RCU on several
 115 different CPUs [McKenney04b], a dissertation describing use of RCU in a
 116 number of operating-system kernels [PaulEdwardMcKenneyPhD], a paper
 117 describing how to make RCU safe for soft-realtime applications [Sarma04c],
 118 and a paper describing SELinux performance with RCU [JamesMorris04b].
 119
 120 2005 has seen further adaptation of RCU to realtime use, permitting
 121 preemption of RCU realtime critical sections [PaulMcKenney05a,
 122 PaulMcKenney05b].
 123
 124 Bibtex Entries
 125
 126 @article{Kung80
 127 ,author="H. T. Kung and Q. Lehman"
 128 ,title="Concurrent Maintenance of Binary Search Trees"
 129 ,Year="1980"
 130 ,Month="September"
 131 ,journal="ACM Transactions on Database Systems"
 132 ,volume="5"
 133 ,number="3"
 134 ,pages="354-382"
 135 }
 136
 137 @techreport{Manber82
 138 ,author="Udi Manber and Richard E. Ladner"
 139 ,title="Concurrency Control in a Dynamic Search Structure"
 140 ,institution="Department of Computer Science, University of Washington"
 141 ,address="Seattle, Washington"
 142 ,year="1982"
 143 ,number="82-01-01"
 144 ,month="January"
 145 ,pages="28"
 146 }
 147
 148 @article{Manber84
 149 ,author="Udi Manber and Richard E. Ladner"
 150 ,title="Concurrency Control in a Dynamic Search Structure"
 151 ,Year="1984"
 152 ,Month="September"
 153 ,journal="ACM Transactions on Database Systems"
 154 ,volume="9"
 155 ,number="3"
 156 ,pages="439-455"
 157 }
 158
 159 @techreport{Hennessy89
 160 ,author="James P. Hennessy and Damian L. Osisek and Joseph W. {Seigh II}"
 161 ,title="Passive Serialization in a Multitasking Environment"
 162 ,institution="US Patent and Trademark Office"
 163 ,address="Washington, DC"
 164 ,year="1989"
 165 ,number="US Patent 4,809,168 (lapsed)"
 166 ,month="February"
 167 ,pages="11"
 168 }
 169
 170 @techreport{Pugh90
 171 ,author="William Pugh"
 172 ,title="Concurrent Maintenance of Skip Lists"
 173 ,institution="Institute of Advanced Computer Science Studies, Department of Computer Science, University of Maryland"
 174 ,address="College Park, Maryland"
 175 ,year="1990"
 176 ,number="CS-TR-2222.1"
 177 ,month="June"
 178 }
 179
 180 @Book{Adams91
 181 ,Author="Gregory R. Adams"
 182 ,title="Concurrent Programming, Principles, and Practices"
 183 ,Publisher="Benjamin Cummins"
 184 ,Year="1991"
 185 }
 186
 187 @unpublished{Jacobson93
 188 ,author="Van Jacobson"
 189 ,title="Avoid Read-Side Locking Via Delayed Free"
 190 ,year="1993"
 191 ,month="September"
 192 ,note="Verbal discussion"
 193 }
 194
 195 @Conference{AjuJohn95
 196 ,Author="Aju John"
 197 ,Title="Dynamic vnodes -- Design and Implementation"
 198 ,Booktitle="{USENIX Winter 1995}"
 199 ,Publisher="USENIX Association"
 200 ,Month="January"
 201 ,Year="1995"
 202 ,pages="11-23"
 203 ,Address="New Orleans, LA"
 204 }
 205
 206 @techreport{Slingwine95
 207 ,author="John D. Slingwine and Paul E. McKenney"
 208 ,title="Apparatus and Method for Achieving Reduced Overhead Mutual
 209 Exclusion and Maintaining Coherency in a Multiprocessor System
 210 Utilizing Execution History and Thread Monitoring"
 211 ,institution="US Patent and Trademark Office"
 212 ,address="Washington, DC"
 213 ,year="1995"
 214 ,number="US Patent 5,442,758 (contributed under GPL)"
 215 ,month="August"
 216 }
 217
 218 @techreport{Slingwine97
 219 ,author="John D. Slingwine and Paul E. McKenney"
 220 ,title="Method for maintaining data coherency using thread
 221 activity summaries in a multicomputer system"
 222 ,institution="US Patent and Trademark Office"
 223 ,address="Washington, DC"
 224 ,year="1997"
 225 ,number="US Patent 5,608,893 (contributed under GPL)"
 226 ,month="March"
 227 }
 228
 229 @techreport{Slingwine98
 230 ,author="John D. Slingwine and Paul E. McKenney"
 231 ,title="Apparatus and method for achieving reduced overhead
 232 mutual exclusion and maintaining coherency in a multiprocessor
 233 system utilizing execution history and thread monitoring"
 234 ,institution="US Patent and Trademark Office"
 235 ,address="Washington, DC"
 236 ,year="1998"
 237 ,number="US Patent 5,727,209 (contributed under GPL)"
 238 ,month="March"
 239 }
 240
 241 @Conference{McKenney98
 242 ,Author="Paul E. McKenney and John D. Slingwine"
 243 ,Title="Read-Copy Update: Using Execution History to Solve Concurrency
 244 Problems"
 245 ,Booktitle="{Parallel and Distributed Computing and Systems}"
 246 ,Month="October"
 247 ,Year="1998"
 248 ,pages="509-518"
 249 ,Address="Las Vegas, NV"
 250 }
 251
 252 @Conference{Gamsa99
 253 ,Author="Ben Gamsa and Orran Krieger and Jonathan Appavoo and Michael Stumm"
 254 ,Title="Tornado: Maximizing Locality and Concurrency in a Shared Memory
 255 Multiprocessor Operating System"
 256 ,Booktitle="{Proceedings of the 3\textsuperscript{rd} Symposium on
 257 Operating System Design and Implementation}"
 258 ,Month="February"
 259 ,Year="1999"
 260 ,pages="87-100"
 261 ,Address="New Orleans, LA"
 262 }
 263
 264 @techreport{Slingwine01
 265 ,author="John D. Slingwine and Paul E. McKenney"
 266 ,title="Apparatus and method for achieving reduced overhead
 267 mutual exclusion and maintaining coherency in a multiprocessor
 268 system utilizing execution history and thread monitoring"
 269 ,institution="US Patent and Trademark Office"
 270 ,address="Washington, DC"
 271 ,year="2001"
 272 ,number="US Patent 5,219,690 (contributed under GPL)"
 273 ,month="April"
 274 }
 275
 276 @Conference{McKenney01a
 277 ,Author="Paul E. McKenney and Jonathan Appavoo and Andi Kleen and
 278 Orran Krieger and Rusty Russell and Dipankar Sarma and Maneesh Soni"
 279 ,Title="Read-Copy Update"
 280 ,Booktitle="{Ottawa Linux Symposium}"
 281 ,Month="July"
 282 ,Year="2001"
 283 ,note="Available:
 284 \url{http://www.linuxsymposium.org/2001/abstracts/readcopy.php}
 285 \url{http://www.rdrop.com/users/paulmck/rclock/rclock_OLS.2001.05.01c.pdf}
 286 [Viewed June 23, 2004]"
 287 annotation="
 288 Described RCU, and presented some patches implementing and using it in
 289 the Linux kernel.
 290 "
 291 }
 292
 293 @Conference{Linder02a
 294 ,Author="Hanna Linder and Dipankar Sarma and Maneesh Soni"
 295 ,Title="Scalability of the Directory Entry Cache"
 296 ,Booktitle="{Ottawa Linux Symposium}"
 297 ,Month="June"
 298 ,Year="2002"
 299 ,pages="289-300"
 300 }
 301
 302 @Conference{McKenney02a
 303 ,Author="Paul E. McKenney and Dipankar Sarma and
 304 Andrea Arcangeli and Andi Kleen and Orran Krieger and Rusty Russell"
 305 ,Title="Read-Copy Update"
 306 ,Booktitle="{Ottawa Linux Symposium}"
 307 ,Month="June"
 308 ,Year="2002"
 309 ,pages="338-367"
 310 ,note="Available:
 311 \url{http://www.linux.org.uk/~ajh/ols2002_proceedings.pdf.gz}
 312 [Viewed June 23, 2004]"
 313 }
 314
 315 @article{Appavoo03a
 316 ,author="J. Appavoo and K. Hui and C. A. N. Soules and R. W. Wisniewski and
 317 D. M. {Da Silva} and O. Krieger and M. A. Auslander and D. J. Edelsohn and
 318 B. Gamsa and G. R. Ganger and P. McKenney and M. Ostrowski and
 319 B. Rosenburg and M. Stumm and J. Xenidis"
 320 ,title="Enabling Autonomic Behavior in Systems Software With Hot Swapping"
 321 ,Year="2003"
 322 ,Month="January"
 323 ,journal="IBM Systems Journal"
 324 ,volume="42"
 325 ,number="1"
 326 ,pages="60-76"
 327 }
 328
 329 @Conference{Arcangeli03
 330 ,Author="Andrea Arcangeli and Mingming Cao and Paul E. McKenney and
 331 Dipankar Sarma"
 332 ,Title="Using Read-Copy Update Techniques for {System V IPC} in the
 333 {Linux} 2.5 Kernel"
 334 ,Booktitle="Proceedings of the 2003 USENIX Annual Technical Conference
 335 (FREENIX Track)"
 336 ,Publisher="USENIX Association"
 337 ,year="2003"
 338 ,month="June"
 339 ,pages="297-310"
 340 }
 341
 342 @article{McKenney03a
 343 ,author="Paul E. McKenney"
 344 ,title="Using {RCU} in the {Linux} 2.5 Kernel"
 345 ,Year="2003"
 346 ,Month="October"
 347 ,journal="Linux Journal"
 348 ,volume="1"
 349 ,number="114"
 350 ,pages="18-26"
 351 }
 352
 353 @techreport{Friedberg03a
 354 ,author="Stuart A. Friedberg"
 355 ,title="Lock-Free Wild Card Search Data Structure and Method"
 356 ,institution="US Patent and Trademark Office"
 357 ,address="Washington, DC"
 358 ,year="2003"
 359 ,number="US Patent 6,662,184 (contributed under GPL)"
 360 ,month="December"
 361 ,pages="112"
 362 }
 363
 364 @article{McKenney04a
 365 ,author="Paul E. McKenney and Dipankar Sarma and Maneesh Soni"
 366 ,title="Scaling dcache with {RCU}"
 367 ,Year="2004"
 368 ,Month="January"
 369 ,journal="Linux Journal"
 370 ,volume="1"
 371 ,number="118"
 372 ,pages="38-46"
 373 }
 374
 375 @Conference{McKenney04b
 376 ,Author="Paul E. McKenney"
 377 ,Title="{RCU} vs. Locking Performance on Different {CPUs}"
 378 ,Booktitle="{linux.conf.au}"
 379 ,Month="January"
 380 ,Year="2004"
 381 ,Address="Adelaide, Australia"
 382 ,note="Available:
 383 \url{http://www.linux.org.au/conf/2004/abstracts.html#90}
 384 \url{http://www.rdrop.com/users/paulmck/rclock/lockperf.2004.01.17a.pdf}
 385 [Viewed June 23, 2004]"
 386 }
 387
 388 @phdthesis{PaulEdwardMcKenneyPhD
 389 ,author="Paul E. McKenney"
 390 ,title="Exploiting Deferred Destruction:
 391 An Analysis of Read-Copy-Update Techniques
 392 in Operating System Kernels"
 393 ,school="OGI School of Science and Engineering at
 394 Oregon Health and Sciences University"
 395 ,year="2004"
 396 ,note="Available:
 397 \url{http://www.rdrop.com/users/paulmck/RCU/RCUdissertation.2004.07.14e1.pdf}
 398 [Viewed October 15, 2004]"
 399 }
 400
 401 @Conference{Sarma04c
 402 ,Author="Dipankar Sarma and Paul E. McKenney"
 403 ,Title="Making RCU Safe for Deep Sub-Millisecond Response Realtime Applications"
 404 ,Booktitle="Proceedings of the 2004 USENIX Annual Technical Conference
 405 (FREENIX Track)"
 406 ,Publisher="USENIX Association"
 407 ,year="2004"
 408 ,month="June"
 409 ,pages="182-191"
 410 }
 411
 412 @unpublished{JamesMorris04b
 413 ,Author="James Morris"
 414 ,Title="Recent Developments in {SELinux} Kernel Performance"
 415 ,month="December"
 416 ,year="2004"
 417 ,note="Available:
 418 \url{http://www.livejournal.com/users/james_morris/2153.html}
 419 [Viewed December 10, 2004]"
 420 }
 421
 422 @unpublished{PaulMcKenney05a
 423 ,Author="Paul E. McKenney"
 424 ,Title="{[RFC]} {RCU} and {CONFIG\_PREEMPT\_RT} progress"
 425 ,month="May"
 426 ,year="2005"
 427 ,note="Available:
 428 \url{http://lkml.org/lkml/2005/5/9/185}
 429 [Viewed May 13, 2005]"
 430 ,annotation="
 431         First publication of working lock-based deferred free patches
 432         for the CONFIG_PREEMPT_RT environment.
 433 "
 434 }
 435
 436 @conference{PaulMcKenney05b
 437 ,Author="Paul E. McKenney and Dipankar Sarma"
 438 ,Title="Towards Hard Realtime Response from the Linux Kernel on SMP Hardware"
 439 ,Booktitle="linux.conf.au 2005"
 440 ,month="April"
 441 ,year="2005"
 442 ,address="Canberra, Australia"
 443 ,note="Available:
 444 \url{http://www.rdrop.com/users/paulmck/RCU/realtimeRCU.2005.04.23a.pdf}
 445 [Viewed May 13, 2005]"
 446 ,annotation="
 447         Realtime turns into making RCU yet more realtime friendly.
 448 "
 449 }