linux經(jīng)典的rcu如何實現(xiàn)？

一、RCU有什么用？

RCU主要用于對性能要求苛刻的并行實時計算。例如：天氣預報、模擬核爆炸計算、內(nèi)核同步等等。

假設你正在編寫一個并行實時程序，該程序需要訪問隨時變化的數(shù)據(jù)。這些數(shù)據(jù)可能是隨著溫度、濕度的變化而逐漸變化的大氣壓。這個程序的實時響應要求是如此嚴格，需要處理的數(shù)據(jù)量如此巨大，以至于不允許任何自旋或者阻塞，因此不能使用任何鎖。

幸運的是，溫度和壓力的范圍通常變化不大，因此使用默認的數(shù)據(jù)集也是可行的。當溫度、濕度和壓力抖動時，有必要使用實時數(shù)據(jù)。但是溫度、濕度和壓力是逐漸變化的，我們可以在幾分鐘內(nèi)更新數(shù)據(jù)，但沒必要實時更新值。

在這種情況下，可以使用一個全局指針，即gptr，通常為NULL，表示要使用默認值。偶爾也可以將gptr指向假設命名為a、b和c的變量，以反映氣壓的變化。

傳統(tǒng)的軟件可以使用自旋鎖這樣的同步機制，來保護gptr指針的讀寫。一旦舊的值不被使用，就可以將舊指針指向的數(shù)據(jù)釋放。這種簡單的方法有一個最大的問題：它會使軟件效率下降數(shù)個數(shù)量級（注意，不是下降數(shù)倍而是下降數(shù)個數(shù)量級）。

在現(xiàn)代計算系統(tǒng)中，向gptr寫入a、b、c這樣的值，并發(fā)的讀者要么看到一個NULL指針要么看到指向新結構gptr的指針，不會看到中間結果。也就是說，對于指針賦值來說，某種意義上這種賦值是原子的。讀者不會看到a、b、c之外的其他結果。并且，更好的一點，也是更重要的一點是：讀者不需要使用任何代價高昂的同步原語，因此這種方法非常適合于實時使用。

真正的難點在于：在讀者獲得gptr的引用時，它可能看到a、b、c這三個值中任意一個值，寫者何時才能安全的釋放a、b、c所指向的內(nèi)存數(shù)據(jù)結構？

引用計數(shù)的方案很有誘惑力，但正如鎖和順序鎖一樣，引用計數(shù)可能消耗掉數(shù)百個CPU指令周期，更致命的是，它會引用緩存行在CPU之間的來回顛簸，破壞各個CPU的緩存，引起系統(tǒng)整體性能的下降。很明顯，這種選擇不是我們所期望的。

想要理解Linux經(jīng)典RCU實現(xiàn)的讀者，應當認真閱讀下面這段話：

一種實現(xiàn)方法是，寫者完全不知道有哪些讀者存在。這種方法顯然讓讀者的性能最佳，但留給寫者的問題是：如何才能確定所有的老讀者已經(jīng)完成。

最簡單的實現(xiàn)是：讓線程不會被搶占，或者說，讀者在讀RCU數(shù)據(jù)期間不能被搶占。在這種不可搶占的環(huán)境中，每個線程將一直運行，直到它明確地和自愿地阻塞自己（現(xiàn)實世界確實有這樣的操作系統(tǒng)，它由線程自己決定何時釋放CPU。例如大名鼎鼎的Solaris操作系統(tǒng)）。這要求一個不能阻塞的無限循環(huán)將使該CPU在循環(huán)開始后無法用于任何其他目的，還要求還要求線程在持有自旋鎖時禁止阻塞。否則會形成死鎖。

這種方法的示意圖下所示，圖中的時間從頂部推移到底部，CPU 1的list_del()操作是RCU寫者操作，CPU2、CPU3在讀端讀取list節(jié)點。

Linux經(jīng)典RCU的概念即是如此。雖然這種方法在生產(chǎn)環(huán)境上的實現(xiàn)可能相當復雜，但是玩具實現(xiàn)卻非常簡單。

1 for_each_online_cpu(cpu)

2 run_on(cpu);

for_each_online_cpu()原語遍歷所有CPU，run_on()函數(shù)導致當前線程在指定的CPU上執(zhí)行，這會強制目標CPU執(zhí)行上下文切換。因此，一旦for_each_online_cpu()完成，每個CPU都執(zhí)行了一次上下文切換，這又保證了所有之前存在的讀線程已經(jīng)完成。

請注意，這個方法不能用于生產(chǎn)環(huán)境。正確處理各種邊界條件和對性能優(yōu)化的強烈要求意味著用于生產(chǎn)環(huán)境的代碼實現(xiàn)將十分復雜。此外，可搶占環(huán)境的RCU實現(xiàn)需要讀者實際做點什么事情（也就是在讀臨界區(qū)內(nèi)，禁止搶占。這是Linux經(jīng)典RCU讀鎖的實現(xiàn)）。不過，這種簡單的不可搶占的方法在概念上是完整的，有助于我們理解RCU的基本原理。

二、RCU是什么？

RCU是read-copy-update的簡稱，翻譯為中文有點別扭“讀-復制-更新”。它是是一種同步機制，有三種角色或者操作：讀者、寫者和復制操作，我理解其中的復制操作就是不同CPU上的讀者復制了不同的數(shù)據(jù)值，或者說擁有同一個指針的不同拷貝值，也可以理解為：在讀者讀取值的時候，寫者復制并替換其內(nèi)容（后一種理解來自于RCU作者的解釋）。它于2002年10月引入Linux內(nèi)核。

RCU允許讀操作可以與更新操作并發(fā)執(zhí)行，這一點提升了程序的可擴展性。常規(guī)的互斥鎖讓并發(fā)線程互斥執(zhí)行，并不關心該線程是讀者還是寫者，而讀/寫鎖在沒有寫者時允許并發(fā)的讀者，相比于這些常規(guī)鎖操作，RCU在維護對象的多個版本時確保讀操作保持一致，同時保證只有所有當前讀端臨界區(qū)都執(zhí)行完畢后才釋放對象。RCU定義并使用了高效并且易于擴展的機制，用來發(fā)布和讀取對象的新版本，還用于延后舊版本對象的垃圾收集工作。這些機制恰當?shù)卦谧x端和更新端并行工作，使得讀端特別快速。在某些場合下（比如非搶占式內(nèi)核里），RCU讀端的函數(shù)完全是零開銷。

Seqlock也可以讓讀者和寫者并發(fā)執(zhí)行，但是二者有什么區(qū)別？

首先是二者的目的不一樣。Seqlock是為了保證讀端在讀取值的時候，寫者沒有對它進行修改，而RCU是為了多核擴展性。

其次是保護的數(shù)據(jù)結構大小不一樣。Seqlock可以保護一組相關聯(lián)的數(shù)據(jù)，而RCU只能保護指針這樣的unsigned long類型的數(shù)據(jù)。

最重要的區(qū)別還在于效率，Seqlock本質上是與自旋鎖同等重量級的原語，其效率與RCU不在同一個數(shù)量級上面。

下面從三個基礎機制來闡述RCU究竟是什么？

RCU由三種基礎機制構成，第一個機制用于插入，第二個用于刪除，第三個用于讓讀者可以不受并發(fā)的插入和刪除干擾。分別是：

發(fā)布/訂閱機制，用于插入。

等待已有的RCU讀者完成的機制，用于刪除。

維護對象多個版本的機制，以允許并發(fā)的插入和刪除操作。

1、發(fā)布/訂閱機制

RCU的一個關鍵特性是可以安全的讀取數(shù)據(jù)，即使數(shù)據(jù)此時正被修改。RCU通過一種發(fā)布/訂閱機制達成了并發(fā)的數(shù)據(jù)插入。舉個例子，假設初始值為NULL的全局指針gp現(xiàn)在被賦值指向一個剛分配并初始化的數(shù)據(jù)結構。如下所示的代碼片段：

1 structfoo {

2 inta;

3 intb;

4 intc;

5 };

6 structfoo *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;

“發(fā)布”數(shù)據(jù)結構（不安全）

不幸的是，這塊代碼無法保證編譯器和CPU會按照編程順序執(zhí)行最后4條賦值語句。如果對gp的賦值發(fā)生在初始化p的各字段之前，那么并發(fā)的讀者會讀到未初始化的值。這里需要內(nèi)存屏障來保證事情按順序發(fā)生，可是內(nèi)存屏障又向來以難用而聞名。所以這里我們用一句rcu_assign_ pointer()原語將內(nèi)存屏障封裝起來，讓其擁有發(fā)布的語義。最后4行代碼如下。

