[linux.git] / lib / test_parman.c

/*
 * lib/test_parman.c - Test module for parman
 * Copyright (c) 2017 Mellanox Technologies. All rights reserved.
 * Copyright (c) 2017 Jiri Pirko <[email protected]>
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the names of the copyright holders nor the names of its
 *    contributors may be used to endorse or promote products derived from
 *    this software without specific prior written permission.
 *
 * Alternatively, this software may be distributed under the terms of the
 * GNU General Public License ("GPL") version 2 as published by the Free
 * Software Foundation.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt

#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/slab.h>
#include <linux/bitops.h>
#include <linux/err.h>
#include <linux/random.h>
#include <linux/parman.h>

#define TEST_PARMAN_PRIO_SHIFT 7 /* defines number of prios for testing */
#define TEST_PARMAN_PRIO_COUNT BIT(TEST_PARMAN_PRIO_SHIFT)
#define TEST_PARMAN_PRIO_MASK (TEST_PARMAN_PRIO_COUNT - 1)

#define TEST_PARMAN_ITEM_SHIFT 13 /* defines a total number
				   * of items for testing
				   */
#define TEST_PARMAN_ITEM_COUNT BIT(TEST_PARMAN_ITEM_SHIFT)
#define TEST_PARMAN_ITEM_MASK (TEST_PARMAN_ITEM_COUNT - 1)

#define TEST_PARMAN_BASE_SHIFT 8
#define TEST_PARMAN_BASE_COUNT BIT(TEST_PARMAN_BASE_SHIFT)
#define TEST_PARMAN_RESIZE_STEP_SHIFT 7
#define TEST_PARMAN_RESIZE_STEP_COUNT BIT(TEST_PARMAN_RESIZE_STEP_SHIFT)

#define TEST_PARMAN_BULK_MAX_SHIFT (2 + TEST_PARMAN_RESIZE_STEP_SHIFT)
#define TEST_PARMAN_BULK_MAX_COUNT BIT(TEST_PARMAN_BULK_MAX_SHIFT)
#define TEST_PARMAN_BULK_MAX_MASK (TEST_PARMAN_BULK_MAX_COUNT - 1)

#define TEST_PARMAN_RUN_BUDGET (TEST_PARMAN_ITEM_COUNT * 256)

struct test_parman_prio {
	struct parman_prio parman_prio;
	unsigned long priority;
};

struct test_parman_item {
	struct parman_item parman_item;
	struct test_parman_prio *prio;
	bool used;
};

struct test_parman {
	struct parman *parman;
	struct test_parman_item **prio_array;
	unsigned long prio_array_limit;
	struct test_parman_prio prios[TEST_PARMAN_PRIO_COUNT];
	struct test_parman_item items[TEST_PARMAN_ITEM_COUNT];
	struct rnd_state rnd;
	unsigned long run_budget;
	unsigned long bulk_budget;
	bool bulk_noop;
	unsigned int used_items;
};

#define ITEM_PTRS_SIZE(count) (sizeof(struct test_parman_item *) * (count))

static int test_parman_resize(void *priv, unsigned long new_count)
{
	struct test_parman *test_parman = priv;
	struct test_parman_item **prio_array;
	unsigned long old_count;

	prio_array = krealloc(test_parman->prio_array,
			      ITEM_PTRS_SIZE(new_count), GFP_KERNEL);
	if (new_count == 0)
		return 0;
	if (!prio_array)
		return -ENOMEM;
	old_count = test_parman->prio_array_limit;
	if (new_count > old_count)
		memset(&prio_array[old_count], 0,
		       ITEM_PTRS_SIZE(new_count - old_count));
	test_parman->prio_array = prio_array;
	test_parman->prio_array_limit = new_count;
	return 0;
}

static void test_parman_move(void *priv, unsigned long from_index,
			     unsigned long to_index, unsigned long count)
{
	struct test_parman *test_parman = priv;
	struct test_parman_item **prio_array = test_parman->prio_array;

	memmove(&prio_array[to_index], &prio_array[from_index],
		ITEM_PTRS_SIZE(count));
	memset(&prio_array[from_index], 0, ITEM_PTRS_SIZE(count));
}

static const struct parman_ops test_parman_lsort_ops = {
	.base_count	= TEST_PARMAN_BASE_COUNT,
	.resize_step	= TEST_PARMAN_RESIZE_STEP_COUNT,
	.resize		= test_parman_resize,
	.move		= test_parman_move,
	.algo		= PARMAN_ALGO_TYPE_LSORT,
};

