[PATCH 1/2] bitmap: add bitmap_weight_from()

[PATCH 1/2] bitmap: add bitmap_weight_from()

[Yury Norov]

From: Yury Norov (NVIDIA) <yury.norov@gmail.com>

bitmap_weight_from is useful in topo_unit_count() and potentially
more spots.

Signed-off-by: Yury Norov (NVIDIA) <yury.norov@gmail.com>
---
 include/linux/bitmap.h | 11 +++++++++++
 lib/bitmap.c           | 28 ++++++++++++++++++++++++++++
 2 files changed, 39 insertions(+)

diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h
index 595217b7a6e7..3cde3bd766b7 100644
--- a/include/linux/bitmap.h
+++ b/include/linux/bitmap.h
@@ -56,6 +56,7 @@ struct device;
  *  bitmap_weight(src, nbits)                   Hamming Weight: number set bits
  *  bitmap_weight_and(src1, src2, nbits)        Hamming Weight of and'ed bitmap
  *  bitmap_weight_andnot(src1, src2, nbits)     Hamming Weight of andnot'ed bitmap
+ *  bitmap_weight_from(src, start, nbits)       Hamming Weight starting from @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
@@ -181,6 +182,8 @@ unsigned int __bitmap_weight_and(const unsigned long *bitmap1,
 				 const unsigned long *bitmap2, unsigned int nbits);
 unsigned int __bitmap_weight_andnot(const unsigned long *bitmap1,
 				    const unsigned long *bitmap2, unsigned int nbits);
+unsigned int __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);
 
@@ -446,6 +449,14 @@ unsigned int bitmap_weight(const unsigned long *src, unsigned int nbits)
 	return __bitmap_weight(src, nbits);
 }
 
+static __always_inline
+unsigned int bitmap_weight_from(const unsigned long *src, unsigned int start, unsigned int nbits)
+{
+	if (small_const_nbits(start + nbits - 1))
+		return hweight_long(*src & GENMASK(start + nbits - 1, start));
+	return __bitmap_weight_from(src, start, nbits);
+}
+
 static __always_inline
 unsigned long bitmap_weight_and(const unsigned long *src1,
 				const unsigned long *src2, unsigned int nbits)
diff --git a/lib/bitmap.c b/lib/bitmap.c
index b97692854966..eb9905071e3b 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -335,12 +335,40 @@ EXPORT_SYMBOL(__bitmap_subset);
 	w;									\
 })
 
+#define BITMAP_WEIGHT_FROM(FETCH, start, bits)					\
+({										\
+	unsigned long __start = (start), __bits = (bits);			\
+	unsigned int idx, w = 0;						\
+										\
+	if (unlikely(__start >= bits))						\
+		goto out;							\
+										\
+	idx = __start / BITS_PER_LONG;						\
+	w = (FETCH) & BITMAP_FIRST_WORD_MASK(__start);				\
+										\
+	for (++idx; idx < __bits / BITS_PER_LONG; idx++)			\
+		w += hweight_long(FETCH);					\
+										\
+	if (__bits % BITS_PER_LONG)						\
+		w += hweight_long((FETCH) & BITMAP_LAST_WORD_MASK(__bits));	\
+										\
+out:										\
+	w;									\
+})
+
 unsigned int __bitmap_weight(const unsigned long *bitmap, unsigned int bits)
 {
 	return BITMAP_WEIGHT(bitmap[idx], bits);
 }
 EXPORT_SYMBOL(__bitmap_weight);
 
