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