基于Linux內(nèi)核源碼的RCU實(shí)現(xiàn)方案

RCU（Read-Copy Update）是數(shù)據(jù)同步的一種方式，在當(dāng)前的Linux內(nèi)核中發(fā)揮著重要的作用。RCU主要針對(duì)的數(shù)據(jù)對(duì)象是鏈表，目的是提高遍歷讀取數(shù)據(jù)的效率，為了達(dá)到目的使用RCU機(jī)制讀取數(shù)據(jù)的時(shí)候不對(duì)鏈表進(jìn)行耗時(shí)的加鎖操作。這樣在同一時(shí)間可以有多個(gè)線程同時(shí)讀取該鏈表，并且允許一個(gè)線程對(duì)鏈表進(jìn)行修改（修改的時(shí)候，需要加鎖）。RCU適用于需要頻繁的讀取數(shù)據(jù)，而相應(yīng)修改數(shù)據(jù)并不多的情景，例如在文件系統(tǒng)中，經(jīng)常需要查找定位目錄，而對(duì)目錄的修改相對(duì)來(lái)說(shuō)并不多，這就是RCU發(fā)揮作用的最佳場(chǎng)景。

Linux內(nèi)核源碼當(dāng)中,關(guān)于RCU的文檔比較齊全，你可以在 /Documentation/RCU/ 目錄下找到這些文件。Paul E. McKenney 是內(nèi)核中RCU源碼的主要實(shí)現(xiàn)者，他也寫了很多RCU方面的文章。他把這些文章和一些關(guān)于RCU的論文的鏈接整理到了一起。http://www2.rdrop.com/users/paulmck/RCU/

在RCU的實(shí)現(xiàn)過(guò)程中，我們主要解決以下問(wèn)題：

1，在讀取過(guò)程中，另外一個(gè)線程刪除了一個(gè)節(jié)點(diǎn)。刪除線程可以把這個(gè)節(jié)點(diǎn)從鏈表中移除，但它不能直接銷毀這個(gè)節(jié)點(diǎn)，必須等到所有的讀取線程讀取完成以后，才進(jìn)行銷毀操作。RCU中把這個(gè)過(guò)程稱為寬限期（Grace period）。

2，在讀取過(guò)程中，另外一個(gè)線程插入了一個(gè)新節(jié)點(diǎn)，而讀線程讀到了這個(gè)節(jié)點(diǎn)，那么需要保證讀到的這個(gè)節(jié)點(diǎn)是完整的。這里涉及到了發(fā)布-訂閱機(jī)制（Publish-Subscribe Mechanism）。

3， 保證讀取鏈表的完整性。新增或者刪除一個(gè)節(jié)點(diǎn)，不至于導(dǎo)致遍歷一個(gè)鏈表從中間斷開(kāi)。但是RCU并不保證一定能讀到新增的節(jié)點(diǎn)或者不讀到要被刪除的節(jié)點(diǎn)。

寬限期

通過(guò)例子，方便理解這個(gè)內(nèi)容。以下例子修改于Paul的文章。

[cpp]view plaincopy

structfoo{

inta;

charb;

longc;

};

DEFINE_SPINLOCK(foo_mutex);

structfoo*gbl_foo;

voidfoo_read(void)

{

foo*fp=gbl_foo;

if(fp!=NULL)

dosomething(fp->a,fp->b,fp->c);

}

voidfoo_update(foo*new_fp)

{

spin_lock(&foo_mutex);

foo*old_fp=gbl_foo;

gbl_foo=new_fp;

spin_unlock(&foo_mutex);

kfee(old_fp);

}

如上的程序，是針對(duì)于全局變量gbl_foo的操作。假設(shè)以下場(chǎng)景。有兩個(gè)線程同時(shí)運(yùn)行 foo_ read和foo_update的時(shí)候，當(dāng)foo_ read執(zhí)行完賦值操作后，線程發(fā)生切換；此時(shí)另一個(gè)線程開(kāi)始執(zhí)行foo_update并執(zhí)行完成。當(dāng)foo_ read運(yùn)行的進(jìn)程切換回來(lái)后，運(yùn)行dosomething 的時(shí)候，fp已經(jīng)被刪除，這將對(duì)系統(tǒng)造成危害。為了防止此類事件的發(fā)生，RCU里增加了一個(gè)新的概念叫寬限期（Grace period）。如下圖所示：

圖中每行代表一個(gè)線程，最下面的一行是刪除線程，當(dāng)它執(zhí)行完刪除操作后，線程進(jìn)入了寬限期。寬限期的意義是，在一個(gè)刪除動(dòng)作發(fā)生后，它必須等待所有在寬限期開(kāi)始前已經(jīng)開(kāi)始的讀線程結(jié)束，才可以進(jìn)行銷毀操作。這樣做的原因是這些線程有可能讀到了要?jiǎng)h除的元素。圖中的寬限期必須等待1和2結(jié)束；而讀線程5在寬限期開(kāi)始前已經(jīng)結(jié)束，不需要考慮；而3,4,6也不需要考慮，因?yàn)樵趯捪奁诮Y(jié)束后開(kāi)始后的線程不可能讀到已刪除的元素。為此RCU機(jī)制提供了相應(yīng)的API來(lái)實(shí)現(xiàn)這個(gè)功能。

[cpp]view plaincopy

voidfoo_read(void)

{

rcu_read_lock();

foo*fp=gbl_foo;

if(fp!=NULL)

dosomething(fp->a,fp->b,fp->c);

rcu_read_unlock();

}

voidfoo_update(foo*new_fp)

{

spin_lock(&foo_mutex);

foo*old_fp=gbl_foo;

gbl_foo=new_fp;

spin_unlock(&foo_mutex);

synchronize_rcu();

kfee(old_fp);

}

其中foo_read中增加了rcu_read_lock和rcu_read_unlock，這兩個(gè)函數(shù)用來(lái)標(biāo)記一個(gè)RCU讀過(guò)程的開(kāi)始和結(jié)束。其實(shí)作用就是幫助檢測(cè)寬限期是否結(jié)束。foo_update增加了一個(gè)函數(shù)synchronize_rcu()，調(diào)用該函數(shù)意味著一個(gè)寬限期的開(kāi)始，而直到寬限期結(jié)束，該函數(shù)才會(huì)返回。我們?cè)賹?duì)比著圖看一看，線程1和2，在synchronize_rcu之前可能得到了舊的gbl_foo，也就是foo_update中的old_fp，如果不等它們運(yùn)行結(jié)束，就調(diào)用kfee(old_fp)，極有可能造成系統(tǒng)崩潰。而3,4,6在synchronize_rcu之后運(yùn)行，此時(shí)它們已經(jīng)不可能得到old_fp，此次的kfee將不對(duì)它們產(chǎn)生影響。

寬限期是RCU實(shí)現(xiàn)中最復(fù)雜的部分,原因是在提高讀數(shù)據(jù)性能的同時(shí)，刪除數(shù)據(jù)的性能也不能太差。

訂閱——發(fā)布機(jī)制

當(dāng)前使用的編譯器大多會(huì)對(duì)代碼做一定程度的優(yōu)化，CPU也會(huì)對(duì)執(zhí)行指令做一些優(yōu)化調(diào)整,目的是提高代碼的執(zhí)行效率，但這樣的優(yōu)化，有時(shí)候會(huì)帶來(lái)不期望的結(jié)果。如例：

[cpp]view plaincopy

voidfoo_update(foo*new_fp)

{

spin_lock(&foo_mutex);

foo*old_fp=gbl_foo;

new_fp->a=1;

new_fp->b=‘b’;

new_fp->c=100;

gbl_foo=new_fp;

spin_unlock(&foo_mutex);

synchronize_rcu();

kfee(old_fp);

}

這段代碼中，我們期望的是6，7，8行的代碼在第10行代碼之前執(zhí)行。但優(yōu)化后的代碼并不對(duì)執(zhí)行順序做出保證。在這種情形下，一個(gè)讀線程很可能讀到 new_fp，但new_fp的成員賦值還沒(méi)執(zhí)行完成。當(dāng)讀線程執(zhí)行dosomething(fp->a, fp->b , fp->c ) 的 時(shí)候，就有不確定的參數(shù)傳入到dosomething，極有可能造成不期望的結(jié)果，甚至程序崩潰。可以通過(guò)優(yōu)化屏障來(lái)解決該問(wèn)題，RCU機(jī)制對(duì)優(yōu)化屏障做了包裝，提供了專用的API來(lái)解決該問(wèn)題。這時(shí)候，第十行不再是直接的指針賦值，而應(yīng)該改為 :

rcu_assign_pointer(gbl_foo,new_fp);

rcu_assign_pointer的實(shí)現(xiàn)比較簡(jiǎn)單，如下：

[cpp]view plaincopy

#definercu_assign_pointer(p,v)

__rcu_assign_pointer((p),(v),__rcu)

#define__rcu_assign_pointer(p,v,space)

do{

smp_wmb();

(p)=(typeof(*v)__forcespace*)(v);

}while(0)

我們可以看到它的實(shí)現(xiàn)只是在賦值之前加了優(yōu)化屏障 smp_wmb來(lái)確保代碼的執(zhí)行順序。另外就是宏中用到的__rcu，只是作為編譯過(guò)程的檢測(cè)條件來(lái)使用的。

在DEC Alpha CPU機(jī)器上還有一種更強(qiáng)悍的優(yōu)化，如下所示：

[cpp]view plaincopy

voidfoo_read(void)

{

rcu_read_lock();

foo*fp=gbl_foo;

if(fp!=NULL)

dosomething(fp->a,fp->b,fp->c);

rcu_read_unlock();

}

