Skip to contentSkip to conversation

bitmap: add new tests

PATCH In review Yury Norov 3 participants 7 messages Mar 19 – Mar 24

Subsystems (3)
lore
Share & tools
lore

Yury Norov

author
#0 lore raw

cover bitmap: add new tests

- Test bitmap_weight() for correctness when tail bits are not zeroed.
- Explicitly test nbits == 0 case.

On top of bitmap-for-next.

Yury Norov (3):
bitmap: test bitmap_weight() for more
bitmap: exclude nbits == 0 cases from bitmap test
bitmap: add test_zero_nbits()

 lib/test_bitmap.c | 84 ++++++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 80 insertions(+), 4 deletions(-)
Signature · 1 line
2.43.0
author
#1 lore raw

PATCH 1/3 bitmap: test bitmap_weight() for more

Test the function for correctness when some bits are set in the last word of bitmap beyond nbits. This is motivated by commit a9dadc1c512807f9 ("powerpc/xive: Fix the size of the cpumask used in xive_find_target_in_mask()").

---
 lib/test_bitmap.c | 19 +++++++++++++++++++
 1 file changed, 19 insertions(+)
lib/test_bitmap.c +19 -0
index cd4cb36e42a5..eeb497016ed3 100644
@@ -858,6 +858,7 @@ 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);
 
@@ -877,6 +878,24 @@ static void __init test_bitmap_weight(void)
 		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)
Signature · 1 line
2.43.0
author
#2 lore raw

PATCH 2/3 bitmap: exclude nbits == 0 cases from bitmap test

In reply to Yury Norov

Bitmap API handles nbits == 0 in most cases correctly, i.e. it doesn't dereferene underlying bitmap and returns a sane value where convenient, or implementation defined, or undef.

Implicitly testing nbits == 0 case, however, may make an impression that this is a regular case. This is wrong. In most cases nbits == 0 is a sign of an error on a client side. The tests should not make such an implression.

This patch reworks the existing tests to not test nbits == 0. The following patch adds an explicit test for it with an appropriate precaution.

---
 lib/test_bitmap.c | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)
lib/test_bitmap.c +4 -4
index eeb497016ed3..b6f27c632c75 100644
@@ -653,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);
@@ -681,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);
@@ -714,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));
 
@@ -873,7 +873,7 @@ static void __init test_bitmap_weight(void)
 
 	/* Test outline implementation */
 	w = bitmap_weight(exp1, EXP1_IN_BITS);
-	for (bit = 0; bit < EXP1_IN_BITS; bit++) {
+	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);
Signature · 1 line
2.43.0
author
#3 lore raw

PATCH 3/3 bitmap: add test_zero_nbits()

In reply to Yury Norov

In most real-life cases, 0-length bitmap provided by user is a sign of an error. The API doesn't provide any guarantees on returned value, and the bitmap pointers are not dereferenced.

---
 lib/test_bitmap.c | 57 +++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 57 insertions(+)
lib/test_bitmap.c +57 -0
index b6f27c632c75..7a61ea858837 100644
@@ -1467,6 +1467,62 @@ static void __init test_bitmap_write_perf(void)
 	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
 
 static void __init selftest(void)
@@ -1490,6 +1546,7 @@ static void __init selftest(void)
 	test_bitmap_read_perf();
 	test_bitmap_weight();
 	test_bitmap_write_perf();
+	test_zero_nbits();
 
 	test_find_nth_bit();
 	test_for_each_set_bit();
Signature · 1 line
2.43.0
#4 lore raw

Re: [PATCH 3/3] bitmap: add test_zero_nbits()

kernel test robot noticed the following build errors:

Hi Yury,

kernel test robot noticed the following build errors:

[auto build test ERROR on next-20260318]
[cannot apply to akpm-mm/mm-nonmm-unstable v7.0-rc4 v7.0-rc3 v7.0-rc2 linus/master v7.0-rc4] [If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]

