Merge tag 'bitmap-for-v7.1' of https://github.com/norov/linux

Pull bitmap updates from Yury Norov:

 - new API: bitmap_weight_from() and bitmap_weighted_xor() (Yury)

 - drop unused __find_nth_andnot_bit() (Yury)

 - new tests and test improvements (Andy, Akinobu, Yury)

 - fixes for count_zeroes API (Yury)

 - cleanup bitmap_print_to_pagebuf() mess (Yury)

 - documentation updates (Andy, Kai, Kit).

* tag 'bitmap-for-v7.1' of https://github.com/norov/linux: (24 commits)
  bitops: Update kernel-doc for sign_extendXX()
  powerpc/xive: simplify xive_spapr_debug_show()
  thermal: intel: switch cpumask_get() to using cpumask_print_to_pagebuf()
  coresight: don't use bitmap_print_to_pagebuf()
  lib/prime_numbers: drop temporary buffer in dump_primes()
  drm/xe: switch xe_pagefault_queue_init() to using bitmap_weighted_or()
  ice: use bitmap_empty() in ice_vf_has_no_qs_ena
  ice: use bitmap_weighted_xor() in ice_find_free_recp_res_idx()
  bitmap: introduce bitmap_weighted_xor()
  bitmap: add test_zero_nbits()
  bitmap: exclude nbits == 0 cases from bitmap test
  bitmap: test bitmap_weight() for more
  asm-generic/bitops: Fix a comment typo in instrumented-atomic.h
  bitops: fix kernel-doc parameter name for parity8()
  lib: count_zeros: unify count_{leading,trailing}_zeros()
  lib: count_zeros: fix 32/64-bit inconsistency in count_trailing_zeros()
  lib: crypto: fix comments for count_leading_zeros()
  x86/topology: use bitmap_weight_from()
  bitmap: add bitmap_weight_from()
  lib/find_bit_benchmark: avoid clearing randomly filled bitmap in test_find_first_bit()
  ...

6 files changed, 144 insertions, 36 deletions

diff --git a/lib/bitmap.c b/lib/bitmap.c
index 9dc526507875..b9bfa157e095 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -69,6 +69,7 @@ bool __bitmap_or_equal(const unsigned long *bitmap1,
 	tmp = (bitmap1[k] | bitmap2[k]) ^ bitmap3[k];
 	return (tmp & BITMAP_LAST_WORD_MASK(bits)) == 0;
 }
+EXPORT_SYMBOL(__bitmap_or_equal);
 
 void __bitmap_complement(unsigned long *dst, const unsigned long *src, unsigned int bits)
 {
@@ -360,6 +361,14 @@ unsigned int __bitmap_weighted_or(unsigned long *dst, const unsigned long *bitma
 {
 	return BITMAP_WEIGHT(({dst[idx] = bitmap1[idx] | bitmap2[idx]; dst[idx]; }), bits);
 }
+EXPORT_SYMBOL(__bitmap_weighted_or);
+
+unsigned int __bitmap_weighted_xor(unsigned long *dst, const unsigned long *bitmap1,
+				  const unsigned long *bitmap2, unsigned int bits)
+{
+	return BITMAP_WEIGHT(({dst[idx] = bitmap1[idx] ^ bitmap2[idx]; dst[idx]; }), bits);
+}
+EXPORT_SYMBOL(__bitmap_weighted_xor);
 
 void __bitmap_set(unsigned long *map, unsigned int start, int len)
 {
diff --git a/lib/crypto/mpi/longlong.h b/lib/crypto/mpi/longlong.h
index b6fa1d08fb55..6d31c3a729f1 100644
--- a/lib/crypto/mpi/longlong.h
+++ b/lib/crypto/mpi/longlong.h
@@ -66,12 +66,12 @@
  * denominator).  Like udiv_qrnnd but the numbers are signed.  The quotient
  * is rounded towards 0.
  *
- * 5) count_leading_zeros(count, x) counts the number of zero-bits from the
+ * 5) count_leading_zeros(x) counts the number of zero-bits from the
  * msb to the first non-zero bit in the UWtype X.  This is the number of
- * steps X needs to be shifted left to set the msb.  Undefined for X == 0,
- * unless the symbol COUNT_LEADING_ZEROS_0 is defined to some value.
+ * steps X needs to be shifted left to set the msb.
+ * count_leading_zeros(0) == BITS_PER_LONG
  *
