要想恢復誤刪除的文件，必須清楚數據在磁碟上究竟是如何存儲的，以及如何定位並恢複數據。本文從數據恢復的角度，著重介紹了 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. 新建磁碟分區
在筆者的機器上，這個分區是 /dev/sdb6。然後創建文件系統：
清單 6. 在新分區上創建 ext2 文件系統
並將其掛載到系統上來：
清單 7. 掛載創建的 ext2 文件系統
在真正使用這個文件系統之前，讓我們首先使用系統提供的一個命令 dumpe2fs 來熟悉一下這個文件系統的一些具體參數：
清單 8. 使用 dumpe2fs 熟悉這個文件系統的參數
應用前面介紹的一些知識，我們可以看到，這個文件系統中，塊大小（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 腳本的用法
第 1 個參數表示所生成的文件大小，單位是 KB；第 2 個參數表示所生成文件的名字。
下面讓我們創建幾個測試文件：
清單 10. 準備測試文件
上面的命令新創建了大小為 35 KB 和 9000KB 的兩個文件，並為它們各自保存了一個備份，備份文件的目的是為了方便使用 diff 之類的工具驗證最終恢復出來的文件與原始文件完全一致。
ls 命令的 –i 選項可以查看有關保存文件使用的索引節點的信息：
清單11. 查看文件的索引節點號
第一列中的數字就是索引節點號。從上面的輸出結果我們可以看出，索引節點號是按照我們創建文件的順序而逐漸自增的，我們剛才創建的 35K 大小的文件的索引節點號為 13，10M 大小的文件的索引節點號為 14。debugfs 中提供了很多工具，可以幫助我們了解進一步的信息。現在執行下面的命令：
清單12. 查看索引節點 <13> 的詳細信息
輸出結果顯示的就是索引節點 13 的詳細信息，從中我們可以看到諸如文件大小（35840=35K）、許可權（0644）等信息，尤其需要注意的是最後 3 行的信息，即該文件被保存到磁碟上的 4096 到 4104 總共 9 個數據塊中。
下面再看一下索引節點 14 （即 testfile.10M 文件）的詳細信息：
清單13. 查看索引節點 <14> 的詳細信息
和索引節點 13 相比，二者之間最重要的區別在於 BLOCKS 的數據，testfile.10M 在磁碟上總共佔用了 2564 個數據塊，由於需要採用二級間接定址模式進行訪問，所以使用了4個塊來存放間接定址的信息，分別是24588、25613、25614和26639，其中25613塊中存放的是二級間接定址的信息。
恢復刪除文件
現在將剛才創建的兩個文件刪除：
清單14. 刪除測試文件
debugfs 的 lsdel 命令可以查看文件系統中刪除的索引節點的信息：
清單15. 使用 lsdel 命令搜索已刪除的文件
回想一下 inode 結構中有 4 個有關時間的域，分別是 i_atime、i_ctime、i_mtime和i_dtime，分別表示該索引節點的最近訪問時間、創建時間、修改時間和刪除時間。其中 i_dtime域只有在該索引節點對應的文件或目錄被刪除時才會被設置。dubugfs 的 lsdel 命令會去掃描磁碟上索引節點表中的所有索引節點，其中 i_dtime 不為空的項就被認為是已經刪除的文件所對應的索引節點。
從上面的結果可以看到，剛才刪除的兩個文件都已經找到了，我們可以通過文件大小區分這兩個文件，二者一個大小為35K，另外一個大小為10M，正式我們剛才刪除的兩個文件。debugfs 的 dump 命令可以幫助恢復文件：
清單16. 使用 dump 命令恢復已刪除的文件
執行上面的命令之後，在 /tmp/recover 目錄中會生成兩個文件，比較這兩個文件與我們前面備份的文件的內容就會發現，testfile.35K.dump 與 testfile.35K.orig 的內容完全相同，而 testfile.10M.dump 文件中則僅有前 48K 數據是對的，後面的數據全部為 0 了。這是否意味著刪除文件時間已經把數據也同時刪除了呢？實際上不是，我們還是有辦法把數據全部恢復出來的。記得我們剛才使用 debugfs 的 stat 命令查看索引節點 14 時的 BLOCKS 的數據嗎？這些數據記錄了整個文件在磁碟上存儲的位置，有了這些數據就可以把整個文件恢復出來了，請執行下面的命令：
清單 17. 使用 dd 命令手工恢復已刪除的文件
比較一下最終的 testfile.10M.dd 文件和已經備份過的 testfile.10M.orig 文件就會發現，二者完全相同：
清單 18. 使用 diff 命令對恢復文件和原文件進行比較
數據明明存在，但是剛才我們為什麼沒法使用 debugfs 的 dump 命令將數據恢復出來呢？現在使用 debugfs 的 stat 命令再次查看一下索引節點 14 的信息：
清單 19. 再次查看索引節點 <14> 的詳細信息
與前面的結果比較一下不難發現，BLOCKS後面的數據說明總塊數為 14，而且也沒有整個文件所佔據的數據塊的詳細說明了。既然文件的數據全部都沒有發生變化，那麼間接定址所使用的那些索引數據塊會不會有問題呢？現在我們來查看一下 24588 這個間接索引塊中的內容：
清單 20. 查看間接索引塊 24588 中的內容
顯然，這個數據塊的內容被全部清零了。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 結構定義
struct ext2_dir_entry_2 { __le32 inode; /* 索引節點號 */ __le16 rec_len; /* 目錄項的長度 */ __u8 name_len; /* 文件名長度 */ __u8 file_type; /* 文件類型 */ char name[EXT2_NAME_LEN]; /* 文件名 */ }; |
其中 file_type 域就標識了每個文件的類型。ext2 文件系統中支持的文件類型定義如下表所示：
表 1. ext2 文件系統中支持的文件類型
| file_type | 宏定義 | 說明 |
| 1 | EXT2_FT_REG_FILE | 普通文件 |
| 2 | EXT2_FT_DIR | 目錄 |
| 3 | EXT2_FT_CHRDEV | 字元設備 |
| 4 | EXT2_FT_BLKDEV | 塊設備 |
| 5 | EXT2_FT_FIFO | 命名管道 |
| 6 | EXT2_FT_SOCK | socket |
| 7 | EXT2_FT_SYMLINK | 符號鏈接 |
對應的宏定義在 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. 創建帶有文件洞的文件
# echo -n "X" | dd of=/tmp/test/hole bs=1024 seek=7 # ls -li /tmp/test/hole 15 -rw-r--r-- 1 root root 7169 Nov 26 11:03 /tmp/test/hole # hexdump /tmp/test/hole 0000000 0000 0000 0000 0000 0000 0000 0000 0000 * 0001c00 0058 0001c01 |
第一個命令生成的 /tmp/test/hole 文件大小是 7169 位元組，其前 7168 位元組都為空，第 7169 位元組的內容是字母 X。正常來講，7169 位元組的文件需要佔用兩個數據塊來存儲，第一個數據塊全部為空，第二個數據塊的第 3073 位元組為字母 X，其餘位元組都為空。顯然，第一個數據塊就是一個文件洞，在這個數據塊真正被寫入數據之前，ext2 並不為其實際分配數據塊，而是將 i_block 域的對應位（或間接定址使用的索引數據塊中的對應位）設置為0，表示這是一個文件洞。該文件的內容如下圖所示：
圖1. /tmp/test/hole 文件的存儲方法
file_hole.jpg
現在我們可以使用 debugfs 來查看一下這個文件的詳細信息：
清單3. 帶有文件洞的文件的 inode 信息
# echo "stat <15>" | debugfs /dev/sdb6 debugfs 1.39 (29-May-2006) debugfs: Inode: 15 Type: regular Mode: 0644 Flags: 0x0 Generation: 4118330634 User: 0 Group: 0 Size: 7169 File ACL: 1544 Directory ACL: 0 Links: 1 Blockcount: 16 Fragment: Address: 0 Number: 0 Size: 0 ctime: 0x474a379c -- Mon Nov 26 11:03:56 2007 atime: 0x474a379c -- Mon Nov 26 11:03:56 2007 mtime: 0x474a379c -- Mon Nov 26 11:03:56 2007 BLOCKS: (1):20480 TOTAL: 1 |
從輸出結果中我們可以看出，這個文件的大小是 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 if=/dev/zero of=/tmp/recover/hole.part1 bs=4096 count=1 # dd if=/dev/sdb6 of=/tmp/recover/hole.part2 bs=4096 count=1 skip=20480 # cat /tmp/recover/hole.part1 /tmp/recover/hole.part2 > /tmp/recover/hole.full # split -d -b 7169 hole.full hole # mv hole00 hole # diff /tmp/test/hole /tmp/recover/hole |
注意第一個 dd 命令就是用來填充這個大小為 4096 位元組的文件洞的，這是文件的第一部分；第二個 dd 命令從磁碟上讀取出 20480 數據塊的內容，其中包含了文件的第二部分。從合併之後的文件中提取出前 7169 位元組的數據，就是最終恢復出來的文件。
接下來讓我們看一個稍微大一些的帶有文件洞的例子，使用下面的命令創建一個大小為57KB 的文件：
清單5. 創建 57K 大小的帶有文件洞的文件
# echo -n "Y" | dd of=/tmp/test/hole.57K bs=1024 seek=57 # ls -li /tmp/test/hole.57K 17 -rw-r--r-- 1 root root 58369 Nov 26 12:53 /tmp/test/hole.57K # hexdump /tmp/test/hole.57K 0000000 0000 0000 0000 0000 0000 0000 0000 0000 * 000e400 0059 000e401 |
與上一個文件類似，這個文件的數據也只有一個字元，是 0x000e400（即第58369位元組）為字元“Y”。我們真正關心的是這個文件的數據存儲情況：
清單6. 使用間接定址方式的帶有文件洞的文件的 inode 信息
# echo "stat <17>" | debugfs /dev/sdb6 debugfs 1.39 (29-May-2006) debugfs: Inode: 17 Type: regular Mode: 0644 Flags: 0x0 Generation: 4261347083 User: 0 Group: 0 Size: 58369 File ACL: 1544 Directory ACL: 0 Links: 1 Blockcount: 24 Fragment: Address: 0 Number: 0 Size: 0 ctime: 0x474a5166 -- Mon Nov 26 12:53:58 2007 atime: 0x474a5187 -- Mon Nov 26 12:54:31 2007 mtime: 0x474a5166 -- Mon Nov 26 12:53:58 2007 BLOCKS: (IND):24576, (14):24577 TOTAL: 2 |
從結果中可以看出，該文件佔用了兩個數據塊來存儲數據，一個是間接定址使用的索引塊 24576，一個是真正存放數據的數據塊24577。下面讓我們來查看一下 24576 這個數據塊中的內容：
清單7. 索引數據塊中存儲的數據
# dd if=/dev/sdb6 of=/tmp/recover/block.24576 bs=4096 count=1 skip=24576 # hexdump block.24576 0000000 0000 0000 0000 0000 6001 0000 0000 0000 0000010 0000 0000 0000 0000 0000 0000 0000 0000 * 0001000 |
正如預期的一樣，其中只有第3個 32 位（每個數據塊的地址佔用32位）表示了真正存儲數據的數據塊的地址：0x6001，即十進位的 24577。現在恢復這個文件也就便得非常簡單了：
清單8. 手工恢復帶有文件洞的大文件
# dd if=/dev/zero of=/tmp/recover/hole.57K.part1 bs=4096 count=14 # dd if=/dev/sdb6 of=/tmp/recover/hole.57K.part2 bs=4096 count=1 skip=24577 # cat /tmp/recover/hole.57K.part1 /tmp/recover/hole.57K.part2 \ > /tmp/recover/hole.57K.full # split -d -b 58369 hole.57K.full hole.57K # mv hole.57K00 hole.57K # diff /tmp/test/hole.57K /tmp/recover/hole.57K |
幸運的是，debugfs 的 dump 命令可以很好地理解文件洞機制，所以可以與普通文件一樣完美地恢復整個文件，詳細介紹請參看本系列文章的第一部分。
|
目錄
在 ext2 文件系統中，目錄是一種特殊的文件，其索引節點的結構與普通文件沒什麼兩樣，唯一的區別是目錄中的數據都是按照 ext2_dir_entry_2 結構存儲在數據塊中的（按照 4 位元組對齊）。在開始嘗試恢複目錄之前，首先讓我們詳細了解一下目錄數據塊中的數據究竟是如何存儲的。現在我們使用 debugfs 來查看一個已經準備好的目錄的信息：
清單9. 用來測試的文件系統的信息
# debugfs /dev/sdb6 debugfs 1.39 (29-May-2006) debugfs: ls -l 2 40755 (2) 0 0 4096 28-Nov-2007 16:57 . 2 40755 (2) 0 0 4096 28-Nov-2007 16:57 .. 11 40700 (2) 0 0 16384 28-Nov-2007 16:52 lost+found 12 100755 (1) 0 0 1406 28-Nov-2007 16:53 createfile.sh 13 100644 (1) 0 0 35840 28-Nov-2007 16:53 testfile.35K 14 100644 (1) 0 0 10485760 28-Nov-2007 16:54 testfile.10M 32577 40755 (2) 0 0 4096 28-Nov-2007 16:56 dir1 15 100644 (1) 0 0 35840 28-Nov-2007 16:56 testfile.35K.orig 16 100644 (1) 0 0 10485760 28-Nov-2007 16:57 testfile.10M.orig debugfs: ls -l dir1 32577 40755 (2) 0 0 4096 28-Nov-2007 16:56 . 2 40755 (2) 0 0 4096 28-Nov-2007 16:57 .. 32578 100755 (1) 0 0 1406 28-Nov-2007 16:55 createfile.sh 32579 40755 (2) 0 0 4096 28-Nov-2007 16:55 subdir11 48865 40755 (2) 0 0 4096 28-Nov-2007 16:55 subdir12 32580 100644 (1) 0 0 35840 28-Nov-2007 16:56 testfile.35K 32581 100644 (1) 0 0 10485760 28-Nov-2007 16:56 testfile.10M |
從輸出結果中可以看出，每個目錄結構中至少要包含兩項：當前目錄（.）和父目錄（..）的信息。在一個文件系統中，會有一些特殊的索引節點是保留的，用戶創建的文件無法使用這些索引節點。2 就是這樣一個特殊的索引節點，表示根目錄。結合上面的輸出結果，當前目錄（.）和父目錄（..）對應的索引節點號都是2，表示這是該分區的根目錄。特別地，在使用 mke2fs 命令創建一個 ext2 類型的文件系統時，會自動創建一個名為 lost+found 的目錄，並為其預留 4 個數據塊的大小（16KB），其用途稍後就會介紹。
我們在根目錄下面創建了幾個文件和一個名為 dir1（索引節點號為 32577）的目錄，並在 dir1 中又創建了兩個子目錄（subdir1 和 subdir2）和幾個文件。
要想完美地恢複目錄，必須了解清楚在刪除目錄時究竟對系統進行了哪些操作，其中哪些是可以恢復的，哪些是無法恢復的，這樣才能尋找適當的方式去嘗試恢複數據。現在先讓我們記錄下這個文件系統目前的一些狀態：
清單10. 根目錄（索引節點 <2>）子目錄 dir1的 inode 信息
debugfs: stat <2> Inode: 2 Type: directory Mode: 0755 Flags: 0x0 Generation: 0 User: 0 Group: 0 Size: 4096 File ACL: 0 Directory ACL: 0 Links: 4 Blockcount: 8 Fragment: Address: 0 Number: 0 Size: 0 ctime: 0x474d2d63 -- Wed Nov 28 16:57:07 2007 atime: 0x474d3203 -- Wed Nov 28 17:16:51 2007 mtime: 0x474d2d63 -- Wed Nov 28 16:57:07 2007 BLOCKS: (0):1536 TOTAL: 1 debugfs: stat <32577> Inode: 32577 Type: directory Mode: 0755 Flags: 0x0 Generation: 1695264350 User: 0 Group: 0 Size: 4096 File ACL: 1542 Directory ACL: 0 Links: 4 Blockcount: 16 Fragment: Address: 0 Number: 0 Size: 0 ctime: 0x474d2d2a -- Wed Nov 28 16:56:10 2007 atime: 0x474d3203 -- Wed Nov 28 17:16:51 2007 mtime: 0x474d2d2a -- Wed Nov 28 16:56:10 2007 BLOCKS: (0):88064 TOTAL: 1 |
以及根目錄和 dir1 目錄的數據塊：
清單11. 備份根目錄和子目錄 dir1 的數據塊
# dd if=/dev/sdb6 of=/tmp/recover/block.1536.orig bs=4096 count=1 skip=1536 # dd if=/dev/sdb6 of=/tmp/recover/block.88064.orig bs=4096 count=1 skip=88064 |
為了方便閱讀目錄數據塊中的數據，我們編寫了一個小程序，源代碼如下所示：
清單12. read_dir_entry.c 源代碼
#include <stdio.h> #include <stdlib.h> #include <ext2fs/ext2_fs.h> struct ext2_dir_entry_part { __u32 inode; /* Inode number */ __u16 rec_len; /* Directory entry length */ __u8 name_len; /* Name length */ __u8 file_type; } dep; void usage() { printf("read_dir_entry [dir entry filename] [dir entry size]\n"); } int main(int argc, char **argv) { struct ext2_dir_entry_2 de; char *filename = NULL; FILE *fp = NULL; int rtn = 0; int length = 0; int de_size = 0; if (argc < 3) { printf("Too few parameters!\n"); usage(); exit(1); } filename = argv[1]; de_size = atoi(argv[2]); fp = fopen(filename, "r"); if (!fp) { printf("cannot open file: %s\n", filename); exit(1); } printf(" offset | inode number | rec_len | name_len | file_type | name\n"); printf("=================================================================\n"); while ( rtn = fread(&dep, sizeof(struct ext2_dir_entry_part), 1, fp) ) { if (dep.rec_len <= 0) { fclose(fp); exit(0); } fseek(fp, 0 - sizeof(struct ext2_dir_entry_part), SEEK_CUR); fread(&de, ((int)(dep.name_len + 3)/4)*4 + sizeof(struct ext2_dir_entry_part), 1, fp); de.name[de.name_len] = '\0'; printf("%6d: %12d%12d%12d%12d %s\n", length, de.inode, de.rec_len, de.name_len, de.file_type, de.name); |-------- XML error: The previous line is longer than the max of 90 characters ---------| length += dep.rec_len; if (length >= de_size - sizeof(struct ext2_dir_entry_part)) { fclose(fp); exit(0); } } fclose(fp); } |
這段程序的基本想法是要遍歷目錄對應的數據塊的內容，並列印每個目錄項的內容（一個 ext2_dir_entry_2 結構）。需要注意的是，在遍歷整個文件時，我們並沒有採用 rec_length 作為步長，而是採用了 name_length + sizeof(struct ext2_dir_entry_part) 作為步長，這是為了能夠讀取到其中被標識為刪除的目錄項的數據，大家稍後就會明白這一點。
將這段程序保存為 read_dir_entry.c，並編譯成可執行程序：
清單13. 編譯 read_dir_entry.c
# gcc –o read_dir_entry read_dir_entry.c |
並分析剛才得到的兩個數據塊的結果：
清單14. 分析原始目錄項中的數據
# ./read_dir_entry block.1536.orig 4096 offset | inode number | rec_len | name_len | file_type | name ================================================================= 0: 2 12 1 2 . 12: 2 12 2 2 .. 24: 11 20 10 2 lost+found 44: 12 24 13 1 createfile.sh 68: 13 20 12 1 testfile.35K 88: 14 20 12 1 testfile.10M 108: 32577 12 4 2 dir1 120: 15 28 17 1 testfile.35K.orig 148: 16 3948 17 1 testfile.10M.orig # ./read_dir_entry block.88064.orig 4096 offset | inode number | rec_len | name_len | file_type | name ================================================================= 0: 32577 12 1 2 . 12: 2 12 2 2 .. 24: 32578 24 13 1 createfile.sh 48: 32579 16 8 2 subdir11 64: 48865 16 8 2 subdir12 80: 32580 20 12 1 testfile.35K 100: 32581 3996 12 1 testfile.10M |
這與上面在 debugfs 中使用 ls 命令看到的結果是完全吻合的。
現在刪除 dir1 這個目錄，然後卸載測試目錄（這是為了確保刪除文件操作會被同步到磁碟上的數據塊中），然後重新讀取我們關注的這兩個數據塊的內容：
清單15. 刪除目錄並重新備份目錄項數據
# rm –rf /tmp/test/dir1 # cd / # umount /tmp/test # dd if=/dev/sdb6 of=/tmp/recover/block.1536.deleted bs=4096 count=1 skip=1536 # dd if=/dev/sdb6 of=/tmp/recover/block.88064. deleted bs=4096 count=1 skip=88064 |
現在再來查看一下這兩個數據塊中內容的變化：
清單16. 分析新目錄項中的數據
# ./read_dir_entry block.1536.deleted 4096 offset | inode number | rec_len | name_len | file_type | name ================================================================= 0: 2 12 1 2 . 12: 2 12 2 2 .. 24: 11 20 10 2 lost+found 44: 12 24 13 1 createfile.sh 68: 13 20 12 1 testfile.35K 88: 14 32 12 1 testfile.10M 108: 0 12 4 2 dir1 120: 15 28 17 1 testfile.35K.orig 148: 16 3948 17 1 testfile.10M.orig # ./read_dir_entry block.88064.deleted 4096 offset | inode number | rec_len | name_len | file_type | name ================================================================= 0: 32577 12 1 2 . 12: 2 12 2 2 .. 24: 32578 24 13 1 createfile.sh 48: 32579 16 8 2 subdir11 64: 48865 16 8 2 subdir12 80: 32580 20 12 1 testfile.35K 100: 32581 3996 12 1 testfile.10M |
與前面的結果進行一下對比就會發現，dir1 目錄的數據塊並沒有發生任何變化，而根目錄的數據塊中 dir1 以及之前的一項則變得不同了。實際上，在刪除 dir1 目錄時，所執行的操作是將 dir1 項中的索引節點號清空，並將這段空間合併到前一項上（即將 dir1 項的 rec_length 加到前一項的 rec_length上）。這也就是為什麼我們編寫的 read_dir_entry 程序沒有採用 rec_length 作為步長來遍曆數據的原因。
除了數據之外，索引節點信息也發生了一些變化，現在我們來了解一下最新的索引節點信息：
清單17. 刪除子目錄后索引節點信息的變化
# debugfs /dev/sdb6 debugfs 1.39 (29-May-2006) debugfs: stat <2> Inode: 2 Type: directory Mode: 0755 Flags: 0x0 Generation: 0 User: 0 Group: 0 Size: 4096 File ACL: 0 Directory ACL: 0 Links: 3 Blockcount: 8 Fragment: Address: 0 Number: 0 Size: 0 ctime: 0x474d3387 -- Wed Nov 28 17:23:19 2007 atime: 0x474d33c2 -- Wed Nov 28 17:24:18 2007 mtime: 0x474d3387 -- Wed Nov 28 17:23:19 2007 BLOCKS: (0):1536 TOTAL: 1 debugfs: stat <32577> Inode: 32577 Type: directory Mode: 0755 Flags: 0x0 Generation: 1695264350 User: 0 Group: 0 Size: 0 File ACL: 1542 Directory ACL: 0 Links: 0 Blockcount: 16 Fragment: Address: 0 Number: 0 Size: 0 ctime: 0x474d3387 -- Wed Nov 28 17:23:19 2007 atime: 0x474d3387 -- Wed Nov 28 17:23:19 2007 mtime: 0x474d3387 -- Wed Nov 28 17:23:19 2007 dtime: 0x474d3387 -- Wed Nov 28 17:23:19 2007 BLOCKS: (0):88064 TOTAL: 1 |
與刪除之前的結果進行一下比較就會發現，主要區別包括：
通過了解數據塊和索引節點的相應變化可以為恢複目錄提供一個清晰的思路，其具體步驟如下：
實際上，步驟3並不是必須的，因為如果這個目錄中包含文件或子目錄，使用 debugfs 的 lsdel 命令（遍歷索引節點表）也可以找到所刪除的索引節點記錄，採用本文中介紹的方法也可以將其逐一恢復出來。
debugfs 的 mi 命令可以用來直接修改索引節點的信息，下面我們就使用這個命令來修改 dir1 這個目錄對應的索引節點的信息：
清單18. 使用 debugfs 的 mi 命令直接修改索引節點信息
# debugfs -w /dev/sdb6 debugfs 1.39 (29-May-2006) debugfs: lsdel Inode Owner Mode Size Blocks Time deleted 32577 0 40755 0 1/ 1 Wed Nov 28 17:23:19 2007 32578 0 100755 1406 1/ 1 Wed Nov 28 17:23:19 2007 32579 0 40755 0 1/ 1 Wed Nov 28 17:23:19 2007 32580 0 100644 35840 9/ 9 Wed Nov 28 17:23:19 2007 32581 0 100644 10485760 2564/2564 Wed Nov 28 17:23:19 2007 48865 0 40755 0 1/ 1 Wed Nov 28 17:23:19 2007 6 deleted inodes found. debugfs: mi <32577> Mode [040755] User ID [0] Group ID [0] Size [0] 4096 Creation time [1196241799] Modification time [1196241799] Access time [1196241799] Deletion time [1196241799] 0 Link count [0] 4 Block count [16] File flags [0x0] Generation [0x650bae5e] File acl [1542] Directory acl [0] Fragment address [0] Fragment number [0] Fragment size [0] Direct Block #0 [88064] Direct Block #1 [0] Direct Block #2 [0] Direct Block #3 [0] Direct Block #4 [0] Direct Block #5 [0] Direct Block #6 [0] Direct Block #7 [0] Direct Block #8 [0] Direct Block #9 [0] Direct Block #10 [0] Direct Block #11 [0] Indirect Block [0] Double Indirect Block [0] Triple Indirect Block [0] debugfs: link <32577> dir1 debugfs: q |
注意要使用 mi 命令直接修改索引節點的信息，在執行 debugfs 命令時必須加上 –w 選項，表示以可寫方式打開該設備文件。在上面這個例子中，lsdel 命令找到 6 個已經刪除的文件，其中 32577 就是 dir1 目錄原來對應的索引節點。接下來使用 mi 命令修改這個索引節點的內容，將 Size 設置為 4096（Block count * 512），Deletion Time 設置為 0，Links count 設置為 4。最後又執行了一個 link 命令，為這個索引節點起名為 dir1（這樣並不會修改父目錄的 Links count 值）。
退出 debugfs 並重新掛載這個設備，就會發現 dir1 目錄已經被找回來了，不過儘管該目錄下面的目錄結構都是正確的，但是這些文件和子目錄的數據都是錯誤的：
清單19. 驗證恢復結果
# mount /dev/sdb6 /tmp/test # ls -li /tmp/test total 20632 12 -rwxr-xr-x 1 root root 1406 Nov 28 16:53 createfile.sh 32577 drwxr-xr-x 4 root root 4096 Nov 28 17:23 dir1 11 drwx------ 2 root root 16384 Nov 28 16:52 lost+found 14 -rw-r--r-- 1 root root 10485760 Nov 28 16:54 testfile.10M 16 -rw-r--r-- 1 root root 10485760 Nov 28 16:57 testfile.10M.orig 13 -rw-r--r-- 1 root root 35840 Nov 28 16:53 testfile.35K 15 -rw-r--r-- 1 root root 35840 Nov 28 16:56 testfile.35K.orig # ls -li /tmp/test/dir1 total 0 ??--------- ? ? ? ? ? /tmp/test/dir1/createfile.sh ??--------- ? ? ? ? ? /tmp/test/dir1/subdir11 ??--------- ? ? ? ? ? /tmp/test/dir1/subdir12 ??--------- ? ? ? ? ? /tmp/test/dir1/testfile.10M ??--------- ? ? ? ? ? /tmp/test/dir1/testfile.35K |
其原因是 dir1 中所包含的另外兩個子目錄和三個文件都還沒有恢復。可以想像，恢復一個刪除的目錄會是件非常複雜而繁瑣的事情。幸運的是，e2fsck 這個工具可以很好地理解 ext2 文件系統的實現，它可以用來對文件系統進行檢查，並自動修復諸如鏈接數不對等問題。現在請按照上面的方法使用 mi 命令將其他 5 個找到的索引節點 Deletion Time 設置為 0，並將 Link count 設置為 1。然後使用下面的命令，強制 e2fsck 對整個文件系統進行檢查：
清單20. 使用 e2fsck 強制對文件系統進行一致性檢查
# e2fsck -f -y /dev/sdb6 > e2fsck.out 2>&1 |
e2fsck 的結果保存在 e2fsck.out 文件中。查看這個文件就會發現，e2fsck要執行 4 個步驟的檢查：
現在重新掛載這個文件系統，會發現所有的文件已經全部恢復出來了。
|
符號鏈接
我們知道，在 ext2 文件系統中，鏈接可以分為兩種：硬鏈接和符號鏈接（或稱為軟鏈接）。實際上，目錄中的每個文件名都對應一個硬鏈接。硬鏈接的出現是為了解決使用不同的文件名來引用同一個文件的問題。如果沒有硬鏈接，只能通過給現有文件新建一份拷貝才能通過另外一個名字來引用這個文件，這樣做的問題是在文件內容發生變化的情況下，勢必會造成引用這些文件的進程所訪問到的數據不一致的情況出現。而雖然每個硬鏈接在文件目錄項中都是作為一個單獨的項存在的，但是其索引節點號完全相同，這就是說它們引用的是同一個索引節點，因此對應的文件數據也完全相同。下面讓我們通過一個例子來驗證一下：
清單21.硬鏈接採用相同的索引節點號
# ln testfile.10M hardlink.10M # ls -li total 20592 12 -rwxr-xr-x 1 root root 1406 Nov 29 19:19 createfile.sh 1205313 drwxr-xr-x 2 root root 4096 Nov 29 19:29 dir1 14 -rw-r--r-- 2 root root 10485760 Nov 29 19:21 hardlink.10M 11 drwx------ 2 root root 16384 Nov 29 19:19 lost+found 14 -rw-r--r-- 2 root root 10485760 Nov 29 19:21 testfile.10M 13 -rw-r--r-- 1 root root 35840 Nov 29 19:20 testfile.35K |
我們可以看到，使用 ln 建立的硬鏈接 hardlink.10M 的索引節點號也是 14，這與 testfile.10M 的索引節點號完全相同，因此通過這兩個名字所訪問到的數據是完全一致的。
因此，硬鏈接的恢復與普通文件的恢復非常類似，唯一的區別在於如果索引節點指向的數據已經恢復出來了，現在就無需再恢複數據了，只需要恢復其父目錄中的對應目錄項即可，這可以通過 debugfs 的 link 命令實現。
硬體鏈接的出現雖然可以滿足通過不同名字來引用相同文件的需要，但是也存在一些問題，包括：
為了解決上面的問題，符號鏈接就應運而生了。符號鏈接與硬鏈接的區別在於它要佔用一個單獨的索引節點來存儲相關數據，但卻並不存儲鏈接指向的文件的數據，而是存儲鏈接的路徑名：如果這個路徑名小於60個字元，就其存儲在符號鏈接索引節點的 i_block 域中；如果超過 60 個字元，就使用一個單獨的數據塊來存儲。下面讓我們來看一個例子：
清單22. 符號鏈接採用不同的索引節點號
# ln -s testfile.10M softlink.10M # ls -li total 20596 12 -rwxr-xr-x 1 root root 1406 Nov 29 19:19 createfile.sh 1205313 drwxr-xr-x 2 root root 4096 Nov 29 19:29 dir1 14 -rw-r--r-- 2 root root 10485760 Nov 29 19:21 hardlink.10M 11 drwx------ 2 root root 16384 Nov 29 19:19 lost+found 15 lrwxrwxrwx 1 root root 12 Nov 29 19:41 softlink.10M -> testfile.10M 14 -rw-r--r-- 2 root root 10485760 Nov 29 19:21 testfile.10M 13 -rw-r--r-- 1 root root 35840 Nov 29 19:20 testfile.35K # echo "stat <15>" | debugfs /dev/sdb6 debugfs 1.39 (29-May-2006) debugfs: Inode: 15 Type: symlink Mode: 0777 Flags: 0x0 Generation: 2344716327 User: 0 Group: 0 Size: 12 File ACL: 1542 Directory ACL: 0 Links: 1 Blockcount: 8 Fragment: Address: 0 Number: 0 Size: 0 ctime: 0x474ea56f -- Thu Nov 29 19:41:35 2007 atime: 0x474ea571 -- Thu Nov 29 19:41:37 2007 mtime: 0x474ea56f -- Thu Nov 29 19:41:35 2007 Fast_link_dest: testfile.10M |
ln 命令的 –s 參數就用來指定創建一個符號鏈接。從結果中可以看出，新創建的符號鏈接使用的索引節點號是 15，索引節點中的 i_block 中存儲的值就是這個符號鏈接所指向的目標：testfile.10M（Fast_link_dest 的值）。
現在再來看一個指向長路徑的符號鏈接的例子：
清單23. 長名符號鏈接
# touch abcdwfghijklmnopqrstuvwxyz0123456789abcdwfghijklmnopqrstuvwxyz0123456789.sh # ln -s abcdwfghijklmnopqrstuvwxyz0123456789abcdwfghijklmnopqrstuvwxyz0123456789.sh \ longsoftlink.sh # ls -li total 20608 16 -rw-r--r-- 1 root root 0 Nov 29 19:52 \ abcdwfghijklmnopqrstuvwxyz0123456789abcdwfghijklmnopqrstuvwxyz0123456789.sh 12 -rwxr-xr-x 1 root root 1406 Nov 29 19:19 createfile.sh 1205313 drwxr-xr-x 2 root root 4096 Nov 29 19:29 dir1 14 -rw-r--r-- 2 root root 10485760 Nov 29 19:21 hardlink.10M 17 lrwxrwxrwx 1 root root 75 Nov 29 19:53 longsoftlink.sh -> \ abcdwfghijklmnopqrstuvwxyz0123456789abcdwfghijklmnopqrstuvwxyz0123456789.sh 11 drwx------ 2 root root 16384 Nov 29 19:19 lost+found 15 lrwxrwxrwx 1 root root 12 Nov 29 19:41 softlink.10M -> testfile.10M 14 -rw-r--r-- 2 root root 10485760 Nov 29 19:21 testfile.10M 13 -rw-r--r-- 1 root root 35840 Nov 29 19:20 testfile.35K # echo "stat <17>" | debugfs /dev/sdb6 debugfs 1.39 (29-May-2006) debugfs: Inode: 17 Type: symlink Mode: 0777 Flags: 0x0 Generation: 744523175 User: 0 Group: 0 Size: 75 File ACL: 1542 Directory ACL: 0 Links: 1 Blockcount: 16 Fragment: Address: 0 Number: 0 Size: 0 ctime: 0x474ea824 -- Thu Nov 29 19:53:08 2007 atime: 0x474ea826 -- Thu Nov 29 19:53:10 2007 mtime: 0x474ea824 -- Thu Nov 29 19:53:08 2007 BLOCKS: (0):6144 TOTAL: 1 |
此處我們創建了一個名字長度為 75 個字元的文件，並建立一個符號鏈接（其索引節點號是 17）指向這個文件。由於鏈接指向的位置路徑名超過了 60 個字元，因此還需要使用一個數據塊（6144）來存儲這個路徑名。手工恢復方法如下：
清單24. 恢復長名符號鏈接
# dd if=/dev/sdb6 of=longsoftlink.6144 bs=4096 count=1 skip=6144 # xxd longsoftlink.6144 | more 0000000: 6162 6364 7766 6768 696a 6b6c 6d6e 6f70 abcdwfghijklmnop 0000010: 7172 7374 7576 7778 797a 3031 3233 3435 qrstuvwxyz012345 0000020: 3637 3839 6162 6364 7766 6768 696a 6b6c 6789abcdwfghijkl 0000030: 6d6e 6f70 7172 7374 7576 7778 797a 3031 mnopqrstuvwxyz01 0000040: 3233 3435 3637 3839 2e73 6800 0000 0000 23456789.sh..... 0000050: 0000 0000 0000 0000 0000 0000 0000 0000 ................ |
這樣符號鏈接的數據就可以完整地恢復出來了。
需要注意的是，為了保證整個文件系統的完整性，在恢復硬鏈接時，還需要修改鏈接指向的索引節點的引用計數值，這可以使用 e2fsck 幫助完成，詳細步驟請參看上一節目錄的恢復。
|
小結
本文介紹了 ext2 文件系統中比較特殊的一些文件的存儲和恢復機制，包括文件洞、目錄和鏈接，並介紹了如何結合使用 debugfs 和 e2fsck 等工具完整恢復 ext2 文件系統的方法。在本系列的後續文章中，我們將介紹幾個可以自動恢復 ext2 文件系統中已刪除文件的工具，以及對 ext2 文件系統的後繼者 ext3 和 ext4 文件系統的一些考慮。
恢復系統中刪除的文件是一個非常繁瑣的過程，而 e2undel 這個工具可以用來方便地恢復文件系統中已刪除的文件。本文將首先討論 e2undel 的工作原理和用法，並對之進行一些改進。然後討論了文件系統故障、文件系統重建、磁碟物理損壞等情況下應該如何恢複數據。
在本系列文章的前兩部分中，我們介紹了 ext2 文件系統中各種文件在磁碟上的存儲結構，以及如何利用 debugfs 工具的輔助，手工恢復這些文件的詳細過程。
通過這兩部分的學習，我們可以看出恢復系統中刪除的文件是一個非常繁瑣的過程，需要非常仔細地考慮各種情況，並且要保持足夠的細心，才可能把數據準確無誤地恢復出來。稍有差錯，就會造成數據丟失的情況。聰明的讀者肯定會想，如果有一些好工具來自動或輔助完成數據的恢復過程，那簡直就太好了。
幸運的是，已經有人開發了這樣一些工具，來簡化用戶的數據恢復工作，e2undel 就是其中功能最為強大的一個。
自動恢復工具 e2undel
回想一下，在 ext2 文件系統中刪除一個文件時，該文件本身的數據並沒有被真正刪除，實際執行的操作如下：
而索引節點中的一些關鍵信息（或稱為元數據，包括文件屬主、訪問許可權、文件大小、該文件所佔用的數據塊等）都並沒有發生任何變化。因此只要知道了索引節點號，就完全可以用本系列文章介紹的技術將文件完整地從磁碟上恢復出來了，這正是 e2undel 之類的工具賴以生存的基礎。
然而，由於所刪除的文件在目錄項中對應的項中的索引節點號被清空了，因此我們就無法從索引節點中獲得文件名的信息了。不過，由於文件大小、屬主和刪除時間信息依然能反映文件的原始信息，因此我們可以通過這些信息來幫助判斷所刪除的文件是哪個。
e2undel 是由Oliver Diedrich 開發的一個用來恢復 ext2 文件系統中已刪除文件的工具，它會遍歷所檢測的文件系統的索引節點表，從中找出所有被標記為刪除的索引節點，並按照屬主和刪除時間列出這些文件。另外，e2undel 還提供了文件大小信息，並試圖按照 file 命令的方式來確定文件類型。如果您使用 rm –rf * 之類的命令一次刪除了很多文件，這種信息就可以用來非常方便地幫助確定希望恢復的是哪些文件。在選擇要恢復的文件之後，e2undel 會從磁碟上讀取該文件佔用的數據塊（這些數據塊的信息全部保存在索引節點中），並將其寫入到一個新文件中。下面我們來看一下 e2undel 這個工具的詳細用法。
首先請從 e2undel 的主頁（http://e2undel.sourceforge.net/）上下載最新的源碼包（截止到撰寫本文為止，最新的版本是 0.82），並將其保存到本地文件系統中。不過這個源碼包在最新的 Fedora Core 8 上編譯時可能會有些問題，這是由於 ext2 文件系統內部實現中一些數據結構的變化引起來的，讀者可以下載本文“下載”部分給出的補丁來修正這個問題（請下載這個補丁文件 e2undel-0.82.patch，並將其保存到與源碼包相同的目錄中）。要想編譯 e2undel，系統中還必須安裝 e2fsprogs 和 e2fsprogs-devel 這兩個包，其中有編譯 e2undel 所需要的一些頭文件。Fedora Core 8 中自帶的這兩個包的版本號是 1.39-7：
清單1. 確認系統中已經安裝了 e2fsprogs 和 e2fsprogs-devel
# rpm -qa | grep e2fsprogs e2fsprogs-libs-1.39-7 e2fsprogs-1.39-7 e2fsprogs-devel-1.39-7 |
現在就可以開始編譯 e2undel 了：
清單2. 編譯 e2undel
# tar -zxf e2undel-0.82.tgz # patch -p0 < e2undel-0.82.patch patching file e2undel-0.82/Makefile patching file e2undel-0.82/e2undel.h patching file e2undel-0.82.orig/libundel.c # cd e2undel-0.82 # make all |
編譯之後會生成一個名為 e2undel 的可執行文件，其用法如下：
清單3. e2undel 的用法
# ./e2undel ./e2undel 0.82 usage: ./e2undel -d device -s path [-a] [-t] usage: ./e2undel -l '-d': file system where to look for deleted files '-s': directory where to save undeleted files '-a': work on all files, not only on those listed in undel log file '-t': try to determine type of deleted files w/o names, works only with '-a' '-l': just give a list of valid files in undel log file |
e2undel 實際上並沒有像前面介紹的使用 e2fsck 那樣的方法一樣真正將已經刪除的文件恢復到原來的文件系統中，因為它並不會修改磁碟上 ext2 使用的內部數據結構（例如索引節點、塊點陣圖和索引節點點陣圖）。相反，它僅僅是將所刪除文件的數據恢復出來並將這些數據保存到一個新文件中。因此，-s 參數指定是保存恢復出來的文件的目錄，最好是在另外一個文件系統上，否則可能會覆蓋磁碟上的原有數據。如果指定了 -t 參數，e2undel 會試圖讀取文件的前 1KB 數據，並試圖從中確定該文件的類型，其原理與系統中的 file 命令非常類似，這些信息可以幫助判斷正在恢復的是什麼文件。
下面讓我們來看一個使用 e2undel 恢復文件系統的實例。
清單4. 使用 e2undel 恢復文件的實例
# ./e2undel -a -t -d /dev/sda2 -s /tmp/recover/ ./e2undel 0.82 Trying to recover files on /dev/sda2, saving them on /tmp/recover/ |
/dev/sda2 opened for read-only access /dev/sda2 was not cleanly unmounted. Do you want wo continue (y/n)? y 489600 inodes (489583 free) 977956 blocks of 4096 bytes (941677 free) last mounted on Fri Dec 28 16:21:50 2007 |
reading log file: opening log file: No such file or directory no entries for /dev/sda2 in log file searching for deleted inodes on /dev/sda2: |==================================================| 489600 inodes scanned, 26 deleted files found |
user name | 1 <12 h | 2 <48 h | 3 <7 d | 4 <30 d | 5 <1 y | 6 older -------------+---------+---------+---------+---------+---------+-------- root | 0 | 0 | 0 | 2 | 0 | 0 phost | 24 | 0 | 0 | 0 | 0 | 0 Select user name from table or press enter to exit: root Select time interval (1 to 6) or press enter to exit: 4 |
inode size deleted at name ----------------------------------------------------------- 13 35840 Dec 19 17:43 2007 * ASCII text 14 10485760 Dec 19 17:43 2007 * ASCII text Select an inode listed above or press enter to go back: 13 35840 bytes written to /tmp/recover//inode-13-ASCII_text Select an inode listed above or press enter to go back: |
user name | 1 <12 h | 2 <48 h | 3 <7 d | 4 <30 d | 5 <1 y | 6 older -------------+---------+---------+---------+---------+---------+-------- root | 0 | 0 | 0 | 2 | 0 | 0 phost | 24 | 0 | 0 | 0 | 0 | 0 Select user name from table or press enter to exit: # |
e2undel 是一個互動式的命令，命令執行過程中需要輸入的內容已經使用黑體表示出來了。從輸出結果中可以看出，e2undel 一共在這個文件系統中找到了 26 個文件，其中 root 用戶刪除的有兩個。這些文件按照刪除時間的先後順序被劃分到幾類中。索引節點號 13 對應的是一個 ASCII 正文的文本文件，最終被恢復到 /tmp/recover//inode-13-ASCII_text 文件中。查看一下這個文件就會發現，正是我們在本系列前兩部分中刪除的那個 35KB 的測試文件。
利用 libundel 庫完美恢復文件
儘管 e2undel 可以非常方便地簡化恢復文件的過程，但是美中不足的是，其恢復出來的文件的文件名卻丟失了，其原因是文件名是保存在父目錄的目錄項中的，而不是保存在索引節點中的。本系列文章第 2 部分中給出了一種通過遍歷父目錄的目錄項來查找已刪除文件的文件名的方法，但是由於索引節點會被重用，因此通過這種方式恢復出來的文件名也許並不總是正確的。另外，如果目錄結構的非常複雜，就很難確定某個文件的父目錄究竟是哪個，因此查找正確文件名的難度就會變得很大。如果能在刪除文件時記錄下索引節點號和文件名之間的對應關係，這個問題就能完美地解決了。
這個問題在 e2undel 中得到了完美的解決。實際上，所有刪除命令，例如 rm、unlink 都是通過一些底層的系統調用（例如 unlink(2)、rmdir(2)）來實現的。基於這一點，e2undel 又利用了Linux 系統中動態鏈接庫載入時提供的一種便利：如果設置了環境變數 LD_PRELOAD，那麼在載入動態鏈接庫時，會優先從 $LD_PRELOAD 指向的動態鏈接庫中查找符號表，然後才會在系統使用 ldconfig 配置的動態鏈接庫中繼續查找符號表。因此，我們可以在自己編寫的庫函數中實現一部分系統調用，並將這個庫優先於系統庫載入，這樣就能欺騙系統使用我們自己定義的系統調用來執行原有的操作。具體到 e2undel 上來說，就是要在調用這些系統調用刪除文件時，記錄下文件名和索引節點號之間的對應關係。
在編譯 e2undel 源代碼之後，還會生成一個庫文件 libundel.so.1.0，其中包含了刪除文件時所使用的一些系統調用的鉤子函數。e2undel官方主頁上下載的源碼包中僅僅包括了對 unlink(2) 和 remove(3) 這兩個系統調用的鉤子函數，但是從 2.6.16 版本的內核開始，引入了一系列新的系統調用，包括 faccessat(2), fchmodat(2), fchownat(2), fstatat(2), futimesat(2), linkat(2), mkdirat(2), mknodat(2), openat(2), readlinkat(2), renameat(2), symlinkat(2), unlinkat(2), mkfifoat(3) 等，儘管這些系統調用目前還沒有成為POSIX標準的一部分，但是相信這個過程不會很久了。目前諸如 Fecora Core 8 之類的系統中自帶的 rm 命令（屬於 coreutils）包已經使用這些新的系統調用進行了改寫，另外本文下載部分中的補丁文件中已經提供了對 rmdir 和 unlinkat 的鉤子函數。部分源代碼如下所示：
清單5. libundel.c 代碼片斷
void _init() { f = fopen("/var/e2undel/e2undel", "a"); if (!f) fprintf(stderr, "libundel: can't open log file, undeletion disabled\n"); } |
...... |
int rmdir(const char *pathname) { int err; struct stat buf; char pwd[PATH_MAX]; int (*rmdirp)(char *) = dlsym(RTLD_NEXT, "rmdir"); |
if (NULL != pathname) { if (__lxstat(3, pathname, &buf)) buf.st_ino = 0; if (!realpath(pathname, pwd)) pwd[0] = '\0'; } err = (*rmdirp)((char *) pathname); if (err) return err; /* remove() did not succeed */ if (f) { if (!S_ISLNK(buf.st_mode)) /* !!! should we check for other file types? */ { /* don't log deleted symlinks */ fprintf(f, "%ld,%ld::%ld::%s\n", (long) (buf.st_dev & 0xff00) / 256, (long) buf.st_dev & 0xff, (long) buf.st_ino, pwd[0] ? pwd : pathname); fflush(f); } } /* if (f) */ return err; } /* rmdir() */ |
...... |
void _fini() { if (f) fclose(f); } |
_init 和 _fini 這兩個函數分別在打開和關閉動態鏈接庫時執行，分別用來打開和關閉日誌文件。如果某個命令（例如 rm）執行了 rmdir 系統調用，就會被這個庫接管。rmdir 的處理比較簡單，它先搜索到真正的 rmdir 系統調用的符號表，然後使用同樣的參數來執行這個系統調用，如果成功，就將有關索引節點和文件名之類的信息記錄到日誌中（默認是 /var/e2undel/ e2undel）。
這個庫的使用非常簡單，請執行下面的命令：
清單6. libundel 的設置
# cp libundel.so.1.0 /usr/local/lib # cd /usr/local/lib # ln -s libundel.so.1.0 libundel.so.1 # ln –s libundel.so.1.0 libundel.so |
# ldconfig # mkdir /var/e2undel # chmod 711 /var/e2undel # touch /var/e2undel/e2undel # chmod 622 /var/e2undel/e2undel |
上面的設置僅僅允許 root 用戶可以恢復文件，如果希望讓普通用戶也能恢復文件，就需要修改對應文件的許可權設置。
現在嘗試以另外一個用戶的身份來刪除些文件：
清單7. 設置libundel之後刪除文件
$ export LD_PRELOAD=/usr/local/lib/libundel.so $ rm -rf e2undel-0.82 |
要想記錄所有用戶的刪除文件的操作，可以將 export LD_PRELOAD=/usr/local/lib/libundel.so 這行內容加入到 /etc/profile 文件中。
現在使用 e2undel 來恢復已刪除的文件就變得簡單多了，因為已經可以通過文件名來恢復文件了：
清單8. e2undel 利用 libundel 日誌恢復刪除文件
# ./e2undel -a -t -d /dev/sda2 -s /tmp/recover/ ./e2undel 0.82 Trying to recover files on /dev/sda2, saving them on /tmp/recover/ |
/dev/sda2 opened for read-only access /dev/sda2 was not cleanly unmounted. Do you want wo continue (y/n)? y 489600 inodes (489531 free) 977956 blocks of 4096 bytes (941559 free) last mounted on Fri Dec 28 20:45:05 2007 |
reading log file: found 24 entries for /dev/sda2 in log file searching for deleted inodes on /dev/sda2: |==================================================| 489600 inodes scanned, 26 deleted files found checking names from log file for deleted files: 24 deleted files with names |
user name | 1 <12 h | 2 <48 h | 3 <7 d | 4 <30 d | 5 <1 y | 6 older -------------+---------+---------+---------+---------+---------+-------- root | 0 | 0 | 0 | 2 | 0 | 0 phost | 24 | 0 | 0 | 0 | 0 | 0 Select user name from table or press enter to exit: phost Select time interval (1 to 6) or press enter to exit: 1 |
inode size deleted at name ----------------------------------------------------------- 310083 0 Dec 29 17:23 2007 /tmp/test/undel/e2undel-0.82 310113 2792 Dec 29 17:23 2007 /tmp/test/undel/e2undel-0.82/BUGS 310115 3268 Dec 29 17:23 2007 /tmp/test/undel/e2undel-0.82/HISTORY 310116 1349 Dec 29 17:23 2007 /tmp/test/undel/e2undel-0.82/INSTALL 310117 1841 Dec 29 17:23 2007 /tmp/test/undel/e2undel-0.82/INSTALL.de 310118 2175 Dec 29 17:23 2007 /tmp/test/undel/e2undel-0.82/Makefile 310119 12247 Dec 29 17:23 2007 /tmp/test/undel/e2undel-0.82/README 310120 9545 Dec 29 17:23 2007 /tmp/test/undel/e2undel-0.82/README.de 310121 13690 Dec 29 17:23 2007 /tmp/test/undel/e2undel-0.82/apprentice.c 310122 19665 Dec 29 17:23 2007 /tmp/test/undel/e2undel-0.82/ascmagic.c 310123 221 Dec 29 17:23 2007 /tmp/test/undel/e2undel-0.82/common.h 310124 1036 Dec 29 17:23 2007 /tmp/test/undel/e2undel-0.82/compactlog.c 310125 30109 Dec 29 17:23 2007 /tmp/test/undel/e2undel-0.82/e2undel.c 310127 2447 Dec 29 17:23 2007 /tmp/test/undel/e2undel-0.82/e2undel.h 310128 1077 Dec 29 17:23 2007 /tmp/test/undel/e2undel-0.82/file.c 310129 2080 Dec 29 17:23 2007 /tmp/test/undel/e2undel-0.82/file.h 310130 4484 Dec 29 17:23 2007 /tmp/test/undel/e2undel-0.82/find_del.c 310131 2141 Dec 29 17:23 2007 /tmp/test/undel/e2undel-0.82/is_tar.c 310132 2373 Dec 29 17:23 2007 /tmp/test/undel/e2undel-0.82/libundel.c 310133 7655 Dec 29 17:23 2007 /tmp/test/undel/e2undel-0.82/log.c 310134 39600 Dec 29 17:23 2007 /tmp/test/undel/e2undel-0.82/magic.h 310135 4591 Dec 29 17:23 2007 /tmp/test/undel/e2undel-0.82/names.h 310136 13117 Dec 29 17:23 2007 /tmp/test/undel/e2undel-0.82/softmagic.c 310137 5183 Dec 29 17:23 2007 /tmp/test/undel/e2undel-0.82/tar.h |
如果對所有用戶都打開這個功能，由於日誌文件是單向增長的，隨著時間的推移，可能會變得很大，不過 e2undel 中還提供了一個 compactlog 工具來刪除日誌文件中的重複項。
在學習本系列文章介紹的技術之後，利用 e2undel 之類的工具，並使用本系列文章第一部分中提供的補丁，恢復刪除文件就變得非常簡單了。但是在日常使用過程中，大家可能還會碰到一些意外的情況，比如文件系統發生問題，從而無法正常掛載；使用 mke2fs 之類的工具重做了文件系統；甚至磁碟上出現壞道。此時應該如何恢復系統中的文件呢，下面讓我們來逐一看一下如何解決這些問題。
|
文件系統故障的恢復
回想一下，在超級塊中保存了有關文件系統本身的一些數據，在 ext2 文件系統中，還使用塊組描述符保存了有關塊組的信息；另外，索引節點點陣圖、塊點陣圖中分別保存了索引節點和磁碟上數據塊的使用情況，而文件本身的索引節點信息（即文件的元數據）則保存在索引節點表中。這些數據對於文件系統來說都是至關重要的，它們是存取文件的基礎。如果超級塊和塊組描述符的信息一旦出錯，則會造成文件系統無法正常掛載的情況出現。造成這些信息出錯的原因有：
如果出現這種問題，可能造成的後果有：
下面讓我們來模擬一個出現這種錯誤的情況。我們知道，超級塊信息就保存在分區中的第一個塊中，現在我們來試驗一下清空這個塊中數據的後果：
清單9. 清空超級塊信息的後果
# dd if=/dev/zero of=/dev/sda2 bs=4096 count=1 |
# mount /dev/sda2 /tmp/test -t ext2 mount: wrong fs type, bad option, bad superblock on /dev/sda2, missing codepage or helper program, or other error In some cases useful info is found in syslog - try dmesg | tail or so |
由於無法從磁碟上讀取到有效的超級塊信息，mount 命令已經無法掛載 /dev/sda2 設備上的文件系統了。
為了防止這個問題會造成嚴重的後果，ext2 文件系統會在每個塊組中保存一份超級塊的拷貝。當然，這會造成一定的空間浪費，因此在最新的 ext2 文件系統中，只是在特定的塊組中保存一份超級塊的拷貝。具體來說，是在第 0、1 個塊組和第 3、5、7 的整數次冪個塊組中保存一份超級塊的拷貝，而其他塊組中的空間都可以節省出來了。下面來看一個 20GB 大小的文件系統的實際例子：
清單10. ext2 文件系統中超級塊拷貝的位置
# dumpe2fs /dev/sdb6 | grep -i superblock dumpe2fs 1.39 (29-May-2006) Primary superblock at 0, Group descriptors at 1-2 Backup superblock at 32768, Group descriptors at 32769-32770 Backup superblock at 98304, Group descriptors at 98305-98306 Backup superblock at 163840, Group descriptors at 163841-163842 Backup superblock at 229376, Group descriptors at 229377-229378 Backup superblock at 294912, Group descriptors at 294913-294914 Backup superblock at 819200, Group descriptors at 819201-819202 Backup superblock at 884736, Group descriptors at 884737-884738 Backup superblock at 1605632, Group descriptors at 1605633-1605634 Backup superblock at 2654208, Group descriptors at 2654209-2654210 Backup superblock at 4096000, Group descriptors at 4096001-4096002 |
這是一個 20GB 大的 ext2 文件系統，每個塊組的大小是 32768 個塊，超級塊一共有 11 個拷貝，分別存儲在第 0、1、3、5、7、9、25、27、49、81 和 125 個塊組中。默認情況下，內核只會使用第一個超級塊中的信息來對磁碟進行操作。在出現故障的情況下，就可以使用這些超級塊的備份來恢複數據了。具體說來，有兩種方法：首先 mount 命令可以使用 sb 選項指定備用超級塊信息來掛載文件系統：
清單11. 使用超級塊拷貝掛載文件系統
# mount -o sb=131072 /dev/sda2 /tmp/test -t ext2 |
需要注意的是，mount 命令中塊大小是以 1024 位元組為單位計算的，而這個文件系統則採用的是 4096 位元組為單位的塊，因此 sb 的值應該是 32768*4=131072。
儘管 mount 命令可以使用備用超級塊來掛載文件系統，但卻無法修復主超級塊的問題，這需要使用 e2fsck 這個工具來完成：
清單12. 利用 e2fsck 工具修復 ext2 文件系統中主超級塊的問題
# e2fsck /dev/sda2 e2fsck 1.40.2 (12-Jul-2007) Couldn't find ext2 superblock, trying backup blocks... /dev/sda2 was not cleanly unmounted, check forced. Pass 1: Checking inodes, blocks, and sizes Pass 2: Checking directory structure Pass 3: Checking directory connectivity Pass 4: Checking reference counts Pass 5: Checking group summary information /dev/sda2: ***** FILE SYSTEM WAS MODIFIED ***** /dev/sda2: 11/489600 files (9.1% non-contiguous), 17286/977956 blocks # mount /dev/sda2 /tmp/test -t ext2 |
e2fsck 工具可以檢查出主超級塊的問題，然後從其他超級塊拷貝中讀取數據，並使用它來恢復主超級塊中的數據（在 ext2 文件系統中，超級塊信息保存在一個 ext2_super_block 的數據結構中，詳細信息請參考內核源代碼）。修復主超級塊的問題之後，mount 命令就可以成功掛載原來的文件系統了。
|
重建文件系統的解決辦法
在日常使用過程中，可能碰到的另外一個問題是管理員可能錯誤地執行了某些命令，例如使用mke2fs 重建了文件系統，從而造成數據的丟失。實際上，在 mke2fs 創建文件系統的過程中，並不會真正去清空原有文件系統中存儲的文件的數據，但卻會重新生成超級塊、塊組描述符之類的信息，並清空索引節點點陣圖和塊點陣圖中的數據，最為關鍵的是，它還會清空索引節點表中的數據。因此儘管文件數據依然存儲在磁碟上，但是由於索引節點中存儲的文件元數據已經丟失了，要想完整地恢復原有文件，已經變得非常困難了。
然而，這個問題也並非完全無法解決。在 e2fsprogs 包中還提供了一個名為 e2image 的工具，可以用來將 ext2 文件系統中的元數據保存到一個文件中，下面是一個例子：
清單13. 使用超級塊拷貝掛載文件系統
# e2image -r /dev/sda2 sda2.e2image |
這會生成一個與文件系統大小相同的文件，其中包含了文件系統的元數據，包括索引節點中的間接塊數據以及目錄數據。另外，其中所有數據的位置均與磁碟上存儲的位置完全相同，因此可以使用 debugfs、dumpe2fs 之類的工具直接查看：
清單14. 使用 debugfs 查看 e2image 映像文件的信息
# debugfs sda2.e2image.raw debugfs 1.40.2 (12-Jul-2007) debugfs: ls -l 2 40755 (2) 0 0 4096 31-Dec-2007 15:56 . 2 40755 (2) 0 0 4096 31-Dec-2007 15:56 .. 11 40700 (2) 0 0 16384 31-Dec-2007 15:54 lost+found 12 100644 (1) 0 0 10485760 31-Dec-2007 15:56 testfile.10M 13 100644 (1) 0 0 35840 31-Dec-2007 15:56 testfile.35K |
為了節省空間，這些映像文件以稀疏文件的形式保存在磁碟上，在一個 4GB 的文件系統中，如果 55 萬個索引節點中已經使用了 1 萬 5 千個，使用 bizp2 壓縮后的文件大概只有 3MB左右。
當然，這些映像文件中並沒有包含實際文件的數據，不過文件數據依然保存在磁碟上，因此只要及時備份相關信息，在發生意外的情況下是有可能恢復大部分數據的。
|
磁碟壞道情況的處理
隨著磁碟使用的時間越來越長，難免會出現磁碟上出現一些物理故障，比如產生物理壞道。根據物理損壞的嚴重程度，可能會造成文件丟失、文件系統無法載入甚至整個磁碟都無法識別的情況出現。因此要想將損失控制在最小範圍內，除了經常備份數據，在發現問題的第一時間採取及時地應對措施也非常重要。
物理故障一旦出現，極有可能會有加劇趨勢，因此應該在恢複數據的同時，盡量減少對磁碟的使用，dd 命令可以用來創建磁碟的完美映像。應該使用的命令如下：
清單15. 使用 dd 命令創建磁碟映像
# dd if=/dev/sdb of=/images/sdb.image bs=4096 conv=noerror,sync |
noerror 參數告訴 dd 在碰到讀寫錯（可能是由於壞道引起的）時繼續向下操作，而不是停止退出。sync 參數說明對於從源設備無法正常讀取的塊，就使用NULL填充。默認情況下，dd 使用 512 位元組作為一個塊的單位來讀寫 I/O 設備，指定 bs 為 4096 位元組可以在一定程度上加速 I/O 操作，但同時也會造成一個問題：如果所讀取的這個 4096 位元組為單位的數據塊中某一部分出現問題，則整個 4096 位元組的就全部被清空了，這樣會造成數據的丟失。為了解決這種問題，我們可以使用 dd_rescue 這個工具（可以從 http://www.garloff.de/kurt/linux/ddrescue/ 上下載），其用法如下：
清單16. 使用 dd_rescue 命令創建磁碟映像
# dd_rescue /dev/sdb /images/sdb.image –b 65536 –B 512 |
與 dd 相比，dd_rescue 強大之處在於在碰到錯誤時，可以以更小的數據塊為單位重新讀取這段數據，從而確保能夠讀出盡量多的數據。上面命令中的參數指明正常操作時以 64KB 為單位讀取磁碟數據，一旦出錯，則以 512 位元組為單位重新讀取這段數據，直至整個硬碟被完整讀出為止。
獲得磁碟映像之後，就可以將其當作普通磁碟一樣進行操作了。應用本系列文章中介紹的技術，應該能從中恢復出儘可能多的數據。當然，對於那些剛好處於坏道位置的數據，那就實在回天乏力了。
|
恢復文件策略
截至到現在，本系列文章中介紹的都是在刪除文件或出現意外情況之後如何恢復文件，實際上，對於保證數據可用性的目的來講，這些方法都無非是亡羊補牢而已。制定恰當地數據備份策略，並及時備份重要數據才是真正的解決之道。
不過即使有良好的數據備份策略，也難免會出現有部分數據沒有備份的情況。因此，一旦出現誤刪文件的情況，應該立即執行相應的對策，防止文件數據被覆蓋：
當然，在進行數據備份的同時，也需要考慮本文中介紹的一些技術本身的要求，例如 e2image映像文件、e2undel 的日誌文件等，都非常重要，值得及時備份。
|
小結
本文介紹了一個功能非常強大的工具 e2undel，可以用來方便地恢復已刪除的文件。然後討論了文件系統故障、文件系統重建、磁碟物理損壞等情況下應該如何恢複數據。隨著文件系統的不斷發展，Linux 上常用的文件系統也越來越多，例如 ext3/ext4/reiserfs/jfs 等，這些文件系統上刪除的文件能否成功恢復呢？有哪些工具可以用來輔助恢復文件呢？本系列後續文章將繼續探討這個問題。
作為 ext2 文件系統的後繼者，ext3 文件系統由於日誌的存在，使其可用性大大增加。儘管 ext3 文件系統可以完全兼容 ext2 文件系統，但是由於關鍵的一點區別卻使得在 ext3 上恢復刪除文件變得異常困難。本文將逐漸探討其中的原因，並給出了三種解決方案：正文匹配，元數據備份，以及修改 ext3 的實現。
本系列文章的前 3 部分詳細介紹了 ext2 文件系統中文件的數據存儲格式，並討論了各種情況下數據恢復的問題。作為 ext2 文件系統的後繼者，ext3 文件系統可以實現與 ext2 文件系統近乎完美的兼容。但是前文中介紹的各種技術在 ext3 文件系統中是否同樣適用呢？ext3 文件系統中刪除文件的恢復又有哪些特殊之處呢？本文將逐一探討這些問題。
ext3：日誌文件系統
由於具有很好的文件存取性能，ext2 文件系統自從 1993 年發布之後，已經迅速得到了用戶的青睞，成為很多 Linux 發行版中預設的文件系統，原因之一在於 ext2 文件系統採用了文件系統緩存的概念，可以加速文件的讀寫速度。然而，如果文件系統緩存中的數據尚未寫入磁碟，機器就發生了掉電等意外狀況，就會造成磁碟數據不一致的狀態，這會損壞磁碟數據的完整性（文件數據與元數據不一致），嚴重情況下甚至會造成文件系統的崩潰。
為了確保數據的完整性，在系統引導時，會自動檢查文件系統上次是否是正常卸載的。如果是非正常卸載，或者已經使用到一定的次數，就會自動運行 fsck 之類的程序強制進行一致性檢查（具體例子請參看本系列文章的第 2 部分），並修復存在問題的地方，使 ext2 文件系統恢復到新的一致狀態。
然而，隨著硬碟技術的發展，磁碟容量變得越來越大，對磁碟進行一致性檢查可能會佔用很長時間，這對於一些關鍵應用來說是不可忍受的；於是日誌文件系統（Journal File System）的概念也就應運而生了。
所謂日誌文件系統，就是在文件系統中借用了資料庫中“事務”（transaction）的概念，將文件的更新操作變成原子操作。具體來說，就是在修改文件系統內容的同時（或之前），將修改變化記錄到日誌中，這樣就可以在意外發生的情況下，就可以根據日誌將文件系統恢復到一致狀態。這些操作完全可以在重新掛載文件系統時來完成，因此在重新啟動機器時，並不需要對文件系統再進行一致性檢查，這樣可以大大提高系統的可用程度。
Linux 系統中目前已經出現了很多日誌文件系統，例如 SGI 開發的 XFS、IBM 開發的 JFS 和 ReiserFS 以及 ext3 等。與其他日誌文件系統相比，ext3 最大的特性在於它完全兼容 ext2 文件系統。用戶可以在 ext2 和 ext3 文件系統之間無縫地進行變換，二者在磁碟上採用完全相同的的數據格式進行存儲，因此大部分支持 ext2 文件系統的工具也都可以在 ext3 文件系統上使用。甚至為 ext2 開發的很多特性也都可以非常平滑地移植到 ext3 文件系統上來。ext3 文件系統的另外一個特性在於它提供了 3 種日誌模式，可以滿足各種不同用戶的要求：
在重新掛載文件系統時，系統會自動檢查日誌項，將尚未提交到磁碟上的操作重新寫入磁碟，從而確保文件系統的狀態與最後一次操作的結果保持一致。
  |
