Try   HackMD

2025q1 第 17 週測驗題

目的: 檢驗學員對並行和多執行緒程式設計的認知

作答表單: 測驗 1

測驗 1

(mutex) lock 可能會導致 deadlock,但若始終按照一致的順序去 acquire lock,即可避免該情況。以下程式碼提供追蹤功能,確保使用者採取正確的順序。程式會跟蹤目前執行緒持有的 lock,每當 acquire 獲取新 lock 時,就會從最後一個 lock 到新 lock 建立一個依賴關係,後者構成一個 graph,只要該 graph 不包含任何循環,就不會發生 deadlock。

延伸閱讀: Deadlock-free Mutexes and Directed Acyclic Graphs

考慮以下的程式碼:

/* Task A locks mutex1 then mutex2, simulating a resource access pattern. */
void *taskA(void *thread_id)
{
    long tid = (long) thread_id;
    printf("[%s] thread #%ld\n", __func__, tid);

    for (int i = 0; i < N_TESTS; i++) {
        mutex_lock(&mutex1);
        sleep(1);
        mutex_lock(&mutex2);
        printf("task A in loop %d \n", i);
        sleep(1);
        mutex_unlock(&mutex2);
        sleep(1);
        mutex_unlock(&mutex1);
        sleep(1);
    }
    pthread_exit(NULL);
}

/* Task B locks mutex2 then mutex1, simulating a different resource access
 * pattern.
 */
void *taskB(void *thread_id)
{
    long tid = (long) thread_id;
    printf("[%s] thread #%ld\n", __func__, tid);

    for (int i = 0; i < N_TESTS; i++) {
        mutex_lock(&mutex2);
        sleep(1);
        mutex_lock(&mutex1);
        printf("task B in loop %d \n", i);
        sleep(1);
        mutex_unlock(&mutex1);
        sleep(1);
        mutex_unlock(&mutex2);
        sleep(1);
    }
    pthread_exit(NULL);
}

參考執行輸出: (ok 那行可能不出現)

[taskA] thread #0
[taskB] thread #1
will_lock: --- pid 0xddf9a700 deadlock lock 0x94120442286208x (id=0) -> lock 0x94120442286144x (id=1)
current mutex with holding threads (PID)
========================================
pid 0x0 holds lock 0x1f875080 (id=0)
pid 0x1 holds lock 0x1f875040 (id=1)

Recorded lock dependency
========================================
pid 0x0 lock 0x1f875080 (id=0) -> lock 0x1f875040 (id=1) deadlock
pid 0x1 lock 0x1f875040 (id=1) -> lock 0x1f875080 (id=0) ok

Linux 核心也有 lock 相依性的偵測機制,參見 Runtime locking correctness validator,對應的程式碼:

補完程式碼,使 lockdep 運作符合預期。

作答規範:

  • AAAA, CCCC, DDDD 為表示式,注意遞迴呼叫
  • BBBB 為 bool 型態,必為 truefalse

延伸閱讀:

Lock Dependency Validator

以下改寫自 Linux 核心官方文件:lockdep-design.html

Lockdep 是 Linux 核心中的一個執行時期鎖定驗證工具。它透過追蹤核心中所有鎖的取得與釋放,來偵測潛在的鎖定相關死結 (deadlock) 風險,而不需要讓死結實際發生。

鎖定類別 (Lock-class)

在 Linux 核心中,一個鎖定類別 (lock-class) 代表一群具有相同鎖定規則 (locking rules) 的鎖。一個鎖定類別可以有多種實作 (implementation),但它們共享相同的驗證邏輯。舉例來說,inode 結構中的某個鎖定義一個鎖定類別,而每個 inode 物件都擁有該鎖的一個實體 (instance)。

驗證器 (validator) 的作用是追蹤每個鎖定類別的「使用狀態」 (usage state),並檢查不同鎖定類別之間的相依性 (dependency)。

  • 使用狀態 (Lock usage):指一個鎖在特定的中斷情境 (IRQ context) 下被如何使用。
  • 相依性 (Lock dependency):指鎖定的順序 (lock order)。本文中,L1 -> L2 表示一個任務在已經持有 L1 的情況下,嘗試去獲取 L2。從 lockdep 的角度來看,兩個鎖不一定有邏輯上的關聯,此相依性僅表示某個特定的鎖定順序曾經發生過。

驗證器的目標就是確保所有鎖的使用狀態和相依性都是正確且一致的。

當某個鎖定類別的第一個實體在系統執行期間被使用時,該鎖定類別會被註冊,之後其所有實體的使用狀態和相依性都會被追蹤。即使該類別的某個實體被銷毀,鎖定類別的資訊依然會被保留,直到其佔用的記憶體空間被回收(例如:核心模組被移除或工作佇列 (workqueue) 被銷毀)。

