Blog Sketch

使用 FUSE 创建一个用户空间文件系统

这是我再次阅读、重新构建并调试修改一个之前做过的项目时所做的笔记。因此，本文主要包括原理介绍、重新编译和运行项目的步骤、代码解析、以及这一次所修改的内容。

项目本身：

关于 FUSE

FUSE (Filesystem in USEr space)，即用户空间文件系统，是一个类 Unix 操作系统中的一个软件接口。它允许用户在不修改内核的情况下、在用户空间创建自定义的文件系统。Linux 通过内核模块（Kernel Module）来支持 FUSE。

Github上的 libfuse 仓库（依据其 Readme）包括 1）内核模块的实现，和 2）在用户空间与内核模块通信的代码库。主流的 Linux 发行版都默认包含 libfuse 代码库。

编译与运行 fischl 文件系统

观察代码仓库的基本结构

fischl 文件系统由 C++ 语言编写，利用 CMake 构建系统。CMake 系统是这样引入 FUSE 的：

# Use pkg-config to get flags for fuse3
find_package(PkgConfig REQUIRED) # 保证 PkgConfig 工具存在
pkg_search_module(FUSE3 REQUIRED fuse3) # 寻找 fuse3 包，并创建名称为 FUSE3 的模块，记录相关信息（包括 FUSE3_INCLUDE_DIRS, FUSE3_LIBRARIES）

# Add the flags from pkg-config for fuse3
target_include_directories(fischl PRIVATE ${FUSE3_INCLUDE_DIRS}) # 编译时需要包含 fuse3 的头文件
target_link_libraries(fischl PRIVATE ${FUSE3_LIBRARIES}) # 需要链接到 fuse3 的库

事实上，fischl 的 main 函数在做了一系列准备工作之后，最终将控制流交给 fuse 函数库的 main 函数：

#include <fuse.h>
...
// in main:
ret = fuse_main(args.argc, args.argv, &fischl_oper, NULL); // 通过 fischl_oper 传入我们实现的诸多文件系统调用 
fuse_opt_free_args(&args);
return ret;

我们实现的诸多文件系统调用，如 mknod, mkdir, open, read, write，最终是要落实到块设备上的，比如 rawdisk.cpp 中的：

// fd is a class variable of RealRawDisk
// in RealRawDisk::RealRawDisk(const char *directory), we have
fd = open(dir, O_RDWR); // Open the block device (an actual device such as /dev/sdX)
...
ssize_t bytesRead = read(fd, buffer, IO_BLOCK_SIZE);
ssize_t bytesWritten = write(fd, buffer, IO_BLOCK_SIZE);

编译和运行代码仓库

如 Readme 中所说，编译的命令是：

mkdir -p build && cd build
cmake ..
make # cmake --build . is same

运行的方法是：

./fischl diskpath n -s mountpoint # 格式化块设备，在块设备上创建新的 fischl 文件系统
./fischl diskpath l -s mountpoint # 假设块设备中已经有一个 fischl 文件系统，去加载它
# -s 是传给 fuse3 的参数，保证我们的文件系统仅被单线程访问
# 如果你是非 root 用户并遇到了形如 "cannot access 'mountpoint': Permission denied" 的报错，在 n/l 之后加入参数 -o allow_other

这样，利用 diskpath 指向的块设备实现的文件系统就被挂载在 mountpoint 上了。

要查看 path 是否已经是挂载点，可以运行命令 mountpoint path 。

编译过程中报错的可能解决方式

请事先保证 cmake, g++, pkg-config 包已被安装（如果你的 Linux 系统长期未用，应该用类似 apt-get update 的命令更新包列表，避免安装包时发生相关错误）

fuse3 not found

遇到报错 “Package fuse3 was not found in the pkg-config search path.” 或者 “None of the required ‘fuse3’ found”，可以先尝试执行 pkg-config --modversion fuse3，直到该命令无错为止。

