TREE_RCU의 expedited grace period 둘러보기

Expedited grace period의 목적

이 문서는 RCU의 expedited grace period를 설명합니다. Normal grace period는 효율을 높이고 시스템 교란을 최소화하기 위해 긴 latency를 받아들이지만, expedited grace period는 짧은 latency를 얻기 위해 효율 저하와 상당한 교란을 감수합니다.

현재 설명 대상은 RCU-preempt와 RCU-sched 두 flavor입니다. 과거의 세 번째 RCU-bh flavor는 이 둘을 이용해 구현됐으며, 두 현행 구현은 각각 별도 절에서 다룹니다.

=================================================
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.

IPI 기반 expedited GP 설계

Expedited GP는 현재 GP에 필요한 quiescent state를 아직 내지 않은 모든 CPU를 적극적으로 재촉합니다. 예전의 `try_stop_cpus()` 호출은 각 대상 CPU에 IPI를 일으키는 `smp_call_function_single()` 호출 묶음으로 대체되어 충격은 줄었지만, 여전히 시간 우선 설계입니다.

대상 CPU의 handler는 CPU 상태를 검사하고 가능한 경우 더 빠른 quiescent state로 가도록 유도한 뒤 그 상태를 보고합니다. 필요한 모든 실행 주체가 quiescent state를 거치면 expedited grace period가 끝납니다. Handler의 구체적인 동작은 RCU flavor마다 다릅니다.

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의 CPU와 task 추적

`CONFIG_PREEMPTION=y` 커널은 RCU-preempt를 구현합니다. ExpRCUFlow.svg의 실선은 function call 같은 직접 동작, 점선은 IPI나 시간이 지나 도달하는 상태 같은 간접 동작을 뜻합니다.

`synchronize_rcu_expedited()`는 offline 또는 idle CPU를 이미 quiescent state에 있다고 보고 무시합니다. 그 밖의 CPU에는 `smp_call_function_single()`로 IPI를 보내 `rcu_exp_handler()`가 처리합니다.

Preemptible RCU이므로 handler는 현재 CPU가 RCU read-side critical section 안인지 확인할 수 있습니다. 밖이라면 즉시 quiescent state를 보고합니다. 안이라면 가장 바깥 `rcu_read_unlock()`이 필요한 보고를 하도록 flag를 설정합니다. 이 방법은 read section이 있을 수 있는 CPU를 예전처럼 강제 preempt하지 않고 scheduler common fastpath의 overhead도 늘리지 않습니다.

Read-side critical section 도중 task가 preempt되면 RCU가 task를 queue하며, task가 다시 실행해 가장 바깥 `rcu_read_unlock()`을 만날 때까지 현재 expedited GP를 막습니다. CPU 자체는 task를 queue한 직후 더 이상 blocker가 아니므로 quiescent state를 보고합니다. Blocked-task list는 scheduler의 `rcu_note_context_switch()`에서 `rcu_preempt_note_context_switch()`를 거쳐 호출되는 `rcu_preempt_ctxt_queue()`가 관리합니다.

다른 CPU가 reader 상태를 직접 검사해 IPI를 피할 수는 없습니다. 빠른 RCU reader에는 memory barrier가 없으므로 remote CPU가 그 상태를 안전하게 판정할 수 없고, 판정이 가능하더라도 앞으로의 `rcu_read_unlock()`과 안전하게 상호작용하려면 결국 IPI가 필요해 worst-case RT latency가 줄지 않습니다. `CONFIG_NO_HZ_FULL=y`로 RT application CPU를 RCU가 idle로 인식하게 하면 IPI를 피할 수 있습니다.

이 흐름에는 CPU가 동시에 idle 또는 offline으로 전환하는 race 등 추가 복잡성이 있습니다.

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의 context-switch 강제

`CONFIG_PREEMPTION=n` 커널은 RCU-sched를 구현합니다. RCU-preempt와 마찬가지로 offline과 idle CPU는 remote에서 확인 가능한 quiescent state에 있으므로 무시합니다.

