写一个简单的用户态文件系统

1. 介绍

本项目是仿照Linux下的ext4文件系统所编写的一个十分简单的用户态文件系统。本系统用标准的C99编写，在Linux下编译运行通过。本系统做了如下的工作：

1. 利用普通文件来模拟磁盘，文件系统对磁盘的所有操作均会映射到该文件(下文均简称磁盘文件)上；
2. 磁盘文件可以随时持久化到本地以及从磁盘加载到内存；
3. 本文件系统模拟了ext文件系统的超级块，I-node节点表，数据块的bitmap以及数据块表四个部分，所有上层操作都是对这四个部分进行读写；
4. 本文件系统支持磁盘的创建、格式化、以及文件的创建、写内容和读内容。

下一节介绍了本文件系统的概要以及详细设计。

2. 概要设计

本文件系统采用分层设计的原则，从底至顶一共分为下面四个层级:

1. 磁盘布局层。该层提供了对I-node和数据块的创建和销毁的功能以及对超级块的读写功能；
2. I-node节点层。该层封装了对i-node的各种操作，包括修改和维护i-node的索引节点以及各种元数据维护。除此之外，该层还提供了对I-node索引的数据块进行数据读写的功能；
3. 调用接口层。该层向上层提供了创建文件，向文件写入内容和读写内容，以及查看当前目录中文件列表的接口；
4. 应用层。该层为用户提供了操作磁盘的交互式终端。

下图展示了本文件系统的基本架构:

3. 详细设计

3.1 磁盘布局

本文设计的磁盘布局如下图所示:

​ 其中超级块(super block)记录了磁盘的元数据，包括每个i-node的大小、i-node的数量、空闲的i-node的数量、每个数据块元数据的大小、每个数据块的大小、磁盘大小等信息。在本系统中，数据块大小固定为1024B。

​ 在初始化一个磁盘时，系统会根据磁盘大小来计算i-node以及数据块的数量，遵循的原则是令i-node占据整个磁盘约1%的空间。为确保不存在碎片空间，系统在实际创建的磁盘时会对磁盘大小做微调。因此创建的磁盘实际大小与用户出入有细微出入。除此之外，每个i-node以及数据块会被分配一个唯一的id以便在需要时进行索引。

3.2 I-node读写

本系统中i-node的结构如下图所示:

I-node包含了文件的各种元数据以及数据块的位置，其中元数据包括i-node节点号，是否被占用，文件模式(类型，权限信息)，用户id，用户组id,修改时间以及链接个数等信息。对于数据块索引，本系统采用直接索引，一级索引和二级索引这三种方式来记录数据块的位置，其中直接索引一共有12个，后面两种间接索引各有一个。一个i-node节点号是8Byte的无符号整数，因此一个1024B的数据块可以存储1024/8=128个块索引，由此可得本文件系统支持的最大文件大小为(128*128+128 + 12) *1024 = 16.137MB。

与此同时，i-node还维护了一个索引指针，用来指向最后一个指向数据块的索引，以便对数据块的内容进行读写。索引指针就是数据块的块号，磁盘根据块号来读写数据块。

在初始化磁盘的时候，系统会默认将0号i-node作为根目录”/“的节点号,并为其分配一个数据块用于存储”..”和”.”这两个目录表项。由于本系统暂不支持多级目录，因此每创建一个文件都会在0号i-node的数据块上增加一个文件表项目。每个文件表项记录了文件的名字以及其对应的i-node节点号，其大小为128B,其中文件名占据120B，而I-node节点号占据8B。

3.3 调用接口

调用接口层提供了创建文件，读写文件内容的接口。创建文件主要分为两个步骤：

1. 申请分配一个空闲的的i-node，向该i-node中写入包括文件类型在内的各种元数据；
2. 将文件名和申请得到的i-node节点号构成的文件表项写入0号i-node的数据块中.

而对于写文件，系统首先获取该文件所对应的i-node最后一个数据块的指针，然后向其中追加内容，如果数据块被写完就为该i-node分配一个新的数据块，并更新i-node相关数据即可。而对于读文件，原理相似：首先从inode中获取第一个数据块的指针，然后依次遍历属于该i-node的所有数据块，读取内容并存到buffer即可。

3.4 Shell

为方便使用，本系统基于上述接口开发了一个简单的shell，并支持如下命令:

1. init [num]: 创建一个大小为numKB的磁盘并进行格式化
2. ls列出根目录下的所有文件以及其元数据信息
3. touch [file]创建一个空文件
4. cat [file]根据文件名读取该文件的内容并输出到终端
5. write [file]将从终端标准输入流读取的数据写入文件
6. save [disk]将磁盘文件保存到本地
7. load [disk]加载本地磁盘的文件
8. info 获取磁盘的详细信息，包括每个已经分配的i-node和数据块的内容以及超级块的信息等。

详细的数据结构见附录。

4. 总结和展望

本系统实现了磁盘布局，文件的创建和读写等功能，完成了要求的任务。但是仍有很大的提升空间，如增加多级目录等功能。

5. 附录

下面展示了各个对象的数据结构:

/**
 *超级块
 */
struct super_block_t {
    uint32_t magic_number; //魔数
    uint16_t size_of_sb;  //超级块的大小
    uint16_t size_of_inode; //inode大小
    uint16_t size_of_bi; //数据块元数据大小
    uint16_t size_of_block; //数据块大小

    uint32_t total_i_cnt; //inode数量
    uint32_t total_b_cnt; //数据块数量
    uint32_t free_i_cnt; //空闲的inode数量
    uint32_t free_b_cnt; //空闲的数据块数量
    uint32_t disk_size;  //磁盘大小
};
/**
 * 数据块元数据
 */
struct block_info_t {
    bool occupied; //是否被占用
    uint16_t space_used; //已被写入的数据长度
    uint32_t number; //块号
    uint32_t inode_number; //被索引的inode号
};

/*
 * 数据块
 */
struct data_block_t {
    struct block_info_t info; //元数据
    byte_t data[DATA_BLOCK_SIZE]; //实际数据
};

/*
 *文件表项
 */
struct dir_entry_t {
    char dir_name[124]; //文件名字
    uint32_t inode_number; //inode节点号
};
/*
 *文件类型
 */
enum FILETYPE {
    None = '?',
    Normal = '-',
    Dir = 'd',
    Charctor = 'c',
    Block = 'b',
    Socket = 's',
    Pipe = 'p',
    Link = 'l'
};
/*
 *文件模式
 */
struct file_mode_t {
    enum FILETYPE file_type; //文件类型
    byte_t up: 3; //用户权限
    byte_t gp: 3; //组权限
    byte_t ap: 3; //其他人的权限
};
/*
 *inode数据结构
 */
struct inode_t {
    bool occupied; //是否被占用
    uint32_t number; //节点号
    uint32_t file_size; //文件大小
    struct file_mode_t mode; //文件模式
    int8_t uid; //用户id
    int8_t gid; //组id
    time_t c_time; //创建时间
    time_t m_time; //修改时间
    time_t a_time; //访问时间
    uint8_t links; //链接数
    inode_pointer_t direct[INODE_DIRECT_NUM]; //直接索引
    uint32_t block_used; //引用的数据块数量
    uint16_t cnt_file_num; //(当前目录下的文件数量，仅目录类型有效)
    inode_pointer_t singly; //一级索引
    inode_pointer_t doubly; //二级索引
};
/*
 *磁盘数据结构(和本地存储的二进制结构不一样)
 */
struct disk_t {
    super_block_t sb; //超级块
    inode_t *inode_list; //inod节点表
    data_block_t *data_block_list; //数据块表(包括元数据和实际内容)
};