28. 文件系统

文件系统

文件 = struct file_operations

数据文件：hello.c, a.out, …
- 虚拟的磁盘
- vector
设备驱动
- null, nuke0, …
虚拟文件
- 进程的地址空间, …

新需求：怎么管理系统中众多的文件？

find_file_by_name?

管理文件

文件那么多，怎么找到想要的？

信息的局部性：将虚拟磁盘 (文件) 组织成层次结构

思路：信息的局部性

树状层次结构

.
└── 学习资料
    ├── .学习资料(隐藏)
    ├── 问题求解1
    ├── 问题求解2
    ├── 问题求解3
    ├── 问题求解4
    └── 操作系统

麻烦的是 “非数据” 的文件

UNIX/Linux: Everything is a File

一切都在 “/” 中 (例子：中文语言包, fstab)

Windows 的设计

一个驱动器一棵树：A:, B:, C:, …
其他命名空间：Windows Driver Model, Registry
- (也可以 “everything is a file”)

HANDLE hDevice = CreateFile(
    "\\\\.\\PhysicalDrive0",
    GENERIC_READ | GENERIC_WRITE,
    FILE_SHARE_READ | FILE_SHARE_WRITE,
    NULL, OPEN_EXISTING, 0, NULL
);

UNIX 的设计：目录树的拼接

mount: 将一个目录解析为另一个文件系统的根

mount(source, target, filesystemtype, mountflags, data);

再看 “最小 Linux”
- 初始时只有 /dev/console 和几个文件
- /proc, /sys, 甚至 /tmp 都没有
  - 答案：它们都是 mount 系统调用创建出来的
UNIX 一贯的设计哲学：灵活
- Linux 安装时的 “mount point”
  - /, /home, /var 可以是独立的磁盘设备

Quiz

如何挂载一个 filesystem.img?

一个微妙的循环
- 文件 = 磁盘上的虚拟磁盘
- 挂载文件 = 在虚拟磁盘上虚拟出的虚拟磁盘
镜像

Linux 的处理方式

创建一个 loopback (回环) 设备

设备驱动把设备的 read/write 翻译成文件的 read/write
drivers/block/loop.c
- 实现了 loop_mq_ops (不是 file_operations)

观察挂载文件的 strace

lsblk 查看系统中的 block devices (strace)
strace 观察挂载的流程
- ioctl(3, LOOP_CTL_GET_FREE)
- ioctl(4, LOOP_SET_FD, 3)

Filesystem Hierarchy Standard

我们看到的目录结构

FHS enables software and user to predict the location of installed files and directories.
- 例子：macOS 是 UNIX 的内核 (BSD), 但不遵循 Linux FHS

文件系统 API: 目录管理

mkdir

rmdir

删除一个空目录
没有 “递归删除” 的系统调用
- rm -rf 会遍历目录，逐个删除 (试试 strace)

getdents

返回 count 个目录项 (ls, find, tree 都使用这个)
- 更友好的方式：globbing

硬 (hard) 链接

需求：系统中可能有同一个运行库的多个版本

libc-2.27.so, libc-2.26.so, …
还需要一个 “当前版本的 libc”
- 程序需要链接 “libc.so.6”，能否避免文件的一份拷贝？

(硬) 链接：允许一个文件被多个目录引用

文件系统实现的特性 (ls -i 查看)
- 不能链接目录、不能跨文件系统
- 删除文件的系统调用称为 “unlink” (refcount–)

软 (symbolic) 链接

软链接：在文件里存储一个 “跳转提示”

软链接也是一个文件
- 当引用这个文件时，去找另一个文件
- 另一个文件的绝对/相对路径以文本形式存储在文件里
- 可以跨文件系统、可以链接目录、……

几乎没有任何限制

类似 “快捷方式”
- 链接指向的位置不存在也没关系
- (也许下次就存在了)

文件系统：实现

文件系统实现

文件的实现

文件 = “虚拟” 磁盘
API: read, write, ftruncate, …

目录的实现

目录 = 文件/目录的集合
API: mkdir, rmdir, readdir, link, unlink, …

mount 的实现

最好由操作系统统一管理 (而不是由具体的文件系统实现)

数据结构

借助 RAM 自由布局目录和文件

文件系统就是一个 Abstract DataType (ADT)

class FSObject {
}; 

class File: FSObject {
  std::vector<char> content; 
}; 

class Directory: FSObject {
  std::map<std::string, FSObject*> children; 
};

操作系统

对不起，没有 Random Access Memory

我们只有 block device
两个 API
- bread(int bid, struct block *b);
- bwrite(int bid, struct block *b);

实现：

read, write, ftruncate, …
mkdir, rmdir, readdir, link, unlink, …
- 用 bread/bwrite 模拟 RAM → 严重的读/写放大
- 我们需要更适合磁盘的数据结构

我们的敌人和朋友

敌人：读/写放大

被迫读写连续的一块数据

朋友：局部性 + 缓存

适当地排布数据，使得临近的数据有 “一同访问” 的倾向
数据暂时停留在内存，延迟写回

FAT 和 UNIX 文件系统

让时间回到 1980 年

