| 词条 | 叶子节点 |
| 释义 | 叶子也就是leaf指在网络结构中某些计算机，它们从比较靠近中心的计算机处接收信号，而不把信号传送至较远的计算机。叶子节点就是树中最底段的节点，叶子节点没有子节点。格式化叶子节点的结构比中间节点的结构稍微复杂一点。为了能够在一个格式化叶子节点中保存多个条目，reiserfs 采用了如图 4 所示的布局结构。 格式化叶子节点的布局从图中可以看出，每个格式化叶子节点都以一个数据块头开始，然后是从两端向中间伸展的条目头和条目数据的数组，空闲空间保留在中间，这种设计是为了扩充方便。 所谓条目（item，或称为项）就是可以存储在单个节点中的一个数据容器，我们可以认为条目是由条目头和条目数据体组成的。 item_head 结构定义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 所示。 reiserfs 支持的条目类型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 所示： stat_data 结构定义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 所示。 reiserfs_de_head 结构定义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）。在这种情况下，存储一个文件至少需要使用一个间接条目和一个直接条目。 |
| 随便看 |
百科全书收录4421916条中文百科知识，基本涵盖了大多数领域的百科知识，是一部内容开放、自由的电子版百科全书。