深入解析ext2 文件系统之为dir分配inode

    前面两篇博文讲了ext2文件系统的框架，讲了如何按照需要创建ext2文件系统，这篇博文的重点是目录dir。

    目录是Linux支持的7种文件格式之一，是最常见的两种文件之一。一般来讲目录文件和普通文件是我们最常见的文件。ext2 文件系统是怎么创建目录的呢？这是我们这篇博文的重点。

    我写了一个systemtap的脚本来跟踪部分的ext2文件系统的函数调用。

probe kernel.function("*@fs/ext2/namei.c"),kernel.function("*@fs/ext2/namei.c").return,
      kernel.function("*@fs/ext2/ialloc.c"),kernel.function("*@fs/ext2/ialloc.c").return {
      printf("PID:%d probepoint :%s   execname:%s\n ",pid(),pp(),execname());
}

    上面代码的含义基本是跟踪所有的kernel中ext2文件系统中namei.c和ialloc.c中的function。 进入和退出都打印。
   

[root@localhost systemtap]# stap test.stp
PID:5732 probepoint :kernel.function("ext2_lookup@fs/ext2/namei.c:56")   execname:mkdir
PID:5732 probepoint :kernel.function("iget@include/linux/fs.h:1839")   execname:mkdir
PID:5732 probepoint :kernel.function("ext2_lookup@fs/ext2/namei.c:56").return   execname:mkdir
PID:5732 probepoint :kernel.function("ext2_mkdir@fs/ext2/namei.c:209")   execname:mkdir
PID:5732 probepoint :kernel.function("inode_inc_link_count@include/linux/fs.h:1349")   execname:mkdir
PID:5732 probepoint :kernel.function("inc_nlink@include/linux/fs.h:1344")   execname:mkdir
PID:5732 probepoint :kernel.function("mark_inode_dirty@include/linux/fs.h:1326")   execname:mkdir
PID:5732 probepoint :kernel.function("ext2_new_inode@fs/ext2/ialloc.c:449")   execname:mkdir
PID:5732 probepoint :kernel.function("EXT2_SB@include/linux/ext2_fs.h:74")   execname:mkdir
PID:5732 probepoint :kernel.function("EXT2_I@fs/ext2/ext2.h:87")   execname:mkdir
PID:5732 probepoint :kernel.function("find_group_orlov@fs/ext2/ialloc.c:272")   execname:mkdir
PID:5732 probepoint :kernel.function("percpu_counter_read_positive@include/linux/percpu_counter.h:56")   execname:mkdir
PID:5732 probepoint :kernel.function("percpu_counter_read_positive@include/linux/percpu_counter.h:56")   execname:mkdir
PID:5732 probepoint :kernel.function("percpu_counter_read_positive@include/linux/percpu_counter.h:56")   execname:mkdir
PID:5732 probepoint :kernel.function("brelse@include/linux/buffer_head.h:265")   execname:mkdir
PID:5732 probepoint :kernel.function("read_inode_bitmap@fs/ext2/ialloc.c:47")   execname:mkdir
PID:5732 probepoint :kernel.function("sb_bread@include/linux/buffer_head.h:278")   execname:mkdir
PID:5732 probepoint :kernel.function("read_inode_bitmap@fs/ext2/ialloc.c:47").return   execname:mkdir
PID:5732 probepoint :kernel.function("EXT2_SB@include/linux/ext2_fs.h:74")   execname:mkdir
PID:5732 probepoint :kernel.function("EXT2_SB@include/linux/ext2_fs.h:74")   execname:mkdir
PID:5732 probepoint :kernel.function("brelse@include/linux/buffer_head.h:265")   execname:mkdir
PID:5732 probepoint :kernel.function("EXT2_SB@include/linux/ext2_fs.h:74")   execname:mkdir
PID:5732 probepoint :kernel.function("percpu_counter_inc@include/linux/percpu_counter.h:114")   execname:mkdir
PID:5732 probepoint :kernel.function("EXT2_SB@include/linux/ext2_fs.h:74")   execname:mkdir
PID:5732 probepoint :kernel.function("EXT2_I@fs/ext2/ext2.h:87")   execname:mkdir
PID:5732 probepoint :kernel.function("__constant_c_and_count_memset@include/asm/string.h:419")   execname:mkdir
PID:5732 probepoint :kernel.function("insert_inode_hash@include/linux/fs.h:1862")   execname:mkdir
PID:5732 probepoint :kernel.function("DQUOT_ALLOC_INODE@include/linux/quotaops.h:134")   execname:mkdir
PID:5732 probepoint :kernel.function("mark_inode_dirty@include/linux/fs.h:1326")   execname:mkdir
PID:5732 probepoint :kernel.function("ext2_preread_inode@fs/ext2/ialloc.c:176")   execname:mkdir
PID:5732 probepoint :kernel.function("bdi_congested@include/linux/backing-dev.h:69")   execname:mkdir
PID:5732 probepoint :kernel.function("bdi_read_congested@include/linux/backing-dev.h:76")   execname:mkdir
PID:5732 probepoint :kernel.function("bdi_congested@include/linux/backing-dev.h:69")   execname:mkdir
PID:5732 probepoint :kernel.function("bdi_write_congested@include/linux/backing-dev.h:81")   execname:mkdir
PID:5732 probepoint :kernel.function("EXT2_SB@include/linux/ext2_fs.h:74")   execname:mkdir
PID:5732 probepoint :kernel.function("sb_breadahead@include/linux/buffer_head.h:284")   execname:mkdir
PID:5732 probepoint :kernel.function("ext2_new_inode@fs/ext2/ialloc.c:449").return   execname:mkdir
PID:5732 probepoint :kernel.function("mark_inode_dirty@include/linux/fs.h:1326")   execname:mkdir
PID:5732 probepoint :kernel.function("inode_inc_link_count@include/linux/fs.h:1349")   execname:mkdir
PID:5732 probepoint :kernel.function("inc_nlink@include/linux/fs.h:1344")   execname:mkdir
PID:5732 probepoint :kernel.function("ext2_mkdir@fs/ext2/namei.c:209").return   execname:mkdi

