Linux核心RCU(Read Copy Update)鎖簡析

前面寫過一篇關於Linux RCU鎖的文章《RCU鎖在Linux核心的演變》，現在我承認，那個時候我雖然懂了RCU鎖，但是我沒有能力用一種非常簡單的描述把Linux的實現給展示出來，有道是你能給別人用你自己的方式非常簡潔地描述清楚，你才是真正的精通它，否則，無異於背誦。換個說法，如果你在被面試，在短時間內靠嘴說給面試官，且他還要能聽明白，就說明自己真的懂了，這種時候，是不會給你機會分析原始碼的，也不可能讓你背誦原始碼。

近期又碰到了這個話題，我不能自詡自己對RCU鎖是多麼精通，但是起碼，和前面這篇相比，我確實有所進步，因此在這個颱風肆虐的次日，我嘗試著用我自己的方式描述一下Linux對RCU鎖的一種實現方式，作為《RCU鎖在Linux核心的演變》這篇文章的補充。本文不配圖，沒程式碼，只是文字。

宣告：如果你還不知道RCU鎖是什麼，請自行baidu，本文不再贅述概念，但是這也就等於說，如果我自己有一天忘記了RCU，我也不能指望從本文中得到任何幫助，我總是這樣，不是嗎？能力在忘不在記，得其義而忘其形。

RCU要素

RCU鎖的要素包括

讀標誌

如果一個Reader企圖佔據一把RCU鎖，它是不需要付出任何代價的，只需要設定一個標誌，讓外界知道有Reader在佔據這把RCU鎖，多個Reader可以共同持有一把RCU鎖。

寫時拷貝

如果有一個Write企圖更新RCU鎖所保護的資料，那麼它會首先檢視該RCU鎖的讀標誌，如果有該標誌，說明有最少一個Reader持有了該RCU鎖，它需要對原始資料make a copy，寫這個副本並將更新過的副本儲存在某處，等待時機用該副本更新原始資料。

更新時機

這個時機就是用副本更新原始資料的時間點，這個時間點如何確定是RCU鎖實現的演算法核心，它直接可以確定所有的資料結構。確切來講，Writer必須waitting for all readers leaving，方可Update原始資料，問題是，它是怎麼知道所有的Reader都離開了呢？

Linux核心對RCU鎖的幾種實現

1.原始實現-利用搶占禁止

Linux核心於2.6核心引入了RCU鎖的概念，在第一個版本中，它利用了搶占禁止的方式來標誌有Reader持有RCU鎖，這意味著期間不能發生task切換(指的是task_struct所代表的sched entity切換)。那麼所有Reader均已經釋放RCU鎖的標誌就是，task切換了，因此很簡單，用副本Update原始資料的時機就是task切換時。

所有的Write會將自己寫的副本掛在一個list上，在task切換的時候會touch這個list，如果該list非空，則遍歷每一個元素，Update原始資料。

評價[該部分與實現無關，純形而上的，可以忽略]

這就是第一版的原始實現，它是否合理姑且不論，確實，它可以工作。但是：

a.它這種實現是否會影響排程子系統的時延

b.由於禁用搶占，搶占粒度變粗，對互動性是否會有影響

c.對CPU間的task負載均衡的影響呢

我們發現，由於RCU的這個實現不是靠自身機制實現的，它不可避免地會影響到系統的核心機制，比如排程，負載均衡等，這意味著它不能長久，也無法經歷複雜的演變，因為隨著它在這條路上的逐步演進，對系統核心機制的影響將越來越大，故而，它必須從系統層面剝離出來。確實，它也是這麼做的，這就是第二代RCU實現-可搶佔RCU鎖。

2.新實現-利用階段計數器

需要一種更加有效的方式來標誌Reader已經持有鎖-第一要素讀標誌，並且這個標誌要盡可能精確，且不能使用系統核心的機制，要做成完全封閉的閉環，不依靠外部當然也就不會影響外部。

純天然的想法就是使用計數器，每一把RCU持有一個Reader計數器，一旦有Reader前來持鎖，只需要一個原子操作，將該計數器加1即可，Writer寫資料時，發現計數器不是0就意味著需要make a copy了-第二要素寫時拷貝(COW-Copy On Write)。現在的問題是第三要素，Writer怎麼知道所有的Reade都已經將鎖釋放了呢？？

純天然的想法就是在某個Reader釋放鎖的時候，計數器減1，當計數器重新變為0的時候，這就是副本更新原始資料的時機。確實是這樣，但是按照持鎖和解鎖的分布看，它們應該是均等的，這意味著計數器的值會在一個期望值上下波動，變成0的希望及其渺茫，因此需要引入另一個參量，即階段。

將唯一的那個RCU計數器分裂為兩個計數器：old readers和new readers。

太初，任選某一個時刻，將RCU鎖當前的計數器(稱為原始計數器)值複製一份存入old readers，計數器清0，原始計數器改稱為new readers。複製結束的當下，new readers計數器為0，old readers計數器為現階段持有鎖的reader的數量。並且持鎖者task(即task_struct)與RCU鎖之間保持關聯(難道不是一個task_struct欄位可以搞定的嗎？)，task永遠知道自己是new reader還是old reader。

此時，就可以明確定義lock和unlock的行為了：

lock--設定自己的task為new reader，將RCU的new reader計數器加1。

unlock--獲取自己的task是new reader還是old reader，將自己所在的reader計數器減1。

此時很明確的事實是，old reader計數器總是會遞減而不會遞增，而new reader不但會遞增也會遞減，這樣，選擇Update的時機也很明確了，那就是，old reader計數器變為0，這個時刻，就該將所有的副本覆蓋原始資料了。

現在總結所有的三個要素：

讀標誌

為該RCU鎖的new reader計數器加1

寫時拷貝

如果該RCU鎖的old reader計數器不為0，則執行寫時複製。

更新時機

每次unlock操作，都會將本task的reader計數器(或者是new reader，或者是old reader)減1，一旦該RCU鎖的old reader計數器變成0，則執行所有的Update操作。

評價[該部分與實現無關，純形而上的，可以忽略]

持有RCU鎖的reader，可以睡眠，可以被搶占，可以排程到別的CPU上，完全是封閉的，和系統其它的機制無關。然而，我一直在思考一個更好的實現，只因瘋子不給力！！

3.RCU Tree實現(實在是沒有2好)

後續補充。

本文永久更新連結地址：http://www.linuxidc.com/Linux/2015-07/120043.htm