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 | |
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(objp: 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(state: &test_parman->rnd, seed: 3141592653589793238ULL); |
135 | } |
136 | |
137 | static u32 test_parman_rnd_get(struct test_parman *test_parman) |
138 | { |
139 | return prandom_u32_state(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(parman: test_parman->parman, prio: &prio->parman_prio, |
173 | priority: 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: &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(parman: test_parman->parman, |
212 | prio: &item->prio->parman_prio, |
213 | item: &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(size: sizeof(*test_parman), GFP_KERNEL); |
223 | if (!test_parman) |
224 | return ERR_PTR(error: -ENOMEM); |
225 | err = test_parman_resize(priv: test_parman, TEST_PARMAN_BASE_COUNT); |
226 | if (err) |
227 | goto err_resize; |
228 | test_parman->parman = parman_create(ops, priv: 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(priv: test_parman, new_count: 0); |
241 | err_resize: |
242 | kfree(objp: test_parman); |
243 | return ERR_PTR(error: 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(parman: test_parman->parman); |
251 | test_parman_resize(priv: test_parman, new_count: 0); |
252 | kfree(objp: 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(parman: test_parman->parman, |
282 | prio: &item->prio->parman_prio, |
283 | item: &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(parman: test_parman->parman, |
291 | prio: &item->prio->parman_prio, |
292 | item: &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) { |
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 | |
360 | static int test_parman_lsort(void) |
361 | { |
362 | struct test_parman *test_parman; |
363 | int err; |
364 | |
365 | test_parman = test_parman_create(ops: &test_parman_lsort_ops); |
366 | if (IS_ERR(ptr: test_parman)) |
367 | return PTR_ERR(ptr: 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, gaps_allowed: 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 <jiri@mellanox.com>" ); |
395 | MODULE_DESCRIPTION("Test module for parman" ); |
396 | |