Documentation: update broken web addresses.
[linux-2.6.git] / 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 most production garbage collectors incur significant
13 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
29 has lapsed, so this approach may be used in non-GPL software, if desired.
30 (In contrast, implementation of RCU is permitted only in software licensed
31 under either GPL or LGPL.  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 1992, Henry (now Alexia) Massalin completed a dissertation advising
56 parallel programmers to defer processing when feasible to simplify
57 synchronization.  RCU makes extremely heavy use of this advice.
58
59 In 1993, Jacobson [Jacobson93] verbally described what is perhaps the
60 simplest deferred-free technique: simply waiting a fixed amount of time
61 before freeing blocks awaiting deferred free.  Jacobson did not describe
62 any write-side changes he might have made in this work using SGI's Irix
63 kernel.  Aju John published a similar technique in 1995 [AjuJohn95].
64 This works well if there is a well-defined upper bound on the length of
65 time that reading threads can hold references, as there might well be in
66 hard real-time systems.  However, if this time is exceeded, perhaps due
67 to preemption, excessive interrupts, or larger-than-anticipated load,
68 memory corruption can ensue, with no reasonable means of diagnosis.
69 Jacobson's technique is therefore inappropriate for use in production
70 operating-system kernels, except when such kernels can provide hard
71 real-time response guarantees for all operations.
72
73 Also in 1995, Pu et al. [Pu95a] applied a technique similar to that of Pugh's
74 read-side-tracking to permit replugging of algorithms within a commercial
75 Unix operating system.  However, this replugging permitted only a single
76 reader at a time.  The following year, this same group of researchers
77 extended their technique to allow for multiple readers [Cowan96a].
78 Their approach requires memory barriers (and thus pipeline stalls),
79 but reduces memory latency, contention, and locking overheads.
80
81 1995 also saw the first publication of DYNIX/ptx's RCU mechanism
82 [Slingwine95], which was optimized for modern CPU architectures,
83 and was successfully applied to a number of situations within the
84 DYNIX/ptx kernel.  The corresponding conference paper appeared in 1998
85 [McKenney98].
86
87 In 1999, the Tornado and K42 groups described their "generations"
88 mechanism, which quite similar to RCU [Gamsa99].  These operating systems
89 made pervasive use of RCU in place of "existence locks", which greatly
90 simplifies locking hierarchies.
91
92 2001 saw the first RCU presentation involving Linux [McKenney01a]
93 at OLS.  The resulting abundance of RCU patches was presented the
94 following year [McKenney02a], and use of RCU in dcache was first
95 described that same year [Linder02a].
96
97 Also in 2002, Michael [Michael02b,Michael02a] presented "hazard-pointer"
98 techniques that defer the destruction of data structures to simplify
99 non-blocking synchronization (wait-free synchronization, lock-free
100 synchronization, and obstruction-free synchronization are all examples of
101 non-blocking synchronization).  In particular, this technique eliminates
102 locking, reduces contention, reduces memory latency for readers, and
103 parallelizes pipeline stalls and memory latency for writers.  However,
104 these techniques still impose significant read-side overhead in the
105 form of memory barriers.  Researchers at Sun worked along similar lines
106 in the same timeframe [HerlihyLM02].  These techniques can be thought
107 of as inside-out reference counts, where the count is represented by the
108 number of hazard pointers referencing a given data structure (rather than
109 the more conventional counter field within the data structure itself).
110
111 By the same token, RCU can be thought of as a "bulk reference count",
112 where some form of reference counter covers all reference by a given CPU
113 or thread during a set timeframe.  This timeframe is related to, but
114 not necessarily exactly the same as, an RCU grace period.  In classic
115 RCU, the reference counter is the per-CPU bit in the "bitmask" field,
116 and each such bit covers all references that might have been made by
117 the corresponding CPU during the prior grace period.  Of course, RCU
118 can be thought of in other terms as well.
119
120 In 2003, the K42 group described how RCU could be used to create
121 hot-pluggable implementations of operating-system functions [Appavoo03a].
122 Later that year saw a paper describing an RCU implementation of System
123 V IPC [Arcangeli03], and an introduction to RCU in Linux Journal
124 [McKenney03a].
125
126 2004 has seen a Linux-Journal article on use of RCU in dcache
127 [McKenney04a], a performance comparison of locking to RCU on several
128 different CPUs [McKenney04b], a dissertation describing use of RCU in a
129 number of operating-system kernels [PaulEdwardMcKenneyPhD], a paper
130 describing how to make RCU safe for soft-realtime applications [Sarma04c],
131 and a paper describing SELinux performance with RCU [JamesMorris04b].
132
133 2005 brought further adaptation of RCU to realtime use, permitting
134 preemption of RCU realtime critical sections [PaulMcKenney05a,
135 PaulMcKenney05b].
136
137 2006 saw the first best-paper award for an RCU paper [ThomasEHart2006a],
138 as well as further work on efficient implementations of preemptible
139 RCU [PaulEMcKenney2006b], but priority-boosting of RCU read-side critical
140 sections proved elusive.  An RCU implementation permitting general
141 blocking in read-side critical sections appeared [PaulEMcKenney2006c],
142 Robert Olsson described an RCU-protected trie-hash combination
143 [RobertOlsson2006a].
144
145 2007 saw the journal version of the award-winning RCU paper from 2006
146 [ThomasEHart2007a], as well as a paper demonstrating use of Promela
147 and Spin to mechanically verify an optimization to Oleg Nesterov's
148 QRCU [PaulEMcKenney2007QRCUspin], a design document describing
149 preemptible RCU [PaulEMcKenney2007PreemptibleRCU], and the three-part
150 LWN "What is RCU?" series [PaulEMcKenney2007WhatIsRCUFundamentally,
151 PaulEMcKenney2008WhatIsRCUUsage, and PaulEMcKenney2008WhatIsRCUAPI].
152
153 2008 saw a journal paper on real-time RCU [DinakarGuniguntala2008IBMSysJ],
154 a history of how Linux changed RCU more than RCU changed Linux
155 [PaulEMcKenney2008RCUOSR], and a design overview of hierarchical RCU
156 [PaulEMcKenney2008HierarchicalRCU].
157
158 2009 introduced user-level RCU algorithms [PaulEMcKenney2009MaliciousURCU],
159 which Mathieu Desnoyers is now maintaining [MathieuDesnoyers2009URCU]
160 [MathieuDesnoyersPhD].  TINY_RCU [PaulEMcKenney2009BloatWatchRCU] made
161 its appearance, as did expedited RCU [PaulEMcKenney2009expeditedRCU].
162 The problem of resizeable RCU-protected hash tables may now be on a path
163 to a solution [JoshTriplett2009RPHash].
164
165 Bibtex Entries
166
167 @article{Kung80
168 ,author="H. T. Kung and Q. Lehman"
169 ,title="Concurrent Maintenance of Binary Search Trees"
170 ,Year="1980"
171 ,Month="September"
172 ,journal="ACM Transactions on Database Systems"
173 ,volume="5"
174 ,number="3"
175 ,pages="354-382"
176 }
177
178 @techreport{Manber82
179 ,author="Udi Manber and Richard E. Ladner"
180 ,title="Concurrency Control in a Dynamic Search Structure"
181 ,institution="Department of Computer Science, University of Washington"
182 ,address="Seattle, Washington"
183 ,year="1982"
184 ,number="82-01-01"
185 ,month="January"
186 ,pages="28"
187 }
188
189 @article{Manber84
190 ,author="Udi Manber and Richard E. Ladner"
191 ,title="Concurrency Control in a Dynamic Search Structure"
192 ,Year="1984"
193 ,Month="September"
194 ,journal="ACM Transactions on Database Systems"
195 ,volume="9"
196 ,number="3"
197 ,pages="439-455"
198 }
199
200 @techreport{Hennessy89
201 ,author="James P. Hennessy and Damian L. Osisek and Joseph W. {Seigh II}"
202 ,title="Passive Serialization in a Multitasking Environment"
203 ,institution="US Patent and Trademark Office"
204 ,address="Washington, DC"
205 ,year="1989"
206 ,number="US Patent 4,809,168 (lapsed)"
207 ,month="February"
208 ,pages="11"
209 }
210
211 @techreport{Pugh90
212 ,author="William Pugh"
213 ,title="Concurrent Maintenance of Skip Lists"
214 ,institution="Institute of Advanced Computer Science Studies, Department of Computer Science, University of Maryland"
215 ,address="College Park, Maryland"
216 ,year="1990"
217 ,number="CS-TR-2222.1"
218 ,month="June"
219 }
220
221 @Book{Adams91
222 ,Author="Gregory R. Adams"
223 ,title="Concurrent Programming, Principles, and Practices"
224 ,Publisher="Benjamin Cummins"
225 ,Year="1991"
226 }
227
228 @phdthesis{HMassalinPhD
229 ,author="H. Massalin"
230 ,title="Synthesis: An Efficient Implementation of Fundamental Operating
231 System Services"
232 ,school="Columbia University"
233 ,address="New York, NY"
234 ,year="1992"
235 ,annotation="
236         Mondo optimizing compiler.
237         Wait-free stuff.
238         Good advice: defer work to avoid synchronization.
239 "
240 }
241
242 @unpublished{Jacobson93
243 ,author="Van Jacobson"
244 ,title="Avoid Read-Side Locking Via Delayed Free"
245 ,year="1993"
246 ,month="September"
247 ,note="Verbal discussion"
248 }
249
250 @Conference{AjuJohn95
251 ,Author="Aju John"
252 ,Title="Dynamic vnodes -- Design and Implementation"
253 ,Booktitle="{USENIX Winter 1995}"
254 ,Publisher="USENIX Association"
255 ,Month="January"
256 ,Year="1995"
257 ,pages="11-23"
258 ,Address="New Orleans, LA"
259 }
260
261 @conference{Pu95a,
262 Author = "Calton Pu and Tito Autrey and Andrew Black and Charles Consel and
263 Crispin Cowan and Jon Inouye and Lakshmi Kethana and Jonathan Walpole and
264 Ke Zhang",
265 Title = "Optimistic Incremental Specialization: Streamlining a Commercial
266 Operating System",
267 Booktitle = "15\textsuperscript{th} ACM Symposium on
268 Operating Systems Principles (SOSP'95)",
269 address = "Copper Mountain, CO",
270 month="December",
271 year="1995",
272 pages="314-321",
273 annotation="
274         Uses a replugger, but with a flag to signal when people are
275         using the resource at hand.  Only one reader at a time.
276 "
277 }
278
279 @conference{Cowan96a,
280 Author = "Crispin Cowan and Tito Autrey and Charles Krasic and
281 Calton Pu and Jonathan Walpole",
282 Title = "Fast Concurrent Dynamic Linking for an Adaptive Operating System",
283 Booktitle = "International Conference on Configurable Distributed Systems
284 (ICCDS'96)",
285 address = "Annapolis, MD",
286 month="May",
287 year="1996",
288 pages="108",
289 isbn="0-8186-7395-8",
290 annotation="
291         Uses a replugger, but with a counter to signal when people are
292         using the resource at hand.  Allows multiple readers.
293 "
294 }
295
296 @techreport{Slingwine95
297 ,author="John D. Slingwine and Paul E. McKenney"
298 ,title="Apparatus and Method for Achieving Reduced Overhead Mutual
299 Exclusion and Maintaining Coherency in a Multiprocessor System
300 Utilizing Execution History and Thread Monitoring"
301 ,institution="US Patent and Trademark Office"
302 ,address="Washington, DC"
303 ,year="1995"
304 ,number="US Patent 5,442,758 (contributed under GPL)"
305 ,month="August"
306 }
307
308 @techreport{Slingwine97
309 ,author="John D. Slingwine and Paul E. McKenney"
310 ,title="Method for maintaining data coherency using thread
311 activity summaries in a multicomputer system"
312 ,institution="US Patent and Trademark Office"
313 ,address="Washington, DC"
314 ,year="1997"
315 ,number="US Patent 5,608,893 (contributed under GPL)"
316 ,month="March"
317 }
318
319 @techreport{Slingwine98
320 ,author="John D. Slingwine and Paul E. McKenney"
321 ,title="Apparatus and method for achieving reduced overhead
322 mutual exclusion and maintaining coherency in a multiprocessor
323 system utilizing execution history and thread monitoring"
324 ,institution="US Patent and Trademark Office"
325 ,address="Washington, DC"
326 ,year="1998"
327 ,number="US Patent 5,727,209 (contributed under GPL)"
328 ,month="March"
329 }
330
331 @Conference{McKenney98
332 ,Author="Paul E. McKenney and John D. Slingwine"
333 ,Title="Read-Copy Update: Using Execution History to Solve Concurrency
334 Problems"
335 ,Booktitle="{Parallel and Distributed Computing and Systems}"
336 ,Month="October"
337 ,Year="1998"
338 ,pages="509-518"
339 ,Address="Las Vegas, NV"
340 }
341
342 @Conference{Gamsa99
343 ,Author="Ben Gamsa and Orran Krieger and Jonathan Appavoo and Michael Stumm"
344 ,Title="Tornado: Maximizing Locality and Concurrency in a Shared Memory
345 Multiprocessor Operating System"
346 ,Booktitle="{Proceedings of the 3\textsuperscript{rd} Symposium on
347 Operating System Design and Implementation}"
348 ,Month="February"
349 ,Year="1999"
350 ,pages="87-100"
351 ,Address="New Orleans, LA"
352 }
353
354 @techreport{Slingwine01
355 ,author="John D. Slingwine and Paul E. McKenney"
356 ,title="Apparatus and method for achieving reduced overhead
357 mutual exclusion and maintaining coherency in a multiprocessor
358 system utilizing execution history and thread monitoring"
359 ,institution="US Patent and Trademark Office"
360 ,address="Washington, DC"
361 ,year="2001"
362 ,number="US Patent 5,219,690 (contributed under GPL)"
363 ,month="April"
364 }
365
366 @Conference{McKenney01a
367 ,Author="Paul E. McKenney and Jonathan Appavoo and Andi Kleen and
368 Orran Krieger and Rusty Russell and Dipankar Sarma and Maneesh Soni"
369 ,Title="Read-Copy Update"
370 ,Booktitle="{Ottawa Linux Symposium}"
371 ,Month="July"
372 ,Year="2001"
373 ,note="Available:
374 \url{http://www.linuxsymposium.org/2001/abstracts/readcopy.php}
375 \url{http://www.rdrop.com/users/paulmck/rclock/rclock_OLS.2001.05.01c.pdf}
376 [Viewed June 23, 2004]"
377 annotation="
378 Described RCU, and presented some patches implementing and using it in
379 the Linux kernel.
380 "
381 }
382
383 @Conference{Linder02a
384 ,Author="Hanna Linder and Dipankar Sarma and Maneesh Soni"
385 ,Title="Scalability of the Directory Entry Cache"
386 ,Booktitle="{Ottawa Linux Symposium}"
387 ,Month="June"
388 ,Year="2002"
389 ,pages="289-300"
390 }
391
392 @Conference{McKenney02a
393 ,Author="Paul E. McKenney and Dipankar Sarma and
394 Andrea Arcangeli and Andi Kleen and Orran Krieger and Rusty Russell"
395 ,Title="Read-Copy Update"
396 ,Booktitle="{Ottawa Linux Symposium}"
397 ,Month="June"
398 ,Year="2002"
399 ,pages="338-367"
400 ,note="Available:
401 \url{http://www.linux.org.uk/~ajh/ols2002_proceedings.pdf.gz}
402 [Viewed June 23, 2004]"
403 }
404
405 @conference{Michael02a
406 ,author="Maged M. Michael"
407 ,title="Safe Memory Reclamation for Dynamic Lock-Free Objects Using Atomic
408 Reads and Writes"
409 ,Year="2002"
410 ,Month="August"
411 ,booktitle="{Proceedings of the 21\textsuperscript{st} Annual ACM
412 Symposium on Principles of Distributed Computing}"
413 ,pages="21-30"
414 ,annotation="
415         Each thread keeps an array of pointers to items that it is
416         currently referencing.  Sort of an inside-out garbage collection
417         mechanism, but one that requires the accessing code to explicitly
418         state its needs.  Also requires read-side memory barriers on
419         most architectures.
420 "
421 }
422
423 @conference{Michael02b
424 ,author="Maged M. Michael"
425 ,title="High Performance Dynamic Lock-Free Hash Tables and List-Based Sets"
426 ,Year="2002"
427 ,Month="August"
428 ,booktitle="{Proceedings of the 14\textsuperscript{th} Annual ACM
429 Symposium on Parallel
430 Algorithms and Architecture}"
431 ,pages="73-82"
432 ,annotation="
433         Like the title says...
434 "
435 }
436
437 @InProceedings{HerlihyLM02
438 ,author={Maurice Herlihy and Victor Luchangco and Mark Moir}
439 ,title="The Repeat Offender Problem: A Mechanism for Supporting Dynamic-Sized,
440 Lock-Free Data Structures"
441 ,booktitle={Proceedings of 16\textsuperscript{th} International
442 Symposium on Distributed Computing}
443 ,year=2002
444 ,month="October"
445 ,pages="339-353"
446 }
447
448 @article{Appavoo03a
449 ,author="J. Appavoo and K. Hui and C. A. N. Soules and R. W. Wisniewski and
450 D. M. {Da Silva} and O. Krieger and M. A. Auslander and D. J. Edelsohn and
451 B. Gamsa and G. R. Ganger and P. McKenney and M. Ostrowski and
452 B. Rosenburg and M. Stumm and J. Xenidis"
453 ,title="Enabling Autonomic Behavior in Systems Software With Hot Swapping"
454 ,Year="2003"
455 ,Month="January"
456 ,journal="IBM Systems Journal"
457 ,volume="42"
458 ,number="1"
459 ,pages="60-76"
460 }
461
462 @Conference{Arcangeli03
463 ,Author="Andrea Arcangeli and Mingming Cao and Paul E. McKenney and
464 Dipankar Sarma"
465 ,Title="Using Read-Copy Update Techniques for {System V IPC} in the
466 {Linux} 2.5 Kernel"
467 ,Booktitle="Proceedings of the 2003 USENIX Annual Technical Conference
468 (FREENIX Track)"
469 ,Publisher="USENIX Association"
470 ,year="2003"
471 ,month="June"
472 ,pages="297-310"
473 }
474
475 @article{McKenney03a
476 ,author="Paul E. McKenney"
477 ,title="Using {RCU} in the {Linux} 2.5 Kernel"
478 ,Year="2003"
479 ,Month="October"
480 ,journal="Linux Journal"
481 ,volume="1"
482 ,number="114"
483 ,pages="18-26"
484 }
485
486 @techreport{Friedberg03a
487 ,author="Stuart A. Friedberg"
488 ,title="Lock-Free Wild Card Search Data Structure and Method"
489 ,institution="US Patent and Trademark Office"
490 ,address="Washington, DC"
491 ,year="2003"
492 ,number="US Patent 6,662,184 (contributed under GPL)"
493 ,month="December"
494 ,pages="112"
495 }
496
497 @article{McKenney04a
498 ,author="Paul E. McKenney and Dipankar Sarma and Maneesh Soni"
499 ,title="Scaling dcache with {RCU}"
500 ,Year="2004"
501 ,Month="January"
502 ,journal="Linux Journal"
503 ,volume="1"
504 ,number="118"
505 ,pages="38-46"
506 }
507
508 @Conference{McKenney04b
509 ,Author="Paul E. McKenney"
510 ,Title="{RCU} vs. Locking Performance on Different {CPUs}"
511 ,Booktitle="{linux.conf.au}"
512 ,Month="January"
513 ,Year="2004"
514 ,Address="Adelaide, Australia"
515 ,note="Available:
516 \url{http://www.linux.org.au/conf/2004/abstracts.html#90}
517 \url{http://www.rdrop.com/users/paulmck/rclock/lockperf.2004.01.17a.pdf}
518 [Viewed June 23, 2004]"
519 }
520
521 @phdthesis{PaulEdwardMcKenneyPhD
522 ,author="Paul E. McKenney"
523 ,title="Exploiting Deferred Destruction:
524 An Analysis of Read-Copy-Update Techniques
525 in Operating System Kernels"
526 ,school="OGI School of Science and Engineering at
527 Oregon Health and Sciences University"
528 ,year="2004"
529 ,note="Available:
530 \url{http://www.rdrop.com/users/paulmck/RCU/RCUdissertation.2004.07.14e1.pdf}
531 [Viewed October 15, 2004]"
532 }
533
534 @Conference{Sarma04c
535 ,Author="Dipankar Sarma and Paul E. McKenney"
536 ,Title="Making RCU Safe for Deep Sub-Millisecond Response Realtime Applications"
537 ,Booktitle="Proceedings of the 2004 USENIX Annual Technical Conference
538 (FREENIX Track)"
539 ,Publisher="USENIX Association"
540 ,year="2004"
541 ,month="June"
542 ,pages="182-191"
543 }
544
545 @unpublished{JamesMorris04b
546 ,Author="James Morris"
547 ,Title="Recent Developments in {SELinux} Kernel Performance"
548 ,month="December"
549 ,year="2004"
550 ,note="Available:
551 \url{http://www.livejournal.com/users/james_morris/2153.html}
552 [Viewed December 10, 2004]"
553 }
554
555 @unpublished{PaulMcKenney05a
556 ,Author="Paul E. McKenney"
557 ,Title="{[RFC]} {RCU} and {CONFIG\_PREEMPT\_RT} progress"
558 ,month="May"
559 ,year="2005"
560 ,note="Available:
561 \url{http://lkml.org/lkml/2005/5/9/185}
562 [Viewed May 13, 2005]"
563 ,annotation="
564         First publication of working lock-based deferred free patches
565         for the CONFIG_PREEMPT_RT environment.
566 "
567 }
568
569 @conference{PaulMcKenney05b
570 ,Author="Paul E. McKenney and Dipankar Sarma"
571 ,Title="Towards Hard Realtime Response from the Linux Kernel on SMP Hardware"
572 ,Booktitle="linux.conf.au 2005"
573 ,month="April"
574 ,year="2005"
575 ,address="Canberra, Australia"
576 ,note="Available:
577 \url{http://www.rdrop.com/users/paulmck/RCU/realtimeRCU.2005.04.23a.pdf}
578 [Viewed May 13, 2005]"
579 ,annotation="
580         Realtime turns into making RCU yet more realtime friendly.
581 "
582 }
583
584 @conference{ThomasEHart2006a
585 ,Author="Thomas E. Hart and Paul E. McKenney and Angela Demke Brown"
586 ,Title="Making Lockless Synchronization Fast: Performance Implications
587 of Memory Reclamation"
588 ,Booktitle="20\textsuperscript{th} {IEEE} International Parallel and
589 Distributed Processing Symposium"
590 ,month="April"
591 ,year="2006"
592 ,day="25-29"
593 ,address="Rhodes, Greece"
594 ,annotation="
595         Compares QSBR (AKA "classic RCU"), HPBR, EBR, and lock-free
596         reference counting.
597 "
598 }
599
600 @Conference{PaulEMcKenney2006b
601 ,Author="Paul E. McKenney and Dipankar Sarma and Ingo Molnar and
602 Suparna Bhattacharya"
603 ,Title="Extending RCU for Realtime and Embedded Workloads"
604 ,Booktitle="{Ottawa Linux Symposium}"
605 ,Month="July"
606 ,Year="2006"
607 ,pages="v2 123-138"
608 ,note="Available:
609 \url{http://www.linuxsymposium.org/2006/index_2006.php}
610 \url{http://www.rdrop.com/users/paulmck/RCU/OLSrtRCU.2006.08.11a.pdf}
611 [Viewed January 1, 2007]"
612 ,annotation="
613         Described how to improve the -rt implementation of realtime RCU.
614 "
615 }
616
617 @unpublished{PaulEMcKenney2006c
618 ,Author="Paul E. McKenney"
619 ,Title="Sleepable {RCU}"
620 ,month="October"
621 ,day="9"
622 ,year="2006"
623 ,note="Available:
624 \url{http://lwn.net/Articles/202847/}
625 Revised:
626 \url{http://www.rdrop.com/users/paulmck/RCU/srcu.2007.01.14a.pdf}
627 [Viewed August 21, 2006]"
628 ,annotation="
629         LWN article introducing SRCU.
630 "
631 }
632
633 @unpublished{RobertOlsson2006a
634 ,Author="Robert Olsson and Stefan Nilsson"
635 ,Title="{TRASH}: A dynamic {LC}-trie and hash data structure"
636 ,month="August"
637 ,day="18"
638 ,year="2006"
639 ,note="Available:
640 \url{http://www.nada.kth.se/~snilsson/public/papers/trash/trash.pdf}
641 [Viewed February 24, 2007]"
642 ,annotation="
643         RCU-protected dynamic trie-hash combination.
644 "
645 }
646
647 @unpublished{ThomasEHart2007a
648 ,Author="Thomas E. Hart and Paul E. McKenney and Angela Demke Brown and Jonathan Walpole"
649 ,Title="Performance of memory reclamation for lockless synchronization"
650 ,journal="J. Parallel Distrib. Comput."
651 ,year="2007"
652 ,note="To appear in J. Parallel Distrib. Comput.
653        \url{doi=10.1016/j.jpdc.2007.04.010}"
654 ,annotation={
655         Compares QSBR (AKA "classic RCU"), HPBR, EBR, and lock-free
656         reference counting.  Journal version of ThomasEHart2006a.
657 }
658 }
659
660 @unpublished{PaulEMcKenney2007QRCUspin
661 ,Author="Paul E. McKenney"
662 ,Title="Using Promela and Spin to verify parallel algorithms"
663 ,month="August"
664 ,day="1"
665 ,year="2007"
666 ,note="Available:
667 \url{http://lwn.net/Articles/243851/}
668 [Viewed September 8, 2007]"
669 ,annotation="
670         LWN article describing Promela and spin, and also using Oleg
671         Nesterov's QRCU as an example (with Paul McKenney's fastpath).
672 "
673 }
674
675 @unpublished{PaulEMcKenney2007PreemptibleRCU
676 ,Author="Paul E. McKenney"
677 ,Title="The design of preemptible read-copy-update"
678 ,month="October"
679 ,day="8"
680 ,year="2007"
681 ,note="Available:
682 \url{http://lwn.net/Articles/253651/}
683 [Viewed October 25, 2007]"
684 ,annotation="
685         LWN article describing the design of preemptible RCU.
686 "
687 }
688
689 ########################################################################
690 #
691 #       "What is RCU?" LWN series.
692 #
693
694 @unpublished{PaulEMcKenney2007WhatIsRCUFundamentally
695 ,Author="Paul E. McKenney and Jonathan Walpole"
696 ,Title="What is {RCU}, Fundamentally?"
697 ,month="December"
698 ,day="17"
699 ,year="2007"
700 ,note="Available:
701 \url{http://lwn.net/Articles/262464/}
702 [Viewed December 27, 2007]"
703 ,annotation="
704         Lays out the three basic components of RCU: (1) publish-subscribe,
705         (2) wait for pre-existing readers to complete, and (2) maintain
706         multiple versions.
707 "
708 }
709
710 @unpublished{PaulEMcKenney2008WhatIsRCUUsage
711 ,Author="Paul E. McKenney"
712 ,Title="What is {RCU}? Part 2: Usage"
713 ,month="January"
714 ,day="4"
715 ,year="2008"
716 ,note="Available:
717 \url{http://lwn.net/Articles/263130/}
718 [Viewed January 4, 2008]"
719 ,annotation="
720         Lays out six uses of RCU:
721         1. RCU is a Reader-Writer Lock Replacement
722         2. RCU is a Restricted Reference-Counting Mechanism
723         3. RCU is a Bulk Reference-Counting Mechanism
724         4. RCU is a Poor Man's Garbage Collector
725         5. RCU is a Way of Providing Existence Guarantees
726         6. RCU is a Way of Waiting for Things to Finish 
727 "
728 }
729
730 @unpublished{PaulEMcKenney2008WhatIsRCUAPI
731 ,Author="Paul E. McKenney"
732 ,Title="{RCU} part 3: the {RCU} {API}"
733 ,month="January"
734 ,day="17"
735 ,year="2008"
736 ,note="Available:
737 \url{http://lwn.net/Articles/264090/}
738 [Viewed January 10, 2008]"
739 ,annotation="
740         Gives an overview of the Linux-kernel RCU API and a brief annotated RCU
741         bibliography.
742 "
743 }
744
745 #
746 #       "What is RCU?" LWN series.
747 #
748 ########################################################################
749
750 @article{DinakarGuniguntala2008IBMSysJ
751 ,author="D. Guniguntala and P. E. McKenney and J. Triplett and J. Walpole"
752 ,title="The read-copy-update mechanism for supporting real-time applications on shared-memory multiprocessor systems with {Linux}"
753 ,Year="2008"
754 ,Month="April"
755 ,journal="IBM Systems Journal"
756 ,volume="47"
757 ,number="2"
758 ,pages="@@-@@"
759 ,annotation="
760         RCU, realtime RCU, sleepable RCU, performance.
761 "
762 }
763
764 @article{PaulEMcKenney2008RCUOSR
765 ,author="Paul E. McKenney and Jonathan Walpole"
766 ,title="Introducing technology into the {Linux} kernel: a case study"
767 ,Year="2008"
768 ,journal="SIGOPS Oper. Syst. Rev."
769 ,volume="42"
770 ,number="5"
771 ,pages="4--17"
772 ,issn="0163-5980"
773 ,doi={http://doi.acm.org/10.1145/1400097.1400099}
774 ,publisher="ACM"
775 ,address="New York, NY, USA"
776 ,annotation={
777         Linux changed RCU to a far greater degree than RCU has changed Linux.
778 }
779 }
780
781 @unpublished{PaulEMcKenney2008HierarchicalRCU
782 ,Author="Paul E. McKenney"
783 ,Title="Hierarchical {RCU}"
784 ,month="November"
785 ,day="3"
786 ,year="2008"
787 ,note="Available:
788 \url{http://lwn.net/Articles/305782/}
789 [Viewed November 6, 2008]"
790 ,annotation="
791         RCU with combining-tree-based grace-period detection,
792         permitting it to handle thousands of CPUs.
793 "
794 }
795
796 @conference{PaulEMcKenney2009MaliciousURCU
797 ,Author="Paul E. McKenney"
798 ,Title="Using a Malicious User-Level {RCU} to Torture {RCU}-Based Algorithms"
799 ,Booktitle="linux.conf.au 2009"
800 ,month="January"
801 ,year="2009"
802 ,address="Hobart, Australia"
803 ,note="Available:
804 \url{http://www.rdrop.com/users/paulmck/RCU/urcutorture.2009.01.22a.pdf}
805 [Viewed February 2, 2009]"
806 ,annotation="
807         Realtime RCU and torture-testing RCU uses.
808 "
809 }
810
811 @unpublished{MathieuDesnoyers2009URCU
812 ,Author="Mathieu Desnoyers"
813 ,Title="[{RFC} git tree] Userspace {RCU} (urcu) for {Linux}"
814 ,month="February"
815 ,day="5"
816 ,year="2009"
817 ,note="Available:
818 \url{http://lkml.org/lkml/2009/2/5/572}
819 \url{git://lttng.org/userspace-rcu.git}
820 [Viewed February 20, 2009]"
821 ,annotation="
822         Mathieu Desnoyers's user-space RCU implementation.
823         git://lttng.org/userspace-rcu.git
824 "
825 }
826
827 @unpublished{PaulEMcKenney2009BloatWatchRCU
828 ,Author="Paul E. McKenney"
829 ,Title="{RCU}: The {Bloatwatch} Edition"
830 ,month="March"
831 ,day="17"
832 ,year="2009"
833 ,note="Available:
834 \url{http://lwn.net/Articles/323929/}
835 [Viewed March 20, 2009]"
836 ,annotation="
837         Uniprocessor assumptions allow simplified RCU implementation.
838 "
839 }
840
841 @unpublished{PaulEMcKenney2009expeditedRCU
842 ,Author="Paul E. McKenney"
843 ,Title="[{PATCH} -tip 0/3] expedited 'big hammer' {RCU} grace periods"
844 ,month="June"
845 ,day="25"
846 ,year="2009"
847 ,note="Available:
848 \url{http://lkml.org/lkml/2009/6/25/306}
849 [Viewed August 16, 2009]"
850 ,annotation="
851         First posting of expedited RCU to be accepted into -tip.
852 "
853 }
854
855 @unpublished{JoshTriplett2009RPHash
856 ,Author="Josh Triplett"
857 ,Title="Scalable concurrent hash tables via relativistic programming"
858 ,month="September"
859 ,year="2009"
860 ,note="Linux Plumbers Conference presentation"
861 ,annotation="
862         RP fun with hash tables.
863 "
864 }
865
866 @phdthesis{MathieuDesnoyersPhD
867 , title  = "Low-Impact Operating System Tracing"
868 , author = "Mathieu Desnoyers"
869 , school = "Ecole Polytechnique de Montr\'{e}al"
870 , month  = "December"
871 , year   = 2009
872 ,note="Available:
873 \url{http://www.lttng.org/pub/thesis/desnoyers-dissertation-2009-12.pdf}
874 [Viewed December 9, 2009]"
875 }