blob: 3fe401067e20ba81c762fb00ae00730de6b9502f
1 | |
2 | #define pr_fmt(fmt) "list_sort_test: " fmt |
3 | |
4 | #include <linux/kernel.h> |
5 | #include <linux/bug.h> |
6 | #include <linux/compiler.h> |
7 | #include <linux/export.h> |
8 | #include <linux/string.h> |
9 | #include <linux/list_sort.h> |
10 | #include <linux/list.h> |
11 | |
12 | #define MAX_LIST_LENGTH_BITS 20 |
13 | |
14 | /* |
15 | * Returns a list organized in an intermediate format suited |
16 | * to chaining of merge() calls: null-terminated, no reserved or |
17 | * sentinel head node, "prev" links not maintained. |
18 | */ |
19 | static struct list_head *merge(void *priv, |
20 | int (*cmp)(void *priv, struct list_head *a, |
21 | struct list_head *b), |
22 | struct list_head *a, struct list_head *b) |
23 | { |
24 | struct list_head head, *tail = &head; |
25 | |
26 | while (a && b) { |
27 | /* if equal, take 'a' -- important for sort stability */ |
28 | if ((*cmp)(priv, a, b) <= 0) { |
29 | tail->next = a; |
30 | a = a->next; |
31 | } else { |
32 | tail->next = b; |
33 | b = b->next; |
34 | } |
35 | tail = tail->next; |
36 | } |
37 | tail->next = a?:b; |
38 | return head.next; |
39 | } |
40 | |
41 | /* |
42 | * Combine final list merge with restoration of standard doubly-linked |
43 | * list structure. This approach duplicates code from merge(), but |
44 | * runs faster than the tidier alternatives of either a separate final |
45 | * prev-link restoration pass, or maintaining the prev links |
46 | * throughout. |
47 | */ |
48 | static void merge_and_restore_back_links(void *priv, |
49 | int (*cmp)(void *priv, struct list_head *a, |
50 | struct list_head *b), |
51 | struct list_head *head, |
52 | struct list_head *a, struct list_head *b) |
53 | { |
54 | struct list_head *tail = head; |
55 | u8 count = 0; |
56 | |
57 | while (a && b) { |
58 | /* if equal, take 'a' -- important for sort stability */ |
59 | if ((*cmp)(priv, a, b) <= 0) { |
60 | tail->next = a; |
61 | a->prev = tail; |
62 | a = a->next; |
63 | } else { |
64 | tail->next = b; |
65 | b->prev = tail; |
66 | b = b->next; |
67 | } |
68 | tail = tail->next; |
69 | } |
70 | tail->next = a ? : b; |
71 | |
72 | do { |
73 | /* |
74 | * In worst cases this loop may run many iterations. |
75 | * Continue callbacks to the client even though no |
76 | * element comparison is needed, so the client's cmp() |
77 | * routine can invoke cond_resched() periodically. |
78 | */ |
79 | if (unlikely(!(++count))) |
80 | (*cmp)(priv, tail->next, tail->next); |
81 | |
82 | tail->next->prev = tail; |
83 | tail = tail->next; |
84 | } while (tail->next); |
85 | |
86 | tail->next = head; |
87 | head->prev = tail; |
88 | } |
89 | |
90 | /** |
91 | * list_sort - sort a list |
92 | * @priv: private data, opaque to list_sort(), passed to @cmp |
93 | * @head: the list to sort |
94 | * @cmp: the elements comparison function |
95 | * |
96 | * This function implements "merge sort", which has O(nlog(n)) |
97 | * complexity. |
98 | * |
99 | * The comparison function @cmp must return a negative value if @a |
100 | * should sort before @b, and a positive value if @a should sort after |
101 | * @b. If @a and @b are equivalent, and their original relative |
102 | * ordering is to be preserved, @cmp must return 0. |
103 | */ |
104 | void list_sort(void *priv, struct list_head *head, |
105 | int (*cmp)(void *priv, struct list_head *a, |
106 | struct list_head *b)) |
107 | { |
108 | struct list_head *part[MAX_LIST_LENGTH_BITS+1]; /* sorted partial lists |
109 | -- last slot is a sentinel */ |
110 | int lev; /* index into part[] */ |
111 | int max_lev = 0; |
112 | struct list_head *list; |
113 | |
114 | if (list_empty(head)) |
115 | return; |
116 | |
117 | memset(part, 0, sizeof(part)); |
118 | |
119 | head->prev->next = NULL; |
120 | list = head->next; |
121 | |
122 | while (list) { |
123 | struct list_head *cur = list; |
124 | list = list->next; |
125 | cur->next = NULL; |
126 | |
127 | for (lev = 0; part[lev]; lev++) { |
128 | cur = merge(priv, cmp, part[lev], cur); |
129 | part[lev] = NULL; |
130 | } |
131 | if (lev > max_lev) { |
132 | if (unlikely(lev >= ARRAY_SIZE(part)-1)) { |
133 | printk_once(KERN_DEBUG "list too long for efficiency\n"); |
134 | lev--; |
135 | } |
136 | max_lev = lev; |
137 | } |
138 | part[lev] = cur; |
139 | } |
140 | |
141 | for (lev = 0; lev < max_lev; lev++) |
142 | if (part[lev]) |
143 | list = merge(priv, cmp, part[lev], list); |
144 | |
145 | merge_and_restore_back_links(priv, cmp, head, part[max_lev], list); |
146 | } |
147 | EXPORT_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 | |
163 | struct 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 */ |
172 | static struct debug_el **elts __initdata; |
173 | |
174 | static 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 | |
201 | static 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 | |
212 | static 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; |
286 | exit: |
287 | for (i = 0; i < TEST_LIST_LEN; i++) |
288 | kfree(elts[i]); |
289 | kfree(elts); |
290 | return err; |
291 | } |
292 | late_initcall(list_sort_test); |
293 | #endif /* CONFIG_TEST_LIST_SORT */ |
294 |