標籤：

RCU鎖

03-03

一個讀寫問題

在編寫高性能程序的時候，經常採用的一個無鎖技巧是在更新只發生在最後，並且只有64位的更新（單個匯流排位寬操作）。

舉個例子，我們要修改一個結構體的內容，我們可以只持有這個結構體的指針，在修改的時候重新創建一個結構體，然後在新的結構體上把要修改的內容修改好，最後再進行一次指針內容交換即可完成結構體的更新。

struct A{
int a;
int b;
int c;
};

A* a = new A;

bool change(){
A* b = new A;
b->a=1;
b->b=2;
b->c=3;
A* tmp = a;
a=b;
free(tmp)
}

如上述代碼，在change的時候將a結構體內容的三個域的更新變為一個指針內容的更新。這樣就不需要加鎖了。

這在簡單的程序中經過仔細思考下是沒有問題的。能夠這麼寫的話，就代表了一個深思熟慮的思考過程了。因為簡單的這麼寫，是有很多特殊情況的。

比如，我們思考a原來的內容有其它的讀取者正在讀取其中的內容，而其他的線程調用change函數會立刻把原來的結構體釋放，導致其他在讀取的線程輕則只是讀取到錯誤的信息，重則進行指針的二次引用訪問了非法地址導致core dump。

我們思考在什麼場景可以不用考慮這個問題。當結構體是簡單的內容結構體，中間沒有指針的時候，我們就不擔心其他讀取者二次引用，最多在讀取的過程中讀取到錯誤的內容，而如果程序本身可以對讀取錯誤包容，那麼就可以簡單的這麼組織邏輯，這就是最高效原始的RCU思路。

事實上，這麼組織代碼，讀取到錯誤的內容的概率遠比想像的大。這個讀取錯誤不一定是因為該塊內存被釋放進而被其他人使用修改了，還有一個可能是因為CPU的亂序執行能力。因為在亂序執行的情況下，a=b有可能發生在b->c=3的前面。也就是說當結構體的內容正確的設置之前，指針就可能被提前設置了。

還有第三個可能導致讀取錯誤的原因，這個原因是發生在編譯器的優化策略上。

bool read(){
A* tmp = a;
if (tmp != NULL) {
do_something_with(tmp->a, tmp->b, tmp->c);
}
}

上述寫法在有的優化策略上有可能導致tmp->a,tmp->b的讀取發生在tmp=a之前。這個並不是因為亂序引擎引起的，反而是因為編譯器優化引起的。確切的說，這是不恰當的優化。值的提前索引。不過這種優化好像在gcc，llvm上不存在。

解決二三兩個讀取錯誤問題

我們先解決這個因為亂序導致的讀取不正確的問題。防止亂序的通常做法就是內存柵。巧的是，內存柵同時可以預防編譯器的過度優化，所以用內存柵的方法就可以同時解決二三兩個問題。

RCU並沒有直接讓使用者自己去使用內存柵，而是封裝了一個函數rcu_assign_pointer(a,b)。相當於先用內存柵防止亂序，再執行a=b。這一步是應用在寫的一端的，也就是我們這裡的change函數中。內存柵本身也存在讀和寫兩種情況，分別用來確保寫一致和讀一致兩種情況。

但是在讀的時候，也就是我們的read函數，並不存在這種防止寫亂序的賦值場景，而是讀取的順序問題。RCU又定義了一個新的函數rcu_dereference，這樣我們的代碼就會變成A* tmp = rcu_dereference(a); 這個rcu_dereference同樣的是一個讀內存柵，它保證了編譯器不會過度優化。

所以，我們初步的得到一個階段性的結論，為了解決CPU亂序和編譯器過度優化導致的讀取錯誤的問題，有rcu_assign_pointer和rcu_dereference兩個函數的實現，用內存柵的方式達到了這個目的。

解決第一個讀錯誤的問題

寫操作一個很大的問題是要同時刪除之前的數據結構，這個時候有其他的讀者在使用這個結構的時候，就會導致讀取問題。解決這個問題有兩個顯而易見的思路，一個是引用計數，銷毀僅發生在引用計數為0的情況下。另外一個方式是寫阻塞，寫操作要等到所有的讀操作全部完成才能繼續。

