[PATCH 0/2] Improve the performance of bitmap_find_next_zero_area_off()

[PATCH 0/2] Improve the performance of bitmap_find_next_zero_area_off()

[Yi Sun]

Replacing find_next_bit() with find_last_bit_range()
can improve performance by an average of 50%.

===========

Test result:
	cnt	old_a_cnt	new_a_cnt	cnt_ratio	old_time(ns)	new_time(ns)	time_ratio
test1	8	71		34		52.1%		51357		25019		51.3%
test2	8	1		1		0%		1150		1153		around 0%

test1	32	81925		10402		87.3%		23103730	2910315		87.4%
test2	32	1		1		0%		434		434		around 0%

test1	128	82166		2572		96.9%		23054634	731453		96.8%
test2	128	1		1		0%		434		438		around 0%

test1	1024	81620		321		99.6%		23035192	234330		99%
test2   1024	14		7		50%		4257		2257		47%

test1	4096	80923		81		99.9%		22700265	57861		99.7%
test2	4096	648		92		85.8%		192854		27177		85.9%

============

Test result explanation:
@test1: The bitmap is filled with random numbers,
so the bitmap is very messy.
@test2: Sparse bitmap.

@cnt: The expected number of consecutive clear bits.

@old_a_cnt: Total number of "goto again" when
using find_next_bit().
@new_a_cnt: Total number of "goto again" when
using find_last_bit_range().
Finding @cnt consecutive clear bits in the bitmap
may require multiple attempts.
The number of repetitions should be recorded.
@cnt_ratio = (old_a_cnt - new_a_cnt) / old_a_cnt.

@old_time(ns): The total time consumed by
bitmap_find_next_zero_area_off() when
using find_next_bit().
@new_time(ns): The total time consumed by
bitmap_find_next_zero_area_off() when
using find_last_bit_range().
@time_ratio = (old_time - new_time) / old_time.

==============

Test case(refer to lib/find_bit_benchmark.c):

define BITMAP_LEN      (4096UL * 8 * 10)
define SPARSE          500
static DECLARE_BITMAP(bitmap, BITMAP_LEN);

static void test_main()
{
	unsigned long nbits = BITMAP_LEN / SPARSE;

	//test1
	get_random_bytes(bitmap, sizeof(bitmap));
	__test_all();

	//test2
	bitmap_zero(bitmap, BITMAP_LEN);
        while (nbits--)
		__set_bit(get_random_u32_below(BITMAP_LEN), bitmap);
	__test_all();
}

static void __test_all()
{
	//Expected number of consecutive clear bits.
	u32 cnt = 8;

	//Ignore the results of this test.
	__test_new(cnt);

	//To mitigate the impact of caching,
	//we will use the results of this test.
	__test_new(cnt);

	//Ignore the results of this test.
	__test_old(cnt);

	//To mitigate the impact of caching,
	//we will use the results of this test.
	__test_old(cnt);
}

//Add time-consuming statistics to bitmap_find_next_zero_area_off().
static ktime_t __test_old/__test_new(u32 nr)
{
        unsigned long *map = bitmap;
        unsigned long size = BITMAP_LEN;
        unsigned long start = 0;
        unsigned long align_mask = 0;
        unsigned long align_offset = 0;

        unsigned long index, end, i, again_cnt = 0;
        //Here add time-consuming statistics.
        ktime_t time = ktime_get();

again:
        again_cnt++;
        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) {
                //Here add time-consuming statistics.
                time = ktime_get() - time;
                return time;
        }

        //__test_old() use this.
        i = find_next_bit(map, end, index);

        //__test_new() use this.
        i = find_last_bit_range(map, end, index);

        if (i < end) {
                start = i + 1;
                goto again;
        }

        //Here add time-consuming statistics.
        time = ktime_get() - time;
        return time;
}


Yi Sun (2):
  lib: bitmap: add find_last_bit_range() and _find_last_bit_range()
  lib: bitmap: reduce the number of goto again in
    bitmap_find_next_zero_area_off()

 include/linux/find.h | 35 +++++++++++++++++++++++++++++++++++
 lib/bitmap.c         |  2 +-
 lib/find_bit.c       | 30 ++++++++++++++++++++++++++++++
 3 files changed, 66 insertions(+), 1 deletion(-)

