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

Acked-by: Michał Nazarewicz <mina86@xxxxxxxxxx>

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