TREE_RCU grace period의 memory ordering

Grace period가 보장하는 양방향 ordering

이 글은 2017년 8월 8일 Paul E. McKenney가 기고한 TREE_RCU grace-period memory-ordering 보장의 시각적 개요입니다.

Idle이나 offline이 아닌 code에 대해 RCU GP는 매우 강한 ordering을 제공합니다. 어떤 GP가 시작되기 전에 수행된 RCU read-side critical section의 모든 access 효과는 그 GP가 끝난 뒤 실행되는 code에서 보입니다. 반대로 GP 시작 전 code는 GP 종료 뒤의 read-side critical section access 효과를 미리 볼 수 없습니다.

RCU-sched read-side critical section에는 preemption이 disable된 모든 code가 포함됩니다. 기계어 instruction 하나도 아주 짧은 preemption-disabled 영역으로 볼 수 있으므로 `synchronize_rcu()`는 흔히 `smp_mb()`의 매우 강력한 확장처럼 생각할 수 있습니다.

Updater는 update를 GP 전의 phase one과 GP 뒤의 phase two로 나눠 이 보장을 사용합니다. 흔한 경우 phase one에서 RCU-protected linked structure의 원소를 제거하고 phase two에서 free합니다. 제거 전 상태를 본 reader가 free 이후 상태까지 관찰하면 안 됩니다.

RCU 구현은 `rcu_node` lock critical section, memory barrier와 per-CPU 처리를 network로 연결해 이 ordering을 만듭니다.

======================================================
A Tour Through TREE_RCU's Grace-Period Memory Ordering
======================================================

August 8, 2017

This article was contributed by Paul E. McKenney

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

This document gives a rough visual overview of how Tree RCU's
grace-period memory ordering guarantee is provided.

What Is Tree RCU's Grace Period Memory Ordering Guarantee?
==========================================================

RCU grace periods provide extremely strong memory-ordering guarantees
for non-idle non-offline code.
Any code that happens after the end of a given RCU grace period is guaranteed
to see the effects of all accesses prior to the beginning of that grace
period that are within RCU read-side critical sections.
Similarly, any code that happens before the beginning of a given RCU grace
period is guaranteed to not see the effects of all accesses following the end
of that grace period that are within RCU read-side critical sections.

Note well that RCU-sched read-side critical sections include any region
of code for which preemption is disabled.
Given that each individual machine instruction can be thought of as
an extremely small region of preemption-disabled code, one can think of
``synchronize_rcu()`` as ``smp_mb()`` on steroids.

RCU updaters use this guarantee by splitting their updates into
two phases, one of which is executed before the grace period and
the other of which is executed after the grace period.
In the most common use case, phase one removes an element from
a linked RCU-protected data structure, and phase two frees that element.
For this to work, any readers that have witnessed state prior to the
phase-one update (in the common case, removal) must not witness state
following the phase-two update (in the common case, freeing).

The RCU implementation provides this guarantee using a network
of lock-based critical sections, memory barriers, and per-CPU
processing, as is described in the following sections.

rcu_node lock과 unlock-lock full ordering

핵심 일꾼은 `rcu_node->lock` critical section입니다. 획득 helper는 `raw_spin_lock_rcu_node()`, `raw_spin_lock_irq_rcu_node()`, `raw_spin_lock_irqsave_rcu_node()`이며 대응 unlock helper와 `raw_spin_trylock_rcu_node()`도 있습니다. 모든 성공한 획득은 직후 `smp_mb__after_unlock_lock()`을 호출합니다.

같은 `rcu_node`에서 이전 unlock 전 access는 모든 CPU에게 이후 lock 뒤 access보다 먼저 보입니다. 더 나아가 같은 CPU에서 이전 unlock과 이후 lock이 서로 다른 `rcu_node`를 다뤄도 unlock 전 access가 lock 뒤 access보다 먼저 보입니다. TREE_RCU는 이를 이어 GP에 관여한 모든 CPU, GP 중 online/offline된 CPU까지 포함하는 ordering network를 만듭니다.

Litmus test에서 task0은 lock 아래 `x=1` 뒤 `y`를 읽고, task1은 같은 lock 아래 `y=1` 뒤 `z`를 읽으며, task2는 `z=1`, `smp_mb()`, `x` read를 수행합니다. 모든 변화가 전파된 뒤 `r1==0 && r2==0 && r3==0`은 허용되지 않습니다. 획득 helper의 `smp_mb__after_unlock_lock()`이 없으면 PowerPC 등에서 이 결과가 가능할 수 있습니다.

Lock chain만으로 new reader와 updater phase를 정렬할 수 있어 보여도 polling GP primitive 때문에 explicit barrier가 필요합니다. CPU0이 `X=1`, `get_state_synchronize_rcu()`, `poll_state_synchronize_rcu()` 완료 뒤 Y를 읽고 CPU1이 `Y=1`, `smp_mb()`, X를 읽는 경우 `r0==0 && r1==0`은 금지됩니다. CPU1이 전체 GP 동안 extended quiescent state여서 RCU core와 직접 상호작용하지 않아도 이 보장이 성립해야 합니다.

Tree RCU Grace Period Memory Ordering Building Blocks
=====================================================

The workhorse for RCU's grace-period memory ordering is the
critical section for the ``rcu_node`` structure's
``->lock``. These critical sections use helper functions for lock
acquisition, including ``raw_spin_lock_rcu_node()``,
``raw_spin_lock_irq_rcu_node()``, and ``raw_spin_lock_irqsave_rcu_node()``.
Their lock-release counterparts are ``raw_spin_unlock_rcu_node()``,
``raw_spin_unlock_irq_rcu_node()``, and
``raw_spin_unlock_irqrestore_rcu_node()``, respectively.
For completeness, a ``raw_spin_trylock_rcu_node()`` is also provided.
The key point is that the lock-acquisition functions, including
``raw_spin_trylock_rcu_node()``, all invoke ``smp_mb__after_unlock_lock()``
immediately after successful acquisition of the lock.

