Wound/Wait 防死鎖互斥鎖設計¶
請先閱讀 通用互斥鎖子系統，因為它也適用於 wait/wound 互斥鎖。
WW-互斥鎖的動機¶
GPU 執行的操作通常涉及許多緩衝區。這些緩衝區可以在上下文/程序之間共享，存在於不同的記憶體域（例如，VRAM 與系統記憶體）等等。並且透過 PRIME / dmabuf，它們甚至可以在裝置之間共享。因此，驅動程式需要在許多情況下等待緩衝區準備就緒。如果您從等待緩衝區互斥鎖變為可用狀態的角度來考慮這一點，則會出現一個問題，因為無法保證緩衝區在所有上下文中都以相同的順序出現在 execbuf/batch 中。這直接受使用者空間的控制，並且是應用程式發出的 GL 呼叫序列的結果。這會導致死鎖的可能性。當您考慮到核心可能需要在 GPU 在緩衝區上操作之前將緩衝區遷移到 VRAM 中時，問題會變得更加複雜，這可能又需要驅逐其他一些緩衝區（並且您不想驅逐已經排隊到 GPU 的其他緩衝區），但為了簡化對該問題的理解，您可以忽略這一點。
TTM 圖形子系統為處理此問題而提出的演算法非常簡單。對於需要鎖定的每組緩衝區 (execbuf)，呼叫者將從全域性計數器分配一個唯一的保留 id/票證。如果在鎖定與 execbuf 關聯的所有緩衝區時發生死鎖，則保留票證最低的（即，最舊的任務）獲勝，而保留 id 較高的（即，較新的任務）解鎖已鎖定的所有緩衝區，然後重試。
在 RDBMS 文獻中，保留票證與事務相關聯。死鎖處理方法稱為 Wait-Die。該名稱基於鎖定執行緒遇到已鎖定互斥鎖時的行為。如果持有鎖的事務較新，則鎖定事務等待。如果持有鎖的事務較舊，則鎖定事務退避並終止。因此稱為 Wait-Die。還有另一種演算法稱為 Wound-Wait：如果持有鎖的事務較新，則鎖定事務會“傷害”持有鎖的事務，請求其終止。如果持有鎖的事務較舊，則它會等待另一個事務。因此稱為 Wound-Wait。這兩種演算法都是公平的，因為事務最終會成功。但是，通常認為 Wound-Wait 演算法比 Wait-Die 產生更少的退避，但是，另一方面，從退避中恢復時，Wound-Wait 與比 Wait-Die 更多的工作相關聯。Wound-Wait 也是一種搶佔式演算法，因為事務會被其他事務“傷害”，這需要一種可靠的方法來拾取“傷害”狀態並搶佔正在執行的事務。請注意，這與程序搶佔不同。在 Wound-Wait 事務死亡（返回 -EDEADLK）之後，它被認為是被搶佔了。
概念¶
與普通互斥鎖相比，w/w 互斥鎖的鎖介面中出現了兩個額外的概念/物件
獲取上下文：為了確保最終向前進展，重要的是嘗試獲取鎖的任務不會獲取新的保留 id，而是保留它在開始獲取鎖時獲得的那個 id。該票證儲存在獲取上下文中。此外，獲取上下文會跟蹤除錯狀態，以捕獲 w/w 互斥鎖介面濫用。獲取上下文代表一個事務。
W/w 類：與普通互斥鎖相反，對於 w/w 互斥鎖，鎖類需要是顯式的，因為需要初始化獲取上下文。鎖類還指定要使用的演算法，Wound-Wait 或 Wait-Die。
此外，還有三種不同的 w/w 鎖獲取函式類
使用上下文的正常鎖獲取，使用 ww_mutex_lock。
在爭用鎖上進行慢速路徑鎖獲取，由剛剛終止其事務（在放棄所有已獲取的鎖之後）的任務使用。這些函式具有 _slow 字尾。
從簡單的語義角度來看，_slow 函式不是嚴格必需的，因為在爭用鎖上簡單地呼叫正常的 ww_mutex_lock 函式（在放棄所有其他已獲取的鎖之後）可以正常工作。畢竟，如果尚未獲取其他 ww 互斥鎖，則不存在死鎖的可能性，因此 ww_mutex_lock 呼叫將阻塞並且不會過早地返回 -EDEADLK。_slow 函式的優點在於介面安全
ww_mutex_lock 具有 __must_check int 返回型別，而 ww_mutex_lock_slow 具有 void 返回型別。請注意，由於 ww 互斥鎖程式碼無論如何都需要迴圈/重試，因此即使第一個鎖操作永遠不會失敗，__must_check 也不會導致虛假警告。
當啟用完整除錯時，ww_mutex_lock_slow 會檢查是否已釋放所有已獲取的 ww 互斥鎖（防止死鎖），並確保我們在爭用鎖上阻塞（防止在 -EDEADLK 慢速路徑中旋轉，直到可以獲取爭用鎖）。
僅獲取單個 w/w 互斥鎖的函式，其結果與普通互斥鎖的語義完全相同。這透過使用 NULL 上下文呼叫 ww_mutex_lock 來完成。
同樣，這不是嚴格必需的。但是通常您只想獲取一個鎖，在這種情況下，設定獲取上下文毫無意義（因此最好避免獲取死鎖避免票證）。
當然，還提供了用於處理由於訊號引起的喚醒的所有常用變體。
用法¶
該演算法（Wait-Die 與 Wound-Wait）透過使用 DEFINE_WW_CLASS() (Wound-Wait) 或 DEFINE_WD_CLASS() (Wait-Die) 來選擇。作為一個粗略的經驗法則，如果您期望同時競爭的事務數量通常很小，並且您希望減少回滾次數，則使用 Wound-Wait。
在同一個 w/w 類中獲取鎖的三種不同方法。方法 #1 和 #2 的常見定義
static DEFINE_WW_CLASS(ww_class);
struct obj {
struct ww_mutex lock;
/* obj data */
};
struct obj_entry {
struct list_head head;
struct obj *obj;
};
方法 1，使用 execbuf->buffers 中的列表，不允許重新排序。如果已在某處跟蹤所需物件的列表，這將非常有用。此外，鎖助手可以將 -EALREADY 返回程式碼傳播回撥用者，作為物件在列表中出現兩次的訊號。如果列表是從使用者空間輸入構造的，並且 ABI 要求使用者空間沒有重複條目（例如，對於 gpu 命令緩衝區提交 ioctl），這將非常有用
int lock_objs(struct list_head *list, struct ww_acquire_ctx *ctx)
{
struct obj *res_obj = NULL;
struct obj_entry *contended_entry = NULL;
struct obj_entry *entry;
ww_acquire_init(ctx, &ww_class);
retry:
list_for_each_entry (entry, list, head) {
if (entry->obj == res_obj) {
res_obj = NULL;
continue;
}
ret = ww_mutex_lock(&entry->obj->lock, ctx);
if (ret < 0) {
contended_entry = entry;
goto err;
}
}
ww_acquire_done(ctx);
return 0;
err:
list_for_each_entry_continue_reverse (entry, list, head)
ww_mutex_unlock(&entry->obj->lock);
if (res_obj)
ww_mutex_unlock(&res_obj->lock);
if (ret == -EDEADLK) {
/* we lost out in a seqno race, lock and retry.. */
ww_mutex_lock_slow(&contended_entry->obj->lock, ctx);
res_obj = contended_entry->obj;
goto retry;
}
ww_acquire_fini(ctx);
return ret;
}
方法 2，使用 execbuf->buffers 中的列表，可以重新排序。使用 -EALREADY 的重複條目檢測的語義與上面的方法 1 相同。但是列表重新排序允許使用更符合習慣的程式碼
int lock_objs(struct list_head *list, struct ww_acquire_ctx *ctx)
{
struct obj_entry *entry, *entry2;
ww_acquire_init(ctx, &ww_class);
list_for_each_entry (entry, list, head) {
ret = ww_mutex_lock(&entry->obj->lock, ctx);
if (ret < 0) {
entry2 = entry;
list_for_each_entry_continue_reverse (entry2, list, head)
ww_mutex_unlock(&entry2->obj->lock);
if (ret != -EDEADLK) {
ww_acquire_fini(ctx);
return ret;
}
/* we lost out in a seqno race, lock and retry.. */
ww_mutex_lock_slow(&entry->obj->lock, ctx);
/*
* Move buf to head of the list, this will point
* buf->next to the first unlocked entry,
* restarting the for loop.
*/
list_del(&entry->head);
list_add(&entry->head, list);
}
}
ww_acquire_done(ctx);
return 0;
}
對於方法 #1 和 #2，解鎖的工作方式相同
void unlock_objs(struct list_head *list, struct ww_acquire_ctx *ctx)
{
struct obj_entry *entry;
list_for_each_entry (entry, list, head)
ww_mutex_unlock(&entry->obj->lock);
ww_acquire_fini(ctx);
}
如果物件的列表是臨時構造的而不是預先構造的，則方法 3 非常有用，例如，在圖中調整邊緣時，每個節點都有自己的 ww_mutex 鎖，並且只有在持有所有涉及節點的鎖時才能更改邊緣。w/w 互斥鎖非常適合這種情況，原因有兩個
它們可以按任何順序處理鎖獲取，這允許我們從起點開始遍歷圖，然後迭代地發現新邊緣並鎖定這些邊緣連線到的節點。
由於 -EALREADY 返回程式碼表示給定的物件已被持有，因此無需額外的簿記來打破圖中的迴圈或跟蹤哪些查詢已被持有（當使用多個節點作為起點時）。
請注意，此方法與上述方法在兩個重要方面有所不同
由於物件列表是動態構造的（並且在由於遇到 -EDEADLK 終止條件而重試時可能非常不同），因此無需在物件未鎖定時將任何物件保留在持久列表中。因此，我們可以將 list_head 移動到物件本身中。
另一方面，動態物件列表構造也意味著無法傳播 -EALREADY 返回程式碼。
另請注意，可以組合方法 #1 和 #2 以及方法 #3，例如，首先使用上述方法之一鎖定起始節點列表（從使用者空間傳入）。然後鎖定使用下面的方法 #3 影響的任何其他物件。回退/重試過程會更復雜一些，因為當動態鎖定步驟遇到 -EDEADLK 時，我們還需要解鎖使用固定列表獲取的所有物件。但是 w/w 互斥鎖除錯檢查將捕獲這些情況下的任何介面濫用。
此外，方法 3 不會使鎖獲取步驟失敗，因為它不會返回 -EALREADY。當然，當使用 _interruptible 變體時，情況會有所不同，但這超出了此處這些示例的範圍
struct obj {
struct ww_mutex ww_mutex;
struct list_head locked_list;
};
static DEFINE_WW_CLASS(ww_class);
void __unlock_objs(struct list_head *list)
{
struct obj *entry, *temp;
list_for_each_entry_safe (entry, temp, list, locked_list) {
/* need to do that before unlocking, since only the current lock holder is
allowed to use object */
list_del(&entry->locked_list);
ww_mutex_unlock(entry->ww_mutex)
}
}
void lock_objs(struct list_head *list, struct ww_acquire_ctx *ctx)
{
struct obj *obj;
ww_acquire_init(ctx, &ww_class);
retry:
/* re-init loop start state */
loop {
/* magic code which walks over a graph and decides which objects
* to lock */
ret = ww_mutex_lock(obj->ww_mutex, ctx);
if (ret == -EALREADY) {
/* we have that one already, get to the next object */
continue;
}
if (ret == -EDEADLK) {
__unlock_objs(list);
ww_mutex_lock_slow(obj, ctx);
list_add(&entry->locked_list, list);
goto retry;
}
/* locked a new object, add it to the list */
list_add_tail(&entry->locked_list, list);
}
ww_acquire_done(ctx);
return 0;
}
void unlock_objs(struct list_head *list, struct ww_acquire_ctx *ctx)
{
__unlock_objs(list);
ww_acquire_fini(ctx);
}
方法 4：僅鎖定一個物件。在這種情況下，死鎖檢測和預防顯然是過度殺傷，因為僅使用一個鎖就無法在單個類中產生死鎖。為了簡化這種情況，w/w 互斥鎖 API 可以與 NULL 上下文一起使用。
實現細節¶
設計：¶
ww_mutex 當前封裝了一個 struct mutex，這意味著對於更常見的普通互斥鎖，沒有額外的開銷。因此，如果不使用 wait/wound 互斥鎖，程式碼大小隻會略有增加。
我們為等待列表維護以下不變性
具有獲取上下文的等待者按時間戳順序排序；沒有獲取上下文的等待者以 FIFO 順序穿插。
對於 Wait-Die，在具有上下文的等待者中，只有第一個可以已經獲取了其他鎖 (ctx->acquired > 0)。請注意，此等待者可能在列表中沒有上下文的其他等待者之後出現。
Wound-Wait 搶佔是透過延遲搶佔方案實現的：僅當爭用新鎖並且真正存在死鎖機會時，才檢查事務的“傷害”狀態。在這種情況下，如果事務受到“傷害”，它會退避，清除“傷害”狀態並重試。以這種方式實現搶佔的一個巨大好處是，“受傷”事務可以識別爭用鎖，以便在重新啟動事務之前等待。盲目地重新啟動事務可能會使事務最終陷入不得不再次退避的情況。
總的來說，預計不會有太多的爭用。這些鎖通常用於序列化對裝置資源的訪問，因此最佳化重點應放在非爭用情況上。
Lockdep：¶
已特別注意警告儘可能多的 api 濫用情況。一些常見的 api 濫用將透過 CONFIG_DEBUG_MUTEXES 捕獲，但建議使用 CONFIG_PROVE_LOCKING。
- 將警告的一些錯誤
忘記呼叫 ww_acquire_fini 或 ww_acquire_init。
在 ww_acquire_done 之後嘗試鎖定更多互斥鎖。
在 -EDEADLK 之後嘗試鎖定錯誤的互斥鎖並解鎖所有互斥鎖。
在 -EDEADLK 之後，在解鎖所有互斥鎖之前，嘗試鎖定正確的互斥鎖。
在返回 -EDEADLK 之前呼叫 ww_mutex_lock_slow。
使用錯誤的解鎖函式解鎖互斥鎖。
在同一上下文中兩次呼叫 ww_acquire_* 之一。
對互斥鎖使用與 ww_acquire_ctx 不同的 ww_class。
可能導致死鎖的正常 lockdep 錯誤。
- 可能導致死鎖的一些 lockdep 錯誤
在對第一個 ww_acquire_ctx 呼叫 ww_acquire_fini 之前，呼叫 ww_acquire_init 以初始化第二個 ww_acquire_ctx。
可能發生的“正常”死鎖。
- 待辦事項
一旦我們實現了 TASK_DEADLOCK 任務狀態標誌魔術，就更新此部分。