[root@localhost bean]# mkdir dir_b

    创建一个目录(如dir_c），首先是要判断是否已经存在同名的文件，不管是7种文件中的哪一种，都不同有同名文件的存在。ext2_lookup是查找文件的函数，我不是我们重点，而且，毛德操老先生的情景分析花了大量的篇幅讲解，还有linux那些事儿中也讲到非常不错。想看的可以去这两部分参考资料。
   

PID:5732 probepoint :kernel.function("ext2_lookup@fs/ext2/namei.c:56")   execname:mkdir
PID:5732 probepoint :kernel.function("iget@include/linux/fs.h:1839")   execname:mkdir
PID:5732 probepoint :kernel.function("ext2_lookup@fs/ext2/namei.c:56").return   execname:mkdir

    接下来就到了非常重要的ext2_mkdir。这个函数从systemtap跟踪出来的函数来看，调用了大量的函数，我不想一一的去分析每个函数，这样太累，而且，我的能力尚不足以分析每一函数的存在的意义，而且代码就在那里，有闲工夫听我瞎讲不如直接去看 code。 我们换一种大家都易于接受的方式。

    我们知道，文件要有inode，还要有文件实实在在内容，不管你是普通文件还是目录文件。那么第一个问题来了，我要建立一个目录文件我首先就要分配一个inode。我们说过了，ext2文件系统组织成块组的形式，每个块组都有空闲的inode ，都有空闲的block，到底将这个目录文件的inode分配到那个块组管理呢？

    这就是ext2_new_inode函数干的事情，这个函数也是我们关注的重点。

    ext2对于分配目录文件的inode的设计原则是
    1 每个块组尽量的均衡。防止出现一个块组inode快耗尽了，另一个块组还有大量的inode的现象。
    2 目录尽量和它的父目录在一个块组，尽量靠近。
    比如有个目录叫 /home/libin/code/，code尽量和libin在同一个目录，libin尽量和home同     一 个目录。原因也比较简单，物理相邻的块，减少磁盘寻道的时间，读起来比较快，而用户到达libin目录后，需要读其下code的可能性要比读/etc/下目录要大，所以他们在一个群组，甚至挨得近，是有好处的。

    ext2文件系统是怎么做到的呢？
    把大象放入冰箱都需要步骤，ext2分配inode也是需要步骤的。
    1 确定inode所在的块组
    2 在第一步确定的块组free inode位图中寻找一个free inode 分配给这个要建的目录。

    确定inode所在的块组是由find_group_orlov这个内核函数完成的。这个函数是为目录寻找合适块组的函数。 我们看下这个函数是如何满足前文提到的两个原则的：

    1 如果目录是文件系统挂载点下的第一级目录
  

/dev/loop0 on /mnt/bean type ext2 (rw)

   我的ext2文件系统就是挂载在/mnt/bean下的，/mnt/bean/dir就属于挂载点下第一级目录，/mnt/bean/dir/testdir 就不属于第一级目录。
   对于这种情况，目录尽量分散到各个块组。
   方法
1 存在空闲inode
2 目录数要少于上一个块组备选项,
3 块组freeinode数不小于average
4 块组free block数不小于average
遍历所有的块组，找到的块组就是我们要目的块组。如果这四个条件不能同时满足，那么只能退而求其次，谁有freeinode 就是谁了。

[root@localhost bean]# dumpe2fs /dev/loop0
....

Free blocks:              126863
Free inodes:              131061
First block:              0
Block size:               4096
Fragment size:            4096
Reserved GDT blocks:      31
Blocks per group:         32768
Fragments per group:      32768
Inodes per group:         32768

...
Group 0: (Blocks 0-32767)
Primary superblock at 0, Group descriptors at 1-1
Reserved GDT blocks at 2-32
Block bitmap at 33 (+33), Inode bitmap at 34 (+34)
Inode table at 35-1058 (+35)
31703 free blocks, 32757 free inodes, 2 directories
Free blocks: 1065-32767
Free inodes: 12-32768
Group 1: (Blocks 32768-65535)
Backup superblock at 32768, Group descriptors at 32769-32769
Reserved GDT blocks at 32770-32800
Block bitmap at 32801 (+33), Inode bitmap at 32802 (+34)
Inode table at 32803-33826 (+35)
31709 free blocks, 32768 free inodes, 0 directories
Free blocks: 33827-65535
Free inodes: 32769-65536
Group 2: (Blocks 65536-98303)
Block bitmap at 65536 (+0), Inode bitmap at 65537 (+1)
Inode table at 65538-66561 (+2)
31742 free blocks, 32768 free inodes, 0 directories
Free blocks: 66562-98303
Free inodes: 65537-98304
Group 3: (Blocks 98304-131071)
Backup superblock at 98304, Group descriptors at 98305-98305
Reserved GDT blocks at 98306-98336
Block bitmap at 98337 (+33), Inode bitmap at 98338 (+34)
Inode table at 98339-99362 (+35)
31709 free blocks, 32768 free inodes, 0 directories
Free blocks: 99363-131071
Free inodes: 98305-131072

干干净净的ext2文件系统，挂载在/mnt/bean目录下。共4个块组，我要建立第一个目录，看下选哪个块组。
         free block                      free inode          total dir
------------------------------------------------------------------------------------
块组0      31703                           32757                2
块组1      31709                           32768                0
块组2      31742                           32768                0
块组3      31709                           32768                0
aver       31715                           32765                *
------------------------------------------------------------------------------------
满足条件的只有块组2 。其他的free block都低于平均值。之所以块组2的free block 比较多是由于他们各有GDT和super block。

[root@localhost bean]# mkdir dir_0
[root@localhost bean]# ll -ai
total 36
2 drwxr-xr-x 4 root root  4096 Aug  4 11:18 .
9273345 drwxr-xr-x 5 root root  4096 Aug  1 11:56 ..
65537 drwxr-xr-x 2 root root  4096 Aug  4 11:18 dir_0
11 drwx------ 2 root root 16384 Aug  4 11:03 lost+found

    2 如果目录不是挂载点下的第一级目录。
    除了考虑的比较目录个数 ，free inode 个数，和free block个数，这种情况下增加了一个考虑，kernel称之为debt ，翻译成中文就是债。这个名字起得还是很形象的。债是什么意思呢？

    目录文件是为普通文件存在的，可是有些情况下只有目录文件，目录下空空如也。债的含义其实就是统计这种情况的，当然是粗略的统计。对于这种这有目录没有普通，也就不占额外block，但是我们必须为这种目录预留一定的block，因为用户建立目录大多数的情况都是为了保存普通文件。 有点绕，呵呵。换个角度，用户创建了目录，不在目录下写文件，这种行为是需要受到限制的，比如说公司需要管理人员，也需要普通的工作人员，正常来讲一个管理人员管理N个普通工作人员。但是如果公司不停地来管理人员，就是不来普通工作人员，这样管理人员手下没有兵，这是很不正常的情况，如果管理人员太多，把办公环境占的满满的，就是想招普通工作人员，也没办公环境提供了。就是这个道理。

    公司计算一下目前的目前公司的管理人员：工作人员的比例，在考虑办公环境容纳的人数，可以大致的计算出最多能涌进多少手下没兵的管理人员。如果手下没兵的管理人员已经超过警戒线了，那么，如果还需要塞进一个管理人员（目录），那么不好意思，我们南京分公司（这个块组）已经债太多了，请去另一个块组--苏州分公司问问。

    我算算平均一共用了多少个目录，一个用了多少block ，kernel大概清楚每个目录大概需要多少个blk，当然这只是粗略的统计。 我们

blocks_per_dir = (le32_to_cpu(es->s_blocks_count)-free_blocks) / ndirs;
max_debt = EXT2_BLOCKS_PER_GROUP(sb) / max(blocks_per_dir, BLOCK_COST);

if (max_debt * INODE_COST > inodes_per_group)    max_debt = inodes_per_group / INODE_COST;    if (max_debt > 255)        max_debt = 255;    if (max_debt == 0)        max_debt = 1;

   
    怎么看出来尽量子级目录和父目录尽量在一个块组呢。 因为从父目录开始找起，如果父目录能满足负债不多，并且block inode 目录个数 的情况和平均情况差不多，那么就选择父目录所在的块组。这样定位起来就快了。

    下面还有在块组中选择inode，这个就比较简单了，块组描述符中有位图，可以选择没有分配的inode。我就不赘述了。

参考文献：
1 kernel code
2 systemtap_beginners_guide