深入理解Linux RCU:RCU是讀寫鎖的替代者

一、

RCU的用法

RCU最常用的目的是替換已有的機制，如下所示：

讀寫鎖

受限制的引用計數(shù)機制

批量引用計數(shù)機制

窮人版的垃圾回收器

存在擔保

類型安全的內(nèi)存

等待事物結(jié)束

1.1 RCU是讀寫鎖的替代者

在Linux內(nèi)核中，RCU最常見的用途是替換讀寫鎖。在20世紀90年代初期，Paul在實現(xiàn)通用RCU之前，實現(xiàn)了一種輕量級的讀寫鎖。后來，為這個輕量級讀寫鎖原型所設(shè)想的每個用途，最終都使用RCU來實現(xiàn)了。

RCU和讀寫鎖最關(guān)鍵的相似之處，在于兩者都有可以并行執(zhí)行讀端臨界區(qū)。事實上，在某些情況下，完全可以用對應的讀寫鎖API來替換RCU的API，反之亦然。

RCU的優(yōu)點在于：性能、不會死鎖，以及良好的實時延遲。當然RCU也有一點缺點，比如：讀者與更新者并發(fā)執(zhí)行，低優(yōu)先級RCU讀者也可以阻塞正等待優(yōu)雅周期(Grace Period)結(jié)束的高優(yōu)先級線程，優(yōu)雅周期的延遲可能達到好幾毫秒。

上圖是不是略顯奇怪，RCU讀端延遲竟然小于一個CPU周期？這不是開玩笑，因為有某些實現(xiàn)中（例如，服務器Linux），RCU讀端就完全是一個空操作。當然，在這樣的實現(xiàn)中，它可能會包含一個編譯屏障，因此也會對性能產(chǎn)生那么一點點影響。

請注意，在單個CPU上讀寫鎖比RCU慢一個數(shù)量級，在16個CPU上讀寫鎖比RCU幾乎要慢兩個數(shù)量級。隨著CPU數(shù)量的增加，RCU的擴展性優(yōu)勢越來越突出?？梢赃@么說，RCU幾乎就是水平擴展，這可以在上圖中看出來。

當內(nèi)核配置了CONFIG_PREEMPT的時候，RCU仍然超過了讀寫鎖一到三個數(shù)量級，如下圖所示。請注意：讀寫鎖在CPU數(shù)目很多時的陡峭曲線。

當然，上圖中的臨界區(qū)長度為0，這夸大了讀寫鎖的性能劣勢。隨著臨界區(qū)的加大，RCU的性能優(yōu)勢也不再顯著。在下圖中，有16個CPU，y軸代表讀端原語的總開銷，x軸代表臨界區(qū)長度。

然而，一般說來，臨界區(qū)都能在幾個毫秒內(nèi)完成，所以總的來說，在性能方面，測試結(jié)果對RCU是有利的。

另外，RCU讀端原語基本上是不會死鎖的。因為它本身就屬于無鎖編程的范疇。

這種免于死鎖的能力來源于RCU的讀端原語不阻塞、不自旋，甚至不存在向后跳轉(zhuǎn)語句，所以RCU讀端原語的執(zhí)行時間是確定的。這使得RCU讀端原語不可能形成死鎖循環(huán)。

RCU讀端免于死鎖的能力帶來了一個有趣的后果：RCU讀者可以恣意地升級為RCU更新者。在讀寫鎖中嘗試這種升級則會有可能造成死鎖。進行RCU讀者到更新者升級的代碼片段如下所示：

1 rcu_read_lock();

2 list_for_each_entry_rcu(p, &head, list_field) {

3 do_something_with(p);

4 if (need_update(p)) {

5 spin_lock(my_lock);

6 do_update(p);

7 spin_unlock(&my_lock);

8 }

9 }

10 rcu_read_unlock();

請注意，do_update()是在鎖的保護下執(zhí)行，也是在RCU讀端的保護下執(zhí)行。

RCU免于死鎖的特性帶來的另一個有趣后果是RCU不會受優(yōu)先級反轉(zhuǎn)問題影響。比如，低優(yōu)先級的RCU讀者無法阻止高優(yōu)先級的RCU更新者獲取更新端鎖。類似地，低優(yōu)先級的更新者也無法阻止高優(yōu)先級的RCU讀者進入RCU讀端臨界區(qū)。

