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

[PATCH v7 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

Version 7 only changed the alignment format of the test code.

---
v6: https://lore.kernel.org/all/20260618133518.4079981-1-yi.sun@unisoc.com
- Improve test code.
- Change infinite for loop to for_each_clear_bit_from.

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 | 17 +++++++++++++++++
 lib/test_bitmap.c        | 38 ++++++++++++++++++++++++++++++++++++++
 3 files changed, 71 insertions(+), 15 deletions(-)

-- 
2.34.1

[PATCH v7 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 | 17 +++++++++++++++++
 lib/test_bitmap.c        | 38 ++++++++++++++++++++++++++++++++++++++
 2 files changed, 55 insertions(+)

diff --git a/lib/find_bit_benchmark.c b/lib/find_bit_benchmark.c
index 00d9dc61cd46..05305e655f99 100644
--- a/lib/find_bit_benchmark.c
+++ b/lib/find_bit_benchmark.c
@@ -149,6 +149,21 @@ static int __init test_find_next_and_bit(const void *bitmap,
 	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:%7llu ns, %6ld iterations\n", time, cnt);
+
+	return 0;
+}
+
 static int __init find_bit_test(void)
 {
 	unsigned long nbits = BITMAP_LEN / SPARSE;
@@ -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

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

[Michał Nazarewicz]

On Mon, Jun 22 2026, 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>

Acked-by: Michał Nazarewicz <mina86@mina86.com>

> ---
>  lib/find_bit_benchmark.c | 17 +++++++++++++++++
>  lib/test_bitmap.c        | 38 ++++++++++++++++++++++++++++++++++++++
>  2 files changed, 55 insertions(+)
>
> diff --git a/lib/find_bit_benchmark.c b/lib/find_bit_benchmark.c
> index 00d9dc61cd46..05305e655f99 100644
> --- a/lib/find_bit_benchmark.c
> +++ b/lib/find_bit_benchmark.c
> @@ -149,6 +149,21 @@ static int __init test_find_next_and_bit(const void *bitmap,
>  	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:%7llu ns, %6ld iterations\n", time, cnt);
> +
> +	return 0;
> +}
> +
>  static int __init find_bit_test(void)
>  {
>  	unsigned long nbits = BITMAP_LEN / SPARSE;
> @@ -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));

In C `x >= y` yields 0 or 1.  There’s no need for `!!`.

About `>` vs `>=`, the original code returns `> 192` (because it returns
`end` when it exceeds `size`).  The new code returns `192` (because it
returns `size` if loop fails to find an area).  If that’s the case, this
patch, PATCH 1/2, should have `>` and PATCH 2/2 should change it to
`expect_eq_uint(192, …)` to reflect change in the API.
 
> +}
> +
>  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);

-- 
Best regards
ミハウ “𝓶𝓲𝓷𝓪86” ナザレヴィツ
«If at first you don’t succeed, give up skydiving»

答复: [PATCH v7 1/2] lib: bitmap: add tests for bitmap_find_next_zero_area_off()

[孙毅 (Yi Sun)]