使用狀態 (Usage state)

驗證器會追蹤鎖定類別的使用紀錄,並將其使用狀態劃分為 (4 種用法 * n 種狀態 + 1) 個種類。

4 種用法分別是:

  • 曾在 STATE 情境中被持有
  • 曾在 STATE 情境中被當作讀取鎖 (read-lock) 持有
  • 曾在 STATE 啟用時被持有
  • 曾在 STATE 啟用時被當作讀取鎖持有

而 n 種狀態 (STATE) 目前記錄在 kernel/locking/lockdep_states.h 中,主要包括:

  • 硬體中斷 (hardirq)
  • 軟體中斷 (softirq)

最後一個 +1 的種類是:

  • 曾經被使用過 (ever used)

當鎖定規則被違反時,這些使用狀態的位元 (bits) 會被顯示在錯誤訊息中。對於一個鎖,其狀態字串中的字元代表:

  • .:在中斷停用 (irqs disabled) 且非中斷情境下取得
  • -:在中斷情境 (in irq context) 中取得
  • +:在中斷啟用 (irqs enabled) 狀態下取得
  • ?:在中斷情境中,但中斷卻是啟用狀態下取得(這通常是一個錯誤配置)

對於任一 STATE,一個鎖是否在該 STATE 的情境中被持有,以及該 STATE 本身是否啟用,可以組合成四種情況,如下表所示:

中斷已啟用 (IRQ enabled) 中斷已停用 (IRQ disabled)
曾在中斷情境 ? -
未曾在中斷情境 + .

一個從未被使用過的鎖,自然不會出現在任何錯誤報告中。

單一鎖定狀態規則 (Single-lock state rules)

若一個鎖被標記為中斷安全 (irq-safe),代表它可以在中斷情境中使用。反之,若被標記為中斷不安全 (irq-unsafe),代表它曾在中斷啟用的狀態下被持有。

一個 softirq-unsafe 的鎖定類別必定也是 hardirq-unsafe。以下的狀態具有排他性,每個鎖定類別在任何時間點,根據其使用歷史,只會有其中一個狀態:

<hardirq-safe> 或 <hardirq-unsafe>
<softirq-safe> 或 <softirq-unsafe>

關鍵規則:一個可以在中斷情境中使用的鎖 (irq-safe),絕不能在普通情境且中斷為啟用狀態時被持有 (irq-unsafe)。

否則,可能會發生遞迴死結 (recursion deadlock)。舉例來說,若某個任務持有一個 irq-unsafe 的鎖 L,此時一個硬體中斷發生,而該中斷處理常式也嘗試獲取同一個 L(因為 L 也是 irq-safe 的)。由於中斷無法等待任務釋放鎖,任務也因被中斷而無法繼續執行,這就形成一個無法解開的死結。

同樣地,同一個鎖定類別中的同一個鎖實體,不能在持有它的情境中再次被獲取(除非是遞迴鎖),否則也會導致遞迴死結。

多重鎖定相依性規則 (Multi-lock dependency rules)

對於兩個不同的鎖,它們不能被以相反的順序獲取,否則會導致鎖反轉死結 (lock inversion deadlock)。

<L1> -> <L2>
<L2> -> <L1>

這種情況會形成一個循環 (circle) 等待,導致相關任務永遠無法繼續執行。驗證器能夠在這種循環鏈的任何一個環節被建立時就立即偵測到它,即使鏈中還存在其他鎖定序列。

此外,以下兩種相依性也是被禁止的:

<hardirq-safe>   ->  <hardirq-unsafe>
<softirq-safe>   ->  <softirq-unsafe>
  1. 第一條規則的理由是:一個 hardirq-safe 的鎖可能在硬體中斷情境中被取得。若此時中斷一個正在持有 hardirq-unsafe 鎖的任務,並嘗試獲取該 hardirq-unsafe 鎖,就會形成 (<hardirq-unsafe> -> <hardirq-safe>) 的反向相依性,造成鎖反轉死結。
  2. 第二條規則同理,只是情境換成軟體中斷。

上述規則會被強制應用於核心中的每一個鎖。每當嘗試獲取一個新鎖時,驗證器都會檢查當前已持有的鎖與這個新鎖之間是否違反這些規則。

