hellokitty2

翻譯：kernel-5.10\Documentation\RCU\Design\Data-Structures\Data-Structures.rst

================================================ =
TREE_RCU 數據結構導覽 [LWN.net]
================================================ =

2016 年 12 月 18 日

本文由 Paul E. McKenney 提供

介紹
============

本文檔描述了 RCU 的主要數據結構以及它們之間的關系。

數據結構關系
============================

RCU 出于所有意圖和目的是一個大型狀態機，其數據結構以允許 RCU 讀者極快地執行的方式維護狀態，同時還以高效且極具可擴展性的方式處理更新程序請求的 RCU 寬限期 .
RCU updaters 的效率和可擴展性主要由組合樹提供，如下所示：

.. 內核圖:: BigTreeClassicRCU.svg

此圖顯示了一個包含“rcu_node”結構樹的封閉“rcu_state”結構。 ``rcu_node`` 樹的每個葉節點最多有 16 個 ``rcu_data`` 結構與之關聯，因此有 ``NR_CPUS`` 數量的 ``rcu_data`` 結構，
每個可能的 CPU 一個。 如果需要，此結構會在啟動時進行調整，以處理 ``nr_cpu_ids`` 遠小于 ``NR_CPUs`` 的常見情況。 例如，許多 Linux 發行版設置了“NR_CPUs=4096”，這導致了一個
三級“rcu_node”樹。 如果實際硬件只有 16 個 CPU，RCU 會在啟動時自行調整，導致只有一個節點的 ``rcu_node`` 樹。

此組合樹的目的是允許高效且可擴展地處理每個 CPU 事件，例如靜態、dyntick-idle 轉換和 CPU 熱插拔操作。
靜態由每個 CPU 的“rcu_data”結構記錄，和其他事件由葉級 ``rcu_node`` 結構記錄。
所有這些事件都在樹的每一層進行組合，直到最后在樹的根“rcu_node”結構中完成寬限期。
一旦每個 CPU（或者，在 ``CONFIG_PREEMPT_RCU`` 的情況下，任務）已經通過靜止狀態，就可以在根節點完成寬限期。 一旦寬限期結束，該事實的記錄就會沿著樹向下傳播。

從圖中可以看出，在64位系統上，一棵64個葉子的兩級樹可以容納1024個CPU，根部的扇出為64，葉子的扇出為16。

| **小測驗**： |
+------------------------------------------------ ----------------------+
| 為什么葉子的扇出不是 64？ |
+------------------------------------------------ ----------------------+
| **回答**：
因為影響葉級 ``rcu_node`` 結構的事件類型多于樹的更上層。 因此，如果葉 ``rcu_node`` 結構的扇出為 64，則對這些結構的``->structures`` 的爭用變得過多。 在各種系統上進行的實驗表明，
16 的扇出適用于 ``rcu_node`` 樹的葉子。

當然，具有數百或數千個 CPU 的系統的進一步經驗可能會證明非葉 ``rcu_node`` 結構的扇出也必須減少。 當證明有必要時，可以很容易地進行這種減少。 同時，如果您正在使用這樣的系統并在非
葉``rcu_node``結構上遇到爭用問題，您可以使用``CONFIG_RCU_FANOUT``內核配置參數根據需要減少非葉扇出。

為具有強大 NUMA 特性的系統構建的內核可能還需要調整“CONFIG_RCU_FANOUT”，以便“rcu_node”結構的域與硬件邊界對齊。 然而，到目前為止還沒有這個必要。

如果您的系統有超過 1,024 個 CPU（或在 32 位系統上超過 512 個 CPU），那么 RCU 會自動向樹中添加更多層級。 例如，如果你足夠瘋狂地構建一個具有 65,536 個 CPU 的 64 位系統，RCU 將配置
``rcu_node`` 樹如下：

.. 內核圖:: HugeTreeClassicRCU.svg

RCU 目前允許最多四級樹，在 64 位系統上最多可容納 4,194,304 個 CPU，但在 32 位系統上只能容納 524,288 個 CPU。 另一方面，您可以將 ``CONFIG_RCU_FANOUT`` 和 ``CONFIG_RCU_FANOUT_LEAF``
設置為小至 2，這將導致使用 4 級樹的 16-CPU 測試。 這對于在小型測試機器上測試大型系統功能很有用。

這種多級組合樹使我們能夠獲得分區的大部分性能和可伸縮性優勢，即使 RCU 寬限期檢測本質上是一個全局操作。 這里的技巧是，只有最后一個 CPU 將靜止狀態報告給給定的 ``rcu_node`` 結構需要前
進到樹的下一層的 ``rcu_node`` 結構。 這意味著在葉級 ``rcu_node`` 結構中，16 個訪問中只有一個會在樹上進行。 對于內部的 ``rcu_node`` 結構，情況更加極端：64 次訪問中只有一次會在樹上進
行。 因為絕大多數 CPU 沒有在樹中向上移動，所以鎖爭用在樹中大致保持不變。 無論系統中有多少個 CPU，每個寬限期最多 64 個靜態報告將一直進行到根 ``rcu_node`` 結構，從而確保該根 ``rcu_node``
結構上的鎖爭用仍然處于可接受的低水平。

實際上，組合樹就像一個大減震器，無論系統負載水平如何，都可以在所有樹級別控制鎖爭用。

RCU updaters 通過注冊 RCU 回調來等待正常的寬限期，可以直接通過 ``call_rcu()`` 或間接通過 ``synchronize_rcu()`` 或其朋友函數。 RCU 回調由 ``rcu_head`` 結構表示，它們在等待寬限期結束時在
``rcu_data`` 結構上排隊，如下圖所示：

.. 內核圖:: BigTreePreemptRCUBHdyntickCB.svg

此圖顯示了 ``TREE_RCU`` 和 ``PREEMPT_RCU`` 的主要數據結構之間的關系。 較小的數據結構將與使用它們的算法一起引入。

注意上圖中的每個數據結構都有自己的同步：

#. 每個 ``rcu_state`` 結構都有一個鎖和一個互斥量，一些字段由相應的根 ``rcu_node`` 結構的鎖保護。
#. 每個 ``rcu_node`` 結構都有一個自旋鎖。
#. ``rcu_data`` 中的字段是相應 CPU 私有的，盡管有一些字段可以被其他 CPU 讀取和寫入。

重要的是要注意，不同的數據結構在任何給定時間對 RCU 的狀態可能有非常不同的想法。 舉一個例子，對給定 RCU 寬限期開始或結束的意識通過數據結構緩慢傳播。 這種緩慢的傳播對于 RCU 具有良好
的讀取端性能是絕對必要的。 如果您覺得這種割裂的實現方式很陌生，一個有用的技巧是將這些數據結構的每個實例都視為不同的人，每個人對現實的看法通常略有不同。

