参考文献

Operating System - Three Easy Pieces

stack overflow

概述

在 Windows 下, 常用的文件系统就是 NTFS (网龄稍微大一点的会知道 FAT32), 所以 Windows 用户 对文件系统通常没有太大的印象.

而 Linux 用户经常会听到 ext4, btrfs, zfs, yaffs 等名词, 如果不懂文件系统的概念的话, 那就很尴尬了.

最近在研究 zfs, 因此具体地了解了一下文件系统. 这篇文章主要是对文件系统的一个整体概念澄清, 以及一些设计的解释. 但是不会涉及任何具体的文件系统. 硬要说的话, 是基于第一个参考文献的.

为什么要有文件系统

一个例子: 近代的留声机影碟.

任何看过近代电影的人都知道, 影碟是一种存储信息的介质, 其中存储的是音乐. 只要把影碟放到留声机上, 拨好播放头 (似乎叫唱针). 基座带动影碟旋转, 唱针划过影碟表面, 然后留声机就将影碟中存储的音乐播放出来.

现代磁盘

(当然近几年固态硬盘已经发展起来, 但是我这种穷鬼并没有在 PC 上实际使用过). 磁盘中也存储着信息, 这个信息不只是音乐, 还可能是图片小说甚至游戏程序. 把磁盘插进主板上的插槽, (假设其他东西调教好了之后), 打开电脑, 这块磁盘中的信息就可以被读取了.

一些区别

磁盘相对近代的影碟, 有什么区别呢? 这篇文章当中, 只考虑如下几个区别

  1. 普通用户使用磁盘的时候, 都是通过 “文件”, “目录” 等抽象的概念来操作的. 而影碟上面, 只是一个信息流 (unsegmented information flow), 不可能有 part1.mp3, part2.mp3 之类的.

  2. 我们使用磁盘的时候, 一般都能看到 “文件” “目录” 的元信息, 比如文件的大小, 上次访问的时间, 文件的保护权限等等. 影碟不会有这些.

磁盘 (magnetic disk)

从底层开始, 在磁盘这个介质上, 信息是怎么存储的? 只总结一下机械磁盘, 固态硬盘我并不了解.

不过可能这里让读者失望, 研究文件系统并不需要关注磁盘上信息具体是什么存储的. 而且我也不知道是怎么存储的, 因为物理课考完后 “磁滞效应” 之类的概念就永远地从我的大脑里面消失了.

磁盘的结构如下图所示

disk-structure

来源: Figure 10.1 - Moving-head disk mechanism.

扇区

扇区 (sector) 是硬件上访问磁盘的最小信息单元. 每个扇区都有一个扇区号, 就像 “0号扇区”, “1号扇区” 这种. 我们靠扇区号来指代一个扇区. 就像用 i 来指代 a[i].

不然我们想给别人说我们心里想的是哪一个扇区的时候, 就要把磁盘拿出来, 拿着一个针指着上面某个位置说 “这个扇区!” “不, 不是那个, 是这个扇区!”, 做出这种愚蠢的行为别人才能知道你想说那个扇区. 不过这种愚蠢的行为倒是有点类似用 *p 来指代 a[i].

注意扇区和块 (block) 是不同的概念, 块是操作系统 / 文件系统读取磁盘的最小单元. 块的大小通常是扇区的多倍. 块也有块号, 也用来唯一指代是哪个块.

磁盘上数据的访问

访问磁盘某扇区包含的信息需要三步

  1. 寻道: 将磁头放到正确的道上 (track)
  2. 旋转: 旋转磁盘, 使得磁头指向要访问的扇区
  3. 读取数据: 从这个扇区读出数据

很显然, 在这样的模型中, 顺序访问要比随机访问快很多.

操作系统应当认为磁盘上数据的访问是异步的, 完成时间是毫秒甚至数十毫秒级别的.

其他

首次阅读时, 这些可以略过.

磁盘调度

实践中, 磁盘访问不是有了就执行. 可能会等待一段时间, 看有没有新的磁盘访问能和这个访问合并 (如访问同一个扇区中的数据). 这种行为成为磁盘调度, 它能降低平均相应时间, 以及减轻磁盘负载.

调度有软件层面和硬件层面的.

驱动

驱动负责隔离磁盘的物理, 机械, 电气特性, 如控制信号的电压和时序等, 向上层软件 (如文件系统) 提供一个硬件无关的模型.

驱动提供的磁盘的模型

可以将磁盘看成一个非常大的数组, 而且断电不丢失数据 (当然是正常断电的情况). 并且这个数组的元素是 sector 而非 unsigned char, 一次访问也只能访问一个 sector.

struct sector {
    unsigned char data[512];    // 通常一个扇区是 512 字节
};

struct disk {
    struct sector sectors[2*1024*1024*500];     // 500 G 磁盘
} my_disk;

无论是 Kingston 还是 Seagate 或者美帝良心想的磁盘, 经过驱动的包装, 都提供的是这么一个简单的模型.