그러나 `rcu_read_lock_sched()`와 `rcu_read_unlock_sched()`은 호출 흔적을 남기지 않아 CPU가 read-side critical section 안인지 일반적으로 알 수 없습니다. `rcu_exp_handler()`는 IPI가 이동 중일 때 CPU가 idle에 들어갔는지만 확인할 수 있고, idle이면 바로 보고합니다.

Idle이 아니면 현재 task의 thread flag와 CPU preempt counter에 `NEED_RESCHED`를 설정해 미래 context switch를 강제합니다. CPU는 context switch 때 quiescent state를 보고하며, 그보다 먼저 offline되면 offline 과정에서 보고합니다.

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 GP와 CPU hotplug의 다중 snapshot

Expedited GP는 normal GP보다 CPU hotplug과 훨씬 긴밀히 조정해야 합니다. Offline CPU에 IPI를 보내면 splat이 나고 online CPU를 놓치면 GP가 너무 일찍 끝나므로 둘 다 허용할 수 없습니다.

`rcu_state.ncpus`는 한 번이라도 online이었던 CPU 수를, `ncpus_snap`은 expedited GP 시작 시점의 그 수를 기록합니다. 이 수는 time machine이 없는 한 감소하지 않습니다. `rcu_node.expmaskinitnext`는 한 번이라도 online이었던 CPU의 identity를 추적하고, `expmaskinit`은 가장 최근 expedited GP 시작 시점의 snapshot입니다.

`ncpus`와 `ncpus_snap`의 차이로 마지막 GP 뒤 처음 online된 CPU가 있는지 감지합니다. 변화가 있으면 각 node의 `expmaskinit`을 `expmaskinitnext`에서 갱신합니다. GP 시작에는 `expmaskinit`으로 `expmask`를 초기화하므로 한 번이라도 online이었던 CPU만 대상이 됩니다.

Offline CPU는 leaf `rcu_node.qsmaskinitnext`에서 자기 bit를 지우므로 bit가 clear면 안전하게 무시할 수 있습니다. 다만 online/offline 진행 중에는 `cpu_online()`이 false인데 bit가 잠시 set일 수 있습니다. RCU가 online이라고 보는 non-idle CPU에 `smp_call_function_single()`이 성공하면 완전히 online이었고, 실패하면 online 또는 offline 전환 중이므로 hotplug 작업이 끝나도록 잠시 기다린 뒤 재시도합니다. RCU-sched에서 outgoing CPU가 마지막에 `rcutree_report_cpu_dead()`로 QS를 보고하는 것은 아마도 방어적 중복입니다.

현재 online CPU mask 하나만 유지하면 GP 초기화가 tree 아래로 진행하는 동시에 CPU-offline이 위로 진행할 때 상위에는 bit가 남고 하위 counterpart는 사라질 수 있습니다. 그 bit는 영원히 clear되지 않아 GP가 hang합니다. 다중 counter와 mask는 tree 전체에서 일관된 초기 snapshot을 보장합니다.

이는 동기화를 피하려고 작업을 미루는 설계입니다. CPU-hotplug 사건을 즉시 모든 단계에 반영하지 않고 다음 GP 시작에 lazy하게 기록해 `rcu_node` CPU-tracking bitmask 관리를 단순화합니다.

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 has changed since the beginning of the last RCU expedited grace
   period, which triggers an update of each ``rcu_node`` structure's
   ``->expmaskinit`` field from its ``->expmaskinitnext`` field.
#. Each ``rcu_node`` structure's ``->expmaskinit`` field is used to
   initialize that structure's ``->expmask`` at the beginning of each
   RCU expedited grace period. This means that only those CPUs that have
   been online at least once will be considered for a given grace
   period.
#. Any CPU that goes offline will clear its bit in its leaf ``rcu_node``
   structure's ``->qsmaskinitnext`` field, so any CPU with that bit
   clear can safely be ignored. However, it is possible for a CPU coming
   online or going offline to have this bit set for some time while
   ``cpu_online`` returns ``false``.
