分級RCU的基礎(chǔ)知識

1、準(zhǔn)備工作

本文基于linux 2.6.32-rc7版本的源碼， 因此請準(zhǔn)備一份linux2.6.32-rc7代碼。建議用如下兩種方法獲取源代碼：

1、直接在linux.org上面下載源碼包。

2、使用git從linux-next拉取最新代碼，然后使用git checkout -b linux-2.6.32-rc7 v2.6.32-rc7檢出2.6.32-rc7版本的源碼。

2、概述

雖然Linux更早版本中的經(jīng)典RCU，其讀端原語擁有出色的性能和擴(kuò)展性，但是寫端原語則需要判斷預(yù)先存在的讀端臨界區(qū)在什么時候完成，它僅僅被設(shè)計(jì)用于數(shù)十個CPU的系統(tǒng)。經(jīng)典RCU的實(shí)現(xiàn)，要求在每個優(yōu)雅周期內(nèi)，每個CPU必須獲取一個全局鎖，這使得它們的擴(kuò)展性受到了限制。雖然在實(shí)際生產(chǎn)系統(tǒng)中，經(jīng)典RCU可以運(yùn)行在幾百個CPU的系統(tǒng)中，甚至能夠比較困難的使用到上千個 CPU的系統(tǒng)中，但是大型多核系統(tǒng)仍然需要更好的擴(kuò)展性。

另外，經(jīng)典RCU有一個不是最優(yōu)的dynticks 接口，導(dǎo)致經(jīng)典RCU在每一個優(yōu)雅周期都要喚醒每一個CPU，即使這些CPU處于idle狀態(tài)。我們考慮一個16核的系統(tǒng)，它只有四個CPU比較忙，其他CPU的負(fù)載都很輕。理想情況下，余下12個CPU可以一直處于深度睡眠模式以節(jié)約能源。然而不幸的是，如果四個忙的CPU頻繁的執(zhí)行RCU更新，這12個空閑CPU會被周期性的喚醒，浪費(fèi)了重要的能源。因此，對于經(jīng)典RCU的任何優(yōu)化，都應(yīng)當(dāng)讓這些睡眠狀態(tài)的CPU繼續(xù)處于睡眠狀態(tài)。

經(jīng)典RCU和分級RCU實(shí)現(xiàn)都有和經(jīng)典RCU相同的語義和API。但是，原有的實(shí)現(xiàn)被稱為“經(jīng)典RCU”，新實(shí)現(xiàn)被稱為“分級RCU”。

2.1.RCU基礎(chǔ)回顧

從最基本的方面來說，RCU 是一種等待事務(wù)完成的方法。當(dāng)然，要等待事務(wù)完成，還存在很多其他方法，包括引用計(jì)數(shù)、讀寫鎖、事件等等。RCU的一個大的優(yōu)勢是可以同時等待20，000個不同的事件，而不必具體的跟蹤其中每一個事件，并且不用擔(dān)心性能被降低，以及擴(kuò)展性被限制，也不用擔(dān)心復(fù)雜的死鎖情況和內(nèi)存泄漏的危險(xiǎn)。

在RCU中，被等待的事件被稱為“RCU 讀端臨界區(qū)”。RCU讀端臨界區(qū)以rcu_read_lock()原語開始，以相應(yīng)的rcu_read_unlock() 原語結(jié)束。RCU讀端臨界區(qū)可以嵌套，也可以包含相當(dāng)多的代碼，只要這些代碼不阻塞或者睡眠(當(dāng)然，這是針對經(jīng)典RCU來說的。有一種特殊的名為SRCU的可睡眠RCU，它允許在SRCU讀端臨界區(qū)中進(jìn)行短期睡眠)。如果您遵從這些約束，您可以使用RCU來等待任何代碼片段完成。

RCU通過間接的確定其他事務(wù)何時完成來實(shí)現(xiàn)這一點(diǎn)。但是，請注意：在特定的優(yōu)雅周期之后開始的RCU 讀端臨界區(qū)能夠、也必然會延長優(yōu)雅周期的結(jié)束點(diǎn)。

2.2.經(jīng)典RCU實(shí)現(xiàn)概要

經(jīng)典RCU實(shí)現(xiàn)的關(guān)鍵原理是：經(jīng)典RCU 讀端臨界區(qū)限制其中的內(nèi)核代碼不允許阻塞。這意味著在任意時刻，一個特定的CPU只要看起來處于阻塞狀態(tài)、IDLE循環(huán)、或者離開了內(nèi)核后，我們就知道所有RCU讀端臨界區(qū)已經(jīng)完成。這些狀態(tài)被稱為“靜止?fàn)顟B(tài)”，當(dāng)每一個CPU已經(jīng)經(jīng)歷過至少一次靜止?fàn)顟B(tài)時，RCU優(yōu)雅周期結(jié)束。

經(jīng)典RCU最重要的數(shù)據(jù)結(jié)構(gòu)是rcu_ctrlblk，它包含了->cpumask字段，每一個CPU在該字段中包含一位，如上圖所示。當(dāng)每一個優(yōu)雅周期開始時，每一個 CPU相應(yīng)的位被設(shè)置為1，每一個CPU經(jīng)過一次靜止?fàn)顟B(tài)時，必須清除相應(yīng)的位。由于多個CPU可能希望同時清除它們的位，這將破壞->cpumask 字段，因此使用了一個->lock自旋鎖來保護(hù)->cpumask。不幸的是，當(dāng)超過幾千個CPU時，這個自旋鎖會遇到嚴(yán)重的競爭狀態(tài)。更糟糕的是，事實(shí)上所有CPU必須清除它們的位，意味著在一個優(yōu)雅周期內(nèi)，CPU不允許一直睡眠。這削弱了LINUX節(jié)能的能力。

2.3.RCU 迫切要解決的問題

