[PATCH] lib/tests: add KUnit tests for the timerqueue

[PATCH] lib/tests: add KUnit tests for the timerqueue

[Amit Patole]

lib/timerqueue.c is the time-ordered queue behind hrtimers, POSIX CPU
timers and the alarm timers, and since commit 1339eeb73d6b
("timerqueue: Provide linked timerqueue") it also has a linked variant
that keeps prev/next pointers for hrtimer rearming. Neither has unit
tests.

Add a KUnit suite that covers:

- an empty queue, and timerqueue_iterate_next(NULL);
- timerqueue_add() returning true only when the node becomes the
  first, and timerqueue_del() returning true while nodes remain;
- iteration in expiry order, and nodes with the same expiry time
  staying in the order they were added;
- a deleted node being queued again;
- 256 nodes with pseudo-random expiry times (fixed seed): order and
  count after inserting, deleting from the middle and draining from
  the front;
- the linked variant: prev/next links in both directions after
  inserts, deletes from the middle and the front, and re-adding; and
  the same pseudo-random stress with every prev link checked.

An AI coding assistant (Claude Opus 5.5) was used to draft the tests.
They were run with "tools/testing/kunit/kunit.py run" on UML (6/6
pass), built with W=1 without warnings, and checked against
deliberately broken versions of the two comparison functions and of
timerqueue_del()'s return value, which the suite catches.

Signed-off-by: Amit Patole <amit.patole@gmail.com>
---
Tested on UML with a kunitconfig of CONFIG_KUNIT=y and

CONFIG_TIMERQUEUE_KUNIT_TEST=y: 6/6 pass.
---
 lib/Kconfig.debug            |  13 ++
 lib/tests/Makefile           |   1 +
 lib/tests/timerqueue_kunit.c | 293 +++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 307 insertions(+)

diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index 2d22638ec13a..5707ed622d5d 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -3461,6 +3461,19 @@ config RATELIMIT_KUNIT_TEST
 
 	  If unsure, say N.
 
+config TIMERQUEUE_KUNIT_TEST
+	tristate "KUnit test for the timerqueue" if !KUNIT_ALL_TESTS
+	depends on KUNIT
+	default KUNIT_ALL_TESTS
+	help
+	  This option enables the KUnit test suite for lib/timerqueue.c,
+	  the time-ordered queue behind hrtimers and POSIX CPU timers.
+	  The tests cover ordering, the return values of the add and
+	  delete helpers, equal expiry times and the prev/next links of
+	  the linked timerqueue.
+
+	  If unsure, say N.
+
 config UUID_KUNIT_TEST
 	tristate "KUnit test for UUID" if !KUNIT_ALL_TESTS
 	depends on KUNIT
diff --git a/lib/tests/Makefile b/lib/tests/Makefile
index df0537e1b91f..1d18cfdca256 100644
--- a/lib/tests/Makefile
+++ b/lib/tests/Makefile
@@ -58,5 +58,6 @@ obj-$(CONFIG_USERCOPY_KUNIT_TEST) += usercopy_kunit.o
 obj-$(CONFIG_UTIL_MACROS_KUNIT) += util_macros_kunit.o
 obj-$(CONFIG_RATELIMIT_KUNIT_TEST) += test_ratelimit.o
 obj-$(CONFIG_UUID_KUNIT_TEST) += uuid_kunit.o
+obj-$(CONFIG_TIMERQUEUE_KUNIT_TEST) += timerqueue_kunit.o
 
 obj-$(CONFIG_TEST_RUNTIME_MODULE)		+= module/
