路径名查找

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

由 Neil Brown 撰写，并得到 Al Viro 和 Jon Corbet 的帮助。随后进行了更新，以反映内核中的变化，包括

  • 每个目录的并行名称查找。

  • openat2() 解析限制标志。

路径名查找简介

路径名查找最明显的方面，无需太多探索即可发现，就是它很复杂。有许多规则、特殊情况和实现替代方案，所有这些加在一起让粗心的读者感到困惑。计算机科学早就熟悉这种复杂性，并有工具来帮助管理它。我们将广泛使用的一个工具是“分而治之”。在分析的早期部分，我们将分离出符号链接 - 将其留到最后一部分。在我们接触到符号链接之前，我们还有另一个主要的分区，基于 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/b”重命名为“a/c/b”，则该进程可能会成功解析为“a/c”。大多数竞争条件要微妙得多，路径名查找的大部分任务是防止它们产生破坏性影响。许多可能的竞争条件在“dcache”的上下文中最为清楚地看到，对它的理解是理解路径名查找的关键。

不仅仅是缓存

“dcache”缓存每个文件系统中有关名称的信息，以便快速用于查找。每个条目（称为“dentry”）包含三个重要字段：组件名称，指向父 dentry 的指针以及指向“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 原语来提供自旋锁和引用计数。此原语的特殊之处在于，概念序列“lock; inc_ref; unlock;”通常可以使用单个原子内存操作来执行。

保持对 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 也用于检测和防御针对 LOOKUP_BENEATH 和 LOOKUP_IN_ROOT 在解析“..” 时的潜在攻击（其中父目录被移动到根目录之外，绕过 path_equal() 检查）。如果在查找期间更新了 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。一个例外是由于内存压力而从 dcache 中删除空闲 dentry 时。这使用 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() 需要做更多的工作。它首先等待使用传递给赢得竞争的 d_alloc_parallel() 实例的 wait_queue 来清除 DCACHE_PAR_LOOKUP，并且该实例将由对 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 还用于检测和防御针对 LOOKUP_BENEATH 和 LOOKUP_IN_ROOT 的潜在攻击，当解析“..”时（当父目录被移动到根目录之外，绕过 path_equal() 检查）。如果在查找期间更新了 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_NORM 时，last 字段才有效。

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)，检查当前目录是否具有执行权限，然后在更新 last_type 和 last 的同时将 name 向前移动一个组件。如果这是最后一个组件，则返回，否则调用 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 path 安装到 struct nameidata 中，并删除不需要的引用。

这种“手递手”序列，即在删除对先前 dentry 的引用之前获得对新 dentry 的引用，似乎是显而易见的，但值得指出，以便我们能够识别其在“RCU 遍历”版本中的类似之处。

处理最终组件

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 文件系统标识自己，然后该文件系统将通过返回 -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 遍历，如果失败则尝试 REF 遍历”的模式可以清楚地在诸如 `filename_lookup()`、`filename_parentat()`、`do_filp_open()` 和 `do_file_open_root()` 等函数中看到。这四个函数大致对应于我们前面遇到的三个 `path_*()` 函数，每个函数都调用 `link_path_walk()`。`path_*()` 函数会使用不同的模式标志进行调用，直到找到一个可用的模式。它们首先使用 `LOOKUP_RCU` 设置来请求 “RCU 遍历”。如果该操作因 `ECHILD` 错误而失败，它们会再次调用，并且不带任何特殊标志以请求 “REF 遍历”。如果其中任何一个报告了 `ESTALE` 错误，则会使用 `LOOKUP_REVAL` 设置（且不使用 `LOOKUP_RCU`）进行最后一次尝试，以确保强制重新验证缓存中找到的条目 - 通常，只有当文件系统确定条目过于陈旧而不可信任时才会重新验证条目。

`LOOKUP_RCU` 尝试可能会在内部删除该标志并切换到 REF 遍历，但绝不会尝试切换回 RCU 遍历。触发 RCU 遍历失败的位置更可能靠近叶子节点，因此从切换回 RCU 遍历中获得任何好处的可能性很小，甚至没有好处。

RCU 和 seqlock：快速轻量

毫不奇怪，RCU 对于 RCU 遍历模式至关重要。在 RCU 遍历向下遍历路径的整个过程中，都会持有 `rcu_read_lock()`。它提供的特殊保证是，在持有锁时，关键数据结构（dentry、inode、super_block 和 mount）不会被释放。它们可能会以某种方式取消链接或失效，但内存不会被重新利用，因此各个字段中的值仍然有意义。这是 RCU 提供的唯一保证；其他一切都使用 seqlock 完成。

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

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

但是，seqlock 不仅仅如此。如果 RCU 遍历访问受 seqlock 保护的结构中的两个不同字段，或者两次访问同一字段，则无法先验地保证这些访问之间的一致性。当需要一致性时（通常是这种情况），RCU 遍历必须进行复制，然后使用 `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 遍历如何使用 seqlock 的更大图景。

`mount_lock` 和 `nd->m_seq`

当 REF 遍历使用 `mount_lock` 来确保安全执行跨越挂载点时，我们已经遇到了它。RCU 遍历也将其用于此目的，但它用于更多功能。

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

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

如果 RCU 遍历发现 `mount_lock` 没有更改，则它可以确定，如果 REF 遍历在每个 vfsmount 上都采用计数引用，则结果将相同。这确保了不变性成立，至少对于 vfsmount 结构而言。

`dentry->d_seq` 和 `nd->seq`

RCU 遍历不是在 `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() 调用它。

导致退出 RCU-walk 而不触发调用 unlazy_walk() 的其他原因是在发现一些无法立即处理的不一致情况时，例如 mount_lock 或 d_seq seqlocks 报告更改。在这些情况下，相关函数将返回 -ECHILD，该返回值会向上渗透，直到它触发从顶部使用 REF-walk 进行新的尝试。

对于那些 unlazy_walk() 是一个选项的情况，它本质上会引用它持有的每个指针（vfsmount、dentry，以及可能的一些符号链接），然后验证相关的 seqlocks 没有被更改。如果发生了更改，它也会使用 -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 中，并且它必须知道要小心。

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

如果文件系统可能需要重新验证 dcache 条目，那么也可以在 RCU-walk 中调用 d_op->d_revalidate。此接口 *确实* 将 dentry 传递给它，但无权访问 nameidata 中的 inode 或 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 不使用这种模式 - 如果出现任何问题，最好是中止并尝试一种更平静的方法。

这里的重点是 “快速尝试并检查”。它可能应该是 “快速 *且谨慎地* 尝试，然后检查”。需要检查的事实提醒我们，系统是动态的，只有少数事情是完全安全的。整个过程中最可能导致错误的原因是假设某些事情是安全的，而实际上并非如此。有时需要仔细考虑什么能保证每次访问的安全。