引用計數的方式最優雅，不需要阻塞。但是引用計數需要被操作的數據結構本身參與，並且要維護引用計數不為0的鏈表，不同的數據結構要考慮很多問題。這種用法只能用在特定的系統中，也就是數據結構本身可以去設計適配這種思路。這顯然不會發生在內核的通用機制中。像DPVS的實現中，對資源都進行了引用計數的設計，專用系統專門處理，從具體的業務場景上實現了RCU的思路就是非常好的工程實踐。

等待的方式幾乎是所有鎖的通用做法，由於RCU是用在單寫多讀的情況下，如果多寫需要自己加寫鎖，這並不影響RCU機制的運行，只是會降低效率。因為RCU的實現在寫的時候是非常的重量級的。它要等待所有的讀操作都結束。

這個等待讀操作都結束，在很多其他的同步機制中都有類似的思想，但是都是通過一個類似引用計數的變數來控制的，也就是說專門的場景有專門的鎖數據結構來判斷並發程度。RCU的最大特點就是並沒有採用這種專門的鎖結構，而是用了一個系統層面的機制來做到。與其他的鎖一樣，RCU的讀取操作也有臨界區，進入臨界區和出臨界區必須成對出現。

臨界區函數是rcu_read_lock()和rcu_read_unlock() 。與其他的鎖實現的一個很大的區別是，這個進入臨界區和出臨界區非常的輕量，僅僅是禁止當前進程被搶佔和打開搶佔。也就是說，RCU的讀取操作只需要關閉搶佔，退出臨界區的時候打開搶佔即可。這兩個操作都是很輕量級的。

在更新的操作里，要同時調用synchronize_rcu()函數，這個函數可以阻塞到所有的讀臨界區都退出然後才會繼續執行。不同於自旋鎖，這個函數是類似於加鎖處於阻塞狀態，不會持續佔用CPU。

bool change(){
A* b = new A;
b->a=1;
b->b=2;
b->c=3;
A* tmp = a;
a=b;
synchronize_rcu();
free(tmp)
}

在釋放原內存的時候，增加synchronize_rcu()函數，該函數能夠檢測所有的讀取臨界區退出之後才會繼續執行，仍舊是讀寫配合的使用方式。

總結一下，RCU的讀操作用到的幾個主要函數是rcu_dereference(), rcu_read_lock(), rcu_read_unlock(). 寫操作用到的幾個主要函數是rcu_assign_pointer()和synchronize_rcu()。這一系列函數都是為了解決原始的RCU思想的讀到數據錯誤的問題的。

整個使用中，讀操作非常輕量級，不涉及到實際的鎖操作，讀操作無論如何都不會阻塞。但是帶來的是寫操作的嚴重損耗。因為RCU用於處理一寫多讀的場景，拋開這個使用場景使用RCU是不合適的。至於如何通過讀操作關閉搶佔來與寫操作的阻塞聯動起來，是一個很複雜的話題。見後續說明。

其他問題的提出

  1. 寫操作在等待刪除舊內容的過程中，會來新的請求。新的請求使用新的內容，還是舊的內容？
  2. 有沒有可能走引用計數的思路實現整個系統，避免對業務數據結構的入侵？
  3. rcu鎖和seqlock和rwlock的區別在哪裡？
  4. 讀臨界區和寫同步是如何聯動的？
  5. 臨界區中的代碼是否允許睡眠和阻塞？
  6. rcu鎖的實際應用場景舉例。hlist，reuseport

第一個問題很好回答，這也是RCU的精髓，就是寫發生的期間的讀操作仍舊讀到的是舊的數據，並且系統允許這個老數據讀取的存在。

第二個思路有人擔心集中式的引用計數會有cache的問題，分散式的又需要應用場景數據結構的參與。事實上，資源代價確實很高。

3. rcu鎖和seqlock和rwlock的區別

rcu鎖在讀的一側不存在加鎖，那麼就意味著在讀的一側永遠不會阻塞，也就更不會死鎖。

rwlock讀寫鎖當發生寫數據的時候，讀的部分需要阻塞等待，這個等待是自旋的。讀寫鎖的最大特點是寫者是排他性的，一個讀寫鎖同時只能有一個寫者或多個讀者，但不能同時既有讀者又有寫者。也就是說，在寫操作發生的時候，讀操作要全部自旋等待寫操作完成。這對於耗時比較多的寫操作來說，更新期間系統幾乎不可用。例如路由表的更新時間比較久，如果使用讀寫鎖，路由表的服務質量會顯著下滑。而RCU在寫的過程中所有的讀操作都不需要暫停，只是更新發生之前進行的讀操作讀取到的是老的條目，更新發生之後的讀操作讀取到的是新條目。這在很多更新並不代表老的內容不可用的場景是非常重要的能持續提供服務的特性。這就意味著整個系統穩定的不中斷的對外提供服務能力。

