sundayhut's Blog

Ext4文件系统目录项有两种实现方式：

方式一：线性方式

        该方式的目录项以ext4_dir_entry_2的结构一个接连一个直接存储在目录结点所指向的block块中。（缺省配置使用ext4_dir_entry_2这个结构）

 

方式二：Hash树的方式

        若目录下的文件数量很多，则若按照线性方式查找对应文件名的信息则会很低效。Hash树的方式，则可以用文件名来做hash计算，从而定位到对应文件的目录项结构所在的block，从而缩小查找范围、加快查找效率。

 

1.查看文件系统是否开启了方式二的目录管理方式

      root@f303server:~# tune2fs -l /dev/sde3 | grep dir_index

Filesystem features:      has_journal ext_attr resize_inode dir_index filetype needs_recovery extent flex_bg sparse_super large_file huge_file uninit_bg 

  输入如上指令，则可以发现文件系统的目录已经开启了hash树的管理方式。

 

2.hash树管理方式的打开和关闭

      在上述开启状态下，我们可以关闭hash树目录管理方式。关闭之后再打开。

root@f303server:~# tune2fs -O ^dir_index /dev/sde3

tune2fs 1.42.11 (09-Jul-2014)

root@f303server:~# tune2fs -l /dev/sde3 | grep dir_index  # 查找不到了

root@f303server:~# tune2fs -O dir_index /dev/sde3

tune2fs 1.42.11 (09-Jul-2014)

root@f303server:~# tune2fs -l /dev/sde3 | grep dir_index

Filesystem features:      has_journal ext_attr resize_inode dir_index filetype needs_recovery extent flex_bg sparse_super large_file huge_file uninit_bg dir_nlink extra_isize

root@f303server:~# 

 

 

3.怎么判断某目录是否以hash树的方式管理

 

    文件系统开启了hash树管理目录结点的方式并不意味着所有的目录都按树形结构组织管理。在文件系统中，系统会根据某个目录底下文件的多少来自动进行目录管理方式的选择，只有当文件数量大于某个数时，才会采用hash树管理方式。

 

    怎么判断某目录的管理方式是那种？

   

    若不是hash树的管理方式，则htree中debugfs中则会有如下提示

 

 

 

 

     若是hash树的管理方式，则

debugfs:  htree linux-2.6.34.14/kernel 显示如下

 

 

Root node dump:
         Reserved zero: 0
         Hash Version: 1
         Info length: 8
         Indirect levels: 0
         Flags: 0
Number of entries (count): 2
Number of entries (limit): 508
Entry #0: Hash 0x00000000, block 1
Entry #1: Hash 0x775173ee, block 2

Entry #0: Hash 0x00000000, block 1
Reading directory block 1, phys 3154297
791969 0x33788c78-7df72ede (20) rtmutex.c   
791971 0x12e2688e-f00920c3 (28) .latencytop.o.cmd   
791973 0x6d76fd8a-f7dad208 (16) futex.o   
791974 0x1f1d389c-0beb6325 (20) ns_cgroup.c   
791975 0x21f726a2-367f43fb (24) .built-in.o.cmd   
791977 0x2a43c4ba-ae0695eb (16) itimer.o   
791978 0x6139ce78-4032f3c2 (16) user.c   
791979 0x615af808-2478500b (24) test_kprobes.c   
791981 0x30feba52-ba8da1e9 (20) audit_tree.c   
791982 0x24bb2b3c-8100eb0d (20) kallsyms.o   
791987 0x71a57d4c-81410e0a (20) .uid16.o.cmd   
791989 0x3e1650ba-3d29a28e (20) freezer.c   
791991 0x0ba6a23a-978af98d (20) spinlock.o   
791992 0x1c6819e6-010b1d97 (24) sched_clock.o   
791997 0x6dc7a2ac-6b0769cb (12) gcov   792005 0x1db5303a-76fff9c7 (16) cpu.o   
792009 0x74def468-a27557c6 (20) .timer.o.cmd   
792010 0x540fdfac-e9e8121b (20) slow-work.o   
792014 0x4c0dc1c8-05179835 (24) Kconfig.preempt   
792018 0x620198da-2fb834e3 (16) cred.c   
792019 0x5973e25e-39b86f3d (32) .cgroup_freezer.o.cmd   
792021 0x1077ffa8-16896967 (16) sys.o   
792025 0x4011172e-63cbf0ec (28) .audit_tree.o.cmd   
792026 0x4c92aabc-1f86d6e5 (20) seccomp.o   
792027 0x5d7f2368-8aaa1cf9 (20) latencytop.c   
792028 0x2ff6ae9c-7b348c25 (24) pid_namespace.o   
792030 0x5f780482-e9fe78e9 (16) groups.o   
792031 0x6079e2b2-acbbff3a (24) rcutree_plugin.h   
792034 0x624e25c0-64cbfd07 (20) stacktrace.o   
792035 0x6e2d0608-09d837e7 (24) .sys_ni.o.cmd   
792036 0x7035c67c-3620d4f6 (16) uid16.o   
792038 0x5b9c06d0-57b802ad (24) .rcutree.o.cmd   
792039 0x356bc37c-95dc4cfb (16) fork.o   
792042 0x46df975e-cef87f2d (16) async.c 

