Linux內(nèi)核中RCU的用法

一、RCU的法

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

讀寫鎖

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

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

窮人版的垃圾回收器

存在擔(dān)保

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

等待事物結(jié)束

1.1 RCU是讀寫鎖的替代者

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

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

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

上圖是不是略顯奇怪，RCU讀端延遲竟然小于一個(gè)CPU周期？這不是開玩笑，因?yàn)橛心承?shí)現(xiàn)中（例如，服務(wù)器Linux），RCU讀端就完全是一個(gè)空操作。當(dāng)然，在這樣的實(shí)現(xiàn)中，它可能會(huì)包含一個(gè)編譯屏障，因此也會(huì)對性能產(chǎn)生那么一點(diǎn)點(diǎn)影響。

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

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

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

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

另外，RCU讀端原語基本上是不會(huì)死鎖的。因?yàn)樗旧砭蛯儆跓o鎖編程的范疇。

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

RCU讀端免于死鎖的能力帶來了一個(gè)有趣的后果：RCU讀者可以恣意地升級為RCU更新者。在讀寫鎖中嘗試這種升級則會(huì)有可能造成死鎖。進(jìn)行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()是在鎖的保護(hù)下執(zhí)行，也是在RCU讀端的保護(hù)下執(zhí)行。

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

另一方面，因?yàn)镽CU讀端原語既不自旋也不阻塞，所以這些原語有著極佳的實(shí)時(shí)延遲。而自旋鎖或者讀寫鎖都存在不確定的實(shí)時(shí)延遲。

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

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

不過，令人吃驚的是，在大量情景中，數(shù)據(jù)不一致和舊數(shù)據(jù)都不是問題。網(wǎng)絡(luò)路由表是一個(gè)經(jīng)典例子。因?yàn)槁酚傻母驴赡芤ㄏ喈?dāng)長一段時(shí)間才能到達(dá)指定系統(tǒng)（幾秒甚至幾分鐘），所以系統(tǒng)可能會(huì)在新數(shù)據(jù)到來后的一段時(shí)間內(nèi)，仍然將報(bào)文發(fā)到錯(cuò)誤的地址去。通常，在幾毫秒內(nèi)將報(bào)文發(fā)送到錯(cuò)誤地址并不算什么問題。

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

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

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

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

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

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

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àn)橄鄳?yīng)的優(yōu)雅周期無法在配對的rcu_read_unlock()之前結(jié)束。這種引用計(jì)數(shù)機(jī)制是受限制的，因?yàn)槲覀儾辉试S在RCU讀端臨界區(qū)中阻塞，也不允許將一個(gè)任務(wù)的RCU讀端臨界區(qū)傳遞給另一個(gè)任務(wù)。

不管上述的限制，下列代碼可以安全地刪除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);

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

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

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

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

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

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

當(dāng)人們剛開始學(xué)習(xí)RCU時(shí)，有種比較少見的感嘆是“RCU有點(diǎn)像垃圾回收器！”。這種感嘆有一部分是對的，不過還是會(huì)給學(xué)習(xí)造成誤導(dǎo)。

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

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

1.5 RCU是一種提供存在擔(dān)保的方法

通過鎖來提供存在擔(dān)保有其不利之處。與鎖類似，如果任何受RCU保護(hù)的數(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的存在擔(dān)保如何通過從哈希表刪除元素的函數(shù)來實(shí)現(xiàn)每數(shù)據(jù)元素鎖。第6行計(jì)算哈希函數(shù)，第7行進(jìn)入RCU讀端臨界區(qū)。如果第9行發(fā)現(xiàn)哈希表對應(yīng)的哈希項(xiàng)（bucket）為空，或者數(shù)據(jù)元素不是我們想要?jiǎng)h除的那個(gè)，那么第10行退出RCU讀端臨界區(qū)，第11行返回錯(cuò)誤。

如果第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行返回錯(cuò)誤以刪除該關(guān)鍵字。

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

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

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

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

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

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

1．做出改變，比如，OS對一個(gè)NMI做出反應(yīng)。在NMI中使用RCU讀端原語。

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

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

下面是一個(gè)Linux內(nèi)核中的例子。在這個(gè)例子中，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)，包含一個(gè)大小和一個(gè)變長數(shù)組的入口。第5行定義了指向profile_buffer的指針，這里假設(shè)別處對該指針進(jìn)行了初始化，指向內(nèi)存的動(dòng)態(tài)分配區(qū)。

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

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

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

二、RCU API

2.1 等待完成的API族

“RCU Classic”一列對應(yīng)的是RCU的原始實(shí)現(xiàn)，rcu_read_lock()和rcu_read_unlock()原語標(biāo)示出RCU讀端臨界區(qū)，可以嵌套使用。對應(yīng)的同步的更新端原語synchronize_rcu()和synchronize_net()都是等待當(dāng)前正在執(zhí)行的RCU讀端臨界區(qū)退出。等待時(shí)間被稱為“優(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()。有一點(diǎn)很重要，SLAB_DESTROY_BY_RCU不會(huì)阻止kmem_cache_alloc()立即重新分配剛被kmem_cache_free()釋放的內(nèi)存！事實(shí)上，由rcu_dereference返回的受SLAB_DESTROY_ BY_RCU標(biāo)記保護(hù)的數(shù)據(jù)結(jié)構(gòu)可能會(huì)釋放——重新分配任意次，甚至在rcu_read_lock()保護(hù)下也是如此。但是，SLAB_DESTROY_BY_RCU可以阻止kmem_cache_free()在RCU優(yōu)雅周期結(jié)束之前，它所返回?cái)?shù)據(jù)結(jié)構(gòu)的完全釋放給SLAB。一句話，雖然數(shù)據(jù)元素可能被釋放——重新分配N次，但是它的類型是保持不變的。

2.2 訂閱和版本維護(hù)API

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

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

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