动手写一个简单的文件系统.md

作者: vergilzhang | 来源:发表于2018-03-25 17:59 被阅读35次

原帖地址：
https://zhangshurong.github.io/2018/03/25/%E5%8A%A8%E6%89%8B%E5%86%99%E4%B8%80%E4%B8%AA%E7%AE%80%E5%8D%95%E7%9A%84%E6%96%87%E4%BB%B6%E7%B3%BB%E7%BB%9F/
项目地址：https://github.com/ZhangShurong/HUST_OS_fs_experiment

title: 动手写一个简单的文件系统
date: 2018-03-25 16:53:50
categories: "Linux"
tags:

Linux
Kernel
FileSystem

总体设计

本文件系统的磁盘结构参考minix的文件系统实现。但是自举块（或称引导块）中没有数据。切不采用二级或者多级索引，其结构如下:

|Dummy Block|Super Block|IMap|BMap|Inode Table|Data blocks|

其中每个块的大小定义为4096bytes，每个Inode含有10个块所以单个文件最大为40KB，支持的最小磁盘大小为24K。以下详细阐述文件系统中所需要的三个基本数据结构。

1. 超级块结构：

struct HUST_fs_super_block {
    uint64_t version;
    uint64_t magic;
    uint64_t block_size;
    uint64_t inodes_count;
    uint64_t free_blocks;
    uint64_t blocks_count;
    uint64_t bmap_block;
    uint64_t imap_block;
    uint64_t inode_table_block;
    uint64_t data_block_number;
    char padding[4016];
};

超级块中的padding数组，是为了使超级块的大小为4096bytes，以简化后期的工作；“Magic”为1314522；indoe_count记录文件系统所支持的inode个数，这个值在格式化时就已经计算并写入超级块了。Bmap_block记录着bmap开始的数据块索引,imap_block，inode_table_block和data_block_number同理，记录索引是为了简化文件块的定位操作。

2. HUST_inode结构

struct HUST_inode {  
    mode_t mode; //sizeof(mode_t) is 4  
    uint64_t inode_no;  
    uint64_t blocks;  
    uint64_t block[HUST_N_BLOCKS];  
    union {  
        uint64_t file_size;  
        uint64_t dir_children_count;  
    };  
    int32_t i_uid;   
    int32_t i_gid;  
    int32_t i_nlink;  
    int64_t i_atime;  
    int64_t i_mtime;  
    int64_t i_ctime;  
    char padding[112];  
};

HUST_inode对应着磁盘上的inode结构，在后文会描述它是如何转换为VFS中的inode的。在上述结构体中，mode代表该inode是文件还是目录，blocks代表该inode的大小（所占块的数目），i_uid和i_gid用于后面的多用户管理。Padding数组是为了让HUST_inode结构体能够被4096整除；宏HUST_N_BLOCK被定义为10，意味着每个文件（目录）最大的大小为10个块；block数组存储着每个块的索引，用于定位文件。

3. 文件系统的目录结构

struct HUST_dir_record {  
    char filename[HUST_FILENAME_MAX_LEN];  
    uint64_t inode_no;  
};

文件记录是为了储存目录项，其中HUST_FILENAME_MAX_LEN定义为256也就是说，文件名最大长度256。
编写文件系统除了设计文件系统的磁盘结构，定义文件系统支持的操作也是十分重要的，这个直接影响了文件系统的功能。本文件系统支持基本的文件的增删改查，多用户等功能，但是不支持文件的移动，软硬链接等操作。

mkfs的实现

要使用这个文件系统，必须首先创建一个符合磁盘布局的映像文件，所以我们需要实现一个格式化程序，这个程序按照惯例叫做mkfs。本节详细描述mkfs的实现。
mkfs的作用是将一个文件改写成对应于我们文件系统的结构，其主要功能点为写入超级块，写入imap,bmap，写入inode table，以及创建一个根目录和测试文件。
超级块包含了文件系统的基本信息，其信息在上文中有详细描述。写入超级块信息，需要计算整个磁盘的大小，然后计算imap，bmap以及inode table的大小，这样才能确定各个区域在磁盘中的位置。这些工作都是在init_disk这个函数中完成的。基本逻辑为读取需要格式化的文件大小，计算出整个磁盘中的块的个数，简单的将块的个数与inode的个数等同起来；然后通过块数以及inode个数计算imap和bmap的大小。其中bmap的大小如下（imap大小计算公式与bmap一致）：
$$
bmapsize = blockcount/ HUST_BLOCKSIZE * 8
$$
关键代码如下：

