Commit | Line | Data |
---|---|---|
1da177e4 LT |
1 | Read the F-ing Papers! |
2 | ||
3 | ||
4 | This document describes RCU-related publications, and is followed by | |
dd81eca8 PM |
5 | the corresponding bibtex entries. A number of the publications may |
6 | be found at http://www.rdrop.com/users/paulmck/RCU/. | |
1da177e4 LT |
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 | |
f85d6c71 PM |
12 | collectors, but most production garbage collectors incur significant |
13 | overhead. | |
1da177e4 LT |
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 | |
4c54005c PM |
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!!!) | |
1da177e4 LT |
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 | ||
32300751 PM |
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 | ||
1da177e4 LT |
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 | ||
d19720a9 PM |
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 | |
f85d6c71 PM |
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. | |
1da177e4 LT |
119 | |
120 | In 2003, the K42 group described how RCU could be used to create | |
f85d6c71 PM |
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]. | |
1da177e4 LT |
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 | |
a83f1fe2 PM |
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]. | |
1da177e4 | 132 | |
f85d6c71 | 133 | 2005 brought further adaptation of RCU to realtime use, permitting |
dd81eca8 PM |
134 | preemption of RCU realtime critical sections [PaulMcKenney05a, |
135 | PaulMcKenney05b]. | |
136 | ||
f85d6c71 PM |
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 | ||
32300751 PM |
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]. | |
f85d6c71 | 152 | |
4c54005c PM |
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 | ||
1da177e4 LT |
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 | ||
32300751 PM |
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 | ||
1da177e4 LT |
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 | ||
f85d6c71 PM |
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 | ||
1da177e4 LT |
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 | ||
f85d6c71 PM |
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 | ||
1da177e4 LT |
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 | ||
a83f1fe2 PM |
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 | ||
1da177e4 LT |
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" | |
a83f1fe2 PM |
529 | ,note="Available: |
530 | \url{http://www.rdrop.com/users/paulmck/RCU/RCUdissertation.2004.07.14e1.pdf} | |
531 | [Viewed October 15, 2004]" | |
1da177e4 LT |
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 | } | |
a83f1fe2 PM |
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 | } | |
dd81eca8 PM |
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 | } | |
f85d6c71 PM |
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/view_abstract.php?content_key=184} | |
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 | ||
32300751 PM |
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 | ||
4c54005c PM |
745 | # |
746 | # "What is RCU?" LWN series. | |
747 | # | |
748 | ######################################################################## | |
749 | ||
32300751 PM |
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 | } | |
240ebbf8 PM |
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 | } | |
4c54005c PM |
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 | |
998f2ac3 | 867 | , title = "Low-Impact Operating System Tracing" |
4c54005c PM |
868 | , author = "Mathieu Desnoyers" |
869 | , school = "Ecole Polytechnique de Montr\'{e}al" | |
870 | , month = "December" | |
871 | , year = 2009 | |
998f2ac3 | 872 | ,note="Available: |
1bd22e37 | 873 | \url{http://www.lttng.org/pub/thesis/desnoyers-dissertation-2009-12.pdf} |
998f2ac3 | 874 | [Viewed December 9, 2009]" |
4c54005c | 875 | } |