- * 6) count_trailing_zeros(count, x) like count_leading_zeros, but counts
+ * 6) count_trailing_zeros() like count_leading_zeros(), but counts
  * from the least significant end.
  *
  * 7) add_ssaaaa(high_sum, low_sum, high_addend_1, low_addend_1,
diff --git a/lib/find_bit.c b/lib/find_bit.c
index 5a0066c26d9a..5ac52dfce730 100644
--- a/lib/find_bit.c
+++ b/lib/find_bit.c
@@ -172,13 +172,6 @@ unsigned long __find_nth_and_bit(const unsigned long *addr1, const unsigned long
 }
 EXPORT_SYMBOL(__find_nth_and_bit);
 
-unsigned long __find_nth_andnot_bit(const unsigned long *addr1, const unsigned long *addr2,
-				 unsigned long size, unsigned long n)
-{
-	return FIND_NTH_BIT(addr1[idx] & ~addr2[idx], size, n);
-}
-EXPORT_SYMBOL(__find_nth_andnot_bit);
-
 unsigned long __find_nth_and_andnot_bit(const unsigned long *addr1,
 					const unsigned long *addr2,
 					const unsigned long *addr3,
diff --git a/lib/find_bit_benchmark.c b/lib/find_bit_benchmark.c
index 402e160e7186..00d9dc61cd46 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;
 
 /*
- * 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 int __init test_find_first_bit(const void *bitmap, unsigned long len)
 {
+	static DECLARE_BITMAP(cp, BITMAP_LEN) __initdata;
 	unsigned long i, cnt;
 	ktime_t time;
 
+	bitmap_copy(cp, bitmap, BITMAP_LEN);
+
 	time = ktime_get();
 	for (cnt = i = 0; i < len; cnt++) {
-		i = find_first_bit(bitmap, len);
-		__clear_bit(i, bitmap);
+		i = find_first_bit(cp, len);
+		__clear_bit(i, cp);
 	}
 	time = ktime_get() - time;
 	pr_err("find_first_bit:     %18llu ns, %6ld iterations\n", time, cnt);
@@ -49,7 +51,8 @@ static int __init test_find_first_bit(void *bitmap, unsigned long len)
 	return 0;
 }
 
-static int __init test_find_first_and_bit(void *bitmap, const void *bitmap2, unsigned long len)
+static int __init test_find_first_and_bit(const void *bitmap, const void *bitmap2,
+		unsigned long len)
 {
 	static DECLARE_BITMAP(cp, BITMAP_LEN) __initdata;
 	unsigned long i, cnt;
diff --git a/lib/math/tests/prime_numbers_kunit.c b/lib/math/tests/prime_numbers_kunit.c
index 2f1643208c66..55ac160c6dfa 100644
--- a/lib/math/tests/prime_numbers_kunit.c
+++ b/lib/math/tests/prime_numbers_kunit.c
@@ -8,12 +8,10 @@
 
 static void dump_primes(void *ctx, const struct primes *p)
 {
-	static char buf[PAGE_SIZE];
 	struct kunit_suite *suite = ctx;
 
-	bitmap_print_to_pagebuf(true, buf, p->primes, p->sz);
-	kunit_info(suite, "primes.{last=%lu, .sz=%lu, .primes[]=...x%lx} = %s",
-		   p->last, p->sz, p->primes[BITS_TO_LONGS(p->sz) - 1], buf);
+	kunit_info(suite, "primes.{last=%lu, .sz=%lu, .primes[]=...x%lx} = %*pbl",
+		   p->last, p->sz, p->primes[BITS_TO_LONGS(p->sz) - 1], (int)p->sz, p->primes);
 }
 
 static void prime_numbers_test(struct kunit *test)
diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c
index c83829ef557f..69813c10e6c0 100644
--- a/lib/test_bitmap.c
+++ b/lib/test_bitmap.c
@@ -354,18 +354,22 @@ static void __init test_replace(void)
 
 static const unsigned long sg_mask[] __initconst = {
 	BITMAP_FROM_U64(0x000000000000035aULL),
+	BITMAP_FROM_U64(0x0000000000000000ULL),
 };
 
 static const unsigned long sg_src[] __initconst = {
 	BITMAP_FROM_U64(0x0000000000000667ULL),
+	BITMAP_FROM_U64(0x0000000000000000ULL),
 };
 
 static const unsigned long sg_gather_exp[] __initconst = {
 	BITMAP_FROM_U64(0x0000000000000029ULL),
+	BITMAP_FROM_U64(0x0000000000000000ULL),
 };
 
 static const unsigned long sg_scatter_exp[] __initconst = {
 	BITMAP_FROM_U64(0x000000000000021aULL),
+	BITMAP_FROM_U64(0x0000000000000000ULL),
 };
 
 static void __init test_bitmap_sg(void)
@@ -379,18 +383,18 @@ static void __init test_bitmap_sg(void)
 	/* Simple gather call */
 	bitmap_zero(bmap_gather, 100);
 	bitmap_gather(bmap_gather, sg_src, sg_mask, nbits);
-	expect_eq_bitmap(sg_gather_exp, bmap_gather, nbits);
+	expect_eq_bitmap(sg_gather_exp, bmap_gather, 100);
 
 	/* Simple scatter call */
 	bitmap_zero(bmap_scatter, 100);
 	bitmap_scatter(bmap_scatter, sg_src, sg_mask, nbits);
-	expect_eq_bitmap(sg_scatter_exp, bmap_scatter, nbits);
+	expect_eq_bitmap(sg_scatter_exp, bmap_scatter, 100);
 
 	/* Scatter/gather relationship */
 	bitmap_zero(bmap_tmp, 100);
 	bitmap_gather(bmap_tmp, bmap_scatter, sg_mask, nbits);
 	bitmap_scatter(bmap_res, bmap_tmp, sg_mask, nbits);
-	expect_eq_bitmap(bmap_scatter, bmap_res, nbits);
+	expect_eq_bitmap(bmap_scatter, bmap_res, 100);
 }
 
 #define PARSE_TIME	0x1
@@ -520,8 +524,7 @@ static void __init test_bitmap_parselist(void)
 		}
 
 		if (ptest.flags & PARSE_TIME)
