From nobody Fri Dec 19 07:19:30 2025 Received: from smtpout.efficios.com (smtpout.efficios.com [167.114.26.122]) (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 1C6EC1B29D2 for ; Fri, 30 Aug 2024 19:11:11 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=167.114.26.122 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1725045075; cv=none; b=Ne6fhehrKgQd5adtFvOa8puKxHfAE4iLi8Z0N5KlCmrMNRXKwkFaMc3MdYJ/I13WYT3jKuA5JBOHQdINKKhJ0AcCBfimjm2f7VEAoGdK3qfc7GB4yIxfLb6Y+psfQY2DhmjQ9Lsj2kwcFq9isasXGka01L0We74E2JWve5Px9hs= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1725045075; c=relaxed/simple; bh=AGFDpfa+bqvaKAyzR3i8XqMbzLG42VLnwzugz17jL9I=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=P7y64aWMUVIfX92CLeCMD654wBQl8SkHNNheor+odJBTEicLyVpIB+wI2qjW2O1QI0zQT1/UMZ0awRi+8lLTD0WQchxoDxhesWezlJfxiIYwHHV2+glIPfO4qrCPDudIYD6oIUbIS+cLXAcc98i+VloHHFG40Tn7Ktp3N4CmapY= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=efficios.com; spf=pass smtp.mailfrom=efficios.com; dkim=pass (2048-bit key) header.d=efficios.com header.i=@efficios.com header.b=nOZQ1YRY; arc=none smtp.client-ip=167.114.26.122 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=efficios.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=efficios.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=efficios.com header.i=@efficios.com header.b="nOZQ1YRY" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=efficios.com; s=smtpout1; t=1725045071; bh=AGFDpfa+bqvaKAyzR3i8XqMbzLG42VLnwzugz17jL9I=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=nOZQ1YRYxq0Zyyinb9H+IICCQLk+CV1rWnBJaasEXEdJHWNH1Rf+Z/COOh6oHqERh j/TDngwVcSiTLh5I30v7H4y5UxiuuRsG2V5fJfGfC3c6/I9WurOoRer8pA9Q1TR7eW Posir0GrAycxafyiZR9edZVEAr6x+EPWtppR7yk49dJ04HMUf+wd6kMx4YYUw8WBLD pu8EZD/QOx/0AWj4SowkLaZrVS7LBe5lUg4V75mXwn03Y2GOsDnh1wdG4D4pbvjYEW /3nhPq3TObH9VGPKZTxGB9LYZjhUaRCHNxthuDeyLlRxusu0Gicrr//SqxLPOEbqR7 PvPd01SB4iTJQ== Received: from thinkos.internal.efficios.com (96-127-217-162.qc.cable.ebox.net [96.127.217.162]) by smtpout.efficios.com (Postfix) with ESMTPSA id 4WwSRf6f4qz1Jjy; Fri, 30 Aug 2024 15:11:10 -0400 (EDT) From: Mathieu Desnoyers To: Yury Norov , Rasmus Villemoes Cc: linux-kernel@vger.kernel.org, Mathieu Desnoyers Subject: [PATCH v3 1/6] lib: Clarify comment on top of find_next_andnot_bit Date: Fri, 30 Aug 2024 15:10:38 -0400 Message-Id: <20240830191043.1028827-2-mathieu.desnoyers@efficios.com> X-Mailer: git-send-email 2.39.2 In-Reply-To: <20240830191043.1028827-1-mathieu.desnoyers@efficios.com> References: <20240830191043.1028827-1-mathieu.desnoyers@efficios.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Make the comment on top of find_next_andnot_bit clearer by discussing in terms of "cleared bits" rather than "excluding bits". Signed-off-by: Mathieu Desnoyers Acked-by: Yury Norov Cc: Yury Norov Cc: Rasmus Villemoes --- include/linux/find.h | 7 +++---- 1 file changed, 3 insertions(+), 4 deletions(-) diff --git a/include/linux/find.h b/include/linux/find.h index 5dfca4225fef..8a170aa55634 100644 --- a/include/linux/find.h +++ b/include/linux/find.h @@ -102,15 +102,14 @@ unsigned long find_next_and_bit(const unsigned long *= addr1, =20 #ifndef find_next_andnot_bit /** - * find_next_andnot_bit - find the next set bit in *addr1 excluding all th= e bits - * in *addr2 + * find_next_andnot_bit - find the next set bit in *addr1, cleared in *add= r2 * @addr1: The first address to base the search on * @addr2: The second address to base the search on * @size: The bitmap size in bits * @offset: The bitnumber to start searching at * - * Returns the bit number for the next set bit - * If no bits are set, returns @size. + * Returns the bit number for the next bit set in *addr1, cleared in *addr= 2. + * If no such bits are found, returns @size. */ static inline unsigned long find_next_andnot_bit(const unsigned long *addr1, --=20 2.39.2 From nobody Fri Dec 19 07:19:30 2025 Received: from smtpout.efficios.com (smtpout.efficios.com [167.114.26.122]) (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 46EA51BA281 for ; Fri, 30 Aug 2024 19:11:12 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=167.114.26.122 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1725045075; cv=none; b=C+32r084KzNphA5ol15gvtlnUR7quJwMvj16B/AaqlzuRmVug4lDQl8clAtLm+OrRgsCgss1396nbtu9hzFcW3OfXjlW5FXKJnoHoCEAZRa/IBLBy3NeTn1drXeU8ilfpcU0AGl9Otge8i6YZhm/jExMzcpNV3K4UPXDNWfXpvs= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1725045075; c=relaxed/simple; bh=33t8IWbFnlxFx2ACGJktspProS/MnEs4WbGTgYyL254=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=CNuENDges8y8EwBnUBg7iypktzqZqgFU4W4wzj0IjYXla6hqm8boS85a+/ZvKZU9oBYV0IfBWCfPq0kwB5aEGlsjsJy9Bjrl2tgMqes9MieoZgOO+zG409bfIZGuXsrlfgUAoULeU+tXgd7PYusmmYnhB/VHj/0TFxHfWpDS860= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=efficios.com; spf=pass smtp.mailfrom=efficios.com; dkim=pass (2048-bit key) header.d=efficios.com header.i=@efficios.com header.b=rudIMeqe; arc=none smtp.client-ip=167.114.26.122 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=efficios.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=efficios.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=efficios.com header.i=@efficios.com header.b="rudIMeqe" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=efficios.com; s=smtpout1; t=1725045071; bh=33t8IWbFnlxFx2ACGJktspProS/MnEs4WbGTgYyL254=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=rudIMeqeuf9SF3Oo6sJX4XhuRkp7cRRT3o0IffdUQh5Ksrv41GMO1yB7O7Oy3cdmu BE5Xap/ZRclLyg7dVLBC78iL5bv7ohFjJxPklLSacsXLW6O3+FK7ONyzAd/FqgpMIk 9mhOsTToLxtlQVYAURW9stzpmo9EOY1ywBmcTxpIwbqi9jMpq55x0ACJzYxsHP0wO5 zZ6Aq1Pv0q7nLtWGFW6tPEJFBnTq3I6C1rxm0rODymuaEkV9LJAhbIbbg8B6ZLJ5yC WzlO2iHk4mVsXAkwmEP/pXR1kliFsAn9QH5KxHztjVp3kONnrGLt0WR8kcAURAboZL ZCxGT7IcBGbag== Received: from thinkos.internal.efficios.com (96-127-217-162.qc.cable.ebox.net [96.127.217.162]) by smtpout.efficios.com (Postfix) with ESMTPSA id 4WwSRg0tLWz1Jk0; Fri, 30 Aug 2024 15:11:11 -0400 (EDT) From: Mathieu Desnoyers To: Yury Norov , Rasmus Villemoes Cc: linux-kernel@vger.kernel.org, Mathieu Desnoyers Subject: [PATCH v3 2/6] lib: Implement find_{first,next,nth}_nor_bit, for_each_nor_bit, find_first_andnot_bit Date: Fri, 30 Aug 2024 15:10:39 -0400 Message-Id: <20240830191043.1028827-3-mathieu.desnoyers@efficios.com> X-Mailer: git-send-email 2.39.2 In-Reply-To: <20240830191043.1028827-1-mathieu.desnoyers@efficios.com> References: <20240830191043.1028827-1-mathieu.desnoyers@efficios.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Allow finding the first, next, or nth bit within two input bitmasks which is zero in both masks. Allow fiding the first bit within two input bitmasks which is set in first mask and cleared in the second mask. find_next_andnot_bit and find_nth_andnot_bit already exist, so find the first bit appears to be missing. Signed-off-by: Mathieu Desnoyers Acked-by: Yury Norov Cc: Yury Norov Cc: Rasmus Villemoes --- Changes since v0: - Rename "notandnot" to "nor", document equivalence. - Move comment cleanups to a separate patch. - Use __always_inline. Changes since v1: - Introduce for_each_nor_bit. Changes since v2: - Remove extern. --- include/linux/find.h | 117 +++++++++++++++++++++++++++++++++++++++++++ lib/find_bit.c | 36 +++++++++++++ 2 files changed, 153 insertions(+) diff --git a/include/linux/find.h b/include/linux/find.h index 8a170aa55634..d47591e6c999 100644 --- a/include/linux/find.h +++ b/include/linux/find.h @@ -14,6 +14,8 @@ unsigned long _find_next_and_bit(const unsigned long *add= r1, const unsigned long unsigned long nbits, unsigned long start); unsigned long _find_next_andnot_bit(const unsigned long *addr1, const unsi= gned long *addr2, unsigned long nbits, unsigned long start); +unsigned long _find_next_nor_bit(const unsigned long *addr1, const unsigne= d long *addr2, + unsigned long nbits, unsigned long start); unsigned long _find_next_or_bit(const unsigned long *addr1, const unsigned= long *addr2, unsigned long nbits, unsigned long start); unsigned long _find_next_zero_bit(const unsigned long *addr, unsigned long= nbits, @@ -24,11 +26,17 @@ unsigned long __find_nth_and_bit(const unsigned long *a= ddr1, const unsigned long unsigned long size, unsigned long n); unsigned long __find_nth_andnot_bit(const unsigned long *addr1, const unsi= gned long *addr2, unsigned long size, unsigned long n); +unsigned long __find_nth_nor_bit(const unsigned long *addr1, const unsigne= d long *addr2, + unsigned long size, unsigned long n); unsigned long __find_nth_and_andnot_bit(const unsigned long *addr1, const = unsigned long *addr2, const unsigned long *addr3, unsigned long size, unsigned long n); extern unsigned long _find_first_and_bit(const unsigned long *addr1, const unsigned long *addr2, unsigned long size); +unsigned long _find_first_andnot_bit(const unsigned long *addr1, + const unsigned long *addr2, unsigned long size); +unsigned long _find_first_nor_bit(const unsigned long *addr1, + const unsigned long *addr2, unsigned long size); unsigned long _find_first_and_and_bit(const unsigned long *addr1, const un= signed long *addr2, const unsigned long *addr3, unsigned long size); extern unsigned long _find_first_zero_bit(const unsigned long *addr, unsig= ned long size); @@ -130,6 +138,35 @@ unsigned long find_next_andnot_bit(const unsigned long= *addr1, } #endif =20 +/** + * find_next_nor_bit - find the next bit cleared in both *addr1 and *addr2 + * @addr1: The first address to base the search on + * @addr2: The second address to base the search on + * @size: The bitmap size in bits + * @offset: The bitnumber to start searching at + * + * Returns the bit number for the next bit cleared in both *addr1 and *add= r2. + * If no such bits are found, returns @size. + * The bitwise operation nor ~(A | B) is equivalent to (~A & ~B). + */ +static __always_inline +unsigned long find_next_nor_bit(const unsigned long *addr1, + const unsigned long *addr2, unsigned long size, + unsigned long offset) +{ + if (small_const_nbits(size)) { + unsigned long val; + + if (unlikely(offset >=3D size)) + return size; + + val =3D ~(*addr1 | *addr2) & GENMASK(size - 1, offset); + return val ? __ffs(val) : size; + } + + return _find_next_nor_bit(addr1, addr2, size, offset); +} + #ifndef find_next_or_bit /** * find_next_or_bit - find the next set bit in either memory regions @@ -291,6 +328,33 @@ unsigned long find_nth_andnot_bit(const unsigned long = *addr1, const unsigned lon return __find_nth_andnot_bit(addr1, addr2, size, n); } =20 +/** + * find_nth_nor_bit - find N'th cleared bit in 2 memory regions. + * @addr1: The 1st address to start the search at + * @addr2: The 2nd address to start the search at + * @size: The maximum number of bits to search + * @n: The number of set bit, which position is needed, counting from 0 + * + * Returns the bit number of the N'th bit cleared in the two regions. + * If no such, returns @size. + * The bitwise operation nor ~(A | B) is equivalent to (~A & ~B). + */ +static __always_inline +unsigned long find_nth_nor_bit(const unsigned long *addr1, const unsigned = long *addr2, + unsigned long size, unsigned long n) +{ + if (n >=3D size) + return size; + + if (small_const_nbits(size)) { + unsigned long val =3D ~(*addr1 | *addr2) & GENMASK(size - 1, 0); + + return val ? fns(val, n) : size; + } + + return __find_nth_nor_bit(addr1, addr2, size, n); +} + /** * find_nth_and_andnot_bit - find N'th set bit in 2 memory regions, * excluding those set in 3rd region @@ -346,6 +410,54 @@ unsigned long find_first_and_bit(const unsigned long *= addr1, } #endif =20 +/** + * find_first_andnot_bit - find the first set bit in 2 memory regions, + * flipping bits in 2nd region. + * @addr1: The first address to base the search on + * @addr2: The second address to base the search on + * @size: The bitmap size in bits + * + * Returns the bit number for the next set bit. + * If no bits are set, returns @size. + */ +static __always_inline +unsigned long find_first_andnot_bit(const unsigned long *addr1, + const unsigned long *addr2, + unsigned long size) +{ + if (small_const_nbits(size)) { + unsigned long val =3D *addr1 & (~*addr2) & GENMASK(size - 1, 0); + + return val ? __ffs(val) : size; + } + + return _find_first_andnot_bit(addr1, addr2, size); +} + +/** + * find_first_nor_bit - find the first cleared bit in 2 memory regions + * @addr1: The first address to base the search on + * @addr2: The second address to base the search on + * @size: The bitmap size in bits + * + * Returns the bit number for the next cleared bit. + * If no bits are set, returns @size. + * The bitwise operation nor ~(A | B) is equivalent to (~A & ~B). + */ +static __always_inline +unsigned long find_first_nor_bit(const unsigned long *addr1, + const unsigned long *addr2, + unsigned long size) +{ + if (small_const_nbits(size)) { + unsigned long val =3D ~(*addr1 | *addr2) & GENMASK(size - 1, 0); + + return val ? __ffs(val) : size; + } + + return _find_first_nor_bit(addr1, addr2, size); +} + /** * find_first_and_and_bit - find the first set bit in 3 memory regions * @addr1: The first address to base the search on @@ -594,6 +706,11 @@ unsigned long find_next_bit_le(const void *addr, unsig= ned (bit) =3D find_next_andnot_bit((addr1), (addr2), (size), (bit)), (bi= t) < (size);\ (bit)++) =20 +#define for_each_nor_bit(bit, addr1, addr2, size) \ + for ((bit) =3D 0; \ + (bit) =3D find_next_nor_bit((addr1), (addr2), (size), (bit)), (bit) = < (size);\ + (bit)++) + #define for_each_or_bit(bit, addr1, addr2, size) \ for ((bit) =3D 0; \ (bit) =3D find_next_or_bit((addr1), (addr2), (size), (bit)), (bit) <= (size);\ diff --git a/lib/find_bit.c b/lib/find_bit.c index 0836bb3d76c5..8050bc7c7ede 100644 --- a/lib/find_bit.c +++ b/lib/find_bit.c @@ -116,6 +116,28 @@ unsigned long _find_first_and_bit(const unsigned long = *addr1, EXPORT_SYMBOL(_find_first_and_bit); #endif =20 +/* + * Find the first set bit in two memory regions, flipping bits in 2nd regi= on. + */ +unsigned long _find_first_andnot_bit(const unsigned long *addr1, + const unsigned long *addr2, + unsigned long size) +{ + return FIND_FIRST_BIT(addr1[idx] & ~addr2[idx], /* nop */, size); +} +EXPORT_SYMBOL(_find_first_andnot_bit); + +/* + * Find the first cleared bit in two memory regions. + */ +unsigned long _find_first_nor_bit(const unsigned long *addr1, + const unsigned long *addr2, + unsigned long size) +{ + return FIND_FIRST_BIT(~(addr1[idx] | addr2[idx]), /* nop */, size); +} +EXPORT_SYMBOL(_find_first_nor_bit); + /* * Find the first set bit in three memory regions. */ @@ -167,6 +189,13 @@ unsigned long __find_nth_andnot_bit(const unsigned lon= g *addr1, const unsigned l } EXPORT_SYMBOL(__find_nth_andnot_bit); =20 +unsigned long __find_nth_nor_bit(const unsigned long *addr1, const unsigne= d long *addr2, + unsigned long size, unsigned long n) +{ + return FIND_NTH_BIT(~(addr1[idx] | addr2[idx]), size, n); +} +EXPORT_SYMBOL(__find_nth_nor_bit); + unsigned long __find_nth_and_andnot_bit(const unsigned long *addr1, const unsigned long *addr2, const unsigned long *addr3, @@ -194,6 +223,13 @@ unsigned long _find_next_andnot_bit(const unsigned lon= g *addr1, const unsigned l EXPORT_SYMBOL(_find_next_andnot_bit); #endif =20 +unsigned long _find_next_nor_bit(const unsigned long *addr1, const unsigne= d long *addr2, + unsigned long nbits, unsigned long start) +{ + return FIND_NEXT_BIT(~(addr1[idx] | addr2[idx]), /* nop */, nbits, start); +} +EXPORT_SYMBOL(_find_next_nor_bit); + #ifndef find_next_or_bit unsigned long _find_next_or_bit(const unsigned long *addr1, const unsigned= long *addr2, unsigned long nbits, unsigned long start) --=20 2.39.2 From nobody Fri Dec 19 07:19:30 2025 Received: from smtpout.efficios.com (smtpout.efficios.com [167.114.26.122]) (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 46E491B375E for ; Fri, 30 Aug 2024 19:11:12 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=167.114.26.122 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1725045074; cv=none; b=bCWAFhqThCM0P5eNT5tFly68aT9ZfbfvLlv8HOsdpxZP3w4qp2y3/rmWKkqJ67UaU+JRGGHfHeLAJyGlVncZY67UZcIuAJcDb/HTGjp82tatQ88mRQJc6IgbM74nT50qV6IPIsXGYT7PkXlserd/hGFK0nLYugKm5LWsWiCBEVI= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1725045074; c=relaxed/simple; bh=mSlbGJz8j44ZPE+sDl5Lu+E4GWu7DyDgzRUR10EQ6Ys=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=GwCMAxOa51iKZzVvKYk18MBxneWbyv/3t/nGaXmIpWW3aNUza+5Sec2N8bXCJ+UhHevoZCYBclx0x7VqhRuV6dVCYhfc6mIQLgG9PGnoshW3QL5VfgZSRFZn0KjOqaiycdwFMUqFot3Y9AOTIVfJhyH0nUe/uhBELu4KqZLwsiA= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=efficios.com; spf=pass smtp.mailfrom=efficios.com; dkim=pass (2048-bit key) header.d=efficios.com header.i=@efficios.com header.b=JHTSylWx; arc=none smtp.client-ip=167.114.26.122 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=efficios.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=efficios.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=efficios.com header.i=@efficios.com header.b="JHTSylWx" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=efficios.com; s=smtpout1; t=1725045071; bh=mSlbGJz8j44ZPE+sDl5Lu+E4GWu7DyDgzRUR10EQ6Ys=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=JHTSylWxBG4FVA3RizCacwvwEbALeTW+cfabR3VlpeOFXPSNpouIRx5VKqJI7EvvK nNhkcGvZawaANoXaWttpemdCnQcVDmWt7KUTZziLocBRg6TEmkCM4UUprUHs1sHLjs LCcrRGgzn5PjaVg/rydbSE0EO9rOwISneJPbH37jI26VF/Rhjr1OzVriFp2PtoXZ3M 44hHkJGSsGSH+1/wN4PszivZRa3kmoIZZrE/ZN9Uddxeop+1nQOBz9+/dJv8tnEN56 1VFcduGSmWCRrBE5kxH0bke73Sy4TzELeaDaPfGvBL6YQiNw6d9u2eAaZOST+QtMoq +7LdrMtj39YJw== Received: from thinkos.internal.efficios.com (96-127-217-162.qc.cable.ebox.net [96.127.217.162]) by smtpout.efficios.com (Postfix) with ESMTPSA id 4WwSRg284Zz1Jk1; Fri, 30 Aug 2024 15:11:11 -0400 (EDT) From: Mathieu Desnoyers To: Yury Norov , Rasmus Villemoes Cc: linux-kernel@vger.kernel.org, Mathieu Desnoyers Subject: [PATCH v3 3/6] lib: test bitmap sets binary operation iterators Date: Fri, 30 Aug 2024 15:10:40 -0400 Message-Id: <20240830191043.1028827-4-mathieu.desnoyers@efficios.com> X-Mailer: git-send-email 2.39.2 In-Reply-To: <20240830191043.1028827-1-mathieu.desnoyers@efficios.com> References: <20240830191043.1028827-1-mathieu.desnoyers@efficios.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Test the following bitmap iterators applying binary operations on sets of two bitmaps: - for_each_and_bit, - for_each_andnot_bit, - for_each_nor_bit, - for_each_or_bit. Signed-off-by: Mathieu Desnoyers Cc: Yury Norov Cc: Rasmus Villemoes --- lib/test_bitmap.c | 81 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 81 insertions(+) diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c index 6dfb8d46a4ff..96ce3c78c7fa 100644 --- a/lib/test_bitmap.c +++ b/lib/test_bitmap.c @@ -184,6 +184,32 @@ __check_eq_str(const char *srcfile, unsigned int line, result; \ }) =20 +static bool __init +__check_neq_range_ulong(const char *srcfile, unsigned int line, + const unsigned long exp_ulong_begin, + const unsigned long exp_ulong_end, + unsigned long x) +{ + if (exp_ulong_begin <=3D x && exp_ulong_end >=3D x) { + pr_err("[%s:%u] did not value %lu within range [%lu,%lu]\n", + srcfile, line, x, exp_ulong_begin, exp_ulong_end); + return false; + } + return true; +} + +#define __expect_neq_range(suffix, ...) \ + ({ \ + int result =3D 0; \ + total_tests++; \ + if (!__check_neq_range_ ## suffix(__FILE__, __LINE__, \ + ##__VA_ARGS__)) { \ + failed_tests++; \ + result =3D 1; \ + } \ + result; \ + }) + #define expect_eq_ulong(...) __expect_eq(ulong, ##__VA_ARGS__) #define expect_eq_uint(x, y) expect_eq_ulong((unsigned int)(x), (unsigned= int)(y)) #define expect_eq_bitmap(...) __expect_eq(bitmap, ##__VA_ARGS__) @@ -192,6 +218,9 @@ __check_eq_str(const char *srcfile, unsigned int line, #define expect_eq_clump8(...) __expect_eq(clump8, ##__VA_ARGS__) #define expect_eq_str(...) __expect_eq(str, ##__VA_ARGS__) =20 +#define expect_neq_range_ulong(...) __expect_neq_range(ulong, ##__VA_ARGS= __) +#define expect_neq_range_uint(begin, end, y) expect_neq_range_ulong((unsig= ned int)(begin), (unsigned int) end, (unsigned int)(y)) + static void __init test_zero_clear(void) { DECLARE_BITMAP(bmap, 1024); @@ -849,6 +878,57 @@ static void __init test_for_each_set_bit(void) expect_eq_bitmap(orig, copy, 500); } =20 +static void __init test_for_each_binaryops_bit(void) +{ + DECLARE_BITMAP(orig1, 500); + DECLARE_BITMAP(orig2, 500); + unsigned int bit, count; + + bitmap_zero(orig1, 500); + bitmap_zero(orig2, 500); + + /* Set individual bits in orig1 and orig2 with stride 10 (expected in bot= h orig1 & orig2) */ + for (bit =3D 0; bit < 500; bit +=3D 10) { + bitmap_set(orig1, bit, 1); + bitmap_set(orig2, bit, 1); + } + /* Set individual bits in orig1 with offset 1, stride 10 (expected in ori= g1 only) */ + for (bit =3D 1; bit < 500; bit +=3D 10) + bitmap_set(orig1, bit, 1); + /* Set individual bits in orig2 with offset 2, stride 10 (expected in ori= g2 only). */ + for (bit =3D 2; bit < 500; bit +=3D 10) + bitmap_set(orig2, bit, 1); + + count =3D 0; + for_each_and_bit(bit, orig1, orig2, 500) { /* orig1 & orig2 */ + expect_neq_range_uint(1, 9, bit % 10); + count++; + } + expect_eq_uint(50, count); + + count =3D 0; + for_each_andnot_bit(bit, orig1, orig2, 500) { /* orig1 & ~orig2 */ + expect_neq_range_uint(0, 0, bit % 10); + expect_neq_range_uint(2, 9, bit % 10); + count++; + } + expect_eq_uint(50, count); + + count =3D 0; + for_each_nor_bit(bit, orig1, orig2, 500) { /* ~(orig1 | orig2) */ + expect_neq_range_uint(0, 2, bit % 10); + count++; + } + expect_eq_uint(7 * 50, count); + + count =3D 0; + for_each_or_bit(bit, orig1, orig2, 500) { /* orig1 | orig2 */ + expect_neq_range_uint(3, 9, bit % 10); + count++; + } + expect_eq_uint(3 * 50, count); +} + static void __init test_for_each_set_bit_from(void) { DECLARE_BITMAP(orig, 500); @@ -1482,6 +1562,7 @@ static void __init selftest(void) test_for_each_clear_bitrange_from(); test_for_each_set_clump8(); test_for_each_set_bit_wrap(); + test_for_each_binaryops_bit(); } =20 KSTM_MODULE_LOADERS(test_bitmap); --=20 2.39.2 From nobody Fri Dec 19 07:19:30 2025 Received: from smtpout.efficios.com (smtpout.efficios.com [167.114.26.122]) (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 825D61BAEDE for ; Fri, 30 Aug 2024 19:11:12 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=167.114.26.122 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1725045074; cv=none; b=WZrP764k73C23DCeNZhCl8Gxpa/3R9YrQlPgVQtzUvIPZfyDsJqk9DyL9sRl/feZpyrUG/n7+kuklOvjYWG5mW32yl6OTRIx1/sMkev/FIFQUIo9Gr9maqESxJskwVs6pPlkTxm525XQtIu8beZx9bQiOF8h1Vp4uW6b82yVY1c= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1725045074; c=relaxed/simple; bh=9Uj3/VQbpr4+TFsjkAbUH7PZHPe4UnTPFjOJXxx1hRg=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=gy6comGRRrPgFlWTpj8wWGK8nZK63Fbopz1TiHTuYUAfqc88+HkFRhpAnyvaY7UjddUDhVB8GtkQnWqwe0rHe63GsjLxqqbwBw3HnlcZpS/jEX8okUtlDH1gSYroY5O5QlRIO3o3R32dXCOoa+u9b7ZjIOmxC6wn0ee+fuSRlnY= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=efficios.com; spf=pass smtp.mailfrom=efficios.com; dkim=pass (2048-bit key) header.d=efficios.com header.i=@efficios.com header.b=dwsVbZJj; arc=none smtp.client-ip=167.114.26.122 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=efficios.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=efficios.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=efficios.com header.i=@efficios.com header.b="dwsVbZJj" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=efficios.com; s=smtpout1; t=1725045071; bh=9Uj3/VQbpr4+TFsjkAbUH7PZHPe4UnTPFjOJXxx1hRg=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=dwsVbZJj8Z42vlgUtBZvDqHWtYsRctUT99FsG0b2sh2D8H2KiHofU8caGSA4SUqt0 gt13WE942927nOvca7ejEU3r++DarBCIrdpWmARj0dHjZ4NKDmr8bGIdYfOdM0y1L+ Z515MQGN8B9oLBCrLgj56onoeDycoesTVqniyUCbf9a8fB9Qsalv6lvFJPYuEr46OJ xwvKosS+A/1GX7UnRieWQvRLHcKyPQH0kl4NS/B+AO6igzvYWr0mg6sLw9vhgYX6U5 iykLkhoPPvqFakA97vnycB7KUmmQqExF8vlQm8wEM9AhZg36jHfChXb4vwTK1uhk30 JU5ujdsXsl2Xw== Received: from thinkos.internal.efficios.com (96-127-217-162.qc.cable.ebox.net [96.127.217.162]) by smtpout.efficios.com (Postfix) with ESMTPSA id 4WwSRg3NvPz1Jk2; Fri, 30 Aug 2024 15:11:11 -0400 (EDT) From: Mathieu Desnoyers To: Yury Norov , Rasmus Villemoes Cc: linux-kernel@vger.kernel.org, Mathieu Desnoyers Subject: [PATCH v3 4/6] lib: Fix test_find_first_and_bit and test_find_next_and_bit benchmark Date: Fri, 30 Aug 2024 15:10:41 -0400 Message-Id: <20240830191043.1028827-5-mathieu.desnoyers@efficios.com> X-Mailer: git-send-email 2.39.2 In-Reply-To: <20240830191043.1028827-1-mathieu.desnoyers@efficios.com> References: <20240830191043.1028827-1-mathieu.desnoyers@efficios.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Modify test_find_first_bit so it modifies a local copy of bitmap rather than modifying the input bitmap, which removes the requirement of placing it last in the tests. Calls to test_find_first_and_bit and test_find_next_and_bit are placed after test_find_first_bit, which makes them use a bitmap entirely filled rather than the expected bitmap (random-filled or sparse). Use bitmap_alloc rather than a local static variable in test_find_first_bit and test_find_first_and_bit. Only clear bits when find bit returns a value within range, which causes an out-of-bound access otherwise. Use BITMAP_LEN / 10 for all find_first tests to ensure they run within a few ms each. Signed-off-by: Mathieu Desnoyers Cc: Yury Norov Cc: Rasmus Villemoes --- Changes since v2: - Use bitmap_alloc rather than a local static variable in test_find_first_b= it and test_find_first_and_bit. - Use BITMAP_LEN / 10 for all find_first tests. - Use len parameter rather than BITMAP_LEN. - Only clear bits when find bit returns a value within range. --- lib/find_bit_benchmark.c | 24 ++++++++++++++---------- 1 file changed, 14 insertions(+), 10 deletions(-) diff --git a/lib/find_bit_benchmark.c b/lib/find_bit_benchmark.c index d3fb09e6eff1..81d358fb459b 100644 --- a/lib/find_bit_benchmark.c +++ b/lib/find_bit_benchmark.c @@ -30,18 +30,21 @@ static DECLARE_BITMAP(bitmap, BITMAP_LEN) __initdata; static DECLARE_BITMAP(bitmap2, BITMAP_LEN) __initdata; =20 /* - * This is Schlemiel the Painter's algorithm. It should be called after - * all other tests for the same bitmap because it sets all bits of bitmap = to 1. + * This is Schlemiel the Painter's algorithm. */ static int __init test_find_first_bit(void *bitmap, unsigned long len) { + unsigned long *cp __free(bitmap) =3D bitmap_alloc(len, GFP_KERNEL); unsigned long i, cnt; ktime_t time; =20 + bitmap_copy(cp, bitmap, len); + time =3D ktime_get(); for (cnt =3D i =3D 0; i < len; cnt++) { - i =3D find_first_bit(bitmap, len); - __clear_bit(i, bitmap); + i =3D find_first_bit(cp, len); + if (i < len) + __clear_bit(i, cp); } time =3D ktime_get() - time; pr_err("find_first_bit: %18llu ns, %6ld iterations\n", time, cnt); @@ -51,16 +54,17 @@ static int __init test_find_first_bit(void *bitmap, uns= igned long len) =20 static int __init test_find_first_and_bit(void *bitmap, const void *bitmap= 2, unsigned long len) { - static DECLARE_BITMAP(cp, BITMAP_LEN) __initdata; + unsigned long *cp __free(bitmap) =3D bitmap_alloc(len, GFP_KERNEL); unsigned long i, cnt; ktime_t time; =20 - bitmap_copy(cp, bitmap, BITMAP_LEN); + bitmap_copy(cp, bitmap, len); =20 time =3D ktime_get(); for (cnt =3D i =3D 0; i < len; cnt++) { i =3D find_first_and_bit(cp, bitmap2, len); - __clear_bit(i, cp); + if (i < len) + __clear_bit(i, cp); } time =3D ktime_get() - time; pr_err("find_first_and_bit: %18llu ns, %6ld iterations\n", time, cnt); @@ -165,7 +169,7 @@ static int __init find_bit_test(void) * traverse only part of bitmap to avoid soft lockup. */ test_find_first_bit(bitmap, BITMAP_LEN / 10); - test_find_first_and_bit(bitmap, bitmap2, BITMAP_LEN / 2); + test_find_first_and_bit(bitmap, bitmap2, BITMAP_LEN / 10); test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN); =20 pr_err("\nStart testing find_bit() with sparse bitmap\n"); @@ -182,8 +186,8 @@ static int __init find_bit_test(void) test_find_next_zero_bit(bitmap, BITMAP_LEN); test_find_last_bit(bitmap, BITMAP_LEN); test_find_nth_bit(bitmap, BITMAP_LEN); - test_find_first_bit(bitmap, BITMAP_LEN); - test_find_first_and_bit(bitmap, bitmap2, BITMAP_LEN); + test_find_first_bit(bitmap, BITMAP_LEN / 10); + test_find_first_and_bit(bitmap, bitmap2, BITMAP_LEN / 10); test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN); =20 /* --=20 2.39.2 From nobody Fri Dec 19 07:19:30 2025 Received: from smtpout.efficios.com (smtpout.efficios.com [167.114.26.122]) (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 C77E81BD02C for ; Fri, 30 Aug 2024 19:11:14 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=167.114.26.122 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1725045076; cv=none; b=OGTkEuR0OOBMjB+oNQLB/xZHgPoEVdW65SB0P0S84Mm98T4lz1jyq3afHjAFpljiQRxP7GkPMSGxSahtFzcCyoLyK/3nU88DLDqg6XfusjzyiMffq1Ww2OQNQ9DpR1rXfVDu7+L+3g5gi4i8msAL88Yxu7Su7M/TQZvxeftFSsU= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1725045076; c=relaxed/simple; bh=aePfiYTeMyAz3U6m1iQCHycP01bwRNlRPeuv8aAmuQM=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=fhhYZVkqUZH04sERZ8nYkDFFMoCcs59Z46fjKtidFGUiD35N2KsGww2ptJrGClfQ0yjL1VIRnhDWMXtXhUJjml16yRY6X/01J6qpMiqzenedaqrEoPXLkMSv9SMv5NqV0R822c02DMhXH8VHSk7Z6GbbgTNHqmDr7zLQrJj4R9Y= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=efficios.com; spf=pass smtp.mailfrom=efficios.com; dkim=pass (2048-bit key) header.d=efficios.com header.i=@efficios.com header.b=aySvJyyr; arc=none smtp.client-ip=167.114.26.122 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=efficios.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=efficios.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=efficios.com header.i=@efficios.com header.b="aySvJyyr" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=efficios.com; s=smtpout1; t=1725045071; bh=aePfiYTeMyAz3U6m1iQCHycP01bwRNlRPeuv8aAmuQM=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=aySvJyyr+BHJ7I3/8TV+GoS/gxRqotbiocx22bJQ6AYhluXQmdFu7nR4BPaifyoSk UkBaUvK9x+zaOxryJTLH0PODEZ8LgEY08obwG3e32qrEeJtZjWZBLlSC15XUOsdLaG BBgnN24iqVv+z+3nUYG9Q64spJYouMJ7524wD1Zf50M2OpBgHHYpz1wGBYQKkBoHWp 6uHLc+3uITYQcUgACbkNlXu7KzK6JsmOpu7YvPqVtM9nWoUlN+Rl6jhUZlUMirq+B1 HSyWAUqYIvxKgpsOvodTUHKdtFx9txq4RCPsijHyb7tidJzd43zfSxmF8wOjEaVjWu gQfzL8ANJ6KpA== Received: from thinkos.internal.efficios.com (96-127-217-162.qc.cable.ebox.net [96.127.217.162]) by smtpout.efficios.com (Postfix) with ESMTPSA id 4WwSRg4d08z1Jk3; Fri, 30 Aug 2024 15:11:11 -0400 (EDT) From: Mathieu Desnoyers To: Yury Norov , Rasmus Villemoes Cc: linux-kernel@vger.kernel.org, Mathieu Desnoyers Subject: [PATCH v3 5/6] lib: benchmark bitmap sets binary operation find Date: Fri, 30 Aug 2024 15:10:42 -0400 Message-Id: <20240830191043.1028827-6-mathieu.desnoyers@efficios.com> X-Mailer: git-send-email 2.39.2 In-Reply-To: <20240830191043.1028827-1-mathieu.desnoyers@efficios.com> References: <20240830191043.1028827-1-mathieu.desnoyers@efficios.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Benchmark the following bitmap find functions applying binary operations on sets of two bitmaps: - find_first_andnot_bit, - find_first_nor_bit, - find_next_andnot_bit, - find_next_nor_bit, - find_next_or_bit. Note that find_first_or_bit is not part of the current API, so it is not covered. Use "len" parameters rather than BITMAP_LEN within all benchmark functions (changed across the whole file). Example output: (AMD EPYC 9654 96-Core Processor) Start testing find_bit() with random-filled bitmap find_next_bit: 595816 ns, 163603 iterations find_next_zero_bit: 613227 ns, 164078 iterations find_last_bit: 464619 ns, 163602 iterations find_nth_bit: 2647830 ns, 16413 iterations find_first_bit: 1240485 ns, 16414 iterations find_first_and_bit: 623258 ns, 8136 iterations find_next_and_bit: 321039 ns, 81576 iterations find_first_andnot_bit: 929316 ns, 8279 iterations find_next_andnot_bit: 324820 ns, 82027 iterations find_first_nor_bit: 971359 ns, 8241 iterations find_next_nor_bit: 346981 ns, 82058 iterations find_next_or_bit: 882343 ns, 245623 iterations Start testing find_bit() with sparse bitmap find_next_bit: 8751 ns, 656 iterations find_next_zero_bit: 1184552 ns, 327025 iterations find_last_bit: 8820 ns, 656 iterations find_nth_bit: 1111597 ns, 655 iterations find_first_bit: 4980 ns, 59 iterations find_first_and_bit: 550 ns, 1 iterations find_next_and_bit: 3110 ns, 1 iterations find_first_andnot_bit: 7420 ns, 59 iterations find_next_andnot_bit: 9500 ns, 656 iterations find_first_nor_bit: 3889256 ns, 32647 iterations find_next_nor_bit: 1254026 ns, 326370 iterations find_next_or_bit: 14341 ns, 1311 iterations Signed-off-by: Mathieu Desnoyers Cc: Yury Norov Cc: Rasmus Villemoes --- Changes since v2: - Use bitmap_alloc rather than a local static variable for bitmaps. - Divide BITMAP_LEN by 10 for all find_first tests to ensure the test runs fast enough (a few ms per test). - Fix alignment of text output. - Clear/set bits only within range, fixing an out-of-bound access. - Use "len" parameters rather than BITMAP_LEN within all benchmark functions (changed across the whole file). --- lib/find_bit_benchmark.c | 119 +++++++++++++++++++++++++++++++++++---- 1 file changed, 107 insertions(+), 12 deletions(-) diff --git a/lib/find_bit_benchmark.c b/lib/find_bit_benchmark.c index 81d358fb459b..5ab72829e7ee 100644 --- a/lib/find_bit_benchmark.c +++ b/lib/find_bit_benchmark.c @@ -47,7 +47,7 @@ static int __init test_find_first_bit(void *bitmap, unsig= ned long len) __clear_bit(i, cp); } time =3D ktime_get() - time; - pr_err("find_first_bit: %18llu ns, %6ld iterations\n", time, cnt); + pr_err("find_first_bit: %18llu ns, %6ld iterations\n", time, cnt); =20 return 0; } @@ -67,7 +67,47 @@ static int __init test_find_first_and_bit(void *bitmap, = const void *bitmap2, uns __clear_bit(i, cp); } time =3D ktime_get() - time; - pr_err("find_first_and_bit: %18llu ns, %6ld iterations\n", time, cnt); + pr_err("find_first_and_bit: %18llu ns, %6ld iterations\n", time, cnt); + + return 0; +} + +static int __init test_find_first_andnot_bit(void *bitmap, const void *bit= map2, unsigned long len) +{ + unsigned long *cp __free(bitmap) =3D bitmap_alloc(len, GFP_KERNEL); + unsigned long i, cnt; + ktime_t time; + + bitmap_copy(cp, bitmap, len); + + time =3D ktime_get(); + for (cnt =3D i =3D 0; i < len; cnt++) { + i =3D find_first_andnot_bit(cp, bitmap2, len); + if (i < len) + __clear_bit(i, cp); + } + time =3D ktime_get() - time; + pr_err("find_first_andnot_bit: %18llu ns, %6ld iterations\n", time, cnt); + + return 0; +} + +static int __init test_find_first_nor_bit(void *bitmap, const void *bitmap= 2, unsigned long len) +{ + unsigned long *cp __free(bitmap) =3D bitmap_alloc(len, GFP_KERNEL); + unsigned long i, cnt; + ktime_t time; + + bitmap_copy(cp, bitmap, len); + + time =3D ktime_get(); + for (cnt =3D i =3D 0; i < len; cnt++) { + i =3D find_first_nor_bit(cp, bitmap2, len); + if (i < len) + __set_bit(i, cp); + } + time =3D ktime_get() - time; + pr_err("find_first_nor_bit: %18llu ns, %6ld iterations\n", time, cnt); =20 return 0; } @@ -78,10 +118,10 @@ static int __init test_find_next_bit(const void *bitma= p, unsigned long len) ktime_t time; =20 time =3D ktime_get(); - for (cnt =3D i =3D 0; i < BITMAP_LEN; cnt++) - i =3D find_next_bit(bitmap, BITMAP_LEN, i) + 1; + for (cnt =3D i =3D 0; i < len; cnt++) + i =3D find_next_bit(bitmap, len, i) + 1; time =3D ktime_get() - time; - pr_err("find_next_bit: %18llu ns, %6ld iterations\n", time, cnt); + pr_err("find_next_bit: %18llu ns, %6ld iterations\n", time, cnt); =20 return 0; } @@ -92,10 +132,10 @@ static int __init test_find_next_zero_bit(const void *= bitmap, unsigned long len) ktime_t time; =20 time =3D ktime_get(); - for (cnt =3D i =3D 0; i < BITMAP_LEN; cnt++) + for (cnt =3D i =3D 0; i < len; cnt++) i =3D find_next_zero_bit(bitmap, len, i) + 1; time =3D ktime_get() - time; - pr_err("find_next_zero_bit: %18llu ns, %6ld iterations\n", time, cnt); + pr_err("find_next_zero_bit: %18llu ns, %6ld iterations\n", time, cnt); =20 return 0; } @@ -114,7 +154,7 @@ static int __init test_find_last_bit(const void *bitmap= , unsigned long len) len =3D l; } while (len); time =3D ktime_get() - time; - pr_err("find_last_bit: %18llu ns, %6ld iterations\n", time, cnt); + pr_err("find_last_bit: %18llu ns, %6ld iterations\n", time, cnt); =20 return 0; } @@ -130,7 +170,7 @@ static int __init test_find_nth_bit(const unsigned long= *bitmap, unsigned long l WARN_ON(l >=3D len); } time =3D ktime_get() - time; - pr_err("find_nth_bit: %18llu ns, %6ld iterations\n", time, w); + pr_err("find_nth_bit: %18llu ns, %6ld iterations\n", time, w); =20 return 0; } @@ -142,10 +182,55 @@ static int __init test_find_next_and_bit(const void *= bitmap, ktime_t time; =20 time =3D ktime_get(); - for (cnt =3D i =3D 0; i < BITMAP_LEN; cnt++) - i =3D find_next_and_bit(bitmap, bitmap2, BITMAP_LEN, i + 1); + for (cnt =3D i =3D 0; i < len; cnt++) + i =3D find_next_and_bit(bitmap, bitmap2, len, i + 1); + time =3D ktime_get() - time; + pr_err("find_next_and_bit: %18llu ns, %6ld iterations\n", time, cnt); + + return 0; +} + +static int __init test_find_next_andnot_bit(const void *bitmap, + const void *bitmap2, unsigned long len) +{ + unsigned long i, cnt; + ktime_t time; + + time =3D ktime_get(); + for (cnt =3D i =3D 0; i < len; cnt++) + i =3D find_next_andnot_bit(bitmap, bitmap2, len, i + 1); + time =3D ktime_get() - time; + pr_err("find_next_andnot_bit: %18llu ns, %6ld iterations\n", time, cnt); + + return 0; +} + +static int __init test_find_next_nor_bit(const void *bitmap, + const void *bitmap2, unsigned long len) +{ + unsigned long i, cnt; + ktime_t time; + + time =3D ktime_get(); + for (cnt =3D i =3D 0; i < len; cnt++) + i =3D find_next_nor_bit(bitmap, bitmap2, len, i + 1); + time =3D ktime_get() - time; + pr_err("find_next_nor_bit: %18llu ns, %6ld iterations\n", time, cnt); + + return 0; +} + +static int __init test_find_next_or_bit(const void *bitmap, + const void *bitmap2, unsigned long len) +{ + unsigned long i, cnt; + ktime_t time; + + time =3D ktime_get(); + for (cnt =3D i =3D 0; i < len; cnt++) + i =3D find_next_or_bit(bitmap, bitmap2, len, i + 1); time =3D ktime_get() - time; - pr_err("find_next_and_bit: %18llu ns, %6ld iterations\n", time, cnt); + pr_err("find_next_or_bit: %18llu ns, %6ld iterations\n", time, cnt); =20 return 0; } @@ -171,6 +256,11 @@ static int __init find_bit_test(void) test_find_first_bit(bitmap, BITMAP_LEN / 10); test_find_first_and_bit(bitmap, bitmap2, BITMAP_LEN / 10); test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN); + test_find_first_andnot_bit(bitmap, bitmap2, BITMAP_LEN / 10); + test_find_next_andnot_bit(bitmap, bitmap2, BITMAP_LEN); + test_find_first_nor_bit(bitmap, bitmap2, BITMAP_LEN / 10); + test_find_next_nor_bit(bitmap, bitmap2, BITMAP_LEN); + test_find_next_or_bit(bitmap, bitmap2, BITMAP_LEN); =20 pr_err("\nStart testing find_bit() with sparse bitmap\n"); =20 @@ -189,6 +279,11 @@ static int __init find_bit_test(void) test_find_first_bit(bitmap, BITMAP_LEN / 10); test_find_first_and_bit(bitmap, bitmap2, BITMAP_LEN / 10); test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN); + test_find_first_andnot_bit(bitmap, bitmap2, BITMAP_LEN / 10); + test_find_next_andnot_bit(bitmap, bitmap2, BITMAP_LEN); + test_find_first_nor_bit(bitmap, bitmap2, BITMAP_LEN / 10); + test_find_next_nor_bit(bitmap, bitmap2, BITMAP_LEN); + test_find_next_or_bit(bitmap, bitmap2, BITMAP_LEN); =20 /* * Everything is OK. Return error just to let user run benchmark --=20 2.39.2 From nobody Fri Dec 19 07:19:30 2025 Received: from smtpout.efficios.com (smtpout.efficios.com [167.114.26.122]) (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 071F11BD4E5 for ; Fri, 30 Aug 2024 19:11:14 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=167.114.26.122 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1725045076; cv=none; b=tBps1zUPhD1gAg+G2uDzDpLslxQtRg+mU/rCl8dtI7sX61CWLyHIf4KzOL0YO1+2s0uf9jzoXRJ94W7NYqtHEBduU26bq4VbTNUrXr4lbmMEMyQHmCpd4Lzjn6rsSAggDF6gIgNSKGui7N+BzqEyjwvn+DgYW0ahDZfl1E5QrD8= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1725045076; c=relaxed/simple; bh=J+LpSR94ACn9qMFTKmrkKUKhlvib9nAQ8DfHXmh0T68=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=RDNti8lU1sWfez6fNdWQJDrN/Suhh984XFaaxzXcuAXy36R5Wo0K336SIcbkHQSGsnU+R951UqqES2tFRn93zArHnNGseAd3FetAoTGLOX2QHBdAyYQaTtoSJtsel5hHbXlKalgUxZqSbzajtBhb23fMeDBNtnqxHLWrpRg7PBU= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=efficios.com; spf=pass smtp.mailfrom=efficios.com; dkim=pass (2048-bit key) header.d=efficios.com header.i=@efficios.com header.b=uJVMzZcj; arc=none smtp.client-ip=167.114.26.122 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=efficios.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=efficios.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=efficios.com header.i=@efficios.com header.b="uJVMzZcj" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=efficios.com; s=smtpout1; t=1725045071; bh=J+LpSR94ACn9qMFTKmrkKUKhlvib9nAQ8DfHXmh0T68=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=uJVMzZcjMKmfISt6D/Gafqja4qtTfr8I+YQO8lwGQ++JnW7szfrncLXFeYCmVNskK xHg664oMQLzJT3dOOhUA0jLbI3zh+8iDlhJbUy8bkyaWBVv6Qrq7Myc53i5rrpnoaA 0rdu8dodE/L4J3Jlb7BRtPDRUBJxozqMqO9GUyrFi+Uz3ieITGWAtZ4MnWBKYL0rPy mKdCxuRZRxzr2zQwkclildVMLdYbbOJuitNVKz8oj3W/RwBgZHPOf4XetSaHMpZl4z KBbELGFhfe+vN4oWdwEtjOSn2bE1ypZ+iEZ0u7o7ZI5Vw2gbX0a1d2h1tQHAQ1ZiCx 1wK7+A0BeWdYg== Received: from thinkos.internal.efficios.com (96-127-217-162.qc.cable.ebox.net [96.127.217.162]) by smtpout.efficios.com (Postfix) with ESMTPSA id 4WwSRg5w2Pz1JlK; Fri, 30 Aug 2024 15:11:11 -0400 (EDT) From: Mathieu Desnoyers To: Yury Norov , Rasmus Villemoes Cc: linux-kernel@vger.kernel.org, Mathieu Desnoyers Subject: [PATCH v3 6/6] cpumask: Implement cpumask_{first,next}_{nor,andnot} Date: Fri, 30 Aug 2024 15:10:43 -0400 Message-Id: <20240830191043.1028827-7-mathieu.desnoyers@efficios.com> X-Mailer: git-send-email 2.39.2 In-Reply-To: <20240830191043.1028827-1-mathieu.desnoyers@efficios.com> References: <20240830191043.1028827-1-mathieu.desnoyers@efficios.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Allow finding the first or next bit within two input cpumasks which is either: - both zero and zero, - respectively one and zero. Signed-off-by: Mathieu Desnoyers Cc: Yury Norov Cc: Rasmus Villemoes --- Changes since v0: - Rename "notandnot" to "nor". - Use __always_inline. Changes since v1: - Use small_cpumask_bits instead of nr_cpumask_bits, which is better optimized for NR_CPUS < BITS_PER_LONG. --- include/linux/cpumask.h | 60 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 60 insertions(+) diff --git a/include/linux/cpumask.h b/include/linux/cpumask.h index 23686bed441d..0bf6aabae62c 100644 --- a/include/linux/cpumask.h +++ b/include/linux/cpumask.h @@ -204,6 +204,32 @@ unsigned int cpumask_first_and_and(const struct cpumas= k *srcp1, cpumask_bits(srcp3), small_cpumask_bits); } =20 +/** + * cpumask_first_andnot - return the first cpu from *srcp1 & ~*srcp2 + * @src1p: the first input + * @src2p: the second input + * + * Returns >=3D nr_cpu_ids if no cpus match in both. + */ +static __always_inline +unsigned int cpumask_first_andnot(const struct cpumask *srcp1, const struc= t cpumask *srcp2) +{ + return find_first_andnot_bit(cpumask_bits(srcp1), cpumask_bits(srcp2), sm= all_cpumask_bits); +} + +/** + * cpumask_first_nor - return the first cpu from ~(*srcp1 | *srcp2) + * @src1p: the first input + * @src2p: the second input + * + * Returns >=3D nr_cpu_ids if no cpus match in both. + */ +static __always_inline +unsigned int cpumask_first_nor(const struct cpumask *srcp1, const struct c= pumask *srcp2) +{ + return find_first_nor_bit(cpumask_bits(srcp1), cpumask_bits(srcp2), small= _cpumask_bits); +} + /** * cpumask_last - get the last CPU in a cpumask * @srcp: - the cpumask pointer @@ -246,6 +272,40 @@ static inline unsigned int cpumask_next_zero(int n, co= nst struct cpumask *srcp) return find_next_zero_bit(cpumask_bits(srcp), small_cpumask_bits, n+1); } =20 +/** + * cpumask_next_andnot - return the next cpu from *srcp1 & ~*srcp2 + * @n: the cpu prior to the place to search (ie. return will be > @n) + * @src1p: the first input + * @src2p: the second input + * + * Returns >=3D nr_cpu_ids if no cpus match in both. + */ +static __always_inline +unsigned int cpumask_next_andnot(int n, const struct cpumask *srcp1, const= struct cpumask *srcp2) +{ + /* -1 is a legal arg here. */ + if (n !=3D -1) + cpumask_check(n); + return find_next_andnot_bit(cpumask_bits(srcp1), cpumask_bits(srcp2), sma= ll_cpumask_bits, n+1); +} + +/** + * cpumask_next_nor - return the next cpu from ~(*srcp1 | *srcp2) + * @n: the cpu prior to the place to search (ie. return will be > @n) + * @src1p: the first input + * @src2p: the second input + * + * Returns >=3D nr_cpu_ids if no cpus match in both. + */ +static __always_inline +unsigned int cpumask_next_nor(int n, const struct cpumask *srcp1, const st= ruct cpumask *srcp2) +{ + /* -1 is a legal arg here. */ + if (n !=3D -1) + cpumask_check(n); + return find_next_nor_bit(cpumask_bits(srcp1), cpumask_bits(srcp2), small_= cpumask_bits, n+1); +} + #if NR_CPUS =3D=3D 1 /* Uniprocessor: there is only one valid CPU */ static inline unsigned int cpumask_local_spread(unsigned int i, int node) --=20 2.39.2