Documentation/RCU/whatisRCU.rst

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 ----------------
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 ---------------------------
165 	This temporal primitive is used by a reader to inform the
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.
179 	This temporal primitives is used by a reader to inform the
180 	reclaimer that the reader is exiting an RCU read-side critical
181 	section.  Note that RCU read-side critical sections may be nested
188 	This temporal primitive marks the end of updater code and the
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
249 	opposed to temporal) macro.  It does not evaluate to an rvalue,
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 	                                         +-----------+
368 The RCU infrastructure observes the temporal sequence of rcu_read_lock(),
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
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
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
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