LWN：介紹lockless算法！
Loading [Contrib]/a11y/accessibility-menu.js
關(guān)注了就能看到更多這么棒的文章哦～
An introduction to lockless algorithms
February 19, 2021
This article was contributed by Paolo Bonzini
DeepL assisted translation
https://lwn.net/Articles/844224/
Linux kernel 里面有些場(chǎng)景無(wú)法使用普通的 locking primitives（互斥鎖接口），或者擔(dān)心這些互斥鎖帶來(lái)的性能影響，這種時(shí)候就可以考慮 lockless algorithm 了，也就是無(wú)鎖算法。因此 lockless 會(huì)時(shí)不時(shí)地出現(xiàn)在 LWN 上。最后一次被提及是在去年 7 月，也因此促使我撰寫(xiě)了這一系列文章。而更加頻繁被提到的話題則是 read-copy-update（也就是 RCU，2007 年就有好多 LWN 文章介紹了）、引用計(jì)數(shù)（reference counting）、以及各種將 lockess primitives 包裝成更高級(jí)別更容易理解的 API 的方法。這些文章會(huì)深入探討 lockless 算法背后的概念，以及如何在內(nèi)核中使用。
關(guān)于 memory model 的底層知識(shí)是大家公認(rèn)的進(jìn)階內(nèi)容了，即使是最老練的內(nèi)核開(kāi)發(fā)者也會(huì)感到發(fā)憷。編者在 7 月份的文章中寫(xiě)到，"需要一種特殊的大腦才能真正理解 memory model"。有人說(shuō)，Linux 內(nèi)核的內(nèi)存模型（尤其是 Documentation/memory-barriers.txt）可以用來(lái)嚇唬小孩子，光是 "acquire"（獲?。┖?"release"（釋放）這兩個(gè)詞就讓人很頭痛了。
同時(shí)，像 RCU 和 seqlocks 這樣的機(jī)制在內(nèi)核中被廣泛使用，幾乎每個(gè)開(kāi)發(fā)者遲早都會(huì)遇到基本的 lockless 編程接口。出于這個(gè)原因，大家最好至少讓自己對(duì) lockless 的基本函數(shù)有個(gè)簡(jiǎn)單的了解。在本系列中，我將解釋 acquire 和 release 的真正含義，并介紹五種相對(duì)簡(jiǎn)單的模式，它們可以涵蓋 lockless 接口在大多數(shù)場(chǎng)景下的應(yīng)用。
Acquire, release, and "happens before"
為了從相對(duì)來(lái)說(shuō)簡(jiǎn)單易懂的同步接口（synchronization primitives）轉(zhuǎn)向 lockless 編程方式，我們首先要了解為什么加鎖會(huì)是有必要的。通常，談到鎖的價(jià)值的時(shí)候，一般都是在講互斥的情況（mutual exclusive）：加鎖可以防止多個(gè)同時(shí)執(zhí)行的線程對(duì)同一個(gè)數(shù)據(jù)進(jìn)行并發(fā)地讀或?qū)懖僮?。?"concurrently（并發(fā)）"到底是什么意思呢？當(dāng)線程 T 處理完某個(gè)數(shù)據(jù)之后，線程 U 開(kāi)始使用該數(shù)據(jù)，這有什么問(wèn)題嗎？
為了回答這些問(wèn)題，Leslie Lamport 在 1978 年的論文 "時(shí)間、時(shí)鐘和分布式系統(tǒng)中的事件排序（Time, Clocks and the Ordering of Events in a Distributed System" 中建立的一個(gè)理論框架就有用武之地了。根據(jù)該論文，分布式系統(tǒng)中的事件(event) 的順序可以根據(jù)一個(gè)事件 P 是否發(fā)生在另一個(gè)事件 Q 之前定義：
同一個(gè)線程內(nèi)的事件都是按順序發(fā)生的，也稱之為"total ordering(完全順序)"。通俗地講，對(duì)于同一線程的任意兩個(gè)事件，你總能說(shuō)出哪個(gè)先發(fā)生，哪個(gè)后發(fā)生。
如果兩個(gè)時(shí)間不是在同一個(gè)線程內(nèi)的，那么如果事件 P 是在做 message send，而事件 Q 是與之相對(duì)應(yīng)的 message receive，那么事件 P 就一定發(fā)生在事件 Q 之前。
這種關(guān)系是具有傳遞性的。因此，如果事件 P 發(fā)生在事件 Q 之前，而事件 Q 發(fā)生在事件 R 之前，那么事件 P 也會(huì)發(fā)生在 R 之前。
"在其之前發(fā)生" （happen before）的這種關(guān)系是 partial ordering（不完全順序），也就是說(shuō)有可能有兩個(gè)事件 P 和 Q，我們無(wú)法判斷這兩個(gè)事件是誰(shuí)先誰(shuí)后的。當(dāng)這種情況發(fā)生時(shí)，就意味著這兩個(gè)事件是 concurrent 的(并發(fā)的)。還記得加鎖是如何預(yù)防對(duì)同一數(shù)據(jù)結(jié)構(gòu)的并發(fā)訪問(wèn)嗎？這是因?yàn)?，?dāng)你用鎖保護(hù)一個(gè)數(shù)據(jù)結(jié)構(gòu)時(shí)，所有對(duì)該數(shù)據(jù)結(jié)構(gòu)的訪問(wèn)都會(huì)形成一個(gè) total ordering（完全順序關(guān)系），就像它們都是來(lái)自同一個(gè)線程的操作一樣。Lamport 的論文還提供了一個(gè)基本概念，即當(dāng)鎖被從一個(gè)線程交給另一個(gè)線程時(shí)會(huì)發(fā)生什么：會(huì)有一些 "message passing" 機(jī)制來(lái)確保線程 T 的 unlock 操作是發(fā)生在線程 U 的 lock 操作之前的。
事實(shí)證明，這種說(shuō)法并不僅僅是一個(gè)理論而已：CPU 為了確保它們的 cache 一致性，會(huì)需要通過(guò)總線（如 Intel 的 QPI 或 AMD 的 HyperTransport）來(lái)傳遞 message。然而，本文中我們不需要深入到這些細(xì)節(jié)中。所以，我們這里將 "happen before" 的定義推廣為所有同步原語(yǔ)（synchronization primitive）的一個(gè)公共定義。
Lamport 的基本觀點(diǎn)是，當(dāng)兩個(gè)線程對(duì)同一數(shù)據(jù)結(jié)構(gòu)進(jìn)行對(duì)稱操作時(shí)，就需要 synchronization。在我們推廣之后的說(shuō)明中，我們會(huì)列舉出那些使一個(gè)線程與另一個(gè)線程 synchronize(同步)的配對(duì)操作（例如通過(guò)同一個(gè)隊(duì)列來(lái)發(fā)送和接收消息）。此外，我們將把每一對(duì)操作中都分為 release（釋放）或 acquire（獲?。﹥蓚€(gè)操作。也就是說(shuō)我們后面只會(huì)用"釋放了"或者"獲取了"這種語(yǔ)義來(lái)說(shuō)明。
在每一對(duì)操作內(nèi)，具有釋放語(yǔ)義的操作與相應(yīng)的獲取語(yǔ)義操作是同步操作。"同步(synchronizing) "意味著每當(dāng)一個(gè)線程內(nèi)執(zhí)行釋放操作、另一個(gè)線程執(zhí)行相應(yīng)的獲取操作時(shí)，就表示這個(gè)進(jìn)行釋放的線程是發(fā)生在獲取線程之前的。"happen before" 一般來(lái)說(shuō)仍然是一個(gè)不完全順序關(guān)系（partial order），但現(xiàn)在它可以跨越兩個(gè)線程了，甚至是更多線程，這要?dú)w功于傳遞性。更正式的說(shuō)法是：
在單個(gè)線程中，各個(gè)操作都是完全順序的（total ordering）
如果一個(gè)進(jìn)行釋放動(dòng)作的操作 P 與一個(gè)進(jìn)行獲取動(dòng)作的操作 Q 是同步的（synchronized），就意味著操作 P 發(fā)生在操作 Q 之前，哪怕這兩個(gè)操作是發(fā)生在不同的線程中的。
像之前一樣，這個(gè)關(guān)系是具有傳遞性的，也具有 partial ordering 的特性
按照舊的定義，message send 是屬于釋放操作，而 message receive 屬于獲取操作。message send 和 message receive 就使得發(fā)送消息的線程與接收消息的線程（或多個(gè)接收線程）實(shí)現(xiàn)了同步。我們也可以根據(jù)新定義來(lái)重新解釋我們之前的觀點(diǎn)：為了讓鎖有效果，unlock 操作就是釋放操作，并且必須與 lock 操作進(jìn)行同步，加鎖操作就是獲取操作。無(wú)論是否有人競(jìng)爭(zhēng)這把鎖，最終結(jié)果都保證了一個(gè) thread 和另一個(gè) thread 中的操作有了"happen before"的關(guān)系。
獲取操作和釋放操作似乎是一個(gè)抽象的概念，但它們確實(shí)為許多常見(jiàn)的多線程編程實(shí)例進(jìn)行了簡(jiǎn)單的解釋。例如，如果有兩個(gè)用戶空間線程都需要訪問(wèn)一個(gè)全局變量 s：
thread 1 thread 2
-------------------------------- ------------------------
s = "hello";
pthread_create(&t, NULL, t2, NULL);
puts(s);
s = "world";
pthread_join(t, NULL);
puts(s);
那么這里對(duì)變量的訪問(wèn)是否安全？是否能確定 thread 2 從 s 中讀出的內(nèi)容是 "hello"，并且 thread 1 在 pthread_join()后輸出的 s 的值一定為 "world"？答案是可以確定，下面我們用獲取和釋放的語(yǔ)義來(lái)解釋原因：
pthread_create() 具有釋放的語(yǔ)義，并與 thread 2（具有獲取語(yǔ)義）的 start（即線程開(kāi)始執(zhí)行）有同步關(guān)系。因此，在線程創(chuàng)建之前所寫(xiě)的任何數(shù)據(jù)都可以安全地從線程中訪問(wèn)到。
thread 2 的 exit 操作具有釋放語(yǔ)義，并與 pthread_join() （其具有獲取語(yǔ)義）有同步關(guān)系。因此，線程在退出之前寫(xiě)的任何東西都可以在 pthread_join()之后安全地訪問(wèn)到。
請(qǐng)注意，這里成功地在不用 lock 的情況下將數(shù)據(jù)從一個(gè)線程可靠地傳遞到了另一個(gè)線程。恭喜，你已經(jīng)完成了 lockless 編程的第一個(gè)例子?？偨Y(jié)一下：
如果程序作者想讓 thread 2 "看到 " thread 1 到目前為止發(fā)生的所有事情的效果，那么兩個(gè)線程需要相互同步，也就是需要在 thread 1 中進(jìn)行釋放操作，在 thread 2 中進(jìn)行獲取操作。
只要知道哪些 API 提供了 acquire/release 語(yǔ)義，就可以利用這些 API 來(lái)寫(xiě)出確保 order 的代碼。
在了解了釋放和獲取語(yǔ)義對(duì)這種 high-level synchronization primitive （高層次的同步原語(yǔ)）是如何起作用之后，我們現(xiàn)在可以再看一下對(duì)同一個(gè)內(nèi)存數(shù)據(jù)訪問(wèn)中可以如何利用它們了。
The message-passing pattern
在前一段中，我們已經(jīng)看到了 pthread_create()和 pthread_join()的獲取和釋放語(yǔ)義是如何讓線程的創(chuàng)建者與該線程進(jìn)行信息交換的，以及如何反向傳遞信息?，F(xiàn)在，我們將看到在線程運(yùn)行過(guò)程中如何采用 lockless 方式進(jìn)行同步。
如果傳遞的 message 只是一個(gè)簡(jiǎn)單的標(biāo)量值，例如就是一個(gè)布爾值，那么可以通過(guò)對(duì)這個(gè)內(nèi)存地址進(jìn)行讀寫(xiě)就訪問(wèn)到了。然而，如果消息是一個(gè)指針會(huì)怎樣呢？
thread 1 thread 2
-------------------------------- ------------------------
a.x = 1;
message = &a; datum = message;
if (datum != NULL)
printk("%d\n", datum->x);
最初這個(gè) message 是 NULL 的話，那么我們不清楚 thread 2 打印出來(lái)的是 NULL 還是 &a。問(wèn)題是，哪怕這里 “datum = message” 操作讀到的是 &a，這個(gè)賦值操作其實(shí)與 thread 1 中的賦值操作“message = &a ”并無(wú)同步關(guān)系。因此，這兩個(gè)線程并沒(méi)有一個(gè)"happens before"的關(guān)系。
a.x = 1; datum = message;
| |
| happens before |
v v
message = &a; datum->x
因?yàn)檫@兩個(gè)線程的執(zhí)行并沒(méi)有同步關(guān)系，所以不能保證 datum->x 讀出來(lái)的值肯定是 1，畢竟我們不知道對(duì) a.x 的賦值是否發(fā)生在讀取 datum->x 之前。要確保 datum-> 讀出來(lái)的值必定是 1 的話，就需要讓 store 和 load 操作擁有釋放和獲取的語(yǔ)義。
為此，我們定義了 "store-release" 和 "load-acquire" 這兩種操作。store-release 操作 （取名為操作 P）除了會(huì)向內(nèi)存位置寫(xiě)入數(shù)據(jù)之外，也能確保與采用 load-acquire 方式讀取這個(gè)內(nèi)存數(shù)據(jù)的操作（名為操作 Q）是互相同步的。因此我們可以使用 Linux 的 smp_store_release()和 smp_load_acquire()來(lái)修復(fù)上述代碼：
thread 1 thread 2
-------------------------------- ------------------------
a.x = 1;
smp_store_release(&message, &a); datum = smp_load_acquire(&message);
if (datum != NULL)
printk("%x\n", datum->x);
這樣改動(dòng)之后，如果 datum 是 &a，就一定可以確認(rèn) store 發(fā)生在 load 之前。(為了簡(jiǎn)單起見(jiàn)，我假設(shè)只有一個(gè)線程可以將 &a 寫(xiě)入 message。我們所說(shuō)的 "thread 2 讀取 thread 1 所寫(xiě)的值 "并不是指具體的那個(gè)數(shù)據(jù)進(jìn)入了內(nèi)存，它的真正意思是 thread 1 的 store 操作是可以影響到 thread 2 的所有操作中的最后一個(gè)），這樣一來(lái)就形成了下面的順序關(guān)系：
a.x = 1;
|
v
smp_store_release(&message, &a); -----> datum = smp_load_acquire(&message);
|
v
datum->x
這樣一來(lái)就一切可控了。由于可傳遞性的效果，每當(dāng) thread 2 讀取 thread 1 寫(xiě)入的值時(shí)，thread 1 在 store-release 之前所做的一切操作在 load-acquire 操作之后對(duì) thread 2 也全部都是可見(jiàn)的。需要注意的是，與 pthread_join()的情況不同，這里說(shuō)的"synchronize with" 的說(shuō)法并不意味著 thread 2 在 "等待" thread 1 完成寫(xiě)入操作。上面這幅順序圖中的情況其實(shí)只是 thread 2 恰好讀到了 thread 1 寫(xiě)入值的情況。
在 Linux 內(nèi)核中，上述代碼的編寫(xiě)方式一般會(huì)有點(diǎn)不一樣：
thread 1 thread 2
-------------------------------- ------------------------
a.x = 1;
smp_wmb();
WRITE_ONCE(message, &a); datum = READ_ONCE(message);
smp_rmb();
if (datum != NULL)
printk("%x\n", datum->x);
在這種寫(xiě)法下，釋放和獲取語(yǔ)義是由兩個(gè) memory barrier 操作 smp_wmb()和 smp_rmb() 所提供的。memory barrier 也有獲取和釋放的語(yǔ)義，但它們比簡(jiǎn)單的 load 和 store 操作更復(fù)雜一些。等我們今后介紹 seqlocks 時(shí)會(huì)再講講它們。
不管是 load-acquire/store-release 還是 smp_rmb()/smp_wmb()，都是非常常見(jiàn)的寫(xiě)法，大家需要確保理解。如下這些地方都用到了這些方式：
各種 ring buffer 方案。ring buffer 中每一項(xiàng)往往都指向其他的數(shù)據(jù)，一般來(lái)說(shuō)還會(huì)有一些 head/tail 的信息都是指向 ring buffer 中某個(gè)位置的索引。給 ring buffer 填數(shù)據(jù)的一方（producer）會(huì)使用 store-release 操作，這樣就能與 consumer（讀取 ring buffer 中的數(shù)據(jù)的一方）確保同步。
RCU。在 compiler 看來(lái)，我們熟悉的 rcu_dereference() 和 rcu_assign_pointer() API 跟 load-acquire 和 store-release 操作是一個(gè)效果。得益于除了 Alpha 以外的其他處理器中都具有的一些特性，rcu_dereference() 就可以被直接編譯成普通的 load 操作，此時(shí) rcu_assign_pointer() 仍然跟 rcu_dereference()操作是確保同步的，就好像它還是一個(gè) load-acquire 操作一樣。
將指針寫(xiě)入數(shù)組時(shí)。在下面的 KVM 代碼中（當(dāng)然是簡(jiǎn)寫(xiě)過(guò)的），如果 kvm_get_vcpu()可能看到 kvm->online_vcpus 增長(zhǎng)過(guò)了，那么數(shù)組中與之關(guān)聯(lián)的哪一項(xiàng)就一定是有效的。
kvm_vm_ioctl_create_vcpu() kvm_get_vcpu()
----------------------------------------- -----------------------------------------------
kvm->vcpus[kvm->online_vcpus] = vcpu; if (idx < smp_load_acquire(&kvm->online_vcpus))
smp_store_release(&kvm->online_vcpus, return kvm->vcpus[idx];
kvm->online_vcpus + 1); return NULL;除了 load-acquire/store-release 操作機(jī)制外，message-passing 模式中還有一點(diǎn)值得注意：它是一種只有單個(gè) producer（生產(chǎn)者）的算法。如果有多個(gè) writer 的話，就必須通過(guò)其他手段（比如用 mutex）來(lái)進(jìn)行互斥保護(hù)。lockless 算法并不是一個(gè)無(wú)法跟其他工具配合的東西，它們是并發(fā)編程工具(concurrent programming toolbox) 的一部分，當(dāng)它們與其他傳統(tǒng)工具結(jié)合時(shí)效果最好。
本文只是關(guān)于 lockless 算法的擴(kuò)展介紹系列文章的開(kāi)始。下一期將進(jìn)一步探討如何確保 atomic memory operation 的順序的，并探討 memory barrier 如何成為 "seqcounts "和 Linux scheduler 的核心機(jī)制。
全文完
LWN 文章遵循 CC BY-SA 4.0 許可協(xié)議。
長(zhǎng)按下面二維碼關(guān)注，關(guān)注 LWN 深度文章以及開(kāi)源社區(qū)的各種新近言論～