RCU鎖在Linux核心的演變

2.6核心引入了RCU鎖，這種鎖十分高效，總的說來就是讀時加鎖，寫時拷貝，讀後更新。具體的流程可以參照 rcu的相關文件。本文主要談一下rcu在Linux2.6核心的演變過程，它分別經歷了三個階段，分別是傳統rcu鎖，可搶佔rcu鎖以及2.6.29 中將要引入的樹形分層rcu鎖。

Linux中最早引入的rcu鎖十分的粗糙，實現原理也是非常簡單，畢竟Linux中不管多複雜的機制一開始的時候都是十分簡單的，這一點可以看看 Linux0.01到Linux2.6.28的演變。傳統的rcu鎖就是在有讀者讀資料的時候加上rcu鎖，注意這裡的“加鎖”僅僅是邏輯意義上的加鎖， 至於真正實現可以很靈活，實際上Linux的實現就沒有用到所謂的鎖，而是簡單的禁用搶占。為何可以這麼實現呢？因為在一個cpu上禁用了搶占也就禁用了 這個cpu上的進程切換，該cpu上的當前進程將一直執行，除非重新使能搶占，那麼什麼時候使能搶占呢？當然是在讀者釋放rcu鎖的時候了，而Linux 中傳統rcu實現規定在進程切換的時候才會執行更新回撥函數，這就是本質。每當一個cpu經歷進程上下文切換時，rcu就說此cpu經過了一個 quiescent state，而所有的cpu都經過一個quiescent state的時間稱為一個grace period，在這個grace period點之後，該grace period的更新回撥函數就可以被安全的執行了，因為此時，系統已經確定所有的讀者都不再持有rcu鎖了。我們再次理一下這是為什麼，讀者釋放鎖就是使 能搶占，也就是可以切換進程，而且換進程的時候rcu就認為經過了一個quiescent state，所有的cpu都經過了一個quiescent state意味著所有的cpu都可以進程切換了，就是意味著所有的cpu上的讀者都不再持有rcu鎖了。就是這麼簡單，但是我們看一下這個實現會存在什麼 問題，只要讀者加鎖，就意味著禁用搶佔，就是禁止切換，這會很大地減低系統的互動效能，當然也會降低實時任務的效能，這一切都不是想要的，單獨一個rcu 把大家都拖下水實在不應該，難道要為了保護讀者保護的資料而凍住整個系統不讓切換進程嗎？傳統的rcu不允許佔有rcu的進程睡眠，睡眠了進程又不允許切 換，系統就相當於死掉了。於是下一個版本的rcu就要出來了，它試圖將rcu對系統的影響減小到最小，也就是說將rcu單獨做成一個可以自洽自治的模組， 它本身就可以處理好資料的保護而不再需要通過系統其它的機制來確保rcu讀者資料在允許更新前被保護，這就是preemptible-RCU鎖。其實 Linux最開始引入的所謂傳統的rcu鎖是一個很失敗的實現，作業系統的任務就是管理各種複雜的模組以模擬真實世界，優秀的作業系統可以做到模組化的管 理各種機制，比如進程，記憶體，裝置，以及各種鎖和併行機制等等，在管理它們的時候各個模組低耦合地通訊而不至於互相依賴互相影響效能，如果說要想不出問 題，最簡單也是最失敗的方式就是只讓一個進程跑，沒有切換沒有共用當然也就沒有了競爭，沒有競爭也就意味著沒有競態，也就意味著沒有了並行問題，這很簡 單，但是很不靈活，也讓人感覺到這不是一個優秀的作業系統，就好像人不能說怕淋雨就不出門，正確的解決方案就是發明出雨傘和雨衣。Linux第一代rcu 就是這種很差勁的實現。

既然第二代rcu是preemptible的rcu，那麼就是說在持有rcu鎖期間不再需要禁用搶佔了，這個實現看到這裡就知道它是一個很優秀的實現，因 為它不再需要搶占機制幫忙來實現資料保護，rcu的內部機制已經可以實現資料保護了。那麼它是怎麼實現的呢？如果你不想用別的機制實現rcu資料保護，那 麼就要自己實現，當然代價就是引入新的資料結構和邏輯控制機制，在preemptible-rcu中，一個grace period被分解為了兩個階段而不是所有cpu完成quiescent state了所有的資料保護機制都是在這兩個階段大做文章而實現的。這兩個階段通過一系列的軟體計數器來實現了rcu，之所以分為兩個階段是因為rcu有 lock和unlock兩個動作，我們能不能像實現傳統rcu一樣，不用真正的鎖就實現邏輯上的rcu鎖呢？當然可以了，引入一個每cpu變數：