另一方面，因為RCU讀端原語既不自旋也不阻塞，所以這些原語有著極佳的實時延遲。而自旋鎖或者讀寫鎖都存在不確定的實時延遲。

但是，RCU還是會受到更隱晦的優(yōu)先級反轉(zhuǎn)問題影響，比如，在等待RCU優(yōu)雅周期結(jié)束而阻塞的高優(yōu)先級進程，會被-rt內(nèi)核的低優(yōu)先級RCU讀者阻塞。這可以用RCU優(yōu)先級提升來解決。

再一方面，因為RCU讀者既不自旋也不阻塞，RCU更新者也沒有任何類似回滾或者中止的語義，所以RCU讀者和更新者可以并發(fā)執(zhí)行。這意味著RCU讀者有可能訪問舊數(shù)據(jù)，還有可能發(fā)現(xiàn)數(shù)據(jù)不一致，無論這兩個問題中的哪一個，都讓讀寫鎖有卷土重來的機會。

不過，令人吃驚的是，在大量情景中，數(shù)據(jù)不一致和舊數(shù)據(jù)都不是問題。網(wǎng)絡(luò)路由表是一個經(jīng)典例子。因為路由的更新可能要花相當長一段時間才能到達指定系統(tǒng)（幾秒甚至幾分鐘），所以系統(tǒng)可能會在新數(shù)據(jù)到來后的一段時間內(nèi)，仍然將報文發(fā)到錯誤的地址去。通常，在幾毫秒內(nèi)將報文發(fā)送到錯誤地址并不算什么問題。

簡單地說，讀寫鎖和RCU提供了不同的保證。在讀寫鎖中，任何在寫者之后開始的讀者都“保證”能看到新值。與之相反，在RCU中，在更新者完成后才開始的讀者都“保證”能看見新值，在更新者開始后才完成的讀者有可能看見新值，也有可能看見舊值，這取決于具體的時機。

在實時RCU、SRCU或QRCU中，被搶占的讀者將阻止正在進行中的優(yōu)雅周期的完成，即使有高優(yōu)先級的任務在等待優(yōu)雅周期完成時也是如此。實時RCU可以通過用call_rcu()替換synchronize_rcu()來避免此問題，或者采用RCU優(yōu)先級提升來避免。

除了那些“玩具”RCU實現(xiàn)，RCU優(yōu)雅周期可能會延續(xù)好幾個毫秒。這使得RCU更適于使用在讀數(shù)據(jù)占多數(shù)的情景。

將讀寫鎖轉(zhuǎn)換成RCU非常簡單，如下：

1.2 RCU是一種受限制的引用計數(shù)機制

因為優(yōu)雅周期不能在RCU讀端臨界區(qū)進行時結(jié)束，所以RCU讀端原語可以像受限的引用計數(shù)機制一樣使用。比如考慮下面的代碼片段：

1 rcu_read_lock(); /* acquire reference. */

2 p = rcu_dereference(head);

3 /* do something with p. */

4 rcu_read_unlock(); /* release reference. */

rcu_read_lock()原語可以看作是獲取對p的引用，因為相應的優(yōu)雅周期無法在配對的rcu_read_unlock()之前結(jié)束。這種引用計數(shù)機制是受限制的，因為我們不允許在RCU讀端臨界區(qū)中阻塞，也不允許將一個任務的RCU讀端臨界區(qū)傳遞給另一個任務。

不管上述的限制，下列代碼可以安全地刪除p：

1 spin_lock(&mylock);

2 p = head;

3 rcu_assign_pointer(head, NULL);

4 spin_unlock(&mylock);

5 /* Wait for all references to be released. */

6 synchronize_rcu();

7 kfree(p);

當然，RCU也可以與傳統(tǒng)的引用計數(shù)結(jié)合。但是為什么不直接使用引用計數(shù)？部分原因是性能，如下圖所示，圖中顯示了在16個3GHz CPU的Intel x86系統(tǒng)中采集的數(shù)據(jù)。

和讀寫鎖一樣，RCU的性能優(yōu)勢主要來源于較短的臨界區(qū)，如下圖所示。

1.3 RCU是一種可大規(guī)模使用的引用計數(shù)機制

