Linux2.6.23 ：sleepable RCU的實(shí)現(xiàn)

一、前言

由于曾經(jīng)在Linux2.6.23上工作了多年，我對(duì)這個(gè)版本還是非常有感情的（拋開感情因素，本來(lái)應(yīng)該選擇longterm的2.6.32版本來(lái)分析的，^_^），本文主要就是描述Linux2.6.23內(nèi)核版本中對(duì)RCU有哪些修正。所謂修正主要包括兩個(gè)部分，一部分是bug fixed，一部分是新增的特性。

?

二、issue修復(fù)

1、synchronize_kernel是什么鬼？

僅僅從符號(hào)命名上就能看出來(lái)synchronize_kernel有點(diǎn)格格不入，其他的rcu API都有rcu這個(gè)字符，但是synchronize_kernel沒(méi)有。該函數(shù)的功能其實(shí)很多，如下：

（1）等待RCU reader離開臨界區(qū)（這是大家都熟悉的功能）

（2）等待NMI的handler調(diào)用完成

（3）等待所有的interrupt handler調(diào)用完成

（4）其他

因此，該函數(shù)用途太多，最終被兩個(gè)函數(shù)代替：synchronize_rcu和synchronize_sched。其中synchronize_rcu用于RCU的同步。而synchronize_sched負(fù)責(zé)其他方面的功能（本質(zhì)是等待系統(tǒng)中所有CPU退出不可搶占區(qū)）。順便一提的是這兩個(gè)函數(shù)目前的實(shí)現(xiàn)代碼是一樣的，不過(guò)由于語(yǔ)義不同，后續(xù)應(yīng)該會(huì)有所修改。

2、RCU callback的處理機(jī)制

為了實(shí)時(shí)性，在2.6.11內(nèi)核中，如果RCU callback數(shù)目太多，那么我們會(huì)把RCU callback分在若干次的tasklet context中執(zhí)行，而不是一次性的處理完畢。這樣大大降低了調(diào)度延遲，不過(guò)，又帶來(lái)了另外一個(gè)問(wèn)題：在負(fù)荷比較重的場(chǎng)景，由于每次處理的callback缺省是10個(gè)，實(shí)際上更多的callback請(qǐng)求會(huì)掛入從而導(dǎo)致RCU的鏈表不斷的增大，不斷的增大……

因此，在23內(nèi)核上，批量處理RCU請(qǐng)求的算法進(jìn)行了調(diào)整，增加了三個(gè)控制變量：

static int blimit = 10;?
static int qhimark = 10000;?
static int qlowmark = 100;

如果說(shuō)RCU是黑盒子，那么這三個(gè)變量就是控制黑盒子工作參數(shù)的旋鈕，如果你對(duì)目前系統(tǒng)中的RCU模塊工作狀態(tài)不滿意，可以轉(zhuǎn)動(dòng)這些旋鈕，調(diào)整一下該模塊的工作參數(shù)。blimit用來(lái)控制一次tasklet上下文中處理的RCU callback個(gè)數(shù)，類似2.6.11內(nèi)核中的maxbatch。在各個(gè)CPU初始化的時(shí)候會(huì)進(jìn)行下面的初始化動(dòng)作：

rdp->blimit = blimit;

rdp->blimit 是真正控制算法的變量，初始化的時(shí)候等于blimit，在運(yùn)行過(guò)程中，該值是動(dòng)態(tài)變化的，具體如何變是根據(jù)兩個(gè)watermark來(lái)處理的：qhimark是上限水位，qlowmark 是下限水位。此外，在struct rcu_data數(shù)據(jù)結(jié)構(gòu)中也增加了一個(gè)qlen成員來(lái)跟蹤目前RCU callback的數(shù)目。每次提交一個(gè)RCU callback，qlen就加一。當(dāng)渡過(guò)GP之后，調(diào)用RCU callback函數(shù)的時(shí)候qlen減一。

在了解了上述基礎(chǔ)信息之后，我們一起看看call_rcu的代碼：

if (unlikely(++rdp->qlen > qhimark)) {?
??? rdp->blimit = INT_MAX;－－－－－－－－－－－－－－－－－（1）?
??? force_quiescent_state(rdp, &rcu_ctrlblk);－－－－－－－－－（2）?
}

