[PATCH v2] ext4: fix underflow in ext4_max_bitmap_size()

[PATCH v2] ext4: fix underflow in ext4_max_bitmap_size()

[Zhang Yi]

The same to commit 1c2d14212b15 ("ext2: Fix underflow in ext2_max_size()")
in ext2 filesystem, ext4 driver has the same issue with 64K block size
and ^huge_file, fix this issue the same as ext2. This patch also revert
commit 75ca6ad408f4 ("ext4: fix loff_t overflow in ext4_max_bitmap_size()")
because it's no longer needed.

Signed-off-by: Zhang Yi <yi.zhang@huawei.com>
---
v2->v1: use DIV_ROUND_UP_ULL instead of DIV_ROUND_UP.

 fs/ext4/super.c | 46 +++++++++++++++++++++++++++++++---------------
 1 file changed, 31 insertions(+), 15 deletions(-)

diff --git a/fs/ext4/super.c b/fs/ext4/super.c
index c5021ca0a28a..95608c2127e7 100644
--- a/fs/ext4/super.c
+++ b/fs/ext4/super.c
@@ -3468,8 +3468,9 @@ static loff_t ext4_max_size(int blkbits, int has_huge_files)
  */
 static loff_t ext4_max_bitmap_size(int bits, int has_huge_files)
 {
-	unsigned long long upper_limit, res = EXT4_NDIR_BLOCKS;
+	loff_t upper_limit, res = EXT4_NDIR_BLOCKS;
 	int meta_blocks;
+	unsigned int ppb = 1 << (bits - 2);
 
 	/*
 	 * This is calculated to be the largest file size for a dense, block
@@ -3501,27 +3502,42 @@ static loff_t ext4_max_bitmap_size(int bits, int has_huge_files)
 
 	}
 
-	/* indirect blocks */
-	meta_blocks = 1;
-	/* double indirect blocks */
-	meta_blocks += 1 + (1LL << (bits-2));
-	/* tripple indirect blocks */
-	meta_blocks += 1 + (1LL << (bits-2)) + (1LL << (2*(bits-2)));
-
-	upper_limit -= meta_blocks;
-	upper_limit <<= bits;
-
+	/* Compute how many blocks we can address by block tree */
 	res += 1LL << (bits-2);
 	res += 1LL << (2*(bits-2));
 	res += 1LL << (3*(bits-2));
+	/* Compute how many metadata blocks are needed */
+	meta_blocks = 1;
+	meta_blocks += 1 + ppb;
+	meta_blocks += 1 + ppb + ppb * ppb;
+	/* Does block tree limit file size? */
+	if (res + meta_blocks <= upper_limit)
+		goto check_lfs;
+
+	res = upper_limit;
+	/* How many metadata blocks are needed for addressing upper_limit? */
+	upper_limit -= EXT4_NDIR_BLOCKS;
+	/* indirect blocks */
+	meta_blocks = 1;
+	upper_limit -= ppb;
+	/* double indirect blocks */
+	if (upper_limit < ppb * ppb) {
+		meta_blocks += 1 + DIV_ROUND_UP_ULL(upper_limit, ppb);
+		res -= meta_blocks;
+		goto check_lfs;
+	}
+	meta_blocks += 1 + ppb;
+	upper_limit -= ppb * ppb;
+	/* tripple indirect blocks for the rest */
+	meta_blocks += 1 + DIV_ROUND_UP_ULL(upper_limit, ppb) +
+		DIV_ROUND_UP_ULL(upper_limit, ppb*ppb);
+	res -= meta_blocks;
+check_lfs:
 	res <<= bits;
-	if (res > upper_limit)
-		res = upper_limit;
-
 	if (res > MAX_LFS_FILESIZE)
 		res = MAX_LFS_FILESIZE;
 
-	return (loff_t)res;
+	return res;
 }
 
 static ext4_fsblk_t descriptor_loc(struct super_block *sb,
-- 
2.31.1

Re: [PATCH v2] ext4: fix underflow in ext4_max_bitmap_size()

[Jan Kara]

On Fri 25-02-22 18:28:37, Zhang Yi wrote:
> The same to commit 1c2d14212b15 ("ext2: Fix underflow in ext2_max_size()")
> in ext2 filesystem, ext4 driver has the same issue with 64K block size
> and ^huge_file, fix this issue the same as ext2. This patch also revert
> commit 75ca6ad408f4 ("ext4: fix loff_t overflow in ext4_max_bitmap_size()")
> because it's no longer needed.
> 
> Signed-off-by: Zhang Yi <yi.zhang@huawei.com>

Thanks for the patch. I would not refer to ext2 patch in the changelog - it
is better to have it self-contained. AFAIU the problem is that (meta_blocks
> upper_limit) for 64k blocksize and ^huge_file and so upper_limit would
underflow during the computations, am I right?

Also two comments below:

> diff --git a/fs/ext4/super.c b/fs/ext4/super.c
> index c5021ca0a28a..95608c2127e7 100644
> --- a/fs/ext4/super.c
> +++ b/fs/ext4/super.c
> @@ -3468,8 +3468,9 @@ static loff_t ext4_max_size(int blkbits, int has_huge_files)
>   */
>  static loff_t ext4_max_bitmap_size(int bits, int has_huge_files)
>  {
> -	unsigned long long upper_limit, res = EXT4_NDIR_BLOCKS;
> +	loff_t upper_limit, res = EXT4_NDIR_BLOCKS;
>  	int meta_blocks;
> +	unsigned int ppb = 1 << (bits - 2);
>  
>  	/*
>  	 * This is calculated to be the largest file size for a dense, block
> @@ -3501,27 +3502,42 @@ static loff_t ext4_max_bitmap_size(int bits, int has_huge_files)
>  
>  	}
>  
> -	/* indirect blocks */
> -	meta_blocks = 1;
> -	/* double indirect blocks */
> -	meta_blocks += 1 + (1LL << (bits-2));
> -	/* tripple indirect blocks */
> -	meta_blocks += 1 + (1LL << (bits-2)) + (1LL << (2*(bits-2)));
> -
> -	upper_limit -= meta_blocks;
> -	upper_limit <<= bits;
> -
> +	/* Compute how many blocks we can address by block tree */
>  	res += 1LL << (bits-2);
>  	res += 1LL << (2*(bits-2));
>  	res += 1LL << (3*(bits-2));

When you have the 'ppb' convenience variable, perhaps you can update this
math to:

	res = EXT4_NDIR_BLOCKS + ppb + ppb*ppb + ((long long)ppb)*ppb*ppb;

It is easier to understand and matches how you compute meta_blocks as well.

> +	/* Compute how many metadata blocks are needed */
> +	meta_blocks = 1;
> +	meta_blocks += 1 + ppb;
> +	meta_blocks += 1 + ppb + ppb * ppb;
> +	/* Does block tree limit file size? */
> +	if (res + meta_blocks <= upper_limit)
> +		goto check_lfs;
> +
> +	res = upper_limit;
> +	/* How many metadata blocks are needed for addressing upper_limit? */
> +	upper_limit -= EXT4_NDIR_BLOCKS;
> +	/* indirect blocks */
> +	meta_blocks = 1;
> +	upper_limit -= ppb;
> +	/* double indirect blocks */
> +	if (upper_limit < ppb * ppb) {
> +		meta_blocks += 1 + DIV_ROUND_UP_ULL(upper_limit, ppb);
> +		res -= meta_blocks;
> +		goto check_lfs;
> +	}
> +	meta_blocks += 1 + ppb;
> +	upper_limit -= ppb * ppb;
> +	/* tripple indirect blocks for the rest */
> +	meta_blocks += 1 + DIV_ROUND_UP_ULL(upper_limit, ppb) +
> +		DIV_ROUND_UP_ULL(upper_limit, ppb*ppb);
> +	res -= meta_blocks;
> +check_lfs:
>  	res <<= bits;

Cannot this overflow loff_t again? I mean if upper_limit == (1 << 48) - 1
and we have 64k blocksize, 'res' will be larger than (1 << 47) and thus 
res << 16 will be greater than 1 << 63 => negative... Am I missing
something?

								Honza
-- 
Jan Kara <jack@suse.com>
SUSE Labs, CR

Re: [PATCH v2] ext4: fix underflow in ext4_max_bitmap_size()

[Zhang Yi]

On 2022/2/25 20:38, Jan Kara wrote:
> On Fri 25-02-22 18:28:37, Zhang Yi wrote:
>> The same to commit 1c2d14212b15 ("ext2: Fix underflow in ext2_max_size()")
>> in ext2 filesystem, ext4 driver has the same issue with 64K block size
>> and ^huge_file, fix this issue the same as ext2. This patch also revert
>> commit 75ca6ad408f4 ("ext4: fix loff_t overflow in ext4_max_bitmap_size()")
>> because it's no longer needed.
>>
>> Signed-off-by: Zhang Yi <yi.zhang@huawei.com>
> 
> Thanks for the patch. I would not refer to ext2 patch in the changelog - it
> is better to have it self-contained. AFAIU the problem is that (meta_blocks
>> upper_limit) for 64k blocksize and ^huge_file and so upper_limit would
> underflow during the computations, am I right?

Thanks for the review. Yes, I will rewrite the change log.

> 
> Also two comments below:
> 
>> diff --git a/fs/ext4/super.c b/fs/ext4/super.c
>> index c5021ca0a28a..95608c2127e7 100644
>> --- a/fs/ext4/super.c
>> +++ b/fs/ext4/super.c
>> @@ -3468,8 +3468,9 @@ static loff_t ext4_max_size(int blkbits, int has_huge_files)
>>   */
>>  static loff_t ext4_max_bitmap_size(int bits, int has_huge_files)
>>  {
>> -	unsigned long long upper_limit, res = EXT4_NDIR_BLOCKS;
>> +	loff_t upper_limit, res = EXT4_NDIR_BLOCKS;
>>  	int meta_blocks;
>> +	unsigned int ppb = 1 << (bits - 2);
>>  
>>  	/*
>>  	 * This is calculated to be the largest file size for a dense, block
>> @@ -3501,27 +3502,42 @@ static loff_t ext4_max_bitmap_size(int bits, int has_huge_files)
>>  
>>  	}
>>  
>> -	/* indirect blocks */
>> -	meta_blocks = 1;
>> -	/* double indirect blocks */
>> -	meta_blocks += 1 + (1LL << (bits-2));
>> -	/* tripple indirect blocks */
>> -	meta_blocks += 1 + (1LL << (bits-2)) + (1LL << (2*(bits-2)));
>> -
>> -	upper_limit -= meta_blocks;
>> -	upper_limit <<= bits;
>> -
>> +	/* Compute how many blocks we can address by block tree */
>>  	res += 1LL << (bits-2);
>>  	res += 1LL << (2*(bits-2));
>>  	res += 1LL << (3*(bits-2));
> 
> When you have the 'ppb' convenience variable, perhaps you can update this
> math to:
> 
> 	res = EXT4_NDIR_BLOCKS + ppb + ppb*ppb + ((long long)ppb)*ppb*ppb;
> 
> It is easier to understand and matches how you compute meta_blocks as well.
> 
>> +	/* Compute how many metadata blocks are needed */
>> +	meta_blocks = 1;
>> +	meta_blocks += 1 + ppb;
>> +	meta_blocks += 1 + ppb + ppb * ppb;
>> +	/* Does block tree limit file size? */
>> +	if (res + meta_blocks <= upper_limit)
>> +		goto check_lfs;
>> +
>> +	res = upper_limit;
>> +	/* How many metadata blocks are needed for addressing upper_limit? */
>> +	upper_limit -= EXT4_NDIR_BLOCKS;
>> +	/* indirect blocks */
>> +	meta_blocks = 1;
>> +	upper_limit -= ppb;
>> +	/* double indirect blocks */
>> +	if (upper_limit < ppb * ppb) {
>> +		meta_blocks += 1 + DIV_ROUND_UP_ULL(upper_limit, ppb);
>> +		res -= meta_blocks;
>> +		goto check_lfs;
>> +	}
>> +	meta_blocks += 1 + ppb;
>> +	upper_limit -= ppb * ppb;
>> +	/* tripple indirect blocks for the rest */
>> +	meta_blocks += 1 + DIV_ROUND_UP_ULL(upper_limit, ppb) +
>> +		DIV_ROUND_UP_ULL(upper_limit, ppb*ppb);
>> +	res -= meta_blocks;
>> +check_lfs:
>>  	res <<= bits;
> 
> Cannot this overflow loff_t again? I mean if upper_limit == (1 << 48) - 1
> and we have 64k blocksize, 'res' will be larger than (1 << 47) and thus 
> res << 16 will be greater than 1 << 63 => negative... Am I missing
> something?
> 

If upper_limit==(1 << 48) - 1, we could address the whole data blocks, the 'res'
is equal to EXT4_NDIR_BLOCKS + ppb + ppb*ppb + ((long long)ppb)*ppb*ppb, it's
smaller than (1 << 43) - 1, so res << 16 is still smaller 1 << 59, so it cannot
overflow loff_t again.

Thanks,
Yi.

Re: [PATCH v2] ext4: fix underflow in ext4_max_bitmap_size()

[Jan Kara]

On Sat 26-02-22 10:30:31, Zhang Yi wrote:
> On 2022/2/25 20:38, Jan Kara wrote:
> > On Fri 25-02-22 18:28:37, Zhang Yi wrote:
> >> +	/* Compute how many metadata blocks are needed */
> >> +	meta_blocks = 1;
> >> +	meta_blocks += 1 + ppb;
> >> +	meta_blocks += 1 + ppb + ppb * ppb;
> >> +	/* Does block tree limit file size? */
> >> +	if (res + meta_blocks <= upper_limit)
> >> +		goto check_lfs;
> >> +
> >> +	res = upper_limit;
> >> +	/* How many metadata blocks are needed for addressing upper_limit? */
> >> +	upper_limit -= EXT4_NDIR_BLOCKS;
> >> +	/* indirect blocks */
> >> +	meta_blocks = 1;
> >> +	upper_limit -= ppb;
> >> +	/* double indirect blocks */
> >> +	if (upper_limit < ppb * ppb) {
> >> +		meta_blocks += 1 + DIV_ROUND_UP_ULL(upper_limit, ppb);
> >> +		res -= meta_blocks;
> >> +		goto check_lfs;
> >> +	}
> >> +	meta_blocks += 1 + ppb;
> >> +	upper_limit -= ppb * ppb;
> >> +	/* tripple indirect blocks for the rest */
> >> +	meta_blocks += 1 + DIV_ROUND_UP_ULL(upper_limit, ppb) +
> >> +		DIV_ROUND_UP_ULL(upper_limit, ppb*ppb);
> >> +	res -= meta_blocks;
> >> +check_lfs:
> >>  	res <<= bits;
> > 
> > Cannot this overflow loff_t again? I mean if upper_limit == (1 << 48) - 1
> > and we have 64k blocksize, 'res' will be larger than (1 << 47) and thus 
> > res << 16 will be greater than 1 << 63 => negative... Am I missing
> > something?
> > 
> 
> If upper_limit==(1 << 48) - 1, we could address the whole data blocks, the 'res'
> is equal to EXT4_NDIR_BLOCKS + ppb + ppb*ppb + ((long long)ppb)*ppb*ppb, it's
> smaller than (1 << 43) - 1, so res << 16 is still smaller 1 << 59, so it cannot
> overflow loff_t again.

Indeed, sorry for confusion. Not sure where I did mistake in my math
previously.

								Honza
-- 
Jan Kara <jack@suse.com>
SUSE Labs, CR