~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/lib/test_parman.c

Version: ~ [ linux-5.4 ] ~ [ linux-5.3.13 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.86 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.156 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.203 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.202 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.78 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-3.9.11 ] ~ [ linux-3.8.13 ] ~ [ linux-3.7.10 ] ~ [ linux-3.6.11 ] ~ [ linux-3.5.7 ] ~ [ linux-3.4.113 ] ~ [ linux-3.3.8 ] ~ [ linux-3.2.102 ] ~ [ linux-3.1.10 ] ~ [ linux-3.0.101 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  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(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) {
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(&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 <jiri@mellanox.com>");
395 MODULE_DESCRIPTION("Test module for parman");
396 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp