the-tree/lib/test_parman.c

0001 /*
0002  * lib/test_parman.c - Test module for parman
0003  * Copyright (c) 2017 Mellanox Technologies. All rights reserved.
0004  * Copyright (c) 2017 Jiri Pirko <jiri@mellanox.com>
0005  *
0006  * Redistribution and use in source and binary forms, with or without
0007  * modification, are permitted provided that the following conditions are met:
0008  *
0009  * 1. Redistributions of source code must retain the above copyright
0010  *    notice, this list of conditions and the following disclaimer.
0011  * 2. Redistributions in binary form must reproduce the above copyright
0012  *    notice, this list of conditions and the following disclaimer in the
0013  *    documentation and/or other materials provided with the distribution.
0014  * 3. Neither the names of the copyright holders nor the names of its
0015  *    contributors may be used to endorse or promote products derived from
0016  *    this software without specific prior written permission.
0017  *
0018  * Alternatively, this software may be distributed under the terms of the
0019  * GNU General Public License ("GPL") version 2 as published by the Free
0020  * Software Foundation.
0021  *
0022  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
0023  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
0024  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
0025  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
0026  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
0027  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
0028  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
0029  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
0030  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
0031  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
0032  * POSSIBILITY OF SUCH DAMAGE.
0033  */
0034
0035 #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
0036
0037 #include <linux/kernel.h>
0038 #include <linux/module.h>
0039 #include <linux/slab.h>
0040 #include <linux/bitops.h>
0041 #include <linux/err.h>
0042 #include <linux/random.h>
0043 #include <linux/parman.h>
0044
0045 #define TEST_PARMAN_PRIO_SHIFT 7 /* defines number of prios for testing */
0046 #define TEST_PARMAN_PRIO_COUNT BIT(TEST_PARMAN_PRIO_SHIFT)
0047 #define TEST_PARMAN_PRIO_MASK (TEST_PARMAN_PRIO_COUNT - 1)
0048
0049 #define TEST_PARMAN_ITEM_SHIFT 13 /* defines a total number
0050                    * of items for testing
0051                    */
0052 #define TEST_PARMAN_ITEM_COUNT BIT(TEST_PARMAN_ITEM_SHIFT)
0053 #define TEST_PARMAN_ITEM_MASK (TEST_PARMAN_ITEM_COUNT - 1)
0054
0055 #define TEST_PARMAN_BASE_SHIFT 8
0056 #define TEST_PARMAN_BASE_COUNT BIT(TEST_PARMAN_BASE_SHIFT)
0057 #define TEST_PARMAN_RESIZE_STEP_SHIFT 7
0058 #define TEST_PARMAN_RESIZE_STEP_COUNT BIT(TEST_PARMAN_RESIZE_STEP_SHIFT)
0059
0060 #define TEST_PARMAN_BULK_MAX_SHIFT (2 + TEST_PARMAN_RESIZE_STEP_SHIFT)
0061 #define TEST_PARMAN_BULK_MAX_COUNT BIT(TEST_PARMAN_BULK_MAX_SHIFT)
0062 #define TEST_PARMAN_BULK_MAX_MASK (TEST_PARMAN_BULK_MAX_COUNT - 1)
0063
0064 #define TEST_PARMAN_RUN_BUDGET (TEST_PARMAN_ITEM_COUNT * 256)
0065
0066 struct test_parman_prio {
0067     struct parman_prio parman_prio;
0068     unsigned long priority;
0069 };
0070
0071 struct test_parman_item {
0072     struct parman_item parman_item;
0073     struct test_parman_prio *prio;
0074     bool used;
0075 };
0076
0077 struct test_parman {
0078     struct parman *parman;
0079     struct test_parman_item **prio_array;
0080     unsigned long prio_array_limit;
0081     struct test_parman_prio prios[TEST_PARMAN_PRIO_COUNT];
0082     struct test_parman_item items[TEST_PARMAN_ITEM_COUNT];
0083     struct rnd_state rnd;
0084     unsigned long run_budget;
0085     unsigned long bulk_budget;
0086     bool bulk_noop;
0087     unsigned int used_items;
0088 };
0089
0090 #define ITEM_PTRS_SIZE(count) (sizeof(struct test_parman_item *) * (count))
0091
0092 static int test_parman_resize(void *priv, unsigned long new_count)
0093 {
0094     struct test_parman *test_parman = priv;
0095     struct test_parman_item **prio_array;
0096     unsigned long old_count;
0097
0098     prio_array = krealloc(test_parman->prio_array,
0099                   ITEM_PTRS_SIZE(new_count), GFP_KERNEL);
0100     if (new_count == 0)
0101         return 0;
0102     if (!prio_array)
0103         return -ENOMEM;
0104     old_count = test_parman->prio_array_limit;
0105     if (new_count > old_count)
0106         memset(&prio_array[old_count], 0,
0107                ITEM_PTRS_SIZE(new_count - old_count));
0108     test_parman->prio_array = prio_array;
0109     test_parman->prio_array_limit = new_count;
0110     return 0;
0111 }
0112
0113 static void test_parman_move(void *priv, unsigned long from_index,
0114                  unsigned long to_index, unsigned long count)
0115 {
0116     struct test_parman *test_parman = priv;
0117     struct test_parman_item **prio_array = test_parman->prio_array;
0118
0119     memmove(&prio_array[to_index], &prio_array[from_index],
0120         ITEM_PTRS_SIZE(count));
0121     memset(&prio_array[from_index], 0, ITEM_PTRS_SIZE(count));
0122 }
0123
0124 static const struct parman_ops test_parman_lsort_ops = {
0125     .base_count = TEST_PARMAN_BASE_COUNT,
0126     .resize_step    = TEST_PARMAN_RESIZE_STEP_COUNT,
0127     .resize     = test_parman_resize,
0128     .move       = test_parman_move,
0129     .algo       = PARMAN_ALGO_TYPE_LSORT,
0130 };
0131
0132 static void test_parman_rnd_init(struct test_parman *test_parman)
0133 {
0134     prandom_seed_state(&test_parman->rnd, 3141592653589793238ULL);
0135 }
0136
0137 static u32 test_parman_rnd_get(struct test_parman *test_parman)
0138 {
0139     return prandom_u32_state(&test_parman->rnd);
0140 }
0141
0142 static unsigned long test_parman_priority_gen(struct test_parman *test_parman)
0143 {
0144     unsigned long priority;
0145     int i;
0146
0147 again:
0148     priority = test_parman_rnd_get(test_parman);
0149     if (priority == 0)
0150         goto again;
0151
0152     for (i = 0; i < TEST_PARMAN_PRIO_COUNT; i++) {
0153         struct test_parman_prio *prio = &test_parman->prios[i];
0154
0155         if (prio->priority == 0)
0156             break;
0157         if (prio->priority == priority)
0158             goto again;
0159     }
0160     return priority;
0161 }
0162
0163 static void test_parman_prios_init(struct test_parman *test_parman)
0164 {
0165     int i;
0166
0167     for (i = 0; i < TEST_PARMAN_PRIO_COUNT; i++) {
0168         struct test_parman_prio *prio = &test_parman->prios[i];
0169
0170         /* Assign random uniqueue priority to each prio structure */
0171         prio->priority = test_parman_priority_gen(test_parman);
0172         parman_prio_init(test_parman->parman, &prio->parman_prio,
0173                  prio->priority);
0174     }
0175 }
0176
0177 static void test_parman_prios_fini(struct test_parman *test_parman)
0178 {
0179     int i;
0180
0181     for (i = 0; i < TEST_PARMAN_PRIO_COUNT; i++) {
0182         struct test_parman_prio *prio = &test_parman->prios[i];
0183
0184         parman_prio_fini(&prio->parman_prio);
0185     }
0186 }
0187
0188 static void test_parman_items_init(struct test_parman *test_parman)
0189 {
0190     int i;
0191
0192     for (i = 0; i < TEST_PARMAN_ITEM_COUNT; i++) {
0193         struct test_parman_item *item = &test_parman->items[i];
0194         unsigned int prio_index = test_parman_rnd_get(test_parman) &
0195                       TEST_PARMAN_PRIO_MASK;
0196
0197         /* Assign random prio to each item structure */
0198         item->prio = &test_parman->prios[prio_index];
0199     }
0200 }
0201
0202 static void test_parman_items_fini(struct test_parman *test_parman)
0203 {
0204     int i;
0205
0206     for (i = 0; i < TEST_PARMAN_ITEM_COUNT; i++) {
0207         struct test_parman_item *item = &test_parman->items[i];
0208
0209         if (!item->used)
0210             continue;
0211         parman_item_remove(test_parman->parman,
0212                    &item->prio->parman_prio,
0213                    &item->parman_item);
0214     }
0215 }
0216
0217 static struct test_parman *test_parman_create(const struct parman_ops *ops)
0218 {
0219     struct test_parman *test_parman;
0220     int err;
0221
0222     test_parman = kzalloc(sizeof(*test_parman), GFP_KERNEL);
0223     if (!test_parman)
0224         return ERR_PTR(-ENOMEM);
0225     err = test_parman_resize(test_parman, TEST_PARMAN_BASE_COUNT);
0226     if (err)
0227         goto err_resize;
0228     test_parman->parman = parman_create(ops, test_parman);
0229     if (!test_parman->parman) {
0230         err = -ENOMEM;
0231         goto err_parman_create;
0232     }
0233     test_parman_rnd_init(test_parman);
0234     test_parman_prios_init(test_parman);
0235     test_parman_items_init(test_parman);
0236     test_parman->run_budget = TEST_PARMAN_RUN_BUDGET;
0237     return test_parman;
0238
0239 err_parman_create:
0240     test_parman_resize(test_parman, 0);
0241 err_resize:
0242     kfree(test_parman);
0243     return ERR_PTR(err);
0244 }
0245
0246 static void test_parman_destroy(struct test_parman *test_parman)
0247 {
0248     test_parman_items_fini(test_parman);
0249     test_parman_prios_fini(test_parman);
0250     parman_destroy(test_parman->parman);
0251     test_parman_resize(test_parman, 0);
0252     kfree(test_parman);
0253 }
0254
0255 static bool test_parman_run_check_budgets(struct test_parman *test_parman)
0256 {
0257     if (test_parman->run_budget-- == 0)
0258         return false;
0259     if (test_parman->bulk_budget-- != 0)
0260         return true;
0261
0262     test_parman->bulk_budget = test_parman_rnd_get(test_parman) &
0263                    TEST_PARMAN_BULK_MAX_MASK;
0264     test_parman->bulk_noop = test_parman_rnd_get(test_parman) & 1;
0265     return true;
0266 }
0267
0268 static int test_parman_run(struct test_parman *test_parman)
0269 {
0270     unsigned int i = test_parman_rnd_get(test_parman);
0271     int err;
0272
0273     while (test_parman_run_check_budgets(test_parman)) {
0274         unsigned int item_index = i++ & TEST_PARMAN_ITEM_MASK;
0275         struct test_parman_item *item = &test_parman->items[item_index];
0276
0277         if (test_parman->bulk_noop)
0278             continue;
0279
0280         if (!item->used) {
0281             err = parman_item_add(test_parman->parman,
0282                           &item->prio->parman_prio,
0283                           &item->parman_item);
0284             if (err)
0285                 return err;
0286             test_parman->prio_array[item->parman_item.index] = item;
0287             test_parman->used_items++;
0288         } else {
0289             test_parman->prio_array[item->parman_item.index] = NULL;
0290             parman_item_remove(test_parman->parman,
0291                        &item->prio->parman_prio,
0292                        &item->parman_item);
0293             test_parman->used_items--;
0294         }
0295         item->used = !item->used;
0296     }
0297     return 0;
0298 }
0299
0300 static int test_parman_check_array(struct test_parman *test_parman,
0301                    bool gaps_allowed)
0302 {
0303     unsigned int last_unused_items = 0;
0304     unsigned long last_priority = 0;
0305     unsigned int used_items = 0;
0306     int i;
0307
0308     if (test_parman->prio_array_limit < TEST_PARMAN_BASE_COUNT) {
0309         pr_err("Array limit is lower than the base count (%lu < %lu)\n",
0310                test_parman->prio_array_limit, TEST_PARMAN_BASE_COUNT);
0311         return -EINVAL;
0312     }
0313
0314     for (i = 0; i < test_parman->prio_array_limit; i++) {
0315         struct test_parman_item *item = test_parman->prio_array[i];
0316
0317         if (!item) {
0318             last_unused_items++;
0319             continue;
0320         }
0321         if (last_unused_items && !gaps_allowed) {
0322             pr_err("Gap found in array even though they are forbidden\n");
0323             return -EINVAL;
0324         }
0325
0326         last_unused_items = 0;
0327         used_items++;
0328
0329         if (item->prio->priority < last_priority) {
0330             pr_err("Item belongs under higher priority then the last one (current: %lu, previous: %lu)\n",
0331                    item->prio->priority, last_priority);
0332             return -EINVAL;
0333         }
0334         last_priority = item->prio->priority;
0335
0336         if (item->parman_item.index != i) {
0337             pr_err("Item has different index in compare to where it actually is (%lu != %d)\n",
0338                    item->parman_item.index, i);
0339             return -EINVAL;
0340         }
0341     }
0342
0343     if (used_items != test_parman->used_items) {
0344         pr_err("Number of used items in array does not match (%u != %u)\n",
0345                used_items, test_parman->used_items);
0346         return -EINVAL;
0347     }
0348
0349     if (last_unused_items >= TEST_PARMAN_RESIZE_STEP_COUNT) {
0350         pr_err("Number of unused item at the end of array is bigger than resize step (%u >= %lu)\n",
0351                last_unused_items, TEST_PARMAN_RESIZE_STEP_COUNT);
0352         return -EINVAL;
0353     }
0354
0355     pr_info("Priority array check successful\n");
0356
0357     return 0;
0358 }
0359
0360 static int test_parman_lsort(void)
0361 {
0362     struct test_parman *test_parman;
0363     int err;
0364
0365     test_parman = test_parman_create(&test_parman_lsort_ops);
0366     if (IS_ERR(test_parman))
0367         return PTR_ERR(test_parman);
0368
0369     err = test_parman_run(test_parman);
0370     if (err)
0371         goto out;
0372
0373     err = test_parman_check_array(test_parman, false);
0374     if (err)
0375         goto out;
0376 out:
0377     test_parman_destroy(test_parman);
0378     return err;
0379 }
0380
0381 static int __init test_parman_init(void)
0382 {
0383     return test_parman_lsort();
0384 }
0385
0386 static void __exit test_parman_exit(void)
0387 {
0388 }
0389
0390 module_init(test_parman_init);
0391 module_exit(test_parman_exit);
0392
0393 MODULE_LICENSE("Dual BSD/GPL");
0394 MODULE_AUTHOR("Jiri Pirko <jiri@mellanox.com>");
0395 MODULE_DESCRIPTION("Test module for parman");