背景 By 魯迅 By 高爾基說明： 1. Kernel版本：4.14 2. ARM64處理器，Contex A53，雙核 3. 使用工具：Source Insight 3.5， Visio 1. 概述我會假設你已經看過了 "《Linux RCU原理剖析（一）初窺門徑》" 本文將進一步去探索下 ...

背景

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

說明：

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

1. 概述

我會假設你已經看過了《Linux RCU原理剖析（一）-初窺門徑》

本文將進一步去探索下RCU背後的機制。

2. 基礎概念

2.1 `Grace Period`

繼續貼出《Linux RCU原理剖析（一）-初窺門徑》中的圖片：

中間的黃色部分代表的就是Grace Period，中文叫做寬限期，從Removal到Reclamation，中間就隔了一個寬限期；
只有當寬限期結束後，才會觸發回收的工作，寬限期的結束代表著Reader都已經退出了臨界區，因此回收工作也就是安全的操作了；
寬限期是否結束，與處理器的執行狀態檢測有關，也就是檢測靜止狀態Quiescent Status；
RCU的性能與可擴展性依賴於它是否能有效的檢測出靜止狀態(Quiescent Status)，並且判斷寬限期是否結束。

來一張圖：

2.2 `Quiescent Status`

Quiescent Status，用於描述處理器的執行狀態。當某個CPU正在訪問RCU保護的臨界區時，認為是活動的狀態，而當它離開了臨界區後，則認為它是靜止的狀態。當所有的CPU都至少經歷過一次QS後，寬限期將結束並觸發回收工作。

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

3. 數據結構

RCU實際是一個大型的狀態機，它的數據結構維護著狀態，可以讓RCU讀者快速執行，同時也可以高效和靈活的處理RCU寫者請求的寬限期。
RCU的性能和可擴展性依賴於採用什麼機制來探測寬限期的結束；
RCU使用點陣圖cpumask去記錄CPU經歷靜止狀態，在經典RCU(Classic RCU)實現中，由於使用了全局的cpumask點陣圖，當CPU數量很大時鎖爭用會帶來很大開銷（GP開始時設置對應位，GP結束時清除對應位），因此也促成了Tree RCU的誕生；
Tree RCU以樹形分層來組織CPU，將CPU分組，本小組的CPU爭用同一個鎖，當本小組的某個CPU經歷了一個靜止狀態QS後，將其對應的位從點陣圖清除，如果該小組最後一個CPU經歷完靜止狀態QS後，表明該小組全部經歷了CPU的QS狀態，那麼將上一層對應該組的位從點陣圖清除；
RCU有幾個關鍵的數據結構：struct rcu_state，struct rcu_node，struct rcu_data；

圖來了：

struct rcu_state：用於描述RCU的全局狀態，它負責組織樹狀層級結構，系統中支持不同類型的RCU狀態：rcu_sched_state， rcu_bh_state，rcu_preempt_state；
struct rcu_node：Tree RCU中的組織節點；
struct rcu_data：用於描述處理器的RCU狀態，每個CPU都維護一個數據，它歸屬於某一個struct rcu_node，struct rcu_data檢測靜止狀態併進行處理，對應的CPU進行RCU回調，__percpu的定義也減少了同步的開銷；

看到這種描述，如果還是在懵逼的狀態，那麼再來一張拓撲圖，讓真相更白一點：

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

關鍵點來了：Tree RCU使用rcu_node節點來構造層級結構，進而管理靜止狀態Quiescent State和寬限期Grace Period，靜止狀態信息QS是從每個CPU的rcu_data往上傳遞到根節點的，而寬限期GP信息是通過根節點從上往下傳遞的，當每個CPU經歷過一次QS狀態後，寬限期結束

關鍵欄位還是有必要介紹一下的，否則豈不是耍流氓？

