15 · 特性专题：rolling-hash 去重（dedupe）

特性标志：EROFS_FEATURE_INCOMPAT_DEDUPE（internal.h） 内核侧代码：很少——主要在 decompressor.c（处理 deduped 页）与 sysfs 暴露 重要：本特性以 mkfs 侧为主，内核只负责”认得它 + 正确处理去重页”

本文回答：为什么压缩之后还要去重 → rolling hash 怎么找到重复块 → 内核这边的少量工作是什么 → fillgaps 为什么关键 → 与 fragment 的区别（06 专题点名最容易混淆）。

本专题目标（读完你应该能做到什么）

1. 说清去重解决什么问题，以及为什么压缩之后仍需要去重
2. 解释 rolling hash（滚动哈希） 的基本思路（不要求懂算法细节）
3. 说明 ⚠️ 内核侧几乎不做去重——重头戏在 mkfs
4. 解释 fillgaps 字段为什么是内核侧的关键（并联系 D12 缺陷）
5. 清楚区分 dedupe 与 fragment（最容易混淆的一对）
6. 知道怎么确认一个镜像启用了 dedupe

图解

一句话：mkfs 用 rolling hash 找出跨文件的相同块、只存一份，其余位置标成”引用”； 内核不算哈希，只需认得这种 pcluster（partial-referenced）并正确解压。

自上而下五段 + 底部澄清：

⚠️ 底部红框的三件事（都比想象中容易搞混）：

1. 一个机制三个名字 —— rolling hash = variant-CDC = 内核的 partial-referenced pcluster，是同一件事换了三种说法。
2. dedupe ≠ fragment —— 前者消跨文件相同块，后者收压缩零头； 两者在 mkfs 侧是两个独立开关（-Ededupe / -Efragdedupe）。
3. 位别名（冷知识） —— EROFS_FEATURE_INCOMPAT_DEDUPE 与 EROFS_FEATURE_INCOMPAT_FRAGMENTS 都是 0x00000020， 所以开了 dedupe 的镜像，erofs_sb_has_fragments() 同样为真 ⇒ 挂载时也会去 igot packed inode（即使这份镜像其实没有 fragment）。

一、特性缘由：压缩之后为什么还要去重

1.1 压缩解决不了的重复

压缩（LZ4/LZMA 等）消除的是单个文件内部的冗余。 但下面这种重复它管不了：

文件 A： [块1][块2][块3][块4]
文件 B： [块1][块2][块3][块4]     ← 与 A 完全相同的四个块

压缩算法各自处理各自的文件， 不会发现”文件 B 的内容其实和文件 A 一样”。

⇒ 磁盘上存了两份。

1.2 场景：容器镜像里大量重复

容器镜像中这种”跨文件重复”极其常见：

• 多个镜像基于同一个基础层
• 不同路径下的相同库文件
• 升级前后只改了一点的大文件

⇒ 去重能省下相当可观的磁盘空间。

1.3 怎么做：找出相同的数据块

思路很朴素：

把每个 pcluster 的内容算个哈希， 哈希相同的就只存一份。

难点在于效率：如果按固定边界切块， 插入/删除一点内容就会让后面所有块的边界错位，去重率暴跌。

⇒ 这就是 rolling hash（滚动哈希） 的用武之地—— 它能在任意位置高效地计算滑动窗口的哈希， 从而找到”内容相同但位置不同”的块。

二、设计理念

理念 1：把去重放在 mkfs，不在内核

这是理解本特性的关键：

为什么？

• 去重需要全局扫描与大量计算——构建时做一次远比运行时做划算
• 内核是只读的，运行时去重既无必要也太慢

⇒ 内核侧的代码量很小。看到 INCOMPAT_DEDUPE 这个 feature flag 基本就代表了内核的”认知”程度。

理念 2：用 incompat 标志保护

EROFS_FEATURE_FUNCS(dedupe, incompat, INCOMPAT_DEDUPE)

incompat 意味着：不认识这个特性的内核不能挂载该镜像。

原因很直接——去重改变了数据的组织方式， 老内核按常规方式读会读到错的东西。宁可拒绝挂载。

理念 3：去重页 —— 给未认领的输出槽补一个临时页

解压时，如果某个输出槽没有预先认领的目标页（decompressed_pages[i] == NULL）， 内核需要知道怎么处理它。

这就是 fillgaps 的作用（见下）。

三、实现架构

3.1 内核侧：不算哈希，但要认得「partial-referenced pcluster」

内核里没有 rolling hash 的实现。它实际做的是四步：