#. For each non-idle CPU that RCU believes is currently online, the
   grace period invokes ``smp_call_function_single()``. If this
   succeeds, the CPU was fully online. Failure indicates that the CPU is
   in the process of coming online or going offline, in which case it is
   necessary to wait for a short time period and try again. The purpose
   of this wait (or series of waits, as the case may be) is to permit a
   concurrent CPU-hotplug operation to complete.
#. In the case of RCU-sched, one of the last acts of an outgoing CPU is
   to invoke ``rcutree_report_cpu_dead()``, which reports a quiescent state for
   that CPU. However, this is likely paranoia-induced redundancy.

+-----------------------------------------------------------------------+
| **Quick Quiz**:                                                       |
+-----------------------------------------------------------------------+
| Why all the dancing around with multiple counters and masks tracking  |
| CPUs that were once online? Why not just have a single set of masks   |
| tracking the currently online CPUs and be done with it?               |
+-----------------------------------------------------------------------+
| **Answer**:                                                           |
+-----------------------------------------------------------------------+
| Maintaining single set of masks tracking the online CPUs *sounds*     |
| easier, at least until you try working out all the race conditions    |
| between grace-period initialization and CPU-hotplug operations. For   |
| example, suppose initialization is progressing down the tree while a  |
| CPU-offline operation is progressing up the tree. This situation can  |
| result in bits set at the top of the tree that have no counterparts   |
| at the bottom of the tree. Those bits will never be cleared, which    |
| will result in grace-period hangs. In short, that way lies madness,   |
| to say nothing of a great many bugs, hangs, and deadlocks.            |
| In contrast, the current multi-mask multi-counter scheme ensures that |
| grace-period initialization will always see consistent masks up and   |
| down the tree, which brings significant simplifications over the      |
| single-mask method.                                                   |
|                                                                       |
| This is an instance of `deferring work in order to avoid              |
| synchronization <http://www.cs.columbia.edu/~library/TR-repository/re |
| ports/reports-1992/cucs-039-92.ps.gz>`__.                             |
| Lazily recording CPU-hotplug events at the beginning of the next      |
| grace period greatly simplifies maintenance of the CPU-tracking       |
| bitmasks in the ``rcu_node`` tree.                                    |
+-----------------------------------------------------------------------+

세 단계 idle CPU 검사

각 expedited GP는 `sync_rcu_exp_select_cpus()`에서 IPI 대상 mask를 처음 만들 때와 각 CPU에 IPI를 보내기 직전에 idle 여부를 검사합니다. 두 시점 사이 언제라도 CPU가 idle이었다면 IPI하지 않고, GP를 진행하는 task가 그 CPU를 `rcu_report_exp_cpu_mult()`에 넘길 mask에 넣어 보고합니다.

RCU-sched에서는 IPI가 idle loop를 interrupt했다면 `rcu_exp_handler()`가 `rcu_report_exp_rdp()`를 호출합니다. RCU-preempt handler는 별도 idle 검사를 하지 않지만 idle loop에서는 RCU read section이 허용되지 않습니다. 따라서 handler가 read section을 발견하면 확실히 non-idle이고, 아니면 idle 여부와 상관없이 `rcu_report_exp_rdp()`로 QS를 보고할 수 있습니다.

Expedited Grace Period Refinements
----------------------------------

Idle-CPU Checks
~~~~~~~~~~~~~~~

Each expedited grace period checks for idle CPUs when initially forming
the mask of CPUs to be IPIed and again just before IPIing a CPU (both
checks are carried out by ``sync_rcu_exp_select_cpus()``). If the CPU is
idle at any time between those two times, the CPU will not be IPIed.
Instead, the task pushing the grace period forward will include the idle
CPUs in the mask passed to ``rcu_report_exp_cpu_mult()``.

For RCU-sched, there is an additional check: If the IPI has interrupted
the idle loop, then ``rcu_exp_handler()`` invokes
``rcu_report_exp_rdp()`` to report the corresponding quiescent state.

For RCU-preempt, there is no specific check for idle in the IPI handler
(``rcu_exp_handler()``), but because RCU read-side critical sections are
not permitted within the idle loop, if ``rcu_exp_handler()`` sees that
the CPU is within RCU read-side critical section, the CPU cannot
possibly be idle. Otherwise, ``rcu_exp_handler()`` invokes
``rcu_report_exp_rdp()`` to report the corresponding quiescent state,
regardless of whether or not that quiescent state was due to the CPU
being idle.

