並行程式設計: Atomics 操作

--- tags: concurrency --- # [並行程式設計](https://hackmd.io/@sysprog/concurrency): Atomics 操作 > 資料整理: [jserv](https://wiki.csie.ncku.edu.tw/User/jserv), [qwe661234](https://github.com/qwe661234) ## 點題在[並行程式設計](https://hackmd.io/@sysprog/concurrency)中，常用 lock 避免多個執行緒在修改同一個資料時，遭遇 [race condition](http://en.wikipedia.org/wiki/Race_condition) 的狀況。 ![](https://hackmd.io/_uploads/S1C-S3m-2.png) 考慮上圖，主記憶體某處原本內含值是 `17`，我們挪用作計數器 (counter) 這樣的共用變數。考慮有 2 個執行緒 Thread~A~ 和 Thread~B~，倘若二者都對計數器遞增 `1`，預期計數器會得到 `19`，即 $17 + 1 + 1$，但最終可能出現非預期的 `18`，為什麼？其中一個可能是，Thread~A~ 自主記憶體讀取計數器內含值 (此時是 `17`) 後，觸發 context switch，切換到 Thread~B~ 執行，後者也從記憶體讀取計數器內含值 (即 `17`)，隨後遞增 `1`，並且寫回主記憶體中。爾後，切換到 Thread~A~，依據程式碼的邏輯，要將計數器的數值遞增 `1`，之前已取得 `17` (舊數值)，但 Thread~B~ 沒有察覺主記憶體裡頭的計數器內含值已變更，依然對 `17` 遞增 `1`，並寫回主記憶體，即 `18`。我們可發現，「寫回主記憶體」的操作分別在 Thread~A~ 和 Thread~B~，但最終沒得到我們預期的 `19`。為了便於探討上方案例，我們將 `count` 的初始值設為 `0`: ![image](https://hackmd.io/_uploads/B1fnsaReC.png) 如今有二個執行緒讀取 `count` 變數的內容，再把 `count` 加 1，於是每個 `count = count + 1` 敘述可視為以下二個獨立的步驟: * `temp = count + 1` (讀取 `count` 的值並且加 `1`) * `count = temp` (把計算好的值重新存回 `count`) 對照上方示意圖，在沒有任何限制的情況下，多個執行緒之間可能會交互執行指令，現在按照紅色箭頭的軌跡來分析： * Thread~0~ 先取出 `count` 並且加 `1`，存到 `temp0`，於是 `temp0 = 1` * 接著輪到 Thread~1~ 取出 `count` 並且加 `1`，存到 `temp1`，亦即 `temp1 = 1`，Thread~0~ 計算完 `temp0` 後尚未指派的動作就被切換，所以 Thread~1~ 取到的 `count` 依舊是 `0` * 再回到 Thread~0~，把計算好的 `temp0` 指派到 `count`，於是 `count = temp0 = 1`，此時 `count` 被更新為 `1` * 最後輪到 Thread~1~，把計算好的 `temp1` 指派給 count，亦即 `count = temp1 = 1`，最後結果 `count = 1`，不符合我們的預期我們把上述因執行緒競相變更資料，卻無法達到預期的結果，稱為 [race condition](http://en.wikipedia.org/wiki/Race_condition)，可簡稱 `race`。在多執行緒環境下，若缺乏適度的同步機制，會造成很多無法預期的結果，換言之，我們的目的就是不要讓執行緒之間隨意交互執行，所以我們應該要關注[執行順序](https://hackmd.io/@sysprog/concurrency-ordering)。一味依賴 lock 易致使 [lock contention](https://en.wikipedia.org/wiki/Lock_(computer_science)#Granularity)，甚至當 lock 成為[多核處理器](https://en.wikipedia.org/wiki/Multi-core_processor)的效能瓶頸時，我們不得不接觸到微處理器提供 atomic 專用指令，但要用 atomic 指令寫出正確的並行程式卻是困難的事，不僅要廣泛顧及 [ABA 問題](https://en.wikipedia.org/wiki/ABA_problem), [memory barrier](https://en.wikipedia.org/wiki/Memory_barrier) 及多核處理器特性，還要思索現有演算法的改寫和驗證。本文回顧微處理器的 atomic 指令及軟硬體設計考量、[memory ordering](https://en.wikipedia.org/wiki/Memory_ordering) 及 [memory barrier](https://en.wikipedia.org/wiki/Memory_barrier)、C11 標準的 [stdatomic.h](https://en.cppreference.com/w/cpp/header/stdatomic.h) 及 Linux 核心介面，和探討經典 [lock-free](https://en.wikipedia.org/wiki/Non-blocking_algorithm) 資料結構和演算法案例。 ## 詞源和澄清 ![](https://hackmd.io/_uploads/BkqzrhQbh.png) 原子的英文 "atom" 源於希臘文 [ἄτομος](https://en.wiktionary.org/wiki/%E1%BC%84%CF%84%CE%BF%CE%BC%CE%BF%CF%82) (拉丁轉寫為 atomos)，意思是「不可分割的單位」。最先提出原子學說的是古希臘米利都學派 (也稱為愛奧尼亞學派，被譽為是西方哲學的開創者) 中的留基伯 ([Leucippus](https://en.wikipedia.org/wiki/Leucippus))，他的學生德謨克利斯 ([Democritus](https://en.wikipedia.org/wiki/Democritus)) 繼承並發展原子學說，並用原子學說來解釋宇宙：宇宙由原子和虛空組成，所有物質都由不可再分割的微小粒子組成。因這個微小粒子已不能再分割，他將希臘文 [τόμος](https://en.wiktionary.org/wiki/%CF%84%CF%8C%CE%BC%CE%BF%CF%82) (拉丁轉寫為 tomos，意思是分割) 加上了反義字首 a-，成為 "atomos"，即「不可分割的」。`-os` 是希臘文名詞的後綴，十五世紀晚期 atomos 這詞去除後綴轉寫為現代英語，成為 [atom](https://www.dictionary.com/browse/atom)。電腦科學進一步借用 [atomic](https://www.dictionary.com/browse/atomic) 一詞來表示「不可再拆分的」，於是 "atomic operation" 寓意為「不可再拆分的執行步驟」，也就是「最小操作」，即某個動作執行時，中間沒有辦法分割。既然提到 atomic，我們來看貌似不相關，但會影響到文意思考的詞彙 —— 原子筆，後者的英語書寫為 "[ballpoint](https://en.wikipedia.org/wiki/Ballpoint_pen)"。香港利豐有限公司當年把 ballpoint 從美國輸入香港時，產品並無中文名稱，「原子」一詞在當時有高新科技的意象，代理商將 ballpoint 取名為「原子筆」則表示該發明乃創新、突破性的尖端書寫技術。倘若我們將 atomic operation 翻譯為「原子操作」，可能會讓人聯想到高科技或者核能 (nuclear)，但事實根本不是這個意思！本文將 atomic operation 簡稱 atomics 或保留原文，避免用「原子操作」這樣無法望文生義的譯詞。 > 延伸閱讀: [香港利豐集團百年傳奇](https://www.businessweekly.com.tw/Archive/MagindexContent?issueNumber=1063) > atomic 的國際音標 (IPA) 是 [əˈtɑmɪk] > atom 的國際音標是 [ˈætəm] ## 阻塞式同步機制為確保多個執行緒或行程之間得以符合預期地執行 (即成語「[並行不悖](https://dict.revised.moe.edu.tw/dictView.jsp?ID=19763)」)，其中一種手段是讓某個執行緒執行，同個時間阻塞 (blocking) 其他執行緒，直到前者完成某一段會影響到共享資源存取的程式碼，後者方可繼續執行。這個策略稱為阻塞式同步 (blocking synchronization)，語意簡潔且易於開發，但缺點是: 1. 就算硬體有能力處理多個執行緒，但只要涉及共享資源的存取，不免要藉由阻塞達到同步：被阻塞的執行緒，要不原地等待 (spin)，要不等待喚醒 (sleep/wake) 的訊號，無法充分運用硬體能力 2. 非預期的狀況可能致使毫無進展 (progress)：某個持有阻塞式同步鎖 (lock) 的執行緒，若恰好因為非預期的原因致使崩潰，這樣 lock 就不會釋放 (除非系統管理者介入)，從而使得等待該 lock 的執行緒無法再執行下去，自然就不會有進展，這樣的程式會讓終端使用者認為「程式卡住了」，儘管微處理器其實仍在執行特定的程式 3. mutex lock 在特定的場景代價很大，例如可能會遇到 [priority inversion](https://en.wikipedia.org/wiki/Priority_inversion) 的議題，儘管存在 PIP (Priority inheritance) 和 PCP (Priority ceiling protocol) 一類的解法，但執行時期的複雜度提升，甚至還要考慮 [Runtime locking correctness validator](https://www.kernel.org/doc/html/latest/locking/lockdep-design.html) 的機制特別你想充分發揮多處理器的硬體能力，或不容許整個系統因為單一執行緒拖延整體進度，抑或是 [scalability](https://hackmd.io/@sysprog/linux-scalability) 是你迫切面對的議題，那就要考慮到阻塞式同步機制以外的方案。 ## Atomic 操作：非阻塞式同步的基石 "atom" 作為電腦術語，指無法再拆分為更小的執行步驟，這實際是對「硬體」的觀點，即微處理器的指令，並非從「軟體」的觀點來看。atomic 指令形式不一，我們可用較高階的語法來解釋: (即 C11) ```c _Atomic int cnt; atomic_fetch_add_explicit(&cnt, 1, memory_order_relaxed); ``` 從函式 `atomic_fetch_add_explicit` 的開頭不難猜出這是 atomic 操作，至於 `explicit` 涉及 memory order，稍後解釋。這裡的 `fetch` (自記憶體取值), `add` (執行加法，這裡就是 `+ 1` 操作) 以及最終的寫回主記憶體等 3 個步驟必須是 atomic，意思是要不什麼都沒做，要不 `fetch`, `add` 和寫回主記憶體三者都完成，不會有中間狀態 —— 儘管概念上拆解為 3 個步驟，但視作 3 個步驟都是不可分割的最小單元。類似 `atomic_fetch_add_explicit` 的 atomic 操作，我們歸類為 read-modify-write 操作，簡稱 RMW。不難聯想到，本文點題時提到計數器的案例，就該用 atomic RMW 操作來解決，但背後的演算法卻略為複雜 —— 既然 atomic 是將單一或若干步驟視作最小操作單元，實際上就會遇到「要不全部成功，要不全部失敗」的現象，於是我們需要變更原本執行緒的程式邏輯，當 atomic 操作不能成功時，就重來 (成語「[一氣呵成](https://dict.revised.moe.edu.tw/dictView.jsp?ID=149457)」)，直到 RMW 一類的 atomic 操作成功為止。在 single-core 下只要關閉 global interrupt，防止 CPU 被 preempt，就可確保 atomic，但在 multi-core 就要有特殊的硬體支援（且關閉 global interrupt 會影響回應時間，從而增加 latency）。其中很大一部分要確保 RMW operation 是 atomic，特別是在 lock 與 counter 的實作上面。通常 CPU 會提供有別於一般 load/store memory 的特殊指令，以達成 RMW atomic。常見以下二種: * [compare-and-swap](https://en.wikipedia.org/wiki/Compare-and-swap) (CAS) / swap (SWP): CAS 寫入時同時提供舊值 (之前自 `target` 讀出來的值，對應下方程式碼的 `compare`)，如果舊值和記憶體裡的相同，就將新值 (即下方程式碼的 `new`) 寫入，確保 RMW 的動作完整性，如 x86 的 `CMPXCHG` 指令。SWP 在寫入時讀回記憶體的值，可用於與之前讀出的值比對。如 ARMv5 (含) 之前的 SWP，ARMv8.1 也引入 CAS 指令 ```c lock cmpxchg(target, compare, new): lock(memory_bus); register = load(target); if (register == compare) store(target, new); unlock(memory_bus); return register; ``` * [load-link/store-conditional](https://en.wikipedia.org/wiki/Load-link/store-conditional) (LL/SC)：這類的指令成對使用。在 LL 讀取記憶體的值，同時標記進入 exclusive 狀態，SC 寫入時清除 exclusive 狀態。在 exclusive 狀態時如有其他 core 較早執行寫入，導致 exclusive 狀態被清除，則忽略這次的寫入並返回失敗。程式可在下一行發現失敗時重新執行 LL/SC 的動作直到成功為止。Power 和 Arm (ARMv6 以上) 提供這類的指令。其他尚有如 [test-and-set](https://en.wikipedia.org/wiki/Test-and-set) (簡稱 TAS) 和 [Fetch-and-add](https://en.wikipedia.org/wiki/Fetch-and-add) (簡稱 FAA) 等指令。 ARM 早期 CPU 使用的 `SWP` 指令在多核處理器中會遇上效能瓶頸 > 詳見 [ARM Synchronization Primitives Development Article](https://developer.arm.com/documentation/dht0008/a/) ARMv6 以上改用 LL/SC 指令，即 `ldrex/strex`。針對 x86 記憶體存取的指令，可加上 `LOCK` 前綴，以轉成 atomic 的存取。 CAS 的關鍵概念是，目前執行緒先載入共用變數的內含值，然後對其修改，最後寫入之際確保操作為 atomic —— 判定之前載入的共用記憶體內含值和目前操作是否一致，若相同，則將新變更的值寫回，否則就失敗。程式可搭配流程控制，確認 CAS 和資料變更符合預期地完成。以下是示範程式碼: ```c void atomic_sum_of_squares(volatile int *atom, int b) { int org, dst; do { org = *atom; dst = org * org + b * b; } while (!CAS(atom, &org, dst)); /* | | | * | | +-- 比較成功後，寫入指定地址 * | +-- 之前載入的數值 * +-- atomic 物件 */ } ``` CAS 指令對其所操作的 atomic 物件是「即刻生效」(或「即刻退回」)，只要沒有其他執行緒對該 atomic 物件進行變更，CAS 操作就會成功，當然就可結束，反之，lock 的實作內部通常也有 atomic 操作 (軟體演算法如 [Dekker's Algorithm](https://en.wikipedia.org/wiki/Dekker%27s_algorithm) 儘管可達成 mutual exclusion，因效率太差且對 memory order 做了限制，現代系統通常不用)，但其邏輯是等待 atomic 物件的狀態 (如 lock 和 unlock，或者 wait/signal)。換言之，CAS 的指令設計即考慮 [race condition](http://en.wikipedia.org/wiki/Race_condition) 的議題。延伸閱讀: * video: [A Pragmatic Introduction to Multicore Synchronization](https://youtu.be/LX4ugnzwggg?t=503), 08:23 起藉由 atomic 指令，我們可以實現一些基本的 counter 操作與簡單的 SMP lock，如 spinlock, rwlock 等，並確保程式狀態維護的正確性。然而當競爭相同 lock 的處理器數量增長時，卻可能會造成 scalability 不佳的問題。 ## C11 Atomics C11 標準引入 `_Atomic` 關鍵字，將特定的型態轉變為對應的 atomic 型態，如: * `char` $\to$ `_Atomic(char)` 且等同於 `atomic_char` * `int` $\to$ `_Atomic(int)` 且等同於 `atomic_int` C11 提供的 atomic 操作函式常見二種版本: * 沒有 memory order 參數 * 指定 memory order 參數，並以 `_explicit` 結尾以下是 C11 示範程式: (檔名 `atomic.c`) ```c= #include <pthread.h> #include <stdalign.h> #include <stdatomic.h> #include <stdbool.h> #include <stddef.h> #include <stdint.h> #include <stdio.h> #if defined(__x86_64__) || defined(__i386__) #define CPU_PAUSE() asm("pause") #elif defined(__aarch64__) #define CPU_PAUSE() asm("isb") #else #define CPU_PAUSE() do { /* nop */ } while (0) #endif struct atomic_float { volatile atomic_flag flag; int padding; /* avoid false sharing */ alignas(16) float value; }; static volatile struct atomic_float atomic_float_obj; static void atomic_val_inc(int nLoops) { for (int loop = 0; loop < nLoops; loop++) { while (atomic_flag_test_and_set(&atomic_float_obj.flag)) CPU_PAUSE(); atomic_float_obj.value += 1.0f; atomic_flag_clear(&atomic_float_obj.flag); } } static void *func(void *args) { atomic_val_inc(10000); return NULL; } int main(int argc, const char *argv[]) { printf("The size is: %zu, `value` offset is: %zu\n", sizeof(atomic_float_obj), offsetof(struct atomic_float, value)); atomic_float_obj.flag = (atomic_flag) ATOMIC_FLAG_INIT; atomic_float_obj.value = 0.0f; pthread_t tid; if (pthread_create(&tid, NULL, func, NULL) != 0) { puts("Failed to create a thread!"); return 1; } atomic_val_inc(10000); pthread_join(tid, NULL); printf("The final result is: %f\n", atomic_float_obj.value); return 0; } ``` 預期執行結果: (編譯時記得加上 `-lpthread` 參數) ``` The size is: 32, `value` offset is: 16 The final result is: 20000.000000 ``` 倘若我們將第 28 行 `while (atomic_flag_test_and_set(&atomic_float_obj.flag))` 改為 `while (0)` 編譯後，利用 `watch -n 1 ./atomic` 命令觀察，會發現執行輸出不一，即前述的 [race condition](http://en.wikipedia.org/wiki/Race_condition)。 > 若編譯時加上 `-fsanitize=thread -g` 選項，搭配上述第 28 行的 `while (0)` 程式碼變更，執行後會遇到以下警告: ``` WARNING: ThreadSanitizer: data race (pid=2473325) Read of size 4 at 0x5603a6108050 by main thread: #0 atomic_val_inc atomic.c:28 (atomic+0x1339) #1 main atomic.c:53 (atomic+0x14e7) Previous write of size 4 at 0x5603a6108050 by thread T1: #0 atomic_val_inc atomic.c:28 (atomic+0x135e) #1 func atomic.c:35 (atomic+0x13bc) Location is global 'atomic_float_obj' of size 32 at 0x5603a6108040 (atomic+0x000000004050) ``` 留意上方程式碼第 2 行的 `#include <stdalign.h>` 和第 20 行的 `alignas(16)`，這是 C11 規範的記憶體對齊 (alignment) 操作，以下定義於 `<stdalign.h>`: - `alignas` : 對齊記憶體地址 - `alignof` : 取得變數的對齊基數考慮以下程式碼: ```c alignas(16) int x; printBinary(&x); printf("%ld\n", alignof(x)); ``` 對應的執行輸出: ``` _0000_0000_0000_0000_0000_0000_1010_1101_1001_0100_1111_1111_1111_1000_1101_0000 16 ``` 因為 `int x` 變數的地址會對齊 16 (單位：位元組_，亦即 2^4^，在其二進位表示中，低位元處 4 個位元皆為 `0`，此處使用 `alignas` 以避免 [false sharing](https://en.wikipedia.org/wiki/False_sharing)。考慮以下結構體: ```c struct Par { int n1; int n2; }; ``` 在並行程式設計中，可能會改為: ```c struct Par { alignas(64) int n1; alignas(64) int n2; }; ``` 看似後者佔用更多記憶體空間 (64 + 64 > 4 + 4)，但後者效率較前者好，因為記憶體存取以 cacheline 為單位 (x86-64 為 64B，在 Arm 架構會依據組態而有不同表現，可見 [Detect L1 cache size at compile time](https://github.com/microsoft/mimalloc/pull/419))，上方程式碼刻意將成員變數 `n1` 和 `n2` 置於不同的 cacheline，可避免頻繁的 cache coherence。在 `<stdatomic.h>` 中，有個特別的變數 `atomic_flag`，其定義如下, 是個被結構化的 unsigned char: ```c typedef _Atomic struct { #if __GCC_ATOMIC_TEST_AND_SET_TRUEVAL == 1 _Bool __val; #else unsigned char __val; #endif } atomic_flag; ``` 可用巨集來初始化: ```c #define ATOMIC_FLAG_INIT { 0 } ``` 搭配以下函式操作 `atomic_flag` ```c atomic_test_and_set(); atomic_test_and_set_explicit(); atomic_flag_clear(); atomic_flag_clear_explicit(); ``` 延伸閱讀: * [ATOMIC](https://biscuitos.github.io/blog/ATOMIC/) ## 背後作祟的 cache :::success "[There are only two hard things in Computer Science: **cache invalidation** and naming things.](https://martinfowler.com/bliki/TwoHardThings.html)" -- [Phil Karlton](https://www.karlton.org/) ::: 電腦發展之初，CPU 和主記憶體都很慢，但後來 CPU 速度大幅提升，主記憶體讀寫速度反而沒有顯著提升，因此主記憶體的存取就比 CPU 緩慢，於是現代電腦加上 cache 以降低讀寫主記憶體的次數，從〈[Latency Numbers Every Programmer Should Know](https://gist.github.com/jboner/2841832)〉可知，存取主記憶體的時間是 100 ns，L1 cache 是 0.5 ns，兩者相距 200 倍。 > 延伸閱讀: [Napkin Math](https://github.com/sirupsen/napkin-math) / [演講](https://youtu.be/IxkSlnrRFqc) 顯然，不存在任何競爭或只被一個執行緒存取的 atomic 操作較快，此處的「競爭」指的是多個執行緒同時存取同一個 [cacheline](https://en.wikipedia.org/wiki/CPU_cache#Cache_entries) 。 ```graphviz digraph { splines=ortho subgraph cluster_threads { rank=same style=filled color=lightgrey label="Threads" node[style=filled shape=box] subgraph { rank=same 0 [color=dodgerblue] 1 [color=orange] dummy [style=invis width=0] 0->dummy->1 [style=invis] } } cache_controller [label="Cache controller" shape=record width=3.5 style=filled color=coral4 fontcolor=white] subgraph cluster_cache { style=filled color=lightgrey label="Cache" node[shape=plaintext] cache [label=< <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> <TR><TD BGCOLOR="dodgerblue"> </TD><TD BGCOLOR="dodgerblue"> </TD><TD BGCOLOR="dodgerblue"> </TD><TD BGCOLOR="dodgerblue"> </TD><TD BGCOLOR="dodgerblue"> </TD></TR> <TR><TD BGCOLOR="dodgerblue"> </TD><TD BGCOLOR="orange"> </TD><TD BGCOLOR="dodgerblue"> </TD><TD BGCOLOR="orange"> </TD><TD BGCOLOR="orange"> </TD></TR> <TR><TD BGCOLOR="dodgerblue"> </TD><TD BGCOLOR="dodgerblue"> </TD><TD BGCOLOR="orange"> </TD><TD BGCOLOR="orange"> </TD><TD BGCOLOR="orange"> </TD></TR> <TR><TD BGCOLOR="dodgerblue"> </TD><TD BGCOLOR="orange"> </TD><TD BGCOLOR="orange"> </TD><TD BGCOLOR="orange"> </TD><TD BGCOLOR="orange"> </TD></TR> </TABLE>>] } memory_ctl [label="Memory Controller" shape=record width=2 style=filled color=coral4 fontcolor=white] RAM [shape=record width=3] {0, 1}->cache_controller dummy->cache_controller [style=invis] cache_controller->cache->memory_ctl->RAM } ``` 接下來我們藉由實驗來回顧，給定程式碼: (檔名: `cacheline.c`) ```c= #include <pthread.h> #include <stdio.h> #include <stdlib.h> #ifndef min #define min(x, y) (x) < (y) ? (x) : (y) #endif #define N_THREADS 128 static int64_t loop_count = 0; #pragma pack(1) struct data { int32_t pad[15]; int64_t v; }; static struct data value __attribute__((aligned(64))); static int64_t counter[N_THREADS]; static void worker(int *cnt) { for (int64_t i = 0; i < loop_count; ++i) { const int64_t t = value.v; if (t != 0L || t != ~0L) *cnt += 1; value.v = ~t; /* creates a compiler level memory barrier * forcing optimizer to not re-order memory * accesses across the barrier. */ __asm__ volatile("" ::: "memory"); } } int main(int argc, char *argv[]) { pthread_t threads[N_THREADS]; if (argc != 3) { fprintf(stderr, "USAGE: %s <threads> <loopcount>\n", argv[0]); return 1; } /* Parse argument */ int64_t n = min(atol(argv[1]), N_THREADS); loop_count = atol(argv[2]); /* Start the threads */ for (int64_t i = 0L; i < n; ++i) pthread_create(&threads[i], NULL, (void *(*) (void *) ) worker, &counter[i]); int64_t count = 0L; for (int64_t i = 0L; i < n; ++i) { pthread_join(threads[i], NULL); count += counter[i]; } printf("iteration: %lu\n", count); printf("data size: %lu\n", sizeof(value)); printf("final: %016lX\n", value.v); return 0; } ``` 這段程式碼操作貌似簡單：建立執行緒，不斷對全域變數進行 `NOT` (第 28 行)，這樣最終的結果 (即第 58 行的輸出) 為何？倘若我們不做實驗，只用臆測，會歸納出在 `int64_t` 資料寬度的內容，不是全為 `0`，就是全為 `1`，但真實狀況會如何呢？編譯方式: ```shell $ gcc -o cacheline cacheline.c -lpthread ``` 在真正的多核處理器硬體 (注意: 不能在虛擬機器上測試)，這個程式預期指定執行緒和測試總量，例如在 AMD Ryzen Threadripper 2990WX 32-Core Processor 執行: ```shell $ ./cacheline 24 10000 iteration: 240000 data size: 68 final: ? ``` 可用以下命令持續觀察: ```shell $ watch -n 1 "./cacheline 24 10000" ``` 其中 `final` 那行有 4 種可能: 1. `FFFFFFFFFFFFFFFF` 2. `0000000000000000` 3. `00000000FFFFFFFF` 4. `FFFFFFFF00000000` 前 2 者是我們不用執行程式即可臆測的結果，但後 2 者該如何解釋？注意看上述程式碼的第 12 到第 16 行，成員變數 `v` 恰好放在跨越 2 個 cacheline (在 `x86_64` 架構中，cacheline 為 64 bytes)，從而引出違反直覺的事實：存取一個 64 位元寬度的資料，對 CPU 需要 2 個存取。 > 延伸閱讀: [你所不知道的 C 語言：記憶體管理、對齊及硬體特性](https://hackmd.io/@sysprog/c-memory) 硬體的 cache coherence 操作的基本單元就是 cache line，為了寫進記憶體，CPU 必須 exclusive 地佔有該 cacheline，而若一個變數座落於在 2 個不同的 cacheline 上，則 cacheline 之間的競爭是「沒有」atomic 特性保證，資料讀取也類似。《[Intel® 64 architecture memory ordering white paper](https://software.intel.com/content/www/us/en/develop/articles/intel-sdm.html)》(已整合進《Intel® 64 and IA-32 architectures software developer's manual》的第 3 卷) 提及: > Intel 64 memory ordering guarantees that for each of the following memory-access instructions, the constituent memory operation appears to execute as a single memory access regardless of memory type: > 1. Instructions that read or write a single byte. > 2. Instructions that read or write a word (2 bytes) whose address is aligned on a 2 byte boundary. > 3. Instructions that read or write a doubleword (4 bytes) whose address is aligned on a 4 byte boundary. > 4. Instructions that read or write a quadword (8 bytes) whose address is aligned on an 8 byte boundary. > All locked instructions (the implicitly locked xchg instruction and other read-modify-write instructions with a lock prefix) are an indivisible and uninterruptible sequence of load(s) followed by store(s) regardless of memory type and alignment. > > Other instructions may be implemented with multiple memory accesses. From a memory-ordering point of view, **there are no guarantees regarding the relative order in which the constituent memory accesses are made**. There is also no guarantee that the constituent operations of a store are executed in the same order as the constituent operations of a load. 上述描述可知，Intel 微處理器架構只保證滿足 alignment 規則的變數存取的 atomic 特性，但不能保證跨越多個 cacheline 的狀況。 ## 多核處理器之間的 cache coherence 多核和單核究竟有什麼差異？多數問題就來自 cache! 在多核處理器的機器中，每個 CPU 都有自己的 cache，以彌補 CPU 和主記憶體之間較慢的存取速度，當個特定資料首次被特定的 CPU 讀取時，此資料顯然不存在於該 CPU 的 cache 中 (即 cache miss)，意味著 CPU 需要自主記憶體中讀取資料 (為此，CPU 通常要等待數百個 cycle)，此資料最終將會存放於 CPU 的 cache 中，這樣後續就能直接自 cache 上快速存取，不用再透過主記憶體。因為每個 CPU 上的 cache 資料是 private 的，因此在進行寫入操作時，會造成其他 CPU 上的 cache 資料不一致的問題。示意如下： ![image](https://hackmd.io/_uploads/ByoUHbZbA.png) > 取自 [MIT 6.004 L25: Cache Coherence](https://youtu.be/83jOKVb_HTM) 解說： 1. Core~0~ load memory from address `0xA`，資料內容為 `2` 2. Core~2~ store memory to address `0xA`，更新資料在自己的 cache 上，並在稍後補回 memory，而更新內容為 `3` 3. Core~2~ 的更新不被 Core~0~ 得知，因此 Core~0~ 還以為 `0xA` 上所存的資料是 `2`，但顯然這份資料已過時。為了確保所有 CPU 上的 cache 資料是一致的，當某個 CPU 進行寫入操作時，它必須保證其他 CPU 已將資料從他的 cache 中移除 (方可確保一致性)，僅在移除操作完成後，此 CPU 才能安全的修改資料。專門處理一致性協定統稱為 cache-coherence protocol。透過 cache-coherence protocol，任何一個 CPU 要寫入資料前，都要先確保其他 CPU 已 invalid 同一位置的 cache 後 (希望寫入的 CPU 廣播 invalidate，其它 CPU 回 invalidate ack)，方可寫資料到自己的 cache，並在稍後補寫回主記憶體。一個處理器寫入自己的 (private) L1 cache 非常快 (4 cycles, ~2ns)，但當另一個處理器讀取或寫入同一處記憶體時，它要確認看到其他處理器核對應的 cacheline。 ![](https://hackmd.io/_uploads/ByuISh7-2.png) 這帶來新的問題：同一個資料有可能會分佈在多個 CPU 的 cache 中，從而會有一致性 (consistency) 問題，更明確來說，在同一時間，同一變數在不同的 CPU 可能會有不同的值，如下圖： ![](https://hackmd.io/_uploads/H1EDS2Xb2.png) 試想一個情境：當 CPU~0~ 剛修改記憶體某處的資料，最新的數值是先寫入到 CPU~0~ 的 cache，等待 cache line 被標註為 invalidate，才會寫入到主記憶體，若此時另一個 CPU (如 CPU~7~) 打算存取主記憶體中同一位置的資料，則不論是 CPU~7~ 的 cache，抑或是主記憶體中都沒有最新值，後者只存在於 CPU~0~ 的 cache中，是此，我們需要一個機制來確保 cache 在不同 CPU 間的一致性，以軟體的觀點，這個過程也該是 atomic，即不能在中間穿插其他程式碼，只能等待處理器完成 [cache coherence](https://en.wikipedia.org/wiki/Cache_coherence)，這個複雜的硬體操作會讓 atomic 指令成本大幅提升，`atomic_fetch_add` 可能因此需要 700 ns。像是 `x = 1;` 和 `y = x;` 這樣的 C 語言敘述看似簡單，但對 CPU 來說，可能要做非常多的工作，因為 CPU 既要保證存取效率 (藉由 cache)，還要保證 cache 內部資料的一致。因此，對於現代處理器架構來說，都在其系統中引入更 weak (注意: 這不是說能力的 weak，而是「順序」的 weak，可詮釋為「身段的柔軟」) 的 memory order，從而使整體的存取效率得以提升。不同 CPU 間是如何進行溝通的。CPU 之間的溝通主要是透過 [system bus](https://en.wikipedia.org/wiki/System_bus)，system bus 主要是用來連接 CPU、主記憶體和其他 I/O 設備，因為 CPU 中的 cache 進行 cache coherency 時，也是透過 system bus 來廣播 Probe Read 以及 Probe Write 請求，其他 CPU 也是透過 system bus 進行相對應的回應。因此，我們也稱 system bus 為 cache coherent interconnect (CCI)。 ![image](https://hackmd.io/_uploads/SJxiLW--A.png) > 取自 [OpenMP, Cache Coherence](https://inst.eecs.berkeley.edu/~cs61c/su20/pdfs/lectures/lec23.pdf) 當一個特定資料首次被特定的 CPU 讀取時，此資料顯然不存在於該 CPU 的 cache 中 (即 cache miss)，意味著 CPU 需要自主記憶體中讀取資料 (為此，CPU 通常要等待數百個週期)，此資料最終將會存放於 CPU 的 cache 中，這樣後續就能直接自 cache 上快速存取。當某個 CPU 進行寫入操作時，它必須保證其他 CPU 已將資料從它們的 cache 中移除 (方可確保 **一致性**)，僅在移除操作完成後，此 CPU 才能安全的修改資料。顯然，倘若存在多個 cache 時，勢必要有個專門處理一致性的機制，排除潛在的資料不一致問題，也正因如此，可能會導致記憶體存取的亂序議題。 ```graphviz digraph { splines=ortho node [shape=box] subgraph { rank=same node [width=2] cpu0 [label=<CPU 0>] cpu1 [label=<CPU 1>] } subgraph { rank=same node [width=2] cache0 [label="cache"] cache1 [label="cache"] } subgraph { rank=same node [shape=point width=0] edge [dir=none] p0->p1->p2 } memory [label="Memory" width=2] cpu0->cache0->p0 [weight=2 dir=none] cpu1->cache1->p2 [weight=2 dir=none] p1->memory [dir=none] } ``` 使用 cache 時，要確保個別 CPU 有看到「==一致== (coherent) 的資料」(注意重點放在 CPU 之間的順序，而非讓 cache 和 memory 保持==同步== [synchronous]，如此概念差異會影響到架構設計)。維護這點的協定統稱為 [cache-coherence protocol](https://en.wikipedia.org/wiki/Cache_coherence)。實作 cache-coherence protocol 時，系統設計者會定義一系列請求，這些請求有 CPU 對於自己的 cache 的請求，也有 CPU 對於其他 CPU 的 cache 的請求。定義如下: * Read Hit: CPU 要讀取資料時，發現自己的 cache 中含有這份資料 * Write Hit: CPU 要寫入資料時，發現自己的 cache 中含有這份資料 * Read Miss: CPU 要讀取資料時，發現自己的 cache 中沒有這份資料 * Write Miss: CPU 要讀取資料時，發現自己的 cache 中沒有這份資料 * Probe Read: 某一 CPU 要讀取資料時，先去看其他 CPU 中的 cache 有沒有更新這份資料 * Probe Write: 某一 CPU 要寫入資料時，去看其他 CPU 中的 cache 是否存有這份資料 * Probe Read Hit: 其他 CPU 中的 cache 打算讀取這份資料，且該 CPU 含有這份資料 * Probe Write Hit: 其他 CPU 中的 cache 打算寫入這份資料，且該 CPU 含有這份資料 ### MESI protocol [MESI protocol](https://en.wikipedia.org/wiki/MESI_protocol) 是個基本形式，從 [MESI protocol](https://en.wikipedia.org/wiki/MESI_protocol) 可了解 CPU 之間如何維持看到一致的資料。 | | M | E | S | I | | --- |:------------------:|:------------------:|:------------------:|:------------------:| | M | :x: | :x: | :x: | :heavy_check_mark: | | E | :x: | :x: | :x: | :heavy_check_mark: | | S | :x: | :x: | :heavy_check_mark: | :heavy_check_mark: | | I | :heavy_check_mark: | :heavy_check_mark: | :heavy_check_mark: | :heavy_check_mark: | 簡述 4 個狀態意思: 1. Modified(M) * 這份資料是最新且被修改過的，這份資料可以被寫回主記憶體 * 其他 CPU 上的 cache 沒有這份資料 * 在主記憶體中的這份資料是過時的 2. Exclusive(E) * 其他 CPU 上的 cache 沒有這份資料 * 在主記憶體中的這份資料和 cache 中存有的這份資料是一樣的 * 其他 CPU 上的 cache 發 probe read 時，會將資料提供給他 3. Shared(S) * 其他 CPU 上的 cache 必定含有同一份資料 * 在主記憶體中的這份資料和 cache 中存有的這份資料是一樣的 4. Invalid(I) * cache 中存有的這份資料是過時的 - [ ] CPU 對自己的 cache 下請求的狀態圖 ![image](https://hackmd.io/_uploads/rJsnwZWbA.png) > 取自 [OpenMP, Cache Coherence](https://inst.eecs.berkeley.edu/~cs61c/su20/pdfs/lectures/lec23.pdf) - [ ] 收到其他 CPU 上的 cache 下請求的狀態圖 ![image](https://hackmd.io/_uploads/ByuavbbbR.png) > 取自 [OpenMP, Cache Coherence](https://inst.eecs.berkeley.edu/~cs61c/su20/pdfs/lectures/lec23.pdf) 實作上，用 3 個位元來表示該 cacheline 的狀態，分別是 valid bit, dirty bit 和 shared bit，由這三個 bit 來組合出 `MESI` 4 個不同的狀態: | | Valid bit | Dirty bit | Shared bit | | -------- | -------- | -------- | -------- | | Modified | 1 | 1 | 0 | | Exclusive | 1 | 0 | 0 | | Shared | 1 | 0 | 1 | | Invalid | 0 | X | X | > X 指 doesn't matter 舉例說明 MESI protocol 的流程: 1. CPU~0~ 對主記憶體中的 Block 0 進行讀取，因為 CPU~0~ 是第一個且第一次進行讀取，因此這個 cacheline 的狀態會設定成 `Exclusive` 2. CPU~1~ 想對 Block 0 進行讀取，他會發 Probe read 給 Processor 0，接著 Processor 0 會收到 Probe read hit，因為其 cache 中有 Block 0 的資料，Processor 1 從 CPU~0~ 讀取資料，並將其 cacheline 狀態設定成 `Shared` 3. CPU~0~ 想對 Block 0 進行寫入，CPU~0~ 含有 Block 0 的 cacheline 被設定成 `Modified`，他必須發 Probe Write 給 CPU~1~，去看 CPU~1~ 的 cache 中是否含有 Block 0。接著 CPU~1~ 會收到 Probe write hit，因為其 cache 中有 Block 0 的資料。此時，CPU~1~ 含有 Block 0 的 cacheline 也會被設定成 `Invalid`，因為其資料已過時。 4. CPU~1~ 想對 Block 0 進行讀取，他會發 Probe read 給 CPU~0~，接著 Processor 0 會收到 Probe read hit，因為其 cache 中有 Block 0 的資料。因為這個 cacheline 的狀態是 `Modified`，當收到 Probe read hit 時，會將這份資料寫回主記憶體中，並將狀態改為 `Shared`，接著 CPU~1~ 從 CPU~0~ 讀取資料，並將其 cacheline 狀態設定成 `Shared` MESI protocol 的缺點就是每次發送 Probe read 讀到一個狀態為 `Modified` 的 cacheline 時，就要將資料更新回主記憶體，但將資料寫回主記憶體是非常浪費時間的。 ### MOESI protocol 為了避免將資料寫回主記憶體，MOESI protocol 加入新的狀態 Owner，並稍微修改 Shared 狀態的定義: 1. Owner(O) * 其他 CPU 上的 cache 含有這份資料　 * 在主記憶體中的這份資料和 cache 中存有的這份資料不一樣 (Owner 擁有的資料比較新) * 其他 CPU 上的 cache 發 probe read 時，會將資料提供給他且不會寫回 memory 3. Shared(S) * 其他 CPU 上的 cache 必定含有同一份資料 * 在主記憶體中的這份資料和 cache 中存有的這份資料**可能是**一樣的 - [ ] CPU 對自己的 cache 下請求的狀態圖 ![image](https://hackmd.io/_uploads/B1RI_bZ-R.png) > 取自 [OpenMP, Cache Coherence](https://inst.eecs.berkeley.edu/~cs61c/su20/pdfs/lectures/lec23.pdf) - [ ] 收到其他 CPU 上的 cache 下請求的狀態圖 ![image](https://hackmd.io/_uploads/rJhvuZ-ZC.png) > 取自 [OpenMP, Cache Coherence](https://inst.eecs.berkeley.edu/~cs61c/su20/pdfs/lectures/lec23.pdf) 實作上，用 3 個 bit 來表示該 cacheline 的狀態，分別是 valid bit、dirty bit 和 shared bit，由這三個 bit 來組合出 `MOESI` 5 個不同的狀態: | | Valid bit | Dirty bit | Shared bit | | -------- | -------- | -------- | -------- | | Modified | 1 | 1 | 0 | | Owner | 1 | 1 | 1 | | Exclusive | 1 | 0 | 0 | | Shared | 1 | 0 | 1 | | Invalid | 0 | X | X | X = doesn’t matter 我們一樣舉個例子來說明 MOESI protocol 的流程: 1. Processor 0 對主記憶體中的 Block 0 進行讀取，因為 Processor 0 是第一個且第一次進行讀取，因此這個 cacheline 的狀態會設定成 `Exclusive` 2. Processor 0 想對 Block 0 進行寫入，Processor 0 含有 Block 0 的 cacheline 被設定成 `Modified`，他必須發 Probe Write 給 Processor 1，但因為 Processor 1 的 cache 中有是空的，所以沒有任何改變。 3. Processor 1 想對 Block 0 進行讀取，他會發 Probe read 給 Processor 0，接著 Processor 0 會收到 Probe read hit，因為其 cache 中有 Block 0 的資料，Processor 1 直接從 Processor 0 讀取資料，並將其 cacheline 狀態設定成 `Shared`，而 Processor 0 上的 cacheline 狀態則會從 `Modified` 變為 `Owner`。 4. Processor 0 想對 Block 0 進行寫入，Processor 0 含有 Block 0 的 cacheline 從 `Modified` 被設定成 `Owner`，他必須發 Probe Write 給 Processor 1，去看 Processor 1 的 cache 中是否含有 Block 0。接著 Processor 1 會收到 Probe write hit，因為其 cache 中有 Block 0 的資料。此時，Processor 1 含有 Block 0 的 cacheline 也會被設定成 `Invalid`，因為其資料已過時。 5. Processor 1 想對 Block 0 進行讀取，他會發 Probe read 給 Processor 0，接著 Processor 0 會收到 Probe read hit，因為其 cache 中有 Block 0 的資料，Processor 1 直接從 Processor 0 讀取資料，並將其 cacheline 狀態設定成 `Shared`，而 Processor 0 上的 cacheline 狀態則會從 `Modified` 變為 `Owner`。透過上述案例我們可以發現，整個過程中並沒有涉及到任何將 cache 中資料更新回主記憶體的動作，因此，MOESI protocol 成功解決要將資料寫回主記憶體的問題。 ## cache coherence 對程式效能的衝擊接著我們考慮一個具備 3 層 cache 且有 2 個處理器核的系統，向下箭頭表示儲存 (即 write) 操作、向上箭頭表示載入 (即 read) 操作，對 CPU~0~ 和 CPU~1~ 來說，同顆 CPU 其左側操作的時序先於右側操作。如下圖: ```graphviz digraph { splines=ortho node [shape=record] subgraph { rank=same node [width=2] pro0 [label=<CPU0>] pro1 [label=<CPU1>] } subgraph { rank=same node [width=2] l1_0 [label="L1 Cache"] l1_1 [label="L1 Cache"] dummy0 [width=1 style=invis] l1_0->dummy0->l1_1 [style=invis] } subgraph { rank=same node [width=2] l2_0 [label="L2 Cache"] l2_1 [label="L2 Cache"] dummy1 [width=1 style=invis] l2_0->dummy1->l2_1 [style=invis] } l3 [label="L3 Cache" width=5.5] subgraph { rank=same node [width=1.5] ram0 [label=RAM] // ram1 [label=RAM] ram2 [label=RAM] ram3 [label=RAM] ram0->ram2->ram3 [dir=none] } pro0->l1_0 [xlabel="x = 1"] pro0->l1_0 [xlabel="y = 2" minlen=2] l1_0->l2_0 [xlabel="x = 1"] l1_0->l2_0 [xlabel="y = 2"] l2_0->l3 [xlabel="y = 2" weight=3] l2_0->l3 [xlabel="x = 1"] pro1->l1_1 [xlabel="y = 0"] l1_1->pro1 [xlabel="y = 2"] l1_1->pro1 [xlabel="x = 1"] l1_1->l2_1 [xlabel="y = 0"] l2_1->l1_1 [xlabel="x = 1"] l2_1->l1_1 [xlabel="y = 2" minlen=2] l2_1->l3 [xlabel="y = 0" weight=2] l3->l2_1 [xlabel="y = 2"] l3->l2_1 [xlabel="x = 1" minlen=2] l3->ram0 [xlabel="x = 1" weight=2] l3->ram0 [xlabel="y = 2" weight=2] l3->ram3 [xlabel="y = 0"] ram3->l3 [xlabel="x = 1" weight=2] ram3->l3 [xlabel="y = 2" weight=1 minlen=2] } ``` 在上圖中，有二個被原生執行緒 (native thread，指執行緒被作業系統核心識別，且納入排程的執行單元，在本例中，分別執行在 CPU~0~ 和 CPU~1~) 共享的變數 `x` 和 `y`，同時假定 CPU~1~ 的執行緒先做 `y = 0;` 的儲存操作，使得在它的 cache 中都安排好存放變數 `y` 的 cache 內容 (entry)，且假定此時沒有關於任何針對變數 `x` 的 cache 內容。首先，CPU~1~ 的執行緒先對 `y` 進行 `y = 0` 的儲存操作，等該操作完畢後，CPU~0~ 的執行緒才有動作。CPU~0~ 的執行緒先做 `x = 1` 的儲存操作，接著做 `y = 2` 的儲存操作。完成之後，CPU~1~ 的執行緒立即對 `x` 和 `y` 進行讀取。我們從圖中可見，`x` 和 `y` 的儲存操作依次經過 CPU~0~ 的 L1 cache, L2 cache，再是 CPU~0~ 和 CPU~1~ 共用的 L3 cache，最後到外部記憶體。此時，L3 cache 中已有 `x` 和 `y` 這兩個變數對應的 cache 內容。因此在 CPU~1~ 讀取時，`x` 和 `y` 的寫入順序是一致的。到了 CPU~1~ 的 L2 Cache 時，由於之前沒有 `x` 相關的 cache 內容，因此此時 L2 cache 控制器會進行判斷是直接將它分配給一個空白的 cache 條目，抑或將已有的 cache 內容進行逐出 (evict)，然後將變數 `x` 所處的 cacheline 增添到到 cache 內容中。這裡就會有一些延遲與記憶體重新安排的情況。此時，由於變數 `y` 已處於 cache 內容中，因此它有可能被直接寫回（write back），只要之前針對 `x` 的 cacheline 的安排過程，不將 `y` 所處的 cacheline 予以逐出 (evict)。如此一來，右側執行緒所觀察到的寫入順序，就會變為先寫 `y` 再寫 `x`。注意：上述情況僅僅是 memory order 的其中一種，x86 和 Arm 處理器中均引入 [Non-Temporal 的載入和儲存](https://sites.utexas.edu/jdm4372/2018/01/01/notes-on-non-temporal-aka-streaming-stores/) 操作，這些操作不會經由 cache，而是直接針對外部記憶體控制器進行存取。而它們的存取順序就是典型的 weak memory order，因為即便在匯流排上，都會有各種不同情況發生。這就好比說，在網際網路通訊時，先發送的請求反而後送達的情況，特別在無線網路訊號不佳的狀況，我們之前在通訊聊天軟體中發送的幾則訊息尚在「轉圈」(即等待發送)，等訊號品質變好時，往往是前次最後發送的那則訊息，率先送達予對方。存取被多個執行緒頻繁共享的主記憶體往往很慢。在某些情境中，critical section (CS) 看似很短，但 spinlock 卻承受嚴重的效能問題，因為 spinlock 使用的 CAS 指令必須等待最新的 cacheline，看上去只有幾條指令，花費數千數萬 ns 也有可能。要提高速度，就要避免讓 CPU 頻繁進行 [cache coherence](https://en.wikipedia.org/wiki/Cache_coherence)。這不單和 atomic 指令本身有關，還會影響到程式的整體表現。最有效的解決方法就是**降低共享**。 * 一個依賴全域 [multi-producer/multiple-consumer](https://en.wikipedia.org/wiki/Producer%E2%80%93consumer_problem) (MPMC) 的程式難有好的 scalability，因為 MPMC 的極限吞吐量 (throughput) 取決於 cache coherence 的成本，而非處理器的個數! 最好是用多個 SPMC 或多個 MPSC，甚至多個 SPSC 代替，在源頭就規避掉競爭。 * 另一個例子是計數器，如果所有執行緒都頻繁修改一個計數器，性能就會大受影響，同樣是因不同的處理器不停地進行 cache coherence。若這個計數器只是用於輸出流水號碼，我們可用 [thread-local storage](https://gcc.gnu.org/onlinedocs/gcc/Thread-Local.html) (TLS) 改寫程式碼，然後規範特定時機點合併所有執行緒的數值，這樣相較之前，可能會有數十倍的效能落差。相關的程式設計陷阱是 [false sharing](https://en.wikipedia.org/wiki/False_sharing)，示意如下: ![](https://hackmd.io/_uploads/H1yFHnQb2.png) cache line 的「所有權」獲取過程涉及到多個 CPU 之間的訊息傳遞，相較直接在單核進行操作，執行成本必定居高不下，然而此處有個陷阱：程式開發過程中，我們通常以變數作為「思想」操作的單元，但 CPU 之間競爭的單元卻是 cacheline (常見 64 個位元組)，於是上圖展示一種狀況：在並行的程式中，一個執行緒不斷寫入變數 `X`，另一個執行緒不斷寫入變數 `Y`，二者本來相互不衝突，但 `X` 和 `Y` 這二個變數在記憶體中的排列若入同一個 cache line 範圍，導致執行過程中，在兩個 CPU 之間不斷發生該 cacheline 的競爭，從而程式效率低落。如此本該「不分享」的二個變數，卻因 cacheline 而「分享」，影響到記憶體存取，就稱為 [false sharing](https://en.wikipedia.org/wiki/False_sharing)。我們可用簡單的程式來測試 ```shell $ wget https://raw.githubusercontent.com/Zeosleus/False_Sharing/main/false_sharing.c $ gcc -o false_sharing false_sharing.c -lpthread ``` 在 AMD Ryzen Threadripper 2990WX 32-Core Processor 實驗: - [ ] 有 false sharing 的狀況 ```shell $ ./false_sharing Total wtime elapsed = 7.093128 seconds ``` - [ ] 抑制 false sharing ```shell $ ./false_sharing --nofalse-sharing Total wtime elapsed = 2.976462 seconds ``` 我們可見 `7.09` 到 `2.97` 秒這樣顯著的落差。用 `$ sudo perf stat -d <執行檔和參數>` 觀察: - [ ] 有 false sharing ``` 175,3222,0759 L1-dcache-loads # 1208.436 M/sec (62.51%) 18,0305,0951 L1-dcache-load-misses # 10.28% of all L1-dcache hits (62.45%) ``` - [ ] 抑制 false sharing ``` 140,1115,6709 L1-dcache-loads # 2353.822 M/sec (62.41%) 48,4434 L1-dcache-load-misses # 0.00% of all L1-dcache hits (62.32%) ``` 延伸閱讀: * [C2C - False Sharing Detection in Linux Perf](https://joemario.github.io/blog/2016/09/01/c2c-blog/) * 〈[What Every Programmer Should Know About Memory](https://www.akkadia.org/drepper/cpumemory.pdf)〉 / [繁體中文翻譯](https://sysprog21.github.io/cpumemory-zhtw/) ## Memory Ordering 和 Barrier 僅靠 atomic 指令，無法達到對共用資源的存取控制，即使簡單如 [spinlock](https://en.wikipedia.org/wiki/Spinlock) 或 [reference count](https://en.wikipedia.org/wiki/Reference_counting)，看上去正確的程式碼也可能會出錯。為何？因為 [memory (re)ordering](https://en.wikipedia.org/wiki/Memory_ordering): * [Memory Ordering at Compile Time](https://preshing.com/20120625/memory-ordering-at-compile-time/) * [Out-of-order execution](https://en.wikipedia.org/wiki/Out-of-order_execution) 為何有 memory reordering 呢？動機非常自然，CPU 要盡量塞滿每個 cycle，在單位時間內運行盡量多的指令。如前述，存取指令在等待 cache coherence 時，可能要花費數百 ns，最高效且直觀的策略是同時處理多個 cache coherence，而非一個接著一個。一個執行緒在程式碼中對多個變數的依次修改，可能會以不同的次序 [cohere](https://www.dictionary.com/browse/cohere) (`coherence` 的動詞) 到另一個執行緒所在的處理器上。不同處理器對資料的需求不同，也會導致 cacheline 的讀取和寫入順序的落差。既然 CPU 會 reorder 指令的執行順序，為何沒有造成混亂？因為有個前提：對於前後有資料的相依 (dependency) 的指令，CPU 通常不會去做 reorder (Alpha 架構除外)，可看作處理器提升速度所做最佳化策略的「底線」。 ![](https://hackmd.io/_uploads/SkX9SnQ-n.png) 上圖中，前一道指令將 `1` 指派給變數 `x`，後一道指令將變數 `x` 的值指派給變數 `y`，那麼這兩道指令的執行順序 (通常) 不會被 CPU 改變。對於沒有這種相依關係的指令，CPU 就有發揮的空間，不同架構的處理器的策略不同，這也是 CPU 的 memory ordering 要顧及的議題。在 Arm 架構中，只要沒有相依關係，對指令的執行順序沒有要求，`load` 指令 (以` L` 表示) 和 `store` 指令 (以 `S` 表示) 可任意交換，屬於 relaxed model，即 weak order。  ```graphviz digraph order { node [shape=box] { a [label="L"] b [label="S"] c [label="L"] d [label="S"] } { a1 [label="L"] b1 [label="S"] c1 [label="S"] d1 [label="L"] } { a->a1 [dir="both" fontsize="20" penwidth ="2" headlabel="◯" labeldistance="3.5" labelangle="0" minlen="2"] b->b1 [dir="both" fontsize="20" penwidth ="2" headlabel="◯" labeldistance="3.5" labelangle="0" minlen="2"] c->c1 [dir="both" fontsize="20" penwidth ="2" headlabel="◯" labeldistance="3.5" labelangle="0" minlen="2"] d->d1 [dir="both" fontsize="20" penwidth ="2" headlabel="◯" labeldistance="3.5" labelangle="0" minlen="2"] } } ``` > $\uparrow$ Arm: weak order 在 x86 中，對於同一 CPU 執行的 `load` 指令後接 `load` 指令 (即 `L-L`)，store 指令後接 store指令 (即 `S-S`)，load 指令後接 store 指令 (即 `L-S`)，都禁止交換指令的執行順序，只有 store 指令後接 `load` 指令 (即 `S-L`) 時才可。這種 memory order 被稱為 [TSO (Total Store Order)](https://en.wikipedia.org/wiki/Memory_ordering)，即 strong order。  ```graphviz digraph order { node [shape=box] { a [label="L"] b [label="S"] c [label="L"] d [label="S"] } { a1 [label="L"] b1 [label="S"] c1 [label="S"] d1 [label="L"] } { a->a1 [dir="both" fontsize="20" color = "red" headlabel="×" labeldistance="3.5" labelangle="0" minlen="2"] b->b1 [dir="both" fontsize="20" color = "red" headlabel="×" labeldistance="3.5" labelangle="0" minlen="2"] c->c1 [dir="both" fontsize="20" color = "red" headlabel="×" labeldistance="3.5" labelangle="0" minlen="2"] d->d1 [dir="both" fontsize="20" penwidth ="2" headlabel="◯" labeldistance="3.5" labelangle="0" minlen="2"] } } ``` > $\uparrow$ x86: TSO / strong order 為何唯獨 `store` 指令後接 `load` 指令這種情況，被 x86 允許重排呢？因為寫入一則資料的動作若尚未完成，一般沒多大影響，反之，如果讀取一則資料的操作沒完成，就可能對後面依賴這個資料的指令的繼續執行，造成影響，也就是 "stall"，因此 CPU 會優先保證讀取操作的完成。換言之，「讀取」會比「寫入」重要，因此 `load` 可跑到 `store` 前面去執行，而 [TSO (Total Store Order)](https://en.wikipedia.org/wiki/Memory_ordering) 其他的三種情況，要不重要性相當，要不後面的一道指令較不重要。不精準來說，memory order 一旦越 weak (不嚴格)，達到同等速度的硬體成本則越低。但也不要死板認定 x86 僅有 strong order，它也支持對 memory order 的動態調整 —— 處理硬體周邊 I/O 時，memory order 則 strong，其他時候則可適當地 weak，以獲取更好的速度。依據 AMD 公司的手冊《[AMD64 ArchitectureProgrammer's Manual Volume 2](http://developer.amd.com/wordpress/media/2012/10/24593_APM_v2.pdf)》第 7.1 節，AMD64 允許部分 out-of-order reads (`L-L` 形式的 reorder)，這與記憶體型態相關，詳見該手冊第 7.4.2 節 "Memory Barrier Interaction with Memory Types"。延伸閱讀: * [Memory Consistency Models: A Tutorial](https://www.cs.utexas.edu/~bornholt/post/memory-models.html) * [x86 TSO: A Programmer's Model for x86 Multiprocessors](https://paulcavallaro.com/blog/x86-tso-a-programmers-model-for-x86-multiprocessors/) 在亂序 (out-of-order) 執行時，一個處理器真正執行指令的順序，是由可用的輸入資料決定，而非程式開發者在程式碼規範的順序。現代處理器可分 in-order 和 out-of-order 等二種實作。 - [ ] In-order processors (循序) 執行步驟 1. instruction fetch (IF) 2. 若指令的 input operands 可用 (例如已在暫存器中)，則將此指令分派 (dispatch) 到適當的功能單元中。若一個或多個 input operands 不可用 (通常因為要從主記憶體獲取)，則處理器會等待直到它們可用 3. 指令被適當的功能單元執行 (IE) 4. 功能單元將結果寫回到 register file (CPU 的一組暫存器) - [ ] Out-of-order processors (亂序) 執行步驟 1. instruction fetch (IF) 2. 指令被分派 (dispatch) 到 instruction queue 3. 指令在 instruction queue 中等待，直到 input operands 可用 (一旦 input operands 可用，指令即可離開 instruction queue，即便更早的指令尚未執行) 4. 指令被分派到適當的功能單元並執行 (IE) 5. 執行結果被放入 queue 中，而非立即寫入 register file 6. 只有所有更早請求執行的指令的執行結果被寫入 register file 後，指令執行的結果才被寫入 register file (即執行結果重排，讓執行看起來是有序的) 由上可見，亂序執行相比循序執行能夠避免等待不可用的 input operands (即上述 in-order 執行的第二步)，從而提高執行速度。現代電腦系統中，處理器執行的速度遠高於主記憶體，in-order 處理器花在等待可用資料的時間中，out-of-order 處理器已可處理大量指令。總結 out-of-order 處理器的流程: * 對單個 CPU 來說，instruction fetch (IF) 是循序的 (藉由 queue 實作) * 對單個 CPU 來說，指令執行結果也是依序寫回 register file (也藉由 queue 實作) 由此可知，在單一處理器，不考慮編譯器優化，多執行緒執行不存在記憶體亂序存取的議題。從 Linux 核心原始程式碼中，也可得到類似的結論 (檔案: `include/asm-generic/barrier.h`) ```c #ifdef CONFIG_SMP #define smp_mb() mb() #else /* !CONFIG_SMP */ #define smp_mb() barrier() #endif ``` 若是 SMP 則使用 `mb`，即 CPU Memory barrier，而非 SMP 時，直接使用 compiler barrier。前面討論 cache coherence 時，提到 MESI 一類的 protocol，我們知道，一個 CPU 要寫入資料前，必須發送 Probe write 去確保其他 CPU 已 invalid 同一位置的 cache，等到其他 CPU 回應 invalidate ack 後，才能寫資料到自己的 cache 中。這個設計確保資料的一致性，不用擔心同一時間同一個位置的資料會有不同的值，但是代價是寫入 cache 的速度較慢，讓 CPU 閒置。 ```mermaid sequenceDiagram rect rgba(0, 0, 0, 0.1) CPU 0->>CPU 1: Invalidate Note over CPU 0: Stall CPU 1->>CPU 0: Acknowledgement end ``` 假設 CPU~0~ 打算寫入資料到位置 `X`，CPU~1~ 的 cache 有 `X` 的內含值。存取延遲 (stall) 的原因如下： * CPU~0~ 要等 CPU~1~ 回應 invalidate ack * CPU~1~ 的 cache 可能太忙而拖慢了回覆時間 (比方同時從 cache 大量的讀寫資料，或是短時間收到大量 invalidate ack)。 ### Store Buffer 針對上述問題，引入 **store buffer** 可縮短 CPU~0~ 的閒置時間： * CPU~0~ 不等 invalidate ack: 先寫入 store buffer，然後繼續作事。之後收到 invalidate ack 再更新 cache 的狀態。因為最新的資料可能存在 store buffer，CPU 讀資料的順序變成 store buffer $\to$ cache $\to$ memory。 * CPU~1~ 立即回覆 invalidate ack: 收到 invalidate 時，記錄到 invalidate queue 裡，先回 invalidate ack，稍後再處理 invalidate。對應的 cache 架構如下： ```graphviz digraph { splines=ortho node [shape=box] subgraph { rank=same node [width=1.5] cpu0 [label=<CPU 0>] cpu1 [label=<CPU 1>] } subgraph { rank=same buf0 [label="Store\nBuffer"] buf1 [label="Store\nBuffer"] } subgraph { rank=same node [width=1] cache0 [label="cache"] cache1 [label="cache"] } subgraph { rank=same node [shape=point width=0] edge [dir=none] inter0->inter1->inter2 [label="Interconnect"] } memory [label=Memory width=1.5] cpu0->buf0->cache0 [weight=2] cpu1->buf1->cache1 [weight=2] cpu0->cache0 [dir=back weight=2] cpu1->cache1 [dir=back weight=2] cache0->inter0 [dir=none] cache1->inter2 [dir=none] inter1->memory [dir=none] } ``` 更新資料時，CPU 會先將更新後的資料置於 store buffer，由於訊號發送是非同步，cache 和 store buffer 內部資料可能不一致，於是需要先讀取 store buffer 裡頭的資料，即 cache with store forwarding。然而，某些問題無法藉由 store buffer forwarding 解決。考慮以下程式碼: (`foobar.c`) ```c int a = 0, b = 0; void foo(void) { a = 1; b = 1; } void bar(void) { while (b == 0) continue; assert(a == 1); } ``` 變數 `a` 和 `b` 起初都是 `0`。假設 CPU~0~ 執行 `foo()`， CPU~1~ 執行 `bar()`，且 cache 的狀態如下: | CPU | `a` | `b` | |:------:|:-------:|:--------:| | CPU~0~ | Shared | Modified | | CPU~1~ | Shared | Invalid | 步驟如下: 1. CPU~0~ 即將執行 `a = 1` 但 CPU~0~ cache 中不存在 `a`，於是寫入 `a` 的值 (`= 1`) 到 store buffer (但 cache 裡仍是 `0`) 2. CPU~0~ 廣播 "invalidate a"，注意這個操作的成本較高，先發送廣播，但 CPU~0~ 不會等待廣播完成，而是繼續執行 3. CPU~1~ 執行 `while (b == 0) continue` 時，CPU~1~ cache 不存在 `b`，因此 CPU~1~ 要發送訊息向 CPU~0~ 取值。 4. CPU~0~ 繼續執行，遇到 `b = 1`，因為 `b` 只在 CPU~0~ cache 中，CPU 直接更新 cache 內容 5. CPU~0~ 收到讀取的訊息，將 `b` 最新內容 (即 `1`) 傳遞給 CPU~1~ 6. CPU~1~ 收到 CPU~0~ 的訊息後，將 `b` 更新為 `1` 7. CPU~1~ 再次執行 `while (b == 0) continue` 時，`b` 為 `1`，於是接著準備執行 `assert(a == 1)` 8. CPU~1~ 準備執行 `assert(a == 1)` 時，`a` 的值仍為 `0` (invalidate 訊息處理較慢)，這會使得 assert 失敗 9. CPU~1~ 收到 CPU~0~ 送來 "invalidate a" 的訊息，但已太遲，前一步驟的 assert 失敗已造成歸納可知，`a = 1` 對 CPU~1~ 來說還不知道，但 CPU~0~ 卻早知道 `b = 1`。問題出在 store buffer 破壞 cache coherence，資料不再是同一時間只有一份值。於是 CPU 需要提供 write memory barrier (簡稱 `wmb`)，讓軟體得以避免這個問題。 write memory barrier 確保之前在 store buffer 裡的資料會先更新到 cache，然後才能寫入 barrier 之後的資料到 cache。假設我們在 foo() 的 `a = 1` 和 `b = 1` 之間插一個 write memory barrier，如 `smp_mb`: ```c void foo(void) { a = 1; smp_mb(); b = 1; } ``` 實作方式如下: 1. write memory barrier 先設定 store buffer 裡的資料為 "marked" (即 `a = 1`) 2. 寫入 `b` 時 (即 `b = 1`)，因發現 store buffer 裡有 marked 的欄位，所以即使 `b` 已處於 Modified，仍需寫入 `b = 1` 到 store buffer，不過狀態是 "unmarked"，所以 `b = 1` 不會寫到 cache 3. CPU~1~ 向 CPU~0~ 要求 `b` 的內含值時，仍是 `0` 4. 直到 CPU~0~ 收到 CPU~1~ 對 `a` 的 invalidate ack 後，cache 中 `a` 的狀態改為 Modified，接著先寫入有 marked 欄位的值到 cache，再寫入 unmarked 欄位的值到 cache。 5. 更新 `a = 1` 到 cacheline 後，才會更新 `b = 1` 到 cacheline 這樣其它 CPU 就會依序看到 `a` 和 `b` 更新的值，也就不會觸發 assert 失敗。 > 延伸閱讀: > * [x86 TSO: A Programmer's Model for x86 Multiprocessors](https://paulcavallaro.com/blog/x86-tso-a-programmers-model-for-x86-multiprocessors/?fbclid=IwAR0RBQKYDp8ThwhO0q66joctJv4QeWgg-Pi987CIjxCa_8VweRg1zvpvC04) ### invalidate queue 由於若要更新特定的 cacheline，就要讓其他 CPU 對應的 cacheline 變成 invalid。收到 invalidate 訊息的 cache 可能來不及處理，又因為 store buffer 很小，store buffer 一旦填滿時，CPU~0~ 還是得等 invalidate ack，所以加上 **invalidate queue**，雙管齊下縮減 CPU~0~ 等待時間。擴展後的 cache 架構如下： ```graphviz digraph { splines=ortho node [shape=box] subgraph { rank=same node [width=2] cpu0 [label=<CPU 0>] cpu1 [label=<CPU 1>] } subgraph { rank=same buf0 [label="Store\nBuffer"] buf1 [label="Store\nBuffer"] p0 [shape=point width=0] p1 [shape=point width=0] } subgraph { rank=same node [width=2] cache0 [label="cache"] cache1 [label="cache"] } subgraph { rank=same node [width=1] queue0 [label="Invalidate\nQueue"] queue1 [label="Invalidate\nQueue"] } subgraph { rank=same node [shape=point width=0] edge [dir=none] inter0->inter1->inter2 [label="Interconnect"] } memory [label=Memory width=2] cpu0->buf0->cache0 [weight=2] cpu1->buf1->cache1 [weight=2] cpu0->p0 [dir=back weight=2] p0->cache0 [dir=none weight=2] buf0->p0 [dir=both minlen=2] cpu1->p1 [dir=back weight=2] p1->cache1 [dir=none weight=2] buf1->p1 [dir=both minlen=2] cache0->queue0 [dir=none] cache1->queue1 [dir=none] queue0->inter0 [dir=none] queue1->inter2 [dir=none] inter1->memory [dir=none] } ``` cache 會將收到的 invalidate 訊息先放置於 invalidate queue，並回報 ACK 的訊息。這樣的設計使得多個 CPU 之間的關係更複雜，由於 invalidate queue導致 Invalidate 訊息的處理會被延遲，所以 CPU 先發出的 `load` 操作可能在讀出之際，已被確認 Invalidate 但在本地 CPU 狀態尚未切換 cache line，導致 CPU 的 load 操作也會是重排。換言之，invalidate queue 會導致新的問題：若 CPU 需要對其他 CPU 發送 Probe Write 前，必須要先檢查 invalidate queue 中有無該 cacheline 的 invalidate 請求，若有，則需要先行處理。若不先處理invalidate queue 中對應的 Invalidate 消息直接對其他 CPU 發送 Probe Write，那麼，這次的寫入操作就會直接被送到 store buffer 中，後續 CPU 再進行處理時，store buffer 有寫該 cacheline 的請求，而 invalidate queue 有讓該 cacheline 狀態改為 `Invlaid` 的請求，那到底該以哪個為準？若都以 store buffer 為準，假如 invalidate queue 中的請求是後於 store buffer 產生的，表示其他 CPU 後續又對該cacheline 進行了寫入，但此時 store buffer 中的舊值會被寫到 cacheline 且標示 `Modified`，這顯然是錯的。反之，以 invalidate queue 為準，那 store buffer 的請求後於 invalidate queue，那一樣也會產生錯誤。回顧稍早提及的 `foobar.c` 程式碼。初始情況假定 a 和 b 都為 0，且 a 同時在 CPU 0 和 CPU 1 的cacheline 中，b 只在 CPU 0 的 cacheline 中。由此，a 對應的 cacheline 狀態為`Shared`，b 對應的 cacheline 狀態為 `Exclusive`，CPU 0 執行 foo()，CPU 1 執行 bar()。 ```c void foo() { a = 1; smp_mb(); b = 1; } void bar() { while(b == 0) continue; assert(a == 1); } ``` 假設程式執行順序如下: 1. CPU~0~ 執行 a = 1，發現 a 在 cache 中但 cacheline 狀態為 `Shared`，便發送 Probe Write 給其他 CPU，同時將 a 的值 1 寫入store buffer 2. CPU~1~ 執行 while loop，發現 b 不在 cache 中(cache miss)，便發送 Probe Read 給其他 CPU 3. CPU~1~ 收到來自 CPU0 的 Probe Write 消息，將這個請求加到 invalidate queue中並立即回應 invalidate ack 給 CPU~0~ 4. CPU~0~ 執行 `smp_mb`，將目前在 store buffer 中的 entry 做標記 5. CPU~0~ 收到 invalidate ack，將 store buffer 中的 a = 1 寫入到 cacheline 中，並將狀態改為 `Modified` 6. CPU~0~ 執行 b = 1，因為 store buffer 為空，沒有任何被標記的 entry，b 也已在 cache 中且狀態是 `Exclusive`，故可以直接將值 1 寫入 cacheline，將cacheline 狀態變更為 `Modified` 7. CPU~1~ 收到變數 b 的資料，並將消息中的 cacheline 放入到自身的 cache 8. CPU~1~ 從 cache 中載入 b 值，發現為 1，結束 while 迴圈 9. CPU~1~ 執行 assert，從 cache 中讀取 a 值，發現為 0，觸發assert 錯誤 10. CPU~1~ 處理 invalidate queue 中的 Probe Write，將 a 所在的 cacheline 設為 `Invalid` 11. CPU~1~ 執行 assert，因為剛剛 a 所在的 cacheline 狀便被改為 `Invalid` 了，等同於 a 不在 cache 中，所以 CPU 1 會發送 Probe Read 從上述執行結果來看，引入 invalidate queue 確實加速 CPU 0 的執行，但即使加上 memory barrier，對 CPU~1~ 來說，CPU~0~ 仍然發生了 I/O reordering。原因在於兩者對於 invalidate cacheline 的理解不一致，CPU 0 認為既然發出了 invalidate acknowledge，你的 cache 中就不會有 a 對應的 cacheline，因為那條 cacheline 被設定為 `Invlaid`，而 CPU~1~ 則認為將 invalidate 消息放入 invalidate queue，已讓 a 的 cacheline 失效。為了讓這二個 CPU 執行程式時達成一致，我們仍然是透過 memory barrier，後者要求該 CPU 必須先處理完在 invalidate queue 中所有的請求，修改後程式碼如下: ```c void foo() { a = 1; smp_mb(); b = 1; } void bar() { while(b == 0) continue; smp_mb(); assert(a == 1); } ``` 加入 memory barrier 後程式執行順序如下: 1. CPU~0~ 執行 a = 1，發現 a 在 cache 中但 cacheline 狀態為 `Shared`，便發送 Probe Write 給其他 CPU，同時將 a 的值 1 寫入store buffer 2. CPU~1~ 執行 while loop，發現 b 不在 cache 中 (即 cache miss)，便發送 Probe Read 給其他 CPU 3. CPU~1~ 收到來自 CPU~0~ 的 Probe Write 消息，將這個請求加到 invalidate queue 中並立即回應 invalidate ack 給 CPU~0~ 4. CPU~0~ 執行 `smp_mb`，將目前在 store buffer 中的 entry 做標記 5. CPU~0~ 收到 invalidate ack，將 store buffer 中的 a = 1 寫入到 cacheline 中，並將狀態改為 `Modified` 6. CPU~0~ 執行 b = 1，因為 store buffer 為空，沒有任何被標記的 entry，b 也已在 cache 中且狀態是 `Exclusive`，故可以直接將值 1 寫入 cacheline，將 cacheline 狀態變更為 `Modified` 7. CPU~1~ 收到變數 b 的資料，並將消息中的 cacheline 放入到自身的 cache 8. CPU~1~ 從 cache 中載入 b 值，發現為 1，結束 while 迴圈 9. CPU~1~ 執行 `smp_mb`，後者要求 CPU~1~ 必須先處理完 invalidate queue 中的請求，於是 Probe Write 的請求是關於 a 的，故將 a 對應的 cacheline 設為 `Invalid` 10. CPU~1~ 執行 assert，從 cache 中讀取 a 值發現是 `Invalid`，於是發出 Probe Read 11. CPU~0~ 處理來自 CPU~1~ 的 Probe Read，將 a 所在的 cacheline 設為 `Shared`，將 a 的資料送給 CPU~1~ 13. CPU~1~ 收到變數 a 的資料，並將消息中的 cacheline 放入到自身的 cache 14. CPU~1 從 cache 中載入 a 值，發現為 1，不再觸發 assert 錯誤從上述執行結果來看，`smp_mb` 再次保證多處理器程式的執行達到預期結果。當然，使用 `smp_mb` 會增加執行成本，因為必須先處理 store buffer 或是 invalidate queue，且以上問題也是在特定的執行順序才會發生。不過，當執行次數夠多時，上述情形必然會發生，而且資料的正確是我們首要議題。為了約束與 store buffer 和 invalidate queue，用到`smp_mb`。也就是說，CPU 執行指令中如果遇到 `smp_mb`，則需要處理 store buffer 和 invalidate queue。但其實從程式碼來看，`foo( )` 中的 `smp_mb` 其實只需要處理 store buffer 的部分，而 `bar( )` 中的則只需要處理 invalidate queue 。有些 CPU 提供更為細分的 `smp_mb`，細分為 `read memory barrier` 和 `write memory barrier`，前者只會處理 invalidate queue，而後者只會處理 store buffer。顯然，只處理其中之一肯定比同時處理二者效率要高，不過約束就會更少，可能的行為也就越多。 ### 硬體實作策略從 sequential consistency (SC) 的角度來說明<什麼順序對 SC 來說是不允許的。sequential consistency 的定義最初是 Leslie Lamport 在 1979 年提出： > ... 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 考慮以下程式碼： ```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] } ``` 從 SC 的角度來說，**the order specified by its program** 這句話的意思就是在說 {**b,d**,a,c} 這種順序是不會發生的。但在並非嚴格 SC 的現代處理器中，**foo == bar == 0** 可能會發生。硬體為了減少讀寫 memory 而有 cache。有 cache 就要確保 cache 之間的資料一致 (同一時間同一位置只有一個值)。但確保 cache 資料完全一致容易讓 CPU 閒置，於是有了 store buffer 和 invalidate queue 降少 CPU 閒置。代價是只保證 CPU 自己會讀到自己寫入的最新資料，但其它 CPU 不一定。為了讓其它 CPU 有需要的時候也能讀到最新的資料，針對 store buffer 和 invalidate queue 的副作用設計了 write/read memory barrier。於是寫軟體的人在需要的時候可以用 memory barrier 確保關鍵的資料有依正確的順序更新 (無法保證更新的時間)。CPU 在多數情況下仍能避免閒置。到此可理解為何這二種操作搭配，較符合現代處理器架構： * 一個執行緒「先 write X，後執行 write memory barrier」 * 另一個執行緒「先執行 read memory barrier，後 read X」二者合起來構成 happens-before 關係。由此可理解 sequential consistency (SC) 和多核硬體的運作方式差太多，會太常讓多個 CPU 閒置，無法發揮多 CPU 的效能。因此程式開發者應儘量避免依賴 SC。 > 延伸閱讀: [並行程式設計: 執行順序](https://hackmd.io/@sysprog/concurrency-ordering) 硬體設計者引入 read memory barrier 和 write memory barrier，其中 read memory barrier 只對 invalidate queue 有效，write memory barrier 只對 store buffer 有效。延伸閱讀: * [Memory Barriers: a Hardware View for Software Hackers](http://www.rdrop.com/users/paulmck/scalability/paper/whymb.2010.07.23a.pdf) 參考 [I/O ordering 學習紀錄](https://hackmd.io/@butastur/rkkQEGjUN#Store-Buffer) 中的實驗，我們利用 [litmus7](http://diy.inria.fr/doc/litmus.html) 在硬體架構為 `arm64` 得機器上進進行實驗，實驗程式碼如下： (`arm000.litmus`) ``` ARM arm000 "PodWW Rfe PodRR Fre" Cycle=Rfe PodRR Fre PodWW Relax= Safe=Rfe Fre PodWW PodRR Generator=diy7 (version 7.56.2) 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 | MOV R1,#1 ; STR R0,[%x0] | STR R1,[%y1] ; LDR R0,[%y0] | LDR R1,[%x1] ; exists (0:R0=0 /\ 1:R1=0) ``` 上方程式碼是 [litmus7](http://diy.inria.fr/doc/litmus.html) 的語法，首先宣告兩個共享變數 x, y，且初始化為 0，接著，CPU~0~ 所做的事情是寫入 a = 1 和讀取 b，而 CPU~1~ 所做的事情是寫入 b = 1 和讀取 a，二個 CPU 都是做一個 store 指令接著一個 load 指令，我們藉由本實驗，想觀察是否出現「CPU~0~ 讀到的 b 是 0，而 CPU~1~ 讀到的 a 也是 0」的情況。利用 [litmus7](http://diy.inria.fr/doc/litmus.html) 執行上面提供的測試程式，並重複執行 1000000 次，結果如下: ``` Test arm000 Allowed Histogram (3 states) 15 *>0:R0=0; 1:R1=0; 499994:>0:R0=1; 1:R1=0; 499991:>0:R0=0; 1:R1=1; Ok Witnesses Positive: 15, Negative: 999985 Condition exists (0:R0=0 /\ 1:R1=0) is validated ... Time arm000 0.38 ... ``` 根據上訴實驗結果，可發現出現 15 次 CPU~0~ 讀到的 b 是 0，而 CPU~1~ 讀到的 a 也是 0 的情況，代表其中一個或兩個 CPU 發生 memory reordering 的情況，否則正常執行下至少會有一個 CPU 讀到的值為 1。為了測試 memory barrier 是否有效，我們在 store 指令與 load 指令之間加上 arm64 架構提供的 memory barrier 指令 `DMB`。摘錄 [ARM Compiler toolchain Assembler Reference Version 4.1](https://developer.arm.com/documentation/dui0489/c/arm-and-thumb-instructions/miscellaneous-instructions/dmb--dsb--and-isb)： > Data Memory Barrier acts as a memory barrier. It ensures that all explicit memory accesses that appear in program order before the DMB instruction are observed before any explicit memory accesses that appear in program order after the DMB instruction. It does not affect the ordering of any other instructions executing on the processor. 也就是說 DMB 指令的作用是，保證在 DMB 之後記憶體存取相關的指令都「看到」DMB 之前記憶體存取相關的指令的結果。加入 DMB 指令: ```diff P0 | P1 ; MOV R0,#1 | MOV R1,#1 ; STR R0,[%x0] | STR R1,[%y1] ; + DMB | DMB ; LDR R0,[%y0] | LDR R1,[%x1] ; exists (0:R0=0 /\ 1:R1=0) ``` 利用 [litmus7](http://diy.inria.fr/doc/litmus.html) 執行上面提供的測試程式，並重複執行 1000000 次，結果如下: ``` Test arm000 Allowed Histogram (3 states) 499998:>0:R0=1; 1:R1=0; 500000:>0:R0=0; 1:R1=1; 2 :>0:R0=1; 1:R1=1; No Witnesses Positive: 0, Negative: 1000000 Condition exists (0:R0=0 /\ 1:R1=0) is NOT validated ... Time arm000 0.46 ... ``` 透過實驗結果可發現加入 memory barrier 之後，不再出現 CPU~0~ 讀到的 b 是 0，而 CPU~1~ 讀到的 a 也是 0 的情況。另外，也可發現，加入 memory barrier 之後的執行時間較長。由實驗證實，雖然加入 memory barrier 確實會影響效能，但為了保證資料的正確性，這是必要的犧牲。 ### 軟體觀點現代編譯器進行最佳化時，會引入多種策略。考慮到以下程式碼: ```c int x, y; void foo() { x = y + 1; y = 0; } ``` 我們藉由 gcc 來編譯並比較有無最佳化的組合語言 (以 Arm64 為探討標的)。 - [ ] 抑制最佳化 ```shell $ gcc -S foo.c $ cat foo.s ... foo: .LFB0: .cfi_startproc adrp x0, :got:y ldr x0, [x0, #:got_lo12:y] // load y to x0 ldr w0, [x0] // load y to w0 add w1, w0, 1 // add w0 with 1 to w1 adrp x0, :got:x ldr x0, [x0, #:got_lo12:x] // load x to x0 str w1, [x0] // store w1 to x adrp x0, :got:y ldr x0, [x0, #:got_lo12:y] // load y to x0 str wzr, [x0] // store 0 to y nop ret ... ``` - [ ] 啟用 `-O2` 最佳化等級 ```shell $ gcc -S -O2 foo.c -o foo1.s $ cat foo1.s ... foo: .LFB0: .cfi_startproc adrp x0, :got:y adrp x1, :got:x ldr x0, [x0, #:got_lo12:y] // load y to x0 ldr x1, [x1, #:got_lo12:x] // load x to x1 ldr w2, [x0] // load y to w2 str wzr, [x0] // store 0 to x add w0, w2, 1 // add w2 with 1 to w0 str w0, [x1] // store w0 to x ret ... ``` 觀察以上 Arm64 組合語言可知，在沒有最佳化下，程式會先做完 `x = y + 1` 的 store 指令接著再完成 `y = 0` 的 store 指令，但在利用 `O2` 最佳化的情況下，程式先做 `y = 0` 的 store 指令，再做`x = y + 1` 的 store 指令，因為程式把 y 的值先存在暫存器 `w2` 中，後續的計算直接從暫存器 `w2` 取值，這樣的指令重排不影響單一執行緒的資料正確性。然而，在並行多執行緒程式中將可能導致資料的不正確，試想，如果程式中的 y 作用如果是 lock，在設成 0 之後其他執行緒才能進入 critical section 中更改 x 的資料，但在指令重排之後，某一執行緒把 y 先被設成 0，才改動 x 的資料，而另一執行緒看到 y 變成了 0，也馬上進到 critical section 中去改 x 的資料，同時讓兩個執行緒進入 critical section 修改同一份資料顯然違反了程式的正確性。如果我們想要讓程式運作符合預期，就要有辦法明確告知編譯器，特定的讀寫操作都要確實地去記憶體位置上讀寫，不能用臨時結果，例如用 `-O2` 最佳化後的測試程式用存在暫存器 `w2` 中的結果。讀到這裡，你是否覺得處理器和編譯器的設計者為了提升速度，真是[無所不用其極](https://dict.idioms.moe.edu.tw/idiomView.jsp?ID=7567&webMd=2)，這樣軟體開發如何安心地撰寫程式呢？慶幸的是，處理器和編譯器的設計者除了做出這些激進的速度提升方案，也給留下後路，讓我們能夠在需要時，運用這些機制來抑制對處理器和編譯器施加的激進手段，從而確保程式的正確。 ![](https://hackmd.io/_uploads/Bk3hS37-h.png) > [圖片出處](https://www.ig.supply/start-barrier) 對於編譯器來說，compiler barrier 有如前述程式 `cacheline.c` 第 29 行的 `asm volatile("" ::: "memory");`，其作用是告訴編譯器，不管進行何種最佳化手段，程式的讀寫操作影響不該跨越這個「屏障」，更白話來說是，要求編譯器不要自作聰明，在 `asm volatile("" ::: "memory");` 出現後的讀寫都確實地去記憶體位置上讀寫，不能偷懶用「屏障」之前的臨時結果。另一個由 Linus Torvalds 提出的 compiler barrier 的[例子](https://yarchive.net/comp/linux/memory_barriers.html)，考慮以下程式碼: ```c local_cpu_lock = 1; // .. do something critical .. local_cpu_lock = 0; ``` 對於編譯器來說，一旦發現 `local_cpu_lock` 跟 `.. do something critical ..` 裡頭的程式沒有任何的相關性。在沒有 `barrier()` 的情況下，`local_cpu_lock` 可能被編譯器重排，甚至 `local_cpu_lock = 1` 這行程式碼可能會在編譯器最佳化時被移除，畢竟 `local_cpu_lock = 1` 後再設定為 `local_cpu_lock = 0`，第一個動作可能被認定是無效操作 (NOP)。為了確保程式邏輯的正確性，就該加入 `barrier()` 來抑制編譯器最佳化。 Linux 核心針對 compiler barrier 的巨集是 `barrier()`，對應 gcc 的定義如下: (詳見 [include/linux/compiler-gcc.h](https://github.com/torvalds/linux/blob/master/include/linux/compiler-gcc.h): ```c /* The "volatile" is due to gcc bugs */ #define barrier() __asm__ __volatile__("": : :"memory") ``` 你或許好奇，空的指令要怎麼發揮作用？ `barrier` 巨集利用 [inline assembly](https://gcc.gnu.org/onlinedocs/gcc/Extended-Asm.html) 的 [clobber list 裡的 `"memory"`](https://gcc.gnu.org/onlinedocs/gcc/Extended-Asm.html)，clobber list 是 gcc 和 gas (GNU Assembler) 的介面，用於 gas 通知 gcc 對暫存器和記憶體的修改情況。此處 `"memory"` 就是告知 gcc，在組合語言中，實際修改記憶體中的內容，之前和其後的 C 程式碼所見的記憶體內容不同，對記憶體的存取不能依賴此前暫存器的內容，編譯器應當自記憶體讀取資料。要注意的事情是，compiler barrier 無法避免 CPU 在執行指令時，對指令進行重排。如果要避免 CPU 在執行期間對於指令進行重排，需要利用 memory barrier 來達成（詳見下文中 Dekker's algorithm 的實作）。 CPU 針對可能出現的重排，一般可分類為 3 種 memory barrier: * 儲存屏障 (store barrier/fence)：維持 barrier 前後的 `store` 操作的順序，即 barrier 後的 `store` 一定發生在 barrier 前的 `store` 之後。 * 呼應前述處理器設計，store barrier 的作用在於在 Store Buffer * 實作既可等待 Store Buffer 清空，亦可在 Store Buffer 中寫入一個標記，並禁止後續的 `store` 指令直接寫入 cache，轉而寫入 Store Buffer 中，直到 Store Buffer 中沒有標記，才恢復正常 * 讀取屏障 (load barrier/fence): 維持 barrier 前後的 load 操作的順序，即 barrier 後的 `load` 一定發生在 barrier 前的 `load` 之後。 * 呼應前述處理器機制，load barrier 的作用在於 Invalidate Queue * load barrier 會強制等待 Invalidate Queue 清空才繼續執行，這樣可消除其引發的讀取重排問題 * 全屏障 (full barrier/fence): 作用相當於前二者之和 ==Full Fence== : std::atomic_thread_fence()，可防止任二種操作的 reordering，除了 **StoreLoad** 以外。 ![Full Fence]![](https://hackmd.io/_uploads/rJBEglQ-3.png) ==Acquire Fence== : atomic_thread_fence(std::memory_order_acquire)，可防止 Load 被排到 barrier 後面。或是 barrier 後面的read(load) / write(store) 不可重排到 barrier 前面的 load。 ![](https://hackmd.io/_uploads/B1MBggQ-3.png) ==Release Fence== : atomic_thread_fence(std::memory_order_release)，可防止後面的 Store 被排到前面。或是 barrier 前面的 read(load) / write(store) 不可重排到 barrier 後面的 store。 ![](https://hackmd.io/_uploads/B1IGVChX2.png) 於是: + acquire fence = LoadLoad + LoadStore barrier + release fence = LoadStore + StoreStore barrier. 歸納可得到以下關係圖。 ![](https://hackmd.io/_uploads/SkJdlgmW3.png) Arm 架構中，針對 memory barrier 提供 `DMB`, `DSB`, `ISB` 等指令。以 Inner Shareable (IS) 為例，使用 `DSB` 指令加上 `ISH`，可防止所有 `load` 指令和 `store` 指令的 reorder (即 full memory reorder)。若只想抑制 `L-L` 和 `L-S` 之間的 reorder (即 read memory barrier)，應用`ISHLD`。若只想抑制 `S-S` 之間的重排 (write memory barrier)，則該用 `ISHST`。Arm 用 `ISHLD` + `ISHST` 的效果，等同於 x86 預設 memory order。 | 指令 | 場景 | 特徵 | |:---:|-----|------| | `ISHLD` | Load-Load, Load-Store | Inner Shareable | | `ISHST` | Store-Store | - | | `ISH` | Any-Any | - | > $\uparrow$ Arm: memory barrier 指令 x86 中用於設定 "full memory barrier" 的指令是 `fence`，依據 x86 預設的 memory order，只在防止 `S-L` 這種情況的 reorder 才要特別處理，但前面提過，x86 的 memory order 強度可調整，因此仍有針對 write memory barrier 的 `sfence` 指令和設定 read memory barrier 的 `lfence` 指令。關於 memory barrier，我們要留意以下: * memory barrier 不提供時間保證 * store barrier/fence 指令執行結束並不代表 Store Buffer 已清空並寫入 cache 中 (所謂的「全區域可見」)，memory barrier 只提供 barrier 前後指令的順序保證 * memory barrier 沒有辦法對其他 CPU 產生影響 * 在某個 CPU 執行的 memory barrier 指令，無法對其他 CPU 的 cache 和執行產生直接影響，只會改變其他 CPU 看到的本 CPU 的記憶體存取順序 * memory barrier 需要成對使用 * 即使藉由 store barrier/fence 維持 barrier 前後的 store 操作順序，由於 Invaliate Queue 的影響，其他 CPU 可能仍無法看到正確的順序，因此在程式碼中，store barrier/fence 仍要和 load barrier/fence 成對使用我們考慮一個程式場景：若其中首個變數扮演開關的作用，控制對後續變數的存取，那麼當這些變數被一起 cohere 到其他處理器時，更新順序可能變，第一個變數未必是第一個更新的，然而其他執行緒還認為它代表著其他變數有效，去存取實際已被刪除的變數，從而導致未定義的行為。程式碼列表如下: ```c struct object *p; /* Thread 1 */ { /* ready was initialized to false */ p = init(); ready = true; ... } /* Thread2 */ { if (ready) { p->bar(); } } ``` 乍看之下，這似乎沒錯，因為 Thread~2~ 在 `ready` 為 true 時，才會存取 `p`，按 Thread~1~ 的邏輯，此時 `p` 應完成初始化。但對多核處理器來說，上述程式碼執行結果可能無法符合我們的預期: - Thread~1~ 中的 `ready = true` 可能會被編譯器或處理器 reorder 到 `p = init()` 之前，從而使 Thread~2~ 看到 `ready` 為 true 時，`p` 尚未初始化。這種情況同樣也會在 Thread~2~ 中發生，`p->bar()` 裡頭部分程式碼可能被 reorder 到檢查 `ready` 之前。 - 即使不存在 reorder，`ready` 和 `p` 的值也會獨立地 cohere 到 Thread~2~ 所在處理器的 cache，Thread~2~ 仍然可能在看到 `ready` 為 true 時，看到未初始化的 `p` 注：x86 和 x64 的 load 具備 acquire 語意，store 具備 release 語意，上面的程式碼扣除編譯器因素，可符合預期地執行。 CPU 和編譯器提供 [memory barrier](http://en.wikipedia.org/wiki/Memory_barrier)，讓開發者得以指定指令間的 visibility 關係: | memory order | 作用 | |:------------:|:---------------------:| | memory_order_relaxed | 沒有 memory barrier，允許編譯器和處理器充分發揮。若目前操作為 atomic，則只保證該 atomic 操作的順序 | | memory_order_consume | 後面依賴此 atomic 變數的存取指令，不得重排至此條指令之前 | | memory_order_acquire | 後面存取指令不得重排至此條指令之前 | | memory_order_release | 前面存取指令不得重排至此條指令之後。當此條指令的結果對其他執行緒可見後，之前的所有指令都可見 | | memory_order_acq_rel | acquire + release 語意 | | memory_order_seq_cst | acq_rel 語意外加所有使用 seq_cst 的指令有嚴格地順序，若沒指定 memory order，則預設採用 | 以上 6 種 memory order 的 weak 及 strong 關係，如下圖: ![](https://hackmd.io/_uploads/HkMCrhQb2.png) `memory_order_acquire` (用於記憶體資料「讀取」，即 `load`) 與 `memory_order_release` (用於記憶體資料「寫入」，即 `store`) 成對使用時，建立 Release-Acquire ordering，其效果是抑制指令重排: * 在 load 之後的讀寫將被禁止重排到此操作之前 * 在 store 之前的讀寫將被禁止重排此操作之後主要效果是，確保在 Thread~A~ 的 `store` 之前對記憶體的操作，對 Thread~B~ 的 `load` 是可見的 (visible)。 ![](https://i.imgur.com/qqt9CPz.png) 上圖展示 acquire 和 release 語意，可發現沒有用到 store-load barrier，而 x86 剛好只有 store load 重排，因此 x86 架構確保 Lock Acquire 和 Unlock Release。但對於 Aarch64 之類的處理器架構，又有不同的表現。 `memory_order_consume` (用於記憶體資料「讀取」，即 `load`) 與 `memory_order_release` 成對使用時，建立 Release-Consume ordering，後者相較於 Release-Acquire ordering 的限制更弱，因此允許編譯器和處理器做更多調整。在 `load` 之後與操作變數有相依性的其他讀寫將被限制重排，反之，沒有相依性的操作則不在此限。有了 memory order，上面的例子可更正如下: ```c /* Thread1 */ { /* ready was initialized to false */ p = init(); atomic_store_explicit(&ready, true, memory_order_release); } /* Thread2 */ { if (atomic_load_explicit(&ready, memory_order_acquire)) { p->bar(); } } ``` Thread~2~ 中的 ==acquire== 和 Thread~1~ 的 ==release== 配對，確保 Thread~2~ 在看到 `ready == true` 時，能看到 Thread~1~ 的 release 之前，所有的存取操作。注意，memory barrier 不等於「立即可見」，即使 Thread~2~ 恰好在 Thread~1~ 處於將 `ready` 設定為 true 後，讀取 `ready` 也不意味著它能看到 true，因為 cache coherence 會有時間差！memory barrier 保證的是可見性的==順序==：「假如我看到 `a` 的最新值，那我一定也得看到 `b` 的最新值」。這又帶出另一個問題：如何得知數值是新或舊？一般分兩種情況： - 值是特殊的。在例子，`ready = true` 是個特殊值，只要 Thread~2~ 看到 `ready` 為 true 就意味著更新。只要設定特殊值，讀到或沒有讀到特殊值都代表一種意義。 - 總是累加。一些場景下沒有特殊值，那我們就用 `atomic_fetch_add `之類的 atomic 操作累加一個變數，只要變數的值域足夠大，在很長一段時間內，新值和之前所有的舊值都會不相同，我們就能區分彼此。 C11 標準 (5.1.2.4 和 7.17.4 章節) 描述 fence-to-fence 和 fence-to-atomic 同步 (即 "synchronizes with" 語意)，若只用 memory fence/barrier 不足以同步 non-atomic 或 relaxed atomic load/store 操作，因為這些必須要有成對的 atomic 操作 (規格書原文: "... if there exist atomic operations ..." and ".. is sequenced before ..")。 C11 刻意不將 acquire/release fences 定義為 "acquire/release operations"，相反地，C11 定義 "acquire/release semantics" —— 看似只是文字遊戲，但實際行為大異其趣。在 C11 規範中，memory fence 必須搭配 `atomic_{load,store}_*()` 使用，即便 load/store 已是 `memory_order_relaxed`。接下來思考二個範例，都是共用記憶體的存取。 ![](https://hackmd.io/_uploads/BJEkU37W2.png) > 經典的 publisher (訊息發布者) 和 subsriber (訊息訂閱者) 模式 ```c /* Thread A */ *val = 1; atomic_thread_fence(memory_order_release); atomic_store_explicit(published, 1, memory_order_relaxed); /* Thread B */ if (atomic_load_explicit(published, memory_order_relaxed) == 1) { atomic_thread_fence(memory_order_acquire); assert(*val == 1); /* 不會失敗 */ } ``` 但若改寫為以下: ```c /* Thread A */ *val = 1; atomic_thread_fence(memory_order_release); *published = 1; /* Thread B */ if (*published == 1) { atomic_thread_fence(memory_order_acquire); assert(*val == 1); /* 可能會失敗 */ } ``` 裡頭的 `assert` 可能會失敗，正因 memory fence 沒有搭配正確的 `atomic_store`。延伸閱讀: * [Memory fences, atomics and C11 memory model](https://github.com/rmind/stdc/blob/master/c11memfences.md) ### 易於誤用 `volatile` 關鍵字使用 C 或 C++ 程式語言的開發者應該對 `volatile` 關鍵字不陌生，但後者在多執行緒的環境中很容易被誤用。我們先回顧 `volatile` 的作用：在變數宣告前加上該關鍵字，表示這個變數「可能被意外地修改」，並要求編譯器每次使用該變數時，都要從記憶體地址中讀出最新內容。換言之，`volatile` 的使用意味著抑制編譯器最佳化，不少人忽略到一個事實：程式中對 `volatile` 的使用，有時無法達到預期效果。這是因為僅保證編譯器不進行最佳化，不能保證 CPU 不會遭遇重排，若讀取操作被提前，即使抑制最佳化，也可能讀出意料之外的資料。以下是 [Dekker's Algorithm](https://en.wikipedia.org/wiki/Dekker%27s_algorithm) 的實作程式碼: (檔名: `dekker.c`) ```c= #include <pthread.h> #include <stdio.h> #include <stdlib.h> static volatile int flag1 = 0, flag2 = 0, turn = 1; static volatile int counter = 0; int loop_cnt; static void dekker1(void) { flag1 = 1; turn = 2; // __atomic_thread_fence(__ATOMIC_SEQ_CST); while ((flag2 == 1) && (turn == 2)) ; /* critical section */ counter++; /* let the other task run */ flag1 = 0; } static void dekker2(void) { flag2 = 1; turn = 1; // __atomic_thread_fence(__ATOMIC_SEQ_CST); while ((flag1 == 1) && (turn == 1)) ; /* critical section */ counter++; /* leave critical section */ flag2 = 0; } static void *task1(void *arg) { printf("Starting %s\n", __func__); for (int i = loop_cnt; i > 0; i--) dekker1(); return NULL; } static void *task2(void *arg) { printf("Starting %s\n", __func__); for (int i = loop_cnt; i > 0; i--) dekker2(); return NULL; } int main(int argc, char **argv) { pthread_t thread1, thread2; if (argc != 2) { fprintf(stderr, "Usage: %s <loopcount>\n", argv[0]); exit(1); } loop_cnt = atoi(argv[1]); /* FIXME: format checks */ int expected_sum = 2 * loop_cnt; (void) pthread_create(&thread1, NULL, task1, NULL); (void) pthread_create(&thread2, NULL, task2, NULL); void *ret; (void) pthread_join(thread1, &ret); (void) pthread_join(thread2, &ret); printf("Both threads terminated\n"); /* Check result */ if (counter != expected_sum) { printf("[-] Dekker did not work, sum %d rather than %d.\n", counter, expected_sum); printf("%d missed updates due to memory consistency races.\n", (expected_sum - counter)); return 1; } printf("[+] Dekker worked.\n"); return 0; } ``` 這個程式碼中，我們可見變數 `flag1`, `flag2` 和 `turn` 皆已宣告為 `volatile`，倘若就此認為執行緒總能讀到這 3 個變數的「最新數值」，既然 [Dekker's Algorithm](https://en.wikipedia.org/wiki/Dekker%27s_algorithm) 已被證明理論是正確的，那麼程式執行結果如何？一樣在 AMD Ryzen Threadripper 2990WX 32-Core Processor 實驗: ```shell $ ./dekker 10000000 Starting task1 Starting task2 Both threads terminated [-] Dekker did not work, sum 19164869 rather than 20000000. 835131 missed updates due to memory consistency races. ``` 顯然結果不正確，問題在於 `volatile` 不能保證能夠讀到「最新」的資料，它只保證編譯器每次都產生 `load` 操作，而 CPU 在執行過程中重排，使得該 `load` 操作讀到「舊值」，從而導致混亂。倘若我們修改上述程式碼的第 13 和第 26 行，使得 `__atomic_thread_fence(__ATOMIC_SEQ_CST);` 作為 memory barrier 得以執行，才會得到符合預期的 [Dekker's Algorithm](https://en.wikipedia.org/wiki/Dekker%27s_algorithm) 的實作。上例說明單獨使用 `volatile` 關鍵字，很有可能無法得到預期結果。因此，當我們要使用 `volatile` 時，一定要想楚究竟「為什麼要用」？是否需要使用 memory barrier？是否對編譯器最佳化產生無謂的抑制？ Linux 核心文件〈[Why the "volatile" type class should not be used](https://www.kernel.org/doc/Documentation/process/volatile-considered-harmful.rst)〉提到，在 Linux 核心使用 `volatile` 的場景，絕大部分是誤用。在 [Linux Kernel Memory Barriers](https://www.kernel.org/doc/Documentation/memory-barriers.txt) 提到巨集 `READ_ONCE` 和 `WRITE_ONCE`，定義於 `include/asm-generic/rwonce.h`: ```c /* * Use __READ_ONCE() instead of READ_ONCE() if you do not require any * atomicity. Note that this may result in tears! */ #ifndef __READ_ONCE #define __READ_ONCE(x) (*(const volatile __unqual_scalar_typeof(x) *)&(x)) #endif #define READ_ONCE(x) \ ({ \ compiletime_assert_rwonce_type(x); \ __READ_ONCE(x); \ }) ``` 我們撰寫簡單的 C 程式來試驗: (檔名: `t.c`) ```c= int a, b; int i, j; void foo() { a = i; b = j / 16; } ``` 在開啟編譯器最佳化的狀態，進行編譯: ```shell $ gcc -S -O2 t.c ``` 對應的組合語言輸出: ``` movl j(%rip), %edx ; 讀取 j movl i(%rip), %eax ; 讀取 i testl %edx, %edx movl %eax, a(%rip) leal 15(%rdx), %eax cmovns %edx, %eax sarl $4, %eax movl %eax, b(%rip) ``` 在 C 程式中，第 6 行先是讀取變數 `i`，再來是第 7 行讀取變數 `j` 的值，卻跟組合語言輸出不同，換言之，這就是編譯器最佳化的效果。我們在第 6 行之後新增一行: (即前述的 compiler barrier) ```c=7 __asm__ __volatile__("": : :"memory"); ``` 產生的組合語言就變更: ``` movl i(%rip), %eax ; 先讀取 i movl %eax, a(%rip) ; i 的內容指派到變數 a 中 movl j(%rip), %edx ; 再來才讀取 j testl %edx, %edx ... ``` 也就是說，compiler barrier 告訴編譯器：在 barrier() 前後必須明確區隔：barrier 之前的操作不可跑到 barrier 後，反之亦然。所以，「讀取 `i` 並寫入 `a`」和「讀取 `j` 並寫入 `b`」這兩組操作被 barrier 所隔離。接下來引入 Linux 核心的 `READ_ONCE` 巨集，使用到 `volatile` 關鍵字，繼續實驗: ```c #define __READ_ONCE(x) (*(const volatile int *) &(x)) int a, b; int i, j; void foo() { a = __READ_ONCE(i); b = __READ_ONCE(j) / 16; } ``` 產生的組合語言如下: ``` movl i(%rip), %eax ; 讀取 i movl j(%rip), %edx ; 讀取 j movl %eax, a(%rip) ; 寫入 a testl %edx, %edx leal 15(%rdx), %eax cmovns %edx, %eax sarl $4, %eax movl %eax, b(%rip) ; 寫入 b ``` 可見 `i` 和 `j` 的讀取順序被保證，但 `volatile` 畢竟不是 compiler barrier ，不能把 `a = i` 和 `b = j / 16` 完全隔離，因此用 `__READ_ONCE` 能保證的也只是 `i` 和 `j` 的讀取順序，其他的寫入順序或者讀寫之間的順序，就無法保證，以上例來說，讀取 `j` 和寫入 `a`，就不同於 C 程式原本的順序。摘錄 C 語言規格: > The least requirements on a conforming implementation are: > At sequence points, volatile objects are stable in the sense that previous accesses are complete and subsequent accesses have not yet occurred. > > The following are the sequence points described in 5.1.2.3: > > The end of a full expression: an initializer (6.7.8); the expression in an expression statement (6.8.3); the controlling expression of a selection statement (if or switch) (6.8.4); the controlling expression of a while or do statement (6.8.5); each of the expressions of a for statement (6.8.5.3); the expression in a return statement (6.8.6.4). 這裡引出 sequence point 的概念：sequence point 之前的表達式所造成的影響，不能擴散到 sequence point 之後。尤其是對於 `volatile` 變數來說，以一個 sequence point 為分界點，對於前面 `volatile` 變數的存取必須完成，且對於後面 `volatile` 變數的存取必須尚未開始。依循上述 C 語言規範，常見的 `;` (分號) 就是個 sequence point，於是 `a = __READ_ONCE(i)` 和 `b = __READ_ONCE(j) / 16` 之間隔著一個 sequence point，因此對變數 `i` 的讀取必須放在變數 `j` 之前。但要注意的是，編譯器只是保證 2 個 `volatile` 變數之間讀取不會被亂序，但是 non-`volatile` 變數和 volatile 變數的讀取順序，依舊允許亂序。讀者可試著將上述程式碼裡頭第二個 `__READ_ONCE` 巨集移除，就會發現 `i` 和 `j` 的讀取順序又顛倒。 ## 處理器架構和其 Memory Order 即使有用來抑制編譯器最佳化的工具，你是否仍然感覺難以寫出正確的程式碼呢？可能發生指令重排的情況如此多，似乎在任何時候都要考慮 memory barrier 的使用，實在困難。誠然，針對多核處理器的並行程式設計就是如此複雜，但前提是你打算撰寫跨越多種處理器架構的可攜性 (portable) 程式碼。不同處理器架構的順序保證往往不同的，x86 架構實際上已提供很強的順序性保證，如下圖： ![](https://hackmd.io/_uploads/HyYg82QZh.png) 可見 x86 架構結構中只會發生一種重排 (先不討論最右邊欄位，是探討指令 cache 的一致性)，即 store-load 重排。考慮下圖的案例，在 2 個 CPU 並行的程式碼: ![](https://hackmd.io/_uploads/B1kMIn7-3.png) 上圖中，2 個執行緒都是先執行 `store` 操作 (變數 `x` 和 `y` 的初始值都是 `0`)，再執行 `load` 操作，於是我們可確認執行完畢後，`r1` 和 `r2` 的值至少有一個是 `1`。然而在 x86 結構中，由於會出現 store-load 重排，所以 2 個執行緒的 store-load 執行順序可能產生變化，如下圖： ![](https://hackmd.io/_uploads/rkKGI2Qbh.png) 由於重排，可能會產生 `r1` 和 `r2` 都為 `0` 的執行結果 —— 這和原本的程式邏輯牴觸。以下我們撰寫程式來觀察處理器重排的狀況: (檔名: `reorder.c`) ```c #include <pthread.h> #include <stdio.h> #include <stdlib.h> static int loop_count; static int A, B, X, Y; static void *worker1(void *arg) { X = 1; asm volatile("" ::: "memory"); A = Y; } static void *worker2(void *arg) { Y = 1; asm volatile("" ::: "memory"); B = X; } int main(int argc, char *argv[]) { pthread_t thread_1, thread_2; int64_t count = 0; if (argc != 2) { fprintf(stderr, "USAGE: %s <loop_count>\n", argv[0]); exit(1); } loop_count = atoi(argv[1]); /* FIXME: format checks */ for (int i = 0; i < loop_count; ++i) { X = 0; Y = 0; /* Start the threads */ pthread_create(&thread_1, NULL, (void *(*) (void *) ) worker1, NULL); pthread_create(&thread_2, NULL, (void *(*) (void *) ) worker2, NULL); /* Wait for the threads to end */ pthread_join(thread_1, NULL); pthread_join(thread_2, NULL); if (A == 0 && B == 0) /* reorder caught */ count++; } printf("%d reorder caught in %d iterations.\n", count, loop_count); return 0; } ``` 在 AMD Ryzen Threadripper 2990WX 32-Core Processor 實驗: (Ubuntu Linux 20.04) ```shell $ ./reorder 100000 34 reorder caught in 100000 iterations. ``` 10 萬次迴圈中，Threadripper 2990WX 重排發生 `34` 次。在 Intel(R) Xeon(R) CPU E5-2650 實驗: (Ubuntu Linux 20.04) ```shell $ ./reorder 100000 267 reorder caught in 100000 iterations. ``` 10 萬次迴圈中，Xenon E5-2650 重排發生 `267` 次。在 [AWS Graviton 處理器](https://aws.amazon.com/ec2/graviton/) (Aarch64 架構) 實驗: (Ubuntu Linux 20.04) ```shell $ ./reorder 100000 1114 reorder caught in 100000 iterations. ``` 10 萬次迴圈中，Graviton2 重排發生 `1114` 次。在 Intel Core i5 + macOS 測試: ```shell $ ./reorder 100000 0 reorder caught in 100000 iterations. ``` 在 Apple M1 晶片 + macOS 測試: ```shell $ ./reorder 100000 2 reorder caught in 100000 iterations. ``` macOS 的結果很有趣，其 POSIX Thread 實作中，主動安插 memory barrier。延伸閱讀: * [C++ Memory Model: Migrating From X86 to ARM](https://dzone.com/articles/c-memory-model-migrating-from-x86-to-arm) * [Current sorry state of C11 code and suggestions to fix it](https://www.dpdk.org/wp-content/uploads/sites/35/2019/10/StateofC11Code.pdf) ## wait-free & lock-free ![](https://hackmd.io/_uploads/SkoX8nXWn.png) > [Non-blocking algorithm](https://en.wikipedia.org/wiki/Non-blocking_algorithm): wait-free 是 lock-free 之中具備更嚴格的條件 atomic 指令可作為 [wait-free](http://en.wikipedia.org/wiki/Nonblocking_algorithm#Wait-freedom) 和 [lock-free](https://en.wikipedia.org/wiki/Non-blocking_algorithm#Lock-freedom) 演算法的基礎建設。[wait-free](http://en.wikipedia.org/wiki/Non-blocking_algorithm#Wait-freedom) 指無論作業系統如何排程，**每個** 執行緒始終有進展；[lock-free](https://en.wikipedia.org/wiki/Non-blocking_algorithm#Lock-freedom) 的規範則較前者弱，指無論作業系統如何排程，**至少有一個** 執行緒有進展。若在我們的服務中使用 lock，那麼作業系統可能將一個剛獲取 lock 的執行緒切換出去，這時所有依賴這個 lock 的執行緒都在等待，因而沒進展，因此依賴 lock 的操作難以達到 lock-free ，更不會是 wait-free。 [Non-blocking algorithm](https://en.wikipedia.org/wiki/Non-blocking_algorithm) 尚有 obstruction-free 方案。英語 "obstruction" 有「阻礙」和「阻擋」的意涵，obstruction-free 指在任何時間點，一個孤立執行執行緒的每個操作可在有限步之內結束。只要沒有競爭，執行緒就可持續執行。一旦共用資料被修改，obstruction-free 要求中止已完成的部分操作，並進行回復 (rollback)。所有 Lock-Free 演算法都滿足 obstruction-free 要求。值得注意的是，或許有人會認定 lock-free 或 wait-free 演算法會較快，但事實可能恰好相反，因為： - lock-free 和 wait-free 必須處理更多更複雜的 race condition 和 ABA problem，完成相同目的的程式碼比用 lock 更複雜。程式碼越多，執行路徑也會增長。 - 使用 mutex 的演算法具備「後退」(backoff) 的效果，即出現競爭時嘗試另一個途徑，以便臨時避免競爭，mutex 出現競爭時會讓嘗試獲取 lock 者進入睡眠，使拿到 lock 的那個執行緒得以很快地獨占完成一系列流程，吞吐量反而因此提高。。 mutex 導致效能下降的因素，往往是因臨界區過長且過於頻繁，也就限制並行程度，或競爭過於激烈 (context switch 開銷大幅增加)。lock-free/wait-free 演算法的價值在於，其保證一個或所有執行緒始終有進展，而非絕對的高效率。lock-free 和 wait-free 演算法在一種狀況會獲得更好的效率：演算法本身可用少量 atomic 指令實作 —— 實作 lock 也要用到 atomic 指令，當演算法本身用少數指令即可完成時，相比額外用 lock 當然就會有優勢。 ### 案例探討: SPSC [`ringbuffer.c`](https://github.com/sysprog21/concurrent-programs/blob/master/ringbuffer/ringbuffer.c) 是一個 [lock-less](https://en.wikipedia.org/wiki/Non-blocking_algorithm) 的 [Ring buffer](https://en.wikipedia.org/wiki/Circular_buffer) 範例實作，並且適用於 SPSC (single-producer and single-consumer) 情境。 ```c typedef struct { struct { /** Ring producer status. */ uint32_t watermark; /**< Maximum items before EDQUOT. */ uint32_t size; /**< Size of ring. */ uint32_t mask; /**< Mask (size - 1) of ring. */ volatile uint32_t head, tail; /**< Producer head and tail. */ } prod __attribute__((__aligned__(CACHE_LINE_SIZE))); struct { /** Ring consumer status. */ uint32_t size; /**< Size of the ring. */ uint32_t mask; /**< Mask (size - 1) of ring. */ volatile uint32_t head, tail; /**< Consumer head and tail. */ } cons __attribute__((__aligned__(CACHE_LINE_SIZE))); void *ring[] __attribute__((__aligned__(CACHE_LINE_SIZE))); } ringbuf_t; ``` `ringbuf_t` 是該程式的主體結構，可見結構中除了儲存指標的 buffer 本身 (`ring`)，分別還有與生產者/消費者工作相關的 `prod` 和 `cons` 兩個結構。其中，個別的 `head` 和 `tail` 的設計是為了滿足 [lock-less](https://en.wikipedia.org/wiki/Non-blocking_algorithm) 的考量，下面的程式碼更清楚了展示如何使用之。 ```c static inline int ringbuffer_sp_do_enqueue(ringbuf_t *r, void *const *obj_table, const unsigned n) { uint32_t mask = r->prod.mask; uint32_t prod_head = r->prod.head, cons_tail = r->cons.tail; /* The subtraction is done between two unsigned 32-bits value (the result * is always modulo 32 bits even if we have prod_head > cons_tail). So * @free_entries is always between 0 and size(ring) - 1. */ uint32_t free_entries = mask + cons_tail - prod_head; /* check that we have enough room in ring buffer */ if ((n > free_entries)) return -ENOBUFS; uint32_t prod_next = prod_head + n; r->prod.head = prod_next; /* write entries in ring buffer */ ENQUEUE_PTRS(); __compiler_barrier(); r->prod.tail = prod_next; /* if we exceed the watermark */ return ((mask + 1) - free_entries + n) > r->prod.watermark ? -EDQUOT : 0; } ``` `ringbuffer_sp_do_enqueue` 是生產者所運作的主要任務。在進入這個函式之前， `r->cons.head` 和 `r->cons.tail` 數值相同，代表著前一次結束生產的 index 位置。進入函式後，首先計算出 `free_entries`，它是允許生產的最大數量。然後生產者會先更新 `r->cons.head` 到生產結束後的 index 位置，直到核心的生產操作 `ENQUEUE_PTRS()` 結束，再把 `r->cons.tail` 也一併更新成生產完成後的 index 位置。換言之，當 `r->cons.tail` 和 `r->cons.head` 在某個執行的時間點有差異，兩個變數之間的範圍表示「生產者正在存取的 buffer 範圍」，消費者可以藉由兩個變數的差異得知無法操作的 buffer 區域。 :::info :information_source: 關於 `free_entries` 如何而得: 注意 `head` 和 `tail` 的數值範圍實際上並不總是小於 buffer 大小，其範圍恆為 `uint32_t` 可表示之大小(0 到 $2^{32} - 1$)。然而受益於此程式要求 buffer 必須是 $2^n$ 大小的限制(n 為整數)，可以透過 `mask` 是 $2^n - 1$ 的性質，以 `mask + cons_tail - prod_head` (modulo) 來計算出正確 `free_entries` 數量。 ::: ### 案例探討: SPMC 談及更複雜的 SPMC (single-producer, multiple-consumer)，就要思索新議題: 對於 dequeue 操作，消費者執行緒除了要確保存取的 buffer 範圍沒有生產者嘗試建立新的元素，還要保證不與其他消費者同時消費相同的元素。[`spmc.c`](https://github.com/sysprog21/concurrent-programs/blob/master/spmc/spmc.c) 就是一個針對SPMC(single-producer, multiple-consumer) 情境的 concurrent queue 案例。 ```c typedef struct __spmc_node { size_t cap; /* One more than the number of slots available */ _Atomic size_t front, back; struct __spmc_node *_Atomic next; uintptr_t buf[]; } spmc_node_t; typedef void (*spmc_destructor_t)(uintptr_t); struct spmc_base { /* current node which enqueues/dequeues */ spmc_node_t *_Atomic curr_enqueue, *_Atomic curr_dequeue; uint8_t last_power; spmc_destructor_t destructor; }; typedef struct spmc_base *spmc_ref_t; ``` `struct spmc_base` 是該程式的主體結構，其中需要關注的成員包含: * `curr_enqueue` 和 `curr_dequeue` 都是 `_Atomic` 類型的 `spmc_node_t *`，指向在 buffer 中要消費或者生產的目標節點 * `last_power`: 是最近一次建立的 `spmc_node_t` 中之 buffer 的大小 (`cap`=$2^{last\_{power}}$) 而 `spmc_node_t` 是包含 buffer 的節點，這些節點同時還會形成一個 linked list，當節點中的 buffer 已達生產上限(尚未被消費掉)，就產生一個新的節點並配置一個更大的 buffer: * `buf[]` 是實際要操作的元素之 buffer，這是 [Arrays of Length Zero](https://gcc.gnu.org/onlinedocs/gcc/Zero-Length.html) 語法，允許對一個 struct 分配變數長度大小的空間 * `front` 是消費者對該 node 的 buffer 所操作的下個 index，`back` 是生產者對該 node 的 buffer 所操作的下個 index，兩者需要搭配使用確認 buffer 是否是空或滿狀態 * `next` 是下一個 `spmc_node_t` 節點 * `cap` 是節點中 buffer 的大小對此程式的資料結構有一定的認知後，我們關注其 dequeue 操作與 SPSC 版本的差異之處: ```c= bool spmc_dequeue(spmc_ref_t spmc, uintptr_t *slot) { spmc_node_t *node = atomic_load_explicit(&spmc->curr_dequeue, memory_order_consume); size_t idx; no_increment: do { idx = atomic_load_explicit(&node->front, memory_order_consume); if (!IS_READABLE(idx, node)) { if (node != spmc->curr_enqueue) atomic_compare_exchange_strong( &spmc->curr_dequeue, &node, atomic_load_explicit(&node->next, memory_order_relaxed)); goto no_increment; } else *slot = node->buf[INDEX_OF(idx, node)]; } while ( !atomic_compare_exchange_weak(&node->front, &(size_t){idx}, idx + 1)); return true; } ``` `spmc_dequeue` 消費 buffer 中的元素，再次注意 SPMC 情境下會有多個 thread 同時在進行 `spmc_dequeue`。最開始，`atomic_load_explicit` atomically 的載入 `spmc->curr_dequeue` 指向的節點，並使用 `atomic_load_explicit` 載入該節點的 `node->front` 的值。接著 `IS_READABLE(idx, node)` 檢查讀出來的 `node->front` 與 `node->back` 是否相同，這表示該 node 中之 buffer 為空狀態，根據狀況可以區分成: 1. 如果 buffer 不為空，先直接取出 buffer 中的元素即可 (第 16 行) 2. 如果 buffer 為空，且 `spmc->curr_dequeue` 指向的也是目前的 `spmc->curr_enqueue` 所指向，表示確實沒有新的元素可以消費，則只能 goto 持續等待 queue 被填入(第 10 行條件為 false) 3. 如果 buffer 為空，但 `spmc->curr_dequeue` 與 `spmc->curr_enqueue` 是不同的節點，表示其他節點上可能存在可以消費的元素，則嘗試將 `spmc->curr_dequeue` 移動到下個 node(第 11 行)，之所以需要 compare-and-swap (CAS)，是因為多消費者的 `spmc->curr_dequeue` 會有多個 thread 嘗試改寫最後要 CAS 的更新 `node->front`，將其加 `1`，這個操作是與 SPSC 的差異關鍵，在 SPSC 中，我們只要確保取得元素的 buffer 位置不要同時被生產者存取。但在 SPMC 情境下，還要確保消費者互相不會重複的取到同個元素，為此需要 CAS 或者類似的操作去競爭該元素的消費權利，競爭到的執行緒之 CAS 會成功並得以返回，其他執行續則需再次留在 while 迴圈直到競爭到下一個元素。

Read more

2024q1 第 9 週測驗題

你所不知道的 C 語言：函式呼叫篇

2024q1 第 10 週測驗題

Linux 核心設計: RCU 同步機制