LINUX LOCKDEP
1 依賴鎖

關於依賴鎖的參考文件是 linux/Documentation/lockdep-design.txt。 致能器(validator)運作的基本物件是鎖類別，而鎖類別是一群應用於相同鎖規則的鎖的集合。 例如 inode 結構中的鎖就是一種鎖的類別，而 inode 可能會有上千個 inode 實例 (instantiation)。 核心透過依賴鎖的方式，處理物件的存取，因為在多工的環境中，任何物件的存取都有可能發生衝突，必須透過鎖的機制加以錯開。

致能器追蹤鎖類別的狀態和鎖類別之間的相依性，並輪流確認鎖類別的狀態和相依性是正確的。

鎖類別狀態：
致能器追蹤鎖類別的使用紀錄，分成 4n+1 個別狀態位元。 鎖的狀態多應用於保持狀態內文，做為狀態內文的讀取鎖，或應用於狀態致能，做為狀態致能鎖。 狀態可以是硬體中斷(hardirq)、軟體中斷(softirq)、取得檔案系統(reclaim_fs)。 

linux/kernel/lockdep_states.h
01 LOCKDEP_STATE(HARDIRQ)
02 LOCKDEP_STATE(SOFTIRQ)
03 LOCKDEP_STATE(RECLAIM_FS)

當違反鎖規則時，就會將狀態位元值以大括號方式，顯示於鎖的錯誤訊息。 一個人為的錯誤例子是，當使用 modprobe 嘗試去取得一個鎖，而這個鎖卻已經被一個任務取得，此時就會產生鎖的違例。 此時就會產生如下面的訊息。 

01    modprobe/2287 is trying to acquire lock:
01     (&sio_locks[i].lock){-.-...}, at: [] mutex_lock+0x21/0x24
01 
01    but task is already holding lock:
01     (&sio_locks[i].lock){-.-...}, at: [] mutex_lock+0x21/0x24

大括號內的符號定義是，小點 (.) 表示 IRQ 除能，並且不在 IRQ 內執行。
減號 (-) 表示 IRQ 除能，並且在 IRQ 內執行。
減號 (+) 表示 IRQ 致能，但不在 IRQ 內執行。
減號 (?) 表示 IRQ 致能，並且在 IRQ 內執行。

2 鎖的規則
2.1 單層鎖的規則

軟體中斷不安全鎖的鎖類別等同於硬體中斷不安全鎖的鎖類別。
下面的狀態是互斥的狀態，同時間只有一個會成立。

軟體中斷不安全狀態或軟體中斷安全狀態。
硬體中斷不安全狀態或硬體中斷安全狀態。

致能器會偵測並報告鎖使用上的違例。

2.2 多重鎖的規則

同樣的鎖類別不能被取得兩次，否則有可能導致鎖死(dead lock)。
再者，兩個鎖必須用同樣的次序取得，不然有可能導致反轉鎖死(inversion deadlock)。 致能器會找出像這種任意複雜的相依性，例如可能會有多種取得鎖的順序，致能器會追蹤鎖之間的所有相依性。
又再者，中斷類別的鎖不適用於任何兩個鎖類別的鎖依賴。這是因為取得硬體中斷安全鎖的硬體中斷程序會干擾硬體中斷不安全鎖，而導致鎖的反轉鎖死。中斷的發生是沒有順序可言的。 同理，軟體中斷不安全鎖亦是如此。
當上述的一個鎖類別改變狀態時，會強制執行下面的鎖動作。
當發現一個新的硬體中斷安全鎖，檢查他是否持有過任何硬體中斷不安全鎖。
當發現一個新的軟體中斷安全鎖，檢查他是否持有過任何軟體中斷安全鎖。
當發現一個新的硬體中斷不安全鎖，檢查他是否持有過任何硬體中斷不安全鎖。
當發現一個新的軟體中斷不安全鎖，檢查他是否持有過任何軟體中斷安全鎖。

再次地，也檢查中斷程式打岔了可能會引發反轉鎖死的中斷安全鎖或中斷不安全鎖，即使實際上還尚未發生。

2.3 巢狀鎖

