Skip to contentSkip to conversation

lib/tests: kunit for associative array

PATCH In review Jarkko Sakkinen 5 participants 10 messages Oct 14 – Oct 18

Subsystems (4)
lore
Share & tools
lore

Jarkko Sakkinen

author maintainer
#0 lore raw

PATCH 1/1 lib/tests: kunit for associative array

This is a kunit test for lib/assoc_array.c, which maintains a shadow model across assoc_array operations, and checks its integrity after every operation.

I wrote a draft version so that I could properly test 'assoc-array-fixes' tag at Linus' tree, and spent today rewriting a new more polished version with as good description as I could possibly could on how the seeded test keys were cherry-picked. Along the way I also tweaked the numbers to be a bit less messier set than in my original version.

The transcripts that follow were executed with this command-line:

    ./tools/testing/kunit/kunit.py run --raw_output assoc_array

With 'assoc-array-fixes' commits and its subsequent tag iterations all eight tests pass, and without them all of them fail.

---
 lib/Kconfig.debug             |  15 +
 lib/tests/Makefile            |   1 +
 lib/tests/assoc_array_kunit.c | 570 ++++++++++++++++++++++++++++++++++
 3 files changed, 586 insertions(+)
 create mode 100644 lib/tests/assoc_array_kunit.c
lib/Kconfig.debug +15 -0
index 6b24a2c89b84..3e8d3852f53c 100644
@@ -2857,6 +2857,21 @@ config HASHTABLE_KUNIT_TEST
 
 	  If unsure, say N.
 
+config ASSOC_ARRAY_KUNIT_TEST
+	tristate "KUnit test for assoc_array" if !KUNIT_ALL_TESTS
+	depends on KUNIT
+	default KUNIT_ALL_TESTS
+	select ASSOCIATIVE_ARRAY
+	help
+	  This builds the assoc_array KUnit test suite.
+	  It tests the basic functionality of the API defined in
+	  include/linux/assoc_array.h.
+
+	  For more information on KUnit and unit tests in general please refer
+	  to the KUnit documentation in Documentation/dev-tools/kunit/.
+
+	  If unsure, say N.
+
 config LINEAR_RANGES_TEST
 	tristate "KUnit test for linear_ranges"
 	depends on KUNIT
lib/tests/Makefile +1 -0
index 3cac3b63a752..107e16b4ebc1 100644
@@ -4,6 +4,7 @@
 
 # KUnit tests
 CFLAGS_bitfield_kunit.o := $(DISABLE_STRUCTLEAK_PLUGIN)
+obj-$(CONFIG_ASSOC_ARRAY_KUNIT_TEST) += assoc_array_kunit.o
 obj-$(CONFIG_BASE64_KUNIT) += base64_kunit.o
 obj-$(CONFIG_BITOPS_KUNIT) += bitops_kunit.o
 obj-$(CONFIG_BITFIELD_KUNIT) += bitfield_kunit.o
lib/tests/assoc_array_kunit.c new file +570 -0

570 lines not on this page · raw message

--
2.47.3

#1 lore raw
Quoted 10 lines · Jarkko Sakkinen

This is a kunit test for lib/assoc_array.c, which maintains a shadow model across assoc_array operations, and checks its integrity after every operation.

I wrote a draft version so that I could properly test 'assoc-array-fixes' tag at Linus' tree, and spent today rewriting a new more polished version with as good description as I could possibly could on how the seeded test keys were cherry-picked. Along the way I also tweaked the numbers to be a bit less messier set than in my original version.

Quoted 8 lines

The transcripts that follow were executed with this command-line:

    ./tools/testing/kunit/kunit.py run --raw_output assoc_array

With 'assoc-array-fixes' commits and its subsequent tag iterations all eight tests pass, and without them all of them fail.

