路径名查找

本文基于 lwn.net 上发表的三篇文章：

由 Neil Brown 撰写，Al Viro 和 Jon Corbet 协助。此后已更新，以反映内核中的更改，包括

  • 每目录并行名称查找。

  • openat2() 解析限制标志。

路径名查找简介

路径名查找最明显的方面，几乎无需深入探索即可发现，就是其复杂性。它包含许多规则、特殊情况和实现替代方案，这些都可能让粗心的读者感到困惑。计算机科学早就熟悉这种复杂性，并拥有帮助管理它的工具。我们将广泛使用的一种工具是“分而治之”。在分析的早期部分，我们将把符号链接（symlinks）分开处理——把它们留到最后一部分。在处理符号链接之前，我们还有另一个重要的划分，它是基于 VFS 的锁定方法，这将使我们能够单独回顾“REF-walk”和“RCU-walk”。但我们有些超前了。首先我们需要澄清一些重要的低级区别。

有两种...

路径名（有时也称为“文件名”）用于标识文件系统中的对象，大多数读者对此都很熟悉。它们包含两种元素：“斜杠”，即一个或多个“/”字符的序列；以及“组件”，即一个或多个非“/”字符的序列。这些形成两种路径。以斜杠开头的路径是“绝对路径”，从文件系统根目录开始。其他路径是“相对路径”，从当前目录开始，或者从通过文件描述符指定给“*at()”系统调用（例如 openat()）的某个其他位置开始。

描述第二种路径以组件开头很吸引人，但这并不总是准确的：路径名可以既没有斜杠也没有组件，换句话说，它可以是空的。这在 POSIX 中通常是禁止的，但 Linux 中的一些“*at()”系统调用在给定 AT_EMPTY_PATH 标志时允许这样做。例如，如果你有一个指向可执行文件的打开文件描述符，你可以通过调用 execveat() 并传递该文件描述符、一个空路径和 AT_EMPTY_PATH 标志来执行它。

这些路径可以分为两部分：最终组件和其余部分。“其余部分”是简单的部分。在所有情况下，它必须标识一个已存在的目录，否则将报告 ENOENT 或 ENOTDIR 等错误。

最终组件则不那么简单。不仅不同的系统调用对其解释大相径庭（例如，有些创建它，有些不创建），而且它甚至可能不存在：空路径名和仅由斜杠组成的路径名都没有最终组件。如果它确实存在，它可能是“.”或“..”，这些与其它组件的处理方式截然不同。

如果路径名以斜杠结尾，例如“/tmp/foo/”，可能很想认为它有一个空的最终组件。在许多方面，这会产生正确的结果，但并非总是如此。特别是，mkdir() 和 rmdir() 都创建或删除由最终组件命名的目录，并且它们被要求能够处理以“/”结尾的路径名。根据 POSIX：

包含至少一个非斜杠字符并以一个或多个尾随斜杠字符结尾的路径名，除非尾随斜杠字符之前的最后一个路径名组件命名一个现有目录，或者是在路径名解析后立即为一个目录创建的目录项，否则将无法成功解析。

Linux 路径遍历代码（主要在 fs/namei.c 中）处理所有这些问题：将路径分解为组件，将“其余部分”与最终组件完全分开处理，并检查尾随斜杠是否未在不允许的地方使用。它还解决了并发访问的重要问题。

当一个进程正在查找路径名时，另一个进程可能正在进行会影响该查找的更改。一个相当极端的例子是，如果“a/b”被重命名为“a/c/b”，而另一个进程正在查找“a/b/..”，那么该进程可能会成功解析到“a/c”。大多数竞态条件要微妙得多，路径名查找的一大部分任务就是防止它们产生破坏性影响。许多可能的竞态条件在“dcache”的上下文中表现得最清楚，理解它对于理解路径名查找至关重要。

不仅仅是缓存

“dcache”缓存每个文件系统中关于名称的信息，以便快速查找。每个条目（称为“dentry”）包含三个重要字段：组件名称、指向父 dentry 的指针以及指向“inode”的指针，inode 包含该父目录中具有给定名称的对象的更多信息。inode 指针可以为 NULL，表示该名称在父目录中不存在。虽然目录的 dentry 中可能存在指向子目录 dentry 的链接，但该链接不用于路径名查找，因此在此不予考虑。

dcache 除了加速查找之外还有许多用途。其中一个特别相关的是它与挂载表紧密集成，挂载表记录了哪个文件系统挂载在哪里。挂载表实际存储的是哪个 dentry 挂载在哪个其他 dentry 之上。

考虑 dcache 时，我们又遇到了“两种类型”的区别：文件系统有两种类型。

一些文件系统确保 dcache 中的信息始终完全准确（尽管不一定完整）。这使得 VFS 可以在不检查文件系统的情况下确定特定文件是否存在，并意味着 VFS 可以保护文件系统免受某些竞态条件和其他问题的影响。这些通常是“本地”文件系统，例如 ext3、XFS 和 Btrfs。

其他文件系统不提供该保证，因为它们不能。这些通常是跨网络共享的文件系统，无论是像 NFS 和 9P 这样的远程文件系统，还是像 ocfs2 或 cephfs 这样的集群文件系统。这些文件系统允许 VFS 重新验证缓存的信息，并且必须提供自己的保护以防止棘手的竞态条件。VFS 可以通过 dentry 中设置的 DCACHE_OP_REVALIDATE 标志来检测这些文件系统。

REF-walk：使用引用计数和自旋锁的简单并发管理

在对所有这些划分进行了仔细分类之后，我们现在可以开始研究路径遍历的实际过程。特别是，我们将从路径名中“其余部分”的处理开始，并重点关注“REF-walk”并发管理方法。如果你忽略所有仅在设置了“LOOKUP_RCU”（表示使用 RCU-walk）时运行的地方，此代码可以在 link_path_walk() 函数中找到。

REF-walk 在锁和引用计数方面相当“强硬”。虽然不像过去“大内核锁”时代那样强硬，但肯定不害怕在需要时获取锁。它使用了各种不同的并发控制机制。这里假设读者对各种原语有背景知识，或者可以从其他地方（例如 Meet the Lockers）了解它们。

REF-walk 使用的锁定机制包括：

dentry->d_lockref

这使用 lockref 原语来提供自旋锁和引用计数。这个原语的特别之处在于，概念上的“锁定；增加引用计数；解锁”序列通常可以通过单个原子内存操作完成。

持有 dentry 的引用可确保 dentry 不会突然被释放并用于其他目的，从而使各种字段中的值按预期运行。它还在一定程度上保护了对 inode 的 ->d_inode 引用。

dentry 及其 inode 之间的关联是相当永久的。例如，当文件重命名时，dentry 和 inode 会一起移动到新位置。当文件创建时，dentry 最初将是负的（即 d_inode 为 NULL），并将在创建过程中分配给新的 inode。

当文件被删除时，这可以在缓存中通过两种方式反映：一是将 d_inode 设置为 NULL，二是从用于在父目录中查找名称的哈希表（稍后描述）中移除它。如果 dentry 仍在被使用，则使用第二种选项，因为在文件被删除后继续使用打开的文件是完全合法的，并且保留 dentry 有助于此。如果 dentry 没有被其他方式使用（即 d_lockref 中的引用计数为 1），则只有此时才会将 d_inode 设置为 NULL。这样做对于非常常见的情况效率更高。

因此，只要持有对 dentry 的计数引用，非 NULL 的 ->d_inode 值就不会被改变。

dentry->d_lock

d_lock 是上述 d_lockref 中自旋锁的同义词。就我们的目的而言，持有此锁可防止 dentry 被重命名或解除链接。特别是，它的父项（d_parent）和它的名称（d_name）不能被改变，并且它不能从 dentry 哈希表中移除。

在目录中查找名称时，REF-walk 会对它在哈希表中找到的每个候选 dentry 获取 d_lock，然后检查父项和名称是否正确。因此，它在缓存中搜索时不会锁定父项；它只锁定子项。

当查找给定名称的父项（以处理“..”）时，REF-walk 可以获取 d_lock 以获取对 d_parent 的稳定引用，但它首先尝试一种更轻量级的方法。正如在 dget_parent() 中所见，如果可以获取对父项的引用，并且随后发现 d_parent 没有改变，那么实际上没有必要对子项获取锁。

rename_lock

在给定目录中查找给定名称涉及从两个值（名称和目录的 dentry）计算哈希值，访问哈希表中的相应槽位，并搜索在那里找到的链表。

当 dentry 被重命名时，名称和父 dentry 都可以更改，因此哈希值也几乎肯定会更改。这将把 dentry 移动到哈希表中的不同链。如果文件名搜索碰巧正在查找以这种方式移动的 dentry，它最终可能会沿着错误的链继续搜索，从而错过正确链的一部分。

名称查找过程（d_lookup()）*不*尝试阻止这种情况发生，而只是在发生时检测到它。rename_lock 是一个 seqlock，每当有 dentry 被重命名时，它都会更新。如果 d_lookup 发现在它扫描哈希表中的一个链失败时发生了重命名，它会简单地重试。

rename_lock 也用于检测和防御在解析“..”时（父目录被移到根目录之外，绕过 path_equal() 检查）针对 LOOKUP_BENEATH 和 LOOKUP_IN_ROOT 的潜在攻击。如果在查找过程中 rename_lock 被更新，并且路径遇到“..”，则表示发生了潜在攻击，handle_dots() 将以 -EAGAIN 退出。

inode->i_rwsem

i_rwsem 是一个读/写信号量，它将对特定目录的所有更改序列化。这确保了例如 unlink() 和 rename() 不能同时发生。它还在文件系统被要求查找当前不在 dcache 中的名称时，或者（可选地）在使用 readdir() 检索目录中的条目列表时，保持目录的稳定。

