EROFS 碎片去重准备

因为 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.