On Tue, Dec 27, 2022 at 9:00 PM Daniel Latypov dlatypov@google.com wrote:
On Mon, Dec 19, 2022 at 7:16 PM Rae Moar rmoar@google.com wrote:
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 rmoar@google.com
Looks pretty good from a cursory glance. Had some mostly stylistic nits/suggestions below.
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
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index 3fc7abffc7aa..3cf3b6f8cff4 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -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_TESTSdepends on KUNITdefault KUNIT_ALL_TESTShelpThis builds the hashtable KUnit test suite.It tests the API and basic functionality of the functionsand 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!
For more information on KUnit and unit tests in general please referto 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 diff --git a/lib/Makefile b/lib/Makefile index 161d6a724ff7..9036d3aeee0a 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -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 diff --git a/lib/hashtable_test.c b/lib/hashtable_test.c new file mode 100644 index 000000000000..7907df66a8e7 --- /dev/null +++ b/lib/hashtable_test.c @@ -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 rmoar@google.com
- */
+#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;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.
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, ...);
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?
/* 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);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.
}/* 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) {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);
Yes, this makes a lot of sense. I will switch out just the if statements for using assert statements.
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);/* 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 { ... }
I really like the idea of using hash_for_each to determine the bucket. I will add this to the test.
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.
Daniel
Thanks Daniel! -Rae