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:", NULL, 8, 0},
 222         {-EINVAL, "0-31:0", NULL, 8, 0},
 223         {-EINVAL, "0-31:0/0", NULL, 8, 0},
 224         {-EINVAL, "0-31:1/0", NULL, 8, 0},
 225         {-EINVAL, "0-31:10/1", NULL, 8, 0},
 226 };
 227
 228 static void __init test_bitmap_parselist(void)
 229 {
 230         int i;
 231         int err;
 232         cycles_t cycles;
 233         DECLARE_BITMAP(bmap, 2048);
 234
 235         for (i = 0; i < ARRAY_SIZE(parselist_tests); i++) {
 236 #define ptest parselist_tests[i]
 237
 238                 cycles = get_cycles();
 239                 err = bitmap_parselist(ptest.in, bmap, ptest.nbits);
 240                 cycles = get_cycles() - cycles;
 241
 242                 if (err != ptest.errno) {
 243                         pr_err("test %d: input is %s, errno is %d, expected %d\n",
 244                                         i, ptest.in, err, ptest.errno);
 245                         continue;
 246                 }
 247
 248                 if (!err && ptest.expected
 249                          && !__bitmap_equal(bmap, ptest.expected, ptest.nbits)) {
 250                         pr_err("test %d: input is %s, result is 0x%lx, expected 0x%lx\n",
 251                                         i, ptest.in, bmap[0], *ptest.expected);
 252                         continue;
 253                 }
 254
 255                 if (ptest.flags & PARSE_TIME)
 256                         pr_err("test %d: input is '%s' OK, Time: %llu\n",
 257                                         i, ptest.in,
 258                                         (unsigned long long)cycles);
 259         }
 260 }
 261
 262 static void __init test_bitmap_u32_array_conversions(void)
 263 {
 264         DECLARE_BITMAP(bmap1, 1024);
 265         DECLARE_BITMAP(bmap2, 1024);
 266         u32 exp_arr[32], arr[32];
 267         unsigned nbits;
 268
 269         for (nbits = 0 ; nbits < 257 ; ++nbits) {
 270                 const unsigned int used_u32s = DIV_ROUND_UP(nbits, 32);
 271                 unsigned int i, rv;
 272
 273                 bitmap_zero(bmap1, nbits);
 274                 bitmap_set(bmap1, nbits, 1024 - nbits);  /* garbage */
 275
 276                 memset(arr, 0xff, sizeof(arr));
 277                 rv = bitmap_to_u32array(arr, used_u32s, bmap1, nbits);
 278                 expect_eq_uint(nbits, rv);
 279
 280                 memset(exp_arr, 0xff, sizeof(exp_arr));
 281                 memset(exp_arr, 0, used_u32s*sizeof(*exp_arr));
 282                 expect_eq_u32_array(exp_arr, 32, arr, 32);
 283
 284                 bitmap_fill(bmap2, 1024);
 285                 rv = bitmap_from_u32array(bmap2, nbits, arr, used_u32s);
 286                 expect_eq_uint(nbits, rv);
 287                 expect_eq_bitmap(bmap1, 1024, bmap2, 1024);
 288
 289                 for (i = 0 ; i < nbits ; ++i) {
 290                         /*
 291                          * test conversion bitmap -> u32[]
 292                          */
 293
 294                         bitmap_zero(bmap1, 1024);
 295                         __set_bit(i, bmap1);
 296                         bitmap_set(bmap1, nbits, 1024 - nbits);  /* garbage */
 297
 298                         memset(arr, 0xff, sizeof(arr));
 299                         rv = bitmap_to_u32array(arr, used_u32s, bmap1, nbits);
 300                         expect_eq_uint(nbits, rv);
 301
 302                         /* 1st used u32 words contain expected bit set, the
 303                          * remaining words are left unchanged (0xff)
 304                          */
 305                         memset(exp_arr, 0xff, sizeof(exp_arr));
 306                         memset(exp_arr, 0, used_u32s*sizeof(*exp_arr));
 307                         exp_arr[i/32] = (1U<<(i%32));
 308                         expect_eq_u32_array(exp_arr, 32, arr, 32);
 309
 310
 311                         /* same, with longer array to fill
 312                          */
 313                         memset(arr, 0xff, sizeof(arr));
 314                         rv = bitmap_to_u32array(arr, 32, bmap1, nbits);
 315                         expect_eq_uint(nbits, rv);
 316
 317                         /* 1st used u32 words contain expected bit set, the
 318                          * remaining words are all 0s
 319                          */
 320                         memset(exp_arr, 0, sizeof(exp_arr));
 321                         exp_arr[i/32] = (1U<<(i%32));
 322                         expect_eq_u32_array(exp_arr, 32, arr, 32);
 323
 324                         /*
 325                          * test conversion u32[] -> bitmap
 326                          */
 327
 328                         /* the 1st nbits of bmap2 are identical to
 329                          * bmap1, the remaining bits of bmap2 are left
 330                          * unchanged (all 1s)
 331                          */
 332                         bitmap_fill(bmap2, 1024);
 333                         rv = bitmap_from_u32array(bmap2, nbits,
 334                                                   exp_arr, used_u32s);
 335                         expect_eq_uint(nbits, rv);
 336
 337                         expect_eq_bitmap(bmap1, 1024, bmap2, 1024);
 338
 339                         /* same, with more bits to fill
 340                          */
 341                         memset(arr, 0xff, sizeof(arr));  /* garbage */
 342                         memset(arr, 0, used_u32s*sizeof(u32));
 343                         arr[i/32] = (1U<<(i%32));
 344
 345                         bitmap_fill(bmap2, 1024);
 346                         rv = bitmap_from_u32array(bmap2, 1024, arr, used_u32s);
 347                         expect_eq_uint(used_u32s*32, rv);
 348
 349                         /* the 1st nbits of bmap2 are identical to
 350                          * bmap1, the remaining bits of bmap2 are cleared
 351                          */
 352                         bitmap_zero(bmap1, 1024);
 353                         __set_bit(i, bmap1);
 354                         expect_eq_bitmap(bmap1, 1024, bmap2, 1024);
 355
 356
 357                         /*
 358                          * test short conversion bitmap -> u32[] (1
 359                          * word too short)
 360                          */
 361                         if (used_u32s > 1) {
 362                                 bitmap_zero(bmap1, 1024);
 363                                 __set_bit(i, bmap1);
 364                                 bitmap_set(bmap1, nbits,
 365                                            1024 - nbits);  /* garbage */
 366                                 memset(arr, 0xff, sizeof(arr));
 367
 368                                 rv = bitmap_to_u32array(arr, used_u32s - 1,
 369                                                         bmap1, nbits);
 370                                 expect_eq_uint((used_u32s - 1)*32, rv);
 371
 372                                 /* 1st used u32 words contain expected
 373                                  * bit set, the remaining words are
 374                                  * left unchanged (0xff)
 375                                  */
 376                                 memset(exp_arr, 0xff, sizeof(exp_arr));
 377                                 memset(exp_arr, 0,
 378                                        (used_u32s-1)*sizeof(*exp_arr));
 379                                 if ((i/32) < (used_u32s - 1))
 380                                         exp_arr[i/32] = (1U<<(i%32));
 381                                 expect_eq_u32_array(exp_arr, 32, arr, 32);
 382                         }
 383
 384                         /*
 385                          * test short conversion u32[] -> bitmap (3
 386                          * bits too short)
 387                          */
 388                         if (nbits > 3) {
 389                                 memset(arr, 0xff, sizeof(arr));  /* garbage */
 390                                 memset(arr, 0, used_u32s*sizeof(*arr));
 391                                 arr[i/32] = (1U<<(i%32));
 392
 393                                 bitmap_zero(bmap1, 1024);
 394                                 rv = bitmap_from_u32array(bmap1, nbits - 3,
 395                                                           arr, used_u32s);
 396                                 expect_eq_uint(nbits - 3, rv);
 397
 398                                 /* we are expecting the bit < nbits -
 399                                  * 3 (none otherwise), and the rest of
 400                                  * bmap1 unchanged (0-filled)
 401                                  */
 402                                 bitmap_zero(bmap2, 1024);
 403                                 if (i < nbits - 3)
 404                                         __set_bit(i, bmap2);
 405                                 expect_eq_bitmap(bmap2, 1024, bmap1, 1024);
 406
 407                                 /* do the same with bmap1 initially
 408                                  * 1-filled
 409                                  */
 410
 411                                 bitmap_fill(bmap1, 1024);
 412                                 rv = bitmap_from_u32array(bmap1, nbits - 3,
 413                                                          arr, used_u32s);
 414                                 expect_eq_uint(nbits - 3, rv);
 415
 416                                 /* we are expecting the bit < nbits -
 417                                  * 3 (none otherwise), and the rest of
 418                                  * bmap1 unchanged (1-filled)
 419                                  */
 420                                 bitmap_zero(bmap2, 1024);
 421                                 if (i < nbits - 3)
 422                                         __set_bit(i, bmap2);
 423                                 bitmap_set(bmap2, nbits-3, 1024 - nbits + 3);
 424                                 expect_eq_bitmap(bmap2, 1024, bmap1, 1024);
 425                         }
 426                 }
 427         }
 428 }
 429
 430 static void noinline __init test_mem_optimisations(void)
 431 {
 432         DECLARE_BITMAP(bmap1, 1024);
 433         DECLARE_BITMAP(bmap2, 1024);
 434         unsigned int start, nbits;
 435
 436         for (start = 0; start < 1024; start += 8) {
 437                 for (nbits = 0; nbits < 1024 - start; nbits += 8) {
 438                         memset(bmap1, 0x5a, sizeof(bmap1));
 439                         memset(bmap2, 0x5a, sizeof(bmap2));
 440
 441                         bitmap_set(bmap1, start, nbits);
 442                         __bitmap_set(bmap2, start, nbits);
 443                         if (!bitmap_equal(bmap1, bmap2, 1024)) {
 444                                 printk("set not equal %d %d\n", start, nbits);
 445                                 failed_tests++;
 446                         }
 447                         if (!__bitmap_equal(bmap1, bmap2, 1024)) {
 448                                 printk("set not __equal %d %d\n", start, nbits);
 449                                 failed_tests++;
 450                         }
 451
 452                         bitmap_clear(bmap1, start, nbits);
 453                         __bitmap_clear(bmap2, start, nbits);
 454                         if (!bitmap_equal(bmap1, bmap2, 1024)) {
 455                                 printk("clear not equal %d %d\n", start, nbits);
 456                                 failed_tests++;
 457                         }
 458                         if (!__bitmap_equal(bmap1, bmap2, 1024)) {
 459                                 printk("clear not __equal %d %d\n", start,
 460                                                                         nbits);
 461                                 failed_tests++;
 462                         }
 463                 }
 464         }
 465 }
 466
 467 static int __init test_bitmap_init(void)
 468 {
 469         test_zero_fill_copy();
 470         test_bitmap_u32_array_conversions();
 471         test_bitmap_parselist();
 472         test_mem_optimisations();
 473
 474         if (failed_tests == 0)
 475                 pr_info("all %u tests passed\n", total_tests);
 476         else
 477                 pr_warn("failed %u out of %u tests\n",
 478                         failed_tests, total_tests);
 479
 480         return failed_tests ? -EINVAL : 0;
 481 }
 482
 483 static void __exit test_bitmap_cleanup(void)
 484 {
 485 }
 486
 487 module_init(test_bitmap_init);
 488 module_exit(test_bitmap_cleanup);
 489
 490 MODULE_AUTHOR("david decotigny <david.decotigny@googlers.com>");
 491 MODULE_LICENSE("GPL");