前面两篇博文讲了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
阅读(356) | 评论(0) | 转发(0) |