Therefore, for any given ``rcu_node`` structure, any access
happening before one of the above lock-release functions will be seen
by all CPUs as happening before any access happening after a later
one of the above lock-acquisition functions.
Furthermore, any access happening before one of the
above lock-release function on any given CPU will be seen by all
CPUs as happening before any access happening after a later one
of the above lock-acquisition functions executing on that same CPU,
even if the lock-release and lock-acquisition functions are operating
on different ``rcu_node`` structures.
Tree RCU uses these two ordering guarantees to form an ordering
network among all CPUs that were in any way involved in the grace
period, including any CPUs that came online or went offline during
the grace period in question.

The following litmus test exhibits the ordering effects of these
lock-acquisition and lock-release functions::

    1 int x, y, z;
    2
    3 void task0(void)
    4 {
    5   raw_spin_lock_rcu_node(rnp);
    6   WRITE_ONCE(x, 1);
    7   r1 = READ_ONCE(y);
    8   raw_spin_unlock_rcu_node(rnp);
    9 }
   10
   11 void task1(void)
   12 {
   13   raw_spin_lock_rcu_node(rnp);
   14   WRITE_ONCE(y, 1);
   15   r2 = READ_ONCE(z);
   16   raw_spin_unlock_rcu_node(rnp);
   17 }
   18
   19 void task2(void)
   20 {
   21   WRITE_ONCE(z, 1);
   22   smp_mb();
   23   r3 = READ_ONCE(x);
   24 }
   25
   26 WARN_ON(r1 == 0 && r2 == 0 && r3 == 0);

The ``WARN_ON()`` is evaluated at "the end of time",
after all changes have propagated throughout the system.
Without the ``smp_mb__after_unlock_lock()`` provided by the
acquisition functions, this ``WARN_ON()`` could trigger, for example
on PowerPC.
The ``smp_mb__after_unlock_lock()`` invocations prevent this
``WARN_ON()`` from triggering.

+-----------------------------------------------------------------------+
| **Quick Quiz**:                                                       |
+-----------------------------------------------------------------------+
| But the chain of rcu_node-structure lock acquisitions guarantees      |
| that new readers will see all of the updater's pre-grace-period       |
| accesses and also guarantees that the updater's post-grace-period     |
| accesses will see all of the old reader's accesses.  So why do we     |
| need all of those calls to smp_mb__after_unlock_lock()?               |
+-----------------------------------------------------------------------+
| **Answer**:                                                           |
+-----------------------------------------------------------------------+
| Because we must provide ordering for RCU's polling grace-period       |
| primitives, for example, get_state_synchronize_rcu() and              |
| poll_state_synchronize_rcu().  Consider this code::                   |
|                                                                       |
|  CPU 0                                     CPU 1                      |
|  ----                                      ----                       |
|  WRITE_ONCE(X, 1)                          WRITE_ONCE(Y, 1)           |
|  g = get_state_synchronize_rcu()           smp_mb()                   |
|  while (!poll_state_synchronize_rcu(g))    r1 = READ_ONCE(X)          |
|          continue;                                                    |
|  r0 = READ_ONCE(Y)                                                    |
|                                                                       |
| RCU guarantees that the outcome r0 == 0 && r1 == 0 will not           |
| happen, even if CPU 1 is in an RCU extended quiescent state           |
| (idle or offline) and thus won't interact directly with the RCU       |
| core processing at all.                                               |
+-----------------------------------------------------------------------+

Idle·offline CPU와 synchronize_rcu waiter 연결

Idle CPU의 현재 idle sojourn 앞뒤에 있는 RCU read section에도 GP ordering이 이어져야 합니다. Idle 진입의 `ct_kernel_exit_state()`와 idle 종료의 `ct_kernel_enter_state()`가 strongly ordered value-returning atomic `atomic_add_return()`을 사용합니다. GP kthread는 full memory barrier 뒤 `ct_rcu_watching_cpu_acquire()`와 acquire semantics의 `rcu_watching_snap_stopped_since()`로 idle CPU를 감지합니다.

GP 전체 동안 offline인 CPU는 시작 때부터 QS 대상이 아닙니다. GP 시작과 CPU hotplug의 race는 해당 CPU leaf `rcu_node->lock`이 중재합니다.

마지막 예외는 `synchronize_rcu()`에서 block된 task를 깨우는 경우입니다. Task affinity CPU가 아직 GP 종료를 인식하지 못했다면 ordering network가 그 CPU까지 도달하지 않았을 수 있습니다. 그래서 `synchronize_rcu()` 경로의 `wait_for_completion()` 반환 뒤에는 `smp_mb()`가 필요합니다. 이 문서를 작성하면서 발견되어 v4.14 무렵 mainline 반영이 예상됐고 Lance Roy, Will Deacon, Peter Zijlstra, Jonathan Cameron의 질문이 발견에 기여했습니다.

This approach must be extended to include idle CPUs, which need
RCU's grace-period memory ordering guarantee to extend to any
RCU read-side critical sections preceding and following the current
idle sojourn.
This case is handled by calls to the strongly ordered
``atomic_add_return()`` read-modify-write atomic operation that
is invoked within ``ct_kernel_exit_state()`` at idle-entry
time and within ``ct_kernel_enter_state()`` at idle-exit time.
The grace-period kthread invokes first ``ct_rcu_watching_cpu_acquire()``
(preceded by a full memory barrier) and ``rcu_watching_snap_stopped_since()``
(both of which rely on acquire semantics) to detect idle CPUs.

