目录锁定¶
用于目录操作的锁定方案基于两种锁：每 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() 以使其在存在此类“野兽”的情况下也能工作。