《LINUX3.0核心源代碼分析》第三章：核心同步(１)

摘要：本文主要講述linux如何處理ARM cortex A9多核處理器的核心同步部分。主要包括其中的記憶體屏障、原子變量、每ＣＰＵ變量。

自旋鎖、信号量、complete、讀寫自旋鎖、讀寫信号量、順序鎖、ＲＣＵ放在後文介紹。

本連載文章并不是為了形成一本适合出版的書籍，而是為了向有一定核心基本的讀者提供一些linux3.0源碼分析。是以，請讀者結合《深入了解LINUX核心》第三版閱讀本連載。

1       核心同步

1.1 記憶體屏障

Paul曾經講過：在建造大橋之前，必須得明白力學的原理。要了解記憶體屏障，首先得明白計算機硬體體系結構，特别是硬體是如何管理緩存的。緩存在多核上的一緻性問題是如何産生的。

要深入了解記憶體屏障，建議大家首先閱讀以下資料：

２、核心自帶的文檔documentation/memory-barriers.txt．

記憶體屏障是如此難此了解也難以使用，為什麼還需要它呢？硬體工程師為什麼不給軟體開發者提供一種程式邏輯一緻性的記憶體視圖呢？歸根結底，這個問題受到光速的影響。在１.８Ｇ的主頻系統中，在一個時鐘周期内，光在真空中的傳播距離隻有幾厘米，電子的傳播距離更短，根本無法傳播到整個系統中。

Linux為開發者實作了以下記憶體屏障：

名稱

函數名

作用

讀寫屏障

mb

在多核和ＩＯ記憶體、緩存之間設定一個完全讀寫屏障

讀屏障

rmb

在多核和ＩＯ記憶體、緩存之間設定一個讀屏障

寫屏障

wmb

在多核和ＩＯ記憶體、緩存之間設定一個寫屏障

讀依賴屏障

read_barrier_depends

在多核和ＩＯ記憶體、緩存之間設定一個讀依賴屏障

多核讀寫屏障

Smp_mb

在多核之間設定一個完全讀寫屏障

多核讀屏障

Smp_rmb

在多核之間設定一個讀屏障

多核寫屏障

Smp_wmb

在多核之間設定一個寫屏障

多核讀依賴屏障

Smp_read_barrier_depends

在多核之間設定一個讀依賴屏障

按照linux設計，mb、rmb、wmb、read_barrier_depends主要用于ＣＰＵ與外設ＩＯ之間。在arm及其他一些RISC系統中，通常将外設ＩＯ位址映射為一段記憶體位址。雖然這樣的記憶體是非緩存的，但是仍然受到記憶體讀寫亂序的影響。例如，我們要讀寫一個外部ＩＯ端口的資料時，可能會先向某個寄存器寫入一個要讀寫的端口号，再讀取另一個端口得到其值。如果要讀取值之前，設定的端口号還沒有到達外設，那麼通常讀取的資料是不可靠的，有時甚至會損壞硬體。這種情況下，需要在讀寄存器前，設定一個記憶體屏障，保證二次操作外部端口之間沒有亂序。

Smp_mb、smp_rmb、smp_wmb僅僅用于ＳＭＰ系統，它解決的是多核之間記憶體亂序的問題。其具體用法及原理，請參閱《深入了解并行程式設計》。

read_barrier_depends和smp_ read_barrier_depends是讀依賴屏障。除了在DEC alpha架構外，linux支援的其他均不需要這個屏障。Alpha需要它，是因為alpha架構中，使用的緩存是split cache．所謂split cache，簡單的說就是一個核的緩存不止一個．在arm架構下，我們可以簡單的忽略這個屏障。

雖然linux分讀寫屏障、讀屏障、寫屏障，但是在ARM中，它們的實作都是一樣的，沒有嚴格差別不同的屏障。

記憶體屏障也隐含了編譯屏障的作用。所謂編譯屏障，是為了解決編譯亂序的問題。這個問題的根源在于：在發明編譯器的時候，多核還未出現。編譯器開發者認為編譯出來的二進制代碼隻要在單核上運作正确就可以了。甚至，隻要保證單線程内的程式邏輯正确性即可。例如，我們有兩句指派語句：

