t/axmap.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <inttypes.h>
   4
   5 #include "../lib/lfsr.h"
   6 #include "../lib/axmap.h"
   7
   8 static int test_regular(size_t size, int seed)
   9 {
  10         struct fio_lfsr lfsr;
  11         struct axmap *map;
  12         int err;
  13
  14         printf("Using %llu entries...", (unsigned long long) size);
  15         fflush(stdout);
  16
  17         lfsr_init(&lfsr, size, seed, seed & 0xF);
  18         map = axmap_new(size);
  19         err = 0;
  20
  21         while (size--) {
  22                 uint64_t val;
  23
  24                 if (lfsr_next(&lfsr, &val)) {
  25                         printf("lfsr: short loop\n");
  26                         err = 1;
  27                         break;
  28                 }
  29                 if (axmap_isset(map, val)) {
  30                         printf("bit already set\n");
  31                         err = 1;
  32                         break;
  33                 }
  34                 axmap_set(map, val);
  35                 if (!axmap_isset(map, val)) {
  36                         printf("bit not set\n");
  37                         err = 1;
  38                         break;
  39                 }
  40         }
  41
  42         if (err)
  43                 return err;
  44
  45         printf("pass!\n");
  46         axmap_free(map);
  47         return 0;
  48 }
  49
  50 static int check_next_free(struct axmap *map, uint64_t start, uint64_t expected)
  51 {
  52
  53         uint64_t ff;
  54
  55         ff = axmap_next_free(map, start);
  56         if (ff != expected) {
  57                 printf("axmap_next_free broken: Expected %llu, got %llu\n",
  58                                 (unsigned long long)expected, (unsigned long long) ff);
  59                 return 1;
  60         }
  61         return 0;
  62 }
  63
  64 static int test_next_free(size_t size, int seed)
  65 {
  66         struct fio_lfsr lfsr;
  67         struct axmap *map;
  68         size_t osize;
  69         uint64_t ff, lastfree;
  70         int err, i;
  71
  72         printf("Test next_free %llu entries...", (unsigned long long) size);
  73         fflush(stdout);
  74
  75         map = axmap_new(size);
  76         err = 0;
  77
  78
  79         /* Empty map.  Next free after 0 should be 1. */
  80         if (check_next_free(map, 0, 1))
  81                 err = 1;
  82
  83         /* Empty map.  Next free after 63 should be 64. */
  84         if (check_next_free(map, 63, 64))
  85                 err = 1;
  86
  87         /* Empty map.  Next free after size - 2 should be size - 1 */
  88         if (check_next_free(map, size - 2, size - 1))
  89                 err = 1;
  90
  91         /* Empty map.  Next free after size - 1 should be 0 */
  92         if (check_next_free(map, size - 1, 0))
  93                 err = 1;
  94
  95         /* Empty map.  Next free after 63 should be 64. */
  96         if (check_next_free(map, 63, 64))
  97                 err = 1;
  98
  99
 100         /* Bit 63 set.  Next free after 62 should be 64. */
 101         axmap_set(map, 63);
 102         if (check_next_free(map, 62, 64))
 103                 err = 1;
 104
 105         /* Last bit set.  Next free after size - 2 should be 0. */
 106         axmap_set(map, size - 1);
 107         if (check_next_free(map, size - 2, 0))
 108                 err = 1;
 109
 110         /* Last bit set.  Next free after size - 1 should be 0. */
 111         if (check_next_free(map, size - 1, 0))
 112                 err = 1;
 113
 114         /* Last 64 bits set.  Next free after size - 66 or size - 65 should be 0. */
 115         for (i=size - 65; i < size; i++)
 116                 axmap_set(map, i);
 117         if (check_next_free(map, size - 66, 0))
 118                 err = 1;
 119         if (check_next_free(map, size - 65, 0))
 120                 err = 1;
 121
 122         /* Last 64 bits set.  Next free after size - 67 should be size - 66. */
 123         if (check_next_free(map, size - 67, size - 66))
 124                 err = 1;
 125
 126         axmap_free(map);
 127
 128         /* Start with a fresh map and mostly fill it up */
 129         lfsr_init(&lfsr, size, seed, seed & 0xF);
 130         map = axmap_new(size);
 131         osize = size;
 132
 133         /* Leave 1 entry free */
 134         size--;
 135         while (size--) {
 136                 uint64_t val;
 137
 138                 if (lfsr_next(&lfsr, &val)) {
 139                         printf("lfsr: short loop\n");
 140                         err = 1;
 141                         break;
 142                 }
 143                 if (axmap_isset(map, val)) {
 144                         printf("bit already set\n");
 145                         err = 1;
 146                         break;
 147                 }
 148                 axmap_set(map, val);
 149                 if (!axmap_isset(map, val)) {
 150                         printf("bit not set\n");
 151                         err = 1;
 152                         break;
 153                 }
 154         }
 155
 156         /* Get last free bit */
 157         lastfree = axmap_next_free(map, 0);
 158         if (lastfree == -1ULL) {
 159                 printf("axmap_next_free broken: Couldn't find last free bit\n");
 160                 err = 1;
 161         }
 162
 163         /* Start with last free bit and test wrap-around */
 164         ff = axmap_next_free(map, lastfree);
 165         if (ff != lastfree) {
 166                 printf("axmap_next_free broken: wrap-around test #1 failed\n");
 167                 err = 1;
 168         }
 169
 170         /* Start with last bit and test wrap-around */
 171         ff = axmap_next_free(map, osize - 1);
 172         if (ff != lastfree) {
 173                 printf("axmap_next_free broken: wrap-around test #2 failed\n");
 174                 err = 1;
 175         }
 176
 177         /* Set last free bit */
 178         axmap_set(map, lastfree);
 179         ff = axmap_next_free(map, 0);
 180         if (ff != -1ULL) {
 181                 printf("axmap_next_free broken: Expected -1 from full map\n");
 182                 err = 1;
 183         }
 184
 185         ff = axmap_next_free(map, osize);
 186         if (ff != -1ULL) {
 187                 printf("axmap_next_free broken: Expected -1 from out of bounds request\n");
 188                 err = 1;
 189         }
 190
 191         if (err)
 192                 return err;
 193
 194         printf("pass!\n");
 195         axmap_free(map);
 196         return 0;
 197 }
 198
 199 static int test_multi(size_t size, unsigned int bit_off)
 200 {
 201         unsigned int map_size = size;
 202         struct axmap *map;
 203         uint64_t val = bit_off;
 204         int i, err;
 205
 206         printf("Test multi %llu entries %u offset...", (unsigned long long) size, bit_off);
 207         fflush(stdout);
 208
 209         map = axmap_new(map_size);
 210         while (val + 128 <= map_size) {
 211                 err = 0;
 212                 for (i = val; i < val + 128; i++) {
 213                         if (axmap_isset(map, val + i)) {
 214                                 printf("bit already set\n");
 215                                 err = 1;
 216                                 break;
 217                         }
 218                 }
 219
 220                 if (err)
 221                         break;
 222
 223                 err = axmap_set_nr(map, val, 128);
 224                 if (err != 128) {
 225                         printf("only set %u bits\n", err);
 226                         break;
 227                 }
 228
 229                 err = 0;
 230                 for (i = 0; i < 128; i++) {
 231                         if (!axmap_isset(map, val + i)) {
 232                                 printf("bit not set: %llu\n", (unsigned long long) val + i);
 233                                 err = 1;
 234                                 break;
 235                         }
 236                 }
 237
 238                 val += 128;
 239                 if (err)
 240                         break;
 241         }
 242
 243         if (!err)
 244                 printf("pass!\n");
 245
 246         axmap_free(map);
 247         return err;
 248 }
 249
 250 struct overlap_test {
 251         unsigned int start;
 252         unsigned int nr;
 253         unsigned int ret;
 254 };
 255
 256 static int test_overlap(void)
 257 {
 258         struct overlap_test tests[] = {
 259                 {
 260                         .start  = 0,
 261                         .nr     = 0,
 262                         .ret    = 0,
 263                 },
 264                 {
 265                         .start  = 16,
 266                         .nr     = 16,
 267                         .ret    = 16,
 268                 },
 269                 {
 270                         .start  = 16,
 271                         .nr     = 0,
 272                         .ret    = 0,
 273                 },
 274                 {
 275                         .start  = 0,
 276                         .nr     = 32,
 277                         .ret    = 16,
 278                 },
 279                 {
 280                         .start  = 48,
 281                         .nr     = 32,
 282                         .ret    = 32,
 283                 },
 284                 {
 285                         .start  = 32,
 286                         .nr     = 32,
 287                         .ret    = 16,
 288                 },
 289                 {
 290                         .start  = 79,
 291                         .nr     = 1,
 292                         .ret    = 0,
 293                 },
 294                 {
 295                         .start  = 80,
 296                         .nr     = 21,
 297                         .ret    = 21,
 298                 },
 299                 {
 300                         .start  = 102,
 301                         .nr     = 1,
 302                         .ret    = 1,
 303                 },
 304                 {
 305                         .start  = 101,
 306                         .nr     = 3,
 307                         .ret    = 1,
 308                 },
 309                 {
 310                         .start  = 106,
 311                         .nr     = 4,
 312                         .ret    = 4,
 313                 },
 314                 {
 315                         .start  = 105,
 316                         .nr     = 3,
 317                         .ret    = 1,
 318                 },
 319                 {
 320                         .start  = 120,
 321                         .nr     = 4,
 322                         .ret    = 4,
 323                 },
 324                 {
 325                         .start  = 118,
 326                         .nr     = 2,
 327                         .ret    = 2,
 328                 },
 329                 {
 330                         .start  = 118,
 331                         .nr     = 2,
 332                         .ret    = 0,
 333                 },
 334                 {
 335                         .start  = 1100,
 336                         .nr     = 1,
 337                         .ret    = 1,
 338                 },
 339                 {
 340                         .start  = 1000,
 341                         .nr     = 256,
 342                         .ret    = 100,
 343                 },
 344                 {
 345                         .start  = 22684,
 346                         .nr     = 1,
 347                         .ret    = 1,
 348                 },
 349                 {
 350                         .start  = 22670,
 351                         .nr     = 60,
 352                         .ret    = 14,
 353                 },
 354                 {
 355                         .start  = 22670,
 356                         .nr     = 60,
 357                         .ret    = 0,
 358                 },
 359                 {
 360                         .start  = -1U,
 361                 },
 362         };
 363         struct axmap *map;
 364         int entries, i, ret, err = 0;
 365
 366         entries = 0;
 367         for (i = 0; tests[i].start != -1U; i++) {
 368                 unsigned int this = tests[i].start + tests[i].nr;
 369
 370                 if (this > entries)
 371                         entries = this;
 372         }
 373
 374         printf("Test overlaps...");
 375         fflush(stdout);
 376
 377         map = axmap_new(entries);
 378
 379         for (i = 0; tests[i].start != -1U; i++) {
 380                 struct overlap_test *t = &tests[i];
 381
 382                 ret = axmap_set_nr(map, t->start, t->nr);
 383                 if (ret != t->ret) {
 384                         printf("fail\n");
 385                         printf("start=%u, nr=%d, ret=%d: %d\n", t->start, t->nr,
 386                                                                 t->ret, ret);
 387                         err = 1;
 388                         break;
 389                 }
 390         }
 391
 392         if (!err)
 393                 printf("pass!\n");
 394         axmap_free(map);
 395         return err;
 396 }
 397
 398 int main(int argc, char *argv[])
 399 {
 400         size_t size = (1UL << 23) - 200;
 401         int seed = 1;
 402
 403         if (argc > 1) {
 404                 size = strtoul(argv[1], NULL, 10);
 405                 if (argc > 2)
 406                         seed = strtoul(argv[2], NULL, 10);
 407         }
 408
 409         if (test_regular(size, seed))
 410                 return 1;
 411         if (test_multi(size, 0))
 412                 return 2;
 413         if (test_multi(size, 17))
 414                 return 3;
 415         if (test_overlap())
 416                 return 4;
 417         if (test_next_free(size, seed))
 418                 return 5;
 419
 420         /* Test 3 levels, all full:  64*64*64 */
 421         if (test_next_free(64*64*64, seed))
 422                 return 6;
 423
 424         /* Test 4 levels, with 2 inner levels not full */
 425         if (test_next_free(((((64*64)-63)*64)-63)*64*12, seed))
 426                 return 7;
 427
 428         return 0;
 429 }