如果qlen太大，超過(guò)了qhimark水位，說(shuō)明提交的RCU callback太多，tasklet已經(jīng)忙不過(guò)來(lái)了，這時(shí)候，必須采取兩個(gè)措施：

（1）不再限制每次tasklet context中處理的請(qǐng)求個(gè)數(shù)。

（2）加快GP，讓各個(gè)CPU快點(diǎn)通過(guò)QS。如何做呢？其實(shí)至于強(qiáng)迫每個(gè)CPU上都進(jìn)行一個(gè)進(jìn)程切換就OK了。對(duì)于本CPU可以直接調(diào)用set_need_resched，對(duì)于其他CPU，只能是調(diào)用send_ipi_message函數(shù)發(fā)送ipi message，以便讓其他CPU自己進(jìn)行進(jìn)程調(diào)度。

看完上限水位的處理，我們?cè)僖黄鹂纯聪孪匏蝗绾翁幚?，在rcu_do_batch中：

if (rdp->blimit == INT_MAX && rdp->qlen <= qlowmark)?
??? rdp->blimit = blimit;

當(dāng)我們采用了上面所說(shuō)的方法雙管齊下，qlen應(yīng)該會(huì)不斷的減少，當(dāng)觸及下限水位的時(shí)候，將rdp->blimit的值恢復(fù)正常。

3、rcu_start_batch函數(shù)中的race issue

2.6.11中rcu_start_batch函數(shù)的部分代碼如下：

if (rcp->next_pending && rcp->completed == rcp->cur) {?
??? cpus_andnot(rsp->cpumask, cpu_online_map, nohz_cpu_mask); －－－－－－－A

??? rcp->next_pending = 0;?
??? smp_wmb();?
??? rcp->cur++;－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－B?
}

當(dāng)重新啟動(dòng)一個(gè)批次的RCU callback的Grace Period探測(cè)的時(shí)候，需要reset cpumask，設(shè)置next_pending以及給當(dāng)前的批次號(hào)加一。這里訪問(wèn)了nohz_cpu_mask這個(gè)全局變量，主要是為了減輕檢測(cè)各個(gè)CPU通過(guò)Quiescent state的工作量，畢竟那些進(jìn)入idle狀態(tài)的CPU其實(shí)是沒(méi)有進(jìn)行QS的檢查（注意：這里僅僅限于dynamic tick的情況，對(duì)于周期性tick而言，nohz_cpu_mask總是等于0）。不過(guò)，如果是上面的代碼邏輯，A點(diǎn)和B點(diǎn)之間，如果CPU進(jìn)入了IDLE，那么這會(huì)導(dǎo)致已經(jīng)進(jìn)入idle的CPU也進(jìn)入cpumask，從而延長(zhǎng)的GP的時(shí)長(zhǎng)。如何修正呢？很簡(jiǎn)單，將A處的代碼放到B之后。

rcu_start_batch函數(shù)還有一個(gè)小改動(dòng)，去掉了next_pending參數(shù)，改由調(diào)用者設(shè)定。

4、合并了struct rcu_ctrlblk和struct rcu_state

除了讓參數(shù)傳遞變得繁瑣，rcu控制塊分成兩個(gè)數(shù)據(jù)結(jié)構(gòu)是沒(méi)有什么意義的。

?

三、新增的功能

1、增加rcu_barrier

有些特殊的場(chǎng)合（例如卸載模塊或者umount文件系統(tǒng)）需要當(dāng)前的所有的RCU callback（也包括nxtlist鏈表中的剛剛提交請(qǐng)求的那些）都執(zhí)行完畢。注意：是callback執(zhí)行完畢而不是僅僅渡過(guò)Grace Period。我們可以舉一個(gè)實(shí)際的例子：比如文件系統(tǒng)的unmount函數(shù)中一般會(huì)釋放該文件系統(tǒng)特定的super block數(shù)據(jù)結(jié)構(gòu)實(shí)例，但是，如果RCU callback中還需要操作這個(gè)文件系統(tǒng)特定的super block數(shù)據(jù)結(jié)構(gòu)實(shí)例的時(shí)候（比如在callback中將該數(shù)據(jù)結(jié)構(gòu)實(shí)例從鏈表中摘除），在這樣的場(chǎng)景中，unmount函數(shù)必須要要等到RCU callback執(zhí)行完畢之后才能free該文件系統(tǒng)特定的super block數(shù)據(jù)結(jié)構(gòu)實(shí)例。