这与 d_lock 具有互补作用：目录上的 i_rwsem 保护该目录中的所有名称，而名称上的 d_lock 仅保护目录中的一个名称。对 dcache 的大多数更改都会在相关目录 inode 上持有 i_rwsem，并在更改发生时短暂地对一个或多个 dentry 获取 d_lock。一个例外是当空闲 dentry 因内存压力而从 dcache 中移除时。这使用 d_lock，但 i_rwsem 不起作用。

该信号量以两种不同的方式影响路径名查找。首先，它防止在目录中查找名称时发生更改。walk_component() 首先使用 lookup_fast()，后者反过来检查名称是否在缓存中，仅使用 d_lock 锁定。如果未找到名称，则 walk_component() 会回退到 lookup_slow()，后者在 i_rwsem 上获取共享锁，再次检查名称是否不在缓存中，然后调用文件系统以获取确定性答案。无论结果如何，新的 dentry 都将被添加到缓存中。

其次，当路径名查找到达最终组件时，有时需要在执行最后一次查找之前对 i_rwsem 获取排他锁，以便实现所需的排他性。路径查找如何选择获取或不获取 i_rwsem 是后续章节中讨论的问题之一。

如果两个线程同时尝试查找同一个名称（一个尚未在 dcache 中的名称），i_rwsem 上的共享锁将无法阻止它们同时添加具有相同名称的新 dentry。由于这会导致混淆，因此采用了额外一层的互锁，基于一个辅助哈希表（in_lookup_hashtable）和一个每 dentry 标志位（DCACHE_PAR_LOOKUP）。

要在仅持有 i_rwsem 共享锁的情况下向缓存添加新的 dentry，线程必须调用 d_alloc_parallel()。这会分配一个 dentry，在其中存储所需的名称和父项，检查主哈希表或辅助哈希表中是否已存在匹配的 dentry，如果不存在，则将新分配的 dentry 存储在辅助哈希表中，并设置 DCACHE_PAR_LOOKUP。

如果在主哈希表中找到匹配的 dentry，则返回该 dentry，调用者便可知它在与另一个线程添加条目的竞争中失败了。如果在任何缓存中都没有找到匹配的 dentry，则返回新分配的 dentry，调用者可以通过 DCACHE_PAR_LOOKUP 的存在来检测这一点。在这种情况下，它知道它赢得了任何竞争，现在负责要求文件系统执行查找并找到匹配的 inode。当查找完成时，它必须调用 d_lookup_done()，该函数会清除标志并执行其他一些内部管理工作，包括从辅助哈希表中移除 dentry——它通常已经添加到主哈希表中了。请注意，一个 struct waitqueue_head 会传递给 d_alloc_parallel()，并且必须在 waitqueue_head 仍在作用域内时调用 d_lookup_done()。

如果在辅助哈希表中找到匹配的 dentry，d_alloc_parallel() 还有更多工作要做。它首先等待 DCACHE_PAR_LOOKUP 被清除，使用传递给赢得竞态的 d_alloc_parallel() 实例的 wait_queue，该 wait_queue 将由对 d_lookup_done() 的调用唤醒。然后它检查 dentry 是否已添加到主哈希表。如果已添加，则返回该 dentry，调用者只是看到它在任何竞争中失败了。如果它尚未添加到主哈希表，最可能的解释是使用 d_splice_alias() 添加了其他 dentry。无论如何，d_alloc_parallel() 会从头开始重复所有查找，并且通常会从主哈希表中返回一些东西。

mnt->mnt_count

mnt_count 是“mount”结构上的每 CPU 引用计数器。这里的“每 CPU”意味着增加计数成本很低，因为它只使用 CPU 本地内存，但检查计数是否为零成本很高，因为它需要检查每个 CPU。获取 mnt_count 引用可防止挂载结构因常规卸载操作而消失，但不会阻止“惰性”卸载。因此，持有 mnt_count 并不能确保挂载保留在命名空间中，特别是不能稳定到挂载点 dentry 的链接。然而，它确实确保了 mount 数据结构保持一致，并且它提供了对挂载文件系统根 dentry 的引用。因此，通过 ->mnt_count 的引用提供了对已挂载 dentry 的稳定引用，但不是对挂载点 dentry 的稳定引用。

mount_lock

mount_lock 是一个全局的 seqlock，有点像 rename_lock。它可用于检查是否对任何挂载点进行了任何更改。

在向下遍历树（远离根）时，此锁用于在跨越挂载点时检查跨越是否安全。也就是说，读取 seqlock 中的值，然后代码查找当前目录上挂载的挂载点（如果有），并增加 mnt_count。最后，将 mount_lock 中的值与旧值进行比较。如果没有更改，则跨越是安全的。如果发生了更改，则 mnt_count 递减，整个过程重新尝试。

当通过遵循“..”链接向上遍历树（朝向根）时，需要更加小心。在这种情况下，seqlock（包含计数器和自旋锁）被完全锁定，以防止在向上移动时对任何挂载点进行任何更改。此锁定是稳定到挂载点 dentry 的链接所必需的，而挂载本身的引用计数无法保证这一点。

