Linux 核心專題: 記憶體模型

執行人: I-Ying-Tsai

TODO: 研讀 Atomics 操作教材並改進

細讀並行程式設計: Atomics 操作、紀錄認知和提問，務必涵蓋「Memory Ordering 和 Barrier」
利用 litmus7 在 Raspberry Pi 4B 硬體實驗並充分解讀
適度改進筆記內容
搭配閱讀 2024 年報告-1 及 2024 年報告-2

利用 litmus7 在 Raspberry Pi 4B 硬體實驗並充分解讀

做實驗之前我需要先了解我的硬體架構：

i-ying-tsai@raspberrypi:~/herdtools7/catalogue/aarch64/tests $ lscpu
Architecture:             aarch64
  CPU op-mode(s):         32-bit, 64-bit
  Byte Order:             Little Endian
CPU(s):                   4
  On-line CPU(s) list:    0-3
Vendor ID:                ARM
  Model name:             Cortex-A72
    Model:                3
    Thread(s) per core:   1
    Core(s) per cluster:  4
    Socket(s):            -
    Cluster(s):           1
    Stepping:             r0p3
    CPU(s) scaling MHz:   33%
    CPU max MHz:          1800.0000
    CPU min MHz:          600.0000
    BogoMIPS:             108.00
    Flags:                fp asimd evtstrm crc32 cpuid
Caches (sum of all):      
  L1d:                    128 KiB (4 instances)
  L1i:                    192 KiB (4 instances)
  L2:                     1 MiB (1 instance)
NUMA:                     
  NUMA node(s):           1
  NUMA node0 CPU(s):      0-3
Vulnerabilities:          
  Gather data sampling:   Not affected
  Itlb multihit:          Not affected
  L1tf:                   Not affected
  Mds:                    Not affected
  Meltdown:               Not affected
  Mmio stale data:        Not affected
  Reg file data sampling: Not affected
  Retbleed:               Not affected
  Spec rstack overflow:   Not affected
  Spec store bypass:      Vulnerable
  Spectre v1:             Mitigation; __user pointer sanitization
  Spectre v2:             Vulnerable
  Srbds:                  Not affected
  Tsx async abort:        Not affected

架構如下：

                      +-----------------------+
                      |        DRAM           |
                      +-----------------------+
                               |
                      +-----------------------+
                      |     L2 Cache (1 MiB)  |
                      |     (Cluster Shared)  |
                      +-----------------------+
                      /      |       |       \
             +---------+ +---------+ +---------+ +---------+
             | Core 0  | | Core 1  | | Core 2  | | Core 3  |
             +---------+ +---------+ +---------+ +---------+
             | L1i 48K | | L1i 48K | | L1i 48K | | L1i 48K |
             | L1d 32K | | L1d 32K | | L1d 32K | | L1d 32K |
             +---------+ +---------+ +---------+ +---------+

首先安裝工具：

我根據 Paul McKenney 在演講中所使用的簡報使用以下指令先安裝了 herd7tools ：

sudo apt update
sudo apt install opam
opam init
eval $(opam env)
opam update
opam upgrade
opam install herdtools7

接著我先使用了 litmus7 工具分析了 SB.litmus ：
SB.litmus :

AArch64 SB
"PodWR Fre PodWR Fre"
Cycle=Fre PodWR Fre PodWR
Generator=diycross7 (version 7.54+01(dev))
Prefetch=0:x=F,0:y=T,1:y=F,1:x=T
Com=Fr Fr
Orig=PodWR Fre PodWR Fre
{
0:X1=x; 0:X3=y;
1:X1=y; 1:X3=x;
}
 P0          | P1          ;
 MOV W0,#1   | MOV W0,#1   ;
 STR W0,[X1] | STR W0,[X1] ;
 LDR W2,[X3] | LDR W2,[X3] ;
exists
(0:X2=0 /\ 1:X2=0)

對它執行 litmus7 ./SB.litmus -carch AArch64 指令後結果如下：

Test SB Allowed
Histogram (3 states)
324   *>0:X2=0; 1:X2=0;
499761:>0:X2=1; 1:X2=0;
499915:>0:X2=0; 1:X2=1;
Ok

