* [PATCH v8 0/2] Improve the performance of bitmap_find_next_zero_area_off()
@ 2026-06-22 13:08 Yi Sun
2026-06-22 13:08 ` [PATCH v8 1/2] lib: bitmap: add tests for bitmap_find_next_zero_area_off() Yi Sun
2026-06-22 13:08 ` [PATCH v8 2/2] lib: bitmap: optimize bitmap_find_next_zero_area_off() Yi Sun
0 siblings, 2 replies; 3+ messages in thread
From: Yi Sun @ 2026-06-22 13:08 UTC (permalink / raw)
To: yury.norov
Cc: yi.sun, 279644543, mina86, mnazarewicz, akpm, akinobu.mita,
linux-kernel, tjmercier, fvdl, tglx, song, hch, minchan, jstultz
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 8 improve test code.
When original bitmap_find_next_zero_area_off() fails,
it returns end, where end is greater than size.
Therefore, patch1 should use >.
expect_eq_uint(1,
bitmap_find_next_zero_area_off(bmap, 192, 0, 33, 0, 0) > 192);
When new bitmap_find_next_zero_area_off() fails, it returns size.
Therefore, patch2 should be changed to =.
expect_eq_uint(192,
bitmap_find_next_zero_area_off(bmap, 192, 0, 33, 0, 0));
---
v7: https://lore.kernel.org/all/20260622030036.1744080-1-yi.sun@unisoc.com
- 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
^ permalink raw reply [flat|nested] 3+ messages in thread
* [PATCH v8 1/2] lib: bitmap: add tests for bitmap_find_next_zero_area_off()
2026-06-22 13:08 [PATCH v8 0/2] Improve the performance of bitmap_find_next_zero_area_off() Yi Sun
@ 2026-06-22 13:08 ` Yi Sun
2026-06-22 13:08 ` [PATCH v8 2/2] lib: bitmap: optimize bitmap_find_next_zero_area_off() Yi Sun
1 sibling, 0 replies; 3+ messages in thread
From: Yi Sun @ 2026-06-22 13:08 UTC (permalink / raw)
To: yury.norov
Cc: yi.sun, 279644543, mina86, mnazarewicz, akpm, akinobu.mita,
linux-kernel, tjmercier, fvdl, tglx, song, hch, minchan, jstultz
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..5acb4dc5223c 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
^ permalink raw reply [flat|nested] 3+ messages in thread
* [PATCH v8 2/2] lib: bitmap: optimize bitmap_find_next_zero_area_off()
2026-06-22 13:08 [PATCH v8 0/2] Improve the performance of bitmap_find_next_zero_area_off() Yi Sun
2026-06-22 13:08 ` [PATCH v8 1/2] lib: bitmap: add tests for bitmap_find_next_zero_area_off() Yi Sun
@ 2026-06-22 13:08 ` Yi Sun
1 sibling, 0 replies; 3+ messages in thread
From: Yi Sun @ 2026-06-22 13:08 UTC (permalink / raw)
To: yury.norov
Cc: yi.sun, 279644543, mina86, mnazarewicz, akpm, akinobu.mita,
linux-kernel, tjmercier, fvdl, tglx, song, hch, minchan, jstultz
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 ++++++++++++++++---------------
lib/test_bitmap.c | 4 ++--
2 files changed, 18 insertions(+), 17 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);
diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c
index 5acb4dc5223c..40df8d8575c0 100644
--- a/lib/test_bitmap.c
+++ b/lib/test_bitmap.c
@@ -267,8 +267,8 @@ test_bitmap_find_next_zero_area_off(void)
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);
+ expect_eq_uint(192,
+ bitmap_find_next_zero_area_off(bmap, 192, 0, 33, 0, 0));
}
static void __init test_fill_set(void)
--
2.34.1
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2026-06-22 13:09 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2026-06-22 13:08 [PATCH v8 0/2] Improve the performance of bitmap_find_next_zero_area_off() Yi Sun
2026-06-22 13:08 ` [PATCH v8 1/2] lib: bitmap: add tests for bitmap_find_next_zero_area_off() Yi Sun
2026-06-22 13:08 ` [PATCH v8 2/2] lib: bitmap: optimize bitmap_find_next_zero_area_off() Yi Sun
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox
all inboxes | Powered by JetHome®