aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--lib/Kconfig.debug7
-rw-r--r--lib/Makefile1
-rw-r--r--lib/list_sort.c149
-rw-r--r--lib/test_list_sort.c150
4 files changed, 155 insertions, 152 deletions
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index de3f7c151320..e4587ebe52c7 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -1719,11 +1719,12 @@ config LKDTM
1719 Documentation/fault-injection/provoke-crashes.txt 1719 Documentation/fault-injection/provoke-crashes.txt
1720 1720
1721config TEST_LIST_SORT 1721config TEST_LIST_SORT
1722 bool "Linked list sorting test" 1722 tristate "Linked list sorting test"
1723 depends on DEBUG_KERNEL 1723 depends on DEBUG_KERNEL || m
1724 help 1724 help
1725 Enable this to turn on 'list_sort()' function test. This test is 1725 Enable this to turn on 'list_sort()' function test. This test is
1726 executed only once during system boot, so affects only boot time. 1726 executed only once during system boot (so affects only boot time),
1727 or at module load time.
1727 1728
1728 If unsure, say N. 1729 If unsure, say N.
1729 1730
diff --git a/lib/Makefile b/lib/Makefile
index a155c73e3437..0166fbc0fa81 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -52,6 +52,7 @@ obj-$(CONFIG_TEST_FIRMWARE) += test_firmware.o
52obj-$(CONFIG_TEST_HASH) += test_hash.o test_siphash.o 52obj-$(CONFIG_TEST_HASH) += test_hash.o test_siphash.o
53obj-$(CONFIG_TEST_KASAN) += test_kasan.o 53obj-$(CONFIG_TEST_KASAN) += test_kasan.o
54obj-$(CONFIG_TEST_KSTRTOX) += test-kstrtox.o 54obj-$(CONFIG_TEST_KSTRTOX) += test-kstrtox.o
55obj-$(CONFIG_TEST_LIST_SORT) += test_list_sort.o
55obj-$(CONFIG_TEST_LKM) += test_module.o 56obj-$(CONFIG_TEST_LKM) += test_module.o
56obj-$(CONFIG_TEST_RHASHTABLE) += test_rhashtable.o 57obj-$(CONFIG_TEST_RHASHTABLE) += test_rhashtable.o
57obj-$(CONFIG_TEST_SORT) += test_sort.o 58obj-$(CONFIG_TEST_SORT) += test_sort.o
diff --git a/lib/list_sort.c b/lib/list_sort.c
index 3fe401067e20..9e9acc37652f 100644
--- a/lib/list_sort.c
+++ b/lib/list_sort.c
@@ -1,6 +1,3 @@
1
2#define pr_fmt(fmt) "list_sort_test: " fmt
3
4#include <linux/kernel.h> 1#include <linux/kernel.h>
5#include <linux/bug.h> 2#include <linux/bug.h>
6#include <linux/compiler.h> 3#include <linux/compiler.h>
@@ -145,149 +142,3 @@ void list_sort(void *priv, struct list_head *head,
145 merge_and_restore_back_links(priv, cmp, head, part[max_lev], list); 142 merge_and_restore_back_links(priv, cmp, head, part[max_lev], list);
146} 143}
147EXPORT_SYMBOL(list_sort); 144EXPORT_SYMBOL(list_sort);
148
149#ifdef CONFIG_TEST_LIST_SORT
150
151#include <linux/slab.h>
152#include <linux/random.h>
153
154/*
155 * The pattern of set bits in the list length determines which cases
156 * are hit in list_sort().
157 */
158#define TEST_LIST_LEN (512+128+2) /* not including head */
159
160#define TEST_POISON1 0xDEADBEEF
161#define TEST_POISON2 0xA324354C
162
163struct debug_el {
164 unsigned int poison1;
165 struct list_head list;
166 unsigned int poison2;
167 int value;
168 unsigned serial;
169};
170
171/* Array, containing pointers to all elements in the test list */
172static struct debug_el **elts __initdata;
173
174static int __init check(struct debug_el *ela, struct debug_el *elb)
175{
176 if (ela->serial >= TEST_LIST_LEN) {
177 pr_err("error: incorrect serial %d\n", ela->serial);
178 return -EINVAL;
179 }
180 if (elb->serial >= TEST_LIST_LEN) {
181 pr_err("error: incorrect serial %d\n", elb->serial);
182 return -EINVAL;
183 }
184 if (elts[ela->serial] != ela || elts[elb->serial] != elb) {
185 pr_err("error: phantom element\n");
186 return -EINVAL;
187 }
188 if (ela->poison1 != TEST_POISON1 || ela->poison2 != TEST_POISON2) {
189 pr_err("error: bad poison: %#x/%#x\n",
190 ela->poison1, ela->poison2);
191 return -EINVAL;
192 }
193 if (elb->poison1 != TEST_POISON1 || elb->poison2 != TEST_POISON2) {
194 pr_err("error: bad poison: %#x/%#x\n",
195 elb->poison1, elb->poison2);
196 return -EINVAL;
197 }
198 return 0;
199}
200
201static int __init cmp(void *priv, struct list_head *a, struct list_head *b)
202{
203 struct debug_el *ela, *elb;
204
205 ela = container_of(a, struct debug_el, list);
206 elb = container_of(b, struct debug_el, list);
207
208 check(ela, elb);
209 return ela->value - elb->value;
210}
211
212static int __init list_sort_test(void)
213{
214 int i, count = 1, err = -ENOMEM;
215 struct debug_el *el;
216 struct list_head *cur;
217 LIST_HEAD(head);
218
219 pr_debug("start testing list_sort()\n");
220
221 elts = kcalloc(TEST_LIST_LEN, sizeof(*elts), GFP_KERNEL);
222 if (!elts) {
223 pr_err("error: cannot allocate memory\n");
224 return err;
225 }
226
227 for (i = 0; i < TEST_LIST_LEN; i++) {
228 el = kmalloc(sizeof(*el), GFP_KERNEL);
229 if (!el) {
230 pr_err("error: cannot allocate memory\n");
231 goto exit;
232 }
233 /* force some equivalencies */
234 el->value = prandom_u32() % (TEST_LIST_LEN / 3);
235 el->serial = i;
236 el->poison1 = TEST_POISON1;
237 el->poison2 = TEST_POISON2;
238 elts[i] = el;
239 list_add_tail(&el->list, &head);
240 }
241
242 list_sort(NULL, &head, cmp);
243
244 err = -EINVAL;
245 for (cur = head.next; cur->next != &head; cur = cur->next) {
246 struct debug_el *el1;
247 int cmp_result;
248
249 if (cur->next->prev != cur) {
250 pr_err("error: list is corrupted\n");
251 goto exit;
252 }
253
254 cmp_result = cmp(NULL, cur, cur->next);
255 if (cmp_result > 0) {
256 pr_err("error: list is not sorted\n");
257 goto exit;
258 }
259
260 el = container_of(cur, struct debug_el, list);
261 el1 = container_of(cur->next, struct debug_el, list);
262 if (cmp_result == 0 && el->serial >= el1->serial) {
263 pr_err("error: order of equivalent elements not "
264 "preserved\n");
265 goto exit;
266 }
267
268 if (check(el, el1)) {
269 pr_err("error: element check failed\n");
270 goto exit;
271 }
272 count++;
273 }
274 if (head.prev != cur) {
275 pr_err("error: list is corrupted\n");
276 goto exit;
277 }
278
279
280 if (count != TEST_LIST_LEN) {
281 pr_err("error: bad list length %d", count);
282 goto exit;
283 }
284
285 err = 0;
286exit:
287 for (i = 0; i < TEST_LIST_LEN; i++)
288 kfree(elts[i]);
289 kfree(elts);
290 return err;
291}
292late_initcall(list_sort_test);
293#endif /* CONFIG_TEST_LIST_SORT */
diff --git a/lib/test_list_sort.c b/lib/test_list_sort.c
new file mode 100644
index 000000000000..28e817387b04
--- /dev/null
+++ b/lib/test_list_sort.c
@@ -0,0 +1,150 @@
1#define pr_fmt(fmt) "list_sort_test: " fmt
2
3#include <linux/kernel.h>
4#include <linux/list_sort.h>
5#include <linux/list.h>
6#include <linux/module.h>
7#include <linux/printk.h>
8#include <linux/slab.h>
9#include <linux/random.h>
10
11/*
12 * The pattern of set bits in the list length determines which cases
13 * are hit in list_sort().
14 */
15#define TEST_LIST_LEN (512+128+2) /* not including head */
16
17#define TEST_POISON1 0xDEADBEEF
18#define TEST_POISON2 0xA324354C
19
20struct debug_el {
21 unsigned int poison1;
22 struct list_head list;
23 unsigned int poison2;
24 int value;
25 unsigned serial;
26};
27
28/* Array, containing pointers to all elements in the test list */
29static struct debug_el **elts __initdata;
30
31static int __init check(struct debug_el *ela, struct debug_el *elb)
32{
33 if (ela->serial >= TEST_LIST_LEN) {
34 pr_err("error: incorrect serial %d\n", ela->serial);
35 return -EINVAL;
36 }
37 if (elb->serial >= TEST_LIST_LEN) {
38 pr_err("error: incorrect serial %d\n", elb->serial);
39 return -EINVAL;
40 }
41 if (elts[ela->serial] != ela || elts[elb->serial] != elb) {
42 pr_err("error: phantom element\n");
43 return -EINVAL;
44 }
45 if (ela->poison1 != TEST_POISON1 || ela->poison2 != TEST_POISON2) {
46 pr_err("error: bad poison: %#x/%#x\n",
47 ela->poison1, ela->poison2);
48 return -EINVAL;
49 }
50 if (elb->poison1 != TEST_POISON1 || elb->poison2 != TEST_POISON2) {
51 pr_err("error: bad poison: %#x/%#x\n",
52 elb->poison1, elb->poison2);
53 return -EINVAL;
54 }
55 return 0;
56}
57
58static int __init cmp(void *priv, struct list_head *a, struct list_head *b)
59{
60 struct debug_el *ela, *elb;
61
62 ela = container_of(a, struct debug_el, list);
63 elb = container_of(b, struct debug_el, list);
64
65 check(ela, elb);
66 return ela->value - elb->value;
67}
68
69static int __init list_sort_test(void)
70{
71 int i, count = 1, err = -ENOMEM;
72 struct debug_el *el;
73 struct list_head *cur;
74 LIST_HEAD(head);
75
76 pr_debug("start testing list_sort()\n");
77
78 elts = kcalloc(TEST_LIST_LEN, sizeof(*elts), GFP_KERNEL);
79 if (!elts) {
80 pr_err("error: cannot allocate memory\n");
81 return err;
82 }
83
84 for (i = 0; i < TEST_LIST_LEN; i++) {
85 el = kmalloc(sizeof(*el), GFP_KERNEL);
86 if (!el) {
87 pr_err("error: cannot allocate memory\n");
88 goto exit;
89 }
90 /* force some equivalencies */
91 el->value = prandom_u32() % (TEST_LIST_LEN / 3);
92 el->serial = i;
93 el->poison1 = TEST_POISON1;
94 el->poison2 = TEST_POISON2;
95 elts[i] = el;
96 list_add_tail(&el->list, &head);
97 }
98
99 list_sort(NULL, &head, cmp);
100
101 err = -EINVAL;
102 for (cur = head.next; cur->next != &head; cur = cur->next) {
103 struct debug_el *el1;
104 int cmp_result;
105
106 if (cur->next->prev != cur) {
107 pr_err("error: list is corrupted\n");
108 goto exit;
109 }
110
111 cmp_result = cmp(NULL, cur, cur->next);
112 if (cmp_result > 0) {
113 pr_err("error: list is not sorted\n");
114 goto exit;
115 }
116
117 el = container_of(cur, struct debug_el, list);
118 el1 = container_of(cur->next, struct debug_el, list);
119 if (cmp_result == 0 && el->serial >= el1->serial) {
120 pr_err("error: order of equivalent elements not "
121 "preserved\n");
122 goto exit;
123 }
124
125 if (check(el, el1)) {
126 pr_err("error: element check failed\n");
127 goto exit;
128 }
129 count++;
130 }
131 if (head.prev != cur) {
132 pr_err("error: list is corrupted\n");
133 goto exit;
134 }
135
136
137 if (count != TEST_LIST_LEN) {
138 pr_err("error: bad list length %d", count);
139 goto exit;
140 }
141
142 err = 0;
143exit:
144 for (i = 0; i < TEST_LIST_LEN; i++)
145 kfree(elts[i]);
146 kfree(elts);
147 return err;
148}
149module_init(list_sort_test);
150MODULE_LICENSE("GPL");
generated by cgit v1.2.2 (git 2.25.0) at 2026-05-29 19:43:09 -0400