util/hbitmap.c

   1 /*
   2  * Hierarchical Bitmap Data Type
   3  *
   4  * Copyright Red Hat, Inc., 2012
   5  *
   6  * Author: Paolo Bonzini <pbonzini@redhat.com>
   7  *
   8  * This work is licensed under the terms of the GNU GPL, version 2 or
   9  * later.  See the COPYING file in the top-level directory.
  10  */
  11
  12 #include "qemu/osdep.h"
  13 #include "qemu/hbitmap.h"
  14 #include "qemu/host-utils.h"
  15 #include "trace.h"
  16 #include "crypto/hash.h"
  17
  18 /* HBitmaps provides an array of bits.  The bits are stored as usual in an
  19  * array of unsigned longs, but HBitmap is also optimized to provide fast
  20  * iteration over set bits; going from one bit to the next is O(logB n)
  21  * worst case, with B = sizeof(long) * CHAR_BIT: the result is low enough
  22  * that the number of levels is in fact fixed.
  23  *
  24  * In order to do this, it stacks multiple bitmaps with progressively coarser
  25  * granularity; in all levels except the last, bit N is set iff the N-th
  26  * unsigned long is nonzero in the immediately next level.  When iteration
  27  * completes on the last level it can examine the 2nd-last level to quickly
  28  * skip entire words, and even do so recursively to skip blocks of 64 words or
  29  * powers thereof (32 on 32-bit machines).
  30  *
  31  * Given an index in the bitmap, it can be split in group of bits like
  32  * this (for the 64-bit case):
  33  *
  34  *   bits 0-57 => word in the last bitmap     | bits 58-63 => bit in the word
  35  *   bits 0-51 => word in the 2nd-last bitmap | bits 52-57 => bit in the word
  36  *   bits 0-45 => word in the 3rd-last bitmap | bits 46-51 => bit in the word
  37  *
  38  * So it is easy to move up simply by shifting the index right by
  39  * log2(BITS_PER_LONG) bits.  To move down, you shift the index left
  40  * similarly, and add the word index within the group.  Iteration uses
  41  * ffs (find first set bit) to find the next word to examine; this
  42  * operation can be done in constant time in most current architectures.
  43  *
  44  * Setting or clearing a range of m bits on all levels, the work to perform
  45  * is O(m + m/W + m/W^2 + ...), which is O(m) like on a regular bitmap.
  46  *
  47  * When iterating on a bitmap, each bit (on any level) is only visited
  48  * once.  Hence, The total cost of visiting a bitmap with m bits in it is
  49  * the number of bits that are set in all bitmaps.  Unless the bitmap is
  50  * extremely sparse, this is also O(m + m/W + m/W^2 + ...), so the amortized
  51  * cost of advancing from one bit to the next is usually constant (worst case
  52  * O(logB n) as in the non-amortized complexity).
  53  */
  54
  55 struct HBitmap {
  56     /*
  57      * Size of the bitmap, as requested in hbitmap_alloc or in hbitmap_truncate.
  58      */
  59     uint64_t orig_size;
  60
  61     /* Number of total bits in the bottom level.  */
  62     uint64_t size;
  63
  64     /* Number of set bits in the bottom level.  */
  65     uint64_t count;
  66
  67     /* A scaling factor.  Given a granularity of G, each bit in the bitmap will
  68      * will actually represent a group of 2^G elements.  Each operation on a
  69      * range of bits first rounds the bits to determine which group they land
  70      * in, and then affect the entire page; iteration will only visit the first
  71      * bit of each group.  Here is an example of operations in a size-16,
  72      * granularity-1 HBitmap:
  73      *
  74      *    initial state            00000000
  75      *    set(start=0, count=9)    11111000 (iter: 0, 2, 4, 6, 8)
  76      *    reset(start=1, count=3)  00111000 (iter: 4, 6, 8)
  77      *    set(start=9, count=2)    00111100 (iter: 4, 6, 8, 10)
  78      *    reset(start=5, count=5)  00000000
  79      *
  80      * From an implementation point of view, when setting or resetting bits,
  81      * the bitmap will scale bit numbers right by this amount of bits.  When
  82      * iterating, the bitmap will scale bit numbers left by this amount of
  83      * bits.
  84      */
  85     int granularity;
  86
  87     /* A meta dirty bitmap to track the dirtiness of bits in this HBitmap. */
  88     HBitmap *meta;
  89
  90     /* A number of progressively less coarse bitmaps (i.e. level 0 is the
  91      * coarsest).  Each bit in level N represents a word in level N+1 that
  92      * has a set bit, except the last level where each bit represents the
  93      * actual bitmap.
  94      *
  95      * Note that all bitmaps have the same number of levels.  Even a 1-bit
  96      * bitmap will still allocate HBITMAP_LEVELS arrays.
  97      */
  98     unsigned long *levels[HBITMAP_LEVELS];
  99
 100     /* The length of each levels[] array. */
 101     uint64_t sizes[HBITMAP_LEVELS];
 102 };
 103
 104 /* Advance hbi to the next nonzero word and return it.  hbi->pos
 105  * is updated.  Returns zero if we reach the end of the bitmap.
 106  */
 107 static unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi)
 108 {
 109     size_t pos = hbi->pos;
 110     const HBitmap *hb = hbi->hb;
 111     unsigned i = HBITMAP_LEVELS - 1;
 112
 113     unsigned long cur;
 114     do {
 115         i--;
 116         pos >>= BITS_PER_LEVEL;
 117         cur = hbi->cur[i] & hb->levels[i][pos];
 118     } while (cur == 0);
 119
 120     /* Check for end of iteration.  We always use fewer than BITS_PER_LONG
 121      * bits in the level 0 bitmap; thus we can repurpose the most significant
 122      * bit as a sentinel.  The sentinel is set in hbitmap_alloc and ensures
 123      * that the above loop ends even without an explicit check on i.
 124      */
 125
 126     if (i == 0 && cur == (1UL << (BITS_PER_LONG - 1))) {
 127         return 0;
 128     }
 129     for (; i < HBITMAP_LEVELS - 1; i++) {
 130         /* Shift back pos to the left, matching the right shifts above.
 131          * The index of this word's least significant set bit provides
 132          * the low-order bits.
 133          */
 134         assert(cur);
 135         pos = (pos << BITS_PER_LEVEL) + ctzl(cur);
 136         hbi->cur[i] = cur & (cur - 1);
 137
 138         /* Set up next level for iteration.  */
 139         cur = hb->levels[i + 1][pos];
 140     }
 141
 142     hbi->pos = pos;
 143     trace_hbitmap_iter_skip_words(hbi->hb, hbi, pos, cur);
 144
 145     assert(cur);
 146     return cur;
 147 }
 148
 149 int64_t hbitmap_iter_next(HBitmapIter *hbi)
 150 {
 151     unsigned long cur = hbi->cur[HBITMAP_LEVELS - 1] &
 152             hbi->hb->levels[HBITMAP_LEVELS - 1][hbi->pos];
 153     int64_t item;
 154
 155     if (cur == 0) {
 156         cur = hbitmap_iter_skip_words(hbi);
 157         if (cur == 0) {
 158             return -1;
 159         }
 160     }
 161
 162     /* The next call will resume work from the next bit.  */
 163     hbi->cur[HBITMAP_LEVELS - 1] = cur & (cur - 1);
 164     item = ((uint64_t)hbi->pos << BITS_PER_LEVEL) + ctzl(cur);
 165
 166     return item << hbi->granularity;
 167 }
 168
 169 void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first)
 170 {
 171     unsigned i, bit;
 172     uint64_t pos;
 173
 174     hbi->hb = hb;
 175     pos = first >> hb->granularity;
 176     assert(pos < hb->size);
 177     hbi->pos = pos >> BITS_PER_LEVEL;
 178     hbi->granularity = hb->granularity;
 179
 180     for (i = HBITMAP_LEVELS; i-- > 0; ) {
 181         bit = pos & (BITS_PER_LONG - 1);
 182         pos >>= BITS_PER_LEVEL;
 183
 184         /* Drop bits representing items before first.  */
 185         hbi->cur[i] = hb->levels[i][pos] & ~((1UL << bit) - 1);
 186
 187         /* We have already added level i+1, so the lowest set bit has
 188          * been processed.  Clear it.
 189          */
 190         if (i != HBITMAP_LEVELS - 1) {
 191             hbi->cur[i] &= ~(1UL << bit);
 192         }
 193     }
 194 }
 195
 196 int64_t hbitmap_next_dirty(const HBitmap *hb, int64_t start, int64_t count)
 197 {
 198     HBitmapIter hbi;
 199     int64_t first_dirty_off;
 200     uint64_t end;
 201
 202     assert(start >= 0 && count >= 0);
 203
 204     if (start >= hb->orig_size || count == 0) {
 205         return -1;
 206     }
 207
 208     end = count > hb->orig_size - start ? hb->orig_size : start + count;
 209
 210     hbitmap_iter_init(&hbi, hb, start);
 211     first_dirty_off = hbitmap_iter_next(&hbi);
 212
 213     if (first_dirty_off < 0 || first_dirty_off >= end) {
 214         return -1;
 215     }
 216
 217     return MAX(start, first_dirty_off);
 218 }
 219
 220 int64_t hbitmap_next_zero(const HBitmap *hb, int64_t start, int64_t count)
 221 {
 222     size_t pos = (start >> hb->granularity) >> BITS_PER_LEVEL;
 223     unsigned long *last_lev = hb->levels[HBITMAP_LEVELS - 1];
 224     unsigned long cur = last_lev[pos];
 225     unsigned start_bit_offset;
 226     uint64_t end_bit, sz;
 227     int64_t res;
 228
 229     assert(start >= 0 && count >= 0);
 230
 231     if (start >= hb->orig_size || count == 0) {
 232         return -1;
 233     }
 234
 235     end_bit = count > hb->orig_size - start ?
 236                 hb->size :
 237                 ((start + count - 1) >> hb->granularity) + 1;
 238     sz = (end_bit + BITS_PER_LONG - 1) >> BITS_PER_LEVEL;
 239
 240     /* There may be some zero bits in @cur before @start. We are not interested
 241      * in them, let's set them.
 242      */
 243     start_bit_offset = (start >> hb->granularity) & (BITS_PER_LONG - 1);
 244     cur |= (1UL << start_bit_offset) - 1;
 245     assert((start >> hb->granularity) < hb->size);
 246
 247     if (cur == (unsigned long)-1) {
 248         do {
 249             pos++;
 250         } while (pos < sz && last_lev[pos] == (unsigned long)-1);
 251
 252         if (pos >= sz) {
 253             return -1;
 254         }
 255
 256         cur = last_lev[pos];
 257     }
 258
 259     res = (pos << BITS_PER_LEVEL) + ctol(cur);
 260     if (res >= end_bit) {
 261         return -1;
 262     }
 263
 264     res = res << hb->granularity;
 265     if (res < start) {
 266         assert(((start - res) >> hb->granularity) == 0);
 267         return start;
 268     }
 269
 270     return res;
 271 }
 272
 273 bool hbitmap_next_dirty_area(const HBitmap *hb, int64_t start, int64_t end,
 274                              int64_t max_dirty_count,
 275                              int64_t *dirty_start, int64_t *dirty_count)
 276 {
 277     int64_t next_zero;
 278
 279     assert(start >= 0 && end >= 0 && max_dirty_count > 0);
 280
 281     end = MIN(end, hb->orig_size);
 282     if (start >= end) {
 283         return false;
 284     }
 285
 286     start = hbitmap_next_dirty(hb, start, end - start);
 287     if (start < 0) {
 288         return false;
 289     }
 290
 291     end = start + MIN(end - start, max_dirty_count);
 292
 293     next_zero = hbitmap_next_zero(hb, start, end - start);
 294     if (next_zero >= 0) {
 295         end = next_zero;
 296     }
 297
 298     *dirty_start = start;
 299     *dirty_count = end - start;
 300
 301     return true;
 302 }
 303
 304 bool hbitmap_status(const HBitmap *hb, int64_t start, int64_t count,
 305                     int64_t *pnum)
 306 {
 307     int64_t next_dirty, next_zero;
 308
 309     assert(start >= 0);
 310     assert(count > 0);
 311     assert(start + count <= hb->orig_size);
 312
 313     next_dirty = hbitmap_next_dirty(hb, start, count);
 314     if (next_dirty == -1) {
 315         *pnum = count;
 316         return false;
 317     }
 318
 319     if (next_dirty > start) {
 320         *pnum = next_dirty - start;
 321         return false;
 322     }
 323
 324     assert(next_dirty == start);
 325
 326     next_zero = hbitmap_next_zero(hb, start, count);
 327     if (next_zero == -1) {
 328         *pnum = count;
 329         return true;
 330     }
 331
 332     assert(next_zero > start);
 333     *pnum = next_zero - start;
 334     return false;
 335 }
 336
 337 bool hbitmap_empty(const HBitmap *hb)
 338 {
 339     return hb->count == 0;
 340 }
 341
 342 int hbitmap_granularity(const HBitmap *hb)
 343 {
 344     return hb->granularity;
 345 }
 346
 347 uint64_t hbitmap_count(const HBitmap *hb)
 348 {
 349     return hb->count << hb->granularity;
 350 }
 351
 352 /**
 353  * hbitmap_iter_next_word:
 354  * @hbi: HBitmapIter to operate on.
 355  * @p_cur: Location where to store the next non-zero word.
 356  *
 357  * Return the index of the next nonzero word that is set in @hbi's
 358  * associated HBitmap, and set *p_cur to the content of that word
 359  * (bits before the index that was passed to hbitmap_iter_init are
 360  * trimmed on the first call).  Return -1, and set *p_cur to zero,
 361  * if all remaining words are zero.
 362  */
 363 static size_t hbitmap_iter_next_word(HBitmapIter *hbi, unsigned long *p_cur)
 364 {
 365     unsigned long cur = hbi->cur[HBITMAP_LEVELS - 1];
 366
 367     if (cur == 0) {
 368         cur = hbitmap_iter_skip_words(hbi);
 369         if (cur == 0) {
 370             *p_cur = 0;
 371             return -1;
 372         }
 373     }
 374
 375     /* The next call will resume work from the next word.  */
 376     hbi->cur[HBITMAP_LEVELS - 1] = 0;
 377     *p_cur = cur;
 378     return hbi->pos;
 379 }
 380
 381 /* Count the number of set bits between start and end, not accounting for
 382  * the granularity.  Also an example of how to use hbitmap_iter_next_word.
 383  */
 384 static uint64_t hb_count_between(HBitmap *hb, uint64_t start, uint64_t last)
 385 {
 386     HBitmapIter hbi;
 387     uint64_t count = 0;
 388     uint64_t end = last + 1;
 389     unsigned long cur;
 390     size_t pos;
 391
 392     hbitmap_iter_init(&hbi, hb, start << hb->granularity);
 393     for (;;) {
 394         pos = hbitmap_iter_next_word(&hbi, &cur);
 395         if (pos >= (end >> BITS_PER_LEVEL)) {
 396             break;
 397         }
 398         count += ctpopl(cur);
 399     }
 400
 401     if (pos == (end >> BITS_PER_LEVEL)) {
 402         /* Drop bits representing the END-th and subsequent items.  */
 403         int bit = end & (BITS_PER_LONG - 1);
 404         cur &= (1UL << bit) - 1;
 405         count += ctpopl(cur);
 406     }
 407
 408     return count;
 409 }
 410
 411 /* Setting starts at the last layer and propagates up if an element
 412  * changes.
 413  */
 414 static inline bool hb_set_elem(unsigned long *elem, uint64_t start, uint64_t last)
 415 {
 416     unsigned long mask;
 417     unsigned long old;
 418
 419     assert((last >> BITS_PER_LEVEL) == (start >> BITS_PER_LEVEL));
 420     assert(start <= last);
 421
 422     mask = 2UL << (last & (BITS_PER_LONG - 1));
 423     mask -= 1UL << (start & (BITS_PER_LONG - 1));
 424     old = *elem;
 425     *elem |= mask;
 426     return old != *elem;
 427 }
 428
 429 /* The recursive workhorse (the depth is limited to HBITMAP_LEVELS)...
 430  * Returns true if at least one bit is changed. */
 431 static bool hb_set_between(HBitmap *hb, int level, uint64_t start,
 432                            uint64_t last)
 433 {
 434     size_t pos = start >> BITS_PER_LEVEL;
 435     size_t lastpos = last >> BITS_PER_LEVEL;
 436     bool changed = false;
 437     size_t i;
 438
 439     i = pos;
 440     if (i < lastpos) {
 441         uint64_t next = (start | (BITS_PER_LONG - 1)) + 1;
 442         changed |= hb_set_elem(&hb->levels[level][i], start, next - 1);
 443         for (;;) {
 444             start = next;
 445             next += BITS_PER_LONG;
 446             if (++i == lastpos) {
 447                 break;
 448             }
 449             changed |= (hb->levels[level][i] == 0);
 450             hb->levels[level][i] = ~0UL;
 451         }
 452     }
 453     changed |= hb_set_elem(&hb->levels[level][i], start, last);
 454
 455     /* If there was any change in this layer, we may have to update
 456      * the one above.
 457      */
 458     if (level > 0 && changed) {
 459         hb_set_between(hb, level - 1, pos, lastpos);
 460     }
 461     return changed;
 462 }
 463
 464 void hbitmap_set(HBitmap *hb, uint64_t start, uint64_t count)
 465 {
 466     /* Compute range in the last layer.  */
 467     uint64_t first, n;
 468     uint64_t last = start + count - 1;
 469
 470     if (count == 0) {
 471         return;
 472     }
 473
 474     trace_hbitmap_set(hb, start, count,
 475                       start >> hb->granularity, last >> hb->granularity);
 476
 477     first = start >> hb->granularity;
 478     last >>= hb->granularity;
 479     assert(last < hb->size);
 480     n = last - first + 1;
 481
 482     hb->count += n - hb_count_between(hb, first, last);
 483     if (hb_set_between(hb, HBITMAP_LEVELS - 1, first, last) &&
 484         hb->meta) {
 485         hbitmap_set(hb->meta, start, count);
 486     }
 487 }
 488
 489 /* Resetting works the other way round: propagate up if the new
 490  * value is zero.
 491  */
 492 static inline bool hb_reset_elem(unsigned long *elem, uint64_t start, uint64_t last)
 493 {
 494     unsigned long mask;
 495     bool blanked;
 496
 497     assert((last >> BITS_PER_LEVEL) == (start >> BITS_PER_LEVEL));
 498     assert(start <= last);
 499
 500     mask = 2UL << (last & (BITS_PER_LONG - 1));
 501     mask -= 1UL << (start & (BITS_PER_LONG - 1));
 502     blanked = *elem != 0 && ((*elem & ~mask) == 0);
 503     *elem &= ~mask;
 504     return blanked;
 505 }
 506
 507 /* The recursive workhorse (the depth is limited to HBITMAP_LEVELS)...
 508  * Returns true if at least one bit is changed. */
 509 static bool hb_reset_between(HBitmap *hb, int level, uint64_t start,
 510                              uint64_t last)
 511 {
 512     size_t pos = start >> BITS_PER_LEVEL;
 513     size_t lastpos = last >> BITS_PER_LEVEL;
 514     bool changed = false;
 515     size_t i;
 516
 517     i = pos;
 518     if (i < lastpos) {
 519         uint64_t next = (start | (BITS_PER_LONG - 1)) + 1;
 520
 521         /* Here we need a more complex test than when setting bits.  Even if
 522          * something was changed, we must not blank bits in the upper level
 523          * unless the lower-level word became entirely zero.  So, remove pos
 524          * from the upper-level range if bits remain set.
 525          */
 526         if (hb_reset_elem(&hb->levels[level][i], start, next - 1)) {
 527             changed = true;
 528         } else {
 529             pos++;
 530         }
 531
 532         for (;;) {
 533             start = next;
 534             next += BITS_PER_LONG;
 535             if (++i == lastpos) {
 536                 break;
 537             }
 538             changed |= (hb->levels[level][i] != 0);
 539             hb->levels[level][i] = 0UL;
 540         }
 541     }
 542
 543     /* Same as above, this time for lastpos.  */
 544     if (hb_reset_elem(&hb->levels[level][i], start, last)) {
 545         changed = true;
 546     } else {
 547         lastpos--;
 548     }
 549
 550     if (level > 0 && changed) {
 551         hb_reset_between(hb, level - 1, pos, lastpos);
 552     }
 553
 554     return changed;
 555
 556 }
 557
 558 void hbitmap_reset(HBitmap *hb, uint64_t start, uint64_t count)
 559 {
 560     /* Compute range in the last layer.  */
 561     uint64_t first;
 562     uint64_t last = start + count - 1;
 563     uint64_t gran = 1ULL << hb->granularity;
 564
 565     if (count == 0) {
 566         return;
 567     }
 568
 569     assert(QEMU_IS_ALIGNED(start, gran));
 570     assert(QEMU_IS_ALIGNED(count, gran) || (start + count == hb->orig_size));
 571
 572     trace_hbitmap_reset(hb, start, count,
 573                         start >> hb->granularity, last >> hb->granularity);
 574
 575     first = start >> hb->granularity;
 576     last >>= hb->granularity;
 577     assert(last < hb->size);
 578
 579     hb->count -= hb_count_between(hb, first, last);
 580     if (hb_reset_between(hb, HBITMAP_LEVELS - 1, first, last) &&
 581         hb->meta) {
 582         hbitmap_set(hb->meta, start, count);
 583     }
 584 }
 585
 586 void hbitmap_reset_all(HBitmap *hb)
 587 {
 588     unsigned int i;
 589
 590     /* Same as hbitmap_alloc() except for memset() instead of malloc() */
 591     for (i = HBITMAP_LEVELS; --i >= 1; ) {
 592         memset(hb->levels[i], 0, hb->sizes[i] * sizeof(unsigned long));
 593     }
 594
 595     hb->levels[0][0] = 1UL << (BITS_PER_LONG - 1);
 596     hb->count = 0;
 597 }
 598
 599 bool hbitmap_is_serializable(const HBitmap *hb)
 600 {
 601     /* Every serialized chunk must be aligned to 64 bits so that endianness
 602      * requirements can be fulfilled on both 64 bit and 32 bit hosts.
 603      * We have hbitmap_serialization_align() which converts this
 604      * alignment requirement from bitmap bits to items covered (e.g. sectors).
 605      * That value is:
 606      *    64 << hb->granularity
 607      * Since this value must not exceed UINT64_MAX, hb->granularity must be
 608      * less than 58 (== 64 - 6, where 6 is ld(64), i.e. 1 << 6 == 64).
 609      *
 610      * In order for hbitmap_serialization_align() to always return a
 611      * meaningful value, bitmaps that are to be serialized must have a
 612      * granularity of less than 58. */
 613
 614     return hb->granularity < 58;
 615 }
 616
 617 bool hbitmap_get(const HBitmap *hb, uint64_t item)
 618 {
 619     /* Compute position and bit in the last layer.  */
 620     uint64_t pos = item >> hb->granularity;
 621     unsigned long bit = 1UL << (pos & (BITS_PER_LONG - 1));
 622     assert(pos < hb->size);
 623
 624     return (hb->levels[HBITMAP_LEVELS - 1][pos >> BITS_PER_LEVEL] & bit) != 0;
 625 }
 626
 627 uint64_t hbitmap_serialization_align(const HBitmap *hb)
 628 {
 629     assert(hbitmap_is_serializable(hb));
 630
 631     /* Require at least 64 bit granularity to be safe on both 64 bit and 32 bit
 632      * hosts. */
 633     return UINT64_C(64) << hb->granularity;
 634 }
 635
 636 /* Start should be aligned to serialization granularity, chunk size should be
 637  * aligned to serialization granularity too, except for last chunk.
 638  */
 639 static void serialization_chunk(const HBitmap *hb,
 640                                 uint64_t start, uint64_t count,
 641                                 unsigned long **first_el, uint64_t *el_count)
 642 {
 643     uint64_t last = start + count - 1;
 644     uint64_t gran = hbitmap_serialization_align(hb);
 645
 646     assert((start & (gran - 1)) == 0);
 647     assert((last >> hb->granularity) < hb->size);
 648     if ((last >> hb->granularity) != hb->size - 1) {
 649         assert((count & (gran - 1)) == 0);
 650     }
 651
 652     start = (start >> hb->granularity) >> BITS_PER_LEVEL;
 653     last = (last >> hb->granularity) >> BITS_PER_LEVEL;
 654
 655     *first_el = &hb->levels[HBITMAP_LEVELS - 1][start];
 656     *el_count = last - start + 1;
 657 }
 658
 659 uint64_t hbitmap_serialization_size(const HBitmap *hb,
 660                                     uint64_t start, uint64_t count)
 661 {
 662     uint64_t el_count;
 663     unsigned long *cur;
 664
 665     if (!count) {
 666         return 0;
 667     }
 668     serialization_chunk(hb, start, count, &cur, &el_count);
 669
 670     return el_count * sizeof(unsigned long);
 671 }
 672
 673 void hbitmap_serialize_part(const HBitmap *hb, uint8_t *buf,
 674                             uint64_t start, uint64_t count)
 675 {
 676     uint64_t el_count;
 677     unsigned long *cur, *end;
 678
 679     if (!count) {
 680         return;
 681     }
 682     serialization_chunk(hb, start, count, &cur, &el_count);
 683     end = cur + el_count;
 684
 685     while (cur != end) {
 686         unsigned long el =
 687             (BITS_PER_LONG == 32 ? cpu_to_le32(*cur) : cpu_to_le64(*cur));
 688
 689         memcpy(buf, &el, sizeof(el));
 690         buf += sizeof(el);
 691         cur++;
 692     }
 693 }
 694
 695 void hbitmap_deserialize_part(HBitmap *hb, uint8_t *buf,
 696                               uint64_t start, uint64_t count,
 697                               bool finish)
 698 {
 699     uint64_t el_count;
 700     unsigned long *cur, *end;
 701
 702     if (!count) {
 703         return;
 704     }
 705     serialization_chunk(hb, start, count, &cur, &el_count);
 706     end = cur + el_count;
 707
 708     while (cur != end) {
 709         memcpy(cur, buf, sizeof(*cur));
 710
 711         if (BITS_PER_LONG == 32) {
 712             le32_to_cpus((uint32_t *)cur);
 713         } else {
 714             le64_to_cpus((uint64_t *)cur);
 715         }
 716
 717         buf += sizeof(unsigned long);
 718         cur++;
 719     }
 720     if (finish) {
 721         hbitmap_deserialize_finish(hb);
 722     }
 723 }
 724
 725 void hbitmap_deserialize_zeroes(HBitmap *hb, uint64_t start, uint64_t count,
 726                                 bool finish)
 727 {
 728     uint64_t el_count;
 729     unsigned long *first;
 730
 731     if (!count) {
 732         return;
 733     }
 734     serialization_chunk(hb, start, count, &first, &el_count);
 735
 736     memset(first, 0, el_count * sizeof(unsigned long));
 737     if (finish) {
 738         hbitmap_deserialize_finish(hb);
 739     }
 740 }
 741
 742 void hbitmap_deserialize_ones(HBitmap *hb, uint64_t start, uint64_t count,
 743                               bool finish)
 744 {
 745     uint64_t el_count;
 746     unsigned long *first;
 747
 748     if (!count) {
 749         return;
 750     }
 751     serialization_chunk(hb, start, count, &first, &el_count);
 752
 753     memset(first, 0xff, el_count * sizeof(unsigned long));
 754     if (finish) {
 755         hbitmap_deserialize_finish(hb);
 756     }
 757 }
 758
 759 void hbitmap_deserialize_finish(HBitmap *bitmap)
 760 {
 761     int64_t i, size, prev_size;
 762     int lev;
 763
 764     /* restore levels starting from penultimate to zero level, assuming
 765      * that the last level is ok */
 766     size = MAX((bitmap->size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL, 1);
 767     for (lev = HBITMAP_LEVELS - 1; lev-- > 0; ) {
 768         prev_size = size;
 769         size = MAX((size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL, 1);
 770         memset(bitmap->levels[lev], 0, size * sizeof(unsigned long));
 771
 772         for (i = 0; i < prev_size; ++i) {
 773             if (bitmap->levels[lev + 1][i]) {
 774                 bitmap->levels[lev][i >> BITS_PER_LEVEL] |=
 775                     1UL << (i & (BITS_PER_LONG - 1));
 776             }
 777         }
 778     }
 779
 780     bitmap->levels[0][0] |= 1UL << (BITS_PER_LONG - 1);
 781     bitmap->count = hb_count_between(bitmap, 0, bitmap->size - 1);
 782 }
 783
 784 void hbitmap_free(HBitmap *hb)
 785 {
 786     unsigned i;
 787     assert(!hb->meta);
 788     for (i = HBITMAP_LEVELS; i-- > 0; ) {
 789         g_free(hb->levels[i]);
 790     }
 791     g_free(hb);
 792 }
 793
 794 HBitmap *hbitmap_alloc(uint64_t size, int granularity)
 795 {
 796     HBitmap *hb = g_new0(struct HBitmap, 1);
 797     unsigned i;
 798
 799     assert(size <= INT64_MAX);
 800     hb->orig_size = size;
 801
 802     assert(granularity >= 0 && granularity < 64);
 803     size = (size + (1ULL << granularity) - 1) >> granularity;
 804     assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE));
 805
 806     hb->size = size;
 807     hb->granularity = granularity;
 808     for (i = HBITMAP_LEVELS; i-- > 0; ) {
 809         size = MAX((size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL, 1);
 810         hb->sizes[i] = size;
 811         hb->levels[i] = g_new0(unsigned long, size);
 812     }
 813
 814     /* We necessarily have free bits in level 0 due to the definition
 815      * of HBITMAP_LEVELS, so use one for a sentinel.  This speeds up
 816      * hbitmap_iter_skip_words.
 817      */
 818     assert(size == 1);
 819     hb->levels[0][0] |= 1UL << (BITS_PER_LONG - 1);
 820     return hb;
 821 }
 822
 823 void hbitmap_truncate(HBitmap *hb, uint64_t size)
 824 {
 825     bool shrink;
 826     unsigned i;
 827     uint64_t num_elements = size;
 828     uint64_t old;
 829
 830     assert(size <= INT64_MAX);
 831     hb->orig_size = size;
 832
 833     /* Size comes in as logical elements, adjust for granularity. */
 834     size = (size + (1ULL << hb->granularity) - 1) >> hb->granularity;
 835     assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE));
 836     shrink = size < hb->size;
 837
 838     /* bit sizes are identical; nothing to do. */
 839     if (size == hb->size) {
 840         return;
 841     }
 842
 843     /* If we're losing bits, let's clear those bits before we invalidate all of
 844      * our invariants. This helps keep the bitcount consistent, and will prevent
 845      * us from carrying around garbage bits beyond the end of the map.
 846      */
 847     if (shrink) {
 848         /* Don't clear partial granularity groups;
 849          * start at the first full one. */
 850         uint64_t start = ROUND_UP(num_elements, UINT64_C(1) << hb->granularity);
 851         uint64_t fix_count = (hb->size << hb->granularity) - start;
 852
 853         assert(fix_count);
 854         hbitmap_reset(hb, start, fix_count);
 855     }
 856
 857     hb->size = size;
 858     for (i = HBITMAP_LEVELS; i-- > 0; ) {
 859         size = MAX(BITS_TO_LONGS(size), 1);
 860         if (hb->sizes[i] == size) {
 861             break;
 862         }
 863         old = hb->sizes[i];
 864         hb->sizes[i] = size;
 865         hb->levels[i] = g_renew(unsigned long, hb->levels[i], size);
 866         if (!shrink) {
 867             memset(&hb->levels[i][old], 0x00,
 868                    (size - old) * sizeof(*hb->levels[i]));
 869         }
 870     }
 871     if (hb->meta) {
 872         hbitmap_truncate(hb->meta, hb->size << hb->granularity);
 873     }
 874 }
 875
 876 /**
 877  * hbitmap_sparse_merge: performs dst = dst | src
 878  * works with differing granularities.
 879  * best used when src is sparsely populated.
 880  */
 881 static void hbitmap_sparse_merge(HBitmap *dst, const HBitmap *src)
 882 {
 883     int64_t offset;
 884     int64_t count;
 885
 886     for (offset = 0;
 887          hbitmap_next_dirty_area(src, offset, src->orig_size, INT64_MAX,
 888                                  &offset, &count);
 889          offset += count)
 890     {
 891         hbitmap_set(dst, offset, count);
 892     }
 893 }
 894
 895 /**
 896  * Given HBitmaps A and B, let R := A (BITOR) B.
 897  * Bitmaps A and B will not be modified,
 898  *     except when bitmap R is an alias of A or B.
 899  * Bitmaps must have same size.
 900  */
 901 void hbitmap_merge(const HBitmap *a, const HBitmap *b, HBitmap *result)
 902 {
 903     int i;
 904     uint64_t j;
 905
 906     assert(a->orig_size == result->orig_size);
 907     assert(b->orig_size == result->orig_size);
 908
 909     if ((!hbitmap_count(a) && result == b) ||
 910         (!hbitmap_count(b) && result == a)) {
 911         return;
 912     }
 913
 914     if (!hbitmap_count(a) && !hbitmap_count(b)) {
 915         hbitmap_reset_all(result);
 916         return;
 917     }
 918
 919     if (a->granularity != b->granularity) {
 920         if ((a != result) && (b != result)) {
 921             hbitmap_reset_all(result);
 922         }
 923         if (a != result) {
 924             hbitmap_sparse_merge(result, a);
 925         }
 926         if (b != result) {
 927             hbitmap_sparse_merge(result, b);
 928         }
 929         return;
 930     }
 931
 932     /* This merge is O(size), as BITS_PER_LONG and HBITMAP_LEVELS are constant.
 933      * It may be possible to improve running times for sparsely populated maps
 934      * by using hbitmap_iter_next, but this is suboptimal for dense maps.
 935      */
 936     assert(a->size == b->size);
 937     for (i = HBITMAP_LEVELS - 1; i >= 0; i--) {
 938         for (j = 0; j < a->sizes[i]; j++) {
 939             result->levels[i][j] = a->levels[i][j] | b->levels[i][j];
 940         }
 941     }
 942
 943     /* Recompute the dirty count */
 944     result->count = hb_count_between(result, 0, result->size - 1);
 945 }
 946
 947 char *hbitmap_sha256(const HBitmap *bitmap, Error **errp)
 948 {
 949     size_t size = bitmap->sizes[HBITMAP_LEVELS - 1] * sizeof(unsigned long);
 950     char *data = (char *)bitmap->levels[HBITMAP_LEVELS - 1];
 951     char *hash = NULL;
 952     qcrypto_hash_digest(QCRYPTO_HASH_ALG_SHA256, data, size, &hash, errp);
 953
 954     return hash;
 955 }