1e7c033c3SPaolo Bonzini /* 2e7c033c3SPaolo Bonzini * Hierarchical Bitmap Data Type 3e7c033c3SPaolo Bonzini * 4e7c033c3SPaolo Bonzini * Copyright Red Hat, Inc., 2012 5e7c033c3SPaolo Bonzini * 6e7c033c3SPaolo Bonzini * Author: Paolo Bonzini <pbonzini@redhat.com> 7e7c033c3SPaolo Bonzini * 8e7c033c3SPaolo Bonzini * This work is licensed under the terms of the GNU GPL, version 2 or 9e7c033c3SPaolo Bonzini * later. See the COPYING file in the top-level directory. 10e7c033c3SPaolo Bonzini */ 11e7c033c3SPaolo Bonzini 12e7c033c3SPaolo Bonzini #include "qemu/osdep.h" 13e7c033c3SPaolo Bonzini #include "qemu/hbitmap.h" 14e7c033c3SPaolo Bonzini #include "qemu/host-utils.h" 15e7c033c3SPaolo Bonzini #include "trace.h" 16e7c033c3SPaolo Bonzini 17e7c033c3SPaolo Bonzini /* HBitmaps provides an array of bits. The bits are stored as usual in an 18e7c033c3SPaolo Bonzini * array of unsigned longs, but HBitmap is also optimized to provide fast 19e7c033c3SPaolo Bonzini * iteration over set bits; going from one bit to the next is O(logB n) 20e7c033c3SPaolo Bonzini * worst case, with B = sizeof(long) * CHAR_BIT: the result is low enough 21e7c033c3SPaolo Bonzini * that the number of levels is in fact fixed. 22e7c033c3SPaolo Bonzini * 23e7c033c3SPaolo Bonzini * In order to do this, it stacks multiple bitmaps with progressively coarser 24e7c033c3SPaolo Bonzini * granularity; in all levels except the last, bit N is set iff the N-th 25e7c033c3SPaolo Bonzini * unsigned long is nonzero in the immediately next level. When iteration 26e7c033c3SPaolo Bonzini * completes on the last level it can examine the 2nd-last level to quickly 27e7c033c3SPaolo Bonzini * skip entire words, and even do so recursively to skip blocks of 64 words or 28e7c033c3SPaolo Bonzini * powers thereof (32 on 32-bit machines). 29e7c033c3SPaolo Bonzini * 30e7c033c3SPaolo Bonzini * Given an index in the bitmap, it can be split in group of bits like 31e7c033c3SPaolo Bonzini * this (for the 64-bit case): 32e7c033c3SPaolo Bonzini * 33e7c033c3SPaolo Bonzini * bits 0-57 => word in the last bitmap | bits 58-63 => bit in the word 34e7c033c3SPaolo Bonzini * bits 0-51 => word in the 2nd-last bitmap | bits 52-57 => bit in the word 35e7c033c3SPaolo Bonzini * bits 0-45 => word in the 3rd-last bitmap | bits 46-51 => bit in the word 36e7c033c3SPaolo Bonzini * 37e7c033c3SPaolo Bonzini * So it is easy to move up simply by shifting the index right by 38e7c033c3SPaolo Bonzini * log2(BITS_PER_LONG) bits. To move down, you shift the index left 39e7c033c3SPaolo Bonzini * similarly, and add the word index within the group. Iteration uses 40e7c033c3SPaolo Bonzini * ffs (find first set bit) to find the next word to examine; this 41e7c033c3SPaolo Bonzini * operation can be done in constant time in most current architectures. 42e7c033c3SPaolo Bonzini * 43e7c033c3SPaolo Bonzini * Setting or clearing a range of m bits on all levels, the work to perform 44e7c033c3SPaolo Bonzini * is O(m + m/W + m/W^2 + ...), which is O(m) like on a regular bitmap. 45e7c033c3SPaolo Bonzini * 46e7c033c3SPaolo Bonzini * When iterating on a bitmap, each bit (on any level) is only visited 47e7c033c3SPaolo Bonzini * once. Hence, The total cost of visiting a bitmap with m bits in it is 48e7c033c3SPaolo Bonzini * the number of bits that are set in all bitmaps. Unless the bitmap is 49e7c033c3SPaolo Bonzini * extremely sparse, this is also O(m + m/W + m/W^2 + ...), so the amortized 50e7c033c3SPaolo Bonzini * cost of advancing from one bit to the next is usually constant (worst case 51e7c033c3SPaolo Bonzini * O(logB n) as in the non-amortized complexity). 52e7c033c3SPaolo Bonzini */ 53e7c033c3SPaolo Bonzini 54e7c033c3SPaolo Bonzini struct HBitmap { 55e7c033c3SPaolo Bonzini /* Number of total bits in the bottom level. */ 56e7c033c3SPaolo Bonzini uint64_t size; 57e7c033c3SPaolo Bonzini 58e7c033c3SPaolo Bonzini /* Number of set bits in the bottom level. */ 59e7c033c3SPaolo Bonzini uint64_t count; 60e7c033c3SPaolo Bonzini 61e7c033c3SPaolo Bonzini /* A scaling factor. Given a granularity of G, each bit in the bitmap will 62e7c033c3SPaolo Bonzini * will actually represent a group of 2^G elements. Each operation on a 63e7c033c3SPaolo Bonzini * range of bits first rounds the bits to determine which group they land 64e7c033c3SPaolo Bonzini * in, and then affect the entire page; iteration will only visit the first 65e7c033c3SPaolo Bonzini * bit of each group. Here is an example of operations in a size-16, 66e7c033c3SPaolo Bonzini * granularity-1 HBitmap: 67e7c033c3SPaolo Bonzini * 68e7c033c3SPaolo Bonzini * initial state 00000000 69e7c033c3SPaolo Bonzini * set(start=0, count=9) 11111000 (iter: 0, 2, 4, 6, 8) 70e7c033c3SPaolo Bonzini * reset(start=1, count=3) 00111000 (iter: 4, 6, 8) 71e7c033c3SPaolo Bonzini * set(start=9, count=2) 00111100 (iter: 4, 6, 8, 10) 72e7c033c3SPaolo Bonzini * reset(start=5, count=5) 00000000 73e7c033c3SPaolo Bonzini * 74e7c033c3SPaolo Bonzini * From an implementation point of view, when setting or resetting bits, 75e7c033c3SPaolo Bonzini * the bitmap will scale bit numbers right by this amount of bits. When 76e7c033c3SPaolo Bonzini * iterating, the bitmap will scale bit numbers left by this amount of 77e7c033c3SPaolo Bonzini * bits. 78e7c033c3SPaolo Bonzini */ 79e7c033c3SPaolo Bonzini int granularity; 80e7c033c3SPaolo Bonzini 8107ac4cdbSFam Zheng /* A meta dirty bitmap to track the dirtiness of bits in this HBitmap. */ 8207ac4cdbSFam Zheng HBitmap *meta; 8307ac4cdbSFam Zheng 84e7c033c3SPaolo Bonzini /* A number of progressively less coarse bitmaps (i.e. level 0 is the 85e7c033c3SPaolo Bonzini * coarsest). Each bit in level N represents a word in level N+1 that 86e7c033c3SPaolo Bonzini * has a set bit, except the last level where each bit represents the 87e7c033c3SPaolo Bonzini * actual bitmap. 88e7c033c3SPaolo Bonzini * 89e7c033c3SPaolo Bonzini * Note that all bitmaps have the same number of levels. Even a 1-bit 90e7c033c3SPaolo Bonzini * bitmap will still allocate HBITMAP_LEVELS arrays. 91e7c033c3SPaolo Bonzini */ 92e7c033c3SPaolo Bonzini unsigned long *levels[HBITMAP_LEVELS]; 938515efbeSJohn Snow 948515efbeSJohn Snow /* The length of each levels[] array. */ 958515efbeSJohn Snow uint64_t sizes[HBITMAP_LEVELS]; 96e7c033c3SPaolo Bonzini }; 97e7c033c3SPaolo Bonzini 98e7c033c3SPaolo Bonzini /* Advance hbi to the next nonzero word and return it. hbi->pos 99e7c033c3SPaolo Bonzini * is updated. Returns zero if we reach the end of the bitmap. 100e7c033c3SPaolo Bonzini */ 101e7c033c3SPaolo Bonzini unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi) 102e7c033c3SPaolo Bonzini { 103e7c033c3SPaolo Bonzini size_t pos = hbi->pos; 104e7c033c3SPaolo Bonzini const HBitmap *hb = hbi->hb; 105e7c033c3SPaolo Bonzini unsigned i = HBITMAP_LEVELS - 1; 106e7c033c3SPaolo Bonzini 107e7c033c3SPaolo Bonzini unsigned long cur; 108e7c033c3SPaolo Bonzini do { 109e7c033c3SPaolo Bonzini cur = hbi->cur[--i]; 110e7c033c3SPaolo Bonzini pos >>= BITS_PER_LEVEL; 111e7c033c3SPaolo Bonzini } while (cur == 0); 112e7c033c3SPaolo Bonzini 113e7c033c3SPaolo Bonzini /* Check for end of iteration. We always use fewer than BITS_PER_LONG 114e7c033c3SPaolo Bonzini * bits in the level 0 bitmap; thus we can repurpose the most significant 115e7c033c3SPaolo Bonzini * bit as a sentinel. The sentinel is set in hbitmap_alloc and ensures 116e7c033c3SPaolo Bonzini * that the above loop ends even without an explicit check on i. 117e7c033c3SPaolo Bonzini */ 118e7c033c3SPaolo Bonzini 119e7c033c3SPaolo Bonzini if (i == 0 && cur == (1UL << (BITS_PER_LONG - 1))) { 120e7c033c3SPaolo Bonzini return 0; 121e7c033c3SPaolo Bonzini } 122e7c033c3SPaolo Bonzini for (; i < HBITMAP_LEVELS - 1; i++) { 123e7c033c3SPaolo Bonzini /* Shift back pos to the left, matching the right shifts above. 124e7c033c3SPaolo Bonzini * The index of this word's least significant set bit provides 125e7c033c3SPaolo Bonzini * the low-order bits. 126e7c033c3SPaolo Bonzini */ 12718331e7cSRichard Henderson assert(cur); 12818331e7cSRichard Henderson pos = (pos << BITS_PER_LEVEL) + ctzl(cur); 129e7c033c3SPaolo Bonzini hbi->cur[i] = cur & (cur - 1); 130e7c033c3SPaolo Bonzini 131e7c033c3SPaolo Bonzini /* Set up next level for iteration. */ 132e7c033c3SPaolo Bonzini cur = hb->levels[i + 1][pos]; 133e7c033c3SPaolo Bonzini } 134e7c033c3SPaolo Bonzini 135e7c033c3SPaolo Bonzini hbi->pos = pos; 136e7c033c3SPaolo Bonzini trace_hbitmap_iter_skip_words(hbi->hb, hbi, pos, cur); 137e7c033c3SPaolo Bonzini 138e7c033c3SPaolo Bonzini assert(cur); 139e7c033c3SPaolo Bonzini return cur; 140e7c033c3SPaolo Bonzini } 141e7c033c3SPaolo Bonzini 142e7c033c3SPaolo Bonzini void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first) 143e7c033c3SPaolo Bonzini { 144e7c033c3SPaolo Bonzini unsigned i, bit; 145e7c033c3SPaolo Bonzini uint64_t pos; 146e7c033c3SPaolo Bonzini 147e7c033c3SPaolo Bonzini hbi->hb = hb; 148e7c033c3SPaolo Bonzini pos = first >> hb->granularity; 1491b095244SPaolo Bonzini assert(pos < hb->size); 150e7c033c3SPaolo Bonzini hbi->pos = pos >> BITS_PER_LEVEL; 151e7c033c3SPaolo Bonzini hbi->granularity = hb->granularity; 152e7c033c3SPaolo Bonzini 153e7c033c3SPaolo Bonzini for (i = HBITMAP_LEVELS; i-- > 0; ) { 154e7c033c3SPaolo Bonzini bit = pos & (BITS_PER_LONG - 1); 155e7c033c3SPaolo Bonzini pos >>= BITS_PER_LEVEL; 156e7c033c3SPaolo Bonzini 157e7c033c3SPaolo Bonzini /* Drop bits representing items before first. */ 158e7c033c3SPaolo Bonzini hbi->cur[i] = hb->levels[i][pos] & ~((1UL << bit) - 1); 159e7c033c3SPaolo Bonzini 160e7c033c3SPaolo Bonzini /* We have already added level i+1, so the lowest set bit has 161e7c033c3SPaolo Bonzini * been processed. Clear it. 162e7c033c3SPaolo Bonzini */ 163e7c033c3SPaolo Bonzini if (i != HBITMAP_LEVELS - 1) { 164e7c033c3SPaolo Bonzini hbi->cur[i] &= ~(1UL << bit); 165e7c033c3SPaolo Bonzini } 166e7c033c3SPaolo Bonzini } 167e7c033c3SPaolo Bonzini } 168e7c033c3SPaolo Bonzini 169e7c033c3SPaolo Bonzini bool hbitmap_empty(const HBitmap *hb) 170e7c033c3SPaolo Bonzini { 171e7c033c3SPaolo Bonzini return hb->count == 0; 172e7c033c3SPaolo Bonzini } 173e7c033c3SPaolo Bonzini 174e7c033c3SPaolo Bonzini int hbitmap_granularity(const HBitmap *hb) 175e7c033c3SPaolo Bonzini { 176e7c033c3SPaolo Bonzini return hb->granularity; 177e7c033c3SPaolo Bonzini } 178e7c033c3SPaolo Bonzini 179e7c033c3SPaolo Bonzini uint64_t hbitmap_count(const HBitmap *hb) 180e7c033c3SPaolo Bonzini { 181e7c033c3SPaolo Bonzini return hb->count << hb->granularity; 182e7c033c3SPaolo Bonzini } 183e7c033c3SPaolo Bonzini 184e7c033c3SPaolo Bonzini /* Count the number of set bits between start and end, not accounting for 185e7c033c3SPaolo Bonzini * the granularity. Also an example of how to use hbitmap_iter_next_word. 186e7c033c3SPaolo Bonzini */ 187e7c033c3SPaolo Bonzini static uint64_t hb_count_between(HBitmap *hb, uint64_t start, uint64_t last) 188e7c033c3SPaolo Bonzini { 189e7c033c3SPaolo Bonzini HBitmapIter hbi; 190e7c033c3SPaolo Bonzini uint64_t count = 0; 191e7c033c3SPaolo Bonzini uint64_t end = last + 1; 192e7c033c3SPaolo Bonzini unsigned long cur; 193e7c033c3SPaolo Bonzini size_t pos; 194e7c033c3SPaolo Bonzini 195e7c033c3SPaolo Bonzini hbitmap_iter_init(&hbi, hb, start << hb->granularity); 196e7c033c3SPaolo Bonzini for (;;) { 197e7c033c3SPaolo Bonzini pos = hbitmap_iter_next_word(&hbi, &cur); 198e7c033c3SPaolo Bonzini if (pos >= (end >> BITS_PER_LEVEL)) { 199e7c033c3SPaolo Bonzini break; 200e7c033c3SPaolo Bonzini } 201591b320aSPeter Maydell count += ctpopl(cur); 202e7c033c3SPaolo Bonzini } 203e7c033c3SPaolo Bonzini 204e7c033c3SPaolo Bonzini if (pos == (end >> BITS_PER_LEVEL)) { 205e7c033c3SPaolo Bonzini /* Drop bits representing the END-th and subsequent items. */ 206e7c033c3SPaolo Bonzini int bit = end & (BITS_PER_LONG - 1); 207e7c033c3SPaolo Bonzini cur &= (1UL << bit) - 1; 208591b320aSPeter Maydell count += ctpopl(cur); 209e7c033c3SPaolo Bonzini } 210e7c033c3SPaolo Bonzini 211e7c033c3SPaolo Bonzini return count; 212e7c033c3SPaolo Bonzini } 213e7c033c3SPaolo Bonzini 214e7c033c3SPaolo Bonzini /* Setting starts at the last layer and propagates up if an element 21507ac4cdbSFam Zheng * changes. 216e7c033c3SPaolo Bonzini */ 217e7c033c3SPaolo Bonzini static inline bool hb_set_elem(unsigned long *elem, uint64_t start, uint64_t last) 218e7c033c3SPaolo Bonzini { 219e7c033c3SPaolo Bonzini unsigned long mask; 22007ac4cdbSFam Zheng unsigned long old; 221e7c033c3SPaolo Bonzini 222e7c033c3SPaolo Bonzini assert((last >> BITS_PER_LEVEL) == (start >> BITS_PER_LEVEL)); 223e7c033c3SPaolo Bonzini assert(start <= last); 224e7c033c3SPaolo Bonzini 225e7c033c3SPaolo Bonzini mask = 2UL << (last & (BITS_PER_LONG - 1)); 226e7c033c3SPaolo Bonzini mask -= 1UL << (start & (BITS_PER_LONG - 1)); 22707ac4cdbSFam Zheng old = *elem; 228e7c033c3SPaolo Bonzini *elem |= mask; 22907ac4cdbSFam Zheng return old != *elem; 230e7c033c3SPaolo Bonzini } 231e7c033c3SPaolo Bonzini 23207ac4cdbSFam Zheng /* The recursive workhorse (the depth is limited to HBITMAP_LEVELS)... 23307ac4cdbSFam Zheng * Returns true if at least one bit is changed. */ 23407ac4cdbSFam Zheng static bool hb_set_between(HBitmap *hb, int level, uint64_t start, 23507ac4cdbSFam Zheng uint64_t last) 236e7c033c3SPaolo Bonzini { 237e7c033c3SPaolo Bonzini size_t pos = start >> BITS_PER_LEVEL; 238e7c033c3SPaolo Bonzini size_t lastpos = last >> BITS_PER_LEVEL; 239e7c033c3SPaolo Bonzini bool changed = false; 240e7c033c3SPaolo Bonzini size_t i; 241e7c033c3SPaolo Bonzini 242e7c033c3SPaolo Bonzini i = pos; 243e7c033c3SPaolo Bonzini if (i < lastpos) { 244e7c033c3SPaolo Bonzini uint64_t next = (start | (BITS_PER_LONG - 1)) + 1; 245e7c033c3SPaolo Bonzini changed |= hb_set_elem(&hb->levels[level][i], start, next - 1); 246e7c033c3SPaolo Bonzini for (;;) { 247e7c033c3SPaolo Bonzini start = next; 248e7c033c3SPaolo Bonzini next += BITS_PER_LONG; 249e7c033c3SPaolo Bonzini if (++i == lastpos) { 250e7c033c3SPaolo Bonzini break; 251e7c033c3SPaolo Bonzini } 252e7c033c3SPaolo Bonzini changed |= (hb->levels[level][i] == 0); 253e7c033c3SPaolo Bonzini hb->levels[level][i] = ~0UL; 254e7c033c3SPaolo Bonzini } 255e7c033c3SPaolo Bonzini } 256e7c033c3SPaolo Bonzini changed |= hb_set_elem(&hb->levels[level][i], start, last); 257e7c033c3SPaolo Bonzini 258e7c033c3SPaolo Bonzini /* If there was any change in this layer, we may have to update 259e7c033c3SPaolo Bonzini * the one above. 260e7c033c3SPaolo Bonzini */ 261e7c033c3SPaolo Bonzini if (level > 0 && changed) { 262e7c033c3SPaolo Bonzini hb_set_between(hb, level - 1, pos, lastpos); 263e7c033c3SPaolo Bonzini } 26407ac4cdbSFam Zheng return changed; 265e7c033c3SPaolo Bonzini } 266e7c033c3SPaolo Bonzini 267e7c033c3SPaolo Bonzini void hbitmap_set(HBitmap *hb, uint64_t start, uint64_t count) 268e7c033c3SPaolo Bonzini { 269e7c033c3SPaolo Bonzini /* Compute range in the last layer. */ 27007ac4cdbSFam Zheng uint64_t first, n; 271e7c033c3SPaolo Bonzini uint64_t last = start + count - 1; 272e7c033c3SPaolo Bonzini 273e7c033c3SPaolo Bonzini trace_hbitmap_set(hb, start, count, 274e7c033c3SPaolo Bonzini start >> hb->granularity, last >> hb->granularity); 275e7c033c3SPaolo Bonzini 27607ac4cdbSFam Zheng first = start >> hb->granularity; 277e7c033c3SPaolo Bonzini last >>= hb->granularity; 2780e321191SVladimir Sementsov-Ogievskiy assert(last < hb->size); 27907ac4cdbSFam Zheng n = last - first + 1; 280e7c033c3SPaolo Bonzini 28107ac4cdbSFam Zheng hb->count += n - hb_count_between(hb, first, last); 28207ac4cdbSFam Zheng if (hb_set_between(hb, HBITMAP_LEVELS - 1, first, last) && 28307ac4cdbSFam Zheng hb->meta) { 28407ac4cdbSFam Zheng hbitmap_set(hb->meta, start, count); 28507ac4cdbSFam Zheng } 286e7c033c3SPaolo Bonzini } 287e7c033c3SPaolo Bonzini 288e7c033c3SPaolo Bonzini /* Resetting works the other way round: propagate up if the new 289e7c033c3SPaolo Bonzini * value is zero. 290e7c033c3SPaolo Bonzini */ 291e7c033c3SPaolo Bonzini static inline bool hb_reset_elem(unsigned long *elem, uint64_t start, uint64_t last) 292e7c033c3SPaolo Bonzini { 293e7c033c3SPaolo Bonzini unsigned long mask; 294e7c033c3SPaolo Bonzini bool blanked; 295e7c033c3SPaolo Bonzini 296e7c033c3SPaolo Bonzini assert((last >> BITS_PER_LEVEL) == (start >> BITS_PER_LEVEL)); 297e7c033c3SPaolo Bonzini assert(start <= last); 298e7c033c3SPaolo Bonzini 299e7c033c3SPaolo Bonzini mask = 2UL << (last & (BITS_PER_LONG - 1)); 300e7c033c3SPaolo Bonzini mask -= 1UL << (start & (BITS_PER_LONG - 1)); 301e7c033c3SPaolo Bonzini blanked = *elem != 0 && ((*elem & ~mask) == 0); 302e7c033c3SPaolo Bonzini *elem &= ~mask; 303e7c033c3SPaolo Bonzini return blanked; 304e7c033c3SPaolo Bonzini } 305e7c033c3SPaolo Bonzini 30607ac4cdbSFam Zheng /* The recursive workhorse (the depth is limited to HBITMAP_LEVELS)... 30707ac4cdbSFam Zheng * Returns true if at least one bit is changed. */ 30807ac4cdbSFam Zheng static bool hb_reset_between(HBitmap *hb, int level, uint64_t start, 30907ac4cdbSFam Zheng uint64_t last) 310e7c033c3SPaolo Bonzini { 311e7c033c3SPaolo Bonzini size_t pos = start >> BITS_PER_LEVEL; 312e7c033c3SPaolo Bonzini size_t lastpos = last >> BITS_PER_LEVEL; 313e7c033c3SPaolo Bonzini bool changed = false; 314e7c033c3SPaolo Bonzini size_t i; 315e7c033c3SPaolo Bonzini 316e7c033c3SPaolo Bonzini i = pos; 317e7c033c3SPaolo Bonzini if (i < lastpos) { 318e7c033c3SPaolo Bonzini uint64_t next = (start | (BITS_PER_LONG - 1)) + 1; 319e7c033c3SPaolo Bonzini 320e7c033c3SPaolo Bonzini /* Here we need a more complex test than when setting bits. Even if 321e7c033c3SPaolo Bonzini * something was changed, we must not blank bits in the upper level 322e7c033c3SPaolo Bonzini * unless the lower-level word became entirely zero. So, remove pos 323e7c033c3SPaolo Bonzini * from the upper-level range if bits remain set. 324e7c033c3SPaolo Bonzini */ 325e7c033c3SPaolo Bonzini if (hb_reset_elem(&hb->levels[level][i], start, next - 1)) { 326e7c033c3SPaolo Bonzini changed = true; 327e7c033c3SPaolo Bonzini } else { 328e7c033c3SPaolo Bonzini pos++; 329e7c033c3SPaolo Bonzini } 330e7c033c3SPaolo Bonzini 331e7c033c3SPaolo Bonzini for (;;) { 332e7c033c3SPaolo Bonzini start = next; 333e7c033c3SPaolo Bonzini next += BITS_PER_LONG; 334e7c033c3SPaolo Bonzini if (++i == lastpos) { 335e7c033c3SPaolo Bonzini break; 336e7c033c3SPaolo Bonzini } 337e7c033c3SPaolo Bonzini changed |= (hb->levels[level][i] != 0); 338e7c033c3SPaolo Bonzini hb->levels[level][i] = 0UL; 339e7c033c3SPaolo Bonzini } 340e7c033c3SPaolo Bonzini } 341e7c033c3SPaolo Bonzini 342e7c033c3SPaolo Bonzini /* Same as above, this time for lastpos. */ 343e7c033c3SPaolo Bonzini if (hb_reset_elem(&hb->levels[level][i], start, last)) { 344e7c033c3SPaolo Bonzini changed = true; 345e7c033c3SPaolo Bonzini } else { 346e7c033c3SPaolo Bonzini lastpos--; 347e7c033c3SPaolo Bonzini } 348e7c033c3SPaolo Bonzini 349e7c033c3SPaolo Bonzini if (level > 0 && changed) { 350e7c033c3SPaolo Bonzini hb_reset_between(hb, level - 1, pos, lastpos); 351e7c033c3SPaolo Bonzini } 35207ac4cdbSFam Zheng 35307ac4cdbSFam Zheng return changed; 35407ac4cdbSFam Zheng 355e7c033c3SPaolo Bonzini } 356e7c033c3SPaolo Bonzini 357e7c033c3SPaolo Bonzini void hbitmap_reset(HBitmap *hb, uint64_t start, uint64_t count) 358e7c033c3SPaolo Bonzini { 359e7c033c3SPaolo Bonzini /* Compute range in the last layer. */ 36007ac4cdbSFam Zheng uint64_t first; 361e7c033c3SPaolo Bonzini uint64_t last = start + count - 1; 362e7c033c3SPaolo Bonzini 363e7c033c3SPaolo Bonzini trace_hbitmap_reset(hb, start, count, 364e7c033c3SPaolo Bonzini start >> hb->granularity, last >> hb->granularity); 365e7c033c3SPaolo Bonzini 36607ac4cdbSFam Zheng first = start >> hb->granularity; 367e7c033c3SPaolo Bonzini last >>= hb->granularity; 3680e321191SVladimir Sementsov-Ogievskiy assert(last < hb->size); 369e7c033c3SPaolo Bonzini 37007ac4cdbSFam Zheng hb->count -= hb_count_between(hb, first, last); 37107ac4cdbSFam Zheng if (hb_reset_between(hb, HBITMAP_LEVELS - 1, first, last) && 37207ac4cdbSFam Zheng hb->meta) { 37307ac4cdbSFam Zheng hbitmap_set(hb->meta, start, count); 37407ac4cdbSFam Zheng } 375e7c033c3SPaolo Bonzini } 376e7c033c3SPaolo Bonzini 377c6a8c328SWen Congyang void hbitmap_reset_all(HBitmap *hb) 378c6a8c328SWen Congyang { 379c6a8c328SWen Congyang unsigned int i; 380c6a8c328SWen Congyang 381c6a8c328SWen Congyang /* Same as hbitmap_alloc() except for memset() instead of malloc() */ 382c6a8c328SWen Congyang for (i = HBITMAP_LEVELS; --i >= 1; ) { 383c6a8c328SWen Congyang memset(hb->levels[i], 0, hb->sizes[i] * sizeof(unsigned long)); 384c6a8c328SWen Congyang } 385c6a8c328SWen Congyang 386c6a8c328SWen Congyang hb->levels[0][0] = 1UL << (BITS_PER_LONG - 1); 387c6a8c328SWen Congyang hb->count = 0; 388c6a8c328SWen Congyang } 389c6a8c328SWen Congyang 390*20a579deSMax Reitz bool hbitmap_is_serializable(const HBitmap *hb) 391*20a579deSMax Reitz { 392*20a579deSMax Reitz /* Every serialized chunk must be aligned to 64 bits so that endianness 393*20a579deSMax Reitz * requirements can be fulfilled on both 64 bit and 32 bit hosts. 394*20a579deSMax Reitz * We have hbitmap_serialization_granularity() which converts this 395*20a579deSMax Reitz * alignment requirement from bitmap bits to items covered (e.g. sectors). 396*20a579deSMax Reitz * That value is: 397*20a579deSMax Reitz * 64 << hb->granularity 398*20a579deSMax Reitz * Since this value must not exceed UINT64_MAX, hb->granularity must be 399*20a579deSMax Reitz * less than 58 (== 64 - 6, where 6 is ld(64), i.e. 1 << 6 == 64). 400*20a579deSMax Reitz * 401*20a579deSMax Reitz * In order for hbitmap_serialization_granularity() to always return a 402*20a579deSMax Reitz * meaningful value, bitmaps that are to be serialized must have a 403*20a579deSMax Reitz * granularity of less than 58. */ 404*20a579deSMax Reitz 405*20a579deSMax Reitz return hb->granularity < 58; 406*20a579deSMax Reitz } 407*20a579deSMax Reitz 408e7c033c3SPaolo Bonzini bool hbitmap_get(const HBitmap *hb, uint64_t item) 409e7c033c3SPaolo Bonzini { 410e7c033c3SPaolo Bonzini /* Compute position and bit in the last layer. */ 411e7c033c3SPaolo Bonzini uint64_t pos = item >> hb->granularity; 412e7c033c3SPaolo Bonzini unsigned long bit = 1UL << (pos & (BITS_PER_LONG - 1)); 4130e321191SVladimir Sementsov-Ogievskiy assert(pos < hb->size); 414e7c033c3SPaolo Bonzini 415e7c033c3SPaolo Bonzini return (hb->levels[HBITMAP_LEVELS - 1][pos >> BITS_PER_LEVEL] & bit) != 0; 416e7c033c3SPaolo Bonzini } 417e7c033c3SPaolo Bonzini 4188258888eSVladimir Sementsov-Ogievskiy uint64_t hbitmap_serialization_granularity(const HBitmap *hb) 4198258888eSVladimir Sementsov-Ogievskiy { 420*20a579deSMax Reitz assert(hbitmap_is_serializable(hb)); 4216725f887SMax Reitz 4228258888eSVladimir Sementsov-Ogievskiy /* Require at least 64 bit granularity to be safe on both 64 bit and 32 bit 4238258888eSVladimir Sementsov-Ogievskiy * hosts. */ 4246725f887SMax Reitz return UINT64_C(64) << hb->granularity; 4258258888eSVladimir Sementsov-Ogievskiy } 4268258888eSVladimir Sementsov-Ogievskiy 4278258888eSVladimir Sementsov-Ogievskiy /* Start should be aligned to serialization granularity, chunk size should be 4288258888eSVladimir Sementsov-Ogievskiy * aligned to serialization granularity too, except for last chunk. 4298258888eSVladimir Sementsov-Ogievskiy */ 4308258888eSVladimir Sementsov-Ogievskiy static void serialization_chunk(const HBitmap *hb, 4318258888eSVladimir Sementsov-Ogievskiy uint64_t start, uint64_t count, 4328258888eSVladimir Sementsov-Ogievskiy unsigned long **first_el, uint64_t *el_count) 4338258888eSVladimir Sementsov-Ogievskiy { 4348258888eSVladimir Sementsov-Ogievskiy uint64_t last = start + count - 1; 4358258888eSVladimir Sementsov-Ogievskiy uint64_t gran = hbitmap_serialization_granularity(hb); 4368258888eSVladimir Sementsov-Ogievskiy 4378258888eSVladimir Sementsov-Ogievskiy assert((start & (gran - 1)) == 0); 4388258888eSVladimir Sementsov-Ogievskiy assert((last >> hb->granularity) < hb->size); 4398258888eSVladimir Sementsov-Ogievskiy if ((last >> hb->granularity) != hb->size - 1) { 4408258888eSVladimir Sementsov-Ogievskiy assert((count & (gran - 1)) == 0); 4418258888eSVladimir Sementsov-Ogievskiy } 4428258888eSVladimir Sementsov-Ogievskiy 4438258888eSVladimir Sementsov-Ogievskiy start = (start >> hb->granularity) >> BITS_PER_LEVEL; 4448258888eSVladimir Sementsov-Ogievskiy last = (last >> hb->granularity) >> BITS_PER_LEVEL; 4458258888eSVladimir Sementsov-Ogievskiy 4468258888eSVladimir Sementsov-Ogievskiy *first_el = &hb->levels[HBITMAP_LEVELS - 1][start]; 4478258888eSVladimir Sementsov-Ogievskiy *el_count = last - start + 1; 4488258888eSVladimir Sementsov-Ogievskiy } 4498258888eSVladimir Sementsov-Ogievskiy 4508258888eSVladimir Sementsov-Ogievskiy uint64_t hbitmap_serialization_size(const HBitmap *hb, 4518258888eSVladimir Sementsov-Ogievskiy uint64_t start, uint64_t count) 4528258888eSVladimir Sementsov-Ogievskiy { 4538258888eSVladimir Sementsov-Ogievskiy uint64_t el_count; 4548258888eSVladimir Sementsov-Ogievskiy unsigned long *cur; 4558258888eSVladimir Sementsov-Ogievskiy 4568258888eSVladimir Sementsov-Ogievskiy if (!count) { 4578258888eSVladimir Sementsov-Ogievskiy return 0; 4588258888eSVladimir Sementsov-Ogievskiy } 4598258888eSVladimir Sementsov-Ogievskiy serialization_chunk(hb, start, count, &cur, &el_count); 4608258888eSVladimir Sementsov-Ogievskiy 4618258888eSVladimir Sementsov-Ogievskiy return el_count * sizeof(unsigned long); 4628258888eSVladimir Sementsov-Ogievskiy } 4638258888eSVladimir Sementsov-Ogievskiy 4648258888eSVladimir Sementsov-Ogievskiy void hbitmap_serialize_part(const HBitmap *hb, uint8_t *buf, 4658258888eSVladimir Sementsov-Ogievskiy uint64_t start, uint64_t count) 4668258888eSVladimir Sementsov-Ogievskiy { 4678258888eSVladimir Sementsov-Ogievskiy uint64_t el_count; 4688258888eSVladimir Sementsov-Ogievskiy unsigned long *cur, *end; 4698258888eSVladimir Sementsov-Ogievskiy 4708258888eSVladimir Sementsov-Ogievskiy if (!count) { 4718258888eSVladimir Sementsov-Ogievskiy return; 4728258888eSVladimir Sementsov-Ogievskiy } 4738258888eSVladimir Sementsov-Ogievskiy serialization_chunk(hb, start, count, &cur, &el_count); 4748258888eSVladimir Sementsov-Ogievskiy end = cur + el_count; 4758258888eSVladimir Sementsov-Ogievskiy 4768258888eSVladimir Sementsov-Ogievskiy while (cur != end) { 4778258888eSVladimir Sementsov-Ogievskiy unsigned long el = 4788258888eSVladimir Sementsov-Ogievskiy (BITS_PER_LONG == 32 ? cpu_to_le32(*cur) : cpu_to_le64(*cur)); 4798258888eSVladimir Sementsov-Ogievskiy 4808258888eSVladimir Sementsov-Ogievskiy memcpy(buf, &el, sizeof(el)); 4818258888eSVladimir Sementsov-Ogievskiy buf += sizeof(el); 4828258888eSVladimir Sementsov-Ogievskiy cur++; 4838258888eSVladimir Sementsov-Ogievskiy } 4848258888eSVladimir Sementsov-Ogievskiy } 4858258888eSVladimir Sementsov-Ogievskiy 4868258888eSVladimir Sementsov-Ogievskiy void hbitmap_deserialize_part(HBitmap *hb, uint8_t *buf, 4878258888eSVladimir Sementsov-Ogievskiy uint64_t start, uint64_t count, 4888258888eSVladimir Sementsov-Ogievskiy bool finish) 4898258888eSVladimir Sementsov-Ogievskiy { 4908258888eSVladimir Sementsov-Ogievskiy uint64_t el_count; 4918258888eSVladimir Sementsov-Ogievskiy unsigned long *cur, *end; 4928258888eSVladimir Sementsov-Ogievskiy 4938258888eSVladimir Sementsov-Ogievskiy if (!count) { 4948258888eSVladimir Sementsov-Ogievskiy return; 4958258888eSVladimir Sementsov-Ogievskiy } 4968258888eSVladimir Sementsov-Ogievskiy serialization_chunk(hb, start, count, &cur, &el_count); 4978258888eSVladimir Sementsov-Ogievskiy end = cur + el_count; 4988258888eSVladimir Sementsov-Ogievskiy 4998258888eSVladimir Sementsov-Ogievskiy while (cur != end) { 5008258888eSVladimir Sementsov-Ogievskiy memcpy(cur, buf, sizeof(*cur)); 5018258888eSVladimir Sementsov-Ogievskiy 5028258888eSVladimir Sementsov-Ogievskiy if (BITS_PER_LONG == 32) { 5038258888eSVladimir Sementsov-Ogievskiy le32_to_cpus((uint32_t *)cur); 5048258888eSVladimir Sementsov-Ogievskiy } else { 5058258888eSVladimir Sementsov-Ogievskiy le64_to_cpus((uint64_t *)cur); 5068258888eSVladimir Sementsov-Ogievskiy } 5078258888eSVladimir Sementsov-Ogievskiy 5088258888eSVladimir Sementsov-Ogievskiy buf += sizeof(unsigned long); 5098258888eSVladimir Sementsov-Ogievskiy cur++; 5108258888eSVladimir Sementsov-Ogievskiy } 5118258888eSVladimir Sementsov-Ogievskiy if (finish) { 5128258888eSVladimir Sementsov-Ogievskiy hbitmap_deserialize_finish(hb); 5138258888eSVladimir Sementsov-Ogievskiy } 5148258888eSVladimir Sementsov-Ogievskiy } 5158258888eSVladimir Sementsov-Ogievskiy 5168258888eSVladimir Sementsov-Ogievskiy void hbitmap_deserialize_zeroes(HBitmap *hb, uint64_t start, uint64_t count, 5178258888eSVladimir Sementsov-Ogievskiy bool finish) 5188258888eSVladimir Sementsov-Ogievskiy { 5198258888eSVladimir Sementsov-Ogievskiy uint64_t el_count; 5208258888eSVladimir Sementsov-Ogievskiy unsigned long *first; 5218258888eSVladimir Sementsov-Ogievskiy 5228258888eSVladimir Sementsov-Ogievskiy if (!count) { 5238258888eSVladimir Sementsov-Ogievskiy return; 5248258888eSVladimir Sementsov-Ogievskiy } 5258258888eSVladimir Sementsov-Ogievskiy serialization_chunk(hb, start, count, &first, &el_count); 5268258888eSVladimir Sementsov-Ogievskiy 5278258888eSVladimir Sementsov-Ogievskiy memset(first, 0, el_count * sizeof(unsigned long)); 5288258888eSVladimir Sementsov-Ogievskiy if (finish) { 5298258888eSVladimir Sementsov-Ogievskiy hbitmap_deserialize_finish(hb); 5308258888eSVladimir Sementsov-Ogievskiy } 5318258888eSVladimir Sementsov-Ogievskiy } 5328258888eSVladimir Sementsov-Ogievskiy 5338258888eSVladimir Sementsov-Ogievskiy void hbitmap_deserialize_finish(HBitmap *bitmap) 5348258888eSVladimir Sementsov-Ogievskiy { 5358258888eSVladimir Sementsov-Ogievskiy int64_t i, size, prev_size; 5368258888eSVladimir Sementsov-Ogievskiy int lev; 5378258888eSVladimir Sementsov-Ogievskiy 5388258888eSVladimir Sementsov-Ogievskiy /* restore levels starting from penultimate to zero level, assuming 5398258888eSVladimir Sementsov-Ogievskiy * that the last level is ok */ 5408258888eSVladimir Sementsov-Ogievskiy size = MAX((bitmap->size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL, 1); 5418258888eSVladimir Sementsov-Ogievskiy for (lev = HBITMAP_LEVELS - 1; lev-- > 0; ) { 5428258888eSVladimir Sementsov-Ogievskiy prev_size = size; 5438258888eSVladimir Sementsov-Ogievskiy size = MAX((size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL, 1); 5448258888eSVladimir Sementsov-Ogievskiy memset(bitmap->levels[lev], 0, size * sizeof(unsigned long)); 5458258888eSVladimir Sementsov-Ogievskiy 5468258888eSVladimir Sementsov-Ogievskiy for (i = 0; i < prev_size; ++i) { 5478258888eSVladimir Sementsov-Ogievskiy if (bitmap->levels[lev + 1][i]) { 5488258888eSVladimir Sementsov-Ogievskiy bitmap->levels[lev][i >> BITS_PER_LEVEL] |= 5498258888eSVladimir Sementsov-Ogievskiy 1UL << (i & (BITS_PER_LONG - 1)); 5508258888eSVladimir Sementsov-Ogievskiy } 5518258888eSVladimir Sementsov-Ogievskiy } 5528258888eSVladimir Sementsov-Ogievskiy } 5538258888eSVladimir Sementsov-Ogievskiy 5548258888eSVladimir Sementsov-Ogievskiy bitmap->levels[0][0] |= 1UL << (BITS_PER_LONG - 1); 5558258888eSVladimir Sementsov-Ogievskiy } 5568258888eSVladimir Sementsov-Ogievskiy 557e7c033c3SPaolo Bonzini void hbitmap_free(HBitmap *hb) 558e7c033c3SPaolo Bonzini { 559e7c033c3SPaolo Bonzini unsigned i; 56007ac4cdbSFam Zheng assert(!hb->meta); 561e7c033c3SPaolo Bonzini for (i = HBITMAP_LEVELS; i-- > 0; ) { 562e7c033c3SPaolo Bonzini g_free(hb->levels[i]); 563e7c033c3SPaolo Bonzini } 564e7c033c3SPaolo Bonzini g_free(hb); 565e7c033c3SPaolo Bonzini } 566e7c033c3SPaolo Bonzini 567e7c033c3SPaolo Bonzini HBitmap *hbitmap_alloc(uint64_t size, int granularity) 568e7c033c3SPaolo Bonzini { 569e1cf5582SMarkus Armbruster HBitmap *hb = g_new0(struct HBitmap, 1); 570e7c033c3SPaolo Bonzini unsigned i; 571e7c033c3SPaolo Bonzini 572e7c033c3SPaolo Bonzini assert(granularity >= 0 && granularity < 64); 573e7c033c3SPaolo Bonzini size = (size + (1ULL << granularity) - 1) >> granularity; 574e7c033c3SPaolo Bonzini assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE)); 575e7c033c3SPaolo Bonzini 576e7c033c3SPaolo Bonzini hb->size = size; 577e7c033c3SPaolo Bonzini hb->granularity = granularity; 578e7c033c3SPaolo Bonzini for (i = HBITMAP_LEVELS; i-- > 0; ) { 579e7c033c3SPaolo Bonzini size = MAX((size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL, 1); 5808515efbeSJohn Snow hb->sizes[i] = size; 581e1cf5582SMarkus Armbruster hb->levels[i] = g_new0(unsigned long, size); 582e7c033c3SPaolo Bonzini } 583e7c033c3SPaolo Bonzini 584e7c033c3SPaolo Bonzini /* We necessarily have free bits in level 0 due to the definition 585e7c033c3SPaolo Bonzini * of HBITMAP_LEVELS, so use one for a sentinel. This speeds up 586e7c033c3SPaolo Bonzini * hbitmap_iter_skip_words. 587e7c033c3SPaolo Bonzini */ 588e7c033c3SPaolo Bonzini assert(size == 1); 589e7c033c3SPaolo Bonzini hb->levels[0][0] |= 1UL << (BITS_PER_LONG - 1); 590e7c033c3SPaolo Bonzini return hb; 591e7c033c3SPaolo Bonzini } 592be58721dSJohn Snow 593ce1ffea8SJohn Snow void hbitmap_truncate(HBitmap *hb, uint64_t size) 594ce1ffea8SJohn Snow { 595ce1ffea8SJohn Snow bool shrink; 596ce1ffea8SJohn Snow unsigned i; 597ce1ffea8SJohn Snow uint64_t num_elements = size; 598ce1ffea8SJohn Snow uint64_t old; 599ce1ffea8SJohn Snow 600ce1ffea8SJohn Snow /* Size comes in as logical elements, adjust for granularity. */ 601ce1ffea8SJohn Snow size = (size + (1ULL << hb->granularity) - 1) >> hb->granularity; 602ce1ffea8SJohn Snow assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE)); 603ce1ffea8SJohn Snow shrink = size < hb->size; 604ce1ffea8SJohn Snow 605ce1ffea8SJohn Snow /* bit sizes are identical; nothing to do. */ 606ce1ffea8SJohn Snow if (size == hb->size) { 607ce1ffea8SJohn Snow return; 608ce1ffea8SJohn Snow } 609ce1ffea8SJohn Snow 610ce1ffea8SJohn Snow /* If we're losing bits, let's clear those bits before we invalidate all of 611ce1ffea8SJohn Snow * our invariants. This helps keep the bitcount consistent, and will prevent 612ce1ffea8SJohn Snow * us from carrying around garbage bits beyond the end of the map. 613ce1ffea8SJohn Snow */ 614ce1ffea8SJohn Snow if (shrink) { 615ce1ffea8SJohn Snow /* Don't clear partial granularity groups; 616ce1ffea8SJohn Snow * start at the first full one. */ 6176725f887SMax Reitz uint64_t start = ROUND_UP(num_elements, UINT64_C(1) << hb->granularity); 618ce1ffea8SJohn Snow uint64_t fix_count = (hb->size << hb->granularity) - start; 619ce1ffea8SJohn Snow 620ce1ffea8SJohn Snow assert(fix_count); 621ce1ffea8SJohn Snow hbitmap_reset(hb, start, fix_count); 622ce1ffea8SJohn Snow } 623ce1ffea8SJohn Snow 624ce1ffea8SJohn Snow hb->size = size; 625ce1ffea8SJohn Snow for (i = HBITMAP_LEVELS; i-- > 0; ) { 626ce1ffea8SJohn Snow size = MAX(BITS_TO_LONGS(size), 1); 627ce1ffea8SJohn Snow if (hb->sizes[i] == size) { 628ce1ffea8SJohn Snow break; 629ce1ffea8SJohn Snow } 630ce1ffea8SJohn Snow old = hb->sizes[i]; 631ce1ffea8SJohn Snow hb->sizes[i] = size; 632ce1ffea8SJohn Snow hb->levels[i] = g_realloc(hb->levels[i], size * sizeof(unsigned long)); 633ce1ffea8SJohn Snow if (!shrink) { 634ce1ffea8SJohn Snow memset(&hb->levels[i][old], 0x00, 635ce1ffea8SJohn Snow (size - old) * sizeof(*hb->levels[i])); 636ce1ffea8SJohn Snow } 637ce1ffea8SJohn Snow } 63807ac4cdbSFam Zheng if (hb->meta) { 63907ac4cdbSFam Zheng hbitmap_truncate(hb->meta, hb->size << hb->granularity); 64007ac4cdbSFam Zheng } 641ce1ffea8SJohn Snow } 642ce1ffea8SJohn Snow 643ce1ffea8SJohn Snow 644be58721dSJohn Snow /** 645be58721dSJohn Snow * Given HBitmaps A and B, let A := A (BITOR) B. 646be58721dSJohn Snow * Bitmap B will not be modified. 647be58721dSJohn Snow * 648be58721dSJohn Snow * @return true if the merge was successful, 649be58721dSJohn Snow * false if it was not attempted. 650be58721dSJohn Snow */ 651be58721dSJohn Snow bool hbitmap_merge(HBitmap *a, const HBitmap *b) 652be58721dSJohn Snow { 653be58721dSJohn Snow int i; 654be58721dSJohn Snow uint64_t j; 655be58721dSJohn Snow 656be58721dSJohn Snow if ((a->size != b->size) || (a->granularity != b->granularity)) { 657be58721dSJohn Snow return false; 658be58721dSJohn Snow } 659be58721dSJohn Snow 660be58721dSJohn Snow if (hbitmap_count(b) == 0) { 661be58721dSJohn Snow return true; 662be58721dSJohn Snow } 663be58721dSJohn Snow 664be58721dSJohn Snow /* This merge is O(size), as BITS_PER_LONG and HBITMAP_LEVELS are constant. 665be58721dSJohn Snow * It may be possible to improve running times for sparsely populated maps 666be58721dSJohn Snow * by using hbitmap_iter_next, but this is suboptimal for dense maps. 667be58721dSJohn Snow */ 668be58721dSJohn Snow for (i = HBITMAP_LEVELS - 1; i >= 0; i--) { 669be58721dSJohn Snow for (j = 0; j < a->sizes[i]; j++) { 670be58721dSJohn Snow a->levels[i][j] |= b->levels[i][j]; 671be58721dSJohn Snow } 672be58721dSJohn Snow } 673be58721dSJohn Snow 674be58721dSJohn Snow return true; 675be58721dSJohn Snow } 67607ac4cdbSFam Zheng 67707ac4cdbSFam Zheng HBitmap *hbitmap_create_meta(HBitmap *hb, int chunk_size) 67807ac4cdbSFam Zheng { 67907ac4cdbSFam Zheng assert(!(chunk_size & (chunk_size - 1))); 68007ac4cdbSFam Zheng assert(!hb->meta); 68107ac4cdbSFam Zheng hb->meta = hbitmap_alloc(hb->size << hb->granularity, 68207ac4cdbSFam Zheng hb->granularity + ctz32(chunk_size)); 68307ac4cdbSFam Zheng return hb->meta; 68407ac4cdbSFam Zheng } 68507ac4cdbSFam Zheng 68607ac4cdbSFam Zheng void hbitmap_free_meta(HBitmap *hb) 68707ac4cdbSFam Zheng { 68807ac4cdbSFam Zheng assert(hb->meta); 68907ac4cdbSFam Zheng hbitmap_free(hb->meta); 69007ac4cdbSFam Zheng hb->meta = NULL; 69107ac4cdbSFam Zheng } 692