-- 
2.34.1

[PATCH 1/2] lib: bitmap: add find_last_bit_range() and _find_last_bit_range()

[Yi Sun]

In some scenarios, it's not desirable to keep searching through the
beginning of the bitmap, but rather to search within a specific part.
The newly added function can accomplish this quickly.

Signed-off-by: Yi Sun <yi.sun@unisoc.com>
---
 include/linux/find.h | 35 +++++++++++++++++++++++++++++++++++
 lib/find_bit.c       | 30 ++++++++++++++++++++++++++++++
 2 files changed, 65 insertions(+)

diff --git a/include/linux/find.h b/include/linux/find.h
index 6c2be8ca615d..7126b0fffe0f 100644
--- a/include/linux/find.h
+++ b/include/linux/find.h
@@ -33,6 +33,8 @@ unsigned long _find_first_and_and_bit(const unsigned long *addr1, const unsigned
 				      const unsigned long *addr3, unsigned long size);
 extern unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size);
 extern unsigned long _find_last_bit(const unsigned long *addr, unsigned long size);
+extern unsigned long _find_last_bit_range(const unsigned long *addr, unsigned long size,
+					unsigned long offset);
 
 #ifdef __BIG_ENDIAN
 unsigned long _find_first_zero_bit_le(const unsigned long *addr, unsigned long size);
@@ -413,6 +415,39 @@ unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
 }
 #endif
 
+#ifndef find_last_bit_range
+/**
+ * find_last_bit_range - find the last set bit in a memory region
+ * @addr: The address to base the search on
+ * @size: The bitmap size in bits
+ * @offset: The bit number to start searching at
+ *
+ * Compared to the find_last_bit(),
+ * find_last_bit_range() has an additional parameter @offset,
+ * so it can search within a specific range of the bitmap,
+ * just like the find_next_bit().
+ *
+ * Returns the bit number of the last set bit, or size.
+ */
+static __always_inline
+unsigned long find_last_bit_range(const unsigned long *addr, unsigned long size,
+				unsigned long offset)
+{
+	if (small_const_nbits(size)) {
+		unsigned long val;
+
+		if (unlikely(offset >= size))
+			return size;
+
+		val = *addr & GENMASK(size - 1, offset);
+
+		return val ? __fls(val) : size;
+	}
+
+	return _find_last_bit_range(addr, size, offset);
+}
+#endif
+
 /**
  * find_next_and_bit_wrap - find the next set bit in both memory regions
  * @addr1: The first address to base the search on
diff --git a/lib/find_bit.c b/lib/find_bit.c
index 5ac52dfce730..bedc85053cea 100644
--- a/lib/find_bit.c
+++ b/lib/find_bit.c
@@ -237,6 +237,36 @@ unsigned long _find_last_bit(const unsigned long *addr, unsigned long size)
 EXPORT_SYMBOL(_find_last_bit);
 #endif
 
+#ifndef find_last_bit_range
+unsigned long _find_last_bit_range(const unsigned long *addr, unsigned long size,
+				unsigned long offset)
+{
+	unsigned long val, idx, start_idx;
+
+	if (unlikely(offset >= size))
+		return size;
+
+	val = BITMAP_LAST_WORD_MASK(size);
+	idx = (size - 1) / BITS_PER_LONG;
+	start_idx = offset / BITS_PER_LONG;
+
+	do {
+		val &= addr[idx];
+
+		if (idx == start_idx)
+			val &= BITMAP_FIRST_WORD_MASK(offset);
+
+		if (val)
+			return idx * BITS_PER_LONG + __fls(val);
+
+		val = ~0UL;
+	} while (idx-- > start_idx);
+
+	return size;
+}
+EXPORT_SYMBOL(_find_last_bit_range);
+#endif
+
 unsigned long find_next_clump8(unsigned long *clump, const unsigned long *addr,
 			       unsigned long size, unsigned long offset)
 {
-- 
2.34.1

[PATCH 2/2] lib: bitmap: reduce the number of goto again in 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 "goto again" calls.

Signed-off-by: Yi Sun <yi.sun@unisoc.com>
---
 lib/bitmap.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/lib/bitmap.c b/lib/bitmap.c
index b9bfa157e095..53961a7683a4 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -442,7 +442,7 @@ 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);
+	i = find_last_bit_range(map, end, index);
 	if (i < end) {
 		start = i + 1;
 		goto again;
-- 
2.34.1

Re: [PATCH 1/2] lib: bitmap: add find_last_bit_range() and _find_last_bit_range()

[Michał Nazarewicz]

On Tue, May 12 2026, Yi Sun wrote:
> In some scenarios, it's not desirable to keep searching through the
> beginning of the bitmap, but rather to search within a specific part.
> The newly added function can accomplish this quickly.
>
> Signed-off-by: Yi Sun <yi.sun@unisoc.com>

Acked-by: Michał Nazarewicz <mina86@mina86.com>

> ---
>  include/linux/find.h | 35 +++++++++++++++++++++++++++++++++++
>  lib/find_bit.c       | 30 ++++++++++++++++++++++++++++++
>  2 files changed, 65 insertions(+)
>
> diff --git a/include/linux/find.h b/include/linux/find.h
> index 6c2be8ca615d..7126b0fffe0f 100644
> --- a/include/linux/find.h
> +++ b/include/linux/find.h
> @@ -33,6 +33,8 @@ unsigned long _find_first_and_and_bit(const unsigned long *addr1, const unsigned
>  				      const unsigned long *addr3, unsigned long size);
>  extern unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size);
>  extern unsigned long _find_last_bit(const unsigned long *addr, unsigned long size);
> +extern unsigned long _find_last_bit_range(const unsigned long *addr, unsigned long size,
> +					unsigned long offset);
>  
>  #ifdef __BIG_ENDIAN
>  unsigned long _find_first_zero_bit_le(const unsigned long *addr, unsigned long size);
> @@ -413,6 +415,39 @@ unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
>  }
>  #endif
>  
> +#ifndef find_last_bit_range
> +/**
> + * find_last_bit_range - find the last set bit in a memory region
> + * @addr: The address to base the search on
> + * @size: The bitmap size in bits
> + * @offset: The bit number to start searching at
> + *
> + * Compared to the find_last_bit(),
> + * find_last_bit_range() has an additional parameter @offset,
> + * so it can search within a specific range of the bitmap,
> + * just like the find_next_bit().
> + *
> + * Returns the bit number of the last set bit, or size.
> + */
> +static __always_inline
> +unsigned long find_last_bit_range(const unsigned long *addr, unsigned long size,
> +				unsigned long offset)

