Table of Contents
rCore ch6 是在将如何实现一个简易的文件系统，事实上文件系统的 PR 已经和进去很久了，但是最近面临学校中期、实习答辩等问题，所以一直没有时间把文章整理出来，中间有很多感悟都有点忘了，在写的过程中努力回想，慢慢修改吧。
什么是文件系统
块设备是一种非易失性的存储设备，这是作为持久化存储设备最基本的特征。块设备内部按照块划分，能够按照地址定位块（随机读写能力），比如我们常用的硬盘的一个块就是 4kb。
文件系统的使命是让数据能够持久化保存在外部块设备上（写能力），同时能够将数据从块设备上取出（读能力）。
我们在使用操作系统的时候，我们很自然的使用文件、文件夹等来组织数据，在块设备中也需要存储对应的数据结构，如何组织、存储这些结构这是文件系统要做的事情之一，比如耳熟能详的超级快（super block）、inode 等数据结构，都是在做这类事情。
在 CPU 视角中块设备速度太慢了，设置一个内存缓存层能够有效的缓解速度不对等的问题，所以文件系统需要考虑什么时候把块设备的数据加载到内存中，缓存在什么时候被写回到块设备等等。
文件系统还需要暴露给 OS 可调用的接口，为 open、read、write 等系统调用提供支持。
Easyfs 实现细节
在 rCore 将文件系统拆解为五层，分别是块设备接口层、磁盘的布局 & 数据结构、块缓存层、块管理层以及索引节点（inode），最顶层是通过暴露系统调用的方式向用户提供服务。
块设备接口层
块设备层是一个接口（trait），主要是为了适配不同的 block device，定义了 read_block 和 write_block 两个核心的方法，read_block 方法是根据 block_id（一种地址）读取一个或几个数据块，write_block 顾名思义就是以 block_id 为开始写入一个或几个数据块。
任何一种块设备只要实现了这两种接口都能被用于这个文件系统，在测试的时候我们使用一个文件模拟块设备，只要为文件实现上面的接口就可以了。
磁盘的布局 & 数据结构
第二层是磁盘的布局 & 数据结构，严格意义上来说他们不是一层，不为上层提供任何功能，但是他们的定义方式影响了块设备上组织数据的方式。
磁盘布局是指在磁盘上划分区域的方案。一块硬盘可以简单的理解为一个大数组，呈现给用户的时候是有层级的目录结构，所以需要规划在不同的区域存放索引、层级结构关系、数据等。
在上图中我们可以看出，磁盘的布局被划分为 superblock、inode 和 data 三种结构，superblock 的作用是对整体磁盘结构进行定位以及校验，inode 则是对 data 存储的数据建立索引，而 data 则是存放的真正的二进制数据。
Superblock 的定义如下所示。magic 字段存放一个随机字符串，用于校验文件系统是否是 easyfs，剩下的字段都是表示上图的各个部分所占用的空间。Superblock 主要负责在加载的时候告知操作系统当前文件系统的整体布局。
Bitmap 是用于记录磁盘 block 状态的一种数据结构。假设目前有 8 blocks，那么对应的 bitmap 的长度为 8 bits。假设在 8 blocks 都为空，则 bitmap 的值为 0x00，如果第三个 block 被占用（block 从 1 开始），那么 bitmap 的值为 1<<3 = 0x04。Inode bitmap 就是为了记录磁盘 blocks 中的 inode 空闲状态，同理 data bitmap 记录了磁盘 blocks 中的数据空闲状态。Bitmap 的应用场景是在申请新的 inode 和 data 的时候，能够让文件系统知道哪个 block 已经被别人用了，哪个 block 还是空闲的。
Inode 在磁盘上和内存中有多种定义，从名字中能分辨出来，DiskInode 是存储在硬盘中的。在 easyfs 中假定 block 的大小为 512B，DiskInode 占用空间为 128B，所以一个 block 最多可以存放 4 个 DiskInode。
DiskInode 的作用是索引数据块（aka data area）Size 字段表示当前 DiskInode 指向的数据的长度。Type_ 表明当前 DiskInode 的类型，决定了最终的数据类型，如果是文件（File）那么数据类型就是二进制，由应用程序决定如何处理。如果是文件夹（Directory）则存放的是当前文件夹中的目录项（可能是文件，也可能是文件夹）。稍后会介绍目录项的数据结构。
磁盘的 inode 多级结构与内存的页表结构有异曲同工之妙，本质上都在追求大寻址空间的同时避免占用大量空间，也就是用时间换空间。
DiskInode 结构存储在 inode area，间接索引结构和数据都存储在 data area。Direct 是直接索引，文件系统可以直接访问数据块。直接索引的数据块的数量（INODE_DIRECT_COUNT）是 28 个，是因为在设计上一个 DiskInode 占用的空间是 128B（一个数据块可以存 4 个 DiskInode），其他的字段已经占用了 32B（4 *4B）的空间，剩余的 28 个 4B 空间作为直接索引。间接索引在结构上是非常相似的，他们都是递归地链接下一个数据块，直到数据块中存放的是数据。Easyfs 实现了最高二级间接索引结构，数据的最大尺寸为 (28 + 128 + 128 * 128) * 512B（约为 8M）。
数据在保存的时候先占用直接索引的数据块，占满后则从 data area 申请一个间接索引数据块，再来的数据填充一级间接索引直至填满，最后以上面的方案再填充二级间接索引。
（我的想法不一定对）8M 的索引空间有点小，那么应该怎么拓展呢？最简单的方法是增加三级索引、四级索引等，但是每增加一级索引，意味着找到最终的数据需要多访问一次磁盘，速度是会收到影响的，第二个可能的方案是充分利用连续存储空间，让最终的索引数据长度不局限在 512B，当然也要结合磁盘的存储状况。
在上面我们提到了 type_ 是控制 DiskInode 的类型的，在 easyfs 中只有 /（根目录）一个文件夹，所以默认索引指向的内容，要么是文件元数据，要么是文件数据。
DirEnty 数据结构存储的是文件元数据，如上所示。DirEntry 的长度为 32B，一个数据块可以存 16 个 DirEntries。名字的最后一个字符是 \0，所以 name 只能存 27 个有效字符。Inode_number 是指向当前文件的 DiskInode，从根文件夹到某个文件的数据的查询全链路（都使用二级间接缓存的情况）如下图所示。
块缓存层
块缓存层是将数据块从磁盘加载到内存中，CPU 操作磁盘都是操作内存，在缓存失效/被替换的时候写回到磁盘中。这一层做的事情比较直观，就不再赘述了。
磁盘块管理器
磁盘块管理器处于内存中，它的作用有机的结合和使用上述的数据结构管理磁盘。具体表现在（1）在初始化阶段能根据要求划分磁盘布局并记录到 SuperBlock，以后打开文件系统的时候能读取 SuperBlock 确认布局。（2）能够操作 bitmap 申请/销毁 inode 和 data blocks。
索引节点
索引节点处于内存中。磁盘块管理器的作用式组织磁盘结构，更多是从磁盘的角度出发的。但是我们在使用或者操作系统在使用文件的时候，我们不会考虑 inode 是什么、磁盘布局是什么。一个明显的例子：尽管一个文件的所有数据块在物理上是分散的，而用户一般把文件看作是一个连续的二进制（逻辑上的）。那么这一层做的事情就显而易见了：向上层屏蔽物理视角，提供喜闻乐见的逻辑视角。
在这一层中出现了全新的、不带 Disk 的 Inode 数据结构，如下所示。
Block_id 和 block_offset 共同定位了一个具体的 DiskInode，之前我们提到过一个数据块可以存 4 个 DiskInode，block_id 定位数据块，block_offset 则确定数据块内偏移量，理论上一个 DiskInode 就能获取全部的数据（结合上面 DiskInode 到实际数据的链路图），这是实现物理到逻辑转换的基础。Fs 是磁盘块管理器的引用，block_device 是块设备的引用。
针对不同 Inode 类别，提供的功能也有所区别：
通用
- read_disk_inode: 读取 DiskInode。
- modify_disk_inode: 修改 DiskInode。
根目录
- find: 传入一个文件名，查找对应的 Inode。
- ls: 遍历目录中的全部目录项，返回目录项名字的数组。
- create: 传入一个文件名，在当前目录创建一个文件，返回新创建的文件的 Inode。
文件
- clear: 清除文件的全部数据。
- read_at: 传入一个偏移量（逻辑上的），从该位置读取一定长度的数据到缓冲区中。
- write_at: 传入一个偏移量（逻辑上的），将缓冲区的数据写入到该位置中。
Easyfs 接入 OS
在这一章中我们不再关注 Inode 的具体实现，主要关注 OS 层中是如何整合 easyfs 的，以及 OS 中的特有的性能，比如文件描述符（file descriptor, fd）、文件描述表等。除此之外，在原有的 rCore 教程中还有对 QEMU、virtio、MMIO 等有简略的介绍，这些内容在第九章的时候会详细介绍，所以就不在这一章中赘述了。
File trait 是对文件的抽象，其定义如下所示。在 UNIX 和 Linux 都遵循“一切皆文件”的准则，这里对文件实际上是一层极高的抽象，比如外设、socket 等等都可以被归类为文件，因为都具备读和写这个最基本的抽象。当然在 rCore 没有那么复杂的实现，不需要实现这么复杂的情况。
在 rCore os crate 内部又进一步封装 Inode 为 OSInode，为 OSInode 实现了 File trait，这就因为着操作系统可以直接读或者写当前 Inode 对应的数据，也为标准输入（Stdin）和标准输出（Stdout）都实现了 File trait。
进程的 TCB（Task Control Block）新增了一个名叫 fd_table 的字段，如下所示。这个字段中文名就是文件描述表，虽然名字是表，但是它就是一个可变数组，维护一个进程已打开的文件。
为什么要维护在进程内维护 fd_table 呢？文件的读写是有连续性的，比如文件写入位置是依赖于上一次的写入位置的。换句话说，如果没有这个表，那么每次写入都要重新打开这个文件，重新定位偏移量，所以维护这个结构是非常有必要的。
文件描述符就是 fd_table 的索引，对应着一个已经打开的文件。