zram: Optimize LZ4 dictionary compression performance

zram: Optimize LZ4 dictionary compression performance

[gao xu]

Calling `LZ4_loadDict()` repeatedly in Zram causes significant overhead
due to its internal dictionary pre-processing. This commit introduces a
template stream mechanism to pre-process the dictionary only once when
the dictionary is initially set or modified. It then efficiently copies
this state for subsequent compressions.

This optimization improves LZ4 dictionary compression performance by
over 50% in Zram I/O tests.
---
 drivers/block/zram/backend_lz4.c | 55 ++++++++++++++++++++++++++++++--
 drivers/block/zram/zcomp.h       |  1 +
 drivers/block/zram/zram_drv.c    |  1 +
 3 files changed, 54 insertions(+), 3 deletions(-)

diff --git a/drivers/block/zram/backend_lz4.c b/drivers/block/zram/backend_lz4.c
index 04e186614..b353f74a8 100644
--- a/drivers/block/zram/backend_lz4.c
+++ b/drivers/block/zram/backend_lz4.c
@@ -12,15 +12,36 @@ struct lz4_ctx {
 	LZ4_stream_t *cstrm;
 };
 
+struct lz4_drv {
+	/* template compression stream with dictionary */
+	LZ4_stream_t base_cstream;
+	/* dictionary index of the current template */
+	u32 dict_gen;
+	bool base_c_valid;
+};
+
 static void lz4_release_params(struct zcomp_params *params)
 {
+	kfree(params->drv_data);
+	params->drv_data = NULL;
 }
 
 static int lz4_setup_params(struct zcomp_params *params)
 {
+	struct lz4_drv *drv;
+
 	if (params->level == ZCOMP_PARAM_NOT_SET)
 		params->level = LZ4_ACCELERATION_DEFAULT;
 
+	drv = kzalloc_obj(drv, GFP_KERNEL);
+	if (!drv)
+		return -ENOMEM;
+
+	drv->dict_gen = 0;
+	drv->base_c_valid = false;
+
+	params->drv_data = drv;
+
 	return 0;
 }
 
@@ -67,10 +88,32 @@ static int lz4_create(struct zcomp_params *params, struct zcomp_ctx *ctx)
 	return -ENOMEM;
 }
 
