[v1] list: test: Test the klist structure

  Add KUnit tests to the klist linked-list structure.
These perform testing for different variations of node add
and node delete in the klist data structure (<linux/klist.h>).

Limitation: Since we use a static global variable, and if
multiple instances of this test are run concurrently, the test may fail.

Signed-off-by: Sadiya Kazi <sadiyakazi@google.com>
---
 lib/list-test.c | 298 +++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 297 insertions(+), 1 deletion(-)
  

On Wed, Mar 29, 2023 at 7:07 AM Sadiya Kazi <sadiyakazi@google.com> wrote:
>
> Add KUnit tests to the klist linked-list structure.
> These perform testing for different variations of node add
> and node delete in the klist data structure (<linux/klist.h>).
>
> Limitation: Since we use a static global variable, and if
> multiple instances of this test are run concurrently, the test may fail.
>
> Signed-off-by: Sadiya Kazi <sadiyakazi@google.com>

Looks good!

Reviewed-by: Brendan Higgins <brendanhiggins@google.com>
  

On Wed, 29 Mar 2023 at 19:07, Sadiya Kazi <sadiyakazi@google.com> wrote:
>
> Add KUnit tests to the klist linked-list structure.
> These perform testing for different variations of node add
> and node delete in the klist data structure (<linux/klist.h>).
>
> Limitation: Since we use a static global variable, and if
> multiple instances of this test are run concurrently, the test may fail.
>
> Signed-off-by: Sadiya Kazi <sadiyakazi@google.com>
> ---

Thanks very much! This will be a great addition to the list tests (and
the device model tests).

A couple of super-minor suggestions re: comment formatting, otherwise
good-to-go.

Reviewed-by: David Gow <davidgow@google.com>

Cheers,
-- David

