在Rust中从头开始编写文件系统

程序产生的数据需要存储在某个地方以备将来参考，而且必须有某种组织，这样我们才能快速检索所需的信息。文件系统(FS)负责此任务，并在物理存储数据的存储设备上提供抽象。

在这篇文章中，我们将更多地了解文件系统使用的概念，以及在编写您自己的文件系统时它们是如何组合在一起的。

当数据存储在硬盘驱动器(HDD)或固态驱动器(SSD)中时，它以称为扇区(在SSD情况下称为页)的小单位写入。驱动器没有任何关于这段数据代表什么的信息，尽管如此，磁盘只是一个巨大的扇区阵列。理解这一切是文件系统的工作。

文件系统将磁盘划分为固定大小的块。FS使用这些块中的大部分来存储用户数据，但也有一些块用于存储文件系统操作所必需的元数据。

下图举例说明了文件系统如何组织磁盘上的信息：

超级块存储关于文件系统的大部分元数据，例如：块大小、时间戳、正在使用的块和文件的数量以及有多少空闲的，等等。

位图是跟踪哪些数据块和索引节点空闲的一种方式。位图中的索引设置为0表示空闲时隙，而索引设置为1表示占用的时隙。

Inode是存储有关文件的元数据的结构。形成文件的数据块的权限、大小、位置等属性保存在inode中。

Inode存储在一起形成inode表的块中，如下图所示。

对于设置为1的inode位图中的每个插槽，表中将有一个对应的inode。槽的索引与表中的索引相同，这解释了名称inode是索引节点的简称。

顾名思义，数据块是写入文件的实际数据的块。这些积木也有不同的用途，我们很快就会看到。

Inode需要有一种指向组装文件的数据块的方式。最简单的方法是有直接的指针。在这种情况下，每个指针都指向包含某些文件数据的块。问题是，这种模式不支持大文件(大小超过索引节点可以拥有的直接指针数)。解决这个问题的一种方法是使用间接指针，而不是存储用户数据，而是存储指向保存用户数据的块的指针。对于较大的文件，使用双间接指针添加另一层间接层。而对于更大的文件，则会使用三个间接指针。

为了给出每个级别允许的最大文件大小的概念，让我们运行一个示例，假设每个块大小为4 KiB。研究表明，大多数文件都很小[1]，因此12个直接指针可以支持高达48 KiB的文件。考虑到每个指针占用4个字节，因此单个间接指针将允许文件最大约为4 MiB：

最后，使用三个间接指针，文件的大小可能在4TiB左右：

此方法对于处理大文件可能效率不高。例如，100MiB的文件需要分配25600个数据块。如果数据块在磁盘上碎片化，性能可能会受到严重影响。

一些文件系统使用区段来帮助解决这种情况。在这种方法中，只有一个指针和一个长度来告诉数据从指针的地址开始，并在给定的块范围内运行。在上面的示例中，描述同一文件将使用大小为100MB的单个区段。可以使用多个区段来支持更大的文件。

您可能已经注意到，目录没有特定的结构。其背后的原因是inode同时表示文件和目录。区别在于存储在相应数据块中的内容。目录只是它包含的所有文件的列表。每个条目的形式为(名称、索引号)，因此在查找特定文件(或另一个目录)时，系统使用该名称来查找相应的inode。

如果目录包含大量文件，则搜索文件可能会很慢。这个问题可以通过维护排序的列表并使用二进制搜索来缓解，或者也可以使用哈希表或平衡搜索树而不是将其表示为列表。

从文件读取时，文件系统需要遍历整个路径，沿途访问每个信息节点，直到到达所需文件的信息节点。假设用户具有访问文件的权限，文件系统会咨询与其关联的块，然后从这些块读取请求的数据。

当写入文件时，同样的过程必须找到相应的inode。如果写入需要新的数据块，则文件系统必须分配该数据块，更新相关信息(位图和索引节点)，然后写入该数据块。因此，一次写入操作需要五次I/O操作：一次读取位图，一次写入以将新块标记为已占用，两次读取和写入索引节点，以及一次写入块中的数据。在创建新文件时，此数字可能会增加，因为现在还必须读取和写入目录的关联信息以反映此新文件，以及创建新索引节点的操作。

作为一个附带项目，我决定在学习Rust语言时编写自己的文件系统。有些方面受到ext4[2](和家族)的启发，在本节中，您将了解更多关于它的信息。文件系统使用FUSE[3]，磁盘表示为常规文件。数据块大小可以配置为1 KiB、2 KiB或4 KiB。对于4KiB的数据块大小，文件大小最高可达4 GiB，而文件系统理论上最大可达16 TiB。

第一步是使用文件系统的配置值创建映像本身。这是通过mkfs命令实现的：

运行该命令后，将创建总大小为10 GiB的映像，并且文件系统中的每个数据块的大小为4 KiB。