static int init_disk(int fd, const char* path)  
{  
//获取基本信息  
//... ...  
    //计算bmap  
    bmap_size = super_block.blocks_count/(8*HUST_BLOCKSIZE);  
    super_block.bmap_block = RESERVE_BLOCKS;  
  
    if (super_block.blocks_count%(8*HUST_BLOCKSIZE) != 0) {  
        bmap_size += 1;  
    }  
    bmap = (uint8_t *)malloc(bmap_size*HUST_BLOCKSIZE);  
    memset(bmap,0,bmap_size*HUST_BLOCKSIZE);  
  
    //计算imap  
    imap_size = super_block.inodes_count/(8*HUST_BLOCKSIZE);  
    super_block.imap_block = super_block.bmap_block + bmap_size;  
 
    if(super_block.inodes_count%(8*HUST_BLOCKSIZE) != 0) {  
        imap_size += 1;  
    }  
    imap = (uint8_t *)malloc(imap_size*HUST_BLOCKSIZE);  
    memset(imap,0,imap_size*HUST_BLOCKSIZE);  
  
    //计算inode_table  
    inode_table_size = super_block.inodes_count/(HUST_BLOCKSIZE/HUST_INODE_SIZE);  
    super_block.inode_table_block = super_block.imap_block + imap_size;  
    super_block.data_block_number = RESERVE_BLOCKS + bmap_size + imap_size + inode_table_size;  
    super_block.free_blocks = super_block.blocks_count - super_block.data_block_number - 1;  

    //设置bmap以及imap  
//... ...  
}

其中，imap和bmap为uint8_t的全局数组。
计算完基本信息之后，我们需要将其写入文件并创建根目录和测试文件。文件创建的基本步骤如下：

检测（获取）磁盘（文件）大小，确认是否有足够的空间
找的空闲的inode和block，并标记imap和bmap。
生成相应的数据，并写入对应的块中。对于根目录来讲，写入的数据为三个目录项，目录项的内容为文件（目录）名以及对应的inode编号。第一个目录项为当前目录和对应的inode编号0，第二个目录项为上一级目录和对应的inode编号0，第三个目录项为欢迎文件，内容为文件名“file”和对应的inode编号1。
设置对应的inode信息，如是文件还是目录（mode信息），创建时间修改时间(i_ctime和i_mtime)，用户id和组id信息（i_uid和i_gid）等。
更新超级块信息。

在我们的文件系统写完之前，我们可以新建一个文件来测试我们的mkfs是否能正常运行，通过16进制编辑器来查看是否功能正常。具体步骤如下：

运行下列命令创建文件。

dd bs=4096 count=100 if=/dev/zero of=image

编译mkfs.c

 gcc mkfs.c -o mkfs

格式化image文件

./mkfs ./image

通过hexdumo来查看文件的结构，结果如下图。通过检查，我们发现，image文件结构写入正确无误。

文件系统的实现

一个通常意义上的文件系统驱动可以单独被编译成模块动态加载，也可以被直接编译到内核中，为了调试的方便，本文中的文件系统采用动态加载的方式实现。实现一个文件系统必须遵照内核的一些“规则”，以下我将以递进的顺序阐述文件系统的实现过程。

一、文件系统的加载与卸载

首先为了能够成功加载文件系统，文件系统需要提供文件系统的名字，超级块的加载和删除方法。这些东西反应在file_system,_type中。

struct file_system_type HUST_fs_type = {  
    .owner = THIS_MODULE,  
    .name = "HUST_fs",  
    .mount = HUST_fs_mount,  
    .kill_sb = HUST_fs_kill_superblock, /* unmount */  
};

文件系统作为一种块设备驱动，自然也需要实现module_init以及mocule_exit。代码如下：

/* Called when the module is loaded. */  
int HUST_fs_init(void)  
{  
    int ret;  
    ret = register_filesystem(&HUST_fs_type);  
    if (ret == 0)  
        printk(KERN_INFO "Sucessfully registered HUST_fs\n");  
    else  
        printk(KERN_ERR "Failed to register HUST_fs. Error: [%d]\n", ret);  
    return ret;  
}  
  
/* Called when the module is unloaded. */  
void HUST_fs_exit(void)  

    int ret;  
    ret = unregister_filesystem(&HUST_fs_type);  
    if (ret == 0)  
        printk(KERN_INFO "Sucessfully unregistered HUST_fs\n");  
    else  
        printk(KERN_ERR "Failed to unregister HUST_fs. Error: [%d]\n", ret);  
}  
module_init(HUST_fs_init);  
module_exit(HUST_fs_exit);  
  
MODULE_LICENSE("MIT");  
MODULE_AUTHOR("cv");

