1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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
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
50
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
66struct test_parman_prio {
67 struct parman_prio parman_prio;
68 unsigned long priority;
69};
70
71struct test_parman_item {
72 struct parman_item parman_item;
73 struct test_parman_prio *prio;
74 bool used;
75};
76
77struct 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
92static 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
113static 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
124static 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
132static void test_parman_rnd_init(struct test_parman *test_parman)
133{
134 prandom_seed_state(&test_parman->rnd, 3141592653589793238ULL);
135}
136
137static u32 test_parman_rnd_get(struct test_parman *test_parman)
138{
139 return prandom_u32_state(&test_parman->rnd);
140}
141
142static unsigned long test_parman_priority_gen(struct test_parman *test_parman)
143{
144 unsigned long priority;
145 int i;
146
147again:
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
163static 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
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
177static 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
188static 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
198 item->prio = &test_parman->prios[prio_index];
199 }
200}
201
202static 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
217static 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
239err_parman_create:
240 test_parman_resize(test_parman, 0);
241err_resize:
242 kfree(test_parman);
243 return ERR_PTR(err);
244}
245
246static 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
255static 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
268static 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
300static 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
360static 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;
376out:
377 test_parman_destroy(test_parman);
378 return err;
379}
380
381static int __init test_parman_init(void)
382{
383 return test_parman_lsort();
384}
385
386static void __exit test_parman_exit(void)
387{
388}
389
390module_init(test_parman_init);
391module_exit(test_parman_exit);
392
393MODULE_LICENSE("Dual BSD/GPL");
394MODULE_AUTHOR("Jiri Pirko <jiri@mellanox.com>");
395MODULE_DESCRIPTION("Test module for parman");
396
