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