About Kernel Documentation Linux Kernel Contact Linux Resources Linux Blog

Documentation / RCU / RTFP.txt




Custom Search

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