一、什麼是RCU機制
RCU機制是Linux2.6之後提供的一種資料一緻性通路的機制，從RCU（read-copy-update）的名稱上看，我們就能對他的實作機制有一個大概的了解，在修改資料的時候，首先需要讀取資料，然後生成一個副本，對副本進行修改，修改完成之後再将老資料update成新的資料，此所謂RCU。
RCU 是Linux中比較重要的一種同步機制。顧名思義就是== " 讀，拷貝更新" ==，該機制記錄了指向共享資料結構的指針的所有使用者，在該結構将要改變的時候，首先建立一個副本，在副本中修改，在所有進行讀通路的使用者結束對舊副本的讀取之後，指針可以替換指向新的，修改後的副本的指針，這種機制可以允許并發讀寫。
在作業系統中，資料一緻性通路是一個非常重要的部分，通常我們可以采用鎖機制實作資料的一緻性通路。例如，semaphore、spinlock機制，在通路共享資料時，首先通路鎖資源，在擷取鎖資源的前提下才能實作資料的通路。這種原理很簡單，根本的思想就是在通路臨界資源時，首先通路一個全局的變量（鎖），通過全局變量的狀态來控制線程對臨界資源的通路。但是，這種思想是需要硬體支援的，硬體需要配合實作全局變量（鎖）的讀-修改-寫，現代CPU都會提供這樣的原子化指令。采用鎖機制實作資料通路的一緻性存在如下兩個問題：
效率問題。鎖機制的實作需要對記憶體的原子化通路，這種通路操作會破壞流水線操作，降低了流水線效率。這是影響性能的一個因素。另外，在采用讀寫鎖機制的情況下，寫鎖是排他鎖，無法實作寫鎖與讀鎖的并發操作，在某些應用下會降低性能。
擴充性問題。當系統中CPU數量增多的時候，采用鎖機制實作資料的同步通路效率偏低。并且随着CPU數量的增多，效率降低，由此可見鎖機制實作的資料一緻性通路擴充性差。
為了解決上述問題，Linux中引進了RCU機制。該機制在多CPU的平台上比較适用，對于讀多寫少的應用尤其适用。
1、曆史背景 —— 原始的RCU思想
在多線程場景下，經常我們需要并發通路一個資料結構，為了保證線程安全我們會考慮使用互斥設施來進行同步，更進一步我們會根據對這個資料結構的讀寫比例而選用讀寫鎖進行優化。但是讀寫鎖不是唯一的方式，我們可以借助于COW技術來做到寫操作不需要加鎖，也就是在讀的時候正常讀，寫的時候，先加鎖拷貝一份，然後進行寫，寫完就原子的更新回去，使用COW實作避免了頻繁加讀寫鎖本身的性能開銷。
優點
1、由于 RCU 旨在最小化讀取端開銷，是以僅在以更高速率使用同步邏輯進行讀取操作時才使用它。如果更新操作超過10%，性能反而會變差，是以應該選擇另一種同步方式而不是RCU。
2、幾乎沒有讀取端開銷。零等待，零開銷沒有死鎖問題沒有優先級倒置問題（優先級倒置和優先級繼承）無限制延遲沒有問題無記憶體洩漏風險問題。
缺點
1、使用起來有點複雜對于寫操作，它比其他同步技術稍慢适用場景。
2、基礎架構 —— RCU算法設計
Linux 核心RCU 參考QSBR算法設計一套無鎖同步機制。
多個讀者可以并發通路共享資料，而不需要加鎖；
寫者更新共享資料時候，需要先copy副本，在副本上修改，最終，讀者隻通路原始資料，是以他們可以安全地通路資料，多個寫者之間是需要用鎖互斥通路的（比如用自旋鎖）；
修改資源後，需要更新共享資源，讓後面讀者可以通路最新的資料；
等舊資源上所有的讀者都通路完畢後，就可以回收舊資源了
3、實作思路—— 讀寫回收實作思路
RCU 的關鍵思想有兩個：1）複制後更新；2）延遲回收記憶體。典型的RCU更新時序如下:
- 複制：将需要更新的資料複制到新記憶體位址；
- 更新：更新複制資料，這時候操作的新的記憶體位址；
- 替換：使用新記憶體位址指針替換舊資料記憶體位址指針，
- 此後舊資料将無法被後續讀者通路；
- 等待，所有通路舊資料的讀者進入靜默期，即通路舊資料完成；
- 回收：當沒有任何持有舊資料結構引用的讀者後，安全地回收舊資料記憶體。
1、對于讀操作，可以直接對共享資源進行通路，但是前提是需要CPU支援訪存操作的原子化，現代CPU對這一點都做了保證。但是RCU的讀操作上下文是不可搶占的（這一點在下面解釋），是以讀通路共享資源時可以采用read_rcu_lock()，該函數的工作是停止搶占。
2、對于寫操作，其需要将原來的老資料作一次備份（copy），然後對備份資料進行修改，修改完畢之後再用新資料更新老資料，更新老資料時采用了rcu_assign_pointer（）宏，在該函數中首先屏障一下memory，然後修改老資料。這個操作完成之後，需要進行老資料資源的回收。操作線程向系統注冊回收方法，等待回收。采用資料備份的方法可以實作讀者與寫者之間的并發操作，但是不能解決多個寫者之間的同步，是以當存在多個寫者時，需要通過鎖機制對其進行互斥，也就是在同一時刻隻能存在一個寫者。
3、在RCU機制中存在一個垃圾回收的daemon，當共享資源被update之後，可以采用該daemon實作老資料資源的回收。回收時間點就是在update之前的所有的讀者全部退出。由此可見寫者在update之後是需要睡眠等待的，需要等待讀者完成操作，如果在這個時刻讀者被搶占或者睡眠，那麼很可能會導緻系統死鎖。因為此時寫者在等待讀者，讀者被搶占或者睡眠，如果正在運作的線程需要通路讀者和寫者已經占用的資源，那麼死鎖的條件就很有可能形成了。
4、實作思路 —— 執行個體說明
RCU（Read-Copy Update）是資料同步的一種方式，在目前的Linux核心中發揮着重要的作用。RCU主要針對的資料對象是連結清單，目的是提高周遊讀取資料的效率，為了達到目的使用RCU機制讀取資料的時候不對連結清單進行耗時的加鎖操作。這樣在同一時間可以有多個線程同時讀取該連結清單，并且允許一個線程對連結清單進行修改（修改的時候，需要加鎖）。RCU适用于需要頻繁的讀取資料，而相應修改資料并不多的情景，例如在檔案系統中，經常需要查找定位目錄，而對目錄的修改相對來說并不多，這就是RCU發揮作用的最佳場景。
Linux核心源碼當中,關于RCU的文檔比較齊全，你可以在 /Documentation/RCU/ 目錄下找到這些檔案。Paul E. McKenney 是核心中RCU源碼的主要實作者，他也寫了很多RCU方面的文章。他把這些文章和一些關于RCU的論文的連結整理到了一起。http://www2.rdrop.com/users/paulmck/RCU/
在RCU的實作過程中，我們主要解決以下問題：
在讀取過程中，另外一個線程删除了一個節點。删除線程可以把這個節點從連結清單中移除，但它不能直接銷毀這個節點，必須等到所有的讀取線程讀取完成以後，才進行銷毀操作。RCU中把這個過程稱為寬限期（Grace period）。
在讀取過程中，另外一個線程插入了一個新節點，而讀線程讀到了這個節點，那麼需要保證讀到的這個節點是完整的。這裡涉及到了釋出-訂閱機制（Publish-Subscribe Mechanism）。
保證讀取連結清單的完整性。新增或者删除一個節點，不至于導緻周遊一個連結清單從中間斷開。但是RCU并不保證一定能讀到新增的節點或者不讀到要被删除的節點。
寬限期
struct rcu_st {
int a;
char b;
long c;
};
DEFINE_SPINLOCK(rcu_st_mutex);
struct rcu_st *gbl_rcu_st = NULL;
void rcu_st_read(void)
{
rcu_st *fp = gbl_rcu_st;
if ( fp != NULL ) {
dosomething(fp->a, fp->b , fp->c );
}
}
void rcu_st_update(rcu_st* new_fp)
{
spin_lock(&rcu_st_mutex);
rcu_st *old_fp = gbl_rcu_st;
gbl_rcu_st = new_fp;
spin_unlock(&rcu_st_mutex);
kfee(old_fp);
}
如上的程式，是針對于全局變量gbl_rcu_st的操作。假設以下場景。有兩個線程同時運作 rcu_st_read和rcu_st_update的時候，當 rcu_st_read執行完指派操作後，線程發生切換；此時另一個線程開始執行rcu_st_update并執行完成。當rcu_st_read運作的程序切換回來後，運作dosomething 的時候，fp已經被删除，這将對系統造成危害。為了防止此類事件的發生，RCU裡增加了一個新的概念叫寬限期（Grace period）。如下圖所示：
Removal：在寫端臨界區部分，讀取（Read()），進行複制（Copy），并執行更改（Update）操作；
Grace Period：這是一個等待期，以確定所有與執行删除的資料相關的reader通路完畢；
Reclamation：回收舊資料；
圖中每行代表一個線程，最下面的一行是删除線程，當它執行完删除操作後，線程進入了寬限期。
寬限期的意義是，在一個删除動作發生後，它必須等待所有在寬限期開始前已經開始的讀線程結束，才可以進行銷毀操作。這樣做的原因是這些線程有可能讀到了要删除的元素。圖中的寬限期必須等待1和2結束；而讀線程5在寬限期開始前已經結束，不需要考慮；而3,4,6也不需要考慮，因為在寬限期結束後開始後的線程不可能讀到已删除的元素。為此RCU機制提供了相應的API來實作這個功能。
void rcu_st_read(void)
{
rcu_read_lock();
rcu_st *fp = gbl_rcu_st;
if ( fp != NULL ) {
dosomething(fp->a, fp->b , fp->c);
}
rcu_read_unlock();
}
void rcu_st_update(rcu_st* new_fp)
{
spin_lock(&rcu_st_mutex);
rcu_st *old_fp = gbl_rcu_st;
gbl_rcu_st = new_fp;
spin_unlock(&rcu_st_mutex);
synchronize_rcu();
kfee(old_fp);
}
其中rcu_st_read中增加了rcu_read_lock和rcu_read_unlock，這兩個函數用來标記一個RCU讀過程的開始和結束。其實作用就是幫助檢測寬限期是否結束。rcu_st_update增加了一個函數synchronize_rcu()，調用該函數意味着一個寬限期的開始，而直到寬限期結束，該函數才會傳回。我們再對比着圖看一看，線程1和2，在synchronize_rcu之前可能得到了舊的gbl_rcu_st，也就是rcu_st_update中的old_fp，如果不等它們運作結束，就調用kfee(old_fp)，極有可能造成系統崩潰。而3,4,6在synchronize_rcu之後運作，此時它們已經不可能得到old_fp，此次的kfee将不對它們産生影響。
寬限期是RCU實作中最複雜的部分,原因是在提高讀資料性能的同時，删除資料的性能也不能太差。
訂閱——釋出機制
目前使用的編譯器大多會對代碼做一定程度的優化，CPU也會對執行指令做一些優化調整,目的是提高代碼的執行效率，但這樣的優化，有時候會帶來不期望的結果。如例：
void rcu_st_read(void)
{
rcu_read_lock();
rcu_st *fp = gbl_rcu_st;
if ( fp != NULL ) {
dosomething(fp->a, fp->b , fp->c);
}
rcu_read_unlock();
}
void rcu_st_update(rcu_st* new_fp)
{
spin_lock(&rcu_st_mutex);
rcu_st *old_fp = gbl_rcu_st;
new_fp->a = 1; /* Line 3 */
new_fp->b = ‘b’; /* Line 4 */
new_fp->c = 100; /* Line 5 */
gbl_rcu_st = new_fp; /* Line 6 */
spin_unlock(&rcu_st_mutex);
synchronize_rcu();
kfee(old_fp);
}
這段代碼中，我們期望的是3，4，5行的代碼在第6行代碼之前執行。但優化後的代碼并不對執行順序做出保證。在這種情形下，一個讀線程很可能讀到new_fp，但new_fp的成員指派還沒執行完成。當讀線程執行dosomething(fp->a, fp->b , fp->c) 的 時候，就有不确定的參數傳入到dosomething，極有可能造成不期望的結果，甚至程式崩潰。可以通過優化屏障來解決該問題，RCU機制對優化屏障做了包裝，提供了專用的API來解決該問題。這時候，第6行不再是直接的指針指派，而應該改為 :
rcu_assign_pointer(gbl_rcu_st,new_fp);
rcu_assign_pointer的實作比較簡單，如下：
#include <linux/rcupdate.h>
#define rcu_assign_pointer(p, v) \
__rcu_assign_pointer((p), (v), __rcu)
#define __rcu_assign_pointer(p, v, space) \
do { \
smp_wmb(); \
(p) = (typeof(*v) __force space *)(v); \
} while (0)
我們可以看到它的實作隻是在指派之前加了優化屏障 smp_wmb來確定代碼的執行順序。另外就是宏中用到的__rcu，隻是作為編譯過程的檢測條件來使用的。
或者改成：
3，4，5的new_fp a,b,c指派操作，可能在rcu_st_read，rcu_st *old_fp = gbl_rcu_st;指派前還沒有完成指派，當他和rcu_st_update同時運作的時候，可能導緻傳入dosomething的一部分屬于舊的gbl_rcu_st，而另外的屬于新的。這樣導緻運作結果的錯誤。為了避免該類問題，RCU還是提供了宏來解決該問題：
#include <linux/rcupdate.h>
#define rcu_dereference(p) rcu_dereference_check(p, 0)
#define rcu_dereference_check(p, c) \
__rcu_dereference_check((p), rcu_read_lock_held() || (c), __rcu)
#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)); \
})
static inline int rcu_read_lock_held(void)
{
if (!debug_lockdep_rcu_enabled())
return 1;
if (rcu_is_cpu_idle())
return 0;
if (!rcu_lockdep_current_cpu_online())
return 0;
return lock_is_held(&rcu_lock_map);
}
在指派後加入優化屏障smp_read_barrier_depends()。
在rcu_st_read我們之前的第四行代碼改為 foo *fp = rcu_dereference(gbl_foo);，就可以防止上述問題。
void rcu_st_read(void)
{
rcu_read_lock();
rcu_st *fp = rcu_dereference(gbl_rcu_st);
if ( fp != NULL ) {
dosomething(fp->a, fp->b , fp->c);
}
rcu_read_unlock();
}
資料讀取的完整性
還是通過例子來說明這個問題：
如圖我們在原list中加入一個節點new到A之前，所要做的第一步是将new的指針指向A節點，第二步才是将Head的指針指向new。這樣做的目的是當插入操作完成第一步的時候，對于連結清單的讀取并不産生影響，而執行完第二步的時候，讀線程如果讀到new節點，也可以繼續周遊連結清單。
如果把這個過程反過來，第一步head指向new，而這時一個線程讀到new，由于new的指針指向的是Null，這樣将導緻讀線程無法讀取到A，B等後續節點。從以上過程中，可以看出RCU并不保證讀線程讀取到new節點。如果該節點對程式産生影響，那麼就需要外部調用做相應的調整。如在檔案系統中，通過RCU定位後，如果查找不到相應節點，就會進行其它形式的查找。
如圖我們希望删除B，這時候要做的就是将A的指針指向C，保持B的指針，然後删除程式将進入寬限期檢測。由于B的内容并沒有變更，讀到B的線程仍然可以繼續讀取B的後續節點。B不能立即銷毀，它必須等待寬限期結束後，才能進行相應銷毀操作。由于A的節點已經指向了C，當寬限期開始之後所有的後續讀操作通過A找到的是C，而B已經隐藏了，後續的讀線程都不會讀到它。這樣就確定寬限期過後，删除B并不對系統造成影響。
二、RCU核心API
如果指針ptr指向被RCU保護的資料結構，直接反引用指針是被禁止的，首先必須調用rcu_dereference(ptr)，然後反引用傳回的結果，需要使用rcu_read_lock和rcu_read_unlock 調用來進行保護。
rcu_read_lock()
rcu_read_unlock()
synchronize_rcu()/call_rcu()
rcu_assign_pointer()
rcu_dereference()
1、rcu_read_lock()
void rcu_read_lock(void);
讀者讀取受RCU保護的資料結構時使用，通知回收者讀者進入了RCU的讀端臨界區。在RCU讀端臨界區通路的任何受RCU保護的資料結構都會保證在臨界區期間保持未回收狀态。另外，引用計數可以與RCU一起使用，以維護對資料結構的長期引用。在RCU讀側臨界區阻塞是非法的。rcu_read_lock的實作非常簡單，是關閉搶占：
static inline void __rcu_read_lock(void)
{
preempt_disable();
}
2、rcu_read_unlock()
void rcu_read_unlock(void);
讀者結束讀取後使用，用于通知回收者其退出了讀端臨界區。RCU的讀端臨界區可能被嵌套或重疊。rcu_read_unlock 的實作是開發搶占。
static inline void __rcu_read_unlock(void)
{
preempt_enable();
}
3、synchronize_rcu()
void synchronize_rcu(void);
synchronize_rcu 函數的關鍵思想是等待。確定讀者完成對舊結構體的操作後釋放舊結構體。synchronize_rcu 的調用點标志着“更新者代碼的結束”和“回收者代碼的開始”。它通過阻塞來做到這一點，直到所有cpu上所有預先存在的RCU讀端臨界區都完成。
需要注意的是，synchronize_rcu()隻需要等待調用它之前的讀端臨界區完成，不需要等待調用它之後開始的讀取者完成。另外，synchronize_rcu()不一定在最後一個預先存在的RCU讀端臨界區完成之後立即傳回。具體實作中可能會有延時排程。同時，為了提高效率，許多RCU實作請求批量處理，這可能會進一步延遲 synchronize_rcu() 的傳回。
4、call_rcu()
call_rcu() API是syncnize_rcu()的回調形式，它注冊而不是阻塞，而是注冊一個函數和自變量，這些函數和自變量在所有正在進行的RCU讀取側關鍵部分均已完成之後被調用。 在禁止非法通路或更新端性能要求比較高時，此回調變體特别有用。
但是，不應輕易使用call_rcu() API，因為對syncnize_rcu() API的使用通常會使代碼更簡單。 此外，synchronize_rcu() API具有不錯的屬性，可以在寬限期被延遲時自動限制更新速率。 面對拒絕服務攻擊，此屬性導緻系統具有彈性。 使用call_rcu（）的代碼應限制更新速率，以獲得相同的彈性。
在上面的例子中，rcu_st_update阻塞直到一個寬限期結束。這很簡單，但在某些情況下，人們不能等這麼久——可能還有其他高優先級的工作要做。 在這種情況下，使用call_rcu()而不是synchronize_rcu()。call_rcu() API如下：
void call_rcu(struct rcu_head * head, void (*func)(struct rcu_head *head));
此函數在寬限期過後調用func(heda)。此調用可能發生在softirq或程序上下文中，是以不允許阻止該函數。rcu_st結構需要添加一個rcu-head結構，可能如下所示：
struct foo {
int a;
char b;
long c;
struct rcu_head rcu;
};
foo_update_a()函數示例如下：
/*
* Create a new struct foo that is the same as the one currently
* * pointed to by gbl_foo, except that field "a" is replaced
* * with "new_a". Points gbl_foo to the new structure, and
* * frees up the old structure after a grace period. *
* Uses rcu_assign_pointer() to ensure that concurrent readers
* * see the initialized version of the new structure.
* * Uses call_rcu() to ensure that any readers that might have
* * references to the old structure complete before freeing the * old structure.
* */
void foo_update_a(int new_a) {
struct foo *new_fp = NULL;
struct foo *old_fp = NULL;
new_fp = kmalloc(sizeof(*new_fp), GFP_KERNEL);
spin_lock(&foo_mutex);
old_fp = rcu_dereference_protected(gbl_foo, lockdep_is_held(&foo_mutex));
*new_fp = *old_fp;
new_fp->a = new_a;
rcu_assign_pointer(gbl_foo, new_fp);
spin_unlock(&foo_mutex);
/* 挂接釋放函數 */
call_rcu(&old_fp->rcu, foo_reclaim);
}
// The foo_reclaim() function might appear as follows:
void foo_reclaim(struct rcu_head *rp)
{
struct foo *fp = container_of(rp, struct foo, rcu);
foo_cleanup(fp->a);
kfree(fp);
}
container_of() 原語是一個宏，給定指向結構的指針，結構的類型以及結構内的指向字段，該宏将傳回指向結構開頭的指針。
使用 call_rcu() 可使 foo_update_a() 的調用方立即重新獲得控制權，而不必擔心新近更新的元素的舊版本。 它還清楚地顯示了更新程式 foo_update_a()和回收程式 foo_reclaim() 之間的RCU差別。
在從受RCU保護的資料結構中删除資料元素之後，請使用call_rcu()-以注冊一個回調函數，該函數将在所有可能引用該資料項的RCU讀取側完成後調用。如果call_rcu()的回調除了在結構上調用kfree()之外沒有做其他事情，則可以使用kfree_rcu()代替call_rcu()來避免編寫自己的回調：kfree_rcu（old_fp，rcu）
5、rcu_assign_pointer()
原型：
void rcu_assign_pointer(p, typeof(p) v);
rcu_assign_pointer()通過宏實作。将新指針賦給RCU結構體，指派前的讀者看到的還是舊的指針。
更新者使用這個函數為受rcu保護的指針配置設定一個新值，以便安全地将更新的值更改傳遞給讀者。 此宏不計算rvalue，但它執行某CPU體系結構所需的記憶體屏障指令。保證記憶體屏障前的指令一定會先于記憶體屏障後的指令被執行。
它用于記錄
（1）哪些指針受RCU保護以及
（2）給定結構可供其他CPU通路的點。 rcu_assign_pointer()最常通過_rcu清單操作原語（例如list_add_rcu()）間接使用。
6、rcu_dereference()
原型：
typeof(p) rcu_dereference(p);
與rcu_assign_pointer()類似，rcu_dereference()也必須通過宏實作。
讀者通過rcu_dereference()擷取受保護的RCU指針，該指針傳回一個可以安全解除引用的值。 請注意，rcu_dereference()實際上并未取消對指針的引用，相反，它保護指針供以後取消引用。 它還針對給定的CPU體系結構執行任何所需的記憶體屏障指令。
常見的編碼實踐是使用rcu_dereference() 将一個受rcu保護的指針複制到一個局部變量，然後解引用這個局部變量，例如:
p = rcu_dereference(head.next);
return p->data;
然而，上述情況可以整合成如下一句：
return rcu_dereference(head.next)->data;
7、核心常見使用執行個體
rcu_read_lock();
list_for_each_entry_rcu(pos, head, member) {
// do something with `pos`
}
rcu_read_unlock();
/* p 指向一塊受 RCU 保護的共享資料 */
/* reader */
rcu_read_lock();
p1 = rcu_dereference(p);
if (p1 != NULL) {
printk("%d\n", p1->field);
}
rcu_read_unlock();
/* free the memory */
p2 = p;
if (p2 != NULL) {
p = NULL;
synchronize_rcu();
kfree(p2);
}