Linux 2.6内核中新的锁机制--RCU [转]
2005 年 7 月 01 日
本文詳細地介紹了 Linux 2.6 內(nèi)核中新的鎖機制 RCU(Read-Copy Update) 的實現(xiàn)機制，使用要求與典型應用。一、 引言
眾所周知，為了保護共享數(shù)據(jù),需要一些同步機制,如自旋鎖(spinlock)，讀寫鎖(rwlock)，它們使用起來非常簡單,而且是一種很有效的同步機制，在UNIX系統(tǒng)和Linux系統(tǒng)中得到了廣泛的使用。但是隨著計算機硬件的快速發(fā)展，獲得這種鎖的開銷相對于CPU的速度在成倍地增加，原因很簡單，CPU的速度與訪問內(nèi)存的速度差距越來越大，而這種鎖使用了原子操作指令，它需要原子地訪問內(nèi)存，也就說獲得鎖的開銷與訪存速度相關，另外在大部分非x86架構上獲取鎖使用了內(nèi)存柵(Memory Barrier)，這會導致處理器流水線停滯或刷新，因此它的開銷相對于CPU速度而言就越來越大。表1數(shù)據(jù)證明了這一點。
表1是在700MHz的奔騰III機器上的基本操作的開銷，在該機器上一個時鐘周期能夠執(zhí)行兩條整數(shù)指令。在1.8GHz的奔騰4機器上, 原子加1指令的開銷要比700MHz的奔騰III機器慢75納秒(ns)，盡管CPU速度快兩倍多。
這種鎖機制的另一個問題在于其可擴展性，在多處理器系統(tǒng)上，可擴展性非常重要，否則根本無法發(fā)揮其性能。圖1表明了Linux上各種鎖的擴展性。
圖 1 Linux的4種鎖機制的擴展性
注：refcnt表示自旋鎖與引用記數(shù)一起使用。
讀寫鎖rwlock在兩個CPU的情況下性能反倒比一個CPU的差，在四個CPU的情況下，refcnt的性能要高于rwlock，refcnt大約是理論性能的45%，而rwlock是理論性能的39%,自旋縮spinlock的性能明顯好于refcnt和rwlock，但它也只達到了理性性能的 57%，brlock（Big Reader Lock）性能可以線性擴展。Brlock是由Redhat的Ingo Molnar實現(xiàn)的一個高性能的rwlock，它適用于讀特多而寫特少的情況，讀者獲得brlock的開銷很低，但寫者獲得鎖的開銷非常大，而且它只預定義了幾個鎖，用戶無法隨便定義并使用這種鎖，它也需要為每個CPU定義一個鎖狀態(tài)數(shù)組，因此這種鎖并沒有被作為rwlock的替代方案廣泛使用，只是在一些特別的地方使用到。
正是在這種背景下，一個高性能的鎖機制RCU呼之欲出，它克服了以上鎖的缺點，具有很好的擴展性，但是這種鎖機制的使用范圍比較窄，它只適用于讀多寫少的情況，如網(wǎng)絡路由表的查詢更新、設備狀態(tài)表的維護、數(shù)據(jù)結構的延遲釋放以及多徑I/O設備的維護等。
RCU并不是新的鎖機制，它只是對Linux內(nèi)核而言是新的。早在二十世紀八十年代就有了這種機制，而且在生產(chǎn)系統(tǒng)中使用了這種機制，但這種早期的實現(xiàn)并不太好，在二十世紀九十年代出現(xiàn)了一個比較高效的實現(xiàn)，而在linux中是在開發(fā)內(nèi)核2.5.43中引入該技術的并正式包含在2.6內(nèi)核中。
二、RCU的原理
RCU(Read-Copy Update)，顧名思義就是讀-拷貝修改，它是基于其原理命名的。對于被RCU保護的共享數(shù)據(jù)結構，讀者不需要獲得任何鎖就可以訪問它，但寫者在訪問它時首先拷貝一個副本，然后對副本進行修改，最后使用一個回調(diào)（callback）機制在適當?shù)臅r機把指向原來數(shù)據(jù)的指針重新指向新的被修改的數(shù)據(jù)。這個時機就是所有引用該數(shù)據(jù)的CPU都退出對共享數(shù)據(jù)的操作。
因此RCU實際上是一種改進的rwlock，讀者幾乎沒有什么同步開銷，它不需要鎖，不使用原子指令，而且在除alpha的所有架構上也不需要內(nèi)存柵（Memory Barrier），因此不會導致鎖競爭，內(nèi)存延遲以及流水線停滯。不需要鎖也使得使用更容易，因為死鎖問題就不需要考慮了。寫者的同步開銷比較大，它需要延遲數(shù)據(jù)結構的釋放，復制被修改的數(shù)據(jù)結構，它也必須使用某種鎖機制同步并行的其它寫者的修改操作。讀者必須提供一個信號給寫者以便寫者能夠確定數(shù)據(jù)可以被安全地釋放或修改的時機。有一個專門的垃圾收集器來探測讀者的信號，一旦所有的讀者都已經(jīng)發(fā)送信號告知它們都不在使用被RCU保護的數(shù)據(jù)結構，垃圾收集器就調(diào)用回調(diào)函數(shù)完成最后的數(shù)據(jù)釋放或修改操作。 RCU與rwlock的不同之處是：它既允許多個讀者同時訪問被保護的數(shù)據(jù)，又允許多個讀者和多個寫者同時訪問被保護的數(shù)據(jù)（注意：是否可以有多個寫者并行訪問取決于寫者之間使用的同步機制），讀者沒有任何同步開銷，而寫者的同步開銷則取決于使用的寫者間同步機制。但RCU不能替代rwlock，因為如果寫比較多時，對讀者的性能提高不能彌補寫者導致的損失。
讀者在訪問被RCU保護的共享數(shù)據(jù)期間不能被阻塞，這是RCU機制得以實現(xiàn)的一個基本前提，也就說當讀者在引用被RCU保護的共享數(shù)據(jù)期間，讀者所在的CPU不能發(fā)生上下文切換，spinlock和rwlock都需要這樣的前提。寫者在訪問被RCU保護的共享數(shù)據(jù)時不需要和讀者競爭任何鎖，只有在有多于一個寫者的情況下需要獲得某種鎖以與其他寫者同步。寫者修改數(shù)據(jù)前首先拷貝一個被修改元素的副本，然后在副本上進行修改，修改完畢后它向垃圾回收器注冊一個回調(diào)函數(shù)以便在適當?shù)臅r機執(zhí)行真正的修改操作。等待適當時機的這一時期稱為grace period，而CPU發(fā)生了上下文切換稱為經(jīng)歷一個quiescent state，grace period就是所有CPU都經(jīng)歷一次quiescent state所需要的等待的時間。垃圾收集器就是在grace period之后調(diào)用寫者注冊的回調(diào)函數(shù)來完成真正的數(shù)據(jù)修改或數(shù)據(jù)釋放操作的。
以下以鏈表元素刪除為例詳細說明這一過程。
寫者要從鏈表中刪除元素 B，它首先遍歷該鏈表得到指向元素 B 的指針，然后修改元素 B 的前一個元素的 next 指針指向元素 B 的 next 指針指向的元素C，修改元素 B 的 next 指針指向的元素 C 的 prep 指針指向元素 B 的 prep指針指向的元素 A,在這期間可能有讀者訪問該鏈表，修改指針指向的操作是原子的，所以不需要同步，而元素 B 的指針并沒有去修改，因為讀者可能正在使用 B 元素來得到下一個或前一個元素。寫者完成這些操作后注冊一個回調(diào)函數(shù)以便在 grace period 之后刪除元素 B，然后就認為已經(jīng)完成刪除操作。垃圾收集器在檢測到所有的CPU不在引用該鏈表后，即所有的 CPU 已經(jīng)經(jīng)歷了 quiescent state,grace period 已經(jīng)過去后，就調(diào)用剛才寫者注冊的回調(diào)函數(shù)刪除了元素 B。
圖 2 使用 RCU 進行鏈表刪除操作
?
三、RCU 實現(xiàn)機制
按照第二節(jié)所講原理，對于讀者，RCU 僅需要搶占失效，因此獲得讀鎖和釋放讀鎖分別定義為：
#define rcu_read_lock() preempt_disable()#define rcu_read_unlock() preempt_enable()
它們有一個變種：
#define rcu_read_lock_bh() local_bh_disable()#define rcu_read_unlock_bh() local_bh_enable()
這個變種只在修改是通過 call_rcu_bh 進行的情況下使用，因為 call_rcu_bh將把 softirq 的執(zhí)行完畢也認為是一個 quiescent state，因此如果修改是通過 call_rcu_bh 進行的，在進程上下文的讀端臨界區(qū)必須使用這一變種。
每一個 CPU 維護兩個數(shù)據(jù)結構rcu_data,rcu_bh_data，它們用于保存回調(diào)函數(shù)，函數(shù)call_rcu和函數(shù)call_rcu_bh用戶注冊回調(diào)函數(shù)，前者把回調(diào)函數(shù)注冊到rcu_data，而后者則把回調(diào)函數(shù)注冊到rcu_bh_data，在每一個數(shù)據(jù)結構上，回調(diào)函數(shù)被組成一個鏈表，先注冊的排在前頭，后注冊的排在末尾。
當在CPU上發(fā)生進程切換時，函數(shù)rcu_qsctr_inc將被調(diào)用以標記該CPU已經(jīng)經(jīng)歷了一個quiescent state。該函數(shù)也會被時鐘中斷觸發(fā)調(diào)用。
時鐘中斷觸發(fā)垃圾收集器運行，它會檢查：
如果以上四個條件只要有一個滿足，它就調(diào)用函數(shù)rcu_check_callbacks。
函數(shù)rcu_check_callbacks首先檢查該CPU是否經(jīng)歷了一個quiescent state，如果：
1． 當前進程運行在用戶態(tài)；
或
2． 當前進程為idle且當前不處在運行softirq狀態(tài)，也不處在運行IRQ處理函數(shù)的狀態(tài)；
那么，該CPU已經(jīng)經(jīng)歷了一個quiescent state，因此通過調(diào)用函數(shù)rcu_qsctr_inc標記該CPU的數(shù)據(jù)結構rcu_data和rcu_bh_data的標記字段 passed_quiesc，以記錄該CPU已經(jīng)經(jīng)歷一個quiescent state。
否則，如果當前不處在運行softirq狀態(tài)，那么，只標記該CPU的數(shù)據(jù)結構rcu_bh_data的標記字段passed_quiesc，以記錄該CPU已經(jīng)經(jīng)歷一個quiescent state。注意，該標記只對rcu_bh_data有效。
然后，函數(shù)rcu_check_callbacks將調(diào)用tasklet_schedule，它將調(diào)度為該CPU設置的tasklet rcu_tasklet，每一個CPU都有一個對應的rcu_tasklet。
在時鐘中斷返回后，rcu_tasklet將在softirq上下文被運行。
rcu_tasklet將運行函數(shù)rcu_process_callbacks，函數(shù)rcu_process_callbacks可能做以下事情：
1． 開始一個新的grace period；這通過調(diào)用函數(shù)rcu_start_batch實現(xiàn)。
2． 運行需要處理的回調(diào)函數(shù)；這通過調(diào)用函數(shù)rcu_do_batch實現(xiàn)。
3． 檢查該CPU是否經(jīng)歷一個quiescent state；這通過函數(shù)rcu_check_quiescent_state實現(xiàn)
如果還沒有開始grace period，就調(diào)用rcu_start_batch開始新的grace period。調(diào)用函數(shù)rcu_check_quiescent_state檢查該CPU是否經(jīng)歷了一個quiescent state,如果是并且是最后一個經(jīng)歷quiescent state的CPU，那么就結束grace period，并開始新的grace period。如果有完成的grace period，那么就調(diào)用rcu_do_batch運行所有需要處理的回調(diào)函數(shù)。函數(shù)rcu_process_callbacks將對該CPU的兩個數(shù)據(jù)結構rcu_data和rcu_bh_data執(zhí)行上述操作。
四、RCU API
rcu_read_lock()
讀者在讀取由RCU保護的共享數(shù)據(jù)時使用該函數(shù)標記它進入讀端臨界區(qū)。
rcu_read_unlock()
該函數(shù)與rcu_read_lock配對使用，用以標記讀者退出讀端臨界區(qū)。夾在這兩個函數(shù)之間的代碼區(qū)稱為"讀端臨界區(qū)"(read-side critical section)。讀端臨界區(qū)可以嵌套，如圖3，臨界區(qū)2被嵌套在臨界區(qū)1內(nèi)。
圖 3 嵌套讀端臨界區(qū)示例
synchronize_rcu()
該函數(shù)由RCU寫端調(diào)用，它將阻塞寫者，直到經(jīng)過grace period后，即所有的讀者已經(jīng)完成讀端臨界區(qū)，寫者才可以繼續(xù)下一步操作。如果有多個RCU寫端調(diào)用該函數(shù)，他們將在一個grace period之后全部被喚醒。注意，該函數(shù)在2.6.11及以前的2.6內(nèi)核版本中為synchronize_kernel，只是在2.6.12才更名為 synchronize_rcu,但在2.6.12中也提供了synchronize_kernel和一個新的函數(shù)synchronize_sched，因為以前有很多內(nèi)核開發(fā)者使用synchronize_kernel用于等待所有CPU都退出不可搶占區(qū)，而在RCU設計時該函數(shù)只是用于等待所有CPU 都退出讀端臨界區(qū)，它可能會隨著RCU實現(xiàn)的修改而發(fā)生語意變化，因此為了預先防止這種情況發(fā)生，在新的修改中增加了專門的用于其它內(nèi)核用戶的 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ù)來等待所有CPU處在可搶占狀態(tài)，目前功能等同于synchronize_rcu，但現(xiàn)在已經(jīng)不建議使用，而使用synchronize_sched。
synchronize_sched()
該函數(shù)用于等待所有CPU都處在可搶占狀態(tài)，它能保證正在運行的中斷處理函數(shù)處理完畢，但不能保證正在運行的softirq處理完畢。注意，synchronize_rcu只保證所有CPU都處理完正在運行的讀端臨界區(qū)。注：在2.6.12內(nèi)核中，synchronize_kernel和synchronize_sched都實際使用synchronize_rcu，因此當前它們的功能實際是完全等同的，但是將來將可能有大的變化，因此務必根據(jù)需求選擇恰當?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 寫端調(diào)用，它不會使寫者阻塞，因而可以在中斷上下文或 softirq 使用，而 synchronize_rcu、synchronize_kernel 和synchronize_shced 只能在進程上下文使用。該函數(shù)將把函數(shù) func 掛接到 RCU回調(diào)函數(shù)鏈上，然后立即返回。一旦所有的 CPU 都已經(jīng)完成端臨界區(qū)操作，該函數(shù)將被調(diào)用來釋放刪除的將絕不在被應用的數(shù)據(jù)。參數(shù) head 用于記錄回調(diào)函數(shù) func，一般該結構會作為被 RCU 保護的數(shù)據(jù)結構的一個字段，以便省去單獨為該結構分配內(nèi)存的操作。需要指出的是，函數(shù) synchronize_rcu 的實現(xiàn)實際上使用函數(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的完成也當作經(jīng)歷一個quiescent state，因此如果寫端使用了該函數(shù)，在進程上下文的讀端必須使用rcu_read_lock_bh。
| #define rcu_dereference(p) ({ \ typeof(p) _________p1 = p; \ smp_read_barrier_depends(); \ (_________p1); \ }) |
該宏用于在RCU讀端臨界區(qū)獲得一個RCU保護的指針，該指針可以在以后安全地引用，內(nèi)存柵只在alpha架構上才使用。
除了這些API，RCU還增加了鏈表操作的RCU版本，因為對于RCU，對共享數(shù)據(jù)的操作必須保證能夠被沒有使用同步機制的讀者看到，所以內(nèi)存柵是非常必要的。
static inline void list_add_rcu(struct list_head *new, struct list_head *head) 該函數(shù)把鏈表項new插入到RCU保護的鏈表head的開頭。使用內(nèi)存柵保證了在引用這個新插入的鏈表項之前，新鏈表項的鏈接指針的修改對所有讀者是可見的。
| static inline void list_add_tail_rcu(struct list_head *new, struct list_head *head) |
該函數(shù)類似于list_add_rcu，它將把新的鏈表項new添加到被RCU保護的鏈表的末尾。
| static inline void list_del_rcu(struct list_head *entry) |
該函數(shù)從RCU保護的鏈表中移走指定的鏈表項entry，并且把entry的prev指針設置為LIST_POISON2，但是并沒有把entry的next指針設置為LIST_POISON1，因為該指針可能仍然在被讀者用于便利該鏈表。
| static inline void list_replace_rcu(struct list_head *old, struct list_head *new) |
該函數(shù)是RCU新添加的函數(shù)，并不存在非RCU版本。它使用新的鏈表項new取代舊的鏈表項old，內(nèi)存柵保證在引用新的鏈表項之前，它的鏈接指針的修正對所有讀者可見。
| list_for_each_rcu(pos, head) |
該宏用于遍歷由RCU保護的鏈表head，只要在讀端臨界區(qū)使用該函數(shù)，它就可以安全地和其它_rcu鏈表操作函數(shù)（如list_add_rcu）并發(fā)運行。
| list_for_each_safe_rcu(pos, n, head) |
該宏類似于list_for_each_rcu，但不同之處在于它允許安全地刪除當前鏈表項pos。
| list_for_each_entry_rcu(pos, head, member) |
該宏類似于list_for_each_rcu，不同之處在于它用于遍歷指定類型的數(shù)據(jù)結構鏈表，當前鏈表項pos為一包含struct list_head結構的特定的數(shù)據(jù)結構。
| list_for_each_continue_rcu(pos, head) |
該宏用于在退出點之后繼續(xù)遍歷由RCU保護的鏈表head。
| static inline void hlist_del_rcu(struct hlist_node *n) |
它從由RCU保護的哈希鏈表中移走鏈表項n，并設置n的ppre指針為LIST_POISON2，但并沒有設置next為LIST_POISON1,因為該指針可能被讀者使用用于遍利鏈表。
| static inline void hlist_add_head_rcu(struct hlist_node *n, struct hlist_head *h) |
該函數(shù)用于把鏈表項n插入到被RCU保護的哈希鏈表的開頭，但同時允許讀者對該哈希鏈表的遍歷。內(nèi)存柵確保在引用新鏈表項之前，它的指針修正對所有讀者可見。
| hlist_for_each_rcu(pos, head) |
該宏用于遍歷由RCU保護的哈希鏈表head，只要在讀端臨界區(qū)使用該函數(shù)，它就可以安全地和其它_rcu哈希鏈表操作函數(shù)（如hlist_add_rcu）并發(fā)運行。
| hlist_for_each_entry_rcu(tpos, pos, head, member) |
類似于hlist_for_each_rcu，不同之處在于它用于遍歷指定類型的數(shù)據(jù)結構哈希鏈表，當前鏈表項pos為一包含struct list_head結構的特定的數(shù)據(jù)結構。
五、RCU 典型應用
在 linux 2.6 內(nèi)核中，RCU 被內(nèi)核使用的越來越廣泛。下面是在最新的 2.6.12內(nèi)核中搜索得到的RCU使用情況統(tǒng)計表。
表 1 rcu_read_lock 的使用情況統(tǒng)計
表 2 rcu_read_unlock 的使用情況統(tǒng)計
表 3 rcu_read_lock_bh 的使用情況統(tǒng)計
表 4 rcu_read_unlock_bh 的使用情況統(tǒng)計
表 5 call_rcu 的使用情況統(tǒng)計
表 6 call_rcu_bh 的使用情況統(tǒng)計
表 7 list API 的使用情況統(tǒng)計
表 8 synchronize_rcu 的使用情況統(tǒng)計
表 9 rcu_dereferance 的使用情況統(tǒng)計
從以上統(tǒng)計結果可以看出，RCU已經(jīng)在網(wǎng)絡驅(qū)動層、網(wǎng)絡核心層、IPC、dcache、內(nèi)存設備層、軟RAID層、系統(tǒng)調(diào)用審計和SELinux中使用。從所有RCU API的使用統(tǒng)計匯總（表 10），不難看出，RCU已經(jīng)是一個非常重要的內(nèi)核鎖機制。
表 10 所有RCU API使用情況總匯
因此，如何正確使用 RCU 對于內(nèi)核開發(fā)者而言非常重要。
下面部分將就 RCU 的幾種典型應用情況詳細講解。
1．只有增加和刪除的鏈表操作
在這種應用情況下，絕大部分是對鏈表的遍歷，即讀操作，而很少出現(xiàn)的寫操作只有增加或刪除鏈表項，并沒有對鏈表項的修改操作，這種情況使用RCU非常容易，從rwlock轉(zhuǎn)換成RCU非常自然。路由表的維護就是這種情況的典型應用，對路由表的操作，絕大部分是路由表查詢，而對路由表的寫操作也僅僅是增加或刪除，因此使用RCU替換原來的rwlock順理成章。系統(tǒng)調(diào)用審計也是這樣的情況。
這是一段使用rwlock的系統(tǒng)調(diào)用審計部分的讀端代碼：
| 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的寫端代碼：
| 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后寫端代碼變成為：
| 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; } |
對于鏈表刪除操作，list_del替換為list_del_rcu和call_rcu，這是因為被刪除的鏈表項可能還在被別的讀者引用，所以不能立即刪除，必須等到所有讀者經(jīng)歷一個quiescent state才可以刪除。另外，list_for_each_entry并沒有被替換為list_for_each_entry_rcu，這是因為，只有一個寫者在做鏈表刪除操作，因此沒有必要使用_rcu版本。
通常情況下，write_lock和write_unlock應當分別替換成spin_lock和spin_unlock，但是對于只是對鏈表進行增加和刪除操作而且只有一個寫者的寫端，在使用了_rcu版本的鏈表操作API后，rwlock可以完全消除，不需要spinlock來同步讀者的訪問。對于上面的例子，由于已經(jīng)有audit_netlink_sem被調(diào)用者保持，所以spinlock就沒有必要了。
這種情況允許修改結果延后一定時間才可見，而且寫者對鏈表僅僅做增加和刪除操作，所以轉(zhuǎn)換成使用RCU非常容易。
2．寫端需要對鏈表條目進行修改操作
如果寫者需要對鏈表條目進行修改，那么就需要首先拷貝要修改的條目，然后修改條目的拷貝，等修改完畢后，再使用條目拷貝取代要修改的條目，要修改條目將被在經(jīng)歷一個grace period后安全刪除。
對于系統(tǒng)調(diào)用審計代碼，并沒有這種情況。這里假設有修改的情況，那么使用rwlock的修改代碼應當如下：
| 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，修改代碼應當為；
| 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．修改操作立即可見
前面兩種情況，讀者能夠容忍修改可以在一段時間后看到，也就說讀者在修改后某一時間段內(nèi)，仍然看到的是原來的數(shù)據(jù)。在很多情況下，讀者不能容忍看到舊的數(shù)據(jù)，這種情況下，需要使用一些新措施，如System V IPC，它在每一個鏈表條目中增加了一個deleted字段，標記該字段是否刪除，如果刪除了，就設置為真，否則設置為假，當代碼在遍歷鏈表時，核對每一個條目的deleted字段，如果為真，就認為它是不存在的。
還是以系統(tǒng)調(diào)用審計代碼為例，如果它不能容忍舊數(shù)據(jù)，那么，讀端代碼應該修改為：
| 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; } |
注意，對于這種情況，每一個鏈表條目都需要一個spinlock保護，因為刪除操作將修改條目的deleted標志。此外，該函數(shù)如果搜索到條目，返回時應當保持該條目的鎖，因為只有這樣，才能看到新的修改的數(shù)據(jù)，否則，仍然可能看到就的數(shù)據(jù)。
寫端的刪除操作將變成：
| 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 */ } |
刪除條目時，需要標記該條目為已刪除。這樣讀者就可以通過該標志立即得知條目是否已經(jīng)刪除。
六、小結
RCU是2.6內(nèi)核引入的新的鎖機制，在絕大部分為讀而只有極少部分為寫的情況下，它是非常高效的，因此在路由表維護、系統(tǒng)調(diào)用審計、 SELinux的AVC、dcache和IPC等代碼部分中，使用它來取代rwlock來獲得更高的性能。但是，它也有缺點，延后的刪除或釋放將占用一些內(nèi)存，尤其是對嵌入式系統(tǒng)，這可能是非常昂貴的內(nèi)存開銷。此外，寫者的開銷比較大，尤其是對于那些無法容忍舊數(shù)據(jù)的情況以及不只一個寫者的情況，寫者需要 spinlock或其他的鎖機制來與其他寫者同步。
在作者先前的兩篇文章"Linux 實時技術與典型實現(xiàn)分析, 第 1 部分: 介紹"和"Linux 實時技術與典型實現(xiàn)分析, 第 2 部分: Ingo Molnar 的實時補丁"中，Ingo Molnar的實時實現(xiàn)要求RCU讀端臨界區(qū)可搶占，而RCU的實現(xiàn)的前提是讀端臨界區(qū)不可搶占，因此如何解決這一矛盾但同時不損害RCU的性能是RCU 未來的一大挑戰(zhàn)。
參考資料
[1] Linux RCU實現(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月對RCU的簡介, 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/*。
［轉(zhuǎn)］http://www.ibm.com/developerworks/cn/linux/l-rcu/
關于作者
| 楊燚，計算機科學碩士，畢業(yè)于中科院計算技術研究所，有4年的Linux內(nèi)核編程經(jīng)驗，目前從事嵌入式實時Linux的開發(fā)與性能測試。您可以通過mailto:yang.yi@bmrtech.com?cc=或mailto:yyang@ch.mvista.com?cc=與作者聯(lián)系。 | ||
轉(zhuǎn)載于:https://www.cnblogs.com/papam/archive/2009/08/25/1553739.html
總結
以上是生活随笔為你收集整理的Linux 2.6内核中新的锁机制--RCU [转]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 最近面试，笔试题中的一道sql题
- 下一篇： ERROR 1093 解决方法