ext3 文件系統探索
下面讓我們通過一個例子來了解一下 ext3 文件系統中有關日誌的一些詳細信息。
# mkfs.ext3 /dev/sdb7 mke2fs 1.39 (29-May-2006) Filesystem label= OS type: Linux Block size=4096 (log=2) Fragment size=4096 (log=2) 2443200 inodes, 4885760 blocks 244288 blocks (5.00%) reserved for the super user First data block=0 Maximum filesystem blocks=0 150 block groups 32768 blocks per group, 32768 fragments per group 16288 inodes per group Superblock backups stored on blocks: 32768, 98304, 163840, 229376, 294912, 819200, 884736, 1605632, 2654208, 4096000 Writing inode tables: done Creating journal (32768 blocks): done Writing superblocks and filesystem accounting information: done This filesystem will be automatically checked every 27 mounts or 180 days, whichever comes first. Use tune2fs -c or -i to override. |
在清單 1 中，我們使用 mkfs.ext3 創建了一個 ext3 類型的文件系統，與 ext2 文件系統相比，mkfs.ext3 命令額外在文件系統中使用 32768 個數據塊創建了日誌。實際上，ext2 文件系統可以使用 tune2fs 命令平滑地轉換成 ext3 文件系統，用法如清單 2 所示。
# tune2fs -j /dev/sdb6 tune2fs 1.39 (29-May-2006) Creating journal inode: done This filesystem will be automatically checked every 28 mounts or 180 days, whichever comes first. Use tune2fs -c or -i to override. |
類似地，dumpe2fs 命令也可以用來查看有關 ext3 文件系統的信息：
# dumpe2fs /dev/sdb7 | grep "Group 0" -B 10 -A 21 dumpe2fs 1.39 (29-May-2006) Reserved blocks gid: 0 (group root) First inode: 11 Inode size: 128 Journal inode: 8 Default directory hash: tea Directory Hash Seed: 69de4e53-27fc-42db-a9ea-36debd6e68de Journal backup: inode blocks Journal size: 128M 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) 0 free blocks, 16277 free inodes, 2 directories Free blocks: Free inodes: 12-16288 Group 1: (Blocks 32768-65535) Backup superblock at 32768, Group descriptors at 32769-32770 Reserved GDT blocks at 32771-33792 Block bitmap at 33793 (+1025), Inode bitmap at 33794 (+1026) Inode table at 33795-34303 (+1027) 29656 free blocks, 16288 free inodes, 0 directories Free blocks: 35880-65535 Free inodes: 16289-32576 Group 2: (Blocks 65536-98303) Block bitmap at 65536 (+0), Inode bitmap at 65537 (+1) Inode table at 65538-66046 (+2) 32257 free blocks, 16288 free inodes, 0 directories Free blocks: 66047-98303 Free inodes: 32577-48864 |
從清單 3 中的輸出結果可以看出，這個文件系統上的日誌一共佔用了 128MB 的空間，日誌文件使用索引節點號為 8，塊組 0 和塊組 1 中空閑塊比其他塊組明顯要少，這是因為日誌文件主要就保存在這兩個塊組中了，這一點可以使用 debugfs 來驗證：
# debugfs /dev/sdb7 debugfs 1.39 (29-May-2006) debugfs: stat <8> Inode: 8 Type: regular Mode: 0600 Flags: 0x0 Generation: 0 User: 0 Group: 0 Size: 134217728 File ACL: 0 Directory ACL: 0 Links: 1 Blockcount: 262416 Fragment: Address: 0 Number: 0 Size: 0 ctime: 0x4795d200 -- Tue Jan 22 19:22:40 2008 atime: 0x00000000 -- Thu Jan 1 08:00:00 1970 mtime: 0x4795d200 -- Tue Jan 22 19:22:40 2008 BLOCKS: (0-11):1542-1553, (IND):1554, (12-1035):1555-2578, (DIND):2579, \ (IND):2580, (1036-2059):2581-3604, (IND):3605, (2060-3083):3606-4629 , (IND):4630, (3084-4107):4631-5654, (IND):5655, (4108-5131):5656-6679, \ (IND):6680, (5132-6155):6681-7704, (IND):7705, (6156-7179):7 706-8729, (IND):8730, (7180-8203):8731-9754, (IND):9755, (8204-9227):9756-10779, \ (IND):10780, (9228-10251):10781-11804, (IND):11805, (10252-11275):11806-12829, (IND):12830, (11276-12299):12831-13854, \ (IND):13855, (12300-13323):13856-14879, (IND):14880, (13324-1434 7):14881-15904, (IND):15905, (14348-15371):15906-16929, \ (IND):16930, (15372-16395):16931-17954, (IND):17955, (16396-17419):17956-189 79, (IND):18980, (17420-18443):18981-20004, (IND):20005, (18444-19467):20006-21029, \ (IND):21030, (19468-20491):21031-22054, (IND):22 055, (20492-21515):22056-23079, (IND):23080, (21516-22539):23081-24104, \ (IND):24105, (22540-23563):24106-25129, (IND):25130, (23564- 24587):25131-26154, (IND):26155, (24588-25611):26156-27179, \ (IND):27180, (25612-26635):27181-28204, (IND):28205, (26636-27659):28206 -29229, (IND):29230, (27660-28683):29231-30254, (IND):30255, \ (28684-29707):30256-31279, (IND):31280, (29708-30731):31281-32304, (IND ):32305, (30732-31193):32306-32767, (31194-31755):34304-34865, \ (IND):34866, (31756-32768):34867-35879 TOTAL: 32802 debugfs:. |
另外，ext3 的日誌文件也可以單獨存儲到其他設備上。但是無論如何，這對於用戶來說都是透明的，用戶根本就覺察不到日誌文件的存在，只是內核在掛載文件系統時會檢查日誌文件的內容，並採取相應的操作，使文件系統恢復到最後一次操作時的一致狀態。
對於恢復刪除文件的目的來說，我們並不需要關心日誌文件，真正應該關心的是文件在磁碟上的存儲格式。實際上，ext3 在這方面完全兼容 ext2，以存儲目錄項和索引節點使用的數據結構為例，ext3 使用的兩個數據結構 ext3_dir_entry_2 和 ext3_inode 分別如清單 5 和清單 6 所示。與 ext2 的數據結構對比一下就會發現，二者並沒有什麼根本的區別，這正是 ext2 和 ext3 文件系統可以實現自由轉換的基礎。
/* * The new version of the directory entry. Since EXT3 structures are * stored in intel byte order, and the name_len field could never be * bigger than 255 chars, it's safe to reclaim the extra byte for the * file_type field. */ struct ext3_dir_entry_2 { __le32 inode; /* Inode number */ __le16 rec_len; /* Directory entry length */ __u8 name_len; /* Name length */ __u8 file_type; char name[EXT3_NAME_LEN]; /* File name */ }; |
/* * Structure of an inode on the disk */ struct ext3_inode { __le16 i_mode; /* File mode */ __le16 i_uid; /* Low 16 bits of Owner Uid */ __le32 i_size; /* Size in bytes */ __le32 i_atime; /* Access time */ __le32 i_ctime; /* Creation time */ __le32 i_mtime; /* Modification time */ __le32 i_dtime; /* Deletion Time */ __le16 i_gid; /* Low 16 bits of Group Id */ __le16 i_links_count; /* Links count */ __le32 i_blocks; /* Blocks count */ __le32 i_flags; /* File flags */ ... __le32 i_block[EXT3_N_BLOCKS];/* Pointers to blocks */ ... }; |
既然 ext3 與 ext2 文件系統有這麼好的兼容性和相似性，這是否就意味著本系列文章前 3 部分介紹的各種技術同樣也適用於 ext3 文件系統呢？對於大部分情況來說，答案是肯定的。ext3 與 ext2 文件系統存儲文件所採用的機制並沒有什麼不同，第 1 部分中介紹的原理以及後續介紹的 debugfs 等工具也完全適用於 ext3 文件系統。
然而，這並非就說 ext3 與 ext2 文件系統是完全相同的。讓我們來看一個例子：清單 7 給出了在 ext3 文件系統中刪除一個文件前後索引節點的變化。
# debugfs /dev/sdb7 debugfs 1.39 (29-May-2006) debugfs: stat <48865> Inode: 48865 Type: regular Mode: 0644 Flags: 0x0 Generation: 3736765465 User: 0 Group: 0 Size: 61261 File ACL: 99840 Directory ACL: 0 Links: 1 Blockcount: 136 Fragment: Address: 0 Number: 0 Size: 0 ctime: 0x478618e1 -- Thu Jan 10 21:08:49 2008 atime: 0x478618e1 -- Thu Jan 10 21:08:49 2008 mtime: 0x478618e1 -- Thu Jan 10 21:08:49 2008 BLOCKS: (0-11):129024-129035, (IND):129036, (12-14):129037-129039 TOTAL: 16 debugfs: q # rm -f Home.html # sync # cd .. # umount test # debugfs /dev/sdb7 debugfs 1.39 (29-May-2006) debugfs: lsdel Inode Owner Mode Size Blocks Time deleted 0 deleted inodes found. debugfs: stat <48865> Inode: 48865 Type: regular Mode: 0644 Flags: 0x0 Generation: 3736765465 User: 0 Group: 0 Size: 0 File ACL: 99840 Directory ACL: 0 Links: 0 Blockcount: 0 Fragment: Address: 0 Number: 0 Size: 0 ctime: 0x47861900 -- Thu Jan 10 21:09:20 2008 atime: 0x478618e1 -- Thu Jan 10 21:08:49 2008 mtime: 0x47861900 -- Thu Jan 10 21:09:20 2008 dtime: 0x47861900 -- Thu Jan 10 21:09:20 2008 BLOCKS: debugfs: q |
仔細看一下結果就會發現，在刪除文件之後，除了設置了刪除時間 dtime 之外，還將文件大小（size）設置為 0，佔用塊數（Blockcount）也設置為 0，並清空了存儲文件數據的數據（i_block 數組）。這正是 ext3 文件系統與 ext2 文件系統在刪除文件時最重要的一點的區別：在刪除文件時，對於 ext2 文件系統來說，操作系統只是簡單地修改對應索引節點中的刪除時間，並修改索引節點點陣圖和數據塊點陣圖中的標誌，表明它們已經處於空閑狀態，可以被重新使用；而對於 ext3 文件系統來說，還清除了表明數據塊存放位置的欄位（i_block），並將索引節點中的文件大小信息設置為 0。然而，這點區別對於恢復被刪除文件的用途來說卻是至關重要的，因為缺少了文件大小和數據塊位置的信息，儘管文件數據依然完好地保存在磁碟上，但卻沒有任何一條清晰的線索能夠說明這個文件的數據塊被存儲到哪些磁碟塊中，以及這些數據塊的相互順序如何，文件中間是否存在文件洞等信息，因此要想完整地恢復文件就變得非常困難了。這也正是使用 debugfs 的 dump 命令在 ext3 文件系統中並不能恢復已刪除文件的原因。
不過，這是否就意味著 ext3 文件系統中刪除的文件就無法恢復了呢？其實不然。基於這樣一個事實：“在刪除文件時，並不會將文件數據真正從磁碟上刪除”，我們可以採用其他一些方法來嘗試恢複數據。
|
ext3 文件系統中恢復刪除文件的方法 1：正文匹配
我們知道，磁碟以及磁碟上的某個分區在系統中都以設備文件的形式存在，我們可以將這些設備文件當作普通文件一樣來讀取數據。不過，既然已經無法通過文件名來定位文件的數據塊位置，現在要想恢復文件，就必須了解文件的數據，並通過正文匹配進行檢索了。自然，grep 就是這樣一個理想的工具：
# ./creatfile.sh 35 testfile.35K # rm -f testfile.35K # cd .. # umount test # grep -A 1 -B 1 -a -n " 10:0" /dev/sdb7 > sdb7.testfile.35K grep: memory exhausted # cat sdb7.testfile.35K 545- 9:0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 546: 10:0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 547- 11:0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, |
在清單 8 中的例子中，我們首先使用本系列文章第 1 部分中提供的腳本創建了一個測試文件，在刪除該文件后，通過利用 grep 以“ 10:0”作為關鍵字對設備文件進行正文匹配，我們順利地找到了測試文件中的第 10 行數據。需要注意的是，grep 命令中我們使用了幾個參數，-a 參數表明將設備文件當作文本文件進行處理，-B 和 –A 參數分別說明同時列印匹配項的前/後幾行的數據。同一關鍵字可能會在很多文件中多次出現，因此如何從中挑選出所需的數據就完全取決於對數據的熟悉程度了。
利用 grep 進行正文匹配也存在一個問題，由於打開的設備文件非常大，grep 會產生內存不足的問題，因此無法完成整個設備的正文匹配工作。解決這個問題的方法是使用 strings。strings 命令可以將文件中所有可列印字元全部列印出來，因此對於正文匹配的目的來說，它可以很好地實現文本數據的提取工作。
# time strings /dev/sdb7 > sdb7.strings real 12m42.386s user 10m44.140s sys 1m42.950s # grep " 10:0" sdb7.strings 10:0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ, |
清單 9 中的例子使用 strings 將 /dev/sdb7 中的可列印字元提取出來，並重定向到一個文本文件中，此後就可以使用任何文本編輯工具或正文匹配工具從這個文件中尋找自己的數據了。不過掃描磁碟需要的時間可能會比較長，在上面這個例子中，掃描 20GB 的分區大概需要 13 分鐘。
|
ext3 文件系統中恢復刪除文件的方法 2：提前備份元數據
利用 grep 或 strings 對磁碟數據進行正文匹配，這種方法有一定的局限性：它只是對文本文件的恢複比較有用，這還要依賴於用戶對數據的熟悉程度；而對於二進位文件來說，除非有其他備份，否則要通過這種正文匹配的方式來恢復文件，幾乎是不可能完成的任務。然而，如果沒有其他機制的輔助，在 ext3 文件系統中，這卻幾乎是唯一可以嘗試用來恢複數據的方法了。究其原因是因為，這種方法僅僅是一種亡羊補牢的做法，而所需要的一些關鍵數據已經不存在了，因此恢復文件就變得愈發困難了。不過，索引節點中的這些關鍵信息在刪除文件之前肯定是存在的。
受本系列文章介紹過的 debugfs 和 libundel 的啟發，我們可以對 libundel 進行擴充，使其在刪除文件的同時，除了記錄文件名、磁碟設備、索引節點信息之外，把文件大小、數據塊位置等重要信息也同時記錄下來，這樣就可以根據日誌文件中的元數據信息完美地恢復文件了。
為了實現以上想法，我們需要對 libundel 的實現進行很大的調整，下面介紹所使用的幾個關鍵的函數。
static unsigned long get_bmap(int fd, unsigned long block) { int ret; unsigned int b; b = block; ret = ioctl(fd, FIBMAP, &b); /* FIBMAP takes a pointer to an integer */ if (ret < 0) { if (errno == EPERM) { if (f) { { /* don't log deleted symlinks */ fprintf(f, "No permission to use FIBMAP ioctl.\n"); fflush(f); } } /* if (f) */ return 0; } } return b; } |
get_bmap 函數是整個改進的基礎，其作用是返回磁碟上保存指定文件的某塊數據使用的數據塊的位置，這是通過 ioctl 的 FIBMAP 命令來實現的。ioctl 提供了一種在用戶空間與內核進行交互的便捷機制，在內核中會通過調用 f_op->ioctl() 進行處理。對於 FIBMAP 命令來說，會由 VFS 調用 f_op->bmap() 獲取指定數據塊在磁碟上的塊號，並將結果保存到第 3 個參數指向的地址中。
int get_blocks(const char *filename) { #ifdef HAVE_FSTAT64 struct stat64 fileinfo; #else struct stat fileinfo; #endif int bs; long fd; unsigned long block, last_block = 0, first_cblock = 0, numblocks, i; long bpib; /* Blocks per indirect block */ char cblock_list[256]; char pwd[PATH_MAX]; if (NULL != filename) { if (__lxstat(3, filename, &fileinfo)) fileinfo.st_ino = 0; if (!realpath(filename, pwd)) pwd[0] = '\0'; } #ifdef HAVE_OPEN64 fd = open64(filename, O_RDONLY); #else fd = open(filename, O_RDONLY); #endif if (fd < 0) { fprintf(stderr, "cannot open the file of %s\n", filename); return -1; } if (ioctl(fd, FIGETBSZ, &bs) < 0) { /* FIGETBSZ takes an int */ perror("FIGETBSZ"); close(fd); return -1; } bpib = bs / 4; numblocks = (fileinfo.st_size + (bs-1)) / bs; sprintf(block_list, "%ld,%ld::%ld::%ld::%ld::", (long) (fileinfo.st_dev & 0xff00) / 256, (long) fileinfo.st_dev & 0xff, (long) fileinfo.st_ino, (long) fileinfo.st_size, (long)bs); for (i=0; i < numblocks; i++) { block = get_bmap(fd, i); if (last_block == 0) { first_cblock = block; } if (last_block && (block != last_block +1) ) { sprintf(cblock_list, "(%ld-%ld):%ld-%ld,", i-(last_block-first_cblock)-1, i-1, first_cblock, last_block); strcat(block_list, cblock_list); first_cblock = block; } if (i == numblocks - 1 ) { if (last_block == 0) { sprintf(cblock_list, "(%ld-%ld):%ld-%ld", i, i, first_cblock, block); } else { sprintf(cblock_list, "(%ld-%ld):%ld-%ld", i-(last_block-first_cblock)-1, i, first_cblock, block); } strcat(block_list, cblock_list); } last_block = block; } sprintf(cblock_list, "::%s", pwd[0] ? pwd : filename); strcat(block_list, cblock_list); close(fd); return 0; } |
get_blocks 函數的作用是遍歷文件包含的每個數據塊，獲取它們在磁碟上保存的數據塊位置。為了保證日誌文件中的數據盡量精簡，數據塊位置會按照本身的連續情況被劃分成一個個的連續塊域，每個都記錄為下面的形式：(文件中的起始塊號-文件中的結束塊號):磁碟上的起始數據塊號-磁碟上的結束數據塊號。
自然，get_blocks 函數應該是在用戶調用刪除文件的系統調用時被調用的，這些系統調用的實現也應該進行修改。清單 12 給出了 remove 庫函數修改後的例子。
int remove(const char *pathname) { int err; int (*removep)(char *) = dlsym(RTLD_NEXT, "remove"); err = get_blocks(pathname); if (err < 0) { fprintf(stderr, "error while reading blocks from %s\n", pathname); } err = (*removep)((char *) pathname); if (err) return err; /* remove() did not succeed */ if (f) { fprintf(f, "%s\n", block_list); fflush(f); } /* if (f) */ return err; } /* remove() */ |
現在，記錄元數據信息的日誌文件 /var/e2undel/e2undel 如清單 13 所示：
8,23::48865::13690::4096::(0-3):106496-106499::/tmp/test/apprentice.c 8,23::48867::19665::4096::(0-4):106528-106532::/tmp/test/ascmagic.c 8,23::48872::1036::4096::(0-0):106545-106545::/tmp/test/compactlog.c 8,23::48875::31272::4096::(0-7):106596-106603::/tmp/test/e2undel.c 8,23::48878::1077::4096::(0-0):106616-106616::/tmp/test/file.c 8,23::48880::4462::4096::(0-1):106618-106619::/tmp/test/find_del.c 8,23::48885::2141::4096::(0-0):106628-106628::/tmp/test/is_tar.c 8,23::48887::6540::4096::(0-1):106631-106632::/tmp/test/libundel.c 8,23::48890::8983::4096::(0-2):106637-106639::/tmp/test/log.c 8,23::48897::13117::4096::(0-3):106663-106666::/tmp/test/softmagic.c 8,23::48866::10485760::4096::(0-11):108544-108555,(12-1035):108557-109580,\ (1036-2059):109583-110606,(2060-2559):110608-111107::/tmp/test/testfile.10M 8,23::48866::7169::4096::(1-1):129024-129024::/tmp/test/hole 8,23::48865::21505::4096::(1-1):129025-129025,(5-5):129026-129026::/tmp/test/hole2 |
文件名前所增加的 3 項分別為文件大小、塊大小和數據塊列表。
當然，為了能夠利用 /var/e2undel/e2undel 中記錄的信息恢復文件，e2undel 的對應實現也必須相應地進行修改。詳細實現請參看本文下載部分給出的補丁，在此不再詳述。修改後的 libundel 的用法與原來完全相同，詳細介紹請參看本系列文章的第 3 部分。
|
ext3 文件系統中恢復刪除文件的方法 3：修改 ext3 實現
利用 libundel 方法的確可以完美地恢復刪除文件，但是這畢竟是一種治標不治本的方法，就像是本系列文章第 3 部分中所介紹的一樣，這要依賴於環境變數 LD_PRELOAD 的設置。如果用戶在刪除文件之前，並沒有正確設置這個環境變數，那麼對應的刪除操作就不會記錄到日誌文件 /var/e2undel/e2undel 中，因此也就無從恢復文件了。
還記得在本系列文章的第 2 部分中我們是如何通過修改 Linux 內核來支持大文件的刪除的 嗎？採用同樣的思路，我們也可以修改 ext3 的實現，使其支持文件的恢復，這樣本系列前面文章中介紹的工具就都可以在 ext3 文件系統上正常使用了。
總結一下，在刪除文件時，內核中執行的操作至少包括：
其中步驟 5 和 6 只適用於 ext3 文件系統，在 ext2 文件系統中並不需要執行。在 ext3 文件系統的實現中，它們分別是由 fs/ext3/inode.c 中的 ext3_delete_inode 和 ext3_truncate 函數實現的：
182 void ext3_delete_inode (struct inode * inode) 183 { 184 handle_t *handle; 185 186 truncate_inode_pages(&inode->i_data, 0); 187 188 if (is_bad_inode(inode)) 189 goto no_delete; 190 191 handle = start_transaction(inode); 192 if (IS_ERR(handle)) { 193 /* 194 * If we're going to skip the normal cleanup, we still need to 195 * make sure that the in-core orphan linked list is properly 196 * cleaned up. 197 */ 198 ext3_orphan_del(NULL, inode); 199 goto no_delete; 200 } 201 202 if (IS_SYNC(inode)) 203 handle->h_sync = 1; 204 inode->i_size = 0; 205 if (inode->i_blocks) 206 ext3_truncate(inode); 207 /* 208 * Kill off the orphan record which ext3_truncate created. 209 * AKPM: I think this can be inside the above `if'. 210 * Note that ext3_orphan_del() has to be able to cope with the 211 * deletion of a non-existent orphan - this is because we don't 212 * know if ext3_truncate() actually created an orphan record. 213 * (Well, we could do this if we need to, but heck - it works) 214 */ 215 ext3_orphan_del(handle, inode); 216 EXT3_I(inode)->i_dtime = get_seconds(); 217 218 /* 219 * One subtle ordering requirement: if anything has gone wrong 220 * (transaction abort, IO errors, whatever), then we can still 221 * do these next steps (the fs will already have been marked as 222 * having errors), but we can't free the inode if the mark_dirty 223 * fails. 224 */ 225 if (ext3_mark_inode_dirty(handle, inode)) 226 /* If that failed, just do the required in-core inode clear. */ 227 clear_inode(inode); 228 else 229 ext3_free_inode(handle, inode); 230 ext3_journal_stop(handle); 231 return; 232 no_delete: 233 clear_inode(inode); /* We must guarantee clearing of inode... */ 234 } |
2219 void ext3_truncate(struct inode *inode) 2220 { 2221 handle_t *handle; 2222 struct ext3_inode_info *ei = EXT3_I(inode); 2223 __le32 *i_data = ei->i_data; 2224 int addr_per_block = EXT3_ADDR_PER_BLOCK(inode->i_sb); 2225 struct address_space *mapping = inode->i_mapping; 2226 int offsets[4]; 2227 Indirect chain[4]; 2228 Indirect *partial; 2229 __le32 nr = 0; 2230 int n; 2231 long last_block; 2232 unsigned blocksize = inode->i_sb->s_blocksize; 2233 struct page *page; 2234 ... 2247 if ((inode->i_size & (blocksize - 1)) == 0) { 2248 /* Block boundary? Nothing to do */ 2249 page = NULL; 2250 } else { 2251 page = grab_cache_page(mapping, 2252 inode->i_size >> PAGE_CACHE_SHIFT); 2253 if (!page) 2254 return; 2255 } 2256 2257 handle = start_transaction(inode); 2258 if (IS_ERR(handle)) { 2259 if (page) { 2260 clear_highpage(page); 2261 flush_dcache_page(page); 2262 unlock_page(page); 2263 page_cache_release(page); 2264 } 2265 return; /* AKPM: return what? */ 2266 } 2267 2268 last_block = (inode->i_size + blocksize-1) 2269 >> EXT3_BLOCK_SIZE_BITS(inode->i_sb); 2270 2271 if (page) 2272 ext3_block_truncate_page(handle, page, mapping, inode->i_size); 2273 2274 n = ext3_block_to_path(inode, last_block, offsets, NULL); 2275 if (n == 0) 2276 goto out_stop; /* error */ ... 2287 if (ext3_orphan_add(handle, inode)) 2288 goto out_stop; 2289 ... 2297 ei->i_disksize = inode->i_size; ... 2303 mutex_lock(&ei->truncate_mutex); 2304 2305 if (n == 1) { /* direct blocks */ 2306 ext3_free_data(handle, inode, NULL, i_data+offsets[0], 2307 i_data + EXT3_NDIR_BLOCKS); 2308 goto do_indirects; 2309 } 2310 2311 partial = ext3_find_shared(inode, n, offsets, chain, &nr); 2312 /* Kill the top of shared branch (not detached) */ 2313 if (nr) { 2314 if (partial == chain) { 2315 /* Shared branch grows from the inode */ 2316 ext3_free_branches(handle, inode, NULL, 2317 &nr, &nr+1, (chain+n-1) - partial); 2318 *partial->p = 0; 2319 /* 2320 * We mark the inode dirty prior to restart, 2321 * and prior to stop. No need for it here. 2322 */ 2323 } else { 2324 /* Shared branch grows from an indirect block */ 2325 BUFFER_TRACE(partial->bh, "get_write_access"); 2326 ext3_free_branches(handle, inode, partial->bh, 2327 partial->p, 2328 partial->p+1, (chain+n-1) - partial); 2329 } 2330 } 2331 /* Clear the ends of indirect blocks on the shared branch */ 2332 while (partial > chain) { 2333 ext3_free_branches(handle, inode, partial->bh, partial->p + 1, 2334 (__le32*)partial->bh->b_data+addr_per_block, 2335 (chain+n-1) - partial); 2336 BUFFER_TRACE(partial->bh, "call brelse"); 2337 brelse (partial->bh); 2338 partial--; 2339 } 2340 do_indirects: 2341 /* Kill the remaining (whole) subtrees */ 2342 switch (offsets[0]) { 2343 default: 2344 nr = i_data[EXT3_IND_BLOCK]; 2345 if (nr) { 2346 ext3_free_branches(handle, inode, NULL, &nr, &nr+1, 1); 2347 i_data[EXT3_IND_BLOCK] = 0; 2348 } 2349 case EXT3_IND_BLOCK: 2350 nr = i_data[EXT3_DIND_BLOCK]; 2351 if (nr) { 2352 ext3_free_branches(handle, inode, NULL, &nr, &nr+1, 2); 2353 i_data[EXT3_DIND_BLOCK] = 0; 2354 } 2355 case EXT3_DIND_BLOCK: 2356 nr = i_data[EXT3_TIND_BLOCK]; 2357 if (nr) { 2358 ext3_free_branches(handle, inode, NULL, &nr, &nr+1, 3); 2359 i_data[EXT3_TIND_BLOCK] = 0; 2360 } 2361 case EXT3_TIND_BLOCK: 2362 ; 2363 } 2364 2365 ext3_discard_reservation(inode); 2366 2367 mutex_unlock(&ei->truncate_mutex); 2368 inode->i_mtime = inode->i_ctime = CURRENT_TIME_SEC; 2369 ext3_mark_inode_dirty(handle, inode); 2370 2371 /* 2372 * In a multi-transaction truncate, we only make the final transaction 2373 * synchronous 2374 */ 2375 if (IS_SYNC(inode)) 2376 handle->h_sync = 1; 2377 out_stop: 2378 /* 2379 * If this was a simple ftruncate(), and the file will remain alive 2380 * then we need to clear up the orphan record which we created above. 2381 * However, if this was a real unlink then we were called by 2382 * ext3_delete_inode(), and we allow that function to clean up the 2383 * orphan info for us. 2384 */ 2385 if (inode->i_nlink) 2386 ext3_orphan_del(handle, inode); 2387 2388 ext3_journal_stop(handle); 2389 } |
清單 14 和 15 列出的 ext3_delete_inode 和 ext3_truncate 函數實現中，使用黑體標出了與前面提到的問題相關的部分代碼。本文下載部分給出的針對 ext3 文件系統的補丁中，包括了對這些問題的一些修改。清單 16 給出了使用這個補丁之後在 ext3 文件系統中刪除文件的一個例子。
# ./creatfile.sh 90 testfile.90K # ls -li total 116 12 -rwxr-xr-x 1 root root 1407 2008-01-23 07:25 creatfile.sh 11 drwx------ 2 root root 16384 2008-01-23 07:23 lost+found 13 -rw-r--r-- 1 root root 92160 2008-01-23 07:25 testfile.90K # rm -f testfile.90K # cd .. # umount /tmp/test # debugfs /dev/sda3 debugfs 1.40.2 (12-Jul-2007) debugfs: lsdel Inode Owner Mode Size Blocks Time deleted 0 deleted inodes found. debugfs: stat <13> Inode: 13 Type: regular Mode: 0644 Flags: 0x0 Generation: 3438957668 User: 0 Group: 0 Size: 92160 File ACL: 0 Directory ACL: 0 Links: 1 Blockcount: 192 Fragment: Address: 0 Number: 0 Size: 0 ctime: 0x47967b69 -- Wed Jan 23 07:25:29 2008 atime: 0x47967b68 -- Wed Jan 23 07:25:28 2008 mtime: 0x47967b69 -- Wed Jan 23 07:25:29 2008 BLOCKS: (0-11):22528-22539, (IND):22540, (12-22):22541-22551 TOTAL: 24 debugfs: |
在清單 16 中，我們首先創建了一個大小為 90KB 的測試文件，刪除該文件並使用 debugfs 查看對應的設備文件時，stat <13> 顯示的信息說明數據塊的位置信息都仍然保存在了索引節點中，不過 lsdel 命令並未找到這個索引節點。因此下載部分中給出的補丁尚不完善，感興趣的讀者可以自行開發出更加完善的補丁。
|
小結
本文首先介紹了 ext3 文件系統作為一種日誌文件系統的一些特性，然後針對這些特性介紹了 3 種恢復刪除文件的方法：正文匹配、利用 libundel 和修改內核中 ext3 文件系統的實現，並給出了對 libundel 和 ext3 文件系統實現的補丁程序。應用本文介紹的方法，讀者可以最大程度地恢復 ext3 文件系統中刪除的文件。本系列的後續文章將繼續探討在其他文件系統上如何恢復已刪除的文件，並著手設計更加通用的文件備份方法。
為了支持更大的文件系統，ext4 對 ext3 的現有實現進行了一系列擴充，使用 48 位的塊號來增大塊號定址範圍，並採用 extent 的設計來簡化對數據塊的索引，這勢必會影響到磁碟數據結構的變化，以及刪除文件的恢復。本文將逐一介紹 ext4 在對大文件系統支持方面所採用的全新設計，並探討 ext4 文件系統中文件的刪除和恢復的相關技術。
ext3 自從誕生之日起，就由於其可靠性好、特性豐富、性能高、版本間兼容性好等優勢而迅速成為 Linux 上非常流行的文件系統，諸如 Redhat 等發行版都將 ext3 作為默認的文件系統格式。為了盡量保持與 ext2 文件系統實現更好的兼容性，ext3 在設計時採用了很多保守的做法，這些保守的設計為 ext3 贏得了穩定、健壯的聲譽，迅速得到了 Linux 用戶（尤其是原有的 ext2 文件系統的用戶）的青睞，但同時這也限制了它的可擴展能力，無法支持特別大的文件系統。
隨著硬碟存儲容量越來越大（硬碟容量每年幾乎都會翻一倍，現在市面上已經有 1TB 的硬碟出售，很快桌面用戶也可以享用這麼大容量的存儲空間了），企業應用所需要和產生的數據越來越多（Lawrence Livermore National Labs 使用的 BlueGene/L 系統上所使用的數據早已超過了 1PB），以及在線重新調整大小特性的支持，ext3 所面臨的可擴充性問題和性能方面的壓力也越來越大。在 ext3 文件系統中，如果使用 4KB 大小的數據塊，所支持的最大文件系統上限為16TB，這是由於它使用了 32 位的塊號所決定的（232 * 212 B = 244 B = 16 TB）。為了解決這些限制，從 2006 年 8 月開始，陸續有很多為 ext3 設計的補丁發布出來，這些補丁主要是擴充了兩個特性：針對大文件系統支持的設計和 extent 映射技術。不過要想支持更大的文件系統，就必須對磁碟上的存儲格式進行修改，這會破壞向前兼容性。因此為了為龐大的 ext3 用戶群維護更好的穩定性，設計人員決定從 ext3 中另闢一支，設計下一代 Linux 上的文件系統，即 ext4。
ext4 的主要目標是解決 ext3 所面臨的可擴展性、性能和可靠性問題。從 2.6.19 版本的內核開始，ext4 已經正式進入內核源代碼中，不過它被標記為正在開發過程中，即 ext4dev。本文將介紹 ext4 為了支持更好的可擴展性方面所採用的設計，並探討由此而引起的磁碟數據格式的變化，以及對恢復刪除文件所帶來的影響。
可擴展性
為了支持更大的文件系統，ext4 決定採用 48 位的塊號取代 ext3 原來的 32 位塊號，並採用 extent 映射來取代 ext3 所採用的間接數據塊映射的方法。這樣既可以增大文件系統的容量，又可以改進大文件的訪問效率。在使用 4KB 大小的數據塊時，ext4 可以支持最大 248 * 212 = 260 B（1 EB）的文件系統。之所以採用 48 位的塊號而不是直接將其擴展到 64 位是因為，ext4 的開發者認為 1 EB 大小的文件系統對未來很多年都足夠了（實際上，按照目前的速度，要對 1 EB 大小的文件系統執行一次完整的 fsck 檢查，大約需要 119 年的時間），與其耗費心機去完全支持 64 位的文件系統，還不如先花些精力來解決更加棘手的可靠性問題。
將塊號從 32 位修改為 48 位之後，存儲元數據的結構都必須相應地發生變化，主要包括超級塊、組描述符和日誌。下面給出了 ext4 中所使用的新結構的部分代碼。
清單1. ext4_super_block 結構定義
520 /* 521 * Structure of the super block 522 */ 523 struct ext4_super_block { 524 /*00*/ __le32 s_inodes_count; /* Inodes count */ 525 __le32 s_blocks_count; /* Blocks count */ 526 __le32 s_r_blocks_count; /* Reserved blocks count */ 527 __le32 s_free_blocks_count; /* Free blocks count */ 528 /*10*/ __le32 s_free_inodes_count; /* Free inodes count */ 529 __le32 s_first_data_block; /* First Data Block */ 530 __le32 s_log_block_size; /* Block size */ … 594 /* 64bit support valid if EXT4_FEATURE_COMPAT_64BIT */ 595 /*150*/ __le32 s_blocks_count_hi; /* Blocks count */ 596 __le32 s_r_blocks_count_hi; /* Reserved blocks count */ 597 __le32 s_free_blocks_count_hi; /* Free blocks count */ … 606 }; |
在 ext4_super_block 結構中，增加了 3 個與此相關的欄位：s_blocks_count_hi、s_r_blocks_count_hi、s_free_blocks_count_hi，它們分別表示 s_blocks_count、s_r_blocks_count、s_free_blocks_count 高 32 位的值，將它們擴充到 64 位。
清單2. ext4_group_desc 結構定義
121 /* 122 * Structure of a blocks group descriptor 123 */ 124 struct ext4_group_desc 125 { 126 __le32 bg_block_bitmap; /* Blocks bitmap block */ 127 __le32 bg_inode_bitmap; /* Inodes bitmap block */ 128 __le32 bg_inode_table; /* Inodes table block */ 129 __le16 bg_free_blocks_count; /* Free blocks count */ 130 __le16 bg_free_inodes_count; /* Free inodes count */ 131 __le16 bg_used_dirs_count; /* Directories count */ 132 __u16 bg_flags; 133 __u32 bg_reserved[3]; 134 __le32 bg_block_bitmap_hi; /* Blocks bitmap block MSB */ 135 __le32 bg_inode_bitmap_hi; /* Inodes bitmap block MSB */ 136 __le32 bg_inode_table_hi; /* Inodes table block MSB */ 137 }; |
類似地，在 ext4_group_desc 中引入了另外 3 個欄位：bg_block_bitmap_hi、bg_inode_bitmap_hi、bg_inode_table_hi，分別表示 bg_block_bitmap、bg_inode_bitmap、bg_inode_table 的高 32 位。
另外，由於日誌中要記錄所修改數據塊的塊號，因此 JBD也需要相應地支持 48 位的塊號。同樣是為了為 ext3 廣大的用戶群維護更好的穩定性，JBD2 也從 JBD 中分離出來，詳細實現請參看內核源代碼。
採用 48 位塊號取代原有的 32 位塊號之後，文件系統的最大值還受文件系統中最多塊數的制約，這是由於 ext3 原來採用的結構決定的。回想一下，對於 ext3 類型的分區來說，在每個分區的開頭，都有一個引導塊，用來保存引導信息；文件系統的數據一般從第 2 個數據塊開始（更確切地說，文件系統數據都是從 1KB 之後開始的，對於 1024 位元組大小的數據塊來說，就是從第 2 個數據塊開始；對於超過 1KB 大小的數據塊，引導塊與後面的超級塊等信息共同保存在第 1 個數據塊中，超級塊從 1KB 之後的位置開始）。為了管理方便，文件系統將剩餘磁碟劃分為一個個塊組。塊組前面存儲了超級塊、塊組描述符、數據塊點陣圖、索引節點點陣圖、索引節點表，然後才是數據塊。通過有效的管理，ext2/ext3 可以盡量將文件的數據放入同一個塊組中，從而實現文件數據在磁碟上的最大連續性。
在 ext3 中，為了安全性方面的考慮，所有的塊描述符信息全部被保存到第一個塊組中，因此以預設的 128MB （227 B）大小的塊組為例，最多能夠支持 227 / 32 = 222 個塊組，最大支持的文件系統大小為 222 * 227 = 249 B= 512 TB。而ext4_group_desc 目前的大小為 44 位元組，以後會擴充到 64 位元組，所能夠支持的文件系統最大隻有 256 TB。
為了解決這個問題，ext4 中採用了元塊組（metablock group）的概念。所謂元塊組就是指塊組描述符可以存儲在一個數據塊中的一些連續塊組。仍然以 128MB 的塊組（數據塊為 4KB）為例，ext4 中每個元塊組可以包括 4096 / 64 = 64 個塊組，即每個元塊組的大小是 64 * 128 MB = 8 GB。
採用元塊組的概念之後，每個元塊組中的塊組描述符都變成定長的，這對於文件系統的擴展非常有利。原來在 ext3 中，要想擴大文件系統的大小，只能在第一個塊組中增加更多塊描述符，通常這都需要重新格式化文件系統，無法實現在線擴容；另外一種可能的解決方案是為塊組描述符預留一部分空間，在增加數據塊時，使用這部分空間來存儲對應的塊組描述符；但是這樣也會受到前面介紹的最大容量的限制。而採用元塊組概念之後，如果需要擴充文件系統的大小，可以在現有數據塊之後新添加磁碟數據塊，並將這些數據塊也按照元塊組的方式進行管理即可，這樣就可以突破文件系統大小原有的限制了。當然，為了使用這些新增加的空間，在 superblock 結構中需要增加一些欄位來記錄相關信息。（ext4_super_block 結構中增加了一個 s_first_meta_bg 欄位用來引用第一個元塊組的位置，這樣還可以解決原有塊組和新的元塊組共存的問題。）下圖給出了 ext3 為塊組描述符預留空間和在 ext4 中採用元塊組后的磁碟布局。
圖 1. ext3 與 ext4 磁碟布局對比
  |
extent
ext2/ext3 文件系統與大部分經典的 UNIX/Linux 文件系統一樣，都使用了直接、間接、二級間接和三級間接塊的形式來定位磁碟中的數據塊。對於小文件或稀疏文件來說，這非常有效（以 4KB 大小的數據塊為例，小於 48KB 的文件只需要通過索引節點中 i_block 數組的前 12 個元素一次定位即可），但是對於大文件來說，需要經過幾級間接索引，這會導致在這些文件系統上大文件的性能較差。
測試表明，在生產環境中，數據不連續的情況不會超過10％。因此，在 ext4 中引入了 extent 的概念來表示文件數據所在的位置。所謂 extent 就是描述保存文件數據使用的連續物理塊的一段範圍。每個 extent 都是一個 ext4_extent 類型的結構，大小為 12 位元組。定義如下所示：
清單3. ext4 文件系統中有關 extent 的結構定義
69 /* 70 * This is the extent on-disk structure. 71 * It's used at the bottom of the tree. 72 */ 73 struct ext4_extent { 74 __le32 ee_block; /* first logical block extent covers */ 75 __le16 ee_len; /* number of blocks covered by extent */ 76 __le16 ee_start_hi; /* high 16 bits of physical block */ 77 __le32 ee_start; /* low 32 bits of physical block */ 78 }; 79 80 /* 81 * This is index on-disk structure. 82 * It's used at all the levels except the bottom. 83 */ 84 struct ext4_extent_idx { 85 __le32 ei_block; /* index covers logical blocks from 'block' */ 86 __le32 ei_leaf; /* pointer to the physical block of the next * 87 * level. leaf or next index could be there */ 88 __le16 ei_leaf_hi; /* high 16 bits of physical block */ 89 __u16 ei_unused; 90 }; 91 92 /* 93 * Each block (leaves and indexes), even inode-stored has header. 94 */ 95 struct ext4_extent_header { 96 __le16 eh_magic; /* probably will support different formats */ 97 __le16 eh_entries; /* number of valid entries */ 98 __le16 eh_max; /* capacity of store in entries */ 99 __le16 eh_depth; /* has tree real underlying blocks? */ 100 __le32 eh_generation; /* generation of the tree */ 101 }; 102 103 #define EXT4_EXT_MAGIC cpu_to_le16(0xf30a) |
每個 ext4_extent 結構可以表示該文件從 ee_block 開始的 ee_len 個數據塊，它們在磁碟上的位置是從 ee_start_hi<<32 + ee_start 開始，到 ee_start_hi<<32 + ee_start + ee_len – 1 結束，全部都是連續的。儘管 ee_len 是一個 16 位的無符號整數，但是其最高位被在預分配特性中用來標識這個 extent 是否被初始化過了，因此可以一個 extent 可以表示 215 個連續的數據塊，如果採用 4KB 大小的數據塊，就相當於 128MB。
如果文件大小超過了一個 ext4_extent 結構能夠表示的範圍，或者其中有不連續的數據塊，就需要使用多個 ext4_extent 結構來表示了。為了解決這個問題，ext4 文件系統的設計者們採用了一棵 extent 樹結構，它是一棵高度固定的樹，其布局如下圖所示：
圖 2. ext4 中 extent 樹的布局結構
在 extent 樹中，節點一共有兩類：葉子節點和索引節點。保存文件數據的磁碟塊信息全部記錄在葉子節點中；而索引節點中則存儲了葉子節點的位置和相對順序。不管是葉子節點還是索引節點，最開始的 12 個位元組總是一個 ext4_extent_header 結構，用來標識該數據塊中有效項（ext4_extent 或 ext4_extent_idx 結構）的個數（eh_entries 域的值），其中 eh_depth 域用來表示它在 extent 樹中的位置：對於葉子節點來說，該值為 0，之上每層索引節點依次加 1。extent 樹的根節點保存在索引節點結構中的 i_block 域中，我們知道它是一個大小為 60 位元組的數組，最多可以保存一個 ext4_extent_header 結構以及 4 個 ext4_extent 結構。對於小文件來說，只需要一次定址就可以獲得保存文件數據塊的位置；而超出此限制的文件（例如很大的文件、碎片非常多的文件以及稀疏文件）只能通過遍歷 extent 樹來獲得數據塊的位置。
|
索引節點
索引節點是 ext2/ext3/ext4 文件系統中最為基本的一個概念，它是文件語義與數據之間關聯的橋樑。為了最大程度地實現向後兼容性，ext4 盡量保持索引節點不會發生太大變化。ext4_inode 結構定義如下所示：
清單4. ext4_inode 結構定義
284 /* 285 * Structure of an inode on the disk 286 */ 287 struct ext4_inode { 288 __le16 i_mode; /* File mode */ 289 __le16 i_uid; /* Low 16 bits of Owner Uid */ 290 __le32 i_size; /* Size in bytes */ 291 __le32 i_atime; /* Access time */ 292 __le32 i_ctime; /* Inode Change time */ 293 __le32 i_mtime; /* Modification time */ 294 __le32 i_dtime; /* Deletion Time */ 295 __le16 i_gid; /* Low 16 bits of Group Id */ 296 __le16 i_links_count; /* Links count */ 297 __le32 i_blocks; /* Blocks count */ 298 __le32 i_flags; /* File flags */ … 310 __le32 i_block[EXT4_N_BLOCKS];/* Pointers to blocks */ 311 __le32 i_generation; /* File version (for NFS) */ 312 __le32 i_file_acl; /* File ACL */ 313 __le32 i_dir_acl; /* Directory ACL */ 314 __le32 i_faddr; /* Fragment address */ … 339 __le16 i_extra_isize; 340 __le16 i_pad1; 341 __le32 i_ctime_extra; /* extra Change time (nsec << 2 | epoch) */ 342 __le32 i_mtime_extra; /* extra Modification time(nsec << 2 | epoch) */ 343 __le32 i_atime_extra; /* extra Access time (nsec << 2 | epoch) */ 344 __le32 i_crtime; /* File Creation time */ 345 __le32 i_crtime_extra; /* extra FileCreationtime (nsec << 2 | epoch) */ 346 }; |
與 ext3 文件系統中使用的 ext3_inode 結構對比一下可知，索引節點結構並沒有發生太大變化，不同之處在於最後添加了 5 個與時間有關的欄位，這是為了提高時間戳的精度。在 ext2/ext3 文件系統中，時間戳的精度只能達到秒級。隨著硬體性能的提升，這種精度已經無法區分在同一秒中創建的文件的時間戳差異，這對於對精度要求很高的程序來說是無法接受的。在 ext4 文件系統中，通過擴充索引節點結構解決了這個問題，可以實現納秒級的精度。最後兩個新增欄位 i_crtime 和 i_crtime_extra 用來表示文件的創建時間，這可以用來滿足某些應用程序的需求。
前面已經介紹過，儘管索引節點中的 i_block 欄位保持不變，但是由於 extent 概念的引入，對於這個數組的使用方式已經改變了，其前 3 個元素一定是一個 ext4_extent_header 結構，後續每 3 個元素可能是一個 ext4_extent 或 ext4_extent_idx 結構，這取決於所表示的文件的大小。這種設計可以有效地表示連續存放的大文件，但是對於包含碎片非常多的文件或者稀疏文件來說，就不是那麼有效了。為了解決這個問題，ext4 的設計者們正在討論設計一種新型的 extent 來表示這種特殊文件，它將在葉子節點中採用類似於 ext3 所採用的間接索引塊的形式來保存為該文件分配的數據塊位置。該類型的 ext4_extent_header 結構中的 eh_magic 欄位將採用一個新值，以便與目前的 extent 區別開來。
採用這種結構的索引節點還存在一個問題：我們知道，在 ext3 中 i_blocks 是以扇區（即 512 位元組）為單位的，因此單個文件的最大限制是 232 * 512 B = 2 TB。為了支持更大的文件，ext4 的 i_blocks 可以以數據塊大小為單位（這需要 HUGE_FILE 特性的支持），因此文件上限可以擴充到 16TB（數據塊大小為 4KB）。同時為了避免需要對整個文件系統都需要進行類似轉換，還引入了一個 EXT4_HUGE_FILE_FL 標誌，i_flags 中不包含這個標誌的索引節點的 i_blocks 依然以 512 位元組為單位。當文件所佔用的磁碟空間大小增大到不能夠用以512位元組為單位的i_blocks來表示時，ext4自動激活EXT4_HUGE_FILE_FL標誌，以數據塊為單位重新計算i_blocks的值。該轉換是自動進行的，對用戶透明。
|
目錄項
ext4 文件系統中使用的目錄項與 ext2/ext3 並沒有太大的區別。所使用的結構定義如下所示：
清單5. 目錄項結構定義
737 /* 738 * Structure of a directory entry 739 */ 740 #define EXT4_NAME_LEN 255 741 742 struct ext4_dir_entry { 743 __le32 inode; /* Inode number */ 744 __le16 rec_len; /* Directory entry length */ 745 __le16 name_len; /* Name length */ 746 char name[EXT4_NAME_LEN]; /* File name */ 747 }; 748 749 /* 750 * The new version of the directory entry. Since EXT4 structures are 751 * stored in intel byte order, and the name_len field could never be 752 * bigger than 255 chars, it's safe to reclaim the extra byte for the 753 * file_type field. 754 */ 755 struct ext4_dir_entry_2 { 756 __le32 inode; /* Inode number */ 757 __le16 rec_len; /* Directory entry length */ 758 __u8 name_len; /* Name length */ 759 __u8 file_type; 760 char name[EXT4_NAME_LEN]; /* File name */ 761 }; |
與 ext2/ext3 類似，當目錄項被刪除時，也會將該目錄項的空間合併到上一個目錄項中。與 ext2/ext3 不同的地方在於，在刪除目錄項時，該目錄項中的索引節點號並沒有被清空，而是得以保留了下來，這使得在恢復刪除文件時，文件名就可以通過查找目錄項中匹配的索引節點號得以正確恢復。詳細數據如下所示：
清單6. 刪除文件前後目錄項的變化
[root@vmfc8 ext4]# ./read_dir_entry root.block.547.orig 4096 offset | inode number | rec_len | name_len | file_type | name ================================================================= 0: 2 12 1 2 . 12: 2 12 2 2 .. 24: 11 20 10 2 lost+found 44: 12 16 5 1 hello 60: 13 32 12 1 testfile.35K 80: 14 12 4 1 hole 92: 15 4004 4 1 home [root@vmfc8 ext4]# ./read_dir_entry root.block.547.deleted 4096 offset | inode number | rec_len | name_len | file_type | name ================================================================= 0: 2 12 1 2 . 12: 2 12 2 2 .. 24: 11 36 10 2 lost+found 44: 12 16 5 1 hello 60: 13 32 12 1 testfile.35K 80: 14 12 4 1 hole 92: 15 4004 4 1 home |
上面給出了保存根目錄的數據塊（547）在刪除 hello 文件前後的變化，從中我們可以看出，唯一的區別在於 hello 所使用的 16 個位元組的空間後來被合併到 lost+found 目錄項所使用的空間中了，而索引節點號等信息都得以完整地保留了下來。清單中使用的 read_dir_entry 程序用來顯示目錄項中的數據，其源碼可以在本文下載部分中獲得。有關如何抓取保存目錄數據的數據塊的方法，請參看本系列文章第 2 部分的介紹。
在 ext2/3 文件系統中，一個目錄下面最多可以包含 32,000 個子目錄，這對於大型的企業應用來說顯然是不夠的。ext4 決定將其上限擴充到可以支持任意多個子目錄。然而對於這種鏈表式的存儲結構來說，目錄項的查找和刪除需要遍歷整個目錄的所有目錄項，效率顯然是相當低的。實際上，從 ext2 開始，文件系統的設計者引入了一棵 H-樹來對目錄項的 hash 值進行索引，速度可以提高 50 - 100 倍。相關內容已經超出了本文的範圍，感興趣的讀者可自行參考 Linux 內核源代碼中的相關實現。
|
ext4 文件系統的使用
目前，ext4 文件系統仍然處於非常活躍的狀態，因此內核在相應的地方都加上了 DEV 標誌。在編譯內核時，需要在內核的 .config 文件中啟用 EXT4DEV_FS 選項才能編譯出最終使用的內核模塊 ext4dev.ko。
由於 ext4 內部採用的關鍵數據結構與 ext3 並沒有什麼關鍵區別，因此在創建文件系統時依然是使用 mkfs.ext3 命令，如下所示：
清單7. 創建 ext4 文件系統，目前與創建 ext3 文件系統沒什麼兩樣
[root@vmfc8 ~]# mkfs.ext3 /dev/sda3 |
為了保持向前兼容性，現有的 ext3 文件系統也可以當作 ext4 文件系統進行載入，命令如下所示：
清單8. 掛載 ext4 文件系統
[root@vmfc8 ~]# mount -t ext4dev -o extents /dev/sda3 /tmp/test
-o extents 選項就是指定要啟用 extent 特性。如果不在這個文件系統中執行任何寫入操作，以後這個文件系統也依然可以按照 ext3 或 ext4 格式正常掛載。但是一旦在這個文件系統中寫入文件之後，文件系統所使用的特性中就包含了 extent 特性，因此以後再也不能按照 ext3 格式進行掛載了，如下所示：
清單9. 寫入文件前後 ext4 文件系統特性的變化據
[root@vmfc8 ext4]# umount /tmp/test; mount -t ext4dev -o extents /dev/sda3 /tmp/test; \ dumpe2fs /dev/sda3 > sda3.ext4_1 [root@vmfc8 ext4]# umount /tmp/test; mount -t ext4dev -o extents /dev/sda3 /tmp/test; \ echo hello > /tmp/test/hello; dumpe2fs /dev/sda3 > sda3.ext4_2 [root@vmfc8 ext4]# diff sda3.ext4_1 sda3.ext4_2 6c6 < Filesystem features: has_journal resize_inode dir_index filetype \ needs_recovery sparse_super large_file --- > Filesystem features: has_journal resize_inode dir_index filetype \ needs_recovery extents sparse_super large_file … [root@vmfc8 ext4]# umount /tmp/test; mount -t ext3 /dev/sda3 /tmp/test mount: wrong fs type, bad option, bad superblock on /dev/sda3, missing codepage or helper program, or other error In some cases useful info is found in syslog - try dmesg | tail or so |
|
e2fsprogs 工具的支持
在本系列前面的文章中，我們已經初步體驗了 e2fsprogs 包中提供的諸如 debugfs、dumpe2fs 之類的工具對於深入理解文件系統和磁碟數據來說是如何方便。作為一種新生的文件系統，ext4 文件系統要想得到廣泛應用，相關工具的支持也非常重要。從 1.39 版本開始，e2fsprogs 已經逐漸開始加入對 ext4 文件系統的支持，例如創建文件系統使用的 mkfs.ext3 命令以後會被一個新的命令 mkfs.ext4 所取代。但是截止到本文撰寫時為止，e2fsprogs 的最新版本（1.40.7）對於 ext4 的支持尚不完善，下面的例子給出了 debugfs 查看 hello 文件時的結果：
清單10. debugfs 命令對 ext4 文件系統的支持尚不完善
[root@vmfc8 ext4]# echo "hello world" > /tmp/test/hello [root@vmfc8 ext4]# debugfs /dev/sda3 debugfs 1.40.2 (12-Jul-2007) debugfs: stat hello Inode: 12 Type: regular Mode: 0644 Flags: 0x80000 Generation: 827135866 User: 0 Group: 0 Size: 12 File ACL: 0 Directory ACL: 0 Links: 1 Blockcount: 8 Fragment: Address: 0 Number: 0 Size: 0 ctime: 0x47ced460 -- Thu Mar 6 01:12:00 2008 atime: 0x47ced460 -- Thu Mar 6 01:12:00 2008 mtime: 0x47ced460 -- Thu Mar 6 01:12:00 2008 BLOCKS: (0):127754, (1):4, (4):1, (5):28672 TOTAL: 4 |
從上面的輸出結果中我們可以看出，儘管這個索引節點的 i_flags 欄位值為 0x80000，表示使用 extent 方式來存儲數據，而不是原有的直接/間接索引模式來存儲數據（此時 i_flags 欄位值為 0），但是對 i_block 數組中內容的顯示卻依然沿用了原有的模式。如果文件佔用多個 extent 進行存儲，會發現 debugfs 依然嘗試將 i_block[12]、i_block[13]、i_block[14] 分別作為一級、二級和三級間接索引使用，顯然從中讀出的數據也是毫無意義的。
索引節點中使用的 i_flags 值是在內核源代碼的 /include/linux/ext4_fs.h 中定義的，如下所示：
清單11. i_flags 值定義節選
#define EXT4_EXTENTS_FL 0x00080000 /* Inode uses extents */ |
|
ext4 文件系統中文件的刪除與恢復
在 ext4 文件系統中刪除文件時，所執行的操作與在 ext2/ext3 文件系統中非常類似，也不會真正修改存儲文件數據所使用的磁碟數據塊的內容，而是僅僅刪除或修改了相關的元數據信息，使文件數據無法正常索引，從而實現刪除文件的目的。因此，在 ext4 文件系統中恢復刪除文件也完全是可能的。
前文中已經介紹過，在 ext4 文件系統中刪除文件時，並沒有將目錄項中的索引節點號清空，因此通過遍歷目錄項的方式完全可以完整地恢復出文件名來。
對於文件數據來說，實際數據塊中的數據在文件刪除前後也沒有任何變化，這可以利用本系列文章第一部分中介紹的直接比較數據塊的方法進行驗證。然而由於 extent 的引入，在 ext4 中刪除文件與 ext3 也有所區別。下面讓我們通過一個實例來驗證一下。
在下面的例子中，我們要創建一個非常特殊的文件，它每 7KB 之後的都是一個數字（7 的倍數），其他地方數據全部為 0。
清單12. 創建測試文件
[root@vmfc8 ext4]# cat -n create_extents.sh 1 #!/bin/bash 2 3 if [ $# -ne 2 ] 4 then 5 echo "$0 [filename] [size in kb]" 6 exit 1 7 fi 8 9 filename=$1 10 size=$2 11 i=0 12 13 while [ $i -lt $size ] 14 do 15 i=`expr $i + 7` 16 echo -n "$i" | dd of=$1 bs=1024 seek=$i 17 dones [root@vmfc8 ext4]# ./create_extents.sh /tmp/test/sparsefile.70K 70 [root@vmfc8 ext4]# ls -li /tmp/test/sparsefile.70K 13 -rw-r--r-- 1 root root 71682 2008-03-06 10:49 /tmp/test/sparsefile.70K [root@vmfc8 ext4]# hexdump -C /tmp/test/sparsefile.70K 00000000 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................| * 00001c00 37 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |7...............| 00001c10 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................| * 00003800 31 34 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |14..............| 00003810 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................| * 00005400 32 31 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |21..............| 00005410 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................| * 00007000 32 38 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |28..............| 00007010 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................| * 00008c00 33 35 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |35..............| 00008c10 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................| * 0000a800 34 32 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |42..............| 0000a810 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................| * 0000c400 34 39 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |49..............| 0000c410 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................| * 0000e000 35 36 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |56..............| 0000e010 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................| * 0000fc00 36 33 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |63..............| 0000fc10 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................| * 00011800 37 30 |70| 00011802 |
之所以要使用這個文件當作測試文件，完全為了迴避 extent 的優點，否則在 4KB 大小數據塊的 ext4 文件系統中，一個 extent 就可以表示 128MB 的空間，因此要想測試 extent 樹的變化情況就必須創建非常大的文件才行。
由於 debugfs 對 ext4 的支持尚不完善，我們自己編寫了一個小程序（list_extents）來遍歷 extent 樹的內容，並顯示索引節點和葉子節點的數據塊的位置。該程序的源代碼可以在本文下載部分中獲得，其用法如下：
清單13. 查看測試文件使用的 extent 樹信息
[root@vmfc8 ext4]# ./list_extents /dev/sda3 13 root node: depth of the tree: 1, 1 entries in root level idx: logical block: 1, block: 20491 - logical block: 1 - 1, physical block: 20481 - 20481 - logical block: 3 - 3, physical block: 20483 - 20483 - logical block: 5 - 5, physical block: 20485 - 20485 - logical block: 7 - 8, physical block: 20487 - 20488 - logical block: 10 - 10, physical block: 20490 - 20490 - logical block: 12 - 12, physical block: 20492 - 20492 - logical block: 14 - 15, physical block: 20494 - 20495 - logical block: 17 - 17, physical block: 20497 - 20497 |
list_extents 程序會對指定磁碟進行搜索，從其中的索引節點表中尋找搜索指定的索引節點號（13）所對應的項，並將其 i_block 數組當作一棵 extent 樹進行遍歷。從輸出結果中我們可以看出，這棵 extent 樹包括 1 個索引節點和 1個包含了8個 ext4_extent 結構的葉子節點，其中索引節點保存 i_block 數組中，而葉子節點則保存在20491 這個數據塊中。下面讓我們來看一下該文件的索引節點在刪除文件前後的變化：
清單14. ext4 文件系統中刪除文件前後文件索引節點的變化
[root@vmfc8 ext4]# echo "stat <13>" | debugfs /dev/sda3 debugfs 1.40.2 (12-Jul-2007) debugfs: Inode: 13 Type: regular Mode: 0644 Flags: 0x80000 Generation: 2866260918 User: 0 Group: 0 Size: 71682 File ACL: 0 Directory ACL: 0 Links: 1 Blockcount: 88 Fragment: Address: 0 Number: 0 Size: 0 ctime: 0x47cf5bb1 -- Thu Mar 6 10:49:21 2008 atime: 0x47cf5bb0 -- Thu Mar 6 10:49:20 2008 mtime: 0x47cf5bb1 -- Thu Mar 6 10:49:21 2008 BLOCKS: (0):127754, (1):65540, (3):1, (4):20491, (6):3, (7):1, (8):20483, (9):5, (10):1, (11):20485, (IND):7, (12):32775, (13):98311, (14):163847, (15):229383, (DIND):2, (IND):32770, (IND):98306, (IND):163842, (IND):229378, (TIND):20487, (DIND):14386 TOTAL: 22 [root@vmfc8 ext4]# rm -f /tmp/test/sparsefile.70K [root@vmfc8 ext4]# sync [root@vmfc8 ext4]# echo "stat <13>" | debugfs /dev/sda3 debugfs 1.40.2 (12-Jul-2007) debugfs: Inode: 13 Type: regular Mode: 0644 Flags: 0x80000 Generation: 2866260918 User: 0 Group: 0 Size: 0 File ACL: 0 Directory ACL: 0 Links: 0 Blockcount: 0 Fragment: Address: 0 Number: 0 Size: 0 ctime: 0x47cf5ebc -- Thu Mar 6 11:02:20 2008 atime: 0x47cf5bb0 -- Thu Mar 6 10:49:20 2008 mtime: 0x47cf5bb1 -- Thu Mar 6 10:49:21 2008 dtime: 0x47cf5ebc -- Thu Mar 6 11:02:20 2008 BLOCKS: (0):62218, (1):4, (3):1, (4):20491, (6):3, (7):1, (8):20483, (9):5, (10):1, (11):20485, (IND):7, (12):32775, (13):98311, (14):163847, (15):229383, (DIND):2, (IND):32770, (IND):98306, (IND):163842, (IND):229378, (TIND):20487, (DIND):14386 TOTAL: 22 |
首先需要注意的一點是，對於上面這棵 extent 樹來說，只需要使用 i_block 數組的前 6 個元素就可以存儲一個 ext4_extent_header 和一個 ext4_extent_idx 結構了，而 i_block 數組中的所有元素卻都是有數據的。之所以出現這種情況是因為在創建這個特殊的測試文件的過程中，我們是不斷創建一個文件並在此文件尾部追加數據從而生成新文件的。當該文件使用的 extent 超過 4 個時，便擴充成一棵 extent 樹，但是剩餘 3 個 extent 的內容（i_block 數組的后 9 個元素）並沒有被清空。
對比刪除文件前後的變化會發現，ext4 與 ext3 非常類似，也都將文件大小設置為 0，這使得 debugfs 的 dump 命令也無從正常工作了。不過與 ext3 不同的是，ext4 並沒有將 i_block 數組的元素全部清空，而是將 ext4_extent_header 結構中有效項數設置為 0，這樣就將 extent 樹破壞掉了。另外，比較葉子節點（數據塊 20491）中的數據變化會發現，下面這些域在刪除文件時也都被清除了：
圖3. 刪除文件前後 extent 樹中葉子節點數據塊的變化
了解清楚這些變化之後，我們會發現在 ext4 中恢復刪除文件的方法與 ext3 基本類似，也可以使用全文匹配、提前備份元數據和修改內核實現 3 種方法。
正如前面介紹的一樣，由於 ext4 文件系統中採用了 extent 的設計，試圖最大程度地確保文件數據會被保存到連續的數據塊中，因此在 ext2/ext3 恢復刪除文件時所介紹的正文匹配方法也完全適用，正常情況下採用這種方式恢復出來的數據會比 ext2/ext3 中更多。詳細內容請參看本系列文章第 4 部分的介紹，本文中不再贅述。
儘管 ext4 是基於 extent 來管理空間的，但是在 ext3 中備份數據塊位置的方法依然完全適用，下面給出了一個例子。
清單15. 備份文件數據塊位置
[root@vmfc8 ext4]# export LD_PRELOAD=/usr/local/lib/libundel.so [root@vmfc8 ext4]# rm -f /tmp/test/sparsefile.70K [root@vmfc8 ext4]# tail -n 1 /var/e2undel/e2undel 8,3::13::71682::4096::(1-1): 20481-20481,(3-3): 20483-20483, (5-5): 20485-20485,(7-8): 20487-20488,(10-10): 20490-20490, (12-12): 20492-20492,(14-15): 20494-20495, (17-17): 20497-20497::/tmp/test/sparsefile.70K |
當然，如果內核實現中可以在刪除文件時，extent樹（其中包括i_block數組，其他extent索引節點和葉子節點）中的數據保留下來，那自然恢復起來就更加容易了。由於 ext4 的開發依然正在非常活躍地進行中，相關代碼可能會頻繁地發生變化，本文就不再深入探討這個話題了，感興趣的讀者可以自行嘗試。
|
小結
本文從 ext3 的在支持大文件系統方面的缺陷入手，逐漸介紹了 ext4 為了支持大文件系統而引入的一些設計特性，並探討了這些特性對磁碟數據格式引起的變化，以及對恢復刪除文件所帶來的影響，最終討論了在 ext4 文件系統中如何恢復刪除文件的問題。在本系列的下一篇文章中，我們將開始討論另外一個設計非常精巧的文件系統 reiserfs 上的相關問題。
reiserfs 對於小文件的存取速度非常高，這取決於它所採用的精美的設計：reiserfs 文件系統就是一棵動態的 B+ 樹，小文件和大文件的尾部數據都可以通過保存到葉子節點中而加快存取速度。本文將探討 reiserfs 的設計和實現內幕，並從中探討恢復刪除文件的可能性。
reiserfs 是由 namesys 公司的 Hans Reiser 設計並開發的一種通用日誌文件系統，它是第一個進入 Linux 標準內核日誌文件系統。從誕生之日起，reiserfs 就由於其諸多非常有吸引力的特性而受到很多用戶的青睞，迅速成為 Slackware 等發行版的默認文件系統。它也一度也是 SUSE Linux Enterprise 發行版上的默認文件系統，直到 2006 年 10 月 12 日 Novell 公司決定將默認文件系統轉換到 ext3 為止。儘管其主要設計人員 Hans Reiser 由於涉嫌殺害妻子遭到指控而入獄，從而導致他不得不試圖出售 namesys 公司來支付龐大的訴訟費用，但是 reiserfs 已經受到廣大社區開發人員和用戶的極大關注，有很多志願者已經投入到新的 reiserfs 4 的開發工作中來。本文中的介紹都是基於最新的穩定版本 3.6 版本的，所引用的代碼都基於 2.6.23 版本的內核。
reiserfs 最初的設計目標是為了改進 ext2 文件系統的性能，提高文件系統的利用率，並增強對包含大量文件的目錄的處理能力（ext2/ext3 文件系統中一個目錄下可以包含的子目錄最多只能有 31998 個）。傳統的 ext2 和 ufs 文件系統都採用了將文件數據和文件元數據分離開保存的形式，將元數據保存到索引節點中，將文件數據保存到單獨的磁碟塊中，並通過索引節點中的 i_block 數組利用直接索引和間接索引的形式在磁碟上定位文件數據。這種設計非常適合存儲較大的文件（比如20KB以上），但是對於具有大量小文件的系統來說就存在一些問題。首先在於文件系統的利用率，由於 ext2 會將文件數據以數據塊為單位（默認為 4KB）進行存儲，因此對於存儲只有幾十個位元組的文件來說，會造成空間的極大浪費。另外由於在讀取文件時需要分別讀取文件元數據和文件數據，加上多讀取數據塊的開銷，ext2 文件系統在處理大量小文件時，性能會比較差。為了獲取最好的性能和最大程度地利用磁碟空間，很多用戶會在文件系統之上採用資料庫之類的解決方案來存儲這些小文件，因此會導致上層應用程序的介面極不統一。
為了解決上面提到的問題，reiserfs 為每個文件系統採用一棵經過專門優化的 B+ 樹來組織所有的文件數據，並實現了很多新特性，例如元數據日誌。為了提高文件系統的利用率，reiserfs 中採用了所謂的尾部封裝（tail packing）設計，可以充分利用已分配磁碟塊中的剩餘空間來存儲小文件。實際上，reiserfs 文件系統中存儲的文件會比 ext2/ext3 大 5% - 6% 以上。下面讓我們來探索一下 reiserfs 文件系統中數據在磁碟上究竟是如何存儲的。
磁碟布局
與 ext2/ext3 類似，reiserfs 文件系統在創建時，也會將磁碟空間劃分成固定大小的數據塊。數據塊從 0 開始編號，最多可以有 232 個數據塊。因此如果採用默認的 4KB 大小的數據塊，單個 reiserfs 文件系統的上限是 16TB。reiserfs 分區的前 64KB 保留給引導扇區、磁碟標籤等使用。超級塊（super block）從 64KB 開始，會佔用一個數據塊；之後是一個數據塊點陣圖，用來標識對應的數據塊是否處於空閑狀態。如果一個數據塊點陣圖可以標識 n 個數據塊，那麼 reiserfs 分區中的第 n 個數據塊也都是這樣一個數據塊，用來標識此後（包括自己）n 的數據塊的狀態。reiserfs 文件系統的磁碟結構如圖 1 所示。
圖 1. reiserfs 分區磁碟布局
與 ext2/ext3 類似，reiserfs 文件系統的一些關鍵信息也保存超級塊中。reiserfs 的超級塊使用一個 reiserfs_super_block 結構來表示，其定義如清單1 所示：
清單1. reiserfs_super_block 結構定義
135 struct reiserfs_super_block_v1 { 136 __le32 s_block_count; /* blocks count */ 137 __le32 s_free_blocks; /* free blocks count */ 138 __le32 s_root_block; /* root block number */ 139 struct journal_params s_journal; 140 __le16 s_blocksize; /* block size */ 141 __le16 s_oid_maxsize; /* max size of object id array, see 142 * get_objectid() commentary */ 143 __le16 s_oid_cursize; /* current size of object id array */ 144 __le16 s_umount_state; /* this is set to 1 when filesystem was 145 * umounted, to 2 - when not */ 146 char s_magic[10]; /* reiserfs magic string indicates that 147 * file system is reiserfs: 148 * "ReIsErFs" or "ReIsEr2Fs" or "ReIsEr3Fs" */ 149 __le16 s_fs_state; /* it is set to used by fsck to mark which 150 * phase of rebuilding is done */ 151 __le32 s_hash_function_code; /* indicate, what hash function is being use 152 * to sort names in a directory*/ 153 __le16 s_tree_height; /* height of disk tree */ 154 __le16 s_bmap_nr; /* amount of bitmap blocks needed to address 155 * each block of file system */ 156 __le16 s_version; /* this field is only reliable on filesystem 157 * with non-standard journal */ 158 __le16 s_reserved_for_journal; /* size in blocks of journal area on main 159 * device, we need to keep after 160 * making fs with non-standard journal */ 161 } __attribute__ ((__packed__)); 162 163 #define SB_SIZE_V1 (sizeof(struct reiserfs_super_block_v1)) 164 165 /* this is the on disk super block */ 166 struct reiserfs_super_block { 167 struct reiserfs_super_block_v1 s_v1; 168 __le32 s_inode_generation; 169 __le32 s_flags; /* Right now used only by inode-attributes, if enabled */ 170 unsigned char s_uuid[16]; /* filesystem unique identifier */ 171 unsigned char s_label[16]; /* filesystem volume label */ 172 char s_unused[88]; /* zero filled by mkreiserfs and 173 * reiserfs_convert_objectid_map_v1() 174 * so any additions must be updated 175 * there as well. */ 176 } __attribute__ ((__packed__)); |
該結構定義中還包含了其他結構的定義，例如 journal_params，這是有關日誌的一個結構，並非本文關注的重點，讀者可以自行參考內核源代碼中的 include/linux/ reiserfs_fs.h 文件。
實際上，超級塊並不需要一個完整的數據塊來存儲，這個數據塊中剩餘的空間用來解決文件對象 id 的重用問題，詳細內容請參看本系列文章下一部分的介紹。
  |
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 個部分，形式如下：
( 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 中與關鍵字有關的定義
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 位長，但是從幾個相關函數中可以清楚地看到這一點。
|
數據塊頭
在圖 2 中我們曾經介紹過，b+ 樹中的節點可以分為格式化節點和未格式化節點兩種。未格式化節點中保存的全部是文件數據，而格式化節點中包含了 b+ 樹本身需要的一些信息。為了與未格式化節點區分開來，每個格式化節點所佔用的數據塊最開頭都使用一個數據塊頭來表示。數據塊頭大小為 24 個位元組，定義如清單 3 所示。
清單3. block_head 結構定義
698 /* Header of a disk block. More precisely, header of a formatted leaf 699 or internal node, and not the header of an unformatted node. */ 700 struct block_head { 701 __le16 blk_level; /* Level of a block in the tree. */ 702 __le16 blk_nr_item; /* Number of keys/items in a block. */ 703 __le16 blk_free_space; /* Block free space in bytes. */ 704 __le16 blk_reserved; 705 /* dump this in v4/planA */ 706 struct reiserfs_key blk_right_delim_key; /* kept only for compatibility */ 707 }; |
block_head 結構中的 blk_level 表示該節點在 B+ 樹中的層次，對於葉子節點來說，該值為 1；blk_nr_item 表示這個數據塊中條目的個數；blk_free_space 表示這個數據塊中的空閑磁碟空間。
格式化節點可以分為中間節點和葉子節點兩類，它們所採用的存儲結構是不同的。
|
中間節點
中間節點由數據塊頭、關鍵字和指針數組構成。中間節點中的關鍵字和指針數組都是按照從小到大的順序依次存放的，它們在磁碟上的布局如圖 3 所示。
圖 3. 中間節點的布局
每個關鍵字就是一個 16 位元組的 reiserfs_key 結構，而指針則是一個 disk_child 結構，其大小為 8 個位元組，定義如清單 4 所示。
清單4. disk_child 結構定義
1086 /* Disk child pointer: The pointer from an internal node of the tree 1087 to a node that is on disk. */ 1088 struct disk_child { 1089 __le32 dc_block_number; /* Disk child's block number. */ 1090 __le16 dc_size; /* Disk child's used space. */ 1091 __le16 dc_reserved; 1092 }; |
其中 dc_block_number 欄位是所指向子節點所在的數據塊塊號，dc_size 表示這個數據塊中已用空間的大小。對於一共有 n 個關鍵字的中間節點來說，第 i 個關鍵字位於 24+i*16 位元組處，對應的指針位於 24+16*n+8*i 位元組處。
需要注意的是，對於中間節點來說，數據塊頭的 blk_nr_item 欄位表示的是關鍵字的個數，而指針數總是比關鍵字個數多 1，這是由 B+ 樹的結構所決定的，小於 Key 0 的關鍵字可以在 Pointer 0 指針指向的數據塊（下一層中間節點或葉子節點）中找到，而介於 Key 0 和 Key 1 之間的關鍵字則保存在 Pointer 1 指向的數據塊中，依此類推。大於Key n的關鍵字可以在Pointer n+1中找到。
|
葉子節點
格式化葉子節點的結構比中間節點的結構稍微複雜一點。為了能夠在一個格式化葉子節點中保存多個條目，reiserfs 採用了如圖 4 所示的布局結構。
圖 4. 格式化葉子節點的布局
從圖中可以看出，每個格式化葉子節點都以一個數據塊頭開始，然後是從兩端向中間伸展的條目頭和條目數據的數組，空閑空間保留在中間，這種設計是為了擴充方便。
所謂條目（item，或稱為項）就是可以存儲在單個節點中的一個數據容器，我們可以認為條目是由條目頭和條目數據體組成的。
清單5. 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 所示。
清單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 所示：
清單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 所示。
圖 5. 目錄條目存儲結構
目錄頭是一個 reiserfs_de_head 結構，大小為 16 位元組，其定義如清單 8 所示。
清單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 給出了間接條目的存儲結構。
圖 6. 間接條目存儲結構
對於預設的 4096 位元組的數據塊來說，一個間接條目所能存儲的數據最大可達 4048 KB（4096*(4096-48)/4 位元組），更大的文件需要使用多個間接條目進行存儲，它們之間的順序是通過關鍵字中的 offset 進行標識的。
另外，文件末尾不足一個數據塊的部分也可以像小文件一樣存儲到直接條目中，這種技術就稱為尾部封裝（tail packing）。在這種情況下，存儲一個文件至少需要使用一個間接條目和一個直接條目。
|
實例分析
下面讓我們來看一個實際的例子，以便了解 reiserfs 中的實際情況是什麼樣子。首先讓我們來創建一個 reiserfs 文件系統，這需要在系統中安裝 reiserfs-utils 包，其中包含的內容如清單 9 所示。
清單9. reiserfs-utils 包中包含的文件
[root@vmfc8 reiserfs]# rpm -ql reiserfs-utils /sbin/debugreiserfs /sbin/fsck.reiserfs /sbin/mkfs.reiserfs /sbin/mkreiserfs /sbin/reiserfsck /sbin/reiserfstune /sbin/resize_reiserfs /usr/share/doc/reiserfs-utils-3.6.19 /usr/share/doc/reiserfs-utils-3.6.19/README /usr/share/man/man8/debugreiserfs.8.gz /usr/share/man/man8/mkreiserfs.8.gz /usr/share/man/man8/reiserfsck.8.gz /usr/share/man/man8/reiserfstune.8.gz /usr/share/man/man8/resize_reiserfs.8.gz |
mkreiserfs 命令用來創建 reiserfs 文件系統，debugreiserfs 用來查看 reiserfs 文件系統的詳細信息，如清單 10 所示。
清單10. 創建 reiserfs 文件系統
[root@ vmfc8 reiserfs]# echo y | mkreiserfs /dev/sda2 [root@vmfc8 reiserfs]# debugreiserfs -m /dev/sda2 debugreiserfs 3.6.19 (2003 www.namesys.com) Filesystem state: consistent Reiserfs super block in block 16 on 0x802 of format 3.6 with standard journal Count of blocks on the device: 977952 Number of bitmaps: 30 Blocksize: 4096 Free blocks (count of blocks - used [journal, bitmaps, data, reserved] blocks): 969711 Root block: 8211 Filesystem is clean Tree height: 2 Hash function used to sort names: "r5" Objectid map size 2, max 972 Journal parameters: Device [0x0] Magic [0x28ec4899] Size 8193 blocks (including 1 for journal header) (first block 18) Max transaction length 1024 blocks Max batch size 900 blocks Max commit age 30 Blocks reserved by journal: 0 Fs state field: 0x0: sb_version: 2 inode generation number: 0 UUID: 02e4b98a-bdf3-4654-9cae-89e38970f43c LABEL: Set flags in SB: ATTRIBUTES CLEAN Bitmap blocks are: #0: block 17: Busy (0-8211) Free(8212-32767) used 8212, free 24556 #1: block 32768: Busy (32768-32768) Free(32769-65535) used 1, free 32767 … #29: block 950272: Busy (950272-950272) Free(950273-977951) Busy(977952-983039) used 5089, free 27679 |
從輸出結果中可以看出，這是大約是一個 4GB 的分區，總共劃分成 977952 個 4096B 大小的數據塊；而超級塊是第 16 個數據塊（從 0 開始計算）。格式化過程中佔用了其中的 8241 個數據塊，其中從第 18 個數據塊開始的 8193 個數據塊用於日誌（第 8210 數據塊供日誌頭使用）。這個 B+ 樹的根節點保存在該分區的第 8211 個數據塊中。另外，數據塊點陣圖總共佔用了 30 個數據塊，-m 參數給出了這些數據塊點陣圖所佔用的數據塊的具體位置，這與前文中的介紹是完全吻合的。
我們真正關心的是存儲實際數據的部分，從中可以了解在 reiserfs 中是如何對文件進行訪問的。下面讓我們來看一個實際文件系統的例子。
清單11. 分析 8211 數據塊的內容
[root@vmfc8 reiserfs]# mount /dev/sda2 /tmp/test [root@vmfc8 reiserfs]# dd if=/dev/sda2 of=block.8211 bs=4096 count=1 skip=8211 [root@vmfc8 reiserfs]# hexdump –C block.8211.hex |
block.8211.hex 文件中就是根節點中的實際數據，圖 7 給出了一個更為清晰的分析結果。
圖 7. 新文件系統根節點的數據分析
從圖 7 中可以清楚地看出，這是一個格式化葉子節點（深度為 1），其中包含 4 個條目：兩個是 STAT 條目，另外兩個是目錄條目。實際上，它們分別是當前目錄和其父目錄。繼續分析就會發現，當前目錄中只包含兩個目錄項：當前目錄及其父目錄，因此這是一個空目錄。
|
|
小結
總體來說，reiserfs 所採用的設計很多都是專門針對如何充分提高空間利用率和改進小文件的訪問速度。與 ext2/ext3 不同，reiserfs 並不以固定大小的塊為單位給文件分配存儲空間。相反，它會恰好分配文件大小的磁碟空間。另外，reiserfs 還包括了圍繞文件末尾而專門設計的尾部封裝方案，將文件名和文件數據（或部分數據）共同保存在 B+ 樹的葉子節點中，而不會像 ext2 那樣將數據單獨保存在一個磁碟上的數據塊中，然後使用一個指針指向這個數據塊的位置。
這種設計會帶來兩個優點。首先，它可以極大地改進小文件的性能。由於文件數據和 stat_data（對應於 ext2 中的 inode）信息都是緊鄰保存的，只需要一次磁碟 I/O 就可以將這些數據全部讀出。其次，可以有效提高對磁碟空間的利用率。統計表明，reiserfs 採用這種設計之後，可以比相應的 ext2 文件系統多存儲超過 6% 的數據。
不過，尾部封裝的設計可能會對性能稍有影響，因為它每次文件發生修改時，都需要重新對尾部數據進行封裝。由於這個原因，reiserfs 的尾部封裝特性被設計為可以關閉的，這樣就為管理員在性能和存儲效率之間可以提供一個選擇。對於性能非常關鍵的應用程序來說，管理員可以使用 notail 選項禁用這個特性，從而犧牲一部分磁碟空間來獲得更好的性能。
與 ext2/ext3 相比，在處理小於 4KB 的文件時，reiserfs 的速度通常會快 10 到 15 倍。這對於新聞組、HTTP 緩存、郵件發送系統以及其他一些小文件性能非常重要的應用程序來說是非常有益的。
（責任編輯：A6）
[火星人 ] 如何恢復 Linux 上刪除的文件已經有1519次圍觀
