File System

概述

文件系统的目的是组织和存储数据。文件系统通常支持用户和应用程序之间的数据共享，并且具有持久性。

主要有三个主题：崩溃恢复、磁盘文件排布、性能。

文件系统的路径名提供了文件的可读性，它内置 offset ，可为文件创建别名链接。其内部对文件的标识不依赖于文件名

文件系统的目的是实现一系列API，也即是典型的文件系统API。但是，这并不是唯一构建一个存储系统的方式。例如数据库的API

数据库如果没有直接访问磁盘的权限的话，通常是在文件系统之上实现的

inode

• fs 用 inode 表示一个文件对象，这个数字标识了一个文件。
• 存在一个 link count 来跟踪指向这个inode的文件名的数量
  • 为0时才删除文件
  • 实际中可能有 openfd count，二者均为0时才会删除文件

fd

主要与用户进程进行交互

• 为了追踪I/O，fd 维护了读写的 offset

文件系统层次结构

• 磁盘层： 持久化存储
• block cache：缓存，避免频繁的读写磁盘
• logging：应对崩溃，维护持久性
• inode cache：同步
• inode：读写
• 文件名、fd

fs 与 disk

实际中有非常非常多不同类型的存储设备，这些设备的区别在于性能，容量，数据保存的期限等。其中两种最常见，并且你们应该也挺熟悉的是SSD和HDD。这两类存储虽然有着不同的性能，但是都在合理的成本上提供了大量的存储空间。SSD通常是0.1到1毫秒的访问时间，而HDD通常是在10毫秒量级完成读写一个disk block。

sector 与 block

• sector 通常是磁盘驱动可以读写的最小单元，它过去通常是512字节

• block 通常是操作系统或者文件系统视角的数据

  • 它由文件系统定义，在XV6中它是1024字节
  • 所以XV6中一个block对应两个sector

fs 视角的磁盘读写

抽象磁盘为一堆 block，然后用inode参数调用接口即可

驱动会通过写设备的控制寄存器，然后设备就会完成相应的工作

fs：文件布局

• block 0 要么用作引导扇区，要么完全没用
• block 1 用于描述文件系统，存放fs元数据
• 在 XV 6中，log 从 block 2 开始，到 block 32 结束
• block32到block45之间，XV6存储了 inode
  • 一个inode是64字节，所有inode大小相同
  • 多个inode会打包存在一个block中
• 之后是bitmap block，只占据一个 block，跟踪 block 是否空闲
• data block，存储文件和目录

通常来说，bitmap block，inode blocks和log blocks被统称为metadata block。

它们虽然不存储实际的数据，但是它们存储了能帮助文件系统完成工作的元数据。

inode

这是一个64字节的数据结构，它的字段通常有：

• type、nlink、size
• 数据的 block numbers，分为 direct 和 indirect

Xv6 中，一个文件最大大小为：$(256+12)\times blocksize$，也即 268 KB

学生提问：为什么每个block存储256个block编号？

Frans教授：因为每个编号是4个字节。1024/4 = 256。这又带出了一个问题，如果block编号只是4个字节，磁盘最大能有多大？是的，2的32次方（注，4TB）。有些磁盘比这个数字要大，所以通常人们会使用比32bit更长的数字来表示block编号。

扩展文件大小

类似于页表的方式，顶级表包含一堆 indirect block 的 inode number，然后不断向下扩展即可

一个二级的结构可以支持 256*256*1 KB 大小的最大文件

也可以按照B树或者其他更复杂的树结构实现

block 计算

假设我们需要读取文件的第8000个字节，那么你该读取哪个block呢？从inode的数据结构中该如何计算呢？
s
8000 / blocksize = 7，因此 index 7；8000 % 1024 = 832，所以我们需要读取第7个block的第832个字节

目录

提供了层次化的命名空间（hierarchical namespace），你可以在文件系统中保存对用户友好的文件名。

Unix 中，一个目录本质上是一个文件加上一些文件系统能够理解的结构。

xv6 dirent

xv6 中这里的结构极其简单，每一个目录包含了directory entries，每一条 entry 被称为 dirent，其格式为：