當一個鎖定類別的狀態改變時(例如從 unsafe 變成 safe),驗證器會執行以下檢查:

  • 若一個鎖變為 hardirq-safe,檢查它是否曾經持有過任何 hardirq-unsafe 的鎖
  • 若一個鎖變為 softirq-safe,檢查它是否曾經持有過任何 softirq-unsafe 的鎖
  • 若一個鎖變為 hardirq-unsafe,檢查它是否曾經被任何 hardirq-safe 的鎖持有過
  • 若一個鎖變為 softirq-unsafe,檢查它是否曾經被任何 softirq-safe 的鎖持有過

這些檢查是必要的,因為中斷情境可以搶佔 (preempt) 任何持有 unsafe 鎖的程式碼,即使死結尚未實際發生,這種潛在風險也必須被立即報告。

例外狀況:巢狀鎖定 (Nested Locking)

在 Linux 核心中,存在一些合法情境需要獲取同一個鎖定類別的多個實體。這通常發生在具有階層架構的物件之間,例如親屬關係。在這些案例中,核心程式碼獲取鎖的順序是固定且符合階層結構的。

一個典型的例子是磁碟裝置的 block-dev 物件:一個代表整個磁碟的物件,以及多個代表分割區 (partition) 的物件。分割區是整個磁碟的一部分,因此「全磁碟鎖」的層級比「分割區鎖」更高。全磁碟鎖 -> 分割區鎖 這樣的鎖定順序是完全正確的。

然而,驗證器無法自動推斷這種基於資料結構的自然順序。為了告知驗證器這種合法的使用模型,許多鎖定原語 (primitives) 提供帶有 _nested 後綴的新版本,允許開發者明確指定一個「巢狀層級」(nesting level)。

例如,區塊裝置的 mutex

enum bdev_bd_mutex_lock_class
{
     BD_MUTEX_NORMAL,
     BD_MUTEX_WHOLE,
     BD_MUTEX_PARTITION
};

mutex_lock_nested(&bdev->bd_contains->bd_mutex, BD_MUTEX_PARTITION);

以上程式碼明確告知 lockdep,此次在 bdev 物件上的鎖定屬於 PARTITION 層級。驗證器會將這種巢狀鎖定的每個層級視為一個獨立的鎖定類別來追蹤。

標記 (Annotations)

有兩組函式是用來標記和檢查特定鎖是否被持有的:

  • lockdep_assert_held*(&lock)
  • lockdep_*pin_lock(&lock)

lockdep_assert_held*() 是一系列在核心中被大量使用的巨集,用來斷言 (assert) 某個特定的鎖在程式碼的特定位置必須是已被持有的狀態。若未被持有,會觸發一個 WARN() 警告。

另一組巨集 lockdep_*pin_lock() 目前主要用於排程器的 rq->lock。它們用來確保一個鎖不會被意外地釋放。這在具有回呼 (callbacks) 的情境中非常有用:上層程式碼可能假設鎖在整個回呼過程中都應被持有,但下層實作卻可能認為可以先釋放再重新獲取。lockdep_pin_lock() 會回傳一個 struct pin_cookie,並在之後傳遞給 lockdep_unpin_lock(),以確保在 pinunpin 之間,該鎖的狀態未被不當地改變。

百分之百正確性證明

驗證器在分析每個簡單且獨立的單一任務鎖定序列 (single-task locking sequence)** 時,可以達到數學上的 closure。這意味著,只要驗證器見過所有單獨的鎖定鏈環節(如 A->BB->C),它就能證明這些鎖定序列在任何時間、任何組合下,都不可能造成與順序相關的死結。

對於更複雜的多 CPU 和多任務情境,驗證器不需要等待死結實際發生來證明其存在。只要構成死結循環的所有單獨鎖定鏈(例如 A->BB->A)各自至少發生過一次,驗證器就能夠組合這些資訊並報告潛在的死結。

這大幅簡化核心中與鎖定相關的品質保證 (QA) 工作的複雜度。在 QA 階段,我們只需要盡可能地觸發多樣的單一任務鎖定相依性,而不需要去窮舉測試所有 CPU 之間、所有任務之間複雜的鎖定交錯組合。

效能 (Performance)

上述所有規則都是執行時期的檢查。若每次獲取鎖或啟用中斷都要完整檢查一次,系統將會慢到無法使用,因為檢查的時間複雜度是 O(n²),其中 n 是已持有的鎖數量。

為了解決這個問題,lockdep 採用最佳化策略:每種鎖定場景只會完整檢查一次。核心會維護一個當前持有鎖的堆疊 (stack),並為其計算一個輕量的 64 位元雜湊值 (hash value)。每種獨特的鎖鏈(持有鎖的種類與順序)都會產生一個獨特的雜湊值。

