如何恢复 Linux 上删除的文件–reiserfs 文件系统的恢复

reiserfs 文件系统所采用的 B+ 树的动态变化特性为恢复删除文件增加了很多困难。本文将逐渐分析在 reiserfs 文件系统中删除文件前后磁盘数据的变化,从而探讨恢复删除文件的方法。

在本系列文章的上一部分中,我们详细介绍了 reiserfs 文件系统在磁盘上的存储结构,以及访问文件系统所使用的 B+ 树和内部数据结构。在本文中,我们将继续讨论 reiserfs 文件系统中如何恢复已删除的文件。

与 ext2/ext3 类似,要想确定能否恢复已删除的文件,必须弄清楚文件系统在删除文件时都执行了哪些操作,磁盘的数据块中保留了哪些相关信息,以及如何从这些信息中恢复出相关数据来。

通过上一部分的介绍,我们大概也能猜测出来,在 reiserfs 文件系统中恢复已删除的文件并不容易,这是由于 reiserfs 所采用的内部数据结构所决定的:它将小文件的数据(以及大文件的部分尾部数据)与 stat 数据一起保存到 B+ 树的叶子节点中。虽然这种设计可以有效地提高空间利用率,但却给数据恢复带来了很多困难。首先,数据在叶子节点中的位置并非是一成不变的,它会随着前后数据的变化而发生移动,这会导致有些数据可能会被覆盖,因此有些数据可能根本就无法恢复。其次,B+ 树本身就是一棵动态变化的树,节点的分裂和合并更大程度地增加了数据恢复的难度。

对象 id 的分配和管理

在本系列文章的上一部分中,我们介绍过超级块保存在一个单独的数据块上。实际上,超级块信息的存储并不需要占用一个完整的数据块,这个数据块中空闲的部分就用来解决对象 id 的冲突和重用问题。

我们知道,在 reiserfs 文件系统中,对象 id 就像是 ext2/ext3 文件系统中的索引节点号一样,是文件的唯一标志;而在关键字中加入目录 id 就间接反应了文件系统中的目录层次关系。为了确保文件对象 id 的唯一性,必须随时能够了解可用 id 的范围。为此,reiserfs 采用了一个如下格式的二元组的数组来保存已经使用的 id 范围:

[(first used object-id, first unused object-id)]

 

 

二元组的第一项表示第一个已经使用的 object-id 值,第二项表示下一个未用的最小 object-id 值。第一个二元组的第一项总是 1,并且其中每个元素都是从小到大的顺序存放的。例如,下面是一个系统使用过程中的例子:

1, 6, 16, 17, 38, 47, 48, 56

 

 

我们可以看出,现在已经使用的对象 id 包括:1-5、16、38-46、48-55,而其他的对象 id 都是可用的。此时如果删除对象 id 为 41 的文件,则上面的数组就会变为:

1, 6, 16, 17, 38, 41, 42, 47, 48, 56

恢复单个删除文件试验

 

下面让我们先从一个简单的例子入手,了解磁盘数据在 reiserfs 文件系统删除文件前后的变化,并探讨能否以及如何恢复已删除的文件。

本文后面所介绍的方法大部分都需要对磁盘进行扫描,这对于在 reiserfs 文件系统中恢复已删除文件是必不可少的。为了简单起见,我们新建立了一个只有 128MB 大小的分区,并使用这个分区来进行后续实验(笔者系统中这个分区是 /dev/sda4,如果您的系统配置与此不同,请自行修改文中使用的命令和脚本)。

为了保证实验结果不会受到磁盘上历史数据的影响,我们需要使用一个全新的分区来创建文件系统。为了确保这一点,每次在创建文件系统之前,我们首先将该分区上的数据全部清 0。命令如清单 1 所示。
清单1. 创建全新的测试文件系统

                
[root@vmfc8 reiserfs]# dd if=/dev/zero of=/dev/sda4
[root@vmfc8 reiserfs]# echo y | mkreiserfs /dev/sda4

 

 

小文件

reiserfs 最大的优势就在于对小文件的存取性能非常高,下面让我们先来了解一下一个小文件的实际存储情况,以及在删除文件前后,磁盘上数据块的变化。

