Linux 文件系统学习之 EROFS 源码阅读笔记

前言

学 C 语言已有两个多月，还没尝试过调试一个完整的项目。故借 erofs-utils 项目实战一下，记录一些调试笔记，并对 erofs 文件系统根据源码进行更近一步的梳理

erofs-utils 使用

笔者使用的主机环境为 Ubuntu 18.04，可正常运行

环境配置

可以先查阅 linux 官方文档 https://www.kernel.org/doc/html/latest/filesystems/erofs.html

其中提供了 erofs-utils 的地址

git://git.kernel.org/pub/scm/linux/kernel/git/xiang/erofs-utils.git
1

clone 到本地后，根据 README 可以进行使用。由于 erofs 默认支持 lz4 压缩算法，因此需要安装相应的库，不然 .configure 时会关闭 lz4

sudo apt-get install liblz4-dev
1

工具编译

	$ ./autogen.sh
	$ ./configure
	$ make
1
2
3

进行压缩

先生成一个 img 为 erofs_disk，并创建测试所用待压缩路径 /home/srcd

# dd if=/dev/zero of=/home/erofs_disk bs=512 count=23000

# mkdir /home/srcd
# cp README /home/srcd
# cp COPYING /home/srcd
# cp ChangeLog /home/srcd
# cp Makefile /home/srcd
1
2
3
4
5
6
7

使用 lz4 进行压缩

# ./mkfs/mkfs.erofs -zlz4 /home/erofs_disk /home/srcd/
1

将 img 挂载到某个路径下进行查看

mount -t erofs /home/erofs_disk /mnt/scratch -oloop
1

vscode 配置

我们需要对 vscode 进行配置，使其能够对 mkfs.erofs 进行调试

安装 C/C++ 插件（这部分不赘述）

在 {workspace} 中创建 .vscode 目录，并在其下创建 launch.json。笔者没有编写 task.json。而是每次手动进行 make

