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
21struct debug_el {
22	unsigned int poison1;
23	struct list_head list;
24	unsigned int poison2;
25	int value;
26	unsigned int serial;
27};
28
29static 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. */
47static 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
58static 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
110static struct kunit_case list_sort_cases[] = {
111	KUNIT_CASE(list_sort_test),
112	{}
113};
114
115static struct kunit_suite list_sort_suite = {
116	.name = "list_sort",
117	.test_cases = list_sort_cases,
118};
119
120kunit_test_suites(&list_sort_suite);
121
122MODULE_LICENSE("GPL");
123