第六行的fp->a,fp->b,fp->c會(huì)在第3行還沒(méi)執(zhí)行的時(shí)候就預(yù)先判斷運(yùn)行，當(dāng)他和foo_update同時(shí)運(yùn)行的時(shí)候，可能導(dǎo)致傳入dosomething的一部分屬于舊的gbl_foo，而另外的屬于新的。這樣導(dǎo)致運(yùn)行結(jié)果的錯(cuò)誤。為了避免該類問(wèn)題，RCU還是提供了宏來(lái)解決該問(wèn)題：

[cpp]view plaincopy

#definercu_dereference(p)rcu_dereference_check(p,0)

#definercu_dereference_check(p,c)

__rcu_dereference_check((p),rcu_read_lock_held()||(c),__rcu)

#define__rcu_dereference_check(p,c,space)

({

typeof(*p)*_________p1=(typeof(*p)*__force)ACCESS_ONCE(p);

rcu_lockdep_assert(c,"suspiciousrcu_dereference_check()"

"usage");

rcu_dereference_sparse(p,space);

smp_read_barrier_depends();

((typeof(*p)__force__kernel*)(_________p1));

})

staticinlineintrcu_read_lock_held(void)

{

if(!debug_lockdep_rcu_enabled())

return1;

if(rcu_is_cpu_idle())

return0;

if(!rcu_lockdep_current_cpu_online())

return0;

returnlock_is_held(&rcu_lock_map);

}

這段代碼中加入了調(diào)試信息，去除調(diào)試信息，可以是以下的形式（其實(shí)這也是舊版本中的代碼）：

[cpp]view plaincopy

#definercu_dereference(p)({

typeof(p)_________p1=p;

smp_read_barrier_depends();

(_________p1);

})

在賦值后加入優(yōu)化屏障smp_read_barrier_depends()。

我們之前的第四行代碼改為foo *fp = rcu_dereference(gbl_foo);，就可以防止上述問(wèn)題。

數(shù)據(jù)讀取的完整性

還是通過(guò)例子來(lái)說(shuō)明這個(gè)問(wèn)題：

如圖我們?cè)谠璴ist中加入一個(gè)節(jié)點(diǎn)new到A之前，所要做的第一步是將new的指針指向A節(jié)點(diǎn)，第二步才是將Head的指針指向new。這樣做的目的是當(dāng)插入操作完成第一步的時(shí)候，對(duì)于鏈表的讀取并不產(chǎn)生影響，而執(zhí)行完第二步的時(shí)候，讀線程如果讀到new節(jié)點(diǎn)，也可以繼續(xù)遍歷鏈表。如果把這個(gè)過(guò)程反過(guò)來(lái)，第一步head指向new，而這時(shí)一個(gè)線程讀到new，由于new的指針指向的是Null，這樣將導(dǎo)致讀線程無(wú)法讀取到A，B等后續(xù)節(jié)點(diǎn)。從以上過(guò)程中，可以看出RCU并不保證讀線程讀取到new節(jié)點(diǎn)。如果該節(jié)點(diǎn)對(duì)程序產(chǎn)生影響，那么就需要外部調(diào)用做相應(yīng)的調(diào)整。如在文件系統(tǒng)中，通過(guò)RCU定位后，如果查找不到相應(yīng)節(jié)點(diǎn)，就會(huì)進(jìn)行其它形式的查找，相關(guān)內(nèi)容等分析到文件系統(tǒng)的時(shí)候再進(jìn)行敘述。

我們?cè)倏匆幌聞h除一個(gè)節(jié)點(diǎn)的例子：

如圖我們希望刪除B，這時(shí)候要做的就是將A的指針指向C，保持B的指針，然后刪除程序?qū)⑦M(jìn)入寬限期檢測(cè)。由于B的內(nèi)容并沒(méi)有變更，讀到B的線程仍然可以繼續(xù)讀取B的后續(xù)節(jié)點(diǎn)。B不能立即銷毀，它必須等待寬限期結(jié)束后，才能進(jìn)行相應(yīng)銷毀操作。由于A的節(jié)點(diǎn)已經(jīng)指向了C，當(dāng)寬限期開(kāi)始之后所有的后續(xù)讀操作通過(guò)A找到的是C，而B(niǎo)已經(jīng)隱藏了，后續(xù)的讀線程都不會(huì)讀到它。這樣就確保寬限期過(guò)后，刪除B并不對(duì)系統(tǒng)造成影響。

小結(jié)

RCU的原理并不復(fù)雜，應(yīng)用也很簡(jiǎn)單。但代碼的實(shí)現(xiàn)確并不是那么容易，難點(diǎn)都集中在了寬限期的檢測(cè)上，后續(xù)分析源代碼的時(shí)候，我們可以看到一些極富技巧的實(shí)現(xiàn)方式。