Board logo

标题: 如何恢复 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/) Powered by Discuz! 7.0.0