mount_lock 也用于检测和防御在解析“..”时（父目录被移到根目录之外，绕过 path_equal() 检查）针对 LOOKUP_BENEATH 和 LOOKUP_IN_ROOT 的潜在攻击。如果在查找过程中 mount_lock 被更新，并且路径遇到“..”，则表示发生了潜在攻击，handle_dots() 将以 -EAGAIN 退出。

RCU

最后，全局（但极其轻量级的）RCU 读锁会不时地持有，以确保某些数据结构不会意外地被释放。

特别是在扫描 dcache 哈希表和挂载点哈希表中的链时持有。

结合 struct nameidata

在路径遍历的整个过程中，当前状态存储在 struct nameidata 中，“namei”是传统名称——追溯到 Unix 第一版——用于将“名称”转换为“inode”的函数。struct nameidata 包含（除其他字段外）：

struct path path

一个 path 包含一个 struct vfsmount（嵌入在 struct mount 中）和一个 struct dentry。它们共同记录遍历的当前状态。它们最初指向起点（当前工作目录、根目录或由文件描述符标识的某个其他目录），并在每一步中更新。通过 d_lockref 和 mnt_count 的引用始终被持有。

struct qstr last

这是一个字符串及其长度（即 *不* 以 nul 终止），它是路径名中的“下一个”组件。

int last_type

这是一个 LAST_NORM、LAST_ROOT、LAST_DOT 或 LAST_DOTDOT 之一。last 字段仅在类型为 LAST_NORM 时有效。

struct path root

这用于保存对文件系统有效根的引用。通常不需要该引用，因此此字段仅在首次使用时或请求非标准根时才分配。在 nameidata 中保留引用可确保在整个路径遍历过程中只有一个根生效，即使它与 chroot() 系统调用发生竞态。

应该注意的是，在 LOOKUP_IN_ROOT 或 LOOKUP_BENEATH 的情况下，有效根成为传递给 openat2()（暴露这些 LOOKUP_ 标志的函数）的目录文件描述符。

当满足以下两个条件之一时，需要根目录：（1）路径名或符号链接以“/”开头；或（2）正在处理“..”组件，因为从根目录的“..”必须始终停留在根目录。使用的值通常是调用进程的当前根目录。可以提供替代根，例如当 sysctl() 调用 file_open_root() 时，以及当 NFSv4 或 Btrfs 调用 mount_subtree() 时。在每种情况下，路径名都在文件系统的特定部分中查找，并且不允许查找逃离该子树。它的工作方式有点像局部 chroot()。

忽略符号链接的处理，我们现在可以描述“link_path_walk()”函数，它处理除最终组件之外的所有内容的查找，如下所示：

给定一个路径 (name) 和一个 nameidata 结构 (nd)，检查当前目录是否具有执行权限，然后将 name 推进一个组件，同时更新 last_type 和 last。如果这是最终组件，则返回，否则调用 walk_component() 并从头开始重复。

walk_component() 甚至更简单。如果组件是 LAST_DOTS，它会调用 handle_dots()，后者执行已描述的必要锁定。如果它发现一个 LAST_NORM 组件，它首先调用“lookup_fast()”，该函数只在 dcache 中查找，但如果文件系统是那种类型的文件系统，它会要求文件系统重新验证结果。如果这没有得到好的结果，它会调用“lookup_slow()”，该函数获取 i_rwsem 的共享锁，重新检查缓存，然后要求文件系统找到最终答案。

作为 walk_component() 的最后一步，step_into() 将直接从 walk_component() 或 handle_dots() 中调用。它调用 handle_mounts() 来检查和处理挂载点，其中会创建一个新的 struct path，包含对新 dentry 的计数引用以及对新 vfsmount 的引用（仅当其与之前的 vfsmount 不同时才计数）。然后，如果存在符号链接，step_into() 调用 pick_link() 来处理它，否则它会在 struct nameidata 中安装新的 struct path，并丢弃不需要的引用。

这种“手把手”的顺序——在释放对前一个 dentry 的引用之前获取对新 dentry 的引用——可能看起来很明显，但值得指出，以便我们能在“RCU-walk”版本中识别出它的类似物。

处理最终组件

link_path_walk() 只遍历到设置 nd->last 和 nd->last_type 以引用路径的最终组件。它不会在最后一次调用 walk_component()。处理该最终组件的任务留给调用者解决。这些调用者是 path_lookupat()、path_parentat() 和 path_openat()，它们各自处理不同系统调用的不同要求。

path_parentat() 显然是最简单的——它只是在 link_path_walk() 周围包装了一些内务处理，并向调用者返回父目录和最终组件。调用者要么旨在创建名称（通过 filename_create()），要么删除或重命名名称（在这种情况下使用 user_path_parent()）。他们将使用 i_rwsem 来排除其他更改，同时他们验证并执行其操作。

path_lookupat() 也差不多简单——它用于需要现有对象的情况，例如通过 stat() 或 chmod()。它本质上只是通过调用 lookup_last() 来对最终组件调用 walk_component()。path_lookupat() 只返回最终的 dentry。值得注意的是，当设置了标志 LOOKUP_MOUNTPOINT 时，path_lookupat() 将在 nameidata 中取消设置 LOOKUP_JUMPED，以便在随后的路径遍历中不会调用 d_weak_revalidate()。这在卸载不可访问的文件系统（例如由宕机的 NFS 服务器提供的文件系统）时很重要。