讀寫鎖和RCU鎖在寫操作發生時讀操作的狀態

seqlock能夠在這個問題上比rwlock處理的好，可能可以說是某種程度上的好，實際的效果並不一定。因為seqlock的原理是允許讀寫同時發生，但是在寫操作發生之後的讀取會被回滾丟棄，重新讀取新的值。也就是說seqlock仍然是一個順序讀寫的屏障，所以叫做順序鎖。順序鎖是對讀寫鎖的升級，寫操作發生的時候會更快速的獲得鎖。因為seqlock只有寫操作需要加鎖，寫操作發生的時候不需要等待讀的鎖釋放。而讀寫鎖則是讀寫互斥，當寫入發生的時候需要等待讀取結束。

但是這裡討論的都是一個寫操作多個讀操作的時候。當同時有很多的寫操作的時候，RCU幾乎沒有什麼用，仍然需要其他的鎖機制來提供多寫的順序化能力。但是順序鎖和讀寫鎖都是可以天然的處理多寫的問題的，雖然代價也很高。讀寫鎖的應用場景是幾乎萬能的，順序鎖不能用於保護指針資源，因為指針資源的更改繼續允許讀取可能會導致二次引用引起core dump。但是順序鎖比讀寫鎖性能更好，所以順序鎖對讀寫鎖也不是取代關係，而是很多場景下的優化關係。

從性能上看seqlock與RCU最接近，RCU的寫性能不如seqlock，seqlock還能提供多寫的支持。兩者在讀上都沒有性能代價，但是seqlock在讀取的時候遇到不一致需要回滾，而RCU不需要回滾。所以兩者的區別在於業務場景的問題。如果業務要求新數據到達的時候，舊數據必須立刻作廢，就只能用seqlock，反之，如果沒有這個要求，可以考慮RCU。而RCU真正強大的地方，並不在於讀寫鎖的控制能力，而是它不需要為每個資源準備一個鎖結構。比如seqlock針對每個要保護的資源的sequence值。

4.讀臨界區和寫同步的聯動

讀寫聯動的演算法的關鍵在synchronize_rcu函數的實現上。

內核把從寫操作開始到等待所有讀操作結束的這段時間叫做寬限期（Grace Period）。synchronize_rcu函數就是等待寬限期結束的函數。

我們很容易發現，RCU的讀鎖是沒有參數的，也就是全局使用相同的讀鎖，都是關閉當前CPU的搶佔。

static inline void __rcu_read_lock(void)
{
preempt_disable();
}

static inline void __rcu_read_unlock(void)
{
preempt_enable();
}

那麼判斷當前沒有在臨界區也不是針對某一個資源的，而是直接針對整個內核中的所有資源的，當寫操作發生的時候，synchronize_rcu開始計算，當所有的CPU都發生過搶佔的時候，就可以說明是當前沒有在進行的讀操作了，寫操作就可以順利的繼續執行。

內核中有一個rcu_gp_kthread線程，專門用來發起寬限期和收集各個CPU的搶佔信息，在滿足條件後通知寫操作繼續。由於RCU是全局的，對不同資源的寫操作有可能同時在產生，這個時候在一個寬限期結束的時候，會同時喚醒所有在等待的寫操作。

也正是因為RCU可以算是一個超大力度的內核鎖，任何的寫請求都要等待整個系統的讀請求完成，所以RCU鎖對寫操作時非常不友好的。這也是RCU鎖用在多讀少寫的情況。

5.其他種類的RCU

RCU的經典實現考慮的問題比較少，有很多限制，比如沒有讀的優先順序概念，讀臨界區內不允許睡眠和阻塞。針對這些特殊的需求，RCU還實現了很多的變種。

可睡眠RCU

Sleepable RCU [LWN.net]?

lwn.net圖標

可搶佔RCU Realtime RCU

RCU ClassicRCU BHRCU SchedRealtime RCUSRCU

實時RCU

6.rcu鎖的實際應用場景舉例：hlist

Hlist是開鏈哈希表常用的鏈表數據結構，hlist本身不是線程安全，多線程的情況下要加鎖。但是內核提供了一個帶RCU借口的hlist實現（類似的實現還有list），通過帶rcu後綴的API直接封裝了RCU的鎖操作。

