linux記憶體屏障淺析

記憶體屏障是一個很神奇的東西，之前翻譯了linux核心文檔memory-barriers.txt，對記憶體屏障有了一定有了解。現在用自己的方式來整理一下。

在我看來，記憶體屏障主要解決了兩個問題：單處理器下的亂序問題和多處理器下的記憶體同步問題。

為什麼會亂序

現在的cpu一般采用流水線來執行指令。一個指令的執行被分成：取指、譯碼、訪存、執行、寫回、等若幹個階段。然後，多條指令可以同時存在于流水線中，同時被執行。

指令流水線并不是串行的，并不會因為一個耗時很長的指令在“執行”階段呆很長時間，而導緻後續的指令都卡在“執行”之前的階段上。

相反，流水線是并行的，多個指令可以同時處于同一個階段，隻要cpu内部相應的處理部件未被占滿即可。比如說cpu有一個加法器和一個除法器，那麼一條加法指令和一條除法指令就可能同時處于“執行”階段, 而兩條加法指令在“執行”階段就隻能串行工作。

相比于串行+阻塞的方式，流水線像這樣并行的工作，效率是非常高的。

然而，這樣一來，亂序可能就産生了。比如一條加法指令原本出現在一條除法指令的後面，但是由于除法的執行時間很長，在它執行完之前，加法可能先執行完了。再比如兩條訪存指令，可能由于第二條指令命中了cache而導緻它先于第一條指令完成。

一般情況下，指令亂序并不是cpu在執行指令之前刻意去調整順序。cpu總是順序的去記憶體裡面取指令，然後将其順序的放入指令流水線。但是指令執行時的各種條件，指令與指令之間的互相影響，可能導緻順序放入流水線的指令，最終亂序執行完成。這就是所謂的“順序流入，亂序流出”。

指令流水線除了在資源不足的情況下會卡住之外（如前所述的一個加法器應付兩條加法指令的情況），指令之間的相關性也是導緻流水線阻塞的重要原因。

cpu的亂序執行并不是任意的亂序，而是以保證程式上下文因果關系為前提的。有了這個前提，cpu執行的正确性才有保證。比如：

a++; b=f(a); c--;

由于b=f(a)這條指令依賴于前一條指令a++的執行結果，是以b=f(a)将在“執行”階段之前被阻塞，直到a++的執行結果被生成出來；而c--跟前面沒有依賴，它可能在b=f(a)之前就能執行完。（注意，這裡的f(a)并不代表一個以a為參數的函數調用，而是代表以a為操作數的指令。c語言的函數調用是需要若幹條指令才能實作的，情況要更複雜些。）

像這樣有依賴關系的指令如果挨得很近，後一條指令必定會因為等待前一條執行的結果，而在流水線中阻塞很久，占用流水線的資源。而編譯器的亂序，作為編譯優化的一種手段，則試圖通過指令重排将這樣的兩條指令拉開距離, 以至于後一條指令進入cpu的時候，前一條指令結果已經得到了，那麼也就不再需要阻塞等待了。比如将指令重排為：

a++; c--; b=f(a);

相比于cpu的亂序，編譯器的亂序才是真正對指令順序做了調整。但是編譯器的亂序也必須保證程式上下文的因果關系不發生改變。

亂序的後果

亂序執行，有了“保證上下文因果關系”這一前提，一般情況下是不會有問題的。是以，在絕大多數情況下，我們寫程式都不會去考慮亂序所帶來的影響。

但是，有些程式邏輯，單純從上下文是看不出它們的因果關系的。比如：

*addr=5; val=*data;

從表面上看，addr和data是沒有什麼聯系的，完全可以放心的去亂序執行。但是如果這是在某某裝置驅動程式中，這兩個變量卻可能對應到裝置的位址端口和資料端口。并且，這個裝置規定了，當你需要讀寫裝置上的某個寄存器時，先将寄存器編号設定到位址端口，然後就可以通過對資料端口的讀寫而操作到對應的寄存器。那麼這麼一來，對前面那兩條指令的亂序執行就可能造成錯誤。

