File System in xv6

xv6 文件系统层次

xv6 文件系统分为7层：

1. File Descriptor
   • 用于抽象 Unix 系统资源（管道，设备，文件等）
2. Pathname
   • 提供层级式的路径名
3. Directory
   • 每个目录被实现为一种特殊的 inode
   • 包含一组目录项，每项包含一个文件名和 i-number
4. Inode
   • 提供单独的文件, 每个文件由一个 inode 表示
   • 每个 inode 有唯一的 i-number 和一些 blocks 来存储文件的数据
5. Logging
   • 允许更高层级将针对多个 blocks 的更新打包进一个 transaction
   • 并确保一个 transaction 内的块都会被原子地更新（确保崩溃一致性）
6. Buffer Cache
   • 缓存来自 disk 的 blocks ，并和 disk 同步对于他们的访问
   • 确保一次只有一个内核进程可以修改任何 block 上的数据
7. Disk
   • 在 virtio 硬件驱动上读写 blocks

Disk

512 字节的 block 所组成的标号序列的设备

操作系统使用的 block size 和 disk 实际实现的 block size 可能不同（但通常情况下一致）

xv6 将读入内存的 block 放入结构体 struct buf

inode block 和 content block 在 Disk 中的存储

xv6 disk 分为几个 sections:

1. boot sector
2. superblock 包含文件系统元数据
   • 文件系统大小(blocks), data blocks 数量, inodes 数量, log blocks 数量
   • 通过 mkfs 程序写入
3. log blocks
4. inode blocks
   • 每个 block 内有多个 inodes
5. bitmap blocks 追踪哪些 data blocks 被使用
6. data blocks
   • 每个 data block 都在 bitmap 中被标记: free or hold

Block Allocator

in kernel/fs.c

block allocator 在磁盘中维护一个 bitmap, 每个 block 对应一个 bit (0: free, 1: in-use)

mkfs 会设置 bitmap : 包括 boot sector, superblock, log blocks, inode blocks 和 bitmap blocks 等对应的 bit

提供 2 个 API:

1. balloc()
   • 循环遍历所有 block (0 ~ sb.size), 一旦查到相应的 bitmap 中的 bit 为 0 则选择该 block 进行分配：bitmap 中 bit 置 1, block 清 0
   • 如果两个进程尝试同时分配 block 时，可能发生数据竞争：buffer cache 每次只允许一个进程访问 bitmap block
2. bfree(): 找到要释放的 block 的 bitmap 对应的 bit 并置 0

balloc() 和 bfree() 必须在一个事务内部被调用，因为二者对 bitmap block 的写入均需要通过日志系统

Buffer Cache

两个任务：

1. 同步对于 disk blocks 的访问，确保每个 block 在内存中只有一个 copy, 且一次只有一个内核线程可以使用该 copy
2. 缓存常用 blocks, 不需要反复从磁盘读 (功能同 cache 类似)

接口：

• bread: 获取一个 buf 结构体(slepp-locked)，包含相应 block 的一个 copy, 可以直接在内存中读写
• bwrite: 将一个修改过的 buf 写入 disk 中相应的位置
• brelse: 释放 buf (内核线程在 bwrite 后必须调用 brelse)

每个 buf 有一个 sleep-lock 来确保每次只有一个内核线程可以访问 buf

使用简单的 LRU 替换策略

现代的 buffer cache 往往和虚拟内存系统结合起来，支持 memory-mapped files

实现 in kernel/bio.c

buffer cache 实现为所有 buffer 的双端链表

每个 buffer 有2个状态域，valid 表明该 buffer 是否持有一个 block 的 copy, disk 表明 buffer 的内容已经被提交给 disk

