Extent文件区间映射

压缩连续关系，保留随机定位 ​

记录 $(5,4,20)$ 表示文件块5、6、7、8依次在设备块20、21、22、23。要读文件块7，不必顺序经过5和6；在起点处做一次差值便能算到22。若文件有 $m$ 条记录，排好序的数组可用二分查找在 $O(1+\log (m+1))$ 时间内定位候选，数组插入仍可能移动 $O(m)$ 条记录；空表直接按常数时间返回无映射。

大文件可能需要树形索引。树只是帮助找到那条前驱记录，叶子记录的区间含义不变。实际ext4把文件逻辑起点、长度、物理起点放在extent叶子中，内节点负责下一层定位；文件很连续时，一条extent能替代很多逐块指针。外部碎片严重时，记录数量仍会增长，不能假定任何大文件都只有一条记录。

两边连续才有合并意义 ​

相邻记录 $({\ell }_1,n_1,p_1)$ 与 $({\ell }_2,n_2,p_2)$，只有在

且初始化、共享等属性兼容时，才可合成 $({\ell }_1,n_1+n_2,p_1)$。只满足逻辑连续，设备上可能隔着其他文件；只满足物理连续，文件中可能隔着一个应读零的洞。任意一边不连续都不能删掉这道边界。

1553号字节在哪里 ​

重置DISK-32教学快照：设备块0到31，每块256字节，文件长度 $L=11\times 256=2816$ 字节。初始extent表为 $(0,3,8)$、$(5,4,20)$。

偏移1553满足 $1553=6\times 256+17$。块6落在第二条记录中，设备块为 $20+(6-5)=21$，设备字节偏移为 $21\times 256+17=5393$。对偏移1025做同样拆分，得到逻辑块4偏移1；前驱是 $(0,3,8)$，但 $4\nless 3$，所以读取零，不能误算成设备块12。

覆盖中间两块会把一条记录拆开 ​

现在为文件块6和7取得两个新设备块12和13，并准备把它们改映射到新位置。原记录 $(5,4,20)$ 有三部分：左端文件块5继续指向20，中间两块指向12、13，右端文件块8继续指向23。新表是

一般覆盖 $[a,c)$ 与旧extent有交集时，未覆盖左片的长度是 $a-\ell$，若为正则保留 $(\ell ,a-\ell ,p)$；未覆盖右片从 $c$ 开始，若 $c<\ell +n$，则保留 $(c,\ell +n-c,p+c-\ell )$。这两个公式用于覆盖端点位于该extent内的情形；覆盖横跨多条记录时，应先对每条记录取交集，不能把负长度也插入表中。

上面的三片不能重新合并：20之后应是21，但中间实际从12开始；中间12、13之后应是14，右片却在23。映射记录变多，是这次实际物理布局的结果。洞3、4、9、10完全未动；已用设备块总数仍是7，但从21、22换成12、13。

一张正确的新表还不等于安全落盘 ​

发布前，旧表仍指向21、22。若先把它们交给另一文件覆盖，再发生崩溃恢复旧表，旧文件就会读到别人的内容。因此，新数据写入、映射发布、旧块回收必须服从已有持久化协议；本页的区间计算只决定新表应当是什么。

实际ext4还区分未初始化extent。这样的extent已经拥有物理空间，但不能因此把盘上的旧字节暴露为文件内容；读取语义仍需要按未初始化状态处理。它与“没有物理分配”的稀疏洞都可能读出零，空闲空间扣账却不同。扩大本页模型时应把这个状态写进记录，并禁止随意跨状态合并。

检查映射可以分成三张账 ​

第一张是文件语义：每个有效字节要么由恰好一个已初始化extent提供，要么属于明确的洞。第二张是物理所有权：所有引用的设备块确实归本文件使用，新旧版本过渡中尚不能回收的块也仍被保留。第三张是持久性：恢复选中的映射只能指向已经完整持久的数据。这三项可分别检查，少一项都可能造成错误。

分配连续物理区间的具体选择可见文件系统空闲区间管理理路文件系统空闲区间管理Free-space extent management · 空闲区间双索引 · First fit and best fit ranges把设备空闲块组织成最大连续区间，维护地址和长度两种索引，执行首次适配、最佳适配与左右合并，并用双向反例区分策略。。如果底层只能交付若干分散区间，文件仍可用多条extent表示；连续性关系到元数据数量和I/O形状，不是文件能否具有连续字节地址的前提。

迁移练习：把新物理起点12改成21，覆盖内容更新但布局回到原来的连续位置。新表三片此时可以合回 $(5,4,20)$。再把中间映射改为只覆盖文件块6，块7应保留原设备块22；若照抄两块覆盖的右片起点8，就会错误制造一个洞。