這些數據結構的一般作用如下：

#. ``rcu_state``：該結構形成``rcu_node``和``rcu_data``結構之間的互連，跟蹤寬限期，作為CPU熱插拔事件孤立的回調的短期存儲庫，維護``rcu_barrier()`` 狀態，跟蹤加速寬限期狀態，并在寬限
期延長太長時維護用于強制靜態狀態的狀態，

#. ``rcu_node``：這個結構形成了組合樹，它將靜止狀態信息從葉子傳播到根，并且還將寬限期信息從根傳播到葉子。它提供寬限期狀態的本地副本，以允許以同步方式訪問此信息，而不會受到全局鎖定強加的
可伸縮性限制。 在 ``CONFIG_PREEMPT_RCU`` 內核中，它管理在當前 RCU 讀端臨界區中阻塞的任務列表。 在 ``CONFIG_PREEMPT_RCU`` 和 ``CONFIG_RCU_BOOST`` 中，它管理每 ``rcu_node`` 的優先級提
升內核線程（kthreads）和狀態。 最后，它記錄 CPU 熱插拔狀態以確定在給定的寬限期內應忽略哪些 CPU。

#. ``rcu_data``：這個每 CPU 的結構是靜態檢測和 RCU 回調排隊的重點。 它還跟蹤它與相應的葉``rcu_node``結構的關系，以允許更有效地將靜態狀態傳播到``rcu_node``組合樹上。 與 rcu_node 結構
一樣，它提供了寬限期信息的本地副本，以允許從相應的 CPU 中訪問此信息，而不需要任何同步操作。 最后，該結構記錄了相應 CPU 過去的 dyntick-idle 狀態并跟蹤統計信息。

#. ``rcu_head``：這個結構代表RCU回調，并且是RCU用戶分配和管理的唯一結構。 ``rcu_head`` 結構通常嵌入在受 RCU 保護的數據結構中。

如果您希望從本文中了解 RCU 的數據結構如何相關的一般概念，那么您已經完成了。 否則，以下各節將提供有關 ``rcu_state``、``rcu_node`` 和 ``rcu_data`` 數據結構的更多詳細信息。

 

一、``rcu_state`` 結構

~~~~~~~~~~~~~~~~~~~~~~~~~~~

``rcu_state`` 結構是表示系統中 RCU 狀態的基本結構。 這個結構形成了 ``rcu_node`` 和 ``rcu_data`` 結構之間的互連，跟蹤寬限期，包含用于與 CPU 熱插拔事件同步的鎖，并維護用于在寬限期延長太
長時強制進入靜止狀態的狀態 ,

在以下部分中，將單獨或成組地討論一些 rcu_state 結構的字段。 更專業的領域涵蓋在它們的使用討論中。

1.1. 與 rcu_node 和 rcu_data 結構的關系
'''''''''''''''''''''''''''''''''''''''''''''''

``rcu_state`` 結構的這一部分聲明如下：

::
1 struct rcu_node node[NUM_RCU_NODES];
2 struct rcu_node *level[NUM_RCU_LVLS + 1];
3 struct rcu_data __percpu *rda;

 

| **小測驗**： |
+------------------------------------------------ ----------------------+
| 等一下！ 你說 ``rcu_node`` 結構形成了一棵樹，但它們被聲明為平面數組！ 是什么賦予了？
+------------------------------------------------ ----------------------+
| **回答**： |
+------------------------------------------------ ----------------------+
| 樹被布置在數組中。 數組中的第一個節點是頭，數組中的下一組節點是頭節點的子節點，依此類推，直到數組中的最后一組節點是葉子。 請參閱下圖以了解其工作原理。

``rcu_node`` 樹嵌入到``->node[]`` 數組中，如下圖所示：

.. 內核圖:: TreeMapping.svg

這種映射的一個有趣的結果是樹的廣度優先遍歷被實現為數組的簡單線性掃描，這實際上是 ``rcu_for_each_node_breadth_first()`` 宏所做的。 該宏在寬限期的開始和結束時使用。

``->level`` 數組的每個條目都引用樹的相應級別上的第一個 ``rcu_node`` 結構，例如，如下所示：

.. 內核圖:: TreeMappingLevel.svg

數組的第零個 :sup:`th` 元素引用根 ``rcu_node`` 結構，第一個元素引用根 ``rcu_node`` 的第一個子節點，最后第二個元素引用第一個葉子 `` rcu_node``結構。

不管怎樣，如果你把樹畫成樹形而不是數組形，就很容易畫出平面表示：

.. 內核圖:: TreeLevel.svg

最后，``->rda`` 字段引用一個指向相應 CPU 的``rcu_data`` 結構的每 CPU 指針。

一旦初始化完成，所有這些字段都是常量，因此不需要保護。

1.2. 寬限期跟蹤
''''''''''''''''''''

``rcu_state`` 結構的這一部分聲明如下：

::

1 unsigned long gp_seq;

RCU 寬限期是被編號的，``->gp_seq`` 字段包含當前寬限期序列號。 低兩位是當前寬限期的狀態，可以為 0 表示尚未開始，也可以為 1 表示進行中。換句話說，如果 ``->gp_seq`` 的低兩位為零，則 RCU 空閑。
底部兩位中的任何其他值都表示有東西壞了。 該字段受根 ``rcu_node`` 結構的 ``->lock`` 字段保護。

``rcu_node`` 和 ``rcu_data`` 結構中也有 ``->gp_seq`` 字段。 ``rcu_state`` 結構中的字段表示最新值，并且比較其他結構中的字段，以便以分布式方式檢測寬限期的開始和結束。
值從 ``rcu_state`` 流向 ``rcu_node``（從根到葉的樹）到 ``rcu_data``。

各種各樣的
'''''''''''''

``rcu_state`` 結構的這一部分聲明如下：

::
1 unsigned long gp_max;
2 char abbr;
3 char *name;

``->gp_max`` 字段以 jiffies 為單位跟蹤最長寬限期的持續時間。 它受根 ``rcu_node`` 的 ``->lock`` 保護。

``->name`` 和 ``->abbr`` 字段區分搶占式 RCU（“rcu_preempt”和“p”）和非搶占式 RCU（“rcu_sched”和“s”）。 這些字段用于診斷和跟蹤目的。

 

二、``rcu_node`` 結構

~~~~~~~~~~~~~~~~~~~~~~~~~~

``rcu_node`` 結構形成了組合樹，它將靜止狀態信息從葉子傳播到根，并將寬限期信息從根向下傳播到葉子。 它們提供寬限期狀態的本地副本，以允許以同步方式訪問此信息，而不
會受到全局鎖定強加的可伸縮性限制。 在 ``CONFIG_PREEMPT_RCU`` 內核中，它們管理在當前 RCU 讀端臨界區中阻塞的任務列表。在 ``CONFIG_PREEMPT_RCU`` 和 ``CONFIG_RCU_BOOST`` 中，
它們管理每個 ``rcu_node`` 優先級提升內核線程（kthreads）和狀態。 最后，他們記錄 CPU 熱插拔狀態以確定在給定的寬限期內應忽略哪些 CPU。

``rcu_node`` 結構的字段將在以下部分單獨和成組討論。

2.1. 連接到組合樹
''''''''''''''''''''''''''

``rcu_node`` 結構的這一部分聲明如下：

::
1 struct rcu_node *parent;
2 u8 level;
3 u8 grpnum;
4 unsigned long grpmask;
5 int grplo;
6 int grphi;

``->parent`` 指針引用樹中上一層的``rcu_node``，對于根``rcu_node`` 為``NULL``。 RCU 實現大量使用此字段將靜止狀態推到樹上。 ``->level`` 字段給出了樹中的級別，根為零級，
其子級為一級，依此類推。 ``->grpnum`` 字段給出了該節點在其父節點的子節點中的位置，因此該數字在 32 位系統上可以介于 0 到 31 之間，在 64 位系統上可以介于 0 到 63 之間。
``->level`` 和 ``->grpnum`` 字段僅在初始化和tracing期間使用。 ``->grpmask`` 字段是 ``->grpnum`` 的對應位掩碼，因此總是只有一位設置。此掩碼用于清除其父級位掩碼中與此
``rcu_node`` 結構對應的位，稍后將對此進行描述。 最后，``->grplo`` 和``->grphi`` 字段分別包含此 ``rcu_node`` 結構服務的編號最低和最高的 CPU。

所有這些字段都是常量，因此不需要任何同步。

2.2. 同步
'''''''''''''''