實(shí)時RCU迫切要解決的問題列表如下：

1. 延遲銷毀。這樣，直到所有已經(jīng)預(yù)先存在的RCU讀端臨界區(qū)已經(jīng)完成，一個RCU優(yōu)雅周期才能結(jié)束。

2. 可靠性，這樣RCU支持24x7運(yùn)行。

3. 可以在IRQ處理函數(shù)中調(diào)用。

4. 包含內(nèi)存標(biāo)記，這樣，如果有很多回調(diào)過程，這種機(jī)制將加快結(jié)束優(yōu)雅周期。

5. 獨(dú)立的內(nèi)存塊，這樣RCU能夠基于可信的內(nèi)存分配器進(jìn)行工作。

6. synchronization-free的讀端，這樣允許通常的非原子指令操作于CPU（或者任務(wù)）的本地內(nèi)存。

7. 無條件的read-to-write提升，在LINUX內(nèi)核中，有幾個地方需要這樣使用。

8. 兼容的API。

9. 搶占RCU讀端臨界區(qū)的要求可以被去掉。

10. 極低的RCU內(nèi)部鎖的競爭，從而帶來極大的擴(kuò)展性。RCU必須支持至少1，024個CPU，最好是至少4，096個CPU。

11. 節(jié)能：RCU必須能夠避免喚醒低電壓狀態(tài)的dynticks-idle CPU，但是仍然能夠判斷當(dāng)前的優(yōu)雅周期何時結(jié)束。這已經(jīng)在實(shí)時RCU中實(shí)現(xiàn)，但是需要大大的簡化。

12. RCU讀端臨界區(qū)必須允許在NMI處理函數(shù)中使用，就如在中斷處理函數(shù)中一樣。

13. RCU必須很好的管理不停的CPU熱插撥操作。

14. 必須能夠等待所有事先注冊的RCU回調(diào)完成，雖然這已經(jīng)以rcu_barrier()的形式提供。

15. 檢測失去響應(yīng)的CPU是值得的，以幫助診斷RCU和死循環(huán)BUG及硬件錯誤，這能夠防止RCU優(yōu)雅周期不能結(jié)束的情況。

16. 加快RCU優(yōu)雅周期是值得的，這樣RCU優(yōu)雅周期能夠強(qiáng)制在數(shù)百微秒內(nèi)完成。但是，這樣的操作預(yù)期會帶來嚴(yán)重的CPU負(fù)載。

最急迫的首要需求是：可擴(kuò)展性。因此需要減少RCU的內(nèi)部鎖。

2.4.邁向可擴(kuò)展RCU實(shí)現(xiàn)

減少鎖競爭的一個有效方法是創(chuàng)建一個分級結(jié)構(gòu)，如上圖所示。在此，四個rcu_node 結(jié)構(gòu)中的每一個都有各自的鎖，這樣只有 CPU 0 和 1 會獲取最左邊的 rcu_node的鎖， CPU 2 和 3 會獲取中間的rcu_node的鎖，CPU 4和5會獲取右邊的rcu_node的鎖。在任一個優(yōu)雅周期期間，僅僅某一個CPU節(jié)點(diǎn)會訪問rcu_node 結(jié)構(gòu)的上一層的rcu_node。也就是說，在上圖中，每一對CPU(它們處于同一個CPU節(jié)點(diǎn))中，最后一個記錄靜止?fàn)顟B(tài)的CPU才會訪問上一層的rcu_node。

這樣做的最終結(jié)果，是減少了鎖的競爭。在經(jīng)典RCU中，6個CPU在每一個優(yōu)雅周期內(nèi)競爭同一個全局鎖，在上圖中，僅僅是三個節(jié)點(diǎn)競爭最上層的rcu_node鎖 (降低了50%)。

rcu_node結(jié)構(gòu)樹被嵌入到rcu_state 結(jié)構(gòu)的一個線性數(shù)組，樹根是結(jié)點(diǎn)0，如上圖。它是一個8-CPU的、三層分級結(jié)構(gòu)的系統(tǒng)。每一個箭頭將一個rcu_node 結(jié)構(gòu)鏈接到它的父結(jié)點(diǎn)，這對應(yīng)著rcu_node結(jié)構(gòu)的->parent 字段。每一個rcu_node都標(biāo)示了它所覆蓋的CPU范圍，這樣根結(jié)點(diǎn)覆蓋了所有CPU，每一個二級結(jié)點(diǎn)覆蓋了一半的CPU，每一個葉子結(jié)點(diǎn)覆蓋了兩個 CPU。這個數(shù)組在編譯時基于NR_CPUS的值靜態(tài)分配。

上圖顯示了如何檢測優(yōu)雅周期。在第一個圖中，沒有CPU經(jīng)過靜止?fàn)顟B(tài)，并用紅塊標(biāo)示。假設(shè)所有6個CPU試圖同時告訴RCU，它們已經(jīng)經(jīng)過一個靜止?fàn)顟B(tài)。那么，在每一對CPU中，僅僅其中某一個CPU能夠獲得底層rcu_node結(jié)構(gòu)的鎖。第二個圖中，假設(shè)CPU0、3、5比較幸運(yùn)的獲得了底層rcu_node結(jié)構(gòu)的鎖，在圖中標(biāo)識為綠色塊。一旦這些幸運(yùn)的CPU結(jié)束了，那么其他CPU將獲得鎖，如圖3所示。這三個CPU中，每一個CPU將會發(fā)現(xiàn)它們是組內(nèi)最后一個CPU，因此所有三個CPU嘗試移到上層rcu_node。此時，僅僅其中一個能獲得上層rcu_node 鎖。我們假設(shè)CPU1、2、4依次獲得了鎖，則第4、5、6圖顯示了相應(yīng)的狀態(tài)。最后，第6圖顯示了所有CPU已經(jīng)經(jīng)過一次靜止?fàn)顟B(tài)，因此優(yōu)雅周期結(jié)束。

在上面的順序中，沒有超過3個CPU為同一個鎖產(chǎn)生競爭，與經(jīng)典RCU進(jìn)行對比，我們會高興的發(fā)現(xiàn)，經(jīng)典RCU中，所有6個CPU都可能沖突。但是，對更多的CPU來說，可以再顯著的減少鎖之間的沖突?？紤]有64個底層結(jié)構(gòu)及64*64=4,096 CPU的分組結(jié)構(gòu)，如圖上圖。

在此，每一個底層rcu_node 結(jié)構(gòu)的鎖被64個CPU申請，將從經(jīng)典RCU的4096個CPU競爭一個單一的鎖降為64個CPU競爭一個鎖。在一個特定的優(yōu)雅周期期間，僅僅一個底層rcu_node 中的某一個CPU會申請上級rcu_node 的鎖。這樣，與經(jīng)典RCU相比，減少了64倍的鎖競爭。

2.5.邁向不成熟的RCU實(shí)現(xiàn)

正如較早前提示的一樣，這些努力的一個重要目的是使一個處于睡眠狀態(tài)的CPU保持它的睡眠狀態(tài)，以節(jié)約能源。與之相對的是，經(jīng)典RCU至少會在一個優(yōu)雅周期內(nèi)喚醒每一個處于睡眠狀態(tài)的CPU。當(dāng)其他大多數(shù)CPU都處于空閑狀態(tài)時，這些個別的CPU進(jìn)行rcu寫操作，會使得這種處理方法不是最優(yōu)的。這種情形將在周期性的高負(fù)載系統(tǒng)中發(fā)生，我們需要更好的處理這種情況。

這是通過要求所有CPU操作位于一個每CPU rcu_dynticks 結(jié)構(gòu)中的計(jì)數(shù)器來實(shí)現(xiàn)的。不是那么準(zhǔn)確的說，當(dāng)相應(yīng)的CPU處于dynticks idle模式時，計(jì)數(shù)器的值為偶數(shù)，否則是奇數(shù)。這樣，RCU僅僅需要等待rcu_dynticks 計(jì)數(shù)值為奇數(shù)的CPU經(jīng)過靜止?fàn)顟B(tài)，而不必喚醒正在睡眠的CPU。如上圖，每一個每CPU rcu_dynticks結(jié)構(gòu)被“rcu”和“rcu_bh”實(shí)現(xiàn)所共享。

2.6.狀態(tài)機(jī)

從十分高層的視角來看，Linux內(nèi)核RCU 實(shí)現(xiàn)可以被認(rèn)為是一個高級狀態(tài)機(jī)，如上圖。在一個很繁忙的系統(tǒng)上，通常的路徑是最上面的兩個循環(huán)。在每一個優(yōu)雅周期(GP)開始時進(jìn)行初始化，等待靜止?fàn)顟B(tài) (QS)。在一個特定的優(yōu)雅周期中，當(dāng)每一個CPU都經(jīng)歷過靜止?fàn)顟B(tài)時，它其實(shí)什么都不用做。在這樣一個系統(tǒng)中，經(jīng)歷如下事件表明產(chǎn)生一個靜止?fàn)顟B(tài)：

1、每一次進(jìn)程切換

2、在CPU進(jìn)入idle狀態(tài)

3、或者執(zhí)行用戶態(tài)代碼時

CPU熱插撥事件將使?fàn)顟B(tài)機(jī)進(jìn)入“CPU Offline”流程。而“holdout”CPU（那些由于軟件或者硬件原因?qū)е逻t遲不能經(jīng)過一次靜止?fàn)顟B(tài)的CPU）的出現(xiàn)，使得不能快速經(jīng)歷一次靜止?fàn)顟B(tài)，這將使?fàn)顟B(tài)機(jī)進(jìn)入“send reschedIPIs to Holdout CPUs”（發(fā)送重新調(diào)度IPI給Holdout CPUS）流程。為了避免不必要的喚醒處于dyntick-idle 狀態(tài)的CPU，RCU 實(shí)現(xiàn)將標(biāo)記這些CPU處于擴(kuò)展的靜止?fàn)顟B(tài)，通過“Y”分支離開“CPUs in dyntick-idle Mode?”（但是請注意，這些處于dyntick-idle模式的CPU將不會被發(fā)送重新調(diào)度IPI）。最后，如果CONFIG_RCU_CPU_STALL_DETECTOR打開了，過遲的到達(dá)靜止?fàn)顟B(tài)將使?fàn)顟B(tài)機(jī)進(jìn)入“Complain About Holdout CPUs”流程。

上面的狀態(tài)圖中，事件會與不同的數(shù)據(jù)結(jié)構(gòu)交互。但是，狀態(tài)圖不會被任何RCU實(shí)現(xiàn)直接翻譯為C代碼。相反的，這些實(shí)現(xiàn)在內(nèi)核中被編碼為事件驅(qū)動的系統(tǒng)。我們通過一些用例來表示這些事件。

2.7.用例

這些事件驅(qū)動的用例包括：

1.開始一個新的優(yōu)雅周期

2.經(jīng)歷一個靜止?fàn)顟B(tài)

3.向RCU通告一個靜止?fàn)顟B(tài)

4.進(jìn)入、退出Dynticks Idle 模式

5.從Dynticks Idle 模式進(jìn)入中斷

6.從 Dynticks Idle 模式進(jìn)入NMI

7.標(biāo)記一個CPU處于Dynticks Idle 模式

8.CPU離線

9.CPU上線

10.檢測一個太長的優(yōu)雅周期

2.7.1.開始一個新的優(yōu)雅周期