为了更加清晰地了解磁盘数据在删除文件前后到底是如何变化的,我们需要抓取并比较删除文件前后数据块的变化。debugreiserfs 命令可以提供一些帮助,此处我们使用 -d 选项打印 B+ 树中内部节点所使用的数据块信息。抓取删除文件前后数据块的命令如清单 2 所示。
清单2. 删除小文件前后磁盘数据的变化

                
[root@vmfc8 smallfiles]# cat -n cmds.small.sh 
     1  #!/bin/bash
     2
     3  umount /tmp/test
     4  dd if=/dev/zero of=/dev/sda4
     5  echo y | mkreiserfs /dev/sda4
     6  mount /dev/sda4 /tmp/test
     7  echo "hello world" > /tmp/test/helloworld
     8  ls -l /tmp/test/helloworld
     9  cat /tmp/test/helloworld
    10  umount /tmp/test
    11  export rootblock=`debugreiserfs -d /dev/sda4 2>/dev/null \
          | grep "Root block:" | cut -d" " -f3`
    12  export blocksize=`debugreiserfs -d /dev/sda4 2>/dev/null \
          | grep "Blocksize:" | cut -d" " -f2`
    13  debugreiserfs -d /dev/sda4 2>/dev/null > smallfile.-d.created
    14  dd if=/dev/sda4 of=smallfile.block.${rootblock}.created bs=${blocksize} \
          count=1 skip=${rootblock}
    15  hexdump -C smallfile.block.${rootblock}.created > \
          smallfile.block.${rootblock}.created.hex
    16
    17  mount /dev/sda4 /tmp/test
    18  rm -f /tmp/test/helloworld
    19  umount /tmp/test
    20  export rootblock=`debugreiserfs -d /dev/sda4 2>/dev/null \
          | grep "Root block:" | cut -d" " -f3`
    21  export blocksize=`debugreiserfs -d /dev/sda4 2>/dev/null \
          | grep "Blocksize:" | cut -d" " -f2`
    22  debugreiserfs -d /dev/sda4 2>/dev/null > smallfile.-d.deleted
    23  dd if=/dev/sda4 of=smallfile.block.${rootblock}.deleted bs=${blocksize} \
          count=1 skip=${rootblock}
    24  hexdump -C smallfile.block.${rootblock}.deleted \
          > smallfile.block.${rootblock}.deleted.hex
[root@vmfc8 smallfiles]# sh cmds.small.sh

 

 

在清单 2 中,我们首先按照前面介绍的方法清空整个分区,并创建一个全新的 reiserfs 文件系统;然后在这个文件系统上创建了一个大小为 12 个字节(包括最后一个换行字符)的测试文件 helloworld。在删除文件前后,我们需要抓取相关磁盘块中的数据。由于整个文件系统中只有这样一个小文件,整个 B+ 树只有一个根节点(同时也是叶子节点),所有数据全部保存在这个节点中。同时为了确保文件系统的变化已经同步到磁盘上,在抓取数据块中的数据之前,都要首先将文件系统卸载掉。最后,为了方便比较,我们使用 hexdump 命令对数据块的内容进行处理,忽略掉其中的无效数据(连续全零部分),-C 参数可以指定同时以十六进制和 ASCII 字符的形式输出结果。

对于这样一个块大小为4096B的全新的 reiserfs 文件系统来说,B+ 树的根节点总是从第一个非日志空闲数据块(即 8211)开始的。图 1 中给出了删除文件前后根节点的对比结果。
图1. 删除小文件前后根节点中数据的对比
删除小文件前后根节点中数据的对比

仔细分析根节点在删除小文件前后的变化会发现,主要区别包括:

  • 数据块头中表示条目个数的字段从 6 变成 4,减少的两项分别是所删除文件对应的 STAT 条目和直接数据条目。
  • 在条目头数组部分中,以上两项的实际内容也发生了很大变化:ih_version(最后 16 位)由 1 变成了 0,表示删除文件之后关键字写入时使用的格式变成了旧的格式,其中 directory-id 部分为 0xffffffff,offset 和 type 也都已经变得无效;条目数据也发生了变化,此时变成了一个 4 字节的数字,值为 2(实际上是该文件父目录的 directory-id 值)。
  • 所删除文件所在的目录(在这个例子中就是根目录)的目录数据条目部分,减少了所删除部分对应的目录项(0x0fa4 – 0x0fb3)以及对应的目录头(0x0f94 – 0x0fa3),共 32 个字节。
  • 目录的其他目录数据条目部分向内收缩,挤压掉空闲出来的 32 字节。
  • 0x0ee8 至 0x0f07 部分由于原有数据向下收缩而出现空缺,补充 32 字节数据。
  • 0x0ecc 至 0x0edd 这 16 个字节是所删除文件数据占用空间(实际数据只有 12 个字节,但是在磁盘上会按照 8 字节对齐),在删除文件前后并未发生变化,然而删除文件之后却没有合适的指针来引用这部分数据了。
  • 其他数据的变化包括文件/目录的 MAC 时间的变化,标明数据位置的对应字段的变化等。

