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