erofs-utils: mkfs: support fragment deduplication
PATCH v6 1/1 erofs-utils: mkfs: support fragment deduplication
From: Yue Hu <[email protected]>
Previously, there's no fragment deduplication when this feature is introduced. Let's support it now.
Fragments are deduplicated before compression, so that duplicated parts will not be written into the packed inode.
---
v6:
- add fragemitted in ctx and move frag ctx generating after vle_compress_one
- add a jumping label for fixing flow in vle_compress_one
- increase EROFS_CONFIG_COMPR_MAX_SZ
- new variable naming include tof_chksum, fix_dedupedfrag in ctx, len_to_hash -> EROFS_TOF_HASHLEN
- refine the interface of z_erofs_fragments_dedupe_update, rename it to z_erofs_fixup_deduped_fragment
- refine list_for_each_entry in dedupe
- code comments/commit message minor update
v5:
- fix the issue that decompression may fail when ztailpacking is enabled as well
- fix the issue that decompression may fail when dedupe is enabled as well in v4
- minor commit message update
v4:
- renaming include tofcrc/new_fragmentsize
- move fixup into ctx
- use may_fixing to check packing fragment or not
- move sb/inode flag + 64bits case from erofs_pack_fragments() to new helper erofs_fragments_commit()
- move recompress ahead of may_inline case when compressing succeeds
- update commit message/code comments
- change to generate a ctx for duplicate fragment in compression
- note that decompress will fail when enable ztailpacking at the same time, need some time to debug
v3:
- modify acrroding to Xiang's comments in v2
- simplify the logic in vle_compress_one
- fix the crash for 1MB pcluster
v2: mainly improve the logic in compression
include/erofs/compress.h | 3 +- include/erofs/fragments.h | 4 +- lib/compress.c | 133 +++++++++++++++++++++----- lib/fragments.c | 193 ++++++++++++++++++++++++++++++++++++-- 4 files changed, 299 insertions(+), 34 deletions(-)
include/erofs/compress.h +1 -2
@@ -14,8 +14,7 @@ extern "C"#include "internal.h" -#define EROFS_CONFIG_COMPR_MAX_SZ (3000 * 1024) -#define EROFS_CONFIG_COMPR_MIN_SZ (32 * 1024) +#define EROFS_CONFIG_COMPR_MAX_SZ (4000 * 1024)void z_erofs_drop_inline_pcluster (struct erofs_inode *inode);int erofs_write_compressed_file (struct erofs_inode *inode,int fd);
include/erofs/fragments.h +3 -1
@@ -15,8 +15,10 @@ extern "C"extern const char *frags_packedname;#define EROFS_PACKED_INODE frags_packedname +int z_erofs_fragments_dedupe (struct erofs_inode *inode,int fd,u32 *tofcrc);int z_erofs_pack_fragments (struct erofs_inode *inode,void *data, -unsigned int len); +unsigned int len,u32 tofcrc); +void z_erofs_fragments_commit (struct erofs_inode *inode);struct erofs_inode *erofs_mkfs_build_fragments (void );int erofs_fragments_init (void );void erofs_fragments_exit (void );
lib/compress.c +109 -24
252 lines not on this page · raw message
lib/fragments.c +186 -7
227 lines not on this page · raw message
Signature · 1 line
2.17.1
Quoted 10 lines · Yue Hu
From: Yue Hu <[email protected]>
Previously, there's no fragment deduplication when this feature is introduced. Let's support it now.
Fragments are deduplicated before compression, so that duplicated parts will not be written into the packed inode.
Suggested-by Gao Xiang <[email protected]>Signed-off-by Yue Hu <[email protected]>
I'd like to submit it with minor update:
lib/compress.c +2 -2
@@ -349,8 +349,8 @@ static bool z_erofs_fixup_deduped_fragment(struct z_erofs_vle_compress_ctx *ctx, inode->fragmentoff += inode->fragment_size - newsize; inode->fragment_size = newsize; -erofs_dbg ("Reducing fragment size to %u at %lu" , - inode->fragment_size, inode->fragmentoff); +erofs_dbg ("Reducing fragment size to %u at %llu" , + inode->fragment_size, inode->fragmentoff |0ULL );/* it's the end */ ctx->head += newsize;
lib/fragments.c +7 -10
@@ -22,10 +22,10 @@ struct erofs_fragment_dedupe_item {#define EROFS_TOF_HASHLEN 16 -#define FRAGMENT_HASHTABLE_SIZE 65536 -#define FRAGMENT_HASH (crc) (crc & (FRAGMENT_HASHTABLE_SIZE - 1)) +#define FRAGMENT_HASHSIZE 65536 +#define FRAGMENT_HASH (c) ((c) & (FRAGMENT_HASHSIZE - 1)) -static struct list_head dupli_frags[FRAGMENT_HASHTABLE_SIZE ]; +static struct list_head dupli_frags[FRAGMENT_HASHSIZE ];static FILE *packedfile;const char *frags_packedname ="packed_file" ;
@@ -98,8 +98,8 @@ static int z_erofs_fragments_dedupe_find(struct erofs_inode *inode, int fd, inode->fragment_size = di->nr_dup; inode->fragmentoff = di->pos + di->length - di->nr_dup; -erofs_dbg ("Dedupe %u fragment data at %lu" , inode->fragment_size, - inode->fragmentoff); +erofs_dbg ("Dedupe %u tail data at %llu" , inode->fragment_size, + inode->fragmentoff |0ULL ); out:free (data);return ret;
@@ -156,7 +156,7 @@ static void z_erofs_fragments_dedupe_init(void) {unsigned int i; -for (i =0 ; i <FRAGMENT_HASHTABLE_SIZE ; ++i) +for (i =0 ; i <FRAGMENT_HASHSIZE ; ++i)init_list_head (&dupli_frags[i]); }
@@ -166,12 +166,9 @@ static void z_erofs_fragments_dedupe_exit(void)struct list_head *head;unsigned int i; -for (i =0 ; i <FRAGMENT_HASHTABLE_SIZE ; ++i) { +for (i =0 ; i <FRAGMENT_HASHSIZE ; ++i) { head = &dupli_frags[i]; -if (list_empty (head)) -continue ; -list_for_each_entry_safe (di, n, head, list)free (di); }
PATCH v6 1/1 erofs-utils: mkfs: support fragment deduplication
From: Yue Hu <[email protected]>
Previously, there's no fragment deduplication when this feature is introduced. Let's support it now.
Fragments are deduplicated before compression, so that duplicated parts will not be written into the packed inode again.
Dataset: linux 5.10 + 5.10.50 + 5.10.100 Compression algorithm: lz4hc,12
Additional options: -T0 --force-uid=1000 --force-gid=1000
(in order to force 32-byte inodes to match squashfs)
4k pcluster + fragment + dedupe 397168640
8k pcluster + fragment + dedupe 364224512
16k pcluster + fragment + dedupe 341921792
32k pcluster + fragment + dedupe 328298496
64k pcluster + fragment + dedupe 324694016
128k pcluster + fragment + dedupe 323674112
256k pcluster + fragment + dedupe 322011136squashfs-tools 4.5.1 test results (which uses level 12 by default for lz4hc):
16k block 428785664
32k block 382894080
64k block 350179328
128k block 327073792
128k block + noI 334327808
256k block 315441152
256k block + noI 322707456
1m block 307425280
1m block + noI 314712064If the compressed block size is large, the image size of squashfs will benefit from its simple _unseekable_ data block indexes:
location = block_start
for i = 0; i < index; i++
location += block_sizes[i] & 0x00FFFFFF
and its fragment lookup table. EROFS can improve such cases later.
---
Let's submit this version.
include/erofs/compress.h | 3 +- include/erofs/fragments.h | 4 +- lib/compress.c | 133 +++++++++++++++++++++----- lib/fragments.c | 190 ++++++++++++++++++++++++++++++++++++-- 4 files changed, 296 insertions(+), 34 deletions(-)
include/erofs/compress.h +1 -2
@@ -14,8 +14,7 @@ extern "C"#include "internal.h" -#define EROFS_CONFIG_COMPR_MAX_SZ (3000 * 1024) -#define EROFS_CONFIG_COMPR_MIN_SZ (32 * 1024) +#define EROFS_CONFIG_COMPR_MAX_SZ (4000 * 1024)void z_erofs_drop_inline_pcluster (struct erofs_inode *inode);int erofs_write_compressed_file (struct erofs_inode *inode,int fd);
include/erofs/fragments.h +3 -1
@@ -15,8 +15,10 @@ extern "C"extern const char *frags_packedname;#define EROFS_PACKED_INODE frags_packedname +int z_erofs_fragments_dedupe (struct erofs_inode *inode,int fd,u32 *tofcrc);int z_erofs_pack_fragments (struct erofs_inode *inode,void *data, -unsigned int len); +unsigned int len,u32 tofcrc); +void z_erofs_fragments_commit (struct erofs_inode *inode);struct erofs_inode *erofs_mkfs_build_fragments (void );int erofs_fragments_init (void );void erofs_fragments_exit (void );
lib/compress.c +109 -24
252 lines not on this page · raw message
lib/fragments.c +183 -7
224 lines not on this page · raw message
Signature · 1 line
2.24.4