From: David Gow <davidgow@google.com>
To: Rae Moar <rmoar@google.com>
Cc: brendanhiggins@google.com, dlatypov@google.com,
skhan@linuxfoundation.org, kunit-dev@googlegroups.com,
linux-kernel@vger.kernel.org, linux-kselftest@vger.kernel.org
Subject: Re: [PATCH v1] lib/hashtable_test.c: add test for the hashtable structure
Date: Tue, 10 Jan 2023 12:23:54 +0800 [thread overview]
Message-ID: <CABVgOS=gSOqa4td5ta4Ma85-hHJ0qXp_WFga9z6se80HJC1ayQ@mail.gmail.com> (raw)
In-Reply-To: <20221220031023.197178-1-rmoar@google.com>
On Tue, 20 Dec 2022 at 11:16, 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>
> ---
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@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) {
> + 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
>
prev parent reply other threads:[~2023-01-10 4:24 UTC|newest]
Thread overview: 5+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-12-20 3:10 [PATCH v1] lib/hashtable_test.c: add test for the hashtable structure Rae Moar
2022-12-28 2:00 ` Daniel Latypov
2023-01-13 22:23 ` Rae Moar
2023-01-13 22:45 ` Daniel Latypov
2023-01-10 4:23 ` David Gow [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CABVgOS=gSOqa4td5ta4Ma85-hHJ0qXp_WFga9z6se80HJC1ayQ@mail.gmail.com' \
--to=davidgow@google.com \
--cc=brendanhiggins@google.com \
--cc=dlatypov@google.com \
--cc=kunit-dev@googlegroups.com \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-kselftest@vger.kernel.org \
--cc=rmoar@google.com \
--cc=skhan@linuxfoundation.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.