RCU（Read Copy Update）十年計

本文主要摘抄并翻譯自 http://www2.rdrop.com/~paulmck/techreports/RCUUsage.2013.02.24a.pdf ，同時也加入了譯者在核心研發中的一些感悟，寫出來以飨讀者。

介紹

核心開發者使用了各種不同的同步原語來提升核心的并行性：細粒度鎖（fine-grained locks），無鎖化資料結構（lock-free data structures），CPU本地資料結構（per-CPU data structures），以及讀拷貝更新機制(RCU)。RCU機制在2002年開始在linux kernel中使用，在2013年已經超過6500個API在核心中被使用。RCU的成功得以與在并發讀與寫情況下的高性能，主要包括兩個語義：讀者在RCU讀關鍵區間（RCU read-side critical sections）中通路資料結構；寫者使用RCU同步語句等待已在讀關鍵區間的讀者完成。

使用RCU的好處

RCU的存在滿足了核心的三點需求：

在有寫者的情況下支援并行讀

核心中有許多的資料結構被設計來支援大量的讀寫操作，特别是VFS以及網絡子系統。

舉個例子，VFS中使用dentry來緩存最近通路的檔案中繼資料，因為應用程式會通路大量的檔案，核心需要經常通路或者替換dentry，是以理想情況下線程在讀取緩存資料的同時不希望與寫沖突。RCU即滿足了這種場景的需要。

很低的計算與存儲代價

低空間代價是很重要的，因為核心會同時通路成千上萬的對象，比如，在一些伺服器中緩存了800萬個dentry，就算在dentry的結構中加入極少的位元組也會帶來很大的存儲代價。

低計算代價也很重要，因為核心頻繁通路的資料結構往往是很短的代碼路徑，比如SELinux通路資料結構AVC，隻有很段的代碼路徑進行通路，如果通過鎖來保護，由于拿鎖放鎖帶來的cache miss可能會有幾百個cycle，而這就已經是通路AVC資料結構的一倍時間了，是以低執行代價在一些場景中非常重要。

讀操作确定的運作時間

在NMI處理函數中通路共享資料的時候，線程可能在執行關鍵區域被中斷。如果使用spinlock有可能帶來死鎖。而如果使用無鎖化的資料結構，那麼在沖突的時候就需要多次嘗試直到成功，而這點卻使得運作的時間變成非确定性的。

回到相關的一些同步原語設計：讀寫鎖，本地鎖，全局鎖，事務性記憶體，都無法滿足上訴讨論的特性。就算僅使用一個32位的字段存儲鎖資料，在很多場景下也是不可接受的。并且這些鎖還會帶來代價很大的原子操作以及記憶體屏障。

RCU的設計

RCU原語包含兩個方面：RCU臨界區以及RCU同步。

線程通過調用rcu_read_lock進入臨界區，離開則是使用rcu_read_unlock。當需要進行RCU同步的時候，則使用synchronize_rcu，當這個接口被調用之後，會等待所有的進入臨界區的線程都退出了才會傳回。synchronize_rcu既不會阻止線程新進入臨界區，也不會去等待synchronize_rcu調用之後進入臨界區的線程。RCU允許線程去等待已在臨界區的讀者完成，但是不會提供多個寫者之間的同步原語，多個寫者還是需要鎖機制來保證。

為了滿足讀寫并發、低空間低計算代價、以及讀操作确定時間，Linux核心通過排程器上下文切換的契機進行RCU的同步處理。在進入臨界區的時候禁止搶占，那麼一次的上下文切換就意味着線程已經出了臨界區。synchronize_rcu則隻需要等待所有的CPU經曆一次上下文切換即可。

上述代碼描述了一個RCU的簡單實作。調用rcu_read_lock會禁止搶占并且是可以嵌套的。rcu_read_unlock允許搶占。為了保證所有的CPU都經曆了一次上下文切換，線程在每個CPU上執行synchronize_rcu。我們注意到執synchronize_rcu的代價和執行rcu_read_lock與rcu_read_unlock的線程數目無關，隻與CPU的個數有關。

