Re: Re: [PATCH v7 2/2] lib: bitmap: optimize bitmap_find_next_zero_area_off()
From: yi . sun
Date: Sat Jul 04 2026 - 05:12:49 EST
>Hi,
>
>On Mon, Jun 22, 2026 at 11:00:36AM +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) ->
>> next loop ->
>> find_next_zero_bit(start = 5, find bit 6) -> find_next_bit(find bit 9) ->
>> next loop ->
>> 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) ->
>> next loop ->
>> find_next_zero_bit(start = 10, find bit 11) -> success
>>
>> 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
>>
>> Co-developed-by: Yury Norov <yury.norov@xxxxxxxxx>
>> Signed-off-by: Yury Norov <yury.norov@xxxxxxxxx>
>> Signed-off-by: Yi Sun <yi.sun@xxxxxxxxxx>
>
>I bisected a warning I see when virtually boot testing powerpc to this
>change in -next as commit 6eecaf5cf2dd ("lib: bitmap: optimize
>bitmap_find_next_zero_area_off()").
>
> $ make -skj"$(nproc)" ARCH=powerpc CROSS_COMPILE=powerpc64-linux- mrproper ppc64le_guest_defconfig zImage.epapr
>
> $ curl -LSs https://github.com/ClangBuiltLinux/boot-utils/releases/download/20241120-044434/ppc64le-rootfs.cpio.zst | zstd -d >rootfs.cpio
>
> $ qemu-system-ppc64 \
> -display none \
> -nodefaults \
> -device ipmi-bmc-sim,id=bmc0 \
> -device isa-ipmi-bt,bmc=bmc0,irq=10 \
> -machine powernv \
> -kernel arch/powerpc/boot/zImage.epapr \
> -initrd rootfs.cpio \
> -m 2G \
> -serial mon:stdio
> ...
> [ 0.660986][ T1] Running code patching self-tests ...
> [ 0.667347][ T1] ------------[ cut here ]------------
> [ 0.667519][ T1] WARNING: arch/powerpc/sysdev/msi_bitmap.c:181 at msi_bitmap_selftest+0x1c8/0x3f8, CPU#0: swapper/0/1
This issue was caused by the return value of the function bitmap_find_next_zero_area.
Previously, the return value could be greater than size; now it has been modified to be equal to size.
int msi_bitmap_alloc_hwirqs(struct msi_bitmap *bmp, int num)
{
offset = bitmap_find_next_zero_area(bmp->bitmap, bmp->irq_count, 0, num, (1 << order) - 1);
if (offset > bmp->irq_count)
goto err;
So, what should we do next?
Should we make bitmap_find_next_zero_area_off return "size + 1" instead, all for the sake of compatibility?
Or should we modify all the places that call bitmap_find_next_zero_area_off (which might be a big project)?
> [ 0.667964][ T1] Modules linked in:
> [ 0.668237][ T1] CPU: 0 UID: 0 PID: 1 Comm: swapper/0 Not tainted 7.2.0-rc1-next-20260630 #1 PREEMPTLAZY
> [ 0.668462][ T1] Hardware name: IBM PowerNV (emulated by qemu) POWER10 0x801200 opal:v7.1-106-g785a5e307 PowerNV
> [ 0.668681][ T1] NIP: c00000000201eb70 LR: c00000000201eb68 CTR: 0000000000000000
> [ 0.668809][ T1] REGS: c0000000037d78b0 TRAP: 0700 Not tainted (7.2.0-rc1-next-20260630)
> [ 0.668956][ T1] MSR: 9000000000029033 <SF,HV,EE,ME,IR,DR,RI,LE> CR: 24000224 XER: 20040000
> [ 0.669190][ T1] CFAR: c000000000181880 IRQMASK: 0
> [ 0.669190][ T1] GPR00: c00000000201eb68 c0000000037d7b70 c000000001c78100 0000000000000001
> [ 0.669190][ T1] GPR04: 0000000000000000 0000000000000001 0000000000000001 0000000000000000
> [ 0.669190][ T1] GPR08: 0000000000000000 0000000000000000 c000000003764f80 c000000000181d08
> [ 0.669190][ T1] GPR12: 0000000000000000 c000000002c10000 c0000000000114d8 0000000000000000
> [ 0.669190][ T1] GPR16: 0000000000000000 0000000000000000 0000000000000000 0000000000000000
> [ 0.669190][ T1] GPR20: 0000000000000000 0000000000000000 0000000000000000 0000000000000000
> [ 0.669190][ T1] GPR24: 0000000000000000 c000000002003408 c0000000020b1070 c0000000021ecee0
> [ 0.669190][ T1] GPR28: 0000000000000000 0000000000000008 0000000000000000 c000000005836480
> [ 0.670393][ T1] NIP [c00000000201eb70] msi_bitmap_selftest+0x1c8/0x3f8
> [ 0.670499][ T1] LR [c00000000201eb68] msi_bitmap_selftest+0x1c0/0x3f8
> [ 0.670657][ T1] Call Trace:
> [ 0.670747][ T1] [c0000000037d7b70] [c00000000201eb68] msi_bitmap_selftest+0x1c0/0x3f8 (unreliable)
> [ 0.670941][ T1] [c0000000037d7c20] [c000000000010d9c] do_one_initcall+0x7c/0x37c
> [ 0.671085][ T1] [c0000000037d7d00] [c000000002004ba8] kernel_init_freeable+0x2fc/0x3cc
> [ 0.671218][ T1] [c0000000037d7dd0] [c0000000000114fc] kernel_init+0x2c/0x1b0
> [ 0.671336][ T1] [c0000000037d7e30] [c00000000000debc] ret_from_kernel_user_thread+0x14/0x1c
> [ 0.671479][ T1] ---- interrupt: 0 at 0x0
> [ 0.671777][ T1] Code: 38800001 38610068 4a162c61 54630ffe 0b030000 37deffff 4082ffe8 38800001 38610068 4a162c45 7c6318f8 54630ffe <0b030000> eba10070 7fdff378 3bde0001
> [ 0.672127][ T1] ---[ end trace 0000000000000000 ]---
> ...
>
>--
>Cheers,
>Nathan