[PATCH 0/2] ext4: fixes for mb_check_buddy integrity checks

[PATCH 0/2] ext4: fixes for mb_check_buddy integrity checks

[Yongjian Sun]

From: Yongjian Sun <sunyongjian1@huawei.com>

Yongjian Sun (2):
  ext4: fix incorrect group number assertion in mb_check_buddy for
    exhausted preallocations
  ext4: improve integrity checking in __mb_check_buddy by enhancing
    order-0 validation

 fs/ext4/mballoc.c | 59 +++++++++++++++++++++++++++++++++--------------
 1 file changed, 42 insertions(+), 17 deletions(-)

-- 
2.39.2

[PATCH 1/2] ext4: fix incorrect group number assertion in mb_check_buddy for exhausted preallocations

[Yongjian Sun]

From: Yongjian Sun <sunyongjian1@huawei.com>

When the MB_CHECK_ASSERT macro is enabled, an assertion failure can
occur in __mb_check_buddy when checking preallocated blocks (pa) in
a block group:

Assertion failure in mb_free_blocks() : "groupnr == e4b->bd_group"

This happens when a pa at the very end of a block group (e.g.,
pa_pstart=32765, pa_len=3 in a group of 32768 blocks) becomes
exhausted - its pa_pstart is advanced by pa_len to 32768, which
lies in the next block group. If this exhausted pa (with pa_len == 0)
is still in the bb_prealloc_list during the buddy check, the assertion
incorrectly flags it as belonging to the wrong group. A possible
sequence is as follows:

ext4_mb_new_blocks
  ext4_mb_release_context
    pa->pa_pstart += EXT4_C2B(sbi, ac->ac_b_ex.fe_len)
    pa->pa_len -= ac->ac_b_ex.fe_len

	                 __mb_check_buddy
                           for each pa in group
                             ext4_get_group_no_and_offset
                             MB_CHECK_ASSERT(groupnr == e4b->bd_group)

To fix this, we modify the check to skip block group validation for
exhausted preallocations (where pa_len == 0). Such entries are in a
transitional state and will be removed from the list soon, so they
should not trigger an assertion. This change prevents the false
positive while maintaining the integrity of the checks for active
allocations.

Fixes: c9de560ded61f ("ext4: Add multi block allocator for ext4")
Signed-off-by: Yongjian Sun <sunyongjian1@huawei.com>
Reviewed-by: Baokun Li <libaokun1@huawei.com>
---
 fs/ext4/mballoc.c | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/fs/ext4/mballoc.c b/fs/ext4/mballoc.c
index 9087183602e4..194a9f995c36 100644
--- a/fs/ext4/mballoc.c
+++ b/fs/ext4/mballoc.c
@@ -768,6 +768,8 @@ static void __mb_check_buddy(struct ext4_buddy *e4b, char *file,
 		ext4_group_t groupnr;
 		struct ext4_prealloc_space *pa;
 		pa = list_entry(cur, struct ext4_prealloc_space, pa_group_list);
+		if (!pa->pa_len)
+			continue;
 		ext4_get_group_no_and_offset(sb, pa->pa_pstart, &groupnr, &k);
 		MB_CHECK_ASSERT(groupnr == e4b->bd_group);
 		for (i = 0; i < pa->pa_len; i++)
-- 
2.39.2

[PATCH 2/2] ext4: improve integrity checking in __mb_check_buddy by enhancing order-0 validation

[Yongjian Sun]

From: Yongjian Sun <sunyongjian1@huawei.com>

When the MB_CHECK_ASSERT macro is enabled, we found that the
current validation logic in __mb_check_buddy has a gap in
detecting certain invalid buddy states, particularly related
to order-0 (bitmap) bits.

The original logic consists of three steps:
1. Validates higher-order buddies: if a higher-order bit is
set, at most one of the two corresponding lower-order bits
may be free; if a higher-order bit is clear, both lower-order
bits must be allocated (and their bitmap bits must be 0).
2. For any set bit in order-0, ensures all corresponding
higher-order bits are not free.
3. Verifies that all preallocated blocks (pa) in the group
have pa_pstart within bounds and their bitmap bits marked as
allocated.

However, this approach fails to properly validate cases where
order-0 bits are incorrectly cleared (0), allowing some invalid
configurations to pass:

               corrupt            integral

order 3           1                  1
order 2       1       1          1       1
order 1     1   1   1   1      1   1   1   1
order 0    0 0 1 1 1 1 1 1    1 1 1 1 1 1 1 1

Here we get two adjacent free blocks at order-0 with inconsistent
higher-order state, and the right one shows the correct scenario.

The root cause is insufficient validation of order-0 zero bits.
To fix this and improve completeness without significant performance
cost, we refine the logic:

1. Maintain the top-down higher-order validation, but we no longer
check the cases where the higher-order bit is 0, as this case will
be covered in step 2.
2. Enhance order-0 checking by examining pairs of bits:
   - If either bit in a pair is set (1), all corresponding
     higher-order bits must not be free.
   - If both bits are clear (0), then exactly one of the
     corresponding higher-order bits must be free
3. Keep the preallocation (pa) validation unchanged.

This change closes the validation gap, ensuring illegal buddy states
involving order-0 are correctly detected, while removing redundant
checks and maintaining efficiency.

Fixes: c9de560ded61f ("ext4: Add multi block allocator for ext4")
Signed-off-by: Yongjian Sun <sunyongjian1@huawei.com>
Reviewed-by: Baokun Li <libaokun1@huawei.com>
---
 fs/ext4/mballoc.c | 57 +++++++++++++++++++++++++++++++++--------------
 1 file changed, 40 insertions(+), 17 deletions(-)

diff --git a/fs/ext4/mballoc.c b/fs/ext4/mballoc.c
index 194a9f995c36..e6cd27507c3e 100644
--- a/fs/ext4/mballoc.c
+++ b/fs/ext4/mballoc.c
@@ -682,6 +682,24 @@ do {									\
 	}								\
 } while (0)
 