static void test_parman_rnd_init(struct test_parman *test_parman)
{
	prandom_seed_state(&test_parman->rnd, 3141592653589793238ULL);
}

static u32 test_parman_rnd_get(struct test_parman *test_parman)
{
	return prandom_u32_state(&test_parman->rnd);
}

static unsigned long test_parman_priority_gen(struct test_parman *test_parman)
{
	unsigned long priority;
	int i;

again:
	priority = test_parman_rnd_get(test_parman);
	if (priority == 0)
		goto again;

	for (i = 0; i < TEST_PARMAN_PRIO_COUNT; i++) {
		struct test_parman_prio *prio = &test_parman->prios[i];

		if (prio->priority == 0)
			break;
		if (prio->priority == priority)
			goto again;
	}
	return priority;
}

static void test_parman_prios_init(struct test_parman *test_parman)
{
	int i;

	for (i = 0; i < TEST_PARMAN_PRIO_COUNT; i++) {
		struct test_parman_prio *prio = &test_parman->prios[i];

		/* Assign random uniqueue priority to each prio structure */
		prio->priority = test_parman_priority_gen(test_parman);
		parman_prio_init(test_parman->parman, &prio->parman_prio,
				 prio->priority);
	}
}

static void test_parman_prios_fini(struct test_parman *test_parman)
{
	int i;

	for (i = 0; i < TEST_PARMAN_PRIO_COUNT; i++) {
		struct test_parman_prio *prio = &test_parman->prios[i];

		parman_prio_fini(&prio->parman_prio);
	}
}

static void test_parman_items_init(struct test_parman *test_parman)
{
	int i;

	for (i = 0; i < TEST_PARMAN_ITEM_COUNT; i++) {
		struct test_parman_item *item = &test_parman->items[i];
		unsigned int prio_index = test_parman_rnd_get(test_parman) &
					  TEST_PARMAN_PRIO_MASK;

		/* Assign random prio to each item structure */
		item->prio = &test_parman->prios[prio_index];
	}
}

static void test_parman_items_fini(struct test_parman *test_parman)
{
	int i;

	for (i = 0; i < TEST_PARMAN_ITEM_COUNT; i++) {
		struct test_parman_item *item = &test_parman->items[i];

		if (!item->used)
			continue;
		parman_item_remove(test_parman->parman,
				   &item->prio->parman_prio,
				   &item->parman_item);
	}
}

static struct test_parman *test_parman_create(const struct parman_ops *ops)
{
	struct test_parman *test_parman;
	int err;

	test_parman = kzalloc(sizeof(*test_parman), GFP_KERNEL);
	if (!test_parman)
		return ERR_PTR(-ENOMEM);
	err = test_parman_resize(test_parman, TEST_PARMAN_BASE_COUNT);
	if (err)
		goto err_resize;
	test_parman->parman = parman_create(ops, test_parman);
	if (!test_parman->parman) {
		err = -ENOMEM;
		goto err_parman_create;
	}
	test_parman_rnd_init(test_parman);
	test_parman_prios_init(test_parman);
	test_parman_items_init(test_parman);
	test_parman->run_budget = TEST_PARMAN_RUN_BUDGET;
	return test_parman;

err_parman_create:
	test_parman_resize(test_parman, 0);
err_resize:
	kfree(test_parman);
	return ERR_PTR(err);
}

static void test_parman_destroy(struct test_parman *test_parman)
{
	test_parman_items_fini(test_parman);
	test_parman_prios_fini(test_parman);
	parman_destroy(test_parman->parman);
	test_parman_resize(test_parman, 0);
	kfree(test_parman);
}

static bool test_parman_run_check_budgets(struct test_parman *test_parman)
{
	if (test_parman->run_budget-- == 0)
		return false;
	if (test_parman->bulk_budget-- != 0)
		return true;

	test_parman->bulk_budget = test_parman_rnd_get(test_parman) &
				   TEST_PARMAN_BULK_MAX_MASK;
	test_parman->bulk_noop = test_parman_rnd_get(test_parman) & 1;
	return true;
}

