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 | |
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. */ |
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(test: priv, ela, elb); |
55 | return ela->value - elb->value; |
56 | } |
57 | |
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, size: 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, size: 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(new: &el->list, head: &head); |
80 | } |
81 | |
82 | list_sort(priv: test, head: &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(priv: test, a: cur, b: 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, ela: el, elb: 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 | |