文件系统实现 | Uonlra‘s Blog

type

status

date

slug

summary

基本策略

文件系统的数据结构

文件系统在磁盘上使用哪些类型的结构来组织其数据和元数据？如块或其他对象的数组，还有更复杂的基于树的结构。

💡

心智模型

心智模型是学习系统时的发展方向，它包含以下问题答案：

磁盘上的哪些结构存储文件系统的数据和元数据?

当一个进程打开一个文件时会发生什么？

在读取或写入期间访问哪些磁盘结构?

通过研究和改进心智模型，可以对发生得到事情有一个抽象的理解。

访问方法（access method）

如何将进程发出的调用，如open()、read()、write()等，映射到它的结构上？
在执行特定系统调用期间读取哪些结构？
改写哪些结构？
所有这些步骤的执行效率如何？

整体组织

首先我们需要将磁盘分成块（block）。简单的文件系统只使用一种块大小。我们现在用4KB。

构建文件系统磁盘分区：一系列块，每块大小为4KB。在1大小为N个4KB块的分区中，这些块地址从0到N-1。假设有一个非常小的磁盘，只有64块：

为了构建文件系统，我们首先应该在这些块中存储用户数据，将用于存放用户数据的磁盘区域称为数据区域（data region），简单起见，将磁盘的固定部分留给这些块，例如磁盘上64个块的最后56个：

文件系统必须记录每个文件的信息。该信息是元数据（metadata）的关键部分，并且记录诸如文件包含哪些数据块、文件的大小，其所有者和访问权限、访问和修改时间以及其他类似信息的事情。为了存储这些信息，文件系统通常有一个名为inode的结构。

为了存放inode，我们需要在磁盘上留出一些空间。将这部分磁盘称为inode表（inode table) ，它只是保存了一个磁盘上inode的数组。我们现在将64个块中的5块用于inode，磁盘映像如下：

现在还需要某种方法来记录inode或数据块是空闲还是已分配。因此，需要分配结构（allocation structure) 是所有文件系统中必须的部分。我们选择位图（bitmap）来分配记录，一种是数据区域（data bitmap），另一种用于inode表（inode位图，inode bitmap）。位图是一种简单的结构：每个位用于指示相应对象/块是空闲（0）还是正在使用（1）。因此新的磁盘布局如下（包含inode位图 i，和数据位图 d）：

最后一块我们留给超级块（superblock），用S表示，超级块包含关于特定文件系统的信息，包括例如文件系统中有多少个 inode 和数据块、inode 表的开始位置等。还可能包含一些幻数，来识别文件系统类型。

因此，在挂载文件系统时，操作系统将首先读取超级块，初始化各种参数，然后将该卷添加到文件系统树中。当卷中的文件被访问时，系统就会知道在哪里查找所需的磁盘上的结构。

Inode

文件系统最重要的磁盘结构之一，几乎所有的文件系统都有类似的结构。是index node(索引节点) 的缩写，因为这些节点最初放在一个数组中，在访问特定的inode时会用到该数组的索引。

💡

数据结构 — inode

inode 是许多文件系统中使用的通用名称，用于描述保存给定文件的元数据的结构。

inode 号用于索引磁盘上的inode数组，以便查找该inode号对于的inode。其设计是文件系统的关键部分之一，大多数现代系统对于它们记录的每个文件都有这样的结构。

每个inode都由一个数字（inumber）隐式引用，也就是低级文件名称（low-level name)。在VSFS中，给定一个inumber能直接计算磁盘对于节点的位置。例如，获取VSFS的inode表。

假设 inode区域从 12KB 开始（即超级块从 0KB 开始，inode 位图在 4KB 地址，数据位图在 8KB，因此 inode 表紧随其后）。因此，在 VSFS 中，我们为文件系统分区的开头提供了以下布局（特写视图）：

要读取 inode 号 32，文件系统首先会计算 inode 区域的偏移量（32×inode 的大小，即 8192），将它加上磁盘 inode 表的起始地址（inodeStartAddr = 12KB），从而得到希望的 inode 块的正确字节地址：20KB。

