Memory Barriers 筆記

本篇內容來自Paul E. McKenney的perfbook Appendix C “Why Memory Barriers”以及蜗窝科技網誌上的翻譯，快速地讀完一次之後覺得基本的原理了解了，不過說到細節還是有很多需要釐清的部分，所以想用自己的方式寫下來。內容會比原文少非常多，要完整的學習的話建議閱讀原文。
Ascii art generated by asciiflow.

Stores 有時候很慢

這是對一個SMP系統的簡略想像:

┌───────┐          ┌───────┐
│ CPU 0 │          │ CPU 1 │
└───┬───┘          └───┬───┘
┌───┴───┐          ┌───┴───┐
│ CACHE │          │ CACHE │
└───┬───┘          └───┬───┘
    │   INTERCONNECT   │
    └────────┬─────────┘
             │
         ┌───┴────┐
         │ MEMORY │
         └────────┘

如果CPU0想要寫一個狀態是shared的cache line，必須發送一個invalidate訊號到interconnect上，再等其他所有CPU回傳invalidate acknowledge，如果其他的CPU cache很忙碌，這可能會讓CPU0 stall很久。

Store Buffer and Store Forwarding

為了增加速度，CPU設計師增加了store buffer，把即將要寫的內容先存起來，等到所有的invalidate acknowledge都拿到了再寫進cache中:

┌───────┐          ┌───────┐
│ CPU 0 │          │ CPU 1 │
└─┬──┬──┘          └─┬──┬──┘
  │ ┌┴─────┐         │ ┌┴─────┐
  │ │STORE │         │ │STORE │
  │ │BUFFER│         │ │BUFFER│
  │ └┬─────┘         │ └┬─────┘
┌─┴──┴──┐          ┌─┴──┴──┐
│ CACHE │          │ CACHE │
└───┬───┘          └───┬───┘
    │   INTERCONNECT   │
    └─────────┬────────┘
          ┌───┴────┐
          │ MEMORY │
          └────────┘

如此一來CPU就不用等所有invalidate acknowledge到，只要先寫進store buffer就可以繼續執行接下來的指令了。不過這也會有一些問題:

/* all variables start with 0 */
a = 1;
b = a + 1;
assert(b == 2);

assert有可能不會過，步驟如下:

CPU0發送read invalidate a
CPU0 把a = 1寫進store buffer
CPU1回傳a的值並invalidate自己的cache line
CPU0從CPU1得到a = 0的值，並放在cache中
CPU0在沒有觀察store buffer的情況下執行b = a + 1
b最終的值=1

這個問題硬體可解，解法就是CPU0在做read的時候必須觀察自己的store buffer是否有新的值，也就是所謂的store forwarding。

Store Buffers and Memory Barriers

看題目:

/* all variables start with 0 */
void zero() /* CPU 0 */
{
    a = 1;
    b = 1;
}

void one() /* CPU 1 */
{
    while (b == 0) continue;
    assert(a == 1);
}

現在假設CPU0的cache line有b缺a，CPU1有a缺b
assert也有可能不會過，步驟如下:

CPU1沒有b，所以發送read b
CPU0沒有a，所以發送read invalidate a並把a = 1寫進store buffer
CPU0執行b = 1
CPU1收到b = 1
CPU1跳出迴圈執行assert，fail
CPU1現在才收到read invalidate a

問題出在CPU0傳的read invalidate a和針對CPU1的read b response順序錯了，導致CPU1先看到b的更新才看到a的更新，至於順序為什麼錯，我能想到的原因有:

read response優先於read invalidate
cache優先於store buffer
interconnect的硬體設計
compiler reordering (但這篇文章不是討論這個)

這樣的問題沒有辦法透過硬體直接解決，因為硬體沒有辦法知道a和b之間的依賴關係。為了解決這樣的問題CPU提供了所謂的memory barriers讓軟體使用:

/* all variables start with 0 */
void zero() /* CPU 0 */
{
    a = 1;
    smp_mb();
    b = 1;
}

void one() /* CPU 1 */
{
    while (b == 0) continue;
    assert(a == 1);
}

如此一來，smp_mb()執行之後在store buffer中的所有entry(包含a = 1)會被註記，CPU在所有被標記的store完成之前不會讓後續的store顯示在cache中。b = 1也會被存在store buffer中，即使b的cache line對於CPU0是Modified或Exclusive。
還是列一下步驟:

CPU1沒有b，所以發送read b
CPU0沒有a，所以發送read invalidate a並把a = 1寫進store buffer
smp_mb()，CPU0 store buffer中的a = 1被標註
CPU0執行b = 1，而因為store buffer中有被標註的entry所以也把b = 1放入store buffer
CPU0把b的原始值(0)傳給CPU1，此時雙方的b處於shared狀態
CPU1把自己的a給invalidate並傳送invalidate acknowledge給CPU0
CPU0收到invalidate acknowledge，a的狀態為Exclusive
CPU0把store buffer的a = 1寫進cache，a狀態變為Modified
CPU0把store buffer的b = 1寫進cache，b狀態從shared變為modified，並發送b的invalidate給CPU1
CPU1收到b的invalidate，發送invalidate acknowledge，然後執行while (b == 0)時發現自己沒有b(invalidated)便發送b的read
CPU0把b傳給CPU1，狀態改為shared
CPU1執行assert，再向CPU0要a
assert通過

