Rev 6934 | Go to most recent revision | 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 */>>>=>=> |