rcu: 1Q2010 update for RCU documentation

Add expedited functions.  Review documentation and update
obsolete verbiage.  Also fix the advice for the RCU CPU-stall
kernel configuration parameter, and document RCU CPU-stall
warnings.

Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Cc: laijs@cn.fujitsu.com
Cc: dipankar@in.ibm.com
Cc: mathieu.desnoyers@polymtl.ca
Cc: josh@joshtriplett.org
Cc: dvhltc@us.ibm.com
Cc: niv@us.ibm.com
Cc: peterz@infradead.org
Cc: rostedt@goodmis.org
Cc: Valdis.Kletnieks@vt.edu
Cc: dhowells@redhat.com
LKML-Reference: <12635142581866-git-send-email->
Signed-off-by: Ingo Molnar <mingo@elte.hu>

9 files changed, 258 insertions, 136 deletions

diff --git a/Documentation/RCU/00-INDEX b/Documentation/RCU/00-INDEX
index 9bb62f7b89c3..0a27ea9621fa 100644
--- a/Documentation/RCU/00-INDEX
+++ b/Documentation/RCU/00-INDEX
@@ -8,14 +8,18 @@ listRCU.txt
         - Using RCU to Protect Read-Mostly Linked Lists
 NMI-RCU.txt
         - Using RCU to Protect Dynamic NMI Handlers
+rcubarrier.txt
+        - RCU and Unloadable Modules
+rculist_nulls.txt
+        - RCU list primitives for use with SLAB_DESTROY_BY_RCU
 rcuref.txt
         - Reference-count design for elements of lists/arrays protected by RCU
 rcu.txt
         - RCU Concepts
-rcubarrier.txt
-        - Unloading modules that use RCU callbacks
 RTFP.txt
         - List of RCU papers (bibliography) going back to 1980.
+stallwarn.txt
+        - RCU CPU stall warnings (CONFIG_RCU_CPU_STALL_DETECTOR)
 torture.txt
         - RCU Torture Test Operation (CONFIG_RCU_TORTURE_TEST)
 trace.txt
diff --git a/Documentation/RCU/RTFP.txt b/Documentation/RCU/RTFP.txt
index d2b85237c76e..5051209e6835 100644
--- a/Documentation/RCU/RTFP.txt
+++ b/Documentation/RCU/RTFP.txt
@@ -25,10 +25,10 @@ to be referencing the data structure.  However, this mechanism was not
 optimized for modern computer systems, which is not surprising given
 that these overheads were not so expensive in the mid-80s.  Nonetheless,
 passive serialization appears to be the first deferred-destruction
-mechanism to be used in production.  Furthermore, the relevant patent has
-lapsed, so this approach may be used in non-GPL software, if desired.
-(In contrast, use of RCU is permitted only in software licensed under
-GPL.  Sorry!!!)
+mechanism to be used in production.  Furthermore, the relevant patent
+has lapsed, so this approach may be used in non-GPL software, if desired.
+(In contrast, implementation of RCU is permitted only in software licensed
+under either GPL or LGPL.  Sorry!!!)
 
 In 1990, Pugh [Pugh90] noted that explicitly tracking which threads
 were reading a given data structure permitted deferred free to operate
@@ -150,6 +150,18 @@ preemptible RCU [PaulEMcKenney2007PreemptibleRCU], and the three-part
 LWN "What is RCU?" series [PaulEMcKenney2007WhatIsRCUFundamentally,
 PaulEMcKenney2008WhatIsRCUUsage, and PaulEMcKenney2008WhatIsRCUAPI].
 
+2008 saw a journal paper on real-time RCU [DinakarGuniguntala2008IBMSysJ],
+a history of how Linux changed RCU more than RCU changed Linux
+[PaulEMcKenney2008RCUOSR], and a design overview of hierarchical RCU
+[PaulEMcKenney2008HierarchicalRCU].
+
+2009 introduced user-level RCU algorithms [PaulEMcKenney2009MaliciousURCU],
+which Mathieu Desnoyers is now maintaining [MathieuDesnoyers2009URCU]
+[MathieuDesnoyersPhD].  TINY_RCU [PaulEMcKenney2009BloatWatchRCU] made
+its appearance, as did expedited RCU [PaulEMcKenney2009expeditedRCU].
+The problem of resizeable RCU-protected hash tables may now be on a path
+to a solution [JoshTriplett2009RPHash].
+
 Bibtex Entries
 
 @article{Kung80
@@ -730,6 +742,11 @@ Revised:
 "
 }
 