Witnesses
Positive: 324, Negative: 999676
Condition exists (0:X2=0 /\ 1:X2=0) is validated
Hash=dca0cdb9995839b737bab4e9b28561fa
Cycle=Fre PodWR Fre PodWR
Generator=diycross7 (version 7.54+01(dev))
Com=Fr Fr
Orig=PodWR Fre PodWR Fre
Observation SB Sometimes 324 999676
Time SB 0.18

在實驗之前，我透過閱讀老師的 Atomics 操作的教材以及借助詢問 GPT 給我的一些破碎的資訊，先得到了一些概念並試著翻閱手冊，思考問題後再進行實驗：

STR W0, [X1] : 首先我知道這段指令它會把 W0 的值（1）寫到 X1 指定的位址（這裡是 x）。但在硬體層面它有可能會出錯，首先是 Cache 和主記憶體的信息延遲可能會導致在 P0 更改 X1 後的某段時刻，其他 CPU 看到的 X1 會不一樣。
- Cache coherence : 翻閱 Arm 關於 Cache coherence 的手冊後，發現手段有三種：
  - Disable caching：這個很直觀，它會把要共享的記憶體區域標記成 non-cacheable。但這會讓DRAM 延遲大幅提高、功耗高、效能降低。也就是會讓 Cache 的優勢消失。在這裡不會被實做。
  - Software managed coherency：
    對於這個方法，Arm 官方是這麼描述的：
    
    Software managed coherency is the traditional solution to the data sharing problem. Here the software, usually device drivers, must clean or flush dirty data from caches, and invalidate old data to enable sharing with other processors or masters in the system. This takes processor cycles, bus bandwidth, and power.
    
    於是我寫了一個 Kernel Module 搭配 dma 來試著使用它：
  - Hardware managed coherency：
    這個是目前大部分的處理器採用的方式，而 ARM Cortex-A72 採用的是基於 MOESI protocol 的 Cache 行為，具體行為如下：
    - Modified (已修改)
    - Owned (擁有者，允許共享但自己負責寫回)
    - Exclusive (獨佔，未修改)
    - Shared (共享)
    - Invalid (無效)
    並基於這個協定讓每個 CPU 使用 Snoop Control Unit (SCU) 監控各個 CPU 的 Cacheline 狀態。(當某 CPU 要讀一條 Cacheline 時，SCU 會 snoop 其他 CPU，看是否有更新版本)，接著各 CPU 之間透過 ARM 定義的 AMBA ACE bus (AMBA Coherent Extensions) 傳輸 snoop transaction：
    - AMBA ACE bus :
      定義了 5 個 channel：
      - Read Address Channel
      - Write Address Channel
      - Read Data Channel
      - Write Data Channel
      - Snoop Channel(就是透過這個發出 snoop 的請求)
- Store Buffering
  ARM TRM 裡提到：
  
  The Load-Store Unit contains multiple queues, including a store buffer. This enables stores to retire from the pipeline before they are globally visible, improving throughput.
  
  Q：那 Cortex-A72 pipeline 是如何設計的呢？
  A：被分成這幾個步驟：
  - Instruction Fetch：從 L1 I-Cache 抓取指令，每 cycle 可供應最多 3 條指令。
  - Instruction Decode：參考原文
    
    The decode unit translates fetched instructions into internal operations that can be dispatched out of order to execution pipelines. It includes branch decode, register rename, and allocation logic.
  - Dispatch / Rename：它會實際地執行 rename ，具體行為如下
    - 讀取 free list 中可用的 physical registers
      - free list : 它會記錄「目前哪些 Physical Registers 是空閒的，可以被新的指令使用」。
        這裡可能是用 bit vector + priority encoder 來實做，因為我沒有在手冊裡翻到對 free list 的實做細節描述，但在閱讀其他開源專案時發現幾乎都是使用了這個實做方式其變形。
        Ex：Berkeley Out-of-Order Machine
        
        其中 free list 在這裡被定義，使用了 bit vector 的方式：
        
        val free_list = RegInit(UInt(numPregs.W), io.initial_allocation)
        
        io.initial_allocation：它會告訴 FreeList：「剛開機時，哪些 Physical Register 預設是空的？」，來紀錄初始能用的 Physical Register。
        
        Q：為何 AR 和 PR 需要分開設計？我直覺想到說 AR 應該直接照著 PR 來定義。
        A：為了讓 Pipeline 可以支援 Reordering 與 speculative execution。首先因為 PR 的數量比 AR 還多，如果 CPU 內部只有 Architectural Register， Pipeline 中同一
        一個 AR 只能有一份值。但若有兩條指令要對同一個 AR 寫入：
        
        ADD X1, X1, #1 ; X1 = X1 + 1 ADD X1, X1, #2 ; X1 = X1 + 2
        
        或是 WAR：
        
        I1: R1 = R2 + R3 I2: R2 = 7
        
        在第一個範例中，第二條指令必須等到第一條指令將值寫回 AR，才能開始執行，否則會發生 harzard。
        在第二個範例中，I2 可能因為 reordering 而導致先執行，直接把 R2 改成 7。
        
        WAW (Write After Write) hazard → 需要序列化。
        
        WAR (Write After Read) hazard → 需要 stall 等待。
    - 將每個 architectural register 對應到一個新的 physical register
    - 更新 rename table
    - 配給 Reorder Buffer (ROB) Entry，建立依賴鏈
      - Reorder Buffer (ROB)：它允許指令在 pipeline 中亂序執行，但結果只能按程式原順序送回到 register file 或 memory。保證了 No reorder violation externally。
      - ROB Entry：每條進入 pipeline 的指令，都會在 ROB 裡分配一個 entry slot。
        他是一個一個環狀隊列（Ring Buffer），保存 pipeline 內每條指令的執行狀態。
    - 將 rename 後的 µops 放進 Issue Queue。
