tests/test-hbitmap.c

   1 /*
   2  * Hierarchical bitmap unit-tests.
   3  *
   4  * Copyright (C) 2012 Red Hat Inc.
   5  *
   6  * Author: Paolo Bonzini <[email protected]>
   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 "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     int            granularity;
  27 } TestHBitmapData;
  28
  29
  30 /* Check that the HBitmap and the shadow bitmap contain the same data,
  31  * ignoring the same "first" bits.
  32  */
  33 static void hbitmap_test_check(TestHBitmapData *data,
  34                                uint64_t first)
  35 {
  36     uint64_t count = 0;
  37     size_t pos;
  38     int bit;
  39     HBitmapIter hbi;
  40     int64_t i, next;
  41
  42     hbitmap_iter_init(&hbi, data->hb, first);
  43
  44     i = first;
  45     for (;;) {
  46         next = hbitmap_iter_next(&hbi);
  47         if (next < 0) {
  48             next = data->size;
  49         }
  50
  51         while (i < next) {
  52             pos = i >> LOG_BITS_PER_LONG;
  53             bit = i & (BITS_PER_LONG - 1);
  54             i++;
  55             g_assert_cmpint(data->bits[pos] & (1UL << bit), ==, 0);
  56         }
  57
  58         if (next == data->size) {
  59             break;
  60         }
  61
  62         pos = i >> LOG_BITS_PER_LONG;
  63         bit = i & (BITS_PER_LONG - 1);
  64         i++;
  65         count++;
  66         g_assert_cmpint(data->bits[pos] & (1UL << bit), !=, 0);
  67     }
  68
  69     if (first == 0) {
  70         g_assert_cmpint(count << data->granularity, ==, hbitmap_count(data->hb));
  71     }
  72 }
  73
  74 /* This is provided instead of a test setup function so that the sizes
  75    are kept in the test functions (and not in main()) */
  76 static void hbitmap_test_init(TestHBitmapData *data,
  77                               uint64_t size, int granularity)
  78 {
  79     size_t n;
  80     data->hb = hbitmap_alloc(size, granularity);
  81
  82     n = (size + BITS_PER_LONG - 1) / BITS_PER_LONG;
  83     if (n == 0) {
  84         n = 1;
  85     }
  86     data->bits = g_new0(unsigned long, n);
  87     data->size = size;
  88     data->granularity = granularity;
  89     if (size) {
  90         hbitmap_test_check(data, 0);
  91     }
  92 }
  93
  94 static void hbitmap_test_teardown(TestHBitmapData *data,
  95                                   const void *unused)
  96 {
  97     if (data->hb) {
  98         hbitmap_free(data->hb);
  99         data->hb = NULL;
 100     }
 101     if (data->bits) {
 102         g_free(data->bits);
 103         data->bits = NULL;
 104     }
 105 }
 106
 107 /* Set a range in the HBitmap and in the shadow "simple" bitmap.
 108  * The two bitmaps are then tested against each other.
 109  */
 110 static void hbitmap_test_set(TestHBitmapData *data,
 111                              uint64_t first, uint64_t count)
 112 {
 113     hbitmap_set(data->hb, first, count);
 114     while (count-- != 0) {
 115         size_t pos = first >> LOG_BITS_PER_LONG;
 116         int bit = first & (BITS_PER_LONG - 1);
 117         first++;
 118
 119         data->bits[pos] |= 1UL << bit;
 120     }
 121
 122     if (data->granularity == 0) {
 123         hbitmap_test_check(data, 0);
 124     }
 125 }
 126
 127 /* Reset a range in the HBitmap and in the shadow "simple" bitmap.
 128  */
 129 static void hbitmap_test_reset(TestHBitmapData *data,
 130                                uint64_t first, uint64_t count)
 131 {
 132     hbitmap_reset(data->hb, first, count);
 133     while (count-- != 0) {
 134         size_t pos = first >> LOG_BITS_PER_LONG;
 135         int bit = first & (BITS_PER_LONG - 1);
 136         first++;
 137
 138         data->bits[pos] &= ~(1UL << bit);
 139     }
 140
 141     if (data->granularity == 0) {
 142         hbitmap_test_check(data, 0);
 143     }
 144 }
 145
 146 static void hbitmap_test_check_get(TestHBitmapData *data)
 147 {
 148     uint64_t count = 0;
 149     uint64_t i;
 150
 151     for (i = 0; i < data->size; i++) {
 152         size_t pos = i >> LOG_BITS_PER_LONG;
 153         int bit = i & (BITS_PER_LONG - 1);
 154         unsigned long val = data->bits[pos] & (1UL << bit);
 155         count += hbitmap_get(data->hb, i);
 156         g_assert_cmpint(hbitmap_get(data->hb, i), ==, val != 0);
 157     }
 158     g_assert_cmpint(count, ==, hbitmap_count(data->hb));
 159 }
 160
 161 static void test_hbitmap_zero(TestHBitmapData *data,
 162                                const void *unused)
 163 {
 164     hbitmap_test_init(data, 0, 0);
 165 }
 166
 167 static void test_hbitmap_unaligned(TestHBitmapData *data,
 168                                    const void *unused)
 169 {
 170     hbitmap_test_init(data, L3 + 23, 0);
 171     hbitmap_test_set(data, 0, 1);
 172     hbitmap_test_set(data, L3 + 22, 1);
 173 }
 174
 175 static void test_hbitmap_iter_empty(TestHBitmapData *data,
 176                                     const void *unused)
 177 {
 178     hbitmap_test_init(data, L1, 0);
 179 }
 180
 181 static void test_hbitmap_iter_partial(TestHBitmapData *data,
 182                                       const void *unused)
 183 {
 184     hbitmap_test_init(data, L3, 0);
 185     hbitmap_test_set(data, 0, L3);
 186     hbitmap_test_check(data, 1);
 187     hbitmap_test_check(data, L1 - 1);
 188     hbitmap_test_check(data, L1);
 189     hbitmap_test_check(data, L1 * 2 - 1);
 190     hbitmap_test_check(data, L2 - 1);
 191     hbitmap_test_check(data, L2);
 192     hbitmap_test_check(data, L2 + 1);
 193     hbitmap_test_check(data, L2 + L1);
 194     hbitmap_test_check(data, L2 + L1 * 2 - 1);
 195     hbitmap_test_check(data, L2 * 2 - 1);
 196     hbitmap_test_check(data, L2 * 2);
 197     hbitmap_test_check(data, L2 * 2 + 1);
 198     hbitmap_test_check(data, L2 * 2 + L1);
 199     hbitmap_test_check(data, L2 * 2 + L1 * 2 - 1);
 200     hbitmap_test_check(data, L3 / 2);
 201 }
 202
 203 static void test_hbitmap_set_all(TestHBitmapData *data,
 204                                  const void *unused)
 205 {
 206     hbitmap_test_init(data, L3, 0);
 207     hbitmap_test_set(data, 0, L3);
 208 }
 209
 210 static void test_hbitmap_get_all(TestHBitmapData *data,
 211                                  const void *unused)
 212 {
 213     hbitmap_test_init(data, L3, 0);
 214     hbitmap_test_set(data, 0, L3);
 215     hbitmap_test_check_get(data);
 216 }
 217
 218 static void test_hbitmap_get_some(TestHBitmapData *data,
 219                                   const void *unused)
 220 {
 221     hbitmap_test_init(data, 2 * L2, 0);
 222     hbitmap_test_set(data, 10, 1);
 223     hbitmap_test_check_get(data);
 224     hbitmap_test_set(data, L1 - 1, 1);
 225     hbitmap_test_check_get(data);
 226     hbitmap_test_set(data, L1, 1);
 227     hbitmap_test_check_get(data);
 228     hbitmap_test_set(data, L2 - 1, 1);
 229     hbitmap_test_check_get(data);
 230     hbitmap_test_set(data, L2, 1);
 231     hbitmap_test_check_get(data);
 232 }
 233
 234 static void test_hbitmap_set_one(TestHBitmapData *data,
 235                                  const void *unused)
 236 {
 237     hbitmap_test_init(data, 2 * L2, 0);
 238     hbitmap_test_set(data, 10, 1);
 239     hbitmap_test_set(data, L1 - 1, 1);
 240     hbitmap_test_set(data, L1, 1);
 241     hbitmap_test_set(data, L2 - 1, 1);
 242     hbitmap_test_set(data, L2, 1);
 243 }
 244
 245 static void test_hbitmap_set_two_elem(TestHBitmapData *data,
 246                                       const void *unused)
 247 {
 248     hbitmap_test_init(data, 2 * L2, 0);
 249     hbitmap_test_set(data, L1 - 1, 2);
 250     hbitmap_test_set(data, L1 * 2 - 1, 4);
 251     hbitmap_test_set(data, L1 * 4, L1 + 1);
 252     hbitmap_test_set(data, L1 * 8 - 1, L1 + 1);
 253     hbitmap_test_set(data, L2 - 1, 2);
 254     hbitmap_test_set(data, L2 + L1 - 1, 8);
 255     hbitmap_test_set(data, L2 + L1 * 4, L1 + 1);
 256     hbitmap_test_set(data, L2 + L1 * 8 - 1, L1 + 1);
 257 }
 258
 259 static void test_hbitmap_set(TestHBitmapData *data,
 260                              const void *unused)
 261 {
 262     hbitmap_test_init(data, L3 * 2, 0);
 263     hbitmap_test_set(data, L1 - 1, L1 + 2);
 264     hbitmap_test_set(data, L1 * 3 - 1, L1 + 2);
 265     hbitmap_test_set(data, L1 * 5, L1 * 2 + 1);
 266     hbitmap_test_set(data, L1 * 8 - 1, L1 * 2 + 1);
 267     hbitmap_test_set(data, L2 - 1, L1 + 2);
 268     hbitmap_test_set(data, L2 + L1 * 2 - 1, L1 + 2);
 269     hbitmap_test_set(data, L2 + L1 * 4, L1 * 2 + 1);
 270     hbitmap_test_set(data, L2 + L1 * 7 - 1, L1 * 2 + 1);
 271     hbitmap_test_set(data, L2 * 2 - 1, L3 * 2 - L2 * 2);
 272 }
 273
 274 static void test_hbitmap_set_twice(TestHBitmapData *data,
 275                                    const void *unused)
 276 {
 277     hbitmap_test_init(data, L1 * 3, 0);
 278     hbitmap_test_set(data, 0, L1 * 3);
 279     hbitmap_test_set(data, L1, 1);
 280 }
 281
 282 static void test_hbitmap_set_overlap(TestHBitmapData *data,
 283                                      const void *unused)
 284 {
 285     hbitmap_test_init(data, L3 * 2, 0);
 286     hbitmap_test_set(data, L1 - 1, L1 + 2);
 287     hbitmap_test_set(data, L1 * 2 - 1, L1 * 2 + 2);
 288     hbitmap_test_set(data, 0, L1 * 3);
 289     hbitmap_test_set(data, L1 * 8 - 1, L2);
 290     hbitmap_test_set(data, L2, L1);
 291     hbitmap_test_set(data, L2 - L1 - 1, L1 * 8 + 2);
 292     hbitmap_test_set(data, L2, L3 - L2 + 1);
 293     hbitmap_test_set(data, L3 - L1, L1 * 3);
 294     hbitmap_test_set(data, L3 - 1, 3);
 295     hbitmap_test_set(data, L3 - 1, L2);
 296 }
 297
 298 static void test_hbitmap_reset_empty(TestHBitmapData *data,
 299                                      const void *unused)
 300 {
 301     hbitmap_test_init(data, L3, 0);
 302     hbitmap_test_reset(data, 0, L3);
 303 }
 304
 305 static void test_hbitmap_reset(TestHBitmapData *data,
 306                                const void *unused)
 307 {
 308     hbitmap_test_init(data, L3 * 2, 0);
 309     hbitmap_test_set(data, L1 - 1, L1 + 2);
 310     hbitmap_test_reset(data, L1 * 2 - 1, L1 * 2 + 2);
 311     hbitmap_test_set(data, 0, L1 * 3);
 312     hbitmap_test_reset(data, L1 * 8 - 1, L2);
 313     hbitmap_test_set(data, L2, L1);
 314     hbitmap_test_reset(data, L2 - L1 - 1, L1 * 8 + 2);
 315     hbitmap_test_set(data, L2, L3 - L2 + 1);
 316     hbitmap_test_reset(data, L3 - L1, L1 * 3);
 317     hbitmap_test_set(data, L3 - 1, 3);
 318     hbitmap_test_reset(data, L3 - 1, L2);
 319     hbitmap_test_set(data, 0, L3 * 2);
 320     hbitmap_test_reset(data, 0, L1);
 321     hbitmap_test_reset(data, 0, L2);
 322     hbitmap_test_reset(data, L3, L3);
 323     hbitmap_test_set(data, L3 / 2, L3);
 324 }
 325
 326 static void test_hbitmap_granularity(TestHBitmapData *data,
 327                                      const void *unused)
 328 {
 329     /* Note that hbitmap_test_check has to be invoked manually in this test.  */
 330     hbitmap_test_init(data, L1, 1);
 331     hbitmap_test_set(data, 0, 1);
 332     g_assert_cmpint(hbitmap_count(data->hb), ==, 2);
 333     hbitmap_test_check(data, 0);
 334     hbitmap_test_set(data, 2, 1);
 335     g_assert_cmpint(hbitmap_count(data->hb), ==, 4);
 336     hbitmap_test_check(data, 0);
 337     hbitmap_test_set(data, 0, 3);
 338     g_assert_cmpint(hbitmap_count(data->hb), ==, 4);
 339     hbitmap_test_reset(data, 0, 1);
 340     g_assert_cmpint(hbitmap_count(data->hb), ==, 2);
 341 }
 342
 343 static void test_hbitmap_iter_granularity(TestHBitmapData *data,
 344                                           const void *unused)
 345 {
 346     HBitmapIter hbi;
 347
 348     /* Note that hbitmap_test_check has to be invoked manually in this test.  */
 349     hbitmap_test_init(data, 131072 << 7, 7);
 350     hbitmap_iter_init(&hbi, data->hb, 0);
 351     g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
 352
 353     hbitmap_test_set(data, ((L2 + L1 + 1) << 7) + 8, 8);
 354     hbitmap_iter_init(&hbi, data->hb, 0);
 355     g_assert_cmpint(hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7);
 356     g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
 357
 358     hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7);
 359     g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
 360
 361     hbitmap_test_set(data, (131072 << 7) - 8, 8);
 362     hbitmap_iter_init(&hbi, data->hb, 0);
 363     g_assert_cmpint(hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7);
 364     g_assert_cmpint(hbitmap_iter_next(&hbi), ==, 131071 << 7);
 365     g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
 366
 367     hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7);
 368     g_assert_cmpint(hbitmap_iter_next(&hbi), ==, 131071 << 7);
 369     g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
 370 }
 371
 372 static void hbitmap_test_add(const char *testpath,
 373                                    void (*test_func)(TestHBitmapData *data, const void *user_data))
 374 {
 375     g_test_add(testpath, TestHBitmapData, NULL, NULL, test_func,
 376                hbitmap_test_teardown);
 377 }
 378
 379 int main(int argc, char **argv)
 380 {
 381     g_test_init(&argc, &argv, NULL);
 382     hbitmap_test_add("/hbitmap/size/0", test_hbitmap_zero);
 383     hbitmap_test_add("/hbitmap/size/unaligned", test_hbitmap_unaligned);
 384     hbitmap_test_add("/hbitmap/iter/empty", test_hbitmap_iter_empty);
 385     hbitmap_test_add("/hbitmap/iter/partial", test_hbitmap_iter_partial);
 386     hbitmap_test_add("/hbitmap/iter/granularity", test_hbitmap_iter_granularity);
 387     hbitmap_test_add("/hbitmap/get/all", test_hbitmap_get_all);
 388     hbitmap_test_add("/hbitmap/get/some", test_hbitmap_get_some);
 389     hbitmap_test_add("/hbitmap/set/all", test_hbitmap_set_all);
 390     hbitmap_test_add("/hbitmap/set/one", test_hbitmap_set_one);
 391     hbitmap_test_add("/hbitmap/set/two-elem", test_hbitmap_set_two_elem);
 392     hbitmap_test_add("/hbitmap/set/general", test_hbitmap_set);
 393     hbitmap_test_add("/hbitmap/set/twice", test_hbitmap_set_twice);
 394     hbitmap_test_add("/hbitmap/set/overlap", test_hbitmap_set_overlap);
 395     hbitmap_test_add("/hbitmap/reset/empty", test_hbitmap_reset_empty);
 396     hbitmap_test_add("/hbitmap/reset/general", test_hbitmap_reset);
 397     hbitmap_test_add("/hbitmap/granularity", test_hbitmap_granularity);
 398     g_test_run();
 399
 400     return 0;
 401 }