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 <glib.h>
  14 #include "qemu/hbitmap.h"
  15
  16 #define LOG_BITS_PER_LONG          (BITS_PER_LONG == 32 ? 5 : 6)
  17
  18 #define L1                         BITS_PER_LONG
  19 #define L2                         (BITS_PER_LONG * L1)
  20 #define L3                         (BITS_PER_LONG * L2)
  21
  22 typedef struct TestHBitmapData {
  23     HBitmap       *hb;
  24     unsigned long *bits;
  25     size_t         size;
  26     size_t         old_size;
  27     int            granularity;
  28 } TestHBitmapData;
  29
  30
  31 /* Check that the HBitmap and the shadow bitmap contain the same data,
  32  * ignoring the same "first" bits.
  33  */
  34 static void hbitmap_test_check(TestHBitmapData *data,
  35                                uint64_t first)
  36 {
  37     uint64_t count = 0;
  38     size_t pos;
  39     int bit;
  40     HBitmapIter hbi;
  41     int64_t i, next;
  42
  43     hbitmap_iter_init(&hbi, data->hb, first);
  44
  45     i = first;
  46     for (;;) {
  47         next = hbitmap_iter_next(&hbi);
  48         if (next < 0) {
  49             next = data->size;
  50         }
  51
  52         while (i < next) {
  53             pos = i >> LOG_BITS_PER_LONG;
  54             bit = i & (BITS_PER_LONG - 1);
  55             i++;
  56             g_assert_cmpint(data->bits[pos] & (1UL << bit), ==, 0);
  57         }
  58
  59         if (next == data->size) {
  60             break;
  61         }
  62
  63         pos = i >> LOG_BITS_PER_LONG;
  64         bit = i & (BITS_PER_LONG - 1);
  65         i++;
  66         count++;
  67         g_assert_cmpint(data->bits[pos] & (1UL << bit), !=, 0);
  68     }
  69
  70     if (first == 0) {
  71         g_assert_cmpint(count << data->granularity, ==, hbitmap_count(data->hb));
  72     }
  73 }
  74
  75 /* This is provided instead of a test setup function so that the sizes
  76    are kept in the test functions (and not in main()) */
  77 static void hbitmap_test_init(TestHBitmapData *data,
  78                               uint64_t size, int granularity)
  79 {
  80     size_t n;
  81     data->hb = hbitmap_alloc(size, granularity);
  82
  83     n = (size + BITS_PER_LONG - 1) / BITS_PER_LONG;
  84     if (n == 0) {
  85         n = 1;
  86     }
  87     data->bits = g_new0(unsigned long, n);
  88     data->size = size;
  89     data->granularity = granularity;
  90     if (size) {
  91         hbitmap_test_check(data, 0);
  92     }
  93 }
  94
  95 static inline size_t hbitmap_test_array_size(size_t bits)
  96 {
  97     size_t n = (bits + BITS_PER_LONG - 1) / BITS_PER_LONG;
  98     return n ? n : 1;
  99 }
 100
 101 static void hbitmap_test_truncate_impl(TestHBitmapData *data,
 102                                        size_t size)
 103 {
 104     size_t n;
 105     size_t m;
 106     data->old_size = data->size;
 107     data->size = size;
 108
 109     if (data->size == data->old_size) {
 110         return;
 111     }
 112
 113     n = hbitmap_test_array_size(size);
 114     m = hbitmap_test_array_size(data->old_size);
 115     data->bits = g_realloc(data->bits, sizeof(unsigned long) * n);
 116     if (n > m) {
 117         memset(&data->bits[m], 0x00, sizeof(unsigned long) * (n - m));
 118     }
 119
 120     /* If we shrink to an uneven multiple of sizeof(unsigned long),
 121      * scrub the leftover memory. */
 122     if (data->size < data->old_size) {
 123         m = size % (sizeof(unsigned long) * 8);
 124         if (m) {
 125             unsigned long mask = (1ULL << m) - 1;
 126             data->bits[n-1] &= mask;
 127         }
 128     }
 129
 130     hbitmap_truncate(data->hb, size);
 131 }
 132
 133 static void hbitmap_test_teardown(TestHBitmapData *data,
 134                                   const void *unused)
 135 {
 136     if (data->hb) {
 137         hbitmap_free(data->hb);
 138         data->hb = NULL;
 139     }
 140     g_free(data->bits);
 141     data->bits = NULL;
 142 }
 143
 144 /* Set a range in the HBitmap and in the shadow "simple" bitmap.
 145  * The two bitmaps are then tested against each other.
 146  */
 147 static void hbitmap_test_set(TestHBitmapData *data,
 148                              uint64_t first, uint64_t count)
 149 {
 150     hbitmap_set(data->hb, first, count);
 151     while (count-- != 0) {
 152         size_t pos = first >> LOG_BITS_PER_LONG;
 153         int bit = first & (BITS_PER_LONG - 1);
 154         first++;
 155
 156         data->bits[pos] |= 1UL << bit;
 157     }
 158
 159     if (data->granularity == 0) {
 160         hbitmap_test_check(data, 0);
 161     }
 162 }
 163
 164 /* Reset a range in the HBitmap and in the shadow "simple" bitmap.
 165  */
 166 static void hbitmap_test_reset(TestHBitmapData *data,
 167                                uint64_t first, uint64_t count)
 168 {
 169     hbitmap_reset(data->hb, first, count);
 170     while (count-- != 0) {
 171         size_t pos = first >> LOG_BITS_PER_LONG;
 172         int bit = first & (BITS_PER_LONG - 1);
 173         first++;
 174
 175         data->bits[pos] &= ~(1UL << bit);
 176     }
 177
 178     if (data->granularity == 0) {
 179         hbitmap_test_check(data, 0);
 180     }
 181 }
 182
 183 static void hbitmap_test_reset_all(TestHBitmapData *data)
 184 {
 185     size_t n;
 186
 187     hbitmap_reset_all(data->hb);
 188
 189     n = (data->size + BITS_PER_LONG - 1) / BITS_PER_LONG;
 190     if (n == 0) {
 191         n = 1;
 192     }
 193     memset(data->bits, 0, n * sizeof(unsigned long));
 194
 195     if (data->granularity == 0) {
 196         hbitmap_test_check(data, 0);
 197     }
 198 }
 199
 200 static void hbitmap_test_check_get(TestHBitmapData *data)
 201 {
 202     uint64_t count = 0;
 203     uint64_t i;
 204
 205     for (i = 0; i < data->size; i++) {
 206         size_t pos = i >> LOG_BITS_PER_LONG;
 207         int bit = i & (BITS_PER_LONG - 1);
 208         unsigned long val = data->bits[pos] & (1UL << bit);
 209         count += hbitmap_get(data->hb, i);
 210         g_assert_cmpint(hbitmap_get(data->hb, i), ==, val != 0);
 211     }
 212     g_assert_cmpint(count, ==, hbitmap_count(data->hb));
 213 }
 214
 215 static void test_hbitmap_zero(TestHBitmapData *data,
 216                                const void *unused)
 217 {
 218     hbitmap_test_init(data, 0, 0);
 219 }
 220
 221 static void test_hbitmap_unaligned(TestHBitmapData *data,
 222                                    const void *unused)
 223 {
 224     hbitmap_test_init(data, L3 + 23, 0);
 225     hbitmap_test_set(data, 0, 1);
 226     hbitmap_test_set(data, L3 + 22, 1);
 227 }
 228
 229 static void test_hbitmap_iter_empty(TestHBitmapData *data,
 230                                     const void *unused)
 231 {
 232     hbitmap_test_init(data, L1, 0);
 233 }
 234
 235 static void test_hbitmap_iter_partial(TestHBitmapData *data,
 236                                       const void *unused)
 237 {
 238     hbitmap_test_init(data, L3, 0);
 239     hbitmap_test_set(data, 0, L3);
 240     hbitmap_test_check(data, 1);
 241     hbitmap_test_check(data, L1 - 1);
 242     hbitmap_test_check(data, L1);
 243     hbitmap_test_check(data, L1 * 2 - 1);
 244     hbitmap_test_check(data, L2 - 1);
 245     hbitmap_test_check(data, L2);
 246     hbitmap_test_check(data, L2 + 1);
 247     hbitmap_test_check(data, L2 + L1);
 248     hbitmap_test_check(data, L2 + L1 * 2 - 1);
 249     hbitmap_test_check(data, L2 * 2 - 1);
 250     hbitmap_test_check(data, L2 * 2);
 251     hbitmap_test_check(data, L2 * 2 + 1);
 252     hbitmap_test_check(data, L2 * 2 + L1);
 253     hbitmap_test_check(data, L2 * 2 + L1 * 2 - 1);
 254     hbitmap_test_check(data, L3 / 2);
 255 }
 256
 257 static void test_hbitmap_set_all(TestHBitmapData *data,
 258                                  const void *unused)
 259 {
 260     hbitmap_test_init(data, L3, 0);
 261     hbitmap_test_set(data, 0, L3);
 262 }
 263
 264 static void test_hbitmap_get_all(TestHBitmapData *data,
 265                                  const void *unused)
 266 {
 267     hbitmap_test_init(data, L3, 0);
 268     hbitmap_test_set(data, 0, L3);
 269     hbitmap_test_check_get(data);
 270 }
 271
 272 static void test_hbitmap_get_some(TestHBitmapData *data,
 273                                   const void *unused)
 274 {
 275     hbitmap_test_init(data, 2 * L2, 0);
 276     hbitmap_test_set(data, 10, 1);
 277     hbitmap_test_check_get(data);
 278     hbitmap_test_set(data, L1 - 1, 1);
 279     hbitmap_test_check_get(data);
 280     hbitmap_test_set(data, L1, 1);
 281     hbitmap_test_check_get(data);
 282     hbitmap_test_set(data, L2 - 1, 1);
 283     hbitmap_test_check_get(data);
 284     hbitmap_test_set(data, L2, 1);
 285     hbitmap_test_check_get(data);
 286 }
 287
 288 static void test_hbitmap_set_one(TestHBitmapData *data,
 289                                  const void *unused)
 290 {
 291     hbitmap_test_init(data, 2 * L2, 0);
 292     hbitmap_test_set(data, 10, 1);
 293     hbitmap_test_set(data, L1 - 1, 1);
 294     hbitmap_test_set(data, L1, 1);
 295     hbitmap_test_set(data, L2 - 1, 1);
 296     hbitmap_test_set(data, L2, 1);
 297 }
 298
 299 static void test_hbitmap_set_two_elem(TestHBitmapData *data,
 300                                       const void *unused)
 301 {
 302     hbitmap_test_init(data, 2 * L2, 0);
 303     hbitmap_test_set(data, L1 - 1, 2);
 304     hbitmap_test_set(data, L1 * 2 - 1, 4);
 305     hbitmap_test_set(data, L1 * 4, L1 + 1);
 306     hbitmap_test_set(data, L1 * 8 - 1, L1 + 1);
 307     hbitmap_test_set(data, L2 - 1, 2);
 308     hbitmap_test_set(data, L2 + L1 - 1, 8);
 309     hbitmap_test_set(data, L2 + L1 * 4, L1 + 1);
 310     hbitmap_test_set(data, L2 + L1 * 8 - 1, L1 + 1);
 311 }
 312
 313 static void test_hbitmap_set(TestHBitmapData *data,
 314                              const void *unused)
 315 {
 316     hbitmap_test_init(data, L3 * 2, 0);
 317     hbitmap_test_set(data, L1 - 1, L1 + 2);
 318     hbitmap_test_set(data, L1 * 3 - 1, L1 + 2);
 319     hbitmap_test_set(data, L1 * 5, L1 * 2 + 1);
 320     hbitmap_test_set(data, L1 * 8 - 1, L1 * 2 + 1);
 321     hbitmap_test_set(data, L2 - 1, L1 + 2);
 322     hbitmap_test_set(data, L2 + L1 * 2 - 1, L1 + 2);
 323     hbitmap_test_set(data, L2 + L1 * 4, L1 * 2 + 1);
 324     hbitmap_test_set(data, L2 + L1 * 7 - 1, L1 * 2 + 1);
 325     hbitmap_test_set(data, L2 * 2 - 1, L3 * 2 - L2 * 2);
 326 }
 327
 328 static void test_hbitmap_set_twice(TestHBitmapData *data,
 329                                    const void *unused)
 330 {
 331     hbitmap_test_init(data, L1 * 3, 0);
 332     hbitmap_test_set(data, 0, L1 * 3);
 333     hbitmap_test_set(data, L1, 1);
 334 }
 335
 336 static void test_hbitmap_set_overlap(TestHBitmapData *data,
 337                                      const void *unused)
 338 {
 339     hbitmap_test_init(data, L3 * 2, 0);
 340     hbitmap_test_set(data, L1 - 1, L1 + 2);
 341     hbitmap_test_set(data, L1 * 2 - 1, L1 * 2 + 2);
 342     hbitmap_test_set(data, 0, L1 * 3);
 343     hbitmap_test_set(data, L1 * 8 - 1, L2);
 344     hbitmap_test_set(data, L2, L1);
 345     hbitmap_test_set(data, L2 - L1 - 1, L1 * 8 + 2);
 346     hbitmap_test_set(data, L2, L3 - L2 + 1);
 347     hbitmap_test_set(data, L3 - L1, L1 * 3);
 348     hbitmap_test_set(data, L3 - 1, 3);
 349     hbitmap_test_set(data, L3 - 1, L2);
 350 }
 351
 352 static void test_hbitmap_reset_empty(TestHBitmapData *data,
 353                                      const void *unused)
 354 {
 355     hbitmap_test_init(data, L3, 0);
 356     hbitmap_test_reset(data, 0, L3);
 357 }
 358
 359 static void test_hbitmap_reset(TestHBitmapData *data,
 360                                const void *unused)
 361 {
 362     hbitmap_test_init(data, L3 * 2, 0);
 363     hbitmap_test_set(data, L1 - 1, L1 + 2);
 364     hbitmap_test_reset(data, L1 * 2 - 1, L1 * 2 + 2);
 365     hbitmap_test_set(data, 0, L1 * 3);
 366     hbitmap_test_reset(data, L1 * 8 - 1, L2);
 367     hbitmap_test_set(data, L2, L1);
 368     hbitmap_test_reset(data, L2 - L1 - 1, L1 * 8 + 2);
 369     hbitmap_test_set(data, L2, L3 - L2 + 1);
 370     hbitmap_test_reset(data, L3 - L1, L1 * 3);
 371     hbitmap_test_set(data, L3 - 1, 3);
 372     hbitmap_test_reset(data, L3 - 1, L2);
 373     hbitmap_test_set(data, 0, L3 * 2);
 374     hbitmap_test_reset(data, 0, L1);
 375     hbitmap_test_reset(data, 0, L2);
 376     hbitmap_test_reset(data, L3, L3);
 377     hbitmap_test_set(data, L3 / 2, L3);
 378 }
 379
 380 static void test_hbitmap_reset_all(TestHBitmapData *data,
 381                                    const void *unused)
 382 {
 383     hbitmap_test_init(data, L3 * 2, 0);
 384     hbitmap_test_set(data, L1 - 1, L1 + 2);
 385     hbitmap_test_reset_all(data);
 386     hbitmap_test_set(data, 0, L1 * 3);
 387     hbitmap_test_reset_all(data);
 388     hbitmap_test_set(data, L2, L1);
 389     hbitmap_test_reset_all(data);
 390     hbitmap_test_set(data, L2, L3 - L2 + 1);
 391     hbitmap_test_reset_all(data);
 392     hbitmap_test_set(data, L3 - 1, 3);
 393     hbitmap_test_reset_all(data);
 394     hbitmap_test_set(data, 0, L3 * 2);
 395     hbitmap_test_reset_all(data);
 396     hbitmap_test_set(data, L3 / 2, L3);
 397     hbitmap_test_reset_all(data);
 398 }
 399
 400 static void test_hbitmap_granularity(TestHBitmapData *data,
 401                                      const void *unused)
 402 {
 403     /* Note that hbitmap_test_check has to be invoked manually in this test.  */
 404     hbitmap_test_init(data, L1, 1);
 405     hbitmap_test_set(data, 0, 1);
 406     g_assert_cmpint(hbitmap_count(data->hb), ==, 2);
 407     hbitmap_test_check(data, 0);
 408     hbitmap_test_set(data, 2, 1);
 409     g_assert_cmpint(hbitmap_count(data->hb), ==, 4);
 410     hbitmap_test_check(data, 0);
 411     hbitmap_test_set(data, 0, 3);
 412     g_assert_cmpint(hbitmap_count(data->hb), ==, 4);
 413     hbitmap_test_reset(data, 0, 1);
 414     g_assert_cmpint(hbitmap_count(data->hb), ==, 2);
 415 }
 416
 417 static void test_hbitmap_iter_granularity(TestHBitmapData *data,
 418                                           const void *unused)
 419 {
 420     HBitmapIter hbi;
 421
 422     /* Note that hbitmap_test_check has to be invoked manually in this test.  */
 423     hbitmap_test_init(data, 131072 << 7, 7);
 424     hbitmap_iter_init(&hbi, data->hb, 0);
 425     g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
 426
 427     hbitmap_test_set(data, ((L2 + L1 + 1) << 7) + 8, 8);
 428     hbitmap_iter_init(&hbi, data->hb, 0);
 429     g_assert_cmpint(hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7);
 430     g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
 431
 432     hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7);
 433     g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
 434
 435     hbitmap_test_set(data, (131072 << 7) - 8, 8);
 436     hbitmap_iter_init(&hbi, data->hb, 0);
 437     g_assert_cmpint(hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7);
 438     g_assert_cmpint(hbitmap_iter_next(&hbi), ==, 131071 << 7);
 439     g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
 440
 441     hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7);
 442     g_assert_cmpint(hbitmap_iter_next(&hbi), ==, 131071 << 7);
 443     g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
 444 }
 445
 446 static void hbitmap_test_set_boundary_bits(TestHBitmapData *data, ssize_t diff)
 447 {
 448     size_t size = data->size;
 449
 450     /* First bit */
 451     hbitmap_test_set(data, 0, 1);
 452     if (diff < 0) {
 453         /* Last bit in new, shortened map */
 454         hbitmap_test_set(data, size + diff - 1, 1);
 455
 456         /* First bit to be truncated away */
 457         hbitmap_test_set(data, size + diff, 1);
 458     }
 459     /* Last bit */
 460     hbitmap_test_set(data, size - 1, 1);
 461     if (data->granularity == 0) {
 462         hbitmap_test_check_get(data);
 463     }
 464 }
 465
 466 static void hbitmap_test_check_boundary_bits(TestHBitmapData *data)
 467 {
 468     size_t size = MIN(data->size, data->old_size);
 469
 470     if (data->granularity == 0) {
 471         hbitmap_test_check_get(data);
 472         hbitmap_test_check(data, 0);
 473     } else {
 474         /* If a granularity was set, note that every distinct
 475          * (bit >> granularity) value that was set will increase
 476          * the bit pop count by 2^granularity, not just 1.
 477          *
 478          * The hbitmap_test_check facility does not currently tolerate
 479          * non-zero granularities, so test the boundaries and the population
 480          * count manually.
 481          */
 482         g_assert(hbitmap_get(data->hb, 0));
 483         g_assert(hbitmap_get(data->hb, size - 1));
 484         g_assert_cmpint(2 << data->granularity, ==, hbitmap_count(data->hb));
 485     }
 486 }
 487
 488 /* Generic truncate test. */
 489 static void hbitmap_test_truncate(TestHBitmapData *data,
 490                                   size_t size,
 491                                   ssize_t diff,
 492                                   int granularity)
 493 {
 494     hbitmap_test_init(data, size, granularity);
 495     hbitmap_test_set_boundary_bits(data, diff);
 496     hbitmap_test_truncate_impl(data, size + diff);
 497     hbitmap_test_check_boundary_bits(data);
 498 }
 499
 500 static void test_hbitmap_truncate_nop(TestHBitmapData *data,
 501                                       const void *unused)
 502 {
 503     hbitmap_test_truncate(data, L2, 0, 0);
 504 }
 505
 506 /**
 507  * Grow by an amount smaller than the granularity, without crossing
 508  * a granularity alignment boundary. Effectively a NOP.
 509  */
 510 static void test_hbitmap_truncate_grow_negligible(TestHBitmapData *data,
 511                                                   const void *unused)
 512 {
 513     size_t size = L2 - 1;
 514     size_t diff = 1;
 515     int granularity = 1;
 516
 517     hbitmap_test_truncate(data, size, diff, granularity);
 518 }
 519
 520 /**
 521  * Shrink by an amount smaller than the granularity, without crossing
 522  * a granularity alignment boundary. Effectively a NOP.
 523  */
 524 static void test_hbitmap_truncate_shrink_negligible(TestHBitmapData *data,
 525                                                     const void *unused)
 526 {
 527     size_t size = L2;
 528     ssize_t diff = -1;
 529     int granularity = 1;
 530
 531     hbitmap_test_truncate(data, size, diff, granularity);
 532 }
 533
 534 /**
 535  * Grow by an amount smaller than the granularity, but crossing over
 536  * a granularity alignment boundary.
 537  */
 538 static void test_hbitmap_truncate_grow_tiny(TestHBitmapData *data,
 539                                             const void *unused)
 540 {
 541     size_t size = L2 - 2;
 542     ssize_t diff = 1;
 543     int granularity = 1;
 544
 545     hbitmap_test_truncate(data, size, diff, granularity);
 546 }
 547
 548 /**
 549  * Shrink by an amount smaller than the granularity, but crossing over
 550  * a granularity alignment boundary.
 551  */
 552 static void test_hbitmap_truncate_shrink_tiny(TestHBitmapData *data,
 553                                               const void *unused)
 554 {
 555     size_t size = L2 - 1;
 556     ssize_t diff = -1;
 557     int granularity = 1;
 558
 559     hbitmap_test_truncate(data, size, diff, granularity);
 560 }
 561
 562 /**
 563  * Grow by an amount smaller than sizeof(long), and not crossing over
 564  * a sizeof(long) alignment boundary.
 565  */
 566 static void test_hbitmap_truncate_grow_small(TestHBitmapData *data,
 567                                              const void *unused)
 568 {
 569     size_t size = L2 + 1;
 570     size_t diff = sizeof(long) / 2;
 571
 572     hbitmap_test_truncate(data, size, diff, 0);
 573 }
 574
 575 /**
 576  * Shrink by an amount smaller than sizeof(long), and not crossing over
 577  * a sizeof(long) alignment boundary.
 578  */
 579 static void test_hbitmap_truncate_shrink_small(TestHBitmapData *data,
 580                                                const void *unused)
 581 {
 582     size_t size = L2;
 583     size_t diff = sizeof(long) / 2;
 584
 585     hbitmap_test_truncate(data, size, -diff, 0);
 586 }
 587
 588 /**
 589  * Grow by an amount smaller than sizeof(long), while crossing over
 590  * a sizeof(long) alignment boundary.
 591  */
 592 static void test_hbitmap_truncate_grow_medium(TestHBitmapData *data,
 593                                               const void *unused)
 594 {
 595     size_t size = L2 - 1;
 596     size_t diff = sizeof(long) / 2;
 597
 598     hbitmap_test_truncate(data, size, diff, 0);
 599 }
 600
 601 /**
 602  * Shrink by an amount smaller than sizeof(long), while crossing over
 603  * a sizeof(long) alignment boundary.
 604  */
 605 static void test_hbitmap_truncate_shrink_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  * Grow by an amount larger than sizeof(long).
 616  */
 617 static void test_hbitmap_truncate_grow_large(TestHBitmapData *data,
 618                                              const void *unused)
 619 {
 620     size_t size = L2;
 621     size_t diff = 8 * sizeof(long);
 622
 623     hbitmap_test_truncate(data, size, diff, 0);
 624 }
 625
 626 /**
 627  * Shrink by an amount larger than sizeof(long).
 628  */
 629 static void test_hbitmap_truncate_shrink_large(TestHBitmapData *data,
 630                                                const void *unused)
 631 {
 632     size_t size = L2;
 633     size_t diff = 8 * sizeof(long);
 634
 635     hbitmap_test_truncate(data, size, -diff, 0);
 636 }
 637
 638 static void hbitmap_test_add(const char *testpath,
 639                                    void (*test_func)(TestHBitmapData *data, const void *user_data))
 640 {
 641     g_test_add(testpath, TestHBitmapData, NULL, NULL, test_func,
 642                hbitmap_test_teardown);
 643 }
 644
 645 int main(int argc, char **argv)
 646 {
 647     g_test_init(&argc, &argv, NULL);
 648     hbitmap_test_add("/hbitmap/size/0", test_hbitmap_zero);
 649     hbitmap_test_add("/hbitmap/size/unaligned", test_hbitmap_unaligned);
 650     hbitmap_test_add("/hbitmap/iter/empty", test_hbitmap_iter_empty);
 651     hbitmap_test_add("/hbitmap/iter/partial", test_hbitmap_iter_partial);
 652     hbitmap_test_add("/hbitmap/iter/granularity", test_hbitmap_iter_granularity);
 653     hbitmap_test_add("/hbitmap/get/all", test_hbitmap_get_all);
 654     hbitmap_test_add("/hbitmap/get/some", test_hbitmap_get_some);
 655     hbitmap_test_add("/hbitmap/set/all", test_hbitmap_set_all);
 656     hbitmap_test_add("/hbitmap/set/one", test_hbitmap_set_one);
 657     hbitmap_test_add("/hbitmap/set/two-elem", test_hbitmap_set_two_elem);
 658     hbitmap_test_add("/hbitmap/set/general", test_hbitmap_set);
 659     hbitmap_test_add("/hbitmap/set/twice", test_hbitmap_set_twice);
 660     hbitmap_test_add("/hbitmap/set/overlap", test_hbitmap_set_overlap);
 661     hbitmap_test_add("/hbitmap/reset/empty", test_hbitmap_reset_empty);
 662     hbitmap_test_add("/hbitmap/reset/general", test_hbitmap_reset);
 663     hbitmap_test_add("/hbitmap/reset/all", test_hbitmap_reset_all);
 664     hbitmap_test_add("/hbitmap/granularity", test_hbitmap_granularity);
 665
 666     hbitmap_test_add("/hbitmap/truncate/nop", test_hbitmap_truncate_nop);
 667     hbitmap_test_add("/hbitmap/truncate/grow/negligible",
 668                      test_hbitmap_truncate_grow_negligible);
 669     hbitmap_test_add("/hbitmap/truncate/shrink/negligible",
 670                      test_hbitmap_truncate_shrink_negligible);
 671     hbitmap_test_add("/hbitmap/truncate/grow/tiny",
 672                      test_hbitmap_truncate_grow_tiny);
 673     hbitmap_test_add("/hbitmap/truncate/shrink/tiny",
 674                      test_hbitmap_truncate_shrink_tiny);
 675     hbitmap_test_add("/hbitmap/truncate/grow/small",
 676                      test_hbitmap_truncate_grow_small);
 677     hbitmap_test_add("/hbitmap/truncate/shrink/small",
 678                      test_hbitmap_truncate_shrink_small);
 679     hbitmap_test_add("/hbitmap/truncate/grow/medium",
 680                      test_hbitmap_truncate_grow_medium);
 681     hbitmap_test_add("/hbitmap/truncate/shrink/medium",
 682                      test_hbitmap_truncate_shrink_medium);
 683     hbitmap_test_add("/hbitmap/truncate/grow/large",
 684                      test_hbitmap_truncate_grow_large);
 685     hbitmap_test_add("/hbitmap/truncate/shrink/large",
 686                      test_hbitmap_truncate_shrink_large);
 687     g_test_run();
 688
 689     return 0;
 690 }