健壯的 Futex ABI

作者:

由 Paul Jackson <pj@sgi.com> 發起

Robust_futexes 提供了一種機制，除了正常的 futexes 之外，還用於在任務退出時核心輔助清理持有的鎖。

關於執行緒持有哪些 futexes 的有趣資料儲存在使用者空間的一個連結串列中，在獲取和釋放鎖時可以有效地更新該連結串列，而無需核心干預。 除了 futexes 之外，robust_futexes 所需的唯一額外核心干預是

  1. 每個執行緒一次性呼叫，告訴核心其持有的 robust_futexes 列表的起始位置，以及

  2. 在退出時，內部核心程式碼處理正在退出的執行緒持有的任何列出的鎖。

現有的普通 futexes 已經提供了一種“快速使用者空間鎖定”機制，該機制無需系統呼叫即可處理無競爭鎖定，並透過在核心中維護等待執行緒的列表來處理有競爭鎖定。 sys_futex(2) 系統呼叫上的選項支援等待特定的 futex，以及喚醒特定 futex 上的下一個等待者。

為了使 robust_futexes 工作，使用者程式碼（通常在與應用程式連結的 glibc 等庫中）必須完全按照核心期望的方式管理和放置必要的列表元素。 如果它未能做到這一點，那麼未正確列出的鎖將不會在退出時被清理，可能會導致死鎖或等待相同鎖的其他執行緒的其他此類故障。

預計可能使用 robust_futexes 的執行緒應首先發出系統呼叫

asmlinkage long
sys_set_robust_list(struct robust_list_head __user *head, size_t len);

指標 “head” 指向執行緒地址空間中的一個結構，該結構由三個字組成。在 32 位架構上，每個字都是 32 位，在 64 位架構上，每個字都是 64 位，並且是本地位元組序。 每個執行緒都應該有自己的執行緒私有 “head”。

如果一個執行緒在 64 位原生架構核心上以 32 位相容模式執行，那麼它實際上可以有兩個這樣的結構 - 一個使用 32 位字用於 32 位相容模式，另一個使用 64 位字用於 64 位原生模式。 如果核心是支援 32 位相容模式的 64 位核心，那麼如果已發出相應的 sys_set_robust_list() 呼叫來設定該列表，它將嘗試在每個任務退出時處理兩個列表。

“head” 處的記憶體結構中的第一個字包含指向 “鎖條目” 的單鏈表的指標，每個鎖一個，如下所述。 如果列表為空，則指標將指向自身，即 “head”。 最後一個 “鎖條目” 指回 “head”。

第二個字，稱為 “offset”，指定從相關的 “鎖條目” 的地址到 “鎖字” 的偏移量，加或減。“鎖字” 始終是一個 32 位字，這與其他字不同。“鎖字” 在高 2 位中儲存 2 個標誌位，在低 30 位中儲存持有鎖的執行緒的執行緒 ID (TID)。 有關標誌位的說明，請參見下文。

第三個字，稱為 “list_op_pending”，在列表插入和刪除期間包含 “鎖條目” 地址的瞬態副本，並且需要正確解決執行緒在鎖定或解鎖操作中間退出時可能出現的競爭。

從 “head” 開始的單鏈表上的每個 “鎖條目” 僅由一個字組成，該字指向下一個 “鎖條目”，如果沒有更多條目，則指回 “head”。 此外，在每個 “鎖條目” 附近，在 “offset” 字指定的距 “鎖條目” 的偏移量處，是一個 “鎖字”。

“鎖字” 始終是 32 位，旨在成為 futex 機制使用的相同的 32 位鎖變數，與 robust_futexes 結合使用。 只有下一個執行緒使用 futex 機制向核心註冊了該 “鎖字” 的地址，核心才能線上程退出時喚醒等待鎖的下一個執行緒。

對於執行緒當前持有的每個 futex 鎖，如果它希望對此鎖的退出清理提供 robust_futex 支援，則它應該在此列表上有一個 “鎖條目”，其關聯的 “鎖字” 位於指定的 “offset” 處。 如果一個執行緒在持有任何此類鎖時死亡，核心將遍歷此列表，使用一個指示其持有者死亡的位來標記任何此類鎖，並使用 futex 機制喚醒等待該鎖的下一個執行緒。