+unsigned int __bitmap_weight_from(const unsigned long *bitmap,
+					unsigned int start, unsigned int bits)
+{
+	return BITMAP_WEIGHT_FROM(bitmap[idx], start, bits);
+}
+EXPORT_SYMBOL(__bitmap_weight_from);
+
 unsigned int __bitmap_weight_and(const unsigned long *bitmap1,
 				const unsigned long *bitmap2, unsigned int bits)
 {
-- 
2.43.0

Re: [PATCH 1/2] bitmap: add bitmap_weight_from()

[Thomas Gleixner]

On Sat, Jul 19 2025 at 21:41, Yury Norov wrote:
>  
> +#define BITMAP_WEIGHT_FROM(FETCH, start, bits)				\
> +({										\
> +	unsigned long __start = (start), __bits = (bits);			\
> +	unsigned int idx, w = 0;						\
> +										\
> +	if (unlikely(__start >= bits))						\
> +		goto out;							\
> +										\
> +	idx = __start / BITS_PER_LONG;						\
> +	w = (FETCH) & BITMAP_FIRST_WORD_MASK(__start);				\

So this expands to

        w = bitmap[idx] & (~0UL << ((start) & (BITS_PER_LONG - 1)));

Which means @w contains the content of the first bitmap word except for
the masked off bits. Let's assume @start is 0 and @bits is 32. Therefore
@idx is 0.

Assume further bitmap[idx] is all ones, which means 64bits set on a
64bit system. That results in

      w = bitmap[0] & (~0UL << ((0) & (BITS_PER_LONG - 1)));
-->   w = 0xFFFFFFFFFFFFFFFF & (0xFFFFFFFFFFFFFFFF << (0 & 0x3F));
-->   w = 0xFFFFFFFFFFFFFFFF;

which is obviously bogus.

> +	for (++idx; idx < __bits / BITS_PER_LONG; idx++)			\
> +		w += hweight_long(FETCH);					\

Evaluates to false

> +	if (__bits % BITS_PER_LONG)						\

Evaluates to true.

> +		w += hweight_long((FETCH) & BITMAP_LAST_WORD_MASK(__bits));	\

So this is executed and evaluates to:

      w += hweight_long(bitmap[1] & (~0UL >> (-(32UL) & (BITS_PER_LONG - 1))));

Let's assume the second word contains all ones as well.

-->   w += hweight_long(0xFFFFFFFFFFFFFFFF & (0xFFFFFFFFFFFFFFFF >> (0xFFFFFFFFFFFFFFE0 & 0x3F)));
-->   w += hweight_long(0xFFFFFFFFFFFFFFFF & (0xFFFFFFFFFFFFFFFF >> (0x20)));
-->   w += hweight_long(0xFFFFFFFFFFFFFFFF & 0xFFFFFFFF);

-->   w += 32;

Due to the wraparound of the addition it results in

      w = 31

which is not making the bogosity above more correct. And no, you can't
just fix up the initial assignment to @w:

	w = hweight_long((FETCH) & BITMAP_FIRST_WORD_MASK(__start);

because then the result is 32 + 32 == 64 as the final clause is
unconditionally executed.

Something like this should work:

        unsigned int idx, maxidx, w = 0;

	idx = start / BITS_PER_LONG;
	w = hweight_long((FETCH) & BITMAP_FIRST_WORD_MASK((unsigned long)start));

        maxidx = bits / BITS_PER_LONG;
        for (idx++; idx < maxidx; idx++)
        	w += hweight_long((FETCH));

        if (maxidx * BITS_PER_LONG < bits)
        	w += hweight_long((FETCH) & BITMAP_LAST_WORD_MASK((unsigned long)bits));
        
No?

Thanks,

        tglx

[PATCH 0/2] x86/topology: add bitmap_weight_from() and use it in topo_unit_count()

[Yury Norov (NVIDIA)]

Currently the function open-codes the missing bitmap_weight_from() with
a for-loop, which is known to be less effective. Add the helper and
switch topo_unit_count() to using it.

Yury Norov (NVIDIA) (2):
  bitmap: add bitmap_weight_from()
  topology: use bitmap_weight_from()

 arch/x86/kernel/cpu/topology.c |  8 ++------
 include/linux/bitmap.h         | 25 +++++++++++++++++++++++++
 lib/bitmap.c                   | 28 ++++++++++++++++++++++++++++
 lib/test_bitmap.c              | 29 +++++++++++++++++++++++++++++
 4 files changed, 84 insertions(+), 6 deletions(-)

-- 
2.43.0

[PATCH 1/2] bitmap: add bitmap_weight_from()

[Yury Norov (NVIDIA)]

The function calculates a Hamming weight of a bitmap starting from an
arbitrary bit.

Signed-off-by: Yury Norov (NVIDIA) <yury.norov@gmail.com>
---
 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 bitmap
  *  bitmap_weight_andnot(src1, src2, nbits)     Hamming Weight of andnot'ed bitmap
+ *  bitmap_weight_from(src, start, nbits)       Hamming Weight starting from @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 *bitmap1,
 				 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);
 
@@ -479,6 +482,28 @@ unsigned long bitmap_weight_andnot(const unsigned long *src1,
 	return __bitmap_weight_andnot(src1, src2, nbits);
 }
 
+/**
+ * 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 error.
+ */
+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 >= 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;									\
 })
 
+#define BITMAP_WEIGHT_FROM(FETCH, start, nbits)	\
+({										\
+	unsigned int __start = (start), __end = (nbits), idx, w;		\
+										\
+	if (unlikely(__start >= __end)) {					\
+		w = __end + 1;							\
+		goto out;							\
+	}									\
+										\
+	idx = __start / BITS_PER_LONG;						\
+	w = hweight_long((FETCH) & BITMAP_FIRST_WORD_MASK(__start));		\
+										\
+	for (idx++; idx * BITS_PER_LONG < __end; idx++)				\
+		w += hweight_long(FETCH);					\
+										\
+	if (__end % BITS_PER_LONG)						\
+		w += hweight_long((FETCH) & BITMAP_LAST_WORD_MASK(__end));	\
+out:										\
+	w;									\
+})
+
 unsigned int __bitmap_weight(const unsigned long *bitmap, unsigned int bits)
 {
 	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] = bitmap1[idx] | bitmap2[idx]; dst[idx]; }), bits);
 }
 