+-----------------------------------------------------------------------+
| **Quick Quiz**:                                                       |
+-----------------------------------------------------------------------+
| But what about CPUs that remain offline for the entire grace period?  |
+-----------------------------------------------------------------------+
| **Answer**:                                                           |
+-----------------------------------------------------------------------+
| Such CPUs will be offline at the beginning of the grace period, so    |
| the grace period won't expect quiescent states from them. Races       |
| between grace-period start and CPU-hotplug operations are mediated    |
| by the CPU's leaf ``rcu_node`` structure's ``->lock`` as described    |
| above.                                                                |
+-----------------------------------------------------------------------+

The approach must be extended to handle one final case, that of waking a
task blocked in ``synchronize_rcu()``. This task might be affined to
a CPU that is not yet aware that the grace period has ended, and thus
might not yet be subject to the grace period's memory ordering.
Therefore, there is an ``smp_mb()`` after the return from
``wait_for_completion()`` in the ``synchronize_rcu()`` code path.

+-----------------------------------------------------------------------+
| **Quick Quiz**:                                                       |
+-----------------------------------------------------------------------+
| What? Where??? I don't see any ``smp_mb()`` after the return from     |
| ``wait_for_completion()``!!!                                          |
+-----------------------------------------------------------------------+
| **Answer**:                                                           |
+-----------------------------------------------------------------------+
| That would be because I spotted the need for that ``smp_mb()`` during |
| the creation of this documentation, and it is therefore unlikely to   |
| hit mainline before v4.14. Kudos to Lance Roy, Will Deacon, Peter     |
| Zijlstra, and Jonathan Cameron for asking questions that sensitized   |
| me to the rather elaborate sequence of events that demonstrate the    |
| need for this memory barrier.                                         |
+-----------------------------------------------------------------------+

Lock critical-section 도식과 전체 구성 요소

TREE_RCU ordering은 `rcu_node->lock`에 크게 의존하므로 뒤 그림에서는 이 pattern을 축약합니다. `rcu_prepare_for_idle()`도 새 callback과 미래 GP를 정렬하는 함수 중 하나입니다. 이 설명에서 중요한 부분은 pending callback이 있으면 leaf node lock을 획득하고 `rcu_accelerate_cbs()`를 실행한 뒤 unlock하는 lines 32~34입니다.

도식의 box는 `rcu_node->lock` critical section이고 위쪽 이중선은 추가 `smp_mb__after_unlock_lock()`을 뜻합니다. 원문 code는 nohz 활성화 snapshot, callback 존재 여부, jiffy당 한 번의 acceleration과 필요 시 `rcu_gp_kthread_wake()`까지 그대로 보여 줍니다.

Tree RCU's grace--period memory-ordering guarantees rely most heavily on
the ``rcu_node`` structure's ``->lock`` field, so much so that it is
necessary to abbreviate this pattern in the diagrams in the next
section. For example, consider the ``rcu_prepare_for_idle()`` function
shown below, which is one of several functions that enforce ordering of
newly arrived RCU callbacks against future grace periods:

::

    1 static void rcu_prepare_for_idle(void)
    2 {
    3   bool needwake;
    4   struct rcu_data *rdp = this_cpu_ptr(&rcu_data);
    5   struct rcu_node *rnp;
    6   int tne;
    7
    8   lockdep_assert_irqs_disabled();
    9   if (rcu_rdp_is_offloaded(rdp))
   10     return;
   11
   12   /* Handle nohz enablement switches conservatively. */
   13   tne = READ_ONCE(tick_nohz_active);
   14   if (tne != rdp->tick_nohz_enabled_snap) {
   15     if (!rcu_segcblist_empty(&rdp->cblist))
   16       invoke_rcu_core(); /* force nohz to see update. */
   17     rdp->tick_nohz_enabled_snap = tne;
   18     return;
   19        }
   20   if (!tne)
   21     return;
   22
   23   /*
   24    * If we have not yet accelerated this jiffy, accelerate all
   25    * callbacks on this CPU.
   26   */
   27   if (rdp->last_accelerate == jiffies)
   28     return;
   29   rdp->last_accelerate = jiffies;
   30   if (rcu_segcblist_pend_cbs(&rdp->cblist)) {
   31     rnp = rdp->mynode;
   32     raw_spin_lock_rcu_node(rnp); /* irqs already disabled. */
   33     needwake = rcu_accelerate_cbs(rnp, rdp);
   34     raw_spin_unlock_rcu_node(rnp); /* irqs remain disabled. */
   35     if (needwake)
   36       rcu_gp_kthread_wake();
   37   }
   38 }

But the only part of ``rcu_prepare_for_idle()`` that really matters for
this discussion are lines 32–34. We will therefore abbreviate this
function as follows:

.. kernel-figure:: rcu_node-lock.svg

The box represents the ``rcu_node`` structure's ``->lock`` critical
section, with the double line on top representing the additional
``smp_mb__after_unlock_lock()``.

Tree RCU Grace Period Memory Ordering Components
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Tree RCU's grace-period memory-ordering guarantee is provided by a
number of RCU components:

#. `Callback Registry`_
#. `Grace-Period Initialization`_
#. `Self-Reported Quiescent States`_
#. `Dynamic Tick Interface`_
#. `CPU-Hotplug Interface`_
#. `Forcing Quiescent States`_
#. `Grace-Period Cleanup`_
#. `Callback Invocation`_

Each of the following section looks at the corresponding component in
detail.