① 挂载时：识别 INCOMPAT_DEDUPE 特性
      └ 不认识 → 拒绝挂载（incompat 语义）（见宏定义 EROFS_ALL_FEATURE_INCOMPAT）

② 映射时（zmap.c）：从磁盘标志位认出"这段是引用"
      └ m->partialref = !!(advise & Z_EROFS_LI_PARTIAL_REF)
      └ if (m.partialref)  map->m_flags |= EROFS_MAP_PARTIAL_REF
        （extents 形态则看 Z_EROFS_EXTENT_PLEN_PARTIAL）

③ 组装解压请求（zdata.c）：把这个事实带下去
      └ .partial_decoding = pcl->partial
      └ .fillgaps         = be->keepxcpy      ← ★ D12 缺陷点

④ 解压时（decompressor.c）：两个开关各管一件事
      └ if (rq->partial_decoding)   → 只解压其中一部分（还影响能否 in-place）
      └ if (!*pgo && rq->fillgaps)  → 空隙槽：分配一页作为解压落点（不置零）

这是两条并行的线索，别混成一条：

⇒ 全程没有哈希计算、没有重复查找——找重复全是 mkfs 的活。 内核的贡献是”认得它 + 把它解对”。

3.2 关键：fillgaps 字段

struct z_erofs_decompress_req（compress.h）里的 fillgaps：

bool inplace_io, partial_decoding, fillgaps;

含义：输出里有”空隙”（gap，即未被整页认领的输出槽）时，是否分配一个临时页接住解压输出。

• fillgaps = true → 为该槽分配一个临时页（erofs_allocpage() → alloc_page()，不带 __GFP_ZERO，不会置零）
• fillgaps = false → 跳过，不分配

⇒ 如果 fillgaps 传错，deduped 页可能没有正确初始化， 读到错误数据。

⚠️ fillgaps 不是 dedupe 专用：decompressor_deflate.c 与 decompressor_zstd.c 里都会无条件写 rq->fillgaps = true （注释原文：”DEFLATE/ZSTD doesn’t support NULL output buffer”）。 所以「fillgaps 为真」不能反推「这一页是 deduped 页」。

📌 这与 D12 缺陷直接相关： z_erofs_decompress_queue() 里 be.keepxcpy 未初始化， 而它被当作 rq.fillgaps 传下去（fillgaps = be->keepxcpy）—— 栈上的垃圾值会导致 deduped 页处理错误。

3.3 sysfs 暴露

EROFS_ATTR_FEATURE(dedupe);

挂载后可通过 /sys/fs/erofs/<dev>/features 看到该特性是否启用。

四、关键结构体与字段

4.1 struct z_erofs_decompress_req（compress.h）

本特性唯一直接相关的字段就是 fillgaps。

4.2 feature 标志（internal.h）

EROFS_FEATURE_FUNCS(dedupe, incompat, INCOMPAT_DEDUPE)

展开出 erofs_sb_has_dedupe(sbi) 之类的辅助函数。

4.3 erofs_sb_info

u32 feature_incompat;      /* INCOMPAT_DEDUPE 位在这里 */

五、主要函数

内核侧确实没有“dedupe 专属的算法函数”（没有 rolling hash、没有查重），
但”认标志位 → 打标记 → 带进解压请求 → 决定怎么解压“这条链路是实打实存在的：

5.1 zmap.c：认出「这段是引用」

去重的产物落到 on-disk 上就是一个标志位。两种 inode 形态各有一处读法。

noncompact 形态 —— z_erofs_load_lcluster_from_disk() 从 lcluster index 的 advise 位取：

} else {
        m->partialref = !!(advise & Z_EROFS_LI_PARTIAL_REF);
        m->clusterofs = le16_to_cpu(di->di_clusterofs);
        ...

Z_EROFS_LI_PARTIAL_REF 是 1 << 15（erofs_fs.h），注释很直白： this pcluster refers to partial decompressed data。

随后在 z_erofs_map_blocks_fo() 末尾转成内核的映射标志：

if (m.partialref)
        map->m_flags |= EROFS_MAP_PARTIAL_REF;

extents 形态则把同一信息放在 m_plen 的高位（Z_EROFS_EXTENT_PLEN_PARTIAL，BIT(27)）：

if (map->m_plen & Z_EROFS_EXTENT_PLEN_PARTIAL)
        map->m_flags |= EROFS_MAP_PARTIAL_REF;
map->m_plen &= Z_EROFS_EXTENT_PLEN_MASK;

⇒ 两条路最终都落到 EROFS_MAP_PARTIAL_REF（0x0008），后面就统一了。

配套的判据在 internal.h：

#define EROFS_MAP_FULL(f)  (!((f) & (EROFS_MAP_PARTIAL_MAPPED | \
                              EROFS_MAP_PARTIAL_REF)))

