1*db6fe4d6SKees Cook // SPDX-License-Identifier: GPL-2.0-only
2*db6fe4d6SKees Cook #include <kunit/test.h>
3*db6fe4d6SKees Cook
4*db6fe4d6SKees Cook #include <linux/kernel.h>
5*db6fe4d6SKees Cook #include <linux/list_sort.h>
6*db6fe4d6SKees Cook #include <linux/list.h>
7*db6fe4d6SKees Cook #include <linux/module.h>
8*db6fe4d6SKees Cook #include <linux/printk.h>
9*db6fe4d6SKees Cook #include <linux/slab.h>
10*db6fe4d6SKees Cook #include <linux/random.h>
11*db6fe4d6SKees Cook
12*db6fe4d6SKees Cook /*
13*db6fe4d6SKees Cook * The pattern of set bits in the list length determines which cases
14*db6fe4d6SKees Cook * are hit in list_sort().
15*db6fe4d6SKees Cook */
16*db6fe4d6SKees Cook #define TEST_LIST_LEN (512+128+2) /* not including head */
17*db6fe4d6SKees Cook
18*db6fe4d6SKees Cook #define TEST_POISON1 0xDEADBEEF
19*db6fe4d6SKees Cook #define TEST_POISON2 0xA324354C
20*db6fe4d6SKees Cook
21*db6fe4d6SKees Cook struct debug_el {
22*db6fe4d6SKees Cook unsigned int poison1;
23*db6fe4d6SKees Cook struct list_head list;
24*db6fe4d6SKees Cook unsigned int poison2;
25*db6fe4d6SKees Cook int value;
26*db6fe4d6SKees Cook unsigned int serial;
27*db6fe4d6SKees Cook };
28*db6fe4d6SKees Cook
check(struct kunit * test,struct debug_el * ela,struct debug_el * elb)29*db6fe4d6SKees Cook static void check(struct kunit *test, struct debug_el *ela, struct debug_el *elb)
30*db6fe4d6SKees Cook {
31*db6fe4d6SKees Cook struct debug_el **elts = test->priv;
32*db6fe4d6SKees Cook
33*db6fe4d6SKees Cook KUNIT_EXPECT_LT_MSG(test, ela->serial, (unsigned int)TEST_LIST_LEN, "incorrect serial");
34*db6fe4d6SKees Cook KUNIT_EXPECT_LT_MSG(test, elb->serial, (unsigned int)TEST_LIST_LEN, "incorrect serial");
35*db6fe4d6SKees Cook
36*db6fe4d6SKees Cook KUNIT_EXPECT_PTR_EQ_MSG(test, elts[ela->serial], ela, "phantom element");
37*db6fe4d6SKees Cook KUNIT_EXPECT_PTR_EQ_MSG(test, elts[elb->serial], elb, "phantom element");
38*db6fe4d6SKees Cook
39*db6fe4d6SKees Cook KUNIT_EXPECT_EQ_MSG(test, ela->poison1, TEST_POISON1, "bad poison");
40*db6fe4d6SKees Cook KUNIT_EXPECT_EQ_MSG(test, ela->poison2, TEST_POISON2, "bad poison");
41*db6fe4d6SKees Cook
42*db6fe4d6SKees Cook KUNIT_EXPECT_EQ_MSG(test, elb->poison1, TEST_POISON1, "bad poison");
43*db6fe4d6SKees Cook KUNIT_EXPECT_EQ_MSG(test, elb->poison2, TEST_POISON2, "bad poison");
44*db6fe4d6SKees Cook }
45*db6fe4d6SKees Cook
46*db6fe4d6SKees Cook /* `priv` is the test pointer so check() can fail the test if the list is invalid. */
cmp(void * priv,const struct list_head * a,const struct list_head * b)47*db6fe4d6SKees Cook static int cmp(void *priv, const struct list_head *a, const struct list_head *b)
48*db6fe4d6SKees Cook {
49*db6fe4d6SKees Cook struct debug_el *ela, *elb;
50*db6fe4d6SKees Cook
51*db6fe4d6SKees Cook ela = container_of(a, struct debug_el, list);
52*db6fe4d6SKees Cook elb = container_of(b, struct debug_el, list);
53*db6fe4d6SKees Cook
54*db6fe4d6SKees Cook check(priv, ela, elb);
55*db6fe4d6SKees Cook return ela->value - elb->value;
56*db6fe4d6SKees Cook }
57*db6fe4d6SKees Cook
list_sort_test(struct kunit * test)58*db6fe4d6SKees Cook static void list_sort_test(struct kunit *test)
59*db6fe4d6SKees Cook {
60*db6fe4d6SKees Cook int i, count = 1;
61*db6fe4d6SKees Cook struct debug_el *el, **elts;
62*db6fe4d6SKees Cook struct list_head *cur;
63*db6fe4d6SKees Cook LIST_HEAD(head);
64*db6fe4d6SKees Cook
65*db6fe4d6SKees Cook elts = kunit_kcalloc(test, TEST_LIST_LEN, sizeof(*elts), GFP_KERNEL);
66*db6fe4d6SKees Cook KUNIT_ASSERT_NOT_ERR_OR_NULL(test, elts);
67*db6fe4d6SKees Cook test->priv = elts;
68*db6fe4d6SKees Cook
69*db6fe4d6SKees Cook for (i = 0; i < TEST_LIST_LEN; i++) {
70*db6fe4d6SKees Cook el = kunit_kmalloc(test, sizeof(*el), GFP_KERNEL);
71*db6fe4d6SKees Cook KUNIT_ASSERT_NOT_ERR_OR_NULL(test, el);
72*db6fe4d6SKees Cook
73*db6fe4d6SKees Cook /* force some equivalencies */
74*db6fe4d6SKees Cook el->value = get_random_u32_below(TEST_LIST_LEN / 3);
75*db6fe4d6SKees Cook el->serial = i;
76*db6fe4d6SKees Cook el->poison1 = TEST_POISON1;
77*db6fe4d6SKees Cook el->poison2 = TEST_POISON2;
78*db6fe4d6SKees Cook elts[i] = el;
79*db6fe4d6SKees Cook list_add_tail(&el->list, &head);
80*db6fe4d6SKees Cook }
81*db6fe4d6SKees Cook
82*db6fe4d6SKees Cook list_sort(test, &head, cmp);
83*db6fe4d6SKees Cook
84*db6fe4d6SKees Cook for (cur = head.next; cur->next != &head; cur = cur->next) {
85*db6fe4d6SKees Cook struct debug_el *el1;
86*db6fe4d6SKees Cook int cmp_result;
87*db6fe4d6SKees Cook
88*db6fe4d6SKees Cook KUNIT_ASSERT_PTR_EQ_MSG(test, cur->next->prev, cur,
89*db6fe4d6SKees Cook "list is corrupted");
90*db6fe4d6SKees Cook
91*db6fe4d6SKees Cook cmp_result = cmp(test, cur, cur->next);
92*db6fe4d6SKees Cook KUNIT_ASSERT_LE_MSG(test, cmp_result, 0, "list is not sorted");
93*db6fe4d6SKees Cook
94*db6fe4d6SKees Cook el = container_of(cur, struct debug_el, list);
95*db6fe4d6SKees Cook el1 = container_of(cur->next, struct debug_el, list);
96*db6fe4d6SKees Cook if (cmp_result == 0) {
97*db6fe4d6SKees Cook KUNIT_ASSERT_LE_MSG(test, el->serial, el1->serial,
98*db6fe4d6SKees Cook "order of equivalent elements not preserved");
99*db6fe4d6SKees Cook }
100*db6fe4d6SKees Cook
101*db6fe4d6SKees Cook check(test, el, el1);
102*db6fe4d6SKees Cook count++;
103*db6fe4d6SKees Cook }
104*db6fe4d6SKees Cook KUNIT_EXPECT_PTR_EQ_MSG(test, head.prev, cur, "list is corrupted");
105*db6fe4d6SKees Cook
106*db6fe4d6SKees Cook KUNIT_EXPECT_EQ_MSG(test, count, TEST_LIST_LEN,
107*db6fe4d6SKees Cook "list length changed after sorting!");
108*db6fe4d6SKees Cook }
109*db6fe4d6SKees Cook
110*db6fe4d6SKees Cook static struct kunit_case list_sort_cases[] = {
111*db6fe4d6SKees Cook KUNIT_CASE(list_sort_test),
112*db6fe4d6SKees Cook {}
113*db6fe4d6SKees Cook };
114*db6fe4d6SKees Cook
115*db6fe4d6SKees Cook static struct kunit_suite list_sort_suite = {
116*db6fe4d6SKees Cook .name = "list_sort",
117*db6fe4d6SKees Cook .test_cases = list_sort_cases,
118*db6fe4d6SKees Cook };
119*db6fe4d6SKees Cook
120*db6fe4d6SKees Cook kunit_test_suites(&list_sort_suite);
121*db6fe4d6SKees Cook
122*db6fe4d6SKees Cook MODULE_DESCRIPTION("list_sort() KUnit test suite");
123*db6fe4d6SKees Cook MODULE_LICENSE("GPL");
124