rcu: Use single-stage IPI algorithm for RCU expedited grace period
authorPaul E. McKenney <paulmck@linux.vnet.ibm.com>
Sun, 2 Aug 2015 20:53:17 +0000 (13:53 -0700)
committerPaul E. McKenney <paulmck@linux.vnet.ibm.com>
Mon, 21 Sep 2015 04:16:19 +0000 (21:16 -0700)
commit8203d6d0ee784cfb2ebf89053f7fe399abc867d7
treecb0598f473834f117a06b1eeab32576fcddd0e52
parentb9585e940a0d78770cda8f9aebf81b17b4d19e6d
rcu: Use single-stage IPI algorithm for RCU expedited grace period

The current preemptible-RCU expedited grace-period algorithm invokes
synchronize_sched_expedited() to enqueue all tasks currently running
in a preemptible-RCU read-side critical section, then waits for all the
->blkd_tasks lists to drain.  This works, but results in both an IPI and
a double context switch even on CPUs that do not happen to be running
in a preemptible RCU read-side critical section.

This commit implements a new algorithm that causes less OS jitter.
This new algorithm IPIs all online CPUs that are not idle (from an
RCU perspective), but refrains from self-IPIs.  If a CPU receiving
this IPI is not in a preemptible RCU read-side critical section (or
is just now exiting one), it pushes quiescence up the rcu_node tree,
otherwise, it sets a flag that will be handled by the upcoming outermost
rcu_read_unlock(), which will then push quiescence up the tree.

The expedited grace period must of course wait on any pre-existing blocked
readers, and newly blocked readers must be queued carefully based on
the state of both the normal and the expedited grace periods.  This
new queueing approach also avoids the need to update boost state,
courtesy of the fact that blocked tasks are no longer ever migrated to
the root rcu_node structure.

Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
include/linux/sched.h
kernel/rcu/tree.c
kernel/rcu/tree_plugin.h