TREE_RCU 資料結構導覽 [LWN.net]¶
2016年12月18日
本文由 Paul E. McKenney 貢獻
簡介¶
本文件描述了 RCU 的主要資料結構及其相互關係。
資料結構關係¶
RCU 在所有意圖和目的上都是一個大型狀態機，其資料結構以允許 RCU 讀取器極快地執行的方式維護狀態，同時還以高效且極其可擴充套件的方式處理更新器請求的 RCU 寬限期。 RCU 更新器的效率和可擴充套件性主要由組合樹提供，如下所示
此圖顯示了一個包含 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 的事件，例如靜止狀態、動態節拍空閒轉換和 CPU 熱插拔操作。 靜止狀態由每個 CPU 的 rcu_data 結構記錄，其他事件由葉級 rcu_node 結構記錄。 所有這些事件都會在樹的每一層進行組合，直到最終在樹的根 rcu_node 結構處完成寬限期。 一旦每個 CPU（或者，在 CONFIG_PREEMPT_RCU 的情況下，任務）透過靜止狀態，就可以在根處完成寬限期。 一旦寬限期完成，該事實的記錄將傳播回樹中。
從圖中可以看出，在 64 位系統上，具有 64 個葉子的兩級樹可以容納 1,024 個 CPU，根部的扇出為 64，葉子的扇出為 16。
快速測驗: |
為什麼葉子的扇出也不是 64？ |
答案: |
因為影響葉級 當然，使用數百或數千個 CPU 的進一步經驗可能會表明，非葉 為具有強大 NUMA 特徵的系統構建的核心可能還需要調整 |
如果您的系統有超過 1,024 個 CPU（或者 32 位系統上有超過 512 個 CPU），則 RCU 將自動向樹中新增更多層。 例如，如果您瘋狂到構建一個具有 65,536 個 CPU 的 64 位系統，RCU 會將 rcu_node 樹配置如下
RCU 目前允許最多四級樹，在 64 位系統上最多可容納 4,194,304 個 CPU，但在 32 位系統上僅可容納 524,288 個 CPU。 另一方面，您可以將 CONFIG_RCU_FANOUT 和 CONFIG_RCU_FANOUT_LEAF 都設定為小至 2，這會導致使用 4 級樹的 16 CPU 測試。 這對於在小型測試機器上測試大型系統功能很有用。
這種多級組合樹使我們能夠獲得分割槽的大部分效能和可擴充套件性優勢，即使 RCU 寬限期檢測本質上是全域性操作。 這裡的訣竅是，只有最後一個報告靜止狀態到給定 rcu_node 結構的 CPU 才需要前進到樹中上一級的 rcu_node 結構。 這意味著在葉級 rcu_node 結構中，每十六次訪問中只有一次會向上移動到樹中。 對於內部 rcu_node 結構，情況甚至更加極端：每六十四次訪問中只有一次會向上移動到樹中。 因為絕大多數 CPU 不會向上移動到樹中，所以鎖爭用在樹中保持大致恆定。 無論系統中存在多少 CPU，每個寬限期最多有 64 個靜止狀態報告會一直傳遞到根 rcu_node 結構，從而確保該根 rcu_node 結構上的鎖爭用保持在可接受的低水平。
實際上，組合樹的作用就像一個大的減震器，無論系統上的負載水平如何，都能使鎖爭用保持在所有樹級別的控制之下。
RCU 更新器透過註冊 RCU 回撥來等待正常寬限期，可以直接透過 call_rcu() 註冊，也可以間接透過 synchronize_rcu() 及其友元函式註冊。 RCU 回撥由 rcu_head 結構表示，這些結構在等待寬限期過去時在 rcu_data 結構上排隊，如下圖所示
此圖顯示了 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_RCU_BOOST的CONFIG_PREEMPT_RCU中，它管理每個rcu_node的優先順序提升核心執行緒 (kthread) 和狀態。 最後，它記錄 CPU 熱插拔狀態，以便確定在給定的寬限期內應忽略哪些 CPU。rcu_data：此每個 CPU 結構是靜止狀態檢測和 RCU 回撥排隊的重點。 它還會跟蹤其與相應葉rcu_node結構的關係，以便更有效地將靜止狀態向上傳播到rcu_node組合樹中。 與rcu_node結構一樣，它提供寬限期資訊的本地副本，以便從相應 CPU 免費同步訪問此資訊。 最後，此結構記錄相應 CPU 的過去動態節拍空閒狀態，並跟蹤統計資訊。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 結構的幾個欄位在以下部分中單獨和成組地進行討論。 更專業的欄位將在討論其用途時進行介紹。
與 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 樹嵌入到 ->node[] 陣列中，如下圖所示
此對映的一個有趣的後果是，樹的廣度優先遍歷實現為陣列的簡單線性掃描，這實際上是 rcu_for_each_node_breadth_first() 宏的作用。 此宏在寬限期的開始和結束時使用。
->level 陣列的每個條目都引用樹的相應級別上的第一個 rcu_node 結構，例如，如下圖所示
陣列的第零個元素引用根 rcu_node 結構，第一個元素引用根 rcu_node 的第一個子節點，最後第二個元素引用第一個葉 rcu_node 結構。
無論其價值如何，如果您將樹繪製成樹形而不是陣列形，則很容易繪製平面表示
最後，->rda 欄位引用每個 CPU 指向相應 CPU 的 rcu_data 結構的指標。
一旦初始化完成，所有這些欄位都是常量，因此不需要任何保護。
寬限期跟蹤¶
rcu_state 結構的這一部分宣告如下
1 unsigned long gp_seq;
RCU 寬限期已編號，並且 ->gp_seq 欄位包含當前寬限期序列號。 底部的兩個位是當前寬限期的狀態，對於尚未啟動的狀態為零，對於正在進行的狀態為一。 換句話說，如果 ->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 欄位以節拍數跟蹤最長寬限期的持續時間。 它由根 rcu_node 的 ->lock 保護。
->name 和 ->abbr 欄位區分可搶佔 RCU（“rcu_preempt”和“p”）和不可搶佔 RCU（“rcu_sched”和“s”）。 這些欄位用於診斷和跟蹤目的。
rcu_node 結構¶
rcu_node 結構形成一個組合樹，該樹將靜止狀態資訊從葉子傳播到根，並將寬限期資訊從根向下傳播到葉子。 它們提供寬限期狀態的本地副本，以便以同步方式訪問此資訊，而不會受到全域性鎖定原本會帶來的可擴充套件性限制。 在 CONFIG_PREEMPT_RCU 核心中，它們管理在其當前 RCU 讀取端臨界區中被阻止的任務列表。 在具有 CONFIG_RCU_BOOST 的 CONFIG_PREEMPT_RCU 中，它們管理每個 rcu_node 的優先順序提升核心執行緒 (kthread) 和狀態。 最後，它們記錄 CPU 熱插拔狀態，以便確定在給定的寬限期內應忽略哪些 CPU。
rcu_node 結構的欄位將在以下部分中單獨和成組地進行討論。
連線到組合樹¶
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 欄位僅在初始化和跟蹤期間使用。 ->grpmask 欄位是 ->grpnum 的位掩碼對應項，因此始終只有一個位設定。 此掩碼用於清除此 rcu_node 結構在其父節點的位掩碼中的對應位，稍後將對此進行描述。 最後，->grplo 和 ->grphi 欄位分別包含此 rcu_node 結構服務的最低編號和最高編號 CPU。
所有這些欄位都是常量，因此不需要任何同步。
同步¶
rcu_node 結構的此欄位宣告如下
1 raw_spinlock_t lock;
此欄位用於保護此結構中的其餘欄位，除非另有說明。 也就是說，此結構中的所有欄位都可以在沒有鎖定的情況下訪問以進行跟蹤。 是的，這可能會導致令人困惑的跟蹤，但與其因為黑森堡蟲而消失，不如一些跟蹤混亂。
寬限期跟蹤¶
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 結構的這一部分具有以下欄位
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 和正常寬限期和加速寬限期的開始。
快速測驗: |
為什麼這些位掩碼受到鎖定的保護？ 來吧，您沒聽說過原子指令嗎？？？ |
答案: |
無鎖寬限期計算！ 如此誘人的可能性！ 但請考慮以下事件序列
因此，絕對需要鎖定才能協調位清除與 |
阻止任務管理¶
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 欄位）排隊到與傳出上下文切換執行的 CPU 對應的葉 rcu_node 結構的 ->blkd_tasks 列表的頭部。 當這些任務稍後退出其 RCU 讀取端臨界區時，它們會從列表中刪除自己。 因此，此列表按反時間順序排列，因此，如果其中一個任務正在阻止當前的寬限期，則所有後續任務也必須阻止相同的寬限期。 因此，指向此列表的單個指標足以跟蹤阻止給定寬限期的所有任務。 該指標儲存在正常寬限期的 ->gp_tasks 中，儲存在加速寬限期的 ->exp_tasks 中。 如果沒有正在進行的寬限期，或者沒有阻止任務阻止該寬限期完成，則最後兩個欄位為 NULL。 如果這兩個指標中的任何一個引用從 ->blkd_tasks 列表中刪除自己的任務，則該任務必須將指標前進到列表中的下一個任務，或者如果沒有列表中的後續任務，則將指標設定為 NULL。
例如，假設任務 T1、T2 和 T3 都硬關聯到系統中編號最大的 CPU。 然後，如果任務 T1 在 RCU 讀取端臨界區中被阻止，則加速寬限期開始，然後任務 T2 在 RCU 讀取端臨界區中被阻止，然後正常寬限期開始，最後任務 3 在 RCU 讀取端臨界區中被阻止，則最後一個葉 rcu_node 結構的阻止任務列表的狀態將如下所示
任務 T1 正在阻止兩個寬限期，任務 T2 僅阻止正常寬限期，任務 T3 不阻止任何寬限期。 請注意，這些任務不會在恢復執行後立即從列表中刪除自己。 相反，它們將保留在列表中，直到它們執行結束其 RCU 讀取端臨界區的最外層 rcu_read_unlock()。
->wait_blkd_tasks 欄位指示當前寬限期是否正在等待被阻止的任務。
調整 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，這在每個插槽有八個 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 預處理器變數中。
這些變數用於控制 C 預處理器 #if 語句（跨越第 26-66 行），該語句計算樹的每一級所需的 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 結構 ¶
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 （這與空 not 相同）。 ->tails[] 陣列的每個元素都引用列表中相應段的最後一個回撥的 ->next 指標，如果該段和所有先前的段都為空，則引用列表的 ->head 指標。如果相應的段為空但某些先前的段不為空，則陣列元素與其前身相同。較舊的回撥更靠近列表的頭部，新的回撥新增到尾部。 ->head 指標， ->tails[] 陣列和回撥之間的這種關係顯示在此圖中
在此圖中， ->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] 陣列元素還有一個重要的特殊情況：當此列表 disabled 時，它可以為 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 結構的回撥， not ->head 指標。原因是所有準備好呼叫的回撥（即 RCU_DONE_TAIL 段中的回撥）都會在回撥呼叫時間 (rcu_do_batch) 一次性提取出來，因此，如果沒有 rcu_segcblist 中剩餘的未完成回撥，則 ->head 可能會設定為 NULL。如果必須推遲迴調呼叫，例如，因為一個高優先順序程序剛剛在此 CPU 上喚醒，則剩餘的回撥會放回 RCU_DONE_TAIL 段，並且 ->head 再次指向該段的開頭。簡而言之，即使 CPU 一直存在回撥，head 欄位也可能短暫地為 NULL 。因此，測試 ->head 指標是否為 NULL 是不合適的。
相比之下，只有在呼叫了相應的回撥後，才會調整 ->len 和 ->len_lazy 計數。這意味著只有當 rcu_segcblist 結構確實沒有回撥時， ->len 計數才為零。當然，對 ->len 計數的異 CPU 取樣需要仔細使用適當的同步，例如記憶體屏障。這種同步可能有點微妙，特別是在 rcu_barrier() 的情況下。
rcu_data 結構 ¶
rcu_data 維護 RCU 子系統的每個 CPU 狀態。除非另有說明，否則此結構中的欄位只能從相應的 CPU （和從跟蹤）訪問。此結構是靜止狀態檢測和 RCU 回撥排隊的重點。它還跟蹤其與相應的葉 rcu_node 結構的關係，以允許更有效地將靜止狀態傳播到 rcu_node 組合樹。與 rcu_node 結構一樣，它提供了寬限期資訊的本地副本，以允許從相應的 CPU 免費同步訪問此資訊。最後，此結構記錄了相應 CPU 的過去 dyntick-idle 狀態，並跟蹤統計資訊。
rcu_data 結構的欄位將在以下各節中單獨或分組討論。
與其他資料結構的連線 ¶
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 結構的位，並且在傳播靜止狀態時也使用。每當相應的 CPU 上線時，就會設定 ->beenonline 標誌，這意味著 debugfs 跟蹤不需要轉儲任何未設定此標誌的 rcu_data 結構。
靜止狀態和寬限期跟蹤 ¶
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 在下次退出空閒狀態時忽略其計數器的值。
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 接收的回撥數。當 CPU 的回撥被解除安裝到 kthread 時，使用 ->n_nocbs_invoked 。
最後， ->blimit 計數器是給定時間可以呼叫的 RCU 回撥的最大數量。
Dyntick-Idle 處理 ¶
rcu_data 結構的這一部分宣告如下
1 int watching_snap;
2 unsigned long dynticks_fqs;
->watching_snap 欄位用於在強制靜止狀態時獲取相應 CPU 的 dyntick-idle 狀態的快照，因此可以從其他 CPU 訪問。最後， ->dynticks_fqs 欄位用於計算此 CPU 被確定處於 dyntick-idle 狀態的次數，並用於跟蹤和除錯目的。
rcu_data 結構的這一部分宣告如下
1 long nesting;
2 long nmi_nesting;
3 atomic_t dynticks;
4 bool rcu_need_heavy_qs;
5 bool rcu_urgent_qs;
rcu_data 結構中的這些欄位維護相應 CPU 的每個 CPU dyntick-idle 狀態。除非另有說明，否則這些欄位只能從相應的 CPU （和從跟蹤）訪問。
->nesting 欄位計算程序執行的巢狀深度，因此在正常情況下，此計數器的值為零或一。 NMI、irq 和 tracers 由 ->nmi_nesting 欄位計數。由於 NMI 無法遮蔽，因此必須使用 Andy Lutomirski 提供的演算法小心地對該變數進行更改。從空閒狀態的初始轉換增加 1，巢狀轉換增加 2，因此 5 的巢狀級別由 ->nmi_nesting 值 9 表示。因此，除了程序級別轉換之外，該計數器可以被認為是計算不允許此 CPU 進入 dyntick-idle 模式的原因的數量。
然而，事實證明，在非空閒核心上下文中執行時，Linux 核心完全能夠進入永遠不會退出的中斷處理程式，反之亦然。因此，每當 ->nesting 欄位從零遞增時， ->nmi_nesting 欄位都會設定為一個大的正數，每當 ->nesting 欄位遞減為零時， ->nmi_nesting 欄位都會設定為零。假設錯誤巢狀中斷的數量不足以使計數器溢位，則此方法每次相應的 CPU 從程序上下文中進入空閒迴圈時都會更正 ->nmi_nesting 欄位。
->dynticks 欄位計算相應 CPU 與 dyntick-idle 或使用者模式之間的轉換，因此當 CPU 處於 dyntick-idle 模式或使用者模式時，此計數器具有偶數值，否則具有奇數值。需要為使用者模式自適應滴答支援計數到/從使用者模式的轉換（請參閱 NO_HZ: 減少排程時鐘滴答）。
->rcu_need_heavy_qs 欄位用於記錄 RCU 核心程式碼確實希望看到相應 CPU 的靜止狀態的事實，以至於它願意呼叫重量級 dyntick-counter 操作。此標誌由 RCU 的上下文切換和 cond_resched() 程式碼檢查，這些程式碼提供了短暫的空閒停留時間來作為響應。
最後， ->rcu_urgent_qs 欄位用於記錄 RCU 核心程式碼確實希望看到相應 CPU 的靜止狀態的事實，其中各種其他欄位指示 RCU 有多希望獲得此靜止狀態。此標誌由 RCU 的上下文切換路徑 (rcu_note_context_switch) 和 cond_resched 程式碼檢查。
快速測驗: |
為什麼不簡單地將 |
答案: |
因為這會在處理程式永遠不會返回的中斷和設法從虛構的中斷返回的處理程式面前失敗。 |
存在一些特殊用途構建的其他欄位，將在單獨討論。
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_head 結構連結在一起在 rcu_data 結構中的列表中。 ->func 欄位是指向回調準備好被呼叫時要呼叫的函式的指標，並且該函式被傳遞給一個指向 rcu_head 結構的指標。但是， kfree_rcu() 使用 ->func 欄位來記錄包含的 RCU 保護的資料結構中 rcu_head 結構的偏移量。
這兩個欄位都由 RCU 在內部使用。從 RCU 使用者的角度來看，此結構是一個不透明的“cookie”。
快速測驗: |
鑑於回撥函式 |
答案: |
在實際實踐中，每種型別的 RCU 保護的資料結構都有一個單獨的回撥函式。因此，回撥函式可以使用 Linux 核心中的 |
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 寬限期開始時經歷的自願上下文切換次數，如果當前的 task-RCU 寬限期正在等待此任務，則設定 ->rcu_tasks_holdout ， ->rcu_tasks_holdout_list 是一個列表元素，將此任務排隊到保留列表， ->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 的狀態由 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 的註冊商標。
其他公司、產品和服務名稱可能是其他公司的商標或服務標記。