From nobody Sun Feb 8 05:30:09 2026 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 DB0F41AD41B for ; Thu, 29 Aug 2024 14:00:05 +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=1724940008; cv=none; b=gJXq0hi9qbBd6j8VuFet95TssMt2iv3eqEw1xvuK1pYwyFByuJAEnhZgI3jMcde31Pa/lGR07s9YxTElHL0rkEiwLYcdoHj2Dg/b7mOPQ6eEzZORWnSZe5N/TDSN7p/D1QXoAWCf5pzzxsmkkz7wQ8EpnueydQ1PR3fHwDkP9U8= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1724940008; c=relaxed/simple; bh=AGFDpfa+bqvaKAyzR3i8XqMbzLG42VLnwzugz17jL9I=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=lnsRYt4PplIslTEcUmt46cYQuW6grMQbwRPAS87Z+tHbg6FYmS9je9dTpmqMU6biOQC+ZVZXxEZDGJNM07j4pdmaY1P1RqMKaYX4W6diz7UEZ/NMbxPCd4NAAdjlbt1vfTkvkCdvxLr63amHtDKG5laDrtg4kS+EdoVHHxSoEEQ= 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=sS48Fecv; 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="sS48Fecv" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=efficios.com; s=smtpout1; t=1724939999; bh=AGFDpfa+bqvaKAyzR3i8XqMbzLG42VLnwzugz17jL9I=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=sS48Fecvdc8VDjaawHe1Gz1xZXn9YvKWE27J4RI8FQsuK3bIEFdLs3TCxJGLDkl2y 6Nj/wlj/NZUyBH0OKSmHBBddT0Mm73zC9pGgu/aNxwNC87t2g08VsHAWL6EsqxycRz hQJQXBXjH6O3HFLiKVSIxzGUtt1HZJCN6WmITKItuUU0uO4sCd+/J158uuXa34kBen YN6W+GB5ciw3OqcguZQOt1HWIOY1rQF6iXoa09Hml+Lh6w4XvewyLobstLNqxEsRvo ZB9+4tH8rtY4toah9aj8x5klmCy8riAd+oS913QKeMjtzUycZnzZldKNPazvwZOK5T aUNHfBF6/k8Sg== 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 4Wvjb31pXVz1JQc; Thu, 29 Aug 2024 09:59:59 -0400 (EDT) From: Mathieu Desnoyers To: Yury Norov , Rasmus Villemoes Cc: linux-kernel@vger.kernel.org, Mathieu Desnoyers Subject: [PATCH v2 1/6] lib: Clarify comment on top of find_next_andnot_bit Date: Thu, 29 Aug 2024 09:59:21 -0400 Message-Id: <20240829135926.926603-2-mathieu.desnoyers@efficios.com> X-Mailer: git-send-email 2.39.2 In-Reply-To: <20240829135926.926603-1-mathieu.desnoyers@efficios.com> References: <20240829135926.926603-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 Sun Feb 8 05:30:09 2026 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 DB1E71AD9E5 for ; Thu, 29 Aug 2024 14:00:05 +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=1724940009; cv=none; b=bFUyJ4UcG5QUxHZCqFyA+Il2RcqmfYWVO0f5/7VnC45/iyypxEijoiBnlP2avVrPDgZdUwGLZYVemgNucTePXMN1eBjw1/joKAb6EVB93UL+cAt0EVtNnbq4VAnBg+Sl+KMX6hUKzVkr0llbu2P1pbHjqPDz3VPaEsS3LUpovqw= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1724940009; c=relaxed/simple; bh=GZRhJ9V/rBWzlcb4oNthjmQL/Bu5uEyMcfx5lKJI1xc=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=JY13iN8E4gQHZfGD6dXrpJ9aYOVUEOBB1rgmPtv6R2EYV76CDgXepR92rL8cag3KvIVTGslO4mMzNlRzDNmw9EBM8iW7VGf2dmmf2F+et4LTo41t7bBE5/FdRrtRT827LH0u1UkWmVcyU528wFv7CkFdIFBpE1BWtSVjgtZQFzY= 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=oDrAiUex; 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="oDrAiUex" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=efficios.com; s=smtpout1; t=1724939999; bh=GZRhJ9V/rBWzlcb4oNthjmQL/Bu5uEyMcfx5lKJI1xc=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=oDrAiUex+fFf4A+WRjhRVn7/ZsaATNPR4PeLiHilQhgiGKNhrfHtvuepQhX5jT3Oz lnUjRKRdKhU5tl5fhbjjFoKSiHO4vd4s7NQitGsYTzTB/ej4rP+KyRxSRuTQueI6UH aEkrrykPPHQg3KARI58K24+a1QWzmYCRf88tJehyU7UORHWiMLeB5DgeX3TKW0p9Zq BAjwI+iLldtRGCpWxfUcRhrv2exjmbg3rH0chbSy6CK1CbVB3o5VxUd9rfJTxMWxTD Vee7Qu5AXbIGejszn3IV8fIF+ilR8Jsi00VRJTX8PgyViaEukDN5AUvsEGz7X6pSd1 dSdr8//MYKCqg== 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 4Wvjb334rhz1JQd; Thu, 29 Aug 2024 09:59:59 -0400 (EDT) From: Mathieu Desnoyers To: Yury Norov , Rasmus Villemoes Cc: linux-kernel@vger.kernel.org, Mathieu Desnoyers Subject: [PATCH v2 2/6] lib: Implement find_{first,next,nth}_nor_bit, for_each_nor_bit, find_first_andnot_bit Date: Thu, 29 Aug 2024 09:59:22 -0400 Message-Id: <20240829135926.926603-3-mathieu.desnoyers@efficios.com> X-Mailer: git-send-email 2.39.2 In-Reply-To: <20240829135926.926603-1-mathieu.desnoyers@efficios.com> References: <20240829135926.926603-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. --- 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..cf3a49d18c1f 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); +extern unsigned long _find_first_andnot_bit(const unsigned long *addr1, + const unsigned long *addr2, unsigned long size); +extern 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 Sun Feb 8 05:30:09 2026 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 DB1421AD9C0 for ; Thu, 29 Aug 2024 14:00:05 +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=1724940009; cv=none; b=AZe0akPIBstRIQZIxk86qPilPQ7w272uU5ngPdaCkuHz1ZgoRv75rCikQdXsWHsdW3JaEFKwG1p2DEUbFC8GqN+cqC0yXwdrjmNmgkQP5Hu262PB0qvnVXqoHdeGoLrdbaHlaQvHJZVlBHE+8Dx6dd5UFOPt6PwBoxWM248FhHY= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1724940009; c=relaxed/simple; bh=mSlbGJz8j44ZPE+sDl5Lu+E4GWu7DyDgzRUR10EQ6Ys=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=Af0jR6HBTkAxrzmYh0TwJAfddiO5mcmCuOeAfUTBcj4SI94rHKa9xnvsuzYV7/9zdZjCJtLcIv4F2n2oszr96rczoQyiKgh+T4lI7RmDw40pdqv6+t1bfUQBIEgDsUnhk0PWtt+PvN8LMrZdLDd4GKS2SfsTyFGvP2bXoII7d3c= 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=BP8MWRHx; 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="BP8MWRHx" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=efficios.com; s=smtpout1; t=1724939999; bh=mSlbGJz8j44ZPE+sDl5Lu+E4GWu7DyDgzRUR10EQ6Ys=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=BP8MWRHxV7Ukq5DQoYHaCUGG9SUOIXGLYpo30B0X42c2ZncexFKkYd4ZN3aZN0ZME 0JHnDkZWOfzPFOvBh2eSRrYwkniuAmRF2udxRjwW/Pq5r/DSlyx8pgjXYn2a66aBiT 0GAVNZyGMIzCjm+7REC4frVoNNqv2Q50nbR7Vtit8vETjITM5GK/6wfEUlXNTpVbjk Dyjzb3iu/qQmzZ2HXUmt1XTyFcU7Ht8ZQhj2NaXS6wFKEWGIJ2y423Aj5ddJqNxNmq Ek+tJHogq5N2/xuOAO4OleZwPlr141V51DZceqmIN7wNB9GI9OxgUY4ZjU6BYapyOA etnbgECMugx0A== 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 4Wvjb34MJQz1JQf; Thu, 29 Aug 2024 09:59:59 -0400 (EDT) From: Mathieu Desnoyers To: Yury Norov , Rasmus Villemoes Cc: linux-kernel@vger.kernel.org, Mathieu Desnoyers Subject: [PATCH v2 3/6] lib: test bitmap sets binary operation iterators Date: Thu, 29 Aug 2024 09:59:23 -0400 Message-Id: <20240829135926.926603-4-mathieu.desnoyers@efficios.com> X-Mailer: git-send-email 2.39.2 In-Reply-To: <20240829135926.926603-1-mathieu.desnoyers@efficios.com> References: <20240829135926.926603-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 Sun Feb 8 05:30:09 2026 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 F0BF41AD419 for ; Thu, 29 Aug 2024 14:00:06 +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=1724940009; cv=none; b=eo8Id3mhJh17tWg1AWmpZYpiRGoBUK7toHMiXSh2eJV0+E7zsjc2NoXIKQkp5o7l0c63deDkTxyGvGLAT1tMMeMzdC2enuc8Pzu8dzaAaGYQdmTh7KSSr7KKpG1MS2qCzS7tLsJ5AWWw/WIxvQYwbxWlcCdroXoUfO+GbXzdU0Q= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1724940009; c=relaxed/simple; bh=TauEHashCWRZD329tWKJi8OZYV4rw/E8L6w9rrOoAiM=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=h6KHudPSvI8Vf82czMmOCwRxpgGFD1S2VZVkTR/ezgpUftBJ1okScgQn//LCZGNsewyEw76sTT6D6hNg5eltsGH00CrVOHk4kRxRaqR1QTQM1yjX8bJR3ZiBULlXlvb27EBX81DKW6PCji9xTEA6uF4K5siKjFq9fTBwCHglsBI= 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=eu6ntkBT; 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="eu6ntkBT" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=efficios.com; s=smtpout1; t=1724939999; bh=TauEHashCWRZD329tWKJi8OZYV4rw/E8L6w9rrOoAiM=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=eu6ntkBTZBDl9ttS7nu2yJARmQcwZBalGKT86rtnGFwOSe+7C3JY30x//Ih0qhm39 KsP1CHskeJ1tdSlbSnrbffP5yVa80Dn+J6TlEo3q34Atf+c2qVWwCKekhiE0Z9RiZO dpw8yZU4BG21UB3edR2j9Jh2FoWwi5bp/XPmfULDvdEQlx7+/g6urnJdkMCFf4pmFN CWI/VH2YBY/9HLCGBCP1coH1YIKjyJscAHuNWswrohBigaCLX8C3IBReljDOQA1JtF VHxZ/P/jdVtnd48XbARmM6A8dysRAQ09TIqhMvxgzjgEWFND1f4cB8S22X/dU0A9Tv JSt08pIYBeyVQ== 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 4Wvjb35c6Bz1JQg; Thu, 29 Aug 2024 09:59:59 -0400 (EDT) From: Mathieu Desnoyers To: Yury Norov , Rasmus Villemoes Cc: linux-kernel@vger.kernel.org, Mathieu Desnoyers Subject: [PATCH v2 4/6] lib: Fix test_find_first_and_bit and test_find_next_and_bit benchmark Date: Thu, 29 Aug 2024 09:59:24 -0400 Message-Id: <20240829135926.926603-5-mathieu.desnoyers@efficios.com> X-Mailer: git-send-email 2.39.2 In-Reply-To: <20240829135926.926603-1-mathieu.desnoyers@efficios.com> References: <20240829135926.926603-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). Signed-off-by: Mathieu Desnoyers Cc: Yury Norov Cc: Rasmus Villemoes --- lib/find_bit_benchmark.c | 10 ++++++---- 1 file changed, 6 insertions(+), 4 deletions(-) diff --git a/lib/find_bit_benchmark.c b/lib/find_bit_benchmark.c index d3fb09e6eff1..aee2ebb6b3cd 100644 --- a/lib/find_bit_benchmark.c +++ b/lib/find_bit_benchmark.c @@ -30,18 +30,20 @@ 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) { + static DECLARE_BITMAP(cp, BITMAP_LEN) __initdata; unsigned long i, cnt; ktime_t time; =20 + bitmap_copy(cp, bitmap, 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); + __clear_bit(i, cp); } time =3D ktime_get() - time; pr_err("find_first_bit: %18llu ns, %6ld iterations\n", time, cnt); --=20 2.39.2 From nobody Sun Feb 8 05:30:09 2026 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 4F26C1AE854 for ; Thu, 29 Aug 2024 14:00:09 +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=1724940011; cv=none; b=kfg1b8n6BI7nuV45X2bUkHUlzGDvu8l3RZe0o5sHO05Gme6lsq9XHtl6LVQD2/NAmZYcpWCRytbdTN3rBr0KUB3gMGT9di6keYAiLra2Y9Nj05hxFw7DHxprMWo/pDKXkmKtB23ghtJVk4wiv/YudT+PlB7ZgPS8vCeiwkttVCc= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1724940011; c=relaxed/simple; bh=KdXiOvXe3KSszStvVJj4Th0Hm05YrgAvrJXDPd4DUs4=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=Zd4epGRPafpryLCR/QkTFCNYW8RyvWAxQYT4ipDIGo7inIWCc4ioiSl7osVnfBYNflJYUN35Zh17Fo5hrpBuIafdm78KC8LZqgpWqop4MNFEDTJ7zbhw/m7XaGawcLjWdoTmVmEu4VORy1JF/wCSpTtVFvtcpFI3ER756tFW7g8= 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=OTTGS7gy; 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="OTTGS7gy" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=efficios.com; s=smtpout1; t=1724940000; bh=KdXiOvXe3KSszStvVJj4Th0Hm05YrgAvrJXDPd4DUs4=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=OTTGS7gyXAZqvgCmOFPQUW47uzXn+4BuGQ1vk92uC8FErUI+ryHONu3HbVgUAL9r3 KLGIzIgj1t98d3aE2tOh6QN+lzIY9NfD8+V/7XDcuMILTyWJvXSX5GbvqGHWwFvSpV taqxJoLFt+eLW30o/ZOBoZpZk4i6PYKKtexkqQB8vZlyAOKA2aOjh4/U+E67rdu45U BS4WtiYfYMVwSXcuGQKedVjzs3UgJ0vElonG8xZBfm6ztef42e6zI039Ty2Le2CUWG r6OwZBjEgojrC8iMsU5IKd18KdcrXgEXNGGDeLRDeF+HLAo0Sx52He54br5hkkSGEb C4mJM3ppWAsUQ== 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 4Wvjb36w1cz1JQh; Thu, 29 Aug 2024 09:59:59 -0400 (EDT) From: Mathieu Desnoyers To: Yury Norov , Rasmus Villemoes Cc: linux-kernel@vger.kernel.org, Mathieu Desnoyers Subject: [PATCH v2 5/6] lib: benchmark bitmap sets binary operation find Date: Thu, 29 Aug 2024 09:59:25 -0400 Message-Id: <20240829135926.926603-6-mathieu.desnoyers@efficios.com> X-Mailer: git-send-email 2.39.2 In-Reply-To: <20240829135926.926603-1-mathieu.desnoyers@efficios.com> References: <20240829135926.926603-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. Signed-off-by: Mathieu Desnoyers Cc: Yury Norov Cc: Rasmus Villemoes --- lib/find_bit_benchmark.c | 93 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 93 insertions(+) diff --git a/lib/find_bit_benchmark.c b/lib/find_bit_benchmark.c index aee2ebb6b3cd..3b16254dec23 100644 --- a/lib/find_bit_benchmark.c +++ b/lib/find_bit_benchmark.c @@ -70,6 +70,44 @@ static int __init test_find_first_and_bit(void *bitmap, = const void *bitmap2, uns return 0; } =20 +static int __init test_find_first_andnot_bit(void *bitmap, const void *bit= map2, unsigned long len) +{ + static DECLARE_BITMAP(cp, BITMAP_LEN) __initdata; + unsigned long i, cnt; + ktime_t time; + + bitmap_copy(cp, bitmap, BITMAP_LEN); + + time =3D ktime_get(); + for (cnt =3D i =3D 0; i < len; cnt++) { + i =3D find_first_andnot_bit(cp, bitmap2, 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) +{ + static DECLARE_BITMAP(cp, BITMAP_LEN) __initdata; + unsigned long i, cnt; + ktime_t time; + + bitmap_copy(cp, bitmap, BITMAP_LEN); + + time =3D ktime_get(); + for (cnt =3D i =3D 0; i < len; cnt++) { + i =3D find_first_nor_bit(cp, bitmap2, len); + __set_bit(i, cp); + } + time =3D ktime_get() - time; + pr_err("find_first_nor_bit: %18llu ns, %6ld iterations\n", time, cnt); + + return 0; +} + static int __init test_find_next_bit(const void *bitmap, unsigned long len) { unsigned long i, cnt; @@ -148,6 +186,51 @@ static int __init test_find_next_and_bit(const void *b= itmap, return 0; } =20 +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 < BITMAP_LEN; cnt++) + i =3D find_next_andnot_bit(bitmap, bitmap2, BITMAP_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 < BITMAP_LEN; cnt++) + i =3D find_next_nor_bit(bitmap, bitmap2, BITMAP_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 < BITMAP_LEN; cnt++) + i =3D find_next_or_bit(bitmap, bitmap2, BITMAP_LEN, i + 1); + time =3D ktime_get() - time; + pr_err("find_next_or_bit: %18llu ns, %6ld iterations\n", time, cnt); + + return 0; +} + static int __init find_bit_test(void) { unsigned long nbits =3D BITMAP_LEN / SPARSE; @@ -169,6 +252,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 / 2); test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN); + test_find_first_andnot_bit(bitmap, bitmap2, BITMAP_LEN / 2); + test_find_next_andnot_bit(bitmap, bitmap2, BITMAP_LEN); + test_find_first_nor_bit(bitmap, bitmap2, BITMAP_LEN / 2); + 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 @@ -187,6 +275,11 @@ static int __init find_bit_test(void) test_find_first_bit(bitmap, BITMAP_LEN); test_find_first_and_bit(bitmap, bitmap2, BITMAP_LEN); test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN); + test_find_first_andnot_bit(bitmap, bitmap2, BITMAP_LEN); + test_find_next_andnot_bit(bitmap, bitmap2, BITMAP_LEN); + test_find_first_nor_bit(bitmap, bitmap2, BITMAP_LEN); + 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 Sun Feb 8 05:30:09 2026 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 4F2191AE850 for ; Thu, 29 Aug 2024 14:00:09 +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=1724940010; cv=none; b=D+FfkIYddQmHpwBU6xGv9/+P4g/GjZpXq4DzW+2H9khym4uurQN0zw4/0eFbnQGZbjyGOHR4KWelZx1DUzBNzXBAzweMH12kLu6EDIs1tMxxz+S+6eEnh0/qagavfa+R2/cMvrrueO5u7oZt+AP9bJp/2bTGsNukmlGefqr4D7E= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1724940010; c=relaxed/simple; bh=J+LpSR94ACn9qMFTKmrkKUKhlvib9nAQ8DfHXmh0T68=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=NCUOrW/O4k7idleqMlDqUwAvZIgGmQ1vOeHQdQGCeeeJN6ceDG8QbH5Iq7ArkkSRkcKFMa9WFUOCnXUw1r0eAdX9zdEzZHkxPkCsuOu6Q5pTYo/PvVx187+nfiNJOEqH5xT9ZowyIrVtn2lz7WOvVts+20XExZPbrPDj7SAUZLE= 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=ITSFUHQ4; 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="ITSFUHQ4" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=efficios.com; s=smtpout1; t=1724940000; bh=J+LpSR94ACn9qMFTKmrkKUKhlvib9nAQ8DfHXmh0T68=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=ITSFUHQ4hj1NCpSaio66hyRJtTI++w7ANKEfytxEAnBuz5xjpoFCrkXjlPFW1hpl8 uG6dLJVkpWjwsXNtY2jhOvzPRgFsMyKP1U0NYhRmuWbMUshrIqwLLGj8YBCTCJjO6h Pv4LKHwl09L/53J92cPRYsLVJ7tkqyJSybsEacp0c7ZTlpPJ5WebVPIbMvLuvfLApa H7T84dJLf+eWiEFGDisW/uTcPCO0z67FK9GSBP5xDTtFZLhtUlbi0F/4Leajsh7kTA bPyOUih2DqiCTuWp8rWYi+pNhOlT0Ym0vONQyVvUflMWLKYGZWYc3+TCeOp8WROejb ACrWB62gU62dg== 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 4Wvjb415Q6z1JQj; Thu, 29 Aug 2024 10:00:00 -0400 (EDT) From: Mathieu Desnoyers To: Yury Norov , Rasmus Villemoes Cc: linux-kernel@vger.kernel.org, Mathieu Desnoyers Subject: [PATCH v2 6/6] cpumask: Implement cpumask_{first,next}_{nor,andnot} Date: Thu, 29 Aug 2024 09:59:26 -0400 Message-Id: <20240829135926.926603-7-mathieu.desnoyers@efficios.com> X-Mailer: git-send-email 2.39.2 In-Reply-To: <20240829135926.926603-1-mathieu.desnoyers@efficios.com> References: <20240829135926.926603-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