396 lines · c
1/*2 * lib/test_parman.c - Test module for parman3 * 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 without7 * modification, are permitted provided that the following conditions are met:8 *9 * 1. Redistributions of source code must retain the above copyright10 * notice, this list of conditions and the following disclaimer.11 * 2. Redistributions in binary form must reproduce the above copyright12 * notice, this list of conditions and the following disclaimer in the13 * documentation and/or other materials provided with the distribution.14 * 3. Neither the names of the copyright holders nor the names of its15 * contributors may be used to endorse or promote products derived from16 * this software without specific prior written permission.17 *18 * Alternatively, this software may be distributed under the terms of the19 * GNU General Public License ("GPL") version 2 as published by the Free20 * 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, THE24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE25 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE26 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR27 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF28 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS29 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN30 * 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 THE32 * POSSIBILITY OF SUCH DAMAGE.33 */34 35#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt36 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 number50 * of items for testing51 */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 856#define TEST_PARMAN_BASE_COUNT BIT(TEST_PARMAN_BASE_SHIFT)57#define TEST_PARMAN_RESIZE_STEP_SHIFT 758#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 /* 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 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 /* Assign random prio to each item structure */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