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

[Yury Norov]

On Mon, Jun 01, 2026 at 05:42:33PM +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 "goto again" calls.
> 
> Signed-off-by: Yi Sun <yi.sun@xxxxxxxxxx>
> ---
>  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:

Can you make an extra step, and remove the 'goto again' completely
with the more high-level for(), do-while() or similar?

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

Too many indexes here. Can you find some better, meaningful names?

> +
> +	i = find_last_bit(map + index_idx, end - index_bits_align) + index_bits_align;
> +	if (i > index && i < end) {
>  		start = i + 1;
>  		goto again;
>  	}

I spent a couple cycles trying to understand why it works better,
comparing to find_next_bit(). The thing is that the distance between
first set bit and the beginning of the area is greater than between
the last bit and the beginning, so we make bigger steps traversing the
butmap. Is that right? Can you add a step-by-step explanation in the
commit message for both versions, for clarity?

Still wondering why the 'last_bit' version is slower here. Looking at
the find_bit_benchmark output, the 'last_bit' is generally faster than
the 'next_bit'...

Thanks,
Yury

> -- 
> 2.34.1