从上面这些差异中可以看出,对于小文件来说,在被删除之后,尽管文件数据依然保存在磁盘上,但是却很难恢复出来了,原因在于:

  • 包含文件名的目录项所使用的磁盘空间已经被覆盖,文件名是根本无从恢复的。
  • 文件的 STAT 数据遭到了破坏,中间插入了无效数据。
  • 尽管文件数据在磁盘上保持未变,但却没有合适的指针来标明文件数据的位置和大小。

另外,由于 B+ 树的动态重构特性,在一次删除多个文件时,如果引起了 B+ 树的重构,那么磁盘上的数据就存在被覆盖的可能,这更是增大了数据恢复的难度。

大文件

在前文中已经介绍过,间接条目在叶子节点中存储的是指向实际数据块位置的指针,真正的数据保存在未格式化数据块中;如果启用了尾部封装特性,如果文件末尾的数据很小,也会一起封装并保存到叶子节点中。

下面让我们来比较一下删除大文件前后磁盘数据的变化,所执行的命令如清单 3 所示。
清单3. 删除大文件前后磁盘数据的变化

                
[root@vmfc8 bigfiles]# cat -n cmds.big.sh 
     1  #!/bin/bash
     2
     3  umount /tmp/test
     4  dd if=/dev/zero of=/dev/sda4
     5  echo y | mkreiserfs /dev/sda4
     6  mount /dev/sda4 /tmp/test
     7  ./createfile.sh 37 testfile.37K
     8  cp testfile.37K /tmp/test/testfile.37K
     9  ls -li /tmp/test/testfile.37K
    10  umount /tmp/test
    11  export rootblock=`debugreiserfs -d /dev/sda4 2>/dev/null \
          | grep "Root block:" | cut -d" " -f3`
    12  export blocksize=`debugreiserfs -d /dev/sda4 2>/dev/null \
          | grep "Blocksize:" | cut -d" " -f2`
    13  debugreiserfs -d /dev/sda4 2>/dev/null > bigfile.-d.created
    14  dd if=/dev/sda4 of=bigfile.block.${rootblock}.created \
          bs=${blocksize} count=1 skip=${rootblock}
    15  hexdump -C bigfile.block.${rootblock}.created \
          > bigfile.block.${rootblock}.created.hex
    16
    17  mount /dev/sda4 /tmp/test
    18  rm -f /tmp/test/testfile.37K
    19  umount /tmp/test
    20  export rootblock=`debugreiserfs -d /dev/sda4 2>/dev/null \
          | grep "Root block:" | cut -d" " -f3`
    21  export blocksize=`debugreiserfs -d /dev/sda4 2>/dev/null \
          | grep "Blocksize:" | cut -d" " -f2`
    22  debugreiserfs -d /dev/sda4 2>/dev/null > bigfile.-d.deleted
    23  dd if=/dev/sda4 of=bigfile.block.${rootblock}.deleted \
          bs=${blocksize} count=1 skip=${rootblock}
    24  hexdump -C bigfile.block.${rootblock}.deleted > \
          bigfile.block.${rootblock}.deleted.hex
[root@vmfc8 bigfiles]# sh cmds.big.sh

 

 

清单 3 中执行的命令与对小文件的操作基本上是类似的,不同之处在于我们创建了一个大小为 37KB 的文件作为测试文件,这个文件在磁盘上需要占用 10 个未格式化数据块进行存储。查看 debugreiserfs -d 的输出结果可以看出,这 10 个数据块分别是 34127 以及从 8212 开始的 10 个数据块。
图 2. 删除大文件前后根节点中数据的对比
删除大文件前后根节点中数据的对比

对比图2 与图 1 中的结果会发现,删除大文件和小文件的结果非常类似,不同之处在于对于小文件来说,文件数据部分存储的是真正的数据,而对于大文件来说,存储的则是真正保存数据的数据块位置。另外,在填充由于目录条目数据收缩而产生的空间时,这次破坏的不是 STAT 条目数据,而是间接条目数据。

不过,文件的数据本身并未产生任何变化,这可以通过清单 4 所示的方法进行验证。
清单4. 验证大文件的数据在删除文件前后是否发生变化

                
[root@vmfc8 bigfiles]# cat -n cmds.recoverbig.sh 
     1  #!/bin/bash
     2
     3  mkdir recoverbig
     4  cd recoverbig
     5  for block in 34127 8212 8213 8214 8215 8216 8217 8218 8219 8220
     6  do
     7    dd if=/dev/sda4 bs=4096 count=1 skip=$block >> recover.blocks
     8  done
     9
    10  dd if=recover.blocks of=testfile.37K.recover bs=37888 count=1
    11
    12  diff testfile.37K.recover ../testfile.37K
    13  cd ..
[root@vmfc8 bigfiles]# sh cmds.recoverbig.sh

 

 

