因为 EROFS 就是奔着取代 SquashFS 去的(should be),之前我们已经添加了碎片的支持,但是不支持去重。先大概看下 SquashFS 碎片去重是怎么做的。知己知彼,才能百战百胜。

Check SquashFS 碎片去重

参考 squashfs-tools 4.5.1

/* hash tables used to do fast duplicate searches in duplicate check */
struct file_info **dupl_frag;

定义了一个 hash table 用来快速查找重复的碎片。这个 table 是怎么用的呢,能看到这样的使用:

/* Look for a possible duplicate fragment */
if(fragment_size) {
for(dupl_ptr = dupl_frag[fragment_size]; dupl_ptr; dupl_ptr = dupl_ptr->frag_next)
if(dupl_ptr->fragment->size == fragment_size) {
return TRUE;
}
}

也就是把 fragment_size 碎片大小用作 hash value。so,只有相同大小的碎片才能去重?继续看:

static struct file_info *frag_duplicate(struct file_buffer *file_buffer, int *duplicate)

frag_duplicate()这函数名起的,是要做去重 dedupe吗?看着落款 Phillip Lougher phillip@squashfs.org.uk 应该是大英的。

/* Look for a possible duplicate fragment */
if(frag_bytes) {
for(dupl_ptr = dupl_frag[frag_bytes]; dupl_ptr; dupl_ptr = dupl_ptr->frag_next) {
if(frag_bytes == dupl_ptr->fragment->size && fragment_checksum == get_fragment_checksum(dupl_ptr)) {
/* Checksums match, so now we need to do a byte by byte comparison */
struct file_buffer *frag_buffer = get_fragment(dupl_ptr->fragment);
int res = memcmp(file_buffer->data, frag_buffer->data + dupl_ptr->fragment->offset, frag_bytes);

cache_block_put(frag_buffer);

if(res == 0) {
/* Yes, the fragment matches. This file may have
* a matching block list and fragment, in which case
* we're finished. */
if(block_dupl && block_dupl->start == dupl_ptr->start) {
*dupf = *block_dup = TRUE;
return dupl_ptr;
}

ok, 看了上面这一段,基本逻辑就是 fragment_size 碎片大小相同而且 fragment_checksum 相同时然后再看内容是否一致。”Am i missing sth?” (mmm…留点退路不流破绽)

简要回顾下哈希

A hash function is any function that can be used to map data of arbitrary size to fixed-size values. The values returned by a hash function are called hash values, hash codes, digests, or simply hashes. The values are usually used to index a fixed-size table called a hash table. Use of a hash function to index a hash table is called hashing or scatter storage addressing.

A hash table is typically an array of linked lists.

需要留意的是 hash table size 若过小 + link list 长度过长,效率低点, 就是 collision 的问题,不多说,知道这个即可。

EROFS 碎片去重

f哥,长度短点的不能去重么。可以使用 16bits checksum 作为 hash, table size 就 64KB。

我的想法比较简单也比较好写,就是顺着当前逻辑,在 packing fragment 分支时查表。但是有个问题,就是大碎片只有部分重复的怎么办?

Gao Xiang 建议在压缩前做去重,这样做的好处是避免把一部分重复的碎片写到 packed inode 里。不过改起来有点别扭,因为压缩 final 时要返回再读文件重新压缩。这种做法也解决了上面的疑问,rt?

Now, let’s do it.