若某個鎖鏈是第一次出現,驗證器會執行完整的檢查,並將其雜湊值存入一個雜湊表。此雜湊表是以無鎖 (lock-free) 方式進行存取的。之後若相同的鎖鏈再次出現,透過查詢雜湊表就能得知它已經被驗證過,從而跳過昂貴的檢查。

遞迴讀取鎖 (Recursive read locks)

鎖的持有者 (locker) 可分為三種類型:

  • 寫入者 (Writers, W/E):獨佔鎖 (exclusive lock),例如 spin_lock()write_lock()
  • 非遞迴讀取者 (Non-recursive readers, r):共享鎖 (shared lock),例如 down_read()
  • 遞迴讀取者 (Recursive readers, R):可遞迴的共享鎖,例如 rcu_read_lock()

為了方便描述,我們使用以下符號:

  • S (Shared):代表所有讀取者 (r + R)
  • N (Non-recursive):代表寫入者和非遞迴讀取者 (W + r)

遞迴讀取者,顧名思義,允許在同一個鎖實體 (lock instance) 的讀取者臨界區段 (critical section) 內,再次嘗試獲取該讀取鎖。換句話說,它允許巢狀的讀取鎖定。

相對地,非遞迴讀取者若嘗試在已持有該讀取鎖的情境下再次獲取,將會導致自我死結 (self-deadlock)。

二者的關鍵區別在於它們的阻塞條件:

  • 遞迴讀取者只會被寫入鎖的持有者 (writer holder) 阻塞
  • 非遞迴讀取者會被寫入鎖的持有者以及等待中的寫入者 (writer waiter) 阻塞

來看以下例子:

任務 A:                 任務 B:

read_lock(X);
                        write_lock(X); // B 被 A 阻塞,成為等待者
read_lock_2(X);
  1. 任務 A 取得 X 的讀取鎖
  2. 任務 B 嘗試取得 X 的寫入鎖,但因為 A 持有讀取鎖,B 被阻塞,成為 X 的一個等待中的寫入者
  3. 此時,若 read_lock_2(X) 是一個遞迴讀取鎖,任務 A 可以成功獲取,因為等待中的寫入者 B 不會阻塞遞迴讀取者
  4. 但若 read_lock_2(X) 是一個非遞迴讀取鎖,任務 A 將會被等待中的寫入者 B 阻塞,而 B 又在等待 A 釋放鎖,從而形成死結

讀取者/寫入者之間的阻塞條件

對於同一個鎖實體,有四種阻塞條件:

  • 寫入者會阻塞其他寫入者
  • 寫入者會阻塞所有類型的讀取者
  • 讀取者 (不論是否遞迴) 會阻塞寫入者
  • 讀取者之間:遞迴讀取者不會互相阻塞;但非遞迴讀取者可能會被其他讀取者阻塞(因為可能存在一個等待中的寫入者)

注意:一個鎖實體本身沒有固定的類型;它的類型(獨佔、非遞迴讀取、遞迴讀取)取決於當次獲取它時所使用的操作函式(更精確地說,是傳給 lock_acquire()read 參數值)。

  • 遞迴鎖 (Recursive locks):指遞迴讀取鎖。
  • 非遞迴鎖 (Non-recursive locks):指寫入鎖和非遞迴讀取鎖。

遞迴鎖之間不會互相阻塞,但非遞迴鎖之間會。此外,一個非遞迴鎖可以阻塞一個遞迴鎖,反之亦然。

以下是一個由不同鎖的遞迴讀取鎖造成的死結範例:

任務 A:                 任務 B:

read_lock(X);           // A 取得 X 的讀取鎖
                        read_lock(Y);           // B 取得 Y 的讀取鎖
write_lock(Y);          // A 嘗試取得 Y 的寫入鎖,被 B 阻塞
                        write_lock(X);          // B 嘗試取得 X 的寫入鎖,被 A 阻塞

此處,任務 A 等待任務 B 釋放 Y,而任務 B 等待任務 A 釋放 X,形成典型的鎖反轉死結。

相依性類型與強相依路徑

Lockdep 記錄的鎖相依性是一對鎖之間的獲取順序。由於鎖的持有者有三種類型(獨佔寫、非遞迴讀、遞迴讀),理論上會有九種相依性。但為了偵測死結,我們只需要四種相依性類型。

L1 -> L2 表示 lockdep 觀察到一個任務在已持有 L1 的情況下,嘗試獲取 L2。死結偵測的邏輯可以簡化為:我們是否可能在持有 L1 的同時,被 L2 的持有者阻塞?

因此,我們只關心兩件事:

  1. L1 會阻塞誰?
  2. 誰會阻塞 L2

