brintos / linux-shallow public Read only

1Read the Fscking Papers!2 3 4This document describes RCU-related publications, and is followed by5the corresponding bibtex entries.  A number of the publications may6be found at http://www.rdrop.com/users/paulmck/RCU/.  For others, browsers7and search engines will usually find what you are looking for.8 9The first thing resembling RCU was published in 1980, when Kung and Lehman10[Kung80] recommended use of a garbage collector to defer destruction11of nodes in a parallel binary search tree in order to simplify its12implementation.  This works well in environments that have garbage13collectors, but most production garbage collectors incur significant14overhead.15 16In 1982, Manber and Ladner [Manber82,Manber84] recommended deferring17destruction until all threads running at that time have terminated, again18for a parallel binary search tree.  This approach works well in systems19with short-lived threads, such as the K42 research operating system.20However, Linux has long-lived tasks, so more is needed.21 22In 1986, Hennessy, Osisek, and Seigh [Hennessy89] introduced passive23serialization, which is an RCU-like mechanism that relies on the presence24of "quiescent states" in the VM/XA hypervisor that are guaranteed not25to be referencing the data structure.  However, this mechanism was not26optimized for modern computer systems, which is not surprising given27that these overheads were not so expensive in the mid-80s.  Nonetheless,28passive serialization appears to be the first deferred-destruction29mechanism to be used in production.  Furthermore, the relevant patent30has lapsed, so this approach may be used in non-GPL software, if desired.31(In contrast, implementation of RCU is permitted only in software licensed32under either GPL or LGPL.  Sorry!!!)33 34In 1987, Rashid et al. described lazy TLB-flush [RichardRashid87a].35At first glance, this has nothing to do with RCU, but nevertheless36this paper helped inspire the update-side batching used in the later37RCU implementation in DYNIX/ptx.  In 1988, Barbara Liskov published38a description of Argus that noted that use of out-of-date values can39be tolerated in some situations.  Thus, this paper provides some early40theoretical justification for use of stale data.41 42In 1990, Pugh [Pugh90] noted that explicitly tracking which threads43were reading a given data structure permitted deferred free to operate44in the presence of non-terminating threads.  However, this explicit45tracking imposes significant read-side overhead, which is undesirable46in read-mostly situations.  This algorithm does take pains to avoid47write-side contention and parallelize the other write-side overheads by48providing a fine-grained locking design, however, it would be interesting49to see how much of the performance advantage reported in 1990 remains50today.51 52At about this same time, Andrews [Andrews91textbook] described ``chaotic53relaxation'', where the normal barriers between successive iterations54of convergent numerical algorithms are relaxed, so that iteration $n$55might use data from iteration $n-1$ or even $n-2$.  This introduces56error, which typically slows convergence and thus increases the number of57iterations required.  However, this increase is sometimes more than made58up for by a reduction in the number of expensive barrier operations,59which are otherwise required to synchronize the threads at the end60of each iteration.  Unfortunately, chaotic relaxation requires highly61structured data, such as the matrices used in scientific programs, and62is thus inapplicable to most data structures in operating-system kernels.63 64In 1992, Henry (now Alexia) Massalin completed a dissertation advising65parallel programmers to defer processing when feasible to simplify66synchronization [HMassalinPhD].  RCU makes extremely heavy use of67this advice.68 69In 1993, Jacobson [Jacobson93] verbally described what is perhaps the70simplest deferred-free technique: simply waiting a fixed amount of time71before freeing blocks awaiting deferred free.  Jacobson did not describe72any write-side changes he might have made in this work using SGI's Irix73kernel.  Aju John published a similar technique in 1995 [AjuJohn95].74This works well if there is a well-defined upper bound on the length of75time that reading threads can hold references, as there might well be in76hard real-time systems.  However, if this time is exceeded, perhaps due77to preemption, excessive interrupts, or larger-than-anticipated load,78memory corruption can ensue, with no reasonable means of diagnosis.79Jacobson's technique is therefore inappropriate for use in production80operating-system kernels, except when such kernels can provide hard81real-time response guarantees for all operations.82 83Also in 1995, Pu et al. [Pu95a] applied a technique similar to that of Pugh's84read-side-tracking to permit replugging of algorithms within a commercial85Unix operating system.  However, this replugging permitted only a single86reader at a time.  The following year, this same group of researchers87extended their technique to allow for multiple readers [Cowan96a].88Their approach requires memory barriers (and thus pipeline stalls),89but reduces memory latency, contention, and locking overheads.90 911995 also saw the first publication of DYNIX/ptx's RCU mechanism92[Slingwine95], which was optimized for modern CPU architectures,93and was successfully applied to a number of situations within the94DYNIX/ptx kernel.  The corresponding conference paper appeared in 199895[McKenney98].96 97In 1999, the Tornado and K42 groups described their "generations"98mechanism, which is quite similar to RCU [Gamsa99].  These operating99systems made pervasive use of RCU in place of "existence locks", which100greatly simplifies locking hierarchies and helps avoid deadlocks.101 102The year 2000 saw an email exchange that would likely have103led to yet another independent invention of something like RCU104[RustyRussell2000a,RustyRussell2000b].  Instead, 2001 saw the first105RCU presentation involving Linux [McKenney01a] at OLS.  The resulting106abundance of RCU patches was presented the following year [McKenney02a],107and use of RCU in dcache was first described that same year [Linder02a].108 109Also in 2002, Michael [Michael02b,Michael02a] presented "hazard-pointer"110techniques that defer the destruction of data structures to simplify111non-blocking synchronization (wait-free synchronization, lock-free112synchronization, and obstruction-free synchronization are all examples of113non-blocking synchronization).  The corresponding journal article appeared114in 2004 [MagedMichael04a].  This technique eliminates locking, reduces115contention, reduces memory latency for readers, and parallelizes pipeline116stalls and memory latency for writers.  However, these techniques still117impose significant read-side overhead in the form of memory barriers.118Researchers at Sun worked along similar lines in the same timeframe119[HerlihyLM02].  These techniques can be thought of as inside-out reference120counts, where the count is represented by the number of hazard pointers121referencing a given data structure rather than the more conventional122counter field within the data structure itself.  The key advantage123of inside-out reference counts is that they can be stored in immortal124variables, thus allowing races between access and deletion to be avoided.125 126By the same token, RCU can be thought of as a "bulk reference count",127where some form of reference counter covers all reference by a given CPU128or thread during a set timeframe.  This timeframe is related to, but129not necessarily exactly the same as, an RCU grace period.  In classic130RCU, the reference counter is the per-CPU bit in the "bitmask" field,131and each such bit covers all references that might have been made by132the corresponding CPU during the prior grace period.  Of course, RCU133can be thought of in other terms as well.134 135In 2003, the K42 group described how RCU could be used to create136hot-pluggable implementations of operating-system functions [Appavoo03a].137Later that year saw a paper describing an RCU implementation138of System V IPC [Arcangeli03] (following up on a suggestion by139Hugh Dickins [Dickins02a] and an implementation by Mingming Cao140[MingmingCao2002IPCRCU]), and an introduction to RCU in Linux Journal141[McKenney03a].142 1432004 has seen a Linux-Journal article on use of RCU in dcache144[McKenney04a], a performance comparison of locking to RCU on several145different CPUs [McKenney04b], a dissertation describing use of RCU in a146number of operating-system kernels [PaulEdwardMcKenneyPhD], a paper147describing how to make RCU safe for soft-realtime applications [Sarma04c],148and a paper describing SELinux performance with RCU [JamesMorris04b].149 1502005 brought further adaptation of RCU to realtime use, permitting151preemption of RCU realtime critical sections [PaulMcKenney05a,152PaulMcKenney05b].153 1542006 saw the first best-paper award for an RCU paper [ThomasEHart2006a],155as well as further work on efficient implementations of preemptible156RCU [PaulEMcKenney2006b], but priority-boosting of RCU read-side critical157sections proved elusive.  An RCU implementation permitting general158blocking in read-side critical sections appeared [PaulEMcKenney2006c],159Robert Olsson described an RCU-protected trie-hash combination160[RobertOlsson2006a].161 1622007 saw the journal version of the award-winning RCU paper from 2006163[ThomasEHart2007a], as well as a paper demonstrating use of Promela164and Spin to mechanically verify an optimization to Oleg Nesterov's165QRCU [PaulEMcKenney2007QRCUspin], a design document describing166preemptible RCU [PaulEMcKenney2007PreemptibleRCU], and the three-part167LWN "What is RCU?" series [PaulEMcKenney2007WhatIsRCUFundamentally,168PaulEMcKenney2008WhatIsRCUUsage, and PaulEMcKenney2008WhatIsRCUAPI].169 1702008 saw a journal paper on real-time RCU [DinakarGuniguntala2008IBMSysJ],171a history of how Linux changed RCU more than RCU changed Linux172[PaulEMcKenney2008RCUOSR], and a design overview of hierarchical RCU173[PaulEMcKenney2008HierarchicalRCU].174 1752009 introduced user-level RCU algorithms [PaulEMcKenney2009MaliciousURCU],176which Mathieu Desnoyers is now maintaining [MathieuDesnoyers2009URCU]177[MathieuDesnoyersPhD].  TINY_RCU [PaulEMcKenney2009BloatWatchRCU] made178its appearance, as did expedited RCU [PaulEMcKenney2009expeditedRCU].179The problem of resizable RCU-protected hash tables may now be on a path180to a solution [JoshTriplett2009RPHash].  A few academic researchers are now181using RCU to solve their parallel problems [HariKannan2009DynamicAnalysisRCU].182 1832010 produced a simpler preemptible-RCU implementation184based on TREE_RCU [PaulEMcKenney2010SimpleOptRCU], lockdep-RCU185[PaulEMcKenney2010LockdepRCU], another resizable RCU-protected hash186table [HerbertXu2010RCUResizeHash] (this one consuming more memory,187but allowing arbitrary changes in hash function, as required for DoS188avoidance in the networking code), realization of the 2009 RCU-protected189hash table with atomic node move [JoshTriplett2010RPHash], an update on190the RCU API [PaulEMcKenney2010RCUAPI].191 1922011 marked the inclusion of Nick Piggin's fully lockless dentry search193[LinusTorvalds2011Linux2:6:38:rc1:NPigginVFS], an RCU-protected red-black194tree using software transactional memory to protect concurrent updates195(strange, but true!) [PhilHoward2011RCUTMRBTree], yet another variant of196RCU-protected resizable hash tables [Triplett:2011:RPHash], the 3.0 RCU197trainwreck [PaulEMcKenney2011RCU3.0trainwreck], and Neil Brown's "Meet the198Lockers" LWN article [NeilBrown2011MeetTheLockers].  Some academic199work looked at debugging uses of RCU [Seyster:2011:RFA:2075416.2075425].200 201In 2012, Josh Triplett received his Ph.D. with his dissertation202covering RCU-protected resizable hash tables and the relationship203between memory barriers and read-side traversal order:  If the updater204is making changes in the opposite direction from the read-side traversal205order, the updater need only execute a memory-barrier instruction,206but if in the same direction, the updater needs to wait for a grace207period between the individual updates [JoshTriplettPhD].  Also in 2012,208after seventeen years of attempts, an RCU paper made it into a top-flight209academic journal, IEEE Transactions on Parallel and Distributed Systems210[MathieuDesnoyers2012URCU].  A group of researchers in Spain applied211user-level RCU to crowd simulation [GuillermoVigueras2012RCUCrowd], and212another group of researchers in Europe produced a formal description of213RCU based on separation logic [AlexeyGotsman2012VerifyGraceExtended],214which was published in the 2013 European Symposium on Programming215[AlexeyGotsman2013ESOPRCU].216 217 218 219Bibtex Entries220 221@article{Kung80222,author="H. T. Kung and Q. Lehman"223,title="Concurrent Manipulation of Binary Search Trees"224,Year="1980"225,Month="September"226,journal="ACM Transactions on Database Systems"227,volume="5"228,number="3"229,pages="354-382"230,annotation={231	Use garbage collector to clean up data after everyone is done with it.232	.233	Oldest use of something vaguely resembling RCU that I have found.234	http://portal.acm.org/citation.cfm?id=320619&dl=GUIDE,235	[Viewed December 3, 2007]236}237}238 239@techreport{Manber82240,author="Udi Manber and Richard E. Ladner"241,title="Concurrency Control in a Dynamic Search Structure"242,institution="Department of Computer Science, University of Washington"243,address="Seattle, Washington"244,year="1982"245,number="82-01-01"246,month="January"247,pages="28"248,annotation={249	.250	Superseded by Manber84.251	.252	Describes concurrent AVL tree implementation.  Uses a253	garbage-collection mechanism to handle concurrent use and deletion254	of nodes in the tree, but lacks the summary-of-execution-history255	concept of read-copy locking.256	.257	Keeps full list of processes that were active when a given258	node was to be deleted, and waits until all such processes have259	-terminated- before allowing this node to be reused.  This is260	not described in great detail -- one could imagine using process261	IDs for this if the ID space was large enough that overlapping262	never occurred.263	.264	This restriction makes this algorithm unsuitable for use in265	systems comprised of long-lived processes.  It also produces266	completely unacceptable overhead in systems with large numbers267	of processes.  Finally, it is specific to AVL trees.268	.269	Cites Kung80, so not an independent invention, but the first270	RCU-like usage that does not rely on an automatic garbage271	collector.272}273}274 275@article{Manber84276,author="Udi Manber and Richard E. Ladner"277,title="Concurrency Control in a Dynamic Search Structure"278,Year="1984"279,Month="September"280,journal="ACM Transactions on Database Systems"281,volume="9"282,number="3"283,pages="439-455"284,annotation={285	Describes concurrent AVL tree implementation.  Uses a286	garbage-collection mechanism to handle concurrent use and deletion287	of nodes in the tree, but lacks the summary-of-execution-history288	concept of read-copy locking.289	.290	Keeps full list of processes that were active when a given291	node was to be deleted, and waits until all such processes have292	-terminated- before allowing this node to be reused.  This is293	not described in great detail -- one could imagine using process294	IDs for this if the ID space was large enough that overlapping295	never occurred.296	.297	This restriction makes this algorithm unsuitable for use in298	systems comprised of long-lived processes.  It also produces299	completely unacceptable overhead in systems with large numbers300	of processes.  Finally, it is specific to AVL trees.301}302}303 304@Conference{RichardRashid87a305,Author="Richard Rashid and Avadis Tevanian and Michael Young and306David Golub and Robert Baron and David Black and William Bolosky and307Jonathan Chew"308,Title="Machine-Independent Virtual Memory Management for Paged309Uniprocessor and Multiprocessor Architectures"310,Booktitle="{2\textsuperscript{nd} Symposium on Architectural Support311for Programming Languages and Operating Systems}"312,Publisher="Association for Computing Machinery"313,Month="October"314,Year="1987"315,pages="31-39"316,Address="Palo Alto, CA"317,note="Available:318\url{http://www.cse.ucsc.edu/~randal/221/rashid-machvm.pdf}319[Viewed February 17, 2005]"320,annotation={321	Describes lazy TLB flush, where one waits for each CPU to pass322	through a scheduling-clock interrupt before reusing a given range323	of virtual address.  Does not describe how one determines that324	all CPUs have in fact taken such an interrupt, though there are325	no shortage of straightforward methods for accomplishing this.326	.327	Note that it does not make sense to just wait a fixed amount of328	time, since a given CPU might have interrupts disabled for an329	extended amount of time.330}331}332 333@article{BarbaraLiskov1988ArgusCACM334,author = {Barbara Liskov}335,title = {Distributed programming in {Argus}}336,journal = {Commun. ACM}337,volume = {31}338,number = {3}339,year = {1988}340,issn = {0001-0782}341,pages = {300--312}342,doi = {http://doi.acm.org/10.1145/42392.42399}343,publisher = {ACM}344,address = {New York, NY, USA}345,annotation={346	At the top of page 307: "Conflicts with deposits and withdrawals347	are necessary if the reported total is to be up to date.  They348	could be avoided by having total return a sum that is slightly349	out of date."  Relies on semantics -- approximate numerical350	values sometimes OK.351}352}353 354@techreport{Hennessy89355,author="James P. Hennessy and Damian L. Osisek and Joseph W. {Seigh II}"356,title="Passive Serialization in a Multitasking Environment"357,institution="US Patent and Trademark Office"358,address="Washington, DC"359,year="1989"360,number="US Patent 4,809,168 (lapsed)"361,month="February"362,pages="11"363}364 365@techreport{Pugh90366,author="William Pugh"367,title="Concurrent Maintenance of Skip Lists"368,institution="Institute of Advanced Computer Science Studies, Department of Computer Science, University of Maryland"369,address="College Park, Maryland"370,year="1990"371,number="CS-TR-2222.1"372,month="June"373,annotation={374	Concurrent access to skip lists.  Has both weak and strong search.375	Uses concept of ``garbage queue'', but has no real way of cleaning376	the garbage efficiently.377	.378	Appears to be an independent invention of an RCU-like mechanism.379}380}381 382# Was Adams91, see also syncrefs.bib.383@Book{Andrews91textbook384,Author="Gregory R. Andrews"385,title="Concurrent Programming, Principles, and Practices"386,Publisher="Benjamin Cummins"387,Year="1991"388,annotation={389	Has a few paragraphs describing ``chaotic relaxation'', a390	numerical analysis technique that allows multiprocessors to391	avoid synchronization overhead by using possibly-stale data.392	.393	Seems like this is descended from yet another independent394	invention of RCU-like function -- but this is restricted395	in that reclamation is not necessary.396}397}398 399@phdthesis{HMassalinPhD400,author="H. Massalin"401,title="Synthesis: An Efficient Implementation of Fundamental Operating402System Services"403,school="Columbia University"404,address="New York, NY"405,year="1992"406,annotation={407	Mondo optimizing compiler.408	Wait-free stuff.409	Good advice: defer work to avoid synchronization.  See page 90410		(PDF page 106), Section 5.4, fourth bullet point.411}412}413 414@unpublished{Jacobson93415,author="Van Jacobson"416,title="Avoid Read-Side Locking Via Delayed Free"417,year="1993"418,month="September"419,note="private communication"420,annotation={421	Use fixed time delay to approximate grace period.  Very simple,422	but subject to random memory corruption under heavy load.423	.424	Independent invention of RCU-like mechanism.425}426}427 428@Conference{AjuJohn95429,Author="Aju John"430,Title="Dynamic vnodes -- Design and Implementation"431,Booktitle="{USENIX Winter 1995}"432,Publisher="USENIX Association"433,Month="January"434,Year="1995"435,pages="11-23"436,Address="New Orleans, LA"437,note="Available:438\url{https://www.usenix.org/publications/library/proceedings/neworl/full_papers/john.a}439[Viewed October 1, 2010]"440,annotation={441	Age vnodes out of the cache, and have a fixed time set by a kernel442	parameter.  Not clear that all races were in fact correctly handled.443	Used a 20-minute time by default, which would most definitely not444	be suitable during DoS attacks or virus scans.445	.446	Apparently independent invention of RCU-like mechanism.447}448}449 450@conference{Pu95a451,Author = "Calton Pu and Tito Autrey and Andrew Black and Charles Consel and452Crispin Cowan and Jon Inouye and Lakshmi Kethana and Jonathan Walpole and453Ke Zhang"454,Title = "Optimistic Incremental Specialization: Streamlining a Commercial455,Operating System"456,Booktitle = "15\textsuperscript{th} ACM Symposium on457,Operating Systems Principles (SOSP'95)"458,address = "Copper Mountain, CO"459,month="December"460,year="1995"461,pages="314-321"462,annotation={463	Uses a replugger, but with a flag to signal when people are464	using the resource at hand.  Only one reader at a time.465}466}467 468@conference{Cowan96a469,Author = "Crispin Cowan and Tito Autrey and Charles Krasic and470,Calton Pu and Jonathan Walpole"471,Title = "Fast Concurrent Dynamic Linking for an Adaptive Operating System"472,Booktitle = "International Conference on Configurable Distributed Systems473(ICCDS'96)"474,address = "Annapolis, MD"475,month="May"476,year="1996"477,pages="108"478,isbn="0-8186-7395-8"479,annotation={480	Uses a replugger, but with a counter to signal when people are481	using the resource at hand.  Allows multiple readers.482}483}484 485@techreport{Slingwine95486,author="John D. Slingwine and Paul E. McKenney"487,title="Apparatus and Method for Achieving Reduced Overhead Mutual488Exclusion and Maintaining Coherency in a Multiprocessor System489Utilizing Execution History and Thread Monitoring"490,institution="US Patent and Trademark Office"491,address="Washington, DC"492,year="1995"493,number="US Patent 5,442,758"494,month="August"495,annotation={496	Describes the parallel RCU infrastructure.  Includes NUMA aspect497	(structure of bitmap can reflect bus structure of computer system).498	.499	Another independent invention of an RCU-like mechanism, but the500	"real" RCU this time!501}502}503 504@techreport{Slingwine97505,author="John D. Slingwine and Paul E. McKenney"506,title="Method for Maintaining Data Coherency Using Thread Activity507Summaries in a Multicomputer System"508,institution="US Patent and Trademark Office"509,address="Washington, DC"510,year="1997"511,number="US Patent 5,608,893"512,month="March"513,pages="19"514,annotation={515	Describes use of RCU to synchronize data between a pair of516	SMP/NUMA computer systems.517}518}519 520@techreport{Slingwine98521,author="John D. Slingwine and Paul E. McKenney"522,title="Apparatus and Method for Achieving Reduced Overhead Mutual523Exclusion and Maintaining Coherency in a Multiprocessor System524Utilizing Execution History and Thread Monitoring"525,institution="US Patent and Trademark Office"526,address="Washington, DC"527,year="1998"528,number="US Patent 5,727,209"529,month="March"530,annotation={531	Describes doing an atomic update by copying the data item and532	then substituting it into the data structure.533}534}535 536@Conference{McKenney98537,Author="Paul E. McKenney and John D. Slingwine"538,Title="Read-Copy Update: Using Execution History to Solve Concurrency539Problems"540,Booktitle="{Parallel and Distributed Computing and Systems}"541,Month="October"542,Year="1998"543,pages="509-518"544,Address="Las Vegas, NV"545,annotation={546	Describes and analyzes RCU mechanism in DYNIX/ptx.  Describes547	application to linked list update and log-buffer flushing.548	Defines 'quiescent state'.  Includes both measured and analytic549	evaluation.550	http://www.rdrop.com/users/paulmck/RCU/rclockpdcsproof.pdf551	[Viewed December 3, 2007]552}553}554 555@Conference{Gamsa99556,Author="Ben Gamsa and Orran Krieger and Jonathan Appavoo and Michael Stumm"557,Title="Tornado: Maximizing Locality and Concurrency in a Shared Memory558Multiprocessor Operating System"559,Booktitle="{Proceedings of the 3\textsuperscript{rd} Symposium on560Operating System Design and Implementation}"561,Month="February"562,Year="1999"563,pages="87-100"564,Address="New Orleans, LA"565,annotation={566	Use of RCU-like facility in K42/Tornado.  Another independent567	invention of RCU.568	See especially pages 7-9 (Section 5).569	http://www.usenix.org/events/osdi99/full_papers/gamsa/gamsa.pdf570	[Viewed August 30, 2006]571}572}573 574@unpublished{RustyRussell2000a575,Author="Rusty Russell"576,Title="Re: modular net drivers"577,month="June"578,year="2000"579,day="23"580,note="Available:581\url{http://oss.sgi.com/projects/netdev/archive/2000-06/msg00250.html}582[Viewed April 10, 2006]"583,annotation={584	Proto-RCU proposal from Phil Rumpf and Rusty Russell.585	Yet another independent invention of RCU.586	Outline of algorithm to unload modules...587	.588	Appeared on net-dev mailing list.589}590}591 592@unpublished{RustyRussell2000b593,Author="Rusty Russell"594,Title="Re: modular net drivers"595,month="June"596,year="2000"597,day="24"598,note="Available:599\url{http://oss.sgi.com/projects/netdev/archive/2000-06/msg00254.html}600[Viewed April 10, 2006]"601,annotation={602	Proto-RCU proposal from Phil Rumpf and Rusty Russell.603	.604	Appeared on net-dev mailing list.605}606}607 608@unpublished{McKenney01b609,Author="Paul E. McKenney and Dipankar Sarma"610,Title="Read-Copy Update Mutual Exclusion in {Linux}"611,month="February"612,year="2001"613,note="Available:614\url{http://lse.sourceforge.net/locking/rcu/rcupdate_doc.html}615[Viewed October 18, 2004]"616,annotation={617	Prototypical Linux documentation for RCU.618}619}620 621@techreport{Slingwine01622,author="John D. Slingwine and Paul E. McKenney"623,title="Apparatus and Method for Achieving Reduced Overhead Mutual624Exclusion and Maintaining Coherency in a Multiprocessor System625Utilizing Execution History and Thread Monitoring"626,institution="US Patent and Trademark Office"627,address="Washington, DC"628,year="2001"629,number="US Patent 6,219,690"630,month="April"631,annotation={632	'Change in mode' aspect of RCU.  Can be thought of as a lazy barrier.633}634}635 636@Conference{McKenney01a637,Author="Paul E. McKenney and Jonathan Appavoo and Andi Kleen and638Orran Krieger and Rusty Russell and Dipankar Sarma and Maneesh Soni"639,Title="Read-Copy Update"640,Booktitle="{Ottawa Linux Symposium}"641,Month="July"642,Year="2001"643,note="Available:644\url{http://www.linuxsymposium.org/2001/abstracts/readcopy.php}645\url{http://www.rdrop.com/users/paulmck/RCU/rclock_OLS.2001.05.01c.pdf}646[Viewed June 23, 2004]"647,annotation={648	Described RCU, and presented some patches implementing and using649	it in the Linux kernel.650}651}652 653@unpublished{McKenney01f654,Author="Paul E. McKenney"655,Title="{RFC:} patch to allow lock-free traversal of lists with insertion"656,month="October"657,year="2001"658,note="Available:659\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=100259266316456&w=2}660[Viewed June 23, 2004]"661,annotation={662	Memory-barrier and Alpha thread.  100 messages, not too bad...663}664}665 666@unpublished{Spraul01667,Author="Manfred Spraul"668,Title="Re: {RFC:} patch to allow lock-free traversal of lists with insertion"669,month="October"670,year="2001"671,note="Available:672\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=100264675012867&w=2}673[Viewed June 23, 2004]"674,annotation={675	Suggested burying memory barriers in Linux's list-manipulation676	primitives.677}678}679 680@unpublished{LinusTorvalds2001a681,Author="Linus Torvalds"682,Title="{Re:} {[Lse-tech]} {Re:} {RFC:} patch to allow lock-free traversal of lists with insertion"683,month="October"684,year="2001"685,note="Available:686\url{https://lore.kernel.org/r/Pine.LNX.4.33.0110131015410.8707-100000@penguin.transmeta.com}687[Viewed August 21, 2004]"688,annotation={689}690}691 692@unpublished{Blanchard02a693,Author="Anton Blanchard"694,Title="some RCU dcache and ratcache results"695,month="March"696,year="2002"697,note="Available:698\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=101637107412972&w=2}699[Viewed October 18, 2004]"700}701 702@conference{Michael02b703,author="Maged M. Michael"704,title="High Performance Dynamic Lock-Free Hash Tables and List-Based Sets"705,Year="2002"706,Month="August"707,booktitle="{Proceedings of the 14\textsuperscript{th} Annual ACM708Symposium on Parallel709Algorithms and Architecture}"710,pages="73-82"711,annotation={712Like the title says...713}714}715 716@Conference{Linder02a717,Author="Hanna Linder and Dipankar Sarma and Maneesh Soni"718,Title="Scalability of the Directory Entry Cache"719,Booktitle="{Ottawa Linux Symposium}"720,Month="June"721,Year="2002"722,pages="289-300"723,annotation={724	Measured scalability of Linux 2.4 kernel's directory-entry cache725	(dcache), and measured some scalability enhancements.726}727}728 729@Conference{McKenney02a730,Author="Paul E. McKenney and Dipankar Sarma and731Andrea Arcangeli and Andi Kleen and Orran Krieger and Rusty Russell"732,Title="Read-Copy Update"733,Booktitle="{Ottawa Linux Symposium}"734,Month="June"735,Year="2002"736,pages="338-367"737,note="Available:738\url{http://www.linux.org.uk/~ajh/ols2002_proceedings.pdf.gz}739[Viewed June 23, 2004]"740,annotation={741	Presented and compared a number of RCU implementations for the742	Linux kernel.743}744}745 746@unpublished{Sarma02a747,Author="Dipankar Sarma"748,Title="specweb99: dcache scalability results"749,month="July"750,year="2002"751,note="Available:752\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=102645767914212&w=2}753[Viewed June 23, 2004]"754,annotation={755	Compare fastwalk and RCU for dcache.  RCU won.756}757}758 759@unpublished{Barbieri02760,Author="Luca Barbieri"761,Title="Re: {[PATCH]} Initial support for struct {vfs\_cred}"762,month="August"763,year="2002"764,note="Available:765\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=103082050621241&w=2}766[Viewed: June 23, 2004]"767,annotation={768	Suggested RCU for vfs\_shared\_cred.769}770}771 772@conference{Michael02a773,author="Maged M. Michael"774,title="Safe Memory Reclamation for Dynamic Lock-Free Objects Using Atomic775Reads and Writes"776,Year="2002"777,Month="August"778,booktitle="{Proceedings of the 21\textsuperscript{st} Annual ACM779Symposium on Principles of Distributed Computing}"780,pages="21-30"781,annotation={782	Each thread keeps an array of pointers to items that it is783	currently referencing.	Sort of an inside-out garbage collection784	mechanism, but one that requires the accessing code to explicitly785	state its needs.  Also requires read-side memory barriers on786	most architectures.787}788}789 790@unpublished{Dickins02a791,author="Hugh Dickins"792,title="Use RCU for System-V IPC"793,year="2002"794,month="October"795,note="private communication"796}797 798@InProceedings{HerlihyLM02799,author={Maurice Herlihy and Victor Luchangco and Mark Moir}800,title="The Repeat Offender Problem: A Mechanism for Supporting Dynamic-Sized,801Lock-Free Data Structures"802,booktitle={Proceedings of 16\textsuperscript{th} International803Symposium on Distributed Computing}804,year=2002805,month="October"806,pages="339-353"807}808 809@unpublished{Sarma02b810,Author="Dipankar Sarma"811,Title="Some dcache\_rcu benchmark numbers"812,month="October"813,year="2002"814,note="Available:815\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=103462075416638&w=2}816[Viewed June 23, 2004]"817,annotation={818	Performance of dcache RCU on kernbench for 16x NUMA-Q and 1x,819	2x, and 4x systems.  RCU does no harm, and helps on 16x.820}821}822 823@unpublished{MingmingCao2002IPCRCU824,Author="Mingming Cao"825,Title="[PATCH]updated ipc lock patch"826,month="October"827,year="2002"828,note="Available:829\url{https://lore.kernel.org/r/3DB86B05.447E7410@us.ibm.com}830[Viewed February 15, 2014]"831,annotation={832	Mingming Cao's patch to introduce RCU to SysV IPC.833}834}835 836@unpublished{LinusTorvalds2003a837,Author="Linus Torvalds"838,Title="Re: {[PATCH]} small fixes in brlock.h"839,month="March"840,year="2003"841,note="Available:842\url{https://lore.kernel.org/r/Pine.LNX.4.44.0303091831560.2129-100000@home.transmeta.com}843[Viewed March 13, 2006]"844,annotation={845	Linus suggests replacing brlock with RCU and/or seqlocks:846	.847	'It's entirely possible that the current user could be replaced848	by RCU and/or seqlocks, and we could get rid of brlocks entirely.'849	.850	Stephen Hemminger responds by replacing them with RCU.851}852}853 854@article{Appavoo03a855,author="J. Appavoo and K. Hui and C. A. N. Soules and R. W. Wisniewski and856D. M. {Da Silva} and O. Krieger and M. A. Auslander and D. J. Edelsohn and857B. Gamsa and G. R. Ganger and P. McKenney and M. Ostrowski and858B. Rosenburg and M. Stumm and J. Xenidis"859,title="Enabling Autonomic Behavior in Systems Software With Hot Swapping"860,Year="2003"861,Month="January"862,journal="IBM Systems Journal"863,volume="42"864,number="1"865,pages="60-76"866,annotation={867	Use of RCU to enable hot-swapping for autonomic behavior in K42.868}869}870 871@unpublished{Seigh03872,author="Joseph W. {Seigh II}"873,title="Read Copy Update"874,Year="2003"875,Month="March"876,note="email correspondence"877,annotation={878	Described the relationship of the VM/XA passive serialization to RCU.879}880}881 882@Conference{Arcangeli03883,Author="Andrea Arcangeli and Mingming Cao and Paul E. McKenney and884Dipankar Sarma"885,Title="Using Read-Copy Update Techniques for {System V IPC} in the886{Linux} 2.5 Kernel"887,Booktitle="Proceedings of the 2003 USENIX Annual Technical Conference888(FREENIX Track)"889,Publisher="USENIX Association"890,year="2003"891,month="June"892,pages="297-310"893,annotation={894	Compared updated RCU implementations for the Linux kernel, and895	described System V IPC use of RCU, including order-of-magnitude896	performance improvements.897	http://www.rdrop.com/users/paulmck/RCU/rcu.FREENIX.2003.06.14.pdf898}899}900 901@Conference{Soules03a902,Author="Craig A. N. Soules and Jonathan Appavoo and Kevin Hui and903Dilma {Da Silva} and Gregory R. Ganger and Orran Krieger and904Michael Stumm and Robert W. Wisniewski and Marc Auslander and905Michal Ostrowski and Bryan Rosenburg and Jimi Xenidis"906,Title="System Support for Online Reconfiguration"907,Booktitle="Proceedings of the 2003 USENIX Annual Technical Conference"908,Publisher="USENIX Association"909,year="2003"910,month="June"911,pages="141-154"912}913 914@article{McKenney03a915,author="Paul E. McKenney"916,title="Using {RCU} in the {Linux} 2.5 Kernel"917,Year="2003"918,Month="October"919,journal="Linux Journal"920,volume="1"921,number="114"922,pages="18-26"923,note="Available:924\url{http://www.linuxjournal.com/article/6993}925[Viewed November 14, 2007]"926,annotation={927	Reader-friendly intro to RCU, with the infamous old-man-and-brat928	cartoon.929}930}931 932@unpublished{Sarma03a933,Author="Dipankar Sarma"934,Title="RCU low latency patches"935,month="December"936,year="2003"937,note="Message ID: 20031222180114.GA2248@in.ibm.com"938,annotation={939	dipankar/ct.2004.03.27/RCUll.2003.12.22.patch940}941}942 943@techreport{Friedberg03a944,author="Stuart A. Friedberg"945,title="Lock-Free Wild Card Search Data Structure and Method"946,institution="US Patent and Trademark Office"947,address="Washington, DC"948,year="2003"949,number="US Patent 6,662,184"950,month="December"951,pages="112"952,annotation={953	Applies RCU to a wildcard-search Patricia tree in order to permit954	synchronization-free lookup.  RCU is used to retain removed nodes955	for a grace period before freeing them.956}957}958 959@article{McKenney04a960,author="Paul E. McKenney and Dipankar Sarma and Maneesh Soni"961,title="Scaling dcache with {RCU}"962,Year="2004"963,Month="January"964,journal="Linux Journal"965,volume="1"966,number="118"967,pages="38-46"968,annotation={969	Reader friendly intro to dcache and RCU.970	http://www.linuxjournal.com/node/7124971	[Viewed December 26, 2010]972}973}974 975@Conference{McKenney04b976,Author="Paul E. McKenney"977,Title="{RCU} vs. Locking Performance on Different {CPUs}"978,Booktitle="{linux.conf.au}"979,Month="January"980,Year="2004"981,Address="Adelaide, Australia"982,note="Available:983\url{http://www.linux.org.au/conf/2004/abstracts.html#90}984\url{http://www.rdrop.com/users/paulmck/RCU/lockperf.2004.01.17a.pdf}985[Viewed June 23, 2004]"986,annotation={987	Compares performance of RCU to that of other locking primitives988	over a number of CPUs (x86, Opteron, Itanium, and PPC).989}990}991 992@unpublished{Sarma04a993,Author="Dipankar Sarma"994,Title="{[PATCH]} {RCU} for low latency (experimental)"995,month="March"996,year="2004"997,note="\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=108003746402892&w=2}"998,annotation={999	Head of thread: dipankar/2004.03.23/rcu-low-lat.1.patch1000}1001}1002 1003@unpublished{Sarma04b1004,Author="Dipankar Sarma"1005,Title="Re: {[PATCH]} {RCU} for low latency (experimental)"1006,month="March"1007,year="2004"1008,note="\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=108016474829546&w=2}"1009,annotation={1010	dipankar/rcuth.2004.03.24/rcu-throttle.patch1011}1012}1013 1014@unpublished{Spraul04a1015,Author="Manfred Spraul"1016,Title="[RFC] 0/5 rcu lock update"1017,month="May"1018,year="2004"1019,note="Available:1020\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=108546407726602&w=2}1021[Viewed June 23, 2004]"1022,annotation={1023	Hierarchical-bitmap patch for RCU infrastructure.1024}1025}1026 1027@unpublished{Steiner04a1028,Author="Jack Steiner"1029,Title="Re: [Lse-tech] [RFC, PATCH] 1/5 rcu lock update:1030Add per-cpu batch counter"1031,month="May"1032,year="2004"1033,note="Available:1034\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=108551764515332&w=2}1035[Viewed June 23, 2004]"1036,annotation={1037	RCU runs reasonably on a 512-CPU SGI using Manfred Spraul's patches,1038	which may be found at:1039	https://lore.kernel.org/r/40AC9823.6020709@colorfullife.com (split vars into cachelines)1040	https://lore.kernel.org/r/Pine.LNX.4.44.0405222141260.11106-100000@dbl.q-ag.de (cpu_quiet() patch)1041	https://lore.kernel.org/r/200405250535.i4P5ZJo8017583@dbl.q-ag.de (0/5)1042	https://lore.kernel.org/r/200405250535.i4P5ZKAQ017591@dbl.q-ag.de (1/5)1043		https://lore.kernel.org/r/20040525203215.GB5127@sgi.com (works for Jack)1044	https://lore.kernel.org/r/200405250535.i4P5ZLiR017599@dbl.q-ag.de (2/5)1045	https://lore.kernel.org/r/200405250535.i4P5ZMFt017607@dbl.q-ag.de (3/5)1046	https://lore.kernel.org/r/200405250535.i4P5ZN6g017615@dbl.q-ag.de (4/5)1047	https://lore.kernel.org/r/200405250535.i4P5ZO7I017623@dbl.q-ag.de (5/5)1048}1049}1050 1051@Conference{Sarma04c1052,Author="Dipankar Sarma and Paul E. McKenney"1053,Title="Making {RCU} Safe for Deep Sub-Millisecond Response1054Realtime Applications"1055,Booktitle="Proceedings of the 2004 USENIX Annual Technical Conference1056(FREENIX Track)"1057,Publisher="USENIX Association"1058,year="2004"1059,month="June"1060,pages="182-191"1061,annotation={1062	Describes and compares a number of modifications to the Linux RCU1063	implementation that make it friendly to realtime applications.1064	https://www.usenix.org/conference/2004-usenix-annual-technical-conference/making-rcu-safe-deep-sub-millisecond-response1065	[Viewed July 26, 2012]1066}1067}1068 1069@article{MagedMichael04a1070,author="Maged M. Michael"1071,title="Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects"1072,Year="2004"1073,Month="June"1074,journal="IEEE Transactions on Parallel and Distributed Systems"1075,volume="15"1076,number="6"1077,pages="491-504"1078,url="Available:1079\url{http://www.research.ibm.com/people/m/michael/ieeetpds-2004.pdf}1080[Viewed March 1, 2005]"1081,annotation={1082	New canonical hazard-pointer citation.1083}1084}1085 1086@phdthesis{PaulEdwardMcKenneyPhD1087,author="Paul E. McKenney"1088,title="Exploiting Deferred Destruction:1089An Analysis of Read-Copy-Update Techniques1090in Operating System Kernels"1091,school="OGI School of Science and Engineering at1092Oregon Health and Sciences University"1093,year="2004"1094,annotation={1095	Describes RCU implementations and presents design patterns1096	corresponding to common uses of RCU in several operating-system1097	kernels.1098	http://www.rdrop.com/users/paulmck/RCU/RCUdissertation.2004.07.14e1.pdf1099	[Viewed October 15, 2004]1100}1101}1102 1103@unpublished{PaulEMcKenney2004rcu:dereference1104,Author="Dipankar Sarma"1105,Title="{Re: RCU : Abstracted RCU dereferencing [5/5]}"1106,month="August"1107,year="2004"1108,note="Available:1109\url{https://lore.kernel.org/r/20040807192424.GF3936@in.ibm.com}1110[Viewed June 8, 2010]"1111,annotation={1112	Introduce rcu_dereference().1113}1114}1115 1116@unpublished{JimHouston04a1117,Author="Jim Houston"1118,Title="{[RFC\&PATCH] Alternative {RCU} implementation}"1119,month="August"1120,year="2004"1121,note="Available:1122\url{https://lore.kernel.org/r/1093873222.984.12.camel@new.localdomain}1123[Viewed February 17, 2005]"1124,annotation={1125	Uses active code in rcu_read_lock() and rcu_read_unlock() to1126	make RCU happen, allowing RCU to function on CPUs that do not1127	receive a scheduling-clock interrupt.1128}1129}1130 1131@unpublished{TomHart04a1132,Author="Thomas E. Hart"1133,Title="Master's Thesis: Applying Lock-free Techniques to the {Linux} Kernel"1134,month="October"1135,year="2004"1136,note="Available:1137\url{http://www.cs.toronto.edu/~tomhart/masters_thesis.html}1138[Viewed October 15, 2004]"1139,annotation={1140	Proposes comparing RCU to lock-free methods for the Linux kernel.1141}1142}1143 1144@unpublished{Vaddagiri04a1145,Author="Srivatsa Vaddagiri"1146,Title="Subject: [RFC] Use RCU for tcp\_ehash lookup"1147,month="October"1148,year="2004"1149,note="Available:1150\url{http://marc.theaimsgroup.com/?t=109395731700004&r=1&w=2}1151[Viewed October 18, 2004]"1152,annotation={1153	Srivatsa's RCU patch for tcp_ehash lookup.1154}1155}1156 1157@unpublished{Thirumalai04a1158,Author="Ravikiran Thirumalai"1159,Title="Subject: [patchset] Lockfree fd lookup 0 of 5"1160,month="October"1161,year="2004"1162,note="Available:1163\url{http://marc.theaimsgroup.com/?t=109144217400003&r=1&w=2}1164[Viewed October 18, 2004]"1165,annotation={1166	Ravikiran's lockfree FD patch.1167}1168}1169 1170@unpublished{Thirumalai04b1171,Author="Ravikiran Thirumalai"1172,Title="Subject: Re: [patchset] Lockfree fd lookup 0 of 5"1173,month="October"1174,year="2004"1175,note="Available:1176\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=109152521410459&w=2}1177[Viewed October 18, 2004]"1178,annotation={1179	Ravikiran's lockfree FD patch.1180}1181}1182 1183@unpublished{PaulEMcKenney2004rcu:assign:pointer1184,Author="Paul E. McKenney"1185,Title="{[PATCH 1/3] RCU: \url{rcu_assign_pointer()} removal of memory barriers}"1186,month="October"1187,year="2004"1188,note="Available:1189\url{https://lore.kernel.org/r/20041023202723.GA1930@us.ibm.com}1190[Viewed June 8, 2010]"1191,annotation={1192	Introduce rcu_assign_pointer().1193}1194}1195 1196@unpublished{JamesMorris04a1197,Author="James Morris"1198,Title="{[PATCH 2/3] SELinux} scalability - convert {AVC} to {RCU}"1199,day="15"1200,month="November"1201,year="2004"1202,note="\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=110054979416004&w=2}"1203,annotation={1204	James Morris posts Kaigai Kohei's patch to LKML.1205	[Viewed December 10, 2004]1206	Kaigai's patch is at https://lore.kernel.org/r/200409271057.i8RAvcA1007873@mailsv.bs1.fc.nec.co.jp1207}1208}1209 1210@unpublished{JamesMorris04b1211,Author="James Morris"1212,Title="Recent Developments in {SELinux} Kernel Performance"1213,month="December"1214,year="2004"1215,note="Available:1216\url{http://www.livejournal.com/users/james_morris/2153.html}1217[Viewed December 10, 2004]"1218,annotation={1219	RCU helps SELinux performance.  ;-)  Made LWN.1220}1221}1222 1223@unpublished{PaulMcKenney2005RCUSemantics1224,Author="Paul E. McKenney and Jonathan Walpole"1225,Title="{RCU} Semantics: A First Attempt"1226,month="January"1227,year="2005"1228,day="30"1229,note="Available:1230\url{http://www.rdrop.com/users/paulmck/RCU/rcu-semantics.2005.01.30a.pdf}1231[Viewed December 6, 2009]"1232,annotation={1233	Early derivation of RCU semantics.1234}1235}1236 1237@unpublished{PaulMcKenney2005e1238,Author="Paul E. McKenney"1239,Title="Real-Time Preemption and {RCU}"1240,month="March"1241,year="2005"1242,day="17"1243,note="Available:1244\url{https://lore.kernel.org/r/20050318002026.GA2693@us.ibm.com}1245[Viewed September 5, 2005]"1246,annotation={1247	First posting showing how RCU can be safely adapted for1248	preemptible RCU read side critical sections.1249}1250}1251 1252@unpublished{EsbenNeilsen2005a1253,Author="Esben Neilsen"1254,Title="Re: Real-Time Preemption and {RCU}"1255,month="March"1256,year="2005"1257,day="18"1258,note="Available:1259\url{https://lore.kernel.org/r/Pine.OSF.4.05.10503181336310.2466-100000@da410.phys.au.dk}1260[Viewed March 30, 2006]"1261,annotation={1262	Esben Neilsen suggests read-side suppression of grace-period1263	processing for crude-but-workable realtime RCU.  The downside1264	is indefinite grace periods...  But this is OK for experimentation1265	and testing.1266}1267}1268 1269@unpublished{TomHart05a1270,Author="Thomas E. Hart and Paul E. McKenney and Angela Demke Brown"1271,Title="Efficient Memory Reclamation is Necessary for Fast Lock-Free1272Data Structures"1273,month="March"1274,year="2005"1275,note="Available:1276\url{ftp://ftp.cs.toronto.edu/csrg-technical-reports/515/}1277[Viewed March 4, 2005]"1278,annotation={1279	Comparison of RCU, QBSR, and EBSR.  RCU wins for read-mostly1280	workloads.  ;-)1281}1282}1283 1284@unpublished{JonCorbet2005DeprecateSyncKernel1285,Author="Jonathan Corbet"1286,Title="API change: synchronize_kernel() deprecated"1287,month="May"1288,day="3"1289,year="2005"1290,note="Available:1291\url{http://lwn.net/Articles/134484/}1292[Viewed May 3, 2005]"1293,annotation={1294	Jon Corbet describes deprecation of synchronize_kernel()1295	in favor of synchronize_rcu() and synchronize_sched().1296}1297}1298 1299@unpublished{PaulMcKenney05a1300,Author="Paul E. McKenney"1301,Title="{[RFC]} {RCU} and {CONFIG\_PREEMPT\_RT} progress"1302,month="May"1303,year="2005"1304,note="Available:1305\url{https://lore.kernel.org/r/20050510012444.GA3011@us.ibm.com}1306[Viewed May 13, 2005]"1307,annotation={1308	First publication of working lock-based deferred free patches1309	for the CONFIG_PREEMPT_RT environment.1310}1311}1312 1313@conference{PaulMcKenney05b1314,Author="Paul E. McKenney and Dipankar Sarma"1315,Title="Towards Hard Realtime Response from the {Linux} Kernel on {SMP} Hardware"1316,Booktitle="linux.conf.au 2005"1317,month="April"1318,year="2005"1319,address="Canberra, Australia"1320,note="Available:1321\url{http://www.rdrop.com/users/paulmck/RCU/realtimeRCU.2005.04.23a.pdf}1322[Viewed May 13, 2005]"1323,annotation={1324	Realtime turns into making RCU yet more realtime friendly.1325	http://lca2005.linux.org.au/Papers/Paul%20McKenney/Towards%20Hard%20Realtime%20Response%20from%20the%20Linux%20Kernel/LKS.2005.04.22a.pdf1326}1327}1328 1329@unpublished{PaulEMcKenneyHomePage1330,Author="Paul E. McKenney"1331,Title="{Paul} {E.} {McKenney}"1332,month="May"1333,year="2005"1334,note="Available:1335\url{http://www.rdrop.com/users/paulmck/}1336[Viewed May 25, 2005]"1337,annotation={1338	Paul McKenney's home page.1339}1340}1341 1342@unpublished{PaulEMcKenneyRCUPage1343,Author="Paul E. McKenney"1344,Title="Read-Copy Update {(RCU)}"1345,month="May"1346,year="2005"1347,note="Available:1348\url{http://www.rdrop.com/users/paulmck/RCU}1349[Viewed May 25, 2005]"1350,annotation={1351	Paul McKenney's RCU page.1352}1353}1354 1355@unpublished{JosephSeigh2005a1356,Author="Joseph Seigh"1357,Title="{RCU}+{SMR} (hazard pointers)"1358,month="July"1359,year="2005"1360,note="Personal communication"1361,annotation={1362	Joe Seigh announcing his atomic-ptr-plus project.1363	http://sourceforge.net/projects/atomic-ptr-plus/1364}1365}1366 1367@unpublished{JosephSeigh2005b1368,Author="Joseph Seigh"1369,Title="Lock-free synchronization primitives"1370,month="July"1371,day="6"1372,year="2005"1373,note="Available:1374\url{http://sourceforge.net/projects/atomic-ptr-plus/}1375[Viewed August 8, 2005]"1376,annotation={1377	Joe Seigh's atomic-ptr-plus project.1378}1379}1380 1381@unpublished{PaulMcKenney2005c1382,Author="Paul E.McKenney"1383,Title="{[RFC,PATCH] RCU} and {CONFIG\_PREEMPT\_RT} sane patch"1384,month="August"1385,day="1"1386,year="2005"1387,note="Available:1388\url{https://lore.kernel.org/r/20050801171137.GA1754@us.ibm.com}1389[Viewed March 14, 2006]"1390,annotation={1391	First operating counter-based realtime RCU patch posted to LKML.1392}1393}1394 1395@unpublished{PaulMcKenney2005d1396,Author="Paul E. McKenney"1397,Title="Re: [Fwd: Re: [patch] Real-Time Preemption, -RT-2.6.13-rc4-V0.7.52-01]"1398,month="August"1399,day="8"1400,year="2005"1401,note="Available:1402\url{https://lore.kernel.org/r/20050808144216.GA1307@us.ibm.com}1403[Viewed March 14, 2006]"1404,annotation={1405	First operating counter-based realtime RCU patch posted to LKML,1406	but fixed so that various unusual combinations of configuration1407	parameters all function properly.1408}1409}1410 1411@unpublished{PaulMcKenney2005rcutorture1412,Author="Paul E. McKenney"1413,Title="{[PATCH]} {RCU} torture testing"1414,month="October"1415,day="1"1416,year="2005"1417,note="Available:1418\url{https://lore.kernel.org/r/20051001182056.GA1613@us.ibm.com}1419[Viewed March 14, 2006]"1420,annotation={1421	First rcutorture patch.1422}1423}1424 1425@unpublished{DavidSMiller2006HashedLocking1426,Author="David S. Miller"1427,Title="Re: [{PATCH}, {RFC}] {RCU} : {OOM} avoidance and lower latency"1428,month="January"1429,day="6"1430,year="2006"1431,note="Available:1432\url{https://lore.kernel.org/r/20060106.231054.43576567.davem@davemloft.net}1433[Viewed February 29, 2012]"1434,annotation={1435	David Miller's view on hashed arrays of locks: used to really1436	like it, but time he saw an opportunity for this technique,1437	something else always proved superior.  Partitioning or RCU.  ;-)1438}1439}1440 1441@conference{ThomasEHart2006a1442,Author="Thomas E. Hart and Paul E. McKenney and Angela Demke Brown"1443,Title="Making Lockless Synchronization Fast: Performance Implications1444of Memory Reclamation"1445,Booktitle="20\textsuperscript{th} {IEEE} International Parallel and1446Distributed Processing Symposium"1447,month="April"1448,year="2006"1449,day="25-29"1450,address="Rhodes, Greece"1451,note="Available:1452\url{http://www.rdrop.com/users/paulmck/RCU/hart_ipdps06.pdf}1453[Viewed April 28, 2008]"1454,annotation={1455	Compares QSBR, HPBR, EBR, and lock-free reference counting.1456	http://www.cs.toronto.edu/~tomhart/perflab/ipdps06.tgz1457}1458}1459 1460@unpublished{NickPiggin2006radixtree1461,Author="Nick Piggin"1462,Title="[patch 3/3] radix-tree: {RCU} lockless readside"1463,month="June"1464,day="20"1465,year="2006"1466,note="Available:1467\url{https://lore.kernel.org/r/20060408134707.22479.33814.sendpatchset@linux.site}1468[Viewed March 25, 2008]"1469,annotation={1470	RCU-protected radix tree.1471}1472}1473 1474@Conference{PaulEMcKenney2006b1475,Author="Paul E. McKenney and Dipankar Sarma and Ingo Molnar and1476Suparna Bhattacharya"1477,Title="Extending {RCU} for Realtime and Embedded Workloads"1478,Booktitle="{Ottawa Linux Symposium}"1479,Month="July"1480,Year="2006"1481,pages="v2 123-138"1482,note="Available:1483\url{http://www.linuxsymposium.org/2006/view_abstract.php?content_key=184}1484\url{http://www.rdrop.com/users/paulmck/RCU/OLSrtRCU.2006.08.11a.pdf}1485[Viewed January 1, 2007]"1486,annotation={1487	Described how to improve the -rt implementation of realtime RCU.1488}1489}1490 1491@unpublished{WikipediaRCU1492,Author="Paul E. McKenney and Chris Purcell and Algae and Ben Schumin and1493Gaius Cornelius and Qwertyus and Neil Conway and Sbw and Blainster and1494Canis Rufus and Zoicon5 and Anome and Hal Eisen"1495,Title="Read-Copy Update"1496,month="July"1497,day="8"1498,year="2006"1499,note="\url{https://en.wikipedia.org/wiki/Read-copy-update}"1500,annotation={1501	Wikipedia RCU page as of July 8 2006.1502	[Viewed August 21, 2006]1503}1504}1505 1506@Conference{NickPiggin2006LocklessPageCache1507,Author="Nick Piggin"1508,Title="A Lockless Pagecache in Linux---Introduction, Progress, Performance"1509,Booktitle="{Ottawa Linux Symposium}"1510,Month="July"1511,Year="2006"1512,pages="v2 249-254"1513,note="Available:1514\url{http://www.linuxsymposium.org/2006/view_abstract.php?content_key=184}1515[Viewed January 11, 2009]"1516,annotation={1517	Uses RCU-protected radix tree for a lockless page cache.1518}1519}1520 1521@unpublished{PaulEMcKenney2006c1522,Author="Paul E. McKenney"1523,Title="Sleepable {RCU}"1524,month="October"1525,day="9"1526,year="2006"1527,note="Available:1528\url{http://lwn.net/Articles/202847/}1529Revised:1530\url{http://www.rdrop.com/users/paulmck/RCU/srcu.2007.01.14a.pdf}1531[Viewed August 21, 2006]"1532,annotation={1533	LWN article introducing SRCU.1534}1535}1536 1537@unpublished{RobertOlsson2006a1538,Author="Robert Olsson and Stefan Nilsson"1539,Title="{TRASH}: A dynamic {LC}-trie and hash data structure"1540,month="August"1541,day="18"1542,year="2006"1543,note="\url{http://www.nada.kth.se/~snilsson/publications/TRASH/trash.pdf}"1544,annotation={1545	RCU-protected dynamic trie-hash combination.1546	[Viewed March 4, 2011]1547}1548}1549 1550@unpublished{ChristophHellwig2006RCU2SRCU1551,Author="Christoph Hellwig"1552,Title="Re: {[-mm PATCH 1/4]} {RCU}: split classic rcu"1553,month="September"1554,day="28"1555,year="2006"1556,note="Available:1557\url{https://lore.kernel.org/r/20060928142616.GA20185@infradead.org}1558[Viewed March 27, 2008]"1559}1560 1561@unpublished{PaulEMcKenneyRCUusagePage1562,Author="Paul E. McKenney"1563,Title="{RCU} {Linux} Usage"1564,month="October"1565,year="2006"1566,note="Available:1567\url{http://www.rdrop.com/users/paulmck/RCU/linuxusage.html}1568[Viewed January 14, 2007]"1569,annotation={1570	Paul McKenney's RCU page showing graphs plotting Linux-kernel1571	usage of RCU.1572}1573}1574 1575@unpublished{PaulEMcKenneyRCUusageRawDataPage1576,Author="Paul E. McKenney"1577,Title="Read-Copy Update {(RCU)} Usage in {Linux} Kernel"1578,month="October"1579,year="2006"1580,note="Available:1581\url{http://www.rdrop.com/users/paulmck/RCU/linuxusage/rculocktab.html}1582[Viewed January 14, 2007]"1583,annotation={1584	Paul McKenney's RCU page showing Linux usage of RCU in tabular1585	form, with links to corresponding cscope databases.1586}1587}1588 1589@unpublished{GauthamShenoy2006RCUrwlock1590,Author="Gautham R. Shenoy"1591,Title="[PATCH 4/5] lock\_cpu\_hotplug: Redesign - Lightweight implementation of lock\_cpu\_hotplug"1592,month="October"1593,year="2006"1594,day=261595,note="Available:1596\url{https://lore.kernel.org/r/20061026105731.GE11803@in.ibm.com}1597[Viewed January 26, 2009]"1598,annotation={1599	RCU-based reader-writer lock that allows readers to proceed with1600	no memory barriers or atomic instruction in absence of writers.1601	If writer do show up, readers must of course wait as required by1602	the semantics of reader-writer locking.  This is a recursive1603	lock.1604}1605}1606 1607@unpublished{JensAxboe2006SlowSRCU1608,Author="Jens Axboe"1609,Title="Re: [patch] cpufreq: mark \url{cpufreq_tsc()} as1610\url{core_initcall_sync}"1611,month="November"1612,year="2006"1613,day=171614,note="Available:1615\url{https://lore.kernel.org/r/20061117092925.GT7164@kernel.dk}1616[Viewed May 28, 2007]"1617,annotation={1618	SRCU's grace periods are too slow for Jens, even after a1619	factor-of-three speedup.1620	Sped-up version of SRCU at https://lore.kernel.org/r/20061118002845.GF2632@us.ibm.com.1621}1622}1623 1624@unpublished{OlegNesterov2006QRCU1625,Author="Oleg Nesterov"1626,Title="Re: [patch] cpufreq: mark {\tt cpufreq\_tsc()} as1627{\tt core\_initcall\_sync}"1628,month="November"1629,year="2006"1630,day=191631,note="Available:1632\url{https://lore.kernel.org/r/20061119190027.GA3676@oleg}1633[Viewed May 28, 2007]"1634,annotation={1635	First cut of QRCU.  Expanded/corrected versions followed.1636	Used to be OlegNesterov2007QRCU, now time-corrected.1637}1638}1639 1640@unpublished{OlegNesterov2006aQRCU1641,Author="Oleg Nesterov"1642,Title="Re: [RFC, PATCH 1/2] qrcu: {"quick"} srcu implementation"1643,month="November"1644,year="2006"1645,day=301646,note="Available:1647\url{https://lore.kernel.org/r/20061130015714.GC1350@oleg}1648[Viewed November 26, 2008]"1649,annotation={1650	Expanded/corrected version of QRCU.1651	Used to be OlegNesterov2007aQRCU, now time-corrected.1652}1653}1654 1655@unpublished{EvgeniyPolyakov2006RCUslowdown1656,Author="Evgeniy Polyakov"1657,Title="Badness in postponing work"1658,month="December"1659,year="2006"1660,day=051661,note="Available:1662\url{http://www.ioremap.net/node/41}1663[Viewed October 28, 2008]"1664,annotation={1665	Using RCU as a pure delay leads to a 2.5x slowdown in skbs in1666	the Linux kernel.1667}1668}1669 1670@inproceedings{ChrisMatthews2006ClusteredObjectsRCU1671,author = {Matthews, Chris and Coady, Yvonne and Appavoo, Jonathan}1672,title = {Portability events: a programming model for scalable system infrastructures}1673,booktitle = {PLOS '06: Proceedings of the 3rd workshop on Programming languages and operating systems}1674,year = {2006}1675,isbn = {1-59593-577-0}1676,pages = {11}1677,location = {San Jose, California}1678,doi = {http://doi.acm.org/10.1145/1215995.1216006}1679,publisher = {ACM}1680,address = {New York, NY, USA}1681,annotation={1682	Uses K42's RCU-like functionality to manage clustered-object1683	lifetimes.1684}1685}1686 1687@article{DilmaDaSilva2006K421688,author = {Silva, Dilma Da and Krieger, Orran and Wisniewski, Robert W. and Waterland, Amos and Tam, David and Baumann, Andrew}1689,title = {K42: an infrastructure for operating system research}1690,journal = {SIGOPS Oper. Syst. Rev.}1691,volume = {40}1692,number = {2}1693,year = {2006}1694,issn = {0163-5980}1695,pages = {34--42}1696,doi = {http://doi.acm.org/10.1145/1131322.1131333}1697,publisher = {ACM}1698,address = {New York, NY, USA}1699,annotation={1700	Describes relationship of K42 generations to RCU.1701}1702}1703 1704# CoreyMinyard2007list_splice_rcu1705@unpublished{CoreyMinyard2007list:splice:rcu1706,Author="Corey Minyard and Paul E. McKenney"1707,Title="{[PATCH]} add an {RCU} version of list splicing"1708,month="January"1709,year="2007"1710,day=31711,note="Available:1712\url{https://lore.kernel.org/r/20070103152738.GA16063@localdomain}1713[Viewed May 28, 2007]"1714,annotation={1715	Patch for list_splice_rcu().1716}1717}1718 1719@unpublished{PaulEMcKenney2007rcubarrier1720,Author="Paul E. McKenney"1721,Title="{RCU} and Unloadable Modules"1722,month="January"1723,day="14"1724,year="2007"1725,note="Available:1726\url{http://lwn.net/Articles/217484/}1727[Viewed November 22, 2007]"1728,annotation={1729	LWN article introducing the rcu_barrier() primitive.1730}1731}1732 1733@unpublished{PeterZijlstra2007SyncBarrier1734,Author="Peter Zijlstra and Ingo Molnar"1735,Title="{[PATCH 3/7]} barrier: a scalable synchonisation barrier"1736,month="January"1737,year="2007"1738,day=281739,note="Available:1740\url{https://lore.kernel.org/r/20070128120509.719287000@programming.kicks-ass.net}1741[Viewed March 27, 2008]"1742,annotation={1743	RCU-like implementation for frequent updaters and rare readers(!).1744	Subsumed into QRCU.  Maybe...1745}1746}1747 1748@unpublished{PaulEMcKenney2007BoostRCU1749,Author="Paul E. McKenney"1750,Title="Priority-Boosting {RCU} Read-Side Critical Sections"1751,month="February"1752,day="5"1753,year="2007"1754,note="\url{http://lwn.net/Articles/220677/}"1755,annotation={1756	LWN article introducing RCU priority boosting.1757	Revised:1758	http://www.rdrop.com/users/paulmck/RCU/RCUbooststate.2007.04.16a.pdf1759	[Viewed September 7, 2007]1760}1761}1762 1763@unpublished{PaulMcKenney2007QRCUpatch1764,Author="Paul E. McKenney"1765,Title="{[PATCH]} {QRCU} with lockless fastpath"1766,month="February"1767,year="2007"1768,day=241769,note="Available:1770\url{https://lore.kernel.org/r/20070225062349.GA17468@linux.vnet.ibm.com}1771[Viewed March 27, 2008]"1772,annotation={1773	Patch for QRCU supplying lock-free fast path.1774}1775}1776 1777@article{JonathanAppavoo2007K42RCU1778,author = {Appavoo, Jonathan and Silva, Dilma Da and Krieger, Orran and Auslander, Marc and Ostrowski, Michal and Rosenburg, Bryan and Waterland, Amos and Wisniewski, Robert W. and Xenidis, Jimi and Stumm, Michael and Soares, Livio}1779,title = {Experience distributing objects in an SMMP OS}1780,journal = {ACM Trans. Comput. Syst.}1781,volume = {25}1782,number = {3}1783,year = {2007}1784,issn = {0734-2071}1785,pages = {6/1--6/52}1786,doi = {http://doi.acm.org/10.1145/1275517.1275518}1787,publisher = {ACM}1788,address = {New York, NY, USA}1789,annotation={1790	Role of RCU in K42.1791}1792}1793 1794@conference{RobertOlsson2007Trash1795,Author="Robert Olsson and Stefan Nilsson"1796,Title="{TRASH}: A dynamic {LC}-trie and hash data structure"1797,booktitle="Workshop on High Performance Switching and Routing (HPSR'07)"1798,month="May"1799,year="2007"1800,note="Available:1801\url{http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4281239}1802[Viewed October 1, 2010]"1803,annotation={1804	RCU-protected dynamic trie-hash combination.1805}1806}1807 1808@conference{PeterZijlstra2007ConcurrentPagecacheRCU1809,Author="Peter Zijlstra"1810,Title="Concurrent Pagecache"1811,Booktitle="Linux Symposium"1812,month="June"1813,year="2007"1814,address="Ottawa, Canada"1815,note="Available:1816\url{http://ols.108.redhat.com/2007/Reprints/zijlstra-Reprint.pdf}1817[Viewed April 14, 2008]"1818,annotation={1819	Page-cache modifications permitting RCU readers and concurrent1820	updates.1821}1822}1823 1824@unpublished{PaulEMcKenney2007whatisRCU1825,Author="Paul E. McKenney"1826,Title="What is {RCU}?"1827,year="2007"1828,month="07"1829,note="Available:1830\url{http://www.rdrop.com/users/paulmck/RCU/whatisRCU.html}1831[Viewed July 6, 2007]"1832,annotation={1833	Describes RCU in Linux kernel.1834}1835}1836 1837@unpublished{PaulEMcKenney2007QRCUspin1838,Author="Paul E. McKenney"1839,Title="Using {Promela} and {Spin} to verify parallel algorithms"1840,month="August"1841,day="1"1842,year="2007"1843,note="Available:1844\url{http://lwn.net/Articles/243851/}1845[Viewed September 8, 2007]"1846,annotation={1847	LWN article describing Promela and spin, and also using Oleg1848	Nesterov's QRCU as an example (with Paul McKenney's fastpath).1849	Merged patch at: https://lore.kernel.org/r/20070225062349.GA17468@linux.vnet.ibm.com1850}1851}1852 1853@unpublished{PaulEMcKenney2007WG21DDOatomics1854,Author="Paul E. McKenney and Hans-J. Boehm and Lawrence Crowl"1855,Title="C++ Data-Dependency Ordering: Atomics and Memory Model"1856,month="August"1857,day="3"1858,year="2007"1859,note="Available:1860\url{http://open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2664.htm}1861[Viewed December 7, 2009]"1862,annotation={1863	RCU for C++, parts 1 and 2.1864}1865}1866 1867@unpublished{PaulEMcKenney2007WG21DDOannotation1868,Author="Paul E. McKenney and Lawrence Crowl"1869,Title="C++ Data-Dependency Ordering: Function Annotation"1870,month="September"1871,day="18"1872,year="2008"1873,note="Available:1874\url{http://open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2782.htm}1875[Viewed December 7, 2009]"1876,annotation={1877	RCU for C++, part 2, updated many times.1878}1879}1880 1881@unpublished{PaulEMcKenney2007PreemptibleRCUPatch1882,Author="Paul E. McKenney"1883,Title="[PATCH RFC 0/9] {RCU}: Preemptible {RCU}"1884,month="September"1885,day="10"1886,year="2007"1887,note="Available:1888\url{https://lore.kernel.org/r/20070910183004.GA3299@linux.vnet.ibm.com}1889[Viewed October 25, 2007]"1890,annotation={1891	Final patch for preemptible RCU to -rt.  (Later patches were1892	to mainline, eventually incorporated.)1893}1894}1895 1896@unpublished{PaulEMcKenney2007PreemptibleRCU1897,Author="Paul E. McKenney"1898,Title="The design of preemptible read-copy-update"1899,month="October"1900,day="8"1901,year="2007"1902,note="Available:1903\url{http://lwn.net/Articles/253651/}1904[Viewed October 25, 2007]"1905,annotation={1906	LWN article describing the design of preemptible RCU.1907}1908}1909 1910@article{ThomasEHart2007a1911,Author="Thomas E. Hart and Paul E. McKenney and Angela Demke Brown and Jonathan Walpole"1912,Title="Performance of memory reclamation for lockless synchronization"1913,journal="J. Parallel Distrib. Comput."1914,volume={67}1915,number="12"1916,year="2007"1917,issn="0743-7315"1918,pages="1270--1285"1919,doi="http://dx.doi.org/10.1016/j.jpdc.2007.04.010"1920,publisher="Academic Press, Inc."1921,address="Orlando, FL, USA"1922,annotation={1923	Compares QSBR, HPBR, EBR, and lock-free reference counting.1924	Journal version of ThomasEHart2006a.1925}1926}1927 1928# MathieuDesnoyers2007call_rcu_schedNeeded1929@unpublished{MathieuDesnoyers2007call:rcu:schedNeeded1930,Author="Mathieu Desnoyers"1931,Title="Re: [patch 1/2] {Linux} Kernel Markers - Support Multiple Probes"1932,month="December"1933,day="20"1934,year="2007"1935,note="Available:1936\url{https://lore.kernel.org/r/20071220142540.GB22523@Krystal}1937[Viewed March 27, 2008]"1938,annotation={1939	Request for call_rcu_sched() and rcu_barrier_sched().1940}1941}1942 1943 1944########################################################################1945#1946#	"What is RCU?" LWN series.1947#1948#	http://lwn.net/Articles/262464/ (What is RCU, Fundamentally?)1949#	http://lwn.net/Articles/263130/ (What is RCU's Usage?)1950#	http://lwn.net/Articles/264090/ (What is RCU's API?)1951 1952@unpublished{PaulEMcKenney2007WhatIsRCUFundamentally1953,Author="Paul E. McKenney and Jonathan Walpole"1954,Title="What is {RCU}, Fundamentally?"1955,month="December"1956,day="17"1957,year="2007"1958,note="Available:1959\url{http://lwn.net/Articles/262464/}1960[Viewed December 27, 2007]"1961,annotation={1962	Lays out the three basic components of RCU: (1) publish-subscribe,1963	(2) wait for pre-existing readers to complete, and (2) maintain1964	multiple versions.1965}1966}1967 1968@unpublished{PaulEMcKenney2008WhatIsRCUUsage1969,Author="Paul E. McKenney"1970,Title="What is {RCU}? Part 2: Usage"1971,month="January"1972,day="4"1973,year="2008"1974,note="Available:1975\url{http://lwn.net/Articles/263130/}1976[Viewed January 4, 2008]"1977,annotation={1978	Lays out six uses of RCU:1979	1. RCU is a Reader-Writer Lock Replacement1980	2. RCU is a Restricted Reference-Counting Mechanism1981	3. RCU is a Bulk Reference-Counting Mechanism1982	4. RCU is a Poor Man's Garbage Collector1983	5. RCU is a Way of Providing Existence Guarantees1984	6. RCU is a Way of Waiting for Things to Finish1985}1986}1987 1988@unpublished{PaulEMcKenney2008WhatIsRCUAPI1989,Author="Paul E. McKenney"1990,Title="{RCU} part 3: the {RCU} {API}"1991,month="January"1992,day="17"1993,year="2008"1994,note="Available:1995\url{http://lwn.net/Articles/264090/}1996[Viewed January 10, 2008]"1997,annotation={1998	Gives an overview of the Linux-kernel RCU API and a brief annotated RCU1999	bibliography.2000}2001}2002 2003#2004#	"What is RCU?" LWN series.2005#2006########################################################################2007 2008 2009@unpublished{SteveRostedt2008dyntickRCUpatch2010,Author="Steven Rostedt and Paul E. McKenney"2011,Title="{[PATCH]} add support for dynamic ticks and preempt rcu"2012,month="January"2013,day="29"2014,year="2008"2015,note="Available:2016\url{https://lore.kernel.org/r/Pine.LNX.4.58.0801291113350.20371@gandalf.stny.rr.com}2017[Viewed March 27, 2008]"2018,annotation={2019	Patch that prevents preemptible RCU from unnecessarily waking2020	up dynticks-idle CPUs.2021}2022}2023 2024@unpublished{PaulEMcKenney2008LKMLDependencyOrdering2025,Author="Paul E. McKenney"2026,Title="Re: [PATCH 02/22 -v7] Add basic support for gcc profiler instrumentation"2027,month="February"2028,day="1"2029,year="2008"2030,note="Available:2031\url{https://lore.kernel.org/r/20080202214124.GA28612@linux.vnet.ibm.com}2032[Viewed October 18, 2008]"2033,annotation={2034	Explanation of compilers violating dependency ordering.2035}2036}2037 2038@Conference{PaulEMcKenney2008Beijing2039,Author="Paul E. McKenney"2040,Title="Introducing Technology Into {Linux} Or:2041Introducing your technology Into {Linux} will require introducing a2042lot of {Linux} into your technology!!!"2043,Booktitle="2008 Linux Developer Symposium - China"2044,Publisher="OSS China"2045,Month="February"2046,Year="2008"2047,Address="Beijing, China"2048,note="Available:2049\url{http://www.rdrop.com/users/paulmck/RCU/TechIntroLinux.2008.02.19a.pdf}2050[Viewed August 12, 2008]"2051}2052 2053@unpublished{PaulEMcKenney2008dynticksRCU2054,Author="Paul E. McKenney and Steven Rostedt"2055,Title="Integrating and Validating dynticks and Preemptable RCU"2056,month="April"2057,day="24"2058,year="2008"2059,note="Available:2060\url{http://lwn.net/Articles/279077/}2061[Viewed April 24, 2008]"2062,annotation={2063	Describes use of Promela and Spin to validate (and fix!) the2064	dynticks/RCU interface.2065}2066}2067 2068@article{DinakarGuniguntala2008IBMSysJ2069,author="D. Guniguntala and P. E. McKenney and J. Triplett and J. Walpole"2070,title="The read-copy-update mechanism for supporting real-time applications on shared-memory multiprocessor systems with {Linux}"2071,Year="2008"2072,Month="May"2073,journal="IBM Systems Journal"2074,volume="47"2075,number="2"2076,pages="221-236"2077,annotation={2078	RCU, realtime RCU, sleepable RCU, performance.2079	http://www.research.ibm.com/journal/sj/472/guniguntala.pdf2080	[Viewed April 24, 2008]2081}2082}2083 2084@unpublished{LaiJiangshan2008NewClassicAlgorithm2085,Author="Lai Jiangshan"2086,Title="[{RFC}][{PATCH}] rcu classic: new algorithm for callbacks-processing"2087,month="June"2088,day="3"2089,year="2008"2090,note="Available:2091\url{https://lore.kernel.org/r/4844BE83.5010401@cn.fujitsu.com}2092[Viewed December 10, 2008]"2093,annotation={2094	Updated RCU classic algorithm.  Introduced multi-tailed list2095	for RCU callbacks and also pulling common code into2096	__call_rcu().2097}2098}2099 2100@article{PaulEMcKenney2008RCUOSR2101,author="Paul E. McKenney and Jonathan Walpole"2102,title="Introducing technology into the {Linux} kernel: a case study"2103,Year="2008"2104,journal="SIGOPS Oper. Syst. Rev."2105,volume="42"2106,number="5"2107,pages="4--17"2108,issn="0163-5980"2109,doi={http://doi.acm.org/10.1145/1400097.1400099}2110,publisher="ACM"2111,address="New York, NY, USA"2112,annotation={2113	Linux changed RCU to a far greater degree than RCU has changed Linux.2114	http://portal.acm.org/citation.cfm?doid=1400097.14000992115}2116}2117 2118@unpublished{ManfredSpraul2008StateMachineRCU2119,Author="Manfred Spraul"2120,Title="[{RFC}, {PATCH}] state machine based rcu"2121,month="August"2122,day="21"2123,year="2008"2124,note="Available:2125\url{https://lore.kernel.org/r/48AD8969.7060900@colorfullife.com}2126[Viewed December 8, 2008]"2127,annotation={2128	State-based RCU.  One key thing that this patch does is to2129	separate the dynticks handling of NMIs and IRQs.2130}2131}2132 2133@unpublished{ManfredSpraul2008dyntickIRQNMI2134,Author="Manfred Spraul"2135,Title="Re: [{RFC}, {PATCH}] v4 scalable classic {RCU} implementation"2136,month="September"2137,day="6"2138,year="2008"2139,note="Available:2140\url{https://lore.kernel.org/r/48C2B1D2.5070801@colorfullife.com}2141[Viewed December 8, 2008]"2142,annotation={2143	Manfred notes a fix required to my attempt to separate irq2144	and NMI processing for hierarchical RCU's dynticks interface.2145}2146}2147 2148# Was PaulEMcKenney2011cyclicRCU2149@techreport{PaulEMcKenney2008cyclicRCU2150,author="Paul E. McKenney"2151,title="Efficient Support of Consistent Cyclic Search With Read-Copy Update"2152,institution="US Patent and Trademark Office"2153,address="Washington, DC"2154,year="2008"2155,number="US Patent 7,426,511"2156,month="September"2157,pages="23"2158,annotation={2159	Maintains an additional level of indirection to allow2160	readers to confine themselves to the desired snapshot of the2161	data structure.  Only permits one update at a time.2162}2163}2164 2165@unpublished{PaulEMcKenney2008HierarchicalRCU2166,Author="Paul E. McKenney"2167,Title="Hierarchical {RCU}"2168,month="November"2169,day="3"2170,year="2008"2171,note="\url{http://lwn.net/Articles/305782/}"2172,annotation={2173	RCU with combining-tree-based grace-period detection,2174	permitting it to handle thousands of CPUs.2175	[Viewed November 6, 2008]2176}2177}2178 2179@unpublished{PaulEMcKenney2009BloatwatchRCU2180,Author="Paul E. McKenney"2181,Title="Re: [PATCH fyi] RCU: the bloatwatch edition"2182,month="January"2183,day="14"2184,year="2009"2185,note="Available:2186\url{https://lore.kernel.org/r/20090114202044.GJ6734@linux.vnet.ibm.com}2187[Viewed January 15, 2009]"2188,annotation={2189	Small-footprint implementation of RCU for uniprocessor2190	embedded applications -- and also for exposition purposes.2191}2192}2193 2194@conference{PaulEMcKenney2009MaliciousURCU2195,Author="Paul E. McKenney"2196,Title="Using a Malicious User-Level {RCU} to Torture {RCU}-Based Algorithms"2197,Booktitle="linux.conf.au 2009"2198,month="January"2199,year="2009"2200,address="Hobart, Australia"2201,note="Available:2202\url{http://www.rdrop.com/users/paulmck/RCU/urcutorture.2009.01.22a.pdf}2203[Viewed February 2, 2009]"2204,annotation={2205	Realtime RCU and torture-testing RCU uses.2206}2207}2208 2209@unpublished{MathieuDesnoyers2009URCU2210,Author="Mathieu Desnoyers"2211,Title="[{RFC} git tree] Userspace {RCU} (urcu) for {Linux}"2212,month="February"2213,day="5"2214,year="2009"2215,note="\url{http://lttng.org/urcu}"2216,annotation={2217	Mathieu Desnoyers's user-space RCU implementation.2218	git://lttng.org/userspace-rcu.git2219	http://lttng.org/cgi-bin/gitweb.cgi?p=userspace-rcu.git2220	http://lttng.org/urcu2221	https://lore.kernel.org/r/20090206030543.GB8560@Krystal2222}2223}2224 2225@unpublished{PaulEMcKenney2009LWNBloatWatchRCU2226,Author="Paul E. McKenney"2227,Title="{RCU}: The {Bloatwatch} Edition"2228,month="March"2229,day="17"2230,year="2009"2231,note="Available:2232\url{http://lwn.net/Articles/323929/}2233[Viewed March 20, 2009]"2234,annotation={2235	Uniprocessor assumptions allow simplified RCU implementation.2236}2237}2238 2239@unpublished{EvgeniyPolyakov2009EllipticsNetwork2240,Author="Evgeniy Polyakov"2241,Title="The Elliptics Network"2242,month="April"2243,day="17"2244,year="2009"2245,note="Available:2246\url{http://www.ioremap.net/projects/elliptics}2247[Viewed April 30, 2009]"2248,annotation={2249	Distributed hash table with transactions, using elliptic2250	hash functions to distribute data.2251}2252}2253 2254@unpublished{PaulEMcKenney2009expeditedRCU2255,Author="Paul E. McKenney"2256,Title="[{PATCH} -tip 0/3] expedited 'big hammer' {RCU} grace periods"2257,month="June"2258,day="25"2259,year="2009"2260,note="Available:2261\url{https://lore.kernel.org/r/20090625160706.GA9467@linux.vnet.ibm.com}2262[Viewed August 16, 2009]"2263,annotation={2264	First posting of expedited RCU to be accepted into -tip.2265}2266}2267 2268@unpublished{PaulEMcKenney2009fastRTRCU2269,Author="Paul E. McKenney"2270,Title="[{PATCH} {RFC} -tip 0/4] {RCU} cleanups and simplified preemptable {RCU}"2271,month="July"2272,day="23"2273,year="2009"2274,note="Available:2275\url{https://lore.kernel.org/r/20090724001429.GA17374@linux.vnet.ibm.com}2276[Viewed August 15, 2009]"2277,annotation={2278	First posting of simple and fast preemptible RCU.2279}2280}2281 2282@unpublished{JoshTriplett2009RPHash2283,Author="Josh Triplett"2284,Title="Scalable concurrent hash tables via relativistic programming"2285,month="September"2286,year="2009"2287,note="Linux Plumbers Conference presentation"2288,annotation={2289	RP fun with hash tables.2290	Superseded by JoshTriplett2010RPHash2291}2292}2293 2294@phdthesis{MathieuDesnoyersPhD2295, title  = "Low-Impact Operating System Tracing"2296, author = "Mathieu Desnoyers"2297, school = "Ecole Polytechnique de Montr\'{e}al"2298, month  = "December"2299, year   = 20092300,note="Available:2301\url{http://www.lttng.org/pub/thesis/desnoyers-dissertation-2009-12.pdf}2302[Viewed December 9, 2009]"2303,annotation={2304	Chapter 6 (page 97) covers user-level RCU.2305}2306}2307 2308@unpublished{RelativisticProgrammingWiki2309,Author="Josh Triplett and Paul E. McKenney and Jonathan Walpole"2310,Title="Relativistic Programming"2311,month="September"2312,year="2009"2313,note="Available:2314\url{http://wiki.cs.pdx.edu/rp/}2315[Viewed December 9, 2009]"2316,annotation={2317	Main Relativistic Programming Wiki.2318}2319}2320 2321@conference{PaulEMcKenney2009DeterministicRCU2322,Author="Paul E. McKenney"2323,Title="Deterministic Synchronization in Multicore Systems: the Role of {RCU}"2324,Booktitle="Eleventh Real Time Linux Workshop"2325,month="September"2326,year="2009"2327,address="Dresden, Germany"2328,note="Available:2329\url{http://www.rdrop.com/users/paulmck/realtime/paper/DetSyncRCU.2009.08.18a.pdf}2330[Viewed January 14, 2009]"2331}2332 2333@unpublished{PaulEMcKenney2009HuntingHeisenbugs2334,Author="Paul E. McKenney"2335,Title="Hunting Heisenbugs"2336,month="November"2337,year="2009"2338,day="1"2339,note="Available:2340\url{http://paulmck.livejournal.com/14639.html}2341[Viewed June 4, 2010]"2342,annotation={2343	Day-one bug in Tree RCU that took forever to track down.2344}2345}2346 2347@unpublished{MathieuDesnoyers2009defer:rcu2348,Author="Mathieu Desnoyers"2349,Title="Kernel RCU: shrink the size of the struct rcu\_head"2350,month="December"2351,year="2009"2352,note="Available:2353\url{https://lore.kernel.org/r/20091018232918.GA7385@Krystal}2354[Viewed December 29, 2009]"2355,annotation={2356	Mathieu proposed defer_rcu() with fixed-size per-thread pool2357	of RCU callbacks.2358}2359}2360 2361@unpublished{MathieuDesnoyers2009VerifPrePub2362,Author="Mathieu Desnoyers and Paul E. McKenney and Michel R. Dagenais"2363,Title="Multi-Core Systems Modeling for Formal Verification of Parallel Algorithms"2364,month="December"2365,year="2009"2366,note="Submitted to IEEE TPDS"2367,annotation={2368	OOMem model for Mathieu's user-level RCU mechanical proof of2369	correctness.2370}2371}2372 2373@unpublished{MathieuDesnoyers2009URCUPrePub2374,Author="Mathieu Desnoyers and Paul E. McKenney and Alan Stern and Michel R. Dagenais and Jonathan Walpole"2375,Title="User-Level Implementations of Read-Copy Update"2376,month="December"2377,year="2010"2378,url={\url{http://www.computer.org/csdl/trans/td/2012/02/ttd2012020375-abs.html}}2379,annotation={2380	RCU overview, desiderata, semi-formal semantics, user-level RCU2381	usage scenarios, three classes of RCU implementation, wait-free2382	RCU updates, RCU grace-period batching, update overhead,2383	http://www.rdrop.com/users/paulmck/RCU/urcu-main-accepted.2011.08.30a.pdf2384	http://www.rdrop.com/users/paulmck/RCU/urcu-supp-accepted.2011.08.30a.pdf2385	Superseded by MathieuDesnoyers2012URCU.2386}2387}2388 2389@inproceedings{HariKannan2009DynamicAnalysisRCU2390,author = {Kannan, Hari}2391,title = {Ordering decoupled metadata accesses in multiprocessors}2392,booktitle = {MICRO 42: Proceedings of the 42nd Annual IEEE/ACM International Symposium on Microarchitecture}2393,year = {2009}2394,isbn = {978-1-60558-798-1}2395,pages = {381--390}2396,location = {New York, New York}2397,doi = {http://doi.acm.org/10.1145/1669112.1669161}2398,publisher = {ACM}2399,address = {New York, NY, USA}2400,annotation={2401	Uses RCU to protect metadata used in dynamic analysis.2402}2403}2404 2405@conference{PaulEMcKenney2010SimpleOptRCU2406,Author="Paul E. McKenney"2407,Title="Simplicity Through Optimization"2408,Booktitle="linux.conf.au 2010"2409,month="January"2410,year="2010"2411,address="Wellington, New Zealand"2412,note="Available:2413\url{http://www.rdrop.com/users/paulmck/RCU/SimplicityThruOptimization.2010.01.21f.pdf}2414[Viewed October 10, 2010]"2415,annotation={2416	TREE_PREEMPT_RCU optimizations greatly simplified the old2417	PREEMPT_RCU implementation.2418}2419}2420 2421@unpublished{PaulEMcKenney2010LockdepRCU2422,Author="Paul E. McKenney"2423,Title="Lockdep-{RCU}"2424,month="February"2425,year="2010"2426,day="1"2427,note="\url{https://lwn.net/Articles/371986/}"2428,annotation={2429	CONFIG_PROVE_RCU, or at least an early version.2430	[Viewed June 4, 2010]2431}2432}2433 2434@unpublished{AviKivity2010KVM2RCU2435,Author="Avi Kivity"2436,Title="[{PATCH} 37/40] {KVM}: Bump maximum vcpu count to 64"2437,month="February"2438,year="2010"2439,note="Available:2440\url{http://www.mail-archive.com/kvm@vger.kernel.org/msg28640.html}2441[Viewed March 20, 2010]"2442,annotation={2443	Use of RCU permits KVM to increase the size of guest OSes from2444	16 CPUs to 64 CPUs.2445}2446}2447 2448@unpublished{HerbertXu2010RCUResizeHash2449,Author="Herbert Xu"2450,Title="bridge: Add core IGMP snooping support"2451,month="February"2452,year="2010"2453,note="Available:2454\url{http://thread.gmane.org/gmane.linux.network/153338}2455[Viewed June 9, 2014]"2456,annotation={2457	Use a pair of list_head structures to support RCU-protected2458	resizable hash tables.2459}2460}2461 2462@mastersthesis{AbhinavDuggal2010Masters2463,author="Abhinav Duggal"2464,title="Stopping Data Races Using Redflag"2465,school="Stony Brook University"2466,year="2010"2467,annotation={2468	Data-race detector incorporating RCU.2469	http://www.filesystems.org/docs/abhinav-thesis/abhinav_thesis.pdf2470}2471}2472 2473@article{JoshTriplett2010RPHash2474,author="Josh Triplett and Paul E. McKenney and Jonathan Walpole"2475,title="Scalable Concurrent Hash Tables via Relativistic Programming"2476,journal="ACM Operating Systems Review"2477,year=20102478,volume=442479,number=32480,month="July"2481,annotation={2482	RP fun with hash tables.2483	http://portal.acm.org/citation.cfm?id=1842733.18427502484}2485}2486 2487@unpublished{PaulEMcKenney2010RCUAPI2488,Author="Paul E. McKenney"2489,Title="The {RCU} {API}, 2010 Edition"2490,month="December"2491,day="8"2492,year="2010"2493,note="\url{http://lwn.net/Articles/418853/}"2494,annotation={2495	Includes updated software-engineering features.2496	[Viewed December 8, 2010]2497}2498}2499 2500@mastersthesis{AndrejPodzimek2010masters2501,author="Andrej Podzimek"2502,title="Read-Copy-Update for OpenSolaris"2503,school="Charles University in Prague"2504,year="2010"2505,note="Available:2506\url{https://andrej.podzimek.org/thesis.pdf}2507[Viewed January 31, 2011]"2508,annotation={2509	Reviews RCU implementations and creates a few for OpenSolaris.2510	Drives quiescent-state detection from RCU read-side primitives,2511	in a manner roughly similar to that of Jim Houston.2512}2513}2514 2515@unpublished{LinusTorvalds2011Linux2:6:38:rc1:NPigginVFS2516,Author="Linus Torvalds"2517,Title="Linux 2.6.38-rc1"2518,month="January"2519,year="2011"2520,note="Available:2521\url{https://lore.kernel.org/r/AANLkTimajU0x1v6y3rH2+jr-bZ=tNLs1S_agXdGGAa3S@mail.gmail.com}2522[Viewed March 4, 2011]"2523,annotation={2524	"The RCU-based name lookup is at the other end of the spectrum - the2525	absolute anti-gimmick. It's some seriously good stuff, and gets rid of2526	the last main global lock that really tends to hurt some kernel loads.2527	The dentry lock is no longer a big serializing issue. What's really2528	nice about it is that it actually improves performance a lot even for2529	single-threaded loads (on an SMP kernel), because it gets rid of some2530	of the most expensive parts of path component lookup, which was the2531	d_lock on every component lookup. So I'm seeing improvements of 30-50%2532	on some seriously pathname-lookup intensive loads."2533}2534}2535 2536@techreport{JoshTriplett2011RPScalableCorrectOrdering2537,author = {Josh Triplett and Philip W. Howard and Paul E. McKenney and Jonathan Walpole}2538,title = {Scalable Correct Memory Ordering via Relativistic Programming}2539,year = {2011}2540,number = {11-03}2541,institution = {Portland State University}2542,note = {\url{http://www.cs.pdx.edu/pdfs/tr1103.pdf}}2543}2544 2545@inproceedings{PhilHoward2011RCUTMRBTree2546,author = {Philip W. Howard and Jonathan Walpole}2547,title = {A Relativistic Enhancement to Software Transactional Memory}2548,booktitle = {Proceedings of the 3rd USENIX conference on Hot topics in parallelism}2549,series = {HotPar'11}2550,year = {2011}2551,location = {Berkeley, CA}2552,pages = {1--6}2553,numpages = {6}2554,url = {http://www.usenix.org/event/hotpar11/tech/final_files/Howard.pdf}2555,publisher = {USENIX Association}2556,address = {Berkeley, CA, USA}2557}2558 2559@techreport{PaulEMcKenney2011cyclicparallelRCU2560,author="Paul E. McKenney and Jonathan Walpole"2561,title="Efficient Support of Consistent Cyclic Search With Read-Copy Update and Parallel Updates"2562,institution="US Patent and Trademark Office"2563,address="Washington, DC"2564,year="2011"2565,number="US Patent 7,953,778"2566,month="May"2567,pages="34"2568,annotation={2569	Maintains an array of generation numbers to track in-flight2570	updates and keeps an additional level of indirection to allow2571	readers to confine themselves to the desired snapshot of the2572	data structure.2573}2574}2575 2576@inproceedings{Triplett:2011:RPHash2577,author = {Triplett, Josh and McKenney, Paul E. and Walpole, Jonathan}2578,title = {Resizable, Scalable, Concurrent Hash Tables via Relativistic Programming}2579,booktitle = {Proceedings of the 2011 USENIX Annual Technical Conference}2580,month = {June}2581,year = {2011}2582,pages = {145--158}2583,numpages = {14}2584,url={http://www.usenix.org/event/atc11/tech/final_files/Triplett.pdf}2585,publisher = {The USENIX Association}2586,address = {Portland, OR USA}2587}2588 2589@unpublished{PaulEMcKenney2011RCU3.0trainwreck2590,Author="Paul E. McKenney"2591,Title="3.0 and {RCU:} what went wrong"2592,month="July"2593,day="27"2594,year="2011"2595,note="\url{http://lwn.net/Articles/453002/}"2596,annotation={2597	Analysis of the RCU trainwreck in Linux kernel 3.0.2598	[Viewed July 27, 2011]2599}2600}2601 2602@unpublished{NeilBrown2011MeetTheLockers2603,Author="Neil Brown"2604,Title="Meet the {Lockers}"2605,month="August"2606,day="3"2607,year="2011"2608,note="Available:2609\url{http://lwn.net/Articles/453685/}2610[Viewed September 2, 2011]"2611,annotation={2612	The Locker family as an analogy for locking, reference counting,2613	RCU, and seqlock.2614}2615}2616 2617@inproceedings{Seyster:2011:RFA:2075416.20754252618,author = {Seyster, Justin and Radhakrishnan, Prabakar and Katoch, Samriti and Duggal, Abhinav and Stoller, Scott D. and Zadok, Erez}2619,title = {Redflag: a framework for analysis of Kernel-level concurrency}2620,booktitle = {Proceedings of the 11th international conference on Algorithms and architectures for parallel processing - Volume Part I}2621,series = {ICA3PP'11}2622,year = {2011}2623,isbn = {978-3-642-24649-4}2624,location = {Melbourne, Australia}2625,pages = {66--79}2626,numpages = {14}2627,url = {http://dl.acm.org/citation.cfm?id=2075416.2075425}2628,acmid = {2075425}2629,publisher = {Springer-Verlag}2630,address = {Berlin, Heidelberg}2631}2632 2633@phdthesis{JoshTriplettPhD2634,author="Josh Triplett"2635,title="Relativistic Causal Ordering: A Memory Model for Scalable Concurrent Data Structures"2636,school="Portland State University"2637,year="2012"2638,annotation={2639	RCU-protected hash tables, barriers vs. read-side traversal order.2640	.2641	If the updater is making changes in the opposite direction from2642	the read-side traversal order, the updater need only execute a2643	memory-barrier instruction, but if in the same direction, the2644	updater needs to wait for a grace period between the individual2645	updates.2646}2647}2648 2649@article{MathieuDesnoyers2012URCU2650,Author="Mathieu Desnoyers and Paul E. McKenney and Alan Stern and Michel R. Dagenais and Jonathan Walpole"2651,Title="User-Level Implementations of Read-Copy Update"2652,journal="IEEE Transactions on Parallel and Distributed Systems"2653,volume={23}2654,year="2012"2655,issn="1045-9219"2656,pages="375-382"2657,doi="http://doi.ieeecomputersociety.org/10.1109/TPDS.2011.159"2658,publisher="IEEE Computer Society"2659,address="Los Alamitos, CA, USA"2660,annotation={2661	RCU overview, desiderata, semi-formal semantics, user-level RCU2662	usage scenarios, three classes of RCU implementation, wait-free2663	RCU updates, RCU grace-period batching, update overhead,2664	http://www.rdrop.com/users/paulmck/RCU/urcu-main-accepted.2011.08.30a.pdf2665	http://www.rdrop.com/users/paulmck/RCU/urcu-supp-accepted.2011.08.30a.pdf2666	http://www.computer.org/cms/Computer.org/dl/trans/td/2012/02/extras/ttd2012020375s.pdf2667}2668}2669 2670@inproceedings{AustinClements2012RCULinux:mmapsem2671,author = {Austin Clements and Frans Kaashoek and Nickolai Zeldovich}2672,title = {Scalable Address Spaces Using {RCU} Balanced Trees}2673,booktitle = {Architectural Support for Programming Languages and Operating Systems (ASPLOS 2012)}2674,month = {March}2675,year = {2012}2676,pages = {199--210}2677,numpages = {12}2678,publisher = {ACM}2679,address = {London, UK}2680,url="http://people.csail.mit.edu/nickolai/papers/clements-bonsai.pdf"2681}2682 2683@unpublished{PaulEMcKenney2012ELCbattery2684,Author="Paul E. McKenney"2685,Title="Making {RCU} Safe For Battery-Powered Devices"2686,month="February"2687,day="15"2688,year="2012"2689,note="Available:2690\url{http://www.rdrop.com/users/paulmck/RCU/RCUdynticks.2012.02.15b.pdf}2691[Viewed March 1, 2012]"2692,annotation={2693	RCU_FAST_NO_HZ, round 2.2694}2695}2696 2697@article{GuillermoVigueras2012RCUCrowd2698,author = {Vigueras, Guillermo and Ordu\~{n}a, Juan M. and Lozano, Miguel}2699,day = {25}2700,doi = {10.1007/s11227-012-0766-x}2701,issn = {0920-8542}2702,journal = {The Journal of Supercomputing}2703,keywords = {linux, simulation}2704,month = apr2705,posted-at = {2012-05-03 09:12:04}2706,priority = {2}2707,title = {{A Read-Copy Update based parallel server for distributed crowd simulations}}2708,url = {http://dx.doi.org/10.1007/s11227-012-0766-x}2709,year = {2012}2710}2711 2712 2713@unpublished{JonCorbet2012ACCESS:ONCE2714,Author="Jon Corbet"2715,Title="{ACCESS\_ONCE()}"2716,month="August"2717,day="1"2718,year="2012"2719,note="\url{http://lwn.net/Articles/508991/}"2720,annotation={2721	A couple of simple specific compiler optimizations that motivate2722	ACCESS_ONCE().2723}2724}2725 2726@unpublished{AlexeyGotsman2012VerifyGraceExtended2727,Author="Alexey Gotsman and Noam Rinetzky and Hongseok Yang"2728,Title="Verifying Highly Concurrent Algorithms with Grace (extended version)"2729,month="July"2730,day="10"2731,year="2012"2732,note="\url{http://software.imdea.org/~gotsman/papers/recycling-esop13-ext.pdf}"2733,annotation={2734	Separation-logic formulation of RCU uses.2735}2736}2737 2738@unpublished{PaulMcKenney2012RCUUsage2739,Author="Paul E. McKenney and Silas Boyd-Wickizer and Jonathan Walpole"2740,Title="{RCU} Usage In the Linux Kernel: One Decade Later"2741,month="September"2742,day="17"2743,year="2012"2744,url=http://rdrop.com/users/paulmck/techreports/survey.2012.09.17a.pdf2745,note="Technical report paulmck.2012.09.17"2746,annotation={2747	Overview of the first variant of no-CBs CPUs for RCU.2748}2749}2750 2751@unpublished{JonCorbet2012NOCB2752,Author="Jon Corbet"2753,Title="Relocating RCU callbacks"2754,month="October"2755,day="31"2756,year="2012"2757,note="\url{http://lwn.net/Articles/522262/}"2758,annotation={2759	Overview of the first variant of no-CBs CPUs for RCU.2760}2761}2762 2763@phdthesis{JustinSeyster2012PhD2764,author="Justin Seyster"2765,title="Runtime Verification of Kernel-Level Concurrency Using Compiler-Based Instrumentation"2766,school="Stony Brook University"2767,year="2012"2768,annotation={2769	Looking for data races, including those involving RCU.2770	Proposal:2771	http://www.fsl.cs.sunysb.edu/docs/jseyster-proposal/redflag.pdf2772	Dissertation:2773	http://www.fsl.cs.sunysb.edu/docs/jseyster-dissertation/redflag.pdf2774}2775}2776 2777@unpublished{PaulEMcKenney2013RCUUsage2778,Author="Paul E. McKenney and Silas Boyd-Wickizer and Jonathan Walpole"2779,Title="{RCU} Usage in the {Linux} Kernel: One Decade Later"2780,month="February"2781,day="24"2782,year="2013"2783,note="\url{http://rdrop.com/users/paulmck/techreports/RCUUsage.2013.02.24a.pdf}"2784,annotation={2785	Usage of RCU within the Linux kernel.2786}2787}2788 2789@inproceedings{AlexeyGotsman2013ESOPRCU2790,author = {Alexey Gotsman and Noam Rinetzky and Hongseok Yang}2791,title = {Verifying concurrent memory reclamation algorithms with grace}2792,booktitle = {ESOP'13: European Symposium on Programming}2793,year = {2013}2794,pages = {249--269}2795,publisher = {Springer}2796,address = {Rome, Italy}2797,annotation={2798	http://software.imdea.org/~gotsman/papers/recycling-esop13.pdf2799}2800}2801 2802@unpublished{PaulEMcKenney2013NoTinyPreempt2803,Author="Paul E. McKenney"2804,Title="Simplifying RCU"2805,month="March"2806,day="6"2807,year="2013"2808,note="\url{http://lwn.net/Articles/541037/}"2809,annotation={2810	Getting rid of TINY_PREEMPT_RCU.2811}2812}2813