[v2] 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>
Reviewed-by: Brendan Higgins <brendanhiggins@google.com>
Reviewed-by: David Gow <davidgow@google.com>
---
Thank you Brendan and David for reviewing this patch. I have addressed
the review comments in this iteration.

Changes since v1:
https://lore.kernel.org/linux-kselftest/20230329110723.3458843-1-sadiyakazi@google.com/

- Corrected the commenting style
- Deleted the comment /* counts the number of nodes*/
- Renamed last_node_count to last_node


---
 lib/list-test.c | 300 +++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 299 insertions(+), 1 deletion(-)
  

On Fri, 31 Mar 2023 at 14:45, 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>
> Reviewed-by: Brendan Higgins <brendanhiggins@google.com>
> Reviewed-by: David Gow <davidgow@google.com>
> ---
> Thank you Brendan and David for reviewing this patch. I have addressed
> the review comments in this iteration.
>
> Changes since v1:
> https://lore.kernel.org/linux-kselftest/20230329110723.3458843-1-sadiyakazi@google.com/
>
> - Corrected the commenting style
> - Deleted the comment /* counts the number of nodes*/
> - Renamed last_node_count to last_node
>
>
> ---

Looks good now, thanks!

-- David

>  lib/list-test.c | 300 +++++++++++++++++++++++++++++++++++++++++++++++-
>  1 file changed, 299 insertions(+), 1 deletion(-)
>
> diff --git a/lib/list-test.c b/lib/list-test.c
> index d374cf5d1a57..0cc27de9cec8 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,303 @@ 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;
> +};
> +
> +static int node_count;
> +static struct klist_node *last_node;
> +
> +static void check_node(struct klist_node *node_ptr)
> +{
> +       node_count++;
> +       last_node = node_ptr;
> +}
> +
> +static void check_delete_node(struct klist_node *node_ptr)
> +{
> +       node_count--;
> +       last_node = 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, &a);
> +
> +       klist_add_tail(&b, &mylist);
> +       KUNIT_EXPECT_EQ(test, node_count, 2);
> +       KUNIT_EXPECT_PTR_EQ(test, last_node, &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, &a);
> +
> +       klist_add_head(&b, &mylist);
> +       KUNIT_EXPECT_EQ(test, node_count, 2);
> +       KUNIT_EXPECT_PTR_EQ(test, last_node, &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, &c);
> +
> +       klist_add_behind(&d, &b);
> +       KUNIT_EXPECT_EQ(test, node_count, 4);
> +       KUNIT_EXPECT_PTR_EQ(test, last_node, &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, &c);
> +
> +       klist_add_before(&d, &b);
> +       KUNIT_EXPECT_EQ(test, node_count, 4);
> +       KUNIT_EXPECT_PTR_EQ(test, last_node, &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
> + */
> +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, &d);
> +
> +       klist_iter_exit(&i);
> +
> +       /*
> +        * Since the iterator is no longer pointing to node c, node c is removed
> +        * from the list
> +        */
> +       KUNIT_EXPECT_EQ(test, node_count, 3);
> +       KUNIT_EXPECT_PTR_EQ(test, last_node, &c);
> +
> +}
> +
> +/*
> + * Verify that klist_del() deletes a node immediately when there are no
> + * other references to it.
> + */
> +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, &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, &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
>