TREE_RCU 的寬限期記憶體排序之旅¶
2017 年 8 月 8 日
本文由 Paul E. McKenney 貢獻
簡介¶
本文件粗略地概述了 Tree RCU 的寬限期記憶體排序保證是如何提供的。
什麼是 Tree RCU 的寬限期記憶體排序保證？¶
RCU 寬限期為非空閒非離線程式碼提供了極其強大的記憶體排序保證。保證在給定 RCU 寬限期結束之後發生的任何程式碼都能看到該寬限期開始之前的所有訪問的效果，這些訪問都在 RCU 讀取端關鍵區域內。類似地，保證在給定 RCU 寬限期開始之前發生的任何程式碼都看不到該寬限期結束後發生的所有訪問的效果，這些訪問都在 RCU 讀取端關鍵區域內。
請注意，RCU-sched 讀取端關鍵區域包括停用搶佔的任何程式碼區域。鑑於每個單獨的機器指令都可以被認為是一個極小的停用搶佔的程式碼區域，可以將 synchronize_rcu() 視為增強版的 smp_mb()。
RCU 更新器透過將其更新分為兩個階段來使用此保證，其中一個階段在寬限期之前執行，另一個階段在寬限期之後執行。在最常見的用例中，第一階段從連結的 RCU 保護資料結構中刪除一個元素，第二階段釋放該元素。為了使其工作，任何在第一階段更新之前（在常見情況下，刪除）目睹狀態的讀取器都不能目睹第二階段更新之後（在常見情況下，釋放）的狀態。
RCU 實現使用基於鎖的關鍵區域網路、記憶體屏障和每個 CPU 的處理來提供此保證，如下節所述。
Tree RCU 寬限期記憶體排序構建塊¶
RCU 寬限期記憶體排序的主要工具是 rcu_node 結構的 ->lock 的關鍵區域。這些關鍵區域使用輔助函式進行鎖獲取，包括 raw_spin_lock_rcu_node()、raw_spin_lock_irq_rcu_node() 和 raw_spin_lock_irqsave_rcu_node()。它們的鎖釋放對應物分別是 raw_spin_unlock_rcu_node()、raw_spin_unlock_irq_rcu_node() 和 raw_spin_unlock_irqrestore_rcu_node()。為了完整起見，還提供了 raw_spin_trylock_rcu_node()。關鍵點在於鎖獲取函式，包括 raw_spin_trylock_rcu_node()，在成功獲取鎖後立即呼叫 smp_mb__after_unlock_lock()。
因此，對於任何給定的 rcu_node 結構，所有 CPU 都會看到在上述鎖釋放函式之一之前發生的任何訪問發生在稍後的上述鎖獲取函式之一之後發生的任何訪問之前。此外，所有 CPU 都會看到在給定 CPU 上上述鎖釋放函式之一之前發生的任何訪問發生在稍後在該同一 CPU 上執行的上述鎖獲取函式之一之後發生的任何訪問之前，即使鎖釋放和鎖獲取函式操作的是不同的 rcu_node 結構。Tree RCU 使用這兩個排序保證在所有以任何方式參與寬限期的 CPU 之間形成排序網路，包括在相關寬限期期間上線或下線的任何 CPU。
以下測試程式展示了這些鎖獲取和鎖釋放函式的排序效果
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);
WARN_ON() 在“時間盡頭”評估，在所有更改都已在整個系統中傳播之後。如果沒有獲取函式提供的 smp_mb__after_unlock_lock()，例如在 PowerPC 上，此 WARN_ON() 可能會觸發。smp_mb__after_unlock_lock() 呼叫阻止此 WARN_ON() 觸發。
快速測驗: |
但是 rcu_node 結構鎖獲取鏈保證新的讀取器將看到更新器的所有寬限期前訪問，並且還保證更新器的寬限期後訪問將看到所有舊讀取器的訪問。那麼為什麼我們需要所有這些對 smp_mb__after_unlock_lock() 的呼叫呢？ |
答案: |
因為我們必須為 RCU 的輪詢寬限期原語提供排序，例如， 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 保證不會發生 r0 == 0 && r1 == 0 的結果，即使 CPU 1 處於 RCU 擴充套件靜止狀態（空閒或離線），因此根本不會直接與 RCU 核心處理互動。 |
這種方法必須擴充套件到包括空閒 CPU，這些 CPU 需要 RCU 的寬限期記憶體排序保證，以擴充套件到當前空閒停留之前和之後的所有 RCU 讀取端關鍵區域。這種情況由對強排序的 atomic_add_return() 讀取-修改-寫入原子操作的呼叫處理，該操作在空閒進入時的 ct_kernel_exit_state() 和空閒退出時的 ct_kernel_enter_state() 中呼叫。寬限期 kthread 首先呼叫 ct_rcu_watching_cpu_acquire()（前面有一個完整的記憶體屏障）和 rcu_watching_snap_stopped_since()（兩者都依賴於獲取語義）來檢測空閒 CPU。
快速測驗: |
但是對於在整個寬限期內保持離線的 CPU 呢？ |
答案: |
這樣的 CPU 在寬限期開始時將處於離線狀態，因此寬限期不會期望它們的靜止狀態。寬限期開始和 CPU 熱插拔操作之間的競爭由 CPU 的葉 |
該方法必須擴充套件到處理最後一個案例，即喚醒在 synchronize_rcu() 中阻塞的任務。此任務可能被繫結到尚未意識到寬限期已結束的 CPU，因此可能尚未受到寬限期的記憶體排序的約束。因此，在 synchronize_rcu() 程式碼路徑中，從 wait_for_completion() 返回後有一個 smp_mb()。
快速測驗: |
什麼？在哪裡？？？我沒有看到從 |
答案: |
那是因為我在建立此文件時發現了對該 |
Tree RCU 的寬限期記憶體排序保證最嚴重地依賴於 rcu_node 結構的 ->lock 欄位，以至於有必要在下一節的圖中縮寫此模式。例如，考慮下面顯示的 rcu_prepare_for_idle() 函式，該函式是強制執行新到達的 RCU 回撥針對未來寬限期的排序的幾個函式之一
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 }
但是對於此討論真正重要的 rcu_prepare_for_idle() 的部分是第 32-34 行。因此，我們將此函式縮寫如下
該框表示 rcu_node 結構的 ->lock 關鍵區域，頂部的雙線表示額外的 smp_mb__after_unlock_lock()。
Tree RCU 寬限期記憶體排序元件¶
Tree RCU 的寬限期記憶體排序保證由多個 RCU 元件提供
以下每個部分都詳細介紹了相應的元件。
回撥登錄檔¶
如果 RCU 的寬限期保證有任何意義，那麼在給定 call_rcu() 呼叫之前發生的任何訪問也必須發生在相應的寬限期之前。RCU 寬限期保證的此部分的實現如下圖所示
因為 call_rcu() 通常僅作用於 CPU 本地狀態，所以它不提供任何排序保證，無論是對於自身還是對於更新的第一階段（再次，通常是從 RCU 保護的資料結構中刪除元素）。它只是將 rcu_head 結構排隊到每個 CPU 的列表中，直到稍後呼叫 rcu_accelerate_cbs() 才能與寬限期關聯，如上圖所示。
左側顯示的一組程式碼路徑透過 note_gp_changes() 呼叫 rcu_accelerate_cbs()，要麼直接從 call_rcu() 呼叫（如果當前 CPU 被排隊的 rcu_head 結構淹沒），要麼更可能從 RCU_SOFTIRQ 處理程式呼叫。中間的另一個程式碼路徑僅在以 CONFIG_RCU_FAST_NO_HZ=y 構建的核心中採用，該路徑透過 rcu_prepare_for_idle() 呼叫 rcu_accelerate_cbs()。右側的最後一個程式碼路徑僅在以 CONFIG_HOTPLUG_CPU=y 構建的核心中採用，該路徑透過 rcu_advance_cbs()、rcu_migrate_callbacks、rcutree_migrate_callbacks() 和 takedown_cpu() 呼叫 rcu_accelerate_cbs()，而 takedown_cpu() 反過來又在傳出 CPU 完全離線後在倖存的 CPU 上呼叫。
寬限期處理中還有一些其他程式碼路徑會機會主義地呼叫 rcu_accelerate_cbs()。但是，無論哪種方式，CPU 最近排隊的所有 rcu_head 結構都與未來的寬限期編號相關聯，該編號受 CPU 的主要 rcu_node 結構的 ->lock 的保護。在所有情況下，對於同一 rcu_node 結構的 ->lock 的任何先前關鍵區域，以及對於任何 rcu_node 結構的 ->lock 的當前任務或 CPU 的任何先前關鍵區域，都存在完整的排序。
下一節將顯示此排序如何確保在 call_rcu() 之前發生的任何訪問（特別包括更新的第一階段）發生在相應寬限期開始之前。
快速測驗: |
但是 |
答案: |
|
寬限期初始化¶
寬限期初始化由寬限期核心執行緒執行，該執行緒在 rcu_gp_init() 函式中多次遍歷 rcu_node 樹。這意味著顯示透過寬限期計算的完整排序流程將需要複製此樹。如果您發現這令人困惑，請注意 rcu_node 的狀態會隨著時間的推移而變化，就像赫拉克利特的河流一樣。但是，為了使 rcu_node 河流易於處理，寬限期核心執行緒的遍歷分多個部分呈現，從本節中的寬限期初始化的各個階段開始。
第一個與排序相關的寬限期初始化操作是推進 rcu_state 結構的 ->gp_seq 寬限期編號計數器，如下所示
實際的增量是使用 smp_store_release() 執行的，這有助於拒絕誤報 RCU CPU 停頓檢測。請注意，僅觸控根 rcu_node 結構。
第一次遍歷 rcu_node 樹會根據自上次寬限期開始以來已上線或下線的 CPU 來更新位掩碼。在常見情況下，此 rcu_node 結構的線上 CPU 數量尚未轉換到或從零轉換，此遍歷將僅掃描葉 rcu_node 結構。但是，如果給定葉 rcu_node 結構的線上 CPU 數量已從零轉換，則將為第一個傳入的 CPU 呼叫 rcu_init_new_rnp()。類似地，如果給定葉 rcu_node 結構的線上 CPU 數量已轉換為零，則將為最後一個傳出的 CPU 呼叫 rcu_cleanup_dead_rnp()。下圖顯示瞭如果最左邊的 rcu_node 結構上線其第一個 CPU 且如果下一個 rcu_node 結構沒有線上 CPU（或者，如果最左邊的 rcu_node 結構離線其最後一個 CPU 且如果下一個 rcu_node 結構沒有線上 CPU）時的排序路徑。
透過 rcu_node 樹的最後一次 rcu_gp_init() 遍歷以廣度優先的方式進行，將每個 rcu_node 結構的 ->gp_seq 欄位設定為來自 rcu_state 結構的最新推進值，如下圖所示。
此更改還將導致每個 CPU 下一次呼叫 __note_gp_changes() 時注意到新的寬限期已經開始，如下節所述。但是因為寬限期 kthread 在根處（透過推進 rcu_state 結構的 ->gp_seq 欄位）啟動了寬限期，然後在設定每個葉 rcu_node 結構的 ->gp_seq 欄位之前，每個 CPU 對寬限期開始的觀察將在寬限期實際開始之後發生。
快速測驗: |
但是啟動寬限期的 CPU 呢？為什麼它不會在啟動寬限期時立即看到寬限期的開始？ |
答案: |
在某些深刻的哲學和過度擬人化的意義上，是的，啟動寬限期的 CPU 會立即意識到已經這樣做了。但是，如果我們改為假設 RCU 沒有自我意識，那麼即使啟動寬限期的 CPU 也要到第一次呼叫 |
自我報告的靜止狀態¶
當可能阻止寬限期的所有實體都報告了靜止狀態（或者如後面的章節所述，已經代表它們報告了靜止狀態）時，寬限期可以結束。線上非空閒 CPU 報告自己的靜止狀態，如下圖所示
這是最後一個報告靜止狀態的 CPU，它發出寬限期結束的訊號。較早的靜止狀態將僅向上推動 rcu_node 樹，直到它們遇到正在等待其他靜止狀態的 rcu_node 結構。但是，排序仍然得到保留，因為稍後的某個靜止狀態將獲取該 rcu_node 結構的 ->lock。
任意數量的事件都可能導致 CPU 呼叫 note_gp_changes（或者，直接呼叫 __note_gp_changes()），此時該 CPU 將注意到在保持其葉 rcu_node 鎖的同時，新的寬限期已經開始。因此，此圖中顯示的所有執行都在寬限期開始之後發生。此外，此 CPU 將考慮在呼叫 __note_gp_changes() 之前啟動的任何 RCU 讀取端關鍵區域在寬限期之前啟動，因此寬限期必須等待的關鍵區域。
快速測驗: |
但是 RCU 讀取端關鍵區域可能在寬限期開始之後啟動（較早的 |
答案: |
寬限期確實沒有必要等待這樣的關鍵區域。但是，允許等待它。而且，等待它也很重要，因為這種惰性方法比“大爆炸”一次性寬限期開始可能具有的可伸縮性要高得多。 |
如果 CPU 進行上下文切換，則 rcu_note_context_switch() 將在左側注意到靜止狀態。另一方面，如果 CPU 在使用者模式下執行時發生排程程式時鐘中斷，則 rcu_sched_clock_irq() 將在右側注意到靜止狀態。無論哪種方式，透過靜止狀態的通道都將在每個 CPU 的變數中記錄。
下次 RCU_SOFTIRQ 處理程式在此 CPU 上執行時（例如，在下一次排程程式時鐘中斷之後），rcu_core() 將呼叫 rcu_check_quiescent_state()，後者將注意到記錄的靜止狀態，並呼叫 rcu_report_qs_rdp()。如果 rcu_report_qs_rdp() 驗證靜止狀態確實適用於當前寬限期，它將呼叫 rcu_report_rnp()，後者將遍歷 rcu_node 樹，如圖底部所示，從每個 rcu_node 結構的 ->qsmask 欄位中清除位，並在結果為零時向樹向上傳播。
請注意，只有噹噹前 CPU 報告由該 rcu_node 結構為首的子樹的最後一個靜止狀態時，遍歷才會從給定的 rcu_node 結構向上傳遞。關鍵的一點是，如果 CPU 的遍歷停止在給定的 rcu_node 結構處，那麼將會有另一個 CPU（或者可能是同一個 CPU）的稍後遍歷從該點向上進行，並且 rcu_node ->lock 保證第一個 CPU 的靜止狀態發生在第二個 CPU 遍歷的其餘部分之前。重複應用此思路表明，所有 CPU 的靜止狀態都發生在最後一個 CPU 遍歷根 rcu_node 結構之前，“最後一個 CPU”是清除根 rcu_node 結構的 ->qsmask 欄位中的最後一位的 CPU。
動態滴答介面¶
由於能源效率方面的考慮，RCU 被禁止干擾空閒 CPU。因此，CPU 需要在進入或離開空閒狀態時通知 RCU，它們透過在每個 CPU 的變數上進行完全排序的返回值原子操作來做到這一點。排序效果如下所示
RCU 寬限期核心執行緒在保持相應 CPU 的葉 rcu_node 結構的 ->lock 的同時，對每個 CPU 的空閒變數進行取樣。這意味著在空閒期間之前（上圖頂部附近的橢圓）的任何 RCU 讀取端關鍵區域都將在當前寬限期結束之前發生。類似地，當前寬限期的開始將在空閒期間之後的任何 RCU 讀取端關鍵區域（上圖底部附近的橢圓）之前發生。
將其整合到完整的寬限期執行中將在下面介紹。
CPU 熱插拔介面¶
RCU 也被禁止干擾離線 CPU，這些 CPU 很可能已斷電並已從系統中完全移除。因此，CPU 需要將它們的來來去去通知 RCU，作為相應的 CPU 熱插拔操作的一部分。排序效果如下所示
由於 CPU 熱插拔操作的頻率遠低於空閒轉換，因此它們的權重更大，因此獲取 CPU 的葉 rcu_node 結構的 ->lock 並更新該結構的 ->qsmaskinitnext。RCU 寬限期核心執行緒對該掩碼進行取樣，以檢測自此寬限期開始以來已離線的 CPU。
將其整合到完整的寬限期執行中將在下面介紹。
強制靜止狀態¶
如上所述，空閒和離線 CPU 無法報告自己的靜止狀態，因此寬限期核心執行緒必須代表它們進行報告。此過程稱為“強制靜止狀態”，每隔幾個節拍重複一次，其排序效果如下所示
保證靜止狀態強制的每次透過都遍歷葉 rcu_node 結構，如果沒有由於最近空閒和/或離線 CPU 而導致的新靜止狀態，則僅遍歷葉。但是，如果如左側所示有新離線 CPU，或者如右側所示有新空閒 CPU，則相應的靜止狀態將被推向根。與自我報告的靜止狀態一樣，一旦到達 rcu_node 結構，該結構具有來自其他 CPU 的未完成的靜止狀態，則向上驅動停止。
快速測驗: |
最左邊的驅動程式在到達根 |
答案: |
分析得很好！實際上，在沒有 RCU 的錯誤的情況下，這是不可能的。但是此圖本身已經足夠複雜，因此為了簡潔而犧牲了準確性。您可以將其視為詩意的許可，也可以將其視為在拼接圖中解決的誤導。 |
寬限期清理¶
寬限期清理首先以廣度優先的方式掃描 rcu_node 樹，推進所有 ->gp_seq 欄位，然後推進 rcu_state 結構的 ->gp_seq 欄位。排序效果如下所示
如圖底部的橢圓形所示，一旦寬限期清理完成，下一個寬限期就可以開始。
快速測驗: |
但是寬限期到底何時結束呢？ |
答案: |
沒有一個有用的單點可以說寬限期結束了。最早合理的候選時間是最後一個 CPU 報告其靜止狀態之後，但 RCU 可能需要幾毫秒才能意識到這一點。最晚合理的候選時間是 |
回撥呼叫¶
一旦給定的 CPU 的葉 rcu_node 結構的 ->gp_seq 欄位已更新，該 CPU 就可以開始呼叫正在等待此寬限期結束的 RCU 回撥。這些回撥由 rcu_advance_cbs() 標識，通常由 __note_gp_changes() 呼叫。如下圖所示，此呼叫可以由排程時鐘中斷（左側的 rcu_sched_clock_irq()）或空閒進入（右側的 rcu_cleanup_after_idle()）觸發，但僅適用於使用 CONFIG_RCU_FAST_NO_HZ=y 構建的核心。無論哪種方式，都會引發 RCU_SOFTIRQ，從而導致 rcu_do_batch() 呼叫回撥，進而允許這些回撥執行每個更新所需的第二階段處理（直接或間接透過喚醒）。
請注意，回撥呼叫也可以由任何數量的極端情況程式碼路徑提示，例如，當 CPU 注意到它已排隊過多的回撥時。在所有情況下，CPU 在呼叫回撥之前都會獲取其葉 rcu_node 結構的 ->lock，從而保持了針對新完成的寬限期所需的排序。
但是，如果回撥函式與其他 CPU 通訊，例如，執行喚醒操作，則保持排序是該函式的責任。例如，如果回撥函式喚醒了一個在某些其他 CPU 上執行的任務，則回撥函式和被喚醒的任務都必須正確排序。要了解為什麼這很重要，請考慮寬限期清理圖的上半部分。回撥可能在對應於最左邊的葉 rcu_node 結構的 CPU 上執行，並喚醒一個將在對應於最右邊的葉 rcu_node 結構的 CPU 上執行的任務，並且寬限期核心執行緒可能尚未到達最右邊的葉。在這種情況下，寬限期的記憶體排序可能尚未到達該 CPU，因此回撥函式和喚醒的任務必須再次提供正確的排序。
整合在一起¶
拼接圖在此處
法律宣告¶
這項工作代表作者的觀點，不一定代表 IBM 的觀點。
Linux 是 Linus Torvalds 的註冊商標。
其他公司、產品和服務名稱可能是其他公司的商標或服務標誌。