About Kernel Documentation Linux Kernel Contact Linux Resources Linux Blog

Documentation / RCU / RTFP.txt




Custom Search

Based on kernel version 3.16. Page generated on 2014-08-06 21:40 EST.

1	Read the Fscking Papers!
2	
3	
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.
8	
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.
15	
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.
21	
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!!!)
33	
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.
41	
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.
51	
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.
63	
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.
68	
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.
82	
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.
90	
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].
96	
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 resizeable 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 resizeable 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 resizeable 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 traveral
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{http://www.linuxsymposium.org/2001/abstracts/readcopy.php}
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{http://lkml.org/lkml/2001/10/13/105}
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://lkml.org/lkml/2002/10/24/262}
830	[Viewed February 15, 2014]"
831	,annotation={
832		Mingming Cao's patch to introduce RCU to SysV IPC.
833	}
834	}
835	
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{http://lkml.org/lkml/2003/3/9/205}
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		Steve 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://lkml.org/lkml/2004/5/20/49 (split vars into cachelines)
1040		https://lkml.org/lkml/2004/5/22/114 (cpu_quiet() patch)
1041		https://lkml.org/lkml/2004/5/25/24 (0/5)
1042		https://lkml.org/lkml/2004/5/25/23 (1/5)
1043			https://lkml.org/lkml/2004/5/25/265 (works for Jack)
1044		https://lkml.org/lkml/2004/5/25/20 (2/5)
1045		https://lkml.org/lkml/2004/5/25/22 (3/5)
1046		https://lkml.org/lkml/2004/5/25/19 (4/5)
1047		https://lkml.org/lkml/2004/5/25/21 (5/5)
1048	}
1049	}
1050	
1051	@Conference{Sarma04c
1052	,Author="Dipankar Sarma and Paul E. McKenney"
1053	,Title="Making {RCU} Safe for Deep Sub-Millisecond Response
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{http://lkml.org/lkml/2004/8/6/237}
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{http://lkml.org/lkml/2004/8/30/87}
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{http://lkml.org/lkml/2004/10/23/241}
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://lkml.org/lkml/2004/9/27/52
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{http://lkml.org/lkml/2005/3/17/199}
1245	[Viewed September 5, 2005]"
1246	,annotation={
1247		First posting showing how RCU can be safely adapted for
1248		preemptable 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{http://lkml.org/lkml/2005/3/18/122}
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{http://lkml.org/lkml/2005/5/9/185}
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{http://lkml.org/lkml/2005/8/1/155}
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{http://lkml.org/lkml/2005/8/8/108}
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{http://lkml.org/lkml/2005/10/1/70}
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://lkml.org/lkml/2006/1/7/22}
1433	[Viewed February 29, 2012]"
1434	,annotation={
1435		David Miller's view on hashed arrays of locks: used to really
1436		like it, but time he saw an opportunity for this technique,
1437		something else always proved superior.  Partitioning or RCU.  ;-)
1438	}
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{http://lkml.org/lkml/2006/6/20/238}
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{http://www.linuxsymposium.org/2006/view_abstract.php?content_key=184}
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{http://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{http://www.linuxsymposium.org/2006/view_abstract.php?content_key=184}
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{http://lkml.org/lkml/2006/9/28/160}
1558	[Viewed March 27, 2008]"
1559	}
1560	
1561	@unpublished{PaulEMcKenneyRCUusagePage
1562	,Author="Paul E. McKenney"
1563	,Title="{RCU} {Linux} Usage"
1564	,month="October"
1565	,year="2006"
1566	,note="Available:
1567	\url{http://www.rdrop.com/users/paulmck/RCU/linuxusage.html}
1568	[Viewed January 14, 2007]"
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{http://lkml.org/lkml/2006/10/26/73}
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{http://lkml.org/lkml/2006/11/17/56}
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 http://lkml.org/lkml/2006/11/17/359.
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{http://lkml.org/lkml/2006/11/19/69}
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{http://lkml.org/lkml/2006/11/29/330}
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{http://lkml.org/lkml/2007/1/3/112}
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{http://lkml.org/lkml/2007/1/28/34}
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{http://lkml.org/lkml/2007/2/25/18}
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: http://lkml.org/lkml/2007/2/25/18
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{http://lkml.org/lkml/2007/9/10/213}
1889	[Viewed October 25, 2007]"
1890	,annotation={
1891		Final patch for preemptable 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{http://lkml.org/lkml/2007/12/20/244}
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{http://lkml.org/lkml/2008/1/29/208}
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{http://lkml.org/lkml/2008/2/2/255}
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{http://lkml.org/lkml/2008/6/2/539}
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{http://lkml.org/lkml/2008/8/21/336}
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{http://lkml.org/lkml/2008/9/6/86}
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{http://lkml.org/lkml/2009/1/14/449}
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		http://lkml.org/lkml/2009/2/5/572
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{http://lkml.org/lkml/2009/6/25/306}
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{http://lkml.org/lkml/2009/7/23/294}
2276	[Viewed August 15, 2009]"
2277	,annotation={
2278		First posting of simple and fast preemptable 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{http://lkml.org/lkml/2009/10/18/129}
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://kerneltrap.com/mailarchive/linux-netdev/2010/2/26/6270589}
2455	[Viewed March 20, 2011]"
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://lkml.org/lkml/2011/1/18/322}
2522	[Viewed March 4, 2011]"
2523	,annotation={
2524		"The RCU-based name lookup is at the other end of the spectrum - the
2525		absolute anti-gimmick. It's some seriously good stuff, and gets rid of
2526		the last main global lock that really tends to hurt some kernel loads.
2527		The dentry lock is no longer a big serializing issue. What's really
2528		nice about it is that it actually improves performance a lot even for
2529		single-threaded loads (on an SMP kernel), because it gets rid of some
2530		of the most expensive parts of path component lookup, which was the
2531		d_lock on every component lookup. So I'm seeing improvements of 30-50%
2532		on some seriously pathname-lookup intensive loads."
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 traveral order, the updater need only execute a
2643		memory-barrier instruction, but if in the same direction, the
2644		updater needs to wait for a grace period between the individual
2645		updates.
2646	}
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	}
Hide Line Numbers
About Kernel Documentation Linux Kernel Contact Linux Resources Linux Blog

Information is copyright its respective author. All material is available from the Linux Kernel Source distributed under a GPL License. This page is provided as a free service by mjmwired.net.