即：既不是「部分映射」也不是「部分引用」，才算一张完整的映射。这个宏在 5.2 里很关键。

5.2 zdata.c：pcl->partial 什么时候为真

理解它的关键是：默认值为真。三处赋值：

① 新建 pcluster 时直接置 true：

lockref_init(&pcl->lockref);
pcl->algorithmformat = map->m_algorithmformat;
pcl->pclustersize = map->m_plen;
pcl->length = 0;
pcl->partial = true;

② 只有映射完整、且收齐的长度正好等于 m_llen 时，才改回 false（z_erofs_scan_folio()）：

if (EROFS_MAP_FULL(map->m_flags) &&
    f->pcl->length == map->m_llen)
        f->pcl->partial = false;

③ pcluster 用完后重置，又回到 true：

pcl->length = 0;
pcl->partial = true;
pcl->besteffort = false;

⇒ 去重产生的 pcluster 永远走不到第 ② 步——它带着 EROFS_MAP_PARTIAL_REF， EROFS_MAP_FULL() 恒为假，于是 partial 保持真。
这就是”只解压一部分”这个开关的来源。

5.3 zdata.c：把两个开关塞进解压请求

z_erofs_decompress_queue() 组装 z_erofs_decompress_req 时：

.in = be->compressed_pages,
.out = be->decompressed_pages,
...
.inplace_io = overlapped,
.partial_decoding = pcl->partial,
.fillgaps = be->keepxcpy,
.gfp = pcl->besteffort ? GFP_KERNEL : GFP_NOWAIT | __GFP_NORETRY

⚠️ 这两个开关的来源完全不同，别混为一谈：

后者正是 D12 缺陷：be.keepxcpy 未经初始化就被当作 rq.fillgaps 传下去， 栈上的垃圾值会让”空隙页该不该补”变成随机行为。

5.4 decompressor.c：partial_decoding 决定怎么解压

以 LZ4 为例（z_erofs_lz4_decompress()），这是本专题最落地的一处：

out = dst + rq->pageofs_out;
if (rq->partial_decoding)
        ret = LZ4_decompress_safe_partial(src + inputmargin, out,
                        rq->inputsize, rq->outputsize, rq->outputsize);
else
        ret = LZ4_decompress_safe(src + inputmargin, out,
                                  rq->inputsize, rq->outputsize);

• 普通压缩：整段解压（LZ4_decompress_safe）
• 去重产生的 partial pcluster：只解出需要的那一截 （_partial 版本，最后那个参数就是要的长度）
• LZMA 同样有对应分支（decompressor_lzma.c 里 !rq->partial_decoding）

它还影响能否 in-place（就地解压）：