當一個執行緒呼叫上述系統呼叫以表明它期望使用 robust_futexes 時，核心會儲存該任務傳入的 “head” 指標。 該任務可以透過使用系統呼叫稍後檢索該值

asmlinkage long
sys_get_robust_list(int pid, struct robust_list_head __user **head_ptr,
                    size_t __user *len_ptr);

預計執行緒將使用嵌入到更大的使用者級別鎖定結構中的 robust_futexes，每個鎖一個。 核心 robust_futex 機制並不關心該結構中還有什麼，只要所有執行緒使用的 robust_futexes 的 “鎖字” 的 “offset” 相同即可。 該執行緒應使用 “鎖條目” 指標連結它當前持有的鎖。 它可能還在鎖之間有其他連結，例如雙鏈表的反面，但這對於核心來說無關緊要。

透過以這種方式保持其鎖鏈接，在一個以核心已知的 “head” 指標開始的列表上，核心可以為執行緒提供 robust_futexes 可用的基本服務，即幫助清理在（可能意外的）退出時持有的鎖。

正常操作期間的實際鎖定和解鎖完全由爭用執行緒中的使用者級別程式碼處理，並由現有的 futex 機制等待和喚醒鎖。 核心在 robust_futexes 中唯一的基本參與是記住列表 “head” 的位置，並在執行緒退出時遍歷列表，處理離開執行緒仍然持有的鎖，如下所述。

在一個執行緒的共享記憶體中，在給定的時間點，各種資料結構上可能存在數千個 futex 鎖結構。 在給定時間，只有該執行緒當前持有的鎖的鎖結構才應該在該執行緒的 robust_futex 連結鎖列表上。

使用者共享記憶體區域中的給定 futex 鎖結構可以在不同的時間被有權訪問該區域的任何執行緒持有。 當前持有此類鎖的執行緒（如果有）在 “鎖字” 的低 30 位中用執行緒的 TID 標記。

當從其持有的鎖的列表中新增或刪除鎖時，為了使核心能夠正確處理鎖清理，無論任務何時退出（可能在操作此列表的中間獲得意外的訊號 9），使用者程式碼必須在 “鎖條目” 插入和刪除時遵守以下協議

在插入時

  1. 將 “list_op_pending” 字設定為要插入的 “鎖條目” 的地址，

  2. 獲取 futex 鎖，

  3. 將鎖條目及其執行緒 ID (TID) 新增到 “鎖字” 的低 30 位，新增到從 “head” 開始的連結串列中，以及

  4. 清除 “list_op_pending” 字。

在刪除時

  1. 將 “list_op_pending” 字設定為要刪除的 “鎖條目” 的地址，

  2. 從此鎖的 “head” 列表中刪除鎖條目，

  3. 釋放 futex 鎖，以及

  4. 清除 “lock_op_pending” 字。

在退出時，核心將考慮儲存在 “list_op_pending” 中的地址和透過遍歷從 “head” 開始的列表找到的每個 “鎖字” 的地址。 對於每個這樣的地址，如果從該地址偏移 “offset” 的 “鎖字” 的低 30 位等於退出執行緒的 TID，則核心將執行兩件事

  1. 如果在該字中設定了位 31 (0x80000000)，則嘗試在該地址上進行 futex 喚醒，這將喚醒下一個使用 futex 機制等待該地址的執行緒，以及

  2. 原子地在 “鎖字” 中設定位 30 (0x40000000)。

在上面，位 31 由該鎖上的 futex 等待者設定，以指示他們正在等待，位 30 由核心設定，以指示鎖所有者死亡時持有該鎖。

如果核心在任何時候發現以下情況，退出程式碼將靜默停止掃描列表

  1. “head” 指標或後續連結列表指標不是使用者空間字的有效地址

  2. “鎖字” 的計算位置（地址加上 “offset”）不是 32 位使用者空間字的有效地址

  3. 如果列表包含超過 100 萬個元素（可能會受到未來核心配置更改的影響）。

當核心看到一個列表條目的 “鎖字” 的低 30 位中沒有當前執行緒的 TID 時，它不會對該條目執行任何操作，而是轉到下一個條目。