在 Ubuntu 20.04 上，可能需要安装如下包： sudo apt-get install libfuse3-dev 。如果仍未找到，可能需要手动将 fuse3.pc 的路径添加到 PKG_CONFIG_PATH：

find /usr -name fuse3.pc
export PKG_CONFIG_PATH=/usr/lib/x86_64-linux-gnu/pkgconfig:$PKG_CONFIG_PATH # Change to the actual path
Googletest 子文件夹为空

googletest 是一个 fischl 仓库的一个 git 子模块。它最初是通过 git submodule add https://github.com/google/googletest.git 添加的，可以通过运行 git submodule 命令查看当前仓库包含的所有子模块。

如果你在最初 clone 仓库时，没有使用 --recurse-submodules 选项，子模块不会自动克隆。对此可以通过 git submodule init 和 git submodule update 来 clone googletest 子模块。

可选地用 Loop 设备作为块设备

如果你的运行环境不方便使用外设存储设备或者真正的磁盘分区作为块设备，可以考虑创建一个 Loop 设备（参考）作为块设备来运行 fischl 文件系统。

Loop 设备可以使得文件像设备一样被访问。创建一个 50 MB 的设备文件：dd if=/dev/zero of=/loopfile bs=1024 count=51200。

用 losetup -f 找到第一个可用的 loop 设备编号，如 /dev/loop1 。将其绑定到设别文件上：losetup /dev/loop1 /loopfile 。随后，就可以列出所有 Loop 设备，确认刚才创建的 Loop 设备可用了：losetup -a 。要取消 Loop 设备和文件的绑定，losetup -d /dev/loop1。

程序调试方法

输出 FUSE help 的方法是：./fischl diskpath l --help，从而看到 fuse 的选项，包括但不限于

    -h   --help            print help
    -V   --version         print version
    -d   -o debug          enable debug output (implies -f)
    -f                     foreground operation
    -s                     disable multi-threaded operation

因此，调试的方法是 ./fischl diskpath l -d -s mountpoint。

内核和进程眼中的文件系统

内核中包括三种文件系统打开表（参考 USNA 的 Unix Filesystem 教程）：

  • 最底层的，Vnode Table，即每个打开的文件对应一个表项，表项拷贝了外存中文件的 inode 等信息。有引用计数
  • 中间层的，Open File Table，即每个与文件进行的连接(“connection”)。多个进程（如 fork 创造的父子进程）可能共用一个连接，这个连接需要储存读写位置的偏置 offset 和引用计数
  • 最表层的，File Descriptor Table, 每个进程都对应一份。它把暴露给用户空间进程的文件描述符 File Descriptor 映射到 Open File Table 的下标。

注意，这三层结构都在内核空间，是用户不能访问的。

举例说明三张表的运行逻辑：

  • 如果对同一个设备文件或普通文件建立了一个新连接（如一个新进程打开了目标文件），那么 Open File Table 就会出现一个新表项，Vnode Table 对应表项的引用计数会加一。
  • 如果打开了目标文件的进程调用了 fork，子进程继承了父进程的连接（父子进程共用一个既有连接），那么 File Descriptor Table 就会出现一个新表项， Open File Table 对应表项的引用计数要加一。
  • 注意，这两个引用计数和 inode 内的引用计数是分开的，inode 中的引用计数会因为硬链接而增加。前者是内核数据结构的一个 field，后者是硬盘上 inode 的一个 field。

内核中的三张表，FUSE 的库都已经帮我们实现好了，fischl 不需要实现。

Fischl 文件系统代码解析

Fischl 文件系统使用了分层设计的方法，每一层调用其下一层的提供的接口和服务，为其上一层提供接口和服务

块设备读写层

源文件：rawdisk.hpp

接口：读 / 写第几块

提供以块（被指定为 IO_BLOCK_SIZE=4096 个字节）为单位读写块设备的接口：

virtual int read_block(u_int64_t block_number, char *buffer) = 0;
virtual int write_block(u_int64_t block_number, char *buffer) = 0;