在實際實作中，synchronize_rcu會等待所有的CPU都經曆過一次上下文切換，而不是去在每一個CPU上排程一下線程。

除了使用同步的synchronize_rcu，線程還可以使用異步的原語call_rcu，當所有的CPU都經曆了上下文切換，則會通過一個回調函數來完成特定的需求。

由于RCU的讀者和寫者并行執行，在設計上還有需要考慮亂序問題，例如編譯器指令亂序以及訪存亂序。如果不能很好的保證順序，讀者有可能通路到一個寫者初始化之前的值，造成空指針通路之類的問題。RCU通過接口rcu_dereference和rcu_assign_pointer來保證訪存順序。這兩個接口通過體系結構相關的一些記憶體屏障指令或者編譯器指令來強制保證訪存順序。

rcu_read_lock() -- Begin an RCU critical section.

rcu_read_unlock() -- Complete an RCU critical section.

synchronize_rcu() -- Wait for existing RCU critical sections to complete.

call_rcu(callback, arguments...) -- Call the callback when existing RCU critical sections complete. Signal the intent to deference a pointer in an RCU critical section.

rcu_dereference(pointer) -- Signal the intent to deference a pointer in an RCU critical section.

rcu_assign_pointer(pointer_addr, pointer) -- Assign a value to a pointer that is read in RCU critical sections.

上述代碼展示了Linux中RCU的接口。

使用RCU的幾個場景

Wait for completion

Linux核心使用RCU進行NMI處理函數的登出操作。在登出之前，核心必須保證沒有CPU目前正在執行NMI處理函數，否則，就有可能出現核心将NMI處理函數的所在的記憶體釋放了，但CPU卻嘗試通路處理函數。

rcu_list_t nmi_list;
spinlock_t nmi_list_lock;
void handle_nmi()
{
rcu_read_lock();
rcu_list_for_each(&nmi_list, handler_t cb)
cb();
rcu_read_unlock();
}
void register_nmi_handler(handler_t cb)
{
spin_lock(&nmi_list_lock);
rcu_list_add(&nmi_list, cb);
spin_unlock(&nmi_list_lock);
}
void unregister_nmi_handler(handler_t cb)
{
spin_lock(&nmi_list_lock);
rcu_list_remove(cb);
spin_unlock(&nmi_list_lock);
synchronize_rcu();
}           

上面的僞代碼展示了NMI系統的工作流程nmi_list儲存了NMI的處理函數，并且使用spinlock進行寫保護，但支援無鎖化的讀操作。rcu_list_for_each在周遊每一個元素的時候會調用rcu_dereference，rcu_list_ad和rcu_list_remove則會調用rcu_assign_pointer。在一個RCU臨界區内，NMI系統會執行所有的NMI處理函數。登出處理函數的時候，NMI系統會先清空list，然後調用synchronize_rcu保證它傳回時所有的處理函數都已經完成了。

在此場景下，如果想使用讀寫鎖，很容易造成死鎖，CPU在unregister_nmi_handler中拿鎖的情況下，依然會被NMI打斷，NMI處理函數中也會嘗試拿鎖，造成死鎖。

引用計數

RCU是一個替代引用計數的很好的辦法。不需要顯式對特定的資料對象進行引用計數，對象的使用者在讀臨界區進行操作即可，為了釋放一個資料對象，線程可以同調用 call_rcu防止其他線程持有對象的指針。

void udp_sendmsg(sock_t *sock, msg_t *msg)
{
ip_options_t *opts;
char packet[];
copy_msg(packet, msg);
rcu_read_lock();
opts = rcu_dereference(sock->opts);
if (opts != NULL)
copy_opts(packet, opts);
rcu_read_unlock();
queue_packet(packet);
}
void setsockopt(sock_t *sock, int opt,
void *arg)
{
if (opt == IP_OPTIONS) {
ip_options_t *old = sock->opts;
ip_options_t *new = arg;
rcu_assign_pointer(&sock->opts, new);
if (old != NULL)
call_rcu(kfree, old);
return;
}
/* Handle other opt values */
}           