最后，path_openat() 用于 open() 系统调用；它在以“open_last_lookups()”开头的辅助函数中包含了处理 O_CREAT（带或不带 O_EXCL）、最终“/”字符和尾随符号链接等不同微妙之处所需的所有复杂性。我们将在本系列的最后一部分重新探讨这一点，该部分重点关注这些符号链接。“open_last_lookups()”有时会（但并非总是）获取 i_rwsem，具体取决于它发现的内容。

这些函数，或调用它们的函数，都需要警惕最终组件不是 LAST_NORM 的可能性。如果查找的目标是创建某个东西，那么 last_type 的任何值（除了 LAST_NORM）都将导致错误。例如，如果 path_parentat() 报告 LAST_DOTDOT，那么调用者就不会尝试创建该名称。它们还通过测试 last.name[last.len] 来检查尾随斜杠。如果最终组件之外有任何字符，那它必须是一个尾随斜杠。

重新验证和自动挂载

除了符号链接之外，“REF-walk”过程还有两个尚未涵盖的部分。一个是处理陈旧的缓存条目，另一个是自动挂载。

在需要的文件系统上，查找例程将调用 ->d_revalidate() dentry 方法以确保缓存信息是当前的。这通常会确认有效性或从服务器更新一些详细信息。在某些情况下，它可能会发现路径上游发生了变化，并且以前认为有效的东西实际上并非如此。发生这种情况时，整个路径的查找会被中止，并设置“LOOKUP_REVAL”标志进行重试。这会强制重新验证更彻底。我们将在下一篇文章中看到有关此重试过程的更多详细信息。

自动挂载点是文件系统中的位置，在这些位置上尝试查找名称可能会触发该查找的处理方式发生变化，特别是通过在该处挂载文件系统。这些内容在 Linux 文档树中的 autofs - 工作原理 中有更详细的介绍，但此处需要特别指出一些与路径查找相关的注意事项。

Linux VFS 有一个“托管”dentry 的概念。关于这些 dentry，有三点可能有趣的地方，它们对应于 dentry->d_flags 中可能设置的三个不同标志：

DCACHE_MANAGE_TRANSIT

如果设置了此标志，则文件系统已请求在处理任何可能的挂载点之前调用 d_manage() dentry 操作。这可以提供两种特定服务：

它可以阻塞以避免竞态条件。如果正在卸载一个自动挂载点，d_manage() 函数通常会等待该过程完成，然后才允许新的查找继续并可能触发新的自动挂载。

它可以选择性地只允许某些进程通过挂载点。当服务器进程管理自动挂载时，它可能需要访问目录而不触发正常的自动挂载处理。该服务器进程可以向 autofs 文件系统表明身份，然后 autofs 将通过返回 -EISDIR 来给予其通过 d_manage() 的特殊权限。

DCACHE_MOUNTED

此标志设置在每个被挂载的 dentry 上。由于 Linux 支持多个文件系统命名空间，因此 dentry 可能并未在此命名空间中挂载，而是在其他命名空间中挂载。因此，此标志被视为一个提示，而非承诺。

如果此标志已设置，并且 d_manage() 未返回 -EISDIR，则调用 lookup_mnt() 来检查挂载哈希表（尊重前面描述的 mount_lock），并可能返回新的 vfsmount 和新的 dentry（两者均带有计数引用）。

DCACHE_NEED_AUTOMOUNT

如果 d_manage() 允许我们走到这一步，并且 lookup_mnt() 没有找到挂载点，那么这个标志会触发调用 d_automount() dentry 操作。

鉴于 d_automount() 操作可以任意复杂，并且可能与服务器进程等进行通信，它最终应该要么报告发生错误，要么报告没有要挂载的内容，或者提供一个包含新的 dentry 和 vfsmount 的更新的 struct path。

在后一种情况下，将调用 finish_automount() 以安全地将新挂载点安装到挂载表中。

这里没有新的重要锁定，并且重要的是，在此处理过程中不持有任何锁（仅持有计数引用），因为这极有可能导致长时间延迟。这在下次我们研究对延迟特别敏感的 RCU-walk 时将变得更加重要。

RCU-walk - Linux 中更快的路径名查找

RCU-walk 是 Linux 中执行路径名查找的另一种算法。它在许多方面与 REF-walk 相似，并且两者共享相当多的代码。RCU-walk 的显著区别在于它如何允许并发访问的可能性。

我们注意到 REF-walk 很复杂，因为它有许多细节和特殊情况。RCU-walk 通过简单地拒绝处理某些情况来降低这种复杂性——它反而回退到 REF-walk。RCU-walk 的困难来自另一个方向：不熟悉。依赖 RCU 时的锁定规则与传统锁定截然不同，因此当我们遇到这些规则时，我们将花费更多时间。

明确的角色划分

