Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
Date:   Wed, 29 Mar 2023 11:07:22 +0000
Mime-Version: 1.0
Message-ID: <20230329110723.3458843-1-sadiyakazi@google.com>
Subject: [PATCH v1] list: test: Test the klist structure
From:   Sadiya Kazi <sadiyakazi@google.com>
To:     brendanhiggins@google.com, davidgow@google.com,
        skhan@linuxfoundation.org, corbet@lwn.net
Cc:     Sadiya Kazi <sadiyakazi@google.com>,
        linux-kselftest@vger.kernel.org, kunit-dev@googlegroups.com,
        linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org
Content-Type: text/plain; charset="UTF-8"
Precedence: bulk

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(-)

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*/
+static int node_count;
+static struct klist_node *last_node_count;
+
+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
+ */
+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
+	 */
+	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.
+ */
+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