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" 16a3b52535SVladimir Sementsov-Ogievskiy #include "crypto/hash.h" 17e7c033c3SPaolo Bonzini 18e7c033c3SPaolo Bonzini /* HBitmaps provides an array of bits. The bits are stored as usual in an 19e7c033c3SPaolo Bonzini * array of unsigned longs, but HBitmap is also optimized to provide fast 20e7c033c3SPaolo Bonzini * iteration over set bits; going from one bit to the next is O(logB n) 21e7c033c3SPaolo Bonzini * worst case, with B = sizeof(long) * CHAR_BIT: the result is low enough 22e7c033c3SPaolo Bonzini * that the number of levels is in fact fixed. 23e7c033c3SPaolo Bonzini * 24e7c033c3SPaolo Bonzini * In order to do this, it stacks multiple bitmaps with progressively coarser 25e7c033c3SPaolo Bonzini * granularity; in all levels except the last, bit N is set iff the N-th 26e7c033c3SPaolo Bonzini * unsigned long is nonzero in the immediately next level. When iteration 27e7c033c3SPaolo Bonzini * completes on the last level it can examine the 2nd-last level to quickly 28e7c033c3SPaolo Bonzini * skip entire words, and even do so recursively to skip blocks of 64 words or 29e7c033c3SPaolo Bonzini * powers thereof (32 on 32-bit machines). 30e7c033c3SPaolo Bonzini * 31e7c033c3SPaolo Bonzini * Given an index in the bitmap, it can be split in group of bits like 32e7c033c3SPaolo Bonzini * this (for the 64-bit case): 33e7c033c3SPaolo Bonzini * 34e7c033c3SPaolo Bonzini * bits 0-57 => word in the last bitmap | bits 58-63 => bit in the word 35e7c033c3SPaolo Bonzini * bits 0-51 => word in the 2nd-last bitmap | bits 52-57 => bit in the word 36e7c033c3SPaolo Bonzini * bits 0-45 => word in the 3rd-last bitmap | bits 46-51 => bit in the word 37e7c033c3SPaolo Bonzini * 38e7c033c3SPaolo Bonzini * So it is easy to move up simply by shifting the index right by 39e7c033c3SPaolo Bonzini * log2(BITS_PER_LONG) bits. To move down, you shift the index left 40e7c033c3SPaolo Bonzini * similarly, and add the word index within the group. Iteration uses 41e7c033c3SPaolo Bonzini * ffs (find first set bit) to find the next word to examine; this 42e7c033c3SPaolo Bonzini * operation can be done in constant time in most current architectures. 43e7c033c3SPaolo Bonzini * 44e7c033c3SPaolo Bonzini * Setting or clearing a range of m bits on all levels, the work to perform 45e7c033c3SPaolo Bonzini * is O(m + m/W + m/W^2 + ...), which is O(m) like on a regular bitmap. 46e7c033c3SPaolo Bonzini * 47e7c033c3SPaolo Bonzini * When iterating on a bitmap, each bit (on any level) is only visited 48e7c033c3SPaolo Bonzini * once. Hence, The total cost of visiting a bitmap with m bits in it is 49e7c033c3SPaolo Bonzini * the number of bits that are set in all bitmaps. Unless the bitmap is 50e7c033c3SPaolo Bonzini * extremely sparse, this is also O(m + m/W + m/W^2 + ...), so the amortized 51e7c033c3SPaolo Bonzini * cost of advancing from one bit to the next is usually constant (worst case 52e7c033c3SPaolo Bonzini * O(logB n) as in the non-amortized complexity). 53e7c033c3SPaolo Bonzini */ 54e7c033c3SPaolo Bonzini 55e7c033c3SPaolo Bonzini struct HBitmap { 564e4de222SVladimir Sementsov-Ogievskiy /* 574e4de222SVladimir Sementsov-Ogievskiy * Size of the bitmap, as requested in hbitmap_alloc or in hbitmap_truncate. 584e4de222SVladimir Sementsov-Ogievskiy */ 5976d570dcSVladimir Sementsov-Ogievskiy uint64_t orig_size; 6076d570dcSVladimir Sementsov-Ogievskiy 61e7c033c3SPaolo Bonzini /* Number of total bits in the bottom level. */ 62e7c033c3SPaolo Bonzini uint64_t size; 63e7c033c3SPaolo Bonzini 64e7c033c3SPaolo Bonzini /* Number of set bits in the bottom level. */ 65e7c033c3SPaolo Bonzini uint64_t count; 66e7c033c3SPaolo Bonzini 67e7c033c3SPaolo Bonzini /* A scaling factor. Given a granularity of G, each bit in the bitmap will 68e7c033c3SPaolo Bonzini * will actually represent a group of 2^G elements. Each operation on a 69e7c033c3SPaolo Bonzini * range of bits first rounds the bits to determine which group they land 70e7c033c3SPaolo Bonzini * in, and then affect the entire page; iteration will only visit the first 71e7c033c3SPaolo Bonzini * bit of each group. Here is an example of operations in a size-16, 72e7c033c3SPaolo Bonzini * granularity-1 HBitmap: 73e7c033c3SPaolo Bonzini * 74e7c033c3SPaolo Bonzini * initial state 00000000 75e7c033c3SPaolo Bonzini * set(start=0, count=9) 11111000 (iter: 0, 2, 4, 6, 8) 76e7c033c3SPaolo Bonzini * reset(start=1, count=3) 00111000 (iter: 4, 6, 8) 77e7c033c3SPaolo Bonzini * set(start=9, count=2) 00111100 (iter: 4, 6, 8, 10) 78e7c033c3SPaolo Bonzini * reset(start=5, count=5) 00000000 79e7c033c3SPaolo Bonzini * 80e7c033c3SPaolo Bonzini * From an implementation point of view, when setting or resetting bits, 81e7c033c3SPaolo Bonzini * the bitmap will scale bit numbers right by this amount of bits. When 82e7c033c3SPaolo Bonzini * iterating, the bitmap will scale bit numbers left by this amount of 83e7c033c3SPaolo Bonzini * bits. 84e7c033c3SPaolo Bonzini */ 85e7c033c3SPaolo Bonzini int granularity; 86e7c033c3SPaolo Bonzini 8707ac4cdbSFam Zheng /* A meta dirty bitmap to track the dirtiness of bits in this HBitmap. */ 8807ac4cdbSFam Zheng HBitmap *meta; 8907ac4cdbSFam Zheng 90e7c033c3SPaolo Bonzini /* A number of progressively less coarse bitmaps (i.e. level 0 is the 91e7c033c3SPaolo Bonzini * coarsest). Each bit in level N represents a word in level N+1 that 92e7c033c3SPaolo Bonzini * has a set bit, except the last level where each bit represents the 93e7c033c3SPaolo Bonzini * actual bitmap. 94e7c033c3SPaolo Bonzini * 95e7c033c3SPaolo Bonzini * Note that all bitmaps have the same number of levels. Even a 1-bit 96e7c033c3SPaolo Bonzini * bitmap will still allocate HBITMAP_LEVELS arrays. 97e7c033c3SPaolo Bonzini */ 98e7c033c3SPaolo Bonzini unsigned long *levels[HBITMAP_LEVELS]; 998515efbeSJohn Snow 1008515efbeSJohn Snow /* The length of each levels[] array. */ 1018515efbeSJohn Snow uint64_t sizes[HBITMAP_LEVELS]; 102e7c033c3SPaolo Bonzini }; 103e7c033c3SPaolo Bonzini 104e7c033c3SPaolo Bonzini /* Advance hbi to the next nonzero word and return it. hbi->pos 105e7c033c3SPaolo Bonzini * is updated. Returns zero if we reach the end of the bitmap. 106e7c033c3SPaolo Bonzini */ 10730b8346cSVladimir Sementsov-Ogievskiy static unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi) 108e7c033c3SPaolo Bonzini { 109e7c033c3SPaolo Bonzini size_t pos = hbi->pos; 110e7c033c3SPaolo Bonzini const HBitmap *hb = hbi->hb; 111e7c033c3SPaolo Bonzini unsigned i = HBITMAP_LEVELS - 1; 112e7c033c3SPaolo Bonzini 113e7c033c3SPaolo Bonzini unsigned long cur; 114e7c033c3SPaolo Bonzini do { 115f63ea4e9SVladimir Sementsov-Ogievskiy i--; 116e7c033c3SPaolo Bonzini pos >>= BITS_PER_LEVEL; 117f63ea4e9SVladimir Sementsov-Ogievskiy cur = hbi->cur[i] & hb->levels[i][pos]; 118e7c033c3SPaolo Bonzini } while (cur == 0); 119e7c033c3SPaolo Bonzini 120e7c033c3SPaolo Bonzini /* Check for end of iteration. We always use fewer than BITS_PER_LONG 121e7c033c3SPaolo Bonzini * bits in the level 0 bitmap; thus we can repurpose the most significant 122e7c033c3SPaolo Bonzini * bit as a sentinel. The sentinel is set in hbitmap_alloc and ensures 123e7c033c3SPaolo Bonzini * that the above loop ends even without an explicit check on i. 124e7c033c3SPaolo Bonzini */ 125e7c033c3SPaolo Bonzini 126e7c033c3SPaolo Bonzini if (i == 0 && cur == (1UL << (BITS_PER_LONG - 1))) { 127e7c033c3SPaolo Bonzini return 0; 128e7c033c3SPaolo Bonzini } 129e7c033c3SPaolo Bonzini for (; i < HBITMAP_LEVELS - 1; i++) { 130e7c033c3SPaolo Bonzini /* Shift back pos to the left, matching the right shifts above. 131e7c033c3SPaolo Bonzini * The index of this word's least significant set bit provides 132e7c033c3SPaolo Bonzini * the low-order bits. 133e7c033c3SPaolo Bonzini */ 13418331e7cSRichard Henderson assert(cur); 13518331e7cSRichard Henderson pos = (pos << BITS_PER_LEVEL) + ctzl(cur); 136e7c033c3SPaolo Bonzini hbi->cur[i] = cur & (cur - 1); 137e7c033c3SPaolo Bonzini 138e7c033c3SPaolo Bonzini /* Set up next level for iteration. */ 139e7c033c3SPaolo Bonzini cur = hb->levels[i + 1][pos]; 140e7c033c3SPaolo Bonzini } 141e7c033c3SPaolo Bonzini 142e7c033c3SPaolo Bonzini hbi->pos = pos; 143e7c033c3SPaolo Bonzini trace_hbitmap_iter_skip_words(hbi->hb, hbi, pos, cur); 144e7c033c3SPaolo Bonzini 145e7c033c3SPaolo Bonzini assert(cur); 146e7c033c3SPaolo Bonzini return cur; 147e7c033c3SPaolo Bonzini } 148e7c033c3SPaolo Bonzini 14919c021e1SVladimir Sementsov-Ogievskiy int64_t hbitmap_iter_next(HBitmapIter *hbi) 150f63ea4e9SVladimir Sementsov-Ogievskiy { 151f63ea4e9SVladimir Sementsov-Ogievskiy unsigned long cur = hbi->cur[HBITMAP_LEVELS - 1] & 152f63ea4e9SVladimir Sementsov-Ogievskiy hbi->hb->levels[HBITMAP_LEVELS - 1][hbi->pos]; 153f63ea4e9SVladimir Sementsov-Ogievskiy int64_t item; 154f63ea4e9SVladimir Sementsov-Ogievskiy 155f63ea4e9SVladimir Sementsov-Ogievskiy if (cur == 0) { 156f63ea4e9SVladimir Sementsov-Ogievskiy cur = hbitmap_iter_skip_words(hbi); 157f63ea4e9SVladimir Sementsov-Ogievskiy if (cur == 0) { 158f63ea4e9SVladimir Sementsov-Ogievskiy return -1; 159f63ea4e9SVladimir Sementsov-Ogievskiy } 160f63ea4e9SVladimir Sementsov-Ogievskiy } 161f63ea4e9SVladimir Sementsov-Ogievskiy 162f63ea4e9SVladimir Sementsov-Ogievskiy /* The next call will resume work from the next bit. */ 163f63ea4e9SVladimir Sementsov-Ogievskiy hbi->cur[HBITMAP_LEVELS - 1] = cur & (cur - 1); 164f63ea4e9SVladimir Sementsov-Ogievskiy item = ((uint64_t)hbi->pos << BITS_PER_LEVEL) + ctzl(cur); 165f63ea4e9SVladimir Sementsov-Ogievskiy 166f63ea4e9SVladimir Sementsov-Ogievskiy return item << hbi->granularity; 167f63ea4e9SVladimir Sementsov-Ogievskiy } 168f63ea4e9SVladimir Sementsov-Ogievskiy 169e7c033c3SPaolo Bonzini void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first) 170e7c033c3SPaolo Bonzini { 171e7c033c3SPaolo Bonzini unsigned i, bit; 172e7c033c3SPaolo Bonzini uint64_t pos; 173e7c033c3SPaolo Bonzini 174e7c033c3SPaolo Bonzini hbi->hb = hb; 175e7c033c3SPaolo Bonzini pos = first >> hb->granularity; 1761b095244SPaolo Bonzini assert(pos < hb->size); 177e7c033c3SPaolo Bonzini hbi->pos = pos >> BITS_PER_LEVEL; 178e7c033c3SPaolo Bonzini hbi->granularity = hb->granularity; 179e7c033c3SPaolo Bonzini 180e7c033c3SPaolo Bonzini for (i = HBITMAP_LEVELS; i-- > 0; ) { 181e7c033c3SPaolo Bonzini bit = pos & (BITS_PER_LONG - 1); 182e7c033c3SPaolo Bonzini pos >>= BITS_PER_LEVEL; 183e7c033c3SPaolo Bonzini 184e7c033c3SPaolo Bonzini /* Drop bits representing items before first. */ 185e7c033c3SPaolo Bonzini hbi->cur[i] = hb->levels[i][pos] & ~((1UL << bit) - 1); 186e7c033c3SPaolo Bonzini 187e7c033c3SPaolo Bonzini /* We have already added level i+1, so the lowest set bit has 188e7c033c3SPaolo Bonzini * been processed. Clear it. 189e7c033c3SPaolo Bonzini */ 190e7c033c3SPaolo Bonzini if (i != HBITMAP_LEVELS - 1) { 191e7c033c3SPaolo Bonzini hbi->cur[i] &= ~(1UL << bit); 192e7c033c3SPaolo Bonzini } 193e7c033c3SPaolo Bonzini } 194e7c033c3SPaolo Bonzini } 195e7c033c3SPaolo Bonzini 1969399c54bSVladimir Sementsov-Ogievskiy int64_t hbitmap_next_dirty(const HBitmap *hb, int64_t start, int64_t count) 1979399c54bSVladimir Sementsov-Ogievskiy { 1989399c54bSVladimir Sementsov-Ogievskiy HBitmapIter hbi; 1999399c54bSVladimir Sementsov-Ogievskiy int64_t first_dirty_off; 2009399c54bSVladimir Sementsov-Ogievskiy uint64_t end; 2019399c54bSVladimir Sementsov-Ogievskiy 2029399c54bSVladimir Sementsov-Ogievskiy assert(start >= 0 && count >= 0); 2039399c54bSVladimir Sementsov-Ogievskiy 2049399c54bSVladimir Sementsov-Ogievskiy if (start >= hb->orig_size || count == 0) { 2059399c54bSVladimir Sementsov-Ogievskiy return -1; 2069399c54bSVladimir Sementsov-Ogievskiy } 2079399c54bSVladimir Sementsov-Ogievskiy 2089399c54bSVladimir Sementsov-Ogievskiy end = count > hb->orig_size - start ? hb->orig_size : start + count; 2099399c54bSVladimir Sementsov-Ogievskiy 2109399c54bSVladimir Sementsov-Ogievskiy hbitmap_iter_init(&hbi, hb, start); 2119399c54bSVladimir Sementsov-Ogievskiy first_dirty_off = hbitmap_iter_next(&hbi); 2129399c54bSVladimir Sementsov-Ogievskiy 2139399c54bSVladimir Sementsov-Ogievskiy if (first_dirty_off < 0 || first_dirty_off >= end) { 2149399c54bSVladimir Sementsov-Ogievskiy return -1; 2159399c54bSVladimir Sementsov-Ogievskiy } 2169399c54bSVladimir Sementsov-Ogievskiy 2179399c54bSVladimir Sementsov-Ogievskiy return MAX(start, first_dirty_off); 2189399c54bSVladimir Sementsov-Ogievskiy } 2199399c54bSVladimir Sementsov-Ogievskiy 220642700fdSVladimir Sementsov-Ogievskiy int64_t hbitmap_next_zero(const HBitmap *hb, int64_t start, int64_t count) 22156207df5SVladimir Sementsov-Ogievskiy { 22256207df5SVladimir Sementsov-Ogievskiy size_t pos = (start >> hb->granularity) >> BITS_PER_LEVEL; 22356207df5SVladimir Sementsov-Ogievskiy unsigned long *last_lev = hb->levels[HBITMAP_LEVELS - 1]; 22456207df5SVladimir Sementsov-Ogievskiy unsigned long cur = last_lev[pos]; 22576d570dcSVladimir Sementsov-Ogievskiy unsigned start_bit_offset; 22676d570dcSVladimir Sementsov-Ogievskiy uint64_t end_bit, sz; 22756207df5SVladimir Sementsov-Ogievskiy int64_t res; 22856207df5SVladimir Sementsov-Ogievskiy 229642700fdSVladimir Sementsov-Ogievskiy assert(start >= 0 && count >= 0); 230642700fdSVladimir Sementsov-Ogievskiy 23176d570dcSVladimir Sementsov-Ogievskiy if (start >= hb->orig_size || count == 0) { 23276d570dcSVladimir Sementsov-Ogievskiy return -1; 23376d570dcSVladimir Sementsov-Ogievskiy } 23476d570dcSVladimir Sementsov-Ogievskiy 23576d570dcSVladimir Sementsov-Ogievskiy end_bit = count > hb->orig_size - start ? 23676d570dcSVladimir Sementsov-Ogievskiy hb->size : 23776d570dcSVladimir Sementsov-Ogievskiy ((start + count - 1) >> hb->granularity) + 1; 23876d570dcSVladimir Sementsov-Ogievskiy sz = (end_bit + BITS_PER_LONG - 1) >> BITS_PER_LEVEL; 23976d570dcSVladimir Sementsov-Ogievskiy 24076d570dcSVladimir Sementsov-Ogievskiy /* There may be some zero bits in @cur before @start. We are not interested 24176d570dcSVladimir Sementsov-Ogievskiy * in them, let's set them. 24276d570dcSVladimir Sementsov-Ogievskiy */ 24376d570dcSVladimir Sementsov-Ogievskiy start_bit_offset = (start >> hb->granularity) & (BITS_PER_LONG - 1); 24456207df5SVladimir Sementsov-Ogievskiy cur |= (1UL << start_bit_offset) - 1; 24556207df5SVladimir Sementsov-Ogievskiy assert((start >> hb->granularity) < hb->size); 24656207df5SVladimir Sementsov-Ogievskiy 24756207df5SVladimir Sementsov-Ogievskiy if (cur == (unsigned long)-1) { 24856207df5SVladimir Sementsov-Ogievskiy do { 24956207df5SVladimir Sementsov-Ogievskiy pos++; 25056207df5SVladimir Sementsov-Ogievskiy } while (pos < sz && last_lev[pos] == (unsigned long)-1); 25156207df5SVladimir Sementsov-Ogievskiy 25256207df5SVladimir Sementsov-Ogievskiy if (pos >= sz) { 25356207df5SVladimir Sementsov-Ogievskiy return -1; 25456207df5SVladimir Sementsov-Ogievskiy } 25556207df5SVladimir Sementsov-Ogievskiy 25656207df5SVladimir Sementsov-Ogievskiy cur = last_lev[pos]; 25756207df5SVladimir Sementsov-Ogievskiy } 25856207df5SVladimir Sementsov-Ogievskiy 25956207df5SVladimir Sementsov-Ogievskiy res = (pos << BITS_PER_LEVEL) + ctol(cur); 26076d570dcSVladimir Sementsov-Ogievskiy if (res >= end_bit) { 26156207df5SVladimir Sementsov-Ogievskiy return -1; 26256207df5SVladimir Sementsov-Ogievskiy } 26356207df5SVladimir Sementsov-Ogievskiy 26456207df5SVladimir Sementsov-Ogievskiy res = res << hb->granularity; 26556207df5SVladimir Sementsov-Ogievskiy if (res < start) { 26656207df5SVladimir Sementsov-Ogievskiy assert(((start - res) >> hb->granularity) == 0); 26756207df5SVladimir Sementsov-Ogievskiy return start; 26856207df5SVladimir Sementsov-Ogievskiy } 26956207df5SVladimir Sementsov-Ogievskiy 27056207df5SVladimir Sementsov-Ogievskiy return res; 27156207df5SVladimir Sementsov-Ogievskiy } 27256207df5SVladimir Sementsov-Ogievskiy 273299ea9ffSVladimir Sementsov-Ogievskiy bool hbitmap_next_dirty_area(const HBitmap *hb, int64_t start, int64_t end, 274299ea9ffSVladimir Sementsov-Ogievskiy int64_t max_dirty_count, 275299ea9ffSVladimir Sementsov-Ogievskiy int64_t *dirty_start, int64_t *dirty_count) 276a78a1a48SVladimir Sementsov-Ogievskiy { 277299ea9ffSVladimir Sementsov-Ogievskiy int64_t next_zero; 278a78a1a48SVladimir Sementsov-Ogievskiy 279299ea9ffSVladimir Sementsov-Ogievskiy assert(start >= 0 && end >= 0 && max_dirty_count > 0); 280299ea9ffSVladimir Sementsov-Ogievskiy 281299ea9ffSVladimir Sementsov-Ogievskiy end = MIN(end, hb->orig_size); 282299ea9ffSVladimir Sementsov-Ogievskiy if (start >= end) { 283a78a1a48SVladimir Sementsov-Ogievskiy return false; 284a78a1a48SVladimir Sementsov-Ogievskiy } 285a78a1a48SVladimir Sementsov-Ogievskiy 286299ea9ffSVladimir Sementsov-Ogievskiy start = hbitmap_next_dirty(hb, start, end - start); 287299ea9ffSVladimir Sementsov-Ogievskiy if (start < 0) { 288299ea9ffSVladimir Sementsov-Ogievskiy return false; 289a78a1a48SVladimir Sementsov-Ogievskiy } 290a78a1a48SVladimir Sementsov-Ogievskiy 291299ea9ffSVladimir Sementsov-Ogievskiy end = start + MIN(end - start, max_dirty_count); 292299ea9ffSVladimir Sementsov-Ogievskiy 293299ea9ffSVladimir Sementsov-Ogievskiy next_zero = hbitmap_next_zero(hb, start, end - start); 294299ea9ffSVladimir Sementsov-Ogievskiy if (next_zero >= 0) { 295299ea9ffSVladimir Sementsov-Ogievskiy end = next_zero; 296299ea9ffSVladimir Sementsov-Ogievskiy } 297299ea9ffSVladimir Sementsov-Ogievskiy 298299ea9ffSVladimir Sementsov-Ogievskiy *dirty_start = start; 299299ea9ffSVladimir Sementsov-Ogievskiy *dirty_count = end - start; 300a78a1a48SVladimir Sementsov-Ogievskiy 301a78a1a48SVladimir Sementsov-Ogievskiy return true; 302a78a1a48SVladimir Sementsov-Ogievskiy } 303a78a1a48SVladimir Sementsov-Ogievskiy 304*a6426475SVladimir Sementsov-Ogievskiy bool hbitmap_status(const HBitmap *hb, int64_t start, int64_t count, 305*a6426475SVladimir Sementsov-Ogievskiy int64_t *pnum) 306*a6426475SVladimir Sementsov-Ogievskiy { 307*a6426475SVladimir Sementsov-Ogievskiy int64_t next_dirty, next_zero; 308*a6426475SVladimir Sementsov-Ogievskiy 309*a6426475SVladimir Sementsov-Ogievskiy assert(start >= 0); 310*a6426475SVladimir Sementsov-Ogievskiy assert(count > 0); 311*a6426475SVladimir Sementsov-Ogievskiy assert(start + count <= hb->orig_size); 312*a6426475SVladimir Sementsov-Ogievskiy 313*a6426475SVladimir Sementsov-Ogievskiy next_dirty = hbitmap_next_dirty(hb, start, count); 314*a6426475SVladimir Sementsov-Ogievskiy if (next_dirty == -1) { 315*a6426475SVladimir Sementsov-Ogievskiy *pnum = count; 316*a6426475SVladimir Sementsov-Ogievskiy return false; 317*a6426475SVladimir Sementsov-Ogievskiy } 318*a6426475SVladimir Sementsov-Ogievskiy 319*a6426475SVladimir Sementsov-Ogievskiy if (next_dirty > start) { 320*a6426475SVladimir Sementsov-Ogievskiy *pnum = next_dirty - start; 321*a6426475SVladimir Sementsov-Ogievskiy return false; 322*a6426475SVladimir Sementsov-Ogievskiy } 323*a6426475SVladimir Sementsov-Ogievskiy 324*a6426475SVladimir Sementsov-Ogievskiy assert(next_dirty == start); 325*a6426475SVladimir Sementsov-Ogievskiy 326*a6426475SVladimir Sementsov-Ogievskiy next_zero = hbitmap_next_zero(hb, start, count); 327*a6426475SVladimir Sementsov-Ogievskiy if (next_zero == -1) { 328*a6426475SVladimir Sementsov-Ogievskiy *pnum = count; 329*a6426475SVladimir Sementsov-Ogievskiy return true; 330*a6426475SVladimir Sementsov-Ogievskiy } 331*a6426475SVladimir Sementsov-Ogievskiy 332*a6426475SVladimir Sementsov-Ogievskiy assert(next_zero > start); 333*a6426475SVladimir Sementsov-Ogievskiy *pnum = next_zero - start; 334*a6426475SVladimir Sementsov-Ogievskiy return false; 335*a6426475SVladimir Sementsov-Ogievskiy } 336*a6426475SVladimir Sementsov-Ogievskiy 337e7c033c3SPaolo Bonzini bool hbitmap_empty(const HBitmap *hb) 338e7c033c3SPaolo Bonzini { 339e7c033c3SPaolo Bonzini return hb->count == 0; 340e7c033c3SPaolo Bonzini } 341e7c033c3SPaolo Bonzini 342e7c033c3SPaolo Bonzini int hbitmap_granularity(const HBitmap *hb) 343e7c033c3SPaolo Bonzini { 344e7c033c3SPaolo Bonzini return hb->granularity; 345e7c033c3SPaolo Bonzini } 346e7c033c3SPaolo Bonzini 347e7c033c3SPaolo Bonzini uint64_t hbitmap_count(const HBitmap *hb) 348e7c033c3SPaolo Bonzini { 349e7c033c3SPaolo Bonzini return hb->count << hb->granularity; 350e7c033c3SPaolo Bonzini } 351e7c033c3SPaolo Bonzini 352be24c714SVladimir Sementsov-Ogievskiy /** 353be24c714SVladimir Sementsov-Ogievskiy * hbitmap_iter_next_word: 354be24c714SVladimir Sementsov-Ogievskiy * @hbi: HBitmapIter to operate on. 355be24c714SVladimir Sementsov-Ogievskiy * @p_cur: Location where to store the next non-zero word. 356be24c714SVladimir Sementsov-Ogievskiy * 357be24c714SVladimir Sementsov-Ogievskiy * Return the index of the next nonzero word that is set in @hbi's 358be24c714SVladimir Sementsov-Ogievskiy * associated HBitmap, and set *p_cur to the content of that word 359be24c714SVladimir Sementsov-Ogievskiy * (bits before the index that was passed to hbitmap_iter_init are 360be24c714SVladimir Sementsov-Ogievskiy * trimmed on the first call). Return -1, and set *p_cur to zero, 361be24c714SVladimir Sementsov-Ogievskiy * if all remaining words are zero. 362be24c714SVladimir Sementsov-Ogievskiy */ 363be24c714SVladimir Sementsov-Ogievskiy static size_t hbitmap_iter_next_word(HBitmapIter *hbi, unsigned long *p_cur) 364be24c714SVladimir Sementsov-Ogievskiy { 365be24c714SVladimir Sementsov-Ogievskiy unsigned long cur = hbi->cur[HBITMAP_LEVELS - 1]; 366be24c714SVladimir Sementsov-Ogievskiy 367be24c714SVladimir Sementsov-Ogievskiy if (cur == 0) { 368be24c714SVladimir Sementsov-Ogievskiy cur = hbitmap_iter_skip_words(hbi); 369be24c714SVladimir Sementsov-Ogievskiy if (cur == 0) { 370be24c714SVladimir Sementsov-Ogievskiy *p_cur = 0; 371be24c714SVladimir Sementsov-Ogievskiy return -1; 372be24c714SVladimir Sementsov-Ogievskiy } 373be24c714SVladimir Sementsov-Ogievskiy } 374be24c714SVladimir Sementsov-Ogievskiy 375be24c714SVladimir Sementsov-Ogievskiy /* The next call will resume work from the next word. */ 376be24c714SVladimir Sementsov-Ogievskiy hbi->cur[HBITMAP_LEVELS - 1] = 0; 377be24c714SVladimir Sementsov-Ogievskiy *p_cur = cur; 378be24c714SVladimir Sementsov-Ogievskiy return hbi->pos; 379be24c714SVladimir Sementsov-Ogievskiy } 380be24c714SVladimir Sementsov-Ogievskiy 381e7c033c3SPaolo Bonzini /* Count the number of set bits between start and end, not accounting for 382e7c033c3SPaolo Bonzini * the granularity. Also an example of how to use hbitmap_iter_next_word. 383e7c033c3SPaolo Bonzini */ 384e7c033c3SPaolo Bonzini static uint64_t hb_count_between(HBitmap *hb, uint64_t start, uint64_t last) 385e7c033c3SPaolo Bonzini { 386e7c033c3SPaolo Bonzini HBitmapIter hbi; 387e7c033c3SPaolo Bonzini uint64_t count = 0; 388e7c033c3SPaolo Bonzini uint64_t end = last + 1; 389e7c033c3SPaolo Bonzini unsigned long cur; 390e7c033c3SPaolo Bonzini size_t pos; 391e7c033c3SPaolo Bonzini 392e7c033c3SPaolo Bonzini hbitmap_iter_init(&hbi, hb, start << hb->granularity); 393e7c033c3SPaolo Bonzini for (;;) { 394e7c033c3SPaolo Bonzini pos = hbitmap_iter_next_word(&hbi, &cur); 395e7c033c3SPaolo Bonzini if (pos >= (end >> BITS_PER_LEVEL)) { 396e7c033c3SPaolo Bonzini break; 397e7c033c3SPaolo Bonzini } 398591b320aSPeter Maydell count += ctpopl(cur); 399e7c033c3SPaolo Bonzini } 400e7c033c3SPaolo Bonzini 401e7c033c3SPaolo Bonzini if (pos == (end >> BITS_PER_LEVEL)) { 402e7c033c3SPaolo Bonzini /* Drop bits representing the END-th and subsequent items. */ 403e7c033c3SPaolo Bonzini int bit = end & (BITS_PER_LONG - 1); 404e7c033c3SPaolo Bonzini cur &= (1UL << bit) - 1; 405591b320aSPeter Maydell count += ctpopl(cur); 406e7c033c3SPaolo Bonzini } 407e7c033c3SPaolo Bonzini 408e7c033c3SPaolo Bonzini return count; 409e7c033c3SPaolo Bonzini } 410e7c033c3SPaolo Bonzini 411e7c033c3SPaolo Bonzini /* Setting starts at the last layer and propagates up if an element 41207ac4cdbSFam Zheng * changes. 413e7c033c3SPaolo Bonzini */ 414e7c033c3SPaolo Bonzini static inline bool hb_set_elem(unsigned long *elem, uint64_t start, uint64_t last) 415e7c033c3SPaolo Bonzini { 416e7c033c3SPaolo Bonzini unsigned long mask; 41707ac4cdbSFam Zheng unsigned long old; 418e7c033c3SPaolo Bonzini 419e7c033c3SPaolo Bonzini assert((last >> BITS_PER_LEVEL) == (start >> BITS_PER_LEVEL)); 420e7c033c3SPaolo Bonzini assert(start <= last); 421e7c033c3SPaolo Bonzini 422e7c033c3SPaolo Bonzini mask = 2UL << (last & (BITS_PER_LONG - 1)); 423e7c033c3SPaolo Bonzini mask -= 1UL << (start & (BITS_PER_LONG - 1)); 42407ac4cdbSFam Zheng old = *elem; 425e7c033c3SPaolo Bonzini *elem |= mask; 42607ac4cdbSFam Zheng return old != *elem; 427e7c033c3SPaolo Bonzini } 428e7c033c3SPaolo Bonzini 42907ac4cdbSFam Zheng /* The recursive workhorse (the depth is limited to HBITMAP_LEVELS)... 43007ac4cdbSFam Zheng * Returns true if at least one bit is changed. */ 43107ac4cdbSFam Zheng static bool hb_set_between(HBitmap *hb, int level, uint64_t start, 43207ac4cdbSFam Zheng uint64_t last) 433e7c033c3SPaolo Bonzini { 434e7c033c3SPaolo Bonzini size_t pos = start >> BITS_PER_LEVEL; 435e7c033c3SPaolo Bonzini size_t lastpos = last >> BITS_PER_LEVEL; 436e7c033c3SPaolo Bonzini bool changed = false; 437e7c033c3SPaolo Bonzini size_t i; 438e7c033c3SPaolo Bonzini 439e7c033c3SPaolo Bonzini i = pos; 440e7c033c3SPaolo Bonzini if (i < lastpos) { 441e7c033c3SPaolo Bonzini uint64_t next = (start | (BITS_PER_LONG - 1)) + 1; 442e7c033c3SPaolo Bonzini changed |= hb_set_elem(&hb->levels[level][i], start, next - 1); 443e7c033c3SPaolo Bonzini for (;;) { 444e7c033c3SPaolo Bonzini start = next; 445e7c033c3SPaolo Bonzini next += BITS_PER_LONG; 446e7c033c3SPaolo Bonzini if (++i == lastpos) { 447e7c033c3SPaolo Bonzini break; 448e7c033c3SPaolo Bonzini } 449e7c033c3SPaolo Bonzini changed |= (hb->levels[level][i] == 0); 450e7c033c3SPaolo Bonzini hb->levels[level][i] = ~0UL; 451e7c033c3SPaolo Bonzini } 452e7c033c3SPaolo Bonzini } 453e7c033c3SPaolo Bonzini changed |= hb_set_elem(&hb->levels[level][i], start, last); 454e7c033c3SPaolo Bonzini 455e7c033c3SPaolo Bonzini /* If there was any change in this layer, we may have to update 456e7c033c3SPaolo Bonzini * the one above. 457e7c033c3SPaolo Bonzini */ 458e7c033c3SPaolo Bonzini if (level > 0 && changed) { 459e7c033c3SPaolo Bonzini hb_set_between(hb, level - 1, pos, lastpos); 460e7c033c3SPaolo Bonzini } 46107ac4cdbSFam Zheng return changed; 462e7c033c3SPaolo Bonzini } 463e7c033c3SPaolo Bonzini 464e7c033c3SPaolo Bonzini void hbitmap_set(HBitmap *hb, uint64_t start, uint64_t count) 465e7c033c3SPaolo Bonzini { 466e7c033c3SPaolo Bonzini /* Compute range in the last layer. */ 46707ac4cdbSFam Zheng uint64_t first, n; 468e7c033c3SPaolo Bonzini uint64_t last = start + count - 1; 469e7c033c3SPaolo Bonzini 470fed33bd1SVladimir Sementsov-Ogievskiy if (count == 0) { 471fed33bd1SVladimir Sementsov-Ogievskiy return; 472fed33bd1SVladimir Sementsov-Ogievskiy } 473fed33bd1SVladimir Sementsov-Ogievskiy 474e7c033c3SPaolo Bonzini trace_hbitmap_set(hb, start, count, 475e7c033c3SPaolo Bonzini start >> hb->granularity, last >> hb->granularity); 476e7c033c3SPaolo Bonzini 47707ac4cdbSFam Zheng first = start >> hb->granularity; 478e7c033c3SPaolo Bonzini last >>= hb->granularity; 4790e321191SVladimir Sementsov-Ogievskiy assert(last < hb->size); 48007ac4cdbSFam Zheng n = last - first + 1; 481e7c033c3SPaolo Bonzini 48207ac4cdbSFam Zheng hb->count += n - hb_count_between(hb, first, last); 48307ac4cdbSFam Zheng if (hb_set_between(hb, HBITMAP_LEVELS - 1, first, last) && 48407ac4cdbSFam Zheng hb->meta) { 48507ac4cdbSFam Zheng hbitmap_set(hb->meta, start, count); 48607ac4cdbSFam Zheng } 487e7c033c3SPaolo Bonzini } 488e7c033c3SPaolo Bonzini 489e7c033c3SPaolo Bonzini /* Resetting works the other way round: propagate up if the new 490e7c033c3SPaolo Bonzini * value is zero. 491e7c033c3SPaolo Bonzini */ 492e7c033c3SPaolo Bonzini static inline bool hb_reset_elem(unsigned long *elem, uint64_t start, uint64_t last) 493e7c033c3SPaolo Bonzini { 494e7c033c3SPaolo Bonzini unsigned long mask; 495e7c033c3SPaolo Bonzini bool blanked; 496e7c033c3SPaolo Bonzini 497e7c033c3SPaolo Bonzini assert((last >> BITS_PER_LEVEL) == (start >> BITS_PER_LEVEL)); 498e7c033c3SPaolo Bonzini assert(start <= last); 499e7c033c3SPaolo Bonzini 500e7c033c3SPaolo Bonzini mask = 2UL << (last & (BITS_PER_LONG - 1)); 501e7c033c3SPaolo Bonzini mask -= 1UL << (start & (BITS_PER_LONG - 1)); 502e7c033c3SPaolo Bonzini blanked = *elem != 0 && ((*elem & ~mask) == 0); 503e7c033c3SPaolo Bonzini *elem &= ~mask; 504e7c033c3SPaolo Bonzini return blanked; 505e7c033c3SPaolo Bonzini } 506e7c033c3SPaolo Bonzini 50707ac4cdbSFam Zheng /* The recursive workhorse (the depth is limited to HBITMAP_LEVELS)... 50807ac4cdbSFam Zheng * Returns true if at least one bit is changed. */ 50907ac4cdbSFam Zheng static bool hb_reset_between(HBitmap *hb, int level, uint64_t start, 51007ac4cdbSFam Zheng uint64_t last) 511e7c033c3SPaolo Bonzini { 512e7c033c3SPaolo Bonzini size_t pos = start >> BITS_PER_LEVEL; 513e7c033c3SPaolo Bonzini size_t lastpos = last >> BITS_PER_LEVEL; 514e7c033c3SPaolo Bonzini bool changed = false; 515e7c033c3SPaolo Bonzini size_t i; 516e7c033c3SPaolo Bonzini 517e7c033c3SPaolo Bonzini i = pos; 518e7c033c3SPaolo Bonzini if (i < lastpos) { 519e7c033c3SPaolo Bonzini uint64_t next = (start | (BITS_PER_LONG - 1)) + 1; 520e7c033c3SPaolo Bonzini 521e7c033c3SPaolo Bonzini /* Here we need a more complex test than when setting bits. Even if 522e7c033c3SPaolo Bonzini * something was changed, we must not blank bits in the upper level 523e7c033c3SPaolo Bonzini * unless the lower-level word became entirely zero. So, remove pos 524e7c033c3SPaolo Bonzini * from the upper-level range if bits remain set. 525e7c033c3SPaolo Bonzini */ 526e7c033c3SPaolo Bonzini if (hb_reset_elem(&hb->levels[level][i], start, next - 1)) { 527e7c033c3SPaolo Bonzini changed = true; 528e7c033c3SPaolo Bonzini } else { 529e7c033c3SPaolo Bonzini pos++; 530e7c033c3SPaolo Bonzini } 531e7c033c3SPaolo Bonzini 532e7c033c3SPaolo Bonzini for (;;) { 533e7c033c3SPaolo Bonzini start = next; 534e7c033c3SPaolo Bonzini next += BITS_PER_LONG; 535e7c033c3SPaolo Bonzini if (++i == lastpos) { 536e7c033c3SPaolo Bonzini break; 537e7c033c3SPaolo Bonzini } 538e7c033c3SPaolo Bonzini changed |= (hb->levels[level][i] != 0); 539e7c033c3SPaolo Bonzini hb->levels[level][i] = 0UL; 540e7c033c3SPaolo Bonzini } 541e7c033c3SPaolo Bonzini } 542e7c033c3SPaolo Bonzini 543e7c033c3SPaolo Bonzini /* Same as above, this time for lastpos. */ 544e7c033c3SPaolo Bonzini if (hb_reset_elem(&hb->levels[level][i], start, last)) { 545e7c033c3SPaolo Bonzini changed = true; 546e7c033c3SPaolo Bonzini } else { 547e7c033c3SPaolo Bonzini lastpos--; 548e7c033c3SPaolo Bonzini } 549e7c033c3SPaolo Bonzini 550e7c033c3SPaolo Bonzini if (level > 0 && changed) { 551e7c033c3SPaolo Bonzini hb_reset_between(hb, level - 1, pos, lastpos); 552e7c033c3SPaolo Bonzini } 55307ac4cdbSFam Zheng 55407ac4cdbSFam Zheng return changed; 55507ac4cdbSFam Zheng 556e7c033c3SPaolo Bonzini } 557e7c033c3SPaolo Bonzini 558e7c033c3SPaolo Bonzini void hbitmap_reset(HBitmap *hb, uint64_t start, uint64_t count) 559e7c033c3SPaolo Bonzini { 560e7c033c3SPaolo Bonzini /* Compute range in the last layer. */ 56107ac4cdbSFam Zheng uint64_t first; 562e7c033c3SPaolo Bonzini uint64_t last = start + count - 1; 56348557b13SVladimir Sementsov-Ogievskiy uint64_t gran = 1ULL << hb->granularity; 56448557b13SVladimir Sementsov-Ogievskiy 565fed33bd1SVladimir Sementsov-Ogievskiy if (count == 0) { 566fed33bd1SVladimir Sementsov-Ogievskiy return; 567fed33bd1SVladimir Sementsov-Ogievskiy } 568fed33bd1SVladimir Sementsov-Ogievskiy 56948557b13SVladimir Sementsov-Ogievskiy assert(QEMU_IS_ALIGNED(start, gran)); 57048557b13SVladimir Sementsov-Ogievskiy assert(QEMU_IS_ALIGNED(count, gran) || (start + count == hb->orig_size)); 571e7c033c3SPaolo Bonzini 572e7c033c3SPaolo Bonzini trace_hbitmap_reset(hb, start, count, 573e7c033c3SPaolo Bonzini start >> hb->granularity, last >> hb->granularity); 574e7c033c3SPaolo Bonzini 57507ac4cdbSFam Zheng first = start >> hb->granularity; 576e7c033c3SPaolo Bonzini last >>= hb->granularity; 5770e321191SVladimir Sementsov-Ogievskiy assert(last < hb->size); 578e7c033c3SPaolo Bonzini 57907ac4cdbSFam Zheng hb->count -= hb_count_between(hb, first, last); 58007ac4cdbSFam Zheng if (hb_reset_between(hb, HBITMAP_LEVELS - 1, first, last) && 58107ac4cdbSFam Zheng hb->meta) { 58207ac4cdbSFam Zheng hbitmap_set(hb->meta, start, count); 58307ac4cdbSFam Zheng } 584e7c033c3SPaolo Bonzini } 585e7c033c3SPaolo Bonzini 586c6a8c328SWen Congyang void hbitmap_reset_all(HBitmap *hb) 587c6a8c328SWen Congyang { 588c6a8c328SWen Congyang unsigned int i; 589c6a8c328SWen Congyang 590c6a8c328SWen Congyang /* Same as hbitmap_alloc() except for memset() instead of malloc() */ 591c6a8c328SWen Congyang for (i = HBITMAP_LEVELS; --i >= 1; ) { 592c6a8c328SWen Congyang memset(hb->levels[i], 0, hb->sizes[i] * sizeof(unsigned long)); 593c6a8c328SWen Congyang } 594c6a8c328SWen Congyang 595c6a8c328SWen Congyang hb->levels[0][0] = 1UL << (BITS_PER_LONG - 1); 596c6a8c328SWen Congyang hb->count = 0; 597c6a8c328SWen Congyang } 598c6a8c328SWen Congyang 59920a579deSMax Reitz bool hbitmap_is_serializable(const HBitmap *hb) 60020a579deSMax Reitz { 60120a579deSMax Reitz /* Every serialized chunk must be aligned to 64 bits so that endianness 60220a579deSMax Reitz * requirements can be fulfilled on both 64 bit and 32 bit hosts. 603ecbfa281SEric Blake * We have hbitmap_serialization_align() which converts this 60420a579deSMax Reitz * alignment requirement from bitmap bits to items covered (e.g. sectors). 60520a579deSMax Reitz * That value is: 60620a579deSMax Reitz * 64 << hb->granularity 60720a579deSMax Reitz * Since this value must not exceed UINT64_MAX, hb->granularity must be 60820a579deSMax Reitz * less than 58 (== 64 - 6, where 6 is ld(64), i.e. 1 << 6 == 64). 60920a579deSMax Reitz * 610ecbfa281SEric Blake * In order for hbitmap_serialization_align() to always return a 61120a579deSMax Reitz * meaningful value, bitmaps that are to be serialized must have a 61220a579deSMax Reitz * granularity of less than 58. */ 61320a579deSMax Reitz 61420a579deSMax Reitz return hb->granularity < 58; 61520a579deSMax Reitz } 61620a579deSMax Reitz 617e7c033c3SPaolo Bonzini bool hbitmap_get(const HBitmap *hb, uint64_t item) 618e7c033c3SPaolo Bonzini { 619e7c033c3SPaolo Bonzini /* Compute position and bit in the last layer. */ 620e7c033c3SPaolo Bonzini uint64_t pos = item >> hb->granularity; 621e7c033c3SPaolo Bonzini unsigned long bit = 1UL << (pos & (BITS_PER_LONG - 1)); 6220e321191SVladimir Sementsov-Ogievskiy assert(pos < hb->size); 623e7c033c3SPaolo Bonzini 624e7c033c3SPaolo Bonzini return (hb->levels[HBITMAP_LEVELS - 1][pos >> BITS_PER_LEVEL] & bit) != 0; 625e7c033c3SPaolo Bonzini } 626e7c033c3SPaolo Bonzini 627ecbfa281SEric Blake uint64_t hbitmap_serialization_align(const HBitmap *hb) 6288258888eSVladimir Sementsov-Ogievskiy { 62920a579deSMax Reitz assert(hbitmap_is_serializable(hb)); 6306725f887SMax Reitz 6318258888eSVladimir Sementsov-Ogievskiy /* Require at least 64 bit granularity to be safe on both 64 bit and 32 bit 6328258888eSVladimir Sementsov-Ogievskiy * hosts. */ 6336725f887SMax Reitz return UINT64_C(64) << hb->granularity; 6348258888eSVladimir Sementsov-Ogievskiy } 6358258888eSVladimir Sementsov-Ogievskiy 6368258888eSVladimir Sementsov-Ogievskiy /* Start should be aligned to serialization granularity, chunk size should be 6378258888eSVladimir Sementsov-Ogievskiy * aligned to serialization granularity too, except for last chunk. 6388258888eSVladimir Sementsov-Ogievskiy */ 6398258888eSVladimir Sementsov-Ogievskiy static void serialization_chunk(const HBitmap *hb, 6408258888eSVladimir Sementsov-Ogievskiy uint64_t start, uint64_t count, 6418258888eSVladimir Sementsov-Ogievskiy unsigned long **first_el, uint64_t *el_count) 6428258888eSVladimir Sementsov-Ogievskiy { 6438258888eSVladimir Sementsov-Ogievskiy uint64_t last = start + count - 1; 644ecbfa281SEric Blake uint64_t gran = hbitmap_serialization_align(hb); 6458258888eSVladimir Sementsov-Ogievskiy 6468258888eSVladimir Sementsov-Ogievskiy assert((start & (gran - 1)) == 0); 6478258888eSVladimir Sementsov-Ogievskiy assert((last >> hb->granularity) < hb->size); 6488258888eSVladimir Sementsov-Ogievskiy if ((last >> hb->granularity) != hb->size - 1) { 6498258888eSVladimir Sementsov-Ogievskiy assert((count & (gran - 1)) == 0); 6508258888eSVladimir Sementsov-Ogievskiy } 6518258888eSVladimir Sementsov-Ogievskiy 6528258888eSVladimir Sementsov-Ogievskiy start = (start >> hb->granularity) >> BITS_PER_LEVEL; 6538258888eSVladimir Sementsov-Ogievskiy last = (last >> hb->granularity) >> BITS_PER_LEVEL; 6548258888eSVladimir Sementsov-Ogievskiy 6558258888eSVladimir Sementsov-Ogievskiy *first_el = &hb->levels[HBITMAP_LEVELS - 1][start]; 6568258888eSVladimir Sementsov-Ogievskiy *el_count = last - start + 1; 6578258888eSVladimir Sementsov-Ogievskiy } 6588258888eSVladimir Sementsov-Ogievskiy 6598258888eSVladimir Sementsov-Ogievskiy uint64_t hbitmap_serialization_size(const HBitmap *hb, 6608258888eSVladimir Sementsov-Ogievskiy uint64_t start, uint64_t count) 6618258888eSVladimir Sementsov-Ogievskiy { 6628258888eSVladimir Sementsov-Ogievskiy uint64_t el_count; 6638258888eSVladimir Sementsov-Ogievskiy unsigned long *cur; 6648258888eSVladimir Sementsov-Ogievskiy 6658258888eSVladimir Sementsov-Ogievskiy if (!count) { 6668258888eSVladimir Sementsov-Ogievskiy return 0; 6678258888eSVladimir Sementsov-Ogievskiy } 6688258888eSVladimir Sementsov-Ogievskiy serialization_chunk(hb, start, count, &cur, &el_count); 6698258888eSVladimir Sementsov-Ogievskiy 6708258888eSVladimir Sementsov-Ogievskiy return el_count * sizeof(unsigned long); 6718258888eSVladimir Sementsov-Ogievskiy } 6728258888eSVladimir Sementsov-Ogievskiy 6738258888eSVladimir Sementsov-Ogievskiy void hbitmap_serialize_part(const HBitmap *hb, uint8_t *buf, 6748258888eSVladimir Sementsov-Ogievskiy uint64_t start, uint64_t count) 6758258888eSVladimir Sementsov-Ogievskiy { 6768258888eSVladimir Sementsov-Ogievskiy uint64_t el_count; 6778258888eSVladimir Sementsov-Ogievskiy unsigned long *cur, *end; 6788258888eSVladimir Sementsov-Ogievskiy 6798258888eSVladimir Sementsov-Ogievskiy if (!count) { 6808258888eSVladimir Sementsov-Ogievskiy return; 6818258888eSVladimir Sementsov-Ogievskiy } 6828258888eSVladimir Sementsov-Ogievskiy serialization_chunk(hb, start, count, &cur, &el_count); 6838258888eSVladimir Sementsov-Ogievskiy end = cur + el_count; 6848258888eSVladimir Sementsov-Ogievskiy 6858258888eSVladimir Sementsov-Ogievskiy while (cur != end) { 6868258888eSVladimir Sementsov-Ogievskiy unsigned long el = 6878258888eSVladimir Sementsov-Ogievskiy (BITS_PER_LONG == 32 ? cpu_to_le32(*cur) : cpu_to_le64(*cur)); 6888258888eSVladimir Sementsov-Ogievskiy 6898258888eSVladimir Sementsov-Ogievskiy memcpy(buf, &el, sizeof(el)); 6908258888eSVladimir Sementsov-Ogievskiy buf += sizeof(el); 6918258888eSVladimir Sementsov-Ogievskiy cur++; 6928258888eSVladimir Sementsov-Ogievskiy } 6938258888eSVladimir Sementsov-Ogievskiy } 6948258888eSVladimir Sementsov-Ogievskiy 6958258888eSVladimir Sementsov-Ogievskiy void hbitmap_deserialize_part(HBitmap *hb, uint8_t *buf, 6968258888eSVladimir Sementsov-Ogievskiy uint64_t start, uint64_t count, 6978258888eSVladimir Sementsov-Ogievskiy bool finish) 6988258888eSVladimir Sementsov-Ogievskiy { 6998258888eSVladimir Sementsov-Ogievskiy uint64_t el_count; 7008258888eSVladimir Sementsov-Ogievskiy unsigned long *cur, *end; 7018258888eSVladimir Sementsov-Ogievskiy 7028258888eSVladimir Sementsov-Ogievskiy if (!count) { 7038258888eSVladimir Sementsov-Ogievskiy return; 7048258888eSVladimir Sementsov-Ogievskiy } 7058258888eSVladimir Sementsov-Ogievskiy serialization_chunk(hb, start, count, &cur, &el_count); 7068258888eSVladimir Sementsov-Ogievskiy end = cur + el_count; 7078258888eSVladimir Sementsov-Ogievskiy 7088258888eSVladimir Sementsov-Ogievskiy while (cur != end) { 7098258888eSVladimir Sementsov-Ogievskiy memcpy(cur, buf, sizeof(*cur)); 7108258888eSVladimir Sementsov-Ogievskiy 7118258888eSVladimir Sementsov-Ogievskiy if (BITS_PER_LONG == 32) { 7128258888eSVladimir Sementsov-Ogievskiy le32_to_cpus((uint32_t *)cur); 7138258888eSVladimir Sementsov-Ogievskiy } else { 7148258888eSVladimir Sementsov-Ogievskiy le64_to_cpus((uint64_t *)cur); 7158258888eSVladimir Sementsov-Ogievskiy } 7168258888eSVladimir Sementsov-Ogievskiy 7178258888eSVladimir Sementsov-Ogievskiy buf += sizeof(unsigned long); 7188258888eSVladimir Sementsov-Ogievskiy cur++; 7198258888eSVladimir Sementsov-Ogievskiy } 7208258888eSVladimir Sementsov-Ogievskiy if (finish) { 7218258888eSVladimir Sementsov-Ogievskiy hbitmap_deserialize_finish(hb); 7228258888eSVladimir Sementsov-Ogievskiy } 7238258888eSVladimir Sementsov-Ogievskiy } 7248258888eSVladimir Sementsov-Ogievskiy 7258258888eSVladimir Sementsov-Ogievskiy void hbitmap_deserialize_zeroes(HBitmap *hb, uint64_t start, uint64_t count, 7268258888eSVladimir Sementsov-Ogievskiy bool finish) 7278258888eSVladimir Sementsov-Ogievskiy { 7288258888eSVladimir Sementsov-Ogievskiy uint64_t el_count; 7298258888eSVladimir Sementsov-Ogievskiy unsigned long *first; 7308258888eSVladimir Sementsov-Ogievskiy 7318258888eSVladimir Sementsov-Ogievskiy if (!count) { 7328258888eSVladimir Sementsov-Ogievskiy return; 7338258888eSVladimir Sementsov-Ogievskiy } 7348258888eSVladimir Sementsov-Ogievskiy serialization_chunk(hb, start, count, &first, &el_count); 7358258888eSVladimir Sementsov-Ogievskiy 7368258888eSVladimir Sementsov-Ogievskiy memset(first, 0, el_count * sizeof(unsigned long)); 7378258888eSVladimir Sementsov-Ogievskiy if (finish) { 7388258888eSVladimir Sementsov-Ogievskiy hbitmap_deserialize_finish(hb); 7398258888eSVladimir Sementsov-Ogievskiy } 7408258888eSVladimir Sementsov-Ogievskiy } 7418258888eSVladimir Sementsov-Ogievskiy 7426bdc8b71SVladimir Sementsov-Ogievskiy void hbitmap_deserialize_ones(HBitmap *hb, uint64_t start, uint64_t count, 7436bdc8b71SVladimir Sementsov-Ogievskiy bool finish) 7446bdc8b71SVladimir Sementsov-Ogievskiy { 7456bdc8b71SVladimir Sementsov-Ogievskiy uint64_t el_count; 7466bdc8b71SVladimir Sementsov-Ogievskiy unsigned long *first; 7476bdc8b71SVladimir Sementsov-Ogievskiy 7486bdc8b71SVladimir Sementsov-Ogievskiy if (!count) { 7496bdc8b71SVladimir Sementsov-Ogievskiy return; 7506bdc8b71SVladimir Sementsov-Ogievskiy } 7516bdc8b71SVladimir Sementsov-Ogievskiy serialization_chunk(hb, start, count, &first, &el_count); 7526bdc8b71SVladimir Sementsov-Ogievskiy 7536bdc8b71SVladimir Sementsov-Ogievskiy memset(first, 0xff, el_count * sizeof(unsigned long)); 7546bdc8b71SVladimir Sementsov-Ogievskiy if (finish) { 7556bdc8b71SVladimir Sementsov-Ogievskiy hbitmap_deserialize_finish(hb); 7566bdc8b71SVladimir Sementsov-Ogievskiy } 7576bdc8b71SVladimir Sementsov-Ogievskiy } 7586bdc8b71SVladimir Sementsov-Ogievskiy 7598258888eSVladimir Sementsov-Ogievskiy void hbitmap_deserialize_finish(HBitmap *bitmap) 7608258888eSVladimir Sementsov-Ogievskiy { 7618258888eSVladimir Sementsov-Ogievskiy int64_t i, size, prev_size; 7628258888eSVladimir Sementsov-Ogievskiy int lev; 7638258888eSVladimir Sementsov-Ogievskiy 7648258888eSVladimir Sementsov-Ogievskiy /* restore levels starting from penultimate to zero level, assuming 7658258888eSVladimir Sementsov-Ogievskiy * that the last level is ok */ 7668258888eSVladimir Sementsov-Ogievskiy size = MAX((bitmap->size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL, 1); 7678258888eSVladimir Sementsov-Ogievskiy for (lev = HBITMAP_LEVELS - 1; lev-- > 0; ) { 7688258888eSVladimir Sementsov-Ogievskiy prev_size = size; 7698258888eSVladimir Sementsov-Ogievskiy size = MAX((size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL, 1); 7708258888eSVladimir Sementsov-Ogievskiy memset(bitmap->levels[lev], 0, size * sizeof(unsigned long)); 7718258888eSVladimir Sementsov-Ogievskiy 7728258888eSVladimir Sementsov-Ogievskiy for (i = 0; i < prev_size; ++i) { 7738258888eSVladimir Sementsov-Ogievskiy if (bitmap->levels[lev + 1][i]) { 7748258888eSVladimir Sementsov-Ogievskiy bitmap->levels[lev][i >> BITS_PER_LEVEL] |= 7758258888eSVladimir Sementsov-Ogievskiy 1UL << (i & (BITS_PER_LONG - 1)); 7768258888eSVladimir Sementsov-Ogievskiy } 7778258888eSVladimir Sementsov-Ogievskiy } 7788258888eSVladimir Sementsov-Ogievskiy } 7798258888eSVladimir Sementsov-Ogievskiy 7808258888eSVladimir Sementsov-Ogievskiy bitmap->levels[0][0] |= 1UL << (BITS_PER_LONG - 1); 7813260cdffSLiang Li bitmap->count = hb_count_between(bitmap, 0, bitmap->size - 1); 7828258888eSVladimir Sementsov-Ogievskiy } 7838258888eSVladimir Sementsov-Ogievskiy 784e7c033c3SPaolo Bonzini void hbitmap_free(HBitmap *hb) 785e7c033c3SPaolo Bonzini { 786e7c033c3SPaolo Bonzini unsigned i; 78707ac4cdbSFam Zheng assert(!hb->meta); 788e7c033c3SPaolo Bonzini for (i = HBITMAP_LEVELS; i-- > 0; ) { 789e7c033c3SPaolo Bonzini g_free(hb->levels[i]); 790e7c033c3SPaolo Bonzini } 791e7c033c3SPaolo Bonzini g_free(hb); 792e7c033c3SPaolo Bonzini } 793e7c033c3SPaolo Bonzini 794e7c033c3SPaolo Bonzini HBitmap *hbitmap_alloc(uint64_t size, int granularity) 795e7c033c3SPaolo Bonzini { 796e1cf5582SMarkus Armbruster HBitmap *hb = g_new0(struct HBitmap, 1); 797e7c033c3SPaolo Bonzini unsigned i; 798e7c033c3SPaolo Bonzini 7996a150995SVladimir Sementsov-Ogievskiy assert(size <= INT64_MAX); 80076d570dcSVladimir Sementsov-Ogievskiy hb->orig_size = size; 80176d570dcSVladimir Sementsov-Ogievskiy 802e7c033c3SPaolo Bonzini assert(granularity >= 0 && granularity < 64); 803e7c033c3SPaolo Bonzini size = (size + (1ULL << granularity) - 1) >> granularity; 804e7c033c3SPaolo Bonzini assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE)); 805e7c033c3SPaolo Bonzini 806e7c033c3SPaolo Bonzini hb->size = size; 807e7c033c3SPaolo Bonzini hb->granularity = granularity; 808e7c033c3SPaolo Bonzini for (i = HBITMAP_LEVELS; i-- > 0; ) { 809e7c033c3SPaolo Bonzini size = MAX((size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL, 1); 8108515efbeSJohn Snow hb->sizes[i] = size; 811e1cf5582SMarkus Armbruster hb->levels[i] = g_new0(unsigned long, size); 812e7c033c3SPaolo Bonzini } 813e7c033c3SPaolo Bonzini 814e7c033c3SPaolo Bonzini /* We necessarily have free bits in level 0 due to the definition 815e7c033c3SPaolo Bonzini * of HBITMAP_LEVELS, so use one for a sentinel. This speeds up 816e7c033c3SPaolo Bonzini * hbitmap_iter_skip_words. 817e7c033c3SPaolo Bonzini */ 818e7c033c3SPaolo Bonzini assert(size == 1); 819e7c033c3SPaolo Bonzini hb->levels[0][0] |= 1UL << (BITS_PER_LONG - 1); 820e7c033c3SPaolo Bonzini return hb; 821e7c033c3SPaolo Bonzini } 822be58721dSJohn Snow 823ce1ffea8SJohn Snow void hbitmap_truncate(HBitmap *hb, uint64_t size) 824ce1ffea8SJohn Snow { 825ce1ffea8SJohn Snow bool shrink; 826ce1ffea8SJohn Snow unsigned i; 827ce1ffea8SJohn Snow uint64_t num_elements = size; 828ce1ffea8SJohn Snow uint64_t old; 829ce1ffea8SJohn Snow 8306a150995SVladimir Sementsov-Ogievskiy assert(size <= INT64_MAX); 8314e4de222SVladimir Sementsov-Ogievskiy hb->orig_size = size; 8324e4de222SVladimir Sementsov-Ogievskiy 833ce1ffea8SJohn Snow /* Size comes in as logical elements, adjust for granularity. */ 834ce1ffea8SJohn Snow size = (size + (1ULL << hb->granularity) - 1) >> hb->granularity; 835ce1ffea8SJohn Snow assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE)); 836ce1ffea8SJohn Snow shrink = size < hb->size; 837ce1ffea8SJohn Snow 838ce1ffea8SJohn Snow /* bit sizes are identical; nothing to do. */ 839ce1ffea8SJohn Snow if (size == hb->size) { 840ce1ffea8SJohn Snow return; 841ce1ffea8SJohn Snow } 842ce1ffea8SJohn Snow 843ce1ffea8SJohn Snow /* If we're losing bits, let's clear those bits before we invalidate all of 844ce1ffea8SJohn Snow * our invariants. This helps keep the bitcount consistent, and will prevent 845ce1ffea8SJohn Snow * us from carrying around garbage bits beyond the end of the map. 846ce1ffea8SJohn Snow */ 847ce1ffea8SJohn Snow if (shrink) { 848ce1ffea8SJohn Snow /* Don't clear partial granularity groups; 849ce1ffea8SJohn Snow * start at the first full one. */ 8506725f887SMax Reitz uint64_t start = ROUND_UP(num_elements, UINT64_C(1) << hb->granularity); 851ce1ffea8SJohn Snow uint64_t fix_count = (hb->size << hb->granularity) - start; 852ce1ffea8SJohn Snow 853ce1ffea8SJohn Snow assert(fix_count); 854ce1ffea8SJohn Snow hbitmap_reset(hb, start, fix_count); 855ce1ffea8SJohn Snow } 856ce1ffea8SJohn Snow 857ce1ffea8SJohn Snow hb->size = size; 858ce1ffea8SJohn Snow for (i = HBITMAP_LEVELS; i-- > 0; ) { 859ce1ffea8SJohn Snow size = MAX(BITS_TO_LONGS(size), 1); 860ce1ffea8SJohn Snow if (hb->sizes[i] == size) { 861ce1ffea8SJohn Snow break; 862ce1ffea8SJohn Snow } 863ce1ffea8SJohn Snow old = hb->sizes[i]; 864ce1ffea8SJohn Snow hb->sizes[i] = size; 865ce1ffea8SJohn Snow hb->levels[i] = g_realloc(hb->levels[i], size * sizeof(unsigned long)); 866ce1ffea8SJohn Snow if (!shrink) { 867ce1ffea8SJohn Snow memset(&hb->levels[i][old], 0x00, 868ce1ffea8SJohn Snow (size - old) * sizeof(*hb->levels[i])); 869ce1ffea8SJohn Snow } 870ce1ffea8SJohn Snow } 87107ac4cdbSFam Zheng if (hb->meta) { 87207ac4cdbSFam Zheng hbitmap_truncate(hb->meta, hb->size << hb->granularity); 87307ac4cdbSFam Zheng } 874ce1ffea8SJohn Snow } 875ce1ffea8SJohn Snow 876fa000f2fSVladimir Sementsov-Ogievskiy bool hbitmap_can_merge(const HBitmap *a, const HBitmap *b) 877fa000f2fSVladimir Sementsov-Ogievskiy { 878c5b40c1fSJohn Snow return (a->orig_size == b->orig_size); 879c5b40c1fSJohn Snow } 880c5b40c1fSJohn Snow 881c5b40c1fSJohn Snow /** 882c5b40c1fSJohn Snow * hbitmap_sparse_merge: performs dst = dst | src 883c5b40c1fSJohn Snow * works with differing granularities. 884c5b40c1fSJohn Snow * best used when src is sparsely populated. 885c5b40c1fSJohn Snow */ 886c5b40c1fSJohn Snow static void hbitmap_sparse_merge(HBitmap *dst, const HBitmap *src) 887c5b40c1fSJohn Snow { 888299ea9ffSVladimir Sementsov-Ogievskiy int64_t offset; 889299ea9ffSVladimir Sementsov-Ogievskiy int64_t count; 890c5b40c1fSJohn Snow 891299ea9ffSVladimir Sementsov-Ogievskiy for (offset = 0; 892299ea9ffSVladimir Sementsov-Ogievskiy hbitmap_next_dirty_area(src, offset, src->orig_size, INT64_MAX, 893299ea9ffSVladimir Sementsov-Ogievskiy &offset, &count); 894299ea9ffSVladimir Sementsov-Ogievskiy offset += count) 895299ea9ffSVladimir Sementsov-Ogievskiy { 896c5b40c1fSJohn Snow hbitmap_set(dst, offset, count); 897c5b40c1fSJohn Snow } 898fa000f2fSVladimir Sementsov-Ogievskiy } 899ce1ffea8SJohn Snow 900be58721dSJohn Snow /** 9013bde4b01SJohn Snow * Given HBitmaps A and B, let R := A (BITOR) B. 9023bde4b01SJohn Snow * Bitmaps A and B will not be modified, 9033bde4b01SJohn Snow * except when bitmap R is an alias of A or B. 904be58721dSJohn Snow * 905be58721dSJohn Snow * @return true if the merge was successful, 906be58721dSJohn Snow * false if it was not attempted. 907be58721dSJohn Snow */ 908fa000f2fSVladimir Sementsov-Ogievskiy bool hbitmap_merge(const HBitmap *a, const HBitmap *b, HBitmap *result) 909be58721dSJohn Snow { 910be58721dSJohn Snow int i; 911be58721dSJohn Snow uint64_t j; 912be58721dSJohn Snow 913fa000f2fSVladimir Sementsov-Ogievskiy if (!hbitmap_can_merge(a, b) || !hbitmap_can_merge(a, result)) { 914be58721dSJohn Snow return false; 915be58721dSJohn Snow } 916fa000f2fSVladimir Sementsov-Ogievskiy assert(hbitmap_can_merge(b, result)); 917be58721dSJohn Snow 9183bde4b01SJohn Snow if ((!hbitmap_count(a) && result == b) || 9193bde4b01SJohn Snow (!hbitmap_count(b) && result == a)) { 9203bde4b01SJohn Snow return true; 9213bde4b01SJohn Snow } 9223bde4b01SJohn Snow 9233bde4b01SJohn Snow if (!hbitmap_count(a) && !hbitmap_count(b)) { 9243bde4b01SJohn Snow hbitmap_reset_all(result); 925be58721dSJohn Snow return true; 926be58721dSJohn Snow } 927be58721dSJohn Snow 928c5b40c1fSJohn Snow if (a->granularity != b->granularity) { 929c5b40c1fSJohn Snow if ((a != result) && (b != result)) { 930c5b40c1fSJohn Snow hbitmap_reset_all(result); 931c5b40c1fSJohn Snow } 932c5b40c1fSJohn Snow if (a != result) { 933c5b40c1fSJohn Snow hbitmap_sparse_merge(result, a); 934c5b40c1fSJohn Snow } 935c5b40c1fSJohn Snow if (b != result) { 936c5b40c1fSJohn Snow hbitmap_sparse_merge(result, b); 937c5b40c1fSJohn Snow } 938c5b40c1fSJohn Snow return true; 939c5b40c1fSJohn Snow } 940c5b40c1fSJohn Snow 941be58721dSJohn Snow /* This merge is O(size), as BITS_PER_LONG and HBITMAP_LEVELS are constant. 942be58721dSJohn Snow * It may be possible to improve running times for sparsely populated maps 943be58721dSJohn Snow * by using hbitmap_iter_next, but this is suboptimal for dense maps. 944be58721dSJohn Snow */ 945c5b40c1fSJohn Snow assert(a->size == b->size); 946be58721dSJohn Snow for (i = HBITMAP_LEVELS - 1; i >= 0; i--) { 947be58721dSJohn Snow for (j = 0; j < a->sizes[i]; j++) { 948fa000f2fSVladimir Sementsov-Ogievskiy result->levels[i][j] = a->levels[i][j] | b->levels[i][j]; 949be58721dSJohn Snow } 950be58721dSJohn Snow } 951be58721dSJohn Snow 952d1dde714SEric Blake /* Recompute the dirty count */ 953d1dde714SEric Blake result->count = hb_count_between(result, 0, result->size - 1); 954d1dde714SEric Blake 955be58721dSJohn Snow return true; 956be58721dSJohn Snow } 95707ac4cdbSFam Zheng 958a3b52535SVladimir Sementsov-Ogievskiy char *hbitmap_sha256(const HBitmap *bitmap, Error **errp) 959a3b52535SVladimir Sementsov-Ogievskiy { 960a3b52535SVladimir Sementsov-Ogievskiy size_t size = bitmap->sizes[HBITMAP_LEVELS - 1] * sizeof(unsigned long); 961a3b52535SVladimir Sementsov-Ogievskiy char *data = (char *)bitmap->levels[HBITMAP_LEVELS - 1]; 962a3b52535SVladimir Sementsov-Ogievskiy char *hash = NULL; 963a3b52535SVladimir Sementsov-Ogievskiy qcrypto_hash_digest(QCRYPTO_HASH_ALG_SHA256, data, size, &hash, errp); 964a3b52535SVladimir Sementsov-Ogievskiy 965a3b52535SVladimir Sementsov-Ogievskiy return hash; 966a3b52535SVladimir Sementsov-Ogievskiy } 967