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 return err;
81
82 for (i = 0; i < TEST_LIST_LEN; i++) {
83 el = kmalloc(sizeof(*el), GFP_KERNEL);
84 if (!el)
85 goto exit;
86
87 /* force some equivalencies */
88 el->value = prandom_u32() % (TEST_LIST_LEN / 3);
89 el->serial = i;
90 el->poison1 = TEST_POISON1;
91 el->poison2 = TEST_POISON2;
92 elts[i] = el;
93 list_add_tail(&el->list, &head);
94 }
95
96 list_sort(NULL, &head, cmp);
97
98 err = -EINVAL;
99 for (cur = head.next; cur->next != &head; cur = cur->next) {
100 struct debug_el *el1;
101 int cmp_result;
102
103 if (cur->next->prev != cur) {
104 pr_err("error: list is corrupted\n");
105 goto exit;
106 }
107
108 cmp_result = cmp(NULL, cur, cur->next);
109 if (cmp_result > 0) {
110 pr_err("error: list is not sorted\n");
111 goto exit;
112 }
113
114 el = container_of(cur, struct debug_el, list);
115 el1 = container_of(cur->next, struct debug_el, list);
116 if (cmp_result == 0 && el->serial >= el1->serial) {
117 pr_err("error: order of equivalent elements not "
118 "preserved\n");
119 goto exit;
120 }
121
122 if (check(el, el1)) {
123 pr_err("error: element check failed\n");
124 goto exit;
125 }
126 count++;
127 }
128 if (head.prev != cur) {
129 pr_err("error: list is corrupted\n");
130 goto exit;
131 }
132
133
134 if (count != TEST_LIST_LEN) {
135 pr_err("error: bad list length %d", count);
136 goto exit;
137 }
138
139 err = 0;
140exit:
141 for (i = 0; i < TEST_LIST_LEN; i++)
142 kfree(elts[i]);
143 kfree(elts);
144 return err;
145}
146module_init(list_sort_test);
147MODULE_LICENSE("GPL");
148