RCU(Read-Copy Update)，是 linux 中比較重要的一種同步機制。顧名思義就是“讀，拷貝更新”，再直白點是“隨意讀，但更新數據的時候，需要先復制一份副本，在副本上完成修改，再一次性地替換舊數據”。這是 Linux 內核實現的一種針對“讀多寫少”的共享數據的同步機制。

不同于其他的同步機制，它允許多個讀者同時訪問共享數據，而且讀者的性能不會受影響（“隨意讀”），讀者與寫者之間也不需要同步機制（但需要“復制后再寫”），但如果存在多個寫者時，在寫者把更新后的“副本”覆蓋到原數據時，寫者與寫者之間需要利用其他同步機制保證同步。

RCU 的一個典型的應用場景是鏈表，在 Linux kernel 中還專門提供了一個頭文件（include/linux/rculist.h），提供了利用 RCU 機制對鏈表進行增刪查改操作的接口。本文將通過一個例子，利用 rculist.h 提供的接口對鏈表進行增刪查改的操作，來講述 RCU 的原理，以及介紹 Linux kernel 中相關的 API（基于 Linux v3.4.0 的源碼）。

增加鏈表項

Linux kernel 中利用 RCU 往鏈表增加項的源碼如下：

#define list_next_rcu(list)     (*((struct list_head __rcu **)(&(list)->next)))

static inline void __list_add_rcu(struct list_head *new,
                struct list_head *prev, struct list_head *next)
{
        new->next = next;
        new->prev = prev;
        rcu_assign_pointer(list_next_rcu(prev), new);
        next->prev = new;
}

list_next_rcu() 函數中的 rcu 是一個供代碼分析工具 Sparse 使用的編譯選項，規定有 rcu 標簽的指針不能直接使用，而需要使用 rcu_dereference() 返回一個受 RCU 保護的指針才能使用。rcu_dereference() 接口的相關知識會在后文介紹，這一節重點關注 rcu_assign_pointer() 接口。首先看一下 rcu_assign_pointer() 的源碼：

#define __rcu_assign_pointer(p, v, space) 
    ({ 
        smp_wmb(); 
        (p) = (typeof(*v) __force space *)(v); 
    })

上述代碼的最終效果是把 v 的值賦值給 p，關鍵點在于第 3 行的內存屏障。什么是內存屏障（Memory Barrier）呢？CPU 采用流水線技術執行指令時，只保證有內存依賴關系的指令的執行順序，例如 p = v; a = *p;，由于第 2 條指令訪問的指針 p 所指向的內存依賴于第 1 條指令，因此 CPU 會保證第 1 條指令在第 2 條指令執行前執行完畢。但對于沒有內存依賴的指令，例如上述 __list_add_rcu() 接口中，假如把第 8 行寫成 prev->next = new;，由于這個賦值操作并沒涉及到對 new 指針指向的內存的訪問，因此認為不依賴于 6,7 行對 new->next 和 new->prev 的賦值，CPU 有可能實際運行時會先執行 prev->next = new; 再執行 new->prev = prev;，這就會造成 new 指針（也就是新加入的鏈表項）還沒完成初始化就被加入了鏈表中，假如這時剛好有一個讀者剛好遍歷訪問到了該新的鏈表項（因為 RCU 的一個重要特點就是可隨意執行讀操作），就會訪問到一個未完成初始化的鏈表項！通過設置內存屏障就能解決該問題，它保證了在內存屏障前邊的指令一定會先于內存屏障后邊的指令被執行。這就保證了被加入到鏈表中的項，一定是已經完成了初始化的。

最后提醒一下，這里要注意的是，如果可能存在多個線程同時執行添加鏈表項的操作，添加鏈表項的操作需要用其他同步機制（如 spin_lock 等）進行保護。

訪問鏈表項

Linux kernel 中訪問 RCU 鏈表項常見的代碼模式是：

rcu_read_lock();
list_for_each_entry_rcu(pos, head, member) {
    // do something with `pos`
}
rcu_read_unlock();

這里要講到的 rcu_read_lock() 和 rcu_read_unlock()，是 RCU “隨意讀” 的關鍵，它們的效果是聲明了一個讀端的臨界區（read-side critical sections）。在說讀端臨界區之前，我們先看看讀取鏈表項的宏函數 list_for_each_entry_rcu。追溯源碼，獲取一個鏈表項指針主要調用的是一個名為 rcu_dereference() 的宏函數，而這個宏函數的主要實現如下：

#define __rcu_dereference_check(p, c, space) 
    ({ 
        typeof(*p) *_________p1 = (typeof(*p)*__force )ACCESS_ONCE(p); 
        rcu_lockdep_assert(c, "suspicious rcu_dereference_check()" 
                      " usage"); 
        rcu_dereference_sparse(p, space); 
        smp_read_barrier_depends(); 
        ((typeof(*p) __force __kernel *)(_________p1)); 
    })
第 3 行：聲明指針 _p1 = p;
第 7 行：smp_read_barrier_depends();
第 8 行：返回 _p1;

上述兩塊代碼，實際上可以看作這樣一種模式：