rcu_start_gp()函數(shù)開始一個新的優(yōu)雅周期。當(dāng)一個CPU存在回調(diào)，而該回調(diào)需要等待優(yōu)雅周期時，就需要調(diào)用此函數(shù)。

rcu_start_gp()函數(shù)更新rcu_state和rcu_data結(jié)構(gòu)中的狀態(tài)，以標(biāo)識開始一個新的優(yōu)雅周期，獲取->onoff 鎖 (并關(guān)中斷) 以防止任何并發(fā)的CPU熱插撥操作，在所有的rcu_node結(jié)構(gòu)中設(shè)置位，以標(biāo)識所有CPU (包括當(dāng)前CPU) 必須經(jīng)歷一次靜止?fàn)顟B(tài)，最后釋放->onoff 鎖。

設(shè)置位操作分兩個階段進(jìn)行。首先，在沒有持有任何鎖的情況下，非葉子節(jié)點(diǎn)rcu_node 的位被設(shè)置，然后，在持有->lock的情況下，每一個葉子節(jié)點(diǎn)的rcu_node 結(jié)構(gòu)的位被設(shè)置。

2.7.2.經(jīng)歷一次靜止?fàn)顟B(tài)

rcu和rcu_bh有各自的靜止?fàn)顟B(tài)集合。

RCU的靜止?fàn)顟B(tài)是進(jìn)程切換、IDLE (不管是dynticks 還是IDLE循環(huán))、以及執(zhí)行用戶態(tài)程序。

RCU-bh的靜止?fàn)顟B(tài)是在開中斷狀態(tài)下，退出軟中斷。

需要注意的是，rcu的靜止?fàn)顟B(tài)也是rcu_bh的靜止?fàn)顟B(tài)。rcu的靜止?fàn)顟B(tài)通過調(diào)用rcu_qsctr_inc()來記錄。而rcu_bh的靜止?fàn)顟B(tài)通過調(diào)用rcu_bh_qsctr_inc()來記錄。這兩個函數(shù)將它們的狀態(tài)記錄到當(dāng)前CPU的rcu_data 結(jié)構(gòu)中。請注意：在2.6.32版本中，rcu_qsctr_inc和rcu_bh_qsctr_inc函數(shù)已經(jīng)被更名。如何通過git查找它們被更名為什么名稱，這個任務(wù)就留給作者當(dāng)做練習(xí)了。

這些函數(shù)在調(diào)度器、__do_softirq()和rcu_check_callbacks()中被調(diào)用。后面這個函數(shù)在調(diào)度時鐘中斷中調(diào)用，并分析狀態(tài)以確定中斷是否發(fā)生在一個靜止?fàn)顟B(tài)中，以確定是調(diào)用rcu_qsctr_inc()或者 rcu_bh_qsctr_inc()。它也觸發(fā)RCU_SOFTIRQ軟中斷，并導(dǎo)致當(dāng)前CPU在隨后的軟中斷上下文中調(diào)用rcu_process_callbacks()，rcu_process_callbacks函數(shù)處理RCU在每個CPU上的回調(diào)函數(shù)以釋放資源。

2.7.3.向RCU宣告一次靜止?fàn)顟B(tài)

前述的rcu_process_callbacks() 函數(shù)要完成幾個事情：

1.確定何時結(jié)束一個太長的優(yōu)雅周期(通過force_quiescent_state())。

2.當(dāng)CPU檢測到優(yōu)雅周期結(jié)束時，采用適當(dāng)?shù)膭幼鳌?通過 rcu_process_gp_end())?！斑m當(dāng)?shù)膭幼鳌卑涌毂綜PU的回調(diào)，以及記錄新的優(yōu)雅周期。同一個函數(shù)也更新狀態(tài)以響應(yīng)其他CPU。

3.向RCU核心機(jī)制報(bào)告當(dāng)前CPU的靜止?fàn)顟B(tài)。(通過 rcu_check_quiescent_state()，它會調(diào)用 cpu_quiet())。當(dāng)然，這個過程也會標(biāo)記當(dāng)前的優(yōu)雅周期結(jié)束。

4.如果沒有處理優(yōu)雅周期，并且這個CPU有RCU回調(diào)等待優(yōu)雅周期，則開始一個新的優(yōu)雅周期(通過 cpu_needs_another_gp()和rcu_start_gp())。

5.當(dāng)優(yōu)雅周期結(jié)束時，調(diào)用這個CPU的回調(diào) (通過 rcu_do_batch())。

這些接口都經(jīng)過精心實(shí)現(xiàn)，以避免BUG，如：錯誤的從上一個優(yōu)雅周期向當(dāng)前優(yōu)雅周期報(bào)告靜止?fàn)顟B(tài)這樣的BUG。

2.7.4.進(jìn)入和退出 Dynticks Idle模式

調(diào)度器調(diào)用rcu_enter_nohz()進(jìn)入dynticks-idle 模式，并調(diào)用 rcu_exit_nohz()離開此模式。rcu_enter_nohz() 函數(shù)遞增每CPU dynticks_nesting變量，也遞增每CPU dynticks計(jì)數(shù)器，然后，后者必然擁有一個偶數(shù)值。rcu_exit_nohz() 函數(shù)遞減每CPU dynticks_nesting 變量，并且再一次遞增每CPU dynticks計(jì)數(shù)器，后者將擁有一個奇數(shù)值。

dynticks 計(jì)數(shù)器可以被其他 CPU采樣。如果其值是偶數(shù)，那么該CPU處于擴(kuò)展靜止?fàn)顟B(tài)。類似的，如果計(jì)數(shù)器在一個特定的優(yōu)雅周期內(nèi)發(fā)生了改變，那么CPU必然在優(yōu)雅周期期間的某個時間點(diǎn)上處于擴(kuò)展靜止?fàn)顟B(tài)。但是，還需要采樣另外一個dynticks_nmi每CPU變量，隨后我們將討論這個變量。

