JFS 文件系统概述及布局分析（五）

　　块分配映射表

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

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

　　块分配映射表跟踪是否每个个别的聚集块被分配还是释放。

　　映射表的每页长度为4K。映射表包含三种类型的页：bmap控制页、dmap控制页和dmap页。

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

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

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

　　块分配映射表的dmap控制页包含与dmap结构中树相似的树，除叶层包含1024个元素外。dmap控制页由structdmapctl_t定义。可在jfs_dmap.h.文件中找到它。

　　要注意，dmap结构中的这一字段是一个平面数组，但它表示图中显示的树。树跟踪除最底层之外的每层上连续块的最大号。树的最底层，从树[85]到树[341]，包含下面描述的工作映射表的二进制搭档表示法。树的其它层包含来自下一较低层的四个部分的最大数目相连空闲块。

　　二进制搭档系统用来完成每个摘要树的叶层。通过首先为位图的每个字获得空闲位的最长二进制搭档字符串而形成dmap结构的树。字符以2的幂编码，-1用来表示已分配全部。

　　然后，使用二进制搭档系统完成树的叶。通过取得从指定索引开始、只包括其以2的幂显示的搭档的最大数目空闲块，可形成此树。

　　请注意，只有完全空闲的字才与其完全空闲的搭档组合。组合时，最右搭档变成-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结构不同外，这种表示法的逻辑和物理结构与前一种一样。

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

　　

　　以下为引用的内容：

　　/*

　　*dmapsummarytree

　　*

　　*dmaptree_tmustbeconsistentwithdmapctl_t.

　　*/

　　typedefstruct{

　　int32nleafs;/*4:numberoftreeleafs*/

　　int32l2nleafs;/*4:l2numberoftreeleafs*/

　　int32leafidx;/*4:indexoffirsttreeleaf*/

　　int32height;/*4:heightofthetree*/

　　int8budmin;/*1:minl2treeleafvaluetocombine*/

　　int8stree[TREESIZE];/*TREESIZE:tree*/

　　uint8pad[2];/*2:padtowordboundary*/

　　}dmaptree_t;/*-360-*/

　　

　　

　　/*

　　*dmappageper8Kblocksbitmap

　　*/

　　typedefstruct{

　　int32nblocks;/*4:numblkscoveredbythisdmap*/

　　int32nfree;/*4:numoffreeblksinthisdmap*/

　　int64start;/*8:startingblknoforthisdmap*/

　　dmaptree_ttree;/*360:dmaptree*/

　　uint8pad[1672];/*1672:padto2048bytes*/

　　uint32wmap[LPERDMAP];/*1024:bitsoftheworkingmap*/

　　uint32pmap[LPERDMAP];/*1024:bitsofthepersistentmap*/

　　}dmap_t;/*-4096-*/

　　

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

　　对于每个全空闲项，如果其相同大小的左搭档也完全空闲，则右搭档设为"don'tcare"类型，且右搭档的空间合并入左搭档。当分配块时，仅当搭档分配在同一盘区才合并。必须维护"don'tcare"类型，以便logredo修正映射表。

　　结构dmap包含一个摘要树。其它每个映射层都包含一个摘要树。摘要树提高了查找空闲块大盘区的性能。摘要信息足以判断dmap页是否有足够的空闲位，这样就无需查看dmap页，从而可以避免无效搜索。

　　要注意，dmap结构中的这一字段是一个平面数组，但它表示图中显示的树。树的每一层都索引最大数目个相邻的块。树的最底层，树[21]至树[84]，映射至工作映射表中的二进制编码搭档表示。树的其它层包含来自下一较低层的四个部分的最大数目相连空闲块。块分配映射表的其它层可能有一个相似的树，除了叶节点层有1024个元素。这些元素映射至树[0]的二进制编码搭档表示，树[0]指向后面的dmap页。

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

　　inode分配

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

　　正向查找:给定inode号，找到磁盘上的inode。文件查找是一种典型的正向查找。