Invalidate Queues

Store Buffers存在的原因是等待所有CPU的invalidate acknowledge太慢了，所以先把要寫的東西放在一個地方，然後繼續執行下面的指令。那有沒有可能讓其他CPU的invalidate acknowledge回傳得快一點?
一個思考的方向是invalidate acknowledge只是說明「我知道我這個cache line不能用了」，並不一定要當場把那個cache line給invalidate掉，所以就誕生了invalidate queue，把需要invalidate的cache line的資訊給暫時存在一個queue上，就馬上回傳invalidate queue。如此一來即使cache正在忙碌，也能快速地回覆invalidate acknowledge給其他的CPU，讓他們繼續執行，而自己只需要在往外廣播coherency protocol的訊息時確認廣播的cache line不在invalidate queue中，因為cache line C如果在invalidate queue中，必須先處理才能向外面的interconnect發送關於C的訊息，不然不合理。

 ┌───────┐          ┌───────┐
 │ CPU 0 │          │ CPU 1 │
 └─┬──┬──┘          └─┬──┬──┘
   │ ┌┴─────┐         │ ┌┴─────┐
   │ │STORE │         │ │STORE │
   │ │BUFFER│         │ │BUFFER│
   │ └┬─────┘         │ └┬─────┘
 ┌─┴──┴──┐          ┌─┴──┴──┐
 │ CACHE │          │ CACHE │
 └───┬───┘          └───┬───┘
┌────┴─────┐       ┌────┴─────┐
│INVALIDATE│       │INVALIDATE│
│  QUEUE   │       │  QUEUE   │
└────┬─────┘       └────┬─────┘
     │   INTERCONNECT   │
     └─────────┬────────┘
           ┌───┴────┐
           │ MEMORY │
           └────────┘

好事不成雙，這樣的設計也會出錯，同樣的例子:

/* all variables start with 0 */
void zero() /* CPU 0 */
{
    a = 1;
    smp_mb();
    b = 1;
}

void one() /* CPU 1 */
{
    while (b == 0) continue;
    assert(a == 1);
}

CPU1沒有b，所以發送read b
CPU0沒有a，所以發送read invalidate a並把a = 1寫進store buffer
smp_mb()，CPU0 store buffer中的a = 1被標註
CPU0執行b = 1，而因為store buffer中有被標註的entry所以也把b = 1放入store buffer
CPU1收到read invalidate a，放進invalidate queue，馬上回覆invalidate acknowledge
CPU0收到a的invalidate acknowledge，依序把a = 1，b = 1寫進cache
CPU0把b的新值1傳給CPU1
CPU1執行while (b == 0)，跳出迴圈
CPU1執行assert(a == 1)，失敗
CPU1現在才有空處理invalidate queue，發現a處於invalidate狀態，不過錯誤已經產生

read的時候會觀察store buffer，避免自己寫自己沒看到，不過不會觀察invalidate queue，以增加效能

增加memory barrier可以解決這樣的錯誤:

/* all variables start with 0 */
void zero() /* CPU 0 */
{
    a = 1;
    smp_mb();
    b = 1;
}

void one() /* CPU 1 */
{
    while (b == 0) continue;
    smp_mb();
    assert(a == 1);
}

CPU1沒有b，所以發送read b
CPU0沒有a，所以發送read invalidate a並把a = 1寫進store buffer
smp_mb()，CPU0 store buffer中的a = 1被標註
CPU0執行b = 1，而因為store buffer中有被標註的entry所以也把b = 1放入store buffer
CPU1收到read invalidate a，放進invalidate queue，馬上回覆invalidate acknowledge
CPU0收到a的invalidate acknowledge，依序把a = 1，b = 1寫進cache
CPU0把b的新值1傳給CPU1
CPU1執行while (b == 0)，跳出迴圈
smp_mb()，在invalidate queue中的invalidate a被標註
CPU1中的a被invalidate，無法執行assert(a == 1)，發送read a
CPU1得到a的新值，assert通過

Read and Write Memory Barriers

前面所使用的smp_mb()會把store buffer和invadate queue中的entry都加上標註，這有時候是不需要的，zero()沒有讀東西，用不到invalidate queue，one()沒有寫東西，用不到store buffer，所以有效果比較弱的read memory barriers，對應到invalidate queue加標註和write memory barriers，對應到store buffer加標註，前面的例子可以改為:

/* all variables start with 0 */
void zero() /* CPU 0 */
{
    a = 1;
    smp_wmb();
    b = 1;
}

void one() /* CPU 1 */
{
    while (b == 0) continue;
    smp_rmb();
    assert(a == 1);
}

rhythm16.github.io