Would this effort (and Linus's effort) be better spent on converting keyrings to use an rhashtable?

keyrings is the only user of assoc_array. So if it's made to use something else, assoc_array (all 1724 lines of it!) can just be deleted.

I understand assoc_array.c was intended to be for general use. But clearly that hasn't happened in the 13 years it's been in the kernel. Keyrings has always been its only user. All other kernel code needing a map data structure uses something else.

- Eric

author maintainer
#2 lore raw
Quoted 15 lines · Eric Biggers
Quoted 14 lines · Jarkko Sakkinen

This is a kunit test for lib/assoc_array.c, which maintains a shadow model across assoc_array operations, and checks its integrity after every operation.

I wrote a draft version so that I could properly test 'assoc-array-fixes' tag at Linus' tree, and spent today rewriting a new more polished version with as good description as I could possibly could on how the seeded test keys were cherry-picked. Along the way I also tweaked the numbers to be a bit less messier set than in my original version.

The transcripts that follow were executed with this command-line:

    ./tools/testing/kunit/kunit.py run --raw_output assoc_array
Quoted 7 lines
Quoted 4 lines

With 'assoc-array-fixes' commits and its subsequent tag iterations all eight tests pass, and without them all of them fail.

Would this effort (and Linus's effort) be better spent on converting keyrings to use an rhashtable?

It did cross my mind when I reviewed and tested those fixes but you are asking something that I would need at least a few hours to have any opinion.

We do bugs and QA to the end-of-life-cycle. We neither can predict exact time how such major overhaul would take, if we even want to do it. I don't know.

My brain is on this and I'm really bad at multitasking :-)

Quoted 10 lines

keyrings is the only user of assoc_array. So if it's made to use something else, assoc_array (all 1724 lines of it!) can just be deleted.

I understand assoc_array.c was intended to be for general use. But clearly that hasn't happened in the 13 years it's been in the kernel. Keyrings has always been its only user. All other kernel code needing a map data structure uses something else.

- Eric

Br, Jarkko

author maintainer
#3 lore raw
Quoted 28 lines · Jarkko Sakkinen
Quoted 15 lines · Eric Biggers
Quoted 14 lines · Jarkko Sakkinen

This is a kunit test for lib/assoc_array.c, which maintains a shadow model across assoc_array operations, and checks its integrity after every operation.

I wrote a draft version so that I could properly test 'assoc-array-fixes' tag at Linus' tree, and spent today rewriting a new more polished version with as good description as I could possibly could on how the seeded test keys were cherry-picked. Along the way I also tweaked the numbers to be a bit less messier set than in my original version.

The transcripts that follow were executed with this command-line:

    ./tools/testing/kunit/kunit.py run --raw_output assoc_array
Quoted 7 lines
Quoted 4 lines

With 'assoc-array-fixes' commits and its subsequent tag iterations all eight tests pass, and without them all of them fail.

Would this effort (and Linus's effort) be better spent on converting keyrings to use an rhashtable?

It did cross my mind when I reviewed and tested those fixes but you are asking something that I would need at least a few hours to have any opinion.

Quoted 5 lines

We do bugs and QA to the end-of-life-cycle. We neither can predict exact time how such major overhaul would take, if we even want to do it. I don't know.

My brain is on this and I'm really bad at multitasking :-)

If migration was done probably two-phase approach is what should sought after. I.e. keep the API and change the internals.

After that it is time for re-consideration because from that point there are multiple (API) paths forward.

Br, Jarkko

author maintainer
#4 lore raw
Quoted 33 lines · Jarkko Sakkinen
Quoted 32 lines · Jarkko Sakkinen
Quoted 15 lines · Eric Biggers
Quoted 14 lines · Jarkko Sakkinen

This is a kunit test for lib/assoc_array.c, which maintains a shadow model across assoc_array operations, and checks its integrity after every operation.

I wrote a draft version so that I could properly test 'assoc-array-fixes' tag at Linus' tree, and spent today rewriting a new more polished version with as good description as I could possibly could on how the seeded test keys were cherry-picked. Along the way I also tweaked the numbers to be a bit less messier set than in my original version.

The transcripts that follow were executed with this command-line:

    ./tools/testing/kunit/kunit.py run --raw_output assoc_array
Quoted 7 lines
Quoted 4 lines

With 'assoc-array-fixes' commits and its subsequent tag iterations all eight tests pass, and without them all of them fail.

Would this effort (and Linus's effort) be better spent on converting keyrings to use an rhashtable?

It did cross my mind when I reviewed and tested those fixes but you are asking something that I would need at least a few hours to have any opinion.

We do bugs and QA to the end-of-life-cycle. We neither can predict exact time how such major overhaul would take, if we even want to do it. I don't know.

Quoted 7 lines
Quoted 1 line

My brain is on this and I'm really bad at multitasking :-)

If migration was done probably two-phase approach is what should sought after. I.e. keep the API and change the internals.

After that it is time for re-consideration because from that point there are multiple (API) paths forward.

rhashtable is the best pick I think. xarray not so much given the data topology.

Br, Jarkko

#5 lore raw
In reply to Eric Biggers
Quoted 3 lines · Eric Biggers

Would this effort (and Linus's effort) be better spent on converting keyrings to use an rhashtable?

I agree that it would be lovely to just get rid of assoc_array, since this is the only use for it, and no other use has grown in the (many) years it's been around.

Linus

#6 lore raw
In reply to Jarkko Sakkinen
kernel test robot noticed the following build warnings:

Hi Jarkko,

kernel test robot noticed the following build warnings:

[auto build test WARNING on akpm-mm/mm-nonmm-unstable]
[also build test WARNING on linus/master v7.3-rc7]
[cannot apply to next-20261012]
[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/Jarkko-Sakkinen/lib-tests-kunit-for-associative-array/20261014-190138
base:   https://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm.git mm-nonmm-unstable
patch link:    https://lore.kernel.org/r/20261014160144.1835860-1-jarkko%40kernel.org
patch subject: [PATCH] lib/tests: kunit for associative array
config: arm-randconfig-1001-20261016 (https://download.01.org/0day-ci/archive/20261016/[email protected]/config)
compiler: arm-linux-gnueabi-gcc (GCC) 8.5.0
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20261016/[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 warnings (new ones prefixed by >>):

>> lib/tests/assoc_array_kunit.c:62:2: warning: conversion from 'long long unsigned int' to 'long unsigned int' changes value from '16045690984503098046' to '3405691582' [-Woverflow]
     0xdeadbeefcafebabeUL, 0x0000000000000010UL,
     ^~~~~~~~~~~~~~~~~~~~
   lib/tests/assoc_array_kunit.c:63:2: warning: conversion from 'long long unsigned int' to 'long unsigned int' changes value from '16045690984503098046' to '3405691582' [-Woverflow]
     0xdeadbeefcafebabeUL, 0x0000000000000020UL,
     ^~~~~~~~~~~~~~~~~~~~
   lib/tests/assoc_array_kunit.c:64:2: warning: conversion from 'long long unsigned int' to 'long unsigned int' changes value from '16045690984503098046' to '3405691582' [-Woverflow]
     0xdeadbeefcafebabeUL, 0x0000000000000030UL,
     ^~~~~~~~~~~~~~~~~~~~
   lib/tests/assoc_array_kunit.c:65:2: warning: conversion from 'long long unsigned int' to 'long unsigned int' changes value from '16045690984503098046' to '3405691582' [-Woverflow]
     0xdeadbeefcafebabeUL, 0x0000000000000040UL,
     ^~~~~~~~~~~~~~~~~~~~
   lib/tests/assoc_array_kunit.c:66:2: warning: conversion from 'long long unsigned int' to 'long unsigned int' changes value from '16045690984503098046' to '3405691582' [-Woverflow]
     0xdeadbeefcafebabeUL, 0x0000000000000050UL,
     ^~~~~~~~~~~~~~~~~~~~
   lib/tests/assoc_array_kunit.c:67:2: warning: conversion from 'long long unsigned int' to 'long unsigned int' changes value from '16045690984503098046' to '3405691582' [-Woverflow]
     0xdeadbeefcafebabeUL, 0x0000000000000060UL,
     ^~~~~~~~~~~~~~~~~~~~
   lib/tests/assoc_array_kunit.c:68:2: warning: conversion from 'long long unsigned int' to 'long unsigned int' changes value from '16045690984503098046' to '3405691582' [-Woverflow]
     0xdeadbeefcafebabeUL, 0x0000000000000070UL,
     ^~~~~~~~~~~~~~~~~~~~
   lib/tests/assoc_array_kunit.c:69:2: warning: conversion from 'long long unsigned int' to 'long unsigned int' changes value from '16045690984503098046' to '3405691582' [-Woverflow]
     0xdeadbeefcafebabeUL, 0x0000000000000080UL,
     ^~~~~~~~~~~~~~~~~~~~
   lib/tests/assoc_array_kunit.c:70:2: warning: conversion from 'long long unsigned int' to 'long unsigned int' changes value from '16045690984503098046' to '3405691582' [-Woverflow]
     0xdeadbeefcafebabeUL, 0x0000000000000090UL,
     ^~~~~~~~~~~~~~~~~~~~
   lib/tests/assoc_array_kunit.c:71:2: warning: conversion from 'long long unsigned int' to 'long unsigned int' changes value from '16045690984503098046' to '3405691582' [-Woverflow]
     0xdeadbeefcafebabeUL, 0x00000000000000a0UL,
     ^~~~~~~~~~~~~~~~~~~~
   lib/tests/assoc_array_kunit.c:72:2: warning: conversion from 'long long unsigned int' to 'long unsigned int' changes value from '16045690984503098046' to '3405691582' [-Woverflow]
     0xdeadbeefcafebabeUL, 0x00000000000000b0UL,
     ^~~~~~~~~~~~~~~~~~~~
   lib/tests/assoc_array_kunit.c:73:2: warning: conversion from 'long long unsigned int' to 'long unsigned int' changes value from '16045690984503098046' to '3405691582' [-Woverflow]
     0xdeadbeefcafebabeUL, 0x00000000000000c0UL,
     ^~~~~~~~~~~~~~~~~~~~
   lib/tests/assoc_array_kunit.c:74:2: warning: conversion from 'long long unsigned int' to 'long unsigned int' changes value from '16045690984503098046' to '3405691582' [-Woverflow]
     0xdeadbeefcafebabeUL, 0x00000000000000d0UL,
     ^~~~~~~~~~~~~~~~~~~~
   lib/tests/assoc_array_kunit.c:75:2: warning: conversion from 'long long unsigned int' to 'long unsigned int' changes value from '16045690984503098046' to '3405691582' [-Woverflow]
     0xdeadbeefcafebabeUL, 0x00000000000000e0UL,
     ^~~~~~~~~~~~~~~~~~~~
   lib/tests/assoc_array_kunit.c:76:2: warning: conversion from 'long long unsigned int' to 'long unsigned int' changes value from '16045690984503098046' to '3405691582' [-Woverflow]
     0xdeadbeefcafebabeUL, 0x00000000000000f0UL,
     ^~~~~~~~~~~~~~~~~~~~
   lib/tests/assoc_array_kunit.c:77:2: warning: conversion from 'long long unsigned int' to 'long unsigned int' changes value from '16045690984503098046' to '3405691582' [-Woverflow]
     0xdeadbeefcafebabeUL, 0x0000000000000100UL,
     ^~~~~~~~~~~~~~~~~~~~
   lib/tests/assoc_array_kunit.c:78:2: warning: conversion from 'long long unsigned int' to 'long unsigned int' changes value from '16045690984503098046' to '3405691582' [-Woverflow]
     0xdeadbeefcafebabeUL, 0x0000000000000110UL,
     ^~~~~~~~~~~~~~~~~~~~
   lib/tests/assoc_array_kunit.c:79:2: warning: conversion from 'long long unsigned int' to 'long unsigned int' changes value from '16045690984503098046' to '3405691582' [-Woverflow]
     0xdeadbeefcafebabeUL, 0x0000000000000001UL,
     ^~~~~~~~~~~~~~~~~~~~

vim +62 lib/tests/assoc_array_kunit.c

    19	
    20	/*
    21	 * As a quick remainder, these are the basic building blocks of an associative
    22	 * array:
    23	 *
    24	 * - struct assoc_array_node: a tree node representing a nibble of the search
    25	 *   key.
    26	 * - struct assoc_array_shortcut: a tree node representing a sequence of nibbles
    27	 *   shared by multiple search keys with no divergence among them.
    28	 *
    29	 * The keys in array will be created in order in tests, and is a constructed in
    30	 * a way that splits reach the level 8:
    31	 *
    32	 * - 0..16:  Share prefix 0x21 at levels 0 and 4.
    33	 * - 17:     Splits root shortcut at level 4.
    34	 * - 18..34: Share chunk 0.
    35	 * - 35:     Splits shortcut at chunk boundary.
    36	 * - 36..46: Share prefix 0xbeef at levels 0..12.
    37	 * - 47:     Splits shortcut at level 8.
    38	 * - 48..63: Distinct leaves at level 0.
    39	 *
    40	 * The numbers were picked partly based on trial and error, and partly trying to
    41	 * find smallest possible numbers reaching the level 8.
    42	 */
    43	static const unsigned long assoc_array_test_keys[ASSOC_ARRAY_TEST_NR_KEYS * 2] = {
    44		0x0000000000000121UL, 0x0000000000000000UL,
    45		0x0000000000000221UL, 0x0000000000000000UL,
    46		0x0000000000000321UL, 0x0000000000000000UL,
    47		0x0000000000000421UL, 0x0000000000000000UL,
    48		0x0000000000000521UL, 0x0000000000000000UL,
    49		0x0000000000000621UL, 0x0000000000000000UL,
    50		0x0000000000000721UL, 0x0000000000000000UL,
    51		0x0000000000000821UL, 0x0000000000000000UL,
    52		0x0000000000000921UL, 0x0000000000000000UL,
    53		0x0000000000000a21UL, 0x0000000000000000UL,
    54		0x0000000000000b21UL, 0x0000000000000000UL,
    55		0x0000000000000c21UL, 0x0000000000000000UL,
    56		0x0000000000000d21UL, 0x0000000000000000UL,
    57		0x0000000000000e21UL, 0x0000000000000000UL,
    58		0x0000000000000f21UL, 0x0000000000000000UL,
    59		0x0000000000001021UL, 0x0000000000000000UL,
    60		0x0000000000001121UL, 0x0000000000000000UL,
    61		0x0000000000000001UL, 0x0000000000000000UL,
  > 62		0xdeadbeefcafebabeUL, 0x0000000000000010UL,
    63		0xdeadbeefcafebabeUL, 0x0000000000000020UL,
    64		0xdeadbeefcafebabeUL, 0x0000000000000030UL,
    65		0xdeadbeefcafebabeUL, 0x0000000000000040UL,
    66		0xdeadbeefcafebabeUL, 0x0000000000000050UL,
    67		0xdeadbeefcafebabeUL, 0x0000000000000060UL,
    68		0xdeadbeefcafebabeUL, 0x0000000000000070UL,
    69		0xdeadbeefcafebabeUL, 0x0000000000000080UL,
    70		0xdeadbeefcafebabeUL, 0x0000000000000090UL,
    71		0xdeadbeefcafebabeUL, 0x00000000000000a0UL,
    72		0xdeadbeefcafebabeUL, 0x00000000000000b0UL,
    73		0xdeadbeefcafebabeUL, 0x00000000000000c0UL,
    74		0xdeadbeefcafebabeUL, 0x00000000000000d0UL,
    75		0xdeadbeefcafebabeUL, 0x00000000000000e0UL,
    76		0xdeadbeefcafebabeUL, 0x00000000000000f0UL,
    77		0xdeadbeefcafebabeUL, 0x0000000000000100UL,
    78		0xdeadbeefcafebabeUL, 0x0000000000000110UL,
    79		0xdeadbeefcafebabeUL, 0x0000000000000001UL,
    80		0x000000000001beefUL, 0x0000000000000000UL,
    81		0x000000000002beefUL, 0x0000000000000000UL,
    82		0x000000000003beefUL, 0x0000000000000000UL,
    83		0x000000000004beefUL, 0x0000000000000000UL,
    84		0x000000000005beefUL, 0x0000000000000000UL,
    85		0x000000000006beefUL, 0x0000000000000000UL,
    86		0x000000000007beefUL, 0x0000000000000000UL,
    87		0x000000000008beefUL, 0x0000000000000000UL,
    88		0x000000000009beefUL, 0x0000000000000000UL,
    89		0x00000000000abeefUL, 0x0000000000000000UL,
    90		0x00000000000bbeefUL, 0x0000000000000000UL,
    91		0x00000000000000efUL, 0x0000000000000000UL,
    92		0x0000000000001000UL, 0x0000000000000000UL,
    93		0x0000000000001001UL, 0x0000000000000000UL,
    94		0x0000000000001002UL, 0x0000000000000000UL,
    95		0x0000000000001003UL, 0x0000000000000000UL,
    96		0x0000000000001004UL, 0x0000000000000000UL,
    97		0x0000000000001005UL, 0x0000000000000000UL,
    98		0x0000000000001006UL, 0x0000000000000000UL,
    99		0x0000000000001007UL, 0x0000000000000000UL,

100 0x0000000000001008UL, 0x0000000000000000UL,
101 0x0000000000001009UL, 0x0000000000000000UL,
102 0x000000000000100aUL, 0x0000000000000000UL,
103 0x000000000000100bUL, 0x0000000000000000UL,
104 0x000000000000100cUL, 0x0000000000000000UL,
105 0x000000000000100dUL, 0x0000000000000000UL,
106 0x000000000000100eUL, 0x0000000000000000UL,
107 0x000000000000100fUL, 0x0000000000000000UL,
108 };
109

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

#7 lore raw
In reply to Jarkko Sakkinen
kernel test robot noticed the following build errors:

Hi Jarkko,

kernel test robot noticed the following build errors:

[auto build test ERROR on akpm-mm/mm-nonmm-unstable]
[also build test ERROR on linus/master v7.3-rc7]
[cannot apply to next-20261012]
[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/Jarkko-Sakkinen/lib-tests-kunit-for-associative-array/20261014-190138
base:   https://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm.git mm-nonmm-unstable
patch link:    https://lore.kernel.org/r/20261014160144.1835860-1-jarkko%40kernel.org
patch subject: [PATCH] lib/tests: kunit for associative array
config: i386-randconfig-1010-20261016 (https://download.01.org/0day-ci/archive/20261016/[email protected]/config)
compiler: clang version 22.1.8 (https://github.com/llvm/llvm-project ca7933e47d3a3451d81e72ac174dcb5aa28b59d1)
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20261016/[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: lib/tests/assoc_array_kunit.ko: symbol 'assoc_array_iterate' undefined!
>> ERROR: modpost: lib/tests/assoc_array_kunit.ko: symbol 'assoc_array_gc' undefined!
>> ERROR: modpost: lib/tests/assoc_array_kunit.ko: symbol 'assoc_array_insert' undefined!
>> ERROR: modpost: lib/tests/assoc_array_kunit.ko: symbol 'assoc_array_cancel_edit' undefined!
>> ERROR: modpost: lib/tests/assoc_array_kunit.ko: symbol 'assoc_array_delete' undefined!
>> ERROR: modpost: lib/tests/assoc_array_kunit.ko: symbol 'assoc_array_clear' undefined!
>> ERROR: modpost: lib/tests/assoc_array_kunit.ko: symbol 'assoc_array_apply_edit' undefined!
>> ERROR: modpost: lib/tests/assoc_array_kunit.ko: symbol 'assoc_array_destroy' undefined!
>> ERROR: modpost: lib/tests/assoc_array_kunit.ko: symbol 'assoc_array_find' undefined!

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

#8 lore raw
In reply to Jarkko Sakkinen
Quoted 56 lines · Jarkko Sakkinen

This is a kunit test for lib/assoc_array.c, which maintains a shadow model across assoc_array operations, and checks its integrity after every operation.

I wrote a draft version so that I could properly test 'assoc-array-fixes' tag at Linus' tree, and spent today rewriting a new more polished version with as good description as I could possibly could on how the seeded test keys were cherry-picked. Along the way I also tweaked the numbers to be a bit less messier set than in my original version.

The transcripts that follow were executed with this command-line:

    ./tools/testing/kunit/kunit.py run --raw_output assoc_array

With 'assoc-array-fixes' commits and its subsequent tag iterations all eight tests pass, and without them all of them fail.

---
 lib/Kconfig.debug             |  15 +
 lib/tests/Makefile            |   1 +
 lib/tests/assoc_array_kunit.c | 570 ++++++++++++++++++++++++++++++++++
 3 files changed, 586 insertions(+)
 create mode 100644 lib/tests/assoc_array_kunit.c
lib/Kconfig.debug +15 -0
index 6b24a2c89b84..3e8d3852f53c 100644
@@ -2857,6 +2857,21 @@ config HASHTABLE_KUNIT_TEST
 
 	  If unsure, say N.
 
+config ASSOC_ARRAY_KUNIT_TEST
+	tristate "KUnit test for assoc_array" if !KUNIT_ALL_TESTS
+	depends on KUNIT
+	default KUNIT_ALL_TESTS
+	select ASSOCIATIVE_ARRAY
+	help
+	  This builds the assoc_array KUnit test suite.
+	  It tests the basic functionality of the API defined in
+	  include/linux/assoc_array.h.
+
+	  For more information on KUnit and unit tests in general please refer
+	  to the KUnit documentation in Documentation/dev-tools/kunit/.
+
+	  If unsure, say N.
+
 config LINEAR_RANGES_TEST
 	tristate "KUnit test for linear_ranges"
 	depends on KUNIT
lib/tests/Makefile +0 -0
index 3cac3b63a752..107e16b4ebc1 100644

lib/tests/Makefile line 10

Quoted 7 lines
lib/tests/Makefile +1 -0
@@ -4,6 +4,7 @@
 
 # KUnit tests
 CFLAGS_bitfield_kunit.o := $(DISABLE_STRUCTLEAK_PLUGIN)
+obj-$(CONFIG_ASSOC_ARRAY_KUNIT_TEST) += assoc_array_kunit.o
 obj-$(CONFIG_BASE64_KUNIT) += base64_kunit.o
 obj-$(CONFIG_BITOPS_KUNIT) += bitops_kunit.o
 obj-$(CONFIG_BITFIELD_KUNIT) += bitfield_kunit.o

Why does this one end with _TEST and the others do not? I see LINEAR_RANGES_TEST in the context above, but it also lacks _KUINT. There is HASHTABLE_KUNIT_TEST nearby too, so perhaps consistency has just never been popular around these parts.

Thanks,

--Ben

author maintainer
#9 lore raw
Quoted 58 lines · Ben Boeckel
Quoted 57 lines · Jarkko Sakkinen

This is a kunit test for lib/assoc_array.c, which maintains a shadow model across assoc_array operations, and checks its integrity after every operation.

I wrote a draft version so that I could properly test 'assoc-array-fixes' tag at Linus' tree, and spent today rewriting a new more polished version with as good description as I could possibly could on how the seeded test keys were cherry-picked. Along the way I also tweaked the numbers to be a bit less messier set than in my original version.

The transcripts that follow were executed with this command-line:

    ./tools/testing/kunit/kunit.py run --raw_output assoc_array

With 'assoc-array-fixes' commits and its subsequent tag iterations all eight tests pass, and without them all of them fail.

---
 lib/Kconfig.debug             |  15 +
 lib/tests/Makefile            |   1 +
 lib/tests/assoc_array_kunit.c | 570 ++++++++++++++++++++++++++++++++++
 3 files changed, 586 insertions(+)
 create mode 100644 lib/tests/assoc_array_kunit.c
lib/Kconfig.debug +15 -0
index 6b24a2c89b84..3e8d3852f53c 100644
@@ -2857,6 +2857,21 @@ config HASHTABLE_KUNIT_TEST
 
 	  If unsure, say N.
 
+config ASSOC_ARRAY_KUNIT_TEST
+	tristate "KUnit test for assoc_array" if !KUNIT_ALL_TESTS
+	depends on KUNIT
+	default KUNIT_ALL_TESTS
+	select ASSOCIATIVE_ARRAY
+	help
+	  This builds the assoc_array KUnit test suite.
+	  It tests the basic functionality of the API defined in
+	  include/linux/assoc_array.h.
+
+	  For more information on KUnit and unit tests in general please refer
+	  to the KUnit documentation in Documentation/dev-tools/kunit/.
+
+	  If unsure, say N.
+
 config LINEAR_RANGES_TEST
 	tristate "KUnit test for linear_ranges"
 	depends on KUNIT
lib/tests/Makefile +0 -0
index 3cac3b63a752..107e16b4ebc1 100644
@@ -4,6 +4,7 @@
 
Quoted 11 lines

lib/tests/Makefile line 10

Quoted 6 lines
lib/tests/Makefile +1 -0
 # KUnit tests
 CFLAGS_bitfield_kunit.o := $(DISABLE_STRUCTLEAK_PLUGIN)
+obj-$(CONFIG_ASSOC_ARRAY_KUNIT_TEST) += assoc_array_kunit.o
 obj-$(CONFIG_BASE64_KUNIT) += base64_kunit.o
 obj-$(CONFIG_BITOPS_KUNIT) += bitops_kunit.o
 obj-$(CONFIG_BITFIELD_KUNIT) += bitfield_kunit.o

Why does this one end with _TEST and the others do not? I see LINEAR_RANGES_TEST in the context above, but it also lacks _KUINT. There is HASHTABLE_KUNIT_TEST nearby too, so perhaps consistency has just never been popular around these parts.

A blind spot. I started with that name.

This is phasing down as an RF patch set with rhashtable migration is already out.

Quoted 4 lines

Thanks,

--Ben

Regardless, appreciate your feedback, thanks!

Br, Jarkko