| 1 | // SPDX-License-Identifier: GPL-2.0-only |
| 2 | /* |
| 3 | * Test cases for bitmap API. |
| 4 | */ |
| 5 | |
| 6 | #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt |
| 7 | |
| 8 | #include <linux/bitmap.h> |
| 9 | #include <linux/init.h> |
| 10 | #include <linux/kernel.h> |
| 11 | #include <linux/module.h> |
| 12 | #include <linux/printk.h> |
| 13 | #include <linux/slab.h> |
| 14 | #include <linux/string.h> |
| 15 | #include <linux/uaccess.h> |
| 16 | |
| 17 | #include "../tools/testing/selftests/kselftest_module.h" |
| 18 | |
| 19 | #define EXP1_IN_BITS (sizeof(exp1) * 8) |
| 20 | |
| 21 | KSTM_MODULE_GLOBALS(); |
| 22 | |
| 23 | static char pbl_buffer[PAGE_SIZE] __initdata; |
| 24 | static char print_buf[PAGE_SIZE * 2] __initdata; |
| 25 | |
| 26 | static const unsigned long exp1[] __initconst = { |
| 27 | BITMAP_FROM_U64(1), |
| 28 | BITMAP_FROM_U64(2), |
| 29 | BITMAP_FROM_U64(0x0000ffff), |
| 30 | BITMAP_FROM_U64(0xffff0000), |
| 31 | BITMAP_FROM_U64(0x55555555), |
| 32 | BITMAP_FROM_U64(0xaaaaaaaa), |
| 33 | BITMAP_FROM_U64(0x11111111), |
| 34 | BITMAP_FROM_U64(0x22222222), |
| 35 | BITMAP_FROM_U64(0xffffffff), |
| 36 | BITMAP_FROM_U64(0xfffffffe), |
| 37 | BITMAP_FROM_U64(0x3333333311111111ULL), |
| 38 | BITMAP_FROM_U64(0xffffffff77777777ULL), |
| 39 | BITMAP_FROM_U64(0), |
| 40 | BITMAP_FROM_U64(0x00008000), |
| 41 | BITMAP_FROM_U64(0x80000000), |
| 42 | }; |
| 43 | |
| 44 | static const unsigned long exp2[] __initconst = { |
| 45 | BITMAP_FROM_U64(0x3333333311111111ULL), |
| 46 | BITMAP_FROM_U64(0xffffffff77777777ULL), |
| 47 | }; |
| 48 | |
| 49 | /* Fibonacci sequence */ |
| 50 | static const unsigned long exp2_to_exp3_mask[] __initconst = { |
| 51 | BITMAP_FROM_U64(0x008000020020212eULL), |
| 52 | }; |
| 53 | /* exp3_0_1 = (exp2[0] & ~exp2_to_exp3_mask) | (exp2[1] & exp2_to_exp3_mask) */ |
| 54 | static const unsigned long exp3_0_1[] __initconst = { |
| 55 | BITMAP_FROM_U64(0x33b3333311313137ULL), |
| 56 | }; |
| 57 | /* exp3_1_0 = (exp2[1] & ~exp2_to_exp3_mask) | (exp2[0] & exp2_to_exp3_mask) */ |
| 58 | static const unsigned long exp3_1_0[] __initconst = { |
| 59 | BITMAP_FROM_U64(0xff7fffff77575751ULL), |
| 60 | }; |
| 61 | |
| 62 | static bool __init |
| 63 | __check_eq_uint(const char *srcfile, unsigned int line, |
| 64 | const unsigned int exp_uint, unsigned int x) |
| 65 | { |
| 66 | if (exp_uint != x) { |
| 67 | pr_err("[%s:%u] expected %u, got %u\n", |
| 68 | srcfile, line, exp_uint, x); |
| 69 | return false; |
| 70 | } |
| 71 | return true; |
| 72 | } |
| 73 | |
| 74 | |
| 75 | static bool __init |
| 76 | __check_eq_bitmap(const char *srcfile, unsigned int line, |
| 77 | const unsigned long *exp_bmap, const unsigned long *bmap, |
| 78 | unsigned int nbits) |
| 79 | { |
| 80 | if (!bitmap_equal(exp_bmap, bmap, nbits)) { |
| 81 | pr_warn("[%s:%u] bitmaps contents differ: expected \"%*pbl\", got \"%*pbl\"\n", |
| 82 | srcfile, line, |
| 83 | nbits, exp_bmap, nbits, bmap); |
| 84 | return false; |
| 85 | } |
| 86 | return true; |
| 87 | } |
| 88 | |
| 89 | static bool __init |
| 90 | __check_eq_pbl(const char *srcfile, unsigned int line, |
| 91 | const char *expected_pbl, |
| 92 | const unsigned long *bitmap, unsigned int nbits) |
| 93 | { |
| 94 | snprintf(pbl_buffer, sizeof(pbl_buffer), "%*pbl", nbits, bitmap); |
| 95 | if (strcmp(expected_pbl, pbl_buffer)) { |
| 96 | pr_warn("[%s:%u] expected \"%s\", got \"%s\"\n", |
| 97 | srcfile, line, |
| 98 | expected_pbl, pbl_buffer); |
| 99 | return false; |
| 100 | } |
| 101 | return true; |
| 102 | } |
| 103 | |
| 104 | static bool __init |
| 105 | __check_eq_u32_array(const char *srcfile, unsigned int line, |
| 106 | const u32 *exp_arr, unsigned int exp_len, |
| 107 | const u32 *arr, unsigned int len) __used; |
| 108 | static bool __init |
| 109 | __check_eq_u32_array(const char *srcfile, unsigned int line, |
| 110 | const u32 *exp_arr, unsigned int exp_len, |
| 111 | const u32 *arr, unsigned int len) |
| 112 | { |
| 113 | if (exp_len != len) { |
| 114 | pr_warn("[%s:%u] array length differ: expected %u, got %u\n", |
| 115 | srcfile, line, |
| 116 | exp_len, len); |
| 117 | return false; |
| 118 | } |
| 119 | |
| 120 | if (memcmp(exp_arr, arr, len*sizeof(*arr))) { |
| 121 | pr_warn("[%s:%u] array contents differ\n", srcfile, line); |
| 122 | print_hex_dump(KERN_WARNING, " exp: ", DUMP_PREFIX_OFFSET, |
| 123 | 32, 4, exp_arr, exp_len*sizeof(*exp_arr), false); |
| 124 | print_hex_dump(KERN_WARNING, " got: ", DUMP_PREFIX_OFFSET, |
| 125 | 32, 4, arr, len*sizeof(*arr), false); |
| 126 | return false; |
| 127 | } |
| 128 | |
| 129 | return true; |
| 130 | } |
| 131 | |
| 132 | static bool __init __check_eq_clump8(const char *srcfile, unsigned int line, |
| 133 | const unsigned int offset, |
| 134 | const unsigned int size, |
| 135 | const unsigned char *const clump_exp, |
| 136 | const unsigned long *const clump) |
| 137 | { |
| 138 | unsigned long exp; |
| 139 | |
| 140 | if (offset >= size) { |
| 141 | pr_warn("[%s:%u] bit offset for clump out-of-bounds: expected less than %u, got %u\n", |
| 142 | srcfile, line, size, offset); |
| 143 | return false; |
| 144 | } |
| 145 | |
| 146 | exp = clump_exp[offset / 8]; |
| 147 | if (!exp) { |
| 148 | pr_warn("[%s:%u] bit offset for zero clump: expected nonzero clump, got bit offset %u with clump value 0", |
| 149 | srcfile, line, offset); |
| 150 | return false; |
| 151 | } |
| 152 | |
| 153 | if (*clump != exp) { |
| 154 | pr_warn("[%s:%u] expected clump value of 0x%lX, got clump value of 0x%lX", |
| 155 | srcfile, line, exp, *clump); |
| 156 | return false; |
| 157 | } |
| 158 | |
| 159 | return true; |
| 160 | } |
| 161 | |
| 162 | static bool __init |
| 163 | __check_eq_str(const char *srcfile, unsigned int line, |
| 164 | const char *exp_str, const char *str, |
| 165 | unsigned int len) |
| 166 | { |
| 167 | bool eq; |
| 168 | |
| 169 | eq = strncmp(exp_str, str, len) == 0; |
| 170 | if (!eq) |
| 171 | pr_err("[%s:%u] expected %s, got %s\n", srcfile, line, exp_str, str); |
| 172 | |
| 173 | return eq; |
| 174 | } |
| 175 | |
| 176 | #define __expect_eq(suffix, ...) \ |
| 177 | ({ \ |
| 178 | int result = 0; \ |
| 179 | total_tests++; \ |
| 180 | if (!__check_eq_ ## suffix(__FILE__, __LINE__, \ |
| 181 | ##__VA_ARGS__)) { \ |
| 182 | failed_tests++; \ |
| 183 | result = 1; \ |
| 184 | } \ |
| 185 | result; \ |
| 186 | }) |
| 187 | |
| 188 | #define expect_eq_uint(...) __expect_eq(uint, ##__VA_ARGS__) |
| 189 | #define expect_eq_bitmap(...) __expect_eq(bitmap, ##__VA_ARGS__) |
| 190 | #define expect_eq_pbl(...) __expect_eq(pbl, ##__VA_ARGS__) |
| 191 | #define expect_eq_u32_array(...) __expect_eq(u32_array, ##__VA_ARGS__) |
| 192 | #define expect_eq_clump8(...) __expect_eq(clump8, ##__VA_ARGS__) |
| 193 | #define expect_eq_str(...) __expect_eq(str, ##__VA_ARGS__) |
| 194 | |
| 195 | static void __init test_zero_clear(void) |
| 196 | { |
| 197 | DECLARE_BITMAP(bmap, 1024); |
| 198 | |
| 199 | /* Known way to set all bits */ |
| 200 | memset(bmap, 0xff, 128); |
| 201 | |
| 202 | expect_eq_pbl("0-22", bmap, 23); |
| 203 | expect_eq_pbl("0-1023", bmap, 1024); |
| 204 | |
| 205 | /* single-word bitmaps */ |
| 206 | bitmap_clear(bmap, 0, 9); |
| 207 | expect_eq_pbl("9-1023", bmap, 1024); |
| 208 | |
| 209 | bitmap_zero(bmap, 35); |
| 210 | expect_eq_pbl("64-1023", bmap, 1024); |
| 211 | |
| 212 | /* cross boundaries operations */ |
| 213 | bitmap_clear(bmap, 79, 19); |
| 214 | expect_eq_pbl("64-78,98-1023", bmap, 1024); |
| 215 | |
| 216 | bitmap_zero(bmap, 115); |
| 217 | expect_eq_pbl("128-1023", bmap, 1024); |
| 218 | |
| 219 | /* Zeroing entire area */ |
| 220 | bitmap_zero(bmap, 1024); |
| 221 | expect_eq_pbl("", bmap, 1024); |
| 222 | } |
| 223 | |
| 224 | static void __init test_find_nth_bit(void) |
| 225 | { |
| 226 | unsigned long b, bit, cnt = 0; |
| 227 | DECLARE_BITMAP(bmap, 64 * 3); |
| 228 | |
| 229 | bitmap_zero(bmap, 64 * 3); |
| 230 | __set_bit(10, bmap); |
| 231 | __set_bit(20, bmap); |
| 232 | __set_bit(30, bmap); |
| 233 | __set_bit(40, bmap); |
| 234 | __set_bit(50, bmap); |
| 235 | __set_bit(60, bmap); |
| 236 | __set_bit(80, bmap); |
| 237 | __set_bit(123, bmap); |
| 238 | |
| 239 | expect_eq_uint(10, find_nth_bit(bmap, 64 * 3, 0)); |
| 240 | expect_eq_uint(20, find_nth_bit(bmap, 64 * 3, 1)); |
| 241 | expect_eq_uint(30, find_nth_bit(bmap, 64 * 3, 2)); |
| 242 | expect_eq_uint(40, find_nth_bit(bmap, 64 * 3, 3)); |
| 243 | expect_eq_uint(50, find_nth_bit(bmap, 64 * 3, 4)); |
| 244 | expect_eq_uint(60, find_nth_bit(bmap, 64 * 3, 5)); |
| 245 | expect_eq_uint(80, find_nth_bit(bmap, 64 * 3, 6)); |
| 246 | expect_eq_uint(123, find_nth_bit(bmap, 64 * 3, 7)); |
| 247 | expect_eq_uint(64 * 3, find_nth_bit(bmap, 64 * 3, 8)); |
| 248 | |
| 249 | expect_eq_uint(10, find_nth_bit(bmap, 64 * 3 - 1, 0)); |
| 250 | expect_eq_uint(20, find_nth_bit(bmap, 64 * 3 - 1, 1)); |
| 251 | expect_eq_uint(30, find_nth_bit(bmap, 64 * 3 - 1, 2)); |
| 252 | expect_eq_uint(40, find_nth_bit(bmap, 64 * 3 - 1, 3)); |
| 253 | expect_eq_uint(50, find_nth_bit(bmap, 64 * 3 - 1, 4)); |
| 254 | expect_eq_uint(60, find_nth_bit(bmap, 64 * 3 - 1, 5)); |
| 255 | expect_eq_uint(80, find_nth_bit(bmap, 64 * 3 - 1, 6)); |
| 256 | expect_eq_uint(123, find_nth_bit(bmap, 64 * 3 - 1, 7)); |
| 257 | expect_eq_uint(64 * 3 - 1, find_nth_bit(bmap, 64 * 3 - 1, 8)); |
| 258 | |
| 259 | for_each_set_bit(bit, exp1, EXP1_IN_BITS) { |
| 260 | b = find_nth_bit(exp1, EXP1_IN_BITS, cnt++); |
| 261 | expect_eq_uint(b, bit); |
| 262 | } |
| 263 | } |
| 264 | |
| 265 | static void __init test_fill_set(void) |
| 266 | { |
| 267 | DECLARE_BITMAP(bmap, 1024); |
| 268 | |
| 269 | /* Known way to clear all bits */ |
| 270 | memset(bmap, 0x00, 128); |
| 271 | |
| 272 | expect_eq_pbl("", bmap, 23); |
| 273 | expect_eq_pbl("", bmap, 1024); |
| 274 | |
| 275 | /* single-word bitmaps */ |
| 276 | bitmap_set(bmap, 0, 9); |
| 277 | expect_eq_pbl("0-8", bmap, 1024); |
| 278 | |
| 279 | bitmap_fill(bmap, 35); |
| 280 | expect_eq_pbl("0-63", bmap, 1024); |
| 281 | |
| 282 | /* cross boundaries operations */ |
| 283 | bitmap_set(bmap, 79, 19); |
| 284 | expect_eq_pbl("0-63,79-97", bmap, 1024); |
| 285 | |
| 286 | bitmap_fill(bmap, 115); |
| 287 | expect_eq_pbl("0-127", bmap, 1024); |
| 288 | |
| 289 | /* Zeroing entire area */ |
| 290 | bitmap_fill(bmap, 1024); |
| 291 | expect_eq_pbl("0-1023", bmap, 1024); |
| 292 | } |
| 293 | |
| 294 | static void __init test_copy(void) |
| 295 | { |
| 296 | DECLARE_BITMAP(bmap1, 1024); |
| 297 | DECLARE_BITMAP(bmap2, 1024); |
| 298 | |
| 299 | bitmap_zero(bmap1, 1024); |
| 300 | bitmap_zero(bmap2, 1024); |
| 301 | |
| 302 | /* single-word bitmaps */ |
| 303 | bitmap_set(bmap1, 0, 19); |
| 304 | bitmap_copy(bmap2, bmap1, 23); |
| 305 | expect_eq_pbl("0-18", bmap2, 1024); |
| 306 | |
| 307 | bitmap_set(bmap2, 0, 23); |
| 308 | bitmap_copy(bmap2, bmap1, 23); |
| 309 | expect_eq_pbl("0-18", bmap2, 1024); |
| 310 | |
| 311 | /* multi-word bitmaps */ |
| 312 | bitmap_set(bmap1, 0, 109); |
| 313 | bitmap_copy(bmap2, bmap1, 1024); |
| 314 | expect_eq_pbl("0-108", bmap2, 1024); |
| 315 | |
| 316 | bitmap_fill(bmap2, 1024); |
| 317 | bitmap_copy(bmap2, bmap1, 1024); |
| 318 | expect_eq_pbl("0-108", bmap2, 1024); |
| 319 | |
| 320 | /* the following tests assume a 32- or 64-bit arch (even 128b |
| 321 | * if we care) |
| 322 | */ |
| 323 | |
| 324 | bitmap_fill(bmap2, 1024); |
| 325 | bitmap_copy(bmap2, bmap1, 109); /* ... but 0-padded til word length */ |
| 326 | expect_eq_pbl("0-108,128-1023", bmap2, 1024); |
| 327 | |
| 328 | bitmap_fill(bmap2, 1024); |
| 329 | bitmap_copy(bmap2, bmap1, 97); /* ... but aligned on word length */ |
| 330 | expect_eq_pbl("0-108,128-1023", bmap2, 1024); |
| 331 | } |
| 332 | |
| 333 | #define EXP2_IN_BITS (sizeof(exp2) * 8) |
| 334 | |
| 335 | static void __init test_replace(void) |
| 336 | { |
| 337 | unsigned int nbits = 64; |
| 338 | unsigned int nlongs = DIV_ROUND_UP(nbits, BITS_PER_LONG); |
| 339 | DECLARE_BITMAP(bmap, 1024); |
| 340 | |
| 341 | BUILD_BUG_ON(EXP2_IN_BITS < nbits * 2); |
| 342 | |
| 343 | bitmap_zero(bmap, 1024); |
| 344 | bitmap_replace(bmap, &exp2[0 * nlongs], &exp2[1 * nlongs], exp2_to_exp3_mask, nbits); |
| 345 | expect_eq_bitmap(bmap, exp3_0_1, nbits); |
| 346 | |
| 347 | bitmap_zero(bmap, 1024); |
| 348 | bitmap_replace(bmap, &exp2[1 * nlongs], &exp2[0 * nlongs], exp2_to_exp3_mask, nbits); |
| 349 | expect_eq_bitmap(bmap, exp3_1_0, nbits); |
| 350 | |
| 351 | bitmap_fill(bmap, 1024); |
| 352 | bitmap_replace(bmap, &exp2[0 * nlongs], &exp2[1 * nlongs], exp2_to_exp3_mask, nbits); |
| 353 | expect_eq_bitmap(bmap, exp3_0_1, nbits); |
| 354 | |
| 355 | bitmap_fill(bmap, 1024); |
| 356 | bitmap_replace(bmap, &exp2[1 * nlongs], &exp2[0 * nlongs], exp2_to_exp3_mask, nbits); |
| 357 | expect_eq_bitmap(bmap, exp3_1_0, nbits); |
| 358 | } |
| 359 | |
| 360 | #define PARSE_TIME 0x1 |
| 361 | #define NO_LEN 0x2 |
| 362 | |
| 363 | struct test_bitmap_parselist{ |
| 364 | const int errno; |
| 365 | const char *in; |
| 366 | const unsigned long *expected; |
| 367 | const int nbits; |
| 368 | const int flags; |
| 369 | }; |
| 370 | |
| 371 | static const struct test_bitmap_parselist parselist_tests[] __initconst = { |
| 372 | #define step (sizeof(u64) / sizeof(unsigned long)) |
| 373 | |
| 374 | {0, "0", &exp1[0], 8, 0}, |
| 375 | {0, "1", &exp1[1 * step], 8, 0}, |
| 376 | {0, "0-15", &exp1[2 * step], 32, 0}, |
| 377 | {0, "16-31", &exp1[3 * step], 32, 0}, |
| 378 | {0, "0-31:1/2", &exp1[4 * step], 32, 0}, |
| 379 | {0, "1-31:1/2", &exp1[5 * step], 32, 0}, |
| 380 | {0, "0-31:1/4", &exp1[6 * step], 32, 0}, |
| 381 | {0, "1-31:1/4", &exp1[7 * step], 32, 0}, |
| 382 | {0, "0-31:4/4", &exp1[8 * step], 32, 0}, |
| 383 | {0, "1-31:4/4", &exp1[9 * step], 32, 0}, |
| 384 | {0, "0-31:1/4,32-63:2/4", &exp1[10 * step], 64, 0}, |
| 385 | {0, "0-31:3/4,32-63:4/4", &exp1[11 * step], 64, 0}, |
| 386 | {0, " ,, 0-31:3/4 ,, 32-63:4/4 ,, ", &exp1[11 * step], 64, 0}, |
| 387 | |
| 388 | {0, "0-31:1/4,32-63:2/4,64-95:3/4,96-127:4/4", exp2, 128, 0}, |
| 389 | |
| 390 | {0, "0-2047:128/256", NULL, 2048, PARSE_TIME}, |
| 391 | |
| 392 | {0, "", &exp1[12 * step], 8, 0}, |
| 393 | {0, "\n", &exp1[12 * step], 8, 0}, |
| 394 | {0, ",, ,, , , ,", &exp1[12 * step], 8, 0}, |
| 395 | {0, " , ,, , , ", &exp1[12 * step], 8, 0}, |
| 396 | {0, " , ,, , , \n", &exp1[12 * step], 8, 0}, |
| 397 | |
| 398 | {0, "0-0", &exp1[0], 32, 0}, |
| 399 | {0, "1-1", &exp1[1 * step], 32, 0}, |
| 400 | {0, "15-15", &exp1[13 * step], 32, 0}, |
| 401 | {0, "31-31", &exp1[14 * step], 32, 0}, |
| 402 | |
| 403 | {0, "0-0:0/1", &exp1[12 * step], 32, 0}, |
| 404 | {0, "0-0:1/1", &exp1[0], 32, 0}, |
| 405 | {0, "0-0:1/31", &exp1[0], 32, 0}, |
| 406 | {0, "0-0:31/31", &exp1[0], 32, 0}, |
| 407 | {0, "1-1:1/1", &exp1[1 * step], 32, 0}, |
| 408 | {0, "0-15:16/31", &exp1[2 * step], 32, 0}, |
| 409 | {0, "15-15:1/2", &exp1[13 * step], 32, 0}, |
| 410 | {0, "15-15:31/31", &exp1[13 * step], 32, 0}, |
| 411 | {0, "15-31:1/31", &exp1[13 * step], 32, 0}, |
| 412 | {0, "16-31:16/31", &exp1[3 * step], 32, 0}, |
| 413 | {0, "31-31:31/31", &exp1[14 * step], 32, 0}, |
| 414 | |
| 415 | {0, "N-N", &exp1[14 * step], 32, 0}, |
| 416 | {0, "0-0:1/N", &exp1[0], 32, 0}, |
| 417 | {0, "0-0:N/N", &exp1[0], 32, 0}, |
| 418 | {0, "0-15:16/N", &exp1[2 * step], 32, 0}, |
| 419 | {0, "15-15:N/N", &exp1[13 * step], 32, 0}, |
| 420 | {0, "15-N:1/N", &exp1[13 * step], 32, 0}, |
| 421 | {0, "16-N:16/N", &exp1[3 * step], 32, 0}, |
| 422 | {0, "N-N:N/N", &exp1[14 * step], 32, 0}, |
| 423 | |
| 424 | {0, "0-N:1/3,1-N:1/3,2-N:1/3", &exp1[8 * step], 32, 0}, |
| 425 | {0, "0-31:1/3,1-31:1/3,2-31:1/3", &exp1[8 * step], 32, 0}, |
| 426 | {0, "1-10:8/12,8-31:24/29,0-31:0/3", &exp1[9 * step], 32, 0}, |
| 427 | |
| 428 | {0, "all", &exp1[8 * step], 32, 0}, |
| 429 | {0, "0, 1, all, ", &exp1[8 * step], 32, 0}, |
| 430 | {0, "all:1/2", &exp1[4 * step], 32, 0}, |
| 431 | {0, "ALL:1/2", &exp1[4 * step], 32, 0}, |
| 432 | {-EINVAL, "al", NULL, 8, 0}, |
| 433 | {-EINVAL, "alll", NULL, 8, 0}, |
| 434 | |
| 435 | {-EINVAL, "-1", NULL, 8, 0}, |
| 436 | {-EINVAL, "-0", NULL, 8, 0}, |
| 437 | {-EINVAL, "10-1", NULL, 8, 0}, |
| 438 | {-ERANGE, "8-8", NULL, 8, 0}, |
| 439 | {-ERANGE, "0-31", NULL, 8, 0}, |
| 440 | {-EINVAL, "0-31:", NULL, 32, 0}, |
| 441 | {-EINVAL, "0-31:0", NULL, 32, 0}, |
| 442 | {-EINVAL, "0-31:0/", NULL, 32, 0}, |
| 443 | {-EINVAL, "0-31:0/0", NULL, 32, 0}, |
| 444 | {-EINVAL, "0-31:1/0", NULL, 32, 0}, |
| 445 | {-EINVAL, "0-31:10/1", NULL, 32, 0}, |
| 446 | {-EOVERFLOW, "0-98765432123456789:10/1", NULL, 8, 0}, |
| 447 | |
| 448 | {-EINVAL, "a-31", NULL, 8, 0}, |
| 449 | {-EINVAL, "0-a1", NULL, 8, 0}, |
| 450 | {-EINVAL, "a-31:10/1", NULL, 8, 0}, |
| 451 | {-EINVAL, "0-31:a/1", NULL, 8, 0}, |
| 452 | {-EINVAL, "0-\n", NULL, 8, 0}, |
| 453 | |
| 454 | }; |
| 455 | |
| 456 | static void __init test_bitmap_parselist(void) |
| 457 | { |
| 458 | int i; |
| 459 | int err; |
| 460 | ktime_t time; |
| 461 | DECLARE_BITMAP(bmap, 2048); |
| 462 | |
| 463 | for (i = 0; i < ARRAY_SIZE(parselist_tests); i++) { |
| 464 | #define ptest parselist_tests[i] |
| 465 | |
| 466 | time = ktime_get(); |
| 467 | err = bitmap_parselist(ptest.in, bmap, ptest.nbits); |
| 468 | time = ktime_get() - time; |
| 469 | |
| 470 | if (err != ptest.errno) { |
| 471 | pr_err("parselist: %d: input is %s, errno is %d, expected %d\n", |
| 472 | i, ptest.in, err, ptest.errno); |
| 473 | continue; |
| 474 | } |
| 475 | |
| 476 | if (!err && ptest.expected |
| 477 | && !__bitmap_equal(bmap, ptest.expected, ptest.nbits)) { |
| 478 | pr_err("parselist: %d: input is %s, result is 0x%lx, expected 0x%lx\n", |
| 479 | i, ptest.in, bmap[0], |
| 480 | *ptest.expected); |
| 481 | continue; |
| 482 | } |
| 483 | |
| 484 | if (ptest.flags & PARSE_TIME) |
| 485 | pr_err("parselist: %d: input is '%s' OK, Time: %llu\n", |
| 486 | i, ptest.in, time); |
| 487 | |
| 488 | #undef ptest |
| 489 | } |
| 490 | } |
| 491 | |
| 492 | static void __init test_bitmap_printlist(void) |
| 493 | { |
| 494 | unsigned long *bmap = kmalloc(PAGE_SIZE, GFP_KERNEL); |
| 495 | char *buf = kmalloc(PAGE_SIZE, GFP_KERNEL); |
| 496 | char expected[256]; |
| 497 | int ret, slen; |
| 498 | ktime_t time; |
| 499 | |
| 500 | if (!buf || !bmap) |
| 501 | goto out; |
| 502 | |
| 503 | memset(bmap, -1, PAGE_SIZE); |
| 504 | slen = snprintf(expected, 256, "0-%ld", PAGE_SIZE * 8 - 1); |
| 505 | if (slen < 0) |
| 506 | goto out; |
| 507 | |
| 508 | time = ktime_get(); |
| 509 | ret = bitmap_print_to_pagebuf(true, buf, bmap, PAGE_SIZE * 8); |
| 510 | time = ktime_get() - time; |
| 511 | |
| 512 | if (ret != slen + 1) { |
| 513 | pr_err("bitmap_print_to_pagebuf: result is %d, expected %d\n", ret, slen); |
| 514 | goto out; |
| 515 | } |
| 516 | |
| 517 | if (strncmp(buf, expected, slen)) { |
| 518 | pr_err("bitmap_print_to_pagebuf: result is %s, expected %s\n", buf, expected); |
| 519 | goto out; |
| 520 | } |
| 521 | |
| 522 | pr_err("bitmap_print_to_pagebuf: input is '%s', Time: %llu\n", buf, time); |
| 523 | out: |
| 524 | kfree(buf); |
| 525 | kfree(bmap); |
| 526 | } |
| 527 | |
| 528 | static const unsigned long parse_test[] __initconst = { |
| 529 | BITMAP_FROM_U64(0), |
| 530 | BITMAP_FROM_U64(1), |
| 531 | BITMAP_FROM_U64(0xdeadbeef), |
| 532 | BITMAP_FROM_U64(0x100000000ULL), |
| 533 | }; |
| 534 | |
| 535 | static const unsigned long parse_test2[] __initconst = { |
| 536 | BITMAP_FROM_U64(0x100000000ULL), BITMAP_FROM_U64(0xdeadbeef), |
| 537 | BITMAP_FROM_U64(0x100000000ULL), BITMAP_FROM_U64(0xbaadf00ddeadbeef), |
| 538 | BITMAP_FROM_U64(0x100000000ULL), BITMAP_FROM_U64(0x0badf00ddeadbeef), |
| 539 | }; |
| 540 | |
| 541 | static const struct test_bitmap_parselist parse_tests[] __initconst = { |
| 542 | {0, "", &parse_test[0 * step], 32, 0}, |
| 543 | {0, " ", &parse_test[0 * step], 32, 0}, |
| 544 | {0, "0", &parse_test[0 * step], 32, 0}, |
| 545 | {0, "0\n", &parse_test[0 * step], 32, 0}, |
| 546 | {0, "1", &parse_test[1 * step], 32, 0}, |
| 547 | {0, "deadbeef", &parse_test[2 * step], 32, 0}, |
| 548 | {0, "1,0", &parse_test[3 * step], 33, 0}, |
| 549 | {0, "deadbeef,\n,0,1", &parse_test[2 * step], 96, 0}, |
| 550 | |
| 551 | {0, "deadbeef,1,0", &parse_test2[0 * 2 * step], 96, 0}, |
| 552 | {0, "baadf00d,deadbeef,1,0", &parse_test2[1 * 2 * step], 128, 0}, |
| 553 | {0, "badf00d,deadbeef,1,0", &parse_test2[2 * 2 * step], 124, 0}, |
| 554 | {0, "badf00d,deadbeef,1,0", &parse_test2[2 * 2 * step], 124, NO_LEN}, |
| 555 | {0, " badf00d,deadbeef,1,0 ", &parse_test2[2 * 2 * step], 124, 0}, |
| 556 | {0, " , badf00d,deadbeef,1,0 , ", &parse_test2[2 * 2 * step], 124, 0}, |
| 557 | {0, " , badf00d, ,, ,,deadbeef,1,0 , ", &parse_test2[2 * 2 * step], 124, 0}, |
| 558 | |
| 559 | {-EINVAL, "goodfood,deadbeef,1,0", NULL, 128, 0}, |
| 560 | {-EOVERFLOW, "3,0", NULL, 33, 0}, |
| 561 | {-EOVERFLOW, "123badf00d,deadbeef,1,0", NULL, 128, 0}, |
| 562 | {-EOVERFLOW, "badf00d,deadbeef,1,0", NULL, 90, 0}, |
| 563 | {-EOVERFLOW, "fbadf00d,deadbeef,1,0", NULL, 95, 0}, |
| 564 | {-EOVERFLOW, "badf00d,deadbeef,1,0", NULL, 100, 0}, |
| 565 | #undef step |
| 566 | }; |
| 567 | |
| 568 | static void __init test_bitmap_parse(void) |
| 569 | { |
| 570 | int i; |
| 571 | int err; |
| 572 | ktime_t time; |
| 573 | DECLARE_BITMAP(bmap, 2048); |
| 574 | |
| 575 | for (i = 0; i < ARRAY_SIZE(parse_tests); i++) { |
| 576 | struct test_bitmap_parselist test = parse_tests[i]; |
| 577 | size_t len = test.flags & NO_LEN ? UINT_MAX : strlen(test.in); |
| 578 | |
| 579 | time = ktime_get(); |
| 580 | err = bitmap_parse(test.in, len, bmap, test.nbits); |
| 581 | time = ktime_get() - time; |
| 582 | |
| 583 | if (err != test.errno) { |
| 584 | pr_err("parse: %d: input is %s, errno is %d, expected %d\n", |
| 585 | i, test.in, err, test.errno); |
| 586 | continue; |
| 587 | } |
| 588 | |
| 589 | if (!err && test.expected |
| 590 | && !__bitmap_equal(bmap, test.expected, test.nbits)) { |
| 591 | pr_err("parse: %d: input is %s, result is 0x%lx, expected 0x%lx\n", |
| 592 | i, test.in, bmap[0], |
| 593 | *test.expected); |
| 594 | continue; |
| 595 | } |
| 596 | |
| 597 | if (test.flags & PARSE_TIME) |
| 598 | pr_err("parse: %d: input is '%s' OK, Time: %llu\n", |
| 599 | i, test.in, time); |
| 600 | } |
| 601 | } |
| 602 | |
| 603 | static void __init test_bitmap_arr32(void) |
| 604 | { |
| 605 | unsigned int nbits, next_bit; |
| 606 | u32 arr[EXP1_IN_BITS / 32]; |
| 607 | DECLARE_BITMAP(bmap2, EXP1_IN_BITS); |
| 608 | |
| 609 | memset(arr, 0xa5, sizeof(arr)); |
| 610 | |
| 611 | for (nbits = 0; nbits < EXP1_IN_BITS; ++nbits) { |
| 612 | bitmap_to_arr32(arr, exp1, nbits); |
| 613 | bitmap_from_arr32(bmap2, arr, nbits); |
| 614 | expect_eq_bitmap(bmap2, exp1, nbits); |
| 615 | |
| 616 | next_bit = find_next_bit(bmap2, |
| 617 | round_up(nbits, BITS_PER_LONG), nbits); |
| 618 | if (next_bit < round_up(nbits, BITS_PER_LONG)) |
| 619 | pr_err("bitmap_copy_arr32(nbits == %d:" |
| 620 | " tail is not safely cleared: %d\n", |
| 621 | nbits, next_bit); |
| 622 | |
| 623 | if (nbits < EXP1_IN_BITS - 32) |
| 624 | expect_eq_uint(arr[DIV_ROUND_UP(nbits, 32)], |
| 625 | 0xa5a5a5a5); |
| 626 | } |
| 627 | } |
| 628 | |
| 629 | static void __init test_bitmap_arr64(void) |
| 630 | { |
| 631 | unsigned int nbits, next_bit; |
| 632 | u64 arr[EXP1_IN_BITS / 64]; |
| 633 | DECLARE_BITMAP(bmap2, EXP1_IN_BITS); |
| 634 | |
| 635 | memset(arr, 0xa5, sizeof(arr)); |
| 636 | |
| 637 | for (nbits = 0; nbits < EXP1_IN_BITS; ++nbits) { |
| 638 | memset(bmap2, 0xff, sizeof(arr)); |
| 639 | bitmap_to_arr64(arr, exp1, nbits); |
| 640 | bitmap_from_arr64(bmap2, arr, nbits); |
| 641 | expect_eq_bitmap(bmap2, exp1, nbits); |
| 642 | |
| 643 | next_bit = find_next_bit(bmap2, round_up(nbits, BITS_PER_LONG), nbits); |
| 644 | if (next_bit < round_up(nbits, BITS_PER_LONG)) |
| 645 | pr_err("bitmap_copy_arr64(nbits == %d:" |
| 646 | " tail is not safely cleared: %d\n", nbits, next_bit); |
| 647 | |
| 648 | if ((nbits % 64) && |
| 649 | (arr[(nbits - 1) / 64] & ~GENMASK_ULL((nbits - 1) % 64, 0))) |
| 650 | pr_err("bitmap_to_arr64(nbits == %d): tail is not safely cleared: 0x%016llx (must be 0x%016llx)\n", |
| 651 | nbits, arr[(nbits - 1) / 64], |
| 652 | GENMASK_ULL((nbits - 1) % 64, 0)); |
| 653 | |
| 654 | if (nbits < EXP1_IN_BITS - 64) |
| 655 | expect_eq_uint(arr[DIV_ROUND_UP(nbits, 64)], 0xa5a5a5a5); |
| 656 | } |
| 657 | } |
| 658 | |
| 659 | static void noinline __init test_mem_optimisations(void) |
| 660 | { |
| 661 | DECLARE_BITMAP(bmap1, 1024); |
| 662 | DECLARE_BITMAP(bmap2, 1024); |
| 663 | unsigned int start, nbits; |
| 664 | |
| 665 | for (start = 0; start < 1024; start += 8) { |
| 666 | for (nbits = 0; nbits < 1024 - start; nbits += 8) { |
| 667 | memset(bmap1, 0x5a, sizeof(bmap1)); |
| 668 | memset(bmap2, 0x5a, sizeof(bmap2)); |
| 669 | |
| 670 | bitmap_set(bmap1, start, nbits); |
| 671 | __bitmap_set(bmap2, start, nbits); |
| 672 | if (!bitmap_equal(bmap1, bmap2, 1024)) { |
| 673 | printk("set not equal %d %d\n", start, nbits); |
| 674 | failed_tests++; |
| 675 | } |
| 676 | if (!__bitmap_equal(bmap1, bmap2, 1024)) { |
| 677 | printk("set not __equal %d %d\n", start, nbits); |
| 678 | failed_tests++; |
| 679 | } |
| 680 | |
| 681 | bitmap_clear(bmap1, start, nbits); |
| 682 | __bitmap_clear(bmap2, start, nbits); |
| 683 | if (!bitmap_equal(bmap1, bmap2, 1024)) { |
| 684 | printk("clear not equal %d %d\n", start, nbits); |
| 685 | failed_tests++; |
| 686 | } |
| 687 | if (!__bitmap_equal(bmap1, bmap2, 1024)) { |
| 688 | printk("clear not __equal %d %d\n", start, |
| 689 | nbits); |
| 690 | failed_tests++; |
| 691 | } |
| 692 | } |
| 693 | } |
| 694 | } |
| 695 | |
| 696 | static const unsigned char clump_exp[] __initconst = { |
| 697 | 0x01, /* 1 bit set */ |
| 698 | 0x02, /* non-edge 1 bit set */ |
| 699 | 0x00, /* zero bits set */ |
| 700 | 0x38, /* 3 bits set across 4-bit boundary */ |
| 701 | 0x38, /* Repeated clump */ |
| 702 | 0x0F, /* 4 bits set */ |
| 703 | 0xFF, /* all bits set */ |
| 704 | 0x05, /* non-adjacent 2 bits set */ |
| 705 | }; |
| 706 | |
| 707 | static void __init test_for_each_set_clump8(void) |
| 708 | { |
| 709 | #define CLUMP_EXP_NUMBITS 64 |
| 710 | DECLARE_BITMAP(bits, CLUMP_EXP_NUMBITS); |
| 711 | unsigned int start; |
| 712 | unsigned long clump; |
| 713 | |
| 714 | /* set bitmap to test case */ |
| 715 | bitmap_zero(bits, CLUMP_EXP_NUMBITS); |
| 716 | bitmap_set(bits, 0, 1); /* 0x01 */ |
| 717 | bitmap_set(bits, 9, 1); /* 0x02 */ |
| 718 | bitmap_set(bits, 27, 3); /* 0x28 */ |
| 719 | bitmap_set(bits, 35, 3); /* 0x28 */ |
| 720 | bitmap_set(bits, 40, 4); /* 0x0F */ |
| 721 | bitmap_set(bits, 48, 8); /* 0xFF */ |
| 722 | bitmap_set(bits, 56, 1); /* 0x05 - part 1 */ |
| 723 | bitmap_set(bits, 58, 1); /* 0x05 - part 2 */ |
| 724 | |
| 725 | for_each_set_clump8(start, clump, bits, CLUMP_EXP_NUMBITS) |
| 726 | expect_eq_clump8(start, CLUMP_EXP_NUMBITS, clump_exp, &clump); |
| 727 | } |
| 728 | |
| 729 | static void __init test_for_each_set_bit_wrap(void) |
| 730 | { |
| 731 | DECLARE_BITMAP(orig, 500); |
| 732 | DECLARE_BITMAP(copy, 500); |
| 733 | unsigned int wr, bit; |
| 734 | |
| 735 | bitmap_zero(orig, 500); |
| 736 | |
| 737 | /* Set individual bits */ |
| 738 | for (bit = 0; bit < 500; bit += 10) |
| 739 | bitmap_set(orig, bit, 1); |
| 740 | |
| 741 | /* Set range of bits */ |
| 742 | bitmap_set(orig, 100, 50); |
| 743 | |
| 744 | for (wr = 0; wr < 500; wr++) { |
| 745 | bitmap_zero(copy, 500); |
| 746 | |
| 747 | for_each_set_bit_wrap(bit, orig, 500, wr) |
| 748 | bitmap_set(copy, bit, 1); |
| 749 | |
| 750 | expect_eq_bitmap(orig, copy, 500); |
| 751 | } |
| 752 | } |
| 753 | |
| 754 | static void __init test_for_each_set_bit(void) |
| 755 | { |
| 756 | DECLARE_BITMAP(orig, 500); |
| 757 | DECLARE_BITMAP(copy, 500); |
| 758 | unsigned int bit; |
| 759 | |
| 760 | bitmap_zero(orig, 500); |
| 761 | bitmap_zero(copy, 500); |
| 762 | |
| 763 | /* Set individual bits */ |
| 764 | for (bit = 0; bit < 500; bit += 10) |
| 765 | bitmap_set(orig, bit, 1); |
| 766 | |
| 767 | /* Set range of bits */ |
| 768 | bitmap_set(orig, 100, 50); |
| 769 | |
| 770 | for_each_set_bit(bit, orig, 500) |
| 771 | bitmap_set(copy, bit, 1); |
| 772 | |
| 773 | expect_eq_bitmap(orig, copy, 500); |
| 774 | } |
| 775 | |
| 776 | static void __init test_for_each_set_bit_from(void) |
| 777 | { |
| 778 | DECLARE_BITMAP(orig, 500); |
| 779 | DECLARE_BITMAP(copy, 500); |
| 780 | unsigned int wr, bit; |
| 781 | |
| 782 | bitmap_zero(orig, 500); |
| 783 | |
| 784 | /* Set individual bits */ |
| 785 | for (bit = 0; bit < 500; bit += 10) |
| 786 | bitmap_set(orig, bit, 1); |
| 787 | |
| 788 | /* Set range of bits */ |
| 789 | bitmap_set(orig, 100, 50); |
| 790 | |
| 791 | for (wr = 0; wr < 500; wr++) { |
| 792 | DECLARE_BITMAP(tmp, 500); |
| 793 | |
| 794 | bitmap_zero(copy, 500); |
| 795 | bit = wr; |
| 796 | |
| 797 | for_each_set_bit_from(bit, orig, 500) |
| 798 | bitmap_set(copy, bit, 1); |
| 799 | |
| 800 | bitmap_copy(tmp, orig, 500); |
| 801 | bitmap_clear(tmp, 0, wr); |
| 802 | expect_eq_bitmap(tmp, copy, 500); |
| 803 | } |
| 804 | } |
| 805 | |
| 806 | static void __init test_for_each_clear_bit(void) |
| 807 | { |
| 808 | DECLARE_BITMAP(orig, 500); |
| 809 | DECLARE_BITMAP(copy, 500); |
| 810 | unsigned int bit; |
| 811 | |
| 812 | bitmap_fill(orig, 500); |
| 813 | bitmap_fill(copy, 500); |
| 814 | |
| 815 | /* Set individual bits */ |
| 816 | for (bit = 0; bit < 500; bit += 10) |
| 817 | bitmap_clear(orig, bit, 1); |
| 818 | |
| 819 | /* Set range of bits */ |
| 820 | bitmap_clear(orig, 100, 50); |
| 821 | |
| 822 | for_each_clear_bit(bit, orig, 500) |
| 823 | bitmap_clear(copy, bit, 1); |
| 824 | |
| 825 | expect_eq_bitmap(orig, copy, 500); |
| 826 | } |
| 827 | |
| 828 | static void __init test_for_each_clear_bit_from(void) |
| 829 | { |
| 830 | DECLARE_BITMAP(orig, 500); |
| 831 | DECLARE_BITMAP(copy, 500); |
| 832 | unsigned int wr, bit; |
| 833 | |
| 834 | bitmap_fill(orig, 500); |
| 835 | |
| 836 | /* Set individual bits */ |
| 837 | for (bit = 0; bit < 500; bit += 10) |
| 838 | bitmap_clear(orig, bit, 1); |
| 839 | |
| 840 | /* Set range of bits */ |
| 841 | bitmap_clear(orig, 100, 50); |
| 842 | |
| 843 | for (wr = 0; wr < 500; wr++) { |
| 844 | DECLARE_BITMAP(tmp, 500); |
| 845 | |
| 846 | bitmap_fill(copy, 500); |
| 847 | bit = wr; |
| 848 | |
| 849 | for_each_clear_bit_from(bit, orig, 500) |
| 850 | bitmap_clear(copy, bit, 1); |
| 851 | |
| 852 | bitmap_copy(tmp, orig, 500); |
| 853 | bitmap_set(tmp, 0, wr); |
| 854 | expect_eq_bitmap(tmp, copy, 500); |
| 855 | } |
| 856 | } |
| 857 | |
| 858 | static void __init test_for_each_set_bitrange(void) |
| 859 | { |
| 860 | DECLARE_BITMAP(orig, 500); |
| 861 | DECLARE_BITMAP(copy, 500); |
| 862 | unsigned int s, e; |
| 863 | |
| 864 | bitmap_zero(orig, 500); |
| 865 | bitmap_zero(copy, 500); |
| 866 | |
| 867 | /* Set individual bits */ |
| 868 | for (s = 0; s < 500; s += 10) |
| 869 | bitmap_set(orig, s, 1); |
| 870 | |
| 871 | /* Set range of bits */ |
| 872 | bitmap_set(orig, 100, 50); |
| 873 | |
| 874 | for_each_set_bitrange(s, e, orig, 500) |
| 875 | bitmap_set(copy, s, e-s); |
| 876 | |
| 877 | expect_eq_bitmap(orig, copy, 500); |
| 878 | } |
| 879 | |
| 880 | static void __init test_for_each_clear_bitrange(void) |
| 881 | { |
| 882 | DECLARE_BITMAP(orig, 500); |
| 883 | DECLARE_BITMAP(copy, 500); |
| 884 | unsigned int s, e; |
| 885 | |
| 886 | bitmap_fill(orig, 500); |
| 887 | bitmap_fill(copy, 500); |
| 888 | |
| 889 | /* Set individual bits */ |
| 890 | for (s = 0; s < 500; s += 10) |
| 891 | bitmap_clear(orig, s, 1); |
| 892 | |
| 893 | /* Set range of bits */ |
| 894 | bitmap_clear(orig, 100, 50); |
| 895 | |
| 896 | for_each_clear_bitrange(s, e, orig, 500) |
| 897 | bitmap_clear(copy, s, e-s); |
| 898 | |
| 899 | expect_eq_bitmap(orig, copy, 500); |
| 900 | } |
| 901 | |
| 902 | static void __init test_for_each_set_bitrange_from(void) |
| 903 | { |
| 904 | DECLARE_BITMAP(orig, 500); |
| 905 | DECLARE_BITMAP(copy, 500); |
| 906 | unsigned int wr, s, e; |
| 907 | |
| 908 | bitmap_zero(orig, 500); |
| 909 | |
| 910 | /* Set individual bits */ |
| 911 | for (s = 0; s < 500; s += 10) |
| 912 | bitmap_set(orig, s, 1); |
| 913 | |
| 914 | /* Set range of bits */ |
| 915 | bitmap_set(orig, 100, 50); |
| 916 | |
| 917 | for (wr = 0; wr < 500; wr++) { |
| 918 | DECLARE_BITMAP(tmp, 500); |
| 919 | |
| 920 | bitmap_zero(copy, 500); |
| 921 | s = wr; |
| 922 | |
| 923 | for_each_set_bitrange_from(s, e, orig, 500) |
| 924 | bitmap_set(copy, s, e - s); |
| 925 | |
| 926 | bitmap_copy(tmp, orig, 500); |
| 927 | bitmap_clear(tmp, 0, wr); |
| 928 | expect_eq_bitmap(tmp, copy, 500); |
| 929 | } |
| 930 | } |
| 931 | |
| 932 | static void __init test_for_each_clear_bitrange_from(void) |
| 933 | { |
| 934 | DECLARE_BITMAP(orig, 500); |
| 935 | DECLARE_BITMAP(copy, 500); |
| 936 | unsigned int wr, s, e; |
| 937 | |
| 938 | bitmap_fill(orig, 500); |
| 939 | |
| 940 | /* Set individual bits */ |
| 941 | for (s = 0; s < 500; s += 10) |
| 942 | bitmap_clear(orig, s, 1); |
| 943 | |
| 944 | /* Set range of bits */ |
| 945 | bitmap_set(orig, 100, 50); |
| 946 | |
| 947 | for (wr = 0; wr < 500; wr++) { |
| 948 | DECLARE_BITMAP(tmp, 500); |
| 949 | |
| 950 | bitmap_fill(copy, 500); |
| 951 | s = wr; |
| 952 | |
| 953 | for_each_clear_bitrange_from(s, e, orig, 500) |
| 954 | bitmap_clear(copy, s, e - s); |
| 955 | |
| 956 | bitmap_copy(tmp, orig, 500); |
| 957 | bitmap_set(tmp, 0, wr); |
| 958 | expect_eq_bitmap(tmp, copy, 500); |
| 959 | } |
| 960 | } |
| 961 | |
| 962 | struct test_bitmap_cut { |
| 963 | unsigned int first; |
| 964 | unsigned int cut; |
| 965 | unsigned int nbits; |
| 966 | unsigned long in[4]; |
| 967 | unsigned long expected[4]; |
| 968 | }; |
| 969 | |
| 970 | static struct test_bitmap_cut test_cut[] = { |
| 971 | { 0, 0, 8, { 0x0000000aUL, }, { 0x0000000aUL, }, }, |
| 972 | { 0, 0, 32, { 0xdadadeadUL, }, { 0xdadadeadUL, }, }, |
| 973 | { 0, 3, 8, { 0x000000aaUL, }, { 0x00000015UL, }, }, |
| 974 | { 3, 3, 8, { 0x000000aaUL, }, { 0x00000012UL, }, }, |
| 975 | { 0, 1, 32, { 0xa5a5a5a5UL, }, { 0x52d2d2d2UL, }, }, |
| 976 | { 0, 8, 32, { 0xdeadc0deUL, }, { 0x00deadc0UL, }, }, |
| 977 | { 1, 1, 32, { 0x5a5a5a5aUL, }, { 0x2d2d2d2cUL, }, }, |
| 978 | { 0, 15, 32, { 0xa5a5a5a5UL, }, { 0x00014b4bUL, }, }, |
| 979 | { 0, 16, 32, { 0xa5a5a5a5UL, }, { 0x0000a5a5UL, }, }, |
| 980 | { 15, 15, 32, { 0xa5a5a5a5UL, }, { 0x000125a5UL, }, }, |
| 981 | { 15, 16, 32, { 0xa5a5a5a5UL, }, { 0x0000a5a5UL, }, }, |
| 982 | { 16, 15, 32, { 0xa5a5a5a5UL, }, { 0x0001a5a5UL, }, }, |
| 983 | |
| 984 | { BITS_PER_LONG, BITS_PER_LONG, BITS_PER_LONG, |
| 985 | { 0xa5a5a5a5UL, 0xa5a5a5a5UL, }, |
| 986 | { 0xa5a5a5a5UL, 0xa5a5a5a5UL, }, |
| 987 | }, |
| 988 | { 1, BITS_PER_LONG - 1, BITS_PER_LONG, |
| 989 | { 0xa5a5a5a5UL, 0xa5a5a5a5UL, }, |
| 990 | { 0x00000001UL, 0x00000001UL, }, |
| 991 | }, |
| 992 | |
| 993 | { 0, BITS_PER_LONG * 2, BITS_PER_LONG * 2 + 1, |
| 994 | { 0xa5a5a5a5UL, 0x00000001UL, 0x00000001UL, 0x00000001UL }, |
| 995 | { 0x00000001UL, }, |
| 996 | }, |
| 997 | { 16, BITS_PER_LONG * 2 + 1, BITS_PER_LONG * 2 + 1 + 16, |
| 998 | { 0x0000ffffUL, 0x5a5a5a5aUL, 0x5a5a5a5aUL, 0x5a5a5a5aUL }, |
| 999 | { 0x2d2dffffUL, }, |
| 1000 | }, |
| 1001 | }; |
| 1002 | |
| 1003 | static void __init test_bitmap_cut(void) |
| 1004 | { |
| 1005 | unsigned long b[5], *in = &b[1], *out = &b[0]; /* Partial overlap */ |
| 1006 | int i; |
| 1007 | |
| 1008 | for (i = 0; i < ARRAY_SIZE(test_cut); i++) { |
| 1009 | struct test_bitmap_cut *t = &test_cut[i]; |
| 1010 | |
| 1011 | memcpy(in, t->in, sizeof(t->in)); |
| 1012 | |
| 1013 | bitmap_cut(out, in, t->first, t->cut, t->nbits); |
| 1014 | |
| 1015 | expect_eq_bitmap(t->expected, out, t->nbits); |
| 1016 | } |
| 1017 | } |
| 1018 | |
| 1019 | struct test_bitmap_print { |
| 1020 | const unsigned long *bitmap; |
| 1021 | unsigned long nbits; |
| 1022 | const char *mask; |
| 1023 | const char *list; |
| 1024 | }; |
| 1025 | |
| 1026 | static const unsigned long small_bitmap[] __initconst = { |
| 1027 | BITMAP_FROM_U64(0x3333333311111111ULL), |
| 1028 | }; |
| 1029 | |
| 1030 | static const char small_mask[] __initconst = "33333333,11111111\n"; |
| 1031 | static const char small_list[] __initconst = "0,4,8,12,16,20,24,28,32-33,36-37,40-41,44-45,48-49,52-53,56-57,60-61\n"; |
| 1032 | |
| 1033 | static const unsigned long large_bitmap[] __initconst = { |
| 1034 | BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL), |
| 1035 | BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL), |
| 1036 | BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL), |
| 1037 | BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL), |
| 1038 | BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL), |
| 1039 | BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL), |
| 1040 | BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL), |
| 1041 | BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL), |
| 1042 | BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL), |
| 1043 | BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL), |
| 1044 | BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL), |
| 1045 | BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL), |
| 1046 | BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL), |
| 1047 | BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL), |
| 1048 | BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL), |
| 1049 | BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL), |
| 1050 | BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL), |
| 1051 | BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL), |
| 1052 | BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL), |
| 1053 | BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL), |
| 1054 | }; |
| 1055 | |
| 1056 | static const char large_mask[] __initconst = "33333333,11111111,33333333,11111111," |
| 1057 | "33333333,11111111,33333333,11111111," |
| 1058 | "33333333,11111111,33333333,11111111," |
| 1059 | "33333333,11111111,33333333,11111111," |
| 1060 | "33333333,11111111,33333333,11111111," |
| 1061 | "33333333,11111111,33333333,11111111," |
| 1062 | "33333333,11111111,33333333,11111111," |
| 1063 | "33333333,11111111,33333333,11111111," |
| 1064 | "33333333,11111111,33333333,11111111," |
| 1065 | "33333333,11111111,33333333,11111111," |
| 1066 | "33333333,11111111,33333333,11111111," |
| 1067 | "33333333,11111111,33333333,11111111," |
| 1068 | "33333333,11111111,33333333,11111111," |
| 1069 | "33333333,11111111,33333333,11111111," |
| 1070 | "33333333,11111111,33333333,11111111," |
| 1071 | "33333333,11111111,33333333,11111111," |
| 1072 | "33333333,11111111,33333333,11111111," |
| 1073 | "33333333,11111111,33333333,11111111," |
| 1074 | "33333333,11111111,33333333,11111111," |
| 1075 | "33333333,11111111,33333333,11111111\n"; |
| 1076 | |
| 1077 | static const char large_list[] __initconst = /* more than 4KB */ |
| 1078 | "0,4,8,12,16,20,24,28,32-33,36-37,40-41,44-45,48-49,52-53,56-57,60-61,64,68,72,76,80,84,88,92,96-97,100-101,104-1" |
| 1079 | "05,108-109,112-113,116-117,120-121,124-125,128,132,136,140,144,148,152,156,160-161,164-165,168-169,172-173,176-1" |
| 1080 | "77,180-181,184-185,188-189,192,196,200,204,208,212,216,220,224-225,228-229,232-233,236-237,240-241,244-245,248-2" |
| 1081 | "49,252-253,256,260,264,268,272,276,280,284,288-289,292-293,296-297,300-301,304-305,308-309,312-313,316-317,320,3" |
| 1082 | "24,328,332,336,340,344,348,352-353,356-357,360-361,364-365,368-369,372-373,376-377,380-381,384,388,392,396,400,4" |
| 1083 | "04,408,412,416-417,420-421,424-425,428-429,432-433,436-437,440-441,444-445,448,452,456,460,464,468,472,476,480-4" |
| 1084 | "81,484-485,488-489,492-493,496-497,500-501,504-505,508-509,512,516,520,524,528,532,536,540,544-545,548-549,552-5" |
| 1085 | "53,556-557,560-561,564-565,568-569,572-573,576,580,584,588,592,596,600,604,608-609,612-613,616-617,620-621,624-6" |
| 1086 | "25,628-629,632-633,636-637,640,644,648,652,656,660,664,668,672-673,676-677,680-681,684-685,688-689,692-693,696-6" |
| 1087 | "97,700-701,704,708,712,716,720,724,728,732,736-737,740-741,744-745,748-749,752-753,756-757,760-761,764-765,768,7" |
| 1088 | "72,776,780,784,788,792,796,800-801,804-805,808-809,812-813,816-817,820-821,824-825,828-829,832,836,840,844,848,8" |
| 1089 | "52,856,860,864-865,868-869,872-873,876-877,880-881,884-885,888-889,892-893,896,900,904,908,912,916,920,924,928-9" |
| 1090 | "29,932-933,936-937,940-941,944-945,948-949,952-953,956-957,960,964,968,972,976,980,984,988,992-993,996-997,1000-" |
| 1091 | "1001,1004-1005,1008-1009,1012-1013,1016-1017,1020-1021,1024,1028,1032,1036,1040,1044,1048,1052,1056-1057,1060-10" |
| 1092 | "61,1064-1065,1068-1069,1072-1073,1076-1077,1080-1081,1084-1085,1088,1092,1096,1100,1104,1108,1112,1116,1120-1121" |
| 1093 | ",1124-1125,1128-1129,1132-1133,1136-1137,1140-1141,1144-1145,1148-1149,1152,1156,1160,1164,1168,1172,1176,1180,1" |
| 1094 | "184-1185,1188-1189,1192-1193,1196-1197,1200-1201,1204-1205,1208-1209,1212-1213,1216,1220,1224,1228,1232,1236,124" |
| 1095 | "0,1244,1248-1249,1252-1253,1256-1257,1260-1261,1264-1265,1268-1269,1272-1273,1276-1277,1280,1284,1288,1292,1296," |
| 1096 | "1300,1304,1308,1312-1313,1316-1317,1320-1321,1324-1325,1328-1329,1332-1333,1336-1337,1340-1341,1344,1348,1352,13" |
| 1097 | "56,1360,1364,1368,1372,1376-1377,1380-1381,1384-1385,1388-1389,1392-1393,1396-1397,1400-1401,1404-1405,1408,1412" |
| 1098 | ",1416,1420,1424,1428,1432,1436,1440-1441,1444-1445,1448-1449,1452-1453,1456-1457,1460-1461,1464-1465,1468-1469,1" |
| 1099 | "472,1476,1480,1484,1488,1492,1496,1500,1504-1505,1508-1509,1512-1513,1516-1517,1520-1521,1524-1525,1528-1529,153" |
| 1100 | "2-1533,1536,1540,1544,1548,1552,1556,1560,1564,1568-1569,1572-1573,1576-1577,1580-1581,1584-1585,1588-1589,1592-" |
| 1101 | "1593,1596-1597,1600,1604,1608,1612,1616,1620,1624,1628,1632-1633,1636-1637,1640-1641,1644-1645,1648-1649,1652-16" |
| 1102 | "53,1656-1657,1660-1661,1664,1668,1672,1676,1680,1684,1688,1692,1696-1697,1700-1701,1704-1705,1708-1709,1712-1713" |
| 1103 | ",1716-1717,1720-1721,1724-1725,1728,1732,1736,1740,1744,1748,1752,1756,1760-1761,1764-1765,1768-1769,1772-1773,1" |
| 1104 | "776-1777,1780-1781,1784-1785,1788-1789,1792,1796,1800,1804,1808,1812,1816,1820,1824-1825,1828-1829,1832-1833,183" |
| 1105 | "6-1837,1840-1841,1844-1845,1848-1849,1852-1853,1856,1860,1864,1868,1872,1876,1880,1884,1888-1889,1892-1893,1896-" |
| 1106 | "1897,1900-1901,1904-1905,1908-1909,1912-1913,1916-1917,1920,1924,1928,1932,1936,1940,1944,1948,1952-1953,1956-19" |
| 1107 | "57,1960-1961,1964-1965,1968-1969,1972-1973,1976-1977,1980-1981,1984,1988,1992,1996,2000,2004,2008,2012,2016-2017" |
| 1108 | ",2020-2021,2024-2025,2028-2029,2032-2033,2036-2037,2040-2041,2044-2045,2048,2052,2056,2060,2064,2068,2072,2076,2" |
| 1109 | "080-2081,2084-2085,2088-2089,2092-2093,2096-2097,2100-2101,2104-2105,2108-2109,2112,2116,2120,2124,2128,2132,213" |
| 1110 | "6,2140,2144-2145,2148-2149,2152-2153,2156-2157,2160-2161,2164-2165,2168-2169,2172-2173,2176,2180,2184,2188,2192," |
| 1111 | "2196,2200,2204,2208-2209,2212-2213,2216-2217,2220-2221,2224-2225,2228-2229,2232-2233,2236-2237,2240,2244,2248,22" |
| 1112 | "52,2256,2260,2264,2268,2272-2273,2276-2277,2280-2281,2284-2285,2288-2289,2292-2293,2296-2297,2300-2301,2304,2308" |
| 1113 | ",2312,2316,2320,2324,2328,2332,2336-2337,2340-2341,2344-2345,2348-2349,2352-2353,2356-2357,2360-2361,2364-2365,2" |
| 1114 | "368,2372,2376,2380,2384,2388,2392,2396,2400-2401,2404-2405,2408-2409,2412-2413,2416-2417,2420-2421,2424-2425,242" |
| 1115 | "8-2429,2432,2436,2440,2444,2448,2452,2456,2460,2464-2465,2468-2469,2472-2473,2476-2477,2480-2481,2484-2485,2488-" |
| 1116 | "2489,2492-2493,2496,2500,2504,2508,2512,2516,2520,2524,2528-2529,2532-2533,2536-2537,2540-2541,2544-2545,2548-25" |
| 1117 | "49,2552-2553,2556-2557\n"; |
| 1118 | |
| 1119 | static const struct test_bitmap_print test_print[] __initconst = { |
| 1120 | { small_bitmap, sizeof(small_bitmap) * BITS_PER_BYTE, small_mask, small_list }, |
| 1121 | { large_bitmap, sizeof(large_bitmap) * BITS_PER_BYTE, large_mask, large_list }, |
| 1122 | }; |
| 1123 | |
| 1124 | static void __init test_bitmap_print_buf(void) |
| 1125 | { |
| 1126 | int i; |
| 1127 | |
| 1128 | for (i = 0; i < ARRAY_SIZE(test_print); i++) { |
| 1129 | const struct test_bitmap_print *t = &test_print[i]; |
| 1130 | int n; |
| 1131 | |
| 1132 | n = bitmap_print_bitmask_to_buf(print_buf, t->bitmap, t->nbits, |
| 1133 | 0, 2 * PAGE_SIZE); |
| 1134 | expect_eq_uint(strlen(t->mask) + 1, n); |
| 1135 | expect_eq_str(t->mask, print_buf, n); |
| 1136 | |
| 1137 | n = bitmap_print_list_to_buf(print_buf, t->bitmap, t->nbits, |
| 1138 | 0, 2 * PAGE_SIZE); |
| 1139 | expect_eq_uint(strlen(t->list) + 1, n); |
| 1140 | expect_eq_str(t->list, print_buf, n); |
| 1141 | |
| 1142 | /* test by non-zero offset */ |
| 1143 | if (strlen(t->list) > PAGE_SIZE) { |
| 1144 | n = bitmap_print_list_to_buf(print_buf, t->bitmap, t->nbits, |
| 1145 | PAGE_SIZE, PAGE_SIZE); |
| 1146 | expect_eq_uint(strlen(t->list) + 1 - PAGE_SIZE, n); |
| 1147 | expect_eq_str(t->list + PAGE_SIZE, print_buf, n); |
| 1148 | } |
| 1149 | } |
| 1150 | } |
| 1151 | |
| 1152 | static void __init test_bitmap_const_eval(void) |
| 1153 | { |
| 1154 | DECLARE_BITMAP(bitmap, BITS_PER_LONG); |
| 1155 | unsigned long initvar = BIT(2); |
| 1156 | unsigned long bitopvar = 0; |
| 1157 | unsigned long var = 0; |
| 1158 | int res; |
| 1159 | |
| 1160 | /* |
| 1161 | * Compilers must be able to optimize all of those to compile-time |
| 1162 | * constants on any supported optimization level (-O2, -Os) and any |
| 1163 | * architecture. Otherwise, trigger a build bug. |
| 1164 | * The whole function gets optimized out then, there's nothing to do |
| 1165 | * in runtime. |
| 1166 | */ |
| 1167 | |
| 1168 | /* |
| 1169 | * Equals to `unsigned long bitmap[1] = { GENMASK(6, 5), }`. |
| 1170 | * Clang on s390 optimizes bitops at compile-time as intended, but at |
| 1171 | * the same time stops treating @bitmap and @bitopvar as compile-time |
| 1172 | * constants after regular test_bit() is executed, thus triggering the |
| 1173 | * build bugs below. So, call const_test_bit() there directly until |
| 1174 | * the compiler is fixed. |
| 1175 | */ |
| 1176 | bitmap_clear(bitmap, 0, BITS_PER_LONG); |
| 1177 | #if defined(__s390__) && defined(__clang__) |
| 1178 | if (!const_test_bit(7, bitmap)) |
| 1179 | #else |
| 1180 | if (!test_bit(7, bitmap)) |
| 1181 | #endif |
| 1182 | bitmap_set(bitmap, 5, 2); |
| 1183 | |
| 1184 | /* Equals to `unsigned long bitopvar = BIT(20)` */ |
| 1185 | __change_bit(31, &bitopvar); |
| 1186 | bitmap_shift_right(&bitopvar, &bitopvar, 11, BITS_PER_LONG); |
| 1187 | |
| 1188 | /* Equals to `unsigned long var = BIT(25)` */ |
| 1189 | var |= BIT(25); |
| 1190 | if (var & BIT(0)) |
| 1191 | var ^= GENMASK(9, 6); |
| 1192 | |
| 1193 | /* __const_hweight<32|64>(GENMASK(6, 5)) == 2 */ |
| 1194 | res = bitmap_weight(bitmap, 20); |
| 1195 | BUILD_BUG_ON(!__builtin_constant_p(res)); |
| 1196 | BUILD_BUG_ON(res != 2); |
| 1197 | |
| 1198 | /* !(BIT(31) & BIT(18)) == 1 */ |
| 1199 | res = !test_bit(18, &bitopvar); |
| 1200 | BUILD_BUG_ON(!__builtin_constant_p(res)); |
| 1201 | BUILD_BUG_ON(!res); |
| 1202 | |
| 1203 | /* BIT(2) & GENMASK(14, 8) == 0 */ |
| 1204 | res = initvar & GENMASK(14, 8); |
| 1205 | BUILD_BUG_ON(!__builtin_constant_p(res)); |
| 1206 | BUILD_BUG_ON(res); |
| 1207 | |
| 1208 | /* ~BIT(25) */ |
| 1209 | BUILD_BUG_ON(!__builtin_constant_p(~var)); |
| 1210 | BUILD_BUG_ON(~var != ~BIT(25)); |
| 1211 | } |
| 1212 | |
| 1213 | static void __init selftest(void) |
| 1214 | { |
| 1215 | test_zero_clear(); |
| 1216 | test_fill_set(); |
| 1217 | test_copy(); |
| 1218 | test_replace(); |
| 1219 | test_bitmap_arr32(); |
| 1220 | test_bitmap_arr64(); |
| 1221 | test_bitmap_parse(); |
| 1222 | test_bitmap_parselist(); |
| 1223 | test_bitmap_printlist(); |
| 1224 | test_mem_optimisations(); |
| 1225 | test_bitmap_cut(); |
| 1226 | test_bitmap_print_buf(); |
| 1227 | test_bitmap_const_eval(); |
| 1228 | |
| 1229 | test_find_nth_bit(); |
| 1230 | test_for_each_set_bit(); |
| 1231 | test_for_each_set_bit_from(); |
| 1232 | test_for_each_clear_bit(); |
| 1233 | test_for_each_clear_bit_from(); |
| 1234 | test_for_each_set_bitrange(); |
| 1235 | test_for_each_clear_bitrange(); |
| 1236 | test_for_each_set_bitrange_from(); |
| 1237 | test_for_each_clear_bitrange_from(); |
| 1238 | test_for_each_set_clump8(); |
| 1239 | test_for_each_set_bit_wrap(); |
| 1240 | } |
| 1241 | |
| 1242 | KSTM_MODULE_LOADERS(test_bitmap); |
| 1243 | MODULE_AUTHOR("david decotigny <david.decotigny@googlers.com>"); |
| 1244 | MODULE_LICENSE("GPL"); |