我们可以看到，设备驱动加载的时候，驱动向内核注册了文件系统，而驱动卸载的时候，文件系统的信息也被删除。文件系统加载时调用的函数为HUST_fs_mount，实际上，这个函数向内核注册了一个回调：

int HUST_fs_fill_super(struct super_block *sb, void *data, int silent)

这个函数是用来与VFS交互从而生成VFS超级块的。在HUST fs中，超级块在磁盘的第二个4096字节上，即块号为1。这个函数执行时会从磁盘中读取信息，填充到VFS提供的超级块结构体中，下列为部分关键代码。

int HUST_fs_fill_super(struct super_block *sb, void *data, int silent)  {  
    struct buffer_head *bh;  
    bh = sb_bread(sb, 1);  
    struct HUST_fs_super_block *sb_disk;  
    sb_disk = (struct HUST_fs_super_block *)bh->b_data;  
    struct inode *root_inode;  
    if (sb_disk->block_size != 4096) {  
        printk(KERN_ERR "HUST_fs expects a blocksize of %d\n", 4096);  
        ret = -EFAULT;  
        goto release;  
   }  
   //fill vfs super block  
    sb->s_magic = sb_disk->magic;  
    sb->s_fs_info = sb_disk;  
    sb->s_maxbytes = HUST_BLOCKSIZE * HUST_N_BLOCKS; /* Max file size */  
    sb->s_op = &HUST_fs_super_ops;  
}

从上述代码可以看出，我们用sb_read来读取磁盘上的内容，然后填充super_block结构体。值得注意的是，有关超级块的操作函数即superblock_operations也是在此处赋值的。由于super_block* sb在文件系统卸载之前是一直存在于内存中的，所以我们可以使用s_fs_info来存储原始的超级块信息，避免后期交互时再次读取磁盘。
文件系统卸载的时候超级块信息需要被删除，所以HUST_fs_kill_superblock的作用时释放该超级块，通知VFS该挂载点已经卸载。
实现基本函数后，可以对文件系统进行挂载操作，挂载操作的脚本内容如下：

sudo umount ./test  
sudo rmmod HUST_fs  
dd bs=4096 count=100 if=/dev/zero of=image  
./mkfs image  
insmod HUST_fs.ko  
mount -o loop -t HUST_fs image ./test  
dmesg

上述脚本，将项目下的test文件夹作为文件系统的挂载点，并在挂载之后答应出了内核调试目录。成功执行该脚本的截图如下：

我们可以看到test目录已经挂载成功而且内核调试信息显示文件系统挂载成功。

二、 ls命令的实现

加载文件系统之后第一个要实现的功能是读取文件系统中的数据，所以选择实现文件夹读取操作，这一操作在2.x内核中是.readdir函数指针，在最新版本中是,.iterate函数指针。这个指针在保存在file_operation中，如下所示。

const struct file_operations HUST_fs_dir_ops = {  
    .owner = THIS_MODULE,  
    .iterate = HUST_fs_iterate,  
};

HUST_fs_iterate函数主要功能逻辑是读取inode的块数据，并且将块数据中的inode和文件名通过dir_emit函数传输到VFS层。以根目录为例，根目录的包含三个数据项，分别是父目录，当前目录和欢迎文件，所以该函数会执行以下三个语句

//参数分别表示上下文，文件/目录名，文件/目录名长度，inode号，文件类型  
dir_emit(ctx, ".", 1,0, DT_DIR);  
dir_emit(ctx, "..", 2,0, DT_DIR);  
dir_emit(ctx, "file", 4,1, DT_REG);

完成该函数后，在填充根目录inode时将HUST_fs_dir_ops指针赋值，即可在挂在文件系统后执行ls命令。

如上图所示，我们成功看到了欢迎文件。但是此时我们不能对文件进行任何操作，因为还没有实现其他的接口。

三、磁盘管理相关逻辑的实现

这个磁盘管理的内涵包括向磁盘写入和从磁盘取出读取inode，更新inode信息，维护imap，bmap，inode table等操作。为了使磁盘上的内容有序的组合起来，磁盘空间的管理十分的重要，后续的文件读写操作都与此相关。
写入和删除inode的操作存放在super_operations这个结构体中。

const struct super_operations HUST_fs_super_ops = {  
    .evict_inode = HUST_evict_inode,  
    .write_inode = HUST_write_inode,  
};

HUST_fs_super_ops需要在填充超级块时赋值到super_block的s_ops字段中。HUST_write_inode函数的功能是将内存中的inode保存在磁盘上。关键代码如下。

