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 static void __init test_bitmap_u32_array_conversions(void)
 169 {
 170         DECLARE_BITMAP(bmap1, 1024);
 171         DECLARE_BITMAP(bmap2, 1024);
 172         u32 exp_arr[32], arr[32];
 173         unsigned nbits;
 174
 175         for (nbits = 0 ; nbits < 257 ; ++nbits) {
 176                 const unsigned int used_u32s = DIV_ROUND_UP(nbits, 32);
 177                 unsigned int i, rv;
 178
 179                 bitmap_zero(bmap1, nbits);
 180                 bitmap_set(bmap1, nbits, 1024 - nbits);  /* garbage */
 181
 182                 memset(arr, 0xff, sizeof(arr));
 183                 rv = bitmap_to_u32array(arr, used_u32s, bmap1, nbits);
 184                 expect_eq_uint(nbits, rv);
 185
 186                 memset(exp_arr, 0xff, sizeof(exp_arr));
 187                 memset(exp_arr, 0, used_u32s*sizeof(*exp_arr));
 188                 expect_eq_u32_array(exp_arr, 32, arr, 32);
 189
 190                 bitmap_fill(bmap2, 1024);
 191                 rv = bitmap_from_u32array(bmap2, nbits, arr, used_u32s);
 192                 expect_eq_uint(nbits, rv);
 193                 expect_eq_bitmap(bmap1, 1024, bmap2, 1024);
 194
 195                 for (i = 0 ; i < nbits ; ++i) {
 196                         /*
 197                          * test conversion bitmap -> u32[]
 198                          */
 199
 200                         bitmap_zero(bmap1, 1024);
 201                         __set_bit(i, bmap1);
 202                         bitmap_set(bmap1, nbits, 1024 - nbits);  /* garbage */
 203
 204                         memset(arr, 0xff, sizeof(arr));
 205                         rv = bitmap_to_u32array(arr, used_u32s, bmap1, nbits);
 206                         expect_eq_uint(nbits, rv);
 207
 208                         /* 1st used u32 words contain expected bit set, the
 209                          * remaining words are left unchanged (0xff)
 210                          */
 211                         memset(exp_arr, 0xff, sizeof(exp_arr));
 212                         memset(exp_arr, 0, used_u32s*sizeof(*exp_arr));
 213                         exp_arr[i/32] = (1U<<(i%32));
 214                         expect_eq_u32_array(exp_arr, 32, arr, 32);
 215
 216
 217                         /* same, with longer array to fill
 218                          */
 219                         memset(arr, 0xff, sizeof(arr));
 220                         rv = bitmap_to_u32array(arr, 32, bmap1, nbits);
 221                         expect_eq_uint(nbits, rv);
 222
 223                         /* 1st used u32 words contain expected bit set, the
 224                          * remaining words are all 0s
 225                          */
 226                         memset(exp_arr, 0, sizeof(exp_arr));
 227                         exp_arr[i/32] = (1U<<(i%32));
 228                         expect_eq_u32_array(exp_arr, 32, arr, 32);
 229
 230                         /*
 231                          * test conversion u32[] -> bitmap
 232                          */
 233
 234                         /* the 1st nbits of bmap2 are identical to
 235                          * bmap1, the remaining bits of bmap2 are left
 236                          * unchanged (all 1s)
 237                          */
 238                         bitmap_fill(bmap2, 1024);
 239                         rv = bitmap_from_u32array(bmap2, nbits,
 240                                                   exp_arr, used_u32s);
 241                         expect_eq_uint(nbits, rv);
 242
 243                         expect_eq_bitmap(bmap1, 1024, bmap2, 1024);
 244
 245                         /* same, with more bits to fill
 246                          */
 247                         memset(arr, 0xff, sizeof(arr));  /* garbage */
 248                         memset(arr, 0, used_u32s*sizeof(u32));
 249                         arr[i/32] = (1U<<(i%32));
 250
 251                         bitmap_fill(bmap2, 1024);
 252                         rv = bitmap_from_u32array(bmap2, 1024, arr, used_u32s);
 253                         expect_eq_uint(used_u32s*32, rv);
 254
 255                         /* the 1st nbits of bmap2 are identical to
 256                          * bmap1, the remaining bits of bmap2 are cleared
 257                          */
 258                         bitmap_zero(bmap1, 1024);
 259                         __set_bit(i, bmap1);
 260                         expect_eq_bitmap(bmap1, 1024, bmap2, 1024);
 261
 262
 263                         /*
 264                          * test short conversion bitmap -> u32[] (1
 265                          * word too short)
 266                          */
 267                         if (used_u32s > 1) {
 268                                 bitmap_zero(bmap1, 1024);
 269                                 __set_bit(i, bmap1);
 270                                 bitmap_set(bmap1, nbits,
 271                                            1024 - nbits);  /* garbage */
 272                                 memset(arr, 0xff, sizeof(arr));
 273
 274                                 rv = bitmap_to_u32array(arr, used_u32s - 1,
 275                                                         bmap1, nbits);
 276                                 expect_eq_uint((used_u32s - 1)*32, rv);
 277
 278                                 /* 1st used u32 words contain expected
 279                                  * bit set, the remaining words are
 280                                  * left unchanged (0xff)
 281                                  */
 282                                 memset(exp_arr, 0xff, sizeof(exp_arr));
 283                                 memset(exp_arr, 0,
 284                                        (used_u32s-1)*sizeof(*exp_arr));
 285                                 if ((i/32) < (used_u32s - 1))
 286                                         exp_arr[i/32] = (1U<<(i%32));
 287                                 expect_eq_u32_array(exp_arr, 32, arr, 32);
 288                         }
 289
 290                         /*
 291                          * test short conversion u32[] -> bitmap (3
 292                          * bits too short)
 293                          */
 294                         if (nbits > 3) {
 295                                 memset(arr, 0xff, sizeof(arr));  /* garbage */
 296                                 memset(arr, 0, used_u32s*sizeof(*arr));
 297                                 arr[i/32] = (1U<<(i%32));
 298
 299                                 bitmap_zero(bmap1, 1024);
 300                                 rv = bitmap_from_u32array(bmap1, nbits - 3,
 301                                                           arr, used_u32s);
 302                                 expect_eq_uint(nbits - 3, rv);
 303
 304                                 /* we are expecting the bit < nbits -
 305                                  * 3 (none otherwise), and the rest of
 306                                  * bmap1 unchanged (0-filled)
 307                                  */
 308                                 bitmap_zero(bmap2, 1024);
 309                                 if (i < nbits - 3)
 310                                         __set_bit(i, bmap2);
 311                                 expect_eq_bitmap(bmap2, 1024, bmap1, 1024);
 312
 313                                 /* do the same with bmap1 initially
 314                                  * 1-filled
 315                                  */
 316
 317                                 bitmap_fill(bmap1, 1024);
 318                                 rv = bitmap_from_u32array(bmap1, nbits - 3,
 319                                                          arr, used_u32s);
 320                                 expect_eq_uint(nbits - 3, rv);
 321
 322                                 /* we are expecting the bit < nbits -
 323                                  * 3 (none otherwise), and the rest of
 324                                  * bmap1 unchanged (1-filled)
 325                                  */
 326                                 bitmap_zero(bmap2, 1024);
 327                                 if (i < nbits - 3)
 328                                         __set_bit(i, bmap2);
 329                                 bitmap_set(bmap2, nbits-3, 1024 - nbits + 3);
 330                                 expect_eq_bitmap(bmap2, 1024, bmap1, 1024);
 331                         }
 332                 }
 333         }
 334 }
 335
 336 static void noinline __init test_mem_optimisations(void)
 337 {
 338         DECLARE_BITMAP(bmap1, 1024);
 339         DECLARE_BITMAP(bmap2, 1024);
 340         unsigned int start, nbits;
 341
 342         for (start = 0; start < 1024; start += 8) {
 343                 memset(bmap1, 0x5a, sizeof(bmap1));
 344                 memset(bmap2, 0x5a, sizeof(bmap2));
 345                 for (nbits = 0; nbits < 1024 - start; nbits += 8) {
 346                         bitmap_set(bmap1, start, nbits);
 347                         __bitmap_set(bmap2, start, nbits);
 348                         if (!bitmap_equal(bmap1, bmap2, 1024))
 349                                 printk("set not equal %d %d\n", start, nbits);
 350                         if (!__bitmap_equal(bmap1, bmap2, 1024))
 351                                 printk("set not __equal %d %d\n", start, nbits);
 352
 353                         bitmap_clear(bmap1, start, nbits);
 354                         __bitmap_clear(bmap2, start, nbits);
 355                         if (!bitmap_equal(bmap1, bmap2, 1024))
 356                                 printk("clear not equal %d %d\n", start, nbits);
 357                         if (!__bitmap_equal(bmap1, bmap2, 1024))
 358                                 printk("clear not __equal %d %d\n", start,
 359                                                                         nbits);
 360                 }
 361         }
 362 }
 363
 364 static int __init test_bitmap_init(void)
 365 {
 366         test_zero_fill_copy();
 367         test_bitmap_u32_array_conversions();
 368         test_mem_optimisations();
 369
 370         if (failed_tests == 0)
 371                 pr_info("all %u tests passed\n", total_tests);
 372         else
 373                 pr_warn("failed %u out of %u tests\n",
 374                         failed_tests, total_tests);
 375
 376         return failed_tests ? -EINVAL : 0;
 377 }
 378
 379 static void __exit test_bitmap_cleanup(void)
 380 {
 381 }
 382
 383 module_init(test_bitmap_init);
 384 module_exit(test_bitmap_cleanup);
 385
 386 MODULE_AUTHOR("david decotigny <david.decotigny@googlers.com>");
 387 MODULE_LICENSE("GPL");