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 return err; 81 82 for (i = 0; i < TEST_LIST_LEN; i++) { 83 el = kmalloc(sizeof(*el), GFP_KERNEL); 84 if (!el) 85 goto exit; 86 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"); 148