Re: [PATCH v1] lib/hashtable_test.c: add test for the hashtable structure

[David Gow]

On Tue, 20 Dec 2022 at 11:16, Rae Moar <rmoar@xxxxxxxxxx> 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@xxxxxxxxxx>
> ---

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 <rmoar@xxxxxxxxxx>
> + */
> +#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
>