管理并发最简单的方法是强制阻止任何其他线程更改给定线程正在查看的数据结构。在没有其他线程会想到更改数据并且许多不同线程希望同时读取的情况下，这可能会非常昂贵。即使使用允许多个并发读取器的锁，简单地更新当前读取器数量的计数也可能带来不必要的开销。因此，当读取其他进程未更改的共享数据结构时，目标是完全避免向内存写入任何内容。不获取锁，不增加计数，不留下任何痕迹。

已经描述的 REF-walk 机制显然不遵循这一原则，但它确实设计用于可能存在其他线程修改数据的情况。相比之下，RCU-walk 旨在处理常见情况：存在大量频繁读取器而只有偶尔写入器。这在文件系统树的所有部分可能不常见，但在许多部分会是这样。对于其他部分，重要的是 RCU-walk 可以快速回退到使用 REF-walk。

路径名查找总是以 RCU-walk 模式开始，但只有当它查找的内容在缓存中且稳定时才保持该模式。它轻快地沿着缓存的文件系统映像向下“舞蹈”，不留下任何痕迹，并仔细观察其位置，以确保它不会出错。如果它发现某些东西已更改或正在更改，或者某些东西不在缓存中，那么它会尝试优雅地停止并切换到 REF-walk。

这种停止需要获取对当前 vfsmount 和 dentry 的计数引用，并确保这些仍然有效——即使用 REF-walk 遍历路径也会找到相同的条目。这是 RCU-walk 必须保证的一个不变式。它只能做出 REF-walk 在同时遍历树时也能做出的决策，例如选择下一步。如果优雅停止成功，路径的其余部分将由可靠但略显迟缓的 REF-walk 处理。如果 RCU-walk 发现它无法优雅停止，它会简单地放弃并使用 REF-walk 从头开始重新启动。

这种“尝试 RCU-walk，如果失败则尝试 REF-walk”的模式可以清楚地在 filename_lookup()、filename_parentat()、do_filp_open() 和 do_file_open_root() 等函数中看到。这四个函数大致对应于我们前面遇到的三个 path_*() 函数，每个函数都调用 link_path_walk()。path_*() 函数会使用不同的模式标志进行调用，直到找到一个有效模式。它们首先在设置了 LOOKUP_RCU 的情况下调用，以请求“RCU-walk”。如果失败并返回错误 ECHILD，它们会再次在没有特殊标志的情况下调用，以请求“REF-walk”。如果其中任何一个报告错误 ESTALE，则会进行最后一次尝试，设置 LOOKUP_REVAL（且不设置 LOOKUP_RCU），以确保缓存中找到的条目被强制重新验证——通常只有当文件系统确定它们太旧而不可信时才重新验证条目。

LOOKUP_RCU 尝试可能会在内部放弃该标志并切换到 REF-walk，但此后绝不会尝试切换回 RCU-walk。阻碍 RCU-walk 的地方更有可能靠近叶子，因此切换回来几乎不会有任何好处。

RCU 和 Seqlocks：快速轻量

RCU 对 RCU-walk 模式至关重要，这并不奇怪。rcu_read_lock() 在 RCU-walk 遍历路径的整个过程中都被持有。它提供的具体保证是，在持有锁期间，关键数据结构——dentries、inodes、super_blocks 和 mounts——不会被释放。它们可能以某种方式被解除链接或失效，但内存不会被重新利用，因此各个字段中的值仍然有意义。这是 RCU 提供的唯一保证；其他一切都使用 seqlock 完成。

正如我们上面看到的，REF-walk 持有对当前 dentry 和当前 vfsmount 的计数引用，并且在获取对“下一个”dentry 或 vfsmount 的引用之前不会释放这些引用。它有时也会获取 d_lock 自旋锁。获取这些引用和锁是为了防止某些更改发生。RCU-walk 不得获取这些引用或锁，因此无法阻止此类更改。相反，它会检查是否发生了更改，如果发生了更改，则中止或重试。

为了保持上述不变式（即 RCU-walk 只能做出 REF-walk 也能做出的决策），它必须在 REF-walk 持有引用的相同或附近位置进行检查。因此，当 REF-walk 增加引用计数或获取自旋锁时，RCU-walk 会使用 read_seqcount_begin() 或类似函数采样 seqlock 的状态。当 REF-walk 减少计数或释放锁时，RCU-walk 会使用 read_seqcount_retry() 或类似函数检查采样的状态是否仍然有效。

然而，seqlock 还有更多内容。如果 RCU-walk 访问受 seqlock 保护的结构中两个不同的字段，或者两次访问同一个字段，则无法先验保证这些访问之间存在任何一致性。当需要一致性时（通常是这样），RCU-walk 必须复制一份，然后使用 read_seqcount_retry() 来验证该副本。

