Commit | Line | Data |
---|---|---|
09c434b8 | 1 | // SPDX-License-Identifier: GPL-2.0-only |
e327fd7c GU |
2 | #define pr_fmt(fmt) "list_sort_test: " fmt |
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 serial; | |
27 | }; | |
28 | ||
29 | /* Array, containing pointers to all elements in the test list */ | |
30 | static struct debug_el **elts __initdata; | |
31 | ||
32 | static int __init check(struct debug_el *ela, struct debug_el *elb) | |
33 | { | |
34 | if (ela->serial >= TEST_LIST_LEN) { | |
35 | pr_err("error: incorrect serial %d\n", ela->serial); | |
36 | return -EINVAL; | |
37 | } | |
38 | if (elb->serial >= TEST_LIST_LEN) { | |
39 | pr_err("error: incorrect serial %d\n", elb->serial); | |
40 | return -EINVAL; | |
41 | } | |
42 | if (elts[ela->serial] != ela || elts[elb->serial] != elb) { | |
43 | pr_err("error: phantom element\n"); | |
44 | return -EINVAL; | |
45 | } | |
46 | if (ela->poison1 != TEST_POISON1 || ela->poison2 != TEST_POISON2) { | |
47 | pr_err("error: bad poison: %#x/%#x\n", | |
48 | ela->poison1, ela->poison2); | |
49 | return -EINVAL; | |
50 | } | |
51 | if (elb->poison1 != TEST_POISON1 || elb->poison2 != TEST_POISON2) { | |
52 | pr_err("error: bad poison: %#x/%#x\n", | |
53 | elb->poison1, elb->poison2); | |
54 | return -EINVAL; | |
55 | } | |
56 | return 0; | |
57 | } | |
58 | ||
59 | static int __init cmp(void *priv, struct list_head *a, struct list_head *b) | |
60 | { | |
61 | struct debug_el *ela, *elb; | |
62 | ||
63 | ela = container_of(a, struct debug_el, list); | |
64 | elb = container_of(b, struct debug_el, list); | |
65 | ||
66 | check(ela, elb); | |
67 | return ela->value - elb->value; | |
68 | } | |
69 | ||
70 | static int __init list_sort_test(void) | |
71 | { | |
72 | int i, count = 1, err = -ENOMEM; | |
73 | struct debug_el *el; | |
74 | struct list_head *cur; | |
75 | LIST_HEAD(head); | |
76 | ||
77 | pr_debug("start testing list_sort()\n"); | |
78 | ||
79 | elts = kcalloc(TEST_LIST_LEN, sizeof(*elts), GFP_KERNEL); | |
dc2bf000 | 80 | if (!elts) |
e327fd7c | 81 | return err; |
e327fd7c GU |
82 | |
83 | for (i = 0; i < TEST_LIST_LEN; i++) { | |
84 | el = kmalloc(sizeof(*el), GFP_KERNEL); | |
dc2bf000 | 85 | if (!el) |
e327fd7c | 86 | goto exit; |
dc2bf000 | 87 | |
e327fd7c GU |
88 | /* force some equivalencies */ |
89 | el->value = prandom_u32() % (TEST_LIST_LEN / 3); | |
90 | el->serial = i; | |
91 | el->poison1 = TEST_POISON1; | |
92 | el->poison2 = TEST_POISON2; | |
93 | elts[i] = el; | |
94 | list_add_tail(&el->list, &head); | |
95 | } | |
96 | ||
97 | list_sort(NULL, &head, cmp); | |
98 | ||
99 | err = -EINVAL; | |
100 | for (cur = head.next; cur->next != &head; cur = cur->next) { | |
101 | struct debug_el *el1; | |
102 | int cmp_result; | |
103 | ||
104 | if (cur->next->prev != cur) { | |
105 | pr_err("error: list is corrupted\n"); | |
106 | goto exit; | |
107 | } | |
108 | ||
109 | cmp_result = cmp(NULL, cur, cur->next); | |
110 | if (cmp_result > 0) { | |
111 | pr_err("error: list is not sorted\n"); | |
112 | goto exit; | |
113 | } | |
114 | ||
115 | el = container_of(cur, struct debug_el, list); | |
116 | el1 = container_of(cur->next, struct debug_el, list); | |
117 | if (cmp_result == 0 && el->serial >= el1->serial) { | |
118 | pr_err("error: order of equivalent elements not " | |
119 | "preserved\n"); | |
120 | goto exit; | |
121 | } | |
122 | ||
123 | if (check(el, el1)) { | |
124 | pr_err("error: element check failed\n"); | |
125 | goto exit; | |
126 | } | |
127 | count++; | |
128 | } | |
129 | if (head.prev != cur) { | |
130 | pr_err("error: list is corrupted\n"); | |
131 | goto exit; | |
132 | } | |
133 | ||
134 | ||
135 | if (count != TEST_LIST_LEN) { | |
136 | pr_err("error: bad list length %d", count); | |
137 | goto exit; | |
138 | } | |
139 | ||
140 | err = 0; | |
141 | exit: | |
142 | for (i = 0; i < TEST_LIST_LEN; i++) | |
143 | kfree(elts[i]); | |
144 | kfree(elts); | |
145 | return err; | |
146 | } | |
147 | module_init(list_sort_test); | |
148 | MODULE_LICENSE("GPL"); |