[PATCH v6 0/2] Improve the performance of bitmap_find_next_zero_area_off()

[PATCH v6 0/2] Improve the performance of bitmap_find_next_zero_area_off()

[Yi Sun]

Use lib/find_bit_benchmark.c for testing.
Test results showed a 40% improvement in dense cases,
and almost no change in sparse cases.

Performance test results on my hardware:
	before(ns)	after(ns)	change	p-value
dense	1211		688		-43.2%	8.3e-11
sparse	13.3		13.4		0.8%	0.27

---
v5: https://lore.kernel.org/all/20260618015252.3601554-1-yi.sun@unisoc.com
- Improve test code.
- Change the "goto again" code structure to a for loop.

v4: https://lore.kernel.org/all/20260601094234.103863-1-yi.sun@unisoc.com
- Test code has been added to PATCH v2.

v3: https://lore.kernel.org/all/20260514090607.231387-1-yi.sun@unisoc.com
- Code optimization was performed on PATCH v1.

v2: https://lore.kernel.org/all/20260514035644.4118050-1-yi.sun@unisoc.com
- Do not introduce find_last_bit_from().

v1: https://lore.kernel.org/all/20260512040659.2992142-1-yi.sun@unisoc.com


Yi Sun (2):
  lib: bitmap: add tests for bitmap_find_next_zero_area_off()
  lib: bitmap: optimize bitmap_find_next_zero_area_off()

 lib/bitmap.c             | 31 ++++++++++++++++---------------
 lib/find_bit_benchmark.c | 31 ++++++++++++++++++++++++-------
 lib/test_bitmap.c        | 38 ++++++++++++++++++++++++++++++++++++++
 3 files changed, 78 insertions(+), 22 deletions(-)

-- 
2.34.1

[PATCH v6 1/2] lib: bitmap: add tests for bitmap_find_next_zero_area_off()

[Yi Sun]

Add functional and performance tests
for bitmap_find_next_zero_area_off().

performance tests partial output:
Start testing find_bit() with random-filled bitmap
[    0.310073] bitmap_find_next_zero_area_off:         852731 ns,   1154 iterations
[    0.311435] find_next_bit:                         1356654 ns, 163975 iterations
Start testing find_bit() with sparse bitmap
[    0.316267] bitmap_find_next_zero_area_off:        4426808 ns, 322479 iterations
[    0.316292] find_next_bit:                           15154 ns,    656 iterations

Signed-off-by: Yi Sun <yi.sun@unisoc.com>
---
 lib/find_bit_benchmark.c | 31 ++++++++++++++++++++++++-------
 lib/test_bitmap.c        | 38 ++++++++++++++++++++++++++++++++++++++
 2 files changed, 62 insertions(+), 7 deletions(-)

diff --git a/lib/find_bit_benchmark.c b/lib/find_bit_benchmark.c
index 00d9dc61cd46..cde7c09de05c 100644
--- a/lib/find_bit_benchmark.c
+++ b/lib/find_bit_benchmark.c
@@ -46,7 +46,7 @@ static int __init test_find_first_bit(const void *bitmap, unsigned long len)
 		__clear_bit(i, cp);
 	}
 	time = ktime_get() - time;
-	pr_err("find_first_bit:     %18llu ns, %6ld iterations\n", time, cnt);
+	pr_err("find_first_bit:                 %14llu ns, %6ld iterations\n", time, cnt);
 
 	return 0;
 }
@@ -66,7 +66,7 @@ static int __init test_find_first_and_bit(const void *bitmap, const void *bitmap
 		__clear_bit(i, cp);
 	}
 	time = ktime_get() - time;
-	pr_err("find_first_and_bit: %18llu ns, %6ld iterations\n", time, cnt);
+	pr_err("find_first_and_bit:             %14llu ns, %6ld iterations\n", time, cnt);
 
 	return 0;
 }
@@ -80,7 +80,7 @@ static int __init test_find_next_bit(const void *bitmap, unsigned long len)
 	for (cnt = i = 0; i < BITMAP_LEN; cnt++)
 		i = find_next_bit(bitmap, BITMAP_LEN, i) + 1;
 	time = ktime_get() - time;
-	pr_err("find_next_bit:      %18llu ns, %6ld iterations\n", time, cnt);
+	pr_err("find_next_bit:                  %14llu ns, %6ld iterations\n", time, cnt);
 
 	return 0;
 }
@@ -94,7 +94,7 @@ static int __init test_find_next_zero_bit(const void *bitmap, unsigned long len)
 	for (cnt = i = 0; i < BITMAP_LEN; cnt++)
 		i = find_next_zero_bit(bitmap, len, i) + 1;
 	time = ktime_get() - time;