+#
+#       "What is RCU?" LWN series.
+#
+########################################################################
+
 @article{DinakarGuniguntala2008IBMSysJ
 ,author="D. Guniguntala and P. E. McKenney and J. Triplett and J. Walpole"
 ,title="The read-copy-update mechanism for supporting real-time applications on shared-memory multiprocessor systems with {Linux}"
@@ -820,3 +837,36 @@ Revised:
         Uniprocessor assumptions allow simplified RCU implementation.
 "
 }
+
+@unpublished{PaulEMcKenney2009expeditedRCU
+,Author="Paul E. McKenney"
+,Title="[{PATCH} -tip 0/3] expedited 'big hammer' {RCU} grace periods"
+,month="June"
+,day="25"
+,year="2009"
+,note="Available:
+\url{http://lkml.org/lkml/2009/6/25/306}
+[Viewed August 16, 2009]"
+,annotation="
+        First posting of expedited RCU to be accepted into -tip.
+"
+}
+
+@unpublished{JoshTriplett2009RPHash
+,Author="Josh Triplett"
+,Title="Scalable concurrent hash tables via relativistic programming"
+,month="September"
+,year="2009"
+,note="Linux Plumbers Conference presentation"
+,annotation="
+        RP fun with hash tables.
+"
+}
+
+@phdthesis{MathieuDesnoyersPhD
+, title  = "Low-impact Operating System Tracing"
+, author = "Mathieu Desnoyers"
+, school = "Ecole Polytechnique de Montr\'{e}al"
+, month  = "December"
+, year   = 2009
+}
diff --git a/Documentation/RCU/checklist.txt b/Documentation/RCU/checklist.txt
index 51525a30e8b4..767cf06a4276 100644
--- a/Documentation/RCU/checklist.txt
+++ b/Documentation/RCU/checklist.txt
@@ -8,13 +8,12 @@ would cause.  This list is based on experiences reviewing such patches
 over a rather long period of time, but improvements are always welcome!
 
 0.      Is RCU being applied to a read-mostly situation?  If the data
-        structure is updated more than about 10% of the time, then
-        you should strongly consider some other approach, unless
-        detailed performance measurements show that RCU is nonetheless
-        the right tool for the job.  Yes, you might think of RCU
-        as simply cutting overhead off of the readers and imposing it
-        on the writers.  That is exactly why normal uses of RCU will
-        do much more reading than updating.
+        structure is updated more than about 10% of the time, then you
+        should strongly consider some other approach, unless detailed
+        performance measurements show that RCU is nonetheless the right
+        tool for the job.  Yes, RCU does reduce read-side overhead by
+        increasing write-side overhead, which is exactly why normal uses
+        of RCU will do much more reading than updating.
 
         Another exception is where performance is not an issue, and RCU
         provides a simpler implementation.  An example of this situation
@@ -35,13 +34,13 @@ over a rather long period of time, but improvements are always welcome!
 
         If you choose #b, be prepared to describe how you have handled
         memory barriers on weakly ordered machines (pretty much all of
-        them -- even x86 allows reads to be reordered), and be prepared
-        to explain why this added complexity is worthwhile.  If you
-        choose #c, be prepared to explain how this single task does not
-        become a major bottleneck on big multiprocessor machines (for
-        example, if the task is updating information relating to itself
-        that other tasks can read, there by definition can be no
-        bottleneck).
+        them -- even x86 allows later loads to be reordered to precede
+        earlier stores), and be prepared to explain why this added
+        complexity is worthwhile.  If you choose #c, be prepared to
+        explain how this single task does not become a major bottleneck on
+        big multiprocessor machines (for example, if the task is updating
+        information relating to itself that other tasks can read, there
+        by definition can be no bottleneck).
 
 2.      Do the RCU read-side critical sections make proper use of
         rcu_read_lock() and friends?  These primitives are needed
@@ -51,8 +50,10 @@ over a rather long period of time, but improvements are always welcome!
         actuarial risk of your kernel.
 
         As a rough rule of thumb, any dereference of an RCU-protected