關於健壯型 Futex 的描述¶
- 作者:
Ingo Molnar <mingo@redhat.com>
背景¶
什麼是健壯型 futex？要回答這個問題，我們首先需要了解什麼是 futex：普通的 futex 是特殊型別的鎖，在非競爭情況下，可以直接從使用者空間獲取/釋放，而無需進入核心。
Futex 本質上是一個使用者空間地址，例如一個 32 位鎖變數欄位。如果使用者空間注意到競爭（鎖已經被擁有，並且其他人也想獲取它），那麼該鎖會被標記為一個值，表明“有一個等待者正在等待”，並且使用 sys_futex(FUTEX_WAIT) 系統呼叫來等待另一個人釋放它。核心在內部建立一個“futex 佇列”，以便以後可以將等待者與喚醒者匹配起來 - 而無需他們彼此瞭解。當所有者執行緒釋放 futex 時，它會注意到（透過變數值）有等待者正在等待，並執行 sys_futex(FUTEX_WAKE) 系統呼叫來喚醒他們。一旦所有等待者都獲取並釋放了鎖，futex 再次回到“非競爭”狀態，並且沒有與其相關的核心狀態。核心完全忘記了曾經在該地址存在過一個 futex。這種方法使得 futex 非常輕量級且可擴充套件。
“健壯性”是指在持有鎖時處理崩潰：如果一個程序在持有 pthread_mutex_t 鎖的同時過早退出，而該鎖也與某些其他程序共享（例如，yum 在持有 pthread_mutex_t 時發生段錯誤，或者 yum 被 kill -9-ed），那麼該鎖的等待者需要被通知該鎖的最後一個所有者以某種不規則的方式退出。
為了解決這類問題，建立了“健壯互斥鎖”使用者空間 API：如果所有者過早退出，pthread_mutex_lock() 會返回一個錯誤值 - 並且新的所有者可以決定由該鎖保護的資料是否可以安全恢復。
但是基於 futex 的互斥鎖存在一個很大的概念問題：是核心銷燬了所有者任務（例如，由於 SEGFAULT），但是核心無法幫助進行清理：如果沒有“futex 佇列”（並且在大多數情況下沒有，因為 futex 是快速的輕量級鎖），那麼核心沒有資訊來清理持有的鎖！使用者空間也沒有機會清理鎖 - 使用者空間是崩潰的一方，因此它沒有機會清理。進退兩難。
實際上，當例如 yum 被 kill -9-ed（或發生段錯誤）時，需要系統重啟才能釋放基於該 futex 的鎖。 這是針對 yum 的主要錯誤報告之一。
為了解決這個問題，傳統的方法是擴充套件 vma（虛擬記憶體區域描述符）概念，使其具有“附加到此區域的待處理健壯型 futex”的概念。 這種方法需要 3 個新的 sys_futex() 系統呼叫變體：FUTEX_REGISTER、FUTEX_DEREGISTER 和 FUTEX_RECOVER。 在 do_exit() 時，會搜尋所有 vma 以檢視它們是否設定了 robust_head。 這種方法仍然存在兩個根本問題
它具有相當複雜的鎖機制和競爭場景。 基於 vma 的方法已經掛起多年，但它們仍然不完全可靠。
它們必須在 sys_exit() 時掃描 _每個_ vma，每個執行緒！
第二個缺點是真正的殺手：pthread_exit() 在 Linux 上大約需要 1 微秒，但是對於成千上萬（或數萬個）vma，每個 pthread_exit() 需要一毫秒或更長時間，這也完全破壞了 CPU 的 L1 和 L2 快取！
即使對於正常的程序 sys_exit_group() 呼叫，這也是非常明顯的：核心必須無條件地進行 vma 掃描！ （這是因為核心不知道有多少健壯型 futex 需要清理，因為健壯型 futex 可能已在另一個任務中註冊，並且 futex 變數可能只是 mmap() 對映到此程序的地址空間中）。
這種巨大的開銷迫使建立 CONFIG_FUTEX_ROBUST，以便正常的核心可以將其關閉，但更糟糕的是：這種開銷使得健壯型 futex 對於任何型別的通用 Linux 發行版都不切實際。
所以必須做一些事情。
健壯型 Futex 的新方法¶
這種新方法的核心是每個執行緒的私有健壯鎖列表，該列表由使用者空間持有（由 glibc 維護） - 該使用者空間列表透過新的系統呼叫在核心中註冊[此註冊每個執行緒生命週期最多發生一次]。 在 do_exit() 時，核心檢查此使用者空間列表：是否有任何健壯型 futex 鎖需要清理？
在常見情況下，在 do_exit() 時，沒有註冊列表，因此健壯型 futex 的成本只是一個簡單的 current->robust_list != NULL 比較。 如果執行緒註冊了一個列表，那麼通常該列表是空的。 如果執行緒/程序崩潰或以某種不正確的方式終止，那麼該列表可能非空：在這種情況下，核心會仔細地遍歷該列表 [不信任它]，並將該執行緒擁有的所有鎖標記為 FUTEX_OWNER_DIED 位，並喚醒一個等待者（如果有）。
該列表保證在 do_exit() 時是私有的和每個執行緒的，因此核心可以以無鎖方式訪問它。
但是存在一種可能的競爭：由於新增到列表和從列表刪除是在 glibc 獲取 futex 之後完成的，因此執行緒（或程序）可能會在那裡死亡，從而使 futex 掛起。 為了防止這種可能性，使用者空間 (glibc) 還維護一個簡單的每個執行緒的 'list_op_pending' 欄位，以便核心線上程獲取鎖後但在新增到列表之前死亡時進行清理。 Glibc 在嘗試獲取 futex 之前設定此 list_op_pending 欄位，並在列表新增（或列表刪除）完成後清除它。
這就是所需要的全部 - 所有剩餘的 robust-futex 清理都在使用者空間中完成 [就像之前的補丁一樣]。
Ulrich Drepper 已經實現了這個新機制所需的 glibc 支援，這完全啟用了健壯互斥鎖。
與基於 vma 的方法相比，這種基於使用者空間列表的方法的主要區別
它更快得多：線上程退出時，無需遍歷每個 vma (!)，而 VM-based 方法必須這樣做。 只需一個非常簡單的“列表是否為空”操作即可。
不需要 VM 更改 - '
struct address_space' 保持不變。不需要註冊單個鎖：健壯互斥鎖不需要任何額外的每個鎖的系統呼叫。 因此，健壯互斥鎖成為一個非常輕量級的原語 - 因此它們不會迫使應用程式設計者在效能和健壯性之間做出艱難的選擇 - 健壯互斥鎖同樣快速。
不發生每個鎖的核心分配。
不需要資源限制。
不需要核心空間恢復呼叫 (FUTEX_RECOVER)。
實現和鎖機制是“顯而易見的”，並且沒有與 VM 的互動。
效能¶
我已經基準測試了核心處理 100 萬 (!) 個持有鎖列表所需的時間，使用新方法 [在 2GHz CPU 上]
使用 FUTEX_WAIT 設定 [競爭互斥鎖]：130 毫秒
未使用 FUTEX_WAIT 設定 [非競爭互斥鎖]：30 毫秒
我還測量了一種方法，其中 glibc 執行鎖通知 [它目前對 !pshared 健壯互斥鎖執行此操作]，這花費了 256 毫秒 - 顯然較慢，因為使用者空間必須執行 100 萬個 FUTEX_WAKE 系統呼叫。
（100 萬個持有鎖是聞所未聞的 - 我們期望一次最多持有少量鎖。儘管如此，很高興知道這種方法可以很好地擴充套件。）
實現細節¶
該補丁添加了兩個新的系統呼叫：一個用於註冊使用者空間列表，一個用於查詢註冊的列表指標
asmlinkage long
sys_set_robust_list(struct robust_list_head __user *head,
size_t len);
asmlinkage long
sys_get_robust_list(int pid, struct robust_list_head __user **head_ptr,
size_t __user *len_ptr);
列表註冊非常快：該指標只是儲存在 current->robust_list 中。[請注意，將來，如果健壯型 futex 變得普遍，我們可以擴充套件 sys_clone() 以為新執行緒註冊一個健壯列表頭，而無需另一個系統呼叫。]
因此，對於不使用健壯型 futex 的任務，幾乎沒有開銷，即使對於健壯型 futex 使用者，每個執行緒生命週期也只有一個額外的系統呼叫，並且清理操作（如果發生）快速而直接。 核心在內部不對健壯型 futex 和普通 futex 進行任何區分。
如果在退出時發現持有 futex，則核心設定 futex 字的以下位
#define FUTEX_OWNER_DIED 0x40000000
並喚醒下一個 futex 等待者（如果有）。 使用者空間完成剩餘的清理。
否則，glibc 透過將 TID 原子地放入 futex 欄位來獲取健壯型 futex。 等待者設定 FUTEX_WAITERS 位
#define FUTEX_WAITERS 0x80000000
剩餘的位用於 TID。
測試、架構支援¶
我已經在 x86 和 x86_64 上測試了新的系統呼叫，並確保了使用者空間列表的解析是健壯的 [;-) ]，即使該列表被故意損壞。
i386 和 x86_64 系統呼叫目前已連線，Ulrich 已經測試了新的 glibc 程式碼（在 x86_64 和 i386 上），它適用於他的 robust-mutex 測試用例。
所有其他架構也應該構建良好 - 但它們還沒有新的系統呼叫。
架構需要在編寫系統呼叫之前實現新的 futex_atomic_cmpxchg_inatomic() 行內函數。