-	pr_err("find_next_zero_bit: %18llu ns, %6ld iterations\n", time, cnt);
+	pr_err("find_next_zero_bit:             %14llu ns, %6ld iterations\n", time, cnt);
 
 	return 0;
 }
@@ -113,7 +113,7 @@ static int __init test_find_last_bit(const void *bitmap, unsigned long len)
 		len = l;
 	} while (len);
 	time = ktime_get() - time;
-	pr_err("find_last_bit:      %18llu ns, %6ld iterations\n", time, cnt);
+	pr_err("find_last_bit:                  %14llu ns, %6ld iterations\n", time, cnt);
 
 	return 0;
 }
@@ -129,7 +129,7 @@ static int __init test_find_nth_bit(const unsigned long *bitmap, unsigned long l
 		WARN_ON(l >= len);
 	}
 	time = ktime_get() - time;
-	pr_err("find_nth_bit:       %18llu ns, %6ld iterations\n", time, w);
+	pr_err("find_nth_bit:                   %14llu ns, %6ld iterations\n", time, w);
 
 	return 0;
 }
@@ -144,7 +144,22 @@ static int __init test_find_next_and_bit(const void *bitmap,
 	for (cnt = i = 0; i < BITMAP_LEN; cnt++)
 		i = find_next_and_bit(bitmap, bitmap2, BITMAP_LEN, i + 1);
 	time = ktime_get() - time;
-	pr_err("find_next_and_bit:  %18llu ns, %6ld iterations\n", time, cnt);
+	pr_err("find_next_and_bit:              %14llu ns, %6ld iterations\n", time, cnt);
+
+	return 0;
+}
+
+static int __init
+test_bitmap_find_next_zero_area_off(unsigned long *bitmap, unsigned long len)
+{
+	unsigned long i, cnt;
+	ktime_t time;
+
+	time = ktime_get();
+	for (cnt = i = 0; i < BITMAP_LEN; cnt++)
+		i = bitmap_find_next_zero_area_off(bitmap, BITMAP_LEN, i, 8, 0, 0) + 1;
+	time = ktime_get() - time;
+	pr_err("bitmap_find_next_zero_area_off: %14llu ns, %6ld iterations\n", time, cnt);
 
 	return 0;
 }
@@ -158,6 +173,7 @@ static int __init find_bit_test(void)
 	get_random_bytes(bitmap, sizeof(bitmap));
 	get_random_bytes(bitmap2, sizeof(bitmap2));
 
+	test_bitmap_find_next_zero_area_off(bitmap, BITMAP_LEN);
 	test_find_next_bit(bitmap, BITMAP_LEN);
 	test_find_next_zero_bit(bitmap, BITMAP_LEN);
 	test_find_last_bit(bitmap, BITMAP_LEN);
@@ -181,6 +197,7 @@ static int __init find_bit_test(void)
 		__set_bit(get_random_u32_below(BITMAP_LEN), bitmap2);
 	}
 
+	test_bitmap_find_next_zero_area_off(bitmap, BITMAP_LEN);
 	test_find_next_bit(bitmap, BITMAP_LEN);
 	test_find_next_zero_bit(bitmap, BITMAP_LEN);
 	test_find_last_bit(bitmap, BITMAP_LEN);
diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c
index 69813c10e6c0..8665df77c960 100644
--- a/lib/test_bitmap.c
+++ b/lib/test_bitmap.c
@@ -234,6 +234,43 @@ static void __init test_find_nth_bit(void)
 	}
 }
 