2.7.5.從Dynticks Idle 模式進(jìn)入中斷

從dynticks idle 模式進(jìn)入中斷由rcu_irq_enter() 和 rcu_irq_exit()處理。rcu_irq_enter() 函數(shù)遞增每CPU dynticks_nesting 變量，如果此變量為0，也遞增dynticks每CPU變量 (它將擁有一個奇數(shù)值)。

rcu_irq_exit()函數(shù)遞減每CPU dynticks_nesting變量。并且，如果新值是0，也遞增dynticks每CPU變量 (它將擁有一個偶數(shù)值)。

注意：進(jìn)入中斷會處理退出dynticks idle模式，反之也一樣。進(jìn)入、退出之間不一致可能導(dǎo)致一些混亂，不用警告你也應(yīng)該想得到這一點(diǎn)。

2.7.6.從Dynticks Idle 模式進(jìn)入NMI

從dynticks idle模式進(jìn)入NMI由rcu_nmi_enter()和rcu_nmi_exit()處理。這些函數(shù)同時遞增dynticks_nmi計(jì)數(shù)器，但僅僅是在前述dynticks 計(jì)數(shù)是偶數(shù)時才進(jìn)行遞增。換句話說，如果NMI發(fā)生時，處于非dynticks-idle模式或者處于中斷狀態(tài)，那么 NMI將不操作dynticks_nmi計(jì)數(shù)器。

這兩個函數(shù)之間唯一的差異在于錯誤檢查，rcu_nmi_enter()必然使dynticks_nmi計(jì)數(shù)器為奇數(shù)值，rcu_nmi_exit()必然使這個計(jì)數(shù)器為偶數(shù)值。

2.7.7.標(biāo)記CPU處于Dynticks Idle模式

force_quiescent_state()函數(shù)實(shí)現(xiàn)一個三階段的狀態(tài)機(jī)。第一個階段 (RCU_INITIALIZING)等待rcu_start_gp()完成對優(yōu)雅周期的初始化。這個狀態(tài)不是從force_quiescent_state()退出，就是從rcu_start_gp()退出。

在第二階段(RCU_SAVE_DYNTICK)，dyntick_save_progress_counter()函數(shù)掃描還沒有報(bào)告靜止?fàn)顟B(tài)的CPU，記錄它們的每CPU dynticks 和dynticks_nmi 計(jì)數(shù)器。如果這些計(jì)數(shù)器都是偶數(shù)值，那么相應(yīng)的CPU處于dynticks-idle 狀態(tài)，因此標(biāo)記它們?yōu)閿U(kuò)展靜止?fàn)顟B(tài)(通過cpu_quiet_msk()報(bào)告)。

在第三階段(RCU_FORCE_QS)，rcu_implicit_dynticks_qs()函數(shù)再一次掃描仍然沒有報(bào)告靜止?fàn)顟B(tài)的CPU (既沒有明確標(biāo)示，也沒有在RCU_SAVE_DYNTICK階段隱含的標(biāo)示)，再一次檢查每CPU dynticks 和 dynticks_nmi計(jì)數(shù)器。如果每一個值都變化，或者目前為偶數(shù)，那么相應(yīng)的相應(yīng)的CPU已經(jīng)經(jīng)過一次靜止?fàn)顟B(tài)或者目前處于dynticks idle模式，也就是前述擴(kuò)展靜止?fàn)顟B(tài)。

如果rcu_implicit_dynticks_qs()發(fā)現(xiàn)特定CPU既沒有處于dynticks idle模式，也沒有報(bào)告一個靜止?fàn)顟B(tài)，它調(diào)用rcu_implicit_offline_qs()，這個函數(shù)檢查CPU是否處于離線狀態(tài)，如果是，那么也報(bào)告一個擴(kuò)展靜止?fàn)顟B(tài)。如果CPU在線，那么rcu_implicit_offline_qs()發(fā)送一個重新調(diào)度IPI，嘗試提醒該CPU應(yīng)當(dāng)向RCU報(bào)告一個靜止?fàn)顟B(tài)。

請注意：force_quiescent_state() 既不直接調(diào)用dyntick_save_progress_counter()，也不直接調(diào)用rcu_implicit_dynticks_qs()，而是將它們傳遞給rcu_process_dyntick() 函數(shù)。這個函數(shù)抽象出掃描CPU、報(bào)告擴(kuò)展靜止?fàn)顟B(tài)的通用代碼。

2.7.8.CPU離線

CPU離線事件導(dǎo)致rcu_cpu_notify()調(diào)用rcu_offline_cpu()，在rcu和rcu_bh上依次調(diào)用__rcu_offline_cpu()。這個函數(shù)清除離線CPU的位，這樣，后面的優(yōu)雅周期將不再期望這個CPU宣告靜止?fàn)顟B(tài)，隨后調(diào)用cpu_quiet()，以宣告離線擴(kuò)展靜止?fàn)顟B(tài)。這是在持有全局->onofflock鎖的情況下執(zhí)行的，這是為了防止與優(yōu)雅周期初始化相沖突。

2.7.9.CPU上線

CPU上線事件導(dǎo)致rcu_cpu_notify()調(diào)用rcu_online_cpu()，用于初始化CPU的dynticks狀態(tài)，然后調(diào)用rcu_init_percpu_data()初始化CPU的rcu_data 數(shù)據(jù)結(jié)構(gòu)，也設(shè)置這個 CPU的位(同樣通過全局->onofflock進(jìn)行保護(hù))，這樣后面的優(yōu)雅周期將等待這個CPU的靜止?fàn)顟B(tài)。最后，rcu_online_cpu()設(shè)置這個CPU的RCU 軟中斷向量。