static int test_parman_run(struct test_parman *test_parman)
{
	unsigned int i = test_parman_rnd_get(test_parman);
	int err;

	while (test_parman_run_check_budgets(test_parman)) {
		unsigned int item_index = i++ & TEST_PARMAN_ITEM_MASK;
		struct test_parman_item *item = &test_parman->items[item_index];

		if (test_parman->bulk_noop)
			continue;

		if (!item->used) {
			err = parman_item_add(test_parman->parman,
					      &item->prio->parman_prio,
					      &item->parman_item);
			if (err)
				return err;
			test_parman->prio_array[item->parman_item.index] = item;
			test_parman->used_items++;
		} else {
			test_parman->prio_array[item->parman_item.index] = NULL;
			parman_item_remove(test_parman->parman,
					   &item->prio->parman_prio,
					   &item->parman_item);
			test_parman->used_items--;
		}
		item->used = !item->used;
	}
	return 0;
}

static int test_parman_check_array(struct test_parman *test_parman,
				   bool gaps_allowed)
{
	unsigned int last_unused_items = 0;
	unsigned long last_priority = 0;
	unsigned int used_items = 0;
	int i;

	if (test_parman->prio_array_limit < TEST_PARMAN_BASE_COUNT) {
		pr_err("Array limit is lower than the base count (%lu < %lu)\n",
		       test_parman->prio_array_limit, TEST_PARMAN_BASE_COUNT);
		return -EINVAL;
	}

	for (i = 0; i < test_parman->prio_array_limit; i++) {
		struct test_parman_item *item = test_parman->prio_array[i];

		if (!item) {
			last_unused_items++;
			continue;
		}
		if (last_unused_items && !gaps_allowed) {
			pr_err("Gap found in array even though they are forbidden\n");
			return -EINVAL;
		}

		last_unused_items = 0;
		used_items++;

		if (item->prio->priority < last_priority) {
			pr_err("Item belongs under higher priority then the last one (current: %lu, previous: %lu)\n",
			       item->prio->priority, last_priority);
			return -EINVAL;
		}
		last_priority = item->prio->priority;

		if (item->parman_item.index != i) {
			pr_err("Item has different index in compare to where it actually is (%lu != %d)\n",
			       item->parman_item.index, i);
			return -EINVAL;
		}
	}

	if (used_items != test_parman->used_items) {
		pr_err("Number of used items in array does not match (%u != %u)\n",
		       used_items, test_parman->used_items);
		return -EINVAL;
	}

	if (last_unused_items >= TEST_PARMAN_RESIZE_STEP_COUNT) {
		pr_err("Number of unused item at the end of array is bigger than resize step (%u >= %lu)\n",
		       last_unused_items, TEST_PARMAN_RESIZE_STEP_COUNT);
		return -EINVAL;
	}

	pr_info("Priority array check successful\n");

	return 0;
}

static int test_parman_lsort(void)
{
	struct test_parman *test_parman;
	int err;

	test_parman = test_parman_create(&test_parman_lsort_ops);
	if (IS_ERR(test_parman))
		return PTR_ERR(test_parman);

	err = test_parman_run(test_parman);
	if (err)
		goto out;

	err = test_parman_check_array(test_parman, false);
	if (err)
		goto out;
out:
	test_parman_destroy(test_parman);
	return err;
}

static int __init test_parman_init(void)
{
	return test_parman_lsort();
}

static void __exit test_parman_exit(void)
{
}

module_init(test_parman_init);
module_exit(test_parman_exit);