结果表明,通过前面获得的数据块号恢复出来的文件与原有文件是完全相同的。

对于更大的文件(超过 4048 KB)来说,会采用多个间接条目来保存存储实际数据的位置,它们之间的先后顺序是通过关键字中的 offset 进行标识的。读者可以对以上脚本自行修改,查看删除更大文件前后磁盘数据的变化。

文件洞

与 ext2/ext3 一样,带有文件洞的文件在 reiserfs 文件系统中的存储也与其他文件有所不同,下面让我们来看一个实际的例子。
清单5. 删除带有文件洞的文件前后磁盘数据的变化

                
[root@vmfc8 hole]# cat -n cmds.hole.sh 
     1  #!/bin/bash
     2
     3  umount /tmp/test
     4  dd if=/dev/zero of=/dev/sda4
     5  echo y | mkreiserfs /dev/sda4
     6  mount /dev/sda4 /tmp/test
     7  echo -n "X" | dd of=/tmp/test/hole bs=1024 seek=7
     8  ls -li /tmp/test/hole
     9  umount /tmp/test
    10  export rootblock=`debugreiserfs -d /dev/sda4 2>/dev/null \
          | grep "Root block:" | cut -d" " -f3`
    11  export blocksize=`debugreiserfs -d /dev/sda4 2>/dev/null \
          | grep "Blocksize:" | cut -d" " -f2`
    12  debugreiserfs -d /dev/sda4 2>/dev/null > holefile.-d.created
    13  dd if=/dev/sda4 of=holefile.block.${rootblock}.created \
          bs=${blocksize} count=1 skip=${rootblock}
    14  hexdump -C holefile.block.${rootblock}.created \
          > holefile.block.${rootblock}.created.hex
    15
    16  mount /dev/sda4 /tmp/test
    17  rm -f /tmp/test/hole
    18  umount /tmp/test
    19  export rootblock=`debugreiserfs -d /dev/sda4 2>/dev/null \
          | grep "Root block:" | cut -d" " -f3`
    20  export blocksize=`debugreiserfs -d /dev/sda4 2>/dev/null \
          | grep "Blocksize:" | cut -d" " -f2`
    21  debugreiserfs -d /dev/sda4 2>/dev/null > holefile.-d.deleted
    22  dd if=/dev/sda4 of=holefile.block.${rootblock}.deleted \
          bs=${blocksize} count=1 skip=${rootblock}
    23  hexdump -C holefile.block.${rootblock}.deleted \
          > holefile.block.${rootblock}.deleted.hex
[root@vmfc8 hole]# sh cmds.hole.sh
[root@vmfc8 hole]# tail -n 10  holefile.-d.created
-------------------------------------------------------------------------------
|  4|2 4 0x0 SD (0), len 44, location 3812 entry count 65535, fsck need 0, format new|
(NEW SD), mode -rw-r--r--, size 7169, nlink 1, mtime 22/2008 01:16:38 blocks 8, uid 0
-------------------------------------------------------------------------------
|  5|2 4 0x1 IND (1), len 8, location 3804 entry count 0, fsck need 0, format new|
2 pointers
[ 0 34127]
===================================================================
The internal reiserfs tree has:
        0 internal + 1 leaves + 1 unformatted nodes = 2 blocks

 

 

对于这个文件来说,它的实际数据只有一个字符,即第 7169 个字符是一个 X,其他部分均为 0。debugreiserfs 的结果显示这个文件在磁盘上总共占用两个数据块,分别是 0 和 34127。实际上,我们知道前 64KB 数据是保留的,因此此处的 0 就意味着该块数据全部为 0。

在删除文件之后,非空部分的数据也不会发生任何变化,清单 6 中的结果充分证明了这一点。
清单6. 带有文件洞的文件中的非空部分在删除文件前后不会发生任何变化

                
[root@vmfc8 hole]# dd if=/dev/sda4 bs=4096 count=1 skip=34127 | hexdump -C
00000000  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
*
00000c00  58 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |X...............|
00000c10  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
*
00001000

 

 

目录

目录的删除与普通文件类似,不同之处在于需要先将目录中的所有内容(包括文件和子目录)删除,然后才会删除该目录。感兴趣的读者可以使用本文下载部分中提供的脚本自行分析删除目录前后磁盘数据块的变化。

 


reiserfs 文件系统中恢复删除文件方法

 

到目前为止,一切看似都非常令人失望:由于访问文件所需要的信息在删除文件时遭到了不同程度的破坏,删除文件之后,要想从磁盘上恢复出文件来就变得非常困难了。但是是否就没有任何方法能够对文件提供帮助呢?实际上,尽管不能确保完全恢复所有的文件,但是依然还有一些方法能够为恢复删除文件提供一些辅助的。

