Documentation updates for 4.5

new file mode 100644
index 0000000000000000000000000000000000000000..7496a55e4e7b41becdb658a2bd34765fbe80013f
GIT binary patch

374 lines not on this page · raw message

237 lines not on this page · raw message

639 lines not on this page · raw message

1,750 lines not on this page · raw message

2,643 lines not on this page · raw message

108 lines not on this page · raw message

index 36de7aaa941e..871f627b7713 100644
@@ -1678,6 +1678,7 @@ Some of the relevant points of interest are as follows:
 <li>	<a href="#Scheduler and RCU">Scheduler and RCU</a>.
 <li>	<a href="#Tracing and RCU">Tracing and RCU</a>.
 <li>	<a href="#Energy Efficiency">Energy Efficiency</a>.
+<li>	<a href="#Memory Efficiency">Memory Efficiency</a>.
 <li>	<a href="#Performance, Scalability, Response Time, and Reliability">
 	Performance, Scalability, Response Time, and Reliability</a>.
 </ol>

@@ -2006,6 +2007,48 @@ I learned of many of these requirements via angry phone calls:
 Flaming me on the Linux-kernel mailing list was apparently not
 sufficient to fully vent their ire at RCU's energy-efficiency bugs!
 
+<h3><a name="Memory Efficiency">Memory Efficiency</a></h3>
+
+<p>
+Although small-memory non-realtime systems can simply use Tiny RCU,
+code size is only one aspect of memory efficiency.
+Another aspect is the size of the <tt>rcu_head</tt> structure
+used by <tt>call_rcu()</tt> and <tt>kfree_rcu()</tt>.
+Although this structure contains nothing more than a pair of pointers,
+it does appear in many RCU-protected data structures, including
+some that are size critical.
+The <tt>page</tt> structure is a case in point, as evidenced by
+the many occurrences of the <tt>union</tt> keyword within that structure.
+
+<p>
+This need for memory efficiency is one reason that RCU uses hand-crafted
+singly linked lists to track the <tt>rcu_head</tt> structures that
+are waiting for a grace period to elapse.
+It is also the reason why <tt>rcu_head</tt> structures do not contain
+debug information, such as fields tracking the file and line of the
+<tt>call_rcu()</tt> or <tt>kfree_rcu()</tt> that posted them.
+Although this information might appear in debug-only kernel builds at some
+point, in the meantime, the <tt>-&gt;func</tt> field will often provide
+the needed debug information.
+
+<p>
+However, in some cases, the need for memory efficiency leads to even
+more extreme measures.
+Returning to the <tt>page</tt> structure, the <tt>rcu_head</tt> field
+shares storage with a great many other structures that are used at
+various points in the corresponding page's lifetime.
+In order to correctly resolve certain
+<a href="https://lkml.kernel.org/g/1439976106-137226-1-git-send-email-kirill.shutemov@linux.intel.com">race conditions</a>,
+the Linux kernel's memory-management subsystem needs a particular bit
+to remain zero during all phases of grace-period processing,
+and that bit happens to map to the bottom bit of the
+<tt>rcu_head</tt> structure's <tt>-&gt;next</tt> field.
+RCU makes this guarantee as long as <tt>call_rcu()</tt>
+is used to post the callback, as opposed to <tt>kfree_rcu()</tt>
+or some future &ldquo;lazy&rdquo;
+variant of <tt>call_rcu()</tt> that might one day be created for
+energy-efficiency purposes.
+
 <h3><a name="Performance, Scalability, Response Time, and Reliability">
 Performance, Scalability, Response Time, and Reliability</a></h3>
 

55 lines not on this page · raw message

index 871f627b7713..cc5b587c0ec5 100644
@@ -1618,12 +1618,35 @@ guard against mishaps and misuse:
 	supplied the needed
 	<a href="https://lkml.kernel.org/g/20100319013024.GA28456@Krystal">patch</a>.
 <li>	An infinite loop in an RCU read-side critical section will