hlist_add_after_rcu()
hlist_add_before_rcu()
hlist_add_head_rcu()
hlist_replace_rcu()
hlist_del_rcu()
hlist_for_each_entry_rcu()

還有幾個特殊情況的API，但是主要用的就是上述的幾個。實際上，hlist_del_rcu()並沒有rcu相關的操作，與普通hlist刪除差不多。

update的更新操作就對應hlist_replace_rcu() 函數，讀取操作就對應hlist_for_each_entry_rcu()函數。

#define hlist_for_each_entry_rcu(pos, head, member)
for (pos = hlist_entry_safe (rcu_dereference_raw(hlist_first_rcu(head)),
typeof(*(pos)), member);
pos;
pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu(
&(pos)->member)), typeof(*(pos)), member))

遍歷操作很簡單，就是在正常的遍歷操作的基礎上增加了rcu的讀保護機制。所以在使用這個函數的時候，遍歷函數的外面還需要加上rcu_read_lock()和rcu_read_unlock()函數包起來，才組成了RCU的讀取臨界區。

這個遍歷的過程如果在遍歷中刪除了當前遍歷到的pos節點，遍歷就會中斷，為了能在遍歷中同時刪除節點，hlist_del_rcu()的定義如下。在調用hlist_for_each_entry_rcu遍歷的時候，可以直接在循環內部刪除當前entry。

static inline void hlist_del_rcu(struct hlist_node *n)
{
__hlist_del(n);
n->pprev = LIST_POISON2;
}
static inline void hlist_del(struct hlist_node *n)
{
__hlist_del(n);
n->next = LIST_POISON1;
n->pprev = LIST_POISON2;
}

hlist_del_rcu函數與普通刪除的區別在於n->next不能被下毒，也就是遍歷可以繼續執行了。但是也僅限於此，刪除操作仍然不能跟添加操作並行發生，單讀使用需要額外加鎖，但是如果與遍歷函數一起使用，由於外部與RCU讀鎖，與寫操作就不衝突了，就可以直接使用。所以刪除操作大部分發生在RCU遍歷之中。

static inline void hlist_replace_rcu(struct hlist_node *old,
struct hlist_node *new)
{
struct hlist_node *next = old->next;

new->next = next;
new->pprev = old->pprev;
rcu_assign_pointer(*(struct hlist_node __rcu **)new->pprev, new);
if (next)
new->next->pprev = &new->next;
old->pprev = LIST_POISON2;
}

replace函數是一個典型的update操作，但是沒有調用同步函數，所以這個函數不會等待讀操作完就可以執行。原因也很簡單，這個函數並不涉及內存回收。

static inline void hlist_add_head_rcu(struct hlist_node *n,
struct hlist_head *h)
{
struct hlist_node *first = h->first;

n->next = first;
n->pprev = &h->first;
rcu_assign_pointer(hlist_first_rcu(h), n);
if (first)
first->pprev = &n->next;
}

同樣add操作也是一樣，沒有涉及內存回收，整個RCU操作中只涉及到內存柵。無論是add還是del操作都是排他的，也就是意味著同時只能發生一個寫操作。這個保證就只能由使用者自己用其他的鎖機制來保證了。這裡封裝的RCU的API的最大意義是可以將修改與遍歷操作同時用，不需要加鎖。

這樣就產生了另外一個疑問，既然所有的API中都沒有synchronize_rcu()函數，那為何遍歷函數的外部要求加rcu_read_lock()和rcu_read_unlock()呢？因為修改操作不涉及到釋放內存，前面說的很清楚，整個RCU的核心是釋放內存帶來的讀取錯誤問題，既然hlist操作（list操作同樣）都在語意上不釋放內存，所以整個API的內部都沒有臨界區和寫同步的函數使用。但是，如果使用者需要在從鏈表上刪除節點的同時釋放內存，就需要在遍歷的外部加臨界區，在釋放內存之前加synchronize_rcu()函數。

總結一下，hlist的RCU介面只提供了內存柵層面的並發支持，只是解決了二三兩個問題。至於第一個問題，是否訪問到錯誤的內存內容，取決於使用者是否需要釋放鏈表對應的內存，如果需要就需要在遍歷讀取的時候加rcu_read_lock()和rcu_read_unlock()，在釋放內存之前加synchronize_rcu()。

7.rcu鎖的實際應用場景舉例：reuseport


推薦閱讀：

TAG:Linux內核 |