This should be called find_last_bit_off instead.  `_range` suffix, to me
at least, implies that the order of arguments is (addr, offset, size).
`_off` is also the suffix used by `bitmap_find_next_zero_area_off` name.

> +{
> +	if (small_const_nbits(size)) {
> +		unsigned long val;
> +
> +		if (unlikely(offset >= size))
> +			return size;
> +
> +		val = *addr & GENMASK(size - 1, offset);
> +
> +		return val ? __fls(val) : size;
> +	}
> +
> +	return _find_last_bit_range(addr, size, offset);
> +}
> +#endif
> +
>  /**
>   * find_next_and_bit_wrap - find the next set bit in both memory regions
>   * @addr1: The first address to base the search on
> diff --git a/lib/find_bit.c b/lib/find_bit.c
> index 5ac52dfce730..bedc85053cea 100644
> --- a/lib/find_bit.c
> +++ b/lib/find_bit.c
> @@ -237,6 +237,36 @@ unsigned long _find_last_bit(const unsigned long *addr, unsigned long size)
>  EXPORT_SYMBOL(_find_last_bit);
>  #endif
>  
> +#ifndef find_last_bit_range
> +unsigned long _find_last_bit_range(const unsigned long *addr, unsigned long size,
> +				unsigned long offset)
> +{
> +	unsigned long val, idx, start_idx;
> +
> +	if (unlikely(offset >= size))
> +		return size;
> +
> +	val = BITMAP_LAST_WORD_MASK(size);
> +	idx = (size - 1) / BITS_PER_LONG;
> +	start_idx = offset / BITS_PER_LONG;
> +
> +	do {
> +		val &= addr[idx];
> +
> +		if (idx == start_idx)
> +			val &= BITMAP_FIRST_WORD_MASK(offset);
> +
> +		if (val)
> +			return idx * BITS_PER_LONG + __fls(val);
> +
> +		val = ~0UL;
> +	} while (idx-- > start_idx);

Perhaps:

```
	val = BITMAP_LAST_WORD_MASK(size) & addr[idx];
	while (!val && idx > start_idx)
		val = addr[--idx];
	if (idx == start_idx)
		val &= BITMAP_FIRST_WORD_MASK(offset);
	return val ? idx * BITS_PER_LONG + __fls(val) : size;
```

This moves the `idx == start_idx` condition outside of the loop so that
it’s not checked on each iteration.  It also removes the need for `val =
~0UL` from the loop again simplifying its body.

> +
> +	return size;
> +}
> +EXPORT_SYMBOL(_find_last_bit_range);
> +#endif
> +
>  unsigned long find_next_clump8(unsigned long *clump, const unsigned long *addr,
>  			       unsigned long size, unsigned long offset)
>  {

-- 
Best regards
ミハウ “𝓶𝓲𝓷𝓪86” ナザレヴィツ
«If at first you don’t succeed, give up skydiving»

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

[Michał Nazarewicz]

On Tue, May 12 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 "goto again" calls.
>
> Signed-off-by: Yi Sun <yi.sun@unisoc.com>

Acked-by: Michał Nazarewicz <mina86@mina86.com>

> ---
>  lib/bitmap.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
>
> diff --git a/lib/bitmap.c b/lib/bitmap.c
> index b9bfa157e095..53961a7683a4 100644
> --- a/lib/bitmap.c
> +++ b/lib/bitmap.c
> @@ -442,7 +442,7 @@ 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);
> +	i = find_last_bit_range(map, end, index);
>  	if (i < end) {
>  		start = i + 1;
>  		goto again;

-- 
Best regards
ミハウ “𝓶𝓲𝓷𝓪86” ナザレヴィツ
«If at first you don’t succeed, give up skydiving»

Re: [PATCH 0/2] Improve the performance of bitmap_find_next_zero_area_off()

[Yury Norov]

On Tue, May 12, 2026 at 12:06:57PM +0800, Yi Sun wrote:
> Replacing find_next_bit() with find_last_bit_range()
> can improve performance by an average of 50%.
>
> ===========
> 
> Test result:
> 	cnt	old_a_cnt	new_a_cnt	cnt_ratio	old_time(ns)	new_time(ns)	time_ratio
> test1	8	71		34		52.1%		51357		25019		51.3%
> test2	8	1		1		0%		1150		1153		around 0%
> 
> test1	32	81925		10402		87.3%		23103730	2910315		87.4%
> test2	32	1		1		0%		434		434		around 0%
> 
> test1	128	82166		2572		96.9%		23054634	731453		96.8%
> test2	128	1		1		0%		434		438		around 0%
> 
> test1	1024	81620		321		99.6%		23035192	234330		99%
> test2   1024	14		7		50%		4257		2257		47%
> 
> test1	4096	80923		81		99.9%		22700265	57861		99.7%
> test2	4096	648		92		85.8%		192854		27177		85.9%
> 
> ============
> 
> Test result explanation:
> @test1: The bitmap is filled with random numbers,
> so the bitmap is very messy.
> @test2: Sparse bitmap.
> 
> @cnt: The expected number of consecutive clear bits.
> 
> @old_a_cnt: Total number of "goto again" when
> using find_next_bit().
> @new_a_cnt: Total number of "goto again" when
> using find_last_bit_range().
> Finding @cnt consecutive clear bits in the bitmap
> may require multiple attempts.
> The number of repetitions should be recorded.
> @cnt_ratio = (old_a_cnt - new_a_cnt) / old_a_cnt.
> 
> @old_time(ns): The total time consumed by
> bitmap_find_next_zero_area_off() when
> using find_next_bit().
> @new_time(ns): The total time consumed by
> bitmap_find_next_zero_area_off() when
> using find_last_bit_range().
> @time_ratio = (old_time - new_time) / old_time.
> 
> ==============
> 
> Test case(refer to lib/find_bit_benchmark.c):
> 
> define BITMAP_LEN      (4096UL * 8 * 10)
> define SPARSE          500
> static DECLARE_BITMAP(bitmap, BITMAP_LEN);
> 
> static void test_main()
> {
> 	unsigned long nbits = BITMAP_LEN / SPARSE;
> 
> 	//test1
> 	get_random_bytes(bitmap, sizeof(bitmap));
> 	__test_all();
> 
> 	//test2
> 	bitmap_zero(bitmap, BITMAP_LEN);
>         while (nbits--)
> 		__set_bit(get_random_u32_below(BITMAP_LEN), bitmap);
> 	__test_all();
> }
> 
> static void __test_all()
> {
> 	//Expected number of consecutive clear bits.
> 	u32 cnt = 8;
> 
> 	//Ignore the results of this test.
> 	__test_new(cnt);
> 
> 	//To mitigate the impact of caching,
> 	//we will use the results of this test.
> 	__test_new(cnt);
> 
> 	//Ignore the results of this test.
> 	__test_old(cnt);
> 
> 	//To mitigate the impact of caching,
> 	//we will use the results of this test.
> 	__test_old(cnt);
> }
> 
> //Add time-consuming statistics to bitmap_find_next_zero_area_off().
> static ktime_t __test_old/__test_new(u32 nr)
> {
>         unsigned long *map = bitmap;
>         unsigned long size = BITMAP_LEN;
>         unsigned long start = 0;
>         unsigned long align_mask = 0;
>         unsigned long align_offset = 0;
> 
>         unsigned long index, end, i, again_cnt = 0;
>         //Here add time-consuming statistics.
>         ktime_t time = ktime_get();
> 
> again:
>         again_cnt++;
>         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) {
>                 //Here add time-consuming statistics.
>                 time = ktime_get() - time;
>                 return time;
>         }
> 
>         //__test_old() use this.
>         i = find_next_bit(map, end, index);
> 
>         //__test_new() use this.
>         i = find_last_bit_range(map, end, index);
> 
>         if (i < end) {
>                 start = i + 1;
>                 goto again;
>         }
> 
>         //Here add time-consuming statistics.
>         time = ktime_get() - time;
>         return time;
> }

Please check the lib/find_bit_benchmark.c and extend it with your
scenario. Please make sure you're printing and everything is aligned
with the existing format.

> Yi Sun (2):
>   lib: bitmap: add find_last_bit_range() and _find_last_bit_range()
>   lib: bitmap: reduce the number of goto again in
>     bitmap_find_next_zero_area_off()
> 
>  include/linux/find.h | 35 +++++++++++++++++++++++++++++++++++
>  lib/bitmap.c         |  2 +-
>  lib/find_bit.c       | 30 ++++++++++++++++++++++++++++++
>  3 files changed, 66 insertions(+), 1 deletion(-)
> 
> -- 
> 2.34.1

Re: [PATCH 1/2] lib: bitmap: add find_last_bit_range() and _find_last_bit_range()

[Yury Norov]

On Tue, May 12, 2026 at 12:06:58PM +0800, Yi Sun wrote:
> In some scenarios, it's not desirable to keep searching through the
> beginning of the bitmap, but rather to search within a specific part.
> The newly added function can accomplish this quickly.
> 
> Signed-off-by: Yi Sun <yi.sun@unisoc.com>
> ---
>  include/linux/find.h | 35 +++++++++++++++++++++++++++++++++++
>  lib/find_bit.c       | 30 ++++++++++++++++++++++++++++++
>  2 files changed, 65 insertions(+)
> 
> diff --git a/include/linux/find.h b/include/linux/find.h
> index 6c2be8ca615d..7126b0fffe0f 100644
> --- a/include/linux/find.h
> +++ b/include/linux/find.h
> @@ -33,6 +33,8 @@ unsigned long _find_first_and_and_bit(const unsigned long *addr1, const unsigned
>  				      const unsigned long *addr3, unsigned long size);
>  extern unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size);
>  extern unsigned long _find_last_bit(const unsigned long *addr, unsigned long size);
> +extern unsigned long _find_last_bit_range(const unsigned long *addr, unsigned long size,
> +					unsigned long offset);
>  
>  #ifdef __BIG_ENDIAN
>  unsigned long _find_first_zero_bit_le(const unsigned long *addr, unsigned long size);
> @@ -413,6 +415,39 @@ unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
>  }
>  #endif
>  
> +#ifndef find_last_bit_range

Drop ifdefery. There's no arch implementation, so nothing to protect.

> +/**
> + * find_last_bit_range - find the last set bit in a memory region

find_last_bit_from, please. This is how the existing API named.

> + * @addr: The address to base the search on
> + * @size: The bitmap size in bits
> + * @offset: The bit number to start searching at
> + *
> + * Compared to the find_last_bit(),
> + * find_last_bit_range() has an additional parameter @offset,
> + * so it can search within a specific range of the bitmap,
> + * just like the find_next_bit().
> + *
> + * Returns the bit number of the last set bit, or size.
> + */
> +static __always_inline
> +unsigned long find_last_bit_range(const unsigned long *addr, unsigned long size,
> +				unsigned long offset)
> +{
> +	if (small_const_nbits(size)) {
> +		unsigned long val;
> +
> +		if (unlikely(offset >= size))
> +			return size;
> +
> +		val = *addr & GENMASK(size - 1, offset);
> +
> +		return val ? __fls(val) : size;
> +	}
> +
> +	return _find_last_bit_range(addr, size, offset);
> +}
> +#endif
> +
>  /**
>   * find_next_and_bit_wrap - find the next set bit in both memory regions
>   * @addr1: The first address to base the search on
> diff --git a/lib/find_bit.c b/lib/find_bit.c
> index 5ac52dfce730..bedc85053cea 100644
> --- a/lib/find_bit.c
> +++ b/lib/find_bit.c
> @@ -237,6 +237,36 @@ unsigned long _find_last_bit(const unsigned long *addr, unsigned long size)
>  EXPORT_SYMBOL(_find_last_bit);
>  #endif
>  
> +#ifndef find_last_bit_range
> +unsigned long _find_last_bit_range(const unsigned long *addr, unsigned long size,
> +				unsigned long offset)
> +{
> +	unsigned long val, idx, start_idx;
> +
> +	if (unlikely(offset >= size))
> +		return size;
> +
> +	val = BITMAP_LAST_WORD_MASK(size);
> +	idx = (size - 1) / BITS_PER_LONG;
> +	start_idx = offset / BITS_PER_LONG;
> +
> +	do {
> +		val &= addr[idx];
> +
> +		if (idx == start_idx)
> +			val &= BITMAP_FIRST_WORD_MASK(offset);
> +
> +		if (val)
> +			return idx * BITS_PER_LONG + __fls(val);
> +
> +		val = ~0UL;

Can you consider handling the last bit out of the loop, so the loop
will have less code?

> +	} while (idx-- > start_idx);
> +
> +	return size;
> +}
> +EXPORT_SYMBOL(_find_last_bit_range);
> +#endif
> +
>  unsigned long find_next_clump8(unsigned long *clump, const unsigned long *addr,
>  			       unsigned long size, unsigned long offset)
>  {
> -- 
> 2.34.1

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

[Yury Norov]

On Tue, May 12, 2026 at 12:06:59PM +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@unisoc.com>
> ---
>  lib/bitmap.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
> 
> diff --git a/lib/bitmap.c b/lib/bitmap.c
> index b9bfa157e095..53961a7683a4 100644
> --- a/lib/bitmap.c
> +++ b/lib/bitmap.c
> @@ -442,7 +442,7 @@ 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);
> +	i = find_last_bit_range(map, end, index);
>  	if (i < end) {
>  		start = i + 1;
>  		goto again;

If the only user of the API is in-house, I believe we can just move
the 'map' pointer and decrease the 'end' accordingly:

        i = find_last_bit(map + BITS_TO_LONGS(index),
                                end - round_down(index, BITS_PER_LONG));

That way you'll be able to bail out earlier just as well.

(Not tested, just an illustration)

Thanks,
Yury