In summary, RCU expedited grace periods check for idle when building the
bitmask of CPUs that must be IPIed, just before sending each IPI, and
(either explicitly or implicitly) within the IPI handler.

Sequence counter를 통한 request batching

모든 요청이 별도 expedited GP를 실행하면 확장성과 고부하 동작이 매우 나빠집니다. GP 하나는 update 수에 제한 없이 적용될 수 있으므로 동시 요청을 batch해 한 번의 GP가 batch 전체를 처리해야 합니다.

`rcu_state.expedited_sequence`는 진행 중이면 홀수, 아니면 짝수입니다. 값을 2로 나누면 완료된 GP 수가 됩니다. 어떤 update 요청도 관찰한 counter가 짝수→홀수→짝수로 한 번 전이하는 것을 기다려야 합니다. 최초 값이 `s`라면 최소 `(s+3)&~0x1`에 도달해야 완전한 GP 하나가 지난 것입니다.

한 batch에서는 요청 하나만 실제 GP를 시작하면 됩니다. 어떤 요청이 initiator가 될지 효율적으로 고르고 나머지를 효율적으로 재우는 역할은 다음 funnel locking이 담당합니다.

Batching via Sequence Counter
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

If each grace-period request was carried out separately, expedited grace
periods would have abysmal scalability and problematic high-load
characteristics. Because each grace-period operation can serve an
unlimited number of updates, it is important to *batch* requests, so
that a single expedited grace-period operation will cover all requests
in the corresponding batch.

This batching is controlled by a sequence counter named
``->expedited_sequence`` in the ``rcu_state`` structure. This counter
has an odd value when there is an expedited grace period in progress and
an even value otherwise, so that dividing the counter value by two gives
the number of completed grace periods. During any given update request,
the counter must transition from even to odd and then back to even, thus
indicating that a grace period has elapsed. Therefore, if the initial
value of the counter is ``s``, the updater must wait until the counter
reaches at least the value ``(s+3)&~0x1``. This counter is managed by
the following access functions:

#. ``rcu_exp_gp_seq_start()``, which marks the start of an expedited
   grace period.
#. ``rcu_exp_gp_seq_end()``, which marks the end of an expedited grace
   period.
#. ``rcu_exp_gp_seq_snap()``, which obtains a snapshot of the counter.
#. ``rcu_exp_gp_seq_done()``, which returns ``true`` if a full expedited
   grace period has elapsed since the corresponding call to
   ``rcu_exp_gp_seq_snap()``.

Again, only one request in a given batch need actually carry out a
grace-period operation, which means there must be an efficient way to
identify which of many concurrent requests will initiate the grace
period, and that there be an efficient way for the remaining requests to
wait for that grace period to complete. However, that is the topic of
the next section.

Funnel lock과 네 waitqueue의 순환

`exp_funnel_lock()`은 `rcu_node` 결합 트리로 동시 updater 중 GP를 시작할 하나를 선별합니다. 특정 GP 목표 sequence를 들고 node에 처음 도착한 updater는 `exp_seq_rq`에 값을 기록하고 부모로 올라갑니다. 이미 같거나 더 늦은 목표가 기록돼 있으면 `exp_wq[4]` 중 하나에서 block합니다. Index는 sequence의 아래에서 두 번째와 세 번째 bit를 사용하며 `exp_lock`이 이 field들을 보호합니다.

현재 `expedited_sequence`가 0일 때 Task A와 B가 좌우 leaf에 오면 목표는 `(0+3)&~1 = 2`입니다. 둘은 각 leaf `exp_seq_rq`에 2를 쓰고 root로 올라갑니다.

Root에서는 A가 먼저 2를 기록했다고 가정합니다. A는 새 GP 시작으로 진행하고, 뒤따른 B는 이미 같은 목표가 있음을 보고 root `exp_wq[1]`에서 block합니다. 목표 sequence 2를 그대로 index 2로 쓰지 않는 이유는 bit 0이 GP 진행 상태이므로 오른쪽으로 한 bit shift해 GP 번호 1을 얻기 때문입니다.