``rcu_node`` 結構的這個字段聲明如下：

::
1 raw_spinlock_t lock;

除非另有說明，否則此字段用于保護此結構中的其余字段。 也就是說，出于跟蹤目的，無需鎖定即可訪問此結構中的所有字段。 是的，這可能會導致混亂的trace，但一些混亂trace比被 heisenbugged
淘汰好。

.. _grace-period-tracking-1:

2.3. 寬限期跟蹤
''''''''''''''''''''

``rcu_node`` 結構的這一部分聲明如下：

::
1 unsigned long gp_seq;
2 unsigned long gp_seq_needed;

``rcu_node`` 結構的``->gp_seq`` 字段是``rcu_state`` 結構中同名字段的對應項。 他們每個人都可能落后于他們的 ``rcu_state`` 一步。 如果給定 ``rcu_node`` 結構的 ``->gp_seq`` 字
段的底部兩位為零，則此 ``rcu_node`` 結構認為 RCU 空閑。

每個“rcu_node”結構的“>gp_seq”字段在每個寬限期的開始和結束時更新。

``->gp_seq_needed`` 字段記錄相應 ``rcu_node`` 結構看到的最遠的未來寬限期請求。 當 ``->gp_seq`` 字段的值等于或超過 ``->gp_seq_needed`` 字段的值時，請求被認為已完成。

| **小測驗**： |
+------------------------------------------------ ----------------------+
| 假設這個 ``rcu_node`` 結構很長時間沒有看到請求。 ``->gp_seq`` 字段的 wrapping 不會導致問題嗎？ |
+------------------------------------------------ ----------------------+
| **回答**： |
+------------------------------------------------ ----------------------+
| 不會，因為如果 ``->gp_seq_needed`` 字段滯后于 ``->gp_seq`` 字段，``->gp_seq_needed`` 字段將在寬限期結束時更新。 因此，模算術比較總是會得到正確的答案，即使有回繞也是如此。 |

2.4. 靜態跟蹤
'''''''''''''''''''''''

這些字段管理靜態在組合樹上的傳播。

``rcu_node`` 結構的這一部分具有如下字段：

::
1 unsigned long qsmask;
2 unsigned long expmask;
3 unsigned long qsmaskinit;
4 unsigned long expmaskinit;

``->qsmask`` 字段跟蹤此 ``rcu_node`` 結構的哪些子結構仍需要報告當前正常寬限期的靜止狀態。 這樣的孩子在其相應位中的值為 1。 請注意，葉 ``rcu_node`` 結構應該被視為具有 ``rcu_data``
結構作為它們的子結構。 類似地，``->expmask`` 字段跟蹤此 ``rcu_node`` 結構的哪些子結構仍需要報告當前加速寬限期的靜止狀態。 加速寬限期與正常寬限期具有相同的概念屬性，但加速實施接受
極端的 CPU 開銷以獲得更低的寬限期延遲，例如，消耗幾十微秒的 CPU 時間來減少持續時間從幾毫秒到幾十微秒的寬限期。 ``->qsmaskinit`` 字段跟蹤這個 ``rcu_node`` 結構的哪個子結構覆蓋了至
少一個在線 CPU。 此掩碼用于初始化``->qsmask``，``->expmaskinit`` 用于初始化``->expmask`` 以及正常和加速寬限期的開始。

| **小測驗**： |
+------------------------------------------------ ----------------------+
| 為什么這些位掩碼受鎖保護？ 拜托，你沒聽說過原子指令嗎？？？ |
+------------------------------------------------ ----------------------+
| **回答**： |
+------------------------------------------------ ----------------------+
| 無鎖寬限期計算！ 如此誘人的可能性！ 但是請考慮以下事件序列：
|
| #. CPU 0 已經處于 dyntick-idle 模式很長一段時間了。 當它醒來時，它注意到當前的 RCU 寬限期需要它報告，所以它設置一個標志，調度時鐘中斷將找到它。
| #. 與此同時，CPU 1 正在運行“force_quiescent_state()”，并注意到 CPU 0 一直處于 dyntick 空閑模式，這符合擴展靜止狀態的條件。
| #. CPU 0 的調度時鐘中斷在 RCU 讀端臨界區的中間觸發，并注意到 RCU 核心需要一些東西，因此開始 RCU softirq 處理。
| #. CPU 0 的 softirq 處理程序執行并準備好向 ``rcu_node`` 樹報告其靜止狀態。
| #. 但是 CPU 1 先發制人，完成了當前的寬限期并開始了新的寬限期。
| #. CPU 0 現在報告錯誤寬限期的靜止狀態。 該寬限期現在可能會在 RCU 讀端臨界區之前結束。 如果發生這種情況，災難就會接踵而至。
|
| 所以鎖定是絕對需要的，以便協調位的清除與更新 ``->gp_seq`` 中的寬限期序列號。

2.5. 阻塞任務管理
''''''''''''''''''''''

