easyfs 简易文件系统

文件系统

常规文件和目录实际都是保存在持久存储设备中的。持久存储设备仅支持以扇区为单位的随即读写，这和我们通常认识的通过路径即可索引到文件进行操作的用户视角有很大的不同。负责两者转换的便是 文件系统 。

文件系统负责将逻辑上的目录树结构映射到持久存储器上，决定设备上的每个扇区各应存储哪些内容；同时，文件系统页可以从持久存储设备还原出逻辑上的目录树结构。

虚拟文件系统 VFS

一个计算机系统中存在多个持久存储设备，每个存储设备上面的数据可以以不同文件系统格式存储的；所以为了能够向用户提供统一的界面和对这些设备进行统一的管理，内核中增加了一层 虚拟文件系统 VFS 。

虚拟文件系统规定了逻辑上的目录结构的通用格式以及相关操作的抽象接口。不同的底层文件系统均实现虚拟文件系统要求的那些抽象接口，并挂在到系统中，就可以实现对这些持久存储设备上的不同文件系统的统一管理。

简易文件系统 easyfs

该文件系统只是为了完整展示文件系统的工作原理。

• 扁平化：仅存在一个目录 /。在索引一个文件时，直接使用文件名而不关心其路径；
• 权限控制：全程只有单用户，不区分用户和用户组概念。
• 不记录文件访问/修改的时间辍。

磁盘的布局体现在磁盘上各个扇区的内容上，而解析磁盘布局得到的逻辑目录树结构则是通过内存上的数据结构来访问的——这表示文件系统涉及到同时对磁盘和对内存的访问：

• 对内存直接通过一条指令即可直接读写内存相应的位置；
• 操作磁盘则需要使用软件的方式向磁盘发出请求来间接进行对写；

我们需要特别注意哪些数据结构是存放在磁盘上的，哪些时存储在内存中的——这样才不会引起还乱。

easyfs 本身划分为不同的层次，形成层次花模块设计构架：

• 磁盘块设备接口层：定义了以块大小为单位对磁盘块设备进行对写的 trait 接口
• 块缓存层：在内存中缓存磁盘块的数据，避免频繁读写磁盘；
• 磁盘数据结构层：磁盘上的超级块、位图、索引节点、数据块、目录项等核心数据结构和相关处理；
• 磁盘块管理器层：合并了上述核心数据结构和磁盘布局所形成的磁盘文件系统数据结构，以及创建/打开文件系统相关处理和磁盘块的分配和回收处理；
• 索引点层：管理索引节点（文件控制块）数据结构，并实现文件创建/打开/读写等成员函数来支持文件操作相关的系统调用的处理；

块设备接口层

在 easyfs 最底层声明了一个块设备的抽象接口 BlockDevice :

pub trait BlockDevice: Send + Sync + Any {fn read_block(&self, block_id: usize, buf: &mut [u8]);fn write_block(&self, block_id: usize, buf: &mut [u8]);
}

它实现了两个抽象方法：

• read_block 可以将编号为 block_id 的块从磁盘读入内存中的缓冲区 buf ;
• write_block 可以将内存中的缓冲区 buf 中的数据写入磁盘编号为 block_id 的块；

因为块设备仅支持以块为单位进行随即读写，这两个抽象方法向上提供了统一的接口方法；但具体实现需要由块设备驱动实现。

easyfs 的块缓存层会调用这两个方法进行块缓存的管理。

Tips:

块与扇区

扇区（Sector）是块设备随即读写的大小单位，通常扇区为 512 字节。

块（Block） 是文件系统存储文件时的大小单位，每个块的大小等同于一个或多个扇区。

在 easyfs 中块大小和扇区同为 512 字节。

块缓存层

由于操作系统频繁读写磁盘会极大降低性能，因此先通过 read_block 将一个块上的数据从磁盘督导内存缓冲区中，这个缓冲区中的内容是可以直接读写的。如果对于缓冲区中的内容进行了修改，那么后续还需要通过 write_block 将缓冲区中的内容写回到磁盘块中。

