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

[Nathan Chancellor]

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