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.
本站采用CC BY-NC-SA 4.0进行许可 | 转载请注明原文链接 - EROFS 碎片去重准备