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

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

[Yongjian Sun]

From: Yongjian Sun <sunyongjian1@huawei.com>

Link to v1:
 - https://lore.kernel.org/all/20251105074250.3517687-1-sunyongjian@huaweicloud.com/

Changes in v2:
 - Patch 2/2: the logical error in the order-0 check code has been corrected.

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 | 51 +++++++++++++++++++++++++++++++----------------
 1 file changed, 34 insertions(+), 17 deletions(-)

-- 
2.39.2

[PATCH v2 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>
Reviewed-by: Jan Kara <jack@suse.cz>
---
 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 v2 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")
Suggested-by: Jan Kara <jack@suse.cz>
Signed-off-by: Yongjian Sun <sunyongjian1@huawei.com>
Reviewed-by: Baokun Li <libaokun1@huawei.com>
---
 fs/ext4/mballoc.c | 49 +++++++++++++++++++++++++++++++----------------
 1 file changed, 32 insertions(+), 17 deletions(-)

diff --git a/fs/ext4/mballoc.c b/fs/ext4/mballoc.c
index 194a9f995c36..65335248825c 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,21 @@ 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 = 0;
+
+			in_use = mb_test_bit(i, buddy) || mb_test_bit(i + 1, buddy);
+			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);
 		}
 	}
 	MB_CHECK_ASSERT(!EXT4_MB_GRP_NEED_INIT(e4b->bd_info));
-- 
2.39.2

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

[Jan Kara]

On Thu 06-11-25 14:06:14, 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")
> Suggested-by: Jan Kara <jack@suse.cz>
> 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 | 49 +++++++++++++++++++++++++++++++----------------
>  1 file changed, 32 insertions(+), 17 deletions(-)
> 
> diff --git a/fs/ext4/mballoc.c b/fs/ext4/mballoc.c
> index 194a9f995c36..65335248825c 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,21 @@ 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 = 0;
> +
> +			in_use = mb_test_bit(i, buddy) || mb_test_bit(i + 1, buddy);
> +			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);
>  		}
>  	}
>  	MB_CHECK_ASSERT(!EXT4_MB_GRP_NEED_INIT(e4b->bd_info));
> -- 
> 2.39.2
> 
-- 
Jan Kara <jack@suse.com>
SUSE Labs, CR

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

[Theodore Ts'o]

On Thu, 06 Nov 2025 14:06:12 +0800, Yongjian Sun wrote:
> Link to v1:
>  - https://lore.kernel.org/all/20251105074250.3517687-1-sunyongjian@huaweicloud.com/
> 
> Changes in v2:
>  - Patch 2/2: the logical error in the order-0 check code has been corrected.
> 
> 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
> 
> [...]

Applied, thanks!

[1/2] ext4: fix incorrect group number assertion in mb_check_buddy for exhausted preallocations
      commit: 3f7a79d05c692c7cfec70bf104b1b3c3d0ce6247
[2/2] ext4: improve integrity checking in __mb_check_buddy by enhancing order-0 validation
      commit: d9ee3ff810f1cc0e253c9f2b17b668b973cb0e06

Best regards,
-- 
Theodore Ts'o <tytso@mit.edu>