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]>
---
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_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
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 <[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;
+ if (x->key == b.key && x->data == b.data)
+ b.visited += 1;
+ }
+
+ /* 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;
+ }
+
+ /* 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;
+ 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))) {
+ KUNIT_EXPECT_EQ(test, count, 4);
+ KUNIT_EXPECT_EQ(test, entries[3].visited, 1);
+ } else {
+ KUNIT_EXPECT_EQ(test, count, 3);
+ }
+}
+
+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
On Mon, Dec 19, 2022 at 7:16 PM Rae Moar <[email protected]> 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 <[email protected]>
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_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.
> + 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
> 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 <[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;
> + 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, ...);
> +
> + /* 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.
> + }
> +
> + /* 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);
> + 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 { ... }
> + 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
On Tue, 20 Dec 2022 at 11:16, Rae Moar <[email protected]> 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 <[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
>
> 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...
>
> 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_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
> 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 <[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;
> + 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.
> + }
> +
> + /* 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;
Again, just increment x->visited here, and possibly add
KUNIT_EXPECT_NEQ(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) {
> + 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).
> + 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))) {
> + 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)?
> +}
> +
> +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
>
On Tue, Dec 27, 2022 at 9:00 PM Daniel Latypov <[email protected]> wrote:
>
> On Mon, Dec 19, 2022 at 7:16 PM Rae Moar <[email protected]> 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 <[email protected]>
>
> 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_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!
>
> > + 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
> > 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 <[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;
> > + 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
On Fri, Jan 13, 2023 at 2:23 PM Rae Moar <[email protected]> wrote:
<snip>
> > 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?
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