LWN: Lockless編程模式 - 介紹compare-and-swap！
關注了就能看到更多這么棒的文章哦～
Lockless patterns: an introduction to compare-and-swap
March 12, 2021
This article was contributed by Paolo Bonzini
Lockless patterns
DeepL assisted translation
https://lwn.net/Articles/847973/
系列文章之一：LWN：介紹lockless算法！
系列文章之二：LWN: lockless編程模式——relaxed acess和partial memory barrier
系列文章之三：LWN: lockless編程模式 - full memory barrier！
在本系列第一篇文章中，我介紹了并發(fā)內存模型（concurrent memory models）背后的理論，以及如何用該理論來解釋普通的加載和存儲操作（load and store）。然而，要想創(chuàng)建更高層的同步原語（比如 spinlock、mutex 和 condition variable），僅靠 load 和 store 分析并不好用。盡管也確實可以利用上次介紹的 full memory-barrier 模式（Dekker 算法）來保持兩個線程的同步，但實際上現代處理器提供了一種更簡單、更通用、更快速的方式（是的，這三方面都有優(yōu)勢）：compare-and-swap 操作。
從 Linux 內核程序員的角度來看，compare-and-swap 原型如下：
T cmpxchg(T *ptr, T old, T new);
其中 T 可以是一個整數類型(不過不能超過指針所占用的空間)，也可以是一個指針類型。為了支持這種多態(tài)性（polymorphism），cmpxchg()被定義為一個宏，而不是一個函數。但編寫這個宏時很小心，以免對其參數進行多次運算。Linux 也有一個 cmpxchg64()宏，采用了 64 位整數作為參數，但它不能保證在所有的 32 位平臺上都可用。
cmpxchg()從 *ptr 指向的位置來 load 數值，如果其它等于 old，則在它的位置存儲 new 這個值；否則就不會進行 store 操作。然后將 load 的值返回回去，無論其是否與 old 值匹配。compare-and-swap 是原子操作：如果進行了 store，那么可以確定其他線程不會偷偷地把除 old 以外的值寫入*ptr。因為它在一個原子操作之內就既讀取了 old 值并且 store 了一個 new 值，所以 compare-and-swap 被稱為是一個 atomic read-modify-write 操作。
在 Linux 中，cmpxchg()宏對前后代碼的執(zhí)行順序提出了要求。一個 compare-and-swap 操作包括一個 load 和和一個 store，在本文中，你可以認為它們分別是 load-acquire 和 store-release 操作。這意味著 cmpxchg()可以與其他線程對同一地址進行的 load-acquire 或 store-release 操作保證同步。
Lock-free stacks and queues
"Lockless algorithms for mere mortals" （LWN：凡人如何理解lockless算法？）一文中已經提到了針對 lock-free list 如何使用 compare-and-swap。在本文中，我們將看到如何在 C 語言中實現一個 lockless（無鎖的）單向鏈表，以及如何使用。然而，首先還是先讓我們回顧一下單線程的 C 程序是如何在一個單向鏈表前面插入一項的：
struct thing {
struct thing *next;
...
};
struct thing *first;
node->next = first;
first = node;
有了本系列第一部分的知識，我們就知道了應該把對 first 的賦值操作變成一個 store-release，這樣對于其他在做 load-acquire 操作的線程來說就可以看到 node-next 的改變了。這里介紹的模式就是一個應用例子。
但是，該模式只對單個生產者和單個消費者的情況有效。在有多個生產者的情況下，這兩條指令必須用一個鎖來保護起來。這是因為在這兩條指令的間隙，有可能 first 的值會被改變，比如此時另一個線程在鏈表中插入了另一個節(jié)點。如果發(fā)生了這種情況，新的節(jié)點中的指向后一個節(jié)點的指針(node->next) 會指向在賦值操作發(fā)生前的 first 的內容。這給我們提了個醒（盡管很明顯）：acquire 和 release 語義只是設計以及證明 lockless 算法正確性的一部分而已。哪怕用了它們，還是有可能發(fā)生邏輯錯誤（logic mistakes）以及 race condition。
cmpxchg()不使用鎖，而是讓我們一上來就能發(fā)現其他線程正在修改這里。下面的代碼，無論有多少個生產者都是安全的：
if (cmpxchg(&first, node->next, node) == node->next)
/* yay! */
else
/* now what? */
如你所見，還是有些東西需要明確決定一下。首先，如果 cmpxchg() 觀察到 first 發(fā)生了變化，該怎么辦。在這種情況下，正確的做法是直接將 first 的新值讀到 node->next，然后再試一次。這種做法可以奏效，是因為對于其他線程來說，它們仍然看不到我們的 node，沒有人會注意到我們剛才撞到了它們正在處理的時機。
第二個更微妙的問題是：我們如何對 first 進行 load？這個 load 操作不需要有 acquire 或 release 的語義，因為代碼中并沒有做其他內存訪問是依賴于 first 值的。另一方面，也許那些進行過度優(yōu)化的編譯器（the big bad optimizing compiler，見 LWN：怕不怕編譯器優(yōu)化讓你的代碼徹底亂套？（完整版））會認為 first 循環(huán)體內都不會發(fā)生改變？盡管 Linux 的 cmpxchg() 確實阻止了這種編譯器優(yōu)化，但更好的做法還是使用 READ_ONCE()和 WRITE_ONCE()來標記這些對共享內存進行 relaxed load 和 store。
補上這些內容之后，代碼變成了這樣：
struct thing *old, *expected;
old = READ_ONCE(first);
do {
node->next = expected = old;
old = cmpxchg(&first, expected, node);
} while (old != expected);
一切都很完美，但我們只完成了一半的工作。咱們仍然沒有討論關于消費者這邊是如何解讀這個鏈表的。答案是，這取決于生產者和消費者之間的關系、消費者的數量、以及消費者是否有興趣按照 LIFO（last-in-first-out）或 FIFO（first-in-first-out）的順序訪問各個節(jié)點。
首先，有可能所有的 read 操作都發(fā)生在生產者完成自己的動作之后。這種情況下，生產者和消費者之間的同步就發(fā)生在對列表進行操作的代碼之外，消費者可以通過正常的、非原子 load 操作來訪問鏈表。比如說，這里的同步機制可以是 thread-exit 和 thread-join，就像我們在第一篇文章中看到的例子一樣。
如果很少進行讀操作，或者是可以分批進行的，那么可以使用一個更巧妙的實現方式，從而讓生產者可以 lockless 地完成工作，而讀操作則是序列化完成的（serialized）?？梢允褂?reader-writer lock(rwlock)來實現。然而，生產者需要使用的是 shared access 要用的鎖(即使用 read_lock()函數)，而消費者則要用 exclusive access 的鎖(使用 write_lock()函數)! 這樣做了之后也能避免讀與寫同時執(zhí)行，從而能讓消費者也可以使用 non-atomic load 操作。我們希望這個例子能夠讓大家理解，即使你堅持使用最常見的 lockless 編程模式，也不會有太多的注釋或太多的文檔。
如果許多消費者會在這些生產者運行時并發(fā)執(zhí)行，并且它們會以任意順序來使用這些節(jié)點，那么消費者可以用一條指令來獲取整批節(jié)點（這里指從列表中刪除）：
my_things = xchg_acquire(&first, NULL);
xchg()像 cmpxchg()一樣，會將對內存位置的讀和寫操作采用原子方式組合起來執(zhí)行。在這種情況下，它會將 list 原來的 head 內容返回，并且將其改成 NULL，從而實現將鏈表清空的目的。這里我使用的是 xchg_acquire()變體，它對 first 進行 load 操作的時候帶有 acquire 語義，但是就像 WRITE_ONCE()一樣，在 store NULL 的時候時并不需要使用 release 語義。Acquire 語義在這里就足夠了，因為基本上這個模式還是第一部分中講到的 store-release 和 load-acquire 模式。更準確地說，它是那個模式擴展為多生產者、多消費者（multi-producer, multi-consumer）之后的樣子。
我們是否需要在寫入這部分邏輯里也做同樣的事情，也就是用 cmpxchg_release()代替 cmpxchg()呢？我們確實可以這么做，原則上來說，writer 需要做的只是將對 node-next 的 store 操作公告給其他人就行了。然而，cmpxchg() 在對 list head 進行 load 操作時的 acquire 語義有一個很有好處的副作用：它會確保每個 writer 與寫入前一個元素的線程的先后順序。在下圖中，load-acquire 和 store-release 操作都是 cmpxchg()一系列成功調用的組成部分：
thread 1: load-acquire first (returns NULL)
store-release node1 into first
\
thread 2: load-acquire first (returns node1)
store-release node2 into first
\
thread 3: load-acquire first (returns node2)
store-release node3 into first
\
thread 4: xchg-acquire first (returns node3)
thread 3 的 cmpxchg() 是唯一一個確保與 thread 4 的 xchg_acquire()同步的。然而，由于傳遞性，所有的 cmpxchg()都會在 xchg_acquire()之前發(fā)生。因此，如果在 writer 中使用了 cmpxchg()，那么 reader 就可以用普通的 load 操作來遍歷列表了。
反之，如果這些 writer 都使用了 cmpxchg_release()，那么先后關系就會變成這樣：
thread 1: load-acquire first (returns NULL)
store-release node1 into first
thread 2: load first (returns node1)
store-release node2 into first
thread 3: load first (returns node2)
store-release node3 into first
\
thread 4: xchg-acquire first (returns node3)
thread 4 總是會從 node3->next 中讀取到 node2，因為讀到的 first 值是 thread 3 寫入的。然而，從 thread 1 和 thread 2 到 thread 4 之間并沒有先后順序的保證，因此，thread 4 需要一個 smp_load_acquire()才能確保看到 node2->next 中的值為 node1。
上面介紹的數據結構已經在 Linux 的 linux/llist.h 頭文件中實現了。當然，我們強烈建議各位不要自己重新發(fā)明輪子，可以直接使用這個實現好的版本。事實上該 API 還包含了兩個有趣的函數：llist_del_first()和 llist_reverse_order()。
llist_del_first() 會把 llist 的第一個元素返回回來，并將 header 指針移動到指向第二個元素。它的文檔中有警告說，只有在僅有一個 reader 的情況下才可以使用這個函數。相反，如果有兩個消費者，那么在經過一系列復雜的添加和刪除操作之后，就可能導致所謂的 ABA 問題。由于本文堅定地立足于 "如果有些解釋過于復雜了，就不做解釋了" 的原則，所以這里就不再進行詳細的解釋了。不過值得指出，它與之前的 rwlock 例子有相似之處。在這個情況下，多個消費者需要使用 lock 機制來確保對數據結構的并發(fā)訪問保持順序執(zhí)行。而 llist_del_first() 則讓 writer 在調用 llist_add()時完全不需要獲取 lock，而這些 reader 則可以使用 spinlock 或 mutex。
llist_del_first()為 llist 實現了 LIFO 的語義。然而，如果你的應用程序需要 FIFO 順序，你可以使用一個很有用的技巧，這就是 llist_reverse_order()發(fā)揮價值的地方了。用 xchg()刪除一批項目（就像用 llist_del_all()做的那樣）確實可以將數據批量按照 FIFO 順序提供出來，只是每一批數據中的節(jié)點是從后到前排序的。于是我們可以使用下面的算法：
struct thing *first, *current_batch;
if (current_batch == NULL) {
current_batch = xchg_acquire(&first, NULL);
... reverse the order of the nodes in current_batch ...
}
node = current_batch;
current_batch = current_batch->next;
每執(zhí)行一次這組偽代碼，就會按照 FIFO 順序來返回鏈表中的一個元素。這也是一個單消費者數據結構（single-consumer data structure），因為它假設在任意時刻都只有一個線程在訪問 current_batch。如何將偽代碼轉換為 llist API，就留給讀者去練習了。
這一期的內容就到此為止。本系列的下一篇文章將繼續(xù)探討 read-modify-write 操作、如何利用 compare-and-swap 來構建這些操作、以及如何利用它們來加速引用計數操作。
全文完
參考資料：
長按下面二維碼關注，關注 LWN 深度文章以及開源社區(qū)的各種新近言論～