文件系统空闲区间管理

分配找大小，释放找邻居 ​

长度索引可直接寻找不小于 $r$ 的最小键，适合最佳适配。地址索引让释放者寻找左前驱与右后继，判断是否正好接壤。XFS的空闲空间管理便有按起点和按块数排序的两棵树；本页使用它们的有序查找接口，不要求先实现树的分裂与旋转。

如果索引是普通平衡搜索树，最佳适配和更新可在 $O(1+\log (m+1))$ 时间内完成，其中 $m=|F|$；空树按常数时间处理。首次适配直接扫描地址序列最坏仍为 $O(1+m)$。要把首次适配也加速，需要在子树中增加最大可用长度等摘要，不能仅凭“用了树”就宣布所有选择都是对数时间。

最佳适配希望少留下零头；首次适配希望尽早找到合格位置。每次局部选择都可能改变未来的大区间形状。以下两条不同的请求序列说明，两种政策都不能只靠名称获得总体优越性。

请求5、7：保住大段的一方成功 ​

每个实验重新从 $F=\{[1,9),[12,18)\}$ 开始，长度分别8和6，总空闲14块，其余块已保留或分配。两个请求依次为5、7，中间不释放。

首次适配第二步还有9块空闲，却分散在长度3和6的两段中。请求合同要一段连续7块，不接受把两段拼成逻辑列表。若上层允许多extent，它可以改发多个请求；那是换了请求合同，不是原来7块请求突然成功。

请求5、3、6：小零头也可能更有用 ​

重置同样的初态，这次请求5、3、6。首次适配先用 $[1,6)$，第二次恰好用完余下 $[6,9)$，第三次用完整 $[12,18)$，三次全部成功。

最佳适配先用 $[12,17)$，留下1块和8块。请求3只能切走 $[1,4)$，剩下长度5和1；最后请求6失败。初态与总请求量仍是14，改变顺序和长度就改变了谁成功。两组轨迹一起排除了“最佳适配总比首次适配少失败”及其反命题。

释放中间块时，要同时看两边 ​

另开一个释放实验：连续区间 $[1,9)$ 已交付为A=$[1,3)$、B=$[3,6)$、C=$[6,9)$，原来的 $[12,18)$ 仍空闲。先释放A和C，此时三段空闲为 $[1,3)$、$[6,9)$、$[12,18)$。

再释放B。地址前驱在3结束，与B起点相等；地址后继从6开始，与B终点相等。应从两个索引中删除这两条邻居记录，再插入合并后的 $[1,9)$，最后仍有 $[12,18)$。如果只合左边，留下 $[1,6)$ 和 $[6,9)$ 两条相邻空闲记录，就破坏了“最大区间”不变量，后续8块请求会被错误拒绝。

在长度索引中，合并前的键是 $(2,1)$ 和 $(3,6)$，合并后必须替换为 $(8,1)$。只改地址索引、忘删旧长度键，会让分配器再次交付已被大区间覆盖的旧片段，造成重复分配。两个索引一致属于正确性要求，不只是查询效率要求。

元数据也需要空间和恢复规则 ​

释放空间可能让索引增加新记录，树节点也可能需要分裂。因此“设备已经满了，但释放总会成功，因为释放不占空间”并不成立。实际系统会为元数据维护保留空间或专门的空闲列表；本页把预留元数据作为前提，避免递归地先分配空间才能记录一次释放。

本页原子操作指并发观察下不暴露半更新状态，不自动意味着掉电原子性。把双索引、所有权与文件映射持久地一起更新，可以复用文件系统重做日志理路文件系统重做日志与提交边界Filesystem redo journal · Journaling filesystem commit把文件数据、位图、inode和目录组成有界块事务，证明payload、commit、home和清日志的稳定顺序及再次崩溃恢复。；若只把其中一个索引刷盘，恢复后仍会出现两份互相矛盾的空间账。

三个数字给出不同信息 ​

总空闲量 $T=\sum _{[a,b)\in F}(b-a)$ 描述容量；最大空闲长度 $M=\underset{[a,b)\in F}{max}(b-a)$ 描述本页一次连续请求的可行性；区间数 $m$ 描述碎片形状及索引规模。空集合时约定 $M=0$。在没有额外资格、对齐和保留预算的当前模型里，请求成功当且仅当 $r\le M$，而 $r\le T$ 只是必要条件。

Extent映射理路Extent文件区间映射Extent mapping · 文件extent · 文件区段映射用逻辑起点、长度和物理起点描述文件中的连续区域，逐步计算字节寻址、孔洞、覆盖拆分与合并条件，区分表示更新与持久发布。能使用这里交付的区间，但映射连续性与空闲连续性是两个不同状态。文件删去中间一段后，物理空间是否能立即回收，还要检查快照、未完成I/O与恢复根是否仍引用它；本页只能合并已经真正交回的块。

复算终点除了写出分配地址，还应给出两套排序键、每个所有者的区间以及空闲总数。对任何失败或非法重复释放，逐项比较操作前后的状态应完全一致。这样可以区分“策略选择不理想”和“分配器把同一块给了两个人”这两种本质不同的问题。