　　反向查找：给定分区磁盘号（更确定，则给定分配组号），查找邻近的空闲i-结点。分配新inode就属于这种情况，JFS尽量查找物理上邻近所选分配组的inode（以便，例如,同一子目录的文件其inode都是相邻的）。

　　空闲inode号查找：要分配新的inode盘区，先要找到32个相邻的、未分配给相应inode盘区的inode。当所有已分配的inode都在使用，或当JFS需要给分配组分配inode但以前从未分配过inode时，或当一个分配组中没有空闲inode时，需要分配新的inode盘区。

　　注意动态inode分配的一种微妙效应：相邻inode号在磁盘上未必相邻：inodeN+32可以和inodeN相隔任意远。然而，相隔很远的inode号在磁盘上可以是紧邻的；所以，inodeN+K和inodeN紧邻在理论上是可能的（即使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由structiag_t定义（见jfs_imap.h)。

　　以下为引用的内容：

　　/*

　　*inodeallocationgrouppage(per4096inodesofanAG)

　　*/

　　typedefstruct{

　　int64agstart;/*8:startingblockofag*/

　　int32iagnum;/*4:inodeallocationgroupnumber*/

　　int32inofreefwd;/*4:aginodefreelistforward*/

　　int32inofreeback;/*4:aginodefreelistback*/

　　int32extfreefwd;/*4:aginodeextentfreelistforward*/

　　int32extfreeback;/*4:aginodeextentfreelistback*/

　　int32iagfree;/*4:iagfreelist*/

　　

　　/*summarymap:1bitperinodeextent*/

　　int32inosmap[SMAPSZ];/*16:summapofmapwordsw/freeinodes;

　　*note:thisindicatesfreeandbacked

　　*inodes,iftheextentisnotbackedthe

　　*valuewillbe1.iftheextentis

　　*backedbutallinodesarebeingusedthe

　　*valuewillbe1.iftheextentis

　　*backedbutatleastoneoftheinodesis

　　*freethevaluewillbe0.

　　*/

　　int32extsmap[SMAPSZ];/*16:summapofmapwordsw/freeextents*/

　　int32nfreeinos;/*4:numberoffreeinodes*/

　　int32nfreeexts;/*4:numberoffreeextents*/

　　/*(72)*/

　　uint8pad[1976];/*1976:padto2048bytes*/

　　/*allocationbitmap:1bitperinode(0-free,1-allocated)*/

　　uint32wmap[EXTSPERIAG];/*512:workingallocationmap*/

　　uint32pmap[EXTSPERIAG];/*512:persistentallocationmap*/

　　pxd_tinoext[EXTSPERIAG];/*1024:inodeextentaddresses*/

　　}iag_t;/*(4096)*/

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

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

　　structiaginode_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+树中的键（字节偏移量）。

　　iagkey=((Inodenumber/Inodesperiag)*Inodesperiag)+4096(EQ1)

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

　　iaginodeindex=(Inodenumber)mod(Inodesperiag)(EQ2)

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

　　inodeextentdescriptor=(iaginodeindex)/(Inodeperinodeextent)(EQ3)

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

　　inodeoffset=((iaginodeindex)mod(Inodesperinodeextent)

　　*sizeofdinode)(EQ4)

　　inode分配映射表本身由聚集inode表中文件集的分配映射表inode描述。

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

　　

　　以下为引用的内容：

　　iagkey=((inum/num_inodes_per_iag)*(num_inodes_per_iag))+4096

　　=((9157/4096)*4096)+4096

　　=12288

　　iaginodeindex=inummodnum_inodes_per_iag

　　=(9157mod4096)

　　=965

　　inodeextentdescriptor=iag_inode_index/num_inodes_per_extent

　　=965/32

　　=30

　　inodeoffset=(iag_inode_indexmodnum_inodes_per_extent)

　　*sizeofdinode

　　=(965mod32)*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。

　　注意AG3中的IAG没有任何相应的inode盘区可供分配。所以，这些inode未在AG空闲inode列表中表示。

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