> -----邮件原件-----
> 发件人: Michał Nazarewicz <mnazarewicz@gmail.com> 代表 Micha?
> Nazarewicz
> 发送时间: 2026年6月22日 18:06
> 收件人: 孙毅 (Yi Sun) <Yi.Sun@unisoc.com>; yury.norov@gmail.com
> 抄送: 孙毅 (Yi Sun) <Yi.Sun@unisoc.com>; 279644543@qq.com; akpm@linux-
> foundation.org; akinobu.mita@gmail.com; linux-kernel@vger.kernel.org;
> tjmercier@google.com; fvdl@google.com; tglx@kernel.org; song@kernel.org;
> hch@lst.de; minchan@kernel.org; jstultz@google.com
> 主题: Re: [PATCH v7 1/2] lib: bitmap: add tests for
> bitmap_find_next_zero_area_off()
> 
> 
> 注意: 这封邮件来自于外部。除非你确定邮件内容安全，否则不要点击任何链
> 接和附件。
> CAUTION: This email originated from outside of the organization. Do not click links
> or open attachments unless you recognize the sender and know the content is
> safe.
> 
> 
> 
> On Mon, Jun 22 2026, 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>
> 
> Acked-by: Michał Nazarewicz <mina86@mina86.com>
> 
> > ---
> >  lib/find_bit_benchmark.c | 17 +++++++++++++++++
> >  lib/test_bitmap.c        | 38 ++++++++++++++++++++++++++++++++++++++
> >  2 files changed, 55 insertions(+)
> >
> > diff --git a/lib/find_bit_benchmark.c b/lib/find_bit_benchmark.c
> > index 00d9dc61cd46..05305e655f99 100644
> > --- a/lib/find_bit_benchmark.c
> > +++ b/lib/find_bit_benchmark.c
> > @@ -149,6 +149,21 @@ static int __init test_find_next_and_bit(const void
> *bitmap,
> >       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:%7llu ns, %6ld iterations\n", time,
> cnt);
> > +
> > +     return 0;
> > +}
> > +
> >  static int __init find_bit_test(void)
> >  {
> >       unsigned long nbits = BITMAP_LEN / SPARSE;
> > @@ -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));
> 
> In C `x >= y` yields 0 or 1.  There’s no need for `!!`.
> 
> About `>` vs `>=`, the original code returns `> 192` (because it returns
> `end` when it exceeds `size`).  The new code returns `192` (because it
> returns `size` if loop fails to find an area).  If that’s the case, this
> patch, PATCH 1/2, should have `>` and PATCH 2/2 should change it to
> `expect_eq_uint(192, …)` to reflect change in the API.
> 

Very helpful feedback.
I will make changes in v8.

> > +}
> > +
> >  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);
> 
> --
> Best regards
> ミハウ “𝓶𝓲𝓷𝓪86” ナザレヴィツ
> «If at first you don’t succeed, give up skydiving»

[PATCH v7 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 v7 2/2] lib: bitmap: optimize bitmap_find_next_zero_area_off()

[Michał Nazarewicz]

On Mon, Jun 22 2026, Yi Sun wrote:
> 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.
[…]
> 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>

Acked-by: Michał Nazarewicz <mina86@mina86.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 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;

Gotta be honest, I’m not a fan of `for_each_clear_bit_from` the way it’s
used here.  It hides the `start++` that happens at end of each loop.
The code works either way, but I find the current form harder to read
than an infinite loop.

Having said that, Yury is the maintainer here so if he prefers that, I’m
obviously not gonna fight it.

>  	}
> -	return index;
> +
> +	return size;
>  }
>  EXPORT_SYMBOL(bitmap_find_next_zero_area_off);

-- 
Best regards
ミハウ “𝓶𝓲𝓷𝓪86” ナザレヴィツ
«If at first you don’t succeed, give up skydiving»

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

[Nathan Chancellor]

Hi,

On Mon, Jun 22, 2026 at 11:00:36AM +0800, Yi Sun wrote:
> 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>

