From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail-yw1-f177.google.com (mail-yw1-f177.google.com [209.85.128.177]) (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 8396642A792 for ; Mon, 7 Sep 2026 21:54:43 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.177 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1788818085; cv=none; b=QsoVWA2KXgawVICNC9/zCwoxrSVg+pM9uBehC0/9qs1xO646ZL5sqCM8HtiT3Y7552IdZ3/Bz7tqqkTk/DJkgY5OrDS7zRf5bTA+BET/LaTxxZjhB8xIb4EBx1g4eHim7LI5mxEOtBmeomF5LzTROYFTjj5ySGB6Gbvuk+IRXME= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1788818085; c=relaxed/simple; bh=j0DDQjd0eZ3nMQsdZ3f1Pa74wovJjaApzFKCeaNg59s=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=UrJ40aH1NIVKlCaiGqQtu5OW24xjAiHF06Pwdtw7L9y3Uxf5WEhQ2knVKtV087eet+inb5XN2VVTrD/zuNwWRhSpyXUV5Peajb5TKyDmEcMO/SexJdByFhqydEbruU7c1LXSOpPUD84I/jO7dIvmRSv8smAe8ki0CHRFRUIwUJA= 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=fDIEO8uy; arc=none smtp.client-ip=209.85.128.177 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="fDIEO8uy" Received: by mail-yw1-f177.google.com with SMTP id 00721157ae682-8623b1e7cb2so17985397b3.1 for ; Mon, 07 Sep 2026 14:54:43 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1788818082; x=1789422882; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to:content-type; bh=kt5vYk7oIJTAvWcYqFLR1526VYebZHALzcXyXv4GXys=; b=fDIEO8uyl1O4l8QZ+Hw+z3DESPGvz399XC3yrX0UXNA2IMQpMuRDCKzCwK3qH2p8D5 hMRk06HzLlhGR/coF18S8S2NAj92p9EVOh6hT83WilXDafoS5HPEsqttFNTf3krFEOqQ zY4cquifbyoUWyKmMD9adaGbXSpJP/KyLFELKoaqWeRR6lzZBX23zU0AW0kiLgpcl6wX Uw8BT4krYyd8mYPzm5Hu8JDE1Sb9qMEHX+0jKZoQtfl+ZlONSA08tp0CG/D48PadTIAF R3Lna6sIx+2pjTPUhPzvVbA+74ajzF0Z/57uhr2jhtqaMKOFcwk/pJNa1bHcR5Gu1LA9 7isw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1788818082; x=1789422882; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-gg:x-gm-message-state:from :to:cc:subject:date:message-id:reply-to:content-type; bh=kt5vYk7oIJTAvWcYqFLR1526VYebZHALzcXyXv4GXys=; b=SKnxgWqsyjuz1D8iBpKwHn8KCCbPbMr9/lecFNuqn0du84jEzkJPluyVlY3HcTub8d PM4PxzGCn3IG+0tKrIHltvFy4G1rxEZ99dIbQr1S2FVhiphgjllcBanQ1BMAfZOh6dMN WVTRqkzFZ8xHMr+g+BIODBvypms/jZVpXSDEbhaIHi2n9/CJwJPqSjQnw9rg/Xmyp+CU Aedj25F4UZPIEYe5sWQvRtkt1dLxbE7D8I3TqFe1Ex5ZBfkVVwofLdooNSRUHaQuFbRW 3lq9YZJYVO9CWwNf6P1ZPRiBfGxT/IPvxnCKj2NZc2oW5zpvG8PsNrT9FmDb9irPWY7S p8YA== X-Forwarded-Encrypted: i=1; AKwUvBx152f7LgkGxIdPDb/TclzpJYa7K0PWDyMXmXiaNDqvlw+VstuGR1l8ZUYnSUE078sTi0LWL/ghqmamNUk=@vger.kernel.org X-Gm-Message-State: AFuF++kH2pzBjnk3QWPQNQA0y7fwpg5Mot1dF9AIyZm5NlZZ47pljYeG 0qZIK9ZUS2s7QBGbqNJzjx3jWi1RrTHxkZkwCmeoNKaeZ0VZbN74kvc8 X-Gm-Gg: AYBFou0Mcvc+gKaBCvgRXmEJSY1f3G6xu2WAD4tiU5z99pC4OLGoe3SOUbPpx1Hr1/k 0NIqgOtuVtVYj2Li4+ahxGjOEyBg3keUPZ+QQnGXjU7tXqH4zrk/hVXgPqL5JG9/bjUUz0tQfe3 4o0ZV+8j5ub8GrhazKGtmVelAvMGPWF17GYpHYTkAzzB5vBG4nPg/qTx5PCxvMUA3GfCSI2f5uD UQd0yR1JKITEWYWD3eX3unJCkICBlb/txlEyp+1mVnu2fvd3Z4fqsRutq4WukgOoWvIL5gvW8l1 lFgslHDgjtlgmoETHpYu6/APmKGbvGha6hma++Lc6Y2+/xRdyVxsTUeB4hhQr9Ax8xvp72DYeZE Ni5CPNnYX47ccapVzRv1tfN4U33Fc89dwOlZ5g5/ewb7vW1FUgPAHD6j3JOyKiwSG+vs6LbEGf2 UePiJ9LdPQ1s+MV4vkO0CpCLBswMwLo1arwPVQSYqmUJCDasgmqP/Jy7OvoVpikaEqbW9Eiyfwt Zsxs+DOafTzL9Zp0A== X-Received: by 2002:a05:690c:4f02:b0:81e:eebb:8e4a with SMTP id 00721157ae682-87123521b7fmr78031777b3.12.1788818082551; Mon, 07 Sep 2026 14:54:42 -0700 (PDT) Received: from localhost (c-73-105-0-191.hsd1.fl.comcast.net. [73.105.0.191]) by smtp.gmail.com with ESMTPSA id 00721157ae682-8714bb0efc1sm77847347b3.45.2026.09.07.14.54.42 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 07 Sep 2026 14:54:42 -0700 (PDT) From: Yury Norov X-Google-Original-From: Yury Norov To: Andrew Lunn , Heiner Kallweit , Russell King , Raju Rangoju , Prashanth Kumar K R , Tony Nguyen , Przemek Kitszel , Jian Shen , Jijie Shao , "David S. Miller" , Eric Dumazet , Jakub Kicinski , Paolo Abeni , linux-kernel@vger.kernel.org, netdev@vger.kernel.org, intel-wired-lan@lists.osuosl.org, linux-usb@vger.kernel.org Cc: Yury Norov , Yury Norov , Rasmus Villemoes , Andrew Morton Subject: [PATCH 1/9] bitmap: add bitmap_and_and() and bitmap_and_andnot() Date: Mon, 7 Sep 2026 17:54:30 -0400 Message-ID: <20260907215439.409858-2-ynorov@nvidia.com> X-Mailer: git-send-email 2.53.0 In-Reply-To: <20260907215439.409858-1-ynorov@nvidia.com> References: <20260907215439.409858-1-ynorov@nvidia.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Add bitmap_and_and() and bitmap_and_andnot() to combine three bitmaps in a single pass. Both helpers return whether the resulting bitmap is non-empty. Introduce BITMAP_OP() to share the word iteration with bitmap_and(), and add tests for small constants, multiword bitmaps, aliases, tail masking, empty results and zero-sized bitmaps. Signed-off-by: Yury Norov --- include/linux/bitmap.h | 32 +++++++++++++++++ lib/bitmap.c | 46 +++++++++++++++++++------ lib/test_bitmap.c | 78 ++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 146 insertions(+), 10 deletions(-) diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h index 7df1573a409c..d524ef6b0300 100644 --- a/include/linux/bitmap.h +++ b/include/linux/bitmap.h @@ -44,6 +44,10 @@ struct device; * bitmap_fill(dst, nbits) *dst = ~0UL * bitmap_copy(dst, src, nbits) *dst = *src * bitmap_and(dst, src1, src2, nbits) *dst = *src1 & *src2 + * bitmap_and_and(dst, src1, src2, src3, nbits) + * *dst = *src1 & *src2 & *src3 + * bitmap_and_andnot(dst, src1, src2, src3, nbits) + * *dst = *src1 & *src2 & ~(*src3) * bitmap_or(dst, src1, src2, nbits) *dst = *src1 | *src2 * bitmap_weighted_or(dst, src1, src2, nbits) *dst = *src1 | *src2. Returns Hamming Weight of dst * bitmap_weighted_xor(dst, src1, src2, nbits) *dst = *src1 ^ *src2. Returns Hamming Weight of dst @@ -166,6 +170,12 @@ void bitmap_cut(unsigned long *dst, const unsigned long *src, unsigned int first, unsigned int cut, unsigned int nbits); bool __bitmap_and(unsigned long *dst, const unsigned long *bitmap1, const unsigned long *bitmap2, unsigned int nbits); +bool __bitmap_and_and(unsigned long *dst, const unsigned long *bitmap1, + const unsigned long *bitmap2, + const unsigned long *bitmap3, unsigned int nbits); +bool __bitmap_and_andnot(unsigned long *dst, const unsigned long *bitmap1, + const unsigned long *bitmap2, + const unsigned long *bitmap3, unsigned int nbits); void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1, const unsigned long *bitmap2, unsigned int nbits); unsigned int __bitmap_weighted_or(unsigned long *dst, const unsigned long *bitmap1, @@ -337,6 +347,28 @@ bool bitmap_and(unsigned long *dst, const unsigned long *src1, return __bitmap_and(dst, src1, src2, nbits); } +static __always_inline +bool bitmap_and_and(unsigned long *dst, const unsigned long *src1, + const unsigned long *src2, const unsigned long *src3, + unsigned int nbits) +{ + if (small_const_nbits(nbits)) + return (*dst = *src1 & *src2 & *src3 & + BITMAP_LAST_WORD_MASK(nbits)) != 0; + return __bitmap_and_and(dst, src1, src2, src3, nbits); +} + +static __always_inline +bool bitmap_and_andnot(unsigned long *dst, const unsigned long *src1, + const unsigned long *src2, const unsigned long *src3, + unsigned int nbits) +{ + if (small_const_nbits(nbits)) + return (*dst = *src1 & *src2 & ~(*src3) & + BITMAP_LAST_WORD_MASK(nbits)) != 0; + return __bitmap_and_andnot(dst, src1, src2, src3, nbits); +} + static __always_inline void bitmap_or(unsigned long *dst, const unsigned long *src1, const unsigned long *src2, unsigned int nbits) diff --git a/lib/bitmap.c b/lib/bitmap.c index ed685127a107..85ce3cbaa9ab 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -34,6 +34,25 @@ * for the best explanations of this ordering. */ +/* + * Common helper for bitmap operations. + * @FETCH: The expression that fetches and combines each word of the bitmaps + * @bits: The bitmap size in bits + */ +#define BITMAP_OP(FETCH, bits) \ +({ \ + unsigned long idx, val, sz = (bits), result = 0; \ + \ + for (idx = 0; idx * BITS_PER_LONG < sz; idx++) { \ + val = (FETCH); \ + if (sz - idx * BITS_PER_LONG < BITS_PER_LONG) \ + val &= BITMAP_LAST_WORD_MASK(sz); \ + result |= (dst[idx] = val); \ + } \ + \ + result != 0; \ +}) + bool __bitmap_equal(const unsigned long *bitmap1, const unsigned long *bitmap2, unsigned int bits) { @@ -230,19 +249,26 @@ EXPORT_SYMBOL(bitmap_cut); bool __bitmap_and(unsigned long *dst, const unsigned long *bitmap1, const unsigned long *bitmap2, unsigned int bits) { - unsigned int k; - unsigned int lim = bits/BITS_PER_LONG; - unsigned long result = 0; - - for (k = 0; k < lim; k++) - result |= (dst[k] = bitmap1[k] & bitmap2[k]); - if (bits % BITS_PER_LONG) - result |= (dst[k] = bitmap1[k] & bitmap2[k] & - BITMAP_LAST_WORD_MASK(bits)); - return result != 0; + return BITMAP_OP(bitmap1[idx] & bitmap2[idx], bits); } EXPORT_SYMBOL(__bitmap_and); +bool __bitmap_and_and(unsigned long *dst, const unsigned long *bitmap1, + const unsigned long *bitmap2, + const unsigned long *bitmap3, unsigned int bits) +{ + return BITMAP_OP(bitmap1[idx] & bitmap2[idx] & bitmap3[idx], bits); +} +EXPORT_SYMBOL(__bitmap_and_and); + +bool __bitmap_and_andnot(unsigned long *dst, const unsigned long *bitmap1, + const unsigned long *bitmap2, + const unsigned long *bitmap3, unsigned int bits) +{ + return BITMAP_OP(bitmap1[idx] & bitmap2[idx] & ~bitmap3[idx], bits); +} +EXPORT_SYMBOL(__bitmap_and_andnot); + void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1, const unsigned long *bitmap2, unsigned int bits) { diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c index 56bd23059b26..fbc46ed960a4 100644 --- a/lib/test_bitmap.c +++ b/lib/test_bitmap.c @@ -193,6 +193,81 @@ static void __init test_zero_clear(void) expect_eq_pbl("", bmap, 1024); } +static void __init test_bitmap_and(void) +{ + enum { nbits = BITS_PER_LONG + 13 }; + DECLARE_BITMAP(src1, nbits); + DECLARE_BITMAP(src2, nbits); + DECLARE_BITMAP(src3, nbits); + DECLARE_BITMAP(dst, nbits); + DECLARE_BITMAP(expected, nbits); + unsigned long small_src1 = ~0UL; + unsigned long small_src2 = ~0UL; + unsigned long small_src3 = BIT(2); + unsigned long small_dst; + bool ret; + + ret = bitmap_and_and(&small_dst, &small_src1, &small_src2, + &small_src3, 4); + expect_eq_ulong(true, ret); + expect_eq_ulong(BIT(2), small_dst); + + ret = bitmap_and_andnot(&small_dst, &small_src1, &small_src2, + &small_src3, 4); + expect_eq_ulong(true, ret); + expect_eq_ulong(GENMASK(3, 0) & ~BIT(2), small_dst); + + bitmap_zero(src1, nbits); + bitmap_zero(src2, nbits); + bitmap_zero(src3, nbits); + bitmap_zero(expected, nbits); + __set_bit(1, src1); + __set_bit(2, src1); + __set_bit(BITS_PER_LONG + 1, src1); + __set_bit(BITS_PER_LONG + 12, src1); + __set_bit(BITS_PER_LONG + 13, src1); + __set_bit(1, src2); + __set_bit(BITS_PER_LONG + 1, src2); + __set_bit(BITS_PER_LONG + 12, src2); + __set_bit(BITS_PER_LONG + 13, src2); + __set_bit(BITS_PER_LONG + 1, src3); + __set_bit(1, expected); + __set_bit(BITS_PER_LONG + 1, expected); + __set_bit(BITS_PER_LONG + 12, expected); + + ret = bitmap_and(dst, src1, src2, nbits); + expect_eq_ulong(true, ret); + expect_eq_bitmap(expected, dst, nbits); + expect_eq_ulong(BIT(1) | BIT(12), dst[1]); + + bitmap_zero(expected, nbits); + __set_bit(BITS_PER_LONG + 1, expected); + ret = bitmap_and_and(dst, src1, src2, src3, nbits); + expect_eq_ulong(true, ret); + expect_eq_bitmap(expected, dst, nbits); + expect_eq_ulong(BIT(1), dst[1]); + + bitmap_zero(expected, nbits); + __set_bit(1, expected); + __set_bit(2, expected); + __set_bit(BITS_PER_LONG + 12, expected); + ret = bitmap_andnot(dst, src1, src3, nbits); + expect_eq_ulong(true, ret); + expect_eq_bitmap(expected, dst, nbits); + expect_eq_ulong(BIT(12), dst[1]); + + __clear_bit(2, expected); + ret = bitmap_and_andnot(src2, src1, src2, src3, nbits); + expect_eq_ulong(true, ret); + expect_eq_bitmap(expected, src2, nbits); + expect_eq_ulong(BIT(12), src2[1]); + + bitmap_fill(src3, nbits); + ret = bitmap_and_andnot(src2, src1, src2, src3, nbits); + expect_eq_ulong(false, ret); + expect_eq_pbl("", src2, nbits); +} + static void __init test_find_nth_bit(void) { unsigned long b, bit, cnt = 0; @@ -1533,6 +1608,8 @@ static void __init test_zero_nbits(void) bitmap_zero(NULL, 0); ret = bitmap_and(NULL, NULL, NULL, 0); + ret = bitmap_and_and(NULL, NULL, NULL, NULL, 0); + ret = bitmap_and_andnot(NULL, NULL, NULL, NULL, 0); ret = bitmap_empty(NULL, 0); ret = bitmap_equal(NULL, NULL, 0); ret = bitmap_full(NULL, 0); @@ -1566,6 +1643,7 @@ static void __init test_zero_nbits(void) static void __init selftest(void) { test_zero_clear(); + test_bitmap_and(); test_fill_set(); test_copy(); test_bitmap_region(); -- 2.53.0