• binit(): 将所有 buffer 组成的数组初始化为双端链表，之后所有对 buffer 的访问均通过 bcache.head 访问而非静态数组 buf
• bread(): 调用 bget() 从给定 sector 获取一个 buffer
  • 如果未找到，则从 disk 中读取 buffer: virtio_disk_rw(b, 0)
  • bget(): 扫描 buffer 链表
    • 如果找到 buffer ,则给 buffer 上锁(sleep-lock)并返回
    • 如果未找到 buffer ,则选择一个未使用的 buffer 替换掉(refcnt == 0)，同时标记 valid = 0
    • 如果没有找到未使用的 buffer，则 panic (说明系统中有太多的进程同时运行, 也可以 sleep 进程等待 buffer 可用)
• bwrite(): 调用 virtio_disk_rw(b, 1) 将修改过的 buffer 写入 disk
• brelse(): 释放 sleeplock 并将 buffer 加入到 buffer 链表的前端(为了使未使用的 buffer 尽可能在链表前端, 以减少链表扫描的时间)

一个更加优化的实现是：使用 hash table 实现查找，使用堆进行替换

Logging

主要解决的问题: 崩溃一致性(原子性)

• 当多个文件系统的操作涉及对磁盘的多次写入，而部分写入在崩溃之后可能导致磁盘上的文件系统处于不一致的状态
• 根据磁盘写入的顺序，崩溃可能会导致:
  1. 一个 inode 仍引用一个被标记为已释放的数据块
     • 可能导致严重的问题：
       之后文件系统可能将这个数据块分配给另外一个文件，导致两个文件指向同一个数据块
  2. 导致一个已被分配但未被引用的数据块
     • 相对无害

Log Design

xv6 通过简单的日志实现:

1. syscall 不会直接写入磁盘上的数据结构，会先将写入的操作记录到磁盘上的日志 log
2. syscall 将所有的操作写入 log 后，会再向磁盘写入一个特殊的 commit 表示提交一个完整的事务
3. 之后 syscall 将日志记录的所有写入操作复制到文件系统的实际的数据结构中，完成后清除日志

系统崩溃恢复的过程：

• 若日志完整（包含最后的那个特殊的 commit）则将写入内容复制到磁盘的对应区域
• 否则，忽略日志，并清除

除了日志系统外，也可以通过文件系统恢复程序来处理崩溃一致性，比如 UNIX 系统中的 fsck 程序，但是会比较耗时

在磁盘中存储：

• 存储在一个已知的固定位置，该位置在 superblock 中指定
  • 事务中单个 syscall 写入的总块数必须不能超出预留的日志区域
    • write syscall: 可能写入大量数据块，需要将一个大的写入操作拆分成多个小的写入操作
      大文件写入涉及许多数据块，许多位图块和一个 inode 块
      大文件删除涉及许多位图块和一个 inode 块
    • unlink syscall: xv6 中仅涉及一个 bitmap 块，不会造成问题
• 由一个 header block 和一系列需要更新的块副本（“logged block”）组成
  • header block: 包含一个扇区号数组，并包含 logged block 的数量
    • header block 中的 logged block 计数为零时，表示日志中没有事务
    • 否则为非零值，表示日志中包含一个完整的已提交事务，并带有指定数量的 logged block
    • 在事务提交时写入 header block
    • 在将 logged blocks 复制到文件系统后将 header block 的计数设置为零
    • 在事务中途崩溃会导致 header block 中的计数为零；而在提交后崩溃则会导致非零计数。
  • 每个 logged blcok 对应一个扇区号

为允许多个文件系统的并发操作，日志系统会将多个 syscall 的写入操作合并到一个事务中。
为避免一次 syscall 跨越多个事务，事务的提交只会在没有 syscall 时进行。

xv6 logging 的缺点：

1. commit 操作不能和其他 syscall 并发执行
2. 日志记录一整个 block ，尽管修改的 bytes 可能只占一小部分
3. 同步写入日志时，每次写入一个 block, 可能需要一整个磁盘旋转的时间

Group Commit

group commit: 将多个事务一起提交