如前所述，傳統(tǒng)的引用計數(shù)通常與某種或者一組數(shù)據(jù)結(jié)構(gòu)有聯(lián)系。然而，維護一組數(shù)據(jù)結(jié)構(gòu)的全局引用計數(shù)，通常會導致包含引用計數(shù)的緩存行來回“乒乓”。這種緩存行“乒乓”會嚴重影響系統(tǒng)性能。

相反，RCU的輕量級讀端原語允許讀端極其頻繁地調(diào)用，卻只帶來微不足道的性能影響，這使得RCU可以作為一種幾乎沒有性能損失的“批量引用計數(shù)機制”。當某個任務需要在一大段代碼中持有引用時，可以使用可睡眠RCU（SRCU）。但是，一個任務不能將引用鎖引用傳遞給另一個任務。例如：在開始一次I/O時獲取引用，然后當對應的I/O完成時在中斷處理函數(shù)里釋放該引用。

1.4 RCU是窮人版的垃圾回收器

當人們剛開始學習RCU時，有種比較少見的感嘆是“RCU有點像垃圾回收器！”。這種感嘆有一部分是對的，不過還是會給學習造成誤導。

也許思考RCU與垃圾自動回收器（GC）之間關(guān)系的最好辦法是，RCU類似自動決定回收時機的GC，但是RCU與GC有幾點不同：（1）程序員必須手動指示何時可以回收指定數(shù)據(jù)結(jié)構(gòu)，（2）程序員必須手動標出可以合法持有引用的RCU讀端臨界區(qū)。

盡管存在這些差異，兩者的相似程度仍然相當高，至少有一篇理論分析RCU的文獻曾經(jīng)分析過兩者的相似度。

1.5 RCU是一種提供存在擔保的方法

通過鎖來提供存在擔保有其不利之處。與鎖類似，如果任何受RCU保護的數(shù)據(jù)元素在RCU讀端臨界區(qū)中被訪問，那么數(shù)據(jù)元素在RCU讀端臨界區(qū)持續(xù)期間保證存在。

1 int delete(int key)

2 {

3 struct element *p;

4 int b;

5 5

6 b = hashfunction(key);

7 rcu_read_lock();

8 p = rcu_dereference(hashtable[b]);

9 if (p == NULL || p->key != key) {

10 rcu_read_unlock();

11 return 0;

12 }

13 spin_lock(&p->lock);

14 if (hashtable[b] == p && p->key == key) {

15 rcu_read_unlock();

16 hashtable[b] = NULL;

17 spin_unlock(&p->lock);

18 synchronize_rcu();

19 kfree(p);

20 return 1;

21 }

22 spin_unlock(&p->lock);

23 rcu_read_unlock();

24 return 0;

25 }

上圖展示了基于RCU的存在擔保如何通過從哈希表刪除元素的函數(shù)來實現(xiàn)每數(shù)據(jù)元素鎖。第6行計算哈希函數(shù)，第7行進入RCU讀端臨界區(qū)。如果第9行發(fā)現(xiàn)哈希表對應的哈希項（bucket）為空，或者數(shù)據(jù)元素不是我們想要刪除的那個，那么第10行退出RCU讀端臨界區(qū)，第11行返回錯誤。

如果第9行判斷為false，第13行獲取更新端的自旋鎖，然后第14行檢查元素是否還是我們想要的。如果是，第15行退出RCU讀端臨界區(qū)，第16行從哈希表中刪除找到的元素，第17行釋放鎖，第18行等待所有之前已經(jīng)存在的RCU讀端臨界區(qū)退出，第19行釋放剛被刪除的元素，最后第20行返回成功。如果14行的判斷發(fā)現(xiàn)元素不再是我們想要的，那么第22行釋放鎖，第23行退出RCU讀端臨界區(qū)，第24行返回錯誤以刪除該關(guān)鍵字。

1.6 RCU是一種提供類型安全內(nèi)存的方法