在此步骤中，将配置值和其他结构(如根目录)写入第一个块(即超级块)中的映像。它对应的位图条目和数据也被写入。这些值将有助于下一步：挂载文件系统。

创建映像后，我们需要挂载它，以便可以开始使用它。Mount命令用于执行以下操作：

超级块写入前1024个字节，它保存mkfs命令中提供的配置值。

发布结构超级块{发布魔术：u32，发布块大小：u32，发布创建时间：u64，发布修改时间：选项<；U64>；，发布最后安装时间：选项<；U64>；，pub block_count：u32，pub inode_count：u32，pub free_block：u32，pub free_inode：u32，pub group：u32，pub data_block_per_group：u32，pub uid：u32，pub gid：u32，pub checksum：u32，}。

接下来的两个块表示数据位图和信息节点位图。然后，将n个块的运行用于索引节点表。并且紧随其后的块是将写入用户数据的块。

Pub struct inode{pub mode：libc：：mode_t，pub hard_link：u16，pub user_id：libc：：uid_t，pub group_id：libc：：gid_t，pub block_count：u32，//pub大小：u64，pub Created_at：u64，pub access_at：option<；i64>；，pub Modified_at：option。I64>；，发布直接块：[u32；作为usize的直接指针]，发布间接块：u32，发布双间接块：u32，发布校验和：u32，}。

如上所述，inode支持双间接指针，这意味着对于块大小为4 KiB的磁盘，文件的最大容量为4 GiB。直接指针数量设置为12：

第一次启动文件系统时，将使用下面的定义创建根目录：

信息节点位图具有4 KiB，这意味着每个位图块将具有32768个信息节点的容量。假设我们将inode的大小四舍五入为128字节；相应的inode表将需要4MiB的空间。构造它们的方法之一是让许多块专用于位图，然后相应的编号块用于存储索引节点，其余块用于用户数据。

与其这样做，我们可以创建块组，使其始终具有一个用于数据位图的块和一个用于inode位图的块。接下来的1024个数据块包含索引节点表，然后是用于用户数据的32768个数据块。

现在“磁盘”已经设置好了，我们可以开始从其中写入和读取文件了。使用mkdir创建新目录：

发生的过程如下：系统搜索根目录的索引节点，查找内容正被写入的数据块，为新目录分配新的索引节点和数据块，将条目写入根目录，最后将新目录写入其数据块。

写入新文件遵循类似的方法。系统遍历给定路径，直到到达最终目录，并添加表示新文件的条目。

WRITE函数提供路径、带有数据的缓冲区、偏移量和一个fileinfo结构，该结构可能包含一个文件句柄以及关于该文件的额外信息：

在这种情况下，系统不会再次遍历路径来查找索引节点，而是使用文件句柄(FS之前在创建文件时设置了它)。有了inode，FS就可以通过查找写入inode的确切位置来构建结构：

Fn inode_offsets(&；self，index：u32)->；(U64，U64){let inodes_per_group=self.superblock().data_block_per_group as U64；let inode_bg=(index as U64-1)/inodes_per_group；let bitmap_index=(index as U64-1)&；(inodes_per_group-1)；(inode_bg，bitmap_index)}fn inode_Seek_position(&；self，index：u32)->；U64{let(group_index，bitmap_index)=self.inode_offsets(Index)；let block_size=sel.superblock().block_size；group_index*util：：block_group_size(Block_Size)+2*block_size as U64+bitmap_index*inode_size+superblock。

既然FS有了关于当前分配给inode的数据块的信息，它就可以使用这些信息来查找写入数据的确切位置，过程类似于上面所示的过程。新数据块首先添加到信息节点直接数据块阵列，如果文件大小超过(12*block_size)，FS将分配一个INDIRECT_BLOCK，其中包含标识包含用户数据的其他数据块的编号。在文件更大且需要更多块的情况下，系统使用指向更多间接块的DUBLE_INDIRECT_BLOCK字段添加额外的间接层。从文件读取遵循相同的方法。您可以看到它在这里运行：

文件系统背后的思想是为磁盘上的内容定义一个结构，然后允许系统在创建、写入和读取文件和目录时在其上操作。

我们学习了一些用于磁盘格式的概念，目录和文件是如何表示的。一个有趣的方面是使用间接指针来存储大文件。如果您有兴趣了解有关文件系统的更多信息，我建议您阅读更多有关使用的其他技术的信息，例如日志记录、写入时复制、日志结构的文件系统，以及现代文件系统如何应用这些技术和其他技术。也许可以开始学习一下你现在正在使用的那个。

[1]Agrawal，N.，Bolosky，W.J.，Douceur，J.R.和Lorch，J.R.，2007。一项为期五年的文件系统元数据研究。ACM存储学报(TOS)，3(3)，第9-ES页。