對于這樣的邏輯，我們姑且将其稱作隐式的因果關系；而指令與指令之間直接的輸入輸出依賴，也姑且稱作顯式的因果關系。cpu或者編譯器的亂序是以保持顯式的因果關系不變為前提的，但是它們都無法識别隐式的因果關系。再舉個例子：

obj->data = xxx; obj->ready = 1;

當設定了data之後，記下标志，然後在另一個線程中可能執行：

if (obj->ready) do_something(obj->data);

雖然這個代碼看上去有些别扭，但是似乎沒錯。不過，考慮到亂序，如果标志被置位先于data被設定，那麼結果很可能就杯具了。因為從字面上看，前面的那兩條指令其實并不存在顯式的因果關系，亂序是有可能發生的。

總的來說，如果程式具有顯式的因果關系的話，亂序一定會尊重這些關系；否則，亂序就可能打破程式原有的邏輯。這時候，就需要使用屏障來抑制亂序，以維持程式所期望的邏輯。

屏障的作用

記憶體屏障主要有：讀屏障、寫屏障、通用屏障、優化屏障、幾種。

以讀屏障為例，它用于保證讀操作有序。屏障之前的讀操作一定會先于屏障之後的讀操作完成，寫操作不受影響，同屬于屏障的某一側的讀操作也不受影響。類似的，寫屏障用于限制寫操作。而通用屏障則對讀寫操作都有作用。而優化屏障則用于限制編譯器的指令重排，不區分讀寫。前三種屏障都隐含了優化屏障的功能。比如：

tmp = ttt; *addr = 5; mb(); val = *data;

有了記憶體屏障就了確定先設定位址端口，再讀資料端口。而至于設定位址端口與tmp的指派孰先孰後，屏障則不做幹預。

有了記憶體屏障，就可以在隐式因果關系的場景中，保證因果關系邏輯正确。

多處理器情況

前面隻是考慮了單處理器指令亂序的問題，而在多處理器下，除了每個處理器要獨自面對上面讨論的問題之外，當處理器之間存在互動的時候，同樣要面對亂序的問題。

一個處理器（記為a）對記憶體的寫操作并不是直接就在記憶體上生效的，而是要先經過自身的cache。另一個處理器（記為b）如果要讀取相應記憶體上的新值，先得等a的cache同步到記憶體，然後b的cache再從記憶體同步這個新值。而如果需要同步的值不止一個的話，就會存在順序問題。再舉前面的一個例子：

<cpu-a> <cpu-b>

obj->data = xxx;

wmb(); if (obj->ready)

obj->ready = 1; do_something(obj->data);

前面也說過，必須要使用屏障來保證cpu-a不發生亂序，進而使得ready标記置位的時候，data一定是有效的。但是在多處理器情況下，這還不夠。data和ready标記的新值可能以相反的順序更新到cpu-b上！

其實這種情況在大多數體系結構下并不會發生，不過核心文檔memory-barriers.txt舉了alpha機器的例子。alpha機器可能使用分列的cache結構，每個cache列可以并行工作，以提升效率。而每個cache列上面緩存的資料是互斥的（如果不互斥就還得解決cache列之間的一緻性），于是就可能引發cache更新不同步的問題。

假設cache被分成兩列，而cpu-a和cpu-b上的data和ready都分别被緩存在不同的cache列上。

首先是cpu-a更新了cache之後，會發送消息讓其他cpu的cache來同步新的值，對于data和ready的更新消息是需要按順序發出的。如果cache隻有一列，那麼指令執行的順序就決定了操作cache的順序，也就決定了cache更新消息發出的順序。但是現在假設了有兩個cache列，可能由于緩存data的cache列比較繁忙而使得data的更新消息晚于ready發出，那麼程式邏輯就沒法保證了。不過好在smp下的記憶體屏障在解決指令亂序問題之外，也将cache更新消息亂序的問題解決了。隻要使用了屏障，就能保證屏障之前的cache更新消息先于屏障之後的消息被發出。

然後就是cpu-b的問題。在使用了屏障之後，cpu-a已經保證data的更新消息先發出了，那麼cpu-b也會先收到data的更新消息。不過同樣，cpu-b上緩存data的cache列可能比較繁忙，導緻對data的更新晚于對ready的更新。這裡同樣會出問題。