具體如何實(shí)現(xiàn)倒是比較簡(jiǎn)單。每個(gè)CPU都定義一個(gè)特別用于rcu barrier的callback請(qǐng)求，具體在struct rcu_data數(shù)據(jù)結(jié)構(gòu)中的barrier成員：

struct rcu_head barrier;

一旦用戶調(diào)用rcu_barrier函數(shù)，那么就在各個(gè)CPU上提交這個(gè)barrier的請(qǐng)求。如果每一個(gè)CPU上的barrier這個(gè)RCU callback已經(jīng)執(zhí)行完畢，那么就說(shuō)明系統(tǒng)中所有的（在調(diào)用rcu_barrier那一點(diǎn)）callback都已經(jīng)執(zhí)行完畢。為了跟蹤每一個(gè)CPU上的barrier執(zhí)行情況，需要一個(gè)counter：

static atomic_t rcu_barrier_cpu_count;

該counter初始值是0，提交barrier請(qǐng)求的時(shí)候該count加一，渡過(guò)Grace Period之后，在callback函數(shù)中減一，當(dāng)該counter減到0值的時(shí)候，說(shuō)明所有的CPU的barrier callback函數(shù)都執(zhí)行完畢，也就意味著當(dāng)前的所有的RCU callback都執(zhí)行完畢。

2、增加rcu_needs_cpu

在RCU模塊發(fā)展的同時(shí)，其他的內(nèi)核子系統(tǒng)也不斷在演進(jìn)，例如時(shí)間子系統(tǒng)。當(dāng)一個(gè)CPU由于無(wú)事可做而進(jìn)入idle的時(shí)候，關(guān)閉周期性的tick可以節(jié)省功耗，這也就是傳說(shuō)中的tickless（或者dynamic tick）特性。我們首先假設(shè)CPU A處于這樣的狀態(tài)：

（1）沒(méi)有新的請(qǐng)求，即nxtlist鏈表為空

（2）curlist鏈表有待處理的批次，雖然分配了批次號(hào)，但是還沒(méi)有啟動(dòng)該批次，也就是說(shuō)該批次是pending的

（3）當(dāng)前批次在本cpu的QS狀態(tài)已經(jīng)檢測(cè)通過(guò)

（4）沒(méi)有處理中的callback請(qǐng)求，即donelist鏈表為空

在這種狀態(tài)下，周期性tick到來(lái)的時(shí)候，其實(shí)沒(méi)有什么相關(guān)的RUC事情要處理，這時(shí)候，__rcu_pending返回0。在這種情況下，似乎停掉tick應(yīng)該是OK的，但是假設(shè)我們停掉了CPU A的tick，讓該CPU進(jìn)入idle狀態(tài)。如果CPU B是最后一個(gè)pass QS的CPU，這時(shí)候，該CPU會(huì)調(diào)用rcu_start_batch啟動(dòng)pending的那個(gè)批次（CPU A的curlist上的請(qǐng)求就是該批次的），由于要啟動(dòng)一個(gè)新的批次進(jìn)行GP的檢測(cè)，因此在該函數(shù)中會(huì)reset cpumask，代碼如下：

cpus_andnot(rcp->cpumask, cpu_online_map, nohz_cpu_mask);

如果CPU A進(jìn)入了idle state，并停掉了tick，那么cpumask將不處理CPU A的QS狀態(tài)，但是，curlist上的請(qǐng)求其實(shí)就是該批次的。怎么辦？應(yīng)該在curlist仍然有請(qǐng)求的時(shí)候，禁止該CPU進(jìn)入idle state并停掉tick，因此時(shí)間子系統(tǒng)需要RCU歐酷提供一個(gè)接口函數(shù)，用來(lái)收集RCU是否還需要該CPU的信息，這個(gè)接口就是rcu_needs_cpu。

