lib/hashtable_test.c: add test for the hashtable structure
Subsystems (2)
PATCH v2 1/1 lib/hashtable_test.c: add test for the hashtable structure
Add a KUnit test for the kernel hashtable implementation in include/linux/hashtable.h.
Note that this version does not yet test each of the rcu alternative versions of functions.
---
Changes since v1:
- Change Kconfig.debug message to be more succinct.
- Directly increment current element's visited field rather than looking up corresponding element.
- Use KUNIT_EXPECT_… statements to check keys are within range rather than using if statements.
- Change hash_for_each_possible test to check buckets using a hash_for_each method instead of calculating the bucket number using hash_min.
Note: The check patch script is outputting open brace errors on lines 158, 192, 247 of lib/hashtable_test.c. However, I think these errors are a mistake as the format of the braces on those lines seems consistent with the Linux Kernel style guide.
lib/Kconfig.debug | 13 ++ lib/Makefile | 1 + lib/hashtable_test.c | 326 +++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 340 insertions(+) create mode 100644 lib/hashtable_test.c
lib/Kconfig.debug +13 -0
@@ -2496,6 +2496,19 @@ config LIST_KUNIT_TEST If unsure, say N. +config HASHTABLE_KUNIT_TEST + tristate "KUnit Test for Kernel Hashtable structures" if !KUNIT_ALL_TESTS + depends on KUNIT + default KUNIT_ALL_TESTS + help + This builds the hashtable KUnit test suite. + It tests the basic functionality of the API defined in + include/linux/hashtable.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/Makefile +1 -0
@@ -369,6 +369,7 @@ obj-$(CONFIG_PLDMFW) += pldmfw/ CFLAGS_bitfield_kunit.o := $(DISABLE_STRUCTLEAK_PLUGIN) obj-$(CONFIG_BITFIELD_KUNIT) += bitfield_kunit.o obj-$(CONFIG_LIST_KUNIT_TEST) += list-test.o +obj-$(CONFIG_HASHTABLE_KUNIT_TEST) += hashtable_test.o obj-$(CONFIG_LINEAR_RANGES_TEST) += test_linear_ranges.o obj-$(CONFIG_BITS_TEST) += test_bits.o obj-$(CONFIG_CMDLINE_KUNIT_TEST) += cmdline_kunit.o
lib/hashtable_test.c new file +326 -0
326 lines not on this page · raw message
base-commit: 88603b6dc419445847923fcb7fe5080067a30f98
Signature · 1 line
2.39.0.314.g84b9a713c41-goog
Quoted 9 lines · Rae Moar
Add a KUnit test for the kernel hashtable implementation in
include/linux/hashtable.h.Note that this version does not yet test each of the rcu alternative versions of functions.
Signed-off-by Rae Moar <[email protected]>---
This looks good, and TBH, I could accept it as-is. There are a few very minor stylistic nitpicks below, but there are a couple of bigger issues, too:
- DEFINE_HASHTABLE() should initialise the hashtable itself, so you shouldn't need to also call hash_init().
- It'd be nice if we had some hashtables of different sizes. At the moment, they're all 3-bit (8 entries). Let's mix it up a little bit.
With those two changes (and optionally, any of the stylistic ones below), this is:
Cheers,
-- David
Quoted 11 lines
Changes since v1:
- ChangeKconfig.debugmessage to be more succinct.
- Directly increment current element's visited field rather than looking up corresponding element.
- Use KUNIT_EXPECT_… statements to check keys are within range rather than using if statements.
- Changehash_for_each_possibletest to check buckets using ahash_for_eachmethod instead of calculating the bucket number usinghash_min.
Quoted 5 lines
Note: The check patch script is outputting open brace errors on lines 158, 192, 247 of
lib/hashtable_test.c. However, I think these errors are a mistake as the format of the braces on those lines seems consistent with the Linux Kernel style guide.
This is a known issue with checkpatch and function names with "for_each" in them. It was discussed here, and we ultimately decided just to ignore the warnings:
https://lore.kernel.org/all/CABVgOSmCHbGjZBjeWSbPEZbJw22SaBQnoO77xxNzN_ugAwzNiQ@mail.gmail.com/
Quoted 61 lines
lib/Kconfig.debug | 13 ++ lib/Makefile | 1 + lib/hashtable_test.c | 326 +++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 340 insertions(+) create mode 100644 lib/hashtable_test.clib/Kconfig.debug +13
-0@@ -2496,6 +2496,19 @@ config LIST_KUNIT_TEST If unsure, say N. +config HASHTABLE_KUNIT_TEST + tristate "KUnit Test for Kernel Hashtable structures" if !KUNIT_ALL_TESTS + depends on KUNIT + default KUNIT_ALL_TESTS + help + This builds the hashtable KUnit test suite. + It tests the basic functionality of the API defined in + include/linux/hashtable.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 KUNITlib/Makefile +1
-0@@ -369,6 +369,7 @@ obj-$(CONFIG_PLDMFW) += pldmfw/ CFLAGS_bitfield_kunit.o := $(DISABLE_STRUCTLEAK_PLUGIN) obj-$(CONFIG_BITFIELD_KUNIT) += bitfield_kunit.o obj-$(CONFIG_LIST_KUNIT_TEST) += list-test.o +obj-$(CONFIG_HASHTABLE_KUNIT_TEST) += hashtable_test.o obj-$(CONFIG_LINEAR_RANGES_TEST) += test_linear_ranges.o obj-$(CONFIG_BITS_TEST) += test_bits.o obj-$(CONFIG_CMDLINE_KUNIT_TEST) += cmdline_kunit.olib/hashtable_test.c new file +13
-0@@ -0,0 +1,326 @@ +// SPDX-License-Identifier: GPL-2.0 +/* +* KUnit test for the Kernel Hashtable structures. +* +* Copyright (C) 2022, Google LLC. +* Author: Rae Moar <[email protected]> +*/ +#include <kunit/test.h> + +#include <linux/hashtable.h> + +struct hashtable_test_entry { +int key;
lib/hashtable_test.c line 23
Quoted 10 lines
lib/hashtable_test.c new file +10
-0+int data; +struct hlist_node node; +int visited; +}; + +static void hashtable_test_hash_init (struct kunit *test) +{ +/* Test the different ways of initialising a hashtable. */ +DEFINE_HASHTABLE (hash1,3 ); +DECLARE_HASHTABLE (hash2,3 );
As I understand it, DEFINE_HASHTABLE shouldn't need a hash_init(), but DECLARE_HASHTABLE() does?
Could we make that clearer (and in so doing, get rid of the hash_init for all hashtables which were DEFINE_HASHTABLE()ed?
Quoted 8 lines
lib/hashtable_test.c new file +8
-0+ +hash_init (hash1); +hash_init (hash2); + +KUNIT_EXPECT_TRUE (test,hash_empty (hash1)); +KUNIT_EXPECT_TRUE (test,hash_empty (hash2)); +} +
lib/hashtable_test.c line 41
Quoted 10 lines
lib/hashtable_test.c new file +10
-0+static void hashtable_test_hash_empty (struct kunit *test) +{ +struct hashtable_test_entry a; +DEFINE_HASHTABLE (hash,3 ); + +hash_init (hash); +KUNIT_EXPECT_TRUE (test,hash_empty (hash)); + + a.key =1 ; + a.data =13 ;
I guess it doesn't matter what (if any) data is in 'a', so this isn't strictly necessary. I don't mind having it though, as it's nice to have some actual data to add.
If you really wanted, you could just add a struct hlist_node directly, rather than struct hashtable_test_entry, though again, this is a more realistic-looking test as-is, so I'm okay with keeping it.
Quoted 7 lines
lib/hashtable_test.c new file +7
-0+hash_add (hash, &a.node, a.key); + +/* Hashtable should no longer be empty. */ +KUNIT_EXPECT_FALSE (test,hash_empty (hash)); +} + +static void hashtable_test_hash_hashed (struct kunit *test)
lib/hashtable_test.c line 58
Quoted 10 lines
lib/hashtable_test.c new file +10
-0+{ +struct hashtable_test_entry a, b; +DEFINE_HASHTABLE (hash,3 ); + +hash_init (hash); + a.key =1 ; + a.data =13 ; + b.key =1 ; + b.data =2 ; +
Nit: I might put the initialisation of the data in the same block as adding them. Or possibly do something like:
a.key = 1;
a.data = …;hash_add(…);
b.key = 1;
b.data = …;hash_add(…);
Not something I actually care too much about, though: this is readable enough as-is.
Quoted 13 lines
lib/hashtable_test.c new file +13
-0+hash_add (hash, &a.node, a.key); +hash_add (hash, &b.node, b.key); + +KUNIT_EXPECT_TRUE (test,hash_hashed (&a.node)); +KUNIT_EXPECT_TRUE (test,hash_hashed (&b.node)); +} + +static void hashtable_test_hash_add (struct kunit *test) +{ +struct hashtable_test_entry a, b, *x; +int bkt; +DEFINE_HASHTABLE (hash,3 ); +
lib/hashtable_test.c line 81
Quoted 10 lines
lib/hashtable_test.c new file +10
-0+hash_init (hash); + a.key =1 ; + a.data =13 ; + a.visited =0 ; + b.key =2 ; + b.data =10 ; + b.visited =0 ; + +hash_add (hash, &a.node, a.key); +hash_add (hash, &b.node, b.key);
As above, can we reorder these to do everything with a, then everything with b (and remove the hash_init)?
Quoted 20 lines
lib/hashtable_test.c new file +20
-0+ +hash_for_each (hash, bkt, x, node) { + x->visited++; +if (x->key == a.key) +KUNIT_EXPECT_EQ (test, x->data,13 ); +else if (x->key == b.key) +KUNIT_EXPECT_EQ (test, x->data,10 ); +else +KUNIT_FAIL (test,"Unexpected key in hashtable." ); + } + +/* Both entries should have been visited exactly once. */ +KUNIT_EXPECT_EQ (test, a.visited,1 ); +KUNIT_EXPECT_EQ (test, b.visited,1 ); +} + +static void hashtable_test_hash_del (struct kunit *test) +{ +struct hashtable_test_entry a, b, *x; +DEFINE_HASHTABLE (hash,3 );
lib/hashtable_test.c line 111
Quoted 10 lines
lib/hashtable_test.c new file +10
-0+ +hash_init (hash); + a.key =1 ; + a.data =13 ; + b.key =2 ; + b.data =10 ; + b.visited =0 ; + +hash_add (hash, &a.node, a.key); +hash_add (hash, &b.node, b.key);
As above, maybe adjust the spacing here. Though, to be honest, I don't think it matters _quite_ as much once you get rid of hash_init(). Still probably better to do [init a][add a][init b][add b], IMO, though.
Quoted 109 lines
lib/hashtable_test.c new file +109
-0+ +hash_del (&b.node); +hash_for_each_possible (hash, x, node, b.key) { + x->visited++; +KUNIT_EXPECT_NE (test, x->key, b.key); + } + +/* The deleted entry should not have been visited. */ +KUNIT_EXPECT_EQ (test, b.visited,0 ); + +hash_del (&a.node); + +/* The hashtable should be empty. */ +KUNIT_EXPECT_TRUE (test,hash_empty (hash)); +} + +static void hashtable_test_hash_for_each (struct kunit *test) +{ +struct hashtable_test_entry entries[3 ]; +struct hashtable_test_entry *x; +int bkt, i, j, count; +DEFINE_HASHTABLE (hash,3 ); + +/* Initialize a hashtable with three entries. */ +hash_init (hash); +for (i =0 ; i <3 ; i++) { + entries[i].key = i; + entries[i].data = i +10 ; + entries[i].visited =0 ; +hash_add (hash, &entries[i].node, entries[i].key); + } + + count =0 ; +hash_for_each (hash, bkt, x, node) { + x->visited +=1 ; +KUNIT_ASSERT_GE (test, x->key,0 ); +KUNIT_ASSERT_LT (test, x->key,3 ); + count++; + } + +/* Should have visited each entry exactly once. */ +KUNIT_EXPECT_EQ (test, count,3 ); +for (j =0 ; j <3 ; j++) +KUNIT_EXPECT_EQ (test, entries[j].visited,1 ); +} + +static void hashtable_test_hash_for_each_safe (struct kunit *test) +{ +struct hashtable_test_entry entries[3 ]; +struct hashtable_test_entry *x; +struct hlist_node *tmp; +int bkt, i, j, count; +DEFINE_HASHTABLE (hash,3 ); + +/* Initialize a hashtable with three entries. */ +hash_init (hash); +for (i =0 ; i <3 ; i++) { + entries[i].key = i; + entries[i].data = i +10 ; + entries[i].visited =0 ; +hash_add (hash, &entries[i].node, entries[i].key); + } + + count =0 ; +hash_for_each_safe (hash, bkt, tmp, x, node) { + x->visited +=1 ; +KUNIT_ASSERT_GE (test, x->key,0 ); +KUNIT_ASSERT_LT (test, x->key,3 ); + count++; + +/* Delete entry during loop. */ +hash_del (&x->node); + } + +/* Should have visited each entry exactly once. */ +KUNIT_EXPECT_EQ (test, count,3 ); +for (j =0 ; j <3 ; j++) +KUNIT_EXPECT_EQ (test, entries[j].visited,1 ); +} + +static void hashtable_test_hash_for_each_possible (struct kunit *test) +{ +struct hashtable_test_entry entries[4 ]; +struct hashtable_test_entry *x, *y; +int buckets[2 ]; +int bkt, i, j, count; +DEFINE_HASHTABLE (hash,3 ); + +/* Initialize a hashtable with three entries with key = 0. */ +hash_init (hash); +for (i =0 ; i <3 ; i++) { + entries[i].key =0 ; + entries[i].data = i; + entries[i].visited =0 ; +hash_add (hash, &entries[i].node, entries[i].key); + } + +/* Add an entry with key = 1. */ + entries[3 ].key =1 ; + entries[3 ].data =3 ; + entries[3 ].visited =0 ; +hash_add (hash, &entries[3 ].node, entries[3 ].key); + + count =0 ; +hash_for_each_possible (hash, x, node,0 ) { + x->visited +=1 ; +KUNIT_ASSERT_GE (test, x->data,0 ); +KUNIT_ASSERT_LT (test, x->data,4 ); + count++;
lib/hashtable_test.c line 230
Quoted 10 lines
lib/hashtable_test.c new file +10
-0+ } + +/* Should have visited each entry with key = 0 exactly once. */ +for (j =0 ; j <3 ; j++) +KUNIT_EXPECT_EQ (test, entries[j].visited,1 ); + +/* Save the buckets for the different keys. */ +hash_for_each (hash, bkt, y, node) { +if (y->key <0 || y->key >1 ) +KUNIT_ASSERT_FAILURE (test,"Unexpected key in hashtable." );
Nit: could we just use KUNIT_ASSERT_LEQ() and KUNIT_ASSERT_GEQ() here? (Or better still, their _MSG variants)?
Quoted 49 lines
lib/hashtable_test.c new file +49
-0+ buckets[y->key] = bkt; + } + +/* If entry with key = 1 is in the same bucket as the entries with +* key = 0, check it was visited. Otherwise ensure that only three +* entries were visited. +*/ +if (buckets[0 ] == buckets[1 ]) { +KUNIT_EXPECT_EQ (test, count,4 ); +KUNIT_EXPECT_EQ (test, entries[3 ].visited,1 ); + }else { +KUNIT_EXPECT_EQ (test, count,3 ); +KUNIT_EXPECT_EQ (test, entries[3 ].visited,0 ); + } +} + +static void hashtable_test_hash_for_each_possible_safe (struct kunit *test) +{ +struct hashtable_test_entry entries[4 ]; +struct hashtable_test_entry *x, *y; +struct hlist_node *tmp; +int buckets[2 ]; +int bkt, i, j, count; +DEFINE_HASHTABLE (hash,3 ); + +/* Initialize a hashtable with three entries with key = 0. */ +hash_init (hash); +for (i =0 ; i <3 ; i++) { + entries[i].key =0 ; + entries[i].data = i; + entries[i].visited =0 ; +hash_add (hash, &entries[i].node, entries[i].key); + } + +/* Add an entry with key = 1. */ + entries[3 ].key =1 ; + entries[3 ].data =3 ; + entries[3 ].visited =0 ; +hash_add (hash, &entries[3 ].node, entries[3 ].key); + + count =0 ; +hash_for_each_possible_safe (hash, x, tmp, node,0 ) { + x->visited +=1 ; +KUNIT_ASSERT_GE (test, x->data,0 ); +KUNIT_ASSERT_LT (test, x->data,4 ); + count++; + +/* Delete entry during loop. */ +hash_del (&x->node);
lib/hashtable_test.c line 289
Quoted 10 lines
lib/hashtable_test.c new file +10
-0+ } + +/* Should have visited each entry with key = 0 exactly once. */ +for (j =0 ; j <3 ; j++) +KUNIT_EXPECT_EQ (test, entries[j].visited,1 ); + +/* Save the buckets for the different keys. */ +hash_for_each (hash, bkt, y, node) { +if (y->key <0 || y->key >1 ) +KUNIT_ASSERT_FAILURE (test,"Unexpected key in hashtable." );
Nit: could we just use KUNIT_ASSERT_LEQ() and KUNIT_ASSERT_GEQ() here? (Or better still, their _MSG variants)?
Quoted 42 lines
lib/hashtable_test.c new file +37
-0+ buckets[y->key] = bkt; + } + +/* If entry with key = 1 is in the same bucket as the entries with +* key = 0, check it was visited. Otherwise ensure that only three +* entries were visited. +*/ +if (buckets[0 ] == buckets[1 ]) { +KUNIT_EXPECT_EQ (test, count,4 ); +KUNIT_EXPECT_EQ (test, entries[3 ].visited,1 ); + }else { +KUNIT_EXPECT_EQ (test, count,3 ); +KUNIT_EXPECT_EQ (test, entries[3 ].visited,0 ); + } +} + +static struct kunit_case hashtable_test_cases[] = { +KUNIT_CASE (hashtable_test_hash_init), +KUNIT_CASE (hashtable_test_hash_empty), +KUNIT_CASE (hashtable_test_hash_hashed), +KUNIT_CASE (hashtable_test_hash_add), +KUNIT_CASE (hashtable_test_hash_del), +KUNIT_CASE (hashtable_test_hash_for_each), +KUNIT_CASE (hashtable_test_hash_for_each_safe), +KUNIT_CASE (hashtable_test_hash_for_each_possible), +KUNIT_CASE (hashtable_test_hash_for_each_possible_safe), + {}, +}; + +static struct kunit_suite hashtable_test_module = { + .name ="hashtable" , + .test_cases = hashtable_test_cases, +}; + +kunit_test_suites (&hashtable_test_module); + +MODULE_LICENSE ("GPL" );base-commit:
88603b6dc419445847923fcb7fe5080067a30f98--
2.39.0.314.g84b9a713c41-goog