JFS布局:日志文件系统如何处理磁盘布局

图 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 descriptor  = (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)

图 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 descriptor = 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。

图 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 列表相同。