read_seqcount_retry() 不仅检查序列号，还强制设置内存屏障，以确保 CPU 或编译器不会将 *调用之前* 的任何内存读取指令延迟到 *调用之后*。一个简单的例子可以在 slow_dentry_cmp() 中看到，对于不使用简单字节级名称相等性的文件系统，该函数会调用文件系统来将名称与 dentry 进行比较。长度和名称指针被复制到局部变量中，然后调用 read_seqcount_retry() 以确认两者一致，然后才调用 ->d_compare()。当使用标准文件名比较时，则调用 dentry_cmp()。值得注意的是，它 *不* 使用 read_seqcount_retry()，而是有一个详细的注释解释为什么不需要一致性保证。随后的 read_seqcount_retry() 将足以捕获此时可能发生的任何问题。

在简单回顾了 seqlock 之后，我们可以看看 RCU-walk 如何使用 seqlock 的更大图景。

mount_lock 和 nd->m_seq

我们在 REF-walk 中已经遇到过 mount_lock seqlock，它用于确保安全地跨越挂载点。RCU-walk 也为此目的使用它，但用途远不止于此。

RCU-walk 在向下遍历树时，不获取每个 vfsmount 的计数引用，而是在遍历开始时采样 mount_lock 的状态，并将此初始序列号存储在 struct nameidata 的 m_seq 字段中。这一个锁和一个序列号用于验证对所有 vfsmounts 的所有访问以及所有挂载点交叉。由于挂载表的更改相对较少，因此在发生任何“挂载”或“卸载”时，回退到 REF-walk 是合理的。

在 RCU-walk 序列结束时，m_seq 会被检查（使用 read_seqretry()），无论是在路径的其余部分切换到 REF-walk 还是到达路径末尾。在向下遍历挂载点（在 __follow_mount_rcu() 中）或向上遍历（在 follow_dotdot_rcu() 中）时也会检查它。如果发现它已更改，则整个 RCU-walk 序列将被中止，并由 REF-walk 再次处理路径。

如果 RCU-walk 发现 mount_lock 没有改变，那么它可以确定，如果 REF-walk 对每个 vfsmount 都取得了计数引用，结果也会相同。这确保了不变式成立，至少对于 vfsmount 结构而言。

dentry->d_seq 和 nd->seq

RCU-walk 不在 d_reflock 上获取计数或锁，而是采样每个 dentry 的 d_seq seqlock，并将序列号存储在 nameidata 结构的 seq 字段中，因此 nd->seq 应该始终是 nd->dentry 的当前序列号。在复制之后、使用 dentry 的名称、父级或 inode 之前，需要重新验证此数字。

名称的处理我们已经看过，而父项只在 follow_dotdot_rcu() 中访问，该函数相当简单地遵循所需的模式，尽管它处理了三种不同的情况。

当不在挂载点时，会遵循 d_parent 并收集其 d_seq。当我们在挂载点时，我们会改为遵循 mnt->mnt_mountpoint 链接以获取新的 dentry 并收集其 d_seq。然后，在最终找到要遵循的 d_parent 后，我们必须检查是否已到达挂载点，如果到达，则必须找到该挂载点并遵循 mnt->mnt_root 链接。这可能意味着一种有些不寻常但肯定可能发生的情况，即路径查找的起点位于文件系统的某个已挂载部分，因此从根目录不可见。

存储在 ->d_inode 中的 inode 指针更有趣一些。inode 总是需要至少访问两次，一次是确定它是否为 NULL，另一次是验证访问权限。符号链接处理也需要一个经过验证的 inode 指针。与其在每次访问时都重新验证，不如在第一次访问时复制一份，并将其存储在 nameidata 的 inode 字段中，从那里可以安全访问而无需进一步验证。

lookup_fast() 是 RCU 模式下唯一使用的查找例程，因为 lookup_slow() 太慢且需要锁。正是在 lookup_fast() 中，我们发现了对当前 dentry 重要的“手递手”跟踪。

当前的 dentry 和当前的 seq 数字被传递给 __d_lookup_rcu()，该函数在成功时返回一个新的 dentry 和一个新的 seq 数字。lookup_fast() 随后复制 inode 指针并重新验证新的 seq 数字。然后它最后一次使用旧的 seq 数字验证旧的 dentry，然后才继续。获取新 dentry 的 seq 数字然后检查旧 dentry 的 seq 数字的这个过程，与我们在 REF-walk 中看到的在释放旧 dentry 的计数引用之前获取新 dentry 的计数引用这一过程完全相同。

无 inode->i_rwsem 甚至无 rename_lock

信号量是一种相当重量级的锁，只有在允许休眠时才能获取。由于 rcu_read_lock() 禁止休眠，因此 inode->i_rwsem 在 RCU-walk 中不起作用。如果其他线程获取 i_rwsem 并以 RCU-walk 需要注意的方式修改目录，结果将是 RCU-walk 未能找到它正在寻找的 dentry，或者它会找到一个 read_seqretry() 无法验证的 dentry。在这两种情况下，它都会降级到 REF-walk 模式，该模式可以获取所需的任何锁。