基於此,我們可以將持有者的類型進行分組:

  • 對於 L1 (已持有的鎖):遞迴讀取者和非遞迴讀取者行為類似(它們都會阻塞寫入者),可歸為共享讀取者 (Shared reader, S)。寫入者自成一類,為獨佔寫入者 (Exclusive writer, E)。
  • 對於 L2 (要獲取的鎖):遞迴讀取者可以被視為一類,因為它們只被寫入者阻塞。寫入者和非遞迴讀取者行為類似(它們都會被等待中的寫入者阻塞),可歸為非遞迴持有者 (Non-recursive locker, N)。

這樣就產生 lockdep 圖 (graph) 中的四種相依性邊 (dependency edges):

  • -(ER)->:從 Exclusive writer 到 Recursive reader。X-(ER)->Y 表示 X 作為寫入鎖被持有的情況下,嘗試獲取 Y 作為遞迴讀取鎖
  • -(EN)->:從 Exclusive writer 到 Non-recursive locker
  • -(SR)->:從 Shared reader 到 Recursive reader
  • -(SN)->:從 Shared reader 到 Non-recursive locker

對於同一對鎖,它們之間可以存在多種相依性。例如:

任務 A:                 任務 B:
read_lock(X);           write_lock(X);
write_lock(Y);          write_lock(Y);

這會在相依性圖中建立 X-(SN)->Y(來自任務 A)和 X-(EN)->Y(來自任務 B)。

多個連續的相依性邊構成一條「路徑」(path)。我們進一步定義「強路徑 」(strong path),其定義為:路徑中任意連續的兩個邊 X->Y->Z 不會是 -(xR)->-(Sx)-> 的組合。

換句話說,在強路徑中,若 X->Y 是一個指向遞迴讀取者 Y 的邊(-(ER)->-(SR)->),那麼 Y->Z 的邊中,Y 不能是共享讀取者(即 Y->Z 不能是 -(SR)->-(SN)->)。這確保路徑上的每一步都是一個「硬等待」,而不是可以被遞迴讀取繞過的「軟等待」。

遞迴讀取死結偵測

引理 1 (充分性)
若相依性圖中存在一個封閉的強路徑 (closed strong path),那麼必定存在一種鎖定序列的組合會導致死結。

引理 2 (必要性)
若相依性圖中不存在封閉的強路徑,那麼任何鎖定序列的組合都不可能導致死結。

結合這兩個引理,我們可以得出結論:一個封閉的強路徑是死結發生的充分且必要條件。因此,偵測封閉的強路徑就等同於偵測死結。

引理 1 證明 (充分性):
假設我們有一個強路徑循環:L1 -> L2 -> ... -> Ln -> L1
我們可以構建一個死結場景:讓 n 個任務 P1, P2, , Pn 分別持有鎖 L1, L2, , Ln。

  • 任務 P1 持有 L1,並等待獲取 L2
  • 任務 P2 持有 L2,並等待獲取 L3
  • 任務 Pn 持有 Ln,並等待獲取 L1

因為這是一個強路徑,對於任意 Lx -> Lx+1,持有 Lx 的任務 Px 會被持有 Lx+1 的任務 Px+1 阻塞。這意味著每個任務都在等待下一個任務釋放鎖,形成一個無法解開的死結循環。

引理 2 證明 (必要性):
此引理等價於:若發生死結,那麼相依性圖中必定存在一個封閉的強路徑。
假設有 n 個任務 P1, , Pn 發生死結。每個任務 Px 都在等待下一個任務 P(x+1) 釋放它需要的鎖 Lx。

  • P1 持有 L(n),等待 P2 釋放 L1。這構成 Ln -> L1 的相依性。
  • P2 持有 L1,等待 P3 釋放 L2。這構成 L1 -> L2 的相依性。

這自然形成一個循環:L1 -> L2 -> ... -> Ln -> L1

接下來證明此循環是強路徑。對於任意一個鎖 Lx,任務 Px 貢獻 L(x-1) -> Lx 的邊,任務 P(x+1) 貢獻 Lx -> L(x+1) 的邊。因為 Px 正在等待 Lx,這意味著 P(x+1) 持有 Lx 的方式必須能阻塞 Px。若 L(x-1) -> Lx 是一個指向遞迴讀取者的邊(-(xR)->),而 Lx -> L(x+1) 是一個從共享讀取者出發的邊(-(Sx)->),那麼 P(x+1) 持有的 Lx 就是一個讀取鎖,而 Px 嘗試獲取 Lx 的行為是遞迴讀取。根據定義,這種情況不會發生阻塞。

因此,既然發生阻塞和死結,路徑中就不可能存在 -(xR)->-(Sx)-> 的組合,故此循環必為強路徑。