-	eventually trigger an RCU CPU stall warning splat.
+	eventually trigger an RCU CPU stall warning splat, with
+	the duration of &ldquo;eventually&rdquo; being controlled by the
+	<tt>RCU_CPU_STALL_TIMEOUT</tt> <tt>Kconfig</tt> option, or,
+	alternatively, by the
+	<tt>rcupdate.rcu_cpu_stall_timeout</tt> boot/sysfs
+	parameter.
 	However, RCU is not obligated to produce this splat
 	unless there is a grace period waiting on that particular
 	RCU read-side critical section.
+	<p>
+	Some extreme workloads might intentionally delay
+	RCU grace periods, and systems running those workloads can
+	be booted with <tt>rcupdate.rcu_cpu_stall_suppress</tt>
+	to suppress the splats.
+	This kernel parameter may also be set via <tt>sysfs</tt>.
+	Furthermore, RCU CPU stall warnings are counter-productive
+	during sysrq dumps and during panics.
+	RCU therefore supplies the <tt>rcu_sysrq_start()</tt> and
+	<tt>rcu_sysrq_end()</tt> API members to be called before
+	and after long sysrq dumps.
+	RCU also supplies the <tt>rcu_panic()</tt> notifier that is
+	automatically invoked at the beginning of a panic to suppress
+	further RCU CPU stall warnings.
+
+	<p>
 	This requirement made itself known in the early 1990s, pretty
 	much the first time that it was necessary to debug a CPU stall.
+	That said, the initial implementation in DYNIX/ptx was quite
+	generic in comparison with that of Linux.
 <li>	Although it would be very good to detect pointers leaking out
 	of RCU read-side critical sections, there is currently no
 	good way of doing this.

index a544db4646c6..23524d75a3c3 100644
@@ -1777,12 +1777,35 @@ guard against mishaps and misuse:
 	supplied the needed
 	<a href="https://lkml.kernel.org/g/20100319013024.GA28456@Krystal">patch</a>.
 <li>	An infinite loop in an RCU read-side critical section will
-	eventually trigger an RCU CPU stall warning splat.
+	eventually trigger an RCU CPU stall warning splat, with
+	the duration of &ldquo;eventually&rdquo; being controlled by the
+	<tt>RCU_CPU_STALL_TIMEOUT</tt> <tt>Kconfig</tt> option, or,
+	alternatively, by the
+	<tt>rcupdate.rcu_cpu_stall_timeout</tt> boot/sysfs
+	parameter.
 	However, RCU is not obligated to produce this splat
 	unless there is a grace period waiting on that particular
 	RCU read-side critical section.
+	<p>
+	Some extreme workloads might intentionally delay
+	RCU grace periods, and systems running those workloads can
+	be booted with <tt>rcupdate.rcu_cpu_stall_suppress</tt>
+	to suppress the splats.
+	This kernel parameter may also be set via <tt>sysfs</tt>.
+	Furthermore, RCU CPU stall warnings are counter-productive
+	during sysrq dumps and during panics.
+	RCU therefore supplies the <tt>rcu_sysrq_start()</tt> and
+	<tt>rcu_sysrq_end()</tt> API members to be called before
+	and after long sysrq dumps.
+	RCU also supplies the <tt>rcu_panic()</tt> notifier that is
+	automatically invoked at the beginning of a panic to suppress
+	further RCU CPU stall warnings.
+
+	<p>
 	This requirement made itself known in the early 1990s, pretty
 	much the first time that it was necessary to debug a CPU stall.
+	That said, the initial implementation in DYNIX/ptx was quite
+	generic in comparison with that of Linux.
 <li>	Although it would be very good to detect pointers leaking out
 	of RCU read-side critical sections, there is currently no
 	good way of doing this.

index cc5b587c0ec5..105247149975 100644
@@ -1495,6 +1495,14 @@ section, neither of which is conducive to a long-lived and prosperous
 kernel.
 
 <p>