恢复方法1:提前记录存储文件数据的位置

第一种方法是像 ext2/ext3 那样,在删除文件之前,提前记录下存储数据的数据块的位置。有关这个问题的详细介绍请参看本系列文章的第 4 部分。清单 7 给出了一个实际的例子。
清单7. 通过记录保存文件的数据块位置来恢复文件

                
[root@vmfc8 reiserfs]# export LD_PRELOAD=/usr/local/lib/libundel.so
[root@vmfc8 reiserfs]# ./createfile.sh 1 /tmp/test/testfile.01K
[root@vmfc8 reiserfs]# ./createfile.sh 35 /tmp/test/testfile.35K
[root@vmfc8 reiserfs]# ls -li /tmp/test/testfile.*
 89 -rw-r--r-- 1 root root  1024 2008-02-23 05:32 /tmp/test/testfile.01K
107 -rw-r--r-- 1 root root 12298 2008-02-23 05:33 /tmp/test/testfile.12K
106 -rw-r--r-- 1 root root 35840 2008-02-23 05:33 /tmp/test/testfile.35K
[root@vmfc8 reiserfs]# rm -f /tmp/test/testfile.01K /tmp/test/testfile.35K
[root@vmfc8 reiserfs]# cat /var/e2undel/e2undel 
8,4::89::1024::4096::(0-0):0-0::/tmp/test/testfile.01K
8,4::106::35840::4096::(0-8):8658-8666::/tmp/test/testfile.35K

 

 

利用在 /var/e2undel/e2undel 文件中记录下来的数据块位置信息,就可以顺利地从磁盘上恢复出文件数据来。

不过需要注意的是,这种方法并不适用于小文件。在清单 7 中,我们可以看到对于 1KB 的文件来说,并没有记录下正确的块号位置。实际上,由于小文件都已经被封装到了叶子节点中,并不会占用一个单独的数据块,因此仅仅记录数据块号是并不足够的。另外,如果启用尾部封装特性,大文件尾部数据也可能会被保存到叶子节点中,在增删文件时可能会被覆盖,从而导致数据无法完全恢复。幸运的是,reiserfs 也认识到了这个问题,可以在挂载文件系统时指定 notail 参数来禁用尾部封装特性,这样尽管会稍微浪费一点磁盘空间,但却可以改善文件存取速度,对于数据恢复来说也大有好处。

恢复方法 2:正文匹配

当然,对于文本文件来说,我们也可以像 ext2/ext3 那样使用 grep 工具在磁盘上进行全文搜索,从而定位数据位置,进而尽可能地恢复数据。不过,尽管 reiserfs 也会尽量使用连续的数据块来存放数据,但是却不能保证所有的数据块都是连续的。由于中间节点和尾部封装特性的存在,这种方法对于大文件来说,效果会比 ext2/ext3 文件系统略差。

恢复方法 3:重新构造 B+ 树

最后一种方法是通过重新构造 reiserfs 的 B+ 树来恢复文件,这是 reiserfs 文件系统所特有的一种方法,充分利用了 B+ 树的特性:叶子节点和中间节点都具有特定的格式,而未格式化数据块中的数据则完全取决于文件本身,在文件系统层次看来并没有特定的格式。另外,叶子节点和中间节点中的数据项也都是按照关键字从小到大的顺序存放的,这就为猜测数据项是否有效提供了一个依据。实际上,在 reiserfs 文件系统中重新构造 B+ 树最初的目的与 ext2/ext3 中使用的 fsck 工具一样,是为了检查并修复文件系统的一致性问题。它的操作模式就是不断进行猜测:如果数据块中的数据符合叶子节点或中间节点的格式要求,就假定这是一个叶子节点或中间节点;如果其中部分数据存在问题,可以按照合理的推测来修正这些问题。获得叶子节点的详细列表之后,就可以通过重新构造 B+ 来重构文件系统了。

下面让我们首先来看一个具体的例子,了解一下如何通过重构 B+ 树的方法来恢复删除文件。命令如清单 8 所示。

清单8. 通过重构 B+ 树恢复删除文件

[root@vmfc8 nosync]# sh cmds.nosync.sh

[root@vmfc8 nosync]# umount /tmp/test; sync; echo Yes \
  | reiserfsck --rebuild-tree -S -l undelete.log  /dev/sda4 ; \
  mount /dev/sda4 /tmp/test ; ls -l /tmp/test