rcu_read_lock();
p1 = rcu_dereference(p);
if (p1 != NULL) {
    // do something with p1, such as:
    printk("%dn", p1->field);
}
rcu_read_unlock();

根據 rcu_dereference() 的實現，最終效果就是把一個指針賦值給另一個，那如果把上述第 2 行的 rcu_dereference() 直接寫成 p1 = p 會怎樣呢？在一般的處理器架構上是一點問題都沒有的。但在 alpha 上，編譯器的 value-speculation 優化選項據說可能會“猜測” p1 的值，然后重排指令先取值 p1->field~ 因此 Linux kernel 中，smp_read_barrier_depends() 的實現是架構相關的，arm、x86 等架構上是空實現，alpha 上則加了內存屏障，以保證先獲得 p 真正的地址再做解引用。因此上一節 “增加鏈表項” 中提到的 “__rcu” 編譯選項強制檢查是否使用 rcu_dereference() 訪問受 RCU 保護的數據，實際上是為了讓代碼擁有更好的可移植性。

現在回到讀端臨界區的問題上來。多個讀端臨界區不互斥，即多個讀者可同時處于讀端臨界區中，但一塊內存數據一旦能夠在讀端臨界區內被獲取到指針引用，這塊內存塊數據的釋放必須等到讀端臨界區結束，等待讀端臨界區結束的 Linux kernel API 是synchronize_rcu()。讀端臨界區的檢查是全局的，系統中有任何的代碼處于讀端臨界區，synchronize_rcu() 都會阻塞，知道所有讀端臨界區結束才會返回。為了直觀理解這個問題，舉以下的代碼實例：

/* `p` 指向一塊受 RCU 保護的共享數據 */

/* reader */
rcu_read_lock();
p1 = rcu_dereference(p);
if (p1 != NULL) {
    printk("%dn", p1->field);
}
rcu_read_unlock();

/* free the memory */
p2 = p;
if (p2 != NULL) {
    p = NULL;
    synchronize_rcu();
    kfree(p2);
}

用以下圖示來表示多個讀者與內存釋放線程的時序關系：

上圖中，每個讀者的方塊表示獲得 p 的引用（第5行代碼）到讀端臨界區結束的時間周期；t1 表示 p = NULL 的時間；t2 表示 synchronize_rcu() 調用開始的時間；t3 表示 synchronize_rcu() 返回的時間。我們先看 Reader1,2,3，雖然這 3 個讀者的結束時間不一樣，但都在 t1 前獲得了 p 地址的引用。t2 時調用 synchronize_rcu()，這時 Reader1 的讀端臨界區已結束，但 Reader2,3 還處于讀端臨界區，因此必須等到 Reader2,3 的讀端臨界區都結束，也就是 t3，t3 之后，就可以執行 kfree(p2) 釋放內存。synchronize_rcu() 阻塞的這一段時間，有個名字，叫做 Grace period。而 Reader4,5,6，無論與 Grace period 的時間關系如何，由于獲取引用的時間在 t1 之后，都無法獲得 p 指針的引用，因此不會進入 p1 != NULL 的分支。

刪除鏈表項

知道了前邊說的 Grace period，理解鏈表項的刪除就很容易了。常見的代碼模式是：

p = seach_the_entry_to_delete();
list_del_rcu(p->list);
synchronize_rcu();
kfree(p);
其中 list_del_rcu() 的源碼如下，把某一項移出鏈表：

/* list.h */
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
    next->prev = prev;
    prev->next = next;
}

/* rculist.h */
static inline void list_del_rcu(struct list_head *entry)
{
    __list_del(entry->prev, entry->next);
    entry->prev = LIST_POISON2;
}

根據上一節“訪問鏈表項”的實例，假如一個讀者能夠從鏈表中獲得我們正打算刪除的鏈表項，則肯定在 synchronize_rcu() 之前進入了讀端臨界區，synchronize_rcu() 就會保證讀端臨界區結束時才會真正釋放鏈表項的內存，而不會釋放讀者正在訪問的鏈表項。

更新鏈表項

前文提到，RCU 的更新機制是 “Copy Update”，RCU 鏈表項的更新也是這種機制，典型代碼模式是：

p = search_the_entry_to_update();
q = kmalloc(sizeof(*p), GFP_KERNEL);
*q = *p;
q->field = new_value;
list_replace_rcu(&p->list, &q->list);
synchronize_rcu();
kfree(p);

其中第 3,4 行就是復制一份副本，并在副本上完成更新，然后調用 list_replace_rcu() 用新節點替換掉舊節點。源碼如下：
其中第 3,4 行就是復制一份副本，并在副本上完成更新，然后調用 list_replace_rcu() 用新節點替換掉舊節點，最后釋放舊節點內存。list_replace_rcu() 源碼如下：

static inline void list_replace_rcu(struct list_head *old,
                struct list_head *new)
{
    new->next = old->next;
    new->prev = old->prev;
    rcu_assign_pointer(list_next_rcu(new->prev), new);
    new->next->prev = new;
    old->prev = LIST_POISON2;
}