5.25" 软盘：单面 180 KiB

360 个 512B 扇区 (sectors)
在这样的设备上实现文件系统，应该选用怎样的数据结构？

需求分析

相当小的文件系统

目录中一般只有几个、十几个文件
文件以小文件为主 (几个 block 以内)

文件的实现方式

struct block * 的链表
- 任何复杂的高级数据结构都显得浪费

目录的实现方式

目录就是一个普通的文件 (虚拟磁盘；“目录文件”)
操作系统会对文件的内容作为目录的解读
- 文件内容就是一个 struct dentry[];

用链表存储数据：两种设计

在每个数据块后放置指针

优点：实现简单、无须单独开辟存储空间
缺点：数据的大小不是 $2^k$ ; 单纯的 lseek 需要读整块数据

将指针集中存放在文件系统的某个区域

优点：局部性好；lseek 更快
缺点：集中存放的数据损坏将导致数据丢失

哪种方式的缺陷是致命、难以解决的？

集中保存所有指针

集中存储的指针容易损坏？存$n $份就行！

FAT-12/16/32 (FAT entry，即 “next 指针” 的大小)

“File Allocation Table” 文件系统

RTFM 得到必要的细节

诸如 tutorial、博客都不可靠
还会丢失很多重要的细节

if (CountofClusters < 4085) {
  // Volume is FAT12 (2 MiB for 512B cluster)
} else if (CountofCluster < 65525) {
  // Volume is FAT16 (32 MiB for 512B cluster)
} else {
  // Volume is FAT32
}

FAT: 链接存储的文件

“FAT” 的 “next” 数组

0: free; 2… MAX: allocated;
ffffff7: bad cluster; ffffff8-ffffffe, -1: end-of-file

以普通文件的方式存储 “目录” 这个数据结构

FAT: 目录 = 32-byte 定长目录项的集合
操作系统在解析时把标记为目录的目录项 “当做” 目录即可
- 可以用连续的若干个目录项存储 “长文件名”
思考题：为什么不把元数据 (大小、文件名、……) 保存在vector<struct block *> file 的头部？

Talk is Cheap, Show Me the Code!

首先，观察 “快速格式化” (mkfs.fat) 是如何工作的

老朋友：strace

然后，把整个磁盘镜像 mmap 进内存

照抄手册，遍历目录树 (fat-tree demo)，试试镜像

另一个有趣的问题：文件系统恢复

快速格式化 = FAT 表丢失
- 所有的文件内容 (包括目录文件) 都还在
- 只是在数据结构眼里看起来都是 “free block”
猜出文件系统的参数 (SecPerClus, BytsPerSec, …)，恢复 next 关系

FAT: 性能与可靠性

性能

＋ 小文件简直太合适了
－ 但大文件的随机访问就不行了
- 4 GB 的文件跳到末尾 (4 KB cluster) 有 $2^20$ 次 next 操作
- 缓存能部分解决这个问题
在 FAT 时代，磁盘连续访问性能更佳
- 使用时间久的磁盘会产生碎片 (fragmentation)
- malloc 也会产生碎片，不过对性能影响不太大

可靠性

维护若干个 FAT 的副本防止元数据损坏 (额外的开销)

想要一个更好的文件系统？

不能 “尽善尽美”，但可以在 “实际 workload” 下尽可能好

Summary	Findings
Most files are small	Roughly 2K is the most common size
Average file size is growing	Almost 200K is the average
Most bytes are stored in large files	A few big files use most of the space
File systems contains lots of files	Almost 100K on average
File systems are roughly half full	Even as disks grow, file systems remain ~50% full
Directories are typically small	Many have few entries; most have 20 or fewer

ext2/UNIX 文件系统

按对象方式集中存储文件/目录元数据

增强局部性 (更易于缓存)
支持链接

为大小文件区分 fast/slow path

小的时候应该用数组
- 连链表遍历都省了
大的时候应该用树 (B-Tree; Radix-Tree; …)
- 快速的随机访问

ext2: 磁盘镜像格式

对磁盘进行分组

“superblock”：文件系统元数据

文件 (inode) 数量
block group 信息
- ext2.h 里有你需要知道的一切

ext2 目录文件

与 FAT 本质相同：在文件上建立目录的数据结构

注意到 inode 统一存储
- 目录文件中存储文件名到 inode 编号的 key-value mapping

ext2: 性能与可靠性

局部性与缓存

bitmap, inode 都有 “集中存储” 的局部性
通过内存缓存减少读/写放大

大文件的随机读写性能提升明显 $(O(1))$

支持链接 (一定程度减少空间浪费)
inode 在磁盘上连续存储，便于缓存/预取
依然有碎片的问题

但可靠性依然是个很大的问题

存储 inode 的数据块损坏是很严重的

把文件系统理解成一个 “数据结构”，就不难分析其中的重点和实现要点——我们总是把数据按照局部性组织起来，无论是 FAT 还是 bitmap/inode 的设计，都利用了这一点。另一个重要的设计是 “目录也是文件”——文件系统实现将目录文件中的数据作出解读，从而解析出其中的目录结构。