上面的僞代碼展示了RCU在Linux網絡棧中取代引用計數的應用。該例子利用RCU對IP options進行引用計數，表示目前核心網絡棧正在拷貝IP options到一個packet中。udp_sendmsg調用rcu_read_lock與rcu_read_unlock标記臨界區的進入與退出。而應用程式可以通過系統調用sys_setsockop(最終到核心的setsockopt函數)對IP options進行修改。修改的過程是先将新值拷貝，然後調用call_rcu進行舊值的删除。

類型安全記憶體（Type Safe Memory）

類型安全記憶體指的是在釋放之後保留它的類型，這個對一個線程已經釋放某一個對象，而有其他線程仍然持有這個對象的引用很有幫組。一般來說，RCU可以直接使用因為它可以保證在其他線程持有引用的情況下記憶體對象不會重複利用。然而有些情況下是RCU覆寫不到，比如異步是否對象的調用可能會被阻塞。這樣的話使用RCU不能提供存在的保證，而是用來實作類型安全記憶體。

Linux slab配置設定器就是使用這個的例子，每一個slab配置設定器首先利用頁配置設定器，并把他們劃分成單一類型的對象進行管理。當一個完整的頁中對象都變成free時，slab配置設定器可以将這個頁還給頁配置設定器。如果開發者不希望這個頁被重複使用為不同的對象類型，可以設定特殊SLAB_DESTROY_BY_RCU，這樣如果這個slab中對象通過RCU臨界區通路的話，這個方法可以保證類型安全記憶體。

訂閱釋出（Publish-Subscribe）

在訂閱-釋出使用時，寫者會調用rcu_assign_pointer來釋出，并發的讀者使用rcu_dereference來擷取指針。

syscall_t *table;
spinlock_t *table_lock;
int invoke_syscall(int number, void *args...)
{
syscall_t *local_table;
int r = -1;
rcu_read_lock();
local_table = rcu_deference(table);
if (local_table != NULL)
r = local_table[number](args);
rcu_read_unlock();
return r;
}
void retract_table()
{
syscall_t *local_table;
spin_lock(&table_lock);
local_table = table;
rcu_assign_pointer(&table, NULL);
spin_unlock(&table_lock);
synchronize_rcu();
kfree(locl_table);
}           

上面是linux中使用訂閱-釋出一個例子，核心通過使用rcu_assign_pointer釋出指針來追加系統調用表，在索引系統調用表與執行系統調用之前調用rcu_read_lock，并通過調用rcu_deference讀取擴充的系統調用表。

替代讀寫鎖（Read-Write Lock Alternative）

Linux中的RCU最常用的是替代讀寫鎖，相對傳統的讀寫鎖，RCU除了可以提供高性能以外，還能夠防止死鎖的發生。Linux使用單一整型變量來實作讀寫鎖，為了保證鎖在讀寫狀态，線程必須使用昂貴的原子指令和記憶體屏障來實作。

使用RCU作為讀寫鎖的一個例子是同步通路PID哈希表：

pid_table_entry_t pid_table[];
process_t *pid_lookup(int pid)
{
process_t *p;
rcu_read_lock();
p = pid_table[pid_hash(pid)].process;
if (p)
atomic_inc(&p->ref);
rcu_read_unlock();
return p;
}
void pid_free(process *p)
{
if (atomic_inc(&p->ref))
free(p);
}
void pid_remove(int pid)
{
process_t **p;
spin_lock(&pid_table[pid_hash(pid)].lock);
p = &pid_table[pid_hash(pid)].process;
rcu_assign_pointer(p, NULL);
spin_unlock(&pid_table[pid_hash(pid)].lock);
if (*p)
call_rcu(pid_free, *p);
}           

使用RCU與讀寫鎖一個重要的差別是RCU支援并發讀寫相同的資料，而讀寫鎖保證他們的互斥。但是RCU并發通路的結果與讀寫鎖不同，比如上面的例子，設想兩個現象同時增加A與B到不同哈希桶中，一個并發執行的讀程序可能先找到A，但是找不到B。而另外一個讀者可能找到B但是沒有找到A，這個結果是合理的，但是在使用讀寫鎖時不會發生。