if (!rq->partial_decoding && may_inplace &&
    omargin >= LZ4_DECOMPRESS_INPLACE_MARGIN(rq->inputsize)) {

⇒ 部分解压时不做 in-place —— 输出缓冲区的布局不满足就地解压的前提。

5.5 fillgaps：输出里的「空隙」怎么办

解压输出是一组页指针 rq->out[]。去重时某些槽位的内容与别处相同、 不需要重新产生，这些槽位可能是 NULL。
decompressor.c 里这样处理：

pgo = &rq->out[dctx->no];
if (!*pgo && rq->fillgaps) {            /* deduped */
        *pgo = erofs_allocpage(pgpl, rq->gfp);
        if (!*pgo) {
                dctx->kout = NULL;
                return ERR_PTR(-ENOMEM);
        }
        set_page_private(*pgo, Z_EROFS_SHORTLIVED_PAGE);
}

• fillgaps = true → 给这些空槽分配一页（内容为零），解压器有地方可写
• fillgaps = false → 跳过，不分配

⚠️ 它不是 dedupe 专用。DEFLATE / ZSTD 后端会无条件打开：

rq->fillgaps = true;    /* 后端不支持 NULL 输出缓冲（DEFLATE） */
rq->fillgaps = true;    /* 后端不支持 NULL 输出缓冲（ZSTD） */

所以不能由 fillgaps == true 反推”这一页是 deduped 页”。

5.6 两个「名不副实」的入口

⇒ 这也解释了 15 专题为什么说”内核侧代码量很小”：
真正的判据散落在zmap.c / zdata.c / decompressor.c 的既有路径里，dedupe 只是借道， 没有独立的一套代码。

mkfs 侧（不在内核，仅说明）：负责 rolling hash 计算、 重复判定、只写一份、记录引用关系。

六、来龙去脉：完整串一遍

① 构建镜像（mkfs，用户态）
     ├ 按 rolling hash 滑动窗口扫描所有压缩数据
     ├ 发现内容相同的块 → 只保留一份
     ├ 其余位置记为"引用"（deduped）
     └ 在 superblock 打上 INCOMPAT_DEDUPE 标志
        │
② 挂载（内核）
     ├ 读 feature_incompat
     ├ 若内核不认识 INCOMPAT_DEDUPE → 拒绝挂载
     └ 认识 → 继续
        │
③ 读某个文件，需要解压
        │
④ 组装 z_erofs_decompress_req
     └ fillgaps = be->keepxcpy     ← ★ 必须为确定值
        │
⑤ 解压后端处理输出页
     ├ 正常页：解压写入
     └ deduped 页（!*pgo）：
           if (rq->fillgaps) → 分配一个临时页（不置零）
        │
⑥ 数据完整 → 读完成

第 ⑤ 步是内核侧对 dedupe 的全部贡献： 认出”这个页是去重页”，给它一个置零的页。

七、动手验证

验证 1：确认内核侧特性定义

cd /sdd/linux/linux-stable/fs/erofs
grep -rn "dedupe\|INCOMPAT_DEDUPE" .

会看到：feature 定义、sysfs 暴露、以及 decompressor.c 里的 fillgaps 分支。 注意代码量很小——这本身就印证了”重头在 mkfs”。

验证 2：确认镜像是否启用 dedupe

/opt/erofs-utils/bin/dump.erofs -s /tmp/erofs-lab/comp2.erofs

看 superblock 的 incompat feature 里有没有 dedupe 位。

验证 3：VM 里看 sysfs

mount -t sysfs sysfs /sys
mount -t erofs /host/comp2.erofs /mnt
cat /sys/fs/erofs/*/features

输出里若含 dedupe 即表示启用。

验证 4：定位 fillgaps 的使用点

grep -rn "fillgaps" /sdd/linux/linux-stable/fs/erofs/

看它从哪来（be->keepxcpy）、在哪用。 顺便理解 D12 缺陷为什么会发生。

八、常见误解（重要）

误解 1：内核会做去重计算

不会。去重是 mkfs（构建时） 的工作。 内核只认特性标志 + 正确处理 deduped 页。

在内核里找”rolling hash 实现”是找不到的。

误解 2：dedupe 与 fragment 是一回事

不是（06 专题点名最容易混淆）：

误解 3：fillgaps 只是个无关紧要的标志

不是。它决定 deduped 页是否被正确初始化。 传错会导致数据错误——这正是 D12 缺陷的根因。

误解 4：老内核能读去重镜像（只是读不出内容）

不能挂载。INCOMPAT_DEDUPE 是 incompat 特性， 不认识它的内核会直接拒绝挂载（而不是”读错”）。

误解 5：feature 位能区分 dedupe 与 fragment

不能。erofs_fs.h 里 EROFS_FEATURE_INCOMPAT_DEDUPE 与 EROFS_FEATURE_INCOMPAT_FRAGMENTS 都是 0x00000020——同位别名。

后果：开了 dedupe 的镜像，erofs_sb_has_fragments() 同样返回真， 挂载时也会去 igot packed inode（只要 packed_nid 非 0）。

内核真正的区分发生在更细的层面：
lcluster index 的 advise 位 Z_EROFS_LI_PARTIAL_REF、 / extent 的 m_plen 高位 Z_EROFS_EXTENT_PLEN_PARTIAL 标志位。

误解 6：去重会让解压变慢

基本不会。去重省的是磁盘空间， 解压侧多出来的开销只是：为未被整页认领的输出槽分配临时页（一次 alloc_page()）， 不会引入第二轮解压。

九、与其他特性的关系

自测检查点

1. 为什么压缩之后还需要去重？
2. rolling hash 解决什么问题？（不要求算法细节）
3. ⚠️ 去重主要在内核还是 mkfs 做？为什么？
4. INCOMPAT_DEDUPE 是 incompat 意味着什么？
5. fillgaps 字段的作用是什么？传错会怎样？
6. fillgaps 与哪个真实缺陷相关？
7. dedupe 与 fragment 的三点区别？
8. 内核侧对 dedupe 做了哪四步？partial_decoding 与 fillgaps 各管什么？
9. 怎么确认一个镜像启用了 dedupe？
10. deduped 页在解压时是怎么被处理的？

自测答案

参考

linux-stable
EROFS 官方文档 Release 0.1

• Previous
  EROFS fragment and ztailpacking
• Next
  EROFS trace fragment/ztailpacking reading-path