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