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

 

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

 

 

 

 

 

前言：

linux内核是一个很伟大的东西。。。（好吧~我居然用“伟大”来形容了linux内核），不过说实话，内核代码绝对是c语言中经典的经典。里面的一些设计思想都值得反复推敲、琢磨（虽然我还看不大懂，在啃过程中）。。按照我导师的话来说：写linux内核的那帮人绝对是顶级聪明的人。

看聪明人的作品，熏陶 熏陶自己。

我们今天关注问题如下：why linux的文件系统设计group这个概念。有什么好处呢？linux文件系统已经够复杂了，为什么还要加上group这个管理单元？

那天导师问这问题时，我硬是没怎么反应过来，说了几个答案，但都没说到点上，这儿我总结一下：

面对问题的思考方法：

从多角度思考这个问题：

从用户角度：方便用户容量的扩充或减少

    很明显，有了group这个概念，我们的元数据区、数据区可以一个版块一个版块地管理，如果用户容量扩充，只需要在现有group后增加几个group，然后修改super block，GDT(块组描述符)等就可以了。减小容量也是如此；试想一下如下没有group这个概念，若要扩容，则inode bitmap，data bitmap，inode table所占的空间都要变大，那么整个数据区都要向后迁移，代价太大。

从计算机性能角度：一次IO能抓取所需元数据，提高访问速度

    首先我们要知道，在默认的配置中，一个group单元中的block bitmap的个数为32768，这个在格式化磁盘时，可以在输出信息上看到信息：32768 blocks per group。所以说block bitmap所需要的占用的存储空间大小刚好为1个block大小，即4k，所以说在一次IO读操作，我就可以把当前访问数据的bitmap区域的元数据一次性缓存，由于与访问的局部性，一段时间访问的数据很大概率都是位于这个block的，所以需要多次访问元数据，而这些元数据系统都cache住了，故性能得到很好地提高。

     上面说的是block bitmap为4k，默认一个group中inode bitmap为1k。也是可以一次IO都缓存下的。而且data区域4k*8*4k= 128M，这个大小都是一次调入Mem可以缓存下的。所以极大提高了cache命中率，也就提高了访问速率。

     其实上述的解释都可以类比于一个概念：对齐。在计算机系统结构中，一定要建立一个对齐的概念，对齐的概念我通过两个例子稍微解释。

例1：一个数据结构如果放在未对齐的内存中，则会引起两次访存操作。

例2：放在磁盘上一个4k的文件，如果跨了两个block，那么要进行两次访问disk的操作，效率大打折扣。

所以说计算机系统结构中，对齐是效率的一个关键点所在。

从磁盘寿命的角度：写均匀，延长寿命

元数据、数据写的区域因为布局方式的因素，因而把写均匀到了磁盘的各个区域。个人感觉有一定的延长寿命作用。

 

关于group概念还能带来什么好处，欢迎留言！

 

补充：

这里对group概念稍做介绍，文件系统结构图如下：

 

文件系统是以分区为单位的，所以说一个分区上的所有group的文件系统类型都相同。

整个分区group的inode是连续编号的，给定一个inode编号，可以通过取模、取余的方式可以知道该inode为那个group上的第几个inode。inode编号从1开始，故所在块组bg=inode_num -1)/ ext4_super_block.s_inodes_per_group 

所在 块组的index

index=(inode_num -1) % ext4_super_block.s_inodes_per_group