Message-ID: <157994896987.396.12313571754216721120.tip-bot2@tip-bot2>
Date:   Sat, 25 Jan 2020 10:42:49 -0000
From:   "tip-bot2 for Phong Tran" <tip-bot2@...utronix.de>
To:     linux-tip-commits@...r.kernel.org
Cc:     Phong Tran <tranmanphong@...il.com>,
        Madhuparna Bhowmik <madhuparnabhowmik04@...il.com>,
        Amol Grover <frextrite@...il.com>,
        "Paul E. McKenney" <paulmck@...nel.org>, x86 <x86@...nel.org>,
        LKML <linux-kernel@...r.kernel.org>
Subject: [tip: core/rcu] doc: Convert whatisRCU.txt to .rst

The following commit has been merged into the core/rcu branch of tip:

Commit-ID:     5e1bc932818f74082e8331b59aa550101ead08e0
Gitweb:        https://git.kernel.org/tip/5e1bc932818f74082e8331b59aa550101ead08e0
Author:        Phong Tran <tranmanphong@...il.com>
AuthorDate:    Wed, 06 Nov 2019 20:09:50 +07:00
Committer:     Paul E. McKenney <paulmck@...nel.org>
CommitterDate: Tue, 10 Dec 2019 18:51:53 -08:00

doc: Convert whatisRCU.txt to .rst

This commit updates whatisRCU.txt to the new .rst format.
This change includes:

- Formatting bullet lists
- Adding literal blocks
- Links from table of contents to corresponding sections
- Links to external documents
- Reformat quick quizzes

Signed-off-by: Phong Tran <tranmanphong@...il.com>
Tested-by: Madhuparna Bhowmik <madhuparnabhowmik04@...il.com>
[ tranmanphong: Apply Amol Grover feedback. ]
Reviewed-by: Amol Grover <frextrite@...il.com>
Signed-off-by: Paul E. McKenney <paulmck@...nel.org>
---
 Documentation/RCU/index.rst     |    1 +-
 Documentation/RCU/whatisRCU.rst | 1149 ++++++++++++++++++++++++++++++-
 Documentation/RCU/whatisRCU.txt | 1079 +----------------------------
 3 files changed, 1150 insertions(+), 1079 deletions(-)
 create mode 100644 Documentation/RCU/whatisRCU.rst
 delete mode 100644 Documentation/RCU/whatisRCU.txt

diff --git a/Documentation/RCU/index.rst b/Documentation/RCU/index.rst
index 627128c..b9b1148 100644
--- a/Documentation/RCU/index.rst
+++ b/Documentation/RCU/index.rst
@@ -8,6 +8,7 @@ RCU concepts
    :maxdepth: 3
 
    arrayRCU
+   whatisRCU
    rcu
    listRCU
    NMI-RCU