RealRawDisk 提供依块设备名称来构造的方法：

RealRawDisk(const char *directory);

构造函数中，使用 open 来打开块设备文件，使用 ioctl （BLKGETSIZE64 参数）来获知磁盘可用的字节数。

读写时，首先使用 lseek 将读写位置移动到正确的位置，然后使用 read 或 write 系统调用。

文件系统存储资源分配层

源文件：
fs.hpp, fs/{fs_data_types, inode_manager, datablock_manager}.hpp
fs/{fs, fs_data_types, inode_manager, datablock_manager}.cpp

接口：
分配一个 Inode，回收第几个 Inode，读第几个 Inode，写第几个 Inode
分配一个 DataBlock，回收第几个 Datablock，读第几个 Datablock，写第几个 Datablock

ext4 类的文件系统的底层结构主要包括 Superblock，inode list 和 datablock。这三部分在磁盘上顺序排列，构成了一个文件系统。

Superblock, Inodes, datablocks

简要地说，Superblock 占用磁盘上文件系统的第一个块（最容易找到），存储文件系统的一些元信息，比如有 Inode 数组有多长 / 有多少个 Inode，有多少个 Datablock 等等；Inode list 是一个固定长度的数组，每个元素是一个 Inode，负责一个文件的索引（这个数组有多长，文件系统就最多支持多少个文件）；Datablocks 负责存储用户创建的文件内容本身。

本层需要处理 Inode 和 Datablocks 的创建（分配）和删除，因此关键任务是记录哪些 Inode 和 Datablocks 是未分配的。对于 Inode 来说，这个问题比较简单，只需要在每个元素中加入一个域来记录当前 Inode 被占用或空闲即可。对于 Datablocks 来说，这个问题更复杂，因为我们默认把每个 Datablock 的全部空间用来记录用户指定的内容，没有空间记录 Datablock 的已分配未分配状态。

Free list 的概念

可以使用名为“空闲链表“ (Free List) 的数据结构来解决该问题：在每个未分配的块（无论 Inode 还是 Datablock）中，记录下一个未分配块的地址；在 Superblock 中，记录第一个未分配块的地址（head）。要分配块 / 删除空闲块，就把 head 分配出去，让 head 指向下一个空闲块；要回收块 / 插入空闲块，就让它记录指向 head 原先的地址，让 head 指向它。

INODE_MANAGER_FREELIST

INode_Manager_Freelist 类使用了上述机制来快速分配和删除 Inode。其中的函数，format 负责了空闲链表的初始化，free_inode 负责回收 Inode，new_inode 负责分配 Inode。如果阅读代码，有如下细节：

  • 我们指定 INODE_SIZE=512，所以一个磁盘块中可以存 8 个 Inode。通过 get_block_num 和 get_block_offset 来将 Inode 编号转换为该 Inode 在磁盘上的第几块和起始位置。
  • head 及每个空闲链表元素中存储的“地址”实际上是 Inode 编号，它的数据类型为 u_int64_t，占用 8 个字节。
  • head 是从 superblock 在内存中的缓存（SuperBlock_Data 类）读取的，而改变 head 时，必须通知 SuperBlock_Data 将内存中的数据写回磁盘（利用 save_inode_list_head 函数）
DATABLOCK_MANAGER_BITMAP