很多無鎖算法并不需要數(shù)據(jù)元素在被RCU讀端臨界區(qū)引用時保持完全一致，只要數(shù)據(jù)元素的類型不變就可以了。換句話說，只要數(shù)據(jù)結(jié)構(gòu)類型不變，無鎖算法可以允許某個數(shù)據(jù)元素在被其他對象引用時被釋放并重新分配，但是決不允許類型上的改變。這種“保證”，在學術(shù)文獻中被稱為“類型安全的內(nèi)存”，它比前一節(jié)提到的存在擔保要弱一些，因此處理起來也要困難一些。類型安全的內(nèi)存算法在Linux內(nèi)核中的應用是slab緩存，被SLAB_DESTROY_BY_RCU標記專門標出來的緩存通過RCU將已釋放的slab返回給系統(tǒng)內(nèi)存。在任何已有的RCU讀端臨界區(qū)持續(xù)期間，使用RCU可以保證所有帶有SLAB_DESTROY_BY_RCU標記且正在使用的slab元素仍然在該slab中，類型保持一致。

雖然基于類型安全的無鎖算法在特定情景下非常有效，但是最好還是盡量使用存在擔保。畢竟簡單總是更好的。

1.7 RCU是一種等待事物結(jié)束的方式

RCU的一個強大之處，就是允許你在等待上千個不同事物結(jié)束的同時，又不用顯式地去跟蹤其中每一個事物，因此也就無需擔心性能下降、擴展限制、復雜的死鎖場景、內(nèi)存泄露等顯式跟蹤機制本身的問題。

下面展示如何實現(xiàn)與不可屏蔽中斷（NMI）處理函數(shù)的交互，如果用鎖來實現(xiàn)，這將極其困難。步驟如下：

1．做出改變，比如，OS對一個NMI做出反應。在NMI中使用RCU讀端原語。

2．等待所有已有的讀端臨界區(qū)完全退出（比如使用synchronize_sched()原語）。

3．掃尾工作，比如，返回表明改變成功完成的狀態(tài)。

下面是一個Linux內(nèi)核中的例子。在這個例子中，timer_stop()函數(shù)使用synchronize_sched()確保在釋放相關(guān)資源之前，所有正在處理的NMI處理函數(shù)已經(jīng)完成。

1 struct profile_buffer {

2 long size;

3 atomic_t entry[0];

4 };

5 static struct profile_buffer *buf = NULL;

6

7 void nmi_profile(unsigned long pcvalue)

8 {

9 struct profile_buffer *p =

rcu_dereference(buf);

10

11 if (p == NULL)

12 return;

13 if (pcvalue >= p->size)

14 return;

15 atomic_inc(&p->entry[pcvalue]);

16 }

17

18 void nmi_stop(void)

19 {

20 struct profile_buffer *p = buf;

21

22 if (p == NULL)

23 return;

24 rcu_assign_pointer(buf, NULL);

25 synchronize_sched();

26 kfree(p);

27 }

第1到4行定義了profile_buffer結(jié)構(gòu)，包含一個大小和一個變長數(shù)組的入口。第5行定義了指向profile_buffer的指針，這里假設(shè)別處對該指針進行了初始化，指向內(nèi)存的動態(tài)分配區(qū)。

第7至16行定義了nmi_profile()函數(shù)，供NMI中斷處理函數(shù)調(diào)用。該函數(shù)不會被搶占，也不會被普通的中斷處理函數(shù)打斷，但是，該函數(shù)還是會受高速緩存未命中、ECC錯誤以及被同一個核的其他硬件線程搶占時鐘周期等因素影響。第9行使用rcu_dereference()原語來獲取指向profile_buffer的本地指針，這樣做是為了確保在DECAlpha上的內(nèi)存順序執(zhí)行，如果當前沒有分配profile_buffer，第11行和12行退出，如果參數(shù)pcvalue超出范圍，第13和14行退出。否則，第15行增加以參數(shù)pcvalue為下標的profile_buffer項的值。請注意，profile_buffer結(jié)構(gòu)中的size保證了pcvalue不會超出緩沖區(qū)的范圍，即使突然將較大的緩沖區(qū)替換成了較小的緩沖區(qū)也是如此。