顺便, 前面说的留声机影碟就在这个层次, 只不过它可能没有最小访问单元是扇区的限制.

文件系统

文件系统建立在驱动之上, 驱动又在硬件之上. 这就类似于网络协议栈使用了分层技术.

文件系统不直接访问磁盘, 而是通过驱动提供的模型和接口来访问磁盘, 因此是硬件无关的.

文件系统提供的功能

现代磁盘至少应该提供的功能是

  1. 文件 (不同信息块之间的隔离)
  2. 目录 (树状存储)
  3. 元信息 (最后访问时间, 保护权限, 大小和实际使用大小…)

高级一点的可能还有

块 (block)

块是文件系统层面访问磁盘的最小单位, 文件系统看磁盘看到的是一个 struct block[].

块大小是扇区的整数倍, 而且 (我觉得应该) 是页的整数分之一倍. 据我所见, 块大小基本都是 4KB. 块越小, 意味着同样的磁盘上有更多块, 也就意味着需要存储的元信息就更多. 至少某块是否空闲这个元信息是更多的. 而块越大, 存储小文件浪费了数据块的空间. 不过我的观点时, 块大小等于页大小是最好的, 简化虚拟内存的设计.

下面是块的不同种类.

空闲块

就是不包含任何信息的块, 可以随时被文件系统征用.

数据块

文件系统总要保存用户数据吧? 所以有一种块叫数据块, 其中保存用户数据.

inode 块

我们想要维护文件元信息, 而且断电之后还不能丢失. 不然某人偷看了你的小电影之后重启一下就能销声匿迹, 因为最后访问时间就被清空了. 所以文件的元信息总要放到磁盘上吧? 存放这些元信息的块就是 inode 块.

inode 又是什么? 每个文件都有一个 inode, 它是该文件系统中这个文件的唯一句柄 (unique handle), 其中保存了文件的元信息 (使用 stat 命令查看), 包括.

我们用 inode 号 (inumber) 来指代 inode, 所以 inode 号是文件的唯一标志.

超级块

再来我们有充足的理由保存文件系统自身的元信息. 比如它是什么文件系统, ext4 还是 zfs?

块的布局

上面说了我们需要的几种块. 然而, 一个问题是, 给定某个块号, 我们怎么知道这个块是哪种类型的?

这个问题的解决方法显然是多样的, 文件系统为了简单可能采用固定分配的方法:

文件系统的实现

文件的实现

文件的数据块里边, 当然是保存文件的内容.

要访问一个文件, 假设已知他的 inode 号. 那么

  1. 找到对应的 inode, 通常 inode 在 inode 块里面是顺序存放的, 因此可以直接由 inode 号得到对应 inode 的位置 inode 里面记录了这个文件的数据放在那些数据块里面. 然后访问这些数据块就好了. 当然不要忘记修改 inode 里面这个文件的最后访问时间.

但是, 给定文件名, 如何寻找其 inode 号呢? 在没有目录的情况下 (比如早期的 DOS), 这个问题还是比较解决的, 方法也显然是多样的,

目录的实现

*nix 中, 目录也是文件, 由 inode 唯一指代, 也占据数据块.

In Unix, everything is a file.

但是目录的数据块中, 应当保存

  1. 目录中每项的名字
  2. 目录中每项的 inode 号

类似

data block for directory /home/stupid/stupid_program
========================
name            inode_no
------------------------
.               100
..              87
test.c          125
CMakeLists.txt  199
build/          124

(这个例子中也描述了如何处理目录嵌套目录的方法)

另外, 目录应当和普通文件区分开. 不然用户打开目录, 看到上面的内容将会一头雾水. 因此目录在它的元信息 (即 inode) 中应当包含一条 “我是目录”.

这样文件系统在执行目录 (是的 cd xxx/ 是执行 xxx/, 需要执行权限) 的时候就知道, 执行的不是普通的可执行文件, 而是要进入这个目录.

在有目录的时候, 从文件名 / 目录名的映射机制显然只需要一个树遍历即可. 但是这就牵扯到一个问题: 根目录 “/” 作为遍历的起点, 其 inode 号是多少? 解决方案愚蠢有效, 直接要求根目录的 inode 号就是 2. 这个的解释可以看 stack overflow.

符号链接的实现

有了上面讨论, 任何一个有正常思维的人也能知道符号链接实现大致是什么样的了. 这也是一个简单的练习.

其他

mkfs

mkfs DEV 用来格式化 DEV 代表的设备 (磁盘, 或者可能是虚拟磁盘 – 循环文件). mkfs 就是向磁盘中写入一些信息, 在磁盘上构建起一个新的文件系统 – 一般是不包含任何文件的. 实际中我们是使用 mkfs.ext4, mkfs.btrfs 之类的.

mount

mount DEV MNTPT 之后, cd MNTPT 实际上是进入 DEV 的根目录, 当然这要求 DEV 已经被正确地格式化, 包含某个当前内核能够识别的文件系统.

概念