Re: [PATCH v5 2/2] lib: bitmap: optimize bitmap_find_next_zero_area_off()

[Yury Norov]

On Thu, Jun 18, 2026 at 09:52:52AM +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 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) ->
> goto again ->
> find_next_zero_bit(start = 5, find bit 6) -> find_next_bit(find bit 9) ->
> goto again ->
> 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) ->
> goto again ->
> find_next_zero_bit(start = 10, find bit 11) -> success

In new logic there's no goto, right?

> 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
> 
> Signed-off-by: Yi Sun <yi.sun@xxxxxxxxxx>
> ---
>  lib/bitmap.c | 35 +++++++++++++++++++++--------------
>  1 file changed, 21 insertions(+), 14 deletions(-)
> 
> diff --git a/lib/bitmap.c b/lib/bitmap.c
> index b9bfa157e095..a2c4bd22d875 100644
> --- a/lib/bitmap.c
> +++ b/lib/bitmap.c
> @@ -432,22 +432,29 @@ 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) {
> +	unsigned long find_idx, end, i, find_word_idx, find_word_off;
> +
> +	for (;;) {

"Infinite" loop is nothing better than the backward goto. 
Can you try this:

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

If it works for you, let's move with the for_each() version.
Can you test and add my Co-developed-by please?

Thanks,
Yury

> +		find_idx = find_next_zero_bit(map, size, start);
> +
> +		/* Align allocation */
> +		find_idx = __ALIGN_MASK(find_idx + align_offset,
> +			align_mask) - align_offset;
> +
> +		end = find_idx + nr;
> +		if (end > size)
> +			return end;
> +
> +		find_word_idx = find_idx / BITS_PER_LONG;
> +		find_word_off = find_word_idx * BITS_PER_LONG;
> +
> +		i = find_last_bit(map + find_word_idx,
> +			end - find_word_off) + find_word_off;
> +		if (i >= end || i < find_idx)
> +			return find_idx;
> +
>  		start = i + 1;
> -		goto again;
>  	}
> -	return index;
>  }
>  EXPORT_SYMBOL(bitmap_find_next_zero_area_off);
>  
> -- 
> 2.34.1