Rev 6934 | Show entire file | Regard whitespace | Details | Blame | Last modification | View Log | RSS feed
| Rev 6934 | Rev 7143 | ||
|---|---|---|---|
| Line 143... | Line 143... | ||
| 143 | 143 | ||
| Line 144... | Line 144... | ||
| 144 | merge_and_restore_back_links(priv, cmp, head, part[max_lev], list); |
144 | merge_and_restore_back_links(priv, cmp, head, part[max_lev], list); |
| 145 | } |
145 | } |
| 146 | EXPORT_SYMBOL(list_sort); |
146 | EXPORT_SYMBOL(list_sort); |
| - | 147 | ||
| - | 148 | #ifdef CONFIG_TEST_LIST_SORT |
|
| - | 149 | ||
| - | 150 | #include |
|
| - | 151 | #include |
|
| - | 152 | ||
| - | 153 | /* |
|
| - | 154 | * The pattern of set bits in the list length determines which cases |
|
| - | 155 | * are hit in list_sort(). |
|
| - | 156 | */ |
|
| - | 157 | #define TEST_LIST_LEN (512+128+2) /* not including head */ |
|
| - | 158 | ||
| - | 159 | #define TEST_POISON1 0xDEADBEEF |
|
| - | 160 | #define TEST_POISON2 0xA324354C |
|
| - | 161 | ||
| - | 162 | struct debug_el { |
|
| - | 163 | unsigned int poison1; |
|
| - | 164 | struct list_head list; |
|
| - | 165 | unsigned int poison2; |
|
| - | 166 | int value; |
|
| - | 167 | unsigned serial; |
|
| - | 168 | }; |
|
| - | 169 | ||
| - | 170 | /* Array, containing pointers to all elements in the test list */ |
|
| - | 171 | static struct debug_el **elts __initdata; |
|
| - | 172 | ||
| - | 173 | static int __init check(struct debug_el *ela, struct debug_el *elb) |
|
| - | 174 | { |
|
| - | 175 | if (ela->serial >= TEST_LIST_LEN) { |
|
| - | 176 | pr_err("error: incorrect serial %d\n", ela->serial); |
|
| - | 177 | return -EINVAL; |
|
| - | 178 | } |
|
| - | 179 | if (elb->serial >= TEST_LIST_LEN) { |
|
| - | 180 | pr_err("error: incorrect serial %d\n", elb->serial); |
|
| - | 181 | return -EINVAL; |
|
| - | 182 | } |
|
| - | 183 | if (elts[ela->serial] != ela || elts[elb->serial] != elb) { |
|
| - | 184 | pr_err("error: phantom element\n"); |
|
| - | 185 | return -EINVAL; |
|
| - | 186 | } |
|
| - | 187 | if (ela->poison1 != TEST_POISON1 || ela->poison2 != TEST_POISON2) { |
|
| - | 188 | pr_err("error: bad poison: %#x/%#x\n", |
|
| - | 189 | ela->poison1, ela->poison2); |
|
| - | 190 | return -EINVAL; |
|
| - | 191 | } |
|
| - | 192 | if (elb->poison1 != TEST_POISON1 || elb->poison2 != TEST_POISON2) { |
|
| - | 193 | pr_err("error: bad poison: %#x/%#x\n", |
|
| - | 194 | elb->poison1, elb->poison2); |
|
| - | 195 | return -EINVAL; |
|
| - | 196 | } |
|
| - | 197 | return 0; |
|
| - | 198 | } |
|
| - | 199 | ||
| - | 200 | static int __init cmp(void *priv, struct list_head *a, struct list_head *b) |
|
| - | 201 | { |
|
| - | 202 | struct debug_el *ela, *elb; |
|
| - | 203 | ||
| - | 204 | ela = container_of(a, struct debug_el, list); |
|
| - | 205 | elb = container_of(b, struct debug_el, list); |
|
| - | 206 | ||
| - | 207 | check(ela, elb); |
|
| - | 208 | return ela->value - elb->value; |
|
| - | 209 | } |
|
| - | 210 | ||
| - | 211 | static int __init list_sort_test(void) |
|
| - | 212 | { |
|
| - | 213 | int i, count = 1, err = -ENOMEM; |
|
| - | 214 | struct debug_el *el; |
|
| - | 215 | struct list_head *cur; |
|
| - | 216 | LIST_HEAD(head); |
|
| - | 217 | ||
| - | 218 | pr_debug("start testing list_sort()\n"); |
|
| - | 219 | ||
| - | 220 | elts = kcalloc(TEST_LIST_LEN, sizeof(*elts), GFP_KERNEL); |
|
| - | 221 | if (!elts) { |
|
| - | 222 | pr_err("error: cannot allocate memory\n"); |
|
| - | 223 | return err; |
|
| - | 224 | } |
|
| - | 225 | ||
| - | 226 | for (i = 0; i < TEST_LIST_LEN; i++) { |
|
| - | 227 | el = kmalloc(sizeof(*el), GFP_KERNEL); |
|
| - | 228 | if (!el) { |
|
| - | 229 | pr_err("error: cannot allocate memory\n"); |
|
| - | 230 | goto exit; |
|
| - | 231 | } |
|
| - | 232 | /* force some equivalencies */ |
|
| - | 233 | el->value = prandom_u32() % (TEST_LIST_LEN / 3); |
|
| - | 234 | el->serial = i; |
|
| - | 235 | el->poison1 = TEST_POISON1; |
|
| - | 236 | el->poison2 = TEST_POISON2; |
|
| - | 237 | elts[i] = el; |
|
| - | 238 | list_add_tail(&el->list, &head); |
|
| - | 239 | } |
|
| - | 240 | ||
| - | 241 | list_sort(NULL, &head, cmp); |
|
| - | 242 | ||
| - | 243 | err = -EINVAL; |
|
| - | 244 | for (cur = head.next; cur->next != &head; cur = cur->next) { |
|
| - | 245 | struct debug_el *el1; |
|
| - | 246 | int cmp_result; |
|
| - | 247 | ||
| - | 248 | if (cur->next->prev != cur) { |
|
| - | 249 | pr_err("error: list is corrupted\n"); |
|
| - | 250 | goto exit; |
|
| - | 251 | } |
|
| - | 252 | ||
| - | 253 | cmp_result = cmp(NULL, cur, cur->next); |
|
| - | 254 | if (cmp_result > 0) { |
|
| - | 255 | pr_err("error: list is not sorted\n"); |
|
| - | 256 | goto exit; |
|
| - | 257 | } |
|
| - | 258 | ||
| - | 259 | el = container_of(cur, struct debug_el, list); |
|
| - | 260 | el1 = container_of(cur->next, struct debug_el, list); |
|
| - | 261 | if (cmp_result == 0 && el->serial >= el1->serial) { |
|
| - | 262 | pr_err("error: order of equivalent elements not " |
|
| - | 263 | "preserved\n"); |
|
| - | 264 | goto exit; |
|
| - | 265 | } |
|
| - | 266 | ||
| - | 267 | if (check(el, el1)) { |
|
| - | 268 | pr_err("error: element check failed\n"); |
|
| - | 269 | goto exit; |
|
| - | 270 | } |
|
| - | 271 | count++; |
|
| - | 272 | } |
|
| - | 273 | if (head.prev != cur) { |
|
| - | 274 | pr_err("error: list is corrupted\n"); |
|
| - | 275 | goto exit; |
|
| - | 276 | } |
|
| - | 277 | ||
| - | 278 | ||
| - | 279 | if (count != TEST_LIST_LEN) { |
|
| - | 280 | pr_err("error: bad list length %d", count); |
|
| - | 281 | goto exit; |
|
| - | 282 | } |
|
| - | 283 | ||
| - | 284 | err = 0; |
|
| - | 285 | exit: |
|
| - | 286 | for (i = 0; i < TEST_LIST_LEN; i++) |
|
| - | 287 | kfree(elts[i]); |
|
| - | 288 | kfree(elts); |
|
| - | 289 | return err; |
|
| - | 290 | } |
|
| - | 291 | late_initcall(list_sort_test); |
|
| - | 292 | #endif /* CONFIG_TEST_LIST_SORT */ |
|