Geert Uytterhoeven | e327fd7 | 2017-05-08 15:55:26 -0700 | [diff] [blame] | 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); |
Markus Elfring | dc2bf000 | 2017-11-17 15:28:00 -0800 | [diff] [blame] | 79 | if (!elts) |
Geert Uytterhoeven | e327fd7 | 2017-05-08 15:55:26 -0700 | [diff] [blame] | 80 | return err; |
Geert Uytterhoeven | e327fd7 | 2017-05-08 15:55:26 -0700 | [diff] [blame] | 81 | |
| 82 | for (i = 0; i < TEST_LIST_LEN; i++) { |
| 83 | el = kmalloc(sizeof(*el), GFP_KERNEL); |
Markus Elfring | dc2bf000 | 2017-11-17 15:28:00 -0800 | [diff] [blame] | 84 | if (!el) |
Geert Uytterhoeven | e327fd7 | 2017-05-08 15:55:26 -0700 | [diff] [blame] | 85 | goto exit; |
Markus Elfring | dc2bf000 | 2017-11-17 15:28:00 -0800 | [diff] [blame] | 86 | |
Geert Uytterhoeven | e327fd7 | 2017-05-08 15:55:26 -0700 | [diff] [blame] | 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; |
| 140 | exit: |
| 141 | for (i = 0; i < TEST_LIST_LEN; i++) |
| 142 | kfree(elts[i]); |
| 143 | kfree(elts); |
| 144 | return err; |
| 145 | } |
| 146 | module_init(list_sort_test); |
| 147 | MODULE_LICENSE("GPL"); |