```
┌─────────────────────────────┐
│      Instruction Fetch       │
└────────────┬────────────────┘
             ↓
┌─────────────────────────────┐
│       Instruction Decode     │
└────────────┬────────────────┘
             ↓
┌─────────────────────────────┐
│      Issue / Rename Stage    │
└────────────┬────────────────┘
             ↓
┌─────────────────────────────┐
│      Execution Units (ALU)   │
│  +-------------------------+ │
│  | Load-Store Unit (LSU)   | │
│  |  ┌─────────────────────┐ | │
│  |  │  Store Buffer       │ | │
│  |  └─────────────────────┘ | │
│  +-------------------------+ │
└────────────┬────────────────┘
             ↓
┌─────────────────────────────┐
│       L1 Data Cache (L1D)    │
└────────────┬────────────────┘
             ↓
┌─────────────────────────────┐
│   L2 Cache (Cluster Shared)  │
└────────────┬────────────────┘
             ↓
┌─────────────────────────────┐
│        AMBA ACE Bus          │
│    (Snoop Control Unit)      │
└────────────┬────────────────┘
             ↓
         Main Memory (DRAM)
```

首先觀察上面的測試結果，發現這段程式理論上只會出現 (1,1) ，也就是 Sequential Consistency ，但顯然結果並非如此，首先因為 Cache 的存在，

接著，我下載了 Linux kernel 的 tools/memory-model 子目錄，接著進入 tools/memory-model 資料夾，以 herd 執行其中的範例測試並試著分析結果：

分析 `MP+poonceonces.litmus` :

C MP+poonceonces

(*
 * Result: Sometimes
 *
 * Can the counter-intuitive message-passing outcome be prevented with
 * no ordering at all?
 *)

{}

P0(int *buf, int *flag) // Producer
{
	WRITE_ONCE(*buf, 1);
	WRITE_ONCE(*flag, 1);
}

P1(int *buf, int *flag) // Consumer
{
	int r0;
	int r1;

	r0 = READ_ONCE(*flag);
	r1 = READ_ONCE(*buf);
}

exists (1:r0=1 /\ 1:r1=0) (* Bad outcome. *)

這裡使用了 WRITE_ONCE 和 READ_ONCE ，保證了讀和寫是一個 atomic 操作，compiler 不會將它重排。

根據這段程式碼，理論上它只會有 3 種情況：

1 : r0 = 0, r1 = 0
2 : r0 = 0, r1 = 1
3 : r0 = 1, r1 = 1

然而當我用 herd 進行分析後的執行結果卻是：

