I/O ordering 學習紀錄

contributed by < jserv, jeffrey.w >

Arm 工程師 Will Deacon 在 Edinburgh 的演講 Uh-oh; it's I/O ordering 中提到一個範例：

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

先看一下 WRITE_ONCE / READ_ONCE，這兩個 macros 所作的事絕對不只字面上所說的 write / read 而己，我們看一下這段註解

The compiler is also forbidden from reordering successive instances of READ_ONCE and WRITE_ONCE, …

這兩個 macros 其實有用到 barrier_[1] _[2] 來處理 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 個問題：

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

範例中的 *x, *y 這種「共享資源」要如何取得讀寫的共識？
reordering 一定會發生嗎？
如何改變 memory order？

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

[實驗紀錄]

diy: Design and Test Weak Memory Models

diy 是由 INRIA (法國國家資訊與自動化研究所) 開發的一套可檢驗 memory model 的工具，對於模擬不同 CPU 架構的執行結果很有用，因為 compiler 將 C compile 成 assembly 雖然可以看出 compiler 在 reordering 上作了什麼最佳化，但少了 litmus，就很難模擬出 CPU 在 reordering 上作了什麼最佳化。

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

先看一下這個範例 SB.litmus

[source]

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 來看，有 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

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

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

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

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

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

=-=- 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 差不多

Witnesses
Positive: 41, Negative: 999959

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

"litmus" 這字是「石蕊」的意思，是一種藍色色素，分子式C₇H₇O₄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");
}

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

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

用 GraphViz 重畫後，位置和原圖 _{[page 7]} 有點不一樣，不過概念是一樣的。

在 COSCUP 上有人提問，store buffer 之間有沒有 coherence 的問題？
Jeffrey.WFri, Aug 23, 2019 5:36 AM

關於 store buffer，先看一個基於 Dekker Protocol 的例子。Dekker's algorithm 是第一個被驗證 mutual exclusion 的解法，但因為效率低落，現代電腦系統不採用。

