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