电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛

标题: 如何恢复 Linux 上删除的文件-reiserfs 文件系统原理（3） [打印本页]

作者: look_w 时间: 2018-5-22 16:05 标题: 如何恢复 Linux 上删除的文件-reiserfs 文件系统原理（3）

数据块头在图 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

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

欢迎光临电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛 (http://bbs.eccn.com/)