MODULE_LICENSE("Dual BSD/GPL");
MODULE_AUTHOR("Jiri Pirko <[email protected]>");
MODULE_DESCRIPTION("Test module for parman");
Commit	Line	Data
44091d29 JP	1	/*
	2	* lib/test_parman.c - Test module for parman
	3	* Copyright (c) 2017 Mellanox Technologies. All rights reserved.
	4	* Copyright (c) 2017 Jiri Pirko <[email protected]>
	5	*
	6	* Redistribution and use in source and binary forms, with or without
	7	* modification, are permitted provided that the following conditions are met:
	8	*
	9	* 1. Redistributions of source code must retain the above copyright
	10	* notice, this list of conditions and the following disclaimer.
	11	* 2. Redistributions in binary form must reproduce the above copyright
	12	* notice, this list of conditions and the following disclaimer in the
	13	* documentation and/or other materials provided with the distribution.
	14	* 3. Neither the names of the copyright holders nor the names of its
	15	* contributors may be used to endorse or promote products derived from
	16	* this software without specific prior written permission.
	17	*
	18	* Alternatively, this software may be distributed under the terms of the
	19	* GNU General Public License ("GPL") version 2 as published by the Free
	20	* Software Foundation.
	21	*
	22	* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
	23	* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	24	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
	25	* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
	26	* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
	27	* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
	28	* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
	29	* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
	30	* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
	31	* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
	32	* POSSIBILITY OF SUCH DAMAGE.
	33	*/
	34
	35	#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
	36
	37	#include <linux/kernel.h>
	38	#include <linux/module.h>
	39	#include <linux/slab.h>
	40	#include <linux/bitops.h>
	41	#include <linux/err.h>
	42	#include <linux/random.h>
	43	#include <linux/parman.h>
	44
	45	#define TEST_PARMAN_PRIO_SHIFT 7 /* defines number of prios for testing */
	46	#define TEST_PARMAN_PRIO_COUNT BIT(TEST_PARMAN_PRIO_SHIFT)
	47	#define TEST_PARMAN_PRIO_MASK (TEST_PARMAN_PRIO_COUNT - 1)
	48
	49	#define TEST_PARMAN_ITEM_SHIFT 13 /* defines a total number
	50	* of items for testing
	51	*/
	52	#define TEST_PARMAN_ITEM_COUNT BIT(TEST_PARMAN_ITEM_SHIFT)
	53	#define TEST_PARMAN_ITEM_MASK (TEST_PARMAN_ITEM_COUNT - 1)
	54
	55	#define TEST_PARMAN_BASE_SHIFT 8
	56	#define TEST_PARMAN_BASE_COUNT BIT(TEST_PARMAN_BASE_SHIFT)
	57	#define TEST_PARMAN_RESIZE_STEP_SHIFT 7
	58	#define TEST_PARMAN_RESIZE_STEP_COUNT BIT(TEST_PARMAN_RESIZE_STEP_SHIFT)
	59
	60	#define TEST_PARMAN_BULK_MAX_SHIFT (2 + TEST_PARMAN_RESIZE_STEP_SHIFT)
	61	#define TEST_PARMAN_BULK_MAX_COUNT BIT(TEST_PARMAN_BULK_MAX_SHIFT)
	62	#define TEST_PARMAN_BULK_MAX_MASK (TEST_PARMAN_BULK_MAX_COUNT - 1)
	63
	64	#define TEST_PARMAN_RUN_BUDGET (TEST_PARMAN_ITEM_COUNT * 256)