``PREEMPT_RCU`` 允許任務在其 RCU 讀端臨界區中被搶占，并且必須顯式跟蹤這些任務。 跟蹤它們的確切原因和方式的詳細信息將在有關 RCU 讀取端處理的另一篇文章中介紹。 現在，知道 ``rcu_node``
結構跟蹤它們就足夠了。

::
1 struct list_head blkd_tasks;
2 struct list_head *gp_tasks;
3 struct list_head *exp_tasks;
4 bool wait_blkd_tasks;

``->blkd_tasks`` 字段是阻塞和搶占任務列表的列表頭。 當任務在 RCU 讀端臨界區內進行上下文切換時，它們的 ``task_struct`` 結構被排入隊列（通過 ``task_struct`` 的 ``->rcu_node_entry`` 字段）
到 ``-> blkd_tasks`` 中，它是葉``rcu_node``結構的列表，對應于執行傳出上下文切換的CPU。 當這些任務稍后退出它們的 RCU 讀端臨界區時，它們將自己從列表中移除。 因此這個列表是時間倒序的，所以如
果其中一個任務阻塞了當前的寬限期，那么所有后續任務也必須阻塞同一個寬限期。 因此，指向此列表的單個指針足以跟蹤所有阻塞給定寬限期的任務。 對于正常的寬限期，該指針存儲在 ``->gp_tasks`` 中，
對于加速的寬限期存儲在 ``->exp_tasks`` 中。 如果沒有進行中的寬限期或者沒有阻止寬限期完成的阻塞任務，最后兩個字段為“NULL”。 如果這兩個指針中的任何一個正在引用一個從``->blkd_tasks``列表中
刪除自身的任務，那么該任務必須將指針推進到列表中的下一個任務，或者將指針設置為``NULL``如果列表中沒有后續任務。

例如，假設任務 T1、T2 和 T3 都 hard-affinitied 到系統中編號最大的 CPU 上。 然后，如果任務 T1 阻塞在 RCU 讀端臨界區，然后加速寬限期開始，然后任務 T2 阻塞在 RCU 讀端臨界區，然后正常寬限期開
始，最后任務 3 阻塞在 RCU 讀端臨界區，那么最后一個葉子 ``rcu_node`` 結構的阻塞任務列表的狀態將如下所示：

.. 內核圖:: blkd_task.svg

任務 T1 阻塞了兩個寬限期，任務 T2 僅阻塞了正常寬限期，任務 T3 沒有阻塞任何寬限期。 請注意，這些任務不會在恢復執行后立即從該列表中刪除。 它們將保留在列表中，直到它們執行最外層的
``rcu_read_unlock()`` 結束它們的 RCU 讀端臨界區。

``->wait_blkd_tasks`` 字段指示當前寬限期是否正在等待阻塞的任務。

 