i-ying-tsai@raspberrypi:~/memory_model/tools/memory-model $ ~/herdtools7/_build/default/herd/herd.exe -conf linux-kernel.cfg litmus-tests/MP+poonceonces.litmus
Test MP+poonceonces Allowed
States 4
1:r0=0; 1:r1=0;
1:r0=0; 1:r1=1;
1:r0=1; 1:r1=0;
1:r0=1; 1:r1=1;
Ok
Witnesses
Positive: 1 Negative: 3
Condition exists (1:r0=1 /\ 1:r1=0)
Observation MP+poonceonces Sometimes 1 3
Time MP+poonceonces 0.03
Hash=c0ebd8ca556580d772ac73303c4c4f84

第四種可能出現了！根據這個執行結果我們幾乎可以 100% 確定 CPU 有可能重排了這段程式碼，於是我是著去試著查看 Arm 手冊來試著了解 ARMv8-A 架構下 memory model 對 weak ordering 的容忍程度後發現：

load-load, load-store, store-store, store-load 都可能被 CPU pipeline 重排。
那什麼情況下可能會被重排呢？查看手冊 B2.3 後整理如下 :
1 :
2 :

接著我試著使用了 litmus7 分析在 AArch64 架構下的實驗結果：

首先我用以下指令試著利用 herd 工具包裡的 litmus.exe 將 MP+poonceonces.litmus 轉成 .c

~/herdtools7/_build/default/litmus/litmus.exe -carch AArch64 -o mp_dir litmus-tests/MP+poonceonces.litmus
cd mp_dir
make

但出現了：

gcc -Wall -std=gnu99  -pthread -O2 -c outs.c
gcc -Wall -std=gnu99  -pthread -O2 -c utils.c
gcc -Wall -std=gnu99  -pthread -O2 -c litmus_rand.c
gcc -Wall -std=gnu99  -pthread -S MP+poonceonces.c
MP+poonceonces.c: In function ‘P0’:
MP+poonceonces.c:199:9: warning: implicit declaration of function ‘WRITE_ONCE’ [-Wimplicit-function-declaration]
  199 |         WRITE_ONCE(*buf, 1);
      |         ^~~~~~~~~~
MP+poonceonces.c: In function ‘P1’:
MP+poonceonces.c:227:14: warning: implicit declaration of function ‘READ_ONCE’ [-Wimplicit-function-declaration]
  227 |         r0 = READ_ONCE(*flag);
      |              ^~~~~~~~~
gcc -Wall -std=gnu99  -pthread  -o MP+poonceonces.exe outs.o utils.o litmus_rand.o MP+poonceonces.s
/usr/bin/ld: /tmp/cca8NjdC.o: in function `P0':
MP+poonceonces.c:(.text+0x46c): undefined reference to `WRITE_ONCE'
/usr/bin/ld: MP+poonceonces.c:(.text+0x47c): undefined reference to `WRITE_ONCE'
/usr/bin/ld: /tmp/cca8NjdC.o: in function `P1':
MP+poonceonces.c:(.text+0x56c): undefined reference to `READ_ONCE'
/usr/bin/ld: MP+poonceonces.c:(.text+0x57c): undefined reference to `READ_ONCE'
collect2: error: ld returned 1 exit status
make: *** [Makefile:30: MP+poonceonces.exe] Error 1
rm MP+poonceonces.s

我檢查了 util.c/h 發現是空的，於是我手動將這兩個巨集加進了 MP+poonceonces.c :

#define READ_ONCE(x) (*(volatile typeof(x) *)&(x))
#define WRITE_ONCE(x, val) (*(volatile typeof(x) *)&(x) = (val))

結果編譯成功：

i-ying-tsai@raspberrypi:~/memory_model/tools/memory-model/mp_dir $ make
gcc -Wall -std=gnu99  -pthread -S MP+poonceonces.c
gcc -Wall -std=gnu99  -pthread  -o MP+poonceonces.exe outs.o utils.o litmus_rand.o MP+poonceonces.s
awk -f show.awk MP+poonceonces.s > MP+poonceonces.t
rm MP+poonceonces.s

TODO: 研讀 LKMM 的演講材料

至少該涵蓋以下演講: (包含錄影)

Installing and Using the LinuxKernel Memory Model / video

How to Avoid Learning the Linux-Kernel Memory Model / video

TODO: 重現 LKMM 實驗

適度調整 paulmckrcu/litmus 和 tools/memory-model