尽管 rename_lock 可以被 RCU-walk 使用，因为它不需要任何休眠，但 RCU-walk 不会费心使用它。REF-walk 使用 rename_lock 来防止在搜索 dcache 中的哈希链时发生变化。这可能导致未能找到实际存在的内容。当 RCU-walk 未能在 dentry 缓存中找到某些内容时，无论它是否真的存在，它都会降级到 REF-walk 模式，并使用适当的锁重新尝试。这巧妙地处理了所有情况，因此添加额外的 rename_lock 检查不会带来显著价值。

unlazy walk() 和 complete_walk()

“降级到 REF-walk”通常涉及调用 unlazy_walk()，之所以这样命名是因为“RCU-walk”有时也被称为“lazy walk”。当沿着路径到达当前的 vfsmount/dentry 对似乎已成功进行，但下一步出现问题时，会调用 unlazy_walk()。这可能发生在以下情况：dcache 中找不到下一个名称；在持有 rcu_read_lock()（禁止休眠）时无法完成权限检查或名称重新验证；发现自动挂载点；或者涉及符号链接的几种情况。它也会在查找到达最终组件或路径的末尾时（取决于使用的特定查找方式）从 complete_walk() 调用。

不触发调用 unlazy_walk() 而退出 RCU-walk 的其他原因包括发现无法立即处理的不一致性，例如 mount_lock 或其中一个 d_seq 序列锁报告更改。在这些情况下，相关函数将返回 -ECHILD，这将向上渗透直到触发从顶部使用 REF-walk 的新尝试。

对于那些 unlazy_walk() 是一个选项的情况，它本质上是对其持有的每个指针（vfsmount、dentry 以及可能的某些符号链接）进行引用，然后验证相关序列锁是否未被更改。如果发生了更改，它也会以 -ECHILD 中止，否则到 REF-walk 的转换成功，查找过程继续。

对这些指针进行引用并不像简单地递增计数器那么简单。如果你已经有了一个引用（通常通过另一个对象间接获得），它可以用作第二个引用，但如果你根本没有计数引用，它就不够了。对于 dentry->d_lockref，除非它被明确标记为“dead”（这涉及到将计数器设置为 -128），否则递增引用计数器以获取引用是安全的。lockref_get_not_dead() 实现了这一点。

对于 mnt->mnt_count，只要随后使用 mount_lock 来验证引用，获取引用就是安全的。如果该验证失败，则可能不安全以调用 mnt_put() 的标准方式直接删除该引用——卸载可能已经进展得太远。因此，legitimize_mnt() 中的代码，当它发现所获得的引用可能不安全时，会检查 MNT_SYNC_UMOUNT 标志以确定简单的 mnt_put() 是否正确，或者它是否应该只是递减计数并假装这一切从未发生过。

文件系统中的注意事项

RCU-walk 几乎完全依赖于缓存信息，并且通常根本不会调用文件系统。然而，除了前面提到的组件名称比较之外，文件系统可能被包含在 RCU-walk 中的两个地方，并且它必须知道要小心。

如果文件系统具有非标准的权限检查要求——例如可能需要与服务器检查的网络文件系统——则 i_op->permission 接口可能会在 RCU-walk 期间被调用。在这种情况下，会传递一个额外的“MAY_NOT_BLOCK”标志，以便它知道不能休眠，而是如果不能及时完成则返回 -ECHILD。i_op->permission 获得了 inode 指针，而不是 dentry，因此它不需要担心进一步的一致性检查。但是，如果它访问任何其他文件系统数据结构，它必须确保它们在仅持有 rcu_read_lock() 的情况下可以安全访问。这通常意味着它们必须使用 kfree_rcu() 或类似方式释放。

如果文件系统可能需要重新验证 dcache 条目，那么 d_op->d_revalidate 也可能在 RCU-walk 中被调用。这个接口确实传递了 dentry，但无法访问 inode 或来自 nameidata 的 seq 号，因此在访问 dentry 中的字段时需要格外小心。这种“格外小心”通常涉及使用 READ_ONCE() 来访问字段，并在使用之前验证结果是否非 NULL。这种模式可以在 nfs_lookup_revalidate() 中看到。

一对模式

在 REF-walk 和 RCU-walk 的细节中，以及在整体上，有几个相关的模式值得注意。

第一个是“快速尝试并检查，如果失败则慢速尝试”。我们可以在高层方法中看到这一点，即首先尝试 RCU-walk，然后尝试 REF-walk，以及在 unlazy_walk() 用于将剩余路径切换到 REF-walk 的地方。我们之前在 dget_parent() 遵循“..”链接时也看到了这一点。它尝试一种快速方式获取引用，然后在需要时回退到获取锁。

第二种模式是“快速尝试并检查，如果失败则重复尝试”。这在 REF-walk 中使用 rename_lock 和 mount_lock 时可见。RCU-walk 不使用这种模式——如果出现任何问题，中止并尝试更稳健的方法要安全得多。

这里的重点是“快速尝试并检查”。它可能应该是“快速且仔细地尝试，然后检查”。需要检查这一事实提醒我们系统是动态的，只有有限数量的东西是完全安全的。整个过程中最常见的错误原因是假设某物是安全的，而实际上它并非如此。有时有必要仔细考虑究竟是什么保证了每次访问的安全性。