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