qemu/util/hbitmap.c
<<
>>
Prefs
   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
  55struct 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 */
 107static 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
 149int64_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
 169void 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
 196int64_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
 220int64_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
 273bool 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
 304bool 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 true;
 335}
 336
 337bool hbitmap_empty(const HBitmap *hb)
 338{
 339    return hb->count == 0;
 340}
 341
 342int hbitmap_granularity(const HBitmap *hb)
 343{
 344    return hb->granularity;
 345}
 346
 347uint64_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 */
 363static 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 */
 384static 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 */
 414static 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. */
 431static 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
 464void 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 */
 492static 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. */
 509static 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
 558void 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
 586void 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
 599bool 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
 617bool 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
 627uint64_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 */
 639static 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
 659uint64_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
 673void 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
 695void 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
 725void 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
 742void 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
 759void 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
 784void 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
 794HBitmap *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
 823void 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 */
 881static 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 */
 901void 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
 947char *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}
 956