尽管我们把 Datablock 中的全部空间用于记录用户数据，但我们可以将 Datablock 内部再分出一个层级：每 2048 个 Datablock 中，有一个块（称为 Bitmap Block）专门作为剩下 2047 个 Datablock 的 bitmap，记录它们当中哪些被分配了。只有 Bitmap 块会被我们挂上空闲链表。

  • 初始化方法很简单，每 2048 个 Datablock 中，初始化其中的第一块也就是 Bitmap 块：在块的开头记录下一个 Bitmap 块的下标（磁盘上的第几块？），块的其余部分（8 字节后）置 0，代表 Bitmap 中全部数据块空闲。将首个 Bitmap 块的下标（head）记录在 Superblock 中。
  • 检查 Bitmap 的最靠左的空闲数据块的函数是 BitmapBlock_Data::find_unfilled，它在有空闲数据块时返回其下标（1..2047，因为第 0 块是 Bitmap Block 不是数据块），在没有空闲数据块时返回 0。
  • 分配数据块的函数是 DataBlock_Manager_Bitmap::new_datablock。它会找出 head 指向的 Bitmap 块，从其最左侧分配一个数据块出来，然后检查 2047 个数据块是否全部被占用了，如果是则将 head 向“前”移动一次，保证 head 指向的 Bitmap 块始终有可用的数据块。
  • 回收数据块的函数是 DataBlock_Manager_Bitmap::free_datablock。函数根据传入的数据块下标找出管理它的 Bitmap 块。如果该 Bitmap 先前没有空闲的数据块，则将它挂上空闲链表，并更新 Superblock 中的 head。不论哪种情况，都更新 Bitmap 标注该数据块空闲。

单文件操作层

源文件：
fs.hpp, fs/fs_file_io.cpp

接口：对于第几个文件（Inode），

  • 从 offset 开始读取 count 个字节
  • 从 offset 开始写入 count 个字节
  • 将文件截断到 count 个字节

这一层把 Datablock 的概念隐藏了，抽象为对文件的读写。这关系到 “Inode 如何充当文件内容的索引” 的问题。Inode 中显然需要存储数据块的编号：有的数据块内存储的就是文件内容本身，这些数据块被称为“直接块” (Direct Blocks)；有的数据块内存储的是一张直接块的编号构成的列表，称为“一级间接块”（Single Indirect Blocks）；有的数据块内存储的是一张一级间接块的编号构成的列表，称为“二级间接块”，同理还有“三级间接块”，这是一个层级的结构。

Inode 中存储若干直接块、一个一级间接块、一个二级间接块、一个三级间接块，按顺序“遍历”它们，就相当于按顺序读取了文件的字节流。

具体到代码层面：

  • 将我们操作参数记录在 DatablockOperation 类中，成员变量包括 count, offset, 成功执行的字节数，数据缓冲区。将它的实例作为参数传入一个名为”扫描”或者“遍历” (sweep) 的函数中，该函数在执行所需操作的同时更新 inode 和间接块中与索引相关的内容。
  • 事实上，无论读、写还是截断文件（删除某个数据块后的所有数据块），都需要进行层次遍历。负责遍历单个 Datablock 的函数为 DatablockOperation 的虚函数 operation，若发生错误则返回负数，若整个操作刚好在这个数据块结束则返回 0，若整个操作还未结束则返回 1。
  • 读、写、截断函数直接调用的是 sweep_inode_datablocks 函数，它的流程为，按照 [直接块1, …, 直接块k，一级间接块，二级间接块，三级间接块] 的顺序，只要操作涉及该地址下辖数据块（通过 offset 判断），将地址、间接层数作为参数，调用 sweep_datablocks 函数，直到出错或操作结束。
  • sweep_datablocks 函数会调用 DatablockOperation::operation，因此返回值也代表错误（-负数）、刚好结束（0）、仍应继续（1）。如果间接层数为 0（直接块），则直接调用 operation；如果间接层数大于 0，则按 8 字节为单位取出本 datablock 中的地址的引用（若本 datablock 的地址为 0 即不存在，则创建并将内容全部置 0，即地址向量最初为空），递归地调用 sweep_datablocks 函数（间接层数减一）

sweep_datablocks 函数中个人有疑问的几点：

  • 第三个参数，即 u_int64_t start_block_index，似乎并没有被使用，可以删去
  • 有几处判断 result = op->operation(*block_num, &delete_block) < 0 才返回 (return result)，改成 <= 0 似乎也可以并且语义上更清晰（不需要继续就返回），且和 sweep_inode_datablocks 中的写法保持一致
  • fs 类的 lseek_next_data, lseek_next_hole 似乎没有被使用，DO 类中的 skip 函数指针作用并不清楚

