ADD: rcu: Add a TINY_PREEMPT_RCU

    Implement a small-memory-footprint uniprocessor-only implementation of
    preemptible RCU.  This implementation uses but a single blocked-tasks
    list rather than the combinatorial number used per leaf rcu_node by
    TREE_PREEMPT_RCU, which reduces memory consumption and greatly simplifies
    processing.  This version also takes advantage of uniprocessor execution
    to accelerate grace periods in the case where there are no readers.

    The general design is otherwise broadly similar to that of TREE_PREEMPT_RCU.

    This implementation is a step towards having RCU implementation driven
    off of the SMP and PREEMPT kernel configuration variables, which can
    happen once this implementation has accumulated sufficient experience.

    Removed ACCESS_ONCE() from __rcu_read_unlock() and added barrier() as
    suggested by Steve Rostedt in order to avoid the compiler-reordering
    issue noted by Mathieu Desnoyers (http://lkml.org/lkml/2010/8/16/183).

    As can be seen below, CONFIG_TINY_PREEMPT_RCU represents almost 5Kbyte
    savings compared to CONFIG_TREE_PREEMPT_RCU.  Of course, for non-real-time
    workloads, CONFIG_TINY_RCU is even better.

    	CONFIG_TREE_PREEMPT_RCU

    	   text	   data	    bss	    dec	   filename
    	     13	      0	      0	     13	   kernel/rcupdate.o
    	   6170	    825	     28	   7023	   kernel/rcutree.o
    				   ----
    				   7026    Total

    	CONFIG_TINY_PREEMPT_RCU

    	   text	   data	    bss	    dec	   filename
    	     13	      0	      0	     13	   kernel/rcupdate.o
    	   2081	     81	      8	   2170	   kernel/rcutiny.o
    				   ----
    				   2183    Total

    	CONFIG_TINY_RCU (non-preemptible)

    	   text	   data	    bss	    dec	   filename
    	     13	      0	      0	     13	   kernel/rcupdate.o
    	    719	     25	      0	    744	   kernel/rcutiny.o
    				    ---
    				    757    Total

    Requested-by: Loïc Minier <loic.minier@canonical.com>
    Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
rcu: apply TINY_PREEMPT_RCU read-side speedup to TREE_PREEMPT_RCU

    Replace one of the ACCESS_ONCE() calls in each of __rcu_read_lock()
    and __rcu_read_unlock() with barrier() as suggested by Steve Rostedt in
    order to avoid the potential compiler-optimization-induced bug noted by
    Mathieu Desnoyers.

    Located-by: Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>
    Suggested-by: Steven Rostedt <rostedt@goodmis.org>
    Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
rcu: move TINY_RCU from softirq to kthread

    If RCU priority boosting is to be meaningful, callback invocation must
    be boosted in addition to preempted RCU readers.  Otherwise, in presence
    of CPU real-time threads, the grace period ends, but the callbacks don't
    get invoked.  If the callbacks don't get invoked, the associated memory
    doesn't get freed, so the system is still subject to OOM.

    But it is not reasonable to priority-boost RCU_SOFTIRQ, so this commit
    moves the callback invocations to a kthread, which can be boosted easily.

    Signed-off-by: Paul E. McKenney <paul.mckenney@linaro.org>
    Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
rcu: priority boosting for TINY_PREEMPT_RCU

    Add priority boosting, but only for TINY_PREEMPT_RCU.  This is enabled
    by the default-off RCU_BOOST kernel parameter.  The priority to which to
    boost preempted RCU readers is controlled by the RCU_BOOST_PRIO kernel
    parameter (defaulting to real-time priority 1) and the time to wait
    before boosting the readers blocking a given grace period is controlled
    by the RCU_BOOST_DELAY kernel parameter (defaulting to 500 milliseconds).

    Signed-off-by: Paul E. McKenney <paul.mckenney@linaro.org>
    Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
rcu: avoid pointless blocked-task warnings

    If the RCU callback-processing kthread has nothing to do, it parks in
    a wait_event().  If RCU remains idle for more than two minutes, the
    kernel complains about this.  This commit changes from wait_event()
    to wait_event_interruptible() to prevent the kernel from complaining
    just because RCU is idle.

    Reported-by: Russell King <rmk+kernel@arm.linux.org.uk>
    Signed-off-by: Paul E. McKenney <paul.mckenney@linaro.org>
    Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
    Tested-by: Thomas Weber <weber@corscience.de>
    Tested-by: Russell King <rmk+kernel@arm.linux.org.uk>
rcu: add tracing for TINY_RCU and TINY_PREEMPT_RCU

    Add tracing for the tiny RCU implementations, including statistics on
    boosting in the case of TINY_PREEMPT_RCU and RCU_BOOST.

    Signed-off-by: Paul E. McKenney <paul.mckenney@linaro.org>
    Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
rcu: document TINY_RCU and TINY_PREEMPT_RCU tracing.

    Add the required verbiage to Documentation/RCU/trace.txt.

    Signed-off-by: Paul E. McKenney <paul.mckenney@linaro.org>
    Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
rcu: Distinguish between boosting and boosted

    RCU priority boosting's tracing did not distinguish between ongoing
    boosting and completion of boosting.  This commit therefore adds this
    capability.

    Signed-off-by: Paul E. McKenney <paul.mckenney@linaro.org>
    Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
rcu: get rid of obsolete "classic" names in TREE_RCU tracing

    The TREE_RCU tracing had obsolete rcuclassic_trace_init() and
    rcuclassic_trace_cleanup() function names.  This commit brings them
    up to date: rcutree_trace_init() and rcutree_trace_cleanup(),
    respectively.

    Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
rcu,cleanup: move synchronize_sched_expedited() out of sched.c

    The first version of synchronize_sched_expedited() used the migration
    code in the scheduler, and was therefore implemented in kernel/sched.c.
    However, the more recent version of this code no longer uses the
    migration code, so this commit moves it to the main RCU source files.

    Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
    Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>

Signed-off-by: scotthartbti <scott.hart.bti@gmail.com>

Conflicts:

	kernel/sched.c

Conflicts:
	kernel/sched.c
	kernel/sched_bfs.c
rcu: remove unused __list_for_each_rcu() macro

    Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
rcu: Make synchronize_srcu_expedited() fast if running readers

The synchronize_srcu_expedited() function is currently quick if there
are no active readers, but will delay a full jiffy if there are any.
If these readers leave their SRCU read-side critical sections quickly,
this is way too long to wait.  So this commit first waits ten microseconds,
and only then falls back to jiffy-at-a-time waiting.

Reported-by: Avi Kivity <avi@redhat.com>
Reported-by: Marcelo Tosatti <mtosatti@redhat.com>
Tested-by: Takuya Yoshikawa <yoshikawa.takuya@oss.ntt.co.jp>
Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
rcu: fine-tune grace-period begin/end checks

Use the CPU's bit in rnp->qsmask to determine whether or not the CPU
should try to report a quiescent state.  Handle overflow in the check
for rdp->gpnum having fallen behind.

Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
rcu: limit rcu_node leaf-level fanout

Some recent benchmarks have indicated possible lock contention on the
leaf-level rcu_node locks.  This commit therefore limits the number of
CPUs per leaf-level rcu_node structure to 16, in other words, there
can be at most 16 rcu_data structures fanning into a given rcu_node
structure.  Prior to this, the limit was 32 on 32-bit systems and 64 on
64-bit systems.

Note that the fanout of non-leaf rcu_node structures is unchanged.  The
organization of accesses to the rcu_node tree is such that references
to non-leaf rcu_node structures are much less frequent than to the
leaf structures.

Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
rcu: reduce __call_rcu()-induced contention on rcu_node structures

When the current __call_rcu() function was written, the expedited
APIs did not exist.  The __call_rcu() implementation therefore went
to great lengths to detect the end of old grace periods and to start
new ones, all in the name of reducing grace-period latency.  Now the
expedited APIs do exist, and the usage of __call_rcu() has increased
considerably.  This commit therefore causes __call_rcu() to avoid
worrying about grace periods unless there are a large number of
RCU callbacks stacked up on the current CPU.

Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
rcu: demote SRCU_SYNCHRONIZE_DELAY from kernel-parameter status

Because the adaptive synchronize_srcu_expedited() approach has
worked very well in testing, remove the kernel parameter and
replace it by a C-preprocessor macro.  If someone finds problems
with this approach, a more complex and aggressively adaptive
approach might be required.

Longer term, SRCU will be merged with the other RCU implementations,
at which point synchronize_srcu_expedited() will be event driven,
just as synchronize_sched_expedited() currently is.  At that point,
there will be no need for this adaptive approach.

Reported-by: Linus Torvalds <torvalds@linux-foundation.org>
Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
rcu: optimize rcutiny

    rcu_sched_qs() currently calls local_irq_save()/local_irq_restore() up
    to three times.

    Remove irq masking from rcu_qsctr_help() / invoke_rcu_kthread()
    and do it once in rcu_sched_qs() / rcu_bh_qs()

    This generates smaller code as well.

       text	   data	    bss	    dec	    hex	filename
       2314	    156	     24	   2494	    9be	kernel/rcutiny.old.o
       2250	    156	     24	   2430	    97e	kernel/rcutiny.new.o

    Fix an outdated comment for rcu_qsctr_help()
    Move invoke_rcu_kthread() definition before its use.

    Signed-off-by: Eric Dumazet <eric.dumazet@gmail.com>
    Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
    Reviewed-by: Josh Triplett <josh@joshtriplett.org>
rcu: add an rcu_dereference_index_check()

The sparse RCU-pointer checking relies on type magic that dereferences
the pointer in question.  This does not work if the pointer is in fact
an array index.  This commit therefore supplies a new RCU API that
omits the sparse checking to continue to support rcu_dereference()
on integers.

Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
rcu: improve kerneldoc for rcu_read_lock(), call_rcu(), and synchronize_rcu()

Make it explicit that new RCU read-side critical sections that start
after call_rcu() and synchronize_rcu() start might still be running
after the end of the relevant grace period.

Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Reviewed-by: Josh Triplett <josh@joshtriplett.org>
rcu: update obsolete rcu_read_lock() comment.

The comment says that blocking is illegal in rcu_read_lock()-style
RCU read-side critical sections, which is no longer entirely true
given preemptible RCU.  This commit provides a fix.

Suggested-by: David Miller <davem@davemloft.net>
Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>