tests/test-hbitmap.c

   1 /*
   2  * Hierarchical bitmap unit-tests.
   3  *
   4  * Copyright (C) 2012 Red Hat Inc.
   5  *
   6  * Author: Paolo Bonzini <pbonzini@redhat.com>
   7  *
   8  * This work is licensed under the terms of the GNU GPL, version 2 or later.
   9  * See the COPYING file in the top-level directory.
  10  */
  11
  12 #include "qemu/osdep.h"
  13 #include "qemu/hbitmap.h"
  14 #include "qemu/bitmap.h"
  15 #include "block/block.h"
  16
  17 #define LOG_BITS_PER_LONG          (BITS_PER_LONG == 32 ? 5 : 6)
  18
  19 #define L1                         BITS_PER_LONG
  20 #define L2                         (BITS_PER_LONG * L1)
  21 #define L3                         (BITS_PER_LONG * L2)
  22
  23 typedef struct TestHBitmapData {
  24     HBitmap       *hb;
  25     HBitmap       *meta;
  26     unsigned long *bits;
  27     size_t         size;
  28     size_t         old_size;
  29     int            granularity;
  30 } TestHBitmapData;
  31
  32
  33 /* Check that the HBitmap and the shadow bitmap contain the same data,
  34  * ignoring the same "first" bits.
  35  */
  36 static void hbitmap_test_check(TestHBitmapData *data,
  37                                uint64_t first)
  38 {
  39     uint64_t count = 0;
  40     size_t pos;
  41     int bit;
  42     HBitmapIter hbi;
  43     int64_t i, next;
  44
  45     hbitmap_iter_init(&hbi, data->hb, first);
  46
  47     i = first;
  48     for (;;) {
  49         next = hbitmap_iter_next(&hbi);
  50         if (next < 0) {
  51             next = data->size;
  52         }
  53
  54         while (i < next) {
  55             pos = i >> LOG_BITS_PER_LONG;
  56             bit = i & (BITS_PER_LONG - 1);
  57             i++;
  58             g_assert_cmpint(data->bits[pos] & (1UL << bit), ==, 0);
  59         }
  60
  61         if (next == data->size) {
  62             break;
  63         }
  64
  65         pos = i >> LOG_BITS_PER_LONG;
  66         bit = i & (BITS_PER_LONG - 1);
  67         i++;
  68         count++;
  69         g_assert_cmpint(data->bits[pos] & (1UL << bit), !=, 0);
  70     }
  71
  72     if (first == 0) {
  73         g_assert_cmpint(count << data->granularity, ==, hbitmap_count(data->hb));
  74     }
  75 }
  76
  77 /* This is provided instead of a test setup function so that the sizes
  78    are kept in the test functions (and not in main()) */
  79 static void hbitmap_test_init(TestHBitmapData *data,
  80                               uint64_t size, int granularity)
  81 {
  82     size_t n;
  83     data->hb = hbitmap_alloc(size, granularity);
  84
  85     n = DIV_ROUND_UP(size, BITS_PER_LONG);
  86     if (n == 0) {
  87         n = 1;
  88     }
  89     data->bits = g_new0(unsigned long, n);
  90     data->size = size;
  91     data->granularity = granularity;
  92     if (size) {
  93         hbitmap_test_check(data, 0);
  94     }
  95 }
  96
  97 static void hbitmap_test_init_meta(TestHBitmapData *data,
  98                                    uint64_t size, int granularity,
  99                                    int meta_chunk)
 100 {
 101     hbitmap_test_init(data, size, granularity);
 102     data->meta = hbitmap_create_meta(data->hb, meta_chunk);
 103 }
 104
 105 static inline size_t hbitmap_test_array_size(size_t bits)
 106 {
 107     size_t n = DIV_ROUND_UP(bits, BITS_PER_LONG);
 108     return n ? n : 1;
 109 }
 110
 111 static void hbitmap_test_truncate_impl(TestHBitmapData *data,
 112                                        size_t size)
 113 {
 114     size_t n;
 115     size_t m;
 116     data->old_size = data->size;
 117     data->size = size;
 118
 119     if (data->size == data->old_size) {
 120         return;
 121     }
 122
 123     n = hbitmap_test_array_size(size);
 124     m = hbitmap_test_array_size(data->old_size);
 125     data->bits = g_realloc(data->bits, sizeof(unsigned long) * n);
 126     if (n > m) {
 127         memset(&data->bits[m], 0x00, sizeof(unsigned long) * (n - m));
 128     }
 129
 130     /* If we shrink to an uneven multiple of sizeof(unsigned long),
 131      * scrub the leftover memory. */
 132     if (data->size < data->old_size) {
 133         m = size % (sizeof(unsigned long) * 8);
 134         if (m) {
 135             unsigned long mask = (1ULL << m) - 1;
 136             data->bits[n-1] &= mask;
 137         }
 138     }
 139
 140     hbitmap_truncate(data->hb, size);
 141 }
 142
 143 static void hbitmap_test_teardown(TestHBitmapData *data,
 144                                   const void *unused)
 145 {
 146     if (data->hb) {
 147         if (data->meta) {
 148             hbitmap_free_meta(data->hb);
 149         }
 150         hbitmap_free(data->hb);
 151         data->hb = NULL;
 152     }
 153     g_free(data->bits);
 154     data->bits = NULL;
 155 }
 156
 157 /* Set a range in the HBitmap and in the shadow "simple" bitmap.
 158  * The two bitmaps are then tested against each other.
 159  */
 160 static void hbitmap_test_set(TestHBitmapData *data,
 161                              uint64_t first, uint64_t count)
 162 {
 163     hbitmap_set(data->hb, first, count);
 164     while (count-- != 0) {
 165         size_t pos = first >> LOG_BITS_PER_LONG;
 166         int bit = first & (BITS_PER_LONG - 1);
 167         first++;
 168
 169         data->bits[pos] |= 1UL << bit;
 170     }
 171
 172     if (data->granularity == 0) {
 173         hbitmap_test_check(data, 0);
 174     }
 175 }
 176
 177 /* Reset a range in the HBitmap and in the shadow "simple" bitmap.
 178  */
 179 static void hbitmap_test_reset(TestHBitmapData *data,
 180                                uint64_t first, uint64_t count)
 181 {
 182     hbitmap_reset(data->hb, first, count);
 183     while (count-- != 0) {
 184         size_t pos = first >> LOG_BITS_PER_LONG;
 185         int bit = first & (BITS_PER_LONG - 1);
 186         first++;
 187
 188         data->bits[pos] &= ~(1UL << bit);
 189     }
 190
 191     if (data->granularity == 0) {
 192         hbitmap_test_check(data, 0);
 193     }
 194 }
 195
 196 static void hbitmap_test_reset_all(TestHBitmapData *data)
 197 {
 198     size_t n;
 199
 200     hbitmap_reset_all(data->hb);
 201
 202     n = DIV_ROUND_UP(data->size, BITS_PER_LONG);
 203     if (n == 0) {
 204         n = 1;
 205     }
 206     memset(data->bits, 0, n * sizeof(unsigned long));
 207
 208     if (data->granularity == 0) {
 209         hbitmap_test_check(data, 0);
 210     }
 211 }
 212
 213 static void hbitmap_test_check_get(TestHBitmapData *data)
 214 {
 215     uint64_t count = 0;
 216     uint64_t i;
 217
 218     for (i = 0; i < data->size; i++) {
 219         size_t pos = i >> LOG_BITS_PER_LONG;
 220         int bit = i & (BITS_PER_LONG - 1);
 221         unsigned long val = data->bits[pos] & (1UL << bit);
 222         count += hbitmap_get(data->hb, i);
 223         g_assert_cmpint(hbitmap_get(data->hb, i), ==, val != 0);
 224     }
 225     g_assert_cmpint(count, ==, hbitmap_count(data->hb));
 226 }
 227
 228 static void test_hbitmap_zero(TestHBitmapData *data,
 229                                const void *unused)
 230 {
 231     hbitmap_test_init(data, 0, 0);
 232 }
 233
 234 static void test_hbitmap_unaligned(TestHBitmapData *data,
 235                                    const void *unused)
 236 {
 237     hbitmap_test_init(data, L3 + 23, 0);
 238     hbitmap_test_set(data, 0, 1);
 239     hbitmap_test_set(data, L3 + 22, 1);
 240 }
 241
 242 static void test_hbitmap_iter_empty(TestHBitmapData *data,
 243                                     const void *unused)
 244 {
 245     hbitmap_test_init(data, L1, 0);
 246 }
 247
 248 static void test_hbitmap_iter_partial(TestHBitmapData *data,
 249                                       const void *unused)
 250 {
 251     hbitmap_test_init(data, L3, 0);
 252     hbitmap_test_set(data, 0, L3);
 253     hbitmap_test_check(data, 1);
 254     hbitmap_test_check(data, L1 - 1);
 255     hbitmap_test_check(data, L1);
 256     hbitmap_test_check(data, L1 * 2 - 1);
 257     hbitmap_test_check(data, L2 - 1);
 258     hbitmap_test_check(data, L2);
 259     hbitmap_test_check(data, L2 + 1);
 260     hbitmap_test_check(data, L2 + L1);
 261     hbitmap_test_check(data, L2 + L1 * 2 - 1);
 262     hbitmap_test_check(data, L2 * 2 - 1);
 263     hbitmap_test_check(data, L2 * 2);
 264     hbitmap_test_check(data, L2 * 2 + 1);
 265     hbitmap_test_check(data, L2 * 2 + L1);
 266     hbitmap_test_check(data, L2 * 2 + L1 * 2 - 1);
 267     hbitmap_test_check(data, L3 / 2);
 268 }
 269
 270 static void test_hbitmap_set_all(TestHBitmapData *data,
 271                                  const void *unused)
 272 {
 273     hbitmap_test_init(data, L3, 0);
 274     hbitmap_test_set(data, 0, L3);
 275 }
 276
 277 static void test_hbitmap_get_all(TestHBitmapData *data,
 278                                  const void *unused)
 279 {
 280     hbitmap_test_init(data, L3, 0);
 281     hbitmap_test_set(data, 0, L3);
 282     hbitmap_test_check_get(data);
 283 }
 284
 285 static void test_hbitmap_get_some(TestHBitmapData *data,
 286                                   const void *unused)
 287 {
 288     hbitmap_test_init(data, 2 * L2, 0);
 289     hbitmap_test_set(data, 10, 1);
 290     hbitmap_test_check_get(data);
 291     hbitmap_test_set(data, L1 - 1, 1);
 292     hbitmap_test_check_get(data);
 293     hbitmap_test_set(data, L1, 1);
 294     hbitmap_test_check_get(data);
 295     hbitmap_test_set(data, L2 - 1, 1);
 296     hbitmap_test_check_get(data);
 297     hbitmap_test_set(data, L2, 1);
 298     hbitmap_test_check_get(data);
 299 }
 300
 301 static void test_hbitmap_set_one(TestHBitmapData *data,
 302                                  const void *unused)
 303 {
 304     hbitmap_test_init(data, 2 * L2, 0);
 305     hbitmap_test_set(data, 10, 1);
 306     hbitmap_test_set(data, L1 - 1, 1);
 307     hbitmap_test_set(data, L1, 1);
 308     hbitmap_test_set(data, L2 - 1, 1);
 309     hbitmap_test_set(data, L2, 1);
 310 }
 311
 312 static void test_hbitmap_set_two_elem(TestHBitmapData *data,
 313                                       const void *unused)
 314 {
 315     hbitmap_test_init(data, 2 * L2, 0);
 316     hbitmap_test_set(data, L1 - 1, 2);
 317     hbitmap_test_set(data, L1 * 2 - 1, 4);
 318     hbitmap_test_set(data, L1 * 4, L1 + 1);
 319     hbitmap_test_set(data, L1 * 8 - 1, L1 + 1);
 320     hbitmap_test_set(data, L2 - 1, 2);
 321     hbitmap_test_set(data, L2 + L1 - 1, 8);
 322     hbitmap_test_set(data, L2 + L1 * 4, L1 + 1);
 323     hbitmap_test_set(data, L2 + L1 * 8 - 1, L1 + 1);
 324 }
 325
 326 static void test_hbitmap_set(TestHBitmapData *data,
 327                              const void *unused)
 328 {
 329     hbitmap_test_init(data, L3 * 2, 0);
 330     hbitmap_test_set(data, L1 - 1, L1 + 2);
 331     hbitmap_test_set(data, L1 * 3 - 1, L1 + 2);
 332     hbitmap_test_set(data, L1 * 5, L1 * 2 + 1);
 333     hbitmap_test_set(data, L1 * 8 - 1, L1 * 2 + 1);
 334     hbitmap_test_set(data, L2 - 1, L1 + 2);
 335     hbitmap_test_set(data, L2 + L1 * 2 - 1, L1 + 2);
 336     hbitmap_test_set(data, L2 + L1 * 4, L1 * 2 + 1);
 337     hbitmap_test_set(data, L2 + L1 * 7 - 1, L1 * 2 + 1);
 338     hbitmap_test_set(data, L2 * 2 - 1, L3 * 2 - L2 * 2);
 339 }
 340
 341 static void test_hbitmap_set_twice(TestHBitmapData *data,
 342                                    const void *unused)
 343 {
 344     hbitmap_test_init(data, L1 * 3, 0);
 345     hbitmap_test_set(data, 0, L1 * 3);
 346     hbitmap_test_set(data, L1, 1);
 347 }
 348
 349 static void test_hbitmap_set_overlap(TestHBitmapData *data,
 350                                      const void *unused)
 351 {
 352     hbitmap_test_init(data, L3 * 2, 0);
 353     hbitmap_test_set(data, L1 - 1, L1 + 2);
 354     hbitmap_test_set(data, L1 * 2 - 1, L1 * 2 + 2);
 355     hbitmap_test_set(data, 0, L1 * 3);
 356     hbitmap_test_set(data, L1 * 8 - 1, L2);
 357     hbitmap_test_set(data, L2, L1);
 358     hbitmap_test_set(data, L2 - L1 - 1, L1 * 8 + 2);
 359     hbitmap_test_set(data, L2, L3 - L2 + 1);
 360     hbitmap_test_set(data, L3 - L1, L1 * 3);
 361     hbitmap_test_set(data, L3 - 1, 3);
 362     hbitmap_test_set(data, L3 - 1, L2);
 363 }
 364
 365 static void test_hbitmap_reset_empty(TestHBitmapData *data,
 366                                      const void *unused)
 367 {
 368     hbitmap_test_init(data, L3, 0);
 369     hbitmap_test_reset(data, 0, L3);
 370 }
 371
 372 static void test_hbitmap_reset(TestHBitmapData *data,
 373                                const void *unused)
 374 {
 375     hbitmap_test_init(data, L3 * 2, 0);
 376     hbitmap_test_set(data, L1 - 1, L1 + 2);
 377     hbitmap_test_reset(data, L1 * 2 - 1, L1 * 2 + 2);
 378     hbitmap_test_set(data, 0, L1 * 3);
 379     hbitmap_test_reset(data, L1 * 8 - 1, L2);
 380     hbitmap_test_set(data, L2, L1);
 381     hbitmap_test_reset(data, L2 - L1 - 1, L1 * 8 + 2);
 382     hbitmap_test_set(data, L2, L3 - L2 + 1);
 383     hbitmap_test_reset(data, L3 - L1, L1 * 3);
 384     hbitmap_test_set(data, L3 - 1, 3);
 385     hbitmap_test_reset(data, L3 - 1, L2);
 386     hbitmap_test_set(data, 0, L3 * 2);
 387     hbitmap_test_reset(data, 0, L1);
 388     hbitmap_test_reset(data, 0, L2);
 389     hbitmap_test_reset(data, L3, L3);
 390     hbitmap_test_set(data, L3 / 2, L3);
 391 }
 392
 393 static void test_hbitmap_reset_all(TestHBitmapData *data,
 394                                    const void *unused)
 395 {
 396     hbitmap_test_init(data, L3 * 2, 0);
 397     hbitmap_test_set(data, L1 - 1, L1 + 2);
 398     hbitmap_test_reset_all(data);
 399     hbitmap_test_set(data, 0, L1 * 3);
 400     hbitmap_test_reset_all(data);
 401     hbitmap_test_set(data, L2, L1);
 402     hbitmap_test_reset_all(data);
 403     hbitmap_test_set(data, L2, L3 - L2 + 1);
 404     hbitmap_test_reset_all(data);
 405     hbitmap_test_set(data, L3 - 1, 3);
 406     hbitmap_test_reset_all(data);
 407     hbitmap_test_set(data, 0, L3 * 2);
 408     hbitmap_test_reset_all(data);
 409     hbitmap_test_set(data, L3 / 2, L3);
 410     hbitmap_test_reset_all(data);
 411 }
 412
 413 static void test_hbitmap_granularity(TestHBitmapData *data,
 414                                      const void *unused)
 415 {
 416     /* Note that hbitmap_test_check has to be invoked manually in this test.  */
 417     hbitmap_test_init(data, L1, 1);
 418     hbitmap_test_set(data, 0, 1);
 419     g_assert_cmpint(hbitmap_count(data->hb), ==, 2);
 420     hbitmap_test_check(data, 0);
 421     hbitmap_test_set(data, 2, 1);
 422     g_assert_cmpint(hbitmap_count(data->hb), ==, 4);
 423     hbitmap_test_check(data, 0);
 424     hbitmap_test_set(data, 0, 3);
 425     g_assert_cmpint(hbitmap_count(data->hb), ==, 4);
 426     hbitmap_test_reset(data, 0, 1);
 427     g_assert_cmpint(hbitmap_count(data->hb), ==, 2);
 428 }
 429
 430 static void test_hbitmap_iter_granularity(TestHBitmapData *data,
 431                                           const void *unused)
 432 {
 433     HBitmapIter hbi;
 434
 435     /* Note that hbitmap_test_check has to be invoked manually in this test.  */
 436     hbitmap_test_init(data, 131072 << 7, 7);
 437     hbitmap_iter_init(&hbi, data->hb, 0);
 438     g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
 439
 440     hbitmap_test_set(data, ((L2 + L1 + 1) << 7) + 8, 8);
 441     hbitmap_iter_init(&hbi, data->hb, 0);
 442     g_assert_cmpint(hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7);
 443     g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
 444
 445     hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7);
 446     g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
 447
 448     hbitmap_test_set(data, (131072 << 7) - 8, 8);
 449     hbitmap_iter_init(&hbi, data->hb, 0);
 450     g_assert_cmpint(hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7);
 451     g_assert_cmpint(hbitmap_iter_next(&hbi), ==, 131071 << 7);
 452     g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
 453
 454     hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7);
 455     g_assert_cmpint(hbitmap_iter_next(&hbi), ==, 131071 << 7);
 456     g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
 457 }
 458
 459 static void hbitmap_test_set_boundary_bits(TestHBitmapData *data, ssize_t diff)
 460 {
 461     size_t size = data->size;
 462
 463     /* First bit */
 464     hbitmap_test_set(data, 0, 1);
 465     if (diff < 0) {
 466         /* Last bit in new, shortened map */
 467         hbitmap_test_set(data, size + diff - 1, 1);
 468
 469         /* First bit to be truncated away */
 470         hbitmap_test_set(data, size + diff, 1);
 471     }
 472     /* Last bit */
 473     hbitmap_test_set(data, size - 1, 1);
 474     if (data->granularity == 0) {
 475         hbitmap_test_check_get(data);
 476     }
 477 }
 478
 479 static void hbitmap_test_check_boundary_bits(TestHBitmapData *data)
 480 {
 481     size_t size = MIN(data->size, data->old_size);
 482
 483     if (data->granularity == 0) {
 484         hbitmap_test_check_get(data);
 485         hbitmap_test_check(data, 0);
 486     } else {
 487         /* If a granularity was set, note that every distinct
 488          * (bit >> granularity) value that was set will increase
 489          * the bit pop count by 2^granularity, not just 1.
 490          *
 491          * The hbitmap_test_check facility does not currently tolerate
 492          * non-zero granularities, so test the boundaries and the population
 493          * count manually.
 494          */
 495         g_assert(hbitmap_get(data->hb, 0));
 496         g_assert(hbitmap_get(data->hb, size - 1));
 497         g_assert_cmpint(2 << data->granularity, ==, hbitmap_count(data->hb));
 498     }
 499 }
 500
 501 /* Generic truncate test. */
 502 static void hbitmap_test_truncate(TestHBitmapData *data,
 503                                   size_t size,
 504                                   ssize_t diff,
 505                                   int granularity)
 506 {
 507     hbitmap_test_init(data, size, granularity);
 508     hbitmap_test_set_boundary_bits(data, diff);
 509     hbitmap_test_truncate_impl(data, size + diff);
 510     hbitmap_test_check_boundary_bits(data);
 511 }
 512
 513 static void test_hbitmap_truncate_nop(TestHBitmapData *data,
 514                                       const void *unused)
 515 {
 516     hbitmap_test_truncate(data, L2, 0, 0);
 517 }
 518
 519 /**
 520  * Grow by an amount smaller than the granularity, without crossing
 521  * a granularity alignment boundary. Effectively a NOP.
 522  */
 523 static void test_hbitmap_truncate_grow_negligible(TestHBitmapData *data,
 524                                                   const void *unused)
 525 {
 526     size_t size = L2 - 1;
 527     size_t diff = 1;
 528     int granularity = 1;
 529
 530     hbitmap_test_truncate(data, size, diff, granularity);
 531 }
 532
 533 /**
 534  * Shrink by an amount smaller than the granularity, without crossing
 535  * a granularity alignment boundary. Effectively a NOP.
 536  */
 537 static void test_hbitmap_truncate_shrink_negligible(TestHBitmapData *data,
 538                                                     const void *unused)
 539 {
 540     size_t size = L2;
 541     ssize_t diff = -1;
 542     int granularity = 1;
 543
 544     hbitmap_test_truncate(data, size, diff, granularity);
 545 }
 546
 547 /**
 548  * Grow by an amount smaller than the granularity, but crossing over
 549  * a granularity alignment boundary.
 550  */
 551 static void test_hbitmap_truncate_grow_tiny(TestHBitmapData *data,
 552                                             const void *unused)
 553 {
 554     size_t size = L2 - 2;
 555     ssize_t diff = 1;
 556     int granularity = 1;
 557
 558     hbitmap_test_truncate(data, size, diff, granularity);
 559 }
 560
 561 /**
 562  * Shrink by an amount smaller than the granularity, but crossing over
 563  * a granularity alignment boundary.
 564  */
 565 static void test_hbitmap_truncate_shrink_tiny(TestHBitmapData *data,
 566                                               const void *unused)
 567 {
 568     size_t size = L2 - 1;
 569     ssize_t diff = -1;
 570     int granularity = 1;
 571
 572     hbitmap_test_truncate(data, size, diff, granularity);
 573 }
 574
 575 /**
 576  * Grow by an amount smaller than sizeof(long), and not crossing over
 577  * a sizeof(long) alignment boundary.
 578  */
 579 static void test_hbitmap_truncate_grow_small(TestHBitmapData *data,
 580                                              const void *unused)
 581 {
 582     size_t size = L2 + 1;
 583     size_t diff = sizeof(long) / 2;
 584
 585     hbitmap_test_truncate(data, size, diff, 0);
 586 }
 587
 588 /**
 589  * Shrink by an amount smaller than sizeof(long), and not crossing over
 590  * a sizeof(long) alignment boundary.
 591  */
 592 static void test_hbitmap_truncate_shrink_small(TestHBitmapData *data,
 593                                                const void *unused)
 594 {
 595     size_t size = L2;
 596     size_t diff = sizeof(long) / 2;
 597
 598     hbitmap_test_truncate(data, size, -diff, 0);
 599 }
 600
 601 /**
 602  * Grow by an amount smaller than sizeof(long), while crossing over
 603  * a sizeof(long) alignment boundary.
 604  */
 605 static void test_hbitmap_truncate_grow_medium(TestHBitmapData *data,
 606                                               const void *unused)
 607 {
 608     size_t size = L2 - 1;
 609     size_t diff = sizeof(long) / 2;
 610
 611     hbitmap_test_truncate(data, size, diff, 0);
 612 }
 613
 614 /**
 615  * Shrink by an amount smaller than sizeof(long), while crossing over
 616  * a sizeof(long) alignment boundary.
 617  */
 618 static void test_hbitmap_truncate_shrink_medium(TestHBitmapData *data,
 619                                                 const void *unused)
 620 {
 621     size_t size = L2 + 1;
 622     size_t diff = sizeof(long) / 2;
 623
 624     hbitmap_test_truncate(data, size, -diff, 0);
 625 }
 626
 627 /**
 628  * Grow by an amount larger than sizeof(long).
 629  */
 630 static void test_hbitmap_truncate_grow_large(TestHBitmapData *data,
 631                                              const void *unused)
 632 {
 633     size_t size = L2;
 634     size_t diff = 8 * sizeof(long);
 635
 636     hbitmap_test_truncate(data, size, diff, 0);
 637 }
 638
 639 /**
 640  * Shrink by an amount larger than sizeof(long).
 641  */
 642 static void test_hbitmap_truncate_shrink_large(TestHBitmapData *data,
 643                                                const void *unused)
 644 {
 645     size_t size = L2;
 646     size_t diff = 8 * sizeof(long);
 647
 648     hbitmap_test_truncate(data, size, -diff, 0);
 649 }
 650
 651 static void hbitmap_check_meta(TestHBitmapData *data,
 652                                int64_t start, int count)
 653 {
 654     int64_t i;
 655
 656     for (i = 0; i < data->size; i++) {
 657         if (i >= start && i < start + count) {
 658             g_assert(hbitmap_get(data->meta, i));
 659         } else {
 660             g_assert(!hbitmap_get(data->meta, i));
 661         }
 662     }
 663 }
 664
 665 static void hbitmap_test_meta(TestHBitmapData *data,
 666                               int64_t start, int count,
 667                               int64_t check_start, int check_count)
 668 {
 669     hbitmap_reset_all(data->hb);
 670     hbitmap_reset_all(data->meta);
 671
 672     /* Test "unset" -> "unset" will not update meta. */
 673     hbitmap_reset(data->hb, start, count);
 674     hbitmap_check_meta(data, 0, 0);
 675
 676     /* Test "unset" -> "set" will update meta */
 677     hbitmap_set(data->hb, start, count);
 678     hbitmap_check_meta(data, check_start, check_count);
 679
 680     /* Test "set" -> "set" will not update meta */
 681     hbitmap_reset_all(data->meta);
 682     hbitmap_set(data->hb, start, count);
 683     hbitmap_check_meta(data, 0, 0);
 684
 685     /* Test "set" -> "unset" will update meta */
 686     hbitmap_reset_all(data->meta);
 687     hbitmap_reset(data->hb, start, count);
 688     hbitmap_check_meta(data, check_start, check_count);
 689 }
 690
 691 static void hbitmap_test_meta_do(TestHBitmapData *data, int chunk_size)
 692 {
 693     uint64_t size = chunk_size * 100;
 694     hbitmap_test_init_meta(data, size, 0, chunk_size);
 695
 696     hbitmap_test_meta(data, 0, 1, 0, chunk_size);
 697     hbitmap_test_meta(data, 0, chunk_size, 0, chunk_size);
 698     hbitmap_test_meta(data, chunk_size - 1, 1, 0, chunk_size);
 699     hbitmap_test_meta(data, chunk_size - 1, 2, 0, chunk_size * 2);
 700     hbitmap_test_meta(data, chunk_size - 1, chunk_size + 1, 0, chunk_size * 2);
 701     hbitmap_test_meta(data, chunk_size - 1, chunk_size + 2, 0, chunk_size * 3);
 702     hbitmap_test_meta(data, 7 * chunk_size - 1, chunk_size + 2,
 703                       6 * chunk_size, chunk_size * 3);
 704     hbitmap_test_meta(data, size - 1, 1, size - chunk_size, chunk_size);
 705     hbitmap_test_meta(data, 0, size, 0, size);
 706 }
 707
 708 static void test_hbitmap_meta_byte(TestHBitmapData *data, const void *unused)
 709 {
 710     hbitmap_test_meta_do(data, BITS_PER_BYTE);
 711 }
 712
 713 static void test_hbitmap_meta_word(TestHBitmapData *data, const void *unused)
 714 {
 715     hbitmap_test_meta_do(data, BITS_PER_LONG);
 716 }
 717
 718 static void test_hbitmap_meta_sector(TestHBitmapData *data, const void *unused)
 719 {
 720     hbitmap_test_meta_do(data, BDRV_SECTOR_SIZE * BITS_PER_BYTE);
 721 }
 722
 723 /**
 724  * Create an HBitmap and test set/unset.
 725  */
 726 static void test_hbitmap_meta_one(TestHBitmapData *data, const void *unused)
 727 {
 728     int i;
 729     int64_t offsets[] = {
 730         0, 1, L1 - 1, L1, L1 + 1, L2 - 1, L2, L2 + 1, L3 - 1, L3, L3 + 1
 731     };
 732
 733     hbitmap_test_init_meta(data, L3 * 2, 0, 1);
 734     for (i = 0; i < ARRAY_SIZE(offsets); i++) {
 735         hbitmap_test_meta(data, offsets[i], 1, offsets[i], 1);
 736         hbitmap_test_meta(data, offsets[i], L1, offsets[i], L1);
 737         hbitmap_test_meta(data, offsets[i], L2, offsets[i], L2);
 738     }
 739 }
 740
 741 static void test_hbitmap_serialize_align(TestHBitmapData *data,
 742                                          const void *unused)
 743 {
 744     int r;
 745
 746     hbitmap_test_init(data, L3 * 2, 3);
 747     g_assert(hbitmap_is_serializable(data->hb));
 748
 749     r = hbitmap_serialization_align(data->hb);
 750     g_assert_cmpint(r, ==, 64 << 3);
 751 }
 752
 753 static void test_hbitmap_meta_zero(TestHBitmapData *data, const void *unused)
 754 {
 755     hbitmap_test_init_meta(data, 0, 0, 1);
 756
 757     hbitmap_check_meta(data, 0, 0);
 758 }
 759
 760 static void hbitmap_test_serialize_range(TestHBitmapData *data,
 761                                          uint8_t *buf, size_t buf_size,
 762                                          uint64_t pos, uint64_t count)
 763 {
 764     size_t i;
 765     unsigned long *el = (unsigned long *)buf;
 766
 767     assert(hbitmap_granularity(data->hb) == 0);
 768     hbitmap_reset_all(data->hb);
 769     memset(buf, 0, buf_size);
 770     if (count) {
 771         hbitmap_set(data->hb, pos, count);
 772     }
 773
 774     g_assert(hbitmap_is_serializable(data->hb));
 775     hbitmap_serialize_part(data->hb, buf, 0, data->size);
 776
 777     /* Serialized buffer is inherently LE, convert it back manually to test */
 778     for (i = 0; i < buf_size / sizeof(unsigned long); i++) {
 779         el[i] = (BITS_PER_LONG == 32 ? le32_to_cpu(el[i]) : le64_to_cpu(el[i]));
 780     }
 781
 782     for (i = 0; i < data->size; i++) {
 783         int is_set = test_bit(i, (unsigned long *)buf);
 784         if (i >= pos && i < pos + count) {
 785             g_assert(is_set);
 786         } else {
 787             g_assert(!is_set);
 788         }
 789     }
 790
 791     /* Re-serialize for deserialization testing */
 792     memset(buf, 0, buf_size);
 793     hbitmap_serialize_part(data->hb, buf, 0, data->size);
 794     hbitmap_reset_all(data->hb);
 795
 796     g_assert(hbitmap_is_serializable(data->hb));
 797     hbitmap_deserialize_part(data->hb, buf, 0, data->size, true);
 798
 799     for (i = 0; i < data->size; i++) {
 800         int is_set = hbitmap_get(data->hb, i);
 801         if (i >= pos && i < pos + count) {
 802             g_assert(is_set);
 803         } else {
 804             g_assert(!is_set);
 805         }
 806     }
 807 }
 808
 809 static void test_hbitmap_serialize_basic(TestHBitmapData *data,
 810                                          const void *unused)
 811 {
 812     int i, j;
 813     size_t buf_size;
 814     uint8_t *buf;
 815     uint64_t positions[] = { 0, 1, L1 - 1, L1, L2 - 1, L2, L2 + 1, L3 - 1 };
 816     int num_positions = ARRAY_SIZE(positions);
 817
 818     hbitmap_test_init(data, L3, 0);
 819     g_assert(hbitmap_is_serializable(data->hb));
 820     buf_size = hbitmap_serialization_size(data->hb, 0, data->size);
 821     buf = g_malloc0(buf_size);
 822
 823     for (i = 0; i < num_positions; i++) {
 824         for (j = 0; j < num_positions; j++) {
 825             hbitmap_test_serialize_range(data, buf, buf_size,
 826                                          positions[i],
 827                                          MIN(positions[j], L3 - positions[i]));
 828         }
 829     }
 830
 831     g_free(buf);
 832 }
 833
 834 static void test_hbitmap_serialize_part(TestHBitmapData *data,
 835                                         const void *unused)
 836 {
 837     int i, j, k;
 838     size_t buf_size;
 839     uint8_t *buf;
 840     uint64_t positions[] = { 0, 1, L1 - 1, L1, L2 - 1, L2, L2 + 1, L3 - 1 };
 841     int num_positions = ARRAY_SIZE(positions);
 842
 843     hbitmap_test_init(data, L3, 0);
 844     buf_size = L2;
 845     buf = g_malloc0(buf_size);
 846
 847     for (i = 0; i < num_positions; i++) {
 848         hbitmap_set(data->hb, positions[i], 1);
 849     }
 850
 851     g_assert(hbitmap_is_serializable(data->hb));
 852
 853     for (i = 0; i < data->size; i += buf_size) {
 854         unsigned long *el = (unsigned long *)buf;
 855         hbitmap_serialize_part(data->hb, buf, i, buf_size);
 856         for (j = 0; j < buf_size / sizeof(unsigned long); j++) {
 857             el[j] = (BITS_PER_LONG == 32 ? le32_to_cpu(el[j]) : le64_to_cpu(el[j]));
 858         }
 859
 860         for (j = 0; j < buf_size; j++) {
 861             bool should_set = false;
 862             for (k = 0; k < num_positions; k++) {
 863                 if (positions[k] == j + i) {
 864                     should_set = true;
 865                     break;
 866                 }
 867             }
 868             g_assert_cmpint(should_set, ==, test_bit(j, (unsigned long *)buf));
 869         }
 870     }
 871
 872     g_free(buf);
 873 }
 874
 875 static void test_hbitmap_serialize_zeroes(TestHBitmapData *data,
 876                                           const void *unused)
 877 {
 878     int i;
 879     HBitmapIter iter;
 880     int64_t next;
 881     uint64_t min_l1 = MAX(L1, 64);
 882     uint64_t positions[] = { 0, min_l1, L2, L3 - min_l1};
 883     int num_positions = ARRAY_SIZE(positions);
 884
 885     hbitmap_test_init(data, L3, 0);
 886
 887     for (i = 0; i < num_positions; i++) {
 888         hbitmap_set(data->hb, positions[i], L1);
 889     }
 890
 891     g_assert(hbitmap_is_serializable(data->hb));
 892
 893     for (i = 0; i < num_positions; i++) {
 894         hbitmap_deserialize_zeroes(data->hb, positions[i], min_l1, true);
 895         hbitmap_iter_init(&iter, data->hb, 0);
 896         next = hbitmap_iter_next(&iter);
 897         if (i == num_positions - 1) {
 898             g_assert_cmpint(next, ==, -1);
 899         } else {
 900             g_assert_cmpint(next, ==, positions[i + 1]);
 901         }
 902     }
 903 }
 904
 905 static void hbitmap_test_add(const char *testpath,
 906                                    void (*test_func)(TestHBitmapData *data, const void *user_data))
 907 {
 908     g_test_add(testpath, TestHBitmapData, NULL, NULL, test_func,
 909                hbitmap_test_teardown);
 910 }
 911
 912 static void test_hbitmap_iter_and_reset(TestHBitmapData *data,
 913                                         const void *unused)
 914 {
 915     HBitmapIter hbi;
 916
 917     hbitmap_test_init(data, L1 * 2, 0);
 918     hbitmap_set(data->hb, 0, data->size);
 919
 920     hbitmap_iter_init(&hbi, data->hb, BITS_PER_LONG - 1);
 921
 922     hbitmap_iter_next(&hbi);
 923
 924     hbitmap_reset_all(data->hb);
 925     hbitmap_iter_next(&hbi);
 926 }
 927
 928 static void test_hbitmap_next_zero_check(TestHBitmapData *data, int64_t start)
 929 {
 930     int64_t ret1 = hbitmap_next_zero(data->hb, start);
 931     int64_t ret2 = start;
 932     for ( ; ret2 < data->size && hbitmap_get(data->hb, ret2); ret2++) {
 933         ;
 934     }
 935     if (ret2 == data->size) {
 936         ret2 = -1;
 937     }
 938
 939     g_assert_cmpint(ret1, ==, ret2);
 940 }
 941
 942 static void test_hbitmap_next_zero_do(TestHBitmapData *data, int granularity)
 943 {
 944     hbitmap_test_init(data, L3, granularity);
 945     test_hbitmap_next_zero_check(data, 0);
 946     test_hbitmap_next_zero_check(data, L3 - 1);
 947
 948     hbitmap_set(data->hb, L2, 1);
 949     test_hbitmap_next_zero_check(data, 0);
 950     test_hbitmap_next_zero_check(data, L2 - 1);
 951     test_hbitmap_next_zero_check(data, L2);
 952     test_hbitmap_next_zero_check(data, L2 + 1);
 953
 954     hbitmap_set(data->hb, L2 + 5, L1);
 955     test_hbitmap_next_zero_check(data, 0);
 956     test_hbitmap_next_zero_check(data, L2 + 1);
 957     test_hbitmap_next_zero_check(data, L2 + 2);
 958     test_hbitmap_next_zero_check(data, L2 + 5);
 959     test_hbitmap_next_zero_check(data, L2 + L1 - 1);
 960     test_hbitmap_next_zero_check(data, L2 + L1);
 961
 962     hbitmap_set(data->hb, L2 * 2, L3 - L2 * 2);
 963     test_hbitmap_next_zero_check(data, L2 * 2 - L1);
 964     test_hbitmap_next_zero_check(data, L2 * 2 - 2);
 965     test_hbitmap_next_zero_check(data, L2 * 2 - 1);
 966     test_hbitmap_next_zero_check(data, L2 * 2);
 967     test_hbitmap_next_zero_check(data, L3 - 1);
 968
 969     hbitmap_set(data->hb, 0, L3);
 970     test_hbitmap_next_zero_check(data, 0);
 971 }
 972
 973 static void test_hbitmap_next_zero_0(TestHBitmapData *data, const void *unused)
 974 {
 975     test_hbitmap_next_zero_do(data, 0);
 976 }
 977
 978 static void test_hbitmap_next_zero_4(TestHBitmapData *data, const void *unused)
 979 {
 980     test_hbitmap_next_zero_do(data, 4);
 981 }
 982
 983 int main(int argc, char **argv)
 984 {
 985     g_test_init(&argc, &argv, NULL);
 986     hbitmap_test_add("/hbitmap/size/0", test_hbitmap_zero);
 987     hbitmap_test_add("/hbitmap/size/unaligned", test_hbitmap_unaligned);
 988     hbitmap_test_add("/hbitmap/iter/empty", test_hbitmap_iter_empty);
 989     hbitmap_test_add("/hbitmap/iter/partial", test_hbitmap_iter_partial);
 990     hbitmap_test_add("/hbitmap/iter/granularity", test_hbitmap_iter_granularity);
 991     hbitmap_test_add("/hbitmap/get/all", test_hbitmap_get_all);
 992     hbitmap_test_add("/hbitmap/get/some", test_hbitmap_get_some);
 993     hbitmap_test_add("/hbitmap/set/all", test_hbitmap_set_all);
 994     hbitmap_test_add("/hbitmap/set/one", test_hbitmap_set_one);
 995     hbitmap_test_add("/hbitmap/set/two-elem", test_hbitmap_set_two_elem);
 996     hbitmap_test_add("/hbitmap/set/general", test_hbitmap_set);
 997     hbitmap_test_add("/hbitmap/set/twice", test_hbitmap_set_twice);
 998     hbitmap_test_add("/hbitmap/set/overlap", test_hbitmap_set_overlap);
 999     hbitmap_test_add("/hbitmap/reset/empty", test_hbitmap_reset_empty);
1000     hbitmap_test_add("/hbitmap/reset/general", test_hbitmap_reset);
1001     hbitmap_test_add("/hbitmap/reset/all", test_hbitmap_reset_all);
1002     hbitmap_test_add("/hbitmap/granularity", test_hbitmap_granularity);
1003
1004     hbitmap_test_add("/hbitmap/truncate/nop", test_hbitmap_truncate_nop);
1005     hbitmap_test_add("/hbitmap/truncate/grow/negligible",
1006                      test_hbitmap_truncate_grow_negligible);
1007     hbitmap_test_add("/hbitmap/truncate/shrink/negligible",
1008                      test_hbitmap_truncate_shrink_negligible);
1009     hbitmap_test_add("/hbitmap/truncate/grow/tiny",
1010                      test_hbitmap_truncate_grow_tiny);
1011     hbitmap_test_add("/hbitmap/truncate/shrink/tiny",
1012                      test_hbitmap_truncate_shrink_tiny);
1013     hbitmap_test_add("/hbitmap/truncate/grow/small",
1014                      test_hbitmap_truncate_grow_small);
1015     hbitmap_test_add("/hbitmap/truncate/shrink/small",
1016                      test_hbitmap_truncate_shrink_small);
1017     hbitmap_test_add("/hbitmap/truncate/grow/medium",
1018                      test_hbitmap_truncate_grow_medium);
1019     hbitmap_test_add("/hbitmap/truncate/shrink/medium",
1020                      test_hbitmap_truncate_shrink_medium);
1021     hbitmap_test_add("/hbitmap/truncate/grow/large",
1022                      test_hbitmap_truncate_grow_large);
1023     hbitmap_test_add("/hbitmap/truncate/shrink/large",
1024                      test_hbitmap_truncate_shrink_large);
1025
1026     hbitmap_test_add("/hbitmap/meta/zero", test_hbitmap_meta_zero);
1027     hbitmap_test_add("/hbitmap/meta/one", test_hbitmap_meta_one);
1028     hbitmap_test_add("/hbitmap/meta/byte", test_hbitmap_meta_byte);
1029     hbitmap_test_add("/hbitmap/meta/word", test_hbitmap_meta_word);
1030     hbitmap_test_add("/hbitmap/meta/sector", test_hbitmap_meta_sector);
1031
1032     hbitmap_test_add("/hbitmap/serialize/align",
1033                      test_hbitmap_serialize_align);
1034     hbitmap_test_add("/hbitmap/serialize/basic",
1035                      test_hbitmap_serialize_basic);
1036     hbitmap_test_add("/hbitmap/serialize/part",
1037                      test_hbitmap_serialize_part);
1038     hbitmap_test_add("/hbitmap/serialize/zeroes",
1039                      test_hbitmap_serialize_zeroes);
1040
1041     hbitmap_test_add("/hbitmap/iter/iter_and_reset",
1042                      test_hbitmap_iter_and_reset);
1043
1044     hbitmap_test_add("/hbitmap/next_zero/next_zero_0",
1045                      test_hbitmap_next_zero_0);
1046     hbitmap_test_add("/hbitmap/next_zero/next_zero_4",
1047                      test_hbitmap_next_zero_4);
1048
1049     g_test_run();
1050
1051     return 0;
1052 }