Task C와 D가 이때 도착하면 각 leaf에도 이미 2가 기록돼 있으므로 leaf의 `exp_wq[1]`에서 block합니다.

A가 `rcu_state.exp_mutex`를 획득해 GP를 시작하면 `expedited_sequence`가 1이 됩니다. 이때 E와 F가 도착하면 목표는 `(1+3)&~1 = 4`이며 각 leaf에 4를 기록하고 위로 진행합니다.

E와 F가 root로 올라오면 F는 root에서 block하고 E는 A가 끝나 `exp_mutex`를 넘겨줄 때까지 기다려 다음 GP를 시작할 준비를 합니다.

GP가 끝나면 A는 현재 GP waiter를 깨우기 시작하고 `expedited_sequence`를 2로 증가시킵니다. 이어 `exp_wake_mutex`를 획득한 뒤 `exp_mutex`를 놓습니다.

E는 `exp_mutex`를 얻어 다음 GP를 시작하고 sequence를 3으로 만듭니다. 동시에 G와 H가 새 목표를 들고 올라오면 root의 여러 세대 waitqueue가 동시에 점유될 수 있습니다.

A가 결국 target 2의 `exp_wq` waiter를 모두 깨우면 해당 queue가 비고, 이후 E와 H가 각 GP와 wakeup을 이어갑니다.

A의 wakeup이 너무 늦어 E의 GP가 먼저 끝나면 E는 `exp_wake_mutex`에서 block합니다. 그러면 `exp_mutex`도 놓지 못해 다음 GP가 시작되지 않습니다. 이 제한이 아직 wakeup되지 않은 세대가 네 개를 넘어 `exp_wq[]` index를 덮어쓰는 overflow를 막습니다.

Funnel Locking and Wait/Wakeup
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

The natural way to sort out which of a batch of updaters will initiate
the expedited grace period is to use the ``rcu_node`` combining tree, as
implemented by the ``exp_funnel_lock()`` function. The first updater
corresponding to a given grace period arriving at a given ``rcu_node``
structure records its desired grace-period sequence number in the
``->exp_seq_rq`` field and moves up to the next level in the tree.
Otherwise, if the ``->exp_seq_rq`` field already contains the sequence
number for the desired grace period or some later one, the updater
blocks on one of four wait queues in the ``->exp_wq[]`` array, using the
second-from-bottom and third-from bottom bits as an index. An
``->exp_lock`` field in the ``rcu_node`` structure synchronizes access
to these fields.

An empty ``rcu_node`` tree is shown in the following diagram, with the
white cells representing the ``->exp_seq_rq`` field and the red cells
representing the elements of the ``->exp_wq[]`` array.

.. kernel-figure:: Funnel0.svg

The next diagram shows the situation after the arrival of Task A and
Task B at the leftmost and rightmost leaf ``rcu_node`` structures,
respectively. The current value of the ``rcu_state`` structure's
``->expedited_sequence`` field is zero, so adding three and clearing the
bottom bit results in the value two, which both tasks record in the
``->exp_seq_rq`` field of their respective ``rcu_node`` structures:

.. kernel-figure:: Funnel1.svg

Each of Tasks A and B will move up to the root ``rcu_node`` structure.
Suppose that Task A wins, recording its desired grace-period sequence
number and resulting in the state shown below:

.. kernel-figure:: Funnel2.svg

Task A now advances to initiate a new grace period, while Task B moves
up to the root ``rcu_node`` structure, and, seeing that its desired
sequence number is already recorded, blocks on ``->exp_wq[1]``.

+-----------------------------------------------------------------------+
| **Quick Quiz**:                                                       |
+-----------------------------------------------------------------------+
| Why ``->exp_wq[1]``? Given that the value of these tasks' desired     |
| sequence number is two, so shouldn't they instead block on            |
| ``->exp_wq[2]``?                                                      |
+-----------------------------------------------------------------------+
| **Answer**:                                                           |
+-----------------------------------------------------------------------+
| No.                                                                   |
| Recall that the bottom bit of the desired sequence number indicates   |
| whether or not a grace period is currently in progress. It is         |
| therefore necessary to shift the sequence number right one bit        |
| position to obtain the number of the grace period. This results in    |
| ``->exp_wq[1]``.                                                      |
+-----------------------------------------------------------------------+

