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