qemu

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 true;
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
}
956