blob: f29bcbc463e70d715a8f522cedf1d10990ae4d0e [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
Paul E. McKenneye4696a12014-02-15 08:52:32 -080034In 1987, Rashid et al. described lazy TLB-flush [RichardRashid87a].
35At first glance, this has nothing to do with RCU, but nevertheless
36this paper helped inspire the update-side batching used in the later
37RCU implementation in DYNIX/ptx. In 1988, Barbara Liskov published
38a description of Argus that noted that use of out-of-date values can
39be tolerated in some situations. Thus, this paper provides some early
40theoretical justification for use of stale data.
41
Linus Torvalds1da177e2005-04-16 15:20:36 -070042In 1990, Pugh [Pugh90] noted that explicitly tracking which threads
43were reading a given data structure permitted deferred free to operate
44in the presence of non-terminating threads. However, this explicit
45tracking imposes significant read-side overhead, which is undesirable
46in read-mostly situations. This algorithm does take pains to avoid
47write-side contention and parallelize the other write-side overheads by
48providing a fine-grained locking design, however, it would be interesting
49to see how much of the performance advantage reported in 1990 remains
Paul E. McKenney6ae37712013-05-01 10:05:01 -070050today.
Linus Torvalds1da177e2005-04-16 15:20:36 -070051
Paul E. McKenneye4696a12014-02-15 08:52:32 -080052At about this same time, Andrews [Andrews91textbook] described ``chaotic
53relaxation'', where the normal barriers between successive iterations
54of convergent numerical algorithms are relaxed, so that iteration $n$
55might use data from iteration $n-1$ or even $n-2$. This introduces
56error, which typically slows convergence and thus increases the number of
Linus Torvalds1da177e2005-04-16 15:20:36 -070057iterations required. However, this increase is sometimes more than made
58up for by a reduction in the number of expensive barrier operations,
59which are otherwise required to synchronize the threads at the end
60of each iteration. Unfortunately, chaotic relaxation requires highly
61structured data, such as the matrices used in scientific programs, and
62is thus inapplicable to most data structures in operating-system kernels.
63
Paul E. McKenney32300752008-05-12 21:21:05 +020064In 1992, Henry (now Alexia) Massalin completed a dissertation advising
65parallel programmers to defer processing when feasible to simplify
Paul E. McKenneye4696a12014-02-15 08:52:32 -080066synchronization [HMassalinPhD]. RCU makes extremely heavy use of
67this advice.
Paul E. McKenney32300752008-05-12 21:21:05 +020068
Linus Torvalds1da177e2005-04-16 15:20:36 -070069In 1993, Jacobson [Jacobson93] verbally described what is perhaps the
70simplest deferred-free technique: simply waiting a fixed amount of time
71before freeing blocks awaiting deferred free. Jacobson did not describe
72any write-side changes he might have made in this work using SGI's Irix
73kernel. Aju John published a similar technique in 1995 [AjuJohn95].
74This works well if there is a well-defined upper bound on the length of
75time that reading threads can hold references, as there might well be in
76hard real-time systems. However, if this time is exceeded, perhaps due
77to preemption, excessive interrupts, or larger-than-anticipated load,
78memory corruption can ensue, with no reasonable means of diagnosis.
79Jacobson's technique is therefore inappropriate for use in production
80operating-system kernels, except when such kernels can provide hard
81real-time response guarantees for all operations.
82
83Also in 1995, Pu et al. [Pu95a] applied a technique similar to that of Pugh's
84read-side-tracking to permit replugging of algorithms within a commercial
85Unix operating system. However, this replugging permitted only a single
86reader at a time. The following year, this same group of researchers
87extended their technique to allow for multiple readers [Cowan96a].
88Their approach requires memory barriers (and thus pipeline stalls),
89but reduces memory latency, contention, and locking overheads.
90
911995 also saw the first publication of DYNIX/ptx's RCU mechanism
92[Slingwine95], which was optimized for modern CPU architectures,
93and was successfully applied to a number of situations within the
94DYNIX/ptx kernel. The corresponding conference paper appeared in 1998
95[McKenney98].
96
97In 1999, the Tornado and K42 groups described their "generations"
Paul E. McKenney6ae37712013-05-01 10:05:01 -070098mechanism, which is quite similar to RCU [Gamsa99]. These operating
99systems made pervasive use of RCU in place of "existence locks", which
100greatly simplifies locking hierarchies and helps avoid deadlocks.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700101
Paul E. McKenneye4696a12014-02-15 08:52:32 -0800102The year 2000 saw an email exchange that would likely have
103led to yet another independent invention of something like RCU
104[RustyRussell2000a,RustyRussell2000b]. Instead, 2001 saw the first
105RCU presentation involving Linux [McKenney01a] at OLS. The resulting
106abundance of RCU patches was presented the following year [McKenney02a],
107and use of RCU in dcache was first described that same year [Linder02a].
Linus Torvalds1da177e2005-04-16 15:20:36 -0700108
Paul E. McKenneyd19720a2006-02-01 03:06:42 -0800109Also in 2002, Michael [Michael02b,Michael02a] presented "hazard-pointer"
110techniques that defer the destruction of data structures to simplify
111non-blocking synchronization (wait-free synchronization, lock-free
112synchronization, and obstruction-free synchronization are all examples of
Paul E. McKenneye4696a12014-02-15 08:52:32 -0800113non-blocking synchronization). The corresponding journal article appeared
114in 2004 [MagedMichael04a]. This technique eliminates locking, reduces
115contention, reduces memory latency for readers, and parallelizes pipeline
116stalls and memory latency for writers. However, these techniques still
117impose significant read-side overhead in the form of memory barriers.
118Researchers at Sun worked along similar lines in the same timeframe
119[HerlihyLM02]. These techniques can be thought of as inside-out reference
120counts, where the count is represented by the number of hazard pointers
121referencing a given data structure rather than the more conventional
122counter field within the data structure itself. The key advantage
123of inside-out reference counts is that they can be stored in immortal
124variables, thus allowing races between access and deletion to be avoided.
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +0100125
126By the same token, RCU can be thought of as a "bulk reference count",
127where some form of reference counter covers all reference by a given CPU
128or thread during a set timeframe. This timeframe is related to, but
129not necessarily exactly the same as, an RCU grace period. In classic
130RCU, the reference counter is the per-CPU bit in the "bitmask" field,
131and each such bit covers all references that might have been made by
132the corresponding CPU during the prior grace period. Of course, RCU
133can be thought of in other terms as well.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700134
135In 2003, the K42 group described how RCU could be used to create
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +0100136hot-pluggable implementations of operating-system functions [Appavoo03a].
Paul E. McKenneye4696a12014-02-15 08:52:32 -0800137Later that year saw a paper describing an RCU implementation
138of System V IPC [Arcangeli03] (following up on a suggestion by
139Hugh Dickins [Dickins02a] and an implementation by Mingming Cao
140[MingmingCao2002IPCRCU]), and an introduction to RCU in Linux Journal
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +0100141[McKenney03a].
Linus Torvalds1da177e2005-04-16 15:20:36 -0700142
1432004 has seen a Linux-Journal article on use of RCU in dcache
144[McKenney04a], a performance comparison of locking to RCU on several
145different CPUs [McKenney04b], a dissertation describing use of RCU in a
Paul E. McKenneya83f1fe2005-05-01 08:59:05 -0700146number of operating-system kernels [PaulEdwardMcKenneyPhD], a paper
147describing how to make RCU safe for soft-realtime applications [Sarma04c],
148and a paper describing SELinux performance with RCU [JamesMorris04b].
Linus Torvalds1da177e2005-04-16 15:20:36 -0700149
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +01001502005 brought further adaptation of RCU to realtime use, permitting
Paul E. McKenneydd81eca2005-09-10 00:26:24 -0700151preemption of RCU realtime critical sections [PaulMcKenney05a,
152PaulMcKenney05b].
153
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +01001542006 saw the first best-paper award for an RCU paper [ThomasEHart2006a],
155as well as further work on efficient implementations of preemptible
156RCU [PaulEMcKenney2006b], but priority-boosting of RCU read-side critical
157sections proved elusive. An RCU implementation permitting general
158blocking in read-side critical sections appeared [PaulEMcKenney2006c],
159Robert Olsson described an RCU-protected trie-hash combination
160[RobertOlsson2006a].
161
Paul E. McKenney32300752008-05-12 21:21:05 +02001622007 saw the journal version of the award-winning RCU paper from 2006
163[ThomasEHart2007a], as well as a paper demonstrating use of Promela
164and Spin to mechanically verify an optimization to Oleg Nesterov's
165QRCU [PaulEMcKenney2007QRCUspin], a design document describing
166preemptible RCU [PaulEMcKenney2007PreemptibleRCU], and the three-part
167LWN "What is RCU?" series [PaulEMcKenney2007WhatIsRCUFundamentally,
168PaulEMcKenney2008WhatIsRCUUsage, and PaulEMcKenney2008WhatIsRCUAPI].
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +0100169
Paul E. McKenney4c540052010-01-14 16:10:57 -08001702008 saw a journal paper on real-time RCU [DinakarGuniguntala2008IBMSysJ],
171a history of how Linux changed RCU more than RCU changed Linux
172[PaulEMcKenney2008RCUOSR], and a design overview of hierarchical RCU
173[PaulEMcKenney2008HierarchicalRCU].
174
1752009 introduced user-level RCU algorithms [PaulEMcKenney2009MaliciousURCU],
176which Mathieu Desnoyers is now maintaining [MathieuDesnoyers2009URCU]
177[MathieuDesnoyersPhD]. TINY_RCU [PaulEMcKenney2009BloatWatchRCU] made
178its appearance, as did expedited RCU [PaulEMcKenney2009expeditedRCU].
179The problem of resizeable RCU-protected hash tables may now be on a path
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800180to a solution [JoshTriplett2009RPHash]. A few academic researchers are now
181using RCU to solve their parallel problems [HariKannan2009DynamicAnalysisRCU].
182
1832010 produced a simpler preemptible-RCU implementation
184based on TREE_RCU [PaulEMcKenney2010SimpleOptRCU], lockdep-RCU
185[PaulEMcKenney2010LockdepRCU], another resizeable RCU-protected hash
186table [HerbertXu2010RCUResizeHash] (this one consuming more memory,
187but allowing arbitrary changes in hash function, as required for DoS
188avoidance in the networking code), realization of the 2009 RCU-protected
189hash table with atomic node move [JoshTriplett2010RPHash], an update on
190the RCU API [PaulEMcKenney2010RCUAPI].
191
1922011 marked the inclusion of Nick Piggin's fully lockless dentry search
193[LinusTorvalds2011Linux2:6:38:rc1:NPigginVFS], an RCU-protected red-black
194tree using software transactional memory to protect concurrent updates
195(strange, but true!) [PhilHoward2011RCUTMRBTree], yet another variant of
196RCU-protected resizeable hash tables [Triplett:2011:RPHash], the 3.0 RCU
197trainwreck [PaulEMcKenney2011RCU3.0trainwreck], and Neil Brown's "Meet the
Paul E. McKenney6ae37712013-05-01 10:05:01 -0700198Lockers" LWN article [NeilBrown2011MeetTheLockers]. Some academic
199work looked at debugging uses of RCU [Seyster:2011:RFA:2075416.2075425].
200
201In 2012, Josh Triplett received his Ph.D. with his dissertation
202covering RCU-protected resizable hash tables and the relationship
203between memory barriers and read-side traversal order: If the updater
204is making changes in the opposite direction from the read-side traveral
205order, the updater need only execute a memory-barrier instruction,
206but if in the same direction, the updater needs to wait for a grace
207period between the individual updates [JoshTriplettPhD]. Also in 2012,
208after seventeen years of attempts, an RCU paper made it into a top-flight
209academic journal, IEEE Transactions on Parallel and Distributed Systems
210[MathieuDesnoyers2012URCU]. A group of researchers in Spain applied
211user-level RCU to crowd simulation [GuillermoVigueras2012RCUCrowd], and
212another group of researchers in Europe produced a formal description of
213RCU based on separation logic [AlexeyGotsman2012VerifyGraceExtended],
214which was published in the 2013 European Symposium on Programming
215[AlexeyGotsman2013ESOPRCU].
216
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800217
Paul E. McKenney4c540052010-01-14 16:10:57 -0800218
Linus Torvalds1da177e2005-04-16 15:20:36 -0700219Bibtex Entries
220
221@article{Kung80
222,author="H. T. Kung and Q. Lehman"
Dhaval Giani0f9574d2012-10-17 14:46:13 -0700223,title="Concurrent Manipulation of Binary Search Trees"
Linus Torvalds1da177e2005-04-16 15:20:36 -0700224,Year="1980"
225,Month="September"
226,journal="ACM Transactions on Database Systems"
227,volume="5"
228,number="3"
229,pages="354-382"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800230,annotation={
231 Use garbage collector to clean up data after everyone is done with it.
232 .
233 Oldest use of something vaguely resembling RCU that I have found.
Paul E. McKenney6ae37712013-05-01 10:05:01 -0700234 http://portal.acm.org/citation.cfm?id=320619&dl=GUIDE,
235 [Viewed December 3, 2007]
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800236}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700237}
238
239@techreport{Manber82
240,author="Udi Manber and Richard E. Ladner"
241,title="Concurrency Control in a Dynamic Search Structure"
242,institution="Department of Computer Science, University of Washington"
243,address="Seattle, Washington"
244,year="1982"
245,number="82-01-01"
246,month="January"
247,pages="28"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800248,annotation={
249 .
250 Superseded by Manber84.
251 .
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 Cites Kung80, so not an independent invention, but the first
270 RCU-like usage that does not rely on an automatic garbage
271 collector.
272}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700273}
274
275@article{Manber84
276,author="Udi Manber and Richard E. Ladner"
277,title="Concurrency Control in a Dynamic Search Structure"
278,Year="1984"
279,Month="September"
280,journal="ACM Transactions on Database Systems"
281,volume="9"
282,number="3"
283,pages="439-455"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800284,annotation={
285 Describes concurrent AVL tree implementation. Uses a
286 garbage-collection mechanism to handle concurrent use and deletion
287 of nodes in the tree, but lacks the summary-of-execution-history
288 concept of read-copy locking.
289 .
290 Keeps full list of processes that were active when a given
291 node was to be deleted, and waits until all such processes have
292 -terminated- before allowing this node to be reused. This is
293 not described in great detail -- one could imagine using process
294 IDs for this if the ID space was large enough that overlapping
295 never occurred.
296 .
297 This restriction makes this algorithm unsuitable for use in
298 systems comprised of long-lived processes. It also produces
299 completely unacceptable overhead in systems with large numbers
300 of processes. Finally, it is specific to AVL trees.
301}
302}
303
304@Conference{RichardRashid87a
305,Author="Richard Rashid and Avadis Tevanian and Michael Young and
306David Golub and Robert Baron and David Black and William Bolosky and
307Jonathan Chew"
308,Title="Machine-Independent Virtual Memory Management for Paged
309Uniprocessor and Multiprocessor Architectures"
310,Booktitle="{2\textsuperscript{nd} Symposium on Architectural Support
311for Programming Languages and Operating Systems}"
312,Publisher="Association for Computing Machinery"
313,Month="October"
314,Year="1987"
315,pages="31-39"
316,Address="Palo Alto, CA"
317,note="Available:
318\url{http://www.cse.ucsc.edu/~randal/221/rashid-machvm.pdf}
319[Viewed February 17, 2005]"
320,annotation={
321 Describes lazy TLB flush, where one waits for each CPU to pass
322 through a scheduling-clock interrupt before reusing a given range
323 of virtual address. Does not describe how one determines that
324 all CPUs have in fact taken such an interrupt, though there are
325 no shortage of straightforward methods for accomplishing this.
326 .
327 Note that it does not make sense to just wait a fixed amount of
328 time, since a given CPU might have interrupts disabled for an
329 extended amount of time.
330}
331}
332
333@article{BarbaraLiskov1988ArgusCACM
334,author = {Barbara Liskov}
335,title = {Distributed programming in {Argus}}
336,journal = {Commun. ACM}
337,volume = {31}
338,number = {3}
339,year = {1988}
340,issn = {0001-0782}
341,pages = {300--312}
342,doi = {http://doi.acm.org/10.1145/42392.42399}
343,publisher = {ACM}
344,address = {New York, NY, USA}
Paul E. McKenney6ae37712013-05-01 10:05:01 -0700345,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800346 At the top of page 307: "Conflicts with deposits and withdrawals
347 are necessary if the reported total is to be up to date. They
348 could be avoided by having total return a sum that is slightly
349 out of date." Relies on semantics -- approximate numerical
350 values sometimes OK.
351}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700352}
353
354@techreport{Hennessy89
355,author="James P. Hennessy and Damian L. Osisek and Joseph W. {Seigh II}"
356,title="Passive Serialization in a Multitasking Environment"
357,institution="US Patent and Trademark Office"
358,address="Washington, DC"
359,year="1989"
360,number="US Patent 4,809,168 (lapsed)"
361,month="February"
362,pages="11"
363}
364
365@techreport{Pugh90
366,author="William Pugh"
367,title="Concurrent Maintenance of Skip Lists"
368,institution="Institute of Advanced Computer Science Studies, Department of Computer Science, University of Maryland"
369,address="College Park, Maryland"
370,year="1990"
371,number="CS-TR-2222.1"
372,month="June"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800373,annotation={
374 Concurrent access to skip lists. Has both weak and strong search.
375 Uses concept of ``garbage queue'', but has no real way of cleaning
376 the garbage efficiently.
377 .
378 Appears to be an independent invention of an RCU-like mechanism.
379}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700380}
381
Paul E. McKenney6ae37712013-05-01 10:05:01 -0700382# Was Adams91, see also syncrefs.bib.
383@Book{Andrews91textbook
384,Author="Gregory R. Andrews"
Linus Torvalds1da177e2005-04-16 15:20:36 -0700385,title="Concurrent Programming, Principles, and Practices"
386,Publisher="Benjamin Cummins"
387,Year="1991"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800388,annotation={
389 Has a few paragraphs describing ``chaotic relaxation'', a
390 numerical analysis technique that allows multiprocessors to
391 avoid synchronization overhead by using possibly-stale data.
392 .
393 Seems like this is descended from yet another independent
394 invention of RCU-like function -- but this is restricted
395 in that reclamation is not necessary.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700396}
Paul E. McKenney32300752008-05-12 21:21:05 +0200397}
398
Paul E. McKenneye4696a12014-02-15 08:52:32 -0800399@phdthesis{HMassalinPhD
400,author="H. Massalin"
401,title="Synthesis: An Efficient Implementation of Fundamental Operating
402System Services"
403,school="Columbia University"
404,address="New York, NY"
405,year="1992"
406,annotation={
407 Mondo optimizing compiler.
408 Wait-free stuff.
409 Good advice: defer work to avoid synchronization. See page 90
410 (PDF page 106), Section 5.4, fourth bullet point.
411}
412}
413
Linus Torvalds1da177e2005-04-16 15:20:36 -0700414@unpublished{Jacobson93
415,author="Van Jacobson"
416,title="Avoid Read-Side Locking Via Delayed Free"
417,year="1993"
418,month="September"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800419,note="private communication"
420,annotation={
421 Use fixed time delay to approximate grace period. Very simple,
422 but subject to random memory corruption under heavy load.
423 .
424 Independent invention of RCU-like mechanism.
425}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700426}
427
428@Conference{AjuJohn95
429,Author="Aju John"
430,Title="Dynamic vnodes -- Design and Implementation"
431,Booktitle="{USENIX Winter 1995}"
432,Publisher="USENIX Association"
433,Month="January"
434,Year="1995"
435,pages="11-23"
436,Address="New Orleans, LA"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800437,note="Available:
438\url{https://www.usenix.org/publications/library/proceedings/neworl/full_papers/john.a}
439[Viewed October 1, 2010]"
440,annotation={
441 Age vnodes out of the cache, and have a fixed time set by a kernel
442 parameter. Not clear that all races were in fact correctly handled.
443 Used a 20-minute time by default, which would most definitely not
444 be suitable during DoS attacks or virus scans.
445 .
446 Apparently independent invention of RCU-like mechanism.
447}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700448}
449
Paul E. McKenney6ae37712013-05-01 10:05:01 -0700450@conference{Pu95a
451,Author = "Calton Pu and Tito Autrey and Andrew Black and Charles Consel and
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +0100452Crispin Cowan and Jon Inouye and Lakshmi Kethana and Jonathan Walpole and
Paul E. McKenney6ae37712013-05-01 10:05:01 -0700453Ke Zhang"
454,Title = "Optimistic Incremental Specialization: Streamlining a Commercial
455,Operating System"
456,Booktitle = "15\textsuperscript{th} ACM Symposium on
457,Operating Systems Principles (SOSP'95)"
458,address = "Copper Mountain, CO"
459,month="December"
460,year="1995"
461,pages="314-321"
462,annotation={
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +0100463 Uses a replugger, but with a flag to signal when people are
464 using the resource at hand. Only one reader at a time.
Paul E. McKenney6ae37712013-05-01 10:05:01 -0700465}
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +0100466}
467
Paul E. McKenney6ae37712013-05-01 10:05:01 -0700468@conference{Cowan96a
469,Author = "Crispin Cowan and Tito Autrey and Charles Krasic and
470,Calton Pu and Jonathan Walpole"
471,Title = "Fast Concurrent Dynamic Linking for an Adaptive Operating System"
472,Booktitle = "International Conference on Configurable Distributed Systems
473(ICCDS'96)"
474,address = "Annapolis, MD"
475,month="May"
476,year="1996"
477,pages="108"
478,isbn="0-8186-7395-8"
479,annotation={
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +0100480 Uses a replugger, but with a counter to signal when people are
481 using the resource at hand. Allows multiple readers.
Paul E. McKenney6ae37712013-05-01 10:05:01 -0700482}
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +0100483}
484
Linus Torvalds1da177e2005-04-16 15:20:36 -0700485@techreport{Slingwine95
486,author="John D. Slingwine and Paul E. McKenney"
487,title="Apparatus and Method for Achieving Reduced Overhead Mutual
488Exclusion and Maintaining Coherency in a Multiprocessor System
489Utilizing Execution History and Thread Monitoring"
490,institution="US Patent and Trademark Office"
491,address="Washington, DC"
492,year="1995"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800493,number="US Patent 5,442,758"
Linus Torvalds1da177e2005-04-16 15:20:36 -0700494,month="August"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800495,annotation={
496 Describes the parallel RCU infrastructure. Includes NUMA aspect
497 (structure of bitmap can reflect bus structure of computer system).
498 .
499 Another independent invention of an RCU-like mechanism, but the
500 "real" RCU this time!
501}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700502}
503
504@techreport{Slingwine97
505,author="John D. Slingwine and Paul E. McKenney"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800506,title="Method for Maintaining Data Coherency Using Thread Activity
507Summaries in a Multicomputer System"
Linus Torvalds1da177e2005-04-16 15:20:36 -0700508,institution="US Patent and Trademark Office"
509,address="Washington, DC"
510,year="1997"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800511,number="US Patent 5,608,893"
Linus Torvalds1da177e2005-04-16 15:20:36 -0700512,month="March"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800513,pages="19"
514,annotation={
515 Describes use of RCU to synchronize data between a pair of
516 SMP/NUMA computer systems.
517}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700518}
519
520@techreport{Slingwine98
521,author="John D. Slingwine and Paul E. McKenney"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800522,title="Apparatus and Method for Achieving Reduced Overhead Mutual
523Exclusion and Maintaining Coherency in a Multiprocessor System
524Utilizing Execution History and Thread Monitoring"
Linus Torvalds1da177e2005-04-16 15:20:36 -0700525,institution="US Patent and Trademark Office"
526,address="Washington, DC"
527,year="1998"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800528,number="US Patent 5,727,209"
Linus Torvalds1da177e2005-04-16 15:20:36 -0700529,month="March"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800530,annotation={
531 Describes doing an atomic update by copying the data item and
532 then substituting it into the data structure.
533}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700534}
535
536@Conference{McKenney98
537,Author="Paul E. McKenney and John D. Slingwine"
538,Title="Read-Copy Update: Using Execution History to Solve Concurrency
539Problems"
540,Booktitle="{Parallel and Distributed Computing and Systems}"
541,Month="October"
542,Year="1998"
543,pages="509-518"
544,Address="Las Vegas, NV"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800545,annotation={
546 Describes and analyzes RCU mechanism in DYNIX/ptx. Describes
547 application to linked list update and log-buffer flushing.
548 Defines 'quiescent state'. Includes both measured and analytic
549 evaluation.
Paul E. McKenney6ae37712013-05-01 10:05:01 -0700550 http://www.rdrop.com/users/paulmck/RCU/rclockpdcsproof.pdf
551 [Viewed December 3, 2007]
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800552}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700553}
554
555@Conference{Gamsa99
556,Author="Ben Gamsa and Orran Krieger and Jonathan Appavoo and Michael Stumm"
557,Title="Tornado: Maximizing Locality and Concurrency in a Shared Memory
558Multiprocessor Operating System"
559,Booktitle="{Proceedings of the 3\textsuperscript{rd} Symposium on
560Operating System Design and Implementation}"
561,Month="February"
562,Year="1999"
563,pages="87-100"
564,Address="New Orleans, LA"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800565,annotation={
566 Use of RCU-like facility in K42/Tornado. Another independent
567 invention of RCU.
568 See especially pages 7-9 (Section 5).
Paul E. McKenney6ae37712013-05-01 10:05:01 -0700569 http://www.usenix.org/events/osdi99/full_papers/gamsa/gamsa.pdf
570 [Viewed August 30, 2006]
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800571}
572}
573
574@unpublished{RustyRussell2000a
575,Author="Rusty Russell"
576,Title="Re: modular net drivers"
577,month="June"
578,year="2000"
579,day="23"
580,note="Available:
581\url{http://oss.sgi.com/projects/netdev/archive/2000-06/msg00250.html}
582[Viewed April 10, 2006]"
583,annotation={
584 Proto-RCU proposal from Phil Rumpf and Rusty Russell.
585 Yet another independent invention of RCU.
586 Outline of algorithm to unload modules...
587 .
588 Appeared on net-dev mailing list.
589}
590}
591
592@unpublished{RustyRussell2000b
593,Author="Rusty Russell"
594,Title="Re: modular net drivers"
595,month="June"
596,year="2000"
597,day="24"
598,note="Available:
599\url{http://oss.sgi.com/projects/netdev/archive/2000-06/msg00254.html}
600[Viewed April 10, 2006]"
601,annotation={
602 Proto-RCU proposal from Phil Rumpf and Rusty Russell.
603 .
604 Appeared on net-dev mailing list.
605}
606}
607
608@unpublished{McKenney01b
609,Author="Paul E. McKenney and Dipankar Sarma"
610,Title="Read-Copy Update Mutual Exclusion in {Linux}"
611,month="February"
612,year="2001"
613,note="Available:
614\url{http://lse.sourceforge.net/locking/rcu/rcupdate_doc.html}
615[Viewed October 18, 2004]"
616,annotation={
617 Prototypical Linux documentation for RCU.
618}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700619}
620
621@techreport{Slingwine01
622,author="John D. Slingwine and Paul E. McKenney"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800623,title="Apparatus and Method for Achieving Reduced Overhead Mutual
624Exclusion and Maintaining Coherency in a Multiprocessor System
625Utilizing Execution History and Thread Monitoring"
Linus Torvalds1da177e2005-04-16 15:20:36 -0700626,institution="US Patent and Trademark Office"
627,address="Washington, DC"
628,year="2001"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800629,number="US Patent 6,219,690"
Linus Torvalds1da177e2005-04-16 15:20:36 -0700630,month="April"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800631,annotation={
632 'Change in mode' aspect of RCU. Can be thought of as a lazy barrier.
633}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700634}
635
636@Conference{McKenney01a
637,Author="Paul E. McKenney and Jonathan Appavoo and Andi Kleen and
638Orran Krieger and Rusty Russell and Dipankar Sarma and Maneesh Soni"
639,Title="Read-Copy Update"
640,Booktitle="{Ottawa Linux Symposium}"
641,Month="July"
642,Year="2001"
643,note="Available:
644\url{http://www.linuxsymposium.org/2001/abstracts/readcopy.php}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800645\url{http://www.rdrop.com/users/paulmck/RCU/rclock_OLS.2001.05.01c.pdf}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700646[Viewed June 23, 2004]"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800647,annotation={
648 Described RCU, and presented some patches implementing and using
649 it in the Linux kernel.
650}
651}
652
653@unpublished{McKenney01f
654,Author="Paul E. McKenney"
655,Title="{RFC:} patch to allow lock-free traversal of lists with insertion"
656,month="October"
657,year="2001"
658,note="Available:
659\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=100259266316456&w=2}
660[Viewed June 23, 2004]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -0700661,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800662 Memory-barrier and Alpha thread. 100 messages, not too bad...
Paul E. McKenney6ae37712013-05-01 10:05:01 -0700663}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700664}
665
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800666@unpublished{Spraul01
667,Author="Manfred Spraul"
668,Title="Re: {RFC:} patch to allow lock-free traversal of lists with insertion"
669,month="October"
670,year="2001"
671,note="Available:
672\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=100264675012867&w=2}
673[Viewed June 23, 2004]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -0700674,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800675 Suggested burying memory barriers in Linux's list-manipulation
676 primitives.
Paul E. McKenney6ae37712013-05-01 10:05:01 -0700677}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800678}
679
680@unpublished{LinusTorvalds2001a
681,Author="Linus Torvalds"
682,Title="{Re:} {[Lse-tech]} {Re:} {RFC:} patch to allow lock-free traversal of lists with insertion"
683,month="October"
684,year="2001"
685,note="Available:
686\url{http://lkml.org/lkml/2001/10/13/105}
687[Viewed August 21, 2004]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -0700688,annotation={
689}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800690}
691
692@unpublished{Blanchard02a
693,Author="Anton Blanchard"
694,Title="some RCU dcache and ratcache results"
695,month="March"
696,year="2002"
697,note="Available:
698\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=101637107412972&w=2}
699[Viewed October 18, 2004]"
700}
701
Paul E. McKenneye4696a12014-02-15 08:52:32 -0800702@conference{Michael02b
703,author="Maged M. Michael"
704,title="High Performance Dynamic Lock-Free Hash Tables and List-Based Sets"
705,Year="2002"
706,Month="August"
707,booktitle="{Proceedings of the 14\textsuperscript{th} Annual ACM
708Symposium on Parallel
709Algorithms and Architecture}"
710,pages="73-82"
711,annotation={
712Like the title says...
713}
714}
715
Linus Torvalds1da177e2005-04-16 15:20:36 -0700716@Conference{Linder02a
717,Author="Hanna Linder and Dipankar Sarma and Maneesh Soni"
718,Title="Scalability of the Directory Entry Cache"
719,Booktitle="{Ottawa Linux Symposium}"
720,Month="June"
721,Year="2002"
722,pages="289-300"
Paul E. McKenney6ae37712013-05-01 10:05:01 -0700723,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800724 Measured scalability of Linux 2.4 kernel's directory-entry cache
725 (dcache), and measured some scalability enhancements.
Paul E. McKenney6ae37712013-05-01 10:05:01 -0700726}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700727}
728
729@Conference{McKenney02a
730,Author="Paul E. McKenney and Dipankar Sarma and
731Andrea Arcangeli and Andi Kleen and Orran Krieger and Rusty Russell"
732,Title="Read-Copy Update"
733,Booktitle="{Ottawa Linux Symposium}"
734,Month="June"
735,Year="2002"
736,pages="338-367"
737,note="Available:
738\url{http://www.linux.org.uk/~ajh/ols2002_proceedings.pdf.gz}
739[Viewed June 23, 2004]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -0700740,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800741 Presented and compared a number of RCU implementations for the
742 Linux kernel.
Paul E. McKenney6ae37712013-05-01 10:05:01 -0700743}
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +0100744}
745
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800746@unpublished{Sarma02a
747,Author="Dipankar Sarma"
748,Title="specweb99: dcache scalability results"
749,month="July"
750,year="2002"
751,note="Available:
752\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=102645767914212&w=2}
753[Viewed June 23, 2004]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -0700754,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800755 Compare fastwalk and RCU for dcache. RCU won.
Paul E. McKenney6ae37712013-05-01 10:05:01 -0700756}
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +0100757}
758
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800759@unpublished{Barbieri02
760,Author="Luca Barbieri"
761,Title="Re: {[PATCH]} Initial support for struct {vfs\_cred}"
762,month="August"
763,year="2002"
764,note="Available:
765\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=103082050621241&w=2}
766[Viewed: June 23, 2004]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -0700767,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800768 Suggested RCU for vfs\_shared\_cred.
Paul E. McKenney6ae37712013-05-01 10:05:01 -0700769}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800770}
771
Paul E. McKenneye4696a12014-02-15 08:52:32 -0800772@conference{Michael02a
773,author="Maged M. Michael"
774,title="Safe Memory Reclamation for Dynamic Lock-Free Objects Using Atomic
775Reads and Writes"
776,Year="2002"
777,Month="August"
778,booktitle="{Proceedings of the 21\textsuperscript{st} Annual ACM
779Symposium on Principles of Distributed Computing}"
780,pages="21-30"
781,annotation={
782 Each thread keeps an array of pointers to items that it is
783 currently referencing. Sort of an inside-out garbage collection
784 mechanism, but one that requires the accessing code to explicitly
785 state its needs. Also requires read-side memory barriers on
786 most architectures.
787}
788}
789
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800790@unpublished{Dickins02a
791,author="Hugh Dickins"
792,title="Use RCU for System-V IPC"
793,year="2002"
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +0100794,month="October"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800795,note="private communication"
796}
797
Paul E. McKenneye4696a12014-02-15 08:52:32 -0800798@InProceedings{HerlihyLM02
799,author={Maurice Herlihy and Victor Luchangco and Mark Moir}
800,title="The Repeat Offender Problem: A Mechanism for Supporting Dynamic-Sized,
801Lock-Free Data Structures"
802,booktitle={Proceedings of 16\textsuperscript{th} International
803Symposium on Distributed Computing}
804,year=2002
805,month="October"
806,pages="339-353"
807}
808
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800809@unpublished{Sarma02b
810,Author="Dipankar Sarma"
811,Title="Some dcache\_rcu benchmark numbers"
812,month="October"
813,year="2002"
814,note="Available:
815\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=103462075416638&w=2}
816[Viewed June 23, 2004]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -0700817,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800818 Performance of dcache RCU on kernbench for 16x NUMA-Q and 1x,
819 2x, and 4x systems. RCU does no harm, and helps on 16x.
Paul E. McKenney6ae37712013-05-01 10:05:01 -0700820}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800821}
822
Paul E. McKenneye4696a12014-02-15 08:52:32 -0800823@unpublished{MingmingCao2002IPCRCU
824,Author="Mingming Cao"
825,Title="[PATCH]updated ipc lock patch"
826,month="October"
827,year="2002"
828,note="Available:
829\url{https://lkml.org/lkml/2002/10/24/262}
830[Viewed February 15, 2014]"
831,annotation={
832 Mingming Cao's patch to introduce RCU to SysV IPC.
833}
834}
835
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800836@unpublished{LinusTorvalds2003a
837,Author="Linus Torvalds"
838,Title="Re: {[PATCH]} small fixes in brlock.h"
839,month="March"
840,year="2003"
841,note="Available:
842\url{http://lkml.org/lkml/2003/3/9/205}
843[Viewed March 13, 2006]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -0700844,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800845 Linus suggests replacing brlock with RCU and/or seqlocks:
846 .
847 'It's entirely possible that the current user could be replaced
848 by RCU and/or seqlocks, and we could get rid of brlocks entirely.'
849 .
850 Steve Hemminger responds by replacing them with RCU.
Paul E. McKenney6ae37712013-05-01 10:05:01 -0700851}
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +0100852}
853
Linus Torvalds1da177e2005-04-16 15:20:36 -0700854@article{Appavoo03a
855,author="J. Appavoo and K. Hui and C. A. N. Soules and R. W. Wisniewski and
856D. M. {Da Silva} and O. Krieger and M. A. Auslander and D. J. Edelsohn and
857B. Gamsa and G. R. Ganger and P. McKenney and M. Ostrowski and
858B. Rosenburg and M. Stumm and J. Xenidis"
859,title="Enabling Autonomic Behavior in Systems Software With Hot Swapping"
860,Year="2003"
861,Month="January"
862,journal="IBM Systems Journal"
863,volume="42"
864,number="1"
865,pages="60-76"
Paul E. McKenney6ae37712013-05-01 10:05:01 -0700866,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800867 Use of RCU to enable hot-swapping for autonomic behavior in K42.
Paul E. McKenney6ae37712013-05-01 10:05:01 -0700868}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800869}
870
871@unpublished{Seigh03
872,author="Joseph W. {Seigh II}"
873,title="Read Copy Update"
874,Year="2003"
875,Month="March"
876,note="email correspondence"
Paul E. McKenney6ae37712013-05-01 10:05:01 -0700877,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800878 Described the relationship of the VM/XA passive serialization to RCU.
Paul E. McKenney6ae37712013-05-01 10:05:01 -0700879}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700880}
881
882@Conference{Arcangeli03
883,Author="Andrea Arcangeli and Mingming Cao and Paul E. McKenney and
884Dipankar Sarma"
885,Title="Using Read-Copy Update Techniques for {System V IPC} in the
886{Linux} 2.5 Kernel"
887,Booktitle="Proceedings of the 2003 USENIX Annual Technical Conference
888(FREENIX Track)"
889,Publisher="USENIX Association"
890,year="2003"
891,month="June"
892,pages="297-310"
Paul E. McKenney6ae37712013-05-01 10:05:01 -0700893,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800894 Compared updated RCU implementations for the Linux kernel, and
895 described System V IPC use of RCU, including order-of-magnitude
896 performance improvements.
Paul E. McKenney6ae37712013-05-01 10:05:01 -0700897 http://www.rdrop.com/users/paulmck/RCU/rcu.FREENIX.2003.06.14.pdf
898}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800899}
900
901@Conference{Soules03a
902,Author="Craig A. N. Soules and Jonathan Appavoo and Kevin Hui and
903Dilma {Da Silva} and Gregory R. Ganger and Orran Krieger and
904Michael Stumm and Robert W. Wisniewski and Marc Auslander and
905Michal Ostrowski and Bryan Rosenburg and Jimi Xenidis"
906,Title="System Support for Online Reconfiguration"
907,Booktitle="Proceedings of the 2003 USENIX Annual Technical Conference"
908,Publisher="USENIX Association"
909,year="2003"
910,month="June"
911,pages="141-154"
Linus Torvalds1da177e2005-04-16 15:20:36 -0700912}
913
914@article{McKenney03a
915,author="Paul E. McKenney"
916,title="Using {RCU} in the {Linux} 2.5 Kernel"
917,Year="2003"
918,Month="October"
919,journal="Linux Journal"
920,volume="1"
921,number="114"
922,pages="18-26"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800923,note="Available:
924\url{http://www.linuxjournal.com/article/6993}
925[Viewed November 14, 2007]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -0700926,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800927 Reader-friendly intro to RCU, with the infamous old-man-and-brat
928 cartoon.
Paul E. McKenney6ae37712013-05-01 10:05:01 -0700929}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800930}
931
932@unpublished{Sarma03a
933,Author="Dipankar Sarma"
934,Title="RCU low latency patches"
935,month="December"
936,year="2003"
937,note="Message ID: 20031222180114.GA2248@in.ibm.com"
Paul E. McKenney6ae37712013-05-01 10:05:01 -0700938,annotation={
939 dipankar/ct.2004.03.27/RCUll.2003.12.22.patch
940}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700941}
942
Paul E. McKenneya83f1fe2005-05-01 08:59:05 -0700943@techreport{Friedberg03a
944,author="Stuart A. Friedberg"
945,title="Lock-Free Wild Card Search Data Structure and Method"
946,institution="US Patent and Trademark Office"
947,address="Washington, DC"
948,year="2003"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800949,number="US Patent 6,662,184"
Paul E. McKenneya83f1fe2005-05-01 08:59:05 -0700950,month="December"
951,pages="112"
Paul E. McKenney6ae37712013-05-01 10:05:01 -0700952,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800953 Applies RCU to a wildcard-search Patricia tree in order to permit
954 synchronization-free lookup. RCU is used to retain removed nodes
955 for a grace period before freeing them.
Paul E. McKenney6ae37712013-05-01 10:05:01 -0700956}
Paul E. McKenneya83f1fe2005-05-01 08:59:05 -0700957}
958
Linus Torvalds1da177e2005-04-16 15:20:36 -0700959@article{McKenney04a
960,author="Paul E. McKenney and Dipankar Sarma and Maneesh Soni"
961,title="Scaling dcache with {RCU}"
962,Year="2004"
963,Month="January"
964,journal="Linux Journal"
965,volume="1"
966,number="118"
967,pages="38-46"
Paul E. McKenney6ae37712013-05-01 10:05:01 -0700968,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800969 Reader friendly intro to dcache and RCU.
Paul E. McKenney6ae37712013-05-01 10:05:01 -0700970 http://www.linuxjournal.com/node/7124
971 [Viewed December 26, 2010]
972}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700973}
974
975@Conference{McKenney04b
976,Author="Paul E. McKenney"
977,Title="{RCU} vs. Locking Performance on Different {CPUs}"
978,Booktitle="{linux.conf.au}"
979,Month="January"
980,Year="2004"
981,Address="Adelaide, Australia"
982,note="Available:
983\url{http://www.linux.org.au/conf/2004/abstracts.html#90}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800984\url{http://www.rdrop.com/users/paulmck/RCU/lockperf.2004.01.17a.pdf}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700985[Viewed June 23, 2004]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -0700986,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800987 Compares performance of RCU to that of other locking primitives
988 over a number of CPUs (x86, Opteron, Itanium, and PPC).
Paul E. McKenney6ae37712013-05-01 10:05:01 -0700989}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -0800990}
991
992@unpublished{Sarma04a
993,Author="Dipankar Sarma"
994,Title="{[PATCH]} {RCU} for low latency (experimental)"
995,month="March"
996,year="2004"
997,note="\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=108003746402892&w=2}"
Paul E. McKenney6ae37712013-05-01 10:05:01 -0700998,annotation={
999 Head of thread: dipankar/2004.03.23/rcu-low-lat.1.patch
1000}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001001}
1002
1003@unpublished{Sarma04b
1004,Author="Dipankar Sarma"
1005,Title="Re: {[PATCH]} {RCU} for low latency (experimental)"
1006,month="March"
1007,year="2004"
1008,note="\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=108016474829546&w=2}"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001009,annotation={
1010 dipankar/rcuth.2004.03.24/rcu-throttle.patch
1011}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001012}
1013
1014@unpublished{Spraul04a
1015,Author="Manfred Spraul"
1016,Title="[RFC] 0/5 rcu lock update"
1017,month="May"
1018,year="2004"
1019,note="Available:
1020\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=108546407726602&w=2}
1021[Viewed June 23, 2004]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001022,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001023 Hierarchical-bitmap patch for RCU infrastructure.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001024}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001025}
1026
1027@unpublished{Steiner04a
1028,Author="Jack Steiner"
1029,Title="Re: [Lse-tech] [RFC, PATCH] 1/5 rcu lock update:
1030Add per-cpu batch counter"
1031,month="May"
1032,year="2004"
1033,note="Available:
1034\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=108551764515332&w=2}
1035[Viewed June 23, 2004]"
1036,annotation={
1037 RCU runs reasonably on a 512-CPU SGI using Manfred Spraul's patches,
1038 which may be found at:
1039 https://lkml.org/lkml/2004/5/20/49 (split vars into cachelines)
1040 https://lkml.org/lkml/2004/5/22/114 (cpu_quiet() patch)
1041 https://lkml.org/lkml/2004/5/25/24 (0/5)
1042 https://lkml.org/lkml/2004/5/25/23 (1/5)
1043 https://lkml.org/lkml/2004/5/25/265 (works for Jack)
1044 https://lkml.org/lkml/2004/5/25/20 (2/5)
1045 https://lkml.org/lkml/2004/5/25/22 (3/5)
1046 https://lkml.org/lkml/2004/5/25/19 (4/5)
1047 https://lkml.org/lkml/2004/5/25/21 (5/5)
1048}
1049}
1050
1051@Conference{Sarma04c
1052,Author="Dipankar Sarma and Paul E. McKenney"
1053,Title="Making {RCU} Safe for Deep Sub-Millisecond Response
1054Realtime Applications"
1055,Booktitle="Proceedings of the 2004 USENIX Annual Technical Conference
1056(FREENIX Track)"
1057,Publisher="USENIX Association"
1058,year="2004"
1059,month="June"
1060,pages="182-191"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001061,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001062 Describes and compares a number of modifications to the Linux RCU
1063 implementation that make it friendly to realtime applications.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001064 https://www.usenix.org/conference/2004-usenix-annual-technical-conference/making-rcu-safe-deep-sub-millisecond-response
1065 [Viewed July 26, 2012]
1066}
Linus Torvalds1da177e2005-04-16 15:20:36 -07001067}
1068
Paul E. McKenneye4696a12014-02-15 08:52:32 -08001069@article{MagedMichael04a
1070,author="Maged M. Michael"
1071,title="Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects"
1072,Year="2004"
1073,Month="June"
1074,journal="IEEE Transactions on Parallel and Distributed Systems"
1075,volume="15"
1076,number="6"
1077,pages="491-504"
1078,url="Available:
1079\url{http://www.research.ibm.com/people/m/michael/ieeetpds-2004.pdf}
1080[Viewed March 1, 2005]"
1081,annotation={
1082 New canonical hazard-pointer citation.
1083}
1084}
1085
Linus Torvalds1da177e2005-04-16 15:20:36 -07001086@phdthesis{PaulEdwardMcKenneyPhD
1087,author="Paul E. McKenney"
1088,title="Exploiting Deferred Destruction:
1089An Analysis of Read-Copy-Update Techniques
1090in Operating System Kernels"
1091,school="OGI School of Science and Engineering at
1092Oregon Health and Sciences University"
1093,year="2004"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001094,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001095 Describes RCU implementations and presents design patterns
1096 corresponding to common uses of RCU in several operating-system
1097 kernels.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001098 http://www.rdrop.com/users/paulmck/RCU/RCUdissertation.2004.07.14e1.pdf
1099 [Viewed October 15, 2004]
1100}
Linus Torvalds1da177e2005-04-16 15:20:36 -07001101}
1102
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001103@unpublished{PaulEMcKenney2004rcu:dereference
1104,Author="Dipankar Sarma"
1105,Title="{Re: RCU : Abstracted RCU dereferencing [5/5]}"
1106,month="August"
Linus Torvalds1da177e2005-04-16 15:20:36 -07001107,year="2004"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001108,note="Available:
1109\url{http://lkml.org/lkml/2004/8/6/237}
1110[Viewed June 8, 2010]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001111,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001112 Introduce rcu_dereference().
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001113}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001114}
1115
1116@unpublished{JimHouston04a
1117,Author="Jim Houston"
1118,Title="{[RFC\&PATCH] Alternative {RCU} implementation}"
1119,month="August"
1120,year="2004"
1121,note="Available:
1122\url{http://lkml.org/lkml/2004/8/30/87}
1123[Viewed February 17, 2005]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001124,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001125 Uses active code in rcu_read_lock() and rcu_read_unlock() to
1126 make RCU happen, allowing RCU to function on CPUs that do not
1127 receive a scheduling-clock interrupt.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001128}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001129}
1130
1131@unpublished{TomHart04a
1132,Author="Thomas E. Hart"
1133,Title="Master's Thesis: Applying Lock-free Techniques to the {Linux} Kernel"
1134,month="October"
1135,year="2004"
1136,note="Available:
1137\url{http://www.cs.toronto.edu/~tomhart/masters_thesis.html}
1138[Viewed October 15, 2004]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001139,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001140 Proposes comparing RCU to lock-free methods for the Linux kernel.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001141}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001142}
1143
1144@unpublished{Vaddagiri04a
1145,Author="Srivatsa Vaddagiri"
1146,Title="Subject: [RFC] Use RCU for tcp\_ehash lookup"
1147,month="October"
1148,year="2004"
1149,note="Available:
1150\url{http://marc.theaimsgroup.com/?t=109395731700004&r=1&w=2}
1151[Viewed October 18, 2004]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001152,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001153 Srivatsa's RCU patch for tcp_ehash lookup.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001154}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001155}
1156
1157@unpublished{Thirumalai04a
1158,Author="Ravikiran Thirumalai"
1159,Title="Subject: [patchset] Lockfree fd lookup 0 of 5"
1160,month="October"
1161,year="2004"
1162,note="Available:
1163\url{http://marc.theaimsgroup.com/?t=109144217400003&r=1&w=2}
1164[Viewed October 18, 2004]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001165,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001166 Ravikiran's lockfree FD patch.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001167}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001168}
1169
1170@unpublished{Thirumalai04b
1171,Author="Ravikiran Thirumalai"
1172,Title="Subject: Re: [patchset] Lockfree fd lookup 0 of 5"
1173,month="October"
1174,year="2004"
1175,note="Available:
1176\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=109152521410459&w=2}
1177[Viewed October 18, 2004]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001178,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001179 Ravikiran's lockfree FD patch.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001180}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001181}
1182
1183@unpublished{PaulEMcKenney2004rcu:assign:pointer
1184,Author="Paul E. McKenney"
1185,Title="{[PATCH 1/3] RCU: \url{rcu_assign_pointer()} removal of memory barriers}"
1186,month="October"
1187,year="2004"
1188,note="Available:
1189\url{http://lkml.org/lkml/2004/10/23/241}
1190[Viewed June 8, 2010]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001191,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001192 Introduce rcu_assign_pointer().
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001193}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001194}
1195
1196@unpublished{JamesMorris04a
1197,Author="James Morris"
1198,Title="{[PATCH 2/3] SELinux} scalability - convert {AVC} to {RCU}"
1199,day="15"
1200,month="November"
1201,year="2004"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001202,note="\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=110054979416004&w=2}"
1203,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001204 James Morris posts Kaigai Kohei's patch to LKML.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001205 [Viewed December 10, 2004]
1206 Kaigai's patch is at https://lkml.org/lkml/2004/9/27/52
1207}
Linus Torvalds1da177e2005-04-16 15:20:36 -07001208}
Paul E. McKenneya83f1fe2005-05-01 08:59:05 -07001209
1210@unpublished{JamesMorris04b
1211,Author="James Morris"
1212,Title="Recent Developments in {SELinux} Kernel Performance"
1213,month="December"
1214,year="2004"
1215,note="Available:
1216\url{http://www.livejournal.com/users/james_morris/2153.html}
1217[Viewed December 10, 2004]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001218,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001219 RCU helps SELinux performance. ;-) Made LWN.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001220}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001221}
1222
1223@unpublished{PaulMcKenney2005RCUSemantics
1224,Author="Paul E. McKenney and Jonathan Walpole"
1225,Title="{RCU} Semantics: A First Attempt"
1226,month="January"
1227,year="2005"
1228,day="30"
1229,note="Available:
1230\url{http://www.rdrop.com/users/paulmck/RCU/rcu-semantics.2005.01.30a.pdf}
1231[Viewed December 6, 2009]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001232,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001233 Early derivation of RCU semantics.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001234}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001235}
1236
1237@unpublished{PaulMcKenney2005e
1238,Author="Paul E. McKenney"
1239,Title="Real-Time Preemption and {RCU}"
1240,month="March"
1241,year="2005"
1242,day="17"
1243,note="Available:
1244\url{http://lkml.org/lkml/2005/3/17/199}
1245[Viewed September 5, 2005]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001246,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001247 First posting showing how RCU can be safely adapted for
1248 preemptable RCU read side critical sections.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001249}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001250}
1251
1252@unpublished{EsbenNeilsen2005a
1253,Author="Esben Neilsen"
1254,Title="Re: Real-Time Preemption and {RCU}"
1255,month="March"
1256,year="2005"
1257,day="18"
1258,note="Available:
1259\url{http://lkml.org/lkml/2005/3/18/122}
1260[Viewed March 30, 2006]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001261,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001262 Esben Neilsen suggests read-side suppression of grace-period
1263 processing for crude-but-workable realtime RCU. The downside
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001264 is indefinite grace periods... But this is OK for experimentation
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001265 and testing.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001266}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001267}
1268
1269@unpublished{TomHart05a
1270,Author="Thomas E. Hart and Paul E. McKenney and Angela Demke Brown"
1271,Title="Efficient Memory Reclamation is Necessary for Fast Lock-Free
1272Data Structures"
1273,month="March"
1274,year="2005"
1275,note="Available:
1276\url{ftp://ftp.cs.toronto.edu/csrg-technical-reports/515/}
1277[Viewed March 4, 2005]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001278,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001279 Comparison of RCU, QBSR, and EBSR. RCU wins for read-mostly
1280 workloads. ;-)
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001281}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001282}
1283
1284@unpublished{JonCorbet2005DeprecateSyncKernel
1285,Author="Jonathan Corbet"
1286,Title="API change: synchronize_kernel() deprecated"
1287,month="May"
1288,day="3"
1289,year="2005"
1290,note="Available:
1291\url{http://lwn.net/Articles/134484/}
1292[Viewed May 3, 2005]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001293,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001294 Jon Corbet describes deprecation of synchronize_kernel()
1295 in favor of synchronize_rcu() and synchronize_sched().
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001296}
Paul E. McKenneya83f1fe2005-05-01 08:59:05 -07001297}
Paul E. McKenneydd81eca2005-09-10 00:26:24 -07001298
1299@unpublished{PaulMcKenney05a
1300,Author="Paul E. McKenney"
1301,Title="{[RFC]} {RCU} and {CONFIG\_PREEMPT\_RT} progress"
1302,month="May"
1303,year="2005"
1304,note="Available:
1305\url{http://lkml.org/lkml/2005/5/9/185}
1306[Viewed May 13, 2005]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001307,annotation={
Paul E. McKenneydd81eca2005-09-10 00:26:24 -07001308 First publication of working lock-based deferred free patches
1309 for the CONFIG_PREEMPT_RT environment.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001310}
Paul E. McKenneydd81eca2005-09-10 00:26:24 -07001311}
1312
1313@conference{PaulMcKenney05b
1314,Author="Paul E. McKenney and Dipankar Sarma"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001315,Title="Towards Hard Realtime Response from the {Linux} Kernel on {SMP} Hardware"
Paul E. McKenneydd81eca2005-09-10 00:26:24 -07001316,Booktitle="linux.conf.au 2005"
1317,month="April"
1318,year="2005"
1319,address="Canberra, Australia"
1320,note="Available:
1321\url{http://www.rdrop.com/users/paulmck/RCU/realtimeRCU.2005.04.23a.pdf}
1322[Viewed May 13, 2005]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001323,annotation={
Paul E. McKenneydd81eca2005-09-10 00:26:24 -07001324 Realtime turns into making RCU yet more realtime friendly.
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001325 http://lca2005.linux.org.au/Papers/Paul%20McKenney/Towards%20Hard%20Realtime%20Response%20from%20the%20Linux%20Kernel/LKS.2005.04.22a.pdf
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001326}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001327}
1328
1329@unpublished{PaulEMcKenneyHomePage
1330,Author="Paul E. McKenney"
1331,Title="{Paul} {E.} {McKenney}"
1332,month="May"
1333,year="2005"
1334,note="Available:
1335\url{http://www.rdrop.com/users/paulmck/}
1336[Viewed May 25, 2005]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001337,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001338 Paul McKenney's home page.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001339}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001340}
1341
1342@unpublished{PaulEMcKenneyRCUPage
1343,Author="Paul E. McKenney"
1344,Title="Read-Copy Update {(RCU)}"
1345,month="May"
1346,year="2005"
1347,note="Available:
1348\url{http://www.rdrop.com/users/paulmck/RCU}
1349[Viewed May 25, 2005]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001350,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001351 Paul McKenney's RCU page.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001352}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001353}
1354
1355@unpublished{JosephSeigh2005a
1356,Author="Joseph Seigh"
1357,Title="{RCU}+{SMR} (hazard pointers)"
1358,month="July"
1359,year="2005"
1360,note="Personal communication"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001361,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001362 Joe Seigh announcing his atomic-ptr-plus project.
1363 http://sourceforge.net/projects/atomic-ptr-plus/
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001364}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001365}
1366
1367@unpublished{JosephSeigh2005b
1368,Author="Joseph Seigh"
1369,Title="Lock-free synchronization primitives"
1370,month="July"
1371,day="6"
1372,year="2005"
1373,note="Available:
1374\url{http://sourceforge.net/projects/atomic-ptr-plus/}
1375[Viewed August 8, 2005]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001376,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001377 Joe Seigh's atomic-ptr-plus project.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001378}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001379}
1380
1381@unpublished{PaulMcKenney2005c
1382,Author="Paul E.McKenney"
1383,Title="{[RFC,PATCH] RCU} and {CONFIG\_PREEMPT\_RT} sane patch"
1384,month="August"
1385,day="1"
1386,year="2005"
1387,note="Available:
1388\url{http://lkml.org/lkml/2005/8/1/155}
1389[Viewed March 14, 2006]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001390,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001391 First operating counter-based realtime RCU patch posted to LKML.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001392}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001393}
1394
1395@unpublished{PaulMcKenney2005d
1396,Author="Paul E. McKenney"
1397,Title="Re: [Fwd: Re: [patch] Real-Time Preemption, -RT-2.6.13-rc4-V0.7.52-01]"
1398,month="August"
1399,day="8"
1400,year="2005"
1401,note="Available:
1402\url{http://lkml.org/lkml/2005/8/8/108}
1403[Viewed March 14, 2006]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001404,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001405 First operating counter-based realtime RCU patch posted to LKML,
1406 but fixed so that various unusual combinations of configuration
1407 parameters all function properly.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001408}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001409}
1410
1411@unpublished{PaulMcKenney2005rcutorture
1412,Author="Paul E. McKenney"
1413,Title="{[PATCH]} {RCU} torture testing"
1414,month="October"
1415,day="1"
1416,year="2005"
1417,note="Available:
1418\url{http://lkml.org/lkml/2005/10/1/70}
1419[Viewed March 14, 2006]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001420,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001421 First rcutorture patch.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001422}
1423}
1424
1425@unpublished{DavidSMiller2006HashedLocking
1426,Author="David S. Miller"
1427,Title="Re: [{PATCH}, {RFC}] {RCU} : {OOM} avoidance and lower latency"
1428,month="January"
1429,day="6"
1430,year="2006"
1431,note="Available:
1432\url{https://lkml.org/lkml/2006/1/7/22}
1433[Viewed February 29, 2012]"
1434,annotation={
1435 David Miller's view on hashed arrays of locks: used to really
1436 like it, but time he saw an opportunity for this technique,
1437 something else always proved superior. Partitioning or RCU. ;-)
1438}
Paul E. McKenneydd81eca2005-09-10 00:26:24 -07001439}
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +01001440
1441@conference{ThomasEHart2006a
1442,Author="Thomas E. Hart and Paul E. McKenney and Angela Demke Brown"
1443,Title="Making Lockless Synchronization Fast: Performance Implications
1444of Memory Reclamation"
1445,Booktitle="20\textsuperscript{th} {IEEE} International Parallel and
1446Distributed Processing Symposium"
1447,month="April"
1448,year="2006"
1449,day="25-29"
1450,address="Rhodes, Greece"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001451,note="Available:
1452\url{http://www.rdrop.com/users/paulmck/RCU/hart_ipdps06.pdf}
1453[Viewed April 28, 2008]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001454,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001455 Compares QSBR, HPBR, EBR, and lock-free reference counting.
1456 http://www.cs.toronto.edu/~tomhart/perflab/ipdps06.tgz
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001457}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001458}
1459
1460@unpublished{NickPiggin2006radixtree
1461,Author="Nick Piggin"
1462,Title="[patch 3/3] radix-tree: {RCU} lockless readside"
1463,month="June"
1464,day="20"
1465,year="2006"
1466,note="Available:
1467\url{http://lkml.org/lkml/2006/6/20/238}
1468[Viewed March 25, 2008]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001469,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001470 RCU-protected radix tree.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001471}
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +01001472}
1473
1474@Conference{PaulEMcKenney2006b
1475,Author="Paul E. McKenney and Dipankar Sarma and Ingo Molnar and
1476Suparna Bhattacharya"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001477,Title="Extending {RCU} for Realtime and Embedded Workloads"
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +01001478,Booktitle="{Ottawa Linux Symposium}"
1479,Month="July"
1480,Year="2006"
1481,pages="v2 123-138"
1482,note="Available:
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001483\url{http://www.linuxsymposium.org/2006/view_abstract.php?content_key=184}
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +01001484\url{http://www.rdrop.com/users/paulmck/RCU/OLSrtRCU.2006.08.11a.pdf}
1485[Viewed January 1, 2007]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001486,annotation={
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +01001487 Described how to improve the -rt implementation of realtime RCU.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001488}
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +01001489}
1490
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001491@unpublished{WikipediaRCU
1492,Author="Paul E. McKenney and Chris Purcell and Algae and Ben Schumin and
1493Gaius Cornelius and Qwertyus and Neil Conway and Sbw and Blainster and
1494Canis Rufus and Zoicon5 and Anome and Hal Eisen"
1495,Title="Read-Copy Update"
1496,month="July"
1497,day="8"
1498,year="2006"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001499,note="\url{http://en.wikipedia.org/wiki/Read-copy-update}"
1500,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001501 Wikipedia RCU page as of July 8 2006.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001502 [Viewed August 21, 2006]
1503}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001504}
1505
1506@Conference{NickPiggin2006LocklessPageCache
1507,Author="Nick Piggin"
1508,Title="A Lockless Pagecache in Linux---Introduction, Progress, Performance"
1509,Booktitle="{Ottawa Linux Symposium}"
1510,Month="July"
1511,Year="2006"
1512,pages="v2 249-254"
1513,note="Available:
1514\url{http://www.linuxsymposium.org/2006/view_abstract.php?content_key=184}
1515[Viewed January 11, 2009]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001516,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001517 Uses RCU-protected radix tree for a lockless page cache.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001518}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001519}
1520
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +01001521@unpublished{PaulEMcKenney2006c
1522,Author="Paul E. McKenney"
1523,Title="Sleepable {RCU}"
1524,month="October"
1525,day="9"
1526,year="2006"
1527,note="Available:
1528\url{http://lwn.net/Articles/202847/}
1529Revised:
1530\url{http://www.rdrop.com/users/paulmck/RCU/srcu.2007.01.14a.pdf}
1531[Viewed August 21, 2006]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001532,annotation={
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +01001533 LWN article introducing SRCU.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001534}
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +01001535}
1536
1537@unpublished{RobertOlsson2006a
1538,Author="Robert Olsson and Stefan Nilsson"
1539,Title="{TRASH}: A dynamic {LC}-trie and hash data structure"
1540,month="August"
1541,day="18"
1542,year="2006"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001543,note="\url{http://www.nada.kth.se/~snilsson/publications/TRASH/trash.pdf}"
1544,annotation={
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +01001545 RCU-protected dynamic trie-hash combination.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001546 [Viewed March 4, 2011]
1547}
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +01001548}
1549
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001550@unpublished{ChristophHellwig2006RCU2SRCU
1551,Author="Christoph Hellwig"
1552,Title="Re: {[-mm PATCH 1/4]} {RCU}: split classic rcu"
1553,month="September"
1554,day="28"
1555,year="2006"
1556,note="Available:
1557\url{http://lkml.org/lkml/2006/9/28/160}
1558[Viewed March 27, 2008]"
1559}
1560
1561@unpublished{PaulEMcKenneyRCUusagePage
1562,Author="Paul E. McKenney"
1563,Title="{RCU} {Linux} Usage"
1564,month="October"
1565,year="2006"
1566,note="Available:
1567\url{http://www.rdrop.com/users/paulmck/RCU/linuxusage.html}
1568[Viewed January 14, 2007]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001569,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001570 Paul McKenney's RCU page showing graphs plotting Linux-kernel
1571 usage of RCU.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001572}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001573}
1574
1575@unpublished{PaulEMcKenneyRCUusageRawDataPage
1576,Author="Paul E. McKenney"
1577,Title="Read-Copy Update {(RCU)} Usage in {Linux} Kernel"
1578,month="October"
1579,year="2006"
1580,note="Available:
1581\url{http://www.rdrop.com/users/paulmck/RCU/linuxusage/rculocktab.html}
1582[Viewed January 14, 2007]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001583,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001584 Paul McKenney's RCU page showing Linux usage of RCU in tabular
1585 form, with links to corresponding cscope databases.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001586}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001587}
1588
1589@unpublished{GauthamShenoy2006RCUrwlock
1590,Author="Gautham R. Shenoy"
1591,Title="[PATCH 4/5] lock\_cpu\_hotplug: Redesign - Lightweight implementation of lock\_cpu\_hotplug"
1592,month="October"
1593,year="2006"
1594,day=26
1595,note="Available:
1596\url{http://lkml.org/lkml/2006/10/26/73}
1597[Viewed January 26, 2009]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001598,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001599 RCU-based reader-writer lock that allows readers to proceed with
1600 no memory barriers or atomic instruction in absence of writers.
1601 If writer do show up, readers must of course wait as required by
1602 the semantics of reader-writer locking. This is a recursive
1603 lock.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001604}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001605}
1606
1607@unpublished{JensAxboe2006SlowSRCU
1608,Author="Jens Axboe"
1609,Title="Re: [patch] cpufreq: mark \url{cpufreq_tsc()} as
1610\url{core_initcall_sync}"
1611,month="November"
1612,year="2006"
1613,day=17
1614,note="Available:
1615\url{http://lkml.org/lkml/2006/11/17/56}
1616[Viewed May 28, 2007]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001617,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001618 SRCU's grace periods are too slow for Jens, even after a
1619 factor-of-three speedup.
1620 Sped-up version of SRCU at http://lkml.org/lkml/2006/11/17/359.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001621}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001622}
1623
1624@unpublished{OlegNesterov2006QRCU
1625,Author="Oleg Nesterov"
1626,Title="Re: [patch] cpufreq: mark {\tt cpufreq\_tsc()} as
1627{\tt core\_initcall\_sync}"
1628,month="November"
1629,year="2006"
1630,day=19
1631,note="Available:
1632\url{http://lkml.org/lkml/2006/11/19/69}
1633[Viewed May 28, 2007]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001634,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001635 First cut of QRCU. Expanded/corrected versions followed.
1636 Used to be OlegNesterov2007QRCU, now time-corrected.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001637}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001638}
1639
1640@unpublished{OlegNesterov2006aQRCU
1641,Author="Oleg Nesterov"
1642,Title="Re: [RFC, PATCH 1/2] qrcu: {"quick"} srcu implementation"
1643,month="November"
1644,year="2006"
1645,day=30
1646,note="Available:
1647\url{http://lkml.org/lkml/2006/11/29/330}
1648[Viewed November 26, 2008]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001649,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001650 Expanded/corrected version of QRCU.
1651 Used to be OlegNesterov2007aQRCU, now time-corrected.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001652}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001653}
1654
1655@unpublished{EvgeniyPolyakov2006RCUslowdown
1656,Author="Evgeniy Polyakov"
1657,Title="Badness in postponing work"
1658,month="December"
1659,year="2006"
1660,day=05
1661,note="Available:
1662\url{http://www.ioremap.net/node/41}
1663[Viewed October 28, 2008]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001664,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001665 Using RCU as a pure delay leads to a 2.5x slowdown in skbs in
1666 the Linux kernel.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001667}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001668}
1669
1670@inproceedings{ChrisMatthews2006ClusteredObjectsRCU
1671,author = {Matthews, Chris and Coady, Yvonne and Appavoo, Jonathan}
1672,title = {Portability events: a programming model for scalable system infrastructures}
1673,booktitle = {PLOS '06: Proceedings of the 3rd workshop on Programming languages and operating systems}
1674,year = {2006}
1675,isbn = {1-59593-577-0}
1676,pages = {11}
1677,location = {San Jose, California}
1678,doi = {http://doi.acm.org/10.1145/1215995.1216006}
1679,publisher = {ACM}
1680,address = {New York, NY, USA}
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +01001681,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001682 Uses K42's RCU-like functionality to manage clustered-object
1683 lifetimes.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001684}
1685}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001686
1687@article{DilmaDaSilva2006K42
1688,author = {Silva, Dilma Da and Krieger, Orran and Wisniewski, Robert W. and Waterland, Amos and Tam, David and Baumann, Andrew}
1689,title = {K42: an infrastructure for operating system research}
1690,journal = {SIGOPS Oper. Syst. Rev.}
1691,volume = {40}
1692,number = {2}
1693,year = {2006}
1694,issn = {0163-5980}
1695,pages = {34--42}
1696,doi = {http://doi.acm.org/10.1145/1131322.1131333}
1697,publisher = {ACM}
1698,address = {New York, NY, USA}
1699,annotation={
1700 Describes relationship of K42 generations to RCU.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001701}
1702}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001703
1704# CoreyMinyard2007list_splice_rcu
1705@unpublished{CoreyMinyard2007list:splice:rcu
1706,Author="Corey Minyard and Paul E. McKenney"
1707,Title="{[PATCH]} add an {RCU} version of list splicing"
1708,month="January"
1709,year="2007"
1710,day=3
1711,note="Available:
1712\url{http://lkml.org/lkml/2007/1/3/112}
1713[Viewed May 28, 2007]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001714,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001715 Patch for list_splice_rcu().
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001716}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001717}
1718
1719@unpublished{PaulEMcKenney2007rcubarrier
1720,Author="Paul E. McKenney"
1721,Title="{RCU} and Unloadable Modules"
1722,month="January"
1723,day="14"
1724,year="2007"
1725,note="Available:
1726\url{http://lwn.net/Articles/217484/}
1727[Viewed November 22, 2007]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001728,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001729 LWN article introducing the rcu_barrier() primitive.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001730}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001731}
1732
1733@unpublished{PeterZijlstra2007SyncBarrier
1734,Author="Peter Zijlstra and Ingo Molnar"
1735,Title="{[PATCH 3/7]} barrier: a scalable synchonisation barrier"
1736,month="January"
1737,year="2007"
1738,day=28
1739,note="Available:
1740\url{http://lkml.org/lkml/2007/1/28/34}
1741[Viewed March 27, 2008]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001742,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001743 RCU-like implementation for frequent updaters and rare readers(!).
1744 Subsumed into QRCU. Maybe...
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001745}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001746}
1747
1748@unpublished{PaulEMcKenney2007BoostRCU
1749,Author="Paul E. McKenney"
1750,Title="Priority-Boosting {RCU} Read-Side Critical Sections"
1751,month="February"
1752,day="5"
1753,year="2007"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001754,note="\url{http://lwn.net/Articles/220677/}"
1755,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001756 LWN article introducing RCU priority boosting.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001757 Revised:
1758 http://www.rdrop.com/users/paulmck/RCU/RCUbooststate.2007.04.16a.pdf
1759 [Viewed September 7, 2007]
1760}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001761}
1762
1763@unpublished{PaulMcKenney2007QRCUpatch
1764,Author="Paul E. McKenney"
1765,Title="{[PATCH]} {QRCU} with lockless fastpath"
1766,month="February"
1767,year="2007"
1768,day=24
1769,note="Available:
1770\url{http://lkml.org/lkml/2007/2/25/18}
1771[Viewed March 27, 2008]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001772,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001773 Patch for QRCU supplying lock-free fast path.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001774}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001775}
1776
1777@article{JonathanAppavoo2007K42RCU
1778,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}
1779,title = {Experience distributing objects in an SMMP OS}
1780,journal = {ACM Trans. Comput. Syst.}
1781,volume = {25}
1782,number = {3}
1783,year = {2007}
1784,issn = {0734-2071}
1785,pages = {6/1--6/52}
1786,doi = {http://doi.acm.org/10.1145/1275517.1275518}
1787,publisher = {ACM}
1788,address = {New York, NY, USA}
1789,annotation={
1790 Role of RCU in K42.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001791}
1792}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001793
1794@conference{RobertOlsson2007Trash
1795,Author="Robert Olsson and Stefan Nilsson"
1796,Title="{TRASH}: A dynamic {LC}-trie and hash data structure"
1797,booktitle="Workshop on High Performance Switching and Routing (HPSR'07)"
1798,month="May"
1799,year="2007"
1800,note="Available:
1801\url{http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4281239}
1802[Viewed October 1, 2010]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001803,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001804 RCU-protected dynamic trie-hash combination.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001805}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001806}
1807
1808@conference{PeterZijlstra2007ConcurrentPagecacheRCU
1809,Author="Peter Zijlstra"
1810,Title="Concurrent Pagecache"
1811,Booktitle="Linux Symposium"
1812,month="June"
1813,year="2007"
1814,address="Ottawa, Canada"
1815,note="Available:
1816\url{http://ols.108.redhat.com/2007/Reprints/zijlstra-Reprint.pdf}
1817[Viewed April 14, 2008]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001818,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001819 Page-cache modifications permitting RCU readers and concurrent
1820 updates.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001821}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001822}
1823
1824@unpublished{PaulEMcKenney2007whatisRCU
1825,Author="Paul E. McKenney"
1826,Title="What is {RCU}?"
1827,year="2007"
1828,month="07"
1829,note="Available:
1830\url{http://www.rdrop.com/users/paulmck/RCU/whatisRCU.html}
1831[Viewed July 6, 2007]"
1832,annotation={
1833 Describes RCU in Linux kernel.
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +01001834}
1835}
1836
1837@unpublished{PaulEMcKenney2007QRCUspin
1838,Author="Paul E. McKenney"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001839,Title="Using {Promela} and {Spin} to verify parallel algorithms"
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +01001840,month="August"
1841,day="1"
1842,year="2007"
1843,note="Available:
1844\url{http://lwn.net/Articles/243851/}
1845[Viewed September 8, 2007]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001846,annotation={
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +01001847 LWN article describing Promela and spin, and also using Oleg
1848 Nesterov's QRCU as an example (with Paul McKenney's fastpath).
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001849 Merged patch at: http://lkml.org/lkml/2007/2/25/18
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001850}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001851}
1852
1853@unpublished{PaulEMcKenney2007WG21DDOatomics
1854,Author="Paul E. McKenney and Hans-J. Boehm and Lawrence Crowl"
1855,Title="C++ Data-Dependency Ordering: Atomics and Memory Model"
1856,month="August"
1857,day="3"
1858,year="2007"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001859,note="Available:
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001860\url{http://open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2664.htm}
1861[Viewed December 7, 2009]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001862,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001863 RCU for C++, parts 1 and 2.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001864}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001865}
1866
1867@unpublished{PaulEMcKenney2007WG21DDOannotation
1868,Author="Paul E. McKenney and Lawrence Crowl"
1869,Title="C++ Data-Dependency Ordering: Function Annotation"
1870,month="September"
1871,day="18"
1872,year="2008"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001873,note="Available:
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001874\url{http://open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2782.htm}
1875[Viewed December 7, 2009]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001876,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001877 RCU for C++, part 2, updated many times.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001878}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001879}
1880
1881@unpublished{PaulEMcKenney2007PreemptibleRCUPatch
1882,Author="Paul E. McKenney"
1883,Title="[PATCH RFC 0/9] {RCU}: Preemptible {RCU}"
1884,month="September"
1885,day="10"
1886,year="2007"
1887,note="Available:
1888\url{http://lkml.org/lkml/2007/9/10/213}
1889[Viewed October 25, 2007]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001890,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001891 Final patch for preemptable RCU to -rt. (Later patches were
1892 to mainline, eventually incorporated.)
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001893}
Paul E. McKenneyf85d6c72008-01-25 21:08:25 +01001894}
1895
Paul E. McKenney32300752008-05-12 21:21:05 +02001896@unpublished{PaulEMcKenney2007PreemptibleRCU
1897,Author="Paul E. McKenney"
1898,Title="The design of preemptible read-copy-update"
1899,month="October"
1900,day="8"
1901,year="2007"
1902,note="Available:
1903\url{http://lwn.net/Articles/253651/}
1904[Viewed October 25, 2007]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001905,annotation={
Paul E. McKenney32300752008-05-12 21:21:05 +02001906 LWN article describing the design of preemptible RCU.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001907}
Paul E. McKenney32300752008-05-12 21:21:05 +02001908}
1909
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001910@article{ThomasEHart2007a
1911,Author="Thomas E. Hart and Paul E. McKenney and Angela Demke Brown and Jonathan Walpole"
1912,Title="Performance of memory reclamation for lockless synchronization"
1913,journal="J. Parallel Distrib. Comput."
1914,volume={67}
1915,number="12"
1916,year="2007"
1917,issn="0743-7315"
1918,pages="1270--1285"
1919,doi="http://dx.doi.org/10.1016/j.jpdc.2007.04.010"
1920,publisher="Academic Press, Inc."
1921,address="Orlando, FL, USA"
1922,annotation={
1923 Compares QSBR, HPBR, EBR, and lock-free reference counting.
1924 Journal version of ThomasEHart2006a.
1925}
1926}
1927
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001928# MathieuDesnoyers2007call_rcu_schedNeeded
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001929@unpublished{MathieuDesnoyers2007call:rcu:schedNeeded
1930,Author="Mathieu Desnoyers"
1931,Title="Re: [patch 1/2] {Linux} Kernel Markers - Support Multiple Probes"
1932,month="December"
1933,day="20"
1934,year="2007"
1935,note="Available:
1936\url{http://lkml.org/lkml/2007/12/20/244}
1937[Viewed March 27, 2008]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001938,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001939 Request for call_rcu_sched() and rcu_barrier_sched().
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001940}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001941}
1942
1943
Paul E. McKenney32300752008-05-12 21:21:05 +02001944########################################################################
1945#
1946# "What is RCU?" LWN series.
1947#
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001948# http://lwn.net/Articles/262464/ (What is RCU, Fundamentally?)
1949# http://lwn.net/Articles/263130/ (What is RCU's Usage?)
1950# http://lwn.net/Articles/264090/ (What is RCU's API?)
Paul E. McKenney32300752008-05-12 21:21:05 +02001951
1952@unpublished{PaulEMcKenney2007WhatIsRCUFundamentally
1953,Author="Paul E. McKenney and Jonathan Walpole"
1954,Title="What is {RCU}, Fundamentally?"
1955,month="December"
1956,day="17"
1957,year="2007"
1958,note="Available:
1959\url{http://lwn.net/Articles/262464/}
1960[Viewed December 27, 2007]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001961,annotation={
Paul E. McKenney32300752008-05-12 21:21:05 +02001962 Lays out the three basic components of RCU: (1) publish-subscribe,
1963 (2) wait for pre-existing readers to complete, and (2) maintain
1964 multiple versions.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001965}
Paul E. McKenney32300752008-05-12 21:21:05 +02001966}
1967
1968@unpublished{PaulEMcKenney2008WhatIsRCUUsage
1969,Author="Paul E. McKenney"
1970,Title="What is {RCU}? Part 2: Usage"
1971,month="January"
1972,day="4"
1973,year="2008"
1974,note="Available:
1975\url{http://lwn.net/Articles/263130/}
1976[Viewed January 4, 2008]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001977,annotation={
Paul E. McKenney32300752008-05-12 21:21:05 +02001978 Lays out six uses of RCU:
1979 1. RCU is a Reader-Writer Lock Replacement
1980 2. RCU is a Restricted Reference-Counting Mechanism
1981 3. RCU is a Bulk Reference-Counting Mechanism
1982 4. RCU is a Poor Man's Garbage Collector
1983 5. RCU is a Way of Providing Existence Guarantees
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08001984 6. RCU is a Way of Waiting for Things to Finish
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001985}
Paul E. McKenney32300752008-05-12 21:21:05 +02001986}
1987
1988@unpublished{PaulEMcKenney2008WhatIsRCUAPI
1989,Author="Paul E. McKenney"
1990,Title="{RCU} part 3: the {RCU} {API}"
1991,month="January"
1992,day="17"
1993,year="2008"
1994,note="Available:
1995\url{http://lwn.net/Articles/264090/}
1996[Viewed January 10, 2008]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07001997,annotation={
Paul E. McKenney32300752008-05-12 21:21:05 +02001998 Gives an overview of the Linux-kernel RCU API and a brief annotated RCU
1999 bibliography.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002000}
Paul E. McKenney32300752008-05-12 21:21:05 +02002001}
2002
Paul E. McKenney4c540052010-01-14 16:10:57 -08002003#
2004# "What is RCU?" LWN series.
2005#
2006########################################################################
2007
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002008
2009@unpublished{SteveRostedt2008dyntickRCUpatch
2010,Author="Steven Rostedt and Paul E. McKenney"
2011,Title="{[PATCH]} add support for dynamic ticks and preempt rcu"
2012,month="January"
2013,day="29"
2014,year="2008"
2015,note="Available:
2016\url{http://lkml.org/lkml/2008/1/29/208}
2017[Viewed March 27, 2008]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002018,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002019 Patch that prevents preemptible RCU from unnecessarily waking
2020 up dynticks-idle CPUs.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002021}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002022}
2023
2024@unpublished{PaulEMcKenney2008LKMLDependencyOrdering
2025,Author="Paul E. McKenney"
2026,Title="Re: [PATCH 02/22 -v7] Add basic support for gcc profiler instrumentation"
2027,month="February"
2028,day="1"
2029,year="2008"
2030,note="Available:
2031\url{http://lkml.org/lkml/2008/2/2/255}
2032[Viewed October 18, 2008]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002033,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002034 Explanation of compilers violating dependency ordering.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002035}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002036}
2037
2038@Conference{PaulEMcKenney2008Beijing
2039,Author="Paul E. McKenney"
2040,Title="Introducing Technology Into {Linux} Or:
2041Introducing your technology Into {Linux} will require introducing a
2042lot of {Linux} into your technology!!!"
2043,Booktitle="2008 Linux Developer Symposium - China"
2044,Publisher="OSS China"
2045,Month="February"
2046,Year="2008"
2047,Address="Beijing, China"
2048,note="Available:
2049\url{http://www.rdrop.com/users/paulmck/RCU/TechIntroLinux.2008.02.19a.pdf}
2050[Viewed August 12, 2008]"
2051}
2052
2053@unpublished{PaulEMcKenney2008dynticksRCU
2054,Author="Paul E. McKenney and Steven Rostedt"
2055,Title="Integrating and Validating dynticks and Preemptable RCU"
2056,month="April"
2057,day="24"
2058,year="2008"
2059,note="Available:
2060\url{http://lwn.net/Articles/279077/}
2061[Viewed April 24, 2008]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002062,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002063 Describes use of Promela and Spin to validate (and fix!) the
2064 dynticks/RCU interface.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002065}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002066}
2067
Paul E. McKenney32300752008-05-12 21:21:05 +02002068@article{DinakarGuniguntala2008IBMSysJ
2069,author="D. Guniguntala and P. E. McKenney and J. Triplett and J. Walpole"
2070,title="The read-copy-update mechanism for supporting real-time applications on shared-memory multiprocessor systems with {Linux}"
2071,Year="2008"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002072,Month="May"
Paul E. McKenney32300752008-05-12 21:21:05 +02002073,journal="IBM Systems Journal"
2074,volume="47"
2075,number="2"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002076,pages="221-236"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002077,annotation={
Paul E. McKenney32300752008-05-12 21:21:05 +02002078 RCU, realtime RCU, sleepable RCU, performance.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002079 http://www.research.ibm.com/journal/sj/472/guniguntala.pdf
2080 [Viewed April 24, 2008]
2081}
Paul E. McKenney32300752008-05-12 21:21:05 +02002082}
Paul E. McKenney240ebbf2009-06-25 09:08:18 -07002083
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002084@unpublished{LaiJiangshan2008NewClassicAlgorithm
2085,Author="Lai Jiangshan"
2086,Title="[{RFC}][{PATCH}] rcu classic: new algorithm for callbacks-processing"
2087,month="June"
2088,day="3"
2089,year="2008"
2090,note="Available:
2091\url{http://lkml.org/lkml/2008/6/2/539}
2092[Viewed December 10, 2008]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002093,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002094 Updated RCU classic algorithm. Introduced multi-tailed list
2095 for RCU callbacks and also pulling common code into
2096 __call_rcu().
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002097}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002098}
2099
Paul E. McKenney240ebbf2009-06-25 09:08:18 -07002100@article{PaulEMcKenney2008RCUOSR
2101,author="Paul E. McKenney and Jonathan Walpole"
2102,title="Introducing technology into the {Linux} kernel: a case study"
2103,Year="2008"
2104,journal="SIGOPS Oper. Syst. Rev."
2105,volume="42"
2106,number="5"
2107,pages="4--17"
2108,issn="0163-5980"
2109,doi={http://doi.acm.org/10.1145/1400097.1400099}
2110,publisher="ACM"
2111,address="New York, NY, USA"
2112,annotation={
2113 Linux changed RCU to a far greater degree than RCU has changed Linux.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002114 http://portal.acm.org/citation.cfm?doid=1400097.1400099
Paul E. McKenney240ebbf2009-06-25 09:08:18 -07002115}
2116}
2117
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002118@unpublished{ManfredSpraul2008StateMachineRCU
2119,Author="Manfred Spraul"
2120,Title="[{RFC}, {PATCH}] state machine based rcu"
2121,month="August"
2122,day="21"
2123,year="2008"
2124,note="Available:
2125\url{http://lkml.org/lkml/2008/8/21/336}
2126[Viewed December 8, 2008]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002127,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002128 State-based RCU. One key thing that this patch does is to
2129 separate the dynticks handling of NMIs and IRQs.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002130}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002131}
2132
2133@unpublished{ManfredSpraul2008dyntickIRQNMI
2134,Author="Manfred Spraul"
2135,Title="Re: [{RFC}, {PATCH}] v4 scalable classic {RCU} implementation"
2136,month="September"
2137,day="6"
2138,year="2008"
2139,note="Available:
2140\url{http://lkml.org/lkml/2008/9/6/86}
2141[Viewed December 8, 2008]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002142,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002143 Manfred notes a fix required to my attempt to separate irq
2144 and NMI processing for hierarchical RCU's dynticks interface.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002145}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002146}
2147
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002148# Was PaulEMcKenney2011cyclicRCU
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002149@techreport{PaulEMcKenney2008cyclicRCU
2150,author="Paul E. McKenney"
2151,title="Efficient Support of Consistent Cyclic Search With Read-Copy Update"
2152,institution="US Patent and Trademark Office"
2153,address="Washington, DC"
2154,year="2008"
2155,number="US Patent 7,426,511"
2156,month="September"
2157,pages="23"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002158,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002159 Maintains an additional level of indirection to allow
2160 readers to confine themselves to the desired snapshot of the
2161 data structure. Only permits one update at a time.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002162}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002163}
2164
Paul E. McKenney240ebbf2009-06-25 09:08:18 -07002165@unpublished{PaulEMcKenney2008HierarchicalRCU
2166,Author="Paul E. McKenney"
2167,Title="Hierarchical {RCU}"
2168,month="November"
2169,day="3"
2170,year="2008"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002171,note="\url{http://lwn.net/Articles/305782/}"
2172,annotation={
Paul E. McKenney240ebbf2009-06-25 09:08:18 -07002173 RCU with combining-tree-based grace-period detection,
2174 permitting it to handle thousands of CPUs.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002175 [Viewed November 6, 2008]
2176}
Paul E. McKenney240ebbf2009-06-25 09:08:18 -07002177}
2178
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002179@unpublished{PaulEMcKenney2009BloatwatchRCU
2180,Author="Paul E. McKenney"
2181,Title="Re: [PATCH fyi] RCU: the bloatwatch edition"
2182,month="January"
2183,day="14"
2184,year="2009"
2185,note="Available:
2186\url{http://lkml.org/lkml/2009/1/14/449}
2187[Viewed January 15, 2009]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002188,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002189 Small-footprint implementation of RCU for uniprocessor
2190 embedded applications -- and also for exposition purposes.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002191}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002192}
2193
Paul E. McKenney240ebbf2009-06-25 09:08:18 -07002194@conference{PaulEMcKenney2009MaliciousURCU
2195,Author="Paul E. McKenney"
2196,Title="Using a Malicious User-Level {RCU} to Torture {RCU}-Based Algorithms"
2197,Booktitle="linux.conf.au 2009"
2198,month="January"
2199,year="2009"
2200,address="Hobart, Australia"
2201,note="Available:
2202\url{http://www.rdrop.com/users/paulmck/RCU/urcutorture.2009.01.22a.pdf}
2203[Viewed February 2, 2009]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002204,annotation={
Paul E. McKenney240ebbf2009-06-25 09:08:18 -07002205 Realtime RCU and torture-testing RCU uses.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002206}
Paul E. McKenney240ebbf2009-06-25 09:08:18 -07002207}
2208
2209@unpublished{MathieuDesnoyers2009URCU
2210,Author="Mathieu Desnoyers"
2211,Title="[{RFC} git tree] Userspace {RCU} (urcu) for {Linux}"
2212,month="February"
2213,day="5"
2214,year="2009"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002215,note="\url{http://lttng.org/urcu}"
2216,annotation={
Paul E. McKenney240ebbf2009-06-25 09:08:18 -07002217 Mathieu Desnoyers's user-space RCU implementation.
2218 git://lttng.org/userspace-rcu.git
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002219 http://lttng.org/cgi-bin/gitweb.cgi?p=userspace-rcu.git
2220 http://lttng.org/urcu
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002221 http://lkml.org/lkml/2009/2/5/572
2222}
Paul E. McKenney240ebbf2009-06-25 09:08:18 -07002223}
2224
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002225@unpublished{PaulEMcKenney2009LWNBloatWatchRCU
Paul E. McKenney240ebbf2009-06-25 09:08:18 -07002226,Author="Paul E. McKenney"
2227,Title="{RCU}: The {Bloatwatch} Edition"
2228,month="March"
2229,day="17"
2230,year="2009"
2231,note="Available:
2232\url{http://lwn.net/Articles/323929/}
2233[Viewed March 20, 2009]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002234,annotation={
Paul E. McKenney240ebbf2009-06-25 09:08:18 -07002235 Uniprocessor assumptions allow simplified RCU implementation.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002236}
2237}
2238
2239@unpublished{EvgeniyPolyakov2009EllipticsNetwork
2240,Author="Evgeniy Polyakov"
2241,Title="The Elliptics Network"
2242,month="April"
2243,day="17"
2244,year="2009"
2245,note="Available:
2246\url{http://www.ioremap.net/projects/elliptics}
2247[Viewed April 30, 2009]"
2248,annotation={
2249 Distributed hash table with transactions, using elliptic
2250 hash functions to distribute data.
2251}
Paul E. McKenney240ebbf2009-06-25 09:08:18 -07002252}
Paul E. McKenney4c540052010-01-14 16:10:57 -08002253
2254@unpublished{PaulEMcKenney2009expeditedRCU
2255,Author="Paul E. McKenney"
2256,Title="[{PATCH} -tip 0/3] expedited 'big hammer' {RCU} grace periods"
2257,month="June"
2258,day="25"
2259,year="2009"
2260,note="Available:
2261\url{http://lkml.org/lkml/2009/6/25/306}
2262[Viewed August 16, 2009]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002263,annotation={
Paul E. McKenney4c540052010-01-14 16:10:57 -08002264 First posting of expedited RCU to be accepted into -tip.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002265}
Paul E. McKenney4c540052010-01-14 16:10:57 -08002266}
2267
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002268@unpublished{PaulEMcKenney2009fastRTRCU
2269,Author="Paul E. McKenney"
2270,Title="[{PATCH} {RFC} -tip 0/4] {RCU} cleanups and simplified preemptable {RCU}"
2271,month="July"
2272,day="23"
2273,year="2009"
2274,note="Available:
2275\url{http://lkml.org/lkml/2009/7/23/294}
2276[Viewed August 15, 2009]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002277,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002278 First posting of simple and fast preemptable RCU.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002279}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002280}
2281
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002282@unpublished{JoshTriplett2009RPHash
Paul E. McKenney4c540052010-01-14 16:10:57 -08002283,Author="Josh Triplett"
2284,Title="Scalable concurrent hash tables via relativistic programming"
2285,month="September"
2286,year="2009"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002287,note="Linux Plumbers Conference presentation"
2288,annotation={
Paul E. McKenney4c540052010-01-14 16:10:57 -08002289 RP fun with hash tables.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002290 Superseded by JoshTriplett2010RPHash
2291}
Paul E. McKenney4c540052010-01-14 16:10:57 -08002292}
2293
2294@phdthesis{MathieuDesnoyersPhD
Paul E. McKenney998f2ac2010-02-22 17:04:58 -08002295, title = "Low-Impact Operating System Tracing"
Paul E. McKenney4c540052010-01-14 16:10:57 -08002296, author = "Mathieu Desnoyers"
2297, school = "Ecole Polytechnique de Montr\'{e}al"
2298, month = "December"
2299, year = 2009
Paul E. McKenney998f2ac2010-02-22 17:04:58 -08002300,note="Available:
Paul E. McKenney1bd22e32010-02-22 17:05:00 -08002301\url{http://www.lttng.org/pub/thesis/desnoyers-dissertation-2009-12.pdf}
Paul E. McKenney998f2ac2010-02-22 17:04:58 -08002302[Viewed December 9, 2009]"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002303,annotation={
2304 Chapter 6 (page 97) covers user-level RCU.
2305}
2306}
2307
2308@unpublished{RelativisticProgrammingWiki
2309,Author="Josh Triplett and Paul E. McKenney and Jonathan Walpole"
2310,Title="Relativistic Programming"
2311,month="September"
2312,year="2009"
2313,note="Available:
2314\url{http://wiki.cs.pdx.edu/rp/}
2315[Viewed December 9, 2009]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002316,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002317 Main Relativistic Programming Wiki.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002318}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002319}
2320
2321@conference{PaulEMcKenney2009DeterministicRCU
2322,Author="Paul E. McKenney"
2323,Title="Deterministic Synchronization in Multicore Systems: the Role of {RCU}"
2324,Booktitle="Eleventh Real Time Linux Workshop"
2325,month="September"
2326,year="2009"
2327,address="Dresden, Germany"
2328,note="Available:
2329\url{http://www.rdrop.com/users/paulmck/realtime/paper/DetSyncRCU.2009.08.18a.pdf}
2330[Viewed January 14, 2009]"
2331}
2332
2333@unpublished{PaulEMcKenney2009HuntingHeisenbugs
2334,Author="Paul E. McKenney"
2335,Title="Hunting Heisenbugs"
2336,month="November"
2337,year="2009"
2338,day="1"
2339,note="Available:
2340\url{http://paulmck.livejournal.com/14639.html}
2341[Viewed June 4, 2010]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002342,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002343 Day-one bug in Tree RCU that took forever to track down.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002344}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002345}
2346
2347@unpublished{MathieuDesnoyers2009defer:rcu
2348,Author="Mathieu Desnoyers"
2349,Title="Kernel RCU: shrink the size of the struct rcu\_head"
2350,month="December"
2351,year="2009"
2352,note="Available:
2353\url{http://lkml.org/lkml/2009/10/18/129}
2354[Viewed December 29, 2009]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002355,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002356 Mathieu proposed defer_rcu() with fixed-size per-thread pool
2357 of RCU callbacks.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002358}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002359}
2360
2361@unpublished{MathieuDesnoyers2009VerifPrePub
2362,Author="Mathieu Desnoyers and Paul E. McKenney and Michel R. Dagenais"
2363,Title="Multi-Core Systems Modeling for Formal Verification of Parallel Algorithms"
2364,month="December"
2365,year="2009"
2366,note="Submitted to IEEE TPDS"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002367,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002368 OOMem model for Mathieu's user-level RCU mechanical proof of
2369 correctness.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002370}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002371}
2372
2373@unpublished{MathieuDesnoyers2009URCUPrePub
2374,Author="Mathieu Desnoyers and Paul E. McKenney and Alan Stern and Michel R. Dagenais and Jonathan Walpole"
2375,Title="User-Level Implementations of Read-Copy Update"
2376,month="December"
2377,year="2010"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002378,url={\url{http://www.computer.org/csdl/trans/td/2012/02/ttd2012020375-abs.html}}
2379,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002380 RCU overview, desiderata, semi-formal semantics, user-level RCU
2381 usage scenarios, three classes of RCU implementation, wait-free
2382 RCU updates, RCU grace-period batching, update overhead,
2383 http://www.rdrop.com/users/paulmck/RCU/urcu-main-accepted.2011.08.30a.pdf
2384 http://www.rdrop.com/users/paulmck/RCU/urcu-supp-accepted.2011.08.30a.pdf
2385 Superseded by MathieuDesnoyers2012URCU.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002386}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002387}
2388
2389@inproceedings{HariKannan2009DynamicAnalysisRCU
2390,author = {Kannan, Hari}
2391,title = {Ordering decoupled metadata accesses in multiprocessors}
2392,booktitle = {MICRO 42: Proceedings of the 42nd Annual IEEE/ACM International Symposium on Microarchitecture}
2393,year = {2009}
2394,isbn = {978-1-60558-798-1}
2395,pages = {381--390}
2396,location = {New York, New York}
2397,doi = {http://doi.acm.org/10.1145/1669112.1669161}
2398,publisher = {ACM}
2399,address = {New York, NY, USA}
2400,annotation={
2401 Uses RCU to protect metadata used in dynamic analysis.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002402}
2403}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002404
2405@conference{PaulEMcKenney2010SimpleOptRCU
2406,Author="Paul E. McKenney"
2407,Title="Simplicity Through Optimization"
2408,Booktitle="linux.conf.au 2010"
2409,month="January"
2410,year="2010"
2411,address="Wellington, New Zealand"
2412,note="Available:
2413\url{http://www.rdrop.com/users/paulmck/RCU/SimplicityThruOptimization.2010.01.21f.pdf}
2414[Viewed October 10, 2010]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002415,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002416 TREE_PREEMPT_RCU optimizations greatly simplified the old
2417 PREEMPT_RCU implementation.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002418}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002419}
2420
2421@unpublished{PaulEMcKenney2010LockdepRCU
2422,Author="Paul E. McKenney"
2423,Title="Lockdep-{RCU}"
2424,month="February"
2425,year="2010"
2426,day="1"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002427,note="\url{https://lwn.net/Articles/371986/}"
2428,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002429 CONFIG_PROVE_RCU, or at least an early version.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002430 [Viewed June 4, 2010]
2431}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002432}
2433
2434@unpublished{AviKivity2010KVM2RCU
2435,Author="Avi Kivity"
2436,Title="[{PATCH} 37/40] {KVM}: Bump maximum vcpu count to 64"
2437,month="February"
2438,year="2010"
2439,note="Available:
2440\url{http://www.mail-archive.com/kvm@vger.kernel.org/msg28640.html}
2441[Viewed March 20, 2010]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002442,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002443 Use of RCU permits KVM to increase the size of guest OSes from
2444 16 CPUs to 64 CPUs.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002445}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002446}
2447
2448@unpublished{HerbertXu2010RCUResizeHash
2449,Author="Herbert Xu"
2450,Title="bridge: Add core IGMP snooping support"
2451,month="February"
2452,year="2010"
2453,note="Available:
Pranith Kumar5e40ad72014-06-09 11:51:23 -04002454\url{http://thread.gmane.org/gmane.linux.network/153338}
2455[Viewed June 9, 2014]"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002456,annotation={
2457 Use a pair of list_head structures to support RCU-protected
2458 resizable hash tables.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002459}
2460}
2461
2462@mastersthesis{AbhinavDuggal2010Masters
2463,author="Abhinav Duggal"
2464,title="Stopping Data Races Using Redflag"
2465,school="Stony Brook University"
2466,year="2010"
2467,annotation={
2468 Data-race detector incorporating RCU.
2469 http://www.filesystems.org/docs/abhinav-thesis/abhinav_thesis.pdf
2470}
2471}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002472
2473@article{JoshTriplett2010RPHash
2474,author="Josh Triplett and Paul E. McKenney and Jonathan Walpole"
2475,title="Scalable Concurrent Hash Tables via Relativistic Programming"
2476,journal="ACM Operating Systems Review"
2477,year=2010
2478,volume=44
2479,number=3
2480,month="July"
2481,annotation={
2482 RP fun with hash tables.
2483 http://portal.acm.org/citation.cfm?id=1842733.1842750
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002484}
2485}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002486
2487@unpublished{PaulEMcKenney2010RCUAPI
2488,Author="Paul E. McKenney"
2489,Title="The {RCU} {API}, 2010 Edition"
2490,month="December"
2491,day="8"
2492,year="2010"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002493,note="\url{http://lwn.net/Articles/418853/}"
2494,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002495 Includes updated software-engineering features.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002496 [Viewed December 8, 2010]
2497}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002498}
2499
2500@mastersthesis{AndrejPodzimek2010masters
2501,author="Andrej Podzimek"
2502,title="Read-Copy-Update for OpenSolaris"
2503,school="Charles University in Prague"
2504,year="2010"
2505,note="Available:
2506\url{https://andrej.podzimek.org/thesis.pdf}
2507[Viewed January 31, 2011]"
2508,annotation={
2509 Reviews RCU implementations and creates a few for OpenSolaris.
2510 Drives quiescent-state detection from RCU read-side primitives,
2511 in a manner roughly similar to that of Jim Houston.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002512}
2513}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002514
2515@unpublished{LinusTorvalds2011Linux2:6:38:rc1:NPigginVFS
2516,Author="Linus Torvalds"
2517,Title="Linux 2.6.38-rc1"
2518,month="January"
2519,year="2011"
2520,note="Available:
2521\url{https://lkml.org/lkml/2011/1/18/322}
2522[Viewed March 4, 2011]"
2523,annotation={
2524 "The RCU-based name lookup is at the other end of the spectrum - the
2525 absolute anti-gimmick. It's some seriously good stuff, and gets rid of
2526 the last main global lock that really tends to hurt some kernel loads.
2527 The dentry lock is no longer a big serializing issue. What's really
2528 nice about it is that it actually improves performance a lot even for
2529 single-threaded loads (on an SMP kernel), because it gets rid of some
2530 of the most expensive parts of path component lookup, which was the
2531 d_lock on every component lookup. So I'm seeing improvements of 30-50%
2532 on some seriously pathname-lookup intensive loads."
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002533}
2534}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002535
2536@techreport{JoshTriplett2011RPScalableCorrectOrdering
2537,author = {Josh Triplett and Philip W. Howard and Paul E. McKenney and Jonathan Walpole}
2538,title = {Scalable Correct Memory Ordering via Relativistic Programming}
2539,year = {2011}
2540,number = {11-03}
2541,institution = {Portland State University}
2542,note = {\url{http://www.cs.pdx.edu/pdfs/tr1103.pdf}}
2543}
2544
2545@inproceedings{PhilHoward2011RCUTMRBTree
2546,author = {Philip W. Howard and Jonathan Walpole}
2547,title = {A Relativistic Enhancement to Software Transactional Memory}
2548,booktitle = {Proceedings of the 3rd USENIX conference on Hot topics in parallelism}
2549,series = {HotPar'11}
2550,year = {2011}
2551,location = {Berkeley, CA}
2552,pages = {1--6}
2553,numpages = {6}
2554,url = {http://www.usenix.org/event/hotpar11/tech/final_files/Howard.pdf}
2555,publisher = {USENIX Association}
2556,address = {Berkeley, CA, USA}
2557}
2558
2559@techreport{PaulEMcKenney2011cyclicparallelRCU
2560,author="Paul E. McKenney and Jonathan Walpole"
2561,title="Efficient Support of Consistent Cyclic Search With Read-Copy Update and Parallel Updates"
2562,institution="US Patent and Trademark Office"
2563,address="Washington, DC"
2564,year="2011"
2565,number="US Patent 7,953,778"
2566,month="May"
2567,pages="34"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002568,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002569 Maintains an array of generation numbers to track in-flight
2570 updates and keeps an additional level of indirection to allow
2571 readers to confine themselves to the desired snapshot of the
2572 data structure.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002573}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002574}
2575
2576@inproceedings{Triplett:2011:RPHash
2577,author = {Triplett, Josh and McKenney, Paul E. and Walpole, Jonathan}
2578,title = {Resizable, Scalable, Concurrent Hash Tables via Relativistic Programming}
2579,booktitle = {Proceedings of the 2011 USENIX Annual Technical Conference}
2580,month = {June}
2581,year = {2011}
2582,pages = {145--158}
2583,numpages = {14}
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002584,url={http://www.usenix.org/event/atc11/tech/final_files/Triplett.pdf}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002585,publisher = {The USENIX Association}
2586,address = {Portland, OR USA}
2587}
2588
2589@unpublished{PaulEMcKenney2011RCU3.0trainwreck
2590,Author="Paul E. McKenney"
2591,Title="3.0 and {RCU:} what went wrong"
2592,month="July"
2593,day="27"
2594,year="2011"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002595,note="\url{http://lwn.net/Articles/453002/}"
2596,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002597 Analysis of the RCU trainwreck in Linux kernel 3.0.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002598 [Viewed July 27, 2011]
2599}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002600}
2601
2602@unpublished{NeilBrown2011MeetTheLockers
2603,Author="Neil Brown"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002604,Title="Meet the {Lockers}"
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002605,month="August"
2606,day="3"
2607,year="2011"
2608,note="Available:
2609\url{http://lwn.net/Articles/453685/}
2610[Viewed September 2, 2011]"
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002611,annotation={
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002612 The Locker family as an analogy for locking, reference counting,
2613 RCU, and seqlock.
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002614}
2615}
2616
2617@inproceedings{Seyster:2011:RFA:2075416.2075425
2618,author = {Seyster, Justin and Radhakrishnan, Prabakar and Katoch, Samriti and Duggal, Abhinav and Stoller, Scott D. and Zadok, Erez}
2619,title = {Redflag: a framework for analysis of Kernel-level concurrency}
2620,booktitle = {Proceedings of the 11th international conference on Algorithms and architectures for parallel processing - Volume Part I}
2621,series = {ICA3PP'11}
2622,year = {2011}
2623,isbn = {978-3-642-24649-4}
2624,location = {Melbourne, Australia}
2625,pages = {66--79}
2626,numpages = {14}
2627,url = {http://dl.acm.org/citation.cfm?id=2075416.2075425}
2628,acmid = {2075425}
2629,publisher = {Springer-Verlag}
2630,address = {Berlin, Heidelberg}
2631}
2632
2633@phdthesis{JoshTriplettPhD
2634,author="Josh Triplett"
2635,title="Relativistic Causal Ordering: A Memory Model for Scalable Concurrent Data Structures"
2636,school="Portland State University"
2637,year="2012"
2638,annotation={
2639 RCU-protected hash tables, barriers vs. read-side traversal order.
2640 .
2641 If the updater is making changes in the opposite direction from
2642 the read-side traveral order, the updater need only execute a
2643 memory-barrier instruction, but if in the same direction, the
2644 updater needs to wait for a grace period between the individual
2645 updates.
2646}
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002647}
2648
2649@article{MathieuDesnoyers2012URCU
2650,Author="Mathieu Desnoyers and Paul E. McKenney and Alan Stern and Michel R. Dagenais and Jonathan Walpole"
2651,Title="User-Level Implementations of Read-Copy Update"
2652,journal="IEEE Transactions on Parallel and Distributed Systems"
2653,volume={23}
2654,year="2012"
2655,issn="1045-9219"
2656,pages="375-382"
2657,doi="http://doi.ieeecomputersociety.org/10.1109/TPDS.2011.159"
2658,publisher="IEEE Computer Society"
2659,address="Los Alamitos, CA, USA"
2660,annotation={
2661 RCU overview, desiderata, semi-formal semantics, user-level RCU
2662 usage scenarios, three classes of RCU implementation, wait-free
2663 RCU updates, RCU grace-period batching, update overhead,
2664 http://www.rdrop.com/users/paulmck/RCU/urcu-main-accepted.2011.08.30a.pdf
2665 http://www.rdrop.com/users/paulmck/RCU/urcu-supp-accepted.2011.08.30a.pdf
Paul E. McKenney6ae37712013-05-01 10:05:01 -07002666 http://www.computer.org/cms/Computer.org/dl/trans/td/2012/02/extras/ttd2012020375s.pdf
2667}
2668}
2669
2670@inproceedings{AustinClements2012RCULinux:mmapsem
2671,author = {Austin Clements and Frans Kaashoek and Nickolai Zeldovich}
2672,title = {Scalable Address Spaces Using {RCU} Balanced Trees}
2673,booktitle = {Architectural Support for Programming Languages and Operating Systems (ASPLOS 2012)}
2674,month = {March}
2675,year = {2012}
2676,pages = {199--210}
2677,numpages = {12}
2678,publisher = {ACM}
2679,address = {London, UK}
2680,url="http://people.csail.mit.edu/nickolai/papers/clements-bonsai.pdf"
2681}
2682
2683@unpublished{PaulEMcKenney2012ELCbattery
2684,Author="Paul E. McKenney"
2685,Title="Making {RCU} Safe For Battery-Powered Devices"
2686,month="February"
2687,day="15"
2688,year="2012"
2689,note="Available:
2690\url{http://www.rdrop.com/users/paulmck/RCU/RCUdynticks.2012.02.15b.pdf}
2691[Viewed March 1, 2012]"
2692,annotation={
2693 RCU_FAST_NO_HZ, round 2.
2694}
2695}
2696
2697@article{GuillermoVigueras2012RCUCrowd
2698,author = {Vigueras, Guillermo and Ordu\~{n}a, Juan M. and Lozano, Miguel}
2699,day = {25}
2700,doi = {10.1007/s11227-012-0766-x}
2701,issn = {0920-8542}
2702,journal = {The Journal of Supercomputing}
2703,keywords = {linux, simulation}
2704,month = apr
2705,posted-at = {2012-05-03 09:12:04}
2706,priority = {2}
2707,title = {{A Read-Copy Update based parallel server for distributed crowd simulations}}
2708,url = {http://dx.doi.org/10.1007/s11227-012-0766-x}
2709,year = {2012}
2710}
2711
2712
2713@unpublished{JonCorbet2012ACCESS:ONCE
2714,Author="Jon Corbet"
2715,Title="{ACCESS\_ONCE()}"
2716,month="August"
2717,day="1"
2718,year="2012"
2719,note="\url{http://lwn.net/Articles/508991/}"
2720,annotation={
2721 A couple of simple specific compiler optimizations that motivate
2722 ACCESS_ONCE().
2723}
2724}
2725
2726@unpublished{AlexeyGotsman2012VerifyGraceExtended
2727,Author="Alexey Gotsman and Noam Rinetzky and Hongseok Yang"
2728,Title="Verifying Highly Concurrent Algorithms with Grace (extended version)"
2729,month="July"
2730,day="10"
2731,year="2012"
2732,note="\url{http://software.imdea.org/~gotsman/papers/recycling-esop13-ext.pdf}"
2733,annotation={
2734 Separation-logic formulation of RCU uses.
2735}
2736}
2737
2738@unpublished{PaulMcKenney2012RCUUsage
2739,Author="Paul E. McKenney and Silas Boyd-Wickizer and Jonathan Walpole"
2740,Title="{RCU} Usage In the Linux Kernel: One Decade Later"
2741,month="September"
2742,day="17"
2743,year="2012"
2744,url=http://rdrop.com/users/paulmck/techreports/survey.2012.09.17a.pdf
2745,note="Technical report paulmck.2012.09.17"
2746,annotation={
2747 Overview of the first variant of no-CBs CPUs for RCU.
2748}
2749}
2750
2751@unpublished{JonCorbet2012NOCB
2752,Author="Jon Corbet"
2753,Title="Relocating RCU callbacks"
2754,month="October"
2755,day="31"
2756,year="2012"
2757,note="\url{http://lwn.net/Articles/522262/}"
2758,annotation={
2759 Overview of the first variant of no-CBs CPUs for RCU.
2760}
2761}
2762
2763@phdthesis{JustinSeyster2012PhD
2764,author="Justin Seyster"
2765,title="Runtime Verification of Kernel-Level Concurrency Using Compiler-Based Instrumentation"
2766,school="Stony Brook University"
2767,year="2012"
2768,annotation={
2769 Looking for data races, including those involving RCU.
2770 Proposal:
2771 http://www.fsl.cs.sunysb.edu/docs/jseyster-proposal/redflag.pdf
2772 Dissertation:
2773 http://www.fsl.cs.sunysb.edu/docs/jseyster-dissertation/redflag.pdf
2774}
2775}
2776
2777@unpublished{PaulEMcKenney2013RCUUsage
2778,Author="Paul E. McKenney and Silas Boyd-Wickizer and Jonathan Walpole"
2779,Title="{RCU} Usage in the {Linux} Kernel: One Decade Later"
2780,month="February"
2781,day="24"
2782,year="2013"
2783,note="\url{http://rdrop.com/users/paulmck/techreports/RCUUsage.2013.02.24a.pdf}"
2784,annotation={
2785 Usage of RCU within the Linux kernel.
2786}
2787}
2788
2789@inproceedings{AlexeyGotsman2013ESOPRCU
2790,author = {Alexey Gotsman and Noam Rinetzky and Hongseok Yang}
2791,title = {Verifying concurrent memory reclamation algorithms with grace}
2792,booktitle = {ESOP'13: European Symposium on Programming}
2793,year = {2013}
2794,pages = {249--269}
2795,publisher = {Springer}
2796,address = {Rome, Italy}
2797,annotation={
2798 http://software.imdea.org/~gotsman/papers/recycling-esop13.pdf
2799}
2800}
2801
2802@unpublished{PaulEMcKenney2013NoTinyPreempt
2803,Author="Paul E. McKenney"
2804,Title="Simplifying RCU"
2805,month="March"
2806,day="6"
2807,year="2013"
2808,note="\url{http://lwn.net/Articles/541037/}"
2809,annotation={
2810 Getting rid of TINY_PREEMPT_RCU.
Paul E. McKenney4c62abc2011-12-29 10:45:24 -08002811}
Paul E. McKenney4c540052010-01-14 16:10:57 -08002812}