第18至27行定義了nmi_stop()函數(shù)，由調(diào)用者負責互斥訪問（比如持有正確的鎖）。第20行獲取profile_buffer的指針，如果緩沖區(qū)為空，第22和23行退出。否則，第24行將profile_buffer的指針置NULL（使用rcu_assign_pointer()原語在弱順序的機器中保證內(nèi)存順序訪問），第25行等待RCU Sched的優(yōu)雅周期結(jié)束，尤其是等待所有不可搶占的代碼——包括NMI中斷處理函數(shù)——結(jié)束。一旦執(zhí)行到第26行，我們就可以保證所有獲取到指向舊緩沖區(qū)指針的nmi_profile()實例都已經(jīng)返回了?，F(xiàn)在可以安全釋放緩沖區(qū)，這時使用kfree()原語。

簡而言之，RCU讓profile_buffer動態(tài)切換變得更簡單，你可以試試原子操作，也可以用鎖來折磨下自己。注意考慮到如下一點：在大多數(shù)CPU架構(gòu)中，原子操作和鎖都可能存在循環(huán)語句，在循環(huán)的過程中可能會被NMI中斷。

二、RCU API

2.1等待完成的API族

“RCU Classic”一列對應的是RCU的原始實現(xiàn)，rcu_read_lock()和rcu_read_unlock()原語標示出RCU讀端臨界區(qū)，可以嵌套使用。對應的同步的更新端原語synchronize_rcu()和synchronize_net()都是等待當前正在執(zhí)行的RCU讀端臨界區(qū)退出。等待時間被稱為“優(yōu)雅周期”。異步的更新端原語call_rcu()在后續(xù)的優(yōu)雅周期結(jié)束后調(diào)用由參數(shù)指定的函數(shù)。比如，call_rcu(p, f);在優(yōu)雅周期結(jié)束后執(zhí)行RCU回調(diào)f(p)。

想要利用基于RCU的類型安全的內(nèi)存，要將SLAB_DESTROY_BY_RCU傳遞給kmem_cache_create()。有一點很重要，SLAB_DESTROY_BY_RCU不會阻止kmem_cache_alloc()立即重新分配剛被kmem_cache_free()釋放的內(nèi)存！事實上，由rcu_dereference返回的受SLAB_DESTROY_ BY_RCU標記保護的數(shù)據(jù)結(jié)構(gòu)可能會釋放——重新分配任意次，甚至在rcu_read_lock()保護下也是如此。但是，SLAB_DESTROY_BY_RCU可以阻止kmem_cache_free()在RCU優(yōu)雅周期結(jié)束之前，它所返回數(shù)據(jù)結(jié)構(gòu)的完全釋放給SLAB。一句話，雖然數(shù)據(jù)元素可能被釋放——重新分配N次，但是它的類型是保持不變的。

2.2訂閱和版本維護API

表中的第一類API作用于Linux的struct list_head循環(huán)雙鏈表。list_for_each_ entry_rcu()原語以類型安全的方式遍歷受RCU保護的鏈表。在非Alpha的平臺上，該原語相較于list_for_each_entry()原語不產(chǎn)生或者只帶來極低的性能懲罰。list_add_rcu()、list_add_tail_rcu()和list_replace_rcu()原語都是對非RCU版本的模擬，但是在弱順序的機器上回帶來額外的內(nèi)存屏障開銷。list_del_rcu()原語同樣是非RCU版本的模擬，但是奇怪的是它要比非RCU版本快一點，這是由于list_del_rcu()只毒化prev指針，而list_del()會同時毒化prev和next指針。最后，list_splice_init_rcu()原語和它的非RCU版本類似，但是會帶來一個完整的優(yōu)雅周期的延遲。

表中的第二類API直接作用于Linux的struct hlist_head線性哈希表。struct hlist_head比structlist_head高級一點的地方是前者只需要一個單指針的鏈表頭部，這在大型哈希表中將節(jié)省大量內(nèi)存。表中的struct hlist_head原語與非RCU版本的關(guān)系同struct list_head原語的類似關(guān)系一樣。

表中的最后一類API直接作用于指針，這對創(chuàng)建受RCU保護的非鏈表數(shù)據(jù)元素非常有用，比如受RCU保護的數(shù)組和樹。rcu_assign_pointer()原語確保在弱序機器上，任何在給指針賦值之前進行的初始化都將按照順序執(zhí)行。同樣，rcu_dereferece()原語確保后續(xù)指針解引用的代碼可以在Alpha CPU上看見對應的rcu_assign_pointer()之前進行的初始化的結(jié)果。