I bisected a warning I see when virtually boot testing powerpc to this
change in -next as commit 6eecaf5cf2dd ("lib: bitmap: optimize
bitmap_find_next_zero_area_off()").

  $ make -skj"$(nproc)" ARCH=powerpc CROSS_COMPILE=powerpc64-linux- mrproper ppc64le_guest_defconfig zImage.epapr

  $ curl -LSs https://github.com/ClangBuiltLinux/boot-utils/releases/download/20241120-044434/ppc64le-rootfs.cpio.zst | zstd -d >rootfs.cpio

  $ qemu-system-ppc64 \
      -display none \
      -nodefaults \
      -device ipmi-bmc-sim,id=bmc0 \
      -device isa-ipmi-bt,bmc=bmc0,irq=10 \
      -machine powernv \
      -kernel arch/powerpc/boot/zImage.epapr \
      -initrd rootfs.cpio \
      -m 2G \
      -serial mon:stdio
  ...
  [    0.660986][    T1] Running code patching self-tests ...
  [    0.667347][    T1] ------------[ cut here ]------------
  [    0.667519][    T1] WARNING: arch/powerpc/sysdev/msi_bitmap.c:181 at msi_bitmap_selftest+0x1c8/0x3f8, CPU#0: swapper/0/1
  [    0.667964][    T1] Modules linked in:
  [    0.668237][    T1] CPU: 0 UID: 0 PID: 1 Comm: swapper/0 Not tainted 7.2.0-rc1-next-20260630 #1 PREEMPTLAZY
  [    0.668462][    T1] Hardware name: IBM PowerNV (emulated by qemu) POWER10 0x801200 opal:v7.1-106-g785a5e307 PowerNV
  [    0.668681][    T1] NIP:  c00000000201eb70 LR: c00000000201eb68 CTR: 0000000000000000
  [    0.668809][    T1] REGS: c0000000037d78b0 TRAP: 0700   Not tainted  (7.2.0-rc1-next-20260630)
  [    0.668956][    T1] MSR:  9000000000029033 <SF,HV,EE,ME,IR,DR,RI,LE>  CR: 24000224  XER: 20040000
  [    0.669190][    T1] CFAR: c000000000181880 IRQMASK: 0
  [    0.669190][    T1] GPR00: c00000000201eb68 c0000000037d7b70 c000000001c78100 0000000000000001
  [    0.669190][    T1] GPR04: 0000000000000000 0000000000000001 0000000000000001 0000000000000000
  [    0.669190][    T1] GPR08: 0000000000000000 0000000000000000 c000000003764f80 c000000000181d08
  [    0.669190][    T1] GPR12: 0000000000000000 c000000002c10000 c0000000000114d8 0000000000000000
  [    0.669190][    T1] GPR16: 0000000000000000 0000000000000000 0000000000000000 0000000000000000
  [    0.669190][    T1] GPR20: 0000000000000000 0000000000000000 0000000000000000 0000000000000000
  [    0.669190][    T1] GPR24: 0000000000000000 c000000002003408 c0000000020b1070 c0000000021ecee0
  [    0.669190][    T1] GPR28: 0000000000000000 0000000000000008 0000000000000000 c000000005836480
  [    0.670393][    T1] NIP [c00000000201eb70] msi_bitmap_selftest+0x1c8/0x3f8
  [    0.670499][    T1] LR [c00000000201eb68] msi_bitmap_selftest+0x1c0/0x3f8
  [    0.670657][    T1] Call Trace:
  [    0.670747][    T1] [c0000000037d7b70] [c00000000201eb68] msi_bitmap_selftest+0x1c0/0x3f8 (unreliable)
  [    0.670941][    T1] [c0000000037d7c20] [c000000000010d9c] do_one_initcall+0x7c/0x37c
  [    0.671085][    T1] [c0000000037d7d00] [c000000002004ba8] kernel_init_freeable+0x2fc/0x3cc
  [    0.671218][    T1] [c0000000037d7dd0] [c0000000000114fc] kernel_init+0x2c/0x1b0
  [    0.671336][    T1] [c0000000037d7e30] [c00000000000debc] ret_from_kernel_user_thread+0x14/0x1c
  [    0.671479][    T1] ---- interrupt: 0 at 0x0
  [    0.671777][    T1] Code: 38800001 38610068 4a162c61 54630ffe 0b030000 37deffff 4082ffe8 38800001 38610068 4a162c45 7c6318f8 54630ffe <0b030000> eba10070 7fdff378 3bde0001
  [    0.672127][    T1] ---[ end trace 0000000000000000 ]---
  ...

-- 
Cheers,
Nathan

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

[Yury Norov]

On Tue, Jun 30, 2026 at 01:52:40PM -0700, Nathan Chancellor wrote:
> Hi,
> 
> On Mon, Jun 22, 2026 at 11:00:36AM +0800, Yi Sun wrote:
> > 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>
> 
> I bisected a warning I see when virtually boot testing powerpc to this
> change in -next as commit 6eecaf5cf2dd ("lib: bitmap: optimize
> bitmap_find_next_zero_area_off()").

Thanks Nathan, I'll drop it from -next for now.
 
>   $ make -skj"$(nproc)" ARCH=powerpc CROSS_COMPILE=powerpc64-linux- mrproper ppc64le_guest_defconfig zImage.epapr
> 
>   $ curl -LSs https://github.com/ClangBuiltLinux/boot-utils/releases/download/20241120-044434/ppc64le-rootfs.cpio.zst | zstd -d >rootfs.cpio
> 
>   $ qemu-system-ppc64 \
>       -display none \
>       -nodefaults \
>       -device ipmi-bmc-sim,id=bmc0 \
>       -device isa-ipmi-bt,bmc=bmc0,irq=10 \
>       -machine powernv \
>       -kernel arch/powerpc/boot/zImage.epapr \
>       -initrd rootfs.cpio \
>       -m 2G \
>       -serial mon:stdio
>   ...
>   [    0.660986][    T1] Running code patching self-tests ...
>   [    0.667347][    T1] ------------[ cut here ]------------
>   [    0.667519][    T1] WARNING: arch/powerpc/sysdev/msi_bitmap.c:181 at msi_bitmap_selftest+0x1c8/0x3f8, CPU#0: swapper/0/1
>   [    0.667964][    T1] Modules linked in:
>   [    0.668237][    T1] CPU: 0 UID: 0 PID: 1 Comm: swapper/0 Not tainted 7.2.0-rc1-next-20260630 #1 PREEMPTLAZY
>   [    0.668462][    T1] Hardware name: IBM PowerNV (emulated by qemu) POWER10 0x801200 opal:v7.1-106-g785a5e307 PowerNV
>   [    0.668681][    T1] NIP:  c00000000201eb70 LR: c00000000201eb68 CTR: 0000000000000000
>   [    0.668809][    T1] REGS: c0000000037d78b0 TRAP: 0700   Not tainted  (7.2.0-rc1-next-20260630)
>   [    0.668956][    T1] MSR:  9000000000029033 <SF,HV,EE,ME,IR,DR,RI,LE>  CR: 24000224  XER: 20040000
>   [    0.669190][    T1] CFAR: c000000000181880 IRQMASK: 0
>   [    0.669190][    T1] GPR00: c00000000201eb68 c0000000037d7b70 c000000001c78100 0000000000000001
>   [    0.669190][    T1] GPR04: 0000000000000000 0000000000000001 0000000000000001 0000000000000000
>   [    0.669190][    T1] GPR08: 0000000000000000 0000000000000000 c000000003764f80 c000000000181d08
>   [    0.669190][    T1] GPR12: 0000000000000000 c000000002c10000 c0000000000114d8 0000000000000000
>   [    0.669190][    T1] GPR16: 0000000000000000 0000000000000000 0000000000000000 0000000000000000
>   [    0.669190][    T1] GPR20: 0000000000000000 0000000000000000 0000000000000000 0000000000000000
>   [    0.669190][    T1] GPR24: 0000000000000000 c000000002003408 c0000000020b1070 c0000000021ecee0
>   [    0.669190][    T1] GPR28: 0000000000000000 0000000000000008 0000000000000000 c000000005836480
>   [    0.670393][    T1] NIP [c00000000201eb70] msi_bitmap_selftest+0x1c8/0x3f8
>   [    0.670499][    T1] LR [c00000000201eb68] msi_bitmap_selftest+0x1c0/0x3f8
>   [    0.670657][    T1] Call Trace:
>   [    0.670747][    T1] [c0000000037d7b70] [c00000000201eb68] msi_bitmap_selftest+0x1c0/0x3f8 (unreliable)
>   [    0.670941][    T1] [c0000000037d7c20] [c000000000010d9c] do_one_initcall+0x7c/0x37c
>   [    0.671085][    T1] [c0000000037d7d00] [c000000002004ba8] kernel_init_freeable+0x2fc/0x3cc
>   [    0.671218][    T1] [c0000000037d7dd0] [c0000000000114fc] kernel_init+0x2c/0x1b0
>   [    0.671336][    T1] [c0000000037d7e30] [c00000000000debc] ret_from_kernel_user_thread+0x14/0x1c
>   [    0.671479][    T1] ---- interrupt: 0 at 0x0
>   [    0.671777][    T1] Code: 38800001 38610068 4a162c61 54630ffe 0b030000 37deffff 4082ffe8 38800001 38610068 4a162c45 7c6318f8 54630ffe <0b030000> eba10070 7fdff378 3bde0001
>   [    0.672127][    T1] ---[ end trace 0000000000000000 ]---
>   ...
> 
> -- 
> Cheers,
> Nathan

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

[yi.sun]

>Hi,



>



>On Mon, Jun 22, 2026 at 11:00:36AM +0800, Yi Sun wrote:



>> 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>



>



>I bisected a warning I see when virtually boot testing powerpc to this



>change in -next as commit 6eecaf5cf2dd ("lib: bitmap: optimize



>bitmap_find_next_zero_area_off()").



>



>  $ make -skj"$(nproc)" ARCH=powerpc CROSS_COMPILE=powerpc64-linux- mrproper ppc64le_guest_defconfig zImage.epapr



>



>  $ curl -LSs https://github.com/ClangBuiltLinux/boot-utils/releases/download/20241120-044434/ppc64le-rootfs.cpio.zst | zstd -d >rootfs.cpio



>



>  $ qemu-system-ppc64 \



>      -display none \



>      -nodefaults \



>      -device ipmi-bmc-sim,id=bmc0 \



>      -device isa-ipmi-bt,bmc=bmc0,irq=10 \



>      -machine powernv \



>      -kernel arch/powerpc/boot/zImage.epapr \



>      -initrd rootfs.cpio \



>      -m 2G \



>      -serial mon:stdio



>  ...



>  [    0.660986][    T1] Running code patching self-tests ...



>  [    0.667347][    T1] ------------[ cut here ]------------



>  [    0.667519][    T1] WARNING: arch/powerpc/sysdev/msi_bitmap.c:181 at msi_bitmap_selftest+0x1c8/0x3f8, CPU#0: swapper/0/1


This issue was caused by the return value of the function bitmap_find_next_zero_area.
Previously, the return value could be greater than size; now it has been modified to be equal to size.


int msi_bitmap_alloc_hwirqs(struct msi_bitmap *bmp, int num)
{
    offset = bitmap_find_next_zero_area(bmp->bitmap, bmp->irq_count, 0, num, (1 << order) - 1);
    if (offset > bmp->irq_count)
        goto err;


So, what should we do next? 
Should we make bitmap_find_next_zero_area_off return "size + 1" instead, all for the sake of compatibility? 
Or should we modify all the places that call bitmap_find_next_zero_area_off (which might be a big project)?




>  [    0.667964][    T1] Modules linked in:



>  [    0.668237][    T1] CPU: 0 UID: 0 PID: 1 Comm: swapper/0 Not tainted 7.2.0-rc1-next-20260630 #1 PREEMPTLAZY



>  [    0.668462][    T1] Hardware name: IBM PowerNV (emulated by qemu) POWER10 0x801200 opal:v7.1-106-g785a5e307 PowerNV



>  [    0.668681][    T1] NIP:  c00000000201eb70 LR: c00000000201eb68 CTR: 0000000000000000



>  [    0.668809][    T1] REGS: c0000000037d78b0 TRAP: 0700   Not tainted  (7.2.0-rc1-next-20260630)



>  [    0.668956][    T1] MSR:  9000000000029033 <SF,HV,EE,ME,IR,DR,RI,LE>  CR: 24000224  XER: 20040000



>  [    0.669190][    T1] CFAR: c000000000181880 IRQMASK: 0



>  [    0.669190][    T1] GPR00: c00000000201eb68 c0000000037d7b70 c000000001c78100 0000000000000001



>  [    0.669190][    T1] GPR04: 0000000000000000 0000000000000001 0000000000000001 0000000000000000



>  [    0.669190][    T1] GPR08: 0000000000000000 0000000000000000 c000000003764f80 c000000000181d08



>  [    0.669190][    T1] GPR12: 0000000000000000 c000000002c10000 c0000000000114d8 0000000000000000



>  [    0.669190][    T1] GPR16: 0000000000000000 0000000000000000 0000000000000000 0000000000000000



>  [    0.669190][    T1] GPR20: 0000000000000000 0000000000000000 0000000000000000 0000000000000000



>  [    0.669190][    T1] GPR24: 0000000000000000 c000000002003408 c0000000020b1070 c0000000021ecee0



>  [    0.669190][    T1] GPR28: 0000000000000000 0000000000000008 0000000000000000 c000000005836480



>  [    0.670393][    T1] NIP [c00000000201eb70] msi_bitmap_selftest+0x1c8/0x3f8



>  [    0.670499][    T1] LR [c00000000201eb68] msi_bitmap_selftest+0x1c0/0x3f8



>  [    0.670657][    T1] Call Trace:



>  [    0.670747][    T1] [c0000000037d7b70] [c00000000201eb68] msi_bitmap_selftest+0x1c0/0x3f8 (unreliable)



>  [    0.670941][    T1] [c0000000037d7c20] [c000000000010d9c] do_one_initcall+0x7c/0x37c



>  [    0.671085][    T1] [c0000000037d7d00] [c000000002004ba8] kernel_init_freeable+0x2fc/0x3cc



>  [    0.671218][    T1] [c0000000037d7dd0] [c0000000000114fc] kernel_init+0x2c/0x1b0



>  [    0.671336][    T1] [c0000000037d7e30] [c00000000000debc] ret_from_kernel_user_thread+0x14/0x1c



>  [    0.671479][    T1] ---- interrupt: 0 at 0x0



>  [    0.671777][    T1] Code: 38800001 38610068 4a162c61 54630ffe 0b030000 37deffff 4082ffe8 38800001 38610068 4a162c45 7c6318f8 54630ffe <0b030000> eba10070 7fdff378 3bde0001



>  [    0.672127][    T1] ---[ end trace 0000000000000000 ]---



>  ...



>



>-- 



>Cheers,



>Nathan

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

[Yury Norov]

> This issue was caused by the return value of the function bitmap_find_next_zero_area.
> Previously, the return value could be greater than size; now it has been modified to be equal to size.
> 
> 
> int msi_bitmap_alloc_hwirqs(struct msi_bitmap *bmp, int num)
> {
>     offset = bitmap_find_next_zero_area(bmp->bitmap, bmp->irq_count, 0, num, (1 << order) - 1);
>     if (offset > bmp->irq_count)
>         goto err;
> 
> 
> So, what should we do next? 
> Should we make bitmap_find_next_zero_area_off return "size + 1" instead, all for the sake of compatibility? 
> Or should we modify all the places that call bitmap_find_next_zero_area_off (which might be a big project)?
> 

Please resend v7 version returning 'size+1'. The next step would be
fixing the function to return size, together with the callers. It
should be the separate series. Please let me know if you want to take
over.

Thanks,
Yury