Lines Matching +full:non +full:- +full:protected
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>`
58 everything, feel free to read the whole thing -- but if you are really
60 never need this document anyway. ;-)
65 ----------------
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 ---------------------------
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.
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
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
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 +-----------+
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>`.
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.
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
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
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
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,
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