1 p->a= 1;

2 p->b= 2;

3 p->c= 3;

4 rcu_assign_pointer(gp, p);

rcu_assign_pointer()“發(fā)布”一個新結構，強制讓編譯器和CPU在為p的各字段賦值后再去為gp賦值。

不過，只保證更新者的執(zhí)行順序并不夠，因為讀者也需要保證讀取順序。請看下面這個例子中的代碼。

1 p= gp;

2 if(p != NULL){

3 do_something_with(p->a, p->b,p->c);

4 }

這塊代碼看起來好像不會受到亂序執(zhí)行的影響，可惜事與愿違，在DEC Alpha CPU機器上，還有啟用編譯器值猜測（value-speculation）優(yōu)化時，會讓p->a，p->b和p->c的值在p賦值之前被讀取。

也許在啟動編譯器的值猜測優(yōu)化時比較容易觀察到這一情形，此時編譯器會先猜測p->a、p->b、p->c的值，然后再去讀取p的實際值來檢查編譯器的猜測是否正確。這種類型的優(yōu)化十分激進，甚至有點瘋狂，但是這確實發(fā)生在剖析驅動（profile-driven）優(yōu)化的上下文中。

然而讀者可能會說，我們一般不會使用編譯器猜測優(yōu)化。那么我們可以考慮DEC Alpha CPU這樣的極端弱序的CPU。在這個CPU上面，引起問題的根源在于：在同一個CPU內(nèi)部，使用了不止一個緩存來緩存CPU數(shù)據(jù)。這樣可能使用p和p->a被分布不同一個CPU的不同緩存中，造成緩存一致性方面的問題。

顯然，我們必須在編譯器和CPU層面阻止這種危險的優(yōu)化。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_read_ lock()和rcu_read_unlock()這對原語定義了RCU讀端的臨界區(qū)。事實上，在沒有配置CONFIG_PREEMPT的內(nèi)核里，這對原語就是空函數(shù)。在可搶占內(nèi)核中，這這對原語就是關閉/打開搶占。

rcu_dereference()原語用一種“訂閱”的辦法獲取指定指針的值。保證后續(xù)的解引用操作可以看見在對應的“發(fā)布”操作（rcu_assign_pointer()）前進行的初始化，即：在看到p的新值之前，能夠看到p->a、p->b、p->c的新值。請注意，rcu_assign_pointer()和rcu_dereference()這對原語既不會自旋或者阻塞，也不會阻止list_add_ rcu()的并發(fā)執(zhí)行。

雖然理論上rcu_assign_pointer()和rcu_derederence()可以用于構造任何能想象到的受RCU保護的數(shù)據(jù)結構，但是實踐中常常只用于構建更上層的原語。例如，將rcu_assign_pointer()和rcu_dereference()原語嵌入在Linux鏈表的RCU變體中。Linux有兩種雙鏈表的變體，循環(huán)鏈表struct list_head和哈希表structhlist_head/struct hlist_node。前一種如下圖所示。

對鏈表采用指針發(fā)布的例子如下：

1 struct foo {

2struct list_head *list;

3 int a;

4 int b;

5 int c;

6 };

7LIST_HEAD(head);

8

9 /* .. . */

10

11 p =kmalloc(sizeof(*p), GFP_KERNEL);

12p->a = 1;

13p->b = 2;

14p->c = 3;

15list_add_rcu(&p->list,&head);

RCU發(fā)布鏈表

第15行必須用某些同步機制（最常見的是各種鎖）來保護，防止多核list_add()實例并發(fā)執(zhí)行。不過，同步并不能阻止list_add()的實例與RCU的讀者并發(fā)執(zhí)行。

訂閱一個受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();

list_add_rcu()原語向指定的鏈表發(fā)布了一項條目，保證對應的list_for_each_ entry_rcu()可以訂閱到同一項條目。

Linux的其他鏈表、哈希表都是線性鏈表，這意味著它的頭結點只需要一個指針，而不是象循環(huán)鏈表那樣需要兩個。因此哈希表的使用可以減少哈希表的hash bucket數(shù)組一半的內(nèi)存消耗。

向受RCU保護的哈希表發(fā)布新元素和向循環(huán)鏈表的操作十分類似，如下所示。