文件系统顶层接口层

源文件：
files.h, fischl.h
files.cpp, fischl.cpp

接口：FUSE 定义的 high-level API 接口，为一系列函数，它们的规约在libfuse/include/fuse.h 中定义
getattr, mkdir, rmdir, mknod, link, unlink, symlink, readlink, rename, truncate, chmod, chown, open, read, write, statfs, release

文件系统暴露给用户的接口不是通过 INODE 访问文件的，而是通过字符串类型的“路径”，从“树根”开始，经过若干级文件夹，到达文件。文件夹是一种特殊的文件（其特殊类型在 Inode 内被标注出来），它在每个数据块中存储的内容是一张 子文件名 对应 Inode 编号的表。

软链接是一种特殊的文件类型（其特殊类型在 Inode 内被标注出来），在文件内存储另一个文件的路径以“指向”那个文件；硬链接就是两个路径指向同一个 inode 的现象（由于引用是带方向的，所以不会导致文件系统中出现环路）。软链接不会改变被指 Inode 的引用计数，硬链接会增加被指 Inode 的引用计数；通过路径删除文件后，软链接会失效，而硬链接不会失效（另一条路径仍然可以访问文件）。

getattr

依据文件路径查询文件属性，与系统调用 stat() 类似。函数内首先通过 namei 将文件路径转换为 Inode 编号，然后依据 Inode 元信息中的 Permissions 位检测它是否是 1）文件夹，2）软链接（symlink）还是 3）其它文件，然后分类处理。

注意，文件的 mode 包含两部分信息：第一是文件类型（文件夹？软链接？字符设备？块设备？管道？套接字？），第二是文件的权限位

readlink

阅读文件路径指向的软链接，将其存储的文件路径读到传入的 buf 中。

mknod, mkdir, symlink

三个操作都是创建文件：mkdir 创建文件夹、symlink 创建一个软链接，mknod 创建其它文件。通用的流程是，找到父文件夹的 inode，在其下寻找是否有同名文件，如果没有，则创建新文件。最后，父在文件夹中创建对应表项。

对于 symlink，要向该文件内写入被指文件的路径。

对于文件夹，要在新建的文件夹中创建文件名为 “.” 和 “..” 文件，指向当前文件夹和父文件夹

unlink, rmdir

可以简单地理解为删除文件或删除文件夹，实质上是删除路径对文件的引用，所以在有硬链接引用计数大于 1 的情况下路径指向的 inode 未必被删除。

unlink 和 rmdir 的函数实现几乎一模一样：首先删除父文件夹中的记录，然后调用内部函数 unlink_inode (inode_number) ，该函数的作用是

  • 若 Inode 是文件，将 Inode 的引用计数减一，如果到了 0 则删除
  • 若 Inode 是文件夹，则无论引用计数，都删除它，这是因为不允许文件夹被硬链接引用（会允许引用环路的出现，让文件系统不再是树状结构；更重要的是允许一个文件夹 dir 有多个父文件夹，让 dir/.. 有歧义）。然后，递归地删除子文件（对其调用 unlink_inode）
rename

函数接受老路径、新路径和一个 flag 参数，取值可能是 RENAME_NOREPLACE （若新路径已经存在，则不能覆盖，应返回错误），或 RENAME_EXCHANGE（若新路径已经存在，则交换新旧路径）

link

创建文件的硬链接，增加引用计数即可

chmod, chown

改变文件的 mode （如前文所述，为类型+访问权限） 和所有者（用户的 uid 和组的 gid）

open, release, read, write, truncate

顾名思义。注意这里的 open 是 FUSE 框架为我们定义的 open 接口，并非暴露给用户的 open 系统调用。read 和 write 同理。

之前提到，用户进程读写文件的连接状态是在 Open File Table 内核数据结构中定义的，由 FUSE 包办。因此，这里我们定义的 open 并没有创建一个“连接”，而 read, write 也是无状态的（每次都要提供 offset）—— FUSE 处理好连接状态后，调用我们实现的 open, read, write 来真正读写块设备。

