執行人: I-Ying-Tsai
解說影片
eleanorLYJ
關於 "Software managed coherency" 的實作嘗試,你寫到「寫了一個 Kernel Module 搭配 dma 來試著使用它」,但程式碼片段是空白的。請問這次嘗試的具體目的是為了比較軟體管理與硬體管理一致性的效能差異,還是在實驗初期探索不同的記憶體一致性策略?
因為在閱讀 Arm 手冊的過程中我發現了軟體管理已經被遺棄的敘述,於是才想說實做出來比較與硬體管理一致性的效能差異,這與後續的實驗其實沒有關聯,而程式碼片段是空白的原因是因為我還沒將它寫好,日後寫好後才會將它補上。
I-Ying-Tsai
HeLunWu0317
現代處理器廣泛使用弱記憶體模型以提升效能,卻可能在多核間引發難以察覺的 race condiction。
race condiction 拼寫錯誤。
現代處理器廣泛使用弱記憶體模型以提升效能,卻可能在多核間引發難以察覺的 race condiction。為此,Linux Kernel Memory Model (LKMM) 提供一套模型與工具(herd7/litmus7)協助驗證記憶體順序是否違反預期。透過對 litmus 測試的分析,我得以觀察 ARMv8-A 真實硬體是否會違反這些模型,並驗證 barrier 的有效性。
細讀並行程式設計: Atomics 操作、紀錄認知和提問,務必涵蓋「Memory Ordering 和 Barrier」
利用 litmus7 在 Raspberry Pi 4B 硬體實驗並充分解讀
適度改進筆記內容
搭配閱讀 2024 年報告-1 及 2024 年報告-2
做實驗之前我需要先了解我做實驗的硬體架構:
畫出架構如下:
首先安裝工具:
我根據 Paul McKenney 在 演講中所使用的簡報 使用以下指令先安裝了 herd7tools :
接著我先使用了 litmus7 工具分析了 SB.litmus :
SB.litmus :
對它執行 litmus7 ./SB.litmus -carch AArch64
指令後結果如下:
避免過多的縮排,參閱課程教材風格予以調整。
在實驗之前,我透過閱讀老師的 Atomics 操作的教材以及借助詢問 GPT 給我的一些破碎的資訊,先得到了一些概念並試著翻閱手冊,思考問題後再進行實驗:
Cache coherence : 翻閱 Arm 關於 Cache coherence 的手冊(DDI0487I.a B2.9.1 Coherent Memory)後,發現手段有三種:
Disable caching:這個很直觀,它會把要共享的記憶體區域標記成 non-cacheable。但這會讓DRAM 延遲大幅提高、功耗高、效能降低。也就是會讓 Cache 的優勢消失。在這裡不會被實做。
Software managed coherency:
對於這個方法,Arm 官方是這麼描述的:
Software managed coherency is the traditional solution to the data sharing problem. Here the software, usually device drivers, must clean or flush dirty data from caches, and invalidate old data to enable sharing with other processors or masters in the system. This takes processor cycles, bus bandwidth, and power.
於是我寫了一個 Kernel Module 搭配 dma 來試著使用它:
Hardware managed coherency:
這個是目前大部分的處理器採用的方式,而 ARM Cortex-A72 採用的是基於 MOESI protocol 的 Cache 行為,具體行為如下:
並基於這個協定讓每個 CPU 使用 Snoop Control Unit (SCU) 監控各個 CPU 的 Cacheline 狀態。(當某 CPU 要讀一條 Cacheline 時,SCU 會 snoop 其他 CPU,看是否有更新版本),接著各 CPU 之間透過 ARM 定義的 AMBA ACE bus (AMBA Coherent Extensions) 傳輸 snoop transaction:
Store Buffering
ARM TRM 裡提到:
The Load-Store Unit contains multiple queues, including a store buffer. This enables stores to retire from the pipeline before they are globally visible, improving throughput.
Q:那 Cortex-A72 pipeline 是如何設計的呢?
A:被分成這幾個步驟:
Instruction Fetch:從 L1 I-Cache 抓取指令,每 cycle 可供應最多 3 條指令。
Instruction Decode:參考原文
The decode unit translates fetched instructions into internal operations that can be dispatched out of order to execution pipelines. It includes branch decode, register rename, and allocation logic.
Dispatch / Rename:它會實際地執行 rename ,具體行為如下
讀取 free list 中可用的 physical registers
free list : 它會記錄「目前哪些 Physical Registers 是空閒的,可以被新的指令使用」。
這裡可能是用 bit vector + priority encoder 來實做,因為我沒有在手冊裡翻到對 free list 的實做細節描述,但在閱讀其他開源專案時發現幾乎都是使用了這個實做方式或其變形。
Ex:Berkeley Out-of-Order Machine
Q:為何 AR 和 PR 需要分開設計?初步會直覺地認為使用 PR 就足以對應 AR,實際上需分離設計以支援 speculative execution 與指令重排序。
A:為了讓 Pipeline 可以支援 Reordering 與 speculative execution。首先因為 PR 的數量比 AR 還多,如果 CPU 內部只有 Architectural Register, Pipeline 中同一
一個 AR 只能有一份值。但若有兩條指令要對同一個 AR 寫入(WAW):
或是 WAR:
在第一個範例中,第二條指令必須等到第一條指令將值寫回 AR,才能開始執行,否則會發生 harzard。
在第二個範例中,I2 可能因為 reordering 而導致先執行,直接把 R2 改成 7。
將每個 architectural register 對應到一個新的 physical register
更新 rename table
配給 Reorder Buffer (ROB) Entry,建立依賴鏈
將 rename 後的 µops 放進 Issue Queue。
Integer Execute:有兩條 ALU pipeline,支援乘累加、除法單元與 branch resolve
Load/Store Unit:
裡面包含了:
Address Generation Logic (AGU):計算 Load/Store 的有效位址
TLB:處理虛擬位址轉換
LSU 包含一個獨立的 Data TLB (DTLB)。
由 32–64 個 entry 構成,在 Cortex-A72 TRM 手冊裡是這麼描述的:
The core implements a main data TLB with 32 entries, and a micro TLB with 10 entries.
以及
These TLBs are fully associative for fast matching.
每個 entry 存放:
當 AGU 計算出虛擬地址後,DTLB 快速比對,若 hit,直接給 LSU 繼續執行。若 miss,啟動 MMU Page Table Walker (PTW),這是 ARM 架構硬體提供的 page table,走訪 TTBR。
Load Queue (Load Buffer):
Load Queue 是一組 FIFO 或 Circular Buffer。每條 Load 進 LSU 後,如果 miss L1 D-cache,會登記在 Load Queue。
Load Queue 記錄了:
允許同時有多條 Outstanding Load,典型可支持 8–16 條。
與 Store Buffer 和 Fill Buffer 協同:
Store Buffer:暫存 retire 後尚未真正寫入 cache 的 Store
Fill Buffer:處理 cache miss 時,從 L2 / DRAM 拉回 cache line
Coherence Controller:處理 ACE snoop,保證多核心 cache line 一致性
Alignment / Merge Logic:處理 unaligned 訪問、write combine
Writeback:
Retirement:
至少該涵蓋以下演講: (包含錄影)
接著,我下載了 Linux kernel 的 tools/memory-model
子目錄,接著進入 tools/memory-model/litmus-tests
資料夾,以 herd 驗證搭配 litmus7 來進行實機實驗,並適度修改程式碼進行分析:
directory 是「目錄」,而非「資料夾」,務必使用課程規範的術語書寫。
MP+poonceonces.litmus
:WRITE_ONCE
和 READ_ONCE
,保證了讀和寫是一個 atomic 操作,compiler 不會將它重排。根據這段程式碼,理論上它只會有 3 種情況:
然而當我用 herd 進行分析後的執行結果卻是:
第四種可能出現了!根據這個執行結果我們幾乎可以 100% 確定 CPU
有可能重排了這段程式碼,於是我是著去試著查看 Arm 手冊 來試著了解 ARMv8-A 架構下 memory model 對 weak ordering 的容忍程度後發現:
load-load
, load-store
, store-store
, store-load
都可能被 CPU pipeline 重排。
那什麼情況下可能會被重排呢?查看手冊 D7-1 後發現它寫著 :
The architecture does not prescribe a particular form for the memory systems.
這說明了 ARM 不強制特定 microarchitecture(例如是否允許亂序、緩存設計等),而是提供一組行為定義,允許實作有所不同。
以及第 B2.3 節寫著:
A DMB ST will prevent two store instructions from being reordered.
A DMB LD will prevent two load instructions from being reordered.
也就是說:
接著我試著使用了 litmus7
分析在 AArch64 架構下的實驗結果:
首先我用以下命令試著利用 herd 工具包裡的 litmus.exe
將 MP+poonceonces.litmus
轉成 .c
但出現了:
我檢查了 util.c/h 發現是空的,於是我手動將這兩個巨集加進了 MP+poonceonces.c
:
結果編譯成功:
參數是:
結果是:
可以發現在實機測試中未觀察到預測的壞結果。
根據這個已經可以發現:
但!那依然有可能發生,於是我做了第二次測試。
我調整了參數為:
結果為:
這時發現,(r0=1; r1=0)出現了!
這驗證了:
接著查看 tools/memory-model/Documentation/explanation.txt 後,裡面是這樣描述的:
smp_store_release() forces the CPU to execute all po-earlier instructions before the store associated with the fence
以及
Any store which propagates to C before a release fence is executed… is forced to propagate to C' before the store associated with the release fence does.
這說明了:
A-cumulative fence 在 LKMM 中的定義如下:
The propagation ordering enforced by release fences and strong fences affects stores from other CPUs that propagate to CPU C before the fence is executed, as well as stores that are executed on C before the fence.
We describe this property by saying that release fences and strong fences are A-cumulative.
也就是說:
從硬體層面來看:
DMB ISHST 是一種 memory barrier 指令,僅影響 store→store 順序。
語義:Store-Store Barrier,只針對 store → store 順序保證。
它保證:
於是接著我參考 LKMM 的規範,使用了 release-store semantics 嘗試阻擋這個情況。
也就是接下來進行的測試的分析。
這個 litmus 測試使用以下同步操作:
P0
:WRITE_ONCE(buf)
➜ smp_wmb()
➜ WRITE_ONCE(flag)
P1
:READ_ONCE(flag)
➜ smp_rmb()
➜ READ_ONCE(buf)
這相當於在 store 和 load 間各自插入 memory barrier:
首先使用 herd7 工具進行分析,結果如下:
可以發現,只出現了三種狀態。
這也驗證了之前的探討。
接著進行實機測試:
使用以下指令轉換成 C code 後:
一樣先在編譯前先在 MP+pooncerelease+poacquireonce.c 裡補上巨集定義:
接著 make
後編譯成功:
更改參數如下:
執行結果:
結果顯示在 LKMM 規範下,使用 smp_wmb() 與 smp_rmb() 可以有效地防止 message-passing 模式中的重排序問題。
改進 MP+poonceonces.litmus 如下(加入 full barrier)
首先使用 herd7 工具分析如下:
可以發現,加入 smp_mb() 後,成功阻止了 message-passing 重排序現象。
接著進行實機測試:
使用以下指令轉換成 C code 後:
一樣先在編譯前先在 MP+pooncerelease+poacquireonce.c 裡補上巨集定義:
接著 make
後編譯成功:
更改參數如下:
執行結果:
查看行為後發現 flag 預設是 0 的狀態,然後讓需要被阻止重排的操作前面讀取 flag 直到它被設成 1,然後負責 store 的那個 Thread 需要負責寫 flag=1。
P0:
WRITE_ONCE(*buf, 1)
:寫入實際資料(payload)。smp_store_release(flag, 1)
:
P1:
smp_load_acquire(flag)
:
flag==1
,則保證之後的所有 load(如 buf)不會被 reorder 到這個 acquire 之前。READ_ONCE(*buf)
:嘗試讀取 payload。Q:這個模式是否只適合只有一個 Producer 和一個 Consumer 的情況?
A:是的,這個模式是 point-to-point 同步。因為:
flag 是一個 單一整數變數(int flag),不具備識別來源或目的的能力:
Q : 那這樣我應該如何利用它來支援 支援 N producers/N consumers 呢?
A:下一個實驗進行探討。
Q:會不會因為工作阻塞而導致 flag 無法釋放,大量浪費 CPU 資源?
A:後續會試著進行探討。
首先使用 herd7 工具進行分析,結果如下:
可以發現,只出現了三種狀態。
這也驗證了之前的探討。
接著進行實機測試:
使用以下指令轉換成 C code 後:
一樣先在編譯前先在 MP+pooncerelease+poacquireonce.c 裡補上巨集定義:
接著 make
後編譯成功:
更改參數如下:
執行結果:
可以發現未出現任何一次 flag = 1 且 buf = 0 的執行結果(我進行了多次實驗),這也驗證了前面所述:
先用 herd7 分析:
發現:
這表示:
接著進行實機測試:
使用以下指令轉換成 C code 後:
接著 make
後編譯成功:
更改參數如下:
執行結果:
可以發現,1:r0=1 /\ 2:r0=1 /\ 2:r1=0 確實發生了 5 次(out of 100 million)
因為在前面的實驗我們已經驗證了 release-acquire memory ordering 可以阻止 L-L, S-S, S-L, L-S 的 reordering ,並且這是對於所有 CPU 的保證。
於是我們期望的目標是:
用 herd7 分析:
發現 release-acquire chain 成功阻止了 memory reordering
接著進行實機測試:
使用以下指令轉換成 C code 後:
補上巨集定義:
但出現了錯誤:
在確保更改不會影響實驗的本質後,我進行了以下修改:
原本:
修改後:
Q :那為什麼一開始設計的時候會是這樣呢?
A :因為 litmus 語法是從更接近 assembly 或 formal model 的角度出發撰寫的,而不是直接當成 C 的巨集使用。它的語法是:「寫入 *x 所指的位置」。
接著 make
後編譯成功:
更改參數如下:
執行結果:
發現沒有出現 1:r0=1 ∧ 2:r0=1 ∧ 2:r1=0
-> release → acquire → release → acquire chain 正確地阻止了 reordering。