If Tasks C and D also arrive at this point, they will compute the same
desired grace-period sequence number, and see that both leaf
``rcu_node`` structures already have that value recorded. They will
therefore block on their respective ``rcu_node`` structures'
``->exp_wq[1]`` fields, as shown below:

.. kernel-figure:: Funnel3.svg

Task A now acquires the ``rcu_state`` structure's ``->exp_mutex`` and
initiates the grace period, which increments ``->expedited_sequence``.
Therefore, if Tasks E and F arrive, they will compute a desired sequence
number of 4 and will record this value as shown below:

.. kernel-figure:: Funnel4.svg

Tasks E and F will propagate up the ``rcu_node`` combining tree, with
Task F blocking on the root ``rcu_node`` structure and Task E wait for
Task A to finish so that it can start the next grace period. The
resulting state is as shown below:

.. kernel-figure:: Funnel5.svg

Once the grace period completes, Task A starts waking up the tasks
waiting for this grace period to complete, increments the
``->expedited_sequence``, acquires the ``->exp_wake_mutex`` and then
releases the ``->exp_mutex``. This results in the following state:

.. kernel-figure:: Funnel6.svg

Task E can then acquire ``->exp_mutex`` and increment
``->expedited_sequence`` to the value three. If new tasks G and H arrive
and moves up the combining tree at the same time, the state will be as
follows:

.. kernel-figure:: Funnel7.svg

Note that three of the root ``rcu_node`` structure's waitqueues are now
occupied. However, at some point, Task A will wake up the tasks blocked
on the ``->exp_wq`` waitqueues, resulting in the following state:

.. kernel-figure:: Funnel8.svg

Execution will continue with Tasks E and H completing their grace
periods and carrying out their wakeups.

+-----------------------------------------------------------------------+
| **Quick Quiz**:                                                       |
+-----------------------------------------------------------------------+
| What happens if Task A takes so long to do its wakeups that Task E's  |
| grace period completes?                                               |
+-----------------------------------------------------------------------+
| **Answer**:                                                           |
+-----------------------------------------------------------------------+
| Then Task E will block on the ``->exp_wake_mutex``, which will also   |
| prevent it from releasing ``->exp_mutex``, which in turn will prevent |
| the next grace period from starting. This last is important in        |
| preventing overflow of the ``->exp_wq[]`` array.                      |
+-----------------------------------------------------------------------+

Workqueue가 실제 GP를 구동하는 이유

예전에는 expedited GP를 요청한 user task가 완료까지 직접 구동해 POSIX signal을 처리해야 했습니다. 지금은 Linux workqueue를 사용합니다. 요청 task는 counter snapshot과 funnel-lock 처리를 계속하지만 funnel 최상단에 도달한 task는 `_synchronize_rcu_expedited()`에서 `schedule_work()`를 호출하고 workqueue kthread가 실제 GP를 수행합니다.

Workqueue kthread는 POSIX signal을 받지 않아 GP wait code가 signal을 고려할 필요가 없습니다. 또한 이전 GP의 wakeup과 다음 GP의 처리를 겹칠 수 있습니다.

Waitqueue set은 네 개뿐이므로 이전 GP wakeup이 다음 GP wakeup 전에 끝나야 합니다. `exp_mutex`는 GP 처리를, `exp_wake_mutex`는 wakeup을 보호합니다. 첫 wakeup이 완료돼 `exp_wake_mutex`를 확보하기 전에는 `exp_mutex`를 놓지 않습니다. 따라서 이전 wakeup과 현재 GP는 겹치지만 그 wakeup은 다음 GP 시작 전에는 끝나며, 실제로 필요한 queue가 최대 세 개라 제공된 네 개면 충분합니다.

Use of Workqueues
~~~~~~~~~~~~~~~~~