{
    "version": "0.2.0",
    "configurations": [
 
        {
            "name": "(gdb) Launch",// 配置名称，将会在启动配置的下拉菜单中显示
            "type": "cppdbg",// 配置类型，这里只能为cppdbg
            "request": "launch",// 请求配置类型，可以为launch（启动）或attach（附加）
            "program": "${workspaceRoot}/linux_learn/new_erofs-utils/erofs-utils/mkfs/mkfs.erofs",// 将要进行调试的程序的路径
            "stopAtEntry": true, // 设为true时程序将暂停在程序入口处，我一般设置为true
            "cwd": "${workspaceRoot}",// 调试程序时的工作目录
            "environment": [],// （环境变量？）
            "externalConsole": false,// 调试时是否显示控制台窗口，vscode自带控制台
            "MIMode": "gdb",// 指定连接的调试器，可以为gdb或lldb。
            //"preLaunchTask": "shell" // 调试会话开始前执行的任务，一般为编译程序。
            //与tasks.json的taskName相对应，可根据需求选择是否使用，本文不需要。
            "args": ["-zlz4","/home/erofs_disk","/home/srcd/"]
        }
    ]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

至此，便能够开始调试了，运行-》启动调试。vscode 便会进入 main 函数，如下所示

跟踪执行流程

上一篇文章只是根据源码对 erofs 格式化流程进行了大致梳理，在此，笔者通过跟踪的方式，进一步细化对 erofs 的学习，整个过程以下述命令为实际例子。

# ./mkfs/mkfs.erofs -zlz4 /home/erofs_disk /home/srcd/
1

main

mkfs/main.c ---> main
    --- erofs_init_configure
    --- erofs_mkfs_default_options
    --- mkfs_parse_options_cfg
    --- dev_open
    --- erofs_set_fs_root
    --- erofs_buffer_init
    --- erofs_load_compress_hints
    --- z_erofs_compress_init (⭐)
    	--- erofs_compressor_init
    		--- compressors[i]->init(c)
    --- erofs_generate_devtable
    --- erofs_inode_manager_init
    --- erofs_build_shared_xattrs_from_path
    --- erofs_mkfs_build_tree_from_path (⭐)
    	--- erofs_iget_from_path ： 初始化文件系统结构
    	--- erofs_mkfs_build_tree ： 压缩文件
    --- erofs_lookupnid(⭐)
    --- erofs_mkfs_update_super_block(⭐)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

由于初始化部分比较简单，笔者主要跟踪后几个方法的执行流程

z_erofs_compress_init

该方法主要调用 erofs_compressor_init 用于初始化 compressors。后续压缩过程需要调用 compressors 的 compress 方法 。 由于命令行传入了 lz4 参数，因此对应 compressors 中只有一个元素，即 erofs_compressor_lz4

static struct erofs_compressor *compressors[] = {
#if LZ4_ENABLED
#if LZ4HC_ENABLED
		&erofs_compressor_lz4hc,
#endif
		&erofs_compressor_lz4,
#endif
#if HAVE_LIBLZMA
		&erofs_compressor_lzma,
#endif
};
1
2
3
4
5
6
7
8
9
10
11

erofs_mkfs_build_tree_from_path

该函数是最核心的函数，我们一步一步跟踪，对于部分参数，笔者直接替换为真实值

1. 通过 erofs_iget_from_path 为 “/home/srcd” 创建目录文件 inode。该目录文件对应的是 erofs 文件系统的根目录 / ，其对应了源文件系统的 “/home/srcd” 目录。
2. 将该 inode 的 parent 指向自己，说明自己是根目录
3. 调用 erofs_mkfs_build_tree 递归地为根目录创建子目录及文件，并一一对应 “/home/srcd” 下的子目录和文件

struct erofs_inode *erofs_mkfs_build_tree_from_path(struct erofs_inode *parent,
						    const char *path)
{
    // *parent = NULL,path = "/home/srcd"
	struct erofs_inode *const inode = erofs_iget_from_path(path, true);

	if (IS_ERR(inode))
		return inode;

	/* a hardlink to the existed inode */
	if (inode->i_parent) {
		++inode->i_nlink;
		return inode;
	}

	/* a completely new inode is found */
	if (parent)
		inode->i_parent = parent;
	else
		inode->i_parent = inode;	/* rootdir mark */

	return erofs_mkfs_build_tree(inode);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

具体地，在执行 erofs_iget_from_path 的过程中，有如下流程

1. 通过 lstat64 解析 path，可以快速获知当前 path 是目录还是文件
2. “/home/srcd” 是目录，因此不会执行 erofs_iget 而直接调用 erofs_new_inode 创建一个新的 inode
3. 通过 erofs_fill_inode 对新 inode 进行初始化

static struct erofs_inode *erofs_iget_from_path(const char *path, bool is_src)
{
	struct stat64 st;
	struct erofs_inode *inode;
	int ret;

	/* currently, only source path is supported */
	if (!is_src)
		return ERR_PTR(-EINVAL);

	ret = lstat64(path, &st);
	if (ret)
		return ERR_PTR(-errno);

	/*
	 * lookup in hash table first, if it already exists we have a
	 * hard-link, just return it. Also don't lookup for directories
	 * since hard-link directory isn't allowed.
	 */
	if (!S_ISDIR(st.st_mode)) {
		inode = erofs_iget(st.st_dev, st.st_ino);
		if (inode)
			return inode;
	}

	/* cannot find in the inode cache */
	inode = erofs_new_inode();
	if (IS_ERR(inode))
		return inode;

	ret = erofs_fill_inode(inode, &st, path);
	if (ret) {
		free(inode);
		return ERR_PTR(ret);
	}

	return inode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

在 erofs_fill_inode 中，主要就是装填 inode 的属性。此时，也将 path 设入 inode 的 srcpath 中，建立了源文件系统与目标文件系统的映射关系。

最后，由于是新的 inode 。需要将其插入 inode_hashtable 中。inode_hashtable 可以理解为 inode 的缓存，便于加速 inode 的分配与释放。

static int erofs_fill_inode(struct erofs_inode *inode,
			    struct stat64 *st,
			    const char *path)
{
	// 省略部分代码
	inode->i_mode = st->st_mode;
	inode->i_uid = cfg.c_uid == -1 ? st->st_uid : cfg.c_uid;
	inode->i_gid = cfg.c_gid == -1 ? st->st_gid : cfg.c_gid;
	inode->i_ctime = st->st_ctime;
	inode->i_ctime_nsec = ST_CTIM_NSEC(st);
	// 省略部分代码
    inode->i_ctime = sbi.build_time;
    inode->i_ctime_nsec = sbi.build_time_nsec;
	// 省略部分代码
	inode->i_nlink = 1;	/* fix up later if needed */
	strncpy(inode->i_srcpath, path, sizeof(inode->i_srcpath) - 1);
	inode->i_srcpath[sizeof(inode->i_srcpath) - 1] = '\0';
	inode->dev = st->st_dev;
	inode->i_ino[1] = st->st_ino;
	// 省略部分代码
	list_add(&inode->i_hash,
		 &inode_hashtable[(st->st_ino ^ st->st_dev) %
				  NR_INODE_HASHTABLE]);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

接着，便从 erofs_iget_from_path 跳出，进入 erofs_mkfs_build_tree。该函数分为两部分，第一部分是初始化当前目录下所有目录项，并持久化当前目录内容。第二部分是遍历目录项，递归执行 erofs_mkfs_build_tree_from_path，从而能够将所有文件完成持久化。首先是第一部分：

1. 首先会通过 i_mode 判断当前 inode 是目录文件还是普通文件，这里是根目录，因此执行目录文件相关操作
2. 通过 opendir 打开根目录对应的源文件系统路径 i_srcpath ，实为 “/home/srcd”，获得 DIR 结构体，再由 readdir 能够根据 DIR 获得一个 dirent。由于点不不开 readdir ，根据上下文推断，readdir 用于从 DIR 目录中迭代获取一个目录项 dp
3. 根据 dir 和 目录项名字 dp->name 通过 erofs_d_alloc 为该目录项申请一个 dentry。具体地，erofs_d_alloc 申请一块 dentry 空间后，并将其链接到 dir 的 subdir 中，表示这一 dentry 是 dir 的子目录项。至此，根目录与其子目录项的 dentry 树被搭建起来。只要如此递归，便能构建完整的 dentry 树
4. 重复上述过程，直到 dir 对应目录下的目录项 dentry 全被初始化。
5. 至此，dir 的内容也更新完毕

其次是第二部分：

1. 通过 list_for_each_entry 宏从 dir 开始遍历其下目录项
2. 对于每个目录项 dentry，其所绑定的 inode 为 erofs_mkfs_build_tree_from_path 获得的，至此开始新一轮的递归（算法无处不在：）
3. 递归完成后，erofs 的目录项以及文件都写好了，通过 erofs_write_dir_file 和 erofs_write_tail_end 将 dir 内容持久化

static struct erofs_inode *erofs_mkfs_build_tree(struct erofs_inode *dir)
{
	int ret;
	DIR *_dir;
	struct dirent *dp;
	struct erofs_dentry *d;
	unsigned int nr_subdirs;
	
    // 省略部分代码
	_dir = opendir(dir->i_srcpath);
	nr_subdirs = 0;
	while (1) {
		/*
		 * set errno to 0 before calling readdir() in order to
		 * distinguish end of stream and from an error.
		 */
		errno = 0;
		dp = readdir(_dir);
		if (!dp)
			break;

		if (is_dot_dotdot(dp->d_name) ||
		    !strncmp(dp->d_name, "lost+found", strlen("lost+found")))
			continue;

		/* skip if it's a exclude file */
		if (erofs_is_exclude_path(dir->i_srcpath, dp->d_name))
			continue;

		d = erofs_d_alloc(dir, dp->d_name);
		if (IS_ERR(d)) {
			ret = PTR_ERR(d);
			goto err_closedir;
		}
		nr_subdirs++;

		/* to count i_nlink for directories */
		d->type = (dp->d_type == DT_DIR ?
			EROFS_FT_DIR : EROFS_FT_UNKNOWN);
	}

	if (errno) {
		ret = -errno;
		goto err_closedir;
	}
	closedir(_dir);

	ret = erofs_prepare_dir_file(dir, nr_subdirs);
	ret = erofs_prepare_inode_buffer(dir);

	list_for_each_entry(d, &dir->i_subdirs, d_child) {
		char buf[PATH_MAX];
		unsigned char ftype;
		ret = snprintf(buf, PATH_MAX, "%s/%s",
			       dir->i_srcpath, d->name);
		d->inode = erofs_mkfs_build_tree_from_path(dir, buf);

	}
	erofs_write_dir_file(dir);
	erofs_write_tail_end(dir);
	return dir;

	return ERR_PTR(ret);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

上述提到，开始遍历 dir 下的目录项，递归执行 erofs_mkfs_build_tree_from_path。例如，此时的 buf 通过 snprintf 的赋值，变为了 “/home/srcd/COPYING”，对应普通文件，因此 erofs_mkfs_build_tree_from_path 过程变得不同

根据上述 erofs_mkfs_build_tree_from_path 的分析，普通文件会进入 erofs_iget_from_path 的 erofs_iget 。该函数很简单，就是遍历缓存 inode_hashtable，看看是否有满足指定 dev 和 ino 的 inode 可以被复用。这里可以理解每个 path 会对应一组独一无二的 dev 和 ino ，因此如果该 path 之前创建过 inode 便能够复用

否则返回 NULL，便会像创建目录文件 inode 一样为普通文件创建 inode

struct erofs_inode *erofs_iget(dev_t dev, ino_t ino)
{
	struct list_head *head =
		&inode_hashtable[(ino ^ dev) % NR_INODE_HASHTABLE];
	struct erofs_inode *inode;

	list_for_each_entry(inode, head, i_hash)
		if (inode->i_ino[1] == ino && inode->dev == dev)
			return erofs_igrab(inode);
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11

同样地，从 erofs_iget_from_path 返回后，进入 erofs_mkfs_build_tree，由于此时输入为普通文件，因此会进入普通文件构建相关的内容，其核心便是调用了 erofs_write_file

static struct erofs_inode *erofs_mkfs_build_tree(struct erofs_inode *dir)
{
	int ret;
	DIR *_dir;
	struct dirent *dp;
	struct erofs_dentry *d;
	unsigned int nr_subdirs;

	ret = erofs_prepare_xattr_ibody(dir);
	if (ret < 0)
		return ERR_PTR(ret);

	if (!S_ISDIR(dir->i_mode)) {
		if (S_ISLNK(dir->i_mode)) {
			char *const symlink = malloc(dir->i_size);

			if (!symlink)
				return ERR_PTR(-ENOMEM);
			ret = readlink(dir->i_srcpath, symlink, dir->i_size);
			if (ret < 0) {
				free(symlink);
				return ERR_PTR(-errno);
			}

			ret = erofs_write_file_from_buffer(dir, symlink);
			free(symlink);
			if (ret)
				return ERR_PTR(ret);
		} else {
			ret = erofs_write_file(dir);
			if (ret)
				return ERR_PTR(ret);
		}

		erofs_prepare_inode_buffer(dir);
		erofs_write_tail_end(dir);
		return dir;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

erofs_write_file 会先根据 cfg.c_compr_alg_master 判断是否需要压缩，若需要则执行 erofs_write_compressed_file ，否则执行 write_uncompressed_file_from_fd。而 c_compr_alg_master 在最开始跟踪时，发现其在 z_erofs_compress_init 被初始化了

int erofs_write_file(struct erofs_inode *inode)
{
	int ret, fd;

	if (!inode->i_size) {
		inode->datalayout = EROFS_INODE_FLAT_PLAIN;
		return 0;
	}

	if (cfg.c_chunkbits) {
		inode->u.chunkbits = cfg.c_chunkbits;
		/* chunk indexes when explicitly specified */
		inode->u.chunkformat = 0;
		if (cfg.c_force_chunkformat == FORCE_INODE_CHUNK_INDEXES)
			inode->u.chunkformat = EROFS_CHUNK_FORMAT_INDEXES;
		return erofs_blob_write_chunked_file(inode);
	}

	if (cfg.c_compr_alg_master && erofs_file_is_compressible(inode)) {
		ret = erofs_write_compressed_file(inode);

		if (!ret || ret != -ENOSPC)
			return ret;
	}

	/* fallback to all data uncompressed */
	fd = open(inode->i_srcpath, O_RDONLY | O_BINARY);
	if (fd < 0)
		return -errno;

	ret = write_uncompressed_file_from_fd(inode, fd);
	close(fd);
	return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

在 erofs_write_compressed_file 中，通过 z_erofs_vle_compress_ctx 封装了一些压缩用的上下文，如 buffer head 等，与 inode 一同传入 vle_compress_one 中。具体地：

1. 先根据 i_srcpath 打开源文件系统文件，获得描述符 fd
2. 通过 z_erofs_write_mapheader 初始化压缩元数据 compressmeta
3. 设置好上下文 ctx 后进入 while 循环
4. while 循环根据 remaining 剩余量判断是否还要进行压缩
5. 若要压缩，先通过 fd ，从源文件中读取指定大小内容，读入 ctx.queue 中
6. 调用 vle_compress_one 进行压缩

int erofs_write_compressed_file(struct erofs_inode *inode)
{
	struct erofs_buffer_head *bh;
	struct z_erofs_vle_compress_ctx ctx;
	erofs_off_t remaining;
	erofs_blk_t blkaddr, compressed_blocks;
	unsigned int legacymetasize;
	int ret, fd;
	u8 *compressmeta = malloc(vle_compressmeta_capacity(inode->i_size));

	if (!compressmeta)
		return -ENOMEM;

	fd = open(inode->i_srcpath, O_RDONLY | O_BINARY);

	/* allocate main data buffer */
	bh = erofs_balloc(DATA, 0, 0, 0);
    // 省略部分代码

	z_erofs_write_mapheader(inode, compressmeta);

	blkaddr = erofs_mapbh(bh->block);	/* start_blkaddr */
	ctx.blkaddr = blkaddr;
	ctx.metacur = compressmeta + Z_EROFS_LEGACY_MAP_HEADER_SIZE;
	ctx.head = ctx.tail = 0;
	ctx.clusterofs = 0;
	remaining = inode->i_size;

	while (remaining) {
		const u64 readcount = min_t(u64, remaining,
					    sizeof(ctx.queue) - ctx.tail);

		ret = read(fd, ctx.queue + ctx.tail, readcount);
		if (ret != readcount) {
			ret = -errno;
			goto err_bdrop;
		}
		remaining -= readcount;
		ctx.tail += readcount;

		/* do one compress round */
		ret = vle_compress_one(inode, &ctx, false);
		if (ret)
			goto err_bdrop;
	}

	/* do the final round */
	ret = vle_compress_one(inode, &ctx, true);
	if (ret)
		goto err_bdrop;
	// 省略部分代码
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

在 vle_compress_one 中，调用 erofs_compress_destsize 将缓冲区内容压缩成固定大小 pclustersize，其具体调用了 lz4 的压缩算法，最终会压入 dstbuf 中。

压缩完成后，需要通过 blk_write 将 dstbuf 写入 ctx 上下文中

static int vle_compress_one(struct erofs_inode *inode,
			    struct z_erofs_vle_compress_ctx *ctx,
			    bool final)
{
	struct erofs_compress *const h = &compresshandle;
	unsigned int len = ctx->tail - ctx->head;
	unsigned int count;
	int ret;
	static char dstbuf[EROFS_CONFIG_COMPR_MAX_SZ + EROFS_BLKSIZ];
	char *const dst = dstbuf + EROFS_BLKSIZ;

	while (len) {
		const unsigned int pclustersize =
			z_erofs_get_max_pclusterblks(inode) * EROFS_BLKSIZ;
		bool raw;

		if (len <= pclustersize) {
			if (final) {
				if (len <= EROFS_BLKSIZ)
					goto nocompression;
			} else {
				break;
			}
		}

		count = min(len, cfg.c_max_decompressed_extent_bytes);
		ret = erofs_compress_destsize(h, ctx->queue + ctx->head,
					      &count, dst, pclustersize);
		if (ret <= 0) {
			if (ret != -EAGAIN) {
				erofs_err("failed to compress %s: %s",
					  inode->i_srcpath,
					  erofs_strerror(ret));
			}
nocompression:
			ret = write_uncompressed_extent(ctx, &len, dst);
			if (ret < 0)
				return ret;
			count = ret;
			ctx->compressedblks = 1;
			raw = true;
		} else {
			const unsigned int tailused = ret & (EROFS_BLKSIZ - 1);
			const unsigned int padding =
				erofs_sb_has_lz4_0padding() && tailused ?
					EROFS_BLKSIZ - tailused : 0;

			ctx->compressedblks = DIV_ROUND_UP(ret, EROFS_BLKSIZ);
			DBG_BUGON(ctx->compressedblks * EROFS_BLKSIZ >= count);

			/* zero out garbage trailing data for non-0padding */
			if (!erofs_sb_has_lz4_0padding())
				memset(dst + ret, 0,
				       roundup(ret, EROFS_BLKSIZ) - ret);

			/* write compressed data */
			erofs_dbg("Writing %u compressed data to %u of %u blocks",
				  count, ctx->blkaddr, ctx->compressedblks);

			ret = blk_write(dst - padding, ctx->blkaddr,
					ctx->compressedblks);
			if (ret)
				return ret;
			raw = false;
		}

		ctx->head += count;
		/* write compression indexes for this pcluster */
		vle_write_indexes(ctx, count, raw);

		ctx->blkaddr += ctx->compressedblks;
		len -= count;

		if (!final && ctx->head >= EROFS_CONFIG_COMPR_MAX_SZ) {
			const unsigned int qh_aligned =
				round_down(ctx->head, EROFS_BLKSIZ);
			const unsigned int qh_after = ctx->head - qh_aligned;

			memmove(ctx->queue, ctx->queue + qh_aligned,
				len + qh_after);
			ctx->head = qh_after;
			ctx->tail = qh_after + len;
			break;
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

至此，对于 erofs 的前半段内容基本梳理完成。需要梳理的是 erofs 的后半段内容。即 erofs 如何将压缩文件写入 img 中？其内容是如何组织的？

erofs 下半段

内容组织形式

既然要探究 erofs 内容具体组织形式，看论文是最快的了，论文名为《EROFS: A Compression-friendly Readonly File System for Resource-scarce Devices》

论文中简单明了的给出了 erofs 内容组织形式，如下图所示

1. super_block 放在开始处
2. 每个文件块，由 inode、xattrs、block index、encoded blocks 组成。encoded block 表示压缩后的数据或者无需压缩的数据块
3. 这里的 block index , 记录的是源 blocks 的分布与压缩后 blocks 分布的对应关系。如图中右半部分所示，源 block 共 10 个 block ，对应 block index 中 10 个元素，分别记录了对应压缩后 blocks 的关系。该结构的好处是，当想要索引某一块源 block 时，只需从 block index 进行查找，找出该源 block 对应现在 encoded block 的编号，便能快速找到并解压。而无需先解压再查找

因此，回到源码，我们的问题变成，如何完成上述组织形式的？

blk_write

事实上，用户态格式化工具无需像内核一样与块设备打交道。其实只需要 open(img_path) ，对其进行写入即可。但如何写，往哪写就需要好好设计一番。因此，在 erofs-utils 中

1. 首先通过 dev_open(img_path) 打开待写入镜像，并获得其句柄
2. 将镜像内容空间抽象成一块块的 erofs_block ，并交由 erofs_buffer_head 进行管理
3. blk_write 则是能够将 buffer_head 中关联的内容通过打开的镜像句柄，写入镜像中，写入的位置由 erofs_block 中记录的块号决定
4. 经过如此抽象后，实现论文中的内容组织形式就变得简单了

首先跟踪 blk_write ，实际上其调用了 dev_write，而 dev_write 调用了 pwrite 。功能很简单，需要弄清楚的是参数分别是什么，从哪来

ret = pwrite(erofs_devfd, buf, len, (off_t)offset);
1

pwrite 表示通过 erofs_devfd 找到对应镜像，将 buf 内容写入镜像空间的 offset 处，写入大小为 len 。在这里的 erofs_devfd 在 dev_open(img_path) 时便被打开，作为全局变量。buf，offset，len 分别对应 dev_write 的三个参数

#define blknr_to_addr(nr)       ((erofs_off_t)(nr) * EROFS_BLKSIZ)

static inline int blk_write(const void *buf, erofs_blk_t blkaddr, u32 nblocks)
{
	return dev_write(buf, blknr_to_addr(blkaddr),blknr_to_addr(nblocks));
}
1
2
3
4
5
6

由上可以得出，blkaddr 为 block 块号，nblocks 为 block 块数，能够通过 blknr_to_addr 将块号转为 offset。也由此我们知道了 blk_write 的作用，则是将 buf 的内容，从打开镜像的第 blkaddr 个块开始写，写 nblocks 个块的长度。

回到 vle_compress_one 的调用链中，可见其执行了 erofs_compress_destsize 后，将 ctx->queue 中的内容压缩到 dst 中，便通过 blk_write 将 dst 的内容写入镜像的 ctx->blkaddr，写入块数为 ctx->compressedblks

static int vle_compress_one(struct erofs_inode *inode,
			    struct z_erofs_vle_compress_ctx *ctx,
			    bool final)
{
		ret = erofs_compress_destsize(h, ctx->queue + ctx->head,
					      &count, dst, pclustersize);
		ret = blk_write(dst - padding, ctx->blkaddr,ctx->compressedblks);
    	ctx->blkaddr += ctx->compressedblks;

}
1
2
3
4
5
6
7
8
9
10

从 vle_compress_one 中返回 erofs_write_compressed_file ,可以看到 ctx->blkaddr 何时被赋值。先是通过 erofs_balloc 申请了 bh 和 block，再通过 erofs_mapbh 能够获取到 block 在镜像空间中对应的块号 blkaddr

int erofs_write_compressed_file(struct erofs_inode *inode)
{
    bh = erofs_balloc(DATA, 0, 0, 0);
    blkaddr = erofs_mapbh(bh->block);
    ret = vle_compress_one(inode, &ctx, false);
}
1
2
3
4
5
6

具体地，erofs_mapbh 可以被理解为用于管理 block 映射的方法，内容如下。主要地，last_mapped_block 指向当前最后一个 block。每个被分配的 block 通过链表串联起来。而 tail_blkaddr 则记录了当前最后一个 block 的下一个 block的编号。erofs_mapbh 做的事情大概就是根据 tail_blkaddr ，为新的 bb 赋予一个 blkaddr。

其中 BLK_ROUND_UP 会根据当前 bb->buffers.off 计算其需要消耗几个 block 。因此，如果当前 bb 需要5个block ，最后 tail_blkadrr 会 +5；也就意味着该 bh 能用几个 block 此时已被分配好。

static erofs_blk_t __erofs_mapbh(struct erofs_buffer_block *bb)
{
	erofs_blk_t blkaddr;

	if (bb->blkaddr == NULL_ADDR) {
		bb->blkaddr = tail_blkaddr;
		last_mapped_block = bb;
		erofs_bupdate_mapped(bb);
	}

	blkaddr = bb->blkaddr + BLK_ROUND_UP(bb->buffers.off);// 
	if (blkaddr > tail_blkaddr)
		tail_blkaddr = blkaddr;

	return blkaddr;
}

erofs_blk_t erofs_mapbh(struct erofs_buffer_block *bb)
{
	struct erofs_buffer_block *t = last_mapped_block;

	if (bb && bb->blkaddr != NULL_ADDR)
		return bb->blkaddr;
	do {
		t = list_next_entry(t, list);
		if (t == &blkh)
			break;

		DBG_BUGON(t->blkaddr != NULL_ADDR);
		(void)__erofs_mapbh(t);
	} while (t != bb);
	return tail_blkaddr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

block 管理

由于笔者第一次接触 block 管理相关内容，花了较多时间对其细节进行梳理，在此进行记录。由上述分析可知通过 dev_write 便能将缓冲区 buf 中的内容写入对应 offset 中。因此对于 block 的管理，实际上就是对于 offset 的管理

那么管理 offset 在 erofs 中设计了 buffer_head 和 buffer_block 进行管理。其关系为，一个 bb 可以由多个 bh 使用。bb 中 buffers.off 表示当前 bb 的 offset ，意味着 offset 之前的内容已被使用。 bh 中的 off 表示该 bh 对应 bb 的哪一段空间的起始地址。使用了 bb 的所有 bh 被 bb 的 list 结构体串联起来。bb 的 blkaddr 表示当前 bb 对应镜像空间的哪一块 block。

基于此，我们可以给出对镜像空间的管理流程。对应 erofs_balloc

情况一：第一次申请

1. 首先，当想要往镜像空间写数据时，需要先申请 bb ，bb 初始化 buffers.off 为 0。
2. 再申请一个 bh 关联该 bb 。其 bh.off 也为 0。此时根据待写入数据大小 size，修改 bb.buffers.off 为 size 。意味着下一个 bh 只能从 size 开始写。

情况二：第二次申请

1. 当又需要往镜像空间写数据时，再申请一次 bb ，发现上一次申请的 bb 还有很多空间，因此拿来复用，并申请一个新的 bh2 关联该 bb 。
2. 根据需要写入的大小 size2 ，修改 bb.buffers.off 为 size+size2。而此时的 bh2.off 为 size。

情况三：第三次申请

1. 此时又需要往镜像空间写数据，但需要写入的大小 size3 超过了一个 bb 的大小
2. 意味着之前的 bb 无法复用，需要新建一个 bb2 ，并新建一个 bh3
3. 此时 bh3.off = 0，且 bb2.buffers.off = size3。

上述流程仍未涉及 block 块号的划分，对应的是 bb.blkaddr 的设置。事实上，在申请新的 bb 时，会将 bb 串起来，以保证 bb 的连贯和有序性。因此当需要划分块号时，只需要一次遍历串联的 bb 链，根据其 buffers.off 值为其划分 block 号。实现函数为 erofs_mapbh

其需要维护 last_mapped_block 和 tail_blkaddr 两个全局变量，其实相当于用来记录已分配内容的指针。last_mapped_block 记录最后一个已经映射了的 bb ，下一次划分从该 bb 的 next 开始。而 tail_blkaddr 记录当前已经分配好的 block 号

static erofs_blk_t __erofs_mapbh(struct erofs_buffer_block *bb)
{
	erofs_blk_t blkaddr;

	if (bb->blkaddr == NULL_ADDR) {
		bb->blkaddr = tail_blkaddr;
		last_mapped_block = bb;
		erofs_bupdate_mapped(bb);
	}

	blkaddr = bb->blkaddr + BLK_ROUND_UP(bb->buffers.off);
	if (blkaddr > tail_blkaddr)
		tail_blkaddr = blkaddr;

	return blkaddr;
}

erofs_blk_t erofs_mapbh(struct erofs_buffer_block *bb)
{
	struct erofs_buffer_block *t = last_mapped_block;

	if (bb && bb->blkaddr != NULL_ADDR)
		return bb->blkaddr;
	do {
		t = list_next_entry(t, list);
		if (t == &blkh)
			break;

		DBG_BUGON(t->blkaddr != NULL_ADDR);
		(void)__erofs_mapbh(t);
	} while (t != bb);
	return tail_blkaddr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

剩下的，就是确定 bb 被写入的顺序了。对此，笔者用 debug 日志的方式，进行跟踪。在 erofs_balloc 、dev_write 等出添加了 debug 输出。执行下述命令可以得到相应的日志输出 checkLog

./mkfs/mkfs.erofs -zlz4 /home/wonghiu/erofs_disk /home/srcd/ -d9 > checkLog
1

至此，我们根据 block 编号对应的顺序，可以画出如下镜像分布图

| meta | inode | compressed data | inode | compressed data|
0              1                 4       5                15
1
2

但上图似乎和论文中的镜像分布图有较大出入，例如没有看到 block index （是我理解错了吗：）（ps：下文会解释，确实我理解错了）

同时，我们可以知道，几个规则：

1. 对于为 DATA 申请的 bb , 只是用来占坑的，用于通过 mapbh 得到 data 应写入的 offset 位置。当 data 写入镜像后，便会将其释放。也不会让其他文件数据共用。但 tail_bldaddr 需要更新到相应位置。
2. 对于为 INODE 以及 META 申请的 bb , 会在 compressed data 持久化完成后才被写入镜像。并且 inode 是可以共用同个 bb 的，意味着 inode 会存放在一起

至此， block 管理基本梳理完成。目前困惑我的问题是，上述结构如何索引？即如何进行解压呢？索引定位需要用到哪些数据结构？

定位流程梳理

此时需要回顾一下 erofs_inode 结构。省略了部分属性。

struct erofs_inode {
	struct list_head i_hash, i_subdirs, i_xattrs;
	struct erofs_inode *i_parent;
	umode_t i_mode;
	erofs_off_t i_size;
	u64 i_ino[2];
	union {
		u32 i_blkaddr;
		u32 i_blocks;
		u32 i_rdev;
		struct {
			unsigned short	chunkformat;
			unsigned char	chunkbits;
		};
	} u;
	char i_srcpath[PATH_MAX + 1];
	unsigned char inode_isize;
	erofs_nid_t nid;
	struct erofs_buffer_head *bh;
	struct erofs_buffer_head *bh_inline, *bh_data;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

1. 首先从镜像中获取超级块 super_block。（很好定位
2. 从 sb 中获取根目录 root_dir 的 nid，nid 能够唯一指向镜像某个 offset
3. 通过 nid 读取 root_dir 的 inode。inode 中的 u.i_blkaddr 表示其数据块的块号。（数据块都是整块存储的不能共用，因此可以用块号直接索引）
4. 根据 u.i_blkaddr 获取到根目录文件内容，其为目录项
5. 根据目录项可找到对应文件的 nid
6. 根据 nid 获取文件的 inode
7. 通过 inode.u.i_blkaddr 找到文件数据块进行读取
8. 读取到内存后进行解压，返回给用户

上述流程属于解压流程，在制作镜像过程中，对应其逆操作，我们来看看源码

写入超级块

main
    --- erofs_buffer_init ： 申请超级块 sb_bh
    --- erofs_mkfs_update_super_block : 更新超级块属性，并添加 bh->op
    --- erofs_bflush : 调用 bh->op ，将超级块写入镜像
1
2
3
4

1. 首先通过 erofs_buffer_init 申请了 sb_bh ，由于是第一个执行 erofs_balloc 的，因此申请到的sb_bh 指向的 bb 对应镜像起始位置。因此解压时，读取很方便
2. erofs_mkfs_update_super_block 对 sb_bh 内容进行更新，特别地，主要将 sb 超级块结构体写入一个 buf 中，并将 buf 放入 sb_bh.fsprivate。并设置 bh->op = &erofs_buf_write_bhops
3. erofs_bflush 会将 bb 链上所有 bb 对应的 bh 内容进行刷盘。具体地会调用每个 bh->op->flush 。对应 sb_bh 便是 erofs_buf_write_bhops.flush = erofs_bh_flush_buf_write -->erofs_bh_flush_generic_write
4. erofs_bh_flush_generic_write 便是将 sb_bh.fsprivate 通过 dev_write 写入 bb 对应的镜像位置中

int erofs_bh_flush_generic_write(struct erofs_buffer_head *bh, void *buf)
{
	struct erofs_buffer_head *nbh = list_next_entry(bh, list);
	erofs_off_t offset = erofs_btell(bh, false);

	DBG_BUGON(nbh->off < bh->off);
	return dev_write(buf, offset, nbh->off - bh->off);
}
int erofs_mkfs_update_super_block(struct erofs_buffer_head *bh,
				  erofs_nid_t root_nid,
				  erofs_blk_t *blocks)
{
	struct erofs_super_block sb = {
	};
	const unsigned int sb_blksize =
		round_up(EROFS_SUPER_END, EROFS_BLKSIZ);
	char *buf;
	sb.root_nid     = cpu_to_le16(root_nid);
	buf = calloc(sb_blksize, 1);
	memcpy(buf + EROFS_SUPER_OFFSET, &sb, sizeof(sb));
	bh->fsprivate = buf;
	bh->op = &erofs_buf_write_bhops;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

设置Root_nid

在 erofs_mkfs_update_super_block 将 root_nid 更新到了 sb 中，而 root_nid 通过 erofs_lookupnid 获得。其计算方式为 (off - meta_offset) >> EROFS_ISLOTBITS。在这里提一下 erofs_btell，在之前分析过，bh 有 off 属性，表示 bh 在其对应 bb 中的偏移量。而 bb 有一个 blkaddr 属性，表示 bb 对应镜像中的块号。那么 erofs_btell 就是用来计算 bh 的 off 在镜像中的偏移。其等于 bh.off + blkaddr*blksize

main
    --- root_nid = erofs_lookupnid(root_inode);
1
2

erofs_nid_t erofs_lookupnid(struct erofs_inode *inode)
{
	struct erofs_buffer_head *const bh = inode->bh;
	erofs_off_t off, meta_offset;

	if (!bh)
		return inode->nid;

	erofs_mapbh(bh->block);
	off = erofs_btell(bh, false);

	meta_offset = blknr_to_addr(sbi.meta_blkaddr);
	DBG_BUGON(off < meta_offset);
	return inode->nid = (off - meta_offset) >> EROFS_ISLOTBITS;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

写入 inode

与 sb 的写入类似，需要先申请一个 bh ,然后将 inode 结构体放入 bh.fsprivate 中，并设置 bh->op ，后续等待 erofs_bflush 进行刷新。具体地，该过程在 erofs_prepare_inode_buffer 中，其调用链为

main
    --- erofs_mkfs_build_tree
    	--- erofs_prepare_inode_buffer
1
2
3

static int erofs_prepare_inode_buffer(struct erofs_inode *inode)
{
	unsigned int inodesize;
	struct erofs_buffer_head *bh, *ibh;
	inodesize = inode->inode_isize + inode->xattr_isize;

	bh = erofs_balloc(INODE, inodesize, 0, inode->idata_size);

	bh->fsprivate = erofs_igrab(inode);
	bh->op = &erofs_write_inode_bhops;
	inode->bh = bh;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

写入文件数据

写文件数据流程在前一节已进行过梳理，具体地，文件分为普通文件和目录文件

目录文件

erofs_mkfs_build_tree
    --- erofs_prepare_dir_file
    --- erofs_write_dir_file
1
2
3

在 erofs_mkfs_build_tree 中，首先通过 erofs_prepare_dir_file 为目录文件映射好 blkaddr 地址，在 erofs_write_dir_file 中，遍历每个目录项 dentry , 将其写入 blkaddr 中

erofs_write_dir_file 根据目录 inode , 遍历每个目录项，并调用 write_dirblock 将文件内容写入对应的 i_blkaddr+blkno 中

具体地，erofs_prepare_dir_file 会调用 allocate_inode_bh_data 为 dir 申请 bb 数据块。在 allocate_inode_bh_data 中会为申请的 bh 挂上 erofs_skip_write_bhops （该 fun 为空 fun），并设置 i_blkaddr

int erofs_prepare_dir_file(struct erofs_inode *dir, unsigned int nr_subdirs)
{
	struct erofs_dentry *d, *n, **sorted_d;
	unsigned int d_size, i_nlink, i;
	int ret;
	/* allocate dir main data */
	ret = __allocate_inode_bh_data(dir, erofs_blknr(d_size));
	if (ret)
		return ret;

	/* it will be used in erofs_prepare_inode_buffer */
	dir->idata_size = d_size % EROFS_BLKSIZ;
	return 0;
}
static int __allocate_inode_bh_data(struct erofs_inode *inode,
				    unsigned long nblocks)
{
	struct erofs_buffer_head *bh;
	int ret;

	if (!nblocks) {
		/* it has only tail-end data */
		inode->u.i_blkaddr = NULL_ADDR;
		return 0;
	}

	/* allocate main data buffer */
	bh = erofs_balloc(DATA, blknr_to_addr(nblocks), 0, 0);
	if (IS_ERR(bh))
		return PTR_ERR(bh);

	bh->op = &erofs_skip_write_bhops;
	inode->bh_data = bh;

	/* get blkaddr of the bh */
	ret = erofs_mapbh(bh->block);
	DBG_BUGON(ret < 0);

	/* write blocks except for the tail-end block */
	inode->u.i_blkaddr = bh->block->blkaddr;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

erofs_write_dir_file 会根据上一步申请好的 blkaddr ，遍历 dir->i_subdirs 将 dentry 内容通过 write_dirblock 写入镜像

static int erofs_write_dir_file(struct erofs_inode *dir)
{
	struct erofs_dentry *head = list_first_entry(&dir->i_subdirs,
						     struct erofs_dentry,
						     d_child);
	struct erofs_dentry *d;
	int ret;
	unsigned int q, used, blkno;

	q = used = blkno = 0;

	list_for_each_entry(d, &dir->i_subdirs, d_child) {
		const unsigned int len = strlen(d->name) +
			sizeof(struct erofs_dirent);

		if (used + len > EROFS_BLKSIZ) {
			ret = write_dirblock(q, head, d,
					     dir->u.i_blkaddr + blkno);
			if (ret)
				return ret;

			head = d;
			q = used = 0;
			++blkno;
		}
		used += len;
		q += sizeof(struct erofs_dirent);
	}

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

可以见得，目录文件的写入不需要像普通文件一样进行压缩，并且相较于普通文件更简单

普通文件

在此对普通文件重新进行一次梳理，因为前面的笔记有些混乱。主函数为 erofs_write_compressed_file。其调用链如下

erofs_mkfs_build_tree
    --- erofs_write_file
    	--- erofs_write_compressed_file
    		--- z_erofs_write_mapheader
    		--- vle_compress_one
    			--- erofs_compress_destsize
    			--- blk_write
    			--- vle_write_indexes
    		--- vle_write_indexes_final
    		--- inode->compressmeta = compressmeta
1
2
3
4
5
6
7
8
9
10

进入 erofs_write_compressed_file 即开始执行普通文件数据内容的压缩，在前面笔记中，梳理了 vle_compress_one 的迭代压缩流程。但在压缩开始之前，需要通过 z_erofs_write_mapheader 初始化压缩元数据 compressmeta 。

而 compressmeta 就是用于记录论文中 block index 的结构。其会被写入 inode 的 compressmeta 属性中，随着 inode 一起被刷盘。

在 vle_compress_one 中首先通过 erofs_compress_destsize 进行数据的压缩，进而调用 blk_write 进行数据具体内容的读写，每轮迭代的最后会调用 vle_write_indexes 将相应 index 记录于 compressmeta 中

对于 vle_write_indexes 的细节就不展开了