[PATCH v8 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@xxxxxxxxx>
Signed-off-by: Yury Norov <yury.norov@xxxxxxxxx>
Signed-off-by: Yi Sun <yi.sun@xxxxxxxxxx>
---
 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