From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from smtp.kernel.org (aws-us-west-2-korg-mail-alma10-1.taild15c8.ts.net [100.103.45.18]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id E1AF13793C2 for ; Tue, 30 Jun 2026 20:52:45 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=100.103.45.18 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1782852767; cv=none; b=FueeCndJskLbdTnO67KGRml1W/13073SyBpfP2+oyhVGSQM3JRxyPcLqwNvG7vIa/RMH1lZagCufWUO4elN9qO3j/tCX+XVP7Z8IjDl9N7KAKDYYj08+YZZ08kIk188rgCq19QPQM8sAuRsSa83oiNO2rw5SPEnd5eLzn23vUow= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1782852767; c=relaxed/simple; bh=zkGx1NnssVGWNWJDgigQKq2KSvsXC4jXTgWGeaSjmhs=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=AsSujssIc0FCN+ScjxdeduJbiGvjYL/9HON/VP9ywsVD+qKeto3UIydpiWzHiVTuT2+Bpkr44QExcLN1uUJypbU/GmcXSP5SyFEIMRcoQ1UB6PajFFnhbvu5oAbuLkM2DRllEjct43XyvsFoJaoEyz6h4d+FtF+t6N/Wc7cLNio= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b=Bisfd1Yh; arc=none smtp.client-ip=100.103.45.18 Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b="Bisfd1Yh" Received: by smtp.kernel.org (Postfix) with ESMTPSA id CCD631F000E9; Tue, 30 Jun 2026 20:52:42 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=kernel.org; s=k20260515; t=1782852765; bh=Ef7nnvsIh2HzVmy/0JyQb5lkn+7pHyisr5/jkmpx0pA=; h=Date:From:To:Cc:Subject:References:In-Reply-To; b=Bisfd1Yhg3VGBO7ZL3TrvBqIICSAyGr/7ROqXi3Kyc93drAeWL+zj7x0vbTTwIEsN Qa10L3X3Yfmm5tbSVrabw12ytzn4jWVN4s6EHfPVQEm/TnLe/VfWuJKwQ5PFavH2EM PBjgF8qxw5U6lVjATdTGt6DSg3Zwa+g0lOjU1w22c2DWiuf539FflfhoGzr2ARDZSj K5n+kTbFTpa55cJYB1Zyqh36mGn40ju15OcwCKumpY5C0xTjMar4FUrEUWujdmoNP0 b0pir+QNZUSOJr1/r62Z7izcUwIvcigiqbRUie7jAVa5eq3wrvYYvdzpxW9PX4nhBO /aMaDZZH5GTuA== Date: Tue, 30 Jun 2026 13:52:40 -0700 From: Nathan Chancellor To: Yi Sun Cc: yury.norov@gmail.com, 279644543@qq.com, mina86@mina86.com, mnazarewicz@gmail.com, akpm@linux-foundation.org, akinobu.mita@gmail.com, linux-kernel@vger.kernel.org, tjmercier@google.com, fvdl@google.com, tglx@kernel.org, song@kernel.org, hch@lst.de, minchan@kernel.org, jstultz@google.com Subject: Re: [PATCH v7 2/2] lib: bitmap: optimize bitmap_find_next_zero_area_off() Message-ID: <20260630205240.GA921840@ax162> References: <20260622030036.1744080-1-yi.sun@unisoc.com> <20260622030036.1744080-3-yi.sun@unisoc.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20260622030036.1744080-3-yi.sun@unisoc.com> 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 > Signed-off-by: Yury Norov > Signed-off-by: Yi Sun 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 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