本文档根据 GNU 通用公共许可证 v2 的条款获得许可。 主要作者是 Darrick J. Wong。
本设计文档分为七个部分。第一部分定义了 fsck 工具是什么以及编写新工具的动机。第二部分和第三部分概述了在线 fsck 进程的工作原理以及如何对其进行测试以确保功能正确。第四部分讨论了用户界面和新程序的预期使用模式。第五部分和第六部分展示了高级组件以及它们如何组合在一起，然后提供每个修复功能实际如何工作的案例研究。第七部分总结了迄今为止讨论的内容，并推测了在线 fsck 之上还可以构建哪些内容。
Unix 文件系统有四个主要职责：
直接支持这些功能的元数据（例如，文件、目录、空间映射）有时被称为主要元数据。次要元数据（例如，反向映射和目录父指针）支持文件系统内部的操作，例如内部一致性检查和重组。顾名思义，汇总元数据会出于性能原因而压缩主要元数据中包含的信息。
文件系统检查 (fsck) 工具会检查文件系统中的所有元数据，以查找错误。除了查找明显的元数据损坏之外，fsck 还会将不同类型的元数据记录相互交叉引用，以查找不一致之处。人们不喜欢丢失数据，因此大多数 fsck 工具还包含一些纠正发现的任何问题的能力。需要注意的是，大多数 Linux fsck 工具的主要目标是将文件系统元数据恢复到一致状态，而不是最大限度地恢复数据。这里不会挑战这个先例。
20 世纪的文件系统通常在其磁盘格式中没有任何冗余，这意味着 fsck 只能通过擦除文件直到不再检测到错误来响应错误。最近的文件系统设计在其元数据中包含足够的冗余，现在可以在发生非灾难性错误时重新生成数据结构；此功能有助于这两种策略。
注意: |
系统管理员通过创建备份来增加独立存储系统的数量，从而避免数据丢失；他们通过创建 RAID 阵列来增加每个存储系统的冗余，从而避免停机。fsck 工具仅解决第一个问题。 |
代码按如下方式发布到 kernel.org git 树中：内核更改， 用户空间更改，以及 QA 测试更改。添加在线修复功能的每个内核补丁集将在内核、xfsprogs 和 fstests git 存储库中使用相同的分支名称。
当前的 XFS 工具遗留了一些未解决的问题：
由于元数据中存在无声损坏，导致意外关机时，用户程序会突然失去对文件系统的访问权限。这些问题无法预测，并且通常没有警告。
在发生意外关机后的恢复期间，用户会经历完全的服务丢失。
如果文件系统被脱机以主动查找问题，则用户会经历完全的服务丢失。
数据所有者在不读取所有数据的情况下，无法检查其存储数据的完整性。当存储系统管理员执行线性介质扫描足以解决问题时，这可能会使他们面临巨大的计费成本。
如果系统管理员在文件系统在线时缺乏评估文件系统健康状况的手段，他们就无法安排维护窗口来处理损坏。
当需要手动干预和停机时，舰队监控工具无法自动执行文件系统健康状况的定期检查。
当恶意行为者利用 Unicode 的怪癖在目录中放置误导性名称时，用户可能会被诱骗做他们不希望做的事情。
鉴于需要解决的问题和将从中受益的角色定义，提出的解决方案是第三个 fsck 工具，它在运行中的文件系统上运行。
这个新的第三个程序有三个组件：一个用于检查元数据的内核内工具、一个用于修复元数据的内核内工具以及一个用户空间驱动程序，用于在活动文件系统上驱动 fsck 活动。 xfs_scrub 是驱动程序的名称。本文档的其余部分介绍了新 fsck 工具的目标和用例，描述了其与这些目标相关的主要设计点，并讨论了与现有工具的异同。
注意: |
在整个文档中，现有的离线 fsck 工具也可以用其当前名称“xfs_repair”来表示。新的在线 fsck 工具的用户空间驱动程序可以称为“xfs_scrub”。在线 fsck 的内核部分，用于验证元数据，称为“在线清理”，内核中修复元数据的部分称为“在线修复”。 |
命名层次结构被分解为称为目录和文件的对象，物理空间被分为称为分配组的片段。分片使得在高度并行的系统上实现更好的性能，并有助于在发生损坏时控制损害。将文件系统划分为主要对象（分配组和 inode）意味着有充足的机会对文件系统的子集执行有针对性的检查和修复。
在进行此操作时，其他部分继续处理 IO 请求。即使文件系统元数据的某一部分只能通过扫描整个系统来重新生成，扫描仍然可以在后台完成，而其他文件操作继续进行。
总之，在线 fsck 利用资源分片和冗余元数据来实现有针对性的检查和修复操作，同时系统仍在运行。此功能将与自动系统管理相结合，以便 XFS 的自主自愈最大化服务可用性。
如前所述，fsck 工具具有三个主要目标
检测元数据中的不一致；
消除这些不一致；以及
最大程度地减少进一步的数据丢失。
必须演示正确的操作，以建立用户对软件行为符合预期的信心。不幸的是，在引入具有高 IOPS 存储的低成本虚拟机之前，实际上不可能对 fsck 工具的每个方面执行常规的详尽测试。考虑到充足的硬件可用性，在线 fsck 项目的测试策略包括与现有 fsck 工具进行差异分析，以及对每种类型的元数据对象的每个属性进行系统测试。测试可以分为四大类，如下所述。
任何自由软件 QA 工作的主要目标是使测试尽可能廉价和广泛，以最大化社区的规模优势。换句话说，测试应最大化文件系统配置方案和硬件设置的广度。这通过使在线 fsck 的作者能够尽早发现和修复错误来提高代码质量，并帮助新功能开发人员在其开发工作中尽早发现集成问题。
Linux 文件系统社区共享一个通用的 QA 测试套件 fstests，用于功能和回归测试。甚至在在线 fsck 的开发工作开始之前，fstests（在 XFS 上运行时）会在每次测试之间对测试和临时文件系统运行 xfs_check 和 xfs_repair -n 命令。这提供了一定程度的保证，即内核和 fsck 工具在关于什么构成一致的元数据方面保持一致。在在线检查代码的开发过程中，fstests 被修改为在每次测试之间运行 xfs_scrub -n，以确保新的检查代码产生与两个现有 fsck 工具相同的结果。
为了开始在线修复的开发，fstests 被修改为运行 xfs_repair，以在测试之间重建文件系统的元数据索引。这确保了离线修复不会崩溃，在退出后不会留下损坏的文件系统，也不会触发在线检查的抱怨。这也为可以和不能离线修复的内容建立了基线。为了完成在线修复的第一个开发阶段，fstests 被修改为能够在“强制重建”模式下运行 xfs_scrub。这使得可以比较在线修复与现有离线修复工具的有效性。
在线 fsck 的一个独特要求是能够与常规工作负载同时在文件系统上运行。尽管当然不可能在运行的系统上对 xfs_scrub 产生零可观察到的影响，但在线修复代码绝不应将不一致性引入文件系统元数据，并且常规工作负载绝不应注意到资源匮乏。为了验证是否满足这些条件，fstests 通过以下方式进行了增强
对于每种 scrub 项目类型，创建一个测试，在运行 fsstress 时执行检查该项目类型。
对于每种 scrub 项目类型，创建一个测试，在运行 fsstress 时执行修复该项目类型。
并行运行 fsstress 和 xfs_scrub -n，以确保检查整个文件系统不会导致问题。
并行运行 fsstress 和强制重建模式下的 xfs_scrub，以确保强制修复整个文件系统不会导致问题。
在冻结和解冻文件系统时，针对 fsstress 并行运行检查和强制修复模式下的 xfs_scrub。
在以只读和读写方式重新挂载文件系统时，针对 fsstress 并行运行检查和强制修复模式下的 xfs_scrub。
相同，但运行 fsx 而不是 fsstress。(尚未完成？)
成功定义为能够运行所有这些测试，而不会因元数据损坏、内核挂起检查警告或任何其他形式的故障而导致任何意外的文件系统关闭。
建议的补丁集包括 通用压力测试 和 现有每个功能压力测试的演变。
与离线修复一样，在线 fsck 的主要用户是系统管理员。在线 fsck 为管理员提供两种操作模式：用于按需在线 fsck 的前台 CLI 进程，以及执行自主检查和修复的后台服务。
对于想要了解文件系统中元数据的绝对最新信息的管理员，可以在命令行上以一个前台进程运行 xfs_scrub。该程序检查文件系统中的每个元数据，同时管理员等待报告结果，就像现有的 xfs_repair 工具一样。这两个工具都共享一个 -n 选项来执行只读扫描，以及一个 -v 选项来增加报告信息的详细程度。
xfs_scrub 的一项新功能是 -x 选项，它利用硬件的纠错功能来检查数据文件内容。默认情况下不启用媒体扫描，因为它可能会大大增加程序运行时间，并在较旧的存储硬件上消耗大量带宽。
前台调用的输出将捕获在系统日志中。
xfs_scrub_all 程序遍历已挂载的文件系统列表，并并行启动每个文件系统的 xfs_scrub。它会对解析为同一顶级内核块设备的任何文件系统进行串行扫描，以防止资源消耗过度。
为了减少系统管理员的工作量，xfs_scrub 包提供了一套 systemd 计时器和服务，默认情况下在周末自动运行在线 fsck。后台服务配置 scrub 以尽可能少的特权运行，最低的 CPU 和 IO 优先级，并在受 CPU 限制的单线程模式下运行。系统管理员可以随时调整此设置，以满足客户工作负载的延迟和吞吐量要求。
后台服务的输出也捕获在系统日志中。如果需要，可以通过在以下服务文件中设置 EMAIL_ADDR 环境变量来自动发送失败（由于不一致或仅仅是运行时错误）的报告
是否启用后台扫描的决定权在于系统管理员。可以通过启用以下任一服务来完成此操作：
此自动每周扫描配置为开箱即用，每月对所有文件数据执行一次额外的介质扫描。这种方法不如存储文件数据块校验和那样可靠，但如果应用软件提供自己的完整性检查，可以在文件系统之上提供冗余，或者认为存储设备的完整性保证足够时，性能会更高。
systemd 单元文件定义已经过安全审计（截至 systemd 249），以确保 xfs_scrub 进程尽可能少地访问系统的其余部分。这是通过 systemd-analyze security 执行的，之后权限被限制为所需的最小值，沙箱设置到使用沙箱和系统调用过滤的最大可能程度；并且对文件系统树的访问被限制为启动程序和访问被扫描的文件系统所需的最小值。服务定义文件将 CPU 使用率限制为一个 CPU 内核的 80%，并尽可能地对 IO 和 CPU 调度应用一个较低的优先级。采取此措施是为了尽量减少文件系统其余部分的延迟。对于 cron 作业，尚未执行此类强化。
建议的补丁集：启用 xfs_scrub 后台服务。
XFS 在内存中缓存每个文件系统运行状况的摘要。每当运行 xfs_scrub 或在常规操作期间检测到文件系统元数据中的不一致时，都会更新此信息。系统管理员应使用 xfs_spaceman 的 health 命令将此信息下载为人类可读的格式。如果观察到问题，管理员可以安排一个缩短的服务窗口来运行在线修复工具来纠正问题。如果无法修复，管理员可以决定安排一个维护窗口来运行传统的离线修复工具来纠正问题。
未来工作问题：运行状况报告是否应该与新的 inotify 文件系统错误通知系统集成？如果系统管理员有一个守护程序来侦听损坏通知并启动修复，是否会有帮助？
答案：这些问题仍然没有答案，但应该是与 XFS 的早期采用者和潜在的下游用户进行对话的一部分。
建议的补丁集包括将运行状况报告连接到更正返回和 在内存回收期间保留故障信息。
本节讨论内核代码的关键算法和数据结构，这些代码和数据结构提供了在系统运行时检查和修复元数据的功能。本节的前几章揭示了为检查元数据提供基础的部分。本节的其余部分介绍了 XFS 自我重建的机制。
XFS 的原始设计（大约在 1993 年）是对 20 世纪 80 年代 Unix 文件系统设计的改进。在那些日子里，存储密度非常昂贵，CPU 时间稀缺，过多的寻道时间可能会扼杀性能。出于性能原因，文件系统作者不愿向文件系统添加冗余，即使以数据完整性为代价。21 世纪初的文件系统设计人员选择不同的策略来增加内部冗余——要么存储几乎相同的元数据副本，要么采用更节省空间的编码技术。
对于 XFS，选择了一种不同的冗余策略来使设计现代化：一个辅助空间使用索引，该索引将已分配的磁盘区段映射回其所有者。通过添加新索引，文件系统保留了在涉及大型数据集的大量线程工作负载中良好扩展的大部分能力，因为主文件元数据（目录树、文件块映射和分配组）保持不变。像任何提高冗余度的系统一样，反向映射功能会增加空间映射活动的开销成本。但是，它有两个关键优势：首先，反向索引是启用在线 fsck 和其他请求功能（如空闲空间碎片整理、更好的介质故障报告和文件系统缩小）的关键。其次，反向映射 btree 的不同磁盘存储格式会阻止设备级重复数据删除，因为文件系统需要真正的冗余。
侧边栏: |
添加辅助索引的一个批评是它无助于提高用户数据存储本身的稳健性。这是一个有效的观点，但是添加用于文件数据块校验和的新索引会通过将数据覆盖变成复制写入来增加写入放大，这会使文件系统过早老化。与三十年的先例保持一致，想要文件数据完整性的用户可以提供他们所需的那样强大的解决方案。至于元数据，添加新的空间使用二级索引的复杂性远小于向 XFS 本身添加卷管理和存储设备镜像。RAID 和卷管理的完善最好留给内核中现有的层。 |
反向空间映射记录中捕获的信息如下：
struct xfs_rmap_irec {
xfs_agblock_t rm_startblock; /* extent start block */
xfs_extlen_t rm_blockcount; /* extent length */
uint64_t rm_owner; /* extent owner */
uint64_t rm_offset; /* offset within the owner */
unsigned int rm_flags; /* state flags */
};
前两个字段捕获物理空间的位置和大小，以文件系统块为单位。所有者字段告诉 scrub 哪个元数据结构或文件 inode 已被分配此空间。对于分配给文件的空间，偏移量字段告诉 scrub 该空间在文件分支中映射的位置。最后，标志字段提供有关空间使用情况的额外信息——这是一个属性分支区段吗？文件映射 btree 区段？还是未写入的数据区段？
在线文件系统检查通过将其信息与所有其他空间索引进行比较来判断每个主元数据记录的一致性。反向映射索引在一致性检查过程中起着关键作用，因为它包含所有空间分配信息的集中式备用副本。程序运行时和资源获取的便利性是在线检查可以咨询的唯一真正限制。例如，可以对照以下内容检查文件数据区段映射：
关于反向映射索引有几个观察结果：
如果上述任何主要元数据存在疑问，反向映射可以提供正确的肯定。大多数主元数据的检查代码遵循类似于上面概述的路径。
证明辅助元数据与主元数据的一致性很困难，因为这需要对所有主空间元数据进行完整扫描，这非常耗时。例如，检查文件区段映射 btree 块的反向映射记录需要锁定该文件并搜索整个 btree 以确认该块。相反，scrub 在主空间映射结构检查期间依赖于严格的交叉引用。
如果所需的锁定顺序与常规文件系统操作使用的顺序不同，则一致性扫描必须使用非阻塞锁获取原语。例如，如果文件系统通常在获取 AGF 缓冲区锁之前获取文件 ILOCK，但 scrub 希望在持有 AGF 缓冲区锁的同时获取文件 ILOCK，则 scrub 不能阻止第二次获取。这意味着如果系统负载很重，则无法保证在反向映射数据扫描的这一部分期间取得进展。
总而言之，反向映射在主元数据的重建中起着关键作用。这些记录如何暂存、写入磁盘并提交到文件系统的详细信息将在后续部分中介绍。
检查元数据结构的第一步是检查结构中包含的每个记录及其与系统其余部分的关系。XFS 包含多层检查，以尝试防止不一致的元数据对系统造成严重破坏。这些层中的每一层都提供信息，帮助内核就元数据结构的运行状况做出三个决定：
此结构的某一部分是否明显损坏 (XFS_SCRUB_OFLAG_CORRUPT)？
此结构是否与系统的其余部分不一致 (XFS_SCRUB_OFLAG_XCORRUPT)？
文件系统周围是否损坏太多以至于无法进行交叉引用 (XFS_SCRUB_OFLAG_XFAIL)？
结构是否可以优化以提高性能或减少元数据的大小（XFS_SCRUB_OFLAG_PREEN）？
结构是否包含不一致但值得系统管理员审查的数据（XFS_SCRUB_OFLAG_WARNING）？
以下部分描述了元数据清理过程的工作方式。
在缓冲区缓存之后，下一级的元数据保护是构建在文件系统中的内部记录验证代码。这些检查在缓冲区验证器、缓冲区缓存的文件系统内部用户和清理代码本身之间进行拆分，具体取决于所需的高级上下文的数量。检查范围仍然在块的内部。这些更高层次的检查函数会回答以下问题：
此类别中的记录检查更加严格且耗时。例如，会检查块指针和 inode 编号，以确保它们指向分配组的动态分配部分和文件系统内部。会检查名称是否存在无效字符，并检查标志是否存在无效组合。还会检查其他记录属性是否存在合理的值。btree 记录跨越 btree 键空间的间隔，会检查其顺序是否正确以及是否缺少可合并性（文件分支映射除外）。出于性能原因，除非启用调试或即将发生写入操作，否则常规代码可能会跳过其中一些检查。当然，清理函数必须检查所有可能的问题。
文件系统元数据的各个部分由用户空间直接控制。由于此性质，验证工作不能比检查值是否在可能的范围内更精确。这些字段包括：
由挂载选项控制的超级块字段
文件系统标签
文件时间戳
文件权限
文件大小
文件标志
目录条目、扩展属性键和文件系统标签中存在的名称
扩展属性键命名空间
扩展属性值
文件数据块内容
配额限制
配额计时器到期时间（如果资源使用超出软限制）
扩展属性实现了一个键值存储，它允许将数据片段附加到任何文件。内核和用户空间都可以访问键和值，但受到命名空间和权限限制。通常，这些片段是关于文件的元数据，例如来源、安全上下文、用户提供的标签、索引信息等。
名称长度可以达到 255 字节，并且可以存在于几个不同的命名空间中。值的大小可以达到 64KB。文件的扩展属性存储在由 attr 分叉映射的块中。这些映射指向叶子块、远程值块或 dabtree 块。属性分叉中的 0 号块始终是结构的顶部，但除此之外，这三种类型的块都可以在 attr 分叉中的任何偏移量处找到。叶子块包含指向名称和值的属性键记录。名称总是存储在同一叶子块的其他位置。小于文件系统块大小 3/4 的值也存储在同一叶子块的其他位置。远程值块包含太大而无法放入叶子块的值。如果叶子信息超过单个文件系统块，则会创建一个 dabtree（也根植于 0 号块）来将属性名称的哈希映射到 attr 分叉中的叶子块。
由于 attr 块和索引块之间缺乏分离，检查扩展属性结构并不那么直接。Scrub 必须读取由 attr 分叉映射的每个块，并忽略非叶子块。
遍历 attr 分叉中的 dabtree（如果存在），以确保块或 dabtree 映射中没有不指向 attr 叶子块的不规则之处。
遍历 attr 分叉的块，寻找叶子块。对于叶子中的每个条目
验证名称不包含无效字符。
读取 attr 值。这将执行 attr 名称的命名查找，以确保 dabtree 的正确性。如果值存储在远程块中，这还会验证远程值块的完整性。
文件系统目录树是一个有向无环图结构，其中文件构成节点，目录项（dirent）构成边。目录是一种特殊类型的文件，包含从 255 字节序列（名称）到 inode 号的映射集合。这些称为目录项，或简称 dirent。每个目录文件必须只有一个指向该文件的目录。根目录指向自身。目录项指向任何类型的文件。每个非目录文件可能有多个目录指向它。
在 XFS 中，目录实现为包含最多三个 32GB 分区的文件。第一个分区包含目录项数据块。每个数据块包含可变大小的记录，这些记录将用户提供的名称与 inode 号以及（可选）文件类型相关联。如果目录项数据增长超过一个块，则第二个分区（以 EOF 后范围的形式存在）将填充一个包含可用空间信息和一个索引的块，该索引将 dirent 名称的哈希映射到第一个分区中的目录数据块。这使得目录名称查找非常快。如果第二个分区增长超过一个块，则第三个分区将填充一个线性排列的可用空间信息，以便更快地扩展。如果可用空间已分离，并且第二个分区再次增长超过一个块，则使用 dabtree 将 dirent 名称的哈希映射到目录数据块。
检查目录非常简单
遍历第二个分区中的 dabtree（如果存在），以确保块或 dabtree 映射中没有不指向 dirent 块的不规则之处。
遍历第一个分区的块，寻找目录项。按如下方式检查每个 dirent
名称是否不包含无效字符？
inode 号是否对应于实际分配的 inode？
子 inode 是否具有非零的链接计数？
如果 dirent 中包含文件类型，它是否与 inode 的类型匹配？
如果子项是子目录，则子项的 dotdot 指针是否指向父项？
如果目录具有第二个分区，则执行 dirent 名称的命名查找，以确保 dabtree 的正确性。
遍历第三个分区中的可用空间列表（如果存在），以确保它描述的可用空间确实未使用。
涉及父级和文件链接计数的检查操作将在后面的章节中更详细地讨论。
如前几节所述，目录/属性 b 树 (dabtree) 索引映射用户提供的名称，以通过避免线性扫描来提高查找时间。在内部，它将名称的 32 位哈希映射到相应文件分叉内的块偏移量。
dabtree 的内部结构与记录固定大小元数据记录的 b 树非常相似——每个 dabtree 块都包含一个魔术数字、一个校验和、同级指针、一个 UUID、一个树级别和一个日志序列号。叶子和节点记录的格式相同——每个条目都指向层次结构中的下一层，其中 dabtree 节点记录指向 dabtree 叶子块，而 dabtree 叶子记录指向分叉中其他位置的非 dabtree 块。
检查和交叉引用 dabtree 与对空间 b 树所做的工作非常相似
块中存储的数据类型是否与清理程序期望的类型匹配？
该块是否属于请求读取的所有结构？
记录是否适合该块？
块内包含的记录是否没有明显的损坏？
名称哈希的顺序是否正确？
dabtree 内的节点指针是否指向 dabtree 块的有效分叉偏移量？
dabtree 内的叶子指针是否指向目录或 attr 叶子块的有效分叉偏移量？
子指针是否指向叶子？
兄弟指针是否指向同一级别？
对于每个 dabtree 节点记录，记录键是否准确反映子 dabtree 块的内容？
对于每个 dabtree 叶子记录，记录键是否准确反映目录或 attr 块的内容？
XFS 维护三类汇总计数器：可用资源、配额资源使用情况和文件链接计数。
理论上，可以通过遍历整个文件系统来找到可用资源量（数据块、inode、实时范围）。这将导致报告非常缓慢，因此事务文件系统可以在超级块中维护此信息的摘要。将这些值与文件系统元数据交叉引用应该只是简单地遍历每个 AG 中的可用空间和 inode 元数据以及实时位图，但在稍后将讨论一些复杂情况。
配额使用情况和文件链接计数检查非常复杂，值得单独讨论。
执行修复后，检查代码将再次运行以验证新结构，并且健康评估的结果将在内部记录并返回给调用进程。此步骤对于使系统管理员能够监视文件系统的状态和任何修复的进度至关重要。对于开发人员来说，它是一种有用的手段，可以判断在线和离线检查工具中错误检测和纠正的有效性。
复杂的操作可以通过一系列事务对多个每个 AG 数据结构进行修改。这些链一旦提交到日志，如果在处理链时系统崩溃，将在日志恢复期间重新启动。由于 AG 标头缓冲区在链中的事务之间是解锁的，因此在线检查必须与正在进行的链式操作协调，以避免由于挂起的链而错误地检测到不一致。此外，当操作挂起时，不得运行在线修复，因为元数据彼此暂时不一致，并且无法重建。
只有在线 fsck 具有对 AG 元数据完全一致性的要求，并且与文件系统更改操作相比应该相对罕见。在线 fsck 按如下方式与事务链协调
这可能会导致在线 fsck 需要很长时间才能完成，但常规的文件系统更新优先于后台检查活动。有关发现这种情况的详细信息将在下一节中介绍，而有关解决方案的详细信息将在之后介绍。
在在线 scrubbing 开发的中途，fsstress 测试发现了在线 fsck 和由其他写入器线程创建的复合事务链之间的错误交互，从而导致了元数据不一致的错误报告。这些报告的根本原因是当引入反向映射和重新链接时，通过扩展延迟工作项和复合事务链引入的最终一致性模型。
最初，将事务链添加到 XFS 中是为了避免从文件中取消映射空间时出现死锁。死锁避免规则要求仅按升序锁定 AG，这使得（例如）无法使用单个事务释放 AG 7 中的空间范围，然后尝试释放 AG 3 中现在多余的块映射 b 树块。为了避免这些类型的死锁，XFS 创建范围释放意图 (EFI) 日志项，以承诺在一个事务中释放某些空间，同时将实际元数据更新延迟到新的事务。事务序列如下所示
第一个事务包含对文件块映射结构的物理更新，以删除 B 树块的映射。然后，它将一个操作项附加到内存中的事务，以安排延迟释放空间。具体而言，每个事务都维护一个 struct xfs_defer_pending 对象列表，每个对象都维护一个 struct xfs_extent_free_item 对象列表。回到上面的示例，该操作项会跟踪释放 AG 7 中未映射的空间以及 AG 3 中的块映射 B 树 (BMBT) 块。以这种方式记录的延迟释放会通过从 struct xfs_extent_free_item 对象创建 EFI 日志项并将该日志项附加到事务来提交到日志中。当日志持久保存到磁盘时，EFI 项会被写入到磁盘上的事务记录中。EFI 可以列出最多 16 个要释放的范围，所有范围都按 AG 顺序排序。
第二个事务包含对 AG 3 的空闲空间 B 树的物理更新，以释放之前的 BMBT 块，以及对 AG 7 的空闲空间 B 树的第二次物理更新，以释放未映射的文件空间。请注意，物理更新在可能的情况下会按正确的顺序重新排序。附加到该事务的是一个范围释放完成 (EFD) 日志项。EFD 包含指向事务 #1 中记录的 EFI 的指针，以便日志恢复可以判断是否需要重放 EFI。
如果系统在事务 #1 写回文件系统后但在 #2 提交之前崩溃，扫描文件系统元数据将显示不一致的文件系统元数据，因为似乎没有任何未映射空间的所有者。幸运的是，日志恢复为我们纠正了这种不一致性——当恢复发现一个意向日志项但没有找到相应的意向完成项时，它将重建意向项的内核状态并完成它。在上面的示例中，日志必须重放已恢复的 EFI 中描述的两个释放操作，才能完成恢复阶段。
XFS 的事务链接策略需要考虑一些微妙之处
必须以正确的顺序将日志项添加到事务中，以防止与事务未持有的主对象发生冲突。换句话说，必须在释放范围的最后更新之前完成未映射块的所有按 AG 元数据更新，并且在最后更新提交到日志之前，不应重新分配范围。
AG 标头缓冲区会在链中的每个事务之间释放。这意味着其他线程可能会观察到处于中间状态的 AG，但只要处理了第一个微妙之处，这就不应影响文件系统操作的正确性。
卸载文件系统会将所有挂起的工作刷新到磁盘，这意味着离线 fsck 永远不会看到由于延迟工作项处理引起的临时不一致性。
通过这种方式，XFS 采用了一种最终一致性的形式来避免死锁并提高并行性。
在反向映射和重链接功能的设计阶段，确定将单个文件系统更改的所有反向映射更新塞进单个事务是不切实际的，因为单个文件映射操作可能会爆炸成许多小更新
块映射更新本身
块映射更新的反向映射更新
修复空闲列表
空闲列表修复的反向映射更新
对块映射 B 树的形状更改
B 树更新的反向映射更新
修复空闲列表（再次）
空闲列表修复的反向映射更新
对引用计数信息的更新
引用计数更新的反向映射更新
修复空闲列表（第三次）
空闲列表修复的反向映射更新
释放任何未映射且不属于任何其他文件的空间
修复空闲列表（第四次）
空闲列表修复的反向映射更新
释放块映射 B 树使用的空间
修复空闲列表（第五次）
空闲列表修复的反向映射更新
每个事务链的每个 AG 通常只需要修复一次空闲列表，但如果空间非常紧张，理论上是可能的。对于写入时复制更新，情况甚至更糟，因为必须完成一次才能将空间从暂存区域中删除，然后再将其映射到文件中！
为了以平静的方式处理这种爆炸式增长，XFS 扩展了其对延迟工作项的使用，以涵盖大多数反向映射更新和所有引用计数更新。这通过将工作分解为一长串小的更新来减少事务预留的最坏情况大小，从而提高了系统中最终一致性的程度。同样，这通常不是问题，因为 XFS 会仔细排序其延迟工作项，以避免不知情的线程之间的资源重用冲突。
但是，在线 fsck 更改了规则——请记住，虽然对每个 AG 结构的物理更新通过锁定 AG 标头的缓冲区来协调，但缓冲区锁会在事务之间释放。一旦 scrub 获取资源并获取数据结构的锁，它必须完成所有验证工作而无需释放锁。如果空间 B 树的主锁是 AG 标头缓冲区锁，则 scrub 可能已中断了另一个线程，该线程正在完成链的过程中。例如，如果执行写入时复制的线程已完成反向映射更新但未完成相应的引用计数更新，则两个 AG B 树对于 scrub 而言将显得不一致，并且会记录到损坏的观察结果。此观察结果将不正确。如果在此状态下尝试修复，结果将是灾难性的！
在发现此缺陷后，评估并拒绝了其他几种解决此问题的方法
为分配组添加更高级别的锁，并要求写入器线程在进行任何更改之前按 AG 顺序获取更高级别的锁。这在实践中很难实现，因为很难在不模拟整个操作的情况下确定需要获取哪些锁以及按什么顺序获取。执行文件操作的空运行以发现必要的锁会使文件系统非常慢。
使延迟工作协调器代码知道针对同一 AG 的连续意向项，并使其在更新之间的事务回滚中保持 AG 标头缓冲区锁定。这将给协调器带来很多复杂性，因为它与实际的延迟工作项松散耦合。这也无法解决问题，因为延迟工作项可以生成新的延迟子任务，但所有子任务都必须在可以开始处理新的同级任务之前完成。
教会在线 fsck 遍历所有等待保护正在被 scrub 的数据结构的锁的事务，以查找挂起的操作。检查和修复操作必须将这些挂起的操作考虑在正在执行的评估中。此解决方案不可行，因为它对主文件系统具有极大的侵入性。
在线 fsck 使用原子意向项计数器和锁循环来与事务链协调。耗尽机制有两个关键属性。首先，当延迟工作项排队到事务时，计数器会递增，并且在关联的意向完成日志项提交到另一个事务后，计数器会递减。第二个属性是，可以将延迟工作添加到事务中而无需持有 AG 标头锁，但是如果不锁定该 AG 标头缓冲区来记录物理更新和意向完成日志项，则无法将每个 AG 工作项标记为完成。第一个属性使 scrub 可以让位于正在运行的事务链，这是对在线 fsck 的明确降级，以使文件操作受益。耗尽的第二个属性是 scrub 正确协调的关键，因为 scrub 始终可以决定是否可能发生冲突。
对于常规文件系统代码，耗尽的工作方式如下
调用适当的子系统函数以将延迟工作项添加到事务中。
该函数调用 xfs_defer_drain_bump 以增加计数器。
当延迟项管理器想要完成延迟工作项时，它会调用 ->finish_item 以完成它。
->finish_item 实现会记录一些更改，并调用 xfs_defer_drain_drop 来减少草率计数器并唤醒任何等待耗尽的线程。
子事务提交，这将解锁与意向项关联的资源。
对于 scrub，耗尽的工作方式如下
锁定与正在被 scrub 的元数据关联的资源。例如，扫描引用计数 B 树将锁定 AGI 和 AGF 标头缓冲区。
如果计数器为零（xfs_defer_drain_busy 返回 false），则没有正在进行的链，并且该操作可以继续。
否则，释放在步骤 1 中获取的资源。
等待意向计数器达到零 (xfs_defer_drain_intents)，然后返回到步骤 1，除非已捕获到信号。
为了避免在步骤 4 中轮询，耗尽提供了一个等待队列，以便在意向计数降至零时唤醒 scrub 线程。
提议的补丁集是scrub 意向耗尽系列。
XFS 的在线 fsck 尽可能将常规文件系统与检查和修复代码分开。但是，在线 fsck 的某些部分（例如意向耗尽，以及稍后的实时更新挂钩）中，在线 fsck 代码知道文件系统的其余部分正在发生什么很有用。由于预计在线 fsck 不会在后台持续运行，因此当在线 fsck 被编译到内核中但未代表用户空间主动运行时，最小化这些挂钩施加的运行时开销非常重要。在写入器线程的热路径中获取锁以访问数据结构，结果发现不需要进一步操作是很昂贵的——在作者的计算机上，每次访问的开销为 40-50 纳秒。幸运的是，内核支持动态代码修补，这使 XFS 可以在在线 fsck 未运行时，使用 nop 滑板替换指向挂钩代码的静态分支。此滑板的开销是指令解码器跳过滑板所需的时间，这似乎小于 1 纳秒，并且不会访问指令获取之外的内存。
当在线 fsck 启用静态键时，雪橇指令会被替换为调用钩子代码的无条件跳转。这种切换的代价相当高（约 22000 纳秒），但完全由调用在线 fsck 的程序承担，如果多个线程同时进入在线 fsck，或者同时检查多个文件系统，则可以分摊成本。更改跳转方向需要获取 CPU 热插拔锁，并且由于 CPU 初始化需要内存分配，因此在线 fsck 必须小心，不要在持有任何可能在内存回收路径中访问的锁或资源时更改静态键。为了最大限度地减少 CPU 热插拔锁的争用，应注意不要不必要地启用或禁用静态键。
由于静态键旨在最小化 xfs_scrub 未运行时常规文件系统操作的钩子开销，因此预期的使用模式如下
XFS 的钩子部分应声明一个默认值为 false 的静态作用域静态键。DEFINE_STATIC_KEY_FALSE 宏负责处理此操作。静态键本身应声明为 static 变量。
当决定调用仅由 scrub 使用的代码时，如果未启用静态键，则常规文件系统应调用 static_branch_unlikely 谓词以避免仅限 scrub 的钩子代码。
常规文件系统应导出调用 static_branch_inc 以启用和调用 static_branch_dec 以禁用静态键的辅助函数。如果内核发行商在构建时关闭了在线 fsck，则包装函数可以轻松编译掉相关代码。
想要启用仅限 scrub 的 XFS 功能的 Scrub 函数应从设置函数调用 xchk_fsgates_enable 来启用特定的钩子。这必须在获取内存回收使用的任何资源之前完成。调用者最好确保他们真的需要静态键控制的功能；TRY_HARDER 标志在这里很有用。
在线 scrub 具有资源获取辅助函数（例如 xchk_perag_lock），用于处理所有 scrubber 函数的 AGI 和 AGF 缓冲区的锁定。如果它检测到 scrub 和正在运行的事务之间存在冲突，它将尝试等待意图完成。如果辅助函数的调用者未启用静态键，则辅助函数将返回 -EDEADLOCK，这应该导致 scrub 使用 TRY_HARDER 标志重新启动。scrub 设置函数应检测到该标志，启用静态键，然后再次尝试 scrub。scrub 拆卸会禁用由 xchk_fsgates_enable 获取的所有静态键。
有关更多信息，请参阅内核文档中的 静态键。
一些在线检查函数的工作原理是扫描文件系统，以在内存中构建磁盘上元数据结构的影子副本，并比较这两个副本。为了使在线修复重建元数据结构，它必须在将新结构持久化到磁盘之前计算将存储在新结构中的记录集。理想情况下，修复以引入新数据结构的单个原子提交完成。为了实现这些目标，内核需要在不需要文件系统正确操作的位置收集大量信息。
内核内存不适合，因为
分配连续的内存区域以创建 C 数组非常困难，尤其是在 32 位系统上。
记录的链表引入了双指针开销，这非常高，并消除了索引查找的可能性。
内核内存被固定，这可能会将系统驱动到 OOM 状态。
系统可能没有足够的内存来暂存所有信息。
在任何给定时间，在线 fsck 不需要将整个记录集保存在内存中，这意味着如果需要，可以分页输出单个记录。在线 fsck 的持续开发表明，执行索引数据存储的能力也非常有用。幸运的是，Linux 内核已经具有字节可寻址和可分页存储的功能：tmpfs。内核图形驱动程序（最值得注意的是 i915）利用 tmpfs 文件来存储不需要始终在内存中的中间数据，因此已经建立了使用先例。因此，xfile 就诞生了！
历史旁注: |
第一版在线修复在找到记录时将其插入到新的 btree 中，但失败了，因为文件系统可以在构建数据结构的情况下关闭，这将在恢复完成后生效。
第二版通过将所有内容存储在内存中解决了半重建结构问题，但经常导致系统内存不足。
第三版通过使用链表解决了 OOM 问题，但列表指针的内存开销非常大。
|
对 xfile 预期用途的调查表明，这些用例
固定大小记录的数组（空间管理 btree、目录和扩展属性条目）
固定大小记录的稀疏数组（配额和链接计数）
可变大小的大型二进制对象 (BLOB)（目录以及扩展属性名称和值）
在内存中暂存 btree（反向映射 btree）
任意内容（实时空间管理）
为了支持前四个用例，高级数据结构包装 xfile 以在在线 fsck 函数之间共享功能。本节的其余部分讨论 xfile 向这五个高级数据结构中的四个提供的接口。第五个用例在 实时摘要 案例研究中讨论。
XFS 是基于记录的，这表明加载和存储完整记录的能力非常重要。为了支持这些情况，提供了一对 xfile_load 和 xfile_store 函数，用于将对象读取并持久化到将任何错误都视为内存不足错误的 xfile 中。对于在线修复，以这种方式压缩错误条件是可以接受的行为，因为唯一的反应是将操作中止返回到用户空间。
但是，如果没有回答“但是 mmap 呢？”这个问题，那么关于文件访问习惯的讨论是不完整的。就像用户空间代码使用常规内存一样，直接使用指针访问存储非常方便。在线 fsck 不得将系统驱动到 OOM 状态，这意味着 xfile 必须对内存回收做出响应。只有当页面缓存 folio 既没有固定也没有锁定时，tmpfs 才能将页面缓存 folio 推送到交换缓存，这意味着 xfile 不能固定太多 folio。
通过锁定页面缓存 folio 并将其映射到内核地址空间来完成对 xfile 内容的短期直接访问。对象加载和存储使用此机制。folio 锁不应长时间持有，因此通过提升 folio 引用计数、将其映射到内核地址空间并放弃 folio 锁来完成对 xfile 内容的长期直接访问。这些长期用户必须通过连接到收缩器基础结构来响应内存回收，以便知道何时释放 folio。
提供了 xfile_get_folio 和 xfile_put_folio 函数来检索支持 xfile 部分的（已锁定）folio 并将其释放。唯一使用这些 folio 租用函数的代码是 xfarray 排序 算法和 内存 btree。
出于安全原因，xfile 必须由内核私有拥有。它们被标记为 S_PRIVATE 以防止安全系统的干扰，绝不能映射到进程文件描述符表中，它们的页面绝不能映射到用户空间进程中。
为了避免与 VFS 的锁定递归问题，对 shmfs 文件的所有访问都是通过直接操作页面缓存来执行的。xfile 写入器调用 xfile 的地址空间的 ->write_begin 和 ->write_end 函数来获取可写页面，将调用者的缓冲区复制到页面中，然后释放页面。xfile 读取器调用 shmem_read_mapping_page_gfp 直接获取页面，然后将内容复制到调用者的缓冲区中。换句话说，xfile 忽略 VFS 读取和写入代码路径，以避免必须创建虚拟 struct kiocb 和避免获取 inode 和冻结锁。tmpfs 无法冻结，xfile 不得暴露给用户空间。
如果 xfile 在线程之间共享以暂存修复，则调用者必须提供自己的锁来协调访问。例如，如果 scrub 函数将扫描结果存储在 xfile 中，并且需要其他线程提供对扫描数据的更新，则 scrub 函数必须为所有线程提供共享的锁。
在 XFS 中，每种类型的索引空间元数据（可用空间、inode、引用计数、文件分支空间和反向映射）都由一组固定大小的记录组成，这些记录使用经典的 B+ 树进行索引。目录有一组指向名称的固定大小的目录项记录，扩展属性有一组指向名称和值的固定大小的属性键。配额计数器和文件链接计数器使用数字索引记录。在修复过程中，擦除操作需要在收集步骤中暂存新记录，并在构建 B 树步骤中检索这些记录。
尽管可以通过直接调用 xfile 的读取和写入方法来满足此要求，但对于调用者来说，使用更高层次的抽象来处理计算数组偏移、提供迭代器函数以及处理稀疏记录和排序会更简单。 xfarray 抽象在字节可访问的 xfile 之上呈现一个固定大小记录的线性数组。
在线 fsck 中的数组访问模式通常分为三类。所有情况都假设需要迭代记录，这将在下一节中介绍。
第一种类型的调用者处理按位置索引的记录。记录之间可能存在间隙，并且在收集步骤中，一个记录可能会被多次更新。换句话说，这些调用者需要一个稀疏的线性寻址表文件。典型的用例是配额记录或文件链接计数记录。通过 xfarray_load 和 xfarray_store 函数以编程方式执行对数组元素的访问，这些函数封装了名称相似的 xfile 函数，以提供在任意数组索引处加载和存储数组元素的功能。间隙定义为空记录，空记录定义为全部为零的字节序列。通过调用 xfarray_element_is_null 检测空记录。它们可以通过调用 xfarray_unset 来将现有记录置为空，或者通过从未向数组索引存储任何内容来创建。
第二种类型的调用者处理不由位置索引且不需要对记录进行多次更新的记录。这里的典型用例是重建空间 B 树和键/值 B 树。这些调用者可以通过 xfarray_append 函数将记录添加到数组，而无需关心数组索引，该函数将记录存储在数组的末尾。对于需要以特定顺序呈现记录的调用者（例如，重建 B 树数据），xfarray_sort 函数可以安排排序后的记录；此函数将在后面介绍。
第三种类型的调用者是包，它对于计算记录很有用。这里的典型用例是从反向映射信息构建空间范围引用计数。记录可以按任意顺序放入包中，可以随时从包中删除，并且记录的唯一性留给调用者处理。xfarray_store_anywhere 函数用于将记录插入包中的任何空记录槽；xfarray_unset 函数从包中删除记录。
提议的补丁集是大型内存数组。
大多数 xfarray 用户都需要能够迭代存储在数组中的记录。调用者可以使用以下方法探测每个可能的数组索引
xfarray_idx_t i;
foreach_xfarray_idx(array, i) {
xfarray_load(array, i, &rec);
/* do something with rec */
}
此习语的所有用户都必须准备好处理空记录，或者必须已经知道没有空记录。
对于想要迭代稀疏数组的 xfarray 用户，xfarray_iter 函数会忽略 xfarray 中从未写入过的索引，方法是调用 xfile_seek_data（其内部使用 SEEK_DATA）来跳过未填充内存页面的数组区域。一旦找到页面，它将跳过页面的零区域。
xfarray_idx_t i = XFARRAY_CURSOR_INIT;
while ((ret = xfarray_iter(array, &i, &rec)) == 1) {
/* do something with rec */
}
在第四次在线修复演示期间，一位社区评论员指出，出于性能原因，在线修复应该将批量记录加载到 B 树记录块中，而不是一次将记录插入到新的 B 树中。XFS 中的 B 树插入代码负责维护记录的正确顺序，因此自然地，xfarray 还必须支持在批量加载之前对记录集进行排序。
xfarray 中使用的排序算法实际上是自适应快速排序和堆排序子算法的组合，其灵感来自 Sedgewick 和 pdqsort，并针对 Linux 内核进行了自定义。为了在相对较短的时间内对记录进行排序，xfarray 利用快速排序提供的二进制子分区，但它也使用堆排序来对冲如果选择的快速排序枢轴较差时的性能崩溃。这两种算法（通常）都是 O(n * lg(n))，但两种实现之间存在很大的性能差距。
Linux 内核已经包含一个相当快的堆排序实现。它仅适用于常规 C 数组，这限制了其适用范围。xfarray 使用它的两个关键位置是
换句话说，xfarray 使用堆排序来约束快速排序的嵌套递归，从而缓解快速排序的最坏运行时行为。
选择快速排序枢轴是一件棘手的事情。一个好的枢轴将要排序的集合分成两半，从而导致对于 O(n * lg(n)) 性能至关重要的分而治之的行为。一个糟糕的枢轴几乎没有分割子集，从而导致 O(n2) 运行时。xfarray 排序例程尝试通过将九个记录采样到内存缓冲区中并使用内核堆排序来识别九个记录的中位数来避免选择错误的枢轴。
大多数现代快速排序实现都采用 Tukey 的“九点中值”来从经典 C 数组中选择枢轴。典型的九点中值实现会选择三个唯一的记录三元组，对每个三元组进行排序，然后对每个三元组的中间值进行排序以确定九点中值。但是，如前所述，xfile 访问并非完全便宜。事实证明，将九个元素读取到内存缓冲区中，在缓冲区上运行内核的内存堆排序，并选择该缓冲区的第 4 个元素作为枢轴，其性能要高得多。 Tukey 的九点中值在 J. W. Tukey，《The ninther, a technique for low-effort robust (resistant) location in large samples》，Contributions to Survey Sampling and Applied Statistics，H. David 编辑，（Academic Press，1978），pp. 251–257 中描述。
快速排序的分区相当简单——围绕枢轴重新排列记录子集，然后设置当前和下一个堆栈帧，分别对枢轴的较大和较小的一半进行排序。这使得堆栈空间需求保持为 log2（记录数）。
作为最后的性能优化，快速排序的 hi 和 lo 扫描阶段会尽可能长时间地将检查过的 xfile 页面映射到内核中，以减少映射/取消映射周期。令人惊讶的是，在考虑直接将堆排序应用于 xfile 页面后，这会将整体排序运行时间缩短近一半。
扩展属性和目录增加了暂存记录的额外要求：任意长度的有限字节序列。每个目录条目记录都需要存储条目名称，每个扩展属性都需要存储属性名称和值。名称、键和值可能会占用大量内存，因此创建了 xfblob 抽象，以简化 xfile 之上这些 blob 的管理。
Blob 数组提供 xfblob_load 和 xfblob_store 函数来检索和持久化对象。存储函数为它持久化的每个对象返回一个魔术 cookie。稍后，调用者将此 cookie 提供给 xblob_load 以回忆该对象。xfblob_free 函数释放特定的 blob，xfblob_truncate 函数释放所有 blob，因为不需要压缩。
修复目录和扩展属性的详细信息将在后续关于原子文件内容交换的部分中讨论。但是，应该注意的是，这些修复函数仅使用 blob 存储来缓存少量条目，然后将其添加到临时的磁盘文件中，这就是为什么不需要压缩的原因。
提议的补丁集位于 扩展属性修复系列的开头。
关于辅助元数据的章节提到，检查和修复辅助元数据通常需要文件系统的实时元数据扫描与更新该元数据的写入线程之间的协调。保持扫描数据最新需要将元数据更新从文件系统传播到扫描收集的数据中的能力。这可以通过将并发更新附加到单独的日志文件中，并在将新元数据写入磁盘之前应用它们来完成，但是如果系统的其余部分非常繁忙，这会导致无限制的内存消耗。另一种选择是跳过侧日志，并将来自文件系统的实时更新直接提交到扫描数据中，这会以更高的开销换取更低的最高内存需求。在这两种情况下，保存扫描结果的数据结构都必须支持索引访问才能表现良好。
鉴于两种策略都需要对扫描数据进行索引查找，在线 fsck 采用第二种策略，将实时更新直接提交到扫描数据中。因为 xfarray 没有索引并且不强制记录顺序，所以它们不适合这项任务。然而，方便的是，XFS 有一个库来创建和维护有序的反向映射记录：现有的 rmap btree 代码！如果有一种方法可以在内存中创建一个就好了。
回想一下，xfile 抽象将内存页表示为常规文件，这意味着内核可以随意创建字节或块可寻址的虚拟地址空间。XFS 缓冲区缓存专门用于抽象到面向块的地址空间的 IO，这意味着将缓冲区缓存调整为与 xfile 接口可以重用整个 btree 库。构建在 xfile 之上的 btree 统称为 xfbtree。接下来的几个部分将描述它们是如何工作的。
提出的补丁集是内存 btree 系列。
需要进行两项修改才能支持将 xfile 作为缓冲区缓存目标。第一个是使 struct xfs_buftarg 结构能够容纳 struct xfs_buf rhashtable，因为通常这些是由每个 AG 结构保存的。第二个更改是修改缓冲区 ioapply 函数以从 xfile “读取” 缓存的页面，并将缓存的页面 “写回” 到 xfile。对单个缓冲区的多次访问由 xfs_buf 锁控制，因为 xfile 本身不提供任何锁定。通过这种适配，xfile 支持的缓冲区缓存的用户使用与磁盘支持的缓冲区缓存的用户完全相同的 API。xfile 和缓冲区缓存之间的分离意味着更高的内存使用率，因为它们不共享页面，但此属性有一天可能会实现对内存中 btree 的事务性更新。然而，今天，它只是消除了对新代码的需求。
xfile 的空间管理非常简单 - 每个 btree 块的大小为一个内存页。这些块使用与磁盘上的 btree 相同的头部格式，但内存中的块验证器会忽略校验和，假设 xfile 内存不比常规 DRAM 更容易损坏。在此重用现有代码比绝对内存效率更重要。
xfbtree 支持的 xfile 的第一个块包含一个头部块。头部描述了所有者、高度和根 xfbtree 块的块号。
要分配一个 btree 块，请使用 xfile_seek_data 来查找文件中的空隙。如果没有空隙，则通过扩展 xfile 的长度来创建一个。使用 xfile_prealloc 为该块预分配空间，然后返回该位置。要释放一个 xfbtree 块，请使用 xfile_discard（内部使用 FALLOC_FL_PUNCH_HOLE）从 xfile 中删除内存页。
想要创建一个 xfbtree 的在线 fsck 函数应按以下步骤进行
调用 xfile_create 来创建一个 xfile。
调用 xfs_alloc_memory_buftarg 来创建一个指向 xfile 的缓冲区缓存目标结构。
将缓冲区缓存目标、缓冲区操作和其他信息传递给 xfbtree_init 以初始化传入的 struct xfbtree 并将初始根块写入 xfile。每个 btree 类型都应定义一个包装器，该包装器将必要的参数传递给创建函数。例如，rmap btree 定义 xfs_rmapbt_mem_create 来处理调用者所需的所有详细信息。
将 xfbtree 对象传递给 btree 类型的 btree 光标创建函数。按照上面的示例，xfs_rmapbt_mem_cursor 为调用者处理此问题。
将 btree 光标传递给常规 btree 函数以对内存中的 btree 进行查询和更新。例如，rmap xfbtree 的 btree 光标可以像任何其他 btree 光标一样传递给 xfs_rmap_* 函数。有关处理记录到事务的 xfbtree 更新的信息，请参见下一节。
完成后，删除 btree 光标，销毁 xfbtree 对象，释放缓冲区目标，并销毁 xfile 以释放所有资源。
虽然重用 rmap btree 代码来处理暂存结构是一种巧妙的技巧，但内存中 btree 块存储的短暂性本身也带来了一些挑战。XFS 事务管理器不得为 xfile 支持的缓冲区提交缓冲区日志项，因为日志格式不了解除数据设备之外的设备的更新。一个临时的 xfbtree 可能在 AIL 将日志事务检查点写回文件系统时不存在，并且在日志恢复期间肯定不存在。由于这些原因，任何在事务上下文中更新 xfbtree 的代码都必须从事务中删除缓冲区日志项，并在提交或取消事务之前将更新写入支持的 xfile。
xfbtree_trans_commit 和 xfbtree_trans_cancel 函数按如下方式实现此功能
查找其缓冲区以 xfile 为目标的每个缓冲区日志项。
记录日志项的脏/有序状态。
从缓冲区分离日志项。
将缓冲区排队到特殊的 delwri 列表中。
如果唯一的脏日志项是在步骤 3 中分离的日志项，则清除事务脏标志。
如果正在提交更新，则提交 delwri 列表以将更改提交到 xfile。
以这种方式从事务中删除 xfile 日志缓冲区后，可以提交或取消事务。
如前所述，早期版本的在线修复通过创建新的 btree 并单独添加观察结果来构建新的 btree 结构。一次加载一个记录的 btree 有一个小的优点，即不需要在提交之前对内存中的记录进行排序，但是非常慢，并且如果在修复期间系统崩溃，则会泄漏块。一次加载一个记录还意味着修复无法控制新 btree 中块的加载因子。
幸运的是，历史悠久的 xfs_repair 工具有一种更有效的方法，可以从记录集合中重建 btree 索引 - 批量 btree 加载。这是以相当低效的代码方式实现的，因为 xfs_repair 为每个 btree 类型都有单独的复制粘贴实现。
为了准备在线 fsck，研究了四个批量加载器中的每一个，记下了笔记，并将四个重构为一个通用的 btree 批量加载机制。这些笔记也进行了刷新，并在下面呈现。
批量加载的第零步是组装将存储在新 btree 中的整个记录集，并对记录进行排序。接下来，调用 xfs_btree_bload_compute_geometry 以从记录集、btree 类型和任何加载因子首选项计算 btree 的形状。此信息是资源预留所必需的。
首先，几何计算从 btree 块的大小和块头的大小计算出适合叶子块的最小和最大记录数。粗略地说，最大记录数是
maxrecs = (block_size - header_size) / record_size
XFS 设计规定，应尽可能合并 B 树块，这意味着最小记录数是最大记录数的一半。
接下来要确定的变量是期望的加载因子。它必须至少为 minrecs，且不超过 maxrecs。选择 minrecs 是不可取的，因为它会浪费一半的块。选择 maxrecs 也是不可取的，因为向每个新重建的叶子块添加单个记录都会导致树分裂，从而立即导致性能明显下降。默认的加载因子被选择为 maxrecs 的 75%，这提供了一个相当紧凑的结构，而没有任何直接的分裂惩罚。
default_load_factor = (maxrecs + minrecs) / 2
如果空间紧张，加载因子将被设置为 maxrecs，以尽量避免空间耗尽。
leaf_load_factor = enough space ? default_load_factor : maxrecs
对于 B 树节点块，加载因子是使用 B 树键和指针的组合大小作为记录大小计算的。
maxrecs = (block_size - header_size) / (key_size + ptr_size)
minrecs = maxrecs / 2
node_load_factor = enough space ? default_load_factor : maxrecs
一旦完成，存储记录集所需的叶子块数量可以计算为：
leaf_blocks = ceil(record_count / leaf_load_factor)
指向树中下一层的节点块数量计算为：
n_blocks = (n == 0 ? leaf_blocks : node_blocks[n])
node_blocks[n + 1] = ceil(n_blocks / node_load_factor)
整个计算以递归方式执行，直到当前层只需要一个块为止。结果几何形状如下：
对于以 AG 为根的 B 树，这一层是根层，因此新树的高度为 level + 1，所需空间是每层块数的总和。
对于以 inode 为根的 B 树，当顶层记录不适合 inode fork 区域时，高度为 level + 2，所需空间是每层块数的总和，并且 inode fork 指向根块。
对于以 inode 为根的 B 树，当顶层记录可以存储在 inode fork 区域时，根块可以存储在 inode 中，高度为 level + 1，所需空间比每层块数的总和少一个。这只有在非 bmap B 树获得在 inode 中扎根的能力时才变得相关，这是一个未来的补丁集，此处仅为完整性而包含。
一旦修复知道新 B 树所需的块数，它将使用可用空间信息分配这些块。每个预留的范围都由 B 树构建器状态数据单独跟踪。为了提高崩溃恢复能力，预留代码还会在每次空间分配的同一事务中记录一个范围释放意向 (EFI) 项，并将其内存中的 struct xfs_extent_free_item 对象附加到空间预留。如果系统崩溃，日志恢复将使用未完成的 EFI 来释放未使用的空间，即可用空间，使文件系统保持不变。
每次 B 树构建器从预留范围中声明一个用于 B 树的块时，它都会更新内存中的预留以反映声明的空间。块预留尝试分配尽可能多的连续空间，以减少正在使用的 EFI 的数量。
当修复正在写入这些新的 B 树块时，为空间预留创建的 EFI 会固定磁盘日志的尾部。系统的其他部分可能会保持忙碌，并将日志的头部推向固定的尾部。为避免文件系统死锁，EFI 不得将日志的尾部固定太久。为了缓解这个问题，此处重用了延迟操作机制的动态重新记录功能，以提交一个包含旧 EFI 的 EFD 和头部的新 EFI 的日志头部的事务。这使日志能够释放旧的 EFI，以保持日志向前移动。
EFI 在提交和回收阶段发挥作用；请参阅下一节以及关于回收的章节，了解更多详细信息。
提议的补丁集是位图重构和批量加载 B 树的准备工作。
这部分非常简单 —— B 树构建器 (xfs_btree_bulkload) 从预留列表中声明一个块，写入新的 B 树块头，用记录填充块的其余部分，并将新的叶子块添加到已写入块的列表中。
┌────┐
│leaf│
│RRR │
└────┘
每次向该层添加新块时，都会设置兄弟指针。
┌────┐ ┌────┐ ┌────┐ ┌────┐
│leaf│→│leaf│→│leaf│→│leaf│
│RRR │←│RRR │←│RRR │←│RRR │
└────┘ └────┘ └────┘ └────┘
当它完成写入记录叶子块时，它会移动到节点块。为了填充节点块，它会遍历树中下一层的每个块，以计算相关的键并将它们写入父节点。
┌────┐ ┌────┐
│node│──────→│node│
│PP │←──────│PP │
└────┘ └────┘
↙ ↘ ↙ ↘
┌────┐ ┌────┐ ┌────┐ ┌────┐
│leaf│→│leaf│→│leaf│→│leaf│
│RRR │←│RRR │←│RRR │←│RRR │
└────┘ └────┘ └────┘ └────┘
当它到达根级别时，它已准备好提交新的 B 树！
┌─────────┐
│ root │
│ PP │
└─────────┘
↙ ↘
┌────┐ ┌────┐
│node│──────→│node│
│PP │←──────│PP │
└────┘ └────┘
↙ ↘ ↙ ↘
┌────┐ ┌────┐ ┌────┐ ┌────┐
│leaf│→│leaf│→│leaf│→│leaf│
│RRR │←│RRR │←│RRR │←│RRR │
└────┘ └────┘ └────┘ └────┘
提交新 B 树的第一步是将 B 树块同步持久化到磁盘。这有点复杂，因为新的 B 树块可能在最近被释放，因此构建器必须使用 xfs_buf_delwri_queue_here 从 AIL 列表中删除（过时的）缓冲区，然后才能将新块写入磁盘。块使用 delwri 列表排队进行 IO，并使用 xfs_buf_delwri_submit 一次性写入。
一旦新块已持久化到磁盘，控制权将返回到调用批量加载器的单个修复函数。修复函数必须在事务中记录新根的位置，清除为新 B 树创建的空间预留，并回收旧的元数据块。
提交新 B 树根的位置。
对于每个内存中的预留：
为 B 树构建器消耗的所有空间记录范围释放完成 (EFD) 项。新的 EFD 必须指向附加到预留的 EFI，以防止日志恢复释放新块。
对于内存预留的未声明部分，创建一个常规的延迟范围释放工作项，以便稍后在事务链中释放未使用的空间。
在步骤 2a 和 2b 中记录的 EFD 和 EFI 不得超出提交事务的预留。如果 B 树加载代码怀疑这种情况可能即将发生，则必须调用 xrep_defer_finish 来清除延迟的工作并获得新的事务。
第二次清除延迟的工作，以完成提交并清除修复事务。
步骤 2c 和 3 中滚动的事务代表了修复算法中的一个弱点，因为在回收步骤结束之前发生日志刷新和崩溃可能会导致空间泄漏。在线修复功能通过使用非常大的事务来最大限度地减少这种情况发生的可能性，每个事务都可以容纳数千个块释放指令。修复继续回收旧块，这将在对批量加载进行一些案例研究后在后续的章节中介绍。
重建 inode 索引 B 树的高级过程是：
遍历反向映射记录，从 inode 块信息和旧 inode B 树块的位图生成 struct xfs_inobt_rec 记录。
按 inode 顺序将记录附加到 xfarray 中。
使用 xfs_btree_bload_compute_geometry 函数计算 inode B 树所需的块数。如果启用了可用空间 inode B 树，则再次调用它以估计 finobt 的几何形状。
分配上一步中计算出的块数。
使用 xfs_btree_bload 将 xfarray 记录写入 B 树块并生成内部节点块。如果启用了可用空间 inode B 树，则再次调用它以加载 finobt。
将新 B 树根块的位置提交到 AGI。
使用步骤 1 中创建的位图回收旧的 B 树块。
详细信息如下。
inode B 树将 inode 号映射到关联 inode 记录的磁盘位置，这意味着 inode B 树可以从反向映射信息重建。所有者为 XFS_RMAP_OWN_INOBT 的反向映射记录标记旧 inode B 树块的位置。所有者为 XFS_RMAP_OWN_INODES 的每个反向映射记录标记至少一个 inode 群集缓冲区的位置。群集是可以在单个事务中分配或释放的最小数量的磁盘 inode；它永远不小于 1 个 fs 块或 4 个 inode。
对于每个 inode 群集表示的空间，请确保可用空间 B 树中没有记录，引用计数 B 树中也没有任何记录。如果有，空间元数据不一致足以中止操作。否则，读取每个群集缓冲区以检查其内容是否似乎是磁盘 inode，并确定文件是已分配 (xfs_dinode.i_mode != 0) 还是空闲 (xfs_dinode.i_mode == 0)。累积连续 inode 群集缓冲区读取的结果，直到有足够的信息来填充单个 inode 块记录，即 inode 号键空间中连续的 64 个数字。如果该块是稀疏的，则该块记录可能包含空洞。
一旦修复函数累积了一个块的数据，它会调用 xfarray_append 将 inode btree 记录添加到 xfarray。此 xfarray 在 btree 创建步骤中被遍历两次 —— 一次用于使用所有 inode 块记录填充 inode btree，另一次用于使用具有空闲非稀疏 inode 的块记录填充空闲 inode btree。inode btree 的记录数量是 xfarray 记录的数量，但空闲 inode btree 的记录计数必须在 inode 块记录存储在 xfarray 中时计算。
提议的补丁集是 AG btree 修复 系列。
反向映射记录用于重建引用计数信息。引用计数对于共享文件数据的写时复制的正确操作是必需的。将反向映射条目想象为表示物理块范围的矩形，并且可以放置这些矩形以便它们可以相互重叠。从下图可以明显看出，引用计数记录必须在堆栈高度发生变化的地方开始或结束。换句话说，记录发射刺激是电平触发的。
█ ███
██ █████ ████ ███ ██████
██ ████ ███████████ ████ █████████
████████████████████████████████ ███████████
^ ^ ^^ ^^ ^ ^^ ^^^ ^^^^ ^ ^^ ^ ^ ^
2 1 23 21 3 43 234 2123 1 01 2 3 0
磁盘上的引用计数 btree 不存储 refcount == 0 的情况，因为空闲空间 btree 已经记录了哪些块是空闲的。用于暂存写时复制操作的范围应该是 refcount == 1 的唯一记录。单所有者文件块不会记录在空闲空间或引用计数 btree 中。
重建引用计数 btree 的高层过程是
遍历反向映射记录，为任何具有多个反向映射的空间生成 struct xfs_refcount_irec 记录，并将它们添加到 xfarray。属于 XFS_RMAP_OWN_COW 的任何记录也会添加到 xfarray，因为这些是分配用于暂存写时复制操作的范围，并在 refcount btree 中进行跟踪。
使用属于 XFS_RMAP_OWN_REFC 的任何记录来创建旧的 refcount btree 块的位图。
按物理范围顺序对记录进行排序，将 CoW 暂存范围放在 xfarray 的末尾。这与 refcount btree 中记录的排序顺序相匹配。
使用 xfs_btree_bload_compute_geometry 函数来计算新树所需的块数。
分配上一步中计算出的块数。
使用 xfs_btree_bload 将 xfarray 记录写入 btree 块并生成内部节点块。
将新 btree 根块的位置提交到 AGF。
使用步骤 1 中创建的位图回收旧的 B 树块。
详细信息如下；xfs_repair 使用相同的算法从反向映射记录生成 refcount 信息。
在这种情况下，类似包的结构是第 2 类 xfarray，如 xfarray 访问模式 部分所述。使用 xfarray_store_anywhere 将反向映射添加到包中，并通过 xfarray_unset 删除。通过 xfarray_iter 循环检查包成员。
提议的补丁集是 AG btree 修复 系列。
重建数据/attr fork 映射 btree 的高层过程是
遍历反向映射记录，从该 inode 和 fork 的反向映射记录生成 struct xfs_bmbt_rec 记录。将这些记录附加到 xfarray。从 BMBT_BLOCK 记录计算旧的 bmap btree 块的位图。
使用 xfs_btree_bload_compute_geometry 函数来计算新树所需的块数。
按文件偏移量顺序对记录进行排序。
如果范围记录可以放入 inode fork 的直接区域，则将记录提交到该直接区域并跳至步骤 8。
分配上一步中计算出的块数。
使用 xfs_btree_bload 将 xfarray 记录写入 btree 块并生成内部节点块。
将新的 btree 根块提交到 inode fork 的直接区域。
使用步骤 1 中创建的位图回收旧的 B 树块。
这里有一些复杂性：首先，如果数据和 attr fork 都不在 BMBT 格式中，则可以移动 fork 偏移量以调整直接区域的大小。其次，如果有足够少量的 fork 映射，则可以使用 EXTENTS 格式而不是 BMBT，这可能需要进行转换。第三，必须小心地重新加载内存中的范围映射，以避免干扰任何延迟分配的范围。
提议的补丁集是 文件映射修复 系列。
必须小心处理 Inode 记录，因为它们既有磁盘记录（“dinodes”）又有内存（“缓存”）表示形式。如果在线 fsck 不注意仅在磁盘元数据损坏到文件系统无法加载内存表示形式时访问磁盘元数据，则存在很高的缓存一致性问题。当在线 fsck 想要打开一个损坏的文件进行清理时，它必须使用专门的资源获取函数，这些函数返回内存表示形式或锁定任何必要的对象，以防止对磁盘位置进行任何更新。
应该对磁盘 inode 缓冲区进行的唯一修复是加载核心结构所需的任何修复。这意味着修复 inode 集群缓冲区和 inode 分支验证器捕获的任何内容，然后重试 iget 操作。如果第二个 iget 失败，则修复失败。
一旦加载了内存表示形式，修复就可以锁定 inode，并可以对其进行全面的检查、修复和优化。大多数 inode 属性都易于检查和约束，或者是用户控制的任意位模式；这些都易于修复。处理数据和 attr 分支盘区计数以及文件块计数更为复杂，因为计算正确的值需要遍历分支，或者如果该操作失败，则保留字段无效并等待分支 fsck 函数运行。
建议的补丁集是 inode 修复系列。
与 inode 类似，配额记录（“dquots”）也具有磁盘记录和内存表示形式，因此会遇到相同的缓存一致性问题。有些令人困惑的是，在 XFS 代码库中，两者都被称为 dquots。
应该对磁盘配额记录缓冲区进行的唯一修复是加载核心结构所需的任何修复。一旦加载了内存表示形式，唯一需要检查的属性是明显错误的限制和计时器值。
配额使用计数器将在 实时 quotacheck 部分中单独检查、修复和讨论。
建议的补丁集是 quota 修复系列。
文件系统摘要计数器跟踪文件系统资源（如可用块、可用 inode 和已分配 inode）的可用性。此信息可以通过遍历可用空间和 inode 索引来编译，但这很慢，因此 XFS 在磁盘超级块中维护一个副本，该副本应反映磁盘元数据，至少在文件系统已干净地卸载时。出于性能原因，XFS 还维护这些计数器的核心副本，这对于为活动事务启用资源预留至关重要。写入器线程从核心计数器中预留最坏情况下的资源量，并在提交时返回任何未使用的资源。因此，仅当超级块被提交到磁盘时，才需要对超级块进行序列化。
XFS v5 中引入的延迟超级块计数器功能更进一步，通过训练日志恢复来重新计算来自 AG 标头的摘要计数器，这消除了大多数事务甚至触及超级块的需要。XFS 提交摘要计数器的唯一时间是在文件系统卸载时。为了进一步减少争用，核心计数器被实现为 percpu 计数器，这意味着每个 CPU 都从全局核心计数器中分配一批块，并且可以满足本地批次中的少量分配。
摘要计数器的高性能特性使得在线 fsck 难以检查它们，因为在系统运行时没有办法使 percpu 计数器静止。尽管在线 fsck 可以读取文件系统元数据来计算摘要计数器的正确值，但无法保持 percpu 计数器的值稳定，因此很可能在遍历完成时计数器将过期。早期版本的在线清理程序会使用不完整的扫描标志返回到用户空间，但这对于系统管理员来说不是一个令人满意的结果。对于修复，必须在遍历文件系统元数据以获取准确的读取并将其安装在 percpu 计数器中时，稳定内存中的计数器。
为了满足此要求，在线 fsck 必须阻止系统中其他程序启动新的文件系统写入，它必须禁用后台垃圾回收线程，并且必须等待现有写入程序退出内核。一旦建立，清理程序就可以遍历 AG 可用空间索引、inode btree 和实时位图，以计算所有四个摘要计数器的正确值。这与文件系统冻结非常相似，尽管并非所有部分都是必需的。
有了这段代码，现在就可以暂停文件系统，以便有足够的时间检查和纠正摘要计数器。
历史旁注: |
最初的实现使用实际的 VFS 文件系统冻结机制来使文件系统活动静止。在文件系统冻结的情况下，可以精确地解析计数器值，但直接调用 VFS 方法存在许多问题。
其他程序可以在我们不知情的情况下解冻文件系统。这会导致扫描结果不正确和修复不正确。 为了添加额外的锁以防止其他程序解冻文件系统，需要添加一个 ->freeze_super 函数来包装 freeze_fs()。反过来，这会导致其他微妙的问题，因为事实证明，VFS freeze_super 和 thaw_super 函数可能会删除对 VFS 超级块的最后一个引用，并且任何后续访问都会成为 UAF 错误！如果底层块设备冻结了文件系统，而该文件系统被卸载，则可能会发生这种情况。可以通过获取超级块的额外引用来解决此问题，但考虑到此方法的其他不足之处，感觉这不是最佳选择。 无需使日志静止即可检查摘要计数器，但 VFS 冻结无论如何都会启动一个。这会给实时的 fscounter fsck 操作增加不必要的运行时。 使日志静止意味着 XFS 会将（可能不正确的）计数器刷新到磁盘，作为清理日志的一部分。 VFS 中的一个错误意味着即使 sync_filesystem 未能刷新文件系统并返回错误，冻结也可能完成。该错误已在 Linux 5.17 中修复。
|
建议的补丁集是 摘要计数器清理 系列。
某些类型的元数据只能通过遍历整个文件系统中的每个文件来检查，以记录观察结果，并将观察结果与磁盘上记录的内容进行比较。与所有其他类型的在线修复一样，修复是通过将这些观察结果写入磁盘上的替换结构并以原子方式提交来进行的。但是，关闭整个文件系统来检查数千亿个文件是不切实际的，因为停机时间会过长。因此，在线 fsck 必须构建基础架构来管理对文件系统中所有文件的实时扫描。要执行实时遍历，需要解决两个问题
清理在收集数据时如何管理扫描？
扫描如何跟上其他线程对系统所做的更改？
在 1970 年代的原始 Unix 文件系统中，每个目录条目都包含一个索引号 (inumber)，该索引号用作固定大小记录 (inodes) 的磁盘数组 (itable) 的索引，这些记录描述文件的属性及其数据块映射。J. Lions 在 “inode (5659)” 中描述了此系统，出自 Lions’ Commentary on UNIX, 6th Edition，（新南威尔士大学计算机科学系，1977 年 11 月），第 18-2 页；以及 D. Ritchie 和 K. Thompson 在 “文件系统的实现” 中描述了此系统，出自 The UNIX Time-Sharing System，（贝尔系统技术期刊，1978 年 7 月），第 1913-4 页。
XFS 保留了大部分这种设计，只是现在的 inumber 是在数据部分文件系统的所有空间上的搜索键。它们形成一个连续的键空间，可以表示为 64 位整数，尽管 inode 本身稀疏地分布在键空间中。扫描在 inumber 键空间中以线性方式进行，从 0x0 开始，到 0xFFFFFFFFFFFFFFFF 结束。自然地，遍历键空间的扫描需要一个扫描游标对象来跟踪扫描进度。由于此键空间是稀疏的，因此该游标包含两个部分。此扫描游标对象的第一个部分跟踪下一个要检查的 inode；称之为检查游标。不那么明显的是，扫描游标对象还必须跟踪已访问过的键空间的哪些部分，这对于决定是否需要将并发文件系统更新合并到扫描数据中至关重要。称之为已访问的 inode 游标。
推进扫描游标是一个多步骤过程，封装在 xchk_iscan_iter 中。
锁定包含由已访问的 inode 游标指向的 inode 的 AG 的 AGI 缓冲区。这保证了在推进游标时，无法分配或释放此 AG 中的 inode。
使用每个 AG 的 inode btree 来查找刚刚访问过的 inode 之后的下一个 inumber，因为它可能不是键空间相邻的。
如果此 AG 中没有剩余的 inode
将检查游标移动到 inumber 键空间中与下一个 AG 的开头对应的点。
调整已访问的 inode 游标，以指示它已“访问”了当前 AG 的 inode 键空间中的最后一个可能的 inode。XFS inumber 是分段的，因此游标需要标记为已访问整个键空间，直到刚好在下一个 AG 的 inode 键空间开头之前。
解锁 AGI 并返回到步骤 1，如果文件系统中存在未检查的 AG。
如果不再有要检查的 AG，请将两个游标都设置为 inumber 键空间的末尾。扫描现已完成。
否则，此 AG 中至少还有一个 inode 要扫描
将检查游标提前到由 inode btree 标记为已分配的下一个 inode。
调整已访问的 inode 游标，使其指向检查游标当前所在位置之前的 inode。由于扫描器持有 AGI 缓冲区锁，因此在已访问的 inode 游标刚刚推进的 inode 键空间部分中不可能创建 inode。
获取检查游标的 inumber 的内核 inode。通过保持 AGI 缓冲区锁直到此时，扫描器知道跨整个键空间推进检查游标是安全的，并且它已稳定了下一个 inode，使其在扫描释放内核 inode 之前不会从文件系统中消失。
删除 AGI 锁并将内核 inode 返回给调用方。
在线 fsck 函数按如下方式扫描文件系统中的所有文件
通过调用 xchk_iscan_start 启动扫描。
推进扫描游标 (xchk_iscan_iter) 以获取下一个 inode。如果提供了
锁定 inode 以防止在扫描期间进行更新。
扫描 inode。
在仍然持有 inode 锁的同时，调整已访问的 inode 游标 (xchk_iscan_mark_visited) 以指向此 inode。
解锁并释放 inode。
调用 xchk_iscan_teardown 以完成扫描。
内核 inode 缓存存在一些微妙之处，这使得为调用方获取内核 inode 变得复杂。显然，绝对要求 inode 元数据足够一致，以便将其加载到 inode 缓存中。其次，如果内核 inode 处于某种中间状态，则扫描协调器必须释放 AGI 并推送主文件系统，以使 inode 返回到可加载状态。
建议的补丁是 inode 扫描器 系列。新功能的第一个用户是 在线配额检查 系列。
在常规文件系统代码中，对已分配的 XFS 内核 inode 的引用始终在事务上下文之外获取 (xfs_iget)，因为为现有文件创建内核上下文不需要元数据更新。但是，重要的是要注意，作为文件创建的一部分获得的对内核 inode 的引用必须在事务上下文中执行，因为文件系统必须确保磁盘 inode btree 索引更新和实际磁盘 inode 的初始化的原子性。
对内核 inode 的引用始终在事务上下文之外释放 (xfs_irele)，因为有一些活动可能需要磁盘更新
这些活动统称为 inode 停用。停用有两个部分——VFS 部分，它在所有脏文件页上启动写回，以及 XFS 部分，它清理特定于 XFS 的信息并在 inode 未链接时释放 inode。如果 inode 未链接（或在文件句柄操作后未连接），则内核会立即将 inode 放入停用机制中。
在正常操作期间，更新的资源获取遵循此顺序以避免死锁
Inode 引用 (iget)。
如果正在修复，则进行文件系统冻结保护 (mnt_want_write_file)。
Inode IOLOCK (VFS i_rwsem) 锁以控制文件 IO。
Inode MMAPLOCK (页缓存 invalidate_lock) 锁用于可以更新页缓存映射的操作。
日志功能启用。
事务日志空间授予。
事务的数据和实时设备上的空间。
内核 dquot 引用（如果正在修复文件）。请注意，它们没有被锁定，只是被获取了。
Inode ILOCK 用于文件元数据更新。
AG头部缓冲区锁 / 实时元数据 inode ILOCK。
如果适用，则为实时元数据缓冲区锁。
如果适用，则为 extent 映射 btree 块。
资源通常以相反的顺序释放，但这并非强制要求。然而，在线 fsck 与常规 XFS 操作不同，因为它可能会检查一个通常在锁顺序的后期阶段获取的对象，然后决定将该对象与锁顺序较早获取的对象进行交叉引用。接下来的几节详细介绍了在线 fsck 如何采取具体措施来避免死锁。
代表扫描操作执行的 inode 扫描在事务上下文中运行，并且可能已经锁定并绑定了资源。对于 iget 来说，这不是什么大问题，因为它可以在现有事务的上下文中运行，只要在常规文件系统中获取 inode 引用之前，所有绑定的资源都已获取。
当 VFS iput 函数被赋予一个没有其他引用的链接 inode 时，它通常会将该 inode 放在 LRU 列表上，希望如果另一个进程在系统内存耗尽并释放它之前重新打开该文件，则可以节省时间。文件系统调用者可以通过在 inode 上设置 DONTCACHE 标志来短路 LRU 过程，从而导致内核尝试立即将 inode 放入停用机制。
过去，停用总是从丢弃 inode 的进程完成的，这对于扫描来说是一个问题，因为扫描可能已经持有事务，而 XFS 不支持嵌套事务。另一方面，如果没有扫描事务，则最好立即丢弃其他未使用的 inode，以避免污染缓存。为了捕获这些细微差别，在线 fsck 代码有一个单独的 xchk_irele 函数来设置或清除 DONTCACHE 标志，以获得所需的释放行为。
提议的补丁集包括修复扫描 iget 用法和目录 iget 用法。
在常规文件系统代码中，VFS 和 XFS 将以众所周知的顺序获取多个 IOLOCK 锁：更新目录树时为父级 → 子级，否则按其 struct inode 对象的地址的数字顺序。对于常规文件，可以在获取 IOLOCK 后获取 MMAPLOCK 以停止页面错误。如果必须获取两个 MMAPLOCK，则按其 struct address_space 对象的地址的数字顺序获取它们。由于现有文件系统代码的结构，必须在分配事务之前获取 IOLOCK 和 MMAPLOCK。如果必须获取两个 ILOCK，则按 inumber 顺序获取它们。
在协调的 inode 扫描期间必须仔细完成 inode 锁的获取。在线 fsck 不能遵守这些约定，因为对于目录树扫描器，扫描进程持有正在扫描的文件的 IOLOCK，并且需要获取目录链接另一端文件的 IOLOCK。如果目录树已损坏，因为它包含一个循环，则 xfs_scrub 不能使用常规的 inode 锁定功能，并避免陷入 ABBA 死锁。
解决这两个问题很简单 - 任何时候在线 fsck 需要获取同一个类的第二个锁时，它都会使用 trylock 来避免 ABBA 死锁。如果 trylock 失败，则扫描会丢弃所有 inode 锁，并使用 trylock 循环来（重新）获取所有必要的资源。Trylock 循环使扫描能够检查待处理的致命信号，这就是扫描如何避免文件系统死锁或成为无响应进程的方法。但是，trylock 循环意味着在线 fsck 必须准备好在锁循环之前和之后测量正在扫描的资源，以检测变化并做出相应的反应。
以目录父指针修复代码为例。在线 fsck 必须验证目录的 dotdot dirent 指向父目录，并且父目录包含恰好一个指向子目录的 dirent。完全验证这种关系（并在可能的情况下修复它）需要在保持子目录锁定的情况下遍历文件系统上的每个目录，同时正在更新目录树。协调的 inode 扫描提供了一种遍历文件系统的方法，而不会遗漏 inode。子目录保持锁定以防止更新 dotdot dirent，但如果扫描仪无法锁定父目录，它可以丢弃并重新锁定子目录和潜在的父目录。如果目录解锁时 dotdot 条目发生更改，则移动或重命名操作必须更改了子目录的父级，并且扫描可以提前退出。
提议的补丁集是目录修复系列。
在线 fsck 函数在完整文件系统扫描期间需要的第二个支持是能够随时了解文件系统中其他线程进行的更新，因为与过去的比较在动态环境中毫无用处。两个 Linux 内核基础设施使在线 fsck 能够监视常规文件系统操作：文件系统钩子和静态键。
文件系统钩子将有关正在进行的文件系统操作的信息传递给下游使用者。在这种情况下，下游使用者始终是在线 fsck 函数。由于多个 fsck 函数可以并行运行，在线 fsck 使用 Linux 通知器调用链工具将更新分派给任何数量的感兴趣的 fsck 进程。调用链是一个动态列表，这意味着它们可以在运行时配置。由于这些钩子是 XFS 模块私有的，因此传递的信息包含检查函数更新其观察结果所需的精确内容。
当前 XFS 钩子的实现使用 SRCU 通知器链来减少对高线程工作负载的影响。常规阻塞通知器链使用 rwsem，并且对于单线程应用程序似乎具有更低的开销。但是，事实证明，阻塞链和静态键的组合是一种性能更高的组合；这里需要进行更多研究。
以下部分是在文件系统中挂钩特定点所必需的
struct xfs_hooks 对象必须嵌入到方便的位置，例如众所周知的内核文件系统对象。
每个钩子必须定义一个动作代码和一个包含有关该动作的更多上下文的结构。
钩子提供程序应在 xfs_hooks 和 xfs_hook 对象周围提供适当的包装器函数和结构，以利用类型检查来确保正确使用。
必须选择常规文件系统代码中的一个调用点，使用动作代码和数据结构调用 xfs_hooks_call。此位置应与将文件系统更新提交到事务的位置相邻（且不早于该位置）。通常，当文件系统调用钩子链时，它应该能够处理休眠，并且不应容易受到内存回收或锁定递归的影响。但是，确切的要求非常依赖于钩子调用者和被调用者的上下文。
在线 fsck 函数应定义一个用于保存扫描数据的结构，一个用于协调对扫描数据访问的锁，以及一个 struct xfs_hook 对象。扫描器函数和常规文件系统代码必须以相同的顺序获取资源；有关详细信息，请参见下一节。
在线 fsck 代码必须包含一个 C 函数来捕获钩子动作代码和数据结构。如果要更新的对象已被扫描访问过，则必须将钩子信息应用于扫描数据。
在解锁 inode 以开始扫描之前，在线 fsck 必须调用 xfs_hooks_setup 来初始化 struct xfs_hook，并调用 xfs_hooks_add 来启用钩子。
在线 fsck 必须调用 xfs_hooks_del 以在扫描完成后禁用钩子。
应将钩子的数量保持在最低限度，以降低复杂性。当在线 fsck 未运行时，静态键用于将文件系统钩子的开销降低到几乎为零。
在线 fsck 扫描代码和挂钩的文件系统代码的代码路径如下所示
other program
↓
inode lock ←────────────────────┐
↓ │
AG header lock │
↓ │
filesystem function │
↓ │
notifier call chain │ same
↓ ├─── inode
scrub hook function │ lock
↓ │
scan data mutex ←──┐ same │
↓ ├─── scan │
update scan data │ lock │
↑ │ │
scan data mutex ←──┘ │
↑ │
inode lock ←────────────────────┘
↑
scrub function
↑
inode scanner
↑
xfs_scrub
必须遵循这些规则，以确保检查代码和对文件系统进行更新的代码之间的正确交互
在调用通知器调用链之前，被挂钩的文件系统函数必须获取扫描扫描函数用于扫描 inode 的同一锁。
扫描函数和扫描钩子函数必须通过获取扫描数据的锁来协调对扫描数据的访问。
清理钩子函数不得将实时更新信息添加到扫描观测结果中，除非被更新的 inode 已经被扫描过。扫描协调器为此提供了一个辅助谓词（xchk_iscan_want_live_update）。
清理钩子函数不得更改调用者的状态，包括其正在运行的事务。它们不得获取任何可能与被钩住的文件系统函数冲突的资源。
钩子函数可以中止 inode 扫描，以避免违反其他规则。
inode 扫描 API 非常简单。
xchk_iscan_start 启动扫描。
xchk_iscan_iter 获取扫描中下一个 inode 的引用，如果没有剩余要扫描的内容，则返回零。
xchk_iscan_want_live_update 用于确定 inode 是否已在扫描中被访问过。这对于钩子函数决定是否需要更新内存中的扫描信息至关重要。
xchk_iscan_mark_visited 用于将 inode 标记为已在扫描中被访问过。
xchk_iscan_teardown 用于完成扫描。
此功能也是 inode 扫描器 系列的一部分。
比较挂载时的配额检查代码与在线修复配额检查代码是很有用的。挂载时配额检查不需要处理并发操作，因此它会执行以下操作：
确保磁盘上的 dquot 状态良好，所有核心 dquot 都将实际加载，并清零磁盘缓冲区中的资源使用计数器。
遍历文件系统中的每个 inode。将每个文件的资源使用情况添加到核心 dquot 中。
遍历每个核心 dquot。如果核心 dquot 没有被刷新，则将支持核心 dquot 的磁盘缓冲区添加到延迟写入（delwri）列表。
将缓冲区列表写入磁盘。
像大多数在线 fsck 函数一样，在线配额检查在新的收集元数据反映所有文件系统状态之前，无法写入常规文件系统对象。因此，在线配额检查将文件资源使用情况记录到使用稀疏 xfarray 实现的影子 dquot 索引中，并且只有在扫描完成后才写入实际 dquot。处理事务更新比较棘手，因为配额资源使用更新是分阶段处理的，以尽量减少 dquot 上的争用。
所涉及的 inode 被加入并锁定到事务中。
对于附加到文件的每个 dquot
dquot 被锁定。
配额预留被添加到 dquot 的资源使用中。预留记录在事务中。
dquot 被解锁。
实际配额使用情况的变化在事务中被跟踪。
在事务提交时，将再次检查每个 dquot。
dquot 再次被锁定。
配额使用情况的变化被记录下来，未使用的预留被返回给 dquot。
dquot 被解锁。
对于在线配额检查，钩子被放置在步骤 2 和 4 中。步骤 2 的钩子创建一个事务 dquot 上下文（dqtrx）的影子版本，其操作方式与常规代码类似。步骤 4 的钩子将影子 dqtrx 的更改提交到影子 dquot。请注意，两个钩子都是在 inode 被锁定的情况下调用的，这就是实时更新与 inode 扫描器协调的方式。
配额检查扫描如下所示：
设置协调的 inode 扫描。
对于 inode 扫描迭代器返回的每个 inode
获取并锁定 inode。
确定 inode 的资源使用情况（数据块、inode 计数、实时块），并将其添加到与 inode 关联的用户、组和项目 id 的影子 dquot 中。
解锁并释放 inode。
对于系统中的每个 dquot
获取并锁定 dquot。
根据扫描创建并由实时钩子更新的影子 dquot 检查 dquot。
实时更新是能够遍历每个配额记录而无需长时间持有任何锁的关键。如果需要修复，则会锁定实际 dquot 和影子 dquot，并且它们的资源计数会设置为影子 dquot 中的值。
提议的补丁集是 在线配额检查 系列。
文件链接计数检查也使用实时更新钩子。协调的 inode 扫描器用于访问文件系统上的所有目录，并且每个文件的链接计数记录存储在由 inode 编号索引的稀疏 xfarray 中。在扫描阶段，目录中的每个条目都会生成如下的观测数据：
如果该条目是根目录的点点（'..'）条目，则该目录的父链接计数会增加，因为根目录的点点条目是自引用的。
如果该条目是子目录的点点条目，则父目录的反向引用计数会增加。
如果该条目既不是点也不是点点条目，则目标文件的父计数会增加。
如果目标是子目录，则父目录的子链接计数会增加。
关于链接计数 inode 扫描器如何与实时更新钩子交互，一个关键的理解点是，扫描光标跟踪哪些 *父* 目录已被扫描。换句话说，当 A 没有被扫描时，即使 B 已经被扫描，实时更新也会忽略任何关于 A → B 的更新。此外，一个具有指向 B 的点点条目的子目录 A 在 A 的影子数据中被计为反向引用计数器，因为子点点条目会影响父目录的链接计数。实时更新钩子被仔细地放置在文件系统中所有创建、更改或删除目录条目的部分中，因为这些操作涉及 bumplink 和 droplink。
对于任何文件，正确的链接计数是父目录的数量加上子目录的数量。非目录永远没有任何类型的子目录。反向引用信息用于检测指向子目录的链接数量和指向后方的点点条目数量的不一致之处。
扫描完成后，可以通过锁定 inode 和影子数据并比较链接计数来检查每个文件的链接计数。第二个协调的 inode 扫描光标用于比较。实时更新是能够遍历每个 inode 而无需在 inode 之间持有任何锁的关键。如果需要修复，则会将 inode 的链接计数设置为影子信息中的值。如果没有找到父目录，则必须将该文件 重新指定父目录 到孤立目录，以防止该文件永远丢失。
提议的补丁集是 文件链接计数修复 系列。
大多数修复函数遵循相同的模式：锁定文件系统资源，遍历幸存的磁盘元数据以查找替换元数据记录，并使用 内存数组 来存储收集的观测结果。这种方法的主要优点是修复代码的简单性和模块化 - 代码和数据完全包含在清理模块中，不需要主文件系统中的钩子，并且通常在内存使用方面效率最高。这种修复方法的第二个优点是原子性 - 一旦内核决定某个结构已损坏，在内核完成修复和重新验证元数据之前，其他线程都无法访问该元数据。
对于在文件系统分片内进行的修复，这些优点胜过在修复分片部分时锁定分片所固有的延迟。不幸的是，反向映射 btree 的修复不能使用“标准”btree 修复策略，因为它必须扫描文件系统中每个文件的每个分支的每个空间映射，并且文件系统不能停止。因此，rmap 修复放弃了清理和修复之间的原子性。它结合了 协调的 inode 扫描器、实时更新钩子 和 内存中的 rmap btree 来完成反向映射记录的扫描。
设置一个 xfbtree 来暂存 rmap 记录。
在持有在清理期间获取的 AGI 和 AGF 缓冲区上的锁时，为所有 AG 元数据生成反向映射：inode、btree、CoW 暂存区和内部日志。
设置 inode 扫描器。
挂接到正在修复的 AG 的 rmap 更新中，以便实时扫描数据可以在文件扫描期间接收来自文件系统其余部分的 rmap btree 更新。
对于在扫描的每个文件的任一分支中找到的每个空间映射，确定该映射是否与感兴趣的 AG 匹配。如果匹配，则
为内存中的 btree 创建一个 btree 光标。
使用 rmap 代码将记录添加到内存中的 btree。
使用 特殊提交函数 将 xfbtree 的更改写入 xfile。
对于通过钩子接收到的每个实时更新，请确定所有者是否已被扫描。如果是，则将实时更新应用到扫描数据中。
为内存中的 btree 创建一个 btree 光标。
将操作回放到内存中的 btree 中。
使用 特殊的提交函数 将 xfbtree 的更改写入 xfile。 这是通过一个空事务执行的，以避免更改调用者的状态。
当 inode 扫描完成时，创建一个新的 scrub 事务并重新锁定两个 AG 头。
像所有其他 btree 重建函数一样，使用影子 btree 中的 rmap 记录数来计算新的 btree 几何结构。
分配上一步中计算出的块数。
执行通常的 btree 批量加载并提交以安装新的 rmap btree。
按照关于如何在 rmap btree 修复后回收的案例研究中讨论的那样，回收旧的 rmap btree 块。
现在释放不再需要的 xfbtree。
提议的补丁集是 rmap 修复 系列。
XFS 在文件 fork 中存储大量元数据：目录、扩展属性、符号链接目标、实时卷的可用空间位图和摘要信息，以及配额记录。文件 fork 将 64 位逻辑文件 fork 空间范围映射到物理存储空间范围，类似于内存管理单元将 64 位虚拟地址映射到物理内存地址的方式。因此，基于文件的树结构（例如目录和扩展属性）使用映射在文件 fork 偏移地址空间中的块，这些块指向映射在同一地址空间内的其他块，而基于文件的线性结构（例如位图和配额记录）则在文件 fork 偏移地址空间中计算数组元素偏移量。
由于文件 fork 可以消耗与整个文件系统一样多的空间，因此即使有分页方案可用，也不能在内存中暂存修复。因此，基于文件的元数据的在线修复会在 XFS 文件系统中创建一个临时文件，将新结构以正确的偏移量写入临时文件，并原子地交换所有文件 fork 映射（以及因此的 fork 内容）以提交修复。修复完成后，可以根据需要回收旧的 fork；如果系统在回收期间关闭，则 iunlink 代码将在日志恢复期间删除块。
注意：文件系统中的所有空间使用情况和 inode 索引必须一致才能安全地使用临时文件！此依赖关系是在线修复只能使用可分页的内核内存来暂存磁盘空间使用信息的原因。
使用临时文件交换元数据文件映射要求块头的 owner 字段与正在修复的文件匹配，而不是与临时文件匹配。目录、扩展属性和符号链接函数都已修改，以允许调用者显式指定所有者编号。
回收过程有一个缺点 -- 如果系统在回收阶段崩溃，并且 fork 范围是交叉链接的，则 iunlink 处理将失败，因为释放空间会发现额外的反向映射并中止。
为修复创建的临时文件类似于用户空间创建的 O_TMPFILE 文件。它们未链接到目录，当对文件的最后一个引用丢失时，将回收整个文件。关键的区别在于，这些文件在内核外部绝对不能有访问权限，必须特别标记以防止通过句柄打开它们，并且永远不能链接到目录树中。
历史旁注: |
在文件元数据修复的初始迭代中，将扫描损坏的元数据块以查找可恢复的数据；将回收文件 fork 中的范围；然后在原位置构建一个新结构。此策略未能通过本文档前面表达的原子修复要求的引入而幸存下来。
第二次迭代探索了从可恢复数据在 fork 中较高的偏移量处构建第二个结构，回收旧范围，并使用 COLLAPSE_RANGE 操作将新范围滑动到位。
这有很多缺点
数组结构是线性寻址的，并且常规文件系统代码库没有线性偏移的概念，该偏移量可以应用于记录偏移计算以构建备用副本。 扩展属性允许使用整个属性 fork 偏移地址空间。 即使修复可以在 fork 地址空间的不同部分中构建数据结构的备用副本，原子修复提交要求也意味着在线修复必须能够执行日志辅助的 COLLAPSE_RANGE 操作，以确保完全替换旧结构。 在构造辅助树之后但在范围折叠之前的崩溃会在文件 fork 中留下无法访问的块。这可能会进一步混淆事情。 修复后回收块不是一个简单的操作，并且在日志恢复期间从重新启动的范围折叠操作中启动回收操作是令人生畏的。 目录条目块和配额记录在每个块的头部区域中记录文件 fork 偏移量。原子范围折叠操作将不得不重写每个块头部的这部分。重写块头中的单个字段不是一个大问题，但是需要注意。 目录或扩展属性 btree 索引中的每个块都包含兄弟和子块指针。如果原子提交使用范围折叠操作，则必须非常仔细地重写每个块以保留图形结构。将其作为范围折叠的一部分意味着重复重写大量块，这不利于快速修复。
这导致了临时文件暂存的引入。
|
在线修复代码应使用 xrep_tempfile_create 函数在文件系统内创建一个临时文件。这会分配一个 inode，将内核中的 inode 标记为私有，并将其附加到 scrub 上下文。这些文件对用户空间隐藏，不能添加到目录树中，并且必须保持私有。
临时文件仅使用两个 inode 锁：IOLOCK 和 ILOCK。此处不需要 MMAPLOCK，因为数据 fork 块不能来自用户空间的分页错误。这两个锁的使用模式与任何其他 XFS 文件相同 -- 对文件数据的访问通过 IOLOCK 控制，而对文件元数据的访问通过 ILOCK 控制。提供了锁定辅助程序，以便可以通过 scrub 上下文清理临时文件及其锁定状态。为了符合 inode 锁定部分中规定的嵌套锁定策略，建议 scrub 函数使用 xrep_tempfile_ilock*_nowait 锁定辅助程序。
可以通过两种方式将数据写入临时文件
xrep_tempfile_copyin 可用于从 xfile 设置常规临时文件的内容。
可以使用常规目录、符号链接和扩展属性函数写入临时文件。
一旦在临时文件中构造了数据文件的良好副本，就必须将其传递给正在修复的文件，这是下一节的主题。
提议的补丁在 修复临时文件 系列中。
一旦修复程序构建了一个临时文件并将新数据结构写入其中，它必须将新更改提交到现有文件中。不可能交换两个文件的 inode 号，因此必须用新的元数据替换旧的元数据。这表明需要交换范围的能力，但是文件碎片整理工具 xfs_fsr 使用的现有范围交换代码不足以进行在线修复，因为
当启用反向映射 btree 时，交换代码必须使反向映射信息与每次映射交换保持最新。因此，它每个事务只能交换一个映射，并且每个事务都是独立的。
反向映射对于在线 fsck 的操作至关重要，因此旧的碎片整理代码（在单个操作中交换整个范围 fork）在此处无用。
假设碎片整理发生在两个内容相同的文件之间。对于此用例，即使操作中断，不完整的交换也不会导致用户可见的文件内容更改。
在线修复需要交换两个在定义上不相同的文件内容。对于目录和 xattr 修复，用户可见的内容可能相同，但单个块的内容可能非常不同。
文件中的旧块可能与其他结构交叉链接，如果系统在修复过程中崩溃，则不得重新出现。
这些问题通过创建一个新的延迟操作和一种新的日志意图项来跟踪交换两个文件范围的操作的进度来解决。新的交换操作类型链接在一起反向映射范围交换代码使用的相同事务，但在日志中记录中间进度，以便可以在崩溃后重新启动操作。此新功能称为文件内容交换 (xfs_exchrange) 代码。底层实现交换文件 fork 映射 (xfs_exchmaps)。新的日志项记录交换的进度，以确保一旦开始交换，它将始终运行完成，即使存在中断。超级块中的新的 XFS_SB_FEAT_INCOMPAT_EXCHRANGE 不兼容功能标志可防止旧内核上重放这些新的日志项记录。
提议的补丁集是 文件内容交换 系列。
侧栏：使用日志不兼容功能标志 |
从 XFS v5 开始，超级块包含一个 sb_features_log_incompat 字段，以指示日志包含并非所有可以挂载此文件系统的内核都能读取的记录。简而言之，日志不兼容功能可保护日志内容免受不了解内容的内核的侵害。与其他超级块功能位不同，日志不兼容位是临时的，因为空的（干净的）日志不需要保护。日志在将其内容提交到文件系统后（作为卸载的一部分或因为系统处于空闲状态）会自行清理。因为上层代码可能在日志清理自身的同时正在处理事务，所以上层代码有必要在它将要使用日志不兼容功能时通知日志。
日志坐标通过为每个特性使用一个 struct rw_semaphore 来访问不兼容的特性。日志清理代码尝试以独占模式获取此 rwsem 以清除该位；如果锁定尝试失败，则该特性位将保持设置状态。支持日志不兼容特性的代码应创建包装函数来获取日志特性，并调用 xfs_add_incompat_log_feature 以设置主超级块中的特性位。超级块更新是事务性执行的，因此必须在创建使用该功能的事务之前调用获取日志协助的包装器。对于文件操作，此步骤必须在获取 IOLOCK 和 MMAPLOCK 之后，但在分配事务之前发生。当事务完成时，将调用 xlog_drop_incompat_feat 函数来释放该特性。只有当日志变为干净时，才会从超级块中清除该特性位。
日志辅助的扩展属性更新和文件内容交换都使用日志不兼容特性，并提供围绕该功能的便捷包装器。
|
在文件分支之间交换内容是一项复杂的任务。目标是交换两个文件分支偏移范围之间的所有文件分支映射。每个分支中可能存在许多范围映射，并且映射的边缘不一定对齐。此外，在交换后可能还需要进行其他更新，例如交换文件大小、inode 标志或将分支数据转换为本地格式。这大致是新的延迟交换映射工作项的格式
struct xfs_exchmaps_intent {
/* Inodes participating in the operation. */
struct xfs_inode *xmi_ip1;
struct xfs_inode *xmi_ip2;
/* File offset range information. */
xfs_fileoff_t xmi_startoff1;
xfs_fileoff_t xmi_startoff2;
xfs_filblks_t xmi_blockcount;
/* Set these file sizes after the operation, unless negative. */
xfs_fsize_t xmi_isize1;
xfs_fsize_t xmi_isize2;
/* XFS_EXCHMAPS_* log operation flags */
uint64_t xmi_flags;
};
新的日志意图项包含足够的信息来跟踪两个逻辑分支偏移范围：(inode1, startoff1, blockcount) 和 (inode2, startoff2, blockcount)。交换操作的每个步骤都会将一个文件中尽可能大的文件范围映射交换到另一个文件。在交换操作的每个步骤之后，两个 startoff 字段都会递增，并且 blockcount 字段会递减以反映所取得的进展。标志字段捕获行为参数，例如交换 attr 分支映射而不是数据分支，以及在交换后要完成的其他工作。如果文件数据分支是操作的目标，则两个 isize 字段用于在操作结束时交换文件大小。
当启动交换时，操作顺序如下
为文件映射交换创建一个延迟工作项。在开始时，它应包含要交换的整个文件块范围。
调用 xfs_defer_finish 来处理交换。这封装在 xrep_tempexch_contents 中，用于清理操作。这将为延迟的映射交换工作项记录一个范围交换意图项到事务中。
直到延迟的映射交换工作项的 xmi_blockcount 为零，
分别读取以 xmi_startoff1 和 xmi_startoff2 开头的两个文件范围的块映射，并计算可以在单个步骤中交换的最长范围。这是映射中两个 br_blockcount 的最小值。继续遍历文件分支，直到至少一个映射包含已写入的块。不交换相互的空洞、未写入的范围和指向同一物理空间的范围映射。
在接下来的几个步骤中，本文档将把来自文件 1 的映射称为“map1”，将来自文件 2 的映射称为“map2”。
创建一个延迟块映射更新，以从文件 1 中取消映射 map1。
创建一个延迟块映射更新，以从文件 2 中取消映射 map2。
创建一个延迟块映射更新，以将 map1 映射到文件 2 中。
创建一个延迟块映射更新，以将 map2 映射到文件 1 中。
记录两个文件的块、配额和范围计数更新。
如有必要，扩展任一文件的磁盘大小。
为在步骤 3 开始时读取的映射交换意图日志项记录一个映射交换完成日志项。
计算刚刚覆盖的文件范围量。此数量为 (map1.br_startoff + map1.br_blockcount - xmi_startoff1)，因为步骤 3a 可能跳过了空洞。
将 xmi_startoff1 和 xmi_startoff2 的起始偏移量增加上一步计算的块数，并将 xmi_blockcount 减去相同的数量。这会推进游标。
记录一个新的映射交换意图日志项，反映工作项的推进状态。
返回适当的错误代码 (EAGAIN) 给延迟操作管理器，以通知它还有更多工作要做。操作管理器在返回到步骤 3 的开始之前，在步骤 3b-3e 中完成延迟的工作。
执行任何后处理。这将在后续章节中更详细地讨论。
如果文件系统在操作过程中崩溃，日志恢复会找到最近未完成的映射交换日志意图项，并从那里重新启动。这就是原子文件映射交换如何保证外部观察者要么看到旧的损坏结构，要么看到新的结构，而永远不会看到两者的混合。
在启动原子文件映射交换操作之前，需要处理一些事情。首先，常规文件需要在操作开始之前将页面缓存刷新到磁盘，并使直接写入静止。像任何文件系统操作一样，文件映射交换必须确定可以代表操作中两个文件消耗的最大磁盘空间和配额，并保留该数量的资源，以避免在开始弄脏元数据后发生不可恢复的空间不足错误。准备步骤会扫描两个文件的范围以估计
对精确估计的需求增加了交换操作的运行时间，但对于保持正确的核算非常重要。文件系统绝不能完全耗尽可用空间，并且映射交换永远不能向分支添加比其可以支持的更多的范围映射。常规用户需要遵守配额限制，尽管元数据修复可能会超过配额以解决其他位置的不一致元数据。
扩展属性、符号链接和目录可以将分支格式设置为“本地”，并将分支视为用于数据存储的文字区域。元数据修复必须采取额外的步骤来支持这些情况
如果两个分支都采用本地格式并且分支区域足够大，则通过复制内存中的分支内容、记录两个分支并提交来执行交换。原子文件映射交换机制不是必需的，因为这可以使用单个事务来完成。
如果两个分支都映射块，则使用常规原子文件映射交换。
否则，只有一个分支采用本地格式。本地格式分支的内容将转换为块以执行交换。转换为块格式必须在记录初始映射交换意图日志项的同一事务中完成。常规原子映射交换用于交换元数据文件映射。在交换操作上设置特殊标志，以便可以再次回滚事务以将第二个文件的分支转换回本地格式，以便第二个文件在 ILOCK 被删除后立即准备好。
扩展属性和目录将所有者 inode 盖印到每个块中，但缓冲区验证器实际上不检查 inode 号！尽管没有验证，但保持引用完整性仍然很重要，因此在执行映射交换之前，在线修复会使用正在修复的文件所有者字段构建新数据结构中的每个块。
在成功的交换操作之后，修复操作必须通过标准 文件范围收割 机制（在修复后完成）处理每个分支映射来收割旧的分支块。如果文件系统在修复的收割部分期间崩溃，恢复结束时的 iunlink 处理将释放临时文件和未收割的任何块。但是，此 iunlink 处理省略了在线修复的交叉链接检测，并且并非完全万无一失。
要修复元数据文件，在线修复的步骤如下
创建临时修复文件。
使用暂存数据将新内容写入临时修复文件。必须写入正在修复的同一分支。
提交清理事务，因为必须在进行事务预留之前完成交换资源估计步骤。
调用 xrep_tempexch_trans_alloc 来分配一个新的 scrub 事务，并进行适当的资源预留、锁定，以及填写一个 struct xfs_exchmaps_req 结构体，其中包含交换操作的详细信息。
调用 xrep_tempexch_contents 来交换内容。
提交事务以完成修复。
在 XFS 文件系统的“实时”部分，空闲空间通过位图进行跟踪，类似于 Unix FFS。位图中的每一位代表一个实时区段，其大小为文件系统块大小的倍数，介于 4KiB 和 1GiB 之间。实时汇总文件将给定大小的空闲区段的数量索引到实时空闲空间位图中这些空闲区段开始的块的偏移量。换句话说，汇总文件帮助分配器按长度查找空闲区段，类似于计数（cntbt）B 树对数据部分所做的事情。
汇总文件本身是一个平面文件（没有块头或校验和！），分为 log2(总 rt 区段数) 个部分，包含足够的 32 位计数器，以匹配 rt 位图中的块数。每个计数器记录从该位图块开始且可以满足 2 的幂分配请求的空闲区段的数量。
要对照位图检查汇总文件
获取实时位图和汇总文件的 ILOCK。
对于位图中记录的每个空闲空间区段
计算汇总文件中包含表示此空闲区段的计数器的位置。
从 xfile 读取计数器。
将其递增，然后写回 xfile。
将 xfile 的内容与磁盘上的文件进行比较。
要修复汇总文件，请将 xfile 内容写入临时文件，并使用原子映射交换来提交新内容。然后清理临时文件。
提议的补丁集是 实时汇总修复 系列。
在 XFS 中，扩展属性实现为命名空间中的名称-值存储。值的大小限制为 64KiB，但名称的数量没有限制。属性 fork 是未分区的，这意味着属性结构的根始终在逻辑块零中，但属性叶块、dabtree 索引块和远程值块是混合在一起的。属性叶块包含可变大小的记录，这些记录将用户提供的名称与用户提供的值相关联。大于一个块的值会分配单独的区段并写入那里。如果叶信息扩展超过单个块，则会创建一个目录/属性 btree (dabtree) 来将属性名称的哈希值映射到条目，以进行快速查找。
挽救扩展属性按如下方式进行：
遍历正在修复的文件的 attr fork 映射以查找属性叶块。当找到一个时，
遍历 attr 叶块以查找候选键。当找到一个时，
检查名称是否存在问题，如果有则忽略该名称。
检索值。如果成功，则将名称和值添加到暂存的 xfarray 和 xfblob。
如果 xfarray 和 xfblob 的内存使用量超过一定数量的内存，或者没有更多 attr fork 块要检查，则解锁文件并将暂存的扩展属性添加到临时文件。
使用原子文件映射交换来交换新的和旧的扩展属性结构。旧的属性块现在附加到临时文件。
清理临时文件。
提议的补丁集是 扩展属性修复 系列。
使用当前可用的文件系统功能很难修复目录，因为目录条目不是冗余的。离线修复工具会扫描所有 inode 以查找链接计数不为零的文件，然后扫描所有目录以建立这些链接文件的父关系。损坏的文件和目录会被清除，没有父文件的文件会被移动到 /lost+found 目录。它不会尝试挽救任何东西。
在线修复目前能做的最好的事情是读取目录数据块并挽救任何看起来合理的 dirent，更正链接计数，并将孤立项移回目录树。文件链接计数 fsck 代码负责修复链接计数并将孤立项移动到 /lost+found 目录。
与扩展属性不同，目录块的大小都相同，因此挽救目录很简单。
查找目录的父目录。如果点点条目不是不可读的，请尝试确认所谓的父目录有一个指向正在修复的目录的子条目。否则，遍历文件系统以查找它。
遍历目录数据 fork 的第一个分区，以查找目录条目数据块。当找到一个时，
遍历目录数据块以查找候选条目。当找到一个条目时，
检查名称是否存在问题，如果有则忽略该名称。
检索 inode 号并获取 inode。如果成功，则将名称、inode 号和文件类型添加到暂存的 xfarray 和 xblob。
如果 xfarray 和 xfblob 的内存使用量超过一定数量的内存，或者没有更多目录数据块要检查，则解锁目录并将暂存的 dirent 添加到临时目录。截断暂存文件。
使用原子文件映射交换来交换新的和旧的目录结构。旧的目录块现在附加到临时文件。
清理临时文件。
未来工作问题：在重建目录时，修复是否应该重新验证 dentry 缓存？
答案：是的，应该。
理论上，有必要扫描目录的所有 dentry 缓存条目，以确保以下情况之一适用：
缓存的 dentry 反映了新目录中的磁盘 dirent。
缓存的 dentry 在新目录中不再具有相应的磁盘 dirent，并且 dentry 可以从缓存中清除。
缓存的 dentry 不再具有磁盘 dirent，但 dentry 无法清除。这是问题所在。
不幸的是，当前的 dentry 缓存设计没有提供一种遍历特定目录的每个子 dentry 的方法，这使它成为一个难题。没有已知的解决方案。
提议的补丁集是目录修复系列。
父指针是一段文件元数据，使用户无需从根目录遍历目录树即可找到文件的父目录。如果没有它们，目录树的重建会受到阻碍，就像历史上缺乏反向空间映射信息曾经阻碍文件系统空间元数据的重建一样。然而，父指针功能使得完全目录重建成为可能。
XFS 父指针包含标识父目录中相应目录条目所需的信息。换句话说，子文件使用扩展属性来存储指向父目录的指针，形式为 (dirent_name) → (parent_inum, parent_gen)。可以加强目录检查过程，以确保每个 dirent 的目标也包含一个指向该 dirent 的父指针。同样，可以通过确保每个父指针的目标都是一个目录并且它包含一个与父指针匹配的 dirent 来检查每个父指针。在线和离线修复都可以使用此策略。
历史旁注: |
SGI 十多年前首次提出目录父指针作为 XFS 功能。从父目录到子文件的每个链接都镜像在子文件中的扩展属性中，该属性可用于标识父目录。不幸的是，这种早期实现存在重大缺陷，并且从未合并到 Linux XFS 中。
2000 年代后期的 XFS 代码库没有基础设施来强制目录树中的强引用完整性。它不保证前向链接的更改始终会跟进对反向链接的相应更改。 引用完整性没有集成到离线修复中。在已挂载的文件系统上执行检查和修复，而没有采取任何内核或 inode 锁来协调访问。目前还不清楚这是如何正常工作的。 扩展属性没有记录父目录中目录条目的名称，因此 SGI 父指针实现不能用于重新连接目录树。 扩展属性 fork 仅支持 65,536 个区段，这意味着父指针属性创建很可能在达到最大文件链接计数之前失败。
最初的父指针设计对于依赖于文件系统修复之类的东西来说太不稳定了。Allison Henderson、Chandan Babu 和 Catherine Hoang 正在进行第二次实现，以解决第一次实现的所有缺点。2022 年，Allison 引入了日志意图项来跟踪扩展属性结构的物理操作。这通过使在同一事务中提交 dirent 更新和父指针更新成为可能来解决引用完整性问题。Chandan 增加了数据和属性 fork 的最大区段计数，从而确保扩展属性结构可以增长以处理任何文件的最大硬链接计数。
对于第二次尝试，最初提出的磁盘上父指针格式为 (parent_inum, parent_gen, dirent_pos) → (dirent_name)。在开发过程中更改了格式，以消除修复工具在重建目录时需要确保 dirent_pos 字段始终匹配的要求。
还有其他几种方法可以解决这个问题
该字段可以被指定为建议性的，因为其他三个值足以在父目录中找到条目。然而，这使得在修复进行时不可能进行索引键查找。 我们可以允许在指定的偏移量创建目录条目，这解决了引用完整性问题，但存在由于与目录中的空闲空间冲突而导致目录条目创建失败的风险。
这些冲突可以通过追加目录条目并修改 xattr 代码以支持更新 xattr 键并重新索引 dabtree 来解决，尽管这必须在父目录仍然锁定的情况下执行。
与上述相同，但原子地删除旧的父指针条目并添加新的条目。 将磁盘上的 xattr 格式更改为 (parent_inum, name) → (parent_gen)，这将提供我们需要的属性名称唯一性，而无需修复代码更新 dirent 位置。不幸的是，这需要更改 xattr 代码以支持长度为 263 字节的属性名称。 将磁盘上的 xattr 格式更改为 (parent_inum, hash(name)) → (name, parent_gen)。如果哈希对冲突具有足够的抵抗力（例如，sha256），那么这应该提供我们需要的属性名称唯一性。长度小于 247 字节的名称可以直接存储。 将磁盘上的 xattr 格式更改为 (dirent_name) → (parent_ino, parent_gen)。此格式不需要先前建议中任何复杂的嵌套名称哈希。然而，发现具有相同文件名的同一 inode 的多个硬链接导致哈希 xattr 查找的性能问题，因此父 inode 号现在被异或到哈希索引中。
最终，决定解决方案 #6 是最紧凑和性能最高的。为父指针设计了一个新的哈希函数。
|
目录重建使用 协调 inode 扫描 和 目录条目实时更新钩子，如下所示
设置一个临时目录以生成新的目录结构，一个用于存储条目名称的 xfblob，以及一个用于存储目录更新中涉及的固定大小字段的 xfarray： (子 inode号, 添加 vs. 删除, 名称 cookie, ftype)。
设置一个 inode 扫描器并挂钩到目录条目代码以接收目录操作的更新。
对于扫描的每个文件中找到的每个父指针，确定父指针是否引用感兴趣的目录。如果是这样
分别将父指针名称和此 dirent 的 addname 条目存储在 xfblob 和 xfarray 中。
当完成扫描该文件或内核内存消耗超过阈值时，将存储的更新刷新到临时目录。
对于通过钩子接收的每个实时目录更新，确定子目录是否已被扫描。如果是这样
分别将父指针名称和此 dirent 更新的 addname 或 removename 条目存储在 xfblob 和 xfarray 中以供稍后使用。我们不能直接写入临时目录，因为不允许钩子函数修改文件系统元数据。相反，我们将更新存储在 xfarray 中，并依靠扫描器线程将存储的更新应用于临时目录。
当扫描完成时，重放 xfarray 中的任何存储的条目。
当扫描完成时，原子地交换临时目录和正在修复的目录的内容。临时目录现在包含损坏的目录结构。
回收临时目录。
建议的补丁集是 父指针目录修复 系列。
在线重建文件的父指针信息的工作方式类似于目录重建
设置一个临时文件以生成新的扩展属性结构，一个用于存储父指针名称的 xfblob，以及一个用于存储父指针更新中涉及的固定大小字段的 xfarray： (父 inode号, 父代数, 添加 vs. 删除, 名称 cookie)。
设置一个 inode 扫描器并挂钩到目录条目代码以接收目录操作的更新。
对于扫描的每个目录中找到的每个目录条目，确定 dirent 是否引用感兴趣的文件。如果是这样
分别将 dirent 名称和此父指针的 addpptr 条目存储在 xfblob 和 xfarray 中。
当完成扫描目录或内核内存消耗超过阈值时，将存储的更新刷新到临时文件。
对于通过钩子接收的每个实时目录更新，确定父目录是否已被扫描。如果是这样
分别将 dirent 名称和此 dirent 更新的 addpptr 或 removepptr 条目存储在 xfblob 和 xfarray 中以供稍后使用。我们不能将父指针直接写入临时文件，因为不允许钩子函数修改文件系统元数据。相反，我们将更新存储在 xfarray 中，并依靠扫描器线程将存储的父指针更新应用于临时文件。
当扫描完成时，重放 xfarray 中的任何存储的条目。
将所有非父指针扩展属性复制到临时文件。
当扫描完成时，原子地交换临时文件的属性分支和正在修复的文件的属性分支的映射。临时文件现在包含损坏的扩展属性结构。
清理临时文件。
建议的补丁集是 父指针修复 系列。
离线修复中检查父指针的工作方式不同，因为损坏的文件在执行目录树连接性检查之前很久就被擦除了。因此，父指针检查是添加到现有连接性检查的第二遍
在确定了幸存文件集（阶段 6）后，遍历文件系统中每个 AG 的幸存目录。这已经作为连接性检查的一部分执行。
对于找到的每个目录条目，
如果该名称已经存储在 xfblob 中，则使用该 cookie 并跳过下一步。
否则，将名称记录在 xfblob 中，并记住 xfblob cookie。唯一映射对于以下方面至关重要
删除重复名称以减少内存使用，以及
为父指针索引创建稳定的排序键，以便下面描述的父指针验证可以工作。
在每个 AG 的内存 slab 中存储 (child_ag_inum, parent_inum, parent_gen, name_hash, name_len, name_cookie) 元组。本节中引用的 name_hash 是常规目录条目名称哈希，而不是用于父指针 xattr 的专用哈希。
对于文件系统中的每个 AG，
按 child_ag_inum、parent_inum、name_hash 和 name_cookie 的顺序对每个 AG 的元组集进行排序。为每个 name 提供一个单独的 name_cookie 对于处理目录包含同一文件的多个硬链接（其中所有名称都哈希到相同的值）的罕见情况至关重要。
对于 AG 中的每个 inode，
扫描 inode 中的父指针。对于找到的每个父指针，
验证磁盘上的父指针。如果验证失败，则继续该文件中的下一个父指针。
如果该名称已经存储在 xfblob 中，则使用该 cookie 并跳过下一步。
将名称记录在每个文件的 xfblob 中，并记住 xfblob cookie。
在每个文件的 slab 中存储 (parent_inum, parent_gen, name_hash, name_len, name_cookie) 元组。
按 parent_inum、name_hash 和 name_cookie 的顺序对每个文件的元组进行排序。
将一个 slab 光标定位到每个 AG 元组 slab 中 inode 记录的开头。由于每个 AG 元组按子 inode 号顺序排列，因此这应该是很简单的。
将第二个 slab 光标定位到每个文件的元组 slab 的开头。
以锁定步骤迭代两个光标，比较每个光标下记录的 parent_ino、name_hash 和 name_cookie 字段
如果每个 AG 光标在键空间中的位置低于每个文件光标，则每个 AG 光标指向丢失的父指针。将父指针添加到 inode 并前进每个 AG 光标。
如果每个文件光标在键空间中的位置低于每个 AG 光标，则每个文件光标指向悬空的父指针。从 inode 中删除父指针并前进每个文件光标。
否则，两个光标都指向相同的父指针。如果需要，更新 parent_gen 组件。前进两个光标。
继续检查链接计数，就像我们今天所做的那样。
建议的补丁集是 离线父指针修复 系列。
在离线修复中从父指针重建目录将非常具有挑战性，因为 xfs_repair 当前在阶段 3 和 4 期间使用对文件系统的两次单次扫描来确定哪些文件损坏到足以被删除。此扫描必须转换为多遍扫描
扫描的第一遍会像现在一样删除损坏的 inode、分支和属性。损坏的目录会被标记但不会被删除。
下一遍记录指向在第一遍中标记为损坏的目录的父指针。如果阶段 4 也能够删除目录，则此第二遍可能必须在阶段 4 扫描重复块之后发生。
第三遍将损坏的目录重置为空的简短目录。尚未确保可用空间元数据，因此修复程序尚不能使用 libxfs 中的目录构建代码。
在第 6 阶段开始时，空间元数据已被重建。使用在步骤 2 中记录的父指针信息来重建目录项（dirent），并将它们添加到现在为空的目录中。
这段代码尚未构建。
如前所述，文件系统目录树应该是一个有向无环图结构。然而，此图中的每个节点都是一个独立的 xfs_inode 对象，具有自己的锁，这使得验证树的特性变得困难。幸运的是，非目录允许有多个父节点且不能有子节点，因此只需要扫描目录。目录通常构成文件系统中 5-10% 的文件，这大大减少了工作量。
如果可以冻结目录树，则可以通过从根目录向下运行深度（或广度）优先搜索，并为找到的每个目录标记位图，从而轻松发现循环和断开连接的区域。在遍历的任何时候，尝试设置已设置的位意味着存在循环。扫描完成后，将标记的 inode 位图与 inode 分配位图进行异或运算，可以显示断开连接的 inode。但是，在线修复的设计目标之一是避免锁定整个文件系统，除非绝对必要。目录树更新可能会在活动文件系统上扫描波前移动子树，因此位图算法无法应用。
目录父指针可以实现树结构验证的增量方法。无需使用一个线程扫描整个文件系统，多个线程可以从各个子目录向上遍历到根目录。为了使此方法有效，所有目录条目和父指针必须在内部一致，每个目录条目必须具有父指针，并且所有目录的链接计数必须正确。每个扫描线程必须能够在持有子目录的 IOLOCK 的同时获取所声称的父目录的 IOLOCK，以防止在树中移动任一目录。这是不可能的，因为 VFS 在移动子目录时不会获取子目录的 IOLOCK，因此扫描程序通过获取 ILOCK 并安装一个目录项更新钩子来检测更改，从而稳定父目录 -> 子目录的关系。
扫描过程使用目录项钩子来检测扫描数据中提到的目录的更改。扫描工作原理如下：
对于文件系统中的每个子目录，
对于该子目录的每个父指针，
为该父指针创建一个路径对象，并在路径对象的位图中标记子目录的 inode 编号。
在路径结构中记录父指针名称和 inode 编号。
如果所声称的父目录是正在清理的子目录，则该路径是一个循环。标记该路径以进行删除，并使用下一个子目录父指针重复步骤 1a。
尝试在路径对象中的位图中标记所声称的父 inode 编号。如果该位已被设置，则目录树中存在循环。将该路径标记为循环，并使用下一个子目录父指针重复步骤 1a。
加载所声称的父目录。如果所声称的父目录不是链接的目录，则中止扫描，因为父指针信息不一致。
对于此所声称的祖先目录的每个父指针，
如果在该级别没有设置父目录，则在路径对象中记录父指针名称和 inode 编号。
如果一个祖先有多个父目录，则将该路径标记为损坏。使用下一个子目录父指针重复步骤 1a。
对于在步骤 1a6a 中标识的祖先重复步骤 1a3-1a6。重复此操作，直到到达目录树根目录或找不到父目录为止。
如果遍历在根目录处终止，则将该路径标记为正常。
如果遍历在未到达根目录的情况下终止，则将该路径标记为断开连接。
如果目录项更新钩子触发，则检查扫描已找到的所有路径。如果该条目与路径的一部分匹配，则标记该路径和扫描已过时。当扫描线程看到扫描已被标记为过时时，它会删除所有扫描数据并重新开始。
修复目录树的工作原理如下：
遍历目标子目录的每条路径。
损坏的路径和循环路径被视为可疑。
已标记为删除的路径被视为错误。
到达根目录的路径被视为良好。
如果子目录是根目录或链接计数为零，则删除直接父目录中的所有传入目录项。修复完成。
如果子目录只有一条路径，则将点点条目设置为父目录并退出。
如果子目录至少有一条良好路径，则删除直接父目录中的所有其他传入目录项。
如果子目录没有良好路径且有多条可疑路径，则删除直接父目录中的所有其他传入目录项。
如果子目录没有路径，则将其附加到丢失和查找目录中。
建议的补丁位于目录树修复系列中。
文件系统将文件呈现为有向的（希望是无环的）图。换句话说，是一棵树。文件系统的根目录是一个目录，目录中的每个条目都向下指向更多的子目录或非目录文件。不幸的是，目录图指针中的中断会导致图断开连接，这使得无法通过常规路径解析访问文件。
如果没有父指针，目录父指针在线清理代码可以检测到指向没有链接回子目录的父目录的点点条目，并且文件链接计数检查器可以检测到文件系统中没有被任何目录指向的文件。如果此类文件具有正的链接计数，则该文件是孤立项。
有了父指针，可以通过扫描父指针来重建目录，并且可以通过扫描目录来重建父指针。这应该会减少文件最终进入 /lost+found 的情况。
找到孤立项时，应将其重新连接到目录树。脱机 fsck 通过创建一个目录 /lost+found 来充当孤立项的收容所，并通过使用 inumber 作为名称将孤立文件链接到收容所。将文件重新父级化到收容所不会重置其任何权限或 ACL。
此过程在内核中比在用户空间中更复杂。目录和文件链接计数修复设置函数必须使用常规的 VFS 机制来创建具有所有必要安全属性和 dentry 缓存条目的孤立项目录，就像常规的目录树修改一样。
孤立文件按如下方式被收容所收养：
在清理设置函数开始时调用 xrep_orphanage_try_create 以尝试确保丢失和查找目录实际存在。这还会将孤立项目录附加到清理上下文中。
如果决定重新连接文件，则获取孤立项和要重新附加的文件的 IOLOCK。xrep_orphanage_iolock_two 函数遵循前面讨论的 inode 锁定策略。
使用 xrep_adoption_trans_alloc 来为修复事务保留资源。
调用 xrep_orphanage_compute_name 来计算孤立项中的新名称。
如果将要进行收养，则调用 xrep_adoption_reparent 将孤立文件重新父级化到丢失和查找目录中，并使 dentry 缓存失效。
调用 xrep_adoption_finish 来提交任何文件系统更新，释放孤立项 ILOCK，并清除清理事务。调用 xrep_adoption_commit 来提交更新和清理事务。
如果发生运行时错误，则调用 xrep_adoption_cancel 来释放所有资源。
建议的补丁位于孤立项收养系列中。
本节讨论用户空间程序 xfs_scrub 的关键算法和数据结构，该程序能够在内核中驱动元数据检查和修复，验证文件数据，并查找其他潜在问题。
一个 XFS 文件系统可以轻松包含数亿个 inode。鉴于 XFS 的目标是具有大型高性能存储的安装，因此最好并行清理 inode 以最大限度地减少运行时，特别是当程序是从命令行手动调用时。这需要仔细调度以尽可能保持线程负载均衡。
xfs_scrub inode 扫描器的早期迭代天真地创建了一个单独的工作队列，并为每个 AG 调度了一个单独的工作队列项。每个工作队列项都遍历 inode btree（使用 XFS_IOC_INUMBERS）以查找 inode 块，然后调用 bulkstat (XFS_IOC_BULKSTAT) 来收集足够的信息以构造文件句柄。然后将文件句柄传递给一个函数，为每个 inode 的每个元数据对象生成清理项。如果文件系统包含一个具有少量大型稀疏文件的 AG，而其余 AG 包含许多较小的文件，则此简单算法会导致阶段 3 中的线程平衡问题。inode 扫描调度函数不够精细；它应该在单个 inode 级别或为了限制内存消耗，在 inode btree 记录级别进行调度。
感谢 Dave Chinner，用户空间中的有界工作队列使 xfs_scrub 可以通过添加第二个工作队列轻松避免此问题。就像以前一样，第一个工作队列为每个 AG 播种一个工作队列项，并且它使用 INUMBERS 来查找 inode btree 块。然而，第二个工作队列配置为可以等待运行的项目数量的上限。第一个工作队列的工作线程找到的每个 inode btree 块都会排队到第二个工作队列，并且由第二个工作队列查询 BULKSTAT、创建文件句柄并将其传递给一个函数，为每个 inode 的每个元数据对象生成清理项。如果第二个工作队列太满，则工作队列添加函数会阻止第一个工作队列的工作线程，直到积压减少。这并没有完全解决平衡问题，但足以减少它，以便继续处理更紧迫的问题。
提议的补丁集是清理性能调整和 inode 扫描重新平衡系列。
在阶段 2 期间，会立即修复任何 AGI 标头或 inode btree 中报告的损坏和不一致，因为阶段 3 依赖于 inode 索引的正常运行来查找要扫描的 inode。失败的修复会重新安排到阶段 4。在任何其他空间元数据中报告的问题会推迟到阶段 4。优化机会始终会推迟到阶段 4，无论其来源如何。
在阶段 3 期间，如果在阶段 2 期间验证了所有空间元数据，则会立即修复文件中任何部分元数据中报告的损坏和不一致。无法立即修复或无法修复的修复将安排在阶段 4 进行。
在 xfs_scrub 的原始设计中，认为修复将非常少见，因此用于与内核通信的 struct xfs_scrub_metadata 对象也可以用作调度修复的主要对象。随着给定文件系统对象可能进行的优化数量最近的增加，使用单个修复项跟踪给定文件系统对象的所有符合条件的修复变得更加节省内存。每个修复项都表示一个可锁定的对象 -- AG、元数据文件、单个 inode 或一类摘要信息。
阶段 4 负责以尽可能快的方式调度大量修复工作。数据依赖关系先前概述的仍然适用，这意味着 xfs_scrub 必须在尝试执行阶段 3 调度的修复工作之前尝试完成阶段 2 调度的修复工作。修复过程如下
启动一轮修复，使用工作队列和足够的工作线程来保持 CPU 像用户期望的那样忙碌。
对于阶段 2 排队的每个修复项，
要求内核修复给定文件系统对象中修复项中列出的所有内容。
如果内核在减少此对象所需的修复数量方面取得任何进展，请记下。
如果该对象不再需要修复，则重新验证与该对象关联的所有元数据。如果重新验证成功，则删除修复项。如果不是，则将该项重新排队以进行更多修复。
如果进行了任何修复，请跳转回 1a 以重试所有阶段 2 的项。
对于阶段 3 排队的每个修复项，
要求内核修复给定文件系统对象中修复项中列出的所有内容。
如果内核在减少此对象所需的修复数量方面取得任何进展，请记下。
如果该对象不再需要修复，则重新验证与该对象关联的所有元数据。如果重新验证成功，则删除修复项。如果不是，则将该项重新排队以进行更多修复。
如果进行了任何修复，请跳转回 1c 以重试所有阶段 3 的项。
如果步骤 1 取得了任何类型的修复进展，请跳转回步骤 1 以开始另一轮修复。
如果还有剩余项需要修复，则再次串行运行它们。如果修复不成功，请发出抱怨，因为这是修复任何东西的最后机会。
在阶段 5 和 7 期间遇到的损坏和不一致会立即修复。阶段 6 报告的损坏的文件数据块无法由文件系统恢复。
提议的补丁集是修复警告改进、修复数据依赖关系和对象跟踪的重构以及修复调度改进系列。
如果 xfs_scrub 在阶段 4 结束时成功验证了文件系统元数据，则会进入阶段 5，该阶段检查文件系统中可疑的名称。这些名称包括文件系统标签、目录条目中的名称和扩展属性的名称。与大多数 Unix 文件系统一样，XFS 对名称的内容施加了最少的约束
目录条目中不允许使用斜杠和空字节。
用户空间可见的扩展属性中不允许使用空字节。
文件系统标签中不允许使用空字节。
目录条目和属性键在磁盘上显式存储名称的长度，这意味着 null 不是名称终止符。对于本节，术语“命名域”是指将名称一起呈现的任何位置 -- 目录中的所有名称或文件的所有属性。
尽管 Unix 命名约束非常宽松，但大多数现代 Linux 系统的现实情况是程序使用 Unicode 字符代码点来支持国际语言。这些程序在与 C 库接口时通常以 UTF-8 编码这些代码点，因为内核期望以 null 结尾的名称。因此，在常见情况下，在 XFS 文件系统中找到的名称实际上是 UTF-8 编码的 Unicode 数据。
为了最大限度地提高其表达能力，Unicode 标准为各种字符定义了单独的控制点，这些字符在世界各地的书写系统中呈现相似或相同。例如，“西里尔小写字母 A” U+0430 “а” 字符的呈现方式通常与“拉丁小写字母 A” U+0061 “a” 相同。
该标准还允许以多种方式构造字符 -- 通过使用定义的代码点，或者通过将一个代码点与各种组合标记组合。例如，“埃符号 U+212B “Å” 字符也可以表示为“拉丁大写字母 A” U+0041 “A”，后跟“组合环上方” U+030A “◌̊”。这两个序列的呈现方式相同。
与之前的标准一样，Unicode 还定义了各种控制字符来改变文本的呈现方式。例如，“从右到左覆盖” U+202E 字符可以欺骗某些程序将“moo\xe2\x80\xaegnp.txt”呈现为“mootxt.png”。第二类呈现问题涉及空格字符。如果在文件名中遇到“零宽度空格” U+200B 字符，则该名称的呈现方式将与不具有零宽度空格的名称相同。
如果命名域内的两个名称具有不同的字节序列但呈现方式相同，则用户可能会对此感到困惑。内核在其对高级编码方案的漠不关心的情况下，允许这样做。大多数文件系统驱动程序会保留 VFS 赋予它们的字节序列名称。
Unicode 安全机制文档的第 4 节和第 5 节详细解释了检测可混淆名称的技术。当 xfs_scrub 检测到系统上正在使用 UTF-8 编码时，它会使用 Unicode 规范化形式 NFD 以及 libicu 的可混淆名称检测组件来识别目录中或文件扩展属性中可能彼此混淆的名称。还会检查名称是否包含控制字符、非渲染字符以及双向字符的混合。所有这些潜在问题都会在阶段 5 期间报告给系统管理员。
希望本文档的读者已经理解了本文档中提出的设计，并且现在对 XFS 如何执行其元数据索引的在线重建以及文件系统用户如何与该功能进行交互有所了解。尽管这项工作的范围令人望而生畏，但希望本指南能够使代码阅读者更容易理解构建的内容、构建的对象以及原因。如有疑问，请随时联系 XFS 邮件列表。
如前所述，原子文件映射交换机制的第二个前端是一个新的 ioctl 调用，用户空间程序可以使用该调用来原子性地提交对文件的更新。这个前端已经发布审查几年了，尽管对在线修复进行必要的改进以及缺乏客户需求意味着该提案没有被大力推动。
如前所述，XFS 长期以来具有在文件之间交换范围的能力，xfs_fsr 几乎完全使用该能力来整理文件碎片。最早的形式是 fork 交换机制，通过交换每个 inode fork 立即区域中的原始字节，可以在两个文件之间交换数据 fork 的全部内容。当 XFS v5 出现并带有自描述元数据时，这个旧机制增加了一些日志支持，以在日志恢复期间继续重写 BMBT 块的所有者字段。当反向映射 btree 稍后添加到 XFS 时，维护 fork 映射与反向映射索引的一致性的唯一方法是开发一个迭代机制，该机制使用延迟的 bmap 和 rmap 操作一次交换一个映射。此机制与上面过程中的步骤 2-3 相同，只是新的跟踪项，因为原子文件映射交换机制是对现有机制的迭代，而不是全新的东西。对于文件碎片整理的狭窄情况，文件内容必须相同，因此恢复保证并没有多大好处。
原子文件内容交换比现有的 swapext 实现灵活得多，因为它可以保证调用者即使在崩溃后也永远不会看到旧内容和新内容的混合，并且它可以对两个任意的文件 fork 范围进行操作。额外的灵活性支持了几个新的用例
事务文件更新：与上述机制相同，但仅当原始文件的内容未更改时，调用者才希望发生提交。为了实现这一点，调用进程在将其数据重链接到临时文件之前，会对原始文件的文件修改和更改时间戳进行快照。当程序准备提交更改时，它会将时间戳作为参数传递给原子文件映射交换系统调用。仅当提供的时间戳与原始文件匹配时，内核才会提交更改。提供了一个新的 ioctl (XFS_IOC_COMMIT_RANGE) 来执行此操作。
模拟原子块设备写入：导出一个逻辑扇区大小与文件系统块大小匹配的块设备，以强制所有写入与文件系统块大小对齐。将所有写入暂存到临时文件，完成后，调用原子文件映射交换系统调用，并带有标志以指示应忽略临时文件中的空洞。这在软件中模拟了原子设备写入，并且可以支持任意分散的写入。
事实证明，前面提到的修复项的重构是启用矢量化清理系统调用的催化剂。自 2018 年以来，在某些系统上，进行内核调用的成本已大幅增加，以缓解推测性执行攻击的影响。这激励了程序作者尽可能少地进行系统调用，以减少执行路径跨越安全边界的次数。
使用矢量化清理，用户空间将文件系统对象的身份、要针对该对象运行的清理类型列表以及所选清理类型之间的数据依赖关系的简单表示推送到内核。内核尽可能执行调用者的计划，直到由于损坏而无法满足依赖关系为止，并告诉用户空间完成了多少工作。希望 io_uring 将拾取足够多的此功能，以便在线 fsck 可以使用它，而不是向 XFS 添加单独的矢量化清理系统调用。
相关的补丁集是内核矢量化清理和用户空间矢量化清理系列。
在线 fsck 代码的一个严重缺点是它在内核中持有资源锁的时间量基本上是无限制的。用户空间允许向该进程发送致命信号，这将导致 xfs_scrub 在到达良好的停止点时退出，但用户空间无法为内核提供时间预算。鉴于清理代码库具有检测致命信号的帮助程序，允许用户空间为清理/修复操作指定超时并在操作超出预算时中止操作应该不会花费太多工作。但是，大多数修复函数都具有一旦它们开始接触磁盘上的元数据，该操作就无法干净地取消的属性，此后 QoS 超时不再有用。
多年来，许多 XFS 用户都要求创建一个程序来清除文件系统下的物理存储的一部分，使其成为连续的可用空间块。简而言之，将此可用空间碎片整理器称为 clearspace。
clearspace 程序需要的第一个部分是从用户空间读取反向映射索引的能力。这已经以 FS_IOC_GETFSMAP ioctl 的形式存在。它需要的第二个部分是一种新的 fallocate 模式 (FALLOC_FL_MAP_FREE_SPACE)，它分配区域中的可用空间并将其映射到文件。将此文件称为“空间收集器”文件。第三部分是强制在线修复的能力。
要清除物理存储一部分中的所有元数据，clearspace 使用新的 fallocate map-freespace 调用将该区域中的任何可用空间映射到空间收集器文件。接下来，clearspace 通过 GETFSMAP 查找该区域中的所有元数据块，并对数据结构发出强制修复请求。这通常会导致元数据在未被清除的某个地方重建。在每次重新定位之后，clearspace 再次调用“映射可用空间”函数来收集正在清除的区域中任何新释放的空间。
要清除物理存储一部分中的所有文件数据，clearspace 使用 FSMAP 信息来查找相关的文件数据块。在确定了一个良好的目标后，它会对该文件的该部分使用 FICLONERANGE 调用，以尝试与虚拟文件共享物理空间。克隆范围意味着原始所有者无法覆盖内容；任何更改都将通过写时复制写入其他位置。Clearspace 在未被清除的区域中创建冻结范围的自己的副本，并使用 FIEDEUPRANGE (或原子文件内容交换功能) 将目标文件的数据范围映射从正在清除的区域移开。当所有其他映射都移动后，clearspace 将空间重链接到空间收集器文件中，使其不可用。
还有一些进一步的优化可以应用于上述算法。要清除具有高共享因子的物理存储，强烈希望保留此共享因子。实际上，这些范围应该首先移动，以在操作完成后最大化共享因子。为了使这项工作顺利进行，clearspace 需要一个新的 ioctl (FS_IOC_GETREFCOUNTS) 以向用户空间报告引用计数信息。通过公开的引用计数信息，clearspace 可以快速找到文件系统中最大、共享最多的数据范围，并首先以它们为目标。
未来工作问题：文件系统如何移动 inode 块？
答案：为了移动 inode 块，Dave Chinner 构建了一个原型程序，该程序创建了一个包含旧内容的新文件，然后以无锁方式在文件系统中运行以更新目录条目。如果文件系统崩溃，则该操作无法完成。这个问题并非完全无法克服：创建一个隐藏在跳转标签后面的 inode 重新映射表，以及一个跟踪内核遍历文件系统以更新目录条目的日志项。问题在于，内核无法对打开的文件执行任何操作，因为它无法撤销它们。
未来工作问题：可以使用静态密钥来最大限度地减少在 XFS 文件上支持 revoke() 的成本吗？
答案：是的。在第一次撤销之前，救援代码根本不需要在调用路径中。
相关的补丁集是内核可用空间碎片整理和用户空间可用空间碎片整理系列。
移除文件系统的末尾应该很简单，只需疏散文件系统末尾的数据和元数据，并将释放的空间交给收缩代码即可。这需要疏散文件系统末尾的空间，这是对可用空间碎片整理的一种运用！