65
66	struct test_parman_prio {
67	struct parman_prio parman_prio;
68	unsigned long priority;
69	};
70
71	struct test_parman_item {
72	struct parman_item parman_item;
73	struct test_parman_prio *prio;
74	bool used;
75	};
76
77	struct test_parman {
78	struct parman *parman;
79	struct test_parman_item **prio_array;
80	unsigned long prio_array_limit;
81	struct test_parman_prio prios[TEST_PARMAN_PRIO_COUNT];
82	struct test_parman_item items[TEST_PARMAN_ITEM_COUNT];
83	struct rnd_state rnd;
84	unsigned long run_budget;
85	unsigned long bulk_budget;
86	bool bulk_noop;
87	unsigned int used_items;
88	};
89
90	#define ITEM_PTRS_SIZE(count) (sizeof(struct test_parman_item ) (count))
91
92	static int test_parman_resize(void *priv, unsigned long new_count)
93	{
94	struct test_parman *test_parman = priv;
95	struct test_parman_item **prio_array;
96	unsigned long old_count;
97
98	prio_array = krealloc(test_parman->prio_array,
99	ITEM_PTRS_SIZE(new_count), GFP_KERNEL);
100	if (new_count == 0)
101	return 0;
102	if (!prio_array)
103	return -ENOMEM;
104	old_count = test_parman->prio_array_limit;
105	if (new_count > old_count)
106	memset(&prio_array[old_count], 0,
107	ITEM_PTRS_SIZE(new_count - old_count));
108	test_parman->prio_array = prio_array;
109	test_parman->prio_array_limit = new_count;
110	return 0;
111	}
112
113	static void test_parman_move(void *priv, unsigned long from_index,
114	unsigned long to_index, unsigned long count)
115	{
116	struct test_parman *test_parman = priv;
117	struct test_parman_item **prio_array = test_parman->prio_array;
118
119	memmove(&prio_array[to_index], &prio_array[from_index],
120	ITEM_PTRS_SIZE(count));
121	memset(&prio_array[from_index], 0, ITEM_PTRS_SIZE(count));
122	}
123
124	static const struct parman_ops test_parman_lsort_ops = {
125	.base_count = TEST_PARMAN_BASE_COUNT,
126	.resize_step = TEST_PARMAN_RESIZE_STEP_COUNT,
127	.resize = test_parman_resize,
128	.move = test_parman_move,
129	.algo = PARMAN_ALGO_TYPE_LSORT,
130	};
131
132	static void test_parman_rnd_init(struct test_parman *test_parman)
133	{
134	prandom_seed_state(&test_parman->rnd, 3141592653589793238ULL);
135	}
136
137	static u32 test_parman_rnd_get(struct test_parman *test_parman)
138	{
139	return prandom_u32_state(&test_parman->rnd);
140	}
141
142	static unsigned long test_parman_priority_gen(struct test_parman *test_parman)
143	{
144	unsigned long priority;
145	int i;
146
147	again:
148	priority = test_parman_rnd_get(test_parman);
149	if (priority == 0)
150	goto again;
151
152	for (i = 0; i < TEST_PARMAN_PRIO_COUNT; i++) {
153	struct test_parman_prio *prio = &test_parman->prios[i];
154
155	if (prio->priority == 0)
156	break;
157	if (prio->priority == priority)
158	goto again;
159	}
160	return priority;
161	}
162
163	static void test_parman_prios_init(struct test_parman *test_parman)
164	{
165	int i;
166
167	for (i = 0; i < TEST_PARMAN_PRIO_COUNT; i++) {
168	struct test_parman_prio *prio = &test_parman->prios[i];
169
170	/* Assign random uniqueue priority to each prio structure */
171	prio->priority = test_parman_priority_gen(test_parman);
172	parman_prio_init(test_parman->parman, &prio->parman_prio,
173	prio->priority);
174	}
175	}
176
177	static void test_parman_prios_fini(struct test_parman *test_parman)
178	{
179	int i;
180
181	for (i = 0; i < TEST_PARMAN_PRIO_COUNT; i++) {
182	struct test_parman_prio *prio = &test_parman->prios[i];
183
184	parman_prio_fini(&prio->parman_prio);
185	}
186	}
187
188	static void test_parman_items_init(struct test_parman *test_parman)
189	{
190	int i;
191
192	for (i = 0; i < TEST_PARMAN_ITEM_COUNT; i++) {
193	struct test_parman_item *item = &test_parman->items[i];
194	unsigned int prio_index = test_parman_rnd_get(test_parman) &
195	TEST_PARMAN_PRIO_MASK;
196
197	/* Assign random prio to each item structure */
198	item->prio = &test_parman->prios[prio_index];
199	}
200	}
201
202	static void test_parman_items_fini(struct test_parman *test_parman)
203	{
204	int i;
205
206	for (i = 0; i < TEST_PARMAN_ITEM_COUNT; i++) {
207	struct test_parman_item *item = &test_parman->items[i];
208
209	if (!item->used)
210	continue;
211	parman_item_remove(test_parman->parman,
212	&item->prio->parman_prio,
213	&item->parman_item);
214	}
215	}
216
217	static struct test_parman test_parman_create(const struct parman_ops ops)
218	{
219	struct test_parman *test_parman;
220	int err;
221
222	test_parman = kzalloc(sizeof(*test_parman), GFP_KERNEL);
223	if (!test_parman)
224	return ERR_PTR(-ENOMEM);
225	err = test_parman_resize(test_parman, TEST_PARMAN_BASE_COUNT);
226	if (err)
227	goto err_resize;
228	test_parman->parman = parman_create(ops, test_parman);
229	if (!test_parman->parman) {
230	err = -ENOMEM;
231	goto err_parman_create;
232	}
233	test_parman_rnd_init(test_parman);
234	test_parman_prios_init(test_parman);
235	test_parman_items_init(test_parman);
236	test_parman->run_budget = TEST_PARMAN_RUN_BUDGET;
237	return test_parman;
238
239	err_parman_create:
240	test_parman_resize(test_parman, 0);
241	err_resize:
242	kfree(test_parman);
243	return ERR_PTR(err);
244	}
245
246	static void test_parman_destroy(struct test_parman *test_parman)
247	{
248	test_parman_items_fini(test_parman);
249	test_parman_prios_fini(test_parman);
250	parman_destroy(test_parman->parman);
251	test_parman_resize(test_parman, 0);
252	kfree(test_parman);
253	}
254
255	static bool test_parman_run_check_budgets(struct test_parman *test_parman)
256	{
257	if (test_parman->run_budget-- == 0)
258	return false;
259	if (test_parman->bulk_budget-- != 0)
260	return true;
261
262	test_parman->bulk_budget = test_parman_rnd_get(test_parman) &
263	TEST_PARMAN_BULK_MAX_MASK;
264	test_parman->bulk_noop = test_parman_rnd_get(test_parman) & 1;
265	return true;
266	}
267
268	static int test_parman_run(struct test_parman *test_parman)
269	{
270	unsigned int i = test_parman_rnd_get(test_parman);
271	int err;
272
273	while (test_parman_run_check_budgets(test_parman)) {
274	unsigned int item_index = i++ & TEST_PARMAN_ITEM_MASK;
275	struct test_parman_item *item = &test_parman->items[item_index];
276
277	if (test_parman->bulk_noop)
278	continue;
279
280	if (!item->used) {
281	err = parman_item_add(test_parman->parman,
282	&item->prio->parman_prio,
283	&item->parman_item);
284	if (err)
285	return err;
286	test_parman->prio_array[item->parman_item.index] = item;
287	test_parman->used_items++;
288	} else {
289	test_parman->prio_array[item->parman_item.index] = NULL;
290	parman_item_remove(test_parman->parman,
291	&item->prio->parman_prio,
292	&item->parman_item);
293	test_parman->used_items--;
294	}
295	item->used = !item->used;
296	}
297	return 0;
298	}
299
300	static int test_parman_check_array(struct test_parman *test_parman,
301	bool gaps_allowed)
302	{
303	unsigned int last_unused_items = 0;
304	unsigned long last_priority = 0;
305	unsigned int used_items = 0;
306	int i;
307
308	if (test_parman->prio_array_limit < TEST_PARMAN_BASE_COUNT) {
309	pr_err("Array limit is lower than the base count (%lu < %lu)\n",
310	test_parman->prio_array_limit, TEST_PARMAN_BASE_COUNT);
311	return -EINVAL;
312	}
313
314	for (i = 0; i < test_parman->prio_array_limit; i++) {
315	struct test_parman_item *item = test_parman->prio_array[i];
316
317	if (!item) {
318	last_unused_items++;
319	continue;
320	}
321	if (last_unused_items && !gaps_allowed) {
322	pr_err("Gap found in array even though they are forbidden\n");
323	return -EINVAL;
324	}
325
326	last_unused_items = 0;
327	used_items++;
328
329	if (item->prio->priority < last_priority) {
330	pr_err("Item belongs under higher priority then the last one (current: %lu, previous: %lu)\n",
331	item->prio->priority, last_priority);
332	return -EINVAL;
333	}
334	last_priority = item->prio->priority;
335
336	if (item->parman_item.index != i) {
8118b7b7	337	pr_err("Item has different index in compare to where it actually is (%lu != %d)\n",
44091d29 JP	338	item->parman_item.index, i);
	339	return -EINVAL;
	340	}
	341	}
	342
	343	if (used_items != test_parman->used_items) {
	344	pr_err("Number of used items in array does not match (%u != %u)\n",
	345	used_items, test_parman->used_items);
	346	return -EINVAL;
	347	}
	348
	349	if (last_unused_items >= TEST_PARMAN_RESIZE_STEP_COUNT) {
	350	pr_err("Number of unused item at the end of array is bigger than resize step (%u >= %lu)\n",
	351	last_unused_items, TEST_PARMAN_RESIZE_STEP_COUNT);
	352	return -EINVAL;
	353	}
	354
	355	pr_info("Priority array check successful\n");
	356
	357	return 0;
	358	}
	359
	360	static int test_parman_lsort(void)
	361	{
	362	struct test_parman *test_parman;
	363	int err;
	364
	365	test_parman = test_parman_create(&test_parman_lsort_ops);
	366	if (IS_ERR(test_parman))
	367	return PTR_ERR(test_parman);
	368
	369	err = test_parman_run(test_parman);
	370	if (err)
	371	goto out;
	372
	373	err = test_parman_check_array(test_parman, false);
	374	if (err)
	375	goto out;
	376	out:
	377	test_parman_destroy(test_parman);
	378	return err;
	379	}
	380
	381	static int __init test_parman_init(void)
	382	{
	383	return test_parman_lsort();
	384	}
	385
	386	static void __exit test_parman_exit(void)
	387	{
	388	}
	389
	390	module_init(test_parman_init);
	391	module_exit(test_parman_exit);
	392
	393	MODULE_LICENSE("Dual BSD/GPL");
	394	MODULE_AUTHOR("Jiri Pirko <[email protected]>");
	395	MODULE_DESCRIPTION("Test module for parman");