int HUST_write_inode(struct inode *inode, struct writeback_control *wbc)  
{  
    struct buffer_head * bh;  
    struct HUST_inode * raw_inode = NULL;  
    HUST_fs_get_inode(inode->i_sb, inode->i_ino, raw_inode);  
    if (!raw_inode)  
        return -EFAULT;  
    raw_inode->mode = inode->i_mode;  
    raw_inode->i_uid = fs_high2lowuid(i_uid_read(inode));  
    raw_inode->i_gid = fs_high2lowgid(i_gid_read(inode));  
    raw_inode->i_nlink = inode->i_nlink;  
    raw_inode->file_size = inode->i_size;      
    raw_inode->i_atime = (inode->i_atime.tv_sec);  
    raw_inode->i_mtime = (inode->i_mtime.tv_sec);  
    raw_inode->i_ctime = (inode->i_ctime.tv_sec);  
    mark_buffer_dirty(bh);  
    brelse(bh);  
    return 0;  
}

可以看到，该函数的将vfs inode中的相关信息存储到HUST_inode结构体中，然后写入磁盘。这个是单独的写入磁盘操作，事实上，当我们申请inode时，imap也是需要检查刷新的，需要把相应位置标记为1。同理，evict_inode函数的作用时删除inode，删除成功后，我们需要刷新imap的值，把相应位置标记为0。
设置和写入map的操作都在map.c中，以下以imap为例。对于imap来讲，申请inode的时候需要检查第一个空闲的inode编号，当inode被释放的时候也要及时清零对应的imap。与此相关的函数如下。

//从磁盘中读取数据并存在imap数组中  
int get_imap(struct super_block* sb, uint8_t* imap, ssize_t imap_size);  
//在vaddr数组中找到第一个为0的bit，这个函数用于定位空inode或者block  
int HUST_find_first_zero_bit(const void *vaddr, unsigned size);  
//将imap的某一位置0或者1，并保存在磁盘上  
int set_and_save_imap(struct super_block* sb, uint64_t inode_num, uint8_t value);  
//定义的位操作宏如下  
#define setbit(number,x) number |= 1UL << x  
#define clearbit(number, x) number &= ~(1UL << x)

由于本文件系统并不是为了实际使用，所以上述的操作都没有考虑性能以及准确性问题。事实上，能够加上校验或者冗余备份是最好的。

四、读写文件内容

为了能够快速看到文件系统在正常工作，所以接下来需要实现文件的读写操作。文件读写操作按照一般处理，应该是实现在struct file_operations这个结构体中的。事实上，最开始我是实现在这个结构体中的read_iter函数指针中的。但是比较有趣的一点是，如果我们实现了struct address_space_operations结构体中的函数，那么struct file_operations结构体中的函数则可以交由VFS实现。代码如下：

const struct file_operations HUST_fs_file_ops = {  
    .owner = THIS_MODULE,  
    .llseek = generic_file_llseek,  
    .mmap = generic_file_mmap,  
    .fsync = generic_file_fsync,  
    .read_iter = generic_file_read_iter,  
    .write_iter = generic_file_write_iter,  
};  
const struct   address_space_operations HUST_fs_aops = {  
    .readpage = HUST_fs_readpage,  
    .writepage = HUST_fs_writepage,  
    .write_begin = HUST_fs_write_begin,  
    .write_end = generic_write_end,  
};

上述的generic开头的函数是不需要我们手动实现的。上述的address_space_operations操作其实是实现了页高速缓存的一些操作。页高速缓存是linux内核实现的一种主要磁盘缓存，它主要用来减少对磁盘的IO操作，具体地讲，是通过把磁盘中的数据缓存到物理内存中，把对磁盘的访问变为对物理内存的访问。这些接口一旦实现，那么对文件的操作就可以转移到内存中，这就是为什么可以使用generic开头的这些函数来代替手写。
HUST_fs_readpage, HUST_fs_writepage以及HUST_fs_write_begin都被注册回调到同一个函数HUST_fs_get_block。HUST_fs_get_block主要返回内核请求长度的数据。至于读写操作，内核调用__bwrite函数最终调用块设备驱动执行。因为在我没有采用二级或者多级索引，故而HUST_fs_get_block函数逻辑比较简单，部分代码如下：

int HUST_fs_get_block(struct inode *inode, sector_t block,  
              struct buffer_head *bh, int create)  
{  
    struct super_block *sb = inode->i_sb;  
    if (block > HUST_N_BLOCKS) 
        return -ENOSPC;  
    struct HUST_inode H_inode;  
    if (-1 == HUST_fs_get_inode(sb, inode->i_ino, &H_inode))  
        return -EFAULT;  
    if (H_inode.blocks == 0)  
        if(alloc_block_for_inode(sb, &H_inode, 1)) 
            return -EFAULT;  
    map_bh(bh, sb, H_inode.block[block]);  
    return 0;  
}

