LWN:為核心繼續改善list遍歷操作!

語言: CN / TW / HK

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

Toward a better list iterator for the kernel

By Jonathan Corbet March 10, 2022 DeepL assisted translation https://lwn.net/Articles/887097/ 

連結串列(linked list)概念很簡單,它們往往在入門級資料結構課程的開始課程內就教過了。因此,要是大家知道核心社群對其長期都在用的連結串列實現感到不太滿意,不僅在尋找解決一些問題的方法,而且一直在努力追求實現更好的解決方案。現在看來,近期就會有一些改動,也就是說:在 30 多年後,核心開發者可能已經找到了一種更好的方法來安全地迭代一個連結串列。

Kernel linked lists

當然,C語言下面建立連結串列相對容易。但是,它並沒有定義和規範好如何建立包含任何型別結構的那種通用連結串列。C 語言的性質適合在每一種需要連結串列的情況下建立一個專用的連結串列,從而也就導致了更多的模板程式碼(boilerplate code)和重複定義。每一個連結串列的實現都必須經過 review 以保證其正確性。如果能有一個可以確認可用的唯一實現,那就最好了,這樣核心開發者就可以更有效地利用他們自己的時間避免在具體領域程式碼之外引入 bug 了。

核心自然有一些關於連結串列的解決方案,但最常用的是 struct list_head:

struct list_head {
  struct list_head *next, *prev;
  };

這個結構可以顯式建立雙向連結串列,類似下面這個樣子:

struct list_head 可以很好地構造出一個連結串列,但有一個明顯的缺點:它不能儲存其他任何資訊。通常,這種資料結構是需要用來把其他一些重要資料串聯起來的,這個 list 結構本身並不是什麼重點。C 語言無法很方便地建立一個可以支援任何形式的 payload 的連結串列,但可以很容易地將結構 list_head 嵌入到開發者希望用連結串列串起來的目標結構中:

這就是在核心中構建連結串列的通常方式。使用 container_of() 這樣的巨集可以把指向 list_head 結構的指標變成指向包含它的結構的指標。使用連結串列的程式碼幾乎總是使用這個巨集(通常是間接呼叫)來獲取對 payload 的訪問指標。

最後還有一個值得注意的細節,list 的實際頭部往往是一個 list_head 結構,並沒有也嵌入到 payload 結構中:

關於這個基礎結構如何使用,有一個現實世界的例子就是 inode 結構,一個 inode 結構就代表了檔案系統中的一個檔案。Inode 可以同時出現在很多 list 中,因此 inode 結構包含了至少五個各不相同的 list_head 結構,不幸的是,編者的製圖水平並不能很好地展示出這個資料結構。其中的一個 list_head 結構名為 i_sb_list,是用來將 inode 與它所屬的檔案系統的 superblock 關聯起來。指向這個列表的 list_head 結構就是 struct super_block 的 s_inodes 欄位。這個例子就是一個沒有嵌入到 inode 結構的的 list_head。

對一個連結串列的遍歷通常就是從這個 list_head 開始,然後跟隨下一個指標跳轉,直到再次找到這個 list_head。當然,我們可以自己寫程式碼來實現遍歷,但是核心也為這個目的提供了許多函式和巨集。其中一個就是 list_for_each_entry(),它將遍歷整個列表,在每個節點都提供一個指向外包結構的指標。使用這個巨集的典型程式碼看起來像這樣:

struct inode *inode;

/* ... */
list_for_each_entry(inode, &sb->s_inodes, i_sb_list) {
  /* Process each inode here */
}
/* Should not use the iterator here */

在迴圈中,該巨集使用 container_of()將 inode 指向每個列表條目的外包 inode 結構。問題是從迴圈中退出時 inode 的值是多少?如果程式碼以 break 語句退出迴圈,inode 將指向當時正在處理的那一項元素。然而,如果完成遍歷整個列表的話,inode 就會是指向那個獨立的列表頭部再使用 container_of() 的結果,但是問題是這個節點並沒有一個外包的 inode 結構。因此核心就可能會出現不確定的行為,導致許多問題。

出於這個原因,像 list_for_each_entry() 這樣的巨集的規則就是,這個迭代變數不應該在迴圈之外使用。如果一個值需要在迴圈之後被訪問,它應該被儲存在一個單獨的變數中,從而才可以在迴圈之後訪問。但這是一條隱含的規則,沒有人覺得有必要在巨集本身的文件中明確指出這個限制。不足為奇的是,這條規則充其量只是一個指導原則,核心中充滿了事實上在迴圈後仍在使用迭代變數的程式碼。

The search for a safer iterator

當我們上次討論這個問題時,Jakob Koschel 已經發布了 patch 來修復其中一部分犯錯的位置,後來他也在繼續這個工作。然而,Linus Torvalds 認為這種改動方法還是不夠的,因為它無法防止未來出現問題:

因此,如果我們的基本規則是 "不要在迴圈結束後使用迴圈迭代變數,因為這種用法可能導致各種微妙的問題",那麼除了修復現有的包含這個問題的程式碼外,我真的希望:a)為未來新加入的這種程式碼要給出一個編譯器警告;b)這種寫法在未來需要確保完全無法正常工作。

因為不這樣的話這個問題今後還會再次發生。

一路走來,開發者們意識到,轉到一個較新版本的 C 標準可能會有幫助,因為它允許在迴圈體內宣告迭代變數(從而使它在迴圈之外不可見)。Torvalds 初步嘗試了一個解決方案,看起來像這樣。

#define list_for_each_entry(pos, head, member)                          \
  for (typeof(pos) __iter = list_first_entry(head, typeof(*pos), member); \
       !list_entry_is_head(__iter, head, member) && (((pos)=__iter),1); \
       __iter = list_next_entry(__iter, member))

