code:
.. SPDX-License-Identifier: GPL-2.0

================================
Review Checklist for RCU Patches
================================

This document contains a checklist for producing and reviewing patches
that make use of RCU.  Violating any of the rules listed below will
result in the same sorts of problems that leaving out a locking primitive
would cause.  This list is based on experiences reviewing such patches
over a rather long period of time, but improvements are always welcome!

0.	Is RCU being applied to a read-mostly situation?  If the data
	structure is updated more than about 10% of the time, then you
	should strongly consider some other approach, unless detailed
	performance measurements show that RCU is nonetheless the right
	tool for the job.  Yes, RCU does reduce read-side overhead by
	increasing write-side overhead, which is exactly why normal uses
	of RCU will do much more reading than updating.

	Another exception is where performance is not an issue, and RCU
	provides a simpler implementation.  An example of this situation
	is the dynamic NMI code in the Linux 2.6 kernel, at least on
	architectures where NMIs are rare.

	Yet another exception is where the low real-time latency of RCU's
	read-side primitives is critically important.

	One final exception is where RCU readers are used to prevent
	the ABA problem (https://en.wikipedia.org/wiki/ABA_problem)
	for lockless updates.  This does result in the mildly
	counter-intuitive situation where rcu_read_lock() and
	rcu_read_unlock() are used to protect updates, however, this
	approach can provide the same simplifications to certain types
	of lockless algorithms that garbage collectors do.

1.	Does the update code have proper mutual exclusion?

	RCU does allow *readers* to run (almost) naked, but *writers* must
	still use some sort of mutual exclusion, such as:

	a.	locking,
	b.	atomic operations, or
	c.	restricting updates to a single task.

	If you choose #b, be prepared to describe how you have handled
	memory barriers on weakly ordered machines (pretty much all of
	them -- even x86 allows later loads to be reordered to precede
	earlier stores), and be prepared to explain why this added
	complexity is worthwhile.  If you choose #c, be prepared to
	explain how this single task does not become a major bottleneck
	on large systems (for example, if the task is updating information
	relating to itself that other tasks can read, there by definition
	can be no bottleneck).	Note that the definition of "large" has
	changed significantly:	Eight CPUs was "large" in the year 2000,
	but a hundred CPUs was unremarkable in 2017.

2.	Do the RCU read-side critical sections make proper use of
	rcu_read_lock() and friends?  These primitives are needed
	to prevent grace periods from ending prematurely, which
	could result in data being unceremoniously freed out from
	under your read-side code, which can greatly increase the
	actuarial risk of your kernel.

	As a rough rule of thumb, any dereference of an RCU-protected
	pointer must be covered by rcu_read_lock(), rcu_read_lock_bh(),
	rcu_read_lock_sched(), or by the appropriate update-side lock.
	Explicit disabling of preemption (preempt_disable(), for example)
	can serve as rcu_read_lock_sched(), but is less readable and
	prevents lockdep from detecting locking issues.

	Please not that you *cannot* rely on code known to be built
	only in non-preemptible kernels.  Such code can and will break,
	especially in kernels built with CONFIG_PREEMPT_COUNT=y.

	Letting RCU-protected pointers "leak" out of an RCU read-side
	critical section is every bit as bad as letting them leak out
	from under a lock.  Unless, of course, you have arranged some
	other means of protection, such as a lock or a reference count
	*before* letting them out of the RCU read-side critical section.

3.	Does the update code tolerate concurrent accesses?

	The whole point of RCU is to permit readers to run without
	any locks or atomic operations.  This means that readers will
	be running while updates are in progress.  There are a number
	of ways to handle this concurrency, depending on the situation:

	a.	Use the RCU variants of the list and hlist update
		primitives to add, remove, and replace elements on
		an RCU-protected list.	Alternatively, use the other
		RCU-protected data structures that have been added to
		the Linux kernel.

		This is almost always the best approach.

	b.	Proceed as in (a) above, but also maintain per-element
		locks (that are acquired by both readers and writers)
		that guard per-element state.  Fields that the readers
		refrain from accessing can be guarded by some other lock
		acquired only by updaters, if desired.

		This also works quite well.

	c.	Make updates appear atomic to readers.	For example,
		pointer updates to properly aligned fields will
		appear atomic, as will individual atomic primitives.
		Sequences of operations performed under a lock will *not*
		appear to be atomic to RCU readers, nor will sequences
		of multiple atomic primitives.	One alternative is to
		move multiple individual fields to a separate structure,
		thus solving the multiple-field problem by imposing an
		additional level of indirection.

		This can work, but is starting to get a bit tricky.

	d.	Carefully order the updates and the reads so that readers
		see valid data at all phases of the update.  This is often
		more difficult than it sounds, especially given modern
		CPUs' tendency to reorder memory references.  One must
		usually liberally sprinkle memory-ordering operations
		through the code, making it difficult to understand and
		to test.  Where it works, it is better to use things
		like smp_store_release() and smp_load_acquire(), but in
		some cases the smp_mb() full memory barrier is required.

		As noted earlier, it is usually better to group the
		changing data into a separate structure, so that the
		change may be made to appear atomic by updating a pointer
		to reference a new structure containing updated values.

4.	Weakly ordered CPUs pose special challenges.  Almost all CPUs
	are weakly ordered -- even x86 CPUs allow later loads to be
	reordered to precede earlier stores.  RCU code must take all of
	the following measures to prevent memory-corruption problems:

	a.	Readers must maintain proper ordering of their memory
		accesses.  The rcu_dereference() primitive ensures that
		the CPU picks up the pointer before it picks up the data
		that the pointer points to.  This really is necessary
		on Alpha CPUs.

		The rcu_dereference() primitive is also an excellent
		documentation aid, letting the person reading the
		code know exactly which pointers are protected by RCU.
		Please note that compilers can also reorder code, and
		they are becoming increasingly aggressive about doing
		just that.  The rcu_dereference() primitive therefore also
		prevents destructive compiler optimizations.  However,
		with a bit of devious creativity, it is possible to
		mishandle the return value from rcu_dereference().
		Please see rcu_dereference.rst for more information.

		The rcu_dereference() primitive is used by the
		various "_rcu()" list-traversal primitives, such
		as the list_for_each_entry_rcu().  Note that it is
		perfectly legal (if redundant) for update-side code to
		use rcu_dereference() and the "_rcu()" list-traversal
		primitives.  This is particularly useful in code that
		is common to readers and updaters.  However, lockdep
		will complain if you access rcu_dereference() outside
		of an RCU read-side critical section.  See lockdep.rst
		to learn what to do about this.

		Of course, neither rcu_dereference() nor the "_rcu()"
		list-traversal primitives can substitute for a good
		concurrency design coordinating among multiple updaters.

	b.	If the list macros are being used, the list_add_tail_rcu()
		and list_add_rcu() primitives must be used in order
		to prevent weakly ordered machines from misordering
		structure initialization and pointer planting.
		Similarly, if the hlist macros are being used, the
		hlist_add_head_rcu() primitive is required.

	c.	If the list macros are being used, the list_del_rcu()
		primitive must be used to keep list_del()'s pointer
		poisoning from inflicting toxic effects on concurrent
		readers.  Similarly, if the hlist macros are being used,
		the hlist_del_rcu() primitive is required.

		The list_replace_rcu() and hlist_replace_rcu() primitives
		may be used to replace an old structure with a new one
		in their respective types of RCU-protected lists.

	d.	Rules similar to (4b) and (4c) apply to the "hlist_nulls"
		type of RCU-protected linked lists.

	e.	Updates must ensure that initialization of a given
		structure happens before pointers to that structure are
		publicized.  Use the rcu_assign_pointer() primitive
		when publicizing a pointer to a structure that can
		be traversed by an RCU read-side critical section.

5.	If any of call_rcu(), call_srcu(), call_rcu_tasks(),
	call_rcu_tasks_rude(), or call_rcu_tasks_trace() is used,
	the callback function may be invoked from softirq context,
	and in any case with bottom halves disabled.  In particular,
	this callback function cannot block.  If you need the callback
	to block, run that code in a workqueue handler scheduled from
	the callback.  The queue_rcu_work() function does this for you
	in the case of call_rcu().

6.	Since synchronize_rcu() can block, it cannot be called
	from any sort of irq context.  The same rule applies
	for synchronize_srcu(), synchronize_rcu_expedited(),
	synchronize_srcu_expedited(), synchronize_rcu_tasks(),
	synchronize_rcu_tasks_rude(), and synchronize_rcu_tasks_trace().

	The expedited forms of these primitives have the same semantics
	as the non-expedited forms, but expediting is more CPU intensive.
	Use of the expedited primitives should be restricted to rare
	configuration-change operations that would not normally be
	undertaken while a real-time workload is running.  Note that
	IPI-sensitive real-time workloads can use the rcupdate.rcu_normal
	kernel boot parameter to completely disable expedited grace
	periods, though this might have performance implications.

	In particular, if you find yourself invoking one of the expedited
	primitives repeatedly in a loop, please do everyone a favor:
	Restructure your code so that it batches the updates, allowing
	a single non-expedited primitive to cover the entire batch.
	This will very likely be faster than the loop containing the
	expedited primitive, and will be much much easier on the rest
	of the system, especially to real-time workloads running on the
	rest of the system.  Alternatively, instead use asynchronous
	primitives such as call_rcu().

7.	As of v4.20, a given kernel implements only one RCU flavor, which
	is RCU-sched for PREEMPTION=n and RCU-preempt for PREEMPTION=y.
	If the updater uses call_rcu() or synchronize_rcu(), then
	the corresponding readers may use:  (1) rcu_read_lock() and
	rcu_read_unlock(), (2) any pair of primitives that disables
	and re-enables softirq, for example, rcu_read_lock_bh() and
	rcu_read_unlock_bh(), or (3) any pair of primitives that disables
	and re-enables preemption, for example, rcu_read_lock_sched() and
	rcu_read_unlock_sched().  If the updater uses synchronize_srcu()
	or call_srcu(), then the corresponding readers must use
	srcu_read_lock() and srcu_read_unlock(), and with the same
	srcu_struct.  The rules for the expedited RCU grace-period-wait
	primitives are the same as for their non-expedited counterparts.

	If the updater uses call_rcu_tasks() or synchronize_rcu_tasks(),
	then the readers must refrain from executing voluntary
	context switches, that is, from blocking.  If the updater uses
	call_rcu_tasks_trace() or synchronize_rcu_tasks_trace(), then
	the corresponding readers must use rcu_read_lock_trace() and
	rcu_read_unlock_trace().  If an updater uses call_rcu_tasks_rude()
	or synchronize_rcu_tasks_rude(), then the corresponding readers
	must use anything that disables preemption, for example,
	preempt_disable() and preempt_enable().

	Mixing things up will result in confusion and broken kernels, and
	has even resulted in an exploitable security issue.  Therefore,
	when using non-obvious pairs of primitives, commenting is
	of course a must.  One example of non-obvious pairing is
	the XDP feature in networking, which calls BPF programs from
	network-driver NAPI (softirq) context.	BPF relies heavily on RCU
	protection for its data structures, but because the BPF program
	invocation happens entirely within a single local_bh_disable()
	section in a NAPI poll cycle, this usage is safe.  The reason
	that this usage is safe is that readers can use anything that
	disables BH when updaters use call_rcu() or synchronize_rcu().

8.	Although synchronize_rcu() is slower than is call_rcu(),
	it usually results in simpler code.  So, unless update
	performance is critically important, the updaters cannot block,
	or the latency of synchronize_rcu() is visible from userspace,
	synchronize_rcu() should be used in preference to call_rcu().
	Furthermore, kfree_rcu() and kvfree_rcu() usually result
	in even simpler code than does synchronize_rcu() without
	synchronize_rcu()'s multi-millisecond latency.	So please take
	advantage of kfree_rcu()'s and kvfree_rcu()'s "fire and forget"
	memory-freeing capabilities where it applies.

	An especially important property of the synchronize_rcu()
	primitive is that it automatically self-limits: if grace periods
	are delayed for whatever reason, then the synchronize_rcu()
	primitive will correspondingly delay updates.  In contrast,
	code using call_rcu() should explicitly limit update rate in
	cases where grace periods are delayed, as failing to do so can
	result in excessive realtime latencies or even OOM conditions.

	Ways of gaining this self-limiting property when using call_rcu(),
	kfree_rcu(), or kvfree_rcu() include:

	a.	Keeping a count of the number of data-structure elements
		used by the RCU-protected data structure, including
		those waiting for a grace period to elapse.  Enforce a
		limit on this number, stalling updates as needed to allow
		previously deferred frees to complete.	Alternatively,
		limit only the number awaiting deferred free rather than
		the total number of elements.

		One way to stall the updates is to acquire the update-side
		mutex.	(Don't try this with a spinlock -- other CPUs
		spinning on the lock could prevent the grace period
		from ever ending.)  Another way to stall the updates
		is for the updates to use a wrapper function around
		the memory allocator, so that this wrapper function
		simulates OOM when there is too much memory awaiting an
		RCU grace period.  There are of course many other
		variations on this theme.

	b.	Limiting update rate.  For example, if updates occur only
		once per hour, then no explicit rate limiting is
		required, unless your system is already badly broken.
		Older versions of the dcache subsystem take this approach,
		guarding updates with a global lock, limiting their rate.

	c.	Trusted update -- if updates can only be done manually by
		superuser or some other trusted user, then it might not
		be necessary to automatically limit them.  The theory
		here is that superuser already has lots of ways to crash
		the machine.

	d.	Periodically invoke rcu_barrier(), permitting a limited
		number of updates per grace period.

	The same cautions apply to call_srcu(), call_rcu_tasks(),
	call_rcu_tasks_rude(), and call_rcu_tasks_trace().  This is
	why there is an srcu_barrier(), rcu_barrier_tasks(),
	rcu_barrier_tasks_rude(), and rcu_barrier_tasks_rude(),
	respectively.

	Note that although these primitives do take action to avoid
	memory exhaustion when any given CPU has too many callbacks,
	a determined user or administrator can still exhaust memory.
	This is especially the case if a system with a large number of
	CPUs has been configured to offload all of its RCU callbacks onto
	a single CPU, or if the system has relatively little free memory.

9.	All RCU list-traversal primitives, which include
	rcu_dereference(), list_for_each_entry_rcu(), and
	list_for_each_safe_rcu(), must be either within an RCU read-side
	critical section or must be protected by appropriate update-side
	locks.	RCU read-side critical sections are delimited by
	rcu_read_lock() and rcu_read_unlock(), or by similar primitives
	such as rcu_read_lock_bh() and rcu_read_unlock_bh(), in which
	case the matching rcu_dereference() primitive must be used in
	order to keep lockdep happy, in this case, rcu_dereference_bh().

	The reason that it is permissible to use RCU list-traversal
	primitives when the update-side lock is held is that doing so
	can be quite helpful in reducing code bloat when common code is
	shared between readers and updaters.  Additional primitives
	are provided for this case, as discussed in lockdep.rst.

	One exception to this rule is when data is only ever added to
	the linked data structure, and is never removed during any
	time that readers might be accessing that structure.  In such
	cases, READ_ONCE() may be used in place of rcu_dereference()
	and the read-side markers (rcu_read_lock() and rcu_read_unlock(),
	for example) may be omitted.

10.	Conversely, if you are in an RCU read-side critical section,
	and you don't hold the appropriate update-side lock, you *must*
	use the "_rcu()" variants of the list macros.  Failing to do so
	will break Alpha, cause aggressive compilers to generate bad code,
	and confuse people trying to understand your code.

11.	Any lock acquired by an RCU callback must be acquired elsewhere
	with softirq disabled, e.g., via spin_lock_bh().  Failing to
	disable softirq on a given acquisition of that lock will result
	in deadlock as soon as the RCU softirq handler happens to run
	your RCU callback while interrupting that acquisition's critical
	section.

12.	RCU callbacks can be and are executed in parallel.  In many cases,
	the callback code simply wrappers around kfree(), so that this
	is not an issue (or, more accurately, to the extent that it is
	an issue, the memory-allocator locking handles it).  However,
	if the callbacks do manipulate a shared data structure, they
	must use whatever locking or other synchronization is required
	to safely access and/or modify that data structure.

	Do not assume that RCU callbacks will be executed on the same
	CPU that executed the corresponding call_rcu() or call_srcu().
	For example, if a given CPU goes offline while having an RCU
	callback pending, then that RCU callback will execute on some
	surviving CPU.	(If this was not the case, a self-spawning RCU
	callback would prevent the victim CPU from ever going offline.)
	Furthermore, CPUs designated by rcu_nocbs= might well *always*
	have their RCU callbacks executed on some other CPUs, in fact,
	for some  real-time workloads, this is the whole point of using
	the rcu_nocbs= kernel boot parameter.

	In addition, do not assume that callbacks queued in a given order
	will be invoked in that order, even if they all are queued on the
	same CPU.  Furthermore, do not assume that same-CPU callbacks will
	be invoked serially.  For example, in recent kernels, CPUs can be
	switched between offloaded and de-offloaded callback invocation,
	and while a given CPU is undergoing such a switch, its callbacks
	might be concurrently invoked by that CPU's softirq handler and
	that CPU's rcuo kthread.  At such times, that CPU's callbacks
	might be executed both concurrently and out of order.

13.	Unlike most flavors of RCU, it *is* permissible to block in an
	SRCU read-side critical section (demarked by srcu_read_lock()
	and srcu_read_unlock()), hence the "SRCU": "sleepable RCU".
	Please note that if you don't need to sleep in read-side critical
	sections, you should be using RCU rather than SRCU, because RCU
	is almost always faster and easier to use than is SRCU.

	Also unlike other forms of RCU, explicit initialization and
	cleanup is required either at build time via DEFINE_SRCU()
	or DEFINE_STATIC_SRCU() or at runtime via init_srcu_struct()
	and cleanup_srcu_struct().  These last two are passed a
	"struct srcu_struct" that defines the scope of a given
	SRCU domain.  Once initialized, the srcu_struct is passed
	to srcu_read_lock(), srcu_read_unlock() synchronize_srcu(),
	synchronize_srcu_expedited(), and call_srcu().	A given
	synchronize_srcu() waits only for SRCU read-side critical
	sections governed by srcu_read_lock() and srcu_read_unlock()
	calls that have been passed the same srcu_struct.  This property
	is what makes sleeping read-side critical sections tolerable --
	a given subsystem delays only its own updates, not those of other
	subsystems using SRCU.	Therefore, SRCU is less prone to OOM the
	system than RCU would be if RCU's read-side critical sections
	were permitted to sleep.

	The ability to sleep in read-side critical sections does not
	come for free.	First, corresponding srcu_read_lock() and
	srcu_read_unlock() calls must be passed the same srcu_struct.
	Second, grace-period-detection overhead is amortized only
	over those updates sharing a given srcu_struct, rather than
	being globally amortized as they are for other forms of RCU.
	Therefore, SRCU should be used in preference to rw_semaphore
	only in extremely read-intensive situations, or in situations
	requiring SRCU's read-side deadlock immunity or low read-side
	realtime latency.  You should also consider percpu_rw_semaphore
	when you need lightweight readers.

	SRCU's expedited primitive (synchronize_srcu_expedited())
	never sends IPIs to other CPUs, so it is easier on
	real-time workloads than is synchronize_rcu_expedited().

	It is also permissible to sleep in RCU Tasks Trace read-side
	critical, which are delimited by rcu_read_lock_trace() and
	rcu_read_unlock_trace().  However, this is a specialized flavor
	of RCU, and you should not use it without first checking with
	its current users.  In most cases, you should instead use SRCU.

	Note that rcu_assign_pointer() relates to SRCU just as it does to
	other forms of RCU, but instead of rcu_dereference() you should
	use srcu_dereference() in order to avoid lockdep splats.

14.	The whole point of call_rcu(), synchronize_rcu(), and friends
	is to wait until all pre-existing readers have finished before
	carrying out some otherwise-destructive operation.  It is
	therefore critically important to *first* remove any path
	that readers can follow that could be affected by the
	destructive operation, and *only then* invoke call_rcu(),
	synchronize_rcu(), or friends.

	Because these primitives only wait for pre-existing readers, it
	is the caller's responsibility to guarantee that any subsequent
	readers will execute safely.

15.	The various RCU read-side primitives do *not* necessarily contain
	memory barriers.  You should therefore plan for the CPU
	and the compiler to freely reorder code into and out of RCU
	read-side critical sections.  It is the responsibility of the
	RCU update-side primitives to deal with this.

	For SRCU readers, you can use smp_mb__after_srcu_read_unlock()
	immediately after an srcu_read_unlock() to get a full barrier.

16.	Use CONFIG_PROVE_LOCKING, CONFIG_DEBUG_OBJECTS_RCU_HEAD, and the
	__rcu sparse checks to validate your RCU code.	These can help
	find problems as follows:

	CONFIG_PROVE_LOCKING:
		check that accesses to RCU-protected data structures
		are carried out under the proper RCU read-side critical
		section, while holding the right combination of locks,
		or whatever other conditions are appropriate.

	CONFIG_DEBUG_OBJECTS_RCU_HEAD:
		check that you don't pass the same object to call_rcu()
		(or friends) before an RCU grace period has elapsed
		since the last time that you passed that same object to
		call_rcu() (or friends).

	__rcu sparse checks:
		tag the pointer to the RCU-protected data structure
		with __rcu, and sparse will warn you if you access that
		pointer without the services of one of the variants
		of rcu_dereference().

	These debugging aids can help you find problems that are
	otherwise extremely difficult to spot.

17.	If you pass a callback function defined within a module to one of
	call_rcu(), call_srcu(), call_rcu_tasks(), call_rcu_tasks_rude(),
	or call_rcu_tasks_trace(), then it is necessary to wait for all
	pending callbacks to be invoked before unloading that module.
	Note that it is absolutely *not* sufficient to wait for a grace
	period!  For example, synchronize_rcu() implementation is *not*
	guaranteed to wait for callbacks registered on other CPUs via
	call_rcu().  Or even on the current CPU if that CPU recently
	went offline and came back online.

	You instead need to use one of the barrier functions:

	-	call_rcu() -> rcu_barrier()
	-	call_srcu() -> srcu_barrier()
	-	call_rcu_tasks() -> rcu_barrier_tasks()
	-	call_rcu_tasks_rude() -> rcu_barrier_tasks_rude()
	-	call_rcu_tasks_trace() -> rcu_barrier_tasks_trace()

	However, these barrier functions are absolutely *not* guaranteed
	to wait for a grace period.  For example, if there are no
	call_rcu() callbacks queued anywhere in the system, rcu_barrier()
	can and will return immediately.

	So if you need to wait for both a grace period and for all
	pre-existing callbacks, you will need to invoke both functions,
	with the pair depending on the flavor of RCU:

	-	Either synchronize_rcu() or synchronize_rcu_expedited(),
		together with rcu_barrier()
	-	Either synchronize_srcu() or synchronize_srcu_expedited(),
		together with and srcu_barrier()
	-	synchronize_rcu_tasks() and rcu_barrier_tasks()
	-	synchronize_tasks_rude() and rcu_barrier_tasks_rude()
	-	synchronize_tasks_trace() and rcu_barrier_tasks_trace()

	If necessary, you can use something like workqueues to execute
	the requisite pair of functions concurrently.

	See rcubarrier.rst for more information.


code:
.. SPDX-License-Identifier: GPL-2.0

.. _rcu_concepts:

============
RCU concepts
============

.. toctree::
   :maxdepth: 3

   checklist
   lockdep
   lockdep-splat
   rcubarrier
   rcu_dereference
   whatisRCU
   rcu
   rculist_nulls
   rcuref
   torture
   stallwarn
   listRCU
   NMI-RCU
   UP

   Design/Memory-Ordering/Tree-RCU-Memory-Ordering
   Design/Expedited-Grace-Periods/Expedited-Grace-Periods
   Design/Requirements/Requirements
   Design/Data-Structures/Data-Structures

.. only:: subproject and html

   Indices
   =======

   * :ref:`genindex`

repo_name: angery/linux


code:
.. _list_rcu_doc:

Using RCU to Protect Read-Mostly Linked Lists
=============================================

One of the most common uses of RCU is protecting read-mostly linked lists
(``struct list_head`` in list.h).  One big advantage of this approach is
that all of the required memory ordering is provided by the list macros.
This document describes several list-based RCU use cases.

Example 1: Read-mostly list: Deferred Destruction
-------------------------------------------------

A widely used usecase for RCU lists in the kernel is lockless iteration over
all processes in the system. ``task_struct::tasks`` represents the list node that
links all the processes. The list can be traversed in parallel to any list
additions or removals.

The traversal of the list is done using ``for_each_process()`` which is defined
by the 2 macros::

	#define next_task(p) \
		list_entry_rcu((p)->tasks.next, struct task_struct, tasks)

	#define for_each_process(p) \
		for (p = &init_task ; (p = next_task(p)) != &init_task ; )

The code traversing the list of all processes typically looks like::

	rcu_read_lock();
	for_each_process(p) {
		/* Do something with p */
	}
	rcu_read_unlock();

The simplified and heavily inlined code for removing a process from a
task list is::

	void release_task(struct task_struct *p)
	{
		write_lock(&tasklist_lock);
		list_del_rcu(&p->tasks);
		write_unlock(&tasklist_lock);
		call_rcu(&p->rcu, delayed_put_task_struct);
	}

When a process exits, ``release_task()`` calls ``list_del_rcu(&p->tasks)``
via __exit_signal() and __unhash_process() under ``tasklist_lock``
writer lock protection.  The list_del_rcu() invocation removes
the task from the list of all tasks. The ``tasklist_lock``
prevents concurrent list additions/removals from corrupting the
list. Readers using ``for_each_process()`` are not protected with the
``tasklist_lock``. To prevent readers from noticing changes in the list
pointers, the ``task_struct`` object is freed only after one or more
grace periods elapse, with the help of call_rcu(), which is invoked via
put_task_struct_rcu_user(). This deferring of destruction ensures that
any readers traversing the list will see valid ``p->tasks.next`` pointers
and deletion/freeing can happen in parallel with traversal of the list.
This pattern is also called an **existence lock**, since RCU refrains
from invoking the delayed_put_task_struct() callback function until
all existing readers finish, which guarantees that the ``task_struct``
object in question will remain in existence until after the completion
of all RCU readers that might possibly have a reference to that object.

Example 2: Read-Side Action Taken Outside of Lock: No In-Place Updates
----------------------------------------------------------------------

Some reader-writer locking use cases compute a value while holding
the read-side lock, but continue to use that value after that lock is
released.  These use cases are often good candidates for conversion
to RCU.  One prominent example involves network packet routing.
Because the packet-routing data tracks the state of equipment outside
of the computer, it will at times contain stale data.  Therefore, once
the route has been computed, there is no need to hold the routing table
static during transmission of the packet.  After all, you can hold the
routing table static all you want, but that won't keep the external
Internet from changing, and it is the state of the external Internet
that really matters.  In addition, routing entries are typically added
or deleted, rather than being modified in place.  This is a rare example
of the finite speed of light and the non-zero size of atoms actually
helping make synchronization be lighter weight.

A straightforward example of this type of RCU use case may be found in
the system-call auditing support.  For example, a reader-writer locked
implementation of ``audit_filter_task()`` might be as follows::

	static enum audit_state audit_filter_task(struct task_struct *tsk, char **key)
	{
		struct audit_entry *e;
		enum audit_state   state;

		read_lock(&auditsc_lock);
		/* Note: audit_filter_mutex held by caller. */
		list_for_each_entry(e, &audit_tsklist, list) {
			if (audit_filter_rules(tsk, &e->rule, NULL, &state)) {
				if (state == AUDIT_STATE_RECORD)
					*key = kstrdup(e->rule.filterkey, GFP_ATOMIC);
				read_unlock(&auditsc_lock);
				return state;
			}
		}
		read_unlock(&auditsc_lock);
		return AUDIT_BUILD_CONTEXT;
	}

Here the list is searched under the lock, but the lock is dropped before
the corresponding value is returned.  By the time that this value is acted
on, the list may well have been modified.  This makes sense, since if
you are turning auditing off, it is OK to audit a few extra system calls.

This means that RCU can be easily applied to the read side, as follows::

	static enum audit_state audit_filter_task(struct task_struct *tsk, char **key)
	{
		struct audit_entry *e;
		enum audit_state   state;

		rcu_read_lock();
		/* Note: audit_filter_mutex held by caller. */
		list_for_each_entry_rcu(e, &audit_tsklist, list) {
			if (audit_filter_rules(tsk, &e->rule, NULL, &state)) {
				if (state == AUDIT_STATE_RECORD)
					*key = kstrdup(e->rule.filterkey, GFP_ATOMIC);
				rcu_read_unlock();
				return state;
			}
		}
		rcu_read_unlock();
		return AUDIT_BUILD_CONTEXT;
	}

The read_lock() and read_unlock() calls have become rcu_read_lock()
and rcu_read_unlock(), respectively, and the list_for_each_entry()
has become list_for_each_entry_rcu().  The **_rcu()** list-traversal
primitives add READ_ONCE() and diagnostic checks for incorrect use
outside of an RCU read-side critical section.

The changes to the update side are also straightforward. A reader-writer lock
might be used as follows for deletion and insertion in these simplified
versions of audit_del_rule() and audit_add_rule()::

	static inline int audit_del_rule(struct audit_rule *rule,
					 struct list_head *list)
	{
		struct audit_entry *e;

		write_lock(&auditsc_lock);
		list_for_each_entry(e, list, list) {
			if (!audit_compare_rule(rule, &e->rule)) {
				list_del(&e->list);
				write_unlock(&auditsc_lock);
				return 0;
			}
		}
		write_unlock(&auditsc_lock);
		return -EFAULT;		/* No matching rule */
	}

	static inline int audit_add_rule(struct audit_entry *entry,
					 struct list_head *list)
	{
		write_lock(&auditsc_lock);
		if (entry->rule.flags & AUDIT_PREPEND) {
			entry->rule.flags &= ~AUDIT_PREPEND;
			list_add(&entry->list, list);
		} else {
			list_add_tail(&entry->list, list);
		}
		write_unlock(&auditsc_lock);
		return 0;
	}

Following are the RCU equivalents for these two functions::

	static inline int audit_del_rule(struct audit_rule *rule,
					 struct list_head *list)
	{
		struct audit_entry *e;

		/* No need to use the _rcu iterator here, since this is the only
		 * deletion routine. */
		list_for_each_entry(e, list, list) {
			if (!audit_compare_rule(rule, &e->rule)) {
				list_del_rcu(&e->list);
				call_rcu(&e->rcu, audit_free_rule);
				return 0;
			}
		}
		return -EFAULT;		/* No matching rule */
	}

	static inline int audit_add_rule(struct audit_entry *entry,
					 struct list_head *list)
	{
		if (entry->rule.flags & AUDIT_PREPEND) {
			entry->rule.flags &= ~AUDIT_PREPEND;
			list_add_rcu(&entry->list, list);
		} else {
			list_add_tail_rcu(&entry->list, list);
		}
		return 0;
	}

Normally, the write_lock() and write_unlock() would be replaced by a
spin_lock() and a spin_unlock(). But in this case, all callers hold
``audit_filter_mutex``, so no additional locking is required. The
auditsc_lock can therefore be eliminated, since use of RCU eliminates the
need for writers to exclude readers.

The list_del(), list_add(), and list_add_tail() primitives have been
replaced by list_del_rcu(), list_add_rcu(), and list_add_tail_rcu().
The **_rcu()** list-manipulation primitives add memory barriers that are
needed on weakly ordered CPUs.  The list_del_rcu() primitive omits the
pointer poisoning debug-assist code that would otherwise cause concurrent
readers to fail spectacularly.

So, when readers can tolerate stale data and when entries are either added or
deleted, without in-place modification, it is very easy to use RCU!

Example 3: Handling In-Place Updates
------------------------------------

The system-call auditing code does not update auditing rules in place.  However,
if it did, the reader-writer-locked code to do so might look as follows
(assuming only ``field_count`` is updated, otherwise, the added fields would
need to be filled in)::

	static inline int audit_upd_rule(struct audit_rule *rule,
					 struct list_head *list,
					 __u32 newaction,
					 __u32 newfield_count)
	{
		struct audit_entry *e;
		struct audit_entry *ne;

		write_lock(&auditsc_lock);
		/* Note: audit_filter_mutex held by caller. */
		list_for_each_entry(e, list, list) {
			if (!audit_compare_rule(rule, &e->rule)) {
				e->rule.action = newaction;
				e->rule.field_count = newfield_count;
				write_unlock(&auditsc_lock);
				return 0;
			}
		}
		write_unlock(&auditsc_lock);
		return -EFAULT;		/* No matching rule */
	}

The RCU version creates a copy, updates the copy, then replaces the old
entry with the newly updated entry.  This sequence of actions, allowing
concurrent reads while making a copy to perform an update, is what gives
RCU (*read-copy update*) its name.

The RCU version of audit_upd_rule() is as follows::

	static inline int audit_upd_rule(struct audit_rule *rule,
					 struct list_head *list,
					 __u32 newaction,
					 __u32 newfield_count)
	{
		struct audit_entry *e;
		struct audit_entry *ne;

		list_for_each_entry(e, list, list) {
			if (!audit_compare_rule(rule, &e->rule)) {
				ne = kmalloc(sizeof(*entry), GFP_ATOMIC);
				if (ne == NULL)
					return -ENOMEM;
				audit_copy_rule(&ne->rule, &e->rule);
				ne->rule.action = newaction;
				ne->rule.field_count = newfield_count;
				list_replace_rcu(&e->list, &ne->list);
				call_rcu(&e->rcu, audit_free_rule);
				return 0;
			}
		}
		return -EFAULT;		/* No matching rule */
	}

Again, this assumes that the caller holds ``audit_filter_mutex``.  Normally, the
writer lock would become a spinlock in this sort of code.

The update_lsm_rule() does something very similar, for those who would
prefer to look at real Linux-kernel code.

Another use of this pattern can be found in the openswitch driver's *connection
tracking table* code in ``ct_limit_set()``.  The table holds connection tracking
entries and has a limit on the maximum entries.  There is one such table
per-zone and hence one *limit* per zone.  The zones are mapped to their limits
through a hashtable using an RCU-managed hlist for the hash chains. When a new
limit is set, a new limit object is allocated and ``ct_limit_set()`` is called
to replace the old limit object with the new one using list_replace_rcu().
The old limit object is then freed after a grace period using kfree_rcu().

Example 4: Eliminating Stale Data
---------------------------------

The auditing example above tolerates stale data, as do most algorithms
that are tracking external state.  After all, given there is a delay
from the time the external state changes before Linux becomes aware
of the change, and so as noted earlier, a small quantity of additional
RCU-induced staleness is generally not a problem.

However, there are many examples where stale data cannot be tolerated.
One example in the Linux kernel is the System V IPC (see the shm_lock()
function in ipc/shm.c).  This code checks a *deleted* flag under a
per-entry spinlock, and, if the *deleted* flag is set, pretends that the
entry does not exist.  For this to be helpful, the search function must
return holding the per-entry spinlock, as shm_lock() does in fact do.

.. _quick_quiz:

Quick Quiz:
	For the deleted-flag technique to be helpful, why is it necessary
	to hold the per-entry lock while returning from the search function?

:ref:`Answer to Quick Quiz <quick_quiz_answer>`

If the system-call audit module were to ever need to reject stale data, one way
to accomplish this would be to add a ``deleted`` flag and a ``lock`` spinlock to the
``audit_entry`` structure, and modify audit_filter_task() as follows::

	static enum audit_state audit_filter_task(struct task_struct *tsk)
	{
		struct audit_entry *e;
		enum audit_state   state;

		rcu_read_lock();
		list_for_each_entry_rcu(e, &audit_tsklist, list) {
			if (audit_filter_rules(tsk, &e->rule, NULL, &state)) {
				spin_lock(&e->lock);
				if (e->deleted) {
					spin_unlock(&e->lock);
					rcu_read_unlock();
					return AUDIT_BUILD_CONTEXT;
				}
				rcu_read_unlock();
				if (state == AUDIT_STATE_RECORD)
					*key = kstrdup(e->rule.filterkey, GFP_ATOMIC);
				return state;
			}
		}
		rcu_read_unlock();
		return AUDIT_BUILD_CONTEXT;
	}

The ``audit_del_rule()`` function would need to set the ``deleted`` flag under the
spinlock as follows::

	static inline int audit_del_rule(struct audit_rule *rule,
					 struct list_head *list)
	{
		struct audit_entry *e;

		/* No need to use the _rcu iterator here, since this
		 * is the only deletion routine. */
		list_for_each_entry(e, list, list) {
			if (!audit_compare_rule(rule, &e->rule)) {
				spin_lock(&e->lock);
				list_del_rcu(&e->list);
				e->deleted = 1;
				spin_unlock(&e->lock);
				call_rcu(&e->rcu, audit_free_rule);
				return 0;
			}
		}
		return -EFAULT;		/* No matching rule */
	}

This too assumes that the caller holds ``audit_filter_mutex``.

Note that this example assumes that entries are only added and deleted.
Additional mechanism is required to deal correctly with the update-in-place
performed by audit_upd_rule().  For one thing, audit_upd_rule() would
need to hold the locks of both the old ``audit_entry`` and its replacement
while executing the list_replace_rcu().

Example 5: Skipping Stale Objects
---------------------------------

For some use cases, reader performance can be improved by skipping
stale objects during read-side list traversal, where stale objects
are those that will be removed and destroyed after one or more grace
periods. One such example can be found in the timerfd subsystem. When a
``CLOCK_REALTIME`` clock is reprogrammed (for example due to setting
of the system time) then all programmed ``timerfds`` that depend on
this clock get triggered and processes waiting on them are awakened in
advance of their scheduled expiry. To facilitate this, all such timers
are added to an RCU-managed ``cancel_list`` when they are setup in
``timerfd_setup_cancel()``::

	static void timerfd_setup_cancel(struct timerfd_ctx *ctx, int flags)
	{
		spin_lock(&ctx->cancel_lock);
		if ((ctx->clockid == CLOCK_REALTIME ||
		     ctx->clockid == CLOCK_REALTIME_ALARM) &&
		    (flags & TFD_TIMER_ABSTIME) && (flags & TFD_TIMER_CANCEL_ON_SET)) {
			if (!ctx->might_cancel) {
				ctx->might_cancel = true;
				spin_lock(&cancel_lock);
				list_add_rcu(&ctx->clist, &cancel_list);
				spin_unlock(&cancel_lock);
			}
		} else {
			__timerfd_remove_cancel(ctx);
		}
		spin_unlock(&ctx->cancel_lock);
	}

When a timerfd is freed (fd is closed), then the ``might_cancel``
flag of the timerfd object is cleared, the object removed from the
``cancel_list`` and destroyed, as shown in this simplified and inlined
version of timerfd_release()::

	int timerfd_release(struct inode *inode, struct file *file)
	{
		struct timerfd_ctx *ctx = file->private_data;

		spin_lock(&ctx->cancel_lock);
		if (ctx->might_cancel) {
			ctx->might_cancel = false;
			spin_lock(&cancel_lock);
			list_del_rcu(&ctx->clist);
			spin_unlock(&cancel_lock);
		}
		spin_unlock(&ctx->cancel_lock);

		if (isalarm(ctx))
			alarm_cancel(&ctx->t.alarm);
		else
			hrtimer_cancel(&ctx->t.tmr);
		kfree_rcu(ctx, rcu);
		return 0;
	}

If the ``CLOCK_REALTIME`` clock is set, for example by a time server, the
hrtimer framework calls ``timerfd_clock_was_set()`` which walks the
``cancel_list`` and wakes up processes waiting on the timerfd. While iterating
the ``cancel_list``, the ``might_cancel`` flag is consulted to skip stale
objects::

	void timerfd_clock_was_set(void)
	{
		ktime_t moffs = ktime_mono_to_real(0);
		struct timerfd_ctx *ctx;
		unsigned long flags;

		rcu_read_lock();
		list_for_each_entry_rcu(ctx, &cancel_list, clist) {
			if (!ctx->might_cancel)
				continue;
			spin_lock_irqsave(&ctx->wqh.lock, flags);
			if (ctx->moffs != moffs) {
				ctx->moffs = KTIME_MAX;
				ctx->ticks++;
				wake_up_locked_poll(&ctx->wqh, EPOLLIN);
			}
			spin_unlock_irqrestore(&ctx->wqh.lock, flags);
		}
		rcu_read_unlock();
	}

The key point is that because RCU-protected traversal of the
``cancel_list`` happens concurrently with object addition and removal,
sometimes the traversal can access an object that has been removed from
the list. In this example, a flag is used to skip such objects.

Summary
-------

Read-mostly list-based data structures that can tolerate stale data are
the most amenable to use of RCU.  The simplest case is where entries are
either added or deleted from the data structure (or atomically modified
in place), but non-atomic in-place modifications can be handled by making
a copy, updating the copy, then replacing the original with the copy.
If stale data cannot be tolerated, then a *deleted* flag may be used
in conjunction with a per-entry spinlock in order to allow the search
function to reject newly deleted data.

.. _quick_quiz_answer:

Answer to Quick Quiz:
	For the deleted-flag technique to be helpful, why is it necessary
	to hold the per-entry lock while returning from the search function?

	If the search function drops the per-entry lock before returning,
	then the caller will be processing stale data in any case.  If it
	is really OK to be processing stale data, then you don't need a
	*deleted* flag.  If processing stale data really is a problem,
	then you need to hold the per-entry lock across all of the code
	that uses the value that was returned.

:ref:`Back to Quick Quiz <quick_quiz>`


code:
.. SPDX-License-Identifier: GPL-2.0

=================
Lockdep-RCU Splat
=================

Lockdep-RCU was added to the Linux kernel in early 2010
(http://lwn.net/Articles/371986/).  This facility checks for some common
misuses of the RCU API, most notably using one of the rcu_dereference()
family to access an RCU-protected pointer without the proper protection.
When such misuse is detected, an lockdep-RCU splat is emitted.

The usual cause of a lockdep-RCU slat is someone accessing an
RCU-protected data structure without either (1) being in the right kind of
RCU read-side critical section or (2) holding the right update-side lock.
This problem can therefore be serious: it might result in random memory
overwriting or worse.  There can of course be false positives, this
being the real world and all that.

So let's look at an example RCU lockdep splat from 3.0-rc5, one that
has long since been fixed::

    =============================
    WARNING: suspicious RCU usage
    -----------------------------
    block/cfq-iosched.c:2776 suspicious rcu_dereference_protected() usage!

other info that might help us debug this::

    rcu_scheduler_active = 1, debug_locks = 0
    3 locks held by scsi_scan_6/1552:
    #0:  (&shost->scan_mutex){+.+.}, at: [<ffffffff8145efca>]
    scsi_scan_host_selected+0x5a/0x150
    #1:  (&eq->sysfs_lock){+.+.}, at: [<ffffffff812a5032>]
    elevator_exit+0x22/0x60
    #2:  (&(&q->__queue_lock)->rlock){-.-.}, at: [<ffffffff812b6233>]
    cfq_exit_queue+0x43/0x190

    stack backtrace:
    Pid: 1552, comm: scsi_scan_6 Not tainted 3.0.0-rc5 #17
    Call Trace:
    [<ffffffff810abb9b>] lockdep_rcu_dereference+0xbb/0xc0
    [<ffffffff812b6139>] __cfq_exit_single_io_context+0xe9/0x120
    [<ffffffff812b626c>] cfq_exit_queue+0x7c/0x190
    [<ffffffff812a5046>] elevator_exit+0x36/0x60
    [<ffffffff812a802a>] blk_cleanup_queue+0x4a/0x60
    [<ffffffff8145cc09>] scsi_free_queue+0x9/0x10
    [<ffffffff81460944>] __scsi_remove_device+0x84/0xd0
    [<ffffffff8145dca3>] scsi_probe_and_add_lun+0x353/0xb10
    [<ffffffff817da069>] ? error_exit+0x29/0xb0
    [<ffffffff817d98ed>] ? _raw_spin_unlock_irqrestore+0x3d/0x80
    [<ffffffff8145e722>] __scsi_scan_target+0x112/0x680
    [<ffffffff812c690d>] ? trace_hardirqs_off_thunk+0x3a/0x3c
    [<ffffffff817da069>] ? error_exit+0x29/0xb0
    [<ffffffff812bcc60>] ? kobject_del+0x40/0x40
    [<ffffffff8145ed16>] scsi_scan_channel+0x86/0xb0
    [<ffffffff8145f0b0>] scsi_scan_host_selected+0x140/0x150
    [<ffffffff8145f149>] do_scsi_scan_host+0x89/0x90
    [<ffffffff8145f170>] do_scan_async+0x20/0x160
    [<ffffffff8145f150>] ? do_scsi_scan_host+0x90/0x90
    [<ffffffff810975b6>] kthread+0xa6/0xb0
    [<ffffffff817db154>] kernel_thread_helper+0x4/0x10
    [<ffffffff81066430>] ? finish_task_switch+0x80/0x110
    [<ffffffff817d9c04>] ? retint_restore_args+0xe/0xe
    [<ffffffff81097510>] ? __kthread_init_worker+0x70/0x70
    [<ffffffff817db150>] ? gs_change+0xb/0xb

Line 2776 of block/cfq-iosched.c in v3.0-rc5 is as follows::

	if (rcu_dereference(ioc->ioc_data) == cic) {

This form says that it must be in a plain vanilla RCU read-side critical
section, but the "other info" list above shows that this is not the
case.  Instead, we hold three locks, one of which might be RCU related.
And maybe that lock really does protect this reference.  If so, the fix
is to inform RCU, perhaps by changing __cfq_exit_single_io_context() to
take the struct request_queue "q" from cfq_exit_queue() as an argument,
which would permit us to invoke rcu_dereference_protected as follows::

	if (rcu_dereference_protected(ioc->ioc_data,
				      lockdep_is_held(&q->queue_lock)) == cic) {

With this change, there would be no lockdep-RCU splat emitted if this
code was invoked either from within an RCU read-side critical section
or with the ->queue_lock held.  In particular, this would have suppressed
the above lockdep-RCU splat because ->queue_lock is held (see #2 in the
list above).

On the other hand, perhaps we really do need an RCU read-side critical
section.  In this case, the critical section must span the use of the
return value from rcu_dereference(), or at least until there is some
reference count incremented or some such.  One way to handle this is to
add rcu_read_lock() and rcu_read_unlock() as follows::

	rcu_read_lock();
	if (rcu_dereference(ioc->ioc_data) == cic) {
		spin_lock(&ioc->lock);
		rcu_assign_pointer(ioc->ioc_data, NULL);
		spin_unlock(&ioc->lock);
	}
	rcu_read_unlock();

With this change, the rcu_dereference() is always within an RCU
read-side critical section, which again would have suppressed the
above lockdep-RCU splat.

But in this particular case, we don't actually dereference the pointer
returned from rcu_dereference().  Instead, that pointer is just compared
to the cic pointer, which means that the rcu_dereference() can be replaced
by rcu_access_pointer() as follows::

	if (rcu_access_pointer(ioc->ioc_data) == cic) {

Because it is legal to invoke rcu_access_pointer() without protection,
this change would also suppress the above lockdep-RCU splat.


code:
.. SPDX-License-Identifier: GPL-2.0

========================
RCU and lockdep checking
========================

All flavors of RCU have lockdep checking available, so that lockdep is
aware of when each task enters and leaves any flavor of RCU read-side
critical section.  Each flavor of RCU is tracked separately (but note
that this is not the case in 2.6.32 and earlier).  This allows lockdep's
tracking to include RCU state, which can sometimes help when debugging
deadlocks and the like.

In addition, RCU provides the following primitives that check lockdep's
state::

	rcu_read_lock_held() for normal RCU.
	rcu_read_lock_bh_held() for RCU-bh.
	rcu_read_lock_sched_held() for RCU-sched.
	rcu_read_lock_any_held() for any of normal RCU, RCU-bh, and RCU-sched.
	srcu_read_lock_held() for SRCU.
	rcu_read_lock_trace_held() for RCU Tasks Trace.

These functions are conservative, and will therefore return 1 if they
aren't certain (for example, if CONFIG_DEBUG_LOCK_ALLOC is not set).
This prevents things like WARN_ON(!rcu_read_lock_held()) from giving false
positives when lockdep is disabled.

In addition, a separate kernel config parameter CONFIG_PROVE_RCU enables
checking of rcu_dereference() primitives:

	rcu_dereference(p):
		Check for RCU read-side critical section.
	rcu_dereference_bh(p):
		Check for RCU-bh read-side critical section.
	rcu_dereference_sched(p):
		Check for RCU-sched read-side critical section.
	srcu_dereference(p, sp):
		Check for SRCU read-side critical section.
	rcu_dereference_check(p, c):
		Use explicit check expression "c" along with
		rcu_read_lock_held().  This is useful in code that is
		invoked by both RCU readers and updaters.
	rcu_dereference_bh_check(p, c):
		Use explicit check expression "c" along with
		rcu_read_lock_bh_held().  This is useful in code that
		is invoked by both RCU-bh readers and updaters.
	rcu_dereference_sched_check(p, c):
		Use explicit check expression "c" along with
		rcu_read_lock_sched_held().  This is useful in code that
		is invoked by both RCU-sched readers and updaters.
	srcu_dereference_check(p, c):
		Use explicit check expression "c" along with
		srcu_read_lock_held().  This is useful in code that
		is invoked by both SRCU readers and updaters.
	rcu_dereference_raw(p):
		Don't check.  (Use sparingly, if at all.)
	rcu_dereference_raw_check(p):
		Don't do lockdep at all.  (Use sparingly, if at all.)
	rcu_dereference_protected(p, c):
		Use explicit check expression "c", and omit all barriers
		and compiler constraints.  This is useful when the data
		structure cannot change, for example, in code that is
		invoked only by updaters.
	rcu_access_pointer(p):
		Return the value of the pointer and omit all barriers,
		but retain the compiler constraints that prevent duplicating
		or coalescsing.  This is useful when testing the
		value of the pointer itself, for example, against NULL.

The rcu_dereference_check() check expression can be any boolean
expression, but would normally include a lockdep expression.  However,
any boolean expression can be used.  For a moderately ornate example,
consider the following::

	file = rcu_dereference_check(fdt->fd[fd],
				     lockdep_is_held(&files->file_lock) ||
				     atomic_read(&files->count) == 1);

This expression picks up the pointer "fdt->fd[fd]" in an RCU-safe manner,
and, if CONFIG_PROVE_RCU is configured, verifies that this expression
is used in:

1.	An RCU read-side critical section (implicit), or
2.	with files->file_lock held, or
3.	on an unshared files_struct.

In case (1), the pointer is picked up in an RCU-safe manner for vanilla
RCU read-side critical sections, in case (2) the ->file_lock prevents
any change from taking place, and finally, in case (3) the current task
is the only task accessing the file_struct, again preventing any change
from taking place.  If the above statement was invoked only from updater
code, it could instead be written as follows::

	file = rcu_dereference_protected(fdt->fd[fd],
					 lockdep_is_held(&files->file_lock) ||
					 atomic_read(&files->count) == 1);

This would verify cases #2 and #3 above, and furthermore lockdep would
complain if this was used in an RCU read-side critical section unless one
of these two cases held.  Because rcu_dereference_protected() omits all
barriers and compiler constraints, it generates better code than do the
other flavors of rcu_dereference().  On the other hand, it is illegal
to use rcu_dereference_protected() if either the RCU-protected pointer
or the RCU-protected data that it points to can change concurrently.

Like rcu_dereference(), when lockdep is enabled, RCU list and hlist
traversal primitives check for being called from within an RCU read-side
critical section.  However, a lockdep expression can be passed to them
as a additional optional argument.  With this lockdep expression, these
traversal primitives will complain only if the lockdep expression is
false and they are called from outside any RCU read-side critical section.

For example, the workqueue for_each_pwq() macro is intended to be used
either within an RCU read-side critical section or with wq->mutex held.
It is thus implemented as follows::

	#define for_each_pwq(pwq, wq)
		list_for_each_entry_rcu((pwq), &(wq)->pwqs, pwqs_node,
					lock_is_held(&(wq->mutex).dep_map))


code:
.. _rcu_doc:

RCU Concepts
============

The basic idea behind RCU (read-copy update) is to split destructive
operations into two parts, one that prevents anyone from seeing the data
item being destroyed, and one that actually carries out the destruction.
A "grace period" must elapse between the two parts, and this grace period
must be long enough that any readers accessing the item being deleted have
since dropped their references.  For example, an RCU-protected deletion
from a linked list would first remove the item from the list, wait for
a grace period to elapse, then free the element.  See listRCU.rst for more
information on using RCU with linked lists.

Frequently Asked Questions
--------------------------

- Why would anyone want to use RCU?

  The advantage of RCU's two-part approach is that RCU readers need
  not acquire any locks, perform any atomic instructions, write to
  shared memory, or (on CPUs other than Alpha) execute any memory
  barriers.  The fact that these operations are quite expensive
  on modern CPUs is what gives RCU its performance advantages
  in read-mostly situations.  The fact that RCU readers need not
  acquire locks can also greatly simplify deadlock-avoidance code.

- How can the updater tell when a grace period has completed
  if the RCU readers give no indication when they are done?

  Just as with spinlocks, RCU readers are not permitted to
  block, switch to user-mode execution, or enter the idle loop.
  Therefore, as soon as a CPU is seen passing through any of these
  three states, we know that that CPU has exited any previous RCU
  read-side critical sections.  So, if we remove an item from a
  linked list, and then wait until all CPUs have switched context,
  executed in user mode, or executed in the idle loop, we can
  safely free up that item.

  Preemptible variants of RCU (CONFIG_PREEMPT_RCU) get the
  same effect, but require that the readers manipulate CPU-local
  counters.  These counters allow limited types of blocking within
  RCU read-side critical sections.  SRCU also uses CPU-local
  counters, and permits general blocking within RCU read-side
  critical sections.  These variants of RCU detect grace periods
  by sampling these counters.

- If I am running on a uniprocessor kernel, which can only do one
  thing at a time, why should I wait for a grace period?

  See UP.rst for more information.

- How can I see where RCU is currently used in the Linux kernel?

  Search for "rcu_read_lock", "rcu_read_unlock", "call_rcu",
  "rcu_read_lock_bh", "rcu_read_unlock_bh", "srcu_read_lock",
  "srcu_read_unlock", "synchronize_rcu", "synchronize_net",
  "synchronize_srcu", and the other RCU primitives.  Or grab one
  of the cscope databases from:

  (http://www.rdrop.com/users/paulmck/RCU/linuxusage/rculocktab.html).

- What guidelines should I follow when writing code that uses RCU?

  See checklist.rst.

- Why the name "RCU"?

  "RCU" stands for "read-copy update".
  listRCU.rst has more information on where this name came from, search
  for "read-copy update" to find it.

- I hear that RCU is patented?  What is with that?

  Yes, it is.  There are several known patents related to RCU,
  search for the string "Patent" in Documentation/RCU/RTFP.txt to find them.
  Of these, one was allowed to lapse by the assignee, and the
  others have been contributed to the Linux kernel under GPL.
  There are now also LGPL implementations of user-level RCU
  available (https://liburcu.org/).

- I hear that RCU needs work in order to support realtime kernels?

  Realtime-friendly RCU can be enabled via the CONFIG_PREEMPT_RCU
  kernel configuration parameter.

- Where can I find more information on RCU?

  See the Documentation/RCU/RTFP.txt file.
  Or point your browser at (http://www.rdrop.com/users/paulmck/RCU/).


code:
.. _rcu_dereference_doc:

PROPER CARE AND FEEDING OF RETURN VALUES FROM rcu_dereference()
===============================================================

Most of the time, you can use values from rcu_dereference() or one of
the similar primitives without worries.  Dereferencing (prefix "*"),
field selection ("->"), assignment ("="), address-of ("&"), addition and
subtraction of constants, and casts all work quite naturally and safely.

It is nevertheless possible to get into trouble with other operations.
Follow these rules to keep your RCU code working properly:

-	You must use one of the rcu_dereference() family of primitives
	to load an RCU-protected pointer, otherwise CONFIG_PROVE_RCU
	will complain.  Worse yet, your code can see random memory-corruption
	bugs due to games that compilers and DEC Alpha can play.
	Without one of the rcu_dereference() primitives, compilers
	can reload the value, and won't your code have fun with two
	different values for a single pointer!  Without rcu_dereference(),
	DEC Alpha can load a pointer, dereference that pointer, and
	return data preceding initialization that preceded the store of
	the pointer.

	In addition, the volatile cast in rcu_dereference() prevents the
	compiler from deducing the resulting pointer value.  Please see
	the section entitled "EXAMPLE WHERE THE COMPILER KNOWS TOO MUCH"
	for an example where the compiler can in fact deduce the exact
	value of the pointer, and thus cause misordering.

-	In the special case where data is added but is never removed
	while readers are accessing the structure, READ_ONCE() may be used
	instead of rcu_dereference().  In this case, use of READ_ONCE()
	takes on the role of the lockless_dereference() primitive that
	was removed in v4.15.

-	You are only permitted to use rcu_dereference on pointer values.
	The compiler simply knows too much about integral values to
	trust it to carry dependencies through integer operations.
	There are a very few exceptions, namely that you can temporarily
	cast the pointer to uintptr_t in order to:

	-	Set bits and clear bits down in the must-be-zero low-order
		bits of that pointer.  This clearly means that the pointer
		must have alignment constraints, for example, this does
		*not* work in general for char* pointers.

	-	XOR bits to translate pointers, as is done in some
		classic buddy-allocator algorithms.

	It is important to cast the value back to pointer before
	doing much of anything else with it.

-	Avoid cancellation when using the "+" and "-" infix arithmetic
	operators.  For example, for a given variable "x", avoid
	"(x-(uintptr_t)x)" for char* pointers.	The compiler is within its
	rights to substitute zero for this sort of expression, so that
	subsequent accesses no longer depend on the rcu_dereference(),
	again possibly resulting in bugs due to misordering.

	Of course, if "p" is a pointer from rcu_dereference(), and "a"
	and "b" are integers that happen to be equal, the expression
	"p+a-b" is safe because its value still necessarily depends on
	the rcu_dereference(), thus maintaining proper ordering.

-	If you are using RCU to protect JITed functions, so that the
	"()" function-invocation operator is applied to a value obtained
	(directly or indirectly) from rcu_dereference(), you may need to
	interact directly with the hardware to flush instruction caches.
	This issue arises on some systems when a newly JITed function is
	using the same memory that was used by an earlier JITed function.

-	Do not use the results from relational operators ("==", "!=",
	">", ">=", "<", or "<=") when dereferencing.  For example,
	the following (quite strange) code is buggy::

		int *p;
		int *q;

		...

		p = rcu_dereference(gp)
		q = &global_q;
		q += p > &oom_p;
		r1 = *q;  /* BUGGY!!! */

	As before, the reason this is buggy is that relational operators
	are often compiled using branches.  And as before, although
	weak-memory machines such as ARM or PowerPC do order stores
	after such branches, but can speculate loads, which can again
	result in misordering bugs.

-	Be very careful about comparing pointers obtained from
	rcu_dereference() against non-NULL values.  As Linus Torvalds
	explained, if the two pointers are equal, the compiler could
	substitute the pointer you are comparing against for the pointer
	obtained from rcu_dereference().  For example::

		p = rcu_dereference(gp);
		if (p == &default_struct)
			do_default(p->a);

	Because the compiler now knows that the value of "p" is exactly
	the address of the variable "default_struct", it is free to
	transform this code into the following::

		p = rcu_dereference(gp);
		if (p == &default_struct)
			do_default(default_struct.a);

	On ARM and Power hardware, the load from "default_struct.a"
	can now be speculated, such that it might happen before the
	rcu_dereference().  This could result in bugs due to misordering.

	However, comparisons are OK in the following cases:

	-	The comparison was against the NULL pointer.  If the
		compiler knows that the pointer is NULL, you had better
		not be dereferencing it anyway.  If the comparison is
		non-equal, the compiler is none the wiser.  Therefore,
		it is safe to compare pointers from rcu_dereference()
		against NULL pointers.

	-	The pointer is never dereferenced after being compared.
		Since there are no subsequent dereferences, the compiler
		cannot use anything it learned from the comparison
		to reorder the non-existent subsequent dereferences.
		This sort of comparison occurs frequently when scanning
		RCU-protected circular linked lists.

		Note that if the pointer comparison is done outside
		of an RCU read-side critical section, and the pointer
		is never dereferenced, rcu_access_pointer() should be
		used in place of rcu_dereference().  In most cases,
		it is best to avoid accidental dereferences by testing
		the rcu_access_pointer() return value directly, without
		assigning it to a variable.

		Within an RCU read-side critical section, there is little
		reason to use rcu_access_pointer().

	-	The comparison is against a pointer that references memory
		that was initialized "a long time ago."  The reason
		this is safe is that even if misordering occurs, the
		misordering will not affect the accesses that follow
		the comparison.  So exactly how long ago is "a long
		time ago"?  Here are some possibilities:

		-	Compile time.

		-	Boot time.

		-	Module-init time for module code.

		-	Prior to kthread creation for kthread code.

		-	During some prior acquisition of the lock that
			we now hold.

		-	Before mod_timer() time for a timer handler.

		There are many other possibilities involving the Linux
		kernel's wide array of primitives that cause code to
		be invoked at a later time.

	-	The pointer being compared against also came from
		rcu_dereference().  In this case, both pointers depend
		on one rcu_dereference() or another, so you get proper
		ordering either way.

		That said, this situation can make certain RCU usage
		bugs more likely to happen.  Which can be a good thing,
		at least if they happen during testing.  An example
		of such an RCU usage bug is shown in the section titled
		"EXAMPLE OF AMPLIFIED RCU-USAGE BUG".

	-	All of the accesses following the comparison are stores,
		so that a control dependency preserves the needed ordering.
		That said, it is easy to get control dependencies wrong.
		Please see the "CONTROL DEPENDENCIES" section of
		Documentation/memory-barriers.txt for more details.

	-	The pointers are not equal *and* the compiler does
		not have enough information to deduce the value of the
		pointer.  Note that the volatile cast in rcu_dereference()
		will normally prevent the compiler from knowing too much.

		However, please note that if the compiler knows that the
		pointer takes on only one of two values, a not-equal
		comparison will provide exactly the information that the
		compiler needs to deduce the value of the pointer.

-	Disable any value-speculation optimizations that your compiler
	might provide, especially if you are making use of feedback-based
	optimizations that take data collected from prior runs.  Such
	value-speculation optimizations reorder operations by design.

	There is one exception to this rule:  Value-speculation
	optimizations that leverage the branch-prediction hardware are
	safe on strongly ordered systems (such as x86), but not on weakly
	ordered systems (such as ARM or Power).  Choose your compiler
	command-line options wisely!

EXAMPLE OF AMPLIFIED RCU-USAGE BUG
----------------------------------

Because updaters can run concurrently with RCU readers, RCU readers can
see stale and/or inconsistent values.  If RCU readers need fresh or
consistent values, which they sometimes do, they need to take proper
precautions.  To see this, consider the following code fragment::

	struct foo {
		int a;
		int b;
		int c;
	};
	struct foo *gp1;
	struct foo *gp2;

	void updater(void)
	{
		struct foo *p;

		p = kmalloc(...);
		if (p == NULL)
			deal_with_it();
		p->a = 42;  /* Each field in its own cache line. */
		p->b = 43;
		p->c = 44;
		rcu_assign_pointer(gp1, p);
		p->b = 143;
		p->c = 144;
		rcu_assign_pointer(gp2, p);
	}

	void reader(void)
	{
		struct foo *p;
		struct foo *q;
		int r1, r2;

		p = rcu_dereference(gp2);
		if (p == NULL)
			return;
		r1 = p->b;  /* Guaranteed to get 143. */
		q = rcu_dereference(gp1);  /* Guaranteed non-NULL. */
		if (p == q) {
			/* The compiler decides that q->c is same as p->c. */
			r2 = p->c; /* Could get 44 on weakly order system. */
		}
		do_something_with(r1, r2);
	}

You might be surprised that the outcome (r1 == 143 && r2 == 44) is possible,
but you should not be.  After all, the updater might have been invoked
a second time between the time reader() loaded into "r1" and the time
that it loaded into "r2".  The fact that this same result can occur due
to some reordering from the compiler and CPUs is beside the point.

But suppose that the reader needs a consistent view?

Then one approach is to use locking, for example, as follows::

	struct foo {
		int a;
		int b;
		int c;
		spinlock_t lock;
	};
	struct foo *gp1;
	struct foo *gp2;

	void updater(void)
	{
		struct foo *p;

		p = kmalloc(...);
		if (p == NULL)
			deal_with_it();
		spin_lock(&p->lock);
		p->a = 42;  /* Each field in its own cache line. */
		p->b = 43;
		p->c = 44;
		spin_unlock(&p->lock);
		rcu_assign_pointer(gp1, p);
		spin_lock(&p->lock);
		p->b = 143;
		p->c = 144;
		spin_unlock(&p->lock);
		rcu_assign_pointer(gp2, p);
	}

	void reader(void)
	{
		struct foo *p;
		struct foo *q;
		int r1, r2;

		p = rcu_dereference(gp2);
		if (p == NULL)
			return;
		spin_lock(&p->lock);
		r1 = p->b;  /* Guaranteed to get 143. */
		q = rcu_dereference(gp1);  /* Guaranteed non-NULL. */
		if (p == q) {
			/* The compiler decides that q->c is same as p->c. */
			r2 = p->c; /* Locking guarantees r2 == 144. */
		}
		spin_unlock(&p->lock);
		do_something_with(r1, r2);
	}

As always, use the right tool for the job!

EXAMPLE WHERE THE COMPILER KNOWS TOO MUCH
-----------------------------------------

If a pointer obtained from rcu_dereference() compares not-equal to some
other pointer, the compiler normally has no clue what the value of the
first pointer might be.  This lack of knowledge prevents the compiler
from carrying out optimizations that otherwise might destroy the ordering
guarantees that RCU depends on.  And the volatile cast in rcu_dereference()
should prevent the compiler from guessing the value.

But without rcu_dereference(), the compiler knows more than you might
expect.  Consider the following code fragment::

	struct foo {
		int a;
		int b;
	};
	static struct foo variable1;
	static struct foo variable2;
	static struct foo *gp = &variable1;

	void updater(void)
	{
		initialize_foo(&variable2);
		rcu_assign_pointer(gp, &variable2);
		/*
		 * The above is the only store to gp in this translation unit,
		 * and the address of gp is not exported in any way.
		 */
	}

	int reader(void)
	{
		struct foo *p;

		p = gp;
		barrier();
		if (p == &variable1)
			return p->a; /* Must be variable1.a. */
		else
			return p->b; /* Must be variable2.b. */
	}

Because the compiler can see all stores to "gp", it knows that the only
possible values of "gp" are "variable1" on the one hand and "variable2"
on the other.  The comparison in reader() therefore tells the compiler
the exact value of "p" even in the not-equals case.  This allows the
compiler to make the return values independent of the load from "gp",
in turn destroying the ordering between this load and the loads of the
return values.  This can result in "p->b" returning pre-initialization
garbage values.

In short, rcu_dereference() is *not* optional when you are going to
dereference the resulting pointer.

WHICH MEMBER OF THE rcu_dereference() FAMILY SHOULD YOU USE?
------------------------------------------------------------

First, please avoid using rcu_dereference_raw() and also please avoid
using rcu_dereference_check() and rcu_dereference_protected() with a
second argument with a constant value of 1 (or true, for that matter).
With that caution out of the way, here is some guidance for which
member of the rcu_dereference() to use in various situations:

1.	If the access needs to be within an RCU read-side critical
	section, use rcu_dereference().  With the new consolidated
	RCU flavors, an RCU read-side critical section is entered
	using rcu_read_lock(), anything that disables bottom halves,
	anything that disables interrupts, or anything that disables
	preemption.

2.	If the access might be within an RCU read-side critical section
	on the one hand, or protected by (say) my_lock on the other,
	use rcu_dereference_check(), for example::

		p1 = rcu_dereference_check(p->rcu_protected_pointer,
					   lockdep_is_held(&my_lock));

3.	If the access might be within an RCU read-side critical section
	on the one hand, or protected by either my_lock or your_lock on
	the other, again use rcu_dereference_check(), for example::

		p1 = rcu_dereference_check(p->rcu_protected_pointer,
					   lockdep_is_held(&my_lock) ||
					   lockdep_is_held(&your_lock));

4.	If the access is on the update side, so that it is always protected
	by my_lock, use rcu_dereference_protected()::

		p1 = rcu_dereference_protected(p->rcu_protected_pointer,
					       lockdep_is_held(&my_lock));

	This can be extended to handle multiple locks as in #3 above,
	and both can be extended to check other conditions as well.

5.	If the protection is supplied by the caller, and is thus unknown
	to this code, that is the rare case when rcu_dereference_raw()
	is appropriate.  In addition, rcu_dereference_raw() might be
	appropriate when the lockdep expression would be excessively
	complex, except that a better approach in that case might be to
	take a long hard look at your synchronization design.  Still,
	there are data-locking cases where any one of a very large number
	of locks or reference counters suffices to protect the pointer,
	so rcu_dereference_raw() does have its place.

	However, its place is probably quite a bit smaller than one
	might expect given the number of uses in the current kernel.
	Ditto for its synonym, rcu_dereference_check( ... , 1), and
	its close relative, rcu_dereference_protected(... , 1).

SPARSE CHECKING OF RCU-PROTECTED POINTERS
-----------------------------------------

The sparse static-analysis tool checks for direct access to RCU-protected
pointers, which can result in "interesting" bugs due to compiler
optimizations involving invented loads and perhaps also load tearing.
For example, suppose someone mistakenly does something like this::

	p = q->rcu_protected_pointer;
	do_something_with(p->a);
	do_something_else_with(p->b);

If register pressure is high, the compiler might optimize "p" out
of existence, transforming the code to something like this::

	do_something_with(q->rcu_protected_pointer->a);
	do_something_else_with(q->rcu_protected_pointer->b);

This could fatally disappoint your code if q->rcu_protected_pointer
changed in the meantime.  Nor is this a theoretical problem:  Exactly
this sort of bug cost Paul E. McKenney (and several of his innocent
colleagues) a three-day weekend back in the early 1990s.

Load tearing could of course result in dereferencing a mashup of a pair
of pointers, which also might fatally disappoint your code.

These problems could have been avoided simply by making the code instead
read as follows::

	p = rcu_dereference(q->rcu_protected_pointer);
	do_something_with(p->a);
	do_something_else_with(p->b);

Unfortunately, these sorts of bugs can be extremely hard to spot during
review.  This is where the sparse tool comes into play, along with the
"__rcu" marker.  If you mark a pointer declaration, whether in a structure
or as a formal parameter, with "__rcu", which tells sparse to complain if
this pointer is accessed directly.  It will also cause sparse to complain
if a pointer not marked with "__rcu" is accessed using rcu_dereference()
and friends.  For example, ->rcu_protected_pointer might be declared as
follows::

	struct foo __rcu *rcu_protected_pointer;

Use of "__rcu" is opt-in.  If you choose not to use it, then you should
ignore the sparse warnings.


code:
.. _rcu_barrier:

RCU and Unloadable Modules
==========================

[Originally published in LWN Jan. 14, 2007: http://lwn.net/Articles/217484/]

RCU (read-copy update) is a synchronization mechanism that can be thought
of as a replacement for read-writer locking (among other things), but with
very low-overhead readers that are immune to deadlock, priority inversion,
and unbounded latency. RCU read-side critical sections are delimited
by rcu_read_lock() and rcu_read_unlock(), which, in non-CONFIG_PREEMPTION
kernels, generate no code whatsoever.

This means that RCU writers are unaware of the presence of concurrent
readers, so that RCU updates to shared data must be undertaken quite
carefully, leaving an old version of the data structure in place until all
pre-existing readers have finished. These old versions are needed because
such readers might hold a reference to them. RCU updates can therefore be
rather expensive, and RCU is thus best suited for read-mostly situations.

How can an RCU writer possibly determine when all readers are finished,
given that readers might well leave absolutely no trace of their
presence? There is a synchronize_rcu() primitive that blocks until all
pre-existing readers have completed. An updater wishing to delete an
element p from a linked list might do the following, while holding an
appropriate lock, of course::

	list_del_rcu(p);
	synchronize_rcu();
	kfree(p);

But the above code cannot be used in IRQ context -- the call_rcu()
primitive must be used instead. This primitive takes a pointer to an
rcu_head struct placed within the RCU-protected data structure and
another pointer to a function that may be invoked later to free that
structure. Code to delete an element p from the linked list from IRQ
context might then be as follows::

	list_del_rcu(p);
	call_rcu(&p->rcu, p_callback);

Since call_rcu() never blocks, this code can safely be used from within
IRQ context. The function p_callback() might be defined as follows::

	static void p_callback(struct rcu_head *rp)
	{
		struct pstruct *p = container_of(rp, struct pstruct, rcu);

		kfree(p);
	}

Unloading Modules That Use call_rcu()
-------------------------------------

But what if p_callback is defined in an unloadable module?

If we unload the module while some RCU callbacks are pending,
the CPUs executing these callbacks are going to be severely
disappointed when they are later invoked, as fancifully depicted at
http://lwn.net/images/ns/kernel/rcu-drop.jpg.

We could try placing a synchronize_rcu() in the module-exit code path,
but this is not sufficient. Although synchronize_rcu() does wait for a
grace period to elapse, it does not wait for the callbacks to complete.

One might be tempted to try several back-to-back synchronize_rcu()
calls, but this is still not guaranteed to work. If there is a very
heavy RCU-callback load, then some of the callbacks might be deferred
in order to allow other processing to proceed. Such deferral is required
in realtime kernels in order to avoid excessive scheduling latencies.

rcu_barrier()
-------------

We instead need the rcu_barrier() primitive.  Rather than waiting for
a grace period to elapse, rcu_barrier() waits for all outstanding RCU
callbacks to complete.  Please note that rcu_barrier() does **not** imply
synchronize_rcu(), in particular, if there are no RCU callbacks queued
anywhere, rcu_barrier() is within its rights to return immediately,
without waiting for a grace period to elapse.

Pseudo-code using rcu_barrier() is as follows:

   1. Prevent any new RCU callbacks from being posted.
   2. Execute rcu_barrier().
   3. Allow the module to be unloaded.

There is also an srcu_barrier() function for SRCU, and you of course
must match the flavor of rcu_barrier() with that of call_rcu().  If your
module uses multiple flavors of call_rcu(), then it must also use multiple
flavors of rcu_barrier() when unloading that module.  For example, if
it uses call_rcu(), call_srcu() on srcu_struct_1, and call_srcu() on
srcu_struct_2, then the following three lines of code will be required
when unloading::

 1 rcu_barrier();
 2 srcu_barrier(&srcu_struct_1);
 3 srcu_barrier(&srcu_struct_2);

The rcutorture module makes use of rcu_barrier() in its exit function
as follows::

 1  static void
 2  rcu_torture_cleanup(void)
 3  {
 4    int i;
 5
 6    fullstop = 1;
 7    if (shuffler_task != NULL) {
 8     VERBOSE_PRINTK_STRING("Stopping rcu_torture_shuffle task");
 9     kthread_stop(shuffler_task);
 10   }
 11   shuffler_task = NULL;
 12
 13   if (writer_task != NULL) {
 14     VERBOSE_PRINTK_STRING("Stopping rcu_torture_writer task");
 15     kthread_stop(writer_task);
 16   }
 17   writer_task = NULL;
 18
 19   if (reader_tasks != NULL) {
 20     for (i = 0; i < nrealreaders; i++) {
 21       if (reader_tasks[i] != NULL) {
 22         VERBOSE_PRINTK_STRING(
 23           "Stopping rcu_torture_reader task");
 24         kthread_stop(reader_tasks[i]);
 25       }
 26       reader_tasks[i] = NULL;
 27     }
 28     kfree(reader_tasks);
 29     reader_tasks = NULL;
 30   }
 31   rcu_torture_current = NULL;
 32
 33   if (fakewriter_tasks != NULL) {
 34     for (i = 0; i < nfakewriters; i++) {
 35       if (fakewriter_tasks[i] != NULL) {
 36         VERBOSE_PRINTK_STRING(
 37           "Stopping rcu_torture_fakewriter task");
 38         kthread_stop(fakewriter_tasks[i]);
 39       }
 40       fakewriter_tasks[i] = NULL;
 41     }
 42     kfree(fakewriter_tasks);
 43     fakewriter_tasks = NULL;
 44   }
 45
 46   if (stats_task != NULL) {
 47     VERBOSE_PRINTK_STRING("Stopping rcu_torture_stats task");
 48     kthread_stop(stats_task);
 49   }
 50   stats_task = NULL;
 51
 52   /* Wait for all RCU callbacks to fire. */
 53   rcu_barrier();
 54
 55   rcu_torture_stats_print(); /* -After- the stats thread is stopped! */
 56
 57   if (cur_ops->cleanup != NULL)
 58     cur_ops->cleanup();
 59   if (atomic_read(&n_rcu_torture_error))
 60     rcu_torture_print_module_parms("End of test: FAILURE");
 61   else
 62     rcu_torture_print_module_parms("End of test: SUCCESS");
 63 }

Line 6 sets a global variable that prevents any RCU callbacks from
re-posting themselves. This will not be necessary in most cases, since
RCU callbacks rarely include calls to call_rcu(). However, the rcutorture
module is an exception to this rule, and therefore needs to set this
global variable.

Lines 7-50 stop all the kernel tasks associated with the rcutorture
module. Therefore, once execution reaches line 53, no more rcutorture
RCU callbacks will be posted. The rcu_barrier() call on line 53 waits
for any pre-existing callbacks to complete.

Then lines 55-62 print status and do operation-specific cleanup, and
then return, permitting the module-unload operation to be completed.

.. _rcubarrier_quiz_1:

Quick Quiz #1:
	Is there any other situation where rcu_barrier() might
	be required?

:ref:`Answer to Quick Quiz #1 <answer_rcubarrier_quiz_1>`

Your module might have additional complications. For example, if your
module invokes call_rcu() from timers, you will need to first cancel all
the timers, and only then invoke rcu_barrier() to wait for any remaining
RCU callbacks to complete.

Of course, if you module uses call_rcu(), you will need to invoke
rcu_barrier() before unloading.  Similarly, if your module uses
call_srcu(), you will need to invoke srcu_barrier() before unloading,
and on the same srcu_struct structure.  If your module uses call_rcu()
**and** call_srcu(), then you will need to invoke rcu_barrier() **and**
srcu_barrier().

Implementing rcu_barrier()
--------------------------

Dipankar Sarma's implementation of rcu_barrier() makes use of the fact
that RCU callbacks are never reordered once queued on one of the per-CPU
queues. His implementation queues an RCU callback on each of the per-CPU
callback queues, and then waits until they have all started executing, at
which point, all earlier RCU callbacks are guaranteed to have completed.

The original code for rcu_barrier() was as follows::

 1  void rcu_barrier(void)
 2  {
 3    BUG_ON(in_interrupt());
 4    /* Take cpucontrol mutex to protect against CPU hotplug */
 5    mutex_lock(&rcu_barrier_mutex);
 6    init_completion(&rcu_barrier_completion);
 7    atomic_set(&rcu_barrier_cpu_count, 0);
 8    on_each_cpu(rcu_barrier_func, NULL, 0, 1);
 9    wait_for_completion(&rcu_barrier_completion);
 10   mutex_unlock(&rcu_barrier_mutex);
 11 }

Line 3 verifies that the caller is in process context, and lines 5 and 10
use rcu_barrier_mutex to ensure that only one rcu_barrier() is using the
global completion and counters at a time, which are initialized on lines
6 and 7. Line 8 causes each CPU to invoke rcu_barrier_func(), which is
shown below. Note that the final "1" in on_each_cpu()'s argument list
ensures that all the calls to rcu_barrier_func() will have completed
before on_each_cpu() returns. Line 9 then waits for the completion.

This code was rewritten in 2008 and several times thereafter, but this
still gives the general idea.

The rcu_barrier_func() runs on each CPU, where it invokes call_rcu()
to post an RCU callback, as follows::

 1  static void rcu_barrier_func(void *notused)
 2  {
 3    int cpu = smp_processor_id();
 4    struct rcu_data *rdp = &per_cpu(rcu_data, cpu);
 5    struct rcu_head *head;
 6
 7    head = &rdp->barrier;
 8    atomic_inc(&rcu_barrier_cpu_count);
 9    call_rcu(head, rcu_barrier_callback);
 10 }

Lines 3 and 4 locate RCU's internal per-CPU rcu_data structure,
which contains the struct rcu_head that needed for the later call to
call_rcu(). Line 7 picks up a pointer to this struct rcu_head, and line
8 increments a global counter. This counter will later be decremented
by the callback. Line 9 then registers the rcu_barrier_callback() on
the current CPU's queue.

The rcu_barrier_callback() function simply atomically decrements the
rcu_barrier_cpu_count variable and finalizes the completion when it
reaches zero, as follows::

 1 static void rcu_barrier_callback(struct rcu_head *notused)
 2 {
 3   if (atomic_dec_and_test(&rcu_barrier_cpu_count))
 4     complete(&rcu_barrier_completion);
 5 }

.. _rcubarrier_quiz_2:

Quick Quiz #2:
	What happens if CPU 0's rcu_barrier_func() executes
	immediately (thus incrementing rcu_barrier_cpu_count to the
	value one), but the other CPU's rcu_barrier_func() invocations
	are delayed for a full grace period? Couldn't this result in
	rcu_barrier() returning prematurely?

:ref:`Answer to Quick Quiz #2 <answer_rcubarrier_quiz_2>`

The current rcu_barrier() implementation is more complex, due to the need
to avoid disturbing idle CPUs (especially on battery-powered systems)
and the need to minimally disturb non-idle CPUs in real-time systems.
However, the code above illustrates the concepts.

rcu_barrier() Summary
---------------------

The rcu_barrier() primitive has seen relatively little use, since most
code using RCU is in the core kernel rather than in modules. However, if
you are using RCU from an unloadable module, you need to use rcu_barrier()
so that your module may be safely unloaded.

Answers to Quick Quizzes
------------------------

.. _answer_rcubarrier_quiz_1:

Quick Quiz #1:
	Is there any other situation where rcu_barrier() might
	be required?

Answer: Interestingly enough, rcu_barrier() was not originally
	implemented for module unloading. Nikita Danilov was using
	RCU in a filesystem, which resulted in a similar situation at
	filesystem-unmount time. Dipankar Sarma coded up rcu_barrier()
	in response, so that Nikita could invoke it during the
	filesystem-unmount process.

	Much later, yours truly hit the RCU module-unload problem when
	implementing rcutorture, and found that rcu_barrier() solves
	this problem as well.

:ref:`Back to Quick Quiz #1 <rcubarrier_quiz_1>`

.. _answer_rcubarrier_quiz_2:

Quick Quiz #2:
	What happens if CPU 0's rcu_barrier_func() executes
	immediately (thus incrementing rcu_barrier_cpu_count to the
	value one), but the other CPU's rcu_barrier_func() invocations
	are delayed for a full grace period? Couldn't this result in
	rcu_barrier() returning prematurely?

Answer: This cannot happen. The reason is that on_each_cpu() has its last
	argument, the wait flag, set to "1". This flag is passed through
	to smp_call_function() and further to smp_call_function_on_cpu(),
	causing this latter to spin until the cross-CPU invocation of
	rcu_barrier_func() has completed. This by itself would prevent
	a grace period from completing on non-CONFIG_PREEMPTION kernels,
	since each CPU must undergo a context switch (or other quiescent
	state) before the grace period can complete. However, this is
	of no use in CONFIG_PREEMPTION kernels.

	Therefore, on_each_cpu() disables preemption across its call
	to smp_call_function() and also across the local call to
	rcu_barrier_func(). This prevents the local CPU from context
	switching, again preventing grace periods from completing. This
	means that all CPUs have executed rcu_barrier_func() before
	the first rcu_barrier_callback() can possibly execute, in turn
	preventing rcu_barrier_cpu_count from prematurely reaching zero.

	Currently, -rt implementations of RCU keep but a single global
	queue for RCU callbacks, and thus do not suffer from this
	problem. However, when the -rt RCU eventually does have per-CPU
	callback queues, things will have to change. One simple change
	is to add an rcu_read_lock() before line 8 of rcu_barrier()
	and an rcu_read_unlock() after line 8 of this same function. If
	you can think of a better change, please let me know!

:ref:`Back to Quick Quiz #2 <rcubarrier_quiz_2>`


code:
.. SPDX-License-Identifier: GPL-2.0

=================================================
Using RCU hlist_nulls to protect list and objects
=================================================

This section describes how to use hlist_nulls to
protect read-mostly linked lists and
objects using SLAB_TYPESAFE_BY_RCU allocations.

Please read the basics in listRCU.rst.

Using 'nulls'
=============

Using special makers (called 'nulls') is a convenient way
to solve following problem :

A typical RCU linked list managing objects which are
allocated with SLAB_TYPESAFE_BY_RCU kmem_cache can
use following algos :

1) Lookup algo
--------------

::

  rcu_read_lock()
  begin:
  obj = lockless_lookup(key);
  if (obj) {
    if (!try_get_ref(obj)) // might fail for free objects
      goto begin;
    /*
    * Because a writer could delete object, and a writer could
    * reuse these object before the RCU grace period, we
    * must check key after getting the reference on object
    */
    if (obj->key != key) { // not the object we expected
      put_ref(obj);
      goto begin;
    }
  }
  rcu_read_unlock();

Beware that lockless_lookup(key) cannot use traditional hlist_for_each_entry_rcu()
but a version with an additional memory barrier (smp_rmb())

::

  lockless_lookup(key)
  {
    struct hlist_node *node, *next;
    for (pos = rcu_dereference((head)->first);
        pos && ({ next = pos->next; smp_rmb(); prefetch(next); 1; }) &&
        ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1; });
        pos = rcu_dereference(next))
      if (obj->key == key)
        return obj;
    return NULL;
  }

And note the traditional hlist_for_each_entry_rcu() misses this smp_rmb()::

  struct hlist_node *node;
  for (pos = rcu_dereference((head)->first);
        pos && ({ prefetch(pos->next); 1; }) &&
        ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1; });
        pos = rcu_dereference(pos->next))
   if (obj->key == key)
     return obj;
  return NULL;

Quoting Corey Minyard::

  "If the object is moved from one list to another list in-between the
  time the hash is calculated and the next field is accessed, and the
  object has moved to the end of a new list, the traversal will not
  complete properly on the list it should have, since the object will
  be on the end of the new list and there's not a way to tell it's on a
  new list and restart the list traversal. I think that this can be
  solved by pre-fetching the "next" field (with proper barriers) before
  checking the key."

2) Insert algo
--------------

We need to make sure a reader cannot read the new 'obj->obj_next' value
and previous value of 'obj->key'. Or else, an item could be deleted
from a chain, and inserted into another chain. If new chain was empty
before the move, 'next' pointer is NULL, and lockless reader can
not detect it missed following items in original chain.

::

  /*
  * Please note that new inserts are done at the head of list,
  * not in the middle or end.
  */
  obj = kmem_cache_alloc(...);
  lock_chain(); // typically a spin_lock()
  obj->key = key;
  /*
  * we need to make sure obj->key is updated before obj->next
  * or obj->refcnt
  */
  smp_wmb();
  atomic_set(&obj->refcnt, 1);
  hlist_add_head_rcu(&obj->obj_node, list);
  unlock_chain(); // typically a spin_unlock()

3) Remove algo
--------------
Nothing special here, we can use a standard RCU hlist deletion.
But thanks to SLAB_TYPESAFE_BY_RCU, beware a deleted object can be reused
very very fast (before the end of RCU grace period)

::

  if (put_last_reference_on(obj) {
    lock_chain(); // typically a spin_lock()
    hlist_del_init_rcu(&obj->obj_node);
    unlock_chain(); // typically a spin_unlock()
    kmem_cache_free(cachep, obj);
  }

--------------------------------------------------------------------------

Avoiding extra smp_rmb()
========================

With hlist_nulls we can avoid extra smp_rmb() in lockless_lookup()
and extra smp_wmb() in insert function.

For example, if we choose to store the slot number as the 'nulls'
end-of-list marker for each slot of the hash table, we can detect
a race (some writer did a delete and/or a move of an object
to another chain) checking the final 'nulls' value if
the lookup met the end of chain. If final 'nulls' value
is not the slot number, then we must restart the lookup at
the beginning. If the object was moved to the same chain,
then the reader doesn't care : It might eventually
scan the list again without harm.

1) lookup algo
--------------

::

  head = &table[slot];
  rcu_read_lock();
  begin:
  hlist_nulls_for_each_entry_rcu(obj, node, head, member) {
    if (obj->key == key) {
      if (!try_get_ref(obj)) // might fail for free objects
        goto begin;
      if (obj->key != key) { // not the object we expected
        put_ref(obj);
        goto begin;
      }
    goto out;
  }
  /*
  * if the nulls value we got at the end of this lookup is
  * not the expected one, we must restart lookup.
  * We probably met an item that was moved to another chain.
  */
  if (get_nulls_value(node) != slot)
  goto begin;
  obj = NULL;

  out:
  rcu_read_unlock();

2) Insert function
------------------

::

  /*
  * Please note that new inserts are done at the head of list,
  * not in the middle or end.
  */
  obj = kmem_cache_alloc(cachep);
  lock_chain(); // typically a spin_lock()
  obj->key = key;
  /*
  * changes to obj->key must be visible before refcnt one
  */
  smp_wmb();
  atomic_set(&obj->refcnt, 1);
  /*
  * insert obj in RCU way (readers might be traversing chain)
  */
  hlist_nulls_add_head_rcu(&obj->obj_node, list);
  unlock_chain(); // typically a spin_unlock()