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? http://lwn.net/Articles/262464/
10 | 2. What is RCU? Part 2: Usage http://lwn.net/Articles/263130/
11 | 3. RCU part 3: the RCU API http://lwn.net/Articles/264090/
12 | 4. The RCU API, 2010 Edition http://lwn.net/Articles/418853/
14 | 5. The RCU API, 2014 Edition http://lwn.net/Articles/609904/
18 What is RCU?
20 RCU is a synchronization mechanism that was added to the Linux kernel
22 situations. Although RCU is actually quite simple once you understand it,
24 most of the past descriptions of RCU have been written with the mistaken
25 assumption that there is "one true way" to describe RCU. Instead,
27 to arrive at an understanding of RCU. This document provides several
30 :ref:`1. RCU OVERVIEW <1_whatisRCU>`
32 :ref:`2. WHAT IS RCU'S CORE API? <2_whatisRCU>`
34 :ref:`3. WHAT ARE SOME EXAMPLE USES OF CORE RCU API? <3_whatisRCU>`
38 :ref:`5. WHAT ARE SOME SIMPLE IMPLEMENTATIONS OF RCU? <5_whatisRCU>`
42 :ref:`7. FULL LIST OF RCU APIs <7_whatisRCU>`
51 understand the RCU implementation should focus on Section 5, then dive
64 1. RCU OVERVIEW
67 The basic idea behind RCU is to split updates into "removal" and
89 So the typical RCU update sequence goes something like the following:
94 b. Wait for all previous readers to complete their RCU read-side
101 Step (b) above is the key idea underlying RCU's deferred destruction.
102 The ability to wait until all readers are done allows RCU readers to
108 and must therefore exclude readers. In contrast, RCU-based updaters
112 readers. Concurrent RCU readers can then continue accessing the old
123 For example, RCU readers and updaters need not communicate at all,
124 but RCU provides implicit low-overhead communication between readers
129 Read on to learn about how RCU's API makes this easy.
133 2. WHAT IS RCU'S CORE API?
136 The core RCU API is quite small:
144 There are many other members of the RCU API, but the rest can be
148 The five core RCU APIs are described below, the other 18 will be enumerated
157 entering an RCU read-side critical section. It is illegal
158 to block while in an RCU read-side critical section, though
159 kernels built with CONFIG_PREEMPT_RCU can preempt RCU
160 read-side critical sections. Any RCU-protected data structure
161 accessed during an RCU read-side critical section is guaranteed to
163 Reference counts may be used in conjunction with RCU to maintain
171 exiting an RCU read-side critical section. Note that RCU
179 code. It does this by blocking until all pre-existing RCU
182 any subsequent RCU read-side critical sections to complete.
194 To reiterate, synchronize_rcu() waits only for ongoing RCU
199 **immediately** after the last pre-existing RCU read-side critical
201 delays. For another thing, many RCU implementations process
206 readers are done, its implementation is key to RCU. For RCU
213 after all ongoing RCU read-side critical sections have completed.
236 RCU-protected pointer, in order to safely communicate the change
242 pointers are protected by RCU and (2) the point at which a
254 The reader uses rcu_dereference() to fetch an RCU-protected
264 RCU-protected pointer to a local variable, then dereferences
276 RCU-protected structure, using the local variable is of
283 only within the enclosing RCU read-side critical section [1]_.
294 Holding a reference from one RCU read-side critical section
303 RCU, in particular, flagging a pointer that is subject to changing
310 of an RCU read-side critical section as long as the usage is
319 a lockdep splat is emitted. See Documentation/RCU/Design/Requirements/Requirements.rst
323 update-side code as well as by RCU readers, then an additional
326 the RCU lockdep code would complain only if this instance was
327 invoked outside of an RCU read-side critical section and without
354 The RCU infrastructure observes the time sequence of rcu_read_lock(),
358 implementations of the RCU infrastructure make heavy use of batching in
361 There are at least three flavors of RCU usage in the Linux kernel. The diagram
383 a. RCU applied to normal data structures.
385 b. RCU applied to networking data structures that may be subjected
388 c. RCU applied to scheduler and interrupt/NMI-handler tasks.
395 3. WHAT ARE SOME EXAMPLE USES OF CORE RCU API?
398 This section shows a simple use of the core RCU API to protect a
400 uses of RCU may be found in :ref:`listRCU.rst <list_rcu_doc>`,
401 :ref:`arrayRCU.rst <array_rcu_doc>`, and :ref:`NMI-RCU.rst <NMI_rcu_doc>`.
462 - Use rcu_read_lock() and rcu_read_unlock() to guard RCU
465 - Within an RCU read-side critical section, use rcu_dereference()
466 to dereference RCU-protected pointers.
471 - Use rcu_assign_pointer() to update an RCU-protected pointer.
478 RCU-protected data structure, but **before** reclaiming/freeing
480 RCU read-side critical sections that might be referencing that
483 See checklist.txt for additional rules to follow when using RCU.
484 And again, more-typical uses of RCU may be found in :ref:`listRCU.rst
485 <list_rcu_doc>`, :ref:`arrayRCU.rst <array_rcu_doc>`, and :ref:`NMI-RCU.rst
512 struct rcu_head rcu;
542 call_rcu(&old_fp->rcu, foo_reclaim);
549 struct foo *fp = container_of(rp, struct foo, rcu);
563 RCU distinction between updater, namely foo_update_a(), and reclaimer,
570 RCU-protected data structure in order to register a callback
571 function that will be invoked after the completion of all RCU
579 kfree_rcu(old_fp, rcu);
581 Again, see checklist.txt for additional rules governing the use of RCU.
585 5. WHAT ARE SOME SIMPLE IMPLEMENTATIONS OF RCU?
588 One of the nice things about RCU is that it has extremely simple "toy"
591 presents two such "toy" implementations of RCU, one that is implemented
593 resembles "classic" RCU. Both are way too simple for real-world use,
595 in getting a feel for how RCU works. See kernel/rcu/update.c for a
598 http://www.rdrop.com/users/paulmck/RCU
600 for papers describing the Linux kernel RCU implementation. The OLS'01
607 This section presents a "toy" RCU implementation that is based on
641 don't forget about them when submitting patches making use of RCU!]::
658 that once synchronize_rcu() exits, all RCU read-side critical sections
665 Documentation/RCU/Design/Requirements/Requirements.rst
669 from deadlock (an important property of RCU). The reason for this is
683 5B. "TOY" EXAMPLE #2: CLASSIC RCU
685 This section presents a "toy" RCU implementation that is based on
686 "classic RCU". It is also short on performance (but only for updates) and
705 This is the great strength of classic RCU in a non-preemptive kernel:
719 Remember that it is illegal to block while in an RCU read-side critical
721 that it must have completed all preceding RCU read-side critical sections.
723 RCU read-side critical sections will have completed.
727 that there are no RCU read-side critical sections holding a reference
733 Give an example where Classic RCU's read-side
741 If it is illegal to block in an RCU read-side
752 Although RCU can be used in many different ways, a very common use of
753 RCU is analogous to reader-writer locking. The following unified
754 diff shows how closely related RCU and reader-writer locking can be.
867 a single atomic update, converting to RCU will require special care.
869 Also, the presence of synchronize_rcu() means that the RCU version of
876 7. FULL LIST OF RCU APIs
879 The RCU APIs are documented in docbook-format header comments in the
884 RCU list traversal::
908 RCU pointer/list update::
932 RCU::
989 All: lockdep-checked RCU-protected pointer access::
1000 However, given that there are no fewer than four families of RCU APIs
1015 or some other mechanism) as if they were explicit RCU readers?
1016 If so, RCU-sched is the only choice that will work for you.
1018 d. Do you need RCU grace periods to complete even in the face
1025 RCU, but inappropriate for other synchronization mechanisms?
1034 g. Otherwise, use RCU.
1036 Of course, this all assumes that you have determined that RCU is in fact
1047 kernel? [Referring to the lock-based "toy" RCU
1075 Even in the absence of deadlock, this RCU implementation
1078 consider task A in an RCU read-side critical section
1082 read_acquire rcu_gp_mutex. Task A's RCU read-side
1086 Realtime RCU implementations therefore use a counter-based
1087 approach where tasks in RCU read-side critical sections
1093 Give an example where Classic RCU's read-side
1103 RCU allows such interrupt-disabling to be dispensed with.
1104 Thus, without RCU, you pay the cost of disabling interrupts,
1105 and with RCU you don't.
1107 One can argue that the overhead of RCU in this
1110 the overhead of RCU is merely zero, and that replacing
1112 with the zero-overhead RCU scheme does not constitute
1122 If it is illegal to block in an RCU read-side
1128 critical sections, it permits preemption of RCU
1130 spinlocks blocking while in RCU read-side critical
1134 possible to use priority boosting to keep the RCU
1154 For more information, see http://www.rdrop.com/users/paulmck/RCU.