Try   HackMD

New website: https://rhythm16.github.io

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有可能不會過，步驟如下:

  1. CPU0發送read invalidate a
  2. CPU0 把a = 1寫進store buffer
  3. CPU1回傳a的值並invalidate自己的cache line
  4. CPU0從CPU1得到a = 0的值，並放在cache中
  5. CPU0在沒有觀察store buffer的情況下執行b = a + 1
  6. 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也有可能不會過，步驟如下:

  1. CPU1沒有b，所以發送read b
  2. CPU0沒有a，所以發送read invalidate a並把a = 1寫進store buffer
  3. CPU0執行b = 1
  4. CPU1收到b = 1
  5. CPU1跳出迴圈執行assert，fail
  6. 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。
還是列一下步驟:

  1. CPU1沒有b，所以發送read b
  2. CPU0沒有a，所以發送read invalidate a並把a = 1寫進store buffer
  3. smp_mb()，CPU0 store buffer中的a = 1被標註
  4. CPU0執行b = 1，而因為store buffer中有被標註的entry所以也把b = 1放入store buffer
  5. CPU0把b的原始值(0)傳給CPU1，此時雙方的b處於shared狀態
  6. CPU1把自己的a給invalidate並傳送invalidate acknowledge給CPU0
  7. CPU0收到invalidate acknowledge，a的狀態為Exclusive
  8. CPU0把store buffer的a = 1寫進cache，a狀態變為Modified
  9. CPU0把store buffer的b = 1寫進cache，b狀態從shared變為modified，並發送b的invalidate給CPU1
  10. CPU1收到b的invalidate，發送invalidate acknowledge，然後執行while (b == 0)時發現自己沒有b(invalidated)便發送b的read
  11. CPU0把b傳給CPU1，狀態改為shared
  12. CPU1執行assert，再向CPU0要a
  13. 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);
}
  1. CPU1沒有b，所以發送read b
  2. CPU0沒有a，所以發送read invalidate a並把a = 1寫進store buffer
  3. smp_mb()，CPU0 store buffer中的a = 1被標註
  4. CPU0執行b = 1，而因為store buffer中有被標註的entry所以也把b = 1放入store buffer
  5. CPU1收到read invalidate a，放進invalidate queue，馬上回覆invalidate acknowledge
  6. CPU0收到a的invalidate acknowledge，依序把a = 1，b = 1寫進cache
  7. CPU0把b的新值1傳給CPU1
  8. CPU1執行while (b == 0)，跳出迴圈
  9. CPU1執行assert(a == 1)，失敗
  10. 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);
}
  1. CPU1沒有b，所以發送read b
  2. CPU0沒有a，所以發送read invalidate a並把a = 1寫進store buffer
  3. smp_mb()，CPU0 store buffer中的a = 1被標註
  4. CPU0執行b = 1，而因為store buffer中有被標註的entry所以也把b = 1放入store buffer
  5. CPU1收到read invalidate a，放進invalidate queue，馬上回覆invalidate acknowledge
  6. CPU0收到a的invalidate acknowledge，依序把a = 1，b = 1寫進cache
  7. CPU0把b的新值1傳給CPU1
  8. CPU1執行while (b == 0)，跳出迴圈
  9. smp_mb()，在invalidate queue中的invalidate a被標註
  10. CPU1中的a被invalidate，無法執行assert(a == 1)，發送read a
  11. 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);
}
Last changed by 
 
rhythm
https://rhythm16.github.io
1
1398

Read more

第一次給Linux Kernel發patch

New website: https://rhythm16.github.io 一路的故事是滿意外的，有天跟同學吃飯聊到了我讀的32bit x86架構的memory reference，又再一次提醒了我我對於64bit一無所知的事實。回家手癢google了"x86_64 memory reference"，前幾個搜尋結果是linux kernel的documentation，瀏覽了一下竟然發現有句話讀起來怪怪的： "16M TB" might look weird at first sight, but it's an easier to visualize size notation than "16 EB", which..(後省略) "easier"後面少了一個"way"啊！ 這在平常可能不算什麼，就少個字，也不至於影響閱讀，但我馬上想到了jserv教授之前在facebook發文提到了一個四歲小孩在爸爸工作時看到了kernel排版少了一個'='，爸爸就幫忙發了一個patch，也被接受了，說明這種重要的大專案連排版這種小錯也是要修正的。

Oct 26, 2022
Looking for Kernel Symbol Addresses in the Linux Kernel Image

New website: https://rhythm16.github.io I have always wondered how the linux kernel translates addresses to symbol names. This mechanism (called kallsyms) is used in multiple places in the kernel, for example in the panic() call the kernel prints out the call trace with function names and offsets with no problem at all, also the ftrace system is able to show the user all function names that the kernel has run, similarly, using kallsyms. This article written in Chinese explains the translation mechanism pretty well, and is worth a read if one is interested in knowing how it is done. However when discussing this topic with a professor, he asked me how I can find the raw bytes of the symbols used by kallsyms which are explained in the linked article above e.g. kallsyms_addresses and kallsyms_num_syms, etc. So, I set to find out where they are. It is unlikely for me and you to use the exact same kernel image, so the offsets and symbols won't be the same. Moreover, I'm using an ARMv8 image of linux version 5.4. From the article linked above we know that the kallsyms symbols are in the .rodata section, lets see where it is:

Oct 26, 2022
How Git repositories are blockchains

New website: https://rhythm16.github.io I think most people (even some computer science people, including me) only think of cryptocurrencies anytime when "blockchain" is mentioned. However I recently learned a bit about how git works internally and was very surprised by how similar it is to some of the bitcoin/blockchain concepts introductions that I have studied. So as a note and sharing of this interesting finding, in this article, I'm going to try to explain how git provides its fundamental functionalities, and hopefully if the reader is somewhat familiar with the basic blockchain concepts, can easily see what I claim in the title of the post. Blockchain knowledge is not required to understand this article, though. I'll be mostly talking about the git internals. Only basic git knowledge is assumed. Toy repo setup I'll setup a simple git repository for demonstration purposes, all commands in this article will be issued in the repo. Setup: # be sure to not be in a repository!

Oct 26, 2022
Makefile Notes

New website: https://rhythm16.github.io My notes for the Makefile file used by the make utility. Assignments The simplest = will expand recursively when the LHS is used a = "1" b = "2" c = $(a)3 # c is now "13"

Oct 26, 2022
Read more from rhythm
Published on HackMD