[MIT 6.1810]Xv6 Chapter 8

File system

文件系统的功能主要就是组织、存储、共享数据。

1 Overview

xv6的文件系统由七层组成。

disk ：以块为单位，读写硬盘
buffer cache：
- 缓存硬盘块
- 同步：确保每次只有一个内核进程可以修改某个特定块的数据。
logging：
- 允许高层在一个事务中对多个块进行更新
- 确保崩溃的时候，多个块的更新具有原子性（都更新或者都没更新）
inode：用i-number唯一标识了一个文件
directory：目录是一个特殊的文件，文件内容是一组目录项，每个目录项包含文件名和i-number
pathname：提供了层次路径，并递归的解析路径
file descriptor：对管道、硬件、文件等资源进行抽象

Layers of the xv6 file system

硬盘传统上以 512 字节块（也称为扇区）的编号序列来组织磁盘上的数据。操作系统文件系统使用的块大小可能与磁盘使用的扇区大小不同，但通常块大小是扇区大小的倍数。Xv6 将读取到内存中的数据块副本保存在 struct buf 类型的对象中（kernel/buf.h:1）。存储在此结构中的数据有时与磁盘不同步：这些数据可能尚未从磁盘读入（磁盘正在处理这些数据，但尚未返回扇区内容），也可能已被软件更新，但尚未写入磁盘。

xv6 将磁盘分为几个部分。

文件系统不使用块 0（存放引导扇区）。
块 1 是超级块，包含文件系统的元数据（以块为单位的文件系统大小、数据块数、inodes 数和log中的块数）。超级块由名为 mkfs 的单独程序填充，该程序负责构建初始文件系统。
从 2 开始的块存放日志。
日志之后是inodes，每个块包含多个inode。
之后是位图块，用于跟踪正在使用的数据块。
其余的块是数据块

Buffer cache layer

该层有两个功能：

同步对硬盘块的访问，确保每个硬盘块在内存中只有一份拷贝，并且每次只有一个内核线程能够访问某块数据。
缓存硬盘块

该层采用LRU策略，当文件系统请求一个新的硬盘块的时候，如果此时缓冲区已满，则需要替换一个最久未使用的块出缓冲区。

为了确保同步访问，每个 buf 都有一个 sleep-lock 锁，bread 返回一个上锁的 buf ，当某个线程使用完这个 buf 之后，需要调用 brelse 释放这个锁。

Code: Buffer cache

缓冲由一个双向链表管理，链表头结点是最近使用的结点，尾结点是最久未使用的结点。

每个 buf 有两个状态位：

valid ：表示 buf 是否持有硬盘块的一份拷贝
disk ：表示 buf 的内容被移交给硬盘，有可能导致 buf 的内容发生改变。

bcache 负责维护双向链表的头结点和一个自旋锁，该锁保护缓存块的信息，而每个 buf 的锁则负责保护对该块内容的读写。

需要确保每个硬盘块至多只有一份缓存，这需要确保对于某个块是否在缓存中的检查和对该块分配缓存块的操作是原子的。若该操作不是原子的，某个内核线程检查某个块a，发现其不在缓存中，然后执行另外一个内核线程，该块同样检查块a，发现不在缓存中，然后为该块分配了一个缓存，接下来回到第一个内核线程执行，该线程由于已经完成了检查，又为块a分配了另一个缓存，导致块a在缓存中有两份拷贝。

如果所有的 buf 此时都在被访问，则 bget 会panic。

如果某个线程修改了 buf 的内容，则它在释放该 buf 之前，必须调用 bwrite 把修改写回硬盘。

当某个线程用完了 buf ，必须调用 brelse 去释放该 buf ，该调用释放该 buf 的锁，然后将该 buf 移动到链表头。

Logging layer

xv6通过日志解决文件系统操作过程中的崩溃问题。

系统调用不会直接写入磁盘，而是在磁盘的日志中记录对磁盘的写入操作，当系统调用记录了所有写入操作，他会向磁盘写入一条特殊的提交记录，表明该日志已经包含一个完整的操作。之后，系统调用会将写入内容开始实际写入到磁盘中，写完后，将日志清除。

如果系统崩溃并重新启动，在运行任何进程之前，文件系统代码会按如下方式从崩溃中恢复：

如果日志被标记为包含完整操作，那么恢复代码会将写入内容复制到磁盘文件系统中属于它们的位置。
如果日志未标记为包含完整操作，则恢复代码会忽略日志。
恢复代码最后会擦除日志。

Log design

