RCU 관련 논문과 자료 읽기 | Linux 6.18.37

요약·해설과 원문, 전문 번역을 서로 분리했습니다. API 이름, symbol, source path는 원문 표기를 사용합니다.

1. 요약·해설

원문의 핵심 논리와 kernel programming 관점의 보충 설명입니다. 아래의 전문 번역과는 별도로 작성했습니다.

요약·해설

RTFP.txt:1-2812

1980년대의 지연 파괴에서 Linux RCU, preemptible·userspace·hierarchical RCU와 형식 검증까지 이어지는 연구사를 약 150개 BibTeX 항목과 함께 해설합니다.

2. 영어 원문 전체

번역 기준이 된 Linux v6.18.37 원문입니다. 줄 번호는 이 버전의 파일 좌표입니다.

원문 전체 펼치기

1 Read the Fscking Papers!

4 This document describes RCU-related publications, and is followed by

5 the corresponding bibtex entries. A number of the publications may

6 be found at http://www.rdrop.com/users/paulmck/RCU/. For others, browsers

7 and search engines will usually find what you are looking for.

9 The first thing resembling RCU was published in 1980, when Kung and Lehman

10 [Kung80] recommended use of a garbage collector to defer destruction

11 of nodes in a parallel binary search tree in order to simplify its

12 implementation. This works well in environments that have garbage

13 collectors, but most production garbage collectors incur significant

14 overhead.

16 In 1982, Manber and Ladner [Manber82,Manber84] recommended deferring

17 destruction until all threads running at that time have terminated, again

18 for a parallel binary search tree. This approach works well in systems

19 with short-lived threads, such as the K42 research operating system.

20 However, Linux has long-lived tasks, so more is needed.

22 In 1986, Hennessy, Osisek, and Seigh [Hennessy89] introduced passive

23 serialization, which is an RCU-like mechanism that relies on the presence

24 of "quiescent states" in the VM/XA hypervisor that are guaranteed not

25 to be referencing the data structure. However, this mechanism was not

26 optimized for modern computer systems, which is not surprising given

27 that these overheads were not so expensive in the mid-80s. Nonetheless,

28 passive serialization appears to be the first deferred-destruction

29 mechanism to be used in production. Furthermore, the relevant patent

30 has lapsed, so this approach may be used in non-GPL software, if desired.

31 (In contrast, implementation of RCU is permitted only in software licensed

32 under either GPL or LGPL. Sorry!!!)

34 In 1987, Rashid et al. described lazy TLB-flush [RichardRashid87a].

35 At first glance, this has nothing to do with RCU, but nevertheless

36 this paper helped inspire the update-side batching used in the later

37 RCU implementation in DYNIX/ptx. In 1988, Barbara Liskov published

38 a description of Argus that noted that use of out-of-date values can

39 be tolerated in some situations. Thus, this paper provides some early

40 theoretical justification for use of stale data.

42 In 1990, Pugh [Pugh90] noted that explicitly tracking which threads

43 were reading a given data structure permitted deferred free to operate

44 in the presence of non-terminating threads. However, this explicit

45 tracking imposes significant read-side overhead, which is undesirable

46 in read-mostly situations. This algorithm does take pains to avoid

47 write-side contention and parallelize the other write-side overheads by

48 providing a fine-grained locking design, however, it would be interesting

49 to see how much of the performance advantage reported in 1990 remains

50 today.

52 At about this same time, Andrews [Andrews91textbook] described ``chaotic

53 relaxation'', where the normal barriers between successive iterations

54 of convergent numerical algorithms are relaxed, so that iteration $n$

55 might use data from iteration $n-1$ or even $n-2$. This introduces

56 error, which typically slows convergence and thus increases the number of

57 iterations required. However, this increase is sometimes more than made

58 up for by a reduction in the number of expensive barrier operations,

59 which are otherwise required to synchronize the threads at the end

60 of each iteration. Unfortunately, chaotic relaxation requires highly

61 structured data, such as the matrices used in scientific programs, and

62 is thus inapplicable to most data structures in operating-system kernels.

64 In 1992, Henry (now Alexia) Massalin completed a dissertation advising

65 parallel programmers to defer processing when feasible to simplify

66 synchronization [HMassalinPhD]. RCU makes extremely heavy use of

67 this advice.

69 In 1993, Jacobson [Jacobson93] verbally described what is perhaps the

70 simplest deferred-free technique: simply waiting a fixed amount of time

71 before freeing blocks awaiting deferred free. Jacobson did not describe

72 any write-side changes he might have made in this work using SGI's Irix

73 kernel. Aju John published a similar technique in 1995 [AjuJohn95].

74 This works well if there is a well-defined upper bound on the length of

75 time that reading threads can hold references, as there might well be in

76 hard real-time systems. However, if this time is exceeded, perhaps due

77 to preemption, excessive interrupts, or larger-than-anticipated load,

78 memory corruption can ensue, with no reasonable means of diagnosis.

79 Jacobson's technique is therefore inappropriate for use in production

80 operating-system kernels, except when such kernels can provide hard

81 real-time response guarantees for all operations.

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 algorithms within a commercial

85 Unix operating system. However, this replugging permitted only a single

86 reader at a time. The following year, this same group of researchers

87 extended their technique to allow for multiple readers [Cowan96a].

88 Their approach requires memory barriers (and thus pipeline stalls),

89 but reduces memory latency, contention, and locking overheads.

91 1995 also saw the first publication of DYNIX/ptx's RCU mechanism

92 [Slingwine95], which was optimized for modern CPU architectures,

93 and was successfully applied to a number of situations within the

94 DYNIX/ptx kernel. The corresponding conference paper appeared in 1998

95 [McKenney98].

97 In 1999, the Tornado and K42 groups described their "generations"

98 mechanism, which is quite similar to RCU [Gamsa99]. These operating

99 systems made pervasive use of RCU in place of "existence locks", which

100 greatly simplifies locking hierarchies and helps avoid deadlocks.

101

102 The year 2000 saw an email exchange that would likely have

103 led to yet another independent invention of something like RCU

104 [RustyRussell2000a,RustyRussell2000b]. Instead, 2001 saw the first

105 RCU presentation involving Linux [McKenney01a] at OLS. The resulting

106 abundance of RCU patches was presented the following year [McKenney02a],

107 and use of RCU in dcache was first described that same year [Linder02a].

108

109 Also in 2002, Michael [Michael02b,Michael02a] presented "hazard-pointer"

110 techniques that defer the destruction of data structures to simplify

111 non-blocking synchronization (wait-free synchronization, lock-free

112 synchronization, and obstruction-free synchronization are all examples of

113 non-blocking synchronization). The corresponding journal article appeared

114 in 2004 [MagedMichael04a]. This technique eliminates locking, reduces

115 contention, reduces memory latency for readers, and parallelizes pipeline

116 stalls and memory latency for writers. However, these techniques still

117 impose significant read-side overhead in the form of memory barriers.

118 Researchers at Sun worked along similar lines in the same timeframe

119 [HerlihyLM02]. These techniques can be thought of as inside-out reference

120 counts, where the count is represented by the number of hazard pointers

121 referencing a given data structure rather than the more conventional

122 counter field within the data structure itself. The key advantage

123 of inside-out reference counts is that they can be stored in immortal

124 variables, thus allowing races between access and deletion to be avoided.

125

126 By the same token, RCU can be thought of as a "bulk reference count",

127 where some form of reference counter covers all reference by a given CPU

128 or thread during a set timeframe. This timeframe is related to, but

129 not necessarily exactly the same as, an RCU grace period. In classic

130 RCU, the reference counter is the per-CPU bit in the "bitmask" field,

131 and each such bit covers all references that might have been made by

132 the corresponding CPU during the prior grace period. Of course, RCU

133 can be thought of in other terms as well.

134

135 In 2003, the K42 group described how RCU could be used to create

136 hot-pluggable implementations of operating-system functions [Appavoo03a].

137 Later that year saw a paper describing an RCU implementation

138 of System V IPC [Arcangeli03] (following up on a suggestion by

139 Hugh Dickins [Dickins02a] and an implementation by Mingming Cao

140 [MingmingCao2002IPCRCU]), and an introduction to RCU in Linux Journal

141 [McKenney03a].

142

143 2004 has seen a Linux-Journal article on use of RCU in dcache

144 [McKenney04a], a performance comparison of locking to RCU on several

145 different CPUs [McKenney04b], a dissertation describing use of RCU in a

146 number of operating-system kernels [PaulEdwardMcKenneyPhD], a paper

147 describing how to make RCU safe for soft-realtime applications [Sarma04c],

148 and a paper describing SELinux performance with RCU [JamesMorris04b].

149

150 2005 brought further adaptation of RCU to realtime use, permitting

151 preemption of RCU realtime critical sections [PaulMcKenney05a,

152 PaulMcKenney05b].

153

154 2006 saw the first best-paper award for an RCU paper [ThomasEHart2006a],

155 as well as further work on efficient implementations of preemptible

156 RCU [PaulEMcKenney2006b], but priority-boosting of RCU read-side critical

157 sections proved elusive. An RCU implementation permitting general

158 blocking in read-side critical sections appeared [PaulEMcKenney2006c],

159 Robert Olsson described an RCU-protected trie-hash combination

160 [RobertOlsson2006a].

161

162 2007 saw the journal version of the award-winning RCU paper from 2006

163 [ThomasEHart2007a], as well as a paper demonstrating use of Promela

164 and Spin to mechanically verify an optimization to Oleg Nesterov's

165 QRCU [PaulEMcKenney2007QRCUspin], a design document describing

166 preemptible RCU [PaulEMcKenney2007PreemptibleRCU], and the three-part

167 LWN "What is RCU?" series [PaulEMcKenney2007WhatIsRCUFundamentally,

168 PaulEMcKenney2008WhatIsRCUUsage, and PaulEMcKenney2008WhatIsRCUAPI].

169

170 2008 saw a journal paper on real-time RCU [DinakarGuniguntala2008IBMSysJ],

171 a history of how Linux changed RCU more than RCU changed Linux

172 [PaulEMcKenney2008RCUOSR], and a design overview of hierarchical RCU

173 [PaulEMcKenney2008HierarchicalRCU].

174

175 2009 introduced user-level RCU algorithms [PaulEMcKenney2009MaliciousURCU],

176 which Mathieu Desnoyers is now maintaining [MathieuDesnoyers2009URCU]

177 [MathieuDesnoyersPhD]. TINY_RCU [PaulEMcKenney2009BloatWatchRCU] made

178 its appearance, as did expedited RCU [PaulEMcKenney2009expeditedRCU].

179 The problem of resizable RCU-protected hash tables may now be on a path

180 to a solution [JoshTriplett2009RPHash]. A few academic researchers are now

181 using RCU to solve their parallel problems [HariKannan2009DynamicAnalysisRCU].

182

183 2010 produced a simpler preemptible-RCU implementation

184 based on TREE_RCU [PaulEMcKenney2010SimpleOptRCU], lockdep-RCU

185 [PaulEMcKenney2010LockdepRCU], another resizable RCU-protected hash

186 table [HerbertXu2010RCUResizeHash] (this one consuming more memory,

187 but allowing arbitrary changes in hash function, as required for DoS

188 avoidance in the networking code), realization of the 2009 RCU-protected

189 hash table with atomic node move [JoshTriplett2010RPHash], an update on

190 the RCU API [PaulEMcKenney2010RCUAPI].

191

192 2011 marked the inclusion of Nick Piggin's fully lockless dentry search

193 [LinusTorvalds2011Linux2:6:38:rc1:NPigginVFS], an RCU-protected red-black

194 tree using software transactional memory to protect concurrent updates

195 (strange, but true!) [PhilHoward2011RCUTMRBTree], yet another variant of

196 RCU-protected resizable hash tables [Triplett:2011:RPHash], the 3.0 RCU

197 trainwreck [PaulEMcKenney2011RCU3.0trainwreck], and Neil Brown's "Meet the

198 Lockers" LWN article [NeilBrown2011MeetTheLockers]. Some academic

199 work looked at debugging uses of RCU [Seyster:2011:RFA:2075416.2075425].

200

201 In 2012, Josh Triplett received his Ph.D. with his dissertation

202 covering RCU-protected resizable hash tables and the relationship

203 between memory barriers and read-side traversal order: If the updater

204 is making changes in the opposite direction from the read-side traversal

205 order, the updater need only execute a memory-barrier instruction,

206 but if in the same direction, the updater needs to wait for a grace

207 period between the individual updates [JoshTriplettPhD]. Also in 2012,

208 after seventeen years of attempts, an RCU paper made it into a top-flight

209 academic journal, IEEE Transactions on Parallel and Distributed Systems

210 [MathieuDesnoyers2012URCU]. A group of researchers in Spain applied

211 user-level RCU to crowd simulation [GuillermoVigueras2012RCUCrowd], and

212 another group of researchers in Europe produced a formal description of

213 RCU based on separation logic [AlexeyGotsman2012VerifyGraceExtended],

214 which was published in the 2013 European Symposium on Programming

215 [AlexeyGotsman2013ESOPRCU].

216

217

218

219 Bibtex Entries

220

221 @article{Kung80

222 ,author="H. T. Kung and Q. Lehman"

223 ,title="Concurrent Manipulation of Binary Search Trees"

224 ,Year="1980"

225 ,Month="September"

226 ,journal="ACM Transactions on Database Systems"

227 ,volume="5"

228 ,number="3"

229 ,pages="354-382"

230 ,annotation={

231 Use garbage collector to clean up data after everyone is done with it.

232 .

233 Oldest use of something vaguely resembling RCU that I have found.

234 http://portal.acm.org/citation.cfm?id=320619&dl=GUIDE,

235 [Viewed December 3, 2007]

236 }

237 }

238

239 @techreport{Manber82

240 ,author="Udi Manber and Richard E. Ladner"

241 ,title="Concurrency Control in a Dynamic Search Structure"

242 ,institution="Department of Computer Science, University of Washington"

243 ,address="Seattle, Washington"

244 ,year="1982"

245 ,number="82-01-01"

246 ,month="January"

247 ,pages="28"

248 ,annotation={

249 .

250 Superseded by Manber84.

251 .

252 Describes concurrent AVL tree implementation. Uses a

253 garbage-collection mechanism to handle concurrent use and deletion

254 of nodes in the tree, but lacks the summary-of-execution-history

255 concept of read-copy locking.

256 .

257 Keeps full list of processes that were active when a given

258 node was to be deleted, and waits until all such processes have

259 -terminated- before allowing this node to be reused. This is

260 not described in great detail -- one could imagine using process

261 IDs for this if the ID space was large enough that overlapping

262 never occurred.

263 .

264 This restriction makes this algorithm unsuitable for use in

265 systems comprised of long-lived processes. It also produces

266 completely unacceptable overhead in systems with large numbers

267 of processes. Finally, it is specific to AVL trees.

268 .

269 Cites Kung80, so not an independent invention, but the first

270 RCU-like usage that does not rely on an automatic garbage

271 collector.

272 }

273 }

274

275 @article{Manber84

276 ,author="Udi Manber and Richard E. Ladner"

277 ,title="Concurrency Control in a Dynamic Search Structure"

278 ,Year="1984"

279 ,Month="September"

280 ,journal="ACM Transactions on Database Systems"

281 ,volume="9"

282 ,number="3"

283 ,pages="439-455"

284 ,annotation={

285 Describes concurrent AVL tree implementation. Uses a

286 garbage-collection mechanism to handle concurrent use and deletion

287 of nodes in the tree, but lacks the summary-of-execution-history

288 concept of read-copy locking.

289 .

290 Keeps full list of processes that were active when a given

291 node was to be deleted, and waits until all such processes have

292 -terminated- before allowing this node to be reused. This is

293 not described in great detail -- one could imagine using process

294 IDs for this if the ID space was large enough that overlapping

295 never occurred.

296 .

297 This restriction makes this algorithm unsuitable for use in

298 systems comprised of long-lived processes. It also produces

299 completely unacceptable overhead in systems with large numbers

300 of processes. Finally, it is specific to AVL trees.

301 }

302 }

303

304 @Conference{RichardRashid87a

305 ,Author="Richard Rashid and Avadis Tevanian and Michael Young and

306 David Golub and Robert Baron and David Black and William Bolosky and

307 Jonathan Chew"

308 ,Title="Machine-Independent Virtual Memory Management for Paged

309 Uniprocessor and Multiprocessor Architectures"

310 ,Booktitle="{2\textsuperscript{nd} Symposium on Architectural Support

311 for Programming Languages and Operating Systems}"

312 ,Publisher="Association for Computing Machinery"

313 ,Month="October"

314 ,Year="1987"

315 ,pages="31-39"

316 ,Address="Palo Alto, CA"

317 ,note="Available:

318 \url{http://www.cse.ucsc.edu/~randal/221/rashid-machvm.pdf}

319 [Viewed February 17, 2005]"

320 ,annotation={

321 Describes lazy TLB flush, where one waits for each CPU to pass

322 through a scheduling-clock interrupt before reusing a given range

323 of virtual address. Does not describe how one determines that

324 all CPUs have in fact taken such an interrupt, though there are

325 no shortage of straightforward methods for accomplishing this.

326 .

327 Note that it does not make sense to just wait a fixed amount of

328 time, since a given CPU might have interrupts disabled for an

329 extended amount of time.

330 }

331 }

332