+/*
+ * Perform buddy integrity check with the following steps:
+ *
+ * 1. Top-down validation (from highest order down to order 1, excluding order-0 bitmap):
+ *    For each pair of adjacent orders, if a higher-order bit is set (indicating a free block),
+ *    at most one of the two corresponding lower-order bits may be clear (free).
+ *
+ * 2. Order-0 (bitmap) validation, performed on bit pairs:
+ *    - If either bit in a pair is set (1, allocated), then all corresponding higher-order bits
+ *      must not be free (0).
+ *    - If both bits in a pair are clear (0, free), then exactly one of the corresponding
+ *      higher-order bits must be free (0).
+ *
+ * 3. Preallocation (pa) list validation:
+ *    For each preallocated block (pa) in the group:
+ *    - Verify that pa_pstart falls within the bounds of this block group.
+ *    - Ensure the corresponding bit(s) in the order-0 bitmap are marked as allocated (1).
+ */
 static void __mb_check_buddy(struct ext4_buddy *e4b, char *file,
 				const char *function, int line)
 {
@@ -723,15 +741,6 @@ static void __mb_check_buddy(struct ext4_buddy *e4b, char *file,
 				continue;
 			}
 
-			/* both bits in buddy2 must be 1 */
-			MB_CHECK_ASSERT(mb_test_bit(i << 1, buddy2));
-			MB_CHECK_ASSERT(mb_test_bit((i << 1) + 1, buddy2));
-
-			for (j = 0; j < (1 << order); j++) {
-				k = (i * (1 << order)) + j;
-				MB_CHECK_ASSERT(
-					!mb_test_bit(k, e4b->bd_bitmap));
-			}
 			count++;
 		}
 		MB_CHECK_ASSERT(e4b->bd_info->bb_counters[order] == count);
@@ -747,15 +756,29 @@ static void __mb_check_buddy(struct ext4_buddy *e4b, char *file,
 				fragments++;
 				fstart = i;
 			}
-			continue;
+		} else {
+			fstart = -1;
 		}
-		fstart = -1;
-		/* check used bits only */
-		for (j = 0; j < e4b->bd_blkbits + 1; j++) {
-			buddy2 = mb_find_buddy(e4b, j, &max2);
-			k = i >> j;
-			MB_CHECK_ASSERT(k < max2);
-			MB_CHECK_ASSERT(mb_test_bit(k, buddy2));
+		if (!(i & 1)) {
+			int in_use, zero_bit_count;
+
+			in_use = mb_test_bit(i, buddy) || mb_test_bit(i + 1, buddy);
+			zero_bit_count = 0;
+			for (j = 1; j < e4b->bd_blkbits + 2; j++) {
+				buddy2 = mb_find_buddy(e4b, j, &max2);
+				k = i >> j;
+				MB_CHECK_ASSERT(k < max2);
+				if (in_use) {
+					/* can not contain any 0 at all orders */
+					MB_CHECK_ASSERT(mb_test_bit(k, buddy2));
+				} else {
+					/* there is and can only be one 0 at all orders */
+					if (!mb_test_bit(k, buddy2)) {
+						zero_bit_count++;
+						MB_CHECK_ASSERT(zero_bit_count == 1);
+					}
+				}
+			}
 		}
 	}
 	MB_CHECK_ASSERT(!EXT4_MB_GRP_NEED_INIT(e4b->bd_info));
