owned this note
owned this note
Published
Linked with GitHub
從 memory model 的角度探討 Linux kernel 在 concurrency 的行為 - 翁敏維
===
{%hackmd LcL4-VI0SGitSiINTuy4rA %}
>
---
[簡報模式](https://hackmd.io/@butastur/coscup-2019-linux-kernel)
## Agenda
- Introduction
- What is reorder?
- What is memory model?
- How Linux kernel supports concurrency?
---
## Introduction
這裡會從 out-of-order、reordering 一路探討到 memory model,並以實驗來理解 atomic operation、memory barrier。
然後我們會看到 linux kernel 怎麼支援 concurrency,例如 membarrier。
---
## What is reorder?
----
<small>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) 中提到:</small>
<small>初始條件:*x, *y 在記憶體裡,初始值為 0,foo, bar 是 local variable</small>
```graphviz
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]
}
```
<small>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 的結果 <font color='red'>有沒有可能會是 foo == bar == 0?</font></small>
----
<font color='red'>為什麼要探討 reordering?</font>
<small>看起來和 linux kernel 無關,也看不出和 concurrency 有關。</small>
----
- reorder 有兩個層級
- Compiler 對 source code
- CPU 執行 instruction
- reordering 後的結果<font color='red'>未必是 100% 正確</font>
- 透過 memory barrier 控制 reordering
- linux kernel 對 memory order、memory barrier 有不同程度的支援
----
#### 為什麼執行順序和 program order 不一樣?
<small>當我們看到執行結果的時候,<br>對照一下 **program order 所預期的結果**,<font color='red'>為什麼不一樣?</font></small>
----
#### In-order and Out-of-Order
- in-order
- out-of-order
<small>我們從這兩種順序來看 CPU 執行順序對效能及<font color='red'>正確性</font>的影響</small>
----
#### in-order
```
1 2 3 4 5 6 7 8
fetch | fetch1 fetch2
decode | decode1 decode2
execute | execute1 execute2
write-back | write1 write1
```
當 processor 是用 in-order 在執行 instruction,<br>執行 2 個 instruction 需要 8 個 cycle。
----
#### out-of-order
```
1 2 3 4 5
fetch | fetch1 fetch2
decode | decode1 decode2
execute | execute1 execute2
write-back | write1 write1
```
<small>如果是 out-of-order,執行 2 個 instruction 只需要 5 個 cycle。</small>
- <small>在上一個指令的 cycle 完整的執行完之前,下一個指令是有可能已經開始執行了。</small>
- <small>execute2 比 write1 還早執行,<font color='red'>這樣會有正確的結果嗎?</font></small>
----
### diy, litmus, armmem
<small>我們用這個工具來作一些實驗</small>
----
- [diy](http://diy.inria.fr/)、[litmus](http://diy.inria.fr/doc/litmus.html) 是由 [INRIA](https://www.inria.fr/en/) (法國國家資訊與自動化研究所) 開發的一套可檢驗 memory model 的工具。
- [litmus](http://diy.inria.fr/doc/litmus.html) 是用來測試 [diy](http://diy.inria.fr/) 所產生的 test case。
<small>linux kernel 使用 litmus 在檢驗 [memory-ordering model](https://lwn.net/Articles/720550/)。</small>
- [armmem](https://www.cl.cam.ac.uk/~pes20/ppcmem/help.html) 是由 INRIA 和劍橋大學的一套檢驗 memory model 的工具。
----
為什麼突然講到 litmus 呢?
----
linux kernel 在檢驗 memory model 的時候,也是需要工具,這些工具包括了 diy, litmus, armmem。
----
- 如果從 C/C++ 檢驗 memory model,<br>還有一個工具 [cppmem](http://svr-pes20-cppmem.cl.cam.ac.uk/cppmem/help.html)
- cppmem 是由劍橋大學 The Computer Laboratory 所開發,以 web 為介面。
----
### litmus 是在模擬什麼?
- reordering 有兩種層次
- Compiler reordering
- CPU reordering
- [litmus](http://diy.inria.fr/doc/litmus.html) 是在模擬 CPU reordering
----
#### 怎麼使用 diy, litmus 作實驗?
----
<small>用 diy 產生 test case</small>
```shell
$ 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
```
<small>透過修改 X.conf,可以產生 test case 來模擬 ARM 或是 x86</small>
----
<small>產生了 6 個 test case:arm000.litmus, arm001.litmus, ..., arm005.litmus</small>
然後就可以用 litmus 作實驗
```shell
$ litmus7 arm000.litmus -o arm000
```
----
litmus7 的 output 有一個 `arm000.c`,我們在這個檔案裡可以看到
```clike
/* Full memory barrier */
inline static void mbar(void) {
asm __volatile__ ("dsb sy" ::: "memory");
}
```
- 這裡看到了 <font color='red'>memory barrier</font> 和 dsb。
- linux kernel 支援什麼 memory barrier?
- 不同的 CPU 架構對 memory barrier 有什麼不同程度的支援?
----
探討 memory barrier 之前,我們先看 store buffer
----
#### What is store buffer?
----
在沒有 `store buffer` 之前,CPU 會直接對 cache 進行 `load` / `store`,像以下這張圖這樣。
```graphviz
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;
}
```
<small>[Memory Barriers: a Hardware View for Software Hackers](http://www.puppetmastertrading.com/images/hwViewForSwHackers.pdf)</small>
----
有了 store buffer
```graphviz
digraph G {
{ rank = same; cpu0; cpu1 }
{ rank = same; cache0; cache1 }
{ rank = same; interconnect0; interconnect1; interconnect_mid }
cpu0 [shape=square;label="CPU 0";fontsize=12];
cache0 [shape=square;label="Cache";fontsize=10];
sb0 [shape=square;label="Store \rBuffer";fontsize=10];
cpu0 -> sb0 -> cache0;
cache0->cpu0;
cpu1 [shape=square;label="CPU 1";fontsize=12];
cache1 [shape=square;label="Cache";fontsize=10];
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";fontsize=10];
interconnect_mid-> memory;
}
```
- <small>`load` 會先從 cache 去讀。</small>
- <small>`store` 並不是直接寫入 cache,而是把 `store` 先放進 store buffer。</small>
- <small>用 GraphViz 重畫後,位置和[原圖](http://www.puppetmastertrading.com/images/hwViewForSwHackers.pdf) 有點不一樣,不過概念是一樣的。</small>
----
#### Data Memory Barrier (DMB)
因為是以 Arm 做實驗,所以我們先說明 DMB
----
#### [Data Memory Barrier (DMB)](https://developer.arm.com/docs/100941/latest/barriers)
<small>This prevents reordering of data accesses instructions across the DMB instruction</small>
<small>It also ensures that any explicit preceding data or unified cache maintenance operations have <font color='lightblue'>completed</font> before any subsequent data accesses are executed</small>
<small>以上節錄自 Arm 官方文件</small>
- <small>避免 dmb 之後的 instruction 被 reordering</small>
- <small>completed 的意思就是 instruction 的 pipeline 已經執行到 write back</small>
----
<small>這個範例來自於 Professor Peter Sewell <br>(劍橋大學 [Computer Laboratory](http://www.cl.cam.ac.uk/))</small>
```
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)
```
<small>[[SB+dmbs](https://www.cl.cam.ac.uk/~pes20/arm-supplemental/arm040.html#tst@SB+dmbs)]</small>
<small>我們將分別用 litmus7、armmem 來對 SB+dmbs 作實驗。</small>
----
- [litmus](http://diy.inria.fr/doc/litmus.html) 是由 [INRIA](https://www.inria.fr/en/) (法國國家資訊與自動化研究所) 開發的一套可檢驗 memory model 的工具。
- linux kernel 使用 litmus 檢驗不同的 [memory-ordering model](https://lwn.net/Articles/720550/#Specifying%20a%20Memory%20Model%20in%20Terms%20of%20Prohibited%20Cycles)
----
#### litmus7 實驗結果
```bash=
#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
```
- <small>從第 14 行我們看到 `0:R1=0; 1:R1=0`,原因之後會說明</small>
- <small>dmb 之後的 instruction 沒有被 reordering</small>
----
- [ppcmem/armmem](https://www.cl.cam.ac.uk/~pes20/ppcmem/help.html) 是由 INRIA 和劍橋大學共同開發的一套檢驗 memory model 的工具,以 web 為介面。
- Linux kernel 也有使用 ppcmem 在檢驗 memory barrier 和 atomic instruction <small>[Validating Memory Barriers and Atomic Instructions](https://lwn.net/Articles/470681/)</small>
----
#### [armmem](https://www.cl.cam.ac.uk/~pes20/ppcmem/index.html#ARM-SB+dmbs) 實驗結果
```bash=
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
```
- <small>沒有看到 `0:R1=0; 1:R1=0`</small>
- <small>dmb 之後的 instruction 沒有被 reordering</small>
----
為什麼 litmus7 和 armmem 實驗的結果<font color='red'>不一樣?</font>
----
- 因為 litmus7 和 armmem 模擬的層級不一樣。
- armmem 並不是真的在一顆 CPU 上執行 instructions,所以,<font color='red'>不會再另外模擬沒有 atomic operation</font> 的結果。
----
暫停一下,目前為止的實驗是要證明什麼事?
----
- 在 litmus7 和 armmem 上的實驗,都是在證明 dmb 之後的 instruction 沒有被 reordering
- litmus7 和 armmem 的測試結果都是正確的。
- litmus7 是真的在 CPU 上執行,可以看到 <font color='red'>沒有 atomic operation</font> 的結果。
這裡說明了 atomic operation 的必要性。
----
### What is atomic operation?
----
以 Arm 架構的指令 (`ldrex`、`strex`) 探討 atomic
```clike=
__asm__ __volatile__(
"1: ldrex %0, [%3]\n"
" add %1, %0, %4\n"
" strex %2, %1, [%3]\n"
" teq %2, #0\n"
" bne 1b"
: "=&r" (lockval), "=&r" (newval), "=&r" (tmp)
: "r" (&lock->slock), "I" (1 << TICKET_SHIFT)
: "cc");
```
<small>以上節錄自 [spinlock](https://github.com/torvalds/linux/blob/master/arch/arm/include/asm/spinlock.h#L63)</small>
----
從這 3 個角度來理解 atomic operation
- Mutual exclusion
- Dekker's algorithm
- Exclusive Monitors
----
#### Mutual exclusion
- 這裡我們探討的 mutual exclusion 是指電腦科學的一個問題 race condition,並不是在探討 mutex,<font color='blue'>mutex 只是其中一種解法</font>。
- 以 critical section 來解決 race condition <font color='red'>會有什麼問題?</font>
- critical section 可能造成 deadlocks 和 resource starvation。
----
#### Mutual exclusion
- 解法有硬體和軟體兩種解法。
- 硬體解法包括 atomic operation、busy-wait ...。
- 軟體解法有 spinlock、RCU ...。
----
#### [Dekker's algorithm](https://en.wikipedia.org/wiki/Dekker%27s_algorithm)
> Dekker's algorithm is the first known correct solution to the mutual exclusion problem
<small>[[wiki](https://en.wikipedia.org/wiki/Dekker%27s_algorithm)]</small>
- Dekker's algorithm 有效率低落的問題,現代的處理器已不採用
- `process` <font color='blue'>不是 `processor`</font>
----
#### [Dekker's algorithm](https://en.wikipedia.org/wiki/Dekker%27s_algorithm)
- 透過 busy wait 的方式,讓任何時候<font color='blue'>最多只能有一個</font> `process` 進入 `critical section`
- 如果已經有一個 `process` 進入了 `critical section`,下一個要進入 `critical section` 的 `process` 就會 <font color='red'>busy wait</font>,直到 P0 離開了 `critical section` <small>(**假設 P0** 先進入 `critical section`)</small>
----
busy wait 會有什麼問題?
----
- busy wait 對效能是有影響的
- `busy wait` 表示起碼會有一個 <font color='red'>最低限度的時間</font> 是花在 <font color='red'>等待</font> 其他 process 離開 `critical section`。
----
#### [Exclusive Monitors](https://developer.arm.com/docs/100934/latest/exclusive-monitors)
- [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 有兩種狀態:
`open` 和 `exclusive`。
* load-exclusive 會把 exclusive monitor 的狀態改成 <font color='blue'>exclusive</font>。
* store-exclusive 只有當 exclusive monitor 的狀態是 exclusive 的時候 store 才會成功。
----
load <font color='red'>進行中</font>的時候無法 store
----
如果 <font color='red'>存在</font> 著一個 exclusive monitor <font color='red'>還沒有</font> **把狀態改成 exclusive**,那麼 store 就不會成功。
----
```clike=
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)
```
<font style='font-size:14px'>Reference:https://www.cl.cam.ac.uk/~pes20/arm-supplemental/arm040.html#tst@SB+dmbs</font>
- <small>當第 10 行的 `STR R0, [%x0]`、`STR R0, [%y1]` 都 <font color='red'>尚未 complete</font>,第 12 行的 `LDR R1, [%y0]`、`LDR R1, [%x1]` 卻同時執行,會是什麼結果?</small>
- <small>dmb 保證 P0 的 LDR 沒有被 reordering,也保證了 P1 的 LDR 沒有被 reordering,但是少了 atomic,所以仍然有可能發生 <font color='red'>P0: R1=0; P1: R1=0</font></small>
----
回顧一開始的範例
```graphviz
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]
}
```
<small><font color='red'>WRITE_ONCE、READ_ONCE 是 atomic operation 嗎?</font></small>
---
### What is memory model?
----
memory model 和 linux kernel 有什麼關係?
memory model 和 concurrency 有什麼關係?
----
### Memory model
不同的 CPU 會有不一樣的 memory model<br>
我們分別探討 x64 和 Arm
----
#### x64
<small>[Intel® 64 Architecture Memory Ordering White Paper](http://www.cs.cmu.edu/~410-f10/doc/Intel_Reordering_318147.pdf) 對於 memory ordering 有 8 條 principle ,這裡舉其中一個例子</small>
:::info
2.3. Loads may be reordered with older stores to different locations
:::
<table>
<tr style='font-size:22px'>
<td>Processor 0</td>
<td>Processor 1</td>
</tr>
<tr>
<td style='border:solid;font-size:24px'>mov [_x], 1 // M1</br>mov r1, [_y] // M2</td>
<td style='border:solid;font-size:24px'>mov [_y], 1 // M3</br>mov r2, [_x] // M4</td>
</tr>
<tr style='font-size:24px'>
<td colspan=2>Initially x == y == 0</br>r1 == 0 and r2 == 0 <b>is allowed</b></td></tr>
</table>
<small>Reference:
http://www.cs.cmu.edu/~410-f10/doc/Intel_Reordering_318147.pdf</small>
----
[Volumn 3A, 8.2 MEMORY ORDERING](
https://software.intel.com/sites/default/files/managed/7c/f1/253668-sdm-vol-3a.pdf)
<small>我們以這個例子來看 strong memory model</small>
:::info
8.2.3.3 Stores Are Not Reordered With Earlier Loads
:::
<table>
<tr style='font-size:24px'>
<td>Processor 0</td>
<td>Processor 1</td>
</tr>
<tr>
<td style='border:solid;font-size:26px'>mov r1,[_x] // M1</br>mov [_y], 1 // M2</td>
<td style='border:solid;font-size:26px'>mov r2, [_y] // M3</br>mov [_x], 1 // M4</td>
</tr>
<tr style='font-size:24px'>
<td colspan=2>Initially x == y == 0</br>r1 == 1 and r2 == 1 <b>is not allowed</b></td></tr>
</table>
<small>Reference:
https://software.intel.com/sites/default/files/managed/7c/f1/253668-sdm-vol-3a.pdf</small>
<small>M2 不會 reordering,M4 也不會 reordering</small>
----
#### Arm
這裡以 [ARMv8A](https://developer.arm.com/docs/100941/latest/the-memory-model) 為例來說明 weakly ordered model
----
### weakly memory model
:::info
the order of memory accesses is **not necessarily** required to be the same as the program order for load and store operations.
:::
<small>Reference:
https://developer.arm.com/docs/100941/latest/the-memory-model
</small>
<small>load 和 store 的順序不一定要和 program order 一樣</small>
<!--
#### Memory model
- 關於 linux kernel 如何支援 memory model,目前最新的文件是 [Linux-Kernel Memory Model, P0124R5](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0124r6.html)。
- [Linux-Kernel Memory Model, P0124R5](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0124r6.html) 這份文件對於 memory model、atomic 在 C11、C++11 和 linux kernel 上的實作有深入的比較和說明。
-->
---
### How Linux kernel supports concurrency?
這份文件 <small>[User-space RCU: Memory-barrier menagerie](https://lwn.net/Articles/573436/)</small> 是由 Paul E. McKenney, Mathieu Desnoyers, Lai Jiangshan, and Josh Triplett 所發表,我們先從這份文件澄清對 memory barrier 的一些誤會。
----
- Memory barriers are not a way of making prior memory accesses <font color='red'>get done faster</font>.
- Memory barriers are not fairy dust that magically makes your <font color='red'>concurrent program work correctly</font>.
<small>Reference:
https://lwn.net/Articles/573436/</small>
----
- Memory barriers are not a mechanism that commits prior stores to <font color='red'>main memory</font>.
<small>Reference:
https://lwn.net/Articles/573436/</small>
----
- [membarrier](http://man7.org/linux/man-pages/man2/membarrier.2.html)
membarrier 是一個 system call,從Linux 4.3 才開始加入
----
#### Barrier
:::info
The ARM architecture includes barrier instructions to force access ordering and access completion at a specific point.
:::
<small>Reference:
https://developer.arm.com/docs/100941/latest/barriers</small>
---
## Reference
- [ ] [Uh-oh; it's I/O ordering](https://elinux.org/images/a/a8/Uh-oh-Its-IO-Ordering-Will-Deacon-Arm.pdf)
- [ ] [Linux memory-barrier.txt](https://www.kernel.org/doc/Documentation/memory-barriers.txt)
- [ ] [diy7: a tool suite for testing shared memory model](http://diy.inria.fr/)
- [ ] [litmus: a small parallel program designed to exercise the memory model of a parallel, shared-memory, computer.](http://diy.inria.fr/tst/doc/litmus.html)
- [ ][Jserv與他愉快的小夥伴](https://www.facebook.com/JservFans/?epa=SEARCH_BOX)
- [ ] [membarrier - issue memory barriers on a set of threads](http://man7.org/linux/man-pages/man2/membarrier.2.html)
- [ ] [Concurrency in The Linux Kernel](https://hackmd.io/@VIRqdo35SvekIiH4p76B7g/Hy9JyrBw?type=view)
---
END
----
###### tags: `COSCUP2019` `系統軟體社群議程` `IB201`