3、增加srcu

SRCU其實(shí)就是sleepable RCU的縮寫，而我們常說(shuō)的RCU實(shí)際上是classic RCU，也就是在reader critical section中不能睡眠的，其在臨界區(qū)內(nèi)的代碼要求是spin lock一樣的。也正因?yàn)槿绱?，我們可以在進(jìn)程調(diào)度的時(shí)候可以判斷該CPU的QS已經(jīng)通過(guò)。SRCU是一個(gè)RCU的變種，從名字上也可以看出來(lái)，其reader critical section中可以block。一旦放開了這個(gè)口子，classic RCU所搭建的一切轟然倒塌，因此，直覺(jué)上SRCU是不可能實(shí)現(xiàn)的：

（1）一旦在reader critical section中sleep，那么GP就變得非常長(zhǎng)了，一直要等到該進(jìn)程被喚醒并調(diào)度執(zhí)行，這么長(zhǎng)的GP系統(tǒng)怎么受得了？畢竟系統(tǒng)需要在GP渡過(guò)之后，在callback中釋放資源

（2）進(jìn)程切換的時(shí)候判斷通過(guò)QS的機(jī)制失效

不過(guò)，realtime linux kernel要求不可搶占的臨界區(qū)要盡量的短，在這樣的需求背景下，spin lock的臨界區(qū)都因此而修改成為preemptible（只有raw spin lock保持了不可搶占的特性），RCU的臨界區(qū)也不能豁免，必須作出相應(yīng)的改動(dòng)，這也就是srcu的源由。

既然sleepable RCU勢(shì)在必行，那么我們必須要面對(duì)的問(wèn)題就是如何減少RCU callback請(qǐng)求的數(shù)量，要知道SRCU的GP可能非常的長(zhǎng)。解決方法如下：

（1）不再提供GP的異步接口（也就是call_rcu API），僅僅保留同步接口。如果提供了call_srcu這樣的接口，那么每一個(gè)使用rcu的線程可以提交任意多的RCU callback請(qǐng)求。而同步接口synchronize_srcu（類似RCU的synchronize_rcu接口）會(huì)阻塞當(dāng)前的thread，因此可以確保一個(gè)線程只會(huì)提交一個(gè)請(qǐng)求，從而大大降低請(qǐng)求的數(shù)目。

（2）細(xì)分GP。classic RCU的GP是一個(gè)批次一個(gè)批次的處理，一個(gè)批次的GP是for整個(gè)系統(tǒng)的，換句話說(shuō)，一個(gè)RCU reader side臨界區(qū)如果delay了，那么整個(gè)系統(tǒng)的RCU callback都會(huì)delay。對(duì)于SRCU而言，雖然GP比較長(zhǎng)，但是如果能夠?qū)⑹褂肧RCU的各個(gè)內(nèi)核子系統(tǒng)隔離開來(lái)，每個(gè)子系統(tǒng)都有自己GP，也就是說(shuō)，一個(gè)RCU reader side臨界區(qū)如果delay了，那么只是影響該子系統(tǒng)的RCU callback請(qǐng)求處理。

根據(jù)上面的思路，在linux2.6.23內(nèi)核中提供了SRCU機(jī)制，提供如下的API：

int init_srcu_struct(struct srcu_struct *sp);?
void cleanup_srcu_struct(struct srcu_struct *sp);?
int srcu_read_lock(struct srcu_struct *sp) __acquires(sp);?
void srcu_read_unlock(struct srcu_struct *sp, int idx) __releases(sp);?
void synchronize_srcu(struct srcu_struct *sp);