#define GP_STAGES    2
struct rcu_data {
        spinlock_t      lock;          //保護此結構中欄位的自旋鎖
        long            completed;      //總的階段計數器
        int            waitlistcount;
        struct rcu_head *nextlist;    //一些連結串列，記錄更新回撥函數
        struct rcu_head **nexttail;
        struct rcu_head *waitlist[GP_STAGES];
        struct rcu_head **waittail[GP_STAGES];
        struct rcu_head *donelist;     
        struct rcu_head **donetail;
        long rcu_flipctr[2];        //這個很重要
        struct rcu_head *nextschedlist;
        struct rcu_head **nextschedtail;
        struct rcu_head *waitschedlist;
        struct rcu_head **waitschedtail;
        int rcu_sched_sleeping;
};
rcu_flipctr 這個欄位十分重要，它是一個陣列，每個元素其實就是一個計數器，第一個元素記錄的是在本階段中的本cpu的rcu鎖持有者數量，而第二個元素表示上個階段 的還沒有釋放的本cpu的rcu鎖數量，注意，只有unlock操作可以遞減第二個元素，lock操作只能遞增第一個元素，另外unlock操作也可以遞 減第一個元素，一旦所有cpu的第二個元素的和變為0了，那麼就可以向前推進一個階段了，在下一個階段中，第一個元素成了只有unlock才能遞減的元 素，而第二個元素lock和unlock都可觸及，記錄著當前階段的新rcu鎖數量，往下依次類推。每個階段都要等待所有cpu的rcu_flipctr 的同一個元素的和成為0，然後進入下一個階段，進入下一個階段同時交換rcu_flipctr的兩個元素的意義。系統維持一個狀態機，為rcu設定了好幾 種狀態，其中包括一個等待所有cpu的前一個階段的rcu計數器降到0的狀態，這一個狀態過去以後，rcu狀態機就可以向前推進一個階段了，注意，可搶佔 的rcu鎖機制的重點執行點不再是grace period，而是一個grace period的兩個階段，可搶佔的rcu鎖也是以階段為基準的，也就是說，在每一個階段結束時都會有一個計數器的和降為0，這時同步將這個計數器對應的回 調函數連結串列推進到最前面，然後就可以安全地執行這些更新回撥函數了，這裡執行回撥函數連結串列的時間是每個階段結束，而不必等到一個grace period的第二個階段結束時。原先的傳統rcu的實現在機進程切換時更新quiescent state狀態然後判斷是否過了一個grace period，現在的可搶佔的rcu中，僅在時鐘中斷裡面執行rcu狀態機，狀態機根據其前一個狀態和當前的rcu狀態採取不同的措施以維持狀態機繼續運 轉，這麼看來可搶佔的rcu就和搶佔沒有關係了，cpu可以隨便被搶占而不會破壞rcu讀者保護的資料，於是就說rcu模組和搶佔模組解耦合了，各自可以 通過各自的方式進行設計，偵錯，優化以提高效能而不用像原來那樣互相依賴雜糅在一起。
我們看一下lock和unlock函數：
void __rcu_read_lock(void)
{
...
        } else {
                unsigned long flags;
                local_irq_save(flags);
                idx = ACCESS_ONCE(rcu_ctrlblk.completed) & 0x1;
                ACCESS_ONCE(RCU_DATA_ME()->rcu_flipctr[idx])++;
                ACCESS_ONCE(t->rcu_read_lock_nesting) = nesting + 1;
                ACCESS_ONCE(t->rcu_flipctr_idx) = idx;
                local_irq_restore(flags);
        }
}
void __rcu_read_unlock(void)
{
...
        } else {
                unsigned long flags;
                local_irq_save(flags);
                idx = ACCESS_ONCE(t->rcu_flipctr_idx);
                ACCESS_ONCE(t->rcu_read_lock_nesting) = nesting - 1;
                ACCESS_ONCE(RCU_DATA_ME()->rcu_flipctr[idx])--;
                local_irq_restore(flags);
        }
}
然後看一幅圖：

