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 <jiri@mellanox.com>
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 
test_parman_resize(void * priv,unsigned long new_count)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 
test_parman_move(void * priv,unsigned long from_index,unsigned long to_index,unsigned long count)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 
test_parman_rnd_init(struct test_parman * test_parman)132 static void test_parman_rnd_init(struct test_parman *test_parman)
133 {
134 	prandom_seed_state(&test_parman->rnd, 3141592653589793238ULL);
135 }
136 
test_parman_rnd_get(struct test_parman * test_parman)137 static u32 test_parman_rnd_get(struct test_parman *test_parman)
138 {
139 	return prandom_u32_state(&test_parman->rnd);
140 }
141 
test_parman_priority_gen(struct test_parman * test_parman)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 
test_parman_prios_init(struct test_parman * test_parman)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 
test_parman_prios_fini(struct test_parman * test_parman)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 
test_parman_items_init(struct test_parman * test_parman)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 
test_parman_items_fini(struct test_parman * test_parman)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 
test_parman_create(const struct parman_ops * ops)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 
test_parman_destroy(struct test_parman * test_parman)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 
test_parman_run_check_budgets(struct test_parman * test_parman)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 
test_parman_run(struct test_parman * test_parman)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 
test_parman_check_array(struct test_parman * test_parman,bool gaps_allowed)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) {
337 			pr_err("Item has different index in compare to where it actually is (%lu != %d)\n",
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 
test_parman_lsort(void)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 
test_parman_init(void)381 static int __init test_parman_init(void)
382 {
383 	return test_parman_lsort();
384 }
385 
test_parman_exit(void)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 <jiri@mellanox.com>");
395 MODULE_DESCRIPTION("Test module for parman");
396