-			pr_info("parselist: %d: input is '%s' OK, Time: %llu\n",
-					i, ptest.in, time);
+			pr_info("parselist('%s'):\t%llu\n", ptest.in, time);
 
 #undef ptest
 	}
@@ -544,22 +547,22 @@ static void __init test_bitmap_printlist(void)
 		goto out;
 
 	time = ktime_get();
-	ret = bitmap_print_to_pagebuf(true, buf, bmap, PAGE_SIZE * 8);
+	ret = scnprintf(buf, PAGE_SIZE, "%*pbl", (int)PAGE_SIZE * 8, bmap);
 	time = ktime_get() - time;
 
-	if (ret != slen + 1) {
-		pr_err("bitmap_print_to_pagebuf: result is %d, expected %d\n", ret, slen);
+	if (ret != slen) {
+		pr_err("scnprintf(\"%%*pbl\"): result is %d, expected %d\n", ret, slen);
 		failed_tests++;
 		goto out;
 	}
 
 	if (strncmp(buf, expected, slen)) {
-		pr_err("bitmap_print_to_pagebuf: result is %s, expected %s\n", buf, expected);
+		pr_err("scnprintf(\"%%*pbl\"): result is %s, expected %s\n", buf, expected);
 		failed_tests++;
 		goto out;
 	}
 
-	pr_info("bitmap_print_to_pagebuf: input is '%s', Time: %llu\n", buf, time);
+	pr_info("scnprintf(\"%%*pbl\", '%s'):\t%llu\n", buf, time);
 out:
 	kfree(buf);
 	kfree(bmap);
@@ -650,7 +653,7 @@ static void __init test_bitmap_arr32(void)
 
 	memset(arr, 0xa5, sizeof(arr));
 
-	for (nbits = 0; nbits < EXP1_IN_BITS; ++nbits) {
+	for (nbits = 1; nbits < EXP1_IN_BITS; ++nbits) {
 		bitmap_to_arr32(arr, exp1, nbits);
 		bitmap_from_arr32(bmap2, arr, nbits);
 		expect_eq_bitmap(bmap2, exp1, nbits);
@@ -678,7 +681,7 @@ static void __init test_bitmap_arr64(void)
 
 	memset(arr, 0xa5, sizeof(arr));
 
-	for (nbits = 0; nbits < EXP1_IN_BITS; ++nbits) {
+	for (nbits = 1; nbits < EXP1_IN_BITS; ++nbits) {
 		memset(bmap2, 0xff, sizeof(arr));
 		bitmap_to_arr64(arr, exp1, nbits);
 		bitmap_from_arr64(bmap2, arr, nbits);
@@ -711,7 +714,7 @@ static void noinline __init test_mem_optimisations(void)
 	unsigned int start, nbits;
 
 	for (start = 0; start < 1024; start += 8) {
-		for (nbits = 0; nbits < 1024 - start; nbits += 8) {
+		for (nbits = 1; nbits < 1024 - start; nbits += 8) {
 			memset(bmap1, 0x5a, sizeof(bmap1));
 			memset(bmap2, 0x5a, sizeof(bmap2));
 
@@ -851,6 +854,50 @@ static void __init test_for_each_set_bit_from(void)
 	}
 }
 
+static void __init test_bitmap_weight(void)
+{
+	unsigned int bit, w1, w2, w;
+	DECLARE_BITMAP(b, 30);
+	DECLARE_BITMAP(b1, 128);
+
+	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 = 1; 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));
+
+	/*
+	 * Test bitmap_weight() for correctness in case of some bits set between
+	 * nbits and end of the last word.
+	 */
+	bitmap_fill(b1, 128);
+
+	/* Inline */
+	expect_eq_uint(30, bitmap_weight(b1, 30));
+	expect_eq_uint(100, bitmap_weight(b1, 100));
+
+	/* Outline */
+	for (int i  = 1; i < 128; i++)
+		expect_eq_uint(i, bitmap_weight(b1, i));
+}
+
 static void __init test_for_each_clear_bit(void)
 {
 	DECLARE_BITMAP(orig, 500);
@@ -1395,7 +1442,7 @@ static void __init test_bitmap_read_perf(void)
 		}
 	}
 	time = ktime_get() - time;
-	pr_info("Time spent in %s:\t%llu\n", __func__, time);
+	pr_info("%s:\t\t%llu\n", __func__, time);
 }
 
 static void __init test_bitmap_write_perf(void)
@@ -1417,7 +1464,63 @@ static void __init test_bitmap_write_perf(void)
 		}
 	}
 	time = ktime_get() - time;
