注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

My Unix World

不要迷恋Unix,Unix只是计算世界很小的一部分!

 
 
 

日志

 
 

JFS文件系统原理--JFS布局  

2008-11-21 13:22:05|  分类: L-FS |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
日志文件系统如何处理磁盘布局

Steve Best,Linux 技术中心,IBM
Dave Kleikamp,Linux 技术中心,IBM

本文描述磁盘日志文件系统(JFS)布局,以及使用磁盘布局结构来实现可扩展性、可靠性和性能的机制。还会了解用来操作这些结构的策略和算法,以及 JFS 是在哪里使用遍布文件系统的 B+ 树来提高文件系统操作性能。

JFS 体系结构可通过其磁盘布局特性的上下文进行说明。磁盘布局是 JFS 用来控制文件系统的格式。本文讨论盘区的文件几何构造、目录格式、块分配映射表格式、inode 和布局结构的其它特性。本文还提供了文件布局使用的 B+ 树数据结构的细节和示例。选择 B+ 树是为了提高读写盘区的性能,这是 JFS 执行的最普通操作。

分区、聚集、分配组、文件集
这里是磁盘布局的“全景图”。

分区
JFS 文件系统建立在分区上,分区是由 FDISK 导出到 JFS 的抽象。

分区有:

固定分区块尺寸,其合法值为 512、1024、2048 或 4096 字节。分区块尺寸定义了分区上支持的最小 I/O 单元。这对应于组成分区的物理设备的基本磁盘扇区大小,最普遍的尺寸是 512 字节。
大小为:PART_NBlocks,是分区磁盘块数。
分区磁盘块的抽象地址空间 [ 0.. PART_NBlocks - 1 ]。

聚集
为了支持 DCE DFS(分布式计算环境分布式文件系统),JFS 将磁盘空间分配池(称为聚集)的概念, 与可安装的文件系统子树(称为文件集)的概念分开。本文中聚集和文件集的术语与其 DFS 用法一致。每个分区刚好只有一个聚集;每个聚集可能有多个文件集。在第一个发行版中,JFS 仅支持每个聚集一个文件集;但是,所有元数据都已设计成适用于所有情况。
JFS文件系统原理--JFS布局 - liqi.xie - Liqix的程序世界
图 1 显示带有两个文件集的聚集的布局。

聚集有:

在此聚集的开始部分有 32K 保留区域。
固定的聚集块尺寸,其合法值为 512、1024、2048 或 4096 字节,但不小于分区块尺寸。聚集块尺寸定义了聚集上支持的最小空间分配单元。不要把它与分区块尺寸混淆起来,后者定义的是 I/O 的最小单元。
主聚集超级块和辅助聚集超级块。超级块包含聚集方面的信息,例如:聚集的大小、分配组的大小、聚集块的尺寸等等,辅助聚集超级块是主聚集超级块的直接副 本。如果主聚集超级块损坏,则使用辅助聚集超级块。这些超级块位于固定位置。这使得 JFS 不依赖任何其它信息,就能够找到它们。超级块结构在 jfs_superblock.h 的 struct jfs_superblock 中定义。
聚集 inode 表,包含描述聚集范围的控制结构的 inode 。聚集 inode 表逻辑上包含一个 inode 数组。聚集无目录结构;在聚集或文件集名字空间中,任何地方都没有聚集 inode 。
辅助聚集 inode 表,包含从聚集 inode 表复制的 inode 。由于对任何文件系统信息的查找而言,聚集 inode 表中的 inode 都是至关重要的,所以它们每一个在辅助聚集 inode 表中都有备份。当然,不会复制 inode 的实际数据,而只是复制可用来查找数据和 inode 本身的寻址结构。
聚集 inode 映射表,描述聚集 inode 表。聚集 inode 分配映射表包含聚集 inode 上及其磁盘位置上的分配状态信息。
辅助聚集 inode 映射表,描述辅助聚集 inode 表。由于必须复制聚集 inode 表本身,辅助聚集 inode 映射表实际上是与聚集 inode 分配映射表分开的映射结构。
块分配映射表,描述在聚集内分配和释放聚集磁盘块的控制结构。块分配映射表在聚集磁盘块内进行一对一映射。
fsck 工作区(未在图 1 中显示),它为 fsck 提供用来跟踪聚集块分配的空间。因为 JFS 支持超大聚集,所以这一区域是必需的;当 fsck 运行时,可能没有足够的内存用来跟踪内存中的这些信息。超级块描述了这一区域。每个聚集块需要一位。fsck 工作区总是存在于聚集的末端。
内嵌日志(未在图 1 中显示)为记录聚集中的元数据更改提供了空间。超级块描述了这一区域。内嵌日志总是紧跟 fsck 工作空间后。

初始情况下,在聚集创建时分配了第一个 inode 盘区。按需要动态分配和释放其它 inode 盘区。每个聚集 inode 描述聚集本身的某些方面,如下:

保留聚集 inode 0。
聚集 inode 1,即自身 inode ,描述包括聚集 inode 映射表的聚集磁盘块。这是一种循环表示法,因为聚集 inode 1 本身也在自己所描述的文件中。可通过强制规定至少第一个聚集 inode 盘区要在众所周知的位置,即主聚集超级块后面 4K 的位置,来处理以上显而易见的循环表示法问题。因此,JFS 能轻而易举地找到聚集 inode 1,从聚集 inode 1,通过跟随 inode 1 中的 B+ 树,能找到聚集 inode 表的余下 inode 。
要复制聚集 inode 表,JFS 还需要找到聚集 inode 1 的副本,以查找所复制表的其余部分。超级块会包含一个盘区描述符,该描述符描述辅助聚集 inode 表的第一个 inode 盘区的位置。JFS 能够从中找到辅助聚集 inode 1,以及辅助聚集 inode 表的余下部分。
聚集 inode 2 描述块分配映射表。
聚集 inode 3 描述安装时的内嵌日志。虽然分配了 inode ,但无数据存入磁盘。
聚集 inode 4 描述在聚集格式化期间发现的坏块。在块映射表中这些标记成已分配。该 inode 是数据为坏块的普通文件。
保留聚集 inode 5 到 15 以备将来扩展。
从聚集 inode 16 开始,每个文件集有一个 inode ,即文件集分配映射表 inode 。这个 inode 描述了表示文件集的控制结构。当更多文件集添加到聚集中时,为了容纳更多的文件集 inode ,聚集 inode 表本身可能必须增大。

