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

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

背景

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

說明：

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

1. 概述

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

2. 基礎(chǔ)概念

2.1?Grace Period

• 中間的黃色部分代表的就是Grace Period，中文叫做寬限期，從Removal到Reclamation，中間就隔了一個寬限期；
• 只有當(dāng)寬限期結(jié)束后，才會觸發(fā)回收的工作，寬限期的結(jié)束代表著Reader都已經(jīng)退出了臨界區(qū)，因此回收工作也就是安全的操作了；
• 寬限期是否結(jié)束，與處理器的執(zhí)行狀態(tài)檢測有關(guān)，也就是檢測靜止?fàn)顟B(tài)Quiescent Status；
• RCU的性能與可擴展性依賴于它是否能有效的檢測出靜止?fàn)顟B(tài)(Quiescent Status)，并且判斷寬限期是否結(jié)束。

來一張圖：

2.2?Quiescent Status

Quiescent Status，用于描述處理器的執(zhí)行狀態(tài)。當(dāng)某個CPU正在訪問RCU保護的臨界區(qū)時，認(rèn)為是活動的狀態(tài)，而當(dāng)它離開了臨界區(qū)后，則認(rèn)為它是靜止的狀態(tài)。當(dāng)所有的CPU都至少經(jīng)歷過一次QS后，寬限期將結(jié)束并觸發(fā)回收工作。

• 在時鐘tick中檢測CPU處于用戶模式或者idle模式，則表明CPU離開了臨界區(qū)；
• 在不支持搶占的RCU實現(xiàn)中，檢測到CPU有context切換，就能表明CPU離開了臨界區(qū)；

3. 數(shù)據(jù)結(jié)構(gòu)

• RCU實際是一個大型的狀態(tài)機，它的數(shù)據(jù)結(jié)構(gòu)維護著狀態(tài)，可以讓RCU讀者快速執(zhí)行，同時也可以高效和靈活的處理RCU寫者請求的寬限期。
• RCU的性能和可擴展性依賴于采用什么機制來探測寬限期的結(jié)束；
• RCU使用位圖cpumask去記錄CPU經(jīng)歷靜止?fàn)顟B(tài)，在經(jīng)典RCU(Classic RCU)實現(xiàn)中，由于使用了全局的cpumask位圖，當(dāng)CPU數(shù)量很大時鎖爭用會帶來很大開銷（GP開始時設(shè)置對應(yīng)位，GP結(jié)束時清除對應(yīng)位），因此也促成了Tree RCU的誕生；
• Tree RCU以樹形分層來組織CPU，將CPU分組，本小組的CPU爭用同一個鎖，當(dāng)本小組的某個CPU經(jīng)歷了一個靜止?fàn)顟B(tài)QS后，將其對應(yīng)的位從位圖清除，如果該小組最后一個CPU經(jīng)歷完靜止?fàn)顟B(tài)QS后，表明該小組全部經(jīng)歷了CPU的QS狀態(tài)，那么將上一層對應(yīng)該組的位從位圖清除；
• RCU有幾個關(guān)鍵的數(shù)據(jù)結(jié)構(gòu)：struct rcu_state，struct rcu_node，struct rcu_data；

圖來了：

• struct rcu_state：用于描述RCU的全局狀態(tài)，它負(fù)責(zé)組織樹狀層級結(jié)構(gòu)，系統(tǒng)中支持不同類型的RCU狀態(tài)：rcu_sched_state，?rcu_bh_state，rcu_preempt_state；
• struct rcu_node：Tree RCU中的組織節(jié)點；
• struct rcu_data：用于描述處理器的RCU狀態(tài)，每個CPU都維護一個數(shù)據(jù)，它歸屬于某一個struct rcu_node，struct rcu_data檢測靜止?fàn)顟B(tài)并進行處理，對應(yīng)的CPU進行RCU回調(diào)，__percpu的定義也減少了同步的開銷；

看到這種描述，如果還是在懵逼的狀態(tài)，那么再來一張拓?fù)鋱D，讓真相更白一點：

