JFS 文件系统概述及布局分析2

B+ 树

这一节描述文件布局使用的 B+ 树数据结构。选择 B+ 树是为了提高读写盘区的性能，这是 JFS 必须进行的最普通操作。B+ 树为读取文件的特定盘区提供快速搜索。它还提供有效方法将盘区添加或插入文件中。较为少见的情形是：当删除文件时，JFS 需要遍历整个 B+ 树。为了保证 JFS 会删除 B+ 树使用的块以及文件数据，对于遍历 B+ 树效率也很高。

盘区分配描述符（xad 结构）描述盘区并且又添加了表示文件所需的两个字段：描述盘区表示的逻辑字节地址的偏移量和标志字段。盘区分配描述符结构在 jfs_xtree.h, struct xad 中定义。

xad 结构为：

struct xad {

unsignedflag:8;

unsignedrsvrd:16;

unsignedoff1:8;

uint32 off2;

unsignedlen:24;

unsignedaddr1:8;

uint32 addr2;

} xad_t;

其中：

flag 是包含各种标志的 8 位字段。这些标志能够表示写入时复制、是否分配了盘区但没有记录它、压缩信息等等。

rsvrd是保留供将来使用的 16 位字段。它总为零。

off1,off2 是 40 位字段，包含盘区中第一个块的逻辑偏移量。逻辑偏移量是以聚集块尺寸为单位表示；也就是说，要取得一个字节，偏移量必须乘以聚集块尺寸。

len 是 24 位字段，包含盘区的长度。长度以聚集块尺寸为单位表示。

addr1,addr2 是 40 位字段，包含盘区的地址。地址以聚集块尺寸为单位表示。

xad 结构描述了两个抽象范围：

磁盘上磁盘块的物理范围。它以聚集块号 xad_address 开始，并且延伸为 xad_length 聚集块。

文件内字节的逻辑范围。它以字节号 xad_offset * AGBS（聚集块尺寸）开始，并且延伸为 xad_length*AGBS 字节。

当然，物理范围和逻辑范围有相同长度的字节。请注意， xad_offset 以聚集块尺寸为单位存储（例如，在 xad_offset 中值 "3" 意味着 3 个聚集块，而不是 3 个字节）。它遵循文件内盘区总是以聚集块尺寸为边界。

JFS 中的所有索引对象（除目录外），有一个类属 B+ 树索引结构。索引的数据将取决于对象。B+ 树以由树描述的数据的 xad 偏移量为键。项按 xad 结构的偏移量排序。xad 结构是 B+ 树节点中的项。

磁盘 inode 第二扇区底部包含数据描述符，它描述在 inode 的后半部分内存储的内容。对于足够小的文件，后半部分可能包含内嵌数据。如果文件数据不适合 inode 的内嵌数据空间，它将包含在盘区中，inode 将包含 B+ 树的根节点。头部指出在使用的 xad 个数，可用的 xad 个数。通常，inode 将包含 8 个 xad 结构 B+ 树的根。如果文件有 8 个或更少盘区，那么这 8 个 xad 结构也是 B+ 树的叶节点。它们将描述盘区。否则，inode 中的 8 个 xad 结构将指向 B+ 树的叶节点或内部节点。

一旦 inode 中的 8 个 xad 结构均已填充，为了有更多的 xad 结构，就会尝试使用 inode 的最后四分之一。如果 INLINEEA 位在 inode 的 di_mode 字段中设置，那么 inode 的最后四分之一可用。

一旦 inode 中所有可用的 xad 结构都被使用，就必须拆分 B+ 树。JFS 将把 4K 的磁盘空间分配给 B+ 树的叶节点。叶节点逻辑上是带头的 xad 项的数组。头部指向节点中第一个空闲的 xad 项，没有分配紧跟其后的所有 xad 项。8 个 xad 项从 inode 复制到叶节点，初始化头部以指向第 9 个项作为第一个空闲项。然后 JFS 将把 B+ 树的根更新为 inode 的第一个 xad 结构；该 xad 结构将指向最新分配的叶节点。这个新的 xad 结构的偏移量是叶节点中第一个项的偏移量。将更新 inode 中的头部以表示当前 B+ 树只使用 1 个 xad。还需要更新 inode 头部以表示当前 inode 包含 B+ 树的纯根。

当把新盘区添加到文件时，将以必需的次序，继续把它们添加到相同的叶节点。这将持续直到节点填满为止。一旦节点填满了，将为 B+ 树的另一个叶节点分配新的 4K 磁盘空间。将把该 inode 的第二个 xad 结构设置成指向新分配的节点。

这将持续直到填满 inode 的所有 8 个 xad 结构为止，这时，将再次拆分 B+ 树。这种拆分将创建 B+ 树的内部 inode ，它们是纯粹用来记录树的搜索路径。JFS 将为 B+ 树的内部 inode 分配 4K 磁盘空间。内部节点看起来如同叶节点。从 inode 复制 8 个 xad 项到内部节点，初始化头部以指向第 9 个项作为第一个空闲项。然后，通过使 inode 的第一个 xad 结构指向新分配的内部节点，JFS 更新 B+ 树的根。将更新 inode 中的头部以表示当前 B+ 树只使用 1 个 xad。

文件 jfs_xtree.h 在 struct xtpage_t 中描述 B+ 树根的头部。文件 jfs_btree.h 是在 struct btpage_t 中的内部节点或叶节点的头部。

例子

下列例子进一步分析了盘区描述符和 xad 结构的用法：

连续分配的 1041377 字节文件。

相同的 1041377 字节文件，但在磁盘上拆分成三段。

1041377 字节的文件，但里面有一个"洞"（稀疏文件）。

连续分配的 16GB 文件。

在所有这些例子中，聚集块尺寸都是 1KB。

连续分配的 1041377 字节尺寸文件： 该文件需要 1017 个 1KB 聚集块，（在最后一个聚集块中，有 31 个字节丢失成为内部存储碎片）。要描述这个连续文件只需要一个 xad 结构：

flag这里不讨论

offset 0 /* the beginning of the file */

length 1017/* 1017 1KB aggregate blocks */

address xxxxx /* aggregate block # */

相同的 xad 结构能够表示任何长度为 1040385 （1016 * 1024 + 1）到 1041408 （1017 * 1024）的连续文件，因为盘区描述符只表示小于聚集块大小粒度的尺寸。只有 inode 的 di_size 字段记录字节粒度。

在 1041377 字节文件分三段： 假设相同的文件拆分成磁盘上三个不同盘区：一个为 495 个聚集块长，一个为 22，一个为 500。需要三个 xad 结构来表示该文件，每个物理盘区需要一个：

xad #0 :

flag这里不讨论

offset 0 /* the beginning of the file */

length 495 /* 495 1KB aggregate blocks */

address xxxxx /* aggregate block # */

xad #1:

flag这里不讨论

offset 495 /* the beginning of the file */

length 22 /* 22 1KB aggregate blocks */

address yyyyy /* aggregate block # */

xad #2:

flag这里不讨论

offset 517 /* the beginning of the file */

length 500 /* 500 1KB aggregate blocks */

address zzzzz /* aggregate block # */

该例中，0 号 xad 描述文件开始的 495 个物理聚集块。 xad_offset 字段包含 0，因为该 xad 描述以逻辑偏移量 0 开始的字节。第二个 xad，1 号 xad，描述文件接下来的 22 个物理聚集块。 xad_offset 字段包含 495，因为该 xad 描述以逻辑偏移量 506880 (495 * 1024) 开始的字节；前面的字节由 xad 0 描述。最后一个 xad 描述文件的最后 500 块。这里， xad_offset 字段是 517。请注意，对于非稀疏文件，给定 xad 的 xad_offset 字段等于所有以前 xad 结构长度和（在本例中，517 = 495 + 22）。如果这一关系总是成立的，那么 xad_offset 字段就是冗余的，可以消除。然而，下一个例子显示，对于稀疏文件， xad_offset 字段不是冗余的。

1041377 字节的稀疏文件： 考虑经由以下 POSIX 风格的操作而创建的文件：

fd = create ("newfile", blah blah blah);

write (fd, "hi", 2);

lseek (fd, 1041374, 0);

write (fd, " bye" , 3);

该文件有以逻辑字节偏移量 0 开始的两字节数据（"hi"），还有以逻辑字节偏移量 1,041,374 开始的三字节数据 ("bye")，并且在这两者之间全为 0（稀疏的）。文件的长度为 1041377 字节。

通常，JFS 不分配物理磁盘空间以保存从不写入文件的字节范围。因此，将占用两个 xad 结构来表示该文件：一个为包含 "hi" 数据的盘区，一个为包含 "bye" 数据的盘区：

xad #0 :

flag这里不讨论

offset 0 /* the beginning of the file */

length 1 /* 1 1KB aggregate blocks */

address xxxxx /* aggregate block # */

xad #1:

flag这里不讨论

offset 1016/* the beginning of the file */

length 1 /* 1 1KB aggregate blocks */

address yyyyy /* aggregate block*/

在该例中，第一个盘区(xad 0)包含字节 "hi"，紧接着是 1022 字节 0。最后一个盘区(xad 1)包含 990 字节 0，紧接着是 3 字节 "bye"。1KB 盘区中剩余的 31 字节不是文件的组成部分。（它们与第一个例子中丢失成为内部存储碎片的 31 个字节相同）。

请注意，该例中， xad_offset 字段是必需的；这是知道 xad 1 表示文件内在无法预料的逻辑偏移量字节序列的唯一方法（也即，xad 1 的偏移量不等于 xad 0 的偏移量加长度）。这是表示稀疏文件的方法。

inode 的 di_size 字段包含写入的最后一个字节偏移值加 1。

连续分配的 16GB 的文件： xad 结构中的长度字段仅有 24 位长：因此，它能包含的最大值是 2(24)-1。如果聚集块大小是 1KB（例如），那么一个 xad 能够表示的最大盘区是(2(24)-1)*2(10)=1KB，小于 16G。暗示这也是 xad 结构能够表示的最大盘区。因此，如果文件够大的话，就算它在磁盘上是相连的，也需要多个 xad 结构来表示它。本例中显示了这样一个连续分配的文件：一个 16G 文件，它从聚集块号 12345 开始连续分配，获取 16777216 个 1KB 的聚集块(16G)。

xad #0 :

flag这里不讨论

offset 0 /* the beginning of the file */

length 16777215/* 1 1KB aggregate blocks */

address 12345 /* aggregate block*/

xad #1:

flag这里不讨论

offset 16777215/* the beginning of the file */

length 1 /* 1 1KB aggregate blocks */

address 16789560/* aggregate block # */

在该例中，不论文件在磁盘上是否相连，要表示它至少需要两个 xad 结构，这是由于单个盘区的长度限制。