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