概述

本篇博客中我们主要阐述ext2文件系统创建文件和目录的实现原理。

文件系统中每个文件/目录有两个结构来描述该文件的元数据信息,第一是文件目录项即struct dentry,主要保存文件名至文件inode号的映射,第二是文件inode结构,保存文件元数据信息。而对应在磁盘上,每个文件目录项保存在父目录的数据块中,而文件inode在ext2文件系统中则保存在磁盘的特定区域(块组的inode table中),每个磁盘inode均对应一个唯一的编号。

因此,总的说来,创建一个文件最主要的步骤就是:1.为文件创建一个文件目录项,2.为文件创建一个inode结构并分配inode号,将inode编号与文件名映射关系保存在1中分配的文件目录项中,3.将1中创建的文件目录项写入到父目录的数据区。而其中最主要和最复杂的过程是2。

实现

linux内核中创建文件的入口函数为sys_create()。该函数的实现如下:

SYSCALL_DEFINE2(creat, const char __user *, pathname, int, mode)  
{  
    return sys_open(pathname, O_CREAT | O_WRONLY | O_TRUNC, mode);  
}  

它只是对sys_open的简单封装,并将open的打开标志设置为O_CREAT | O_WRONLY | O_TRUNC。

SYSCALL_DEFINE3(open, const char __user *, filename, int, flags, int, mode)  
{  
    long ret;  

    if (force_o_largefile())  
        flags |= O_LARGEFILE;  

    ret = do_sys_open(AT_FDCWD, filename, flags, mode);  
    /* avoid REGPARM breakage on x86: */  
    asmlinkage_protect(3, ret, filename, flags, mode);  
    return ret;  
}  

sys_open的实现较为复杂,其复杂性体现在do_sys_open()函数,关于该函数我们不去深入钻研太多,在后面的博客中我们会仔细分析open的处理流程。

long do_sys_open(int dfd, const char __user *filename, int flags, int mode)  
{  
    char *tmp = getname(filename);  
    int fd = PTR_ERR(tmp);  

    if (!IS_ERR(tmp)) {  
        fd = get_unused_fd_flags(flags);  
        if (fd >= 0) {  
            struct file *f = do_filp_open(dfd, tmp, flags, mode, 0);  
            if (IS_ERR(f)) {  
                put_unused_fd(fd);  
                fd = PTR_ERR(f);  
            } else {  
                fsnotify_open(f);  
                fd_install(fd, f);  
            }  
        }  
        putname(tmp);  
    }  
    return fd;  
}

do_sys_open()接着调用了do_filp_open()。这一路走下去,对于文件创建的分支,最后调用的函数为vfs_create(),至于这其中的逻辑和函数跳转,我们就不再仔细描述,在后续的博客中会有详细描述。

int vfs_create(struct inode *dir, struct dentry *dentry, int mode,  
        struct nameidata *nd)  
{  
    int error = may_create(dir, dentry);  

    if (error)  
        return error;  

    if (!dir->i_op->create)  
        return -EACCES; /* shouldn't it be ENOSYS? */  
    mode &= S_IALLUGO;  
    mode |= S_IFREG;  
    error = security_inode_create(dir, dentry, mode);  
    if (error)  
        return error;  
    error = dir->i_op->create(dir, dentry, mode, nd);  
    if (!error)  
        fsnotify_create(dir, dentry);  
    return error;  
} 

在vfs_create中,最核心的函数是调用了目录的i_op的create方法,对ext2文件系统来说,该方法的具体实现为ext2_create()。

static int ext2_create (struct inode * dir, struct dentry * dentry, int mode, struct nameidata *nd)  
{  
    struct inode *inode;  

    dquot_initialize(dir);  
    /* 首先创建内存inode结构 
    ** 并分配inode号 
    */    
    inode = ext2_new_inode(dir, mode);  
    if (IS_ERR(inode))  
        return PTR_ERR(inode);  

    //ext2_create just create a regular file,not a dir ,not symlink either  
    inode->i_op = &ext2_file_inode_operations;  
    if (ext2_use_xip(inode->i_sb)) {  
        inode->i_mapping->a_ops = &ext2_aops_xip;  
        inode->i_fop = &ext2_xip_file_operations;  
    } else if (test_opt(inode->i_sb, NOBH)) {  
        inode->i_mapping->a_ops = &ext2_nobh_aops;  
        inode->i_fop = &ext2_file_operations;  
    } else {  
        inode->i_mapping->a_ops = &ext2_aops;  
        inode->i_fop = &ext2_file_operations;  
    }  
    /* 标记inode为脏*/  
    mark_inode_dirty(inode);  
    /* 将文件与其父目录挂钩*/  
    return ext2_add_nondir(dentry, inode);  
}

如概述中描述,ext2中真正的文件创建包含以下3方面的工作:

  1. 为文件创建内存目录项;
  2. 分配内存inode结构并在磁盘上为其分配inode号;
  3. 文件目录项写回 。

以下分别就这三个方面来详加描述。

创建内存目录项

其实ext2_create()的调用者在调用该函数之前就已经创建好了内存目录项,并作为第一个参数传入,只是目前该内存目录项里面的内容还是无效的,因为inode号都尚未分配。

创建inode

分配inode的含义有两层:1.分配一个特定文件系统的内存inode结构,如ext2文件系统的struct ext2_inode_info,其中包含了vfs层inode结构,因此可随便根据其中之一便可相互转化。2.为创建的内存inode在磁盘上的inode区分配一个尚未使用的inode编号。

