[PATCH v1] erofs-utils: lib: Fix 8MB bug on uncompressed extent size

[PATCH v1] erofs-utils: lib: Fix 8MB bug on uncompressed extent size

[Kelvin Zhang via Linux-erofs]

Previously, uncompressed extent can be at most 8MB before mkfs.erofs
crashes on some error condition. This is due to a minor bug in how
compressed indices are encoded. This patch fixes the issue.

Signed-off-by: Kelvin Zhang <zhangkelvin@google.com>
---
 include/erofs_fs.h |  2 +-
 lib/compress.c     | 21 ++++++++++++++++++++-
 2 files changed, 21 insertions(+), 2 deletions(-)

diff --git a/include/erofs_fs.h b/include/erofs_fs.h
index 9a91877..13eaf24 100644
--- a/include/erofs_fs.h
+++ b/include/erofs_fs.h
@@ -353,7 +353,7 @@ enum {
  * compressed block count of a compressed extent (in logical clusters, aka.
  * block count of a pcluster).
  */
-#define Z_EROFS_VLE_DI_D0_CBLKCNT		(1 << 11)
+#define Z_EROFS_VLE_DI_D0_CBLKCNT		(1U << 11)
 
 struct z_erofs_vle_decompressed_index {
 	__le16 di_advise;
diff --git a/lib/compress.c b/lib/compress.c
index 98be7a2..23e571c 100644
--- a/lib/compress.c
+++ b/lib/compress.c
@@ -97,7 +97,26 @@ static void vle_write_indexes(struct z_erofs_vle_compress_ctx *ctx,
 		} else if (d0) {
 			type = Z_EROFS_VLE_CLUSTER_TYPE_NONHEAD;
 
-			di.di_u.delta[0] = cpu_to_le16(d0);
+			/* If the |Z_EROFS_VLE_DI_D0_CBLKCNT| bit is set, parser
+			 * will interpret |delta[0]| as size of pcluster, rather
+			 * than distance to last head cluster. Normally this
+			 * isn't a problem, because uncompressed extent size are
+			 * below Z_EROFS_VLE_DI_D0_CBLKCNT * BLOCK_SIZE = 8MB.
+			 * But with large pcluster it's possible to go over this
+			 * number, resulting in corrupted compressed indices.
+			 * To solve this, we use Z_EROFS_VLE_DI_D0_CBLKCNT-1 if
+			 * the uncompressed extent size goes above 8MB. This is
+			 * OK because if kernel sees another non-head cluster
+			 * after going back by |delta[0]| blocks, kernel will
+			 * just keep looking back.
+			 */
+			if (d0 & Z_EROFS_VLE_DI_D0_CBLKCNT) {
+				di.di_u.delta[0] = max(
+					d0 & (~Z_EROFS_VLE_DI_D0_CBLKCNT),
+					Z_EROFS_VLE_DI_D0_CBLKCNT-1);
+			} else {
+				di.di_u.delta[0] = cpu_to_le16(d0);
+			}
 			di.di_u.delta[1] = cpu_to_le16(d1);
 		} else {
 			type = raw ? Z_EROFS_VLE_CLUSTER_TYPE_PLAIN :
-- 
2.34.1.448.ga2b2bfdf31-goog

Re: [PATCH v1] erofs-utils: lib: Fix 8MB bug on uncompressed extent size

[Gao Xiang]

On Tue, Dec 21, 2021 at 06:03:07PM -0800, Kelvin Zhang wrote:
> Previously, uncompressed extent can be at most 8MB before mkfs.erofs
> crashes on some error condition. This is due to a minor bug in how
> compressed indices are encoded. This patch fixes the issue.
> 
> Signed-off-by: Kelvin Zhang <zhangkelvin@google.com>

I have to hold this for a while and look into (evaluate) that when I
get a full free time... (maybe a week later.) I understand it's not
quite urgent for all of us currently..

I still stuck into ztailpacking inline feature for now... 

Thanks,
Gao Xiang

> ---
>  include/erofs_fs.h |  2 +-
>  lib/compress.c     | 21 ++++++++++++++++++++-
>  2 files changed, 21 insertions(+), 2 deletions(-)
> 
> diff --git a/include/erofs_fs.h b/include/erofs_fs.h
> index 9a91877..13eaf24 100644
> --- a/include/erofs_fs.h
> +++ b/include/erofs_fs.h
> @@ -353,7 +353,7 @@ enum {
>   * compressed block count of a compressed extent (in logical clusters, aka.
>   * block count of a pcluster).
>   */
> -#define Z_EROFS_VLE_DI_D0_CBLKCNT		(1 << 11)
> +#define Z_EROFS_VLE_DI_D0_CBLKCNT		(1U << 11)
>  
>  struct z_erofs_vle_decompressed_index {
>  	__le16 di_advise;
> diff --git a/lib/compress.c b/lib/compress.c
> index 98be7a2..23e571c 100644
> --- a/lib/compress.c
> +++ b/lib/compress.c
> @@ -97,7 +97,26 @@ static void vle_write_indexes(struct z_erofs_vle_compress_ctx *ctx,
>  		} else if (d0) {
>  			type = Z_EROFS_VLE_CLUSTER_TYPE_NONHEAD;
>  
> -			di.di_u.delta[0] = cpu_to_le16(d0);
> +			/* If the |Z_EROFS_VLE_DI_D0_CBLKCNT| bit is set, parser
> +			 * will interpret |delta[0]| as size of pcluster, rather
> +			 * than distance to last head cluster. Normally this
> +			 * isn't a problem, because uncompressed extent size are
> +			 * below Z_EROFS_VLE_DI_D0_CBLKCNT * BLOCK_SIZE = 8MB.
> +			 * But with large pcluster it's possible to go over this
> +			 * number, resulting in corrupted compressed indices.
> +			 * To solve this, we use Z_EROFS_VLE_DI_D0_CBLKCNT-1 if
> +			 * the uncompressed extent size goes above 8MB. This is
> +			 * OK because if kernel sees another non-head cluster
> +			 * after going back by |delta[0]| blocks, kernel will
> +			 * just keep looking back.
> +			 */
> +			if (d0 & Z_EROFS_VLE_DI_D0_CBLKCNT) {
> +				di.di_u.delta[0] = max(
> +					d0 & (~Z_EROFS_VLE_DI_D0_CBLKCNT),
> +					Z_EROFS_VLE_DI_D0_CBLKCNT-1);
> +			} else {
> +				di.di_u.delta[0] = cpu_to_le16(d0);
> +			}
>  			di.di_u.delta[1] = cpu_to_le16(d1);
>  		} else {
>  			type = raw ? Z_EROFS_VLE_CLUSTER_TYPE_PLAIN :
> -- 
> 2.34.1.448.ga2b2bfdf31-goog

Re: [PATCH v1] erofs-utils: lib: Fix 8MB bug on uncompressed extent size

[Kelvin Zhang via Linux-erofs]

friendly ping : )

On Tue, Dec 21, 2021 at 7:21 PM Gao Xiang <hsiangkao@linux.alibaba.com> wrote:
>
> On Tue, Dec 21, 2021 at 06:03:07PM -0800, Kelvin Zhang wrote:
> > Previously, uncompressed extent can be at most 8MB before mkfs.erofs
> > crashes on some error condition. This is due to a minor bug in how
> > compressed indices are encoded. This patch fixes the issue.
> >
> > Signed-off-by: Kelvin Zhang <zhangkelvin@google.com>
>
> I have to hold this for a while and look into (evaluate) that when I
> get a full free time... (maybe a week later.) I understand it's not
> quite urgent for all of us currently..
>
> I still stuck into ztailpacking inline feature for now...
>
> Thanks,
> Gao Xiang
>
> > ---
> >  include/erofs_fs.h |  2 +-
> >  lib/compress.c     | 21 ++++++++++++++++++++-
> >  2 files changed, 21 insertions(+), 2 deletions(-)
> >
> > diff --git a/include/erofs_fs.h b/include/erofs_fs.h
> > index 9a91877..13eaf24 100644
> > --- a/include/erofs_fs.h
> > +++ b/include/erofs_fs.h
> > @@ -353,7 +353,7 @@ enum {
> >   * compressed block count of a compressed extent (in logical clusters, aka.
> >   * block count of a pcluster).
> >   */
> > -#define Z_EROFS_VLE_DI_D0_CBLKCNT            (1 << 11)
> > +#define Z_EROFS_VLE_DI_D0_CBLKCNT            (1U << 11)
> >
> >  struct z_erofs_vle_decompressed_index {
> >       __le16 di_advise;
> > diff --git a/lib/compress.c b/lib/compress.c
> > index 98be7a2..23e571c 100644
> > --- a/lib/compress.c
> > +++ b/lib/compress.c
> > @@ -97,7 +97,26 @@ static void vle_write_indexes(struct z_erofs_vle_compress_ctx *ctx,
> >               } else if (d0) {
> >                       type = Z_EROFS_VLE_CLUSTER_TYPE_NONHEAD;
> >
> > -                     di.di_u.delta[0] = cpu_to_le16(d0);
> > +                     /* If the |Z_EROFS_VLE_DI_D0_CBLKCNT| bit is set, parser
> > +                      * will interpret |delta[0]| as size of pcluster, rather
> > +                      * than distance to last head cluster. Normally this
> > +                      * isn't a problem, because uncompressed extent size are
> > +                      * below Z_EROFS_VLE_DI_D0_CBLKCNT * BLOCK_SIZE = 8MB.
> > +                      * But with large pcluster it's possible to go over this
> > +                      * number, resulting in corrupted compressed indices.
> > +                      * To solve this, we use Z_EROFS_VLE_DI_D0_CBLKCNT-1 if
> > +                      * the uncompressed extent size goes above 8MB. This is
> > +                      * OK because if kernel sees another non-head cluster
> > +                      * after going back by |delta[0]| blocks, kernel will
> > +                      * just keep looking back.
> > +                      */
> > +                     if (d0 & Z_EROFS_VLE_DI_D0_CBLKCNT) {
> > +                             di.di_u.delta[0] = max(
> > +                                     d0 & (~Z_EROFS_VLE_DI_D0_CBLKCNT),
> > +                                     Z_EROFS_VLE_DI_D0_CBLKCNT-1);
> > +                     } else {
> > +                             di.di_u.delta[0] = cpu_to_le16(d0);
> > +                     }
> >                       di.di_u.delta[1] = cpu_to_le16(d1);
> >               } else {
> >                       type = raw ? Z_EROFS_VLE_CLUSTER_TYPE_PLAIN :
> > --
> > 2.34.1.448.ga2b2bfdf31-goog



-- 
Sincerely,

Kelvin Zhang

Re: [PATCH v1] erofs-utils: lib: Fix 8MB bug on uncompressed extent size

[Gao Xiang]

Hi Kelvin,

On Tue, Jan 18, 2022 at 03:46:14PM -0800, Kelvin Zhang wrote:
> friendly ping : )

Thanks for your reminder.

It's still on my TODO list with many other stuffs along with many
internal paperwork.
I will finish it no later than the end of our Spring Festival.

Thanks,
Gao Xiang

Re: [PATCH v1] erofs-utils: lib: Fix 8MB bug on uncompressed extent size

[Gao Xiang]

Hi Kelvin,

On Tue, Dec 21, 2021 at 06:03:07PM -0800, Kelvin Zhang wrote:
> Previously, uncompressed extent can be at most 8MB before mkfs.erofs
> crashes on some error condition. This is due to a minor bug in how
> compressed indices are encoded. This patch fixes the issue.
> 
> Signed-off-by: Kelvin Zhang <zhangkelvin@google.com>
> ---
>  include/erofs_fs.h |  2 +-
>  lib/compress.c     | 21 ++++++++++++++++++++-
>  2 files changed, 21 insertions(+), 2 deletions(-)
> 
> diff --git a/include/erofs_fs.h b/include/erofs_fs.h
> index 9a91877..13eaf24 100644
> --- a/include/erofs_fs.h
> +++ b/include/erofs_fs.h
> @@ -353,7 +353,7 @@ enum {
>   * compressed block count of a compressed extent (in logical clusters, aka.
>   * block count of a pcluster).
>   */
> -#define Z_EROFS_VLE_DI_D0_CBLKCNT		(1 << 11)
> +#define Z_EROFS_VLE_DI_D0_CBLKCNT		(1U << 11)

If erofs_fs.h update is necessary, I prefer to update in-kernel
header first. Would you mind making a kernel patch for this if needed?

>  
>  struct z_erofs_vle_decompressed_index {
>  	__le16 di_advise;
> diff --git a/lib/compress.c b/lib/compress.c
> index 98be7a2..23e571c 100644
> --- a/lib/compress.c
> +++ b/lib/compress.c
> @@ -97,7 +97,26 @@ static void vle_write_indexes(struct z_erofs_vle_compress_ctx *ctx,
>  		} else if (d0) {
>  			type = Z_EROFS_VLE_CLUSTER_TYPE_NONHEAD;
>  
> -			di.di_u.delta[0] = cpu_to_le16(d0);
> +			/* If the |Z_EROFS_VLE_DI_D0_CBLKCNT| bit is set, parser
> +			 * will interpret |delta[0]| as size of pcluster, rather
> +			 * than distance to last head cluster. Normally this
> +			 * isn't a problem, because uncompressed extent size are
> +			 * below Z_EROFS_VLE_DI_D0_CBLKCNT * BLOCK_SIZE = 8MB.
> +			 * But with large pcluster it's possible to go over this
> +			 * number, resulting in corrupted compressed indices.
> +			 * To solve this, we use Z_EROFS_VLE_DI_D0_CBLKCNT-1 if
> +			 * the uncompressed extent size goes above 8MB. This is
> +			 * OK because if kernel sees another non-head cluster
> +			 * after going back by |delta[0]| blocks, kernel will
> +			 * just keep looking back.
> +			 */

Would you mind updating this into the kernel comment style, I mean
/*
 * ...
 */
Instead?

> +			if (d0 & Z_EROFS_VLE_DI_D0_CBLKCNT) {
> +				di.di_u.delta[0] = max(
> +					d0 & (~Z_EROFS_VLE_DI_D0_CBLKCNT),
> +					Z_EROFS_VLE_DI_D0_CBLKCNT-1);

May I ask if it's actually tested with big pcluster feature? It's
lack of cpu_to_le16() convert and even the original
Z_EROFS_VLE_DI_D0_CBLKCNT flag.

Thanks,
Gao Xiang

> +			} else {
> +				di.di_u.delta[0] = cpu_to_le16(d0);
> +			}
>  			di.di_u.delta[1] = cpu_to_le16(d1);
>  		} else {
>  			type = raw ? Z_EROFS_VLE_CLUSTER_TYPE_PLAIN :
> -- 
> 2.34.1.448.ga2b2bfdf31-goog

Re: [PATCH v1] erofs-utils: lib: Fix 8MB bug on uncompressed extent size

[Gao Xiang]

On Mon, Feb 07, 2022 at 07:59:50AM +0800, Gao Xiang wrote:
> Hi Kelvin,
> 
> On Tue, Dec 21, 2021 at 06:03:07PM -0800, Kelvin Zhang wrote:
> > Previously, uncompressed extent can be at most 8MB before mkfs.erofs
> > crashes on some error condition. This is due to a minor bug in how
> > compressed indices are encoded. This patch fixes the issue.
> > 
> > Signed-off-by: Kelvin Zhang <zhangkelvin@google.com>
> > ---
> >  include/erofs_fs.h |  2 +-
> >  lib/compress.c     | 21 ++++++++++++++++++++-
> >  2 files changed, 21 insertions(+), 2 deletions(-)
> > 
> > diff --git a/include/erofs_fs.h b/include/erofs_fs.h
> > index 9a91877..13eaf24 100644
> > --- a/include/erofs_fs.h
> > +++ b/include/erofs_fs.h
> > @@ -353,7 +353,7 @@ enum {
> >   * compressed block count of a compressed extent (in logical clusters, aka.
> >   * block count of a pcluster).
> >   */
> > -#define Z_EROFS_VLE_DI_D0_CBLKCNT		(1 << 11)
> > +#define Z_EROFS_VLE_DI_D0_CBLKCNT		(1U << 11)
> 
> If erofs_fs.h update is necessary, I prefer to update in-kernel
> header first. Would you mind making a kernel patch for this if needed?
> 
> >  
> >  struct z_erofs_vle_decompressed_index {
> >  	__le16 di_advise;
> > diff --git a/lib/compress.c b/lib/compress.c
> > index 98be7a2..23e571c 100644
> > --- a/lib/compress.c
> > +++ b/lib/compress.c
> > @@ -97,7 +97,26 @@ static void vle_write_indexes(struct z_erofs_vle_compress_ctx *ctx,
> >  		} else if (d0) {
> >  			type = Z_EROFS_VLE_CLUSTER_TYPE_NONHEAD;
> >  
> > -			di.di_u.delta[0] = cpu_to_le16(d0);
> > +			/* If the |Z_EROFS_VLE_DI_D0_CBLKCNT| bit is set, parser
> > +			 * will interpret |delta[0]| as size of pcluster, rather
> > +			 * than distance to last head cluster. Normally this
> > +			 * isn't a problem, because uncompressed extent size are
> > +			 * below Z_EROFS_VLE_DI_D0_CBLKCNT * BLOCK_SIZE = 8MB.
> > +			 * But with large pcluster it's possible to go over this
> > +			 * number, resulting in corrupted compressed indices.
> > +			 * To solve this, we use Z_EROFS_VLE_DI_D0_CBLKCNT-1 if
> > +			 * the uncompressed extent size goes above 8MB. This is
> > +			 * OK because if kernel sees another non-head cluster
> > +			 * after going back by |delta[0]| blocks, kernel will
> > +			 * just keep looking back.
> > +			 */
> 
> Would you mind updating this into the kernel comment style, I mean
> /*
>  * ...
>  */
> Instead?
> 
> > +			if (d0 & Z_EROFS_VLE_DI_D0_CBLKCNT) {
> > +				di.di_u.delta[0] = max(
> > +					d0 & (~Z_EROFS_VLE_DI_D0_CBLKCNT),
> > +					Z_EROFS_VLE_DI_D0_CBLKCNT-1);
> 
> May I ask if it's actually tested with big pcluster feature? It's
> lack of cpu_to_le16() convert and even the original
> Z_EROFS_VLE_DI_D0_CBLKCNT flag.

Sorry this part shouldn't have Z_EROFS_VLE_DI_D0_CBLKCNT flag.

Btw, I think a proper change for this might be just:
	if (d0 > Z_EROFS_VLE_DI_D0_CBLKCNT - 1)
		di.di_u.delta[0] = le16_to_cpu(Z_EROFS_VLE_DI_D0_CBLKCNT - 1);
	else
		di.di_u.delta[0] = cpu_to_le16(d0);
Or using max() to simplify above even more a bit.

Thanks,
Gao Xiang

> 
> Thanks,
> Gao Xiang

Re: [PATCH v1] erofs-utils: lib: Fix 8MB bug on uncompressed extent size

[Kelvin Zhang via Linux-erofs]

-1

On Sun, Feb 6, 2022 at 6:08 PM Gao Xiang <hsiangkao@linux.alibaba.com> wrote:
>
> On Mon, Feb 07, 2022 at 07:59:50AM +0800, Gao Xiang wrote:
> > Hi Kelvin,
> >
> > On Tue, Dec 21, 2021 at 06:03:07PM -0800, Kelvin Zhang wrote:
> > > Previously, uncompressed extent can be at most 8MB before mkfs.erofs
> > > crashes on some error condition. This is due to a minor bug in how
> > > compressed indices are encoded. This patch fixes the issue.
> > >
> > > Signed-off-by: Kelvin Zhang <zhangkelvin@google.com>
> > > ---
> > >  include/erofs_fs.h |  2 +-
> > >  lib/compress.c     | 21 ++++++++++++++++++++-
> > >  2 files changed, 21 insertions(+), 2 deletions(-)
> > >
> > > diff --git a/include/erofs_fs.h b/include/erofs_fs.h
> > > index 9a91877..13eaf24 100644
> > > --- a/include/erofs_fs.h
> > > +++ b/include/erofs_fs.h
> > > @@ -353,7 +353,7 @@ enum {
> > >   * compressed block count of a compressed extent (in logical clusters, aka.
> > >   * block count of a pcluster).
> > >   */
> > > -#define Z_EROFS_VLE_DI_D0_CBLKCNT          (1 << 11)
> > > +#define Z_EROFS_VLE_DI_D0_CBLKCNT          (1U << 11)
> >
> > If erofs_fs.h update is necessary, I prefer to update in-kernel
> > header first. Would you mind making a kernel patch for this if needed?

Reverted erofs_fs.h change.

> >
> > >
> > >  struct z_erofs_vle_decompressed_index {
> > >     __le16 di_advise;
> > > diff --git a/lib/compress.c b/lib/compress.c
> > > index 98be7a2..23e571c 100644
> > > --- a/lib/compress.c
> > > +++ b/lib/compress.c
> > > @@ -97,7 +97,26 @@ static void vle_write_indexes(struct z_erofs_vle_compress_ctx *ctx,
> > >             } else if (d0) {
> > >                     type = Z_EROFS_VLE_CLUSTER_TYPE_NONHEAD;
> > >
> > > -                   di.di_u.delta[0] = cpu_to_le16(d0);
> > > +                   /* If the |Z_EROFS_VLE_DI_D0_CBLKCNT| bit is set, parser
> > > +                    * will interpret |delta[0]| as size of pcluster, rather
> > > +                    * than distance to last head cluster. Normally this
> > > +                    * isn't a problem, because uncompressed extent size are
> > > +                    * below Z_EROFS_VLE_DI_D0_CBLKCNT * BLOCK_SIZE = 8MB.
> > > +                    * But with large pcluster it's possible to go over this
> > > +                    * number, resulting in corrupted compressed indices.
> > > +                    * To solve this, we use Z_EROFS_VLE_DI_D0_CBLKCNT-1 if
> > > +                    * the uncompressed extent size goes above 8MB. This is
> > > +                    * OK because if kernel sees another non-head cluster
> > > +                    * after going back by |delta[0]| blocks, kernel will
> > > +                    * just keep looking back.
> > > +                    */
> >
> > Would you mind updating this into the kernel comment style, I mean
> > /*
> >  * ...
> >  */
> > Instead?

Done

> >
> > > +                   if (d0 & Z_EROFS_VLE_DI_D0_CBLKCNT) {
> > > +                           di.di_u.delta[0] = max(
> > > +                                   d0 & (~Z_EROFS_VLE_DI_D0_CBLKCNT),
> > > +                                   Z_EROFS_VLE_DI_D0_CBLKCNT-1);
> >
> > May I ask if it's actually tested with big pcluster feature? It's
> > lack of cpu_to_le16() convert and even the original
> > Z_EROFS_VLE_DI_D0_CBLKCNT flag.

Sorry.. It was tested on a Little Endian machine, so I didn't discover
the missing cpu_to_le16. Added now.

>
> Sorry this part shouldn't have Z_EROFS_VLE_DI_D0_CBLKCNT flag.
>
> Btw, I think a proper change for this might be just:
>         if (d0 > Z_EROFS_VLE_DI_D0_CBLKCNT - 1)
>                 di.di_u.delta[0] = le16_to_cpu(Z_EROFS_VLE_DI_D0_CBLKCNT - 1);
>         else
>                 di.di_u.delta[0] = cpu_to_le16(d0);
> Or using max() to simplify above even more a bit.

This would work, but it's not optimal. For example,
Z_EROFS_VLE_DI_D0_CBLKCNT << 1
is greater than Z_EROFS_VLE_DI_D0_CBLKCNT, but it does not have the
11th bit set.
Using Z_EROFS_VLE_DI_D0_CBLKCNT-1 in this case would cause the kernel to
take more hops than necessary when finding the head cluster. A better
change would be:

        if (d0 > Z_EROFS_VLE_DI_D0_CBLKCNT - 1)
                di.di_u.delta[0] = le16_to_cpu(largest number smaller
than d0 that does not have Z_EROFS_VLE_DI_D0_CBLKCNT bit set);
        else
                di.di_u.delta[0] = cpu_to_le16(d0);

But how do we find "largest number smaller than d0 that does not have
Z_EROFS_VLE_DI_D0_CBLKCNT bit set" ?
Simple, clear the Z_EROFS_VLE_DI_D0_CBLKCNT bit, and set all bits
before that to 1. In code:
d0 & (~ Z_EROFS_VLE_DI_D0_CBLKCNT) | (Z_EROFS_VLE_DI_D0_CBLKCNT-1)

So final answer:

        if (d0 > Z_EROFS_VLE_DI_D0_CBLKCNT - 1)
                di.di_u.delta[0] = le16_to_cpu(d0 & (~
Z_EROFS_VLE_DI_D0_CBLKCNT) | (Z_EROFS_VLE_DI_D0_CBLKCNT-1));
        else
                di.di_u.delta[0] = cpu_to_le16(d0);



>
> Thanks,
> Gao Xiang
>
> >
> > Thanks,
> > Gao Xiang



-- 
Sincerely,

Kelvin Zhang

[PATCH v2] erofs-utils: lib: Fix 8MB bug on uncompressed extent size

[Kelvin Zhang via Linux-erofs]

Previously, uncompressed extent can be at most 8MB before mkfs.erofs
crashes on some error condition. This is due to a minor bug in how
compressed indices are encoded. This patch fixes the issue.

Signed-off-by: Kelvin Zhang <zhangkelvin@google.com>
---
 lib/compress.c | 32 +++++++++++++++++++++++++++++++-
 1 file changed, 31 insertions(+), 1 deletion(-)

diff --git a/lib/compress.c b/lib/compress.c
index 98be7a2..2f7ffa7 100644
--- a/lib/compress.c
+++ b/lib/compress.c
@@ -97,7 +97,37 @@ static void vle_write_indexes(struct z_erofs_vle_compress_ctx *ctx,
 		} else if (d0) {
 			type = Z_EROFS_VLE_CLUSTER_TYPE_NONHEAD;
 
-			di.di_u.delta[0] = cpu_to_le16(d0);
+			/*
+			 * If the |Z_EROFS_VLE_DI_D0_CBLKCNT| bit is set, parser
+			 * will interpret |delta[0]| as size of pcluster, rather
+			 * than distance to last head cluster. Normally this
+			 * isn't a problem, because uncompressed extent size are
+			 * below Z_EROFS_VLE_DI_D0_CBLKCNT * BLOCK_SIZE = 8MB.
+			 * But with large pcluster it's possible to go over this
+			 * number, resulting in corrupted compressed indices.
+			 * To solve this, we replace d0 with a number that's
+			 * smaller and doesn't have the
+			 * Z_EROFS_VLE_DI_D0_CBLKCNT bit set if
+			 * the uncompressed extent size goes above 8MB. This is
+			 * OK because if kernel sees another non-head cluster
+			 * after going back by |delta[0]| blocks, kernel will
+			 * just keep looking back.
+			 * The largest number smaller than d0 that doesn't have
+			 * Z_EROFS_VLE_DI_D0_CBLKCNT bit set is obtained by
+			 * first clearing Z_EROFS_VLE_DI_D0_CBLKCNT bit, then
+			 * set all bits before Z_EROFS_VLE_DI_D0_CBLKCNT to 1.
+			 * Using Z_EROFS_VLE_DI_D0_CBLKCNT-1 would work, but it
+			 * produces suboptimal indices in certain cases. e.g.
+			 * (Z_EROFS_VLE_DI_D0_CBLKCNT<<4)|
+			 * (Z_EROFS_VLE_DI_D0_CBLKCNT)
+			 */
+			if (d0 & Z_EROFS_VLE_DI_D0_CBLKCNT) {
+				di.di_u.delta[0] = cpu_to_le16(
+					(d0 & (~Z_EROFS_VLE_DI_D0_CBLKCNT)) |
+					(Z_EROFS_VLE_DI_D0_CBLKCNT-1));
+			} else {
+				di.di_u.delta[0] = cpu_to_le16(d0);
+			}
 			di.di_u.delta[1] = cpu_to_le16(d1);
 		} else {
 			type = raw ? Z_EROFS_VLE_CLUSTER_TYPE_PLAIN :
-- 
2.35.0.263.gb82422642f-goog

Re: [PATCH v1] erofs-utils: lib: Fix 8MB bug on uncompressed extent size

[Gao Xiang]

On Mon, Feb 07, 2022 at 09:38:45AM -0800, Kelvin Zhang wrote:
> -1
> 
> On Sun, Feb 6, 2022 at 6:08 PM Gao Xiang <hsiangkao@linux.alibaba.com> wrote:
> >
> > On Mon, Feb 07, 2022 at 07:59:50AM +0800, Gao Xiang wrote:
> > > Hi Kelvin,
> > >
> > > On Tue, Dec 21, 2021 at 06:03:07PM -0800, Kelvin Zhang wrote:
> > > > Previously, uncompressed extent can be at most 8MB before mkfs.erofs
> > > > crashes on some error condition. This is due to a minor bug in how
> > > > compressed indices are encoded. This patch fixes the issue.
> > > >
> > > > Signed-off-by: Kelvin Zhang <zhangkelvin@google.com>
> > > > ---
> > > >  include/erofs_fs.h |  2 +-
> > > >  lib/compress.c     | 21 ++++++++++++++++++++-
> > > >  2 files changed, 21 insertions(+), 2 deletions(-)
> > > >
> > > > diff --git a/include/erofs_fs.h b/include/erofs_fs.h
> > > > index 9a91877..13eaf24 100644
> > > > --- a/include/erofs_fs.h
> > > > +++ b/include/erofs_fs.h
> > > > @@ -353,7 +353,7 @@ enum {
> > > >   * compressed block count of a compressed extent (in logical clusters, aka.
> > > >   * block count of a pcluster).
> > > >   */
> > > > -#define Z_EROFS_VLE_DI_D0_CBLKCNT          (1 << 11)
> > > > +#define Z_EROFS_VLE_DI_D0_CBLKCNT          (1U << 11)
> > >
> > > If erofs_fs.h update is necessary, I prefer to update in-kernel
> > > header first. Would you mind making a kernel patch for this if needed?
> 
> Reverted erofs_fs.h change.
> 
> > >
> > > >
> > > >  struct z_erofs_vle_decompressed_index {
> > > >     __le16 di_advise;
> > > > diff --git a/lib/compress.c b/lib/compress.c
> > > > index 98be7a2..23e571c 100644
> > > > --- a/lib/compress.c
> > > > +++ b/lib/compress.c
> > > > @@ -97,7 +97,26 @@ static void vle_write_indexes(struct z_erofs_vle_compress_ctx *ctx,
> > > >             } else if (d0) {
> > > >                     type = Z_EROFS_VLE_CLUSTER_TYPE_NONHEAD;
> > > >
> > > > -                   di.di_u.delta[0] = cpu_to_le16(d0);
> > > > +                   /* If the |Z_EROFS_VLE_DI_D0_CBLKCNT| bit is set, parser
> > > > +                    * will interpret |delta[0]| as size of pcluster, rather
> > > > +                    * than distance to last head cluster. Normally this
> > > > +                    * isn't a problem, because uncompressed extent size are
> > > > +                    * below Z_EROFS_VLE_DI_D0_CBLKCNT * BLOCK_SIZE = 8MB.
> > > > +                    * But with large pcluster it's possible to go over this
> > > > +                    * number, resulting in corrupted compressed indices.
> > > > +                    * To solve this, we use Z_EROFS_VLE_DI_D0_CBLKCNT-1 if
> > > > +                    * the uncompressed extent size goes above 8MB. This is
> > > > +                    * OK because if kernel sees another non-head cluster
> > > > +                    * after going back by |delta[0]| blocks, kernel will
> > > > +                    * just keep looking back.
> > > > +                    */
> > >
> > > Would you mind updating this into the kernel comment style, I mean
> > > /*
> > >  * ...
> > >  */
> > > Instead?
> 
> Done
> 
> > >
> > > > +                   if (d0 & Z_EROFS_VLE_DI_D0_CBLKCNT) {
> > > > +                           di.di_u.delta[0] = max(
> > > > +                                   d0 & (~Z_EROFS_VLE_DI_D0_CBLKCNT),
> > > > +                                   Z_EROFS_VLE_DI_D0_CBLKCNT-1);
> > >
> > > May I ask if it's actually tested with big pcluster feature? It's
> > > lack of cpu_to_le16() convert and even the original
> > > Z_EROFS_VLE_DI_D0_CBLKCNT flag.
> 
> Sorry.. It was tested on a Little Endian machine, so I didn't discover
> the missing cpu_to_le16. Added now.
> 
> >
> > Sorry this part shouldn't have Z_EROFS_VLE_DI_D0_CBLKCNT flag.
> >
> > Btw, I think a proper change for this might be just:
> >         if (d0 > Z_EROFS_VLE_DI_D0_CBLKCNT - 1)
> >                 di.di_u.delta[0] = le16_to_cpu(Z_EROFS_VLE_DI_D0_CBLKCNT - 1);
> >         else
> >                 di.di_u.delta[0] = cpu_to_le16(d0);
> > Or using max() to simplify above even more a bit.
> 
> This would work, but it's not optimal. For example,
> Z_EROFS_VLE_DI_D0_CBLKCNT << 1
> is greater than Z_EROFS_VLE_DI_D0_CBLKCNT, but it does not have the
> 11th bit set.
> Using Z_EROFS_VLE_DI_D0_CBLKCNT-1 in this case would cause the kernel to
> take more hops than necessary when finding the head cluster. A better
> change would be:
> 
>         if (d0 > Z_EROFS_VLE_DI_D0_CBLKCNT - 1)
>                 di.di_u.delta[0] = le16_to_cpu(largest number smaller
> than d0 that does not have Z_EROFS_VLE_DI_D0_CBLKCNT bit set);
>         else
>                 di.di_u.delta[0] = cpu_to_le16(d0);
> 
> But how do we find "largest number smaller than d0 that does not have
> Z_EROFS_VLE_DI_D0_CBLKCNT bit set" ?
> Simple, clear the Z_EROFS_VLE_DI_D0_CBLKCNT bit, and set all bits
> before that to 1. In code:
> d0 & (~ Z_EROFS_VLE_DI_D0_CBLKCNT) | (Z_EROFS_VLE_DI_D0_CBLKCNT-1)
> 
> So final answer:
> 
>         if (d0 > Z_EROFS_VLE_DI_D0_CBLKCNT - 1)
>                 di.di_u.delta[0] = le16_to_cpu(d0 & (~
> Z_EROFS_VLE_DI_D0_CBLKCNT) | (Z_EROFS_VLE_DI_D0_CBLKCNT-1));
>         else
>                 di.di_u.delta[0] = cpu_to_le16(d0);
> 

That may work for non-compact indexes, but it's somewhat unsafe for
compact indexes (especially compact 2B), since the valid bits for
each lcluster are 14 (12 plus 2-bit lcluster type):
  for head lclusters, it stores lclusterofs;
  for non-head lclusters, it stores delta0 (lookback distance) or
                                    delta1 (lookforward distance)
                          conditionally.

That is also why Z_EROFS_VLE_DI_D0_CBLKCNT is set as (1 << 11). So in
order to make them unique, I suggest just don't reuse higher bits even
for non-compact indexes... (I think we could stand just looking back
multiple times instead for such large logical extents...)

Actually "* eg. for 4k page-sized cluster, maximum 4K*64k = 256M)" is
somewhat outdated now after compact-indexes was introduced. If you
have time, could you submit a kernel patch to fix the description
together?

Thanks,
Gao Xiang

[PATCH v3] erofs-utils: lib: Fix 8MB bug on uncompressed extent size

[Kelvin Zhang via Linux-erofs]

Previously, uncompressed extent can be at most 8MB before mkfs.erofs
crashes on some error condition. This is due to a minor bug in how
compressed indices are encoded. This patch fixes the issue.

Signed-off-by: Kelvin Zhang <zhangkelvin@google.com>
---
 lib/compress.c | 18 +++++++++++++++++-
 1 file changed, 17 insertions(+), 1 deletion(-)

diff --git a/lib/compress.c b/lib/compress.c
index 98be7a2..add95f5 100644
--- a/lib/compress.c
+++ b/lib/compress.c
@@ -97,7 +97,23 @@ static void vle_write_indexes(struct z_erofs_vle_compress_ctx *ctx,
 		} else if (d0) {
 			type = Z_EROFS_VLE_CLUSTER_TYPE_NONHEAD;
 
-			di.di_u.delta[0] = cpu_to_le16(d0);
+			/*
+			 * If the |Z_EROFS_VLE_DI_D0_CBLKCNT| bit is set, parser
+			 * will interpret |delta[0]| as size of pcluster, rather
+			 * than distance to last head cluster. Normally this
+			 * isn't a problem, because uncompressed extent size are
+			 * below Z_EROFS_VLE_DI_D0_CBLKCNT * BLOCK_SIZE = 8MB.
+			 * But with large pcluster it's possible to go over this
+			 * number, resulting in corrupted compressed indices.
+			 * To solve this, we replace d0 with
+			 * Z_EROFS_VLE_DI_D0_CBLKCNT-1.
+			 */
+			if (d0 > Z_EROFS_VLE_DI_D0_CBLKCNT) {
+				di.di_u.delta[0] = cpu_to_le16(
+					Z_EROFS_VLE_DI_D0_CBLKCNT-1);
+			} else {
+				di.di_u.delta[0] = cpu_to_le16(d0);
+			}
 			di.di_u.delta[1] = cpu_to_le16(d1);
 		} else {
 			type = raw ? Z_EROFS_VLE_CLUSTER_TYPE_PLAIN :
-- 
2.35.0.263.gb82422642f-goog

Re: [PATCH v3] erofs-utils: lib: Fix 8MB bug on uncompressed extent size

[Gao Xiang]

On Tue, Feb 08, 2022 at 10:43:17AM -0800, Kelvin Zhang wrote:
> Previously, uncompressed extent can be at most 8MB before mkfs.erofs
> crashes on some error condition. This is due to a minor bug in how
> compressed indices are encoded. This patch fixes the issue.
> 
> Signed-off-by: Kelvin Zhang <zhangkelvin@google.com>
> ---
>  lib/compress.c | 18 +++++++++++++++++-
>  1 file changed, 17 insertions(+), 1 deletion(-)
> 
> diff --git a/lib/compress.c b/lib/compress.c
> index 98be7a2..add95f5 100644
> --- a/lib/compress.c
> +++ b/lib/compress.c
> @@ -97,7 +97,23 @@ static void vle_write_indexes(struct z_erofs_vle_compress_ctx *ctx,
>  		} else if (d0) {
>  			type = Z_EROFS_VLE_CLUSTER_TYPE_NONHEAD;
>  
> -			di.di_u.delta[0] = cpu_to_le16(d0);
> +			/*
> +			 * If the |Z_EROFS_VLE_DI_D0_CBLKCNT| bit is set, parser
> +			 * will interpret |delta[0]| as size of pcluster, rather
> +			 * than distance to last head cluster. Normally this
> +			 * isn't a problem, because uncompressed extent size are
> +			 * below Z_EROFS_VLE_DI_D0_CBLKCNT * BLOCK_SIZE = 8MB.
> +			 * But with large pcluster it's possible to go over this
> +			 * number, resulting in corrupted compressed indices.
> +			 * To solve this, we replace d0 with
> +			 * Z_EROFS_VLE_DI_D0_CBLKCNT-1.
> +			 */
> +			if (d0 > Z_EROFS_VLE_DI_D0_CBLKCNT) {

Thanks for the new version.

I think this part would be "if (d0 >= Z_EROFS_VLE_DI_D0_CBLKCNT)",
and already applied with minor styling changes:

https://git.kernel.org/pub/scm/linux/kernel/git/xiang/erofs-utils.git/commit/?id=789ac9b03c2c0d27c5be81cb8d026e2300ae822e

Thanks,
Gao Xiang

> +				di.di_u.delta[0] = cpu_to_le16(
> +					Z_EROFS_VLE_DI_D0_CBLKCNT-1);
> +			} else {
> +				di.di_u.delta[0] = cpu_to_le16(d0);
> +			}
>  			di.di_u.delta[1] = cpu_to_le16(d1);
>  		} else {
>  			type = raw ? Z_EROFS_VLE_CLUSTER_TYPE_PLAIN :
> -- 
> 2.35.0.263.gb82422642f-goog