lib/hashtable_test.c: add test for the hashtable structure
Subsystems (2)
PATCH 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.
---
Note: The check patch script is outputting open brace errors on lines 154, 186, 231 of lib/hashtable_test.c but I believe the format of the braces on those lines is consistent with the Linux Kernel style guide. Will continue to look at these errors.
lib/Kconfig.debug | 13 ++ lib/Makefile | 1 + lib/hashtable_test.c | 299 +++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 313 insertions(+) create mode 100644 lib/hashtable_test.c
lib/Kconfig.debug +13 -0
@@ -2458,6 +2458,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 API and basic functionality of the functions + and associated macros 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
@@ -370,6 +370,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 +299 -0
299 lines not on this page · raw message
base-commit: 054be257f28ca8eeb8e3620766501b81ceb4b293
Signature · 1 line
2.39.0.314.g84b9a713c41-goog
Quoted 8 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]>
Looks pretty good from a cursory glance.
Had some mostly stylistic nits/suggestions below.
Quoted 19 lines
---
Note: The check patch script is outputting open brace errors on lines 154, 186, 231 of
lib/hashtable_test.cbut I believe the format of the braces on those lines is consistent with the Linux Kernel style guide. Will continue to look at these errors.lib/Kconfig.debug | 13 ++ lib/Makefile | 1 + lib/hashtable_test.c | 299 +++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 313 insertions(+) create mode 100644 lib/hashtable_test.clib/Kconfig.debug +0
-0@@ -2458,6 +2458,19 @@ config LIST_KUNIT_TEST
lib/Kconfig.debug config LIST_KUNIT_TEST · line 2468
Quoted 10 lines
lib/Kconfig.debug +8
-0If 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 API and basic functionality of the functions + and associated macros defined in include/linux/hashtable.h.
nit: the "functions and associated macros" == "the API", so perhaps we can shorten this a bit.
Quoted 104 lines
lib/Kconfig.debug +5
-0+ 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@@ -370,6 +370,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 +78
-0@@ -0,0 +1,299 @@ +// 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; +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 ); + +hash_init (hash1); +hash_init (hash2); + +KUNIT_EXPECT_TRUE (test,hash_empty (hash1)); +KUNIT_EXPECT_TRUE (test,hash_empty (hash2)); +} + +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 ; +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) +{ +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 ; + +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 ); + +hash_init (hash); + a.key =1 ; + a.data =13 ; + a.visited =0 ; + b.key =2 ; + b.data =10 ; + b.visited =0 ;
lib/hashtable_test.c line 88
Quoted 10 lines
lib/hashtable_test.c new file +10
-0+ +hash_add (hash, &a.node, a.key); +hash_add (hash, &b.node, b.key); + +hash_for_each (hash, bkt, x, node) { +if (x->key == a.key && x->data == a.data) + a.visited +=1 ; +if (x->key == b.key && x->data == b.data) + b.visited +=1 ; + }
x->visited += 1;
or
x->visited++;
also do the same thing.
Note: given x is supposed to point to a or b, I don't know if checking against a.data does us much good.
If we're trying to check that hash_add() doesn't mutate the keys and data, this code won't catch it.
We'd have to instead do something like
if(x->key != 1 && x->key != 2) KUNIT_FAIL(test, ...);
Quoted 15 lines
lib/hashtable_test.c new file +15
-0+ +/* 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 ); + +hash_init (hash); + a.key =1 ; + a.data =13 ; + b.key =2 ;
lib/hashtable_test.c line 113
Quoted 10 lines
lib/hashtable_test.c new file +10
-0+ b.data =10 ; + b.visited =0 ; + +hash_add (hash, &a.node, a.key); +hash_add (hash, &b.node, b.key); + +hash_del (&b.node); +hash_for_each_possible (hash, x, node, b.key) { +if (x->key == b.key && x->data == b.data) + b.visited +=1 ;
Similarly to above, x->visited += 1 (or ++) is probably better.
Quoted 21 lines
lib/hashtable_test.c new file +21
-0+ } + +/* 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++) {
lib/hashtable_test.c line 144
Quoted 10 lines
lib/hashtable_test.c new file +10
-0+ 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) { +if (x->key >=0 && x->key <3 ) + entries[x->key].visited +=1 ;
Would this be better using an assert to fail the test if we see unexpected keys? E.g. like
if (x->key < 0 || x->key > 3) KUNIT_ASSERT_FAILURE(test, ...); x->visited++;
count++;
or
KUNIT_ASSERT_GE(test, x->key, 0);
KUNIT_ASSERT_LT(test, x->key, 3);
Quoted 69 lines
lib/hashtable_test.c new file +69
-0+ 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) { +if (x->key >=0 && x->key <3 ) { + entries[x->key].visited +=1 ; +hash_del (&entries[x->key].node); + } + 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_possible (struct kunit *test) +{ +struct hashtable_test_entry entries[4 ]; +struct hashtable_test_entry *x; +int i, j, count; +DEFINE_HASHTABLE (hash,3 ); + +/* Initialize a hashtable with three entries with key = 1. */ +hash_init (hash); +for (i =0 ; i <3 ; i++) { + entries[i].key =1 ; + entries[i].data = i; + entries[i].visited =0 ; +hash_add (hash, &entries[i].node, entries[i].key); + } + +/* Add an entry with key = 2. */ + entries[3 ].key =2 ; + 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,1 ) { +if (x->data >=0 && x->data <4 ) + entries[x->data].visited +=1 ; + count++; + }
lib/hashtable_test.c line 223
Quoted 10 lines
lib/hashtable_test.c new file +10
-0+ +/* Should have visited each entry with key = 1 exactly once. */ +for (j =0 ; j <3 ; j++) +KUNIT_EXPECT_EQ (test, entries[j].visited,1 ); + +/* If entry with key = 2 is in the same bucket as the entries with +* key = 1, check it was visited. Otherwise ensure that only three +* entries were visited. +*/ +if (hash_min (1 ,HASH_BITS (hash)) ==hash_min (2 ,HASH_BITS (hash))) {
nit: this feels like we might be a bit too tied to the impl (not sure if it'll change anytime soon, but still).
Could we check the bucket using hash_for_each?
E.g.
// assume we change the keys from {1,2} to {0,1}
int buckets[2];hash_for_each(hash, bkt, x, node) {
buckets[x->key] = bkt;
}
if (buckets[0] == buckets[1]) { // all in the same bucket
...
} else { ... }
lib/hashtable_test.c line 227
Quoted 4 lines
lib/hashtable_test.c new file +4
-0+KUNIT_EXPECT_EQ (test, count,4 ); +KUNIT_EXPECT_EQ (test, entries[3 ].visited,1 ); + }else { +KUNIT_EXPECT_EQ (test, count,3 );
should we also check that entries[3].visited == 0?
Daniel
Quoted 35 lines · Daniel Latypov
Quoted 8 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]>Looks pretty good from a cursory glance.
Had some mostly stylistic nits/suggestions below.Quoted 21 lines
---
Note: The check patch script is outputting open brace errors on lines 154, 186, 231 of
lib/hashtable_test.cbut I believe the format of the braces on those lines is consistent with the Linux Kernel style guide. Will continue to look at these errors.lib/Kconfig.debug | 13 ++ lib/Makefile | 1 + lib/hashtable_test.c | 299 +++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 313 insertions(+) create mode 100644 lib/hashtable_test.clib/Kconfig.debug +0
-0@@ -2458,6 +2458,19 @@ config LIST_KUNIT_TEST If unsure, say N.
Quoted 11 lines
lib/Kconfig.debug config LIST_KUNIT_TEST · line 2468
Quoted 8 lines
lib/Kconfig.debug +8
-0+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 API and basic functionality of the functions + and associated macros defined in include/linux/hashtable.h.nit: the "functions and associated macros" == "the API", so perhaps we can shorten this a bit.
This seems better to me. Thanks!
Quoted 112 lines
Quoted 112 lines
lib/Kconfig.debug +5
-0+ 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@@ -370,6 +370,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 +85
-0@@ -0,0 +1,299 @@ +// 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; +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 ); + +hash_init (hash1); +hash_init (hash2); + +KUNIT_EXPECT_TRUE (test,hash_empty (hash1)); +KUNIT_EXPECT_TRUE (test,hash_empty (hash2)); +} + +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 ; +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) +{ +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 ; + +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 ); + +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); + +hash_for_each (hash, bkt, x, node) { +if (x->key == a.key && x->data == a.data) + a.visited +=1 ;
Quoted 8 lines
lib/hashtable_test.c line 88
Quoted 3 lines
lib/hashtable_test.c new file +3
-0+if (x->key == b.key && x->data == b.data) + b.visited +=1 ; + }
x->visited+= 1;
or
x->visited++;
also do the same thing.
Oh right. That makes a lot of sense.
Quoted 8 lines
Note: given x is supposed to point to a or b, I don't know if checking against a.data does us much good.
If we're trying to check thathash_add()doesn't mutate the keys and data, this code won't catch it.
We'd have to instead do something like
if(x->key != 1 && x->key != 2)KUNIT_FAIL(test, ...);
This seems like a good change to me in combination with changing it to x->visited++;.
Although David's suggestion might be slightly more exhaustive. Why wouldn't it be important to check that the key matches the data?
Quoted 19 lines
Quoted 19 lines
lib/hashtable_test.c new file +19
-0+ +/* 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 ); + +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);
Quoted 8 lines
lib/hashtable_test.c line 113
Quoted 6 lines
lib/hashtable_test.c new file +6
-0+hash_add (hash, &b.node, b.key); + +hash_del (&b.node); +hash_for_each_possible (hash, x, node, b.key) { +if (x->key == b.key && x->data == b.data) + b.visited +=1 ;Similarly to above,
x->visited+= 1 (or ++) is probably better.
Right. Will switch this out here.
Quoted 33 lines
Quoted 22 lines
lib/hashtable_test.c new file +21
-0+ } + +/* 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++) {lib/hashtable_test.c line 144
Quoted 10 lines
lib/hashtable_test.c new file +10
-0+ 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) { +if (x->key >=0 && x->key <3 ) + entries[x->key].visited +=1 ;
Quoted 8 lines
Would this be better using an assert to fail the test if we see unexpected keys? E.g. like
if (x->key< 0 ||x->key> 3)KUNIT_ASSERT_FAILURE(test, ...); x->visited++;
count++;
or
KUNIT_ASSERT_GE(test, x->key, 0);
KUNIT_ASSERT_LT(test, x->key, 3);
Yes, this makes a lot of sense. I will switch out just the if statements for using assert statements.
Quoted 93 lines
Quoted 70 lines
lib/hashtable_test.c new file +69
-0+ 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) { +if (x->key >=0 && x->key <3 ) { + entries[x->key].visited +=1 ; +hash_del (&entries[x->key].node); + } + 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_possible (struct kunit *test) +{ +struct hashtable_test_entry entries[4 ]; +struct hashtable_test_entry *x; +int i, j, count; +DEFINE_HASHTABLE (hash,3 ); + +/* Initialize a hashtable with three entries with key = 1. */ +hash_init (hash); +for (i =0 ; i <3 ; i++) { + entries[i].key =1 ; + entries[i].data = i; + entries[i].visited =0 ; +hash_add (hash, &entries[i].node, entries[i].key); + } + +/* Add an entry with key = 2. */ + entries[3 ].key =2 ; + 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,1 ) { +if (x->data >=0 && x->data <4 ) + entries[x->data].visited +=1 ; + count++; + }lib/hashtable_test.c line 223
Quoted 10 lines
lib/hashtable_test.c new file +10
-0+ +/* Should have visited each entry with key = 1 exactly once. */ +for (j =0 ; j <3 ; j++) +KUNIT_EXPECT_EQ (test, entries[j].visited,1 ); + +/* If entry with key = 2 is in the same bucket as the entries with +* key = 1, check it was visited. Otherwise ensure that only three +* entries were visited. +*/ +if (hash_min (1 ,HASH_BITS (hash)) ==hash_min (2 ,HASH_BITS (hash))) {nit: this feels like we might be a bit too tied to the impl (not sure if it'll change anytime soon, but still).
Could we check the bucket using
hash_for_each?
E.g.// assume we change the keys from {1,2} to {0,1}
int buckets[2];hash_for_each(hash, bkt, x, node){
buckets[x->key] = bkt;
}
Quoted 3 lines
if (buckets[0] == buckets[1]) { // all in the same bucket
...
} else { ... }
I really like the idea of using hash_for_each to determine the bucket. I will add this to the test.
Quoted 7 lines
lib/hashtable_test.c line 227
Quoted 5 lines
lib/hashtable_test.c new file +4
-0+KUNIT_EXPECT_EQ (test, count,4 ); +KUNIT_EXPECT_EQ (test, entries[3 ].visited,1 ); + }else { +KUNIT_EXPECT_EQ (test, count,3 );should we also check that entries[3].visited == 0?
Right. Must have been a mistake on my end. Oops.
Quoted 2 lines
Daniel
Thanks Daniel!
-Rae
On Fri, Jan 13, 2023 at 2:23 PM Rae Moar <[email protected]> wrote:
<snip>
Quoted 8 lines
Quoted 7 lines
Note: given x is supposed to point to a or b, I don't know if checking against a.data does us much good.
If we're trying to check thathash_add()doesn't mutate the keys and data, this code won't catch it.
We'd have to instead do something like
if(x->key != 1 && x->key != 2)KUNIT_FAIL(test, ...);
Quoted 4 lines
This seems like a good change to me in combination with changing it to x->visited++;.
Although David's suggestion might be slightly more exhaustive. Why wouldn't it be important to check that the key matches the data?
Checks like
KUNIT_EXPECT_EQ(test, x->data, a.data);
won't do anything, given that x == &a.
We're just comparing x->data to itself.
So we would have to write something instead like
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 { /* some call to KUNIT_FAIL about a bad key */ }}
Maybe that's worth it in one of the test cases, but I don't know if it's necessary to replicate this in the other places where we're incrementing visited by checking keys.
Daniel
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]>---
Thanks for completing the triangle (hash, list, hashtable) of hashtable-related tests!
This looks good to me, save for some nitpicks below. They're mostly pretty similar to Daniel's comments, so should be pretty straightforward.
Cheers,
-- David
Quoted 5 lines
Note: The check patch script is outputting open brace errors on lines 154, 186, 231 of
lib/hashtable_test.cbut I believe the format of the braces on those lines is consistent with the Linux Kernel style guide. Will continue to look at these errors.
This is a problem we hit with the list test as well: because these functions have for_each in their name, checkpatch.pl assumes they're loops (using the macro), not functions.
As with the list test, we _could_ try to fix this in checkpatch, or rename the tests, but I suspect it's a special enough case (naming a function after a macro), that it's best to ignore the warnings, keeping a note like this in the patch email.
Maybe one day, checkpatch.pl will be able to tell that this is a function...
Quoted 126 lines
lib/Kconfig.debug | 13 ++ lib/Makefile | 1 + lib/hashtable_test.c | 299 +++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 313 insertions(+) create mode 100644 lib/hashtable_test.clib/Kconfig.debug +13
-0@@ -2458,6 +2458,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 API and basic functionality of the functions + and associated macros 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@@ -370,6 +370,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 +77
-0@@ -0,0 +1,299 @@ +// 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; +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 ); + +hash_init (hash1); +hash_init (hash2); + +KUNIT_EXPECT_TRUE (test,hash_empty (hash1)); +KUNIT_EXPECT_TRUE (test,hash_empty (hash2)); +} + +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 ; +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) +{ +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 ; + +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 ); + +hash_init (hash); + a.key =1 ; + a.data =13 ; + a.visited =0 ; + b.key =2 ; + b.data =10 ;
lib/hashtable_test.c line 87
Quoted 10 lines
lib/hashtable_test.c new file +10
-0+ b.visited =0 ; + +hash_add (hash, &a.node, a.key); +hash_add (hash, &b.node, b.key); + +hash_for_each (hash, bkt, x, node) { +if (x->key == a.key && x->data == a.data) + a.visited +=1 ; +if (x->key == b.key && x->data == b.data) + b.visited +=1 ;
I think we could improve this by checking 'x->key' is one of {a,b}. Daniel's suggestions below are good, otherwise perhaps something like:
x->visited++;
if (x->key == a.key)
KUNIT_EXPECT_EQ(x->data, a.data);
else if (x->key == b.key)
KUNIT_EXPECT_EQ(x->data, b.data);
else
KUNIT_EXPECT_NEQ(x->key, x->key); /* Not an expected key. */The other, more over-the-top option would be to have an array of struct hashtable_test_entry, rather than separate a and b variables, and to loop over them, e.g.
x->visited++;
for (int i = 0; i < ARRAY_SIZE(entries); ++i) {
if (entires[i]->key == x->key) {
…
break;
}
KUNIT_EXPECT_NEQ_MSG(x->key, x->key, "Unexxpected element in hashtable");
}But I suspect the first is actually cleaner.
Quoted 16 lines
lib/hashtable_test.c new file +16
-0+ } + +/* 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 ); + +hash_init (hash); + a.key =1 ; + a.data =13 ; + b.key =2 ;
lib/hashtable_test.c line 113
Quoted 10 lines
lib/hashtable_test.c new file +10
-0+ b.data =10 ; + b.visited =0 ; + +hash_add (hash, &a.node, a.key); +hash_add (hash, &b.node, b.key); + +hash_del (&b.node); +hash_for_each_possible (hash, x, node, b.key) { +if (x->key == b.key && x->data == b.data) + b.visited +=1 ;
Again, just increment x->visited here, and possibly add KUNIT_EXPECT_NEQ(x->key, b.key).
Quoted 21 lines
lib/hashtable_test.c new file +21
-0+ } + +/* 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++) {
lib/hashtable_test.c line 144
Quoted 10 lines
lib/hashtable_test.c new file +10
-0+ 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) { +if (x->key >=0 && x->key <3 ) + entries[x->key].visited +=1 ;
Again, let's just increment x->visited, and maybeKUNIT_EXPECT_GEQ(x->key, 0), ..._LEQ(x->key, 3).
Quoted 74 lines
lib/hashtable_test.c new file +74
-0+ 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) { +if (x->key >=0 && x->key <3 ) { + entries[x->key].visited +=1 ; +hash_del (&entries[x->key].node); + } + 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_possible (struct kunit *test) +{ +struct hashtable_test_entry entries[4 ]; +struct hashtable_test_entry *x; +int i, j, count; +DEFINE_HASHTABLE (hash,3 ); + +/* Initialize a hashtable with three entries with key = 1. */ +hash_init (hash); +for (i =0 ; i <3 ; i++) { + entries[i].key =1 ; + entries[i].data = i; + entries[i].visited =0 ; +hash_add (hash, &entries[i].node, entries[i].key); + } + +/* Add an entry with key = 2. */ + entries[3 ].key =2 ; + 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,1 ) { +if (x->data >=0 && x->data <4 ) + entries[x->data].visited +=1 ; + count++; + } + +/* Should have visited each entry with key = 1 exactly once. */ +for (j =0 ; j <3 ; j++) +KUNIT_EXPECT_EQ (test, entries[j].visited,1 ); +
lib/hashtable_test.c line 228
Quoted 10 lines
lib/hashtable_test.c new file +10
-0+/* If entry with key = 2 is in the same bucket as the entries with +* key = 1, check it was visited. Otherwise ensure that only three +* entries were visited. +*/ +if (hash_min (1 ,HASH_BITS (hash)) ==hash_min (2 ,HASH_BITS (hash))) { +KUNIT_EXPECT_EQ (test, count,4 ); +KUNIT_EXPECT_EQ (test, entries[3 ].visited,1 ); + }else { +KUNIT_EXPECT_EQ (test, count,3 ); + }
I'm a bit on-the-fence about whether or not this is too implementation-specific. I think the way the hashtable works here is supposed to be stable, but given that almost nothing in the actual kernel seems to rely on hash_min directly, maybe it's better to not lock it in with a test.
How about reducing this to a KUNIT_EXPECT_GEQ(test, count, 4)?
Quoted 76 lines
lib/hashtable_test.c new file +71
-0+} + +static void hashtable_test_hash_for_each_possible_safe (struct kunit *test) +{ +struct hashtable_test_entry entries[4 ]; +struct hashtable_test_entry *x; +struct hlist_node *tmp; +int i, j, count; +DEFINE_HASHTABLE (hash,3 ); + +/* Initialize a hashtable with three entries with key = 1. */ +hash_init (hash); +for (i =0 ; i <3 ; i++) { + entries[i].key =1 ; + entries[i].data = i; + entries[i].visited =0 ; +hash_add (hash, &entries[i].node, entries[i].key); + } + +/* Add an entry with key = 2. */ + entries[3 ].key =2 ; + 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,1 ) { +if (x->data >=0 && x->data <4 ) { + entries[x->data].visited +=1 ; +hash_del (&entries[x->data].node); + } + count++; + } + +/* Should have visited each entry with key = 1 exactly once. */ +for (j =0 ; j <3 ; j++) +KUNIT_EXPECT_EQ (test, entries[j].visited,1 ); + +/* If entry with key = 2 is in the same bucket as the entries with +* key = 1, check it was visited. Otherwise ensure that only three +* entries were visited. +*/ +if (hash_min (1 ,HASH_BITS (hash)) ==hash_min (2 ,HASH_BITS (hash))) { +KUNIT_EXPECT_EQ (test, count,4 ); +KUNIT_EXPECT_EQ (test, entries[3 ].visited,1 ); + }else { +KUNIT_EXPECT_EQ (test, count,3 ); + } +} + +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:
054be257f28ca8eeb8e3620766501b81ceb4b293--
2.39.0.314.g84b9a713c41-goog