f2fs论文阅读

f2fs是一款常见的针对NAND介质优化的可读写文件系统

论文题目: F2FS: A New File System for Flash Storage

背景介绍以及f2fs概览

常见的flash设备在写入数据时需要先把数据进行擦除。NAND架构的flash设备由于使用了存储控制器，更支持随机读写操作，因此在很多手机的真实负载场景下有着很好的表现。

f2fs主要把存储空间分成了六个部分：

superblock部分（SB）：保存了文件系统的基本分区信息以及一些初始化变量（后续不可修改）
checkpoint部分（CP）：保存了文件系统状态，bitmap，inode表以及当前处于活动状态的分段入口表。
段信息表部分（SIT）：包含了有效块的数量和数据区域中所有块的位图。
节点地址表部分（NAT）：包含了一个块地址表来定位节点块在存储区域的位置。
段汇总区域部分（SSA）：包含了表示主区域中所有块的所有者信息的摘要条目，例如父节点编号SSA条目会在清理期间迁移有效块之前标识父节点块。

作者专门通过一个例子向我们揭示了f2fs的工作原理：当我们需要访问/dir/file路径下的文件，需要分为下面几步：（1）通过读取NAT获取根节点的inode编号以及对应的数据块位置（2）在进入root数据块后，会查询到一个名为dir的文件目录并且获取其inode号（3）会把获取到的inode号输入进NAT中进行查询到一个新的物理块号（4）读取dir文件目录对应的物理块（5）在dir文件块中寻找file的inode号，之后重复3，4中的步骤直到寻找到对应的文件所在的数据块。真实的数据可以从main area中通过文件索引获取。

文件结构

原始的LFS文件系统通过一个inode map实现把inode号转换成一个磁盘上的位置。这会导致wandering tree效应，因为LFS的脏数据是追加更新的，所以如果一个数据块变脏了，那么那个数据块的直接索引块（必须要更新，但是是在log尾部进行追加更新）、间接索引块（由于直接索引块被更新，会发生递归的对间接索引块进行追加更新）最终导致递归更新，这也就是我们说的wandering tree效应。

LFS的inode map仅仅只是单纯的保存每个node的inode号以及对应的物理块号，间接索引的访问需要先访问上一级索引的数据块，但是f2fs通过NAT表，间接索引指向的并不是下层数据的数据块地址，而仅仅是NAT表中的一个数据条目，这样就不会发生上述wandering tree问题。在f2fs中只会发生一次数据块的修改以及对应的NAT表项的修改，上层的间接索引指向的仍旧是相同表项。

在f2fs中，一个4KB大小的文件目录项是由一个bitmap以及两个数组（里面包含了插槽以及文件名称的数据对）组成的。每一个插槽都拥有一个哈希值、inode号、文件名长度以及文件类型（普通文件，文件目录，标志链接）这几个信息。每一个文件目录都建立了多层级的哈希表来管理大量的数据条目。当f2fs需要在一个文件目录中查找一个文件名。首先会从第0层遍历整个哈希表，在每一层的遍历过程中，都会扫描包含有2个或者4个数据块的桶，需要O（log（数据块数目））的时间复杂度。

多起点的日志区域

不同于LFS文件系统只有一个很大的日志区域，f2fs保持了六个主日志区域来最大程度上进行了冷热数据分离。f2fs针对节点以及数据块定义了三种程度的数据热度：hot，warm以及cold。

f2fs会把直接的节点块当作更热的数据块（会更新的更加频繁，这个因为直接节点会直接指向文件数据块，因此任何对文件数据的修改操作都会有可能对直接节点产生影响。间接node会指向NAT表中的下一级节点，间接节点只会在某个node发生了删除或者添加后才会被修改），此外针对文件目录的节点块以及对应的节点数据块都被当作是hot的（主要是因为相比于常见的文件数据有着不同的写入流程）。

对于常见的数据块，如果一旦满足以下三条标准之一就会被当作cold数据：

被cleaning机制回收的数据块
被用户标记为cold的数据块
那些被标记为只进行一次写入或者只读的数据块，f2fs可以通过文件的扩展名去识别这些数据

f2fs默认是使用了6个日志来处理写入操作（EXT4仅仅使用了一个线程），这样就能够保证多个写入操作能够同时进行。如果开启了6个日志进行写入操作，那么这六个分别对应了表一中的六种情况。如果只开启了4个日志，那么会把cold以及warm进行合并处理，如果只开启了两个日志，那么只会发生一个日志处理data，另外一个处理节点的写入。

f2fs同时设计了一个configure区域用来和FTL层进行兼容，从而减小垃圾回收的开销。常见的FTL层在数据块以及flash日志块有三种方式（全相联，组相联，块相连）。全相联代表了一个flash日志块用来存储所有数据块的日志，组相联代表了一个flash日志块用来存储一组连续数据的日志，块相连代表了一个flash日志块用来存储单个数据的日志信息。（和组原里面的类似）。常见的FTL层使用了全相联或者是组相联的方法来更好的处理随机写操作。f2fs通过把活动的日志分别映射到不同的区域从而在FTL层就能够避免在并行写入操作时发生对一个块的冲突访问（主要是在全相联以及组相联的情况下，因为会有多个数据块对应一个日志块的情况）。

