TREE_RCU 的加速寬限期之旅¶
簡介¶
本文件描述了 RCU 的加速寬限期。與 RCU 的普通寬限期不同，普通寬限期接受較長的延遲以獲得較高的效率和最小的干擾，而加速寬限期接受較低的效率和顯著的干擾以獲得較短的延遲。
RCU 有兩種形式（RCU-preempt 和 RCU-sched），早期的第三種 RCU-bh 形式已透過其他兩種形式實現。這兩種實現的每一種都在其各自的部分中進行介紹。
加速寬限期設計¶
加速 RCU 寬限期不能被指責為微妙，因為它們實際上會衝擊尚未為當前加速寬限期提供靜止狀態的每個 CPU。唯一的優點是，隨著時間的推移，衝擊力已經變小了一些：之前呼叫 try_stop_cpus() 已被一系列呼叫 smp_call_function_single() 替換，每次呼叫都會導致向目標 CPU 傳送 IPI。相應的處理程式函式檢查 CPU 的狀態，儘可能激發更快的靜止狀態，並觸發該靜止狀態的報告。與 RCU 一樣，一旦所有內容都在靜止狀態下花費了一段時間，加速寬限期就已完成。
smp_call_function_single() 處理程式操作的詳細資訊取決於 RCU 的形式，如下面的部分所述。
RCU-preempt 加速寬限期¶
CONFIG_PREEMPTION=y 核心實現 RCU-preempt。以下圖顯示了 RCU-preempt 加速寬限期處理給定 CPU 的總體流程
實心箭頭表示直接操作，例如，函式呼叫。虛線箭頭表示間接操作，例如，IPI 或經過一段時間後達到的狀態。
如果給定 CPU 處於離線或空閒狀態，synchronize_rcu_expedited() 將忽略它，因為空閒和離線 CPU 已經駐留在靜止狀態。否則，加速寬限期將使用 smp_call_function_single() 向 CPU 傳送 IPI，該 IPI 由 rcu_exp_handler() 處理。
但是，由於這是可搶佔的 RCU，rcu_exp_handler() 可以檢查 CPU 當前是否在 RCU 讀取側臨界區中執行。如果不是，則處理程式可以立即報告靜止狀態。否則，它會設定標誌，以便最外層的 rcu_read_unlock() 呼叫將提供所需的靜止狀態報告。此標誌設定避免了先前強制搶佔所有可能具有 RCU 讀取側臨界區的 CPU。此外，完成此標誌設定是為了避免增加透過排程程式的常見情況快速路徑的開銷。
同樣因為這是可搶佔的 RCU，所以可以搶佔 RCU 讀取側臨界區。發生這種情況時，RCU 將使任務入隊，該任務將繼續阻止當前加速寬限期，直到它恢復並找到其最外層的 rcu_read_unlock()。CPU 將在使任務入隊後立即報告靜止狀態，因為 CPU 不再阻止寬限期。而是被搶佔的任務在進行阻止。rcu_preempt_ctxt_queue() 管理被阻止的任務列表，該佇列從 rcu_preempt_note_context_switch() 呼叫，而 rcu_preempt_note_context_switch() 又從 rcu_note_context_switch() 呼叫，而 rcu_note_context_switch() 又從排程程式呼叫。
快速問答: |
為什麼不直接讓加速寬限期檢查所有 CPU 的狀態？畢竟，這將避免所有這些對即時不友好的 IPI。 |
答案: |
因為我們希望 RCU 讀取側臨界區執行速度快，這意味著沒有記憶體屏障。因此，無法安全地從其他 CPU 檢查狀態。即使可以安全地檢查狀態，仍然需要 IPI CPU 以安全地與即將到來的 防止即時應用程式受到這些 IPI 影響的一種方法是使用 |
請注意，這只是總體流程：由於與 CPU 進入空閒或離線狀態的競爭，可能會出現其他複雜情況。
RCU-sched 加速寬限期¶
CONFIG_PREEMPTION=n 核心實現 RCU-sched。以下圖顯示了 RCU-sched 加速寬限期處理給定 CPU 的總體流程
與 RCU-preempt 一樣，RCU-sched 的 synchronize_rcu_expedited() 會忽略離線和空閒 CPU，同樣是因為它們處於遠端可檢測的靜止狀態。但是，由於 rcu_read_lock_sched() 和 rcu_read_unlock_sched() 沒有留下其呼叫的任何痕跡，因此通常無法判斷當前 CPU 是否在 RCU 讀取側臨界區中。RCU-sched 的 rcu_exp_handler() 可以做的最好的事情是檢查是否空閒，以防萬一 CPU 在 IPI 處於飛行狀態時進入空閒狀態。如果 CPU 處於空閒狀態，則 rcu_exp_handler() 會報告靜止狀態。
否則，處理程式透過設定當前任務的執行緒標誌和 CPU 搶佔計數器的 NEED_RESCHED 標誌來強制執行未來的上下文切換。在上下文切換時，CPU 會報告靜止狀態。如果 CPU 首先離線，則它會在此時報告靜止狀態。
加速寬限期和 CPU 熱插拔¶
加速寬限期的加速性質需要與 CPU 熱插拔操作進行比普通寬限期更緊密的互動。此外，嘗試 IPI 離線 CPU 將導致 splat，但未能 IPI 線上 CPU 可能會導致寬限期太短。在生產核心中，這兩種選擇都是不可接受的。
加速寬限期和 CPU 熱插拔操作之間的互動在幾個級別上進行
曾經線上的 CPU 數量由
rcu_state結構的->ncpus欄位跟蹤。rcu_state結構的->ncpus_snap欄位跟蹤在 RCU 加速寬限期開始時曾經線上的 CPU 數量。請注意，至少在沒有時間機器的情況下，此數字永遠不會減少。曾經線上的 CPU 的身份由
rcu_node結構的->expmaskinitnext欄位跟蹤。rcu_node結構的->expmaskinit欄位跟蹤在最近 RCU 加速寬限期開始時至少線上一次的 CPU 的身份。rcu_state結構的->ncpus和->ncpus_snap欄位用於檢測何時首次有新的 CPU 上線，也就是說，當rcu_node結構的->expmaskinitnext欄位自上次 RCU 加速寬限期開始以來已更改時，這會觸發從其->expmaskinitnext欄位更新每個rcu_node結構的->expmaskinit欄位。每個
rcu_node結構的->expmaskinit欄位用於在每個 RCU 加速寬限期開始時初始化該結構的->expmask。這意味著只有至少線上一次的 CPU 才會被考慮用於給定的寬限期。任何離線的 CPU 都會清除其葉
rcu_node結構的->qsmaskinitnext欄位中的位，因此可以安全地忽略任何該位已清除的 CPU。但是，當cpu_online返回false時，上線或離線的 CPU 可能會在一段時間內設定此位。對於 RCU 認為當前線上的每個非空閒 CPU，寬限期會呼叫
smp_call_function_single()。如果成功，則 CPU 完全線上。失敗表示 CPU 正在上線或離線過程中，在這種情況下，需要等待一小段時間並重試。此等待（或一系列等待，視情況而定）的目的是允許併發的 CPU 熱插拔操作完成。對於 RCU-sched，傳出 CPU 的最後一個動作之一是呼叫
rcutree_report_cpu_dead()，這會報告該 CPU 的靜止狀態。但是，這可能是偏執引起的冗餘。
快速問答: |
為什麼所有人都圍繞著跟蹤曾經線上的 CPU 的多個計數器和掩碼跳舞？為什麼不只有一個跟蹤當前線上 CPU 的掩碼集並完成它？ |
答案: |
維護跟蹤線上 CPU 的單個掩碼集聽起來更容易，至少在您嘗試解決寬限期初始化和 CPU 熱插拔操作之間的所有競爭條件之前。例如，假設初始化正在向下遍歷樹，而 CPU 離線操作正在向上遍歷樹。這種情況可能會導致樹頂端設定的位在樹底端沒有對應項。這些位永遠不會被清除，這將導致寬限期掛起。簡而言之，這種方式會導致瘋狂，更不用說許多錯誤、掛起和死鎖。相比之下，當前的多掩碼多計數器方案可確保寬限期初始化始終會在樹的上下看到一致的掩碼，這比單掩碼方法帶來了顯著的簡化。 這是 推遲工作以避免同步 的一個例項。在下一個寬限期開始時延遲記錄 CPU 熱插拔事件極大地簡化了 |
加速寬限期最佳化¶
空閒 CPU 檢查¶
每個加速寬限期在最初形成要 IPIed 的 CPU 掩碼時以及在 IPIing CPU 之前再次檢查空閒 CPU（這兩個檢查都由 sync_rcu_exp_select_cpus() 執行）。如果在這兩個時間之間的任何時間 CPU 處於空閒狀態，則不會 IPI 該 CPU。相反，推動寬限期前進的任務會將空閒 CPU 包含在傳遞給 rcu_report_exp_cpu_mult() 的掩碼中。
對於 RCU-sched，還有一個額外的檢查：如果 IPI 中斷了空閒迴圈，則 rcu_exp_handler() 呼叫 rcu_report_exp_rdp() 來報告相應的靜止狀態。
對於 RCU-preempt，IPI 處理程式 (rcu_exp_handler()) 中沒有針對空閒的特定檢查，但是由於不允許在空閒迴圈中進行 RCU 讀取側臨界區，因此如果 rcu_exp_handler() 看到 CPU 位於 RCU 讀取側臨界區內，則 CPU 不可能處於空閒狀態。否則，rcu_exp_handler() 呼叫 rcu_report_exp_rdp() 來報告相應的靜止狀態，無論該靜止狀態是否是由於 CPU 處於空閒狀態而引起的。
總之，RCU 加速寬限期在構建必須 IPIed 的 CPU 位掩碼時、在傳送每個 IPI 之前以及（顯式或隱式地）在 IPI 處理程式中檢查空閒狀態。
透過序列計數器進行批處理¶
如果每個寬限期請求都單獨執行，則加速寬限期將具有極差的可擴充套件性和有問題的高負載特性。由於每個寬限期操作都可以服務於無限數量的更新，因此批處理請求非常重要，以便單個加速寬限期操作可以涵蓋相應批處理中的所有請求。
此批處理由 rcu_state 結構中名為 ->expedited_sequence 的序列計數器控制。當正在進行加速寬限期時，此計數器具有奇數值，否則具有偶數值，因此將計數器值除以 2 可以得出已完成寬限期的數量。在任何給定的更新請求期間，計數器必須從偶數轉換為奇數，然後再轉換回偶數，從而表明寬限期已過去。因此，如果計數器的初始值為 s，則更新程式必須等到計數器至少達到 (s+3)&~0x1 的值。此計數器由以下訪問函式管理
rcu_exp_gp_seq_start()，用於標記加速寬限期的開始。rcu_exp_gp_seq_end()，用於標記加速寬限期的結束。rcu_exp_gp_seq_snap()，用於獲取計數器的快照。rcu_exp_gp_seq_done()，如果自上次呼叫rcu_exp_gp_seq_snap()以來已經過去了完整的加速寬限期，則返回true。
同樣，給定批處理中只有一個請求需要實際執行寬限期操作，這意味著必須有一種有效的方法來識別許多併發請求中的哪個將啟動寬限期，並且必須有一種有效的方法供其餘請求等待該寬限期完成。但是，這是下一節的主題。
漏斗鎖定和等待/喚醒¶
對一批更新程式中的哪個將啟動加速寬限期進行排序的自然方法是使用 rcu_node 組合樹，如 exp_funnel_lock() 函式所實現的那樣。與給定寬限期相對應的第一個到達給定 rcu_node 結構的更新程式會在 ->exp_seq_rq 欄位中記錄其所需的寬限期序列號，並向上移動到樹中的下一層。否則，如果 ->exp_seq_rq 欄位已包含所需寬限期或稍後寬限期的序列號，則更新程式會在 ->exp_wq[] 陣列中的四個等待佇列之一上阻塞，使用從下往上數第二個和第三個位作為索引。rcu_node 結構中的 ->exp_lock 欄位會同步對這些欄位的訪問。
下圖顯示了一個空的 rcu_node 樹，其中白色單元格表示 ->exp_seq_rq 欄位，紅色單元格表示 ->exp_wq[] 陣列的元素。
下圖顯示了 Task A 和 Task B 分別到達最左側和最右側的葉 rcu_node 結構之後的情況。 rcu_state 結構的 ->expedited_sequence 欄位的當前值為零，因此新增 3 並清除底部位會導致值為 2，這兩個任務都會將其記錄在其各自 rcu_node 結構的 ->exp_seq_rq 欄位中
Task A 和 Task B 將向上移動到根 rcu_node 結構。假設 Task A 獲勝，記錄其所需的寬限期序列號，從而導致以下狀態
Task A 現在前進以啟動一個新的寬限期，而 Task B 向上移動到根 rcu_node 結構，並且看到其所需的序列號已記錄，因此在 ->exp_wq[1] 上阻塞。
快速問答: |
為什麼是 |
答案: |
否。回想一下，所需的序列號的底部位指示當前是否正在進行寬限期。因此，有必要將序列號向右移動一位以獲取寬限期的編號。這會導致 |
如果 Task C 和 Task D 也在此處到達，它們將計算出相同的所需寬限期序列號，並看到兩個葉 rcu_node 結構都已記錄該值。因此，它們將在其各自 rcu_node 結構的 ->exp_wq[1] 欄位上阻塞，如下所示
Task A 現在獲取 rcu_state 結構的 ->exp_mutex 並啟動寬限期，這會遞增 ->expedited_sequence。因此，如果 Task E 和 Task F 到達，它們將計算出所需的序列號為 4，並將該值記錄如下所示
Task E 和 Task F 將傳播到 rcu_node 組合樹，其中 Task F 在根 rcu_node 結構上阻塞，Task E 等待 Task A 完成，以便它可以啟動下一個寬限期。結果狀態如下所示
寬限期完成後，Task A 開始喚醒等待此寬限期完成的任務，遞增 ->expedited_sequence，獲取 ->exp_wake_mutex，然後釋放 ->exp_mutex。這會導致以下狀態
然後，Task E 可以獲取 ->exp_mutex 並將 ->expedited_sequence 遞增到值 3。如果新任務 G 和 H 到達並同時向上移動組合樹，則狀態將如下所示
請注意，根 rcu_node 結構的等待佇列中現在有三個被佔用。但是，在某個時候，Task A 會喚醒在 ->exp_wq 等待佇列上阻塞的任務，從而導致以下狀態
執行將繼續，Task E 和 Task H 完成其寬限期並執行其喚醒。
快速問答: |
如果 Task A 花費太長時間進行喚醒，導致 Task E 的寬限期完成，會發生什麼情況？ |
答案: |
然後，Task E 將在 |
工作佇列的使用¶
在早期的實現中，請求加速寬限期的任務也驅動它完成。這種直接的方法的缺點是需要考慮傳送給使用者任務的 POSIX 訊號，因此最近的實現使用 Linux 核心的工作佇列（參見 工作佇列）。
請求任務仍然進行計數器快照和漏斗鎖定處理，但是到達漏斗鎖定頂端的任務會執行 schedule_work()（來自 _synchronize_rcu_expedited()），以便工作佇列 kthread 進行實際的寬限期處理。由於工作佇列 kthread 不接受 POSIX 訊號，因此寬限期等待處理不需要允許 POSIX 訊號。此外，這種方法允許將先前加速寬限期的喚醒與下一個加速寬限期的處理重疊。由於只有四組等待佇列，因此有必要確保在上一個寬限期的喚醒開始之前完成。這是透過讓 ->exp_mutex 保護加速寬限期處理和 ->exp_wake_mutex 保護喚醒來處理的。關鍵點是 ->exp_mutex 在第一次喚醒完成之前不會釋放，這意味著 ->exp_wake_mutex 此時已經獲取。這種方法可確保在當前寬限期正在進行時可以執行上一個寬限期的喚醒，但是在下一個寬限期開始之前，這些喚醒將完成。這意味著只需要三個等待佇列，從而保證提供的四個是足夠的。
停頓警告¶
當 RCU 讀取器花費太長時間時，加速寬限期不會加速任何操作，因此加速寬限期會像普通寬限期一樣檢查停頓。
快速問答: |
但是，為什麼不讓普通的寬限期機制檢測停頓，因為給定的讀取器必須同時阻止普通和加速寬限期？ |
答案: |
因為很可能在給定時間沒有正在進行的普通寬限期，在這種情況下，普通寬限期無法發出停頓警告。 |
synchronize_sched_expedited_wait() 函式迴圈等待加速寬限期結束，但超時設定為當前的 RCU CPU 停頓警告時間。如果超過此時間，則會列印任何阻止當前寬限期的 CPU 或 rcu_node 結構。每個停頓警告都會導致再次透過迴圈，但是第二個和後續的透過使用更長的停頓時間。
啟動中操作¶
使用工作佇列的優點是加速寬限期程式碼無需擔心 POSIX 訊號。不幸的是，它也有相應的缺點，即在初始化工作佇列之前無法使用工作佇列，這直到排程程式生成第一個任務後一段時間才會發生。鑑於核心的某些部分確實希望在此啟動中“死區”期間執行寬限期，因此加速寬限期必須在此期間執行其他操作。
他們所做的是恢復到舊的做法，即要求請求任務驅動加速寬限期，就像在使用工作佇列之前一樣。然而，請求任務僅需要在啟動中期的死區期間驅動寬限期。在啟動中期之前，同步寬限期是一個空操作。在啟動中期之後的某個時間，將使用工作佇列。
非加速的非SRCU同步寬限期也必須在啟動中期正常執行。這是透過使非加速寬限期在啟動中期採用加速程式碼路徑來處理的。
當前程式碼假設在啟動中期的死區期間沒有POSIX訊號。然而，如果對POSIX訊號的需求非常強烈，可以對加速停頓警告程式碼進行適當的調整。一種這樣的調整是恢復工作佇列之前的停頓警告檢查，但僅在啟動中期的死區期間。
透過這種改進，同步寬限期現在幾乎可以在核心生命週期的任何時間從任務上下文中使用。也就是說，除了暫停、休眠或關閉程式碼路徑中的某些點之外。
總結¶
加速寬限期使用序列號方法來促進批處理，以便單個寬限期操作可以服務於許多請求。漏斗鎖用於有效地識別併發組中將請求寬限期的一個任務。該組的所有成員都將阻塞在 rcu_node 結構中提供的等待佇列上。實際的寬限期處理由工作佇列執行。
CPU熱插拔操作被延遲記錄，以防止加速寬限期和CPU熱插拔操作之間需要緊密同步。dyntick-idle計數器用於避免向空閒CPU傳送IPI（程序間中斷），至少在常見情況下是這樣。RCU-preempt 和 RCU-sched 使用不同的 IPI 處理程式和不同的程式碼來響應這些處理程式執行的狀態更改，但在其他方面使用通用程式碼。
靜止狀態使用 rcu_node 樹進行跟蹤，一旦報告了所有必要的靜止狀態，則會喚醒所有等待此加速寬限期的任務。使用一對互斥鎖允許一個寬限期的喚醒與下一個寬限期的處理同時進行。
這種機制組合允許加速寬限期相當有效地執行。但是，對於非時間關鍵型任務，應使用正常的寬限期，因為它們的持續時間更長，可以實現更高的批處理程度，從而降低每個請求的開銷。