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_err("[%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, const unsigned long *bmap,
  37                   unsigned int nbits)
  38 {
  39         if (!bitmap_equal(exp_bmap, bmap, nbits)) {
  40                 pr_warn("[%s:%u] bitmaps contents differ: expected \"%*pbl\", got \"%*pbl\"\n",
  41                         srcfile, line,
  42                         nbits, exp_bmap, nbits, bmap);
  43                 return false;
  44         }
  45         return true;
  46 }
  47
  48 static bool __init
  49 __check_eq_pbl(const char *srcfile, unsigned int line,
  50                const char *expected_pbl,
  51                const unsigned long *bitmap, unsigned int nbits)
  52 {
  53         snprintf(pbl_buffer, sizeof(pbl_buffer), "%*pbl", nbits, bitmap);
  54         if (strcmp(expected_pbl, pbl_buffer)) {
  55                 pr_warn("[%s:%u] expected \"%s\", got \"%s\"\n",
  56                         srcfile, line,
  57                         expected_pbl, pbl_buffer);
  58                 return false;
  59         }
  60         return true;
  61 }
  62
  63 static bool __init
  64 __check_eq_u32_array(const char *srcfile, unsigned int line,
  65                      const u32 *exp_arr, unsigned int exp_len,
  66                      const u32 *arr, unsigned int len) __used;
  67 static bool __init
  68 __check_eq_u32_array(const char *srcfile, unsigned int line,
  69                      const u32 *exp_arr, unsigned int exp_len,
  70                      const u32 *arr, unsigned int len)
  71 {
  72         if (exp_len != len) {
  73                 pr_warn("[%s:%u] array length differ: expected %u, got %u\n",
  74                         srcfile, line,
  75                         exp_len, len);
  76                 return false;
  77         }
  78
  79         if (memcmp(exp_arr, arr, len*sizeof(*arr))) {
  80                 pr_warn("[%s:%u] array contents differ\n", srcfile, line);
  81                 print_hex_dump(KERN_WARNING, "  exp:  ", DUMP_PREFIX_OFFSET,
  82                                32, 4, exp_arr, exp_len*sizeof(*exp_arr), false);
  83                 print_hex_dump(KERN_WARNING, "  got:  ", DUMP_PREFIX_OFFSET,
  84                                32, 4, arr, len*sizeof(*arr), false);
  85                 return false;
  86         }
  87
  88         return true;
  89 }
  90
  91 #define __expect_eq(suffix, ...)                                        \
  92         ({                                                              \
  93                 int result = 0;                                         \
  94                 total_tests++;                                          \
  95                 if (!__check_eq_ ## suffix(__FILE__, __LINE__,          \
  96                                            ##__VA_ARGS__)) {            \
  97                         failed_tests++;                                 \
  98                         result = 1;                                     \
  99                 }                                                       \
 100                 result;                                                 \
 101         })
 102
 103 #define expect_eq_uint(...)             __expect_eq(uint, ##__VA_ARGS__)
 104 #define expect_eq_bitmap(...)           __expect_eq(bitmap, ##__VA_ARGS__)
 105 #define expect_eq_pbl(...)              __expect_eq(pbl, ##__VA_ARGS__)
 106 #define expect_eq_u32_array(...)        __expect_eq(u32_array, ##__VA_ARGS__)
 107
 108 static void __init test_zero_clear(void)
 109 {
 110         DECLARE_BITMAP(bmap, 1024);
 111
 112         /* Known way to set all bits */
 113         memset(bmap, 0xff, 128);
 114
 115         expect_eq_pbl("0-22", bmap, 23);
 116         expect_eq_pbl("0-1023", bmap, 1024);
 117
 118         /* single-word bitmaps */
 119         bitmap_clear(bmap, 0, 9);
 120         expect_eq_pbl("9-1023", bmap, 1024);
 121
 122         bitmap_zero(bmap, 35);
 123         expect_eq_pbl("64-1023", bmap, 1024);
 124
 125         /* cross boundaries operations */
 126         bitmap_clear(bmap, 79, 19);
 127         expect_eq_pbl("64-78,98-1023", bmap, 1024);
 128
 129         bitmap_zero(bmap, 115);
 130         expect_eq_pbl("128-1023", bmap, 1024);
 131
 132         /* Zeroing entire area */
 133         bitmap_zero(bmap, 1024);
 134         expect_eq_pbl("", bmap, 1024);
 135 }
 136
 137 static void __init test_fill_set(void)
 138 {
 139         DECLARE_BITMAP(bmap, 1024);
 140
 141         /* Known way to clear all bits */
 142         memset(bmap, 0x00, 128);
 143
 144         expect_eq_pbl("", bmap, 23);
 145         expect_eq_pbl("", bmap, 1024);
 146
 147         /* single-word bitmaps */
 148         bitmap_set(bmap, 0, 9);
 149         expect_eq_pbl("0-8", bmap, 1024);
 150
 151         bitmap_fill(bmap, 35);
 152         expect_eq_pbl("0-63", bmap, 1024);
 153
 154         /* cross boundaries operations */
 155         bitmap_set(bmap, 79, 19);
 156         expect_eq_pbl("0-63,79-97", bmap, 1024);
 157
 158         bitmap_fill(bmap, 115);
 159         expect_eq_pbl("0-127", bmap, 1024);
 160
 161         /* Zeroing entire area */
 162         bitmap_fill(bmap, 1024);
 163         expect_eq_pbl("0-1023", bmap, 1024);
 164 }
 165
 166 static void __init test_copy(void)
 167 {
 168         DECLARE_BITMAP(bmap1, 1024);
 169         DECLARE_BITMAP(bmap2, 1024);
 170
 171         bitmap_zero(bmap1, 1024);
 172         bitmap_zero(bmap2, 1024);
 173
 174         /* single-word bitmaps */
 175         bitmap_set(bmap1, 0, 19);
 176         bitmap_copy(bmap2, bmap1, 23);
 177         expect_eq_pbl("0-18", bmap2, 1024);
 178
 179         bitmap_set(bmap2, 0, 23);
 180         bitmap_copy(bmap2, bmap1, 23);
 181         expect_eq_pbl("0-18", bmap2, 1024);
 182
 183         /* multi-word bitmaps */
 184         bitmap_set(bmap1, 0, 109);
 185         bitmap_copy(bmap2, bmap1, 1024);
 186         expect_eq_pbl("0-108", bmap2, 1024);
 187
 188         bitmap_fill(bmap2, 1024);
 189         bitmap_copy(bmap2, bmap1, 1024);
 190         expect_eq_pbl("0-108", bmap2, 1024);
 191
 192         /* the following tests assume a 32- or 64-bit arch (even 128b
 193          * if we care)
 194          */
 195
 196         bitmap_fill(bmap2, 1024);
 197         bitmap_copy(bmap2, bmap1, 109);  /* ... but 0-padded til word length */
 198         expect_eq_pbl("0-108,128-1023", bmap2, 1024);
 199
 200         bitmap_fill(bmap2, 1024);
 201         bitmap_copy(bmap2, bmap1, 97);  /* ... but aligned on word length */
 202         expect_eq_pbl("0-108,128-1023", bmap2, 1024);
 203 }
 204
 205 #define PARSE_TIME 0x1
 206
 207 struct test_bitmap_parselist{
 208         const int errno;
 209         const char *in;
 210         const unsigned long *expected;
 211         const int nbits;
 212         const int flags;
 213 };
 214
 215 static const unsigned long exp[] __initconst = {
 216         BITMAP_FROM_U64(1),
 217         BITMAP_FROM_U64(2),
 218         BITMAP_FROM_U64(0x0000ffff),
 219         BITMAP_FROM_U64(0xffff0000),
 220         BITMAP_FROM_U64(0x55555555),
 221         BITMAP_FROM_U64(0xaaaaaaaa),
 222         BITMAP_FROM_U64(0x11111111),
 223         BITMAP_FROM_U64(0x22222222),
 224         BITMAP_FROM_U64(0xffffffff),
 225         BITMAP_FROM_U64(0xfffffffe),
 226         BITMAP_FROM_U64(0x3333333311111111ULL),
 227         BITMAP_FROM_U64(0xffffffff77777777ULL)
 228 };
 229
 230 static const unsigned long exp2[] __initconst = {
 231         BITMAP_FROM_U64(0x3333333311111111ULL),
 232         BITMAP_FROM_U64(0xffffffff77777777ULL)
 233 };
 234
 235 static const struct test_bitmap_parselist parselist_tests[] __initconst = {
 236 #define step (sizeof(u64) / sizeof(unsigned long))
 237
 238         {0, "0",                        &exp[0], 8, 0},
 239         {0, "1",                        &exp[1 * step], 8, 0},
 240         {0, "0-15",                     &exp[2 * step], 32, 0},
 241         {0, "16-31",                    &exp[3 * step], 32, 0},
 242         {0, "0-31:1/2",                 &exp[4 * step], 32, 0},
 243         {0, "1-31:1/2",                 &exp[5 * step], 32, 0},
 244         {0, "0-31:1/4",                 &exp[6 * step], 32, 0},
 245         {0, "1-31:1/4",                 &exp[7 * step], 32, 0},
 246         {0, "0-31:4/4",                 &exp[8 * step], 32, 0},
 247         {0, "1-31:4/4",                 &exp[9 * step], 32, 0},
 248         {0, "0-31:1/4,32-63:2/4",       &exp[10 * step], 64, 0},
 249         {0, "0-31:3/4,32-63:4/4",       &exp[11 * step], 64, 0},
 250
 251         {0, "0-31:1/4,32-63:2/4,64-95:3/4,96-127:4/4",  exp2, 128, 0},
 252
 253         {0, "0-2047:128/256", NULL, 2048, PARSE_TIME},
 254
 255         {-EINVAL, "-1", NULL, 8, 0},
 256         {-EINVAL, "-0", NULL, 8, 0},
 257         {-EINVAL, "10-1", NULL, 8, 0},
 258         {-EINVAL, "0-31:", NULL, 8, 0},
 259         {-EINVAL, "0-31:0", NULL, 8, 0},
 260         {-EINVAL, "0-31:0/0", NULL, 8, 0},
 261         {-EINVAL, "0-31:1/0", NULL, 8, 0},
 262         {-EINVAL, "0-31:10/1", NULL, 8, 0},
 263 };
 264
 265 static void __init test_bitmap_parselist(void)
 266 {
 267         int i;
 268         int err;
 269         cycles_t cycles;
 270         DECLARE_BITMAP(bmap, 2048);
 271
 272         for (i = 0; i < ARRAY_SIZE(parselist_tests); i++) {
 273 #define ptest parselist_tests[i]
 274
 275                 cycles = get_cycles();
 276                 err = bitmap_parselist(ptest.in, bmap, ptest.nbits);
 277                 cycles = get_cycles() - cycles;
 278
 279                 if (err != ptest.errno) {
 280                         pr_err("test %d: input is %s, errno is %d, expected %d\n",
 281                                         i, ptest.in, err, ptest.errno);
 282                         continue;
 283                 }
 284
 285                 if (!err && ptest.expected
 286                          && !__bitmap_equal(bmap, ptest.expected, ptest.nbits)) {
 287                         pr_err("test %d: input is %s, result is 0x%lx, expected 0x%lx\n",
 288                                         i, ptest.in, bmap[0], *ptest.expected);
 289                         continue;
 290                 }
 291
 292                 if (ptest.flags & PARSE_TIME)
 293                         pr_err("test %d: input is '%s' OK, Time: %llu\n",
 294                                         i, ptest.in,
 295                                         (unsigned long long)cycles);
 296         }
 297 }
 298
 299 #define EXP_BYTES       (sizeof(exp) * 8)
 300
 301 static void __init test_bitmap_arr32(void)
 302 {
 303         unsigned int nbits, next_bit;
 304         u32 arr[sizeof(exp) / 4];
 305         DECLARE_BITMAP(bmap2, EXP_BYTES);
 306
 307         memset(arr, 0xa5, sizeof(arr));
 308
 309         for (nbits = 0; nbits < EXP_BYTES; ++nbits) {
 310                 bitmap_to_arr32(arr, exp, nbits);
 311                 bitmap_from_arr32(bmap2, arr, nbits);
 312                 expect_eq_bitmap(bmap2, exp, nbits);
 313
 314                 next_bit = find_next_bit(bmap2,
 315                                 round_up(nbits, BITS_PER_LONG), nbits);
 316                 if (next_bit < round_up(nbits, BITS_PER_LONG))
 317                         pr_err("bitmap_copy_arr32(nbits == %d:"
 318                                 " tail is not safely cleared: %d\n",
 319                                 nbits, next_bit);
 320
 321                 if (nbits < EXP_BYTES - 32)
 322                         expect_eq_uint(arr[DIV_ROUND_UP(nbits, 32)],
 323                                                                 0xa5a5a5a5);
 324         }
 325 }
 326
 327 static void noinline __init test_mem_optimisations(void)
 328 {
 329         DECLARE_BITMAP(bmap1, 1024);
 330         DECLARE_BITMAP(bmap2, 1024);
 331         unsigned int start, nbits;
 332
 333         for (start = 0; start < 1024; start += 8) {
 334                 memset(bmap1, 0x5a, sizeof(bmap1));
 335                 memset(bmap2, 0x5a, sizeof(bmap2));
 336                 for (nbits = 0; nbits < 1024 - start; nbits += 8) {
 337                         bitmap_set(bmap1, start, nbits);
 338                         __bitmap_set(bmap2, start, nbits);
 339                         if (!bitmap_equal(bmap1, bmap2, 1024))
 340                                 printk("set not equal %d %d\n", start, nbits);
 341                         if (!__bitmap_equal(bmap1, bmap2, 1024))
 342                                 printk("set not __equal %d %d\n", start, nbits);
 343
 344                         bitmap_clear(bmap1, start, nbits);
 345                         __bitmap_clear(bmap2, start, nbits);
 346                         if (!bitmap_equal(bmap1, bmap2, 1024))
 347                                 printk("clear not equal %d %d\n", start, nbits);
 348                         if (!__bitmap_equal(bmap1, bmap2, 1024))
 349                                 printk("clear not __equal %d %d\n", start,
 350                                                                         nbits);
 351                 }
 352         }
 353 }
 354
 355 static int __init test_bitmap_init(void)
 356 {
 357         test_zero_clear();
 358         test_fill_set();
 359         test_copy();
 360         test_bitmap_arr32();
 361         test_bitmap_parselist();
 362         test_mem_optimisations();
 363
 364         if (failed_tests == 0)
 365                 pr_info("all %u tests passed\n", total_tests);
 366         else
 367                 pr_warn("failed %u out of %u tests\n",
 368                         failed_tests, total_tests);
 369
 370         return failed_tests ? -EINVAL : 0;
 371 }
 372
 373 static void __exit test_bitmap_cleanup(void)
 374 {
 375 }
 376
 377 module_init(test_bitmap_init);
 378 module_exit(test_bitmap_cleanup);
 379
 380 MODULE_AUTHOR("david decotigny <david.decotigny@googlers.com>");
 381 MODULE_LICENSE("GPL");