在每个inode中，实际上是所有关于文件的信息：文件类型、大小、分配的块数、保护信息、一些时间信息，以及有关其数据块驻留在磁盘上的位置信息。我们将这些信息称为元数据（metadata）。实际上，文件系统中除了纯粹的用户数据外，其他任何信息通常都称为元数据。

设计inode时，最重要的决定之一是它如何引用数据块的位置。一种简单的方法是在inode中有一个或多个直接指针。每个指针指向属于该文件的一个磁盘块。但是若想要一个非常大的文件（如块的大小乘以直接指针数）则无法实现。

多级索引

为了支持更大的文件，文件系统设计者必须在inode中引入不同的结构。一个常见的思想是有一个称为间接指针（indirect pointer）的特殊指针。它不是指向包含用户数据的块，而是指向包含更多指针的块，每个指针指向用户数据。因此，inode 可以有一些固定数量（例如 12 个）的直接指针和一个间接指针。如果文件变得足够大，则会分配一个间接块（来自磁盘的数据块区域），并将 inode 的间接指针设置为指向它。假设一个块是 4KB，磁盘地址是 4 字节，那就增加了 1024 个指针。文件可以增长到（12 + 1024）×4KB，即 4144KB。

💡

另一种方法是基于范围的方法

范围就是一个磁盘指针加一个长度（以块为单位）。因此，不需要指向文件的每个块的针，只需要指针和长度来指定文件的磁盘位置。只有一个范围是有局限的，因为分配文件时可能无法找到连续的磁盘可用空间块。因此，基于范围的文件系统通常允许多个范围，从而在文件分配期间给予文件系统更多的自由。

在在这种方法中，为了支持更大的文件。只需要添加另一个指向inode的指针：双重间接指针（double indirect pointer)。该指针指的是一个包含间接块指针的块，每个间接块都包含指向数据块的指针。因此，双重间接块提供了可能性，允许使用额外的 1024×1024 个 4KB 块来增长文件，换言之，支持超过 4GB 大小的文件。同样的还有三种间接指针。

这种不平衡树被称为指向文件块的多级索引（multi-level index）方法。若有 12 个直接指针，以及一个间接块和一个双重间接块。假设块大小为 4KB，并且指针为 4 字节，则该结构可以容纳一个刚好超过 4GB 的文件，即（12 + 1024 + 10242）×4KB

💡

还有一种方法—基于链接的方法

使用链接表（linked list) 来设计inode，这样在一个inode中，不是有多个指针，只需要以个，指向文件的第一个块。要处理较大的文件，就在该数据块的末尾添加另一个指针等，这样就可以支持大文件。

为了使链接式更好地工作，一些系统必须在内存中保留链接信息表，而不是将下一个指针于数据块本身一起存储。该表用数据块 D 的地址来索引，一个条目的内容就是 D 的下一个指针，即 D 后面的文件中的下一个块的地址。

那里也可以是空值（表示文件结束），或用其他标记来表示一个特定的块是空闲的。拥有这样的下一块指针表，使得链接分配机制可以有效进行随机文件访问，只需首先扫描（在内存中）表来查找所需的块，然后直接访问（在磁盘上）。

目录组织

在VSFS中,目录的组织很简单。一个目录基本上只包含一个二元组（条目名称，inode 号）的列表。对于给定目录中的每个文件或目录，目录的数据块中都有一个字符串和一个数字。对于每个字符串，可能还有一个长度（假定采用可变大小的名称）。

在命令行运行：ls -a 可知，每个目录有两个额外的条目：.（点）和..（点点）。点目录就是当前目录（在本例中为 dir），而点点是父目录（在本例中是根目录）。

通常，文件系统将目录视作特殊类型的文件。因此，目录有一个inode，位于inode表中的某（inode 表中的 inode 标记为“目录”的类型字段，而不是“常规文件”）。。该目录具有由inode指向的数据块。这些数据块存在于我们的简单文件系统的数据块区域中。磁盘结构因此保持不变。

