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 } 1120