From nobody Tue Dec 16 14:34:58 2025 Received: from mail-yw1-f169.google.com (mail-yw1-f169.google.com [209.85.128.169]) (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 1BDBB284880 for ; Sun, 14 Dec 2025 23:54:41 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.169 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1765756483; cv=none; b=opMCDMB/nBvKQ5g4yasOKUmCJkBkKNPNzZVQqcVaApq7DbI+978/GQStRBKofMFntzosuOxZtxbs44hyCDX8kkW6VJC132hm56JNwO1LoCtAPfywL7uhAl4+O9QheRz+A9UJDKtGvyISE1U3nB5bqDu7t7K4ii1tk+05jB8sJc0= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1765756483; c=relaxed/simple; bh=oyfZv78MCtLgcWXJq+PVszKdmleYZqrVFgfVv7kraDw=; h=From:To:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=QNEKFELxqElOhW3HpbjbFgDLP+5+6gkS54pBlCebtH7V9444Ax1ABBdcTARNu20vDkgcoE/9dWYPN5dwB6adZuIhX0UCaUZ32H6sjTeNNWlB0ykjdjGTNxE8cAwcavf0wDlgk1uo4arZ2m2uPMAUmtmMyLeRuflp8i/aW4w0q8Y= 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=A72ZTOqe; arc=none smtp.client-ip=209.85.128.169 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="A72ZTOqe" Received: by mail-yw1-f169.google.com with SMTP id 00721157ae682-78c2e5745bdso25837917b3.0 for ; Sun, 14 Dec 2025 15:54:41 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1765756481; x=1766361281; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:to:from:from:to:cc:subject:date:message-id :reply-to; bh=k3DqkF11uBKbFVEBC/4dpay7rl+jOo4iAnq0ZCR4aR8=; b=A72ZTOqeDPfxJBJftuxwvW+hBMI3oc5JgNvSbC9M8RRmjUusM57m/Q++uOEZRKuLvH k7V+0oLGlCJEkid6CD5svyySBjuCv8YujWocRak94C/KJmCVd3fjHtK66i8qvIQEVCET e+Qf1oUmxlxAmLw7FNo92sH+6VoOP+lMTKy24dZICQm/Uku/7JKNo/bJga631zP0zfO9 B20+I0zT6lcH7E30CMfzOBbTjDhng/qrxQ3jjjbQL+qdeowKUay5lbozaydG1T5Ee/Np PX17JNvnKz3qZOO7N4bzdSRjXlFzRXEfDbyOlXZOyZbjuIa2IoaiNVWgZxBfMul0+eSQ k3wA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1765756481; x=1766361281; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:to:from:x-gm-gg:x-gm-message-state:from:to :cc:subject:date:message-id:reply-to; bh=k3DqkF11uBKbFVEBC/4dpay7rl+jOo4iAnq0ZCR4aR8=; b=r5r/0Zu8sCBgDSKo/OdhqWZut60DodF+sFdC14uIKeK2x9vOQ/fK4tM6mjXYHCuRC3 U8DU5/xdzI6y46Mdb2D7DG1lMSktxdKsW7jNgMrqg2WbLivvwmPDnodRmop6VNVRXoi4 OtCN3eYVrD21aLfS2/0wwEmqPybAFBR+MVKKcUY487yjTw4eZOEyM95MZtL57B1ZK/Hn 0aEJNAnDshuGAjrfT4YaXHVwC3MgMcHns4n0LGSMSq3umrvrEPxWwV/QXf5Ql9NA27Qn eSIzF8QJYqJeCrIAyHXUl4Y6x0ymoW6vYHciYQkTt9XLWQqDP3XyF1JR69Qy8dwYPzEs zCFg== X-Forwarded-Encrypted: i=1; AJvYcCXrMAyG1QNaO9YxX+xnKjduezXGwGkz2yy1Cw83fXqW/xM52A9cHrtqv52B/QGd3cLD+BheQUrxwodUGg0=@vger.kernel.org X-Gm-Message-State: AOJu0YxqI4EsETgWItMlSeQxbMpj+ZsYPgKoP8zzbvA2puQUXX4WWyBy A6mJMSsyzZ9LQM8RhCtYwK+d4kXI1aK6vZrSQ4V6/rDwlQoZUvVbg3cm X-Gm-Gg: AY/fxX4Wdk+G4B79LTYLDTQdlqeAQB8OA3tNYxtXxTftOZlT1a3r964+K7dFrSvmqKG qlnKLl9Z1moGqGznzJ8N7t0MzEOeIkwsFOAQZFUMq4nk1St70krHilKfOptQJ/jzXDA8JzUxnsT R2cKqKRldo8wxkCrrKWo+kp+PipixyDLG/bOBXh0hhWc4eS6EQdWvyVyOGfZlgJvK0lkEEs2RTh d0hkphdQqoXLxbzLA56X0iBpxPvl7MDoVnyu1cB0+0EjbQPfzOJibIFuP1tLapzjcmQTAJKtNhN 04BV7vazSJe26fBG/hwLXSiMJIs5DNuN3gi/gekhV4ybTbqxpiHNgSs8vASQiAm2mef6gBEOnLs dl2GaEWWBp/uuaKSOAo6c/87Wxoq7ORU2Lg+W9I0xd2473ZYjOJrjCwXjU9cTGdOyF83xCXfIC0 6/XSIhHNU= X-Google-Smtp-Source: AGHT+IH0Vwf2yLZQpVLN9FhI+nq5JWBwTpzeEo2liRzxTMwWPg676DTWLP4oPIM3I/62Olv34T/6Ug== X-Received: by 2002:a05:690c:4988:b0:787:ed2a:79df with SMTP id 00721157ae682-78e66caa9afmr162937857b3.10.1765756480916; Sun, 14 Dec 2025 15:54:40 -0800 (PST) Received: from localhost ([2601:346:0:79bd:3037:17e6:9976:d6ea]) by smtp.gmail.com with ESMTPSA id 00721157ae682-78e748d0bdfsm22444227b3.4.2025.12.14.15.54.40 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 14 Dec 2025 15:54:40 -0800 (PST) From: "Yury Norov (NVIDIA)" To: Ingo Molnar , Thomas Gleixner , Borislav Petkov , Dave Hansen , x86@kernel.org, "H. Peter Anvin" , Yury Norov , Rasmus Villemoes , Andrew Morton , "Peter Zijlstra (Intel)" , =?UTF-8?q?Ilpo=20J=C3=A4rvinen?= , Tony Luck , "Xin Li (Intel)" , "Chang S. Bae" , linux-kernel@vger.kernel.org Subject: [PATCH 1/2] bitmap: add bitmap_weight_from() Date: Sun, 14 Dec 2025 18:54:35 -0500 Message-ID: <20251214235437.244125-2-yury.norov@gmail.com> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20251214235437.244125-1-yury.norov@gmail.com> References: <20251214235437.244125-1-yury.norov@gmail.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" The function calculates a Hamming weight of a bitmap starting from an arbitrary bit. Signed-off-by: Yury Norov (NVIDIA) --- include/linux/bitmap.h | 25 +++++++++++++++++++++++++ lib/bitmap.c | 28 ++++++++++++++++++++++++++++ lib/test_bitmap.c | 29 +++++++++++++++++++++++++++++ 3 files changed, 82 insertions(+) diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h index b0395e4ccf90..0f4789e1f7cb 100644 --- a/include/linux/bitmap.h +++ b/include/linux/bitmap.h @@ -57,6 +57,7 @@ struct device; * bitmap_weight(src, nbits) Hamming Weight: number set= bits * bitmap_weight_and(src1, src2, nbits) Hamming Weight of and'ed b= itmap * bitmap_weight_andnot(src1, src2, nbits) Hamming Weight of andnot'e= d bitmap + * bitmap_weight_from(src, start, nbits) Hamming Weight starting fr= om @start * bitmap_set(dst, pos, nbits) Set specified bit area * bitmap_clear(dst, pos, nbits) Clear specified bit area * bitmap_find_next_zero_area(buf, len, pos, n, mask) Find bit free area @@ -184,6 +185,8 @@ unsigned int __bitmap_weight_and(const unsigned long *b= itmap1, const unsigned long *bitmap2, unsigned int nbits); unsigned int __bitmap_weight_andnot(const unsigned long *bitmap1, const unsigned long *bitmap2, unsigned int nbits); +unsigned long __bitmap_weight_from(const unsigned long *bitmap, + unsigned int start, unsigned int nbits); void __bitmap_set(unsigned long *map, unsigned int start, int len); void __bitmap_clear(unsigned long *map, unsigned int start, int len); =20 @@ -479,6 +482,28 @@ unsigned long bitmap_weight_andnot(const unsigned long= *src1, return __bitmap_weight_andnot(src1, src2, nbits); } =20 +/** + * bitmap_weight_from - Hamming weight for a memory region + * @bitmap: The base address + * @start: The bitnumber to starts weighting + * @nbits: the bitmap size in bits + * + * Returns the number of set bits in the region, or > @nbits in case of er= ror. + */ +static __always_inline +unsigned long bitmap_weight_from(const unsigned long *bitmap, + unsigned int start, unsigned int nbits) +{ + if (small_const_nbits(nbits)) { + if (unlikely(start >=3D nbits)) + return nbits + 1; + + return hweight_long(*bitmap & GENMASK(nbits - 1, start)); + } + + return __bitmap_weight_from(bitmap, start, nbits); +} + static __always_inline void bitmap_set(unsigned long *map, unsigned int start, unsigned int nbits) { diff --git a/lib/bitmap.c b/lib/bitmap.c index 9dc526507875..698d15933c84 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -335,6 +335,27 @@ EXPORT_SYMBOL(__bitmap_subset); w; \ }) =20 +#define BITMAP_WEIGHT_FROM(FETCH, start, nbits) \ +({ \ + unsigned int __start =3D (start), __end =3D (nbits), idx, w; \ + \ + if (unlikely(__start >=3D __end)) { \ + w =3D __end + 1; \ + goto out; \ + } \ + \ + idx =3D __start / BITS_PER_LONG; \ + w =3D hweight_long((FETCH) & BITMAP_FIRST_WORD_MASK(__start)); \ + \ + for (idx++; idx * BITS_PER_LONG < __end; idx++) \ + w +=3D hweight_long(FETCH); \ + \ + if (__end % BITS_PER_LONG) \ + w +=3D hweight_long((FETCH) & BITMAP_LAST_WORD_MASK(__end)); \ +out: \ + w; \ +}) + unsigned int __bitmap_weight(const unsigned long *bitmap, unsigned int bit= s) { return BITMAP_WEIGHT(bitmap[idx], bits); @@ -361,6 +382,13 @@ unsigned int __bitmap_weighted_or(unsigned long *dst, = const unsigned long *bitma return BITMAP_WEIGHT(({dst[idx] =3D bitmap1[idx] | bitmap2[idx]; dst[idx]= ; }), bits); } =20 +unsigned long __bitmap_weight_from(const unsigned long *bitmap, + unsigned int start, unsigned int nbits) +{ + return BITMAP_WEIGHT_FROM(bitmap[idx], start, nbits); +} +EXPORT_SYMBOL(__bitmap_weight_from); + void __bitmap_set(unsigned long *map, unsigned int start, int len) { unsigned long *p =3D map + BIT_WORD(start); diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c index c83829ef557f..0fead99bf867 100644 --- a/lib/test_bitmap.c +++ b/lib/test_bitmap.c @@ -850,6 +850,34 @@ static void __init test_for_each_set_bit_from(void) expect_eq_bitmap(tmp, copy, 500); } } +static void __init test_bitmap_weight(void) +{ + unsigned int bit, w1, w2, w; + DECLARE_BITMAP(b, 30); + + bitmap_parselist("all:1/2", b, 30); + + /* Test inline implementation */ + w =3D bitmap_weight(b, 30); + w1 =3D bitmap_weight(b, 15); + w2 =3D bitmap_weight_from(b, 15, 30); + + expect_eq_uint(15, w); + expect_eq_uint(8, w1); + expect_eq_uint(7, w2); + + /* Test outline implementation */ + w =3D bitmap_weight(exp1, EXP1_IN_BITS); + for (bit =3D 0; bit < EXP1_IN_BITS; bit++) { + w1 =3D bitmap_weight(exp1, bit); + w2 =3D bitmap_weight_from(exp1, bit, EXP1_IN_BITS); + expect_eq_uint(w1 + w2, w); + } + + /* Test out-of-range */ + w =3D bitmap_weight_from(b, 31, 30); + expect_eq_uint(0, !!(w < 30)); +} =20 static void __init test_for_each_clear_bit(void) { @@ -1441,6 +1469,7 @@ static void __init selftest(void) test_bitmap_const_eval(); test_bitmap_read_write(); test_bitmap_read_perf(); + test_bitmap_weight(); test_bitmap_write_perf(); =20 test_find_nth_bit(); --=20 2.43.0