日志位于超级块中指定的已知固定位置。日志由一个标题块和一系列更新块副本（“日志块”）组成。标题块包含一个扇区号数组（每个日志块一个）和日志块计数。磁盘标题块中的计数要么为零，表示日志中没有事务；要么为非零，表示日志中包含一个完整的已提交事务。Xv6 会在事务提交时写入标题块，而不会在事务提交前写入，并在将日志块中指定的操作完成后将计数设为零。

每个系统调用的代码标记了需要原子写入的一系列操作（即要么全部成功，要么全部失败的写入操作）。为了允许多个进程并发执行文件系统操作，日志系统可以将多个系统调用的写入操作累积成一个事务。这种方式允许系统在单个提交中处理多个系统调用的写入请求，这样可以提高效率。

为了避免将一个系统调用分成多个事务，日志系统只有在没有文件系统调用进行时才会提交事务。

将多个事务一起提交的想法被称为分组提交。分组提交可减少磁盘操作次数，因为它将提交的固定成本分摊到多个操作中。

Code: logging

系统调用中对日志的一个典型用法：

begin_op();
// ...
bp = bread(...);
bp->data[..] = ...;
log_write(bp);
// ...
end_op();

begin_op 等待日志系统完成提交，或者有足够的空间记录所有写入块。log.outstanding 表示目前正在执行的系统调用的个数，可以保证提交不会发生在某个系统调用执行过程中。

log_write 是 bwrite 的代理。它在内存中记录了需要写入的块号，并且将 buf 的 refcnt 字段加1，确保该块在提交之前一直保留在缓存中。需要注意的是，如果在一个事务中对某个块多次写入，log_wirte 只会保留一个记录，这样可以提高效率，这种优化技术称为 absorption。

end_op 首先将 log.outstanding 减1，如果 log.outstanding 现在是0，表示该事务是最后一个事务，那么可以提交。

commit 分为四个阶段：

write_log 将需要记录的块写入到磁盘中的log中。
write_head 将当前内存中的标题块写入到磁盘中。这是实际的提交点，在该写入之后的崩溃，都会重新执行崩溃前的事务。
install_trans 将log中的块写入到实际的块。
将标题块中的count置0

Code: Block allocator

xv6用位图来管理空闲块。

balloc 在位图中找一个空闲位。

bfree 在位图中清除一个位。

这两个函数必须在一个事务中调用。

Inode layer

Inode 一词有两种含义：

它可以指包含文件大小和数据块编号列表的磁盘数据结构。
或者，“inode ”可能指内存中的 inode，它包含磁盘 inode 的副本以及内核所需的额外信息。

on-disk inode

磁盘上的inode被打包到磁盘上的一个连续区域，每个inode的大小都是固定的。

// On-disk inode structure
struct dinode {
  short type;           // File type
  short major;          // Major device number (T_DEVICE only)
  short minor;          // Minor device number (T_DEVICE only)
  short nlink;          // Number of links to inode in file system
  uint size;            // Size of file (bytes)
  uint addrs[NDIRECT+1];   // Data block addresses
};

in-memory inode

内核在 itable 中管理in-memory inode。

// in-memory copy of an inode
struct inode {
  uint dev;           // Device number
  uint inum;          // Inode number
  int ref;            // Reference count
  struct sleeplock lock; // protects everything below here
  int valid;          // inode has been read from disk?

  short type;         // copy of disk inode
  short major;
  short minor;
  short nlink;
  uint size;
  uint addrs[NDIRECT+1];
};

内核只有在当前有c指针引用该inode的时候，才会将其加载到 itable 中。

xv6中关于inode有四种锁：

itable.lock 保证某个inode至多只在 itable 中出现一次。并且保证 ref 字段的一致性。
inode.lock 保证对 inode 的互斥访问。
ref 字段保证系统不要重用其 itable 中的inode。
unlink 字段维护引用某个文件的目录项个数。

iget 返回的inode保证是有效的，而且不是互斥访问的。需要注意的是，iget 返回的inode只保证是有效的，但是内容并不一定有用，必须调用 ilock 将其从硬盘中读入内存中。这种分离机制帮助避免一些死锁情况。

Code: Inodes

ialloc 遍历所有inode，找出一个空闲的inode结点并分配之。

iget 在 itable 中查找指定的inode，如果找到，返回之，否则重用一个空闲的inode。

iput 释放一个引用某个inode的c指针，如果该c指针是最后一个引用该inode的指针，则表明 itable 中的该项可以重用。如果 iput 发现某个inode的 ref 字段和 unlink 字段为0，则表明该inode表示的文件必须被删除。iput 调用 itrunc 将该文件截断，释放相应的数据块，将 type 字段设置为0，并将该 inode 写回磁盘中。

iput 中的锁策略：

