[PATCH v4 1/2] lib: bitmap: reduce the number of goto again in bitmap_find_next_zero_area_off()

[Yi Sun <yi.sun@unisoc.com>]

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 "goto again" calls.

Signed-off-by: Yi Sun <yi.sun@unisoc.com>
---
 lib/bitmap.c | 10 +++++++---
 1 file changed, 7 insertions(+), 3 deletions(-)

diff --git a/lib/bitmap.c b/lib/bitmap.c
index b9bfa157e095..7d0fbcbe6973 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -432,7 +432,7 @@ unsigned long bitmap_find_next_zero_area_off(unsigned long *map,
 					     unsigned long align_mask,
 					     unsigned long align_offset)
 {
-	unsigned long index, end, i;
+	unsigned long index, end, i, index_bits_align, index_idx;
 again:
 	index = find_next_zero_bit(map, size, start);
 
@@ -442,8 +442,12 @@ unsigned long bitmap_find_next_zero_area_off(unsigned long *map,
 	end = index + nr;
 	if (end > size)
 		return end;
-	i = find_next_bit(map, end, index);
-	if (i < end) {
+
+	index_bits_align = round_down(index, BITS_PER_LONG);
+	index_idx = index / BITS_PER_LONG;
+
+	i = find_last_bit(map + index_idx, end - index_bits_align) + index_bits_align;
+	if (i > index && i < end) {
 		start = i + 1;
 		goto again;
 	}
-- 
2.34.1