Lines Matching full:rcu
4 This document describes RCU-related publications, and is followed by
6 be found at http://www.rdrop.com/users/paulmck/RCU/. For others, browsers
9 The first thing resembling RCU was published in 1980, when Kung and Lehman
23 serialization, which is an RCU-like mechanism that relies on the presence
31 (In contrast, implementation of RCU is permitted only in software licensed
35 At first glance, this has nothing to do with RCU, but nevertheless
37 RCU implementation in DYNIX/ptx. In 1988, Barbara Liskov published
66 synchronization [HMassalinPhD]. RCU makes extremely heavy use of
91 1995 also saw the first publication of DYNIX/ptx's RCU mechanism
98 mechanism, which is quite similar to RCU [Gamsa99]. These operating
99 systems made pervasive use of RCU in place of "existence locks", which
103 led to yet another independent invention of something like RCU
105 RCU presentation involving Linux [McKenney01a] at OLS. The resulting
106 abundance of RCU patches was presented the following year [McKenney02a],
107 and use of RCU in dcache was first described that same year [Linder02a].
126 By the same token, RCU can be thought of as a "bulk reference count",
129 not necessarily exactly the same as, an RCU grace period. In classic
130 RCU, the reference counter is the per-CPU bit in the "bitmask" field,
132 the corresponding CPU during the prior grace period. Of course, RCU
135 In 2003, the K42 group described how RCU could be used to create
137 Later that year saw a paper describing an RCU implementation
140 [MingmingCao2002IPCRCU]), and an introduction to RCU in Linux Journal
143 2004 has seen a Linux-Journal article on use of RCU in dcache
144 [McKenney04a], a performance comparison of locking to RCU on several
145 different CPUs [McKenney04b], a dissertation describing use of RCU in a
147 describing how to make RCU safe for soft-realtime applications [Sarma04c],
148 and a paper describing SELinux performance with RCU [JamesMorris04b].
150 2005 brought further adaptation of RCU to realtime use, permitting
151 preemption of RCU realtime critical sections [PaulMcKenney05a,
154 2006 saw the first best-paper award for an RCU paper [ThomasEHart2006a],
156 RCU [PaulEMcKenney2006b], but priority-boosting of RCU read-side critical
157 sections proved elusive. An RCU implementation permitting general
159 Robert Olsson described an RCU-protected trie-hash combination
162 2007 saw the journal version of the award-winning RCU paper from 2006
166 preemptible RCU [PaulEMcKenney2007PreemptibleRCU], and the three-part
167 LWN "What is RCU?" series [PaulEMcKenney2007WhatIsRCUFundamentally,
170 2008 saw a journal paper on real-time RCU [DinakarGuniguntala2008IBMSysJ],
171 a history of how Linux changed RCU more than RCU changed Linux
172 [PaulEMcKenney2008RCUOSR], and a design overview of hierarchical RCU
175 2009 introduced user-level RCU algorithms [PaulEMcKenney2009MaliciousURCU],
178 its appearance, as did expedited RCU [PaulEMcKenney2009expeditedRCU].
179 The problem of resizable RCU-protected hash tables may now be on a path
181 using RCU to solve their parallel problems [HariKannan2009DynamicAnalysisRCU].
183 2010 produced a simpler preemptible-RCU implementation
184 based on TREE_RCU [PaulEMcKenney2010SimpleOptRCU], lockdep-RCU
185 [PaulEMcKenney2010LockdepRCU], another resizable RCU-protected hash
188 avoidance in the networking code), realization of the 2009 RCU-protected
190 the RCU API [PaulEMcKenney2010RCUAPI].
193 [LinusTorvalds2011Linux2:6:38:rc1:NPigginVFS], an RCU-protected red-black
196 RCU-protected resizable hash tables [Triplett:2011:RPHash], the 3.0 RCU
199 work looked at debugging uses of RCU [Seyster:2011:RFA:2075416.2075425].
202 covering RCU-protected resizable hash tables and the relationship
208 after seventeen years of attempts, an RCU paper made it into a top-flight
211 user-level RCU to crowd simulation [GuillermoVigueras2012RCUCrowd], and
213 RCU based on separation logic [AlexeyGotsman2012VerifyGraceExtended],
233 Oldest use of something vaguely resembling RCU that I have found.
270 RCU-like usage that does not rely on an automatic garbage
378 Appears to be an independent invention of an RCU-like mechanism.
394 invention of RCU-like function -- but this is restricted
424 Independent invention of RCU-like mechanism.
446 Apparently independent invention of RCU-like mechanism.
496 Describes the parallel RCU infrastructure. Includes NUMA aspect
499 Another independent invention of an RCU-like mechanism, but the
500 "real" RCU this time!
515 Describes use of RCU to synchronize data between a pair of
546 Describes and analyzes RCU mechanism in DYNIX/ptx. Describes
550 http://www.rdrop.com/users/paulmck/RCU/rclockpdcsproof.pdf
566 Use of RCU-like facility in K42/Tornado. Another independent
567 invention of RCU.
584 Proto-RCU proposal from Phil Rumpf and Rusty Russell.
585 Yet another independent invention of RCU.
602 Proto-RCU proposal from Phil Rumpf and Rusty Russell.
614 \url{http://lse.sourceforge.net/locking/rcu/rcupdate_doc.html}
617 Prototypical Linux documentation for RCU.
632 'Change in mode' aspect of RCU. Can be thought of as a lazy barrier.
645 \url{http://www.rdrop.com/users/paulmck/RCU/rclock_OLS.2001.05.01c.pdf}
648 Described RCU, and presented some patches implementing and using
694 ,Title="some RCU dcache and ratcache results"
741 Presented and compared a number of RCU implementations for the
755 Compare fastwalk and RCU for dcache. RCU won.
768 Suggested RCU for vfs\_shared\_cred.
792 ,title="Use RCU for System-V IPC"
818 Performance of dcache RCU on kernbench for 16x NUMA-Q and 1x,
819 2x, and 4x systems. RCU does no harm, and helps on 16x.
832 Mingming Cao's patch to introduce RCU to SysV IPC.
845 Linus suggests replacing brlock with RCU and/or seqlocks:
848 by RCU and/or seqlocks, and we could get rid of brlocks entirely.'
850 Stephen Hemminger responds by replacing them with RCU.
867 Use of RCU to enable hot-swapping for autonomic behavior in K42.
878 Described the relationship of the VM/XA passive serialization to RCU.
894 Compared updated RCU implementations for the Linux kernel, and
895 described System V IPC use of RCU, including order-of-magnitude
897 http://www.rdrop.com/users/paulmck/RCU/rcu.FREENIX.2003.06.14.pdf
916 ,title="Using {RCU} in the {Linux} 2.5 Kernel"
927 Reader-friendly intro to RCU, with the infamous old-man-and-brat
934 ,Title="RCU low latency patches"
953 Applies RCU to a wildcard-search Patricia tree in order to permit
954 synchronization-free lookup. RCU is used to retain removed nodes
961 ,title="Scaling dcache with {RCU}"
969 Reader friendly intro to dcache and RCU.
977 ,Title="{RCU} vs. Locking Performance on Different {CPUs}"
984 \url{http://www.rdrop.com/users/paulmck/RCU/lockperf.2004.01.17a.pdf}
987 Compares performance of RCU to that of other locking primitives
994 ,Title="{[PATCH]} {RCU} for low latency (experimental)"
999 Head of thread: dipankar/2004.03.23/rcu-low-lat.1.patch
1005 ,Title="Re: {[PATCH]} {RCU} for low latency (experimental)"
1010 dipankar/rcuth.2004.03.24/rcu-throttle.patch
1016 ,Title="[RFC] 0/5 rcu lock update"
1023 Hierarchical-bitmap patch for RCU infrastructure.
1029 ,Title="Re: [Lse-tech] [RFC, PATCH] 1/5 rcu lock update:
1037 RCU runs reasonably on a 512-CPU SGI using Manfred Spraul's patches,
1053 ,Title="Making {RCU} Safe for Deep Sub-Millisecond Response
1062 Describes and compares a number of modifications to the Linux RCU
1064 …https://www.usenix.org/conference/2004-usenix-annual-technical-conference/making-rcu-safe-deep-sub…
1095 Describes RCU implementations and presents design patterns
1096 corresponding to common uses of RCU in several operating-system
1098 http://www.rdrop.com/users/paulmck/RCU/RCUdissertation.2004.07.14e1.pdf
1105 ,Title="{Re: RCU : Abstracted RCU dereferencing [5/5]}"
1118 ,Title="{[RFC\&PATCH] Alternative {RCU} implementation}"
1126 make RCU happen, allowing RCU to function on CPUs that do not
1140 Proposes comparing RCU to lock-free methods for the Linux kernel.
1146 ,Title="Subject: [RFC] Use RCU for tcp\_ehash lookup"
1153 Srivatsa's RCU patch for tcp_ehash lookup.
1185 ,Title="{[PATCH 1/3] RCU: \url{rcu_assign_pointer()} removal of memory barriers}"
1198 ,Title="{[PATCH 2/3] SELinux} scalability - convert {AVC} to {RCU}"
1219 RCU helps SELinux performance. ;-) Made LWN.
1225 ,Title="{RCU} Semantics: A First Attempt"
1230 \url{http://www.rdrop.com/users/paulmck/RCU/rcu-semantics.2005.01.30a.pdf}
1233 Early derivation of RCU semantics.
1239 ,Title="Real-Time Preemption and {RCU}"
1247 First posting showing how RCU can be safely adapted for
1248 preemptible RCU read side critical sections.
1254 ,Title="Re: Real-Time Preemption and {RCU}"
1263 processing for crude-but-workable realtime RCU. The downside
1279 Comparison of RCU, QBSR, and EBSR. RCU wins for read-mostly
1301 ,Title="{[RFC]} {RCU} and {CONFIG\_PREEMPT\_RT} progress"
1321 \url{http://www.rdrop.com/users/paulmck/RCU/realtimeRCU.2005.04.23a.pdf}
1324 Realtime turns into making RCU yet more realtime friendly.
1344 ,Title="Read-Copy Update {(RCU)}"
1348 \url{http://www.rdrop.com/users/paulmck/RCU}
1351 Paul McKenney's RCU page.
1357 ,Title="{RCU}+{SMR} (hazard pointers)"
1383 ,Title="{[RFC,PATCH] RCU} and {CONFIG\_PREEMPT\_RT} sane patch"
1391 First operating counter-based realtime RCU patch posted to LKML.
1405 First operating counter-based realtime RCU patch posted to LKML,
1413 ,Title="{[PATCH]} {RCU} torture testing"
1427 ,Title="Re: [{PATCH}, {RFC}] {RCU} : {OOM} avoidance and lower latency"
1437 something else always proved superior. Partitioning or RCU. ;-)
1452 \url{http://www.rdrop.com/users/paulmck/RCU/hart_ipdps06.pdf}
1462 ,Title="[patch 3/3] radix-tree: {RCU} lockless readside"
1470 RCU-protected radix tree.
1477 ,Title="Extending {RCU} for Realtime and Embedded Workloads"
1484 \url{http://www.rdrop.com/users/paulmck/RCU/OLSrtRCU.2006.08.11a.pdf}
1487 Described how to improve the -rt implementation of realtime RCU.
1501 Wikipedia RCU page as of July 8 2006.
1517 Uses RCU-protected radix tree for a lockless page cache.
1523 ,Title="Sleepable {RCU}"
1530 \url{http://www.rdrop.com/users/paulmck/RCU/srcu.2007.01.14a.pdf}
1545 RCU-protected dynamic trie-hash combination.
1552 ,Title="Re: {[-mm PATCH 1/4]} {RCU}: split classic rcu"
1563 ,Title="{RCU} {Linux} Usage"
1567 \url{http://www.rdrop.com/users/paulmck/RCU/linuxusage.html}
1570 Paul McKenney's RCU page showing graphs plotting Linux-kernel
1571 usage of RCU.
1577 ,Title="Read-Copy Update {(RCU)} Usage in {Linux} Kernel"
1581 \url{http://www.rdrop.com/users/paulmck/RCU/linuxusage/rculocktab.html}
1584 Paul McKenney's RCU page showing Linux usage of RCU in tabular
1599 RCU-based reader-writer lock that allows readers to proceed with
1665 Using RCU as a pure delay leads to a 2.5x slowdown in skbs in
1682 Uses K42's RCU-like functionality to manage clustered-object
1700 Describes relationship of K42 generations to RCU.
1705 @unpublished{CoreyMinyard2007list:splice:rcu
1707 ,Title="{[PATCH]} add an {RCU} version of list splicing"
1721 ,Title="{RCU} and Unloadable Modules"
1743 RCU-like implementation for frequent updaters and rare readers(!).
1750 ,Title="Priority-Boosting {RCU} Read-Side Critical Sections"
1756 LWN article introducing RCU priority boosting.
1758 http://www.rdrop.com/users/paulmck/RCU/RCUbooststate.2007.04.16a.pdf
1790 Role of RCU in K42.
1804 RCU-protected dynamic trie-hash combination.
1819 Page-cache modifications permitting RCU readers and concurrent
1826 ,Title="What is {RCU}?"
1830 \url{http://www.rdrop.com/users/paulmck/RCU/whatisRCU.html}
1833 Describes RCU in Linux kernel.
1863 RCU for C++, parts 1 and 2.
1877 RCU for C++, part 2, updated many times.
1883 ,Title="[PATCH RFC 0/9] {RCU}: Preemptible {RCU}"
1891 Final patch for preemptible RCU to -rt. (Later patches were
1906 LWN article describing the design of preemptible RCU.
1929 @unpublished{MathieuDesnoyers2007call:rcu:schedNeeded
1946 # "What is RCU?" LWN series.
1948 # http://lwn.net/Articles/262464/ (What is RCU, Fundamentally?)
1949 # http://lwn.net/Articles/263130/ (What is RCU's Usage?)
1950 # http://lwn.net/Articles/264090/ (What is RCU's API?)
1954 ,Title="What is {RCU}, Fundamentally?"
1962 Lays out the three basic components of RCU: (1) publish-subscribe,
1970 ,Title="What is {RCU}? Part 2: Usage"
1978 Lays out six uses of RCU:
1979 1. RCU is a Reader-Writer Lock Replacement
1980 2. RCU is a Restricted Reference-Counting Mechanism
1981 3. RCU is a Bulk Reference-Counting Mechanism
1982 4. RCU is a Poor Man's Garbage Collector
1983 5. RCU is a Way of Providing Existence Guarantees
1984 6. RCU is a Way of Waiting for Things to Finish
1990 ,Title="{RCU} part 3: the {RCU} {API}"
1998 Gives an overview of the Linux-kernel RCU API and a brief annotated RCU
2004 # "What is RCU?" LWN series.
2011 ,Title="{[PATCH]} add support for dynamic ticks and preempt rcu"
2019 Patch that prevents preemptible RCU from unnecessarily waking
2049 \url{http://www.rdrop.com/users/paulmck/RCU/TechIntroLinux.2008.02.19a.pdf}
2055 ,Title="Integrating and Validating dynticks and Preemptable RCU"
2064 dynticks/RCU interface.
2078 RCU, realtime RCU, sleepable RCU, performance.
2086 ,Title="[{RFC}][{PATCH}] rcu classic: new algorithm for callbacks-processing"
2094 Updated RCU classic algorithm. Introduced multi-tailed list
2095 for RCU callbacks and also pulling common code into
2113 Linux changed RCU to a far greater degree than RCU has changed Linux.
2120 ,Title="[{RFC}, {PATCH}] state machine based rcu"
2128 State-based RCU. One key thing that this patch does is to
2135 ,Title="Re: [{RFC}, {PATCH}] v4 scalable classic {RCU} implementation"
2144 and NMI processing for hierarchical RCU's dynticks interface.
2167 ,Title="Hierarchical {RCU}"
2173 RCU with combining-tree-based grace-period detection,
2181 ,Title="Re: [PATCH fyi] RCU: the bloatwatch edition"
2189 Small-footprint implementation of RCU for uniprocessor
2196 ,Title="Using a Malicious User-Level {RCU} to Torture {RCU}-Based Algorithms"
2202 \url{http://www.rdrop.com/users/paulmck/RCU/urcutorture.2009.01.22a.pdf}
2205 Realtime RCU and torture-testing RCU uses.
2211 ,Title="[{RFC} git tree] Userspace {RCU} (urcu) for {Linux}"
2217 Mathieu Desnoyers's user-space RCU implementation.
2218 git://lttng.org/userspace-rcu.git
2219 http://lttng.org/cgi-bin/gitweb.cgi?p=userspace-rcu.git
2227 ,Title="{RCU}: The {Bloatwatch} Edition"
2235 Uniprocessor assumptions allow simplified RCU implementation.
2256 ,Title="[{PATCH} -tip 0/3] expedited 'big hammer' {RCU} grace periods"
2264 First posting of expedited RCU to be accepted into -tip.
2270 ,Title="[{PATCH} {RFC} -tip 0/4] {RCU} cleanups and simplified preemptable {RCU}"
2278 First posting of simple and fast preemptible RCU.
2304 Chapter 6 (page 97) covers user-level RCU.
2323 ,Title="Deterministic Synchronization in Multicore Systems: the Role of {RCU}"
2343 Day-one bug in Tree RCU that took forever to track down.
2347 @unpublished{MathieuDesnoyers2009defer:rcu
2349 ,Title="Kernel RCU: shrink the size of the struct rcu\_head"
2357 of RCU callbacks.
2368 OOMem model for Mathieu's user-level RCU mechanical proof of
2380 RCU overview, desiderata, semi-formal semantics, user-level RCU
2381 usage scenarios, three classes of RCU implementation, wait-free
2382 RCU updates, RCU grace-period batching, update overhead,
2383 http://www.rdrop.com/users/paulmck/RCU/urcu-main-accepted.2011.08.30a.pdf
2384 http://www.rdrop.com/users/paulmck/RCU/urcu-supp-accepted.2011.08.30a.pdf
2401 Uses RCU to protect metadata used in dynamic analysis.
2413 \url{http://www.rdrop.com/users/paulmck/RCU/SimplicityThruOptimization.2010.01.21f.pdf}
2423 ,Title="Lockdep-{RCU}"
2443 Use of RCU permits KVM to increase the size of guest OSes from
2457 Use a pair of list_head structures to support RCU-protected
2468 Data-race detector incorporating RCU.
2489 ,Title="The {RCU} {API}, 2010 Edition"
2509 Reviews RCU implementations and creates a few for OpenSolaris.
2510 Drives quiescent-state detection from RCU read-side primitives,
2524 "The RCU-based name lookup is at the other end of the spectrum - the
2591 ,Title="3.0 and {RCU:} what went wrong"
2597 Analysis of the RCU trainwreck in Linux kernel 3.0.
2613 RCU, and seqlock.
2639 RCU-protected hash tables, barriers vs. read-side traversal order.
2661 RCU overview, desiderata, semi-formal semantics, user-level RCU
2662 usage scenarios, three classes of RCU implementation, wait-free
2663 RCU updates, RCU grace-period batching, update overhead,
2664 http://www.rdrop.com/users/paulmck/RCU/urcu-main-accepted.2011.08.30a.pdf
2665 http://www.rdrop.com/users/paulmck/RCU/urcu-supp-accepted.2011.08.30a.pdf
2672 ,title = {Scalable Address Spaces Using {RCU} Balanced Trees}
2685 ,Title="Making {RCU} Safe For Battery-Powered Devices"
2690 \url{http://www.rdrop.com/users/paulmck/RCU/RCUdynticks.2012.02.15b.pdf}
2734 Separation-logic formulation of RCU uses.
2740 ,Title="{RCU} Usage In the Linux Kernel: One Decade Later"
2747 Overview of the first variant of no-CBs CPUs for RCU.
2753 ,Title="Relocating RCU callbacks"
2759 Overview of the first variant of no-CBs CPUs for RCU.
2769 Looking for data races, including those involving RCU.
2779 ,Title="{RCU} Usage in the {Linux} Kernel: One Decade Later"
2785 Usage of RCU within the Linux kernel.
2804 ,Title="Simplifying RCU"