struct rcu_state {
	struct rcu_node node[NUM_RCU_NODES];        // rcu_node節點數組，組織成層級樹狀
	struct rcu_node *level[RCU_NUM_LVLS + 1];   //指向每層的首個rcu_node節點，數組加1是為了消除編譯告警
	struct rcu_data __percpu *rda;		                //指向每個CPU的rcu_data實例
	call_rcu_func_t call;			                        //指向特定RCU類型的call_rcu函數：call_rcu_sched, call_rcu_bh等
	int ncpus;				                                // 處理器數量
    
   	unsigned long gpnum;			                //當前寬限期編號，gpnum > completed，表明正處在寬限期內
	unsigned long completed;		                //上一個結束的寬限期編號，如果與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;	        //保護本節點的自旋鎖
     	unsigned long gpnum;			        //本節點寬限期編號，等於或小於根節點的gpnum
        unsigned long completed;		        //本節點上一個結束的寬限期編號，等於或小於根節點的completed
        unsigned long qsmask;                       //QS狀態點陣圖，某位為1，代表對應的成員沒有經歷QS狀態
        unsigned long qsmaskinit;                //正常寬限期開始時，QS狀態的初始值
    ...    
	int	grplo;		//該分組的CPU最小編號
	int	grphi;		//該分組的CPU最大編號
	u8	grpnum;		//該分組在上一層分組裡的編號
	u8	level;		//在樹中的層級，Root為0
    ...
    
        struct rcu_node *parent; //指向父節點
}

/* Per-CPU data for read-copy update. */
struct rcu_data {
	unsigned long	completed;	    //本CPU看到的已結束的寬限期編號
	unsigned long	gpnum;		    //本CPU看到的最高寬限期編號
	union rcu_noqs cpu_no_qs;       //記錄本CPU是否經歷QS狀態
	bool core_need_qs;		        //RCU需要本CPU上報QS狀態
	unsigned long grpmask;		//本CPU在分組的點陣圖中的掩碼
	struct rcu_segcblist;		        //回調函數鏈表，用於存放call_rcu註冊的延後執行的回調函數
    ...
}

4. RCU更新介面

從《Linux RCU原理剖析（一）-初窺門徑》的示例中，我們看到了RCU的寫端調用了synchronize_rcu/call_rcu兩種類型的介面，事實上Linux內核提供了三種不同類型的RCU，因此也對應了相應形式的介面。

來張圖：

RCU寫者，可以通過兩種方式來等待寬限期的結束，一種是調用同步介面等待寬限期結束，一種是非同步介面等待寬限期結束後再進行回調處理，分別如上圖的左右兩側所示；
從圖中的介面調用來看，同步介面中實際會去調用非同步介面，只是同步介面中增加了一個wait_for_completion睡眠等待操作，並且會將wakeme_after_rcu回調函數傳遞給非同步介面，當寬限期結束後，在非同步介面中回調了wakeme_after_rcu進行喚醒處理；
目前內核中提供了三種RCU：
1. 可搶占RCU：rcu_read_lock/rcu_read_unlock來界定區域，在讀端臨界區可以被其他進程搶占；
2. 不可搶占RCU(RCU-sched)：rcu_read_lock_sched/rcu_read_unlock_sched來界定區域，在讀端臨界區不允許其他進程搶占；
3. 關下半部RCU(RCU-bh)：rcu_read_lock_bh/rcu_read_unlock_bh來界定區域，在讀端臨界區禁止軟中斷；
從圖中可以看出來，不管是同步還是非同步介面，最終都是調到__call_rcu介面，它是介面實現的關鍵，所以接下來分析下這個函數了；

5. `__call_rcu`

函數的調用流程如下：

__call_rcu函數，第一個功能是註冊回調函數，而回調的函數的維護是在rcu_data結構中的struct rcu_segcblist cblist欄位中；
rcu_accelerate_cbs/rcu_advance_cbs，實現中都是通過操作struct rcu_segcblist結構，來完成回調函數的移動處理等；
__call_rcu函數第二個功能是判斷是否需要開啟新的寬限期GP；

鏈表的維護關係如下圖所示：

