]>
Commit | Line | Data |
---|---|---|
e327fd7c GU |
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 | ||
20 | struct 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 */ | |
29 | static struct debug_el **elts __initdata; | |
30 | ||
31 | static 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 | ||
58 | static 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 | ||
69 | static 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; | |
143 | exit: | |
144 | for (i = 0; i < TEST_LIST_LEN; i++) | |
145 | kfree(elts[i]); | |
146 | kfree(elts); | |
147 | return err; | |
148 | } | |
149 | module_init(list_sort_test); | |
150 | MODULE_LICENSE("GPL"); |