• 層狀樹形結(jié)構(gòu)由struct rcu_node來組成，這些節(jié)點在struct rcu_state結(jié)構(gòu)中是放置在數(shù)組中的，由于struct rcu_node結(jié)構(gòu)有父節(jié)點指針，因此可以構(gòu)造樹形；
• CPU分組后，對鎖的爭用就會大大減少，比如CPU0/CPU1就不需要和CPU6/CPU7去爭用鎖了，逐級以淘汰賽的形式向上；

關(guān)鍵點來了：Tree RCU使用rcu_node節(jié)點來構(gòu)造層級結(jié)構(gòu)，進而管理靜止?fàn)顟B(tài)Quiescent State和寬限期Grace Period，靜止?fàn)顟B(tài)信息QS是從每個CPU的rcu_data往上傳遞到根節(jié)點的，而寬限期GP信息是通過根節(jié)點從上往下傳遞的，當(dāng)每個CPU經(jīng)歷過一次QS狀態(tài)后，寬限期結(jié)束

關(guān)鍵字段還是有必要介紹一下的，否則豈不是耍流氓？

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

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

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


4. RCU更新接口

我們看到了RCU的寫端調(diào)用了synchronize_rcu/call_rcu兩種類型的接口，事實上Linux內(nèi)核提供了三種不同類型的RCU，因此也對應(yīng)了相應(yīng)形式的接口。來張圖：

• RCU寫者，可以通過兩種方式來等待寬限期的結(jié)束，一種是調(diào)用同步接口等待寬限期結(jié)束，一種是異步接口等待寬限期結(jié)束后再進行回調(diào)處理，分別如上圖的左右兩側(cè)所示；

• 從圖中的接口調(diào)用來看，同步接口中實際會去調(diào)用異步接口，只是同步接口中增加了一個wait_for_completion睡眠等待操作，并且會將wakeme_after_rcu回調(diào)函數(shù)傳遞給異步接口，當(dāng)寬限期結(jié)束后，在異步接口中回調(diào)了wakeme_after_rcu進行喚醒處理；

• 目前內(nèi)核中提供了三種RCU：

1. 可搶占RCU：rcu_read_lock/rcu_read_unlock來界定區(qū)域，在讀端臨界區(qū)可以被其他進程搶占；
2. 不可搶占RCU(RCU-sched)：rcu_read_lock_sched/rcu_read_unlock_sched來界定區(qū)域，在讀端臨界區(qū)不允許其他進程搶占；
3. 關(guān)下半部RCU(RCU-bh)：rcu_read_lock_bh/rcu_read_unlock_bh來界定區(qū)域，在讀端臨界區(qū)禁止軟中斷；
• 從圖中可以看出來，不管是同步還是異步接口，最終都是調(diào)到__call_rcu接口，它是接口實現(xiàn)的關(guān)鍵，所以接下來分析下這個函數(shù)了；

5.?__call_rcu

函數(shù)的調(diào)用流程如下：

• __call_rcu函數(shù)，第一個功能是注冊回調(diào)函數(shù)，而回調(diào)的函數(shù)的維護是在rcu_data結(jié)構(gòu)中的struct rcu_segcblist cblist字段中；
• rcu_accelerate_cbs/rcu_advance_cbs，實現(xiàn)中都是通過操作struct rcu_segcblist結(jié)構(gòu)，來完成回調(diào)函數(shù)的移動處理等；
• __call_rcu函數(shù)第二個功能是判斷是否需要開啟新的寬限期GP；

鏈表的維護關(guān)系如下圖所示：

• 實際的設(shè)計比較巧妙，通過一個鏈表來鏈接所有的回調(diào)函數(shù)節(jié)點，同時維護一個二級指針數(shù)組，用于將該鏈表進行分段，分別維護不同階段的回調(diào)函數(shù)，回調(diào)函數(shù)的移動方向如圖所示，關(guān)于回調(diào)函數(shù)節(jié)點的處理都圍繞著這個圖來展開；

那么通過__call_rcu注冊的這些回調(diào)函數(shù)在哪里調(diào)用呢？答案是在RCU_SOFTIRQ軟中斷中：