另外一个线程可能正在等待 ilock ，这种情况下，当前执行 iput 的线程的 ref 字段不可能为0，保证了不会将inode释放掉。
对 ialloc 的并发调用可能会选择 iput 正在释放的同一个 inode。这种情况只有在 iupdate 写入磁盘，使 inode 类型为零之后才会发生。这种竞赛是良性的；分配线程会礼貌地等待获得 inode 的休眠锁，然后再读取或写入 inode，此时 iput 就完成了。

iput 可能会写硬盘，这意味着即使是只读的系统调用也必须封装在一个事务中。

当文件的链接数降为零时，iput 不会立即截断文件，因为某些进程可能仍在内存中持有对 inode 的引用：某个进程可能仍在读写文件，因为它成功打开了文件。但是，如果崩溃发生在最后一个进程关闭文件的文件描述符之前，那么该文件将被标记为已在磁盘上分配，但没有目录项指向它。
文件系统有两种方法处理这种情况。

一种简单的解决方案是，在重启后恢复时，文件系统会扫描整个文件系统，查找标记为已分配但没有目录项指向的文件。如果存在这样的文件，就可以释放这些文件。
第二种解决方案不需要扫描文件系统。在这种解决方案中，文件系统会在磁盘上（如超级块中）记录链接计数降为零但引用计数不为零的文件的 inode inumber。如果文件系统在其引用计数为 0 时删除了该文件，那么它就会更新磁盘上的列表，将该 inode 从列表中删除。恢复时，文件系统会释放列表中的任何文件。
Xv6 没有实现任何一种方案，这意味着即使节点不再使用，它们也可能被标记为已在磁盘上分配。这意味着随着时间的推移，xv6 可能会面临磁盘空间耗尽的风险

Code: Inode content

磁盘 inode 结构 struct dinode 包含一个大小和一个块编号数组（见图 8.3）。数组的前12个数据块是直接数据块，最后一个数据块是间接数据块。函数 bmap 对表示法进行了管理，这样我们即将看到的 readi 和 writei 等高级例程就不需要管理这种复杂性了。如果 ip 还没有这样的数据块，bmap 会根据需要分配数据块。如果 ip->addrs[] 或间接条目为零，则表示没有分配块。当 bmap 遇到零时，它会用按需分配的新块的编号来代替。

Code: directory layer

目录其实就是一个文件，它的内容是一串目录项。每个目录项 struct dirent 包含文件名和inode number。文件名最多 DIRSIZE （14）个字符，inode numer为0表示该目录项是空闲的。

