1 // SPDX-License-Identifier: GPL-2.0-only 2 #include <kunit/test.h> 3 4 #include <linux/kernel.h> 5 #include <linux/list_sort.h> 6 #include <linux/list.h> 7 #include <linux/module.h> 8 #include <linux/printk.h> 9 #include <linux/slab.h> 10 #include <linux/random.h> 11 12 /* 13 * The pattern of set bits in the list length determines which cases 14 * are hit in list_sort(). 15 */ 16 #define TEST_LIST_LEN (512+128+2) /* not including head */ 17 18 #define TEST_POISON1 0xDEADBEEF 19 #define TEST_POISON2 0xA324354C 20 21 struct debug_el { 22 unsigned int poison1; 23 struct list_head list; 24 unsigned int poison2; 25 int value; 26 unsigned int serial; 27 }; 28 29 static void check(struct kunit *test, struct debug_el *ela, struct debug_el *elb) 30 { 31 struct debug_el **elts = test->priv; 32 33 KUNIT_EXPECT_LT_MSG(test, ela->serial, (unsigned int)TEST_LIST_LEN, "incorrect serial"); 34 KUNIT_EXPECT_LT_MSG(test, elb->serial, (unsigned int)TEST_LIST_LEN, "incorrect serial"); 35 36 KUNIT_EXPECT_PTR_EQ_MSG(test, elts[ela->serial], ela, "phantom element"); 37 KUNIT_EXPECT_PTR_EQ_MSG(test, elts[elb->serial], elb, "phantom element"); 38 39 KUNIT_EXPECT_EQ_MSG(test, ela->poison1, TEST_POISON1, "bad poison"); 40 KUNIT_EXPECT_EQ_MSG(test, ela->poison2, TEST_POISON2, "bad poison"); 41 42 KUNIT_EXPECT_EQ_MSG(test, elb->poison1, TEST_POISON1, "bad poison"); 43 KUNIT_EXPECT_EQ_MSG(test, elb->poison2, TEST_POISON2, "bad poison"); 44 } 45 46 /* `priv` is the test pointer so check() can fail the test if the list is invalid. */ 47 static int cmp(void *priv, const struct list_head *a, const struct list_head *b) 48 { 49 struct debug_el *ela, *elb; 50 51 ela = container_of(a, struct debug_el, list); 52 elb = container_of(b, struct debug_el, list); 53 54 check(priv, ela, elb); 55 return ela->value - elb->value; 56 } 57 58 static void list_sort_test(struct kunit *test) 59 { 60 int i, count = 1; 61 struct debug_el *el, **elts; 62 struct list_head *cur; 63 LIST_HEAD(head); 64 65 elts = kunit_kcalloc(test, TEST_LIST_LEN, sizeof(*elts), GFP_KERNEL); 66 KUNIT_ASSERT_NOT_ERR_OR_NULL(test, elts); 67 test->priv = elts; 68 69 for (i = 0; i < TEST_LIST_LEN; i++) { 70 el = kunit_kmalloc(test, sizeof(*el), GFP_KERNEL); 71 KUNIT_ASSERT_NOT_ERR_OR_NULL(test, el); 72 73 /* force some equivalencies */ 74 el->value = get_random_u32_below(TEST_LIST_LEN / 3); 75 el->serial = i; 76 el->poison1 = TEST_POISON1; 77 el->poison2 = TEST_POISON2; 78 elts[i] = el; 79 list_add_tail(&el->list, &head); 80 } 81 82 list_sort(test, &head, cmp); 83 84 for (cur = head.next; cur->next != &head; cur = cur->next) { 85 struct debug_el *el1; 86 int cmp_result; 87 88 KUNIT_ASSERT_PTR_EQ_MSG(test, cur->next->prev, cur, 89 "list is corrupted"); 90 91 cmp_result = cmp(test, cur, cur->next); 92 KUNIT_ASSERT_LE_MSG(test, cmp_result, 0, "list is not sorted"); 93 94 el = container_of(cur, struct debug_el, list); 95 el1 = container_of(cur->next, struct debug_el, list); 96 if (cmp_result == 0) { 97 KUNIT_ASSERT_LE_MSG(test, el->serial, el1->serial, 98 "order of equivalent elements not preserved"); 99 } 100 101 check(test, el, el1); 102 count++; 103 } 104 KUNIT_EXPECT_PTR_EQ_MSG(test, head.prev, cur, "list is corrupted"); 105 106 KUNIT_EXPECT_EQ_MSG(test, count, TEST_LIST_LEN, 107 "list length changed after sorting!"); 108 } 109 110 static struct kunit_case list_sort_cases[] = { 111 KUNIT_CASE(list_sort_test), 112 {} 113 }; 114 115 static struct kunit_suite list_sort_suite = { 116 .name = "list_sort", 117 .test_cases = list_sort_cases, 118 }; 119 120 kunit_test_suites(&list_sort_suite); 121 122 MODULE_LICENSE("GPL"); 123