+static void __init
+test_bitmap_find_next_zero_area_off(void)
+{
+	DECLARE_BITMAP(bmap, 192);
+
+	bitmap_set(bmap, 0, 192);
+
+	bitmap_clear(bmap, 0, 8);
+	__clear_bit(50, bmap);
+	bitmap_clear(bmap, 60, 18);
+	__set_bit(69, bmap);
+	__clear_bit(80, bmap);
+	bitmap_clear(bmap, 100, 10);
+	__clear_bit(120, bmap);
+	bitmap_clear(bmap, 145, 8);
+	bitmap_clear(bmap, 160, 32);
+
+	expect_eq_uint(0,
+		bitmap_find_next_zero_area_off(bmap, 192, 0, 8, 0, 0));
+	expect_eq_uint(0,
+		bitmap_find_next_zero_area_off(bmap, 192, 0, 8, 3, 0));
+	expect_eq_uint(163,
+		bitmap_find_next_zero_area_off(bmap, 192, 0, 8, 3, 1));
+	expect_eq_uint(60,
+		bitmap_find_next_zero_area_off(bmap, 192, 1, 8, 0, 0));
+	expect_eq_uint(160,
+		bitmap_find_next_zero_area_off(bmap, 192, 1, 8, 7, 0));
+	expect_eq_uint(60,
+		bitmap_find_next_zero_area_off(bmap, 192, 1, 8, 7, 4));
+	expect_eq_uint(100,
+		bitmap_find_next_zero_area_off(bmap, 192, 0, 10, 0, 0));
+	expect_eq_uint(160,
+		bitmap_find_next_zero_area_off(bmap, 192, 0, 32, 0, 0));
+	expect_eq_uint(1,
+		!!(bitmap_find_next_zero_area_off(bmap, 192, 0, 33, 0, 0) >= 192));
+}
+
 static void __init test_fill_set(void)
 {
 	DECLARE_BITMAP(bmap, 1024);
@@ -1559,6 +1596,7 @@ static void __init selftest(void)
 	test_for_each_clear_bitrange_from();
 	test_for_each_set_clump8();
 	test_for_each_set_bit_wrap();
+	test_bitmap_find_next_zero_area_off();
 }
 
 KSTM_MODULE_LOADERS(test_bitmap);
-- 
2.34.1

[PATCH v6 2/2] lib: bitmap: optimize bitmap_find_next_zero_area_off()

[Yi Sun]

Finding a contiguous free region in a highly fragmented
bitmap is not easy and may require many repeated attempts.
Therefore, find_next_bit(map, end, index) is not the optimal choice.
This is because there may be multiple scattered free regions
within the range [index, end) and none of them will meet the length
requirement of @nr.
Instead, it's sufficient to directly find the last bit within
the range [index, end), thus reducing unnecessary repeated calls.

An example of a bitmap:
Bits 0-3:   cleared(4 bits)
Bits 4-5:   set    (2 bits)
Bits 6-8:   cleared(4 bits)
Bits 9-10:  set    (2 bits)
Bits 11-20: cleared(10 bits)

The goal is to find a 10-bit free region.

The old code logic is as follows:
find_next_zero_bit(start = 0, find bit 0) -> find_next_bit(find bit 4) ->
next loop ->
find_next_zero_bit(start = 5, find bit 6) -> find_next_bit(find bit 9) ->
next loop ->
find_next_zero_bit(start = 10, find bit 11) -> success

The new code logic is as follows:
find_next_zero_bit(start = 0, find bit 0) -> find_last_bit(find bit 9) ->
next loop ->
find_next_zero_bit(start = 10, find bit 11) -> success

Performance test results on my hardware(use lib/find_bit_benchmark.c):

		before	after	change	p-value
dense		1211	688	-43.2%	8.3e-11
sparse		13.3	13.4	0.8%	0.27

Co-developed-by: Yury Norov <yury.norov@gmail.com>
Signed-off-by: Yury Norov <yury.norov@gmail.com>
Signed-off-by: Yi Sun <yi.sun@unisoc.com>
---
 lib/bitmap.c | 31 ++++++++++++++++---------------
 1 file changed, 16 insertions(+), 15 deletions(-)