+It is worth noting that RCU is not alone in limiting composability.
+For example, many transactional-memory implementations prohibit
+composing a pair of transactions separated by an irrevocable
+operation (for example, a network receive operation).
+For another example, lock-based critical sections can be composed
+surprisingly freely, but only if deadlock is avoided.
+
+<p>
 In short, although RCU read-side critical sections are highly composable,
 care is required in some situations, just as is the case for any other
 composable synchronization mechanism.

index 23524d75a3c3..5b76e21fa092 100644
@@ -1654,6 +1654,14 @@ section, neither of which is conducive to a long-lived and prosperous
 kernel.
 
 <p>
+It is worth noting that RCU is not alone in limiting composability.
+For example, many transactional-memory implementations prohibit
+composing a pair of transactions separated by an irrevocable
+operation (for example, a network receive operation).
+For another example, lock-based critical sections can be composed
+surprisingly freely, but only if deadlock is avoided.
+
+<p>
 In short, although RCU read-side critical sections are highly composable,
 care is required in some situations, just as is the case for any other
 composable synchronization mechanism.

index 105247149975..ab513ed229d7 100644
@@ -1942,12 +1942,16 @@ RCU depends on the scheduler, and the scheduler uses RCU to
 protect some of its data structures.
 This means the scheduler is forbidden from acquiring
 the runqueue locks and the priority-inheritance locks
-in the middle of an outermost RCU read-side critical section unless
-it also releases them before exiting that same
-RCU read-side critical section.
-This same prohibition also applies to any lock that is acquired
+in the middle of an outermost RCU read-side critical section unless either
+(1) it releases them before exiting that same
+RCU read-side critical section, or
+(2) preemption is disabled across
+that entire RCU read-side critical section.
+This same prohibition also applies (recursively!) to any lock that is acquired
 while holding any lock to which this prohibition applies.
-Violating this rule results in deadlock.
+Adhering to this rule prevents preemptible RCU from invoking
+<tt>rcu_read_unlock_special()</tt> while either runqueue or
+priority-inheritance locks are held, thus avoiding deadlock.
 
 <p>
 For RCU's part, the preemptible-RCU <tt>rcu_read_unlock()</tt>

index 5b76e21fa092..f7c817f235e0 100644
@@ -2109,12 +2109,16 @@ RCU depends on the scheduler, and the scheduler uses RCU to
 protect some of its data structures.
 This means the scheduler is forbidden from acquiring
 the runqueue locks and the priority-inheritance locks
-in the middle of an outermost RCU read-side critical section unless
-it also releases them before exiting that same
-RCU read-side critical section.
-This same prohibition also applies to any lock that is acquired
+in the middle of an outermost RCU read-side critical section unless either
+(1) it releases them before exiting that same
+RCU read-side critical section, or
+(2) preemption is disabled across
+that entire RCU read-side critical section.
+This same prohibition also applies (recursively!) to any lock that is acquired
 while holding any lock to which this prohibition applies.
-Violating this rule results in deadlock.
+Adhering to this rule prevents preemptible RCU from invoking
+<tt>rcu_read_unlock_special()</tt> while either runqueue or
+priority-inheritance locks are held, thus avoiding deadlock.
 
 <p>
 For RCU's part, the preemptible-RCU <tt>rcu_read_unlock()</tt>

index ab513ed229d7..96cdcf7195d5 100644
@@ -80,6 +80,8 @@ These are:
 	Grace-Period Guarantee</a>
 <li>	<a href="#Publish-Subscribe Guarantee">
 	Publish-Subscribe Guarantee</a>
+<li>	<a href="#Memory-Barrier Guarantees">
+	Memory-Barrier Guarantees</a>
 <li>	<a href="#RCU Primitives Guaranteed to Execute Unconditionally">
 	RCU Primitives Guaranteed to Execute Unconditionally</a>
 <li>	<a href="#Guaranteed Read-to-Write Upgrade">

@@ -499,9 +501,37 @@ might the compiler make use of?
 <br><a href="#qq4answer">Answer</a>
 
 <p>