Callback 등록을 미래 GP에 연결

`call_rcu()` 이전의 모든 access, 특히 update phase one은 callback이 기다릴 GP보다 먼저 일어나야 합니다. 하지만 `call_rcu()` 자체는 보통 CPU-local state만 다뤄 ordering을 제공하지 않고 `rcu_head`를 per-CPU list에 넣을 뿐입니다. 나중의 `rcu_accelerate_cbs()`가 callback을 미래 GP 번호와 연결합니다.

왼쪽 경로는 queued `rcu_head`가 폭증했을 때 `call_rcu()`가 직접 또는 보통 `RCU_SOFTIRQ`의 `note_gp_changes()`를 통해 acceleration을 호출합니다. `CONFIG_RCU_FAST_NO_HZ=y`의 중간 경로는 `rcu_prepare_for_idle()`을 사용합니다. `CONFIG_HOTPLUG_CPU=y`의 오른쪽 경로는 완전히 offline된 CPU의 callback을 surviving CPU에서 `takedown_cpu()`→`rcutree_migrate_callbacks()`→`rcu_migrate_callbacks`→`rcu_advance_cbs()`를 거쳐 처리합니다.

GP processing의 다른 경로도 기회가 되면 acceleration을 수행합니다. 어느 경로든 최근 callback을 CPU leaf `rcu_node->lock` 아래 미래 GP 번호와 연결하므로, 같은 node의 이전 critical section 및 현재 task/CPU가 다른 node에서 수행한 이전 critical section과 full ordering됩니다. 다음 GP 초기화 경로가 이 ordering을 GP 실제 시작까지 잇습니다.

`synchronize_rcu()`도 예외가 아닙니다. `call_rcu()`를 `wait_rcu_gp()`에 넘기고 그 함수가 호출하므로 결국 같은 callback registry 경로를 사용합니다.

Callback Registry
^^^^^^^^^^^^^^^^^

If RCU's grace-period guarantee is to mean anything at all, any access
that happens before a given invocation of ``call_rcu()`` must also
happen before the corresponding grace period. The implementation of this
portion of RCU's grace period guarantee is shown in the following
figure:

.. kernel-figure:: TreeRCU-callback-registry.svg

Because ``call_rcu()`` normally acts only on CPU-local state, it
provides no ordering guarantees, either for itself or for phase one of
the update (which again will usually be removal of an element from an
RCU-protected data structure). It simply enqueues the ``rcu_head``
structure on a per-CPU list, which cannot become associated with a grace
period until a later call to ``rcu_accelerate_cbs()``, as shown in the
diagram above.

One set of code paths shown on the left invokes ``rcu_accelerate_cbs()``
via ``note_gp_changes()``, either directly from ``call_rcu()`` (if the
current CPU is inundated with queued ``rcu_head`` structures) or more
likely from an ``RCU_SOFTIRQ`` handler. Another code path in the middle
is taken only in kernels built with ``CONFIG_RCU_FAST_NO_HZ=y``, which
invokes ``rcu_accelerate_cbs()`` via ``rcu_prepare_for_idle()``. The
final code path on the right is taken only in kernels built with
``CONFIG_HOTPLUG_CPU=y``, which invokes ``rcu_accelerate_cbs()`` via
``rcu_advance_cbs()``, ``rcu_migrate_callbacks``,
``rcutree_migrate_callbacks()``, and ``takedown_cpu()``, which in turn
is invoked on a surviving CPU after the outgoing CPU has been completely
offlined.

There are a few other code paths within grace-period processing that
opportunistically invoke ``rcu_accelerate_cbs()``. However, either way,
all of the CPU's recently queued ``rcu_head`` structures are associated
with a future grace-period number under the protection of the CPU's lead
``rcu_node`` structure's ``->lock``. In all cases, there is full
ordering against any prior critical section for that same ``rcu_node``
structure's ``->lock``, and also full ordering against any of the
current task's or CPU's prior critical sections for any ``rcu_node``
structure's ``->lock``.

The next section will show how this ordering ensures that any accesses
prior to the ``call_rcu()`` (particularly including phase one of the
update) happen before the start of the corresponding grace period.

+-----------------------------------------------------------------------+
| **Quick Quiz**:                                                       |
+-----------------------------------------------------------------------+
| But what about ``synchronize_rcu()``?                                 |
+-----------------------------------------------------------------------+
| **Answer**:                                                           |
+-----------------------------------------------------------------------+
| The ``synchronize_rcu()`` passes ``call_rcu()`` to ``wait_rcu_gp()``, |
| which invokes it. So either way, it eventually comes down to          |
| ``call_rcu()``.                                                       |
+-----------------------------------------------------------------------+

GP 초기화의 세 tree pass

GP kthread는 `rcu_gp_init()`에서 `rcu_node` tree를 여러 번 순회합니다. 같은 node의 상태가 시간에 따라 변하므로 전체 ordering 흐름은 tree를 여러 그림에 반복해 나타냅니다.

첫 ordering 동작은 `rcu_state.gp_seq`를 advance하는 것입니다. 실제 increment는 `smp_store_release()`로 수행해 false-positive RCU CPU stall 판정을 줄이며, 이 단계에서는 root `rcu_node`만 만집니다.

첫 tree pass는 이전 GP 시작 뒤 online/offline된 CPU에 맞춰 bitmask를 갱신합니다. Node의 online CPU 수가 0과 비0 사이를 오가지 않은 common case에는 leaf만 scan합니다. Leaf가 0에서 비0으로 바뀌면 첫 incoming CPU에 대해 `rcu_init_new_rnp()`, 비0에서 0이 되면 마지막 outgoing CPU에 대해 `rcu_cleanup_dead_rnp()`를 호출해 parent 방향 상태를 조정합니다.