• 當(dāng)invoke_rcu_core時，在該函數(shù)中調(diào)用raise_softirq接口，從而觸發(fā)軟中斷回調(diào)函數(shù)rcu_process_callbacks的執(zhí)行；
• 涉及到與寬限期GP相關(guān)的操作，在rcu_process_callbacks中會調(diào)用rcu_gp_kthread_wake喚醒內(nèi)核線程，最終會在rcu_gp_kthread線程中執(zhí)行；
• 涉及到RCU注冊的回調(diào)函數(shù)執(zhí)行的操作，都在rcu_do_batch函數(shù)中執(zhí)行，其中有兩種執(zhí)行方式：1）如果不支持優(yōu)先級繼承的話，直接調(diào)用即可；2）支持優(yōu)先級繼承，在把回調(diào)的工作放置在rcu_cpu_kthread內(nèi)核線程中，其中內(nèi)核為每個CPU都創(chuàng)建了一個rcu_cpu_kthread內(nèi)核線程；

6. 寬限期開始與結(jié)束

既然涉及到寬限期GP的操作，都放到了rcu_gp_kthread內(nèi)核線程中了，那么來看看這個內(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)核線程主要完成三個工作：1）創(chuàng)建新的寬限期GP；2）等待強制靜止?fàn)顟B(tài)，設(shè)置超時，提前喚醒說明所有處理器經(jīng)過了靜止?fàn)顟B(tài)；3）寬限期結(jié)束處理。其中，前邊兩個操作都是通過睡眠等待在某個條件上。

7. 靜止?fàn)顟B(tài)檢測及報告

很顯然，對這種狀態(tài)的檢測通常都是周期性的進行，放置在時鐘中斷處理中就是情理之中了：

• rcu_sched/rcu_bh類型的RCU中，當(dāng)檢測CPU處于用戶模式或處于idle線程中，說明當(dāng)前CPU已經(jīng)離開了臨界區(qū)，經(jīng)歷了一個QS靜止?fàn)顟B(tài)，對于rcu_bh的RCU，如果沒有出去softirq上下文中，也表明CPU經(jīng)歷了QS靜止?fàn)顟B(tài)；
• 在rcu_pending滿足條件的情況下，觸發(fā)軟中斷的執(zhí)行，rcu_process_callbacks將會被調(diào)用；
• 在rcu_process_callbacks回調(diào)函數(shù)中，對寬限期進行判斷，并對靜止?fàn)顟B(tài)逐級上報，如果整個樹狀結(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的流程中，會去判斷是否有CPU stall的問題，這個在內(nèi)核中有文檔專門來描述，不再分析了；

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

如果要觀察整個狀態(tài)機的變化，跟蹤一下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)機的輪轉(zhuǎn)，從開啟寬限期GP，到寬限期GP的初始化、靜止?fàn)顟B(tài)QS的檢測、寬限期結(jié)束、回調(diào)函數(shù)的調(diào)用等，而這部分主要涉及到軟中斷RCU_SOFTIRQ和內(nèi)核線程rcu_gp_kthread的動態(tài)運行及交互等；
• 內(nèi)部的狀態(tài)組織是通過rcu_state, rcu_node, rcu_data組織成樹狀結(jié)構(gòu)來維護，此外回調(diào)函數(shù)是通過rcu_data中的分段鏈表來批處理，至于這些結(jié)構(gòu)中相關(guān)字段的處理（比如gpnum, completed字段的設(shè)置來判斷寬限期階段等），以及鏈表的節(jié)點移動等，都沒有進一步去分析跟進了；
• RCU的實現(xiàn)機制很復(fù)雜，很多其他內(nèi)容都還未涉及到，比如SRCU（可睡眠RCU）、可搶占RCU，中斷/NMI對RCU的處理等，只能說是蜻蜓點水了；
• 在閱讀代碼過程中，經(jīng)常會發(fā)現(xiàn)一些巧妙的設(shè)計，有時會有頓悟的感覺，這也是其中的樂趣之一了；

參考

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 -