ushort：2B，DIRSIZ：14

所以每个entry总共是16个字节。

路径名查找

inode从block 32开始

假设我们要查找路径名“/y/x”

1. 首先得到 root inode，xv6中其编号为1，则位于block 32的64到128字节的位置
2. 扫描它的内容，得到目录项，在目录项中匹配 y，得到y的 inum
3. 查找 inode y，得到其目录项，匹配x，得到其 inum

很明现，这里的结构不是很有效。为了找到一个目录名，你需要线性扫描。实际的文件系统会使用更复杂的数据结构来使得查找更快，当然这又是设计数据结构的问题，而不是设计操作系统的问题。你可以使用你喜欢的数据结构并提升性能。出于简单和更容易解释的目的，XV6使用了这里这种非常简单的数据结构。

code：xv6 fs

启动XV6的过程中，调用了makefs指令，来创建一个文件系统：

makefs创建了一个全新的磁盘镜像，在这个磁盘镜像中包含了我们在指令中传入的一些文件。

磁盘布局

从指令的下方可以看出有46个meta block，其中包括了：

• boot block
• super block
• 30 个 log block
• 13 个 inode block
• 1 个 bitmap block

之后是954个data block。所以这是一个袖珍级的文件系统，总共就包含了1000个block。

echo “hi” > x

这里会有几个阶段：

1. 第一阶段是创建文件
2. 第二阶段将“hi”写入文件
3. 第三阶段将“\n”换行符写入到文件

后两个操作即 echo 的实现方式：

创建文件阶段：

• 写入33：即写一个inode，它位于 block 33
  • 第一个是为了标记inode将要被使用，标记他的类型
  • 第二个write 33就是实际的写入inode的内容，会修改它的元数据
• 46：向第一个data block写数据
  • block 46是根目录的第一个block，我们此时在向根目录下写入文件，它的目录项变了
• 32：根目录的大小变了
• 33：再次更新了文件x的inode， 尽管我们没有写入任何数据

向文件写入“hi”：

• 45：更新位图
  • 此时fs已经找到了一个空闲的 data block，使用它存接下来的数据
• 595 x 2：写入 hi 和 \n
• 33：更新数据所在的block，和大小

创建 inode

分配inode发生在sys_open函数中，这个函数会负责创建文件。在sys_open函数中，会调用create函数。

1. create 函数中首先会解析路径名并找到最后一个目录，之后会查看文件是否存在，如果存在的话会返回错误。
2. 之后就会调用 ialloc（inode allocate），这个函数会为文件x分配inode
3. ialloc 会调用 bread 遍历所有可能的inode，寻找一个空闲的inode
   • 找到后将其type字段设置为文件，这会将inode标记为已被分配
   • bread 会调用 bget
4. bget 会获取bcache.lock，然后查看块缓存寻找目标块
   • 找到则引用++，释放bcache.lock，获取缓存块的锁，返回块指针
   • 未找到则

缓存锁与块锁

进程可能并行运行，两个进程可能同时会调用到ialloc函数，然后进而调用 bread，bread 调用 bget

bget 返回一个带锁的缓存块，意味着进程可以独占并修改此缓存块，而无需担心其他进程的影响。

• 一个磁盘block只能有一个缓存

缓存块是进程唯一写入磁盘的方式。如果buffer cache中有两份block 33的cache将会出现问题，可能出现更新丢失的问题。所以必须带锁

另外 XV6 中对bcache做任何修改的话，都必须持有bcache的锁

brelse

如果第一个进程结束了对block 33的读写操作，它会对block的cache调用brelse（block cache release）函数

这个函数会对refcnt减1，并释放sleep lock

• 如果引用为0，还会撤回这个 block，其策略为 LRU
• LRU是一个良好的策略，它遵循了局部性原理

sleep lock

block cache使用的是sleep lock。

sleep lock是基于spinlock实现的。

• 磁盘操作需要很长的时间，spinlock 会浪费大量时间在轮询上，所以使用了 sleeplock
• 另外，sleep lock 还允许在 I/O 过程中持有锁，在开启中断的情况下”持有锁“