要想恢复误删除的文件，必须清楚数据在磁盘上究竟是如何存储的，以及如何定位并恢复数据。本文从数据恢复的角度，着重介绍了 ext2 文件系统中使用的一些基本概念和重要数据结构，并通过几个实例介绍了如何手工恢复已经删除的文件。最后针对 ext2 现有实现存在的大文件无法正常恢复的问题，通过修改内核中的实现，给出了一种解决方案。
对于很多 Linux 的用户来说，可能有一个问题一直都非常头疼：对于那些不小心删除的数据来说，怎样才能恢复出来呢？大家知道，在 Windows 系统上，回收站中保存了最近使用资源管理器时删除的文件。即便是对于那些在命令行中删除的文件来说，也有很多工具（例如recover4all，FinalData Recovery）可以把这些已经删除的文件恢复出来。在Linux 下这一切是否可能呢？
实际上，为了方便用户的使用，现在 Linux 上流行的桌面管理工具（例如gnome和KDE）中都已经集成了回收站的功能。其基本思想是在桌面管理工具中捕获对文件的删除操作，将要删除的文件移动到用户根目录下的 .Trash 文件夹中，但却并不真正删除该文件。当然，像在 Windows 上一样，如果用户在删除文件的同时，按下了 Shift 键并确认删除该文件，那么这个文件就不会被移动到 .Trash 文件夹中，也就无从恢复了。此时，习惯了使用 Windows 上各种恢复工具的人就会顿足捶胸，抱怨 Linux 上工具的缺乏了。但是请稍等一下，难道按照这种方式删除的文件就真的无从恢复了么？或者换一个角度来看，使用 rm 命令删除的文件是否还有办法能够恢复出来呢？
背景知识
在开始真正进行实践之前，让我们首先来了解一下在 Linux 系统中，文件是如何进行存储和定位的，这对于理解如何恢复文件来说非常重要。我们知道，数据最终以数据块的形式保存在磁盘上，而操作系统是通过文件系统来管理这些数据的。ext2/ext3 是 Linux 上应用最为广泛的文件系统，本文将以 ext2 文件系统为例展开介绍。
我们知道，在操作系统中，文件系统是采用一种层次化的形式表示的，通常可以表示成一棵倒置的树。所有的文件和子目录都是通过查找其父目录项来定位的，目录项中通过匹配文件名可以找到对应的索引节点号（inode），通过查找索引节点表（inode table）就可以找到文件在磁盘上的位置，整个过程如图1所示。
图 1. 文件数据定位过程
对于 ext2 类型的文件系统来说，目录项是使用一个名为 ext2_dir_entry_2 的结构来表示的，该结构定义如下所示：
清单 1. ext2_dir_entry_2 结构定义
struct ext2_dir_entry_2 {
__le32 inode; /* 索引节点号 */
__le16 rec_len; /* 目录项的长度 */
__u8 name_len; /* 文件名长度 */
__u8 file_type; /* 文件类型 */
char name[EXT2_NAME_LEN]; /* 文件名 */
};
|
在 Unix/Linux 系统中，目录只是一种特殊的文件。目录和文件是通过 file_type 域来区分的，该值为 1 则表示是普通文件，该值为 2 则表示是目录。
对于每个 ext2 分区来说，其在物理磁盘上的布局如图 2 所示：
图 2. ext2 分区的布局
从图 2 中可以看到，对于 ext2 文件系统来说，磁盘被划分成一个个大小相同的数据块，每个块的大小可以是1024、2048 或 4096 个字节。其中，第一个块称为引导块，一般保留做引导扇区使用，因此 ext2 文件系统一般都是从第二个块开始的。剩余的块被划分为一个个的块组，ext2 文件系统会试图尽量将相同文件的数据块都保存在同一个块组中，并且尽量保证文件在磁盘上的连续性，从而提高文件读写时的性能。
至于一个分区中到底有多少个块组，这取决于两个因素：
- 分区大小。
- 块大小。
最终的计算公式如下：
分区中的块组数＝分区大小/(块大小*8)
这是由于在每个块组中使用了一个数据块位图来标识数据块是否空闲，因此每个块组中最多可以有（块大小*8）个块；该值除上分区大小就是分区中总的块组数。
每个块组都包含以下内容：
- 超级块。存放文件系统超级块的一个拷贝。
- 组描述符。该块组的组描述符。
- 数据块位图。标识相应的数据块是否空闲。
- 索引节点位图。标识相应的索引节点是否空闲。
- 索引节点表。存放所有索引节点的数据。
- 数据块。该块组中用来保存实际数据的数据块。
在每个块组中都保存了超级块的一个拷贝，默认情况下，只有第一个块组中的超级块结构才会被系统内核使用；其他块组中的超级块可以在 e2fsck 之类的程序对磁盘上的文件系统进行一致性检查使用。在 ext2 文件系统中，超级块的结构会通过一个名为 ext2_super_block 的结构进行引用。该结构的一些重要域如下所示：
清单 2. ext2_super_block 结构定义
struct ext2_super_block {
__le32 s_inodes_count; /* 索引节点总数 */
__le32 s_blocks_count; /* 块数，即文件系统以块为单位的大小 */
__le32 s_r_blocks_count; /* 系统预留的块数 */
__le32 s_free_blocks_count; /* 空闲块数 */
__le32 s_free_inodes_count; /* 空闲索引节点数 */
__le32 s_first_data_block; /* 第一个可用数据块的块号 */
__le32 s_log_block_size; /* 块大小 */
__le32 s_blocks_per_group; /* 每个块组中的块数 */
__le32 s_inodes_per_group; /* 每个块组中的索引节点个数 */
...
}
|
每个块组都有自己的组描述符，在 ext2 文件系统中是通过一个名为 ext2_group_desc的结构进行引用的。该结构的定义如下：
清单 3. ext2_group_desc 结构定义
/*
* Structure of a blocks group descriptor
*/
struct ext2_group_desc
{
__le32 bg_block_bitmap; /* 数据块位图的块号 */
__le32 bg_inode_bitmap; /* 索引节点位图的块号 */
__le32 bg_inode_table; /* 第一个索引节点表的块号 */
__le16 bg_free_blocks_count; /* 该组中空闲块数 */
__le16 bg_free_inodes_count; /* 该组中空闲索引节点数 */
__le16 bg_used_dirs_count; /* 该组中的目录项 */
__le16 bg_pad;
__le32 bg_reserved[3];
};
|
数据块位图和索引节点位图分别占用一个块的大小，其每一位描述了对应数据块或索引节点是否空闲，如果该位为0，则表示空闲；如果该位为1，则表示已经使用。
索引节点表存放在一系列连续的数据块中，每个数据块中可以包括若干个索引节点。每个索引节点在 ext2 文件系统中都通过一个名为 ext2_inode 的结构进行引用，该结构大小固定为 128 个字节，其中一些重要的域如下所示：
清单 4. ext2_inode 结构定义
/*
* Structure of an inode on the disk
*/
struct ext2_inode {
__le16 i_mode; /* 文件模式 */
__le16 i_uid; /* 文件所有者的 uid */
__le32 i_size; /* 以字节为单位的文件长度 */
__le32 i_atime; /* 最后一次访问该文件的时间 */
__le32 i_ctime; /* 索引节点最后改变的时间 */
__le32 i_mtime; /* 文件内容最后改变的时间 */
__le32 i_dtime; /* 文件删除的时间 */
__le16 i_gid; /* 文件所有者的 gid */
__le16 i_links_count; /* 硬链接数 */
__le32 i_blocks; /* 文件的数据块数 */
...
__le32 i_block[EXT2_N_BLOCKS];/* 指向数据块的指针 */
...
};
|
第一个索引节点所在的块号保存在该块组描述符的 bg_inode_table 域中。请注意 i_block 域，其中就包含了保存数据的数据块的位置。有关如何对数据块进行寻址，请参看后文“数据块寻址方式”一节的内容。
需要知道的是，在普通的删除文件操作中，操作系统并不会逐一清空保存该文件的数据块的内容，而只会释放该文件所占用的索引节点和数据块，方法是将索引节点位图和数据块位图中的相应标识位设置为空闲状态。因此，如果我们可以找到文件对应的索引节点，由此查到相应的数据块，就可能从磁盘上将已经删除的文件恢复出来。
幸运的是，这一切都是可能的！本文将通过几个实验来了解一下如何从磁盘上恢复删除的文件。
数据块寻址方式
回想一下，ext2_inode 结构的 i_block 域是一个大小为 EXT2_N_BLOCKS 的数组，其中保存的就是真正存放文件数据的数据块的位置。通常来说，EXT2_N_BLOCKS 大小为 15。在 ext2 文件系统，采用了直接寻址和间接寻址两种方式来对数据块进行寻址，原理如图3 所示：
图 3. 数据块寻址方式
- 对于 i_block 的前 12 个元素（i_block[0]到i_block[11]）来说，其中存放的就是实际的数据块号，即对应于文件的 0 到 11 块。这种方式称为直接寻址。
- 对于第13个元素（i_block[12]）来说，其中存放的是另外一个数据块的逻辑块号；这个块中并不存放真正的数据，而是存放真正保存数据的数据块的块号。即 i_block[12] 指向一个二级数组，其每个元素都是对应数据块的逻辑块号。由于每个块号需要使用 4 个字节表示，因此这种寻址方式可以访问的对应文件的块号范围为 12 到 (块大小/4)+11。这种寻址方式称为间接寻址。
- 对于第14个元素（i_block[13]）来说，其中存放也是另外一个数据块的逻辑块号。与间接寻址方式不同的是，i_block[13] 所指向的是一个数据块的逻辑块号的二级数组，而这个二级数组的每个元素又都指向一个三级数组，三级数组的每个元素都是对应数据块的逻辑块号。这种寻址方式称为二次间接寻址，对应文件块号的寻址范围为 (块大小/4)+12 到 (块大小/4)2+(块大小/4)+11。
- 对于第15个元素（i_block[14]）来说，则利用了三级间接索引，其第四级数组中存放的才是逻辑块号对应的文件块号，其寻址范围从 (块大小/4)2+(块大小/4)+12 到 (块大小/4)3+ (块大小/4)2+(块大小/4)+11。
ext2 文件系统可以支持1024、2048和4096字节三种大小的块，对应的寻址能力如下表所示：
表 1. 各种数据块对应的文件寻址范围
| 块大小 |
直接寻址 |
间接寻址 |
二次间接寻址 |
三次间接寻址 |
| 1024 |
12KB |
268KB |
64.26MB |
16.06GB |
| 2048 |
24KB |
1.02MB |
513.02MB |
265.5GB |
| 4096 |
48KB |
4.04MB |
4GB |
~ 4TB |
掌握上面介绍的知识之后，我们就可以开始恢复文件的实验了。
准备文件系统
为了防止破坏已有系统，本文将采用一个新的分区进行恢复删除文件的实验。
首先让我们准备好一个新的分区，并在上面创建 ext2 格式的文件系统。下面的命令可以帮助创建一个 20GB 的分区：
清单 5. 新建磁盘分区
# fdisk /dev/sdb << END
n
+20G
p
w
q
END
|
在笔者的机器上，这个分区是 /dev/sdb6。然后创建文件系统：
清单 6. 在新分区上创建 ext2 文件系统
并将其挂载到系统上来：
清单 7. 挂载创建的 ext2 文件系统
# mkdir /tmp/test
# mount /dev/sdb6 /tmp/test
|
在真正使用这个文件系统之前，让我们首先使用系统提供的一个命令 dumpe2fs 来熟悉一下这个文件系统的一些具体参数：
清单 8. 使用 dumpe2fs 熟悉这个文件系统的参数
# dumpe2fs /dev/sdb6
dumpe2fs 1.39 (29-May-2006)
Filesystem volume name: <none>
Last mounted on: <not available>
Filesystem UUID: d8b10aa9-c065-4aa5-ab6f-96a9bcda52ce
Filesystem magic number: 0xEF53
Filesystem revision #: 1 (dynamic)
Filesystem features: ext_attr resize_inode dir_index filetype sparse_super large_file
Default mount options: (none)
Filesystem state: not clean
Errors behavior: Continue
Filesystem OS type: Linux
Inode count: 2443200
Block count: 4885760
Reserved block count: 244288
Free blocks: 4797829
Free inodes: 2443189
First block: 0
Block size: 4096
Fragment size: 4096
Reserved GDT blocks: 1022
Blocks per group: 32768
Fragments per group: 32768
Inodes per group: 16288
Inode blocks per group: 509
Filesystem created: Mon Oct 29 20:04:16 2007
Last mount time: Mon Oct 29 20:06:52 2007
Last write time: Mon Oct 29 20:08:31 2007
Mount count: 1
Maximum mount count: 39
Last checked: Mon Oct 29 20:04:16 2007
Check interval: 15552000 (6 months)
Next check after: Sat Apr 26 20:04:16 2008
Reserved blocks uid: 0 (user root)
Reserved blocks gid: 0 (group root)
First inode: 11
Inode size: 128
Default directory hash: tea
Directory Hash Seed: d1432419-2def-4762-954a-1a26fef9d5e8
Group 0: (Blocks 0-32767)
Primary superblock at 0, Group descriptors at 1-2
Reserved GDT blocks at 3-1024
Block bitmap at 1025 (+1025), Inode bitmap at 1026 (+1026)
Inode table at 1027-1535 (+1027)
31224 free blocks, 16276 free inodes, 2 directories
Free blocks: 1543-22535, 22537-32767
Free inodes: 12, 14-16288
...
Group 149: (Blocks 4882432-4885759)
Block bitmap at 4882432 (+0), Inode bitmap at 4882433 (+1)
Inode table at 4882434-4882942 (+2)
2817 free blocks, 16288 free inodes, 0 directories
Free blocks: 4882943-4885759
Free inodes: 2426913-2443200
|
应用前面介绍的一些知识，我们可以看到，这个文件系统中，块大小（Block size）为4096字节，因此每个块组中的块数应该是4096*8=32768个（Blocks per group），每个块组的大小是 128MB，整个分区被划分成20GB/(4KB*32768)=160个。但是为什么我们只看到 150 个块组（0到149）呢？实际上，在 fdisk 中，我们虽然输入要创建的分区大小为 20GB，但实际上，真正分配的空间并不是严格的20GB，而是只有大约 20*109 个字节，准确地说，应该是 (4885760 * 4096) / (1024*1024*1024) = 18.64GB。这是由于不同程序的计数单位的不同造成的，在使用存储设备时经常遇到这种问题。因此，这个分区被划分成 150 个块组，前 149 个块组分别包含 32768 个块（即 128B），最后一个块组只包含 3328 个块。
另外，我们还可以看出，每个索引节点的大小是 128 字节，每个块组中包含 16288 个索引节点，在磁盘上使用 509 个块来存储（16288*128/4096），在第一个块组中，索引节点表保存在 1027 到 1535 块上。
数据块和索引节点是否空闲，是分别使用块位图和索引节点位图来标识的，在第一个块组中，块位图和索引节点位图分别保存在 1025 和 1026 块上。
dumpe2fs 的输出结果中还包含了其他一些信息，我们暂时先不用详细关心这些信息。
准备测试文件
现在请将附件中的 createfile.sh 文件下载到本地，并将其保存到 /tmp/test 目录中，这个脚本可以帮助我们创建一个特殊的文件，其中每行包含 1KB 字符，最开始的14个字符表示行号。之所以采用这种文件格式，是为了方便地确认所恢复出来的文件与原始文件之间的区别。这个脚本的用法如下：
清单 9. createfile.sh 脚本的用法
# ./createfile.sh [size in KB] [filename]
|
第 1 个参数表示所生成的文件大小，单位是 KB；第 2 个参数表示所生成文件的名字。
下面让我们创建几个测试文件：
清单 10. 准备测试文件
# cd /tmp/test
#./createfile.sh 35 testfile.35K
#./createfile.sh 10240 testfile.10M
# cp testfile.35K testfile.35K.orig
# cp testfile.10M testfile.10M.orig
|
上面的命令新创建了大小为 35 KB 和 9000KB 的两个文件，并为它们各自保存了一个备份，备份文件的目的是为了方便使用 diff 之类的工具验证最终恢复出来的文件与原始文件完全一致。
ls 命令的 –i 选项可以查看有关保存文件使用的索引节点的信息：
清单11. 查看文件的索引节点号
# ls -li | sort
11 drwx------ 2 root root 16384 Oct 29 20:08 lost+found
12 -rwxr-xr-x 1 root root 1406 Oct 29 20:09 createfile.sh
13 -rw-r--r-- 1 root root 35840 Oct 29 20:09 testfile.35K
14 -rw-r--r-- 1 root root 10485760 Oct 29 20:10 testfile.10M
15 -rw-r--r-- 1 root root 35840 Oct 29 20:10 testfile.35K.orig
16 -rw-r--r-- 1 root root 10485760 Oct 29 20:11 testfile.10M.orig
|
第一列中的数字就是索引节点号。从上面的输出结果我们可以看出，索引节点号是按照我们创建文件的顺序而逐渐自增的，我们刚才创建的 35K 大小的文件的索引节点号为 13，10M 大小的文件的索引节点号为 14。debugfs 中提供了很多工具，可以帮助我们了解进一步的信息。现在执行下面的命令：
清单12. 查看索引节点 <13> 的详细信息
# echo "stat <13>" | debugfs /dev/sdb6
debugfs 1.39 (29-May-2006)
Inode: 13 Type: regular Mode: 0644 Flags: 0x0 Generation: 2957086759
User: 0 Group: 0 Size: 35840
File ACL: 0 Directory ACL: 0
Links: 1 Blockcount: 72
Fragment: Address: 0 Number: 0 Size: 0
ctime: 0x47268467 -- Mon Oct 29 20:09:59 2007
atime: 0x4726849d -- Mon Oct 29 20:10:53 2007
mtime: 0x47268467 -- Mon Oct 29 20:09:59 2007
BLOCKS:
(0-8):4096-4104
TOTAL: 9
|
输出结果显示的就是索引节点 13 的详细信息，从中我们可以看到诸如文件大小（35840=35K）、权限（0644）等信息，尤其需要注意的是最后 3 行的信息，即该文件被保存到磁盘上的 4096 到 4104 总共 9 个数据块中。
下面再看一下索引节点 14 （即 testfile.10M 文件）的详细信息：
清单13. 查看索引节点 <14> 的详细信息
# echo "stat <14>" | debugfs /dev/sdb6
debugfs 1.39 (29-May-2006)
Inode: 14 Type: regular Mode: 0644 Flags: 0x0 Generation: 2957086760
User: 0 Group: 0 Size: 10485760
File ACL: 0 Directory ACL: 0
Links: 1 Blockcount: 20512
Fragment: Address: 0 Number: 0 Size: 0
ctime: 0x47268485 -- Mon Oct 29 20:10:29 2007
atime: 0x472684a5 -- Mon Oct 29 20:11:01 2007
mtime: 0x47268485 -- Mon Oct 29 20:10:29 2007
BLOCKS:
(0-11):24576-24587, (IND):24588, (12-1035):24589-25612, (DIND):25613, (IND):25614,
(1036-2059):25615-26638, (IND):26639, (2060-2559):26640-27139
TOTAL: 2564
|
和索引节点 13 相比，二者之间最重要的区别在于 BLOCKS 的数据，testfile.10M 在磁盘上总共占用了 2564 个数据块，由于需要采用二级间接寻址模式进行访问，所以使用了4个块来存放间接寻址的信息，分别是24588、25613、25614和26639，其中25613块中存放的是二级间接寻址的信息。
恢复删除文件
现在将刚才创建的两个文件删除：
清单14. 删除测试文件
# rm -f testfile.35K testfile.10M
|
debugfs 的 lsdel 命令可以查看文件系统中删除的索引节点的信息：
清单15. 使用 lsdel 命令搜索已删除的文件
# echo "lsdel" | debugfs /dev/sdb6
debugfs 1.39 (29-May-2006)
Inode Owner Mode Size Blocks Time deleted
13 0 100644 35840 9/9 Mon Oct 29 20:32:05 2007
14 0 100644 10485760 2564/2564 Mon Oct 29 20:32:05 2007
2 deleted inodes found.
|
回想一下 inode 结构中有 4 个有关时间的域，分别是 i_atime、i_ctime、i_mtime和i_dtime，分别表示该索引节点的最近访问时间、创建时间、修改时间和删除时间。其中 i_dtime域只有在该索引节点对应的文件或目录被删除时才会被设置。dubugfs 的 lsdel 命令会去扫描磁盘上索引节点表中的所有索引节点，其中 i_dtime 不为空的项就被认为是已经删除的文件所对应的索引节点。
从上面的结果可以看到，刚才删除的两个文件都已经找到了，我们可以通过文件大小区分这两个文件，二者一个大小为35K，另外一个大小为10M，正式我们刚才删除的两个文件。debugfs 的 dump 命令可以帮助恢复文件：
清单16. 使用 dump 命令恢复已删除的文件
# echo "dump <13> /tmp/recover/testfile.35K.dump" | debugfs /dev/sdb6
# echo "dump <14> /tmp/recover/testfile.10M.dump" | debugfs /dev/sdb6
|
执行上面的命令之后，在 /tmp/recover 目录中会生成两个文件，比较这两个文件与我们前面备份的文件的内容就会发现，testfile.35K.dump 与 testfile.35K.orig 的内容完全相同，而 testfile.10M.dump 文件中则仅有前 48K 数据是对的，后面的数据全部为 0 了。这是否意味着删除文件时间已经把数据也同时删除了呢？实际上不是，我们还是有办法把数据全部恢复出来的。记得我们刚才使用 debugfs 的 stat 命令查看索引节点 14 时的 BLOCKS 的数据吗？这些数据记录了整个文件在磁盘上存储的位置，有了这些数据就可以把整个文件恢复出来了，请执行下面的命令：
清单 17. 使用 dd 命令手工恢复已删除的文件
# dd if=/dev/sdb6 of=/tmp/recover/testfile.10M.dd.part1 bs=4096 count=12 skip=24576
# dd if=/dev/sdb6 of=/tmp/recover/testfile.10M.dd.part2 bs=4096 count=1024 skip=24589
# dd if=/dev/sdb6 of=/tmp/recover/testfile.10M.dd.part2 bs=4096 count=1024 skip=25615
# dd if=/dev/sdb6 of=/tmp/recover/testfile.10M.dd.part4 bs=4096 count=500 skip=26640
# cat /tmp/recover/testfile.10M.dd.part[1-4] > /tmp/recover/ testfile.10M.dd
|
比较一下最终的 testfile.10M.dd 文件和已经备份过的 testfile.10M.orig 文件就会发现，二者完全相同：
清单 18. 使用 diff 命令对恢复文件和原文件进行比较
# diff /tmp/recover/ testfile.10M.dd /tmp/test/ testfile.10M.orig
|
数据明明存在，但是刚才我们为什么没法使用 debugfs 的 dump 命令将数据恢复出来呢？现在使用 debugfs 的 stat 命令再次查看一下索引节点 14 的信息：
清单 19. 再次查看索引节点 <14> 的详细信息
# echo "stat <14>" | debugfs /dev/sdb6
debugfs 1.39 (29-May-2006)
Inode: 14 Type: regular Mode: 0644 Flags: 0x0 Generation: 2957086760
User: 0 Group: 0 Size: 10485760
File ACL: 0 Directory ACL: 0
Links: 0 Blockcount: 20512
Fragment: Address: 0 Number: 0 Size: 0
ctime: 0x47268995 -- Mon Oct 29 20:32:05 2007
atime: 0x472684a5 -- Mon Oct 29 20:11:01 2007
mtime: 0x47268485 -- Mon Oct 29 20:10:29 2007
dtime: 0x47268995 -- Mon Oct 29 20:32:05 2007
BLOCKS:
(0-11):24576-24587, (IND):24588, (DIND):25613
TOTAL: 14
|
与前面的结果比较一下不难发现，BLOCKS后面的数据说明总块数为 14，而且也没有整个文件所占据的数据块的详细说明了。既然文件的数据全部都没有发生变化，那么间接寻址所使用的那些索引数据块会不会有问题呢？现在我们来查看一下 24588 这个间接索引块中的内容：
清单 20. 查看间接索引块 24588 中的内容
# dd if=/dev/sdb6 of=block. 24588 bs=4096 count=1 skip=24588
# hexdump block. 24588
0000000 0000 0000 0000 0000 0000 0000 0000 0000
*
0001000
|
显然，这个数据块的内容被全部清零了。debugfs 的dump 命令按照原来的寻址方式试图恢复文件时，所访问到的实际上都是第0 个数据块（引导块）中的内容。这个分区不是可引导分区，因此这个数据块中没有写入任何数据，因此 dump 恢复出来的数据只有前48K是正确的，其后所有的数据全部为0。
实际上，ext2 是一种非常优秀的文件系统，在磁盘空间足够的情况下，它总是试图将数据写入到磁盘上的连续数据块中，因此我们可以假定数据是连续存放的，跳过间接索引所占据的 24588、25613、25614和26639，将从24576 开始的其余 2500 个数据块读出，就能将整个文件完整地恢复出来。但是在磁盘空间有限的情况下，这种假设并不成立，如果系统中磁盘碎片较多，或者同一个块组中已经没有足够大的空间来保存整个文件，那么文件势必会被保存到一些不连续的数据块中，此时上面的方法就无法正常工作了。
反之，如果在删除文件的时候能够将间接寻址使用的索引数据块中的信息保存下来，那么不管文件在磁盘上是否连续，就都可以将文件完整地恢复出来了，但是这样就需要修改 ext2 文件系统的实现了。在 ext2 的实现中，与之有关的有两个函数：ext2_free_data 和 ext2_free_branches（都在 fs/ext2/inode.c 中）。2.6 版本内核中这两个函数的实现如下：
清单 21. 内核中 ext2_free_data 和 ext2_free_branches 函数的实现
814 /**
815 * ext2_free_data - free a list of data blocks
816 * @inode: inode we are dealing with
817 * @p: array of block numbers
818 * @q: points immediately past the end of array
819 *
820 * We are freeing all blocks refered from that array (numbers are
821 * stored as little-endian 32-bit) and updating @inode->i_blocks
822 * appropriately.
823 */
824 static inline void ext2_free_data(struct inode *inode, __le32 *p, __le32 *q)
825 {
826 unsigned long block_to_free = 0, count = 0;
827 unsigned long nr;
828
829 for ( ; p < q ; p++) {
830 nr = le32_to_cpu(*p);
831 if (nr) {
832 *p = 0;
833 /* accumulate blocks to free if they're contiguous */
834 if (count == 0)
835 goto free_this;
836 else if (block_to_free == nr - count)
837 count++;
838 else {
839 mark_inode_dirty(inode);
840 ext2_free_blocks (inode, block_to_free, count);
841 free_this:
842 block_to_free = nr;
843 count = 1;
844 }
845 }
846 }
847 if (count > 0) {
848 mark_inode_dirty(inode);
849 ext2_free_blocks (inode, block_to_free, count);
850 }
851 }
852
853 /**
854 * ext2_free_branches - free an array of branches
855 * @inode: inode we are dealing with
856 * @p: array of block numbers
857 * @q: pointer immediately past the end of array
858 * @depth: depth of the branches to free
859 *
860 * We are freeing all blocks refered from these branches (numbers are
861 * stored as little-endian 32-bit) and updating @inode->i_blocks
862 * appropriately.
863 */
864 static void ext2_free_branches(struct inode *inode, __le32 *p, __le32 *q, int depth)
865 {
866 struct buffer_head * bh;
867 unsigned long nr;
868
869 if (depth--) {
870 int addr_per_block = EXT2_ADDR_PER_BLOCK(inode->i_sb);
871 for ( ; p < q ; p++) {
872 nr = le32_to_cpu(*p);
873 if (!nr)
874 continue;
875 *p = 0;
876 bh = sb_bread(inode->i_sb, nr);
877 /*
878 * A read failure? Report error and clear slot
879 * (should be rare).
880 */
881 if (!bh) {
882 ext2_error(inode->i_sb, "ext2_free_branches",
883 "Read failure, inode=%ld, block=%ld",
884 inode->i_ino, nr);
885 continue;
886 }
887 ext2_free_branches(inode,
888 (__le32*)bh->b_data,
889 (__le32*)bh->b_data + addr_per_block,
890 depth);
891 bforget(bh);
892 ext2_free_blocks(inode, nr, 1);
893 mark_inode_dirty(inode);
894 }
895 } else
896 ext2_free_data(inode, p, q);
897 }
|
注意第 832 和 875 这两行就是用来将对应的索引项置为 0 的。将这两行代码注释掉（对于最新版本的内核 2.6.23 可以下载本文给的补丁）并重新编译 ext2 模块，然后重新加载新编译出来的模块，并重复上面的实验，就会发现利用 debugfs 的 dump 命令又可以完美地恢复出整个文件来了。
显然，这个补丁并不完善，因为这个补丁中的处理只是保留了索引数据块中的索引节点数据，但是还没有考虑数据块位图的处理，如果对应的数据块没有设置为正在使用的状态，并且刚好这些数据块被重用了，其中的索引节点数据就有可能会被覆盖掉了，这样就彻底没有办法再恢复文件了。感兴趣的读者可以沿用这个思路自行开发一个比较完善的补丁。
小结
本文介绍了 ext2 文件系统中的一些基本概念和重要数据结构，并通过几个实例介绍如何恢复已经删除的文件，最后通过修改内核中 ext2 文件系统的实现，解决了大文件无法正常恢复的问题。本系列的下一篇文章中，将介绍如何恢复 ext2 文件系统中的一些特殊文件，以及如何恢复整个目录等方面的问题。
除了普通文件之外，UNIX/Linux 中还存在一些特殊的文件，包括目录、字符设备、块设备、命名管道、socket 以及链接；另外还存在一些带有文件洞的文件，这些特殊文件的恢复是和其存储机制紧密联系在一起的，本文将从这些特殊文件的存储原理和机制入手，逐步介绍这些特殊文件的恢复方法。
在本系列文章的第一部分中，我们介绍了 ext2 文件系统中的一些基本概念和重要数据结构，并通过几个实例学习了如何恢复已经删除的文件，最后通过修改 2.6 版本内核中 ext2 文件系统的实现，解决了大文件无法正常恢复的问题。
通过第一部分的介绍，我们已经知道如何恢复系统中删除的普通文件了，但是系统中还存在一些特殊的文件，比如我们熟悉的符号链接等。回想一下在本系列文章的第一部分中，目录项是使用一个名为 ext2_dir_entry_2 的结构来表示的，该结构定义如下：
清单1. ext2_dir_entry_2 结构定义
表 1. ext2 文件系统中支持的文件类型
对应的宏定义在 include/linux/ext2_fs.h 文件中。其中，命名管道和 socket 是进程间通信时所使用的两种特殊文件，它们都是在程序运行时创建和使用的；一旦程序退出，就会自动删除。另外，字符设备、块设备、命名管道和 socket 这 4 种类型的文件并不占用数据块，所有的信息全部保存在对应的目录项中。因此，对于数据恢复的目的来说，我们只需要重点关注普通文件、符号链接和目录这三种类型的文件即可。
在数据库之类的应用程序中，可能会提前分配一个固定大小的文件，但是并不立即往其中写入数据；数据只有在真正需要的时候才会写入到文件中。如果为这些根本不包含数据的文件立即分配数据块，那就势必会造成磁盘空间的浪费。为了解决这个问题，传统的 Unix 系统中引入了文件洞的概念，文件洞就是普通文件中包含空字符的那部分内容，在磁盘上并不会使用任何数据块来保存这部分数据。也就是说，包含文件洞的普通文件被划分成两部分，一部分是真正包含数据的部分，这部分数据保存在磁盘上的数据块中；另外一部分就是这些文件洞。（在 Windows 操作系统上也存在类似的概念，不过并没有使用文件洞这个概念，而是称之为稀疏文件。）
ext2 文件系统也对文件洞有着很好的支持，其实现是建立在动态数据块分配原则之上的，也就是说，在 ext2 文件系统中，只有当进程需要向文件中写入数据时，才会真正为这个文件分配数据块。
细心的读者可能会发现，在本系列文章第一部分中介绍的 ext2_inode 结构中，有两个与文件大小有关的域：i_size 和 i_blocks，二者分别表示文件的实际大小和存储该文件时真正在磁盘上占用的数据块的个数，其单位分别是字节和块大小（512字节，磁盘每个数据块包含8个块）。通常来说，i_blocks 与块大小的乘积可能会大于或等于 i_size 的值，这是因为文件大小并不都是数据块大小的整数倍，因此分配给该文件的部分数据块可能并没有存满数据。但是在存在文件洞的文件中，i_blocks 与块大小的乘积反而可能会小于 i_size 的值。
清单2. 创建带有文件洞的文件
第一个命令生成的 /tmp/test/hole 文件大小是 7169 字节，其前 7168 字节都为空，第 7169 字节的内容是字母 X。正常来讲，7169 字节的文件需要占用两个数据块来存储，第一个数据块全部为空，第二个数据块的第 3073 字节为字母 X，其余字节都为空。显然，第一个数据块就是一个文件洞，在这个数据块真正被写入数据之前，ext2 并不为其实际分配数据块，而是将 i_block 域的对应位（或间接寻址使用的索引数据块中的对应位）设置为0，表示这是一个文件洞。该文件的内容如下图所示：
图1. /tmp/test/hole 文件的存储方法
清单3. 带有文件洞的文件的 inode 信息
从输出结果中我们可以看出，这个文件的大小是 7169 字节（Size 值，即 ext2_inode 结构中 i_size 域的值），占用块数是 16（Blockcount 值，ext2_inode 结构中 i_blocks 域的值，每个块的大小是 512 字节，而每个数据块占据8个块，因此16个块的大小16×512字节相当于 2 个 512字节×8即4096字节的数据块），但是它的数据在磁盘上只是第一个数据块的内容保存在 20480 这个数据块中。使用下面的方法，我们就可以手工恢复整个文件：
清单4. 使用 dd 命令手工恢复带有文件洞的文件
注意第一个 dd 命令就是用来填充这个大小为 4096 字节的文件洞的，这是文件的第一部分；第二个 dd 命令从磁盘上读取出 20480 数据块的内容，其中包含了文件的第二部分。从合并之后的文件中提取出前 7169 字节的数据，就是最终恢复出来的文件。
清单5. 创建 57K 大小的带有文件洞的文件
清单6. 使用间接寻址方式的带有文件洞的文件的 inode 信息
从结果中可以看出，该文件占用了两个数据块来存储数据，一个是间接寻址使用的索引块 24576，一个是真正存放数据的数据块24577。下面让我们来查看一下 24576 这个数据块中的内容：
清单7. 索引数据块中存储的数据
正如预期的一样，其中只有第3个 32 位（每个数据块的地址占用32位）表示了真正存储数据的数据块的地址：0x6001，即十进制的 24577。现在恢复这个文件也就便得非常简单了：
清单8. 手工恢复带有文件洞的大文件
在 ext2 文件系统中，目录是一种特殊的文件，其索引节点的结构与普通文件没什么两样，唯一的区别是目录中的数据都是按照 ext2_dir_entry_2 结构存储在数据块中的（按照 4 字节对齐）。在开始尝试恢复目录之前，首先让我们详细了解一下目录数据块中的数据究竟是如何存储的。现在我们使用 debugfs 来查看一个已经准备好的目录的信息：
清单9. 用来测试的文件系统的信息
从输出结果中可以看出，每个目录结构中至少要包含两项：当前目录（.）和父目录（..）的信息。在一个文件系统中，会有一些特殊的索引节点是保留的，用户创建的文件无法使用这些索引节点。2 就是这样一个特殊的索引节点，表示根目录。结合上面的输出结果，当前目录（.）和父目录（..）对应的索引节点号都是2，表示这是该分区的根目录。特别地，在使用 mke2fs 命令创建一个 ext2 类型的文件系统时，会自动创建一个名为 lost+found 的目录，并为其预留 4 个数据块的大小（16KB），其用途稍后就会介绍。
我们在根目录下面创建了几个文件和一个名为 dir1（索引节点号为 32577）的目录，并在 dir1 中又创建了两个子目录（subdir1 和 subdir2）和几个文件。
要想完美地恢复目录，必须了解清楚在删除目录时究竟对系统进行了哪些操作，其中哪些是可以恢复的，哪些是无法恢复的，这样才能寻找适当的方式去尝试恢复数据。现在先让我们记录下这个文件系统目前的一些状态：
清单10. 根目录（索引节点 <2>）子目录 dir1的 inode 信息
清单11. 备份根目录和子目录 dir1 的数据块
清单12. read_dir_entry.c 源代码
