Linux內核中的RCU鎖：解鎖高效并發的奧秘
在 Linux 內核這片充滿挑戰與機遇的技術海洋中，高效的并發控制始終是開發者們不懈追求的目標。多處理器環境下，數據的一致性與并發訪問的安全性，猶如兩座巍峨的高山，橫亙在每一位內核開發者的前行道路上。傳統的鎖機制，如自旋鎖、互斥鎖和讀寫鎖等，雖各有其用武之地，但在面對復雜多變的應用場景時，往往會暴露出性能瓶頸或使用局限性。
它以獨特的設計理念和巧妙的工作機制，在眾多鎖機制中脫穎而出，尤其在處理讀多寫少的場景時，展現出了無與倫比的性能優勢。從文件系統到網絡協議棧，從進程管理到內核數據結構維護，RCU 鎖的身影無處不在，默默支撐著 Linux 內核高效穩定地運行。今天，讓我們深入探討一種別具一格且高效強大的鎖機制 ——RCU 鎖。
一、RCU鎖的概述
RCU，即 Read - Copy - Update，從字面上看，它的操作似乎僅包含讀取、復制和更新三個簡單步驟，但實際機制遠比這復雜。它專為讀多寫少的場景而設計，核心思想是允許讀操作無鎖并發執行，極大地提升讀操作的效率。對于寫操作，它則采用了一種獨特的策略：先復制數據，在副本上進行修改，待所有讀操作完成后，再將新副本替換舊數據。
在 RCU 機制中，讀取共享數據結構的操作是無鎖的，因此讀取操作可以并發進行，不會相互干擾。寫入共享數據結構的操作則使用了延遲刪除的策略，即寫入操作并不直接修改共享數據結構，而是將要刪除的數據結構標記為“已刪除”，并在之后的某個時間點（通常是在不會干擾讀取操作的時候）真正刪除這些數據結構。
RCU 機制的實現依賴于一些底層機制，比如內存屏障、原子操作等。在 Linux 內核中，RCU 機制被廣泛應用于多個子系統，比如進程管理、網絡協議棧等，以提高內核的并發性能。
在RCU的實現過程中，我們主要解決以下問題：
- 在讀取過程中，另外一個線程刪除了一個節點。刪除線程可以把這個節點從鏈表中移除，但它不能直接銷毀這個節點，必須等到所有的讀取線程讀取完成以后，才進行銷毀操作。RCU中把這個過程稱為寬限期（Grace period）。
- 在讀取過程中，另外一個線程插入了一個新節點，而讀線程讀到了這個節點，那么需要保證讀到的這個節點是完整的。這里涉及到了發布-訂閱機制（Publish-Subscribe Mechanism）。
- 保證讀取鏈表的完整性。新增或者刪除一個節點，不至于導致遍歷一個鏈表從中間斷開。但是RCU并不保證一定能讀到新增的節點或者不讀到要被刪除的節點。
二、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之后調用寫者注冊的回調函數來完成真正的數據修改或數據釋放操作的。
要想使用好RCU，就要知道RCU的實現原理。我們拿linux 2.6.21 kernel的實現開始分析，為什么選擇這個版本的實現呢？因為這個版本的實現相對較為單純，也比較簡單。當然之后內核做了不少改進，如搶占RCU、可睡眠RCU、分層RCU。但是基本思想都是類似的。所以先從簡單入手。
首先，我們提到的寫者在訪問它時首先拷貝一個副本，然后對副本進行修改，最后使用一個回調（callback）機制在適當的時機把指向原來數據的指針重新指向新的被修改的數據。而這個“適當的時機”就是所有CPU經歷了一次進程切換（也就是一個grace period）。
為什么這么設計？
因為RCU讀者的實現就是關搶占執行讀取，讀完了當然就可以進程切換了，也就等于是寫者可以操作臨界區了。
那么就自然可以想到，內核會設計兩個元素，來分別表示寫者被掛起的起始點，以及每cpu變量，來表示該cpu是否經過了一次進程切換(quies state)。
就是說，當寫者被掛起后要以下步驟：
- 重置每cpu變量，值為0。
- 當某個cpu經歷一次進程切換后，就將自己的變量設為1。
- 當所有的cpu變量都為1后，就可以喚醒寫者了。
下面我們來分別看linux里是如何完成這三步的：
我們從一個例子入手，這個例子來源于linux kernel文檔中的whatisRCU.txt。這個例子使用RCU的核心API來保護一個指向動態分配內存的全局指針。
struct foo {
int a;
char b;
long c;
};
DEFINE_SPINLOCK(foo_mutex);
struct foo *gbl_foo;
void foo_read (void)
{
foo *fp = gbl_foo;
if ( fp != NULL )
dosomething(fp->a, fp->b , fp->c );
}
void foo_update( foo* new_fp )
{
spin_lock(&foo_mutex);
foo *old_fp = gbl_foo;
gbl_foo = new_fp;
spin_unlock(&foo_mutex);
kfee(old_fp);
}如上代碼所示,RCU被用來保護全局指針struct foo *gbl_foo，foo_get_a()用來從RCU保護的結構中取得gbl_foo的值。而foo_update_a()用來更新被RCU保護的gbl_foo的值（更新其a成員）。首先,我們思考一下,為什么要在foo_update_a()中使用自旋鎖foo_mutex呢?假設中間沒有使用自旋鎖.那foo_update_a()的代碼如下：
void foo_read(void)
{
rcu_read_lock();
foo *fp = gbl_foo;
if ( fp != NULL )
dosomething(fp->a,fp->b,fp->c);
rcu_read_unlock();
}
void foo_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);
}假設A進程在上圖—-標識處被B進程搶點.B進程也執行了goo_ipdate_a().等B執行完后，再切換回A進程.此時,A進程所持的old_fd實際上已經被B進程給釋放掉了.此后A進程對old_fd的操作都是非法的。所以在此我們得到一個重要結論：RCU允許多個讀者同時訪問被保護的數據，也允許多個讀者在有寫者時訪問被保護的數據（但是注意：是否可以有多個寫者并行訪問取決于寫者之間使用的同步機制）。
說明：本文中說的進程不是用戶態的進程，而是內核的調用路徑，也可能是內核線程或軟中斷等。
三、RCU的核心機制
寬限期的確定是 RCU 鎖實現的難點與核心。為了準確判斷寬限期，RCU 機制有以下限制：
- 禁止內核搶占：在使用 RCU 鎖前，必須禁止內核搶占。這意味著 CPU 不能隨意調度到其他線程，只能等待當前線程離開臨界區（不再引用舊數據）才能進行調度。
- 臨界區內限制：在 RCU 鎖保護的臨界區中，不能使用可能觸發調度的函數。因為一旦發生調度，就意味著當前線程已經退出了臨界區，不再引用舊數據。
當所有 CPU 都至少發生過一次調度時，就可以確定沒有任何線程再引用舊數據，此時寬限期結束，寫者便可以安全地釋放舊數據。
四、RCU鎖的使用場景
(1)文件系統
在 Linux 文件系統中，RCU 鎖有著廣泛的應用。例如，當多個進程同時讀取文件系統的目錄結構時，讀操作可以并行進行，而當需要對目錄結構進行修改（如創建新文件、刪除文件等）時，寫操作會在確保所有讀操作完成后進行，保證了文件系統的一致性，同時提升了整體性能。
(2)網絡協議棧
在網絡協議棧中，對于一些只讀的網絡配置信息（如路由表），讀操作頻繁，而寫操作相對較少。使用 RCU 鎖可以讓多個網絡數據包處理線程快速讀取路由信息，而當網絡管理員需要修改路由配置時，寫操作會在合適的時機進行，避免了讀操作的阻塞。
(3)內核數據結構管理
Linux 內核在管理進程表、inode 表等數據結構時，也常常借助 RCU 鎖。以進程表為例，眾多線程可能頻繁讀取進程信息，而對進程表的修改（如進程創建、銷毀）相對較少。通過 RCU 鎖，讀操作可以高效進行，寫操作也能在不影響讀性能的前提下有序完成。
五、RCU鎖的優勢
(1)高性能讀操作
由于讀操作無需加鎖，在高并發讀的場景下，RCU 鎖能夠顯著提高系統的性能。相比傳統的鎖機制，讀操作的延遲大大降低，吞吐量顯著提升。
(2)減少鎖爭用
在多處理器環境下，鎖爭用是影響性能的重要因素。RCU 鎖減少了讀操作和寫操作之間的鎖爭用，使得系統能夠更好地利用多核處理器的性能。
(3)簡化代碼設計
對于讀多寫少的場景，使用 RCU 鎖可以簡化代碼的同步邏輯。讀端代碼無需復雜的鎖獲取和釋放操作，使代碼更加簡潔明了，易于維護。
六、在Linux內核中使用RCU鎖
在 Linux 內核中，使用 RCU 鎖需要遵循特定的 API：
讀端 API：
- rcu_read_lock()：用于進入RCU讀臨界區，本質上是禁止CPU搶占。
- rcu_read_unlock()：用于離開RCU讀臨界區，開啟CPU搶占。
寫端 API：
- synchronize_rcu()：等待寬限期結束，確保所有已開始的 RCU 讀操作完成。
- call_rcu()：用于延遲執行函數，通常用于釋放數據結構或對象，在寬限期結束后執行。
- kfree_rcu()：call_rcu()的特殊情況，專門用于釋放動態分配的內存。
RCU 示例：
#include <linux/module.h>
#include <linux/rcupdate.h>
struct my_node {
int val;
struct rcu_head rcu;
struct list_head list;
};
LIST_HEAD(my_list);
/* 添加一個節點到鏈表中 */
void add_node(int val)
{
struct my_node *new_node = kmalloc(sizeof(*new_node), GFP_KERNEL);
if (!new_node) {
printk(KERN_ERR "Failed to allocate memory for new node\n");
return;
}
new_node->val = val;
INIT_LIST_HEAD(&new_node->list);
/* 加入鏈表 */
list_add(&new_node->list, &my_list);
}
/* 刪除值為 val 的節點 */
void del_node(int val)
{
struct my_node *node, *tmp;
/* 遍歷鏈表并刪除匹配節點 */
list_for_each_entry_safe(node, tmp, &my_list, list) {
if (node->val == val) {
list_del_rcu(&node->list);
call_rcu(&node->rcu, kfree);
}
}
}
/* 遍歷整個鏈表，打印節點的值 */
void traverse_list(void)
{
struct my_node *node;
/* 進入 RCU 讀取臨界區 */
rcu_read_lock();
/* 遍歷鏈表并打印節點的值 */
list_for_each_entry_rcu(node, &my_list, list) {
printk(KERN_INFO "Node value: %d\n", node->val);
}
/* 離開 RCU 讀取臨界區 */
rcu_read_unlock();
}示例中，我們使用 RCU 來保護鏈表的訪問。添加節點時，我們不需要獲取鎖來保護共享資源。刪除節點時，我們使用了 list_del_rcu 來刪除節點，并使用 call_rcu 函數來安排釋放內存的回調函數。在遍歷鏈表時，我們使用了 rcu_read_lock 和 rcu_read_unlock 來進入和離開 RCU 讀取臨界區。
