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