| Message ID | 20230331064528.3764174-1-sadiyakazi@google.com (mailing list archive) |
|---|---|
| State | Accepted |
| Commit | 57b4f760f94da13104cd596d5fb1643ae09c4d49 |
| Headers | show |
| Series | [v2] list: test: Test the klist structure | expand |
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 >
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");