创建内存inode

创建内存inode结构相对来说比较简单,一般来说,每种文件系统超级块均提供了一组特定的函数,在该函数中便存在一个create_inode函数,大致来说,该函数会从每种文件系统在模块初始化时创建的inode内存池中分配一个内存inode。这样做是因为每种文件系统其内存inode结构不尽相同,如果由操作系统来统一分配会产生这样的问题:操作系统无法自行知道要分配的inode大小。

分配inode号

这是inode分配的主要部分,因为它需要根据文件系统磁盘布局选择将inode存放在哪个group中,选择的inode应能最大化文件系统IO性能,具体特征是:1.文件inode尽量和文件数据连续,2.文件inode尽量和父目录inode连续,3.文件尽量均匀分布在磁盘上。

ext2将磁盘划分成多个block group,每个块组均存在自己的inode table。因此,分配inode的第一步也是最关键的一步是选择将文件inode存放在哪个group中。根据创建文件的类型不同,ext2采用的分配算法也不尽相同。ext2分配inode函数是ext2_new_inode

创建目录

若创建的是一个目录,则分配算法调用的函数是find_group_orlov,总的来说,该分配算法主要思想和流程可如下描述:

  • 若创建的目录是顶级目录,即在根目录”/”下创建子目录,那么此时需要考虑将该目录均匀分布到磁盘的所有group中。因此,其做法是首先随机选择一个group(真正的随机),从该group开始顺序扫描磁盘的所有group,直到遇到一个符合条件的group,即:1.拥有最少的文件数,2.大于平均数的空闲inode数,3.大于平均数的空闲block数。如果没有找到,转步骤3;
  • 若创建的并非顶级目录,从父目录所在的块组开始搜索,找到第一个这样的group:小于阈值的dir数量,2.大于阈值的空闲inode数,3.大于阈值的空闲磁盘block数。若发现这样的group,立即返回,否则,转步骤3;
  • 流程到此说明1和2没有成功,那么需要放松搜索条件,让我们从第0个group开始,直到发现这样一个group我们便可立即返回:该group中空闲inode数超过平均值。如果没有找到这样的group,那么下面的步骤;
  • 进一步放松条件,将平均空闲inode数设置为0,再转步骤3作再次搜索,如果还没有找到,那么只能放弃,说明系统没有空闲inode可用。返回失败。

创建普通文件

若创建的是普通文件,则调用函数find_group_other来分配group,该分配算法相对上面创建目录简单了许多,具体算法流程如下描述:

  • 检查文件父目录inode所在的group是否有空闲block和空闲inode,如果有,那么直接返回该group号即可,如果没有,那么转步骤2,这样做是尽量将文件与父目录放在相同的group中,根据程序局部性原理,访问父目录以后很有可能继续访问父目录下的文件、子目录。将父目录与文件连续存放有利于加速这一访问过程;
  • 根据一定算法挑选下一次搜索的group号,该算法无需仔细了解,判断该group是否有空闲inode和block,如果还是没有,那么转步骤3,否则直接返回;
  • 至此,需要降低条件,还是继续从父目录inode所在group开始顺序搜索,找到第一个这样的group:有空闲inode即可,此时返回该group,如果该步骤也失败了,说明系统确实无空闲inode可用,只好返回失败。

上面确定了从哪个group去分配磁盘inode,接下来需要读出该group中inode table的bitmap,每个inode table的bitmap占据了1个磁盘块,因此为其分配一个buffer_head并读出inode table的bitmap即可。关于vfs的缓存框架可参考另外一篇技术报告。读出inode table的bitmap以后,从bitmap中寻找未使用的inode,并根据inode位置计算出该inode号,接下来即可根据该磁盘inode号初始化1中分配的内存inode结构,并将上述bitmap所在的buffer_head设置为dirty(因为其数据已被修改)。然后将内存inode结构也标记为脏。

至此,分配inode已经结束。

文件目录项写回

ext2在创建文件完成上述步骤后,最后一步便是修改父目录的文件目录项,因为此时在父目录下面又增加了一个文件,需要以文件目录项的形式反映到父目录中,因此,系统会调用函数ext2_add_link()来完成这最后一个步骤。

ext2_add_link主要步骤如下:

  1. 确定本文件目录项所需的空间大小,主要是根据文件名的长度来确定;
  2. 遍历该目录所有的文件目录项页面,对每个保存目录项的页面,首先调用ext2_get_page()从内存中找到或者磁盘上取出该文件目录项缓存页面;
  3. 在每个缓存页面中线性搜索文件目录项之间是否有空间可容纳这个全新的文件目录项结构,搜索的过程中还会判断拥有该文件名的文件是否已经存在,如果存在,返回错误代码-EXIST,如果不存在且有那么就将文件目录项写在该地方。
  4. 将文件目录项(主要是文件名)写入目录文件的特定页面之后,需要更新父目录的inode,将父目录inode标记为脏,甚至必要的时候会将父目录inode同步到磁盘上。调用了函数ext2_commit_chunk来完成写入之后的一系列工作。

总结

总体来说,ext2文件系统的目录文件将所有子文件、子目录的文件目录项组织成线性结构,这样对于一个大目录下查找文件效率会非常低下,用脚趾头都能想明白。