reiserfsck 3.6.19 (2003 www.namesys.com)
*************************************************************
** Do not  run  the  program  with  --rebuild-tree  unless **
** something is broken and MAKE A BACKUP  before using it. **
** If you have bad sectors on a drive  it is usually a bad **
** idea to continue using it. Then you probably should get **
** a working hard drive, copy the file system from the bad **
** drive  to the good one -- dd_rescue is  a good tool for **
** that -- and only then run this program.                 **
** If you are using the latest reiserfsprogs and  it fails **
** please  email bug reports to reiserfs-list@namesys.com, **
** providing  as  much  information  as  possible --  your **
** hardware,  kernel,  patches,  settings,  all reiserfsck **
** messages  (including version),  the reiserfsck logfile, **
** check  the  syslog file  for  any  related information. **
** If you would like advice on using this program, support **
** is available  for $25 at  www.namesys.com/support.html. **
*************************************************************
Will rebuild the filesystem (/dev/sda4) tree
Will put log info to 'undelete.log'
Do you want to run this program?[N/Yes] (note need to type Yes if you do):Replaying 
journal..
Reiserfs journal '/dev/sda4' in blocks [18..8211]: 0 transactions replayed
###########
reiserfsck --rebuild-tree started at Fri Feb 29 10:42:56 2008
###########
Pass 0:
The whole partition (34128 blocks) is to be scanned
Skipping 8212 blocks (super block, journal, bitmaps) 25916 blocks will be read
0%....20%....40%....60%....80%....100%                         left 0, 518 /sec
        "r5" hash is selected
Flushing..finished
        Read blocks (but not data blocks) 25916
                Leaves among those 10
                Objectids found 67
Pass 1 (will try to insert 10 leaves):
Looking for allocable blocks .. finished
0%....20%....40%....60%....80%....100%                           left 0, 0 /sec
Flushing..finished
        10 leaves read
                7 inserted
                3 not inserted
        non-unique pointers in indirect items (zeroed) 5
Pass 2:
0%....20%....40%....60%....80%....100%                           left 0, 0 /sec
Flushing..finished
        Leaves inserted item by item 3
Pass 3 (semantic):
Flushing..finished                                      
        Files found: 14
        Directories found: 7
        Names pointing to nowhere (removed): 22
Pass 3a (looking for lost dir/files):
Looking for lost directories:
Looking for lost files:0 /sec
Flushing..finished 21, 0 /sec
        Objects without names 21
        Files linked to /lost+found 21
Pass 4 - finished       done 7, 0 /sec
        Deleted unreachable items 1
Flushing..finished
Syncing..finished
###########
reiserfsck finished at Fri Feb 29 10:43:47 2008
###########
total 1
drwx------ 2 root root 552 2008-02-29 10:43 lost+found
drwxr-xr-x 5 root root 208 2008-02-29 10:36 reiserfsprogs-3.6.19

 

 

清单 8 中使用的脚本 cmds.nosync 可以从本文下载部分中获得。该脚本可以用来帮助分析在删除文件前后磁盘数据的变化,从而帮助更好地理解 reiserfs 文件系统的实现机制。下载部分同时还提供了 reiserfsprogs-3.6.19.tar.gz 文件,其中包含了 debugreiserfs、reiserfsck 等工具的源代码,本文使用它作为测试文件使用,请将其与 cmds.nosync 脚本中放到相同的目录中。cmds.nosync 脚本执行的操作如下:

  • 清空测试分区 /dev/sda4
  • 在该分区上创建 reiserfs 文件系统
  • 解压 reiserfsprogs-3.6.19.tar.gz 包
  • 将展开后的文件逐一拷贝到测试文件系统中,每拷一个文件就抓取磁盘数据的变化
  • 逐一删除测试文件系统中的数据,每删除一个文件就抓取磁盘数据的变化

展开后的代码包一共包含 101 个文件和子目录,因此整个过程一共会抓取 204次磁盘数据的变化(另外两次是在做好文件系统以及将其挂载之后抓取的)。

reiserfsck 命令的 –rebuild-tree 参数用来重新构造 B+ 树,此时一般都会使用 -S 参数搜索整个硬盘分区,否则只会搜索其中标记为已用部分。

当 reiserfsck 完成磁盘扫描并重新构造好 B+ 树之后,在测试分区上就出现了两个目录,其中 reiserfsprogs-3.6.19 中存放的是完整恢复出来的文件;而对于那些自己能够成功恢复而父目录却无法恢复的文件和目录,则会被保存到 lost+found 目录中,其中的文件和目录名字都形如 XX_YY 的格式,其中 XX 是其目录的 directory-id 值,YY 是该文件或目录的 object-id 值。

与前面我们自行删除文件的实验对比一下,很多人都会产生疑惑:既然在删除文件时,访问文件所需要的信息可能会被覆盖而导致文件无法访问,为什么重新构造 B+ 树的方法却能够成功恢复数据呢?

