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