[GitHub/moto-9609/android_kernel_motorola_exynos9610.git] / lib / test_list_sort.c

#define pr_fmt(fmt) "list_sort_test: " fmt

#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;
	unsigned serial;
};

/* Array, containing pointers to all elements in the test list */
static struct debug_el **elts __initdata;

static int __init check(struct debug_el *ela, struct debug_el *elb)
{
	if (ela->serial >= TEST_LIST_LEN) {
		pr_err("error: incorrect serial %d\n", ela->serial);
		return -EINVAL;
	}
	if (elb->serial >= TEST_LIST_LEN) {
		pr_err("error: incorrect serial %d\n", elb->serial);
		return -EINVAL;
	}
	if (elts[ela->serial] != ela || elts[elb->serial] != elb) {
		pr_err("error: phantom element\n");
		return -EINVAL;
	}
	if (ela->poison1 != TEST_POISON1 || ela->poison2 != TEST_POISON2) {
		pr_err("error: bad poison: %#x/%#x\n",
			ela->poison1, ela->poison2);
		return -EINVAL;
	}
	if (elb->poison1 != TEST_POISON1 || elb->poison2 != TEST_POISON2) {
		pr_err("error: bad poison: %#x/%#x\n",
			elb->poison1, elb->poison2);
		return -EINVAL;
	}
	return 0;
}

static int __init cmp(void *priv, struct list_head *a, struct list_head *b)
{
	struct debug_el *ela, *elb;

	ela = container_of(a, struct debug_el, list);
	elb = container_of(b, struct debug_el, list);

	check(ela, elb);
	return ela->value - elb->value;
}

static int __init list_sort_test(void)
{
	int i, count = 1, err = -ENOMEM;
	struct debug_el *el;
	struct list_head *cur;
	LIST_HEAD(head);

	pr_debug("start testing list_sort()\n");

	elts = kcalloc(TEST_LIST_LEN, sizeof(*elts), GFP_KERNEL);
	if (!elts) {
		pr_err("error: cannot allocate memory\n");
		return err;
	}

	for (i = 0; i < TEST_LIST_LEN; i++) {
		el = kmalloc(sizeof(*el), GFP_KERNEL);
		if (!el) {
			pr_err("error: cannot allocate memory\n");
			goto exit;
		}
		 /* 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);
	}

	list_sort(NULL, &head, cmp);

	err = -EINVAL;
	for (cur = head.next; cur->next != &head; cur = cur->next) {
		struct debug_el *el1;
		int cmp_result;

		if (cur->next->prev != cur) {
			pr_err("error: list is corrupted\n");
			goto exit;
		}

		cmp_result = cmp(NULL, cur, cur->next);
		if (cmp_result > 0) {
			pr_err("error: list is not sorted\n");
			goto exit;
		}

		el = container_of(cur, struct debug_el, list);
		el1 = container_of(cur->next, struct debug_el, list);
		if (cmp_result == 0 && el->serial >= el1->serial) {
			pr_err("error: order of equivalent elements not "
				"preserved\n");
			goto exit;
		}

		if (check(el, el1)) {
			pr_err("error: element check failed\n");
			goto exit;
		}
		count++;
	}
	if (head.prev != cur) {
		pr_err("error: list is corrupted\n");
		goto exit;
	}


	if (count != TEST_LIST_LEN) {
		pr_err("error: bad list length %d", count);
		goto exit;
	}

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