14c62abc9SPaul E. McKenneyRead the Fscking Papers! 21da177e4SLinus Torvalds 31da177e4SLinus Torvalds 41da177e4SLinus TorvaldsThis document describes RCU-related publications, and is followed by 5dd81eca8SPaul E. McKenneythe corresponding bibtex entries. A number of the publications may 64c62abc9SPaul E. McKenneybe found at http://www.rdrop.com/users/paulmck/RCU/. For others, browsers 74c62abc9SPaul E. McKenneyand search engines will usually find what you are looking for. 81da177e4SLinus Torvalds 91da177e4SLinus TorvaldsThe first thing resembling RCU was published in 1980, when Kung and Lehman 101da177e4SLinus Torvalds[Kung80] recommended use of a garbage collector to defer destruction 111da177e4SLinus Torvaldsof nodes in a parallel binary search tree in order to simplify its 121da177e4SLinus Torvaldsimplementation. This works well in environments that have garbage 13f85d6c71SPaul E. McKenneycollectors, but most production garbage collectors incur significant 14f85d6c71SPaul E. McKenneyoverhead. 151da177e4SLinus Torvalds 161da177e4SLinus TorvaldsIn 1982, Manber and Ladner [Manber82,Manber84] recommended deferring 171da177e4SLinus Torvaldsdestruction until all threads running at that time have terminated, again 181da177e4SLinus Torvaldsfor a parallel binary search tree. This approach works well in systems 191da177e4SLinus Torvaldswith short-lived threads, such as the K42 research operating system. 201da177e4SLinus TorvaldsHowever, Linux has long-lived tasks, so more is needed. 211da177e4SLinus Torvalds 221da177e4SLinus TorvaldsIn 1986, Hennessy, Osisek, and Seigh [Hennessy89] introduced passive 231da177e4SLinus Torvaldsserialization, which is an RCU-like mechanism that relies on the presence 241da177e4SLinus Torvaldsof "quiescent states" in the VM/XA hypervisor that are guaranteed not 251da177e4SLinus Torvaldsto be referencing the data structure. However, this mechanism was not 261da177e4SLinus Torvaldsoptimized for modern computer systems, which is not surprising given 271da177e4SLinus Torvaldsthat these overheads were not so expensive in the mid-80s. Nonetheless, 281da177e4SLinus Torvaldspassive serialization appears to be the first deferred-destruction 294c54005cSPaul E. McKenneymechanism to be used in production. Furthermore, the relevant patent 304c54005cSPaul E. McKenneyhas lapsed, so this approach may be used in non-GPL software, if desired. 314c54005cSPaul E. McKenney(In contrast, implementation of RCU is permitted only in software licensed 324c54005cSPaul E. McKenneyunder either GPL or LGPL. Sorry!!!) 331da177e4SLinus Torvalds 34e4696a1dSPaul E. McKenneyIn 1987, Rashid et al. described lazy TLB-flush [RichardRashid87a]. 35e4696a1dSPaul E. McKenneyAt first glance, this has nothing to do with RCU, but nevertheless 36e4696a1dSPaul E. McKenneythis paper helped inspire the update-side batching used in the later 37e4696a1dSPaul E. McKenneyRCU implementation in DYNIX/ptx. In 1988, Barbara Liskov published 38e4696a1dSPaul E. McKenneya description of Argus that noted that use of out-of-date values can 39e4696a1dSPaul E. McKenneybe tolerated in some situations. Thus, this paper provides some early 40e4696a1dSPaul E. McKenneytheoretical justification for use of stale data. 41e4696a1dSPaul E. McKenney 421da177e4SLinus TorvaldsIn 1990, Pugh [Pugh90] noted that explicitly tracking which threads 431da177e4SLinus Torvaldswere reading a given data structure permitted deferred free to operate 441da177e4SLinus Torvaldsin the presence of non-terminating threads. However, this explicit 451da177e4SLinus Torvaldstracking imposes significant read-side overhead, which is undesirable 461da177e4SLinus Torvaldsin read-mostly situations. This algorithm does take pains to avoid 471da177e4SLinus Torvaldswrite-side contention and parallelize the other write-side overheads by 481da177e4SLinus Torvaldsproviding a fine-grained locking design, however, it would be interesting 491da177e4SLinus Torvaldsto see how much of the performance advantage reported in 1990 remains 506ae37718SPaul E. McKenneytoday. 511da177e4SLinus Torvalds 52e4696a1dSPaul E. McKenneyAt about this same time, Andrews [Andrews91textbook] described ``chaotic 53e4696a1dSPaul E. McKenneyrelaxation'', where the normal barriers between successive iterations 54e4696a1dSPaul E. McKenneyof convergent numerical algorithms are relaxed, so that iteration $n$ 55e4696a1dSPaul E. McKenneymight use data from iteration $n-1$ or even $n-2$. This introduces 56e4696a1dSPaul E. McKenneyerror, which typically slows convergence and thus increases the number of 571da177e4SLinus Torvaldsiterations required. However, this increase is sometimes more than made 581da177e4SLinus Torvaldsup for by a reduction in the number of expensive barrier operations, 591da177e4SLinus Torvaldswhich are otherwise required to synchronize the threads at the end 601da177e4SLinus Torvaldsof each iteration. Unfortunately, chaotic relaxation requires highly 611da177e4SLinus Torvaldsstructured data, such as the matrices used in scientific programs, and 621da177e4SLinus Torvaldsis thus inapplicable to most data structures in operating-system kernels. 631da177e4SLinus Torvalds 6432300751SPaul E. McKenneyIn 1992, Henry (now Alexia) Massalin completed a dissertation advising 6532300751SPaul E. McKenneyparallel programmers to defer processing when feasible to simplify 66e4696a1dSPaul E. McKenneysynchronization [HMassalinPhD]. RCU makes extremely heavy use of 67e4696a1dSPaul E. McKenneythis advice. 6832300751SPaul E. McKenney 691da177e4SLinus TorvaldsIn 1993, Jacobson [Jacobson93] verbally described what is perhaps the 701da177e4SLinus Torvaldssimplest deferred-free technique: simply waiting a fixed amount of time 711da177e4SLinus Torvaldsbefore freeing blocks awaiting deferred free. Jacobson did not describe 721da177e4SLinus Torvaldsany write-side changes he might have made in this work using SGI's Irix 731da177e4SLinus Torvaldskernel. Aju John published a similar technique in 1995 [AjuJohn95]. 741da177e4SLinus TorvaldsThis works well if there is a well-defined upper bound on the length of 751da177e4SLinus Torvaldstime that reading threads can hold references, as there might well be in 761da177e4SLinus Torvaldshard real-time systems. However, if this time is exceeded, perhaps due 771da177e4SLinus Torvaldsto preemption, excessive interrupts, or larger-than-anticipated load, 781da177e4SLinus Torvaldsmemory corruption can ensue, with no reasonable means of diagnosis. 791da177e4SLinus TorvaldsJacobson's technique is therefore inappropriate for use in production 801da177e4SLinus Torvaldsoperating-system kernels, except when such kernels can provide hard 811da177e4SLinus Torvaldsreal-time response guarantees for all operations. 821da177e4SLinus Torvalds 831da177e4SLinus TorvaldsAlso in 1995, Pu et al. [Pu95a] applied a technique similar to that of Pugh's 841da177e4SLinus Torvaldsread-side-tracking to permit replugging of algorithms within a commercial 851da177e4SLinus TorvaldsUnix operating system. However, this replugging permitted only a single 861da177e4SLinus Torvaldsreader at a time. The following year, this same group of researchers 871da177e4SLinus Torvaldsextended their technique to allow for multiple readers [Cowan96a]. 881da177e4SLinus TorvaldsTheir approach requires memory barriers (and thus pipeline stalls), 891da177e4SLinus Torvaldsbut reduces memory latency, contention, and locking overheads. 901da177e4SLinus Torvalds 911da177e4SLinus Torvalds1995 also saw the first publication of DYNIX/ptx's RCU mechanism 921da177e4SLinus Torvalds[Slingwine95], which was optimized for modern CPU architectures, 931da177e4SLinus Torvaldsand was successfully applied to a number of situations within the 941da177e4SLinus TorvaldsDYNIX/ptx kernel. The corresponding conference paper appeared in 1998 951da177e4SLinus Torvalds[McKenney98]. 961da177e4SLinus Torvalds 971da177e4SLinus TorvaldsIn 1999, the Tornado and K42 groups described their "generations" 986ae37718SPaul E. McKenneymechanism, which is quite similar to RCU [Gamsa99]. These operating 996ae37718SPaul E. McKenneysystems made pervasive use of RCU in place of "existence locks", which 1006ae37718SPaul E. McKenneygreatly simplifies locking hierarchies and helps avoid deadlocks. 1011da177e4SLinus Torvalds 102e4696a1dSPaul E. McKenneyThe year 2000 saw an email exchange that would likely have 103e4696a1dSPaul E. McKenneyled to yet another independent invention of something like RCU 104e4696a1dSPaul E. McKenney[RustyRussell2000a,RustyRussell2000b]. Instead, 2001 saw the first 105e4696a1dSPaul E. McKenneyRCU presentation involving Linux [McKenney01a] at OLS. The resulting 106e4696a1dSPaul E. McKenneyabundance of RCU patches was presented the following year [McKenney02a], 107e4696a1dSPaul E. McKenneyand use of RCU in dcache was first described that same year [Linder02a]. 1081da177e4SLinus Torvalds 109d19720a9SPaul E. McKenneyAlso in 2002, Michael [Michael02b,Michael02a] presented "hazard-pointer" 110d19720a9SPaul E. McKenneytechniques that defer the destruction of data structures to simplify 111d19720a9SPaul E. McKenneynon-blocking synchronization (wait-free synchronization, lock-free 112d19720a9SPaul E. McKenneysynchronization, and obstruction-free synchronization are all examples of 113e4696a1dSPaul E. McKenneynon-blocking synchronization). The corresponding journal article appeared 114e4696a1dSPaul E. McKenneyin 2004 [MagedMichael04a]. This technique eliminates locking, reduces 115e4696a1dSPaul E. McKenneycontention, reduces memory latency for readers, and parallelizes pipeline 116e4696a1dSPaul E. McKenneystalls and memory latency for writers. However, these techniques still 117e4696a1dSPaul E. McKenneyimpose significant read-side overhead in the form of memory barriers. 118e4696a1dSPaul E. McKenneyResearchers at Sun worked along similar lines in the same timeframe 119e4696a1dSPaul E. McKenney[HerlihyLM02]. These techniques can be thought of as inside-out reference 120e4696a1dSPaul E. McKenneycounts, where the count is represented by the number of hazard pointers 121e4696a1dSPaul E. McKenneyreferencing a given data structure rather than the more conventional 122e4696a1dSPaul E. McKenneycounter field within the data structure itself. The key advantage 123e4696a1dSPaul E. McKenneyof inside-out reference counts is that they can be stored in immortal 124e4696a1dSPaul E. McKenneyvariables, thus allowing races between access and deletion to be avoided. 125f85d6c71SPaul E. McKenney 126f85d6c71SPaul E. McKenneyBy the same token, RCU can be thought of as a "bulk reference count", 127f85d6c71SPaul E. McKenneywhere some form of reference counter covers all reference by a given CPU 128f85d6c71SPaul E. McKenneyor thread during a set timeframe. This timeframe is related to, but 129f85d6c71SPaul E. McKenneynot necessarily exactly the same as, an RCU grace period. In classic 130f85d6c71SPaul E. McKenneyRCU, the reference counter is the per-CPU bit in the "bitmask" field, 131f85d6c71SPaul E. McKenneyand each such bit covers all references that might have been made by 132f85d6c71SPaul E. McKenneythe corresponding CPU during the prior grace period. Of course, RCU 133f85d6c71SPaul E. McKenneycan be thought of in other terms as well. 1341da177e4SLinus Torvalds 1351da177e4SLinus TorvaldsIn 2003, the K42 group described how RCU could be used to create 136f85d6c71SPaul E. McKenneyhot-pluggable implementations of operating-system functions [Appavoo03a]. 137e4696a1dSPaul E. McKenneyLater that year saw a paper describing an RCU implementation 138e4696a1dSPaul E. McKenneyof System V IPC [Arcangeli03] (following up on a suggestion by 139e4696a1dSPaul E. McKenneyHugh Dickins [Dickins02a] and an implementation by Mingming Cao 140e4696a1dSPaul E. McKenney[MingmingCao2002IPCRCU]), and an introduction to RCU in Linux Journal 141f85d6c71SPaul E. McKenney[McKenney03a]. 1421da177e4SLinus Torvalds 1431da177e4SLinus Torvalds2004 has seen a Linux-Journal article on use of RCU in dcache 1441da177e4SLinus Torvalds[McKenney04a], a performance comparison of locking to RCU on several 1451da177e4SLinus Torvaldsdifferent CPUs [McKenney04b], a dissertation describing use of RCU in a 146a83f1fe2SPaul E. McKenneynumber of operating-system kernels [PaulEdwardMcKenneyPhD], a paper 147a83f1fe2SPaul E. McKenneydescribing how to make RCU safe for soft-realtime applications [Sarma04c], 148a83f1fe2SPaul E. McKenneyand a paper describing SELinux performance with RCU [JamesMorris04b]. 1491da177e4SLinus Torvalds 150f85d6c71SPaul E. McKenney2005 brought further adaptation of RCU to realtime use, permitting 151dd81eca8SPaul E. McKenneypreemption of RCU realtime critical sections [PaulMcKenney05a, 152dd81eca8SPaul E. McKenneyPaulMcKenney05b]. 153dd81eca8SPaul E. McKenney 154f85d6c71SPaul E. McKenney2006 saw the first best-paper award for an RCU paper [ThomasEHart2006a], 155f85d6c71SPaul E. McKenneyas well as further work on efficient implementations of preemptible 156f85d6c71SPaul E. McKenneyRCU [PaulEMcKenney2006b], but priority-boosting of RCU read-side critical 157f85d6c71SPaul E. McKenneysections proved elusive. An RCU implementation permitting general 158f85d6c71SPaul E. McKenneyblocking in read-side critical sections appeared [PaulEMcKenney2006c], 159f85d6c71SPaul E. McKenneyRobert Olsson described an RCU-protected trie-hash combination 160f85d6c71SPaul E. McKenney[RobertOlsson2006a]. 161f85d6c71SPaul E. McKenney 16232300751SPaul E. McKenney2007 saw the journal version of the award-winning RCU paper from 2006 16332300751SPaul E. McKenney[ThomasEHart2007a], as well as a paper demonstrating use of Promela 16432300751SPaul E. McKenneyand Spin to mechanically verify an optimization to Oleg Nesterov's 16532300751SPaul E. McKenneyQRCU [PaulEMcKenney2007QRCUspin], a design document describing 16632300751SPaul E. McKenneypreemptible RCU [PaulEMcKenney2007PreemptibleRCU], and the three-part 16732300751SPaul E. McKenneyLWN "What is RCU?" series [PaulEMcKenney2007WhatIsRCUFundamentally, 16832300751SPaul E. McKenneyPaulEMcKenney2008WhatIsRCUUsage, and PaulEMcKenney2008WhatIsRCUAPI]. 169f85d6c71SPaul E. McKenney 1704c54005cSPaul E. McKenney2008 saw a journal paper on real-time RCU [DinakarGuniguntala2008IBMSysJ], 1714c54005cSPaul E. McKenneya history of how Linux changed RCU more than RCU changed Linux 1724c54005cSPaul E. McKenney[PaulEMcKenney2008RCUOSR], and a design overview of hierarchical RCU 1734c54005cSPaul E. McKenney[PaulEMcKenney2008HierarchicalRCU]. 1744c54005cSPaul E. McKenney 1754c54005cSPaul E. McKenney2009 introduced user-level RCU algorithms [PaulEMcKenney2009MaliciousURCU], 1764c54005cSPaul E. McKenneywhich Mathieu Desnoyers is now maintaining [MathieuDesnoyers2009URCU] 1774c54005cSPaul E. McKenney[MathieuDesnoyersPhD]. TINY_RCU [PaulEMcKenney2009BloatWatchRCU] made 1784c54005cSPaul E. McKenneyits appearance, as did expedited RCU [PaulEMcKenney2009expeditedRCU]. 1794c54005cSPaul E. McKenneyThe problem of resizeable RCU-protected hash tables may now be on a path 1804c62abc9SPaul E. McKenneyto a solution [JoshTriplett2009RPHash]. A few academic researchers are now 1814c62abc9SPaul E. McKenneyusing RCU to solve their parallel problems [HariKannan2009DynamicAnalysisRCU]. 1824c62abc9SPaul E. McKenney 1834c62abc9SPaul E. McKenney2010 produced a simpler preemptible-RCU implementation 1844c62abc9SPaul E. McKenneybased on TREE_RCU [PaulEMcKenney2010SimpleOptRCU], lockdep-RCU 1854c62abc9SPaul E. McKenney[PaulEMcKenney2010LockdepRCU], another resizeable RCU-protected hash 1864c62abc9SPaul E. McKenneytable [HerbertXu2010RCUResizeHash] (this one consuming more memory, 1874c62abc9SPaul E. McKenneybut allowing arbitrary changes in hash function, as required for DoS 1884c62abc9SPaul E. McKenneyavoidance in the networking code), realization of the 2009 RCU-protected 1894c62abc9SPaul E. McKenneyhash table with atomic node move [JoshTriplett2010RPHash], an update on 1904c62abc9SPaul E. McKenneythe RCU API [PaulEMcKenney2010RCUAPI]. 1914c62abc9SPaul E. McKenney 1924c62abc9SPaul E. McKenney2011 marked the inclusion of Nick Piggin's fully lockless dentry search 1934c62abc9SPaul E. McKenney[LinusTorvalds2011Linux2:6:38:rc1:NPigginVFS], an RCU-protected red-black 1944c62abc9SPaul E. McKenneytree using software transactional memory to protect concurrent updates 1954c62abc9SPaul E. McKenney(strange, but true!) [PhilHoward2011RCUTMRBTree], yet another variant of 1964c62abc9SPaul E. McKenneyRCU-protected resizeable hash tables [Triplett:2011:RPHash], the 3.0 RCU 1974c62abc9SPaul E. McKenneytrainwreck [PaulEMcKenney2011RCU3.0trainwreck], and Neil Brown's "Meet the 1986ae37718SPaul E. McKenneyLockers" LWN article [NeilBrown2011MeetTheLockers]. Some academic 1996ae37718SPaul E. McKenneywork looked at debugging uses of RCU [Seyster:2011:RFA:2075416.2075425]. 2006ae37718SPaul E. McKenney 2016ae37718SPaul E. McKenneyIn 2012, Josh Triplett received his Ph.D. with his dissertation 2026ae37718SPaul E. McKenneycovering RCU-protected resizable hash tables and the relationship 2036ae37718SPaul E. McKenneybetween memory barriers and read-side traversal order: If the updater 2046ae37718SPaul E. McKenneyis making changes in the opposite direction from the read-side traveral 2056ae37718SPaul E. McKenneyorder, the updater need only execute a memory-barrier instruction, 2066ae37718SPaul E. McKenneybut if in the same direction, the updater needs to wait for a grace 2076ae37718SPaul E. McKenneyperiod between the individual updates [JoshTriplettPhD]. Also in 2012, 2086ae37718SPaul E. McKenneyafter seventeen years of attempts, an RCU paper made it into a top-flight 2096ae37718SPaul E. McKenneyacademic journal, IEEE Transactions on Parallel and Distributed Systems 2106ae37718SPaul E. McKenney[MathieuDesnoyers2012URCU]. A group of researchers in Spain applied 2116ae37718SPaul E. McKenneyuser-level RCU to crowd simulation [GuillermoVigueras2012RCUCrowd], and 2126ae37718SPaul E. McKenneyanother group of researchers in Europe produced a formal description of 2136ae37718SPaul E. McKenneyRCU based on separation logic [AlexeyGotsman2012VerifyGraceExtended], 2146ae37718SPaul E. McKenneywhich was published in the 2013 European Symposium on Programming 2156ae37718SPaul E. McKenney[AlexeyGotsman2013ESOPRCU]. 2166ae37718SPaul E. McKenney 2174c62abc9SPaul E. McKenney 2184c54005cSPaul E. McKenney 2191da177e4SLinus TorvaldsBibtex Entries 2201da177e4SLinus Torvalds 2211da177e4SLinus Torvalds@article{Kung80 2221da177e4SLinus Torvalds,author="H. T. Kung and Q. Lehman" 2230f9574d8SDhaval Giani,title="Concurrent Manipulation of Binary Search Trees" 2241da177e4SLinus Torvalds,Year="1980" 2251da177e4SLinus Torvalds,Month="September" 2261da177e4SLinus Torvalds,journal="ACM Transactions on Database Systems" 2271da177e4SLinus Torvalds,volume="5" 2281da177e4SLinus Torvalds,number="3" 2291da177e4SLinus Torvalds,pages="354-382" 2304c62abc9SPaul E. McKenney,annotation={ 2314c62abc9SPaul E. McKenney Use garbage collector to clean up data after everyone is done with it. 2324c62abc9SPaul E. McKenney . 2334c62abc9SPaul E. McKenney Oldest use of something vaguely resembling RCU that I have found. 2346ae37718SPaul E. McKenney http://portal.acm.org/citation.cfm?id=320619&dl=GUIDE, 2356ae37718SPaul E. McKenney [Viewed December 3, 2007] 2364c62abc9SPaul E. McKenney} 2371da177e4SLinus Torvalds} 2381da177e4SLinus Torvalds 2391da177e4SLinus Torvalds@techreport{Manber82 2401da177e4SLinus Torvalds,author="Udi Manber and Richard E. Ladner" 2411da177e4SLinus Torvalds,title="Concurrency Control in a Dynamic Search Structure" 2421da177e4SLinus Torvalds,institution="Department of Computer Science, University of Washington" 2431da177e4SLinus Torvalds,address="Seattle, Washington" 2441da177e4SLinus Torvalds,year="1982" 2451da177e4SLinus Torvalds,number="82-01-01" 2461da177e4SLinus Torvalds,month="January" 2471da177e4SLinus Torvalds,pages="28" 2484c62abc9SPaul E. McKenney,annotation={ 2494c62abc9SPaul E. McKenney . 2504c62abc9SPaul E. McKenney Superseded by Manber84. 2514c62abc9SPaul E. McKenney . 2524c62abc9SPaul E. McKenney Describes concurrent AVL tree implementation. Uses a 2534c62abc9SPaul E. McKenney garbage-collection mechanism to handle concurrent use and deletion 2544c62abc9SPaul E. McKenney of nodes in the tree, but lacks the summary-of-execution-history 2554c62abc9SPaul E. McKenney concept of read-copy locking. 2564c62abc9SPaul E. McKenney . 2574c62abc9SPaul E. McKenney Keeps full list of processes that were active when a given 2584c62abc9SPaul E. McKenney node was to be deleted, and waits until all such processes have 2594c62abc9SPaul E. McKenney -terminated- before allowing this node to be reused. This is 2604c62abc9SPaul E. McKenney not described in great detail -- one could imagine using process 2614c62abc9SPaul E. McKenney IDs for this if the ID space was large enough that overlapping 2624c62abc9SPaul E. McKenney never occurred. 2634c62abc9SPaul E. McKenney . 2644c62abc9SPaul E. McKenney This restriction makes this algorithm unsuitable for use in 2654c62abc9SPaul E. McKenney systems comprised of long-lived processes. It also produces 2664c62abc9SPaul E. McKenney completely unacceptable overhead in systems with large numbers 2674c62abc9SPaul E. McKenney of processes. Finally, it is specific to AVL trees. 2684c62abc9SPaul E. McKenney . 2694c62abc9SPaul E. McKenney Cites Kung80, so not an independent invention, but the first 2704c62abc9SPaul E. McKenney RCU-like usage that does not rely on an automatic garbage 2714c62abc9SPaul E. McKenney collector. 2724c62abc9SPaul E. McKenney} 2731da177e4SLinus Torvalds} 2741da177e4SLinus Torvalds 2751da177e4SLinus Torvalds@article{Manber84 2761da177e4SLinus Torvalds,author="Udi Manber and Richard E. Ladner" 2771da177e4SLinus Torvalds,title="Concurrency Control in a Dynamic Search Structure" 2781da177e4SLinus Torvalds,Year="1984" 2791da177e4SLinus Torvalds,Month="September" 2801da177e4SLinus Torvalds,journal="ACM Transactions on Database Systems" 2811da177e4SLinus Torvalds,volume="9" 2821da177e4SLinus Torvalds,number="3" 2831da177e4SLinus Torvalds,pages="439-455" 2844c62abc9SPaul E. McKenney,annotation={ 2854c62abc9SPaul E. McKenney Describes concurrent AVL tree implementation. Uses a 2864c62abc9SPaul E. McKenney garbage-collection mechanism to handle concurrent use and deletion 2874c62abc9SPaul E. McKenney of nodes in the tree, but lacks the summary-of-execution-history 2884c62abc9SPaul E. McKenney concept of read-copy locking. 2894c62abc9SPaul E. McKenney . 2904c62abc9SPaul E. McKenney Keeps full list of processes that were active when a given 2914c62abc9SPaul E. McKenney node was to be deleted, and waits until all such processes have 2924c62abc9SPaul E. McKenney -terminated- before allowing this node to be reused. This is 2934c62abc9SPaul E. McKenney not described in great detail -- one could imagine using process 2944c62abc9SPaul E. McKenney IDs for this if the ID space was large enough that overlapping 2954c62abc9SPaul E. McKenney never occurred. 2964c62abc9SPaul E. McKenney . 2974c62abc9SPaul E. McKenney This restriction makes this algorithm unsuitable for use in 2984c62abc9SPaul E. McKenney systems comprised of long-lived processes. It also produces 2994c62abc9SPaul E. McKenney completely unacceptable overhead in systems with large numbers 3004c62abc9SPaul E. McKenney of processes. Finally, it is specific to AVL trees. 3014c62abc9SPaul E. McKenney} 3024c62abc9SPaul E. McKenney} 3034c62abc9SPaul E. McKenney 3044c62abc9SPaul E. McKenney@Conference{RichardRashid87a 3054c62abc9SPaul E. McKenney,Author="Richard Rashid and Avadis Tevanian and Michael Young and 3064c62abc9SPaul E. McKenneyDavid Golub and Robert Baron and David Black and William Bolosky and 3074c62abc9SPaul E. McKenneyJonathan Chew" 3084c62abc9SPaul E. McKenney,Title="Machine-Independent Virtual Memory Management for Paged 3094c62abc9SPaul E. McKenneyUniprocessor and Multiprocessor Architectures" 3104c62abc9SPaul E. McKenney,Booktitle="{2\textsuperscript{nd} Symposium on Architectural Support 3114c62abc9SPaul E. McKenneyfor Programming Languages and Operating Systems}" 3124c62abc9SPaul E. McKenney,Publisher="Association for Computing Machinery" 3134c62abc9SPaul E. McKenney,Month="October" 3144c62abc9SPaul E. McKenney,Year="1987" 3154c62abc9SPaul E. McKenney,pages="31-39" 3164c62abc9SPaul E. McKenney,Address="Palo Alto, CA" 3174c62abc9SPaul E. McKenney,note="Available: 3184c62abc9SPaul E. McKenney\url{http://www.cse.ucsc.edu/~randal/221/rashid-machvm.pdf} 3194c62abc9SPaul E. McKenney[Viewed February 17, 2005]" 3204c62abc9SPaul E. McKenney,annotation={ 3214c62abc9SPaul E. McKenney Describes lazy TLB flush, where one waits for each CPU to pass 3224c62abc9SPaul E. McKenney through a scheduling-clock interrupt before reusing a given range 3234c62abc9SPaul E. McKenney of virtual address. Does not describe how one determines that 3244c62abc9SPaul E. McKenney all CPUs have in fact taken such an interrupt, though there are 3254c62abc9SPaul E. McKenney no shortage of straightforward methods for accomplishing this. 3264c62abc9SPaul E. McKenney . 3274c62abc9SPaul E. McKenney Note that it does not make sense to just wait a fixed amount of 3284c62abc9SPaul E. McKenney time, since a given CPU might have interrupts disabled for an 3294c62abc9SPaul E. McKenney extended amount of time. 3304c62abc9SPaul E. McKenney} 3314c62abc9SPaul E. McKenney} 3324c62abc9SPaul E. McKenney 3334c62abc9SPaul E. McKenney@article{BarbaraLiskov1988ArgusCACM 3344c62abc9SPaul E. McKenney,author = {Barbara Liskov} 3354c62abc9SPaul E. McKenney,title = {Distributed programming in {Argus}} 3364c62abc9SPaul E. McKenney,journal = {Commun. ACM} 3374c62abc9SPaul E. McKenney,volume = {31} 3384c62abc9SPaul E. McKenney,number = {3} 3394c62abc9SPaul E. McKenney,year = {1988} 3404c62abc9SPaul E. McKenney,issn = {0001-0782} 3414c62abc9SPaul E. McKenney,pages = {300--312} 3424c62abc9SPaul E. McKenney,doi = {http://doi.acm.org/10.1145/42392.42399} 3434c62abc9SPaul E. McKenney,publisher = {ACM} 3444c62abc9SPaul E. McKenney,address = {New York, NY, USA} 3454c62abc9SPaul E. McKenney,annotation={ 3464c62abc9SPaul E. McKenney At the top of page 307: "Conflicts with deposits and withdrawals 3474c62abc9SPaul E. McKenney are necessary if the reported total is to be up to date. They 3484c62abc9SPaul E. McKenney could be avoided by having total return a sum that is slightly 3494c62abc9SPaul E. McKenney out of date." Relies on semantics -- approximate numerical 3504c62abc9SPaul E. McKenney values sometimes OK. 3514c62abc9SPaul E. McKenney} 3521da177e4SLinus Torvalds} 3531da177e4SLinus Torvalds 3541da177e4SLinus Torvalds@techreport{Hennessy89 3551da177e4SLinus Torvalds,author="James P. Hennessy and Damian L. Osisek and Joseph W. {Seigh II}" 3561da177e4SLinus Torvalds,title="Passive Serialization in a Multitasking Environment" 3571da177e4SLinus Torvalds,institution="US Patent and Trademark Office" 3581da177e4SLinus Torvalds,address="Washington, DC" 3591da177e4SLinus Torvalds,year="1989" 3601da177e4SLinus Torvalds,number="US Patent 4,809,168 (lapsed)" 3611da177e4SLinus Torvalds,month="February" 3621da177e4SLinus Torvalds,pages="11" 3631da177e4SLinus Torvalds} 3641da177e4SLinus Torvalds 3651da177e4SLinus Torvalds@techreport{Pugh90 3661da177e4SLinus Torvalds,author="William Pugh" 3671da177e4SLinus Torvalds,title="Concurrent Maintenance of Skip Lists" 3681da177e4SLinus Torvalds,institution="Institute of Advanced Computer Science Studies, Department of Computer Science, University of Maryland" 3691da177e4SLinus Torvalds,address="College Park, Maryland" 3701da177e4SLinus Torvalds,year="1990" 3711da177e4SLinus Torvalds,number="CS-TR-2222.1" 3721da177e4SLinus Torvalds,month="June" 3734c62abc9SPaul E. McKenney,annotation={ 3744c62abc9SPaul E. McKenney Concurrent access to skip lists. Has both weak and strong search. 3754c62abc9SPaul E. McKenney Uses concept of ``garbage queue'', but has no real way of cleaning 3764c62abc9SPaul E. McKenney the garbage efficiently. 3774c62abc9SPaul E. McKenney . 3784c62abc9SPaul E. McKenney Appears to be an independent invention of an RCU-like mechanism. 3794c62abc9SPaul E. McKenney} 3801da177e4SLinus Torvalds} 3811da177e4SLinus Torvalds 3826ae37718SPaul E. McKenney# Was Adams91, see also syncrefs.bib. 3836ae37718SPaul E. McKenney@Book{Andrews91textbook 3846ae37718SPaul E. McKenney,Author="Gregory R. Andrews" 3851da177e4SLinus Torvalds,title="Concurrent Programming, Principles, and Practices" 3861da177e4SLinus Torvalds,Publisher="Benjamin Cummins" 3871da177e4SLinus Torvalds,Year="1991" 3884c62abc9SPaul E. McKenney,annotation={ 3894c62abc9SPaul E. McKenney Has a few paragraphs describing ``chaotic relaxation'', a 3904c62abc9SPaul E. McKenney numerical analysis technique that allows multiprocessors to 3914c62abc9SPaul E. McKenney avoid synchronization overhead by using possibly-stale data. 3924c62abc9SPaul E. McKenney . 3934c62abc9SPaul E. McKenney Seems like this is descended from yet another independent 3944c62abc9SPaul E. McKenney invention of RCU-like function -- but this is restricted 3954c62abc9SPaul E. McKenney in that reclamation is not necessary. 3961da177e4SLinus Torvalds} 39732300751SPaul E. McKenney} 39832300751SPaul E. McKenney 399e4696a1dSPaul E. McKenney@phdthesis{HMassalinPhD 400e4696a1dSPaul E. McKenney,author="H. Massalin" 401e4696a1dSPaul E. McKenney,title="Synthesis: An Efficient Implementation of Fundamental Operating 402e4696a1dSPaul E. McKenneySystem Services" 403e4696a1dSPaul E. McKenney,school="Columbia University" 404e4696a1dSPaul E. McKenney,address="New York, NY" 405e4696a1dSPaul E. McKenney,year="1992" 406e4696a1dSPaul E. McKenney,annotation={ 407e4696a1dSPaul E. McKenney Mondo optimizing compiler. 408e4696a1dSPaul E. McKenney Wait-free stuff. 409e4696a1dSPaul E. McKenney Good advice: defer work to avoid synchronization. See page 90 410e4696a1dSPaul E. McKenney (PDF page 106), Section 5.4, fourth bullet point. 411e4696a1dSPaul E. McKenney} 412e4696a1dSPaul E. McKenney} 413e4696a1dSPaul E. McKenney 4141da177e4SLinus Torvalds@unpublished{Jacobson93 4151da177e4SLinus Torvalds,author="Van Jacobson" 4161da177e4SLinus Torvalds,title="Avoid Read-Side Locking Via Delayed Free" 4171da177e4SLinus Torvalds,year="1993" 4181da177e4SLinus Torvalds,month="September" 4194c62abc9SPaul E. McKenney,note="private communication" 4204c62abc9SPaul E. McKenney,annotation={ 4214c62abc9SPaul E. McKenney Use fixed time delay to approximate grace period. Very simple, 4224c62abc9SPaul E. McKenney but subject to random memory corruption under heavy load. 4234c62abc9SPaul E. McKenney . 4244c62abc9SPaul E. McKenney Independent invention of RCU-like mechanism. 4254c62abc9SPaul E. McKenney} 4261da177e4SLinus Torvalds} 4271da177e4SLinus Torvalds 4281da177e4SLinus Torvalds@Conference{AjuJohn95 4291da177e4SLinus Torvalds,Author="Aju John" 4301da177e4SLinus Torvalds,Title="Dynamic vnodes -- Design and Implementation" 4311da177e4SLinus Torvalds,Booktitle="{USENIX Winter 1995}" 4321da177e4SLinus Torvalds,Publisher="USENIX Association" 4331da177e4SLinus Torvalds,Month="January" 4341da177e4SLinus Torvalds,Year="1995" 4351da177e4SLinus Torvalds,pages="11-23" 4361da177e4SLinus Torvalds,Address="New Orleans, LA" 4374c62abc9SPaul E. McKenney,note="Available: 4384c62abc9SPaul E. McKenney\url{https://www.usenix.org/publications/library/proceedings/neworl/full_papers/john.a} 4394c62abc9SPaul E. McKenney[Viewed October 1, 2010]" 4404c62abc9SPaul E. McKenney,annotation={ 4414c62abc9SPaul E. McKenney Age vnodes out of the cache, and have a fixed time set by a kernel 4424c62abc9SPaul E. McKenney parameter. Not clear that all races were in fact correctly handled. 4434c62abc9SPaul E. McKenney Used a 20-minute time by default, which would most definitely not 4444c62abc9SPaul E. McKenney be suitable during DoS attacks or virus scans. 4454c62abc9SPaul E. McKenney . 4464c62abc9SPaul E. McKenney Apparently independent invention of RCU-like mechanism. 4474c62abc9SPaul E. McKenney} 4481da177e4SLinus Torvalds} 4491da177e4SLinus Torvalds 4506ae37718SPaul E. McKenney@conference{Pu95a 4516ae37718SPaul E. McKenney,Author = "Calton Pu and Tito Autrey and Andrew Black and Charles Consel and 452f85d6c71SPaul E. McKenneyCrispin Cowan and Jon Inouye and Lakshmi Kethana and Jonathan Walpole and 4536ae37718SPaul E. McKenneyKe Zhang" 4546ae37718SPaul E. McKenney,Title = "Optimistic Incremental Specialization: Streamlining a Commercial 4556ae37718SPaul E. McKenney,Operating System" 4566ae37718SPaul E. McKenney,Booktitle = "15\textsuperscript{th} ACM Symposium on 4576ae37718SPaul E. McKenney,Operating Systems Principles (SOSP'95)" 4586ae37718SPaul E. McKenney,address = "Copper Mountain, CO" 4596ae37718SPaul E. McKenney,month="December" 4606ae37718SPaul E. McKenney,year="1995" 4616ae37718SPaul E. McKenney,pages="314-321" 4626ae37718SPaul E. McKenney,annotation={ 463f85d6c71SPaul E. McKenney Uses a replugger, but with a flag to signal when people are 464f85d6c71SPaul E. McKenney using the resource at hand. Only one reader at a time. 4656ae37718SPaul E. McKenney} 466f85d6c71SPaul E. McKenney} 467f85d6c71SPaul E. McKenney 4686ae37718SPaul E. McKenney@conference{Cowan96a 4696ae37718SPaul E. McKenney,Author = "Crispin Cowan and Tito Autrey and Charles Krasic and 4706ae37718SPaul E. McKenney,Calton Pu and Jonathan Walpole" 4716ae37718SPaul E. McKenney,Title = "Fast Concurrent Dynamic Linking for an Adaptive Operating System" 4726ae37718SPaul E. McKenney,Booktitle = "International Conference on Configurable Distributed Systems 4736ae37718SPaul E. McKenney(ICCDS'96)" 4746ae37718SPaul E. McKenney,address = "Annapolis, MD" 4756ae37718SPaul E. McKenney,month="May" 4766ae37718SPaul E. McKenney,year="1996" 4776ae37718SPaul E. McKenney,pages="108" 4786ae37718SPaul E. McKenney,isbn="0-8186-7395-8" 4796ae37718SPaul E. McKenney,annotation={ 480f85d6c71SPaul E. McKenney Uses a replugger, but with a counter to signal when people are 481f85d6c71SPaul E. McKenney using the resource at hand. Allows multiple readers. 4826ae37718SPaul E. McKenney} 483f85d6c71SPaul E. McKenney} 484f85d6c71SPaul E. McKenney 4851da177e4SLinus Torvalds@techreport{Slingwine95 4861da177e4SLinus Torvalds,author="John D. Slingwine and Paul E. McKenney" 4871da177e4SLinus Torvalds,title="Apparatus and Method for Achieving Reduced Overhead Mutual 4881da177e4SLinus TorvaldsExclusion and Maintaining Coherency in a Multiprocessor System 4891da177e4SLinus TorvaldsUtilizing Execution History and Thread Monitoring" 4901da177e4SLinus Torvalds,institution="US Patent and Trademark Office" 4911da177e4SLinus Torvalds,address="Washington, DC" 4921da177e4SLinus Torvalds,year="1995" 4934c62abc9SPaul E. McKenney,number="US Patent 5,442,758" 4941da177e4SLinus Torvalds,month="August" 4954c62abc9SPaul E. McKenney,annotation={ 4964c62abc9SPaul E. McKenney Describes the parallel RCU infrastructure. Includes NUMA aspect 4974c62abc9SPaul E. McKenney (structure of bitmap can reflect bus structure of computer system). 4984c62abc9SPaul E. McKenney . 4994c62abc9SPaul E. McKenney Another independent invention of an RCU-like mechanism, but the 5004c62abc9SPaul E. McKenney "real" RCU this time! 5014c62abc9SPaul E. McKenney} 5021da177e4SLinus Torvalds} 5031da177e4SLinus Torvalds 5041da177e4SLinus Torvalds@techreport{Slingwine97 5051da177e4SLinus Torvalds,author="John D. Slingwine and Paul E. McKenney" 5064c62abc9SPaul E. McKenney,title="Method for Maintaining Data Coherency Using Thread Activity 5074c62abc9SPaul E. McKenneySummaries in a Multicomputer System" 5081da177e4SLinus Torvalds,institution="US Patent and Trademark Office" 5091da177e4SLinus Torvalds,address="Washington, DC" 5101da177e4SLinus Torvalds,year="1997" 5114c62abc9SPaul E. McKenney,number="US Patent 5,608,893" 5121da177e4SLinus Torvalds,month="March" 5134c62abc9SPaul E. McKenney,pages="19" 5144c62abc9SPaul E. McKenney,annotation={ 5154c62abc9SPaul E. McKenney Describes use of RCU to synchronize data between a pair of 5164c62abc9SPaul E. McKenney SMP/NUMA computer systems. 5174c62abc9SPaul E. McKenney} 5181da177e4SLinus Torvalds} 5191da177e4SLinus Torvalds 5201da177e4SLinus Torvalds@techreport{Slingwine98 5211da177e4SLinus Torvalds,author="John D. Slingwine and Paul E. McKenney" 5224c62abc9SPaul E. McKenney,title="Apparatus and Method for Achieving Reduced Overhead Mutual 5234c62abc9SPaul E. McKenneyExclusion and Maintaining Coherency in a Multiprocessor System 5244c62abc9SPaul E. McKenneyUtilizing Execution History and Thread Monitoring" 5251da177e4SLinus Torvalds,institution="US Patent and Trademark Office" 5261da177e4SLinus Torvalds,address="Washington, DC" 5271da177e4SLinus Torvalds,year="1998" 5284c62abc9SPaul E. McKenney,number="US Patent 5,727,209" 5291da177e4SLinus Torvalds,month="March" 5304c62abc9SPaul E. McKenney,annotation={ 5314c62abc9SPaul E. McKenney Describes doing an atomic update by copying the data item and 5324c62abc9SPaul E. McKenney then substituting it into the data structure. 5334c62abc9SPaul E. McKenney} 5341da177e4SLinus Torvalds} 5351da177e4SLinus Torvalds 5361da177e4SLinus Torvalds@Conference{McKenney98 5371da177e4SLinus Torvalds,Author="Paul E. McKenney and John D. Slingwine" 5381da177e4SLinus Torvalds,Title="Read-Copy Update: Using Execution History to Solve Concurrency 5391da177e4SLinus TorvaldsProblems" 5401da177e4SLinus Torvalds,Booktitle="{Parallel and Distributed Computing and Systems}" 5411da177e4SLinus Torvalds,Month="October" 5421da177e4SLinus Torvalds,Year="1998" 5431da177e4SLinus Torvalds,pages="509-518" 5441da177e4SLinus Torvalds,Address="Las Vegas, NV" 5454c62abc9SPaul E. McKenney,annotation={ 5464c62abc9SPaul E. McKenney Describes and analyzes RCU mechanism in DYNIX/ptx. Describes 5474c62abc9SPaul E. McKenney application to linked list update and log-buffer flushing. 5484c62abc9SPaul E. McKenney Defines 'quiescent state'. Includes both measured and analytic 5494c62abc9SPaul E. McKenney evaluation. 5506ae37718SPaul E. McKenney http://www.rdrop.com/users/paulmck/RCU/rclockpdcsproof.pdf 5516ae37718SPaul E. McKenney [Viewed December 3, 2007] 5524c62abc9SPaul E. McKenney} 5531da177e4SLinus Torvalds} 5541da177e4SLinus Torvalds 5551da177e4SLinus Torvalds@Conference{Gamsa99 5561da177e4SLinus Torvalds,Author="Ben Gamsa and Orran Krieger and Jonathan Appavoo and Michael Stumm" 5571da177e4SLinus Torvalds,Title="Tornado: Maximizing Locality and Concurrency in a Shared Memory 5581da177e4SLinus TorvaldsMultiprocessor Operating System" 5591da177e4SLinus Torvalds,Booktitle="{Proceedings of the 3\textsuperscript{rd} Symposium on 5601da177e4SLinus TorvaldsOperating System Design and Implementation}" 5611da177e4SLinus Torvalds,Month="February" 5621da177e4SLinus Torvalds,Year="1999" 5631da177e4SLinus Torvalds,pages="87-100" 5641da177e4SLinus Torvalds,Address="New Orleans, LA" 5654c62abc9SPaul E. McKenney,annotation={ 5664c62abc9SPaul E. McKenney Use of RCU-like facility in K42/Tornado. Another independent 5674c62abc9SPaul E. McKenney invention of RCU. 5684c62abc9SPaul E. McKenney See especially pages 7-9 (Section 5). 5696ae37718SPaul E. McKenney http://www.usenix.org/events/osdi99/full_papers/gamsa/gamsa.pdf 5706ae37718SPaul E. McKenney [Viewed August 30, 2006] 5714c62abc9SPaul E. McKenney} 5724c62abc9SPaul E. McKenney} 5734c62abc9SPaul E. McKenney 5744c62abc9SPaul E. McKenney@unpublished{RustyRussell2000a 5754c62abc9SPaul E. McKenney,Author="Rusty Russell" 5764c62abc9SPaul E. McKenney,Title="Re: modular net drivers" 5774c62abc9SPaul E. McKenney,month="June" 5784c62abc9SPaul E. McKenney,year="2000" 5794c62abc9SPaul E. McKenney,day="23" 5804c62abc9SPaul E. McKenney,note="Available: 5814c62abc9SPaul E. McKenney\url{http://oss.sgi.com/projects/netdev/archive/2000-06/msg00250.html} 5824c62abc9SPaul E. McKenney[Viewed April 10, 2006]" 5834c62abc9SPaul E. McKenney,annotation={ 5844c62abc9SPaul E. McKenney Proto-RCU proposal from Phil Rumpf and Rusty Russell. 5854c62abc9SPaul E. McKenney Yet another independent invention of RCU. 5864c62abc9SPaul E. McKenney Outline of algorithm to unload modules... 5874c62abc9SPaul E. McKenney . 5884c62abc9SPaul E. McKenney Appeared on net-dev mailing list. 5894c62abc9SPaul E. McKenney} 5904c62abc9SPaul E. McKenney} 5914c62abc9SPaul E. McKenney 5924c62abc9SPaul E. McKenney@unpublished{RustyRussell2000b 5934c62abc9SPaul E. McKenney,Author="Rusty Russell" 5944c62abc9SPaul E. McKenney,Title="Re: modular net drivers" 5954c62abc9SPaul E. McKenney,month="June" 5964c62abc9SPaul E. McKenney,year="2000" 5974c62abc9SPaul E. McKenney,day="24" 5984c62abc9SPaul E. McKenney,note="Available: 5994c62abc9SPaul E. McKenney\url{http://oss.sgi.com/projects/netdev/archive/2000-06/msg00254.html} 6004c62abc9SPaul E. McKenney[Viewed April 10, 2006]" 6014c62abc9SPaul E. McKenney,annotation={ 6024c62abc9SPaul E. McKenney Proto-RCU proposal from Phil Rumpf and Rusty Russell. 6034c62abc9SPaul E. McKenney . 6044c62abc9SPaul E. McKenney Appeared on net-dev mailing list. 6054c62abc9SPaul E. McKenney} 6064c62abc9SPaul E. McKenney} 6074c62abc9SPaul E. McKenney 6084c62abc9SPaul E. McKenney@unpublished{McKenney01b 6094c62abc9SPaul E. McKenney,Author="Paul E. McKenney and Dipankar Sarma" 6104c62abc9SPaul E. McKenney,Title="Read-Copy Update Mutual Exclusion in {Linux}" 6114c62abc9SPaul E. McKenney,month="February" 6124c62abc9SPaul E. McKenney,year="2001" 6134c62abc9SPaul E. McKenney,note="Available: 6144c62abc9SPaul E. McKenney\url{http://lse.sourceforge.net/locking/rcu/rcupdate_doc.html} 6154c62abc9SPaul E. McKenney[Viewed October 18, 2004]" 6164c62abc9SPaul E. McKenney,annotation={ 6174c62abc9SPaul E. McKenney Prototypical Linux documentation for RCU. 6184c62abc9SPaul E. McKenney} 6191da177e4SLinus Torvalds} 6201da177e4SLinus Torvalds 6211da177e4SLinus Torvalds@techreport{Slingwine01 6221da177e4SLinus Torvalds,author="John D. Slingwine and Paul E. McKenney" 6234c62abc9SPaul E. McKenney,title="Apparatus and Method for Achieving Reduced Overhead Mutual 6244c62abc9SPaul E. McKenneyExclusion and Maintaining Coherency in a Multiprocessor System 6254c62abc9SPaul E. McKenneyUtilizing Execution History and Thread Monitoring" 6261da177e4SLinus Torvalds,institution="US Patent and Trademark Office" 6271da177e4SLinus Torvalds,address="Washington, DC" 6281da177e4SLinus Torvalds,year="2001" 6294c62abc9SPaul E. McKenney,number="US Patent 6,219,690" 6301da177e4SLinus Torvalds,month="April" 6314c62abc9SPaul E. McKenney,annotation={ 6324c62abc9SPaul E. McKenney 'Change in mode' aspect of RCU. Can be thought of as a lazy barrier. 6334c62abc9SPaul E. McKenney} 6341da177e4SLinus Torvalds} 6351da177e4SLinus Torvalds 6361da177e4SLinus Torvalds@Conference{McKenney01a 6371da177e4SLinus Torvalds,Author="Paul E. McKenney and Jonathan Appavoo and Andi Kleen and 6381da177e4SLinus TorvaldsOrran Krieger and Rusty Russell and Dipankar Sarma and Maneesh Soni" 6391da177e4SLinus Torvalds,Title="Read-Copy Update" 6401da177e4SLinus Torvalds,Booktitle="{Ottawa Linux Symposium}" 6411da177e4SLinus Torvalds,Month="July" 6421da177e4SLinus Torvalds,Year="2001" 6431da177e4SLinus Torvalds,note="Available: 6441da177e4SLinus Torvalds\url{http://www.linuxsymposium.org/2001/abstracts/readcopy.php} 6454c62abc9SPaul E. McKenney\url{http://www.rdrop.com/users/paulmck/RCU/rclock_OLS.2001.05.01c.pdf} 6461da177e4SLinus Torvalds[Viewed June 23, 2004]" 6474c62abc9SPaul E. McKenney,annotation={ 6484c62abc9SPaul E. McKenney Described RCU, and presented some patches implementing and using 6494c62abc9SPaul E. McKenney it in the Linux kernel. 6504c62abc9SPaul E. McKenney} 6514c62abc9SPaul E. McKenney} 6524c62abc9SPaul E. McKenney 6534c62abc9SPaul E. McKenney@unpublished{McKenney01f 6544c62abc9SPaul E. McKenney,Author="Paul E. McKenney" 6554c62abc9SPaul E. McKenney,Title="{RFC:} patch to allow lock-free traversal of lists with insertion" 6564c62abc9SPaul E. McKenney,month="October" 6574c62abc9SPaul E. McKenney,year="2001" 6584c62abc9SPaul E. McKenney,note="Available: 6594c62abc9SPaul E. McKenney\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=100259266316456&w=2} 6604c62abc9SPaul E. McKenney[Viewed June 23, 2004]" 6616ae37718SPaul E. McKenney,annotation={ 6624c62abc9SPaul E. McKenney Memory-barrier and Alpha thread. 100 messages, not too bad... 6636ae37718SPaul E. McKenney} 6641da177e4SLinus Torvalds} 6651da177e4SLinus Torvalds 6664c62abc9SPaul E. McKenney@unpublished{Spraul01 6674c62abc9SPaul E. McKenney,Author="Manfred Spraul" 6684c62abc9SPaul E. McKenney,Title="Re: {RFC:} patch to allow lock-free traversal of lists with insertion" 6694c62abc9SPaul E. McKenney,month="October" 6704c62abc9SPaul E. McKenney,year="2001" 6714c62abc9SPaul E. McKenney,note="Available: 6724c62abc9SPaul E. McKenney\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=100264675012867&w=2} 6734c62abc9SPaul E. McKenney[Viewed June 23, 2004]" 6746ae37718SPaul E. McKenney,annotation={ 6754c62abc9SPaul E. McKenney Suggested burying memory barriers in Linux's list-manipulation 6764c62abc9SPaul E. McKenney primitives. 6776ae37718SPaul E. McKenney} 6784c62abc9SPaul E. McKenney} 6794c62abc9SPaul E. McKenney 6804c62abc9SPaul E. McKenney@unpublished{LinusTorvalds2001a 6814c62abc9SPaul E. McKenney,Author="Linus Torvalds" 6824c62abc9SPaul E. McKenney,Title="{Re:} {[Lse-tech]} {Re:} {RFC:} patch to allow lock-free traversal of lists with insertion" 6834c62abc9SPaul E. McKenney,month="October" 6844c62abc9SPaul E. McKenney,year="2001" 6854c62abc9SPaul E. McKenney,note="Available: 6864c62abc9SPaul E. McKenney\url{http://lkml.org/lkml/2001/10/13/105} 6874c62abc9SPaul E. McKenney[Viewed August 21, 2004]" 6886ae37718SPaul E. McKenney,annotation={ 6896ae37718SPaul E. McKenney} 6904c62abc9SPaul E. McKenney} 6914c62abc9SPaul E. McKenney 6924c62abc9SPaul E. McKenney@unpublished{Blanchard02a 6934c62abc9SPaul E. McKenney,Author="Anton Blanchard" 6944c62abc9SPaul E. McKenney,Title="some RCU dcache and ratcache results" 6954c62abc9SPaul E. McKenney,month="March" 6964c62abc9SPaul E. McKenney,year="2002" 6974c62abc9SPaul E. McKenney,note="Available: 6984c62abc9SPaul E. McKenney\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=101637107412972&w=2} 6994c62abc9SPaul E. McKenney[Viewed October 18, 2004]" 7004c62abc9SPaul E. McKenney} 7014c62abc9SPaul E. McKenney 702e4696a1dSPaul E. McKenney@conference{Michael02b 703e4696a1dSPaul E. McKenney,author="Maged M. Michael" 704e4696a1dSPaul E. McKenney,title="High Performance Dynamic Lock-Free Hash Tables and List-Based Sets" 705e4696a1dSPaul E. McKenney,Year="2002" 706e4696a1dSPaul E. McKenney,Month="August" 707e4696a1dSPaul E. McKenney,booktitle="{Proceedings of the 14\textsuperscript{th} Annual ACM 708e4696a1dSPaul E. McKenneySymposium on Parallel 709e4696a1dSPaul E. McKenneyAlgorithms and Architecture}" 710e4696a1dSPaul E. McKenney,pages="73-82" 711e4696a1dSPaul E. McKenney,annotation={ 712e4696a1dSPaul E. McKenneyLike the title says... 713e4696a1dSPaul E. McKenney} 714e4696a1dSPaul E. McKenney} 715e4696a1dSPaul E. McKenney 7161da177e4SLinus Torvalds@Conference{Linder02a 7171da177e4SLinus Torvalds,Author="Hanna Linder and Dipankar Sarma and Maneesh Soni" 7181da177e4SLinus Torvalds,Title="Scalability of the Directory Entry Cache" 7191da177e4SLinus Torvalds,Booktitle="{Ottawa Linux Symposium}" 7201da177e4SLinus Torvalds,Month="June" 7211da177e4SLinus Torvalds,Year="2002" 7221da177e4SLinus Torvalds,pages="289-300" 7236ae37718SPaul E. McKenney,annotation={ 7244c62abc9SPaul E. McKenney Measured scalability of Linux 2.4 kernel's directory-entry cache 7254c62abc9SPaul E. McKenney (dcache), and measured some scalability enhancements. 7266ae37718SPaul E. McKenney} 7271da177e4SLinus Torvalds} 7281da177e4SLinus Torvalds 7291da177e4SLinus Torvalds@Conference{McKenney02a 7301da177e4SLinus Torvalds,Author="Paul E. McKenney and Dipankar Sarma and 7311da177e4SLinus TorvaldsAndrea Arcangeli and Andi Kleen and Orran Krieger and Rusty Russell" 7321da177e4SLinus Torvalds,Title="Read-Copy Update" 7331da177e4SLinus Torvalds,Booktitle="{Ottawa Linux Symposium}" 7341da177e4SLinus Torvalds,Month="June" 7351da177e4SLinus Torvalds,Year="2002" 7361da177e4SLinus Torvalds,pages="338-367" 7371da177e4SLinus Torvalds,note="Available: 7381da177e4SLinus Torvalds\url{http://www.linux.org.uk/~ajh/ols2002_proceedings.pdf.gz} 7391da177e4SLinus Torvalds[Viewed June 23, 2004]" 7406ae37718SPaul E. McKenney,annotation={ 7414c62abc9SPaul E. McKenney Presented and compared a number of RCU implementations for the 7424c62abc9SPaul E. McKenney Linux kernel. 7436ae37718SPaul E. McKenney} 744f85d6c71SPaul E. McKenney} 745f85d6c71SPaul E. McKenney 7464c62abc9SPaul E. McKenney@unpublished{Sarma02a 7474c62abc9SPaul E. McKenney,Author="Dipankar Sarma" 7484c62abc9SPaul E. McKenney,Title="specweb99: dcache scalability results" 7494c62abc9SPaul E. McKenney,month="July" 7504c62abc9SPaul E. McKenney,year="2002" 7514c62abc9SPaul E. McKenney,note="Available: 7524c62abc9SPaul E. McKenney\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=102645767914212&w=2} 7534c62abc9SPaul E. McKenney[Viewed June 23, 2004]" 7546ae37718SPaul E. McKenney,annotation={ 7554c62abc9SPaul E. McKenney Compare fastwalk and RCU for dcache. RCU won. 7566ae37718SPaul E. McKenney} 757f85d6c71SPaul E. McKenney} 758f85d6c71SPaul E. McKenney 7594c62abc9SPaul E. McKenney@unpublished{Barbieri02 7604c62abc9SPaul E. McKenney,Author="Luca Barbieri" 7614c62abc9SPaul E. McKenney,Title="Re: {[PATCH]} Initial support for struct {vfs\_cred}" 7624c62abc9SPaul E. McKenney,month="August" 7634c62abc9SPaul E. McKenney,year="2002" 7644c62abc9SPaul E. McKenney,note="Available: 7654c62abc9SPaul E. McKenney\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=103082050621241&w=2} 7664c62abc9SPaul E. McKenney[Viewed: June 23, 2004]" 7676ae37718SPaul E. McKenney,annotation={ 7684c62abc9SPaul E. McKenney Suggested RCU for vfs\_shared\_cred. 7696ae37718SPaul E. McKenney} 7704c62abc9SPaul E. McKenney} 7714c62abc9SPaul E. McKenney 772e4696a1dSPaul E. McKenney@conference{Michael02a 773e4696a1dSPaul E. McKenney,author="Maged M. Michael" 774e4696a1dSPaul E. McKenney,title="Safe Memory Reclamation for Dynamic Lock-Free Objects Using Atomic 775e4696a1dSPaul E. McKenneyReads and Writes" 776e4696a1dSPaul E. McKenney,Year="2002" 777e4696a1dSPaul E. McKenney,Month="August" 778e4696a1dSPaul E. McKenney,booktitle="{Proceedings of the 21\textsuperscript{st} Annual ACM 779e4696a1dSPaul E. McKenneySymposium on Principles of Distributed Computing}" 780e4696a1dSPaul E. McKenney,pages="21-30" 781e4696a1dSPaul E. McKenney,annotation={ 782e4696a1dSPaul E. McKenney Each thread keeps an array of pointers to items that it is 783e4696a1dSPaul E. McKenney currently referencing. Sort of an inside-out garbage collection 784e4696a1dSPaul E. McKenney mechanism, but one that requires the accessing code to explicitly 785e4696a1dSPaul E. McKenney state its needs. Also requires read-side memory barriers on 786e4696a1dSPaul E. McKenney most architectures. 787e4696a1dSPaul E. McKenney} 788e4696a1dSPaul E. McKenney} 789e4696a1dSPaul E. McKenney 7904c62abc9SPaul E. McKenney@unpublished{Dickins02a 7914c62abc9SPaul E. McKenney,author="Hugh Dickins" 7924c62abc9SPaul E. McKenney,title="Use RCU for System-V IPC" 7934c62abc9SPaul E. McKenney,year="2002" 794f85d6c71SPaul E. McKenney,month="October" 7954c62abc9SPaul E. McKenney,note="private communication" 7964c62abc9SPaul E. McKenney} 7974c62abc9SPaul E. McKenney 798e4696a1dSPaul E. McKenney@InProceedings{HerlihyLM02 799e4696a1dSPaul E. McKenney,author={Maurice Herlihy and Victor Luchangco and Mark Moir} 800e4696a1dSPaul E. McKenney,title="The Repeat Offender Problem: A Mechanism for Supporting Dynamic-Sized, 801e4696a1dSPaul E. McKenneyLock-Free Data Structures" 802e4696a1dSPaul E. McKenney,booktitle={Proceedings of 16\textsuperscript{th} International 803e4696a1dSPaul E. McKenneySymposium on Distributed Computing} 804e4696a1dSPaul E. McKenney,year=2002 805e4696a1dSPaul E. McKenney,month="October" 806e4696a1dSPaul E. McKenney,pages="339-353" 807e4696a1dSPaul E. McKenney} 808e4696a1dSPaul E. McKenney 8094c62abc9SPaul E. McKenney@unpublished{Sarma02b 8104c62abc9SPaul E. McKenney,Author="Dipankar Sarma" 8114c62abc9SPaul E. McKenney,Title="Some dcache\_rcu benchmark numbers" 8124c62abc9SPaul E. McKenney,month="October" 8134c62abc9SPaul E. McKenney,year="2002" 8144c62abc9SPaul E. McKenney,note="Available: 8154c62abc9SPaul E. McKenney\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=103462075416638&w=2} 8164c62abc9SPaul E. McKenney[Viewed June 23, 2004]" 8176ae37718SPaul E. McKenney,annotation={ 8184c62abc9SPaul E. McKenney Performance of dcache RCU on kernbench for 16x NUMA-Q and 1x, 8194c62abc9SPaul E. McKenney 2x, and 4x systems. RCU does no harm, and helps on 16x. 8206ae37718SPaul E. McKenney} 8214c62abc9SPaul E. McKenney} 8224c62abc9SPaul E. McKenney 823e4696a1dSPaul E. McKenney@unpublished{MingmingCao2002IPCRCU 824e4696a1dSPaul E. McKenney,Author="Mingming Cao" 825e4696a1dSPaul E. McKenney,Title="[PATCH]updated ipc lock patch" 826e4696a1dSPaul E. McKenney,month="October" 827e4696a1dSPaul E. McKenney,year="2002" 828e4696a1dSPaul E. McKenney,note="Available: 829e4696a1dSPaul E. McKenney\url{https://lkml.org/lkml/2002/10/24/262} 830e4696a1dSPaul E. McKenney[Viewed February 15, 2014]" 831e4696a1dSPaul E. McKenney,annotation={ 832e4696a1dSPaul E. McKenney Mingming Cao's patch to introduce RCU to SysV IPC. 833e4696a1dSPaul E. McKenney} 834e4696a1dSPaul E. McKenney} 835e4696a1dSPaul E. McKenney 8364c62abc9SPaul E. McKenney@unpublished{LinusTorvalds2003a 8374c62abc9SPaul E. McKenney,Author="Linus Torvalds" 8384c62abc9SPaul E. McKenney,Title="Re: {[PATCH]} small fixes in brlock.h" 8394c62abc9SPaul E. McKenney,month="March" 8404c62abc9SPaul E. McKenney,year="2003" 8414c62abc9SPaul E. McKenney,note="Available: 8424c62abc9SPaul E. McKenney\url{http://lkml.org/lkml/2003/3/9/205} 8434c62abc9SPaul E. McKenney[Viewed March 13, 2006]" 8446ae37718SPaul E. McKenney,annotation={ 8454c62abc9SPaul E. McKenney Linus suggests replacing brlock with RCU and/or seqlocks: 8464c62abc9SPaul E. McKenney . 8474c62abc9SPaul E. McKenney 'It's entirely possible that the current user could be replaced 8484c62abc9SPaul E. McKenney by RCU and/or seqlocks, and we could get rid of brlocks entirely.' 8494c62abc9SPaul E. McKenney . 8504c62abc9SPaul E. McKenney Steve Hemminger responds by replacing them with RCU. 8516ae37718SPaul E. McKenney} 852f85d6c71SPaul E. McKenney} 853f85d6c71SPaul E. McKenney 8541da177e4SLinus Torvalds@article{Appavoo03a 8551da177e4SLinus Torvalds,author="J. Appavoo and K. Hui and C. A. N. Soules and R. W. Wisniewski and 8561da177e4SLinus TorvaldsD. M. {Da Silva} and O. Krieger and M. A. Auslander and D. J. Edelsohn and 8571da177e4SLinus TorvaldsB. Gamsa and G. R. Ganger and P. McKenney and M. Ostrowski and 8581da177e4SLinus TorvaldsB. Rosenburg and M. Stumm and J. Xenidis" 8591da177e4SLinus Torvalds,title="Enabling Autonomic Behavior in Systems Software With Hot Swapping" 8601da177e4SLinus Torvalds,Year="2003" 8611da177e4SLinus Torvalds,Month="January" 8621da177e4SLinus Torvalds,journal="IBM Systems Journal" 8631da177e4SLinus Torvalds,volume="42" 8641da177e4SLinus Torvalds,number="1" 8651da177e4SLinus Torvalds,pages="60-76" 8666ae37718SPaul E. McKenney,annotation={ 8674c62abc9SPaul E. McKenney Use of RCU to enable hot-swapping for autonomic behavior in K42. 8686ae37718SPaul E. McKenney} 8694c62abc9SPaul E. McKenney} 8704c62abc9SPaul E. McKenney 8714c62abc9SPaul E. McKenney@unpublished{Seigh03 8724c62abc9SPaul E. McKenney,author="Joseph W. {Seigh II}" 8734c62abc9SPaul E. McKenney,title="Read Copy Update" 8744c62abc9SPaul E. McKenney,Year="2003" 8754c62abc9SPaul E. McKenney,Month="March" 8764c62abc9SPaul E. McKenney,note="email correspondence" 8776ae37718SPaul E. McKenney,annotation={ 8784c62abc9SPaul E. McKenney Described the relationship of the VM/XA passive serialization to RCU. 8796ae37718SPaul E. McKenney} 8801da177e4SLinus Torvalds} 8811da177e4SLinus Torvalds 8821da177e4SLinus Torvalds@Conference{Arcangeli03 8831da177e4SLinus Torvalds,Author="Andrea Arcangeli and Mingming Cao and Paul E. McKenney and 8841da177e4SLinus TorvaldsDipankar Sarma" 8851da177e4SLinus Torvalds,Title="Using Read-Copy Update Techniques for {System V IPC} in the 8861da177e4SLinus Torvalds{Linux} 2.5 Kernel" 8871da177e4SLinus Torvalds,Booktitle="Proceedings of the 2003 USENIX Annual Technical Conference 8881da177e4SLinus Torvalds(FREENIX Track)" 8891da177e4SLinus Torvalds,Publisher="USENIX Association" 8901da177e4SLinus Torvalds,year="2003" 8911da177e4SLinus Torvalds,month="June" 8921da177e4SLinus Torvalds,pages="297-310" 8936ae37718SPaul E. McKenney,annotation={ 8944c62abc9SPaul E. McKenney Compared updated RCU implementations for the Linux kernel, and 8954c62abc9SPaul E. McKenney described System V IPC use of RCU, including order-of-magnitude 8964c62abc9SPaul E. McKenney performance improvements. 8976ae37718SPaul E. McKenney http://www.rdrop.com/users/paulmck/RCU/rcu.FREENIX.2003.06.14.pdf 8986ae37718SPaul E. McKenney} 8994c62abc9SPaul E. McKenney} 9004c62abc9SPaul E. McKenney 9014c62abc9SPaul E. McKenney@Conference{Soules03a 9024c62abc9SPaul E. McKenney,Author="Craig A. N. Soules and Jonathan Appavoo and Kevin Hui and 9034c62abc9SPaul E. McKenneyDilma {Da Silva} and Gregory R. Ganger and Orran Krieger and 9044c62abc9SPaul E. McKenneyMichael Stumm and Robert W. Wisniewski and Marc Auslander and 9054c62abc9SPaul E. McKenneyMichal Ostrowski and Bryan Rosenburg and Jimi Xenidis" 9064c62abc9SPaul E. McKenney,Title="System Support for Online Reconfiguration" 9074c62abc9SPaul E. McKenney,Booktitle="Proceedings of the 2003 USENIX Annual Technical Conference" 9084c62abc9SPaul E. McKenney,Publisher="USENIX Association" 9094c62abc9SPaul E. McKenney,year="2003" 9104c62abc9SPaul E. McKenney,month="June" 9114c62abc9SPaul E. McKenney,pages="141-154" 9121da177e4SLinus Torvalds} 9131da177e4SLinus Torvalds 9141da177e4SLinus Torvalds@article{McKenney03a 9151da177e4SLinus Torvalds,author="Paul E. McKenney" 9161da177e4SLinus Torvalds,title="Using {RCU} in the {Linux} 2.5 Kernel" 9171da177e4SLinus Torvalds,Year="2003" 9181da177e4SLinus Torvalds,Month="October" 9191da177e4SLinus Torvalds,journal="Linux Journal" 9201da177e4SLinus Torvalds,volume="1" 9211da177e4SLinus Torvalds,number="114" 9221da177e4SLinus Torvalds,pages="18-26" 9234c62abc9SPaul E. McKenney,note="Available: 9244c62abc9SPaul E. McKenney\url{http://www.linuxjournal.com/article/6993} 9254c62abc9SPaul E. McKenney[Viewed November 14, 2007]" 9266ae37718SPaul E. McKenney,annotation={ 9274c62abc9SPaul E. McKenney Reader-friendly intro to RCU, with the infamous old-man-and-brat 9284c62abc9SPaul E. McKenney cartoon. 9296ae37718SPaul E. McKenney} 9304c62abc9SPaul E. McKenney} 9314c62abc9SPaul E. McKenney 9324c62abc9SPaul E. McKenney@unpublished{Sarma03a 9334c62abc9SPaul E. McKenney,Author="Dipankar Sarma" 9344c62abc9SPaul E. McKenney,Title="RCU low latency patches" 9354c62abc9SPaul E. McKenney,month="December" 9364c62abc9SPaul E. McKenney,year="2003" 9374c62abc9SPaul E. McKenney,note="Message ID: 20031222180114.GA2248@in.ibm.com" 9386ae37718SPaul E. McKenney,annotation={ 9396ae37718SPaul E. McKenney dipankar/ct.2004.03.27/RCUll.2003.12.22.patch 9406ae37718SPaul E. McKenney} 9411da177e4SLinus Torvalds} 9421da177e4SLinus Torvalds 943a83f1fe2SPaul E. McKenney@techreport{Friedberg03a 944a83f1fe2SPaul E. McKenney,author="Stuart A. Friedberg" 945a83f1fe2SPaul E. McKenney,title="Lock-Free Wild Card Search Data Structure and Method" 946a83f1fe2SPaul E. McKenney,institution="US Patent and Trademark Office" 947a83f1fe2SPaul E. McKenney,address="Washington, DC" 948a83f1fe2SPaul E. McKenney,year="2003" 9494c62abc9SPaul E. McKenney,number="US Patent 6,662,184" 950a83f1fe2SPaul E. McKenney,month="December" 951a83f1fe2SPaul E. McKenney,pages="112" 9526ae37718SPaul E. McKenney,annotation={ 9534c62abc9SPaul E. McKenney Applies RCU to a wildcard-search Patricia tree in order to permit 9544c62abc9SPaul E. McKenney synchronization-free lookup. RCU is used to retain removed nodes 9554c62abc9SPaul E. McKenney for a grace period before freeing them. 9566ae37718SPaul E. McKenney} 957a83f1fe2SPaul E. McKenney} 958a83f1fe2SPaul E. McKenney 9591da177e4SLinus Torvalds@article{McKenney04a 9601da177e4SLinus Torvalds,author="Paul E. McKenney and Dipankar Sarma and Maneesh Soni" 9611da177e4SLinus Torvalds,title="Scaling dcache with {RCU}" 9621da177e4SLinus Torvalds,Year="2004" 9631da177e4SLinus Torvalds,Month="January" 9641da177e4SLinus Torvalds,journal="Linux Journal" 9651da177e4SLinus Torvalds,volume="1" 9661da177e4SLinus Torvalds,number="118" 9671da177e4SLinus Torvalds,pages="38-46" 9686ae37718SPaul E. McKenney,annotation={ 9694c62abc9SPaul E. McKenney Reader friendly intro to dcache and RCU. 9706ae37718SPaul E. McKenney http://www.linuxjournal.com/node/7124 9716ae37718SPaul E. McKenney [Viewed December 26, 2010] 9726ae37718SPaul E. McKenney} 9731da177e4SLinus Torvalds} 9741da177e4SLinus Torvalds 9751da177e4SLinus Torvalds@Conference{McKenney04b 9761da177e4SLinus Torvalds,Author="Paul E. McKenney" 9771da177e4SLinus Torvalds,Title="{RCU} vs. Locking Performance on Different {CPUs}" 9781da177e4SLinus Torvalds,Booktitle="{linux.conf.au}" 9791da177e4SLinus Torvalds,Month="January" 9801da177e4SLinus Torvalds,Year="2004" 9811da177e4SLinus Torvalds,Address="Adelaide, Australia" 9821da177e4SLinus Torvalds,note="Available: 9831da177e4SLinus Torvalds\url{http://www.linux.org.au/conf/2004/abstracts.html#90} 9844c62abc9SPaul E. McKenney\url{http://www.rdrop.com/users/paulmck/RCU/lockperf.2004.01.17a.pdf} 9851da177e4SLinus Torvalds[Viewed June 23, 2004]" 9866ae37718SPaul E. McKenney,annotation={ 9874c62abc9SPaul E. McKenney Compares performance of RCU to that of other locking primitives 9884c62abc9SPaul E. McKenney over a number of CPUs (x86, Opteron, Itanium, and PPC). 9896ae37718SPaul E. McKenney} 9904c62abc9SPaul E. McKenney} 9914c62abc9SPaul E. McKenney 9924c62abc9SPaul E. McKenney@unpublished{Sarma04a 9934c62abc9SPaul E. McKenney,Author="Dipankar Sarma" 9944c62abc9SPaul E. McKenney,Title="{[PATCH]} {RCU} for low latency (experimental)" 9954c62abc9SPaul E. McKenney,month="March" 9964c62abc9SPaul E. McKenney,year="2004" 9974c62abc9SPaul E. McKenney,note="\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=108003746402892&w=2}" 9986ae37718SPaul E. McKenney,annotation={ 9996ae37718SPaul E. McKenney Head of thread: dipankar/2004.03.23/rcu-low-lat.1.patch 10006ae37718SPaul E. McKenney} 10014c62abc9SPaul E. McKenney} 10024c62abc9SPaul E. McKenney 10034c62abc9SPaul E. McKenney@unpublished{Sarma04b 10044c62abc9SPaul E. McKenney,Author="Dipankar Sarma" 10054c62abc9SPaul E. McKenney,Title="Re: {[PATCH]} {RCU} for low latency (experimental)" 10064c62abc9SPaul E. McKenney,month="March" 10074c62abc9SPaul E. McKenney,year="2004" 10084c62abc9SPaul E. McKenney,note="\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=108016474829546&w=2}" 10096ae37718SPaul E. McKenney,annotation={ 10106ae37718SPaul E. McKenney dipankar/rcuth.2004.03.24/rcu-throttle.patch 10116ae37718SPaul E. McKenney} 10124c62abc9SPaul E. McKenney} 10134c62abc9SPaul E. McKenney 10144c62abc9SPaul E. McKenney@unpublished{Spraul04a 10154c62abc9SPaul E. McKenney,Author="Manfred Spraul" 10164c62abc9SPaul E. McKenney,Title="[RFC] 0/5 rcu lock update" 10174c62abc9SPaul E. McKenney,month="May" 10184c62abc9SPaul E. McKenney,year="2004" 10194c62abc9SPaul E. McKenney,note="Available: 10204c62abc9SPaul E. McKenney\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=108546407726602&w=2} 10214c62abc9SPaul E. McKenney[Viewed June 23, 2004]" 10226ae37718SPaul E. McKenney,annotation={ 10234c62abc9SPaul E. McKenney Hierarchical-bitmap patch for RCU infrastructure. 10246ae37718SPaul E. McKenney} 10254c62abc9SPaul E. McKenney} 10264c62abc9SPaul E. McKenney 10274c62abc9SPaul E. McKenney@unpublished{Steiner04a 10284c62abc9SPaul E. McKenney,Author="Jack Steiner" 10294c62abc9SPaul E. McKenney,Title="Re: [Lse-tech] [RFC, PATCH] 1/5 rcu lock update: 10304c62abc9SPaul E. McKenneyAdd per-cpu batch counter" 10314c62abc9SPaul E. McKenney,month="May" 10324c62abc9SPaul E. McKenney,year="2004" 10334c62abc9SPaul E. McKenney,note="Available: 10344c62abc9SPaul E. McKenney\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=108551764515332&w=2} 10354c62abc9SPaul E. McKenney[Viewed June 23, 2004]" 10364c62abc9SPaul E. McKenney,annotation={ 10374c62abc9SPaul E. McKenney RCU runs reasonably on a 512-CPU SGI using Manfred Spraul's patches, 10384c62abc9SPaul E. McKenney which may be found at: 10394c62abc9SPaul E. McKenney https://lkml.org/lkml/2004/5/20/49 (split vars into cachelines) 10404c62abc9SPaul E. McKenney https://lkml.org/lkml/2004/5/22/114 (cpu_quiet() patch) 10414c62abc9SPaul E. McKenney https://lkml.org/lkml/2004/5/25/24 (0/5) 10424c62abc9SPaul E. McKenney https://lkml.org/lkml/2004/5/25/23 (1/5) 10434c62abc9SPaul E. McKenney https://lkml.org/lkml/2004/5/25/265 (works for Jack) 10444c62abc9SPaul E. McKenney https://lkml.org/lkml/2004/5/25/20 (2/5) 10454c62abc9SPaul E. McKenney https://lkml.org/lkml/2004/5/25/22 (3/5) 10464c62abc9SPaul E. McKenney https://lkml.org/lkml/2004/5/25/19 (4/5) 10474c62abc9SPaul E. McKenney https://lkml.org/lkml/2004/5/25/21 (5/5) 10484c62abc9SPaul E. McKenney} 10494c62abc9SPaul E. McKenney} 10504c62abc9SPaul E. McKenney 10514c62abc9SPaul E. McKenney@Conference{Sarma04c 10524c62abc9SPaul E. McKenney,Author="Dipankar Sarma and Paul E. McKenney" 10534c62abc9SPaul E. McKenney,Title="Making {RCU} Safe for Deep Sub-Millisecond Response 10544c62abc9SPaul E. McKenneyRealtime Applications" 10554c62abc9SPaul E. McKenney,Booktitle="Proceedings of the 2004 USENIX Annual Technical Conference 10564c62abc9SPaul E. McKenney(FREENIX Track)" 10574c62abc9SPaul E. McKenney,Publisher="USENIX Association" 10584c62abc9SPaul E. McKenney,year="2004" 10594c62abc9SPaul E. McKenney,month="June" 10604c62abc9SPaul E. McKenney,pages="182-191" 10616ae37718SPaul E. McKenney,annotation={ 10624c62abc9SPaul E. McKenney Describes and compares a number of modifications to the Linux RCU 10634c62abc9SPaul E. McKenney implementation that make it friendly to realtime applications. 10646ae37718SPaul E. McKenney https://www.usenix.org/conference/2004-usenix-annual-technical-conference/making-rcu-safe-deep-sub-millisecond-response 10656ae37718SPaul E. McKenney [Viewed July 26, 2012] 10666ae37718SPaul E. McKenney} 10671da177e4SLinus Torvalds} 10681da177e4SLinus Torvalds 1069e4696a1dSPaul E. McKenney@article{MagedMichael04a 1070e4696a1dSPaul E. McKenney,author="Maged M. Michael" 1071e4696a1dSPaul E. McKenney,title="Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects" 1072e4696a1dSPaul E. McKenney,Year="2004" 1073e4696a1dSPaul E. McKenney,Month="June" 1074e4696a1dSPaul E. McKenney,journal="IEEE Transactions on Parallel and Distributed Systems" 1075e4696a1dSPaul E. McKenney,volume="15" 1076e4696a1dSPaul E. McKenney,number="6" 1077e4696a1dSPaul E. McKenney,pages="491-504" 1078e4696a1dSPaul E. McKenney,url="Available: 1079e4696a1dSPaul E. McKenney\url{http://www.research.ibm.com/people/m/michael/ieeetpds-2004.pdf} 1080e4696a1dSPaul E. McKenney[Viewed March 1, 2005]" 1081e4696a1dSPaul E. McKenney,annotation={ 1082e4696a1dSPaul E. McKenney New canonical hazard-pointer citation. 1083e4696a1dSPaul E. McKenney} 1084e4696a1dSPaul E. McKenney} 1085e4696a1dSPaul E. McKenney 10861da177e4SLinus Torvalds@phdthesis{PaulEdwardMcKenneyPhD 10871da177e4SLinus Torvalds,author="Paul E. McKenney" 10881da177e4SLinus Torvalds,title="Exploiting Deferred Destruction: 10891da177e4SLinus TorvaldsAn Analysis of Read-Copy-Update Techniques 10901da177e4SLinus Torvaldsin Operating System Kernels" 10911da177e4SLinus Torvalds,school="OGI School of Science and Engineering at 10921da177e4SLinus TorvaldsOregon Health and Sciences University" 10931da177e4SLinus Torvalds,year="2004" 10946ae37718SPaul E. McKenney,annotation={ 10954c62abc9SPaul E. McKenney Describes RCU implementations and presents design patterns 10964c62abc9SPaul E. McKenney corresponding to common uses of RCU in several operating-system 10974c62abc9SPaul E. McKenney kernels. 10986ae37718SPaul E. McKenney http://www.rdrop.com/users/paulmck/RCU/RCUdissertation.2004.07.14e1.pdf 10996ae37718SPaul E. McKenney [Viewed October 15, 2004] 11006ae37718SPaul E. McKenney} 11011da177e4SLinus Torvalds} 11021da177e4SLinus Torvalds 11034c62abc9SPaul E. McKenney@unpublished{PaulEMcKenney2004rcu:dereference 11044c62abc9SPaul E. McKenney,Author="Dipankar Sarma" 11054c62abc9SPaul E. McKenney,Title="{Re: RCU : Abstracted RCU dereferencing [5/5]}" 11064c62abc9SPaul E. McKenney,month="August" 11071da177e4SLinus Torvalds,year="2004" 11084c62abc9SPaul E. McKenney,note="Available: 11094c62abc9SPaul E. McKenney\url{http://lkml.org/lkml/2004/8/6/237} 11104c62abc9SPaul E. McKenney[Viewed June 8, 2010]" 11116ae37718SPaul E. McKenney,annotation={ 11124c62abc9SPaul E. McKenney Introduce rcu_dereference(). 11136ae37718SPaul E. McKenney} 11144c62abc9SPaul E. McKenney} 11154c62abc9SPaul E. McKenney 11164c62abc9SPaul E. McKenney@unpublished{JimHouston04a 11174c62abc9SPaul E. McKenney,Author="Jim Houston" 11184c62abc9SPaul E. McKenney,Title="{[RFC\&PATCH] Alternative {RCU} implementation}" 11194c62abc9SPaul E. McKenney,month="August" 11204c62abc9SPaul E. McKenney,year="2004" 11214c62abc9SPaul E. McKenney,note="Available: 11224c62abc9SPaul E. McKenney\url{http://lkml.org/lkml/2004/8/30/87} 11234c62abc9SPaul E. McKenney[Viewed February 17, 2005]" 11246ae37718SPaul E. McKenney,annotation={ 11254c62abc9SPaul E. McKenney Uses active code in rcu_read_lock() and rcu_read_unlock() to 11264c62abc9SPaul E. McKenney make RCU happen, allowing RCU to function on CPUs that do not 11274c62abc9SPaul E. McKenney receive a scheduling-clock interrupt. 11286ae37718SPaul E. McKenney} 11294c62abc9SPaul E. McKenney} 11304c62abc9SPaul E. McKenney 11314c62abc9SPaul E. McKenney@unpublished{TomHart04a 11324c62abc9SPaul E. McKenney,Author="Thomas E. Hart" 11334c62abc9SPaul E. McKenney,Title="Master's Thesis: Applying Lock-free Techniques to the {Linux} Kernel" 11344c62abc9SPaul E. McKenney,month="October" 11354c62abc9SPaul E. McKenney,year="2004" 11364c62abc9SPaul E. McKenney,note="Available: 11374c62abc9SPaul E. McKenney\url{http://www.cs.toronto.edu/~tomhart/masters_thesis.html} 11384c62abc9SPaul E. McKenney[Viewed October 15, 2004]" 11396ae37718SPaul E. McKenney,annotation={ 11404c62abc9SPaul E. McKenney Proposes comparing RCU to lock-free methods for the Linux kernel. 11416ae37718SPaul E. McKenney} 11424c62abc9SPaul E. McKenney} 11434c62abc9SPaul E. McKenney 11444c62abc9SPaul E. McKenney@unpublished{Vaddagiri04a 11454c62abc9SPaul E. McKenney,Author="Srivatsa Vaddagiri" 11464c62abc9SPaul E. McKenney,Title="Subject: [RFC] Use RCU for tcp\_ehash lookup" 11474c62abc9SPaul E. McKenney,month="October" 11484c62abc9SPaul E. McKenney,year="2004" 11494c62abc9SPaul E. McKenney,note="Available: 11504c62abc9SPaul E. McKenney\url{http://marc.theaimsgroup.com/?t=109395731700004&r=1&w=2} 11514c62abc9SPaul E. McKenney[Viewed October 18, 2004]" 11526ae37718SPaul E. McKenney,annotation={ 11534c62abc9SPaul E. McKenney Srivatsa's RCU patch for tcp_ehash lookup. 11546ae37718SPaul E. McKenney} 11554c62abc9SPaul E. McKenney} 11564c62abc9SPaul E. McKenney 11574c62abc9SPaul E. McKenney@unpublished{Thirumalai04a 11584c62abc9SPaul E. McKenney,Author="Ravikiran Thirumalai" 11594c62abc9SPaul E. McKenney,Title="Subject: [patchset] Lockfree fd lookup 0 of 5" 11604c62abc9SPaul E. McKenney,month="October" 11614c62abc9SPaul E. McKenney,year="2004" 11624c62abc9SPaul E. McKenney,note="Available: 11634c62abc9SPaul E. McKenney\url{http://marc.theaimsgroup.com/?t=109144217400003&r=1&w=2} 11644c62abc9SPaul E. McKenney[Viewed October 18, 2004]" 11656ae37718SPaul E. McKenney,annotation={ 11664c62abc9SPaul E. McKenney Ravikiran's lockfree FD patch. 11676ae37718SPaul E. McKenney} 11684c62abc9SPaul E. McKenney} 11694c62abc9SPaul E. McKenney 11704c62abc9SPaul E. McKenney@unpublished{Thirumalai04b 11714c62abc9SPaul E. McKenney,Author="Ravikiran Thirumalai" 11724c62abc9SPaul E. McKenney,Title="Subject: Re: [patchset] Lockfree fd lookup 0 of 5" 11734c62abc9SPaul E. McKenney,month="October" 11744c62abc9SPaul E. McKenney,year="2004" 11754c62abc9SPaul E. McKenney,note="Available: 11764c62abc9SPaul E. McKenney\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=109152521410459&w=2} 11774c62abc9SPaul E. McKenney[Viewed October 18, 2004]" 11786ae37718SPaul E. McKenney,annotation={ 11794c62abc9SPaul E. McKenney Ravikiran's lockfree FD patch. 11806ae37718SPaul E. McKenney} 11814c62abc9SPaul E. McKenney} 11824c62abc9SPaul E. McKenney 11834c62abc9SPaul E. McKenney@unpublished{PaulEMcKenney2004rcu:assign:pointer 11844c62abc9SPaul E. McKenney,Author="Paul E. McKenney" 11854c62abc9SPaul E. McKenney,Title="{[PATCH 1/3] RCU: \url{rcu_assign_pointer()} removal of memory barriers}" 11864c62abc9SPaul E. McKenney,month="October" 11874c62abc9SPaul E. McKenney,year="2004" 11884c62abc9SPaul E. McKenney,note="Available: 11894c62abc9SPaul E. McKenney\url{http://lkml.org/lkml/2004/10/23/241} 11904c62abc9SPaul E. McKenney[Viewed June 8, 2010]" 11916ae37718SPaul E. McKenney,annotation={ 11924c62abc9SPaul E. McKenney Introduce rcu_assign_pointer(). 11936ae37718SPaul E. McKenney} 11944c62abc9SPaul E. McKenney} 11954c62abc9SPaul E. McKenney 11964c62abc9SPaul E. McKenney@unpublished{JamesMorris04a 11974c62abc9SPaul E. McKenney,Author="James Morris" 11984c62abc9SPaul E. McKenney,Title="{[PATCH 2/3] SELinux} scalability - convert {AVC} to {RCU}" 11994c62abc9SPaul E. McKenney,day="15" 12004c62abc9SPaul E. McKenney,month="November" 12014c62abc9SPaul E. McKenney,year="2004" 12026ae37718SPaul E. McKenney,note="\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=110054979416004&w=2}" 12036ae37718SPaul E. McKenney,annotation={ 12044c62abc9SPaul E. McKenney James Morris posts Kaigai Kohei's patch to LKML. 12056ae37718SPaul E. McKenney [Viewed December 10, 2004] 12066ae37718SPaul E. McKenney Kaigai's patch is at https://lkml.org/lkml/2004/9/27/52 12076ae37718SPaul E. McKenney} 12081da177e4SLinus Torvalds} 1209a83f1fe2SPaul E. McKenney 1210a83f1fe2SPaul E. McKenney@unpublished{JamesMorris04b 1211a83f1fe2SPaul E. McKenney,Author="James Morris" 1212a83f1fe2SPaul E. McKenney,Title="Recent Developments in {SELinux} Kernel Performance" 1213a83f1fe2SPaul E. McKenney,month="December" 1214a83f1fe2SPaul E. McKenney,year="2004" 1215a83f1fe2SPaul E. McKenney,note="Available: 1216a83f1fe2SPaul E. McKenney\url{http://www.livejournal.com/users/james_morris/2153.html} 1217a83f1fe2SPaul E. McKenney[Viewed December 10, 2004]" 12186ae37718SPaul E. McKenney,annotation={ 12194c62abc9SPaul E. McKenney RCU helps SELinux performance. ;-) Made LWN. 12206ae37718SPaul E. McKenney} 12214c62abc9SPaul E. McKenney} 12224c62abc9SPaul E. McKenney 12234c62abc9SPaul E. McKenney@unpublished{PaulMcKenney2005RCUSemantics 12244c62abc9SPaul E. McKenney,Author="Paul E. McKenney and Jonathan Walpole" 12254c62abc9SPaul E. McKenney,Title="{RCU} Semantics: A First Attempt" 12264c62abc9SPaul E. McKenney,month="January" 12274c62abc9SPaul E. McKenney,year="2005" 12284c62abc9SPaul E. McKenney,day="30" 12294c62abc9SPaul E. McKenney,note="Available: 12304c62abc9SPaul E. McKenney\url{http://www.rdrop.com/users/paulmck/RCU/rcu-semantics.2005.01.30a.pdf} 12314c62abc9SPaul E. McKenney[Viewed December 6, 2009]" 12326ae37718SPaul E. McKenney,annotation={ 12334c62abc9SPaul E. McKenney Early derivation of RCU semantics. 12346ae37718SPaul E. McKenney} 12354c62abc9SPaul E. McKenney} 12364c62abc9SPaul E. McKenney 12374c62abc9SPaul E. McKenney@unpublished{PaulMcKenney2005e 12384c62abc9SPaul E. McKenney,Author="Paul E. McKenney" 12394c62abc9SPaul E. McKenney,Title="Real-Time Preemption and {RCU}" 12404c62abc9SPaul E. McKenney,month="March" 12414c62abc9SPaul E. McKenney,year="2005" 12424c62abc9SPaul E. McKenney,day="17" 12434c62abc9SPaul E. McKenney,note="Available: 12444c62abc9SPaul E. McKenney\url{http://lkml.org/lkml/2005/3/17/199} 12454c62abc9SPaul E. McKenney[Viewed September 5, 2005]" 12466ae37718SPaul E. McKenney,annotation={ 12474c62abc9SPaul E. McKenney First posting showing how RCU can be safely adapted for 12484c62abc9SPaul E. McKenney preemptable RCU read side critical sections. 12496ae37718SPaul E. McKenney} 12504c62abc9SPaul E. McKenney} 12514c62abc9SPaul E. McKenney 12524c62abc9SPaul E. McKenney@unpublished{EsbenNeilsen2005a 12534c62abc9SPaul E. McKenney,Author="Esben Neilsen" 12544c62abc9SPaul E. McKenney,Title="Re: Real-Time Preemption and {RCU}" 12554c62abc9SPaul E. McKenney,month="March" 12564c62abc9SPaul E. McKenney,year="2005" 12574c62abc9SPaul E. McKenney,day="18" 12584c62abc9SPaul E. McKenney,note="Available: 12594c62abc9SPaul E. McKenney\url{http://lkml.org/lkml/2005/3/18/122} 12604c62abc9SPaul E. McKenney[Viewed March 30, 2006]" 12616ae37718SPaul E. McKenney,annotation={ 12624c62abc9SPaul E. McKenney Esben Neilsen suggests read-side suppression of grace-period 12634c62abc9SPaul E. McKenney processing for crude-but-workable realtime RCU. The downside 12644c62abc9SPaul E. McKenney is indefinite grace periods... But this is OK for experimentation 12654c62abc9SPaul E. McKenney and testing. 12666ae37718SPaul E. McKenney} 12674c62abc9SPaul E. McKenney} 12684c62abc9SPaul E. McKenney 12694c62abc9SPaul E. McKenney@unpublished{TomHart05a 12704c62abc9SPaul E. McKenney,Author="Thomas E. Hart and Paul E. McKenney and Angela Demke Brown" 12714c62abc9SPaul E. McKenney,Title="Efficient Memory Reclamation is Necessary for Fast Lock-Free 12724c62abc9SPaul E. McKenneyData Structures" 12734c62abc9SPaul E. McKenney,month="March" 12744c62abc9SPaul E. McKenney,year="2005" 12754c62abc9SPaul E. McKenney,note="Available: 12764c62abc9SPaul E. McKenney\url{ftp://ftp.cs.toronto.edu/csrg-technical-reports/515/} 12774c62abc9SPaul E. McKenney[Viewed March 4, 2005]" 12786ae37718SPaul E. McKenney,annotation={ 12794c62abc9SPaul E. McKenney Comparison of RCU, QBSR, and EBSR. RCU wins for read-mostly 12804c62abc9SPaul E. McKenney workloads. ;-) 12816ae37718SPaul E. McKenney} 12824c62abc9SPaul E. McKenney} 12834c62abc9SPaul E. McKenney 12844c62abc9SPaul E. McKenney@unpublished{JonCorbet2005DeprecateSyncKernel 12854c62abc9SPaul E. McKenney,Author="Jonathan Corbet" 12864c62abc9SPaul E. McKenney,Title="API change: synchronize_kernel() deprecated" 12874c62abc9SPaul E. McKenney,month="May" 12884c62abc9SPaul E. McKenney,day="3" 12894c62abc9SPaul E. McKenney,year="2005" 12904c62abc9SPaul E. McKenney,note="Available: 12914c62abc9SPaul E. McKenney\url{http://lwn.net/Articles/134484/} 12924c62abc9SPaul E. McKenney[Viewed May 3, 2005]" 12936ae37718SPaul E. McKenney,annotation={ 12944c62abc9SPaul E. McKenney Jon Corbet describes deprecation of synchronize_kernel() 12954c62abc9SPaul E. McKenney in favor of synchronize_rcu() and synchronize_sched(). 12966ae37718SPaul E. McKenney} 1297a83f1fe2SPaul E. McKenney} 1298dd81eca8SPaul E. McKenney 1299dd81eca8SPaul E. McKenney@unpublished{PaulMcKenney05a 1300dd81eca8SPaul E. McKenney,Author="Paul E. McKenney" 1301dd81eca8SPaul E. McKenney,Title="{[RFC]} {RCU} and {CONFIG\_PREEMPT\_RT} progress" 1302dd81eca8SPaul E. McKenney,month="May" 1303dd81eca8SPaul E. McKenney,year="2005" 1304dd81eca8SPaul E. McKenney,note="Available: 1305dd81eca8SPaul E. McKenney\url{http://lkml.org/lkml/2005/5/9/185} 1306dd81eca8SPaul E. McKenney[Viewed May 13, 2005]" 13076ae37718SPaul E. McKenney,annotation={ 1308dd81eca8SPaul E. McKenney First publication of working lock-based deferred free patches 1309dd81eca8SPaul E. McKenney for the CONFIG_PREEMPT_RT environment. 13106ae37718SPaul E. McKenney} 1311dd81eca8SPaul E. McKenney} 1312dd81eca8SPaul E. McKenney 1313dd81eca8SPaul E. McKenney@conference{PaulMcKenney05b 1314dd81eca8SPaul E. McKenney,Author="Paul E. McKenney and Dipankar Sarma" 13154c62abc9SPaul E. McKenney,Title="Towards Hard Realtime Response from the {Linux} Kernel on {SMP} Hardware" 1316dd81eca8SPaul E. McKenney,Booktitle="linux.conf.au 2005" 1317dd81eca8SPaul E. McKenney,month="April" 1318dd81eca8SPaul E. McKenney,year="2005" 1319dd81eca8SPaul E. McKenney,address="Canberra, Australia" 1320dd81eca8SPaul E. McKenney,note="Available: 1321dd81eca8SPaul E. McKenney\url{http://www.rdrop.com/users/paulmck/RCU/realtimeRCU.2005.04.23a.pdf} 1322dd81eca8SPaul E. McKenney[Viewed May 13, 2005]" 13236ae37718SPaul E. McKenney,annotation={ 1324dd81eca8SPaul E. McKenney Realtime turns into making RCU yet more realtime friendly. 13254c62abc9SPaul E. McKenney http://lca2005.linux.org.au/Papers/Paul%20McKenney/Towards%20Hard%20Realtime%20Response%20from%20the%20Linux%20Kernel/LKS.2005.04.22a.pdf 13266ae37718SPaul E. McKenney} 13274c62abc9SPaul E. McKenney} 13284c62abc9SPaul E. McKenney 13294c62abc9SPaul E. McKenney@unpublished{PaulEMcKenneyHomePage 13304c62abc9SPaul E. McKenney,Author="Paul E. McKenney" 13314c62abc9SPaul E. McKenney,Title="{Paul} {E.} {McKenney}" 13324c62abc9SPaul E. McKenney,month="May" 13334c62abc9SPaul E. McKenney,year="2005" 13344c62abc9SPaul E. McKenney,note="Available: 13354c62abc9SPaul E. McKenney\url{http://www.rdrop.com/users/paulmck/} 13364c62abc9SPaul E. McKenney[Viewed May 25, 2005]" 13376ae37718SPaul E. McKenney,annotation={ 13384c62abc9SPaul E. McKenney Paul McKenney's home page. 13396ae37718SPaul E. McKenney} 13404c62abc9SPaul E. McKenney} 13414c62abc9SPaul E. McKenney 13424c62abc9SPaul E. McKenney@unpublished{PaulEMcKenneyRCUPage 13434c62abc9SPaul E. McKenney,Author="Paul E. McKenney" 13444c62abc9SPaul E. McKenney,Title="Read-Copy Update {(RCU)}" 13454c62abc9SPaul E. McKenney,month="May" 13464c62abc9SPaul E. McKenney,year="2005" 13474c62abc9SPaul E. McKenney,note="Available: 13484c62abc9SPaul E. McKenney\url{http://www.rdrop.com/users/paulmck/RCU} 13494c62abc9SPaul E. McKenney[Viewed May 25, 2005]" 13506ae37718SPaul E. McKenney,annotation={ 13514c62abc9SPaul E. McKenney Paul McKenney's RCU page. 13526ae37718SPaul E. McKenney} 13534c62abc9SPaul E. McKenney} 13544c62abc9SPaul E. McKenney 13554c62abc9SPaul E. McKenney@unpublished{JosephSeigh2005a 13564c62abc9SPaul E. McKenney,Author="Joseph Seigh" 13574c62abc9SPaul E. McKenney,Title="{RCU}+{SMR} (hazard pointers)" 13584c62abc9SPaul E. McKenney,month="July" 13594c62abc9SPaul E. McKenney,year="2005" 13604c62abc9SPaul E. McKenney,note="Personal communication" 13616ae37718SPaul E. McKenney,annotation={ 13624c62abc9SPaul E. McKenney Joe Seigh announcing his atomic-ptr-plus project. 13634c62abc9SPaul E. McKenney http://sourceforge.net/projects/atomic-ptr-plus/ 13646ae37718SPaul E. McKenney} 13654c62abc9SPaul E. McKenney} 13664c62abc9SPaul E. McKenney 13674c62abc9SPaul E. McKenney@unpublished{JosephSeigh2005b 13684c62abc9SPaul E. McKenney,Author="Joseph Seigh" 13694c62abc9SPaul E. McKenney,Title="Lock-free synchronization primitives" 13704c62abc9SPaul E. McKenney,month="July" 13714c62abc9SPaul E. McKenney,day="6" 13724c62abc9SPaul E. McKenney,year="2005" 13734c62abc9SPaul E. McKenney,note="Available: 13744c62abc9SPaul E. McKenney\url{http://sourceforge.net/projects/atomic-ptr-plus/} 13754c62abc9SPaul E. McKenney[Viewed August 8, 2005]" 13766ae37718SPaul E. McKenney,annotation={ 13774c62abc9SPaul E. McKenney Joe Seigh's atomic-ptr-plus project. 13786ae37718SPaul E. McKenney} 13794c62abc9SPaul E. McKenney} 13804c62abc9SPaul E. McKenney 13814c62abc9SPaul E. McKenney@unpublished{PaulMcKenney2005c 13824c62abc9SPaul E. McKenney,Author="Paul E.McKenney" 13834c62abc9SPaul E. McKenney,Title="{[RFC,PATCH] RCU} and {CONFIG\_PREEMPT\_RT} sane patch" 13844c62abc9SPaul E. McKenney,month="August" 13854c62abc9SPaul E. McKenney,day="1" 13864c62abc9SPaul E. McKenney,year="2005" 13874c62abc9SPaul E. McKenney,note="Available: 13884c62abc9SPaul E. McKenney\url{http://lkml.org/lkml/2005/8/1/155} 13894c62abc9SPaul E. McKenney[Viewed March 14, 2006]" 13906ae37718SPaul E. McKenney,annotation={ 13914c62abc9SPaul E. McKenney First operating counter-based realtime RCU patch posted to LKML. 13926ae37718SPaul E. McKenney} 13934c62abc9SPaul E. McKenney} 13944c62abc9SPaul E. McKenney 13954c62abc9SPaul E. McKenney@unpublished{PaulMcKenney2005d 13964c62abc9SPaul E. McKenney,Author="Paul E. McKenney" 13974c62abc9SPaul E. McKenney,Title="Re: [Fwd: Re: [patch] Real-Time Preemption, -RT-2.6.13-rc4-V0.7.52-01]" 13984c62abc9SPaul E. McKenney,month="August" 13994c62abc9SPaul E. McKenney,day="8" 14004c62abc9SPaul E. McKenney,year="2005" 14014c62abc9SPaul E. McKenney,note="Available: 14024c62abc9SPaul E. McKenney\url{http://lkml.org/lkml/2005/8/8/108} 14034c62abc9SPaul E. McKenney[Viewed March 14, 2006]" 14046ae37718SPaul E. McKenney,annotation={ 14054c62abc9SPaul E. McKenney First operating counter-based realtime RCU patch posted to LKML, 14064c62abc9SPaul E. McKenney but fixed so that various unusual combinations of configuration 14074c62abc9SPaul E. McKenney parameters all function properly. 14086ae37718SPaul E. McKenney} 14094c62abc9SPaul E. McKenney} 14104c62abc9SPaul E. McKenney 14114c62abc9SPaul E. McKenney@unpublished{PaulMcKenney2005rcutorture 14124c62abc9SPaul E. McKenney,Author="Paul E. McKenney" 14134c62abc9SPaul E. McKenney,Title="{[PATCH]} {RCU} torture testing" 14144c62abc9SPaul E. McKenney,month="October" 14154c62abc9SPaul E. McKenney,day="1" 14164c62abc9SPaul E. McKenney,year="2005" 14174c62abc9SPaul E. McKenney,note="Available: 14184c62abc9SPaul E. McKenney\url{http://lkml.org/lkml/2005/10/1/70} 14194c62abc9SPaul E. McKenney[Viewed March 14, 2006]" 14206ae37718SPaul E. McKenney,annotation={ 14214c62abc9SPaul E. McKenney First rcutorture patch. 14226ae37718SPaul E. McKenney} 14236ae37718SPaul E. McKenney} 14246ae37718SPaul E. McKenney 14256ae37718SPaul E. McKenney@unpublished{DavidSMiller2006HashedLocking 14266ae37718SPaul E. McKenney,Author="David S. Miller" 14276ae37718SPaul E. McKenney,Title="Re: [{PATCH}, {RFC}] {RCU} : {OOM} avoidance and lower latency" 14286ae37718SPaul E. McKenney,month="January" 14296ae37718SPaul E. McKenney,day="6" 14306ae37718SPaul E. McKenney,year="2006" 14316ae37718SPaul E. McKenney,note="Available: 14326ae37718SPaul E. McKenney\url{https://lkml.org/lkml/2006/1/7/22} 14336ae37718SPaul E. McKenney[Viewed February 29, 2012]" 14346ae37718SPaul E. McKenney,annotation={ 14356ae37718SPaul E. McKenney David Miller's view on hashed arrays of locks: used to really 14366ae37718SPaul E. McKenney like it, but time he saw an opportunity for this technique, 14376ae37718SPaul E. McKenney something else always proved superior. Partitioning or RCU. ;-) 14386ae37718SPaul E. McKenney} 1439dd81eca8SPaul E. McKenney} 1440f85d6c71SPaul E. McKenney 1441f85d6c71SPaul E. McKenney@conference{ThomasEHart2006a 1442f85d6c71SPaul E. McKenney,Author="Thomas E. Hart and Paul E. McKenney and Angela Demke Brown" 1443f85d6c71SPaul E. McKenney,Title="Making Lockless Synchronization Fast: Performance Implications 1444f85d6c71SPaul E. McKenneyof Memory Reclamation" 1445f85d6c71SPaul E. McKenney,Booktitle="20\textsuperscript{th} {IEEE} International Parallel and 1446f85d6c71SPaul E. McKenneyDistributed Processing Symposium" 1447f85d6c71SPaul E. McKenney,month="April" 1448f85d6c71SPaul E. McKenney,year="2006" 1449f85d6c71SPaul E. McKenney,day="25-29" 1450f85d6c71SPaul E. McKenney,address="Rhodes, Greece" 14514c62abc9SPaul E. McKenney,note="Available: 14524c62abc9SPaul E. McKenney\url{http://www.rdrop.com/users/paulmck/RCU/hart_ipdps06.pdf} 14534c62abc9SPaul E. McKenney[Viewed April 28, 2008]" 14546ae37718SPaul E. McKenney,annotation={ 14554c62abc9SPaul E. McKenney Compares QSBR, HPBR, EBR, and lock-free reference counting. 14564c62abc9SPaul E. McKenney http://www.cs.toronto.edu/~tomhart/perflab/ipdps06.tgz 14576ae37718SPaul E. McKenney} 14584c62abc9SPaul E. McKenney} 14594c62abc9SPaul E. McKenney 14604c62abc9SPaul E. McKenney@unpublished{NickPiggin2006radixtree 14614c62abc9SPaul E. McKenney,Author="Nick Piggin" 14624c62abc9SPaul E. McKenney,Title="[patch 3/3] radix-tree: {RCU} lockless readside" 14634c62abc9SPaul E. McKenney,month="June" 14644c62abc9SPaul E. McKenney,day="20" 14654c62abc9SPaul E. McKenney,year="2006" 14664c62abc9SPaul E. McKenney,note="Available: 14674c62abc9SPaul E. McKenney\url{http://lkml.org/lkml/2006/6/20/238} 14684c62abc9SPaul E. McKenney[Viewed March 25, 2008]" 14696ae37718SPaul E. McKenney,annotation={ 14704c62abc9SPaul E. McKenney RCU-protected radix tree. 14716ae37718SPaul E. McKenney} 1472f85d6c71SPaul E. McKenney} 1473f85d6c71SPaul E. McKenney 1474f85d6c71SPaul E. McKenney@Conference{PaulEMcKenney2006b 1475f85d6c71SPaul E. McKenney,Author="Paul E. McKenney and Dipankar Sarma and Ingo Molnar and 1476f85d6c71SPaul E. McKenneySuparna Bhattacharya" 14774c62abc9SPaul E. McKenney,Title="Extending {RCU} for Realtime and Embedded Workloads" 1478f85d6c71SPaul E. McKenney,Booktitle="{Ottawa Linux Symposium}" 1479f85d6c71SPaul E. McKenney,Month="July" 1480f85d6c71SPaul E. McKenney,Year="2006" 1481f85d6c71SPaul E. McKenney,pages="v2 123-138" 1482f85d6c71SPaul E. McKenney,note="Available: 14834c62abc9SPaul E. McKenney\url{http://www.linuxsymposium.org/2006/view_abstract.php?content_key=184} 1484f85d6c71SPaul E. McKenney\url{http://www.rdrop.com/users/paulmck/RCU/OLSrtRCU.2006.08.11a.pdf} 1485f85d6c71SPaul E. McKenney[Viewed January 1, 2007]" 14866ae37718SPaul E. McKenney,annotation={ 1487f85d6c71SPaul E. McKenney Described how to improve the -rt implementation of realtime RCU. 14886ae37718SPaul E. McKenney} 1489f85d6c71SPaul E. McKenney} 1490f85d6c71SPaul E. McKenney 14914c62abc9SPaul E. McKenney@unpublished{WikipediaRCU 14924c62abc9SPaul E. McKenney,Author="Paul E. McKenney and Chris Purcell and Algae and Ben Schumin and 14934c62abc9SPaul E. McKenneyGaius Cornelius and Qwertyus and Neil Conway and Sbw and Blainster and 14944c62abc9SPaul E. McKenneyCanis Rufus and Zoicon5 and Anome and Hal Eisen" 14954c62abc9SPaul E. McKenney,Title="Read-Copy Update" 14964c62abc9SPaul E. McKenney,month="July" 14974c62abc9SPaul E. McKenney,day="8" 14984c62abc9SPaul E. McKenney,year="2006" 14996ae37718SPaul E. McKenney,note="\url{http://en.wikipedia.org/wiki/Read-copy-update}" 15006ae37718SPaul E. McKenney,annotation={ 15014c62abc9SPaul E. McKenney Wikipedia RCU page as of July 8 2006. 15026ae37718SPaul E. McKenney [Viewed August 21, 2006] 15036ae37718SPaul E. McKenney} 15044c62abc9SPaul E. McKenney} 15054c62abc9SPaul E. McKenney 15064c62abc9SPaul E. McKenney@Conference{NickPiggin2006LocklessPageCache 15074c62abc9SPaul E. McKenney,Author="Nick Piggin" 15084c62abc9SPaul E. McKenney,Title="A Lockless Pagecache in Linux---Introduction, Progress, Performance" 15094c62abc9SPaul E. McKenney,Booktitle="{Ottawa Linux Symposium}" 15104c62abc9SPaul E. McKenney,Month="July" 15114c62abc9SPaul E. McKenney,Year="2006" 15124c62abc9SPaul E. McKenney,pages="v2 249-254" 15134c62abc9SPaul E. McKenney,note="Available: 15144c62abc9SPaul E. McKenney\url{http://www.linuxsymposium.org/2006/view_abstract.php?content_key=184} 15154c62abc9SPaul E. McKenney[Viewed January 11, 2009]" 15166ae37718SPaul E. McKenney,annotation={ 15174c62abc9SPaul E. McKenney Uses RCU-protected radix tree for a lockless page cache. 15186ae37718SPaul E. McKenney} 15194c62abc9SPaul E. McKenney} 15204c62abc9SPaul E. McKenney 1521f85d6c71SPaul E. McKenney@unpublished{PaulEMcKenney2006c 1522f85d6c71SPaul E. McKenney,Author="Paul E. McKenney" 1523f85d6c71SPaul E. McKenney,Title="Sleepable {RCU}" 1524f85d6c71SPaul E. McKenney,month="October" 1525f85d6c71SPaul E. McKenney,day="9" 1526f85d6c71SPaul E. McKenney,year="2006" 1527f85d6c71SPaul E. McKenney,note="Available: 1528f85d6c71SPaul E. McKenney\url{http://lwn.net/Articles/202847/} 1529f85d6c71SPaul E. McKenneyRevised: 1530f85d6c71SPaul E. McKenney\url{http://www.rdrop.com/users/paulmck/RCU/srcu.2007.01.14a.pdf} 1531f85d6c71SPaul E. McKenney[Viewed August 21, 2006]" 15326ae37718SPaul E. McKenney,annotation={ 1533f85d6c71SPaul E. McKenney LWN article introducing SRCU. 15346ae37718SPaul E. McKenney} 1535f85d6c71SPaul E. McKenney} 1536f85d6c71SPaul E. McKenney 1537f85d6c71SPaul E. McKenney@unpublished{RobertOlsson2006a 1538f85d6c71SPaul E. McKenney,Author="Robert Olsson and Stefan Nilsson" 1539f85d6c71SPaul E. McKenney,Title="{TRASH}: A dynamic {LC}-trie and hash data structure" 1540f85d6c71SPaul E. McKenney,month="August" 1541f85d6c71SPaul E. McKenney,day="18" 1542f85d6c71SPaul E. McKenney,year="2006" 15436ae37718SPaul E. McKenney,note="\url{http://www.nada.kth.se/~snilsson/publications/TRASH/trash.pdf}" 15446ae37718SPaul E. McKenney,annotation={ 1545f85d6c71SPaul E. McKenney RCU-protected dynamic trie-hash combination. 15466ae37718SPaul E. McKenney [Viewed March 4, 2011] 15476ae37718SPaul E. McKenney} 1548f85d6c71SPaul E. McKenney} 1549f85d6c71SPaul E. McKenney 15504c62abc9SPaul E. McKenney@unpublished{ChristophHellwig2006RCU2SRCU 15514c62abc9SPaul E. McKenney,Author="Christoph Hellwig" 15524c62abc9SPaul E. McKenney,Title="Re: {[-mm PATCH 1/4]} {RCU}: split classic rcu" 15534c62abc9SPaul E. McKenney,month="September" 15544c62abc9SPaul E. McKenney,day="28" 15554c62abc9SPaul E. McKenney,year="2006" 15564c62abc9SPaul E. McKenney,note="Available: 15574c62abc9SPaul E. McKenney\url{http://lkml.org/lkml/2006/9/28/160} 15584c62abc9SPaul E. McKenney[Viewed March 27, 2008]" 15594c62abc9SPaul E. McKenney} 15604c62abc9SPaul E. McKenney 15614c62abc9SPaul E. McKenney@unpublished{PaulEMcKenneyRCUusagePage 15624c62abc9SPaul E. McKenney,Author="Paul E. McKenney" 15634c62abc9SPaul E. McKenney,Title="{RCU} {Linux} Usage" 15644c62abc9SPaul E. McKenney,month="October" 15654c62abc9SPaul E. McKenney,year="2006" 15664c62abc9SPaul E. McKenney,note="Available: 15674c62abc9SPaul E. McKenney\url{http://www.rdrop.com/users/paulmck/RCU/linuxusage.html} 15684c62abc9SPaul E. McKenney[Viewed January 14, 2007]" 15696ae37718SPaul E. McKenney,annotation={ 15704c62abc9SPaul E. McKenney Paul McKenney's RCU page showing graphs plotting Linux-kernel 15714c62abc9SPaul E. McKenney usage of RCU. 15726ae37718SPaul E. McKenney} 15734c62abc9SPaul E. McKenney} 15744c62abc9SPaul E. McKenney 15754c62abc9SPaul E. McKenney@unpublished{PaulEMcKenneyRCUusageRawDataPage 15764c62abc9SPaul E. McKenney,Author="Paul E. McKenney" 15774c62abc9SPaul E. McKenney,Title="Read-Copy Update {(RCU)} Usage in {Linux} Kernel" 15784c62abc9SPaul E. McKenney,month="October" 15794c62abc9SPaul E. McKenney,year="2006" 15804c62abc9SPaul E. McKenney,note="Available: 15814c62abc9SPaul E. McKenney\url{http://www.rdrop.com/users/paulmck/RCU/linuxusage/rculocktab.html} 15824c62abc9SPaul E. McKenney[Viewed January 14, 2007]" 15836ae37718SPaul E. McKenney,annotation={ 15844c62abc9SPaul E. McKenney Paul McKenney's RCU page showing Linux usage of RCU in tabular 15854c62abc9SPaul E. McKenney form, with links to corresponding cscope databases. 15866ae37718SPaul E. McKenney} 15874c62abc9SPaul E. McKenney} 15884c62abc9SPaul E. McKenney 15894c62abc9SPaul E. McKenney@unpublished{GauthamShenoy2006RCUrwlock 15904c62abc9SPaul E. McKenney,Author="Gautham R. Shenoy" 15914c62abc9SPaul E. McKenney,Title="[PATCH 4/5] lock\_cpu\_hotplug: Redesign - Lightweight implementation of lock\_cpu\_hotplug" 15924c62abc9SPaul E. McKenney,month="October" 15934c62abc9SPaul E. McKenney,year="2006" 15944c62abc9SPaul E. McKenney,day=26 15954c62abc9SPaul E. McKenney,note="Available: 15964c62abc9SPaul E. McKenney\url{http://lkml.org/lkml/2006/10/26/73} 15974c62abc9SPaul E. McKenney[Viewed January 26, 2009]" 15986ae37718SPaul E. McKenney,annotation={ 15994c62abc9SPaul E. McKenney RCU-based reader-writer lock that allows readers to proceed with 16004c62abc9SPaul E. McKenney no memory barriers or atomic instruction in absence of writers. 16014c62abc9SPaul E. McKenney If writer do show up, readers must of course wait as required by 16024c62abc9SPaul E. McKenney the semantics of reader-writer locking. This is a recursive 16034c62abc9SPaul E. McKenney lock. 16046ae37718SPaul E. McKenney} 16054c62abc9SPaul E. McKenney} 16064c62abc9SPaul E. McKenney 16074c62abc9SPaul E. McKenney@unpublished{JensAxboe2006SlowSRCU 16084c62abc9SPaul E. McKenney,Author="Jens Axboe" 16094c62abc9SPaul E. McKenney,Title="Re: [patch] cpufreq: mark \url{cpufreq_tsc()} as 16104c62abc9SPaul E. McKenney\url{core_initcall_sync}" 16114c62abc9SPaul E. McKenney,month="November" 16124c62abc9SPaul E. McKenney,year="2006" 16134c62abc9SPaul E. McKenney,day=17 16144c62abc9SPaul E. McKenney,note="Available: 16154c62abc9SPaul E. McKenney\url{http://lkml.org/lkml/2006/11/17/56} 16164c62abc9SPaul E. McKenney[Viewed May 28, 2007]" 16176ae37718SPaul E. McKenney,annotation={ 16184c62abc9SPaul E. McKenney SRCU's grace periods are too slow for Jens, even after a 16194c62abc9SPaul E. McKenney factor-of-three speedup. 16204c62abc9SPaul E. McKenney Sped-up version of SRCU at http://lkml.org/lkml/2006/11/17/359. 16216ae37718SPaul E. McKenney} 16224c62abc9SPaul E. McKenney} 16234c62abc9SPaul E. McKenney 16244c62abc9SPaul E. McKenney@unpublished{OlegNesterov2006QRCU 16254c62abc9SPaul E. McKenney,Author="Oleg Nesterov" 16264c62abc9SPaul E. McKenney,Title="Re: [patch] cpufreq: mark {\tt cpufreq\_tsc()} as 16274c62abc9SPaul E. McKenney{\tt core\_initcall\_sync}" 16284c62abc9SPaul E. McKenney,month="November" 16294c62abc9SPaul E. McKenney,year="2006" 16304c62abc9SPaul E. McKenney,day=19 16314c62abc9SPaul E. McKenney,note="Available: 16324c62abc9SPaul E. McKenney\url{http://lkml.org/lkml/2006/11/19/69} 16334c62abc9SPaul E. McKenney[Viewed May 28, 2007]" 16346ae37718SPaul E. McKenney,annotation={ 16354c62abc9SPaul E. McKenney First cut of QRCU. Expanded/corrected versions followed. 16364c62abc9SPaul E. McKenney Used to be OlegNesterov2007QRCU, now time-corrected. 16376ae37718SPaul E. McKenney} 16384c62abc9SPaul E. McKenney} 16394c62abc9SPaul E. McKenney 16404c62abc9SPaul E. McKenney@unpublished{OlegNesterov2006aQRCU 16414c62abc9SPaul E. McKenney,Author="Oleg Nesterov" 16424c62abc9SPaul E. McKenney,Title="Re: [RFC, PATCH 1/2] qrcu: {"quick"} srcu implementation" 16434c62abc9SPaul E. McKenney,month="November" 16444c62abc9SPaul E. McKenney,year="2006" 16454c62abc9SPaul E. McKenney,day=30 16464c62abc9SPaul E. McKenney,note="Available: 16474c62abc9SPaul E. McKenney\url{http://lkml.org/lkml/2006/11/29/330} 16484c62abc9SPaul E. McKenney[Viewed November 26, 2008]" 16496ae37718SPaul E. McKenney,annotation={ 16504c62abc9SPaul E. McKenney Expanded/corrected version of QRCU. 16514c62abc9SPaul E. McKenney Used to be OlegNesterov2007aQRCU, now time-corrected. 16526ae37718SPaul E. McKenney} 16534c62abc9SPaul E. McKenney} 16544c62abc9SPaul E. McKenney 16554c62abc9SPaul E. McKenney@unpublished{EvgeniyPolyakov2006RCUslowdown 16564c62abc9SPaul E. McKenney,Author="Evgeniy Polyakov" 16574c62abc9SPaul E. McKenney,Title="Badness in postponing work" 16584c62abc9SPaul E. McKenney,month="December" 16594c62abc9SPaul E. McKenney,year="2006" 16604c62abc9SPaul E. McKenney,day=05 16614c62abc9SPaul E. McKenney,note="Available: 16624c62abc9SPaul E. McKenney\url{http://www.ioremap.net/node/41} 16634c62abc9SPaul E. McKenney[Viewed October 28, 2008]" 16646ae37718SPaul E. McKenney,annotation={ 16654c62abc9SPaul E. McKenney Using RCU as a pure delay leads to a 2.5x slowdown in skbs in 16664c62abc9SPaul E. McKenney the Linux kernel. 16676ae37718SPaul E. McKenney} 16684c62abc9SPaul E. McKenney} 16694c62abc9SPaul E. McKenney 16704c62abc9SPaul E. McKenney@inproceedings{ChrisMatthews2006ClusteredObjectsRCU 16714c62abc9SPaul E. McKenney,author = {Matthews, Chris and Coady, Yvonne and Appavoo, Jonathan} 16724c62abc9SPaul E. McKenney,title = {Portability events: a programming model for scalable system infrastructures} 16734c62abc9SPaul E. McKenney,booktitle = {PLOS '06: Proceedings of the 3rd workshop on Programming languages and operating systems} 16744c62abc9SPaul E. McKenney,year = {2006} 16754c62abc9SPaul E. McKenney,isbn = {1-59593-577-0} 16764c62abc9SPaul E. McKenney,pages = {11} 16774c62abc9SPaul E. McKenney,location = {San Jose, California} 16784c62abc9SPaul E. McKenney,doi = {http://doi.acm.org/10.1145/1215995.1216006} 16794c62abc9SPaul E. McKenney,publisher = {ACM} 16804c62abc9SPaul E. McKenney,address = {New York, NY, USA} 1681f85d6c71SPaul E. McKenney,annotation={ 16824c62abc9SPaul E. McKenney Uses K42's RCU-like functionality to manage clustered-object 16834c62abc9SPaul E. McKenney lifetimes. 16846ae37718SPaul E. McKenney} 16856ae37718SPaul E. McKenney} 16864c62abc9SPaul E. McKenney 16874c62abc9SPaul E. McKenney@article{DilmaDaSilva2006K42 16884c62abc9SPaul E. McKenney,author = {Silva, Dilma Da and Krieger, Orran and Wisniewski, Robert W. and Waterland, Amos and Tam, David and Baumann, Andrew} 16894c62abc9SPaul E. McKenney,title = {K42: an infrastructure for operating system research} 16904c62abc9SPaul E. McKenney,journal = {SIGOPS Oper. Syst. Rev.} 16914c62abc9SPaul E. McKenney,volume = {40} 16924c62abc9SPaul E. McKenney,number = {2} 16934c62abc9SPaul E. McKenney,year = {2006} 16944c62abc9SPaul E. McKenney,issn = {0163-5980} 16954c62abc9SPaul E. McKenney,pages = {34--42} 16964c62abc9SPaul E. McKenney,doi = {http://doi.acm.org/10.1145/1131322.1131333} 16974c62abc9SPaul E. McKenney,publisher = {ACM} 16984c62abc9SPaul E. McKenney,address = {New York, NY, USA} 16994c62abc9SPaul E. McKenney,annotation={ 17004c62abc9SPaul E. McKenney Describes relationship of K42 generations to RCU. 17016ae37718SPaul E. McKenney} 17026ae37718SPaul E. McKenney} 17034c62abc9SPaul E. McKenney 17044c62abc9SPaul E. McKenney# CoreyMinyard2007list_splice_rcu 17054c62abc9SPaul E. McKenney@unpublished{CoreyMinyard2007list:splice:rcu 17064c62abc9SPaul E. McKenney,Author="Corey Minyard and Paul E. McKenney" 17074c62abc9SPaul E. McKenney,Title="{[PATCH]} add an {RCU} version of list splicing" 17084c62abc9SPaul E. McKenney,month="January" 17094c62abc9SPaul E. McKenney,year="2007" 17104c62abc9SPaul E. McKenney,day=3 17114c62abc9SPaul E. McKenney,note="Available: 17124c62abc9SPaul E. McKenney\url{http://lkml.org/lkml/2007/1/3/112} 17134c62abc9SPaul E. McKenney[Viewed May 28, 2007]" 17146ae37718SPaul E. McKenney,annotation={ 17154c62abc9SPaul E. McKenney Patch for list_splice_rcu(). 17166ae37718SPaul E. McKenney} 17174c62abc9SPaul E. McKenney} 17184c62abc9SPaul E. McKenney 17194c62abc9SPaul E. McKenney@unpublished{PaulEMcKenney2007rcubarrier 17204c62abc9SPaul E. McKenney,Author="Paul E. McKenney" 17214c62abc9SPaul E. McKenney,Title="{RCU} and Unloadable Modules" 17224c62abc9SPaul E. McKenney,month="January" 17234c62abc9SPaul E. McKenney,day="14" 17244c62abc9SPaul E. McKenney,year="2007" 17254c62abc9SPaul E. McKenney,note="Available: 17264c62abc9SPaul E. McKenney\url{http://lwn.net/Articles/217484/} 17274c62abc9SPaul E. McKenney[Viewed November 22, 2007]" 17286ae37718SPaul E. McKenney,annotation={ 17294c62abc9SPaul E. McKenney LWN article introducing the rcu_barrier() primitive. 17306ae37718SPaul E. McKenney} 17314c62abc9SPaul E. McKenney} 17324c62abc9SPaul E. McKenney 17334c62abc9SPaul E. McKenney@unpublished{PeterZijlstra2007SyncBarrier 17344c62abc9SPaul E. McKenney,Author="Peter Zijlstra and Ingo Molnar" 17354c62abc9SPaul E. McKenney,Title="{[PATCH 3/7]} barrier: a scalable synchonisation barrier" 17364c62abc9SPaul E. McKenney,month="January" 17374c62abc9SPaul E. McKenney,year="2007" 17384c62abc9SPaul E. McKenney,day=28 17394c62abc9SPaul E. McKenney,note="Available: 17404c62abc9SPaul E. McKenney\url{http://lkml.org/lkml/2007/1/28/34} 17414c62abc9SPaul E. McKenney[Viewed March 27, 2008]" 17426ae37718SPaul E. McKenney,annotation={ 17434c62abc9SPaul E. McKenney RCU-like implementation for frequent updaters and rare readers(!). 17444c62abc9SPaul E. McKenney Subsumed into QRCU. Maybe... 17456ae37718SPaul E. McKenney} 17464c62abc9SPaul E. McKenney} 17474c62abc9SPaul E. McKenney 17484c62abc9SPaul E. McKenney@unpublished{PaulEMcKenney2007BoostRCU 17494c62abc9SPaul E. McKenney,Author="Paul E. McKenney" 17504c62abc9SPaul E. McKenney,Title="Priority-Boosting {RCU} Read-Side Critical Sections" 17514c62abc9SPaul E. McKenney,month="February" 17524c62abc9SPaul E. McKenney,day="5" 17534c62abc9SPaul E. McKenney,year="2007" 17546ae37718SPaul E. McKenney,note="\url{http://lwn.net/Articles/220677/}" 17556ae37718SPaul E. McKenney,annotation={ 17564c62abc9SPaul E. McKenney LWN article introducing RCU priority boosting. 17576ae37718SPaul E. McKenney Revised: 17586ae37718SPaul E. McKenney http://www.rdrop.com/users/paulmck/RCU/RCUbooststate.2007.04.16a.pdf 17596ae37718SPaul E. McKenney [Viewed September 7, 2007] 17606ae37718SPaul E. McKenney} 17614c62abc9SPaul E. McKenney} 17624c62abc9SPaul E. McKenney 17634c62abc9SPaul E. McKenney@unpublished{PaulMcKenney2007QRCUpatch 17644c62abc9SPaul E. McKenney,Author="Paul E. McKenney" 17654c62abc9SPaul E. McKenney,Title="{[PATCH]} {QRCU} with lockless fastpath" 17664c62abc9SPaul E. McKenney,month="February" 17674c62abc9SPaul E. McKenney,year="2007" 17684c62abc9SPaul E. McKenney,day=24 17694c62abc9SPaul E. McKenney,note="Available: 17704c62abc9SPaul E. McKenney\url{http://lkml.org/lkml/2007/2/25/18} 17714c62abc9SPaul E. McKenney[Viewed March 27, 2008]" 17726ae37718SPaul E. McKenney,annotation={ 17734c62abc9SPaul E. McKenney Patch for QRCU supplying lock-free fast path. 17746ae37718SPaul E. McKenney} 17754c62abc9SPaul E. McKenney} 17764c62abc9SPaul E. McKenney 17774c62abc9SPaul E. McKenney@article{JonathanAppavoo2007K42RCU 17784c62abc9SPaul E. McKenney,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} 17794c62abc9SPaul E. McKenney,title = {Experience distributing objects in an SMMP OS} 17804c62abc9SPaul E. McKenney,journal = {ACM Trans. Comput. Syst.} 17814c62abc9SPaul E. McKenney,volume = {25} 17824c62abc9SPaul E. McKenney,number = {3} 17834c62abc9SPaul E. McKenney,year = {2007} 17844c62abc9SPaul E. McKenney,issn = {0734-2071} 17854c62abc9SPaul E. McKenney,pages = {6/1--6/52} 17864c62abc9SPaul E. McKenney,doi = {http://doi.acm.org/10.1145/1275517.1275518} 17874c62abc9SPaul E. McKenney,publisher = {ACM} 17884c62abc9SPaul E. McKenney,address = {New York, NY, USA} 17894c62abc9SPaul E. McKenney,annotation={ 17904c62abc9SPaul E. McKenney Role of RCU in K42. 17916ae37718SPaul E. McKenney} 17926ae37718SPaul E. McKenney} 17934c62abc9SPaul E. McKenney 17944c62abc9SPaul E. McKenney@conference{RobertOlsson2007Trash 17954c62abc9SPaul E. McKenney,Author="Robert Olsson and Stefan Nilsson" 17964c62abc9SPaul E. McKenney,Title="{TRASH}: A dynamic {LC}-trie and hash data structure" 17974c62abc9SPaul E. McKenney,booktitle="Workshop on High Performance Switching and Routing (HPSR'07)" 17984c62abc9SPaul E. McKenney,month="May" 17994c62abc9SPaul E. McKenney,year="2007" 18004c62abc9SPaul E. McKenney,note="Available: 18014c62abc9SPaul E. McKenney\url{http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4281239} 18024c62abc9SPaul E. McKenney[Viewed October 1, 2010]" 18036ae37718SPaul E. McKenney,annotation={ 18044c62abc9SPaul E. McKenney RCU-protected dynamic trie-hash combination. 18056ae37718SPaul E. McKenney} 18064c62abc9SPaul E. McKenney} 18074c62abc9SPaul E. McKenney 18084c62abc9SPaul E. McKenney@conference{PeterZijlstra2007ConcurrentPagecacheRCU 18094c62abc9SPaul E. McKenney,Author="Peter Zijlstra" 18104c62abc9SPaul E. McKenney,Title="Concurrent Pagecache" 18114c62abc9SPaul E. McKenney,Booktitle="Linux Symposium" 18124c62abc9SPaul E. McKenney,month="June" 18134c62abc9SPaul E. McKenney,year="2007" 18144c62abc9SPaul E. McKenney,address="Ottawa, Canada" 18154c62abc9SPaul E. McKenney,note="Available: 18164c62abc9SPaul E. McKenney\url{http://ols.108.redhat.com/2007/Reprints/zijlstra-Reprint.pdf} 18174c62abc9SPaul E. McKenney[Viewed April 14, 2008]" 18186ae37718SPaul E. McKenney,annotation={ 18194c62abc9SPaul E. McKenney Page-cache modifications permitting RCU readers and concurrent 18204c62abc9SPaul E. McKenney updates. 18216ae37718SPaul E. McKenney} 18224c62abc9SPaul E. McKenney} 18234c62abc9SPaul E. McKenney 18244c62abc9SPaul E. McKenney@unpublished{PaulEMcKenney2007whatisRCU 18254c62abc9SPaul E. McKenney,Author="Paul E. McKenney" 18264c62abc9SPaul E. McKenney,Title="What is {RCU}?" 18274c62abc9SPaul E. McKenney,year="2007" 18284c62abc9SPaul E. McKenney,month="07" 18294c62abc9SPaul E. McKenney,note="Available: 18304c62abc9SPaul E. McKenney\url{http://www.rdrop.com/users/paulmck/RCU/whatisRCU.html} 18314c62abc9SPaul E. McKenney[Viewed July 6, 2007]" 18324c62abc9SPaul E. McKenney,annotation={ 18334c62abc9SPaul E. McKenney Describes RCU in Linux kernel. 1834f85d6c71SPaul E. McKenney} 1835f85d6c71SPaul E. McKenney} 1836f85d6c71SPaul E. McKenney 1837f85d6c71SPaul E. McKenney@unpublished{PaulEMcKenney2007QRCUspin 1838f85d6c71SPaul E. McKenney,Author="Paul E. McKenney" 18394c62abc9SPaul E. McKenney,Title="Using {Promela} and {Spin} to verify parallel algorithms" 1840f85d6c71SPaul E. McKenney,month="August" 1841f85d6c71SPaul E. McKenney,day="1" 1842f85d6c71SPaul E. McKenney,year="2007" 1843f85d6c71SPaul E. McKenney,note="Available: 1844f85d6c71SPaul E. McKenney\url{http://lwn.net/Articles/243851/} 1845f85d6c71SPaul E. McKenney[Viewed September 8, 2007]" 18466ae37718SPaul E. McKenney,annotation={ 1847f85d6c71SPaul E. McKenney LWN article describing Promela and spin, and also using Oleg 1848f85d6c71SPaul E. McKenney Nesterov's QRCU as an example (with Paul McKenney's fastpath). 18494c62abc9SPaul E. McKenney Merged patch at: http://lkml.org/lkml/2007/2/25/18 18506ae37718SPaul E. McKenney} 18514c62abc9SPaul E. McKenney} 18524c62abc9SPaul E. McKenney 18534c62abc9SPaul E. McKenney@unpublished{PaulEMcKenney2007WG21DDOatomics 18544c62abc9SPaul E. McKenney,Author="Paul E. McKenney and Hans-J. Boehm and Lawrence Crowl" 18554c62abc9SPaul E. McKenney,Title="C++ Data-Dependency Ordering: Atomics and Memory Model" 18564c62abc9SPaul E. McKenney,month="August" 18574c62abc9SPaul E. McKenney,day="3" 18584c62abc9SPaul E. McKenney,year="2007" 18596ae37718SPaul E. McKenney,note="Available: 18604c62abc9SPaul E. McKenney\url{http://open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2664.htm} 18614c62abc9SPaul E. McKenney[Viewed December 7, 2009]" 18626ae37718SPaul E. McKenney,annotation={ 18634c62abc9SPaul E. McKenney RCU for C++, parts 1 and 2. 18646ae37718SPaul E. McKenney} 18654c62abc9SPaul E. McKenney} 18664c62abc9SPaul E. McKenney 18674c62abc9SPaul E. McKenney@unpublished{PaulEMcKenney2007WG21DDOannotation 18684c62abc9SPaul E. McKenney,Author="Paul E. McKenney and Lawrence Crowl" 18694c62abc9SPaul E. McKenney,Title="C++ Data-Dependency Ordering: Function Annotation" 18704c62abc9SPaul E. McKenney,month="September" 18714c62abc9SPaul E. McKenney,day="18" 18724c62abc9SPaul E. McKenney,year="2008" 18736ae37718SPaul E. McKenney,note="Available: 18744c62abc9SPaul E. McKenney\url{http://open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2782.htm} 18754c62abc9SPaul E. McKenney[Viewed December 7, 2009]" 18766ae37718SPaul E. McKenney,annotation={ 18774c62abc9SPaul E. McKenney RCU for C++, part 2, updated many times. 18786ae37718SPaul E. McKenney} 18794c62abc9SPaul E. McKenney} 18804c62abc9SPaul E. McKenney 18814c62abc9SPaul E. McKenney@unpublished{PaulEMcKenney2007PreemptibleRCUPatch 18824c62abc9SPaul E. McKenney,Author="Paul E. McKenney" 18834c62abc9SPaul E. McKenney,Title="[PATCH RFC 0/9] {RCU}: Preemptible {RCU}" 18844c62abc9SPaul E. McKenney,month="September" 18854c62abc9SPaul E. McKenney,day="10" 18864c62abc9SPaul E. McKenney,year="2007" 18874c62abc9SPaul E. McKenney,note="Available: 18884c62abc9SPaul E. McKenney\url{http://lkml.org/lkml/2007/9/10/213} 18894c62abc9SPaul E. McKenney[Viewed October 25, 2007]" 18906ae37718SPaul E. McKenney,annotation={ 18914c62abc9SPaul E. McKenney Final patch for preemptable RCU to -rt. (Later patches were 18924c62abc9SPaul E. McKenney to mainline, eventually incorporated.) 18936ae37718SPaul E. McKenney} 1894f85d6c71SPaul E. McKenney} 1895f85d6c71SPaul E. McKenney 189632300751SPaul E. McKenney@unpublished{PaulEMcKenney2007PreemptibleRCU 189732300751SPaul E. McKenney,Author="Paul E. McKenney" 189832300751SPaul E. McKenney,Title="The design of preemptible read-copy-update" 189932300751SPaul E. McKenney,month="October" 190032300751SPaul E. McKenney,day="8" 190132300751SPaul E. McKenney,year="2007" 190232300751SPaul E. McKenney,note="Available: 190332300751SPaul E. McKenney\url{http://lwn.net/Articles/253651/} 190432300751SPaul E. McKenney[Viewed October 25, 2007]" 19056ae37718SPaul E. McKenney,annotation={ 190632300751SPaul E. McKenney LWN article describing the design of preemptible RCU. 19076ae37718SPaul E. McKenney} 190832300751SPaul E. McKenney} 190932300751SPaul E. McKenney 19104c62abc9SPaul E. McKenney@article{ThomasEHart2007a 19114c62abc9SPaul E. McKenney,Author="Thomas E. Hart and Paul E. McKenney and Angela Demke Brown and Jonathan Walpole" 19124c62abc9SPaul E. McKenney,Title="Performance of memory reclamation for lockless synchronization" 19134c62abc9SPaul E. McKenney,journal="J. Parallel Distrib. Comput." 19144c62abc9SPaul E. McKenney,volume={67} 19154c62abc9SPaul E. McKenney,number="12" 19164c62abc9SPaul E. McKenney,year="2007" 19174c62abc9SPaul E. McKenney,issn="0743-7315" 19184c62abc9SPaul E. McKenney,pages="1270--1285" 19194c62abc9SPaul E. McKenney,doi="http://dx.doi.org/10.1016/j.jpdc.2007.04.010" 19204c62abc9SPaul E. McKenney,publisher="Academic Press, Inc." 19214c62abc9SPaul E. McKenney,address="Orlando, FL, USA" 19224c62abc9SPaul E. McKenney,annotation={ 19234c62abc9SPaul E. McKenney Compares QSBR, HPBR, EBR, and lock-free reference counting. 19244c62abc9SPaul E. McKenney Journal version of ThomasEHart2006a. 19254c62abc9SPaul E. McKenney} 19264c62abc9SPaul E. McKenney} 19274c62abc9SPaul E. McKenney 19286ae37718SPaul E. McKenney# MathieuDesnoyers2007call_rcu_schedNeeded 19294c62abc9SPaul E. McKenney@unpublished{MathieuDesnoyers2007call:rcu:schedNeeded 19304c62abc9SPaul E. McKenney,Author="Mathieu Desnoyers" 19314c62abc9SPaul E. McKenney,Title="Re: [patch 1/2] {Linux} Kernel Markers - Support Multiple Probes" 19324c62abc9SPaul E. McKenney,month="December" 19334c62abc9SPaul E. McKenney,day="20" 19344c62abc9SPaul E. McKenney,year="2007" 19354c62abc9SPaul E. McKenney,note="Available: 19364c62abc9SPaul E. McKenney\url{http://lkml.org/lkml/2007/12/20/244} 19374c62abc9SPaul E. McKenney[Viewed March 27, 2008]" 19386ae37718SPaul E. McKenney,annotation={ 19394c62abc9SPaul E. McKenney Request for call_rcu_sched() and rcu_barrier_sched(). 19406ae37718SPaul E. McKenney} 19414c62abc9SPaul E. McKenney} 19424c62abc9SPaul E. McKenney 19434c62abc9SPaul E. McKenney 194432300751SPaul E. McKenney######################################################################## 194532300751SPaul E. McKenney# 194632300751SPaul E. McKenney# "What is RCU?" LWN series. 194732300751SPaul E. McKenney# 19484c62abc9SPaul E. McKenney# http://lwn.net/Articles/262464/ (What is RCU, Fundamentally?) 19494c62abc9SPaul E. McKenney# http://lwn.net/Articles/263130/ (What is RCU's Usage?) 19504c62abc9SPaul E. McKenney# http://lwn.net/Articles/264090/ (What is RCU's API?) 195132300751SPaul E. McKenney 195232300751SPaul E. McKenney@unpublished{PaulEMcKenney2007WhatIsRCUFundamentally 195332300751SPaul E. McKenney,Author="Paul E. McKenney and Jonathan Walpole" 195432300751SPaul E. McKenney,Title="What is {RCU}, Fundamentally?" 195532300751SPaul E. McKenney,month="December" 195632300751SPaul E. McKenney,day="17" 195732300751SPaul E. McKenney,year="2007" 195832300751SPaul E. McKenney,note="Available: 195932300751SPaul E. McKenney\url{http://lwn.net/Articles/262464/} 196032300751SPaul E. McKenney[Viewed December 27, 2007]" 19616ae37718SPaul E. McKenney,annotation={ 196232300751SPaul E. McKenney Lays out the three basic components of RCU: (1) publish-subscribe, 196332300751SPaul E. McKenney (2) wait for pre-existing readers to complete, and (2) maintain 196432300751SPaul E. McKenney multiple versions. 19656ae37718SPaul E. McKenney} 196632300751SPaul E. McKenney} 196732300751SPaul E. McKenney 196832300751SPaul E. McKenney@unpublished{PaulEMcKenney2008WhatIsRCUUsage 196932300751SPaul E. McKenney,Author="Paul E. McKenney" 197032300751SPaul E. McKenney,Title="What is {RCU}? Part 2: Usage" 197132300751SPaul E. McKenney,month="January" 197232300751SPaul E. McKenney,day="4" 197332300751SPaul E. McKenney,year="2008" 197432300751SPaul E. McKenney,note="Available: 197532300751SPaul E. McKenney\url{http://lwn.net/Articles/263130/} 197632300751SPaul E. McKenney[Viewed January 4, 2008]" 19776ae37718SPaul E. McKenney,annotation={ 197832300751SPaul E. McKenney Lays out six uses of RCU: 197932300751SPaul E. McKenney 1. RCU is a Reader-Writer Lock Replacement 198032300751SPaul E. McKenney 2. RCU is a Restricted Reference-Counting Mechanism 198132300751SPaul E. McKenney 3. RCU is a Bulk Reference-Counting Mechanism 198232300751SPaul E. McKenney 4. RCU is a Poor Man's Garbage Collector 198332300751SPaul E. McKenney 5. RCU is a Way of Providing Existence Guarantees 198432300751SPaul E. McKenney 6. RCU is a Way of Waiting for Things to Finish 19856ae37718SPaul E. McKenney} 198632300751SPaul E. McKenney} 198732300751SPaul E. McKenney 198832300751SPaul E. McKenney@unpublished{PaulEMcKenney2008WhatIsRCUAPI 198932300751SPaul E. McKenney,Author="Paul E. McKenney" 199032300751SPaul E. McKenney,Title="{RCU} part 3: the {RCU} {API}" 199132300751SPaul E. McKenney,month="January" 199232300751SPaul E. McKenney,day="17" 199332300751SPaul E. McKenney,year="2008" 199432300751SPaul E. McKenney,note="Available: 199532300751SPaul E. McKenney\url{http://lwn.net/Articles/264090/} 199632300751SPaul E. McKenney[Viewed January 10, 2008]" 19976ae37718SPaul E. McKenney,annotation={ 199832300751SPaul E. McKenney Gives an overview of the Linux-kernel RCU API and a brief annotated RCU 199932300751SPaul E. McKenney bibliography. 20006ae37718SPaul E. McKenney} 200132300751SPaul E. McKenney} 200232300751SPaul E. McKenney 20034c54005cSPaul E. McKenney# 20044c54005cSPaul E. McKenney# "What is RCU?" LWN series. 20054c54005cSPaul E. McKenney# 20064c54005cSPaul E. McKenney######################################################################## 20074c54005cSPaul E. McKenney 20084c62abc9SPaul E. McKenney 20094c62abc9SPaul E. McKenney@unpublished{SteveRostedt2008dyntickRCUpatch 20104c62abc9SPaul E. McKenney,Author="Steven Rostedt and Paul E. McKenney" 20114c62abc9SPaul E. McKenney,Title="{[PATCH]} add support for dynamic ticks and preempt rcu" 20124c62abc9SPaul E. McKenney,month="January" 20134c62abc9SPaul E. McKenney,day="29" 20144c62abc9SPaul E. McKenney,year="2008" 20154c62abc9SPaul E. McKenney,note="Available: 20164c62abc9SPaul E. McKenney\url{http://lkml.org/lkml/2008/1/29/208} 20174c62abc9SPaul E. McKenney[Viewed March 27, 2008]" 20186ae37718SPaul E. McKenney,annotation={ 20194c62abc9SPaul E. McKenney Patch that prevents preemptible RCU from unnecessarily waking 20204c62abc9SPaul E. McKenney up dynticks-idle CPUs. 20216ae37718SPaul E. McKenney} 20224c62abc9SPaul E. McKenney} 20234c62abc9SPaul E. McKenney 20244c62abc9SPaul E. McKenney@unpublished{PaulEMcKenney2008LKMLDependencyOrdering 20254c62abc9SPaul E. McKenney,Author="Paul E. McKenney" 20264c62abc9SPaul E. McKenney,Title="Re: [PATCH 02/22 -v7] Add basic support for gcc profiler instrumentation" 20274c62abc9SPaul E. McKenney,month="February" 20284c62abc9SPaul E. McKenney,day="1" 20294c62abc9SPaul E. McKenney,year="2008" 20304c62abc9SPaul E. McKenney,note="Available: 20314c62abc9SPaul E. McKenney\url{http://lkml.org/lkml/2008/2/2/255} 20324c62abc9SPaul E. McKenney[Viewed October 18, 2008]" 20336ae37718SPaul E. McKenney,annotation={ 20344c62abc9SPaul E. McKenney Explanation of compilers violating dependency ordering. 20356ae37718SPaul E. McKenney} 20364c62abc9SPaul E. McKenney} 20374c62abc9SPaul E. McKenney 20384c62abc9SPaul E. McKenney@Conference{PaulEMcKenney2008Beijing 20394c62abc9SPaul E. McKenney,Author="Paul E. McKenney" 20404c62abc9SPaul E. McKenney,Title="Introducing Technology Into {Linux} Or: 20414c62abc9SPaul E. McKenneyIntroducing your technology Into {Linux} will require introducing a 20424c62abc9SPaul E. McKenneylot of {Linux} into your technology!!!" 20434c62abc9SPaul E. McKenney,Booktitle="2008 Linux Developer Symposium - China" 20444c62abc9SPaul E. McKenney,Publisher="OSS China" 20454c62abc9SPaul E. McKenney,Month="February" 20464c62abc9SPaul E. McKenney,Year="2008" 20474c62abc9SPaul E. McKenney,Address="Beijing, China" 20484c62abc9SPaul E. McKenney,note="Available: 20494c62abc9SPaul E. McKenney\url{http://www.rdrop.com/users/paulmck/RCU/TechIntroLinux.2008.02.19a.pdf} 20504c62abc9SPaul E. McKenney[Viewed August 12, 2008]" 20514c62abc9SPaul E. McKenney} 20524c62abc9SPaul E. McKenney 20534c62abc9SPaul E. McKenney@unpublished{PaulEMcKenney2008dynticksRCU 20544c62abc9SPaul E. McKenney,Author="Paul E. McKenney and Steven Rostedt" 20554c62abc9SPaul E. McKenney,Title="Integrating and Validating dynticks and Preemptable RCU" 20564c62abc9SPaul E. McKenney,month="April" 20574c62abc9SPaul E. McKenney,day="24" 20584c62abc9SPaul E. McKenney,year="2008" 20594c62abc9SPaul E. McKenney,note="Available: 20604c62abc9SPaul E. McKenney\url{http://lwn.net/Articles/279077/} 20614c62abc9SPaul E. McKenney[Viewed April 24, 2008]" 20626ae37718SPaul E. McKenney,annotation={ 20634c62abc9SPaul E. McKenney Describes use of Promela and Spin to validate (and fix!) the 20644c62abc9SPaul E. McKenney dynticks/RCU interface. 20656ae37718SPaul E. McKenney} 20664c62abc9SPaul E. McKenney} 20674c62abc9SPaul E. McKenney 206832300751SPaul E. McKenney@article{DinakarGuniguntala2008IBMSysJ 206932300751SPaul E. McKenney,author="D. Guniguntala and P. E. McKenney and J. Triplett and J. Walpole" 207032300751SPaul E. McKenney,title="The read-copy-update mechanism for supporting real-time applications on shared-memory multiprocessor systems with {Linux}" 207132300751SPaul E. McKenney,Year="2008" 20726ae37718SPaul E. McKenney,Month="May" 207332300751SPaul E. McKenney,journal="IBM Systems Journal" 207432300751SPaul E. McKenney,volume="47" 207532300751SPaul E. McKenney,number="2" 20764c62abc9SPaul E. McKenney,pages="221-236" 20776ae37718SPaul E. McKenney,annotation={ 207832300751SPaul E. McKenney RCU, realtime RCU, sleepable RCU, performance. 20796ae37718SPaul E. McKenney http://www.research.ibm.com/journal/sj/472/guniguntala.pdf 20806ae37718SPaul E. McKenney [Viewed April 24, 2008] 20816ae37718SPaul E. McKenney} 208232300751SPaul E. McKenney} 2083240ebbf8SPaul E. McKenney 20844c62abc9SPaul E. McKenney@unpublished{LaiJiangshan2008NewClassicAlgorithm 20854c62abc9SPaul E. McKenney,Author="Lai Jiangshan" 20864c62abc9SPaul E. McKenney,Title="[{RFC}][{PATCH}] rcu classic: new algorithm for callbacks-processing" 20874c62abc9SPaul E. McKenney,month="June" 20884c62abc9SPaul E. McKenney,day="3" 20894c62abc9SPaul E. McKenney,year="2008" 20904c62abc9SPaul E. McKenney,note="Available: 20914c62abc9SPaul E. McKenney\url{http://lkml.org/lkml/2008/6/2/539} 20924c62abc9SPaul E. McKenney[Viewed December 10, 2008]" 20936ae37718SPaul E. McKenney,annotation={ 20944c62abc9SPaul E. McKenney Updated RCU classic algorithm. Introduced multi-tailed list 20954c62abc9SPaul E. McKenney for RCU callbacks and also pulling common code into 20964c62abc9SPaul E. McKenney __call_rcu(). 20976ae37718SPaul E. McKenney} 20984c62abc9SPaul E. McKenney} 20994c62abc9SPaul E. McKenney 2100240ebbf8SPaul E. McKenney@article{PaulEMcKenney2008RCUOSR 2101240ebbf8SPaul E. McKenney,author="Paul E. McKenney and Jonathan Walpole" 2102240ebbf8SPaul E. McKenney,title="Introducing technology into the {Linux} kernel: a case study" 2103240ebbf8SPaul E. McKenney,Year="2008" 2104240ebbf8SPaul E. McKenney,journal="SIGOPS Oper. Syst. Rev." 2105240ebbf8SPaul E. McKenney,volume="42" 2106240ebbf8SPaul E. McKenney,number="5" 2107240ebbf8SPaul E. McKenney,pages="4--17" 2108240ebbf8SPaul E. McKenney,issn="0163-5980" 2109240ebbf8SPaul E. McKenney,doi={http://doi.acm.org/10.1145/1400097.1400099} 2110240ebbf8SPaul E. McKenney,publisher="ACM" 2111240ebbf8SPaul E. McKenney,address="New York, NY, USA" 2112240ebbf8SPaul E. McKenney,annotation={ 2113240ebbf8SPaul E. McKenney Linux changed RCU to a far greater degree than RCU has changed Linux. 21146ae37718SPaul E. McKenney http://portal.acm.org/citation.cfm?doid=1400097.1400099 2115240ebbf8SPaul E. McKenney} 2116240ebbf8SPaul E. McKenney} 2117240ebbf8SPaul E. McKenney 21184c62abc9SPaul E. McKenney@unpublished{ManfredSpraul2008StateMachineRCU 21194c62abc9SPaul E. McKenney,Author="Manfred Spraul" 21204c62abc9SPaul E. McKenney,Title="[{RFC}, {PATCH}] state machine based rcu" 21214c62abc9SPaul E. McKenney,month="August" 21224c62abc9SPaul E. McKenney,day="21" 21234c62abc9SPaul E. McKenney,year="2008" 21244c62abc9SPaul E. McKenney,note="Available: 21254c62abc9SPaul E. McKenney\url{http://lkml.org/lkml/2008/8/21/336} 21264c62abc9SPaul E. McKenney[Viewed December 8, 2008]" 21276ae37718SPaul E. McKenney,annotation={ 21284c62abc9SPaul E. McKenney State-based RCU. One key thing that this patch does is to 21294c62abc9SPaul E. McKenney separate the dynticks handling of NMIs and IRQs. 21306ae37718SPaul E. McKenney} 21314c62abc9SPaul E. McKenney} 21324c62abc9SPaul E. McKenney 21334c62abc9SPaul E. McKenney@unpublished{ManfredSpraul2008dyntickIRQNMI 21344c62abc9SPaul E. McKenney,Author="Manfred Spraul" 21354c62abc9SPaul E. McKenney,Title="Re: [{RFC}, {PATCH}] v4 scalable classic {RCU} implementation" 21364c62abc9SPaul E. McKenney,month="September" 21374c62abc9SPaul E. McKenney,day="6" 21384c62abc9SPaul E. McKenney,year="2008" 21394c62abc9SPaul E. McKenney,note="Available: 21404c62abc9SPaul E. McKenney\url{http://lkml.org/lkml/2008/9/6/86} 21414c62abc9SPaul E. McKenney[Viewed December 8, 2008]" 21426ae37718SPaul E. McKenney,annotation={ 21434c62abc9SPaul E. McKenney Manfred notes a fix required to my attempt to separate irq 21444c62abc9SPaul E. McKenney and NMI processing for hierarchical RCU's dynticks interface. 21456ae37718SPaul E. McKenney} 21464c62abc9SPaul E. McKenney} 21474c62abc9SPaul E. McKenney 21486ae37718SPaul E. McKenney# Was PaulEMcKenney2011cyclicRCU 21494c62abc9SPaul E. McKenney@techreport{PaulEMcKenney2008cyclicRCU 21504c62abc9SPaul E. McKenney,author="Paul E. McKenney" 21514c62abc9SPaul E. McKenney,title="Efficient Support of Consistent Cyclic Search With Read-Copy Update" 21524c62abc9SPaul E. McKenney,institution="US Patent and Trademark Office" 21534c62abc9SPaul E. McKenney,address="Washington, DC" 21544c62abc9SPaul E. McKenney,year="2008" 21554c62abc9SPaul E. McKenney,number="US Patent 7,426,511" 21564c62abc9SPaul E. McKenney,month="September" 21574c62abc9SPaul E. McKenney,pages="23" 21586ae37718SPaul E. McKenney,annotation={ 21594c62abc9SPaul E. McKenney Maintains an additional level of indirection to allow 21604c62abc9SPaul E. McKenney readers to confine themselves to the desired snapshot of the 21614c62abc9SPaul E. McKenney data structure. Only permits one update at a time. 21626ae37718SPaul E. McKenney} 21634c62abc9SPaul E. McKenney} 21644c62abc9SPaul E. McKenney 2165240ebbf8SPaul E. McKenney@unpublished{PaulEMcKenney2008HierarchicalRCU 2166240ebbf8SPaul E. McKenney,Author="Paul E. McKenney" 2167240ebbf8SPaul E. McKenney,Title="Hierarchical {RCU}" 2168240ebbf8SPaul E. McKenney,month="November" 2169240ebbf8SPaul E. McKenney,day="3" 2170240ebbf8SPaul E. McKenney,year="2008" 21716ae37718SPaul E. McKenney,note="\url{http://lwn.net/Articles/305782/}" 21726ae37718SPaul E. McKenney,annotation={ 2173240ebbf8SPaul E. McKenney RCU with combining-tree-based grace-period detection, 2174240ebbf8SPaul E. McKenney permitting it to handle thousands of CPUs. 21756ae37718SPaul E. McKenney [Viewed November 6, 2008] 21766ae37718SPaul E. McKenney} 2177240ebbf8SPaul E. McKenney} 2178240ebbf8SPaul E. McKenney 21794c62abc9SPaul E. McKenney@unpublished{PaulEMcKenney2009BloatwatchRCU 21804c62abc9SPaul E. McKenney,Author="Paul E. McKenney" 21814c62abc9SPaul E. McKenney,Title="Re: [PATCH fyi] RCU: the bloatwatch edition" 21824c62abc9SPaul E. McKenney,month="January" 21834c62abc9SPaul E. McKenney,day="14" 21844c62abc9SPaul E. McKenney,year="2009" 21854c62abc9SPaul E. McKenney,note="Available: 21864c62abc9SPaul E. McKenney\url{http://lkml.org/lkml/2009/1/14/449} 21874c62abc9SPaul E. McKenney[Viewed January 15, 2009]" 21886ae37718SPaul E. McKenney,annotation={ 21894c62abc9SPaul E. McKenney Small-footprint implementation of RCU for uniprocessor 21904c62abc9SPaul E. McKenney embedded applications -- and also for exposition purposes. 21916ae37718SPaul E. McKenney} 21924c62abc9SPaul E. McKenney} 21934c62abc9SPaul E. McKenney 2194240ebbf8SPaul E. McKenney@conference{PaulEMcKenney2009MaliciousURCU 2195240ebbf8SPaul E. McKenney,Author="Paul E. McKenney" 2196240ebbf8SPaul E. McKenney,Title="Using a Malicious User-Level {RCU} to Torture {RCU}-Based Algorithms" 2197240ebbf8SPaul E. McKenney,Booktitle="linux.conf.au 2009" 2198240ebbf8SPaul E. McKenney,month="January" 2199240ebbf8SPaul E. McKenney,year="2009" 2200240ebbf8SPaul E. McKenney,address="Hobart, Australia" 2201240ebbf8SPaul E. McKenney,note="Available: 2202240ebbf8SPaul E. McKenney\url{http://www.rdrop.com/users/paulmck/RCU/urcutorture.2009.01.22a.pdf} 2203240ebbf8SPaul E. McKenney[Viewed February 2, 2009]" 22046ae37718SPaul E. McKenney,annotation={ 2205240ebbf8SPaul E. McKenney Realtime RCU and torture-testing RCU uses. 22066ae37718SPaul E. McKenney} 2207240ebbf8SPaul E. McKenney} 2208240ebbf8SPaul E. McKenney 2209240ebbf8SPaul E. McKenney@unpublished{MathieuDesnoyers2009URCU 2210240ebbf8SPaul E. McKenney,Author="Mathieu Desnoyers" 2211240ebbf8SPaul E. McKenney,Title="[{RFC} git tree] Userspace {RCU} (urcu) for {Linux}" 2212240ebbf8SPaul E. McKenney,month="February" 2213240ebbf8SPaul E. McKenney,day="5" 2214240ebbf8SPaul E. McKenney,year="2009" 22156ae37718SPaul E. McKenney,note="\url{http://lttng.org/urcu}" 22166ae37718SPaul E. McKenney,annotation={ 2217240ebbf8SPaul E. McKenney Mathieu Desnoyers's user-space RCU implementation. 2218240ebbf8SPaul E. McKenney git://lttng.org/userspace-rcu.git 22194c62abc9SPaul E. McKenney http://lttng.org/cgi-bin/gitweb.cgi?p=userspace-rcu.git 22204c62abc9SPaul E. McKenney http://lttng.org/urcu 22216ae37718SPaul E. McKenney http://lkml.org/lkml/2009/2/5/572 22226ae37718SPaul E. McKenney} 2223240ebbf8SPaul E. McKenney} 2224240ebbf8SPaul E. McKenney 22254c62abc9SPaul E. McKenney@unpublished{PaulEMcKenney2009LWNBloatWatchRCU 2226240ebbf8SPaul E. McKenney,Author="Paul E. McKenney" 2227240ebbf8SPaul E. McKenney,Title="{RCU}: The {Bloatwatch} Edition" 2228240ebbf8SPaul E. McKenney,month="March" 2229240ebbf8SPaul E. McKenney,day="17" 2230240ebbf8SPaul E. McKenney,year="2009" 2231240ebbf8SPaul E. McKenney,note="Available: 2232240ebbf8SPaul E. McKenney\url{http://lwn.net/Articles/323929/} 2233240ebbf8SPaul E. McKenney[Viewed March 20, 2009]" 22346ae37718SPaul E. McKenney,annotation={ 2235240ebbf8SPaul E. McKenney Uniprocessor assumptions allow simplified RCU implementation. 22366ae37718SPaul E. McKenney} 22376ae37718SPaul E. McKenney} 22386ae37718SPaul E. McKenney 22396ae37718SPaul E. McKenney@unpublished{EvgeniyPolyakov2009EllipticsNetwork 22406ae37718SPaul E. McKenney,Author="Evgeniy Polyakov" 22416ae37718SPaul E. McKenney,Title="The Elliptics Network" 22426ae37718SPaul E. McKenney,month="April" 22436ae37718SPaul E. McKenney,day="17" 22446ae37718SPaul E. McKenney,year="2009" 22456ae37718SPaul E. McKenney,note="Available: 22466ae37718SPaul E. McKenney\url{http://www.ioremap.net/projects/elliptics} 22476ae37718SPaul E. McKenney[Viewed April 30, 2009]" 22486ae37718SPaul E. McKenney,annotation={ 22496ae37718SPaul E. McKenney Distributed hash table with transactions, using elliptic 22506ae37718SPaul E. McKenney hash functions to distribute data. 22516ae37718SPaul E. McKenney} 2252240ebbf8SPaul E. McKenney} 22534c54005cSPaul E. McKenney 22544c54005cSPaul E. McKenney@unpublished{PaulEMcKenney2009expeditedRCU 22554c54005cSPaul E. McKenney,Author="Paul E. McKenney" 22564c54005cSPaul E. McKenney,Title="[{PATCH} -tip 0/3] expedited 'big hammer' {RCU} grace periods" 22574c54005cSPaul E. McKenney,month="June" 22584c54005cSPaul E. McKenney,day="25" 22594c54005cSPaul E. McKenney,year="2009" 22604c54005cSPaul E. McKenney,note="Available: 22614c54005cSPaul E. McKenney\url{http://lkml.org/lkml/2009/6/25/306} 22624c54005cSPaul E. McKenney[Viewed August 16, 2009]" 22636ae37718SPaul E. McKenney,annotation={ 22644c54005cSPaul E. McKenney First posting of expedited RCU to be accepted into -tip. 22656ae37718SPaul E. McKenney} 22664c54005cSPaul E. McKenney} 22674c54005cSPaul E. McKenney 22684c62abc9SPaul E. McKenney@unpublished{PaulEMcKenney2009fastRTRCU 22694c62abc9SPaul E. McKenney,Author="Paul E. McKenney" 22704c62abc9SPaul E. McKenney,Title="[{PATCH} {RFC} -tip 0/4] {RCU} cleanups and simplified preemptable {RCU}" 22714c62abc9SPaul E. McKenney,month="July" 22724c62abc9SPaul E. McKenney,day="23" 22734c62abc9SPaul E. McKenney,year="2009" 22744c62abc9SPaul E. McKenney,note="Available: 22754c62abc9SPaul E. McKenney\url{http://lkml.org/lkml/2009/7/23/294} 22764c62abc9SPaul E. McKenney[Viewed August 15, 2009]" 22776ae37718SPaul E. McKenney,annotation={ 22784c62abc9SPaul E. McKenney First posting of simple and fast preemptable RCU. 22796ae37718SPaul E. McKenney} 22804c62abc9SPaul E. McKenney} 22814c62abc9SPaul E. McKenney 22826ae37718SPaul E. McKenney@unpublished{JoshTriplett2009RPHash 22834c54005cSPaul E. McKenney,Author="Josh Triplett" 22844c54005cSPaul E. McKenney,Title="Scalable concurrent hash tables via relativistic programming" 22854c54005cSPaul E. McKenney,month="September" 22864c54005cSPaul E. McKenney,year="2009" 22876ae37718SPaul E. McKenney,note="Linux Plumbers Conference presentation" 22886ae37718SPaul E. McKenney,annotation={ 22894c54005cSPaul E. McKenney RP fun with hash tables. 22906ae37718SPaul E. McKenney Superseded by JoshTriplett2010RPHash 22916ae37718SPaul E. McKenney} 22924c54005cSPaul E. McKenney} 22934c54005cSPaul E. McKenney 22944c54005cSPaul E. McKenney@phdthesis{MathieuDesnoyersPhD 2295998f2ac3SPaul E. McKenney, title = "Low-Impact Operating System Tracing" 22964c54005cSPaul E. McKenney, author = "Mathieu Desnoyers" 22974c54005cSPaul E. McKenney, school = "Ecole Polytechnique de Montr\'{e}al" 22984c54005cSPaul E. McKenney, month = "December" 22994c54005cSPaul E. McKenney, year = 2009 2300998f2ac3SPaul E. McKenney,note="Available: 23011bd22e37SPaul E. McKenney\url{http://www.lttng.org/pub/thesis/desnoyers-dissertation-2009-12.pdf} 2302998f2ac3SPaul E. McKenney[Viewed December 9, 2009]" 23034c62abc9SPaul E. McKenney,annotation={ 23044c62abc9SPaul E. McKenney Chapter 6 (page 97) covers user-level RCU. 23054c62abc9SPaul E. McKenney} 23064c62abc9SPaul E. McKenney} 23074c62abc9SPaul E. McKenney 23084c62abc9SPaul E. McKenney@unpublished{RelativisticProgrammingWiki 23094c62abc9SPaul E. McKenney,Author="Josh Triplett and Paul E. McKenney and Jonathan Walpole" 23104c62abc9SPaul E. McKenney,Title="Relativistic Programming" 23114c62abc9SPaul E. McKenney,month="September" 23124c62abc9SPaul E. McKenney,year="2009" 23134c62abc9SPaul E. McKenney,note="Available: 23144c62abc9SPaul E. McKenney\url{http://wiki.cs.pdx.edu/rp/} 23154c62abc9SPaul E. McKenney[Viewed December 9, 2009]" 23166ae37718SPaul E. McKenney,annotation={ 23174c62abc9SPaul E. McKenney Main Relativistic Programming Wiki. 23186ae37718SPaul E. McKenney} 23194c62abc9SPaul E. McKenney} 23204c62abc9SPaul E. McKenney 23214c62abc9SPaul E. McKenney@conference{PaulEMcKenney2009DeterministicRCU 23224c62abc9SPaul E. McKenney,Author="Paul E. McKenney" 23234c62abc9SPaul E. McKenney,Title="Deterministic Synchronization in Multicore Systems: the Role of {RCU}" 23244c62abc9SPaul E. McKenney,Booktitle="Eleventh Real Time Linux Workshop" 23254c62abc9SPaul E. McKenney,month="September" 23264c62abc9SPaul E. McKenney,year="2009" 23274c62abc9SPaul E. McKenney,address="Dresden, Germany" 23284c62abc9SPaul E. McKenney,note="Available: 23294c62abc9SPaul E. McKenney\url{http://www.rdrop.com/users/paulmck/realtime/paper/DetSyncRCU.2009.08.18a.pdf} 23304c62abc9SPaul E. McKenney[Viewed January 14, 2009]" 23314c62abc9SPaul E. McKenney} 23324c62abc9SPaul E. McKenney 23334c62abc9SPaul E. McKenney@unpublished{PaulEMcKenney2009HuntingHeisenbugs 23344c62abc9SPaul E. McKenney,Author="Paul E. McKenney" 23354c62abc9SPaul E. McKenney,Title="Hunting Heisenbugs" 23364c62abc9SPaul E. McKenney,month="November" 23374c62abc9SPaul E. McKenney,year="2009" 23384c62abc9SPaul E. McKenney,day="1" 23394c62abc9SPaul E. McKenney,note="Available: 23404c62abc9SPaul E. McKenney\url{http://paulmck.livejournal.com/14639.html} 23414c62abc9SPaul E. McKenney[Viewed June 4, 2010]" 23426ae37718SPaul E. McKenney,annotation={ 23434c62abc9SPaul E. McKenney Day-one bug in Tree RCU that took forever to track down. 23446ae37718SPaul E. McKenney} 23454c62abc9SPaul E. McKenney} 23464c62abc9SPaul E. McKenney 23474c62abc9SPaul E. McKenney@unpublished{MathieuDesnoyers2009defer:rcu 23484c62abc9SPaul E. McKenney,Author="Mathieu Desnoyers" 23494c62abc9SPaul E. McKenney,Title="Kernel RCU: shrink the size of the struct rcu\_head" 23504c62abc9SPaul E. McKenney,month="December" 23514c62abc9SPaul E. McKenney,year="2009" 23524c62abc9SPaul E. McKenney,note="Available: 23534c62abc9SPaul E. McKenney\url{http://lkml.org/lkml/2009/10/18/129} 23544c62abc9SPaul E. McKenney[Viewed December 29, 2009]" 23556ae37718SPaul E. McKenney,annotation={ 23564c62abc9SPaul E. McKenney Mathieu proposed defer_rcu() with fixed-size per-thread pool 23574c62abc9SPaul E. McKenney of RCU callbacks. 23586ae37718SPaul E. McKenney} 23594c62abc9SPaul E. McKenney} 23604c62abc9SPaul E. McKenney 23614c62abc9SPaul E. McKenney@unpublished{MathieuDesnoyers2009VerifPrePub 23624c62abc9SPaul E. McKenney,Author="Mathieu Desnoyers and Paul E. McKenney and Michel R. Dagenais" 23634c62abc9SPaul E. McKenney,Title="Multi-Core Systems Modeling for Formal Verification of Parallel Algorithms" 23644c62abc9SPaul E. McKenney,month="December" 23654c62abc9SPaul E. McKenney,year="2009" 23664c62abc9SPaul E. McKenney,note="Submitted to IEEE TPDS" 23676ae37718SPaul E. McKenney,annotation={ 23684c62abc9SPaul E. McKenney OOMem model for Mathieu's user-level RCU mechanical proof of 23694c62abc9SPaul E. McKenney correctness. 23706ae37718SPaul E. McKenney} 23714c62abc9SPaul E. McKenney} 23724c62abc9SPaul E. McKenney 23734c62abc9SPaul E. McKenney@unpublished{MathieuDesnoyers2009URCUPrePub 23744c62abc9SPaul E. McKenney,Author="Mathieu Desnoyers and Paul E. McKenney and Alan Stern and Michel R. Dagenais and Jonathan Walpole" 23754c62abc9SPaul E. McKenney,Title="User-Level Implementations of Read-Copy Update" 23764c62abc9SPaul E. McKenney,month="December" 23774c62abc9SPaul E. McKenney,year="2010" 23786ae37718SPaul E. McKenney,url={\url{http://www.computer.org/csdl/trans/td/2012/02/ttd2012020375-abs.html}} 23796ae37718SPaul E. McKenney,annotation={ 23804c62abc9SPaul E. McKenney RCU overview, desiderata, semi-formal semantics, user-level RCU 23814c62abc9SPaul E. McKenney usage scenarios, three classes of RCU implementation, wait-free 23824c62abc9SPaul E. McKenney RCU updates, RCU grace-period batching, update overhead, 23834c62abc9SPaul E. McKenney http://www.rdrop.com/users/paulmck/RCU/urcu-main-accepted.2011.08.30a.pdf 23844c62abc9SPaul E. McKenney http://www.rdrop.com/users/paulmck/RCU/urcu-supp-accepted.2011.08.30a.pdf 23854c62abc9SPaul E. McKenney Superseded by MathieuDesnoyers2012URCU. 23866ae37718SPaul E. McKenney} 23874c62abc9SPaul E. McKenney} 23884c62abc9SPaul E. McKenney 23894c62abc9SPaul E. McKenney@inproceedings{HariKannan2009DynamicAnalysisRCU 23904c62abc9SPaul E. McKenney,author = {Kannan, Hari} 23914c62abc9SPaul E. McKenney,title = {Ordering decoupled metadata accesses in multiprocessors} 23924c62abc9SPaul E. McKenney,booktitle = {MICRO 42: Proceedings of the 42nd Annual IEEE/ACM International Symposium on Microarchitecture} 23934c62abc9SPaul E. McKenney,year = {2009} 23944c62abc9SPaul E. McKenney,isbn = {978-1-60558-798-1} 23954c62abc9SPaul E. McKenney,pages = {381--390} 23964c62abc9SPaul E. McKenney,location = {New York, New York} 23974c62abc9SPaul E. McKenney,doi = {http://doi.acm.org/10.1145/1669112.1669161} 23984c62abc9SPaul E. McKenney,publisher = {ACM} 23994c62abc9SPaul E. McKenney,address = {New York, NY, USA} 24004c62abc9SPaul E. McKenney,annotation={ 24014c62abc9SPaul E. McKenney Uses RCU to protect metadata used in dynamic analysis. 24026ae37718SPaul E. McKenney} 24036ae37718SPaul E. McKenney} 24044c62abc9SPaul E. McKenney 24054c62abc9SPaul E. McKenney@conference{PaulEMcKenney2010SimpleOptRCU 24064c62abc9SPaul E. McKenney,Author="Paul E. McKenney" 24074c62abc9SPaul E. McKenney,Title="Simplicity Through Optimization" 24084c62abc9SPaul E. McKenney,Booktitle="linux.conf.au 2010" 24094c62abc9SPaul E. McKenney,month="January" 24104c62abc9SPaul E. McKenney,year="2010" 24114c62abc9SPaul E. McKenney,address="Wellington, New Zealand" 24124c62abc9SPaul E. McKenney,note="Available: 24134c62abc9SPaul E. McKenney\url{http://www.rdrop.com/users/paulmck/RCU/SimplicityThruOptimization.2010.01.21f.pdf} 24144c62abc9SPaul E. McKenney[Viewed October 10, 2010]" 24156ae37718SPaul E. McKenney,annotation={ 24164c62abc9SPaul E. McKenney TREE_PREEMPT_RCU optimizations greatly simplified the old 24174c62abc9SPaul E. McKenney PREEMPT_RCU implementation. 24186ae37718SPaul E. McKenney} 24194c62abc9SPaul E. McKenney} 24204c62abc9SPaul E. McKenney 24214c62abc9SPaul E. McKenney@unpublished{PaulEMcKenney2010LockdepRCU 24224c62abc9SPaul E. McKenney,Author="Paul E. McKenney" 24234c62abc9SPaul E. McKenney,Title="Lockdep-{RCU}" 24244c62abc9SPaul E. McKenney,month="February" 24254c62abc9SPaul E. McKenney,year="2010" 24264c62abc9SPaul E. McKenney,day="1" 24276ae37718SPaul E. McKenney,note="\url{https://lwn.net/Articles/371986/}" 24286ae37718SPaul E. McKenney,annotation={ 24294c62abc9SPaul E. McKenney CONFIG_PROVE_RCU, or at least an early version. 24306ae37718SPaul E. McKenney [Viewed June 4, 2010] 24316ae37718SPaul E. McKenney} 24324c62abc9SPaul E. McKenney} 24334c62abc9SPaul E. McKenney 24344c62abc9SPaul E. McKenney@unpublished{AviKivity2010KVM2RCU 24354c62abc9SPaul E. McKenney,Author="Avi Kivity" 24364c62abc9SPaul E. McKenney,Title="[{PATCH} 37/40] {KVM}: Bump maximum vcpu count to 64" 24374c62abc9SPaul E. McKenney,month="February" 24384c62abc9SPaul E. McKenney,year="2010" 24394c62abc9SPaul E. McKenney,note="Available: 24404c62abc9SPaul E. McKenney\url{http://www.mail-archive.com/kvm@vger.kernel.org/msg28640.html} 24414c62abc9SPaul E. McKenney[Viewed March 20, 2010]" 24426ae37718SPaul E. McKenney,annotation={ 24434c62abc9SPaul E. McKenney Use of RCU permits KVM to increase the size of guest OSes from 24444c62abc9SPaul E. McKenney 16 CPUs to 64 CPUs. 24456ae37718SPaul E. McKenney} 24464c62abc9SPaul E. McKenney} 24474c62abc9SPaul E. McKenney 24484c62abc9SPaul E. McKenney@unpublished{HerbertXu2010RCUResizeHash 24494c62abc9SPaul E. McKenney,Author="Herbert Xu" 24504c62abc9SPaul E. McKenney,Title="bridge: Add core IGMP snooping support" 24514c62abc9SPaul E. McKenney,month="February" 24524c62abc9SPaul E. McKenney,year="2010" 24534c62abc9SPaul E. McKenney,note="Available: 2454*5e40ad7fSPranith Kumar\url{http://thread.gmane.org/gmane.linux.network/153338} 2455*5e40ad7fSPranith Kumar[Viewed June 9, 2014]" 24564c62abc9SPaul E. McKenney,annotation={ 24574c62abc9SPaul E. McKenney Use a pair of list_head structures to support RCU-protected 24584c62abc9SPaul E. McKenney resizable hash tables. 24596ae37718SPaul E. McKenney} 24606ae37718SPaul E. McKenney} 24616ae37718SPaul E. McKenney 24626ae37718SPaul E. McKenney@mastersthesis{AbhinavDuggal2010Masters 24636ae37718SPaul E. McKenney,author="Abhinav Duggal" 24646ae37718SPaul E. McKenney,title="Stopping Data Races Using Redflag" 24656ae37718SPaul E. McKenney,school="Stony Brook University" 24666ae37718SPaul E. McKenney,year="2010" 24676ae37718SPaul E. McKenney,annotation={ 24686ae37718SPaul E. McKenney Data-race detector incorporating RCU. 24696ae37718SPaul E. McKenney http://www.filesystems.org/docs/abhinav-thesis/abhinav_thesis.pdf 24706ae37718SPaul E. McKenney} 24716ae37718SPaul E. McKenney} 24724c62abc9SPaul E. McKenney 24734c62abc9SPaul E. McKenney@article{JoshTriplett2010RPHash 24744c62abc9SPaul E. McKenney,author="Josh Triplett and Paul E. McKenney and Jonathan Walpole" 24754c62abc9SPaul E. McKenney,title="Scalable Concurrent Hash Tables via Relativistic Programming" 24764c62abc9SPaul E. McKenney,journal="ACM Operating Systems Review" 24774c62abc9SPaul E. McKenney,year=2010 24784c62abc9SPaul E. McKenney,volume=44 24794c62abc9SPaul E. McKenney,number=3 24804c62abc9SPaul E. McKenney,month="July" 24814c62abc9SPaul E. McKenney,annotation={ 24824c62abc9SPaul E. McKenney RP fun with hash tables. 24834c62abc9SPaul E. McKenney http://portal.acm.org/citation.cfm?id=1842733.1842750 24846ae37718SPaul E. McKenney} 24856ae37718SPaul E. McKenney} 24864c62abc9SPaul E. McKenney 24874c62abc9SPaul E. McKenney@unpublished{PaulEMcKenney2010RCUAPI 24884c62abc9SPaul E. McKenney,Author="Paul E. McKenney" 24894c62abc9SPaul E. McKenney,Title="The {RCU} {API}, 2010 Edition" 24904c62abc9SPaul E. McKenney,month="December" 24914c62abc9SPaul E. McKenney,day="8" 24924c62abc9SPaul E. McKenney,year="2010" 24936ae37718SPaul E. McKenney,note="\url{http://lwn.net/Articles/418853/}" 24946ae37718SPaul E. McKenney,annotation={ 24954c62abc9SPaul E. McKenney Includes updated software-engineering features. 24966ae37718SPaul E. McKenney [Viewed December 8, 2010] 24976ae37718SPaul E. McKenney} 24984c62abc9SPaul E. McKenney} 24994c62abc9SPaul E. McKenney 25004c62abc9SPaul E. McKenney@mastersthesis{AndrejPodzimek2010masters 25014c62abc9SPaul E. McKenney,author="Andrej Podzimek" 25024c62abc9SPaul E. McKenney,title="Read-Copy-Update for OpenSolaris" 25034c62abc9SPaul E. McKenney,school="Charles University in Prague" 25044c62abc9SPaul E. McKenney,year="2010" 25054c62abc9SPaul E. McKenney,note="Available: 25064c62abc9SPaul E. McKenney\url{https://andrej.podzimek.org/thesis.pdf} 25074c62abc9SPaul E. McKenney[Viewed January 31, 2011]" 25084c62abc9SPaul E. McKenney,annotation={ 25094c62abc9SPaul E. McKenney Reviews RCU implementations and creates a few for OpenSolaris. 25104c62abc9SPaul E. McKenney Drives quiescent-state detection from RCU read-side primitives, 25114c62abc9SPaul E. McKenney in a manner roughly similar to that of Jim Houston. 25126ae37718SPaul E. McKenney} 25136ae37718SPaul E. McKenney} 25144c62abc9SPaul E. McKenney 25154c62abc9SPaul E. McKenney@unpublished{LinusTorvalds2011Linux2:6:38:rc1:NPigginVFS 25164c62abc9SPaul E. McKenney,Author="Linus Torvalds" 25174c62abc9SPaul E. McKenney,Title="Linux 2.6.38-rc1" 25184c62abc9SPaul E. McKenney,month="January" 25194c62abc9SPaul E. McKenney,year="2011" 25204c62abc9SPaul E. McKenney,note="Available: 25214c62abc9SPaul E. McKenney\url{https://lkml.org/lkml/2011/1/18/322} 25224c62abc9SPaul E. McKenney[Viewed March 4, 2011]" 25234c62abc9SPaul E. McKenney,annotation={ 25244c62abc9SPaul E. McKenney "The RCU-based name lookup is at the other end of the spectrum - the 25254c62abc9SPaul E. McKenney absolute anti-gimmick. It's some seriously good stuff, and gets rid of 25264c62abc9SPaul E. McKenney the last main global lock that really tends to hurt some kernel loads. 25274c62abc9SPaul E. McKenney The dentry lock is no longer a big serializing issue. What's really 25284c62abc9SPaul E. McKenney nice about it is that it actually improves performance a lot even for 25294c62abc9SPaul E. McKenney single-threaded loads (on an SMP kernel), because it gets rid of some 25304c62abc9SPaul E. McKenney of the most expensive parts of path component lookup, which was the 25314c62abc9SPaul E. McKenney d_lock on every component lookup. So I'm seeing improvements of 30-50% 25324c62abc9SPaul E. McKenney on some seriously pathname-lookup intensive loads." 25336ae37718SPaul E. McKenney} 25346ae37718SPaul E. McKenney} 25354c62abc9SPaul E. McKenney 25364c62abc9SPaul E. McKenney@techreport{JoshTriplett2011RPScalableCorrectOrdering 25374c62abc9SPaul E. McKenney,author = {Josh Triplett and Philip W. Howard and Paul E. McKenney and Jonathan Walpole} 25384c62abc9SPaul E. McKenney,title = {Scalable Correct Memory Ordering via Relativistic Programming} 25394c62abc9SPaul E. McKenney,year = {2011} 25404c62abc9SPaul E. McKenney,number = {11-03} 25414c62abc9SPaul E. McKenney,institution = {Portland State University} 25424c62abc9SPaul E. McKenney,note = {\url{http://www.cs.pdx.edu/pdfs/tr1103.pdf}} 25434c62abc9SPaul E. McKenney} 25444c62abc9SPaul E. McKenney 25454c62abc9SPaul E. McKenney@inproceedings{PhilHoward2011RCUTMRBTree 25464c62abc9SPaul E. McKenney,author = {Philip W. Howard and Jonathan Walpole} 25474c62abc9SPaul E. McKenney,title = {A Relativistic Enhancement to Software Transactional Memory} 25484c62abc9SPaul E. McKenney,booktitle = {Proceedings of the 3rd USENIX conference on Hot topics in parallelism} 25494c62abc9SPaul E. McKenney,series = {HotPar'11} 25504c62abc9SPaul E. McKenney,year = {2011} 25514c62abc9SPaul E. McKenney,location = {Berkeley, CA} 25524c62abc9SPaul E. McKenney,pages = {1--6} 25534c62abc9SPaul E. McKenney,numpages = {6} 25544c62abc9SPaul E. McKenney,url = {http://www.usenix.org/event/hotpar11/tech/final_files/Howard.pdf} 25554c62abc9SPaul E. McKenney,publisher = {USENIX Association} 25564c62abc9SPaul E. McKenney,address = {Berkeley, CA, USA} 25574c62abc9SPaul E. McKenney} 25584c62abc9SPaul E. McKenney 25594c62abc9SPaul E. McKenney@techreport{PaulEMcKenney2011cyclicparallelRCU 25604c62abc9SPaul E. McKenney,author="Paul E. McKenney and Jonathan Walpole" 25614c62abc9SPaul E. McKenney,title="Efficient Support of Consistent Cyclic Search With Read-Copy Update and Parallel Updates" 25624c62abc9SPaul E. McKenney,institution="US Patent and Trademark Office" 25634c62abc9SPaul E. McKenney,address="Washington, DC" 25644c62abc9SPaul E. McKenney,year="2011" 25654c62abc9SPaul E. McKenney,number="US Patent 7,953,778" 25664c62abc9SPaul E. McKenney,month="May" 25674c62abc9SPaul E. McKenney,pages="34" 25686ae37718SPaul E. McKenney,annotation={ 25694c62abc9SPaul E. McKenney Maintains an array of generation numbers to track in-flight 25704c62abc9SPaul E. McKenney updates and keeps an additional level of indirection to allow 25714c62abc9SPaul E. McKenney readers to confine themselves to the desired snapshot of the 25724c62abc9SPaul E. McKenney data structure. 25736ae37718SPaul E. McKenney} 25744c62abc9SPaul E. McKenney} 25754c62abc9SPaul E. McKenney 25764c62abc9SPaul E. McKenney@inproceedings{Triplett:2011:RPHash 25774c62abc9SPaul E. McKenney,author = {Triplett, Josh and McKenney, Paul E. and Walpole, Jonathan} 25784c62abc9SPaul E. McKenney,title = {Resizable, Scalable, Concurrent Hash Tables via Relativistic Programming} 25794c62abc9SPaul E. McKenney,booktitle = {Proceedings of the 2011 USENIX Annual Technical Conference} 25804c62abc9SPaul E. McKenney,month = {June} 25814c62abc9SPaul E. McKenney,year = {2011} 25824c62abc9SPaul E. McKenney,pages = {145--158} 25834c62abc9SPaul E. McKenney,numpages = {14} 25846ae37718SPaul E. McKenney,url={http://www.usenix.org/event/atc11/tech/final_files/Triplett.pdf} 25854c62abc9SPaul E. McKenney,publisher = {The USENIX Association} 25864c62abc9SPaul E. McKenney,address = {Portland, OR USA} 25874c62abc9SPaul E. McKenney} 25884c62abc9SPaul E. McKenney 25894c62abc9SPaul E. McKenney@unpublished{PaulEMcKenney2011RCU3.0trainwreck 25904c62abc9SPaul E. McKenney,Author="Paul E. McKenney" 25914c62abc9SPaul E. McKenney,Title="3.0 and {RCU:} what went wrong" 25924c62abc9SPaul E. McKenney,month="July" 25934c62abc9SPaul E. McKenney,day="27" 25944c62abc9SPaul E. McKenney,year="2011" 25956ae37718SPaul E. McKenney,note="\url{http://lwn.net/Articles/453002/}" 25966ae37718SPaul E. McKenney,annotation={ 25974c62abc9SPaul E. McKenney Analysis of the RCU trainwreck in Linux kernel 3.0. 25986ae37718SPaul E. McKenney [Viewed July 27, 2011] 25996ae37718SPaul E. McKenney} 26004c62abc9SPaul E. McKenney} 26014c62abc9SPaul E. McKenney 26024c62abc9SPaul E. McKenney@unpublished{NeilBrown2011MeetTheLockers 26034c62abc9SPaul E. McKenney,Author="Neil Brown" 26046ae37718SPaul E. McKenney,Title="Meet the {Lockers}" 26054c62abc9SPaul E. McKenney,month="August" 26064c62abc9SPaul E. McKenney,day="3" 26074c62abc9SPaul E. McKenney,year="2011" 26084c62abc9SPaul E. McKenney,note="Available: 26094c62abc9SPaul E. McKenney\url{http://lwn.net/Articles/453685/} 26104c62abc9SPaul E. McKenney[Viewed September 2, 2011]" 26116ae37718SPaul E. McKenney,annotation={ 26124c62abc9SPaul E. McKenney The Locker family as an analogy for locking, reference counting, 26134c62abc9SPaul E. McKenney RCU, and seqlock. 26146ae37718SPaul E. McKenney} 26156ae37718SPaul E. McKenney} 26166ae37718SPaul E. McKenney 26176ae37718SPaul E. McKenney@inproceedings{Seyster:2011:RFA:2075416.2075425 26186ae37718SPaul E. McKenney,author = {Seyster, Justin and Radhakrishnan, Prabakar and Katoch, Samriti and Duggal, Abhinav and Stoller, Scott D. and Zadok, Erez} 26196ae37718SPaul E. McKenney,title = {Redflag: a framework for analysis of Kernel-level concurrency} 26206ae37718SPaul E. McKenney,booktitle = {Proceedings of the 11th international conference on Algorithms and architectures for parallel processing - Volume Part I} 26216ae37718SPaul E. McKenney,series = {ICA3PP'11} 26226ae37718SPaul E. McKenney,year = {2011} 26236ae37718SPaul E. McKenney,isbn = {978-3-642-24649-4} 26246ae37718SPaul E. McKenney,location = {Melbourne, Australia} 26256ae37718SPaul E. McKenney,pages = {66--79} 26266ae37718SPaul E. McKenney,numpages = {14} 26276ae37718SPaul E. McKenney,url = {http://dl.acm.org/citation.cfm?id=2075416.2075425} 26286ae37718SPaul E. McKenney,acmid = {2075425} 26296ae37718SPaul E. McKenney,publisher = {Springer-Verlag} 26306ae37718SPaul E. McKenney,address = {Berlin, Heidelberg} 26316ae37718SPaul E. McKenney} 26326ae37718SPaul E. McKenney 26336ae37718SPaul E. McKenney@phdthesis{JoshTriplettPhD 26346ae37718SPaul E. McKenney,author="Josh Triplett" 26356ae37718SPaul E. McKenney,title="Relativistic Causal Ordering: A Memory Model for Scalable Concurrent Data Structures" 26366ae37718SPaul E. McKenney,school="Portland State University" 26376ae37718SPaul E. McKenney,year="2012" 26386ae37718SPaul E. McKenney,annotation={ 26396ae37718SPaul E. McKenney RCU-protected hash tables, barriers vs. read-side traversal order. 26406ae37718SPaul E. McKenney . 26416ae37718SPaul E. McKenney If the updater is making changes in the opposite direction from 26426ae37718SPaul E. McKenney the read-side traveral order, the updater need only execute a 26436ae37718SPaul E. McKenney memory-barrier instruction, but if in the same direction, the 26446ae37718SPaul E. McKenney updater needs to wait for a grace period between the individual 26456ae37718SPaul E. McKenney updates. 26466ae37718SPaul E. McKenney} 26474c62abc9SPaul E. McKenney} 26484c62abc9SPaul E. McKenney 26494c62abc9SPaul E. McKenney@article{MathieuDesnoyers2012URCU 26504c62abc9SPaul E. McKenney,Author="Mathieu Desnoyers and Paul E. McKenney and Alan Stern and Michel R. Dagenais and Jonathan Walpole" 26514c62abc9SPaul E. McKenney,Title="User-Level Implementations of Read-Copy Update" 26524c62abc9SPaul E. McKenney,journal="IEEE Transactions on Parallel and Distributed Systems" 26534c62abc9SPaul E. McKenney,volume={23} 26544c62abc9SPaul E. McKenney,year="2012" 26554c62abc9SPaul E. McKenney,issn="1045-9219" 26564c62abc9SPaul E. McKenney,pages="375-382" 26574c62abc9SPaul E. McKenney,doi="http://doi.ieeecomputersociety.org/10.1109/TPDS.2011.159" 26584c62abc9SPaul E. McKenney,publisher="IEEE Computer Society" 26594c62abc9SPaul E. McKenney,address="Los Alamitos, CA, USA" 26604c62abc9SPaul E. McKenney,annotation={ 26614c62abc9SPaul E. McKenney RCU overview, desiderata, semi-formal semantics, user-level RCU 26624c62abc9SPaul E. McKenney usage scenarios, three classes of RCU implementation, wait-free 26634c62abc9SPaul E. McKenney RCU updates, RCU grace-period batching, update overhead, 26644c62abc9SPaul E. McKenney http://www.rdrop.com/users/paulmck/RCU/urcu-main-accepted.2011.08.30a.pdf 26654c62abc9SPaul E. McKenney http://www.rdrop.com/users/paulmck/RCU/urcu-supp-accepted.2011.08.30a.pdf 26666ae37718SPaul E. McKenney http://www.computer.org/cms/Computer.org/dl/trans/td/2012/02/extras/ttd2012020375s.pdf 26676ae37718SPaul E. McKenney} 26686ae37718SPaul E. McKenney} 26696ae37718SPaul E. McKenney 26706ae37718SPaul E. McKenney@inproceedings{AustinClements2012RCULinux:mmapsem 26716ae37718SPaul E. McKenney,author = {Austin Clements and Frans Kaashoek and Nickolai Zeldovich} 26726ae37718SPaul E. McKenney,title = {Scalable Address Spaces Using {RCU} Balanced Trees} 26736ae37718SPaul E. McKenney,booktitle = {Architectural Support for Programming Languages and Operating Systems (ASPLOS 2012)} 26746ae37718SPaul E. McKenney,month = {March} 26756ae37718SPaul E. McKenney,year = {2012} 26766ae37718SPaul E. McKenney,pages = {199--210} 26776ae37718SPaul E. McKenney,numpages = {12} 26786ae37718SPaul E. McKenney,publisher = {ACM} 26796ae37718SPaul E. McKenney,address = {London, UK} 26806ae37718SPaul E. McKenney,url="http://people.csail.mit.edu/nickolai/papers/clements-bonsai.pdf" 26816ae37718SPaul E. McKenney} 26826ae37718SPaul E. McKenney 26836ae37718SPaul E. McKenney@unpublished{PaulEMcKenney2012ELCbattery 26846ae37718SPaul E. McKenney,Author="Paul E. McKenney" 26856ae37718SPaul E. McKenney,Title="Making {RCU} Safe For Battery-Powered Devices" 26866ae37718SPaul E. McKenney,month="February" 26876ae37718SPaul E. McKenney,day="15" 26886ae37718SPaul E. McKenney,year="2012" 26896ae37718SPaul E. McKenney,note="Available: 26906ae37718SPaul E. McKenney\url{http://www.rdrop.com/users/paulmck/RCU/RCUdynticks.2012.02.15b.pdf} 26916ae37718SPaul E. McKenney[Viewed March 1, 2012]" 26926ae37718SPaul E. McKenney,annotation={ 26936ae37718SPaul E. McKenney RCU_FAST_NO_HZ, round 2. 26946ae37718SPaul E. McKenney} 26956ae37718SPaul E. McKenney} 26966ae37718SPaul E. McKenney 26976ae37718SPaul E. McKenney@article{GuillermoVigueras2012RCUCrowd 26986ae37718SPaul E. McKenney,author = {Vigueras, Guillermo and Ordu\~{n}a, Juan M. and Lozano, Miguel} 26996ae37718SPaul E. McKenney,day = {25} 27006ae37718SPaul E. McKenney,doi = {10.1007/s11227-012-0766-x} 27016ae37718SPaul E. McKenney,issn = {0920-8542} 27026ae37718SPaul E. McKenney,journal = {The Journal of Supercomputing} 27036ae37718SPaul E. McKenney,keywords = {linux, simulation} 27046ae37718SPaul E. McKenney,month = apr 27056ae37718SPaul E. McKenney,posted-at = {2012-05-03 09:12:04} 27066ae37718SPaul E. McKenney,priority = {2} 27076ae37718SPaul E. McKenney,title = {{A Read-Copy Update based parallel server for distributed crowd simulations}} 27086ae37718SPaul E. McKenney,url = {http://dx.doi.org/10.1007/s11227-012-0766-x} 27096ae37718SPaul E. McKenney,year = {2012} 27106ae37718SPaul E. McKenney} 27116ae37718SPaul E. McKenney 27126ae37718SPaul E. McKenney 27136ae37718SPaul E. McKenney@unpublished{JonCorbet2012ACCESS:ONCE 27146ae37718SPaul E. McKenney,Author="Jon Corbet" 27156ae37718SPaul E. McKenney,Title="{ACCESS\_ONCE()}" 27166ae37718SPaul E. McKenney,month="August" 27176ae37718SPaul E. McKenney,day="1" 27186ae37718SPaul E. McKenney,year="2012" 27196ae37718SPaul E. McKenney,note="\url{http://lwn.net/Articles/508991/}" 27206ae37718SPaul E. McKenney,annotation={ 27216ae37718SPaul E. McKenney A couple of simple specific compiler optimizations that motivate 27226ae37718SPaul E. McKenney ACCESS_ONCE(). 27236ae37718SPaul E. McKenney} 27246ae37718SPaul E. McKenney} 27256ae37718SPaul E. McKenney 27266ae37718SPaul E. McKenney@unpublished{AlexeyGotsman2012VerifyGraceExtended 27276ae37718SPaul E. McKenney,Author="Alexey Gotsman and Noam Rinetzky and Hongseok Yang" 27286ae37718SPaul E. McKenney,Title="Verifying Highly Concurrent Algorithms with Grace (extended version)" 27296ae37718SPaul E. McKenney,month="July" 27306ae37718SPaul E. McKenney,day="10" 27316ae37718SPaul E. McKenney,year="2012" 27326ae37718SPaul E. McKenney,note="\url{http://software.imdea.org/~gotsman/papers/recycling-esop13-ext.pdf}" 27336ae37718SPaul E. McKenney,annotation={ 27346ae37718SPaul E. McKenney Separation-logic formulation of RCU uses. 27356ae37718SPaul E. McKenney} 27366ae37718SPaul E. McKenney} 27376ae37718SPaul E. McKenney 27386ae37718SPaul E. McKenney@unpublished{PaulMcKenney2012RCUUsage 27396ae37718SPaul E. McKenney,Author="Paul E. McKenney and Silas Boyd-Wickizer and Jonathan Walpole" 27406ae37718SPaul E. McKenney,Title="{RCU} Usage In the Linux Kernel: One Decade Later" 27416ae37718SPaul E. McKenney,month="September" 27426ae37718SPaul E. McKenney,day="17" 27436ae37718SPaul E. McKenney,year="2012" 27446ae37718SPaul E. McKenney,url=http://rdrop.com/users/paulmck/techreports/survey.2012.09.17a.pdf 27456ae37718SPaul E. McKenney,note="Technical report paulmck.2012.09.17" 27466ae37718SPaul E. McKenney,annotation={ 27476ae37718SPaul E. McKenney Overview of the first variant of no-CBs CPUs for RCU. 27486ae37718SPaul E. McKenney} 27496ae37718SPaul E. McKenney} 27506ae37718SPaul E. McKenney 27516ae37718SPaul E. McKenney@unpublished{JonCorbet2012NOCB 27526ae37718SPaul E. McKenney,Author="Jon Corbet" 27536ae37718SPaul E. McKenney,Title="Relocating RCU callbacks" 27546ae37718SPaul E. McKenney,month="October" 27556ae37718SPaul E. McKenney,day="31" 27566ae37718SPaul E. McKenney,year="2012" 27576ae37718SPaul E. McKenney,note="\url{http://lwn.net/Articles/522262/}" 27586ae37718SPaul E. McKenney,annotation={ 27596ae37718SPaul E. McKenney Overview of the first variant of no-CBs CPUs for RCU. 27606ae37718SPaul E. McKenney} 27616ae37718SPaul E. McKenney} 27626ae37718SPaul E. McKenney 27636ae37718SPaul E. McKenney@phdthesis{JustinSeyster2012PhD 27646ae37718SPaul E. McKenney,author="Justin Seyster" 27656ae37718SPaul E. McKenney,title="Runtime Verification of Kernel-Level Concurrency Using Compiler-Based Instrumentation" 27666ae37718SPaul E. McKenney,school="Stony Brook University" 27676ae37718SPaul E. McKenney,year="2012" 27686ae37718SPaul E. McKenney,annotation={ 27696ae37718SPaul E. McKenney Looking for data races, including those involving RCU. 27706ae37718SPaul E. McKenney Proposal: 27716ae37718SPaul E. McKenney http://www.fsl.cs.sunysb.edu/docs/jseyster-proposal/redflag.pdf 27726ae37718SPaul E. McKenney Dissertation: 27736ae37718SPaul E. McKenney http://www.fsl.cs.sunysb.edu/docs/jseyster-dissertation/redflag.pdf 27746ae37718SPaul E. McKenney} 27756ae37718SPaul E. McKenney} 27766ae37718SPaul E. McKenney 27776ae37718SPaul E. McKenney@unpublished{PaulEMcKenney2013RCUUsage 27786ae37718SPaul E. McKenney,Author="Paul E. McKenney and Silas Boyd-Wickizer and Jonathan Walpole" 27796ae37718SPaul E. McKenney,Title="{RCU} Usage in the {Linux} Kernel: One Decade Later" 27806ae37718SPaul E. McKenney,month="February" 27816ae37718SPaul E. McKenney,day="24" 27826ae37718SPaul E. McKenney,year="2013" 27836ae37718SPaul E. McKenney,note="\url{http://rdrop.com/users/paulmck/techreports/RCUUsage.2013.02.24a.pdf}" 27846ae37718SPaul E. McKenney,annotation={ 27856ae37718SPaul E. McKenney Usage of RCU within the Linux kernel. 27866ae37718SPaul E. McKenney} 27876ae37718SPaul E. McKenney} 27886ae37718SPaul E. McKenney 27896ae37718SPaul E. McKenney@inproceedings{AlexeyGotsman2013ESOPRCU 27906ae37718SPaul E. McKenney,author = {Alexey Gotsman and Noam Rinetzky and Hongseok Yang} 27916ae37718SPaul E. McKenney,title = {Verifying concurrent memory reclamation algorithms with grace} 27926ae37718SPaul E. McKenney,booktitle = {ESOP'13: European Symposium on Programming} 27936ae37718SPaul E. McKenney,year = {2013} 27946ae37718SPaul E. McKenney,pages = {249--269} 27956ae37718SPaul E. McKenney,publisher = {Springer} 27966ae37718SPaul E. McKenney,address = {Rome, Italy} 27976ae37718SPaul E. McKenney,annotation={ 27986ae37718SPaul E. McKenney http://software.imdea.org/~gotsman/papers/recycling-esop13.pdf 27996ae37718SPaul E. McKenney} 28006ae37718SPaul E. McKenney} 28016ae37718SPaul E. McKenney 28026ae37718SPaul E. McKenney@unpublished{PaulEMcKenney2013NoTinyPreempt 28036ae37718SPaul E. McKenney,Author="Paul E. McKenney" 28046ae37718SPaul E. McKenney,Title="Simplifying RCU" 28056ae37718SPaul E. McKenney,month="March" 28066ae37718SPaul E. McKenney,day="6" 28076ae37718SPaul E. McKenney,year="2013" 28086ae37718SPaul E. McKenney,note="\url{http://lwn.net/Articles/541037/}" 28096ae37718SPaul E. McKenney,annotation={ 28106ae37718SPaul E. McKenney Getting rid of TINY_PREEMPT_RCU. 28114c62abc9SPaul E. McKenney} 28124c54005cSPaul E. McKenney} 2813