从性能上考虑，要尽可能降低实际块读写（ read/write_block ）的次数，因为每一次调用都会产生大量的开销。要做到这一点，关键在于对块进行读写合并操作。

统一管理块缓冲区：

• 当要读写一个块的时候，首先区全局管理器中查看这个块是否已经被缓存到内存中；
• 在一段连续时间内对于一个块进行的所有操作均是在同一个固定的缓冲区中进行的，从而解决同步性问题；
• 全局管理器会尽可能将更多的块操作合并起来，并在必要的时机发起真正的块读写；

pub const BLOCK_SZ: usize = 512;
pub struct BlockCache{cache: [u8; BLOCK_SZ],block_id: usize,block_device: Arc<dyn BlockDevice>,modified: bool,
}

cache 是一个 512 字节的数组，表示位于内存中的缓冲区 —— 对应于一个磁盘块的大小；

block_id 记录了这个块缓存来自于磁盘中的块的编号；

block_device 保留一个底层块设备的引用时的可以和它打交道；

modified 记录自从这个块缓存从磁盘在如内存之后，它是否被修改过；

每个 BlockCache 保存一个扇区的数据。

磁盘数据结构层

磁盘上的超级块、位图、索引节点、数据块、目录项等核心数据结构和相关处理

磁盘块管理器层

合并了上述核心数据结构和磁盘布局所形成的磁盘文件系统数据结构，以及创建/打开文件系统的相关处理和磁盘块的分配和回收处理

索引点层

管理索引节点（即文件控制块）数据结构，并实现文件创建/文件打开/文件读写等成员函数来向上支持文件操作相关的系统调用的处理

磁盘布局

如何将一个逻辑上的文件目录树结构映射到磁盘上，决定磁盘上的每个块应该存储文件相关的哪些数据。为了更容易进行管理和更新，将磁盘上的数据组织位若干种不同的磁盘上数据结构，并合理安排它们在磁盘中的位置。

easyfs的磁盘布局：

超级块

#[repr(c)]
pub struct SuperBlock{magic: u32,pub total_blocks: u32,pub inode_bitmap_blocks: u32,pub inode_area_blocks: u32,pub data_bitmap_blocks: u32,pub data_area_blocks: u32,
}

​ magic 用于验证文件系统合法性的魔数；

​ total_block 文件系统管理的总块数， 不一定等于磁盘的总块数；

​ inode_bitmap_blocks 索引块位图区域的长度——索引块位图区用于表示索引块的分配情况；

​ inode_area_blocks 索引块区域——该区域被索引位图块管理；

​ data_bitmap_blocks 数据块位图区域的长度——数据块位图区用于表示数据块的分配情况；

​ data_area_blocks 数据块区域——该区域被数据块位图管理；

​ 超级块是文件系统使用的数据，表示文件系统在磁盘上的布局情况。

• 索引节点位图区域：索引位图的实际保存区域；
• 索引节点区域：索引节点的实际保存区域；
• 数据块位图区域：数据块位图的实际保存区域；
• 数据块区域：数据块的实际保存区域；

通过超级块可以得到文件系统的整体情况：

easyfs 文件系统结构

pub struct EasyFileSystem{pub block_device: Arc<dyn BlockDevice>,pub inode_bitmap: Bitmap,pub data_bitmap: Bitmap,inode_area_start_block: u32,data_area_start_block: u32,
}

impl EasyFileSystem {/// Open a block device as a filesystempub fn open(block_device: Arc<dyn BlockDevice>) -> Arc<Mutex<Self>> {// read SuperBlockget_block_cache(0, Arc::clone(&block_device)).lock().read(0, |super_block: &SuperBlock| {assert!(super_block.is_valid(), "Error loading EFS!");let inode_total_blocks =super_block.inode_bitmap_blocks + super_block.inode_area_blocks;let efs = Self {block_device,inode_bitmap: Bitmap::new(1, super_block.inode_bitmap_blocks as usize),data_bitmap: Bitmap::new((1 + inode_total_blocks) as usize,super_block.data_bitmap_blocks as usize,),inode_area_start_block: 1 + super_block.inode_bitmap_blocks,data_area_start_block: 1 + inode_total_blocks + super_block.data_bitmap_blocks,};Arc::new(Mutex::new(efs))})}
}

