LWN: Lockless編程模式 - 最后的一些話題！
關(guān)注了就能看到更多這么棒的文章哦～
Lockless patterns: some final topics
March 29, 2021
This article was contributed by Paolo Bonzini
Lockless patterns
DeepL assisted translation
https://lwn.net/Articles/850202/
到目前為止，本系列已經(jīng)介紹了 Linux 內(nèi)核中常見的五種 lockless 模式，應(yīng)該是在 Linux 上工作時最可能遇到的五種模式。在整個系列中，為了清楚起見，有些細(xì)節(jié)被遺漏了，有些被簡化了。在這最后一篇文章中，我會梳理一下其中的一些細(xì)節(jié)，并嘗試回答一個可能是最重要的問題：應(yīng)該在什么情況下使用這里介紹的 lockless 模式？
Data, address, and control dependencies
迄今為止所有介紹過的代碼示例中，在同一個線程中的指令的順序要么是通過 acquire 和 release 語義來確保的，要么是通過 memory barrier 確保的。然而，有時候處理器和或者編譯器完全不可以對指令進(jìn)行 reorder（重新排序），因為某條指令是跟前面的另一條指令有依賴性的。這種情況下，哪怕是對那些 relaxed load 和 store 操作，也需要保證這兩個指令之間的順序。這里會出現(xiàn)三種依賴情況。
Data depenencies（數(shù)據(jù)依賴） ：某個 store 操作是要將之前的一個 load 操作所讀出的數(shù)據(jù)進(jìn)行寫入時，或者是需要使用這個 load 出來的數(shù)據(jù)時，就存在數(shù)據(jù)依賴性：
int x = READ_ONCE(a);
WRITE_ONCE(b, x + 1);
Data dependency 是這三種情況中最簡單的一種，在 load 之前，不可能執(zhí)行 store，否則處理器根本不知道應(yīng)該寫入的值是什么。因此，在這種情況下從 a 中進(jìn)行的讀操作其實就跟 load-acquire 一樣，或者說至少對于接下來的這句 WRITE_ONCE() 操作是這樣的。與 smp_load_acquire() 或 smp_rmb()不同的是，利用 data dependency 所得到的 order 順序并不能保證接下來所有的 memory 操作都在這個 read 操作之后進(jìn)行。在下面的例子中，對 c 進(jìn)行的 read 可能會在對 a 的 read 之前就執(zhí)行了，但是 b 的 write 操作不可能在讀 a 之前進(jìn)行：
int x = READ_ONCE(a);
WRITE_ONCE(b, x + 1);
int y = READ_ONCE(c);
然而，我們已經(jīng)看到，大多數(shù)情況下，lockess 代碼只關(guān)心特定的幾個內(nèi)存操作之間的排序，在某些情況下，load 操作完全可以放心地使用 READ_ONCE() 來進(jìn)行，因為唯一會用到這個 load 出來的值的地方就是后面的一個 store 操作，并且這也是唯一一個需要確保順序的操作。不過，在本系列文章中所介紹的各種模式中，都不是這種情況，因為都不是在同一個 thread 中先進(jìn)行 load 再進(jìn)行 store 操作的，所以無法用到這里說到的 data dependency。
Address dependency ：如果一個讀或?qū)懖僮鞯?address 是來自于之前的 load 操作，或者是基于之前 load 結(jié)果算出來的，那么就存在地址依賴性。
int x = READ_ONCE(a);
int y = READ_ONCE(b[x]);
struct s *x = READ_ONCE(a);
WRITE_ONCE(x->f, 1);
address dependency 的道理也是很容易理解的。在第一個例子中，b[x]的 read 操作不可能在 x 的 read 之前進(jìn)行；在第二個例子中，在讀取完成之前 CPU 也是不能知道后續(xù)要寫入的地址的。
同樣，在下面來自第一部分的這段代碼中，datum->x 的地址必須是在從 message 中通過 load 得到 datum 之后才能知道的：
thread 1 thread 2
-------------------------------- ------------------------------------
a.x = 1;
smp_store_release(&message, &a); datum = smp_load_acquire(&message);
printk("%x\n", datum->x);
在不知道目標(biāo)地址的時候，CPU 怎么可能從內(nèi)存中 load 或者 store 數(shù)據(jù)呢？因此，人們會希望將 thread 2 的第一行寫成下面這個樣子，這樣就不需要 load-acquire 指令了：
datum = READ_ONCE(message)
這個想法很合理。查看匯編代碼的話，其實對于幾乎所有 Linux 所能支持的處理器來說也都是成立的，不過，Alpha 架構(gòu)除外，因為它的 cache 架構(gòu)很特殊。從 Linux 4.15 開始，Linux 開發(fā)者決定在 Alpha 上允許 READ_ONCE() 的開銷更高。因此現(xiàn)在 address dependency 的 load 總是會在它們所依賴的 load 之后執(zhí)行。請注意，address-dependent store 從來不會出問題。
最后，*control dependency* ：也就是 read 出來的值可能會導(dǎo)致后續(xù)的 read 或 write 操作完全不會執(zhí)行的話，這就是控制依賴：
int y = 0;
if (READ_ONCE(a))
y = READ_ONCE(b); // *no* ordering here
if (READ_ONCE(a))
WRITE_ONCE(b, 1); // write is ordered here
當(dāng)一個 load 與另一個 load 操作之間存在 control dependency 關(guān)系時（如上面第一個例子），就絕不會出現(xiàn)順序錯誤的情況。CPU 可能會在執(zhí)行判斷邏輯（test）之前先預(yù)測性地執(zhí)行后面的 load 操作，然后如果發(fā)現(xiàn) "then" 這個分支的代碼不應(yīng)該被執(zhí)行，那么直接忽略這個 load 出來的數(shù)據(jù)就好。從 load 到 store 的 control dependency 關(guān)系則是比較棘手的。這里 CPU 不是問題，因為在知道是不是真的需要進(jìn)行 store 操作之前，不會把數(shù)據(jù)寫入 cache，但編譯器這邊可能出現(xiàn)問題。想一想下面這樣的代碼：
x = READ_ONCE(a);
smp_store_release(&b, 1);
if (x)
do_something();
else
do_something_else();
聰明的程序員可能想這樣寫：
x = READ_ONCE(a);
if (x) {
WRITE_ONCE(b, 1);
do_something();
} else {
WRITE_ONCE(b, 1);
do_something_else();
}
這里的 control dependency 確實能讓 CPU 保證 read a 和 write b 之間的順序。然而，編譯器可能會在優(yōu)化時決定提前到判斷條件之前就進(jìn)行 write 操作，然后才會對 x 的值進(jìn)行判斷，這樣導(dǎo)致生成的代碼其實看起來像這個邏輯：
x = READ_ONCE(a);
WRITE_ONCE(b, 1);
if (x)
do_something();
else
do_something_else();
這樣一來 control dependency 就不復(fù)存在了，CPU 和編譯器都可能會在 read a 之前就執(zhí)行了 store 操作。通常情況下，要想解決這些 control dependency 問題，只要避免這么使用并且將每個 store 操作都改為相應(yīng)的 acquire 或 release 的 store 就可以了。
在上述所有這些情況中，address-dependent load 可能是你唯一會真正碰到的情況。最常見（并且很容易理解）的情況就是利用 rcu_dereference() 和 srcu_dereference() 來取得一個數(shù)據(jù)結(jié)構(gòu) struct，然后讀取其中的內(nèi)容。在 Alpha 架構(gòu)上，這些 RCU 和 SRCU 的基本函數(shù)哪怕是在 Linux 4.15 之前版本上都已經(jīng)帶有了必須的 memory barrier 操作。但是，在有些很少見的情況下如果沒有使用 RCU，并且兩個 memory access 都是用 READ_ONCE()，那么您需要多加小心。
Optimized memory barriers
第 5 部分文章中介紹了 atomic read-modify-write 操作，比如 atomic_inc()。Linux 對于這些不會返回數(shù)值的操作都定義為 relax 語義。并且如果 compare-and-swap 操作失敗了，那么也就不能確保帶有 memory barrier，而成功的 compare-and-swap 操作從效果上來說就像開發(fā)者在這個操作的兩邊都加了一個 memory barrier 一樣。
然而，有些處理器并沒有一個 relaxed read-modify-write 操作執(zhí)行。在這些處理器上，寫這樣的代碼（這是第三篇文章中的 full memory barrier 模式的一個變體）就是個浪費了，這里 set_bit()（這個操作一定會先讀取目標(biāo)地址的數(shù)據(jù)之后才會改變指定的 bit）和 smp_mb() 已經(jīng)提供了 back-to-back memory barrier：
set_bit(&flag1, FLAG_DONT_SLEEP);
smp_mb();
if (READ_ONCE(wake_me))
wake(thread2);
為此，Linux 定義了一些優(yōu)化版的 memory barrier 操作：smp_mb__before_atomic() 和 smp_mb__after_atomic() 。它們會根據(jù)當(dāng)前體系架構(gòu)中 atomic read-modify-write 操作的具體硬件實現(xiàn)細(xì)節(jié)，來決定是編譯成 compiler-only barrier 還是 full memory barrier。舉例來說，x86 架構(gòu)上的所有 read-modify-write 操作都會在兩邊隱含了一個 barrier，因此在 x86 架構(gòu)上，這些優(yōu)化版的 memory barrier 操作就會是一個 compiler-only barrier。而在 ARM 架構(gòu)上有可能會定義有 relaxed read-modify-write 操作，因此，這些優(yōu)化版的 memory barrier 將生成一個 dmb 指令，從而替代 smp_mb()：
set_bit(&flag1, FLAG_DONT_SLEEP);
smp_mb__after_atomic();
if (READ_ONCE(wake_me))
wake(thread2);
另一個優(yōu)化版的 memory barrier 是 smp_store_mb()，是用來替代 WRITE_ONCE() 之后緊跟著 smp_mb() 的情況。例如：
thread 1 thread 2
------------------- --------------------------
smp_store_mb(dont_sleep, 1); smp_store_mb(wake_me, 1);
if (READ_ONCE(wake_me)) if (!READ_ONCE(dont_sleep))
wake(thread2); sleep();
When to use lockless patterns?
盡管本系列的前幾篇文章都盡量在舉例的時候使用 Linux kernel 中的實際代碼，但其實它們只是用來展示原理的。雖然這些文章中的內(nèi)容應(yīng)該足夠讓大家理解現(xiàn)有的代碼了，但是一直很少講解什么時候應(yīng)該采用這些模式以及為什么采用這些模式。
在系列文章中，我一直試圖強調(diào)的一件事是，lockless 技術(shù)并不是傳統(tǒng)的 synchronization primitives（同步接口）的替代品。它們只是達(dá)到目的的一種手段，是用來降低同步的開銷的（cacheline contention，也就是 cache 競爭，這也是某種意義上的同步操作，只是它發(fā)生在處理器內(nèi)部，而不是你的代碼中）。并發(fā)代碼（concurrent code）中開銷很昂貴的同步操作是無法徹底消除的，但可以盡量減少使用這些開銷昂貴的指令，或者把將它們移出 hottest parth（也就是最常執(zhí)行到的代碼分支）。為此，下面這些設(shè)計要點值得注意：
與現(xiàn)在已經(jīng)在使用的 lock 和 shared data access（公共數(shù)據(jù)的訪問）的交互。
對公共數(shù)據(jù)（shared data）的寫入頻率：每當(dāng)一個線程向公共位置寫入數(shù)據(jù)時，所引發(fā)的 cache coherency traffic（為了保持 cache 一致性而占用總線的帶寬）最終可能會導(dǎo)致今后的擴展瓶頸（scalability bottleneck）。
進(jìn)行同步的頻率：運行多個線程運行的最好方式是讓它們盡可能地獨立執(zhí)行，因為同步（synchronization）操作總會引入開銷的。
比方說，你想在代碼運行時收集一些統(tǒng)計數(shù)據(jù)，比如統(tǒng)計一下通過網(wǎng)絡(luò)接口發(fā)送了多少個數(shù)據(jù)包，并且希望盡量減少這個統(tǒng)計工作的開銷。在貿(mào)然決定用 lockless 的方式實現(xiàn) counter 之前（比如用 atomic increment 指令），應(yīng)該先調(diào)查一下當(dāng)前發(fā)送數(shù)據(jù)包這個操作是如何確保是序列化進(jìn)行的。比如說發(fā)送數(shù)據(jù)包的地方已經(jīng)利用了一個 spinlock 或者 mutex，那么很可能我們做了一個花里胡哨的 lockless 的 counter 功能也無法獲得什么性能上的好處：如果你確保 counter 是能放在發(fā)送數(shù)據(jù)包時所需要的一個 cacheline 中的話，那么在已經(jīng)持有 lock 的情況下，對單個 memory 內(nèi)容進(jìn)行修改的操作幾乎沒有多大開銷。
如果發(fā)送數(shù)據(jù)包時并沒有一個必定會持有的 lock，那么 lockless 技術(shù)可能確實是會帶來好處的，但這里不僅僅是一個 atomic read-modify-write 操作就能搞定的。比如說，你可以考慮使用多個 counter，這樣你就可以在不用 lock 的情況下（只要這些變量是 per-CPU 的就行）或在一個早已經(jīng)在用的 lock（比如每個 network queue 的保護(hù)鎖）保護(hù)下來對其進(jìn)行遞增操作。在讀取統(tǒng)計信息的時候，可以對這些 counter 進(jìn)行 sum 計算（這種操作應(yīng)該很少進(jìn)行）：這種解決方案避免了對公共數(shù)據(jù)的并發(fā)寫入，并且不需要在 hot path 上增加任何額外同步操作。
在上面的例子中，一個粗粒度的 lock（例如對 network queue 操作進(jìn)行保護(hù)的 lock）并不一定意味著會在今后的擴展（scalability）時導(dǎo)致問題：在一個設(shè)計為保持各個線程大部分時間獨立運行的系統(tǒng)中，對于粗粒度 lock 的競爭通常是很罕見的，甚至完全不存在。相反，如果用細(xì)粒度鎖來保護(hù)過量的公共數(shù)據(jù)訪問，則會大幅增加同步成本，從而導(dǎo)致性能下降。
細(xì)粒度鎖的開銷在 read/write lock 中表現(xiàn)得尤為明顯，這種情況下，哪怕是 read 這一方，也需要進(jìn)行 write 操作才能拿到這個 lock。在編寫那些高可擴展性的代碼（scalable code）時，基本可以將 read/write lock 看做是 "shared/exclusive" lock，這樣可以簡化思考。你可以使用粗粒度的 read/write lock 來確保只有在 hot path 中才需要針對并發(fā)執(zhí)行的情況進(jìn)行特殊設(shè)計：那些不太頻繁執(zhí)行的代碼為了要進(jìn)行 exclusive（獨占）訪問而獲取了鎖，這種情況下所有的 lockless fast path 也完全不用考慮受這些代碼的影響。Linux 的 mmap_sem 就是一個例子，Linux 會在獲取 mmap_sem 信號量的同時也進(jìn)行許多 page-table 操作。不過，獲取 mmap_sem 進(jìn)行 read 操作的開銷還是比較高的，這成為了一個眾所周知的問題，也就是 mmap_sem 的 scalability 問題。
如果需要對特定的數(shù)據(jù)結(jié)構(gòu)進(jìn)行細(xì)粒度的加鎖保護(hù)，那么在一個可擴展性好的系統(tǒng)中，通常會只有很少的對這些數(shù)據(jù)結(jié)構(gòu)進(jìn)行的寫入操作。你可以嘗試用 seqlocks 或 RCU 等機制來代替 read/write lock，對 reader 這一邊的 critical section 進(jìn)行保護(hù)。當(dāng) writer（寫入者）不希望耗費 synchronize_rcu() 的時間時，SRCU（可以認(rèn)為它是一個 subsystem RCU，而不是 sleepable RCU）也可以成為 RCU 的一個有效替代方案。
哪怕 thread 都是獨立運行的，也可能在極少數(shù)情況下是必須進(jìn)行交互的。如果某個系統(tǒng)中每秒都需要對一個 flag 進(jìn)行幾千次甚至幾百萬次的檢查，如果每次檢查中都用細(xì)粒度的鎖進(jìn)行保護(hù)，那么無論線程之間的這些爭搶指令數(shù)有多么少、爭搶的發(fā)生是多么罕見，帶來的開銷都會變得明顯。在這些情況下，在 fast path 中利用 lockless 技術(shù)就非常有價值了。
例如，你可以給每個線程設(shè)計一個請求隊列來容納所有來自其他線程的 request，并通過 single-consumer linked list（單一消費者的鏈表）來進(jìn)行管理。對這些 request 的處理也許可以采用之前 full memory barrier 文章中所提到的 cross-thread notification（線程間通訊）方式來觸發(fā)。然而，這些技巧要想真有效果，那么就必須得到整個系統(tǒng)的支持。換句話說，在一個以避免可擴展性瓶頸為目的的系統(tǒng)中，往往所出現(xiàn)的一些細(xì)節(jié)問題都是比較通用的問題，使用我們文章中介紹的模式通常可以有效解決這些問題。
大家在努力利用 lockless 技術(shù)來提高系統(tǒng)的可擴展性（scalability）時，很需要把 lock-free 和 wait-free 算法區(qū)分開來。lock-free 算法保證了系統(tǒng)整體能往前執(zhí)行下去，但并不能保證每個線程都能正常往下執(zhí)行；lock-free 算法通常都是不公平的，如果每秒的操作次數(shù)超過了某個閾值，那么有可能其中一些線程最終可能會頻繁失敗，從而導(dǎo)致 livelock。wait-free 算法額外保證了每個線程的繼續(xù)執(zhí)行。通常復(fù)雜度就會大增（也并不一定就會更復(fù)雜）。例如消息傳遞和跨線程通知都是符合 wait-free 的。
從 Linux 的 llist 相關(guān) API 來看，llist_add() 就是 lock-free 的。在消費者這一邊來看的話，llist_del_first()是 lock-free 的，而 llist_del_all()是 wait-free 的。因此，如果能預(yù)測到會有許多生產(chǎn)者（producer）會調(diào)用 llist_add()時發(fā)生競爭的話，那么 llist 可能就不是一個合適選擇了；而使用 llist_del_all()可能比 llist_del_first()更好，除非要求時間消耗一定要是個固定時長。對于某些架構(gòu)來說，指令集不允許將 read-modify-write 用在 wait-free 代碼里面。如果是這樣的話，llist_del_all()就只是 lock-free 的（但仍然是比較好的選擇，因為它可以讓消費者對共享數(shù)據(jù)結(jié)構(gòu)進(jìn)行的訪問更加少）。
無論什么情況，最好的檢查代碼性能方法都是對它進(jìn)行基準(zhǔn)測試（benchmark）。盡管直覺以及一些流行 pattern 可以在設(shè)計和實現(xiàn)階段給你指導(dǎo)，但要準(zhǔn)備好最后被測試結(jié)果證明做錯了的覺悟。
最后，我將引用 Dave Chinner 的一段優(yōu)秀點評來結(jié)束這個系列文章：
這就是并發(fā)編程的藝術(shù)——僅僅知道什么是 lockless 算法是不夠的，你需要了解這些算法導(dǎo)致的數(shù)據(jù)訪問模式，以及這些訪問模式何時會對軟件產(chǎn)生限制。當(dāng)然，知道什么時候不使用 lockless 算法（因為有更好的方法來減少公共數(shù)據(jù)的訪問）也是這個藝術(shù)的一部分。
全文完
LWN 文章遵循 CC BY-SA 4.0 許可協(xié)議。
長按下面二維碼關(guān)注，關(guān)注 LWN 深度文章以及開源社區(qū)的各種新近言論～