由于分隔了各個(gè)子系統(tǒng)的GP，因此各個(gè)子系統(tǒng)需要一個(gè)屬于自己的struct srcu_struct數(shù)據(jù)結(jié)構(gòu)，可以靜態(tài)定義也可以動(dòng)態(tài)分配，但是都需要調(diào)用init_srcu_struct來(lái)初始化。如果struct srcu_struct數(shù)據(jù)結(jié)構(gòu)是動(dòng)態(tài)分配，那么在free該數(shù)據(jù)結(jié)構(gòu)之前需要調(diào)用cleanup_srcu_struct來(lái)釋放占用的資源。srcu_read_lock和srcu_read_unlock用來(lái)界定SRCU的臨界區(qū)范圍，struct srcu_struct數(shù)據(jù)結(jié)構(gòu)做為該子系統(tǒng)的SRCU句柄傳遞給srcu_read_lock和srcu_read_unlock是可以理解的，但是idx是什么鬼？srcu_read_lock返回了idx，并做為參數(shù)傳遞給srcu_read_unlock函數(shù)，告知GP相關(guān)信息，具體后面會(huì)進(jìn)行描述。synchronize_srcu和synchronize_rcu行為類似，都是阻塞當(dāng)前進(jìn)程，直到渡過(guò)GP之后才會(huì)繼續(xù)執(zhí)行，不同的是，synchronize_srcu需要struct srcu_struct參數(shù)來(lái)指明是哪一個(gè)子系統(tǒng)的SRCU。

OK，了解了原理和API之后，我們來(lái)看看內(nèi)部實(shí)現(xiàn)。對(duì)于一個(gè)具體的某個(gè)子系統(tǒng)中的SRCU而言，三個(gè)控制數(shù)據(jù)就可以完成SRCU的邏輯：

（1）用一個(gè)全局變量來(lái)跟蹤系統(tǒng)中的GP。為了方便，我們可以給GP編號(hào)，從0開始，每渡過(guò)一個(gè)GP，該ID就會(huì)加1。如果當(dāng)前線程阻塞在synchronize_srcu，等到ID=a的GP過(guò)去，那么a+1就是pending的GP（也就是下一個(gè)要處理的GP ID）。struct srcu_struct中的completed成員就是起這個(gè)作用的。

（2）記錄各個(gè)GP中的位于reader critical section中的數(shù)目。當(dāng)然了，隨著系統(tǒng)的運(yùn)行，各個(gè)GP不斷的渡過(guò)，ID不斷的增加，但是在某個(gè)具體的時(shí)間點(diǎn)上，實(shí)際上不需要記錄每一個(gè)GP的reader臨界區(qū)的counter，只需要記錄current和next pending兩個(gè)reader臨界區(qū)的counter就OK了。為了性能，在2.6.23內(nèi)核中，這個(gè)counter是per cpu的，也就是struct srcu_struct中的per_cpu_ref成員，具體的counter定義如下：

struct srcu_struct_array {?
??? int c[2];?
};

c[0]和c[1]的counter是不斷的toggle的，如果c[0]是current，那么c[1]就是next pending，如果c[1]是current，那么c[0]就是next pending，具體如何選擇是根據(jù)struct srcu_struct中的completed成員的LSB的那個(gè)bit決定的。

根據(jù)上面的描述，我們來(lái)進(jìn)行邏輯解析。首先看srcu_read_lock的，該函數(shù)的邏輯很簡(jiǎn)單，就是根據(jù)next pending ID（保存在completed成員）的LSB bit確定counter的位置，給這個(gè)counter加一。當(dāng)然srcu_read_unlock執(zhí)行相反的動(dòng)作，略過(guò)。由于srcu_read_lock和srcu_read_unlock之間有可能會(huì)調(diào)用synchronize_srcu導(dǎo)致鎖定當(dāng)前pending的狀態(tài)并將GP ID（也就是completed成員）加一，因此，srcu_read_unlock需要一個(gè)額外的index參數(shù)，用來(lái)告知應(yīng)該選擇哪一個(gè)counter。

synchronize_srcu的邏輯也很簡(jiǎn)單，首先要確定當(dāng)前GP ID。也就是說(shuō)，之前next pending的那個(gè)就變成current（說(shuō)的很玄，本質(zhì)就是選擇哪一個(gè)counter，c[0]還是c[1]），completed++讓隨后的srcu_read_lock調(diào)用更換到另外一個(gè)counter中，成為next pending。然后等待current的counter在各個(gè)CPU上的計(jì)數(shù)變成0。一旦counter計(jì)數(shù)等于0則返回，說(shuō)明GP已經(jīng)過(guò)去。

?

四、參考文獻(xiàn)

1、2.6.23 source code

2、https://lwn.net/Articles/202847/