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