1. Linux中的RCU機制[二] - GP的處理
Linux中的RCU機制[一] - 原理與使用方法
說明：由於現代 RCU 的實現已非常復雜，本文將基於 Linux 2.5.43 版本來解釋 RCU 的基本概念與使用方法，同時也會涉及一些現代 RCU 的特性。
GP 的生命周期
RCU 的 Grace Period（GP）從產生到結束的生命周期如下：GP 由 writer 的 CPU 發起，發生在 writer 調用 synchronize_rcu()/call_rcu() 的時刻，表示准備釋放一個 object 的時候。釋放的具體操作（callback）被填入 object 的 "rcu_head" 中，然後加入到待執行的鏈表中。"rcu_head" 主要用於攜帶 callback 信息，類似於 "list_head"。
何時開始與何時結束
GP 開始於 writer 發起釋放 object 的操作，結束條件取決於 CPU 的狀態。在默認的 non-preemptible 的 RCU 中，reader 所在的 CPU 上的調度在進入臨界區時關閉，直到退出後重新打開。除非涉及 SRCU 的情況，臨界區內的代碼不能睡眠或阻塞，因此不會發生線程切換。
判斷退出臨界區
當 CPU 開始執行其他任務，說明發生了線程切換，意味著該 CPU 已退出臨界區。在 tick 中斷時，如果 CPU 在 userspace 執行代碼，同樣可以判斷臨界區已退出。處於 idle loop 中的 CPU 也可作為判斷依據，雖然代碼做了裁剪，未加入 interrupt context 的判斷。
判斷退出的機制
在 tasklet 的執行函數中，通過比較 "qsctr" 的變化來判斷是否退出了臨界區。"qsctr" 是 QS 的計數，從 reader 退出臨界區開始，到可以判定離開臨界區的這段時間，被稱為 "Quiescent State"（QS）。
QS 與 GP
QS 是 CPU 私有的，而 GP 是全局的，類似於「一票否決制」。當所有 CPU 都進入 QS，GP 才能結束。分配 bitmap 用於標記每個 CPU 的狀態，GP 開始後將所有 bit 置 1，一個 CPU 進入 QS 後，將其對應的 bit 清零。所有 bits 都被置 0 後，就可以判斷 GP 的結束。
存在的問題與解決方案
多個 CPU 同時操作 bitmap 的問題需要使用 spinlock 來保護。對於 CPU 數量較多的情況，採用層級管理結構，每個 CPU 向 "rcu_node" 的 leader 匯報 QS 標記狀態，增強了系統的擴展性。
為什麼 writer 側的 callback 需要 per-cpu 的鏈表？
同一個 writer 可能發起多個 object 的 GP，因此採用鏈表排隊，並且鏈表是 per-cpu 的。即使在 GP 之間，一個 writer 可能同時處理多個 callback，直到所有 GP 的 CPU 都進入 QS，這些 GP 的 callback 才能一起執行。
RCU 的優勢與問題
RCU 的基本流程介紹完畢，下文將探討 RCU 的優勢、問題以及衍生品種 SRCU。
注-1：Tree RCU 的實現沒有採用 rbtree 或者 radix tree，而是通過數組與指針連接形成邏輯上的樹形關系，同時實現廣度優先遍歷。
注-2：郭大俠的講解深入淺出，讓一些難以理解的 Linux 內核細節變得清晰，實屬難得。