2.6. 調整 ``rcu_node`` 數組的大小
'''''''''''''''''''''''''''

``rcu_node`` 數組通過一系列 C 預處理器表達式確定大小，如下所示：

::

1 #ifdef CONFIG_RCU_FANOUT
2 #define RCU_FANOUT CONFIG_RCU_FANOUT
3 #else
4 # ifdef CONFIG_64BIT
5 # define RCU_FANOUT 64
6 # else
7 # define RCU_FANOUT 32
8 # endif
9 #endif
10
11 #ifdef CONFIG_RCU_FANOUT_LEAF
12 #define RCU_FANOUT_LEAF CONFIG_RCU_FANOUT_LEAF
13 #else
14 # ifdef CONFIG_64BIT
15 # define RCU_FANOUT_LEAF 64
16 # else
17 # define RCU_FANOUT_LEAF 32
18 # endif
19 #endif
20
21 #define RCU_FANOUT_1 (RCU_FANOUT_LEAF)
22 #define RCU_FANOUT_2 (RCU_FANOUT_1 * RCU_FANOUT)
23 #define RCU_FANOUT_3 (RCU_FANOUT_2 * RCU_FANOUT)
24 #define RCU_FANOUT_4 (RCU_FANOUT_3 * RCU_FANOUT)
25
26 #if NR_CPUS <= RCU_FANOUT_1
27 # define RCU_NUM_LVLS 1
28 # define NUM_RCU_LVL_0 1
29 # define NUM_RCU_NODES NUM_RCU_LVL_0
30 # define NUM_RCU_LVL_INIT { NUM_RCU_LVL_0 }
31 # define RCU_NODE_NAME_INIT { "rcu_node_0" }
32 # define RCU_FQS_NAME_INIT { "rcu_node_fqs_0" }
33 # define RCU_EXP_NAME_INIT { "rcu_node_exp_0" }
34 #elif NR_CPUS <= RCU_FANOUT_2
35 # define RCU_NUM_LVLS 2
36 # define NUM_RCU_LVL_0 1
37 # define NUM_RCU_LVL_1 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_1)
38 # define NUM_RCU_NODES (NUM_RCU_LVL_0 + NUM_RCU_LVL_1)
39 # define NUM_RCU_LVL_INIT { NUM_RCU_LVL_0, NUM_RCU_LVL_1 }
40 # define RCU_NODE_NAME_INIT { "rcu_node_0", "rcu_node_1" }
41 # define RCU_FQS_NAME_INIT { "rcu_node_fqs_0", "rcu_node_fqs_1" }
42 # define RCU_EXP_NAME_INIT { "rcu_node_exp_0", "rcu_node_exp_1" }
43 #elif NR_CPUS <= RCU_FANOUT_3
44 # define RCU_NUM_LVLS 3
45 # define NUM_RCU_LVL_0 1
46 # define NUM_RCU_LVL_1 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_2)
47 # define NUM_RCU_LVL_2 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_1)
48 # define NUM_RCU_NODES (NUM_RCU_LVL_0 + NUM_RCU_LVL_1 + NUM_RCU_LVL_2)
49 # define NUM_RCU_LVL_INIT { NUM_RCU_LVL_0, NUM_RCU_LVL_1, NUM_RCU_LVL_2 }
50 # define RCU_NODE_NAME_INIT { "rcu_node_0", "rcu_node_1", "rcu_node_2" }
51 # define RCU_FQS_NAME_INIT { "rcu_node_fqs_0", "rcu_node_fqs_1", "rcu_node_fqs_2" }
52 # define RCU_EXP_NAME_INIT { "rcu_node_exp_0", "rcu_node_exp_1", "rcu_node_exp_2" }
53 #elif NR_CPUS <= RCU_FANOUT_4
54 # define RCU_NUM_LVLS 4
55 # define NUM_RCU_LVL_0 1
56 # define NUM_RCU_LVL_1 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_3)
57 # define NUM_RCU_LVL_2 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_2)
58 # define NUM_RCU_LVL_3 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_1)
59 # define NUM_RCU_NODES (NUM_RCU_LVL_0 + NUM_RCU_LVL_1 + NUM_RCU_LVL_2 + NUM_RCU_LVL_3)
60 # define NUM_RCU_LVL_INIT { NUM_RCU_LVL_0, NUM_RCU_LVL_1, NUM_RCU_LVL_2, NUM_RCU_LVL_3 }
61 # define RCU_NODE_NAME_INIT { "rcu_node_0", "rcu_node_1", "rcu_node_2", "rcu_node_3" }
62 # define RCU_FQS_NAME_INIT { "rcu_node_fqs_0", "rcu_node_fqs_1", "rcu_node_fqs_2", "rcu_node_fqs_3" }
63 # define RCU_EXP_NAME_INIT { "rcu_node_exp_0", "rcu_node_exp_1", "rcu_node_exp_2", "rcu_node_exp_3" }
64 #else
65 # error "CONFIG_RCU_FANOUT insufficient for NR_CPUS"
66 #endif

``rcu_node`` 結構中的最大層數目前限制為四，如第 21-24 行和后續“if”語句的結構所指定。 對于 32 位系統，這允許 16*32*32*32=524,288 個 CPU，至少在未來幾年應該足夠了。 對于 64 位系統，
16*64*64*64=4,194,304 個 CPU 是允許的，這應該可以讓我們度過未來十年左右的時間。 這個四級樹還允許使用 ``CONFIG_RCU_FANOUT=8`` 構建的內核支持多達 4096 個 CPU，這在每個插槽有 8 個
CPU 的非常大的系統中可能很有用（但請注意，還沒有人顯示任何可測量的性能 由于未對齊的套接字和 ``rcu_node`` 邊界導致的降級）。 此外，使用完整的四級 ``rcu_node`` 樹構建內核可以更好地
測試 RCU 的組合樹代碼。

``RCU_FANOUT`` 符號控制在 ``rcu_node`` 樹的每個非葉級別上允許有多少孩子。 如果沒有指定 ``CONFIG_RCU_FANOUT`` Kconfig 選項，它是根據系統的字大小設置的，這也是 Kconfig 默認值。

``RCU_FANOUT_LEAF`` 符號控制每個葉``rcu_node`` 結構處理多少 CPU。 經驗表明，允許給定的葉子“rcu_node”結構處理 64 個 CPU，如 64 位系統上“->qsmask”字段中的位數所允許的那樣，會導致對
葉子的過度爭用 ``rcu_node`` 結構' `->lock`` 字段。 因此，給定 CONFIG_RCU_FANOUT_LEAF 的默認值，每個葉子 rcu_node 結構的 CPU 數量限制為 16。 如果未指定 ``CONFIG_RCU_FANOUT_LEAF``，
則選擇的值基于系統的字大小，就像 ``CONFIG_RCU_FANOUT`` 一樣。 第 11-19 行執行此計算。

第 21-24 行分別計算單級（包含單個 ``rcu_node`` 結構）、二級、三級和四級 ``rcu_node`` 樹支持的最大 CPU 數量， 給定 RCU_FANOUT 和 RCU_FANOUT_LEAF 指定的扇出。 這些 CPU 數量分別保留
在“RCU_FANOUT_1”、“RCU_FANOUT_2”、“RCU_FANOUT_3”和“RCU_FANOUT_4”C 預處理器變量中。

這些變量用于控制跨越 26-66 行的 C 預處理器“#if”語句，該語句計算樹的每個級別所需的“rcu_node”結構的數量，以及所需的級別數量。 層數由第 27、35、44 和 54 行放置在“NUM_RCU_LVLS”C 預處
理器變量中。樹的最頂層的“rcu_node”結構的數量始終正好是一個，并且 該值無條件地放入第 28、36、45 和 55 行的“NUM_RCU_LVL_0”中。“rcu_node”樹的其余級別（如果有）是通過將最大 CPU 數量
除以 從當前級別向下舍入的級別數支持的扇出。 此計算由第 37、46-47 和 56-58 行執行。 第 31-33、40-42、50-52 和 62-63 行為 lockdep 鎖類名稱創建初始值設定項。 最后，如果 CPU 的最大數
量對于指定的扇出太大，則第 64-66 行會產生錯誤。

 

三、``rcu_segcblist`` 結構

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

3.1. ``rcu_segcblist`` 結構維護一個分段的回調列表，如下所示：

::
1 #define RCU_DONE_TAIL 0
2 #define RCU_WAIT_TAIL 1
3 #define RCU_NEXT_READY_TAIL 2
4 #define RCU_NEXT_TAIL 3
5 #define RCU_CBLIST_NSEGS 4
6
7 struct rcu_segcblist {
8 struct rcu_head *head;
9 struct rcu_head **tails[RCU_CBLIST_NSEGS];
10 unsigned long gp_seq[RCU_CBLIST_NSEGS];
11 long len;
12 long len_lazy;
13 };

分段如下：

#. ``RCU_DONE_TAIL``：寬限期已過的回調。 這些回調已準備好被調用。
#. ``RCU_WAIT_TAIL``：正在等待當前寬限期的回調。 請注意，不同的 CPU 可能對哪個寬限期是當前有不同的想法，見 ``->gp_seq`` 字段。
#. ``RCU_NEXT_READY_TAIL``：等待下一個寬限期開始的回調。
#. ``RCU_NEXT_TAIL``：尚未與寬限期關聯的回調。

``->head`` 指針引用第一個回調，或者如果列表不包含回調（這*不* 等于空）則為 ``NULL``。 ``->tails[]`` 數組的每個元素引用列表相應段中最后一個回調的``->next`` 指針，或者如果該段是列
表的``->head`` 指針 并且之前的所有段都是空的。 如果相應的段為空但之前的某個段不為空，則數組元素與其前身相同。 較舊的回調更靠近列表的頭部，新的回調添加在尾部。 ``->head`` 指針、
``->tails[]`` 數組和回調之間的關系如下圖所示：

.. 內核圖:: nxtlist.svg

在此圖中，``->head`` 指針引用列表中的第一個 RCU 回調。 ``->tails[RCU_DONE_TAIL]`` 數組元素引用``->head`` 指針本身，表明沒有任何回調準備好調用。 ``->tails[RCU_WAIT_TAIL]`` 數組元素引用回
調 CB 2 的 ``->next`` 指針，這表明 CB 1 和 CB 2 都在等待當前寬限期，給出或接受可能的分歧 哪個寬限期是當前的寬限期。 ``->tails[RCU_NEXT_READY_TAIL]`` 數組元素引用與``->tails[RCU_WAIT_TAIL]``
相同的 RCU 回調，這表明沒有回調等待下一個 RCU 寬限期。 ``->tails[RCU_NEXT_TAIL]`` 數組元素引用 CB 4 的``->next`` 指針，表示所有剩余的 RCU 回調尚未被分配 RCU 寬限期。 請注意，
``->tails[RCU_NEXT_TAIL]`` 數組元素始終引用最后一個 RCU 回調的``->next`` 指針，除非回調列表為空，在這種情況下它引用``->head`` 指針 .

``->tails[RCU_NEXT_TAIL]`` 數組元素還有一個重要的特殊情況：當此列表*禁用*時，它可以是 ``NULL``。 當相應的 CPU 處于離線狀態或當相應的 CPU 的回調被卸載到 kthread 時，列表將被禁用，這兩種情
況都在別處描述。

隨著寬限期的推進，CPU 將它們的回調從“RCU_NEXT_TAIL”推進到“RCU_NEXT_READY_TAIL”到“RCU_WAIT_TAIL”到“RCU_DONE_TAIL”列表段。

``->gp_seq[]`` 數組記錄了與列表段對應的寬限期編號。 這就是允許不同的 CPU 對哪個是當前寬限期有不同的想法，同時仍然避免過早調用它們的回調。 特別是，這允許長時間空閑的 CPU 確定它們的哪些回調
已準備好在重新喚醒后調用。

``->len`` 計數``->head`` 中回調的數量，而``->len_lazy`` 包含已知僅釋放內存的那些回調的數量，其調用因此可以安全地推遲。

.. 重要的：：

``->len`` 字段決定是否存在與此 ``rcu_segcblist`` 結構關聯的回調，*不是* ``->head`` 指針。 這樣做的原因是所有準備好調用的回調（即那些在 ``RCU_DONE_TAIL`` 段中的回調）在回調調用時間
（``rcu_do_batch``）被一次性全部提取出來，因此 ` 如果 ``rcu_segcblist`` 中沒有未完成的回調，`->head`` 可以設置為 NULL。 如果 allback 調用必須被推遲，例如，因為一個高優先級進程剛剛在這個 CPU
上醒來，那么剩余的回調將被放回 ``RCU_DONE_TAIL`` 段并且 ``->head`` 再次指向段的開始。 簡而言之，head 字段可以短暫地為“NULL”，即使 CPU 一直存在回調。 因此，測試 ``->head`` 指針是否為 ``NULL``
是不合適的。

相反，``->len`` 和 ``->len_lazy`` 計數僅在調用相應的回調后才進行調整。 這意味著只有當 rcu_segcblist 結構確實沒有回調時，->len 計數才為零。 當然，``->len`` 計數的 off-CPU 采樣需要小心使用適
當的同步，例如內存屏障。 這種同步可能有點微妙，特別是在 ``rcu_barrier()`` 的情況下。

 

四、``rcu_data`` 結構

~~~~~~~~~~~~~~~~~~~~~~~~~~

``rcu_data`` 維護 RCU 子系統的每個 CPU 狀態。 除非另有說明，否則只能從相應的 CPU（和tracing）訪問此結構中的字段。 此結構是靜態檢測和 RCU 回調排隊的重點。 它還跟蹤它與相應的葉``rcu_node``結
構的關系，以允許更有效地將靜態狀態傳播到``rcu_node``組合樹上。 與 rcu_node 結構一樣，它提供了寬限期信息的本地副本，以允許從相應的 CPU 中免費同步訪問此信息。 最后，該結構記錄了相應 CPU 過去
的 dyntick-idle 狀態并跟蹤統計信息。

``rcu_data`` 結構的字段將在以下部分中單獨和成組討論。

4.1. 連接到其他數據結構
'''''''''''''''''''''''''''''''''

