LWN: lockless編程模式——relaxed acess和partial memory barrier
關(guān)注了就能看到更多這么棒的文章哦～
Lockless patterns: relaxed access and partial memory barriers
February 26, 2021
This article was contributed by Paolo Bonzini
DeepL assisted translation
https://lwn.net/Articles/846700/
本系列中的第一篇文章LWN：介紹lockless算法！對(duì) lockless 算法進(jìn)行了介紹，以及介紹了"happens before" 關(guān)系從而幫助理解 lockless 算法。下一步是看一下 "data race" 的概念，以及為防止 data race 需要使用的 primitives（原語(yǔ)）。我們會(huì)繼續(xù)來(lái)了解 relax access、memory barrier，以及如何用它們來(lái)實(shí)現(xiàn)內(nèi)核的 seqcount 機(jī)制。
對(duì)于一些 Linux 內(nèi)核程序員來(lái)說(shuō)，memory barrier 已經(jīng)很熟悉了。第一份對(duì)內(nèi)核中數(shù)據(jù) concurrent access (并發(fā)訪問(wèn))規(guī)范進(jìn)行初步介紹的文檔，其實(shí)名字就叫做 memory-barriers.txt。該文檔介紹了許多種 memory barrier，以及 Linux 對(duì)于 data dependency(數(shù)據(jù)依賴(lài))和 control dependency(控制依賴(lài))有些什么期望。它還介紹了 "memory-barrier pairing"，這可以被看作是 release-acquire 這種配對(duì)概念的類(lèi)似產(chǎn)物，因?yàn)樗彩怯脕?lái)幫助在跨線程環(huán)境中確保 happens before 關(guān)系的。
本文將不會(huì)像 memory-barriers.txt 中那么詳盡地介紹。相反，我們將看看 barrier 比起 acquire and release （獲取和釋放）模型有些什么差異，以及它們?nèi)绾魏?jiǎn)化并確保 seqcount 原語(yǔ)的正確實(shí)現(xiàn)。不過(guò)，一篇文章哪怕連最常見(jiàn)的 memory barrier 都不可能涵蓋完整，所以完整的 memory-barrier 講解將不得不等待下一期的內(nèi)容。
Data races, relaxed accesses, and memory barriers
data race 的概念最早是在 C++11 中引入的，此后，它被應(yīng)用到其他各種語(yǔ)言中，尤其是 C11 和 Rust。這些語(yǔ)言標(biāo)準(zhǔn)在如何處理對(duì)數(shù)據(jù)結(jié)構(gòu)的 lockless access 方面規(guī)定得相當(dāng)嚴(yán)格，它們?cè)O(shè)計(jì)了專(zhuān)門(mén)的 atomic load 和 atomic store 原語(yǔ)來(lái)實(shí)現(xiàn)這個(gè)目的。
當(dāng)兩個(gè)訪問(wèn)是并發(fā)發(fā)生的時(shí)候（即無(wú)法保證它們的 happen before 關(guān)系）、其中至少有一個(gè)是 store 操作、并且至少有一個(gè)沒(méi)有使用 atomic load 或者 atomic store 原語(yǔ)時(shí)，就會(huì)發(fā)生 data race。每當(dāng)發(fā)生 data race 時(shí)，這兩個(gè)操作的最終結(jié)果根據(jù) C11/C++11 定義是不可確定的，這意味著任何結(jié)果都有可能。避免了 data race 并不代表說(shuō)你的算法也是沒(méi)有 "race condition" 的：data race 是對(duì)語(yǔ)言標(biāo)準(zhǔn)（language standard）的違反，而 race condition 則是源于不正確使用鎖、不正確的獲取/釋放語(yǔ)義、或兩種錯(cuò)誤都存在。
然而，data race 和由此產(chǎn)生的未定義行為（undefined behavior）是很容易避免的。在我們想對(duì)一個(gè)共享數(shù)據(jù)進(jìn)行 store 操作時(shí)（這種情形很常見(jiàn)），有兩種方法可以做到這一點(diǎn)。第一種是確保這兩個(gè)操作有 happens before 的順序關(guān)系，也就是使用任意一種可用的獲取和釋放操作來(lái)確保；第二種方法就是使用 atomic load 和 atomic store 操作。
C11、C++11 和 Rust 都提供了各種 memory ordering 機(jī)制供程序員在 load 和 store 時(shí)使用。我們感興趣的三種是：acquire（與 load 一起使用）、release（配合 store）和 relaxed（兩種操作都適用）。Acquire 和 release 現(xiàn)在應(yīng)該大家都理解了，Linux 在 smp_load_acquire()和 smp_store_release() 操作中都使用了同樣的概念。而 relax 操作則不會(huì)對(duì)任何跨線程操作保證順序，也就是不會(huì)確保 happen before 的關(guān)系。相反，relax 操作只是為了 data race 以及相關(guān)的未定義行為，基本上沒(méi)有用處了。
在實(shí)際實(shí)現(xiàn)中，Linux 希望編譯器和 CPU 在實(shí)現(xiàn)的時(shí)候都能比語(yǔ)言標(biāo)準(zhǔn)中的定義更加具有可確定性一些。尤其是內(nèi)核希望普通 load 和 store 都不會(huì)因?yàn)橥瑫r(shí)有個(gè) concurrent store 而導(dǎo)致出現(xiàn) undefined behavior。然而，這種情況下 load 或 store 的最終值仍然是無(wú)法確定的，很可能是完全錯(cuò)誤的數(shù)據(jù)。例如可能包括舊的值的一部分和新值的一部分，混合在一起。這意味著，使用從 data race 中 load 出來(lái)的指針值的話(huà)會(huì)出現(xiàn)問(wèn)題的。
此外，普通的 load 和 store 會(huì)受到編譯器優(yōu)化的影響，這可能也會(huì)產(chǎn)生意外結(jié)果。因此，relaxed-ordering memory operation（放寬內(nèi)存操作的 ordering 要求）、但同時(shí)要保證 atomic 原子操作，這種想法對(duì)于 Linux 來(lái)說(shuō)就很有用了。這就是 READ_ONCE()和 WRITE_ONCE() 宏所提供的功能。本系列中的其他文章將會(huì)總是顯式（explicit）使用 READ_ONCE()和 WRITE_ONCE()，這是如今的 Linux 開(kāi)發(fā)者認(rèn)為比較好的做法。
這些宏已經(jīng)出現(xiàn)在上一篇文章的一個(gè)例子中了：
它們?cè)谑褂梅绞缴项?lèi)似于 smp_load_acquire()和 smp_store_release()，但是它們的第一個(gè)參數(shù)是賦值的目標(biāo)(也就是所謂的左值，lvalue)，而不是指針。除非有其他機(jī)制確保 data race 的結(jié)果會(huì)被扔掉，否則強(qiáng)烈建議使用 READ_ONCE()和 WRITE_ONCE()來(lái)在沒(méi)有 lock 保護(hù)的情況下 load 和 store 公用數(shù)據(jù)（shared data）。通常情況下，relaxed atomic 操作會(huì)與其他一些具有釋放和獲取語(yǔ)義的原語(yǔ)（或同步機(jī)制）一起使用，靠它們來(lái)確保 relaxed write 操作和對(duì)相同內(nèi)存位置的 read 操作保證順序。
舉例來(lái)說(shuō)，假設(shè)你有多個(gè) work item，它們會(huì)用 1 來(lái)填充數(shù)組中的某些單元，spawn 并完成了這些 work item 之后，必須要先調(diào)用 flush_work() ，然后才能對(duì)這個(gè)數(shù)組進(jìn)行 read 操作。與 pthread_join()類(lèi)似，flush_work() 也具有獲?。╝cquire）語(yǔ)義，與 work item 的結(jié)束是保證同步的（synchronized）；flush_work()保證在 work item 完成后才會(huì)讀取數(shù)組內(nèi)容，并且可以用普通的 load 方式來(lái)讀取數(shù)組了。但是，如果多個(gè)、并發(fā)的 work item 可以對(duì)數(shù)組中同一個(gè)元素進(jìn)行 store 操作，就必須使用 WRITE_ONCE(a[x]，1)，而不是僅僅使用普通的 a[x]=1。
當(dāng)釋放和獲取語(yǔ)義是使用 memory barrier 來(lái)實(shí)現(xiàn)時(shí)，就會(huì)出現(xiàn)更復(fù)雜的情況。為了解釋這種情況，我們將講解 seqcounts 這個(gè)實(shí)際例子。
Seqcounts
Seqcounts 這種原語(yǔ)是專(zhuān)門(mén)用來(lái)供消費(fèi)者（consumer）檢測(cè)到數(shù)據(jù)結(jié)構(gòu)在消費(fèi)者的訪問(wèn)過(guò)程中間發(fā)生過(guò)變化。雖然它們只可以用在特殊情況下（要求被保護(hù)的數(shù)據(jù)量小、在 read 時(shí)的 critical section 不會(huì)帶來(lái)副作用、寫(xiě)入速度快并且很少需要寫(xiě)入），但它們有很多有趣的特性，特別是 reader 不會(huì)導(dǎo)致 writer 餓死，writer 可以對(duì)存放這個(gè) seqcount 的 cacheline 保持所有權(quán)。這兩個(gè)特性使得 seqcounts 在那些需要很強(qiáng)的擴(kuò)展性（scalability）的場(chǎng)景特別有用。
seqcounts 是一個(gè)單生產(chǎn)者、多消費(fèi)者(single-producer, multiple-consumer)的原語(yǔ)。為了避免有多個(gè)并發(fā)寫(xiě)入者（concurrent writers），它們通常會(huì)與 spinlock 或 mutex 結(jié)合使用，形成了我們熟悉的 Linux seqlock_t type。不過(guò)，有時(shí)在內(nèi)核之外，你會(huì)看到 seqcounts 被稱(chēng)為 seqlocks。
Seqcounts 實(shí)際上是一個(gè)生成數(shù)(generation count)，其中如果且僅當(dāng) write 操作正在進(jìn)行時(shí)這個(gè)生成數(shù)才是奇數(shù)。如果生成數(shù)在 reader 這一邊的 critical section 之前的時(shí)候看到是奇數(shù)，或者在 reader critical section 內(nèi)部發(fā)生了改變，那么說(shuō)明 reader 就可能已經(jīng)訪問(wèn)到了一個(gè)不一致的狀態(tài)，必須重新嘗試 read 操作。為了使 seqcount 能正確工作，reader 必須要能正確檢測(cè)到 write 操作的開(kāi)始和結(jié)束。這需要兩個(gè) load-acquire 和兩個(gè) store-release 操作。假如我們沒(méi)有已經(jīng)封裝好的 API，通常人們是像下面這樣編寫(xiě) seqcount reader 和 writer 的：
這段代碼類(lèi)似于上一篇文章中所說(shuō)的 "message passing(消息傳遞)" 模式。有兩對(duì) load-acquire 和 store-release 操作，一組是針對(duì) sc 的，一組是針對(duì) data.x 的，甚至很容易講清楚為什么需要兩對(duì) load-acquire/store-release：
為了讓 thread 2 退出循環(huán)，那么 sc 的第一次讀取操作必須要能看到 thread 1 中第二個(gè) store 操作寫(xiě)進(jìn) sc 的偶數(shù)值。只要確實(shí)看到了，那么 smp_store_release()和 smp_load_acquire()就能保證寫(xiě)入 data 中各個(gè)字段的 store 操作是會(huì)正常讓別人看到的。
如果 thread 2 讀取 data.x 的時(shí)候，讀到了 store 到 data.x 的值，那么 smp_store_release()和 smp_load_acquire() 就確保 thread 2 至少能看到生成數(shù)的第一次改變。因此，thread 2 將會(huì)繼續(xù)循環(huán)，或者如果它也看到了生出數(shù)第二次改變，就會(huì)跟上一條所說(shuō)的一樣拿到確保了一致性的新的 data。
然而，這段代碼有一個(gè) bug! 因?yàn)?writer 在最開(kāi)頭沒(méi)有進(jìn)行獲?。╝cquire）操作，所以對(duì) data.y 的寫(xiě)入操作可能會(huì)在將奇數(shù)值寫(xiě)到 sc 之前完成。（注：文章在 3 月 2 日的更新中指出了這個(gè)問(wèn)題）。對(duì) data 中所有字段使用 load-acquire/store-release 可以避開(kāi)這個(gè)問(wèn)題，但這樣做可能有點(diǎn)過(guò)了。而事實(shí)上，可以有更好的做法。
上一篇文章中講過(guò)，舊的 Linux 代碼可能會(huì)使用 smp_wmb()，后面緊跟著 WRITE_ONCE()，而不是 smp_store_release()。同樣，有時(shí) READ_ONCE() 后面會(huì)跟著使用 smp_rmb()，而不是 smp_load_acquire()。這些 partial barrier 操作會(huì)建立起特定的 happens before 這種先后關(guān)系。具體來(lái)說(shuō)（但這里的介紹不是很正式），smp_wmb() 會(huì)將后續(xù)所有的 relaxed store 都變成釋放（release）操作，而 smp_rmb() 會(huì)將其之前所有的 relaxed load 操作都變成獲?。╝cquire）操作。
我們嘗試來(lái)將這種用法替換到對(duì) data.x 的訪問(wèn)操作中：
先不談 barrier 是如何起作用的，至少這里已經(jīng)可以更加適合用一個(gè)易于使用的 API 來(lái)包裝了。數(shù)據(jù)完全是通過(guò) relaxed atomic load 和 store 來(lái)操作的（盡管在 Linux kernel memory model 中，non-atomic access 也是可以的），barrier 就被隱藏在 seqcount 的 read_seqcount_retry()和 write_seqcount_begin()中了。
上面加入的 barrier 將讀和寫(xiě)操作分成了兩組，這就保證了 seqcount access 是安全的。然而，有兩點(diǎn)需要注意：
首先，barrier 并沒(méi)有在 relaxed access 之間保證訪問(wèn)順序。也就是說(shuō) thread 2 可能會(huì)先看到對(duì) data.y 的改動(dòng)，然后再看到對(duì) data.x 的改動(dòng)。這對(duì) seqcount 來(lái)說(shuō)不是問(wèn)題，因?yàn)閷?duì) sc 進(jìn)行檢查就可以要求 thread 2 來(lái)重新嘗試讀取，避免它只看到部分 store 結(jié)果。
其次，barrier 比 load-acquire 和 store-release 操作要弱一些（weaker）。使用 smp_load_acquire() 進(jìn)行的讀取操作會(huì)確保比在其之后所有 load 和 store 都要早完成，同樣，smp_store_release() 不僅會(huì)確保在它之前的 store 操作之后完成，并且也確保一定會(huì)在之前的 load 操作之后完成。相反，smp_rmb() 只保證了 load 操作之間的順序，而 smp_wmb()只保證了 store 操作之間的順序。然而，load-store 操作的順序很少需要保證，這就是為什么 Linux 開(kāi)發(fā)者長(zhǎng)期以來(lái)只使用 smp_rmb()和 smp_wmb()。
在 seqcounts 這個(gè)例子中，load-store 的順序并沒(méi)有嚴(yán)格要求，因?yàn)?reader 不會(huì)在它自己的 critical section 之內(nèi)對(duì)這個(gè)共享位置進(jìn)行寫(xiě)入操作，因此在 writer 對(duì)生成數(shù)進(jìn)行更新期間并不會(huì)有人在并發(fā)地修改這個(gè)共享位置。這個(gè)推理有點(diǎn)粗糙，但只要代碼簡(jiǎn)單并且完全符合這個(gè)模式的話(huà)，這個(gè)結(jié)論其實(shí)是準(zhǔn)確的。如果 reader 需要對(duì)這個(gè)共享位置進(jìn)行 write 操作，那么只要對(duì)這些寫(xiě)操作再加上一個(gè)其他機(jī)制（不能是 seqcount 了）來(lái)保護(hù)就夠了。
前一段的解釋雖然不太嚴(yán)謹(jǐn)，但是也說(shuō)明了了解那些常見(jiàn)的 lockless 編程模式(programming pattern)的重要性。簡(jiǎn)而言之，這些編程模式能夠在不損失精確性的情況下，幫我們用更粗的粒度來(lái)思考代碼。你可以不用單獨(dú)去分析每一次內(nèi)存訪問(wèn)，而是做出 "data.x 和 data.y 受 seqcount sc 保護(hù) "這樣的論述，或者對(duì)本文中第一個(gè)消息傳遞的例子，可以簡(jiǎn)單得出"a 是被通過(guò)消息傳遞方式發(fā)布給其他線程的"。在某種程度上來(lái)說(shuō)，熟練掌握 lockless 編程模式就意味著能夠得出類(lèi)似這樣的結(jié)論，并利用這些結(jié)論來(lái)理解代碼。
我們對(duì) memory barrier 的初步探討到此結(jié)束。這個(gè)話(huà)題自然還有很多內(nèi)容沒(méi)有講完，本系列的下一期將深入探討完整的 memory barrier，包括它們是如何其效果的、以及它們?cè)趦?nèi)核中是如何使用的。
參考此系列上一篇文章：LWN：介紹lockless算法！
全文完
LWN 文章遵循 CC BY-SA 4.0 許可協(xié)議。
長(zhǎng)按下面二維碼關(guān)注，關(guān)注 LWN 深度文章以及開(kāi)源社區(qū)的各種新近言論～