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