该文如下部分探讨按照方式1组织的目录结构：

1.为了理解后文，首先了解ext4_dir_entry_2的每一个元素

 

上表我们可以看到该结构中共5个数据项，前四项占8byte，

通过根目录为例，通过hexdump查看其二进制代码，则“目录项的长度（ren_len）= 文件名长度(name_len) + 8 ”。但是在很多情况下rec_len > = name_len + 8。原因是因为目录项每一项的起始位置必须按照后两位 00 对齐。故有时候会浪费几个字节。

 

 2.通过hexdump指令直接查看二进制内容

先通过

debugfs /dev/sde3

stat .

查找到根目录文件数据所在的块为9249，块大小为4K，故根目录数据所在的起始地址36996k。

 

root@f303server:~# hexdump -C /dev/sde3 -s 36996k -n 4096

02421000  02 00 00 00 0c 00 01 02  2e 00 00 00 02 00 00 00  |................|

02421010  0c 00 02 02 2e 2e 00 00  0b 00 00 00 14 00 0a 02  |................|

02421020  6c 6f 73 74 2b 66 6f 75  6e 64 00 00 01 00 0c 00  |lost+found......|

02421030  0c 00 04 02 64 69 72 31  01 00 0e 00 0c 00 04 02  |....dir1........|

02421040  64 69 72 32 0d 00 00 00  10 00 08 01 73 64 65 33  |dir2........sde3|

02421050  2e 74 78 74 0e 00 00 00  10 00 05 01 32 2e 74 78  |.txt........2.tx|

02421060  74 74 2e 73 11 00 00 00  10 00 05 01 33 2e 74 78  |tt.s........3.tx|

02421070  74 74 2e 73 01 00 10 00  0c 00 04 02 64 69 72 33  |tt.s........dir3|

02421080  01 00 12 00 0c 00 04 02  6d 6b 66 73 0c 00 00 00  |........mkfs....|

02421090  18 00 0e 01 62 6c 6b 74  72 61 63 65 5f 73 74 75  |....blktrace_stu|

024210a0  64 79 65 33 15 00 00 00  18 00 10 01 62 6c 6b 74  |dye3........blkt|

024210b0  72 61 63 65 5f 73 74 75  64 79 2e 63 10 00 00 00  |race_study.c....|

024210c0  14 00 0b 01 67 63 63 5f  62 6c 6b 74 2e 73 68 00  |....gcc_blkt.sh.|

024210d0  0f 00 00 00 10 00 07 01  6e 65 77 2e 74 78 74 63  |........new.txtc|

024210e0  12 00 00 00 1c 00 13 01  62 6c 6b 74 72 61 63 65  |........blktrace|

024210f0  5f 73 74 75 64 79 2d 76  31 2e 63 01 01 00 02 00  |_study-v1.c.....|

02421100  10 00 06 02 4e 65 77 44  69 72 61 63 13 00 00 00  |....NewDirac....|

02421110  1c 00 13 01 62 6c 6b 74  72 61 63 65 5f 73 74 75  |....blktrace_stu|

02421120  64 79 2d 76 32 2e 63 77  14 00 00 00 18 00 0e 01  |dy-v2.cw........|

02421130  64 72 6f 70 5f 63 61 63  68 65 73 2e 73 68 79 2e  |drop_caches.shy.|

02421140  01 00 04 00 10 00 06 02  73 64 65 31 63 70 15 01  |........sde1cp..|

02421150  01 00 08 00 b0 0e 0f 02  6c 69 6e 75 78 2d 32 2e  |........linux-2.|

02421160  36 2e 33 34 2e 31 34 00  00 00 00 00 00 00 00 00  |6.34.14.........|

02421170  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|

*

02422000

 

上图中每个颜色表示一个dentry的记录

 

例1：

观察lost+found目录：

Rec_len = 0x 00 14   name_len = 0a

 

则rec_len = name_len +8 +2   则在对齐时浪费了第三行的第11、12个字节。

 

例2：

我们看到2.txt的文件名变成了2.txtt.s

 

原因是最后三个字节是无效字节，在对齐时已经去掉，对齐时三个字节的内容是随便填充的。