1、準備工作

本文基于linux 2.6.32-rc7版本的源碼， 因此請準備一份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更早版本中的經典RCU，其讀端原語擁有出色的性能和擴展性，但是寫端原語則需要判斷預先存在的讀端臨界區(qū)在什么時候完成，它僅僅被設計用于數(shù)十個CPU的系統(tǒng)。經典RCU的實現(xiàn)，要求在每個優(yōu)雅周期內，每個CPU必須獲取一個全局鎖，這使得它們的擴展性受到了限制。雖然在實際生產系統(tǒng)中，經典RCU可以運行在幾百個CPU的系統(tǒng)中，甚至能夠比較困難的使用到上千個 CPU的系統(tǒng)中，但是大型多核系統(tǒng)仍然需要更好的擴展性。

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

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

2.1.RCU基礎回顧

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

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

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

2.2.經典RCU實現(xiàn)概要

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

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

2.3.RCU 迫切要解決的問題

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

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

2. 可靠性，這樣RCU支持24x7運行。

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

4. 包含內存標記，這樣，如果有很多回調過程，這種機制將加快結束優(yōu)雅周期。

5. 獨立的內存塊，這樣RCU能夠基于可信的內存分配器進行工作。

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

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

8. 兼容的API。

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

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

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

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

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

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

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

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

最急迫的首要需求是：可擴展性。因此需要減少RCU的內部鎖。

2.4.邁向可擴展RCU實現(xiàn)

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

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

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

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

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

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

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

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

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

2.6.狀態(tài)機

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

1、每一次進程切換

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

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

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

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

2.7.用例

這些事件驅動的用例包括：

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

2.經歷一個靜止狀態(tài)

3.向RCU通告一個靜止狀態(tài)

4.進入、退出Dynticks Idle 模式

5.從Dynticks Idle 模式進入中斷

6.從 Dynticks Idle 模式進入NMI

7.標記一個CPU處于Dynticks Idle 模式

8.CPU離線

9.CPU上線

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

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

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

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

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

2.7.2.經歷一次靜止狀態(tài)

rcu和rcu_bh有各自的靜止狀態(tài)集合。

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

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

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

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

2.7.3.向RCU宣告一次靜止狀態(tài)

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

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

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

3.向RCU核心機制報告當前CPU的靜止狀態(tài)。(通過 rcu_check_quiescent_state()，它會調用 cpu_quiet())。當然，這個過程也會標記當前的優(yōu)雅周期結束。

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

5.當優(yōu)雅周期結束時，調用這個CPU的回調 (通過 rcu_do_batch())。

這些接口都經過精心實現(xiàn)，以避免BUG，如：錯誤的從上一個優(yōu)雅周期向當前優(yōu)雅周期報告靜止狀態(tài)這樣的BUG。

2.7.4.進入和退出 Dynticks Idle模式

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

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

2.7.5.從Dynticks Idle 模式進入中斷

從dynticks idle 模式進入中斷由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ù)值)。

注意：進入中斷會處理退出dynticks idle模式，反之也一樣。進入、退出之間不一致可能導致一些混亂，不用警告你也應該想得到這一點。

2.7.6.從Dynticks Idle 模式進入NMI

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

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

2.7.7.標記CPU處于Dynticks Idle模式

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

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

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

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

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

2.7.8.CPU離線

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

2.7.9.CPU上線

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

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

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

2.8.測試

RCU是基本的同步代碼，因此RCU的錯誤導致的后果是隨機的、難于調試的內存錯誤。因此，高可靠的RCU是非常重要的。這些可靠性來自于小心的設計，但是最終還是需要依賴于高強度的壓力測試。

幸運的是，雖然有一些關于覆蓋性方面的爭論，但是仍然可以對軟件進行一些壓力測試。實際上，進行這些測試是被強烈建議的，因為不對你的軟件進行折磨性測試的話，它就會反過來折磨你，這種折磨來自于：它在不合時宜的時候崩潰掉。

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

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

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

1.CONFIG_CLASSIC_RCU：經典 RCU。

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

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

4.CONFIG_RCU_FANOUT：每一個rcu_node 的子結點數(shù)量。

5.CONFIG_RCU_FANOUT_EXACT：平衡rcu_node 樹。

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

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

8.CONFIG_SMP：打開 multi-CPU選項。

9.CONFIG_RCU_CPU_STALL_DETECTOR：當CPU進入擴展靜止狀態(tài)時進行RCU檢測。

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

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

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

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

1.單結點“tree”。

2.兩級平衡樹。

3.三級平衡樹。

4.自動平衡樹，當 CONFIG_RCU_FANOUT 指定一個不平衡樹，但是沒有配置CONFIG_RCU_FANOUT_EXACT 時，進行自動平衡。

5.非平衡樹。

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

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

CONFIG_RCU_TORTURE_TEST=m

CONFIG_MODULE_UNLOAD=y

CONFIG_SUSPEND=n

CONFIG_HIBERNATION=n

15個測試用例如下：

1.強制單節(jié)點“樹”，用于小型系統(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.強制兩級節(jié)點樹用于大型系統(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.強制三級節(jié)點樹，用于非常大型的系統(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 但是沒有搶占的情況下，測試經典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時，測試經典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核心代碼的變化，都應當以上面的組合運行rcutorture，并且在CONFIG_HOTPLUG_CPU時，并發(fā)的進行CPU熱插撥。對小的變化，在每一種情況下運行kernbench就行了。當然，如果變化僅僅限于配置參數(shù)的部分子集，就可以減少測試用例的數(shù)量。

作者強烈推薦壓力測試軟件：Geneva Convention！

2.9.結論

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

這個RCU實現(xiàn)當然也有一些局限：

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

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

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

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也是這樣!)。當然，在一個16 CPU的系統(tǒng)中，配置NR_CPUS=4096將使用一個二級樹，實際上在這種情況下，單節(jié)點樹也會運行得很好。雖然這個配置會增加鎖的負載，但是實際上不會影響經常執(zhí)行的讀端代碼，因此事實上不會有太大的問題。

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

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

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

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