>  lib/list-test.c | 298 +++++++++++++++++++++++++++++++++++++++++++++++-
>  1 file changed, 297 insertions(+), 1 deletion(-)
>
> diff --git a/lib/list-test.c b/lib/list-test.c
> index d374cf5d1a57..af651cacb8f4 100644
> --- a/lib/list-test.c
> +++ b/lib/list-test.c
> @@ -8,6 +8,7 @@
>  #include <kunit/test.h>
>
>  #include <linux/list.h>
> +#include <linux/klist.h>
>
>  struct list_test_struct {
>         int data;
> @@ -1199,6 +1200,301 @@ static struct kunit_suite hlist_test_module = {
>         .test_cases = hlist_test_cases,
>  };
>
> -kunit_test_suites(&list_test_module, &hlist_test_module);
> +
> +struct klist_test_struct {
> +       int data;
> +       struct klist klist;
> +       struct klist_node klist_node;
> +};
> +
> +/* counts the number of nodes*/

This comment doesn't really add anything,

> +static int node_count;
> +static struct klist_node *last_node_count;

This isn't a count... can we rename it?

> +
> +static void check_node(struct klist_node *node_ptr)
> +{
> +       node_count++;
> +       last_node_count = node_ptr;
> +}
> +
> +static void check_delete_node(struct klist_node *node_ptr)
> +{
> +       node_count--;
> +       last_node_count = node_ptr;
> +}
> +
> +static void klist_test_add_tail(struct kunit *test)
> +{
> +       struct klist_node a, b;
> +       struct klist mylist;
> +       struct klist_iter i;
> +
> +       node_count = 0;
> +       klist_init(&mylist, &check_node, NULL);
> +
> +       klist_add_tail(&a, &mylist);
> +       KUNIT_EXPECT_EQ(test, node_count, 1);
> +       KUNIT_EXPECT_PTR_EQ(test, last_node_count, &a);
> +
> +       klist_add_tail(&b, &mylist);
> +       KUNIT_EXPECT_EQ(test, node_count, 2);
> +       KUNIT_EXPECT_PTR_EQ(test, last_node_count, &b);
> +
> +       /* should be [list] -> a -> b */
> +       klist_iter_init(&mylist, &i);
> +
> +       KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &a);
> +       KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &b);
> +       KUNIT_EXPECT_NULL(test, klist_next(&i));
> +
> +       klist_iter_exit(&i);
> +
> +}
> +
> +static void klist_test_add_head(struct kunit *test)
> +{
> +       struct klist_node a, b;
> +       struct klist mylist;
> +       struct klist_iter i;
> +
> +       node_count = 0;
> +       klist_init(&mylist, &check_node, NULL);
> +
> +       klist_add_head(&a, &mylist);
> +       KUNIT_EXPECT_EQ(test, node_count, 1);
> +       KUNIT_EXPECT_PTR_EQ(test, last_node_count, &a);
> +
> +       klist_add_head(&b, &mylist);
> +       KUNIT_EXPECT_EQ(test, node_count, 2);
> +       KUNIT_EXPECT_PTR_EQ(test, last_node_count, &b);
> +
> +       /* should be [list] -> b -> a */
> +       klist_iter_init(&mylist, &i);
> +
> +       KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &b);
> +       KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &a);
> +       KUNIT_EXPECT_NULL(test, klist_next(&i));
> +
> +       klist_iter_exit(&i);
> +
> +}
> +
> +static void klist_test_add_behind(struct kunit *test)
> +{
> +       struct klist_node a, b, c, d;
> +       struct klist mylist;
> +       struct klist_iter i;
> +
> +       node_count = 0;
> +       klist_init(&mylist, &check_node, NULL);
> +
> +       klist_add_head(&a, &mylist);
> +       klist_add_head(&b, &mylist);
> +
> +       klist_add_behind(&c, &a);
> +       KUNIT_EXPECT_EQ(test, node_count, 3);
> +       KUNIT_EXPECT_PTR_EQ(test, last_node_count, &c);
> +
> +       klist_add_behind(&d, &b);
> +       KUNIT_EXPECT_EQ(test, node_count, 4);
> +       KUNIT_EXPECT_PTR_EQ(test, last_node_count, &d);
> +
> +       klist_iter_init(&mylist, &i);
> +
> +       /* should be [list] -> b -> d -> a -> c*/
> +       KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &b);
> +       KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &d);
> +       KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &a);
> +       KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &c);
> +       KUNIT_EXPECT_NULL(test, klist_next(&i));
> +
> +       klist_iter_exit(&i);
> +
> +}
> +
> +static void klist_test_add_before(struct kunit *test)
> +{
> +       struct klist_node a, b, c, d;
> +       struct klist mylist;
> +       struct klist_iter i;
> +
> +       node_count = 0;
> +       klist_init(&mylist, &check_node, NULL);
> +
> +       klist_add_head(&a, &mylist);
> +       klist_add_head(&b, &mylist);
> +       klist_add_before(&c, &a);
> +       KUNIT_EXPECT_EQ(test, node_count, 3);
> +       KUNIT_EXPECT_PTR_EQ(test, last_node_count, &c);
> +
> +       klist_add_before(&d, &b);
> +       KUNIT_EXPECT_EQ(test, node_count, 4);
> +       KUNIT_EXPECT_PTR_EQ(test, last_node_count, &d);
> +
> +       klist_iter_init(&mylist, &i);
> +
> +       /* should be [list] -> b -> d -> a -> c*/
> +       KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &d);
> +       KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &b);
> +       KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &c);
> +       KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &a);
> +       KUNIT_EXPECT_NULL(test, klist_next(&i));
> +
> +       klist_iter_exit(&i);
> +
> +}
> +
> +/* Verify that klist_del() delays the deletion of a node until there
> + * are no other references to it
> + */

These comments are in the wrong style:
https://www.kernel.org/doc/html/latest/process/coding-style.html#commenting

They should be of the form:
/*
 * Text
 * More text
 */
(with the empty line at the top)

> +static void klist_test_del_refcount_greater_than_zero(struct kunit *test)
> +{
> +       struct klist_node a, b, c, d;
> +       struct klist mylist;
> +       struct klist_iter i;
> +
> +       node_count = 0;
> +       klist_init(&mylist, &check_node, &check_delete_node);
> +
> +       /* Add nodes a,b,c,d to the list*/
> +       klist_add_tail(&a, &mylist);
> +       klist_add_tail(&b, &mylist);
> +       klist_add_tail(&c, &mylist);
> +       klist_add_tail(&d, &mylist);
> +
> +       klist_iter_init(&mylist, &i);
> +
> +       KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &a);
> +       KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &b);
> +       /* Advance the iterator to point to node c*/
> +       KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &c);
> +
> +       /* Try to delete node c while there is a reference to it*/
> +       klist_del(&c);
> +
> +       /*
> +        * Verify that node c is still attached to the list even after being
> +        * deleted. Since the iterator still points to c, the reference count is not
> +        * decreased to 0
> +        */
> +       KUNIT_EXPECT_TRUE(test, klist_node_attached(&c));
> +
> +       /* Check that node c has not been removed yet*/
> +       KUNIT_EXPECT_EQ(test, node_count, 4);
> +       KUNIT_EXPECT_PTR_EQ(test, last_node_count, &d);
> +
> +       klist_iter_exit(&i);
> +
> +       /* Since the iterator is no longer pointing to node c, node c is removed
> +        * from the list
> +        */