-This simple linked-data-structure scenario clearly demonstrates the need
-for RCU's stringent memory-ordering guarantees on systems with more than
-one CPU:
+In short, RCU's publish-subscribe guarantee is provided by the combination
+of <tt>rcu_assign_pointer()</tt> and <tt>rcu_dereference()</tt>.
+This guarantee allows data elements to be safely added to RCU-protected
+linked data structures without disrupting RCU readers.
+This guarantee can be used in combination with the grace-period
+guarantee to also allow data elements to be removed from RCU-protected
+linked data structures, again without disrupting RCU readers.
+
+<p>
+This guarantee was only partially premeditated.
+DYNIX/ptx used an explicit memory barrier for publication, but had nothing
+resembling <tt>rcu_dereference()</tt> for subscription, nor did it
+have anything resembling the <tt>smp_read_barrier_depends()</tt>
+that was later subsumed into <tt>rcu_dereference()</tt>.
+The need for these operations made itself known quite suddenly at a
+late-1990s meeting with the DEC Alpha architects, back in the days when
+DEC was still a free-standing company.
+It took the Alpha architects a good hour to convince me that any sort
+of barrier would ever be needed, and it then took me a good <i>two</i> hours
+to convince them that their documentation did not make this point clear.
+More recent work with the C and C++ standards committees have provided
+much education on tricks and traps from the compiler.
+In short, compilers were much less tricky in the early 1990s, but in
+2015, don't even think about omitting <tt>rcu_dereference()</tt>!
+
+<h3><a name="Memory-Barrier Guarantees">Memory-Barrier Guarantees</a></h3>
+
+<p>
+The previous section's simple linked-data-structure scenario clearly
+demonstrates the need for RCU's stringent memory-ordering guarantees on
+systems with more than one CPU:
 
 <ol>
 <li>	Each CPU that has an RCU read-side critical section that

@@ -554,30 +584,12 @@ Are all these memory barriers <i> really</i> required?
 <br><a href="#qq6answer">Answer</a>
 
 <p>
-In short, RCU's publish-subscribe guarantee is provided by the combination
-of <tt>rcu_assign_pointer()</tt> and <tt>rcu_dereference()</tt>.
-This guarantee allows data elements to be safely added to RCU-protected
-linked data structures without disrupting RCU readers.
-This guarantee can be used in combination with the grace-period
-guarantee to also allow data elements to be removed from RCU-protected
-linked data structures, again without disrupting RCU readers.
-
-<p>
-This guarantee was only partially premeditated.
-DYNIX/ptx used an explicit memory barrier for publication, but had nothing
-resembling <tt>rcu_dereference()</tt> for subscription, nor did it
-have anything resembling the <tt>smp_read_barrier_depends()</tt>
-that was later subsumed into <tt>rcu_dereference()</tt>.
-The need for these operations made itself known quite suddenly at a
-late-1990s meeting with the DEC Alpha architects, back in the days when
-DEC was still a free-standing company.
-It took the Alpha architects a good hour to convince me that any sort
-of barrier would ever be needed, and it then took me a good <i>two</i> hours
-to convince them that their documentation did not make this point clear.
-More recent work with the C and C++ standards committees have provided
-much education on tricks and traps from the compiler.
-In short, compilers were much less tricky in the early 1990s, but in
-2015, don't even think about omitting <tt>rcu_dereference()</tt>!
+Note that these memory-barrier requirements do not replace the fundamental
+RCU requirement that a grace period wait for all pre-existing readers.
+On the contrary, the memory barriers called out in this section must operate in
+such a way as to <i>enforce</i> this fundamental requirement.
+Of course, different implementations enforce this requirement in different
+ways, but enforce it they must.
 
 <h3><a name="RCU Primitives Guaranteed to Execute Unconditionally">RCU Primitives Guaranteed to Execute Unconditionally</a></h3>
 

84 lines not on this page · raw message

index 96cdcf7195d5..a725f9900ec8 100644
@@ -1,5 +1,5 @@
 <!-- DO NOT HAND EDIT. -->
