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