+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 = 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 = bitmap_weight(b, 30);
+	w1 = bitmap_weight(b, 15);
+	w2 = 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 = bitmap_weight(exp1, EXP1_IN_BITS);
+	for (bit = 0; bit < EXP1_IN_BITS; bit++) {
+		w1 = bitmap_weight(exp1, bit);
+		w2 = bitmap_weight_from(exp1, bit, EXP1_IN_BITS);
+		expect_eq_uint(w1 + w2, w);
+	}
+
+	/* Test out-of-range */
+	w = bitmap_weight_from(b, 31, 30);
+	expect_eq_uint(0, !!(w < 30));
+}
 
 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();
 
 	test_find_nth_bit();
-- 
2.43.0

[PATCH 2/2] x86/topology: use bitmap_weight_from()

[Yury Norov (NVIDIA)]

Switch topo_unit_count() to use bitmap_weight_from().

Signed-off-by: Yury Norov (NVIDIA) <yury.norov@gmail.com>
---
 arch/x86/kernel/cpu/topology.c | 8 ++------
 1 file changed, 2 insertions(+), 6 deletions(-)

diff --git a/arch/x86/kernel/cpu/topology.c b/arch/x86/kernel/cpu/topology.c
index f55ea3cdbf88..ba7142f417ad 100644
--- a/arch/x86/kernel/cpu/topology.c
+++ b/arch/x86/kernel/cpu/topology.c
@@ -204,15 +204,11 @@ static __init bool check_for_real_bsp(u32 apic_id)
 static unsigned int topo_unit_count(u32 lvlid, enum x86_topology_domains at_level,
 				    unsigned long *map)
 {
-	unsigned int id, end, cnt = 0;
+	unsigned int end;
 
 	/* Calculate the exclusive end */
 	end = lvlid + (1U << x86_topo_system.dom_shifts[at_level]);
-
-	/* Unfortunately there is no bitmap_weight_range() */
-	for (id = find_next_bit(map, end, lvlid); id < end; id = find_next_bit(map, end, ++id))
-		cnt++;
-	return cnt;
+	return bitmap_weight_from(map, lvlid, end);
 }
 
 static __init void topo_register_apic(u32 apic_id, u32 acpi_id, bool present)
-- 
2.43.0

Re: [PATCH 1/2] bitmap: add bitmap_weight_from()

[Ingo Molnar]

* Yury Norov (NVIDIA) <yury.norov@gmail.com> wrote:

> The function calculates a Hamming weight of a bitmap starting from an
> arbitrary bit.
> 
> Signed-off-by: Yury Norov (NVIDIA) <yury.norov@gmail.com>
> ---
>  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 bitmap
>   *  bitmap_weight_andnot(src1, src2, nbits)     Hamming Weight of andnot'ed bitmap
> + *  bitmap_weight_from(src, start, nbits)       Hamming Weight starting from @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 *bitmap1,
>  				 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);
>  
> @@ -479,6 +482,28 @@ unsigned long bitmap_weight_andnot(const unsigned long *src1,
>  	return __bitmap_weight_andnot(src1, src2, nbits);
>  }
>  
> +/**
> + * 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 error.
> + */
> +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 >= nbits))
> +			return nbits + 1;
> +
> +		return hweight_long(*bitmap & GENMASK(nbits - 1, start));
> +	}
> +
> +	return __bitmap_weight_from(bitmap, start, nbits);

The 'nbits' name and description is actively misleading: it suggests
the number of bits searched, like bitmap_write() has nbits for
the number of bits written, but in reality it's the *end* index,
not the size of the area to search.

Note how it contrasts with how bitmap_write(..,start,nbits)
works.

So please rename it to something more suitable, like 'end', or so.

Thanks,

	Ingo