1 struct foo {

2struct hlist_node *list;

3 int a;

4 int b;

5 int c;

6 };

7HLIST_HEAD(head);

8

9 /* .. . */

10

11 p =kmalloc(sizeof(*p), GFP_KERNEL);

12p->a = 1;

13p->b = 2;

14p->c = 3;

15hlist_add_head_rcu(&p->list,&head);

和之前一樣，第15行必須用某種同步機制，比如鎖來保護。

訂閱受RCU保護的哈希表和訂閱循環(huán)鏈表沒什么區(qū)別。

1rcu_read_lock();

2hlist_for_each_entry_rcu(p,q, head, list){

3do_something_with(p->a,p->b, p->c);

4 }

5 rcu_read_unlock();

表9.2是RCU的發(fā)布和訂閱原語，另外還有一個刪除發(fā)布原語。

請注意，list_replace_rcu()、list_del_rcu()、hlist_replace_rcu()和hlist_ del_rcu()這些API引入了一點復雜性。何時才能安全地釋放剛被替換或者刪除的數(shù)據(jù)元素？我們怎么能知道何時所有讀者釋放了他們對數(shù)據(jù)元素的引用？

2、等待已有的RCU讀者執(zhí)行完畢

從最基本的角度來說，RCU就是一種等待事物結束的方式。當然，有很多其他的方式可以用來等待事物結束，比如引用計數(shù)、讀/寫鎖、事件等等。RCU的最偉大之處在于它可以等待（比如）20,000種不同的事物，而無需顯式地去跟蹤它們中的每一個，也無需去擔心對性能的影響，對擴展性的限制，復雜的死鎖場景，還有內(nèi)存泄漏帶來的危害等等使用顯式跟蹤手段會出現(xiàn)的問題。

在RCU的例子中，被等待的事物稱為“RCU讀端臨界區(qū)”。RCU讀端臨界區(qū)從rcu_read_lock()原語開始，到對應的rcu_read_unlock()原語結束。RCU讀端臨界區(qū)可以嵌套，也可以包含一大塊代碼，只要這其中的代碼不會阻塞或者睡眠（先不考慮可睡眠RCU）。如果你遵守這些約定，就可以使用RCU去等待任何代碼的完成。

RCU通過間接地確定這些事物何時完成，才完成了這樣的壯舉。

如上圖所示，RCU是一種等待已有的RCU讀端臨界區(qū)執(zhí)行完畢的方法，這里的執(zhí)行完畢也包括在臨界區(qū)里執(zhí)行的內(nèi)存操作。不過請注意，在某個寬限期開始后才啟動的RCU讀端臨界區(qū)會擴展到該寬限期的結尾處。

下列偽代碼展示了寫者使用RCU等待讀者的基本方法。

1．作出改變，比如替換鏈表中的一個元素。

2．等待所有已有的RCU讀端臨界區(qū)執(zhí)行完畢（比如使用synchronize_rcu()原語）。這里要注意的是后續(xù)的RCU讀端臨界區(qū)無法獲取剛剛刪除元素的引用。

3．清理，比如釋放剛才被替換的元素。

下圖所示的代碼片段演示了這個過程，其中字段a是搜索關鍵字。

1 struct foo {

2struct list_head *list;

3 int a;

4 int b;

5 int c;

6 };

7LIST_HEAD(head);

8

9 /* .. . */

10

11 p =search(head, key);

12 if (p== NULL) {

13 /* Takeappropriate action, unlock,and

return.*/

14 }

15 q =kmalloc(sizeof(*p), GFP_KERNEL);

16 *q = *p;

17q->b = 2;

18q->c = 3;

19list_replace_rcu(&p->list,&q->list);

20synchronize_rcu();

21 kfree(p);

標準RCU替換示例

第19、20和21行實現(xiàn)了剛才提到的三個步驟。第16至19行正如RCU其名（讀-復制-更新），在允許并發(fā)讀的同時，第16行復制，第17到19行更新。

synchronize_rcu()原語可以相當簡單。然而，想要達到產(chǎn)品質量，代碼實現(xiàn)必須處理一些困難的邊界情況，并且還要進行大量優(yōu)化，這兩者都將導致明顯的復雜性。理解RCU的難點，主要在于synchronize_rcu()的實現(xiàn)。

3、維護最近被更新對象的多個版本