open 函数可以获取一个磁盘上文件系统。从函数中的内容可以看出：

• 索引位图区是超级块上从 1 到长度为 inode_bitmap_blocks 的位置的内容；
• 数据位图区是 inode_total_blocks 下一个磁盘块开始长度为 data_bitmap_blocks 的位置的内容；
• 索引区域开始位置为索引位图区的下一个磁盘块位置；
• 数据区域开始位置为数据位图区的下一个磁盘位置；

这正好与磁盘布局相对应。

磁盘上的索引结构

#[repr(C)]
pub struct DiskInode {pub size: u32,pub direct: [u32; INODE_DIRECT_COUNT],pub indirect1: u32,pub indirect2: u32,type_: DiskInodeType,
}#[derive(PartialEq)]
pub enum DiskInodeType {File,Directory,
}

• size 表示文件/目录内容的字节数；
• type_ 表示索引节点的类型 DiskInodeType ，目前仅支持文件 File 和目录 Directory 两种类型；
• direct/indirect1/indirect2 都是存储文件内容/目录内容的数据块的索引，这也是索引节点名字的由来：
• 当文件很小的时候，只需用到直接索引， direct 数组中最多可以指向 INODE_DIRECT_COUNT 个数据块，当取值为 28 的时候，通过直接索引可以找到 14KiB 的内容。
• 当文件比较大的时候，不仅直接索引的 direct 数组装满，还需要用到一级间接索引 indirect1 。它指向一个一级索引块，这个块也位于磁盘布局的数据块区域中。这个一级索引块中的每个 u32 都用来指向数据块区域中一个保存该文件内容的数据块，因此，最多能够索引 $512/4=128$ 个数据块，对应 $64KiB$ 的内容。
• 当文件大小超过直接索引和一级索引支持的容量上限 $78KiB$ 的时候，就需要用到二级间接索引 indirect2 。它指向一个位于数据块区域中的二级索引块。二级索引块中的每个 u32 指向一个不同的一级索引块，这些一级索引块也位于数据块区域中。因此，通过二级间接索引最多能够索引 $128\times 64KiB=8MiB$ 的内容；

索引节点

easyfs 实现了磁盘布局并能够将所有块有效管理起来。但是对于使用者，往往不关心磁盘布局的实现，而更多的时关注目录树中逻辑上的文件和目录。 Inode 索引节点就是实现这个目的而存在的。

pub struct Inode {block_id: usize,block_offset: usize,fs: Arc<Mutex<EasyFileSystem>>,block_device: Arc<dyn BlockDevice>,
}

• block_id 是记录磁盘 id 的 ；
• block_offset 是数据在某个磁盘块中的偏移量；
• fs 是一个指向 easyfs 的指针；
• block_device 代表哪一个磁盘设备；

Inode 和 DiskInode 之间的关系

Inode 是存放在内存中的记录文件索引节点信息的数据结构，对应了磁盘上的 DiskInode 结构体的位置；

DiskInode 是磁盘中固定块的数据结构，它是磁盘上每个数据存储位置的索引，对应实际数据存放于物理的块的管理；

从超级块中得到的文件系统信息和索引的 inode_id 可以得到 Inode 数据结构体。

$Inode.block\_id=super\_block.inode\_area\_start\_block+inode\_id/inodes\_per\_block$

$Inode.block\_offset=(inode\_id\%inodes\_per\_block)asusize\ast inode\_size$

根据 Inode 结构体中的信息可以得到其数据块对应的磁盘索引的位置。

根据读出的磁盘位置索引 DiskInode 可以根据其中的 direct 、 indirect1 和 indirect2 三个字段获取数据块的实际存储位置。

举例说明读取文件的过程（ /hello ）

• 读取根目录内容，获取 hello 的 inode 信息，获取 hello 的数据索引块号；
• 根据数据索引块号找到对应的数据实际存储的物理块号；
• 读取数据信息；

参考文档

《文件系统接口》

《简易文件系统 easy-fs》