背景

• 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. 概述

我會假設你已經看過了《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

上一篇：Linux基礎操作筆記

下一篇：折騰 2 年多！我們終于見面了！