EROFS在快速迭代中出现了许多新特性，而文档并不丰富。本文试图基于erofs-utils的1.3版本摸清压缩文件在EROFS中的on-disk存储格式和用户态文件读取的关键路径，并根据commit信息看懂后续版本的更新。

本文主要关注读取（解压）的流程，基本不涉及压缩侧的特性（如dedupe）。

压缩文件on-disk索引

EROFS将文件未压缩的原始数据划分为若干个lcluster(Logical Cluster)，固定输出大小的压缩数据单元则称为pcluster(Physical Cluster)。其中lcluster的大小是固定的，等于块大小(4K)，pcluster则可以由若干个连续块组成。文件索引的任务就是将给定的逻辑地址（区间）翻译成磁盘上的物理地址（区间）。对于压缩文件，EROFS支持Legacy和Compacted两种索引格式，根据dinode中i_format字段嵌入的datalayout加以区分。

Legacy index

Legacy索引的结构如图所示。每个inode在可选的xattr区域之后存储压缩索引，其中黄色部分struct z_erofs_map_header是per-inode的元数据，占据8个字节，后面跟着8字节的padding。它记录了inode层面开启的压缩特性(h_advice)，使用的压缩算法类型(h_algorithmtype)和lcluster的大小（h_clusterbits，目前实现中为常数）。

紧随其后的是若干个8字节结构体struct z_erofs_vle_decompressed_index，它是一个4KB lcluster的索引，定义如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct z_erofs_vle_decompressed_index {
	__le16 di_advise;
	/* where to decompress in the head cluster */
	__le16 di_clusterofs;

	union {
		/* for the head cluster */
		__le32 blkaddr;
		/*
		 * for the rest clusters
		 * eg. for 4k page-sized cluster, maximum 4K*64k = 256M)
		 * [0] - pointing to the head cluster
		 * [1] - pointing to the tail cluster
		 */
		__le16 delta[2];
	} di_u;
};
其中，di_advice记录了lcluster的种类。PLAIN类型的lcluster未被压缩，以原始数据的格式映射到一个长度为1个block的pcluster中去；HEAD类型的lcluster是一段extent的起始lcluster，它代表这个extent中的一系列lcluster映射到了某个pcluster，并存储了pcluster的物理地址(blk_addr)。该extent中剩余的lcluster则为NONHEAD lcluster，它记录了与前一个HEAD lcluster和后一个HEAD lcluster的距离(delta[0]和delta[1])。

需要注意的是，一段extent并不一定对齐到lcluster的边界。这意味着某个lcluster的前一部分和后一部分可能从属于不同的extent。在这种情况下，这个lcluster的类型是HEAD，并且di_clusterofs是非0值，记录了extent起始位置在该lcluster中的偏移量。

上图给出了一个例子。图中lcluster0, lcluster1以及lcluster2的前1024字节组成了第一个extent，映射到物理地址为0x233000；lcluster2的剩余部分属于第二个extent，映射到物理地址为0x234000的pcluster。两个pcluster的长度均为1个块大小。因此lcluster0和lcluster2都是HEAD lcluster，且di_clusterofs分别为0和1024。lcluster1是NONHEAD lcluster，并且与前后HEAD lcluster的距离都是1。

Big pcluster

在map_block的时候，作为压缩文件系统，EROFS要同时给出extent的llen和plen。早期版本的EROFS要求pcluster的大小等于块大小(4KB)，因此可以假设plen的长度就是4KB。Linux v5.13引入了big pcluster特性，它允许pcluster的大小为块大小的倍数。于是，我们需要在文件索引中记录这个大小。

EROFS选择将pcluster大小记录在组成extent的第一个NONHEAD lcluster中。这个lcluster被称为CBLKCNT lcluster，它的delta[0]一定是1，因此可以复用delta[0]的空间。这种情况下，delta[0]中的Z_EROFS_VLE_DI_D0_CBLKCNT被设为1。如果某个extent没有NONHEAD lcluster，说明它对应的pcluster长度一定只能是1个块大小。

如图所示，由于第一个pcluster的大小是8192（2个块大小），因此对应extent中的第一个NONHEAD lcluster的delta[0]记录了0x2 | 1 << (Z_EROFS_VLE_DI_D0_CBLKCNT)。

Compacted Index

Legacy Index的一大缺点是对于每个4KB大小的lcluster，都要记录一个8字节的索引，导致了不必要的空间占用。Compacted Index的核心思想就是压缩文件索引所占用的空间。EROFS把相邻若干个lcluster的索引编码在一起，称为pack。每个pack需要预留4字节来存放某一个extent对应的起始pcluster地址，由于单个文件的pcluster是连续的，其他extent的物理地址可以根据该地址推算出来。

