# Arm Programmer's Guide X - Memory Ordering 學習筆記
<h1>1. 前言 </h1>
此筆記為學習 [ARM® Cortex™-A Series Programmer's Guide
Version: 4.0 中第十章 Memory Ordering ](https://developer.arm.com/documentation/den0013/d/Memory-Ordering?lang=en) 的心得筆記。主旨在解釋 Armv7 對於記憶體存取 (Memory access) 順序的行為。
會需要特別一章節來解釋是因為一般來說 (在 Normal 類型的記憶體區段中) 實際的記憶體存取順序其實和程式的呼叫順序是不一致的。會有這現象又是因為 CPU 對效能在硬體上的優化技術。由於 CPU 的執行速度遠高於對記憶體的存取速度，所以 CPU 為了能將延遲降到最低、將效能拉到最高，會盡量的使用快取 (Cache) 或是寫緩衝 (Write Buffer)，這樣的結果就是執行順序並不一定會照著程式的執行順序。舉一個簡單的例子就是，在做寫入時，資料被寫入 Write Buffer 後 CPU 就會接著執行下一個指令，導致資料實際上從 Write Buffer 被寫入記憶體的時間會晚於他的下一個指令。
再舉一個跟讀有關的例子之前，需要先提到另一個技術較做 Speculative Access，這技術會讓 CPU 試著去預判接下來要執行的指令，然後提前先去執行，如果預判對了，就可以直接使用提前執行的結果；如果錯了，則丟棄該結果，重新執行正確的指令。這技術常被應用在分支之上，CPU 會試著先去預判要走到哪一個分支，如果預判正確了便能提升效率。回到原本的 Memory Access 順序的範例，當 CPU 也可能因為預判到後方的讀指令而預先執行，導致其實際執行順序其實早於在程式上比他還早的指令。
上述的兩個例子並沒有包含所有指令順序被調換的原因，事實上原因複雜到對軟體設計師來說，只需要把他們當成隨機調換的就好。
另外值得一提的是，上面提到的順序調換機制是在 CPU 硬體層面上實現的，也就是 CPU 拿到指定順序的指令，他並不一定會照著順序走。這和編譯器層面的順序調換是不一樣的，編譯器在將人寫的高階程式語言 (C 或者組合語言) 編譯成機器語言時，也會因為類似的效能優化原因，將執行順序做調換。而本文討論的順序問題都是針對前者，和編譯器的無關。
<h1>2. Memory Type</h1>
Memory Type 有分以下三種：
1. Normal
2. Strong-ordered
3. Device
|Memory Type | Shareable| Cacheable | Description |
|-----------------|----------|-----------|-------------|
| Normal | Yes | Yes | 能在不同核心之間共享的記憶體區段，其執行順序是不被保證的。 |
| Normal | No | Yes | 只給特定單一核心使用的記憶體區段，其執行順序是不被保證的。 |
| Device | - | No | 針對 Memory-mapping 周邊 (Peripheral) 設計的記憶體類型，其實際執行順序是保證和程式呼叫順序一致 |
| Strongly-ordered | - | No | 實際執行順序是保證和程式呼叫順序一致。所有的 Strongly-ordered 記憶體區段在核間都是共享的 |
(所謂的 memory-mapping peripheral 是指可以被映射到記憶體空間的設備，CPU 可以透過一般的記憶存取指令來操作該設備。相對於 memory-mapping peripheral 的是 private port peripheral，也就是需要透過 IN / OUT 指令來操作的周邊設備。)
Normal Memory 沒有辦法保證實際的存取順序，但是 Device 和 Strong-ordered 可以。也就是說，如果有兩個區段的存取，只要他們至少其中之一是 Noraml memory type，他們的存取順序就是無法保證的；相反的，只要他們都不是 Normal memory type，那他們就會依照執行順序去存取記憶體。
<h2>2.1 Strongly-Ordered 和 Device Memory</h2>
這兩個類型的記憶體空間除了執行順序保證和程式呼叫順序一樣外，還有以下幾個共同點：
1. CPU 會忠實地執行程式呼叫的記憶體存取，不會去做任何優化。也就是說，就算程式試著對某個記憶體位置連續做兩次讀取或寫入，CPU 就會真的做兩次，不會把它簡化成一次。如果程式想要讀 8 bit 的空間，CPU 就只會對這 8 bit 做讀取，不會一次讀 32 bit，然後再返回其中 8 bit 的值。
2. 所有的存取都是原子性的 (Atomic)，無法途中被中斷。
3. 不論讀寫都有可能對系統產生副作用 (Side-effect)。這邊的副作用應該是指說因為 Strongly-Ordered 和 Device 記憶體空間常常是外部設備的記憶體映射位置，對該空間做讀寫，有可能會對系統產生影響。舉例來說，對 DMA 的某個 Bit 做寫的動作，可能會觸發 DMA 去改寫記憶體空間。
4. 指令無法被 Cache，且也不支援 Speculative Access。所以這兩個類型才很適合用來作為外設映射記憶體空間類型，因為這樣的記憶體空間不是單純的儲存空間，就算針對某個一位置重複讀寫都有可能會有不同的意義，如果將結果都 Cache 起來，就會得到錯誤的結果。
5. 存取的位置一定要對齊 (Aligned)。假設系統是 32 bit (4 byte) 對齊的，那就沒辦法對 0x00000001 讀取，因為 0x00000001 沒有對齊 4 byte。
6. Device memory 的順序維持僅限於同一個外部設備的記憶體空間中，其大小至少為 1 KB。
7. Normal 記憶體空間的存取還是可以和 Stongly-ordered 或 Memory 記憶體空間存取調換順序。這也是前面 2. Memory Type 提到的 - 如果有兩個區段的存取，只要他們至少其中之一是 Noraml memory type，他們的存取順序就是無法保證的。
而他們的相異點只有一個：
Device memory 是可以寫緩衝的 (Bufferable)。也就是說，Device Memory 允許其 Memory Entry 的 B Bit (BIT[2]) 為 1。在這樣的情況下，寫指令只要寫到緩衝區就算完成，CPU 可以繼續執行下一個記憶體存取動作。這會導至執行順序可能不再是依照程式順序的 (下一個讀指令有可能比前一個寫指令真的寫進記憶體中還要早，但僅限於此，相對於 Normal Memory 的重新排序程度會小很多)，但這樣能提供更高的效率。而 Strongly-Ordered Memory 是完全不允許 Buffer 或是 Cache 存在的，任何讀寫都是直接對記憶體生效，且順序必定是照著程式的順序走。相關的表格可以參考 [Arm Programmer's Guide IX - The Memory Management Unit 學習筆記](https://hackmd.io/2nnVV8vISrO6ywClfJFHjQ?view) 4.3.2 章節中的第二個表格。
如果 Memory Device 的 Buffer 功能是被關閉的，他基本上行為和 Strongly-Ordered 是一樣的。
<h2>2.2 Normal Memory</h2>
Normal Memory 有以下幾個特性：
1. 讀寫指令可以重複執行也不用擔心對系統產生副作用。
2. 能夠執行 Speculative Access 和合併多個指令來提升效率。
3. 存取的位置可以不需要對齊 (Align)。
4. 能夠使用 Cache。Cache 有分 Inner 和 Outer Cache，Inner Cache 為 L1 或 L2 的 Cache，會較先被查詢；Outer Cache 則為 L2 或 L3，較晚被查詢。
5. 能夠設定是否和其他核共享 (Shareable)，這邊指的共享是指硬體能夠自動地去處理不同核間的一致性問題(例如他們的 Cache 會同步)。就算沒有設定共享，其他核其實也可以摸到該記憶體空間，只是開發者會需要自行維護不同核操作間的一致性。
6. 共享又分內部共享 (Inner Shareable) 和外部共享 (Outer Shareable)：內部共享區域 (Inner Shareable Domain) 是指多個處理器之間共享的區域，其他的核心無法接觸該區域。舉例來說，一個 Cortex-A15 處理器可以和另一個 Cortex-A7 處理器組成內部共享區域；外部共享區域 (Outer Shareable Domain) 則是處理器與外部設備的共享區域。舉例來說，一個 Cortex-A7 處理器可以和 GPU 組成外部共享區域。
<h1>3. 記憶體屏障 (Memory Barriers)</h1>
大部分時候我們都可以信任硬體去重排執行順序來達到效能的提升，但有的時候我們會想在關鍵的地方能夠精準地控制執行順序，這時候記憶體屏障就能派上用場。我們先看以下的例子：
Core A:
```c=
STR R0, [Msg] @ write some new data into postbox
STR R1, [Flag] @ new data is ready to read
```
Core B:
```c=
Poll_loop:
LDR R1, [Flag]
CMP R1, #0 @ is the flag set yet?
BEQ Poll_loop
LDR R0, [Msg] @ read new data
```
由於執行順序的不可保證性，上方的程式極有可能不會照個預期的執行。Core A 有可能在把資料 (R0) 填到 Msg 前就先把 Flag 改舉起來；Core B 也有可能在確認到 Flag 被舉起來之前，就先把 Msg 中的值給讀了出來。
在這個例子中，我們會希望 Core A 執行第二行前能先執行第一行、Core B 在執行第三行前能夠先執行第二行，我們可以透過加上記憶體屏障指令 DMB 和 DSB 來達到此目的：
Core A:
```c=
STR R0, [Msg] @ write some new data into postbox
DMB
STR R1, [Flag] @ new data is ready to read
```
Core B:
```c=
Poll_loop:
LDR R1, [Flag]
DSB
CMP R1, #0 @ is the flag set yet?
BEQ Poll_loop
LDR R0, [Msg] @ read new data
```
DMB 能夠確保他之前的指令在他之後的指令前完成、而 DSB 能確保他之前的指令都完成後才繼續往下走。
以下為更詳細的記憶體屏障指令說明：
<h2>3.1 指令說明</h2>
1. DSB (Data Synchronization Barrier)
顧名思義，在 DSB 之前的所有資料存取 (Explicit Data Access) 都需要先全部完成 (讀取完成、寫入進「記憶體」生效)，才可以繼續往下走。但指令的 Pre-fetch 不在此限制。
2. DMB (Data Memory Barrier)
和 DSB 有點像但是較為寬鬆。他將指令分成兩個區域：「 DMB 之前」和「 DMB 之後」，他會確保 「 DMB 之前的指令」一定會在「 DMB 之後的指令」前完成。但他並不像 DSB 一樣會阻擋指令執行下去，當執行到 DMB 時，就算 「DMB 之前的指令」還沒完成，還是會繼續往下執行，只要確保之後的流程中 DMB 前後指令的順序就好。
同樣地，這只限於資料的存取 (Explicit Data Access)、不限於指令的 Pre-fetch。
3. ISB (Instruction Synchronization Barrier)
前兩者都是針對資料的存取， ISB 則是針對指令的 Pre-fetch。在 ISB 會強制清空( Flush ) Pipeline 和 Prefetch Buffer，使其之後的指令都一定是從 Cache 或記憶體中取得。對於完整的資料 和指令屏障，可以用 ISB 搭配 DMB 。
DMB 和 DSB 還可以和以下的幾個指令做搭配：
1. SY：預設值。表示這個屏障會套用給整個系統，包含所有核心還有周邊設備。
3. ST：只針對寫指令( Store )做屏障。
4. ISH：只套用給內部共享區域 (Inner Shareable Domain)。
5. ISHST：ISH + ST。
6. NSH：A Barrier to the Point of Unification (PoU)。(這邊還看不懂，需要先看完原文第八章 Cache。)
7. NSHST：NSH + ST。
8. OSH：只套用給外部共享區域 (Outer Shareable Domain)。
9. OSHST：OSH + ST。
若想要在編譯器層級指定執行順序，Linux 可以呼叫 barrier() 來達到：
```c=
write_to_hw_reg();
barrier();
read_from_hw_reg();
```
上方的代碼防止編譯器將讀取動作重新排列至寫指令之前，但執行時硬體仍然可以因為 speculative access 等原因提早執行讀取指令。
<h2>3.2 使用場景</h2>
<h3>3.2.1 避免 Deadlock </h3>
```=
STR R0, [Addr] @ write a command to a peripheral register
Poll_loop:
LDR R1, [Flag]
CMP R1, #0 @ wait for an acknowledge/state flag to be set
BEQ Poll_loop
```
上述例子在沒有 Multiprocessing extensions 的情況下是很有可能造成 Deadlock 的。原因為第一行的寫指令有可能停留在 Write Buffer，但 CPU 一直忙於 Polling 迴圈中。
解法可以是在第一二行間插入一個 DSB。
(如果有啟用 Multiprocessing extensions，那 Write buffer 會需要在指定的時間內去真的寫進記憶體中，那麼沒有 DSB 也不會造成 deadlock。)
<h3>3.2.2 SEV 之前</h3>
WFE (Wait For Event) 和 WFI (Wait For Interrupt) 能夠使核心進入一種低功號的狀態。這在等待其他核心資源的時候很常使用。當持有該資源的核心要釋放該資源時，可以使用 SEV (Send Event) 指令去喚醒其他在 WFE 等待狀態中的核心。這時候如果 SEV 前沒有加上記憶體屏障，就有可能造成資源實際上還沒被釋放就觸發 SEV 指令，進而造成問題。
另外由於 SEV 不是資料存取指令，所以其之前的記憶體屏障一定要用 DSB 而不能用 DMB，因為 DMB 只在乎其前後資料存取間的順序，不在乎和其他指令間的順序關係，只有 DSB 能夠強迫其之前的所以資料存取都完成，才能接續執行接下來的任何指令。
<h2>3.3 Linux 的記憶體屏障 API</h2>
1. rmb(): rmb 為 Read Memory Barrier 的縮寫。此 API 能強迫他之前的所有讀指令比他之後的讀指令還早完成。
2. wmb(): wmb 為 Write Memory Barrier 的縮寫。此 API 能強迫他之前的所有寫指令比他之後的寫指令還早完成。
3. mb(): mb 為 Memory Barrier 的縮寫。此 API 能強迫他之前的所有讀寫指令比他之後的讀寫指令還早完成。
以上三個 API 都有其各自的 SMP 版本 (smp_rmb()、smp_wmb() 和 smp_mb())，他們用來在相同叢 (cluster) 內的核心之間設定記憶體屏障。
---
上一篇: [Arm Programmer's Guide IX - The Memory Management Unit 學習筆記](https://hackmd.io/@uMqav-XESBCsrtZEx_Jpug/Arm_Programmer_Guide_Memory_Management_Unit_Studying_Note)
下一篇: [Arm Programmer's Guide XI - Exception Handling 學習筆記](https://hackmd.io/@uMqav-XESBCsrtZEx_Jpug/Arm_Programmer_Guide_Exception_Handling_Study_Note)
Sign in with Wallet
Connect another wallet