分配组
分配组(AG)把聚集中的空间分成大块,并且允许 JFS 资源分配策略使用众所周知的方法,来实现更好的 JFS I/O 性能。首先,分配策略尝试将相关数据的磁盘块和磁盘 inode 集群起来,使磁盘实现好的局域性。文件通常是顺序地读写,而目录中的文件通常一起访问。其次,为了容纳局域性,分配策略尝试在整个聚集中分配不相关数据。 聚集内的分配组用从 0 开始的 AG(分配组)索引。即用 AG 标识。

必须选择分配组大小,以使 AG 足够大以不断提供连续资源分配。为了将聚集扩充或缩小时所需进行的更新数最小化,分配组必须限制最大组数 128。此外,JFS 将对 8192 个聚集块的分配组大小规定其最小值。分配组大小必须总是 1 个 dmap 页(1、2、4、8、 ...dmap 页)描述的块数的 2的幂次方。分配组大小在聚集超级块中存储。

大小不是分配组大小倍数的聚集将包含部分分配组;磁盘块没有完全覆盖聚集的最后一个分配组。除了JFS 将标记在块分配映射表中分配的却不存在的磁盘块之外,该部分分配组将被当作完整的分配组。

文件集
文件集是文件和目录的集合,这些文件和目录形成了可独立安装的子树。文件集完全包含在一个聚集中。请注意,一个聚集中可能有多个文件集;在那种情况下,所有文件集共享由聚集控制结构定义的空闲聚集磁盘块公共池。
JFS文件系统原理--JFS布局 - liqi.xie - Liqix的程序世界
图 2 显示在一个聚集中包含两个文件集的布局。

文件集有:

文件集 inode 表,包含描述文件集范围的控制结构的 inode 。文件集 inode 表逻辑上包含一个 inode 数组。
文件集 inode 分配映射表,描述文件集 inode 表。文件集 inode 分配映射表包含文件集 inode 上及其磁盘位置上的分配状态信息。描述文件集分配映射表和其他文件集信息的超级 inode ,驻留前面所描述的聚集 inode 表中。由于复制了聚集 inode 表,因此这个 inode 存在第二个版本,它指向同样的数据。超级 inode 本身是一个文件。当文件集一开始创建时,分配第一个 inode 盘区按需要动态分配和释放其它 inode 盘区。

文件集中 inode 的分配如下所示:

保留文件集 inode 0。
文件集 inode 1 包含附加的文件集信息,它们无法放入聚集 inode 表中的文件集分配映射表 inode 。
文件集 inode 2 是文件集的根目录 inode 。注意,JFS 保留了 inode 2 是文件系统的根这一公共 Unix 约定。
文件集 inode 3 是文件集的 ACL 文件。
从文件集 inode 4 开始,文件集 inode 用于一般文件集对象、用户文件、目录和符号链接。

盘区、inode 、B+ 树
盘区是当作单元分配给 JFS 对象的连续聚集块序列。盘区完全包含在一个聚集(并且因此也是在一个分区)中;但是,大盘区可能跨多个分配组。

每个 JFS 对象可用一个 inode 来表示。inode 包含预期的对象特定信息,例如:时间戳和文件类型。它们还包含记录盘区分配的 B+ 树。注意,所有 JFS 元数据结构(除超级块之外)都以文件表示。通过重用这种数据的 inode 结构,数据格式(即磁盘布局) 自然是可扩展的。

盘区、B+ 树、inode 在以下章节中详细描述。

盘区
文件是按盘区顺序分配的。盘区是当作一个单元分配的聚集块的连续变长序列。盘区的尺寸范围是 1 到 2(24)-1 个聚集块。盘区可能跨越多个分配组(AG)。为了在插入新盘区、定位特定盘区等操作方面有更优性能,这些盘区是按 B+ 树索引的。

定义一个盘区需要两个值,即其长度和其地址。长度以聚集块尺寸为单位计算。JFS 使用 24 位值来表示盘区的长度,因此盘区的范围大小是 1 到 2(24)-1 个聚集块。

对于 512 字节的聚集块尺寸 (所允许的最小值),最大盘区是512*(2(24)-1)字节,(比 8G 稍小)。对于 4096 字节的聚集块尺寸(所允许的最大值),盘区的最大长度是 4096*(2(24)-1)字节,(比 64G 稍小)。这些限制仅适用于一个的盘区;对整体文件大小没有限制作用。地址指的是盘区中第一个块的地址。地址同样以聚集块为单位:它从聚集的开始处计算块偏 移量。

结合了用户特定聚集块尺寸的基于盘区的文件系统,允许 JFS 不需要单独支持内部存储碎片。可配置聚集使用小的聚集块尺寸(例如,512 字节),以使大量小尺寸文件的聚集内部存储碎片最小化。

通常,JFS 分配尝试通过分配最小数量的盘区策略,而使每个盘区尽可能大。这就允许大的 I/O 传送,结果使得性能提高。然而,对于特殊情况,不一定总有这种结果。例如,一个段的写入时复制会造成连续盘区被分割成更小的连续盘区系列。另一种情况是盘 区大小的限制。例如:由于 JFS 必须把整个盘区读入内存,然后进行解压缩,所以压缩文件盘区大小是有限的。由于 JFS 的可用内存数量有限,因此它必须保证有足够的空间用于解压缩盘区。

提供了一个碎片整理实用程序,以减少动态分配/释放可变长盘区时出现的外部存储碎片。这种分配和释放可能导致不相连的变长空闲盘区遍及整个聚集。碎片整理实用程序会把多个小的空闲盘区合并成一个较大的盘区。

inode
JFS 磁盘 inode 是 512 字节。一个 JFS 磁盘 inode 包含 4 组基本信息。第一组描述 JFS 对象的 POSIX 属性。第二组描述 JFS 对象的其它属性;这些属性包括支持 VFS 必需的信息、操作系统环境特定的信息、以及 B+ 树的头部。第三组不是包含 B+ 树根节点的盘区分配描述符就是包含内嵌数据。第四组包含扩展属性、更多内嵌数据或附加的盘区分配描述符。在 jfs_dinode.h 的 struct dinode 中定义磁盘 inode 结构。

JFS 动态分配 inode 提供的好处如下:


inode 磁盘块可放在任何磁盘地址,这使得 inode 号和位置分开。这种分离简化了支持聚集和文件集重组,能够使聚集缩小。可以移动 inode ,移动后号码仍然相同。这允许 JFS 不必需要查找目录结构就可以更新 inode 号。对于支持 DFS 文件集复制而言,这种分离也是必需的。当复制文件集时,仅复制 inode 。既然 JFS 能把新的 inode 放在磁盘的任意位置,新 inode 将有与从它们复制的 inode 相同的号码。这允许 JFS 不需复制目录结构并且更新 inode 号。
不再需要分配实际所需十倍的 inode 。这对于 JFS 中较大的 inode 尺寸(大于 512 字节)而言,尤为重要。
大文件的文件分配可能消耗多个分配组且仍是连续的,而静态分配造成间隔(由于每个分配组中初始分配的 inode )。

另一方面,动态 inode 分配造成大量问题,包括:

对于静态分配,文件系统的几何构造隐含描述了磁盘上 inode 的布局;对于动态分配,必需有单独的映射结构。
对 JFS 完整性而言,这些映射结构是至关重要的。由于复制这些结构的系统开销,JFS 决定接受丢失这些映射表的风险。但是,JFS 将复制 B+ 树结构,该结构允许 JFS 查找映射表。

通过只分配磁盘上 inode 连续大块的 inode 盘区,动态分配了 inode 。根据定义,一个 JFS inode 盘区包含 32 个 inode 。对于 512 字节的 inode 尺寸,因此磁盘上一个 inode 盘区的大小是 16KB。

当分配新的 inode 盘区时,并不初始化盘区。然而,要使 fsck 能够检查是否 inode 在使用中,JFS 需要 inode 的一些信息。一旦盘区中的 inode 标记成在使用中,就必须初始化它的文件集号、inode 号、inode 戳以及 inode 分配组块地址。因此,链接字段就足以确定 inode 当前是否正在使用。

注意,动态 inode 分配意味着在 inode 号与 inode 的磁盘地址之间没有直接关系。因此,JFS 必须有查找磁盘上 inode 的方法。inode 分配映射表提供了这一功能。

inode 生成号只是每当重用 inode 时值就增加的计数器。

存储每个 inode 生成计数器这一静态 inode 分配常用方法在动态 inode 分配中不起作用,因为当 inode 空闲时,其磁盘空间可能确实由不是 inode 的数据所重用,(换句话说,空间可能被收回,以存储普通文件数据)。因此,在 JFS 中,只有一个 inode 生成计数器,它在每一个 inode 分配时增加其值,即在重用 inode 时,相应的计数器增加其值,而不是每个 inode 有一个计数器。

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

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

xad 结构为:

struct xad {
unsigned flag:8;
unsigned rsvrd:16;
unsigned off1:8;
uint32 off2;
unsigned len:24;
unsigned addr1: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+ 树节点中的项。
JFS文件系统原理--JFS布局 - liqi.xie - Liqix的程序世界
图 3 显示了一个 xad 结构以及它是如何描述文件内逻辑字节范围和磁盘上字节范围本身(也就是说,对于聚集)的物理位置。

磁盘 inode 第二扇区底部包含数据描述符,它描述在 inode 的后半部分内存储的内容。对于足够小的文件,后半部分可能包含内嵌数据。如果文件数据不适合 inode 的内嵌数据空间,它将包含在盘区中,inode 将包含 B+ 树的根节点。头部指出在使用的 xad 个数,可用的 xad 个数。通常,inode 将包含 8 个 xad 结构 B+ 树的根。如果文件有 8 个或更少盘区,那么这 8 个 xad 结构也是 B+ 树的叶节点。它们将描述盘区。(参见图 4,例 1。)否则,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+ 树的纯根。(参见图 4,例 2。)

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

这将持续直到填满 inode 的所有 8 个 xad 结构为止,这时,将再次拆分 B+ 树。这种拆分将创建 B+ 树的内部 inode ,它们是纯粹用来记录树的搜索路径。JFS 将为 B+ 树的内部 inode 分配 4K 磁盘空间。内部节点看起来如同叶节点。从 inode 复制 8 个 xad 项到内部节点,初始化头部以指向第 9 个项作为第一个空闲项。然后,通过使 inode 的第一个 xad 结构指向新分配的内部节点,JFS 更新 B+ 树的根。将更新 inode 中的头部以表示当前 B+ 树只使用 1 个 xad。(参见图 4,例 4。)
JFS文件系统原理--JFS布局 - liqi.xie - Liqix的程序世界
文件 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 结构,这是由于单个盘区的长度限制。

块分配映射表
块分配映射表用来为整个聚集跟踪分配或释放的磁盘块。由于聚集内所有的文件集共享相同的磁盘块池,在分配或释放磁盘块时,聚集内所有的文件集可使用该分配映射表。

块分配映射表本身是聚集 inode 2 描述的文件。当初始创建聚集时,分配包括聚集空间的映射表数据块。映射表将随着聚集的扩充或紧缩而相应动态地增大或缩小。

块分配映射表跟踪是否每个个别的聚集块被分配还是释放。
JFS文件系统原理--JFS布局 - liqi.xie - Liqix的程序世界
图 5 显示由块映射表 inode 索引的映射表的逻辑和物理结构。映射表的每页长度为 4K。映射表包含三种类型的页:bmap 控制页、dmap 控制页和 dmap 页。

每个 dmap 包含表示每个聚集块的一位。第 i 位表示第 i 个逻辑聚集块的分配状态。它由 struct dmap_t 的 jfs_dmap.h 文件定义。每个 dmap 页包括 8K 的聚集块。

因为块分配映射表可能有许多 dmap 页,它们由 dmap 控制页组织,LN 在图 5 中。这些页改进了查找空闲块的大盘区的性能。聚集的大小将决定需要多少页和多少层。至多有三层,它允许的聚集块的最大尺寸是 2(43)。如果不是所有层都需要,块映射表 inode 是每个没有使用层的第一页有“洞”的稀疏文件。

JFS 使用提交策略确保控制数据可靠更新。可靠更新意味着一旦系统出错时,要维持一致的 JFS 结构和资源分配状态。为了保证块分配映射表是一致状态,JFS 维护 dmap 结构中的两张映射表,工作映射表和持续映射表。工作映射表记录当前分配状态。持续映射表记录提交的分配状态,由磁盘上找到的或 JFS 日志或提交的 JFS 事务内的记录描述的分配状态组成。当释放聚集块时,首先更新永久映射表。当分配聚集块时,首先更新工作映射表。位值为 0 表示空闲资源,值为 1 表示已分配资源。

块分配映射表的 dmap 控制页包含与 dmap 结构中树相似的树,除叶层包含 1024 个元素外。dmap 控制页由 struct dmapctl_t 定义。可在 jfs_dmap.h. 文件中找到它。
JFS文件系统原理--JFS布局 - liqi.xie - Liqix的程序世界
图 6 从一个 dmap 结构显示树字段的细节。要注意,dmap 结构中的这一字段是一个平面数组,但它表示图中显示的树。树跟踪除最底层之外的每层上连续块的最大号。树的最底层,从树 [85] 到树 [341],包含下面描述的工作映射表的二进制搭档表示法。树的其它层包含来自下一较低层的四个部分的最大数目相连空闲块。

二进制搭档系统用来完成每个摘要树的叶层。通过首先为位图的每个字获得空闲位的最长二进制搭档字符串而形成 dmap 结构的树。字符以 2 的幂编码,-1 用来表示已分配全部。
JFS文件系统原理--JFS布局 - liqi.xie - Liqix的程序世界
图 7 显示了字查找一个空的最长二进制搭档字符串的例子。

然后,使用二进制搭档系统完成树的叶。通过取得从指定索引开始、只包括其以 2 的幂显示的搭档的最大数目空闲块,可形成此树。
JFS文件系统原理--JFS布局 - liqi.xie - Liqix的程序世界
图 8 显示了用图描述 dmap 树叶的缩略的示例。请注意,只有完全空闲的字才与其完全空闲的搭档组合。组合时,最右搭档变成 -1,以指示它由另一项所表示。

块分配映射表的 dmap 控制页包含与 dmap 结构中树相似的树,除叶层包含 1024 个元素外。这些元素是树 [0] 为紧跟下面的 1024 个映射表页的二进制搭档表示法。对于 L0 页,它是接下来的 1024 个 dmap 页,对于 L1 页,它是接下来的 1024 个 L0 页,而对于 L2 页,它是接下来 1024 个 L1 页。

在块分配映射表的顶部,有映射表控制结构 structdbmap_t。该结构包含摘要信息,能加快查找比平均空闲空间多的 AG。可在 jfs_dmap.h 中找到该结构。

块分配映射表没有记日志:它能在恢复期间由 logredo 修复,或者由 fsck 重构。在 fsck 或 logredo 后工作和持续映射表,都必需是相同状态。

扩展聚集以增大文件系统
要扩展聚集,JFS 必须确保有足够的页存储块分配映射表, 索引聚集新扩展的块。通常,从现有的聚集分配空间给新增的页,但是如果该聚集空间已满,那就不可能了。所以我们需要解决这种特殊情况。

要解决该问题,通常 JFS 为块分配映射表分配的空间多于索引聚集地址空间所需的空间。每个映射表都有额外页空间用于存放位图,如果该页指向另一层摘要树,则该映射表就需额外页存放 所需的摘要信息。这种额外空间使得 JFS 可以在必要时将聚集分为更小的单位,以扩大聚集至所需的大小。扩展聚集,需采取以下步骤:


如果现有聚集的空间足以扩展块分配映射表,使其能索引新聚集的所有块,那么,JFS 不做任何特殊处理,将聚集扩展至整个空间。仅当需要考虑聚集将来的扩展时,块分配映射表才需增加额外页。
如果没有足够空间扩展,那么 JFS 仅给聚集扩展块分配映射表中已有额外页所能寻址的块。
至此,JFS 有一些额外的聚集块未在聚集中使用到。JFS 可以用这些聚集块扩大块分配映射表,以继续将聚集扩展至所需大小。JFS 必须谨记将这些额外页放入块分配映射表中。

这个处理过程完全由 vfs_cntl() 处理,对系统的其它部分隐藏。

另一种表示法:二进制编码搭档表示法
块分配映射表也可以用二进制编码搭档系统表示。除了树的叶结点和 dmap 结构不同外,这种表示法的逻辑和物理结构与前一种一样。

struct dmap 定义块分配映射表的最下层。每个 dmap 页包括 8K 的聚集块。

/*
* dmap summary tree
*
* dmaptree_t must be consistent with dmapctl_t.
*/
typedef struct {
int32 nleafs; /* 4: number of tree leafs */
int32 l2nleafs; /* 4: l2 number of tree leafs */
int32 leafidx; /* 4: index of first tree leaf */
int32 height; /* 4: height of the tree */
int8 budmin; /* 1: min l2 tree leaf value to combine*/
int8 stree[TREESIZE]; /* TREESIZE: tree */
uint8 pad[2]; /* 2: pad to word boundary */
} dmaptree_t; /* - 360 - */


/*
* dmap page per 8K blocks bitmap
*/
typedef struct {
int32 nblocks; /* 4: num blks covered by this dmap */
int32 nfree; /* 4: num of free blks in this dmap */
int64 start; /* 8: starting blkno for this dmap */
dmaptree_t tree; /* 360: dmap tree */
uint8 pad[1672]; /* 1672: pad to 2048 bytes */
uint32 wmap[LPERDMAP]; /* 1024: bits of the working map */
uint32 pmap[LPERDMAP]; /* 1024: bits of the persistent map */
} dmap_t; /* - 4096 - */


二进制编码搭档系统的每一项都有三个字段:type,size 和 bitmap。type 字段表示块空闲、已分配、用位图表示或不由该字段表示 (don't care)。如果类型是"don't care"则这些块由左搭档表示,size 字段忽略。如果 type 是位图,则位图字段的 32 位和 32 块一一对应,表示其空闲或已分配。位值 0 表示空闲块,1 表示块已分配。size 是 2 的幂次方,表示该项描述的聚集块的个数。

对于每个全空闲项,如果其相同大小的左搭档也完全空闲,则右搭档设为"don't care"类型,且右搭档的空间合并入左搭档。当分配块时,仅当搭档分配在同一盘区才合并。必须维护"don't care"类型,以便 logredo 修正映射表。
JFS文件系统原理--JFS布局 - liqi.xie - Liqix的程序世界
图 9 显示了进行分配和回收二进制编码搭档的小例子。

结构 dmap 包含一个摘要树。其它每个映射层都包含一个摘要树。摘要树提高了查找空闲块大盘区的性能。摘要信息足以判断 dmap 页是否有足够的空闲位,这样就无需查看 dmap 页,从而可以避免无效搜索。
JFS文件系统原理--JFS布局 - liqi.xie - Liqix的程序世界
图 10 给出了一个 dmap 结构中树字段的细节。要注意,dmap 结构中的这一字段是一个平面数组,但它表示图中显示的树。树的每一层都索引最大数目个相邻的块。树的最底层,树[21]至树[84],映射至工作映射表中 的二进制编码搭档表示。树的其它层包含来自下一较低层的四个部分的最大数目相连空闲块。块分配映射表的其它层可能有一个相似的树,除了叶节点层有 1024 个元素。这些元素映射至树[0]的二进制编码搭档表示,树[0]指向后面的 dmap 页。

如果要合并的四个都为"don't care"类型,则合并项大小标记为 -1。这些项的搭档项负责标记正确的状态。

inode 分配
动态 inode 分配机制中,inode 号不再直接映射至聚集中特定的逻辑磁盘块,所以要支持下列三种操作,需要定义新的数据结构:

正向查找: 给定 inode 号,找到磁盘上的 inode 。文件查找是一种典型的正向查找。
反向查找:给定分区磁盘号(更确定,则给定分配组号),查找邻近的空闲 i-结点。分配新 inode 就属于这种情况,JFS 尽量查找物理上邻近所选分配组的 inode (以便,例如, 同一子目录的文件其 inode 都是相邻的)。
空闲 inode 号查找:要分配新的 inode 盘区,先要找到 32 个相邻的、未分配给相应 inode 盘区的 inode 。当所有已分配的 inode 都在使用,或当 JFS 需要给分配组分配 inode 但以前从未分配过 inode 时,或当一个分配组中没有空闲 inode 时,需要分配新的 inode 盘区。

注意动态 inode 分配的一种微妙效应:相邻 inode 号在磁盘上未必相邻:inode N+32 可以和 inode N 相隔任意远。然而,相隔很远的 inode 号在磁盘上可以是紧邻的;所以,inode N+K 和 inode N 紧邻在理论上是可能的(即使 K>1)

inode 分配映射表
inode 分配映射表解决正向查找问题。聚集和每个文件集都有一个 inode 分配映射表,该表是一个 IAG(inode 分配组)的数组。IAG 是 inode 分配映射表的数据。对于聚集,inode 分配映射表映射的 inode 也称为聚集 inode 表。对于文件集,inode 分配映射表映射的 inode 也称为文件 inode 表。

每个 IAG 大小为 4K,描述磁盘上 128 个物理 inode 盘区。由于每个 inode 盘区包含 32 个 inode ,所以每个 IAG 描述 4096 个 inode 。IAG 可以位于聚集的任意位置。IAG 的所有 inode 盘区位于一个分配组,由此 IAG 和 AG 绑定在一起直至释放所有的 inode 盘区。任意 AG 可以分配空间给一个 inode 盘区,然后该 IAG 就与那个 AG 绑定。IAG 由 struct iag_t 定义(见 jfs_imap.h )。

/*
* inode allocation group page (per 4096 inodes of an AG)
*/
typedef struct {
int64 agstart; /* 8: starting block of ag */
int32 iagnum; /* 4: inode allocation group number */
int32 inofreefwd; /* 4: ag inode free list forward */
int32 inofreeback; /* 4: ag inode free list back */
int32 extfreefwd; /* 4: ag inode extent free list forward */
int32 extfreeback; /* 4: ag inode extent free list back */
int32 iagfree; /* 4: iag free list */

/* summary map: 1 bit per inode extent */
int32 inosmap[SMAPSZ];/* 16: sum map of mapwords w/ free inodes;
* note: this indicates free and backed
* inodes, if the extent is not backed the
* value will be 1. if the extent is
* backed but all inodes are being used the
* value will be 1. if the extent is
* backed but at least one of the inodes is
* free the value will be 0.
*/
int32 extsmap[SMAPSZ];/* 16: sum map of mapwords w/ free extents */
int32 nfreeinos; /* 4: number of free inodes */
int32 nfreeexts; /* 4: number of free extents */
/* (72) */
uint8 pad[1976]; /* 1976: pad to 2048 bytes */
/* allocation bit map: 1 bit per inode (0 - free, 1 - allocated) */
uint32 wmap[EXTSPERIAG]; /* 512: working allocation map */
uint32 pmap[EXTSPERIAG]; /* 512: persistent allocation map */
pxd_t inoext[EXTSPERIAG]; /* 1024: inode extent addresses */
} iag_t; /* (4096) */


inode 分配映射表最前面 4k 大小的页是控制页。该页包含 inode 分配映射表的摘要信息。dinomap_t 结构的定义见 jfs_imap.h。

逻辑上,inode 分配映射表是动态可扩展的 IAG 结构的数组:


struct iag inode_allocation_map [ 1.. N ];

物理上,inode 分配映射表本身是聚集内的一个文件。聚集 inode 分配映射表由聚集 self-node 描述。文件集 inode 分配映射表由文件集 inode 描述。页空间的分配和释放依据 B+ 树索引需要进行。B+ 树的键是 IAG 页的字节偏移量。

JFS 使用提交策略确保控制数据可靠更新。可靠更新意味着一旦系统出错时,要维持一致的 JFS 结构和资源分配状态。为确保 inode 分配映射表的一致性,每个 IAG 都同时维护两个映射表,工作映射表和持续映射表。工作映射表记录当前分配状态。持续磁盘记录递交的分配状态,包括磁盘上记录的分配状态或是 JFS 日志中提交的 JFS 事务记录描述的分配状态。

映射表中的每一位记录相应 inode 是空闲还是已分配的。位值 0 表示 inode 空闲,1 表示 inode 已分配。IAG 的每一个控制区内都有一个摘要映射表,用以提高查找空闲 inode 的性能。摘要映射表映射到 IAG 的工作位图。摘要映射表使用一位映射工作映射表的相邻 32 位。每一位表示相应的 inode 可用(0),或相应的 inode 不可用(1)。(如果没有已分配的盘区,那么该 inode 摘要映射位为 1,表明没有可用的 inode ,)

IAG 还包含 inode 盘区描述符,该描述符描述相应的 inode 盘区。每个 IAG 有 128 个描述符。IAG 的每个控制区内都有一个摘要映射表,用于改进空闲 inode 盘区查找的性能。摘要映射表用一位映射一个 inode 盘区。0 表示空闲的 inode 盘区,1 表示已分配的 inode 盘区。

如果给定 inode 号,用 inode 分配映射表,通过以下步骤,可以找到 inode 的物理位置:

1. 找到描述该 inode 的 IAG。需要找到 inode 分配映射表在 B+ 树中的键(字节偏移量)。

iag key = ((Inode number / Inodes per iag) * Inodes per iag) + 4096 (EQ 1)


2. 查找已找到的 IAG 中引用的 inode 。这可用于在 IAG 工作映射表和持续映射表中索引。

iag inode index = (Inode number) mod (Inodes per iag) (EQ 2)


3. 查找 IAG 中的 inode 盘区描述符,该描述符描述包含指定 inode 的 inode 盘区。

inode extent des criptor = (iag inode index) / (Inode per inode extent) (EQ 3)


4. 要找的 inode 位于找到的 inode 盘区内、适当的偏移量处。

inode offset = ((iag inode index) mod (Inodes per inode extent)
* sizeof dinode) (EQ 4)

JFS文件系统原理--JFS布局 - liqi.xie - Liqix的程序世界
图 11 显示了查找 inode #9157 的例子。inode 分配映射表本身由聚集 inode 表中文件集的分配映射表 inode 描述。

通过前面介绍的公式,将 inode 号,#9157,转换成一个偏移量:

iag key = ((inum / num_inodes_per_iag ) * (num_inodes_per_iag )) + 4096
= ((9157 / 4096) * 4096 ) + 4096
= 12288
iag inode index = inum mod num_inodes_per_iag
= (9157 mod 4096 )
= 965
inode extent des criptor = iag_inode_index / num_inodes_per_extent
= 965 / 32
= 30
inode offset = (iag_inode_index mod num_inodes_per_extent)
* sizeof dinode
= (965 mod 32) * 512
= 5 * 512
= 2560


为简化 JFS 维护命令,及便于理解布局策略的动态性,inode 分配映射文件盘区的大小总为 4KB。

当新文件集创建时,必须分配一个 IAG 以及第一个 inode 盘区,以处理文件集的元数据文件。(即,保留的 inode 和根目录 inode )。

AG 空闲 inode 列表
AG 空闲 inode 列表解决反向查找问题。为减少扩展和缩减聚集的系统开销,JFS 设定每个聚集允许的最大 AG 数。所以,AG 空闲 inode 列表头的个数是固定的。列表头在 inode 分配映射表的控制页中。表的第 i 项是一个双向列表的头,表的第 i 项 是一个双向列表的头,该双向列表是第 i 个 AG 中的所有包含空闲 inode 的 inode 分配映射表项(IAG)的集合。IAG 号作为列表索引。-1 表示列表尾。每个 IAG 控制区都包含指向该列表的正向和反向指针。

AG 列表从表头开始插入。当分配新的 inode 盘区,或当因盘区占满而删除一个 inode 时,会有插入操作。当一个 IAG 所有的 inode 盘区都满时,从列表中删除该 IAG。
JFS文件系统原理--JFS布局 - liqi.xie - Liqix的程序世界
图 12 显示了 AG 空闲 inode 列表的布局。注意 AG3 中的 IAG 没有任何相应的 inode 盘区可供分配。所以,这些 inode 未在 AG 空闲 inode 列表中表示。

此表没有记日志;但可以在恢复时由 logredo 恢复,或由 fsck 重建。AG 空闲列表结构定义是 struct dinomap_t,见 jfs_imap.h 文件。

AG 空闲 inode 盘区列表
AG 空闲 inode 盘区列表有助于解决反向查找问题以及空闲 inode 号查找问题。这使得 JFS 能找到下一个空闲盘区所在的 IAG 号和 AG 号。(实际是给出了空闲 inode 号。)每个文件集的每个 AG 都有一个AG 空闲 inode 盘区列表。为减少扩展和缩减聚集的系统开销,JFS 设定每个聚集允许的最大 AG 数。所以,AG 空闲 inode 盘区列表头的个数是固定的。列表头在 inode 分配映射表的控制页中。表的第 i 项是一个双向列表的头,该双向列表是第 i 个 AG 中所有包含空闲 inode 的 inode 分配映射表项(IAG)的集合。IAG 号作为列表索引。-1 表示列表尾。每个 IAG 控制区都包含指向该列表的正向和反向指针。

当盘区中所有的 inode 都已删除,则释放该 inode 盘区的磁盘块。当 IAG 的一个 inode 盘区被删除时,该 IAG 插至所属的 AG 空闲 inode 盘区列表的表头。当创建新的 IAG,并分配一个 inode 盘区时,该 IAG 号插至 AG 空闲 inode 盘区列表的表头。当 IAG 的所有 inode 盘区分配完时,从列表中删除该 IAG。当释放 IAG 的所有 inode 盘区时,从列表中删除该 IAG 同时加到IAG 空闲列表中。当 AG 需要分配 inode 盘区时, 则使用 AG 空闲列表头上的第一项。图 12 显示了 AG 空闲 inode 盘区列表的布局示例。该例中,AG 空闲 inode 盘区列表和 AG 空闲 inode 列表相同。

此表没有记日志;但可以在恢复时由 logredo 恢复,或由 fsck 重建。

表的结构定义见 jfs_imap.h, struct dinomap_t.

IAG 空闲列表
IAG 空闲列表有助于查找空闲 inode 号。这使得 JFS 不用查看相应分配的 inode 盘区就可找到 IAG。(实际时给出了空闲 inode 号)。聚集和其每个文件集都有自己的链表。该列表的每个项指向一个 IAG 链表。IAG 号作为列表索引。-1 表示列表尾。当删除盘区的所有 inode 时,则释放该 inode 盘区的磁盘块。如果某个 IAG 的所有 inode 都为空闲,则该 IAG 号插入 IAG 空闲列表头。当需要分配新的 inode 盘区,而该 AG 中又没有包含空闲盘区的 IAG,则使用 IAG 空闲列表头的第一项(即从表中删除)。inode 盘区分配描述符一经分配就不再删除。inode 盘区的地址设为 0x0。图 12 中分配组3 的 inode 可能在列表上。

对于聚集 IAG 空闲列表头是聚集自用 inode 的一个字段。对于每个文件集 IAG 空闲列表头是文件集分配映射表 inode 的一个字段。该列表没记日志;但可在恢复时由 logredo 修复,或由 fsck 重建。

IAG 空闲列表的结构定义 struct inomap_t 在文件 jfs_dinode.h 中。

下一个空闲 IAG
下一个空闲 IAG 计数器有助于查找空闲 inode 号。使得 JFS 能找到下一个可以分配的 IAG 的 iag号。(实际是让 JFS 找到空闲 inode 号)。聚集和其每个文件集都有自己的计数器。计数器在 inode 分配映射表的控制页中。IAG 一经分配就不再删除。

文件集分配 inode
文件集 inode 表中的文件集分配映射表 inode 是特殊类型的 inode 。既然这些节点表示文件集,则可以说是文件集的“父 inode ”。这些节点包含文件集特定信息,而不是一般的 inode 数据。同时也记录文件集 inode 分配映射表在 B+ 树中的位置。结构定义 struct dinode 见文件 jfs_dinode.h

文件
文件由包含一个 B+ 树根的 inode 表示,B+树描述包含用户数据的盘区。B+ 树以盘区的偏移量作为索引。

符号链接
符号链接由一个 inode 表示,该 inode 的 di_mode 字段设置为符号链接模式 (S_IFLNK)。如果 inode 内有空间,则链接文件的整个路径直接存储在 inode 中。否则,将作为 inode 的数据存于盘区中(通过该 inode 的 B+ 树索引)。

目录
目录是 JFS 中日志化的元数据文件。目录由目录项组成,目录项表示目录中包含的对象。目录项将名字和 inode 号连接在一起。特定的 inode 描述特定名字的对象。为提高目录项定位的性能,B+ 树采用按名排序。

目录 inode 的 di_size 字段仅表示目录 B+ 树的叶子页。如果 inode 中包含目录的叶节点,则 di_size 字段为256。

目录中没有特定项表示自身 (".") 和父目录 ("..")。而在 inode 中表示。自身就是目录自己的 inode 号。父目录是 inode 中的特殊字段,idotdot,struct dtroot_t,见文件 jfs_dtree.h。

目录 inode 包含 B+ 树的根,处理方法和一般文件类似。只是目录 B+ 树以名为键。目录 B+ 树的叶节点包含目录项,且以目录项的全名作为键值。目录 B+ 树最下层内部节点使用后缀压缩。其它内部节点采用相同的压缩后缀。后缀压缩将名字缩至最短,正好足以区分当前目录项和前一目录项。
JFS文件系统原理--JFS布局 - liqi.xie - Liqix的程序世界
图 13 显示后缀压缩的示例。

由于 B+ 树项的大小是可变的,JFS 需要处理这些项的方案。JFS 想要避免在删除一项时引起的项移动,平均一项有2K的数据。
JFS文件系统原理--JFS布局 - liqi.xie - Liqix的程序世界
图 14 显示了目录 B+ 树节点的内容:


固定个数的目录槽,个数取决于节点的大小。这些槽用于存储目录槽数组和目录项或路由项。目录槽的大小总是 32 字节。固定大小的目录槽使得 JFS 在删除目录项不必移动,从而还避免了内部碎片。
一个目录 B+ 树的头,描述 B+ 树 inode 。此部分包含一个标志,标记节点是内部节点或是叶节点, 及是不是 B+ 树的根节点。还包含自身的块地址。nextindex 字段记录目录槽数组中的最后一项。stblindex 字段记录目录槽数组的开始位置。freelist 字段指向该节点中空闲槽列表头。
一个目录槽数组,它是正使用的目录槽索引的有序数组。使用该数组减少了目录项增删时所需的移动次数。数组比项本身小很多,所以移动的只是数组而不是整个项。在数组中,可以用二分法搜索某个目录项。
一个目录 B+ 树槽空闲列表,使得内部碎片最小化。目录 B+ 树的头包含列表表头,每个空闲目录槽指向列表中的下一个空闲槽。如果有一系列相连的空闲槽,则在第一个槽中设立一个计数值,说明该系列的长度。这有利于在新建目录 B+ 树节点时,进行快速初始化。
一个目录项,将名字链接到一个 inode 号。目录项包含在叶节点的目录槽中。如果需要存储整个目录名,目录项可以有附加槽。目录项的 next 字段表明该项是否有后继项。大多数目录项只有单个槽。
一个路由项,用于记录目录 B+ 树的搜索路径。路由项包含在内部节点的目录槽中。路由项将按后缀压缩的路由键映射到盘区,此盘区包含下一层目录 B+ 树的内部节点或叶节点。如果路由项需要记录整个的路由键,则可以有附加槽。路由项的 next 字段表示该项是否有后继项。大多数路由项只有单个槽。

目录 B+ 树中的内部节点或叶节点是 4K 大小的页。由于许多目录都不是很大,所以这种方式对大多数目录来说是很浪费磁盘空间的。所以目录的初始叶节点采用以下分配方案:

初始目录项存储在目录嵌入数据区中。
当目录 inode 的嵌入数据区填满时,JFS 分配一个叶节点,大小和聚集块的尺寸一样。
当初始叶节被占满,而大小又不到 4k,则倍增节点大小。首先在当前盘区中扩增;如果没有足够空间,则需分配新的盘区,然后将旧盘区的数据复制到新盘区。目录槽数组仅够存放页未扩时的槽, 所以必须创建新的槽数组。从新分配的数组起始处使用槽,并将旧的数组数据复制到新的位置。更新指向该数组的头指针,并将旧数组中的槽添加到空闲列表中。
JFS文件系统原理--JFS布局 - liqi.xie - Liqix的程序世界
图 15 描述了目录增加一层的过程。
如果叶节点再次填满,而大小仍不足 4K,重复步骤 3。一旦叶节点达到 4K 则分配新叶节点。初始节点后的每个叶节点,一开始就分配 4K。
当叶子页的所有项都释放,则从 B+ 树中删除该页。仅当目录中所有目录项都已删除,目录又缩回 inode 。

访问控制列表 (ACL)
JFS 的每个 inode 都有不同的访问控制列表 (ACL)。ACL 可以表示不同的项,例如许可权、用户标识符、或组标识符。聚集 inode 的 ACL 字段是没有用的。

虽然在磁盘上和内存中 ACL 的表示方式没有规定,但从 DFS 外部所看到的“外部”表示是固定的。ACL 大小的唯一限制是其外部表示必须适合 8192 字节大小的 dfs_acl 结构。

任意 JFS 对象都可有一个管理该对象存取的 ACL;这种 ACL 称为常规 ACL。目录对象在创建时可能用到两个关联的可选 ACL;初始目录 ACL和初始文件 ACL。初始 ACL 的作用范围是目录中的所有文件。

ACL 体系结构未指定 ACL 的存储方式,但建议 ACL 有字段标识或命名其辅助对象,这样通过简单的等同性检查就可以检测到文件集中的共享关系。因此,JFS 在每个文件集中用一个文件(ACL 文件)存储文件集的 ACL;文件集 inode 1 就是 ACL 文件。文件集中的每个 inode 在 ACL 文件中存放一个索引。

ACL 文件需要一个存储 ACL 空闲区域的位图。ACL 文件有一个 4K 大小的位图,标识 8M 的 ACL 项,如有必要可扩增。位图中的一位代表 256 字节连续磁盘空间;位图不描述自身的状态。

JFS文件系统原理--JFS布局 - liqi.xie - Liqix的程序世界
图 16 是 ACL 文件的布局。

ACL 文件的数据未日志化。

扩展属性(EA)
扩展属性是附加到 JFS 对象适用存储和存取的机制。EA 连续存储在扩展属性空间 (EAS) 中,空格存储 EAS 由 JFS 对象 inode 的 EA 描述符定义。EA 描述符只是一个盘区描述符,定义见 jfs_types.h,struct dxd_t。

EA 可以存放在 inode 内,或存放在单独盘区内。EA 描述符的标志字段指示存储的方式。由于此空间也可用于存放文件 xtree 附加的 xad 项,所以 inode 的 di_mode 字段指明该空间是否可用。如果该字段值为 INLINEEA,则表明空间可用。

如果 EA 存于 inode 内,则忽略 EA 描述符的 offset 和 length 字段。EA 描述符的大小表示数据的字节数。

如果 EA 存于盘区内,EA 描述符将描述该盘区。JFS 不希望 EA 数据太大,所以 JFS 不支持每个 inode 有多于一个盘区的 EA 数据。

EA 项包括 EA 名称和其值。要访问某个 EA,JFS 只是线性搜索 EA 数据。

EA 数据未日志化,但它是写同步的(即数据不是旧数据,就是新数据,但绝不可能是部分更新的数据)。JFS 在日志中记录 EA 数据的位置。嵌入 EA 数据是日志化的。


流用于将数据连接到一个文件或目录。这种附加数据和目录数据相似,都可按名引用。在第一版中不支持流,在这里讨论仅为元数据结构的完整性。

磁盘 inode 的四部分的第二部分有一个字段描述流描述符。由于附加到一个对象的流数目是可变的,所以流描述符是一个 inode 号,以允许流增加或缩减。流描述符 inode 指向的数据称为流列表。

流没有关联的扩展属性,所以从不使用流的 inode 四部分的最后一个部分-扩展属性。实际上该部分用于附加的流项。B+ 树的数据如同目录项。每个流都有自己的 inode ,它们依次记录流数据存放的数据块地址。
JFS文件系统原理--JFS布局 - liqi.xie - Liqix的程序世界
图 17 是流的例子;流未记入日志。

带有文件集的聚集

JFS文件系统原理--JFS布局 - liqi.xie - Liqix的程序世界
图 18 是包含一个文件集的聚集。

结束语
JFS 小组最重要的目标是创建可靠的,高性能的文件系统。本文讨论了 JFS 磁盘布局结构,以及实现可伸缩性、可靠性和高性能的机制。同时详细探讨了 JFS 如何在整个文件系统中使用 B+ 树提高文件系统操作。

JFS 小组将 JFS 移植到 Linux 的工作正取得重大进展。如有兴趣参与,请访问我们在 developerWorks 上的 JFS 项目主页。

参考资料

关于作者
Steve Best 在美国德克赛斯州奥斯汀 IBM Software Solution & Strategy Division 工作,是文件系统开发部门的成员。Steve 以前从事操作系统上文件系统、国际化以及安全性领域的开发。目前,Steve 正从事将 JFS 移植到 Linux 的工作。可通过 sbest@us.ibm.com 与他取得联系。

Dave Kleikamp 是奥斯汀 IBM Software Solution & Strategy Division 的成员。Dave 曾是 OS/2 JFS 文件系统的技术负责人,并且是 AIX 的调试专家。Dave 正从事 JFS 到 Linux 的开放源码移植。联系地址:shaggy@us.ibm.com。
  评论这张
 
阅读(341)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017