Linux 2.6內(nèi)核中新的鎖機(jī)制--RCU 打印本頁(yè)
級(jí)別： 初級(jí)
楊燚 yang.yi@bmrtech.com
2005 年 7 月 01 日
本文詳細(xì)地介紹了 Linux 2.6 內(nèi)核中新的鎖機(jī)制 RCU(Read-Copy Update) 的實(shí)現(xiàn)機(jī)制，使用要求與典型應(yīng)用。 一、 引言
眾所周知，為了保護(hù)共享數(shù)據(jù),需要一些同步機(jī)制,如自旋鎖(spinlock)，讀寫(xiě)鎖(rwlock)，它們使用起來(lái)非常簡(jiǎn)單,而且是一種很有效的同步機(jī)制，在UNIX系統(tǒng)和Linux系統(tǒng)中得到了廣泛的使用。但是隨著計(jì)算機(jī)硬件的快速發(fā)展，獲得這種鎖的開(kāi)銷(xiāo)相對(duì)于CPU的速度在成倍地增加，原因很簡(jiǎn)單，CPU的速度與訪問(wèn)內(nèi)存的速度差距越來(lái)越大，而這種鎖使用了原子操作指令，它需要原子地訪問(wèn)內(nèi)存，也就說(shuō)獲得鎖的開(kāi)銷(xiāo)與訪存速度相關(guān)，另外在大部分非x86架構(gòu)上獲取鎖使用了內(nèi)存柵(Memory Barrier)，這會(huì)導(dǎo)致處理器流水線停滯或刷新，因此它的開(kāi)銷(xiāo)相對(duì)于CPU速度而言就越來(lái)越大。表1數(shù)據(jù)證明了這一點(diǎn)。
表1是在700MHz的奔騰III機(jī)器上的基本操作的開(kāi)銷(xiāo)，在該機(jī)器上一個(gè)時(shí)鐘周期能夠執(zhí)行兩條整數(shù)指令。在1.8GHz的奔騰4機(jī)器上, 原子加1指令的開(kāi)銷(xiāo)要比700MHz的奔騰III機(jī)器慢75納秒(ns)，盡管CPU速度快兩倍多。
這種鎖機(jī)制的另一個(gè)問(wèn)題在于其可擴(kuò)展性，在多處理器系統(tǒng)上，可擴(kuò)展性非常重要，否則根本無(wú)法發(fā)揮其性能。圖1表明了Linux上各種鎖的擴(kuò)展性。
圖 1 Linux的4種鎖機(jī)制的擴(kuò)展性 注：refcnt表示自旋鎖與引用記數(shù)一起使用。
讀寫(xiě)鎖rwlock在兩個(gè)CPU的情況下性能反倒比一個(gè)CPU的差，在四個(gè)CPU的情況下，refcnt的性能要高于rwlock，refcnt大約是理論性能的45%，而rwlock是理論性能的39%,自旋縮spinlock的性能明顯好于refcnt和rwlock，但它也只達(dá)到了理性性能的57%，brlock（Big Reader Lock）性能可以線性擴(kuò)展。Brlock是由Redhat的Ingo Molnar實(shí)現(xiàn)的一個(gè)高性能的rwlock，它適用于讀特多而寫(xiě)特少的情況，讀者獲得brlock的開(kāi)銷(xiāo)很低，但寫(xiě)者獲得鎖的開(kāi)銷(xiāo)非常大，而且它只預(yù)定義了幾個(gè)鎖，用戶(hù)無(wú)法隨便定義并使用這種鎖，它也需要為每個(gè)CPU定義一個(gè)鎖狀態(tài)數(shù)組，因此這種鎖并沒(méi)有被作為rwlock的替代方案廣泛使用，只是在一些特別的地方使用到。
正是在這種背景下，一個(gè)高性能的鎖機(jī)制RCU呼之欲出，它克服了以上鎖的缺點(diǎn)，具有很好的擴(kuò)展性，但是這種鎖機(jī)制的使用范圍比較窄，它只適用于讀多寫(xiě)少的情況，如網(wǎng)絡(luò)路由表的查詢(xún)更新、設(shè)備狀態(tài)表的維護(hù)、數(shù)據(jù)結(jié)構(gòu)的延遲釋放以及多徑I/O設(shè)備的維護(hù)等。
RCU并不是新的鎖機(jī)制，它只是對(duì)Linux內(nèi)核而言是新的。早在二十世紀(jì)八十年代就有了這種機(jī)制，而且在生產(chǎn)系 統(tǒng)中使用了這種機(jī)制，但這種早期的實(shí)現(xiàn)并不太好，在二十世紀(jì)九十年代出現(xiàn)了一個(gè)比較高效的實(shí)現(xiàn)，而在linux中是在開(kāi)發(fā)內(nèi)核2.5.43中引入該技術(shù)的并正式包含在2.6內(nèi)核中。
回頁(yè)首 二、RCU的原理
RCU(Read-Copy Update)，顧名思義就是讀-拷貝修改，它是基于其原理命名的。對(duì)于被RCU保護(hù)的共享數(shù)據(jù)結(jié)構(gòu)，讀者不需要獲得任何鎖就可以訪問(wèn)它，但寫(xiě)者在訪問(wèn)它時(shí)首先拷貝一個(gè)副本，然后對(duì)副本進(jìn)行修改，最后使用一個(gè)回調(diào)（callback）機(jī)制在適當(dāng)?shù)臅r(shí)機(jī)把指向原來(lái)數(shù)據(jù)的指針重新指向新的被修改的數(shù)據(jù)。這個(gè)時(shí)機(jī)就是所有引用該數(shù)據(jù)的CPU都退出對(duì)共享數(shù)據(jù)的操作。
因此RCU實(shí)際上是一種改進(jìn)的rwlock，讀者幾乎沒(méi)有什么同步開(kāi)銷(xiāo)，它不需要鎖，不使用原子指令，而且在除alpha的所有架構(gòu)上也不需要內(nèi)存柵（Memory Barrier），因此不會(huì)導(dǎo)致鎖競(jìng)爭(zhēng)，內(nèi)存延遲以及流水線停滯。不需要鎖也使得使用更容易，因?yàn)樗梨i問(wèn)題就不需要考慮了。寫(xiě)者的同步開(kāi)銷(xiāo)比較大，它需要延遲數(shù)據(jù)結(jié)構(gòu)的釋放，復(fù)制被修改的數(shù)據(jù)結(jié)構(gòu)，它也必須使用某種鎖機(jī)制同步并行的其它寫(xiě)者的修改操作。讀者必須提供一個(gè)信號(hào)給寫(xiě)者以便寫(xiě)者能夠確定數(shù)據(jù)可以被安全地釋放或修改的時(shí)機(jī)。有一個(gè)專(zhuān)門(mén)的垃圾收集器來(lái)探測(cè)讀者的信號(hào)，一旦所有的讀者都已經(jīng)發(fā)送信號(hào)告知它們都不在使用被RCU保護(hù)的數(shù)據(jù)結(jié)構(gòu)，垃圾收集器就調(diào)用回調(diào)函數(shù)完成最后的數(shù)據(jù)釋放或修改操作。 RCU與rwlock的不同之處是：它既允許多個(gè)讀者同時(shí)訪問(wèn)被保護(hù)的數(shù)據(jù)，又允許多個(gè)讀者和多個(gè)寫(xiě)者同時(shí)訪問(wèn)被保護(hù)的數(shù)據(jù)（注意：是否可以有多個(gè)寫(xiě)者并行訪問(wèn)取決于寫(xiě)者之間使用的同步機(jī)制），讀者沒(méi)有任何同步開(kāi)銷(xiāo)，而寫(xiě)者的同步開(kāi)銷(xiāo)則取決于使用的寫(xiě)者間同步機(jī)制。但RCU不能替代rwlock，因?yàn)槿绻麑?xiě)比較多時(shí)，對(duì)讀者的性能提高不能彌補(bǔ)寫(xiě)者導(dǎo)致的損失。
讀者在訪問(wèn)被RCU保護(hù)的共享數(shù)據(jù)期間不能被阻塞，這是RCU機(jī)制得以實(shí)現(xiàn)的一個(gè)基本前提，也就說(shuō)當(dāng)讀者在引用被RCU保護(hù)的共享數(shù)據(jù)期間，讀者所在的CPU不能發(fā)生上下文切換，spinlock和rwlock都需要這樣的前提。寫(xiě)者在訪問(wèn)被RCU保護(hù)的共享數(shù)據(jù)時(shí)不需要和讀者競(jìng)爭(zhēng)任何鎖，只有在有多于一個(gè)寫(xiě)者的情況下需要獲得某種鎖以與其他寫(xiě)者同步。寫(xiě)者修改數(shù)據(jù)前首先拷貝一個(gè)被修改元素的副本，然后在副本上進(jìn)行修改，修改完畢后它向垃圾回收器注冊(cè)一個(gè)回調(diào)函數(shù)以便在適當(dāng)?shù)臅r(shí)機(jī)執(zhí)行真正的修改操作。等待適當(dāng)時(shí)機(jī)的這一時(shí)期稱(chēng)為grace period，而CPU發(fā)生了上下文切換稱(chēng)為經(jīng)歷一個(gè)quiescent state，grace period就是所有CPU都經(jīng)歷一次quiescent state所需要的等待的時(shí)間。垃圾收集器就是在grace period之后調(diào)用寫(xiě)者注冊(cè)的回調(diào)函數(shù)來(lái)完成真正的數(shù)據(jù)修改或數(shù)據(jù)釋放操作的。
以下以鏈表元素刪除為例詳細(xì)說(shuō)明這一過(guò)程。
寫(xiě)者要從鏈表中刪除元素 B，它首先遍歷該鏈表得到指向元素 B 的指針，然后修改元素 B 的前一個(gè)元素的 next 指針指向元素 B 的 next 指針指向的元素C，修改元素 B 的 next 指針指向的元素 C 的 prep 指針指向元素 B 的 prep指針指向的元素 A,在這期間可能有讀者訪問(wèn)該鏈表，修改指針指向的操作是原子的，所以不需要同步，而元素 B 的指針并沒(méi)有去修改，因?yàn)樽x者可能正在使用 B 元素來(lái)得到下一個(gè)或前一個(gè)元素。寫(xiě)者完成這些操作后注冊(cè)一個(gè)回調(diào)函數(shù)以便在 grace period 之后刪除元素 B，然后就認(rèn)為已經(jīng)完成刪除操作。垃圾收集器在檢測(cè)到所有的CPU不在引用該鏈表后，即所有的 CPU 已經(jīng)經(jīng)歷了 quiescent state,grace period 已經(jīng)過(guò)去后，就調(diào)用剛才寫(xiě)者注冊(cè)的回調(diào)函數(shù)刪除了元素 B。
圖 2 使用 RCU 進(jìn)行鏈表刪除操作 回頁(yè)首 三、RCU 實(shí)現(xiàn)機(jī)制
按照第二節(jié)所講原理，對(duì)于讀者，RCU 僅需要搶占失效，因此獲得讀鎖和釋放讀鎖分別定義為：
#define rcu_read_lock() preempt_disable()#define rcu_read_unlock() preempt_enable() 它們有一個(gè)變種：
#define rcu_read_lock_bh() local_bh_disable()#define rcu_read_unlock_bh() local_bh_enable() 這個(gè)變種只在修改是通過(guò) call_rcu_bh 進(jìn)行的情況下使用，因?yàn)?call_rcu_bh將把 softirq 的執(zhí)行完畢也認(rèn)為是一個(gè) quiescent state，因此如果修改是通過(guò) call_rcu_bh 進(jìn)行的，在進(jìn)程上下文的讀端臨界區(qū)必須使用這一變種。
每一個(gè) CPU 維護(hù)兩個(gè)數(shù)據(jù)結(jié)構(gòu)rcu_data,rcu_bh_data，它們用于保存回調(diào)函數(shù)，函數(shù)call_rcu和函數(shù)call_rcu_bh用戶(hù)注冊(cè)回調(diào)函數(shù)，前者把回調(diào)函數(shù)注冊(cè)到rcu_data，而后者則把回調(diào)函數(shù)注冊(cè)到rcu_bh_data，在每一個(gè)數(shù)據(jù)結(jié)構(gòu)上，回調(diào)函數(shù)被組成一個(gè)鏈表，先注冊(cè)的排在前頭，后注冊(cè)的排在末尾。
當(dāng)在CPU上發(fā)生進(jìn)程切換時(shí)，函數(shù)rcu_qsctr_inc將被調(diào)用以標(biāo)記該CPU已經(jīng)經(jīng)歷了一個(gè)quiescent state。該函數(shù)也會(huì)被時(shí)鐘中斷觸發(fā)調(diào)用。
時(shí)鐘中斷觸發(fā)垃圾收集器運(yùn)行，它會(huì)檢查：
否在該CPU上有需要處理的回調(diào)函數(shù)并且已經(jīng)經(jīng)過(guò)一個(gè)grace period； 否沒(méi)有需要處理的回調(diào)函數(shù)但有注冊(cè)的回調(diào)函數(shù)； 否該CPU已經(jīng)完成回調(diào)函數(shù)的處理； 否該CPU正在等待一個(gè)quiescent state的到來(lái)； 如果以上四個(gè)條件只要有一個(gè)滿(mǎn)足，它就調(diào)用函數(shù)rcu_check_callbacks。
函數(shù)rcu_check_callbacks首先檢查該CPU是否經(jīng)歷了一個(gè)quiescent state，如果：
1． 當(dāng)前進(jìn)程運(yùn)行在用戶(hù)態(tài)；
2． 當(dāng)前進(jìn)程為idle且當(dāng)前不處在運(yùn)行softirq狀態(tài)，也不處在運(yùn)行IRQ處理函數(shù)的狀態(tài)；
那么，該CPU已經(jīng)經(jīng)歷了一個(gè)quiescent state，因此通過(guò)調(diào)用函數(shù)rcu_qsctr_inc標(biāo)記該CPU的數(shù)據(jù)結(jié)構(gòu)rcu_data和rcu_bh_data的標(biāo)記字段passed_quiesc，以記錄該CPU已經(jīng)經(jīng)歷一個(gè)quiescent state。
否則，如果當(dāng)前不處在運(yùn)行softirq狀態(tài)，那么，只標(biāo)記該CPU的數(shù)據(jù)結(jié)構(gòu)rcu_bh_data的標(biāo)記字段passed_quiesc，以記錄該CPU已經(jīng)經(jīng)歷一個(gè)quiescent state。注意，該標(biāo)記只對(duì)rcu_bh_data有效。
然后，函數(shù)rcu_check_callbacks將調(diào)用tasklet_schedule，它將調(diào)度為該CPU設(shè)置的tasklet rcu_tasklet，每一個(gè)CPU都有一個(gè)對(duì)應(yīng)的rcu_tasklet。
在時(shí)鐘中斷返回后，rcu_tasklet將在softirq上下文被運(yùn)行。
rcu_tasklet將運(yùn)行函數(shù)rcu_process_callbacks，函數(shù)rcu_process_callbacks可能做以下事情：
1． 開(kāi)始一個(gè)新的grace period；這通過(guò)調(diào)用函數(shù)rcu_start_batch實(shí)現(xiàn)。
2． 運(yùn)行需要處理的回調(diào)函數(shù)；這通過(guò)調(diào)用函數(shù)rcu_do_batch實(shí)現(xiàn)。
3． 檢查該CPU是否經(jīng)歷一個(gè)quiescent state；這通過(guò)函數(shù)rcu_check_quiescent_state實(shí)現(xiàn)
如果還沒(méi)有開(kāi)始grace period，就調(diào)用rcu_start_batch開(kāi)始新的grace period。調(diào)用函數(shù)rcu_check_quiescent_state檢查該CPU是否經(jīng)歷了一個(gè)quiescent state,如果是并且是最后一個(gè)經(jīng)歷quiescent state的CPU，那么就結(jié)束grace period，并開(kāi)始新的grace period。如果有完成的grace period，那么就調(diào)用rcu_do_batch運(yùn)行所有需要處理的回調(diào)函數(shù)。函數(shù)rcu_process_callbacks將對(duì)該CPU的兩個(gè)數(shù)據(jù)結(jié)構(gòu)rcu_data和rcu_bh_data執(zhí)行上述操作。
回頁(yè)首 四、RCU API
rcu_read_lock()
讀者在讀取由RCU保護(hù)的共享數(shù)據(jù)時(shí)使用該函數(shù)標(biāo)記它進(jìn)入讀端臨界區(qū)。
rcu_read_unlock()
該函數(shù)與rcu_read_lock配對(duì)使用，用以標(biāo)記讀者退出讀端臨界區(qū)。夾在這兩個(gè)函數(shù)之間的代碼區(qū)稱(chēng)為"讀端臨界區(qū)"(read-side critical section)。讀端臨界區(qū)可以嵌套，如圖3，臨界區(qū)2被嵌套在臨界區(qū)1內(nèi)。
圖 3 嵌套讀端臨界區(qū)示例 synchronize_rcu()
該函數(shù)由RCU寫(xiě)端調(diào)用，它將阻塞寫(xiě)者，直到經(jīng)過(guò)grace period后，即所有的讀者已經(jīng)完成讀端臨界區(qū)，寫(xiě)者才可以繼續(xù)下一步操作。如果有多個(gè)RCU寫(xiě)端調(diào)用該函數(shù)，他們將在一個(gè)grace period之后全部被喚醒。注意，該函數(shù)在2.6.11及以前的2.6內(nèi)核版本中為synchronize_kernel，只是在2.6.12才更名為synchronize_rcu,但在2.6.12中也提供了synchronize_kernel和一個(gè)新的函數(shù)synchronize_sched，因?yàn)橐郧坝泻芏鄡?nèi)核開(kāi)發(fā)者使用synchronize_kernel用于等待所有CPU都退出不可搶占區(qū)，而在RCU設(shè)計(jì)時(shí)該函數(shù)只是用于等待所有CPU都退出讀端臨界區(qū)，它可能會(huì)隨著RCU實(shí)現(xiàn)的修改而發(fā)生語(yǔ)意變化，因此為了預(yù)先防止這種情況發(fā)生，在新的修改中增加了專(zhuān)門(mén)的用于其它內(nèi)核用戶(hù)的synchronize_sched函數(shù)和只用于RCU使用的synchronize_rcu，現(xiàn)在建議非RCU內(nèi)核代碼部分不使用synchronize_kernel而使用synchronize_sched，RCU代碼部分則使用synchronize_rcu，synchronize_kernel之所以存在是為了保證代碼兼容性。
synchronize_kernel()
其他非RCU的內(nèi)核代碼使用該函數(shù)來(lái)等待所有CPU處在可搶占狀態(tài)，目前功能等同于synchronize_rcu，但現(xiàn)在已經(jīng)不建議使用，而使用synchronize_sched。
synchronize_sched()
該函數(shù)用于等待所有CPU都處在可搶占狀態(tài)，它能保證正在運(yùn)行的中斷處理函數(shù)處理完畢，但不能保證正在運(yùn)行的softirq處理完畢。注意，synchronize_rcu只保證所有CPU都處理完正在運(yùn)行的讀端臨界區(qū)。注：在2.6.12內(nèi)核中，synchronize_kernel和synchronize_sched都實(shí)際使用synchronize_rcu，因此當(dāng)前它們的功能實(shí)際是完全等同的，但是將來(lái)將可能有大的變化，因此務(wù)必根據(jù)需求選擇恰當(dāng)?shù)暮瘮?shù)。
void fastcall call_rcu(struct rcu_head *head, void (*func)(struct rcu_head *rcu))struct rcu_head { struct rcu_head *next; void (*func)(struct rcu_head *head);}; 函數(shù) call_rcu 也由 RCU 寫(xiě)端調(diào)用，它不會(huì)使寫(xiě)者阻塞，因而可以在中斷上下文或 softirq 使用，而 synchronize_rcu、synchronize_kernel 和synchronize_shced 只能在進(jìn)程上下文使用。該函數(shù)將把函數(shù) func 掛接到 RCU回調(diào)函數(shù)鏈上，然后立即返回。一旦所有的 CPU 都已經(jīng)完成端臨界區(qū)操作，該函數(shù)將被調(diào)用來(lái)釋放刪除的將絕不在被應(yīng)用的數(shù)據(jù)。參數(shù) head 用于記錄回調(diào)函數(shù) func，一般該結(jié)構(gòu)會(huì)作為被 RCU 保護(hù)的數(shù)據(jù)結(jié)構(gòu)的一個(gè)字段，以便省去單獨(dú)為該結(jié)構(gòu)分配內(nèi)存的操作。需要指出的是，函數(shù) synchronize_rcu 的實(shí)現(xiàn)實(shí)際上使用函數(shù)call_rcu。
void fastcall call_rcu_bh(struct rcu_head *head, void (*func)(struct rcu_head *rcu)) 函數(shù)call_ruc_bh功能幾乎與call_rcu完全相同，唯一差別就是它把softirq的完成也當(dāng)作經(jīng)歷一個(gè)quiescent state，因此如果寫(xiě)端使用了該函數(shù)，在進(jìn)程上下文的讀端必須使用rcu_read_lock_bh。
#define rcu_dereference(p) ({ \ typeof(p) _________p1 = p; \ smp_read_barrier_depends(); \ (_________p1); \ }) 該宏用于在RCU讀端臨界區(qū)獲得一個(gè)RCU保護(hù)的指針，該指針可以在以后安全地引用，內(nèi)存柵只在alpha架構(gòu)上才使用。
除了這些API，RCU還增加了鏈表操作的RCU版本，因?yàn)閷?duì)于RCU，對(duì)共享數(shù)據(jù)的操作必須保證能夠被沒(méi)有使用同步機(jī)制的讀者看到，所以?xún)?nèi)存柵是非常必要的。
static inline void list_add_rcu(struct list_head *new, struct list_head *head) 該函數(shù)把鏈表項(xiàng)new插入到RCU保護(hù)的鏈表head的開(kāi)頭。使用內(nèi)存柵保證了在引用這個(gè)新插入的鏈表項(xiàng)之前，新鏈表項(xiàng)的鏈接指針的修改對(duì)所有讀者是可見(jiàn)的。
static inline void list_add_tail_rcu(struct list_head *new, struct list_head *head) 該函數(shù)類(lèi)似于list_add_rcu，它將把新的鏈表項(xiàng)new添加到被RCU保護(hù)的鏈表的末尾。
static inline void list_del_rcu(struct list_head *entry) 該函數(shù)從RCU保護(hù)的鏈表中移走指定的鏈表項(xiàng)entry，并且把entry的prev指針設(shè)置為L(zhǎng)IST_POISON2，但是并沒(méi)有把entry的next指針設(shè)置為L(zhǎng)IST_POISON1，因?yàn)樵撝羔樋赡苋匀辉诒蛔x者用于便利該鏈表。
static inline void list_replace_rcu(struct list_head *old, struct list_head *new) 該函數(shù)是RCU新添加的函數(shù)，并不存在非RCU版本。它使用新的鏈表項(xiàng)new取代舊的鏈表項(xiàng)old，內(nèi)存柵保證在引用新的鏈表項(xiàng)之前，它的鏈接指針的修正對(duì)所有讀者可見(jiàn)。
list_for_each_rcu(pos, head) 該宏用于遍歷由RCU保護(hù)的鏈表head，只要在讀端臨界區(qū)使用該函數(shù)，它就可以安全地和其它_rcu鏈表操作函數(shù)（如list_add_rcu）并發(fā)運(yùn)行。
list_for_each_safe_rcu(pos, n, head) 該宏類(lèi)似于list_for_each_rcu，但不同之處在于它允許安全地刪除當(dāng)前鏈表項(xiàng)pos。
list_for_each_entry_rcu(pos, head, member) 該宏類(lèi)似于list_for_each_rcu，不同之處在于它用于遍歷指定類(lèi)型的數(shù)據(jù)結(jié)構(gòu)鏈表，當(dāng)前鏈表項(xiàng)pos為一包含struct list_head結(jié)構(gòu)的特定的數(shù)據(jù)結(jié)構(gòu)。
list_for_each_continue_rcu(pos, head) 該宏用于在退出點(diǎn)之后繼續(xù)遍歷由RCU保護(hù)的鏈表head。
static inline void hlist_del_rcu(struct hlist_node *n) 它從由RCU保護(hù)的哈希鏈表中移走鏈表項(xiàng)n，并設(shè)置n的ppre指針為L(zhǎng)IST_POISON2，但并沒(méi)有設(shè)置next為L(zhǎng)IST_POISON1,因?yàn)樵撝羔樋赡鼙蛔x者使用用于遍利鏈表。
static inline void hlist_add_head_rcu(struct hlist_node *n, struct hlist_head *h) 該函數(shù)用于把鏈表項(xiàng)n插入到被RCU保護(hù)的哈希鏈表的開(kāi)頭，但同時(shí)允許讀者對(duì)該哈希鏈表的遍歷。內(nèi)存柵確保在引用新鏈表項(xiàng)之前，它的指針修正對(duì)所有讀者可見(jiàn)。
hlist_for_each_rcu(pos, head) 該宏用于遍歷由RCU保護(hù)的哈希鏈表head，只要在讀端臨界區(qū)使用該函數(shù)，它就可以安全地和其它_rcu哈希鏈表操作函數(shù)（如hlist_add_rcu）并發(fā)運(yùn)行。
hlist_for_each_entry_rcu(tpos, pos, head, member) 類(lèi)似于hlist_for_each_rcu，不同之處在于它用于遍歷指定類(lèi)型的數(shù)據(jù)結(jié)構(gòu)哈希鏈表，當(dāng)前鏈表項(xiàng)pos為一包含struct list_head結(jié)構(gòu)的特定的數(shù)據(jù)結(jié)構(gòu)。
回頁(yè)首 五、RCU 典型應(yīng)用
在 linux 2.6 內(nèi)核中，RCU 被內(nèi)核使用的越來(lái)越廣泛。下面是在最新的 2.6.12內(nèi)核中搜索得到的RCU使用情況統(tǒng)計(jì)表。
表 1 rcu_read_lock 的使用情況統(tǒng)計(jì) 表 2 rcu_read_unlock 的使用情況統(tǒng)計(jì) 表 3 rcu_read_lock_bh 的使用情況統(tǒng)計(jì) 表 4 rcu_read_unlock_bh 的使用情況統(tǒng)計(jì) 表 5 call_rcu 的使用情況統(tǒng)計(jì) 表 6 call_rcu_bh 的使用情況統(tǒng)計(jì) 表 7 list API 的使用情況統(tǒng)計(jì) 表 8 synchronize_rcu 的使用情況統(tǒng)計(jì) 表 9 rcu_dereferance 的使用情況統(tǒng)計(jì) 從以上統(tǒng)計(jì)結(jié)果可以看出，RCU已經(jīng)在網(wǎng)絡(luò)驅(qū)動(dòng)層、網(wǎng)絡(luò)核心層、IPC、dcache、內(nèi)存設(shè)備層、軟RAID層、系統(tǒng)調(diào)用審計(jì)和SELinux中使用。從所有RCU API的使用統(tǒng)計(jì)匯總（表 10），不難看出，RCU已經(jīng)是一個(gè)非常重要的內(nèi)核鎖機(jī)制。
表 10 所有RCU API使用情況總匯 因此，如何正確使用 RCU 對(duì)于內(nèi)核開(kāi)發(fā)者而言非常重要。
下面部分將就 RCU 的幾種典型應(yīng)用情況詳細(xì)講解。
1．只有增加和刪除的鏈表操作
在這種應(yīng)用情況下，絕大部分是對(duì)鏈表的遍歷，即讀操作，而很少出現(xiàn)的寫(xiě)操作只有增加或刪除鏈表項(xiàng)，并沒(méi)有對(duì)鏈表項(xiàng)的修改操作，這種情況使用RCU非常容易，從rwlock轉(zhuǎn)換成RCU非常自然。路由表的維護(hù)就是這種情況的典型應(yīng)用，對(duì)路由表的操作，絕大部分是路由表查詢(xún)，而對(duì)路由表的寫(xiě)操作也僅僅是增加或刪除，因此使用RCU替換原來(lái)的rwlock順理成章。系統(tǒng)調(diào)用審計(jì)也是這樣的情況。
這是一段使用rwlock的系統(tǒng)調(diào)用審計(jì)部分的讀端代碼：
static enum audit_state audit_filter_task(struct task_struct *tsk) { struct audit_entry *e; enum audit_state state; read_lock(&auditsc_lock); /* Note: audit_netlink_sem held by caller. */ list_for_each_entry(e, &audit_tsklist, list) { if (audit_filter_rules(tsk, &e->rule, NULL, &state)) { read_unlock(&auditsc_lock); return state; } } read_unlock(&auditsc_lock); return AUDIT_BUILD_CONTEXT; } 使用RCU后將變成：
static enum audit_state audit_filter_task(struct task_struct *tsk) { struct audit_entry *e; enum audit_state state; rcu_read_lock(); /* Note: audit_netlink_sem held by caller. */ list_for_each_entry_rcu(e, &audit_tsklist, list) { if (audit_filter_rules(tsk, &e->rule, NULL, &state)) { rcu_read_unlock(); return state; } } rcu_read_unlock(); return AUDIT_BUILD_CONTEXT; } 這種轉(zhuǎn)換非常直接，使用rcu_read_lock和rcu_read_unlock分別替換read_lock和read_unlock，鏈表遍歷函數(shù)使用_rcu版本替換就可以了。
使用rwlock的寫(xiě)端代碼：
static inline int audit_del_rule(struct audit_rule *rule, struct list_head *list) { struct audit_entry *e; write_lock(&auditsc_lock); list_for_each_entry(e, list, list) { if (!audit_compare_rule(rule, &e->rule)) { list_del(&e->list); write_unlock(&auditsc_lock); return 0; } } write_unlock(&auditsc_lock); return -EFAULT; /* No matching rule */ } static inline int audit_add_rule(struct audit_entry *entry, struct list_head *list) { write_lock(&auditsc_lock); if (entry->rule.flags & AUDIT_PREPEND) { entry->rule.flags &= ~AUDIT_PREPEND; list_add(&entry->list, list); } else { list_add_tail(&entry->list, list); } write_unlock(&auditsc_lock); return 0; } 使用RCU后寫(xiě)端代碼變成為：
static inline int audit_del_rule(struct audit_rule *rule, struct list_head *list) { struct audit_entry *e; /* Do not use the _rcu iterator here, since this is the only * deletion routine. */ list_for_each_entry(e, list, list) { if (!audit_compare_rule(rule, &e->rule)) { list_del_rcu(&e->list); call_rcu(&e->rcu, audit_free_rule, e); return 0; } } return -EFAULT; /* No matching rule */ } static inline int audit_add_rule(struct audit_entry *entry, struct list_head *list) { if (entry->rule.flags & AUDIT_PREPEND) { entry->rule.flags &= ~AUDIT_PREPEND; list_add_rcu(&entry->list, list); } else { list_add_tail_rcu(&entry->list, list); } return 0; } 對(duì)于鏈表刪除操作，list_del替換為list_del_rcu和call_rcu，這是因?yàn)楸粍h除的鏈表項(xiàng)可能還在被別的讀者引用，所以不能立即刪除，必須等到所有讀者經(jīng)歷一個(gè)quiescent state才可以刪除。另外，list_for_each_entry并沒(méi)有被替換為list_for_each_entry_rcu，這是因?yàn)�，只有一個(gè)寫(xiě)者在做鏈表刪除操作，因此沒(méi)有必要使用_rcu版本。
通常情況下，write_lock和write_unlock應(yīng)當(dāng)分別替換成spin_lock和spin_unlock，但是對(duì)于只是對(duì)鏈表進(jìn)行增加和刪除操作而且只有一個(gè)寫(xiě)者的寫(xiě)端，在使用了_rcu版本的鏈表操作API后，rwlock可以完全消除，不需要spinlock來(lái)同步讀者的訪問(wèn)。對(duì)于上面的例子，由于已經(jīng)有audit_netlink_sem被調(diào)用者保持，所以spinlock就沒(méi)有必要了。
這種情況允許修改結(jié)果延后一定時(shí)間才可見(jiàn)，而且寫(xiě)者對(duì)鏈表僅僅做增加和刪除操作，所以轉(zhuǎn)換成使用RCU非常容易。
2．寫(xiě)端需要對(duì)鏈表?xiàng)l目進(jìn)行修改操作
如果寫(xiě)者需要對(duì)鏈表?xiàng)l目進(jìn)行修改，那么就需要首先拷貝要修改的條目，然后修改條目的拷貝，等修改完畢后，再使用條目拷貝取代要修改的條目，要修改條目將被在經(jīng)歷一個(gè)grace period后安全刪除。
對(duì)于系統(tǒng)調(diào)用審計(jì)代碼，并沒(méi)有這種情況。這里假設(shè)有修改的情況，那么使用rwlock的修改代碼應(yīng)當(dāng)如下：
static inline int audit_upd_rule(struct audit_rule *rule, struct list_head *list, __u32 newaction, __u32 newfield_count) { struct audit_entry *e; struct audit_newentry *ne; write_lock(&auditsc_lock); /* Note: audit_netlink_sem held by caller. */ list_for_each_entry(e, list, list) { if (!audit_compare_rule(rule, &e->rule)) { e->rule.action = newaction; e->rule.file_count = newfield_count; write_unlock(&auditsc_lock); return 0; } } write_unlock(&auditsc_lock); return -EFAULT; /* No matching rule */ } 如果使用RCU，修改代碼應(yīng)當(dāng)為；
static inline int audit_upd_rule(struct audit_rule *rule, struct list_head *list, __u32 newaction, __u32 newfield_count) { struct audit_entry *e; struct audit_newentry *ne; list_for_each_entry(e, list, list) { if (!audit_compare_rule(rule, &e->rule)) { ne = kmalloc(sizeof(*entry), GFP_ATOMIC); if (ne == NULL) return -ENOMEM; audit_copy_rule(&ne->rule, &e->rule); ne->rule.action = newaction; ne->rule.file_count = newfield_count; list_replace_rcu(e, ne); call_rcu(&e->rcu, audit_free_rule, e); return 0; } } return -EFAULT; /* No matching rule */ } 3．修改操作立即可見(jiàn)
前面兩種情況，讀者能夠容忍修改可以在一段時(shí)間后看到，也就說(shuō)讀者在修改后某一時(shí)間段內(nèi)，仍然看到的是原來(lái)的數(shù)據(jù)。在很多情況下，讀者不能容忍看到舊的數(shù)據(jù)，這種情況下，需要使用一些新措施，如System V IPC，它在每一個(gè)鏈表?xiàng)l目中增加了一個(gè)deleted字段，標(biāo)記該字段是否刪除，如果刪除了，就設(shè)置為真，否則設(shè)置為假，當(dāng)代碼在遍歷鏈表時(shí)，核對(duì)每一個(gè)條目的deleted字段，如果為真，就認(rèn)為它是不存在的。
還是以系統(tǒng)調(diào)用審計(jì)代碼為例，如果它不能容忍舊數(shù)據(jù)，那么，讀端代碼應(yīng)該修改為：
static enum audit_state audit_filter_task(struct task_struct *tsk) { struct audit_entry *e; enum audit_state state; rcu_read_lock(); list_for_each_entry_rcu(e, &audit_tsklist, list) { if (audit_filter_rules(tsk, &e->rule, NULL, &state)) { spin_lock(&e->lock); if (e->deleted) { spin_unlock(&e->lock); rcu_read_unlock(); return AUDIT_BUILD_CONTEXT; } rcu_read_unlock(); return state; } } rcu_read_unlock(); return AUDIT_BUILD_CONTEXT; } 注意，對(duì)于這種情況，每一個(gè)鏈表?xiàng)l目都需要一個(gè)spinlock保護(hù)，因?yàn)閯h除操作將修改條目的deleted標(biāo)志。此外，該函數(shù)如果搜索到條目，返回時(shí)應(yīng)當(dāng)保持該條目的鎖，因?yàn)橹挥羞@樣，才能看到新的修改的數(shù)據(jù)，否則，仍然可能看到就的數(shù)據(jù)。
寫(xiě)端的刪除操作將變成：
static inline int audit_del_rule(struct audit_rule *rule, struct list_head *list) { struct audit_entry *e; /* Do not use the _rcu iterator here, since this is the only * deletion routine. */ list_for_each_entry(e, list, list) { if (!audit_compare_rule(rule, &e->rule)) { spin_lock(&e->lock); list_del_rcu(&e->list); e->deleted = 1; spin_unlock(&e->lock); call_rcu(&e->rcu, audit_free_rule, e); return 0; } } return -EFAULT; /* No matching rule */ } 刪除條目時(shí)，需要標(biāo)記該條目為已刪除。這樣讀者就可以通過(guò)該標(biāo)志立即得知條目是否已經(jīng)刪除。
回頁(yè)首 六、小結(jié)
RCU是2.6內(nèi)核引入的新的鎖機(jī)制，在絕大部分為讀而只有極少部分為寫(xiě)的情況下，它是非常高效的，因此在路由表維護(hù)、系統(tǒng)調(diào)用審計(jì)、SELinux的AVC、dcache和IPC等代碼部分中，使用它來(lái)取代rwlock來(lái)獲得更高的性能。但是，它也有缺點(diǎn)，延后的刪除或釋放將占用一些內(nèi)存，尤其是對(duì)嵌入式系統(tǒng)，這可能是非常昂貴的內(nèi)存開(kāi)銷(xiāo)。此外，寫(xiě)者的開(kāi)銷(xiāo)比較大，尤其是對(duì)于那些無(wú)法容忍舊數(shù)據(jù)的情況以及不只一個(gè)寫(xiě)者的情況，寫(xiě)者需要spinlock或其他的鎖機(jī)制來(lái)與其他寫(xiě)者同步。
在作者先前的兩篇文章"Linux 實(shí)時(shí)技術(shù)與典型實(shí)現(xiàn)分析, 第 1 部分: 介紹"和"Linux 實(shí)時(shí)技術(shù)與典型實(shí)現(xiàn)分析, 第 2 部分: Ingo Molnar 的實(shí)時(shí)補(bǔ)丁"中，Ingo Molnar的實(shí)時(shí)實(shí)現(xiàn)要求RCU讀端臨界區(qū)可搶占，而RCU的實(shí)現(xiàn)的前提是讀端臨界區(qū)不可搶占，因此如何解決這一矛盾但同時(shí)不損害RCU的性能是RCU未來(lái)的一大挑戰(zhàn)。
回頁(yè)首 參考資料
[1] Linux RCU實(shí)現(xiàn)者之一Paul E. McKenney的RCU資源鏈接，http://www.rdrop.com/users/paulmck/rclock/
[2] Paul E. McKenney的博士論文，"Exploiting Deferred Destruction: An Analysis of Read-Copy Update Techniques in Operating System Kernels"，http://www.rdrop.com/users/paulmck/rclock/RCUdissertation.2004.07.14e1.pdf
[3] Paul E. McKenney's paper in Ottawa Linux Summit 2002, Read-Copy Update，http://www.rdrop.com/users/paulmck/rclock/rcu.2002.07.08.pdf
[4] Linux Journal在2003年10月對(duì)RCU的簡(jiǎn)介, Kernel Korner - Using RCU in the Linux 2.5 Kernel，http://linuxjournal.com/article/6993
[5] Scaling dcache with RCU, http://linuxjournal.com/article/7124
[6] Patch: Real-Time Preemption and RCU，http://lwn.net/Articles/128228/
[7] Using Read-Copy Update Techniques for System V IPC in the Linux 2.5 Kernel, http://www.rdrop.com/users/paulmck/rclock/rcu.FREENIX.2003.06.14.pdf
[8] Linux 2.6.12 kernel source。
[9] Linux kernel documentation, Documentation/RCU/*。
關(guān)于作者
楊燚，計(jì)算機(jī)科學(xué)碩士，畢業(yè)于中科院計(jì)算技術(shù)研究所，有4年的Linux內(nèi)核編程經(jīng)驗(yàn)，目前從事嵌入式實(shí)時(shí)Linux的開(kāi)發(fā)與性能測(cè)試。您可以通過(guò)yang.yi@bmrtech.com yyang@ch.mvista.com
66821730(技術(shù)支持)
