目錄鎖定¶
用於目錄操作的鎖定方案基於兩種鎖：每 inode 鎖（->i_rwsem）和每檔案系統鎖（->s_vfs_rename_mutex）。
當在多個非目錄物件上獲取 i_rwsem 時，我們總是按地址遞增的順序獲取鎖。在下文中，我們稱之為“inode 指標”順序。
原語¶
就我們的目的而言，所有操作分為 6 類
讀訪問。鎖定規則
鎖定我們正在訪問的目錄（共享）
物件建立。鎖定規則
鎖定我們正在訪問的目錄（獨佔）
物件刪除。鎖定規則
鎖定父目錄（獨佔）
找到受害者
鎖定受害者（獨佔）
連結建立。鎖定規則
鎖定父目錄（獨佔）
檢查源不是目錄
鎖定源（獨佔；可能可以弱化為共享）
非跨目錄重新命名。鎖定規則
鎖定父目錄（獨佔）
找到源和目標
決定源和目標中哪些需要被鎖定。如果源是非目錄，則需要鎖定；如果目標是非目錄或即將被移除，則需要鎖定。
獲取需要獲取的鎖（獨佔），如果需要同時獲取兩者（只有當源和目標都是非目錄時才會發生這種情況——源因為它在其他情況下不需要被鎖定，目標因為目錄和非目錄的混合只允許與 RENAME_EXCHANGE 一起使用，並且這不會移除目標），則按 inode 指標順序。
跨目錄重新命名。這批中最棘手的一個。鎖定規則
鎖定檔案系統
如果父目錄沒有共同祖先，操作失敗。
按“祖先優先”順序鎖定父目錄（獨佔）。如果兩者都不是另一個的祖先，則首先鎖定源的父目錄。
找到源和目標。
驗證源不是目標的子孫，目標不是源的子孫；否則操作失敗。
鎖定涉及的子目錄（獨佔），源在目標之前。
鎖定涉及的非目錄（獨佔），按 inode 指標順序。
上述規則顯然保證了所有將透過該方法進行讀取、修改或刪除的目錄都將被呼叫者鎖定。
拼接¶
還有一件事需要考慮——拼接。它本身不是一個獨立的操作；它可能作為查詢的一部分發生。我們談論的是目錄樹上的操作，但我們顯然沒有這些操作的完整圖景——特別是對於網路檔案系統。我們所擁有的是 dcache 中可見的一堆子樹，並且鎖定發生在這些子樹上。樹隨著我們執行操作而增長；記憶體壓力會修剪它們。通常這不是問題，但有一個棘手的轉折——當一棵正在增長的樹達到另一棵的根時，我們應該怎麼做？這可能發生在幾種場景中，從“有人從同一個 NFS4 伺服器掛載了兩個巢狀的子樹，並在其中一箇中進行查詢時達到了另一個的根”開始；還有 open-by-fhandle 的東西，並且我們看到的一個目錄可能被伺服器移動到另一個地方，當我們在進行查詢時會遇到它。
由於很多原因，我們希望同一個目錄在 dcache 中只存在一次。不允許有多個別名。因此，當查詢遇到一個已經有別名的子目錄時，需要對 dcache 樹做些什麼。查詢操作已經持有父目錄的鎖。如果別名是一個獨立樹的根，它將被附加到我們正在查詢的目錄中，以我們正在查詢的名稱。如果別名已經是我們正在查詢的目錄的子項，它會將其名稱更改為我們正在查詢的名稱。這兩種情況不涉及額外的鎖定。然而，如果它是其他目錄的子項，事情就變得棘手了。首先，我們驗證它不是我們目錄的祖先，如果是，則查詢失敗。然後我們嘗試鎖定檔案系統和別名的當前父目錄。如果任何一個嘗試鎖定失敗，我們就會查詢失敗。如果嘗試鎖定成功，我們將別名從其當前父目錄中分離出來，並將其附加到我們的目錄中，以我們正在查詢的名稱。
請注意，拼接不涉及對檔案系統的任何修改；我們所改變的只是 dcache 中的檢視。此外，獨佔持有目錄鎖可以防止涉及其子項的此類更改，而持有檔案系統鎖可以防止任何樹拓撲結構的更改，除了一個樹的根成為另一個目錄的子項。特別是，如果在獲取檔案系統鎖後發現兩個 dentries 具有共同祖先，它們的關係將保持不變，直到鎖被釋放。因此，從目錄操作的角度來看，拼接幾乎無關緊要——它唯一重要的地方是跨目錄重新命名中的一步；我們需要在檢查父目錄是否具有共同祖先時小心。
多檔案系統內容¶
對於某些檔案系統，某個方法可能涉及對另一個檔案系統的目錄操作；可能是 ecryptfs 在底層檔案系統中執行操作，overlayfs 對層進行操作，網路檔案系統使用本地檔案系統作為快取等。在所有這些情況下，對其他檔案系統的操作必須遵循相同的鎖定規則。此外，“此檔案系統上的目錄操作可能涉及彼檔案系統上的目錄操作”應該是一種非對稱關係（或者，如果你願意，應該可以對檔案系統進行排序，以便檔案系統上的目錄操作只能觸發排名更高的檔案系統上的目錄操作——以這些術語來說，overlayfs 排名低於其層，網路檔案系統排名低於它快取的物件等）。
避免死鎖¶
如果任何目錄都不是它自己的祖先，則上述方案是無死鎖的。
證明
鎖上存在一個排名，使得所有原語都按非遞減的排名順序獲取它們。即，
按 inode 指標順序，在給定檔案系統上的非目錄的 ->i_rwsem 排名。
將檔案系統上所有目錄的 ->i_rwsem 置於相同排名，低於同一檔案系統上任何非目錄的 ->i_rwsem。
將 ->s_vfs_rename_mutex 置於低於同一檔案系統上任何 ->i_rwsem 的排名。
在不同檔案系統上的鎖之間，使用這些檔案系統的相對排名。
例如，如果我們有一個在本地檔案系統上快取的 NFS 檔案系統，我們有
NFS 檔案系統的 ->s_vfs_rename_mutex
該 NFS 檔案系統上目錄的 ->i_rwsem，所有目錄的排名相同
該檔案系統上非目錄的 ->i_rwsem，按 inode 地址遞增的順序
本地檔案系統的 ->s_vfs_rename_mutex
本地檔案系統上目錄的 ->i_rwsem，所有目錄的排名相同
本地檔案系統上非目錄的 ->i_rwsem，按 inode 地址遞增的順序。
很容易驗證操作永遠不會獲取排名低於已持有的鎖的鎖。
假設可能發生死鎖。考慮最小的死鎖執行緒集。它是一個由多個執行緒組成的迴圈，每個執行緒都阻塞在迴圈中下一個執行緒所持有的鎖上。
由於鎖定順序與排名一致，最小死鎖中所有競爭的鎖都將具有相同的排名，即它們都將是同一檔案系統上目錄的 ->i_rwsem。此外，不失一般性地，我們可以假設所有操作都直接在該檔案系統上完成，並且它們都沒有真正達到方法呼叫。
換句話說，我們有一個由執行緒 T1, ..., Tn 組成的迴圈，以及相同數量的目錄 (D1, ..., Dn)，使得
T1 被 D1 阻塞，D1 由 T2 持有
T2 被 D2 阻塞，D2 由 T3 持有
...
Tn 被 Dn 阻塞，Dn 由 T1 持有。
最小迴圈中的每個操作都必須至少鎖定了一個目錄，並在嘗試鎖定另一個目錄時被阻塞。這隻剩下 3 種可能的操作：目錄刪除（先鎖定父目錄，再鎖定子目錄）、殺死子目錄的同目錄重新命名（同上）以及某種跨目錄重新命名。
集合中必須有一個跨目錄重新命名；事實上，如果所有操作都是“先鎖定父目錄，再鎖定子目錄”型別，那麼我們將得到 Dn 是 D1 的父目錄，D1 是 D2 的父目錄，D2 是 D3 的父目錄，……，Dn 是 Dn 的父目錄。關係不可能在目錄鎖獲取後發生改變，因此它們將在死鎖時同時成立，並且我們將得到一個迴圈。
由於所有操作都在同一檔案系統上，因此其中不會有多個跨目錄重新命名。不失一般性，我們可以假設 T1 是執行跨目錄重新命名的執行緒，而所有其他操作都是“先鎖定父目錄，再鎖定子目錄”型別。
換句話說，我們有一個跨目錄重新命名操作，它鎖定了 Dn 並在嘗試鎖定 D1 時被阻塞，其中 D1 是 D2 的父目錄，D2 是 D3 的父目錄，……，D 是 Dn 的父目錄。D1, ..., Dn 之間的關係在死鎖時同時成立。此外，跨目錄重新命名在獲取檔案系統鎖並驗證所涉及目錄具有共同祖先之前不會鎖定任何目錄，這保證了它們之間祖先關係是穩定的。
考慮跨目錄重新命名鎖定目錄的順序；先鎖定父目錄，然後可能鎖定其子目錄。Dn 和 D1 必須在其中，且 Dn 在 D1 之前被鎖定。會是哪一對呢？
它不可能是父目錄——事實上，由於 D1 是 Dn 的祖先，它將是第一個被鎖定的父目錄。因此，至少有一個子目錄必須涉及，因此它們都不會是另一個的子孫——否則操作將不會在鎖定父目錄之後進行。
它不可能是父目錄和它的子目錄；否則我們會有一個迴圈，因為父目錄在子目錄之前被鎖定，所以父目錄必須是其子目錄的後代。
它也不能是父目錄和另一個父目錄的子目錄。否則，相關父目錄的子目錄將是另一個子目錄的後代。
這隻剩下一種可能性——即，Dn 和 D1 都屬於子目錄，以某種順序。但這也是不可能的，因為兩個子目錄都不是另一個的後代。
至此證明完畢，因為具有最小死鎖所需屬性的操作集無法存在。
請注意，跨目錄重新命名中檢查是否存在共同祖先至關重要——沒有它就可能發生死鎖。事實上，假設父目錄最初位於不同的樹中；我們將鎖定源的父目錄，然後嘗試鎖定目標的父目錄，結果卻有一個不相關的查詢將源的遠祖先與目標父目錄的某個遠子孫拼接起來。此時，跨目錄重新命名持有源父目錄的鎖，並試圖鎖定其遠祖先。再加上對中間所有目錄的一堆 rmdir() 嘗試（如果它們曾經獲得過鎖，所有這些都將失敗並返回 -ENOTEMPTY），瞧——我們就死鎖了。
避免迴圈¶
這些操作保證避免迴圈建立。事實上，唯一可能引入迴圈的操作是跨目錄重新命名。假設操作後存在一個迴圈；由於操作前不存在這樣的迴圈，那麼該迴圈中至少有一個節點的父目錄發生了改變。換句話說，迴圈必須經過源，或者，在交換的情況下，可能經過目標。
由於操作成功，源和目標都不會是彼此的祖先。因此，從源的父目錄開始的祖先鏈不可能經過目標，反之亦然。另一方面，任何節點的祖先鏈不可能經過節點本身，否則我們會在操作前就有一個迴圈。但除了源和目標之外，所有其他節點在操作後都保留了父目錄，因此操作不會改變源和目標（前）父目錄的祖先鏈。特別是，這些鏈在有限步數後必須終止。
現在考慮操作建立的迴圈。它透過源或目標；迴圈中的下一個節點將是目標或源的前父目錄。之後，迴圈將沿著該父目錄的祖先鏈。但正如我們剛剛所示，該鏈在有限步數後必須終止，這意味著它不可能成為任何迴圈的一部分。證畢。
雖然此鎖定方案適用於任意 DAG，但它依賴於檢查目錄是否為另一個物件的子孫的能力。當前實現假設目錄圖是一棵樹。此假設也由所有操作保持（在不會引入迴圈的樹上進行跨目錄重新命名將使其保持為樹，並且 link() 對於目錄會失敗）。
請注意，上面提到的“目錄”==“任何可能擁有子目錄的物件”，因此如果我們要引入混合物件，我們需要確保 link(2) 對它們不起作用，或者修改 is_subdir() 以使其在存在此類“野獸”的情況下也能工作。