+static int lz4_build_base_cstream(struct zcomp_params *params)
+{
+	struct lz4_drv *drv = params->drv_data;
+	int ret;
+
+	if (!params->dict || !params->dict_sz)
+		return -EINVAL;
+
+	memset(&drv->base_cstream, 0, sizeof(drv->base_cstream));
+
+	ret = LZ4_loadDict(&drv->base_cstream,
+			   params->dict, params->dict_sz);
+	if (ret != params->dict_sz)
+		return -EINVAL;
+
+	drv->dict_gen = params->dict_gen;
+	drv->base_c_valid = true;
+
+	return 0;
+}
+
 static int lz4_compress(struct zcomp_params *params, struct zcomp_ctx *ctx,
 			struct zcomp_req *req)
 {
 	struct lz4_ctx *zctx = ctx->context;
+	struct lz4_drv *drv  = params->drv_data;
 	int ret;
 
 	if (!zctx->cstrm) {
@@ -78,10 +121,16 @@ static int lz4_compress(struct zcomp_params *params, struct zcomp_ctx *ctx,
 					req->dst_len, params->level,
 					zctx->mem);
 	} else {
+		/* rebuild base_cstream when the dictionary changes */
+		if (!drv->base_c_valid || drv->dict_gen != params->dict_gen) {
+			ret = lz4_build_base_cstream(params);
+			if (ret)
+				return ret;
+		}
+
 		/* Cstrm needs to be reset */
-		ret = LZ4_loadDict(zctx->cstrm, params->dict, params->dict_sz);
-		if (ret != params->dict_sz)
-			return -EINVAL;
+		memcpy(zctx->cstrm, &drv->base_cstream,
+		   sizeof(*zctx->cstrm));
 		ret = LZ4_compress_fast_continue(zctx->cstrm, req->src,
 						 req->dst, req->src_len,
 						 req->dst_len, params->level);
diff --git a/drivers/block/zram/zcomp.h b/drivers/block/zram/zcomp.h
index eacfd3f7d..5b7ff9fdd 100644
--- a/drivers/block/zram/zcomp.h
+++ b/drivers/block/zram/zcomp.h
@@ -21,6 +21,7 @@ struct zcomp_params {
 	void *dict;
 	size_t dict_sz;
 	s32 level;
+	u32 dict_gen;
 	union {
 		struct deflate_params deflate;
 	};
diff --git a/drivers/block/zram/zram_drv.c b/drivers/block/zram/zram_drv.c
index bca33403f..f34f3fa43 100644
--- a/drivers/block/zram/zram_drv.c
+++ b/drivers/block/zram/zram_drv.c
@@ -1709,6 +1709,7 @@ static int comp_params_store(struct zram *zram, u32 prio, s32 level,
 	zram->params[prio].dict_sz = sz;
 	zram->params[prio].level = level;
 	zram->params[prio].deflate.winbits = deflate_params->winbits;
+	zram->params[prio].dict_gen++;
 	return 0;
 }
 
--

Re: zram: Optimize LZ4 dictionary compression performance

[Sergey Senozhatsky]

On (26/03/10 02:54), gao xu wrote:
[..]
> @@ -78,10 +121,16 @@ static int lz4_compress(struct zcomp_params *params, struct zcomp_ctx *ctx,
>  					req->dst_len, params->level,
>  					zctx->mem);
>  	} else {
> +		/* rebuild base_cstream when the dictionary changes */

How often does it change and under what circumstances?

> +		if (!drv->base_c_valid || drv->dict_gen != params->dict_gen) {
> +			ret = lz4_build_base_cstream(params);
> +			if (ret)
> +				return ret;
> +		}

Re: zram: Optimize LZ4 dictionary compression performance

[Sergey Senozhatsky]

On (26/03/10 02:54), gao xu wrote:
> +struct lz4_drv {
> +	/* template compression stream with dictionary */
> +	LZ4_stream_t base_cstream;
> +	/* dictionary index of the current template */
> +	u32 dict_gen;
> +	bool base_c_valid;
> +};
> +
>  static void lz4_release_params(struct zcomp_params *params)
>  {
> +	kfree(params->drv_data);
> +	params->drv_data = NULL;
>  }
>  
>  static int lz4_setup_params(struct zcomp_params *params)
>  {
> +	struct lz4_drv *drv;
> +
>  	if (params->level == ZCOMP_PARAM_NOT_SET)
>  		params->level = LZ4_ACCELERATION_DEFAULT;
>  
> +	drv = kzalloc_obj(drv, GFP_KERNEL);
> +	if (!drv)
> +		return -ENOMEM;
> +
> +	drv->dict_gen = 0;
> +	drv->base_c_valid = false;
> +
> +	params->drv_data = drv;
> +
>  	return 0;
>  }
>  
> @@ -67,10 +88,32 @@ static int lz4_create(struct zcomp_params *params, struct zcomp_ctx *ctx)
>  	return -ENOMEM;
>  }
>  
> +static int lz4_build_base_cstream(struct zcomp_params *params)
> +{
> +	struct lz4_drv *drv = params->drv_data;
> +	int ret;
> +
> +	if (!params->dict || !params->dict_sz)
> +		return -EINVAL;
> +
> +	memset(&drv->base_cstream, 0, sizeof(drv->base_cstream));
> +
> +	ret = LZ4_loadDict(&drv->base_cstream,
> +			   params->dict, params->dict_sz);
> +	if (ret != params->dict_sz)
> +		return -EINVAL;
> +
> +	drv->dict_gen = params->dict_gen;
> +	drv->base_c_valid = true;
> +
> +	return 0;
> +}

I think this simply can move to ->lz4_setup_params(), becase that
function is supposed to loadDict.  I guess we can use backend_zstd.c
as a reference.  Also probably can inherit naming scheme from zstd
backend as well.

>  static int lz4_compress(struct zcomp_params *params, struct zcomp_ctx *ctx,
>  			struct zcomp_req *req)
>  {
>  	struct lz4_ctx *zctx = ctx->context;
> +	struct lz4_drv *drv  = params->drv_data;
>  	int ret;
>  
>  	if (!zctx->cstrm) {
> @@ -78,10 +121,16 @@ static int lz4_compress(struct zcomp_params *params, struct zcomp_ctx *ctx,
>  					req->dst_len, params->level,
>  					zctx->mem);
>  	} else {
> +		/* rebuild base_cstream when the dictionary changes */
> +		if (!drv->base_c_valid || drv->dict_gen != params->dict_gen) {
> +			ret = lz4_build_base_cstream(params);
> +			if (ret)
> +				return ret;
> +		}

We should not need this, unless I'm missing something.  Params should
change once algorithms are setups and the device is init.

[..]
> diff --git a/drivers/block/zram/zram_drv.c b/drivers/block/zram/zram_drv.c
> index bca33403f..f34f3fa43 100644
> --- a/drivers/block/zram/zram_drv.c
> +++ b/drivers/block/zram/zram_drv.c
> @@ -1709,6 +1709,7 @@ static int comp_params_store(struct zram *zram, u32 prio, s32 level,
>  	zram->params[prio].dict_sz = sz;
>  	zram->params[prio].level = level;
>  	zram->params[prio].deflate.winbits = deflate_params->winbits;
> +	zram->params[prio].dict_gen++;

We should not need this, as far as I can see.  It was a bug that we
permitted params change after init.  I sent a fixup patch.

Re: zram: Optimize LZ4 dictionary compression performance

[Sergey Senozhatsky]

On (26/03/10 02:54), gao xu wrote:
> +		memcpy(zctx->cstrm, &drv->base_cstream,
> +		   sizeof(*zctx->cstrm));

Do we need to do this memcpy() every time?
A nit: if it cannot fit on one line, then let's align sizeof(*zctx->cstrm)
with "(".

Re: zram: Optimize LZ4 dictionary compression performance

[Sergey Senozhatsky]

On (26/03/10 15:13), Sergey Senozhatsky wrote:
[..]
> > +		/* rebuild base_cstream when the dictionary changes */
> > +		if (!drv->base_c_valid || drv->dict_gen != params->dict_gen) {
> > +			ret = lz4_build_base_cstream(params);
> > +			if (ret)
> > +				return ret;
> > +		}
> 
> We should not need this, unless I'm missing something.  Params should
                                                                 ^ should not
> change once algorithms are setups and the device is init.

RE: zram: Optimize LZ4 dictionary compression performance

[gao xu]

> 
> On (26/03/10 02:54), gao xu wrote:
> > +struct lz4_drv {
> > +	/* template compression stream with dictionary */
> > +	LZ4_stream_t base_cstream;
> > +	/* dictionary index of the current template */
> > +	u32 dict_gen;
> > +	bool base_c_valid;
> > +};
> > +
> >  static void lz4_release_params(struct zcomp_params *params)
> >  {
> > +	kfree(params->drv_data);
> > +	params->drv_data = NULL;
> >  }
> >
> >  static int lz4_setup_params(struct zcomp_params *params)
> >  {
> > +	struct lz4_drv *drv;
> > +
> >  	if (params->level == ZCOMP_PARAM_NOT_SET)
> >  		params->level = LZ4_ACCELERATION_DEFAULT;
> >
> > +	drv = kzalloc_obj(drv, GFP_KERNEL);
> > +	if (!drv)
> > +		return -ENOMEM;
> > +
> > +	drv->dict_gen = 0;
> > +	drv->base_c_valid = false;
> > +
> > +	params->drv_data = drv;
> > +
> >  	return 0;
> >  }
> >
> > @@ -67,10 +88,32 @@ static int lz4_create(struct zcomp_params *params,
> struct zcomp_ctx *ctx)
> >  	return -ENOMEM;
> >  }
> >
> > +static int lz4_build_base_cstream(struct zcomp_params *params)
> > +{
> > +	struct lz4_drv *drv = params->drv_data;
> > +	int ret;
> > +
> > +	if (!params->dict || !params->dict_sz)
> > +		return -EINVAL;
> > +
> > +	memset(&drv->base_cstream, 0, sizeof(drv->base_cstream));
> > +
> > +	ret = LZ4_loadDict(&drv->base_cstream,
> > +			   params->dict, params->dict_sz);
> > +	if (ret != params->dict_sz)
> > +		return -EINVAL;
> > +
> > +	drv->dict_gen = params->dict_gen;
> > +	drv->base_c_valid = true;
> > +
> > +	return 0;
> > +}
> 
> I think this simply can move to ->lz4_setup_params(), becase that
> function is supposed to loadDict.  I guess we can use backend_zstd.c
> as a reference.  Also probably can inherit naming scheme from zstd
> backend as well.
Should I modify it like this?
+static int lz4_create_cstream(struct zcomp_params *params)
+{
+	int ret;
+
+	if (!params->dict || !params->dict_sz)
+		return 0;
+
+	params->drv_data = kzalloc(sizeof(LZ4_stream_t), GFP_KERNEL);
+	if (!params->drv_data)
+		return -ENOMEM;
+
+	ret = LZ4_loadDict((LZ4_stream_t *)params->drv_data,
+			   params->dict, params->dict_sz);
+	if (ret != params->dict_sz) {
+		kfree(params->drv_data);
+		return -EINVAL;
+	}
+
+	return 0;
+}

static int lz4_setup_params(struct zcomp_params *params)
{
	if (params->level == ZCOMP_PARAM_NO_LEVEL)
		params->level = LZ4_ACCELERATION_DEFAULT;

-   return 0;
+	return lz4_create_cstream(params);
}
> 
> >  static int lz4_compress(struct zcomp_params *params, struct zcomp_ctx
> *ctx,
> >  			struct zcomp_req *req)
> >  {
> >  	struct lz4_ctx *zctx = ctx->context;
> > +	struct lz4_drv *drv  = params->drv_data;
> >  	int ret;
> >
> >  	if (!zctx->cstrm) {
> > @@ -78,10 +121,16 @@ static int lz4_compress(struct zcomp_params
> *params, struct zcomp_ctx *ctx,
> >  					req->dst_len, params->level,
> >  					zctx->mem);
> >  	} else {
> > +		/* rebuild base_cstream when the dictionary changes */
> > +		if (!drv->base_c_valid || drv->dict_gen != params->dict_gen) {
> > +			ret = lz4_build_base_cstream(params);
> > +			if (ret)
> > +				return ret;
> > +		}
> 
> We should not need this, unless I'm missing something.  Params should
> change once algorithms are setups and the device is init.
> 
> [..]
> > diff --git a/drivers/block/zram/zram_drv.c b/drivers/block/zram/zram_drv.c
> > index bca33403f..f34f3fa43 100644
> > --- a/drivers/block/zram/zram_drv.c
> > +++ b/drivers/block/zram/zram_drv.c
> > @@ -1709,6 +1709,7 @@ static int comp_params_store(struct zram *zram,
> u32 prio, s32 level,
> >  	zram->params[prio].dict_sz = sz;
> >  	zram->params[prio].level = level;
> >  	zram->params[prio].deflate.winbits = deflate_params->winbits;
> > +	zram->params[prio].dict_gen++;
> 
> We should not need this, as far as I can see.  It was a bug that we
> permitted params change after init.  I sent a fixup patch.
You are right.

Re: zram: Optimize LZ4 dictionary compression performance

[Sergey Senozhatsky]

On (26/03/10 08:32), gao xu wrote:
> +static int lz4_create_cstream(struct zcomp_params *params)
> +{
> +	int ret;
> +
> +	if (!params->dict || !params->dict_sz)
> +		return 0;
> +
> +	params->drv_data = kzalloc(sizeof(LZ4_stream_t), GFP_KERNEL);
> +	if (!params->drv_data)
> +		return -ENOMEM;
> +
> +	ret = LZ4_loadDict((LZ4_stream_t *)params->drv_data,
> +			   params->dict, params->dict_sz);
> +	if (ret != params->dict_sz) {
> +		kfree(params->drv_data);
> +		return -EINVAL;
> +	}
> +
> +	return 0;
> +}
> 
> static int lz4_setup_params(struct zcomp_params *params)
> {
> 	if (params->level == ZCOMP_PARAM_NO_LEVEL)
> 		params->level = LZ4_ACCELERATION_DEFAULT;
> 
> -   return 0;
> +	return lz4_create_cstream(params);
> }

[..]

> Should I modify it like this?

Do you need lz4_create_cstream() as a separate function? If not, you can
just move the code into lz4_setup_params() and remove lz4_create_cstream()?

Re: zram: Optimize LZ4 dictionary compression performance

[Sergey Senozhatsky]

On (26/03/10 02:54), gao xu wrote:
> 
> This optimization improves LZ4 dictionary compression performance by
> over 50% in Zram I/O tests.

Can you also add a little more details here?  What type of
a test, actual IO numbers maybe, etc.

RE: zram: Optimize LZ4 dictionary compression performance

[gao xu]

> On (26/03/10 08:32), gao xu wrote:
> > +static int lz4_create_cstream(struct zcomp_params *params) {
> > +	int ret;
> > +
> > +	if (!params->dict || !params->dict_sz)
> > +		return 0;
> > +
> > +	params->drv_data = kzalloc(sizeof(LZ4_stream_t), GFP_KERNEL);
> > +	if (!params->drv_data)
> > +		return -ENOMEM;
> > +
> > +	ret = LZ4_loadDict((LZ4_stream_t *)params->drv_data,
> > +			   params->dict, params->dict_sz);
> > +	if (ret != params->dict_sz) {
> > +		kfree(params->drv_data);
> > +		return -EINVAL;
> > +	}
> > +
> > +	return 0;
> > +}
> >
> > static int lz4_setup_params(struct zcomp_params *params) {
> > 	if (params->level == ZCOMP_PARAM_NO_LEVEL)
> > 		params->level = LZ4_ACCELERATION_DEFAULT;
> >
> > -   return 0;
> > +	return lz4_create_cstream(params);
> > }
> 
> [..]
> 
> > Should I modify it like this?
> 
> Do you need lz4_create_cstream() as a separate function? If not, you can just
> move the code into lz4_setup_params() and remove lz4_create_cstream()?
lz4_create_cstream() is not needed as a separate function. I will address this in v2.

RE: zram: Optimize LZ4 dictionary compression performance

[gao xu]

> On (26/03/10 02:54), gao xu wrote:
> >
> > This optimization improves LZ4 dictionary compression performance by
> > over 50% in Zram I/O tests.
> 
> Can you also add a little more details here?  What type of a test, actual IO
> numbers maybe, etc.
Received, Add it in v2.

RE: zram: Optimize LZ4 dictionary compression performance

[gao xu]

> 
> On (26/03/10 02:54), gao xu wrote:
> > +		memcpy(zctx->cstrm, &drv->base_cstream,
> > +		   sizeof(*zctx->cstrm));
> 
> Do we need to do this memcpy() every time?
memcpy is a replacement for LZ4_loadDict. LZ4_loadDict updates the LZ4 hash table using the dictionary. Furthermore, LZ4 also updates its hash table with the results of the previous compression. Therefore, to ensure the compression dictionary remains effective, we would need to reset the hash table every time, which would involve executing memcpy() or LZ4_loadDict(). (Please correct me if there's any misunderstanding here.)
> A nit: if it cannot fit on one line, then let's align sizeof(*zctx->cstrm) with "(".
Received, thank you.

Re: zram: Optimize LZ4 dictionary compression performance

[Sergey Senozhatsky]

On (26/03/11 04:00), gao xu wrote:
> > On (26/03/10 02:54), gao xu wrote:
> > > +		memcpy(zctx->cstrm, &drv->base_cstream,
> > > +		   sizeof(*zctx->cstrm));
> > 
> > Do we need to do this memcpy() every time?
> memcpy is a replacement for LZ4_loadDict. LZ4_loadDict updates
> the LZ4 hash table using the dictionary. Furthermore, LZ4 also
> updates its hash table with the results of the previous compression.
> Therefore, to ensure the compression dictionary remains effective, we
> would need to reset the hash table every time, which would involve
> executing memcpy() or LZ4_loadDict()

OK, I see.  (I assume you tested and verified that.)