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

[Yury Norov <yury.norov@gmail.com>]

On Tue, Jun 30, 2026 at 01:52:40PM -0700, Nathan Chancellor wrote:
> 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@gmail.com>
> > Signed-off-by: Yury Norov <yury.norov@gmail.com>
> > Signed-off-by: Yi Sun <yi.sun@unisoc.com>
> 
> 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()").

Thanks Nathan, I'll drop it from -next for now.
 
>   $ 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
>   [    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