另外linux絕對不會放過任何可以優化的空間的，只要能節省一條指令的執行，那麼linux核心就會認為這麼做就是值得的，比如在可搶佔的rcu中，有兩個函數：
void rcu_irq_enter(void)
{
        int cpu = smp_processor_id();
        struct rcu_dyntick_sched *rdssp = &per_cpu(rcu_dyntick_sched, cpu);
        if (per_cpu(rcu_update_flag, cpu))
                per_cpu(rcu_update_flag, cpu)++;
        if (!in_interrupt() && (rdssp->dynticks & 0x1) == 0) {
                rdssp->dynticks++;
                smp_mb();
                per_cpu(rcu_update_flag, cpu)++;
        }
}
void rcu_irq_exit(void)
{
        int cpu = smp_processor_id();
        struct rcu_dyntick_sched *rdssp = &per_cpu(rcu_dyntick_sched, cpu);
        if (per_cpu(rcu_update_flag, cpu)) {
                if (--per_cpu(rcu_update_flag, cpu))
                        return;
                WARN_ON(in_interrupt());
                smp_mb();
                rdssp->dynticks++;
                WARN_ON(rdssp->dynticks & 0x1);
        }
}
注 意有一個dynticks，它在進入irq和出去irq的時候都會遞增，它被初始化為1，但是更要注意，這種遞增是有條件的，比如在 rcu_irq_enter中，這個dynticks遞增的條件就是中斷非巢狀並且dynticks為偶數，顯然第一次進入中斷時dynticks不可能 為偶數，這就是說dynticks應該第一次在rcu_irq_exit中被增加，其實這個小演算法的意義就是在進入nohz的時候或者停掉時鐘節拍的時 候，當事cpu就沒有必要按照常規的更新自己-通知他人-等待他人的方式維持狀態機了，而是直接忽略當事cpu，按照應該的方式直接將該cpu向前推進， 這樣的話就免去了很多操作，在實現這個小演算法的時候，巧妙地利用了奇數偶數的方式，判斷上減少了很多條指令，具體不多說，最後看一眼下面的利用 dynticks的函數：
static inline int rcu_try_flip_waitack_needed(int cpu)
{
        long curr;
        long snap;
        struct rcu_dyntick_sched *rdssp = &per_cpu(rcu_dyntick_sched, cpu);
        curr = rdssp->dynticks;
        snap = rdssp->dynticks_snap;
        smp_mb();
        if ((curr == snap) && ((curr & 0x1) == 0))
                return 0;
        if ((curr - snap) > 2 || (curr & 0x1) == 0)
                return 0;
        return 1;
}
以上就是第二代的可搶佔的rcu的思想和框架，那麼第三代的rcu在那些方面有所創新呢？雖然第三代的rcu還沒有被合進2.6.28核心，準備合入 2.6.29核心，但是Changelog中已經描述地很清晰了，它的主體思想就是：One effective way to reduce lock contention is to create a hierarchy.這句話真的要仔細推敲，這涉及到一個設計思想問題。分散式的對等結構是趨勢嗎？這麼看來這句話就是大錯特錯了，但是分級管理確實可以 省很多事，這樣分級正確的話，對等結構豈不是錯誤的結構嗎？因此這個問題很有意義。國家機器應該是何種結構呢？金字塔式的等級政府合理嗎？第三代的rcu 稱為樹形rcu，它採用了樹結構，將鎖定定義為一個分層分級的操作。這就類似於百米賽跑選拔過程，如果一共有50個人參加，那麼有兩種方式可以進行選拔， 一個是50個人同時上場，這樣的話消耗巨大，另外就是分批分組選拔，這樣的話消耗很小，分批分組其實就是分級選拔，將50個人分為25組，每組2人，這樣 的話同時只有2人比賽，而且25組不必在一個場地上。樹形的rcu就是這麼乾的，把所有的cpu分組，每組2個或多於2個，這樣同時競爭rcu鎖的cpu 就會減少很多，低階組的贏家競爭更高一級的rcu，然後贏家繼續類似的競爭。見下面的幾幅圖：

在上面的圖中，6個cpu分為3組，每兩個同時競爭，之後贏了的3個再競爭，避免了6個同時競爭。

上面的圖就不多說了。在存在大量cpu的機器上，難道要把cpu們分為很多組，必須兩個一組嗎？沒有必要，兩個一組當然可以，但是那是教條，實際上文件上講64個cpu同時競爭鎖的情形下所測試得到的效能是很不錯的，因此上面的圖示所示的兩兩分組的方式實屬為了說明問題而設，樹形rcu的真正用武之地不是少量cpu的機器而是大量，也就是成千cpu的巨猛機器，這些是我接觸不到的，因此我只談思想而沒有任何實戰經驗。如果為了運用樹形rcu而在擁有少量cpu的機器上實施的話，那麼勢必會因為樹形複雜的結構而佔用大量的記憶體空間，所得到的益處不能補償其帶來的弊端，因此一味追求新技術是不對的，必須了解這種新技術最適合的場合再作考慮，考慮好是用時間換空間還是用空間換時間，自己的系統是空間重要還是時間重要。

另外樹形的rcu也實現了節能機制，同樣利用可搶佔rcu的奇數偶數小演算法技巧實現，這樣持有偶數計數器的cpu就不必被喚醒以維持狀態機，因為持有偶數計數器的cpu處的狀態是時鐘節拍停止（nohz），或者掛起狀態，這樣就減少了不必要的能源消耗，可謂不錯。

其實，樹形的分層結構不但可以實現rcu，任何鎖都可以用樹形結構實現，樹形鎖的關鍵在於它可以減少同時競爭鎖的cpu的數量，從而避免過多的競態。.第 一代rcu在Linux上實現表明了Linux可以實現這個古老的鎖機制;第二代的可搶佔的rcu說明了一個優秀的機制可以作為一個模組脫離別的機制獨立 存在,並且活得很好;第三代的樹形rcu表明在實施上,分散式的對等結構是不錯的,在管理上有時分層的等級結構是必要的,畢竟實施的時候實體很多很不確 定,分散式對等結構可以增加系統的對稱性提高效率,但是管理的時候實體很確定,工作很明確,分層的等級結構帶來的是更有條理,管理更有效。

本文永久更新連結地址：http://www.linuxidc.com/Linux/2015-07/120042.htm