是以，在這種情況下，cpu-b也得使用屏障。cpu-a上要使用寫屏障，保證兩個寫操作不亂序，并且相應的兩個cache更新消息不亂序。cpu-b上則需要使用讀屏障，保證對兩個cache單元的同步不亂序。可見，smp下的記憶體屏障一定是需要配對使用的。

是以，上面的例子應該改寫成：

obj->data = xxx; if (obj->ready)

wmb(); rmb();

cpu-b上使用的讀屏障還有一種弱化版本，它不保證讀操作的有序性，叫做資料依賴屏障。顧名思義，它是在具有資料依賴情況下使用的屏障，因為有資料依賴（也就是之前所說的顯式的因果關系），是以cpu和編譯器已經能夠保證指令的順序。

再舉個例子：

init(newval); p = data;

<write barrier> <data dependency barrier>

data = &newval; val = *p;

這裡的屏障就可以保證：如果data指向了newval，那麼newval一定是初始化過的。

誤區

在smp環境下，記憶體屏障保證的是“一個cpu的多個操作的順序”（被另一個cpu所觀察到的順序），而不保證“兩個cpu的操作順序”。

舉例來說，有如下事件序列：

cpu-0：a = 5; cpu-0：wmb(); cpu-1：rmb(); cpu-1: i = a;

假設從時間順序上看，cpu-0對記憶體a的寫操作“a = 5”發生于cpu-1的讀操作“ i = a”之前，并且中間使用了記憶體屏障，那麼在cpu-1上，i一定等于5麼？

未必！因為記憶體屏障并不保證“兩個cpu的操作順序”。為什麼會是這樣呢？

一方面，這樣的保證沒有必要。兩個cpu上執行的操作本身是沒有關聯的，程式沒有要求應該誰先誰後。有可能“a = 5”先執行，也有可能“i = a”先執行，這都符合程式邏輯。隻是現在這個case恰好“a = 5”先執行而已。

另一方面，兩個cpu的操作孰先孰後，是無法通過外部時間來度量的。也就是說，“a = 5”先于“i = a”這件事情不能以它們發生的先後順序來度量。假設，cpu-0執行了“a = 5”，一個cpu主頻周期之後，cpu-1要執行“i = a”。這時候cpu-1如何知道“a = 5”這件事情已經發生了呢？它若想知道，唯一的辦法隻能跟其他cpu同步一下緩存，但是緩存同步的時間顯然遠遠大于一個cpu主頻周期。同步完成之後呢？且不說緩存同步導緻cpu性能變差。的确，現在cpu-1可以知道現在“a = 5”已經發生了，但是“a = 5”到底是發生在同步發起之前還是同步過程中呢？依然沒法知道。除非cpu在修改自己的cache的時候給每個記憶體單元打一個時間戳，并且時間戳層層傳遞到記憶體，并且記錄下來。（記錄時間戳花費的空間可能比中繼資料還大！）

更進一步，即便有時間戳，假設cpu-0執行“a = 5”、cpu-1執行“a = 3”，這兩個操作發生在同一個主頻周期，如何度量誰先誰後呢？從時間順序上顯然是沒法度量的，因為兩個操作是同時發生的，沒有先後順序。但是又非得度量其先後順序不可，最後a到底等于幾總該有個結論吧。度量的标準隻能是誰先搶到總線、把a的新值從cache更新到記憶體，誰就是先者。

是以度量記憶體操作的先後順序看的是誰先同步到記憶體（這一步是串行的，不可能同時發生），而不是看操作發生的時間順序。可能會這樣，cpu-0後執行操作，但是由于種種原因先搶到了總線而先把a更新到記憶體，那麼它就是先者。

那麼，cpu在看到記憶體屏障指令之後，是不是應該立馬flush cache，使得記憶體同步的順序跟時間順序更為趨近呢？cpu也許可以這麼做。但是其實意義并不大，無論如何記憶體同步順序永遠不可能與時間順序完全一緻，畢竟cpu是并行工作的，而記憶體同步是串行的。并且flush cache的開銷是巨大的，因為記憶體屏障的作用範圍不是某次記憶體操作，而是屏障前的所有記憶體操作，是以要flush隻能flush所有的cache。