-- 
2.39.2

Re: [PATCH 1/2] ext4: fix incorrect group number assertion in mb_check_buddy for exhausted preallocations

[Jan Kara]

On Wed 05-11-25 15:42:49, Yongjian Sun wrote:
> From: Yongjian Sun <sunyongjian1@huawei.com>
> 
> When the MB_CHECK_ASSERT macro is enabled, an assertion failure can
> occur in __mb_check_buddy when checking preallocated blocks (pa) in
> a block group:
> 
> Assertion failure in mb_free_blocks() : "groupnr == e4b->bd_group"
> 
> This happens when a pa at the very end of a block group (e.g.,
> pa_pstart=32765, pa_len=3 in a group of 32768 blocks) becomes
> exhausted - its pa_pstart is advanced by pa_len to 32768, which
> lies in the next block group. If this exhausted pa (with pa_len == 0)
> is still in the bb_prealloc_list during the buddy check, the assertion
> incorrectly flags it as belonging to the wrong group. A possible
> sequence is as follows:
> 
> ext4_mb_new_blocks
>   ext4_mb_release_context
>     pa->pa_pstart += EXT4_C2B(sbi, ac->ac_b_ex.fe_len)
>     pa->pa_len -= ac->ac_b_ex.fe_len
> 
> 	                 __mb_check_buddy
>                            for each pa in group
>                              ext4_get_group_no_and_offset
>                              MB_CHECK_ASSERT(groupnr == e4b->bd_group)
> 
> To fix this, we modify the check to skip block group validation for
> exhausted preallocations (where pa_len == 0). Such entries are in a
> transitional state and will be removed from the list soon, so they
> should not trigger an assertion. This change prevents the false
> positive while maintaining the integrity of the checks for active
> allocations.
> 
> Fixes: c9de560ded61f ("ext4: Add multi block allocator for ext4")
> Signed-off-by: Yongjian Sun <sunyongjian1@huawei.com>
> Reviewed-by: Baokun Li <libaokun1@huawei.com>

Looks good. Feel free to add:

Reviewed-by: Jan Kara <jack@suse.cz>

								Honza

