lib/test_parman.c

   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");