如何恢复 Linux 上删除的文件-reiserfs 文件系统原理（3）

look_w

数据块头在图 2 中我们曾经介绍过，b+ 树中的节点可以分为格式化节点和未格式化节点两种。未格式化节点中保存的全部是文件数据，而格式化节点中包含了 b+ 树本身需要的一些信息。为了与未格式化节点区分开来，每个格式化节点所占用的数据块最开头都使用一个数据块头来表示。数据块头大小为 24 个字节，定义如清单 3 所示。
清单3. block_head 结构定义

1 2 3 4 5 6 7 8 9 10

698 /* Header of a disk block.  More precisely, header of a formatted leaf 699    or internal node, and not the header of an unformatted node. */ 700 struct block_head { 701         __le16 blk_level;       /* Level of a block in the tree. */ 702         __le16 blk_nr_item;     /* Number of keys/items in a block. */ 703         __le16 blk_free_space;  /* Block free space in bytes. */ 704         __le16 blk_reserved; 705         /* dump this in v4/planA */ 706         struct reiserfs_key blk_right_delim_key;   /* kept only for compatibility */ 707 };

block_head 结构中的 blk_level 表示该节点在 B+ 树中的层次，对于叶子节点来说，该值为 1；blk_nr_item 表示这个数据块中条目的个数；blk_free_space 表示这个数据块中的空闲磁盘空间。
格式化节点可以分为中间节点和叶子节点两类，它们所采用的存储结构是不同的。
中间节点中间节点由数据块头、关键字和指针数组构成。中间节点中的关键字和指针数组都是按照从小到大的顺序依次存放的，它们在磁盘上的布局如图 3 所示。
图 3. 中间节点的布局每个关键字就是一个 16 字节的 reiserfs_key 结构，而指针则是一个 disk_child 结构，其大小为 8 个字节，定义如清单 4 所示。
清单4. disk_child 结构定义

1 2 3 4 5 6 7

1086 /* Disk child pointer: The pointer from an internal node of the tree 1087    to a node that is on disk. */ 1088 struct disk_child { 1089         __le32 dc_block_number; /* Disk child's block number. */ 1090         __le16 dc_size;         /* Disk child's used space.   */ 1091         __le16 dc_reserved; 1092 };

其中 dc_block_number 字段是所指向子节点所在的数据块块号，dc_size 表示这个数据块中已用空间的大小。对于一共有 n 个关键字的中间节点来说，第 i 个关键字位于 24+i*16 字节处，对应的指针位于 24+16*n+8*i 字节处。
需要注意的是，对于中间节点来说，数据块头的 blk_nr_item 字段表示的是关键字的个数，而指针数总是比关键字个数多 1，这是由 B+ 树的结构所决定的，小于 Key 0 的关键字可以在 Pointer 0 指针指向的数据块（下一层中间节点或叶子节点）中找到，而介于 Key 0 和 Key 1 之间的关键字则保存在 Pointer 1 指向的数据块中，依此类推。大于Key n的关键字可以在Pointer n+1中找到。
叶子节点格式化叶子节点的结构比中间节点的结构稍微复杂一点。为了能够在一个格式化叶子节点中保存多个条目，reiserfs 采用了如图 4 所示的布局结构。
图 4. 格式化叶子节点的布局从图中可以看出，每个格式化叶子节点都以一个数据块头开始，然后是从两端向中间伸展的条目头和条目数据的数组，空闲空间保留在中间，这种设计是为了扩充方便。
所谓条目（item，或称为项）就是可以存储在单个节点中的一个数据容器，我们可以认为条目是由条目头和条目数据体组成的。
清单5. item_head 结构定义

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

460 /*  Everything in the filesystem is stored as a set of items.  The 461     item head contains the key of the item, its free space (for 462     indirect items) and specifies the location of the item itself 463     within the block.  */ 464 465 struct item_head { 466         /* Everything in the tree is found by searching for it based on 467          * its key.*/ 468         struct reiserfs_key ih_key; 469         union { 470                 /* The free space in the last unformatted node of an 471                    indirect item if this is an indirect item.  This 472                    equals 0xFFFF iff this is a direct item or stat data 473                    item. Note that the key, not this field, is used to 474                    determine the item type, and thus which field this 475                    union contains. */ 476                 __le16 ih_free_space_reserved; 477                 /* Iff this is a directory item, this field equals the 478                    number of directory entries in the directory item. */ 479                 __le16 ih_entry_count; 480         } __attribute__ ((__packed__)) u; 481         __le16 ih_item_len;     /* total size of the item body */ 482         __le16 ih_item_location;        /* an offset to the item body 483                                          * within the block */ 484         __le16 ih_version;      /* 0 for all old items, 2 for new 485                                    ones. Highest bit is set by fsck 486                                    temporary, cleaned after all 487                                    done */ 488 } __attribute__ ((__packed__));

从 item_head 结构定义中可以看出，关键字已经包含在其中了。ih_item_len 和 ih_item_location 分别表示对应条目的数据体的长度和在本块中的偏移量。请注意该结构的第 17、18 个字节是一个联合结构，对于不同类型的条目来说，该值的意义不同：对于 stat 数据条目（TYPE_STAT_DATA）或直接数据条目（TYPE_DIRECT），该值为 15；对于间接数据条目（TYPE_INDIRECT），该值表示最后一个未格式化数据块中的空闲空间；对于目录条目（TYPE_DIRENTRY），该值表示目录条目中目录项的个数。
目前 reiserfs 支持的条目类型有 4 种，它们是依靠关键字中的 type 字段来区分的；而在旧版本的关键字中，则是通过 uniqueness 字段来标识条目类型的，其定义如清单 6 所示。
清单6. reiserfs 支持的条目类型

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

346 //       347 // there are 5 item types currently 348 // 349 #define TYPE_STAT_DATA 0 350 #define TYPE_INDIRECT 1 351 #define TYPE_DIRECT 2 352 #define TYPE_DIRENTRY 3 353 #define TYPE_MAXTYPE 3 354 #define TYPE_ANY 15             // FIXME: comment is required 355   … 509 // 510 // in old version uniqueness field shows key type 511 // 512 #define V1_SD_UNIQUENESS 0 513 #define V1_INDIRECT_UNIQUENESS 0xfffffffe 514 #define V1_DIRECT_UNIQUENESS 0xffffffff 515 #define V1_DIRENTRY_UNIQUENESS 500 516 #define V1_ANY_UNIQUENESS 555   // FIXME: comment is required 517

下面让我们逐一来了解一下各种条目的存储结构。