实际上,这是利用了 reiserfs 文件系统实现上提供的一点便利:B+ 树是一棵动态的平衡树,在删除文件时,如果满足一定条件(例如每个节点中的项数小于指定值), B+ 树就会发生节点合并(即将两个节点合并成一个节点,并将另外一个节点从 B+ 树中剔除出去)。此时,reiserfs 并不会将所剔除出去的节点中的信息完全清空,而是仅仅将数据块头中的条目数(blk_nr_item 字段)标记为 0 而已。因此,该节点中所保存的有关文件的信息甚至文件数据本身就能完整地保存下来。

例如,reiserfsprogs.spec 是一个能够通过重新构造 B+ 树完整恢复出来的文件,在删除这个文件时,B+ 树也刚好发生了节点合并的情况,如图 3 所示。
图3. 删除 reiserfsprogs.spec 文件时 B+ 树中节点的变化
删除 reiserfsprogs.spec 文件时 B+ 树中节点的变化

在删除 reiserfsprogs.spec 文件之前,整个 B+ 树由一个中间节点(32770)和 4 个叶子节点(32772、32774,32776,32778)构成。在删除 reiserfsprogs.spec 文件之后,32774 块中的数据被合并到 32772 块中来,然后 32774 被从整个 B+ 树中剔除出去。正如前面介绍的一样,除了数据块头中有效项数被设置为 0 之外,32774 块中其他数据都被保存了下来(当然,如果所剔除的叶子节点中包含所删除条目,对应的数据也会发生变化)。

然而,查看删除 reiserfsprogs.spec 文件前后 32772 和 32774 块中的数据会发现,reiserfsprogs.spec 文件所对应的条目也被覆盖掉了,但是为什么最终这个文件能够被恢复出来呢?

实际上,reiserfsprogs.spec 文件最初是保存在 8211 块的叶子节点中的,这个叶子节点在删除 Makefile.am 文件时被从 B+ 树中剔除了出去,与 reiserfsprogs.spec 文件有关的信息也在这个块中得以保存下来,因此最终才能够被成功恢复出来,查看 0161.FS.00.-d.__reiserfsprogs-3.6.19__lib.rmdir 和 0162.FS.00.-d.__reiserfsprogs-3.6.19__Makefile.am.unlink 这两个文件很容易就能够明白这一点。

重新构造 B+ 树的过程是一个典型的不断猜测和尝试的过程,其目标是首先从磁盘上寻找到所有的叶子节点和中间节点,然后利用这些节点和残留的 B+ 树构造出一个尽量完整的 B+ 树来,从而达到恢复文件的目的。因此,整个过程中对于叶子节点或中间节点的判断非常重要,这是恢复数据多少的关键。对于这个问题,reiserfs 的解决方法是就将数据块当作是一个叶子节点或中间节点,按照相应数据结构的定义对数据块中的数据进行访问,检查它是否符合预定的一些规则。例如,对于叶子节点来说,至少需要满足以下条件:

  • 有一个数据块头,其中的 blk_level 字段值为 1。
  • 每个条目的起点都是前一个条目的终点。
  • 条目项个数不少于数据块头中 blk_nr_item 字段的值。
  • 空闲空间不大于数据块头中 blk_free_space 字段的值。

B+ 树的重新构造包括以下 5 个连续的阶段:

    1. pass_0:扫描整个磁盘分区,从中找到可能的叶子节点,并修正叶子节点中存在的问题。
    2. pass_1:尝试将上一步骤中找到的叶子节点插入到现有的 B+ 树中。
    3. pass_2:将尚未插入 B+ 树中的叶子节点中的所有条目单独插入 B+ 树中。
    4. pass_3:在语义层重新构造整个文件系统,确保文件系统存在根目录和 lost+found 项,并按照文件系统的语义将父目录不存在的项放入 lost+found 目录中,并重新构造根目录和 lost+found 目录所使用的条目。
    5. pass_4:按照关键字进行遍历,剔除不可访问项,最后更新文件系统至一致状态。

在以上 5 个阶段中,只要确定某个条目可能存在问题,就会将其从最终的 B+ 树中删除,从而最大程度地确保最终文件系统的可用性。有问题的条目信息可以在日志文件中看到(reiserfsck 命令的 -l 参数指定),如清单 9 所示。

清单9. 重新构造 B+ 树的问题日志

[root@vmfc8 nosync]# cat undelete.log

####### Pass 0 #######

66 directory entries were hashed with “r5” hash.

####### Pass 1 #######

####### Pass 2 #######

####### Pass 3 #########

rebuild_semantic_pass: The entry [4 58] (“lib”) in directory [2 4] points to nowhere

– is removed

rebuild_semantic_pass: The entry [4 72] (“NEWS”) in directory [2 4] points to nowhere

– is removed

