Skip to contentSkip to conversation

lib/hashtable_test.c: add test for the hashtable structure

PATCH Superseded Rae Moar 3 participants 5 messages Dec 20, 2022 – Jan 13, 2023

Subsystems (2)

v1 of 3 Superseded Latest is v3 →

lore
Share & tools
lore

Rae Moar

author
#0 lore raw

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
index 3fc7abffc7aa..3cf3b6f8cff4 100644
@@ -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
index 161d6a724ff7..9036d3aeee0a 100644
@@ -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
#1 lore raw
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.

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.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 +0 -0
index 3fc7abffc7aa..3cf3b6f8cff4 100644
@@ -2458,6 +2458,19 @@ config LIST_KUNIT_TEST
 

lib/Kconfig.debug config LIST_KUNIT_TEST · line 2468

Quoted 10 lines
lib/Kconfig.debug +8 -0
          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.

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 KUNIT
lib/Makefile +1 -0
index 161d6a724ff7..9036d3aeee0a 100644
@@ -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 +78 -0
new file mode 100644
index 000000000000..7907df66a8e7
@@ -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

#4 lore raw
In reply to Rae Moar
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.

---

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.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.

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.c
lib/Kconfig.debug +13 -0
index 3fc7abffc7aa..3cf3b6f8cff4 100644
@@ -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
index 161d6a724ff7..9036d3aeee0a 100644
@@ -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 +77 -0
new file mode 100644
index 000000000000..7907df66a8e7
@@ -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 maybe
KUNIT_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

author
#2 lore raw
In reply to Daniel Latypov
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.

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.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 +0 -0
index 3fc7abffc7aa..3cf3b6f8cff4 100644
@@ -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 KUNIT
lib/Makefile +1 -0
index 161d6a724ff7..9036d3aeee0a 100644
@@ -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 +85 -0
new file mode 100644
index 000000000000..7907df66a8e7
@@ -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 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?

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

#3 lore raw

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 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 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