深入剖析Linux RCU原理（二）-漸入佳境
說(shuō)明：
Kernel版本：4.14
ARM64處理器，Contex-A53，雙核
使用工具：Source Insight 3.5， Visio
1. 概述
我會(huì)假設(shè)你已經(jīng)看過(guò)了深入剖析Linux RCU原理（一）初窺門(mén)徑
本文將進(jìn)一步去探索下RCU背后的機(jī)制。
2. 基礎(chǔ)概念
2.1?Grace Period
繼續(xù)貼出深入剖析Linux RCU原理（一）初窺門(mén)徑中的圖片：
中間的黃色部分代表的就是
Grace Period，中文叫做寬限期，從Removal到Reclamation，中間就隔了一個(gè)寬限期；只有當(dāng)寬限期結(jié)束后，才會(huì)觸發(fā)回收的工作，寬限期的結(jié)束代表著Reader都已經(jīng)退出了臨界區(qū)，因此回收工作也就是安全的操作了；
寬限期是否結(jié)束，與處理器的執(zhí)行狀態(tài)檢測(cè)有關(guān)，也就是檢測(cè)靜止?fàn)顟B(tài)
Quiescent Status；RCU的性能與可擴(kuò)展性依賴于它是否能有效的檢測(cè)出靜止?fàn)顟B(tài)(
Quiescent Status)，并且判斷寬限期是否結(jié)束。
來(lái)一張圖：
【文章福利】小編推薦自己的Linux內(nèi)核技術(shù)交流群:【749907784】整理了一些個(gè)人覺(jué)得比較好的學(xué)習(xí)書(shū)籍、視頻資料共享在群文件里面，有需要的可以自行添加哦?。。。ê曨l教程、電子書(shū)、實(shí)戰(zhàn)項(xiàng)目及代碼)? ??
2.2?Quiescent Status
Quiescent Status，用于描述處理器的執(zhí)行狀態(tài)。當(dāng)某個(gè)CPU正在訪問(wèn)RCU保護(hù)的臨界區(qū)時(shí)，認(rèn)為是活動(dòng)的狀態(tài)，而當(dāng)它離開(kāi)了臨界區(qū)后，則認(rèn)為它是靜止的狀態(tài)。當(dāng)所有的CPU都至少經(jīng)歷過(guò)一次QS后，寬限期將結(jié)束并觸發(fā)回收工作。
在時(shí)鐘tick中檢測(cè)CPU處于
用戶模式或者idle模式，則表明CPU離開(kāi)了臨界區(qū)；在不支持搶占的RCU實(shí)現(xiàn)中，檢測(cè)到CPU有context切換，就能表明CPU離開(kāi)了臨界區(qū)；
3. 數(shù)據(jù)結(jié)構(gòu)
RCU實(shí)際是一個(gè)大型的狀態(tài)機(jī)，它的數(shù)據(jù)結(jié)構(gòu)維護(hù)著狀態(tài)，可以讓RCU讀者快速執(zhí)行，同時(shí)也可以高效和靈活的處理RCU寫(xiě)者請(qǐng)求的寬限期。
RCU的性能和可擴(kuò)展性依賴于采用什么機(jī)制來(lái)探測(cè)寬限期的結(jié)束；
RCU使用位圖
cpumask去記錄CPU經(jīng)歷靜止?fàn)顟B(tài)，在經(jīng)典RCU(Classic RCU)實(shí)現(xiàn)中，由于使用了全局的cpumask位圖，當(dāng)CPU數(shù)量很大時(shí)鎖爭(zhēng)用會(huì)帶來(lái)很大開(kāi)銷(xiāo)（GP開(kāi)始時(shí)設(shè)置對(duì)應(yīng)位，GP結(jié)束時(shí)清除對(duì)應(yīng)位），因此也促成了Tree RCU的誕生；Tree RCU以樹(shù)形分層來(lái)組織CPU，將CPU分組，本小組的CPU爭(zhēng)用同一個(gè)鎖，當(dāng)本小組的某個(gè)CPU經(jīng)歷了一個(gè)靜止?fàn)顟B(tài)QS后，將其對(duì)應(yīng)的位從位圖清除，如果該小組最后一個(gè)CPU經(jīng)歷完靜止?fàn)顟B(tài)QS后，表明該小組全部經(jīng)歷了CPU的QS狀態(tài)，那么將上一層對(duì)應(yīng)該組的位從位圖清除；RCU有幾個(gè)關(guān)鍵的數(shù)據(jù)結(jié)構(gòu)：
struct rcu_state，struct rcu_node，struct rcu_data；
圖來(lái)了：
struct rcu_state：用于描述RCU的全局狀態(tài)，它負(fù)責(zé)組織樹(shù)狀層級(jí)結(jié)構(gòu)，系統(tǒng)中支持不同類(lèi)型的RCU狀態(tài)：rcu_sched_state，?rcu_bh_state，rcu_preempt_state；struct rcu_node：Tree RCU中的組織節(jié)點(diǎn)；struct rcu_data：用于描述處理器的RCU狀態(tài)，每個(gè)CPU都維護(hù)一個(gè)數(shù)據(jù)，它歸屬于某一個(gè)struct rcu_node，struct rcu_data檢測(cè)靜止?fàn)顟B(tài)并進(jìn)行處理，對(duì)應(yīng)的CPU進(jìn)行RCU回調(diào)，__percpu的定義也減少了同步的開(kāi)銷(xiāo)；
看到這種描述，如果還是在懵逼的狀態(tài)，那么再來(lái)一張拓?fù)鋱D，讓真相更白一點(diǎn)：
層狀樹(shù)形結(jié)構(gòu)由
struct rcu_node來(lái)組成，這些節(jié)點(diǎn)在struct rcu_state結(jié)構(gòu)中是放置在數(shù)組中的，由于struct rcu_node結(jié)構(gòu)有父節(jié)點(diǎn)指針，因此可以構(gòu)造樹(shù)形；CPU分組后，對(duì)鎖的爭(zhēng)用就會(huì)大大減少，比如
CPU0/CPU1就不需要和CPU6/CPU7去爭(zhēng)用鎖了，逐級(jí)以淘汰賽的形式向上；
關(guān)鍵點(diǎn)來(lái)了：Tree RCU使用rcu_node節(jié)點(diǎn)來(lái)構(gòu)造層級(jí)結(jié)構(gòu)，進(jìn)而管理靜止?fàn)顟B(tài)Quiescent State和寬限期Grace Period，靜止?fàn)顟B(tài)信息QS是從每個(gè)CPU的rcu_data往上傳遞到根節(jié)點(diǎn)的，而寬限期GP信息是通過(guò)根節(jié)點(diǎn)從上往下傳遞的，當(dāng)每個(gè)CPU經(jīng)歷過(guò)一次QS狀態(tài)后，寬限期結(jié)束
關(guān)鍵字段還是有必要介紹一下的，否則豈不是耍流氓？
4. RCU更新接口
從深入剖析Linux RCU原理（一）初窺門(mén)徑的示例中，我們看到了RCU的寫(xiě)端調(diào)用了synchronize_rcu/call_rcu兩種類(lèi)型的接口，事實(shí)上Linux內(nèi)核提供了三種不同類(lèi)型的RCU，因此也對(duì)應(yīng)了相應(yīng)形式的接口。
來(lái)張圖：
RCU寫(xiě)者，可以通過(guò)兩種方式來(lái)等待寬限期的結(jié)束，一種是調(diào)用同步接口等待寬限期結(jié)束，一種是異步接口等待寬限期結(jié)束后再進(jìn)行回調(diào)處理，分別如上圖的左右兩側(cè)所示；從圖中的接口調(diào)用來(lái)看，同步接口中實(shí)際會(huì)去調(diào)用異步接口，只是同步接口中增加了一個(gè)
wait_for_completion睡眠等待操作，并且會(huì)將wakeme_after_rcu回調(diào)函數(shù)傳遞給異步接口，當(dāng)寬限期結(jié)束后，在異步接口中回調(diào)了wakeme_after_rcu進(jìn)行喚醒處理；目前內(nèi)核中提供了三種RCU：
可搶占RCU：
rcu_read_lock/rcu_read_unlock來(lái)界定區(qū)域，在讀端臨界區(qū)可以被其他進(jìn)程搶占；不可搶占RCU
(RCU-sched)：rcu_read_lock_sched/rcu_read_unlock_sched來(lái)界定區(qū)域，在讀端臨界區(qū)不允許其他進(jìn)程搶占；關(guān)下半部RCU
(RCU-bh)：rcu_read_lock_bh/rcu_read_unlock_bh來(lái)界定區(qū)域，在讀端臨界區(qū)禁止軟中斷；從圖中可以看出來(lái)，不管是同步還是異步接口，最終都是調(diào)到
__call_rcu接口，它是接口實(shí)現(xiàn)的關(guān)鍵，所以接下來(lái)分析下這個(gè)函數(shù)了；
5.?__call_rcu
函數(shù)的調(diào)用流程如下：
__call_rcu函數(shù)，第一個(gè)功能是注冊(cè)回調(diào)函數(shù)，而回調(diào)的函數(shù)的維護(hù)是在rcu_data結(jié)構(gòu)中的struct rcu_segcblist cblist字段中；rcu_accelerate_cbs/rcu_advance_cbs，實(shí)現(xiàn)中都是通過(guò)操作struct rcu_segcblist結(jié)構(gòu)，來(lái)完成回調(diào)函數(shù)的移動(dòng)處理等；__call_rcu函數(shù)第二個(gè)功能是判斷是否需要開(kāi)啟新的寬限期GP；
鏈表的維護(hù)關(guān)系如下圖所示：
實(shí)際的設(shè)計(jì)比較巧妙，通過(guò)一個(gè)鏈表來(lái)鏈接所有的回調(diào)函數(shù)節(jié)點(diǎn)，同時(shí)維護(hù)一個(gè)二級(jí)指針數(shù)組，用于將該鏈表進(jìn)行分段，分別維護(hù)不同階段的回調(diào)函數(shù)，回調(diào)函數(shù)的移動(dòng)方向如圖所示，關(guān)于回調(diào)函數(shù)節(jié)點(diǎn)的處理都圍繞著這個(gè)圖來(lái)展開(kāi)；
那么通過(guò)__call_rcu注冊(cè)的這些回調(diào)函數(shù)在哪里調(diào)用呢？答案是在RCU_SOFTIRQ軟中斷中：
當(dāng)
invoke_rcu_core時(shí)，在該函數(shù)中調(diào)用raise_softirq接口，從而觸發(fā)軟中斷回調(diào)函數(shù)rcu_process_callbacks的執(zhí)行；涉及到與寬限期GP相關(guān)的操作，在
rcu_process_callbacks中會(huì)調(diào)用rcu_gp_kthread_wake喚醒內(nèi)核線程，最終會(huì)在rcu_gp_kthread線程中執(zhí)行；涉及到RCU注冊(cè)的回調(diào)函數(shù)執(zhí)行的操作，都在
rcu_do_batch函數(shù)中執(zhí)行，其中有兩種執(zhí)行方式：1）如果不支持優(yōu)先級(jí)繼承的話，直接調(diào)用即可；2）支持優(yōu)先級(jí)繼承，在把回調(diào)的工作放置在rcu_cpu_kthread內(nèi)核線程中，其中內(nèi)核為每個(gè)CPU都創(chuàng)建了一個(gè)rcu_cpu_kthread內(nèi)核線程；
6. 寬限期開(kāi)始與結(jié)束
既然涉及到寬限期GP的操作，都放到了rcu_gp_kthread內(nèi)核線程中了，那么來(lái)看看這個(gè)內(nèi)核線程的邏輯操作吧：
內(nèi)核分別為
rcu_preempt_state, rcu_bh_state, rcu_sched_state創(chuàng)建了內(nèi)核線程rcu_gp_kthread；rcu_gp_kthread內(nèi)核線程主要完成三個(gè)工作：1）創(chuàng)建新的寬限期GP；2）等待強(qiáng)制靜止?fàn)顟B(tài)，設(shè)置超時(shí)，提前喚醒說(shuō)明所有處理器經(jīng)過(guò)了靜止?fàn)顟B(tài)；3）寬限期結(jié)束處理。其中，前邊兩個(gè)操作都是通過(guò)睡眠等待在某個(gè)條件上。
7. 靜止?fàn)顟B(tài)檢測(cè)及報(bào)告
很顯然，對(duì)這種狀態(tài)的檢測(cè)通常都是周期性的進(jìn)行，放置在時(shí)鐘中斷處理中就是情理之中了：
rcu_sched/rcu_bh類(lèi)型的RCU中，當(dāng)檢測(cè)CPU處于用戶模式或處于idle線程中，說(shuō)明當(dāng)前CPU已經(jīng)離開(kāi)了臨界區(qū)，經(jīng)歷了一個(gè)QS靜止?fàn)顟B(tài)，對(duì)于rcu_bh的RCU，如果沒(méi)有出去softirq上下文中，也表明CPU經(jīng)歷了QS靜止?fàn)顟B(tài)；在
rcu_pending滿足條件的情況下，觸發(fā)軟中斷的執(zhí)行，rcu_process_callbacks將會(huì)被調(diào)用；在
rcu_process_callbacks回調(diào)函數(shù)中，對(duì)寬限期進(jìn)行判斷，并對(duì)靜止?fàn)顟B(tài)逐級(jí)上報(bào)，如果整個(gè)樹(shù)狀結(jié)構(gòu)都經(jīng)歷了靜止?fàn)顟B(tài)，那就表明了寬限期的結(jié)束，從而喚醒內(nèi)核線程去處理；順便提一句，在
rcu_pending函數(shù)中，rcu_pending->__rcu_pending->check_cpu_stall->print_cpu_stall的流程中，會(huì)去判斷是否有CPU stall的問(wèn)題，這個(gè)在內(nèi)核中有文檔專(zhuān)門(mén)來(lái)描述，不再分析了；
8. 狀態(tài)機(jī)變換
如果要觀察整個(gè)狀態(tài)機(jī)的變化，跟蹤一下trace_rcu_grace_period接口的記錄就能發(fā)現(xiàn)：
大體流程如下：
9. 總結(jié)
本文提綱挈領(lǐng)的捋了一下RCU的大體流程，主要涉及到RCU狀態(tài)機(jī)的輪轉(zhuǎn)，從開(kāi)啟寬限期GP，到寬限期GP的初始化、靜止?fàn)顟B(tài)QS的檢測(cè)、寬限期結(jié)束、回調(diào)函數(shù)的調(diào)用等，而這部分主要涉及到軟中斷
RCU_SOFTIRQ和內(nèi)核線程rcu_gp_kthread的動(dòng)態(tài)運(yùn)行及交互等；內(nèi)部的狀態(tài)組織是通過(guò)
rcu_state, rcu_node, rcu_data組織成樹(shù)狀結(jié)構(gòu)來(lái)維護(hù)，此外回調(diào)函數(shù)是通過(guò)rcu_data中的分段鏈表來(lái)批處理，至于這些結(jié)構(gòu)中相關(guān)字段的處理（比如gpnum, completed字段的設(shè)置來(lái)判斷寬限期階段等），以及鏈表的節(jié)點(diǎn)移動(dòng)等，都沒(méi)有進(jìn)一步去分析跟進(jìn)了；RCU的實(shí)現(xiàn)機(jī)制很復(fù)雜，很多其他內(nèi)容都還未涉及到，比如SRCU（可睡眠RCU）、可搶占RCU，中斷/NMI對(duì)RCU的處理等，只能說(shuō)是蜻蜓點(diǎn)水了；
在閱讀代碼過(guò)程中，經(jīng)常會(huì)發(fā)現(xiàn)一些巧妙的設(shè)計(jì)，有時(shí)會(huì)有頓悟的感覺(jué)，這也是其中的樂(lè)趣之一了；
原文作者：LoyenWang
