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

[Rae Moar]

On Tue, Dec 27, 2022 at 9:00 PM Daniel Latypov <dlatypov@xxxxxxxxxx> wrote:
>
> On Mon, Dec 19, 2022 at 7:16 PM 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>
>
> 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 <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;
> > +       }
>
>   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