例外情況是巢狀資料相依性所導致的巢狀鎖 (nest locking)。 核心在少數狀況下會取得不只一個相同鎖類型的實例(instantiation)。 這些狀況通常是發生於按照某些階層排列的相同類型物件。 在這些狀況中，兩個物件間存在著一種自然的次序，核心以這種固定的次序取得物件的鎖。

由這種物件階層導致的巢狀鎖的一個例子是，整個磁碟的區塊裝置物件和分割區區塊裝置物件。 二者都是區塊裝置物件(block device)，分割區是整個磁碟的一部分。 取得整個磁碟的鎖會高於取得一個分割區的鎖，這是完全正確的。 在這種次序下的鎖規則不是靜態的，致能器不會自動地偵測到這種自然的次序。 為了讓致能器知道這種正確的使用模型，有不同鎖法的新版本的被加進來，以允許指定巢狀層級。
一個給區塊裝置互斥機制的範例呼叫，像下面的類別。 

01 enum bdev_bd_mutex_lock_class{
01        BD_MUTEX_NORMAL,
01        BD_MUTEX_WHOLE,
01        BD_MUTEX_PARTITION
01 };
01 
01 mutex_lock_nested(&bdev->bd_contains->bd_mutex, BD_MUTEX_PARTITION);

在這樣的情況下，鎖住一個已經為分割區的區塊物件。 致能器會以另一個類別(子類別)對這樣一個巢狀類型的物件。 要注意的是，當使用巢狀函式方法時，要小心並且徹底檢查階層是否有正確的對映，否則會產生錯誤允許或是錯誤拒絕。

2.4 依賴鎖的結構群

linux/kernel/lockdep.h
01 struct lock_class {
01     struct list_head   hash_entry;
01     struct list_head   lock_entry;
01     struct lockdep_subclass_key *key;
01     unsigned int       subclass;
01     unsigned int       dep_gen_id;
01     unsigned long      usage_mask;
01     struct stack_trace usage_traces[XXX_LOCK_USAGE_STATES];
01     struct list_head   locks_after, locks_before;
01     unsigned int       version;
01     unsigned long      ops;
01     const char         *name;
01     int                name_version;
01 };


linux/kernel/lockdep.h
01 struct lock_class_stats {
01     unsigned long    contention_point[4];
01     unsigned long    contending_point[4];
01     struct lock_time read_waittime;
01     struct lock_time write_waittime;
01     struct lock_time read_holdtime;
01     struct lock_time write_holdtime;
01     unsigned long    bounces[nr_bounce_types];
01 };


linux/kernel/lockdep.h
01 struct lockdep_map {
01     struct lock_class_key *key;
01     struct lock_class     *class_cache[NR_LOCKDEP_CACHING_CLASSES];
01     const char            *name;
01 };


linux/kernel/lockdep.h
01 struct lock_list {
01     struct list_head   entry;
01     struct lock_class  *class;
01     struct stack_trace trace;
01     int                distance;
01     struct lock_list   *parent;
01 };


linux/kernel/lockdep.h
01 struct lock_chain {
01     u8                irq_context;
01     u8                depth;
01     u16               base;
01     struct list_head  entry;
01     u64               chain_key;
01 };


linux/kernel/lockdep.h
01 struct held_lock {
01     u64                prev_chain_key;
01     unsigned long      acquire_ip;
01     struct lockdep_map *instance;
01     struct lockdep_map *nest_lock;
01     unsigned int       class_idx:MAX_LOCKDEP_KEYS_BITS;
01     unsigned int irq_context:2;
01     unsigned int trylock:1;                        
01     unsigned int read:2;
01     unsigned int check:2;
01     unsigned int hardirqs_off:1;
01     unsigned int references:11;
01 };

2.5 依賴鎖的函式庫
函式名稱說明
lockdep_init函式說明。
lockdep_info函式說明。
lockdep_reset函式說明。
lockdep_reset_lock函式說明。
lockdep_free_key_range函式說明。
lockdep_sys_exit函式說明。
lockdep_off函式說明。
lockdep_on函式說明。
lockdep_init_map函式說明。
lock_acquire函式說明。
lock_release函式說明。
lock_is_held函式說明。
lock_set_class函式說明。
lock_set_class函式說明。
lockdep_set_current_reclaim_state函式說明。
lockdep_clear_current_reclaim_state函式說明。
lockdep_trace_alloc函式說明。
lock_contended函式說明。
lock_acquired函式說明。