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