這版的巨集仍然接受迭代器變數作為引數,保持與之前相同的原型。這一點很重要,因為在核心程式碼中有成千上萬使用這個巨集的位置。但是它聲明瞭一個新的變數來進行實際的迭代使用,並且只在迴圈裡對傳入的迭代變數進行設定。由於迴圈本身可能永遠不會被執行(比如如果是個空列表),存在著迴圈裡從未設定過這個外面傳入的迭代變數,所以它可能在迴圈之後保持未初始化的狀態。

這個版本很快被第二版所取代,都被稱為了 "a work of art (藝術作品)":

#define list_for_each_entry(pos, head, member)                          \
  for (typeof(pos) pos = list_first_entry(head, typeof(*pos), member);  \
       !list_entry_is_head(pos, head, member);                          \
       pos = list_next_entry(pos, member))

現在,迴圈範圍內的迭代變數被宣告為與外層變數同名,從而將外部變數遮蔽掉(shadowing it)。在這個版本中,外部宣告的迭代變數根本就不會在迴圈中使用。

Torvalds 嘗試這兩種方案時希望,如果在迴圈之外使用(外部)迭代變數,這將會導致編譯器產生警告,因為它不會再允許迴圈體內部初始化。但這並未起到效果;現在程式碼中有些地方明確初始化了迭代變數,而且,無論如何,核心裡面早已經禁用了 "使用未初始化的變數" 這種編譯器警告,因為核心裡有太多關於這個的誤報了。

James Bottomley 提出了一個不同的方法:

#define list_for_each_entry(pos, head, member)                          \
  for (pos = list_first_entry(head, typeof(*pos), member);              \
  !list_entry_is_head(pos, head, member) && ((pos = NULL) == NULL;      \
                                             pos = list_next_entry(pos, member))

這一版會在退出迴圈時明確地將迭代變數設定為 NULL,導致任何會使用它的程式碼應該都會 fail。Torvalds 指出了這個做法有個明顯問題:它改變了一個在整個核心中廣泛使用的巨集的語義,並可能會引入 bug。這也會使開發者在向沒有新語義支援的 stable kernel 核心進行 patch backport 時碰到更多困難。

還有一種方法是由 Xiaomeng Tong 提出的:

#define list_for_each_entry_inside(pos, type, head, member) \
  for (type * pos = list_first_entry(head, type, member);   \
       !list_entry_is_head(pos, head, member);              \
       pos = list_next_entry(pos, member))

Tong 的 patch 建立了一套新的巨集,全新的名字,對現有的程式碼可以逐個慢慢切換到新的用法上。完全不使用外部宣告的迭代變數,相反,迭代變數的名稱和型別被作為引數傳遞進來,並且迭代器被宣告在迴圈本身的範圍內。然而,Torvalds 也不喜歡這種方法。他說,幾乎每一處使用它的地方都會導致冗長的、難以閱讀的程式碼,而且在錯誤的地方導致了痛苦。"他說:"我們應該爭取在 糟糕 的情況下必須做額外的工作,而且哪怕在這些地方我們也應該認真追求可讀性。"

A solution at last?

在拒絕了各種解決方案之後,Torvalds 開始思考一個好的解決方案可能是什麼樣子的。他總結說,這裡的一部分問題是,外包結構的型別與 list_head 結構是分開的,這使得編寫迭代遍歷巨集更加困難。如果這兩種型別能夠以某種方式連線起來,事情就會變得簡單。此後不久,他想出了一個解決方案,實現了這個想法。它首先提供了一個新的巨集:

#define list_traversal_head(type,name,target_member)            \
  union { struct list_head name; type *name##_traversal_type; }

這個巨集會被用來宣告 list 的真正 head,而不是包含在其他結構中的 list_head 項。具體來說,它聲明瞭一個新的 union 型別的變數,包含一個名為 name 的 list_head 結構,以及一個指向了外包結構型別的指標,名為 name_traversal_type。這個指標從未被使用過,它只是將包含結構的型別與 list_head 變數聯絡起來的一種方式。

然後,新增了一個迭代 API:

#define list_traverse(pos, head, member)                                \
  for (typeof(*head##_traversal_type) pos = list_first_entry(head, typeof(*pos), member); \
       !list_entry_is_head(pos, head, member);                          \
       pos = list_next_entry(pos, member))

程式碼可以通過使用 list_traverse()而不再使用 list_for_each_entry() 來遍歷一個列表。迭代變數將是 pos,它只存在於迴圈體內部。列表的第一項作為 head 傳遞進來,而 member 是包含結構中 list_head 結構的名稱。該 patch 包括幾個原有使用位置的修改替換,來告訴人們該如何使用。

Torvalds 認為這就是 "未來的方向"。完成這個改動可能是一個長達數年的專案。在核心中,有超過 15000 個使用了 list_for_each_entry()(包括它的變種)的位置。每一個最終都需要被修改,而且列表頭的宣告位置也必須同時改變。所以這不是一個快速的解決方案,但從長遠來看,它可以使核心中的連結串列實現更加安全。

有人可能會說,所有這些都是由於在核心中繼續使用 C 語言而造成的自找的痛苦。這可能是事實,但目前還是缺乏更好的替代方案。例如,儘管 Rust 語言有很多優點,但對想實現連結串列的人來說用 Rust 也都不是容易的事情,所以轉用這種語言也不會能自動解決這個問題。因此,核心開發者似乎不得不在一段時間內繼續容忍這種要小心謹慎使用的基礎設施。

全文完

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

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

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