具体来说，EROFS支持compacted_2B和compacted_4B两种索引格式，归约后每个lcluster索引分别需要占用2字节和4字节的存储空间：

  • 2B: 每个lcluster索引包含14个位，每16个索引为一个pack，pack大小为\((14 * 16 + 32) / 8 = 32\)字节。
  • 4B: 每个lcluster索引包含16个位，每2个索引为一个pack，pack大小为\((16 * 2 + 32) / 8 = 8\)字节。

可见，2B和4B的索引格式分别需要32字节和8字节对齐，以保证它们不会跨越块边界。因此EROFS使用2B索引作为compacted index的主体部分，使用4B索引作为前后填充来满足32字节的对齐要求。

14位lcluster索引的使用：一共有3种不同类型的lcluster，因此需要2个位来存储其类型。对于HEAD和PLAIN lcluster，剩余12个位用来存储clusterofs；对于NONHEAD lcluster，存在3种情况：

  1. CBLKCNT lcluster：存储pcluster大小。
  2. 恰好位于一个pack的最后：存储delta[1]。
  3. 其他情况：存储delta[0]。

每个pack中只会存一个pcluster的地址：

  • 当不开启big pcluster特性时，该地址为pack中第一个HEAD/PLAIN lcluster所对应的pcluster地址减去一个块大小。
  • 当开启big pcluster特性时，该地址为pack中第一个新开启的extent所对应的pcluster地址。对于一般extent，新开启即HEAD/PLAIN lcluster落在该pack中；对于映射到big pcluster的extent，新开启即CBLKCNT lcluster（而不是HEAD lcluster）落在该pack中。

v1.4

fiemap

在一般的解压流程中，如果read()读取的最后一个extent是不完整的，EROFS可以部分解压pcluster来满足读取请求，而不需要计算该extent的完整长度。如图所示，黄色部分标识了第一次返回的map->m_la和map->llen，它并不是一个完整的extent。

然而，存在一个ioctl选项fiemap，它从用户态获取文件的extent。于是EROFS引入了z_erofs_get_extent_decompressedlen()函数，用于在这种情况下计算完整的extent长度。它在带有EROFS_GET_BLOCKS_FIEMAP flag的z_erofs_do_map_blocks()中被调用。

对于legacy索引，extent长度可以简单从存储的delta[1]中获取，不需引入任何额外逻辑。然而对于compacted索引，只有每个pack的最后一个lcluster才会存储delta[1]，因此这个过程需要向后遍历每个lcluster的索引，直到找到一个HEAD/PLAIN lcluster为止。遇到有效的delta[1]可以加速遍历过程。

v1.5

ztailpacking

对于未压缩文件，EROFS允许将文件末尾填不满一个块的数据内联在inode中，避免块对齐导致的空洞，让磁盘布局更加紧凑，而ztailpacking特性允许压缩文件的末尾数据也被内联。内联部分的数据可能是压缩的，也可能是未被压缩的。

实现上，per inode的struct z_erofs_map_header的h_advice会记录ztalipacking是否开启。此外，该结构体还维护了一个h_idata_size变量，存储内联部分数据的压缩后大小。

内联部分的起始位置在最后一个lcluster索引之后，可以使用带EROFS_GET_BLOCKS_FINDTAIL flag的z_erofs_do_map_blocks()计算。

启动ztailpacking特性时的镜像打包过程可以参见[2]。

v1.6

interlace pcluster

TBD

fragment

EROFS允许将若干个文件的一部分打包在一个packed_file中一起压缩，以此提高压缩率。这些部分称为fragment。一般来说，文件的tail部分会作为fragment，也可以将一个完整的文件作为fragment。

实现上，per inode的struct z_erofs_map_header的h_advice会记录该inode是否包含fragment。如果有的话，fragment的文件偏移量被记录在h_fragmentoff中。一个文件不可能同时包含fragment和开启ztailpacking特性，因此h_fragmentoff和h_idata_size位于同一个union中。

z_erofs_do_map_blocks()中，如果发现当前读取的extent是一个fragment，会设置EROFS_MAP_FRAGMENT标记。z_erofs_read_one_data()看到该标记后，会去packed_inode中根据记录的fragmentoff读取数据。

参考资料

  1. EROFS on-disk compact index 生成分析 - TJ的技术博客 (tjtech.me)

  2. EROFS ztailpacking 特性实现详解

  3. [PATCH v3 1/8] staging: erofs: add compacted ondisk compression indexes - Gao Xiang (kernel.org)

  4. EROFS - Enhanced Read-Only File System