-	pr_info("Time spent in %s:\t%llu\n", __func__, time);
+	pr_info("%s:\t\t%llu\n", __func__, time);
+}
+
+/*
+ * nbits == 0 is most commonly not a valid case. Bitmap users should revisit
+ * the caller logic. Bitmap API doesn't provide any guarantees on returned
+ * value. The pointers are not dereferenced. The return value is intentionally
+ * ignored.
+ */
+static void __init test_zero_nbits(void)
+{
+	static volatile __always_used unsigned long ret __initdata;
+
+	bitmap_clear(NULL, 0, 0);
+	bitmap_complement(NULL, NULL, 0);
+	bitmap_copy(NULL, NULL, 0);
+	bitmap_copy_clear_tail(NULL, NULL, 0);
+	bitmap_fill(NULL, 0);
+	bitmap_from_arr32(NULL, NULL, 0);
+	bitmap_from_arr64(NULL, NULL, 0);
+	bitmap_or(NULL, NULL, NULL, 0);
+	bitmap_set(NULL, 0, 0);
+	bitmap_shift_left(NULL, NULL, 0, 0);
+	bitmap_shift_right(NULL, NULL, 0, 0);
+	bitmap_to_arr32(NULL, NULL, 0);
+	bitmap_to_arr64(NULL, NULL, 0);
+	bitmap_write(NULL, 0, 0, 0);
+	bitmap_xor(NULL, NULL, NULL, 0);
+	bitmap_zero(NULL, 0);
+
+	ret = bitmap_and(NULL, NULL, NULL, 0);
+	ret = bitmap_empty(NULL, 0);
+	ret = bitmap_equal(NULL, NULL, 0);
+	ret = bitmap_full(NULL, 0);
+	ret = bitmap_or_equal(NULL, NULL, NULL, 0);
+	ret = bitmap_read(NULL, 0, 0);
+	ret = bitmap_subset(NULL, NULL, 0);
+	ret = bitmap_weight(NULL, 0);
+	ret = bitmap_weight_and(NULL, NULL, 0);
+	ret = bitmap_weight_andnot(NULL, NULL, 0);
+	ret = bitmap_weight_from(NULL, 0, 0);
+	ret = bitmap_weighted_or(NULL, NULL, NULL, 0);
+
+	ret = find_first_and_and_bit(NULL, NULL, NULL, 0);
+	ret = find_first_and_bit(NULL, NULL, 0);
+	ret = find_first_andnot_bit(NULL, NULL, 0);
+	ret = find_first_bit(NULL, 0);
+	ret = find_first_zero_bit(NULL, 0);
+	ret = find_last_bit(NULL, 0);
+	ret = find_next_and_bit(NULL, NULL, 0, 0);
+	ret = find_next_andnot_bit(NULL, NULL, 0, 0);
+	ret = find_next_bit(NULL, 0, 0);
+	ret = find_next_clump8(NULL, NULL, 0, 0);
+	ret = find_next_zero_bit(NULL, 0, 0);
+	ret = find_nth_and_bit(NULL, NULL, 0, 0);
+	ret = find_nth_bit(NULL, 0, 0);
+	ret = find_random_bit(NULL, 0);
 }
 
 #undef TEST_BIT_LEN
@@ -1441,7 +1544,9 @@ 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_zero_nbits();
 
 	test_find_nth_bit();
 	test_for_each_set_bit();