Nit: comment formatting. The comment above ("Verify that node c...") looks good.

> +       KUNIT_EXPECT_EQ(test, node_count, 3);
> +       KUNIT_EXPECT_PTR_EQ(test, last_node_count, &c);
> +
> +}
> +
> +/* Verify that klist_del() deletes a node immediately when there are no
> + * other references to it.
> + */

As above, comment formatting.

> +static void klist_test_del_refcount_zero(struct kunit *test)
> +{
> +       struct klist_node a, b, c, d;
> +       struct klist mylist;
> +       struct klist_iter i;
> +
> +       node_count = 0;
> +       klist_init(&mylist, &check_node, &check_delete_node);
> +
> +       /* Add nodes a,b,c,d to the list*/
> +       klist_add_tail(&a, &mylist);
> +       klist_add_tail(&b, &mylist);
> +       klist_add_tail(&c, &mylist);
> +       klist_add_tail(&d, &mylist);
> +       /* Delete node c*/
> +       klist_del(&c);
> +
> +       /* Check that node c is deleted from the list*/
> +       KUNIT_EXPECT_EQ(test, node_count, 3);
> +       KUNIT_EXPECT_PTR_EQ(test, last_node_count, &c);
> +
> +       /* Should be [list] -> a -> b -> d*/
> +       klist_iter_init(&mylist, &i);
> +
> +       KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &a);
> +       KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &b);
> +       KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &d);
> +       KUNIT_EXPECT_NULL(test, klist_next(&i));
> +
> +       klist_iter_exit(&i);
> +
> +}
> +
> +static void klist_test_remove(struct kunit *test)
> +{
> +       /* This test doesn't check correctness under concurrent access */
> +       struct klist_node a, b, c, d;
> +       struct klist mylist;
> +       struct klist_iter i;
> +
> +       node_count = 0;
> +       klist_init(&mylist, &check_node, &check_delete_node);
> +
> +       /* Add nodes a,b,c,d to the list*/
> +       klist_add_tail(&a, &mylist);
> +       klist_add_tail(&b, &mylist);
> +       klist_add_tail(&c, &mylist);
> +       klist_add_tail(&d, &mylist);
> +       /* Delete node c*/
> +       klist_remove(&c);
> +
> +       /* Check the nodes in the list*/
> +       KUNIT_EXPECT_EQ(test, node_count, 3);
> +       KUNIT_EXPECT_PTR_EQ(test, last_node_count, &c);
> +
> +       /* should be [list] -> a -> b -> d*/
> +       klist_iter_init(&mylist, &i);
> +
> +       KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &a);
> +       KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &b);
> +       KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &d);
> +       KUNIT_EXPECT_NULL(test, klist_next(&i));
> +
> +       klist_iter_exit(&i);
> +
> +}
> +
> +static void klist_test_node_attached(struct kunit *test)
> +{
> +       struct klist_node a = {};
> +       struct klist mylist;
> +
> +       klist_init(&mylist, NULL, NULL);
> +
> +       KUNIT_EXPECT_FALSE(test, klist_node_attached(&a));
> +       klist_add_head(&a, &mylist);
> +       KUNIT_EXPECT_TRUE(test, klist_node_attached(&a));
> +       klist_del(&a);
> +       KUNIT_EXPECT_FALSE(test, klist_node_attached(&a));
> +
> +}
> +
> +static struct kunit_case klist_test_cases[] = {
> +       KUNIT_CASE(klist_test_add_tail),
> +       KUNIT_CASE(klist_test_add_head),
> +       KUNIT_CASE(klist_test_add_behind),
> +       KUNIT_CASE(klist_test_add_before),
> +       KUNIT_CASE(klist_test_del_refcount_greater_than_zero),
> +       KUNIT_CASE(klist_test_del_refcount_zero),
> +       KUNIT_CASE(klist_test_remove),
> +       KUNIT_CASE(klist_test_node_attached),
> +       {},
> +};
> +
> +static struct kunit_suite klist_test_module = {
> +       .name = "klist",
> +       .test_cases = klist_test_cases,
> +};
> +
> +kunit_test_suites(&list_test_module, &hlist_test_module, &klist_test_module);
>
>  MODULE_LICENSE("GPL v2");
> --
> 2.40.0.348.gf938b09366-goog
>