深入剖析Linux RCU原理（一）初窺門徑
說明：
Kernel版本：4.14
ARM64處理器，Contex-A53，雙核
使用工具：Source Insight 3.5， Visio
1. 概述
RCU, Read-Copy-Update，是Linux內(nèi)核中的一種同步機(jī)制。RCU常被描述為讀寫鎖的替代品，它的特點是讀者并不需要直接與寫者進(jìn)行同步，讀者與寫者也能并發(fā)的執(zhí)行。RCU的目標(biāo)就是最大程度來減少讀者側(cè)的開銷，因此也常用于對讀者性能要求高的場景。
優(yōu)點：
讀者側(cè)開銷很少、不需要獲取任何鎖，不需要執(zhí)行原子指令或者內(nèi)存屏障；
沒有死鎖問題；
沒有優(yōu)先級反轉(zhuǎn)的問題；
沒有內(nèi)存泄露的危險問題；
很好的實時延遲；
缺點：
寫者的同步開銷比較大，寫者之間需要互斥處理；
使用上比其他同步機(jī)制復(fù)雜；
來一張圖片來描述下大體的操作吧：
多個讀者可以并發(fā)訪問臨界資源，同時使用
rcu_read_lock/rcu_read_unlock來標(biāo)定臨界區(qū)；寫者(
updater)在更新臨界資源的時候，拷貝一份副本作為基礎(chǔ)進(jìn)行修改，當(dāng)所有讀者離開臨界區(qū)后，把指向舊臨界資源的指針指向更新后的副本，并對舊資源進(jìn)行回收處理；圖中只顯示一個寫者，當(dāng)存在多個寫者的時候，需要在寫者之間進(jìn)行互斥處理；
上述的描述比較簡單，RCU的實現(xiàn)很復(fù)雜。本文先對RCU來一個初印象，并結(jié)合接口進(jìn)行實例分析，后續(xù)文章再逐層深入到背后的實現(xiàn)原理。開始吧！
2. RCU基礎(chǔ)
2.1 RCU基本要素
RCU的基本思想是將更新Update操作分為兩個部分：1）Removal移除；2）Reclamation回收。直白點來理解就是，臨界資源被多個讀者讀取，寫者在拷貝副本修改后進(jìn)行更新時，第一步需要先把舊的臨界資源數(shù)據(jù)移除（修改指針指向），第二步需要把舊的數(shù)據(jù)進(jìn)行回收（比如kfree）。
因此，從功能上分為以下三個基本的要素：Reader/Updater/Reclaimer，三者之間的交互如下圖：
Reader
使用
rcu_read_lock和rcu_read_unlock來界定讀者的臨界區(qū)，訪問受RCU保護(hù)的數(shù)據(jù)時，需要始終在該臨界區(qū)域內(nèi)訪問；在訪問受保護(hù)的數(shù)據(jù)之前，需要使用
rcu_dereference來獲取RCU-protected指針；當(dāng)使用不可搶占的
RCU時，rcu_read_lock/rcu_read_unlock之間不能使用可以睡眠的代碼；Updater
多個Updater更新數(shù)據(jù)時，需要使用互斥機(jī)制進(jìn)行保護(hù)；
Updater使用
rcu_assign_pointer來移除舊的指針指向，指向更新后的臨界資源；Updater使用
synchronize_rcu或call_rcu來啟動Reclaimer，對舊的臨界資源進(jìn)行回收，其中synchronize_rcu表示同步等待回收，call_rcu表示異步回收；Reclaimer
Reclaimer回收的是舊的臨界資源；
為了確保沒有讀者正在訪問要回收的臨界資源，Reclaimer需要等待所有的讀者退出臨界區(qū)，這個等待的時間叫做寬限期（
Grace Period）；
【文章福利】小編推薦自己的Linux內(nèi)核技術(shù)交流群:【749907784】整理了一些個人覺得比較好的學(xué)習(xí)書籍、視頻資料共享在群文件里面，有需要的可以自行添加哦?。。。ê曨l教程、電子書、實戰(zhàn)項目及代碼)? ?
2.2 RCU三個基本機(jī)制
用來提供上述描述的功能，RCU基于三種機(jī)制來實現(xiàn)。
2.2.1?Publish-Subscribe Mechanism
訂閱機(jī)制是個什么概念，來張圖：
Updater與Reader類似于Publisher和Subsriber的關(guān)系；Updater更新內(nèi)容后調(diào)用接口進(jìn)行發(fā)布，Reader調(diào)用接口讀取發(fā)布內(nèi)容；
那么這種訂閱機(jī)制，需要做點什么來保證呢？來看一段偽代碼：
乍一看似乎問題不大，Updater進(jìn)行賦值更新，Reader進(jìn)行讀取和其他處理。然而，由于存在編譯亂序和執(zhí)行亂序的問題，上述代碼的執(zhí)行順序不見得就是代碼的順序，比如在某些架構(gòu)（DEC Alpha）中，讀者的操作部分，可能在p賦值之前就操作了do_something_with()。
為了解決這個問題，Linux提供了rcu_assign_pointer/rcu_dereference宏來確保執(zhí)行順序，Linux內(nèi)核也基于rcu_assign_pointer/rcu_dereference宏進(jìn)行了更高層的封裝，比如list,?hlist，因此，在內(nèi)核中有三種被RCU保護(hù)的場景：1）指針；2）list鏈表；3）hlist哈希鏈表。
針對這三種場景，Publish-Subscribe接口如下表：
2.2.2?Wait For Pre-Existing RCU Readers to Complete
Reclaimer需要對舊的臨界資源進(jìn)行回收，那么問題來了，什么時候進(jìn)行呢？因此RCU需要提供一種機(jī)制來確保之前的RCU讀者全部都已經(jīng)完成，也就是退出了rcu_read_lock/rcu_read_unlock標(biāo)定的臨界區(qū)后，才能進(jìn)行回收處理。
圖中Readers和Updater并發(fā)執(zhí)行；
當(dāng)Updater執(zhí)行
Removal操作后，調(diào)用synchronize_rcu，標(biāo)志著更新結(jié)束并開始進(jìn)入回收階段；在
synchronize_rcu調(diào)用后，此時可能還有新的讀者來讀取臨界資源(更新后的內(nèi)容)，但是，Grace Period只等待Pre-Existing的讀者，也就是在圖中的Reader-4, Reader-5。只要這些之前就存在的RCU讀者退出臨界區(qū)后，意味著寬限期的結(jié)束，因此就進(jìn)行回收處理工作了；synchronize_rcu并不是在最后一個Pre-ExistingRCU讀者離開臨界區(qū)后立馬就返回，它可能存在一個調(diào)度延遲；
2.2.3?Maintain Multiple Versions of Recently Updated Objects
從2.2.2節(jié)可以看出，在Updater進(jìn)行更新后，在Reclaimer進(jìn)行回收之前，是會存在新舊兩個版本的臨界資源的，只有在synchronize_rcu返回后，Reclaimer對舊的臨界資源進(jìn)行回收，最后剩下一個版本。顯然，在有多個Updater時，臨界資源的版本會更多。
還是來張圖吧，分別以指針和鏈表為例：
調(diào)用
synchronize_rcu開始為臨界點，分別維護(hù)不同版本的臨界資源；等到Reclaimer回收舊版本資源后，最終歸一統(tǒng)；
3. RCU示例分析
是時候來一波fucking sample code了。
整體的代碼邏輯：
構(gòu)造四個內(nèi)核線程，兩個內(nèi)核線程測試指針的RCU保護(hù)操作，兩個內(nèi)核線程用于測試鏈表的RCU保護(hù)操作；
在回收的時候，分別用了
synchronize_rcu同步回收和call_rcu異步回收兩種機(jī)制；為了簡化代碼，基本的容錯判斷都已經(jīng)省略了；
沒有考慮多個Updater的機(jī)制，因此，也省略掉了Updater之間的互斥操作；
為了證明沒有騙人，貼出在開發(fā)板上運行的輸出log，如下圖：
4. API介紹
4.1 核心API
下邊的這些接口，不能更核心了。
4.2 其他相關(guān)API
基于核心的API，擴(kuò)展了其他相關(guān)的API，如下，不再詳述：
好吧，羅列這些API有點然并卵。
原文作者：LoyenWang