• 可以将固定成本均摊到多个事务中，减少磁盘操作的次数
• 使磁盘系统可以并发处理多次写入请求

xv6 virtio 驱动不支持 group commit, 但文件系统操作支持

代码实现

in kernel/log.c

任何对磁盘的写入均需使用日志

典型的使用日志的一次完整的事务的流程：

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

1. begin_op(): 等待日志系统处理完之前的 commit 并且保证日志系统中有足够的空间容纳当前 syscall 要写入的数据, log.outstading++;
2. log_write(): 在 header block 中记录写入扇区号（写入到扇区数组的末尾），并将要写入的 buf 固定到 buffer cache 中防止被踢出
   • 对于多次针对同一个扇区的写入，支持写合并 (节省日志空间)
3. end_op(): log.outstading--;， 当其减为 0 (所有 syscall 均已完成)，提交当前日志系统的事务:commit()
   1. write_log(): 将事务中的每个要写入的 block 从 buffer cache 写入 logged block
   2. write_head(): 将 header block 写入磁盘，此时开始提交(之后的操作发生崩溃将触发崩溃恢复)
   3. install_trans(): 读取日志，将日志中要写入的块写入文件系统对应的位置
   4. write_head(): 再次将 header block 写入磁盘(写入块数计数置 0)

崩溃恢复

系统崩溃后重启恢复，因此在初始化时(fsinit()->initlog())进行崩溃恢复: recover_from_log()

recover_from_log():

1. 读取 header block
2. 如果 header block 中计数不为 0 ，则将 logged block 写入文件系统对应位置
   • 如果是崩溃恢复，会重复写入当前事务在崩溃前已写入的部分（but 无伤大雅）
3. 写入 header block (计数置 0)

Inode

in kernel/fs.c

磁盘上存储的 inode 数据结构和内核中使用的内存中的 inode 数据结构不同。
内存中的数据结构还包括一些其他的额外信息。

inode 引用的内容块不会被其他的 inode 再次引用

on-disk inode (struct dinode)

每个 inode 的大小相同，在磁盘上连续存储: inode blocks ，通过 i-number 索引 inode

数据结构为 struct dinode, fileds:

1. type: 表示类型： free(0) / file / directory / special file(device)
2. nlink: 计数引用该 inode 的目录数
   • 用于判断该 inode 何时释放数据块和 inode 块
3. size: 表示的文件的字节数
4. addrs: 文件内容占据的磁盘中的块号 (数组)
   • 包含 NDIRECT+1 个元素: 前 NDIRECT 个元素用于保存 direct blocks, 最后一个元素是保存 indirect blocks 的块号数组的块号
   • 因此，一个文件的前 12KB (NDIRECT * BSIZE) 保存在 direct blocks, 后 256KB (NINDIRECT * BSIZE) 保存在 indirect blcoks 中
   • 块号为 0 表示未分配任何块

提供给客户端的 API:

1. bmap(): 返回 inode 的第 n 个数据块的磁盘块号，如果 inode 还未占用该数据块，则为其分配一个
2. itrunc(): 释放一个 inode 的内容块, 大小置为 0
   • 首先释放所有的 direct blocks，然后释放 indirect block 指向的所有内容块 ，最后释放 indirect block 本身
3. readi(): 读取 inode 数据块，复制到 dst
4. writei(): 写入 inode 数据块，可能会扩展文件大小
5. stati(): 读取 inode 元数据，复制到 stat 结构体

in-memory inode (struct inode)

内核会在内存中保存所有 active inodes 到一个表 itable

• 主要任务是：同步多个进程的访问
• 也可以缓存对 cache 访问友好的 inode (buffer cache 也可以做到)

内存中的 inode 数据结构 struct inode

• 磁盘 inode 数据结构的拷贝
• strucy inode 中的 ref 域指示当前引用该 inode 的指针数
  • 只有在有指针引用该 inode 时 itable 才会存储该 inode
  • 引用 inode 的指针不具有独占性，所以一个 inode 可能被多个指针引用