cleaning回收机制

cleaning机制主要是保证了f2fs的垃圾回收管理。f2fs的cleaning的操作是以section为粒度进行的。f2fs的cleaning分为两个独立的操作过程：foreground和background。foreground操作只会在空余section不足的时候才会被触发，在系统内核中会创建一个线程，周期性的在后台执行cleaning操作，一个cleaning操作会被分成三个部分：

驱逐section选择：首先要选择一个section作为cleaning对象，常见的有两种选择算法，一种是greedy另一种是cost-benefit。贪心算法直接会选择一个拥有最少有效块的section作为驱逐对象。f2fs在foreground选择了这种方式来保证在应用视角获取最少的延迟。此外，f2fs预留了5%的存储空间来保证cleaning过程中较高的空间利用率。cost-benefit准则被background所采用，这个选择准则不仅仅是根据一个section的空间有效率，还根据一个section的使用时间长度来决定，通过对一个section中每一个segment的平均使用长度取平均值来反映一个section的使用时间长度，这也能够帮助f2fs进一步进行冷热数据分类。
有效块的识别以及迁移：当完成了驱逐块的选择过程后，f2fs需要快速识别出一个section中的有效数据块。这个过程通过SIT(segment information table)中的位图进行识别。一旦完成了识别过程，f2fs就会把有效的数据块迁移到其他的空闲日志中去。对于后台的cleaning操作，f2fs并不会产生实际的IO流进行数据块迁移。f2fs通过把数据块加载到页缓存中并把其标记为dirty。之后f2fs会等着内核的工作线程之后把这些脏数据刷回存储设备中即可。
当所有的有效数据块被迁移了之后，该section就会被标记为空闲空间。在检查点被建立之前，这个section还不能够被分配，这是因为一旦发生崩溃，无法通过上一检查点来恢复数据。

动态日志机制

原本的日志文件系统使用了两种日志模式：普通日志模式和线程日志模式。在普通日志模式下，通过写入块数据来对segment进行清理并且严格遵循顺序写原则。即使用户提交了很多个随机写请求，这个过程会把这些请求转换成顺序写。一旦没有足够的空间，这种方式就会产生大量的cleaning操作开销。线程日志模式会向已有的segment中的invalid block中写入数据，但是这种随机写的操作会在一定程度上影响性能。f2fs同时使用了这两种模式，并且会根据文件系统的状态进行动态切换。具体来说，如果当前的文件系统中有k个空闲的section，那么就会优先使用普通日志模式，否则就会切换到线程日志模式。（值得注意的是闪存设备对于线程日志模式的随机写操作很适合，有着极高的性能表现）

检查点机制以及恢复机制

检查点机制主要分为以下几个步骤：

所有的脏节点以及dentry节点都会被从页缓存中flush到底层存储设备中。
停止所有常见的操作如：create、unlink等等
所有的文件系统元数据都会被写入到专用的磁盘区域中
f2fs会创建一个检查点，具体包括了：
- header和footer，会在创建检查点的同时设置对应的版本号。
- NAT和SIT的位图信息
- NAT和SIT的日志
- 孤儿数据块（笑），如果发生了一个inode在被关闭之前就被删除了（两个进程打开了同一个文件，但是只有一个进程删除了该文件），该inode节点就会被标记为孤儿节点。

前滚恢复机制

f2fs使用了一个向前滚机制来进行普通文件数据恢复。前滚恢复则在后滚恢复的基础上进行优化，在写入普通文件时，很多时候只需要对特定文件进行一致性操作，而系统中的其他数据则不关注，如果每次都写入一次Checkpoint，未免太过耗时。所以在写入普通文件时，只需要确保该文件的管理数据落盘即可，并通过特殊的标记，记录其状态，在恢复流程中，根据写入的数据可以恢复到掉电前的状态。

实验部分

使用qemu配合gdb完成对f2fs的调试

首先下载linux内核源码以及busybox源码

# 下载内核
wget https://mirrors.edge.kernel.org/pub/linux/kernel/v5.x/linux-5.10.163.tar.gz

# 下载busybox
git clone https://github.com/mirror/busybox.git

# 编译busybox
export ARCH=arm
export CROSS_COMPILE=arm-linux-gnuabi-
make menuconfig

# 修改设置
Busybox Settings --->
	Build Options --->
		[*] Build BusyBox as a static binary (no shared libs)

# 完成编译
make install

# 把busybox中生成的_install目录拷贝到linux解压后的目录中
sudo mkdir etc
sudo mkdir dev
sudo mkdir mnt
sudo mkdir –p etc/init.d/

# 在_install /etc/init.d/目录下创建rcS文件，写入如下内容

