LWN: lockless編程模式 - full memory barrier！
關(guān)注了就能看到更多這么棒的文章哦～
Lockless patterns: full memory barriers
March 5, 2021
This article was contributed by Paolo Bonzini
Lockless patterns
DeepL assisted translation
https://lwn.net/Articles/847481/
系列文章之一：LWN：介紹lockless算法！
系列文章之二：LWN: lockless編程模式——relaxed acess和partial memory barrier
本系列前兩篇文章中提到過(guò)有四種對(duì)內(nèi)存訪問(wèn)確保順序的方式：第一篇中的 load-acquire 和 store-release 操作，第二篇中的 read 和 write memory barriers。本系列繼續(xù)探討 full memory barrier，為什么它們開銷太大，以及它們?cè)趦?nèi)核中是如何使用的。
到目前為止所介紹的 4 種不同原語(yǔ)（primitives）都可以對(duì) load 和 store 的順序進(jìn)行限制：
load-acquire 操作會(huì)在其后的 load 和 store 操作之前完成。
store-release 操作被排在其前的 load 和 store 之后。
read memory barrier 能確保其前的 load 先完成，再進(jìn)行之后的 load。
write memory barrier 確保其前 store 先完成，再進(jìn)行后續(xù)的 store。
可以看出，上面這些操作居然都不能確保之前的 store 和之后的 load 的先后順序：
其實(shí)對(duì)處理器來(lái)說(shuō)，要保證 store 能在之后的 load 之前完成，這是一個(gè)更加復(fù)雜的過(guò)程，它應(yīng)該有一個(gè)自己的原語(yǔ)。為了給大家講清楚原因，我們無(wú)法繼續(xù)使用到目前為止一直在用的高級(jí)語(yǔ)言概念，而需要直接深入理解處理器是如何運(yùn)作的。
How processors really do it
第一篇文章已經(jīng)提到，從底層來(lái)看，處理器之間是利用消息傳遞架構(gòu)（message-passing architecture）進(jìn)行通信的，如QPI或HyperTransport。然而，在匯編語(yǔ)言層面，程序員看到的只是 memory load 和 store 等操作。任何與這些 memory 操作相關(guān)的 acquire 和 release 語(yǔ)義都是一種假象，是由處理器的執(zhí)行流水線提供出來(lái)的，也是基于它所運(yùn)行的代碼和此處理器的體系架構(gòu)的約束的。
例如，在 x86 處理器上，所有的 memory load 都算作 "load-acquire"，所有的 memory store 都算作 "store-release"；這種行為是（x86 這個(gè)）體系架構(gòu)所要求的。在針對(duì)這些處理器進(jìn)行代碼編譯時(shí)，仍然需要標(biāo)注 acquire 和 release 操作以及插入 memory barrier，但這些標(biāo)注只是給編譯器看的，用來(lái)避免進(jìn)行無(wú)效的優(yōu)化（invalid optimization）。即使是在這個(gè)工作模式下，體系架構(gòu)也不能保證所有處理器都以相同的順序看到這些 load 和 store 的結(jié)果。比如，假設(shè) a 和 b 已經(jīng)初始化為零：
CPU 1 CPU 2
------------------- --------------------
store 1 into a store 1 into b
load b into x load a into y
如果手動(dòng)排一下，將這四個(gè)操作進(jìn)行各種交叉排列，你會(huì)發(fā)現(xiàn)至少有一個(gè) store 是在相應(yīng)的 load 之前完成的。因此，人們會(huì)認(rèn)為在上述流程運(yùn)行完成后，x 和 y 中至少有一個(gè)會(huì)是 1。然而，即使在 x86 處理器上，也有可能 x 和 y 讀出來(lái)都是 0。
為什么會(huì)這樣呢？原因就在于有 store buffer 這么個(gè)東西。store buffer 位于 CPU 與其 L1 cache 之間。到內(nèi)存的 store 操作通常只會(huì)改變 cache line 中的一部分，因此為了完成這些 store，即使只是寫到 cache，也可能需要先從內(nèi)存中讀取一個(gè)完整的 cache line，這個(gè)操作比較耗時(shí)。在這個(gè)操作過(guò)程中，要 store 的數(shù)據(jù)會(huì)先暫存在 store buffer 中，從而允許 CPU 可以繼續(xù)向后執(zhí)行。
即使是這些具有 store buffer 的 CPU，也可以比較容易就確保 load-load、load-store、和 store-store 的順序：
在 out-of-order 的 CPU 上(這種 CPU 可以不按照代碼中出現(xiàn)的順序來(lái)執(zhí)行指令，以提高性能)，可以通過(guò)預(yù)測(cè)執(zhí)行的方式來(lái)針對(duì)之前的 load 操作來(lái)對(duì) memory 操作進(jìn)行排序。在 cache line 訪問(wèn)和引起這次操作訪問(wèn)的指令走完流水線（instruction retire）之間的這段時(shí)間里，CPU 會(huì)記錄、跟蹤這個(gè) cache line 的 eviction 操作。各個(gè)指令走完流水線(retire)的順序是保證按照代碼順序的，所以會(huì)一直跟蹤直到其之前的 load 全部完成。如果在指令 retire 之前，cache line 發(fā)生了 eviction，那么預(yù)測(cè)執(zhí)行就會(huì)被取消，處理器會(huì)重新發(fā)起 memory 操作。
確保 store 的順序就更簡(jiǎn)單了，只要按照 FIFO 的順序，將 store buffer 中的數(shù)據(jù) flush 到 cache 里去即可。
然而，確保 store-load 順序就不那么容易了。首先，某個(gè) CPU 所發(fā)起的 store 操作可能正停留在它的 store buffer 中，因此當(dāng)另一個(gè) CPU 從 L1 cache 中 load 數(shù)據(jù)時(shí)，看不到這個(gè) store 進(jìn)去的值。其次，store buffer 還提供了 store forwarding 的能力，也就是說(shuō)，memory load 的結(jié)果會(huì)直接從 store buffer 中獲取，而不是從 cache 讀取。如果 CPU 1 或 CPU 2 的 store buffer 中有 b 和 a 這一項(xiàng)，那么 load 操作就可能取到這個(gè) store buffer 中的值，也就是 0。
解決這些問(wèn)題的唯一方法是在 store 和 load 之間確保 store buffer 被 flush 干凈了。這個(gè)操作聽(tīng)起來(lái)很耗時(shí)（會(huì)消耗幾十個(gè)時(shí)鐘周期），但這就是 full memory barrier 也就是 smp_mb()所做的事情了。下面代碼和上面的邏輯類似，只是修復(fù)過(guò)寫成 C 語(yǔ)言：
thread 1 thread 2
------------------- --------------------
WRITE_ONCE(a, 1); WRITE_ONCE(b, 1);
smp_mb(); smp_mb();
x = READ_ONCE(b); y = READ_ONCE(a);
假設(shè) x 為 0。下圖中這一條從 read 到 write 的波浪線就表示 WRITE_ONCE(b，1) 覆蓋了 thread 1 所 load 的值，那么情況（在內(nèi)核的 memory-model 文檔中有詳細(xì)描述）如下。
WRITE_ONCE(a, 1);
|
-----+----- smp_mb();
|
v
x = READ_ONCE(b); ???????> WRITE_ONCE(b, 1);
|
-----+----- smp_mb();
|
v
y = READ_ONCE(a);
因?yàn)檫@些都是 relax 操作，所以不足以在 thread 1 和 thread 2 之間確保兩者先后關(guān)系。而 barrier 本身也沒(méi)有 acquire 或 release 的語(yǔ)義，所以兩個(gè)線程之間根本沒(méi)有確保先后關(guān)系。
然而，這里 barrier 確實(shí)確保了兩個(gè)線程中的操作的先后排序。繼續(xù)以 x=0 的情況為例具體來(lái)說(shuō)，thread 2 中 full memory barrier 保證在 read_once(a) 這一句執(zhí)行時(shí)，store buffer 已經(jīng)被 flush 了。會(huì)不會(huì)在 READ_ONCE(b) 執(zhí)行之前就已經(jīng)完成了呢？如果是這樣的話，READ_ONCE(b)肯定會(huì)看到 thread 2 之前的 WRITE_ONCE(b，1) (畢竟 store buffer 已經(jīng)被 flush 了)，而 x 會(huì)是 1。這是一個(gè)矛盾，因此 READ_ONCE(b) 一定是先執(zhí)行的：
WRITE_ONCE(a, 1); WRITE_ONCE(b, 1);
| |
| -----+----- smp_mb();
| |
v v
x = READ_ONCE(b); -----------> y = READ_ONCE(a);
(if x=0)
由于傳遞性原則，READ_ONCE(a)可以看到 WRITE_ONCE(a，1)的效果，也能看到 y=1。同樣，如果 thread 2 從 a 讀出來(lái)是 0，那么 thread 1 的 full memory barrier 保證了 READ_ONCE(a) 一定在 thread 1 的 READ_ONCE(b)之前執(zhí)行完：
WRITE_ONCE(a, 1); WRITE_ONCE(b, 1);
| |
-----+----- smp_mb(); |
| |
v v
x = READ_ONCE(b); <----------- y = READ_ONCE(a);
(if y=0)
這里如果 y=0 就一定意味著 x=1。不同的執(zhí)行流程可能會(huì)走到上述的兩種可能性之一，但無(wú)論如何，x和 y 不可能都是 0，因?yàn)槟且馕吨?read_once(a)在 read_once(b) 之前執(zhí)行，反之亦然，這都是不可能出現(xiàn)的。
Linux 內(nèi)核的 memory model并未提及這些read-read之間的"happen-before"關(guān)系，因?yàn)闆](méi)有說(shuō)明哪個(gè)是釋放操作，哪個(gè)是獲取操作。但是，實(shí)際上它們對(duì)于不同線程之間的 memory 操作順序的確保方面，具有同樣的效果。因此，對(duì)那些底層使用了 full memory barrier 的高級(jí)別 API，我們也可以認(rèn)為它們具有 acquire 或 release 的語(yǔ)義。這些 API 的使用者就也能利用 happens-before 的方式來(lái)思考他們的代碼。接下來(lái)的例子將展示如何在實(shí)踐中使用。
Sleep/wake-up synchronization
上一節(jié)的詳細(xì)描述，已經(jīng)說(shuō)明 full memory barrier 實(shí)際上以一種復(fù)雜、不直觀的方式來(lái)確保了先后順序。幸運(yùn)的是，上述 "two thread and two flags" 這種模式（即每個(gè)線程向一個(gè) flag 寫入、并從另一個(gè) flag 讀取）對(duì)你來(lái)說(shuō)也許就是你關(guān)于全內(nèi)存壁壘所需要知道的全部了。
這個(gè)模式在很多實(shí)際的重要場(chǎng)景下都有應(yīng)用。假設(shè) thread 2 希望 thread 1 在 2 提出請(qǐng)求的時(shí)候采取行動(dòng)，而此時(shí) thread 1 想做一些其他事，甚至可能是一些不確定需要執(zhí)行多長(zhǎng)時(shí)間的工作，例如將打算退出調(diào)度器的 run queue 并進(jìn)入 sleep 狀態(tài)。那么，代碼會(huì)是這樣的：
如果 thread 2 讀取 dont_sleep 得到值為 0，thread 1 讀取 wake_me 就會(huì)得到 1，并喚醒 thread 2。將 thread 1 視為具有 release 語(yǔ)義的話就更容易理解了（可以認(rèn)為 wake()就是 mutex_unlock 的一部分）。如果 thread 1 讀取 wake_me 得到 0，thread 2 讀取 dont_sleep 就會(huì)得到 1，于是不會(huì)進(jìn)入 sleep 狀態(tài)。通常，這種情況下應(yīng)該是使用 acquire 語(yǔ)義的。
這里實(shí)際上隱藏了一個(gè)假設(shè)條件，即 thread 1 的 wake-up 這個(gè)請(qǐng)求永遠(yuǎn)不會(huì)丟失，也就是說(shuō)，哪怕在 thread 2 的 READ_ONCE()之后但在 sleep()之前調(diào)用 wake()，這個(gè)請(qǐng)求也要是仍然有效的。要避免這個(gè) bug，可以讓 wake()和 sleep()的調(diào)用都使用同一個(gè)鎖來(lái)保護(hù)起來(lái)。這里我們?cè)僖淮慰吹搅?lockless pattern 是如何與傳統(tǒng)的 synchronization 合作的，畢竟加鎖的這條路平常都不會(huì)走到（也就是說(shuō)這是一個(gè) slow path）。
這種方法確實(shí)有效，例如在 Linux 的 prepare_to_wait() 和 wake_up_process() API 中就可以看到效果。這組接口是在 2.5.x 內(nèi)核中引入的，當(dāng)時(shí) LWN 就進(jìn)行了一些介紹。下面是展開了一些相關(guān)函數(shù)后，這個(gè)模式看起來(lái)是什么樣子：
正如我們?cè)谘凶x seqcount 時(shí)看到的，memory barrier 被隱藏在更高級(jí)別的 API 的實(shí)現(xiàn)里。實(shí)際上人們定義一個(gè)帶有 acquire 或者 release 語(yǔ)義的 API 的時(shí)候，其實(shí)就是在其內(nèi)部加上一些 memory barrier 或者 load-acquire/store-release 操作。在這個(gè)案例中，wake_up_process() 就具有 release 語(yǔ)義，而 set_current_state()及調(diào)用它的 prepare_to_wait() 就具有 acquire 語(yǔ)義。
為了減少不必要的喚醒，通常會(huì)對(duì) sleep condition 進(jìn)行兩次檢查，就像這樣：
thread 1 thread 2
------------------- --------------------------
WRITE_ONCE(dont_sleep, 1); if (!READ_ONCE(dont_sleep)) {
smp_mb(); WRITE_ONCE(wake_me, 1);
if (READ_ONCE(wake_me)) smp_mb();
wake(thread2); if (!READ_ONCE(dont_sleep))
sleep();
}
在內(nèi)核里，我們可以在 tcp_data_snd_check() 和調(diào)用 tcp_check_space()的地方（thread 1）和 tcp_poll()（thread 2）之間的交互過(guò)程中看到兩次檢查。在這種情況下，代碼沒(méi)能夠利用更高級(jí)別的抽象，所以可以仔細(xì)研究一下。thread 2 希望在 socket 的 send buffer 沒(méi)有空間的情況下 sleep，因此 tcp_poll()在檢查 __sk_stream_is_writeable()之前設(shè)置了帶有 "wake me" 含義的 SOCK_NOSPACE flag。tcp_poll()中lockless synchronization 的核心代碼是：
set_bit(SOCK_NOSPACE, &sk->sk_socket->flags);
smp_mb__after_atomic();
if (__sk_stream_is_writeable(sk, 1))
mask |= EPOLLOUT | EPOLLWRNORM;
如果 mask 是 0，調(diào)用這部分代碼的函數(shù)就會(huì)最終進(jìn)入 sleep。smp_mb__after_atomic()是 smp_mb()的一個(gè)專用版本，但是語(yǔ)義相同。這些用于優(yōu)化過(guò)的 barrier 會(huì)在未來(lái)的文章中得到進(jìn)一步解釋。
而 thread 1 在處理完 send buffer 中的數(shù)據(jù)后，必須喚醒 thread 2，tcp_data_snd_check() 首先發(fā)送 packet 來(lái)從 buffer 中騰出空間（"不要睡覺(jué)了，現(xiàn)在有空間了！"），然后檢查 SOCK_NOSPACE，最后（通過(guò) sk->sk_write_space()函數(shù)指針）調(diào)用到 sk_stream_write_space()，thread 2 就被喚醒。調(diào)用棧不算復(fù)雜，所以建議讀者自己可以去研究一下代碼。不過(guò)，我想強(qiáng)調(diào)一下 tcp_check_space()中的這段注釋：
/* pairs with tcp_poll() */
smp_mb();
if (test_bit(SOCK_NOSPACE, &sk->sk_socket->flags))
tcp_new_space(sk);
這里利用了 barrier 的 "pair" 含義，來(lái)告訴我們這個(gè)函數(shù)具有 acquire 或 release 的語(yǔ)義。read memory barrier 或者 write memory barrier 相當(dāng)于直接告訴我們這個(gè)函數(shù)具有獲取或釋放的語(yǔ)義。對(duì)于一個(gè) full memory barrier 來(lái)說(shuō)，我們需要仔細(xì)閱讀 barrier 周圍的代碼。具體這個(gè)例子中，我們知道該函數(shù)在 "wake-up" 這一側(cè)，因此它就具有 release 語(yǔ)義；而 tcp_poll()則具有 acquire 語(yǔ)義。
幾乎內(nèi)核中所有可以找到 smp_mb()的地方，都是類似的用法。例如：
workqueue 使用這個(gè)方式來(lái)決定是否有更多的工作需要 worker 去做。這種情況下，thread 1 的角色就被換成 insert_work()，而 thread 2 則變成 wq_worker_sleeping()。
在 futex()系統(tǒng)調(diào)用中，thread 1 的 write 是在 user space 發(fā)生的，而 memory barrier 和 read 操作則是 futex(FUTEX_WAKE)內(nèi)部實(shí)現(xiàn)的。thread 2 的操作就完全是 futex(FUTEX_WAIT)的一部分（因?yàn)?wake_me 是 kernel memory 中的一個(gè) flag)；FUTEX_WAIT 會(huì)使用 futex 的預(yù)期值作為系統(tǒng)調(diào)用的參數(shù)，并用它來(lái)決定是否 sleep。關(guān)于這里具體是如何生效的，可以參見(jiàn) kernel/futex.c 文件開頭的長(zhǎng)長(zhǎng)的注釋。
在 KVM 中，沒(méi)有 sleep() 行為了，而是變成了進(jìn)入處理器的 guest mode 并執(zhí)行虛擬機(jī)內(nèi)部工作的這個(gè)行為了。為了讓處理器從 guest mode 退出來(lái)，kvm_vcpu_kick() 會(huì)向處理器發(fā)送一個(gè)處理器間中斷（inter-processor interrupt）?？梢愿@一串函數(shù)調(diào)用直到 kvm_vcpu_exiting_guest_mode()，在這里就能找到我們熟悉的關(guān)于 memory barrier pairing 的注釋了，這個(gè)函數(shù)也是讀取 vcpu->mode 的地方。
Virtio 設(shè)備中實(shí)際上有兩處在使用我們介紹的這個(gè)模式。其中之一是在 driver 希望停止處理 completed requests，并且發(fā)送一個(gè)中斷來(lái)對(duì)其進(jìn)行喚醒操作。另一方面，device 想停止處理 submitted requests，device 就通過(guò)寫入 "doorbell"內(nèi)存位置（相當(dāng)于按門鈴）來(lái)喚醒它。
我們這就完成了 memory barrier 的介紹。后續(xù)，我們將討論一下 compare-and-swap 操作、它們?nèi)绾闻c鎖結(jié)合起來(lái)實(shí)現(xiàn) lock-free fast path、以及它們?cè)趯?shí)現(xiàn) lock-free linked list 中起到的作用。
全文完
參考資料：
LWN 文章遵循 CC BY-SA 4.0 許可協(xié)議。
長(zhǎng)按下面二維碼關(guān)注，關(guān)注 LWN 深度文章以及開源社區(qū)的各種新近言論～