hi, 上次分析了RCU核心思想：深入理解 RCU 核心原理，后面說(shuō)會(huì)分享一篇RCU的源碼剖析，其實(shí)我這邊已經(jīng)總結(jié)得差不多：

但自己思考了一下，發(fā)現(xiàn)大部分都是代碼分析，這樣很多人其實(shí)并不喜歡看源代碼分析(代碼有點(diǎn)多），所以可能其他方式更好，比如圖解，我發(fā)現(xiàn)已經(jīng)有人搞了這個(gè)，而且質(zhì)量也挺高的，打算分享給大家。

背景

• Read the fucking source code!??--By 魯迅
• A picture is worth a thousand words.?--By 高爾基

說(shuō)明：

1. Kernel版本：4.14
2. ARM64處理器，Contex-A53，雙核
3. 使用工具：Source Insight 3.5， Visio

1. 概述

我會(huì)假設(shè)你已經(jīng)看過(guò)了?深入理解RCU|核心原理
本文將進(jìn)一步去探索下RCU背后的機(jī)制。

2. 基礎(chǔ)概念

2.1?Grace Period

• 中間的黃色部分代表的就是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)一張圖：

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)銷（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)中支持不同類型的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)銷；

看到這種描述，如果還是在懵逼的狀態(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)鍵字段還是有必要介紹一下的，否則豈不是耍流氓？

struct?rcu_state?{
?struct?rcu_node?node[NUM_RCU_NODES];????????//?rcu_node節(jié)點(diǎn)數(shù)組，組織成層級(jí)樹(shù)狀
?struct?rcu_node?*level[RCU_NUM_LVLS? ?1];???//指向每層的首個(gè)rcu_node節(jié)點(diǎn)，數(shù)組加1是為了消除編譯告警
?struct?rcu_data?__percpu?*rda;??????????????????//指向每個(gè)CPU的rcu_data實(shí)例
?call_rcu_func_t?call;???????????????????????????//指向特定RCU類型的call_rcu函數(shù)：call_rcu_sched, call_rcu_bh等
?int?ncpus;????????????????????????????????????//?處理器數(shù)量
????
????unsigned?long?gpnum;???????????????????//當(dāng)前寬限期編號(hào)，gpnum?>?completed，表明正處在寬限期內(nèi)
?unsigned?long?completed;??????????????????//上一個(gè)結(jié)束的寬限期編號(hào)，如果與gpnum相等，表明RCU空閑?
????...
????????unsigned?long?gp_max;???????????????????????????????????//最長(zhǎng)的寬限期時(shí)間，jiffies????????
????...
}

/*
?*?Definition?for?node?within?the?RCU?grace-period-detection?hierarchy.
?*/
struct?rcu_node?{
?????raw_spinlock_t?__private?lock;?????????//保護(hù)本節(jié)點(diǎn)的自旋鎖
??????unsigned?long?gpnum;???????????//本節(jié)點(diǎn)寬限期編號(hào)，等于或小于根節(jié)點(diǎn)的gpnum
????????unsigned?long?completed;??????????//本節(jié)點(diǎn)上一個(gè)結(jié)束的寬限期編號(hào)，等于或小于根節(jié)點(diǎn)的completed
????????unsigned?long?qsmask;???????????????????????//QS狀態(tài)位圖，某位為1，代表對(duì)應(yīng)的成員沒(méi)有經(jīng)歷QS狀態(tài)
????????unsigned?long?qsmaskinit;????????????????//正常寬限期開(kāi)始時(shí)，QS狀態(tài)的初始值
????...????
?int?grplo;??//該分組的CPU最小編號(hào)
?int?grphi;??//該分組的CPU最大編號(hào)
?u8?grpnum;??//該分組在上一層分組里的編號(hào)
?u8?level;??//在樹(shù)中的層級(jí)，Root為0
????...
????
????????struct?rcu_node?*parent;?//指向父節(jié)點(diǎn)
}

/*?Per-CPU?data?for?read-copy?update.?*/
struct?rcu_data?{
?unsigned?long?completed;?????//本CPU看到的已結(jié)束的寬限期編號(hào)
?unsigned?long?gpnum;??????//本CPU看到的最高寬限期編號(hào)
?union?rcu_noqs?cpu_no_qs;???????//記錄本CPU是否經(jīng)歷QS狀態(tài)
?bool?core_need_qs;??????????//RCU需要本CPU上報(bào)QS狀態(tài)
?unsigned?long?grpmask;??//本CPU在分組的位圖中的掩碼
?struct?rcu_segcblist;??????????//回調(diào)函數(shù)鏈表，用于存放call_rcu注冊(cè)的延后執(zhí)行的回調(diào)函數(shù)
????...
}


4. RCU更新接口

我們看到了RCU的寫(xiě)端調(diào)用了synchronize_rcu/call_rcu兩種類型的接口，事實(shí)上Linux內(nè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：

1. 可搶占RCU：rcu_read_lock/rcu_read_unlock來(lái)界定區(qū)域，在讀端臨界區(qū)可以被其他進(jìn)程搶占；
2. 不可搶占RCU(RCU-sched)：rcu_read_lock_sched/rcu_read_unlock_sched來(lái)界定區(qū)域，在讀端臨界區(qū)不允許其他進(jìn)程搶占；
3. 關(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類型的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)核中有文檔專門(mén)來(lái)描述，不再分析了；

8. 狀態(tài)機(jī)變換

如果要觀察整個(gè)狀態(tài)機(jī)的變化，跟蹤一下trace_rcu_grace_period接口的記錄就能發(fā)現(xiàn)：

/*
?*?Tracepoint?for?grace-period?events.??Takes?a?string?identifying?the
?*?RCU?flavor,?the?grace-period?number,?and?a?string?identifying?the
?*?grace-period-related?event?as?follows:
?*
?*?"AccReadyCB":?CPU?acclerates?new?callbacks?to?RCU_NEXT_READY_TAIL.
?*?"AccWaitCB":?CPU?accelerates?new?callbacks?to?RCU_WAIT_TAIL.
?*?"newreq":?Request?a?new?grace?period.
?*?"start":?Start?a?grace?period.
?*?"cpustart":?CPU?first?notices?a?grace-period?start.
?*?"cpuqs":?CPU?passes?through?a?quiescent?state.
?*?"cpuonl":?CPU?comes?online.
?*?"cpuofl":?CPU?goes?offline.
?*?"reqwait":?GP?kthread?sleeps?waiting?for?grace-period?request.
?*?"reqwaitsig":?GP?kthread?awakened?by?signal?from?reqwait?state.
?*?"fqswait":?GP?kthread?waiting?until?time?to?force?quiescent?states.
?*?"fqsstart":?GP?kthread?starts?forcing?quiescent?states.
?*?"fqsend":?GP?kthread?done?forcing?quiescent?states.
?*?"fqswaitsig":?GP?kthread?awakened?by?signal?from?fqswait?state.
?*?"end":?End?a?grace?period.
?*?"cpuend":?CPU?first?notices?a?grace-period?end.
?*/
大體流程如下：

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è)趣之一了；

參考

Verification of the Tree-Based Hierarchical Read-Copy Update in the Linux Kernel

Documentation/RCU

What is RCU, Fundamentally?

What is RCU? Part 2: Usage

RCU part 3: the RCU API

Introduction to RCU

- EOF -