rebuild_semantic_pass: The entry [74 76] (“do_balan.c”) in directory [4 74] points to

nowhere – is removed

vpf-10650: The directory [4 74] has the wrong size in the StatData (464)

– corrected to (48)

rebuild_semantic_pass: The entry [4 65] (“missing”) in directory [2 4] points to

nowhere – is removed

vpf-10650: The directory [2 4] has the wrong size in the StatData (432)

– corrected to (208)

vpf-10650: The directory [1 2] has the wrong size in the StatData (112)

– corrected to (152)

####### Pass 3a (lost+found pass) #########

仔细对比一下恢复出来的文件与源文件就会发现,使用重新构造 B+ 树的方法并不能全部恢复出所有的数据。实际上,即使恢复出来的数据也不能确保是完全正确的。对于我们这个例子来说,101 个文件和目录中只有 18 个文件全部完整地恢复出来了;所恢复出来的数据总量还不足原有文件的30%,这是由于我们测试时使用文件的模式所决定的:我们是按照目录层次结构逐一创建目录并在其中添加文件的,删除文件时也是如此,这样 B+ 树产生分裂或合并的情况并不是很多。而在正常的使用情况下,在目录下添加文件或创建子目录会变得非常随机,B+ 树不会像现在一样精简,因此在删除文件时由于节点合并而剔除出来的叶子节点中所保存下来的正确信息也就越多,最终通过使用重新构造 B+ 树所能恢复出来的文件也就越多。实际上,在正常使用的文件系统中,可能恢复出多达 80% 以上的数据。不过,究竟哪些文件可以恢复出来,恢复出来的数据是否绝对正确,这种方法并不能提供保证。

 


小结

 

reiserfs 对文件所采用的独特的存储和访问模式可以极大地提高小文件的存取性能,并且能够有效地提供磁盘空间的利用率;但却为删除文件的恢复带来了很大的困难:叶子节点中由于增删文件而引起的空间收缩或扩展可能会导致存取文件所需要的关键信息被意外覆盖,从而导致文件数据无法正常恢复。

重新构造 B+ 树的方法充分利用 reiserfs 中 B+ 树实现的一些特性,基于一些合理的规则可以不断“猜测” B+ 树中正常的数据应该有的状态,这不但可以解决检查并修复文件系统一致性的问题,还可以将由于被从 B+ 树中剔除出去而幸运地保留下一些正确信息的叶子节点中所保存的文件信息正确地恢复出来。不过这种方法并不能为恢复删除文件提供任何保证,结合使用提前记录存储数据块位置以及全文匹配的方法能够恢复出更多数据。

实际上,reiserfs 中利用 fsck 来重新构造 B+ 树的设计也招致了很多批评。批评者认为,如果文件系统已经严重损坏了,此时 B+ 树就没有多少用处了,此时重新构造 B+ 树可能会导致现有的文件被破坏得更加严重,或者引入一些乱七八糟的数据项(文件或目录)。但是这种行为并非是正常 fsck 操作的一部分,也不是常见的文件系统检查的目的,使用时需要管理员显式地确认,但是对于恢复意外删除的文件来说却大有裨益。然而需要注意的是,在 reiserfs 的分区上不能存储 reiserfs 的镜像文件(例如磁盘备份或模拟器使用的磁盘镜像文件),除非对这些文件进行进一步处理,比如压缩或加密,否则会造成文件系统的误导,将这些镜像文件也会当作文件系统的一部分,导致重构出来的文件系统变得没有意义。

 


参考资料

 

  • Linux 内核源代码中包含了 reiserfs 文件系统的详细实现。
  • reiserfsprogs 包中包含了 debugreiserfs 和 reiserfsck 的实现
  • wikipedia 上有关 reiserfs 的条目介绍了有关 reiserfs 的一些特性
  • 有关如何在其他文件系统上恢复已删除文件的介绍,请参考本系列文章的其他部分

下载

 

描述 名字 大小 下载方法
reiserfsprogs 的源码包 reiserfsprogs-3.6.19.tar.gz 398KB HTTP
模拟删除文件操作脚本 cmds.nosync.sh 5KB HTTP
文中使用的其他脚本:cmds.small.sh、cmds.big.sh、cmds.hole.sh otherscripts.rar 2KB HTTP

作者简介

 

冯锐,软件工程师,目前在 IBM 开发中心从事 AIX 性能测试方面的工作。您可以通过 fengrui@cn.ibm.com 与他联系。

 

丁成,软件工程师,目前在 IBM 开发中心从事 AIX 性能测试方面的工作,您可以通过 dingc@cn.ibm.com 与他联系。

 

出处:http://www.ibm.com/developerworks/cn/linux/l-cn-filesrc7/index.html

 

发表评论