A = 1;

B = 2;

編譯器并不保證生成的彙編是按照Ｃ語句的順序。為了效率或者其他原因，它生成的彙編語句可能與下面的Ｃ代碼是一緻的：

要防止編譯亂序，可以使用編譯屏障指令barrier();

1.2 不是題外話的題外話

在描述原子變量和每ＣＰＵ變量、其他核心同步方法之前，我們先看一段代碼。假設有兩個線程Ａ和線程Ｂ，它們的執行代碼分别是foo_a、foo_b，它們都操作一個全局變量g_a，如下：

Unsigned long g_a;

Int stoped = 0;

Void foo_a(void *unused)

{

         While (stopped == 0)

         {

G_a++;

}

Void foo_b(void *unused)

假設當stopped被設定為１後，線程Ａ和線程Ｂ執行了count_a、count_b次，您會認為g_a的值等于count_a + count_b嗎？

恩，當您在一台真實的計算上測試這個程式的時候，也許您的直覺是對的，g_a的值确實等于count_a + count_b。

但是，請您：

１、将測試程式運作的時間運作得久一點

２、或者将程式放到arm、powerpc或者mips上運作

３、或者找一台運作linux的多核x86機器運作。

g_a的值還會等于count_a + count_b嗎？

答案是不會。

原因是什麼呢？

産生這個問題的根本原因是：

１、             在多核上，一個ＣＰＵ在向記憶體寫入資料時，它并不知道其他核在向同樣的記憶體位址寫入。某一個核寫入的資料可能會覆寫其他核寫入的資料。假說g_a目前值是０，那麼線程Ａ和線程Ｂ同時讀取它的值，當記憶體中的值放入總線上後，兩個線程都認為其值是０.并同時将其值加１後送出給總線并向記憶體中寫入１.其中一個線程對g_a的遞增被丢失了。

２、             Arm、powerpc、mips這些體系結構都是存儲/加載體系結構，它們不能直接對記憶體中的值進行操作。而必須将記憶體中的值加載到寄存器中後，将寄存器中的值加１後，再存儲到記憶體中。如果兩個線程都讀取０值到寄存器中，并将寄存器的值遞增為１後存儲到記憶體，那麼也會丢失一次遞增。

３、             即使在x86體系結構中，允許直接對記憶體進行遞增操作。也會由于編譯器的原因，将記憶體中的值加載到記憶體，同第二點，也可能造成丢失一次遞增。

怎麼解決這個問題呢？

聰明的讀者會說了：是不是需要這樣聲明g_a？

Unsigned long volatile g_a;

更聰明的讀者會說，在寫g_a時還需要鎖住總線，使用彙編語句并在彙編前加lock字首。

鎖總線是正确的，但是也必須将g_a聲明為valatile類型的變量。可是，在我們分析的ＡＲＭ多核上，應該怎麼辦？

1.3 原子變量

原子變量就是為了解決我們遇到的問題：如果在共享記憶體的多核系統上正确的修改共享變量的計數值。

首先，我們看一下老版本是如何定義原子變量的：

/**

 * 将counter聲明成volatile是為了防止編譯器優化,強制從記憶體中讀取counter的值

 */

typedef struct { volatile int counter; } atomic_t;

在linux3.0中，已經有所變化：

typedef struct {

         int counter;

} atomic_t;

已經沒有volatile來定義counter了。難道不需要禁止編譯優化了嗎？答案不是的。這是因為linux3.0已經修改了原子變量相關的函數。

Linux中的基本原子操作

宏或者函數

說明

Atomic_read

傳回原子變量的值

Atomic_set

設定原子變量的值。

Atomic_add

原子的遞增計數的值。

Atomic_sub

原子的遞減計數的值。

atomic_cmpxchg

原子比較并交換計數值。

atomic_clear_mask

原子的清除掩碼。

除此以外，還有一組操作64位原子變量的變體，以及一些位操作宏及函數。這裡不再羅列。

 * 傳回原子變量的值。

 * 這裡強制将counter轉換為volatile int并取其值。目的就是為了避免編譯優化。

#define atomic_read(v)   (*(volatile int *)&(v)->counter)

 * 設定原子變量的值。

#define atomic_set(v,i)    (((v)->counter) = (i))

原子遞增的實作比較精妙，了解它的關鍵是需要明白ldrex、strex這一對指令的含義。

 * 原子的遞增計數的值。

static inline void atomic_add(int i, atomic_t *v)

         unsigned long tmp;

         int result;

         /**

          * __volatile__是為了防止編譯器亂序。與"#define atomic_read(v)          (*(volatile int *)&(v)->counter)"中的volatile類似。

          */

         __asm__ __volatile__("@ atomic_add\n"

          * ldrex是arm為了支援多核引入的新指令，表示"排它性"加載。與mips的ll指令一樣的效果。

          * 它與"排它性"存儲配對使用。

"1:    ldrex         %0, [%3]\n"

          * 原子變量的值已經加載到寄存器中，這裡對寄存器中的值減去指定的值。

"       add  %0, %0, %4\n"

          * strex是"排它性"的存儲寄存器的值到記憶體中。類似于mips的sc指令。

"       strex         %1, %0, [%3]\n"

          * 關鍵代碼是這裡的判斷。如果在ldrex和strex之間，其他核沒有對原子變量變量進行加載存儲操作，

          * 那麼寄存器中值就是０，否則非０.

"       teq   %1, #0\n"

          * 如果其他核與本核沖突，那麼寄存器值為非０，這裡跳轉到标号１處，重新加載記憶體的值并遞增其值。

"       bne  1b"

         : "=&r" (result), "=&r" (tmp), "+Qo" (v->counter)

         : "r" (&v->counter), "Ir" (i)

         : "cc");

atomic_add_return遞增原子變量的值，并傳回它的新值。它與atomic_add的最大不同，在于在原子遞增前後各增加了一句：smp_mb();

這是由linux原子操作函數的語義規定的：所有對原子變量的操作，如果需要向調用者傳回結果，那麼就需要增加多核記憶體屏障的語義。通俗的說，就是其他核看到本核對原子變量的操作結果時，本核在原子變量前的操作對其他核也是可見的。

了解了atomic_add，其他原子變量的實作也就容易了解了。這裡不再詳述。

1.4 每ＣＰＵ變量

原子變量是不是很棒？無論有多少個核，每個核都可以修改共享記憶體變量，并且這樣的修改可以被其他核立即看到。多核程式設計原來so easy！

不過還是不能太高興了，原子變量雖然不是毒瘤，但是也差不多了。我曾經遇到一個兄弟，工作十多年了吧，得意的吹噓：“我寫的代碼精細得很，統計計數都是用的彙編實作的，彙編加法指令還用了lock字首。”嗚呼，這個兄弟完全沒有意識到在x86體系結構中，這個lock字首對性能的影響。

不管哪種架構，原子計數（包含原子比較并交換）都是極耗ＣＰＵ的。與單純的加減計數指令相比，它消耗的ＣＰＵ周期要高一到兩個數量級。原因是什麼呢？還是光信号（電信号）的傳播速度問題。要讓某個核上的修改被其他核發現，需要信号在整個系統中進行傳播。這在幾個核的系統中，可能還不是大問題，但是在１０２４個核以上的系統中呢？比如我們熟知的天河系統。

為了解決這個問題，核心引用入了每ＣＰＵ變量。

可以将它了解為資料結構的數組。系統的每個CPU對應數組中的一個元素。每個ＣＰＵ都隻通路本ＣＰＵ對應的數組元素。

每ＣＰＵ數組中，確定每一個數組元素都位于不同的緩存行中。假如您有一個int型的每ＣＰＵ數組，那麼每個int型都會占用一個緩存行（很多系統中一個緩存行是３２個位元組），這看起來有點浪費。這樣做的原因是：

ü  對每CPU數組的并發通路不會導緻高速緩存行的失效。避免在各個核之間引起緩存行的抖動。

ü  這也是為了避免出現多核之間資料覆寫的情況。對這一點，可能您暫時不能了解。也許您在核心領域實際工作幾年，也會覺得這有點難于了解。不過，現在您隻需要知道有這麼一個事實存在就行了。

關于第二個原因，您可以參考一個核心更新檔：

99dcc3e5a94ed491fbef402831d8c0bbb267f995。據送出更新檔的兄弟講，這個更新檔表面是一個性能優化的措施。但是，它實際上是一個ＢＵＧ。該故障會引起核心記憶體配置設定子系統的一個ＢＵＧ，最終會引起記憶體配置設定子系統陷入死循環。我實際的遇到了這個故障，可憐了我的兩位兄弟，為了解決這個故障，花了近兩個月時間，今天終于被我搞定了。

每CPU變量的主要目的是對多CPU并發通路的保護。但是它不能防止同一核上的中斷的影響。我們曾經講過，在arm、mips等系統中，++、--這樣的簡單計數操作，都需要幾條彙編語句來完成。如果在從記憶體中加載資料到寄存器後，還沒有将資料儲存到記憶體中前，有中斷将操作過程打斷，并在中斷處理函數中對同樣的計數值進行操作，那麼中斷中的操作将被覆寫。

不管在多CPU還是單CPU中，核心搶占都可能象中斷那樣破壞我們對計數的操作。是以，應當在禁用搶占的情況下通路每CPU變量。核心搶占是一個大的話題，我們在講排程的時候再提這個事情。

相關宏和函數：

DEFINE_PER_CPU

靜态定義一個每ＣＰＵ變量數組

per_cpu

獲得每CPU數組中某個ＣＰＵ對應的元素

__this_cpu_ptr

獲得目前ＣＰＵ在數組中的元素的指針。

__get_cpu_var

獲得目前ＣＰＵ在數組中的元素的值。

get_cpu_ptr

關搶占，并獲得ＣＰＵ對應的元素指針。

put_cpu_var

開搶占，與get_cpu_ptr配對使用。

看到這裡，也許大家會覺得，用每ＣＰＵ變量來代替原子變量不是很好麼？不過，存在的東西就必然在存在的理由，因為每ＣＰＵ變量用于計數有一個緻使的弊端：它是不精确的。我們設想：有３２個核的系統，每個核更新自己的ＣＰＵ計數，如果有一個核想知道計數總和怎麼辦？簡單的用一個循環将計數加起來嗎？這顯然是不行的。因為某個核修改了自己的計數變量時，其他核不能立即看到它對這個核的計數進行的修改。這會導緻計數總和不準。特别是某個核對計數進行了大的修改的時候，總計數看起來會嚴重不準。

為了使總和大緻可信，核心又引入了<b>另一種</b>每ＣＰＵ變量：percpu_counter。

percpu_counter的詳細實作在percpu_counter.c中。有興趣的同學可以研究一下。下面我們講一個主要的函數，希望起個抛磚引玉的作用：

* 增加每ＣＰＵ變量計數

*            fbc:            要增加的每ＣＰＵ變量

*            amount:   本次要增加的計數值

*            batch:       當本ＣＰＵ計數超過此值時，要確定其他核能及時看到。　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

*/

void __percpu_counter_add(struct percpu_counter *fbc, s64 amount, s32 batch)

         s64 count;

* 為了避免目前任務飄移到其他核上，或者被其他核搶占，導緻計數丢失

* 這裡需要關搶占。

         preempt_disable();

     * 獲得本ＣＰＵ計數值并加上計數值。

     */

         count = __this_cpu_read(*fbc-&gt;counters) + amount;

         if (count &gt;= batch || count 本次修改的值較大，需要同步到全局計數中 */

                   spin_lock(&amp;fbc-&gt;lock);/* 獲得自旋鎖，這樣可以避免多核同時更新全局計數。 */

                   fbc-&gt;count += count;/* 修改全局計數，并将本ＣＰＵ計數清０ */

                   __this_cpu_write(*fbc-&gt;counters, 0);

                   spin_unlock(&amp;fbc-&gt;lock);

         } else {

                   __this_cpu_write(*fbc-&gt;counters, count);/* 本次修改的計數較小，僅僅更新本ＣＰＵ計數。 */

         }

         preempt_enable();/* 打開搶占 */

大家現在覺得多核程式設計有那麼一點難了吧？一個簡單的計數都可以搞得這麼複雜。

複雜的東西還在後面。接下來我們新開一帖，讨論核心同步的其他技術：自旋鎖、信号量、ＲＣＵ、無鎖程式設計。