마지막 pass는 breadth-first로 모든 `rcu_node.gp_seq`를 새 `rcu_state` 값으로 설정합니다. 이후 각 CPU의 `__note_gp_changes()`가 새 GP 시작을 발견합니다. Root에서 전역 `gp_seq`를 먼저 advance하고 leaf local copy를 나중에 바꾸므로 CPU의 관찰은 실제 GP 시작 뒤에 일어납니다.

GP를 시작한 CPU도 RCU가 자기 인식을 한다고 보지 않는 한 즉시 안다고 할 수 없습니다. 자기 leaf에 대한 마지막 `rcu_gp_init()` pass에서 `__note_gp_changes()`를 호출할 수 있어 다른 CPU보다 빨리 알 가능성은 있지만, local observation은 여전히 그 호출 시점입니다.

Grace-Period Initialization
^^^^^^^^^^^^^^^^^^^^^^^^^^^

Grace-period initialization is carried out by the grace-period kernel
thread, which makes several passes over the ``rcu_node`` tree within the
``rcu_gp_init()`` function. This means that showing the full flow of
ordering through the grace-period computation will require duplicating
this tree. If you find this confusing, please note that the state of the
``rcu_node`` changes over time, just like Heraclitus's river. However,
to keep the ``rcu_node`` river tractable, the grace-period kernel
thread's traversals are presented in multiple parts, starting in this
section with the various phases of grace-period initialization.

The first ordering-related grace-period initialization action is to
advance the ``rcu_state`` structure's ``->gp_seq`` grace-period-number
counter, as shown below:

.. kernel-figure:: TreeRCU-gp-init-1.svg

The actual increment is carried out using ``smp_store_release()``, which
helps reject false-positive RCU CPU stall detection. Note that only the
root ``rcu_node`` structure is touched.

The first pass through the ``rcu_node`` tree updates bitmasks based on
CPUs having come online or gone offline since the start of the previous
grace period. In the common case where the number of online CPUs for
this ``rcu_node`` structure has not transitioned to or from zero, this
pass will scan only the leaf ``rcu_node`` structures. However, if the
number of online CPUs for a given leaf ``rcu_node`` structure has
transitioned from zero, ``rcu_init_new_rnp()`` will be invoked for the
first incoming CPU. Similarly, if the number of online CPUs for a given
leaf ``rcu_node`` structure has transitioned to zero,
``rcu_cleanup_dead_rnp()`` will be invoked for the last outgoing CPU.
The diagram below shows the path of ordering if the leftmost
``rcu_node`` structure onlines its first CPU and if the next
``rcu_node`` structure has no online CPUs (or, alternatively if the
leftmost ``rcu_node`` structure offlines its last CPU and if the next
``rcu_node`` structure has no online CPUs).

.. kernel-figure:: TreeRCU-gp-init-2.svg

The final ``rcu_gp_init()`` pass through the ``rcu_node`` tree traverses
breadth-first, setting each ``rcu_node`` structure's ``->gp_seq`` field
to the newly advanced value from the ``rcu_state`` structure, as shown
in the following diagram.

.. kernel-figure:: TreeRCU-gp-init-3.svg

