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