333 @article{BarbaraLiskov1988ArgusCACM

334 ,author = {Barbara Liskov}

335 ,title = {Distributed programming in {Argus}}

336 ,journal = {Commun. ACM}

337 ,volume = {31}

338 ,number = {3}

339 ,year = {1988}

340 ,issn = {0001-0782}

341 ,pages = {300--312}

342 ,doi = {http://doi.acm.org/10.1145/42392.42399}

343 ,publisher = {ACM}

344 ,address = {New York, NY, USA}

345 ,annotation={

346 At the top of page 307: "Conflicts with deposits and withdrawals

347 are necessary if the reported total is to be up to date. They

348 could be avoided by having total return a sum that is slightly

349 out of date." Relies on semantics -- approximate numerical

350 values sometimes OK.

351 }

352 }

353

354 @techreport{Hennessy89

355 ,author="James P. Hennessy and Damian L. Osisek and Joseph W. {Seigh II}"

356 ,title="Passive Serialization in a Multitasking Environment"

357 ,institution="US Patent and Trademark Office"

358 ,address="Washington, DC"

359 ,year="1989"

360 ,number="US Patent 4,809,168 (lapsed)"

361 ,month="February"

362 ,pages="11"

363 }

364

365 @techreport{Pugh90

366 ,author="William Pugh"

367 ,title="Concurrent Maintenance of Skip Lists"

368 ,institution="Institute of Advanced Computer Science Studies, Department of Computer Science, University of Maryland"

369 ,address="College Park, Maryland"

370 ,year="1990"

371 ,number="CS-TR-2222.1"

372 ,month="June"

373 ,annotation={

374 Concurrent access to skip lists. Has both weak and strong search.

375 Uses concept of ``garbage queue'', but has no real way of cleaning

376 the garbage efficiently.

377 .

378 Appears to be an independent invention of an RCU-like mechanism.

379 }

380 }

381

382 # Was Adams91, see also syncrefs.bib.

383 @Book{Andrews91textbook

384 ,Author="Gregory R. Andrews"

385 ,title="Concurrent Programming, Principles, and Practices"

386 ,Publisher="Benjamin Cummins"

387 ,Year="1991"

388 ,annotation={

389 Has a few paragraphs describing ``chaotic relaxation'', a

390 numerical analysis technique that allows multiprocessors to

391 avoid synchronization overhead by using possibly-stale data.

392 .

393 Seems like this is descended from yet another independent

394 invention of RCU-like function -- but this is restricted

395 in that reclamation is not necessary.

396 }

397 }

398

399 @phdthesis{HMassalinPhD

400 ,author="H. Massalin"

401 ,title="Synthesis: An Efficient Implementation of Fundamental Operating

402 System Services"

403 ,school="Columbia University"

404 ,address="New York, NY"

405 ,year="1992"

406 ,annotation={

407 Mondo optimizing compiler.

408 Wait-free stuff.

409 Good advice: defer work to avoid synchronization. See page 90

410 (PDF page 106), Section 5.4, fourth bullet point.

411 }

412 }

413

414 @unpublished{Jacobson93

415 ,author="Van Jacobson"

416 ,title="Avoid Read-Side Locking Via Delayed Free"

417 ,year="1993"

418 ,month="September"

419 ,note="private communication"

420 ,annotation={

421 Use fixed time delay to approximate grace period. Very simple,

422 but subject to random memory corruption under heavy load.

423 .

424 Independent invention of RCU-like mechanism.

425 }

426 }

427

428 @Conference{AjuJohn95

429 ,Author="Aju John"

430 ,Title="Dynamic vnodes -- Design and Implementation"

431 ,Booktitle="{USENIX Winter 1995}"

432 ,Publisher="USENIX Association"

433 ,Month="January"

434 ,Year="1995"

435 ,pages="11-23"

436 ,Address="New Orleans, LA"

437 ,note="Available:

438 \url{https://www.usenix.org/publications/library/proceedings/neworl/full_papers/john.a}

439 [Viewed October 1, 2010]"

440 ,annotation={

441 Age vnodes out of the cache, and have a fixed time set by a kernel

442 parameter. Not clear that all races were in fact correctly handled.

443 Used a 20-minute time by default, which would most definitely not

444 be suitable during DoS attacks or virus scans.

445 .

446 Apparently independent invention of RCU-like mechanism.

447 }

448 }

449

450 @conference{Pu95a

451 ,Author = "Calton Pu and Tito Autrey and Andrew Black and Charles Consel and

452 Crispin Cowan and Jon Inouye and Lakshmi Kethana and Jonathan Walpole and

453 Ke Zhang"

454 ,Title = "Optimistic Incremental Specialization: Streamlining a Commercial

455 ,Operating System"

456 ,Booktitle = "15\textsuperscript{th} ACM Symposium on

457 ,Operating Systems Principles (SOSP'95)"

458 ,address = "Copper Mountain, CO"

459 ,month="December"

460 ,year="1995"

461 ,pages="314-321"

462 ,annotation={

463 Uses a replugger, but with a flag to signal when people are

464 using the resource at hand. Only one reader at a time.

465 }

466 }

467

468 @conference{Cowan96a

469 ,Author = "Crispin Cowan and Tito Autrey and Charles Krasic and

470 ,Calton Pu and Jonathan Walpole"

471 ,Title = "Fast Concurrent Dynamic Linking for an Adaptive Operating System"

472 ,Booktitle = "International Conference on Configurable Distributed Systems

473 (ICCDS'96)"

474 ,address = "Annapolis, MD"

475 ,month="May"

476 ,year="1996"

477 ,pages="108"

478 ,isbn="0-8186-7395-8"

479 ,annotation={

480 Uses a replugger, but with a counter to signal when people are

481 using the resource at hand. Allows multiple readers.

482 }

483 }

484

485 @techreport{Slingwine95

486 ,author="John D. Slingwine and Paul E. McKenney"

487 ,title="Apparatus and Method for Achieving Reduced Overhead Mutual

488 Exclusion and Maintaining Coherency in a Multiprocessor System

489 Utilizing Execution History and Thread Monitoring"

490 ,institution="US Patent and Trademark Office"

491 ,address="Washington, DC"

492 ,year="1995"

493 ,number="US Patent 5,442,758"

494 ,month="August"

495 ,annotation={

496 Describes the parallel RCU infrastructure. Includes NUMA aspect

497 (structure of bitmap can reflect bus structure of computer system).

498 .

499 Another independent invention of an RCU-like mechanism, but the

500 "real" RCU this time!

501 }

502 }

503

504 @techreport{Slingwine97

505 ,author="John D. Slingwine and Paul E. McKenney"

506 ,title="Method for Maintaining Data Coherency Using Thread Activity

507 Summaries in a Multicomputer System"

508 ,institution="US Patent and Trademark Office"

509 ,address="Washington, DC"

510 ,year="1997"

511 ,number="US Patent 5,608,893"

512 ,month="March"

513 ,pages="19"

514 ,annotation={

515 Describes use of RCU to synchronize data between a pair of

516 SMP/NUMA computer systems.

517 }

518 }

519

520 @techreport{Slingwine98

521 ,author="John D. Slingwine and Paul E. McKenney"

522 ,title="Apparatus and Method for Achieving Reduced Overhead Mutual

523 Exclusion and Maintaining Coherency in a Multiprocessor System

524 Utilizing Execution History and Thread Monitoring"

525 ,institution="US Patent and Trademark Office"

526 ,address="Washington, DC"

527 ,year="1998"

528 ,number="US Patent 5,727,209"

529 ,month="March"

530 ,annotation={

531 Describes doing an atomic update by copying the data item and

532 then substituting it into the data structure.

533 }

534 }

535

536 @Conference{McKenney98

537 ,Author="Paul E. McKenney and John D. Slingwine"

538 ,Title="Read-Copy Update: Using Execution History to Solve Concurrency

539 Problems"

540 ,Booktitle="{Parallel and Distributed Computing and Systems}"

541 ,Month="October"

542 ,Year="1998"

543 ,pages="509-518"

544 ,Address="Las Vegas, NV"

545 ,annotation={

546 Describes and analyzes RCU mechanism in DYNIX/ptx. Describes

547 application to linked list update and log-buffer flushing.

548 Defines 'quiescent state'. Includes both measured and analytic

549 evaluation.

550 http://www.rdrop.com/users/paulmck/RCU/rclockpdcsproof.pdf

551 [Viewed December 3, 2007]

552 }

553 }

554

555 @Conference{Gamsa99

556 ,Author="Ben Gamsa and Orran Krieger and Jonathan Appavoo and Michael Stumm"

557 ,Title="Tornado: Maximizing Locality and Concurrency in a Shared Memory

558 Multiprocessor Operating System"

559 ,Booktitle="{Proceedings of the 3\textsuperscript{rd} Symposium on

560 Operating System Design and Implementation}"

561 ,Month="February"

562 ,Year="1999"

563 ,pages="87-100"

564 ,Address="New Orleans, LA"

565 ,annotation={

566 Use of RCU-like facility in K42/Tornado. Another independent

567 invention of RCU.

568 See especially pages 7-9 (Section 5).

569 http://www.usenix.org/events/osdi99/full_papers/gamsa/gamsa.pdf

570 [Viewed August 30, 2006]

571 }

572 }

573

574 @unpublished{RustyRussell2000a

575 ,Author="Rusty Russell"

576 ,Title="Re: modular net drivers"

577 ,month="June"

578 ,year="2000"

579 ,day="23"

580 ,note="Available:

581 \url{http://oss.sgi.com/projects/netdev/archive/2000-06/msg00250.html}

582 [Viewed April 10, 2006]"

583 ,annotation={

584 Proto-RCU proposal from Phil Rumpf and Rusty Russell.

585 Yet another independent invention of RCU.

586 Outline of algorithm to unload modules...

587 .

588 Appeared on net-dev mailing list.

589 }

590 }

591

592 @unpublished{RustyRussell2000b

593 ,Author="Rusty Russell"

594 ,Title="Re: modular net drivers"

595 ,month="June"

596 ,year="2000"

597 ,day="24"

598 ,note="Available:

599 \url{http://oss.sgi.com/projects/netdev/archive/2000-06/msg00254.html}

600 [Viewed April 10, 2006]"

601 ,annotation={

602 Proto-RCU proposal from Phil Rumpf and Rusty Russell.

603 .

604 Appeared on net-dev mailing list.

605 }

606 }

607

608 @unpublished{McKenney01b

609 ,Author="Paul E. McKenney and Dipankar Sarma"

610 ,Title="Read-Copy Update Mutual Exclusion in {Linux}"

611 ,month="February"

612 ,year="2001"

613 ,note="Available:

614 \url{http://lse.sourceforge.net/locking/rcu/rcupdate_doc.html}

615 [Viewed October 18, 2004]"

616 ,annotation={

617 Prototypical Linux documentation for RCU.

618 }

619 }

620

621 @techreport{Slingwine01

622 ,author="John D. Slingwine and Paul E. McKenney"

623 ,title="Apparatus and Method for Achieving Reduced Overhead Mutual

624 Exclusion and Maintaining Coherency in a Multiprocessor System

625 Utilizing Execution History and Thread Monitoring"

626 ,institution="US Patent and Trademark Office"

627 ,address="Washington, DC"

628 ,year="2001"

629 ,number="US Patent 6,219,690"

630 ,month="April"

631 ,annotation={

632 'Change in mode' aspect of RCU. Can be thought of as a lazy barrier.

633 }

634 }

635

636 @Conference{McKenney01a

637 ,Author="Paul E. McKenney and Jonathan Appavoo and Andi Kleen and

638 Orran Krieger and Rusty Russell and Dipankar Sarma and Maneesh Soni"

639 ,Title="Read-Copy Update"

640 ,Booktitle="{Ottawa Linux Symposium}"

641 ,Month="July"

642 ,Year="2001"

643 ,note="Available:

644 \url{https://kernel.org/doc/ols/2001/read-copy.pdf}

645 \url{http://www.rdrop.com/users/paulmck/RCU/rclock_OLS.2001.05.01c.pdf}

646 [Viewed June 23, 2004]"

647 ,annotation={

648 Described RCU, and presented some patches implementing and using

649 it in the Linux kernel.

650 }

651 }

652

653 @unpublished{McKenney01f

654 ,Author="Paul E. McKenney"

655 ,Title="{RFC:} patch to allow lock-free traversal of lists with insertion"

656 ,month="October"

657 ,year="2001"

658 ,note="Available:

659 \url{http://marc.theaimsgroup.com/?l=linux-kernel&m=100259266316456&w=2}

660 [Viewed June 23, 2004]"

661 ,annotation={

662 Memory-barrier and Alpha thread. 100 messages, not too bad...

663 }

664 }

665

666 @unpublished{Spraul01

667 ,Author="Manfred Spraul"

668 ,Title="Re: {RFC:} patch to allow lock-free traversal of lists with insertion"

669 ,month="October"

670 ,year="2001"

671 ,note="Available:

672 \url{http://marc.theaimsgroup.com/?l=linux-kernel&m=100264675012867&w=2}

673 [Viewed June 23, 2004]"

674 ,annotation={

675 Suggested burying memory barriers in Linux's list-manipulation

676 primitives.

677 }

678 }

679

680 @unpublished{LinusTorvalds2001a

681 ,Author="Linus Torvalds"

682 ,Title="{Re:} {[Lse-tech]} {Re:} {RFC:} patch to allow lock-free traversal of lists with insertion"

683 ,month="October"

684 ,year="2001"

685 ,note="Available:

686 \url{https://lore.kernel.org/r/Pine.LNX.4.33.0110131015410.8707-100000@penguin.transmeta.com}

687 [Viewed August 21, 2004]"

688 ,annotation={

689 }

690 }

691

692 @unpublished{Blanchard02a

693 ,Author="Anton Blanchard"

694 ,Title="some RCU dcache and ratcache results"

695 ,month="March"

696 ,year="2002"

697 ,note="Available:

698 \url{http://marc.theaimsgroup.com/?l=linux-kernel&m=101637107412972&w=2}

699 [Viewed October 18, 2004]"

700 }

701

702 @conference{Michael02b

703 ,author="Maged M. Michael"

704 ,title="High Performance Dynamic Lock-Free Hash Tables and List-Based Sets"

705 ,Year="2002"

706 ,Month="August"

707 ,booktitle="{Proceedings of the 14\textsuperscript{th} Annual ACM

708 Symposium on Parallel

709 Algorithms and Architecture}"

710 ,pages="73-82"

711 ,annotation={

712 Like the title says...

713 }

714 }

715

716 @Conference{Linder02a

717 ,Author="Hanna Linder and Dipankar Sarma and Maneesh Soni"

718 ,Title="Scalability of the Directory Entry Cache"

719 ,Booktitle="{Ottawa Linux Symposium}"

720 ,Month="June"

721 ,Year="2002"

722 ,pages="289-300"

723 ,annotation={

724 Measured scalability of Linux 2.4 kernel's directory-entry cache

725 (dcache), and measured some scalability enhancements.

726 }

727 }

728

729 @Conference{McKenney02a

730 ,Author="Paul E. McKenney and Dipankar Sarma and

731 Andrea Arcangeli and Andi Kleen and Orran Krieger and Rusty Russell"

732 ,Title="Read-Copy Update"

733 ,Booktitle="{Ottawa Linux Symposium}"

734 ,Month="June"

735 ,Year="2002"

736 ,pages="338-367"

737 ,note="Available:

738 \url{http://www.linux.org.uk/~ajh/ols2002_proceedings.pdf.gz}

739 [Viewed June 23, 2004]"

740 ,annotation={

741 Presented and compared a number of RCU implementations for the

742 Linux kernel.

743 }

744 }

745

746 @unpublished{Sarma02a

747 ,Author="Dipankar Sarma"

748 ,Title="specweb99: dcache scalability results"

749 ,month="July"

750 ,year="2002"

751 ,note="Available:

752 \url{http://marc.theaimsgroup.com/?l=linux-kernel&m=102645767914212&w=2}

753 [Viewed June 23, 2004]"

754 ,annotation={

755 Compare fastwalk and RCU for dcache. RCU won.

756 }

757 }

758

759 @unpublished{Barbieri02

760 ,Author="Luca Barbieri"

761 ,Title="Re: {[PATCH]} Initial support for struct {vfs\_cred}"

762 ,month="August"

763 ,year="2002"

764 ,note="Available:

765 \url{http://marc.theaimsgroup.com/?l=linux-kernel&m=103082050621241&w=2}

766 [Viewed: June 23, 2004]"

767 ,annotation={

768 Suggested RCU for vfs\_shared\_cred.

769 }

770 }

771

772 @conference{Michael02a

773 ,author="Maged M. Michael"

774 ,title="Safe Memory Reclamation for Dynamic Lock-Free Objects Using Atomic

775 Reads and Writes"

776 ,Year="2002"

777 ,Month="August"

778 ,booktitle="{Proceedings of the 21\textsuperscript{st} Annual ACM

779 Symposium on Principles of Distributed Computing}"

780 ,pages="21-30"

781 ,annotation={

782 Each thread keeps an array of pointers to items that it is

783 currently referencing. Sort of an inside-out garbage collection

784 mechanism, but one that requires the accessing code to explicitly

785 state its needs. Also requires read-side memory barriers on

786 most architectures.

787 }

788 }

789

790 @unpublished{Dickins02a

791 ,author="Hugh Dickins"

792 ,title="Use RCU for System-V IPC"

793 ,year="2002"

794 ,month="October"

795 ,note="private communication"

796 }

797

798 @InProceedings{HerlihyLM02

799 ,author={Maurice Herlihy and Victor Luchangco and Mark Moir}

800 ,title="The Repeat Offender Problem: A Mechanism for Supporting Dynamic-Sized,

801 Lock-Free Data Structures"

802 ,booktitle={Proceedings of 16\textsuperscript{th} International

803 Symposium on Distributed Computing}

804 ,year=2002

805 ,month="October"

806 ,pages="339-353"

807 }

808

809 @unpublished{Sarma02b

810 ,Author="Dipankar Sarma"

811 ,Title="Some dcache\_rcu benchmark numbers"

812 ,month="October"

813 ,year="2002"

814 ,note="Available:

815 \url{http://marc.theaimsgroup.com/?l=linux-kernel&m=103462075416638&w=2}

816 [Viewed June 23, 2004]"

817 ,annotation={

818 Performance of dcache RCU on kernbench for 16x NUMA-Q and 1x,

819 2x, and 4x systems. RCU does no harm, and helps on 16x.

820 }

821 }

822

823 @unpublished{MingmingCao2002IPCRCU

824 ,Author="Mingming Cao"

825 ,Title="[PATCH]updated ipc lock patch"

826 ,month="October"

827 ,year="2002"

828 ,note="Available:

829 \url{https://lore.kernel.org/r/3DB86B05.447E7410@us.ibm.com}

830 [Viewed February 15, 2014]"

831 ,annotation={

832 Mingming Cao's patch to introduce RCU to SysV IPC.

833 }

834 }

835

836 @unpublished{LinusTorvalds2003a

837 ,Author="Linus Torvalds"

838 ,Title="Re: {[PATCH]} small fixes in brlock.h"

839 ,month="March"

840 ,year="2003"

841 ,note="Available:

842 \url{https://lore.kernel.org/r/Pine.LNX.4.44.0303091831560.2129-100000@home.transmeta.com}

843 [Viewed March 13, 2006]"

844 ,annotation={

845 Linus suggests replacing brlock with RCU and/or seqlocks:

846 .

847 'It's entirely possible that the current user could be replaced

848 by RCU and/or seqlocks, and we could get rid of brlocks entirely.'

849 .

850 Stephen Hemminger responds by replacing them with RCU.

851 }

852 }

853

854 @article{Appavoo03a

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. Auslander and D. J. Edelsohn and

857 B. Gamsa and G. R. Ganger and P. McKenney and M. Ostrowski and

858 B. Rosenburg and M. Stumm and J. Xenidis"

859 ,title="Enabling Autonomic Behavior in Systems Software With Hot Swapping"

860 ,Year="2003"

861 ,Month="January"

862 ,journal="IBM Systems Journal"

863 ,volume="42"

864 ,number="1"

865 ,pages="60-76"

866 ,annotation={

867 Use of RCU to enable hot-swapping for autonomic behavior in K42.

868 }

869 }

870

871 @unpublished{Seigh03

872 ,author="Joseph W. {Seigh II}"

873 ,title="Read Copy Update"

874 ,Year="2003"

875 ,Month="March"

876 ,note="email correspondence"

877 ,annotation={

878 Described the relationship of the VM/XA passive serialization to RCU.

879 }

880 }

881

882 @Conference{Arcangeli03

883 ,Author="Andrea Arcangeli and Mingming Cao and Paul E. McKenney and

884 Dipankar Sarma"

885 ,Title="Using Read-Copy Update Techniques for {System V IPC} in the

886 {Linux} 2.5 Kernel"

887 ,Booktitle="Proceedings of the 2003 USENIX Annual Technical Conference

888 (FREENIX Track)"

889 ,Publisher="USENIX Association"

890 ,year="2003"

891 ,month="June"

892 ,pages="297-310"

893 ,annotation={

894 Compared updated RCU implementations for the Linux kernel, and

895 described System V IPC use of RCU, including order-of-magnitude

896 performance improvements.

897 http://www.rdrop.com/users/paulmck/RCU/rcu.FREENIX.2003.06.14.pdf

898 }

899 }

900

901 @Conference{Soules03a

902 ,Author="Craig A. N. Soules and Jonathan Appavoo and Kevin Hui and

903 Dilma {Da Silva} and Gregory R. Ganger and Orran Krieger and

904 Michael Stumm and Robert W. Wisniewski and Marc Auslander and

905 Michal Ostrowski and Bryan Rosenburg and Jimi Xenidis"

906 ,Title="System Support for Online Reconfiguration"

907 ,Booktitle="Proceedings of the 2003 USENIX Annual Technical Conference"

908 ,Publisher="USENIX Association"

909 ,year="2003"

910 ,month="June"

911 ,pages="141-154"

912 }

913

914 @article{McKenney03a

915 ,author="Paul E. McKenney"

916 ,title="Using {RCU} in the {Linux} 2.5 Kernel"

917 ,Year="2003"

918 ,Month="October"

919 ,journal="Linux Journal"

920 ,volume="1"

921 ,number="114"

922 ,pages="18-26"

923 ,note="Available:

924 \url{http://www.linuxjournal.com/article/6993}

925 [Viewed November 14, 2007]"

926 ,annotation={

927 Reader-friendly intro to RCU, with the infamous old-man-and-brat

928 cartoon.

929 }

930 }

931

932 @unpublished{Sarma03a

933 ,Author="Dipankar Sarma"

934 ,Title="RCU low latency patches"

935 ,month="December"

936 ,year="2003"

937 ,note="Message ID: 20031222180114.GA2248@in.ibm.com"

938 ,annotation={

939 dipankar/ct.2004.03.27/RCUll.2003.12.22.patch

940 }

941 }

942

943 @techreport{Friedberg03a

944 ,author="Stuart A. Friedberg"

945 ,title="Lock-Free Wild Card Search Data Structure and Method"

946 ,institution="US Patent and Trademark Office"

947 ,address="Washington, DC"

948 ,year="2003"

949 ,number="US Patent 6,662,184"

950 ,month="December"

951 ,pages="112"

952 ,annotation={

953 Applies RCU to a wildcard-search Patricia tree in order to permit

954 synchronization-free lookup. RCU is used to retain removed nodes

955 for a grace period before freeing them.

956 }

957 }

958

959 @article{McKenney04a

960 ,author="Paul E. McKenney and Dipankar Sarma and Maneesh Soni"

961 ,title="Scaling dcache with {RCU}"

962 ,Year="2004"

963 ,Month="January"

964 ,journal="Linux Journal"

965 ,volume="1"

966 ,number="118"

967 ,pages="38-46"

968 ,annotation={

969 Reader friendly intro to dcache and RCU.

970 http://www.linuxjournal.com/node/7124

971 [Viewed December 26, 2010]

972 }

973 }

974

975 @Conference{McKenney04b

976 ,Author="Paul E. McKenney"

977 ,Title="{RCU} vs. Locking Performance on Different {CPUs}"

978 ,Booktitle="{linux.conf.au}"

979 ,Month="January"

980 ,Year="2004"

981 ,Address="Adelaide, Australia"

982 ,note="Available:

983 \url{http://www.linux.org.au/conf/2004/abstracts.html#90}

984 \url{http://www.rdrop.com/users/paulmck/RCU/lockperf.2004.01.17a.pdf}

985 [Viewed June 23, 2004]"

986 ,annotation={

987 Compares performance of RCU to that of other locking primitives

988 over a number of CPUs (x86, Opteron, Itanium, and PPC).

989 }

990 }

991

992 @unpublished{Sarma04a

993 ,Author="Dipankar Sarma"

994 ,Title="{[PATCH]} {RCU} for low latency (experimental)"

995 ,month="March"

996 ,year="2004"

997 ,note="\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=108003746402892&w=2}"

998 ,annotation={

999 Head of thread: dipankar/2004.03.23/rcu-low-lat.1.patch

1000 }

1001 }

1002

1003 @unpublished{Sarma04b

1004 ,Author="Dipankar Sarma"

1005 ,Title="Re: {[PATCH]} {RCU} for low latency (experimental)"

1006 ,month="March"

1007 ,year="2004"

1008 ,note="\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=108016474829546&w=2}"

1009 ,annotation={

1010 dipankar/rcuth.2004.03.24/rcu-throttle.patch

1011 }

1012 }

1013

1014 @unpublished{Spraul04a

1015 ,Author="Manfred Spraul"

1016 ,Title="[RFC] 0/5 rcu lock update"

1017 ,month="May"

1018 ,year="2004"

1019 ,note="Available:

1020 \url{http://marc.theaimsgroup.com/?l=linux-kernel&m=108546407726602&w=2}

1021 [Viewed June 23, 2004]"

1022 ,annotation={

1023 Hierarchical-bitmap patch for RCU infrastructure.

1024 }

1025 }

1026

1027 @unpublished{Steiner04a

1028 ,Author="Jack Steiner"

1029 ,Title="Re: [Lse-tech] [RFC, PATCH] 1/5 rcu lock update:

1030 Add per-cpu batch counter"

1031 ,month="May"

1032 ,year="2004"

1033 ,note="Available:

1034 \url{http://marc.theaimsgroup.com/?l=linux-kernel&m=108551764515332&w=2}

1035 [Viewed June 23, 2004]"

1036 ,annotation={

1037 RCU runs reasonably on a 512-CPU SGI using Manfred Spraul's patches,

1038 which may be found at:

1039 https://lore.kernel.org/r/40AC9823.6020709@colorfullife.com (split vars into cachelines)

1040 https://lore.kernel.org/r/Pine.LNX.4.44.0405222141260.11106-100000@dbl.q-ag.de (cpu_quiet() patch)

1041 https://lore.kernel.org/r/200405250535.i4P5ZJo8017583@dbl.q-ag.de (0/5)

1042 https://lore.kernel.org/r/200405250535.i4P5ZKAQ017591@dbl.q-ag.de (1/5)

1043 https://lore.kernel.org/r/20040525203215.GB5127@sgi.com (works for Jack)

1044 https://lore.kernel.org/r/200405250535.i4P5ZLiR017599@dbl.q-ag.de (2/5)

1045 https://lore.kernel.org/r/200405250535.i4P5ZMFt017607@dbl.q-ag.de (3/5)

1046 https://lore.kernel.org/r/200405250535.i4P5ZN6g017615@dbl.q-ag.de (4/5)

1047 https://lore.kernel.org/r/200405250535.i4P5ZO7I017623@dbl.q-ag.de (5/5)

1048 }

1049 }

1050

1051 @Conference{Sarma04c

1052 ,Author="Dipankar Sarma and Paul E. McKenney"

1053 ,Title="Making {RCU} Safe for Deep Sub-Millisecond Response

1054 Realtime Applications"

1055 ,Booktitle="Proceedings of the 2004 USENIX Annual Technical Conference

1056 (FREENIX Track)"

1057 ,Publisher="USENIX Association"

1058 ,year="2004"

1059 ,month="June"

1060 ,pages="182-191"

1061 ,annotation={

1062 Describes and compares a number of modifications to the Linux RCU

1063 implementation that make it friendly to realtime applications.

1064 https://www.usenix.org/conference/2004-usenix-annual-technical-conference/making-rcu-safe-deep-sub-millisecond-response

1065 [Viewed July 26, 2012]

1066 }

1067 }

1068

1069 @article{MagedMichael04a

1070 ,author="Maged M. Michael"

1071 ,title="Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects"

1072 ,Year="2004"

1073 ,Month="June"

1074 ,journal="IEEE Transactions on Parallel and Distributed Systems"

1075 ,volume="15"

1076 ,number="6"

1077 ,pages="491-504"

1078 ,url="Available:

1079 \url{http://www.research.ibm.com/people/m/michael/ieeetpds-2004.pdf}

1080 [Viewed March 1, 2005]"

1081 ,annotation={

1082 New canonical hazard-pointer citation.

1083 }

1084 }

1085

1086 @phdthesis{PaulEdwardMcKenneyPhD

1087 ,author="Paul E. McKenney"

1088 ,title="Exploiting Deferred Destruction:

1089 An Analysis of Read-Copy-Update Techniques

1090 in Operating System Kernels"

1091 ,school="OGI School of Science and Engineering at

1092 Oregon Health and Sciences University"

1093 ,year="2004"

1094 ,annotation={

1095 Describes RCU implementations and presents design patterns

1096 corresponding to common uses of RCU in several operating-system

1097 kernels.

1098 http://www.rdrop.com/users/paulmck/RCU/RCUdissertation.2004.07.14e1.pdf

1099 [Viewed October 15, 2004]

1100 }

1101 }

1102

1103 @unpublished{PaulEMcKenney2004rcu:dereference

1104 ,Author="Dipankar Sarma"

1105 ,Title="{Re: RCU : Abstracted RCU dereferencing [5/5]}"

1106 ,month="August"

1107 ,year="2004"

1108 ,note="Available:

1109 \url{https://lore.kernel.org/r/20040807192424.GF3936@in.ibm.com}

1110 [Viewed June 8, 2010]"

1111 ,annotation={

1112 Introduce rcu_dereference().

1113 }

1114 }

1115

1116 @unpublished{JimHouston04a

1117 ,Author="Jim Houston"

1118 ,Title="{[RFC\&PATCH] Alternative {RCU} implementation}"

1119 ,month="August"

1120 ,year="2004"

1121 ,note="Available:

1122 \url{https://lore.kernel.org/r/1093873222.984.12.camel@new.localdomain}

1123 [Viewed February 17, 2005]"

1124 ,annotation={

1125 Uses active code in rcu_read_lock() and rcu_read_unlock() to

1126 make RCU happen, allowing RCU to function on CPUs that do not

1127 receive a scheduling-clock interrupt.

1128 }

1129 }

1130

1131 @unpublished{TomHart04a

1132 ,Author="Thomas E. Hart"

1133 ,Title="Master's Thesis: Applying Lock-free Techniques to the {Linux} Kernel"

1134 ,month="October"

1135 ,year="2004"

1136 ,note="Available:

1137 \url{http://www.cs.toronto.edu/~tomhart/masters_thesis.html}

1138 [Viewed October 15, 2004]"

1139 ,annotation={

1140 Proposes comparing RCU to lock-free methods for the Linux kernel.

1141 }

1142 }

1143

1144 @unpublished{Vaddagiri04a

1145 ,Author="Srivatsa Vaddagiri"

1146 ,Title="Subject: [RFC] Use RCU for tcp\_ehash lookup"

1147 ,month="October"

1148 ,year="2004"

1149 ,note="Available:

1150 \url{http://marc.theaimsgroup.com/?t=109395731700004&r=1&w=2}

1151 [Viewed October 18, 2004]"

1152 ,annotation={

1153 Srivatsa's RCU patch for tcp_ehash lookup.

1154 }

1155 }

1156

1157 @unpublished{Thirumalai04a

1158 ,Author="Ravikiran Thirumalai"

1159 ,Title="Subject: [patchset] Lockfree fd lookup 0 of 5"

1160 ,month="October"

1161 ,year="2004"

1162 ,note="Available:

1163 \url{http://marc.theaimsgroup.com/?t=109144217400003&r=1&w=2}

1164 [Viewed October 18, 2004]"

1165 ,annotation={

1166 Ravikiran's lockfree FD patch.

1167 }

1168 }

1169

1170 @unpublished{Thirumalai04b

1171 ,Author="Ravikiran Thirumalai"

1172 ,Title="Subject: Re: [patchset] Lockfree fd lookup 0 of 5"

1173 ,month="October"

1174 ,year="2004"

1175 ,note="Available:

1176 \url{http://marc.theaimsgroup.com/?l=linux-kernel&m=109152521410459&w=2}

1177 [Viewed October 18, 2004]"

1178 ,annotation={

1179 Ravikiran's lockfree FD patch.

1180 }

1181 }

1182

1183 @unpublished{PaulEMcKenney2004rcu:assign:pointer

1184 ,Author="Paul E. McKenney"

1185 ,Title="{[PATCH 1/3] RCU: \url{rcu_assign_pointer()} removal of memory barriers}"

1186 ,month="October"

1187 ,year="2004"

1188 ,note="Available:

1189 \url{https://lore.kernel.org/r/20041023202723.GA1930@us.ibm.com}

1190 [Viewed June 8, 2010]"

1191 ,annotation={

1192 Introduce rcu_assign_pointer().

1193 }

1194 }

1195

1196 @unpublished{JamesMorris04a

1197 ,Author="James Morris"

1198 ,Title="{[PATCH 2/3] SELinux} scalability - convert {AVC} to {RCU}"

1199 ,day="15"

1200 ,month="November"

1201 ,year="2004"

1202 ,note="\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=110054979416004&w=2}"

1203 ,annotation={

1204 James Morris posts Kaigai Kohei's patch to LKML.

1205 [Viewed December 10, 2004]

1206 Kaigai's patch is at https://lore.kernel.org/r/200409271057.i8RAvcA1007873@mailsv.bs1.fc.nec.co.jp

1207 }

1208 }

1209

1210 @unpublished{JamesMorris04b

1211 ,Author="James Morris"

1212 ,Title="Recent Developments in {SELinux} Kernel Performance"

1213 ,month="December"

1214 ,year="2004"

1215 ,note="Available:

1216 \url{http://www.livejournal.com/users/james_morris/2153.html}

1217 [Viewed December 10, 2004]"

1218 ,annotation={

1219 RCU helps SELinux performance. ;-) Made LWN.

1220 }

1221 }

1222

1223 @unpublished{PaulMcKenney2005RCUSemantics

1224 ,Author="Paul E. McKenney and Jonathan Walpole"

1225 ,Title="{RCU} Semantics: A First Attempt"

1226 ,month="January"

1227 ,year="2005"

1228 ,day="30"

1229 ,note="Available:

1230 \url{http://www.rdrop.com/users/paulmck/RCU/rcu-semantics.2005.01.30a.pdf}

1231 [Viewed December 6, 2009]"

1232 ,annotation={

1233 Early derivation of RCU semantics.

1234 }

1235 }

1236

1237 @unpublished{PaulMcKenney2005e

1238 ,Author="Paul E. McKenney"

1239 ,Title="Real-Time Preemption and {RCU}"

1240 ,month="March"

1241 ,year="2005"

1242 ,day="17"

1243 ,note="Available:

1244 \url{https://lore.kernel.org/r/20050318002026.GA2693@us.ibm.com}

1245 [Viewed September 5, 2005]"

1246 ,annotation={

1247 First posting showing how RCU can be safely adapted for

1248 preemptible RCU read side critical sections.

1249 }

1250 }

1251

1252 @unpublished{EsbenNeilsen2005a

1253 ,Author="Esben Neilsen"

1254 ,Title="Re: Real-Time Preemption and {RCU}"

1255 ,month="March"

1256 ,year="2005"

1257 ,day="18"

1258 ,note="Available:

1259 \url{https://lore.kernel.org/r/Pine.OSF.4.05.10503181336310.2466-100000@da410.phys.au.dk}

1260 [Viewed March 30, 2006]"

1261 ,annotation={

1262 Esben Neilsen suggests read-side suppression of grace-period

1263 processing for crude-but-workable realtime RCU. The downside

1264 is indefinite grace periods... But this is OK for experimentation

1265 and testing.

1266 }

1267 }

1268

1269 @unpublished{TomHart05a

1270 ,Author="Thomas E. Hart and Paul E. McKenney and Angela Demke Brown"

1271 ,Title="Efficient Memory Reclamation is Necessary for Fast Lock-Free

1272 Data Structures"

1273 ,month="March"

1274 ,year="2005"

1275 ,note="Available:

1276 \url{ftp://ftp.cs.toronto.edu/csrg-technical-reports/515/}

1277 [Viewed March 4, 2005]"

1278 ,annotation={

1279 Comparison of RCU, QBSR, and EBSR. RCU wins for read-mostly

1280 workloads. ;-)

1281 }

1282 }

1283

1284 @unpublished{JonCorbet2005DeprecateSyncKernel

1285 ,Author="Jonathan Corbet"

1286 ,Title="API change: synchronize_kernel() deprecated"

1287 ,month="May"

1288 ,day="3"

1289 ,year="2005"

1290 ,note="Available:

1291 \url{http://lwn.net/Articles/134484/}

1292 [Viewed May 3, 2005]"

1293 ,annotation={

1294 Jon Corbet describes deprecation of synchronize_kernel()

1295 in favor of synchronize_rcu() and synchronize_sched().

1296 }

1297 }

1298

1299 @unpublished{PaulMcKenney05a

1300 ,Author="Paul E. McKenney"

1301 ,Title="{[RFC]} {RCU} and {CONFIG\_PREEMPT\_RT} progress"

1302 ,month="May"

1303 ,year="2005"

1304 ,note="Available:

1305 \url{https://lore.kernel.org/r/20050510012444.GA3011@us.ibm.com}

1306 [Viewed May 13, 2005]"

1307 ,annotation={

1308 First publication of working lock-based deferred free patches

1309 for the CONFIG_PREEMPT_RT environment.

1310 }

1311 }

1312

1313 @conference{PaulMcKenney05b

1314 ,Author="Paul E. McKenney and Dipankar Sarma"

1315 ,Title="Towards Hard Realtime Response from the {Linux} Kernel on {SMP} Hardware"

1316 ,Booktitle="linux.conf.au 2005"

1317 ,month="April"

1318 ,year="2005"

1319 ,address="Canberra, Australia"

1320 ,note="Available:

1321 \url{http://www.rdrop.com/users/paulmck/RCU/realtimeRCU.2005.04.23a.pdf}

1322 [Viewed May 13, 2005]"

1323 ,annotation={

1324 Realtime turns into making RCU yet more realtime friendly.

1325

	http://lca2005.linux.org.au/Papers/Paul%20McKenney/Towards%20Hard%20Realtime%20Response%20from%20the%20Linux%20Kernel/LKS.2005.04.22a.pdf

1326 }

1327 }

1328

1329 @unpublished{PaulEMcKenneyHomePage

1330 ,Author="Paul E. McKenney"

1331 ,Title="{Paul} {E.} {McKenney}"

1332 ,month="May"

1333 ,year="2005"

1334 ,note="Available:

1335 \url{http://www.rdrop.com/users/paulmck/}

1336 [Viewed May 25, 2005]"

1337 ,annotation={

1338 Paul McKenney's home page.

1339 }

1340 }

1341

1342 @unpublished{PaulEMcKenneyRCUPage

1343 ,Author="Paul E. McKenney"

1344 ,Title="Read-Copy Update {(RCU)}"

1345 ,month="May"

1346 ,year="2005"

1347 ,note="Available:

1348 \url{http://www.rdrop.com/users/paulmck/RCU}

1349 [Viewed May 25, 2005]"

1350 ,annotation={

1351 Paul McKenney's RCU page.

1352 }

1353 }

1354

1355 @unpublished{JosephSeigh2005a

1356 ,Author="Joseph Seigh"

1357 ,Title="{RCU}+{SMR} (hazard pointers)"

1358 ,month="July"

1359 ,year="2005"

1360 ,note="Personal communication"

1361 ,annotation={

1362 Joe Seigh announcing his atomic-ptr-plus project.

1363 http://sourceforge.net/projects/atomic-ptr-plus/

1364 }

1365 }

1366

1367 @unpublished{JosephSeigh2005b

1368 ,Author="Joseph Seigh"

1369 ,Title="Lock-free synchronization primitives"

1370 ,month="July"

1371 ,day="6"

1372 ,year="2005"

1373 ,note="Available:

1374 \url{http://sourceforge.net/projects/atomic-ptr-plus/}

1375 [Viewed August 8, 2005]"

1376 ,annotation={

1377 Joe Seigh's atomic-ptr-plus project.

1378 }

1379 }

1380

1381 @unpublished{PaulMcKenney2005c

1382 ,Author="Paul E.McKenney"

1383 ,Title="{[RFC,PATCH] RCU} and {CONFIG\_PREEMPT\_RT} sane patch"

1384 ,month="August"

1385 ,day="1"

1386 ,year="2005"

1387 ,note="Available:

1388 \url{https://lore.kernel.org/r/20050801171137.GA1754@us.ibm.com}

1389 [Viewed March 14, 2006]"

1390 ,annotation={

1391 First operating counter-based realtime RCU patch posted to LKML.

1392 }

1393 }

1394

1395 @unpublished{PaulMcKenney2005d

1396 ,Author="Paul E. McKenney"

1397 ,Title="Re: [Fwd: Re: [patch] Real-Time Preemption, -RT-2.6.13-rc4-V0.7.52-01]"

1398 ,month="August"

1399 ,day="8"

1400 ,year="2005"

1401 ,note="Available:

1402 \url{https://lore.kernel.org/r/20050808144216.GA1307@us.ibm.com}

1403 [Viewed March 14, 2006]"

1404 ,annotation={

1405 First operating counter-based realtime RCU patch posted to LKML,

1406 but fixed so that various unusual combinations of configuration

1407 parameters all function properly.

1408 }

1409 }

1410

1411 @unpublished{PaulMcKenney2005rcutorture

1412 ,Author="Paul E. McKenney"

1413 ,Title="{[PATCH]} {RCU} torture testing"

1414 ,month="October"

1415 ,day="1"

1416 ,year="2005"

1417 ,note="Available:

1418 \url{https://lore.kernel.org/r/20051001182056.GA1613@us.ibm.com}

1419 [Viewed March 14, 2006]"

1420 ,annotation={

1421 First rcutorture patch.

1422 }

1423 }

1424

1425 @unpublished{DavidSMiller2006HashedLocking

1426 ,Author="David S. Miller"

1427 ,Title="Re: [{PATCH}, {RFC}] {RCU} : {OOM} avoidance and lower latency"

1428 ,month="January"

1429 ,day="6"

1430 ,year="2006"

1431 ,note="Available:

1432 \url{https://lore.kernel.org/r/20060106.231054.43576567.davem@davemloft.net}

1433 [Viewed February 29, 2012]"

1434 ,annotation={

1435 David Miller's view on hashed arrays of locks: used to really

1436 like it, but time he saw an opportunity for this technique,

1437 something else always proved superior. Partitioning or RCU. ;-)

1438 }

1439 }

1440

1441 @conference{ThomasEHart2006a

1442 ,Author="Thomas E. Hart and Paul E. McKenney and Angela Demke Brown"

1443 ,Title="Making Lockless Synchronization Fast: Performance Implications

1444 of Memory Reclamation"

1445 ,Booktitle="20\textsuperscript{th} {IEEE} International Parallel and

1446 Distributed Processing Symposium"

1447 ,month="April"

1448 ,year="2006"

1449 ,day="25-29"

1450 ,address="Rhodes, Greece"

1451 ,note="Available:

1452 \url{http://www.rdrop.com/users/paulmck/RCU/hart_ipdps06.pdf}

1453 [Viewed April 28, 2008]"

1454 ,annotation={

1455 Compares QSBR, HPBR, EBR, and lock-free reference counting.

1456 http://www.cs.toronto.edu/~tomhart/perflab/ipdps06.tgz

1457 }

1458 }

1459

1460 @unpublished{NickPiggin2006radixtree

1461 ,Author="Nick Piggin"

1462 ,Title="[patch 3/3] radix-tree: {RCU} lockless readside"

1463 ,month="June"

1464 ,day="20"

1465 ,year="2006"

1466 ,note="Available:

1467 \url{https://lore.kernel.org/r/20060408134707.22479.33814.sendpatchset@linux.site}

1468 [Viewed March 25, 2008]"

1469 ,annotation={

1470 RCU-protected radix tree.

1471 }

1472 }

1473

1474 @Conference{PaulEMcKenney2006b

1475 ,Author="Paul E. McKenney and Dipankar Sarma and Ingo Molnar and

1476 Suparna Bhattacharya"

1477 ,Title="Extending {RCU} for Realtime and Embedded Workloads"

1478 ,Booktitle="{Ottawa Linux Symposium}"

1479 ,Month="July"

1480 ,Year="2006"

1481 ,pages="v2 123-138"

1482 ,note="Available:

1483 \url{https://kernel.org/doc/ols/2006/ols2006v2-pages-131-146.pdf}

1484 \url{http://www.rdrop.com/users/paulmck/RCU/OLSrtRCU.2006.08.11a.pdf}

1485 [Viewed January 1, 2007]"

1486 ,annotation={

1487 Described how to improve the -rt implementation of realtime RCU.

1488 }

1489 }

1490

1491 @unpublished{WikipediaRCU

1492 ,Author="Paul E. McKenney and Chris Purcell and Algae and Ben Schumin and

1493 Gaius Cornelius and Qwertyus and Neil Conway and Sbw and Blainster and

1494 Canis Rufus and Zoicon5 and Anome and Hal Eisen"

1495 ,Title="Read-Copy Update"

1496 ,month="July"

1497 ,day="8"

1498 ,year="2006"

1499 ,note="\url{https://en.wikipedia.org/wiki/Read-copy-update}"

1500 ,annotation={

1501 Wikipedia RCU page as of July 8 2006.

1502 [Viewed August 21, 2006]

1503 }

1504 }

1505

1506 @Conference{NickPiggin2006LocklessPageCache

1507 ,Author="Nick Piggin"

1508 ,Title="A Lockless Pagecache in Linux---Introduction, Progress, Performance"

1509 ,Booktitle="{Ottawa Linux Symposium}"

1510 ,Month="July"

1511 ,Year="2006"

1512 ,pages="v2 249-254"

1513 ,note="Available:

1514 \url{https://kernel.org/doc/ols/2006/ols2006v2-pages-249-262.pdf}

1515 [Viewed January 11, 2009]"

1516 ,annotation={

1517 Uses RCU-protected radix tree for a lockless page cache.

1518 }

1519 }

1520

1521 @unpublished{PaulEMcKenney2006c

1522 ,Author="Paul E. McKenney"

1523 ,Title="Sleepable {RCU}"

1524 ,month="October"

1525 ,day="9"

1526 ,year="2006"

1527 ,note="Available:

1528 \url{http://lwn.net/Articles/202847/}

1529 Revised:

1530 \url{http://www.rdrop.com/users/paulmck/RCU/srcu.2007.01.14a.pdf}

1531 [Viewed August 21, 2006]"

1532 ,annotation={

1533 LWN article introducing SRCU.

1534 }

1535 }

1536

1537 @unpublished{RobertOlsson2006a

1538 ,Author="Robert Olsson and Stefan Nilsson"

1539 ,Title="{TRASH}: A dynamic {LC}-trie and hash data structure"

1540 ,month="August"

1541 ,day="18"

1542 ,year="2006"

1543 ,note="\url{http://www.nada.kth.se/~snilsson/publications/TRASH/trash.pdf}"

1544 ,annotation={

1545 RCU-protected dynamic trie-hash combination.

1546 [Viewed March 4, 2011]

1547 }

1548 }

1549

1550 @unpublished{ChristophHellwig2006RCU2SRCU

1551 ,Author="Christoph Hellwig"

1552 ,Title="Re: {[-mm PATCH 1/4]} {RCU}: split classic rcu"

1553 ,month="September"

1554 ,day="28"

1555 ,year="2006"

1556 ,note="Available:

1557 \url{https://lore.kernel.org/r/20060928142616.GA20185@infradead.org}

1558 [Viewed March 27, 2008]"

1559 }

1560

1561 @unpublished{PaulEMcKenneyRCUusagePage

1562 ,Author="Paul E. McKenney"

1563 ,Title="{RCU} {Linux} Usage"

1564 ,month="October"

1565 ,year="2006"

1566 ,note="Available:

1567 \url{http://www.rdrop.com/users/paulmck/RCU/linuxusage.html}

1568 [Viewed January 14, 2007]"

1569 ,annotation={

1570 Paul McKenney's RCU page showing graphs plotting Linux-kernel

1571 usage of RCU.

1572 }

1573 }

1574

1575 @unpublished{PaulEMcKenneyRCUusageRawDataPage

1576 ,Author="Paul E. McKenney"

1577 ,Title="Read-Copy Update {(RCU)} Usage in {Linux} Kernel"

1578 ,month="October"

1579 ,year="2006"

1580 ,note="Available:

1581 \url{http://www.rdrop.com/users/paulmck/RCU/linuxusage/rculocktab.html}

1582 [Viewed January 14, 2007]"

1583 ,annotation={

1584 Paul McKenney's RCU page showing Linux usage of RCU in tabular

1585 form, with links to corresponding cscope databases.

1586 }

1587 }

1588

1589 @unpublished{GauthamShenoy2006RCUrwlock

1590 ,Author="Gautham R. Shenoy"

1591 ,Title="[PATCH 4/5] lock\_cpu\_hotplug: Redesign - Lightweight implementation of lock\_cpu\_hotplug"

1592 ,month="October"

1593 ,year="2006"

1594 ,day=26

1595 ,note="Available:

1596 \url{https://lore.kernel.org/r/20061026105731.GE11803@in.ibm.com}

1597 [Viewed January 26, 2009]"

1598 ,annotation={

1599 RCU-based reader-writer lock that allows readers to proceed with

1600 no memory barriers or atomic instruction in absence of writers.

1601 If writer do show up, readers must of course wait as required by

1602 the semantics of reader-writer locking. This is a recursive

1603 lock.

1604 }

1605 }

1606

1607 @unpublished{JensAxboe2006SlowSRCU

1608 ,Author="Jens Axboe"

1609 ,Title="Re: [patch] cpufreq: mark \url{cpufreq_tsc()} as

1610 \url{core_initcall_sync}"

1611 ,month="November"

1612 ,year="2006"

1613 ,day=17

1614 ,note="Available:

1615 \url{https://lore.kernel.org/r/20061117092925.GT7164@kernel.dk}

1616 [Viewed May 28, 2007]"

1617 ,annotation={

1618 SRCU's grace periods are too slow for Jens, even after a

1619 factor-of-three speedup.

1620 Sped-up version of SRCU at https://lore.kernel.org/r/20061118002845.GF2632@us.ibm.com.

1621 }

1622 }

1623

1624 @unpublished{OlegNesterov2006QRCU

1625 ,Author="Oleg Nesterov"

1626 ,Title="Re: [patch] cpufreq: mark {\tt cpufreq\_tsc()} as

1627 {\tt core\_initcall\_sync}"

1628 ,month="November"

1629 ,year="2006"

1630 ,day=19

1631 ,note="Available:

1632 \url{https://lore.kernel.org/r/20061119190027.GA3676@oleg}

1633 [Viewed May 28, 2007]"

1634 ,annotation={

1635 First cut of QRCU. Expanded/corrected versions followed.

1636 Used to be OlegNesterov2007QRCU, now time-corrected.

1637 }

1638 }

1639

1640 @unpublished{OlegNesterov2006aQRCU

1641 ,Author="Oleg Nesterov"

1642 ,Title="Re: [RFC, PATCH 1/2] qrcu: {"quick"} srcu implementation"

1643 ,month="November"

1644 ,year="2006"

1645 ,day=30

1646 ,note="Available:

1647 \url{https://lore.kernel.org/r/20061130015714.GC1350@oleg}

1648 [Viewed November 26, 2008]"

1649 ,annotation={

1650 Expanded/corrected version of QRCU.

1651 Used to be OlegNesterov2007aQRCU, now time-corrected.

1652 }

1653 }

1654

1655 @unpublished{EvgeniyPolyakov2006RCUslowdown

1656 ,Author="Evgeniy Polyakov"

1657 ,Title="Badness in postponing work"

1658 ,month="December"

1659 ,year="2006"

1660 ,day=05

1661 ,note="Available:

1662 \url{http://www.ioremap.net/node/41}

1663 [Viewed October 28, 2008]"

1664 ,annotation={

1665 Using RCU as a pure delay leads to a 2.5x slowdown in skbs in

1666 the Linux kernel.

1667 }

1668 }

1669

1670 @inproceedings{ChrisMatthews2006ClusteredObjectsRCU

1671 ,author = {Matthews, Chris and Coady, Yvonne and Appavoo, Jonathan}

1672 ,title = {Portability events: a programming model for scalable system infrastructures}

1673 ,booktitle = {PLOS '06: Proceedings of the 3rd workshop on Programming languages and operating systems}

1674 ,year = {2006}

1675 ,isbn = {1-59593-577-0}

1676 ,pages = {11}

1677 ,location = {San Jose, California}

1678 ,doi = {http://doi.acm.org/10.1145/1215995.1216006}

1679 ,publisher = {ACM}

1680 ,address = {New York, NY, USA}

1681 ,annotation={

1682 Uses K42's RCU-like functionality to manage clustered-object

1683 lifetimes.

1684 }

1685 }

1686

1687 @article{DilmaDaSilva2006K42

1688

,author = {Silva, Dilma Da and Krieger, Orran and Wisniewski, Robert W. and Waterland, Amos and Tam, David and Baumann, Andrew}

1689 ,title = {K42: an infrastructure for operating system research}

1690 ,journal = {SIGOPS Oper. Syst. Rev.}

1691 ,volume = {40}

1692 ,number = {2}

1693 ,year = {2006}

1694 ,issn = {0163-5980}

1695 ,pages = {34--42}

1696 ,doi = {http://doi.acm.org/10.1145/1131322.1131333}

1697 ,publisher = {ACM}

1698 ,address = {New York, NY, USA}

1699 ,annotation={

1700 Describes relationship of K42 generations to RCU.

1701 }

1702 }

1703

1704 # CoreyMinyard2007list_splice_rcu

1705 @unpublished{CoreyMinyard2007list:splice:rcu

1706 ,Author="Corey Minyard and Paul E. McKenney"

1707 ,Title="{[PATCH]} add an {RCU} version of list splicing"

1708 ,month="January"

1709 ,year="2007"

1710 ,day=3

1711 ,note="Available:

1712 \url{https://lore.kernel.org/r/20070103152738.GA16063@localdomain}

1713 [Viewed May 28, 2007]"

1714 ,annotation={

1715 Patch for list_splice_rcu().

1716 }

1717 }

1718

1719 @unpublished{PaulEMcKenney2007rcubarrier

1720 ,Author="Paul E. McKenney"

1721 ,Title="{RCU} and Unloadable Modules"

1722 ,month="January"

1723 ,day="14"

1724 ,year="2007"

1725 ,note="Available:

1726 \url{http://lwn.net/Articles/217484/}

1727 [Viewed November 22, 2007]"

1728 ,annotation={

1729 LWN article introducing the rcu_barrier() primitive.

1730 }

1731 }

1732

1733 @unpublished{PeterZijlstra2007SyncBarrier

1734 ,Author="Peter Zijlstra and Ingo Molnar"

1735 ,Title="{[PATCH 3/7]} barrier: a scalable synchonisation barrier"

1736 ,month="January"

1737 ,year="2007"

1738 ,day=28

1739 ,note="Available:

1740 \url{https://lore.kernel.org/r/20070128120509.719287000@programming.kicks-ass.net}

1741 [Viewed March 27, 2008]"

1742 ,annotation={

1743 RCU-like implementation for frequent updaters and rare readers(!).

1744 Subsumed into QRCU. Maybe...

1745 }

1746 }

1747

1748 @unpublished{PaulEMcKenney2007BoostRCU

1749 ,Author="Paul E. McKenney"

1750 ,Title="Priority-Boosting {RCU} Read-Side Critical Sections"

1751 ,month="February"

1752 ,day="5"

1753 ,year="2007"

1754 ,note="\url{http://lwn.net/Articles/220677/}"

1755 ,annotation={

1756 LWN article introducing RCU priority boosting.

1757 Revised:

1758 http://www.rdrop.com/users/paulmck/RCU/RCUbooststate.2007.04.16a.pdf

1759 [Viewed September 7, 2007]

1760 }

1761 }

1762

1763 @unpublished{PaulMcKenney2007QRCUpatch

1764 ,Author="Paul E. McKenney"

1765 ,Title="{[PATCH]} {QRCU} with lockless fastpath"

1766 ,month="February"

1767 ,year="2007"

1768 ,day=24

1769 ,note="Available:

1770 \url{https://lore.kernel.org/r/20070225062349.GA17468@linux.vnet.ibm.com}

1771 [Viewed March 27, 2008]"

1772 ,annotation={

1773 Patch for QRCU supplying lock-free fast path.

1774 }

1775 }

1776

1777 @article{JonathanAppavoo2007K42RCU

1778

,author = {Appavoo, Jonathan and Silva, Dilma Da and Krieger, Orran and Auslander, Marc and Ostrowski, Michal and Rosenburg, Bryan and Waterland, Amos and Wisniewski, Robert W. and Xenidis, Jimi and Stumm, Michael and Soares, Livio}

1779 ,title = {Experience distributing objects in an SMMP OS}

1780 ,journal = {ACM Trans. Comput. Syst.}

1781 ,volume = {25}

1782 ,number = {3}

1783 ,year = {2007}

1784 ,issn = {0734-2071}

1785 ,pages = {6/1--6/52}

1786 ,doi = {http://doi.acm.org/10.1145/1275517.1275518}

1787 ,publisher = {ACM}

1788 ,address = {New York, NY, USA}

1789 ,annotation={

1790 Role of RCU in K42.

1791 }

1792 }

1793

1794 @conference{RobertOlsson2007Trash

1795 ,Author="Robert Olsson and Stefan Nilsson"

1796 ,Title="{TRASH}: A dynamic {LC}-trie and hash data structure"

1797 ,booktitle="Workshop on High Performance Switching and Routing (HPSR'07)"

1798 ,month="May"

1799 ,year="2007"

1800 ,note="Available:

1801 \url{http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4281239}

1802 [Viewed October 1, 2010]"

1803 ,annotation={

1804 RCU-protected dynamic trie-hash combination.

1805 }

1806 }

1807

1808 @conference{PeterZijlstra2007ConcurrentPagecacheRCU

1809 ,Author="Peter Zijlstra"

1810 ,Title="Concurrent Pagecache"

1811 ,Booktitle="Linux Symposium"

1812 ,month="June"

1813 ,year="2007"

1814 ,address="Ottawa, Canada"

1815 ,note="Available:

1816 \url{http://ols.108.redhat.com/2007/Reprints/zijlstra-Reprint.pdf}

1817 [Viewed April 14, 2008]"

1818 ,annotation={

1819 Page-cache modifications permitting RCU readers and concurrent

1820 updates.

1821 }

1822 }

1823

1824 @unpublished{PaulEMcKenney2007whatisRCU

1825 ,Author="Paul E. McKenney"

1826 ,Title="What is {RCU}?"

1827 ,year="2007"

1828 ,month="07"

1829 ,note="Available:

1830 \url{http://www.rdrop.com/users/paulmck/RCU/whatisRCU.html}

1831 [Viewed July 6, 2007]"

1832 ,annotation={

1833 Describes RCU in Linux kernel.

1834 }

1835 }

1836

1837 @unpublished{PaulEMcKenney2007QRCUspin

1838 ,Author="Paul E. McKenney"

1839 ,Title="Using {Promela} and {Spin} to verify parallel algorithms"

1840 ,month="August"

1841 ,day="1"

1842 ,year="2007"

1843 ,note="Available:

1844 \url{http://lwn.net/Articles/243851/}

1845 [Viewed September 8, 2007]"

1846 ,annotation={

1847 LWN article describing Promela and spin, and also using Oleg

1848 Nesterov's QRCU as an example (with Paul McKenney's fastpath).

1849 Merged patch at: https://lore.kernel.org/r/20070225062349.GA17468@linux.vnet.ibm.com

1850 }

1851 }

1852

1853 @unpublished{PaulEMcKenney2007WG21DDOatomics

1854 ,Author="Paul E. McKenney and Hans-J. Boehm and Lawrence Crowl"

1855 ,Title="C++ Data-Dependency Ordering: Atomics and Memory Model"

1856 ,month="August"

1857 ,day="3"

1858 ,year="2007"

1859 ,note="Available:

1860 \url{http://open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2664.htm}

1861 [Viewed December 7, 2009]"

1862 ,annotation={

1863 RCU for C++, parts 1 and 2.

1864 }

1865 }

1866

1867 @unpublished{PaulEMcKenney2007WG21DDOannotation

1868 ,Author="Paul E. McKenney and Lawrence Crowl"

1869 ,Title="C++ Data-Dependency Ordering: Function Annotation"

1870 ,month="September"

1871 ,day="18"

1872 ,year="2008"

1873 ,note="Available:

1874 \url{http://open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2782.htm}

1875 [Viewed December 7, 2009]"

1876 ,annotation={

1877 RCU for C++, part 2, updated many times.

1878 }

1879 }

1880

1881 @unpublished{PaulEMcKenney2007PreemptibleRCUPatch

1882 ,Author="Paul E. McKenney"

1883 ,Title="[PATCH RFC 0/9] {RCU}: Preemptible {RCU}"

1884 ,month="September"

1885 ,day="10"

1886 ,year="2007"

1887 ,note="Available:

1888 \url{https://lore.kernel.org/r/20070910183004.GA3299@linux.vnet.ibm.com}

1889 [Viewed October 25, 2007]"

1890 ,annotation={

1891 Final patch for preemptible RCU to -rt. (Later patches were

1892 to mainline, eventually incorporated.)

1893 }

1894 }

1895

1896 @unpublished{PaulEMcKenney2007PreemptibleRCU

1897 ,Author="Paul E. McKenney"

1898 ,Title="The design of preemptible read-copy-update"

1899 ,month="October"

1900 ,day="8"

1901 ,year="2007"

1902 ,note="Available:

1903 \url{http://lwn.net/Articles/253651/}

1904 [Viewed October 25, 2007]"

1905 ,annotation={

1906 LWN article describing the design of preemptible RCU.

1907 }

1908 }

1909

1910 @article{ThomasEHart2007a

1911 ,Author="Thomas E. Hart and Paul E. McKenney and Angela Demke Brown and Jonathan Walpole"

1912 ,Title="Performance of memory reclamation for lockless synchronization"

1913 ,journal="J. Parallel Distrib. Comput."

1914 ,volume={67}

1915 ,number="12"

1916 ,year="2007"

1917 ,issn="0743-7315"

1918 ,pages="1270--1285"

1919 ,doi="http://dx.doi.org/10.1016/j.jpdc.2007.04.010"

1920 ,publisher="Academic Press, Inc."

1921 ,address="Orlando, FL, USA"

1922 ,annotation={

1923 Compares QSBR, HPBR, EBR, and lock-free reference counting.

1924 Journal version of ThomasEHart2006a.

1925 }

1926 }

1927

1928 # MathieuDesnoyers2007call_rcu_schedNeeded

1929 @unpublished{MathieuDesnoyers2007call:rcu:schedNeeded

1930 ,Author="Mathieu Desnoyers"

1931 ,Title="Re: [patch 1/2] {Linux} Kernel Markers - Support Multiple Probes"

1932 ,month="December"

1933 ,day="20"

1934 ,year="2007"

1935 ,note="Available:

1936 \url{https://lore.kernel.org/r/20071220142540.GB22523@Krystal}

1937 [Viewed March 27, 2008]"

1938 ,annotation={

1939 Request for call_rcu_sched() and rcu_barrier_sched().

1940 }

1941 }

1942

1943

1944 ########################################################################

1945 #

1946 # "What is RCU?" LWN series.

1947 #

1948 # http://lwn.net/Articles/262464/ (What is RCU, Fundamentally?)

1949 # http://lwn.net/Articles/263130/ (What is RCU's Usage?)

1950 # http://lwn.net/Articles/264090/ (What is RCU's API?)

1951

1952 @unpublished{PaulEMcKenney2007WhatIsRCUFundamentally

1953 ,Author="Paul E. McKenney and Jonathan Walpole"

1954 ,Title="What is {RCU}, Fundamentally?"

1955 ,month="December"

1956 ,day="17"

1957 ,year="2007"

1958 ,note="Available:

1959 \url{http://lwn.net/Articles/262464/}

1960 [Viewed December 27, 2007]"

1961 ,annotation={

1962 Lays out the three basic components of RCU: (1) publish-subscribe,

1963 (2) wait for pre-existing readers to complete, and (2) maintain

1964 multiple versions.

1965 }

1966 }

1967

1968 @unpublished{PaulEMcKenney2008WhatIsRCUUsage

1969 ,Author="Paul E. McKenney"

1970 ,Title="What is {RCU}? Part 2: Usage"

1971 ,month="January"

1972 ,day="4"

1973 ,year="2008"

1974 ,note="Available:

1975 \url{http://lwn.net/Articles/263130/}

1976 [Viewed January 4, 2008]"

1977 ,annotation={

1978 Lays out six uses of RCU:

1979 1. RCU is a Reader-Writer Lock Replacement

1980 2. RCU is a Restricted Reference-Counting Mechanism

1981 3. RCU is a Bulk Reference-Counting Mechanism

1982 4. RCU is a Poor Man's Garbage Collector

1983 5. RCU is a Way of Providing Existence Guarantees

1984 6. RCU is a Way of Waiting for Things to Finish

1985 }

1986 }

1987

1988 @unpublished{PaulEMcKenney2008WhatIsRCUAPI

1989 ,Author="Paul E. McKenney"

1990 ,Title="{RCU} part 3: the {RCU} {API}"

1991 ,month="January"

1992 ,day="17"

1993 ,year="2008"

1994 ,note="Available:

1995 \url{http://lwn.net/Articles/264090/}

1996 [Viewed January 10, 2008]"

1997 ,annotation={

1998 Gives an overview of the Linux-kernel RCU API and a brief annotated RCU

1999 bibliography.

2000 }

2001 }

2002

2003 #

2004 # "What is RCU?" LWN series.

2005 #

2006 ########################################################################

2007

2008

2009 @unpublished{SteveRostedt2008dyntickRCUpatch

2010 ,Author="Steven Rostedt and Paul E. McKenney"

2011 ,Title="{[PATCH]} add support for dynamic ticks and preempt rcu"

2012 ,month="January"

2013 ,day="29"

2014 ,year="2008"

2015 ,note="Available:

2016 \url{https://lore.kernel.org/r/Pine.LNX.4.58.0801291113350.20371@gandalf.stny.rr.com}

2017 [Viewed March 27, 2008]"

2018 ,annotation={

2019 Patch that prevents preemptible RCU from unnecessarily waking

2020 up dynticks-idle CPUs.

2021 }

2022 }

2023

2024 @unpublished{PaulEMcKenney2008LKMLDependencyOrdering

2025 ,Author="Paul E. McKenney"

2026 ,Title="Re: [PATCH 02/22 -v7] Add basic support for gcc profiler instrumentation"

2027 ,month="February"

2028 ,day="1"

2029 ,year="2008"

2030 ,note="Available:

2031 \url{https://lore.kernel.org/r/20080202214124.GA28612@linux.vnet.ibm.com}

2032 [Viewed October 18, 2008]"

2033 ,annotation={

2034 Explanation of compilers violating dependency ordering.

2035 }

2036 }

2037

2038 @Conference{PaulEMcKenney2008Beijing

2039 ,Author="Paul E. McKenney"

2040 ,Title="Introducing Technology Into {Linux} Or:

2041 Introducing your technology Into {Linux} will require introducing a

2042 lot of {Linux} into your technology!!!"

2043 ,Booktitle="2008 Linux Developer Symposium - China"

2044 ,Publisher="OSS China"

2045 ,Month="February"

2046 ,Year="2008"

2047 ,Address="Beijing, China"

2048 ,note="Available:

2049 \url{http://www.rdrop.com/users/paulmck/RCU/TechIntroLinux.2008.02.19a.pdf}

2050 [Viewed August 12, 2008]"

2051 }

2052

2053 @unpublished{PaulEMcKenney2008dynticksRCU

2054 ,Author="Paul E. McKenney and Steven Rostedt"

2055 ,Title="Integrating and Validating dynticks and Preemptable RCU"

2056 ,month="April"

2057 ,day="24"

2058 ,year="2008"

2059 ,note="Available:

2060 \url{http://lwn.net/Articles/279077/}

2061 [Viewed April 24, 2008]"

2062 ,annotation={

2063 Describes use of Promela and Spin to validate (and fix!) the

2064 dynticks/RCU interface.

2065 }

2066 }

2067

2068 @article{DinakarGuniguntala2008IBMSysJ

2069 ,author="D. Guniguntala and P. E. McKenney and J. Triplett and J. Walpole"

2070

,title="The read-copy-update mechanism for supporting real-time applications on shared-memory multiprocessor systems with {Linux}"

2071 ,Year="2008"

2072 ,Month="May"

2073 ,journal="IBM Systems Journal"

2074 ,volume="47"

2075 ,number="2"

2076 ,pages="221-236"

2077 ,annotation={

2078 RCU, realtime RCU, sleepable RCU, performance.

2079 http://www.research.ibm.com/journal/sj/472/guniguntala.pdf

2080 [Viewed April 24, 2008]

2081 }

2082 }

2083

2084 @unpublished{LaiJiangshan2008NewClassicAlgorithm

2085 ,Author="Lai Jiangshan"

2086 ,Title="[{RFC}][{PATCH}] rcu classic: new algorithm for callbacks-processing"

2087 ,month="June"

2088 ,day="3"

2089 ,year="2008"

2090 ,note="Available:

2091 \url{https://lore.kernel.org/r/4844BE83.5010401@cn.fujitsu.com}

2092 [Viewed December 10, 2008]"

2093 ,annotation={

2094 Updated RCU classic algorithm. Introduced multi-tailed list

2095 for RCU callbacks and also pulling common code into

2096 __call_rcu().

2097 }

2098 }

2099

2100 @article{PaulEMcKenney2008RCUOSR

2101 ,author="Paul E. McKenney and Jonathan Walpole"

2102 ,title="Introducing technology into the {Linux} kernel: a case study"

2103 ,Year="2008"

2104 ,journal="SIGOPS Oper. Syst. Rev."

2105 ,volume="42"

2106 ,number="5"

2107 ,pages="4--17"

2108 ,issn="0163-5980"

2109 ,doi={http://doi.acm.org/10.1145/1400097.1400099}

2110 ,publisher="ACM"

2111 ,address="New York, NY, USA"

2112 ,annotation={

2113 Linux changed RCU to a far greater degree than RCU has changed Linux.

2114 http://portal.acm.org/citation.cfm?doid=1400097.1400099

2115 }

2116 }

2117

2118 @unpublished{ManfredSpraul2008StateMachineRCU

2119 ,Author="Manfred Spraul"

2120 ,Title="[{RFC}, {PATCH}] state machine based rcu"

2121 ,month="August"

2122 ,day="21"

2123 ,year="2008"

2124 ,note="Available:

2125 \url{https://lore.kernel.org/r/48AD8969.7060900@colorfullife.com}

2126 [Viewed December 8, 2008]"

2127 ,annotation={

2128 State-based RCU. One key thing that this patch does is to

2129 separate the dynticks handling of NMIs and IRQs.

2130 }

2131 }

2132

2133 @unpublished{ManfredSpraul2008dyntickIRQNMI

2134 ,Author="Manfred Spraul"

2135 ,Title="Re: [{RFC}, {PATCH}] v4 scalable classic {RCU} implementation"

2136 ,month="September"

2137 ,day="6"

2138 ,year="2008"

2139 ,note="Available:

2140 \url{https://lore.kernel.org/r/48C2B1D2.5070801@colorfullife.com}

2141 [Viewed December 8, 2008]"

2142 ,annotation={

2143 Manfred notes a fix required to my attempt to separate irq

2144 and NMI processing for hierarchical RCU's dynticks interface.

2145 }

2146 }

2147

2148 # Was PaulEMcKenney2011cyclicRCU

2149 @techreport{PaulEMcKenney2008cyclicRCU

2150 ,author="Paul E. McKenney"

2151 ,title="Efficient Support of Consistent Cyclic Search With Read-Copy Update"

2152 ,institution="US Patent and Trademark Office"

2153 ,address="Washington, DC"

2154 ,year="2008"

2155 ,number="US Patent 7,426,511"

2156 ,month="September"

2157 ,pages="23"

2158 ,annotation={

2159 Maintains an additional level of indirection to allow

2160 readers to confine themselves to the desired snapshot of the

2161 data structure. Only permits one update at a time.

2162 }

2163 }

2164

2165 @unpublished{PaulEMcKenney2008HierarchicalRCU

2166 ,Author="Paul E. McKenney"

2167 ,Title="Hierarchical {RCU}"

2168 ,month="November"

2169 ,day="3"

2170 ,year="2008"

2171 ,note="\url{http://lwn.net/Articles/305782/}"

2172 ,annotation={

2173 RCU with combining-tree-based grace-period detection,

2174 permitting it to handle thousands of CPUs.

2175 [Viewed November 6, 2008]

2176 }

2177 }

2178

2179 @unpublished{PaulEMcKenney2009BloatwatchRCU

2180 ,Author="Paul E. McKenney"

2181 ,Title="Re: [PATCH fyi] RCU: the bloatwatch edition"

2182 ,month="January"

2183 ,day="14"

2184 ,year="2009"

2185 ,note="Available:

2186 \url{https://lore.kernel.org/r/20090114202044.GJ6734@linux.vnet.ibm.com}

2187 [Viewed January 15, 2009]"

2188 ,annotation={

2189 Small-footprint implementation of RCU for uniprocessor

2190 embedded applications -- and also for exposition purposes.

2191 }

2192 }

2193

2194 @conference{PaulEMcKenney2009MaliciousURCU

2195 ,Author="Paul E. McKenney"

2196 ,Title="Using a Malicious User-Level {RCU} to Torture {RCU}-Based Algorithms"

2197 ,Booktitle="linux.conf.au 2009"

2198 ,month="January"

2199 ,year="2009"

2200 ,address="Hobart, Australia"

2201 ,note="Available:

2202 \url{http://www.rdrop.com/users/paulmck/RCU/urcutorture.2009.01.22a.pdf}

2203 [Viewed February 2, 2009]"

2204 ,annotation={

2205 Realtime RCU and torture-testing RCU uses.

2206 }

2207 }

2208

2209 @unpublished{MathieuDesnoyers2009URCU

2210 ,Author="Mathieu Desnoyers"

2211 ,Title="[{RFC} git tree] Userspace {RCU} (urcu) for {Linux}"

2212 ,month="February"

2213 ,day="5"

2214 ,year="2009"

2215 ,note="\url{http://lttng.org/urcu}"

2216 ,annotation={

2217 Mathieu Desnoyers's user-space RCU implementation.

2218 git://lttng.org/userspace-rcu.git

2219 http://lttng.org/cgi-bin/gitweb.cgi?p=userspace-rcu.git

2220 http://lttng.org/urcu

2221 https://lore.kernel.org/r/20090206030543.GB8560@Krystal

2222 }

2223 }

2224

2225 @unpublished{PaulEMcKenney2009LWNBloatWatchRCU

2226 ,Author="Paul E. McKenney"

2227 ,Title="{RCU}: The {Bloatwatch} Edition"

2228 ,month="March"

2229 ,day="17"

2230 ,year="2009"

2231 ,note="Available:

2232 \url{http://lwn.net/Articles/323929/}

2233 [Viewed March 20, 2009]"

2234 ,annotation={

2235 Uniprocessor assumptions allow simplified RCU implementation.

2236 }

2237 }

2238

2239 @unpublished{EvgeniyPolyakov2009EllipticsNetwork

2240 ,Author="Evgeniy Polyakov"

2241 ,Title="The Elliptics Network"

2242 ,month="April"

2243 ,day="17"

2244 ,year="2009"

2245 ,note="Available:

2246 \url{http://www.ioremap.net/projects/elliptics}

2247 [Viewed April 30, 2009]"

2248 ,annotation={

2249 Distributed hash table with transactions, using elliptic

2250 hash functions to distribute data.

2251 }

2252 }

2253

2254 @unpublished{PaulEMcKenney2009expeditedRCU

2255 ,Author="Paul E. McKenney"

2256 ,Title="[{PATCH} -tip 0/3] expedited 'big hammer' {RCU} grace periods"

2257 ,month="June"

2258 ,day="25"

2259 ,year="2009"

2260 ,note="Available:

2261 \url{https://lore.kernel.org/r/20090625160706.GA9467@linux.vnet.ibm.com}

2262 [Viewed August 16, 2009]"

2263 ,annotation={

2264 First posting of expedited RCU to be accepted into -tip.

2265 }

2266 }

2267

2268 @unpublished{PaulEMcKenney2009fastRTRCU

2269 ,Author="Paul E. McKenney"

2270 ,Title="[{PATCH} {RFC} -tip 0/4] {RCU} cleanups and simplified preemptable {RCU}"

2271 ,month="July"

2272 ,day="23"

2273 ,year="2009"

2274 ,note="Available:

2275 \url{https://lore.kernel.org/r/20090724001429.GA17374@linux.vnet.ibm.com}

2276 [Viewed August 15, 2009]"

2277 ,annotation={

2278 First posting of simple and fast preemptible RCU.

2279 }

2280 }

2281

2282 @unpublished{JoshTriplett2009RPHash

2283 ,Author="Josh Triplett"

2284 ,Title="Scalable concurrent hash tables via relativistic programming"

2285 ,month="September"

2286 ,year="2009"

2287 ,note="Linux Plumbers Conference presentation"

2288 ,annotation={

2289 RP fun with hash tables.

2290 Superseded by JoshTriplett2010RPHash

2291 }

2292 }

2293

2294 @phdthesis{MathieuDesnoyersPhD

2295 , title = "Low-Impact Operating System Tracing"

2296 , author = "Mathieu Desnoyers"

2297 , school = "Ecole Polytechnique de Montr\'{e}al"

2298 , month = "December"

2299 , year = 2009

2300 ,note="Available:

2301 \url{http://www.lttng.org/pub/thesis/desnoyers-dissertation-2009-12.pdf}

2302 [Viewed December 9, 2009]"

2303 ,annotation={

2304 Chapter 6 (page 97) covers user-level RCU.

2305 }

2306 }

2307

2308 @unpublished{RelativisticProgrammingWiki

2309 ,Author="Josh Triplett and Paul E. McKenney and Jonathan Walpole"

2310 ,Title="Relativistic Programming"

2311 ,month="September"

2312 ,year="2009"

2313 ,note="Available:

2314 \url{http://wiki.cs.pdx.edu/rp/}

2315 [Viewed December 9, 2009]"

2316 ,annotation={

2317 Main Relativistic Programming Wiki.

2318 }

2319 }

2320

2321 @conference{PaulEMcKenney2009DeterministicRCU

2322 ,Author="Paul E. McKenney"

2323 ,Title="Deterministic Synchronization in Multicore Systems: the Role of {RCU}"

2324 ,Booktitle="Eleventh Real Time Linux Workshop"

2325 ,month="September"

2326 ,year="2009"

2327 ,address="Dresden, Germany"

2328 ,note="Available:

2329 \url{http://www.rdrop.com/users/paulmck/realtime/paper/DetSyncRCU.2009.08.18a.pdf}

2330 [Viewed January 14, 2009]"

2331 }

2332

2333 @unpublished{PaulEMcKenney2009HuntingHeisenbugs

2334 ,Author="Paul E. McKenney"

2335 ,Title="Hunting Heisenbugs"

2336 ,month="November"

2337 ,year="2009"

2338 ,day="1"

2339 ,note="Available:

2340 \url{http://paulmck.livejournal.com/14639.html}

2341 [Viewed June 4, 2010]"

2342 ,annotation={

2343 Day-one bug in Tree RCU that took forever to track down.

2344 }

2345 }

2346

2347 @unpublished{MathieuDesnoyers2009defer:rcu

2348 ,Author="Mathieu Desnoyers"

2349 ,Title="Kernel RCU: shrink the size of the struct rcu\_head"

2350 ,month="December"

2351 ,year="2009"

2352 ,note="Available:

2353 \url{https://lore.kernel.org/r/20091018232918.GA7385@Krystal}

2354 [Viewed December 29, 2009]"

2355 ,annotation={

2356 Mathieu proposed defer_rcu() with fixed-size per-thread pool

2357 of RCU callbacks.

2358 }

2359 }

2360

2361 @unpublished{MathieuDesnoyers2009VerifPrePub

2362 ,Author="Mathieu Desnoyers and Paul E. McKenney and Michel R. Dagenais"

2363 ,Title="Multi-Core Systems Modeling for Formal Verification of Parallel Algorithms"

2364 ,month="December"

2365 ,year="2009"

2366 ,note="Submitted to IEEE TPDS"

2367 ,annotation={

2368 OOMem model for Mathieu's user-level RCU mechanical proof of

2369 correctness.

2370 }

2371 }

2372

2373 @unpublished{MathieuDesnoyers2009URCUPrePub

2374 ,Author="Mathieu Desnoyers and Paul E. McKenney and Alan Stern and Michel R. Dagenais and Jonathan Walpole"

2375 ,Title="User-Level Implementations of Read-Copy Update"

2376 ,month="December"

2377 ,year="2010"

2378 ,url={\url{http://www.computer.org/csdl/trans/td/2012/02/ttd2012020375-abs.html}}

2379 ,annotation={

2380 RCU overview, desiderata, semi-formal semantics, user-level RCU

2381 usage scenarios, three classes of RCU implementation, wait-free

2382 RCU updates, RCU grace-period batching, update overhead,

2383 http://www.rdrop.com/users/paulmck/RCU/urcu-main-accepted.2011.08.30a.pdf

2384 http://www.rdrop.com/users/paulmck/RCU/urcu-supp-accepted.2011.08.30a.pdf

2385 Superseded by MathieuDesnoyers2012URCU.

2386 }

2387 }

2388

2389 @inproceedings{HariKannan2009DynamicAnalysisRCU

2390 ,author = {Kannan, Hari}

2391 ,title = {Ordering decoupled metadata accesses in multiprocessors}

2392 ,booktitle = {MICRO 42: Proceedings of the 42nd Annual IEEE/ACM International Symposium on Microarchitecture}

2393 ,year = {2009}

2394 ,isbn = {978-1-60558-798-1}

2395 ,pages = {381--390}

2396 ,location = {New York, New York}

2397 ,doi = {http://doi.acm.org/10.1145/1669112.1669161}

2398 ,publisher = {ACM}

2399 ,address = {New York, NY, USA}

2400 ,annotation={

2401 Uses RCU to protect metadata used in dynamic analysis.

2402 }

2403 }

2404

2405 @conference{PaulEMcKenney2010SimpleOptRCU

2406 ,Author="Paul E. McKenney"

2407 ,Title="Simplicity Through Optimization"

2408 ,Booktitle="linux.conf.au 2010"

2409 ,month="January"

2410 ,year="2010"

2411 ,address="Wellington, New Zealand"

2412 ,note="Available:

2413 \url{http://www.rdrop.com/users/paulmck/RCU/SimplicityThruOptimization.2010.01.21f.pdf}

2414 [Viewed October 10, 2010]"

2415 ,annotation={

2416 TREE_PREEMPT_RCU optimizations greatly simplified the old

2417 PREEMPT_RCU implementation.

2418 }

2419 }

2420

2421 @unpublished{PaulEMcKenney2010LockdepRCU

2422 ,Author="Paul E. McKenney"

2423 ,Title="Lockdep-{RCU}"

2424 ,month="February"

2425 ,year="2010"

2426 ,day="1"

2427 ,note="\url{https://lwn.net/Articles/371986/}"

2428 ,annotation={

2429 CONFIG_PROVE_RCU, or at least an early version.

2430 [Viewed June 4, 2010]

2431 }

2432 }

2433

2434 @unpublished{AviKivity2010KVM2RCU

2435 ,Author="Avi Kivity"

2436 ,Title="[{PATCH} 37/40] {KVM}: Bump maximum vcpu count to 64"

2437 ,month="February"

2438 ,year="2010"

2439 ,note="Available:

2440 \url{http://www.mail-archive.com/kvm@vger.kernel.org/msg28640.html}

2441 [Viewed March 20, 2010]"

2442 ,annotation={

2443 Use of RCU permits KVM to increase the size of guest OSes from

2444 16 CPUs to 64 CPUs.

2445 }

2446 }

2447

2448 @unpublished{HerbertXu2010RCUResizeHash

2449 ,Author="Herbert Xu"

2450 ,Title="bridge: Add core IGMP snooping support"

2451 ,month="February"

2452 ,year="2010"

2453 ,note="Available:

2454 \url{http://thread.gmane.org/gmane.linux.network/153338}

2455 [Viewed June 9, 2014]"

2456 ,annotation={

2457 Use a pair of list_head structures to support RCU-protected

2458 resizable hash tables.

2459 }

2460 }

2461

2462 @mastersthesis{AbhinavDuggal2010Masters

2463 ,author="Abhinav Duggal"

2464 ,title="Stopping Data Races Using Redflag"

2465 ,school="Stony Brook University"

2466 ,year="2010"

2467 ,annotation={

2468 Data-race detector incorporating RCU.

2469 http://www.filesystems.org/docs/abhinav-thesis/abhinav_thesis.pdf

2470 }

2471 }

2472

2473 @article{JoshTriplett2010RPHash

2474 ,author="Josh Triplett and Paul E. McKenney and Jonathan Walpole"

2475 ,title="Scalable Concurrent Hash Tables via Relativistic Programming"

2476 ,journal="ACM Operating Systems Review"

2477 ,year=2010

2478 ,volume=44

2479 ,number=3

2480 ,month="July"

2481 ,annotation={

2482 RP fun with hash tables.

2483 http://portal.acm.org/citation.cfm?id=1842733.1842750

2484 }

2485 }

2486

2487 @unpublished{PaulEMcKenney2010RCUAPI

2488 ,Author="Paul E. McKenney"

2489 ,Title="The {RCU} {API}, 2010 Edition"

2490 ,month="December"

2491 ,day="8"

2492 ,year="2010"

2493 ,note="\url{http://lwn.net/Articles/418853/}"

2494 ,annotation={

2495 Includes updated software-engineering features.

2496 [Viewed December 8, 2010]

2497 }

2498 }

2499

2500 @mastersthesis{AndrejPodzimek2010masters

2501 ,author="Andrej Podzimek"

2502 ,title="Read-Copy-Update for OpenSolaris"

2503 ,school="Charles University in Prague"

2504 ,year="2010"

2505 ,note="Available:

2506 \url{https://andrej.podzimek.org/thesis.pdf}

2507 [Viewed January 31, 2011]"

2508 ,annotation={

2509 Reviews RCU implementations and creates a few for OpenSolaris.

2510 Drives quiescent-state detection from RCU read-side primitives,

2511 in a manner roughly similar to that of Jim Houston.

2512 }

2513 }

2514

2515 @unpublished{LinusTorvalds2011Linux2:6:38:rc1:NPigginVFS

2516 ,Author="Linus Torvalds"

2517 ,Title="Linux 2.6.38-rc1"

2518 ,month="January"

2519 ,year="2011"

2520 ,note="Available:

2521 \url{https://lore.kernel.org/r/AANLkTimajU0x1v6y3rH2+jr-bZ=tNLs1S_agXdGGAa3S@mail.gmail.com}

2522 [Viewed March 4, 2011]"

2523 ,annotation={

2524 "The RCU-based name lookup is at the other end of the spectrum - the

2525 absolute anti-gimmick. It's some seriously good stuff, and gets rid of

2526 the last main global lock that really tends to hurt some kernel loads.

2527 The dentry lock is no longer a big serializing issue. What's really

2528 nice about it is that it actually improves performance a lot even for

2529 single-threaded loads (on an SMP kernel), because it gets rid of some

2530 of the most expensive parts of path component lookup, which was the

2531 d_lock on every component lookup. So I'm seeing improvements of 30-50%

2532 on some seriously pathname-lookup intensive loads."

2533 }

2534 }

2535

2536 @techreport{JoshTriplett2011RPScalableCorrectOrdering

2537 ,author = {Josh Triplett and Philip W. Howard and Paul E. McKenney and Jonathan Walpole}

2538 ,title = {Scalable Correct Memory Ordering via Relativistic Programming}

2539 ,year = {2011}

2540 ,number = {11-03}

2541 ,institution = {Portland State University}

2542 ,note = {\url{http://www.cs.pdx.edu/pdfs/tr1103.pdf}}

2543 }

2544

2545 @inproceedings{PhilHoward2011RCUTMRBTree

2546 ,author = {Philip W. Howard and Jonathan Walpole}

2547 ,title = {A Relativistic Enhancement to Software Transactional Memory}

2548 ,booktitle = {Proceedings of the 3rd USENIX conference on Hot topics in parallelism}

2549 ,series = {HotPar'11}

2550 ,year = {2011}

2551 ,location = {Berkeley, CA}

2552 ,pages = {1--6}

2553 ,numpages = {6}

2554 ,url = {http://www.usenix.org/event/hotpar11/tech/final_files/Howard.pdf}

2555 ,publisher = {USENIX Association}

2556 ,address = {Berkeley, CA, USA}

2557 }

2558

2559 @techreport{PaulEMcKenney2011cyclicparallelRCU

2560 ,author="Paul E. McKenney and Jonathan Walpole"

2561 ,title="Efficient Support of Consistent Cyclic Search With Read-Copy Update and Parallel Updates"

2562 ,institution="US Patent and Trademark Office"

2563 ,address="Washington, DC"

2564 ,year="2011"

2565 ,number="US Patent 7,953,778"

2566 ,month="May"

2567 ,pages="34"

2568 ,annotation={

2569 Maintains an array of generation numbers to track in-flight

2570 updates and keeps an additional level of indirection to allow

2571 readers to confine themselves to the desired snapshot of the

2572 data structure.

2573 }

2574 }

2575

2576 @inproceedings{Triplett:2011:RPHash

2577 ,author = {Triplett, Josh and McKenney, Paul E. and Walpole, Jonathan}

2578 ,title = {Resizable, Scalable, Concurrent Hash Tables via Relativistic Programming}

2579 ,booktitle = {Proceedings of the 2011 USENIX Annual Technical Conference}

2580 ,month = {June}

2581 ,year = {2011}

2582 ,pages = {145--158}

2583 ,numpages = {14}

2584 ,url={http://www.usenix.org/event/atc11/tech/final_files/Triplett.pdf}

2585 ,publisher = {The USENIX Association}

2586 ,address = {Portland, OR USA}

2587 }

2588

2589 @unpublished{PaulEMcKenney2011RCU3.0trainwreck

2590 ,Author="Paul E. McKenney"

2591 ,Title="3.0 and {RCU:} what went wrong"

2592 ,month="July"

2593 ,day="27"

2594 ,year="2011"

2595 ,note="\url{http://lwn.net/Articles/453002/}"

2596 ,annotation={

2597 Analysis of the RCU trainwreck in Linux kernel 3.0.

2598 [Viewed July 27, 2011]

2599 }

2600 }

2601

2602 @unpublished{NeilBrown2011MeetTheLockers

2603 ,Author="Neil Brown"

2604 ,Title="Meet the {Lockers}"

2605 ,month="August"

2606 ,day="3"

2607 ,year="2011"

2608 ,note="Available:

2609 \url{http://lwn.net/Articles/453685/}

2610 [Viewed September 2, 2011]"

2611 ,annotation={

2612 The Locker family as an analogy for locking, reference counting,

2613 RCU, and seqlock.

2614 }

2615 }

2616

2617 @inproceedings{Seyster:2011:RFA:2075416.2075425

2618

,author = {Seyster, Justin and Radhakrishnan, Prabakar and Katoch, Samriti and Duggal, Abhinav and Stoller, Scott D. and Zadok, Erez}

2619 ,title = {Redflag: a framework for analysis of Kernel-level concurrency}

2620

,booktitle = {Proceedings of the 11th international conference on Algorithms and architectures for parallel processing - Volume Part I}

2621 ,series = {ICA3PP'11}

2622 ,year = {2011}

2623 ,isbn = {978-3-642-24649-4}

2624 ,location = {Melbourne, Australia}

2625 ,pages = {66--79}

2626 ,numpages = {14}

2627 ,url = {http://dl.acm.org/citation.cfm?id=2075416.2075425}

2628 ,acmid = {2075425}

2629 ,publisher = {Springer-Verlag}

2630 ,address = {Berlin, Heidelberg}

2631 }

2632

2633 @phdthesis{JoshTriplettPhD

2634 ,author="Josh Triplett"

2635 ,title="Relativistic Causal Ordering: A Memory Model for Scalable Concurrent Data Structures"

2636 ,school="Portland State University"

2637 ,year="2012"

2638 ,annotation={

2639 RCU-protected hash tables, barriers vs. read-side traversal order.

2640 .

2641 If the updater is making changes in the opposite direction from

2642 the read-side traversal order, the updater need only execute a

2643 memory-barrier instruction, but if in the same direction, the

2644 updater needs to wait for a grace period between the individual

2645 updates.

2646 }

2647 }

2648

2649 @article{MathieuDesnoyers2012URCU

2650 ,Author="Mathieu Desnoyers and Paul E. McKenney and Alan Stern and Michel R. Dagenais and Jonathan Walpole"

2651 ,Title="User-Level Implementations of Read-Copy Update"

2652 ,journal="IEEE Transactions on Parallel and Distributed Systems"

2653 ,volume={23}

2654 ,year="2012"

2655 ,issn="1045-9219"

2656 ,pages="375-382"

2657 ,doi="http://doi.ieeecomputersociety.org/10.1109/TPDS.2011.159"

2658 ,publisher="IEEE Computer Society"

2659 ,address="Los Alamitos, CA, USA"

2660 ,annotation={

2661 RCU overview, desiderata, semi-formal semantics, user-level RCU

2662 usage scenarios, three classes of RCU implementation, wait-free

2663 RCU updates, RCU grace-period batching, update overhead,

2664 http://www.rdrop.com/users/paulmck/RCU/urcu-main-accepted.2011.08.30a.pdf

2665 http://www.rdrop.com/users/paulmck/RCU/urcu-supp-accepted.2011.08.30a.pdf

2666 http://www.computer.org/cms/Computer.org/dl/trans/td/2012/02/extras/ttd2012020375s.pdf

2667 }

2668 }

2669

2670 @inproceedings{AustinClements2012RCULinux:mmapsem

2671 ,author = {Austin Clements and Frans Kaashoek and Nickolai Zeldovich}

2672 ,title = {Scalable Address Spaces Using {RCU} Balanced Trees}

2673 ,booktitle = {Architectural Support for Programming Languages and Operating Systems (ASPLOS 2012)}

2674 ,month = {March}

2675 ,year = {2012}

2676 ,pages = {199--210}

2677 ,numpages = {12}

2678 ,publisher = {ACM}

2679 ,address = {London, UK}

2680 ,url="http://people.csail.mit.edu/nickolai/papers/clements-bonsai.pdf"

2681 }

2682

2683 @unpublished{PaulEMcKenney2012ELCbattery

2684 ,Author="Paul E. McKenney"

2685 ,Title="Making {RCU} Safe For Battery-Powered Devices"

2686 ,month="February"

2687 ,day="15"

2688 ,year="2012"

2689 ,note="Available:

2690 \url{http://www.rdrop.com/users/paulmck/RCU/RCUdynticks.2012.02.15b.pdf}

2691 [Viewed March 1, 2012]"

2692 ,annotation={

2693 RCU_FAST_NO_HZ, round 2.

2694 }

2695 }

2696

2697 @article{GuillermoVigueras2012RCUCrowd

2698 ,author = {Vigueras, Guillermo and Ordu\~{n}a, Juan M. and Lozano, Miguel}

2699 ,day = {25}

2700 ,doi = {10.1007/s11227-012-0766-x}

2701 ,issn = {0920-8542}

2702 ,journal = {The Journal of Supercomputing}

2703 ,keywords = {linux, simulation}

2704 ,month = apr

2705 ,posted-at = {2012-05-03 09:12:04}

2706 ,priority = {2}

2707 ,title = {{A Read-Copy Update based parallel server for distributed crowd simulations}}

2708 ,url = {http://dx.doi.org/10.1007/s11227-012-0766-x}

2709 ,year = {2012}

2710 }

2711

2712

2713 @unpublished{JonCorbet2012ACCESS:ONCE

2714 ,Author="Jon Corbet"

2715 ,Title="{ACCESS\_ONCE()}"

2716 ,month="August"

2717 ,day="1"

2718 ,year="2012"

2719 ,note="\url{http://lwn.net/Articles/508991/}"

2720 ,annotation={

2721 A couple of simple specific compiler optimizations that motivate

2722 ACCESS_ONCE().

2723 }

2724 }

2725

2726 @unpublished{AlexeyGotsman2012VerifyGraceExtended

2727 ,Author="Alexey Gotsman and Noam Rinetzky and Hongseok Yang"

2728 ,Title="Verifying Highly Concurrent Algorithms with Grace (extended version)"

2729 ,month="July"

2730 ,day="10"

2731 ,year="2012"

2732 ,note="\url{http://software.imdea.org/~gotsman/papers/recycling-esop13-ext.pdf}"

2733 ,annotation={

2734 Separation-logic formulation of RCU uses.

2735 }

2736 }

2737

2738 @unpublished{PaulMcKenney2012RCUUsage

2739 ,Author="Paul E. McKenney and Silas Boyd-Wickizer and Jonathan Walpole"

2740 ,Title="{RCU} Usage In the Linux Kernel: One Decade Later"

2741 ,month="September"

2742 ,day="17"

2743 ,year="2012"

2744 ,url=http://rdrop.com/users/paulmck/techreports/survey.2012.09.17a.pdf

2745 ,note="Technical report paulmck.2012.09.17"

2746 ,annotation={

2747 Overview of the first variant of no-CBs CPUs for RCU.

2748 }

2749 }

2750

2751 @unpublished{JonCorbet2012NOCB

2752 ,Author="Jon Corbet"

2753 ,Title="Relocating RCU callbacks"

2754 ,month="October"

2755 ,day="31"

2756 ,year="2012"

2757 ,note="\url{http://lwn.net/Articles/522262/}"

2758 ,annotation={

2759 Overview of the first variant of no-CBs CPUs for RCU.

2760 }

2761 }

2762

2763 @phdthesis{JustinSeyster2012PhD

2764 ,author="Justin Seyster"

2765 ,title="Runtime Verification of Kernel-Level Concurrency Using Compiler-Based Instrumentation"

2766 ,school="Stony Brook University"

2767 ,year="2012"

2768 ,annotation={

2769 Looking for data races, including those involving RCU.

2770 Proposal:

2771 http://www.fsl.cs.sunysb.edu/docs/jseyster-proposal/redflag.pdf

2772 Dissertation:

2773 http://www.fsl.cs.sunysb.edu/docs/jseyster-dissertation/redflag.pdf

2774 }

2775 }

2776

2777 @unpublished{PaulEMcKenney2013RCUUsage

2778 ,Author="Paul E. McKenney and Silas Boyd-Wickizer and Jonathan Walpole"

2779 ,Title="{RCU} Usage in the {Linux} Kernel: One Decade Later"

2780 ,month="February"

2781 ,day="24"

2782 ,year="2013"

2783 ,note="\url{http://rdrop.com/users/paulmck/techreports/RCUUsage.2013.02.24a.pdf}"

2784 ,annotation={

2785 Usage of RCU within the Linux kernel.

2786 }

2787 }

2788

2789 @inproceedings{AlexeyGotsman2013ESOPRCU

2790 ,author = {Alexey Gotsman and Noam Rinetzky and Hongseok Yang}

2791 ,title = {Verifying concurrent memory reclamation algorithms with grace}

2792 ,booktitle = {ESOP'13: European Symposium on Programming}

2793 ,year = {2013}

2794 ,pages = {249--269}

2795 ,publisher = {Springer}

2796 ,address = {Rome, Italy}

2797 ,annotation={

2798 http://software.imdea.org/~gotsman/papers/recycling-esop13.pdf

2799 }

2800 }

2801

2802 @unpublished{PaulEMcKenney2013NoTinyPreempt

2803 ,Author="Paul E. McKenney"

2804 ,Title="Simplifying RCU"

2805 ,month="March"

2806 ,day="6"

2807 ,year="2013"

2808 ,note="\url{http://lwn.net/Articles/541037/}"

2809 ,annotation={

2810 Getting rid of TINY_PREEMPT_RCU.

2811 }

2812 }

2813

3. 한국어 전문 번역

영어 원문의 문단 순서와 의미를 유지한 전체 번역입니다. 코드, 함수명, symbol과 URL은 원문 표기를 유지합니다.

RCU 아이디어의 역사와 발전

1-218

이 문서는 RCU와 관련된 출판물의 흐름을 설명하고 뒤에 해당 BibTeX 항목을 제공한다. 일부 자료는 Paul E. McKenney의 RCU 자료실에서 찾을 수 있고, 나머지는 논문 제목과 인용 키를 이용해 검색할 수 있다.

RCU와 닮은 최초의 아이디어는 1980년 Kung과 Lehman이 병렬 이진 검색 트리 노드의 파괴를 garbage collector에 맡겨 구현을 단순화한 것이다. 1982년 Manber와 Ladner는 삭제 시점에 실행 중이던 모든 thread가 종료될 때까지 파괴를 미뤘다. 짧은 수명의 thread가 많은 K42 같은 환경에는 맞지만 장수 task가 많은 Linux에는 충분하지 않다.

1986년 Hennessy, Osisek, Seigh의 passive serialization은 VM/XA hypervisor의 quiescent state를 이용해 자료 구조를 더 이상 참조하지 않는 시점을 찾았다. 현대 하드웨어에 최적화되지는 않았지만 실제 제품에 쓰인 최초의 deferred destruction으로 보이며 관련 특허도 만료되었다. 문서는 RCU 구현의 라이선스가 GPL 또는 LGPL이어야 한다는 주의도 덧붙인다.

1987년 lazy TLB flush는 훗날 DYNIX/ptx RCU의 update-side batching에 영감을 주었고, 1988년 Argus는 일부 상황에서 오래된 값을 허용할 수 있다는 이론적 근거를 제공했다. 1990년 Pugh는 읽는 thread를 명시적으로 추적해 종료하지 않는 thread가 있어도 지연 해제를 가능하게 했지만 read-side 비용이 컸다. 같은 시기 chaotic relaxation은 barrier를 줄이는 대신 이전 반복의 값을 허용하는 방식으로 stale data의 유용성을 보였으나 kernel 자료 구조에는 적용 범위가 좁다.

1992년 Massalin은 가능한 작업을 미뤄 동기화를 단순화하라고 권했고 RCU는 이 원칙을 적극 사용한다. 1993년 Jacobson과 1995년 Aju John의 고정 시간 지연 해제는 reader 최대 시간이 엄격히 제한된 hard real-time 환경에서는 가능하지만, 선점·인터럽트·예상보다 큰 부하로 제한을 넘으면 진단하기 어려운 메모리 손상을 만든다.

1995~1998년 DYNIX/ptx의 RCU가 현대 CPU에 맞춰 발표되고 kernel 여러 곳에 적용되었다. 1999년 Tornado와 K42의 generations는 existence lock을 대체해 잠금 계층과 deadlock을 줄였다. 2001년 Linux RCU 발표, 2002년 dcache 적용과 hazard pointer 연구, 2003년 hot-swappable OS 기능과 System V IPC 적용을 거쳐 Linux 안에서 사용 범위가 넓어졌다.

Hazard pointer는 각 자료 구조를 가리키는 불멸 변수의 수로 참조를 표현하는 안팎이 뒤집힌 참조 카운트로 볼 수 있다. 접근과 삭제 경합을 피하지만 독자에게 memory barrier 비용이 남는다. RCU는 일정 시간 동안 한 CPU나 thread가 만든 모든 참조를 묶어 세는 bulk reference count로 볼 수 있으며, classic RCU에서는 이전 GP의 참조 가능성을 per-CPU bitmask가 대표한다.

2004~2008년에는 dcache 성능, soft real-time과 preemptible RCU, sleepable RCU, QRCU 검증, LWN의 What is RCU 시리즈, hierarchical RCU가 발전했다. 2009년에는 userspace RCU, TINY_RCU, expedited RCU, resizable hash가 등장했다. 2010~2012년에는 TREE_RCU 기반 단순 preemptible 구현, lockdep-RCU, 원자적 node 이동 hash, lockless dentry, 형식 검증과 user-level RCU 논문이 이어졌다.

Josh Triplett의 2012년 연구는 reader 순회 방향과 updater 변경 방향의 관계를 정리했다. 서로 반대 방향이면 updater의 memory barrier로 충분할 수 있지만 같은 방향이면 개별 갱신 사이에 grace period가 필요하다. 이 시기 RCU는 crowd simulation과 separation logic 기반 형식 검증에도 적용되었다.

RCU 발전 흐름

1980 garbage collection1986 passive serialization1995 DYNIX/ptx RCU2001 Linux RCU2005 preemptible/RT2009 userspace·TINY·expedited2012 ordering·형식 검증

파괴 지연이라는 아이디어가 실행 이력, quiescent state, memory ordering, 다양한 운영 환경으로 확장되었다.

회수 기법 비교

기법독자 측 비용회수 조건주요 한계

GC낮음collector가 도달성 판정제품 GC 비용

thread 종료 대기낮음당시 thread 모두 종료장수 task

고정 시간 지연낮음시간 상한상한 위반 시 손상

hazard pointer게시와 barrierhazard 없음read-side 비용

RCU매우 낮음grace periodupdate-side 지연

각 기법은 독자 추적 비용과 회수 시점의 확실성 사이에서 다른 선택을 한다.

Read the Fscking Papers!


This document describes RCU-related publications, and is followed by
the corresponding bibtex entries.  A number of the publications may
be found at http://www.rdrop.com/users/paulmck/RCU/.  For others, browsers
and search engines will usually find what you are looking for.

The first thing resembling RCU was published in 1980, when Kung and Lehman
[Kung80] recommended use of a garbage collector to defer destruction
of nodes in a parallel binary search tree in order to simplify its
implementation.  This works well in environments that have garbage
collectors, but most production garbage collectors incur significant
overhead.

In 1982, Manber and Ladner [Manber82,Manber84] recommended deferring
destruction until all threads running at that time have terminated, again
for a parallel binary search tree.  This approach works well in systems
with short-lived threads, such as the K42 research operating system.
However, Linux has long-lived tasks, so more is needed.

In 1986, Hennessy, Osisek, and Seigh [Hennessy89] introduced passive
serialization, which is an RCU-like mechanism that relies on the presence
of "quiescent states" in the VM/XA hypervisor that are guaranteed not
to be referencing the data structure.  However, this mechanism was not
optimized for modern computer systems, which is not surprising given
that these overheads were not so expensive in the mid-80s.  Nonetheless,
passive serialization appears to be the first deferred-destruction
mechanism to be used in production.  Furthermore, the relevant patent
has lapsed, so this approach may be used in non-GPL software, if desired.
(In contrast, implementation of RCU is permitted only in software licensed
under either GPL or LGPL.  Sorry!!!)

In 1987, Rashid et al. described lazy TLB-flush [RichardRashid87a].
At first glance, this has nothing to do with RCU, but nevertheless
this paper helped inspire the update-side batching used in the later
RCU implementation in DYNIX/ptx.  In 1988, Barbara Liskov published
a description of Argus that noted that use of out-of-date values can
be tolerated in some situations.  Thus, this paper provides some early
theoretical justification for use of stale data.

In 1990, Pugh [Pugh90] noted that explicitly tracking which threads
were reading a given data structure permitted deferred free to operate
in the presence of non-terminating threads.  However, this explicit
tracking imposes significant read-side overhead, which is undesirable
in read-mostly situations.  This algorithm does take pains to avoid
write-side contention and parallelize the other write-side overheads by
providing a fine-grained locking design, however, it would be interesting
to see how much of the performance advantage reported in 1990 remains
today.

At about this same time, Andrews [Andrews91textbook] described ``chaotic
relaxation'', where the normal barriers between successive iterations
of convergent numerical algorithms are relaxed, so that iteration $n$
might use data from iteration $n-1$ or even $n-2$.  This introduces
error, which typically slows convergence and thus increases the number of
iterations required.  However, this increase is sometimes more than made
up for by a reduction in the number of expensive barrier operations,
which are otherwise required to synchronize the threads at the end
of each iteration.  Unfortunately, chaotic relaxation requires highly
structured data, such as the matrices used in scientific programs, and
is thus inapplicable to most data structures in operating-system kernels.

In 1992, Henry (now Alexia) Massalin completed a dissertation advising
parallel programmers to defer processing when feasible to simplify
synchronization [HMassalinPhD].  RCU makes extremely heavy use of
this advice.

In 1993, Jacobson [Jacobson93] verbally described what is perhaps the
simplest deferred-free technique: simply waiting a fixed amount of time
before freeing blocks awaiting deferred free.  Jacobson did not describe
any write-side changes he might have made in this work using SGI's Irix
kernel.  Aju John published a similar technique in 1995 [AjuJohn95].
This works well if there is a well-defined upper bound on the length of
time that reading threads can hold references, as there might well be in
hard real-time systems.  However, if this time is exceeded, perhaps due
to preemption, excessive interrupts, or larger-than-anticipated load,
memory corruption can ensue, with no reasonable means of diagnosis.
Jacobson's technique is therefore inappropriate for use in production
operating-system kernels, except when such kernels can provide hard
real-time response guarantees for all operations.

Also in 1995, Pu et al. [Pu95a] applied a technique similar to that of Pugh's
read-side-tracking to permit replugging of algorithms within a commercial
Unix operating system.  However, this replugging permitted only a single
reader at a time.  The following year, this same group of researchers
extended their technique to allow for multiple readers [Cowan96a].
Their approach requires memory barriers (and thus pipeline stalls),
but reduces memory latency, contention, and locking overheads.

1995 also saw the first publication of DYNIX/ptx's RCU mechanism
[Slingwine95], which was optimized for modern CPU architectures,
and was successfully applied to a number of situations within the
DYNIX/ptx kernel.  The corresponding conference paper appeared in 1998
[McKenney98].

In 1999, the Tornado and K42 groups described their "generations"
mechanism, which is quite similar to RCU [Gamsa99].  These operating
systems made pervasive use of RCU in place of "existence locks", which
greatly simplifies locking hierarchies and helps avoid deadlocks.

The year 2000 saw an email exchange that would likely have
led to yet another independent invention of something like RCU
[RustyRussell2000a,RustyRussell2000b].  Instead, 2001 saw the first
RCU presentation involving Linux [McKenney01a] at OLS.  The resulting
abundance of RCU patches was presented the following year [McKenney02a],
and use of RCU in dcache was first described that same year [Linder02a].

Also in 2002, Michael [Michael02b,Michael02a] presented "hazard-pointer"
techniques that defer the destruction of data structures to simplify
non-blocking synchronization (wait-free synchronization, lock-free
synchronization, and obstruction-free synchronization are all examples of
non-blocking synchronization).  The corresponding journal article appeared
in 2004 [MagedMichael04a].  This technique eliminates locking, reduces
contention, reduces memory latency for readers, and parallelizes pipeline
stalls and memory latency for writers.  However, these techniques still
impose significant read-side overhead in the form of memory barriers.
Researchers at Sun worked along similar lines in the same timeframe
[HerlihyLM02].  These techniques can be thought of as inside-out reference
counts, where the count is represented by the number of hazard pointers
referencing a given data structure rather than the more conventional
counter field within the data structure itself.  The key advantage
of inside-out reference counts is that they can be stored in immortal
variables, thus allowing races between access and deletion to be avoided.

By the same token, RCU can be thought of as a "bulk reference count",
where some form of reference counter covers all reference by a given CPU
or thread during a set timeframe.  This timeframe is related to, but
not necessarily exactly the same as, an RCU grace period.  In classic
RCU, the reference counter is the per-CPU bit in the "bitmask" field,
and each such bit covers all references that might have been made by
the corresponding CPU during the prior grace period.  Of course, RCU
can be thought of in other terms as well.

In 2003, the K42 group described how RCU could be used to create
hot-pluggable implementations of operating-system functions [Appavoo03a].
Later that year saw a paper describing an RCU implementation
of System V IPC [Arcangeli03] (following up on a suggestion by
Hugh Dickins [Dickins02a] and an implementation by Mingming Cao
[MingmingCao2002IPCRCU]), and an introduction to RCU in Linux Journal
[McKenney03a].

2004 has seen a Linux-Journal article on use of RCU in dcache
[McKenney04a], a performance comparison of locking to RCU on several
different CPUs [McKenney04b], a dissertation describing use of RCU in a
number of operating-system kernels [PaulEdwardMcKenneyPhD], a paper
describing how to make RCU safe for soft-realtime applications [Sarma04c],
and a paper describing SELinux performance with RCU [JamesMorris04b].

2005 brought further adaptation of RCU to realtime use, permitting
preemption of RCU realtime critical sections [PaulMcKenney05a,
PaulMcKenney05b].

2006 saw the first best-paper award for an RCU paper [ThomasEHart2006a],
as well as further work on efficient implementations of preemptible
RCU [PaulEMcKenney2006b], but priority-boosting of RCU read-side critical
sections proved elusive.  An RCU implementation permitting general
blocking in read-side critical sections appeared [PaulEMcKenney2006c],
Robert Olsson described an RCU-protected trie-hash combination
[RobertOlsson2006a].

2007 saw the journal version of the award-winning RCU paper from 2006
[ThomasEHart2007a], as well as a paper demonstrating use of Promela
and Spin to mechanically verify an optimization to Oleg Nesterov's
QRCU [PaulEMcKenney2007QRCUspin], a design document describing
preemptible RCU [PaulEMcKenney2007PreemptibleRCU], and the three-part
LWN "What is RCU?" series [PaulEMcKenney2007WhatIsRCUFundamentally,
PaulEMcKenney2008WhatIsRCUUsage, and PaulEMcKenney2008WhatIsRCUAPI].

2008 saw a journal paper on real-time RCU [DinakarGuniguntala2008IBMSysJ],
a history of how Linux changed RCU more than RCU changed Linux
[PaulEMcKenney2008RCUOSR], and a design overview of hierarchical RCU
[PaulEMcKenney2008HierarchicalRCU].

2009 introduced user-level RCU algorithms [PaulEMcKenney2009MaliciousURCU],
which Mathieu Desnoyers is now maintaining [MathieuDesnoyers2009URCU]
[MathieuDesnoyersPhD].  TINY_RCU [PaulEMcKenney2009BloatWatchRCU] made
its appearance, as did expedited RCU [PaulEMcKenney2009expeditedRCU].
The problem of resizable RCU-protected hash tables may now be on a path
to a solution [JoshTriplett2009RPHash].  A few academic researchers are now
using RCU to solve their parallel problems [HariKannan2009DynamicAnalysisRCU].

2010 produced a simpler preemptible-RCU implementation
based on TREE_RCU [PaulEMcKenney2010SimpleOptRCU], lockdep-RCU
[PaulEMcKenney2010LockdepRCU], another resizable RCU-protected hash
table [HerbertXu2010RCUResizeHash] (this one consuming more memory,
but allowing arbitrary changes in hash function, as required for DoS
avoidance in the networking code), realization of the 2009 RCU-protected
hash table with atomic node move [JoshTriplett2010RPHash], an update on
the RCU API [PaulEMcKenney2010RCUAPI].

2011 marked the inclusion of Nick Piggin's fully lockless dentry search
[LinusTorvalds2011Linux2:6:38:rc1:NPigginVFS], an RCU-protected red-black
tree using software transactional memory to protect concurrent updates
(strange, but true!) [PhilHoward2011RCUTMRBTree], yet another variant of
RCU-protected resizable hash tables [Triplett:2011:RPHash], the 3.0 RCU
trainwreck [PaulEMcKenney2011RCU3.0trainwreck], and Neil Brown's "Meet the
Lockers" LWN article [NeilBrown2011MeetTheLockers].  Some academic
work looked at debugging uses of RCU [Seyster:2011:RFA:2075416.2075425].

In 2012, Josh Triplett received his Ph.D. with his dissertation
covering RCU-protected resizable hash tables and the relationship
between memory barriers and read-side traversal order:  If the updater
is making changes in the opposite direction from the read-side traversal
order, the updater need only execute a memory-barrier instruction,
but if in the same direction, the updater needs to wait for a grace
period between the individual updates [JoshTriplettPhD].  Also in 2012,
after seventeen years of attempts, an RCU paper made it into a top-flight
academic journal, IEEE Transactions on Parallel and Distributed Systems
[MathieuDesnoyers2012URCU].  A group of researchers in Spain applied
user-level RCU to crowd simulation [GuillermoVigueras2012RCUCrowd], and
another group of researchers in Europe produced a formal description of
RCU based on separation logic [AlexeyGotsman2012VerifyGraceExtended],
which was published in the 2013 European Symposium on Programming
[AlexeyGotsman2013ESOPRCU].

BibTeX: 1980~1988년 선구 연구

219-353

이 묶음은 동시 검색 트리의 삭제 지연, active process 목록을 이용한 재사용 제어, lazy TLB flush, stale value를 허용하는 Argus를 기록한다. Manber82는 Manber84로 대체되며, 두 연구는 삭제 당시 활동 중인 process가 모두 끝나기 전까지 node 재사용을 막는다.

Rashid의 Mach virtual memory 논문은 CPU별 active address-space 집합을 보고 TLB flush를 늦춰 expensive cross-CPU 작업을 batching한다. Liskov의 Argus는 분산 계산에서 일시적으로 오래된 상태를 허용해도 정합성을 유지할 수 있는 상황을 보여 준다.

초기 참고문헌

인용 키한국어 주제·주석

Kung80동시 이진 검색 트리와 garbage collector 기반 지연 파괴

Manber82동적 검색 구조의 동시성 제어 초기 기술 보고서

Manber84활동 중 process 종료를 기다리는 AVL tree node 재사용

RichardRashid87aMach의 machine-independent VM과 lazy TLB flush

BarbaraLiskov1988ArgusCACMArgus와 오래된 값 허용의 분산 시스템 의미

인용 키는 원문의 BibTeX 항목과 일치하며, 제목·저자·발행 정보·URL은 아래 원문 블록에 그대로 보존된다.

Bibtex Entries

@article{Kung80
,author="H. T. Kung and Q. Lehman"
,title="Concurrent Manipulation of Binary Search Trees"
,Year="1980"
,Month="September"
,journal="ACM Transactions on Database Systems"
,volume="5"
,number="3"
,pages="354-382"
,annotation={
        Use garbage collector to clean up data after everyone is done with it.
        .
        Oldest use of something vaguely resembling RCU that I have found.
        http://portal.acm.org/citation.cfm?id=320619&dl=GUIDE,
        [Viewed December 3, 2007]
}
}

@techreport{Manber82
,author="Udi Manber and Richard E. Ladner"
,title="Concurrency Control in a Dynamic Search Structure"
,institution="Department of Computer Science, University of Washington"
,address="Seattle, Washington"
,year="1982"
,number="82-01-01"
,month="January"
,pages="28"
,annotation={
        .
        Superseded by Manber84.
        .
        Describes concurrent AVL tree implementation.  Uses a
        garbage-collection mechanism to handle concurrent use and deletion
        of nodes in the tree, but lacks the summary-of-execution-history
        concept of read-copy locking.
        .
        Keeps full list of processes that were active when a given
        node was to be deleted, and waits until all such processes have
        -terminated- before allowing this node to be reused.  This is
        not described in great detail -- one could imagine using process
        IDs for this if the ID space was large enough that overlapping
        never occurred.
        .
        This restriction makes this algorithm unsuitable for use in
        systems comprised of long-lived processes.  It also produces
        completely unacceptable overhead in systems with large numbers
        of processes.  Finally, it is specific to AVL trees.
        .
        Cites Kung80, so not an independent invention, but the first
        RCU-like usage that does not rely on an automatic garbage
        collector.
}
}

@article{Manber84
,author="Udi Manber and Richard E. Ladner"
,title="Concurrency Control in a Dynamic Search Structure"
,Year="1984"
,Month="September"
,journal="ACM Transactions on Database Systems"
,volume="9"
,number="3"
,pages="439-455"
,annotation={
        Describes concurrent AVL tree implementation.  Uses a
        garbage-collection mechanism to handle concurrent use and deletion
        of nodes in the tree, but lacks the summary-of-execution-history
        concept of read-copy locking.
        .
        Keeps full list of processes that were active when a given
        node was to be deleted, and waits until all such processes have
        -terminated- before allowing this node to be reused.  This is
        not described in great detail -- one could imagine using process
        IDs for this if the ID space was large enough that overlapping
        never occurred.
        .
        This restriction makes this algorithm unsuitable for use in
        systems comprised of long-lived processes.  It also produces
        completely unacceptable overhead in systems with large numbers
        of processes.  Finally, it is specific to AVL trees.
}
}

@Conference{RichardRashid87a
,Author="Richard Rashid and Avadis Tevanian and Michael Young and
David Golub and Robert Baron and David Black and William Bolosky and
Jonathan Chew"
,Title="Machine-Independent Virtual Memory Management for Paged
Uniprocessor and Multiprocessor Architectures"
,Booktitle="{2\textsuperscript{nd} Symposium on Architectural Support
for Programming Languages and Operating Systems}"
,Publisher="Association for Computing Machinery"
,Month="October"
,Year="1987"
,pages="31-39"
,Address="Palo Alto, CA"
,note="Available:
\url{http://www.cse.ucsc.edu/~randal/221/rashid-machvm.pdf}
[Viewed February 17, 2005]"
,annotation={
        Describes lazy TLB flush, where one waits for each CPU to pass
        through a scheduling-clock interrupt before reusing a given range
        of virtual address.  Does not describe how one determines that
        all CPUs have in fact taken such an interrupt, though there are
        no shortage of straightforward methods for accomplishing this.
        .
        Note that it does not make sense to just wait a fixed amount of
        time, since a given CPU might have interrupts disabled for an
        extended amount of time.
}
}

@article{BarbaraLiskov1988ArgusCACM
,author = {Barbara Liskov}
,title = {Distributed programming in {Argus}}
,journal = {Commun. ACM}
,volume = {31}
,number = {3}
,year = {1988}
,issn = {0001-0782}
,pages = {300--312}
,doi = {http://doi.acm.org/10.1145/42392.42399}
,publisher = {ACM}
,address = {New York, NY, USA}
,annotation={
        At the top of page 307: "Conflicts with deposits and withdrawals
        are necessary if the reported total is to be up to date.  They
        could be avoided by having total return a sum that is slightly
        out of date."  Relies on semantics -- approximate numerical
        values sometimes OK.
}
}

BibTeX: passive serialization과 지연 회수

354-484

Passive serialization은 hypervisor의 quiescent state를 사용한 제품 수준 deferred destruction이다. Pugh의 skip list는 독자를 명시적으로 추적하고 fine-grained update lock으로 작성자 경합을 낮춘다. Andrews의 chaotic relaxation과 Massalin의 deferred processing은 동기화 지점을 줄이는 일반 원칙을 제공한다.

Jacobson과 Aju John은 일정 시간을 기다리는 단순 delayed free를, Pu와 Cowan은 실행 중 알고리즘을 교체하는 replugging을 다룬다. 후자는 처음에는 단일 reader만 허용했고 이후 여러 reader로 확장했으며 memory barrier 비용과 locking 감소를 교환한다.

1989~1996 참고문헌

인용 키한국어 주제·주석

Hennessy89VM/XA의 passive serialization

Pugh90동시 skip list와 명시적 reader 추적

Andrews91textbookchaotic relaxation을 포함한 동시 프로그래밍 원칙

HMassalinPhD동기화를 단순화하는 지연 처리

Jacobson93고정 시간 delayed free로 read-side lock 회피

AjuJohn95동적 vnode와 지연 회수

Pu95a상용 UNIX의 단일-reader algorithm replugging

Cowan96a여러 reader를 허용하는 extensible kernel service

인용 키는 원문의 BibTeX 항목과 일치하며, 제목·저자·발행 정보·URL은 아래 원문 블록에 그대로 보존된다.

@techreport{Hennessy89
,author="James P. Hennessy and Damian L. Osisek and Joseph W. {Seigh II}"
,title="Passive Serialization in a Multitasking Environment"
,institution="US Patent and Trademark Office"
,address="Washington, DC"
,year="1989"
,number="US Patent 4,809,168 (lapsed)"
,month="February"
,pages="11"
}

@techreport{Pugh90
,author="William Pugh"
,title="Concurrent Maintenance of Skip Lists"
,institution="Institute of Advanced Computer Science Studies, Department of Computer Science, University of Maryland"
,address="College Park, Maryland"
,year="1990"
,number="CS-TR-2222.1"
,month="June"
,annotation={
        Concurrent access to skip lists.  Has both weak and strong search.
        Uses concept of ``garbage queue'', but has no real way of cleaning
        the garbage efficiently.
        .
        Appears to be an independent invention of an RCU-like mechanism.
}
}

# Was Adams91, see also syncrefs.bib.
@Book{Andrews91textbook
,Author="Gregory R. Andrews"
,title="Concurrent Programming, Principles, and Practices"
,Publisher="Benjamin Cummins"
,Year="1991"
,annotation={
        Has a few paragraphs describing ``chaotic relaxation'', a
        numerical analysis technique that allows multiprocessors to
        avoid synchronization overhead by using possibly-stale data.
        .
        Seems like this is descended from yet another independent
        invention of RCU-like function -- but this is restricted
        in that reclamation is not necessary.
}
}

@phdthesis{HMassalinPhD
,author="H. Massalin"
,title="Synthesis: An Efficient Implementation of Fundamental Operating
System Services"
,school="Columbia University"
,address="New York, NY"
,year="1992"
,annotation={
        Mondo optimizing compiler.
        Wait-free stuff.
        Good advice: defer work to avoid synchronization.  See page 90
                (PDF page 106), Section 5.4, fourth bullet point.
}
}

@unpublished{Jacobson93
,author="Van Jacobson"
,title="Avoid Read-Side Locking Via Delayed Free"
,year="1993"
,month="September"
,note="private communication"
,annotation={
        Use fixed time delay to approximate grace period.  Very simple,
        but subject to random memory corruption under heavy load.
        .
        Independent invention of RCU-like mechanism.
}
}

@Conference{AjuJohn95
,Author="Aju John"
,Title="Dynamic vnodes -- Design and Implementation"
,Booktitle="{USENIX Winter 1995}"
,Publisher="USENIX Association"
,Month="January"
,Year="1995"
,pages="11-23"
,Address="New Orleans, LA"
,note="Available:
\url{https://www.usenix.org/publications/library/proceedings/neworl/full_papers/john.a}
[Viewed October 1, 2010]"
,annotation={
        Age vnodes out of the cache, and have a fixed time set by a kernel
        parameter.  Not clear that all races were in fact correctly handled.
        Used a 20-minute time by default, which would most definitely not
        be suitable during DoS attacks or virus scans.
        .
        Apparently independent invention of RCU-like mechanism.
}
}

@conference{Pu95a
,Author = "Calton Pu and Tito Autrey and Andrew Black and Charles Consel and
Crispin Cowan and Jon Inouye and Lakshmi Kethana and Jonathan Walpole and
Ke Zhang"
,Title = "Optimistic Incremental Specialization: Streamlining a Commercial
,Operating System"
,Booktitle = "15\textsuperscript{th} ACM Symposium on
,Operating Systems Principles (SOSP'95)"
,address = "Copper Mountain, CO"
,month="December"
,year="1995"
,pages="314-321"
,annotation={
        Uses a replugger, but with a flag to signal when people are
        using the resource at hand.  Only one reader at a time.
}
}

@conference{Cowan96a
,Author = "Crispin Cowan and Tito Autrey and Charles Krasic and
,Calton Pu and Jonathan Walpole"
,Title = "Fast Concurrent Dynamic Linking for an Adaptive Operating System"
,Booktitle = "International Conference on Configurable Distributed Systems
(ICCDS'96)"
,address = "Annapolis, MD"
,month="May"
,year="1996"
,pages="108"
,isbn="0-8186-7395-8"
,annotation={
        Uses a replugger, but with a counter to signal when people are
        using the resource at hand.  Allows multiple readers.
}
}

BibTeX: DYNIX/ptx와 generations

485-635

Slingwine과 McKenney의 특허·기술 보고서·논문은 실행 이력을 이용해 read-side overhead를 줄이는 DYNIX/ptx RCU를 정립했다. 핵심은 각 reader 참조를 개별 추적하지 않고 CPU 실행 이력과 quiescent state를 모아 이전 참조가 사라졌음을 판단하는 것이다.

Tornado/K42의 generations는 existence lock을 대체해 객체 수명과 잠금 계층을 단순화했다. 2000년 Linux 네트워크 driver module 토론은 독립적으로 비슷한 아이디어에 접근했고, 2001년 자료는 Linux에서 RCU mutual exclusion을 설명한다.

DYNIX와 초기 Linux 참고문헌

인용 키한국어 주제·주석

Slingwine95낮은 overhead의 read-copy update 특허

Slingwine97thread activity summary를 이용한 coherency

Slingwine98RCU 장치와 방법의 후속 특허

McKenney98실행 이력으로 동시성 문제를 푸는 RCU 논문

Gamsa99Tornado의 locality·concurrency와 generations

RustyRussell2000amodular network driver 수명 토론

RustyRussell2000bLinux module 제거와 지연 회수 토론

McKenney01bLinux의 RCU mutual exclusion

Slingwine01RCU 특허·구현 자료의 확장

인용 키는 원문의 BibTeX 항목과 일치하며, 제목·저자·발행 정보·URL은 아래 원문 블록에 그대로 보존된다.

@techreport{Slingwine95
,author="John D. Slingwine and Paul E. McKenney"
,title="Apparatus and Method for Achieving Reduced Overhead Mutual
Exclusion and Maintaining Coherency in a Multiprocessor System
Utilizing Execution History and Thread Monitoring"
,institution="US Patent and Trademark Office"
,address="Washington, DC"
,year="1995"
,number="US Patent 5,442,758"
,month="August"
,annotation={
        Describes the parallel RCU infrastructure.  Includes NUMA aspect
        (structure of bitmap can reflect bus structure of computer system).
        .
        Another independent invention of an RCU-like mechanism, but the
        "real" RCU this time!
}
}

@techreport{Slingwine97
,author="John D. Slingwine and Paul E. McKenney"
,title="Method for Maintaining Data Coherency Using Thread Activity
Summaries in a Multicomputer System"
,institution="US Patent and Trademark Office"
,address="Washington, DC"
,year="1997"
,number="US Patent 5,608,893"
,month="March"
,pages="19"
,annotation={
        Describes use of RCU to synchronize data between a pair of
        SMP/NUMA computer systems.
}
}

@techreport{Slingwine98
,author="John D. Slingwine and Paul E. McKenney"
,title="Apparatus and Method for Achieving Reduced Overhead Mutual
Exclusion and Maintaining Coherency in a Multiprocessor System
Utilizing Execution History and Thread Monitoring"
,institution="US Patent and Trademark Office"
,address="Washington, DC"
,year="1998"
,number="US Patent 5,727,209"
,month="March"
,annotation={
        Describes doing an atomic update by copying the data item and
        then substituting it into the data structure.
}
}

@Conference{McKenney98
,Author="Paul E. McKenney and John D. Slingwine"
,Title="Read-Copy Update: Using Execution History to Solve Concurrency
Problems"
,Booktitle="{Parallel and Distributed Computing and Systems}"
,Month="October"
,Year="1998"
,pages="509-518"
,Address="Las Vegas, NV"
,annotation={
        Describes and analyzes RCU mechanism in DYNIX/ptx.  Describes
        application to linked list update and log-buffer flushing.
        Defines 'quiescent state'.  Includes both measured and analytic
        evaluation.
        http://www.rdrop.com/users/paulmck/RCU/rclockpdcsproof.pdf
        [Viewed December 3, 2007]
}
}

@Conference{Gamsa99
,Author="Ben Gamsa and Orran Krieger and Jonathan Appavoo and Michael Stumm"
,Title="Tornado: Maximizing Locality and Concurrency in a Shared Memory
Multiprocessor Operating System"
,Booktitle="{Proceedings of the 3\textsuperscript{rd} Symposium on
Operating System Design and Implementation}"
,Month="February"
,Year="1999"
,pages="87-100"
,Address="New Orleans, LA"
,annotation={
        Use of RCU-like facility in K42/Tornado.  Another independent
        invention of RCU.
        See especially pages 7-9 (Section 5).
        http://www.usenix.org/events/osdi99/full_papers/gamsa/gamsa.pdf
        [Viewed August 30, 2006]
}
}

@unpublished{RustyRussell2000a
,Author="Rusty Russell"
,Title="Re: modular net drivers"
,month="June"
,year="2000"
,day="23"
,note="Available:
\url{http://oss.sgi.com/projects/netdev/archive/2000-06/msg00250.html}
[Viewed April 10, 2006]"
,annotation={
        Proto-RCU proposal from Phil Rumpf and Rusty Russell.
        Yet another independent invention of RCU.
        Outline of algorithm to unload modules...
        .
        Appeared on net-dev mailing list.
}
}

@unpublished{RustyRussell2000b
,Author="Rusty Russell"
,Title="Re: modular net drivers"
,month="June"
,year="2000"
,day="24"
,note="Available:
\url{http://oss.sgi.com/projects/netdev/archive/2000-06/msg00254.html}
[Viewed April 10, 2006]"
,annotation={
        Proto-RCU proposal from Phil Rumpf and Rusty Russell.
        .
        Appeared on net-dev mailing list.
}
}

@unpublished{McKenney01b
,Author="Paul E. McKenney and Dipankar Sarma"
,Title="Read-Copy Update Mutual Exclusion in {Linux}"
,month="February"
,year="2001"
,note="Available:
\url{http://lse.sourceforge.net/locking/rcu/rcupdate_doc.html}
[Viewed October 18, 2004]"
,annotation={
        Prototypical Linux documentation for RCU.
}
}

@techreport{Slingwine01
,author="John D. Slingwine and Paul E. McKenney"
,title="Apparatus and Method for Achieving Reduced Overhead Mutual
Exclusion and Maintaining Coherency in a Multiprocessor System
Utilizing Execution History and Thread Monitoring"
,institution="US Patent and Trademark Office"
,address="Washington, DC"
,year="2001"
,number="US Patent 6,219,690"
,month="April"
,annotation={
        'Change in mode' aspect of RCU.  Can be thought of as a lazy barrier.
}
}

BibTeX: Linux RCU 도입과 lock-free 회수

636-853

2001년 OLS 발표와 LKML patch는 삽입 중에도 목록을 lock-free로 순회하는 Linux RCU API를 구체화했다. 이어 dcache, credential, System V IPC, bridge lock 등 실제 kernel subsystem에서 scalability를 검증했다.

Michael의 lock-free hash와 hazard pointer 연구는 원자적 instruction으로 안전한 memory reclamation을 제공했다. Repeat Offender 문제와 관련 연구는 동적 크기 구조에서 같은 주소가 재사용되는 ABA 성격의 경합을 다룬다. 이 계열은 RCU와 목적이 비슷하지만 reader의 hazard 게시 비용이 다르다.

2001~2003 도입기 참고문헌

인용 키한국어 주제·주석

McKenney01aLinux RCU 최초 주요 발표

McKenney01f삽입과 lock-free list traversal RFC

Spraul01RCU list patch 검토

LinusTorvalds2001aLinux list traversal ordering 토론

Blanchard02aRCU dcache와 ratcache 성능

Michael02b동적 lock-free hash와 set

Linder02adirectory entry cache 확장성

McKenney02aLinux RCU patch와 사용 사례

Sarma02aSPECweb99 dcache 확장성

Barbieri02VFS credential과 RCU 토론

Michael02ahazard pointer 기반 안전한 회수

Dickins02aSystem V IPC에 RCU 적용 제안

HerlihyLM02동적 lock-free 구조의 Repeat Offender 문제

Sarma02bdcache_rcu benchmark

MingmingCao2002IPCRCUIPC lock RCU patch

LinusTorvalds2003abrlock과 RCU 관련 kernel 토론

인용 키는 원문의 BibTeX 항목과 일치하며, 제목·저자·발행 정보·URL은 아래 원문 블록에 그대로 보존된다.

@Conference{McKenney01a
,Author="Paul E. McKenney and Jonathan Appavoo and Andi Kleen and
Orran Krieger and Rusty Russell and Dipankar Sarma and Maneesh Soni"
,Title="Read-Copy Update"
,Booktitle="{Ottawa Linux Symposium}"
,Month="July"
,Year="2001"
,note="Available:
\url{https://kernel.org/doc/ols/2001/read-copy.pdf}
\url{http://www.rdrop.com/users/paulmck/RCU/rclock_OLS.2001.05.01c.pdf}
[Viewed June 23, 2004]"
,annotation={
        Described RCU, and presented some patches implementing and using
        it in the Linux kernel.
}
}

@unpublished{McKenney01f
,Author="Paul E. McKenney"
,Title="{RFC:} patch to allow lock-free traversal of lists with insertion"
,month="October"
,year="2001"
,note="Available:
\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=100259266316456&w=2}
[Viewed June 23, 2004]"
,annotation={
        Memory-barrier and Alpha thread.  100 messages, not too bad...
}
}

@unpublished{Spraul01
,Author="Manfred Spraul"
,Title="Re: {RFC:} patch to allow lock-free traversal of lists with insertion"
,month="October"
,year="2001"
,note="Available:
\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=100264675012867&w=2}
[Viewed June 23, 2004]"
,annotation={
        Suggested burying memory barriers in Linux's list-manipulation
        primitives.
}
}

@unpublished{LinusTorvalds2001a
,Author="Linus Torvalds"
,Title="{Re:} {[Lse-tech]} {Re:} {RFC:} patch to allow lock-free traversal of lists with insertion"
,month="October"
,year="2001"
,note="Available:
\url{https://lore.kernel.org/r/Pine.LNX.4.33.0110131015410.8707-100000@penguin.transmeta.com}
[Viewed August 21, 2004]"
,annotation={
}
}

@unpublished{Blanchard02a
,Author="Anton Blanchard"
,Title="some RCU dcache and ratcache results"
,month="March"
,year="2002"
,note="Available:
\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=101637107412972&w=2}
[Viewed October 18, 2004]"
}

@conference{Michael02b
,author="Maged M. Michael"
,title="High Performance Dynamic Lock-Free Hash Tables and List-Based Sets"
,Year="2002"
,Month="August"
,booktitle="{Proceedings of the 14\textsuperscript{th} Annual ACM
Symposium on Parallel
Algorithms and Architecture}"
,pages="73-82"
,annotation={
Like the title says...
}
}

@Conference{Linder02a
,Author="Hanna Linder and Dipankar Sarma and Maneesh Soni"
,Title="Scalability of the Directory Entry Cache"
,Booktitle="{Ottawa Linux Symposium}"
,Month="June"
,Year="2002"
,pages="289-300"
,annotation={
        Measured scalability of Linux 2.4 kernel's directory-entry cache
        (dcache), and measured some scalability enhancements.
}
}

@Conference{McKenney02a
,Author="Paul E. McKenney and Dipankar Sarma and
Andrea Arcangeli and Andi Kleen and Orran Krieger and Rusty Russell"
,Title="Read-Copy Update"
,Booktitle="{Ottawa Linux Symposium}"
,Month="June"
,Year="2002"
,pages="338-367"
,note="Available:
\url{http://www.linux.org.uk/~ajh/ols2002_proceedings.pdf.gz}
[Viewed June 23, 2004]"
,annotation={
        Presented and compared a number of RCU implementations for the
        Linux kernel.
}
}

@unpublished{Sarma02a
,Author="Dipankar Sarma"
,Title="specweb99: dcache scalability results"
,month="July"
,year="2002"
,note="Available:
\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=102645767914212&w=2}
[Viewed June 23, 2004]"
,annotation={
        Compare fastwalk and RCU for dcache.  RCU won.
}
}

@unpublished{Barbieri02
,Author="Luca Barbieri"
,Title="Re: {[PATCH]} Initial support for struct {vfs\_cred}"
,month="August"
,year="2002"
,note="Available:
\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=103082050621241&w=2}
[Viewed: June 23, 2004]"
,annotation={
        Suggested RCU for vfs\_shared\_cred.
}
}

@conference{Michael02a
,author="Maged M. Michael"
,title="Safe Memory Reclamation for Dynamic Lock-Free Objects Using Atomic
Reads and Writes"
,Year="2002"
,Month="August"
,booktitle="{Proceedings of the 21\textsuperscript{st} Annual ACM
Symposium on Principles of Distributed Computing}"
,pages="21-30"
,annotation={
        Each thread keeps an array of pointers to items that it is
        currently referencing.        Sort of an inside-out garbage collection
        mechanism, but one that requires the accessing code to explicitly
        state its needs.  Also requires read-side memory barriers on
        most architectures.
}
}

@unpublished{Dickins02a
,author="Hugh Dickins"
,title="Use RCU for System-V IPC"
,year="2002"
,month="October"
,note="private communication"
}

@InProceedings{HerlihyLM02
,author={Maurice Herlihy and Victor Luchangco and Mark Moir}
,title="The Repeat Offender Problem: A Mechanism for Supporting Dynamic-Sized,
Lock-Free Data Structures"
,booktitle={Proceedings of 16\textsuperscript{th} International
Symposium on Distributed Computing}
,year=2002
,month="October"
,pages="339-353"
}

@unpublished{Sarma02b
,Author="Dipankar Sarma"
,Title="Some dcache\_rcu benchmark numbers"
,month="October"
,year="2002"
,note="Available:
\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=103462075416638&w=2}
[Viewed June 23, 2004]"
,annotation={
        Performance of dcache RCU on kernbench for 16x NUMA-Q and 1x,
        2x, and 4x systems.  RCU does no harm, and helps on 16x.
}
}

@unpublished{MingmingCao2002IPCRCU
,Author="Mingming Cao"
,Title="[PATCH]updated ipc lock patch"
,month="October"
,year="2002"
,note="Available:
\url{https://lore.kernel.org/r/3DB86B05.447E7410@us.ibm.com}
[Viewed February 15, 2014]"
,annotation={
        Mingming Cao's patch to introduce RCU to SysV IPC.
}
}

@unpublished{LinusTorvalds2003a
,Author="Linus Torvalds"
,Title="Re: {[PATCH]} small fixes in brlock.h"
,month="March"
,year="2003"
,note="Available:
\url{https://lore.kernel.org/r/Pine.LNX.4.44.0303091831560.2129-100000@home.transmeta.com}
[Viewed March 13, 2006]"
,annotation={
        Linus suggests replacing brlock with RCU and/or seqlocks:
        .
        'It's entirely possible that the current user could be replaced
        by RCU and/or seqlocks, and we could get rid of brlocks entirely.'
        .
        Stephen Hemminger responds by replacing them with RCU.
}
}

BibTeX: hot swapping과 dcache 확장

854-1050

K42 연구는 OS 기능을 실행 중 교체하는 hot swapping에 RCU를 사용했고, System V IPC와 online reconfiguration 연구는 독자가 진행 중인 상태에서 구현이나 객체를 바꾸는 방법을 보여 준다. Linux Journal 자료는 Linux 2.5의 RCU 사용법을 넓은 독자층에 소개했다.

2004년 자료들은 dcache 확장, CPU별 RCU 대 locking 성능, low-latency RCU, radix/list update 설계를 다룬다. `rcu_dereference()`와 `rcu_assign_pointer()`의 memory ordering 논의로 이어지는 기반도 이 시기에 형성되었다.

2003~2004 참고문헌

인용 키한국어 주제·주석

Appavoo03ahot-swappable system software

Seigh03Read Copy Update 개요

Arcangeli03System V IPC의 RCU 구현

Soules03aonline reconfiguration 지원

McKenney03aLinux 2.5 kernel의 RCU 사용

Sarma03aRCU low-latency patch

Friedberg03alock-free wildcard search 자료 구조

McKenney04aRCU로 dcache 확장

McKenney04b여러 CPU에서 RCU와 locking 성능 비교

Sarma04a실험적 low-latency RCU

Sarma04blow-latency patch 후속 토론

Spraul04aRCU lock update RFC

Steiner04aRCU update patch 검토와 benchmark

인용 키는 원문의 BibTeX 항목과 일치하며, 제목·저자·발행 정보·URL은 아래 원문 블록에 그대로 보존된다.

@article{Appavoo03a
,author="J. Appavoo and K. Hui and C. A. N. Soules and R. W. Wisniewski and
D. M. {Da Silva} and O. Krieger and M. A. Auslander and D. J. Edelsohn and
B. Gamsa and G. R. Ganger and P. McKenney and M. Ostrowski and
B. Rosenburg and M. Stumm and J. Xenidis"
,title="Enabling Autonomic Behavior in Systems Software With Hot Swapping"
,Year="2003"
,Month="January"
,journal="IBM Systems Journal"
,volume="42"
,number="1"
,pages="60-76"
,annotation={
        Use of RCU to enable hot-swapping for autonomic behavior in K42.
}
}

@unpublished{Seigh03
,author="Joseph W. {Seigh II}"
,title="Read Copy Update"
,Year="2003"
,Month="March"
,note="email correspondence"
,annotation={
        Described the relationship of the VM/XA passive serialization to RCU.
}
}

@Conference{Arcangeli03
,Author="Andrea Arcangeli and Mingming Cao and Paul E. McKenney and
Dipankar Sarma"
,Title="Using Read-Copy Update Techniques for {System V IPC} in the
{Linux} 2.5 Kernel"
,Booktitle="Proceedings of the 2003 USENIX Annual Technical Conference
(FREENIX Track)"
,Publisher="USENIX Association"
,year="2003"
,month="June"
,pages="297-310"
,annotation={
        Compared updated RCU implementations for the Linux kernel, and
        described System V IPC use of RCU, including order-of-magnitude
        performance improvements.
        http://www.rdrop.com/users/paulmck/RCU/rcu.FREENIX.2003.06.14.pdf
}
}

@Conference{Soules03a
,Author="Craig A. N. Soules and Jonathan Appavoo and Kevin Hui and
Dilma {Da Silva} and Gregory R. Ganger and Orran Krieger and
Michael Stumm and Robert W. Wisniewski and Marc Auslander and
Michal Ostrowski and Bryan Rosenburg and Jimi Xenidis"
,Title="System Support for Online Reconfiguration"
,Booktitle="Proceedings of the 2003 USENIX Annual Technical Conference"
,Publisher="USENIX Association"
,year="2003"
,month="June"
,pages="141-154"
}

@article{McKenney03a
,author="Paul E. McKenney"
,title="Using {RCU} in the {Linux} 2.5 Kernel"
,Year="2003"
,Month="October"
,journal="Linux Journal"
,volume="1"
,number="114"
,pages="18-26"
,note="Available:
\url{http://www.linuxjournal.com/article/6993}
[Viewed November 14, 2007]"
,annotation={
        Reader-friendly intro to RCU, with the infamous old-man-and-brat
        cartoon.
}
}

@unpublished{Sarma03a
,Author="Dipankar Sarma"
,Title="RCU low latency patches"
,month="December"
,year="2003"
,note="Message ID: 20031222180114.GA2248@in.ibm.com"
,annotation={
        dipankar/ct.2004.03.27/RCUll.2003.12.22.patch
}
}

@techreport{Friedberg03a
,author="Stuart A. Friedberg"
,title="Lock-Free Wild Card Search Data Structure and Method"
,institution="US Patent and Trademark Office"
,address="Washington, DC"
,year="2003"
,number="US Patent 6,662,184"
,month="December"
,pages="112"
,annotation={
        Applies RCU to a wildcard-search Patricia tree in order to permit
        synchronization-free lookup.  RCU is used to retain removed nodes
        for a grace period before freeing them.
}
}

@article{McKenney04a
,author="Paul E. McKenney and Dipankar Sarma and Maneesh Soni"
,title="Scaling dcache with {RCU}"
,Year="2004"
,Month="January"
,journal="Linux Journal"
,volume="1"
,number="118"
,pages="38-46"
,annotation={
        Reader friendly intro to dcache and RCU.
        http://www.linuxjournal.com/node/7124
        [Viewed December 26, 2010]
}
}

@Conference{McKenney04b
,Author="Paul E. McKenney"
,Title="{RCU} vs. Locking Performance on Different {CPUs}"
,Booktitle="{linux.conf.au}"
,Month="January"
,Year="2004"
,Address="Adelaide, Australia"
,note="Available:
\url{http://www.linux.org.au/conf/2004/abstracts.html#90}
\url{http://www.rdrop.com/users/paulmck/RCU/lockperf.2004.01.17a.pdf}
[Viewed June 23, 2004]"
,annotation={
        Compares performance of RCU to that of other locking primitives
        over a number of CPUs (x86, Opteron, Itanium, and PPC).
}
}

@unpublished{Sarma04a
,Author="Dipankar Sarma"
,Title="{[PATCH]} {RCU} for low latency (experimental)"
,month="March"
,year="2004"
,note="\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=108003746402892&w=2}"
,annotation={
        Head of thread: dipankar/2004.03.23/rcu-low-lat.1.patch
}
}

@unpublished{Sarma04b
,Author="Dipankar Sarma"
,Title="Re: {[PATCH]} {RCU} for low latency (experimental)"
,month="March"
,year="2004"
,note="\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=108016474829546&w=2}"
,annotation={
        dipankar/rcuth.2004.03.24/rcu-throttle.patch
}
}

@unpublished{Spraul04a
,Author="Manfred Spraul"
,Title="[RFC] 0/5 rcu lock update"
,month="May"
,year="2004"
,note="Available:
\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=108546407726602&w=2}
[Viewed June 23, 2004]"
,annotation={
        Hierarchical-bitmap patch for RCU infrastructure.
}
}

@unpublished{Steiner04a
,Author="Jack Steiner"
,Title="Re: [Lse-tech] [RFC, PATCH] 1/5 rcu lock update:
Add per-cpu batch counter"
,month="May"
,year="2004"
,note="Available:
\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=108551764515332&w=2}
[Viewed June 23, 2004]"
,annotation={
        RCU runs reasonably on a 512-CPU SGI using Manfred Spraul's patches,
        which may be found at:
        https://lore.kernel.org/r/40AC9823.6020709@colorfullife.com (split vars into cachelines)
        https://lore.kernel.org/r/Pine.LNX.4.44.0405222141260.11106-100000@dbl.q-ag.de (cpu_quiet() patch)
        https://lore.kernel.org/r/200405250535.i4P5ZJo8017583@dbl.q-ag.de (0/5)
        https://lore.kernel.org/r/200405250535.i4P5ZKAQ017591@dbl.q-ag.de (1/5)
                https://lore.kernel.org/r/20040525203215.GB5127@sgi.com (works for Jack)
        https://lore.kernel.org/r/200405250535.i4P5ZLiR017599@dbl.q-ag.de (2/5)
        https://lore.kernel.org/r/200405250535.i4P5ZMFt017607@dbl.q-ag.de (3/5)
        https://lore.kernel.org/r/200405250535.i4P5ZN6g017615@dbl.q-ag.de (4/5)
        https://lore.kernel.org/r/200405250535.i4P5ZO7I017623@dbl.q-ag.de (5/5)
}
}

BibTeX: 실시간 RCU와 hazard pointer

1051-1222

Sarma의 연구는 깊은 sub-millisecond 응답 시간을 위해 RCU를 soft real-time에 맞췄고, Michael의 journal 논문은 hazard pointer memory reclamation을 정리했다. McKenney의 박사 논문은 deferred destruction을 OS kernel 전반에 적용하는 설계와 성능을 체계화했다.

LKML 자료들은 대체 RCU 구현, radix/tree, TCP hash, lock-free fd lookup, `rcu_assign_pointer()` 장벽 제거 조건, SELinux AVC 전환을 기록한다. SELinux 사례는 RCU가 보안 정책 조회의 reader scalability를 높이는 실제 효과를 보여 준다.

2004 참고문헌

인용 키한국어 주제·주석

Sarma04cdeep sub-millisecond 응답을 위한 RCU

MagedMichael04ahazard pointer 안전 회수

PaulEdwardMcKenneyPhDdeferred destruction과 RCU 박사 논문

PaulEMcKenney2004rcu:dereference추상화된 rcu_dereference 토론

JimHouston04a대체 RCU 구현 RFC

TomHart04aLinux kernel lock-free 기법 석사 논문

Vaddagiri04aTCP ehash 조회의 RCU 적용

Thirumalai04alock-free fd lookup patchset

Thirumalai04bfd lookup 후속 검토

PaulEMcKenney2004rcu:assign:pointerrcu_assign_pointer 장벽 최적화

JamesMorris04aSELinux AVC의 RCU 전환

JamesMorris04bSELinux kernel 성능 개선

인용 키는 원문의 BibTeX 항목과 일치하며, 제목·저자·발행 정보·URL은 아래 원문 블록에 그대로 보존된다.

@Conference{Sarma04c
,Author="Dipankar Sarma and Paul E. McKenney"
,Title="Making {RCU} Safe for Deep Sub-Millisecond Response
Realtime Applications"
,Booktitle="Proceedings of the 2004 USENIX Annual Technical Conference
(FREENIX Track)"
,Publisher="USENIX Association"
,year="2004"
,month="June"
,pages="182-191"
,annotation={
        Describes and compares a number of modifications to the Linux RCU
        implementation that make it friendly to realtime applications.
        https://www.usenix.org/conference/2004-usenix-annual-technical-conference/making-rcu-safe-deep-sub-millisecond-response
        [Viewed July 26, 2012]
}
}

@article{MagedMichael04a
,author="Maged M. Michael"
,title="Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects"
,Year="2004"
,Month="June"
,journal="IEEE Transactions on Parallel and Distributed Systems"
,volume="15"
,number="6"
,pages="491-504"
,url="Available:
\url{http://www.research.ibm.com/people/m/michael/ieeetpds-2004.pdf}
[Viewed March 1, 2005]"
,annotation={
        New canonical hazard-pointer citation.
}
}

@phdthesis{PaulEdwardMcKenneyPhD
,author="Paul E. McKenney"
,title="Exploiting Deferred Destruction:
An Analysis of Read-Copy-Update Techniques
in Operating System Kernels"
,school="OGI School of Science and Engineering at
Oregon Health and Sciences University"
,year="2004"
,annotation={
        Describes RCU implementations and presents design patterns
        corresponding to common uses of RCU in several operating-system
        kernels.
        http://www.rdrop.com/users/paulmck/RCU/RCUdissertation.2004.07.14e1.pdf
        [Viewed October 15, 2004]
}
}

@unpublished{PaulEMcKenney2004rcu:dereference
,Author="Dipankar Sarma"
,Title="{Re: RCU : Abstracted RCU dereferencing [5/5]}"
,month="August"
,year="2004"
,note="Available:
\url{https://lore.kernel.org/r/20040807192424.GF3936@in.ibm.com}
[Viewed June 8, 2010]"
,annotation={
        Introduce rcu_dereference().
}
}

@unpublished{JimHouston04a
,Author="Jim Houston"
,Title="{[RFC\&PATCH] Alternative {RCU} implementation}"
,month="August"
,year="2004"
,note="Available:
\url{https://lore.kernel.org/r/1093873222.984.12.camel@new.localdomain}
[Viewed February 17, 2005]"
,annotation={
        Uses active code in rcu_read_lock() and rcu_read_unlock() to
        make RCU happen, allowing RCU to function on CPUs that do not
        receive a scheduling-clock interrupt.
}
}

@unpublished{TomHart04a
,Author="Thomas E. Hart"
,Title="Master's Thesis: Applying Lock-free Techniques to the {Linux} Kernel"
,month="October"
,year="2004"
,note="Available:
\url{http://www.cs.toronto.edu/~tomhart/masters_thesis.html}
[Viewed October 15, 2004]"
,annotation={
        Proposes comparing RCU to lock-free methods for the Linux kernel.
}
}

@unpublished{Vaddagiri04a
,Author="Srivatsa Vaddagiri"
,Title="Subject: [RFC] Use RCU for tcp\_ehash lookup"
,month="October"
,year="2004"
,note="Available:
\url{http://marc.theaimsgroup.com/?t=109395731700004&r=1&w=2}
[Viewed October 18, 2004]"
,annotation={
        Srivatsa's RCU patch for tcp_ehash lookup.
}
}

@unpublished{Thirumalai04a
,Author="Ravikiran Thirumalai"
,Title="Subject: [patchset] Lockfree fd lookup 0 of 5"
,month="October"
,year="2004"
,note="Available:
\url{http://marc.theaimsgroup.com/?t=109144217400003&r=1&w=2}
[Viewed October 18, 2004]"
,annotation={
        Ravikiran's lockfree FD patch.
}
}

@unpublished{Thirumalai04b
,Author="Ravikiran Thirumalai"
,Title="Subject: Re: [patchset] Lockfree fd lookup 0 of 5"
,month="October"
,year="2004"
,note="Available:
\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=109152521410459&w=2}
[Viewed October 18, 2004]"
,annotation={
        Ravikiran's lockfree FD patch.
}
}

@unpublished{PaulEMcKenney2004rcu:assign:pointer
,Author="Paul E. McKenney"
,Title="{[PATCH 1/3] RCU: \url{rcu_assign_pointer()} removal of memory barriers}"
,month="October"
,year="2004"
,note="Available:
\url{https://lore.kernel.org/r/20041023202723.GA1930@us.ibm.com}
[Viewed June 8, 2010]"
,annotation={
        Introduce rcu_assign_pointer().
}
}

@unpublished{JamesMorris04a
,Author="James Morris"
,Title="{[PATCH 2/3] SELinux} scalability - convert {AVC} to {RCU}"
,day="15"
,month="November"
,year="2004"
,note="\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=110054979416004&w=2}"
,annotation={
        James Morris posts Kaigai Kohei's patch to LKML.
        [Viewed December 10, 2004]
        Kaigai's patch is at https://lore.kernel.org/r/200409271057.i8RAvcA1007873@mailsv.bs1.fc.nec.co.jp
}
}

@unpublished{JamesMorris04b
,Author="James Morris"
,Title="Recent Developments in {SELinux} Kernel Performance"
,month="December"
,year="2004"
,note="Available:
\url{http://www.livejournal.com/users/james_morris/2153.html}
[Viewed December 10, 2004]"
,annotation={
        RCU helps SELinux performance.  ;-)  Made LWN.
}
}

BibTeX: preemptible RCU와 real-time

1223-1410

2005년 자료는 RCU semantics를 명문화하고 `CONFIG_PREEMPT_RT`에서 read-side critical section을 선점할 수 있게 하는 방향을 다룬다. 핵심 난제는 선점된 reader를 추적하고 높은 우선순위 updater가 낮은 우선순위 reader 때문에 무기한 막히지 않게 하는 것이다.

`synchronize_kernel()` 폐기와 RCU API 정리, SMR/hazard pointer와의 결합, lock-free reclamation의 성능 필요성도 함께 논의된다. 홈페이지와 RCU 자료실 항목은 당시 설계 문서와 patch를 연결하는 기준점이다.

2005 참고문헌

인용 키한국어 주제·주석

PaulMcKenney2005RCUSemanticsRCU 의미론의 첫 정리

PaulMcKenney2005ereal-time preemption과 RCU

EsbenNeilsen2005aRT RCU 응답과 우선순위 토론

TomHart05a빠른 lock-free 구조에 필요한 효율적 회수

JonCorbet2005DeprecateSyncKernelsynchronize_kernel() 폐기

PaulMcKenney05aCONFIG_PREEMPT_RT RCU 진행

PaulMcKenney05bSMP Linux의 hard real-time 응답

PaulEMcKenneyHomePagePaul E. McKenney 자료 홈페이지

PaulEMcKenneyRCUPageRCU 논문·patch 모음

JosephSeigh2005aRCU와 SMR 결합

JosephSeigh2005block-free 동기화 primitive

PaulMcKenney2005cpreemptible RT RCU patch

PaulMcKenney2005dRT preemption 후속 토론

인용 키는 원문의 BibTeX 항목과 일치하며, 제목·저자·발행 정보·URL은 아래 원문 블록에 그대로 보존된다.

@unpublished{PaulMcKenney2005RCUSemantics
,Author="Paul E. McKenney and Jonathan Walpole"
,Title="{RCU} Semantics: A First Attempt"
,month="January"
,year="2005"
,day="30"
,note="Available:
\url{http://www.rdrop.com/users/paulmck/RCU/rcu-semantics.2005.01.30a.pdf}
[Viewed December 6, 2009]"
,annotation={
        Early derivation of RCU semantics.
}
}

@unpublished{PaulMcKenney2005e
,Author="Paul E. McKenney"
,Title="Real-Time Preemption and {RCU}"
,month="March"
,year="2005"
,day="17"
,note="Available:
\url{https://lore.kernel.org/r/20050318002026.GA2693@us.ibm.com}
[Viewed September 5, 2005]"
,annotation={
        First posting showing how RCU can be safely adapted for
        preemptible RCU read side critical sections.
}
}

@unpublished{EsbenNeilsen2005a
,Author="Esben Neilsen"
,Title="Re: Real-Time Preemption and {RCU}"
,month="March"
,year="2005"
,day="18"
,note="Available:
\url{https://lore.kernel.org/r/Pine.OSF.4.05.10503181336310.2466-100000@da410.phys.au.dk}
[Viewed March 30, 2006]"
,annotation={
        Esben Neilsen suggests read-side suppression of grace-period
        processing for crude-but-workable realtime RCU.  The downside
        is indefinite grace periods...  But this is OK for experimentation
        and testing.
}
}

@unpublished{TomHart05a
,Author="Thomas E. Hart and Paul E. McKenney and Angela Demke Brown"
,Title="Efficient Memory Reclamation is Necessary for Fast Lock-Free
Data Structures"
,month="March"
,year="2005"
,note="Available:
\url{ftp://ftp.cs.toronto.edu/csrg-technical-reports/515/}
[Viewed March 4, 2005]"
,annotation={
        Comparison of RCU, QBSR, and EBSR.  RCU wins for read-mostly
        workloads.  ;-)
}
}

@unpublished{JonCorbet2005DeprecateSyncKernel
,Author="Jonathan Corbet"
,Title="API change: synchronize_kernel() deprecated"
,month="May"
,day="3"
,year="2005"
,note="Available:
\url{http://lwn.net/Articles/134484/}
[Viewed May 3, 2005]"
,annotation={
        Jon Corbet describes deprecation of synchronize_kernel()
        in favor of synchronize_rcu() and synchronize_sched().
}
}

@unpublished{PaulMcKenney05a
,Author="Paul E. McKenney"
,Title="{[RFC]} {RCU} and {CONFIG\_PREEMPT\_RT} progress"
,month="May"
,year="2005"
,note="Available:
\url{https://lore.kernel.org/r/20050510012444.GA3011@us.ibm.com}
[Viewed May 13, 2005]"
,annotation={
        First publication of working lock-based deferred free patches
        for the CONFIG_PREEMPT_RT environment.
}
}

@conference{PaulMcKenney05b
,Author="Paul E. McKenney and Dipankar Sarma"
,Title="Towards Hard Realtime Response from the {Linux} Kernel on {SMP} Hardware"
,Booktitle="linux.conf.au 2005"
,month="April"
,year="2005"
,address="Canberra, Australia"
,note="Available:
\url{http://www.rdrop.com/users/paulmck/RCU/realtimeRCU.2005.04.23a.pdf}
[Viewed May 13, 2005]"
,annotation={
        Realtime turns into making RCU yet more realtime friendly.
        http://lca2005.linux.org.au/Papers/Paul%20McKenney/Towards%20Hard%20Realtime%20Response%20from%20the%20Linux%20Kernel/LKS.2005.04.22a.pdf
}
}

@unpublished{PaulEMcKenneyHomePage
,Author="Paul E. McKenney"
,Title="{Paul} {E.} {McKenney}"
,month="May"
,year="2005"
,note="Available:
\url{http://www.rdrop.com/users/paulmck/}
[Viewed May 25, 2005]"
,annotation={
        Paul McKenney's home page.
}
}

@unpublished{PaulEMcKenneyRCUPage
,Author="Paul E. McKenney"
,Title="Read-Copy Update {(RCU)}"
,month="May"
,year="2005"
,note="Available:
\url{http://www.rdrop.com/users/paulmck/RCU}
[Viewed May 25, 2005]"
,annotation={
        Paul McKenney's RCU page.
}
}

@unpublished{JosephSeigh2005a
,Author="Joseph Seigh"
,Title="{RCU}+{SMR} (hazard pointers)"
,month="July"
,year="2005"
,note="Personal communication"
,annotation={
        Joe Seigh announcing his atomic-ptr-plus project.
        http://sourceforge.net/projects/atomic-ptr-plus/
}
}

@unpublished{JosephSeigh2005b
,Author="Joseph Seigh"
,Title="Lock-free synchronization primitives"
,month="July"
,day="6"
,year="2005"
,note="Available:
\url{http://sourceforge.net/projects/atomic-ptr-plus/}
[Viewed August 8, 2005]"
,annotation={
        Joe Seigh's atomic-ptr-plus project.
}
}

@unpublished{PaulMcKenney2005c
,Author="Paul E.McKenney"
,Title="{[RFC,PATCH] RCU} and {CONFIG\_PREEMPT\_RT} sane patch"
,month="August"
,day="1"
,year="2005"
,note="Available:
\url{https://lore.kernel.org/r/20050801171137.GA1754@us.ibm.com}
[Viewed March 14, 2006]"
,annotation={
        First operating counter-based realtime RCU patch posted to LKML.
}
}

@unpublished{PaulMcKenney2005d
,Author="Paul E. McKenney"
,Title="Re: [Fwd: Re: [patch] Real-Time Preemption, -RT-2.6.13-rc4-V0.7.52-01]"
,month="August"
,day="8"
,year="2005"
,note="Available:
\url{https://lore.kernel.org/r/20050808144216.GA1307@us.ibm.com}
[Viewed March 14, 2006]"
,annotation={
        First operating counter-based realtime RCU patch posted to LKML,
        but fixed so that various unusual combinations of configuration
        parameters all function properly.
}
}

BibTeX: rcutorture, page cache, SRCU

1411-1588

`rcutorture`가 RCU 구현을 반복적으로 압박하고 barrier, priority inversion, callback 진행을 자동 검증하는 기반으로 도입되었다. OOM 회피와 latency, hashed locking, radix tree와 page cache의 lockless read-side 전환이 실제 kernel scalability를 넓혔다.

2006년에는 realtime·embedded workload를 위한 RCU 확장, sleepable RCU, LC-trie/hash 조합이 발표되었다. classic RCU를 분리해 SRCU로 발전시키는 논의와 Linux kernel 안의 RCU 사용량 조사도 포함된다.

2005~2006 참고문헌

인용 키한국어 주제·주석

PaulMcKenney2005rcutortureRCU torture testing 도입

DavidSMiller2006HashedLockingOOM 회피와 hashed locking

ThomasEHart2006alockless synchronization 회수 성능

NickPiggin2006radixtreeradix tree RCU lockless read-side

PaulEMcKenney2006bRT·embedded RCU 확장

WikipediaRCURCU 백과사전 개요

NickPiggin2006LocklessPageCacheLinux lockless page cache

PaulEMcKenney2006cSleepable RCU

RobertOlsson2006aTRASH LC-trie와 hash

ChristophHellwig2006RCU2SRCUclassic RCU 분리와 SRCU

PaulEMcKenneyRCUusagePageLinux RCU 사용 분석

PaulEMcKenneyRCUusageRawDataPageRCU 사용량 원자료

인용 키는 원문의 BibTeX 항목과 일치하며, 제목·저자·발행 정보·URL은 아래 원문 블록에 그대로 보존된다.

@unpublished{PaulMcKenney2005rcutorture
,Author="Paul E. McKenney"
,Title="{[PATCH]} {RCU} torture testing"
,month="October"
,day="1"
,year="2005"
,note="Available:
\url{https://lore.kernel.org/r/20051001182056.GA1613@us.ibm.com}
[Viewed March 14, 2006]"
,annotation={
        First rcutorture patch.
}
}

@unpublished{DavidSMiller2006HashedLocking
,Author="David S. Miller"
,Title="Re: [{PATCH}, {RFC}] {RCU} : {OOM} avoidance and lower latency"
,month="January"
,day="6"
,year="2006"
,note="Available:
\url{https://lore.kernel.org/r/20060106.231054.43576567.davem@davemloft.net}
[Viewed February 29, 2012]"
,annotation={
        David Miller's view on hashed arrays of locks: used to really
        like it, but time he saw an opportunity for this technique,
        something else always proved superior.  Partitioning or RCU.  ;-)
}
}

@conference{ThomasEHart2006a
,Author="Thomas E. Hart and Paul E. McKenney and Angela Demke Brown"
,Title="Making Lockless Synchronization Fast: Performance Implications
of Memory Reclamation"
,Booktitle="20\textsuperscript{th} {IEEE} International Parallel and
Distributed Processing Symposium"
,month="April"
,year="2006"
,day="25-29"
,address="Rhodes, Greece"
,note="Available:
\url{http://www.rdrop.com/users/paulmck/RCU/hart_ipdps06.pdf}
[Viewed April 28, 2008]"
,annotation={
        Compares QSBR, HPBR, EBR, and lock-free reference counting.
        http://www.cs.toronto.edu/~tomhart/perflab/ipdps06.tgz
}
}

@unpublished{NickPiggin2006radixtree
,Author="Nick Piggin"
,Title="[patch 3/3] radix-tree: {RCU} lockless readside"
,month="June"
,day="20"
,year="2006"
,note="Available:
\url{https://lore.kernel.org/r/20060408134707.22479.33814.sendpatchset@linux.site}
[Viewed March 25, 2008]"
,annotation={
        RCU-protected radix tree.
}
}

@Conference{PaulEMcKenney2006b
,Author="Paul E. McKenney and Dipankar Sarma and Ingo Molnar and
Suparna Bhattacharya"
,Title="Extending {RCU} for Realtime and Embedded Workloads"
,Booktitle="{Ottawa Linux Symposium}"
,Month="July"
,Year="2006"
,pages="v2 123-138"
,note="Available:
\url{https://kernel.org/doc/ols/2006/ols2006v2-pages-131-146.pdf}
\url{http://www.rdrop.com/users/paulmck/RCU/OLSrtRCU.2006.08.11a.pdf}
[Viewed January 1, 2007]"
,annotation={
        Described how to improve the -rt implementation of realtime RCU.
}
}

@unpublished{WikipediaRCU
,Author="Paul E. McKenney and Chris Purcell and Algae and Ben Schumin and
Gaius Cornelius and Qwertyus and Neil Conway and Sbw and Blainster and
Canis Rufus and Zoicon5 and Anome and Hal Eisen"
,Title="Read-Copy Update"
,month="July"
,day="8"
,year="2006"
,note="\url{https://en.wikipedia.org/wiki/Read-copy-update}"
,annotation={
        Wikipedia RCU page as of July 8 2006.
        [Viewed August 21, 2006]
}
}

@Conference{NickPiggin2006LocklessPageCache
,Author="Nick Piggin"
,Title="A Lockless Pagecache in Linux---Introduction, Progress, Performance"
,Booktitle="{Ottawa Linux Symposium}"
,Month="July"
,Year="2006"
,pages="v2 249-254"
,note="Available:
\url{https://kernel.org/doc/ols/2006/ols2006v2-pages-249-262.pdf}
[Viewed January 11, 2009]"
,annotation={
        Uses RCU-protected radix tree for a lockless page cache.
}
}

@unpublished{PaulEMcKenney2006c
,Author="Paul E. McKenney"
,Title="Sleepable {RCU}"
,month="October"
,day="9"
,year="2006"
,note="Available:
\url{http://lwn.net/Articles/202847/}
Revised:
\url{http://www.rdrop.com/users/paulmck/RCU/srcu.2007.01.14a.pdf}
[Viewed August 21, 2006]"
,annotation={
        LWN article introducing SRCU.
}
}

@unpublished{RobertOlsson2006a
,Author="Robert Olsson and Stefan Nilsson"
,Title="{TRASH}: A dynamic {LC}-trie and hash data structure"
,month="August"
,day="18"
,year="2006"
,note="\url{http://www.nada.kth.se/~snilsson/publications/TRASH/trash.pdf}"
,annotation={
        RCU-protected dynamic trie-hash combination.
        [Viewed March 4, 2011]
}
}

@unpublished{ChristophHellwig2006RCU2SRCU
,Author="Christoph Hellwig"
,Title="Re: {[-mm PATCH 1/4]} {RCU}: split classic rcu"
,month="September"
,day="28"
,year="2006"
,note="Available:
\url{https://lore.kernel.org/r/20060928142616.GA20185@infradead.org}
[Viewed March 27, 2008]"
}

@unpublished{PaulEMcKenneyRCUusagePage
,Author="Paul E. McKenney"
,Title="{RCU} {Linux} Usage"
,month="October"
,year="2006"
,note="Available:
\url{http://www.rdrop.com/users/paulmck/RCU/linuxusage.html}
[Viewed January 14, 2007]"
,annotation={
        Paul McKenney's RCU page showing graphs plotting Linux-kernel
        usage of RCU.
}
}

@unpublished{PaulEMcKenneyRCUusageRawDataPage
,Author="Paul E. McKenney"
,Title="Read-Copy Update {(RCU)} Usage in {Linux} Kernel"
,month="October"
,year="2006"
,note="Available:
\url{http://www.rdrop.com/users/paulmck/RCU/linuxusage/rculocktab.html}
[Viewed January 14, 2007]"
,annotation={
        Paul McKenney's RCU page showing Linux usage of RCU in tabular
        form, with links to corresponding cscope databases.
}
}

BibTeX: QRCU와 callback barrier

1589-1776

CPU hotplug lock, cpufreq와 SRCU latency 토론은 read-side sleep을 허용하는 RCU flavor의 비용을 드러냈다. Oleg Nesterov의 QRCU는 lockless fast path와 빠른 quiescent-state 판정을 제안했고, callback을 지나치게 미루는 부작용도 논의되었다.

K42 clustered object 자료, RCU list splice, unloadable module을 위한 `rcu_barrier()`, scalable synchronization barrier, priority boosting 연구가 이어졌다. 이들은 callback 수명과 module text 수명, reader priority inversion을 실용적으로 해결한다.

2006~2007 참고문헌

인용 키한국어 주제·주석

GauthamShenoy2006RCUrwlockCPU hotplug lock의 경량 재설계

JensAxboe2006SlowSRCUcpufreq에서 관찰한 SRCU 지연

OlegNesterov2006QRCU빠른 SRCU형 QRCU 제안

OlegNesterov2006aQRCUQRCU lockless fast path

EvgeniyPolyakov2006RCUslowdown작업 지연의 부작용

ChrisMatthews2006ClusteredObjectsRCUclustered object와 RCU

DilmaDaSilva2006K42K42의 RCU 활용

CoreyMinyard2007list:splice:rcuRCU list splicing

PaulEMcKenney2007rcubarrierRCU와 unloadable module

PeterZijlstra2007SyncBarrier확장 가능한 synchronization barrier

PaulEMcKenney2007BoostRCURCU reader priority boosting

PaulMcKenney2007QRCUpatchQRCU lockless fastpath patch

인용 키는 원문의 BibTeX 항목과 일치하며, 제목·저자·발행 정보·URL은 아래 원문 블록에 그대로 보존된다.

@unpublished{GauthamShenoy2006RCUrwlock
,Author="Gautham R. Shenoy"
,Title="[PATCH 4/5] lock\_cpu\_hotplug: Redesign - Lightweight implementation of lock\_cpu\_hotplug"
,month="October"
,year="2006"
,day=26
,note="Available:
\url{https://lore.kernel.org/r/20061026105731.GE11803@in.ibm.com}
[Viewed January 26, 2009]"
,annotation={
        RCU-based reader-writer lock that allows readers to proceed with
        no memory barriers or atomic instruction in absence of writers.
        If writer do show up, readers must of course wait as required by
        the semantics of reader-writer locking.  This is a recursive
        lock.
}
}

@unpublished{JensAxboe2006SlowSRCU
,Author="Jens Axboe"
,Title="Re: [patch] cpufreq: mark \url{cpufreq_tsc()} as
\url{core_initcall_sync}"
,month="November"
,year="2006"
,day=17
,note="Available:
\url{https://lore.kernel.org/r/20061117092925.GT7164@kernel.dk}
[Viewed May 28, 2007]"
,annotation={
        SRCU's grace periods are too slow for Jens, even after a
        factor-of-three speedup.
        Sped-up version of SRCU at https://lore.kernel.org/r/20061118002845.GF2632@us.ibm.com.
}
}

@unpublished{OlegNesterov2006QRCU
,Author="Oleg Nesterov"
,Title="Re: [patch] cpufreq: mark {\tt cpufreq\_tsc()} as
{\tt core\_initcall\_sync}"
,month="November"
,year="2006"
,day=19
,note="Available:
\url{https://lore.kernel.org/r/20061119190027.GA3676@oleg}
[Viewed May 28, 2007]"
,annotation={
        First cut of QRCU.  Expanded/corrected versions followed.
        Used to be OlegNesterov2007QRCU, now time-corrected.
}
}

@unpublished{OlegNesterov2006aQRCU
,Author="Oleg Nesterov"
,Title="Re: [RFC, PATCH 1/2] qrcu: {"quick"} srcu implementation"
,month="November"
,year="2006"
,day=30
,note="Available:
\url{https://lore.kernel.org/r/20061130015714.GC1350@oleg}
[Viewed November 26, 2008]"
,annotation={
        Expanded/corrected version of QRCU.
        Used to be OlegNesterov2007aQRCU, now time-corrected.
}
}

@unpublished{EvgeniyPolyakov2006RCUslowdown
,Author="Evgeniy Polyakov"
,Title="Badness in postponing work"
,month="December"
,year="2006"
,day=05
,note="Available:
\url{http://www.ioremap.net/node/41}
[Viewed October 28, 2008]"
,annotation={
        Using RCU as a pure delay leads to a 2.5x slowdown in skbs in
        the Linux kernel.
}
}

@inproceedings{ChrisMatthews2006ClusteredObjectsRCU
,author = {Matthews, Chris and Coady, Yvonne and Appavoo, Jonathan}
,title = {Portability events: a programming model for scalable system infrastructures}
,booktitle = {PLOS '06: Proceedings of the 3rd workshop on Programming languages and operating systems}
,year = {2006}
,isbn = {1-59593-577-0}
,pages = {11}
,location = {San Jose, California}
,doi = {http://doi.acm.org/10.1145/1215995.1216006}
,publisher = {ACM}
,address = {New York, NY, USA}
,annotation={
        Uses K42's RCU-like functionality to manage clustered-object
        lifetimes.
}
}

@article{DilmaDaSilva2006K42
,author = {Silva, Dilma Da and Krieger, Orran and Wisniewski, Robert W. and Waterland, Amos and Tam, David and Baumann, Andrew}
,title = {K42: an infrastructure for operating system research}
,journal = {SIGOPS Oper. Syst. Rev.}
,volume = {40}
,number = {2}
,year = {2006}
,issn = {0163-5980}
,pages = {34--42}
,doi = {http://doi.acm.org/10.1145/1131322.1131333}
,publisher = {ACM}
,address = {New York, NY, USA}
,annotation={
        Describes relationship of K42 generations to RCU.
}
}

# CoreyMinyard2007list_splice_rcu
@unpublished{CoreyMinyard2007list:splice:rcu
,Author="Corey Minyard and Paul E. McKenney"
,Title="{[PATCH]} add an {RCU} version of list splicing"
,month="January"
,year="2007"
,day=3
,note="Available:
\url{https://lore.kernel.org/r/20070103152738.GA16063@localdomain}
[Viewed May 28, 2007]"
,annotation={
        Patch for list_splice_rcu().
}
}

@unpublished{PaulEMcKenney2007rcubarrier
,Author="Paul E. McKenney"
,Title="{RCU} and Unloadable Modules"
,month="January"
,day="14"
,year="2007"
,note="Available:
\url{http://lwn.net/Articles/217484/}
[Viewed November 22, 2007]"
,annotation={
        LWN article introducing the rcu_barrier() primitive.
}
}

@unpublished{PeterZijlstra2007SyncBarrier
,Author="Peter Zijlstra and Ingo Molnar"
,Title="{[PATCH 3/7]} barrier: a scalable synchonisation barrier"
,month="January"
,year="2007"
,day=28
,note="Available:
\url{https://lore.kernel.org/r/20070128120509.719287000@programming.kicks-ass.net}
[Viewed March 27, 2008]"
,annotation={
        RCU-like implementation for frequent updaters and rare readers(!).
        Subsumed into QRCU.  Maybe...
}
}

@unpublished{PaulEMcKenney2007BoostRCU
,Author="Paul E. McKenney"
,Title="Priority-Boosting {RCU} Read-Side Critical Sections"
,month="February"
,day="5"
,year="2007"
,note="\url{http://lwn.net/Articles/220677/}"
,annotation={
        LWN article introducing RCU priority boosting.
        Revised:
        http://www.rdrop.com/users/paulmck/RCU/RCUbooststate.2007.04.16a.pdf
        [Viewed September 7, 2007]
}
}

@unpublished{PaulMcKenney2007QRCUpatch
,Author="Paul E. McKenney"
,Title="{[PATCH]} {QRCU} with lockless fastpath"
,month="February"
,year="2007"
,day=24
,note="Available:
\url{https://lore.kernel.org/r/20070225062349.GA17468@linux.vnet.ibm.com}
[Viewed March 27, 2008]"
,annotation={
        Patch for QRCU supplying lock-free fast path.
}
}

BibTeX: 형식 검증과 preemptible 설계

1777-1951

K42 RCU와 TRASH, concurrent page cache 자료는 다양한 자료 구조에 RCU를 적용한다. `What is RCU?` 소개와 `rcu_barrier()` 관련 자료는 API의 사용 의미를 설명하고, Promela/Spin 연구는 QRCU 최적화를 기계적으로 검증했다.

C++ data-dependency ordering 제안은 compiler와 language memory model이 RCU식 dependency를 보존하도록 atomics와 annotation을 논의했다. Preemptible RCU patch와 설계 문서는 reader 선점 상태 추적을 구체화하고, memory reclamation 성능 연구는 RCU와 다른 lockless 회수 기법을 비교했다.

2007 참고문헌

인용 키한국어 주제·주석

JonathanAppavoo2007K42RCUK42의 RCU 설계

RobertOlsson2007Trash동적 LC-trie/hash

PeterZijlstra2007ConcurrentPagecacheRCU동시 page cache

PaulEMcKenney2007whatisRCUWhat is RCU 개요

PaulEMcKenney2007QRCUspinPromela와 Spin으로 QRCU 검증

PaulEMcKenney2007WG21DDOatomicsC++ data-dependency ordering atomics

PaulEMcKenney2007WG21DDOannotationdependency ordering 함수 annotation

PaulEMcKenney2007PreemptibleRCUPatchpreemptible RCU patch series

PaulEMcKenney2007PreemptibleRCUpreemptible RCU 설계

ThomasEHart2007alockless memory reclamation 성능

MathieuDesnoyers2007call:rcu:schedNeededmarker probe와 call_rcu_sched 토론

인용 키는 원문의 BibTeX 항목과 일치하며, 제목·저자·발행 정보·URL은 아래 원문 블록에 그대로 보존된다.

@article{JonathanAppavoo2007K42RCU
,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}
,title = {Experience distributing objects in an SMMP OS}
,journal = {ACM Trans. Comput. Syst.}
,volume = {25}
,number = {3}
,year = {2007}
,issn = {0734-2071}
,pages = {6/1--6/52}
,doi = {http://doi.acm.org/10.1145/1275517.1275518}
,publisher = {ACM}
,address = {New York, NY, USA}
,annotation={
        Role of RCU in K42.
}
}

@conference{RobertOlsson2007Trash
,Author="Robert Olsson and Stefan Nilsson"
,Title="{TRASH}: A dynamic {LC}-trie and hash data structure"
,booktitle="Workshop on High Performance Switching and Routing (HPSR'07)"
,month="May"
,year="2007"
,note="Available:
\url{http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4281239}
[Viewed October 1, 2010]"
,annotation={
        RCU-protected dynamic trie-hash combination.
}
}

@conference{PeterZijlstra2007ConcurrentPagecacheRCU
,Author="Peter Zijlstra"
,Title="Concurrent Pagecache"
,Booktitle="Linux Symposium"
,month="June"
,year="2007"
,address="Ottawa, Canada"
,note="Available:
\url{http://ols.108.redhat.com/2007/Reprints/zijlstra-Reprint.pdf}
[Viewed April 14, 2008]"
,annotation={
        Page-cache modifications permitting RCU readers and concurrent
        updates.
}
}

@unpublished{PaulEMcKenney2007whatisRCU
,Author="Paul E. McKenney"
,Title="What is {RCU}?"
,year="2007"
,month="07"
,note="Available:
\url{http://www.rdrop.com/users/paulmck/RCU/whatisRCU.html}
[Viewed July 6, 2007]"
,annotation={
        Describes RCU in Linux kernel.
}
}

@unpublished{PaulEMcKenney2007QRCUspin
,Author="Paul E. McKenney"
,Title="Using {Promela} and {Spin} to verify parallel algorithms"
,month="August"
,day="1"
,year="2007"
,note="Available:
\url{http://lwn.net/Articles/243851/}
[Viewed September 8, 2007]"
,annotation={
        LWN article describing Promela and spin, and also using Oleg
        Nesterov's QRCU as an example (with Paul McKenney's fastpath).
        Merged patch at: https://lore.kernel.org/r/20070225062349.GA17468@linux.vnet.ibm.com
}
}

@unpublished{PaulEMcKenney2007WG21DDOatomics
,Author="Paul E. McKenney and Hans-J. Boehm and Lawrence Crowl"
,Title="C++ Data-Dependency Ordering: Atomics and Memory Model"
,month="August"
,day="3"
,year="2007"
,note="Available:
\url{http://open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2664.htm}
[Viewed December 7, 2009]"
,annotation={
        RCU for C++, parts 1 and 2.
}
}

@unpublished{PaulEMcKenney2007WG21DDOannotation
,Author="Paul E. McKenney and Lawrence Crowl"
,Title="C++ Data-Dependency Ordering: Function Annotation"
,month="September"
,day="18"
,year="2008"
,note="Available:
\url{http://open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2782.htm}
[Viewed December 7, 2009]"
,annotation={
        RCU for C++, part 2, updated many times.
}
}

@unpublished{PaulEMcKenney2007PreemptibleRCUPatch
,Author="Paul E. McKenney"
,Title="[PATCH RFC 0/9] {RCU}: Preemptible {RCU}"
,month="September"
,day="10"
,year="2007"
,note="Available:
\url{https://lore.kernel.org/r/20070910183004.GA3299@linux.vnet.ibm.com}
[Viewed October 25, 2007]"
,annotation={
        Final patch for preemptible RCU to -rt.  (Later patches were
        to mainline, eventually incorporated.)
}
}

@unpublished{PaulEMcKenney2007PreemptibleRCU
,Author="Paul E. McKenney"
,Title="The design of preemptible read-copy-update"
,month="October"
,day="8"
,year="2007"
,note="Available:
\url{http://lwn.net/Articles/253651/}
[Viewed October 25, 2007]"
,annotation={
        LWN article describing the design of preemptible RCU.
}
}

@article{ThomasEHart2007a
,Author="Thomas E. Hart and Paul E. McKenney and Angela Demke Brown and Jonathan Walpole"
,Title="Performance of memory reclamation for lockless synchronization"
,journal="J. Parallel Distrib. Comput."
,volume={67}
,number="12"
,year="2007"
,issn="0743-7315"
,pages="1270--1285"
,doi="http://dx.doi.org/10.1016/j.jpdc.2007.04.010"
,publisher="Academic Press, Inc."
,address="Orlando, FL, USA"
,annotation={
        Compares QSBR, HPBR, EBR, and lock-free reference counting.
        Journal version of ThomasEHart2006a.
}
}

# MathieuDesnoyers2007call_rcu_schedNeeded
@unpublished{MathieuDesnoyers2007call:rcu:schedNeeded
,Author="Mathieu Desnoyers"
,Title="Re: [patch 1/2] {Linux} Kernel Markers - Support Multiple Probes"
,month="December"
,day="20"
,year="2007"
,note="Available:
\url{https://lore.kernel.org/r/20071220142540.GB22523@Krystal}
[Viewed March 27, 2008]"
,annotation={
        Request for call_rcu_sched() and rcu_barrier_sched().
}
}


########################################################################
#
#        "What is RCU?" LWN series.
#
#        http://lwn.net/Articles/262464/ (What is RCU, Fundamentally?)
#        http://lwn.net/Articles/263130/ (What is RCU's Usage?)
#        http://lwn.net/Articles/264090/ (What is RCU's API?)

BibTeX: What is RCU, dynticks, hierarchical RCU

1952-2178

LWN의 세 편은 RCU의 근본 개념, 사용 패턴, API를 단계적으로 설명한다. dependency ordering과 compiler instrumentation 논의는 `rcu_dereference()`가 의존성을 지키기 위해 필요한 언어·compiler 제약을 다룬다.

Dynticks와 preemptible RCU 통합, real-time RCU, callback 처리 state machine, IRQ/NMI 상태 추적은 tickless idle과 낮은 지연을 함께 달성하려는 작업이다. Cyclic search와 hierarchical RCU는 순환 구조의 일관된 탐색과 많은 CPU에서 grace-period 상태를 계층화하는 방법을 제시한다.

2008 참고문헌

인용 키한국어 주제·주석

PaulEMcKenney2007WhatIsRCUFundamentallyRCU의 근본 개념

PaulEMcKenney2008WhatIsRCUUsageRCU 사용 패턴

PaulEMcKenney2008WhatIsRCUAPIRCU API

SteveRostedt2008dyntickRCUpatchdynticks와 preempt RCU 지원

PaulEMcKenney2008LKMLDependencyOrderingcompiler와 dependency ordering

PaulEMcKenney2008BeijingLinux에 기술을 도입하는 과정

PaulEMcKenney2008dynticksRCUdynticks와 preemptible RCU 통합 검증

DinakarGuniguntala2008IBMSysJshared-memory SMP의 real-time RCU

LaiJiangshan2008NewClassicAlgorithmclassic callback 처리 새 알고리즘

PaulEMcKenney2008RCUOSRLinux RCU 도입 사례사

ManfredSpraul2008StateMachineRCUstate-machine 기반 RCU

ManfredSpraul2008dyntickIRQNMIdyntick IRQ/NMI 상태 처리

PaulEMcKenney2008cyclicRCURCU의 일관된 순환 탐색

PaulEMcKenney2008HierarchicalRCUHierarchical RCU 설계

인용 키는 원문의 BibTeX 항목과 일치하며, 제목·저자·발행 정보·URL은 아래 원문 블록에 그대로 보존된다.

@unpublished{PaulEMcKenney2007WhatIsRCUFundamentally
,Author="Paul E. McKenney and Jonathan Walpole"
,Title="What is {RCU}, Fundamentally?"
,month="December"
,day="17"
,year="2007"
,note="Available:
\url{http://lwn.net/Articles/262464/}
[Viewed December 27, 2007]"
,annotation={
        Lays out the three basic components of RCU: (1) publish-subscribe,
        (2) wait for pre-existing readers to complete, and (2) maintain
        multiple versions.
}
}

@unpublished{PaulEMcKenney2008WhatIsRCUUsage
,Author="Paul E. McKenney"
,Title="What is {RCU}? Part 2: Usage"
,month="January"
,day="4"
,year="2008"
,note="Available:
\url{http://lwn.net/Articles/263130/}
[Viewed January 4, 2008]"
,annotation={
        Lays out six uses of RCU:
        1. RCU is a Reader-Writer Lock Replacement
        2. RCU is a Restricted Reference-Counting Mechanism
        3. RCU is a Bulk Reference-Counting Mechanism
        4. RCU is a Poor Man's Garbage Collector
        5. RCU is a Way of Providing Existence Guarantees
        6. RCU is a Way of Waiting for Things to Finish
}
}

@unpublished{PaulEMcKenney2008WhatIsRCUAPI
,Author="Paul E. McKenney"
,Title="{RCU} part 3: the {RCU} {API}"
,month="January"
,day="17"
,year="2008"
,note="Available:
\url{http://lwn.net/Articles/264090/}
[Viewed January 10, 2008]"
,annotation={
        Gives an overview of the Linux-kernel RCU API and a brief annotated RCU
        bibliography.
}
}

#
#        "What is RCU?" LWN series.
#
########################################################################


@unpublished{SteveRostedt2008dyntickRCUpatch
,Author="Steven Rostedt and Paul E. McKenney"
,Title="{[PATCH]} add support for dynamic ticks and preempt rcu"
,month="January"
,day="29"
,year="2008"
,note="Available:
\url{https://lore.kernel.org/r/Pine.LNX.4.58.0801291113350.20371@gandalf.stny.rr.com}
[Viewed March 27, 2008]"
,annotation={
        Patch that prevents preemptible RCU from unnecessarily waking
        up dynticks-idle CPUs.
}
}

@unpublished{PaulEMcKenney2008LKMLDependencyOrdering
,Author="Paul E. McKenney"
,Title="Re: [PATCH 02/22 -v7] Add basic support for gcc profiler instrumentation"
,month="February"
,day="1"
,year="2008"
,note="Available:
\url{https://lore.kernel.org/r/20080202214124.GA28612@linux.vnet.ibm.com}
[Viewed October 18, 2008]"
,annotation={
        Explanation of compilers violating dependency ordering.
}
}

@Conference{PaulEMcKenney2008Beijing
,Author="Paul E. McKenney"
,Title="Introducing Technology Into {Linux} Or:
Introducing your technology Into {Linux} will require introducing a
lot of {Linux} into your technology!!!"
,Booktitle="2008 Linux Developer Symposium - China"
,Publisher="OSS China"
,Month="February"
,Year="2008"
,Address="Beijing, China"
,note="Available:
\url{http://www.rdrop.com/users/paulmck/RCU/TechIntroLinux.2008.02.19a.pdf}
[Viewed August 12, 2008]"
}

@unpublished{PaulEMcKenney2008dynticksRCU
,Author="Paul E. McKenney and Steven Rostedt"
,Title="Integrating and Validating dynticks and Preemptable RCU"
,month="April"
,day="24"
,year="2008"
,note="Available:
\url{http://lwn.net/Articles/279077/}
[Viewed April 24, 2008]"
,annotation={
        Describes use of Promela and Spin to validate (and fix!) the
        dynticks/RCU interface.
}
}

@article{DinakarGuniguntala2008IBMSysJ
,author="D. Guniguntala and P. E. McKenney and J. Triplett and J. Walpole"
,title="The read-copy-update mechanism for supporting real-time applications on shared-memory multiprocessor systems with {Linux}"
,Year="2008"
,Month="May"
,journal="IBM Systems Journal"
,volume="47"
,number="2"
,pages="221-236"
,annotation={
        RCU, realtime RCU, sleepable RCU, performance.
        http://www.research.ibm.com/journal/sj/472/guniguntala.pdf
        [Viewed April 24, 2008]
}
}

@unpublished{LaiJiangshan2008NewClassicAlgorithm
,Author="Lai Jiangshan"
,Title="[{RFC}][{PATCH}] rcu classic: new algorithm for callbacks-processing"
,month="June"
,day="3"
,year="2008"
,note="Available:
\url{https://lore.kernel.org/r/4844BE83.5010401@cn.fujitsu.com}
[Viewed December 10, 2008]"
,annotation={
        Updated RCU classic algorithm.  Introduced multi-tailed list
        for RCU callbacks and also pulling common code into
        __call_rcu().
}
}

@article{PaulEMcKenney2008RCUOSR
,author="Paul E. McKenney and Jonathan Walpole"
,title="Introducing technology into the {Linux} kernel: a case study"
,Year="2008"
,journal="SIGOPS Oper. Syst. Rev."
,volume="42"
,number="5"
,pages="4--17"
,issn="0163-5980"
,doi={http://doi.acm.org/10.1145/1400097.1400099}
,publisher="ACM"
,address="New York, NY, USA"
,annotation={
        Linux changed RCU to a far greater degree than RCU has changed Linux.
        http://portal.acm.org/citation.cfm?doid=1400097.1400099
}
}

@unpublished{ManfredSpraul2008StateMachineRCU
,Author="Manfred Spraul"
,Title="[{RFC}, {PATCH}] state machine based rcu"
,month="August"
,day="21"
,year="2008"
,note="Available:
\url{https://lore.kernel.org/r/48AD8969.7060900@colorfullife.com}
[Viewed December 8, 2008]"
,annotation={
        State-based RCU.  One key thing that this patch does is to
        separate the dynticks handling of NMIs and IRQs.
}
}

@unpublished{ManfredSpraul2008dyntickIRQNMI
,Author="Manfred Spraul"
,Title="Re: [{RFC}, {PATCH}] v4 scalable classic {RCU} implementation"
,month="September"
,day="6"
,year="2008"
,note="Available:
\url{https://lore.kernel.org/r/48C2B1D2.5070801@colorfullife.com}
[Viewed December 8, 2008]"
,annotation={
        Manfred notes a fix required to my attempt to separate irq
        and NMI processing for hierarchical RCU's dynticks interface.
}
}

# Was PaulEMcKenney2011cyclicRCU
@techreport{PaulEMcKenney2008cyclicRCU
,author="Paul E. McKenney"
,title="Efficient Support of Consistent Cyclic Search With Read-Copy Update"
,institution="US Patent and Trademark Office"
,address="Washington, DC"
,year="2008"
,number="US Patent 7,426,511"
,month="September"
,pages="23"
,annotation={
        Maintains an additional level of indirection to allow
        readers to confine themselves to the desired snapshot of the
        data structure.  Only permits one update at a time.
}
}

@unpublished{PaulEMcKenney2008HierarchicalRCU
,Author="Paul E. McKenney"
,Title="Hierarchical {RCU}"
,month="November"
,day="3"
,year="2008"
,note="\url{http://lwn.net/Articles/305782/}"
,annotation={
        RCU with combining-tree-based grace-period detection,
        permitting it to handle thousands of CPUs.
        [Viewed November 6, 2008]
}
}

BibTeX: userspace, TINY, expedited, relativistic programming

2179-2404

2009년에는 작은 시스템을 위한 bloatwatch/TINY_RCU, 악의적 userspace RCU로 알고리즘을 시험하는 방법, liburcu 계열 구현이 등장했다. Expedited GP는 큰 비용을 지불하고 빠르게 reader 종료를 강제하는 big hammer를 제공했다.

Relativistic programming은 RCU ordering 원리를 resizable concurrent hash에 적용했다. Deterministic synchronization, Heisenbug 추적, formal verification 모델, pre-publication user-level RCU 연구는 RCU를 성능 기법에서 분석 가능한 동시성 모델로 확장했다.

2009 참고문헌

인용 키한국어 주제·주석

PaulEMcKenney2009BloatwatchRCU작은 RCU 구현 실험

PaulEMcKenney2009MaliciousURCU악의적 userspace RCU를 이용한 torture

MathieuDesnoyers2009URCULinux userspace RCU tree

PaulEMcKenney2009LWNBloatWatchRCUBloatwatch RCU 설명

EvgeniyPolyakov2009EllipticsNetworkElliptics 분산 network

PaulEMcKenney2009expeditedRCUexpedited big-hammer GP

PaulEMcKenney2009fastRTRCU단순화한 preemptible RT RCU

JoshTriplett2009RPHashrelativistic concurrent hash

MathieuDesnoyersPhDlow-impact OS tracing과 userspace RCU

RelativisticProgrammingWikiRelativistic Programming 자료

PaulEMcKenney2009DeterministicRCUmulticore deterministic synchronization

PaulEMcKenney2009HuntingHeisenbugsHeisenbug 추적

MathieuDesnoyers2009defer:rcurcu_head 크기 축소

MathieuDesnoyers2009VerifPrePubparallel algorithm 형식 검증 모델

MathieuDesnoyers2009URCUPrePubuser-level RCU 구현 논문

HariKannan2009DynamicAnalysisRCU동적 분석에 RCU 적용

인용 키는 원문의 BibTeX 항목과 일치하며, 제목·저자·발행 정보·URL은 아래 원문 블록에 그대로 보존된다.

@unpublished{PaulEMcKenney2009BloatwatchRCU
,Author="Paul E. McKenney"
,Title="Re: [PATCH fyi] RCU: the bloatwatch edition"
,month="January"
,day="14"
,year="2009"
,note="Available:
\url{https://lore.kernel.org/r/20090114202044.GJ6734@linux.vnet.ibm.com}
[Viewed January 15, 2009]"
,annotation={
        Small-footprint implementation of RCU for uniprocessor
        embedded applications -- and also for exposition purposes.
}
}

@conference{PaulEMcKenney2009MaliciousURCU
,Author="Paul E. McKenney"
,Title="Using a Malicious User-Level {RCU} to Torture {RCU}-Based Algorithms"
,Booktitle="linux.conf.au 2009"
,month="January"
,year="2009"
,address="Hobart, Australia"
,note="Available:
\url{http://www.rdrop.com/users/paulmck/RCU/urcutorture.2009.01.22a.pdf}
[Viewed February 2, 2009]"
,annotation={
        Realtime RCU and torture-testing RCU uses.
}
}

@unpublished{MathieuDesnoyers2009URCU
,Author="Mathieu Desnoyers"
,Title="[{RFC} git tree] Userspace {RCU} (urcu) for {Linux}"
,month="February"
,day="5"
,year="2009"
,note="\url{http://lttng.org/urcu}"
,annotation={
        Mathieu Desnoyers's user-space RCU implementation.
        git://lttng.org/userspace-rcu.git
        http://lttng.org/cgi-bin/gitweb.cgi?p=userspace-rcu.git
        http://lttng.org/urcu
        https://lore.kernel.org/r/20090206030543.GB8560@Krystal
}
}

@unpublished{PaulEMcKenney2009LWNBloatWatchRCU
,Author="Paul E. McKenney"
,Title="{RCU}: The {Bloatwatch} Edition"
,month="March"
,day="17"
,year="2009"
,note="Available:
\url{http://lwn.net/Articles/323929/}
[Viewed March 20, 2009]"
,annotation={
        Uniprocessor assumptions allow simplified RCU implementation.
}
}

@unpublished{EvgeniyPolyakov2009EllipticsNetwork
,Author="Evgeniy Polyakov"
,Title="The Elliptics Network"
,month="April"
,day="17"
,year="2009"
,note="Available:
\url{http://www.ioremap.net/projects/elliptics}
[Viewed April 30, 2009]"
,annotation={
        Distributed hash table with transactions, using elliptic
        hash functions to distribute data.
}
}

@unpublished{PaulEMcKenney2009expeditedRCU
,Author="Paul E. McKenney"
,Title="[{PATCH} -tip 0/3] expedited 'big hammer' {RCU} grace periods"
,month="June"
,day="25"
,year="2009"
,note="Available:
\url{https://lore.kernel.org/r/20090625160706.GA9467@linux.vnet.ibm.com}
[Viewed August 16, 2009]"
,annotation={
        First posting of expedited RCU to be accepted into -tip.
}
}

@unpublished{PaulEMcKenney2009fastRTRCU
,Author="Paul E. McKenney"
,Title="[{PATCH} {RFC} -tip 0/4] {RCU} cleanups and simplified preemptable {RCU}"
,month="July"
,day="23"
,year="2009"
,note="Available:
\url{https://lore.kernel.org/r/20090724001429.GA17374@linux.vnet.ibm.com}
[Viewed August 15, 2009]"
,annotation={
        First posting of simple and fast preemptible RCU.
}
}

@unpublished{JoshTriplett2009RPHash
,Author="Josh Triplett"
,Title="Scalable concurrent hash tables via relativistic programming"
,month="September"
,year="2009"
,note="Linux Plumbers Conference presentation"
,annotation={
        RP fun with hash tables.
        Superseded by JoshTriplett2010RPHash
}
}

@phdthesis{MathieuDesnoyersPhD
, title  = "Low-Impact Operating System Tracing"
, author = "Mathieu Desnoyers"
, school = "Ecole Polytechnique de Montr\'{e}al"
, month  = "December"
, year   = 2009
,note="Available:
\url{http://www.lttng.org/pub/thesis/desnoyers-dissertation-2009-12.pdf}
[Viewed December 9, 2009]"
,annotation={
        Chapter 6 (page 97) covers user-level RCU.
}
}

@unpublished{RelativisticProgrammingWiki
,Author="Josh Triplett and Paul E. McKenney and Jonathan Walpole"
,Title="Relativistic Programming"
,month="September"
,year="2009"
,note="Available:
\url{http://wiki.cs.pdx.edu/rp/}
[Viewed December 9, 2009]"
,annotation={
        Main Relativistic Programming Wiki.
}
}

@conference{PaulEMcKenney2009DeterministicRCU
,Author="Paul E. McKenney"
,Title="Deterministic Synchronization in Multicore Systems: the Role of {RCU}"
,Booktitle="Eleventh Real Time Linux Workshop"
,month="September"
,year="2009"
,address="Dresden, Germany"
,note="Available:
\url{http://www.rdrop.com/users/paulmck/realtime/paper/DetSyncRCU.2009.08.18a.pdf}
[Viewed January 14, 2009]"
}

@unpublished{PaulEMcKenney2009HuntingHeisenbugs
,Author="Paul E. McKenney"
,Title="Hunting Heisenbugs"
,month="November"
,year="2009"
,day="1"
,note="Available:
\url{http://paulmck.livejournal.com/14639.html}
[Viewed June 4, 2010]"
,annotation={
        Day-one bug in Tree RCU that took forever to track down.
}
}

@unpublished{MathieuDesnoyers2009defer:rcu
,Author="Mathieu Desnoyers"
,Title="Kernel RCU: shrink the size of the struct rcu\_head"
,month="December"
,year="2009"
,note="Available:
\url{https://lore.kernel.org/r/20091018232918.GA7385@Krystal}
[Viewed December 29, 2009]"
,annotation={
        Mathieu proposed defer_rcu() with fixed-size per-thread pool
        of RCU callbacks.
}
}

@unpublished{MathieuDesnoyers2009VerifPrePub
,Author="Mathieu Desnoyers and Paul E. McKenney and Michel R. Dagenais"
,Title="Multi-Core Systems Modeling for Formal Verification of Parallel Algorithms"
,month="December"
,year="2009"
,note="Submitted to IEEE TPDS"
,annotation={
        OOMem model for Mathieu's user-level RCU mechanical proof of
        correctness.
}
}

@unpublished{MathieuDesnoyers2009URCUPrePub
,Author="Mathieu Desnoyers and Paul E. McKenney and Alan Stern and Michel R. Dagenais and Jonathan Walpole"
,Title="User-Level Implementations of Read-Copy Update"
,month="December"
,year="2010"
,url={\url{http://www.computer.org/csdl/trans/td/2012/02/ttd2012020375-abs.html}}
,annotation={
        RCU overview, desiderata, semi-formal semantics, user-level RCU
        usage scenarios, three classes of RCU implementation, wait-free
        RCU updates, RCU grace-period batching, update overhead,
        http://www.rdrop.com/users/paulmck/RCU/urcu-main-accepted.2011.08.30a.pdf
        http://www.rdrop.com/users/paulmck/RCU/urcu-supp-accepted.2011.08.30a.pdf
        Superseded by MathieuDesnoyers2012URCU.
}
}

@inproceedings{HariKannan2009DynamicAnalysisRCU
,author = {Kannan, Hari}
,title = {Ordering decoupled metadata accesses in multiprocessors}
,booktitle = {MICRO 42: Proceedings of the 42nd Annual IEEE/ACM International Symposium on Microarchitecture}
,year = {2009}
,isbn = {978-1-60558-798-1}
,pages = {381--390}
,location = {New York, New York}
,doi = {http://doi.acm.org/10.1145/1669112.1669161}
,publisher = {ACM}
,address = {New York, NY, USA}
,annotation={
        Uses RCU to protect metadata used in dynamic analysis.
}
}

BibTeX: TREE_RCU, lockdep, scalable hash

2405-2632

TREE_RCU 기반 preemptible 구현은 최적화를 통해 코드를 단순화했고 lockdep-RCU는 잘못된 read-side 문맥을 동적으로 검출했다. KVM vCPU 수 확장, bridge IGMP snooping hash, OpenSolaris RCU 연구는 여러 subsystem과 OS에서 적용 범위를 넓혔다.

Relativistic hash는 node를 원자적으로 옮기며 resize하고, 2010 RCU API 문서는 당시 interface를 정리했다. 2011년 lockless dentry search가 mainline에 들어왔고 transactional memory와 RCU를 결합한 red-black tree, parallel update를 허용하는 cyclic search가 연구되었다.

Linux 3.0 RCU 문제 회고, LWN의 lock 분류, compiler instrumentation 기반 runtime verification은 구현 실패를 분석하고 실제 kernel 동시성 오류를 찾는 도구를 제공한다.

2010~2011 참고문헌

인용 키한국어 주제·주석

PaulEMcKenney2010SimpleOptRCU최적화를 통한 단순 preemptible RCU

PaulEMcKenney2010LockdepRCULockdep-RCU

AviKivity2010KVM2RCUKVM 최대 vCPU 확장과 RCU

HerbertXu2010RCUResizeHashbridge IGMP snooping resizable hash

AbhinavDuggal2010MastersRedflag를 이용한 data race 중지

JoshTriplett2010RPHash원자적 node 이동 concurrent hash

PaulEMcKenney2010RCUAPI2010 RCU API

AndrejPodzimek2010mastersOpenSolaris용 RCU

LinusTorvalds2011Linux2:6:38:rc1:NPigginVFSLinux 2.6.38 lockless dentry search

JoshTriplett2011RPScalableCorrectOrdering확장 가능한 relativistic ordering

PhilHoward2011RCUTMRBTreeRCU와 transactional-memory red-black tree

PaulEMcKenney2011cyclicparallelRCUparallel update를 포함한 cyclic search

Triplett:2011:RPHashrelativistic resizable hash 정식 논문

PaulEMcKenney2011RCU3.0trainwreckLinux 3.0 RCU 문제 회고

NeilBrown2011MeetTheLockersLWN의 kernel locking 도구 비교

Seyster:2011:RFA:2075416.2075425RCU fault의 runtime analysis

인용 키는 원문의 BibTeX 항목과 일치하며, 제목·저자·발행 정보·URL은 아래 원문 블록에 그대로 보존된다.

@conference{PaulEMcKenney2010SimpleOptRCU
,Author="Paul E. McKenney"
,Title="Simplicity Through Optimization"
,Booktitle="linux.conf.au 2010"
,month="January"
,year="2010"
,address="Wellington, New Zealand"
,note="Available:
\url{http://www.rdrop.com/users/paulmck/RCU/SimplicityThruOptimization.2010.01.21f.pdf}
[Viewed October 10, 2010]"
,annotation={
        TREE_PREEMPT_RCU optimizations greatly simplified the old
        PREEMPT_RCU implementation.
}
}

@unpublished{PaulEMcKenney2010LockdepRCU
,Author="Paul E. McKenney"
,Title="Lockdep-{RCU}"
,month="February"
,year="2010"
,day="1"
,note="\url{https://lwn.net/Articles/371986/}"
,annotation={
        CONFIG_PROVE_RCU, or at least an early version.
        [Viewed June 4, 2010]
}
}

@unpublished{AviKivity2010KVM2RCU
,Author="Avi Kivity"
,Title="[{PATCH} 37/40] {KVM}: Bump maximum vcpu count to 64"
,month="February"
,year="2010"
,note="Available:
\url{http://www.mail-archive.com/kvm@vger.kernel.org/msg28640.html}
[Viewed March 20, 2010]"
,annotation={
        Use of RCU permits KVM to increase the size of guest OSes from
        16 CPUs to 64 CPUs.
}
}

@unpublished{HerbertXu2010RCUResizeHash
,Author="Herbert Xu"
,Title="bridge: Add core IGMP snooping support"
,month="February"
,year="2010"
,note="Available:
\url{http://thread.gmane.org/gmane.linux.network/153338}
[Viewed June 9, 2014]"
,annotation={
        Use a pair of list_head structures to support RCU-protected
        resizable hash tables.
}
}

@mastersthesis{AbhinavDuggal2010Masters
,author="Abhinav Duggal"
,title="Stopping Data Races Using Redflag"
,school="Stony Brook University"
,year="2010"
,annotation={
        Data-race detector incorporating RCU.
        http://www.filesystems.org/docs/abhinav-thesis/abhinav_thesis.pdf
}
}

@article{JoshTriplett2010RPHash
,author="Josh Triplett and Paul E. McKenney and Jonathan Walpole"
,title="Scalable Concurrent Hash Tables via Relativistic Programming"
,journal="ACM Operating Systems Review"
,year=2010
,volume=44
,number=3
,month="July"
,annotation={
        RP fun with hash tables.
        http://portal.acm.org/citation.cfm?id=1842733.1842750
}
}

@unpublished{PaulEMcKenney2010RCUAPI
,Author="Paul E. McKenney"
,Title="The {RCU} {API}, 2010 Edition"
,month="December"
,day="8"
,year="2010"
,note="\url{http://lwn.net/Articles/418853/}"
,annotation={
        Includes updated software-engineering features.
        [Viewed December 8, 2010]
}
}

@mastersthesis{AndrejPodzimek2010masters
,author="Andrej Podzimek"
,title="Read-Copy-Update for OpenSolaris"
,school="Charles University in Prague"
,year="2010"
,note="Available:
\url{https://andrej.podzimek.org/thesis.pdf}
[Viewed January 31, 2011]"
,annotation={
        Reviews RCU implementations and creates a few for OpenSolaris.
        Drives quiescent-state detection from RCU read-side primitives,
        in a manner roughly similar to that of Jim Houston.
}
}

@unpublished{LinusTorvalds2011Linux2:6:38:rc1:NPigginVFS
,Author="Linus Torvalds"
,Title="Linux 2.6.38-rc1"
,month="January"
,year="2011"
,note="Available:
\url{https://lore.kernel.org/r/AANLkTimajU0x1v6y3rH2+jr-bZ=tNLs1S_agXdGGAa3S@mail.gmail.com}
[Viewed March 4, 2011]"
,annotation={
        "The RCU-based name lookup is at the other end of the spectrum - the
        absolute anti-gimmick. It's some seriously good stuff, and gets rid of
        the last main global lock that really tends to hurt some kernel loads.
        The dentry lock is no longer a big serializing issue. What's really
        nice about it is that it actually improves performance a lot even for
        single-threaded loads (on an SMP kernel), because it gets rid of some
        of the most expensive parts of path component lookup, which was the
        d_lock on every component lookup. So I'm seeing improvements of 30-50%
        on some seriously pathname-lookup intensive loads."
}
}

@techreport{JoshTriplett2011RPScalableCorrectOrdering
,author = {Josh Triplett and Philip W. Howard and Paul E. McKenney and Jonathan Walpole}
,title = {Scalable Correct Memory Ordering via Relativistic Programming}
,year = {2011}
,number = {11-03}
,institution = {Portland State University}
,note = {\url{http://www.cs.pdx.edu/pdfs/tr1103.pdf}}
}

@inproceedings{PhilHoward2011RCUTMRBTree
,author = {Philip W. Howard and Jonathan Walpole}
,title = {A Relativistic Enhancement to Software Transactional Memory}
,booktitle = {Proceedings of the 3rd USENIX conference on Hot topics in parallelism}
,series = {HotPar'11}
,year = {2011}
,location = {Berkeley, CA}
,pages = {1--6}
,numpages = {6}
,url = {http://www.usenix.org/event/hotpar11/tech/final_files/Howard.pdf}
,publisher = {USENIX Association}
,address = {Berkeley, CA, USA}
}

@techreport{PaulEMcKenney2011cyclicparallelRCU
,author="Paul E. McKenney and Jonathan Walpole"
,title="Efficient Support of Consistent Cyclic Search With Read-Copy Update and Parallel Updates"
,institution="US Patent and Trademark Office"
,address="Washington, DC"
,year="2011"
,number="US Patent 7,953,778"
,month="May"
,pages="34"
,annotation={
        Maintains an array of generation numbers to track in-flight
        updates and keeps an additional level of indirection to allow
        readers to confine themselves to the desired snapshot of the
        data structure.
}
}

@inproceedings{Triplett:2011:RPHash
,author = {Triplett, Josh and McKenney, Paul E. and Walpole, Jonathan}
,title = {Resizable, Scalable, Concurrent Hash Tables via Relativistic Programming}
,booktitle = {Proceedings of the 2011 USENIX Annual Technical Conference}
,month = {June}
,year = {2011}
,pages = {145--158}
,numpages = {14}
,url={http://www.usenix.org/event/atc11/tech/final_files/Triplett.pdf}
,publisher = {The USENIX Association}
,address = {Portland, OR USA}
}

@unpublished{PaulEMcKenney2011RCU3.0trainwreck
,Author="Paul E. McKenney"
,Title="3.0 and {RCU:} what went wrong"
,month="July"
,day="27"
,year="2011"
,note="\url{http://lwn.net/Articles/453002/}"
,annotation={
        Analysis of the RCU trainwreck in Linux kernel 3.0.
        [Viewed July 27, 2011]
}
}

@unpublished{NeilBrown2011MeetTheLockers
,Author="Neil Brown"
,Title="Meet the {Lockers}"
,month="August"
,day="3"
,year="2011"
,note="Available:
\url{http://lwn.net/Articles/453685/}
[Viewed September 2, 2011]"
,annotation={
        The Locker family as an analogy for locking, reference counting,
        RCU, and seqlock.
}
}

@inproceedings{Seyster:2011:RFA:2075416.2075425
,author = {Seyster, Justin and Radhakrishnan, Prabakar and Katoch, Samriti and Duggal, Abhinav and Stoller, Scott D. and Zadok, Erez}
,title = {Redflag: a framework for analysis of Kernel-level concurrency}
,booktitle = {Proceedings of the 11th international conference on Algorithms and architectures for parallel processing - Volume Part I}
,series = {ICA3PP'11}
,year = {2011}
,isbn = {978-3-642-24649-4}
,location = {Melbourne, Australia}
,pages = {66--79}
,numpages = {14}
,url = {http://dl.acm.org/citation.cfm?id=2075416.2075425}
,acmid = {2075425}
,publisher = {Springer-Verlag}
,address = {Berlin, Heidelberg}
}

BibTeX: causal ordering과 형식 검증

2633-2812

Josh Triplett의 박사 논문은 scalable concurrent 자료 구조를 위한 relativistic causal ordering을 memory model로 정리했다. Desnoyers의 user-level RCU 논문은 높은 수준 학술지에서 userspace 구현과 성능을 체계적으로 제시했다.

Linux `mmap_sem` 확장, battery-powered device에서의 RCU, crowd simulation, `ACCESS_ONCE()`, no-callback CPU와 callback relocation은 RCU를 전력·latency·응용 simulation·compiler 접근 제어까지 확장한다.

Separation logic 기반 grace-period 검증은 highly concurrent algorithm을 형식적으로 증명하고, kernel RCU 사용 10년 회고는 API와 사용 패턴의 성숙을 보여 준다. `NoTinyPreempt` 자료는 작은 preemptible 전용 flavor를 없애 구현을 단순화하는 방향을 설명한다.

2012~2013 참고문헌

인용 키한국어 주제·주석

JoshTriplettPhDrelativistic causal ordering 박사 논문

MathieuDesnoyers2012URCUuser-level RCU journal 논문

AustinClements2012RCULinux:mmapsemLinux mmap semaphore 확장과 RCU

PaulEMcKenney2012ELCbatterybattery-powered device의 RCU

GuillermoVigueras2012RCUCrowdcrowd simulation의 userspace RCU

JonCorbet2012ACCESS:ONCEACCESS_ONCE 의미와 사용

AlexeyGotsman2012VerifyGraceExtendedgrace 기반 동시 알고리즘 형식 검증

PaulMcKenney2012RCUUsageLinux RCU 사용 10년 회고

JonCorbet2012NOCBRCU callback relocation과 no-CB CPU

JustinSeyster2012PhDcompiler instrumentation 기반 kernel concurrency 검증

PaulEMcKenney2013RCUUsageLinux kernel RCU 사용의 성숙

AlexeyGotsman2013ESOPRCUseparation logic 기반 RCU 검증

PaulEMcKenney2013NoTinyPreemptTINY_PREEMPT 제거와 RCU 단순화

인용 키는 원문의 BibTeX 항목과 일치하며, 제목·저자·발행 정보·URL은 아래 원문 블록에 그대로 보존된다.

@phdthesis{JoshTriplettPhD
,author="Josh Triplett"
,title="Relativistic Causal Ordering: A Memory Model for Scalable Concurrent Data Structures"
,school="Portland State University"
,year="2012"
,annotation={
        RCU-protected hash tables, barriers vs. read-side traversal order.
        .
        If the updater is making changes in the opposite direction from
        the read-side traversal order, the updater need only execute a
        memory-barrier instruction, but if in the same direction, the
        updater needs to wait for a grace period between the individual
        updates.
}
}

@article{MathieuDesnoyers2012URCU
,Author="Mathieu Desnoyers and Paul E. McKenney and Alan Stern and Michel R. Dagenais and Jonathan Walpole"
,Title="User-Level Implementations of Read-Copy Update"
,journal="IEEE Transactions on Parallel and Distributed Systems"
,volume={23}
,year="2012"
,issn="1045-9219"
,pages="375-382"
,doi="http://doi.ieeecomputersociety.org/10.1109/TPDS.2011.159"
,publisher="IEEE Computer Society"
,address="Los Alamitos, CA, USA"
,annotation={
        RCU overview, desiderata, semi-formal semantics, user-level RCU
        usage scenarios, three classes of RCU implementation, wait-free
        RCU updates, RCU grace-period batching, update overhead,
        http://www.rdrop.com/users/paulmck/RCU/urcu-main-accepted.2011.08.30a.pdf
        http://www.rdrop.com/users/paulmck/RCU/urcu-supp-accepted.2011.08.30a.pdf
        http://www.computer.org/cms/Computer.org/dl/trans/td/2012/02/extras/ttd2012020375s.pdf
}
}

@inproceedings{AustinClements2012RCULinux:mmapsem
,author = {Austin Clements and Frans Kaashoek and Nickolai Zeldovich}
,title = {Scalable Address Spaces Using {RCU} Balanced Trees}
,booktitle = {Architectural Support for Programming Languages and Operating Systems (ASPLOS 2012)}
,month = {March}
,year = {2012}
,pages = {199--210}
,numpages = {12}
,publisher = {ACM}
,address = {London, UK}
,url="http://people.csail.mit.edu/nickolai/papers/clements-bonsai.pdf"
}

@unpublished{PaulEMcKenney2012ELCbattery
,Author="Paul E. McKenney"
,Title="Making {RCU} Safe For Battery-Powered Devices"
,month="February"
,day="15"
,year="2012"
,note="Available:
\url{http://www.rdrop.com/users/paulmck/RCU/RCUdynticks.2012.02.15b.pdf}
[Viewed March 1, 2012]"
,annotation={
        RCU_FAST_NO_HZ, round 2.
}
}

@article{GuillermoVigueras2012RCUCrowd
,author = {Vigueras, Guillermo and Ordu\~{n}a, Juan M. and Lozano, Miguel}
,day = {25}
,doi = {10.1007/s11227-012-0766-x}
,issn = {0920-8542}
,journal = {The Journal of Supercomputing}
,keywords = {linux, simulation}
,month = apr
,posted-at = {2012-05-03 09:12:04}
,priority = {2}
,title = {{A Read-Copy Update based parallel server for distributed crowd simulations}}
,url = {http://dx.doi.org/10.1007/s11227-012-0766-x}
,year = {2012}
}


@unpublished{JonCorbet2012ACCESS:ONCE
,Author="Jon Corbet"
,Title="{ACCESS\_ONCE()}"
,month="August"
,day="1"
,year="2012"
,note="\url{http://lwn.net/Articles/508991/}"
,annotation={
        A couple of simple specific compiler optimizations that motivate
        ACCESS_ONCE().
}
}

@unpublished{AlexeyGotsman2012VerifyGraceExtended
,Author="Alexey Gotsman and Noam Rinetzky and Hongseok Yang"
,Title="Verifying Highly Concurrent Algorithms with Grace (extended version)"
,month="July"
,day="10"
,year="2012"
,note="\url{http://software.imdea.org/~gotsman/papers/recycling-esop13-ext.pdf}"
,annotation={
        Separation-logic formulation of RCU uses.
}
}

@unpublished{PaulMcKenney2012RCUUsage
,Author="Paul E. McKenney and Silas Boyd-Wickizer and Jonathan Walpole"
,Title="{RCU} Usage In the Linux Kernel: One Decade Later"
,month="September"
,day="17"
,year="2012"
,url=http://rdrop.com/users/paulmck/techreports/survey.2012.09.17a.pdf
,note="Technical report paulmck.2012.09.17"
,annotation={
        Overview of the first variant of no-CBs CPUs for RCU.
}
}

@unpublished{JonCorbet2012NOCB
,Author="Jon Corbet"
,Title="Relocating RCU callbacks"
,month="October"
,day="31"
,year="2012"
,note="\url{http://lwn.net/Articles/522262/}"
,annotation={
        Overview of the first variant of no-CBs CPUs for RCU.
}
}

@phdthesis{JustinSeyster2012PhD
,author="Justin Seyster"
,title="Runtime Verification of Kernel-Level Concurrency Using Compiler-Based Instrumentation"
,school="Stony Brook University"
,year="2012"
,annotation={
        Looking for data races, including those involving RCU.
        Proposal:
        http://www.fsl.cs.sunysb.edu/docs/jseyster-proposal/redflag.pdf
        Dissertation:
        http://www.fsl.cs.sunysb.edu/docs/jseyster-dissertation/redflag.pdf
}
}

@unpublished{PaulEMcKenney2013RCUUsage
,Author="Paul E. McKenney and Silas Boyd-Wickizer and Jonathan Walpole"
,Title="{RCU} Usage in the {Linux} Kernel: One Decade Later"
,month="February"
,day="24"
,year="2013"
,note="\url{http://rdrop.com/users/paulmck/techreports/RCUUsage.2013.02.24a.pdf}"
,annotation={
        Usage of RCU within the Linux kernel.
}
}

@inproceedings{AlexeyGotsman2013ESOPRCU
,author = {Alexey Gotsman and Noam Rinetzky and Hongseok Yang}
,title = {Verifying concurrent memory reclamation algorithms with grace}
,booktitle = {ESOP'13: European Symposium on Programming}
,year = {2013}
,pages = {249--269}
,publisher = {Springer}
,address = {Rome, Italy}
,annotation={
        http://software.imdea.org/~gotsman/papers/recycling-esop13.pdf
}
}

@unpublished{PaulEMcKenney2013NoTinyPreempt
,Author="Paul E. McKenney"
,Title="Simplifying RCU"
,month="March"
,day="6"
,year="2013"
,note="\url{http://lwn.net/Articles/541037/}"
,annotation={
        Getting rid of TINY_PREEMPT_RCU.
}
}