一文帶你深入解析Linux內(nèi)核-RCU機制（超詳細~）
概述
Read-copy update (RCU) 是一種 2002 年 10 月被引入到內(nèi)核當中的同步機制。通過允許在更新的同時讀數(shù)據(jù)，RCU 提高了同步機制的可伸縮性（scalability）。相對于傳統(tǒng)的在并發(fā)線程間不區(qū)分是讀者還是寫者的簡單互斥性鎖機制，或者是哪些允許并發(fā)讀但同時不 允許寫的讀寫鎖，RCU 支持同時一個更新線程和多個讀線程的并發(fā)。RCU 通過保存對象的多個副本來保障讀操作的連續(xù)性，并保證在預定的讀方臨界區(qū)沒有完成之前不會釋放這個對象。RCU定義并使用高效、可伸縮的機制來發(fā)布并讀取 對象的新版本，并延長舊版本們的壽命。這些機制將工作分發(fā)到了讀和更新路徑上，以保證讀路徑可以極快地運行。在某些場合（非搶占內(nèi)核），RCU 的讀方?jīng)]有任何性能負擔。
問題1：seqlock 不是也允許讀線程和更新線程并發(fā)工作么？
這個問題可以歸結(jié)到 “確切地說，什么是RCU？” 這個問題，或許還是 “RCU 可能是如何工作的？” （再或者，不太可能的情況下，問題會變?yōu)槭裁辞闆r下 RCU 不太可能工作）。本文從幾個基本的出發(fā)點來回答這些問題；之后還會分批地從使用的角度和 API 的角度來看這些問題。最后一篇連載還會給出一組參考文獻。
RCU 由三個基本機制組成，第一個用于插入，第二個用于刪除，而第三個則用于讓讀線程可以承受并發(fā)的插入或刪除。這三個機制將在下面的三節(jié)中介紹，講述如何將 RCU 轉(zhuǎn)化為鏈表：
訂閱發(fā)布機制 （用于插入）
等待已有的RCU讀者完成 （用于刪除）
維護多個最近更新的對象的版本 （為讀者維護）
這三個章節(jié)之后還有上重點回顧與快速問題答案。
【文章福利】小編推薦自己的Linux內(nèi)核技術(shù)交流群:【891587639】整理了一些個人覺得比較好的學習書籍、視頻資料共享在群文件里面，有需要的可以自行添加哦！?。。ê曨l教程、電子書、實戰(zhàn)項目及代碼)? ? ?
訂閱發(fā)布機制
RCU的一個關(guān)鍵特性是它可以安全地掃描數(shù)據(jù)，即使數(shù)據(jù)正被同時改寫也沒問題。要提供這種并發(fā)插入的能力，RCU使用了一種訂閱發(fā)布機制。舉例說，考慮一 個被初始化為 NULL 的全局指針變量 gp 將要被修改為新分配并初始化的數(shù)據(jù)結(jié)構(gòu)。下面這段代碼（使用附加的合適的鎖機制）可以用于這個目的：
1 struct foo {
2 int a;
3 int b;
4 int c;
5 };
6 struct foo *gp = NULL;
7
8 /* . . . */
9
10 p = kmalloc(sizeof(*p), GFP_KERNEL);
11 p->a = 1;
12 p->b = 2;
13 p->c = 3;
14 gp = p;不幸的是，沒有方法強制保證編譯器和CPU能順序執(zhí)行最后四條語句。如果gp的賦值早于p的各個域的初始化的話，那么并發(fā)的讀操作將訪問到未初始化的變 量。內(nèi)存屏障（barrier）可以用于保障操作的順序，但內(nèi)存屏障以難以使用而聞名。這樣我們將他們封裝到具有發(fā)布語義的 rcu_assign_pointer() 原語之中。最后的四條將成為這樣：
1 p->a = 1;
2 p->b = 2;
3 p->c = 3;
4 rcu_assign_pointer(gp, p);rcu_assign_pointer() 將會發(fā)布新的結(jié)構(gòu)，強制編譯器和CPU在給p的各個域賦值之后再把指針賦值給gp。然而，僅僅強制更新操作的順序是不夠的，讀者也必須強制使用恰當?shù)捻樞??？紤]下面的這段代碼：
1 p = gp;
2 if (p != NULL) {
3 do_something_with(p->a, p->b, p->c);
4 }盡管這段代碼看起來不會受到順序錯亂的影響，不過十分不幸，DEC Alpha CPU 和投機性編譯器優(yōu)化可能會引發(fā)問題，不論你是否相信，這的確有可能會導致 p->a, p->b, p->c 的讀取會在讀取 p 之前！這種情況在投機性編譯器優(yōu)化的情況中最有可能會出現(xiàn)，編譯器會揣測p的值，取出 p->a, p->b 和 p->c，之后取出 p 的真實值來檢查拽側(cè)的正確性。這種優(yōu)化非常激進，或者說瘋狂，不過在確實會在profile-driven優(yōu)化時發(fā)生。
毫無疑問，我們需要在CPU和編譯器上阻止這種情況的發(fā)生。rcu_dereference() 原語使用了必要的內(nèi)存屏障指令和編譯器指令來達到這一目的：
1 rcu_read_lock();
2 p = rcu_dereference(gp);
3 if (p != NULL) {
4 do_something_with(p->a, p->b, p->c);
5 }
6 rcu_read_unlock();rcu_dereference() 原語可以被看作是訂閱了指針指向的值，保證接下來的取值操作將會看到對應的發(fā)布操作（rcu_assign_pointer()）發(fā)生之前被初始化的值。 rcu_read_lock() 和 rcu_read_unlock() 絕對是必須的：他們定義了 RCU 讀方臨界區(qū)的范圍。他們的目的將在下一節(jié) 解釋，不過，他們不會自旋或阻塞，也不阻止 list_add_rcu() 的并發(fā)執(zhí)行。事實上，對于非搶占內(nèi)核，它們不產(chǎn)生任何代碼。
雖然 rcu_assign_pointer() 和 rcu_dereference() 在理論上可以用于構(gòu)建任意 RCU 保護的數(shù)據(jù)結(jié)構(gòu)，但實際上，使用高層構(gòu)造常常更好。因此，rcu_assign_pointer() 和 rcu_dereference() 原語被嵌入到了 Linux 的鏈表維護 API 中的特殊 RCU 變量之中了。Linux 有兩個雙向鏈表的變種，循環(huán)鏈表 struct list_head 和線性鏈表 struct hlist_head/struct hlist_node。前者的結(jié)構(gòu)如下圖所示，綠色的方塊表示表頭，藍色的是鏈表中的元素。
將上面的指針發(fā)布例子放到鏈表的場景中來就是這樣：
1 struct foo {
2 struct list_head list;
3 int a;
4 int b;
5 int c;
6 };
7 LIST_HEAD(head);
8
9 /* . . . */
10
11 p = kmalloc(sizeof(*p), GFP_KERNEL);
12 p->a = 1;
13 p->b = 2;
14 p->c = 3;
15 list_add_rcu(&p->list, &head);第15行被使用某種同步機制保護住了，通常是某種所，以組織多個 list_add() 實例并發(fā)執(zhí)行。然而，這些同步不能組織同時發(fā)生的RCU讀者。訂閱一個 RCU 保護的鏈表非常直接：
1 rcu_read_lock();
2 list_for_each_entry_rcu(p, head, list) {
3 do_something_with(p->a, p->b, p->c);
4 }
5 rcu_read_unlock();ist_add_rcu() 原語發(fā)布一個節(jié)點到制定的鏈表中去，保證對應的 list_for_each_entry_rcu() 調(diào)用都正確的訂閱到同一個節(jié)點上。
問題2：如果在 list_for_each_entry_rcu() 運行時，剛好進行了一次 list_add_rcu()，如何防止 segfault 的發(fā)生呢？
Linux 中的另一個雙向鏈表，hlist，是一個線性表，也就是說，它的頭部僅需要一個指針，而不是向循環(huán)鏈表一樣需要兩個指針。這樣，使用 hlist 作為大型哈希表的 hash-bucket 數(shù)組的容器將僅消耗一半的內(nèi)存空間。
將一個新元素添加到一個 RCU 保護的 hlist 里面與添加到循環(huán)鏈表里非常類似：
1 struct foo {
2 struct hlist_node *list;
3 int a;
4 int b;
5 int c;
6 };
7 HLIST_HEAD(head);
8
9 /* . . . */
10
11 p = kmalloc(sizeof(*p), GFP_KERNEL);
12 p->a = 1;
13 p->b = 2;
14 p->c = 3;
15 hlist_add_head_rcu(&p->list, &head);和上面一樣，第15行一定使用了鎖或其他某種同步機制。
訂閱一個 RCU 保護的 hlist 也和循環(huán)鏈表非常接近。
1 rcu_read_lock();
2 hlist_for_each_entry_rcu(p, q, head, list) {
3 do_something_with(p->a, p->b, p->c);
4 }
5 rcu_read_unlock();問題3：為什么我們需要傳遞兩個指針給 hlist_for_each_entry_rcu()， list_for_each_entry_rcu() 可是只需要一個指針的啊？
RCU 發(fā)布與訂閱原語在如下表中列出，同時給出了 “取消發(fā)布”或是撤回的原語
類別 發(fā)布 撤銷 訂閱 類別 發(fā)布 撤銷 訂閱 指針
rcu_assign_pointer()
rcu_assign_pointer(…, NULL)
rcu_dereference()循環(huán)鏈表
list_add_rcu()
list_add_tail_rcu()
list_replace_rcu()
list_del_rcu()
list_for_each_entry_rcu()雙向鏈表
hlist_add_after_rcu()
hlist_add_before_rcu()
hlist_add_head_rcu()
hlist_replace_rcu()
hlist_del_rcu()
hlist_for_each_entry_rcu()注意，list_replace_rcu(), list_del_rcu(), hlist_replace_rcu(), 以及 hlist_del_rcu() 增加了一些復雜度。什么時候釋放被替換或刪除掉的數(shù)據(jù)元素才是安全的呢？具體地說，我們怎么能知道所有的讀者都釋放了他們手中對數(shù)據(jù)元素的引用呢？
這些問題將在下面的章節(jié)中得到回答。
等待已經(jīng)存在的RCU讀者完成
RCU的最基本的功能就是等待一些事情的完成。當然，還有很多其他方法也是用于等待事情完成的，包括引用計數(shù)、讀寫鎖、事件等。RCU最大的好處在于它可 以等待所有（比如說）兩萬件不同點事情，而無需顯式地跟蹤它們中的每一個，也不需要擔心性能的下降、可伸縮性限制、復雜度死鎖場景，以及內(nèi)存泄露等所有這 些顯式跟蹤手法所固有的問題。
RCU 中，被等待的東西被叫做“RCU讀方臨界區(qū)”。一個RCU讀方臨界區(qū)始于 rcu_read_lock() 原語，止于 rcu_read_unlock() 原語。RCU 讀方臨界區(qū)可以嵌套，也可以放入很多代碼，只要這些代碼顯式阻塞或睡眠即可（有一種稱為“SRCU”的特殊RCU允許在它的讀方臨界區(qū)中睡眠）。只要你遵守這些約定，你就可以使用RCU來等待任何期望的代碼段的完成。
正如其他地方對經(jīng)典RCU和實時RCU的描述，RCU 通過間接確定這些其他事情的完成時間來達到這一目的。
具體地說，如下圖所示，RCU是一種等待已經(jīng)存在的RCU讀方臨界區(qū)結(jié)束的方法，包括這些臨界區(qū)中執(zhí)行的內(nèi)存操作。
注意，開始于一個給定寬限期開始之后的RCU讀方臨界區(qū)能夠、并可以延續(xù)到該寬限期結(jié)束之后。
下面的偽碼展示了使用RCU等待讀者的基本算法形式：
進行改動，比如，替換鏈表中的一個元素。
等待所有已經(jīng)存在的RCU讀方臨界區(qū)完成（比如，使用synchronize_rcu()原語）。關(guān)鍵點是接下來的RCU讀方臨界區(qū)將無法得到新近刪除的元素的引用了。
清理，比如，釋放上述所有被替換的元素。
下面的代碼段是從前一節(jié)修改而得的，用于說明這一過程，這里面的域a是這個搜索的鍵值。
1 struct foo {
2 struct list_head list;
3 int a;
4 int b;
5 int c;
6 };
7 LIST_HEAD(head);
8
9 /* . . . */
10
11 p = search(head, key);
12 if (p == NULL) {
13 /* Take appropriate action, unlock, and return. */
14 }
15 q = kmalloc(sizeof(*p), GFP_KERNEL);
16 *q = *p;
17 q->b = 2;
18 q->c = 3;
19 list_replace_rcu(&p->list, &q->list);
20 synchronize_rcu();
21 kfree(p);第19、20 和 21 行實現(xiàn)了上面所說的三個步驟。第 16-19行展現(xiàn)了 RCU 的名字（讀-復制-更新）：在允許進行并發(fā)讀操作的同時，第16行進行了復制，而第17-19行進行了更新。
乍一看會覺得 synchronize_rcu() 原語顯得比較神秘。畢竟它必須等所有讀方臨界區(qū)完成，而且，正如我們前面看到的，用于限制RCU讀方臨界區(qū)的rcu_read_lock() 和 rcu_read_unlock() 原語在非搶占內(nèi)核中甚至什么代碼都不會生成。
這里有一個小伎倆，經(jīng)典RCU通過 rcu_read_lock() 和 rcu_read_unlock() 界定的讀方臨界區(qū)是不允許阻塞和休眠的。因此，當一個給定的CPU要進行上下文切換的時候，我們可以確定任何已有的RCU讀方臨界區(qū)都已經(jīng)完成了。也就是說，只要每個CPU都至少進行了一次上下文切換，那么所有先前的 RCU 讀方臨界區(qū)也就保證都完成了，即 synchronize_rcu() 可以安全返回了。
因此，經(jīng)典RCU的 synchronize_rcu() 從概念上說可以被簡化成這樣：
1 for_each_online_cpu(cpu)
2 run_on(cpu);這里，run_on() 將當前線程切換到指定 CPU，來強制該 CPU 進行上下文切換。而 for_each_online_cpu() 循環(huán)強制對每個 CPU 進行一次上下文切換。雖然這個簡單的方法可以在一個不支持搶占的內(nèi)核上工作，換句話說，對 non-CONFIG_PREEMPT 和 CONFIG_PREEMPT，但對 CONFIG_PREEMPT_RT 實時 (-rt) 內(nèi)核無效。因此，實時RCU使用了一個（松散地）基于引用計數(shù)的方法。
當然，在真實內(nèi)核中的實現(xiàn)要復雜得多了，因為它需要管理終端，NMI，CPU熱插拔和其他實際內(nèi)核中的可能有的風險，而且還要維護良好的性能和可伸縮性。RCU的實時實現(xiàn)還必須擁有良好的實時響應能力，這就使得（像上面兩行那樣）直接禁止搶占變得不可能了。
雖然我們了解到了 synchronize_rcu() 的簡單實現(xiàn)原理，不過還有很多其它問題呢。比如，RCU讀者們在讀一個正在被并發(fā)地更新的鏈表的時候究竟讀到了什么呢？這個問題將在下一節(jié)講到。
維護多個版本的近期更新的對象
本節(jié)將展示 RCU 如何為多個不需要同步的讀者維護不同版本的鏈表。我們使用兩個例子來展示一個可能被給定的讀者引用的元素必須在該讀者處于讀方臨界區(qū)的整個過程中保持完好無損。第一個例子展示了鏈表元素的刪除，而第二個例子則展示了元素的替換。
例1：在刪除時維護多個版本
要開始這個“刪除”的例子，我們先把上節(jié)這個例子的 11-21行改成如下的形式：
1 p = search(head, key);
2 if (p != NULL) {
3 list_del_rcu(&p->list);
4 synchronize_rcu();
5 kfree(p);
6 }這個鏈表以及指針p的最初情況是這樣的：
表中每個元素的三元組分別代表域a, b, c。紅色的便捷表明讀者可以獲取它們的指針，而且因為讀操作和更新操作不是直接同步的，讀者可以在這個刪除的過程中同時發(fā)生。這里我們?yōu)榱饲逦鷽]有畫出雙向鏈表的反向指針。
在第三行的 list_del_rcu() 完成的時候，5,6,7 這個元素已經(jīng)被從鏈表中刪除了（如下圖）。由于讀者并不直接和更新操作同步，讀者可能同時正在掃描這個鏈表。由于訪問時間不同，這些并發(fā)讀者可能看到、也 可能沒看到新近刪除的元素。不過，那些在獲取指針之后延遲了讀操作的讀者（比如因為中斷、ECC內(nèi)存錯誤，或在 CONFIG_PREEMPT_RT內(nèi)核中因為搶占而延遲了的）可能仍然會在刪除之后的一段時間內(nèi)看到那個老的鏈表的版本。下圖中 5,6,7 元素的邊框仍然是紅色的，這意味著仍然有讀者可能會引用它。
這里注意，在退出讀方臨界區(qū)之后，讀者們就不能再持有 5,6,7 這個元素的引用了。所以，一旦第4行的 synchronize_rcu() 完成了，所有已有讀者也就保證都完成了，這樣就沒有讀者會訪問這個元素了，下圖中，這個元素的邊框也變黑了。我們的鏈表也回到了一個單一的版本了。
這之后，5,6,7 這個元素就可以被安全的釋放了：
這里，我們完成了刪除 5,6,7 這個元素的操作，下一小節(jié)將介紹替換操作。
例2：在替換的過程中維護數(shù)據(jù)的多個不同版本
在開始替換的例子錢，我們再修改一下前面例子的最后幾行：
1 q = kmalloc(sizeof(*p), GFP_KERNEL);
2 *q = *p;
3 q->b = 2;
4 q->c = 3;
5 list_replace_rcu(&p->list, &q->list);
6 synchronize_rcu();
7 kfree(p);這個鏈表的初始狀態(tài)和指針p和刪除的那個例子是完全一樣的：
和之前一樣，每個元素里面的三元組分別代表域 a, b 和 c。紅色的邊框代表了讀者可能會持有這個元素的引用，因為讀者和更新者沒有直接的同步，讀者可能會和整個替換過程并發(fā)進行。再次說明，這里我們?yōu)榱饲逦俅问÷粤朔聪蛑羔槨?/p>
第一行的 kmalloc() 生成了一個替換元素，如下：
第二行把舊的元素的內(nèi)容拷貝給新的元素：
第三行，將 q->b 更新為2：
第四行，將 q->c 更新為3：
現(xiàn)在，第5行進行替換操作，這里，新元素最終對讀者可見了。到了這里，如下所示，我們有了這個鏈表的兩個版本。先前已經(jīng)存在的讀者可以看到 5,6,7 元素，而新讀者將看到 5,2,3 元素。不過，任何讀者都被保證可以看到一個完整的鏈表。
第6行的 synchronize_rcu() 返回后，寬限期將完成，所有在 list_replace_rcu() 之前開始的讀者都將完成。具體地說，任何可能持有 5,6,7 的讀者都已經(jīng)退出了他們的讀方臨界區(qū)，這就保證他們不再持有一個引用。因而也在沒有任何讀者持有老元素的引用了，途中，5,6,7 元素的邊框也就變黑了。對于讀者來說，目前又只有一個單一的鏈表版本了，只是新的元素已經(jīng)替代了舊元素的位置。
第七行的 kfree() 完成后，鏈表舊成為了如下的樣子：
盡管 RCU 是以替換而命名的，但內(nèi)核中的大多數(shù)使用都是前面小節(jié) 中的簡單刪除的情況。
討論
這個例子假設(shè)在更新操作的過程中保存著一個互斥量，也就是說，這個鏈表在一個給定時間最多有兩種版本。
問題4：如何修改刪除的例子，來允許超過兩個版本的鏈表可以同時存在？問題5：在某一時刻，RCU最多可以有多少個鏈表的版本？
這組例子顯示了RCU使用多個版本來保障在存在并發(fā)讀者的情況下的安全更改數(shù)據(jù)。當然，一些算法是無法很好地支持多個版本的。
問題6：如果 rcu_read_lock() 與 rcu_read_unlock() 之間沒有自旋鎖或阻塞，RCU更新者會怎樣延遲RCU讀者？
這三個RCU的組成部分允許數(shù)據(jù)在并發(fā)讀者訪問的同時更新數(shù)據(jù)，并可以以多種方式實現(xiàn)基于RCU的算法，
