Chinaunix首页 | 论坛 | 博客
  • 博客访问: 521554
  • 博文数量: 257
  • 博客积分: 1666
  • 博客等级: 上尉
  • 技术积分: 1535
  • 用 户 组: 普通用户
  • 注册时间: 2012-04-02 23:02
文章分类

全部博文(257)

文章存档

2013年(2)

2012年(255)

分类:

2012-08-06 12:55:02

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

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

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


  1. probe kernel.function("*@fs/ext2/namei.c"),kernel.function("*@fs/ext2/namei.c").return,
  2.       kernel.function("*@fs/ext2/ialloc.c"),kernel.function("*@fs/ext2/ialloc.c").return {
  3.       printf("PID:%d probepoint :%s execname:%s\n ",pid(),pp(),execname());
  4. }
    上面代码的含义基本是跟踪所有的kernel中ext2文件系统中namei.c和ialloc.c中的function。 进入和退出都打印。
   
  1. [root@localhost systemtap]# stap test.stp
  2. PID:5732 probepoint :kernel.function("ext2_lookup@fs/ext2/namei.c:56") execname:mkdir
  3. PID:5732 probepoint :kernel.function("iget@include/linux/fs.h:1839") execname:mkdir
  4. PID:5732 probepoint :kernel.function("ext2_lookup@fs/ext2/namei.c:56").return execname:mkdir
  5. PID:5732 probepoint :kernel.function("ext2_mkdir@fs/ext2/namei.c:209") execname:mkdir
  6. PID:5732 probepoint :kernel.function("inode_inc_link_count@include/linux/fs.h:1349") execname:mkdir
  7. PID:5732 probepoint :kernel.function("inc_nlink@include/linux/fs.h:1344") execname:mkdir
  8. PID:5732 probepoint :kernel.function("mark_inode_dirty@include/linux/fs.h:1326") execname:mkdir
  9. PID:5732 probepoint :kernel.function("ext2_new_inode@fs/ext2/ialloc.c:449") execname:mkdir
  10. PID:5732 probepoint :kernel.function("EXT2_SB@include/linux/ext2_fs.h:74") execname:mkdir
  11. PID:5732 probepoint :kernel.function("EXT2_I@fs/ext2/ext2.h:87") execname:mkdir
  12. PID:5732 probepoint :kernel.function("find_group_orlov@fs/ext2/ialloc.c:272") execname:mkdir
  13. PID:5732 probepoint :kernel.function("percpu_counter_read_positive@include/linux/percpu_counter.h:56") execname:mkdir
  14. PID:5732 probepoint :kernel.function("percpu_counter_read_positive@include/linux/percpu_counter.h:56") execname:mkdir
  15. PID:5732 probepoint :kernel.function("percpu_counter_read_positive@include/linux/percpu_counter.h:56") execname:mkdir
  16. PID:5732 probepoint :kernel.function("brelse@include/linux/buffer_head.h:265") execname:mkdir
  17. PID:5732 probepoint :kernel.function("read_inode_bitmap@fs/ext2/ialloc.c:47") execname:mkdir
  18. PID:5732 probepoint :kernel.function("sb_bread@include/linux/buffer_head.h:278") execname:mkdir
  19. PID:5732 probepoint :kernel.function("read_inode_bitmap@fs/ext2/ialloc.c:47").return execname:mkdir
  20. PID:5732 probepoint :kernel.function("EXT2_SB@include/linux/ext2_fs.h:74") execname:mkdir
  21. PID:5732 probepoint :kernel.function("EXT2_SB@include/linux/ext2_fs.h:74") execname:mkdir
  22. PID:5732 probepoint :kernel.function("brelse@include/linux/buffer_head.h:265") execname:mkdir
  23. PID:5732 probepoint :kernel.function("EXT2_SB@include/linux/ext2_fs.h:74") execname:mkdir
  24. PID:5732 probepoint :kernel.function("percpu_counter_inc@include/linux/percpu_counter.h:114") execname:mkdir
  25. PID:5732 probepoint :kernel.function("EXT2_SB@include/linux/ext2_fs.h:74") execname:mkdir
  26. PID:5732 probepoint :kernel.function("EXT2_I@fs/ext2/ext2.h:87") execname:mkdir
  27. PID:5732 probepoint :kernel.function("__constant_c_and_count_memset@include/asm/string.h:419") execname:mkdir
  28. PID:5732 probepoint :kernel.function("insert_inode_hash@include/linux/fs.h:1862") execname:mkdir
  29. PID:5732 probepoint :kernel.function("DQUOT_ALLOC_INODE@include/linux/quotaops.h:134") execname:mkdir
  30. PID:5732 probepoint :kernel.function("mark_inode_dirty@include/linux/fs.h:1326") execname:mkdir
  31. PID:5732 probepoint :kernel.function("ext2_preread_inode@fs/ext2/ialloc.c:176") execname:mkdir
  32. PID:5732 probepoint :kernel.function("bdi_congested@include/linux/backing-dev.h:69") execname:mkdir
  33. PID:5732 probepoint :kernel.function("bdi_read_congested@include/linux/backing-dev.h:76") execname:mkdir
  34. PID:5732 probepoint :kernel.function("bdi_congested@include/linux/backing-dev.h:69") execname:mkdir
  35. PID:5732 probepoint :kernel.function("bdi_write_congested@include/linux/backing-dev.h:81") execname:mkdir
  36. PID:5732 probepoint :kernel.function("EXT2_SB@include/linux/ext2_fs.h:74") execname:mkdir
  37. PID:5732 probepoint :kernel.function("sb_breadahead@include/linux/buffer_head.h:284") execname:mkdir
  38. PID:5732 probepoint :kernel.function("ext2_new_inode@fs/ext2/ialloc.c:449").return execname:mkdir
  39. PID:5732 probepoint :kernel.function("mark_inode_dirty@include/linux/fs.h:1326") execname:mkdir
  40. PID:5732 probepoint :kernel.function("inode_inc_link_count@include/linux/fs.h:1349") execname:mkdir
  41. PID:5732 probepoint :kernel.function("inc_nlink@include/linux/fs.h:1344") execname:mkdir
  42. PID:5732 probepoint :kernel.function("ext2_mkdir@fs/ext2/namei.c:209").return execname:mkdi
  1. [root@localhost bean]# mkdir dir_b

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

  1. PID:5732 probepoint :kernel.function("ext2_lookup@fs/ext2/namei.c:56") execname:mkdir
  2. PID:5732 probepoint :kernel.function("iget@include/linux/fs.h:1839") execname:mkdir
  3. 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 如果目录是文件系统挂载点下的第一级目录
  
  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 就是谁了。


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

  3. Free blocks: 126863
  4. Free inodes: 131061
  5. First block: 0
  6. Block size: 4096
  7. Fragment size: 4096
  8. Reserved GDT blocks: 31
  9. Blocks per group: 32768
  10. Fragments per group: 32768
  11. Inodes per group: 32768

  12. ...
  13. Group 0: (Blocks 0-32767)
  14. Primary superblock at 0, Group descriptors at 1-1
  15. Reserved GDT blocks at 2-32
  16. Block bitmap at 33 (+33), Inode bitmap at 34 (+34)
  17. Inode table at 35-1058 (+35)
  18. 31703 free blocks, 32757 free inodes, 2 directories
  19. Free blocks: 1065-32767
  20. Free inodes: 12-32768
  21. Group 1: (Blocks 32768-65535)
  22. Backup superblock at 32768, Group descriptors at 32769-32769
  23. Reserved GDT blocks at 32770-32800
  24. Block bitmap at 32801 (+33), Inode bitmap at 32802 (+34)
  25. Inode table at 32803-33826 (+35)
  26. 31709 free blocks, 32768 free inodes, 0 directories
  27. Free blocks: 33827-65535
  28. Free inodes: 32769-65536
  29. Group 2: (Blocks 65536-98303)
  30. Block bitmap at 65536 (+0), Inode bitmap at 65537 (+1)
  31. Inode table at 65538-66561 (+2)
  32. 31742 free blocks, 32768 free inodes, 0 directories
  33. Free blocks: 66562-98303
  34. Free inodes: 65537-98304
  35. Group 3: (Blocks 98304-131071)
  36. Backup superblock at 98304, Group descriptors at 98305-98305
  37. Reserved GDT blocks at 98306-98336
  38. Block bitmap at 98337 (+33), Inode bitmap at 98338 (+34)
  39. Inode table at 98339-99362 (+35)
  40. 31709 free blocks, 32768 free inodes, 0 directories
  41. Free blocks: 99363-131071
  42. 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。
  1. [root@localhost bean]# mkdir dir_0
  2. [root@localhost bean]# ll -ai
  3. total 36
  4. 2 drwxr-xr-x 4 root root 4096 Aug 4 11:18 .
  5. 9273345 drwxr-xr-x 5 root root 4096 Aug 1 11:56 ..
  6. 65537 drwxr-xr-x 2 root root 4096 Aug 4 11:18 dir_0
  7. 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,当然这只是粗略的统计。 我们

  1. blocks_per_dir = (le32_to_cpu(es->s_blocks_count)-free_blocks) / ndirs;
  2. max_debt = EXT2_BLOCKS_PER_GROUP(sb) / max(blocks_per_dir, BLOCK_COST);
  3.    
  4. 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


阅读(357) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~