diff --git a/lib/bitmap.c b/lib/bitmap.c
index b9bfa157e095..a00a71f2b7bb 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -432,22 +432,23 @@ unsigned long bitmap_find_next_zero_area_off(unsigned long *map,
 					     unsigned long align_mask,
 					     unsigned long align_offset)
 {
-	unsigned long index, end, i;
-again:
-	index = find_next_zero_bit(map, size, start);
-
-	/* Align allocation */
-	index = __ALIGN_MASK(index + align_offset, align_mask) - align_offset;
-
-	end = index + nr;
-	if (end > size)
-		return end;
-	i = find_next_bit(map, end, index);
-	if (i < end) {
-		start = i + 1;
-		goto again;
+	unsigned long end, i, off;
+
+	for_each_clear_bit_from(start, map, size) {
+		start = __ALIGN_MASK(start + align_offset, align_mask) - align_offset;
+		end = start + nr;
+		if (end > size)
+			break;
+
+		off = round_down(start, BITS_PER_LONG);
+		i = find_last_bit(map + start / BITS_PER_LONG, end - off) + off;
+		if (i >= end || i < start)
+			return start;
+
+		start = i;
 	}
-	return index;
+
+	return size;
 }
 EXPORT_SYMBOL(bitmap_find_next_zero_area_off);
 
-- 
2.34.1

Re: [PATCH v6 1/2] lib: bitmap: add tests for bitmap_find_next_zero_area_off()

[Yury Norov]

On Thu, Jun 18, 2026 at 09:35:17PM +0800, Yi Sun wrote:
> Add functional and performance tests
> for bitmap_find_next_zero_area_off().
> 
> performance tests partial output:
> Start testing find_bit() with random-filled bitmap
> [    0.310073] bitmap_find_next_zero_area_off:         852731 ns,   1154 iterations
> [    0.311435] find_next_bit:                         1356654 ns, 163975 iterations
> Start testing find_bit() with sparse bitmap
> [    0.316267] bitmap_find_next_zero_area_off:        4426808 ns, 322479 iterations
> [    0.316292] find_next_bit:                           15154 ns,    656 iterations
> 
> Signed-off-by: Yi Sun <yi.sun@unisoc.com>
> ---
>  lib/find_bit_benchmark.c | 31 ++++++++++++++++++++++++-------
>  lib/test_bitmap.c        | 38 ++++++++++++++++++++++++++++++++++++++
>  2 files changed, 62 insertions(+), 7 deletions(-)
> 
> diff --git a/lib/find_bit_benchmark.c b/lib/find_bit_benchmark.c
> index 00d9dc61cd46..cde7c09de05c 100644
> --- a/lib/find_bit_benchmark.c
> +++ b/lib/find_bit_benchmark.c
> @@ -46,7 +46,7 @@ static int __init test_find_first_bit(const void *bitmap, unsigned long len)
>  		__clear_bit(i, cp);
>  	}
>  	time = ktime_get() - time;
> -	pr_err("find_first_bit:     %18llu ns, %6ld iterations\n", time, cnt);
> +	pr_err("find_first_bit:                 %14llu ns, %6ld iterations\n", time, cnt);

No need to change the existing code. Just add your test and make sure
it looks aligned with the existing format.

