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
511 struct rcu_head rcu;
541 call_rcu(&old_fp->rcu, foo_reclaim);
548 struct foo *fp = container_of(rp, struct foo, rcu);
562 RCU distinction between updater, namely foo_update_a(), and reclaimer,
569 RCU-protected data structure in order to register a callback
570 function that will be invoked after the completion of all RCU
578 kfree_rcu(old_fp, rcu);
580 Again, see checklist.txt for additional rules governing the use of RCU.
584 5. WHAT ARE SOME SIMPLE IMPLEMENTATIONS OF RCU?
587 One of the nice things about RCU is that it has extremely simple "toy"
590 presents two such "toy" implementations of RCU, one that is implemented
592 resembles "classic" RCU. Both are way too simple for real-world use,
594 in getting a feel for how RCU works. See kernel/rcu/update.c for a
597 http://www.rdrop.com/users/paulmck/RCU
599 for papers describing the Linux kernel RCU implementation. The OLS'01
606 This section presents a "toy" RCU implementation that is based on
640 don't forget about them when submitting patches making use of RCU!]::
657 that once synchronize_rcu() exits, all RCU read-side critical sections
664 Documentation/RCU/Design/Requirements/Requirements.rst
668 from deadlock (an important property of RCU). The reason for this is
682 5B. "TOY" EXAMPLE #2: CLASSIC RCU argument
684 This section presents a "toy" RCU implementation that is based on
685 "classic RCU". It is also short on performance (but only for updates) and
704 This is the great strength of classic RCU in a non-preemptive kernel:
718 Remember that it is illegal to block while in an RCU read-side critical
720 that it must have completed all preceding RCU read-side critical sections.
722 RCU read-side critical sections will have completed.
726 that there are no RCU read-side critical sections holding a reference
732 Give an example where Classic RCU's read-side
740 If it is illegal to block in an RCU read-side
751 Although RCU can be used in many different ways, a very common use of
752 RCU is analogous to reader-writer locking. The following unified
753 diff shows how closely related RCU and reader-writer locking can be.
866 a single atomic update, converting to RCU will require special care.
868 Also, the presence of synchronize_rcu() means that the RCU version of
875 7. FULL LIST OF RCU APIs
878 The RCU APIs are documented in docbook-format header comments in the
883 RCU list traversal::
907 RCU pointer/list update::
931 RCU::
988 All: lockdep-checked RCU-protected pointer access::
999 However, given that there are no fewer than four families of RCU APIs
1014 or some other mechanism) as if they were explicit RCU readers?
1015 If so, RCU-sched is the only choice that will work for you.
1017 d. Do you need RCU grace periods to complete even in the face
1024 RCU, but inappropriate for other synchronization mechanisms?
1033 g. Otherwise, use RCU.
1035 Of course, this all assumes that you have determined that RCU is in fact
1046 kernel? [Referring to the lock-based "toy" RCU
1074 Even in the absence of deadlock, this RCU implementation
1077 consider task A in an RCU read-side critical section
1081 read_acquire rcu_gp_mutex. Task A's RCU read-side
1085 Realtime RCU implementations therefore use a counter-based
1086 approach where tasks in RCU read-side critical sections
1092 Give an example where Classic RCU's read-side
1102 RCU allows such interrupt-disabling to be dispensed with.
1103 Thus, without RCU, you pay the cost of disabling interrupts,
1104 and with RCU you don't.
1106 One can argue that the overhead of RCU in this
1109 the overhead of RCU is merely zero, and that replacing
1111 with the zero-overhead RCU scheme does not constitute
1121 If it is illegal to block in an RCU read-side
1127 critical sections, it permits preemption of RCU
1129 spinlocks blocking while in RCU read-side critical
1133 possible to use priority boosting to keep the RCU
1153 For more information, see http://www.rdrop.com/users/paulmck/RCU.