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