Lines Matching +full:negative +full:- +full:phase
3 What is RCU? -- "Read, Copy, Update"
21 …ries: Fundamentals https://www.linuxfoundation.org/webinars/unraveling-rcu-usage-mysteries
22 …Cases https://www.linuxfoundation.org/webinars/unraveling-rcu-usage-mysteries-additional-use-cases
28 during the 2.5 development effort that is optimized for read-mostly
47 :ref:`6. ANALOGY WITH READER-WRITER LOCKING <6_whatisRCU>`
67 everything, feel free to read the whole thing -- but if you are really
69 never need this document anyway. ;-)
74 ----------------
77 "reclamation" phases. The removal phase removes references to data items
80 The reason that it is safe to run the removal phase concurrently with
83 partially updated reference. The reclamation phase does the work of reclaiming
85 removal phase. Because reclaiming data items can disrupt any readers
86 concurrently referencing those data items, the reclamation phase must
90 updater to perform the removal phase immediately, and to defer the
91 reclamation phase until all readers active during the removal phase have
94 during the removal phase need be considered, because any reader starting
95 after the removal phase will be unable to gain a reference to the removed
96 data items, and therefore cannot be disrupted by the reclamation phase.
103 b. Wait for all previous readers to complete their RCU read-side
112 use much lighter-weight synchronization, in some cases, absolutely no
113 synchronization at all. In contrast, in more conventional lock-based
114 schemes, readers must use heavy-weight synchronization in order to
116 This is because lock-based updaters typically update data items in place,
117 and must therefore exclude readers. In contrast, RCU-based updaters
123 and communications cache misses that are so expensive on present-day
126 In the three-step procedure shown above, the updater is performing both
129 in the Linux kernel's directory-entry cache (dcache). Even if the same
133 but RCU provides implicit low-overhead communication between readers
143 ---------------------------
166 reclaimer that the reader is entering an RCU read-side critical
167 section. It is illegal to block while in an RCU read-side
169 can preempt RCU read-side critical sections. Any RCU-protected
170 data structure accessed during an RCU read-side critical section
173 with RCU to maintain longer-term references to data structures.
180 reclaimer that the reader is exiting an RCU read-side critical
181 section. Note that RCU read-side critical sections may be nested
190 all pre-existing RCU read-side critical sections on all CPUs
192 necessarily wait for any subsequent RCU read-side critical
197 ----------------- ------------------------- ---------------
206 read-side critical sections to complete, not necessarily for
210 **immediately** after the last pre-existing RCU read-side critical
218 to be useful in all but the most read-intensive situations,
224 argument which are invoked after all ongoing RCU read-side
227 or where update-side performance is critically important.
234 of denial-of-service attacks. Code using call_rcu() should limit
247 RCU-protected pointer, in order to safely communicate the change
250 but it does execute any memory-barrier instructions required
252 of a store-release operation.
258 the _rcu list-manipulation primitives such as list_add_rcu().
268 an RCU-protected pointer, which returns a value that may
272 executes any needed memory-barrier instructions for a given
274 within rcu_dereference() -- on other CPUs, it compiles to a
278 RCU-protected pointer to a local variable, then dereferences
282 return p->data;
287 return rcu_dereference(head.next)->data;
290 RCU-protected structure, using the local variable is of
297 only within the enclosing RCU read-side critical section [1]_.
303 x = p->address; /* BUG!!! */
305 y = p->data; /* BUG!!! */
308 Holding a reference from one RCU read-side critical section
310 one lock-based critical section to another! Similarly,
320 typically used indirectly, via the _rcu list-manipulation
324 of an RCU read-side critical section as long as the usage is
325 protected by locks acquired by the update-side code. This variant
337 update-side code as well as by RCU readers, then an additional
341 invoked outside of an RCU read-side critical section and without
350 +--------+
351 +---------------------->| reader |---------+
352 | +--------+ |
358 +---------+ | |
359 | updater |<----------------+ |
360 +---------+ V
361 | +-----------+
362 +----------------------------------->| reclaimer |
363 +-----------+
375 spatial changes via stores to and loads from the RCU-protected pointer in
403 to remote denial-of-service attacks.
405 c. RCU applied to scheduler and interrupt/NMI-handler tasks.
408 for specialized uses, but are relatively uncommon. The SRCU, RCU-Tasks,
409 RCU-Tasks-Rude, and RCU-Tasks-Trace have similar relationships among
415 -----------------------------------------------
418 global pointer to a dynamically allocated structure. More-typical
419 uses of RCU may be found in listRCU.rst, arrayRCU.rst, and NMI-RCU.rst.
453 new_fp->a = new_a;
473 retval = rcu_dereference(gbl_foo)->a;
480 - Use rcu_read_lock() and rcu_read_unlock() to guard RCU
481 read-side critical sections.
483 - Within an RCU read-side critical section, use rcu_dereference()
484 to dereference RCU-protected pointers.
486 - Use some solid design (such as locks or semaphores) to
489 - Use rcu_assign_pointer() to update an RCU-protected pointer.
495 - Use synchronize_rcu() **after** removing a data element from an
496 RCU-protected data structure, but **before** reclaiming/freeing
498 RCU read-side critical sections that might be referencing that
502 And again, more-typical uses of RCU may be found in listRCU.rst,
503 arrayRCU.rst, and NMI-RCU.rst.
508 --------------------------------------------
512 long -- there might be other high-priority work to be done.
555 new_fp->a = new_a;
558 call_rcu(&old_fp->rcu, foo_reclaim);
567 foo_cleanup(fp->a);
573 struct, the type of the struct, and the pointed-to field within the
585 - Use call_rcu() **after** removing a data element from an
586 RCU-protected data structure in order to register a callback
588 read-side critical sections that might be referencing that
597 If the occasional sleep is permitted, the single-argument form may
603 synchronize_rcu() in response to memory-allocation failure.
610 ------------------------------------------------
614 production-quality implementations in the Linux kernel. This section
617 resembles "classic" RCU. Both are way too simple for real-world use,
620 production-quality implementation, and see:
632 familiar locking primitives. Its overhead makes it a non-starter for
633 real-life use, as does its lack of scalability. It is also unsuitable
635 one read-side critical section to another. It also assumes recursive
636 reader-writer locks: If you try this with non-recursive locks, and
679 The rcu_read_lock() and rcu_read_unlock() primitive read-acquire
680 and release a global reader-writer lock. The synchronize_rcu()
681 primitive write-acquires this same lock, then releases it. This means
682 that once synchronize_rcu() exits, all RCU read-side critical sections
684 to have completed -- there is no way that synchronize_rcu() would have
685 been able to write-acquire the lock otherwise. The smp_mb__after_spinlock()
687 the "Memory-Barrier Guarantees" listed in:
691 It is possible to nest rcu_read_lock(), since reader-writer locks may
702 occur when using this algorithm in a real-world Linux
729 This is the great strength of classic RCU in a non-preemptive kernel:
730 read-side overhead is precisely zero, at least on non-Alpha CPUs.
743 Remember that it is illegal to block while in an RCU read-side critical
745 that it must have completed all preceding RCU read-side critical sections.
747 RCU read-side critical sections will have completed.
751 that there are no RCU read-side critical sections holding a reference
757 Give an example where Classic RCU's read-side
758 overhead is **negative**.
765 If it is illegal to block in an RCU read-side
773 6. ANALOGY WITH READER-WRITER LOCKING
774 --------------------------------------
777 RCU is analogous to reader-writer locking. The following unified
778 diff shows how closely related RCU and reader-writer locking can be.
781 @@ -5,5 +5,5 @@ struct el {
785 -rwlock_t listmutex;
789 @@ -13,15 +14,15 @@
793 - read_lock(&listmutex);
794 - list_for_each_entry(p, head, lp) {
797 if (p->key == key) {
798 *result = p->data;
799 - read_unlock(&listmutex);
804 - read_unlock(&listmutex);
809 @@ -29,15 +30,16 @@
813 - write_lock(&listmutex);
816 if (p->key == key) {
817 - list_del(&p->list);
818 - write_unlock(&listmutex);
819 + list_del_rcu(&p->list);
826 - write_unlock(&listmutex);
831 Or, for those who prefer a side-by-side listing::
852 8 if (p->key == key) { 8 if (p->key == key) {
853 9 *result = p->data; 9 *result = p->data;
870 7 if (p->key == key) { 7 if (p->key == key) {
871 8 list_del(&p->list); 8 list_del_rcu(&p->list);
882 Either way, the differences are quite small. Read-side locking moves
883 to rcu_read_lock() and rcu_read_unlock, update-side locking moves from
884 a reader-writer lock to a simple spinlock, and a synchronize_rcu()
887 However, there is one potential catch: the read-side and update-side
894 delete() can now block. If this is a problem, there is a callback-based
901 -----------------------------------
903 The reader-writer analogy (illustrated by the previous section) is not
909 values from changing, but does prevent changes to type -- particularly the
911 re-allocated for some other purpose. Once a type-safe reference to the
914 but with RCU the typical approach is to perform reads with SMP-aware
916 read-modify-write operations, and to provide the necessary ordering.
924 though a reference-count on that object has been temporarily increased.
934 - Copying out data that is guaranteed to be stable by the object's type.
935 - Using kref_get_unless_zero() or similar to get a longer-term
937 - Acquiring a spinlock in the object, and checking if the object still
953 reference-free spinlock acquisition completely unsafe. Therefore, when
956 including cache-friendly sequence locking.)
958 With traditional reference counting -- such as that implemented by the
959 kref library in Linux -- there is typically code that runs when the last
968 To see how to choose between these two analogies -- of RCU as a
969 reader-writer lock and RCU as a reference counting system -- it is useful
970 to reflect on the scale of the thing being protected. The reader-writer
971 lock analogy looks at larger multi-part objects such as a linked list
973 to, and removed from, the list. The reference-count analogy looks at
980 -------------------------
982 The RCU APIs are documented in docbook-format header comments in the
983 Linux-kernel source code, but it helps to have a full list of the
1075 RCU-Tasks::
1083 RCU-Tasks-Rude::
1091 RCU-Tasks-Trace::
1116 All: lockdep-checked RCU utility APIs::
1121 All: Unchecked RCU-protected pointer access::
1125 All: Unchecked RCU-protected pointer access with dereferencing prohibited::
1139 example, ftrace or BPF? If so, you need RCU-tasks,
1140 RCU-tasks-rude, and/or RCU-tasks-trace.
1142 c. What about the -rt patchset? If readers would need to block in
1143 an non-rt kernel, you need SRCU. If readers would block when
1144 acquiring spinlocks in a -rt kernel, but not in a non-rt kernel,
1145 SRCU is not necessary. (The -rt patchset turns spinlocks into
1152 If so, RCU-sched readers are the only choice that will work
1158 is your code subject to network-based denial-of-service attacks?
1163 f. Is your workload too update-intensive for normal use of
1168 g. Do you need read-side critical sections that are respected even
1170 from user-mode execution, or on an offlined CPU? If so, SRCU
1182 ----------------------------
1186 occur when using this algorithm in a real-world Linux
1187 kernel? [Referring to the lock-based "toy" RCU
1197 2. CPU 1 enters synchronize_rcu(), write-acquiring
1218 consider task A in an RCU read-side critical section
1219 (thus read-holding rcu_gp_mutex), task B blocked
1220 attempting to write-acquire rcu_gp_mutex, and
1222 read_acquire rcu_gp_mutex. Task A's RCU read-side
1226 Realtime RCU implementations therefore use a counter-based
1227 approach where tasks in RCU read-side critical sections
1233 Give an example where Classic RCU's read-side
1234 overhead is **negative**.
1237 Imagine a single-CPU system with a non-CONFIG_PREEMPTION
1238 kernel where a routing table is used by process-context
1239 code, but can be updated by irq-context code (for example,
1241 this would be to have the process-context code disable
1243 RCU allows such interrupt-disabling to be dispensed with.
1248 case is negative with respect to the single-CPU
1249 interrupt-disabling approach. Others might argue that
1251 the positive overhead of the interrupt-disabling scheme
1252 with the zero-overhead RCU scheme does not constitute
1253 negative overhead.
1256 even the theoretical possibility of negative overhead for
1257 a synchronization primitive is a bit unexpected. ;-)
1262 If it is illegal to block in an RCU read-side
1269 read-side critical sections. It also permits
1270 spinlocks blocking while in RCU read-side critical
1281 a computer-operated cattle prod might arouse serious
1290 My thanks to the people who helped make this human-readable, including