Lines Matching full:rcu
3 What is RCU? -- "Read, Copy, Update"
6 Please note that the "What is RCU?" LWN series is an excellent place
7 to start learning about RCU:
9 | 1. What is RCU, Fundamentally? https://lwn.net/Articles/262464/
10 | 2. What is RCU? Part 2: Usage https://lwn.net/Articles/263130/
11 | 3. RCU part 3: the RCU API https://lwn.net/Articles/264090/
12 | 4. The RCU API, 2010 Edition https://lwn.net/Articles/418853/
14 | 5. The RCU API, 2014 Edition https://lwn.net/Articles/609904/
16 | 6. The RCU API, 2019 Edition https://lwn.net/Articles/777036/
20 What is RCU?
22 RCU is a synchronization mechanism that was added to the Linux kernel
24 situations. Although RCU is actually quite simple once you understand it,
26 most of the past descriptions of RCU have been written with the mistaken
27 assumption that there is "one true way" to describe RCU. Instead,
29 to arrive at an understanding of RCU. This document provides several
32 :ref:`1. RCU OVERVIEW <1_whatisRCU>`
34 :ref:`2. WHAT IS RCU'S CORE API? <2_whatisRCU>`
36 :ref:`3. WHAT ARE SOME EXAMPLE USES OF CORE RCU API? <3_whatisRCU>`
40 :ref:`5. WHAT ARE SOME SIMPLE IMPLEMENTATIONS OF RCU? <5_whatisRCU>`
46 :ref:`8. FULL LIST OF RCU APIs <8_whatisRCU>`
55 understand the RCU implementation should focus on Section 5, then dive
68 1. RCU OVERVIEW
71 The basic idea behind RCU is to split updates into "removal" and
93 So the typical RCU update sequence goes something like the following:
98 b. Wait for all previous readers to complete their RCU read-side
105 Step (b) above is the key idea underlying RCU's deferred destruction.
106 The ability to wait until all readers are done allows RCU readers to
112 and must therefore exclude readers. In contrast, RCU-based updaters
116 readers. Concurrent RCU readers can then continue accessing the old
127 For example, RCU readers and updaters need not communicate at all,
128 but RCU provides implicit low-overhead communication between readers
133 Read on to learn about how RCU's API makes this easy.
137 2. WHAT IS RCU'S CORE API?
140 The core RCU API is quite small:
148 There are many other members of the RCU API, but the rest can be
152 The five core RCU APIs are described below, the other 18 will be enumerated
161 entering an RCU read-side critical section. It is illegal
162 to block while in an RCU read-side critical section, though
163 kernels built with CONFIG_PREEMPT_RCU can preempt RCU
164 read-side critical sections. Any RCU-protected data structure
165 accessed during an RCU read-side critical section is guaranteed to
167 Reference counts may be used in conjunction with RCU to maintain
175 exiting an RCU read-side critical section. Note that RCU
183 code. It does this by blocking until all pre-existing RCU
186 any subsequent RCU read-side critical sections to complete.
198 To reiterate, synchronize_rcu() waits only for ongoing RCU
203 **immediately** after the last pre-existing RCU read-side critical
205 delays. For another thing, many RCU implementations process
210 readers are done, its implementation is key to RCU. For RCU
217 after all ongoing RCU read-side critical sections have completed.
240 RCU-protected pointer, in order to safely communicate the change
246 pointers are protected by RCU and (2) the point at which a
258 The reader uses rcu_dereference() to fetch an RCU-protected
268 RCU-protected pointer to a local variable, then dereferences
280 RCU-protected structure, using the local variable is of
287 only within the enclosing RCU read-side critical section [1]_.
298 Holding a reference from one RCU read-side critical section
307 RCU, in particular, flagging a pointer that is subject to changing
314 of an RCU read-side critical section as long as the usage is
327 update-side code as well as by RCU readers, then an additional
330 the RCU lockdep code would complain only if this instance was
331 invoked outside of an RCU read-side critical section and without
358 The RCU infrastructure observes the time sequence of rcu_read_lock(),
362 implementations of the RCU infrastructure make heavy use of batching in
365 There are at least three flavors of RCU usage in the Linux kernel. The diagram
387 a. RCU applied to normal data structures.
389 b. RCU applied to networking data structures that may be subjected
392 c. RCU applied to scheduler and interrupt/NMI-handler tasks.
399 3. WHAT ARE SOME EXAMPLE USES OF CORE RCU API?
402 This section shows a simple use of the core RCU API to protect a
404 uses of RCU may be found in listRCU.rst, arrayRCU.rst, and NMI-RCU.rst.
465 - Use rcu_read_lock() and rcu_read_unlock() to guard RCU
468 - Within an RCU read-side critical section, use rcu_dereference()
469 to dereference RCU-protected pointers.
474 - Use rcu_assign_pointer() to update an RCU-protected pointer.
481 RCU-protected data structure, but **before** reclaiming/freeing
483 RCU read-side critical sections that might be referencing that
486 See checklist.rst for additional rules to follow when using RCU.
487 And again, more-typical uses of RCU may be found in listRCU.rst,
488 arrayRCU.rst, and NMI-RCU.rst.
513 struct rcu_head rcu;
543 call_rcu(&old_fp->rcu, foo_reclaim);
550 struct foo *fp = container_of(rp, struct foo, rcu);
564 RCU distinction between updater, namely foo_update_a(), and reclaimer,
571 RCU-protected data structure in order to register a callback
572 function that will be invoked after the completion of all RCU
580 kfree_rcu(old_fp, rcu);
582 Again, see checklist.rst for additional rules governing the use of RCU.
586 5. WHAT ARE SOME SIMPLE IMPLEMENTATIONS OF RCU?
589 One of the nice things about RCU is that it has extremely simple "toy"
592 presents two such "toy" implementations of RCU, one that is implemented
594 resembles "classic" RCU. Both are way too simple for real-world use,
596 in getting a feel for how RCU works. See kernel/rcu/update.c for a
599 http://www.rdrop.com/users/paulmck/RCU
601 for papers describing the Linux kernel RCU implementation. The OLS'01
608 This section presents a "toy" RCU implementation that is based on
642 don't forget about them when submitting patches making use of RCU!]::
659 that once synchronize_rcu() exits, all RCU read-side critical sections
670 from deadlock (an important property of RCU). The reason for this is
684 5B. "TOY" EXAMPLE #2: CLASSIC RCU argument
686 This section presents a "toy" RCU implementation that is based on
687 "classic RCU". It is also short on performance (but only for updates) and
706 This is the great strength of classic RCU in a non-preemptive kernel:
720 Remember that it is illegal to block while in an RCU read-side critical
722 that it must have completed all preceding RCU read-side critical sections.
724 RCU read-side critical sections will have completed.
728 that there are no RCU read-side critical sections holding a reference
734 Give an example where Classic RCU's read-side
742 If it is illegal to block in an RCU read-side
753 Although RCU can be used in many different ways, a very common use of
754 RCU is analogous to reader-writer locking. The following unified
755 diff shows how closely related RCU and reader-writer locking can be.
868 a single atomic update, converting to RCU will require special care.
870 Also, the presence of synchronize_rcu() means that the RCU version of
881 always the best way to think about using RCU. Another helpful analogy
882 considers RCU an effective reference count on everything which is
883 protected by RCU.
891 but with RCU the typical approach is to perform reads with SMP-aware
894 RCU provides a number of support functions that embed the required
909 which an RCU reference is held include:
917 The understanding that RCU provides a reference that only prevents a
919 slab cache marked ``SLAB_TYPESAFE_BY_RCU``. RCU operations may yield a
922 the same type. In this case RCU doesn't even protect the identity of the
936 passed to kref_put(). When RCU is being used, such finalization code
943 To see how to choose between these two analogies -- of RCU as a
944 reader-writer lock and RCU as a reference counting system -- it is useful
947 and shows how RCU can facilitate concurrency while elements are added
954 8. FULL LIST OF RCU APIs
957 The RCU APIs are documented in docbook-format header comments in the
962 RCU list traversal::
986 RCU pointer/list update::
1010 RCU::
1067 All: lockdep-checked RCU utility APIs::
1073 All: Unchecked RCU-protected pointer access::
1077 All: Unchecked RCU-protected pointer access with dereferencing prohibited::
1084 However, given that there are no fewer than four families of RCU APIs
1099 or some other mechanism) as if they were explicit RCU readers?
1100 If so, RCU-sched is the only choice that will work for you.
1102 d. Do you need RCU grace periods to complete even in the face
1109 RCU, but inappropriate for other synchronization mechanisms?
1118 g. Otherwise, use RCU.
1120 Of course, this all assumes that you have determined that RCU is in fact
1131 kernel? [Referring to the lock-based "toy" RCU
1159 Even in the absence of deadlock, this RCU implementation
1162 consider task A in an RCU read-side critical section
1166 read_acquire rcu_gp_mutex. Task A's RCU read-side
1170 Realtime RCU implementations therefore use a counter-based
1171 approach where tasks in RCU read-side critical sections
1177 Give an example where Classic RCU's read-side
1187 RCU allows such interrupt-disabling to be dispensed with.
1188 Thus, without RCU, you pay the cost of disabling interrupts,
1189 and with RCU you don't.
1191 One can argue that the overhead of RCU in this
1194 the overhead of RCU is merely zero, and that replacing
1196 with the zero-overhead RCU scheme does not constitute
1206 If it is illegal to block in an RCU read-side
1212 critical sections, it permits preemption of RCU
1214 spinlocks blocking while in RCU read-side critical
1218 possible to use priority boosting to keep the RCU
1238 For more information, see http://www.rdrop.com/users/paulmck/RCU.