#!/bin/sh
mkdir –p /proc
mkdir –p /tmp
mkdir -p /sys
mkdir –p /mnt
/bin/mount -a
mkdir -p /dev/pts
mount -t devpts devpts /dev/pts
echo /sbin/mdev > /proc/sys/kernel/hotplug
mdev –s

# 给rcS最高权限
sudo chmod 777 rcS

# 在 _install的etc目录下创建fstab文件并写入如下内容
proc /proc proc defaults 0 0
tmpfs /tmp tmpfs defaults 0 0
sysfs /sys sysfs defaults 0 0
tmpfs /dev tmpfs defaults 0 0
debugfs /sys/kernel/debug debugfs defaults 0 0

# 在_install /etc目录下创建inittab文件并写入如下内容：
::sysinit:/etc/init.d/rcS
::respawn:-/bin/sh
::askfirst:-/bin/sh
::ctrlaltdel:/bin/umount -a -r

# 在_install dev目录下创建设备节点
sudo mknod console c 5 1
sudo mknod null c 1 3

首先是进入linux源码目录，然后通过menuconfig配置qemu运行参数:

$ export ARCH=arm
$ export CROSS_COMPILE= arm-linux-gnueabi-
$ export make vexpress_defconfig
$ make menuconfig

进入menuconfig界面以后，修改几个内核选项:
第一个是修改initramfs的位置，即_install目录，这样系统就会将_install目录作为启动的根目录，还需要把boot option的command string清空。

General setup --->
	[*] Initial RAM filesystem and RAM Disk (initramfs/initrd) support
		(_install) Initramfs source file(s)
Boot options -->
	()Default kernel command string

第二个选项是内存选项，配置 memory split 为“3G/1G user/kernel split”以及打开高端内存。

1
2
3

Kernel Features --->
	Memory split (3G/1G user/kernel split) --->
	[ *] High Memory Support

然后就可以开始编译内核:

1 2	make bzImage –j4 ARCH=arm CROSS_COMPILE=arm-linux-gnueabi- make dtbs

F2FS工具的准备
主要使用到用于格式化的mkfs.f2fs工具，ubuntu下可以执行以下命令进行安装
1
sudo apt-get install f2fs-tools

编译可运行F2FS的内核
经过上述步骤的编译，会在Linux的根目录生成一个.config文件，打开这个文件，找到以下的内核选项，并设置为y。

CONFIG_F2FS_FS=y
CONFIG_F2FS_STAT_FS=y
CONFIG_F2FS_FS_XATTR=y
CONFIG_F2FS_FS_POSIX_ACL=y

# gdb调试信息
CONFIG_GDB_SCRIPTS=y

# debug信息
CONFIG_DEBUG_INFO=y

# 要先把performance那个选项关了再开这个保证Os编译优化
CONFIG_CC_OPTIMIZE_FOR_SIZE=y

记得要打开gdb调试的内核编译选项以及把编译优化参数设置为Os否则会有很多变量被优化掉
然后重新编译

1 2	make bzImage –j4 ARCH=arm CROSS_COMPILE=arm-linux-gnueabi- make dtbs

编译结束后，创建一个文件作为F2FS的磁盘空间

1 2	dd if=/dev/zero of=a9rootfs.f2fs bs=1M count=250 # 创建250MB的F2FS空间 mkfs.f2fs a9rootfs.f2fs #使用F2FS格式化工具进行格式化

接下来，通过执行如下命令启动Qemu虚拟机，需要使用-sd选项将刚刚创建的作为F2FS磁盘空间的文件挂载到系统中:

qemu-system-arm  \
        -M vexpress-a9 \
        -m 512M \
        -kernel /home/xxx/kernels/linux4/linux-4.18/arch/arm/boot/zImage \
        -dtb /home/xxx/kernels/linux4/linux-4.18/arch/arm/boot/dts/vexpress-v2p-ca9.dtb \
        -nographic \
        -append "rdinit=/linuxrc console=ttyAMA0 loglevel=8" \
        -sd a9rootfs.f2fs \
        -s \
        -S

最后，Qemu完成启动之后，在Qemu的linux系统执行如下命令将F2FS挂载到linux中:

1	mount -t f2fs /dev/mmcblk0 /mnt/ -o loop

最终使用vscode打开该项目，创建.vscode目录并设置launch.json文件


{
    // Use IntelliSense to learn about possible attributes.
    // Hover to view descriptions of existing attributes.
    // For more information, visit: https://go.microsoft.com/fwlink/?linkid=830387
    "version": "0.2.0",
    "configurations": [
        {
            "name": "kernel debug",
            "type": "cppdbg",
            "request": "launch",
            "program": "${workspaceFolder}/vmlinux",
            "cwd": "${workspaceFolder}",
            "MIMode": "gdb",
            "miDebuggerPath":"/usr/bin/gdb-multiarch",
            "miDebuggerServerAddress": "localhost:1234"
        }
    ]

}

之后就可以在vscode中打断点查看调试信息了。