2.7.10.檢測太長的優(yōu)雅周期

當(dāng)配置了CONFIG_RCU_CPU_STALL_DETECTOR內(nèi)核參數(shù)時，record_gp_stall_check_time() 函數(shù)記錄當(dāng)前時間，以及3秒以后的時間戳。如果當(dāng)前優(yōu)雅周期到期后仍然沒有結(jié)束，那么check_cpu_stall函數(shù)將檢測罪魁禍?zhǔn)?。并且如果?dāng)前CPU是造成延遲的CPU，則調(diào)用print_cpu_stall()，如果不是，則調(diào)用print_other_cpu_stall()。兩個jiffies的時間差有助于確保其他CPU在可能的情況下報(bào)告它的狀態(tài)，利用這個時間差，CPU能夠做一些事情，例如跟蹤它自己的堆棧。

2.8.測試

RCU是基本的同步代碼，因此RCU的錯誤導(dǎo)致的后果是隨機(jī)的、難于調(diào)試的內(nèi)存錯誤。因此，高可靠的RCU是非常重要的。這些可靠性來自于小心的設(shè)計(jì)，但是最終還是需要依賴于高強(qiáng)度的壓力測試。

幸運(yùn)的是，雖然有一些關(guān)于覆蓋性方面的爭論，但是仍然可以對軟件進(jìn)行一些壓力測試。實(shí)際上，進(jìn)行這些測試是被強(qiáng)烈建議的，因?yàn)椴粚δ愕能浖M(jìn)行折磨性測試的話，它就會反過來折磨你，這種折磨來自于：它在不合時宜的時候崩潰掉。

因此，我們使用rcutorture模塊來對RCU進(jìn)行壓力測試。

但是，根據(jù)通常情況下的RCU用法來對RCU進(jìn)行測試，顯得還不是很充分。也有必要針對不常用的情況進(jìn)行壓力測試。例如，CPU并發(fā)的上線或者離線，CPU并發(fā)的進(jìn)入及退出dynticks idle模式。Paul使用了一個腳本CodeSamples，并向模塊rcutorture使用test_no_idle_hz 模塊參數(shù)對dynticks idle模式進(jìn)行壓力測試。有時作者也比較疑神疑鬼，因此盡量在測試時運(yùn)行一個kernbench負(fù)載測試程序。在128路的機(jī)器上運(yùn)行10個小時的壓力測試，看起來是足夠測試出幾乎所有BUG了。

實(shí)際上這還不算完。Alexey Dobriyan和Nick Piggin早在2008年就證明過，以所有相關(guān)內(nèi)核參數(shù)組合對RCU進(jìn)行壓力測試是必要的。相關(guān)的內(nèi)核參數(shù)可以使用另外一個腳本CodeSamples進(jìn)行標(biāo)識。

1.CONFIG_CLASSIC_RCU：經(jīng)典 RCU。

2.CONFIG_PREEMPT_RCU：可搶占 (實(shí)時) RCU。

3.CONFIG_TREE_RCU：用于大型SMP系統(tǒng)的經(jīng)典 RCU。

4.CONFIG_RCU_FANOUT：每一個rcu_node 的子結(jié)點(diǎn)數(shù)量。

5.CONFIG_RCU_FANOUT_EXACT：平衡rcu_node 樹。

6.CONFIG_HOTPLUG_CPU：允許 CPU上線、離線。

7.CONFIG_NO_HZ：打開dyntick-idle 模式。

8.CONFIG_SMP：打開 multi-CPU選項(xiàng)。

9.CONFIG_RCU_CPU_STALL_DETECTOR：當(dāng)CPU進(jìn)入擴(kuò)展靜止?fàn)顟B(tài)時進(jìn)行RCU檢測。

10.CONFIG_RCU_TRACE：在debugfs中生成 RCU跟蹤文件。

我們忽略CONFIG_DEBUG_LOCK_ALLOC 配置變量，因?yàn)槲覀兗僭O(shè)分級RCU不能打斷 lockdep。仍然有10個配置變量，如果它們是獨(dú)立的布爾值，則導(dǎo)致1024種組合。幸運(yùn)的是，首先，其中前三個是互斥的，這樣可以將組合數(shù)量減少到384個，但是CONFIG_RCU_FANOUT可以取值2-64，將組合數(shù)量增加到12，096。這么大量的組合是不可能都實(shí)施的。

關(guān)鍵的一點(diǎn)是：如果CONFIG_CLASSIC_RCU或者CONFIG_PREEMPT_RCU有效時，預(yù)期僅僅CONFIG_NO_HZ 和 CONFIG_PREEMPT 可能會改變其行為。這幾乎減少了三分之二的組合。

而且，并不是這些所有可能的CONFIG_RCU_FANOUT值都會產(chǎn)生顯著有效的結(jié)果，實(shí)際上僅僅一部分情況需要分別測試：

1.單結(jié)點(diǎn)“tree”。

2.兩級平衡樹。

3.三級平衡樹。

4.自動平衡樹，當(dāng) CONFIG_RCU_FANOUT 指定一個不平衡樹，但是沒有配置CONFIG_RCU_FANOUT_EXACT 時，進(jìn)行自動平衡。

5.非平衡樹。

更進(jìn)一步說，CONFIG_HOTPLUG_CPU僅僅在指定CONFIG_SMP 時才有用，CONFIG_RCU_CPU_STALL_DETECTOR是獨(dú)立的，因此僅僅需要測試一次(然而有些人比我還多疑，他們可能決定在有CONFIG_SMP和沒有CONFIG_SMP 時，都測試它)。類似的，CONFIG_RCU_TRACE也僅僅需要測試一次。但是象我一樣多疑的人，會選擇在有CONFIG_NO_HZ 和沒有CONFIG_NO_HZ 時，都測試一下它。

這允許我們在15種測試情形下，得到一個覆蓋率較好的RCU測試。所有這些測試情形都指定如下配置參數(shù)以運(yùn)行rcutorture，這樣CONFIG_HOTPLUG_CPU=n會產(chǎn)生實(shí)際的效果：

CONFIG_RCU_TORTURE_TEST=m

CONFIG_MODULE_UNLOAD=y

CONFIG_SUSPEND=n

CONFIG_HIBERNATION=n

15個測試用例如下：

1.強(qiáng)制單節(jié)點(diǎn)“樹”，用于小型系統(tǒng)：

CONFIG_NR_CPUS=8

CONFIG_RCU_FANOUT=8

CONFIG_RCU_FANOUT_EXACT=n

CONFIG_RCU_TRACE=y

CONFIG_PREEMPT_RCU=n

CONFIG_CLASSIC_RCU=n

CONFIG_TREE_RCU=y

2.強(qiáng)制兩級節(jié)點(diǎn)樹用于大型系統(tǒng)：

CONFIG_NR_CPUS=8

CONFIG_RCU_FANOUT=4

CONFIG_RCU_FANOUT_EXACT=n

CONFIG_RCU_TRACE=n

CONFIG_PREEMPT_RCU=n

CONFIG_CLASSIC_RCU=n

CONFIG_TREE_RCU=y

3.強(qiáng)制三級節(jié)點(diǎn)樹，用于非常大型的系統(tǒng):

CONFIG_NR_CPUS=8

CONFIG_RCU_FANOUT=2

CONFIG_RCU_FANOUT_EXACT=n

CONFIG_RCU_TRACE=y

CONFIG_PREEMPT_RCU=n

CONFIG_CLASSIC_RCU=n

CONFIG_TREE_RCU=y

4.測試自動平衡：

CONFIG_NR_CPUS=8

CONFIG_RCU_FANOUT=6

CONFIG_RCU_FANOUT_EXACT=n

CONFIG_RCU_TRACE=y

CONFIG_PREEMPT_RCU=n

CONFIG_CLASSIC_RCU=n

CONFIG_TREE_RCU=y

5.測試不平衡樹：

CONFIG_NR_CPUS=8

CONFIG_RCU_FANOUT=6

CONFIG_RCU_FANOUT_EXACT=y

CONFIG_RCU_CPU_STALL_DETECTOR=y

CONFIG_RCU_TRACE=y

CONFIG_PREEMPT_RCU=n

CONFIG_CLASSIC_RCU=n

CONFIG_TREE_RCU=y

6.禁止CPU延遲檢測：

CONFIG_SMP=y

CONFIG_NO_HZ=y

CONFIG_RCU_CPU_STALL_DETECTOR=n

CONFIG_HOTPLUG_CPU=y

CONFIG_RCU_TRACE=y

CONFIG_PREEMPT_RCU=n

CONFIG_CLASSIC_RCU=n

CONFIG_TREE_RCU=y

7.禁止 CPU延遲檢測及dyntick idle 模式：

CONFIG_SMP=y

CONFIG_NO_HZ=n

CONFIG_RCU_CPU_STALL_DETECTOR=n

CONFIG_HOTPLUG_CPU=y

CONFIG_RCU_TRACE=y

CONFIG_PREEMPT_RCU=n

CONFIG_CLASSIC_RCU=n

CONFIG_TREE_RCU=y

8.禁止 CPU延遲檢測及CPU熱插撥：

CONFIG_SMP=y

CONFIG_NO_HZ=y

CONFIG_RCU_CPU_STALL_DETECTOR=n

CONFIG_HOTPLUG_CPU=n

CONFIG_RCU_TRACE=y

CONFIG_PREEMPT_RCU=n

CONFIG_CLASSIC_RCU=n

CONFIG_TREE_RCU=y

9.禁止 CPU延遲檢測，dyntick idle 模式，及CPU熱插撥：

CONFIG_SMP=y

CONFIG_NO_HZ=n

CONFIG_RCU_CPU_STALL_DETECTOR=n

CONFIG_HOTPLUG_CPU=n

CONFIG_RCU_TRACE=y

CONFIG_PREEMPT_RCU=n

CONFIG_CLASSIC_RCU=n

CONFIG_TREE_RCU=y

10.禁止SMP、CPU延遲檢測、dyntick idle 模式、及CPU熱插撥：

CONFIG_SMP=n

CONFIG_NO_HZ=n

CONFIG_RCU_CPU_STALL_DETECTOR=n

CONFIG_HOTPLUG_CPU=n

CONFIG_RCU_TRACE=y

CONFIG_PREEMPT_RCU=n

CONFIG_CLASSIC_RCU=n

CONFIG_TREE_RCU=y

這個組合有一些編譯警告。

11.禁止SMP、禁止CPU熱插撥：

CONFIG_SMP=n

CONFIG_NO_HZ=y

CONFIG_RCU_CPU_STALL_DETECTOR=y

CONFIG_HOTPLUG_CPU=n

CONFIG_RCU_TRACE=y

CONFIG_PREEMPT_RCU=n

CONFIG_CLASSIC_RCU=n

CONFIG_TREE_RCU=y

12.有dynticks idle 但是沒有搶占的情況下，測試經(jīng)典RCU：

CONFIG_NO_HZ=y

CONFIG_PREEMPT=n

CONFIG_RCU_TRACE=y

CONFIG_PREEMPT_RCU=n

CONFIG_CLASSIC_RCU=y

CONFIG_TREE_RCU=n

13.有搶占但是沒有dynticks idle時，測試經(jīng)典RCU：

CONFIG_NO_HZ=n

CONFIG_PREEMPT=y

CONFIG_RCU_TRACE=y

CONFIG_PREEMPT_RCU=n

CONFIG_CLASSIC_RCU=y

CONFIG_TREE_RCU=n

14.在dynticks idle情況下，測試可搶占RCU：

CONFIG_NO_HZ=y

CONFIG_PREEMPT=y

CONFIG_RCU_TRACE=y

CONFIG_PREEMPT_RCU=y

CONFIG_CLASSIC_RCU=n

CONFIG_TREE_RCU=n

15.在沒有 dynticks idle時，測試可搶占RCU：

CONFIG_NO_HZ=n

CONFIG_PREEMPT=y

CONFIG_RCU_TRACE=y

CONFIG_PREEMPT_RCU=y

CONFIG_CLASSIC_RCU=n

CONFIG_TREE_RCU=n

對于每一次大的影響RCU核心代碼的變化，都應(yīng)當(dāng)以上面的組合運(yùn)行rcutorture，并且在CONFIG_HOTPLUG_CPU時，并發(fā)的進(jìn)行CPU熱插撥。對小的變化，在每一種情況下運(yùn)行kernbench就行了。當(dāng)然，如果變化僅僅限于配置參數(shù)的部分子集，就可以減少測試用例的數(shù)量。

作者強(qiáng)烈推薦壓力測試軟件：Geneva Convention！

2.9.結(jié)論

這個分級RCU實(shí)現(xiàn)減少了鎖競爭，避免了不必要的喚醒dyntick-idle睡眠狀態(tài)的CPU，因此有助于調(diào)試Linux CPU熱插撥代碼。這個實(shí)現(xiàn)被設(shè)計(jì)用于處理數(shù)千個CPU的大型系統(tǒng)，并且在64位系統(tǒng)上，CPU數(shù)量限制是250，000，在今后一段時間內(nèi)，這個限制是沒有問題的。

這個RCU實(shí)現(xiàn)當(dāng)然也有一些局限：

1.force_quiescent_state()可能在關(guān)中斷下掃描整個CPU集。這在實(shí)時RCU實(shí)現(xiàn)中，是一個重大缺陷。因此，如果需要在可搶占RCU中加入分級，則需要其他方法。在4096個CPU的系統(tǒng)中，它可能會產(chǎn)生一些問題，但是需要在實(shí)際的系統(tǒng)中進(jìn)行測試以證明真的有問題。

在繁忙的系統(tǒng)中，不能指望force_quiescent_state()掃描會發(fā)生，CPU將在開始一個靜止?fàn)顟B(tài)后，在三個jiffies內(nèi)經(jīng)歷一次靜止?fàn)顟B(tài)。在半繁忙的系統(tǒng)中，僅僅處于dynticks-idle模式的CPU需要掃描。其他情況下，例如，在一個dynticks-idle CPU掃描過程中，處理一個中斷時，后繼的掃描是需要的。但是，這樣的掃描是分別在相應(yīng)的CPU上執(zhí)行的，因此相應(yīng)的調(diào)度延遲僅僅影響該掃描過程所在的CPU負(fù)載。

如果掃描被證明確實(shí)有問題，一個好的方法是進(jìn)行遞增掃描。這將稍微增加一點(diǎn)代碼復(fù)雜性，也增加一點(diǎn)結(jié)束優(yōu)雅周期的時間，但是這也確實(shí)算是一個好的方案。

2.rcu_node分級在編譯時創(chuàng)建，因此其長度是最大的CPU數(shù)量NR_CPUS。但是，即使在4，096 CPU的系統(tǒng)中，在64位系統(tǒng)上，rcu_node 分級也僅僅消耗65個緩存行。(即使在32位系統(tǒng)上包含4，096 CPUs也是這樣!)。當(dāng)然，在一個16 CPU的系統(tǒng)中，配置NR_CPUS=4096將使用一個二級樹，實(shí)際上在這種情況下，單節(jié)點(diǎn)樹也會運(yùn)行得很好。雖然這個配置會增加鎖的負(fù)載，但是實(shí)際上不會影響經(jīng)常執(zhí)行的讀端代碼，因此事實(shí)上不會有太大的問題。

3.這個補(bǔ)丁會稍微增加內(nèi)核代碼及數(shù)據(jù)尺寸：在NR_CPUS=4的系統(tǒng)中，從經(jīng)典RCU的1，757字節(jié)內(nèi)核代碼、456字節(jié)數(shù)據(jù)，共2213字節(jié)的內(nèi)核尺寸，而分級RCU則增加到4，006字節(jié)的內(nèi)核代碼、624字節(jié)的內(nèi)核數(shù)據(jù)，共計(jì)4，630字節(jié)尺寸。即使對大多數(shù)嵌入式系統(tǒng)來說，這也不是一個問題。這些系統(tǒng)通常有上百兆主內(nèi)存。但是對特別小的系統(tǒng)來說，這可能就是一個問題了，需要提供兩種類型的RCU實(shí)現(xiàn)以滿足這樣的嵌入式系統(tǒng)。不過有一個有趣的問題，在這樣的系統(tǒng)中，也許僅僅包含一個CPU，這樣的系統(tǒng)完全可以用一個特別簡單的RCU實(shí)現(xiàn)。

即使有這些問題，相對于經(jīng)典RCU來說，在數(shù)百個CPU的系統(tǒng)中，這個分級RCU實(shí)現(xiàn)仍然是一個巨大的進(jìn)步。最后需要說明一下，經(jīng)典RCU設(shè)計(jì)用于16-32個CPU的系統(tǒng)。

在某些地方，在可搶占RCU實(shí)現(xiàn)中使用分級是有必要的。

后續(xù)章節(jié)將繼續(xù)分析分級RCU的代碼，以及Linux中其他一些RCU的實(shí)現(xiàn)。也許還會討論實(shí)現(xiàn)RCU這類復(fù)雜并行軟件的開發(fā)方法及其形式化驗(yàn)證。