Loading...
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 | // SPDX-License-Identifier: GPL-2.0-only #define pr_fmt(fmt) "list_sort_test: " fmt #include <linux/kernel.h> #include <linux/list_sort.h> #include <linux/list.h> #include <linux/module.h> #include <linux/printk.h> #include <linux/slab.h> #include <linux/random.h> /* * The pattern of set bits in the list length determines which cases * are hit in list_sort(). */ #define TEST_LIST_LEN (512+128+2) /* not including head */ #define TEST_POISON1 0xDEADBEEF #define TEST_POISON2 0xA324354C struct debug_el { unsigned int poison1; struct list_head list; unsigned int poison2; int value; unsigned serial; }; /* Array, containing pointers to all elements in the test list */ static struct debug_el **elts __initdata; static int __init check(struct debug_el *ela, struct debug_el *elb) { if (ela->serial >= TEST_LIST_LEN) { pr_err("error: incorrect serial %d\n", ela->serial); return -EINVAL; } if (elb->serial >= TEST_LIST_LEN) { pr_err("error: incorrect serial %d\n", elb->serial); return -EINVAL; } if (elts[ela->serial] != ela || elts[elb->serial] != elb) { pr_err("error: phantom element\n"); return -EINVAL; } if (ela->poison1 != TEST_POISON1 || ela->poison2 != TEST_POISON2) { pr_err("error: bad poison: %#x/%#x\n", ela->poison1, ela->poison2); return -EINVAL; } if (elb->poison1 != TEST_POISON1 || elb->poison2 != TEST_POISON2) { pr_err("error: bad poison: %#x/%#x\n", elb->poison1, elb->poison2); return -EINVAL; } return 0; } static int __init cmp(void *priv, struct list_head *a, struct list_head *b) { struct debug_el *ela, *elb; ela = container_of(a, struct debug_el, list); elb = container_of(b, struct debug_el, list); check(ela, elb); return ela->value - elb->value; } static int __init list_sort_test(void) { int i, count = 1, err = -ENOMEM; struct debug_el *el; struct list_head *cur; LIST_HEAD(head); pr_debug("start testing list_sort()\n"); elts = kcalloc(TEST_LIST_LEN, sizeof(*elts), GFP_KERNEL); if (!elts) return err; for (i = 0; i < TEST_LIST_LEN; i++) { el = kmalloc(sizeof(*el), GFP_KERNEL); if (!el) goto exit; /* force some equivalencies */ el->value = prandom_u32() % (TEST_LIST_LEN / 3); el->serial = i; el->poison1 = TEST_POISON1; el->poison2 = TEST_POISON2; elts[i] = el; list_add_tail(&el->list, &head); } list_sort(NULL, &head, cmp); err = -EINVAL; for (cur = head.next; cur->next != &head; cur = cur->next) { struct debug_el *el1; int cmp_result; if (cur->next->prev != cur) { pr_err("error: list is corrupted\n"); goto exit; } cmp_result = cmp(NULL, cur, cur->next); if (cmp_result > 0) { pr_err("error: list is not sorted\n"); goto exit; } el = container_of(cur, struct debug_el, list); el1 = container_of(cur->next, struct debug_el, list); if (cmp_result == 0 && el->serial >= el1->serial) { pr_err("error: order of equivalent elements not " "preserved\n"); goto exit; } if (check(el, el1)) { pr_err("error: element check failed\n"); goto exit; } count++; } if (head.prev != cur) { pr_err("error: list is corrupted\n"); goto exit; } if (count != TEST_LIST_LEN) { pr_err("error: bad list length %d", count); goto exit; } err = 0; exit: for (i = 0; i < TEST_LIST_LEN; i++) kfree(elts[i]); kfree(elts); return err; } module_init(list_sort_test); MODULE_LICENSE("GPL"); |