diff --git a/lib/tests/timerqueue_kunit.c b/lib/tests/timerqueue_kunit.c
new file mode 100644
index 000000000000..2499626126ef
--- /dev/null
+++ b/lib/tests/timerqueue_kunit.c
@@ -0,0 +1,293 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * KUnit tests for the timerqueue in lib/timerqueue.c, both the cached
+ * rbtree variant and the linked variant used by hrtimers.
+ */
+
+#include <kunit/test.h>
+#include <linux/module.h>
+#include <linux/prandom.h>
+#include <linux/timerqueue.h>
+
+#define TQ_STRESS_NODES	256
+
+static void timerqueue_empty_test(struct kunit *test)
+{
+	struct timerqueue_head head;
+	struct timerqueue_node node;
+
+	timerqueue_init_head(&head);
+	timerqueue_init(&node);
+
+	KUNIT_EXPECT_NULL(test, timerqueue_getnext(&head));
+	KUNIT_EXPECT_FALSE(test, timerqueue_node_queued(&node));
+	KUNIT_EXPECT_NULL(test, timerqueue_iterate_next(NULL));
+}
+
+static void timerqueue_add_del_test(struct kunit *test)
+{
+	struct timerqueue_head head;
+	struct timerqueue_node a, b, c;
+
+	timerqueue_init_head(&head);
+	timerqueue_init(&a);
+	timerqueue_init(&b);
+	timerqueue_init(&c);
+	a.expires = 20;
+	b.expires = 10;
+	c.expires = 30;
+
+	/* timerqueue_add() returns true when the new node is the first. */
+	KUNIT_EXPECT_TRUE(test, timerqueue_add(&head, &a));
+	KUNIT_EXPECT_TRUE(test, timerqueue_node_queued(&a));
+	KUNIT_EXPECT_PTR_EQ(test, timerqueue_getnext(&head), &a);
+
+	KUNIT_EXPECT_TRUE(test, timerqueue_add(&head, &b));
+	KUNIT_EXPECT_PTR_EQ(test, timerqueue_getnext(&head), &b);
+
+	KUNIT_EXPECT_FALSE(test, timerqueue_add(&head, &c));
+	KUNIT_EXPECT_PTR_EQ(test, timerqueue_getnext(&head), &b);
+
+	/* Iteration is in expiry order. */
+	KUNIT_EXPECT_PTR_EQ(test, timerqueue_iterate_next(&b), &a);
+	KUNIT_EXPECT_PTR_EQ(test, timerqueue_iterate_next(&a), &c);
+	KUNIT_EXPECT_NULL(test, timerqueue_iterate_next(&c));
+
+	/* timerqueue_del() returns true while the queue is not empty. */
+	KUNIT_EXPECT_TRUE(test, timerqueue_del(&head, &b));
+	KUNIT_EXPECT_FALSE(test, timerqueue_node_queued(&b));
+	KUNIT_EXPECT_PTR_EQ(test, timerqueue_getnext(&head), &a);
+
+	/* Deleting a node that is not the first leaves the first alone. */
+	KUNIT_EXPECT_TRUE(test, timerqueue_del(&head, &c));
+	KUNIT_EXPECT_PTR_EQ(test, timerqueue_getnext(&head), &a);
+	KUNIT_EXPECT_NULL(test, timerqueue_iterate_next(&a));
+
+	KUNIT_EXPECT_FALSE(test, timerqueue_del(&head, &a));
+	KUNIT_EXPECT_NULL(test, timerqueue_getnext(&head));
+
+	/* A deleted node can be queued again. */
+	KUNIT_EXPECT_TRUE(test, timerqueue_add(&head, &b));
+	KUNIT_EXPECT_PTR_EQ(test, timerqueue_getnext(&head), &b);
+	KUNIT_EXPECT_FALSE(test, timerqueue_del(&head, &b));
+}
+
+static void timerqueue_equal_expiry_test(struct kunit *test)
+{
+	struct timerqueue_head head;
+	struct timerqueue_node n[3];
+	int i;
+
+	timerqueue_init_head(&head);
+	for (i = 0; i < ARRAY_SIZE(n); i++) {
+		timerqueue_init(&n[i]);
+		n[i].expires = 100;
+	}
+
+	/*
+	 * Nodes with the same expiry time stay in the order they were added,
+	 * and only the first one added reports itself as the new first.
+	 */
+	KUNIT_EXPECT_TRUE(test, timerqueue_add(&head, &n[0]));
+	KUNIT_EXPECT_FALSE(test, timerqueue_add(&head, &n[1]));
+	KUNIT_EXPECT_FALSE(test, timerqueue_add(&head, &n[2]));
+
+	KUNIT_EXPECT_PTR_EQ(test, timerqueue_getnext(&head), &n[0]);
+	KUNIT_EXPECT_PTR_EQ(test, timerqueue_iterate_next(&n[0]), &n[1]);
+	KUNIT_EXPECT_PTR_EQ(test, timerqueue_iterate_next(&n[1]), &n[2]);
+
+	for (i = 0; i < ARRAY_SIZE(n); i++)
+		timerqueue_del(&head, &n[i]);
+	KUNIT_EXPECT_NULL(test, timerqueue_getnext(&head));
+}
+
+/* Check that the queue holds exactly @count nodes, in expiry order. */
+static void timerqueue_check_order(struct kunit *test,
+				   struct timerqueue_head *head,
+				   unsigned int count)
+{
+	struct timerqueue_node *node, *prev = NULL;
+	unsigned int seen = 0;
+
+	for (node = timerqueue_getnext(head); node;
+	     node = timerqueue_iterate_next(node)) {
+		if (prev)
+			KUNIT_EXPECT_LE(test, prev->expires, node->expires);
+		prev = node;
+		seen++;
+	}
+	KUNIT_EXPECT_EQ(test, seen, count);
+}
+
+static void timerqueue_stress_test(struct kunit *test)
+{
+	struct timerqueue_head head;
+	struct timerqueue_node *nodes;
+	struct rnd_state rnd;
+	unsigned int i, left;
+
+	nodes = kunit_kcalloc(test, TQ_STRESS_NODES, sizeof(*nodes), GFP_KERNEL);
+	KUNIT_ASSERT_NOT_NULL(test, nodes);
+
+	prandom_seed_state(&rnd, 42);
+	timerqueue_init_head(&head);
+
+	for (i = 0; i < TQ_STRESS_NODES; i++) {
+		struct timerqueue_node *first = timerqueue_getnext(&head);
+		bool expect_first;
+
+		timerqueue_init(&nodes[i]);
+		/* A small range, so that some expiry times are equal. */
+		nodes[i].expires = prandom_u32_state(&rnd) % 64;
+		expect_first = !first || nodes[i].expires < first->expires;
+		KUNIT_EXPECT_EQ(test, timerqueue_add(&head, &nodes[i]),
+				expect_first);
+	}
+	timerqueue_check_order(test, &head, TQ_STRESS_NODES);
+
+	/* Remove the odd nodes, then drain the queue from the front. */
+	left = TQ_STRESS_NODES;
+	for (i = 1; i < TQ_STRESS_NODES; i += 2) {
+		left--;
+		KUNIT_EXPECT_EQ(test, timerqueue_del(&head, &nodes[i]),
+				left != 0);
+	}
+	timerqueue_check_order(test, &head, left);
+
+	while (left) {
+		struct timerqueue_node *first = timerqueue_getnext(&head);
+		struct timerqueue_node *next;
+
+		KUNIT_ASSERT_NOT_NULL(test, first);
+		next = timerqueue_iterate_next(first);
+		left--;
+		KUNIT_EXPECT_EQ(test, timerqueue_del(&head, first), left != 0);
+		KUNIT_EXPECT_PTR_EQ(test, timerqueue_getnext(&head), next);
+	}
+	KUNIT_EXPECT_NULL(test, timerqueue_getnext(&head));
+}
+
+static void timerqueue_linked_test(struct kunit *test)
+{
+	struct timerqueue_linked_head head;
+	struct timerqueue_linked_node a, b, c;
+
+	timerqueue_linked_init_head(&head);
+	timerqueue_linked_init(&a);
+	timerqueue_linked_init(&b);
+	timerqueue_linked_init(&c);
+	a.expires = 20;
+	b.expires = 10;
+	c.expires = 30;
+
+	KUNIT_EXPECT_NULL(test, timerqueue_linked_first(&head));
+	KUNIT_EXPECT_FALSE(test, timerqueue_linked_node_queued(&a));
+
+	KUNIT_EXPECT_TRUE(test, timerqueue_linked_add(&head, &a));
+	KUNIT_EXPECT_TRUE(test, timerqueue_linked_node_queued(&a));
+	KUNIT_EXPECT_NULL(test, timerqueue_linked_prev(&a));
+	KUNIT_EXPECT_NULL(test, timerqueue_linked_next(&a));
+
+	KUNIT_EXPECT_TRUE(test, timerqueue_linked_add(&head, &b));
+	KUNIT_EXPECT_FALSE(test, timerqueue_linked_add(&head, &c));
+	KUNIT_EXPECT_PTR_EQ(test, timerqueue_linked_first(&head), &b);
+
+	/* The prev/next links follow expiry order in both directions. */
+	KUNIT_EXPECT_NULL(test, timerqueue_linked_prev(&b));
+	KUNIT_EXPECT_PTR_EQ(test, timerqueue_linked_next(&b), &a);
+	KUNIT_EXPECT_PTR_EQ(test, timerqueue_linked_prev(&a), &b);
+	KUNIT_EXPECT_PTR_EQ(test, timerqueue_linked_next(&a), &c);
+	KUNIT_EXPECT_PTR_EQ(test, timerqueue_linked_prev(&c), &a);
+	KUNIT_EXPECT_NULL(test, timerqueue_linked_next(&c));
+
+	/* Deleting from the middle relinks the neighbours. */
+	KUNIT_EXPECT_TRUE(test, timerqueue_linked_del(&head, &a));
+	KUNIT_EXPECT_FALSE(test, timerqueue_linked_node_queued(&a));
+	KUNIT_EXPECT_NULL(test, timerqueue_linked_prev(&a));
+	KUNIT_EXPECT_NULL(test, timerqueue_linked_next(&a));
+	KUNIT_EXPECT_PTR_EQ(test, timerqueue_linked_next(&b), &c);
+	KUNIT_EXPECT_PTR_EQ(test, timerqueue_linked_prev(&c), &b);
+
+	/* Deleting the first node moves the head to the next one. */
+	KUNIT_EXPECT_TRUE(test, timerqueue_linked_del(&head, &b));
+	KUNIT_EXPECT_PTR_EQ(test, timerqueue_linked_first(&head), &c);
+	KUNIT_EXPECT_NULL(test, timerqueue_linked_prev(&c));
+
+	/* Re-adding a deleted node with a later expiry links it last. */
+	a.expires = 40;
+	KUNIT_EXPECT_FALSE(test, timerqueue_linked_add(&head, &a));
+	KUNIT_EXPECT_PTR_EQ(test, timerqueue_linked_next(&c), &a);
+	KUNIT_EXPECT_PTR_EQ(test, timerqueue_linked_prev(&a), &c);
+
+	KUNIT_EXPECT_TRUE(test, timerqueue_linked_del(&head, &c));
+	KUNIT_EXPECT_FALSE(test, timerqueue_linked_del(&head, &a));
+	KUNIT_EXPECT_NULL(test, timerqueue_linked_first(&head));
+}
+
+static void timerqueue_linked_stress_test(struct kunit *test)
+{
+	struct timerqueue_linked_head head;
+	struct timerqueue_linked_node *nodes, *node, *prev;
+	struct rnd_state rnd;
+	unsigned int i, seen;
+
+	nodes = kunit_kcalloc(test, TQ_STRESS_NODES, sizeof(*nodes), GFP_KERNEL);
+	KUNIT_ASSERT_NOT_NULL(test, nodes);
+
+	prandom_seed_state(&rnd, 7);
+	timerqueue_linked_init_head(&head);
+
+	for (i = 0; i < TQ_STRESS_NODES; i++) {
+		struct timerqueue_linked_node *first;
+		bool expect_first;
+
+		first = timerqueue_linked_first(&head);
+		timerqueue_linked_init(&nodes[i]);
+		nodes[i].expires = prandom_u32_state(&rnd) % 64;
+		expect_first = !first || nodes[i].expires < first->expires;
+		KUNIT_EXPECT_EQ(test, timerqueue_linked_add(&head, &nodes[i]),
+				expect_first);
+	}
+
+	/* Remove every third node to exercise relinking. */
+	for (i = 0; i < TQ_STRESS_NODES; i += 3)
+		timerqueue_linked_del(&head, &nodes[i]);
+
+	/* Walk forward checking order and that each prev link points back. */
+	seen = 0;
+	prev = NULL;
+	for (node = timerqueue_linked_first(&head); node;
+	     node = timerqueue_linked_next(node)) {
+		KUNIT_EXPECT_PTR_EQ(test, timerqueue_linked_prev(node), prev);
+		if (prev)
+			KUNIT_EXPECT_LE(test, prev->expires, node->expires);
+		prev = node;
+		seen++;
+	}
+	KUNIT_EXPECT_EQ(test, seen, TQ_STRESS_NODES - (TQ_STRESS_NODES + 2) / 3);
+
+	for (i = 0; i < TQ_STRESS_NODES; i++)
+		if (timerqueue_linked_node_queued(&nodes[i]))
+			timerqueue_linked_del(&head, &nodes[i]);
+	KUNIT_EXPECT_NULL(test, timerqueue_linked_first(&head));
+}
+
+static struct kunit_case timerqueue_test_cases[] = {
+	KUNIT_CASE(timerqueue_empty_test),
+	KUNIT_CASE(timerqueue_add_del_test),
+	KUNIT_CASE(timerqueue_equal_expiry_test),
+	KUNIT_CASE(timerqueue_stress_test),
+	KUNIT_CASE(timerqueue_linked_test),
+	KUNIT_CASE(timerqueue_linked_stress_test),
+	{}
+};
+
+static struct kunit_suite timerqueue_test_suite = {
+	.name = "timerqueue",
+	.test_cases = timerqueue_test_cases,
+};
+
+kunit_test_suite(timerqueue_test_suite);
+
+MODULE_DESCRIPTION("KUnit tests for the timerqueue");
+MODULE_LICENSE("GPL");

---
base-commit: 05441d697f7f9a927264f4058cbbc6a03dfcac9d
change-id: 20261106-kunit-timerqueue-20064ac35b2d

Best regards,
--  
Amit Patole <amit.patole@gmail.com>