空闲空间管理

文件系统必须记录哪些 inode 和数据块是空闲的，哪些不是，这样在分配新文件或目录时，就可以为它找到空间。因此，空闲空间管理（free space management）对于所有文件系统都很重要。在 VSFS 中，我们用两个简单的位图来完成这个任务。

当我们创建一个文件时，必须为该文件分配一个inode。文件系统将通过位图搜索一个空闲的内容，并将其分配给该文件。文件系统必须将inode标记为已使用（用1），并最终用正确的信息更新磁盘上的位图。分配数据块时会发生类似的一组活动。

读取和写入的访问路径

现在我们假设文件系统以及挂载，超级块以及在内存中。其他所有文件仍在磁盘上。

从磁盘读取文件

当发出open() 调用时，文件系统首先需要找到文件的inode,从而获得文件的一些基本信息。为此，文件系统必须能够找到inode，但现在只有完整的路径名，必须遍历路径名，从而找到所需的inode。

所有遍历都从文件系统的根开始，即根目录（root directory），它就记为/。因此，文件系统的第一次磁盘读取是根目录的 inode。为了知道inode在哪里，必须先知道它的i-number。通常在其父目录中找到文件或目录的i-number。根没用父目录。在大多数 UNIX 文件系统中，根的 inode 号为 2。因此，要开始该过程，文件系统会读入 inode 号 2 的块（第一个 inode 块）。

一旦 inode 被读入，文件系统可以在其中查找指向数据块的指针，数据块包含根目录的内容。因此，文件系统将使用这些磁盘上的指针来读取目录。下一步是递归遍历路径名，知道找到所需的inode。然后文件系统进行最后的权限检查，在每个进程的打开文件表中，为此进程分配一个文件描述符，并将它返回给用户。

打开后，程序可以发出 read()系统调用，从文件中读取。第一次读取（除非 lseek()已被调用，则在偏移量 0 处）将在文件的第一个块中读取，查阅 inode 以查找这个块的位置。它也会用新的最后访问时间更新 inode。读取将进一步更新此文件描述符在内存中的打开文件表，更新文件偏移量，以便下一次读取会读取第二个文件块，等等。

在某个时候，文件将被关闭。这里要做的工作要少得多。很明显，文件描述符应该被释放，但现在，这就是 FS 真正要做的。没有磁盘 I/O 发生。整个过程如表 40.3 所示（向下时间递增）。在该表中，打开导致了多次读取，以便最终找到文件的 inode。之后，读取每个块需要文件系统首先查询 inode，然后读取该块，再使用写入更新 inode 的最后访问时间字段。

写入磁盘

写入文件是一个类似的过程。首先，文件必须打开（如上所述）。其次，应用程序可以发出 write()调用以用新内容更新文件。最后，关闭该文件。

与读取不同，写入文件也可能会分配（allocate）一个块（除非块被覆写）。当写入一个新文件时，每次写入操作不仅需要将数据写入磁盘，还必须首先决定将哪个块分配给文件，从而相应地更新磁盘的其他结构（例如数据位图和 inode）因此，每次写入文件在逻辑上会导致 5 个 I/O：

读取数据位图，然后更新以标记新分配的块被使用

写入位图，将他的新状态存入磁盘

两次读取

写入inode，用新块的位置更新

写入真正的数据块本身

要创建一个文件，文件系统不仅要分配一个 inode，还要在包含新文件的目录中分配空间。这样做的 I/O 工作总量非常大：一个读取 inode 位图（查找空闲 inode），一个写入 inode 位图（将其标记为已分配），一个写入新的 inode 本身（初始化它），一个写入目录的数据（将文件的高级名称链接到它的 inode 号），以及一个读写目录 inode 以便更新它。下图展示了在 open()（创建文件）期间和在 3 个 4KB 写入期间发生的情况。