函数 dirlookup 会在一个目录中搜索带有给定名称的条目。如果找到了，它会返回一个指向相应 inode 的指针（未上锁），并将 *poff 设置为该条目在目录中的字节偏移量，以备调用者编辑。如果 dirlookup 找到了名称正确的条目，它会更新 *poff 并返回通过 iget 获得的未上锁的 inode。调用者已经锁定了 dp，因此如果查找的是当前目录的别名 .，在返回之前尝试锁定 inode 会重新锁定 dp 并导致死锁。(还有更复杂的死锁情况，涉及多个进程和..（父目录的别名）；. 不是唯一的问题）。调用者可以先解锁 dp，然后再锁定 ip，以确保每次只持有一个锁。

函数 dirlink 使用给定的名称和 inode 编号向目录 dp 写入一个新的目录条目。如果名称已经存在，dirlink 会返回错误信息。主循环读取目录条目，寻找未分配的条目。找到后，它会提前结束循环，并将 off 设为可用条目的偏移量。否则，循环结束，off 设置为 dp->size。无论哪种情况，dirlink 都会在偏移量 off 处写入一个新条目。

Code: Path names

路径名查找涉及对 dirlookup 的连续调用，每个路径组件都有一个调用。namei 对路径进行求值并返回相应的 inode。函数 nameiparent 是一个变体：它在最后一个元素之前停止，返回父目录的 inode 并将最后一个元素复制到 name 中。

File descriptor layer

Xv6 为每个进程提供了自己的打开文件表或文件描述符。每个打开的文件都由一个 struct file 表示，它是对 inode 或管道的封装，外加一个 I/O 偏移量。每次调用 open 都会创建一个新的打开文件：如果多个进程独立打开同一个文件，不同的实例会有不同的 I/O 偏移量。另一方面，一个打开的文件（同一个结构文件）可以多次出现在一个进程的文件表和多个进程的文件表中。如果一个进程使用 open 打开文件，然后使用 dup 创建别名，或使用 fork 与子进程共享，就会出现这种情况。引用计数跟踪特定打开文件的引用次数。文件可以为读取或写入打开，也可以同时为读取和写入打开。可读和可写字段会跟踪这一点。

struct file {
  enum { FD_NONE, FD_PIPE, FD_INODE, FD_DEVICE } type;
  int ref; // reference count
  char readable;
  char writable;
  struct pipe *pipe; // FD_PIPE
  struct inode *ip;  // FD_INODE and FD_DEVICE
  uint off;          // FD_INODE
  short major;       // FD_DEVICE
};

系统中所有打开的文件都保存在一个全局文件表 ftable 中。文件表中有分配文件（filealloc）、创建重复引用（filedup）、释放引用（fileclose）以及读写数据（fileread 和 filewrite）的函数。

filealloc (kernel/file.c:30) 会在文件表中扫描未引用的文件（f->ref ==0）并返回一个新的引用；filedup (kernel/file.c:48) 会增加引用计数；fileclose (kernel/file.c:60) 会减少引用计数。当文件的引用计数为零时，fileclose 会释放底层管道或 inode。

函数 filestat、fileread 和 filewrite 实现了对文件的统计、读取和写入操作。filestat（kernel/file.c:88）只允许对 inode 进行操作，并调用 stati。fileread 和 filewrite 会检查打开模式是否允许操作，然后将调用传递给管道或 inode 实现。如果文件代表一个 inode，fileread 和 filewrite 会使用 I/O 偏移量作为操作的偏移量，然后向前推进（kernel/file.c:122-123）（kernel/file.c:153-154）。管道没有偏移量的概念。回想一下，inode 函数要求调用者处理加锁（kernel/file.c:94-96）（kernel/file.c:121-124）（kernel/file.c:163-166）。inode 锁定有一个方便的副作用，即读取和写入的偏移量是原子更新的，因此多个同时写入同一文件的人不会覆盖彼此的数据，尽管他们的写入可能会交错进行。

Code: System calls

函数 sys_link 和 sys_unlink 编辑目录，创建或删除对 inodes 的引用。sys_link 首先获取参数，即两个字符串 old 和 new。假设 old 存在且不是目录，sys_link 会增加其 ip->nlink 计数。然后，sys_link 调用 nameiparent 查找 new 的父目录和最终路径元素，并创建一个指向 old 的 inode 的新目录条目。新的父目录必须存在，并且与现有的 inode 位于同一设备上：inode 只有在单个磁盘上才有唯一意义。如果出现类似错误，sys_link 必须返回并递减 ip->nlink .

由于需要更新多个磁盘块，因此事务简化了执行过程，但我们不必担心更新的顺序。它们要么全部成功，要么一个都不成功。例如，如果没有事务，在创建链接之前更新 ip->nlink 会使文件系统暂时处于不安全状态，而中间的崩溃可能会导致大灾难。有了事务，我们就不必担心这个问题了。

sys_link 为现有的 inode 创建新名称。函数 create为新的 inode 创建新名称。它是对三种文件创建系统调用的概括：使用 O_CREATE 标志打开一个新的普通文件，使用 mkdir 创建一个新的目录，使用 mkdev 创建一个新的设备文件。与 sys_link 类似，create 也是通过调用 nameiparent 来获取父目录的 inode。然后调用 dirlookup 检查名称是否已经存在。如果名称确实存在，create 的行为将取决于它被用于哪个系统调用：open 与 mkdir 和 mkdev 的语义不同。如果 create 是代表 open 使用（类型 == T_FILE），而存在的名称本身就是一个普通文件，那么 open 会将其视为成功。否则会出错。如果文件名不存在，create 会使用 ialloc 分配一个新的 inode。如果新的 inode 是一个目录，create 会使用 . 和 ..条目对其进行初始化。最后，既然数据已经正确初始化，create 就可以将其链接到父目录。create 和 sys_link 一样，同时持有两个 inode 锁：ip 和 dp。由于 inode ip 是新分配的，因此不会出现死锁：系统中不会有其他进程在持有 ip 锁后又试图锁定 dp。

使用 create，可以很容易地实现 sys_open、sys_mkdir 和 sys_mknod。sys_open是最复杂的，因为创建新文件只是它能做的事情的一小部分。如果 open 传递了 O_CREATE 标志，它就会调用 create。否则，它将调用 namei。必须锁定 inode 本身。这为检查目录是否只为读取而不是写入打开提供了方便。假设以某种方式获得了 inode，sys_open 会分配一个文件和一个文件描述符，然后填入文件。请注意，其他进程无法访问部分初始化的文件，因为它只存在于当前进程的表中。

操作系统

#MIT 6.1810

[MIT 6.1810]Xv6 Chapter 8

https://erlsrnby04.github.io/2024/10/27/MIT-6-1810-Xv6-Chapter-8/

作者

ErlsrnBy04

发布于

2024年10月27日

许可协议

[OOP]C++面向对象高效编程 Chapter 1 上一篇

[GIT]常用基本操作下一篇