``rcu_data`` 結構的這一部分聲明如下：

::
1 int cpu;
2 struct rcu_node *mynode;
3 unsigned long grpmask;
4 bool beenonline;

``->cpu`` 字字段是相應 CPU 的編號，``->mynode`` 字段引用相應的 ``rcu_node`` 結構。 ``->mynode`` 用于在組合樹上傳播靜止狀態。 這兩個字段是常量，因此不需要同步。

``->grpmask`` 字段表示``->mynode->qsmask`` 中與此``rcu_data`` 結構對應的位，在傳播靜止狀態時也會使用。 ``->beenonline`` 標志在相應的 CPU 上線時設置，這意味著 debugfs 跟蹤不需要轉儲任何未設
置此標志的 ``rcu_data`` 結構。

4.2. 靜態和寬限期跟蹤
'''''''''''''''''''''''''''''''''''''''

``rcu_data`` 結構的這一部分聲明如下：

::
1 unsigned long gp_seq;
2 unsigned long gp_seq_needed;
3 bool cpu_no_qs;
4 bool core_needs_qs;
5 bool gpwrap;

``->gp_seq`` 字段與``rcu_state`` 和``rcu_node`` 結構中的同名字段對應。 ``->gp_seq_needed`` 字段是 rcu_node 結構中同名字段的對應部分。 它們可能每個都落后于它們的 ``rcu_node`` 對應物，但在
``CONFIG_NO_HZ_IDLE`` 和 ``CONFIG_NO_HZ_FULL`` 內核可以任意落后于 dyntick-idle 模式下的 CPU（但一旦退出 dyntick-idle 模式，這些計數器會趕上）。 如果給定的 ``rcu_data`` 結構的 ``->gp_seq``
的低兩位為零，那么這個 ``rcu_data`` 結構認為 RCU 是空閑的。

 

| **小測驗**： |
+------------------------------------------------ ----------------------+
| 所有這些寬限期數字的復制只會造成巨大的混亂。 為什么不只保留一個全局序列號并完成它？？？
+------------------------------------------------ ----------------------+
| **回答**： |
+------------------------------------------------ ----------------------+
| 因為如果只有一個全局序列號，就需要一個全局鎖來允許安全地訪問和更新它。 如果我們不打算擁有一個全局鎖，我們需要在每個節點的基礎上仔細管理數字。 回想一下之前快速測驗的答案，將之前采樣的靜止
狀態應用于錯誤的寬限期的后果非常嚴重。

``->cpu_no_qs`` 標志表示 CPU 尚未通過靜止狀態，而``->core_needs_qs`` 標志表示 RCU 內核需要來自相應 CPU 的靜止狀態。 ``->gpwrap`` 字段表明相應的 CPU 已經保持空閑太久以至于 ``gp_seq`` 計數器
有溢出的危險，這將導致 CPU 在下次從空閑退出時忽略其計數器的值。

4.3. RCU 回調處理
''''''''''''''''''''

在沒有 CPU 熱插拔事件的情況下，RCU 回調由注冊它們的同一個 CPU 調用。 這完全是一種緩存位置優化：回調可以并且確實在注冊它們的 CPU 之外的 CPU 上被調用。 畢竟，如果注冊給定回調的 CPU 在回調可以
被調用之前已經離線，那么真的沒有其他選擇。

``rcu_data`` 結構的這一部分聲明如下：

::
1 struct rcu_segcblist cblist;
2 long qlen_last_fqs_check;
3 unsigned long n_cbs_invoked;
4 unsigned long n_nocbs_invoked;
5 unsigned long n_cbs_orphaned;
6 unsigned long n_cbs_adopted;
7 unsigned long n_force_qs_snap;
8 long blimit;

``->cblist`` 結構是前面描述的分段回調列表。 只要 CPU 注意到另一個 RCU 寬限期已經完成，它就會在其 ``rcu_data`` 結構中推進回調。 CPU 通過注意到其“rcu_data”結構的“->gp_seq”字段的值與其葉
“rcu_node”結構的值不同來檢測 RCU 寬限期的完成。回想一下，每個 ``rcu_node`` 結構的 ``->gp_seq`` 字段在每個寬限期的開始和結束時更新。

當回調列表變得過長時，``->qlen_last_fqs_check`` 和``->n_force_qs_snap`` 協調來自``call_rcu()`` 和其朋友函數的靜態強制。

``->n_cbs_invoked``、``->n_cbs_orphaned`` 和 ``->n_cbs_adopted`` 字段計算調用的回調數，當此 CPU 離線時發送到其他 CPU，并在其他 CPU 離線時從其他 CPU 接收。``->n_nocbs_invoked``
在 CPU 的回調被卸載到 kthread 時使用。

最后，``->blimit`` 計數器是在給定時間可以調用的 RCU 回調的最大數量。

4.4. Dyntick-Idle 處理
''''''''''''''''''''

``rcu_data`` 結構的這一部分聲明如下：

::
1 int dynticks_snap;
2 unsigned long dynticks_fqs;

``->dynticks_snap`` 字段用于在強制靜止狀態時拍攝相應 CPU 的 dyntick-idle 狀態的快照，因此可以從其他 CPU 訪問。 最后，``->dynticks_fqs`` 字段用于統計此CPU 被確定為dyntick-idle 狀態的次數，
用于跟蹤和調試。

rcu_data 結構的這一部分聲明如下：

::
1 long dynticks_nesting;
2 long dynticks_nmi_nesting;
3 atomic_t dynticks;
4 bool rcu_need_heavy_qs;
5 bool rcu_urgent_qs;

rcu_data 結構中的這些字段維護相應 CPU 的 per-CPU dyntick-idle 狀態。 除非另有說明，否則只能從相應的 CPU（和tracing）訪問這些字段。

``->dynticks_nesting`` 字段計算進程執行的嵌套深度，因此在正常情況下該計數器的值為零或一。 NMI、irq 和跟蹤器由“->dynticks_nmi_nesting”字段計算。 由于無法屏蔽 NMI，因此必須使用 Andy Lutomirski
提供的算法仔細更改此變量。 idle 的初始轉換加 1，嵌套轉換加 2，因此嵌套級別 5 由 ``->dynticks_nmi_nesting`` 值 9 表示。 因此，這個計數器可以被認為是計算除了進程級轉換之外，這個 CPU 不能進入
dyntick-idle 模式的原因的數量。

然而，事實證明，當在非空閑內核上下文中運行時，Linux 內核完全能夠進入永不退出的中斷處理程序，反之亦然。 因此，每當 ``->dynticks_nesting`` 字段從零遞增時，``->dynticks_nmi_nesting`` 字段被設置
為一個大的正數，每當 ``->dynticks_nesting`` 字段減少到 零，``->dynticks_nmi_nesting`` 字段設置為零。 假設錯誤嵌套中斷的數量不足以使計數器溢出，每次相應的 CPU 從進程上下文進入空閑循環時，這種
方法都會糾正 ``->dynticks_nmi_nesting`` 字段。

``->dynticks`` 字段計算相應的 CPU 進出 dyntick-idle 模式或用戶模式的轉換次數，因此當 CPU 處于 dyntick-idle 模式或用戶模式時，該計數器的值為偶數，否則為奇數 . 用戶模式自適應滴答支持需要計算
進/出用戶模式的轉換（參見 timers/NO_HZ.txt）。

``->rcu_need_heavy_qs`` 字段用于記錄 RCU 核心代碼真的很想從相應的 CPU 看到一個靜止狀態，以至于它愿意調用重量級的 dyntick-counter 操作 . 此標志由 RCU 的上下文切換和 ``cond_resched()`` 代碼檢查，
它們提供暫時的空閑逗留作為響應。

最后，``->rcu_urgent_qs`` 字段用于記錄 RCU 核心代碼真的希望從相應的 CPU 看到靜止狀態這一事實，其他各種字段表明 RCU 多么想要這種靜止狀態。 此標志由 RCU 的上下文切換路徑
（``rcu_note_context_switch``）和 cond_resched 代碼檢查。

| **小測驗**： |
+------------------------------------------------ ----------------------+
| 為什么不簡單地將 ``->dynticks_nesting`` 和 ``->dynticks_nmi_nesting`` 計數器組合成一個計數器，只計算相應 CPU 非空閑的原因數量？ |
+------------------------------------------------ ----------------------+
| **回答**： |
+------------------------------------------------ ----------------------+
| 因為在存在其處理程序永遠不會返回的中斷以及設法從虛構中斷返回的處理程序的情況下，這將失敗。

一些特殊用途的構建存在其他字段，并將單獨討論。

 

五、``rcu_head`` 結構

~~~~~~~~~~~~~~~~~~~~~~~~~~

每個 ``rcu_head`` 結構代表一個 RCU 回調。 這些結構通常嵌入在受 RCU 保護的數據結構中，其算法使用異步寬限期。 相反，當使用阻塞等待 RCU 寬限期的算法時，RCU 用戶不需要提供“rcu_head”結構。

``rcu_head`` 結構具有如下字段：

::
1 struct rcu_head *next;
2 void (*func)(struct rcu_head *head);

``->next`` 字段用于將 ``rcu_data`` 結構中的列表中的 ``rcu_head`` 結構鏈接在一起。 ``->func`` 字段是一個指向函數的指針，當回調準備好被調用時，這個函數被傳遞一個指向 ``rcu_head`` 結構的
指針。 但是，``kfree_rcu()`` 使用``->func`` 字段來記錄``rcu_head`` 結構在封閉的受 RCU 保護的數據結構中的偏移量。

這兩個字段都由 RCU 在內部使用。 從 RCU 用戶的角度來看，這個結構是一個不透明的“cookie”。

 

| **小測驗**： |
+------------------------------------------------ ----------------------+
| 鑒于回調函數``->func`` 被傳遞了一個指向``rcu_head`` 結構的指針，該函數應該如何找到封閉的受 RCU 保護的數據結構的開頭？
+------------------------------------------------ ----------------------+
| **回答**： |
+------------------------------------------------ ----------------------+
| 實際上，每種類型的受 RCU 保護的數據結構都有一個單獨的回調函數。 因此，回調函數可以使用 Linux 內核中的“container_of()”宏（或其他軟件環境中的其他指針操作工具）來查找封閉結構的開頭。

``task_struct`` 結構中的 RCU 特定字段
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~

``CONFIG_PREEMPT_RCU`` 實現在 ``task_struct`` 結構中使用了一些額外的字段：

::
1 #ifdef CONFIG_PREEMPT_RCU
2 int rcu_read_lock_nesting;
3 union rcu_special rcu_read_unlock_special;
4 struct list_head rcu_node_entry;
5 struct rcu_node *rcu_blocked_node;
6 #endif /* #ifdef CONFIG_PREEMPT_RCU */
7 #ifdef CONFIG_TASKS_RCU
8 unsigned long rcu_tasks_nvcsw;
9 bool rcu_tasks_holdout;
10 struct list_head rcu_tasks_holdout_list;
11 int rcu_tasks_idle_cpu;
12 #endif /* #ifdef CONFIG_TASKS_RCU */

``->rcu_read_lock_nesting`` 字段記錄了 RCU 讀端臨界區的嵌套級別，
``->rcu_read_unlock_special`` 字段是一個位掩碼，記錄了需要 ``rcu_read_unlock()`` 做額外操作的特殊條件。
``->rcu_node_entry`` 字段用于形成在可搶占 RCU 讀端臨界區內阻塞的任務列表，
``->rcu_blocked_node`` 字段引用 ``rcu_node`` 結構，該任務為其列表的成員，或者如果它沒有被阻塞在可搶占的 RCU 讀端臨界區內，則為 ``NULL``。

``->rcu_tasks_nvcsw`` 字段跟蹤該任務在當前任務-RCU 寬限期開始時經歷的自愿上下文切換次數，
``->rcu_tasks_holdout`` 如果當前 task-RCU 寬限期正在等待此任務則設置，
``->rcu_tasks_holdout_list`` 是將此任務排入 holdout 列表的列表元素，
``->rcu_tasks_idle_cpu`` 跟蹤此空閑任務正在運行的 CPU，但前提是該任務當前正在運行 ，也就是說，CPU 當前是否處于空閑狀態。

 

六、 訪問函數

~~~~~~~~~~~~~~~~~~

以下清單顯示了``rcu_get_root()``、``rcu_for_each_node_breadth_first`` 和``rcu_for_each_leaf_node()`` 函數和宏：

::
1 static struct rcu_node *rcu_get_root(struct rcu_state *rsp)
2 {
3 return &rsp->node[0];
4 }
5
6 #define rcu_for_each_node_breadth_first(rsp, rnp) \
7 for ((rnp) = &(rsp)->node[0]; \
8 (rnp) < &(rsp)->node[NUM_RCU_NODES]; (rnp)++)
9
10 #define rcu_for_each_leaf_node(rsp, rnp) \
11 for ((rnp) = (rsp)->level[NUM_RCU_LVLS - 1]; \
12 (rnp) < &(rsp)->node[NUM_RCU_NODES]; (rnp)++)

``rcu_get_root()`` 只是返回指向指定``rcu_state`` 結構的``->node[]`` 數組的第一個元素的指針，這是根``rcu_node`` 結構。

如前所述，``rcu_for_each_node_breadth_first()`` 宏利用``rcu_state`` 結構的``->node[]`` 數組中的``rcu_node`` 結構的布局，執行廣度優先 遍歷只需按順序遍歷數組即可。 類似地，
``rcu_for_each_leaf_node()`` 宏只遍歷數組的最后一部分，因此只遍歷葉``rcu_node`` 結構。

| **小測驗**： |
+------------------------------------------------ ----------------------+
| 如果 ``rcu_node`` 樹只包含一個節點，``rcu_for_each_leaf_node()`` 會做什么？ |
+------------------------------------------------ ----------------------+
| **回答**： |
+------------------------------------------------ ----------------------+
| 在單節點的情況下，``rcu_for_each_leaf_node()`` 遍歷單個節點。

 

概括
~~~~~~~

因此 RCU 的狀態由 ``rcu_state`` 結構表示，其中包含 ``rcu_node`` 和 ``rcu_data`` 結構的組合樹。 最后，在 ``CONFIG_NO_HZ_IDLE`` 內核中，每個 CPU 的 dyntick-idle 狀態由 ``rcu_data``
結構中與 dynticks 相關的字段跟蹤。 如果您做到了這一點，那么您已經做好了閱讀本系列其他文章中的代碼演練的準備。

致謝
~~~~~~~~~~~~~~~

我要感謝 Cyrill Gorcunov、Mathieu Desnoyers、Dhaval Giani、Paul Turner、Abhishek Srivastava、Matt Kowalczyk 和 Serge Hallyn 幫助我使這份文件更易于閱讀。

法律聲明
~~~~~~~~~~~~~~~

本作品僅代表作者觀點，不代表 IBM 觀點。

Linux 是 Linus Torvalds 的注冊商標。

其他公司、產品和服務名稱可能是其他公司的商標或服務標記。