出處：Weak Consistency (TSO as an Example), page 51

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，是透過 busy wait 的方式，讓任何時候最多只能有一個 process 進入 critical section _{(Dekker's algorithm 是在講 process，不是 processor)}。
也就是說，如果已經有一個 process _{(假設是 P0)} 進入了 critical section，下一個要進入 critical section 的 process 就會 busy wait，直到 P0 離開了 critical section _{(假設是 P0 先進入 critical section)}。

回到這個範例

[source]

我們先從 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, dsb 和 isb。

ARM® Compiler armasm User Guide, Version 5.06 對於 dmb 裡有這麼一段文字

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)

[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 和 dsbs，仍然看到 0:R1=0; 1:R1=0;。

重新看一下 litmus7 產生的 assembly，再對照一下 Arm 的文件。

第 4 行和第 9 行看到 dmb sy，在 ARMv8-A Memory systems 裡，對 sy 是這麼說的

Full system operation. This is the default and can be omitted.

我們再完整的看一下 dmb 是什麼

It also ensures that any explicit preceding data or unified cache maintenance operations have completed before any subsequent data accesses are executed.

對照一下 dsb

… 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 是一套基於 web 介面，用來測試 memory model 的工具，我試著在上面實驗一下 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 在 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]。

Completion

Uh-oh; it’s I/O ordering! page 14 對 ordering 和 completion 作了一個比較。

Arm instructions - DMB、DSB and ISB

底下會繼續探討 dmb、dsb and isb，所以回顧一下 ARM® Compiler armasm User Guide Version 5.06 裡相關的說明 _{[Chapter 11 ARM and Thumb Instructions]}。

Data Memory Barrier (DMB)

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

Data Synchronization Barrier (DSB)

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

在我們使用 Exclusive Monitors 來進行 litmus7 的實驗之前，我們看一下 Arm 的 exclusive monitors 和 LDREX / STREX。

Exclusive monitors

Arm 在 Exclusive monitors 的實作上分為兩種 local monitor 和 global monitor。以下這個架構節錄自 Arm Information Center，說明 local monitor 和 global monitor 各自出現在什麼地方。
[source]

Exclusive monitors 有兩種狀態：open 和 exclusive：

load-exclusive 會把 exclusive monitor 的狀態改成 exclusive。
store-exclusive 只有當 exclusive monitor 的狀態是 exclusive 的時候 store 才會成功。
所以，load 進行中的時候無法 store。
也就是說，如果存在著一個 exclusive monitor 還沒有 把狀態改成 exclusive，那麼 store 就不會成功。

[source]

A Store-Exclusive can succeed only if all accessed exclusive monitors are in the exclusive state.

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

實驗紀錄

Example below is from Professor Peter Sewell (University of Cambridge Computer Laboratory)
[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
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 在 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 模擬

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

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

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

Mandatory barriers

Uh-oh; it’s I/O ordering! _{(page 19)} 提到了 mb(), rmb(), wmb()。

在 memory-barrires.txt 我們可以看到 Linux kernel 的 CPU memory barriers，屬於 mandatory barriers 的有 3 個：

關於 mandatory barriers，以下節錄自 memory-barrires.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。

這份文件說明 x64 在 memory ordering 遵守 8 條原則，其中一條是：

2.3. Loads may be reordered with older stores to different locations

以下這個範例節錄自 2.3

Processor 0	Processor 1
mov [_x], 1 // M1 mov r1, [_y] // M2	mov [_y], 1 // M3 mov r2, [_x] // M4
Initially x == y == 0 r1 == 0 and r2 == 0 is allowed

[2.3]

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 這份線上文件對 memory 是這麼說的。

Using the "memory" clobber effectively forms a read/write memory barrier for the compiler

底下的實驗有用到 smp_read_barrier_depends()，所以，先看看 Linus Torvalds 在這篇 email 裡怎麼說 smp_read_barrier_depends() 的 [Re: Memory corruption due to word sharing]。

Uh-oh; it's I/O ordering page 16，提到一個很有趣的 ordering rule AXI，什麼是 AXI 呢？

arm-smp-note

Snoop Control Unit, SCU

Uh-oh; it's I/O ordering page 25 提到了 SCU，我們從 Arm 官方文件中看一下 SCU 是什麼。

Chapter 2 Snoop Control Unit

Reference

arm-smp-note

Arm 如何支援 memory order？

Arm 將 memory types 分成三種：

Normal
Device
Strongly-ordered

Reference

A3.5, Memory types and attributes and the memory order model

Linux kernel 如何支援 memory barrier？

研究 linux kernel 如何支援 memory barrier 的時候，這篇文章memory-barriers.txt是相當重要的參考資料。

Device operations

舉一個例子來說明 device operation 失效的情境
[Example]

初始條件：A 是 address port register；D 是　data port register

*A = 5;
x = *D;

上面兩行在實際執行的時候，可能會有兩種順序：

STORE *A = 5, x = LOAD *D
x = LOAD *D, STORE *A = 5

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

Memory order

memory order 到了 C11 (7.17.3 Orderand consistency) 才開始提供語言本身的規格 _{(C99 還沒有支援)}。我們看一下 Linux kernel 的 memory-ordering model 如何解決這個問題，這裡我們可以看到 smp_read_barrier_depends、smp_mb 和 RCU。

Memory barrier

Memory barriers 有 4 種基本的分類

Write memory barriers
Data dependency barriers
Read memory barriers
General memory barriers

依照 LINUX KERNEL MEMORY BARRIERS 的說明，對記憶體的讀寫提供了幾條最低限度的保證，例如：

在任何一顆給定的CPU，記憶體的讀寫的順序都是照著固定的順序

Memory access ordering part 2: Barriers and the Linux kernel 這篇文章提到 linux kernel 如何使用 barrier 來處理 memory ordering 的問題。裡面提到一個例子來說明 barrier 的影響：

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

diy7: a tool suite for testing shared memory mode / litmus: a small parallel program designed to exercise the memory model of a parallel, shared-memory, computer.

Uh-oh; it's I/O ordering Page 10 - Page 14

Memory model
memory barrier

From Weak to Weedy: Effective Use of Memory Barriers in the ARM Linux Kernel - W. Deacon, ARM

2013, ARMv7-A

Memory Barriers in the Linux Kernel: Semantics and Practices - 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

Jim Huang

2019/07/28 12:41:56

改用 GraphViz 重新製圖 (Edited)

2019/08/08 14:12:23

TODO: 附上 Dekker's Algorithm 的說明，這是第一個被驗證 mutual exclusion 的解法，但因為效率低落，現代電腦系統不採用 (Edited)

2019/08/08 14:13:15

TODO: 不該隨意用一句話「簡單來說」涵蓋經典演算法，否則後文難以銜接 (Edited)

2019/08/08 14:15:18

TODO: Arm 的官方文件連結已變更 (Edited)

2019/08/08 14:15:54

釐清 Thumb2 vs. Thumb 對於 dsb 指令的支援程度 (Edited)

2019/08/08 14:16:45

TODO: 改用最新的 gcc 文件連結: https://gcc.gnu.org/onlinedocs/ (Edited)

I/O ordering 學習紀錄

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

diy: Design and Test Weak Memory Models

Store Buffer

實驗 litmus7

延伸實驗

Completion

Arm instructions - DMB、DSB and ISB

Data Memory Barrier (DMB)

Data Synchronization Barrier (DSB)

Exclusive Monitors

Exclusive monitors

實驗紀錄

在 x86 上用 herd7 模擬

在 VM 上實驗

用 armmem 模擬

在 Raspberry Pi 3 Model B+ 上實驗 Store buffer + dmb

Mandatory barriers

x64

memory barrier (x64)

Snoop Control Unit, SCU

Reference

Arm 如何支援 memory order？

Reference

Linux kernel 如何支援 memory barrier？

Device operations

初始條件：A 是 address port register；D 是 data port register

Memory order

Memory barrier

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

DMA barriers

Reference

Read more

Experiments on Concurrency - Happens-before

Design patterns 筆記 - Strategy pattern on C++

Notes on Java8 Stream and Lambda expression

從 [C++11 規格](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3376.pdf#chapter.14) 學習 C++ Templates — 第一篇

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

在 x86 上用 `herd7` 模擬

初始條件：A 是 address port register；D 是　data port register