Skip to contentSkip to conversation

erofs-utils: mkfs: support fragment deduplication

PATCH Superseded Yue Hu 2 participants 3 messages Dec 7, 2022 – Dec 8, 2022 Library code

v6 of 7 Superseded Latest is v7 →

lore
Share & tools
lore

Yue Hu

author
#0 lore raw

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
index e9dfaf2..08af9e3 100644
@@ -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
index 5444384..4caaf6b 100644
@@ -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
#1 lore raw
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.

I'd like to submit it with minor update:

lib/compress.c +2 -2
index 6b79096..b205aa6 100644
@@ -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
index e855467..e69ae47 100644
@@ -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);
 	}
#2 lore raw

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  322011136

squashfs-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                   314712064

If 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
index e9dfaf2..08af9e3 100644
@@ -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
index 5444384..4caaf6b 100644
@@ -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