This change will also cause each CPU's next call to
``__note_gp_changes()`` to notice that a new grace period has started,
as described in the next section. But because the grace-period kthread
started the grace period at the root (with the advancing of the
``rcu_state`` structure's ``->gp_seq`` field) before setting each leaf
``rcu_node`` structure's ``->gp_seq`` field, each CPU's observation of
the start of the grace period will happen after the actual start of the
grace period.

+-----------------------------------------------------------------------+
| **Quick Quiz**:                                                       |
+-----------------------------------------------------------------------+
| But what about the CPU that started the grace period? Why wouldn't it |
| see the start of the grace period right when it started that grace    |
| period?                                                               |
+-----------------------------------------------------------------------+
| **Answer**:                                                           |
+-----------------------------------------------------------------------+
| In some deep philosophical and overly anthromorphized sense, yes, the |
| CPU starting the grace period is immediately aware of having done so. |
| However, if we instead assume that RCU is not self-aware, then even   |
| the CPU starting the grace period does not really become aware of the |
| start of this grace period until its first call to                    |
| ``__note_gp_changes()``. On the other hand, this CPU potentially gets |
| early notification because it invokes ``__note_gp_changes()`` during  |
| its last ``rcu_gp_init()`` pass through its leaf ``rcu_node``         |
| structure.                                                            |
+-----------------------------------------------------------------------+

Online CPU의 self-reported quiescent state

GP를 막을 수 있는 모든 entity가 직접 QS를 보고하거나 뒤 절처럼 대리 보고되면 GP가 끝납니다. 그림은 마지막 CPU가 QS를 보고해 GP 종료를 신호하는 경로입니다. 앞선 보고는 아직 다른 자식을 기다리는 node에서 멈추지만, 나중 보고가 그 node lock을 다시 획득하므로 ordering은 보존됩니다.

CPU는 `note_gp_changes()` 또는 `__note_gp_changes()`를 leaf lock 아래 호출해 새 GP 시작을 인식합니다. 그 호출 전에 시작된 RCU read section은 GP보다 먼저 시작한 것으로 간주해 기다립니다. 실제 전역 GP 시작 뒤에 시작됐을 수도 있어 논리적으로 기다릴 필요는 없지만, 더 확장성 있는 lazy start를 위해 기다리는 것은 허용되며 중요합니다.

Context switch에서는 `rcu_note_context_switch()`, user mode의 scheduler-clock interrupt에서는 `rcu_sched_clock_irq()`가 QS를 per-CPU 변수에 기록합니다. 다음 `RCU_SOFTIRQ`에서 `rcu_core()`→`rcu_check_quiescent_state()`가 기록을 발견하고 `rcu_report_qs_rdp()`를 호출합니다.

`rcu_report_qs_rdp()`가 QS가 현재 GP에 적용됨을 확인하면 `rcu_report_rnp()`가 tree 위로 올라가 각 `qsmask` bit를 지웁니다. 현재 CPU가 해당 subtree의 마지막 reporter일 때만 node를 넘어 parent로 진행합니다. 어떤 보고가 node에서 멈추면 나중의 다른 보고가 그 node에서 위로 진행하고 node lock이 첫 보고를 뒤 traversal보다 먼저 정렬합니다. 이를 반복하면 모든 CPU의 QS가 root의 마지막 bit를 지우는 CPU보다 먼저 일어납니다.

Self-Reported Quiescent States
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

When all entities that might block the grace period have reported
quiescent states (or as described in a later section, had quiescent
states reported on their behalf), the grace period can end. Online
non-idle CPUs report their own quiescent states, as shown in the
following diagram:

.. kernel-figure:: TreeRCU-qs.svg

This is for the last CPU to report a quiescent state, which signals the
end of the grace period. Earlier quiescent states would push up the
``rcu_node`` tree only until they encountered an ``rcu_node`` structure
that is waiting for additional quiescent states. However, ordering is
nevertheless preserved because some later quiescent state will acquire
that ``rcu_node`` structure's ``->lock``.

Any number of events can lead up to a CPU invoking ``note_gp_changes``
(or alternatively, directly invoking ``__note_gp_changes()``), at which
point that CPU will notice the start of a new grace period while holding
its leaf ``rcu_node`` lock. Therefore, all execution shown in this
diagram happens after the start of the grace period. In addition, this
CPU will consider any RCU read-side critical section that started before
the invocation of ``__note_gp_changes()`` to have started before the
grace period, and thus a critical section that the grace period must
wait on.

+-----------------------------------------------------------------------+
| **Quick Quiz**:                                                       |
+-----------------------------------------------------------------------+
| But a RCU read-side critical section might have started after the     |
| beginning of the grace period (the advancing of ``->gp_seq`` from     |
| earlier), so why should the grace period wait on such a critical      |
| section?                                                              |
+-----------------------------------------------------------------------+
| **Answer**:                                                           |
+-----------------------------------------------------------------------+
| It is indeed not necessary for the grace period to wait on such a     |
| critical section. However, it is permissible to wait on it. And it is |
| furthermore important to wait on it, as this lazy approach is far     |
| more scalable than a “big bang” all-at-once grace-period start could  |
| possibly be.                                                          |
+-----------------------------------------------------------------------+

If the CPU does a context switch, a quiescent state will be noted by
``rcu_note_context_switch()`` on the left. On the other hand, if the CPU
takes a scheduler-clock interrupt while executing in usermode, a
quiescent state will be noted by ``rcu_sched_clock_irq()`` on the right.
Either way, the passage through a quiescent state will be noted in a
per-CPU variable.

The next time an ``RCU_SOFTIRQ`` handler executes on this CPU (for
example, after the next scheduler-clock interrupt), ``rcu_core()`` will
invoke ``rcu_check_quiescent_state()``, which will notice the recorded
quiescent state, and invoke ``rcu_report_qs_rdp()``. If
``rcu_report_qs_rdp()`` verifies that the quiescent state really does
apply to the current grace period, it invokes ``rcu_report_rnp()`` which
traverses up the ``rcu_node`` tree as shown at the bottom of the
diagram, clearing bits from each ``rcu_node`` structure's ``->qsmask``
field, and propagating up the tree when the result is zero.

Note that traversal passes upwards out of a given ``rcu_node`` structure
only if the current CPU is reporting the last quiescent state for the
subtree headed by that ``rcu_node`` structure. A key point is that if a
CPU's traversal stops at a given ``rcu_node`` structure, then there will
be a later traversal by another CPU (or perhaps the same one) that
proceeds upwards from that point, and the ``rcu_node`` ``->lock``
guarantees that the first CPU's quiescent state happens before the
remainder of the second CPU's traversal. Applying this line of thought
repeatedly shows that all CPUs' quiescent states happen before the last
CPU traverses through the root ``rcu_node`` structure, the “last CPU”
being the one that clears the last bit in the root ``rcu_node``
structure's ``->qsmask`` field.

Dynamic tick idle 경계의 ordering

에너지 효율 때문에 RCU는 idle CPU를 방해할 수 없습니다. CPU는 per-CPU 변수에 fully ordered value-returning atomic operation을 수행해 idle 진입과 종료를 RCU에 알립니다.

GP kthread는 대상 CPU leaf `rcu_node->lock`을 잡은 채 idleness 변수를 sample합니다. 따라서 idle period보다 앞선 RCU read section은 현재 GP 종료보다 먼저 일어나고, 현재 GP 시작은 idle 뒤의 RCU read section보다 먼저 일어납니다. 이 상태가 full GP에 연결되는 과정은 forced QS 절에서 설명합니다.

Dynamic Tick Interface
^^^^^^^^^^^^^^^^^^^^^^

Due to energy-efficiency considerations, RCU is forbidden from
disturbing idle CPUs. CPUs are therefore required to notify RCU when
entering or leaving idle state, which they do via fully ordered
value-returning atomic operations on a per-CPU variable. The ordering
effects are as shown below:

.. kernel-figure:: TreeRCU-dyntick.svg

The RCU grace-period kernel thread samples the per-CPU idleness variable
while holding the corresponding CPU's leaf ``rcu_node`` structure's
``->lock``. This means that any RCU read-side critical sections that
precede the idle period (the oval near the top of the diagram above)
will happen before the end of the current grace period. Similarly, the
beginning of the current grace period will happen before any RCU
read-side critical sections that follow the idle period (the oval near
the bottom of the diagram above).

Plumbing this into the full grace-period execution is described
`below <Forcing Quiescent States_>`__.

CPU hotplug 경계의 ordering

Offline CPU는 전원이 꺼지고 제거될 수도 있으므로 RCU가 방해할 수 없습니다. CPU는 hotplug operation의 일부로 online과 offline을 RCU에 알립니다.

Hotplug은 idle 전환보다 훨씬 드물어 더 무거운 경로를 허용합니다. CPU leaf `rcu_node->lock`을 획득해 `qsmaskinitnext`를 갱신하고 GP kthread가 이 mask를 sample해 현재 GP 시작 뒤 offline된 CPU를 찾습니다. Full GP 연결은 forced QS 경로가 담당합니다.

CPU-Hotplug Interface
^^^^^^^^^^^^^^^^^^^^^

RCU is also forbidden from disturbing offline CPUs, which might well be
powered off and removed from the system completely. CPUs are therefore
required to notify RCU of their comings and goings as part of the
corresponding CPU hotplug operations. The ordering effects are shown
below:

.. kernel-figure:: TreeRCU-hotplug.svg

Because CPU hotplug operations are much less frequent than idle
transitions, they are heavier weight, and thus acquire the CPU's leaf
``rcu_node`` structure's ``->lock`` and update this structure's
``->qsmaskinitnext``. The RCU grace-period kernel thread samples this
mask to detect CPUs having gone offline since the beginning of this
grace period.

Plumbing this into the full grace-period execution is described
`below <Forcing Quiescent States_>`__.

Idle·offline CPU의 forced quiescent state

Idle과 offline CPU는 스스로 QS를 보고할 수 없어 GP kthread가 대신 보고합니다. 이 forced quiescent state 과정은 몇 jiffy마다 반복됩니다.

각 FQS pass는 반드시 모든 leaf `rcu_node`를 순회합니다. 최근 idle/offline CPU에서 새 QS가 없으면 leaf만 방문합니다. 새 offline CPU 또는 idle CPU가 있으면 그 QS를 root 방향으로 올리며 self-report와 마찬가지로 다른 CPU의 QS가 남은 node에서 멈춥니다.

원문의 단순화된 그림에서는 왼쪽 root drive가 root 전에 멈췄는데 오른쪽 drive가 GP를 끝내는 모순이 있습니다. 실제 RCU가 정상이라면 불가능하며, 전체를 이어 붙인 마지막 그림에서 정확한 관계가 드러납니다. 원문도 복잡도를 낮추기 위한 시적 허용이라고 명시합니다.

Forcing Quiescent States
^^^^^^^^^^^^^^^^^^^^^^^^

As noted above, idle and offline CPUs cannot report their own quiescent
states, and therefore the grace-period kernel thread must do the
reporting on their behalf. This process is called “forcing quiescent
states”, it is repeated every few jiffies, and its ordering effects are
shown below:

.. kernel-figure:: TreeRCU-gp-fqs.svg

Each pass of quiescent state forcing is guaranteed to traverse the leaf
``rcu_node`` structures, and if there are no new quiescent states due to
recently idled and/or offlined CPUs, then only the leaves are traversed.
However, if there is a newly offlined CPU as illustrated on the left or
a newly idled CPU as illustrated on the right, the corresponding
quiescent state will be driven up towards the root. As with
self-reported quiescent states, the upwards driving stops once it
reaches an ``rcu_node`` structure that has quiescent states outstanding
from other CPUs.

+-----------------------------------------------------------------------+
| **Quick Quiz**:                                                       |
+-----------------------------------------------------------------------+
| The leftmost drive to root stopped before it reached the root         |
| ``rcu_node`` structure, which means that there are still CPUs         |
| subordinate to that structure on which the current grace period is    |
| waiting. Given that, how is it possible that the rightmost drive to   |
| root ended the grace period?                                          |
+-----------------------------------------------------------------------+
| **Answer**:                                                           |
+-----------------------------------------------------------------------+
| Good analysis! It is in fact impossible in the absence of bugs in     |
| RCU. But this diagram is complex enough as it is, so simplicity       |
| overrode accuracy. You can think of it as poetic license, or you can  |
| think of it as misdirection that is resolved in the                   |
| `stitched-together diagram <Putting It All Together_>`__.             |
+-----------------------------------------------------------------------+

Grace-period cleanup과 종료 시점의 분산성

Cleanup은 먼저 `rcu_node` tree를 breadth-first로 scan해 모든 node의 `gp_seq`를 advance하고, 그 다음 `rcu_state.gp_seq`를 advance합니다. Cleanup이 끝나면 다음 GP를 시작할 수 있습니다.

GP가 끝나는 유용한 단일 순간은 없습니다. 가장 이른 후보는 마지막 CPU가 QS를 보고한 때지만 RCU가 이를 인식하기까지 millisecond가 걸릴 수 있습니다. 가장 늦은 후보는 `rcu_state.gp_seq` 갱신 때지만 일부 CPU는 이미 update phase two를 끝냈을 수 있습니다. RCU 종료는 분산된 interval로 이해해야 합니다.

Grace-Period Cleanup
^^^^^^^^^^^^^^^^^^^^

Grace-period cleanup first scans the ``rcu_node`` tree breadth-first
advancing all the ``->gp_seq`` fields, then it advances the
``rcu_state`` structure's ``->gp_seq`` field. The ordering effects are
shown below:

.. kernel-figure:: TreeRCU-gp-cleanup.svg

As indicated by the oval at the bottom of the diagram, once grace-period
cleanup is complete, the next grace period can begin.

+-----------------------------------------------------------------------+
| **Quick Quiz**:                                                       |
+-----------------------------------------------------------------------+
| But when precisely does the grace period end?                         |
+-----------------------------------------------------------------------+
| **Answer**:                                                           |
+-----------------------------------------------------------------------+
| There is no useful single point at which the grace period can be said |
| to end. The earliest reasonable candidate is as soon as the last CPU  |
| has reported its quiescent state, but it may be some milliseconds     |
| before RCU becomes aware of this. The latest reasonable candidate is  |
| once the ``rcu_state`` structure's ``->gp_seq`` field has been        |
| updated, but it is quite possible that some CPUs have already         |
| completed phase two of their updates by that time. In short, if you   |
| are going to work with RCU, you need to learn to embrace uncertainty. |
+-----------------------------------------------------------------------+

Callback 호출과 다른 CPU로의 ordering 전달

CPU leaf `rcu_node.gp_seq`가 갱신되면 그 CPU는 해당 GP를 기다리던 callback을 호출할 수 있습니다. 보통 `__note_gp_changes()`가 `rcu_advance_cbs()`를 호출해 대상을 찾습니다.

Scheduling-clock interrupt의 `rcu_sched_clock_irq()` 또는 `CONFIG_RCU_FAST_NO_HZ=y`에서 idle 진입의 `rcu_cleanup_after_idle()`이 이 과정을 촉발할 수 있습니다. 둘 다 `RCU_SOFTIRQ`를 올리고 `rcu_do_batch()`가 callback을 호출해 직접 또는 wakeup을 통해 update phase two를 실행합니다. Callback 과다 같은 corner case 경로도 촉발할 수 있습니다.

모든 경로에서 CPU는 callback 호출 가능 상태를 만들기 전에 leaf `rcu_node->lock`을 획득해 새로 완료된 GP와 ordering을 지킵니다. 그러나 callback이 wakeup 등으로 다른 CPU와 통신하면 callback 함수와 깨어난 task가 자체 ordering을 제공해야 합니다.

예를 들어 왼쪽 leaf CPU의 callback이 오른쪽 leaf CPU에서 실행될 task를 깨울 때 GP kthread가 아직 오른쪽 leaf cleanup에 도달하지 않았을 수 있습니다. 그 CPU에는 GP ordering이 아직 전파되지 않았으므로 wakeup 양쪽의 올바른 ordering이 필수입니다.

Callback Invocation
^^^^^^^^^^^^^^^^^^^

Once a given CPU's leaf ``rcu_node`` structure's ``->gp_seq`` field has
been updated, that CPU can begin invoking its RCU callbacks that were
waiting for this grace period to end. These callbacks are identified by
``rcu_advance_cbs()``, which is usually invoked by
``__note_gp_changes()``. As shown in the diagram below, this invocation
can be triggered by the scheduling-clock interrupt
(``rcu_sched_clock_irq()`` on the left) or by idle entry
(``rcu_cleanup_after_idle()`` on the right, but only for kernels build
with ``CONFIG_RCU_FAST_NO_HZ=y``). Either way, ``RCU_SOFTIRQ`` is
raised, which results in ``rcu_do_batch()`` invoking the callbacks,
which in turn allows those callbacks to carry out (either directly or
indirectly via wakeup) the needed phase-two processing for each update.

.. kernel-figure:: TreeRCU-callback-invocation.svg

Please note that callback invocation can also be prompted by any number
of corner-case code paths, for example, when a CPU notes that it has
excessive numbers of callbacks queued. In all cases, the CPU acquires
its leaf ``rcu_node`` structure's ``->lock`` before invoking callbacks,
which preserves the required ordering against the newly completed grace
period.

However, if the callback function communicates to other CPUs, for
example, doing a wakeup, then it is that function's responsibility to
maintain ordering. For example, if the callback function wakes up a task
that runs on some other CPU, proper ordering must in place in both the
callback function and the task being awakened. To see why this is
important, consider the top half of the `grace-period
cleanup`_ diagram. The callback might be
running on a CPU corresponding to the leftmost leaf ``rcu_node``
structure, and awaken a task that is to run on a CPU corresponding to
the rightmost leaf ``rcu_node`` structure, and the grace-period kernel
thread might not yet have reached the rightmost leaf. In this case, the
grace period's memory ordering might not yet have reached that CPU, so
again the callback function and the awakened task must supply proper
ordering.

전체 ordering network와 법적 고지

마지막 TreeRCU-gp.svg는 callback registry, 세 단계 GP initialization, self/forced QS, dynamic tick, hotplug, cleanup과 callback invocation 그림을 하나로 이어 전체 happens-before network를 보여 줍니다.

이 글은 저자의 견해이며 반드시 IBM의 견해를 나타내지는 않습니다. Linux는 Linus Torvalds의 등록 상표이고 다른 회사·제품·서비스 이름은 각 소유자의 상표 또는 서비스표일 수 있습니다.

Putting It All Together
~~~~~~~~~~~~~~~~~~~~~~~

A stitched-together diagram is here:

.. kernel-figure:: TreeRCU-gp.svg

Legal Statement
~~~~~~~~~~~~~~~

This work represents the view of the author and does not necessarily
represent the view of IBM.

Linux is a registered trademark of Linus Torvalds.

Other company, product, and service names may be trademarks or service
marks of others.