=================================================
A Tour Through TREE_RCU's Expedited Grace Periods
=================================================

Introduction
============

This document describes RCU's expedited grace periods.
Unlike RCU's normal grace periods, which accept long latencies to attain
high efficiency and minimal disturbance, expedited grace periods accept
lower efficiency and significant disturbance to attain shorter latencies.

There are two flavors of RCU (RCU-preempt and RCU-sched), with an earlier
third RCU-bh flavor having been implemented in terms of the other two.
Each of the two implementations is covered in its own section.

Expedited Grace Period Design
=============================

The expedited RCU grace periods cannot be accused of being subtle,
given that they for all intents and purposes hammer every CPU that
has not yet provided a quiescent state for the current expedited
grace period.
The one saving grace is that the hammer has grown a bit smaller
over time:  The old call to ``try_stop_cpus()`` has been
replaced with a set of calls to ``smp_call_function_single()``,
each of which results in an IPI to the target CPU.
The corresponding handler function checks the CPU's state, motivating
a faster quiescent state where possible, and triggering a report
of that quiescent state.
As always for RCU, once everything has spent some time in a quiescent
state, the expedited grace period has completed.

The details of the ``smp_call_function_single()`` handler's
operation depend on the RCU flavor, as described in the following
sections.

RCU-preempt Expedited Grace Periods
===================================

``CONFIG_PREEMPTION=y`` kernels implement RCU-preempt.
The overall flow of the handling of a given CPU by an RCU-preempt
expedited grace period is shown in the following diagram:

.. kernel-figure:: ExpRCUFlow.svg

The solid arrows denote direct action, for example, a function call.
The dotted arrows denote indirect action, for example, an IPI
or a state that is reached after some time.

If a given CPU is offline or idle, ``synchronize_rcu_expedited()``
will ignore it because idle and offline CPUs are already residing
in quiescent states.
Otherwise, the expedited grace period will use
``smp_call_function_single()`` to send the CPU an IPI, which
is handled by ``rcu_exp_handler()``.

However, because this is preemptible RCU, ``rcu_exp_handler()``
can check to see if the CPU is currently running in an RCU read-side
critical section.
If not, the handler can immediately report a quiescent state.
Otherwise, it sets flags so that the outermost ``rcu_read_unlock()``
invocation will provide the needed quiescent-state report.
This flag-setting avoids the previous forced preemption of all
CPUs that might have RCU read-side critical sections.
In addition, this flag-setting is done so as to avoid increasing
the overhead of the common-case fastpath through the scheduler.

Again because this is preemptible RCU, an RCU read-side critical section
can be preempted.
When that happens, RCU will enqueue the task, which will the continue to
block the current expedited grace period until it resumes and finds its
outermost ``rcu_read_unlock()``.
The CPU will report a quiescent state just after enqueuing the task because
the CPU is no longer blocking the grace period.
It is instead the preempted task doing the blocking.
The list of blocked tasks is managed by ``rcu_preempt_ctxt_queue()``,
which is called from ``rcu_preempt_note_context_switch()``, which
in turn is called from ``rcu_note_context_switch()``, which in
turn is called from the scheduler.


+-----------------------------------------------------------------------+
| **Quick Quiz**:                                                       |
+-----------------------------------------------------------------------+
| Why not just have the expedited grace period check the state of all   |
| the CPUs? After all, that would avoid all those real-time-unfriendly  |
| IPIs.                                                                 |
+-----------------------------------------------------------------------+
| **Answer**:                                                           |
+-----------------------------------------------------------------------+
| Because we want the RCU read-side critical sections to run fast,      |
| which means no memory barriers. Therefore, it is not possible to      |
| safely check the state from some other CPU. And even if it was        |
| possible to safely check the state, it would still be necessary to    |
| IPI the CPU to safely interact with the upcoming                      |
| ``rcu_read_unlock()`` invocation, which means that the remote state   |
| testing would not help the worst-case latency that real-time          |
| applications care about.                                              |
|                                                                       |
| One way to prevent your real-time application from getting hit with   |
| these IPIs is to build your kernel with ``CONFIG_NO_HZ_FULL=y``. RCU  |
| would then perceive the CPU running your application as being idle,   |
| and it would be able to safely detect that state without needing to   |
| IPI the CPU.                                                          |
+-----------------------------------------------------------------------+

Please note that this is just the overall flow: Additional complications
can arise due to races with CPUs going idle or offline, among other
things.

RCU-sched Expedited Grace Periods
---------------------------------

``CONFIG_PREEMPTION=n`` kernels implement RCU-sched. The overall flow of
the handling of a given CPU by an RCU-sched expedited grace period is
shown in the following diagram:

.. kernel-figure:: ExpSchedFlow.svg

As with RCU-preempt, RCU-sched's ``synchronize_rcu_expedited()`` ignores
offline and idle CPUs, again because they are in remotely detectable
quiescent states. However, because the ``rcu_read_lock_sched()`` and
``rcu_read_unlock_sched()`` leave no trace of their invocation, in
general it is not possible to tell whether or not the current CPU is in
an RCU read-side critical section. The best that RCU-sched's
``rcu_exp_handler()`` can do is to check for idle, on the off-chance
that the CPU went idle while the IPI was in flight. If the CPU is idle,
then ``rcu_exp_handler()`` reports the quiescent state.

Otherwise, the handler forces a future context switch by setting the
NEED_RESCHED flag of the current task's thread flag and the CPU preempt
counter. At the time of the context switch, the CPU reports the
quiescent state. Should the CPU go offline first, it will report the
quiescent state at that time.

Expedited Grace Period and CPU Hotplug
--------------------------------------

The expedited nature of expedited grace periods require a much tighter
interaction with CPU hotplug operations than is required for normal
grace periods. In addition, attempting to IPI offline CPUs will result
in splats, but failing to IPI online CPUs can result in too-short grace
periods. Neither option is acceptable in production kernels.

The interaction between expedited grace periods and CPU hotplug
operations is carried out at several levels:

#. The number of CPUs that have ever been online is tracked by the
   ``rcu_state`` structure's ``->ncpus`` field. The ``rcu_state``
   structure's ``->ncpus_snap`` field tracks the number of CPUs that
   have ever been online at the beginning of an RCU expedited grace
   period. Note that this number never decreases, at least in the
   absence of a time machine.
#. The identities of the CPUs that have ever been online is tracked by
   the ``rcu_node`` structure's ``->expmaskinitnext`` field. The
   ``rcu_node`` structure's ``->expmaskinit`` field tracks the
   identities of the CPUs that were online at least once at the
   beginning of the most recent RCU expedited grace period. The
   ``rcu_state`` structure's ``->ncpus`` and ``->ncpus_snap`` fields are
   used to detect when new CPUs have come online for the first time,
   that is, when the ``rcu_node`` structure's ``->expmaskinitnext``
   field h                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         