• inode 中的同步机制
  • itable.lock 保证一个 inode 在 itable 中只出现一次，并且保护 inode.ref
  • 每个 inode 都有一个 lock 域 (sleeplock) ，确保对 inode 本身的访问和对应内容块的访问具有独占性

API:

1. iget() 和 iput() 用于获取和释放指针（并修改引用计数）
   • iget() 会扫描 itable，找到对应的 inode ，引用计数加一后返回该 inode 指针
     如果没找到，会分配 itable 中的第一个空闲 entry 返回其指针
   • iget() 返回的指针指向的 inode 可能不引用任何有效的内容
     需要先锁住 inode，然后从磁盘中读取 inode, 然后释放 inode 的锁
   • iput() 会将引用计数减 1
     如果减到 0 后发现 nlink == 0 即没有任何目录在引用该 inode ，则释放该 inode (type 置 0 并写入磁盘)以及其所引用的内容块(itrunc())
   • iput() 可能会写入磁盘，所有对其的调用都需要包在一个事务中
2. ilock() 和 iunlock() 用于获取和释放 inode 的锁
   • 读写 inode 元数据或者其引用的内容块时，必须获取 inode 的锁
   • inode 使用 sleep-lock , 类似于 buffer cache.
3. iupdate() 将对 inode 的更新写入磁盘
4. ialloc(): 分配一个新的 inode
   • 循环遍历磁盘中所有的 inode, 找到其中标记为 free 的 inode
   • 清空 inode 后将 type 写入磁盘，然后返回 inode 的一个指针:iget()
   • 可以确保一次只有一个进程可以访问当前 inode : 通过对相应 buffer 的引用

与 buffer cache 的 sleeplock 不同的是，iget() 返回的 inode 是不带锁的，这是因为目录查找等操作需要针对多个 inode 操作，可能导致死锁。

可能存在的崩溃：释放文件时崩溃

在 inode.nlink 减到 0 之后，iput() 并不会立即释放 inode 的内容块，需要等到所有的 inode.ref 也减到 0 ，如果操作系统在这段时间内发生崩溃，重启后会发现这个 inode 的内容块在磁盘中已分配，但不会有任何目录引用它

后果：随着崩溃次数的增加，操作系统的磁盘可能被这样的块占满导致没有足够的磁盘空间

解决方案：(xv6 均未实现，因此 xv6 存在此种崩溃的可能)

1. 方案一：系统重启恢复时，检查所有标记为已分配 inode 和内容块但是没有目录引用的文件，将其释放
   • 开销主要在重启时对文件系统的扫描
2. 方案二：当一个文件的 inode.nlink == 0 但是 inode.ref > 0 时将其 inumber 记录到磁盘的 superblocks 中，当 ref 也降到 0 时从 superblock 中移除该 inumber ；恢复的时候系统只释放 superblock 中记录的 inode.
   • 开销存在于操作系统运行期间的文件操作

Directory

in kernel/fs.c

目录的内部实现类似于文件，其 inode.type = T_DIR ，其数据块是一系列目录 entries: struct dirent ，包含一个目录名和 inumber:

• 目录名最多 DIRSIZ 个字节 (默认 14)
• inumber = 0 表示 entry 未分配

API:

1. dirlookup(): 使用给定的目录名搜索指定的目录 inode
   • 如果找到，用 iget() 返回对应 inode 的指针
2. dirlink(): 将给定目录名和 inumber 写入给定目录的目录项
   • 首先查找目录项中是否已有给定的目录名，如果有，返回错误(iput() for iget() in dirlookup())
   • 主循环遍历目录项查找未分配的 dirent: readi() ，找到后赋值写入磁盘: writei()

Pathname

in kernel/fs.c

API:

1. namei(): 根据路径名返回相应的 inode
2. nameiparent(): 返回路径名最后一级的父目录的inode

namei() 和 nameiparent() 均通过 namex() 实现：

