LWN: 要用volatile_if() 來保護control dependency嗎?

語言: CN / TW / HK

關注了就能看到更多這麼棒的文章哦~

Protecting control dependencies with volatile_if()

By Jonathan Corbet June 18, 2021 DeepL assisted translation https://lwn.net/Articles/860037/ 

正如 Linus Torvalds 最近所說,記憶體排序問題(memory ordering issue)是 "the rocket science of CS"。理解 memory ordering 對於編寫易於擴充套件的程式碼來說越來越有必要了,所以核心開發者經常發現自己不得不成為火箭科學家(來研究 memory ordering)。與 control dependency 相關的情況則更是一種特別棘手的問題。最近的關於如何讓 control dependency 能強制實現的討論就展示了這個領域所出現的各種困難。

Control dependencies

C 語言是在簡單的單處理器計算機時代設計出來的。當時某個開發者寫了一系列的 C 語句之後,他們可以確定這些語句會按照寫出來的先後順序來執行。但幾十年後,情況變得更加複雜了,程式碼很可能被編譯器和 CPU 進行了改頭換面的優化,執行的程式碼與最初寫的程式碼幾乎沒有相似之處。如果編譯器(或處理器)認為對程式碼調整順序之後執行的結果是等效的,那麼它就會可能會對程式碼進行 reorder(重新排序),甚至刪除一些程式碼。這種 reorder 對單執行緒程式碼的影響(在沒有出現錯誤的情況下)僅僅是會使其執行得更快。不過,當有多個執行緒同時執行時就可能會有意外情況了。其中一個執行緒觀察到的多個事件的發生順序,可能會與其他執行緒所看到的並不相同,這可能會導致各種混亂。

在必須要保證多個處理器上看到各個操作的順序時,開發人員通常會使用 barrier 來確保 reorder 動作並不會導致錯誤。然而,在有些情況下,開發者可以假設事件的發生順序會是正確的,因為完全不可能會出錯,這些情況就是通常所說的 "dependency"。總共有三類 dependency(依賴關係),在 LWN 最近發表的 lockless pattern 系列文章中有過介紹。例如,下面就是一個簡單的 data dependency(資料依賴關係):

int x = READ_ONCE(a);
WRITE_ONCE(b, x + 1);

這裡,無論怎麼進行 reorder,都不可能在對 a 進行 read 操作之前完成對 b 的寫入操作,因為編譯器和 CPU 都還不知道應該寫入什麼數值。write 進去的資料完全依賴於前面 read 的結果,這種 dependency 關係會阻止這兩個操作被 reorder。當然,這要隱含一個假設,就是編譯器不認為它已經知道 a 的值是什麼,也就是它之前一定沒有讀取過這個 a,這就是為什麼這裡要使用 READ_ONCE()。lockless patterns 系列文章的第二篇就詳細介紹了 READ_ONCE()和 WRITE_ONCE()。

control dependency 則要複雜一些。例如下面這樣的程式碼:

if (READ_ONCE(a))
  WRITE_ONCE(b, 1);

對 a 的 read 操作和對 b 的 write 操作之間沒有 data dependency,但只有當 a 的值為非零時才會進行後面的 write 操作,因此對 a 的 read 操作必定是發生在 write 之前。這種由條件分支(conditional branch)所確保的順序關係就是 control dependency。一般來說,要建立 control dependency 的話,必須滿足三個條件:

  • 先對某個位置(上面的例子中的 a)進行讀取

  • 根據讀出的值來決策後續程式碼分支(conditional branch)

  • 在一個或多個程式碼分支中會對另一個地址進行 write 操作

當滿足這些條件時,這裡的先讀後寫就是一個 control dependency,這兩個操作之間就不會進行 reorder。

The evil optimizing compiler

如果事情能這樣發展就好了。問題是,雖然硬體是這樣工作的,但 C 語言本身卻並不認可 control dependency,或者說,正如著名的 memory-barriers.txt 這個文件所說:"編譯器並不理解 control dependency。因此,需要開發者來確保編譯器不會破壞你的程式碼"。雖然歷史上似乎沒有出現很多次對有 control dependency 關係的程式碼進行了過度優化而導致程式碼出錯的情況,但這仍是開發者會感到擔心的事情。因此,Peter Zijlstra 提出了一個叫做 volatile_if()的機制。

這個機制試圖解決什麼樣的問題呢?以 Paul McKenney 在討論中提供的一段程式碼為例:

if (READ_ONCE(A)) {
    WRITE_ONCE(B, 1);
    do_something();
} else {
    WRITE_ONCE(B, 1);
    do_something_else();
}

這段程式碼中,對 A 的 read 和對 B 的 write 之間有一個 control dependency 關係,而在條件語句的每一個分支中都有這個寫入操作,雖然它們寫入的值是相同的,但並不應該影響 control dependency 的存在。因此人們可能會認為,這裡的 read 和 write 操作不可能被 reorder。但是實際上編譯器很可能會對程式碼進行 reorder,使其看起來像下面這樣:

tmp = READ_ONCE(A);
WRITE_ONCE(B, 1);
if (tmp)
    do_something();
else
    do_something_else();

這段程式碼看起來跟上面的程式碼效果相同,但是實際上對從 A 讀出的值進行判斷的操作就不再發生在對 B 的 write 操作之前。這就打破了 control dependency,如果某個 CPU 格外積極,它就可能會把 write 操作移到 read 之前,從而產生一個微妙的錯誤。

由於 C 語言不能識別 control dependency,因此很難避免這種錯誤,哪怕連開發者都能意識到這個問題的情況下。一個確定的解決方案就是用 acquire 語義來對 A 進行 read 操作,用 release 語義來對 B 進行 write 操作,正如 lockless patterns 系列文章中所說,但 acquire 和 release 操作在某些體系架構上開銷可能會很大。其實很多情況下並不需要付出這個代價。

volatile_if()

Zijlstra 在他的提議中指出,一個好的解決方案是在 if 語句中新增一個限定詞,表明這裡存在一個依賴關係:

volatile if (READ_ONCE(A)) {
    /* ... */

編譯器就會根據這個提示,來確保生成一個 conditional branch,並確保 branch 內部的程式碼不會被移出來到 branch 之外。然而,這需要編譯器開發者的配合。正如 Segher Boessenkool 所指出的,除非 C 語言的標準委員會同意了在語句(statement)上加上 volatile 這樣的限定符,否則這不可能實現。既然做不到,那麼 Zijlstra 就提出了一個神奇的巨集:

volatile_if(condition) {
    /* true case */
} else {
    /* false case */
}

他提供了若干體系架構上的具體實現,通常依賴手寫的彙編程式碼來寫出所需的 conditional branch 指令,從而讓 CPU 能看到這個 control dependency。

後續討論主要集中在兩個話題上:volatile_if()的實現細節,以及它是否真的有價值。在實現細節方面,Torvalds 提出了一個更簡單的方法:

#define barrier_true() ({ barrier(); 1; })
#define volatile_if(x) if ((x) && barrier_true())

barrier() 這個巨集不會生成任何指令,它只是一個空語句,會作為彙編程式碼送給編譯器。Torvalds 說,這樣做也會命令編譯器生成 conditional branch,因為它只能在 branch 的 "true" 的這個分支裡被呼叫。但事實證明這裡並不那麼簡單,需要按照 Jakub Jelinek 建議的思路重新定義 barrier() 之後,才能使這個方案真正起到效果。

但是 Torvalds 也想知道為什麼開發人員需要開始擔心這個問題,因為他認為這個問題不會在實際程式碼中表現出來:

再說一遍,語義(semantics)確實很重要,我不認為編譯器會真的破壞我們的這個基本假設:"根據最基本的因果關係,哪怕沒有 memory barrier,load->conditional->store 也是能保證最基本的順序的",因為你不能隨意生成會被別人看到的預測性地(speculative)store 操作。

而且,事實上,這種問題就算實際發生了,也是很難找到證據的。他後來確實看到了一個可能真的存在的問題(https://lwn.net/ml/linux-kernel/[email protected]om/),但他仍明確表示他認為現在核心中沒有任何程式碼會受此影響。

討論(最終)結束了,對於是否需要 volatile_if() 並沒有得出任何最終結論。經驗告訴我們,對編譯器的優化保持警惕,這通常是個好主意。即使現在並不會對 mainline 合入一個能夠明確標記出 control dependency 的機制,當未來的編譯器版本(如果)產生問題的時候,這個機制也會是一個備用手段。

全文完

LWN 文章遵循 CC BY-SA 4.0 許可協議。

歡迎分享、轉載及基於現有協議再創作~

長按下面二維碼關注,關注 LWN 深度文章以及開源社群的各種新近言論~