如上所示，该函数判断传入的block的大小，并将磁盘内容映射到bh中。后续的读写操作将有VFS帮我们完成。

五、inode操作

Inode操作涉及文件(夹)的创建删除，将HUST_inode映射到VFS中的inode等操作。具体实现的函数如下。

const struct inode_operations HUST_fs_inode_ops = {  
    .lookup = HUST_fs_lookup,  
    .mkdir = HUST_fs_mkdir,  
    .create = HUST_fs_create,  
    .unlink = HUST_fs_unlink,  
};

HUST_fs_lookup是其中比较复杂的一个函数，它负责将一个目录下的inode信息交由VFS管理。首先，HUST_fs_lookup读取文件夹的内容，然后遍历文件夹下面的HUST_inode，找到我们想要的HUST_inode，根据不同的文件属性，申请vfs_inode；并对不同的vfs_inode设置不同的操作。假设vfs_inode对应的是一个文件，那么就设置vfs_inode->mapping->a_ops，如果vfs_inode对应的是文件夹，那么就设置vfs_inode->f_ops = &HUST_fs_dir_ops;最后将vfs_inode注册到VFS中。这部分的关键代码如下：

struct dentry *HUST_fs_lookup(struct inode *parent_inode,  
                  struct dentry *child_dentry, unsigned int flags)  
{  
    struct super_block *sb = parent_inode->i_sb;  
    struct HUST_inode H_inode;  
//省略代码  
    for (i = 0; i < H_inode.dir_children_count; i++) {  
        if (strncmp  
            (child_dentry->d_name.name, dtptr[i].filename,  
             HUST_FILENAME_MAX_LEN) == 0){  
            inode = iget_locked(sb, dtptr[i].inode_no);  
            if (inode->i_state & I_NEW) {  
                inode_init_owner(inode, parent_inode, 0);  
                struct HUST_inode H_child_inode;  
                if (-1 == HUST_fs_get_inode(sb, dtptr[i].inode_no, &H_child_inode))  
                    return ERR_PTR(-EFAULT);  
                HUST_fs_convert_inode(&H_child_inode, inode);  
                inode->i_op = &HUST_fs_inode_ops;  
                if (S_ISDIR(H_child_inode.mode)) {  
                    inode->i_fop = &HUST_fs_dir_ops;  
                } else if (S_ISREG(H_child_inode.mode)) {  
                    inode->i_fop = &HUST_fs_file_ops;;  
                    inode->i_mapping->a_ops = &HUST_fs_aops;  
                }  
                inode->i_mode = H_child_inode.mode;  
                inode->i_size = H_child_inode.file_size;  
                insert_inode_hash(inode);  
                unlock_new_inode(inode);  
            }  
        }  
    }  
//省略代码  
}

只有在这里注册了相关函数，系统调用才能正常执行。不然就会出现不支持的操作这种报错信息。
.create与.mkdir都是对应了inode的创建，只是inode的属性不能而已。.create创建普通文件而.mkdir创建文件夹。所以这两个函数的功能被函数HUST_fs_create_obj所处理。这个函数接受新建文件（夹）的请求，检查磁盘的大小，检查是否有空余的indoe，并且分配inode号，然后更新imap信息，最后更新超级块信息。由于该函数逻辑简单但是代码量比较大，故而不在此展示其具体实现。
在完成上述工作之后，我们的文件系统基本已经完成了，这个系统采用线性（区别于minixi二级索引用树来管理）的方式管理磁盘空间，支持基本的增删改查文件操作，支持文件权限，支持多用户。

动手写一个简单的文件系统.md

总体设计

1. 超级块结构：

2. HUST_inode结构

3. 文件系统的目录结构

mkfs的实现

文件系统的实现

一、文件系统的加载与卸载

二、 ls命令的实现

三、磁盘管理相关逻辑的实现

四、读写文件内容

五、inode操作

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

Kernel

Linux

我用 Linux

Linux kernel

动手写一个简单的文件系统.md

总体设计

1. 超级块结构：

2. HUST_inode结构

3. 文件系统的目录结构

mkfs的实现

文件系统的实现

一、 文件系统的加载与卸载

二、 ls命令的实现

三、 磁盘管理相关逻辑的实现

四、读写文件内容

五、inode操作

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

Kernel

Linux

我用 Linux

Linux kernel

一、文件系统的加载与卸载

三、磁盘管理相关逻辑的实现