From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail-dy1-f182.google.com (mail-dy1-f182.google.com [74.125.82.182]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 07B622DA749 for ; Tue, 30 Jun 2026 23:13:26 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=74.125.82.182 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1782861208; cv=none; b=QLbfAm/fw7Kqk0x0XC+luHU37YSZ+WW7bcX4PGJ1T9Maa3LP9fSgsiC9vX3Lz1tz4abCYykTIuKBzdwt72xHyc0dsXIFOvUs5RhUmq0X6ZlJj4Hx7ziaXihePEHA6D8b0wlHVA8xJSuQCFSyiPb+VJtcAwTuAOZ3QDwOhzHz7hQ= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1782861208; c=relaxed/simple; bh=E4guOqtfG7rxo1qMS6g4XcutMaE2gKP1vrum2ihNKkU=; h=From:Date:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=W2Dkfytlz1aPx1afwjqaSMsHj31Hn5pu6Zd0zMAeNnZ2+Nd0lke/ofx0ggvSrh6T463vRPf7sZXgUN4ekO8tdVJ0WMY+4ukHYxN5WXVWm/0xXqNQ+zGV1MLlXImVNpjf1hKBZW55qqb/WYxFzQQ8ysOgZBVrEFHoEetvZx0N4c0= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=SfrThHu+; arc=none smtp.client-ip=74.125.82.182 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="SfrThHu+" Received: by mail-dy1-f182.google.com with SMTP id 5a478bee46e88-30bc871ecdfso7021648eec.1 for ; Tue, 30 Jun 2026 16:13:26 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1782861206; x=1783466006; darn=vger.kernel.org; h=in-reply-to:content-disposition:content-type:mime-version :references:message-id:subject:cc:to:date:from:from:to:cc:subject :date:message-id:reply-to:content-type; bh=cnnxCEyMM62ZKyjnBatQpSMhFvECAyb7cubp4Idg+4A=; b=SfrThHu+mFB6k2+K7j/efZOOYxw62g/YX5Y/SAMU2meAmGCKgZCDs/3YtGKn2oxcNP UE8gnbmeqXngTfvfZJQrhg7HIQrNY36qHuFaIohyBQO3oSRp97CojOLMC/0hWfpx6tyx xAmebNSLry0xLMngExUYFINjTJdcgJUOFdr4E5DdBCM2/LMY2Bdhmnzb40vTNeB6s+qa OIhgqrsHKBrUAg+a+d9RmBqNTwOlaOwttjLnPwIA8iqCCx3KHafw4zdOEFfz/gfir7WQ BoQQyNTgRY7PYhI5550/6YRCrKPlcLzDpuF/jBqhAb/Koh41oj4Ti9R3M0Hk6N8GcpZt Eqaw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1782861206; x=1783466006; h=in-reply-to:content-disposition:content-type:mime-version :references:message-id:subject:cc:to:date:from:x-gm-gg :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to :content-type; bh=cnnxCEyMM62ZKyjnBatQpSMhFvECAyb7cubp4Idg+4A=; b=iJHv/jAafVvKos97MVLuuixODJdUft1eKy+TsNKOJwhL/9HYCQ3MlBC7WETO0gqc+X U0nU25NBjxoU79HllF5rfIaQDYmgZ0fmLBG3JZlDgNbuat+Ie7imRyuhTZQH+okRs9K0 80EREHvKq30XiC7bx8O0++icg+wqvHp5mAIfNVvxgBFqLRx1HUVck59QFJX4uAlQrgSF ZRJY2z5WVfE/PsDrlJfL8Dc8b4eUHrSZXzC/73TXsIubYiCb01hvFLjnCI5acO1MDEZw HLXwMknvEhBJdpARBWcEbt/epEliZV+96nMhvTqeYPi06Ae9fpB8VT/Dzm+9CVZs0bxr Emwg== X-Forwarded-Encrypted: i=1; AHgh+Rqzb0KH09G4Cxb9lizejNvpLRR71Ic+rUxRYDYlLvRe/IwHK50GvLucOId5UQ9W9XDC4u6IHkp6kLYspFg=@vger.kernel.org X-Gm-Message-State: AOJu0Yx5GQwd9xw1P7IYDzbs+aKgBJDyeoWl0jqCTILkoNU2vmvL0Xek C+Ns6I5FpQY41/NJtR5OKkA6AhEsMzrbDMnaknlWkO0hvS50VEv48dEU X-Gm-Gg: AfdE7cmEx9Fkp787xCGmS/nlkbeJWA4sMCU9YTwAS0mwVMcHEWlA/6L6WUItqc4P7wW 8xv3b6jZON/GsS7KznfyY8ewrMg8xGWyiHyEBfQbxkxBCjswMvwDANg+jbScfdEohIBWCcBX6vX YOLluGcyMgw4ta25S9yWV93IKQ6LdYOpTCUu1FKQMGg/CQIlTzwtyWz8GqDkfovwACEghH2c7l0 Qp2tBaFM96iUyHcU90VU6gFqWdkOlOM1oydgUZAbYHhLOW8I1ZWqr8CjY2VMNpVeSfAw4wxicVa ED4nH8S0diOpDylrEy+z9edHXo5904XZg49aFSkyMKVqIVEAMGfSfDPLr/1Lm/azsGOVIg3TBny GGCi5ut3+etxrgWzYIA6ieE21rdsxcHPqhexSdhvyloAuItrzHyxypwJi3OPzsOg9ljqlesxSIM OnAzubGWgr X-Received: by 2002:a05:7300:748f:b0:30c:ab4d:3824 with SMTP id 5a478bee46e88-30ee1507fc7mr3775645eec.38.1782861206000; Tue, 30 Jun 2026 16:13:26 -0700 (PDT) Received: from localhost ([216.228.127.129]) by smtp.gmail.com with ESMTPSA id 5a478bee46e88-30ee3205796sm15033048eec.23.2026.06.30.16.13.23 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 30 Jun 2026 16:13:25 -0700 (PDT) From: Yury Norov X-Google-Original-From: Yury Norov Date: Tue, 30 Jun 2026 19:13:20 -0400 To: Nathan Chancellor Cc: Yi Sun , 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: References: <20260622030036.1744080-1-yi.sun@unisoc.com> <20260622030036.1744080-3-yi.sun@unisoc.com> <20260630205240.GA921840@ax162> 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: <20260630205240.GA921840@ax162> 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 > > 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()"). 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 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