lib/test_bitmap.c

   1 /*
   2  * Test cases for printf facility.
   3  */
   4
   5 #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
   6
   7 #include <linux/bitmap.h>
   8 #include <linux/init.h>
   9 #include <linux/kernel.h>
  10 #include <linux/module.h>
  11 #include <linux/printk.h>
  12 #include <linux/slab.h>
  13 #include <linux/string.h>
  14
  15 static unsigned total_tests __initdata;
  16 static unsigned failed_tests __initdata;
  17
  18 static char pbl_buffer[PAGE_SIZE] __initdata;
  19
  20
  21 static bool __init
  22 __check_eq_uint(const char *srcfile, unsigned int line,
  23                 const unsigned int exp_uint, unsigned int x)
  24 {
  25         if (exp_uint != x) {
  26                 pr_warn("[%s:%u] expected %u, got %u\n",
  27                         srcfile, line, exp_uint, x);
  28                 return false;
  29         }
  30         return true;
  31 }
  32
  33
  34 static bool __init
  35 __check_eq_bitmap(const char *srcfile, unsigned int line,
  36                   const unsigned long *exp_bmap, unsigned int exp_nbits,
  37                   const unsigned long *bmap, unsigned int nbits)
  38 {
  39         if (exp_nbits != nbits) {
  40                 pr_warn("[%s:%u] bitmap length mismatch: expected %u, got %u\n",
  41                         srcfile, line, exp_nbits, nbits);
  42                 return false;
  43         }
  44
  45         if (!bitmap_equal(exp_bmap, bmap, nbits)) {
  46                 pr_warn("[%s:%u] bitmaps contents differ: expected \"%*pbl\", got \"%*pbl\"\n",
  47                         srcfile, line,
  48                         exp_nbits, exp_bmap, nbits, bmap);
  49                 return false;
  50         }
  51         return true;
  52 }
  53
  54 static bool __init
  55 __check_eq_pbl(const char *srcfile, unsigned int line,
  56                const char *expected_pbl,
  57                const unsigned long *bitmap, unsigned int nbits)
  58 {
  59         snprintf(pbl_buffer, sizeof(pbl_buffer), "%*pbl", nbits, bitmap);
  60         if (strcmp(expected_pbl, pbl_buffer)) {
  61                 pr_warn("[%s:%u] expected \"%s\", got \"%s\"\n",
  62                         srcfile, line,
  63                         expected_pbl, pbl_buffer);
  64                 return false;
  65         }
  66         return true;
  67 }
  68
  69 static bool __init
  70 __check_eq_u32_array(const char *srcfile, unsigned int line,
  71                      const u32 *exp_arr, unsigned int exp_len,
  72                      const u32 *arr, unsigned int len)
  73 {
  74         if (exp_len != len) {
  75                 pr_warn("[%s:%u] array length differ: expected %u, got %u\n",
  76                         srcfile, line,
  77                         exp_len, len);
  78                 return false;
  79         }
  80
  81         if (memcmp(exp_arr, arr, len*sizeof(*arr))) {
  82                 pr_warn("[%s:%u] array contents differ\n", srcfile, line);
  83                 print_hex_dump(KERN_WARNING, "  exp:  ", DUMP_PREFIX_OFFSET,
  84                                32, 4, exp_arr, exp_len*sizeof(*exp_arr), false);
  85                 print_hex_dump(KERN_WARNING, "  got:  ", DUMP_PREFIX_OFFSET,
  86                                32, 4, arr, len*sizeof(*arr), false);
  87                 return false;
  88         }
  89
  90         return true;
  91 }
  92
  93 #define __expect_eq(suffix, ...)                                        \
  94         ({                                                              \
  95                 int result = 0;                                         \
  96                 total_tests++;                                          \
  97                 if (!__check_eq_ ## suffix(__FILE__, __LINE__,          \
  98                                            ##__VA_ARGS__)) {            \
  99                         failed_tests++;                                 \
 100                         result = 1;                                     \
 101                 }                                                       \
 102                 result;                                                 \
 103         })
 104
 105 #define expect_eq_uint(...)             __expect_eq(uint, ##__VA_ARGS__)
 106 #define expect_eq_bitmap(...)           __expect_eq(bitmap, ##__VA_ARGS__)
 107 #define expect_eq_pbl(...)              __expect_eq(pbl, ##__VA_ARGS__)
 108 #define expect_eq_u32_array(...)        __expect_eq(u32_array, ##__VA_ARGS__)
 109
 110 static void __init test_zero_fill_copy(void)
 111 {
 112         DECLARE_BITMAP(bmap1, 1024);
 113         DECLARE_BITMAP(bmap2, 1024);
 114
 115         bitmap_zero(bmap1, 1024);
 116         bitmap_zero(bmap2, 1024);
 117
 118         /* single-word bitmaps */
 119         expect_eq_pbl("", bmap1, 23);
 120
 121         bitmap_fill(bmap1, 19);
 122         expect_eq_pbl("0-18", bmap1, 1024);
 123
 124         bitmap_copy(bmap2, bmap1, 23);
 125         expect_eq_pbl("0-18", bmap2, 1024);
 126
 127         bitmap_fill(bmap2, 23);
 128         expect_eq_pbl("0-22", bmap2, 1024);
 129
 130         bitmap_copy(bmap2, bmap1, 23);
 131         expect_eq_pbl("0-18", bmap2, 1024);
 132
 133         bitmap_zero(bmap1, 23);
 134         expect_eq_pbl("", bmap1, 1024);
 135
 136         /* multi-word bitmaps */
 137         bitmap_zero(bmap1, 1024);
 138         expect_eq_pbl("", bmap1, 1024);
 139
 140         bitmap_fill(bmap1, 109);
 141         expect_eq_pbl("0-108", bmap1, 1024);
 142
 143         bitmap_copy(bmap2, bmap1, 1024);
 144         expect_eq_pbl("0-108", bmap2, 1024);
 145
 146         bitmap_fill(bmap2, 1024);
 147         expect_eq_pbl("0-1023", bmap2, 1024);
 148
 149         bitmap_copy(bmap2, bmap1, 1024);
 150         expect_eq_pbl("0-108", bmap2, 1024);
 151
 152         /* the following tests assume a 32- or 64-bit arch (even 128b
 153          * if we care)
 154          */
 155
 156         bitmap_fill(bmap2, 1024);
 157         bitmap_copy(bmap2, bmap1, 109);  /* ... but 0-padded til word length */
 158         expect_eq_pbl("0-108,128-1023", bmap2, 1024);
 159
 160         bitmap_fill(bmap2, 1024);
 161         bitmap_copy(bmap2, bmap1, 97);  /* ... but aligned on word length */
 162         expect_eq_pbl("0-108,128-1023", bmap2, 1024);
 163
 164         bitmap_zero(bmap2, 97);  /* ... but 0-padded til word length */
 165         expect_eq_pbl("128-1023", bmap2, 1024);
 166 }
 167
 168 #define PARSE_TIME 0x1
 169
 170 struct test_bitmap_parselist{
 171         const int errno;
 172         const char *in;
 173         const unsigned long *expected;
 174         const int nbits;
 175         const int flags;
 176 };
 177
 178 static const unsigned long exp[] __initconst = {
 179         BITMAP_FROM_U64(1),
 180         BITMAP_FROM_U64(2),
 181         BITMAP_FROM_U64(0x0000ffff),
 182         BITMAP_FROM_U64(0xffff0000),
 183         BITMAP_FROM_U64(0x55555555),
 184         BITMAP_FROM_U64(0xaaaaaaaa),
 185         BITMAP_FROM_U64(0x11111111),
 186         BITMAP_FROM_U64(0x22222222),
 187         BITMAP_FROM_U64(0xffffffff),
 188         BITMAP_FROM_U64(0xfffffffe),
 189         BITMAP_FROM_U64(0x3333333311111111ULL),
 190         BITMAP_FROM_U64(0xffffffff77777777ULL)
 191 };
 192
 193 static const unsigned long exp2[] __initconst = {
 194         BITMAP_FROM_U64(0x3333333311111111ULL),
 195         BITMAP_FROM_U64(0xffffffff77777777ULL)
 196 };
 197
 198 static const struct test_bitmap_parselist parselist_tests[] __initconst = {
 199 #define step (sizeof(u64) / sizeof(unsigned long))
 200
 201         {0, "0",                        &exp[0], 8, 0},
 202         {0, "1",                        &exp[1 * step], 8, 0},
 203         {0, "0-15",                     &exp[2 * step], 32, 0},
 204         {0, "16-31",                    &exp[3 * step], 32, 0},
 205         {0, "0-31:1/2",                 &exp[4 * step], 32, 0},
 206         {0, "1-31:1/2",                 &exp[5 * step], 32, 0},
 207         {0, "0-31:1/4",                 &exp[6 * step], 32, 0},
 208         {0, "1-31:1/4",                 &exp[7 * step], 32, 0},
 209         {0, "0-31:4/4",                 &exp[8 * step], 32, 0},
 210         {0, "1-31:4/4",                 &exp[9 * step], 32, 0},
 211         {0, "0-31:1/4,32-63:2/4",       &exp[10 * step], 64, 0},
 212         {0, "0-31:3/4,32-63:4/4",       &exp[11 * step], 64, 0},
 213
 214         {0, "0-31:1/4,32-63:2/4,64-95:3/4,96-127:4/4",  exp2, 128, 0},
 215
 216         {0, "0-2047:128/256", NULL, 2048, PARSE_TIME},
 217
 218         {-EINVAL, "-1", NULL, 8, 0},
 219         {-EINVAL, "-0", NULL, 8, 0},
 220         {-EINVAL, "10-1", NULL, 8, 0},
 221         {-EINVAL, "0-31:10/1", NULL, 8, 0},
 222 };
 223
 224 static void __init test_bitmap_parselist(void)
 225 {
 226         int i;
 227         int err;
 228         cycles_t cycles;
 229         DECLARE_BITMAP(bmap, 2048);
 230
 231         for (i = 0; i < ARRAY_SIZE(parselist_tests); i++) {
 232 #define ptest parselist_tests[i]
 233
 234                 cycles = get_cycles();
 235                 err = bitmap_parselist(ptest.in, bmap, ptest.nbits);
 236                 cycles = get_cycles() - cycles;
 237
 238                 if (err != ptest.errno) {
 239                         pr_err("test %d: input is %s, errno is %d, expected %d\n",
 240                                         i, ptest.in, err, ptest.errno);
 241                         continue;
 242                 }
 243
 244                 if (!err && ptest.expected
 245                          && !__bitmap_equal(bmap, ptest.expected, ptest.nbits)) {
 246                         pr_err("test %d: input is %s, result is 0x%lx, expected 0x%lx\n",
 247                                         i, ptest.in, bmap[0], *ptest.expected);
 248                         continue;
 249                 }
 250
 251                 if (ptest.flags & PARSE_TIME)
 252                         pr_err("test %d: input is '%s' OK, Time: %llu\n",
 253                                         i, ptest.in,
 254                                         (unsigned long long)cycles);
 255         }
 256 }
 257
 258 static void __init test_bitmap_u32_array_conversions(void)
 259 {
 260         DECLARE_BITMAP(bmap1, 1024);
 261         DECLARE_BITMAP(bmap2, 1024);
 262         u32 exp_arr[32], arr[32];
 263         unsigned nbits;
 264
 265         for (nbits = 0 ; nbits < 257 ; ++nbits) {
 266                 const unsigned int used_u32s = DIV_ROUND_UP(nbits, 32);
 267                 unsigned int i, rv;
 268
 269                 bitmap_zero(bmap1, nbits);
 270                 bitmap_set(bmap1, nbits, 1024 - nbits);  /* garbage */
 271
 272                 memset(arr, 0xff, sizeof(arr));
 273                 rv = bitmap_to_u32array(arr, used_u32s, bmap1, nbits);
 274                 expect_eq_uint(nbits, rv);
 275
 276                 memset(exp_arr, 0xff, sizeof(exp_arr));
 277                 memset(exp_arr, 0, used_u32s*sizeof(*exp_arr));
 278                 expect_eq_u32_array(exp_arr, 32, arr, 32);
 279
 280                 bitmap_fill(bmap2, 1024);
 281                 rv = bitmap_from_u32array(bmap2, nbits, arr, used_u32s);
 282                 expect_eq_uint(nbits, rv);
 283                 expect_eq_bitmap(bmap1, 1024, bmap2, 1024);
 284
 285                 for (i = 0 ; i < nbits ; ++i) {
 286                         /*
 287                          * test conversion bitmap -> u32[]
 288                          */
 289
 290                         bitmap_zero(bmap1, 1024);
 291                         __set_bit(i, bmap1);
 292                         bitmap_set(bmap1, nbits, 1024 - nbits);  /* garbage */
 293
 294                         memset(arr, 0xff, sizeof(arr));
 295                         rv = bitmap_to_u32array(arr, used_u32s, bmap1, nbits);
 296                         expect_eq_uint(nbits, rv);
 297
 298                         /* 1st used u32 words contain expected bit set, the
 299                          * remaining words are left unchanged (0xff)
 300                          */
 301                         memset(exp_arr, 0xff, sizeof(exp_arr));
 302                         memset(exp_arr, 0, used_u32s*sizeof(*exp_arr));
 303                         exp_arr[i/32] = (1U<<(i%32));
 304                         expect_eq_u32_array(exp_arr, 32, arr, 32);
 305
 306
 307                         /* same, with longer array to fill
 308                          */
 309                         memset(arr, 0xff, sizeof(arr));
 310                         rv = bitmap_to_u32array(arr, 32, bmap1, nbits);
 311                         expect_eq_uint(nbits, rv);
 312
 313                         /* 1st used u32 words contain expected bit set, the
 314                          * remaining words are all 0s
 315                          */
 316                         memset(exp_arr, 0, sizeof(exp_arr));
 317                         exp_arr[i/32] = (1U<<(i%32));
 318                         expect_eq_u32_array(exp_arr, 32, arr, 32);
 319
 320                         /*
 321                          * test conversion u32[] -> bitmap
 322                          */
 323
 324                         /* the 1st nbits of bmap2 are identical to
 325                          * bmap1, the remaining bits of bmap2 are left
 326                          * unchanged (all 1s)
 327                          */
 328                         bitmap_fill(bmap2, 1024);
 329                         rv = bitmap_from_u32array(bmap2, nbits,
 330                                                   exp_arr, used_u32s);
 331                         expect_eq_uint(nbits, rv);
 332
 333                         expect_eq_bitmap(bmap1, 1024, bmap2, 1024);
 334
 335                         /* same, with more bits to fill
 336                          */
 337                         memset(arr, 0xff, sizeof(arr));  /* garbage */
 338                         memset(arr, 0, used_u32s*sizeof(u32));
 339                         arr[i/32] = (1U<<(i%32));
 340
 341                         bitmap_fill(bmap2, 1024);
 342                         rv = bitmap_from_u32array(bmap2, 1024, arr, used_u32s);
 343                         expect_eq_uint(used_u32s*32, rv);
 344
 345                         /* the 1st nbits of bmap2 are identical to
 346                          * bmap1, the remaining bits of bmap2 are cleared
 347                          */
 348                         bitmap_zero(bmap1, 1024);
 349                         __set_bit(i, bmap1);
 350                         expect_eq_bitmap(bmap1, 1024, bmap2, 1024);
 351
 352
 353                         /*
 354                          * test short conversion bitmap -> u32[] (1
 355                          * word too short)
 356                          */
 357                         if (used_u32s > 1) {
 358                                 bitmap_zero(bmap1, 1024);
 359                                 __set_bit(i, bmap1);
 360                                 bitmap_set(bmap1, nbits,
 361                                            1024 - nbits);  /* garbage */
 362                                 memset(arr, 0xff, sizeof(arr));
 363
 364                                 rv = bitmap_to_u32array(arr, used_u32s - 1,
 365                                                         bmap1, nbits);
 366                                 expect_eq_uint((used_u32s - 1)*32, rv);
 367
 368                                 /* 1st used u32 words contain expected
 369                                  * bit set, the remaining words are
 370                                  * left unchanged (0xff)
 371                                  */
 372                                 memset(exp_arr, 0xff, sizeof(exp_arr));
 373                                 memset(exp_arr, 0,
 374                                        (used_u32s-1)*sizeof(*exp_arr));
 375                                 if ((i/32) < (used_u32s - 1))
 376                                         exp_arr[i/32] = (1U<<(i%32));
 377                                 expect_eq_u32_array(exp_arr, 32, arr, 32);
 378                         }
 379
 380                         /*
 381                          * test short conversion u32[] -> bitmap (3
 382                          * bits too short)
 383                          */
 384                         if (nbits > 3) {
 385                                 memset(arr, 0xff, sizeof(arr));  /* garbage */
 386                                 memset(arr, 0, used_u32s*sizeof(*arr));
 387                                 arr[i/32] = (1U<<(i%32));
 388
 389                                 bitmap_zero(bmap1, 1024);
 390                                 rv = bitmap_from_u32array(bmap1, nbits - 3,
 391                                                           arr, used_u32s);
 392                                 expect_eq_uint(nbits - 3, rv);
 393
 394                                 /* we are expecting the bit < nbits -
 395                                  * 3 (none otherwise), and the rest of
 396                                  * bmap1 unchanged (0-filled)
 397                                  */
 398                                 bitmap_zero(bmap2, 1024);
 399                                 if (i < nbits - 3)
 400                                         __set_bit(i, bmap2);
 401                                 expect_eq_bitmap(bmap2, 1024, bmap1, 1024);
 402
 403                                 /* do the same with bmap1 initially
 404                                  * 1-filled
 405                                  */
 406
 407                                 bitmap_fill(bmap1, 1024);
 408                                 rv = bitmap_from_u32array(bmap1, nbits - 3,
 409                                                          arr, used_u32s);
 410                                 expect_eq_uint(nbits - 3, rv);
 411
 412                                 /* we are expecting the bit < nbits -
 413                                  * 3 (none otherwise), and the rest of
 414                                  * bmap1 unchanged (1-filled)
 415                                  */
 416                                 bitmap_zero(bmap2, 1024);
 417                                 if (i < nbits - 3)
 418                                         __set_bit(i, bmap2);
 419                                 bitmap_set(bmap2, nbits-3, 1024 - nbits + 3);
 420                                 expect_eq_bitmap(bmap2, 1024, bmap1, 1024);
 421                         }
 422                 }
 423         }
 424 }
 425
 426 static void noinline __init test_mem_optimisations(void)
 427 {
 428         DECLARE_BITMAP(bmap1, 1024);
 429         DECLARE_BITMAP(bmap2, 1024);
 430         unsigned int start, nbits;
 431
 432         for (start = 0; start < 1024; start += 8) {
 433                 memset(bmap1, 0x5a, sizeof(bmap1));
 434                 memset(bmap2, 0x5a, sizeof(bmap2));
 435                 for (nbits = 0; nbits < 1024 - start; nbits += 8) {
 436                         bitmap_set(bmap1, start, nbits);
 437                         __bitmap_set(bmap2, start, nbits);
 438                         if (!bitmap_equal(bmap1, bmap2, 1024))
 439                                 printk("set not equal %d %d\n", start, nbits);
 440                         if (!__bitmap_equal(bmap1, bmap2, 1024))
 441                                 printk("set not __equal %d %d\n", start, nbits);
 442
 443                         bitmap_clear(bmap1, start, nbits);
 444                         __bitmap_clear(bmap2, start, nbits);
 445                         if (!bitmap_equal(bmap1, bmap2, 1024))
 446                                 printk("clear not equal %d %d\n", start, nbits);
 447                         if (!__bitmap_equal(bmap1, bmap2, 1024))
 448                                 printk("clear not __equal %d %d\n", start,
 449                                                                         nbits);
 450                 }
 451         }
 452 }
 453
 454 static int __init test_bitmap_init(void)
 455 {
 456         test_zero_fill_copy();
 457         test_bitmap_u32_array_conversions();
 458         test_bitmap_parselist();
 459         test_mem_optimisations();
 460
 461         if (failed_tests == 0)
 462                 pr_info("all %u tests passed\n", total_tests);
 463         else
 464                 pr_warn("failed %u out of %u tests\n",
 465                         failed_tests, total_tests);
 466
 467         return failed_tests ? -EINVAL : 0;
 468 }
 469
 470 static void __exit test_bitmap_cleanup(void)
 471 {
 472 }
 473
 474 module_init(test_bitmap_init);
 475 module_exit(test_bitmap_cleanup);
 476
 477 MODULE_AUTHOR("david decotigny <david.decotigny@googlers.com>");
 478 MODULE_LICENSE("GPL");