Lines Matching +full:side +full:- +full:by +full:- +full:side
3 What is RCU? -- "Read, Copy, Update"
21 during the 2.5 development effort that is optimized for read-mostly
40 :ref:`6. ANALOGY WITH READER-WRITER LOCKING <6_whatisRCU>`
47 Section 1, though most readers will profit by reading this section at
52 into the kernel source code. People who reason best by analogy should
58 everything, feel free to read the whole thing -- but if you are really
60 never need this document anyway. ;-)
65 ----------------
69 within a data structure (possibly by replacing them with references to
83 completed, either by blocking until they finish or by registering a
87 data items, and therefore cannot be disrupted by the reclamation phase.
94 b. Wait for all previous readers to complete their RCU read-side
103 use much lighter-weight synchronization, in some cases, absolutely no
104 synchronization at all. In contrast, in more conventional lock-based
105 schemes, readers must use heavy-weight synchronization in order to
107 This is because lock-based updaters typically update data items in place,
108 and must therefore exclude readers. In contrast, RCU-based updaters
114 and communications cache misses that are so expensive on present-day
117 In the three-step procedure shown above, the updater is performing both
120 in the Linux kernel's directory-entry cache (dcache). Even if the same
124 but RCU provides implicit low-overhead communication between readers
134 ---------------------------
156 Used by a reader to inform the reclaimer that the reader is
157 entering an RCU read-side critical section. It is illegal
158 to block while in an RCU read-side critical section, though
160 read-side critical sections. Any RCU-protected data structure
161 accessed during an RCU read-side critical section is guaranteed to
164 longer-term references to data structures.
170 Used by a reader to inform the reclaimer that the reader is
171 exiting an RCU read-side critical section. Note that RCU
172 read-side critical sections may be nested and/or overlapping.
179 code. It does this by blocking until all pre-existing RCU
180 read-side critical sections on all CPUs have completed.
182 any subsequent RCU read-side critical sections to complete.
186 ----------------- ------------------------- ---------------
195 read-side critical sections to complete, not necessarily for
199 **immediately** after the last pre-existing RCU read-side critical
207 to be useful in all but the most read-intensive situations,
213 after all ongoing RCU read-side critical sections have completed.
215 it is illegal to block or where update-side performance is
223 of denial-of-service attacks. Code using call_rcu() should limit
236 RCU-protected pointer, in order to safely communicate the change
238 evaluate to an rvalue, but it does execute any memory-barrier
242 pointers are protected by RCU and (2) the point at which a
245 the _rcu list-manipulation primitives such as list_add_rcu().
254 The reader uses rcu_dereference() to fetch an RCU-protected
258 later dereferencing. It also executes any needed memory-barrier
260 needs memory barriers within rcu_dereference() -- on other CPUs,
264 RCU-protected pointer to a local variable, then dereferences
268 return p->data;
273 return rcu_dereference(head.next)->data;
276 RCU-protected structure, using the local variable is of
282 Note that the value returned by rcu_dereference() is valid
283 only within the enclosing RCU read-side critical section [1]_.
289 x = p->address; /* BUG!!! */
291 y = p->data; /* BUG!!! */
294 Holding a reference from one RCU read-side critical section
296 one lock-based critical section to another! Similarly,
302 rcu_dereference() is to document which pointers are protected by
306 typically used indirectly, via the _rcu list-manipulation
310 of an RCU read-side critical section as long as the usage is
311 protected by locks acquired by the update-side code. This variant
318 by the caller. If the indicated protection is not provided,
322 .. [2] If the list_for_each_entry_rcu() instance might be used by
323 update-side code as well as by RCU readers, then an additional
327 invoked outside of an RCU read-side critical section and without
336 +--------+
337 +---------------------->| reader |---------+
338 | +--------+ |
344 +---------+ | |
345 | updater |<----------------+ |
346 +---------+ V
347 | +-----------+
348 +----------------------------------->| reclaimer |
349 +-----------+
362 above shows the most common one. On the updater side, the rcu_assign_pointer(),
364 flavors. However for protection (on the reader side), the primitives used vary
386 to remote denial-of-service attacks.
388 c. RCU applied to scheduler and interrupt/NMI-handler tasks.
396 -----------------------------------------------
399 global pointer to a dynamically allocated structure. More-typical
401 :ref:`arrayRCU.rst <array_rcu_doc>`, and :ref:`NMI-RCU.rst <NMI_rcu_doc>`.
415 * pointed to by gbl_foo, except that field "a" is replaced
435 new_fp->a = new_a;
455 retval = rcu_dereference(gbl_foo)->a;
462 - Use rcu_read_lock() and rcu_read_unlock() to guard RCU
463 read-side critical sections.
465 - Within an RCU read-side critical section, use rcu_dereference()
466 to dereference RCU-protected pointers.
468 - Use some solid scheme (such as locks or semaphores) to
471 - Use rcu_assign_pointer() to update an RCU-protected pointer.
477 - Use synchronize_rcu() **after** removing a data element from an
478 RCU-protected data structure, but **before** reclaiming/freeing
480 RCU read-side critical sections that might be referencing that
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
491 --------------------------------------------
495 long -- there might be other high-priority work to be done.
519 * pointed to by gbl_foo, except that field "a" is replaced
539 new_fp->a = new_a;
542 call_rcu(&old_fp->rcu, foo_reclaim);
551 foo_cleanup(fp->a);
557 struct, the type of the struct, and the pointed-to field within the
569 - Use call_rcu() **after** removing a data element from an
570 RCU-protected data structure in order to register a callback
572 read-side critical sections that might be referencing that
586 ------------------------------------------------
590 production-quality implementations in the Linux kernel. This section
593 resembles "classic" RCU. Both are way too simple for real-world use,
596 production-quality implementation, and see:
608 familiar locking primitives. Its overhead makes it a non-starter for
609 real-life use, as does its lack of scalability. It is also unsuitable
611 one read-side critical section to another. It also assumes recursive
612 reader-writer locks: If you try this with non-recursive locks, and
655 The rcu_read_lock() and rcu_read_unlock() primitive read-acquire
656 and release a global reader-writer lock. The synchronize_rcu()
657 primitive write-acquires this same lock, then releases it. This means
658 that once synchronize_rcu() exits, all RCU read-side critical sections
660 to have completed -- there is no way that synchronize_rcu() would have
661 been able to write-acquire the lock otherwise. The smp_mb__after_spinlock()
663 the "Memory-Barrier Guarantees" listed in:
667 It is possible to nest rcu_read_lock(), since reader-writer locks may
678 occur when using this algorithm in a real-world Linux
705 This is the great strength of classic RCU in a non-preemptive kernel:
706 read-side overhead is precisely zero, at least on non-Alpha CPUs.
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
749 6. ANALOGY WITH READER-WRITER LOCKING
750 --------------------------------------
753 RCU is analogous to reader-writer locking. The following unified
754 diff shows how closely related RCU and reader-writer locking can be.
757 @@ -5,5 +5,5 @@ struct el {
761 -rwlock_t listmutex;
765 @@ -13,15 +14,15 @@
769 - read_lock(&listmutex);
770 - list_for_each_entry(p, head, lp) {
773 if (p->key == key) {
774 *result = p->data;
775 - read_unlock(&listmutex);
780 - read_unlock(&listmutex);
785 @@ -29,15 +30,16 @@
789 - write_lock(&listmutex);
792 if (p->key == key) {
793 - list_del(&p->list);
794 - write_unlock(&listmutex);
795 + list_del_rcu(&p->list);
802 - write_unlock(&listmutex);
807 Or, for those who prefer a side-by-side listing::
828 8 if (p->key == key) { 8 if (p->key == key) {
829 9 *result = p->data; 9 *result = p->data;
846 7 if (p->key == key) { 7 if (p->key == key) {
847 8 list_del(&p->list); 8 list_del_rcu(&p->list);
858 Either way, the differences are quite small. Read-side locking moves
859 to rcu_read_lock() and rcu_read_unlock, update-side locking moves from
860 a reader-writer lock to a simple spinlock, and a synchronize_rcu()
863 However, there is one potential catch: the read-side and update-side
870 delete() can now block. If this is a problem, there is a callback-based
877 -------------------------
879 The RCU APIs are documented in docbook-format header comments in the
880 Linux-kernel source code, but it helps to have a full list of the
882 in docbook. Here is the list, by category.
989 All: lockdep-checked RCU-protected pointer access::
1006 b. What about the -rt patchset? If readers would need to block
1007 in an non-rt kernel, you need SRCU. If readers would block
1008 in a -rt kernel, but not in a non-rt kernel, SRCU is not
1009 necessary. (The -rt patchset turns spinlocks into sleeplocks,
1016 If so, RCU-sched is the only choice that will work for you.
1020 example, is your code subject to network-based denial-of-service
1022 for example, by using rcu_read_lock_bh().
1024 e. Is your workload too update-intensive for normal use of
1029 f. Do you need read-side critical sections that are respected
1031 user-mode execution, or on an offlined CPU? If so, SRCU is the
1042 ----------------------------
1046 occur when using this algorithm in a real-world Linux
1047 kernel? [Referring to the lock-based "toy" RCU
1057 2. CPU 1 enters synchronize_rcu(), write-acquiring
1078 consider task A in an RCU read-side critical section
1079 (thus read-holding rcu_gp_mutex), task B blocked
1080 attempting to write-acquire rcu_gp_mutex, and
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
1088 cannot be blocked by tasks executing synchronize_rcu().
1093 Give an example where Classic RCU's read-side
1097 Imagine a single-CPU system with a non-CONFIG_PREEMPT
1098 kernel where a routing table is used by process-context
1099 code, but can be updated by irq-context code (for example,
1100 by an "ICMP REDIRECT" packet). The usual way of handling
1101 this would be to have the process-context code disable
1103 RCU allows such interrupt-disabling to be dispensed with.
1108 case is negative with respect to the single-CPU
1109 interrupt-disabling approach. Others might argue that
1111 the positive overhead of the interrupt-disabling scheme
1112 with the zero-overhead RCU scheme does not constitute
1117 a synchronization primitive is a bit unexpected. ;-)
1122 If it is illegal to block in an RCU read-side
1129 read-side critical sections. It also permits
1130 spinlocks blocking while in RCU read-side critical
1141 a computer-operated cattle prod might arouse serious
1150 My thanks to the people who helped make this human-readable, including