>  
>  	return 0;
>  }
> @@ -66,7 +66,7 @@ static int __init test_find_first_and_bit(const void *bitmap, const void *bitmap
>  		__clear_bit(i, cp);
>  	}
>  	time = ktime_get() - time;
> -	pr_err("find_first_and_bit: %18llu ns, %6ld iterations\n", time, cnt);
> +	pr_err("find_first_and_bit:             %14llu ns, %6ld iterations\n", time, cnt);
>  
>  	return 0;
>  }
> @@ -80,7 +80,7 @@ static int __init test_find_next_bit(const void *bitmap, unsigned long len)
>  	for (cnt = i = 0; i < BITMAP_LEN; cnt++)
>  		i = find_next_bit(bitmap, BITMAP_LEN, i) + 1;
>  	time = ktime_get() - time;
> -	pr_err("find_next_bit:      %18llu ns, %6ld iterations\n", time, cnt);
> +	pr_err("find_next_bit:                  %14llu ns, %6ld iterations\n", time, cnt);
>  
>  	return 0;
>  }
> @@ -94,7 +94,7 @@ static int __init test_find_next_zero_bit(const void *bitmap, unsigned long len)
>  	for (cnt = i = 0; i < BITMAP_LEN; cnt++)
>  		i = find_next_zero_bit(bitmap, len, i) + 1;
>  	time = ktime_get() - time;
> -	pr_err("find_next_zero_bit: %18llu ns, %6ld iterations\n", time, cnt);
> +	pr_err("find_next_zero_bit:             %14llu ns, %6ld iterations\n", time, cnt);
>  
>  	return 0;
>  }
> @@ -113,7 +113,7 @@ static int __init test_find_last_bit(const void *bitmap, unsigned long len)
>  		len = l;
>  	} while (len);
>  	time = ktime_get() - time;
> -	pr_err("find_last_bit:      %18llu ns, %6ld iterations\n", time, cnt);
> +	pr_err("find_last_bit:                  %14llu ns, %6ld iterations\n", time, cnt);
>  
>  	return 0;
>  }
> @@ -129,7 +129,7 @@ static int __init test_find_nth_bit(const unsigned long *bitmap, unsigned long l
>  		WARN_ON(l >= len);
>  	}
>  	time = ktime_get() - time;
> -	pr_err("find_nth_bit:       %18llu ns, %6ld iterations\n", time, w);
> +	pr_err("find_nth_bit:                   %14llu ns, %6ld iterations\n", time, w);
>  
>  	return 0;
>  }
> @@ -144,7 +144,22 @@ static int __init test_find_next_and_bit(const void *bitmap,
>  	for (cnt = i = 0; i < BITMAP_LEN; cnt++)
>  		i = find_next_and_bit(bitmap, bitmap2, BITMAP_LEN, i + 1);
>  	time = ktime_get() - time;
> -	pr_err("find_next_and_bit:  %18llu ns, %6ld iterations\n", time, cnt);
> +	pr_err("find_next_and_bit:              %14llu ns, %6ld iterations\n", time, cnt);
> +
> +	return 0;
> +}
> +
> +static int __init
> +test_bitmap_find_next_zero_area_off(unsigned long *bitmap, unsigned long len)
> +{
> +	unsigned long i, cnt;
> +	ktime_t time;
> +
> +	time = ktime_get();
> +	for (cnt = i = 0; i < BITMAP_LEN; cnt++)
> +		i = bitmap_find_next_zero_area_off(bitmap, BITMAP_LEN, i, 8, 0, 0) + 1;
> +	time = ktime_get() - time;
> +	pr_err("bitmap_find_next_zero_area_off: %14llu ns, %6ld iterations\n", time, cnt);
>  
>  	return 0;
>  }
> @@ -158,6 +173,7 @@ static int __init find_bit_test(void)
>  	get_random_bytes(bitmap, sizeof(bitmap));
>  	get_random_bytes(bitmap2, sizeof(bitmap2));
>  
> +	test_bitmap_find_next_zero_area_off(bitmap, BITMAP_LEN);
>  	test_find_next_bit(bitmap, BITMAP_LEN);
>  	test_find_next_zero_bit(bitmap, BITMAP_LEN);
>  	test_find_last_bit(bitmap, BITMAP_LEN);
> @@ -181,6 +197,7 @@ static int __init find_bit_test(void)
>  		__set_bit(get_random_u32_below(BITMAP_LEN), bitmap2);
>  	}
>  
> +	test_bitmap_find_next_zero_area_off(bitmap, BITMAP_LEN);
>  	test_find_next_bit(bitmap, BITMAP_LEN);
>  	test_find_next_zero_bit(bitmap, BITMAP_LEN);
>  	test_find_last_bit(bitmap, BITMAP_LEN);
> diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c
> index 69813c10e6c0..8665df77c960 100644
> --- a/lib/test_bitmap.c
> +++ b/lib/test_bitmap.c
> @@ -234,6 +234,43 @@ static void __init test_find_nth_bit(void)
>  	}
>  }
>  
> +static void __init
> +test_bitmap_find_next_zero_area_off(void)
> +{
> +	DECLARE_BITMAP(bmap, 192);
> +
> +	bitmap_set(bmap, 0, 192);
> +
> +	bitmap_clear(bmap, 0, 8);
> +	__clear_bit(50, bmap);
> +	bitmap_clear(bmap, 60, 18);
> +	__set_bit(69, bmap);
> +	__clear_bit(80, bmap);
> +	bitmap_clear(bmap, 100, 10);
> +	__clear_bit(120, bmap);
> +	bitmap_clear(bmap, 145, 8);
> +	bitmap_clear(bmap, 160, 32);
> +
> +	expect_eq_uint(0,
> +		bitmap_find_next_zero_area_off(bmap, 192, 0, 8, 0, 0));
> +	expect_eq_uint(0,
> +		bitmap_find_next_zero_area_off(bmap, 192, 0, 8, 3, 0));
> +	expect_eq_uint(163,
> +		bitmap_find_next_zero_area_off(bmap, 192, 0, 8, 3, 1));
> +	expect_eq_uint(60,
> +		bitmap_find_next_zero_area_off(bmap, 192, 1, 8, 0, 0));
> +	expect_eq_uint(160,
> +		bitmap_find_next_zero_area_off(bmap, 192, 1, 8, 7, 0));
> +	expect_eq_uint(60,
> +		bitmap_find_next_zero_area_off(bmap, 192, 1, 8, 7, 4));
> +	expect_eq_uint(100,
> +		bitmap_find_next_zero_area_off(bmap, 192, 0, 10, 0, 0));
> +	expect_eq_uint(160,
> +		bitmap_find_next_zero_area_off(bmap, 192, 0, 32, 0, 0));
> +	expect_eq_uint(1,
> +		!!(bitmap_find_next_zero_area_off(bmap, 192, 0, 33, 0, 0) >= 192));
> +}
> +
>  static void __init test_fill_set(void)
>  {
>  	DECLARE_BITMAP(bmap, 1024);
> @@ -1559,6 +1596,7 @@ static void __init selftest(void)
>  	test_for_each_clear_bitrange_from();
>  	test_for_each_set_clump8();
>  	test_for_each_set_bit_wrap();
> +	test_bitmap_find_next_zero_area_off();
>  }
>  
>  KSTM_MODULE_LOADERS(test_bitmap);
> -- 
> 2.34.1