下面展示RCU如何維護鏈表的多個版本，供并發(fā)的讀者訪問。通過兩個例子來說明在讀者還處于RCU讀端臨界區(qū)時，被讀者引用的數(shù)據(jù)元素如何保持完整性。第一個例子展示了鏈表元素的刪除，第二個例子展示了鏈表元素的替換。

例子1：在刪除過程中維護多個版本

1 p= search(head, key);

2 if(p != NULL){

3 list_del_rcu(&p->list);

4 synchronize_rcu();

5 kfree(p);

6 }

如下圖，每個元素中的三個數(shù)字分別代表字段a、b、c的值。紅色的元素表示RCU讀者此時正持有該元素的引用。請注意，我們?yōu)榱俗寛D更清楚，忽略了后向指針和從尾指向頭的指針。

等第3行的list_del_rcu()執(zhí)行完畢后，“5、6、7”元素從鏈表中被刪除。因為讀者不直接與更新者同步，所以讀者可能還在并發(fā)地掃描鏈表。這些并發(fā)的讀者有可能看見，也有可能看不見剛剛被刪除的元素，這取決于掃描的時機。不過，剛好在取出指向被刪除元素指針后被延遲的讀者（比如，由于中斷、ECC內(nèi)存錯誤），就有可能在刪除后還看見鏈表元素的舊值。因此，我們此時有兩個版本的鏈表，一個有元素“5、6、7”，另一個沒有。元素“5、6、7”用黃色標注，表明老讀者可能還在引用它，但是新讀者已經(jīng)無法獲得它的引用。

請注意，讀者不允許在退出RCU讀端臨界區(qū)后還維護元素“5、6、7”的引用。因此，一旦第4行的synchronize_rcu()執(zhí)行完畢，所有已有的讀者都要保證已經(jīng)執(zhí)行完，不能再有讀者引用該元素。這樣我們又回到了唯一版本的鏈表。

此時，元素“5、6、7”可以安全被釋放了。這樣我們就完成了元素“5、6、7”的刪除。

例子2：在替換過程中維護多個版本

1 q= kmalloc(sizeof(*p), GFP_KERNEL);

2 *q = *p;

3 q->b = 2;

4 q->c = 3;

5list_replace_rcu(&p->list,&q->list);

6synchronize_rcu();

7 kfree(p);

鏈表的初始狀態(tài)包括指針p都和“刪除”例子中一樣。

RCU從鏈表中替換元素

和前面一樣，每個元素中的三個數(shù)字分別代表字段a、b、c。紅色的元素表示讀者可能正在引用，并且因為讀者不直接與更新者同步，所以讀者有可能與整個替換過程并發(fā)執(zhí)行。請注意我們?yōu)榱藞D表的清晰，再一次忽略了后向指針和從尾指向頭的指針。

下面描述了元素“5、2、3”如何替換元素“5、6、7”的過程，任何特定讀者可能看見這兩個值其中一個。

第1行用kmalloc()分配了要替換的元素。此時，沒有讀者持有剛分配的元素的引用（用綠色表示），并且該元素是未初始化的（用問號表示）。

第2行將舊元素復制給新元素。新元素此時還不能被讀者訪問，但是已經(jīng)初始化了。

第3行將q->b的值更新為2，第4行將q->c的值更新為3。

現(xiàn)在，第5行開始替換，這樣新元素終于對讀者可見了，因此顏色也變成了紅色。此時，鏈表就有兩個版本了。已經(jīng)存在的老讀者可能看到元素“5、6、7”（現(xiàn)在顏色是黃色的），而新讀者將會看見元素“5、2、3”。不過這里可以保證任何讀者都能看到一個完好的鏈表。

隨著第6行synchronize_rcu()的返回，寬限期結束，所有在list_replace_rcu()之前開始的讀者都已經(jīng)完成。特別是任何可能持有元素“5、6、7”引用的讀者保證已經(jīng)退出了它們的RCU讀端臨界區(qū)，不能繼續(xù)持有引用。因此，不再有任何讀者持有舊數(shù)據(jù)的引用,，如第6排綠色部分所示。這樣我們又回到了單一版本的鏈表，只是用新元素替換了舊元素。

等第7行的kfree()完成后，鏈表就成了最后一排的樣子。

不過盡管RCU是因替換的例子而得名的，但是RCU在內(nèi)核中的主要用途還是用于簡單的刪除。