linux-erofs.lists.ozlabs.org archive mirror
 help / color / mirror / Atom feed
From: Gao Xiang <xiang@kernel.org>
To: Gao Xiang <hsiangkao@linux.alibaba.com>
Cc: linux-erofs@lists.ozlabs.org,
	ZiyangZhang <ZiyangZhang@linux.alibaba.com>
Subject: Re: [PATCH 4/4] erofs-utils: mkfs: introduce global compressed data deduplication
Date: Thu, 8 Sep 2022 08:56:32 +0800	[thread overview]
Message-ID: <Yxk9wKhFaROqoySM@hsiangkao-PC> (raw)
In-Reply-To: <YxgyZqrZs1X2V1pC@B-P7TQMD6M-0146.local>

On Wed, Sep 07, 2022 at 01:55:50PM +0800, Gao Xiang wrote:
> On Tue, Sep 06, 2022 at 07:40:57PM +0800, ZiyangZhang wrote:
> > From: Ziyang Zhang <ZiyangZhang@linux.alibaba.com>
> > 
> > This patch introduces global compressed data deduplication to
> > reuse potential prefixes for each pcluster.
> > 
> > It also uses rolling hashing and shortens the previous compressed
> > extent in order to explore more possibilities for deduplication.
> > 
> > Co-developped-by: Gao Xiang <hsiangkao@linux.alibaba.com>
> > Signed-off-by: Ziyang Zhang <ZiyangZhang@linux.alibaba.com>
> 
> Some preliminary numbers:
> Image				Fs	Type						Size
> system.raven.87e115a1           erofs   uncompressed                                    910082048
> system.raven.87e115a1           erofs   4k pcluster + lz4hc,9 + ztailpacking            584970240       -35.7% off
> system.raven.87e115a1           erofs   4k pcluster + lz4hc,9 + ztailpacking + dedupe   569376768       -37.4% off
> 
> linux-5.10 + linux-5.10.87      erofs   uncompressed                                     1943691264
> linux-5.10 + linux-5.10.87      erofs   4k pcluster + lz4hc,9 + ztailpacking             661987328      -65.9% off
> linux-5.10 + linux-5.10.87      erofs   4k pcluster + lz4hc,9 + ztailpacking + dedupe    490295296      -74.8% off
> 
> linux-5.10.87                   erofs   4k pcluster + lz4hc,9                            331292672
> 
> One observation is since the tailpacking pcluster doesn't have blkaddr
> so data relating to tailpacking pcluster cannot be deduped.
> 
> On the other side, it can work with `fragment' feature later together to
> minimize image sizes.
> 
> 
> Attach a fix for uncompressed pcluster:
> 
> diff --git a/lib/dedupe.c b/lib/dedupe.c
> index c53a64edfc8d..c382303e2ceb 100644
> --- a/lib/dedupe.c
> +++ b/lib/dedupe.c
> @@ -21,7 +21,7 @@ struct z_erofs_dedupe_item {
>  	unsigned int	compressed_blks;
>  
>  	int		original_length;
> -	bool		partial;
> +	bool		partial, raw;
>  	u8		extra_data[];
>  };
>  
> @@ -86,6 +86,7 @@ int z_erofs_dedupe_match(struct z_erofs_dedupe_ctx *ctx)
>  		ctx->e.length = window_size + extra;
>  		ctx->e.partial = e->partial ||
>  			(window_size + extra < e->original_length);
> +		ctx->e.raw = e->raw;
>  		ctx->e.blkaddr = e->compressed_blkaddr;
>  		ctx->e.compressedblks = e->compressed_blks;
>  		return 0;
> @@ -114,6 +115,7 @@ int z_erofs_dedupe_insert(struct z_erofs_inmem_extent *e,
>  	di->compressed_blkaddr = e->blkaddr;
>  	di->compressed_blks = e->compressedblks;
>  	di->partial = e->partial;
> +	di->raw = e->raw;
>  
>  	/* with the same rolling hash */
>  	if (!rb_tree_insert(dedupe_subtree, di))
> -- 
> 2.30.2
>

Another fix detected by an Android system image:

diff --git a/lib/compress.c b/lib/compress.c
index bdb6e78d32ca..3247835b75b6 100644
--- a/lib/compress.c
+++ b/lib/compress.c
@@ -158,9 +158,14 @@ static int z_erofs_compress_dedupe(struct erofs_inode *inode,
 
 	do {
 		struct z_erofs_dedupe_ctx dctx = {
-			.start = ctx->queue + ctx->head -
-				(ctx->e.length < EROFS_BLKSIZ ? 0 :
-					ctx->e.length - EROFS_BLKSIZ),
+			.start = ctx->queue + ctx->head - ({ int rc;
+				if (ctx->e.length <= EROFS_BLKSIZ)
+					rc = 0;
+				else if (ctx->e.length - EROFS_BLKSIZ >= ctx->head)
+					rc = ctx->head;
+				else
+					rc = ctx->e.length - EROFS_BLKSIZ;
+				rc; }),
 			.end = ctx->queue + ctx->head + *len,
 			.cur = ctx->queue + ctx->head,
 		};


      reply	other threads:[~2022-09-08  0:57 UTC|newest]

Thread overview: 6+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2022-09-06 11:40 [PATCH 1/4] erofs-utils: introduce z_erofs_inmem_extent ZiyangZhang
2022-09-06 11:40 ` [PATCH 2/4] erofs-utils: lib: add rb-tree implementation ZiyangZhang
2022-09-06 11:40 ` [PATCH 3/4] erofs-utils: fuse: introduce partial-referenced pclusters ZiyangZhang
2022-09-06 11:40 ` [PATCH 4/4] erofs-utils: mkfs: introduce global compressed data deduplication ZiyangZhang
2022-09-07  5:55   ` Gao Xiang
2022-09-08  0:56     ` Gao Xiang [this message]

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=Yxk9wKhFaROqoySM@hsiangkao-PC \
    --to=xiang@kernel.org \
    --cc=ZiyangZhang@linux.alibaba.com \
    --cc=hsiangkao@linux.alibaba.com \
    --cc=linux-erofs@lists.ozlabs.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).