---
tags: memory order
---

# I/O ordering 學習紀錄
contributed by < `jserv`, `jeffrey.w` >

Arm 工程師 [Will Deacon](https://www.linkedin.com/in/will-deacon-47946520/) 在 Edinburgh 的演講 [Uh-oh; it's I/O ordering](https://elinux.org/images/a/a8/Uh-oh-Its-IO-Ordering-Will-Deacon-Arm.pdf) 中提到一個範例：

##### 初始條件：*x, *y 在記憶體裡，初始值為 0，foo, bar 是 local variable

digraph g {
    rankdir = "RL";
    
    "cpu0" [label= "CPU0 | a: WRITE_ONCE(*x, 1); | b: foo = READ_ONCE(*y);", shape="record"];
   
    "cpu1" [label= "CPU1 | c: WRITE_ONCE(*y, 1); | d: bar = READ_ONCE(*x);", shape="record"];
    cpu1->cpu0 [color=white]
}

先看一下 [WRITE_ONCE / READ_ONCE](https://github.com/torvalds/linux/blob/master/include/linux/compiler.h#L237)，這兩個 macros 所作的事絕對不只字面上所說的 write / read 而己，我們看一下這段註解

[compile.h](https://github.com/torvalds/linux/blob/master/include/linux/compiler.h#L230)
> The compiler is also forbidden from **reordering** successive instances of READ_ONCE and WRITE_ONCE, ...

這兩個 macros 其實有用到 barrier_{[[1]](https://github.com/torvalds/linux/blob/master/include/linux/compiler.h#L223)} _{[[2]](https://github.com/torvalds/linux/blob/master/include/linux/compiler.h#L261)} 來處理 ordering 這個機制，不過有些背景知識還需要先理解一下，例如 `explicit memory barrier` 和 `smp_read_barrier_depends`，後面會再提到。

回到一開始的例子，a, b, c, d 存在著幾種可能的 **交錯執行順序**
{**a**, b, c, **d**}, {**a**, c, b, **d**}, {**a**, c, **d**, b}, {c, **d**, **a**, b},...

即便是這個順序 {a, b, c, d}，foo 和 bar 的結果**有沒有可能** 會是 foo == bar == 0？

有可能。的確存在這種可能：foo == bar == 0

於是有了以下 3 個問題：
:::warning
:question:
1. 範例中的 `*x`, `*y` 這種 「**共享資源**」 要如何取得讀寫的 **共識**？
2. reordering **一定會發生嗎？**
3. 如何改變 memory order？
:::

上述問題的關鍵在於 memory ordering，底下會探討 I/O ordering 在 linux kernel 中如何被支援，最後會探討 `I/O accessor` 和 `DMA barriers`。

[[`實驗紀錄`](https://hackmd.io/@butastur/rkkQEGjUN#%E5%AF%A6%E9%A9%97%E7%B4%80%E9%8C%84)]

<hr>

## diy: Design and Test Weak Memory Models
[diy](http://diy.inria.fr/) 是由 [INRIA](https://www.inria.fr/en/) (法國國家資訊與自動化研究所) 開發的一套可檢驗 memory model 的工具，對於模擬**不同 CPU 架構**的執行結果很有用，因為 compiler 將 C compile 成 assembly 雖然可以看出 **compiler 在 reordering 上作了什麼最佳化**，但少了 [litmus](http://diy.inria.fr/doc/litmus.html)，就很難模擬出 **CPU 在 reordering 上作了什麼最佳化**。

以下以 diy release 7 (簡稱 `diy7`) 作為探討對象。

先看一下這個範例 [SB.litmus](http://diy.inria.fr/tst/doc/litmus.html#litmus%3Asimple)

[[`source`](http://diy.inria.fr/tst/doc/litmus.html#litmus%3Asimple)]

X86 SB
"Fre PodWR Fre PodWR"
{ x=0; y=0; }
 P0          | P1          ;
 MOV [x],$1  | MOV [y],$1  ;
 MOV EAX,[y] | MOV EAX,[x] ;
exists (0:EAX=0 /\ 1:EAX=0)

從 litmus 的測試結果 [`run log`](http://diy.inria.fr/tst/doc/SB.log) 來看，有 4 種結果

P0:EAX=0; P1:EAX=0;
P0:EAX=1; P1:EAX=0;
P0:EAX=0; P1:EAX=1;
P0:EAX=1; P1:EAX=1;

Witnesses
Positive: 40, Negative: 999960

:::warning
:question:
為什麼在執行了 100 萬次之後，會出現 `EAX` 在 `P0`, `P1` 都是 0 的情況。
:::

herdtools7 用 OCaml 開發，可透過 [opam](https://opam.ocaml.org/) (OCaml Package Manager) 安裝。初次使用請輸入以下命令:

$ sudo apt install opam
$ opam init
$ eval $(opam config env)

:::success
看到以下訊息時，請耐心等待:

=-=- Updating package repositories =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
[default] synchronized from https://opam.ocaml.org/1.2.2

看到以下訊息時，輸入 `y`:

Do you want OPAM to modify ~/.profile and ~/.ocamlinit?
(default is 'no', use 'f' to name a file other than ~/.profile)

:::

若系統中已有 opam，確認升級到最新版本:

$ opam update
$ opam upgrade

接著執行以下命令，安裝 herdtools7:

$ opam install herdtools7

再用 litmus7 測試:

$ litmus7 SB.litmus

跑出來的結果和官方的結果 [`run log`](http://diy.inria.fr/tst/doc/SB.log) 差不多

Witnesses
Positive: 41, Negative: 999959

再實驗一下，這次用 Arm 作範例。

:::info
"litmus" 這字是「[石蕊](https://zh.wikipedia.org/zh-tw/%E7%9F%B3%E8%95%8A)」的意思，是一種藍色色素，分子式C~7~H~7~O~4~N，常用作酸鹼指示劑 (pH 指示劑)。
這裡被引申為測試 memory model 的工具。
:::

先用 `diy7` 產生一些 Arm 的 test case，然後用` litmus7` 測試:

$ cat X.conf 
-arch ARM
-name arm
-nprocs 2
-size 6
-safe Pod**,Fre,Rfe,Wse
-mode critical

$ diy7 -conf X.conf -o .
Generator produced 6 tests

$ litmus7 arm000.litmus

觀察由 `diy7` 產生的 `arm000.litmus` 內容:

ARM arm000
"PodWW Rfe PodRR Fre"
Cycle=Rfe PodRR Fre PodWW
Relax=
Safe=Rfe Fre PodWW PodRR
Generator=diy7 (version 7.51)
Prefetch=0:x=F,0:y=W,1:y=F,1:x=T
Com=Rf Fr
Orig=PodWW Rfe PodRR Fre
{
%x0=x; %y0=y;
%y1=y; %x1=x;
}
 P0           | P1           ;
 MOV R0,#1    | LDR R0,[%y1] ;
 STR R0,[%x0] | LDR R1,[%x1] ;
 MOV R1,#1    |              ;
 STR R1,[%y0] |              ;
exists
(1:R0=1 /\ 1:R1=0)

注意，由於我們指定 Arm 架構，所以 `litmus7` 一定要執行於 Arm/Aarch64 的硬體環境中，否則會出現以下錯誤:

/tmp/dir3a59fc.tmp/arm000.c:40: Error: number of operands mismatch for 'dsb'

預期 `litmus7` 會輸出以下訊息:

Test arm000 Allowed
Histogram (2 states)
512550:>1:R0=0; 1:R1=0;
487450:>1:R0=1; 1:R1=1;
No

Witnesses
Positive: 0, Negative: 1000000
Condition exists (1:R0=1 /\ 1:R1=0) is NOT validated
Hash=40a0063acb5b52574292940da6406eef
Cycle=Rfe PodRR Fre PodWW
Relax arm000 No 
Safe=Rfe Fre PodWW PodRR
Generator=diy7 (version 7.51)
Com=Rf Fr
Orig=PodWW Rfe PodRR Fre
Observation arm000 Never 0 1000000
Time arm000 6.55

觀察 `arm000.c` 的內容:

$ litmus7 arm000.litmus -o arm000

`arm000.c` 的內容:

/* Full memory barrier */
inline static void mbar(void) {
  asm __volatile__ ("dsb sy" ::: "memory");
}

- [Advanced control of test parameters](http://diy.inria.fr/doc/litmus.html#advanced%3Acontrols)
- [POWER and ARM Litmus Tests](https://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test6.pdf)

`dsb` 這個 Arm 指令後面再來探討，先回到 SB.litmus 這個範例。

SB.litmus 和一開始的 WRITE_ONCE / READ_ONCE，基本上探討的是同一個問題，就是當這兩個 CPU 要**對同一個 memory address** 執行 load / store 的時候，各自的 CPU 會**在哪一步讀到什麼值**？

雖然只是在個別的 CPU 作 load / store，但其實相關的知識包括了這兩個 CPU 的 cache 的資料是不是一致 (cache coherency)、CPU 會依照什麼順序執行 (I/O ordering、reordering)、用什麼 barrier 來影響 CPU 執行的順序 (memory barrier)、strong memory model 和 weak memory model 各自的執行順序有什麼不一樣、有什麼相關的 atomic operation ...etc。

在繼續探討 litmus 的 test case 如何撰寫之前，先看一下 store buffer。

## Store Buffer
在沒有 `store buffer` 之前，CPU 會直接對 cache 進行 `load` / `store`，像以下這張圖這樣。
[source](http://www.puppetmastertrading.com/images/hwViewForSwHackers.pdf)

digraph G {
{ rank = same; cpu0; cpu1 }
{ rank = same; cache0; cache1 }
{ rank = same; interconnect0; interconnect1; interconnect_mid }

cpu0 [shape=square;label="CPU 0"];
cache0 [shape=square;label="Cache"];
cpu0->cache0;

cpu1 [shape=square;label="CPU 1"];
cache1 [shape=square;label="Cache"];
cpu1->cache1;

interconnect0 [shape=square;label="";width=0];

interconnect1 [shape=square;label="";width=0];

interconnect_mid [shape=square;label="";width=0];

cache0 -> interconnect0[arrowhead=none; label="  interconnect "];
cache1 -> interconnect1[arrowhead=none];

interconnect0 -> interconnect_mid[arrowhead=none];

interconnect_mid->interconnect1[arrowhead=none];



memory [shape=square;label="Memory"];

interconnect_mid-> memory;
}

但是有了 `store buffer`，情況就有點不一樣了。簡單來說，就是`load` 會先從 cache 去讀 _{(這裡省略了對 [MESI protocol](https://en.wikipedia.org/wiki/MESI_protocol) 的描述，後面會再提到 MESI)}，但是 `store` 的時候，並不是直接對 cache 寫入，而是把 `store instruction` 先放進 store buffer。

用 GraphViz 重畫後，位置和原圖 _{[[page 7](http://www.puppetmastertrading.com/images/hwViewForSwHackers.pdf)]} 有點不一樣，不過概念是一樣的。

digraph G {
{ rank = same; cpu0; cpu1 }
{ rank = same; cache0; cache1 }
{ rank = same; interconnect0; interconnect1; interconnect_mid }

cpu0 [shape=square;label="CPU 0"];
cache0 [shape=square;label="Cache"];
sb0 [shape=square;label="Store \rBuffer";fontsize=10];

cpu0 -> sb0 -> cache0;
cache0->cpu0;

cpu1 [shape=square;label="CPU 1"];
cache1 [shape=square;label="Cache"];
sb1 [shape=square;label="Store\rBuffer";fontsize=10];

cache1->cpu1;
cpu1 -> sb1 -> cache1;

interconnect0 [shape=square;label="";width=0];

interconnect1 [shape=square;label="";width=0];

interconnect_mid [shape=square;label="";width=0];

cache0 -> interconnect0[arrowhead=none; label="  interconnect "];
cache1 -> interconnect1[arrowhead=none];

interconnect0 -> interconnect_mid[arrowhead=none];

interconnect_mid->interconnect1[arrowhead=none];



memory [shape=square;label="Memory"];

interconnect_mid-> memory;
}

> 在 COSCUP 上有人提問，store buffer 之間有沒有 coherence 的問題？
> [name=Jeffrey.W][time=Fri, Aug 23, 2019 5:36 AM]

關於 store buffer，先看一個基於 [Dekker Protocol](https://en.wikipedia.org/wiki/Dekker%27s_algorithm) 的例子。[Dekker's algorithm](https://en.wikipedia.org/wiki/Dekker%27s_algorithm) 是第一個被驗證 mutual exclusion 的解法，但因為效率低落，現代電腦系統不採用。

[出處：Weak Consistency (TSO as an Example), page 51 ](http://user.it.uu.se/~parosh/publications/papers/fmics2017.pdf)

init: (x = 0; y = 0)
P1               | P2
write: x = 1     | write: y = 1
read: y = 0      | read: x = 0
critical section | critical section

          store buffer    +---------+
+----+    +--------+      |  x == 0 |
| P1 |--->|  x = 1 |----->|         |
+----+    +--------+      |         |
          store buffer    |  y == 0 |
+----+    +--------+      |         |
| P2 |--->|  y = 1 |----->|         |
+----+    +--------+      |         |
                          +---------+

[Dekker's algorithm](https://en.wikipedia.org/wiki/Dekker%27s_algorithm)，是透過 `busy wait` 的方式，讓任何時候<font color='blue'>最多只能有一個</font> `process` 進入 `critical section` _{(Dekker's algorithm 是在講 `process`，<font color='blue'>不是 `processor`)</font>}。
也就是說，如果已經有一個 `process` _{(**假設是 P0**)} 進入了 `critical section`，下一個要進入 `critical section` 的 `process` 就會 `busy wait`，直到 P0 離開了 `critical section` _{(**假設是 P0** 先進入 `critical section`)}。

回到這個範例

[[source](https://elinux.org/images/a/a8/Uh-oh-Its-IO-Ordering-Will-Deacon-Arm.pdf)]

digraph g {
    rankdir = "RL";
    
    "cpu0" [label= "CPU0 | a: WRITE_ONCE(*x, 1); | b: foo = READ_ONCE(*y);", shape="record"];
    
    "cpu1" [label= "CPU1 | c: WRITE_ONCE(*y, 1); | d: bar = READ_ONCE(*x);", shape="record"];
    cpu1->cpu0 [color=white]
}

我們先從 sequential consistency (SC) 的角度來說明一下什麼順序對 SC 來說是不允許的。
關於SC，初次被定義是出自於Leslie Lamport
> ... the result of any execution is the same as if the operations of all the processors **were executed in some sequential order**, and the operations of each individual processor appear in this sequence in **the order specified by its program**.
> Leslie Lamport, 1979

從 SC 的角度來說，**the order specified by its program** 這句話的意思就是在說 {**b,d**,a,c} 這種順序是不會發生的。但從 litmus 的實驗來看，**foo == bar == 0** 可能會發生。

在這個例子中，也許我們會想要在某種程度上對 **CPU 最佳化的行為**作一些控制，例如可能會希望**在 load 之前，先完成 store**。

基於這個需求，我們以 Arm 為例，看一下 [dmb](http://infocenter.arm.com/help/topic/com.arm.doc.dui0473m/dom1361289870356.html), dsb 和 isb。

[ARM® Compiler armasm User Guide, Version 5.06](http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.dui0473m/dom1361289870356.html) 對於 [dmb](http://infocenter.arm.com/help/topic/com.arm.doc.dui0473m/dom1361289870356.html) 裡有這麼一段文字
> It **does not affect the ordering** of any other instructions executing on the processor.

這個意思是不是說 dmb 並不會真的**影響** CPU 的**實際執行順序**？

沒錯，`dmb`, `dsb` 和 `isb` 的目的並不是要**控制執行順序**，他們的目的是扮演一種 barrier 的角色，在 **特定條件滿足之後** 再繼續執行 barrier 之後的 instruction。

### 實驗 litmus7
我們透過實驗來了解一下 dmb。底下這個範例來自於 Professor Peter Sewell (劍橋大學 [Computer Laboratory](http://www.cl.cam.ac.uk/))

[[SB+dmbs](https://www.cl.cam.ac.uk/~pes20/arm-supplemental/arm040.html#tst@SB+dmbs)]

ARM SB+dmbs
"DMBdWR Fre DMBdWR Fre"
Cycle=Fre DMBdWR Fre DMBdWR
{
%x0=x; %y0=y;
%y1=y; %x1=x;
}
 P0            | P1            ;
 MOV R0, #1    | MOV R0, #1    ;
 STR R0, [%x0] | STR R0, [%y1] ;
 DMB           | DMB           ;
 LDR R1, [%y0] | LDR R1, [%x1] ;
exists
(0:R1=0 /\ 1:R1=0)

用 litmus7 執行，得到這個結果

#START _litmus_P1
	mov x8,#1
	str x8,[x2]
	dmb sy
	ldr x4,[x0]
#START _litmus_P0
	mov x8,#1
	str x8,[x0]
	dmb sy
	ldr x4,[x2]

Test SB+dmbs Allowed
Histogram (4 states)
2     *>0:R1=0; 1:R1=0;
490580:>0:R1=1; 1:R1=0;
481247:>0:R1=0; 1:R1=1;
28171 :>0:R1=1; 1:R1=1;
Ok

Witnesses
Positive: 2, Negative: 999998
Condition exists (0:R1=0 /\ 1:R1=0) is validated

從第 14 行我們看到 `0:R1=0; 1:R1=0`。

之後用 litmus7 實驗 [isbs](https://www.cl.cam.ac.uk/~pes20/arm-supplemental/arm071.html#tst@SB+isbs) 和 [dsbs](https://www.cl.cam.ac.uk/~pes20/arm-supplemental/arm041.html#tst@SB+dsbs)，仍然看到 `0:R1=0; 1:R1=0;`。

重新看一下 litmus7 產生的 assembly，再對照一下 Arm 的[文件](http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.dui0473m/dom1361289870356.html)。

第 4 行和第 9 行看到 `dmb sy`，在 [ARMv8-A Memory systems](https://developer.arm.com/docs/100941/latest/barriers) 裡，對 sy 是這麼說的
> Full system operation. This is the default and can be omitted.

我們再完整的看一下 [dmb](https://developer.arm.com/docs/100941/latest/barriers) 是什麼
> It also ensures that any explicit preceding data or unified cache maintenance operations have completed before any subsequent data accesses are executed.

對照一下 [dsb](https://developer.arm.com/docs/100941/latest/barriers)
> ... No instruction in program order **after** this instruction executes **until this instruction completes**. This instruction completes when:
>
> - All explicit memory accesses **before this instruction complete**.

以上這兩段，說明 dmb 和 dsb 的不同：
- dmb 所保證的，是保證在 dmb 之前對 memory 的 access，在 dmb 之後都是 **observed**。
- 然而 dsb 的保證更嚴格，dsb 所保證的，是在 dsb 之前 explicit memory access 的 instruction **都要 complete**，才會執行 dsb 之後的 instruction。

[armmem](https://www.cl.cam.ac.uk/~pes20/ppcmem/index.html#ARM-SB+dmbs) 是一套基於 web 介面，用來測試 memory model 的工具，我試著在上面實驗一下 [SB+dmbs](https://www.cl.cam.ac.uk/~pes20/arm-supplemental/arm040.html#tst@SB+dmbs)，得到的結果是這樣

Test SB+dmbs Allowed
States 3
0:R1=0; 1:R1=1; via [0;0;0;1;0;0;2;0;3;0;0;0;1;0;4;0;0;0]
0:R1=1; 1:R1=0; via [0;0;0;1;0;0;1;0;3;4;0;0;0;2;0;0;0;0]
0:R1=1; 1:R1=1; via [0;0;0;1;0;0;1;0;2;0;3;0;0;0;4;0;0;0]
No (allowed not found)
Condition
exists (0:R1=0 /\ 1:R1=0)
Hash=631b5d7f1cd13c8b2af0b5ebf9c34dda
Cycle=Fre DMBdWR Fre DMBdWR
Observation SB+dmbs Never 0 3 

[SB+dmbs](https://www.cl.cam.ac.uk/~pes20/arm-supplemental/arm040.html#tst@SB+dmbs) 在 litmus7 和 armmem 上測試的結果並不一樣，為何？因為 litmus7 和 armmem 是建立在不同層級的測試基礎上，armmem 的測試基礎是**順序**(而且是 bare metal)，而 litmus7 還包括了 atomic operation。再簡單一點的說，就是在 litmus7 上的測試還必須使用 atomic operation 才可以解決 reordering 的問題。

- 在 litmus7 和 armmem 上的實驗，都是在證明 dmb 之前的 instruction 不會在 dmb 執行了之後才執行。

### 延伸實驗
關於 store buffer 與 dmb 在 litmus7 的實驗，實驗細節可以參考這裡 [[`sb_dmbs.md`](https://github.com/jeffrey-minwei/io-ordering/blob/main/arm/sb_dmbs.md)]。

### Completion
[Uh-oh; it’s I/O ordering! page 14](https://events.linuxfoundation.org/wp-content/uploads/2017/12/Uh-oh-Its-IO-Ordering-Will-Deacon-Arm.pdf) 對 ordering 和 completion 作了一個比較。

<hr>

## Arm instructions - [DMB、DSB and ISB](https://developer.arm.com/docs/100941/latest/barriers)
底下會繼續探討 dmb、dsb and isb，所以回顧一下 ARM® Compiler armasm User Guide Version 5.06 裡相關的說明 _{[[Chapter 11 ARM and Thumb Instructions](http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.dui0473m/dom1361289871865.html)]}。

### Data Memory Barrier ([DMB](https://developer.arm.com/docs/100941/latest/barriers))

`dmb` 是 Arm 的 32-bit Thumb instruction，在 16-bit Thumb 沒有 `dmb`。

### Data Synchronization Barrier ([DSB](https://developer.arm.com/docs/100941/latest/barriers))

`dsb` 是 Arm 的 32-bit Thumb instruction，在 16-bit Thumb 沒有 `dsb`。

雖然 `dsb` 在 32-bit Thumb、32-bit Thumb-2 都有支援 ，但支援的程式不一樣。在 Thumb-2 之下，`dsb` 的 option 只支援 `SY`，但在 Thumb 之下，還支援了 `SY`, `ST`, `ISH`, `ISHST`, `NSH`, `NSHST`, `OSH`, `OSHST` 這些 option。

對於 dsb 在不同指令集的支援程度，整理如下：

32-bit Thumb：`SY`, `ST`, `ISH`, `ISHST`, `NSH`, `NSHST`, `OSH`, `OSHST`
32-bit Thumb-2：`SY`
16-bit Thumb： 不支援 dsb

asm __volatile__ ("dsb sy" ::: "memory");

## [Exclusive Monitors](https://developer.arm.com/docs/100934/latest/exclusive-monitors)
在我們使用 [Exclusive Monitors](https://developer.arm.com/docs/100934/latest/exclusive-monitors) 來進行 litmus7 的實驗之前，我們看一下 Arm 的 exclusive monitors 和 LDREX / STREX。
- [Exclusive monitors](http://infocenter.arm.com/help/topic/com.arm.doc.dht0008a/CJAGCFAF.html)
- [Load-Exclusive (LDREX)](http://infocenter.arm.com/help/topic/com.arm.doc.dht0008a/ch01s02s01.html#id3031222)
- [Store-Exclusive (STREX)](http://infocenter.arm.com/help/topic/com.arm.doc.dht0008a/ch01s02s01.html#id3031256)

### Exclusive monitors
Arm 在 Exclusive monitors 的實作上分為兩種 `local monitor` 和 `global monitor`。以下這個架構節錄自 Arm Information Center，說明 local monitor 和 global monitor 各自出現在什麼地方。
[[source](http://infocenter.arm.com/help/topic/com.arm.doc.dht0008a/CJAGCFAF.html#CJABBBAE)]

Exclusive monitors 有兩種狀態：`open` 和 `exclusive`：
* load-exclusive 會把 exclusive monitor 的狀態改成 `exclusive`。
* store-exclusive 只有**當 exclusive monitor 的狀態是 exclusive** 的時候 store 才會成功。
* 所以，load <font color='red'>進行中的時候無法 store</font>。
* 也就是說，如果 <font color='red'>存在</font> 著一個 exclusive monitor <font color='red'>還沒有</font> **把狀態改成 exclusive**，那麼 store 就不會成功。

[[source](http://infocenter.arm.com/help/topic/com.arm.doc.dht0008a/CJAGCFAF.html)]
> A Store-Exclusive can succeed only if **all** accessed exclusive monitors are in the exclusive state.

首先我們看到了 memory location 會被標記為 `non-shareable` <font color='red'>或</font> `shareable`，接下來看一下這個標記如何影響 `local/global monitor` 的行為。

<hr>

## 實驗紀錄

Example below is from Professor Peter Sewell (University of Cambridge [Computer Laboratory](http://www.cl.cam.ac.uk/))
[[`SB+dmbs`](https://www.cl.cam.ac.uk/~pes20/arm-supplemental/arm040.html#tst@SB+dmbs)]

ARM SB+dmbs
"DMBdWR Fre DMBdWR Fre"
Cycle=Fre DMBdWR Fre DMBdWR
{
%x0=x; %y0=y;
%y1=y; %x1=x;
}
 P0            | P1            ;
 MOV R0, #1    | MOV R0, #1    ;
 STR R0, [%x0] | STR R0, [%y1] ;
 DMB           | DMB           ;
 LDR R1, [%y0] | LDR R1, [%x1] ;
exists
(0:R1=0 /\ 1:R1=0)

以下會在 4 種環境實驗 `store buffer` + `dmb`：
- x86
- VM
- [armmem](https://www.cl.cam.ac.uk/~pes20/ppcmem/index.html#ARM-SB+dmbs)
- Raspberry Pi 3 Model B+

### 在 x86 上用 `herd7` 模擬
`herd7` 是一個 simulator，模擬 `Arm` 的結果如下

$ herd7 -model arm.cat sb_dmbs.litmus 
Test SB+dmbs Allowed
States 3
0:R1=0; 1:R1=1;
0:R1=1; 1:R1=0;
0:R1=1; 1:R1=1;
No
Witnesses
Positive: 0 Negative: 3
Condition exists (0:R1=0 /\ 1:R1=0)
Observation SB+dmbs Never 0 3
Time SB+dmbs 0.02
Hash=631b5d7f1cd13c8b2af0b5ebf9c34dda

從結果可以看到 `DMB` 發揮了作用，`R1` 在 `P0` 和 `P1` 都是 `0` 的情況 **並沒有發生**。

這裡再回顧一下 [`dmb`](https://developer.arm.com/docs/100941/latest/barriers) 在 Arm 的規格是怎麼說的
> It also ensures that any explicit preceding data or unified cache maintenance operations **have completed before any subsequent data accesses are executed**.

在 `dmb` 之後如果有 access data 的 instruction，保證會等到 dmb 之前的 operation complete，才會執行 dmb 之後的 instruction。

### 在 VM 上實驗

#START _litmus_P1
	mov x8,#1
	str x8,[x2]
	dmb sy
	ldr x4,[x0]
#START _litmus_P0
	mov x8,#1
	str x8,[x0]
	dmb sy
	ldr x4,[x2]

Test SB+dmbs Allowed
Histogram (4 states)
2     *>0:R1=0; 1:R1=0;
490580:>0:R1=1; 1:R1=0;
481247:>0:R1=0; 1:R1=1;
28171 :>0:R1=1; 1:R1=1;
Ok

Witnesses
Positive: 2, Negative: 999998
Condition exists (0:R1=0 /\ 1:R1=0) is validated

### 用 [armmem](https://www.cl.cam.ac.uk/~pes20/ppcmem/index.html#ARM-SB+dmbs) 模擬

Test SB+dmbs Allowed
States 3
0:R1=0; 1:R1=1; via [0;0;0;1;0;0;2;0;3;0;0;0;1;0;4;0;0;0]
0:R1=1; 1:R1=0; via [0;0;0;1;0;0;1;0;3;4;0;0;0;2;0;0;0;0]
0:R1=1; 1:R1=1; via [0;0;0;1;0;0;1;0;2;0;3;0;0;0;4;0;0;0]
No (allowed not found)
Condition
exists (0:R1=0 /\ 1:R1=0)
Hash=631b5d7f1cd13c8b2af0b5ebf9c34dda
Cycle=Fre DMBdWR Fre DMBdWR
Observation SB+dmbs Never 0 3

跟預期的一樣，dmb 發揮了作用。

### 在 Raspberry Pi 3 Model B+ 上實驗 Store buffer + dmb
:::danger
litmus7 如果少了 `-ccopts -march=armv8-a`，就會出現這類的錯誤 **selected processor does not support `dsb sy` in ARM mode**
:::

$ litmus7 sb_dmbs.litmus -ccopts -march=armv8-a
...
Test SB+dmbs Allowed
Histogram (3 states)
438024:>0:R1=1; 1:R1=0;
438206:>0:R1=0; 1:R1=1;
123770:>0:R1=1; 1:R1=1;
No


:::warning
從以上 4 個不同環境的實驗結果，可以看出只有在 VM 上實驗的結果與 `herd7`、`armmem` 和 `Raspberry 3 Model B+` 不同。
所以在真實的機器上進行實驗還是有必要的。
:::

## Mandatory barriers
[Uh-oh; it’s I/O ordering!](https://events.linuxfoundation.org/wp-content/uploads/2017/12/Uh-oh-Its-IO-Ordering-Will-Deacon-Arm.pdf) _{(page 19)} 提到了 mb(), rmb(), wmb()。

在 [memory-barrires.txt](https://www.kernel.org/doc/Documentation/memory-barriers.txt) 我們可以看到 Linux kernel 的 CPU memory barriers，屬於 mandatory barriers 的有 3 個：
- mb
- rmb
- wmb

關於 mandatory barriers，以下節錄自 [memory-barrires.txt](https://www.kernel.org/doc/Documentation/memory-barriers.txt)
> These barriers are required even on non-SMP systems as they affect
the order in which memory operations appear to a device by **prohibiting** both the
**compiler and the CPU** from **reordering** them.

簡單來說，mandatory barriers 禁止 compiler 和 CPU 進行 reordering。

不同的 CPU 對於禁止 CPU reordering 的 assembly 也不同，我們將分別探討 x64 和 arm。

### x64
我們先從這份文件了解一下 x64 的 memory ordering - [Intel® 64 Architecture Memory Ordering White Paper](http://www.cs.cmu.edu/~410-f10/doc/Intel_Reordering_318147.pdf)。

這份文件說明 x64 在 memory ordering 遵守 8 條原則，其中一條是：
> 2.3. Loads may be reordered with older stores to different locations

以下這個範例節錄自 [2.3](http://www.cs.cmu.edu/~410-f10/doc/Intel_Reordering_318147.pdf)
<table>
<tr>
<td>Processor 0</td>
<td>Processor 1</td>
</tr>
<tr style="background-color:white">
<td>mov [_x], 1 &nbsp; &nbsp;// M1</br>mov r1, [_y] &nbsp; // M2</td>
<td>mov [_y], 1 &nbsp; &nbsp;// M3</br>mov r2, [_x] &nbsp; // M4</td>
</tr>
<tr>
<td colspan=2>Initially x == y == 0</br>r1 == 0 and r2 == 0 <b>is allowed</b></td></tr>
</table>

[[2.3](http://www.cs.cmu.edu/~410-f10/doc/Intel_Reordering_318147.pdf)]
> At processor 0, the load **M2** and the store **M1** are to different locations and hence **may be reordered**

簡單來說，M1 和 M2 可能會被 reordering，M3 和 M4 也是。所以 ，如果沒有 memory barrier，**r1 == 0 and r2 == 0 是有可能會發生的**。

### memory barrier (x64)

接著我們看一下在 x64 下，如何阻止 CPU 進行 reordering

 __asm__ __volatile__("": : :"memory")

上面這一行代表什麼意思？
[GCC 9.1 Manual, 6.47.2.6 Clobbers and Scratch Registers](https://gcc.gnu.org/onlinedocs/gcc-9.1.0/gcc/Extended-Asm.html#Volatile-1) 這份線上文件對 memory 是這麼說的。
> Using the **"memory"** clobber effectively forms a read/write memory barrier for the compiler

<hr>

底下的實驗有用到 `smp_read_barrier_depends()`，所以，先看看 Linus Torvalds 在這篇 email 裡怎麼說 `smp_read_barrier_depends()` 的 [[`Re: Memory corruption due to word sharing`](https://lkml.org/lkml/2012/2/1/521)]。

<!--
## Lock-free
lock-free 所延伸的主題基本上如下圖：

digraph G {
rankdir="LR";

"ABA" [label = "ABA problem", shape="record"];

"Lockfree" [label="Lock-free", shape="record"];
"SpinLock" [label="Spin Lock", shape="record"];
"SeqLock" [label=" Sequential Lock", shape="record"];
"RCU" [label="Read-Copy Update (RCU)", shape="record"];
"USL" [label="Universal Scalability Law (USL)", shape="record"];
"semaphore" [label="semaphore", shape="record"];
rwlock [label="read-write lock (rwlock)", shape="record"];

ABA -> Lockfree;
Lockfree -> SpinLock;
Lockfree -> SeqLock;
Lockfree -> RCU;
RCU -> USL;
RCU -> semaphore;
RCU -> rwlock;
}

-->

<hr>

[Uh-oh; it's I/O ordering](https://elinux.org/images/a/a8/Uh-oh-Its-IO-Ordering-Will-Deacon-Arm.pdf) page 16，提到一個很有趣的 ordering rule **AXI**，什麼是 AXI 呢？
- [arm-smp-note](http://wiki.csie.ncku.edu.tw/embedded/arm-smp-note.pdf)

---

## [Snoop Control Unit, SCU](https://developer.arm.com/docs/100486/latest/snoop-control-unit/about-the-scu)
[Uh-oh; it's I/O ordering](https://elinux.org/images/a/a8/Uh-oh-Its-IO-Ordering-Will-Deacon-Arm.pdf) page 25 提到了 SCU，我們從 Arm 官方文件中看一下 SCU 是什麼。
- [Chapter 2 Snoop Control Unit](https://developer.arm.com/docs/100486/latest/snoop-control-unit)

### Reference
- [arm-smp-note](http://wiki.csie.ncku.edu.tw/embedded/arm-smp-note.pdf)

## Arm 如何支援 memory order？
Arm 將 memory types 分成三種：
1. Normal
2. Device
3. Strongly-ordered

### Reference
- [ ] [A3.5, Memory types and attributes and the memory order model](https://static.docs.arm.com/ddi0406/c/DDI0406C_C_arm_architecture_reference_manual.pdf#G7.4958320)

<hr>

## Linux kernel 如何支援 memory barrier？
研究 linux kernel 如何支援 memory barrier 的時候，這篇文章[` memory-barriers.txt `](https://www.kernel.org/doc/Documentation/memory-barriers.txt)是相當重要的參考資料。
### Device operations
舉一個例子來說明 device operation 失效的情境
[[` Example `]](https://www.kernel.org/doc/Documentation/memory-barriers.txt)
###### 初始條件：A 是 address port register；D 是　data port register

*A = 5;
x = *D;

上面兩行在實際執行的時候，可能會有兩種順序：
1. STORE *A = 5, x = LOAD *D
2. x = LOAD *D, STORE *A = 5

如果是第二個順序，由於 STORE 發生在 LOAD 之後，所以結果會是錯的。

### Memory order
memory order 到了 [C11 (<small>7.17.3 Orderand consistency</small>)](http://open-std.org/jtc1/SC22/wg14/www/docs/n1548.pdf#%5B%7B%22num%22%3A581%2C%22gen%22%3A0%7D%2C%7B%22name%22%3A%22XYZ%22%7D%2C0%2C792%2C0%5D) 才開始提供語言本身的規格 _{(C99 還沒有支援)}。我們看一下 Linux kernel 的 [memory-ordering model](https://lwn.net/Articles/718628/) 如何解決這個問題，這裡我們可以看到 `smp_read_barrier_depends`、`smp_mb` 和 `RCU`。

### [Memory barrier](https://en.wikipedia.org/wiki/Memory_barrier)
Memory barriers 有 4 種基本的分類
- Write memory barriers
- Data dependency barriers
- Read memory barriers
- General memory barriers

依照 [LINUX KERNEL MEMORY BARRIERS](https://www.kernel.org/doc/Documentation/memory-barriers.txt) 的說明，對記憶體的讀寫提供了幾條最低限度的保證，例如：
- 在任何一顆給定的CPU，記憶體的讀寫的順序都是照著 **固定** 的順序

[Memory access ordering part 2: Barriers and the Linux kernel](https://community.arm.com/processors/b/blog/posts/memory-access-ordering-part-2---barriers-and-the-linux-kernel) 這篇文章提到 linux kernel 如何使用 barrier 來處理 memory ordering 的問題。裡面提到一個例子來說明 barrier 的影響：

###### 初始條件: Store 1 和 Load 2 有 dependency

digraph g {
    rankdir = "RL";

  subgraph cluster_0 {
    color=white;
    label = "Program order";
    program_node [
        shape="record",color="white"
       label=<
         <table border="0" color="#000000" cellborder="1" cellspacing="0">
           <tr><td bgcolor="white">Load 0</td></tr>
           <tr><td bgcolor="lightblue">Store 1</td></tr>
           <tr><td bgcolor="black"><font color="lightblue">Load 2</font></td></tr>
           <tr><td bgcolor="white">Load 3</td></tr>
           <tr><td bgcolor="white">Store 4</td></tr>
         </table>>
      ];
  }
  
  subgraph cluster_1 {
    color=white;
    label = "Execution without barrier";
    without_barrier [
        shape="record",color="white"
       label=<
         <table border="0" color="#000000" cellborder="1" cellspacing="0">
           <tr><td bgcolor="black"><font color="lightblue">Load 2</font></td></tr>
           <tr><td bgcolor="white">Store 4</td></tr>
           <tr><td bgcolor="white">Load 0</td></tr>
           <tr><td bgcolor="white">Load 3</td></tr>
           <tr><td bgcolor="lightblue">Store 1</td></tr>
         </table>>
      ];
  };
  
   barrier[color="white"];
   
  subgraph cluster_2 {
    color=white;
    label = "Execution with barrier";
    with_barrier [
        shape="plaintext",color="white"
       label=<
         <table border="0" color="#000000" cellborder="1" cellspacing="0">
           <tr><td bgcolor="lightblue">Store 1</td></tr>
           <tr><td bgcolor="white">Load 0</td></tr>
           <tr><td port='port_one' bgcolor="black"></td></tr>
           <tr><td bgcolor="white">Store 4</td></tr>
           <tr><td bgcolor="black"><font color="lightblue">Load 2</font></td></tr>
           <tr><td>Load 3</td></tr>
         </table>>
      ];
  };
  
   with_barrier -> without_barrier -> program_node [color="white"];
   barrier -> with_barrier:port_one;
}

<!--
## 多少情況下需要等待「共享資源」？

## DMA barriers
### [Shared DMA Buffers](https://www.kernel.org/doc/html/v4.15/driver-api/dma-buf.html#shared-dma-buffers)

### [CPU Access to DMA Buffer Objects](https://www.kernel.org/doc/html/v4.15/driver-api/dma-buf.html#cpu-access-to-dma-buffer-objects)
-->

---

- [ ] [diy7](http://diy.inria.fr/): a tool suite for testing shared memory mode / [litmus](http://diy.inria.fr/tst/doc/litmus.html): a small parallel program designed to exercise the memory model of a parallel, shared-memory, computer.
* [Uh-oh; it's I/O ordering](https://elinux.org/images/a/a8/Uh-oh-Its-IO-Ordering-Will-Deacon-Arm.pdf) Page 10 - Page 14

- [ ] [Memory model](https://www.slideshare.net/YiHsiuHsu/memory-model-54215474)

- [ ] memory barrier
* [以 double-checked locking 為例，了解 memory barrier 的作用以及thread 之間何時會同步資料](https://medium.com/fcamels-notes/%E5%BE%9E-double-checked-locking-%E4%BA%86%E8%A7%A3-memory-barrier-%E7%9A%84%E4%BD%9C%E7%94%A8-bb151a359c1b)
* [簡介 C++11 atomic 和 memory order](https://medium.com/fcamels-notes/%E7%B0%A1%E4%BB%8B-c-11-memory-model-b3f4ed81fea6)
* [SC-DRF load/store 在各平台的實作](https://medium.com/fcamels-notes/sc-drf-load-store-%E5%9C%A8%E5%90%84%E5%B9%B3%E5%8F%B0%E7%9A%84%E5%AF%A6%E4%BD%9C-a96fe5bce4ba)
* [從硬體觀點了解 memory barrier 的實作和效果](https://medium.com/fcamels-notes/%E5%BE%9E%E7%A1%AC%E9%AB%94%E8%A7%80%E9%BB%9E%E4%BA%86%E8%A7%A3-memry-barrier-%E7%9A%84%E5%AF%A6%E4%BD%9C%E5%92%8C%E6%95%88%E6%9E%9C-416ff0a64fc1)

- [ ] [From Weak to Weedy: Effective Use of Memory Barriers in the ARM Linux Kernel](https://www.youtube.com/watch?v=6ORn6_35kKo) - W. Deacon, ARM
* 2013, ARMv7-A

- [ ] [Memory Barriers in the Linux Kernel: Semantics and Practices](https://elinux.org/images/a/ab/Bueso.pdf) - Davidlohr Bueso, SUSE
memory consistency model
sequential consistency (SC)
total store order (TSO)
- similar to SC, but loads may be reordered with writes
relaxed model: like ARM
Linux handles cpu's memory ordering specifics in portable way.
- execute in program order
- single variable consistency
- barrier operate in pair
- sufficient to implement synchronization primitives
barrier()
- prevent the compiler from getting smart
- with a loop foces the compiler to reload conditional variables: READ/WRITE_ONCE
implicit barrier
sleeping / waking

---

## DMA barriers

## Reference
* [Uh-oh; it's I/O ordering](https://elinux.org/images/a/a8/Uh-oh-Its-IO-Ordering-Will-Deacon-Arm.pdf)
* [Linux 核心設計: RCU 同步機制](https://hackmd.io/@sysprog/linux-rcu)
* [A Tutorial Introduction to the ARM and POWER Relaxed Memory Models](https://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test7.pdf)
* [Memory access ordering part 2: Barriers and the Linux kernel](https://community.arm.com/processors/b/blog/posts/memory-access-ordering-part-2---barriers-and-the-linux-kernel)
* [LINUX KERNEL MEMORY BARRIERS](https://www.kernel.org/doc/Documentation/memory-barriers.txt)
* [Linux-Kernel Memory Model](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0124r1.html)
* [Memory Barriers: a Hardware View for Software Hackers](http://www.puppetmastertrading.com/images/hwViewForSwHackers.pdf)
* [C11 規格書](http://open-std.org/jtc1/SC22/wg14/www/docs/n1548.pdf), 7.17.3 Orderand consistency
* [A formal kernel memory-ordering model (part 1)](https://lwn.net/Articles/718628/) [(part 2)](https://lwn.net/Articles/720550/)
* [Automatically Comparing Memory Consistency Models](https://johnwickerson.github.io/papers/memalloy.pdf)
* [A Promising Semantics for Relaxed-Memory Concurrency](https://people.mpi-sws.org/~viktor/papers/popl2017-promising.pdf)
* [Memory Barriers in the Linux Kernel - eLinux.org](https://elinux.org/images/a/ab/Bueso.pdf)
* Wikipedia: [Consistency model](https://en.wikipedia.org/wiki/Consistency_model)
* [Frightening small children and disconcerting grown-ups:Concurrency in the Linux kernel](http://diy.inria.fr/linux/long.pdf)
* [SMP, Multicore, Memory Ordering & Locking](https://www.cse.unsw.edu.au/~cs9242/18/lectures/08-smp_locking.pdf)
* Wikipedia: [MESI protocol](https://en.wikipedia.org/wiki/MESI_protocol)
* [A Calculus for Relaxed Memory](https://www.cs.cmu.edu/~crary/papers/2015/rmc.pdf)
* [Bus-Independent Device Accesses](https://www.kernel.org/doc/html/v4.15/driver-api/device-io.html)
* [從 memory model 的角度探討 Linux kernel 在 concurrency 的行為](https://coscup.org/2019/programs/9bad941c-01a4-4161-96b9-63955467d180/)