可选功能：内存中文件树

源文件：
direntry.h
direntry.cpp

接口：给定一个路径字符串，找到对应文件的信息，包括 Inode
实现为 direntry.h 中的 fischl_find_entry 和 files.h 中的 FilesOperation::namei
它是文件系统顶层接口层下属的一个内部服务

每次做 namei 操作都依照文件夹层级结构逐级访问文件夹的 DataBlock 的话，会导致 namei 操作进行过多次 IO。为了优化，我们考虑建立一棵内存中的文件树来表示文件的层级结构。

具体而言，这里的设计如下：用 FileNode 表示单个文件，用 TreeNode 表示文件树的内部节点（即文件夹）。那么：TreeNode 含有一个哈希表将文件名映射到文件（FileNode），又含有指向父文件夹的指针；FileNode 含有文件信息，以及如果文件是文件夹，一个该文件夹（TreeNode）的指针。顺带一提，哈希表的冲突解决方式是链地址法（separate chaining），保持整个哈希表不变，在每个桶中维护一个链表。

这样，在访问文件夹对应的 DataBlock 时将获得的数据用于构建内存中文件树，namei 大部分时间就能够在内存中完成了。不过要注意其它操作在修改硬盘上的数据时，可能需要同步修改文件树。

Q: 修改文件系统状态的操作，如创建 inode，是实时落实到硬盘上的吗？
A: 是的，这些修改状态的操作必须既落实到硬盘上，也落实到内存中文件树上。这里的内存中文件树相当于一个 write-through 的 cache，硬盘上的数据时时刻刻都是最新的。

改进 fischl 文件系统

提供改进的代码分支：https://git.ziaowang.top/admin/iloveos/commits/branch/adaptive_num_inodes/

让用户自行决定 INODE BLOCKS 个数

与其把分配多少个 Inode Datablock 硬编码，不如在 mkfs 时依据 disksize 来 {自适应地 / 确定一个可行范围让用户自行} 决定这个数字。之后，把这个数字放到 superblock 里面。

实现 STATFS 接口

statfs 的接口如下：

static int fischl_statfs(const char* path, struct statvfs* stbuf) {
  // Your code...
}

语义为把 path 所在的文件系统的统计信息放到 statvfs 数据结构中，具体结构见 statvfs 的 man page。

要测试这个接口，只需要在你的文件系统中运行 statfs 命令。

STATFS 接口冒烟测试

进行冒烟测试 (smoke test)：

# ./fischl /dev/loop0 n -s ../../mpoint
====Initializing RawDisk====
Number of sectors: 1024000
Disk size (in bytes): 524288000
The block device contains 128000 blocks
Choose the number of blocks to store inodes: 1 ~ 125951
12800
FORMAT 0
# cd ../../mpoint
# statfs .
{
        "Type": 1702057286,
        "Bsize": 4096,
        "Blocks": 115199,
        "Bfree": 115198,
        "Bavail": 0,
        "Files": 102400,
        "Ffree": 102399,
        ...
}

解释：创建文件系统分配了 12800 个 4K 数据块用来存储 inode，因此总共允许的文件数目（Files）为 12800 * (4K/512) = 102400 个。创建完文件系统，可用的 inode 和 datablock 各自比总数少了一个，推测是创建 root inode 分配了一个 inode 和一个 datablock 用来存储根目录。

依据 rmdir 的语义更正其实现

在实验过程中因为种种原因发现一个问题：rmdir 的 FUSE3 接口 和 rmdir 系统调用 以及 rmdir 命令 一致要求检查目标文件夹是否为空，仅当其为空时才允许删除，否则报错。先前的 fischl 并没有实现这一语义检查。

为了实现正确的语义，在 files.cpp 的 FilesOperation::fischl_rmdir 中检查文件夹是否为空，若非空则报错。

Posted

in

by

wponaws

Tags:

, ,

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *