# 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 ```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] } ``` 先看一下 [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<sub> [[1]](https://github.com/torvalds/linux/blob/master/include/linux/compiler.h#L223)</sub> <sub> [[2]](https://github.com/torvalds/linux/blob/master/include/linux/compiler.h#L261)</sub> 來處理 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) 安裝。初次使用請輸入以下命令: ```shell $ 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,確認升級到最新版本: ```shell $ opam switch --all $ opam update $ opam upgrade ``` 接著執行以下命令,安裝 herdtools7: ```shell $ opam install herdtools7 ``` 再用 litmus7 測試: ```shell $ 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` 測試: ```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 $ 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 的硬體環境中,否則會出現以下錯誤: ```shell /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` 的內容: ```shell $ litmus7 arm000.litmus -o arm000 ``` `arm000.c` 的內容: ```clike /* 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) ```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; } ``` 但是有了 `store buffer`,情況就有點不一樣了。簡單來說,就是`load` 會先從 cache 去讀 <sub>(這裡省略了對 [MESI protocol](https://en.wikipedia.org/wiki/MESI_protocol) 的描述,後面會再提到 MESI)</sub>,但是 `store` 的時候,並不是直接對 cache 寫入,而是把 `store instruction` 先放進 store buffer。 用 GraphViz 重畫後,位置和原圖 <sub>[[page 7](http://www.puppetmastertrading.com/images/hwViewForSwHackers.pdf)]</sub> 有點不一樣,不過概念是一樣的。 ```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"]; 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` <sub>(Dekker's algorithm 是在講 `process`,<font color='blue'>不是 `processor`)</font></sub>。 也就是說,如果已經有一個 `process` <sub>(**假設是 P0**)</sub> 進入了 `critical section`,下一個要進入 `critical section` 的 `process` 就會 `busy wait`,直到 P0 離開了 `critical section` <sub>(**假設是 P0** 先進入 `critical section`)</sub>。 回到這個範例 [[source](https://elinux.org/images/a/a8/Uh-oh-Its-IO-Ordering-Will-Deacon-Arm.pdf)] ```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] } ``` 我們先從 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 的實驗來看,~~{**b, d**, a, c} 是**確實存在著發生的可能性**的。也就是說,~~**foo == bar == 0** 是可能會發生的。 :::danger 這段重新審視後,**foo == bar == 0** 之所以會發生,並不是因為有了這個執行順序 {**b, d**, a, c} > [name=jeffrey.w][time=Sun, Sep 27, 2020 11:07 PM] ::: 在這個例子中,也許我們會想要在某種程度上對 **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 跑了一下,得到這個結果 ```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 ``` 從第 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;`。 > 我以為加了 dmb 就可以保證「**會等到 dmb 之前的 store 都 complete 才會開始 dmb 之後的 load**」,但從結果來看,**顯然我對 dmb 的理解並不完整**,同時我也**誤解了 SB+dmbs 這個實驗的重點**。 > [name=Jeffrey.W][time=Sat, Aug 3, 2019 6:00 AM] 重新看一下 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),得到的結果是這樣 ```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 ``` >:question: 目前看起來,[SB+dmbs](https://www.cl.cam.ac.uk/~pes20/arm-supplemental/arm040.html#tst@SB+dmbs) 在 litmus7 和 armmem 上測試的結果並不一樣,這是為什麼呢? > [name=Jeffrey.W][time=Sat, Aug 3, 2019 10:00 AM] >> 其實是因為 litmus7 和 armmem 是建立在不同層級的測試基礎上,armmem 的測試基礎是**順序**(而且是 bare metal),而 litmus7 還包括了 atomic operation。再簡單一點的說,就是在 litmus7 上的測試還必須使用 atomic operation 才可以解決 reordering 的問題。 >> [name=Jeffrey.W][time=Sun, Aug 4, 2019 5:03 PM] >>> 畢竟 litmus7 是在 VM 上跑的,為了讓實驗更接近真實,我找一塊 Arm 的版子來實驗看看,同時再試一下其他情境 >>> [name=Jeffrey.W][time=Sun, Oct 13, 2019 4:37 AM] - 在 litmus7 和 armmem 上的實驗,都是在證明 dmb 之前的 instruction 不會在 dmb 執行了之後才執行。 <!-- - litmus7 是真的在 CPU 上執行,所以,可以看到由於沒有導入 atomic operation,因此仍然會有 `0:R1=0; 1:R1=0`。 - 而 armmem 並不是真的在一顆 CPU 上執行這些 instructions,所以,不會再另外模擬沒有 atomic operation 的結果。 --> > 畢竟我是在 VM 上跑 litmus7 的,為了讓實驗更接近真實,我找一塊 Arm 的版子再來實驗看看 > [name=Jeffrey.W][time=Sun, Oct 13, 2019 4:39 AM] ### 延伸實驗 關於 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 裡相關的說明 <sub>[[Chapter 11 ARM and Thumb Instructions](http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.dui0473m/dom1361289871865.html)]</sub>。 ### 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 ```cpp 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)] ![](https://i.imgur.com/hnSOBsV.png) 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)] ```shell 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` 的結果如下 ```shell $ 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 上實驗 ```shell #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) 模擬 ```shell 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** ::: ```shell $ 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 ``` ![](https://i.imgur.com/Q2ncTZx.png) :::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) <sub>(page 19)</sub> 提到了 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 ```c __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 所延伸的主題基本上如下圖: ```graphviz 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) 才開始提供語言本身的規格 <sub>(C99 還沒有支援)</sub>。我們看一下 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 ```graphviz 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 同步機制](http://hackfoldr.org/linux/https%253A%252F%252Fhackmd.io%252Fs%252FH19V4eyfV) - [ ] [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 規格書, 7.17.3 Orderand consistency](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) - [ ] [A formal kernel memory-ordering model (part 1)](https://lwn.net/Articles/718628/) - [ ] [A formal kernel memory-ordering model (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) - [ ] [Consistency model, wikipedia](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) - [ ] [MESI protocol, wikipedia](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/) ###### tags: `I/O ordering` `io ordering` `memory ordering` `memory order` `memory model` `memory barrier` `arm` `diy` `litmus` `armmem`