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