---
tags: linux2022
---
# Memory ordering
contributed by < `ibat10clw` >
## diy 7 安裝
[diy](http://diy.inria.fr/) 的全稱是 diy provides tools to design and test weak
memory models, 內含了一系列針對 parallel program 與 shared-memory 的測試工具
根據官方的[文件](http://diy.inria.fr/sources/index.html), 建議透過 opam 來進行安裝, 若電腦上還沒有裝過 opam 的話能夠透過以下指令安裝以及進行 opam 的初始化。
```
$ sudo apt install opam
$ opam init
$ opam update
$ opam install herdtools7
```
安裝完成後就可以開始在終端機中使用安裝在 opam 內的 herdtools 7 系列工具, 但首先需要先啟動 opam 的環境
```
$ eval `opam env`
```
首先來測試一下官方提供的[範例](http://diy.inria.fr/tst/doc/SB.litmus)
```=
X86 SB
"Fre PodWR Fre PodWR"
{ x=0; y=0; }
P0 | P1 ;
MOV [x],$1 | MOV [y],$1 ;
MOV EAX,[y] | MOV EAX,[x] ;
locations [x; y;]
exists (0:EAX=0 /\ 1:EAX=0)
```
上面的測試檔共分為了三個部份
* 初始化
為第 3 行的部份, 能夠初始化的部份有 registers 以及 memory locations
* 程式碼
在程式碼的部份可以定義多個 process , 以上述範例來說共定義了兩個 process 分別為 P0 P1
底下則各執行了兩個 mov 的指令
* 最終條件
為第 7 行的部份, 能夠去測試括號內的情況是否可能存在
使用以下命令便可以得到最終結果
`$ litmus7 SB.litmus`
我的測試結果與官方文件上的[測試結果](http://diy.inria.fr/tst/doc/SB.log)稍有不同, 但同樣的在最終結果都有出現`EAX=0; 1:EAX=0; x=1; y=1;`的情況, 只是我的次數較少, 同時能發現即便 `x` 與 `y` 確實都是 `1` 的情況下, 依然 `EAX` 有機會為 `0` , 從這邊其實就能觀察出指令在進到記憶體後的順序是不保證能夠與原始程式碼相同的, 特別是在 x86 的 CPU 允許不同 core 的讀寫指令做重新排序, 因此才導致了可能發生兩個 process 的 EAX 最後結果都為 0 的狀況
### litmus 程式生成 使用 diy7
上面的 litmus 程式可以看出雖然看起來與 x86 的語法相似但在格式上卻又有些不同, 且多個 process 的時候橫向撰寫會變得相當麻煩, 這邊可以借助同一系列底下的工具 diy 7 來生成測試程式
首先要查看在目標架構上能夠支援什麼類型的測試的話可以輸入, 將底下的 xxx 替換成 AArch64 ARM MIPS PPC X86 X86_64 RISCV C CPP LISA 之一, 即可查看對應的架構下有哪些測資料
```
$ diyone7 -arch xxx -show edges
CoBack CoLeave Coe Coi Fenced** Fenced*R Fenced*W FencedR* FencedRR FencedRW
FencedW* FencedWR FencedWW Fences** Fences*R Fences*W FencesR* FencesRR FencesRW FencesW* FencesWR FencesWW FrBack FrLeave Fre Fri Hat LxSx MFence
MFenced** MFenced*R MFenced*W MFencedR* MFencedRR MFencedRW MFencedW* MFencedWR MFencedWW MFences** MFences*R MFences*W MFencesR* MFencesRR
MFencesRW MFencesW* MFencesWR MFencesWW Na Pod** Pod*R Pod*W PodR* PodRR
PodRW PodW* PodWR PodWW Pos** Pos*R Pos*W PosR* PosRR PosRW PosW* PosWR PosWW
R Read RfBack RfLeave Rfe Rfi Rmw W Write Wse Wsi
```
而產生測試程式的方法則是來自於資料間的關係, 以前面的範例來說可以得出下圖
[圖片來源](http://diy.inria.fr/doc/gen.html#candidate%3Aintro)
```=
X86 SB
"Fre PodWR Fre PodWR"
{ x=0; y=0; }
P0 | P1 ;
MOV [y],$1 | MOV [x],$1 ; #(a)Wy1 | (c)Wx1
MOV EAX,[x] | MOV EAX,[y] ; #(b)Rx0 | (d)Ry0
exists (0:EAX=0 /\ 1:EAX=0)
```
這邊的範例跟上面一樣, 但在第 5 與 6 行加入了註記, 輔助解釋上面的關係圖
這邊的關係皆是以指令不被
* 箭頭 po 表示這指令 A 到指令 B 的執行需要有先後關係
* 箭頭 fr 表示指令 A 到指令 B 的執行關係為 B 先執行完後 A 才能執行 read
這個圖正好對應上了程式碼 5 至 6 行的讀寫關係, 而測試程式便是由這種概念來產生的, 紀錄在第 2 行中
* Fre 表示了先寫在讀, 且發生在外部的(external)處理器上
* PodWR 代表了 W 在 R 之前, 且是發生在不同的(different)位置
綜合這兩組關係, 便可以透過輸入下列命令來產生測試程式
`$ diyone7 -arch X86 -name SB Fre PodWR Fre PodWR`
### herd7
最後 diy 7 系列的工具還提供了一套模擬器, 前面在使用 litmus7 來做測試的時後無法做跨平台測試, 但若是透過 herd7 則可以支援跨平台的測試
這邊透過了 diy7 來自動生成上個測試範例的 arm 下的文件
使用 litmus7 的話會得到下列錯誤訊息
```
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!! Test SB.litmus failed !!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Reported: Exec of 'gcc -Wall -std=gnu99 -O2 -pthread -o /tmp/dir309b44.tmp/SB.exe /tmp/dir309b44.tmp/utils.c /tmp/dir309b44.tmp/litmus_rand.c /tmp/dir309b44.tmp/outs.c /tmp/dir309b44.tmp/SB.c' failed
```
但是改用 herd7 的話就能成功獲得測試資訊
```
Test SB Allowed
States 4
0:EAX=0; 1:EAX=0;
0:EAX=0; 1:EAX=1;
0:EAX=1; 1:EAX=0;
0:EAX=1; 1:EAX=1;
Ok
Witnesses
Positive: 1 Negative: 3
Condition exists (0:EAX=0 /\ 1:EAX=0)
Observation SB Sometimes 1 3
Time SB 0.00
Hash=edd4722437d708675ed921e7607e77f0
```
## memory ordering 對平行程式的影響
在撰寫 lock-free 的程式時, 如果有遇到共用變數的情形, 那麼程式的執行結果可能會是無法預期的, 由於沒有使用 lock 對程式進行限制, 因此執行順序的不確定性就可能造成預期行為與實際行為的不同
而原始程式碼執行的順序與實際執行時的順序有可能會在下列兩個階段發生變化
* 編譯時期
* 執行時期
下面用一些範例來探討可能的情形與會造成的影響
### Memory ordering at compile time
```c
int A, B;
void test() {
A = B + 1;
B = 0;
}
```
使用 gcc 將其轉化為組合語言可以看到下列結果
`$ gcc -S -masm=intel test.c`
```asm
mov eax, DWORD PTR B[rip]
add eax, 1
mov DWORD PTR A[rip], eax
mov DWORD PTR B[rip], 0
```
可以看到執行順序確實為先將 B + 1 後在將其結果存到 A 最後將 B 歸零
但如果在這邊開啟了優化, 那麼編譯的結果就會產生改變
`$ gcc -S -O2 -masm=intel test.c`
```asm
mov eax, DWORD PTR B[rip]
mov DWORD PTR B[rip], 0
add eax, 1
mov DWORD PTR A[rip], eax
```
最一開始將 B 移動到暫存器的指令不變, 但接下來直接把 B 的值給歸零, 然後透過在暫存器中留存原先 B 的值來完成其餘運算, 並且將結果存到 A
對於 single thread 的程式來說兩者的最終結果相同, 但如果是 multi thread 的程式則會發生不可預期的行為
```c
int value;
int update = 0;
void UpdateValue(int x) {
value = x;
update = 1;
}
```
一個類似的範例, 若將變數 `update` 視為完成任務的一個 flag, 那麼在 multi thread 的環境下他就要保證在 `value` 被更新後才能被執行到, 也就是說若在這邊編譯器進行了優化將 `update = 1` 的指令給提前了, 那麼 `update = 1` 與 `value = x` 將有可能因為中斷而讓其他 thread 誤認了 `value` 已經被更新
### Compiler Barriers
上面的問題是來自於編譯器的優化, 實務上很多時候是不能去關閉編譯器優化的, 在無法關閉優化的前提之下, 能夠採用 barrier 的方式來告知編譯器可以 reorder 的範圍
```c=
int A, B;
void test() {
A = B + 1;
asm volatile("" ::: "memory");
B = 0;
asm volatile("" ::: "memory");
A = B + 1;
B = 0;
}
```
* `asm` 告訴編譯器這邊插入了一條組合語言指令
* `volatile` 則是告訴編譯器不得將這條指令做任何優化, 即是要按照原來的方式執行
* `"":::` 為空指令的意思
* `"memory"` 則是要求編譯器假設記憶體中的資訊有受到更改, 要求在往後有用到相同數據時不可直接從 registers 與 cache 中取用, 而要重新讀取
這邊以 gcc 做範例, 只要加上了 `asm volatile("" ::: "memory");`, 就可以告知編譯器 reorder 不可以跨越這一行, 就如同 barrier 的字面意思一樣, 能夠有效的解決在 compile time 的 reordering
同樣使用 `$ gcc -S -O2 -masm=intel test.c` 來編譯上面的程式, 這邊故意重複了兩次相同的動作, 來驗證 barrier 的作用範圍
```asm
mov eax, DWORD PTR B[rip]
add eax, 1
mov DWORD PTR A[rip], eax
mov DWORD PTR B[rip], 0
mov eax, DWORD PTR B[rip]
mov DWORD PTR B[rip], 0
add eax, 1
mov DWORD PTR A[rip], eax
```
可以上半部確實避掉了 reordering 的狀況, 而在沒有使用 barrier 的下半部則是跟前面的測試一樣將 `B = 0` 的動作給上提了
### Memory ordering at run time
現代的 cpu 在執行指令的時候大多支援 out-of-order execution, 因此連機器碼的順序都不能保證與最後執行的順序相同, 這邊的行為則根據 cpu 的設計會有所不同, 以下搭配了 x64 的 cpu 來進行討論
[Intel® 64 Architecture Memory Ordering White Paper](https://www.cs.cmu.edu/~410-f10/doc/Intel_Reordering_318147.pdf)
在這份文件的第 7 頁列出了 8 條規則
1. Loads are not reordered with other loads.
2. Stores are not reordered with other stores.
3. Stores are not reordered with older loads.
4. Loads may be reordered with older stores to different locations but not with older stores to the same location.
5. In a multiprocessor system, memory ordering obeys causality (memory ordering respects transitive visibility).
6. In a multiprocessor system, stores to the same location have a total order.
7. In a multiprocessor system, locked instructions have a total order.
8. Loads and stores are not reordered with locked instructions.
下面的範例一樣取自於[Intel® 64 Architecture Memory Ordering White Paper](https://www.cs.cmu.edu/~410-f10/doc/Intel_Reordering_318147.pdf), 並搭配 litmus7 來觀察可能發生的結果
* Loads are not reordered with other loads and stores are not reordered with other stores
<table>
<tr>
<td>Processor 0</td>
<td>Processor 1</td>
</tr>
<tr style="background-color:white">
<td>mov [_x], 1 // M1</br>mov [_y], 1 // M2</td>
<td>mov r1, [_x] // M3</br>mov r2, [_y] // M4</td>
</tr>
<tr>
<td colspan=2>Initially x == y == 0</br>r1 == 0 and r2 == 0 <b>is not allowed</b></td></tr>
</table>
由於 M1 與 M2 順序不可調動, M3 與 M4 也是
若 `r1 == 1` 即代表 M2 已經執行過了, 那麼 `r2` 則必須為 1
反之若 `r2 == 0` 則代表 M1 尚未執行與 M3 已經執行, 那麼 `r1` 的值也會是 0
因此可以斷言 `r1 == 1 /\ r2 == 0` 不會發生
litmus7 的測試結果, 確實不會出現 `r1 == 1 /\ r2 == 0` 的情況
```
exists (0:rax=1 /\ 1:rax=0)
Generated assembler
#START _litmus_P1
movl (%rdi,%rcx),%eax
movl (%rdx,%rcx),%eax
#START _litmus_P0
movl $1,(%rdx,%rcx)
movl $1,(%rdi,%rcx)
Test SB Allowed
Histogram (2 states)
499998:>0:rax=0; 1:rax=0;
500002:>0:rax=0; 1:rax=1;
No
Witnesses
Positive: 0, Negative: 1000000
Condition exists (0:rax=1 /\ 1:rax=0) is NOT validated
```
* Stores are not reordered with older loads
<table>
<tr>
<td>Processor 0</td>
<td>Processor 1</td>
</tr>
<tr style="background-color:white">
<td>mov r1, [_x] // M1</br>mov [_y], 1 // M2</td>
<td>mov r2, [_y] // M3</br>mov [_x], 1 // M4</td>
</tr>
<tr>
<td colspan=2>Initially x == y == 0</br>r1 == 1 and r2 == 1 <b>is not allowed</b></td></tr>
</table>
由於禁止將 store 調到 load 前面, 因此 M1 與 M2 和 M3 與 M4 的順序都不會被調動
```
exists (0:rax=1 /\ 1:rax=1)
Generated assembler
#START _litmus_P1
movl (%rdi,%rcx),%eax
movl $1,(%rdx,%rcx)
#START _litmus_P0
movl (%rdx,%rcx),%eax
movl $1,(%rdi,%rcx)
Test SB Allowed
Histogram (3 states)
4 :>0:rax=0; 1:rax=0;
499997:>0:rax=1; 1:rax=0;
499999:>0:rax=0; 1:rax=1;
No
Witnesses
Positive: 0, Negative: 1000000
Condition exists (0:rax=1 /\ 1:rax=1) is NOT validated
```
* Loads may be reordered with older stores to different locations
這個其實就是最一開始的範例, 但現在配上官方的解說文件重新檢視一次
<table>
<tr>
<td>Processor 0</td>
<td>Processor 1</td>
</tr>
<tr style="background-color:white">
<td>mov [_x], 1 // M1</br>mov r1, [_y] // M2</td>
<td>mov [_y], 1 // M3</br>mov r2, [_x] // M4</td>
</tr>
<tr>
<td colspan=2>Initially x == y == 0</br>r1 == 0 and r2 == 0 <b>is allowed</b></td></tr>
</table>
由於對不同位置操作的 store 若發生在 load 之前, 是允許重定位的
因此 M2 可以發生在 M1 之前, 同樣 M3 也可以發生在 M4 之前, 因此就會出現下面的結果
`r1 == 0 /\ r2 == 0`
```
Test SB Allowed
Histogram (4 states)
1 *>0:rax=0; 1:rax=0;
499998:>0:rax=1; 1:rax=0;
500000:>0:rax=0; 1:rax=1;
1 :>0:rax=1; 1:rax=1;
Ok
Witnesses
Positive: 1, Negative: 999999
Condition exists (0:rax=0 /\ 1:rax=0) is validated
```
Sign in with Wallet
Connect another wallet