blob: 7c1dfb19fc40a9074f2cc182f356f458df802d44 [file] [log] [blame]
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001Read the Fscking Papers!
Linus Torvalds1da177e2005-04-16 15:20:36 -07002
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
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08006be found at http://www.rdrop.com/users/paulmck/RCU/. For others, browsers
7and search engines will usually find what you are looking for.
Linus Torvalds1da177e2005-04-16 15:20:36 -07008
9The first thing resembling RCU was published in 1980, when Kung and Lehman
10[Kung80] recommended use of a garbage collector to defer destruction
11of nodes in a parallel binary search tree in order to simplify its
12implementation. This works well in environments that have garbage
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +010013collectors, but most production garbage collectors incur significant
14overhead.
Linus Torvalds1da177e2005-04-16 15:20:36 -070015
16In 1982, Manber and Ladner [Manber82,Manber84] recommended deferring
17destruction until all threads running at that time have terminated, again
18for a parallel binary search tree. This approach works well in systems
19with short-lived threads, such as the K42 research operating system.
20However, Linux has long-lived tasks, so more is needed.
21
22In 1986, Hennessy, Osisek, and Seigh [Hennessy89] introduced passive
23serialization, which is an RCU-like mechanism that relies on the presence
24of "quiescent states" in the VM/XA hypervisor that are guaranteed not
25to be referencing the data structure. However, this mechanism was not
26optimized for modern computer systems, which is not surprising given
27that these overheads were not so expensive in the mid-80s. Nonetheless,
28passive serialization appears to be the first deferred-destruction
Paul E. McKenney4c540052010-01-14 16:10:57 -080029mechanism to be used in production. Furthermore, the relevant patent
30has lapsed, so this approach may be used in non-GPL software, if desired.
31(In contrast, implementation of RCU is permitted only in software licensed
32under either GPL or LGPL. Sorry!!!)
Linus Torvalds1da177e2005-04-16 15:20:36 -070033
34In 1990, Pugh [Pugh90] noted that explicitly tracking which threads
35were reading a given data structure permitted deferred free to operate
36in the presence of non-terminating threads. However, this explicit
37tracking imposes significant read-side overhead, which is undesirable
38in read-mostly situations. This algorithm does take pains to avoid
39write-side contention and parallelize the other write-side overheads by
40providing a fine-grained locking design, however, it would be interesting
41to see how much of the performance advantage reported in 1990 remains
42in 2004.
43
44At about this same time, Adams [Adams91] described ``chaotic relaxation'',
45where the normal barriers between successive iterations of convergent
46numerical algorithms are relaxed, so that iteration $n$ might use
47data from iteration $n-1$ or even $n-2$. This introduces error,
48which typically slows convergence and thus increases the number of
49iterations required. However, this increase is sometimes more than made
50up for by a reduction in the number of expensive barrier operations,
51which are otherwise required to synchronize the threads at the end
52of each iteration. Unfortunately, chaotic relaxation requires highly
53structured data, such as the matrices used in scientific programs, and
54is thus inapplicable to most data structures in operating-system kernels.
55
Paul E. McKenney32300752008-05-12 21:21:05 +020056In 1992, Henry (now Alexia) Massalin completed a dissertation advising
57parallel programmers to defer processing when feasible to simplify
58synchronization. RCU makes extremely heavy use of this advice.
59
Linus Torvalds1da177e2005-04-16 15:20:36 -070060In 1993, Jacobson [Jacobson93] verbally described what is perhaps the
61simplest deferred-free technique: simply waiting a fixed amount of time
62before freeing blocks awaiting deferred free. Jacobson did not describe
63any write-side changes he might have made in this work using SGI's Irix
64kernel. Aju John published a similar technique in 1995 [AjuJohn95].
65This works well if there is a well-defined upper bound on the length of
66time that reading threads can hold references, as there might well be in
67hard real-time systems. However, if this time is exceeded, perhaps due
68to preemption, excessive interrupts, or larger-than-anticipated load,
69memory corruption can ensue, with no reasonable means of diagnosis.
70Jacobson's technique is therefore inappropriate for use in production
71operating-system kernels, except when such kernels can provide hard
72real-time response guarantees for all operations.
73
74Also in 1995, Pu et al. [Pu95a] applied a technique similar to that of Pugh's
75read-side-tracking to permit replugging of algorithms within a commercial
76Unix operating system. However, this replugging permitted only a single
77reader at a time. The following year, this same group of researchers
78extended their technique to allow for multiple readers [Cowan96a].
79Their approach requires memory barriers (and thus pipeline stalls),
80but reduces memory latency, contention, and locking overheads.
81
821995 also saw the first publication of DYNIX/ptx's RCU mechanism
83[Slingwine95], which was optimized for modern CPU architectures,
84and was successfully applied to a number of situations within the
85DYNIX/ptx kernel. The corresponding conference paper appeared in 1998
86[McKenney98].
87
88In 1999, the Tornado and K42 groups described their "generations"
89mechanism, which quite similar to RCU [Gamsa99]. These operating systems
90made pervasive use of RCU in place of "existence locks", which greatly
91simplifies locking hierarchies.
92
932001 saw the first RCU presentation involving Linux [McKenney01a]
94at OLS. The resulting abundance of RCU patches was presented the
95following year [McKenney02a], and use of RCU in dcache was first
96described that same year [Linder02a].
97
Paul E. McKenneyd19720a2006-02-01 03:06:42 -080098Also in 2002, Michael [Michael02b,Michael02a] presented "hazard-pointer"
99techniques that defer the destruction of data structures to simplify
100non-blocking synchronization (wait-free synchronization, lock-free
101synchronization, and obstruction-free synchronization are all examples of
102non-blocking synchronization). In particular, this technique eliminates
103locking, reduces contention, reduces memory latency for readers, and
104parallelizes pipeline stalls and memory latency for writers. However,
105these techniques still impose significant read-side overhead in the
106form of memory barriers. Researchers at Sun worked along similar lines
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +0100107in the same timeframe [HerlihyLM02]. These techniques can be thought
108of as inside-out reference counts, where the count is represented by the
109number of hazard pointers referencing a given data structure (rather than
110the more conventional counter field within the data structure itself).
111
112By the same token, RCU can be thought of as a "bulk reference count",
113where some form of reference counter covers all reference by a given CPU
114or thread during a set timeframe. This timeframe is related to, but
115not necessarily exactly the same as, an RCU grace period. In classic
116RCU, the reference counter is the per-CPU bit in the "bitmask" field,
117and each such bit covers all references that might have been made by
118the corresponding CPU during the prior grace period. Of course, RCU
119can be thought of in other terms as well.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700120
121In 2003, the K42 group described how RCU could be used to create
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +0100122hot-pluggable implementations of operating-system functions [Appavoo03a].
123Later that year saw a paper describing an RCU implementation of System
124V IPC [Arcangeli03], and an introduction to RCU in Linux Journal
125[McKenney03a].
Linus Torvalds1da177e2005-04-16 15:20:36 -0700126
1272004 has seen a Linux-Journal article on use of RCU in dcache
128[McKenney04a], a performance comparison of locking to RCU on several
129different CPUs [McKenney04b], a dissertation describing use of RCU in a
Paul E. McKenneya83f1fe2005-05-01 08:59:05 -0700130number of operating-system kernels [PaulEdwardMcKenneyPhD], a paper
131describing how to make RCU safe for soft-realtime applications [Sarma04c],
132and a paper describing SELinux performance with RCU [JamesMorris04b].
Linus Torvalds1da177e2005-04-16 15:20:36 -0700133
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +01001342005 brought further adaptation of RCU to realtime use, permitting
Paul E. McKenneydd81eca2005-09-10 00:26:24 -0700135preemption of RCU realtime critical sections [PaulMcKenney05a,
136PaulMcKenney05b].
137
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +01001382006 saw the first best-paper award for an RCU paper [ThomasEHart2006a],
139as well as further work on efficient implementations of preemptible
140RCU [PaulEMcKenney2006b], but priority-boosting of RCU read-side critical
141sections proved elusive. An RCU implementation permitting general
142blocking in read-side critical sections appeared [PaulEMcKenney2006c],
143Robert Olsson described an RCU-protected trie-hash combination
144[RobertOlsson2006a].
145
Paul E. McKenney32300752008-05-12 21:21:05 +02001462007 saw the journal version of the award-winning RCU paper from 2006
147[ThomasEHart2007a], as well as a paper demonstrating use of Promela
148and Spin to mechanically verify an optimization to Oleg Nesterov's
149QRCU [PaulEMcKenney2007QRCUspin], a design document describing
150preemptible RCU [PaulEMcKenney2007PreemptibleRCU], and the three-part
151LWN "What is RCU?" series [PaulEMcKenney2007WhatIsRCUFundamentally,
152PaulEMcKenney2008WhatIsRCUUsage, and PaulEMcKenney2008WhatIsRCUAPI].
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +0100153
Paul E. McKenney4c540052010-01-14 16:10:57 -08001542008 saw a journal paper on real-time RCU [DinakarGuniguntala2008IBMSysJ],
155a history of how Linux changed RCU more than RCU changed Linux
156[PaulEMcKenney2008RCUOSR], and a design overview of hierarchical RCU
157[PaulEMcKenney2008HierarchicalRCU].
158
1592009 introduced user-level RCU algorithms [PaulEMcKenney2009MaliciousURCU],
160which Mathieu Desnoyers is now maintaining [MathieuDesnoyers2009URCU]
161[MathieuDesnoyersPhD]. TINY_RCU [PaulEMcKenney2009BloatWatchRCU] made
162its appearance, as did expedited RCU [PaulEMcKenney2009expeditedRCU].
163The problem of resizeable RCU-protected hash tables may now be on a path
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800164to a solution [JoshTriplett2009RPHash]. A few academic researchers are now
165using RCU to solve their parallel problems [HariKannan2009DynamicAnalysisRCU].
166
1672010 produced a simpler preemptible-RCU implementation
168based on TREE_RCU [PaulEMcKenney2010SimpleOptRCU], lockdep-RCU
169[PaulEMcKenney2010LockdepRCU], another resizeable RCU-protected hash
170table [HerbertXu2010RCUResizeHash] (this one consuming more memory,
171but allowing arbitrary changes in hash function, as required for DoS
172avoidance in the networking code), realization of the 2009 RCU-protected
173hash table with atomic node move [JoshTriplett2010RPHash], an update on
174the RCU API [PaulEMcKenney2010RCUAPI].
175
1762011 marked the inclusion of Nick Piggin's fully lockless dentry search
177[LinusTorvalds2011Linux2:6:38:rc1:NPigginVFS], an RCU-protected red-black
178tree using software transactional memory to protect concurrent updates
179(strange, but true!) [PhilHoward2011RCUTMRBTree], yet another variant of
180RCU-protected resizeable hash tables [Triplett:2011:RPHash], the 3.0 RCU
181trainwreck [PaulEMcKenney2011RCU3.0trainwreck], and Neil Brown's "Meet the
182Lockers" LWN article [NeilBrown2011MeetTheLockers].
183
Paul E. McKenney4c540052010-01-14 16:10:57 -0800184
Linus Torvalds1da177e2005-04-16 15:20:36 -0700185Bibtex Entries
186
187@article{Kung80
188,author="H. T. Kung and Q. Lehman"
189,title="Concurrent Maintenance of Binary Search Trees"
190,Year="1980"
191,Month="September"
192,journal="ACM Transactions on Database Systems"
193,volume="5"
194,number="3"
195,pages="354-382"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800196,note="Available:
197\url{http://portal.acm.org/citation.cfm?id=320619&dl=GUIDE,}
198[Viewed December 3, 2007]"
199,annotation={
200 Use garbage collector to clean up data after everyone is done with it.
201 .
202 Oldest use of something vaguely resembling RCU that I have found.
203}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700204}
205
206@techreport{Manber82
207,author="Udi Manber and Richard E. Ladner"
208,title="Concurrency Control in a Dynamic Search Structure"
209,institution="Department of Computer Science, University of Washington"
210,address="Seattle, Washington"
211,year="1982"
212,number="82-01-01"
213,month="January"
214,pages="28"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800215,annotation={
216 .
217 Superseded by Manber84.
218 .
219 Describes concurrent AVL tree implementation. Uses a
220 garbage-collection mechanism to handle concurrent use and deletion
221 of nodes in the tree, but lacks the summary-of-execution-history
222 concept of read-copy locking.
223 .
224 Keeps full list of processes that were active when a given
225 node was to be deleted, and waits until all such processes have
226 -terminated- before allowing this node to be reused. This is
227 not described in great detail -- one could imagine using process
228 IDs for this if the ID space was large enough that overlapping
229 never occurred.
230 .
231 This restriction makes this algorithm unsuitable for use in
232 systems comprised of long-lived processes. It also produces
233 completely unacceptable overhead in systems with large numbers
234 of processes. Finally, it is specific to AVL trees.
235 .
236 Cites Kung80, so not an independent invention, but the first
237 RCU-like usage that does not rely on an automatic garbage
238 collector.
239}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700240}
241
242@article{Manber84
243,author="Udi Manber and Richard E. Ladner"
244,title="Concurrency Control in a Dynamic Search Structure"
245,Year="1984"
246,Month="September"
247,journal="ACM Transactions on Database Systems"
248,volume="9"
249,number="3"
250,pages="439-455"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800251,annotation={
252 Describes concurrent AVL tree implementation. Uses a
253 garbage-collection mechanism to handle concurrent use and deletion
254 of nodes in the tree, but lacks the summary-of-execution-history
255 concept of read-copy locking.
256 .
257 Keeps full list of processes that were active when a given
258 node was to be deleted, and waits until all such processes have
259 -terminated- before allowing this node to be reused. This is
260 not described in great detail -- one could imagine using process
261 IDs for this if the ID space was large enough that overlapping
262 never occurred.
263 .
264 This restriction makes this algorithm unsuitable for use in
265 systems comprised of long-lived processes. It also produces
266 completely unacceptable overhead in systems with large numbers
267 of processes. Finally, it is specific to AVL trees.
268}
269}
270
271@Conference{RichardRashid87a
272,Author="Richard Rashid and Avadis Tevanian and Michael Young and
273David Golub and Robert Baron and David Black and William Bolosky and
274Jonathan Chew"
275,Title="Machine-Independent Virtual Memory Management for Paged
276Uniprocessor and Multiprocessor Architectures"
277,Booktitle="{2\textsuperscript{nd} Symposium on Architectural Support
278for Programming Languages and Operating Systems}"
279,Publisher="Association for Computing Machinery"
280,Month="October"
281,Year="1987"
282,pages="31-39"
283,Address="Palo Alto, CA"
284,note="Available:
285\url{http://www.cse.ucsc.edu/~randal/221/rashid-machvm.pdf}
286[Viewed February 17, 2005]"
287,annotation={
288 Describes lazy TLB flush, where one waits for each CPU to pass
289 through a scheduling-clock interrupt before reusing a given range
290 of virtual address. Does not describe how one determines that
291 all CPUs have in fact taken such an interrupt, though there are
292 no shortage of straightforward methods for accomplishing this.
293 .
294 Note that it does not make sense to just wait a fixed amount of
295 time, since a given CPU might have interrupts disabled for an
296 extended amount of time.
297}
298}
299
300@article{BarbaraLiskov1988ArgusCACM
301,author = {Barbara Liskov}
302,title = {Distributed programming in {Argus}}
303,journal = {Commun. ACM}
304,volume = {31}
305,number = {3}
306,year = {1988}
307,issn = {0001-0782}
308,pages = {300--312}
309,doi = {http://doi.acm.org/10.1145/42392.42399}
310,publisher = {ACM}
311,address = {New York, NY, USA}
312,annotation= {
313 At the top of page 307: "Conflicts with deposits and withdrawals
314 are necessary if the reported total is to be up to date. They
315 could be avoided by having total return a sum that is slightly
316 out of date." Relies on semantics -- approximate numerical
317 values sometimes OK.
318}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700319}
320
321@techreport{Hennessy89
322,author="James P. Hennessy and Damian L. Osisek and Joseph W. {Seigh II}"
323,title="Passive Serialization in a Multitasking Environment"
324,institution="US Patent and Trademark Office"
325,address="Washington, DC"
326,year="1989"
327,number="US Patent 4,809,168 (lapsed)"
328,month="February"
329,pages="11"
330}
331
332@techreport{Pugh90
333,author="William Pugh"
334,title="Concurrent Maintenance of Skip Lists"
335,institution="Institute of Advanced Computer Science Studies, Department of Computer Science, University of Maryland"
336,address="College Park, Maryland"
337,year="1990"
338,number="CS-TR-2222.1"
339,month="June"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800340,annotation={
341 Concurrent access to skip lists. Has both weak and strong search.
342 Uses concept of ``garbage queue'', but has no real way of cleaning
343 the garbage efficiently.
344 .
345 Appears to be an independent invention of an RCU-like mechanism.
346}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700347}
348
349@Book{Adams91
350,Author="Gregory R. Adams"
351,title="Concurrent Programming, Principles, and Practices"
352,Publisher="Benjamin Cummins"
353,Year="1991"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800354,annotation={
355 Has a few paragraphs describing ``chaotic relaxation'', a
356 numerical analysis technique that allows multiprocessors to
357 avoid synchronization overhead by using possibly-stale data.
358 .
359 Seems like this is descended from yet another independent
360 invention of RCU-like function -- but this is restricted
361 in that reclamation is not necessary.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700362}
Paul E. McKenney32300752008-05-12 21:21:05 +0200363}
364
Linus Torvalds1da177e2005-04-16 15:20:36 -0700365@unpublished{Jacobson93
366,author="Van Jacobson"
367,title="Avoid Read-Side Locking Via Delayed Free"
368,year="1993"
369,month="September"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800370,note="private communication"
371,annotation={
372 Use fixed time delay to approximate grace period. Very simple,
373 but subject to random memory corruption under heavy load.
374 .
375 Independent invention of RCU-like mechanism.
376}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700377}
378
379@Conference{AjuJohn95
380,Author="Aju John"
381,Title="Dynamic vnodes -- Design and Implementation"
382,Booktitle="{USENIX Winter 1995}"
383,Publisher="USENIX Association"
384,Month="January"
385,Year="1995"
386,pages="11-23"
387,Address="New Orleans, LA"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800388,note="Available:
389\url{https://www.usenix.org/publications/library/proceedings/neworl/full_papers/john.a}
390[Viewed October 1, 2010]"
391,annotation={
392 Age vnodes out of the cache, and have a fixed time set by a kernel
393 parameter. Not clear that all races were in fact correctly handled.
394 Used a 20-minute time by default, which would most definitely not
395 be suitable during DoS attacks or virus scans.
396 .
397 Apparently independent invention of RCU-like mechanism.
398}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700399}
400
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +0100401@conference{Pu95a,
402Author = "Calton Pu and Tito Autrey and Andrew Black and Charles Consel and
403Crispin Cowan and Jon Inouye and Lakshmi Kethana and Jonathan Walpole and
404Ke Zhang",
405Title = "Optimistic Incremental Specialization: Streamlining a Commercial
406Operating System",
407Booktitle = "15\textsuperscript{th} ACM Symposium on
408Operating Systems Principles (SOSP'95)",
409address = "Copper Mountain, CO",
410month="December",
411year="1995",
412pages="314-321",
413annotation="
414 Uses a replugger, but with a flag to signal when people are
415 using the resource at hand. Only one reader at a time.
416"
417}
418
419@conference{Cowan96a,
420Author = "Crispin Cowan and Tito Autrey and Charles Krasic and
421Calton Pu and Jonathan Walpole",
422Title = "Fast Concurrent Dynamic Linking for an Adaptive Operating System",
423Booktitle = "International Conference on Configurable Distributed Systems
424(ICCDS'96)",
425address = "Annapolis, MD",
426month="May",
427year="1996",
428pages="108",
429isbn="0-8186-7395-8",
430annotation="
431 Uses a replugger, but with a counter to signal when people are
432 using the resource at hand. Allows multiple readers.
433"
434}
435
Linus Torvalds1da177e2005-04-16 15:20:36 -0700436@techreport{Slingwine95
437,author="John D. Slingwine and Paul E. McKenney"
438,title="Apparatus and Method for Achieving Reduced Overhead Mutual
439Exclusion and Maintaining Coherency in a Multiprocessor System
440Utilizing Execution History and Thread Monitoring"
441,institution="US Patent and Trademark Office"
442,address="Washington, DC"
443,year="1995"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800444,number="US Patent 5,442,758"
Linus Torvalds1da177e2005-04-16 15:20:36 -0700445,month="August"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800446,annotation={
447 Describes the parallel RCU infrastructure. Includes NUMA aspect
448 (structure of bitmap can reflect bus structure of computer system).
449 .
450 Another independent invention of an RCU-like mechanism, but the
451 "real" RCU this time!
452}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700453}
454
455@techreport{Slingwine97
456,author="John D. Slingwine and Paul E. McKenney"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800457,title="Method for Maintaining Data Coherency Using Thread Activity
458Summaries in a Multicomputer System"
Linus Torvalds1da177e2005-04-16 15:20:36 -0700459,institution="US Patent and Trademark Office"
460,address="Washington, DC"
461,year="1997"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800462,number="US Patent 5,608,893"
Linus Torvalds1da177e2005-04-16 15:20:36 -0700463,month="March"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800464,pages="19"
465,annotation={
466 Describes use of RCU to synchronize data between a pair of
467 SMP/NUMA computer systems.
468}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700469}
470
471@techreport{Slingwine98
472,author="John D. Slingwine and Paul E. McKenney"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800473,title="Apparatus and Method for Achieving Reduced Overhead Mutual
474Exclusion and Maintaining Coherency in a Multiprocessor System
475Utilizing Execution History and Thread Monitoring"
Linus Torvalds1da177e2005-04-16 15:20:36 -0700476,institution="US Patent and Trademark Office"
477,address="Washington, DC"
478,year="1998"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800479,number="US Patent 5,727,209"
Linus Torvalds1da177e2005-04-16 15:20:36 -0700480,month="March"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800481,annotation={
482 Describes doing an atomic update by copying the data item and
483 then substituting it into the data structure.
484}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700485}
486
487@Conference{McKenney98
488,Author="Paul E. McKenney and John D. Slingwine"
489,Title="Read-Copy Update: Using Execution History to Solve Concurrency
490Problems"
491,Booktitle="{Parallel and Distributed Computing and Systems}"
492,Month="October"
493,Year="1998"
494,pages="509-518"
495,Address="Las Vegas, NV"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800496,note="Available:
497\url{http://www.rdrop.com/users/paulmck/RCU/rclockpdcsproof.pdf}
498[Viewed December 3, 2007]"
499,annotation={
500 Describes and analyzes RCU mechanism in DYNIX/ptx. Describes
501 application to linked list update and log-buffer flushing.
502 Defines 'quiescent state'. Includes both measured and analytic
503 evaluation.
504}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700505}
506
507@Conference{Gamsa99
508,Author="Ben Gamsa and Orran Krieger and Jonathan Appavoo and Michael Stumm"
509,Title="Tornado: Maximizing Locality and Concurrency in a Shared Memory
510Multiprocessor Operating System"
511,Booktitle="{Proceedings of the 3\textsuperscript{rd} Symposium on
512Operating System Design and Implementation}"
513,Month="February"
514,Year="1999"
515,pages="87-100"
516,Address="New Orleans, LA"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800517,note="Available:
518\url{http://www.usenix.org/events/osdi99/full_papers/gamsa/gamsa.pdf}
519[Viewed August 30, 2006]"
520,annotation={
521 Use of RCU-like facility in K42/Tornado. Another independent
522 invention of RCU.
523 See especially pages 7-9 (Section 5).
524}
525}
526
527@unpublished{RustyRussell2000a
528,Author="Rusty Russell"
529,Title="Re: modular net drivers"
530,month="June"
531,year="2000"
532,day="23"
533,note="Available:
534\url{http://oss.sgi.com/projects/netdev/archive/2000-06/msg00250.html}
535[Viewed April 10, 2006]"
536,annotation={
537 Proto-RCU proposal from Phil Rumpf and Rusty Russell.
538 Yet another independent invention of RCU.
539 Outline of algorithm to unload modules...
540 .
541 Appeared on net-dev mailing list.
542}
543}
544
545@unpublished{RustyRussell2000b
546,Author="Rusty Russell"
547,Title="Re: modular net drivers"
548,month="June"
549,year="2000"
550,day="24"
551,note="Available:
552\url{http://oss.sgi.com/projects/netdev/archive/2000-06/msg00254.html}
553[Viewed April 10, 2006]"
554,annotation={
555 Proto-RCU proposal from Phil Rumpf and Rusty Russell.
556 .
557 Appeared on net-dev mailing list.
558}
559}
560
561@unpublished{McKenney01b
562,Author="Paul E. McKenney and Dipankar Sarma"
563,Title="Read-Copy Update Mutual Exclusion in {Linux}"
564,month="February"
565,year="2001"
566,note="Available:
567\url{http://lse.sourceforge.net/locking/rcu/rcupdate_doc.html}
568[Viewed October 18, 2004]"
569,annotation={
570 Prototypical Linux documentation for RCU.
571}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700572}
573
574@techreport{Slingwine01
575,author="John D. Slingwine and Paul E. McKenney"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800576,title="Apparatus and Method for Achieving Reduced Overhead Mutual
577Exclusion and Maintaining Coherency in a Multiprocessor System
578Utilizing Execution History and Thread Monitoring"
Linus Torvalds1da177e2005-04-16 15:20:36 -0700579,institution="US Patent and Trademark Office"
580,address="Washington, DC"
581,year="2001"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800582,number="US Patent 6,219,690"
Linus Torvalds1da177e2005-04-16 15:20:36 -0700583,month="April"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800584,annotation={
585 'Change in mode' aspect of RCU. Can be thought of as a lazy barrier.
586}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700587}
588
589@Conference{McKenney01a
590,Author="Paul E. McKenney and Jonathan Appavoo and Andi Kleen and
591Orran Krieger and Rusty Russell and Dipankar Sarma and Maneesh Soni"
592,Title="Read-Copy Update"
593,Booktitle="{Ottawa Linux Symposium}"
594,Month="July"
595,Year="2001"
596,note="Available:
597\url{http://www.linuxsymposium.org/2001/abstracts/readcopy.php}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800598\url{http://www.rdrop.com/users/paulmck/RCU/rclock_OLS.2001.05.01c.pdf}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700599[Viewed June 23, 2004]"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800600,annotation={
601 Described RCU, and presented some patches implementing and using
602 it in the Linux kernel.
603}
604}
605
606@unpublished{McKenney01f
607,Author="Paul E. McKenney"
608,Title="{RFC:} patch to allow lock-free traversal of lists with insertion"
609,month="October"
610,year="2001"
611,note="Available:
612\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=100259266316456&w=2}
613[Viewed June 23, 2004]"
614,annotation="
615 Memory-barrier and Alpha thread. 100 messages, not too bad...
Linus Torvalds1da177e2005-04-16 15:20:36 -0700616"
617}
618
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800619@unpublished{Spraul01
620,Author="Manfred Spraul"
621,Title="Re: {RFC:} patch to allow lock-free traversal of lists with insertion"
622,month="October"
623,year="2001"
624,note="Available:
625\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=100264675012867&w=2}
626[Viewed June 23, 2004]"
627,annotation="
628 Suggested burying memory barriers in Linux's list-manipulation
629 primitives.
630"
631}
632
633@unpublished{LinusTorvalds2001a
634,Author="Linus Torvalds"
635,Title="{Re:} {[Lse-tech]} {Re:} {RFC:} patch to allow lock-free traversal of lists with insertion"
636,month="October"
637,year="2001"
638,note="Available:
639\url{http://lkml.org/lkml/2001/10/13/105}
640[Viewed August 21, 2004]"
641}
642
643@unpublished{Blanchard02a
644,Author="Anton Blanchard"
645,Title="some RCU dcache and ratcache results"
646,month="March"
647,year="2002"
648,note="Available:
649\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=101637107412972&w=2}
650[Viewed October 18, 2004]"
651}
652
Linus Torvalds1da177e2005-04-16 15:20:36 -0700653@Conference{Linder02a
654,Author="Hanna Linder and Dipankar Sarma and Maneesh Soni"
655,Title="Scalability of the Directory Entry Cache"
656,Booktitle="{Ottawa Linux Symposium}"
657,Month="June"
658,Year="2002"
659,pages="289-300"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800660,annotation="
661 Measured scalability of Linux 2.4 kernel's directory-entry cache
662 (dcache), and measured some scalability enhancements.
663"
Linus Torvalds1da177e2005-04-16 15:20:36 -0700664}
665
666@Conference{McKenney02a
667,Author="Paul E. McKenney and Dipankar Sarma and
668Andrea Arcangeli and Andi Kleen and Orran Krieger and Rusty Russell"
669,Title="Read-Copy Update"
670,Booktitle="{Ottawa Linux Symposium}"
671,Month="June"
672,Year="2002"
673,pages="338-367"
674,note="Available:
675\url{http://www.linux.org.uk/~ajh/ols2002_proceedings.pdf.gz}
676[Viewed June 23, 2004]"
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +0100677,annotation="
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800678 Presented and compared a number of RCU implementations for the
679 Linux kernel.
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +0100680"
681}
682
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800683@unpublished{Sarma02a
684,Author="Dipankar Sarma"
685,Title="specweb99: dcache scalability results"
686,month="July"
687,year="2002"
688,note="Available:
689\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=102645767914212&w=2}
690[Viewed June 23, 2004]"
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +0100691,annotation="
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800692 Compare fastwalk and RCU for dcache. RCU won.
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +0100693"
694}
695
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800696@unpublished{Barbieri02
697,Author="Luca Barbieri"
698,Title="Re: {[PATCH]} Initial support for struct {vfs\_cred}"
699,month="August"
700,year="2002"
701,note="Available:
702\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=103082050621241&w=2}
703[Viewed: June 23, 2004]"
704,annotation="
705 Suggested RCU for vfs\_shared\_cred.
706"
707}
708
709@unpublished{Dickins02a
710,author="Hugh Dickins"
711,title="Use RCU for System-V IPC"
712,year="2002"
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +0100713,month="October"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800714,note="private communication"
715}
716
717@unpublished{Sarma02b
718,Author="Dipankar Sarma"
719,Title="Some dcache\_rcu benchmark numbers"
720,month="October"
721,year="2002"
722,note="Available:
723\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=103462075416638&w=2}
724[Viewed June 23, 2004]"
725,annotation="
726 Performance of dcache RCU on kernbench for 16x NUMA-Q and 1x,
727 2x, and 4x systems. RCU does no harm, and helps on 16x.
728"
729}
730
731@unpublished{LinusTorvalds2003a
732,Author="Linus Torvalds"
733,Title="Re: {[PATCH]} small fixes in brlock.h"
734,month="March"
735,year="2003"
736,note="Available:
737\url{http://lkml.org/lkml/2003/3/9/205}
738[Viewed March 13, 2006]"
739,annotation="
740 Linus suggests replacing brlock with RCU and/or seqlocks:
741 .
742 'It's entirely possible that the current user could be replaced
743 by RCU and/or seqlocks, and we could get rid of brlocks entirely.'
744 .
745 Steve Hemminger responds by replacing them with RCU.
746"
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +0100747}
748
Linus Torvalds1da177e2005-04-16 15:20:36 -0700749@article{Appavoo03a
750,author="J. Appavoo and K. Hui and C. A. N. Soules and R. W. Wisniewski and
751D. M. {Da Silva} and O. Krieger and M. A. Auslander and D. J. Edelsohn and
752B. Gamsa and G. R. Ganger and P. McKenney and M. Ostrowski and
753B. Rosenburg and M. Stumm and J. Xenidis"
754,title="Enabling Autonomic Behavior in Systems Software With Hot Swapping"
755,Year="2003"
756,Month="January"
757,journal="IBM Systems Journal"
758,volume="42"
759,number="1"
760,pages="60-76"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800761,annotation="
762 Use of RCU to enable hot-swapping for autonomic behavior in K42.
763"
764}
765
766@unpublished{Seigh03
767,author="Joseph W. {Seigh II}"
768,title="Read Copy Update"
769,Year="2003"
770,Month="March"
771,note="email correspondence"
772,annotation="
773 Described the relationship of the VM/XA passive serialization to RCU.
774"
Linus Torvalds1da177e2005-04-16 15:20:36 -0700775}
776
777@Conference{Arcangeli03
778,Author="Andrea Arcangeli and Mingming Cao and Paul E. McKenney and
779Dipankar Sarma"
780,Title="Using Read-Copy Update Techniques for {System V IPC} in the
781{Linux} 2.5 Kernel"
782,Booktitle="Proceedings of the 2003 USENIX Annual Technical Conference
783(FREENIX Track)"
784,Publisher="USENIX Association"
785,year="2003"
786,month="June"
787,pages="297-310"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800788,note="Available:
789\url{http://www.rdrop.com/users/paulmck/RCU/rcu.FREENIX.2003.06.14.pdf}
790[Viewed November 21, 2007]"
791,annotation="
792 Compared updated RCU implementations for the Linux kernel, and
793 described System V IPC use of RCU, including order-of-magnitude
794 performance improvements.
795"
796}
797
798@Conference{Soules03a
799,Author="Craig A. N. Soules and Jonathan Appavoo and Kevin Hui and
800Dilma {Da Silva} and Gregory R. Ganger and Orran Krieger and
801Michael Stumm and Robert W. Wisniewski and Marc Auslander and
802Michal Ostrowski and Bryan Rosenburg and Jimi Xenidis"
803,Title="System Support for Online Reconfiguration"
804,Booktitle="Proceedings of the 2003 USENIX Annual Technical Conference"
805,Publisher="USENIX Association"
806,year="2003"
807,month="June"
808,pages="141-154"
Linus Torvalds1da177e2005-04-16 15:20:36 -0700809}
810
811@article{McKenney03a
812,author="Paul E. McKenney"
813,title="Using {RCU} in the {Linux} 2.5 Kernel"
814,Year="2003"
815,Month="October"
816,journal="Linux Journal"
817,volume="1"
818,number="114"
819,pages="18-26"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800820,note="Available:
821\url{http://www.linuxjournal.com/article/6993}
822[Viewed November 14, 2007]"
823,annotation="
824 Reader-friendly intro to RCU, with the infamous old-man-and-brat
825 cartoon.
826"
827}
828
829@unpublished{Sarma03a
830,Author="Dipankar Sarma"
831,Title="RCU low latency patches"
832,month="December"
833,year="2003"
834,note="Message ID: 20031222180114.GA2248@in.ibm.com"
835,annotation="dipankar/ct.2004.03.27/RCUll.2003.12.22.patch"
Linus Torvalds1da177e2005-04-16 15:20:36 -0700836}
837
Paul E. McKenneya83f1fe2005-05-01 08:59:05 -0700838@techreport{Friedberg03a
839,author="Stuart A. Friedberg"
840,title="Lock-Free Wild Card Search Data Structure and Method"
841,institution="US Patent and Trademark Office"
842,address="Washington, DC"
843,year="2003"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800844,number="US Patent 6,662,184"
Paul E. McKenneya83f1fe2005-05-01 08:59:05 -0700845,month="December"
846,pages="112"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800847,annotation="
848 Applies RCU to a wildcard-search Patricia tree in order to permit
849 synchronization-free lookup. RCU is used to retain removed nodes
850 for a grace period before freeing them.
851"
Paul E. McKenneya83f1fe2005-05-01 08:59:05 -0700852}
853
Linus Torvalds1da177e2005-04-16 15:20:36 -0700854@article{McKenney04a
855,author="Paul E. McKenney and Dipankar Sarma and Maneesh Soni"
856,title="Scaling dcache with {RCU}"
857,Year="2004"
858,Month="January"
859,journal="Linux Journal"
860,volume="1"
861,number="118"
862,pages="38-46"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800863,note="Available:
864\url{http://www.linuxjournal.com/node/7124}
865[Viewed December 26, 2010]"
866,annotation="
867 Reader friendly intro to dcache and RCU.
868"
Linus Torvalds1da177e2005-04-16 15:20:36 -0700869}
870
871@Conference{McKenney04b
872,Author="Paul E. McKenney"
873,Title="{RCU} vs. Locking Performance on Different {CPUs}"
874,Booktitle="{linux.conf.au}"
875,Month="January"
876,Year="2004"
877,Address="Adelaide, Australia"
878,note="Available:
879\url{http://www.linux.org.au/conf/2004/abstracts.html#90}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800880\url{http://www.rdrop.com/users/paulmck/RCU/lockperf.2004.01.17a.pdf}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700881[Viewed June 23, 2004]"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800882,annotation="
883 Compares performance of RCU to that of other locking primitives
884 over a number of CPUs (x86, Opteron, Itanium, and PPC).
885"
886}
887
888@unpublished{Sarma04a
889,Author="Dipankar Sarma"
890,Title="{[PATCH]} {RCU} for low latency (experimental)"
891,month="March"
892,year="2004"
893,note="\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=108003746402892&w=2}"
894,annotation="Head of thread: dipankar/2004.03.23/rcu-low-lat.1.patch"
895}
896
897@unpublished{Sarma04b
898,Author="Dipankar Sarma"
899,Title="Re: {[PATCH]} {RCU} for low latency (experimental)"
900,month="March"
901,year="2004"
902,note="\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=108016474829546&w=2}"
903,annotation="dipankar/rcuth.2004.03.24/rcu-throttle.patch"
904}
905
906@unpublished{Spraul04a
907,Author="Manfred Spraul"
908,Title="[RFC] 0/5 rcu lock update"
909,month="May"
910,year="2004"
911,note="Available:
912\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=108546407726602&w=2}
913[Viewed June 23, 2004]"
914,annotation="
915 Hierarchical-bitmap patch for RCU infrastructure.
916"
917}
918
919@unpublished{Steiner04a
920,Author="Jack Steiner"
921,Title="Re: [Lse-tech] [RFC, PATCH] 1/5 rcu lock update:
922Add per-cpu batch counter"
923,month="May"
924,year="2004"
925,note="Available:
926\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=108551764515332&w=2}
927[Viewed June 23, 2004]"
928,annotation={
929 RCU runs reasonably on a 512-CPU SGI using Manfred Spraul's patches,
930 which may be found at:
931 https://lkml.org/lkml/2004/5/20/49 (split vars into cachelines)
932 https://lkml.org/lkml/2004/5/22/114 (cpu_quiet() patch)
933 https://lkml.org/lkml/2004/5/25/24 (0/5)
934 https://lkml.org/lkml/2004/5/25/23 (1/5)
935 https://lkml.org/lkml/2004/5/25/265 (works for Jack)
936 https://lkml.org/lkml/2004/5/25/20 (2/5)
937 https://lkml.org/lkml/2004/5/25/22 (3/5)
938 https://lkml.org/lkml/2004/5/25/19 (4/5)
939 https://lkml.org/lkml/2004/5/25/21 (5/5)
940}
941}
942
943@Conference{Sarma04c
944,Author="Dipankar Sarma and Paul E. McKenney"
945,Title="Making {RCU} Safe for Deep Sub-Millisecond Response
946Realtime Applications"
947,Booktitle="Proceedings of the 2004 USENIX Annual Technical Conference
948(FREENIX Track)"
949,Publisher="USENIX Association"
950,year="2004"
951,month="June"
952,pages="182-191"
953,annotation="
954 Describes and compares a number of modifications to the Linux RCU
955 implementation that make it friendly to realtime applications.
956"
Linus Torvalds1da177e2005-04-16 15:20:36 -0700957}
958
959@phdthesis{PaulEdwardMcKenneyPhD
960,author="Paul E. McKenney"
961,title="Exploiting Deferred Destruction:
962An Analysis of Read-Copy-Update Techniques
963in Operating System Kernels"
964,school="OGI School of Science and Engineering at
965Oregon Health and Sciences University"
966,year="2004"
Paul E. McKenneya83f1fe2005-05-01 08:59:05 -0700967,note="Available:
968\url{http://www.rdrop.com/users/paulmck/RCU/RCUdissertation.2004.07.14e1.pdf}
969[Viewed October 15, 2004]"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800970,annotation="
971 Describes RCU implementations and presents design patterns
972 corresponding to common uses of RCU in several operating-system
973 kernels.
974"
Linus Torvalds1da177e2005-04-16 15:20:36 -0700975}
976
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800977@unpublished{PaulEMcKenney2004rcu:dereference
978,Author="Dipankar Sarma"
979,Title="{Re: RCU : Abstracted RCU dereferencing [5/5]}"
980,month="August"
Linus Torvalds1da177e2005-04-16 15:20:36 -0700981,year="2004"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800982,note="Available:
983\url{http://lkml.org/lkml/2004/8/6/237}
984[Viewed June 8, 2010]"
985,annotation="
986 Introduce rcu_dereference().
987"
988}
989
990@unpublished{JimHouston04a
991,Author="Jim Houston"
992,Title="{[RFC\&PATCH] Alternative {RCU} implementation}"
993,month="August"
994,year="2004"
995,note="Available:
996\url{http://lkml.org/lkml/2004/8/30/87}
997[Viewed February 17, 2005]"
998,annotation="
999 Uses active code in rcu_read_lock() and rcu_read_unlock() to
1000 make RCU happen, allowing RCU to function on CPUs that do not
1001 receive a scheduling-clock interrupt.
1002"
1003}
1004
1005@unpublished{TomHart04a
1006,Author="Thomas E. Hart"
1007,Title="Master's Thesis: Applying Lock-free Techniques to the {Linux} Kernel"
1008,month="October"
1009,year="2004"
1010,note="Available:
1011\url{http://www.cs.toronto.edu/~tomhart/masters_thesis.html}
1012[Viewed October 15, 2004]"
1013,annotation="
1014 Proposes comparing RCU to lock-free methods for the Linux kernel.
1015"
1016}
1017
1018@unpublished{Vaddagiri04a
1019,Author="Srivatsa Vaddagiri"
1020,Title="Subject: [RFC] Use RCU for tcp\_ehash lookup"
1021,month="October"
1022,year="2004"
1023,note="Available:
1024\url{http://marc.theaimsgroup.com/?t=109395731700004&r=1&w=2}
1025[Viewed October 18, 2004]"
1026,annotation="
1027 Srivatsa's RCU patch for tcp_ehash lookup.
1028"
1029}
1030
1031@unpublished{Thirumalai04a
1032,Author="Ravikiran Thirumalai"
1033,Title="Subject: [patchset] Lockfree fd lookup 0 of 5"
1034,month="October"
1035,year="2004"
1036,note="Available:
1037\url{http://marc.theaimsgroup.com/?t=109144217400003&r=1&w=2}
1038[Viewed October 18, 2004]"
1039,annotation="
1040 Ravikiran's lockfree FD patch.
1041"
1042}
1043
1044@unpublished{Thirumalai04b
1045,Author="Ravikiran Thirumalai"
1046,Title="Subject: Re: [patchset] Lockfree fd lookup 0 of 5"
1047,month="October"
1048,year="2004"
1049,note="Available:
1050\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=109152521410459&w=2}
1051[Viewed October 18, 2004]"
1052,annotation="
1053 Ravikiran's lockfree FD patch.
1054"
1055}
1056
1057@unpublished{PaulEMcKenney2004rcu:assign:pointer
1058,Author="Paul E. McKenney"
1059,Title="{[PATCH 1/3] RCU: \url{rcu_assign_pointer()} removal of memory barriers}"
1060,month="October"
1061,year="2004"
1062,note="Available:
1063\url{http://lkml.org/lkml/2004/10/23/241}
1064[Viewed June 8, 2010]"
1065,annotation="
1066 Introduce rcu_assign_pointer().
1067"
1068}
1069
1070@unpublished{JamesMorris04a
1071,Author="James Morris"
1072,Title="{[PATCH 2/3] SELinux} scalability - convert {AVC} to {RCU}"
1073,day="15"
1074,month="November"
1075,year="2004"
1076,note="Available:
1077\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=110054979416004&w=2}
1078[Viewed December 10, 2004]"
1079,annotation="
1080 James Morris posts Kaigai Kohei's patch to LKML.
1081"
Linus Torvalds1da177e2005-04-16 15:20:36 -07001082}
Paul E. McKenneya83f1fe2005-05-01 08:59:05 -07001083
1084@unpublished{JamesMorris04b
1085,Author="James Morris"
1086,Title="Recent Developments in {SELinux} Kernel Performance"
1087,month="December"
1088,year="2004"
1089,note="Available:
1090\url{http://www.livejournal.com/users/james_morris/2153.html}
1091[Viewed December 10, 2004]"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001092,annotation="
1093 RCU helps SELinux performance. ;-) Made LWN.
1094"
1095}
1096
1097@unpublished{PaulMcKenney2005RCUSemantics
1098,Author="Paul E. McKenney and Jonathan Walpole"
1099,Title="{RCU} Semantics: A First Attempt"
1100,month="January"
1101,year="2005"
1102,day="30"
1103,note="Available:
1104\url{http://www.rdrop.com/users/paulmck/RCU/rcu-semantics.2005.01.30a.pdf}
1105[Viewed December 6, 2009]"
1106,annotation="
1107 Early derivation of RCU semantics.
1108"
1109}
1110
1111@unpublished{PaulMcKenney2005e
1112,Author="Paul E. McKenney"
1113,Title="Real-Time Preemption and {RCU}"
1114,month="March"
1115,year="2005"
1116,day="17"
1117,note="Available:
1118\url{http://lkml.org/lkml/2005/3/17/199}
1119[Viewed September 5, 2005]"
1120,annotation="
1121 First posting showing how RCU can be safely adapted for
1122 preemptable RCU read side critical sections.
1123"
1124}
1125
1126@unpublished{EsbenNeilsen2005a
1127,Author="Esben Neilsen"
1128,Title="Re: Real-Time Preemption and {RCU}"
1129,month="March"
1130,year="2005"
1131,day="18"
1132,note="Available:
1133\url{http://lkml.org/lkml/2005/3/18/122}
1134[Viewed March 30, 2006]"
1135,annotation="
1136 Esben Neilsen suggests read-side suppression of grace-period
1137 processing for crude-but-workable realtime RCU. The downside
1138 is indefinite grace periods...But this is OK for experimentation
1139 and testing.
1140"
1141}
1142
1143@unpublished{TomHart05a
1144,Author="Thomas E. Hart and Paul E. McKenney and Angela Demke Brown"
1145,Title="Efficient Memory Reclamation is Necessary for Fast Lock-Free
1146Data Structures"
1147,month="March"
1148,year="2005"
1149,note="Available:
1150\url{ftp://ftp.cs.toronto.edu/csrg-technical-reports/515/}
1151[Viewed March 4, 2005]"
1152,annotation="
1153 Comparison of RCU, QBSR, and EBSR. RCU wins for read-mostly
1154 workloads. ;-)
1155"
1156}
1157
1158@unpublished{JonCorbet2005DeprecateSyncKernel
1159,Author="Jonathan Corbet"
1160,Title="API change: synchronize_kernel() deprecated"
1161,month="May"
1162,day="3"
1163,year="2005"
1164,note="Available:
1165\url{http://lwn.net/Articles/134484/}
1166[Viewed May 3, 2005]"
1167,annotation="
1168 Jon Corbet describes deprecation of synchronize_kernel()
1169 in favor of synchronize_rcu() and synchronize_sched().
1170"
Paul E. McKenneya83f1fe2005-05-01 08:59:05 -07001171}
Paul E. McKenneydd81eca2005-09-10 00:26:24 -07001172
1173@unpublished{PaulMcKenney05a
1174,Author="Paul E. McKenney"
1175,Title="{[RFC]} {RCU} and {CONFIG\_PREEMPT\_RT} progress"
1176,month="May"
1177,year="2005"
1178,note="Available:
1179\url{http://lkml.org/lkml/2005/5/9/185}
1180[Viewed May 13, 2005]"
1181,annotation="
1182 First publication of working lock-based deferred free patches
1183 for the CONFIG_PREEMPT_RT environment.
1184"
1185}
1186
1187@conference{PaulMcKenney05b
1188,Author="Paul E. McKenney and Dipankar Sarma"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001189,Title="Towards Hard Realtime Response from the {Linux} Kernel on {SMP} Hardware"
Paul E. McKenneydd81eca2005-09-10 00:26:24 -07001190,Booktitle="linux.conf.au 2005"
1191,month="April"
1192,year="2005"
1193,address="Canberra, Australia"
1194,note="Available:
1195\url{http://www.rdrop.com/users/paulmck/RCU/realtimeRCU.2005.04.23a.pdf}
1196[Viewed May 13, 2005]"
1197,annotation="
1198 Realtime turns into making RCU yet more realtime friendly.
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001199 http://lca2005.linux.org.au/Papers/Paul%20McKenney/Towards%20Hard%20Realtime%20Response%20from%20the%20Linux%20Kernel/LKS.2005.04.22a.pdf
1200"
1201}
1202
1203@unpublished{PaulEMcKenneyHomePage
1204,Author="Paul E. McKenney"
1205,Title="{Paul} {E.} {McKenney}"
1206,month="May"
1207,year="2005"
1208,note="Available:
1209\url{http://www.rdrop.com/users/paulmck/}
1210[Viewed May 25, 2005]"
1211,annotation="
1212 Paul McKenney's home page.
1213"
1214}
1215
1216@unpublished{PaulEMcKenneyRCUPage
1217,Author="Paul E. McKenney"
1218,Title="Read-Copy Update {(RCU)}"
1219,month="May"
1220,year="2005"
1221,note="Available:
1222\url{http://www.rdrop.com/users/paulmck/RCU}
1223[Viewed May 25, 2005]"
1224,annotation="
1225 Paul McKenney's RCU page.
1226"
1227}
1228
1229@unpublished{JosephSeigh2005a
1230,Author="Joseph Seigh"
1231,Title="{RCU}+{SMR} (hazard pointers)"
1232,month="July"
1233,year="2005"
1234,note="Personal communication"
1235,annotation="
1236 Joe Seigh announcing his atomic-ptr-plus project.
1237 http://sourceforge.net/projects/atomic-ptr-plus/
1238"
1239}
1240
1241@unpublished{JosephSeigh2005b
1242,Author="Joseph Seigh"
1243,Title="Lock-free synchronization primitives"
1244,month="July"
1245,day="6"
1246,year="2005"
1247,note="Available:
1248\url{http://sourceforge.net/projects/atomic-ptr-plus/}
1249[Viewed August 8, 2005]"
1250,annotation="
1251 Joe Seigh's atomic-ptr-plus project.
1252"
1253}
1254
1255@unpublished{PaulMcKenney2005c
1256,Author="Paul E.McKenney"
1257,Title="{[RFC,PATCH] RCU} and {CONFIG\_PREEMPT\_RT} sane patch"
1258,month="August"
1259,day="1"
1260,year="2005"
1261,note="Available:
1262\url{http://lkml.org/lkml/2005/8/1/155}
1263[Viewed March 14, 2006]"
1264,annotation="
1265 First operating counter-based realtime RCU patch posted to LKML.
1266"
1267}
1268
1269@unpublished{PaulMcKenney2005d
1270,Author="Paul E. McKenney"
1271,Title="Re: [Fwd: Re: [patch] Real-Time Preemption, -RT-2.6.13-rc4-V0.7.52-01]"
1272,month="August"
1273,day="8"
1274,year="2005"
1275,note="Available:
1276\url{http://lkml.org/lkml/2005/8/8/108}
1277[Viewed March 14, 2006]"
1278,annotation="
1279 First operating counter-based realtime RCU patch posted to LKML,
1280 but fixed so that various unusual combinations of configuration
1281 parameters all function properly.
1282"
1283}
1284
1285@unpublished{PaulMcKenney2005rcutorture
1286,Author="Paul E. McKenney"
1287,Title="{[PATCH]} {RCU} torture testing"
1288,month="October"
1289,day="1"
1290,year="2005"
1291,note="Available:
1292\url{http://lkml.org/lkml/2005/10/1/70}
1293[Viewed March 14, 2006]"
1294,annotation="
1295 First rcutorture patch.
Paul E. McKenneydd81eca2005-09-10 00:26:24 -07001296"
1297}
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +01001298
1299@conference{ThomasEHart2006a
1300,Author="Thomas E. Hart and Paul E. McKenney and Angela Demke Brown"
1301,Title="Making Lockless Synchronization Fast: Performance Implications
1302of Memory Reclamation"
1303,Booktitle="20\textsuperscript{th} {IEEE} International Parallel and
1304Distributed Processing Symposium"
1305,month="April"
1306,year="2006"
1307,day="25-29"
1308,address="Rhodes, Greece"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001309,note="Available:
1310\url{http://www.rdrop.com/users/paulmck/RCU/hart_ipdps06.pdf}
1311[Viewed April 28, 2008]"
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +01001312,annotation="
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001313 Compares QSBR, HPBR, EBR, and lock-free reference counting.
1314 http://www.cs.toronto.edu/~tomhart/perflab/ipdps06.tgz
1315"
1316}
1317
1318@unpublished{NickPiggin2006radixtree
1319,Author="Nick Piggin"
1320,Title="[patch 3/3] radix-tree: {RCU} lockless readside"
1321,month="June"
1322,day="20"
1323,year="2006"
1324,note="Available:
1325\url{http://lkml.org/lkml/2006/6/20/238}
1326[Viewed March 25, 2008]"
1327,annotation="
1328 RCU-protected radix tree.
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +01001329"
1330}
1331
1332@Conference{PaulEMcKenney2006b
1333,Author="Paul E. McKenney and Dipankar Sarma and Ingo Molnar and
1334Suparna Bhattacharya"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001335,Title="Extending {RCU} for Realtime and Embedded Workloads"
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +01001336,Booktitle="{Ottawa Linux Symposium}"
1337,Month="July"
1338,Year="2006"
1339,pages="v2 123-138"
1340,note="Available:
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001341\url{http://www.linuxsymposium.org/2006/view_abstract.php?content_key=184}
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +01001342\url{http://www.rdrop.com/users/paulmck/RCU/OLSrtRCU.2006.08.11a.pdf}
1343[Viewed January 1, 2007]"
1344,annotation="
1345 Described how to improve the -rt implementation of realtime RCU.
1346"
1347}
1348
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001349@unpublished{WikipediaRCU
1350,Author="Paul E. McKenney and Chris Purcell and Algae and Ben Schumin and
1351Gaius Cornelius and Qwertyus and Neil Conway and Sbw and Blainster and
1352Canis Rufus and Zoicon5 and Anome and Hal Eisen"
1353,Title="Read-Copy Update"
1354,month="July"
1355,day="8"
1356,year="2006"
1357,note="Available:
1358\url{http://en.wikipedia.org/wiki/Read-copy-update}
1359[Viewed August 21, 2006]"
1360,annotation="
1361 Wikipedia RCU page as of July 8 2006.
1362"
1363}
1364
1365@Conference{NickPiggin2006LocklessPageCache
1366,Author="Nick Piggin"
1367,Title="A Lockless Pagecache in Linux---Introduction, Progress, Performance"
1368,Booktitle="{Ottawa Linux Symposium}"
1369,Month="July"
1370,Year="2006"
1371,pages="v2 249-254"
1372,note="Available:
1373\url{http://www.linuxsymposium.org/2006/view_abstract.php?content_key=184}
1374[Viewed January 11, 2009]"
1375,annotation="
1376 Uses RCU-protected radix tree for a lockless page cache.
1377"
1378}
1379
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +01001380@unpublished{PaulEMcKenney2006c
1381,Author="Paul E. McKenney"
1382,Title="Sleepable {RCU}"
1383,month="October"
1384,day="9"
1385,year="2006"
1386,note="Available:
1387\url{http://lwn.net/Articles/202847/}
1388Revised:
1389\url{http://www.rdrop.com/users/paulmck/RCU/srcu.2007.01.14a.pdf}
1390[Viewed August 21, 2006]"
1391,annotation="
1392 LWN article introducing SRCU.
1393"
1394}
1395
1396@unpublished{RobertOlsson2006a
1397,Author="Robert Olsson and Stefan Nilsson"
1398,Title="{TRASH}: A dynamic {LC}-trie and hash data structure"
1399,month="August"
1400,day="18"
1401,year="2006"
1402,note="Available:
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001403\url{http://www.nada.kth.se/~snilsson/publications/TRASH/trash.pdf}
1404[Viewed March 4, 2011]"
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +01001405,annotation="
1406 RCU-protected dynamic trie-hash combination.
1407"
1408}
1409
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001410@unpublished{ChristophHellwig2006RCU2SRCU
1411,Author="Christoph Hellwig"
1412,Title="Re: {[-mm PATCH 1/4]} {RCU}: split classic rcu"
1413,month="September"
1414,day="28"
1415,year="2006"
1416,note="Available:
1417\url{http://lkml.org/lkml/2006/9/28/160}
1418[Viewed March 27, 2008]"
1419}
1420
1421@unpublished{PaulEMcKenneyRCUusagePage
1422,Author="Paul E. McKenney"
1423,Title="{RCU} {Linux} Usage"
1424,month="October"
1425,year="2006"
1426,note="Available:
1427\url{http://www.rdrop.com/users/paulmck/RCU/linuxusage.html}
1428[Viewed January 14, 2007]"
1429,annotation="
1430 Paul McKenney's RCU page showing graphs plotting Linux-kernel
1431 usage of RCU.
1432"
1433}
1434
1435@unpublished{PaulEMcKenneyRCUusageRawDataPage
1436,Author="Paul E. McKenney"
1437,Title="Read-Copy Update {(RCU)} Usage in {Linux} Kernel"
1438,month="October"
1439,year="2006"
1440,note="Available:
1441\url{http://www.rdrop.com/users/paulmck/RCU/linuxusage/rculocktab.html}
1442[Viewed January 14, 2007]"
1443,annotation="
1444 Paul McKenney's RCU page showing Linux usage of RCU in tabular
1445 form, with links to corresponding cscope databases.
1446"
1447}
1448
1449@unpublished{GauthamShenoy2006RCUrwlock
1450,Author="Gautham R. Shenoy"
1451,Title="[PATCH 4/5] lock\_cpu\_hotplug: Redesign - Lightweight implementation of lock\_cpu\_hotplug"
1452,month="October"
1453,year="2006"
1454,day=26
1455,note="Available:
1456\url{http://lkml.org/lkml/2006/10/26/73}
1457[Viewed January 26, 2009]"
1458,annotation="
1459 RCU-based reader-writer lock that allows readers to proceed with
1460 no memory barriers or atomic instruction in absence of writers.
1461 If writer do show up, readers must of course wait as required by
1462 the semantics of reader-writer locking. This is a recursive
1463 lock.
1464"
1465}
1466
1467@unpublished{JensAxboe2006SlowSRCU
1468,Author="Jens Axboe"
1469,Title="Re: [patch] cpufreq: mark \url{cpufreq_tsc()} as
1470\url{core_initcall_sync}"
1471,month="November"
1472,year="2006"
1473,day=17
1474,note="Available:
1475\url{http://lkml.org/lkml/2006/11/17/56}
1476[Viewed May 28, 2007]"
1477,annotation="
1478 SRCU's grace periods are too slow for Jens, even after a
1479 factor-of-three speedup.
1480 Sped-up version of SRCU at http://lkml.org/lkml/2006/11/17/359.
1481"
1482}
1483
1484@unpublished{OlegNesterov2006QRCU
1485,Author="Oleg Nesterov"
1486,Title="Re: [patch] cpufreq: mark {\tt cpufreq\_tsc()} as
1487{\tt core\_initcall\_sync}"
1488,month="November"
1489,year="2006"
1490,day=19
1491,note="Available:
1492\url{http://lkml.org/lkml/2006/11/19/69}
1493[Viewed May 28, 2007]"
1494,annotation="
1495 First cut of QRCU. Expanded/corrected versions followed.
1496 Used to be OlegNesterov2007QRCU, now time-corrected.
1497"
1498}
1499
1500@unpublished{OlegNesterov2006aQRCU
1501,Author="Oleg Nesterov"
1502,Title="Re: [RFC, PATCH 1/2] qrcu: {"quick"} srcu implementation"
1503,month="November"
1504,year="2006"
1505,day=30
1506,note="Available:
1507\url{http://lkml.org/lkml/2006/11/29/330}
1508[Viewed November 26, 2008]"
1509,annotation="
1510 Expanded/corrected version of QRCU.
1511 Used to be OlegNesterov2007aQRCU, now time-corrected.
1512"
1513}
1514
1515@unpublished{EvgeniyPolyakov2006RCUslowdown
1516,Author="Evgeniy Polyakov"
1517,Title="Badness in postponing work"
1518,month="December"
1519,year="2006"
1520,day=05
1521,note="Available:
1522\url{http://www.ioremap.net/node/41}
1523[Viewed October 28, 2008]"
1524,annotation="
1525 Using RCU as a pure delay leads to a 2.5x slowdown in skbs in
1526 the Linux kernel.
1527"
1528}
1529
1530@inproceedings{ChrisMatthews2006ClusteredObjectsRCU
1531,author = {Matthews, Chris and Coady, Yvonne and Appavoo, Jonathan}
1532,title = {Portability events: a programming model for scalable system infrastructures}
1533,booktitle = {PLOS '06: Proceedings of the 3rd workshop on Programming languages and operating systems}
1534,year = {2006}
1535,isbn = {1-59593-577-0}
1536,pages = {11}
1537,location = {San Jose, California}
1538,doi = {http://doi.acm.org/10.1145/1215995.1216006}
1539,publisher = {ACM}
1540,address = {New York, NY, USA}
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +01001541,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001542 Uses K42's RCU-like functionality to manage clustered-object
1543 lifetimes.
1544}}
1545
1546@article{DilmaDaSilva2006K42
1547,author = {Silva, Dilma Da and Krieger, Orran and Wisniewski, Robert W. and Waterland, Amos and Tam, David and Baumann, Andrew}
1548,title = {K42: an infrastructure for operating system research}
1549,journal = {SIGOPS Oper. Syst. Rev.}
1550,volume = {40}
1551,number = {2}
1552,year = {2006}
1553,issn = {0163-5980}
1554,pages = {34--42}
1555,doi = {http://doi.acm.org/10.1145/1131322.1131333}
1556,publisher = {ACM}
1557,address = {New York, NY, USA}
1558,annotation={
1559 Describes relationship of K42 generations to RCU.
1560}}
1561
1562# CoreyMinyard2007list_splice_rcu
1563@unpublished{CoreyMinyard2007list:splice:rcu
1564,Author="Corey Minyard and Paul E. McKenney"
1565,Title="{[PATCH]} add an {RCU} version of list splicing"
1566,month="January"
1567,year="2007"
1568,day=3
1569,note="Available:
1570\url{http://lkml.org/lkml/2007/1/3/112}
1571[Viewed May 28, 2007]"
1572,annotation="
1573 Patch for list_splice_rcu().
1574"
1575}
1576
1577@unpublished{PaulEMcKenney2007rcubarrier
1578,Author="Paul E. McKenney"
1579,Title="{RCU} and Unloadable Modules"
1580,month="January"
1581,day="14"
1582,year="2007"
1583,note="Available:
1584\url{http://lwn.net/Articles/217484/}
1585[Viewed November 22, 2007]"
1586,annotation="
1587 LWN article introducing the rcu_barrier() primitive.
1588"
1589}
1590
1591@unpublished{PeterZijlstra2007SyncBarrier
1592,Author="Peter Zijlstra and Ingo Molnar"
1593,Title="{[PATCH 3/7]} barrier: a scalable synchonisation barrier"
1594,month="January"
1595,year="2007"
1596,day=28
1597,note="Available:
1598\url{http://lkml.org/lkml/2007/1/28/34}
1599[Viewed March 27, 2008]"
1600,annotation="
1601 RCU-like implementation for frequent updaters and rare readers(!).
1602 Subsumed into QRCU. Maybe...
1603"
1604}
1605
1606@unpublished{PaulEMcKenney2007BoostRCU
1607,Author="Paul E. McKenney"
1608,Title="Priority-Boosting {RCU} Read-Side Critical Sections"
1609,month="February"
1610,day="5"
1611,year="2007"
1612,note="Available:
1613\url{http://lwn.net/Articles/220677/}
1614Revised:
1615\url{http://www.rdrop.com/users/paulmck/RCU/RCUbooststate.2007.04.16a.pdf}
1616[Viewed September 7, 2007]"
1617,annotation="
1618 LWN article introducing RCU priority boosting.
1619"
1620}
1621
1622@unpublished{PaulMcKenney2007QRCUpatch
1623,Author="Paul E. McKenney"
1624,Title="{[PATCH]} {QRCU} with lockless fastpath"
1625,month="February"
1626,year="2007"
1627,day=24
1628,note="Available:
1629\url{http://lkml.org/lkml/2007/2/25/18}
1630[Viewed March 27, 2008]"
1631,annotation="
1632 Patch for QRCU supplying lock-free fast path.
1633"
1634}
1635
1636@article{JonathanAppavoo2007K42RCU
1637,author = {Appavoo, Jonathan and Silva, Dilma Da and Krieger, Orran and Auslander, Marc and Ostrowski, Michal and Rosenburg, Bryan and Waterland, Amos and Wisniewski, Robert W. and Xenidis, Jimi and Stumm, Michael and Soares, Livio}
1638,title = {Experience distributing objects in an SMMP OS}
1639,journal = {ACM Trans. Comput. Syst.}
1640,volume = {25}
1641,number = {3}
1642,year = {2007}
1643,issn = {0734-2071}
1644,pages = {6/1--6/52}
1645,doi = {http://doi.acm.org/10.1145/1275517.1275518}
1646,publisher = {ACM}
1647,address = {New York, NY, USA}
1648,annotation={
1649 Role of RCU in K42.
1650}}
1651
1652@conference{RobertOlsson2007Trash
1653,Author="Robert Olsson and Stefan Nilsson"
1654,Title="{TRASH}: A dynamic {LC}-trie and hash data structure"
1655,booktitle="Workshop on High Performance Switching and Routing (HPSR'07)"
1656,month="May"
1657,year="2007"
1658,note="Available:
1659\url{http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4281239}
1660[Viewed October 1, 2010]"
1661,annotation="
1662 RCU-protected dynamic trie-hash combination.
1663"
1664}
1665
1666@conference{PeterZijlstra2007ConcurrentPagecacheRCU
1667,Author="Peter Zijlstra"
1668,Title="Concurrent Pagecache"
1669,Booktitle="Linux Symposium"
1670,month="June"
1671,year="2007"
1672,address="Ottawa, Canada"
1673,note="Available:
1674\url{http://ols.108.redhat.com/2007/Reprints/zijlstra-Reprint.pdf}
1675[Viewed April 14, 2008]"
1676,annotation="
1677 Page-cache modifications permitting RCU readers and concurrent
1678 updates.
1679"
1680}
1681
1682@unpublished{PaulEMcKenney2007whatisRCU
1683,Author="Paul E. McKenney"
1684,Title="What is {RCU}?"
1685,year="2007"
1686,month="07"
1687,note="Available:
1688\url{http://www.rdrop.com/users/paulmck/RCU/whatisRCU.html}
1689[Viewed July 6, 2007]"
1690,annotation={
1691 Describes RCU in Linux kernel.
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +01001692}
1693}
1694
1695@unpublished{PaulEMcKenney2007QRCUspin
1696,Author="Paul E. McKenney"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001697,Title="Using {Promela} and {Spin} to verify parallel algorithms"
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +01001698,month="August"
1699,day="1"
1700,year="2007"
1701,note="Available:
1702\url{http://lwn.net/Articles/243851/}
1703[Viewed September 8, 2007]"
1704,annotation="
1705 LWN article describing Promela and spin, and also using Oleg
1706 Nesterov's QRCU as an example (with Paul McKenney's fastpath).
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001707 Merged patch at: http://lkml.org/lkml/2007/2/25/18
1708"
1709}
1710
1711@unpublished{PaulEMcKenney2007WG21DDOatomics
1712,Author="Paul E. McKenney and Hans-J. Boehm and Lawrence Crowl"
1713,Title="C++ Data-Dependency Ordering: Atomics and Memory Model"
1714,month="August"
1715,day="3"
1716,year="2007"
1717,note="Preprint:
1718\url{http://open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2664.htm}
1719[Viewed December 7, 2009]"
1720,annotation="
1721 RCU for C++, parts 1 and 2.
1722"
1723}
1724
1725@unpublished{PaulEMcKenney2007WG21DDOannotation
1726,Author="Paul E. McKenney and Lawrence Crowl"
1727,Title="C++ Data-Dependency Ordering: Function Annotation"
1728,month="September"
1729,day="18"
1730,year="2008"
1731,note="Preprint:
1732\url{http://open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2782.htm}
1733[Viewed December 7, 2009]"
1734,annotation="
1735 RCU for C++, part 2, updated many times.
1736"
1737}
1738
1739@unpublished{PaulEMcKenney2007PreemptibleRCUPatch
1740,Author="Paul E. McKenney"
1741,Title="[PATCH RFC 0/9] {RCU}: Preemptible {RCU}"
1742,month="September"
1743,day="10"
1744,year="2007"
1745,note="Available:
1746\url{http://lkml.org/lkml/2007/9/10/213}
1747[Viewed October 25, 2007]"
1748,annotation="
1749 Final patch for preemptable RCU to -rt. (Later patches were
1750 to mainline, eventually incorporated.)
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +01001751"
1752}
1753
Paul E. McKenney32300752008-05-12 21:21:05 +02001754@unpublished{PaulEMcKenney2007PreemptibleRCU
1755,Author="Paul E. McKenney"
1756,Title="The design of preemptible read-copy-update"
1757,month="October"
1758,day="8"
1759,year="2007"
1760,note="Available:
1761\url{http://lwn.net/Articles/253651/}
1762[Viewed October 25, 2007]"
1763,annotation="
1764 LWN article describing the design of preemptible RCU.
1765"
1766}
1767
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001768@article{ThomasEHart2007a
1769,Author="Thomas E. Hart and Paul E. McKenney and Angela Demke Brown and Jonathan Walpole"
1770,Title="Performance of memory reclamation for lockless synchronization"
1771,journal="J. Parallel Distrib. Comput."
1772,volume={67}
1773,number="12"
1774,year="2007"
1775,issn="0743-7315"
1776,pages="1270--1285"
1777,doi="http://dx.doi.org/10.1016/j.jpdc.2007.04.010"
1778,publisher="Academic Press, Inc."
1779,address="Orlando, FL, USA"
1780,annotation={
1781 Compares QSBR, HPBR, EBR, and lock-free reference counting.
1782 Journal version of ThomasEHart2006a.
1783}
1784}
1785
1786@unpublished{MathieuDesnoyers2007call:rcu:schedNeeded
1787,Author="Mathieu Desnoyers"
1788,Title="Re: [patch 1/2] {Linux} Kernel Markers - Support Multiple Probes"
1789,month="December"
1790,day="20"
1791,year="2007"
1792,note="Available:
1793\url{http://lkml.org/lkml/2007/12/20/244}
1794[Viewed March 27, 2008]"
1795,annotation="
1796 Request for call_rcu_sched() and rcu_barrier_sched().
1797"
1798}
1799
1800
Paul E. McKenney32300752008-05-12 21:21:05 +02001801########################################################################
1802#
1803# "What is RCU?" LWN series.
1804#
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001805# http://lwn.net/Articles/262464/ (What is RCU, Fundamentally?)
1806# http://lwn.net/Articles/263130/ (What is RCU's Usage?)
1807# http://lwn.net/Articles/264090/ (What is RCU's API?)
Paul E. McKenney32300752008-05-12 21:21:05 +02001808
1809@unpublished{PaulEMcKenney2007WhatIsRCUFundamentally
1810,Author="Paul E. McKenney and Jonathan Walpole"
1811,Title="What is {RCU}, Fundamentally?"
1812,month="December"
1813,day="17"
1814,year="2007"
1815,note="Available:
1816\url{http://lwn.net/Articles/262464/}
1817[Viewed December 27, 2007]"
1818,annotation="
1819 Lays out the three basic components of RCU: (1) publish-subscribe,
1820 (2) wait for pre-existing readers to complete, and (2) maintain
1821 multiple versions.
1822"
1823}
1824
1825@unpublished{PaulEMcKenney2008WhatIsRCUUsage
1826,Author="Paul E. McKenney"
1827,Title="What is {RCU}? Part 2: Usage"
1828,month="January"
1829,day="4"
1830,year="2008"
1831,note="Available:
1832\url{http://lwn.net/Articles/263130/}
1833[Viewed January 4, 2008]"
1834,annotation="
1835 Lays out six uses of RCU:
1836 1. RCU is a Reader-Writer Lock Replacement
1837 2. RCU is a Restricted Reference-Counting Mechanism
1838 3. RCU is a Bulk Reference-Counting Mechanism
1839 4. RCU is a Poor Man's Garbage Collector
1840 5. RCU is a Way of Providing Existence Guarantees
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001841 6. RCU is a Way of Waiting for Things to Finish
Paul E. McKenney32300752008-05-12 21:21:05 +02001842"
1843}
1844
1845@unpublished{PaulEMcKenney2008WhatIsRCUAPI
1846,Author="Paul E. McKenney"
1847,Title="{RCU} part 3: the {RCU} {API}"
1848,month="January"
1849,day="17"
1850,year="2008"
1851,note="Available:
1852\url{http://lwn.net/Articles/264090/}
1853[Viewed January 10, 2008]"
1854,annotation="
1855 Gives an overview of the Linux-kernel RCU API and a brief annotated RCU
1856 bibliography.
1857"
1858}
1859
Paul E. McKenney4c540052010-01-14 16:10:57 -08001860#
1861# "What is RCU?" LWN series.
1862#
1863########################################################################
1864
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001865
1866@unpublished{SteveRostedt2008dyntickRCUpatch
1867,Author="Steven Rostedt and Paul E. McKenney"
1868,Title="{[PATCH]} add support for dynamic ticks and preempt rcu"
1869,month="January"
1870,day="29"
1871,year="2008"
1872,note="Available:
1873\url{http://lkml.org/lkml/2008/1/29/208}
1874[Viewed March 27, 2008]"
1875,annotation="
1876 Patch that prevents preemptible RCU from unnecessarily waking
1877 up dynticks-idle CPUs.
1878"
1879}
1880
1881@unpublished{PaulEMcKenney2008LKMLDependencyOrdering
1882,Author="Paul E. McKenney"
1883,Title="Re: [PATCH 02/22 -v7] Add basic support for gcc profiler instrumentation"
1884,month="February"
1885,day="1"
1886,year="2008"
1887,note="Available:
1888\url{http://lkml.org/lkml/2008/2/2/255}
1889[Viewed October 18, 2008]"
1890,annotation="
1891 Explanation of compilers violating dependency ordering.
1892"
1893}
1894
1895@Conference{PaulEMcKenney2008Beijing
1896,Author="Paul E. McKenney"
1897,Title="Introducing Technology Into {Linux} Or:
1898Introducing your technology Into {Linux} will require introducing a
1899lot of {Linux} into your technology!!!"
1900,Booktitle="2008 Linux Developer Symposium - China"
1901,Publisher="OSS China"
1902,Month="February"
1903,Year="2008"
1904,Address="Beijing, China"
1905,note="Available:
1906\url{http://www.rdrop.com/users/paulmck/RCU/TechIntroLinux.2008.02.19a.pdf}
1907[Viewed August 12, 2008]"
1908}
1909
1910@unpublished{PaulEMcKenney2008dynticksRCU
1911,Author="Paul E. McKenney and Steven Rostedt"
1912,Title="Integrating and Validating dynticks and Preemptable RCU"
1913,month="April"
1914,day="24"
1915,year="2008"
1916,note="Available:
1917\url{http://lwn.net/Articles/279077/}
1918[Viewed April 24, 2008]"
1919,annotation="
1920 Describes use of Promela and Spin to validate (and fix!) the
1921 dynticks/RCU interface.
1922"
1923}
1924
Paul E. McKenney32300752008-05-12 21:21:05 +02001925@article{DinakarGuniguntala2008IBMSysJ
1926,author="D. Guniguntala and P. E. McKenney and J. Triplett and J. Walpole"
1927,title="The read-copy-update mechanism for supporting real-time applications on shared-memory multiprocessor systems with {Linux}"
1928,Year="2008"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001929,Month="April-June"
Paul E. McKenney32300752008-05-12 21:21:05 +02001930,journal="IBM Systems Journal"
1931,volume="47"
1932,number="2"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001933,pages="221-236"
Paul E. McKenney32300752008-05-12 21:21:05 +02001934,annotation="
1935 RCU, realtime RCU, sleepable RCU, performance.
1936"
1937}
Paul E. McKenney240ebbf2009-06-25 09:08:18 -07001938
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001939@unpublished{LaiJiangshan2008NewClassicAlgorithm
1940,Author="Lai Jiangshan"
1941,Title="[{RFC}][{PATCH}] rcu classic: new algorithm for callbacks-processing"
1942,month="June"
1943,day="3"
1944,year="2008"
1945,note="Available:
1946\url{http://lkml.org/lkml/2008/6/2/539}
1947[Viewed December 10, 2008]"
1948,annotation="
1949 Updated RCU classic algorithm. Introduced multi-tailed list
1950 for RCU callbacks and also pulling common code into
1951 __call_rcu().
1952"
1953}
1954
Paul E. McKenney240ebbf2009-06-25 09:08:18 -07001955@article{PaulEMcKenney2008RCUOSR
1956,author="Paul E. McKenney and Jonathan Walpole"
1957,title="Introducing technology into the {Linux} kernel: a case study"
1958,Year="2008"
1959,journal="SIGOPS Oper. Syst. Rev."
1960,volume="42"
1961,number="5"
1962,pages="4--17"
1963,issn="0163-5980"
1964,doi={http://doi.acm.org/10.1145/1400097.1400099}
1965,publisher="ACM"
1966,address="New York, NY, USA"
1967,annotation={
1968 Linux changed RCU to a far greater degree than RCU has changed Linux.
1969}
1970}
1971
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001972@unpublished{ManfredSpraul2008StateMachineRCU
1973,Author="Manfred Spraul"
1974,Title="[{RFC}, {PATCH}] state machine based rcu"
1975,month="August"
1976,day="21"
1977,year="2008"
1978,note="Available:
1979\url{http://lkml.org/lkml/2008/8/21/336}
1980[Viewed December 8, 2008]"
1981,annotation="
1982 State-based RCU. One key thing that this patch does is to
1983 separate the dynticks handling of NMIs and IRQs.
1984"
1985}
1986
1987@unpublished{ManfredSpraul2008dyntickIRQNMI
1988,Author="Manfred Spraul"
1989,Title="Re: [{RFC}, {PATCH}] v4 scalable classic {RCU} implementation"
1990,month="September"
1991,day="6"
1992,year="2008"
1993,note="Available:
1994\url{http://lkml.org/lkml/2008/9/6/86}
1995[Viewed December 8, 2008]"
1996,annotation="
1997 Manfred notes a fix required to my attempt to separate irq
1998 and NMI processing for hierarchical RCU's dynticks interface.
1999"
2000}
2001
2002@techreport{PaulEMcKenney2008cyclicRCU
2003,author="Paul E. McKenney"
2004,title="Efficient Support of Consistent Cyclic Search With Read-Copy Update"
2005,institution="US Patent and Trademark Office"
2006,address="Washington, DC"
2007,year="2008"
2008,number="US Patent 7,426,511"
2009,month="September"
2010,pages="23"
2011,annotation="
2012 Maintains an additional level of indirection to allow
2013 readers to confine themselves to the desired snapshot of the
2014 data structure. Only permits one update at a time.
2015"
2016}
2017
Paul E. McKenney240ebbf2009-06-25 09:08:18 -07002018@unpublished{PaulEMcKenney2008HierarchicalRCU
2019,Author="Paul E. McKenney"
2020,Title="Hierarchical {RCU}"
2021,month="November"
2022,day="3"
2023,year="2008"
2024,note="Available:
2025\url{http://lwn.net/Articles/305782/}
2026[Viewed November 6, 2008]"
2027,annotation="
2028 RCU with combining-tree-based grace-period detection,
2029 permitting it to handle thousands of CPUs.
2030"
2031}
2032
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002033@unpublished{PaulEMcKenney2009BloatwatchRCU
2034,Author="Paul E. McKenney"
2035,Title="Re: [PATCH fyi] RCU: the bloatwatch edition"
2036,month="January"
2037,day="14"
2038,year="2009"
2039,note="Available:
2040\url{http://lkml.org/lkml/2009/1/14/449}
2041[Viewed January 15, 2009]"
2042,annotation="
2043 Small-footprint implementation of RCU for uniprocessor
2044 embedded applications -- and also for exposition purposes.
2045"
2046}
2047
Paul E. McKenney240ebbf2009-06-25 09:08:18 -07002048@conference{PaulEMcKenney2009MaliciousURCU
2049,Author="Paul E. McKenney"
2050,Title="Using a Malicious User-Level {RCU} to Torture {RCU}-Based Algorithms"
2051,Booktitle="linux.conf.au 2009"
2052,month="January"
2053,year="2009"
2054,address="Hobart, Australia"
2055,note="Available:
2056\url{http://www.rdrop.com/users/paulmck/RCU/urcutorture.2009.01.22a.pdf}
2057[Viewed February 2, 2009]"
2058,annotation="
2059 Realtime RCU and torture-testing RCU uses.
2060"
2061}
2062
2063@unpublished{MathieuDesnoyers2009URCU
2064,Author="Mathieu Desnoyers"
2065,Title="[{RFC} git tree] Userspace {RCU} (urcu) for {Linux}"
2066,month="February"
2067,day="5"
2068,year="2009"
2069,note="Available:
2070\url{http://lkml.org/lkml/2009/2/5/572}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002071\url{http://lttng.org/urcu}
Paul E. McKenney240ebbf2009-06-25 09:08:18 -07002072[Viewed February 20, 2009]"
2073,annotation="
2074 Mathieu Desnoyers's user-space RCU implementation.
2075 git://lttng.org/userspace-rcu.git
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002076 http://lttng.org/cgi-bin/gitweb.cgi?p=userspace-rcu.git
2077 http://lttng.org/urcu
Paul E. McKenney240ebbf2009-06-25 09:08:18 -07002078"
2079}
2080
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002081@unpublished{PaulEMcKenney2009LWNBloatWatchRCU
Paul E. McKenney240ebbf2009-06-25 09:08:18 -07002082,Author="Paul E. McKenney"
2083,Title="{RCU}: The {Bloatwatch} Edition"
2084,month="March"
2085,day="17"
2086,year="2009"
2087,note="Available:
2088\url{http://lwn.net/Articles/323929/}
2089[Viewed March 20, 2009]"
2090,annotation="
2091 Uniprocessor assumptions allow simplified RCU implementation.
2092"
2093}
Paul E. McKenney4c540052010-01-14 16:10:57 -08002094
2095@unpublished{PaulEMcKenney2009expeditedRCU
2096,Author="Paul E. McKenney"
2097,Title="[{PATCH} -tip 0/3] expedited 'big hammer' {RCU} grace periods"
2098,month="June"
2099,day="25"
2100,year="2009"
2101,note="Available:
2102\url{http://lkml.org/lkml/2009/6/25/306}
2103[Viewed August 16, 2009]"
2104,annotation="
2105 First posting of expedited RCU to be accepted into -tip.
2106"
2107}
2108
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002109@unpublished{PaulEMcKenney2009fastRTRCU
2110,Author="Paul E. McKenney"
2111,Title="[{PATCH} {RFC} -tip 0/4] {RCU} cleanups and simplified preemptable {RCU}"
2112,month="July"
2113,day="23"
2114,year="2009"
2115,note="Available:
2116\url{http://lkml.org/lkml/2009/7/23/294}
2117[Viewed August 15, 2009]"
2118,annotation="
2119 First posting of simple and fast preemptable RCU.
2120"
2121}
2122
2123@InProceedings{JoshTriplett2009RPHash
Paul E. McKenney4c540052010-01-14 16:10:57 -08002124,Author="Josh Triplett"
2125,Title="Scalable concurrent hash tables via relativistic programming"
2126,month="September"
2127,year="2009"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002128,booktitle="Linux Plumbers Conference 2009"
Paul E. McKenney4c540052010-01-14 16:10:57 -08002129,annotation="
2130 RP fun with hash tables.
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002131 See also JoshTriplett2010RPHash
Paul E. McKenney4c540052010-01-14 16:10:57 -08002132"
2133}
2134
2135@phdthesis{MathieuDesnoyersPhD
Paul E. McKenney998f2ac2010-02-22 17:04:58 -08002136, title = "Low-Impact Operating System Tracing"
Paul E. McKenney4c540052010-01-14 16:10:57 -08002137, author = "Mathieu Desnoyers"
2138, school = "Ecole Polytechnique de Montr\'{e}al"
2139, month = "December"
2140, year = 2009
Paul E. McKenney998f2ac2010-02-22 17:04:58 -08002141,note="Available:
Paul E. McKenney1bd22e32010-02-22 17:05:00 -08002142\url{http://www.lttng.org/pub/thesis/desnoyers-dissertation-2009-12.pdf}
Paul E. McKenney998f2ac2010-02-22 17:04:58 -08002143[Viewed December 9, 2009]"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002144,annotation={
2145 Chapter 6 (page 97) covers user-level RCU.
2146}
2147}
2148
2149@unpublished{RelativisticProgrammingWiki
2150,Author="Josh Triplett and Paul E. McKenney and Jonathan Walpole"
2151,Title="Relativistic Programming"
2152,month="September"
2153,year="2009"
2154,note="Available:
2155\url{http://wiki.cs.pdx.edu/rp/}
2156[Viewed December 9, 2009]"
2157,annotation="
2158 Main Relativistic Programming Wiki.
2159"
2160}
2161
2162@conference{PaulEMcKenney2009DeterministicRCU
2163,Author="Paul E. McKenney"
2164,Title="Deterministic Synchronization in Multicore Systems: the Role of {RCU}"
2165,Booktitle="Eleventh Real Time Linux Workshop"
2166,month="September"
2167,year="2009"
2168,address="Dresden, Germany"
2169,note="Available:
2170\url{http://www.rdrop.com/users/paulmck/realtime/paper/DetSyncRCU.2009.08.18a.pdf}
2171[Viewed January 14, 2009]"
2172}
2173
2174@unpublished{PaulEMcKenney2009HuntingHeisenbugs
2175,Author="Paul E. McKenney"
2176,Title="Hunting Heisenbugs"
2177,month="November"
2178,year="2009"
2179,day="1"
2180,note="Available:
2181\url{http://paulmck.livejournal.com/14639.html}
2182[Viewed June 4, 2010]"
2183,annotation="
2184 Day-one bug in Tree RCU that took forever to track down.
2185"
2186}
2187
2188@unpublished{MathieuDesnoyers2009defer:rcu
2189,Author="Mathieu Desnoyers"
2190,Title="Kernel RCU: shrink the size of the struct rcu\_head"
2191,month="December"
2192,year="2009"
2193,note="Available:
2194\url{http://lkml.org/lkml/2009/10/18/129}
2195[Viewed December 29, 2009]"
2196,annotation="
2197 Mathieu proposed defer_rcu() with fixed-size per-thread pool
2198 of RCU callbacks.
2199"
2200}
2201
2202@unpublished{MathieuDesnoyers2009VerifPrePub
2203,Author="Mathieu Desnoyers and Paul E. McKenney and Michel R. Dagenais"
2204,Title="Multi-Core Systems Modeling for Formal Verification of Parallel Algorithms"
2205,month="December"
2206,year="2009"
2207,note="Submitted to IEEE TPDS"
2208,annotation="
2209 OOMem model for Mathieu's user-level RCU mechanical proof of
2210 correctness.
2211"
2212}
2213
2214@unpublished{MathieuDesnoyers2009URCUPrePub
2215,Author="Mathieu Desnoyers and Paul E. McKenney and Alan Stern and Michel R. Dagenais and Jonathan Walpole"
2216,Title="User-Level Implementations of Read-Copy Update"
2217,month="December"
2218,year="2010"
2219,url=\url{http://www.computer.org/csdl/trans/td/2012/02/ttd2012020375-abs.html}
2220,annotation="
2221 RCU overview, desiderata, semi-formal semantics, user-level RCU
2222 usage scenarios, three classes of RCU implementation, wait-free
2223 RCU updates, RCU grace-period batching, update overhead,
2224 http://www.rdrop.com/users/paulmck/RCU/urcu-main-accepted.2011.08.30a.pdf
2225 http://www.rdrop.com/users/paulmck/RCU/urcu-supp-accepted.2011.08.30a.pdf
2226 Superseded by MathieuDesnoyers2012URCU.
2227"
2228}
2229
2230@inproceedings{HariKannan2009DynamicAnalysisRCU
2231,author = {Kannan, Hari}
2232,title = {Ordering decoupled metadata accesses in multiprocessors}
2233,booktitle = {MICRO 42: Proceedings of the 42nd Annual IEEE/ACM International Symposium on Microarchitecture}
2234,year = {2009}
2235,isbn = {978-1-60558-798-1}
2236,pages = {381--390}
2237,location = {New York, New York}
2238,doi = {http://doi.acm.org/10.1145/1669112.1669161}
2239,publisher = {ACM}
2240,address = {New York, NY, USA}
2241,annotation={
2242 Uses RCU to protect metadata used in dynamic analysis.
2243}}
2244
2245@conference{PaulEMcKenney2010SimpleOptRCU
2246,Author="Paul E. McKenney"
2247,Title="Simplicity Through Optimization"
2248,Booktitle="linux.conf.au 2010"
2249,month="January"
2250,year="2010"
2251,address="Wellington, New Zealand"
2252,note="Available:
2253\url{http://www.rdrop.com/users/paulmck/RCU/SimplicityThruOptimization.2010.01.21f.pdf}
2254[Viewed October 10, 2010]"
2255,annotation="
2256 TREE_PREEMPT_RCU optimizations greatly simplified the old
2257 PREEMPT_RCU implementation.
2258"
2259}
2260
2261@unpublished{PaulEMcKenney2010LockdepRCU
2262,Author="Paul E. McKenney"
2263,Title="Lockdep-{RCU}"
2264,month="February"
2265,year="2010"
2266,day="1"
2267,note="Available:
2268\url{https://lwn.net/Articles/371986/}
2269[Viewed June 4, 2010]"
2270,annotation="
2271 CONFIG_PROVE_RCU, or at least an early version.
2272"
2273}
2274
2275@unpublished{AviKivity2010KVM2RCU
2276,Author="Avi Kivity"
2277,Title="[{PATCH} 37/40] {KVM}: Bump maximum vcpu count to 64"
2278,month="February"
2279,year="2010"
2280,note="Available:
2281\url{http://www.mail-archive.com/kvm@vger.kernel.org/msg28640.html}
2282[Viewed March 20, 2010]"
2283,annotation="
2284 Use of RCU permits KVM to increase the size of guest OSes from
2285 16 CPUs to 64 CPUs.
2286"
2287}
2288
2289@unpublished{HerbertXu2010RCUResizeHash
2290,Author="Herbert Xu"
2291,Title="bridge: Add core IGMP snooping support"
2292,month="February"
2293,year="2010"
2294,note="Available:
2295\url{http://kerneltrap.com/mailarchive/linux-netdev/2010/2/26/6270589}
2296[Viewed March 20, 2011]"
2297,annotation={
2298 Use a pair of list_head structures to support RCU-protected
2299 resizable hash tables.
2300}}
2301
2302@article{JoshTriplett2010RPHash
2303,author="Josh Triplett and Paul E. McKenney and Jonathan Walpole"
2304,title="Scalable Concurrent Hash Tables via Relativistic Programming"
2305,journal="ACM Operating Systems Review"
2306,year=2010
2307,volume=44
2308,number=3
2309,month="July"
2310,annotation={
2311 RP fun with hash tables.
2312 http://portal.acm.org/citation.cfm?id=1842733.1842750
2313}}
2314
2315@unpublished{PaulEMcKenney2010RCUAPI
2316,Author="Paul E. McKenney"
2317,Title="The {RCU} {API}, 2010 Edition"
2318,month="December"
2319,day="8"
2320,year="2010"
2321,note="Available:
2322\url{http://lwn.net/Articles/418853/}
2323[Viewed December 8, 2010]"
2324,annotation="
2325 Includes updated software-engineering features.
2326"
2327}
2328
2329@mastersthesis{AndrejPodzimek2010masters
2330,author="Andrej Podzimek"
2331,title="Read-Copy-Update for OpenSolaris"
2332,school="Charles University in Prague"
2333,year="2010"
2334,note="Available:
2335\url{https://andrej.podzimek.org/thesis.pdf}
2336[Viewed January 31, 2011]"
2337,annotation={
2338 Reviews RCU implementations and creates a few for OpenSolaris.
2339 Drives quiescent-state detection from RCU read-side primitives,
2340 in a manner roughly similar to that of Jim Houston.
2341}}
2342
2343@unpublished{LinusTorvalds2011Linux2:6:38:rc1:NPigginVFS
2344,Author="Linus Torvalds"
2345,Title="Linux 2.6.38-rc1"
2346,month="January"
2347,year="2011"
2348,note="Available:
2349\url{https://lkml.org/lkml/2011/1/18/322}
2350[Viewed March 4, 2011]"
2351,annotation={
2352 "The RCU-based name lookup is at the other end of the spectrum - the
2353 absolute anti-gimmick. It's some seriously good stuff, and gets rid of
2354 the last main global lock that really tends to hurt some kernel loads.
2355 The dentry lock is no longer a big serializing issue. What's really
2356 nice about it is that it actually improves performance a lot even for
2357 single-threaded loads (on an SMP kernel), because it gets rid of some
2358 of the most expensive parts of path component lookup, which was the
2359 d_lock on every component lookup. So I'm seeing improvements of 30-50%
2360 on some seriously pathname-lookup intensive loads."
2361}}
2362
2363@techreport{JoshTriplett2011RPScalableCorrectOrdering
2364,author = {Josh Triplett and Philip W. Howard and Paul E. McKenney and Jonathan Walpole}
2365,title = {Scalable Correct Memory Ordering via Relativistic Programming}
2366,year = {2011}
2367,number = {11-03}
2368,institution = {Portland State University}
2369,note = {\url{http://www.cs.pdx.edu/pdfs/tr1103.pdf}}
2370}
2371
2372@inproceedings{PhilHoward2011RCUTMRBTree
2373,author = {Philip W. Howard and Jonathan Walpole}
2374,title = {A Relativistic Enhancement to Software Transactional Memory}
2375,booktitle = {Proceedings of the 3rd USENIX conference on Hot topics in parallelism}
2376,series = {HotPar'11}
2377,year = {2011}
2378,location = {Berkeley, CA}
2379,pages = {1--6}
2380,numpages = {6}
2381,url = {http://www.usenix.org/event/hotpar11/tech/final_files/Howard.pdf}
2382,publisher = {USENIX Association}
2383,address = {Berkeley, CA, USA}
2384}
2385
2386@techreport{PaulEMcKenney2011cyclicparallelRCU
2387,author="Paul E. McKenney and Jonathan Walpole"
2388,title="Efficient Support of Consistent Cyclic Search With Read-Copy Update and Parallel Updates"
2389,institution="US Patent and Trademark Office"
2390,address="Washington, DC"
2391,year="2011"
2392,number="US Patent 7,953,778"
2393,month="May"
2394,pages="34"
2395,annotation="
2396 Maintains an array of generation numbers to track in-flight
2397 updates and keeps an additional level of indirection to allow
2398 readers to confine themselves to the desired snapshot of the
2399 data structure.
2400"
2401}
2402
2403@inproceedings{Triplett:2011:RPHash
2404,author = {Triplett, Josh and McKenney, Paul E. and Walpole, Jonathan}
2405,title = {Resizable, Scalable, Concurrent Hash Tables via Relativistic Programming}
2406,booktitle = {Proceedings of the 2011 USENIX Annual Technical Conference}
2407,month = {June}
2408,year = {2011}
2409,pages = {145--158}
2410,numpages = {14}
2411,url={http://www.usenix.org/event/atc11/tech/final_files/atc11_proceedings.pdf}
2412,publisher = {The USENIX Association}
2413,address = {Portland, OR USA}
2414}
2415
2416@unpublished{PaulEMcKenney2011RCU3.0trainwreck
2417,Author="Paul E. McKenney"
2418,Title="3.0 and {RCU:} what went wrong"
2419,month="July"
2420,day="27"
2421,year="2011"
2422,note="Available:
2423\url{http://lwn.net/Articles/453002/}
2424[Viewed July 27, 2011]"
2425,annotation="
2426 Analysis of the RCU trainwreck in Linux kernel 3.0.
2427"
2428}
2429
2430@unpublished{NeilBrown2011MeetTheLockers
2431,Author="Neil Brown"
2432,Title="Meet the Lockers"
2433,month="August"
2434,day="3"
2435,year="2011"
2436,note="Available:
2437\url{http://lwn.net/Articles/453685/}
2438[Viewed September 2, 2011]"
2439,annotation="
2440 The Locker family as an analogy for locking, reference counting,
2441 RCU, and seqlock.
2442"
2443}
2444
2445@article{MathieuDesnoyers2012URCU
2446,Author="Mathieu Desnoyers and Paul E. McKenney and Alan Stern and Michel R. Dagenais and Jonathan Walpole"
2447,Title="User-Level Implementations of Read-Copy Update"
2448,journal="IEEE Transactions on Parallel and Distributed Systems"
2449,volume={23}
2450,year="2012"
2451,issn="1045-9219"
2452,pages="375-382"
2453,doi="http://doi.ieeecomputersociety.org/10.1109/TPDS.2011.159"
2454,publisher="IEEE Computer Society"
2455,address="Los Alamitos, CA, USA"
2456,annotation={
2457 RCU overview, desiderata, semi-formal semantics, user-level RCU
2458 usage scenarios, three classes of RCU implementation, wait-free
2459 RCU updates, RCU grace-period batching, update overhead,
2460 http://www.rdrop.com/users/paulmck/RCU/urcu-main-accepted.2011.08.30a.pdf
2461 http://www.rdrop.com/users/paulmck/RCU/urcu-supp-accepted.2011.08.30a.pdf
2462}
Paul E. McKenney4c540052010-01-14 16:10:57 -08002463}