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