目录锁¶
用于目录操作的锁定方案基于两种锁 - 每个 inode 的锁 (->i_rwsem) 和每个文件系统的锁 (->s_vfs_rename_mutex)。
当在多个非目录对象上获取 i_rwsem 时，我们总是按照地址递增的顺序获取锁。在下文中，我们将其称为“inode 指针”顺序。
原语¶
为了我们的目的，所有操作分为 6 类
读取访问。锁定规则
锁定我们正在访问的目录（共享）
对象创建。锁定规则
锁定我们正在访问的目录（独占）
对象删除。锁定规则
锁定父目录（独占）
找到要删除的对象
锁定要删除的对象（独占）
链接创建。锁定规则
锁定父目录（独占）
检查源是否不是目录
锁定源（独占；可能可以弱化为共享）
_非_跨目录的重命名。锁定规则
锁定父目录（独占）
找到源和目标
决定需要锁定源和目标中的哪个。如果源是非目录，则需要锁定源；如果目标是非目录或即将被删除，则需要锁定目标。
获取需要获取的锁（独占），如果需要同时获取两个锁，则按照 inode 指针顺序获取（只有当源和目标都是非目录时才会发生这种情况 - 源因为否则不需要锁定，而目标因为只有 RENAME_EXCHANGE 才允许混合目录和非目录，而这不会删除目标）。
跨目录重命名。这是最棘手的一个。锁定规则
锁定文件系统
如果父目录没有共同的祖先，则操作失败。
按照“祖先优先”的顺序锁定父目录（独占）。如果两者都不是彼此的祖先，则先锁定源的父目录。
找到源和目标。
验证源不是目标的后代，目标也不是源的后代；否则操作失败。
锁定涉及的子目录（独占），先锁定源，再锁定目标。
按照 inode 指针顺序锁定涉及的非目录（独占）。
上面的规则显然保证了方法将要读取、修改或删除的所有目录都将被调用者锁定。
拼接¶
还有一件事需要考虑 - 拼接。它本身不是一个操作；它可能会作为查找的一部分发生。我们讨论的是目录树上的操作，但我们显然没有它们的完整视图 - 特别是对于网络文件系统。我们拥有的是 dcache 中可见的一组子树，并且锁定发生在这些子树上。当我们执行操作时，树会增长；内存压力会修剪它们。通常这不是问题，但有一个讨厌的转折 - 当一个增长的树到达另一个树的根时，我们应该做什么？这可能在几种情况下发生，从“有人从同一个 NFS4 服务器挂载了两个嵌套的子树，并且在其中一个子树中进行查找已到达另一个子树的根”开始；还有 open-by-fhandle 的内容，并且有可能我们在一个地方看到的目录被服务器移动到另一个地方，并且当进行查找时会遇到它。
出于多种原因，我们希望同一个目录在 dcache 中只出现一次。不允许存在多个别名。因此，当查找遇到已经有别名的子目录时，需要对 dcache 树进行一些处理。查找已经持有父目录的锁。如果别名是独立树的根，它将被附加到我们正在查找的目录中，以我们正在查找的名称附加。如果别名已经是我们正在查找的目录的子目录，则它会更改名称为我们正在查找的名称。在这两种情况下，不涉及额外的锁定。但是，如果它是某个其他目录的子目录，则事情会变得棘手。首先，我们验证它_不是_我们目录的祖先，如果它是，则查找失败。然后我们尝试锁定文件系统和别名的当前父目录。如果任何 trylock 失败，则查找失败。如果 trylock 成功，我们会将别名从其当前父目录分离，并以我们正在查找的名称附加到我们的目录。
请注意，拼接_不_涉及对文件系统的任何修改；我们所更改的只是 dcache 中的视图。此外，持有目录的独占锁定可以防止涉及其子目录的此类更改，并且持有文件系统锁可以防止任何树拓扑的更改，除了使一棵树的根成为另一棵树中目录的子目录。特别是，如果在获取文件系统锁之后发现两个目录条目具有共同的祖先，它们的关系将保持不变，直到锁被释放。因此，从目录操作的角度来看，拼接几乎无关紧要 - 它唯一重要的地方是跨目录重命名中的一个步骤；我们需要小心检查父目录是否具有共同的祖先。
多文件系统内容¶
对于某些文件系统，一个方法可能涉及对另一个文件系统执行目录操作；可能是 ecryptfs 在底层文件系统中进行操作，overlayfs 对层进行操作，网络文件系统使用本地文件系统作为缓存等。在所有这些情况下，对其他文件系统的操作必须遵循相同的锁定规则。此外，“在此文件系统上执行目录操作可能会涉及在该文件系统上执行目录操作”应该是不对称的关系（或者，如果愿意，应该可以对文件系统进行排名，以便在文件系统上执行目录操作只能触发在排名较高的文件系统上执行的目录操作 - 在这些方面，overlayfs 的排名低于其层，网络文件系统的排名低于它在上面缓存的任何东西，等等。）
避免死锁¶
如果没有任何目录是它自己的祖先，则上述方案是无死锁的。
证明
锁上有一个排名，这样所有的原语都按照非递减的排名顺序获取它们。即，
给定文件系统上的非目录的 rank ->i_rwsem，按 inode 指针顺序排列。
将文件系统上所有目录的 rank ->i_rwsem 放在同一级别，低于同一文件系统上任何非目录的 ->i_rwsem。
将 ->s_vfs_rename_mutex 放在低于同一文件系统上任何 ->i_rwsem 的级别。
在不同文件系统上的锁之间，使用这些文件系统的相对排名。
例如，如果我们有一个在本地文件系统上缓存的网络文件系统，我们有
网络文件系统的 ->s_vfs_rename_mutex
该网络文件系统上目录的 ->i_rwsem，所有目录的排名相同
该文件系统上非目录的 ->i_rwsem，按 inode 地址递增的顺序排列
本地文件系统的 ->s_vfs_rename_mutex
本地文件系统上目录的 ->i_rwsem，所有目录的排名相同
本地文件系统上非目录的 ->i_rwsem，按 inode 地址递增的顺序排列。
很容易验证，操作永远不会获取排名低于已持有锁的锁。
假设可能出现死锁。考虑最小的死锁线程集。这是一个由多个线程组成的循环，每个线程都阻塞在循环中下一个线程持有的锁上。
由于锁定顺序与排名一致，因此最小死锁中的所有争用锁都将具有相同的排名，即它们都将是同一文件系统上目录的 ->i_rwsem。此外，在不失一般性的情况下，我们可以假设所有操作都是直接在该文件系统上完成的，并且它们实际上都没有到达方法调用。
换句话说，我们有一个线程循环 T1,..., Tn，以及相同数量的目录 (D1,...,Dn)，使得
T1 阻塞在 T2 持有的 D1 上
T2 阻塞在 T3 持有的 D2 上
...
Tn 阻塞在 T1 持有的 Dn 上。
最小循环中的每个操作都必须至少锁定一个目录，并且在尝试锁定另一个目录时阻塞。这只剩下 3 个可能的操作：目录删除（锁定父目录，然后锁定子目录）、杀死子目录的同一目录重命名（同上）和某种形式的跨目录重命名。
集合中必须有一个跨目录重命名；实际上，如果所有操作都是“锁定父目录，然后锁定子目录”类型，那么 Dn 将是 D1 的父目录，D1 是 D2 的父目录，D2 是 D3 的父目录，...，Dn 的父目录。自获取目录锁的那一刻起，关系就不可能发生变化，因此它们会在死锁时同时持有，并且我们会有一个循环。
由于所有操作都在同一个文件系统上，因此它们之间不可能有超过一个跨目录重命名。在不失一般性的情况下，我们可以假设 T1 是执行跨目录重命名的那个，而其他所有操作都是“锁定父目录，然后锁定子目录”类型。
换句话说，我们有一个跨目录重命名，它锁定了 Dn，并且在尝试锁定 D1 时阻塞，而 D1 是 D2 的父目录，D2 是 D3 的父目录，...，Dn 的父目录。D1,...,Dn 之间的关系在死锁时同时成立。此外，跨目录重命名在获取文件系统锁并验证所涉及的目录具有共同的祖先之前不会锁定任何目录，这保证了它们之间所有祖先关系的稳定。
考虑跨目录重命名锁定目录的顺序；先锁定父目录，然后可能锁定其子目录。Dn 和 D1 必须在其中，Dn 在 D1 之前锁定。是哪一对？
不可能是父节点——实际上，由于 D1 是 Dn 的祖先，它应该是第一个被锁定的父节点。因此，至少有一个子节点参与其中，并且它们都不是彼此的后代——否则操作在锁定父节点时就不会继续进行。
不可能是父节点和它的子节点；否则会出现循环，因为父节点在子节点之前被锁定，所以父节点必须是其子节点的后代。
也不可能是父节点和另一个父节点的子节点。否则，该父节点的子节点将是另一个子节点的后代。
只剩下一种可能性——即，Dn 和 D1 都在子节点中，以某种顺序。但这也不可能，因为子节点都不是彼此的后代。
至此，证明结束，因为不存在具有最小死锁所需属性的操作集合。
请注意，跨目录重命名中检查是否存在共同祖先至关重要——没有它，可能会出现死锁。实际上，假设父节点最初在不同的树中；我们会锁定源的父节点，然后尝试锁定目标的父节点，却发现不相关的查找操作将源的远祖先连接到目标父节点的远后代。此时，我们有跨目录重命名持有源父节点的锁，并尝试锁定其远祖先。在所有中间目录上添加一堆 rmdir() 尝试（如果它们获得了锁，所有这些尝试都会因 -ENOTEMPTY 而失败），然后瞧——我们遇到了死锁。
避免循环¶
这些操作保证可以避免创建循环。实际上，唯一可能引入循环的操作是跨目录重命名。假设操作后出现循环；由于在操作之前没有这样的循环，因此该循环中至少有一个节点的父节点发生了更改。换句话说，该循环必须经过源节点，或者在交换的情况下，可能经过目标节点。
由于操作已成功，因此源节点和目标节点都不能是彼此的祖先。因此，从源节点的父节点开始的祖先链不可能经过目标节点，反之亦然。另一方面，任何节点的祖先链都不可能经过节点本身，否则我们在操作之前就会出现循环。但是，除了源节点和目标节点之外的所有节点在操作后都保留了父节点，因此操作不会更改源节点和目标节点（前）父节点的祖先链。特别是，这些链必须在有限的步数后结束。
现在考虑由操作创建的循环。它经过源节点或目标节点；循环中的下一个节点将分别是目标节点或源节点的前父节点。之后，循环将跟随该父节点的祖先链。但是，正如我们刚才所展示的，该链必须在有限的步数后结束，这意味着它不可能成为任何循环的一部分。证毕。
虽然此锁定方案适用于任意 DAG，但它依赖于检查目录是否为另一个对象的后代的能力。当前实现假定目录图是一棵树。此假设也由所有操作保留（对不会引入循环的树执行的跨目录重命名会使其保持为树，并且 link() 对目录失败）。
请注意，上述中的“目录” == “任何可能有子项的东西”，因此，如果我们引入混合对象，我们需要确保 link(2) 对它们不起作用，或者在 is_subdir() 中进行更改，使其即使在存在这种怪物的情况下也能正常工作。