> ---
>  fs/ext4/mballoc.c | 2 ++
>  1 file changed, 2 insertions(+)
> 
> diff --git a/fs/ext4/mballoc.c b/fs/ext4/mballoc.c
> index 9087183602e4..194a9f995c36 100644
> --- a/fs/ext4/mballoc.c
> +++ b/fs/ext4/mballoc.c
> @@ -768,6 +768,8 @@ static void __mb_check_buddy(struct ext4_buddy *e4b, char *file,
>  		ext4_group_t groupnr;
>  		struct ext4_prealloc_space *pa;
>  		pa = list_entry(cur, struct ext4_prealloc_space, pa_group_list);
> +		if (!pa->pa_len)
> +			continue;
>  		ext4_get_group_no_and_offset(sb, pa->pa_pstart, &groupnr, &k);
>  		MB_CHECK_ASSERT(groupnr == e4b->bd_group);
>  		for (i = 0; i < pa->pa_len; i++)
> -- 
> 2.39.2
> 
-- 
Jan Kara <jack@suse.com>
SUSE Labs, CR

Re: [PATCH 2/2] ext4: improve integrity checking in __mb_check_buddy by enhancing order-0 validation

[Jan Kara]

On Wed 05-11-25 15:42:50, Yongjian Sun wrote:
> From: Yongjian Sun <sunyongjian1@huawei.com>
> 
> When the MB_CHECK_ASSERT macro is enabled, we found that the
> current validation logic in __mb_check_buddy has a gap in
> detecting certain invalid buddy states, particularly related
> to order-0 (bitmap) bits.
> 
> The original logic consists of three steps:
> 1. Validates higher-order buddies: if a higher-order bit is
> set, at most one of the two corresponding lower-order bits
> may be free; if a higher-order bit is clear, both lower-order
> bits must be allocated (and their bitmap bits must be 0).
> 2. For any set bit in order-0, ensures all corresponding
> higher-order bits are not free.
> 3. Verifies that all preallocated blocks (pa) in the group
> have pa_pstart within bounds and their bitmap bits marked as
> allocated.
> 
> However, this approach fails to properly validate cases where
> order-0 bits are incorrectly cleared (0), allowing some invalid
> configurations to pass:
> 
>                corrupt            integral
> 
> order 3           1                  1
> order 2       1       1          1       1
> order 1     1   1   1   1      1   1   1   1
> order 0    0 0 1 1 1 1 1 1    1 1 1 1 1 1 1 1
> 
> Here we get two adjacent free blocks at order-0 with inconsistent
> higher-order state, and the right one shows the correct scenario.
> 
> The root cause is insufficient validation of order-0 zero bits.
> To fix this and improve completeness without significant performance
> cost, we refine the logic:
> 
> 1. Maintain the top-down higher-order validation, but we no longer
> check the cases where the higher-order bit is 0, as this case will
> be covered in step 2.
> 2. Enhance order-0 checking by examining pairs of bits:
>    - If either bit in a pair is set (1), all corresponding
>      higher-order bits must not be free.
>    - If both bits are clear (0), then exactly one of the
>      corresponding higher-order bits must be free
> 3. Keep the preallocation (pa) validation unchanged.
> 
> This change closes the validation gap, ensuring illegal buddy states
> involving order-0 are correctly detected, while removing redundant
> checks and maintaining efficiency.
> 
> Fixes: c9de560ded61f ("ext4: Add multi block allocator for ext4")
> Signed-off-by: Yongjian Sun <sunyongjian1@huawei.com>
> Reviewed-by: Baokun Li <libaokun1@huawei.com>

The idea looks good but I have one question regarding the implementation...

> @@ -747,15 +756,29 @@ static void __mb_check_buddy(struct ext4_buddy *e4b, char *file,
>  				fragments++;
>  				fstart = i;
>  			}
> -			continue;
> +		} else {
> +			fstart = -1;
>  		}
> -		fstart = -1;
> -		/* check used bits only */
> -		for (j = 0; j < e4b->bd_blkbits + 1; j++) {
> -			buddy2 = mb_find_buddy(e4b, j, &max2);
> -			k = i >> j;
> -			MB_CHECK_ASSERT(k < max2);
> -			MB_CHECK_ASSERT(mb_test_bit(k, buddy2));
> +		if (!(i & 1)) {
> +			int in_use, zero_bit_count;
> +
> +			in_use = mb_test_bit(i, buddy) || mb_test_bit(i + 1, buddy);
> +			zero_bit_count = 0;
> +			for (j = 1; j < e4b->bd_blkbits + 2; j++) {
> +				buddy2 = mb_find_buddy(e4b, j, &max2);
> +				k = i >> j;
> +				MB_CHECK_ASSERT(k < max2);
> +				if (in_use) {
> +					/* can not contain any 0 at all orders */
> +					MB_CHECK_ASSERT(mb_test_bit(k, buddy2));
> +				} else {
> +					/* there is and can only be one 0 at all orders */
> +					if (!mb_test_bit(k, buddy2)) {
> +						zero_bit_count++;
> +						MB_CHECK_ASSERT(zero_bit_count == 1);
> +					}
> +				}

Your variant doesn't seem to properly assert that at least 1 bit in the
buddy is 0 above 0 bit in the bitmap because the MB_CHECK_ASSERT() doesn't
get executed in that case at all AFAICT.  I think it would be more
understandable to have the loop like:

			for (j = 1; j < e4b->bd_blkbits + 2; j++) {
				buddy2 = mb_find_buddy(e4b, j, &max2);
				k = i >> j;
				MB_CHECK_ASSERT(k < max2);
				if (!mb_test_bit(k, buddy2))
					zero_bit_count++;
			}
			MB_CHECK_ASSERT(zero_bit_count == !in_use);

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

Re: [PATCH 2/2] ext4: improve integrity checking in __mb_check_buddy by enhancing order-0 validation

[Sun Yongjian]

在 2025/11/5 20:04, Jan Kara 写道:
> On Wed 05-11-25 15:42:50, Yongjian Sun wrote:
>> From: Yongjian Sun <sunyongjian1@huawei.com>
>>
>> When the MB_CHECK_ASSERT macro is enabled, we found that the
>> current validation logic in __mb_check_buddy has a gap in
>> detecting certain invalid buddy states, particularly related
>> to order-0 (bitmap) bits.
>>
>> The original logic consists of three steps:
>> 1. Validates higher-order buddies: if a higher-order bit is
>> set, at most one of the two corresponding lower-order bits
>> may be free; if a higher-order bit is clear, both lower-order
>> bits must be allocated (and their bitmap bits must be 0).
>> 2. For any set bit in order-0, ensures all corresponding
>> higher-order bits are not free.
>> 3. Verifies that all preallocated blocks (pa) in the group
>> have pa_pstart within bounds and their bitmap bits marked as
>> allocated.
>>
>> However, this approach fails to properly validate cases where
>> order-0 bits are incorrectly cleared (0), allowing some invalid
>> configurations to pass:
>>
>>                 corrupt            integral
>>
>> order 3           1                  1
>> order 2       1       1          1       1
>> order 1     1   1   1   1      1   1   1   1
>> order 0    0 0 1 1 1 1 1 1    1 1 1 1 1 1 1 1
>>
>> Here we get two adjacent free blocks at order-0 with inconsistent
>> higher-order state, and the right one shows the correct scenario.
>>
>> The root cause is insufficient validation of order-0 zero bits.
>> To fix this and improve completeness without significant performance
>> cost, we refine the logic:
>>
>> 1. Maintain the top-down higher-order validation, but we no longer
>> check the cases where the higher-order bit is 0, as this case will
>> be covered in step 2.
>> 2. Enhance order-0 checking by examining pairs of bits:
>>     - If either bit in a pair is set (1), all corresponding
>>       higher-order bits must not be free.
>>     - If both bits are clear (0), then exactly one of the
>>       corresponding higher-order bits must be free
>> 3. Keep the preallocation (pa) validation unchanged.
>>
>> This change closes the validation gap, ensuring illegal buddy states
>> involving order-0 are correctly detected, while removing redundant
>> checks and maintaining efficiency.
>>
>> Fixes: c9de560ded61f ("ext4: Add multi block allocator for ext4")
>> Signed-off-by: Yongjian Sun <sunyongjian1@huawei.com>
>> Reviewed-by: Baokun Li <libaokun1@huawei.com>
> 
> The idea looks good but I have one question regarding the implementation...
> 
>> @@ -747,15 +756,29 @@ static void __mb_check_buddy(struct ext4_buddy *e4b, char *file,
>>   				fragments++;
>>   				fstart = i;
>>   			}
>> -			continue;
>> +		} else {
>> +			fstart = -1;
>>   		}
>> -		fstart = -1;
>> -		/* check used bits only */
>> -		for (j = 0; j < e4b->bd_blkbits + 1; j++) {
>> -			buddy2 = mb_find_buddy(e4b, j, &max2);
>> -			k = i >> j;
>> -			MB_CHECK_ASSERT(k < max2);
>> -			MB_CHECK_ASSERT(mb_test_bit(k, buddy2));
>> +		if (!(i & 1)) {
>> +			int in_use, zero_bit_count;
>> +
>> +			in_use = mb_test_bit(i, buddy) || mb_test_bit(i + 1, buddy);
>> +			zero_bit_count = 0;
>> +			for (j = 1; j < e4b->bd_blkbits + 2; j++) {
>> +				buddy2 = mb_find_buddy(e4b, j, &max2);
>> +				k = i >> j;
>> +				MB_CHECK_ASSERT(k < max2);
>> +				if (in_use) {
>> +					/* can not contain any 0 at all orders */
>> +					MB_CHECK_ASSERT(mb_test_bit(k, buddy2));
>> +				} else {
>> +					/* there is and can only be one 0 at all orders */
>> +					if (!mb_test_bit(k, buddy2)) {
>> +						zero_bit_count++;
>> +						MB_CHECK_ASSERT(zero_bit_count == 1);
>> +					}
>> +				}
> 
> Your variant doesn't seem to properly assert that at least 1 bit in the
> buddy is 0 above 0 bit in the bitmap because the MB_CHECK_ASSERT() doesn't
> get executed in that case at all AFAICT.  I think it would be more
> understandable to have the loop like:
> 
> 			for (j = 1; j < e4b->bd_blkbits + 2; j++) {
> 				buddy2 = mb_find_buddy(e4b, j, &max2);
> 				k = i >> j;
> 				MB_CHECK_ASSERT(k < max2);
> 				if (!mb_test_bit(k, buddy2))
> 					zero_bit_count++;
> 			}
> 			MB_CHECK_ASSERT(zero_bit_count == !in_use);
> 
> 									Honza

Thanks a lot for pointing out the logical flaw! Yes, you’re right—if 
order-0 bit pair is clear, then without a single 0 showing up at any 
higher order we’ll never enter the `if` branch to run `MB_CHECK_ASSERT`. 
The code you proposed is indeed a better, more elegant implementation!

Thanks,
Yongjian