什麼是 RCU？ -- “讀取、複製、更新”¶
請注意，“什麼是 RCU？” LWN 系列是開始學習 RCU 的絕佳起點
對於那些喜歡影片的人
什麼是 RCU？
RCU 是一種同步機制，在 2.5 開發工作中新增到 Linux 核心中，專門為讀取較多的情況進行了最佳化。 雖然 RCU 實際上非常簡單，但有效使用它需要您以不同的方式思考您的程式碼。 問題的另一部分是錯誤地假設描述和使用 RCU 存在“一種真正的方法”。 相反，經驗表明，不同的人必須採取不同的路徑才能理解 RCU，這取決於他們的經驗和用例。 本文件提供了幾種不同的路徑，如下所示
喜歡從概念概述開始的人應該關注第 1 節，儘管大多數讀者在某個時候閱讀本節都會有所收穫。 喜歡從可以實驗的 API 開始的人應該關注第 2 節。 喜歡從示例用法開始的人應該關注第 3 節和第 4 節。 需要了解 RCU 實現的人應該關注第 5 節，然後深入研究核心原始碼。 擅長類比推理的人應該關注第 6 節和第 7 節。第 8 節充當 docbook API 文件的索引，第 9 節是傳統的答案金鑰。
因此，從對您和您喜歡的學習方法最有意義的部分開始。 如果您需要了解一切，請隨意閱讀全文——但如果您真的是那種人，您就已經仔細閱讀了原始碼，因此無論如何都不需要本文件。 ;-)
1. RCU 概述¶
RCU 背後的基本思想是將更新分為“刪除”和“回收”階段。 刪除階段刪除資料結構中對資料項的引用（可能透過將它們替換為對這些資料項的新版本的引用），並且可以與讀取器同時執行。 與讀取器同時執行刪除階段是安全的，原因是現代 CPU 的語義保證讀取器將看到資料結構的舊版本或新版本，而不是部分更新的引用。 回收階段完成回收（例如，釋放）在刪除階段從資料結構中刪除的資料項的工作。 因為回收資料項可能會中斷同時引用這些資料項的任何讀取器，所以回收階段必須在讀取器不再持有對這些資料項的引用之後才能開始。
將更新分為刪除和回收階段允許更新器立即執行刪除階段，並將回收階段推遲到在刪除階段處於活動狀態的所有讀取器完成之後，可以透過阻塞直到它們完成或透過註冊在它們完成後呼叫的回撥來完成。 只需要考慮在刪除階段處於活動狀態的讀取器，因為在刪除階段之後啟動的任何讀取器都無法獲得對已刪除資料項的引用，因此不會被回收階段中斷。
因此，典型的 RCU 更新序列如下
刪除指向資料結構的指標，以便後續讀取器無法獲得對其的引用。
等待所有先前的讀取器完成其 RCU 讀取端臨界區。
此時，不能有任何讀取器持有對資料結構的引用，因此現在可以安全地回收它（例如，
kfree()d）。
上面的步驟 (b) 是 RCU 延遲銷燬的基礎關鍵思想。 等待直到所有讀取器完成的能力允許 RCU 讀取器使用更輕量級的同步，在某些情況下，根本不需要同步。 相比之下，在更傳統的基於鎖的方案中，讀取器必須使用重量級同步，以防止更新器在它們不知情的情況下刪除資料結構。 這是因為基於鎖的更新器通常就地更新資料項，因此必須排除讀取器。 相比之下，基於 RCU 的更新器通常會利用以下事實：對單個對齊指標的寫入在現代 CPU 上是原子的，允許原子插入、刪除和替換連結結構中的資料項，而不會中斷讀取器。 併發的 RCU 讀取器可以繼續訪問舊版本，並且可以避免原子操作、記憶體屏障和通訊快取未命中，即使在沒有鎖競爭的情況下，這些操作在當今的 SMP 計算機系統中也非常昂貴。
在上面顯示的三步過程中，更新器正在執行刪除和回收步驟，但是通常由一個完全不同的執行緒來執行回收，就像 Linux 核心的目錄條目快取 (dcache) 中的情況一樣。 即使同一個執行緒執行更新步驟（上面的步驟 (a)）和回收步驟（上面的步驟 (c)），將它們分開考慮通常也很有幫助。 例如，RCU 讀取器和更新器不需要進行任何通訊，但 RCU 在讀取器和回收器之間提供隱式的低開銷通訊，即在上面的步驟 (b) 中。
那麼，鑑於讀取器沒有執行任何型別的同步操作，回收器到底如何判斷讀取器何時完成呢？ 繼續閱讀以瞭解 RCU 的 API 如何使這變得容易。
2. RCU 的核心 API 是什麼？¶
核心 RCU API 非常小
RCU API 還有許多其他成員，但其餘成員可以用這五個來表示，儘管大多數實現而是用 call_rcu() 回撥 API 來表示 synchronize_rcu()。
下面描述了五個核心 RCU API，其餘 18 個將在後面列舉。 有關更多資訊，請參閱核心 docbook 文件，或直接檢視函式頭註釋。
rcu_read_lock()¶
void rcu_read_lock(void);
讀取器使用此時間原語來通知回收器該讀取器正在進入 RCU 讀取端臨界區。 在 RCU 讀取端臨界區中阻塞是非法的，儘管使用 CONFIG_PREEMPT_RCU 構建的核心可以搶佔 RCU 讀取端臨界區。 在 RCU 讀取端臨界區期間訪問的任何受 RCU 保護的資料結構都保證在該臨界區的整個持續時間內保持未回收。 引用計數可以與 RCU 結合使用，以維護對資料結構的長期引用。
請注意，任何停用 bottom halves、搶佔或中斷的操作也會進入 RCU 讀取端臨界區。 獲取自旋鎖也會進入 RCU 讀取端臨界區，即使對於不停用搶佔的自旋鎖也是如此，如使用 CONFIG_PREEMPT_RT=y 構建的核心中的情況。 Sleeplocks *不*進入 RCU 讀取端臨界區。
rcu_read_unlock()¶
void rcu_read_unlock(void);
讀取器使用此時間原語來通知回收器該讀取器正在退出 RCU 讀取端臨界區。 任何啟用 bottom halves、搶佔或中斷的操作也會退出 RCU 讀取端臨界區。 釋放自旋鎖也會退出 RCU 讀取端臨界區。
請注意，RCU 讀取端臨界區可以巢狀和/或重疊。
synchronize_rcu()¶
void synchronize_rcu(void);
此時間原語標記更新器程式碼的結尾和回收器程式碼的開始。 它透過阻塞直到所有 CPU 上所有先前存在的 RCU 讀取端臨界區都已完成來實現此目的。 請注意，
synchronize_rcu()*不*一定等待任何後續的 RCU 讀取端臨界區完成。 例如，考慮以下事件序列CPU 0 CPU 1 CPU 2 ----------------- ------------------------- --------------- 1. rcu_read_lock() 2. enters synchronize_rcu() 3. rcu_read_lock() 4. rcu_read_unlock() 5. exits synchronize_rcu() 6. rcu_read_unlock()重申一下，
synchronize_rcu()僅等待正在進行的 RCU 讀取端臨界區完成，不一定等待在呼叫synchronize_rcu()之後開始的任何臨界區。當然，
synchronize_rcu()不一定在最後一個先前存在的 RCU 讀取端臨界區完成後*立即*返回。 一方面，可能會有排程延遲。 另一方面，許多 RCU 實現會批次處理請求以提高效率，這可能會進一步延遲synchronize_rcu()。由於
synchronize_rcu()是必須確定讀取器何時完成的 API，因此其實現是 RCU 的關鍵。 為了使 RCU 在除了讀取密集型情況之外的所有情況中都有用，synchronize_rcu()的開銷也必須非常小。
call_rcu()API 是synchronize_rcu()的非同步回撥形式，並在後面的章節中更詳細地描述。 它不是阻塞，而是註冊一個函式和引數，在所有正在進行的 RCU 讀取端臨界區完成後呼叫。 這種回撥變體在無法阻塞或更新端效能至關重要的情況下特別有用。但是，不應輕易使用
call_rcu()API，因為使用synchronize_rcu()API 通常會導致更簡單的程式碼。 此外，synchronize_rcu()API 具有自動限制更新速率的良好特性，以防寬限期延遲。 面對拒絕服務攻擊，此屬性會產生系統彈性。 使用call_rcu()的程式碼應限制更新速率，以便獲得相同型別的彈性。 請參閱 RCU 補丁的稽核清單，瞭解限制更新速率的一些方法。
rcu_assign_pointer()¶
void rcu_assign_pointer(p, typeof(p) v);
是的，
rcu_assign_pointer()*是*作為宏實現的，儘管能夠以這種方式宣告函式會很酷。 （並且已經有一些關於向 C 語言新增過載函式的討論，所以誰知道呢？）更新器使用此空間宏為受 RCU 保護的指標分配一個新值，以便安全地將值的更改從更新器傳達給讀取器。 這是一個空間（而不是時間）宏。 它不會評估為 rvalue，但它確實提供了給定編譯或 CPU 架構所需的任何編譯器指令和記憶體屏障指令。 它的排序屬性是儲存-釋放操作，也就是說，初始化結構所需的任何先前的載入和儲存操作都在儲存操作之前排序，該儲存操作釋出指向該結構的指標。
也許同樣重要的是，
rcu_assign_pointer()用於記錄 (1) 哪些指標受 RCU 保護，以及 (2) 給定結構變得可供其他 CPU 訪問的點。 也就是說，rcu_assign_pointer()最常間接使用，透過 _rcu 列表操作原語，例如list_add_rcu()。
rcu_dereference()¶
typeof(p) rcu_dereference(p);
與
rcu_assign_pointer()一樣，rcu_dereference()必須作為宏實現。讀取器使用空間
rcu_dereference()宏來獲取受 RCU 保護的指標，該指標返回一個可以安全地取消引用的值。 請注意，rcu_dereference()實際上並不取消引用指標，而是保護指標以供以後取消引用。 它還執行給定 CPU 架構所需的任何記憶體屏障指令。 目前，只有 Alpha 需要在rcu_dereference()中使用記憶體屏障——在其他 CPU 上，它會編譯為易失性載入。 但是，沒有主流的 C 編譯器尊重地址依賴性，因此rcu_dereference()使用易失性轉換，結合 正確處理來自 rcu_dereference() 的返回值 中列出的編碼指南，可以防止當前的編譯器破壞這些依賴性。常見的編碼實踐使用
rcu_dereference()將受 RCU 保護的指標複製到區域性變數，然後取消引用此區域性變數，例如，如下所示p = rcu_dereference(head.next); return p->data;但是，在這種情況下，人們可以很容易地將這些組合成一個語句
return rcu_dereference(head.next)->data;如果要從受 RCU 保護的結構中獲取多個欄位，則當然首選使用區域性變數。 重複的
rcu_dereference()呼叫看起來很醜陋，不能保證如果在臨界區中發生更新會返回相同的指標，並且會在 Alpha CPU 上產生不必要的開銷。請注意，
rcu_dereference()返回的值僅在封閉的 RCU 讀取端臨界區中有效 [1]。 例如，以下程式碼 *不是*合法的rcu_read_lock(); p = rcu_dereference(head.next); rcu_read_unlock(); x = p->address; /* BUG!!! */ rcu_read_lock(); y = p->data; /* BUG!!! */ rcu_read_unlock();將一個 RCU 讀取端臨界區的引用保持到另一個臨界區是非法的，就像將一個基於鎖的臨界區的引用保持到另一個臨界區一樣！ 同樣，在獲取引用的臨界區之外使用引用也是非法的，就像使用普通鎖一樣。
與
rcu_assign_pointer()一樣，rcu_dereference()的一個重要功能是記錄哪些指標受 RCU 保護，特別是標記一個隨時可能更改的指標，包括在rcu_dereference()之後立即更改。 並且，與rcu_assign_pointer()再次一樣，rcu_dereference()通常是間接使用，透過 _rcu 列表操作原語，例如list_for_each_entry_rcu()[2]。
下圖顯示了每個 API 在讀取器、更新器和回收器之間的通訊方式。
rcu_assign_pointer()
+--------+
+---------------------->| reader |---------+
| +--------+ |
| | |
| | | Protect:
| | | rcu_read_lock()
| | | rcu_read_unlock()
| rcu_dereference() | |
+---------+ | |
| updater |<----------------+ |
+---------+ V
| +-----------+
+----------------------------------->| reclaimer |
+-----------+
Defer:
synchronize_rcu() & call_rcu()
RCU 基礎設施觀察 rcu_read_lock()、 rcu_read_unlock()、 synchronize_rcu() 和 call_rcu() 呼叫的時間順序，以確定何時 (1) synchronize_rcu() 呼叫可以返回給呼叫者，以及 (2) 何時可以呼叫 call_rcu() 回撥。 RCU 基礎設施的高效實現大量使用批處理，以便分攤其在相應 API 的多次使用中的開銷。 rcu_assign_pointer() 和 rcu_dereference() 呼叫透過對 RCU 保護指標的儲存和載入來傳達空間變化。
在 Linux 核心中至少有三種 RCU 用法。 上圖顯示了最常見的用法。 在更新端，rcu_assign_pointer()、synchronize_rcu() 和 call_rcu() 原語對於所有三種用法都是相同的。 然而，對於保護（在讀取端），所使用的原語因用法而異。
rcu_read_lock_bh()/rcu_read_unlock_bh()local_bh_disable() / local_bh_enable()rcu_dereference_bh()rcu_read_lock_sched()/rcu_read_unlock_sched()preempt_disable() / preempt_enable() local_irq_save() / local_irq_restore() hardirq enter / hardirq exit NMI enter / NMI exitrcu_dereference_sched()
這三種用法的使用方式如下：
RCU 應用於正常資料結構。
RCU 應用於可能受到遠端拒絕服務攻擊的網路資料結構。
RCU 應用於排程器和中斷/NMI 處理程式任務。
同樣，大多數使用情況將是 (a)。 (b) 和 (c) 的情況對於專門用途非常重要，但相對不常見。 SRCU、RCU-Tasks、RCU-Tasks-Rude 和 RCU-Tasks-Trace 在其各種原語之間具有類似的關係。
3. 核心 RCU API 的一些示例用法是什麼？¶
本節展示了核心 RCU API 的一個簡單用法，以保護指向動態分配結構的全域性指標。 可以在 使用 RCU 保護讀多寫少連結串列 和 使用 RCU 保護動態 NMI 處理程式 中找到更典型的 RCU 用法。
struct foo {
int a;
char b;
long c;
};
DEFINE_SPINLOCK(foo_mutex);
struct foo __rcu *gbl_foo;
/*
* Create a new struct foo that is the same as the one currently
* pointed to by gbl_foo, except that field "a" is replaced
* with "new_a". Points gbl_foo to the new structure, and
* frees up the old structure after a grace period.
*
* Uses rcu_assign_pointer() to ensure that concurrent readers
* see the initialized version of the new structure.
*
* Uses synchronize_rcu() to ensure that any readers that might
* have references to the old structure complete before freeing
* the old structure.
*/
void foo_update_a(int new_a)
{
struct foo *new_fp;
struct foo *old_fp;
new_fp = kmalloc(sizeof(*new_fp), GFP_KERNEL);
spin_lock(&foo_mutex);
old_fp = rcu_dereference_protected(gbl_foo, lockdep_is_held(&foo_mutex));
*new_fp = *old_fp;
new_fp->a = new_a;
rcu_assign_pointer(gbl_foo, new_fp);
spin_unlock(&foo_mutex);
synchronize_rcu();
kfree(old_fp);
}
/*
* Return the value of field "a" of the current gbl_foo
* structure. Use rcu_read_lock() and rcu_read_unlock()
* to ensure that the structure does not get deleted out
* from under us, and use rcu_dereference() to ensure that
* we see the initialized version of the structure (important
* for DEC Alpha and for people reading the code).
*/
int foo_get_a(void)
{
int retval;
rcu_read_lock();
retval = rcu_dereference(gbl_foo)->a;
rcu_read_unlock();
return retval;
}
所以，總結一下：
使用
rcu_read_lock()和rcu_read_unlock()來保護 RCU 讀取端臨界區。在 RCU 讀取端臨界區內，使用
rcu_dereference()來解引用受 RCU 保護的指標。使用一些可靠的設計（例如鎖或訊號量）來防止併發更新相互干擾。
使用
rcu_assign_pointer()來更新受 RCU 保護的指標。 此原語保護併發讀取器免受更新器的影響，**而不是**併發更新免受彼此的影響！ 因此，您仍然需要使用鎖（或類似的東西）來防止併發的rcu_assign_pointer()原語相互干擾。在從受 RCU 保護的資料結構中刪除資料元素**之後**，但在回收/釋放資料元素**之前**，使用
synchronize_rcu()，以便等待可能引用該資料項的所有 RCU 讀取端臨界區完成。
有關使用 RCU 時要遵循的其他規則，請參見 RCU 補丁的稽核清單。 再次，可以在 使用 RCU 保護讀多寫少連結串列 和 使用 RCU 保護動態 NMI 處理程式 中找到更典型的 RCU 用法。
4. 如果我的更新執行緒無法阻塞怎麼辦？¶
在上面的示例中，foo_update_a() 阻塞直到寬限期過去。 這很簡單，但在某些情況下，您無法承受等待這麼長時間 -- 可能還有其他高優先順序的工作要做。
在這種情況下，您使用 call_rcu() 而不是 synchronize_rcu()。call_rcu() API 如下：
void call_rcu(struct rcu_head *head, rcu_callback_t func);
此函式在寬限期過去後呼叫 func(head)。 此呼叫可能來自軟中斷或程序上下文，因此不允許該函式阻塞。 foo 結構需要新增一個 rcu_head 結構，可能如下所示：
struct foo {
int a;
char b;
long c;
struct rcu_head rcu;
};
然後可以將 foo_update_a() 函式編寫如下：
/*
* Create a new struct foo that is the same as the one currently
* pointed to by gbl_foo, except that field "a" is replaced
* with "new_a". Points gbl_foo to the new structure, and
* frees up the old structure after a grace period.
*
* Uses rcu_assign_pointer() to ensure that concurrent readers
* see the initialized version of the new structure.
*
* Uses call_rcu() to ensure that any readers that might have
* references to the old structure complete before freeing the
* old structure.
*/
void foo_update_a(int new_a)
{
struct foo *new_fp;
struct foo *old_fp;
new_fp = kmalloc(sizeof(*new_fp), GFP_KERNEL);
spin_lock(&foo_mutex);
old_fp = rcu_dereference_protected(gbl_foo, lockdep_is_held(&foo_mutex));
*new_fp = *old_fp;
new_fp->a = new_a;
rcu_assign_pointer(gbl_foo, new_fp);
spin_unlock(&foo_mutex);
call_rcu(&old_fp->rcu, foo_reclaim);
}
foo_reclaim() 函式可能如下所示：
void foo_reclaim(struct rcu_head *rp)
{
struct foo *fp = container_of(rp, struct foo, rcu);
foo_cleanup(fp->a);
kfree(fp);
}
container_of() 原語是一個宏，給定一個指向結構體的指標、結構體的型別以及結構體中指向的欄位，返回一個指向結構體開頭的指標。
使用 call_rcu() 允許 foo_update_a() 的呼叫者立即重新獲得控制權，而無需進一步擔心新更新元素的舊版本。 它還清楚地顯示了 RCU 在更新器（即 foo_update_a()）和回收器（即 foo_reclaim()）之間的區別。
建議的摘要與上一節相同，只是我們現在使用 call_rcu() 而不是 synchronize_rcu()。
在從受 RCU 保護的資料結構中刪除資料元素**之後**，使用
call_rcu()來註冊一個回撥函式，該函式將在可能引用該資料項的所有 RCU 讀取端臨界區完成後呼叫。
如果 call_rcu() 的回撥除了在結構體上呼叫 kfree() 之外什麼都不做，則可以使用 kfree_rcu() 而不是 call_rcu()，以避免必須編寫您自己的回撥。
kfree_rcu(old_fp, rcu);
如果允許偶爾睡眠，則可以使用單引數形式，從 foo 結構體中省略 rcu_head 結構體。
kfree_rcu_mightsleep(old_fp);
此變體幾乎從不阻塞，但可能會透過呼叫 synchronize_rcu() 來響應記憶體分配失敗。
再次，有關管理 RCU 使用的其他規則，請參見 RCU 補丁的稽核清單。
5. RCU 的一些簡單實現是什麼？¶
關於 RCU 的一件好事是，它具有非常簡單的“玩具”實現，這是理解 Linux 核心中生產質量實現的第一步。 本節介紹了 RCU 的兩個此類“玩具”實現，一個是用熟悉的鎖定原語實現的，另一個更類似於“經典” RCU。 兩者都過於簡單，無法在現實世界中使用，既缺乏功能又缺乏效能。 但是，它們有助於瞭解 RCU 的工作原理。 有關生產質量的實現，請參見 kernel/rcu/update.c，並參見
有關描述 Linux 核心 RCU 實現的論文。 OLS'01 和 OLS'02 論文是一個很好的介紹，而論文提供了有關截至 2004 年初的當前實現的更多詳細資訊。
5A. “玩具”實現 #1：鎖定¶
本節介紹了一個基於熟悉的鎖定原語的“玩具” RCU 實現。 它的開銷使其無法用於實際用途，它的可伸縮性也是如此。 它也不適合即時使用，因為它允許排程延遲從一個讀取端臨界區“洩漏”到另一個讀取端臨界區。 它還假設遞迴讀者-寫者鎖：如果您嘗試使用非遞迴鎖，並且允許巢狀的 rcu_read_lock() 呼叫，則可能會發生死鎖。
但是，它可能是最容易理解的實現，因此是一個很好的起點。
它非常簡單
static DEFINE_RWLOCK(rcu_gp_mutex);
void rcu_read_lock(void)
{
read_lock(&rcu_gp_mutex);
}
void rcu_read_unlock(void)
{
read_unlock(&rcu_gp_mutex);
}
void synchronize_rcu(void)
{
write_lock(&rcu_gp_mutex);
smp_mb__after_spinlock();
write_unlock(&rcu_gp_mutex);
}
[您可以忽略 rcu_assign_pointer() 和 rcu_dereference() 而不會錯過太多。 但無論如何，這裡有一些簡化的版本。 無論您做什麼，在提交使用 RCU 的補丁時都不要忘記它們！]
#define rcu_assign_pointer(p, v) \
({ \
smp_store_release(&(p), (v)); \
})
#define rcu_dereference(p) \
({ \
typeof(p) _________p1 = READ_ONCE(p); \
(_________p1); \
})
rcu_read_lock() 和 rcu_read_unlock() 原語讀取獲取和釋放全域性讀者-寫者鎖。synchronize_rcu() 原語寫入獲取此相同的鎖，然後釋放它。 這意味著一旦 synchronize_rcu() 退出，保證在呼叫 synchronize_rcu() 之前正在進行的所有 RCU 讀取端臨界區都已完成 -- synchronize_rcu() 無法以其他方式寫入獲取鎖。 smp_mb__after_spinlock() 按照“記憶體屏障保證”中的列出的，將 synchronize_rcu() 提升為完整的記憶體屏障。
可以巢狀 rcu_read_lock()，因為讀者-寫者鎖可以遞迴獲取。 還要注意，rcu_read_lock() 不受死鎖影響（RCU 的一個重要屬性）。 原因是唯一可以阻塞 rcu_read_lock() 的是 synchronize_rcu()。 但是 synchronize_rcu() 在保持 rcu_gp_mutex 時不獲取任何鎖，因此不會有死鎖迴圈。
- 快速測驗 #1
為什麼這個論點很天真？ 在現實世界的 Linux 核心中使用此演算法時，如何發生死鎖？ 如何避免這種死鎖？
5B. “玩具”示例 #2：經典 RCU¶
本節介紹了一個基於“經典 RCU”的“玩具” RCU 實現。 它也缺乏效能（但僅對於更新）以及諸如熱插拔 CPU 和在 CONFIG_PREEMPTION 核心中執行的能力等功能。rcu_dereference() 和 rcu_assign_pointer() 的定義與上一節中顯示的定義相同，因此省略了它們。
void rcu_read_lock(void) { }
void rcu_read_unlock(void) { }
void synchronize_rcu(void)
{
int cpu;
for_each_possible_cpu(cpu)
run_on(cpu);
}
請注意，rcu_read_lock() 和 rcu_read_unlock() 絕對不執行任何操作。 這是非搶佔核心中經典 RCU 的巨大優勢：讀取端開銷恰好為零，至少在非 Alpha CPU 上是這樣。 並且 rcu_read_lock() 絕對不可能參與死鎖迴圈！
synchronize_rcu() 的實現只是依次在每個 CPU 上排程自身。 run_on() 原語可以使用 sched_setaffinity() 原語直接實現。 當然，一個稍微不那麼“玩具”的實現會在完成後恢復親和性，而不僅僅是將所有任務留在最後一個 CPU 上執行，但是當我說“玩具”時，我的意思是 **玩具**！
那麼這到底應該如何工作？？？
請記住，在 RCU 讀取端臨界區中阻塞是非法的。 因此，如果給定的 CPU 執行上下文切換，我們知道它必須已完成所有先前的 RCU 讀取端臨界區。 一旦 **所有** CPU 都執行了上下文切換，那麼 **所有** 先前的 RCU 讀取端臨界區都將完成。
因此，假設我們從其結構中刪除一個數據項，然後呼叫 synchronize_rcu()。 一旦 synchronize_rcu() 返回，我們保證沒有 RCU 讀取端臨界區持有對該資料項的引用，因此我們可以安全地回收它。
- 快速測驗 #2
給出一個經典 RCU 的讀取端開銷為 **負數** 的示例。
- 快速測驗 #3
如果在 RCU 讀取端臨界區中阻塞是非法的，那麼在 CONFIG_PREEMPT_RT 中該怎麼做呢？在 CONFIG_PREEMPT_RT 中，正常的自旋鎖可能會阻塞！！！
6. 與讀者-寫者鎖的類比¶
雖然 RCU 可以以許多不同的方式使用，但 RCU 的一個非常常見的用法類似於讀者-寫者鎖。 以下統一差異顯示了 RCU 和讀者-寫者鎖之間的密切關係。
@@ -5,5 +5,5 @@ struct el {
int data;
/* Other data fields */
};
-rwlock_t listmutex;
+spinlock_t listmutex;
struct el head;
@@ -13,15 +14,15 @@
struct list_head *lp;
struct el *p;
- read_lock(&listmutex);
- list_for_each_entry(p, head, lp) {
+ rcu_read_lock();
+ list_for_each_entry_rcu(p, head, lp) {
if (p->key == key) {
*result = p->data;
- read_unlock(&listmutex);
+ rcu_read_unlock();
return 1;
}
}
- read_unlock(&listmutex);
+ rcu_read_unlock();
return 0;
}
@@ -29,15 +30,16 @@
{
struct el *p;
- write_lock(&listmutex);
+ spin_lock(&listmutex);
list_for_each_entry(p, head, lp) {
if (p->key == key) {
- list_del(&p->list);
- write_unlock(&listmutex);
+ list_del_rcu(&p->list);
+ spin_unlock(&listmutex);
+ synchronize_rcu();
kfree(p);
return 1;
}
}
- write_unlock(&listmutex);
+ spin_unlock(&listmutex);
return 0;
}
或者，對於那些喜歡並排列表的人：
1 struct el { 1 struct el {
2 struct list_head list; 2 struct list_head list;
3 long key; 3 long key;
4 spinlock_t mutex; 4 spinlock_t mutex;
5 int data; 5 int data;
6 /* Other data fields */ 6 /* Other data fields */
7 }; 7 };
8 rwlock_t listmutex; 8 spinlock_t listmutex;
9 struct el head; 9 struct el head;
1 int search(long key, int *result) 1 int search(long key, int *result)
2 { 2 {
3 struct list_head *lp; 3 struct list_head *lp;
4 struct el *p; 4 struct el *p;
5 5
6 read_lock(&listmutex); 6 rcu_read_lock();
7 list_for_each_entry(p, head, lp) { 7 list_for_each_entry_rcu(p, head, lp) {
8 if (p->key == key) { 8 if (p->key == key) {
9 *result = p->data; 9 *result = p->data;
10 read_unlock(&listmutex); 10 rcu_read_unlock();
11 return 1; 11 return 1;
12 } 12 }
13 } 13 }
14 read_unlock(&listmutex); 14 rcu_read_unlock();
15 return 0; 15 return 0;
16 } 16 }
1 int delete(long key) 1 int delete(long key)
2 { 2 {
3 struct el *p; 3 struct el *p;
4 4
5 write_lock(&listmutex); 5 spin_lock(&listmutex);
6 list_for_each_entry(p, head, lp) { 6 list_for_each_entry(p, head, lp) {
7 if (p->key == key) { 7 if (p->key == key) {
8 list_del(&p->list); 8 list_del_rcu(&p->list);
9 write_unlock(&listmutex); 9 spin_unlock(&listmutex);
10 synchronize_rcu();
10 kfree(p); 11 kfree(p);
11 return 1; 12 return 1;
12 } 13 }
13 } 14 }
14 write_unlock(&listmutex); 15 spin_unlock(&listmutex);
15 return 0; 16 return 0;
16 } 17 }
無論哪種方式，差異都很小。 讀取端鎖定移動到 rcu_read_lock() 和 rcu_read_unlock，更新端鎖定從讀者-寫者鎖移動到簡單的自旋鎖，並且 synchronize_rcu() 先於 kfree()。
但是，有一個潛在的問題：讀取端和更新端臨界區現在可以併發執行。 在許多情況下，這不會成為問題，但無論如何都需要仔細檢查。 例如，如果必須將多個獨立的列表更新視為單個原子更新，則轉換為 RCU 將需要特別小心。
此外，synchronize_rcu() 的存在意味著 delete() 的 RCU 版本現在可以阻塞。 如果這是一個問題，則有一種基於回撥的機制永遠不會阻塞，即 call_rcu() 或 kfree_rcu()，可以用來代替 synchronize_rcu()。
7. 與引用計數的類比¶
讀者-寫者類比（如上一節所示）並非總是考慮使用 RCU 的最佳方式。 另一個有用的類比是將 RCU 視為對受 RCU 保護的所有內容進行有效引用計數。
引用計數通常不會阻止被引用物件的值發生變化，但會阻止型別發生變化 -- 特別是當該物件的記憶體被釋放併為其他目的重新分配時發生的型別上的重大變化。 一旦獲得了對物件的型別安全引用，就需要一些其他機制來確保對物件中資料的一致訪問。 這可能涉及獲取自旋鎖，但使用 RCU，典型的方法是使用感知 SMP 的操作（例如 smp_load_acquire()）執行讀取，使用原子讀取-修改-寫入操作執行更新，並提供必要的排序。 RCU 提供了許多支援函式，這些函式嵌入了所需的操作和排序，例如上一節中使用的 list_for_each_entry_rcu() 宏。
更聚焦於引用計數行為的觀點是，在 rcu_read_lock() 和 rcu_read_unlock() 之間，透過 rcu_dereference() 獲取的對標記為 __rcu 的指標的任何引用，都可以被視為該物件的引用計數已暫時增加。 這可以防止物件更改型別。 這到底意味著什麼將取決於該型別物件的正常預期，但通常包括自旋鎖仍然可以安全地鎖定，正常引用計數器可以安全地操作，並且 __rcu 指標可以安全地解引用。
對持有 RCU 引用的物件，一些預期會執行的操作包括：
複製出保證由物件型別保證穩定的資料。
使用
kref_get_unless_zero()或類似方法獲取更長期的引用。當然，這可能會失敗。獲取物件中的自旋鎖，並檢查該物件是否仍然是預期的物件，如果是，則可以自由地操作它。
理解 RCU 提供的引用僅阻止型別更改這一點，在使用標記為 SLAB_TYPESAFE_BY_RCU 的 slab 快取分配的物件時尤其明顯。 RCU 操作可能會產生對來自此類快取的物件的引用，該物件已被併發釋放，並且記憶體已重新分配給一個完全不同的物件，儘管型別相同。 在這種情況下，RCU 甚至不能保護物件身份不發生改變，只能保護其型別。 因此，找到的物件可能不是預期的物件，但它是一個可以安全地獲取引用（然後可能獲取自旋鎖）的物件，從而允許後續程式碼檢查身份是否符合預期。 很容易在不先獲取引用的情況下直接獲取自旋鎖，但不幸的是，SLAB_TYPESAFE_BY_RCU 物件中的任何自旋鎖都必須在每次呼叫 kmem_cache_alloc() 之後初始化，這使得無引用的自旋鎖獲取完全不安全。 因此，當使用 SLAB_TYPESAFE_BY_RCU 時，請正確使用引用計數器。如果使用 refcount_t，則應使用專門的 refcount_{add|inc}_not_zero_acquire() 和 refcount_set_release() API，以確保在驗證物件身份和初始化新分配的物件時的正確操作順序。 refcount_{add|inc}_not_zero_acquire() 中的 Acquire fence 確保身份檢查在獲取引用計數*之後*發生。 refcount_set_release() 應該在新分配的物件完全初始化後呼叫，並且 release fence 確保新值在其他使用者成功獲取引用計數*之前*可見。 一旦 refcount_set_release() 被呼叫，該物件應被認為對其他任務可見。（那些願意在 kmem_cache 建構函式中初始化其鎖的人也可以使用鎖，包括快取友好的序列鎖。）
對於傳統的引用計數（例如 Linux 中 kref 庫實現的引用計數），通常存在當物件的最後一個引用被刪除時執行的程式碼。 對於 kref，這是傳遞給 kref_put() 的函式。 當使用 RCU 時，只有在所有引用該物件的 __rcu 指標都已更新，並且經過一段寬限期後，才能執行此類終結程式碼。 必須將每個剩餘的全域性可見的物件指標視為潛在的計數引用，並且通常僅在所有這些指標都已更改後，才使用 call_rcu() 執行終結程式碼。
為了瞭解如何在這兩個類比之間進行選擇（將 RCU 視為讀者-寫者鎖，將 RCU 視為引用計數系統），反思受保護事物的規模非常有用。 讀者-寫者鎖的類比著眼於更大的多部分物件，例如連結串列，並展示了當元素被新增到連結串列和從連結串列中刪除時，RCU 如何促進併發。 引用計數的類比著眼於單個物件，並著眼於如何在它們所屬的整體中安全地訪問它們。
8. RCU API 的完整列表¶
RCU API 在 Linux 核心原始碼中以 docbook 格式的頭註釋記錄，但擁有完整的 API 列表會有所幫助，因為似乎沒有辦法在 docbook 中對它們進行分類。 這是按類別劃分的列表。
RCU 列表遍歷
list_entry_rcu
list_entry_lockless
list_first_entry_rcu
list_next_rcu
list_for_each_entry_rcu
list_for_each_entry_continue_rcu
list_for_each_entry_from_rcu
list_first_or_null_rcu
list_next_or_null_rcu
hlist_first_rcu
hlist_next_rcu
hlist_pprev_rcu
hlist_for_each_entry_rcu
hlist_for_each_entry_rcu_bh
hlist_for_each_entry_from_rcu
hlist_for_each_entry_continue_rcu
hlist_for_each_entry_continue_rcu_bh
hlist_nulls_first_rcu
hlist_nulls_for_each_entry_rcu
hlist_bl_first_rcu
hlist_bl_for_each_entry_rcu
RCU 指標/列表更新
rcu_assign_pointer
list_add_rcu
list_add_tail_rcu
list_del_rcu
list_replace_rcu
hlist_add_behind_rcu
hlist_add_before_rcu
hlist_add_head_rcu
hlist_add_tail_rcu
hlist_del_rcu
hlist_del_init_rcu
hlist_replace_rcu
list_splice_init_rcu
list_splice_tail_init_rcu
hlist_nulls_del_init_rcu
hlist_nulls_del_rcu
hlist_nulls_add_head_rcu
hlist_bl_add_head_rcu
hlist_bl_del_init_rcu
hlist_bl_del_rcu
hlist_bl_set_first_rcu
RCU
Critical sections Grace period Barrier
rcu_read_lock synchronize_net rcu_barrier
rcu_read_unlock synchronize_rcu
rcu_dereference synchronize_rcu_expedited
rcu_read_lock_held call_rcu
rcu_dereference_check kfree_rcu
rcu_dereference_protected
bh
Critical sections Grace period Barrier
rcu_read_lock_bh call_rcu rcu_barrier
rcu_read_unlock_bh synchronize_rcu
[local_bh_disable] synchronize_rcu_expedited
[and friends]
rcu_dereference_bh
rcu_dereference_bh_check
rcu_dereference_bh_protected
rcu_read_lock_bh_held
sched
Critical sections Grace period Barrier
rcu_read_lock_sched call_rcu rcu_barrier
rcu_read_unlock_sched synchronize_rcu
[preempt_disable] synchronize_rcu_expedited
[and friends]
rcu_read_lock_sched_notrace
rcu_read_unlock_sched_notrace
rcu_dereference_sched
rcu_dereference_sched_check
rcu_dereference_sched_protected
rcu_read_lock_sched_held
RCU-Tasks
Critical sections Grace period Barrier
N/A call_rcu_tasks rcu_barrier_tasks
synchronize_rcu_tasks
RCU-Tasks-Rude
Critical sections Grace period Barrier
N/A N/A
synchronize_rcu_tasks_rude
RCU-Tasks-Trace
Critical sections Grace period Barrier
rcu_read_lock_trace call_rcu_tasks_trace rcu_barrier_tasks_trace
rcu_read_unlock_trace synchronize_rcu_tasks_trace
SRCU
Critical sections Grace period Barrier
srcu_read_lock call_srcu srcu_barrier
srcu_read_unlock synchronize_srcu
srcu_dereference synchronize_srcu_expedited
srcu_dereference_check
srcu_read_lock_held
SRCU：初始化/清理
DEFINE_SRCU
DEFINE_STATIC_SRCU
init_srcu_struct
cleanup_srcu_struct
全部：lockdep 檢查的 RCU 實用程式 API
RCU_LOCKDEP_WARN
rcu_sleep_check
全部：未檢查的 RCU 保護的指標訪問
rcu_dereference_raw
全部：禁止解引用的未檢查的 RCU 保護的指標訪問
rcu_access_pointer
有關更多資訊，請參見原始碼中的註釋頭（或從中生成的 docbook）。
但是，鑑於 Linux 核心中至少有四個系列的 RCU API，您如何選擇使用哪一個？ 以下列表可能會有所幫助
讀者是否需要阻塞？ 如果是，則需要 SRCU。
讀者是否需要阻塞，並且您是否在進行跟蹤，例如 ftrace 或 BPF？ 如果是，則需要 RCU-tasks、RCU-tasks-rude 和/或 RCU-tasks-trace。
那麼 -rt 補丁集呢？ 如果讀者需要在非 rt 核心中阻塞，則需要 SRCU。 如果讀者在 -rt 核心中獲取自旋鎖時會阻塞，但在非 rt 核心中不會阻塞，則不需要 SRCU。（-rt 補丁集將自旋鎖轉換為睡眠鎖，因此存在這種區別。）
您是否需要將 NMI 處理程式、硬中斷處理程式以及停用搶佔的程式碼段（無論是透過 preempt_disable()、local_irq_save()、local_bh_disable() 還是其他機制）視為顯式 RCU 讀者？ 如果是這樣，RCU-sched 讀者將是唯一可行的選擇，但自從大約 v4.20 以來，您可以使用 vanilla RCU 更新原語。
即使在軟中斷壟斷一個或多個 CPU 的情況下，您是否需要 RCU 寬限期才能完成？ 例如，您的程式碼是否容易受到基於網路的拒絕服務攻擊？ 如果是這樣，您應該停用讀者中的軟中斷，例如，透過使用
rcu_read_lock_bh()。自從大約 v4.20 以來，您可以使用 vanilla RCU 更新原語。您的工作負載對於正常使用 RCU 來說是否更新過於密集，但不適合其他同步機制？ 如果是這樣，請考慮 SLAB_TYPESAFE_BY_RCU（最初命名為 SLAB_DESTROY_BY_RCU）。 但請務必小心！
您是否需要在即使在 CPU 處於空閒迴圈深處、進入或退出使用者模式執行期間或在離線 CPU 上也能受到尊重的讀端臨界區？ 如果是這樣，SRCU 和 RCU Tasks Trace 是唯一可行的選擇，但在幾乎所有情況下都強烈建議使用 SRCU。
否則，請使用 RCU。
當然，這都假設您已經確定 RCU 實際上是您工作的正確工具。
9. 快速測驗的答案¶
- 快速測驗 #1
為什麼這個論點是幼稚的？ 在真實的 Linux 核心中使用此演算法時，如何發生死鎖？ [參考基於鎖的“玩具” RCU 演算法。]
- 答案
考慮以下事件序列
CPU 0 獲取一些不相關的鎖，稱之為“problematic_lock”，透過 spin_lock_irqsave() 停用中斷。
CPU 1 進入
synchronize_rcu()，寫獲取 rcu_gp_mutex。CPU 0 進入
rcu_read_lock()，但必須等待，因為 CPU 1 持有 rcu_gp_mutex。CPU 1 被中斷，中斷處理程式嘗試獲取 problematic_lock。
系統現在死鎖。
避免此死鎖的一種方法是使用類似於 CONFIG_PREEMPT_RT 的方法，其中所有普通自旋鎖都變為阻塞鎖，並且所有中斷處理程式都在特殊任務的上下文中執行。 在這種情況下，在上面的步驟 4 中，中斷處理程式將阻塞，允許 CPU 1 釋放 rcu_gp_mutex，從而避免死鎖。
即使在沒有死鎖的情況下，此 RCU 實現也允許延遲透過
synchronize_rcu()從讀者“傳遞”到其他讀者。 為了看到這一點，請考慮 RCU 讀端臨界區中的任務 A（因此讀持有 rcu_gp_mutex），嘗試寫獲取 rcu_gp_mutex 而阻塞的任務 B，以及嘗試讀獲取 rcu_gp_mutex 而在rcu_read_lock()中阻塞的任務 C。任務 A 的 RCU 讀端延遲正在阻止任務 C，儘管是間接透過任務 B。因此，即時 RCU 實現使用一種基於計數器的方法，其中 RCU 讀端臨界區中的任務不會被執行
synchronize_rcu()的任務阻塞。
- 快速測驗 #2
給出一個經典 RCU 的讀取端開銷為 **負數** 的示例。
- 答案
想象一個單 CPU 系統，該系統具有一個非 CONFIG_PREEMPTION 核心，其中路由表由程序上下文程式碼使用，但可以由中斷上下文程式碼（例如，透過“ICMP REDIRECT”資料包）更新。 處理這種情況的通常方法是讓程序上下文程式碼在搜尋路由表時停用中斷。 使用 RCU 可以省去這種中斷停用。 因此，在沒有 RCU 的情況下，您需要支付停用中斷的成本，而使用 RCU 則不需要。
有人可能會爭辯說，在這種情況下，RCU 的開銷相對於單 CPU 中斷停用方法而言是負的。 其他人可能會爭辯說，RCU 的開銷僅僅為零，並且用零開銷的 RCU 方案替換中斷停用方案的正開銷並不構成負開銷。
當然，在現實生活中，事情要複雜得多。 但是，同步原語的負開銷的理論可能性也是有點出乎意料的。 ;-)
- 快速測驗 #3
如果在 RCU 讀取端臨界區中阻塞是非法的，那麼在 CONFIG_PREEMPT_RT 中該怎麼做呢？在 CONFIG_PREEMPT_RT 中，正常的自旋鎖可能會阻塞！！！
- 答案
正如 CONFIG_PREEMPT_RT 允許搶佔自旋鎖臨界區一樣，它也允許搶佔 RCU 讀端臨界區。 它還允許自旋鎖在 RCU 讀端臨界區中阻塞。
為什麼會出現明顯的不一致？ 因為如果需要（例如，如果記憶體不足），可以使用優先順序提升來縮短 RCU 寬限期。 相比之下，如果阻塞等待（例如）網路接收，則無法知道應該提升什麼。 尤其是考慮到我們需要提升的程序很可能是一個出去吃披薩或什麼的普通人。 儘管計算機操作的電擊棒可能會引起極大的興趣，但也可能會引起嚴重的反對。 此外，計算機如何知道這個人去了哪家披薩店？？？
致謝
感謝幫助使本文更易於理解的人們，包括 Jon Walpole、Josh Triplett、Serge Hallyn、Suzanne Wood 和 Alan Stern。
有關更多資訊，請參見 http://www.rdrop.com/users/paulmck/RCU。