1 Read the Fscking Papers! !! 1 Read the F-ing Papers!
2 2
3 3
4 This document describes RCU-related publicatio 4 This document describes RCU-related publications, and is followed by
5 the corresponding bibtex entries. A number of 5 the corresponding bibtex entries. A number of the publications may
6 be found at http://www.rdrop.com/users/paulmck !! 6 be found at http://www.rdrop.com/users/paulmck/RCU/.
7 and search engines will usually find what you <<
8 7
9 The first thing resembling RCU was published i 8 The first thing resembling RCU was published in 1980, when Kung and Lehman
10 [Kung80] recommended use of a garbage collecto 9 [Kung80] recommended use of a garbage collector to defer destruction
11 of nodes in a parallel binary search tree in o 10 of nodes in a parallel binary search tree in order to simplify its
12 implementation. This works well in environmen 11 implementation. This works well in environments that have garbage
13 collectors, but most production garbage collec 12 collectors, but most production garbage collectors incur significant
14 overhead. 13 overhead.
15 14
16 In 1982, Manber and Ladner [Manber82,Manber84] 15 In 1982, Manber and Ladner [Manber82,Manber84] recommended deferring
17 destruction until all threads running at that 16 destruction until all threads running at that time have terminated, again
18 for a parallel binary search tree. This appro 17 for a parallel binary search tree. This approach works well in systems
19 with short-lived threads, such as the K42 rese 18 with short-lived threads, such as the K42 research operating system.
20 However, Linux has long-lived tasks, so more i 19 However, Linux has long-lived tasks, so more is needed.
21 20
22 In 1986, Hennessy, Osisek, and Seigh [Hennessy 21 In 1986, Hennessy, Osisek, and Seigh [Hennessy89] introduced passive
23 serialization, which is an RCU-like mechanism 22 serialization, which is an RCU-like mechanism that relies on the presence
24 of "quiescent states" in the VM/XA hypervisor 23 of "quiescent states" in the VM/XA hypervisor that are guaranteed not
25 to be referencing the data structure. However 24 to be referencing the data structure. However, this mechanism was not
26 optimized for modern computer systems, which i 25 optimized for modern computer systems, which is not surprising given
27 that these overheads were not so expensive in 26 that these overheads were not so expensive in the mid-80s. Nonetheless,
28 passive serialization appears to be the first 27 passive serialization appears to be the first deferred-destruction
29 mechanism to be used in production. Furthermo !! 28 mechanism to be used in production. Furthermore, the relevant patent has
30 has lapsed, so this approach may be used in no !! 29 lapsed, so this approach may be used in non-GPL software, if desired.
31 (In contrast, implementation of RCU is permitt !! 30 (In contrast, use of RCU is permitted only in software licensed under
32 under either GPL or LGPL. Sorry!!!) !! 31 GPL. Sorry!!!)
33 <<
34 In 1987, Rashid et al. described lazy TLB-flus <<
35 At first glance, this has nothing to do with R <<
36 this paper helped inspire the update-side batc <<
37 RCU implementation in DYNIX/ptx. In 1988, Bar <<
38 a description of Argus that noted that use of <<
39 be tolerated in some situations. Thus, this p <<
40 theoretical justification for use of stale dat <<
41 32
42 In 1990, Pugh [Pugh90] noted that explicitly t 33 In 1990, Pugh [Pugh90] noted that explicitly tracking which threads
43 were reading a given data structure permitted 34 were reading a given data structure permitted deferred free to operate
44 in the presence of non-terminating threads. H 35 in the presence of non-terminating threads. However, this explicit
45 tracking imposes significant read-side overhea 36 tracking imposes significant read-side overhead, which is undesirable
46 in read-mostly situations. This algorithm doe 37 in read-mostly situations. This algorithm does take pains to avoid
47 write-side contention and parallelize the othe 38 write-side contention and parallelize the other write-side overheads by
48 providing a fine-grained locking design, howev 39 providing a fine-grained locking design, however, it would be interesting
49 to see how much of the performance advantage r 40 to see how much of the performance advantage reported in 1990 remains
50 today. !! 41 in 2004.
51 42
52 At about this same time, Andrews [Andrews91tex !! 43 At about this same time, Adams [Adams91] described ``chaotic relaxation'',
53 relaxation'', where the normal barriers betwee !! 44 where the normal barriers between successive iterations of convergent
54 of convergent numerical algorithms are relaxed !! 45 numerical algorithms are relaxed, so that iteration $n$ might use
55 might use data from iteration $n-1$ or even $n !! 46 data from iteration $n-1$ or even $n-2$. This introduces error,
56 error, which typically slows convergence and t !! 47 which typically slows convergence and thus increases the number of
57 iterations required. However, this increase i 48 iterations required. However, this increase is sometimes more than made
58 up for by a reduction in the number of expensi 49 up for by a reduction in the number of expensive barrier operations,
59 which are otherwise required to synchronize th 50 which are otherwise required to synchronize the threads at the end
60 of each iteration. Unfortunately, chaotic rel 51 of each iteration. Unfortunately, chaotic relaxation requires highly
61 structured data, such as the matrices used in 52 structured data, such as the matrices used in scientific programs, and
62 is thus inapplicable to most data structures i 53 is thus inapplicable to most data structures in operating-system kernels.
63 54
64 In 1992, Henry (now Alexia) Massalin completed 55 In 1992, Henry (now Alexia) Massalin completed a dissertation advising
65 parallel programmers to defer processing when 56 parallel programmers to defer processing when feasible to simplify
66 synchronization [HMassalinPhD]. RCU makes ext !! 57 synchronization. RCU makes extremely heavy use of this advice.
67 this advice. <<
68 58
69 In 1993, Jacobson [Jacobson93] verbally descri 59 In 1993, Jacobson [Jacobson93] verbally described what is perhaps the
70 simplest deferred-free technique: simply waiti 60 simplest deferred-free technique: simply waiting a fixed amount of time
71 before freeing blocks awaiting deferred free. 61 before freeing blocks awaiting deferred free. Jacobson did not describe
72 any write-side changes he might have made in t 62 any write-side changes he might have made in this work using SGI's Irix
73 kernel. Aju John published a similar techniqu 63 kernel. Aju John published a similar technique in 1995 [AjuJohn95].
74 This works well if there is a well-defined upp 64 This works well if there is a well-defined upper bound on the length of
75 time that reading threads can hold references, 65 time that reading threads can hold references, as there might well be in
76 hard real-time systems. However, if this time 66 hard real-time systems. However, if this time is exceeded, perhaps due
77 to preemption, excessive interrupts, or larger 67 to preemption, excessive interrupts, or larger-than-anticipated load,
78 memory corruption can ensue, with no reasonabl 68 memory corruption can ensue, with no reasonable means of diagnosis.
79 Jacobson's technique is therefore inappropriat 69 Jacobson's technique is therefore inappropriate for use in production
80 operating-system kernels, except when such ker 70 operating-system kernels, except when such kernels can provide hard
81 real-time response guarantees for all operatio 71 real-time response guarantees for all operations.
82 72
83 Also in 1995, Pu et al. [Pu95a] applied a tech 73 Also in 1995, Pu et al. [Pu95a] applied a technique similar to that of Pugh's
84 read-side-tracking to permit replugging of alg 74 read-side-tracking to permit replugging of algorithms within a commercial
85 Unix operating system. However, this repluggi 75 Unix operating system. However, this replugging permitted only a single
86 reader at a time. The following year, this sa 76 reader at a time. The following year, this same group of researchers
87 extended their technique to allow for multiple 77 extended their technique to allow for multiple readers [Cowan96a].
88 Their approach requires memory barriers (and t 78 Their approach requires memory barriers (and thus pipeline stalls),
89 but reduces memory latency, contention, and lo 79 but reduces memory latency, contention, and locking overheads.
90 80
91 1995 also saw the first publication of DYNIX/p 81 1995 also saw the first publication of DYNIX/ptx's RCU mechanism
92 [Slingwine95], which was optimized for modern 82 [Slingwine95], which was optimized for modern CPU architectures,
93 and was successfully applied to a number of si 83 and was successfully applied to a number of situations within the
94 DYNIX/ptx kernel. The corresponding conferenc 84 DYNIX/ptx kernel. The corresponding conference paper appeared in 1998
95 [McKenney98]. 85 [McKenney98].
96 86
97 In 1999, the Tornado and K42 groups described 87 In 1999, the Tornado and K42 groups described their "generations"
98 mechanism, which is quite similar to RCU [Gams !! 88 mechanism, which quite similar to RCU [Gamsa99]. These operating systems
99 systems made pervasive use of RCU in place of !! 89 made pervasive use of RCU in place of "existence locks", which greatly
100 greatly simplifies locking hierarchies and hel !! 90 simplifies locking hierarchies.
101 !! 91
102 The year 2000 saw an email exchange that would !! 92 2001 saw the first RCU presentation involving Linux [McKenney01a]
103 led to yet another independent invention of so !! 93 at OLS. The resulting abundance of RCU patches was presented the
104 [RustyRussell2000a,RustyRussell2000b]. Instea !! 94 following year [McKenney02a], and use of RCU in dcache was first
105 RCU presentation involving Linux [McKenney01a] !! 95 described that same year [Linder02a].
106 abundance of RCU patches was presented the fol <<
107 and use of RCU in dcache was first described t <<
108 96
109 Also in 2002, Michael [Michael02b,Michael02a] 97 Also in 2002, Michael [Michael02b,Michael02a] presented "hazard-pointer"
110 techniques that defer the destruction of data 98 techniques that defer the destruction of data structures to simplify
111 non-blocking synchronization (wait-free synchr 99 non-blocking synchronization (wait-free synchronization, lock-free
112 synchronization, and obstruction-free synchron 100 synchronization, and obstruction-free synchronization are all examples of
113 non-blocking synchronization). The correspond !! 101 non-blocking synchronization). In particular, this technique eliminates
114 in 2004 [MagedMichael04a]. This technique eli !! 102 locking, reduces contention, reduces memory latency for readers, and
115 contention, reduces memory latency for readers !! 103 parallelizes pipeline stalls and memory latency for writers. However,
116 stalls and memory latency for writers. Howeve !! 104 these techniques still impose significant read-side overhead in the
117 impose significant read-side overhead in the f !! 105 form of memory barriers. Researchers at Sun worked along similar lines
118 Researchers at Sun worked along similar lines !! 106 in the same timeframe [HerlihyLM02]. These techniques can be thought
119 [HerlihyLM02]. These techniques can be though !! 107 of as inside-out reference counts, where the count is represented by the
120 counts, where the count is represented by the !! 108 number of hazard pointers referencing a given data structure (rather than
121 referencing a given data structure rather than !! 109 the more conventional counter field within the data structure itself).
122 counter field within the data structure itself <<
123 of inside-out reference counts is that they ca <<
124 variables, thus allowing races between access <<
125 110
126 By the same token, RCU can be thought of as a 111 By the same token, RCU can be thought of as a "bulk reference count",
127 where some form of reference counter covers al 112 where some form of reference counter covers all reference by a given CPU
128 or thread during a set timeframe. This timefr 113 or thread during a set timeframe. This timeframe is related to, but
129 not necessarily exactly the same as, an RCU gr 114 not necessarily exactly the same as, an RCU grace period. In classic
130 RCU, the reference counter is the per-CPU bit 115 RCU, the reference counter is the per-CPU bit in the "bitmask" field,
131 and each such bit covers all references that m 116 and each such bit covers all references that might have been made by
132 the corresponding CPU during the prior grace p 117 the corresponding CPU during the prior grace period. Of course, RCU
133 can be thought of in other terms as well. 118 can be thought of in other terms as well.
134 119
135 In 2003, the K42 group described how RCU could 120 In 2003, the K42 group described how RCU could be used to create
136 hot-pluggable implementations of operating-sys 121 hot-pluggable implementations of operating-system functions [Appavoo03a].
137 Later that year saw a paper describing an RCU !! 122 Later that year saw a paper describing an RCU implementation of System
138 of System V IPC [Arcangeli03] (following up on !! 123 V IPC [Arcangeli03], and an introduction to RCU in Linux Journal
139 Hugh Dickins [Dickins02a] and an implementatio <<
140 [MingmingCao2002IPCRCU]), and an introduction <<
141 [McKenney03a]. 124 [McKenney03a].
142 125
143 2004 has seen a Linux-Journal article on use o 126 2004 has seen a Linux-Journal article on use of RCU in dcache
144 [McKenney04a], a performance comparison of loc 127 [McKenney04a], a performance comparison of locking to RCU on several
145 different CPUs [McKenney04b], a dissertation d 128 different CPUs [McKenney04b], a dissertation describing use of RCU in a
146 number of operating-system kernels [PaulEdward 129 number of operating-system kernels [PaulEdwardMcKenneyPhD], a paper
147 describing how to make RCU safe for soft-realt 130 describing how to make RCU safe for soft-realtime applications [Sarma04c],
148 and a paper describing SELinux performance wit 131 and a paper describing SELinux performance with RCU [JamesMorris04b].
149 132
150 2005 brought further adaptation of RCU to real 133 2005 brought further adaptation of RCU to realtime use, permitting
151 preemption of RCU realtime critical sections [ 134 preemption of RCU realtime critical sections [PaulMcKenney05a,
152 PaulMcKenney05b]. 135 PaulMcKenney05b].
153 136
154 2006 saw the first best-paper award for an RCU 137 2006 saw the first best-paper award for an RCU paper [ThomasEHart2006a],
155 as well as further work on efficient implement 138 as well as further work on efficient implementations of preemptible
156 RCU [PaulEMcKenney2006b], but priority-boostin 139 RCU [PaulEMcKenney2006b], but priority-boosting of RCU read-side critical
157 sections proved elusive. An RCU implementatio 140 sections proved elusive. An RCU implementation permitting general
158 blocking in read-side critical sections appear 141 blocking in read-side critical sections appeared [PaulEMcKenney2006c],
159 Robert Olsson described an RCU-protected trie- 142 Robert Olsson described an RCU-protected trie-hash combination
160 [RobertOlsson2006a]. 143 [RobertOlsson2006a].
161 144
162 2007 saw the journal version of the award-winn 145 2007 saw the journal version of the award-winning RCU paper from 2006
163 [ThomasEHart2007a], as well as a paper demonst 146 [ThomasEHart2007a], as well as a paper demonstrating use of Promela
164 and Spin to mechanically verify an optimizatio 147 and Spin to mechanically verify an optimization to Oleg Nesterov's
165 QRCU [PaulEMcKenney2007QRCUspin], a design doc 148 QRCU [PaulEMcKenney2007QRCUspin], a design document describing
166 preemptible RCU [PaulEMcKenney2007PreemptibleR 149 preemptible RCU [PaulEMcKenney2007PreemptibleRCU], and the three-part
167 LWN "What is RCU?" series [PaulEMcKenney2007Wh 150 LWN "What is RCU?" series [PaulEMcKenney2007WhatIsRCUFundamentally,
168 PaulEMcKenney2008WhatIsRCUUsage, and PaulEMcKe 151 PaulEMcKenney2008WhatIsRCUUsage, and PaulEMcKenney2008WhatIsRCUAPI].
169 152
170 2008 saw a journal paper on real-time RCU [Din <<
171 a history of how Linux changed RCU more than R <<
172 [PaulEMcKenney2008RCUOSR], and a design overvi <<
173 [PaulEMcKenney2008HierarchicalRCU]. <<
174 <<
175 2009 introduced user-level RCU algorithms [Pau <<
176 which Mathieu Desnoyers is now maintaining [Ma <<
177 [MathieuDesnoyersPhD]. TINY_RCU [PaulEMcKenne <<
178 its appearance, as did expedited RCU [PaulEMcK <<
179 The problem of resizable RCU-protected hash ta <<
180 to a solution [JoshTriplett2009RPHash]. A few <<
181 using RCU to solve their parallel problems [Ha <<
182 <<
183 2010 produced a simpler preemptible-RCU implem <<
184 based on TREE_RCU [PaulEMcKenney2010SimpleOptR <<
185 [PaulEMcKenney2010LockdepRCU], another resizab <<
186 table [HerbertXu2010RCUResizeHash] (this one c <<
187 but allowing arbitrary changes in hash functio <<
188 avoidance in the networking code), realization <<
189 hash table with atomic node move [JoshTriplett <<
190 the RCU API [PaulEMcKenney2010RCUAPI]. <<
191 <<
192 2011 marked the inclusion of Nick Piggin's ful <<
193 [LinusTorvalds2011Linux2:6:38:rc1:NPigginVFS], <<
194 tree using software transactional memory to pr <<
195 (strange, but true!) [PhilHoward2011RCUTMRBTre <<
196 RCU-protected resizable hash tables [Triplett: <<
197 trainwreck [PaulEMcKenney2011RCU3.0trainwreck] <<
198 Lockers" LWN article [NeilBrown2011MeetTheLock <<
199 work looked at debugging uses of RCU [Seyster: <<
200 <<
201 In 2012, Josh Triplett received his Ph.D. with <<
202 covering RCU-protected resizable hash tables a <<
203 between memory barriers and read-side traversa <<
204 is making changes in the opposite direction fr <<
205 order, the updater need only execute a memory- <<
206 but if in the same direction, the updater need <<
207 period between the individual updates [JoshTri <<
208 after seventeen years of attempts, an RCU pape <<
209 academic journal, IEEE Transactions on Paralle <<
210 [MathieuDesnoyers2012URCU]. A group of resear <<
211 user-level RCU to crowd simulation [GuillermoV <<
212 another group of researchers in Europe produce <<
213 RCU based on separation logic [AlexeyGotsman20 <<
214 which was published in the 2013 European Sympo <<
215 [AlexeyGotsman2013ESOPRCU]. <<
216 <<
217 <<
218 <<
219 Bibtex Entries 153 Bibtex Entries
220 154
221 @article{Kung80 155 @article{Kung80
222 ,author="H. T. Kung and Q. Lehman" 156 ,author="H. T. Kung and Q. Lehman"
223 ,title="Concurrent Manipulation of Binary Sear !! 157 ,title="Concurrent Maintenance of Binary Search Trees"
224 ,Year="1980" 158 ,Year="1980"
225 ,Month="September" 159 ,Month="September"
226 ,journal="ACM Transactions on Database Systems 160 ,journal="ACM Transactions on Database Systems"
227 ,volume="5" 161 ,volume="5"
228 ,number="3" 162 ,number="3"
229 ,pages="354-382" 163 ,pages="354-382"
230 ,annotation={ <<
231 Use garbage collector to clean up data <<
232 . <<
233 Oldest use of something vaguely resemb <<
234 http://portal.acm.org/citation.cfm?id= <<
235 [Viewed December 3, 2007] <<
236 } <<
237 } 164 }
238 165
239 @techreport{Manber82 166 @techreport{Manber82
240 ,author="Udi Manber and Richard E. Ladner" 167 ,author="Udi Manber and Richard E. Ladner"
241 ,title="Concurrency Control in a Dynamic Searc 168 ,title="Concurrency Control in a Dynamic Search Structure"
242 ,institution="Department of Computer Science, 169 ,institution="Department of Computer Science, University of Washington"
243 ,address="Seattle, Washington" 170 ,address="Seattle, Washington"
244 ,year="1982" 171 ,year="1982"
245 ,number="82-01-01" 172 ,number="82-01-01"
246 ,month="January" 173 ,month="January"
247 ,pages="28" 174 ,pages="28"
248 ,annotation={ <<
249 . <<
250 Superseded by Manber84. <<
251 . <<
252 Describes concurrent AVL tree implemen <<
253 garbage-collection mechanism to handle <<
254 of nodes in the tree, but lacks the su <<
255 concept of read-copy locking. <<
256 . <<
257 Keeps full list of processes that were <<
258 node was to be deleted, and waits unti <<
259 -terminated- before allowing this node <<
260 not described in great detail -- one c <<
261 IDs for this if the ID space was large <<
262 never occurred. <<
263 . <<
264 This restriction makes this algorithm <<
265 systems comprised of long-lived proces <<
266 completely unacceptable overhead in sy <<
267 of processes. Finally, it is specific <<
268 . <<
269 Cites Kung80, so not an independent in <<
270 RCU-like usage that does not rely on a <<
271 collector. <<
272 } <<
273 } 175 }
274 176
275 @article{Manber84 177 @article{Manber84
276 ,author="Udi Manber and Richard E. Ladner" 178 ,author="Udi Manber and Richard E. Ladner"
277 ,title="Concurrency Control in a Dynamic Searc 179 ,title="Concurrency Control in a Dynamic Search Structure"
278 ,Year="1984" 180 ,Year="1984"
279 ,Month="September" 181 ,Month="September"
280 ,journal="ACM Transactions on Database Systems 182 ,journal="ACM Transactions on Database Systems"
281 ,volume="9" 183 ,volume="9"
282 ,number="3" 184 ,number="3"
283 ,pages="439-455" 185 ,pages="439-455"
284 ,annotation={ <<
285 Describes concurrent AVL tree implemen <<
286 garbage-collection mechanism to handle <<
287 of nodes in the tree, but lacks the su <<
288 concept of read-copy locking. <<
289 . <<
290 Keeps full list of processes that were <<
291 node was to be deleted, and waits unti <<
292 -terminated- before allowing this node <<
293 not described in great detail -- one c <<
294 IDs for this if the ID space was large <<
295 never occurred. <<
296 . <<
297 This restriction makes this algorithm <<
298 systems comprised of long-lived proces <<
299 completely unacceptable overhead in sy <<
300 of processes. Finally, it is specific <<
301 } <<
302 } <<
303 <<
304 @Conference{RichardRashid87a <<
305 ,Author="Richard Rashid and Avadis Tevanian an <<
306 David Golub and Robert Baron and David Black a <<
307 Jonathan Chew" <<
308 ,Title="Machine-Independent Virtual Memory Man <<
309 Uniprocessor and Multiprocessor Architectures" <<
310 ,Booktitle="{2\textsuperscript{nd} Symposium o <<
311 for Programming Languages and Operating System <<
312 ,Publisher="Association for Computing Machiner <<
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/rashi <<
319 [Viewed February 17, 2005]" <<
320 ,annotation={ <<
321 Describes lazy TLB flush, where one wa <<
322 through a scheduling-clock interrupt b <<
323 of virtual address. Does not describe <<
324 all CPUs have in fact taken such an in <<
325 no shortage of straightforward methods <<
326 . <<
327 Note that it does not make sense to ju <<
328 time, since a given CPU might have int <<
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} <<
345 ,annotation={ <<
346 At the top of page 307: "Conflicts wit <<
347 are necessary if the reported total is <<
348 could be avoided by having total retur <<
349 out of date." Relies on semantics -- <<
350 values sometimes OK. <<
351 } <<
352 } 186 }
353 187
354 @techreport{Hennessy89 188 @techreport{Hennessy89
355 ,author="James P. Hennessy and Damian L. Osise 189 ,author="James P. Hennessy and Damian L. Osisek and Joseph W. {Seigh II}"
356 ,title="Passive Serialization in a Multitaskin 190 ,title="Passive Serialization in a Multitasking Environment"
357 ,institution="US Patent and Trademark Office" 191 ,institution="US Patent and Trademark Office"
358 ,address="Washington, DC" 192 ,address="Washington, DC"
359 ,year="1989" 193 ,year="1989"
360 ,number="US Patent 4,809,168 (lapsed)" 194 ,number="US Patent 4,809,168 (lapsed)"
361 ,month="February" 195 ,month="February"
362 ,pages="11" 196 ,pages="11"
363 } 197 }
364 198
365 @techreport{Pugh90 199 @techreport{Pugh90
366 ,author="William Pugh" 200 ,author="William Pugh"
367 ,title="Concurrent Maintenance of Skip Lists" 201 ,title="Concurrent Maintenance of Skip Lists"
368 ,institution="Institute of Advanced Computer S 202 ,institution="Institute of Advanced Computer Science Studies, Department of Computer Science, University of Maryland"
369 ,address="College Park, Maryland" 203 ,address="College Park, Maryland"
370 ,year="1990" 204 ,year="1990"
371 ,number="CS-TR-2222.1" 205 ,number="CS-TR-2222.1"
372 ,month="June" 206 ,month="June"
373 ,annotation={ <<
374 Concurrent access to skip lists. Has <<
375 Uses concept of ``garbage queue'', but <<
376 the garbage efficiently. <<
377 . <<
378 Appears to be an independent invention <<
379 } <<
380 } 207 }
381 208
382 # Was Adams91, see also syncrefs.bib. !! 209 @Book{Adams91
383 @Book{Andrews91textbook !! 210 ,Author="Gregory R. Adams"
384 ,Author="Gregory R. Andrews" <<
385 ,title="Concurrent Programming, Principles, an 211 ,title="Concurrent Programming, Principles, and Practices"
386 ,Publisher="Benjamin Cummins" 212 ,Publisher="Benjamin Cummins"
387 ,Year="1991" 213 ,Year="1991"
388 ,annotation={ <<
389 Has a few paragraphs describing ``chao <<
390 numerical analysis technique that allo <<
391 avoid synchronization overhead by usin <<
392 . <<
393 Seems like this is descended from yet <<
394 invention of RCU-like function -- but <<
395 in that reclamation is not necessary. <<
396 } <<
397 } 214 }
398 215
399 @phdthesis{HMassalinPhD 216 @phdthesis{HMassalinPhD
400 ,author="H. Massalin" 217 ,author="H. Massalin"
401 ,title="Synthesis: An Efficient Implementation 218 ,title="Synthesis: An Efficient Implementation of Fundamental Operating
402 System Services" 219 System Services"
403 ,school="Columbia University" 220 ,school="Columbia University"
404 ,address="New York, NY" 221 ,address="New York, NY"
405 ,year="1992" 222 ,year="1992"
406 ,annotation={ !! 223 ,annotation="
407 Mondo optimizing compiler. 224 Mondo optimizing compiler.
408 Wait-free stuff. 225 Wait-free stuff.
409 Good advice: defer work to avoid synch !! 226 Good advice: defer work to avoid synchronization.
410 (PDF page 106), Section 5.4, f !! 227 "
411 } <<
412 } 228 }
413 229
414 @unpublished{Jacobson93 230 @unpublished{Jacobson93
415 ,author="Van Jacobson" 231 ,author="Van Jacobson"
416 ,title="Avoid Read-Side Locking Via Delayed Fr 232 ,title="Avoid Read-Side Locking Via Delayed Free"
417 ,year="1993" 233 ,year="1993"
418 ,month="September" 234 ,month="September"
419 ,note="private communication" !! 235 ,note="Verbal discussion"
420 ,annotation={ <<
421 Use fixed time delay to approximate gr <<
422 but subject to random memory corruptio <<
423 . <<
424 Independent invention of RCU-like mech <<
425 } <<
426 } 236 }
427 237
428 @Conference{AjuJohn95 238 @Conference{AjuJohn95
429 ,Author="Aju John" 239 ,Author="Aju John"
430 ,Title="Dynamic vnodes -- Design and Implement 240 ,Title="Dynamic vnodes -- Design and Implementation"
431 ,Booktitle="{USENIX Winter 1995}" 241 ,Booktitle="{USENIX Winter 1995}"
432 ,Publisher="USENIX Association" 242 ,Publisher="USENIX Association"
433 ,Month="January" 243 ,Month="January"
434 ,Year="1995" 244 ,Year="1995"
435 ,pages="11-23" 245 ,pages="11-23"
436 ,Address="New Orleans, LA" 246 ,Address="New Orleans, LA"
437 ,note="Available: <<
438 \url{https://www.usenix.org/publications/libra <<
439 [Viewed October 1, 2010]" <<
440 ,annotation={ <<
441 Age vnodes out of the cache, and have <<
442 parameter. Not clear that all races w <<
443 Used a 20-minute time by default, whic <<
444 be suitable during DoS attacks or viru <<
445 . <<
446 Apparently independent invention of RC <<
447 } <<
448 } 247 }
449 248
450 @conference{Pu95a !! 249 @conference{Pu95a,
451 ,Author = "Calton Pu and Tito Autrey and Andre !! 250 Author = "Calton Pu and Tito Autrey and Andrew Black and Charles Consel and
452 Crispin Cowan and Jon Inouye and Lakshmi Ketha 251 Crispin Cowan and Jon Inouye and Lakshmi Kethana and Jonathan Walpole and
453 Ke Zhang" !! 252 Ke Zhang",
454 ,Title = "Optimistic Incremental Specializatio !! 253 Title = "Optimistic Incremental Specialization: Streamlining a Commercial
455 ,Operating System" !! 254 Operating System",
456 ,Booktitle = "15\textsuperscript{th} ACM Sympo !! 255 Booktitle = "15\textsuperscript{th} ACM Symposium on
457 ,Operating Systems Principles (SOSP'95)" !! 256 Operating Systems Principles (SOSP'95)",
458 ,address = "Copper Mountain, CO" !! 257 address = "Copper Mountain, CO",
459 ,month="December" !! 258 month="December",
460 ,year="1995" !! 259 year="1995",
461 ,pages="314-321" !! 260 pages="314-321",
462 ,annotation={ !! 261 annotation="
463 Uses a replugger, but with a flag to s 262 Uses a replugger, but with a flag to signal when people are
464 using the resource at hand. Only one 263 using the resource at hand. Only one reader at a time.
465 } !! 264 "
466 } 265 }
467 266
468 @conference{Cowan96a !! 267 @conference{Cowan96a,
469 ,Author = "Crispin Cowan and Tito Autrey and C !! 268 Author = "Crispin Cowan and Tito Autrey and Charles Krasic and
470 ,Calton Pu and Jonathan Walpole" !! 269 Calton Pu and Jonathan Walpole",
471 ,Title = "Fast Concurrent Dynamic Linking for !! 270 Title = "Fast Concurrent Dynamic Linking for an Adaptive Operating System",
472 ,Booktitle = "International Conference on Conf !! 271 Booktitle = "International Conference on Configurable Distributed Systems
473 (ICCDS'96)" !! 272 (ICCDS'96)",
474 ,address = "Annapolis, MD" !! 273 address = "Annapolis, MD",
475 ,month="May" !! 274 month="May",
476 ,year="1996" !! 275 year="1996",
477 ,pages="108" !! 276 pages="108",
478 ,isbn="0-8186-7395-8" !! 277 isbn="0-8186-7395-8",
479 ,annotation={ !! 278 annotation="
480 Uses a replugger, but with a counter t 279 Uses a replugger, but with a counter to signal when people are
481 using the resource at hand. Allows mu 280 using the resource at hand. Allows multiple readers.
482 } !! 281 "
483 } 282 }
484 283
485 @techreport{Slingwine95 284 @techreport{Slingwine95
486 ,author="John D. Slingwine and Paul E. McKenne 285 ,author="John D. Slingwine and Paul E. McKenney"
487 ,title="Apparatus and Method for Achieving Red 286 ,title="Apparatus and Method for Achieving Reduced Overhead Mutual
488 Exclusion and Maintaining Coherency in a Multi 287 Exclusion and Maintaining Coherency in a Multiprocessor System
489 Utilizing Execution History and Thread Monitor 288 Utilizing Execution History and Thread Monitoring"
490 ,institution="US Patent and Trademark Office" 289 ,institution="US Patent and Trademark Office"
491 ,address="Washington, DC" 290 ,address="Washington, DC"
492 ,year="1995" 291 ,year="1995"
493 ,number="US Patent 5,442,758" !! 292 ,number="US Patent 5,442,758 (contributed under GPL)"
494 ,month="August" 293 ,month="August"
495 ,annotation={ <<
496 Describes the parallel RCU infrastruct <<
497 (structure of bitmap can reflect bus s <<
498 . <<
499 Another independent invention of an RC <<
500 "real" RCU this time! <<
501 } <<
502 } 294 }
503 295
504 @techreport{Slingwine97 296 @techreport{Slingwine97
505 ,author="John D. Slingwine and Paul E. McKenne 297 ,author="John D. Slingwine and Paul E. McKenney"
506 ,title="Method for Maintaining Data Coherency !! 298 ,title="Method for maintaining data coherency using thread
507 Summaries in a Multicomputer System" !! 299 activity summaries in a multicomputer system"
508 ,institution="US Patent and Trademark Office" 300 ,institution="US Patent and Trademark Office"
509 ,address="Washington, DC" 301 ,address="Washington, DC"
510 ,year="1997" 302 ,year="1997"
511 ,number="US Patent 5,608,893" !! 303 ,number="US Patent 5,608,893 (contributed under GPL)"
512 ,month="March" 304 ,month="March"
513 ,pages="19" <<
514 ,annotation={ <<
515 Describes use of RCU to synchronize da <<
516 SMP/NUMA computer systems. <<
517 } <<
518 } 305 }
519 306
520 @techreport{Slingwine98 307 @techreport{Slingwine98
521 ,author="John D. Slingwine and Paul E. McKenne 308 ,author="John D. Slingwine and Paul E. McKenney"
522 ,title="Apparatus and Method for Achieving Red !! 309 ,title="Apparatus and method for achieving reduced overhead
523 Exclusion and Maintaining Coherency in a Multi !! 310 mutual exclusion and maintaining coherency in a multiprocessor
524 Utilizing Execution History and Thread Monitor !! 311 system utilizing execution history and thread monitoring"
525 ,institution="US Patent and Trademark Office" 312 ,institution="US Patent and Trademark Office"
526 ,address="Washington, DC" 313 ,address="Washington, DC"
527 ,year="1998" 314 ,year="1998"
528 ,number="US Patent 5,727,209" !! 315 ,number="US Patent 5,727,209 (contributed under GPL)"
529 ,month="March" 316 ,month="March"
530 ,annotation={ <<
531 Describes doing an atomic update by co <<
532 then substituting it into the data str <<
533 } <<
534 } 317 }
535 318
536 @Conference{McKenney98 319 @Conference{McKenney98
537 ,Author="Paul E. McKenney and John D. Slingwin 320 ,Author="Paul E. McKenney and John D. Slingwine"
538 ,Title="Read-Copy Update: Using Execution Hist 321 ,Title="Read-Copy Update: Using Execution History to Solve Concurrency
539 Problems" 322 Problems"
540 ,Booktitle="{Parallel and Distributed Computin 323 ,Booktitle="{Parallel and Distributed Computing and Systems}"
541 ,Month="October" 324 ,Month="October"
542 ,Year="1998" 325 ,Year="1998"
543 ,pages="509-518" 326 ,pages="509-518"
544 ,Address="Las Vegas, NV" 327 ,Address="Las Vegas, NV"
545 ,annotation={ <<
546 Describes and analyzes RCU mechanism i <<
547 application to linked list update and <<
548 Defines 'quiescent state'. Includes b <<
549 evaluation. <<
550 http://www.rdrop.com/users/paulmck/RCU <<
551 [Viewed December 3, 2007] <<
552 } <<
553 } 328 }
554 329
555 @Conference{Gamsa99 330 @Conference{Gamsa99
556 ,Author="Ben Gamsa and Orran Krieger and Jonat 331 ,Author="Ben Gamsa and Orran Krieger and Jonathan Appavoo and Michael Stumm"
557 ,Title="Tornado: Maximizing Locality and Concu 332 ,Title="Tornado: Maximizing Locality and Concurrency in a Shared Memory
558 Multiprocessor Operating System" 333 Multiprocessor Operating System"
559 ,Booktitle="{Proceedings of the 3\textsuperscr 334 ,Booktitle="{Proceedings of the 3\textsuperscript{rd} Symposium on
560 Operating System Design and Implementation}" 335 Operating System Design and Implementation}"
561 ,Month="February" 336 ,Month="February"
562 ,Year="1999" 337 ,Year="1999"
563 ,pages="87-100" 338 ,pages="87-100"
564 ,Address="New Orleans, LA" 339 ,Address="New Orleans, LA"
565 ,annotation={ <<
566 Use of RCU-like facility in K42/Tornad <<
567 invention of RCU. <<
568 See especially pages 7-9 (Section 5). <<
569 http://www.usenix.org/events/osdi99/fu <<
570 [Viewed August 30, 2006] <<
571 } <<
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/archiv <<
582 [Viewed April 10, 2006]" <<
583 ,annotation={ <<
584 Proto-RCU proposal from Phil Rumpf and <<
585 Yet another independent invention of R <<
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/archiv <<
600 [Viewed April 10, 2006]" <<
601 ,annotation={ <<
602 Proto-RCU proposal from Phil Rumpf and <<
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 { <<
611 ,month="February" <<
612 ,year="2001" <<
613 ,note="Available: <<
614 \url{http://lse.sourceforge.net/locking/rcu/rc <<
615 [Viewed October 18, 2004]" <<
616 ,annotation={ <<
617 Prototypical Linux documentation for R <<
618 } <<
619 } 340 }
620 341
621 @techreport{Slingwine01 342 @techreport{Slingwine01
622 ,author="John D. Slingwine and Paul E. McKenne 343 ,author="John D. Slingwine and Paul E. McKenney"
623 ,title="Apparatus and Method for Achieving Red !! 344 ,title="Apparatus and method for achieving reduced overhead
624 Exclusion and Maintaining Coherency in a Multi !! 345 mutual exclusion and maintaining coherency in a multiprocessor
625 Utilizing Execution History and Thread Monitor !! 346 system utilizing execution history and thread monitoring"
626 ,institution="US Patent and Trademark Office" 347 ,institution="US Patent and Trademark Office"
627 ,address="Washington, DC" 348 ,address="Washington, DC"
628 ,year="2001" 349 ,year="2001"
629 ,number="US Patent 6,219,690" !! 350 ,number="US Patent 5,219,690 (contributed under GPL)"
630 ,month="April" 351 ,month="April"
631 ,annotation={ <<
632 'Change in mode' aspect of RCU. Can b <<
633 } <<
634 } 352 }
635 353
636 @Conference{McKenney01a 354 @Conference{McKenney01a
637 ,Author="Paul E. McKenney and Jonathan Appavoo 355 ,Author="Paul E. McKenney and Jonathan Appavoo and Andi Kleen and
638 Orran Krieger and Rusty Russell and Dipankar S 356 Orran Krieger and Rusty Russell and Dipankar Sarma and Maneesh Soni"
639 ,Title="Read-Copy Update" 357 ,Title="Read-Copy Update"
640 ,Booktitle="{Ottawa Linux Symposium}" 358 ,Booktitle="{Ottawa Linux Symposium}"
641 ,Month="July" 359 ,Month="July"
642 ,Year="2001" 360 ,Year="2001"
643 ,note="Available: 361 ,note="Available:
644 \url{http://www.linuxsymposium.org/2001/abstra 362 \url{http://www.linuxsymposium.org/2001/abstracts/readcopy.php}
645 \url{http://www.rdrop.com/users/paulmck/RCU/rc !! 363 \url{http://www.rdrop.com/users/paulmck/rclock/rclock_OLS.2001.05.01c.pdf}
646 [Viewed June 23, 2004]" <<
647 ,annotation={ <<
648 Described RCU, and presented some patc <<
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 traver <<
656 ,month="October" <<
657 ,year="2001" <<
658 ,note="Available: <<
659 \url{http://marc.theaimsgroup.com/?l=linux-ker <<
660 [Viewed June 23, 2004]" <<
661 ,annotation={ <<
662 Memory-barrier and Alpha thread. 100 <<
663 } <<
664 } <<
665 <<
666 @unpublished{Spraul01 <<
667 ,Author="Manfred Spraul" <<
668 ,Title="Re: {RFC:} patch to allow lock-free tr <<
669 ,month="October" <<
670 ,year="2001" <<
671 ,note="Available: <<
672 \url{http://marc.theaimsgroup.com/?l=linux-ker <<
673 [Viewed June 23, 2004]" 364 [Viewed June 23, 2004]"
674 ,annotation={ !! 365 annotation="
675 Suggested burying memory barriers in L !! 366 Described RCU, and presented some patches implementing and using it in
676 primitives. !! 367 the Linux kernel.
677 } !! 368 "
678 } <<
679 <<
680 @unpublished{LinusTorvalds2001a <<
681 ,Author="Linus Torvalds" <<
682 ,Title="{Re:} {[Lse-tech]} {Re:} {RFC:} patch <<
683 ,month="October" <<
684 ,year="2001" <<
685 ,note="Available: <<
686 \url{https://lore.kernel.org/r/Pine.LNX.4.33.0 <<
687 [Viewed August 21, 2004]" <<
688 ,annotation={ <<
689 } <<
690 } <<
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-ker <<
699 [Viewed October 18, 2004]" <<
700 } <<
701 <<
702 @conference{Michael02b <<
703 ,author="Maged M. Michael" <<
704 ,title="High Performance Dynamic Lock-Free Has <<
705 ,Year="2002" <<
706 ,Month="August" <<
707 ,booktitle="{Proceedings of the 14\textsupersc <<
708 Symposium on Parallel <<
709 Algorithms and Architecture}" <<
710 ,pages="73-82" <<
711 ,annotation={ <<
712 Like the title says... <<
713 } <<
714 } 369 }
715 370
716 @Conference{Linder02a 371 @Conference{Linder02a
717 ,Author="Hanna Linder and Dipankar Sarma and M 372 ,Author="Hanna Linder and Dipankar Sarma and Maneesh Soni"
718 ,Title="Scalability of the Directory Entry Cac 373 ,Title="Scalability of the Directory Entry Cache"
719 ,Booktitle="{Ottawa Linux Symposium}" 374 ,Booktitle="{Ottawa Linux Symposium}"
720 ,Month="June" 375 ,Month="June"
721 ,Year="2002" 376 ,Year="2002"
722 ,pages="289-300" 377 ,pages="289-300"
723 ,annotation={ <<
724 Measured scalability of Linux 2.4 kern <<
725 (dcache), and measured some scalabilit <<
726 } <<
727 } 378 }
728 379
729 @Conference{McKenney02a 380 @Conference{McKenney02a
730 ,Author="Paul E. McKenney and Dipankar Sarma a 381 ,Author="Paul E. McKenney and Dipankar Sarma and
731 Andrea Arcangeli and Andi Kleen and Orran Krie 382 Andrea Arcangeli and Andi Kleen and Orran Krieger and Rusty Russell"
732 ,Title="Read-Copy Update" 383 ,Title="Read-Copy Update"
733 ,Booktitle="{Ottawa Linux Symposium}" 384 ,Booktitle="{Ottawa Linux Symposium}"
734 ,Month="June" 385 ,Month="June"
735 ,Year="2002" 386 ,Year="2002"
736 ,pages="338-367" 387 ,pages="338-367"
737 ,note="Available: 388 ,note="Available:
738 \url{http://www.linux.org.uk/~ajh/ols2002_proc 389 \url{http://www.linux.org.uk/~ajh/ols2002_proceedings.pdf.gz}
739 [Viewed June 23, 2004]" 390 [Viewed June 23, 2004]"
740 ,annotation={ <<
741 Presented and compared a number of RCU <<
742 Linux kernel. <<
743 } <<
744 } <<
745 <<
746 @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-ker <<
753 [Viewed June 23, 2004]" <<
754 ,annotation={ <<
755 Compare fastwalk and RCU for dcache. <<
756 } <<
757 } <<
758 <<
759 @unpublished{Barbieri02 <<
760 ,Author="Luca Barbieri" <<
761 ,Title="Re: {[PATCH]} Initial support for stru <<
762 ,month="August" <<
763 ,year="2002" <<
764 ,note="Available: <<
765 \url{http://marc.theaimsgroup.com/?l=linux-ker <<
766 [Viewed: June 23, 2004]" <<
767 ,annotation={ <<
768 Suggested RCU for vfs\_shared\_cred. <<
769 } <<
770 } 391 }
771 392
772 @conference{Michael02a 393 @conference{Michael02a
773 ,author="Maged M. Michael" 394 ,author="Maged M. Michael"
774 ,title="Safe Memory Reclamation for Dynamic Lo 395 ,title="Safe Memory Reclamation for Dynamic Lock-Free Objects Using Atomic
775 Reads and Writes" 396 Reads and Writes"
776 ,Year="2002" 397 ,Year="2002"
777 ,Month="August" 398 ,Month="August"
778 ,booktitle="{Proceedings of the 21\textsupersc 399 ,booktitle="{Proceedings of the 21\textsuperscript{st} Annual ACM
779 Symposium on Principles of Distributed Computi 400 Symposium on Principles of Distributed Computing}"
780 ,pages="21-30" 401 ,pages="21-30"
781 ,annotation={ !! 402 ,annotation="
782 Each thread keeps an array of pointers 403 Each thread keeps an array of pointers to items that it is
783 currently referencing. Sort of an ins 404 currently referencing. Sort of an inside-out garbage collection
784 mechanism, but one that requires the a 405 mechanism, but one that requires the accessing code to explicitly
785 state its needs. Also requires read-s 406 state its needs. Also requires read-side memory barriers on
786 most architectures. 407 most architectures.
787 } !! 408 "
788 } 409 }
789 410
790 @unpublished{Dickins02a !! 411 @conference{Michael02b
791 ,author="Hugh Dickins" !! 412 ,author="Maged M. Michael"
792 ,title="Use RCU for System-V IPC" !! 413 ,title="High Performance Dynamic Lock-Free Hash Tables and List-Based Sets"
793 ,year="2002" !! 414 ,Year="2002"
794 ,month="October" !! 415 ,Month="August"
795 ,note="private communication" !! 416 ,booktitle="{Proceedings of the 14\textsuperscript{th} Annual ACM
>> 417 Symposium on Parallel
>> 418 Algorithms and Architecture}"
>> 419 ,pages="73-82"
>> 420 ,annotation="
>> 421 Like the title says...
>> 422 "
796 } 423 }
797 424
798 @InProceedings{HerlihyLM02 425 @InProceedings{HerlihyLM02
799 ,author={Maurice Herlihy and Victor Luchangco 426 ,author={Maurice Herlihy and Victor Luchangco and Mark Moir}
800 ,title="The Repeat Offender Problem: A Mechani 427 ,title="The Repeat Offender Problem: A Mechanism for Supporting Dynamic-Sized,
801 Lock-Free Data Structures" 428 Lock-Free Data Structures"
802 ,booktitle={Proceedings of 16\textsuperscript{ 429 ,booktitle={Proceedings of 16\textsuperscript{th} International
803 Symposium on Distributed Computing} 430 Symposium on Distributed Computing}
804 ,year=2002 431 ,year=2002
805 ,month="October" 432 ,month="October"
806 ,pages="339-353" 433 ,pages="339-353"
807 } 434 }
808 435
809 @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-ker <<
816 [Viewed June 23, 2004]" <<
817 ,annotation={ <<
818 Performance of dcache RCU on kernbench <<
819 2x, and 4x systems. RCU does no harm, <<
820 } <<
821 } <<
822 <<
823 @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://lore.kernel.org/r/3DB86B05.447E74 <<
830 [Viewed February 15, 2014]" <<
831 ,annotation={ <<
832 Mingming Cao's patch to introduce RCU <<
833 } <<
834 } <<
835 <<
836 @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{https://lore.kernel.org/r/Pine.LNX.4.44.0 <<
843 [Viewed March 13, 2006]" <<
844 ,annotation={ <<
845 Linus suggests replacing brlock with R <<
846 . <<
847 'It's entirely possible that the curre <<
848 by RCU and/or seqlocks, and we could g <<
849 . <<
850 Stephen Hemminger responds by replacin <<
851 } <<
852 } <<
853 <<
854 @article{Appavoo03a 436 @article{Appavoo03a
855 ,author="J. Appavoo and K. Hui and C. A. N. So 437 ,author="J. Appavoo and K. Hui and C. A. N. Soules and R. W. Wisniewski and
856 D. M. {Da Silva} and O. Krieger and M. A. Ausl 438 D. M. {Da Silva} and O. Krieger and M. A. Auslander and D. J. Edelsohn and
857 B. Gamsa and G. R. Ganger and P. McKenney and 439 B. Gamsa and G. R. Ganger and P. McKenney and M. Ostrowski and
858 B. Rosenburg and M. Stumm and J. Xenidis" 440 B. Rosenburg and M. Stumm and J. Xenidis"
859 ,title="Enabling Autonomic Behavior in Systems 441 ,title="Enabling Autonomic Behavior in Systems Software With Hot Swapping"
860 ,Year="2003" 442 ,Year="2003"
861 ,Month="January" 443 ,Month="January"
862 ,journal="IBM Systems Journal" 444 ,journal="IBM Systems Journal"
863 ,volume="42" 445 ,volume="42"
864 ,number="1" 446 ,number="1"
865 ,pages="60-76" 447 ,pages="60-76"
866 ,annotation={ <<
867 Use of RCU to enable hot-swapping for <<
868 } <<
869 } <<
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" <<
877 ,annotation={ <<
878 Described the relationship of the VM/X <<
879 } <<
880 } 448 }
881 449
882 @Conference{Arcangeli03 450 @Conference{Arcangeli03
883 ,Author="Andrea Arcangeli and Mingming Cao and 451 ,Author="Andrea Arcangeli and Mingming Cao and Paul E. McKenney and
884 Dipankar Sarma" 452 Dipankar Sarma"
885 ,Title="Using Read-Copy Update Techniques for 453 ,Title="Using Read-Copy Update Techniques for {System V IPC} in the
886 {Linux} 2.5 Kernel" 454 {Linux} 2.5 Kernel"
887 ,Booktitle="Proceedings of the 2003 USENIX Ann 455 ,Booktitle="Proceedings of the 2003 USENIX Annual Technical Conference
888 (FREENIX Track)" 456 (FREENIX Track)"
889 ,Publisher="USENIX Association" 457 ,Publisher="USENIX Association"
890 ,year="2003" 458 ,year="2003"
891 ,month="June" 459 ,month="June"
892 ,pages="297-310" 460 ,pages="297-310"
893 ,annotation={ <<
894 Compared updated RCU implementations f <<
895 described System V IPC use of RCU, inc <<
896 performance improvements. <<
897 http://www.rdrop.com/users/paulmck/RCU <<
898 } <<
899 } <<
900 <<
901 @Conference{Soules03a <<
902 ,Author="Craig A. N. Soules and Jonathan Appav <<
903 Dilma {Da Silva} and Gregory R. Ganger and Orr <<
904 Michael Stumm and Robert W. Wisniewski and Mar <<
905 Michal Ostrowski and Bryan Rosenburg and Jimi <<
906 ,Title="System Support for Online Reconfigurat <<
907 ,Booktitle="Proceedings of the 2003 USENIX Ann <<
908 ,Publisher="USENIX Association" <<
909 ,year="2003" <<
910 ,month="June" <<
911 ,pages="141-154" <<
912 } 461 }
913 462
914 @article{McKenney03a 463 @article{McKenney03a
915 ,author="Paul E. McKenney" 464 ,author="Paul E. McKenney"
916 ,title="Using {RCU} in the {Linux} 2.5 Kernel" 465 ,title="Using {RCU} in the {Linux} 2.5 Kernel"
917 ,Year="2003" 466 ,Year="2003"
918 ,Month="October" 467 ,Month="October"
919 ,journal="Linux Journal" 468 ,journal="Linux Journal"
920 ,volume="1" 469 ,volume="1"
921 ,number="114" 470 ,number="114"
922 ,pages="18-26" 471 ,pages="18-26"
923 ,note="Available: <<
924 \url{http://www.linuxjournal.com/article/6993} <<
925 [Viewed November 14, 2007]" <<
926 ,annotation={ <<
927 Reader-friendly intro to RCU, with the <<
928 cartoon. <<
929 } <<
930 } <<
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.ib <<
938 ,annotation={ <<
939 dipankar/ct.2004.03.27/RCUll.2003.12.2 <<
940 } <<
941 } 472 }
942 473
943 @techreport{Friedberg03a 474 @techreport{Friedberg03a
944 ,author="Stuart A. Friedberg" 475 ,author="Stuart A. Friedberg"
945 ,title="Lock-Free Wild Card Search Data Struct 476 ,title="Lock-Free Wild Card Search Data Structure and Method"
946 ,institution="US Patent and Trademark Office" 477 ,institution="US Patent and Trademark Office"
947 ,address="Washington, DC" 478 ,address="Washington, DC"
948 ,year="2003" 479 ,year="2003"
949 ,number="US Patent 6,662,184" !! 480 ,number="US Patent 6,662,184 (contributed under GPL)"
950 ,month="December" 481 ,month="December"
951 ,pages="112" 482 ,pages="112"
952 ,annotation={ <<
953 Applies RCU to a wildcard-search Patri <<
954 synchronization-free lookup. RCU is u <<
955 for a grace period before freeing them <<
956 } <<
957 } 483 }
958 484
959 @article{McKenney04a 485 @article{McKenney04a
960 ,author="Paul E. McKenney and Dipankar Sarma a 486 ,author="Paul E. McKenney and Dipankar Sarma and Maneesh Soni"
961 ,title="Scaling dcache with {RCU}" 487 ,title="Scaling dcache with {RCU}"
962 ,Year="2004" 488 ,Year="2004"
963 ,Month="January" 489 ,Month="January"
964 ,journal="Linux Journal" 490 ,journal="Linux Journal"
965 ,volume="1" 491 ,volume="1"
966 ,number="118" 492 ,number="118"
967 ,pages="38-46" 493 ,pages="38-46"
968 ,annotation={ <<
969 Reader friendly intro to dcache and RC <<
970 http://www.linuxjournal.com/node/7124 <<
971 [Viewed December 26, 2010] <<
972 } <<
973 } 494 }
974 495
975 @Conference{McKenney04b 496 @Conference{McKenney04b
976 ,Author="Paul E. McKenney" 497 ,Author="Paul E. McKenney"
977 ,Title="{RCU} vs. Locking Performance on Diffe 498 ,Title="{RCU} vs. Locking Performance on Different {CPUs}"
978 ,Booktitle="{linux.conf.au}" 499 ,Booktitle="{linux.conf.au}"
979 ,Month="January" 500 ,Month="January"
980 ,Year="2004" 501 ,Year="2004"
981 ,Address="Adelaide, Australia" 502 ,Address="Adelaide, Australia"
982 ,note="Available: 503 ,note="Available:
983 \url{http://www.linux.org.au/conf/2004/abstrac 504 \url{http://www.linux.org.au/conf/2004/abstracts.html#90}
984 \url{http://www.rdrop.com/users/paulmck/RCU/lo !! 505 \url{http://www.rdrop.com/users/paulmck/rclock/lockperf.2004.01.17a.pdf}
985 [Viewed June 23, 2004]" 506 [Viewed June 23, 2004]"
986 ,annotation={ <<
987 Compares performance of RCU to that of <<
988 over a number of CPUs (x86, Opteron, I <<
989 } <<
990 } <<
991 <<
992 @unpublished{Sarma04a <<
993 ,Author="Dipankar Sarma" <<
994 ,Title="{[PATCH]} {RCU} for low latency (exper <<
995 ,month="March" <<
996 ,year="2004" <<
997 ,note="\url{http://marc.theaimsgroup.com/?l=li <<
998 ,annotation={ <<
999 Head of thread: dipankar/2004.03.23/rc <<
1000 } <<
1001 } <<
1002 <<
1003 @unpublished{Sarma04b <<
1004 ,Author="Dipankar Sarma" <<
1005 ,Title="Re: {[PATCH]} {RCU} for low latency ( <<
1006 ,month="March" <<
1007 ,year="2004" <<
1008 ,note="\url{http://marc.theaimsgroup.com/?l=l <<
1009 ,annotation={ <<
1010 dipankar/rcuth.2004.03.24/rcu-throttl <<
1011 } <<
1012 } <<
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-ke <<
1021 [Viewed June 23, 2004]" <<
1022 ,annotation={ <<
1023 Hierarchical-bitmap patch for RCU inf <<
1024 } <<
1025 } <<
1026 <<
1027 @unpublished{Steiner04a <<
1028 ,Author="Jack Steiner" <<
1029 ,Title="Re: [Lse-tech] [RFC, PATCH] 1/5 rcu l <<
1030 Add per-cpu batch counter" <<
1031 ,month="May" <<
1032 ,year="2004" <<
1033 ,note="Available: <<
1034 \url{http://marc.theaimsgroup.com/?l=linux-ke <<
1035 [Viewed June 23, 2004]" <<
1036 ,annotation={ <<
1037 RCU runs reasonably on a 512-CPU SGI <<
1038 which may be found at: <<
1039 https://lore.kernel.org/r/40AC9823.60 <<
1040 https://lore.kernel.org/r/Pine.LNX.4. <<
1041 https://lore.kernel.org/r/20040525053 <<
1042 https://lore.kernel.org/r/20040525053 <<
1043 https://lore.kernel.org/r/200 <<
1044 https://lore.kernel.org/r/20040525053 <<
1045 https://lore.kernel.org/r/20040525053 <<
1046 https://lore.kernel.org/r/20040525053 <<
1047 https://lore.kernel.org/r/20040525053 <<
1048 } <<
1049 } <<
1050 <<
1051 @Conference{Sarma04c <<
1052 ,Author="Dipankar Sarma and Paul E. McKenney" <<
1053 ,Title="Making {RCU} Safe for Deep Sub-Millis <<
1054 Realtime Applications" <<
1055 ,Booktitle="Proceedings of the 2004 USENIX An <<
1056 (FREENIX Track)" <<
1057 ,Publisher="USENIX Association" <<
1058 ,year="2004" <<
1059 ,month="June" <<
1060 ,pages="182-191" <<
1061 ,annotation={ <<
1062 Describes and compares a number of mo <<
1063 implementation that make it friendly <<
1064 https://www.usenix.org/conference/200 <<
1065 [Viewed July 26, 2012] <<
1066 } <<
1067 } <<
1068 <<
1069 @article{MagedMichael04a <<
1070 ,author="Maged M. Michael" <<
1071 ,title="Hazard Pointers: Safe Memory Reclamat <<
1072 ,Year="2004" <<
1073 ,Month="June" <<
1074 ,journal="IEEE Transactions on Parallel and D <<
1075 ,volume="15" <<
1076 ,number="6" <<
1077 ,pages="491-504" <<
1078 ,url="Available: <<
1079 \url{http://www.research.ibm.com/people/m/mic <<
1080 [Viewed March 1, 2005]" <<
1081 ,annotation={ <<
1082 New canonical hazard-pointer citation <<
1083 } <<
1084 } 507 }
1085 508
1086 @phdthesis{PaulEdwardMcKenneyPhD 509 @phdthesis{PaulEdwardMcKenneyPhD
1087 ,author="Paul E. McKenney" 510 ,author="Paul E. McKenney"
1088 ,title="Exploiting Deferred Destruction: 511 ,title="Exploiting Deferred Destruction:
1089 An Analysis of Read-Copy-Update Techniques 512 An Analysis of Read-Copy-Update Techniques
1090 in Operating System Kernels" 513 in Operating System Kernels"
1091 ,school="OGI School of Science and Engineerin 514 ,school="OGI School of Science and Engineering at
1092 Oregon Health and Sciences University" 515 Oregon Health and Sciences University"
1093 ,year="2004" 516 ,year="2004"
1094 ,annotation={ <<
1095 Describes RCU implementations and pre <<
1096 corresponding to common uses of RCU i <<
1097 kernels. <<
1098 http://www.rdrop.com/users/paulmck/RC <<
1099 [Viewed October 15, 2004] <<
1100 } <<
1101 } <<
1102 <<
1103 @unpublished{PaulEMcKenney2004rcu:dereference <<
1104 ,Author="Dipankar Sarma" <<
1105 ,Title="{Re: RCU : Abstracted RCU dereferenci <<
1106 ,month="August" <<
1107 ,year="2004" <<
1108 ,note="Available: <<
1109 \url{https://lore.kernel.org/r/20040807192424 <<
1110 [Viewed June 8, 2010]" <<
1111 ,annotation={ <<
1112 Introduce rcu_dereference(). <<
1113 } <<
1114 } <<
1115 <<
1116 @unpublished{JimHouston04a <<
1117 ,Author="Jim Houston" <<
1118 ,Title="{[RFC\&PATCH] Alternative {RCU} imple <<
1119 ,month="August" <<
1120 ,year="2004" <<
1121 ,note="Available: <<
1122 \url{https://lore.kernel.org/r/1093873222.984 <<
1123 [Viewed February 17, 2005]" <<
1124 ,annotation={ <<
1125 Uses active code in rcu_read_lock() a <<
1126 make RCU happen, allowing RCU to func <<
1127 receive a scheduling-clock interrupt. <<
1128 } <<
1129 } <<
1130 <<
1131 @unpublished{TomHart04a <<
1132 ,Author="Thomas E. Hart" <<
1133 ,Title="Master's Thesis: Applying Lock-free T <<
1134 ,month="October" <<
1135 ,year="2004" <<
1136 ,note="Available: 517 ,note="Available:
1137 \url{http://www.cs.toronto.edu/~tomhart/maste !! 518 \url{http://www.rdrop.com/users/paulmck/RCU/RCUdissertation.2004.07.14e1.pdf}
1138 [Viewed October 15, 2004]" 519 [Viewed October 15, 2004]"
1139 ,annotation={ <<
1140 Proposes comparing RCU to lock-free m <<
1141 } <<
1142 } <<
1143 <<
1144 @unpublished{Vaddagiri04a <<
1145 ,Author="Srivatsa Vaddagiri" <<
1146 ,Title="Subject: [RFC] Use RCU for tcp\_ehash <<
1147 ,month="October" <<
1148 ,year="2004" <<
1149 ,note="Available: <<
1150 \url{http://marc.theaimsgroup.com/?t=10939573 <<
1151 [Viewed October 18, 2004]" <<
1152 ,annotation={ <<
1153 Srivatsa's RCU patch for tcp_ehash lo <<
1154 } <<
1155 } <<
1156 <<
1157 @unpublished{Thirumalai04a <<
1158 ,Author="Ravikiran Thirumalai" <<
1159 ,Title="Subject: [patchset] Lockfree fd looku <<
1160 ,month="October" <<
1161 ,year="2004" <<
1162 ,note="Available: <<
1163 \url{http://marc.theaimsgroup.com/?t=10914421 <<
1164 [Viewed October 18, 2004]" <<
1165 ,annotation={ <<
1166 Ravikiran's lockfree FD patch. <<
1167 } <<
1168 } <<
1169 <<
1170 @unpublished{Thirumalai04b <<
1171 ,Author="Ravikiran Thirumalai" <<
1172 ,Title="Subject: Re: [patchset] Lockfree fd l <<
1173 ,month="October" <<
1174 ,year="2004" <<
1175 ,note="Available: <<
1176 \url{http://marc.theaimsgroup.com/?l=linux-ke <<
1177 [Viewed October 18, 2004]" <<
1178 ,annotation={ <<
1179 Ravikiran's lockfree FD patch. <<
1180 } <<
1181 } <<
1182 <<
1183 @unpublished{PaulEMcKenney2004rcu:assign:poin <<
1184 ,Author="Paul E. McKenney" <<
1185 ,Title="{[PATCH 1/3] RCU: \url{rcu_assign_poi <<
1186 ,month="October" <<
1187 ,year="2004" <<
1188 ,note="Available: <<
1189 \url{https://lore.kernel.org/r/20041023202723 <<
1190 [Viewed June 8, 2010]" <<
1191 ,annotation={ <<
1192 Introduce rcu_assign_pointer(). <<
1193 } <<
1194 } 520 }
1195 521
1196 @unpublished{JamesMorris04a !! 522 @Conference{Sarma04c
1197 ,Author="James Morris" !! 523 ,Author="Dipankar Sarma and Paul E. McKenney"
1198 ,Title="{[PATCH 2/3] SELinux} scalability - c !! 524 ,Title="Making RCU Safe for Deep Sub-Millisecond Response Realtime Applications"
1199 ,day="15" !! 525 ,Booktitle="Proceedings of the 2004 USENIX Annual Technical Conference
1200 ,month="November" !! 526 (FREENIX Track)"
>> 527 ,Publisher="USENIX Association"
1201 ,year="2004" 528 ,year="2004"
1202 ,note="\url{http://marc.theaimsgroup.com/?l=l !! 529 ,month="June"
1203 ,annotation={ !! 530 ,pages="182-191"
1204 James Morris posts Kaigai Kohei's pat <<
1205 [Viewed December 10, 2004] <<
1206 Kaigai's patch is at https://lore.ker <<
1207 } <<
1208 } 531 }
1209 532
1210 @unpublished{JamesMorris04b 533 @unpublished{JamesMorris04b
1211 ,Author="James Morris" 534 ,Author="James Morris"
1212 ,Title="Recent Developments in {SELinux} Kern 535 ,Title="Recent Developments in {SELinux} Kernel Performance"
1213 ,month="December" 536 ,month="December"
1214 ,year="2004" 537 ,year="2004"
1215 ,note="Available: 538 ,note="Available:
1216 \url{http://www.livejournal.com/users/james_m 539 \url{http://www.livejournal.com/users/james_morris/2153.html}
1217 [Viewed December 10, 2004]" 540 [Viewed December 10, 2004]"
1218 ,annotation={ <<
1219 RCU helps SELinux performance. ;-) <<
1220 } <<
1221 } <<
1222 <<
1223 @unpublished{PaulMcKenney2005RCUSemantics <<
1224 ,Author="Paul E. McKenney and Jonathan Walpol <<
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/r <<
1231 [Viewed December 6, 2009]" <<
1232 ,annotation={ <<
1233 Early derivation of RCU semantics. <<
1234 } <<
1235 } <<
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{https://lore.kernel.org/r/20050318002026 <<
1245 [Viewed September 5, 2005]" <<
1246 ,annotation={ <<
1247 First posting showing how RCU can be <<
1248 preemptible RCU read side critical se <<
1249 } <<
1250 } <<
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{https://lore.kernel.org/r/Pine.OSF.4.05. <<
1260 [Viewed March 30, 2006]" <<
1261 ,annotation={ <<
1262 Esben Neilsen suggests read-side supp <<
1263 processing for crude-but-workable rea <<
1264 is indefinite grace periods... But t <<
1265 and testing. <<
1266 } <<
1267 } <<
1268 <<
1269 @unpublished{TomHart05a <<
1270 ,Author="Thomas E. Hart and Paul E. McKenney <<
1271 ,Title="Efficient Memory Reclamation is Neces <<
1272 Data Structures" <<
1273 ,month="March" <<
1274 ,year="2005" <<
1275 ,note="Available: <<
1276 \url{ftp://ftp.cs.toronto.edu/csrg-technical- <<
1277 [Viewed March 4, 2005]" <<
1278 ,annotation={ <<
1279 Comparison of RCU, QBSR, and EBSR. R <<
1280 workloads. ;-) <<
1281 } <<
1282 } <<
1283 <<
1284 @unpublished{JonCorbet2005DeprecateSyncKernel <<
1285 ,Author="Jonathan Corbet" <<
1286 ,Title="API change: synchronize_kernel() depr <<
1287 ,month="May" <<
1288 ,day="3" <<
1289 ,year="2005" <<
1290 ,note="Available: <<
1291 \url{http://lwn.net/Articles/134484/} <<
1292 [Viewed May 3, 2005]" <<
1293 ,annotation={ <<
1294 Jon Corbet describes deprecation of s <<
1295 in favor of synchronize_rcu() and syn <<
1296 } <<
1297 } 541 }
1298 542
1299 @unpublished{PaulMcKenney05a 543 @unpublished{PaulMcKenney05a
1300 ,Author="Paul E. McKenney" 544 ,Author="Paul E. McKenney"
1301 ,Title="{[RFC]} {RCU} and {CONFIG\_PREEMPT\_R 545 ,Title="{[RFC]} {RCU} and {CONFIG\_PREEMPT\_RT} progress"
1302 ,month="May" 546 ,month="May"
1303 ,year="2005" 547 ,year="2005"
1304 ,note="Available: 548 ,note="Available:
1305 \url{https://lore.kernel.org/r/20050510012444 !! 549 \url{http://lkml.org/lkml/2005/5/9/185}
1306 [Viewed May 13, 2005]" 550 [Viewed May 13, 2005]"
1307 ,annotation={ !! 551 ,annotation="
1308 First publication of working lock-bas 552 First publication of working lock-based deferred free patches
1309 for the CONFIG_PREEMPT_RT environment 553 for the CONFIG_PREEMPT_RT environment.
1310 } !! 554 "
1311 } 555 }
1312 556
1313 @conference{PaulMcKenney05b 557 @conference{PaulMcKenney05b
1314 ,Author="Paul E. McKenney and Dipankar Sarma" 558 ,Author="Paul E. McKenney and Dipankar Sarma"
1315 ,Title="Towards Hard Realtime Response from t !! 559 ,Title="Towards Hard Realtime Response from the Linux Kernel on SMP Hardware"
1316 ,Booktitle="linux.conf.au 2005" 560 ,Booktitle="linux.conf.au 2005"
1317 ,month="April" 561 ,month="April"
1318 ,year="2005" 562 ,year="2005"
1319 ,address="Canberra, Australia" 563 ,address="Canberra, Australia"
1320 ,note="Available: 564 ,note="Available:
1321 \url{http://www.rdrop.com/users/paulmck/RCU/r 565 \url{http://www.rdrop.com/users/paulmck/RCU/realtimeRCU.2005.04.23a.pdf}
1322 [Viewed May 13, 2005]" 566 [Viewed May 13, 2005]"
1323 ,annotation={ !! 567 ,annotation="
1324 Realtime turns into making RCU yet mo 568 Realtime turns into making RCU yet more realtime friendly.
1325 http://lca2005.linux.org.au/Papers/Pa !! 569 "
1326 } <<
1327 } <<
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]" <<
1337 ,annotation={ <<
1338 Paul McKenney's home page. <<
1339 } <<
1340 } <<
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]" <<
1350 ,annotation={ <<
1351 Paul McKenney's RCU page. <<
1352 } <<
1353 } <<
1354 <<
1355 @unpublished{JosephSeigh2005a <<
1356 ,Author="Joseph Seigh" <<
1357 ,Title="{RCU}+{SMR} (hazard pointers)" <<
1358 ,month="July" <<
1359 ,year="2005" <<
1360 ,note="Personal communication" <<
1361 ,annotation={ <<
1362 Joe Seigh announcing his atomic-ptr-p <<
1363 http://sourceforge.net/projects/atomi <<
1364 } <<
1365 } <<
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-p <<
1375 [Viewed August 8, 2005]" <<
1376 ,annotation={ <<
1377 Joe Seigh's atomic-ptr-plus project. <<
1378 } <<
1379 } <<
1380 <<
1381 @unpublished{PaulMcKenney2005c <<
1382 ,Author="Paul E.McKenney" <<
1383 ,Title="{[RFC,PATCH] RCU} and {CONFIG\_PREEMP <<
1384 ,month="August" <<
1385 ,day="1" <<
1386 ,year="2005" <<
1387 ,note="Available: <<
1388 \url{https://lore.kernel.org/r/20050801171137 <<
1389 [Viewed March 14, 2006]" <<
1390 ,annotation={ <<
1391 First operating counter-based realtim <<
1392 } <<
1393 } <<
1394 <<
1395 @unpublished{PaulMcKenney2005d <<
1396 ,Author="Paul E. McKenney" <<
1397 ,Title="Re: [Fwd: Re: [patch] Real-Time Preem <<
1398 ,month="August" <<
1399 ,day="8" <<
1400 ,year="2005" <<
1401 ,note="Available: <<
1402 \url{https://lore.kernel.org/r/20050808144216 <<
1403 [Viewed March 14, 2006]" <<
1404 ,annotation={ <<
1405 First operating counter-based realtim <<
1406 but fixed so that various unusual com <<
1407 parameters all function properly. <<
1408 } <<
1409 } <<
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{https://lore.kernel.org/r/20051001182056 <<
1419 [Viewed March 14, 2006]" <<
1420 ,annotation={ <<
1421 First rcutorture patch. <<
1422 } <<
1423 } <<
1424 <<
1425 @unpublished{DavidSMiller2006HashedLocking <<
1426 ,Author="David S. Miller" <<
1427 ,Title="Re: [{PATCH}, {RFC}] {RCU} : {OOM} av <<
1428 ,month="January" <<
1429 ,day="6" <<
1430 ,year="2006" <<
1431 ,note="Available: <<
1432 \url{https://lore.kernel.org/r/20060106.23105 <<
1433 [Viewed February 29, 2012]" <<
1434 ,annotation={ <<
1435 David Miller's view on hashed arrays <<
1436 like it, but time he saw an opportuni <<
1437 something else always proved superior <<
1438 } <<
1439 } 570 }
1440 571
1441 @conference{ThomasEHart2006a 572 @conference{ThomasEHart2006a
1442 ,Author="Thomas E. Hart and Paul E. McKenney 573 ,Author="Thomas E. Hart and Paul E. McKenney and Angela Demke Brown"
1443 ,Title="Making Lockless Synchronization Fast: 574 ,Title="Making Lockless Synchronization Fast: Performance Implications
1444 of Memory Reclamation" 575 of Memory Reclamation"
1445 ,Booktitle="20\textsuperscript{th} {IEEE} Int 576 ,Booktitle="20\textsuperscript{th} {IEEE} International Parallel and
1446 Distributed Processing Symposium" 577 Distributed Processing Symposium"
1447 ,month="April" 578 ,month="April"
1448 ,year="2006" 579 ,year="2006"
1449 ,day="25-29" 580 ,day="25-29"
1450 ,address="Rhodes, Greece" 581 ,address="Rhodes, Greece"
1451 ,note="Available: !! 582 ,annotation="
1452 \url{http://www.rdrop.com/users/paulmck/RCU/h !! 583 Compares QSBR (AKA "classic RCU"), HPBR, EBR, and lock-free
1453 [Viewed April 28, 2008]" !! 584 reference counting.
1454 ,annotation={ !! 585 "
1455 Compares QSBR, HPBR, EBR, and lock-fr <<
1456 http://www.cs.toronto.edu/~tomhart/pe <<
1457 } <<
1458 } <<
1459 <<
1460 @unpublished{NickPiggin2006radixtree <<
1461 ,Author="Nick Piggin" <<
1462 ,Title="[patch 3/3] radix-tree: {RCU} lockles <<
1463 ,month="June" <<
1464 ,day="20" <<
1465 ,year="2006" <<
1466 ,note="Available: <<
1467 \url{https://lore.kernel.org/r/20060408134707 <<
1468 [Viewed March 25, 2008]" <<
1469 ,annotation={ <<
1470 RCU-protected radix tree. <<
1471 } <<
1472 } 586 }
1473 587
1474 @Conference{PaulEMcKenney2006b 588 @Conference{PaulEMcKenney2006b
1475 ,Author="Paul E. McKenney and Dipankar Sarma 589 ,Author="Paul E. McKenney and Dipankar Sarma and Ingo Molnar and
1476 Suparna Bhattacharya" 590 Suparna Bhattacharya"
1477 ,Title="Extending {RCU} for Realtime and Embe !! 591 ,Title="Extending RCU for Realtime and Embedded Workloads"
1478 ,Booktitle="{Ottawa Linux Symposium}" 592 ,Booktitle="{Ottawa Linux Symposium}"
1479 ,Month="July" 593 ,Month="July"
1480 ,Year="2006" 594 ,Year="2006"
1481 ,pages="v2 123-138" 595 ,pages="v2 123-138"
1482 ,note="Available: 596 ,note="Available:
1483 \url{http://www.linuxsymposium.org/2006/view_ 597 \url{http://www.linuxsymposium.org/2006/view_abstract.php?content_key=184}
1484 \url{http://www.rdrop.com/users/paulmck/RCU/O 598 \url{http://www.rdrop.com/users/paulmck/RCU/OLSrtRCU.2006.08.11a.pdf}
1485 [Viewed January 1, 2007]" 599 [Viewed January 1, 2007]"
1486 ,annotation={ !! 600 ,annotation="
1487 Described how to improve the -rt impl 601 Described how to improve the -rt implementation of realtime RCU.
1488 } !! 602 "
1489 } <<
1490 <<
1491 @unpublished{WikipediaRCU <<
1492 ,Author="Paul E. McKenney and Chris Purcell a <<
1493 Gaius Cornelius and Qwertyus and Neil Conway <<
1494 Canis Rufus and Zoicon5 and Anome and Hal Eis <<
1495 ,Title="Read-Copy Update" <<
1496 ,month="July" <<
1497 ,day="8" <<
1498 ,year="2006" <<
1499 ,note="\url{https://en.wikipedia.org/wiki/Rea <<
1500 ,annotation={ <<
1501 Wikipedia RCU page as of July 8 2006. <<
1502 [Viewed August 21, 2006] <<
1503 } <<
1504 } <<
1505 <<
1506 @Conference{NickPiggin2006LocklessPageCache <<
1507 ,Author="Nick Piggin" <<
1508 ,Title="A Lockless Pagecache in Linux---Intro <<
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_ <<
1515 [Viewed January 11, 2009]" <<
1516 ,annotation={ <<
1517 Uses RCU-protected radix tree for a l <<
1518 } <<
1519 } 603 }
1520 604
1521 @unpublished{PaulEMcKenney2006c 605 @unpublished{PaulEMcKenney2006c
1522 ,Author="Paul E. McKenney" 606 ,Author="Paul E. McKenney"
1523 ,Title="Sleepable {RCU}" 607 ,Title="Sleepable {RCU}"
1524 ,month="October" 608 ,month="October"
1525 ,day="9" 609 ,day="9"
1526 ,year="2006" 610 ,year="2006"
1527 ,note="Available: 611 ,note="Available:
1528 \url{http://lwn.net/Articles/202847/} 612 \url{http://lwn.net/Articles/202847/}
1529 Revised: 613 Revised:
1530 \url{http://www.rdrop.com/users/paulmck/RCU/s 614 \url{http://www.rdrop.com/users/paulmck/RCU/srcu.2007.01.14a.pdf}
1531 [Viewed August 21, 2006]" 615 [Viewed August 21, 2006]"
1532 ,annotation={ !! 616 ,annotation="
1533 LWN article introducing SRCU. 617 LWN article introducing SRCU.
1534 } !! 618 "
1535 } 619 }
1536 620
1537 @unpublished{RobertOlsson2006a 621 @unpublished{RobertOlsson2006a
1538 ,Author="Robert Olsson and Stefan Nilsson" 622 ,Author="Robert Olsson and Stefan Nilsson"
1539 ,Title="{TRASH}: A dynamic {LC}-trie and hash 623 ,Title="{TRASH}: A dynamic {LC}-trie and hash data structure"
1540 ,month="August" 624 ,month="August"
1541 ,day="18" 625 ,day="18"
1542 ,year="2006" 626 ,year="2006"
1543 ,note="\url{http://www.nada.kth.se/~snilsson/ <<
1544 ,annotation={ <<
1545 RCU-protected dynamic trie-hash combi <<
1546 [Viewed March 4, 2011] <<
1547 } <<
1548 } <<
1549 <<
1550 @unpublished{ChristophHellwig2006RCU2SRCU <<
1551 ,Author="Christoph Hellwig" <<
1552 ,Title="Re: {[-mm PATCH 1/4]} {RCU}: split cl <<
1553 ,month="September" <<
1554 ,day="28" <<
1555 ,year="2006" <<
1556 ,note="Available: <<
1557 \url{https://lore.kernel.org/r/20060928142616 <<
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/l <<
1568 [Viewed January 14, 2007]" <<
1569 ,annotation={ <<
1570 Paul McKenney's RCU page showing grap <<
1571 usage of RCU. <<
1572 } <<
1573 } <<
1574 <<
1575 @unpublished{PaulEMcKenneyRCUusageRawDataPage <<
1576 ,Author="Paul E. McKenney" <<
1577 ,Title="Read-Copy Update {(RCU)} Usage in {Li <<
1578 ,month="October" <<
1579 ,year="2006" <<
1580 ,note="Available: 627 ,note="Available:
1581 \url{http://www.rdrop.com/users/paulmck/RCU/l !! 628 \url{http://www.nada.kth.se/~snilsson/public/papers/trash/trash.pdf}
1582 [Viewed January 14, 2007]" !! 629 [Viewed February 24, 2007]"
1583 ,annotation={ !! 630 ,annotation="
1584 Paul McKenney's RCU page showing Linu <<
1585 form, with links to corresponding csc <<
1586 } <<
1587 } <<
1588 <<
1589 @unpublished{GauthamShenoy2006RCUrwlock <<
1590 ,Author="Gautham R. Shenoy" <<
1591 ,Title="[PATCH 4/5] lock\_cpu\_hotplug: Redes <<
1592 ,month="October" <<
1593 ,year="2006" <<
1594 ,day=26 <<
1595 ,note="Available: <<
1596 \url{https://lore.kernel.org/r/20061026105731 <<
1597 [Viewed January 26, 2009]" <<
1598 ,annotation={ <<
1599 RCU-based reader-writer lock that all <<
1600 no memory barriers or atomic instruct <<
1601 If writer do show up, readers must of <<
1602 the semantics of reader-writer lockin <<
1603 lock. <<
1604 } <<
1605 } <<
1606 <<
1607 @unpublished{JensAxboe2006SlowSRCU <<
1608 ,Author="Jens Axboe" <<
1609 ,Title="Re: [patch] cpufreq: mark \url{cpufre <<
1610 \url{core_initcall_sync}" <<
1611 ,month="November" <<
1612 ,year="2006" <<
1613 ,day=17 <<
1614 ,note="Available: <<
1615 \url{https://lore.kernel.org/r/20061117092925 <<
1616 [Viewed May 28, 2007]" <<
1617 ,annotation={ <<
1618 SRCU's grace periods are too slow for <<
1619 factor-of-three speedup. <<
1620 Sped-up version of SRCU at https://lo <<
1621 } <<
1622 } <<
1623 <<
1624 @unpublished{OlegNesterov2006QRCU <<
1625 ,Author="Oleg Nesterov" <<
1626 ,Title="Re: [patch] cpufreq: mark {\tt cpufre <<
1627 {\tt core\_initcall\_sync}" <<
1628 ,month="November" <<
1629 ,year="2006" <<
1630 ,day=19 <<
1631 ,note="Available: <<
1632 \url{https://lore.kernel.org/r/20061119190027 <<
1633 [Viewed May 28, 2007]" <<
1634 ,annotation={ <<
1635 First cut of QRCU. Expanded/correcte <<
1636 Used to be OlegNesterov2007QRCU, now <<
1637 } <<
1638 } <<
1639 <<
1640 @unpublished{OlegNesterov2006aQRCU <<
1641 ,Author="Oleg Nesterov" <<
1642 ,Title="Re: [RFC, PATCH 1/2] qrcu: {"quick"} <<
1643 ,month="November" <<
1644 ,year="2006" <<
1645 ,day=30 <<
1646 ,note="Available: <<
1647 \url{https://lore.kernel.org/r/20061130015714 <<
1648 [Viewed November 26, 2008]" <<
1649 ,annotation={ <<
1650 Expanded/corrected version of QRCU. <<
1651 Used to be OlegNesterov2007aQRCU, now <<
1652 } <<
1653 } <<
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]" <<
1664 ,annotation={ <<
1665 Using RCU as a pure delay leads to a <<
1666 the Linux kernel. <<
1667 } <<
1668 } <<
1669 <<
1670 @inproceedings{ChrisMatthews2006ClusteredObje <<
1671 ,author = {Matthews, Chris and Coady, Yvonne <<
1672 ,title = {Portability events: a programming m <<
1673 ,booktitle = {PLOS '06: Proceedings of the 3r <<
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.12 <<
1679 ,publisher = {ACM} <<
1680 ,address = {New York, NY, USA} <<
1681 ,annotation={ <<
1682 Uses K42's RCU-like functionality to <<
1683 lifetimes. <<
1684 } <<
1685 } <<
1686 <<
1687 @article{DilmaDaSilva2006K42 <<
1688 ,author = {Silva, Dilma Da and Krieger, Orran <<
1689 ,title = {K42: an infrastructure for operatin <<
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.11 <<
1697 ,publisher = {ACM} <<
1698 ,address = {New York, NY, USA} <<
1699 ,annotation={ <<
1700 Describes relationship of K42 generat <<
1701 } <<
1702 } <<
1703 <<
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 lis <<
1708 ,month="January" <<
1709 ,year="2007" <<
1710 ,day=3 <<
1711 ,note="Available: <<
1712 \url{https://lore.kernel.org/r/20070103152738 <<
1713 [Viewed May 28, 2007]" <<
1714 ,annotation={ <<
1715 Patch for list_splice_rcu(). <<
1716 } <<
1717 } <<
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]" <<
1728 ,annotation={ <<
1729 LWN article introducing the rcu_barri <<
1730 } <<
1731 } <<
1732 <<
1733 @unpublished{PeterZijlstra2007SyncBarrier <<
1734 ,Author="Peter Zijlstra and Ingo Molnar" <<
1735 ,Title="{[PATCH 3/7]} barrier: a scalable syn <<
1736 ,month="January" <<
1737 ,year="2007" <<
1738 ,day=28 <<
1739 ,note="Available: <<
1740 \url{https://lore.kernel.org/r/20070128120509 <<
1741 [Viewed March 27, 2008]" <<
1742 ,annotation={ <<
1743 RCU-like implementation for frequent <<
1744 Subsumed into QRCU. Maybe... <<
1745 } <<
1746 } <<
1747 <<
1748 @unpublished{PaulEMcKenney2007BoostRCU <<
1749 ,Author="Paul E. McKenney" <<
1750 ,Title="Priority-Boosting {RCU} Read-Side Cri <<
1751 ,month="February" <<
1752 ,day="5" <<
1753 ,year="2007" <<
1754 ,note="\url{http://lwn.net/Articles/220677/}" <<
1755 ,annotation={ <<
1756 LWN article introducing RCU priority <<
1757 Revised: <<
1758 http://www.rdrop.com/users/paulmck/RC <<
1759 [Viewed September 7, 2007] <<
1760 } <<
1761 } <<
1762 <<
1763 @unpublished{PaulMcKenney2007QRCUpatch <<
1764 ,Author="Paul E. McKenney" <<
1765 ,Title="{[PATCH]} {QRCU} with lockless fastpa <<
1766 ,month="February" <<
1767 ,year="2007" <<
1768 ,day=24 <<
1769 ,note="Available: <<
1770 \url{https://lore.kernel.org/r/20070225062349 <<
1771 [Viewed March 27, 2008]" <<
1772 ,annotation={ <<
1773 Patch for QRCU supplying lock-free fa <<
1774 } <<
1775 } <<
1776 <<
1777 @article{JonathanAppavoo2007K42RCU <<
1778 ,author = {Appavoo, Jonathan and Silva, Dilma <<
1779 ,title = {Experience distributing objects in <<
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.12 <<
1787 ,publisher = {ACM} <<
1788 ,address = {New York, NY, USA} <<
1789 ,annotation={ <<
1790 Role of RCU in K42. <<
1791 } <<
1792 } <<
1793 <<
1794 @conference{RobertOlsson2007Trash <<
1795 ,Author="Robert Olsson and Stefan Nilsson" <<
1796 ,Title="{TRASH}: A dynamic {LC}-trie and hash <<
1797 ,booktitle="Workshop on High Performance Swit <<
1798 ,month="May" <<
1799 ,year="2007" <<
1800 ,note="Available: <<
1801 \url{http://ieeexplore.ieee.org/xpl/freeabs_a <<
1802 [Viewed October 1, 2010]" <<
1803 ,annotation={ <<
1804 RCU-protected dynamic trie-hash combi 631 RCU-protected dynamic trie-hash combination.
1805 } !! 632 "
1806 } 633 }
1807 634
1808 @conference{PeterZijlstra2007ConcurrentPageca !! 635 @unpublished{ThomasEHart2007a
1809 ,Author="Peter Zijlstra" !! 636 ,Author="Thomas E. Hart and Paul E. McKenney and Angela Demke Brown and Jonathan Walpole"
1810 ,Title="Concurrent Pagecache" !! 637 ,Title="Performance of memory reclamation for lockless synchronization"
1811 ,Booktitle="Linux Symposium" !! 638 ,journal="J. Parallel Distrib. Comput."
1812 ,month="June" <<
1813 ,year="2007" <<
1814 ,address="Ottawa, Canada" <<
1815 ,note="Available: <<
1816 \url{http://ols.108.redhat.com/2007/Reprints/ <<
1817 [Viewed April 14, 2008]" <<
1818 ,annotation={ <<
1819 Page-cache modifications permitting R <<
1820 updates. <<
1821 } <<
1822 } <<
1823 <<
1824 @unpublished{PaulEMcKenney2007whatisRCU <<
1825 ,Author="Paul E. McKenney" <<
1826 ,Title="What is {RCU}?" <<
1827 ,year="2007" 639 ,year="2007"
1828 ,month="07" !! 640 ,note="To appear in J. Parallel Distrib. Comput.
1829 ,note="Available: !! 641 \url{doi=10.1016/j.jpdc.2007.04.010}"
1830 \url{http://www.rdrop.com/users/paulmck/RCU/w <<
1831 [Viewed July 6, 2007]" <<
1832 ,annotation={ 642 ,annotation={
1833 Describes RCU in Linux kernel. !! 643 Compares QSBR (AKA "classic RCU"), HPBR, EBR, and lock-free
>> 644 reference counting. Journal version of ThomasEHart2006a.
1834 } 645 }
1835 } 646 }
1836 647
1837 @unpublished{PaulEMcKenney2007QRCUspin 648 @unpublished{PaulEMcKenney2007QRCUspin
1838 ,Author="Paul E. McKenney" 649 ,Author="Paul E. McKenney"
1839 ,Title="Using {Promela} and {Spin} to verify !! 650 ,Title="Using Promela and Spin to verify parallel algorithms"
1840 ,month="August" 651 ,month="August"
1841 ,day="1" 652 ,day="1"
1842 ,year="2007" 653 ,year="2007"
1843 ,note="Available: 654 ,note="Available:
1844 \url{http://lwn.net/Articles/243851/} 655 \url{http://lwn.net/Articles/243851/}
1845 [Viewed September 8, 2007]" 656 [Viewed September 8, 2007]"
1846 ,annotation={ !! 657 ,annotation="
1847 LWN article describing Promela and sp 658 LWN article describing Promela and spin, and also using Oleg
1848 Nesterov's QRCU as an example (with P 659 Nesterov's QRCU as an example (with Paul McKenney's fastpath).
1849 Merged patch at: https://lore.kernel. !! 660 "
1850 } <<
1851 } <<
1852 <<
1853 @unpublished{PaulEMcKenney2007WG21DDOatomics <<
1854 ,Author="Paul E. McKenney and Hans-J. Boehm a <<
1855 ,Title="C++ Data-Dependency Ordering: Atomics <<
1856 ,month="August" <<
1857 ,day="3" <<
1858 ,year="2007" <<
1859 ,note="Available: <<
1860 \url{http://open-std.org/jtc1/sc22/wg21/docs/ <<
1861 [Viewed December 7, 2009]" <<
1862 ,annotation={ <<
1863 RCU for C++, parts 1 and 2. <<
1864 } <<
1865 } <<
1866 <<
1867 @unpublished{PaulEMcKenney2007WG21DDOannotati <<
1868 ,Author="Paul E. McKenney and Lawrence Crowl" <<
1869 ,Title="C++ Data-Dependency Ordering: Functio <<
1870 ,month="September" <<
1871 ,day="18" <<
1872 ,year="2008" <<
1873 ,note="Available: <<
1874 \url{http://open-std.org/jtc1/sc22/wg21/docs/ <<
1875 [Viewed December 7, 2009]" <<
1876 ,annotation={ <<
1877 RCU for C++, part 2, updated many tim <<
1878 } <<
1879 } <<
1880 <<
1881 @unpublished{PaulEMcKenney2007PreemptibleRCUP <<
1882 ,Author="Paul E. McKenney" <<
1883 ,Title="[PATCH RFC 0/9] {RCU}: Preemptible {R <<
1884 ,month="September" <<
1885 ,day="10" <<
1886 ,year="2007" <<
1887 ,note="Available: <<
1888 \url{https://lore.kernel.org/r/20070910183004 <<
1889 [Viewed October 25, 2007]" <<
1890 ,annotation={ <<
1891 Final patch for preemptible RCU to -r <<
1892 to mainline, eventually incorporated. <<
1893 } <<
1894 } 661 }
1895 662
1896 @unpublished{PaulEMcKenney2007PreemptibleRCU 663 @unpublished{PaulEMcKenney2007PreemptibleRCU
1897 ,Author="Paul E. McKenney" 664 ,Author="Paul E. McKenney"
1898 ,Title="The design of preemptible read-copy-u 665 ,Title="The design of preemptible read-copy-update"
1899 ,month="October" 666 ,month="October"
1900 ,day="8" 667 ,day="8"
1901 ,year="2007" 668 ,year="2007"
1902 ,note="Available: 669 ,note="Available:
1903 \url{http://lwn.net/Articles/253651/} 670 \url{http://lwn.net/Articles/253651/}
1904 [Viewed October 25, 2007]" 671 [Viewed October 25, 2007]"
1905 ,annotation={ !! 672 ,annotation="
1906 LWN article describing the design of 673 LWN article describing the design of preemptible RCU.
1907 } !! 674 "
1908 } <<
1909 <<
1910 @article{ThomasEHart2007a <<
1911 ,Author="Thomas E. Hart and Paul E. McKenney <<
1912 ,Title="Performance of memory reclamation for <<
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.0 <<
1920 ,publisher="Academic Press, Inc." <<
1921 ,address="Orlando, FL, USA" <<
1922 ,annotation={ <<
1923 Compares QSBR, HPBR, EBR, and lock-fr <<
1924 Journal version of ThomasEHart2006a. <<
1925 } <<
1926 } 675 }
1927 676
1928 # MathieuDesnoyers2007call_rcu_schedNeeded <<
1929 @unpublished{MathieuDesnoyers2007call:rcu:sch <<
1930 ,Author="Mathieu Desnoyers" <<
1931 ,Title="Re: [patch 1/2] {Linux} Kernel Marker <<
1932 ,month="December" <<
1933 ,day="20" <<
1934 ,year="2007" <<
1935 ,note="Available: <<
1936 \url{https://lore.kernel.org/r/20071220142540 <<
1937 [Viewed March 27, 2008]" <<
1938 ,annotation={ <<
1939 Request for call_rcu_sched() and rcu_ <<
1940 } <<
1941 } <<
1942 <<
1943 <<
1944 ############################################# 677 ########################################################################
1945 # 678 #
1946 # "What is RCU?" LWN series. 679 # "What is RCU?" LWN series.
1947 # 680 #
1948 # http://lwn.net/Articles/262464/ (What <<
1949 # http://lwn.net/Articles/263130/ (What <<
1950 # http://lwn.net/Articles/264090/ (What <<
1951 681
1952 @unpublished{PaulEMcKenney2007WhatIsRCUFundam 682 @unpublished{PaulEMcKenney2007WhatIsRCUFundamentally
1953 ,Author="Paul E. McKenney and Jonathan Walpol 683 ,Author="Paul E. McKenney and Jonathan Walpole"
1954 ,Title="What is {RCU}, Fundamentally?" 684 ,Title="What is {RCU}, Fundamentally?"
1955 ,month="December" 685 ,month="December"
1956 ,day="17" 686 ,day="17"
1957 ,year="2007" 687 ,year="2007"
1958 ,note="Available: 688 ,note="Available:
1959 \url{http://lwn.net/Articles/262464/} 689 \url{http://lwn.net/Articles/262464/}
1960 [Viewed December 27, 2007]" 690 [Viewed December 27, 2007]"
1961 ,annotation={ !! 691 ,annotation="
1962 Lays out the three basic components o 692 Lays out the three basic components of RCU: (1) publish-subscribe,
1963 (2) wait for pre-existing readers to 693 (2) wait for pre-existing readers to complete, and (2) maintain
1964 multiple versions. 694 multiple versions.
1965 } !! 695 "
1966 } 696 }
1967 697
1968 @unpublished{PaulEMcKenney2008WhatIsRCUUsage 698 @unpublished{PaulEMcKenney2008WhatIsRCUUsage
1969 ,Author="Paul E. McKenney" 699 ,Author="Paul E. McKenney"
1970 ,Title="What is {RCU}? Part 2: Usage" 700 ,Title="What is {RCU}? Part 2: Usage"
1971 ,month="January" 701 ,month="January"
1972 ,day="4" 702 ,day="4"
1973 ,year="2008" 703 ,year="2008"
1974 ,note="Available: 704 ,note="Available:
1975 \url{http://lwn.net/Articles/263130/} 705 \url{http://lwn.net/Articles/263130/}
1976 [Viewed January 4, 2008]" 706 [Viewed January 4, 2008]"
1977 ,annotation={ !! 707 ,annotation="
1978 Lays out six uses of RCU: 708 Lays out six uses of RCU:
1979 1. RCU is a Reader-Writer Lock Replac 709 1. RCU is a Reader-Writer Lock Replacement
1980 2. RCU is a Restricted Reference-Coun 710 2. RCU is a Restricted Reference-Counting Mechanism
1981 3. RCU is a Bulk Reference-Counting M 711 3. RCU is a Bulk Reference-Counting Mechanism
1982 4. RCU is a Poor Man's Garbage Collec 712 4. RCU is a Poor Man's Garbage Collector
1983 5. RCU is a Way of Providing Existenc 713 5. RCU is a Way of Providing Existence Guarantees
1984 6. RCU is a Way of Waiting for Things !! 714 6. RCU is a Way of Waiting for Things to Finish
1985 } !! 715 "
1986 } 716 }
1987 717
1988 @unpublished{PaulEMcKenney2008WhatIsRCUAPI 718 @unpublished{PaulEMcKenney2008WhatIsRCUAPI
1989 ,Author="Paul E. McKenney" 719 ,Author="Paul E. McKenney"
1990 ,Title="{RCU} part 3: the {RCU} {API}" 720 ,Title="{RCU} part 3: the {RCU} {API}"
1991 ,month="January" 721 ,month="January"
1992 ,day="17" 722 ,day="17"
1993 ,year="2008" 723 ,year="2008"
1994 ,note="Available: 724 ,note="Available:
1995 \url{http://lwn.net/Articles/264090/} 725 \url{http://lwn.net/Articles/264090/}
1996 [Viewed January 10, 2008]" 726 [Viewed January 10, 2008]"
1997 ,annotation={ !! 727 ,annotation="
1998 Gives an overview of the Linux-kernel 728 Gives an overview of the Linux-kernel RCU API and a brief annotated RCU
1999 bibliography. 729 bibliography.
2000 } !! 730 "
2001 } <<
2002 <<
2003 # <<
2004 # "What is RCU?" LWN series. <<
2005 # <<
2006 ############################################# <<
2007 <<
2008 <<
2009 @unpublished{SteveRostedt2008dyntickRCUpatch <<
2010 ,Author="Steven Rostedt and Paul E. McKenney" <<
2011 ,Title="{[PATCH]} add support for dynamic tic <<
2012 ,month="January" <<
2013 ,day="29" <<
2014 ,year="2008" <<
2015 ,note="Available: <<
2016 \url{https://lore.kernel.org/r/Pine.LNX.4.58. <<
2017 [Viewed March 27, 2008]" <<
2018 ,annotation={ <<
2019 Patch that prevents preemptible RCU f <<
2020 up dynticks-idle CPUs. <<
2021 } <<
2022 } <<
2023 <<
2024 @unpublished{PaulEMcKenney2008LKMLDependencyO <<
2025 ,Author="Paul E. McKenney" <<
2026 ,Title="Re: [PATCH 02/22 -v7] Add basic suppo <<
2027 ,month="February" <<
2028 ,day="1" <<
2029 ,year="2008" <<
2030 ,note="Available: <<
2031 \url{https://lore.kernel.org/r/20080202214124 <<
2032 [Viewed October 18, 2008]" <<
2033 ,annotation={ <<
2034 Explanation of compilers violating de <<
2035 } <<
2036 } <<
2037 <<
2038 @Conference{PaulEMcKenney2008Beijing <<
2039 ,Author="Paul E. McKenney" <<
2040 ,Title="Introducing Technology Into {Linux} O <<
2041 Introducing your technology Into {Linux} will <<
2042 lot of {Linux} into your technology!!!" <<
2043 ,Booktitle="2008 Linux Developer Symposium - <<
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/T <<
2050 [Viewed August 12, 2008]" <<
2051 } <<
2052 <<
2053 @unpublished{PaulEMcKenney2008dynticksRCU <<
2054 ,Author="Paul E. McKenney and Steven Rostedt" <<
2055 ,Title="Integrating and Validating dynticks a <<
2056 ,month="April" <<
2057 ,day="24" <<
2058 ,year="2008" <<
2059 ,note="Available: <<
2060 \url{http://lwn.net/Articles/279077/} <<
2061 [Viewed April 24, 2008]" <<
2062 ,annotation={ <<
2063 Describes use of Promela and Spin to <<
2064 dynticks/RCU interface. <<
2065 } <<
2066 } 731 }
2067 732
2068 @article{DinakarGuniguntala2008IBMSysJ 733 @article{DinakarGuniguntala2008IBMSysJ
2069 ,author="D. Guniguntala and P. E. McKenney an 734 ,author="D. Guniguntala and P. E. McKenney and J. Triplett and J. Walpole"
2070 ,title="The read-copy-update mechanism for su 735 ,title="The read-copy-update mechanism for supporting real-time applications on shared-memory multiprocessor systems with {Linux}"
2071 ,Year="2008" 736 ,Year="2008"
2072 ,Month="May" !! 737 ,Month="April"
2073 ,journal="IBM Systems Journal" 738 ,journal="IBM Systems Journal"
2074 ,volume="47" 739 ,volume="47"
2075 ,number="2" 740 ,number="2"
2076 ,pages="221-236" !! 741 ,pages="@@-@@"
2077 ,annotation={ !! 742 ,annotation="
2078 RCU, realtime RCU, sleepable RCU, per 743 RCU, realtime RCU, sleepable RCU, performance.
2079 http://www.research.ibm.com/journal/s !! 744 "
2080 [Viewed April 24, 2008] <<
2081 } <<
2082 } <<
2083 <<
2084 @unpublished{LaiJiangshan2008NewClassicAlgori <<
2085 ,Author="Lai Jiangshan" <<
2086 ,Title="[{RFC}][{PATCH}] rcu classic: new alg <<
2087 ,month="June" <<
2088 ,day="3" <<
2089 ,year="2008" <<
2090 ,note="Available: <<
2091 \url{https://lore.kernel.org/r/4844BE83.50104 <<
2092 [Viewed December 10, 2008]" <<
2093 ,annotation={ <<
2094 Updated RCU classic algorithm. Intro <<
2095 for RCU callbacks and also pulling co <<
2096 __call_rcu(). <<
2097 } <<
2098 } 745 }
2099 746
2100 @article{PaulEMcKenney2008RCUOSR 747 @article{PaulEMcKenney2008RCUOSR
2101 ,author="Paul E. McKenney and Jonathan Walpol 748 ,author="Paul E. McKenney and Jonathan Walpole"
2102 ,title="Introducing technology into the {Linu 749 ,title="Introducing technology into the {Linux} kernel: a case study"
2103 ,Year="2008" 750 ,Year="2008"
2104 ,journal="SIGOPS Oper. Syst. Rev." 751 ,journal="SIGOPS Oper. Syst. Rev."
2105 ,volume="42" 752 ,volume="42"
2106 ,number="5" 753 ,number="5"
2107 ,pages="4--17" 754 ,pages="4--17"
2108 ,issn="0163-5980" 755 ,issn="0163-5980"
2109 ,doi={http://doi.acm.org/10.1145/1400097.1400 756 ,doi={http://doi.acm.org/10.1145/1400097.1400099}
2110 ,publisher="ACM" 757 ,publisher="ACM"
2111 ,address="New York, NY, USA" 758 ,address="New York, NY, USA"
2112 ,annotation={ 759 ,annotation={
2113 Linux changed RCU to a far greater de 760 Linux changed RCU to a far greater degree than RCU has changed Linux.
2114 http://portal.acm.org/citation.cfm?do <<
2115 } <<
2116 } <<
2117 <<
2118 @unpublished{ManfredSpraul2008StateMachineRCU <<
2119 ,Author="Manfred Spraul" <<
2120 ,Title="[{RFC}, {PATCH}] state machine based <<
2121 ,month="August" <<
2122 ,day="21" <<
2123 ,year="2008" <<
2124 ,note="Available: <<
2125 \url{https://lore.kernel.org/r/48AD8969.70609 <<
2126 [Viewed December 8, 2008]" <<
2127 ,annotation={ <<
2128 State-based RCU. One key thing that <<
2129 separate the dynticks handling of NMI <<
2130 } <<
2131 } <<
2132 <<
2133 @unpublished{ManfredSpraul2008dyntickIRQNMI <<
2134 ,Author="Manfred Spraul" <<
2135 ,Title="Re: [{RFC}, {PATCH}] v4 scalable clas <<
2136 ,month="September" <<
2137 ,day="6" <<
2138 ,year="2008" <<
2139 ,note="Available: <<
2140 \url{https://lore.kernel.org/r/48C2B1D2.50708 <<
2141 [Viewed December 8, 2008]" <<
2142 ,annotation={ <<
2143 Manfred notes a fix required to my at <<
2144 and NMI processing for hierarchical R <<
2145 } <<
2146 } <<
2147 <<
2148 # Was PaulEMcKenney2011cyclicRCU <<
2149 @techreport{PaulEMcKenney2008cyclicRCU <<
2150 ,author="Paul E. McKenney" <<
2151 ,title="Efficient Support of Consistent Cycli <<
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" <<
2158 ,annotation={ <<
2159 Maintains an additional level of indi <<
2160 readers to confine themselves to the <<
2161 data structure. Only permits one upd <<
2162 } 761 }
2163 } 762 }
2164 763
2165 @unpublished{PaulEMcKenney2008HierarchicalRCU 764 @unpublished{PaulEMcKenney2008HierarchicalRCU
2166 ,Author="Paul E. McKenney" 765 ,Author="Paul E. McKenney"
2167 ,Title="Hierarchical {RCU}" 766 ,Title="Hierarchical {RCU}"
2168 ,month="November" 767 ,month="November"
2169 ,day="3" 768 ,day="3"
2170 ,year="2008" 769 ,year="2008"
2171 ,note="\url{http://lwn.net/Articles/305782/}" !! 770 ,note="Available:
2172 ,annotation={ !! 771 \url{http://lwn.net/Articles/305782/}
>> 772 [Viewed November 6, 2008]"
>> 773 ,annotation="
2173 RCU with combining-tree-based grace-p 774 RCU with combining-tree-based grace-period detection,
2174 permitting it to handle thousands of 775 permitting it to handle thousands of CPUs.
2175 [Viewed November 6, 2008] !! 776 "
2176 } <<
2177 } <<
2178 <<
2179 @unpublished{PaulEMcKenney2009BloatwatchRCU <<
2180 ,Author="Paul E. McKenney" <<
2181 ,Title="Re: [PATCH fyi] RCU: the bloatwatch e <<
2182 ,month="January" <<
2183 ,day="14" <<
2184 ,year="2009" <<
2185 ,note="Available: <<
2186 \url{https://lore.kernel.org/r/20090114202044 <<
2187 [Viewed January 15, 2009]" <<
2188 ,annotation={ <<
2189 Small-footprint implementation of RCU <<
2190 embedded applications -- and also for <<
2191 } <<
2192 } 777 }
2193 778
2194 @conference{PaulEMcKenney2009MaliciousURCU 779 @conference{PaulEMcKenney2009MaliciousURCU
2195 ,Author="Paul E. McKenney" 780 ,Author="Paul E. McKenney"
2196 ,Title="Using a Malicious User-Level {RCU} to 781 ,Title="Using a Malicious User-Level {RCU} to Torture {RCU}-Based Algorithms"
2197 ,Booktitle="linux.conf.au 2009" 782 ,Booktitle="linux.conf.au 2009"
2198 ,month="January" 783 ,month="January"
2199 ,year="2009" 784 ,year="2009"
2200 ,address="Hobart, Australia" 785 ,address="Hobart, Australia"
2201 ,note="Available: 786 ,note="Available:
2202 \url{http://www.rdrop.com/users/paulmck/RCU/u 787 \url{http://www.rdrop.com/users/paulmck/RCU/urcutorture.2009.01.22a.pdf}
2203 [Viewed February 2, 2009]" 788 [Viewed February 2, 2009]"
2204 ,annotation={ !! 789 ,annotation="
2205 Realtime RCU and torture-testing RCU 790 Realtime RCU and torture-testing RCU uses.
2206 } !! 791 "
2207 } 792 }
2208 793
2209 @unpublished{MathieuDesnoyers2009URCU 794 @unpublished{MathieuDesnoyers2009URCU
2210 ,Author="Mathieu Desnoyers" 795 ,Author="Mathieu Desnoyers"
2211 ,Title="[{RFC} git tree] Userspace {RCU} (urc 796 ,Title="[{RFC} git tree] Userspace {RCU} (urcu) for {Linux}"
2212 ,month="February" 797 ,month="February"
2213 ,day="5" 798 ,day="5"
2214 ,year="2009" 799 ,year="2009"
2215 ,note="\url{http://lttng.org/urcu}" !! 800 ,note="Available:
2216 ,annotation={ !! 801 \url{http://lkml.org/lkml/2009/2/5/572}
>> 802 \url{git://lttng.org/userspace-rcu.git}
>> 803 [Viewed February 20, 2009]"
>> 804 ,annotation="
2217 Mathieu Desnoyers's user-space RCU im 805 Mathieu Desnoyers's user-space RCU implementation.
2218 git://lttng.org/userspace-rcu.git 806 git://lttng.org/userspace-rcu.git
2219 http://lttng.org/cgi-bin/gitweb.cgi?p !! 807 "
2220 http://lttng.org/urcu <<
2221 https://lore.kernel.org/r/20090206030 <<
2222 } <<
2223 } 808 }
2224 809
2225 @unpublished{PaulEMcKenney2009LWNBloatWatchRC !! 810 @unpublished{PaulEMcKenney2009BloatWatchRCU
2226 ,Author="Paul E. McKenney" 811 ,Author="Paul E. McKenney"
2227 ,Title="{RCU}: The {Bloatwatch} Edition" 812 ,Title="{RCU}: The {Bloatwatch} Edition"
2228 ,month="March" 813 ,month="March"
2229 ,day="17" 814 ,day="17"
2230 ,year="2009" 815 ,year="2009"
2231 ,note="Available: 816 ,note="Available:
2232 \url{http://lwn.net/Articles/323929/} 817 \url{http://lwn.net/Articles/323929/}
2233 [Viewed March 20, 2009]" 818 [Viewed March 20, 2009]"
2234 ,annotation={ !! 819 ,annotation="
2235 Uniprocessor assumptions allow simpli 820 Uniprocessor assumptions allow simplified RCU implementation.
2236 } !! 821 "
2237 } <<
2238 <<
2239 @unpublished{EvgeniyPolyakov2009EllipticsNetw <<
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/elliptic <<
2247 [Viewed April 30, 2009]" <<
2248 ,annotation={ <<
2249 Distributed hash table with transacti <<
2250 hash functions to distribute data. <<
2251 } <<
2252 } <<
2253 <<
2254 @unpublished{PaulEMcKenney2009expeditedRCU <<
2255 ,Author="Paul E. McKenney" <<
2256 ,Title="[{PATCH} -tip 0/3] expedited 'big ham <<
2257 ,month="June" <<
2258 ,day="25" <<
2259 ,year="2009" <<
2260 ,note="Available: <<
2261 \url{https://lore.kernel.org/r/20090625160706 <<
2262 [Viewed August 16, 2009]" <<
2263 ,annotation={ <<
2264 First posting of expedited RCU to be <<
2265 } <<
2266 } <<
2267 <<
2268 @unpublished{PaulEMcKenney2009fastRTRCU <<
2269 ,Author="Paul E. McKenney" <<
2270 ,Title="[{PATCH} {RFC} -tip 0/4] {RCU} cleanu <<
2271 ,month="July" <<
2272 ,day="23" <<
2273 ,year="2009" <<
2274 ,note="Available: <<
2275 \url{https://lore.kernel.org/r/20090724001429 <<
2276 [Viewed August 15, 2009]" <<
2277 ,annotation={ <<
2278 First posting of simple and fast pree <<
2279 } <<
2280 } <<
2281 <<
2282 @unpublished{JoshTriplett2009RPHash <<
2283 ,Author="Josh Triplett" <<
2284 ,Title="Scalable concurrent hash tables via r <<
2285 ,month="September" <<
2286 ,year="2009" <<
2287 ,note="Linux Plumbers Conference presentation <<
2288 ,annotation={ <<
2289 RP fun with hash tables. <<
2290 Superseded by JoshTriplett2010RPHash <<
2291 } <<
2292 } <<
2293 <<
2294 @phdthesis{MathieuDesnoyersPhD <<
2295 , title = "Low-Impact Operating System Traci <<
2296 , author = "Mathieu Desnoyers" <<
2297 , school = "Ecole Polytechnique de Montr\'{e} <<
2298 , month = "December" <<
2299 , year = 2009 <<
2300 ,note="Available: <<
2301 \url{http://www.lttng.org/pub/thesis/desnoyer <<
2302 [Viewed December 9, 2009]" <<
2303 ,annotation={ <<
2304 Chapter 6 (page 97) covers user-level <<
2305 } <<
2306 } <<
2307 <<
2308 @unpublished{RelativisticProgrammingWiki <<
2309 ,Author="Josh Triplett and Paul E. McKenney a <<
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]" <<
2316 ,annotation={ <<
2317 Main Relativistic Programming Wiki. <<
2318 } <<
2319 } <<
2320 <<
2321 @conference{PaulEMcKenney2009DeterministicRCU <<
2322 ,Author="Paul E. McKenney" <<
2323 ,Title="Deterministic Synchronization in Mult <<
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/realt <<
2330 [Viewed January 14, 2009]" <<
2331 } <<
2332 <<
2333 @unpublished{PaulEMcKenney2009HuntingHeisenbu <<
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.htm <<
2341 [Viewed June 4, 2010]" <<
2342 ,annotation={ <<
2343 Day-one bug in Tree RCU that took for <<
2344 } <<
2345 } <<
2346 <<
2347 @unpublished{MathieuDesnoyers2009defer:rcu <<
2348 ,Author="Mathieu Desnoyers" <<
2349 ,Title="Kernel RCU: shrink the size of the st <<
2350 ,month="December" <<
2351 ,year="2009" <<
2352 ,note="Available: <<
2353 \url{https://lore.kernel.org/r/20091018232918 <<
2354 [Viewed December 29, 2009]" <<
2355 ,annotation={ <<
2356 Mathieu proposed defer_rcu() with fix <<
2357 of RCU callbacks. <<
2358 } <<
2359 } <<
2360 <<
2361 @unpublished{MathieuDesnoyers2009VerifPrePub <<
2362 ,Author="Mathieu Desnoyers and Paul E. McKenn <<
2363 ,Title="Multi-Core Systems Modeling for Forma <<
2364 ,month="December" <<
2365 ,year="2009" <<
2366 ,note="Submitted to IEEE TPDS" <<
2367 ,annotation={ <<
2368 OOMem model for Mathieu's user-level <<
2369 correctness. <<
2370 } <<
2371 } <<
2372 <<
2373 @unpublished{MathieuDesnoyers2009URCUPrePub <<
2374 ,Author="Mathieu Desnoyers and Paul E. McKenn <<
2375 ,Title="User-Level Implementations of Read-Co <<
2376 ,month="December" <<
2377 ,year="2010" <<
2378 ,url={\url{http://www.computer.org/csdl/trans <<
2379 ,annotation={ <<
2380 RCU overview, desiderata, semi-formal <<
2381 usage scenarios, three classes of RCU <<
2382 RCU updates, RCU grace-period batchin <<
2383 http://www.rdrop.com/users/paulmck/RC <<
2384 http://www.rdrop.com/users/paulmck/RC <<
2385 Superseded by MathieuDesnoyers2012URC <<
2386 } <<
2387 } <<
2388 <<
2389 @inproceedings{HariKannan2009DynamicAnalysisR <<
2390 ,author = {Kannan, Hari} <<
2391 ,title = {Ordering decoupled metadata accesse <<
2392 ,booktitle = {MICRO 42: Proceedings of the 42 <<
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.16 <<
2398 ,publisher = {ACM} <<
2399 ,address = {New York, NY, USA} <<
2400 ,annotation={ <<
2401 Uses RCU to protect metadata used in <<
2402 } <<
2403 } <<
2404 <<
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/S <<
2414 [Viewed October 10, 2010]" <<
2415 ,annotation={ <<
2416 TREE_PREEMPT_RCU optimizations greatl <<
2417 PREEMPT_RCU implementation. <<
2418 } <<
2419 } <<
2420 <<
2421 @unpublished{PaulEMcKenney2010LockdepRCU <<
2422 ,Author="Paul E. McKenney" <<
2423 ,Title="Lockdep-{RCU}" <<
2424 ,month="February" <<
2425 ,year="2010" <<
2426 ,day="1" <<
2427 ,note="\url{https://lwn.net/Articles/371986/} <<
2428 ,annotation={ <<
2429 CONFIG_PROVE_RCU, or at least an earl <<
2430 [Viewed June 4, 2010] <<
2431 } <<
2432 } <<
2433 <<
2434 @unpublished{AviKivity2010KVM2RCU <<
2435 ,Author="Avi Kivity" <<
2436 ,Title="[{PATCH} 37/40] {KVM}: Bump maximum v <<
2437 ,month="February" <<
2438 ,year="2010" <<
2439 ,note="Available: <<
2440 \url{http://www.mail-archive.com/kvm@vger.ker <<
2441 [Viewed March 20, 2010]" <<
2442 ,annotation={ <<
2443 Use of RCU permits KVM to increase th <<
2444 16 CPUs to 64 CPUs. <<
2445 } <<
2446 } <<
2447 <<
2448 @unpublished{HerbertXu2010RCUResizeHash <<
2449 ,Author="Herbert Xu" <<
2450 ,Title="bridge: Add core IGMP snooping suppor <<
2451 ,month="February" <<
2452 ,year="2010" <<
2453 ,note="Available: <<
2454 \url{http://thread.gmane.org/gmane.linux.netw <<
2455 [Viewed June 9, 2014]" <<
2456 ,annotation={ <<
2457 Use a pair of list_head structures to <<
2458 resizable hash tables. <<
2459 } <<
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/abhin <<
2470 } <<
2471 } <<
2472 <<
2473 @article{JoshTriplett2010RPHash <<
2474 ,author="Josh Triplett and Paul E. McKenney a <<
2475 ,title="Scalable Concurrent Hash Tables via R <<
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 <<
2484 } <<
2485 } <<
2486 <<
2487 @unpublished{PaulEMcKenney2010RCUAPI <<
2488 ,Author="Paul E. McKenney" <<
2489 ,Title="The {RCU} {API}, 2010 Edition" <<
2490 ,month="December" <<
2491 ,day="8" <<
2492 ,year="2010" <<
2493 ,note="\url{http://lwn.net/Articles/418853/}" <<
2494 ,annotation={ <<
2495 Includes updated software-engineering <<
2496 [Viewed December 8, 2010] <<
2497 } <<
2498 } <<
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 creat <<
2510 Drives quiescent-state detection from <<
2511 in a manner roughly similar to that o <<
2512 } <<
2513 } <<
2514 <<
2515 @unpublished{LinusTorvalds2011Linux2:6:38:rc1 <<
2516 ,Author="Linus Torvalds" <<
2517 ,Title="Linux 2.6.38-rc1" <<
2518 ,month="January" <<
2519 ,year="2011" <<
2520 ,note="Available: <<
2521 \url{https://lore.kernel.org/r/AANLkTimajU0x1 <<
2522 [Viewed March 4, 2011]" <<
2523 ,annotation={ <<
2524 "The RCU-based name lookup is at the <<
2525 absolute anti-gimmick. It's some seri <<
2526 the last main global lock that really <<
2527 The dentry lock is no longer a big se <<
2528 nice about it is that it actually imp <<
2529 single-threaded loads (on an SMP kern <<
2530 of the most expensive parts of path c <<
2531 d_lock on every component lookup. So <<
2532 on some seriously pathname-lookup int <<
2533 } <<
2534 } <<
2535 <<
2536 @techreport{JoshTriplett2011RPScalableCorrect <<
2537 ,author = {Josh Triplett and Philip W. Howard <<
2538 ,title = {Scalable Correct Memory Ordering vi <<
2539 ,year = {2011} <<
2540 ,number = {11-03} <<
2541 ,institution = {Portland State University} <<
2542 ,note = {\url{http://www.cs.pdx.edu/pdfs/tr11 <<
2543 } <<
2544 <<
2545 @inproceedings{PhilHoward2011RCUTMRBTree <<
2546 ,author = {Philip W. Howard and Jonathan Walp <<
2547 ,title = {A Relativistic Enhancement to Softw <<
2548 ,booktitle = {Proceedings of the 3rd USENIX c <<
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/ <<
2555 ,publisher = {USENIX Association} <<
2556 ,address = {Berkeley, CA, USA} <<
2557 } <<
2558 <<
2559 @techreport{PaulEMcKenney2011cyclicparallelRC <<
2560 ,author="Paul E. McKenney and Jonathan Walpol <<
2561 ,title="Efficient Support of Consistent Cycli <<
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" <<
2568 ,annotation={ <<
2569 Maintains an array of generation numb <<
2570 updates and keeps an additional level <<
2571 readers to confine themselves to the <<
2572 data structure. <<
2573 } <<
2574 } <<
2575 <<
2576 @inproceedings{Triplett:2011:RPHash <<
2577 ,author = {Triplett, Josh and McKenney, Paul <<
2578 ,title = {Resizable, Scalable, Concurrent Has <<
2579 ,booktitle = {Proceedings of the 2011 USENIX <<
2580 ,month = {June} <<
2581 ,year = {2011} <<
2582 ,pages = {145--158} <<
2583 ,numpages = {14} <<
2584 ,url={http://www.usenix.org/event/atc11/tech/ <<
2585 ,publisher = {The USENIX Association} <<
2586 ,address = {Portland, OR USA} <<
2587 } <<
2588 <<
2589 @unpublished{PaulEMcKenney2011RCU3.0trainwrec <<
2590 ,Author="Paul E. McKenney" <<
2591 ,Title="3.0 and {RCU:} what went wrong" <<
2592 ,month="July" <<
2593 ,day="27" <<
2594 ,year="2011" <<
2595 ,note="\url{http://lwn.net/Articles/453002/}" <<
2596 ,annotation={ <<
2597 Analysis of the RCU trainwreck in Lin <<
2598 [Viewed July 27, 2011] <<
2599 } <<
2600 } <<
2601 <<
2602 @unpublished{NeilBrown2011MeetTheLockers <<
2603 ,Author="Neil Brown" <<
2604 ,Title="Meet the {Lockers}" <<
2605 ,month="August" <<
2606 ,day="3" <<
2607 ,year="2011" <<
2608 ,note="Available: <<
2609 \url{http://lwn.net/Articles/453685/} <<
2610 [Viewed September 2, 2011]" <<
2611 ,annotation={ <<
2612 The Locker family as an analogy for l <<
2613 RCU, and seqlock. <<
2614 } <<
2615 } <<
2616 <<
2617 @inproceedings{Seyster:2011:RFA:2075416.20754 <<
2618 ,author = {Seyster, Justin and Radhakrishnan, <<
2619 ,title = {Redflag: a framework for analysis o <<
2620 ,booktitle = {Proceedings of the 11th interna <<
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=207 <<
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 Memor <<
2636 ,school="Portland State University" <<
2637 ,year="2012" <<
2638 ,annotation={ <<
2639 RCU-protected hash tables, barriers v <<
2640 . <<
2641 If the updater is making changes in t <<
2642 the read-side traversal order, the up <<
2643 memory-barrier instruction, but if in <<
2644 updater needs to wait for a grace per <<
2645 updates. <<
2646 } <<
2647 } <<
2648 <<
2649 @article{MathieuDesnoyers2012URCU <<
2650 ,Author="Mathieu Desnoyers and Paul E. McKenn <<
2651 ,Title="User-Level Implementations of Read-Co <<
2652 ,journal="IEEE Transactions on Parallel and D <<
2653 ,volume={23} <<
2654 ,year="2012" <<
2655 ,issn="1045-9219" <<
2656 ,pages="375-382" <<
2657 ,doi="http://doi.ieeecomputersociety.org/10.1 <<
2658 ,publisher="IEEE Computer Society" <<
2659 ,address="Los Alamitos, CA, USA" <<
2660 ,annotation={ <<
2661 RCU overview, desiderata, semi-formal <<
2662 usage scenarios, three classes of RCU <<
2663 RCU updates, RCU grace-period batchin <<
2664 http://www.rdrop.com/users/paulmck/RC <<
2665 http://www.rdrop.com/users/paulmck/RC <<
2666 http://www.computer.org/cms/Computer. <<
2667 } <<
2668 } <<
2669 <<
2670 @inproceedings{AustinClements2012RCULinux:mma <<
2671 ,author = {Austin Clements and Frans Kaashoek <<
2672 ,title = {Scalable Address Spaces Using {RCU} <<
2673 ,booktitle = {Architectural Support for Progr <<
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/pa <<
2681 } <<
2682 <<
2683 @unpublished{PaulEMcKenney2012ELCbattery <<
2684 ,Author="Paul E. McKenney" <<
2685 ,Title="Making {RCU} Safe For Battery-Powered <<
2686 ,month="February" <<
2687 ,day="15" <<
2688 ,year="2012" <<
2689 ,note="Available: <<
2690 \url{http://www.rdrop.com/users/paulmck/RCU/R <<
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 <<
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 <<
2708 ,url = {http://dx.doi.org/10.1007/s11227-012- <<
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 <<
2722 ACCESS_ONCE(). <<
2723 } <<
2724 } <<
2725 <<
2726 @unpublished{AlexeyGotsman2012VerifyGraceExte <<
2727 ,Author="Alexey Gotsman and Noam Rinetzky and <<
2728 ,Title="Verifying Highly Concurrent Algorithm <<
2729 ,month="July" <<
2730 ,day="10" <<
2731 ,year="2012" <<
2732 ,note="\url{http://software.imdea.org/~gotsma <<
2733 ,annotation={ <<
2734 Separation-logic formulation of RCU u <<
2735 } <<
2736 } <<
2737 <<
2738 @unpublished{PaulMcKenney2012RCUUsage <<
2739 ,Author="Paul E. McKenney and Silas Boyd-Wick <<
2740 ,Title="{RCU} Usage In the Linux Kernel: One <<
2741 ,month="September" <<
2742 ,day="17" <<
2743 ,year="2012" <<
2744 ,url=http://rdrop.com/users/paulmck/techrepor <<
2745 ,note="Technical report paulmck.2012.09.17" <<
2746 ,annotation={ <<
2747 Overview of the first variant of no-C <<
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-C <<
2760 } <<
2761 } <<
2762 <<
2763 @phdthesis{JustinSeyster2012PhD <<
2764 ,author="Justin Seyster" <<
2765 ,title="Runtime Verification of Kernel-Level <<
2766 ,school="Stony Brook University" <<
2767 ,year="2012" <<
2768 ,annotation={ <<
2769 Looking for data races, including tho <<
2770 Proposal: <<
2771 http://www.fsl.cs.sunysb.edu/docs/jse <<
2772 Dissertation: <<
2773 http://www.fsl.cs.sunysb.edu/docs/jse <<
2774 } <<
2775 } <<
2776 <<
2777 @unpublished{PaulEMcKenney2013RCUUsage <<
2778 ,Author="Paul E. McKenney and Silas Boyd-Wick <<
2779 ,Title="{RCU} Usage in the {Linux} Kernel: On <<
2780 ,month="February" <<
2781 ,day="24" <<
2782 ,year="2013" <<
2783 ,note="\url{http://rdrop.com/users/paulmck/te <<
2784 ,annotation={ <<
2785 Usage of RCU within the Linux kernel. <<
2786 } <<
2787 } <<
2788 <<
2789 @inproceedings{AlexeyGotsman2013ESOPRCU <<
2790 ,author = {Alexey Gotsman and Noam Rinetzky a <<
2791 ,title = {Verifying concurrent memory reclama <<
2792 ,booktitle = {ESOP'13: European Symposium on <<
2793 ,year = {2013} <<
2794 ,pages = {249--269} <<
2795 ,publisher = {Springer} <<
2796 ,address = {Rome, Italy} <<
2797 ,annotation={ <<
2798 http://software.imdea.org/~gotsman/pa <<
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. <<
2811 } <<
2812 } 822 }
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.