url:    https://github.com/intel-lab-lkp/linux/commits/Yury-Norov/bitmap-test-bitmap_weight-for-more/20260319-221930
base:   next-20260318
patch link:    https://lore.kernel.org/r/20260319004349.849281-4-ynorov%40nvidia.com
patch subject: [PATCH 3/3] bitmap: add test_zero_nbits()
config: nios2-allmodconfig (https://download.01.org/0day-ci/archive/20260322/[email protected]/config)
compiler: nios2-linux-gcc (GCC) 11.5.0
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20260322/[email protected]/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <[email protected]>
| Closes: https://lore.kernel.org/oe-kbuild-all/[email protected]/

All errors (new ones prefixed by >>, old ones prefixed by <<):

>> ERROR: modpost: "__bitmap_or_equal" [lib/test_bitmap.ko] undefined!

ERROR: modpost: "__bitmap_weighted_or" [lib/test_bitmap.ko] undefined!

Signature · 2 lines
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki
author
#5 lore raw

Re: [PATCH 3/3] bitmap: add test_zero_nbits()

Quoted 6 lines · kernel test robot

Hi Yury,

kernel test robot noticed the following build errors:

[auto build test ERROR on next-20260318]
[cannot apply to akpm-mm/mm-nonmm-unstable v7.0-rc4 v7.0-rc3 v7.0-rc2 linus/master v7.0-rc4]

Just as said in cover-letter: apply it on top of -next, or bitmap-for-next.

Applying this in bitmap-for-next for testing.

Thanks,
Yury

Quoted 25 lines

[If your patch is applied to the wrong git tree, kindly drop us a note. And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]

url:    https://github.com/intel-lab-lkp/linux/commits/Yury-Norov/bitmap-test-bitmap_weight-for-more/20260319-221930
base:   next-20260318
patch link:    https://lore.kernel.org/r/20260319004349.849281-4-ynorov%40nvidia.com
patch subject: [PATCH 3/3] bitmap: add test_zero_nbits()
config: nios2-allmodconfig (https://download.01.org/0day-ci/archive/20260322/[email protected]/config)
compiler: nios2-linux-gcc (GCC) 11.5.0
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20260322/[email protected]/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <[email protected]>
| Closes: https://lore.kernel.org/oe-kbuild-all/[email protected]/

All errors (new ones prefixed by >>, old ones prefixed by <<):

Quoted 1 line
Quoted 1 line

ERROR: modpost: "__bitmap_or_equal" [lib/test_bitmap.ko] undefined!

ERROR: modpost: "__bitmap_weighted_or" [lib/test_bitmap.ko] undefined!

Signature · 2 lines
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki
#6 lore raw

Re: [PATCH 3/3] bitmap: add test_zero_nbits()

Quoted 10 lines · Yury Norov
Quoted 6 lines · kernel test robot

Hi Yury,

kernel test robot noticed the following build errors:

[auto build test ERROR on next-20260318]
[cannot apply to akpm-mm/mm-nonmm-unstable v7.0-rc4 v7.0-rc3 v7.0-rc2 linus/master v7.0-rc4]

Just as said in cover-letter: apply it on top of -next, or bitmap-for-next.

Got it, sorry for the false report. The report is based on next-20260318, which should use next-20260319 as latest base.

Quoted 32 lines

Applying this in bitmap-for-next for testing.

Thanks,
Yury

Quoted 25 lines

[If your patch is applied to the wrong git tree, kindly drop us a note. And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]

url:    https://github.com/intel-lab-lkp/linux/commits/Yury-Norov/bitmap-test-bitmap_weight-for-more/20260319-221930
base:   next-20260318
patch link:    https://lore.kernel.org/r/20260319004349.849281-4-ynorov%40nvidia.com
patch subject: [PATCH 3/3] bitmap: add test_zero_nbits()
config: nios2-allmodconfig (https://download.01.org/0day-ci/archive/20260322/[email protected]/config)
compiler: nios2-linux-gcc (GCC) 11.5.0
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20260322/[email protected]/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <[email protected]>
| Closes: https://lore.kernel.org/oe-kbuild-all/[email protected]/

All errors (new ones prefixed by >>, old ones prefixed by <<):

Quoted 1 line
Quoted 1 line

ERROR: modpost: "__bitmap_or_equal" [lib/test_bitmap.ko] undefined!

ERROR: modpost: "__bitmap_weighted_or" [lib/test_bitmap.ko] undefined!

Signature · 2 lines
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki