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

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

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

B+ 树与 ext2/ext3 的超级块比较一下会发现，reiserfs 的超级块中并没有索引节点表的信息，这是由于 reiserfs 并没有使用索引节点表，而是采用了 B+ 树来组织数据（在 reiserfs 的文档中也称为是 S+ 树）。图 2 中给出了一棵典型的 2 阶 B+ 树，其深度为 4。
图 2. 2 阶 B+ 树

一棵 B+ 树有唯一一个根节点，其位置保存在超级块的 root_block 字段中。包含子树的节点都是中间节点（internal node），不包含子树的节点称为叶子节点（leaf node）。按照是否包含 B+ 树本身需要的信息，节点又可以分为两类，一类节点包含 B+ 树所需要的信息（例如指向数据块位置的指针，同时也包括文件数据），称为格式化节点（formatted node）；另外一类只包含文件数据，而不包含格式化信息，称为未格式化节点（unformatted node 或 unfleaf）。因此，所有的中间节点都必须是格式化节点。一个格式化的叶子节点中可以包含多个条目（item，也称为项），所谓条目是一个数据容器，其内容可以保存到一个数据块中，也就是说，一个条目只能隶属于一个数据块，它是节点管理空间的基本单位。
为了方便理解起见，我们可以认为对于 B+ 树来说，一共包含 3 类节点：中间节点（其中保存了对叶子节点的索引信息）、叶子节点（包含一个或多个条目项）和数据节点（仅仅用来存放文件数据）。
熟悉数据结构的读者都会清楚，B+ 树是一棵平衡树，从根节点到达每个叶子节点的深度都是相同的。与 B- 树相比，B+ 树的好处是可以将数据全部保存到叶子节点中，而中间节点中并不存放真正的数据，仅仅用作对叶子节点的索引。为了方便起见，树的深度从叶子节点开始计算，叶子节点的深度为 1，之上的中间节点逐层加 1。在 B+ 树中查找匹配项首先要对关键字进行比较并沿对应指针进行遍历，直至搜索到叶子节点为止；而叶子节点也是按照关键字从小到大的顺序进行排列的。也正是由于这种结构，使得 B+ 树非常适合用来存储文件系统结构。
关键字reiferfs 中采用的关键字包含 4 个部分，形式如下：

1	( directory-id, object-id, offset, type )

这 4 个部分分别表示父目录的 id、本对象的 id、本对象在整个对象（文件）中的偏移量以及类型。关键字的比较就是按照这 4 个部分逐一进行的。读者可能会好奇为什么不简单地采用对象 id 作为关键字。实际上，这种设计是有很多考虑的，采用 directory-id作为关键字的一部分，可以将相同目录中的文件和子目录组织在一起，加快对目录项的存取。offset 的出现是为了支持大文件，一个间接条目（后文中会介绍）最多能指向 (数据块大小-48）/4 个数据块来存放文件数据，在默认的 4KB 数据块中最大只能支持 4048KB 的文件。因此使用 offset 就可以表明该对象在文件中所处的偏移量。type 可以用来区分对象的类型。目目前reiserfs 支持四种类型，TYPE_STAT_DATA、TYPE_INDIRECT 1、TYPE_DIRECT 2、 TYPE_DIRENTRY，解释见后文的条目头部分。
在 3.5 之前的版本中，这 4 部分都是 32 位的整数，这样造成的问题是最大只能支持大约 232=4GB 的文件。从 3.6 版本开始，设计人员将 offset 扩充至 60 位，将 type 压缩至 4 位。这样理论上能够支持的最大文件就达到了 260 字节，但是由于其他一些限制，reiserfs 中可以支持的文件上限是 8TB。正是由于这个原因，reiserfs 中有两个版本的关键字，相关定义如清单 2 所示。
清单2. reiserfs 中与关键字有关的定义

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

363 struct offset_v1 {
364       __le32 k_offset;
365       __le32 k_uniqueness;
366 } __attribute__ ((__packed__));
367
368 struct offset_v2 {
369       __le64 v;
370 } __attribute__ ((__packed__));
371
372 static inline __u16 offset_v2_k_type(const struct offset_v2 *v2)
373 {
374       __u8 type = le64_to_cpu(v2->v) >> 60;
375       return (type <= TYPE_MAXTYPE) ? type : TYPE_ANY;
376 }
377
378 static inline void set_offset_v2_k_type(struct offset_v2 *v2, int type)
379 {
380       v2->v =
381          (v2->v & cpu_to_le64(~0ULL >> 4)) | cpu_to_le64((__u64) type << 60);
382 }
383
384 static inline loff_t offset_v2_k_offset(const struct offset_v2 *v2)
385 {
386       return le64_to_cpu(v2->v) & (~0ULL >> 4);
387 }
388
389 static inline void set_offset_v2_k_offset(struct offset_v2 *v2, loff_t offset)
390 {
391       offset &= (~0ULL >> 4);
392       v2->v = (v2->v & cpu_to_le64(15ULL << 60)) | cpu_to_le64(offset);
393 }
394
395 /* Key of an item determines its location in the S+tree, and
396 is composed of 4 components */
397 struct reiserfs_key {
398       __le32 k_dir_id;       /* packing locality: by default parent
399                                  directory object id */
400       __le32 k_objectid;    /* object identifier */
401       union {
402                struct offset_v1 k_offset_v1;
403                struct offset_v2 k_offset_v2;
404       } __attribute__ ((__packed__)) u;
405 } __attribute__ ((__packed__));
406

尽管结构定义中并没有显式地声明 offset 和 type 分别是 60 位和 4 位长，但是从几个相关函数中可以清楚地看到这一点。

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