diff --git a/Documentation/RCU/whatisRCU.rst b/Documentation/RCU/whatisRCU.rst
new file mode 100644
index 0000000..2f6f6eb
--- /dev/null
+++ b/Documentation/RCU/whatisRCU.rst
@@ -0,0 +1,1149 @@
+.. _whatisrcu_doc:
+
+What is RCU?  --  "Read, Copy, Update"
+======================================
+
+Please note that the "What is RCU?" LWN series is an excellent place
+to start learning about RCU:
+
+| 1.	What is RCU, Fundamentally?  http://lwn.net/Articles/262464/
+| 2.	What is RCU? Part 2: Usage   http://lwn.net/Articles/263130/
+| 3.	RCU part 3: the RCU API      http://lwn.net/Articles/264090/
+| 4.	The RCU API, 2010 Edition    http://lwn.net/Articles/418853/
+| 	2010 Big API Table           http://lwn.net/Articles/419086/
+| 5.	The RCU API, 2014 Edition    http://lwn.net/Articles/609904/
+|	2014 Big API Table           http://lwn.net/Articles/609973/
+
+
+What is RCU?
+
+RCU is a synchronization mechanism that was added to the Linux kernel
+during the 2.5 development effort that is optimized for read-mostly
+situations.  Although RCU is actually quite simple once you understand it,
+getting there can sometimes be a challenge.  Part of the problem is that
+most of the past descriptions of RCU have been written with the mistaken
+assumption that there is "one true way" to describe RCU.  Instead,
+the experience has been that different people must take different paths
+to arrive at an understanding of RCU.  This document provides several
+different paths, as follows:
+
+:ref:`1.	RCU OVERVIEW <1_whatisRCU>`
+
+:ref:`2.	WHAT IS RCU'S CORE API? <2_whatisRCU>`
+
+:ref:`3.	WHAT ARE SOME EXAMPLE USES OF CORE RCU API? <3_whatisRCU>`
+
+:ref:`4.	WHAT IF MY UPDATING THREAD CANNOT BLOCK? <4_whatisRCU>`
+
+:ref:`5.	WHAT ARE SOME SIMPLE IMPLEMENTATIONS OF RCU? <5_whatisRCU>`
+
+:ref:`6.	ANALOGY WITH READER-WRITER LOCKING <6_whatisRCU>`
+
+:ref:`7.	FULL LIST OF RCU APIs <7_whatisRCU>`
+
+:ref:`8.	ANSWERS TO QUICK QUIZZES <8_whatisRCU>`
+
+People who prefer starting with a conceptual overview should focus on
+Section 1, though most readers will profit by reading this section at
+some point.  People who prefer to start with an API that they can then
+experiment with should focus on Section 2.  People who prefer to start
+with example uses should focus on Sections 3 and 4.  People who need to
+understand the RCU implementation should focus on Section 5, then dive
+into the kernel source code.  People who reason best by analogy should
+focus on Section 6.  Section 7 serves as an index to the docbook API
+documentation, and Section 8 is the traditional answer key.
+
+So, start with the section that makes the most sense to you and your
+preferred method of learning.  If you need to know everything about
+everything, feel free to read the whole thing -- but if you are really
+that type of person, you have perused the source code and will therefore
+never need this document anyway.  ;-)
+
+.. _1_whatisRCU:
+
+1.  RCU OVERVIEW
+----------------
+
+The basic idea behind RCU is to split updates into "removal" and
+"reclamation" phases.  The removal phase removes references to data items
+within a data structure (possibly by replacing them with references to
+new versions of these data items), and can run concurrently with readers.
+The reason that it is safe to run the removal phase concurrently with
+readers is the semantics of modern CPUs guarantee that readers will see
+either the old or the new version of the data structure rather than a
+partially updated reference.  The reclamation phase does the work of reclaiming
+(e.g., freeing) the data items removed from the data structure during the
+removal phase.  Because reclaiming data items can disrupt any readers
+concurrently referencing those data items, the reclamation phase must
+not start until readers no longer hold references to those data items.
+
+Splitting the update into removal and reclamation phases permits the
+updater to perform the removal phase immediately, and to defer the
+reclamation phase until all readers active during the removal phase have
+completed, either by blocking until they finish or by registering a
+callback that is invoked after they finish.  Only readers that are active
+during the removal phase need be considered, because any reader starting
+after the removal phase will be unable to gain a reference to the removed
+data items, and therefore cannot be disrupted by the reclamation phase.
+
+So the typical RCU update sequence goes something like the following:
+
+a.	Remove pointers to a data structure, so that subsequent
+	readers cannot gain a reference to it.
+
+b.	Wait for all previous readers to complete their RCU read-side
+	critical sections.
+
+c.	At this point, there cannot be any readers who hold references
+	to the data structure, so it now may safely be reclaimed
+	(e.g., kfree()d).
+
+Step (b) above is the key idea underlying RCU's deferred destruction.
+The ability to wait until all readers are done allows RCU readers to
+use much lighter-weight synchronization, in some cases, absolutely no
+synchronization at all.  In contrast, in more conventional lock-based
+schemes, readers must use heavy-weight synchronization in order to
+prevent an updater from deleting the data structure out from under them.
+This is because lock-based updaters typically update data items in place,
+and must therefore exclude readers.  In contrast, RCU-based updaters
+typically take advantage of the fact that writes to single aligned
+pointers are atomic on modern CPUs, allowing atomic insertion, removal,
+and replacement of data items in a linked structure without disrupting
+readers.  Concurrent RCU readers can then continue accessing the old
+versions, and can dispense with the atomic operations, memory barriers,
+and communications cache misses that are so expensive on present-day
+SMP computer systems, even in absence of lock contention.
+
+In the three-step procedure shown above, the updater is performing both
+the removal and the reclamation step, but it is often helpful for an
+entirely different thread to do the reclamation, as is in fact the case
+in the Linux kernel's directory-entry cache (dcache).  Even if the same
+thread performs both the update step (step (a) above) and the reclamation
+step (step (c) above), it is often helpful to think of them separately.
+For example, RCU readers and updaters need not communicate at all,
+but RCU provides implicit low-overhead communication between readers
+and reclaimers, namely, in step (b) above.
+
+So how the heck can a reclaimer tell when a reader is done, given
+that readers are not doing any sort of synchronization operations???
+Read on to learn about how RCU's API makes this easy.
+
+.. _2_whatisRCU:
+
+2.  WHAT IS RCU'S CORE API?
+---------------------------
+
+The core RCU API is quite small:
+
+a.	rcu_read_lock()
+b.	rcu_read_unlock()
+c.	synchronize_rcu() / call_rcu()
+d.	rcu_assign_pointer()
+e.	rcu_dereference()
+
+There are many other members of the RCU API, but the rest can be
+expressed in terms of these five, though most implementations instead
+express synchronize_rcu() in terms of the call_rcu() callback API.
+
+The five core RCU APIs are described below, the other 18 will be enumerated
+later.  See the kernel docbook documentation for more info, or look directly
+at the function header comments.
+
+rcu_read_lock()
+^^^^^^^^^^^^^^^
+	void rcu_read_lock(void);
+
+	Used by a reader to inform the reclaimer that the reader is
+	entering an RCU read-side critical section.  It is illegal
+	to block while in an RCU read-side critical section, though
+	kernels built with CONFIG_PREEMPT_RCU can preempt RCU
+	read-side critical sections.  Any RCU-protected data structure
+	accessed during an RCU read-side critical section is guaranteed to
+	remain unreclaimed for the full duration of that critical section.
+	Reference counts may be used in conjunction with RCU to maintain
+	longer-term references to data structures.
+
+rcu_read_unlock()
+^^^^^^^^^^^^^^^^^
+	void rcu_read_unlock(void);
+
+	Used by a reader to inform the reclaimer that the reader is
+	exiting an RCU read-side critical section.  Note that RCU
+	read-side critical sections may be nested and/or overlapping.
+
+synchronize_rcu()
+^^^^^^^^^^^^^^^^^
+	void synchronize_rcu(void);
+
+	Marks the end of updater code and the beginning of reclaimer
+	code.  It does this by blocking until all pre-existing RCU
+	read-side critical sections on all CPUs have completed.
+	Note that synchronize_rcu() will **not** necessarily wait for
+	any subsequent RCU read-side critical sections to complete.
+	For example, consider the following sequence of events::
+
+	         CPU 0                  CPU 1                 CPU 2
+	     ----------------- ------------------------- ---------------
+	 1.  rcu_read_lock()
+	 2.                    enters synchronize_rcu()
+	 3.                                               rcu_read_lock()
+	 4.  rcu_read_unlock()
+	 5.                     exits synchronize_rcu()
+	 6.                                              rcu_read_unlock()
+
+	To reiterate, synchronize_rcu() waits only for ongoing RCU
+	read-side critical sections to complete, not necessarily for
+	any that begin after synchronize_rcu() is invoked.
+
+	Of course, synchronize_rcu() does not necessarily return
+	**immediately** after the last pre-existing RCU read-side critical
+	section completes.  For one thing, there might well be scheduling
+	delays.  For another thing, many RCU implementations process
+	requests in batches in order to improve efficiencies, which can
+	further delay synchronize_rcu().
+
+	Since synchronize_rcu() is the API that must figure out when
+	readers are done, its implementation is key to RCU.  For RCU
+	to be useful in all but the most read-intensive situations,
+	synchronize_rcu()'s overhead must also be quite small.
+
+	The call_rcu() API is a callback form of synchronize_rcu(),
+	and is described in more detail in a later section.  Instead of
+	blocking, it registers a function and argument which are invoked
+	after all ongoing RCU read-side critical sections have completed.
+	This callback variant is particularly useful in situations where
+	it is illegal to block or where update-side performance is
+	critically important.
+
+	However, the call_rcu() API should not be used lightly, as use
+	of the synchronize_rcu() API generally results in simpler code.
+	In addition, the synchronize_rcu() API has the nice property
+	of automatically limiting update rate should grace periods
+	be delayed.  This property results in system resilience in face
+	of denial-of-service attacks.  Code using call_rcu() should limit
+	update rate in order to gain this same sort of resilience.  See
+	checklist.txt for some approaches to limiting the update rate.
+
+rcu_assign_pointer()
+^^^^^^^^^^^^^^^^^^^^
+	void rcu_assign_pointer(p, typeof(p) v);
+
+	Yes, rcu_assign_pointer() **is** implemented as a macro, though it
+	would be cool to be able to declare a function in this manner.
+	(Compiler experts will no doubt disagree.)
+
+	The updater uses this function to assign a new value to an
+	RCU-protected pointer, in order to safely communicate the change
+	in value from the updater to the reader.  This macro does not
+	evaluate to an rvalue, but it does execute any memory-barrier
+	instructions required for a given CPU architecture.
+
+	Perhaps just as important, it serves to document (1) which
+	pointers are protected by RCU and (2) the point at which a
+	given structure becomes accessible to other CPUs.  That said,
+	rcu_assign_pointer() is most frequently used indirectly, via
+	the _rcu list-manipulation primitives such as list_add_rcu().
+
+rcu_dereference()
+^^^^^^^^^^^^^^^^^
+	typeof(p) rcu_dereference(p);
+
+	Like rcu_assign_pointer(), rcu_dereference() must be implemented
+	as a macro.
+
+	The reader uses rcu_dereference() to fetch an RCU-protected
+	pointer, which returns a value that may then be safely
+	dereferenced.  Note that rcu_dereference() does not actually
+	dereference the pointer, instead, it protects the pointer for
+	later dereferencing.  It also executes any needed memory-barrier
+	instructions for a given CPU architecture.  Currently, only Alpha
+	needs memory barriers within rcu_dereference() -- on other CPUs,
+	it compiles to nothing, not even a compiler directive.
+
+	Common coding practice uses rcu_dereference() to copy an
+	RCU-protected pointer to a local variable, then dereferences
+	this local variable, for example as follows::
+
+		p = rcu_dereference(head.next);
+		return p->data;
+
+	However, in this case, one could just as easily combine these
+	into one statement::
+
+		return rcu_dereference(head.next)->data;
+
+	If you are going to be fetching multiple fields from the
+	RCU-protected structure, using the local variable is of
+	course preferred.  Repeated rcu_dereference() calls look
+	ugly, do not guarantee that the same pointer will be returned
+	if an update happened while in the critical section, and incur
+	unnecessary overhead on Alpha CPUs.
+
+	Note that the value returned by rcu_dereference() is valid
+	only within the enclosing RCU read-side critical section [1]_.
+	For example, the following is **not** legal::
+
+		rcu_read_lock();
+		p = rcu_dereference(head.next);
+		rcu_read_unlock();
+		x = p->address;	/* BUG!!! */
+		rcu_read_lock();
+		y = p->data;	/* BUG!!! */
+		rcu_read_unlock();
+
+	Holding a reference from one RCU read-side critical section
+	to another is just as illegal as holding a reference from
+	one lock-based critical section to another!  Similarly,
+	using a reference outside of the critical section in which
+	it was acquired is just as illegal as doing so with normal
+	locking.
+
+	As with rcu_assign_pointer(), an important function of
+	rcu_dereference() is to document which pointers are protected by
+	RCU, in particular, flagging a pointer that is subject to changing
+	at any time, including immediately after the rcu_dereference().
+	And, again like rcu_assign_pointer(), rcu_dereference() is
+	typically used indirectly, via the _rcu list-manipulation
+	primitives, such as list_for_each_entry_rcu() [2]_.
+
+.. 	[1] The variant rcu_dereference_protected() can be used outside
+	of an RCU read-side critical section as long as the usage is
+	protected by locks acquired by the update-side code.  This variant
+	avoids the lockdep warning that would happen when using (for
+	example) rcu_dereference() without rcu_read_lock() protection.
+	Using rcu_dereference_protected() also has the advantage
+	of permitting compiler optimizations that rcu_dereference()
+	must prohibit.	The rcu_dereference_protected() variant takes
+	a lockdep expression to indicate which locks must be acquired
+	by the caller. If the indicated protection is not provided,
+	a lockdep splat is emitted.  See Documentation/RCU/Design/Requirements/Requirements.rst
+	and the API's code comments for more details and example usage.
+
+.. 	[2] If the list_for_each_entry_rcu() instance might be used by
+	update-side code as well as by RCU readers, then an additional
+	lockdep expression can be added to its list of arguments.
+	For example, given an additional "lock_is_held(&mylock)" argument,
+	the RCU lockdep code would complain only if this instance was
+	invoked outside of an RCU read-side critical section and without
+	the protection of mylock.
+
+The following diagram shows how each API communicates among the
+reader, updater, and reclaimer.
+::
+
+
+	    rcu_assign_pointer()
+	                            +--------+
+	    +---------------------->| reader |---------+
+	    |                       +--------+         |
+	    |                           |              |
+	    |                           |              | Protect:
+	    |                           |              | rcu_read_lock()
+	    |                           |              | rcu_read_unlock()
+	    |        rcu_dereference()  |              |
+	    +---------+                 |              |
+	    | updater |<----------------+              |
+	    +---------+                                V
+	    |                                    +-----------+
+	    +----------------------------------->| reclaimer |
+	                                         +-----------+
+	      Defer:
+	      synchronize_rcu() & call_rcu()
+
+
+The RCU infrastructure observes the time sequence of rcu_read_lock(),
+rcu_read_unlock(), synchronize_rcu(), and call_rcu() invocations in
+order to determine when (1) synchronize_rcu() invocations may return
+to their callers and (2) call_rcu() callbacks may be invoked.  Efficient
+implementations of the RCU infrastructure make heavy use of batching in
+order to amortize their overhead over many uses of the corresponding APIs.
+
+There are at least three flavors of RCU usage in the Linux kernel. The diagram
+above shows the most common one. On the updater side, the rcu_assign_pointer(),
+sychronize_rcu() and call_rcu() primitives used are the same for all three
+flavors. However for protection (on the reader side), the primitives used vary
+depending on the flavor:
+
+a.	rcu_read_lock() / rcu_read_unlock()
+	rcu_dereference()
+
+b.	rcu_read_lock_bh() / rcu_read_unlock_bh()
+	local_bh_disable() / local_bh_enable()
+	rcu_dereference_bh()
+
+c.	rcu_read_lock_sched() / rcu_read_unlock_sched()
+	preempt_disable() / preempt_enable()
+	local_irq_save() / local_irq_restore()
+	hardirq enter / hardirq exit
+	NMI enter / NMI exit
+	rcu_dereference_sched()
+
+These three flavors are used as follows:
+
+a.	RCU applied to normal data structures.
+
+b.	RCU applied to networking data structures that may be subjected
+	to remote denial-of-service attacks.
+
+c.	RCU applied to scheduler and interrupt/NMI-handler tasks.
+
+Again, most uses will be of (a).  The (b) and (c) cases are important
+for specialized uses, but are relatively uncommon.
+
+.. _3_whatisRCU:
+
+3.  WHAT ARE SOME EXAMPLE USES OF CORE RCU API?
+-----------------------------------------------
+
+This section shows a simple use of the core RCU API to protect a
+global pointer to a dynamically allocated structure.  More-typical
+uses of RCU may be found in :ref:`listRCU.rst <list_rcu_doc>`,
+:ref:`arrayRCU.rst <array_rcu_doc>`, and :ref:`NMI-RCU.rst <NMI_rcu_doc>`.
+::
+
+	struct foo {
+		int a;
+		char b;
+		long c;
+	};
+	DEFINE_SPINLOCK(foo_mutex);
+
+	struct foo __rcu *gbl_foo;
+
+	/*
+	 * Create a new struct foo that is the same as the one currently
+	 * pointed to by gbl_foo, except that field "a" is replaced
+	 * with "new_a".  Points gbl_foo to the new structure, and
+	 * frees up the old structure after a grace period.
+	 *
+	 * Uses rcu_assign_pointer() to ensure that concurrent readers
+	 * see the initialized version of the new structure.
+	 *
+	 * Uses synchronize_rcu() to ensure that any readers that might
+	 * have references to the old structure complete before freeing
+	 * the old structure.
+	 */
+	void foo_update_a(int new_a)
+	{
+		struct foo *new_fp;
+		struct foo *old_fp;
+
+		new_fp = kmalloc(sizeof(*new_fp), GFP_KERNEL);
+		spin_lock(&foo_mutex);
+		old_fp = rcu_dereference_protected(gbl_foo, lockdep_is_held(&foo_mutex));
+		*new_fp = *old_fp;
+		new_fp->a = new_a;
+		rcu_assign_pointer(gbl_foo, new_fp);
+		spin_unlock(&foo_mutex);
+		synchronize_rcu();
+		kfree(old_fp);
+	}
+
+	/*
+	 * Return the value of field "a" of the current gbl_foo
+	 * structure.  Use rcu_read_lock() and rcu_read_unlock()
+	 * to ensure that the structure does not get deleted out
+	 * from under us, and use rcu_dereference() to ensure that
+	 * we see the initialized version of the structure (important
+	 * for DEC Alpha and for people reading the code).
+	 */
+	int foo_get_a(void)
+	{
+		int retval;
+
+		rcu_read_lock();
+		retval = rcu_dereference(gbl_foo)->a;
+		rcu_read_unlock();
+		return retval;
+	}
+
+So, to sum up:
+
+-	Use rcu_read_lock() and rcu_read_unlock() to guard RCU
+	read-side critical sections.
+
+-	Within an RCU read-side critical section, use rcu_dereference()
+	to dereference RCU-protected pointers.
+
+-	Use some solid scheme (such as locks or semaphores) to
+	keep concurrent updates from interfering with each other.
+
+-	Use rcu_assign_pointer() to update an RCU-protected pointer.
+	This primitive protects concurrent readers from the updater,
+	**not** concurrent updates from each other!  You therefore still
+	need to use locking (or something similar) to keep concurrent
+	rcu_assign_pointer() primitives from interfering with each other.
+
+-	Use synchronize_rcu() **after** removing a data element from an
+	RCU-protected data structure, but **before** reclaiming/freeing
+	the data element, in order to wait for the completion of all
+	RCU read-side critical sections that might be referencing that
+	data item.
+
+See checklist.txt for additional rules to follow when using RCU.
+And again, more-typical uses of RCU may be found in :ref:`listRCU.rst
+<list_rcu_doc>`, :ref:`arrayRCU.rst <array_rcu_doc>`, and :ref:`NMI-RCU.rst
+<NMI_rcu_doc>`.
+
+.. _4_whatisRCU:
+
+4.  WHAT IF MY UPDATING THREAD CANNOT BLOCK?
+--------------------------------------------
+
+In the example above, foo_update_a() blocks until a grace period elapses.
+This is quite simple, but in some cases one cannot afford to wait so
+long -- there might be other high-priority work to be done.
+
+In such cases, one uses call_rcu() rather than synchronize_rcu().
+The call_rcu() API is as follows::
+
+	void call_rcu(struct rcu_head * head,
+		      void (*func)(struct rcu_head *head));
+
+This function invokes func(head) after a grace period has elapsed.
+This invocation might happen from either softirq or process context,
+so the function is not permitted to block.  The foo struct needs to
+have an rcu_head structure added, perhaps as follows::
+
+	struct foo {
+		int a;
+		char b;
+		long c;
+		struct rcu_head rcu;
+	};
+
+The foo_update_a() function might then be written as follows::
+
+	/*
+	 * Create a new struct foo that is the same as the one currently
+	 * pointed to by gbl_foo, except that field "a" is replaced
+	 * with "new_a".  Points gbl_foo to the new structure, and
+	 * frees up the old structure after a grace period.
+	 *
+	 * Uses rcu_assign_pointer() to ensure that concurrent readers
+	 * see the initialized version of the new structure.
+	 *
+	 * Uses call_rcu() to ensure that any readers that might have
+	 * references to the old structure complete before freeing the
+	 * old structure.
+	 */
+	void foo_update_a(int new_a)
+	{
+		struct foo *new_fp;
+		struct foo *old_fp;
+
+		new_fp = kmalloc(sizeof(*new_fp), GFP_KERNEL);
+		spin_lock(&foo_mutex);
+		old_fp = rcu_dereference_protected(gbl_foo, lockdep_is_held(&foo_mutex));
+		*new_fp = *old_fp;
+		new_fp->a = new_a;
+		rcu_assign_pointer(gbl_foo, new_fp);
+		spin_unlock(&foo_mutex);
+		call_rcu(&old_fp->rcu, foo_reclaim);
+	}
+
+The foo_reclaim() function might appear as follows::
+
+	void foo_reclaim(struct rcu_head *rp)
+	{
+		struct foo *fp = container_of(rp, struct foo, rcu);
+
+		foo_cleanup(fp->a);
+
+		kfree(fp);
+	}
+
+The container_of() primitive is a macro that, given a pointer into a
+struct, the type of the struct, and the pointed-to field within the
+struct, returns a pointer to the beginning of the struct.
+
+The use of call_rcu() permits the caller of foo_update_a() to
+immediately regain control, without needing to worry further about the
+old version of the newly updated element.  It also clearly shows the
+RCU distinction between updater, namely foo_update_a(), and reclaimer,
+namely foo_reclaim().
+
+The summary of advice is the same as for the previous section, except
+that we are now using call_rcu() rather than synchronize_rcu():
+
+-	Use call_rcu() **after** removing a data element from an
+	RCU-protected data structure in order to register a callback
+	function that will be invoked after the completion of all RCU
+	read-side critical sections that might be referencing that
+	data item.
+
+If the callback for call_rcu() is not doing anything more than calling
+kfree() on the structure, you can use kfree_rcu() instead of call_rcu()
+to avoid having to write your own callback::
+
+	kfree_rcu(old_fp, rcu);
+
+Again, see checklist.txt for additional rules governing the use of RCU.
+
+.. _5_whatisRCU:
+
+5.  WHAT ARE SOME SIMPLE IMPLEMENTATIONS OF RCU?
+------------------------------------------------
+
+One of the nice things about RCU is that it has extremely simple "toy"
+implementations that are a good first step towards understanding the
+production-quality implementations in the Linux kernel.  This section
+presents two such "toy" implementations of RCU, one that is implemented
+in terms of familiar locking primitives, and another that more closely
+resembles "classic" RCU.  Both are way too simple for real-world use,
+lacking both functionality and performance.  However, they are useful
+in getting a feel for how RCU works.  See kernel/rcu/update.c for a
+production-quality implementation, and see:
+
+	http://www.rdrop.com/users/paulmck/RCU
+
+for papers describing the Linux kernel RCU implementation.  The OLS'01
+and OLS'02 papers are a good introduction, and the dissertation provides
+more details on the current implementation as of early 2004.
+
+
+5A.  "TOY" IMPLEMENTATION #1: LOCKING
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+This section presents a "toy" RCU implementation that is based on
+familiar locking primitives.  Its overhead makes it a non-starter for
+real-life use, as does its lack of scalability.  It is also unsuitable
+for realtime use, since it allows scheduling latency to "bleed" from
+one read-side critical section to another.  It also assumes recursive
+reader-writer locks:  If you try this with non-recursive locks, and
+you allow nested rcu_read_lock() calls, you can deadlock.
+
+However, it is probably the easiest implementation to relate to, so is
+a good starting point.
+
+It is extremely simple::
+
+	static DEFINE_RWLOCK(rcu_gp_mutex);
+
+	void rcu_read_lock(void)
+	{
+		read_lock(&rcu_gp_mutex);
+	}
+
+	void rcu_read_unlock(void)
+	{
+		read_unlock(&rcu_gp_mutex);
+	}
+
+	void synchronize_rcu(void)
+	{
+		write_lock(&rcu_gp_mutex);
+		smp_mb__after_spinlock();
+		write_unlock(&rcu_gp_mutex);
+	}
+
+[You can ignore rcu_assign_pointer() and rcu_dereference() without missing
+much.  But here are simplified versions anyway.  And whatever you do,
+don't forget about them when submitting patches making use of RCU!]::
+
+	#define rcu_assign_pointer(p, v) \
+	({ \
+		smp_store_release(&(p), (v)); \
+	})
+
+	#define rcu_dereference(p) \
+	({ \
+		typeof(p) _________p1 = READ_ONCE(p); \
+		(_________p1); \
+	})
+
+
+The rcu_read_lock() and rcu_read_unlock() primitive read-acquire
+and release a global reader-writer lock.  The synchronize_rcu()
+primitive write-acquires this same lock, then releases it.  This means
+that once synchronize_rcu() exits, all RCU read-side critical sections
+that were in progress before synchronize_rcu() was called are guaranteed
+to have completed -- there is no way that synchronize_rcu() would have
+been able to write-acquire the lock otherwise.  The smp_mb__after_spinlock()
+promotes synchronize_rcu() to a full memory barrier in compliance with
+the "Memory-Barrier Guarantees" listed in:
+
+	Documentation/RCU/Design/Requirements/Requirements.rst
+
+It is possible to nest rcu_read_lock(), since reader-writer locks may
+be recursively acquired.  Note also that rcu_read_lock() is immune
+from deadlock (an important property of RCU).  The reason for this is
+that the only thing that can block rcu_read_lock() is a synchronize_rcu().
+But synchronize_rcu() does not acquire any locks while holding rcu_gp_mutex,
+so there can be no deadlock cycle.
+
+.. _quiz_1:
+
+Quick Quiz #1:
+		Why is this argument naive?  How could a deadlock
+		occur when using this algorithm in a real-world Linux
+		kernel?  How could this deadlock be avoided?
+
+:ref:`Answers to Quick Quiz <8_whatisRCU>`
+
+5B.  "TOY" EXAMPLE #2: CLASSIC RCU
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+This section presents a "toy" RCU implementation that is based on
+"classic RCU".  It is also short on performance (but only for updates) and
+on features such as hotplug CPU and the ability to run in CONFIG_PREEMPT
+kernels.  The definitions of rcu_dereference() and rcu_assign_pointer()
+are the same as those shown in the preceding section, so they are omitted.
+::
+
+	void rcu_read_lock(void) { }
+
+	void rcu_read_unlock(void) { }
+
+	void synchronize_rcu(void)
+	{
+		int cpu;
+
+		for_each_possible_cpu(cpu)
+			run_on(cpu);
+	}
+
+Note that rcu_read_lock() and rcu_read_unlock() do absolutely nothing.
+This is the great strength of classic RCU in a non-preemptive kernel:
+read-side overhead is precisely zero, at least on non-Alpha CPUs.
+And there is absolutely no way that rcu_read_lock() can possibly
+participate in a deadlock cycle!
+
+The implementation of synchronize_rcu() simply schedules itself on each
+CPU in turn.  The run_on() primitive can be implemented straightforwardly
+in terms of the sched_setaffinity() primitive.  Of course, a somewhat less
+"toy" implementation would restore the affinity upon completion rather
+than just leaving all tasks running on the last CPU, but when I said
+"toy", I meant **toy**!
+
+So how the heck is this supposed to work???
+
+Remember that it is illegal to block while in an RCU read-side critical
+section.  Therefore, if a given CPU executes a context switch, we know
+that it must have completed all preceding RCU read-side critical sections.
+Once **all** CPUs have executed a context switch, then **all** preceding
+RCU read-side critical sections will have completed.
+
+So, suppose that we remove a data item from its structure and then invoke
+synchronize_rcu().  Once synchronize_rcu() returns, we are guaranteed
+that there are no RCU read-side critical sections holding a reference
+to that data item, so we can safely reclaim it.
+
+.. _quiz_2:
+
+Quick Quiz #2:
+		Give an example where Classic RCU's read-side
+		overhead is **negative**.
+
+:ref:`Answers to Quick Quiz <8_whatisRCU>`
+
+.. _quiz_3:
+
+Quick Quiz #3:
+		If it is illegal to block in an RCU read-side
+		critical section, what the heck do you do in
+		PREEMPT_RT, where normal spinlocks can block???
+
+:ref:`Answers to Quick Quiz <8_whatisRCU>`
+
+.. _6_whatisRCU:
+
+6.  ANALOGY WITH READER-WRITER LOCKING
+--------------------------------------
+
+Although RCU can be used in many different ways, a very common use of
+RCU is analogous to reader-writer locking.  The following unified
+diff shows how closely related RCU and reader-writer locking can be.
+::
+
+	@@ -5,5 +5,5 @@ struct el {
+	 	int data;
+	 	/* Other data fields */
+	 };
+	-rwlock_t listmutex;
+	+spinlock_t listmutex;
+	 struct el head;
+
+	@@ -13,15 +14,15 @@
+		struct list_head *lp;
+		struct el *p;
+
+	-	read_lock(&listmutex);
+	-	list_for_each_entry(p, head, lp) {
+	+	rcu_read_lock();
+	+	list_for_each_entry_rcu(p, head, lp) {
+			if (p->key == key) {
+				*result = p->data;
+	-			read_unlock(&listmutex);
+	+			rcu_read_unlock();
+				return 1;
+			}
+		}
+	-	read_unlock(&listmutex);
+	+	rcu_read_unlock();
+		return 0;
+	 }
+
+	@@ -29,15 +30,16 @@
+	 {
+		struct el *p;
+
+	-	write_lock(&listmutex);
+	+	spin_lock(&listmutex);
+		list_for_each_entry(p, head, lp) {
+			if (p->key == key) {
+	-			list_del(&p->list);
+	-			write_unlock(&listmutex);
+	+			list_del_rcu(&p->list);
+	+			spin_unlock(&listmutex);
+	+			synchronize_rcu();
+				kfree(p);
+				return 1;
+			}
+		}
+	-	write_unlock(&listmutex);
+	+	spin_unlock(&listmutex);
+		return 0;
+	 }
+
+Or, for those who prefer a side-by-side listing::
+
+ 1 struct el {                          1 struct el {
+ 2   struct list_head list;             2   struct list_head list;
+ 3   long key;                          3   long key;
+ 4   spinlock_t mutex;                  4   spinlock_t mutex;
+ 5   int data;                          5   int data;
+ 6   /* Other data fields */            6   /* Other data fields */
+ 7 };                                   7 };
+ 8 rwlock_t listmutex;                  8 spinlock_t listmutex;
+ 9 struct el head;                      9 struct el head;
+
+::
+
+  1 int search(long key, int *result)    1 int search(long key, int *result)
+  2 {                                    2 {
+  3   struct list_head *lp;              3   struct list_head *lp;
+  4   struct el *p;                      4   struct el *p;
+  5                                      5
+  6   read_lock(&listmutex);             6   rcu_read_lock();
+  7   list_for_each_entry(p, head, lp) { 7   list_for_each_entry_rcu(p, head, lp) {
+  8     if (p->key == key) {             8     if (p->key == key) {
+  9       *result = p->data;             9       *result = p->data;
+ 10       read_unlock(&listmutex);      10       rcu_read_unlock();
+ 11       return 1;                     11       return 1;
+ 12     }                               12     }
+ 13   }                                 13   }
+ 14   read_unlock(&listmutex);          14   rcu_read_unlock();
+ 15   return 0;                         15   return 0;
+ 16 }                                   16 }
+
+::
+
+  1 int delete(long key)                 1 int delete(long key)
+  2 {                                    2 {
+  3   struct el *p;                      3   struct el *p;
+  4                                      4
+  5   write_lock(&listmutex);            5   spin_lock(&listmutex);
+  6   list_for_each_entry(p, head, lp) { 6   list_for_each_entry(p, head, lp) {
+  7     if (p->key == key) {             7     if (p->key == key) {
+  8       list_del(&p->list);            8       list_del_rcu(&p->list);
+  9       write_unlock(&listmutex);      9       spin_unlock(&listmutex);
+                                        10       synchronize_rcu();
+ 10       kfree(p);                     11       kfree(p);
+ 11       return 1;                     12       return 1;
+ 12     }                               13     }
+ 13   }                                 14   }
+ 14   write_unlock(&listmutex);         15   spin_unlock(&listmutex);
+ 15   return 0;                         16   return 0;
+ 16 }                                   17 }
+
+Either way, the differences are quite small.  Read-side locking moves
+to rcu_read_lock() and rcu_read_unlock, update-side locking moves from
+a reader-writer lock to a simple spinlock, and a synchronize_rcu()
+precedes the kfree().
+
+However, there is one potential catch: the read-side and update-side
+critical sections can now run concurrently.  In many cases, this will
+not be a problem, but it is necessary to check carefully regardless.
+For example, if multiple independent list updates must be seen as
+a single atomic update, converting to RCU will require special care.
+
+Also, the presence of synchronize_rcu() means that the RCU version of
+delete() can now block.  If this is a problem, there is a callback-based
+mechanism that never blocks, namely call_rcu() or kfree_rcu(), that can
+be used in place of synchronize_rcu().
+
+.. _7_whatisRCU:
+
+7.  FULL LIST OF RCU APIs
+-------------------------
+
+The RCU APIs are documented in docbook-format header comments in the
+Linux-kernel source code, but it helps to have a full list of the
+APIs, since there does not appear to be a way to categorize them
+in docbook.  Here is the list, by category.
+
+RCU list traversal::
+
+	list_entry_rcu
+	list_first_entry_rcu
+	list_next_rcu
+	list_for_each_entry_rcu
+	list_for_each_entry_continue_rcu
+	list_for_each_entry_from_rcu
+	hlist_first_rcu
+	hlist_next_rcu
+	hlist_pprev_rcu
+	hlist_for_each_entry_rcu
+	hlist_for_each_entry_rcu_bh
+	hlist_for_each_entry_from_rcu
+	hlist_for_each_entry_continue_rcu
+	hlist_for_each_entry_continue_rcu_bh
+	hlist_nulls_first_rcu
+	hlist_nulls_for_each_entry_rcu
+	hlist_bl_first_rcu
+	hlist_bl_for_each_entry_rcu
+
+RCU pointer/list udate::
+
+	rcu_assign_pointer
+	list_add_rcu
+	list_add_tail_rcu
+	list_del_rcu
+	list_replace_rcu
+	hlist_add_behind_rcu
+	hlist_add_before_rcu
+	hlist_add_head_rcu
+	hlist_del_rcu
+	hlist_del_init_rcu
+	hlist_replace_rcu
+	list_splice_init_rcu()
+	hlist_nulls_del_init_rcu
+	hlist_nulls_del_rcu
+	hlist_nulls_add_head_rcu
+	hlist_bl_add_head_rcu
+	hlist_bl_del_init_rcu
+	hlist_bl_del_rcu
+	hlist_bl_set_first_rcu
+
+RCU::
+
+	Critical sections	Grace period		Barrier
+
+	rcu_read_lock		synchronize_net		rcu_barrier
+	rcu_read_unlock		synchronize_rcu
+	rcu_dereference		synchronize_rcu_expedited
+	rcu_read_lock_held	call_rcu
+	rcu_dereference_check	kfree_rcu
+	rcu_dereference_protected
+
+bh::
+
+	Critical sections	Grace period		Barrier
+
+	rcu_read_lock_bh	call_rcu		rcu_barrier
+	rcu_read_unlock_bh	synchronize_rcu
+	[local_bh_disable]	synchronize_rcu_expedited
+	[and friends]
+	rcu_dereference_bh
+	rcu_dereference_bh_check
+	rcu_dereference_bh_protected
+	rcu_read_lock_bh_held
+
+sched::
+
+	Critical sections	Grace period		Barrier
+
+	rcu_read_lock_sched	call_rcu		rcu_barrier
+	rcu_read_unlock_sched	synchronize_rcu
+	[preempt_disable]	synchronize_rcu_expedited
+	[and friends]
+	rcu_read_lock_sched_notrace
+	rcu_read_unlock_sched_notrace
+	rcu_dereference_sched
+	rcu_dereference_sched_check
+	rcu_dereference_sched_protected
+	rcu_read_lock_sched_held
+
+
+SRCU::
+
+	Critical sections	Grace period		Barrier
+
+	srcu_read_lock		call_srcu		srcu_barrier
+	srcu_read_unlock	synchronize_srcu
+	srcu_dereference	synchronize_srcu_expedited
+	srcu_dereference_check
+	srcu_read_lock_held
+
+SRCU: Initialization/cleanup::
+
+	DEFINE_SRCU
+	DEFINE_STATIC_SRCU
+	init_srcu_struct
+	cleanup_srcu_struct
+
+All: lockdep-checked RCU-protected pointer access::
+
+	rcu_access_pointer
+	rcu_dereference_raw
+	RCU_LOCKDEP_WARN
+	rcu_sleep_check
+	RCU_NONIDLE
+
+See the comment headers in the source code (or the docbook generated
+from them) for more information.
+
+However, given that there are no fewer than four families of RCU APIs
+in the Linux kernel, how do you choose which one to use?  The following
+list can be helpful:
+
+a.	Will readers need to block?  If so, you need SRCU.
+
+b.	What about the -rt patchset?  If readers would need to block
+	in an non-rt kernel, you need SRCU.  If readers would block
+	in a -rt kernel, but not in a non-rt kernel, SRCU is not
+	necessary.  (The -rt patchset turns spinlocks into sleeplocks,
+	hence this distinction.)
+
+c.	Do you need to treat NMI handlers, hardirq handlers,
+	and code segments with preemption disabled (whether
+	via preempt_disable(), local_irq_save(), local_bh_disable(),
+	or some other mechanism) as if they were explicit RCU readers?
+	If so, RCU-sched is the only choice that will work for you.
+
+d.	Do you need RCU grace periods to complete even in the face
+	of softirq monopolization of one or more of the CPUs?  For
+	example, is your code subject to network-based denial-of-service
+	attacks?  If so, you should disable softirq across your readers,
+	for example, by using rcu_read_lock_bh().
+
+e.	Is your workload too update-intensive for normal use of
+	RCU, but inappropriate for other synchronization mechanisms?
+	If so, consider SLAB_TYPESAFE_BY_RCU (which was originally
+	named SLAB_DESTROY_BY_RCU).  But please be careful!
+
+f.	Do you need read-side critical sections that are respected
+	even though they are in the middle of the idle loop, during
+	user-mode execution, or on an offlined CPU?  If so, SRCU is the
+	only choice that will work for you.
+
+g.	Otherwise, use RCU.
+
+Of course, this all assumes that you have determined that RCU is in fact
+the right tool for your job.
+
+.. _8_whatisRCU:
+
+8.  ANSWERS TO QUICK QUIZZES
+----------------------------
+
+Quick Quiz #1:
+		Why is this argument naive?  How could a deadlock
+		occur when using this algorithm in a real-world Linux
+		kernel?  [Referring to the lock-based "toy" RCU
+		algorithm.]
+
+Answer:
+		Consider the following sequence of events:
+
+		1.	CPU 0 acquires some unrelated lock, call it
+			"problematic_lock", disabling irq via
+			spin_lock_irqsave().
+
+		2.	CPU 1 enters synchronize_rcu(), write-acquiring
+			rcu_gp_mutex.
+
+		3.	CPU 0 enters rcu_read_lock(), but must wait
+			because CPU 1 holds rcu_gp_mutex.
+
+		4.	CPU 1 is interrupted, and the irq handler
+			attempts to acquire problematic_lock.
+
+		The system is now deadlocked.
+
+		One way to avoid this deadlock is to use an approach like
+		that of CONFIG_PREEMPT_RT, where all normal spinlocks
+		become blocking locks, and all irq handlers execute in
+		the context of special tasks.  In this case, in step 4
+		above, the irq handler would block, allowing CPU 1 to
+		release rcu_gp_mutex, avoiding the deadlock.
+
+		Even in the absence of deadlock, this RCU implementation
+		allows latency to "bleed" from readers to other
+		readers through synchronize_rcu().  To see this,
+		consider task A in an RCU read-side critical section
+		(thus read-holding rcu_gp_mutex), task B blocked
+		attempting to write-acquire rcu_gp_mutex, and
+		task C blocked in rcu_read_lock() attempting to
+		read_acquire rcu_gp_mutex.  Task A's RCU read-side
+		latency is holding up task C, albeit indirectly via
+		task B.
+
+		Realtime RCU implementations therefore use a counter-based
+		approach where tasks in RCU read-side critical sections
+		cannot be blocked by tasks executing synchronize_rcu().
+
+:ref:`Back to Quick Quiz #1 <quiz_1>`
+
+Quick Quiz #2:
+		Give an example where Classic RCU's read-side
+		overhead is **negative**.
+
+Answer:
+		Imagine a single-CPU system with a non-CONFIG_PREEMPT
+		kernel where a routing table is used by process-context
+		code, but can be updated by irq-context code (for example,
+		by an "ICMP REDIRECT" packet).	The usual way of handling
+		this would be to have the process-context code disable
+		interrupts while searching the routing table.  Use of
+		RCU allows such interrupt-disabling to be dispensed with.
+		Thus, without RCU, you pay the cost of disabling interrupts,
+		and with RCU you don't.
+
+		One can argue that the overhead of RCU in this
+		case is negative with respect to the single-CPU
+		interrupt-disabling approach.  Others might argue that
+		the overhead of RCU is merely zero, and that replacing
+		the positive overhead of the interrupt-disabling scheme
+		with the zero-overhead RCU scheme does not constitute
+		negative overhead.
+
+		In real life, of course, things are more complex.  But
+		even the theoretical possibility of negative overhead for
+		a synchronization primitive is a bit unexpected.  ;-)
+
+:ref:`Back to Quick Quiz #2 <quiz_2>`
+
+Quick Quiz #3:
+		If it is illegal to block in an RCU read-side
+		critical section, what the heck do you do in
+		PREEMPT_RT, where normal spinlocks can block???
+
+Answer:
+		Just as PREEMPT_RT permits preemption of spinlock
+		critical sections, it permits preemption of RCU
+		read-side critical sections.  It also permits
+		spinlocks blocking while in RCU read-side critical
+		sections.
+
+		Why the apparent inconsistency?  Because it is
+		possible to use priority boosting to keep the RCU
+		grace periods short if need be (for example, if running
+		short of memory).  In contrast, if blocking waiting
+		for (say) network reception, there is no way to know
+		what should be boosted.  Especially given that the
+		process we need to boost might well be a human being
+		who just went out for a pizza or something.  And although
+		a computer-operated cattle prod might arouse serious
+		interest, it might also provoke serious objections.
+		Besides, how does the computer know what pizza parlor
+		the human being went to???
+
+:ref:`Back to Quick Quiz #3 <quiz_3>`
+
+ACKNOWLEDGEMENTS
+
+My thanks to the people who helped make this human-readable, including
+Jon Walpole, Josh Triplett, Serge Hallyn, Suzanne Wood, and Alan Stern.
+
+
+For more information, see http://www.rdrop.com/users/paulmck/RCU.
diff --git a/Documentation/RCU/whatisRCU.txt b/Documentation/RCU/whatisRCU.txt
deleted file mode 100644
index 58ba05c..0000000
--- a/Documentation/RCU/whatisRCU.txt
+++ /dev/null
@@ -1,1079 +0,0 @@
-What is RCU?  --  "Read, Copy, Update"
-
-Please note that the "What is RCU?" LWN series is an excellent place
-to start learning about RCU:
-
-1.	What is RCU, Fundamentally?  http://lwn.net/Articles/262464/
-2.	What is RCU? Part 2: Usage   http://lwn.net/Articles/263130/
-3.	RCU part 3: the RCU API      http://lwn.net/Articles/264090/
-4.	The RCU API, 2010 Edition    http://lwn.net/Articles/418853/
-	2010 Big API Table           http://lwn.net/Articles/419086/
-5.	The RCU API, 2014 Edition    http://lwn.net/Articles/609904/
-	2014 Big API Table           http://lwn.net/Articles/609973/
-
-
-What is RCU?
-
-RCU is a synchronization mechanism that was added to the Linux kernel
-during the 2.5 development effort that is optimized for read-mostly
-situations.  Although RCU is actually quite simple once you understand it,
-getting there can sometimes be a challenge.  Part of the problem is that
-most of the past descriptions of RCU have been written with the mistaken
-assumption that there is "one true way" to describe RCU.  Instead,
-the experience has been that different people must take different paths
-to arrive at an understanding of RCU.  This document provides several
-different paths, as follows:
-
-1.	RCU OVERVIEW
-2.	WHAT IS RCU'S CORE API?
-3.	WHAT ARE SOME EXAMPLE USES OF CORE RCU API?
-4.	WHAT IF MY UPDATING THREAD CANNOT BLOCK?
-5.	WHAT ARE SOME SIMPLE IMPLEMENTATIONS OF RCU?
-6.	ANALOGY WITH READER-WRITER LOCKING
-7.	FULL LIST OF RCU APIs
-8.	ANSWERS TO QUICK QUIZZES
-
-People who prefer starting with a conceptual overview should focus on
-Section 1, though most readers will profit by reading this section at
-some point.  People who prefer to start with an API that they can then
-experiment with should focus on Section 2.  People who prefer to start
-with example uses should focus on Sections 3 and 4.  People who need to
-understand the RCU implementation should focus on Section 5, then dive
-into the kernel source code.  People who reason best by analogy should
-focus on Section 6.  Section 7 serves as an index to the docbook API
-documentation, and Section 8 is the traditional answer key.
-
-So, start with the section that makes the most sense to you and your
-preferred method of learning.  If you need to know everything about
-everything, feel free to read the whole thing -- but if you are really
-that type of person, you have perused the source code and will therefore
-never need this document anyway.  ;-)
-
-
-1.  RCU OVERVIEW
-
-The basic idea behind RCU is to split updates into "removal" and
-"reclamation" phases.  The removal phase removes references to data items
-within a data structure (possibly by replacing them with references to
-new versions of these data items), and can run concurrently with readers.
-The reason that it is safe to run the removal phase concurrently with
-readers is the semantics of modern CPUs guarantee that readers will see
-either the old or the new version of the data structure rather than a
-partially updated reference.  The reclamation phase does the work of reclaiming
-(e.g., freeing) the data items removed from the data structure during the
-removal phase.  Because reclaiming data items can disrupt any readers
-concurrently referencing those data items, the reclamation phase must
-not start until readers no longer hold references to those data items.
-
-Splitting the update into removal and reclamation phases permits the
-updater to perform the removal phase immediately, and to defer the
-reclamation phase until all readers active during the removal phase have
-completed, either by blocking until they finish or by registering a
-callback that is invoked after they finish.  Only readers that are active
-during the removal phase need be considered, because any reader starting
-after the removal phase will be unable to gain a reference to the removed
-data items, and therefore cannot be disrupted by the reclamation phase.
-
-So the typical RCU update sequence goes something like the following:
-
-a.	Remove pointers to a data structure, so that subsequent
-	readers cannot gain a reference to it.
-
-b.	Wait for all previous readers to complete their RCU read-side
-	critical sections.
-
-c.	At this point, there cannot be any readers who hold references
-	to the data structure, so it now may safely be reclaimed
-	(e.g., kfree()d).
-
-Step (b) above is the key idea underlying RCU's deferred destruction.
-The ability to wait until all readers are done allows RCU readers to
-use much lighter-weight synchronization, in some cases, absolutely no
-synchronization at all.  In contrast, in more conventional lock-based
-schemes, readers must use heavy-weight synchronization in order to
-prevent an updater from deleting the data structure out from under them.
-This is because lock-based updaters typically update data items in place,
-and must therefore exclude readers.  In contrast, RCU-based updaters
-typically take advantage of the fact that writes to single aligned
-pointers are atomic on modern CPUs, allowing atomic insertion, removal,
-and replacement of data items in a linked structure without disrupting
-readers.  Concurrent RCU readers can then continue accessing the old
-versions, and can dispense with the atomic operations, memory barriers,
-and communications cache misses that are so expensive on present-day
-SMP computer systems, even in absence of lock contention.
-
-In the three-step procedure shown above, the updater is performing both
-the removal and the reclamation step, but it is often helpful for an
-entirely different thread to do the reclamation, as is in fact the case
-in the Linux kernel's directory-entry cache (dcache).  Even if the same
-thread performs both the update step (step (a) above) and the reclamation
-step (step (c) above), it is often helpful to think of them separately.
-For example, RCU readers and updaters need not communicate at all,
-but RCU provides implicit low-overhead communication between readers
-and reclaimers, namely, in step (b) above.
-
-So how the heck can a reclaimer tell when a reader is done, given
-that readers are not doing any sort of synchronization operations???
-Read on to learn about how RCU's API makes this easy.
-
-
-2.  WHAT IS RCU'S CORE API?
-
-The core RCU API is quite small:
-
-a.	rcu_read_lock()
-b.	rcu_read_unlock()
-c.	synchronize_rcu() / call_rcu()
-d.	rcu_assign_pointer()
-e.	rcu_dereference()
-
-There are many other members of the RCU API, but the rest can be
-expressed in terms of these five, though most implementations instead
-express synchronize_rcu() in terms of the call_rcu() callback API.
-
-The five core RCU APIs are described below, the other 18 will be enumerated
-later.  See the kernel docbook documentation for more info, or look directly
-at the function header comments.
-
-rcu_read_lock()
-
-	void rcu_read_lock(void);
-
-	Used by a reader to inform the reclaimer that the reader is
-	entering an RCU read-side critical section.  It is illegal
-	to block while in an RCU read-side critical section, though
-	kernels built with CONFIG_PREEMPT_RCU can preempt RCU
-	read-side critical sections.  Any RCU-protected data structure
-	accessed during an RCU read-side critical section is guaranteed to
-	remain unreclaimed for the full duration of that critical section.
-	Reference counts may be used in conjunction with RCU to maintain
-	longer-term references to data structures.
-
-rcu_read_unlock()
-
-	void rcu_read_unlock(void);
-
-	Used by a reader to inform the reclaimer that the reader is
-	exiting an RCU read-side critical section.  Note that RCU
-	read-side critical sections may be nested and/or overlapping.
-
-synchronize_rcu()
-
-	void synchronize_rcu(void);
-
-	Marks the end of updater code and the beginning of reclaimer
-	code.  It does this by blocking until all pre-existing RCU
-	read-side critical sections on all CPUs have completed.
-	Note that synchronize_rcu() will -not- necessarily wait for
-	any subsequent RCU read-side critical sections to complete.
-	For example, consider the following sequence of events:
-
-	         CPU 0                  CPU 1                 CPU 2
-	     ----------------- ------------------------- ---------------
-	 1.  rcu_read_lock()
-	 2.                    enters synchronize_rcu()
-	 3.                                               rcu_read_lock()
-	 4.  rcu_read_unlock()
-	 5.                     exits synchronize_rcu()
-	 6.                                              rcu_read_unlock()
-
-	To reiterate, synchronize_rcu() waits only for ongoing RCU
-	read-side critical sections to complete, not necessarily for
-	any that begin after synchronize_rcu() is invoked.
-
-	Of course, synchronize_rcu() does not necessarily return
-	-immediately- after the last pre-existing RCU read-side critical
-	section completes.  For one thing, there might well be scheduling
-	delays.  For another thing, many RCU implementations process
-	requests in batches in order to improve efficiencies, which can
-	further delay synchronize_rcu().
-
-	Since synchronize_rcu() is the API that must figure out when
-	readers are done, its implementation is key to RCU.  For RCU
-	to be useful in all but the most read-intensive situations,
-	synchronize_rcu()'s overhead must also be quite small.
-
-	The call_rcu() API is a callback form of synchronize_rcu(),
-	and is described in more detail in a later section.  Instead of
-	blocking, it registers a function and argument which are invoked
-	after all ongoing RCU read-side critical sections have completed.
-	This callback variant is particularly useful in situations where
-	it is illegal to block or where update-side performance is
-	critically important.
-
-	However, the call_rcu() API should not be used lightly, as use
-	of the synchronize_rcu() API generally results in simpler code.
-	In addition, the synchronize_rcu() API has the nice property
-	of automatically limiting update rate should grace periods
-	be delayed.  This property results in system resilience in face
-	of denial-of-service attacks.  Code using call_rcu() should limit
-	update rate in order to gain this same sort of resilience.  See
-	checklist.txt for some approaches to limiting the update rate.
-
-rcu_assign_pointer()
-
-	void rcu_assign_pointer(p, typeof(p) v);
-
-	Yes, rcu_assign_pointer() -is- implemented as a macro, though it
-	would be cool to be able to declare a function in this manner.
-	(Compiler experts will no doubt disagree.)
-
-	The updater uses this function to assign a new value to an
-	RCU-protected pointer, in order to safely communicate the change
-	in value from the updater to the reader.  This macro does not
-	evaluate to an rvalue, but it does execute any memory-barrier
-	instructions required for a given CPU architecture.
-
-	Perhaps just as important, it serves to document (1) which
-	pointers are protected by RCU and (2) the point at which a
-	given structure becomes accessible to other CPUs.  That said,
-	rcu_assign_pointer() is most frequently used indirectly, via
-	the _rcu list-manipulation primitives such as list_add_rcu().
-
-rcu_dereference()
-
-	typeof(p) rcu_dereference(p);
-
-	Like rcu_assign_pointer(), rcu_dereference() must be implemented
-	as a macro.
-
-	The reader uses rcu_dereference() to fetch an RCU-protected
-	pointer, which returns a value that may then be safely
-	dereferenced.  Note that rcu_dereference() does not actually
-	dereference the pointer, instead, it protects the pointer for
-	later dereferencing.  It also executes any needed memory-barrier
-	instructions for a given CPU architecture.  Currently, only Alpha
-	needs memory barriers within rcu_dereference() -- on other CPUs,
-	it compiles to nothing, not even a compiler directive.
-
-	Common coding practice uses rcu_dereference() to copy an
-	RCU-protected pointer to a local variable, then dereferences
-	this local variable, for example as follows:
-
-		p = rcu_dereference(head.next);
-		return p->data;
-
-	However, in this case, one could just as easily combine these
-	into one statement:
-
-		return rcu_dereference(head.next)->data;
-
-	If you are going to be fetching multiple fields from the
-	RCU-protected structure, using the local variable is of
-	course preferred.  Repeated rcu_dereference() calls look
-	ugly, do not guarantee that the same pointer will be returned
-	if an update happened while in the critical section, and incur
-	unnecessary overhead on Alpha CPUs.
-
-	Note that the value returned by rcu_dereference() is valid
-	only within the enclosing RCU read-side critical section [1].
-	For example, the following is -not- legal:
-
-		rcu_read_lock();
-		p = rcu_dereference(head.next);
-		rcu_read_unlock();
-		x = p->address;	/* BUG!!! */
-		rcu_read_lock();
-		y = p->data;	/* BUG!!! */
-		rcu_read_unlock();
-
-	Holding a reference from one RCU read-side critical section
-	to another is just as illegal as holding a reference from
-	one lock-based critical section to another!  Similarly,
-	using a reference outside of the critical section in which
-	it was acquired is just as illegal as doing so with normal
-	locking.
-
-	As with rcu_assign_pointer(), an important function of
-	rcu_dereference() is to document which pointers are protected by
-	RCU, in particular, flagging a pointer that is subject to changing
-	at any time, including immediately after the rcu_dereference().
-	And, again like rcu_assign_pointer(), rcu_dereference() is
-	typically used indirectly, via the _rcu list-manipulation
-	primitives, such as list_for_each_entry_rcu() [2].
-
-	[1] The variant rcu_dereference_protected() can be used outside
-	of an RCU read-side critical section as long as the usage is
-	protected by locks acquired by the update-side code.  This variant
-	avoids the lockdep warning that would happen when using (for
-	example) rcu_dereference() without rcu_read_lock() protection.
-	Using rcu_dereference_protected() also has the advantage
-	of permitting compiler optimizations that rcu_dereference()
-	must prohibit.	The rcu_dereference_protected() variant takes
-	a lockdep expression to indicate which locks must be acquired
-	by the caller. If the indicated protection is not provided,
-	a lockdep splat is emitted.  See Documentation/RCU/Design/Requirements/Requirements.rst
-	and the API's code comments for more details and example usage.
-
-	[2] If the list_for_each_entry_rcu() instance might be used by
-	update-side code as well as by RCU readers, then an additional
-	lockdep expression can be added to its list of arguments.
-	For example, given an additional "lock_is_held(&mylock)" argument,
-	the RCU lockdep code would complain only if this instance was
-	invoked outside of an RCU read-side critical section and without
-	the protection of mylock.
-
-The following diagram shows how each API communicates among the
-reader, updater, and reclaimer.
-
-
-	    rcu_assign_pointer()
-	                            +--------+
-	    +---------------------->| reader |---------+
-	    |                       +--------+         |
-	    |                           |              |
-	    |                           |              | Protect:
-	    |                           |              | rcu_read_lock()
-	    |                           |              | rcu_read_unlock()
-	    |        rcu_dereference()  |              |
-	    +---------+                 |              |
-	    | updater |<----------------+              |
-	    +---------+                                V
-	    |                                    +-----------+
-	    +----------------------------------->| reclaimer |
-	                                         +-----------+
-	      Defer:
-	      synchronize_rcu() & call_rcu()
-
-
-The RCU infrastructure observes the time sequence of rcu_read_lock(),
-rcu_read_unlock(), synchronize_rcu(), and call_rcu() invocations in
-order to determine when (1) synchronize_rcu() invocations may return
-to their callers and (2) call_rcu() callbacks may be invoked.  Efficient
-implementations of the RCU infrastructure make heavy use of batching in
-order to amortize their overhead over many uses of the corresponding APIs.
-
-There are at least three flavors of RCU usage in the Linux kernel. The diagram
-above shows the most common one. On the updater side, the rcu_assign_pointer(),
-sychronize_rcu() and call_rcu() primitives used are the same for all three
-flavors. However for protection (on the reader side), the primitives used vary
-depending on the flavor:
-
-a.	rcu_read_lock() / rcu_read_unlock()
-	rcu_dereference()
-
-b.	rcu_read_lock_bh() / rcu_read_unlock_bh()
-	local_bh_disable() / local_bh_enable()
-	rcu_dereference_bh()
-
-c.	rcu_read_lock_sched() / rcu_read_unlock_sched()
-	preempt_disable() / preempt_enable()
-	local_irq_save() / local_irq_restore()
-	hardirq enter / hardirq exit
-	NMI enter / NMI exit
-	rcu_dereference_sched()
-
-These three flavors are used as follows:
-
-a.	RCU applied to normal data structures.
-
-b.	RCU applied to networking data structures that may be subjected
-	to remote denial-of-service attacks.
-
-c.	RCU applied to scheduler and interrupt/NMI-handler tasks.
-
-Again, most uses will be of (a).  The (b) and (c) cases are important
-for specialized uses, but are relatively uncommon.
-
-
-3.  WHAT ARE SOME EXAMPLE USES OF CORE RCU API?
-
-This section shows a simple use of the core RCU API to protect a
-global pointer to a dynamically allocated structure.  More-typical
-uses of RCU may be found in listRCU.txt, arrayRCU.txt, and NMI-RCU.txt.
-
-	struct foo {
-		int a;
-		char b;
-		long c;
-	};
-	DEFINE_SPINLOCK(foo_mutex);
-
-	struct foo __rcu *gbl_foo;
-
-	/*
-	 * Create a new struct foo that is the same as the one currently
-	 * pointed to by gbl_foo, except that field "a" is replaced
-	 * with "new_a".  Points gbl_foo to the new structure, and
-	 * frees up the old structure after a grace period.
-	 *
-	 * Uses rcu_assign_pointer() to ensure that concurrent readers
-	 * see the initialized version of the new structure.
-	 *
-	 * Uses synchronize_rcu() to ensure that any readers that might
-	 * have references to the old structure complete before freeing
-	 * the old structure.
-	 */
-	void foo_update_a(int new_a)
-	{
-		struct foo *new_fp;
-		struct foo *old_fp;
-
-		new_fp = kmalloc(sizeof(*new_fp), GFP_KERNEL);
-		spin_lock(&foo_mutex);
-		old_fp = rcu_dereference_protected(gbl_foo, lockdep_is_held(&foo_mutex));
-		*new_fp = *old_fp;
-		new_fp->a = new_a;
-		rcu_assign_pointer(gbl_foo, new_fp);
-		spin_unlock(&foo_mutex);
-		synchronize_rcu();
-		kfree(old_fp);
-	}
-
-	/*
-	 * Return the value of field "a" of the current gbl_foo
-	 * structure.  Use rcu_read_lock() and rcu_read_unlock()
-	 * to ensure that the structure does not get deleted out
-	 * from under us, and use rcu_dereference() to ensure that
-	 * we see the initialized version of the structure (important
-	 * for DEC Alpha and for people reading the code).
-	 */
-	int foo_get_a(void)
-	{
-		int retval;
-
-		rcu_read_lock();
-		retval = rcu_dereference(gbl_foo)->a;
-		rcu_read_unlock();
-		return retval;
-	}
-
-So, to sum up:
-
-o	Use rcu_read_lock() and rcu_read_unlock() to guard RCU
-	read-side critical sections.
-
-o	Within an RCU read-side critical section, use rcu_dereference()
-	to dereference RCU-protected pointers.
-
-o	Use some solid scheme (such as locks or semaphores) to
-	keep concurrent updates from interfering with each other.
-
-o	Use rcu_assign_pointer() to update an RCU-protected pointer.
-	This primitive protects concurrent readers from the updater,
-	-not- concurrent updates from each other!  You therefore still
-	need to use locking (or something similar) to keep concurrent
-	rcu_assign_pointer() primitives from interfering with each other.
-
-o	Use synchronize_rcu() -after- removing a data element from an
-	RCU-protected data structure, but -before- reclaiming/freeing
-	the data element, in order to wait for the completion of all
-	RCU read-side critical sections that might be referencing that
-	data item.
-
-See checklist.txt for additional rules to follow when using RCU.
-And again, more-typical uses of RCU may be found in listRCU.txt,
-arrayRCU.txt, and NMI-RCU.txt.
-
-
-4.  WHAT IF MY UPDATING THREAD CANNOT BLOCK?
-
-In the example above, foo_update_a() blocks until a grace period elapses.
-This is quite simple, but in some cases one cannot afford to wait so
-long -- there might be other high-priority work to be done.
-
-In such cases, one uses call_rcu() rather than synchronize_rcu().
-The call_rcu() API is as follows:
-
-	void call_rcu(struct rcu_head * head,
-		      void (*func)(struct rcu_head *head));
-
-This function invokes func(head) after a grace period has elapsed.
-This invocation might happen from either softirq or process context,
-so the function is not permitted to block.  The foo struct needs to
-have an rcu_head structure added, perhaps as follows:
-
-	struct foo {
-		int a;
-		char b;
-		long c;
-		struct rcu_head rcu;
-	};
-
-The foo_update_a() function might then be written as follows:
-
-	/*
-	 * Create a new struct foo that is the same as the one currently
-	 * pointed to by gbl_foo, except that field "a" is replaced
-	 * with "new_a".  Points gbl_foo to the new structure, and
-	 * frees up the old structure after a grace period.
-	 *
-	 * Uses rcu_assign_pointer() to ensure that concurrent readers
-	 * see the initialized version of the new structure.
-	 *
-	 * Uses call_rcu() to ensure that any readers that might have
-	 * references to the old structure complete before freeing the
-	 * old structure.
-	 */
-	void foo_update_a(int new_a)
-	{
-		struct foo *new_fp;
-		struct foo *old_fp;
-
-		new_fp = kmalloc(sizeof(*new_fp), GFP_KERNEL);
-		spin_lock(&foo_mutex);
-		old_fp = rcu_dereference_protected(gbl_foo, lockdep_is_held(&foo_mutex));
-		*new_fp = *old_fp;
-		new_fp->a = new_a;
-		rcu_assign_pointer(gbl_foo, new_fp);
-		spin_unlock(&foo_mutex);
-		call_rcu(&old_fp->rcu, foo_reclaim);
-	}
-
-The foo_reclaim() function might appear as follows:
-
-	void foo_reclaim(struct rcu_head *rp)
-	{
-		struct foo *fp = container_of(rp, struct foo, rcu);
-
-		foo_cleanup(fp->a);
-
-		kfree(fp);
-	}
-
-The container_of() primitive is a macro that, given a pointer into a
-struct, the type of the struct, and the pointed-to field within the
-struct, returns a pointer to the beginning of the struct.
-
-The use of call_rcu() permits the caller of foo_update_a() to
-immediately regain control, without needing to worry further about the
-old version of the newly updated element.  It also clearly shows the
-RCU distinction between updater, namely foo_update_a(), and reclaimer,
-namely foo_reclaim().
-
-The summary of advice is the same as for the previous section, except
-that we are now using call_rcu() rather than synchronize_rcu():
-
-o	Use call_rcu() -after- removing a data element from an
-	RCU-protected data structure in order to register a callback
-	function that will be invoked after the completion of all RCU
-	read-side critical sections that might be referencing that
-	data item.
-
-If the callback for call_rcu() is not doing anything more than calling
-kfree() on the structure, you can use kfree_rcu() instead of call_rcu()
-to avoid having to write your own callback:
-
-	kfree_rcu(old_fp, rcu);
-
-Again, see checklist.txt for additional rules governing the use of RCU.
-
-
-5.  WHAT ARE SOME SIMPLE IMPLEMENTATIONS OF RCU?
-
-One of the nice things about RCU is that it has extremely simple "toy"
-implementations that are a good first step towards understanding the
-production-quality implementations in the Linux kernel.  This section
-presents two such "toy" implementations of RCU, one that is implemented
-in terms of familiar locking primitives, and another that more closely
-resembles "classic" RCU.  Both are way too simple for real-world use,
-lacking both functionality and performance.  However, they are useful
-in getting a feel for how RCU works.  See kernel/rcu/update.c for a
-production-quality implementation, and see:
-
-	http://www.rdrop.com/users/paulmck/RCU
-
-for papers describing the Linux kernel RCU implementation.  The OLS'01
-and OLS'02 papers are a good introduction, and the dissertation provides
-more details on the current implementation as of early 2004.
-
-
-5A.  "TOY" IMPLEMENTATION #1: LOCKING
-
-This section presents a "toy" RCU implementation that is based on
-familiar locking primitives.  Its overhead makes it a non-starter for
-real-life use, as does its lack of scalability.  It is also unsuitable
-for realtime use, since it allows scheduling latency to "bleed" from
-one read-side critical section to another.  It also assumes recursive
-reader-writer locks:  If you try this with non-recursive locks, and
-you allow nested rcu_read_lock() calls, you can deadlock.
-
-However, it is probably the easiest implementation to relate to, so is
-a good starting point.
-
-It is extremely simple:
-
-	static DEFINE_RWLOCK(rcu_gp_mutex);
-
-	void rcu_read_lock(void)
-	{
-		read_lock(&rcu_gp_mutex);
-	}
-
-	void rcu_read_unlock(void)
-	{
-		read_unlock(&rcu_gp_mutex);
-	}
-
-	void synchronize_rcu(void)
-	{
-		write_lock(&rcu_gp_mutex);
-		smp_mb__after_spinlock();
-		write_unlock(&rcu_gp_mutex);
-	}
-
-[You can ignore rcu_assign_pointer() and rcu_dereference() without missing
-much.  But here are simplified versions anyway.  And whatever you do,
-don't forget about them when submitting patches making use of RCU!]
-
-	#define rcu_assign_pointer(p, v) \
-	({ \
-		smp_store_release(&(p), (v)); \
-	})
-
-	#define rcu_dereference(p) \
-	({ \
-		typeof(p) _________p1 = READ_ONCE(p); \
-		(_________p1); \
-	})
-
-
-The rcu_read_lock() and rcu_read_unlock() primitive read-acquire
-and release a global reader-writer lock.  The synchronize_rcu()
-primitive write-acquires this same lock, then releases it.  This means
-that once synchronize_rcu() exits, all RCU read-side critical sections
-that were in progress before synchronize_rcu() was called are guaranteed
-to have completed -- there is no way that synchronize_rcu() would have
-been able to write-acquire the lock otherwise.  The smp_mb__after_spinlock()
-promotes synchronize_rcu() to a full memory barrier in compliance with
-the "Memory-Barrier Guarantees" listed in:
-
-	Documentation/RCU/Design/Requirements/Requirements.rst
-
-It is possible to nest rcu_read_lock(), since reader-writer locks may
-be recursively acquired.  Note also that rcu_read_lock() is immune
-from deadlock (an important property of RCU).  The reason for this is
-that the only thing that can block rcu_read_lock() is a synchronize_rcu().
-But synchronize_rcu() does not acquire any locks while holding rcu_gp_mutex,
-so there can be no deadlock cycle.
-
-Quick Quiz #1:	Why is this argument naive?  How could a deadlock
-		occur when using this algorithm in a real-world Linux
-		kernel?  How could this deadlock be avoided?
-
-
-5B.  "TOY" EXAMPLE #2: CLASSIC RCU
-
-This section presents a "toy" RCU implementation that is based on
-"classic RCU".  It is also short on performance (but only for updates) and
-on features such as hotplug CPU and the ability to run in CONFIG_PREEMPT
-kernels.  The definitions of rcu_dereference() and rcu_assign_pointer()
-are the same as those shown in the preceding section, so they are omitted.
-
-	void rcu_read_lock(void) { }
-
-	void rcu_read_unlock(void) { }
-
-	void synchronize_rcu(void)
-	{
-		int cpu;
-
-		for_each_possible_cpu(cpu)
-			run_on(cpu);
-	}
-
-Note that rcu_read_lock() and rcu_read_unlock() do absolutely nothing.
-This is the great strength of classic RCU in a non-preemptive kernel:
-read-side overhead is precisely zero, at least on non-Alpha CPUs.
-And there is absolutely no way that rcu_read_lock() can possibly
-participate in a deadlock cycle!
-
-The implementation of synchronize_rcu() simply schedules itself on each
-CPU in turn.  The run_on() primitive can be implemented straightforwardly
-in terms of the sched_setaffinity() primitive.  Of course, a somewhat less
-"toy" implementation would restore the affinity upon completion rather
-than just leaving all tasks running on the last CPU, but when I said
-"toy", I meant -toy-!
-
-So how the heck is this supposed to work???
-
-Remember that it is illegal to block while in an RCU read-side critical
-section.  Therefore, if a given CPU executes a context switch, we know
-that it must have completed all preceding RCU read-side critical sections.
-Once -all- CPUs have executed a context switch, then -all- preceding
-RCU read-side critical sections will have completed.
-
-So, suppose that we remove a data item from its structure and then invoke
-synchronize_rcu().  Once synchronize_rcu() returns, we are guaranteed
-that there are no RCU read-side critical sections holding a reference
-to that data item, so we can safely reclaim it.
-
-Quick Quiz #2:	Give an example where Classic RCU's read-side
-		overhead is -negative-.
-
-Quick Quiz #3:  If it is illegal to block in an RCU read-side
-		critical section, what the heck do you do in
-		PREEMPT_RT, where normal spinlocks can block???
-
-
-6.  ANALOGY WITH READER-WRITER LOCKING
-
-Although RCU can be used in many different ways, a very common use of
-RCU is analogous to reader-writer locking.  The following unified
-diff shows how closely related RCU and reader-writer locking can be.
-
-	@@ -5,5 +5,5 @@ struct el {
-	 	int data;
-	 	/* Other data fields */
-	 };
-	-rwlock_t listmutex;
-	+spinlock_t listmutex;
-	 struct el head;
-
-	@@ -13,15 +14,15 @@
-		struct list_head *lp;
-		struct el *p;
-
-	-	read_lock(&listmutex);
-	-	list_for_each_entry(p, head, lp) {
-	+	rcu_read_lock();
-	+	list_for_each_entry_rcu(p, head, lp) {
-			if (p->key == key) {
-				*result = p->data;
-	-			read_unlock(&listmutex);
-	+			rcu_read_unlock();
-				return 1;
-			}
-		}
-	-	read_unlock(&listmutex);
-	+	rcu_read_unlock();
-		return 0;
-	 }
-
-	@@ -29,15 +30,16 @@
-	 {
-		struct el *p;
-
-	-	write_lock(&listmutex);
-	+	spin_lock(&listmutex);
-		list_for_each_entry(p, head, lp) {
-			if (p->key == key) {
-	-			list_del(&p->list);
-	-			write_unlock(&listmutex);
-	+			list_del_rcu(&p->list);
-	+			spin_unlock(&listmutex);
-	+			synchronize_rcu();
-				kfree(p);
-				return 1;
-			}
-		}
-	-	write_unlock(&listmutex);
-	+	spin_unlock(&listmutex);
-		return 0;
-	 }
-
-Or, for those who prefer a side-by-side listing:
-
- 1 struct el {                          1 struct el {
- 2   struct list_head list;             2   struct list_head list;
- 3   long key;                          3   long key;
- 4   spinlock_t mutex;                  4   spinlock_t mutex;
- 5   int data;                          5   int data;
- 6   /* Other data fields */            6   /* Other data fields */
- 7 };                                   7 };
- 8 rwlock_t listmutex;                  8 spinlock_t listmutex;
- 9 struct el head;                      9 struct el head;
-
- 1 int search(long key, int *result)    1 int search(long key, int *result)
- 2 {                                    2 {
- 3   struct list_head *lp;              3   struct list_head *lp;
- 4   struct el *p;                      4   struct el *p;
- 5                                      5
- 6   read_lock(&listmutex);             6   rcu_read_lock();
- 7   list_for_each_entry(p, head, lp) { 7   list_for_each_entry_rcu(p, head, lp) {
- 8     if (p->key == key) {             8     if (p->key == key) {
- 9       *result = p->data;             9       *result = p->data;
-10       read_unlock(&listmutex);      10       rcu_read_unlock();
-11       return 1;                     11       return 1;
-12     }                               12     }
-13   }                                 13   }
-14   read_unlock(&listmutex);          14   rcu_read_unlock();
-15   return 0;                         15   return 0;
-16 }                                   16 }
-
- 1 int delete(long key)                 1 int delete(long key)
- 2 {                                    2 {
- 3   struct el *p;                      3   struct el *p;
- 4                                      4
- 5   write_lock(&listmutex);            5   spin_lock(&listmutex);
- 6   list_for_each_entry(p, head, lp) { 6   list_for_each_entry(p, head, lp) {
- 7     if (p->key == key) {             7     if (p->key == key) {
- 8       list_del(&p->list);            8       list_del_rcu(&p->list);
- 9       write_unlock(&listmutex);      9       spin_unlock(&listmutex);
-                                       10       synchronize_rcu();
-10       kfree(p);                     11       kfree(p);
-11       return 1;                     12       return 1;
-12     }                               13     }
-13   }                                 14   }
-14   write_unlock(&listmutex);         15   spin_unlock(&listmutex);
-15   return 0;                         16   return 0;
-16 }                                   17 }
-
-Either way, the differences are quite small.  Read-side locking moves
-to rcu_read_lock() and rcu_read_unlock, update-side locking moves from
-a reader-writer lock to a simple spinlock, and a synchronize_rcu()
-precedes the kfree().
-
-However, there is one potential catch: the read-side and update-side
-critical sections can now run concurrently.  In many cases, this will
-not be a problem, but it is necessary to check carefully regardless.
-For example, if multiple independent list updates must be seen as
-a single atomic update, converting to RCU will require special care.
-
-Also, the presence of synchronize_rcu() means that the RCU version of
-delete() can now block.  If this is a problem, there is a callback-based
-mechanism that never blocks, namely call_rcu() or kfree_rcu(), that can
-be used in place of synchronize_rcu().
-
-
-7.  FULL LIST OF RCU APIs
-
-The RCU APIs are documented in docbook-format header comments in the
-Linux-kernel source code, but it helps to have a full list of the
-APIs, since there does not appear to be a way to categorize them
-in docbook.  Here is the list, by category.
-
-RCU list traversal:
-
-	list_entry_rcu
-	list_first_entry_rcu
-	list_next_rcu
-	list_for_each_entry_rcu
-	list_for_each_entry_continue_rcu
-	list_for_each_entry_from_rcu
-	hlist_first_rcu
-	hlist_next_rcu
-	hlist_pprev_rcu
-	hlist_for_each_entry_rcu
-	hlist_for_each_entry_rcu_bh
-	hlist_for_each_entry_from_rcu
-	hlist_for_each_entry_continue_rcu
-	hlist_for_each_entry_continue_rcu_bh
-	hlist_nulls_first_rcu
-	hlist_nulls_for_each_entry_rcu
-	hlist_bl_first_rcu
-	hlist_bl_for_each_entry_rcu
-
-RCU pointer/list update:
-
-	rcu_assign_pointer
-	list_add_rcu
-	list_add_tail_rcu
-	list_del_rcu
-	list_replace_rcu
-	hlist_add_behind_rcu
-	hlist_add_before_rcu
-	hlist_add_head_rcu
-	hlist_del_rcu
-	hlist_del_init_rcu
-	hlist_replace_rcu
-	list_splice_init_rcu()
-	hlist_nulls_del_init_rcu
-	hlist_nulls_del_rcu
-	hlist_nulls_add_head_rcu
-	hlist_bl_add_head_rcu
-	hlist_bl_del_init_rcu
-	hlist_bl_del_rcu
-	hlist_bl_set_first_rcu
-
-RCU:	Critical sections	Grace period		Barrier
-
-	rcu_read_lock		synchronize_net		rcu_barrier
-	rcu_read_unlock		synchronize_rcu
-	rcu_dereference		synchronize_rcu_expedited
-	rcu_read_lock_held	call_rcu
-	rcu_dereference_check	kfree_rcu
-	rcu_dereference_protected
-
-bh:	Critical sections	Grace period		Barrier
-
-	rcu_read_lock_bh	call_rcu		rcu_barrier
-	rcu_read_unlock_bh	synchronize_rcu
-	[local_bh_disable]	synchronize_rcu_expedited
-	[and friends]
-	rcu_dereference_bh
-	rcu_dereference_bh_check
-	rcu_dereference_bh_protected
-	rcu_read_lock_bh_held
-
-sched:	Critical sections	Grace period		Barrier
-
-	rcu_read_lock_sched	call_rcu		rcu_barrier
-	rcu_read_unlock_sched	synchronize_rcu
-	[preempt_disable]	synchronize_rcu_expedited
-	[and friends]
-	rcu_read_lock_sched_notrace
-	rcu_read_unlock_sched_notrace
-	rcu_dereference_sched
-	rcu_dereference_sched_check
-	rcu_dereference_sched_protected
-	rcu_read_lock_sched_held
-
-
-SRCU:	Critical sections	Grace period		Barrier
-
-	srcu_read_lock		call_srcu		srcu_barrier
-	srcu_read_unlock	synchronize_srcu
-	srcu_dereference	synchronize_srcu_expedited
-	srcu_dereference_check
-	srcu_read_lock_held
-
-SRCU:	Initialization/cleanup
-	DEFINE_SRCU
-	DEFINE_STATIC_SRCU
-	init_srcu_struct
-	cleanup_srcu_struct
-
-All:  lockdep-checked RCU-protected pointer access
-
-	rcu_access_pointer
-	rcu_dereference_raw
-	RCU_LOCKDEP_WARN
-	rcu_sleep_check
-	RCU_NONIDLE
-
-See the comment headers in the source code (or the docbook generated
-from them) for more information.
-
-However, given that there are no fewer than four families of RCU APIs
-in the Linux kernel, how do you choose which one to use?  The following
-list can be helpful:
-
-a.	Will readers need to block?  If so, you need SRCU.
-
-b.	What about the -rt patchset?  If readers would need to block
-	in an non-rt kernel, you need SRCU.  If readers would block
-	in a -rt kernel, but not in a non-rt kernel, SRCU is not
-	necessary.  (The -rt patchset turns spinlocks into sleeplocks,
-	hence this distinction.)
-
-c.	Do you need to treat NMI handlers, hardirq handlers,
-	and code segments with preemption disabled (whether
-	via preempt_disable(), local_irq_save(), local_bh_disable(),
-	or some other mechanism) as if they were explicit RCU readers?
-	If so, RCU-sched is the only choice that will work for you.
-
-d.	Do you need RCU grace periods to complete even in the face
-	of softirq monopolization of one or more of the CPUs?  For
-	example, is your code subject to network-based denial-of-service
-	attacks?  If so, you should disable softirq across your readers,
-	for example, by using rcu_read_lock_bh().
-
-e.	Is your workload too update-intensive for normal use of
-	RCU, but inappropriate for other synchronization mechanisms?
-	If so, consider SLAB_TYPESAFE_BY_RCU (which was originally
-	named SLAB_DESTROY_BY_RCU).  But please be careful!
-
-f.	Do you need read-side critical sections that are respected
-	even though they are in the middle of the idle loop, during
-	user-mode execution, or on an offlined CPU?  If so, SRCU is the
-	only choice that will work for you.
-
-g.	Otherwise, use RCU.
-
-Of course, this all assumes that you have determined that RCU is in fact
-the right tool for your job.
-
-
-8.  ANSWERS TO QUICK QUIZZES
-
-Quick Quiz #1:	Why is this argument naive?  How could a deadlock
-		occur when using this algorithm in a real-world Linux
-		kernel?  [Referring to the lock-based "toy" RCU
-		algorithm.]
-
-Answer:		Consider the following sequence of events:
-
-		1.	CPU 0 acquires some unrelated lock, call it
-			"problematic_lock", disabling irq via
-			spin_lock_irqsave().
-
-		2.	CPU 1 enters synchronize_rcu(), write-acquiring
-			rcu_gp_mutex.
-
-		3.	CPU 0 enters rcu_read_lock(), but must wait
-			because CPU 1 holds rcu_gp_mutex.
-
-		4.	CPU 1 is interrupted, and the irq handler
-			attempts to acquire problematic_lock.
-
-		The system is now deadlocked.
-
-		One way to avoid this deadlock is to use an approach like
-		that of CONFIG_PREEMPT_RT, where all normal spinlocks
-		become blocking locks, and all irq handlers execute in
-		the context of special tasks.  In this case, in step 4
-		above, the irq handler would block, allowing CPU 1 to
-		release rcu_gp_mutex, avoiding the deadlock.
-
-		Even in the absence of deadlock, this RCU implementation
-		allows latency to "bleed" from readers to other
-		readers through synchronize_rcu().  To see this,
-		consider task A in an RCU read-side critical section
-		(thus read-holding rcu_gp_mutex), task B blocked
-		attempting to write-acquire rcu_gp_mutex, and
-		task C blocked in rcu_read_lock() attempting to
-		read_acquire rcu_gp_mutex.  Task A's RCU read-side
-		latency is holding up task C, albeit indirectly via
-		task B.
-
-		Realtime RCU implementations therefore use a counter-based
-		approach where tasks in RCU read-side critical sections
-		cannot be blocked by tasks executing synchronize_rcu().
-
-Quick Quiz #2:	Give an example where Classic RCU's read-side
-		overhead is -negative-.
-
-Answer:		Imagine a single-CPU system with a non-CONFIG_PREEMPT
-		kernel where a routing table is used by process-context
-		code, but can be updated by irq-context code (for example,
-		by an "ICMP REDIRECT" packet).	The usual way of handling
-		this would be to have the process-context code disable
-		interrupts while searching the routing table.  Use of
-		RCU allows such interrupt-disabling to be dispensed with.
-		Thus, without RCU, you pay the cost of disabling interrupts,
-		and with RCU you don't.
-
-		One can argue that the overhead of RCU in this
-		case is negative with respect to the single-CPU
-		interrupt-disabling approach.  Others might argue that
-		the overhead of RCU is merely zero, and that replacing
-		the positive overhead of the interrupt-disabling scheme
-		with the zero-overhead RCU scheme does not constitute
-		negative overhead.
-
-		In real life, of course, things are more complex.  But
-		even the theoretical possibility of negative overhead for
-		a synchronization primitive is a bit unexpected.  ;-)
-
-Quick Quiz #3:  If it is illegal to block in an RCU read-side
-		critical section, what the heck do you do in
-		PREEMPT_RT, where normal spinlocks can block???
-
-Answer:		Just as PREEMPT_RT permits preemption of spinlock
-		critical sections, it permits preemption of RCU
-		read-side critical sections.  It also permits
-		spinlocks blocking while in RCU read-side critical
-		sections.
-
-		Why the apparent inconsistency?  Because it is
-		possible to use priority boosting to keep the RCU
-		grace periods short if need be (for example, if running
-		short of memory).  In contrast, if blocking waiting
-		for (say) network reception, there is no way to know
-		what should be boosted.  Especially given that the
-		process we need to boost might well be a human being
-		who just went out for a pizza or something.  And although
-		a computer-operated cattle prod might arouse serious
-		interest, it might also provoke serious objections.
-		Besides, how does the computer know what pizza parlor
-		the human being went to???
-
-
-ACKNOWLEDGEMENTS
-
-My thanks to the people who helped make this human-readable, including
-Jon Walpole, Josh Triplett, Serge Hallyn, Suzanne Wood, and Alan Stern.
-
-
-For more information, see http://www.rdrop.com/users/paulmck/RCU.

Powered by blists - more mailing lists