-<!-- Instead, edit Requirements.htmlx and run 'sh htmlqqz.sh Requirements' -->
+<!-- Instead, edit Documentation/RCU/Design/Requirements/Requirements.htmlx and run 'sh htmlqqz.sh Documentation/RCU/Design/Requirements/Requirements' -->
 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
         "http://www.w3.org/TR/html4/loose.dtd">
         <html>

@@ -1957,7 +1957,7 @@ the runqueue locks and the priority-inheritance locks
 in the middle of an outermost RCU read-side critical section unless either
 (1) it releases them before exiting that same
 RCU read-side critical section, or
-(2) preemption is disabled across
+(2) interrupts are disabled across
 that entire RCU read-side critical section.
 This same prohibition also applies (recursively!) to any lock that is acquired
 while holding any lock to which this prohibition applies.

@@ -1966,6 +1966,14 @@ Adhering to this rule prevents preemptible RCU from invoking
 priority-inheritance locks are held, thus avoiding deadlock.
 
 <p>
+Prior to v4.4, it was only necessary to disable preemption across
+RCU read-side critical sections that acquired scheduler locks.
+In v4.4, expedited grace periods started using IPIs, and these
+IPIs could force a <tt>rcu_read_unlock()</tt> to take the slowpath.
+Therefore, this expedited-grace-period change required disabling of
+interrupts, not just preemption.
+
+<p>
 For RCU's part, the preemptible-RCU <tt>rcu_read_unlock()</tt>
 implementation must be written carefully to avoid similar deadlocks.
 In particular, <tt>rcu_read_unlock()</tt> must tolerate an

index 2d0cd90987f6..3a97ba490c42 100644
@@ -2124,7 +2124,7 @@ the runqueue locks and the priority-inheritance locks
 in the middle of an outermost RCU read-side critical section unless either
 (1) it releases them before exiting that same
 RCU read-side critical section, or
-(2) preemption is disabled across
+(2) interrupts are disabled across
 that entire RCU read-side critical section.
 This same prohibition also applies (recursively!) to any lock that is acquired
 while holding any lock to which this prohibition applies.

@@ -2133,6 +2133,14 @@ Adhering to this rule prevents preemptible RCU from invoking
 priority-inheritance locks are held, thus avoiding deadlock.
 
 <p>
+Prior to v4.4, it was only necessary to disable preemption across
+RCU read-side critical sections that acquired scheduler locks.
+In v4.4, expedited grace periods started using IPIs, and these
+IPIs could force a <tt>rcu_read_unlock()</tt> to take the slowpath.
+Therefore, this expedited-grace-period change required disabling of
+interrupts, not just preemption.
+
+<p>
 For RCU's part, the preemptible-RCU <tt>rcu_read_unlock()</tt>
 implementation must be written carefully to avoid similar deadlocks.
 In particular, <tt>rcu_read_unlock()</tt> must tolerate an

index aef9487303d0..85304ebd187c 100644
@@ -194,7 +194,7 @@ There are some minimal guarantees that may be expected of a CPU:
  (*) On any given CPU, dependent memory accesses will be issued in order, with
      respect to itself.  This means that for:
 
-	WRITE_ONCE(Q, P); smp_read_barrier_depends(); D = READ_ONCE(*Q);
+	Q = READ_ONCE(P); smp_read_barrier_depends(); D = READ_ONCE(*Q);
 
      the CPU will issue the following memory operations:
 

@@ -202,9 +202,9 @@ There are some minimal guarantees that may be expected of a CPU:
 
      and always in that order.  On most systems, smp_read_barrier_depends()
      does nothing, but it is required for DEC Alpha.  The READ_ONCE()
-     and WRITE_ONCE() are required to prevent compiler mischief.  Please
-     note that you should normally use something like rcu_dereference()
-     instead of open-coding smp_read_barrier_depends().
+     is required to prevent compiler mischief.  Please note that you
+     should normally use something like rcu_dereference() instead of
+     open-coding smp_read_barrier_depends().
 
  (*) Overlapping loads and stores within a particular CPU will appear to be
      ordered within that CPU.  This means that for: