叶子节点

百科 2022-03-03

叶子节点

叶子也就是leaf指在网路结构中某些计算机,它们从比较靠近中心的计算机处接收信号,而不把信号传送至较远的计算机。叶子节点就是树中最底段的节点,叶子节点没有子节点。格式化叶子节点的结构比中间节点的结构稍微複杂一点。为了能够在一个格式化叶子节点中保存多个条目,reiserfs 採用了如图 4 所示的布局结构。

基本介绍

  • 中文名:叶子节点
  • 最大存储的数据:可达 4048 KB
  • 开始:以一个数据块头开始
  • 设计 :从两端向中间伸展的条目头
  • 条目的含义:存储在单个节点中的一个数据容器

节点布局

从图中可以看出,每个格式化叶子节点都以一个数据块头开始,然后是从两端向中间伸展的条目头和条目数据的数组,空闲空间保留在中间,这种设计是为了扩充方便。
所谓条目(item,或称为项)就是可以存储在单个节点中的一个数据容器,我们可以认为条目是由条目头和条目数据体组成的。

结构定义

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 所示。

条目类型

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
下面让我们逐一来了解一下各种条目的存储结构。
STAT 条目
stat 数据(TYPE_STAT_DATA)非常类似于 ext2 中的索引节点,其中保存了诸如档案许可权、MAC(modified、accessed、changed)时间信息等数据。在3.6 版本的 reiserfs 中,stat 数据使用一个stat_data 结构表示,该结构大小为 44 位元组,其定义如清单 7 所示:

结构定义

835 /* Stat Data on disk (reiserfs version of UFS disk inode minus the
836 address blocks) */
837 struct stat_data {
838 __le16 sd_mode; /* file type, permissions */
839 __le16 sd_attrs; /* persistent inode flags */
840 __le32 sd_nlink; /* number of hard links */
841 __le64 sd_size; /* file size */
842 __le32 sd_uid; /* owner */
843 __le32 sd_gid; /* group */
844 __le32 sd_atime; /* time of last access */
845 __le32 sd_mtime; /* time file was last modified */
846 __le32 sd_ctime; /* time inode (stat data) was last changed */
/* (except changes to sd_atime and sd_mtime) */
847 __le32 sd_blocks;
848 union {
849 __le32 sd_rdev;
850 __le32 sd_generation;
851 //__le32 sd_first_direct_byte;
852 /* first byte of file which is stored in a
853 direct item: except that if it equals 1
854 it is a symlink and if it equals
855 ~(__u32)0 there is no direct item. The
856 existence of this field really grates
857 on me. Let's replace it with a macro
858 based on sd_size and our tail
859 suppression policy? */
860 } __attribute__ ((__packed__)) u;
861 } __attribute__ ((__packed__));
862 //
863 // this is 44 bytes long
864 //
stat_data 条目使用的关键字中,offset 和 type 的值总是 0,这样就能确保 stat 数据是相同对象(object-id)中的第一个条目,从而能够加快访问速度。
与 ext2 的 ext2_indoe 结构对比一下就会发现,stat_data 中既没有记录数据块位置的地方,也没有记录删除时间,而这正是我们在 ext2/ext3 中恢复删除档案的基础,因此可以猜测得到,在reiserfs 档案系统中要想恢复已经删除的档案,难度会变得更大。

目录条目

目录条目中记录了目录项信息。目录条目由目录头和目录项数据(即档案或子目录名)组成。如果一个目录中包含的目录项太多,可以扩充到多个目录条目中存储。为了方便管理某个目录中子目录或档案的增减,目录条目也採用了与条目头类似的设计:从两端向中间扩充,其布局结构如图 5 所示。
目录条目存储结构
目录头是一个 reiserfs_de_head 结构,大小为 16 位元组,其定义如清单 8 所示。

结构定义

920 /*
921 Q: How to get key of object pointed to by entry from entry?
922
923 A: Each directory entry has its header. This header has
deh_dir_id and deh_objectid fields, those are key
924 of object, entry points to */
925
926 /* NOT IMPLEMENTED:
927 Directory will someday contain stat data of object */
928
929 struct reiserfs_de_head {
930 __le32 deh_offset; /* third component of the directory entry key */
931 __le32 deh_dir_id; /* objectid of the parent directory of the object,
932 that is referenced by directory entry */
933 __le32 deh_objectid; /* objectid of the object, that is referenced */
/* by directory entry */
934 __le16 deh_location; /* offset of name in the whole item */
935 __le16 deh_state; /* whether 1) entry contains stat data (for future),
936 and 2) whether entry is hidden (unlinked) */
937 } __attribute__ ((__packed__));
reiserfs_de_head 结构中包含了 deh_dir_id 和 deh_objectid fields 这两个栏位,它们就是其父目录关键字中对应的两个栏位。deh_offset 的 7 到 30 位是档案名称的 hash 值,0 到 6 位用来解决 hash 冲突的问题(reiserfs 中可以使用 3 种 hash 函式:tea、rupasov 和 r5,默认为 r5)。档案名称的位置保存在 deh_location 栏位中,而 deh_state 的第 2 位表示该目录条目是否是可见的(该位为 1 则表示该目录条目是可见的,为 0 表示不可见)。档案名称是一个字元串,以空字元结束,按照 8位元组对齐。

条目方式

在 reiserfs 中,档案数据可以通过两种方式进行存取:直接条目(direct item)和间接条目(indirect item)。对于小档案来说,档案数据本身和 stat 数据可以一起存储到叶子节点中,这种条目就称为直接条目。直接条目就採用图 4 所示的存储结构,不过每个条目数据体就是档案数据本身。对于大档案来说,单个叶子节点无法存储下所有数据,因此会将部分数据存储到未格式化数据块中,并通过间接条目中存储的指针来访问这些数据块。未格式化数据块都是整块使用的,最后一个未格式化数据块中可能会遗留一部分剩余空间,大小是由对应条目头的 ih_free_space_reserved 栏位指定的。图 6 给出了间接条目的存储结构。

存储结构

对于预设的 4096位元组的数据块来说,一个间接条目所能存储的数据最大可达 4048 KB(4096*(4096-48)/4 位元组),更大的档案需要使用多个间接条目进行存储,它们之间的顺序是通过关键字中的 offset 进行标识的。
另外,档案末尾不足一个数据块的部分也可以像小档案一样存储到直接条目中,这种技术就称为尾部封装(tail packing)。在这种情况下,存储一个档案至少需要使用一个间接条目和一个直接条目。

2020-03-06 14:07:18