In earlier implementations, the task requesting the expedited grace
period also drove it to completion. This straightforward approach had
the disadvantage of needing to account for POSIX signals sent to user
tasks, so more recent implementations use the Linux kernel's
workqueues (see Documentation/core-api/workqueue.rst).

The requesting task still does counter snapshotting and funnel-lock
processing, but the task reaching the top of the funnel lock does a
``schedule_work()`` (from ``_synchronize_rcu_expedited()`` so that a
workqueue kthread does the actual grace-period processing. Because
workqueue kthreads do not accept POSIX signals, grace-period-wait
processing need not allow for POSIX signals. In addition, this approach
allows wakeups for the previous expedited grace period to be overlapped
with processing for the next expedited grace period. Because there are
only four sets of waitqueues, it is necessary to ensure that the
previous grace period's wakeups complete before the next grace period's
wakeups start. This is handled by having the ``->exp_mutex`` guard
expedited grace-period processing and the ``->exp_wake_mutex`` guard
wakeups. The key point is that the ``->exp_mutex`` is not released until
the first wakeup is complete, which means that the ``->exp_wake_mutex``
has already been acquired at that point. This approach ensures that the
previous grace period's wakeups can be carried out while the current
grace period is in process, but that these wakeups will complete before
the next grace period starts. This means that only three waitqueues are
required, guaranteeing that the four that are provided are sufficient.

Reader stall 경고

Expedited GP도 너무 오래 실행되는 RCU reader 자체를 빠르게 만들 수는 없으므로 normal GP와 별도로 stall을 검사합니다. 같은 reader가 둘 다 막더라도 특정 시점에 normal GP가 진행 중이지 않을 수 있어 normal machinery만으로는 경고를 낼 수 없습니다.

`synchronize_sched_expedited_wait()`는 현재 RCU CPU stall-warning 시간만큼 timeout을 두고 GP 종료를 반복해서 기다립니다. Timeout을 넘으면 현재 GP를 막는 CPU 또는 `rcu_node`를 출력합니다. 경고 뒤 loop를 다시 돌며 두 번째 이후 pass는 더 긴 stall 시간을 사용합니다.

Stall Warnings
~~~~~~~~~~~~~~

Expediting grace periods does nothing to speed things up when RCU
readers take too long, and therefore expedited grace periods check for
stalls just as normal grace periods do.

+-----------------------------------------------------------------------+
| **Quick Quiz**:                                                       |
+-----------------------------------------------------------------------+
| But why not just let the normal grace-period machinery detect the     |
| stalls, given that a given reader must block both normal and          |
| expedited grace periods?                                              |
+-----------------------------------------------------------------------+
| **Answer**:                                                           |
+-----------------------------------------------------------------------+
| Because it is quite possible that at a given time there is no normal  |
| grace period in progress, in which case the normal grace period       |
| cannot emit a stall warning.                                          |
+-----------------------------------------------------------------------+

The ``synchronize_sched_expedited_wait()`` function loops waiting for
the expedited grace period to end, but with a timeout set to the current
RCU CPU stall-warning time. If this time is exceeded, any CPUs or
``rcu_node`` structures blocking the current grace period are printed.
Each stall warning results in another pass through the loop, but the
second and subsequent passes use longer stall times.

Workqueue 이전 mid-boot 처리

Workqueue를 쓰면 POSIX signal 문제는 사라지지만 scheduler가 첫 task를 만든 뒤 한동안은 workqueue가 초기화되지 않습니다. 이 mid-boot dead zone에도 grace period가 필요한 kernel code가 있어 대체 경로가 필요합니다.

이 구간에는 요청 task가 직접 expedited GP를 구동하는 옛 방식을 사용합니다. Mid-boot 이전의 synchronous GP는 no-op이고, dead zone이 끝난 뒤에는 workqueue를 사용합니다.

Non-expedited non-SRCU synchronous GP도 mid-boot에는 정상 동작해야 하므로 이 시기에는 expedited code path로 보냅니다. 현재 code는 dead zone에 POSIX signal이 없다고 가정합니다. 정말 signal이 필요해지면 workqueue 이전의 stall-warning 검사를 이 구간에만 되살리는 식으로 조정할 수 있습니다.

이 보완으로 task context의 synchronous GP는 suspend, hibernate 또는 shutdown path의 일부 지점을 제외하면 kernel 생애 거의 언제든 사용할 수 있습니다.

Mid-boot operation
~~~~~~~~~~~~~~~~~~

The use of workqueues has the advantage that the expedited grace-period
code need not worry about POSIX signals. Unfortunately, it has the
corresponding disadvantage that workqueues cannot be used until they are
initialized, which does not happen until some time after the scheduler
spawns the first task. Given that there are parts of the kernel that
really do want to execute grace periods during this mid-boot “dead
zone”, expedited grace periods must do something else during this time.

What they do is to fall back to the old practice of requiring that the
requesting task drive the expedited grace period, as was the case before
the use of workqueues. However, the requesting task is only required to
drive the grace period during the mid-boot dead zone. Before mid-boot, a
synchronous grace period is a no-op. Some time after mid-boot,
workqueues are used.

Non-expedited non-SRCU synchronous grace periods must also operate
normally during mid-boot. This is handled by causing non-expedited grace
periods to take the expedited code path during mid-boot.

The current code assumes that there are no POSIX signals during the
mid-boot dead zone. However, if an overwhelming need for POSIX signals
somehow arises, appropriate adjustments can be made to the expedited
stall-warning code. One such adjustment would reinstate the
pre-workqueue stall-warning checks, but only during the mid-boot dead
zone.

With this refinement, synchronous grace periods can now be used from
task context pretty much any time during the life of the kernel. That
is, aside from some points in the suspend, hibernate, or shutdown code
path.

요약과 사용 지침

Expedited GP는 sequence number로 요청을 batch하고 funnel lock으로 동시 group에서 실제 GP를 요청할 task 하나를 효율적으로 고릅니다. 나머지는 `rcu_node`의 waitqueue에서 block하고 실제 처리는 workqueue가 수행합니다.

CPU-hotplug 사건은 expedited GP와 hotplug 사이의 촘촘한 동기화를 피하도록 lazy하게 기록합니다. Dyntick-idle counter로 common case의 idle CPU IPI를 피합니다. RCU-preempt와 RCU-sched는 서로 다른 IPI handler와 후속 반응 code를 쓰지만 나머지는 공통 code를 공유합니다.

`rcu_node` 트리가 quiescent state를 추적해 모두 보고되면 해당 expedited GP waiter를 깨웁니다. Mutex 두 개로 이전 GP wakeup과 다음 GP 처리를 병렬화하면서 wakeup 세대 순서를 지킵니다.

이 조합으로 expedited GP도 합리적인 효율을 얻지만, 시간이 중요하지 않은 task는 normal GP를 사용해야 합니다. 더 긴 실행 시간이 훨씬 큰 batch를 허용해 요청당 overhead가 훨씬 낮기 때문입니다.

Summary
~~~~~~~

Expedited grace periods use a sequence-number approach to promote
batching, so that a single grace-period operation can serve numerous
requests. A funnel lock is used to efficiently identify the one task out
of a concurrent group that will request the grace period. All members of
the group will block on waitqueues provided in the ``rcu_node``
structure. The actual grace-period processing is carried out by a
workqueue.

CPU-hotplug operations are noted lazily in order to prevent the need for
tight synchronization between expedited grace periods and CPU-hotplug
operations. The dyntick-idle counters are used to avoid sending IPIs to
idle CPUs, at least in the common case. RCU-preempt and RCU-sched use
different IPI handlers and different code to respond to the state
changes carried out by those handlers, but otherwise use common code.

Quiescent states are tracked using the ``rcu_node`` tree, and once all
necessary quiescent states have been reported, all tasks waiting on this
expedited grace period are awakened. A pair of mutexes are used to allow
one grace period's wakeups to proceed concurrently with the next grace
period's processing.

This combination of mechanisms allows expedited grace periods to run
reasonably efficiently. However, for non-time-critical tasks, normal
grace periods should be used instead because their longer duration
permits much higher degrees of batching, and thus much lower per-request
overheads.