實際的設計比較巧妙，通過一個鏈表來鏈接所有的回調函數節點，同時維護一個二級指針數組，用於將該鏈表進行分段，分別維護不同階段的回調函數，回調函數的移動方向如圖所示，關於回調函數節點的處理都圍繞著這個圖來展開；

那麼通過__call_rcu註冊的這些回調函數在哪裡調用呢？答案是在RCU_SOFTIRQ軟中斷中：

當invoke_rcu_core時，在該函數中調用raise_softirq介面，從而觸發軟中斷回調函數rcu_process_callbacks的執行；
涉及到與寬限期GP相關的操作，在rcu_process_callbacks中會調用rcu_gp_kthread_wake喚醒內核線程，最終會在rcu_gp_kthread線程中執行；
涉及到RCU註冊的回調函數執行的操作，都在rcu_do_batch函數中執行，其中有兩種執行方式：1）如果不支持優先順序繼承的話，直接調用即可；2）支持優先順序繼承，在把回調的工作放置在rcu_cpu_kthread內核線程中，其中內核為每個CPU都創建了一個rcu_cpu_kthread內核線程；

6. 寬限期開始與結束

既然涉及到寬限期GP的操作，都放到了rcu_gp_kthread內核線程中了，那麼來看看這個內核線程的邏輯操作吧：

內核分別為rcu_preempt_state, rcu_bh_state, rcu_sched_state創建了內核線程rcu_gp_kthread；
rcu_gp_kthread內核線程主要完成三個工作：1）創建新的寬限期GP；2）等待強制靜止狀態，設置超時，提前喚醒說明所有處理器經過了靜止狀態；3）寬限期結束處理。其中，前邊兩個操作都是通過睡眠等待在某個條件上。

7. 靜止狀態檢測及報告

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

rcu_sched/rcu_bh類型的RCU中，當檢測CPU處於用戶模式或處於idle線程中，說明當前CPU已經離開了臨界區，經歷了一個QS靜止狀態，對於rcu_bh的RCU，如果沒有出去softirq上下文中，也表明CPU經歷了QS靜止狀態；
在rcu_pending滿足條件的情況下，觸發軟中斷的執行，rcu_process_callbacks將會被調用；
在rcu_process_callbacks回調函數中，對寬限期進行判斷，並對靜止狀態逐級上報，如果整個樹狀結構都經歷了靜止狀態，那就表明瞭寬限期的結束，從而喚醒內核線程去處理；
順便提一句，在rcu_pending函數中，rcu_pending->__rcu_pending->check_cpu_stall->print_cpu_stall的流程中，會去判斷是否有CPU stall的問題，這個在內核中有文檔專門來描述，不再分析了；

8. 狀態機變換

如果要觀察整個狀態機的變化，跟蹤一下trace_rcu_grace_period介面的記錄就能發現：

/*
 * 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. 總結

本文提綱挈領的捋了一下RCU的大體流程，主要涉及到RCU狀態機的輪轉，從開啟寬限期GP，到寬限期GP的初始化、靜止狀態QS的檢測、寬限期結束、回調函數的調用等，而這部分主要涉及到軟中斷RCU_SOFTIRQ和內核線程rcu_gp_kthread的動態運行及交互等；
內部的狀態組織是通過rcu_state, rcu_node, rcu_data組織成樹狀結構來維護，此外回調函數是通過rcu_data中的分段鏈表來批處理，至於這些結構中相關欄位的處理（比如gpnum, completed欄位的設置來判斷寬限期階段等），以及鏈表的節點移動等，都沒有進一步去分析跟進了；
RCU的實現機制很複雜，很多其他內容都還未涉及到，比如SRCU（可睡眠RCU）、可搶占RCU，中斷/NMI對RCU的處理等，只能說是蜻蜓點水了；
在閱讀代碼過程中，經常會發現一些巧妙的設計，有時會有頓悟的感覺，這也是其中的樂趣之一了；

漸入佳境篇就此打住，是否還會有登堂入室篇呢？想啥呢，歇歇吧。

參考

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

歡迎關註公眾號：

【原創】Linux RCU原理剖析（二）-漸入佳境

背景