1. 确定路径解析的起始位置
   • 以 “/“ 开头则从根目录解析；否则从当前目录开始解析
2. 使用 skipelem() 逐个处理路径中的每一层:
   1. 对 inode 加锁
   2. 检查其是否为目录
      • 如果不是，查找失败。（对 ip 加锁并非因为 ip->type 可能发生变化——它不会变化——而是因为在调用 ilock 之前，无法保证 ip->type 已从磁盘加载。）
   3. 如果调用是 nameiparent，并且这是路径的最后一个元素，则提前终止循环: 释放 inode 的锁并返回
   4. 使用 dirlookup() 查找路径元素。当路径元素查找完毕时，循环结束，返回最后一级的 inode

namex() 操作比较耗时，因为涉及多个磁盘操作。且其每次迭代查找时只锁单个 inode ，为的是可以尽可能支持并发操作。

File Descriptor

in kernel/file.c

Unix 操作系统中，大多数资源都可以用文件表示，包括设备、管道以及真实的管道

xv6 中，每个进程都有一个表保存所有当前进程打开的所有的文件描述符: struct file, 是一个 inode 或者一个 pipe 加 I/O offset 的包装

open 系统调用会创建一个新的文件描述符:

• 多个进程独立的打开同一个文件时，不同的实例(文件描述符)会有不同的 offset
• 一个文件可能在一个进程的文件描述符表中出现多次(dup)，或者在多个进程的表中出现(fork)

所有打开的文件都会保存到一个全局的文件表 ftable, API：

1. filealloc(): 分配一个文件
   • 扫描 ftable, 查找未被引用的文件: ref == 0 , 并返回一个新的引用
2. filedup(): 创建一个文件的复制引用
   • 增加引用计数
3. fileclose(): 释放一个对文件的引用
   • 减少引用计数
   • 当引用计数减为 0 时根据文件类型释放相应的 pipe 或 inode
4. fileread(), filewrite(): 读写文件数据
   • 检查打开模式
   • 调用底层 inode 或 pipe 的读写实现
   • 对于 inode: 在 offset 的基础上访问并增加偏移, 同时调用 ilock -> readi/writei -> iunlock
5. filestat(): 仅允许用于 inode ，并调用 stati()

---

Syscalls 与 文件系统 的交互

in kernel/sysfile.c

1. sys_link / sys_unlink: 编辑目录，创建或删除对于 inode 的引用
   sys_link: 为现有的 inode 增加一个引用/新的名字
   1. 如果 old 存在且非目录，增加 inode.nlink 计数
   2. 调用 nameiparent 找到 new 的父目录和 basename
   3. 创建一个指向 old 的新目录项
2. sys_open:
   1. 获取 inode
      • 如果使用 O_CREATE flag：则创建一个新的普通文件: create() (带 inode 锁)
      • 否则调用 namei 返回对应路径名的 inode 并加锁
   2. 为 inode 分配一个文件(filealloc)和文件描述符(fdalloc) 并初始化
3. sys_mkdir: 创建一个新的目录
4. sys_mkmod: 创建一个新的设备文件

sys_open, sys_mkdir, sys_mkmod 均通过 create 实现：
create(): 为一个新的 inode 创建一个新的名字并返回（带 inode 锁）

1. 调用 nameiparent 获取父目录的 inode
2. 调用 dirlookup 检查名字是否已存在
   • 存在名称是一个普通文件：视为成功并返回该文件的 inode
   • 若不是普通文件：返回错误
   • 若不存在：调用 ialloc 分配一个新的 inode
     • 若创建的是目录，则需要为其初始化 “.” 和 “..” 两个目录项
     • 将这个新的 inode 创建到父目录的目录项中

日志事务简化了这些系统调用的实现，因为系统调用一次可能更新多个磁盘块，使用事务将所有更新包在一起，使其原子性地执行，避免中途崩溃导致文件系统不安全