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 pr_err("error: cannot allocate memory\n"); 81 return err; 82 } 83 84 for (i = 0; i < TEST_LIST_LEN; i++) { 85 el = kmalloc(sizeof(*el), GFP_KERNEL); 86 if (!el) { 87 pr_err("error: cannot allocate memory\n"); 88 goto exit; 89 } 90 /* force some equivalencies */ 91 el->value = prandom_u32() % (TEST_LIST_LEN / 3); 92 el->serial = i; 93 el->poison1 = TEST_POISON1; 94 el->poison2 = TEST_POISON2; 95 elts[i] = el; 96 list_add_tail(&el->list, &head); 97 } 98 99 list_sort(NULL, &head, cmp); 100 101 err = -EINVAL; 102 for (cur = head.next; cur->next != &head; cur = cur->next) { 103 struct debug_el *el1; 104 int cmp_result; 105 106 if (cur->next->prev != cur) { 107 pr_err("error: list is corrupted\n"); 108 goto exit; 109 } 110 111 cmp_result = cmp(NULL, cur, cur->next); 112 if (cmp_result > 0) { 113 pr_err("error: list is not sorted\n"); 114 goto exit; 115 } 116 117 el = container_of(cur, struct debug_el, list); 118 el1 = container_of(cur->next, struct debug_el, list); 119 if (cmp_result == 0 && el->serial >= el1->serial) { 120 pr_err("error: order of equivalent elements not " 121 "preserved\n"); 122 goto exit; 123 } 124 125 if (check(el, el1)) { 126 pr_err("error: element check failed\n"); 127 goto exit; 128 } 129 count++; 130 } 131 if (head.prev != cur) { 132 pr_err("error: list is corrupted\n"); 133 goto exit; 134 } 135 136 137 if (count != TEST_LIST_LEN) { 138 pr_err("error: bad list length %d", count); 139 goto exit; 140 } 141 142 err = 0; 143 exit: 144 for (i = 0; i < TEST_LIST_LEN; i++) 145 kfree(elts[i]); 146 kfree(elts); 147 return err; 148 } 149 module_init(list_sort_test); 150 MODULE_LICENSE("GPL"); 151