1*e7c033c3SPaolo Bonzini /* 2*e7c033c3SPaolo Bonzini * Hierarchical Bitmap Data Type 3*e7c033c3SPaolo Bonzini * 4*e7c033c3SPaolo Bonzini * Copyright Red Hat, Inc., 2012 5*e7c033c3SPaolo Bonzini * 6*e7c033c3SPaolo Bonzini * Author: Paolo Bonzini <pbonzini@redhat.com> 7*e7c033c3SPaolo Bonzini * 8*e7c033c3SPaolo Bonzini * This work is licensed under the terms of the GNU GPL, version 2 or 9*e7c033c3SPaolo Bonzini * later. See the COPYING file in the top-level directory. 10*e7c033c3SPaolo Bonzini */ 11*e7c033c3SPaolo Bonzini 12*e7c033c3SPaolo Bonzini #include <string.h> 13*e7c033c3SPaolo Bonzini #include <glib.h> 14*e7c033c3SPaolo Bonzini #include <assert.h> 15*e7c033c3SPaolo Bonzini #include "qemu/osdep.h" 16*e7c033c3SPaolo Bonzini #include "qemu/hbitmap.h" 17*e7c033c3SPaolo Bonzini #include "qemu/host-utils.h" 18*e7c033c3SPaolo Bonzini #include "trace.h" 19*e7c033c3SPaolo Bonzini 20*e7c033c3SPaolo Bonzini /* HBitmaps provides an array of bits. The bits are stored as usual in an 21*e7c033c3SPaolo Bonzini * array of unsigned longs, but HBitmap is also optimized to provide fast 22*e7c033c3SPaolo Bonzini * iteration over set bits; going from one bit to the next is O(logB n) 23*e7c033c3SPaolo Bonzini * worst case, with B = sizeof(long) * CHAR_BIT: the result is low enough 24*e7c033c3SPaolo Bonzini * that the number of levels is in fact fixed. 25*e7c033c3SPaolo Bonzini * 26*e7c033c3SPaolo Bonzini * In order to do this, it stacks multiple bitmaps with progressively coarser 27*e7c033c3SPaolo Bonzini * granularity; in all levels except the last, bit N is set iff the N-th 28*e7c033c3SPaolo Bonzini * unsigned long is nonzero in the immediately next level. When iteration 29*e7c033c3SPaolo Bonzini * completes on the last level it can examine the 2nd-last level to quickly 30*e7c033c3SPaolo Bonzini * skip entire words, and even do so recursively to skip blocks of 64 words or 31*e7c033c3SPaolo Bonzini * powers thereof (32 on 32-bit machines). 32*e7c033c3SPaolo Bonzini * 33*e7c033c3SPaolo Bonzini * Given an index in the bitmap, it can be split in group of bits like 34*e7c033c3SPaolo Bonzini * this (for the 64-bit case): 35*e7c033c3SPaolo Bonzini * 36*e7c033c3SPaolo Bonzini * bits 0-57 => word in the last bitmap | bits 58-63 => bit in the word 37*e7c033c3SPaolo Bonzini * bits 0-51 => word in the 2nd-last bitmap | bits 52-57 => bit in the word 38*e7c033c3SPaolo Bonzini * bits 0-45 => word in the 3rd-last bitmap | bits 46-51 => bit in the word 39*e7c033c3SPaolo Bonzini * 40*e7c033c3SPaolo Bonzini * So it is easy to move up simply by shifting the index right by 41*e7c033c3SPaolo Bonzini * log2(BITS_PER_LONG) bits. To move down, you shift the index left 42*e7c033c3SPaolo Bonzini * similarly, and add the word index within the group. Iteration uses 43*e7c033c3SPaolo Bonzini * ffs (find first set bit) to find the next word to examine; this 44*e7c033c3SPaolo Bonzini * operation can be done in constant time in most current architectures. 45*e7c033c3SPaolo Bonzini * 46*e7c033c3SPaolo Bonzini * Setting or clearing a range of m bits on all levels, the work to perform 47*e7c033c3SPaolo Bonzini * is O(m + m/W + m/W^2 + ...), which is O(m) like on a regular bitmap. 48*e7c033c3SPaolo Bonzini * 49*e7c033c3SPaolo Bonzini * When iterating on a bitmap, each bit (on any level) is only visited 50*e7c033c3SPaolo Bonzini * once. Hence, The total cost of visiting a bitmap with m bits in it is 51*e7c033c3SPaolo Bonzini * the number of bits that are set in all bitmaps. Unless the bitmap is 52*e7c033c3SPaolo Bonzini * extremely sparse, this is also O(m + m/W + m/W^2 + ...), so the amortized 53*e7c033c3SPaolo Bonzini * cost of advancing from one bit to the next is usually constant (worst case 54*e7c033c3SPaolo Bonzini * O(logB n) as in the non-amortized complexity). 55*e7c033c3SPaolo Bonzini */ 56*e7c033c3SPaolo Bonzini 57*e7c033c3SPaolo Bonzini struct HBitmap { 58*e7c033c3SPaolo Bonzini /* Number of total bits in the bottom level. */ 59*e7c033c3SPaolo Bonzini uint64_t size; 60*e7c033c3SPaolo Bonzini 61*e7c033c3SPaolo Bonzini /* Number of set bits in the bottom level. */ 62*e7c033c3SPaolo Bonzini uint64_t count; 63*e7c033c3SPaolo Bonzini 64*e7c033c3SPaolo Bonzini /* A scaling factor. Given a granularity of G, each bit in the bitmap will 65*e7c033c3SPaolo Bonzini * will actually represent a group of 2^G elements. Each operation on a 66*e7c033c3SPaolo Bonzini * range of bits first rounds the bits to determine which group they land 67*e7c033c3SPaolo Bonzini * in, and then affect the entire page; iteration will only visit the first 68*e7c033c3SPaolo Bonzini * bit of each group. Here is an example of operations in a size-16, 69*e7c033c3SPaolo Bonzini * granularity-1 HBitmap: 70*e7c033c3SPaolo Bonzini * 71*e7c033c3SPaolo Bonzini * initial state 00000000 72*e7c033c3SPaolo Bonzini * set(start=0, count=9) 11111000 (iter: 0, 2, 4, 6, 8) 73*e7c033c3SPaolo Bonzini * reset(start=1, count=3) 00111000 (iter: 4, 6, 8) 74*e7c033c3SPaolo Bonzini * set(start=9, count=2) 00111100 (iter: 4, 6, 8, 10) 75*e7c033c3SPaolo Bonzini * reset(start=5, count=5) 00000000 76*e7c033c3SPaolo Bonzini * 77*e7c033c3SPaolo Bonzini * From an implementation point of view, when setting or resetting bits, 78*e7c033c3SPaolo Bonzini * the bitmap will scale bit numbers right by this amount of bits. When 79*e7c033c3SPaolo Bonzini * iterating, the bitmap will scale bit numbers left by this amount of 80*e7c033c3SPaolo Bonzini * bits. 81*e7c033c3SPaolo Bonzini */ 82*e7c033c3SPaolo Bonzini int granularity; 83*e7c033c3SPaolo Bonzini 84*e7c033c3SPaolo Bonzini /* A number of progressively less coarse bitmaps (i.e. level 0 is the 85*e7c033c3SPaolo Bonzini * coarsest). Each bit in level N represents a word in level N+1 that 86*e7c033c3SPaolo Bonzini * has a set bit, except the last level where each bit represents the 87*e7c033c3SPaolo Bonzini * actual bitmap. 88*e7c033c3SPaolo Bonzini * 89*e7c033c3SPaolo Bonzini * Note that all bitmaps have the same number of levels. Even a 1-bit 90*e7c033c3SPaolo Bonzini * bitmap will still allocate HBITMAP_LEVELS arrays. 91*e7c033c3SPaolo Bonzini */ 92*e7c033c3SPaolo Bonzini unsigned long *levels[HBITMAP_LEVELS]; 93*e7c033c3SPaolo Bonzini }; 94*e7c033c3SPaolo Bonzini 95*e7c033c3SPaolo Bonzini static inline int popcountl(unsigned long l) 96*e7c033c3SPaolo Bonzini { 97*e7c033c3SPaolo Bonzini return BITS_PER_LONG == 32 ? ctpop32(l) : ctpop64(l); 98*e7c033c3SPaolo Bonzini } 99*e7c033c3SPaolo Bonzini 100*e7c033c3SPaolo Bonzini /* Advance hbi to the next nonzero word and return it. hbi->pos 101*e7c033c3SPaolo Bonzini * is updated. Returns zero if we reach the end of the bitmap. 102*e7c033c3SPaolo Bonzini */ 103*e7c033c3SPaolo Bonzini unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi) 104*e7c033c3SPaolo Bonzini { 105*e7c033c3SPaolo Bonzini size_t pos = hbi->pos; 106*e7c033c3SPaolo Bonzini const HBitmap *hb = hbi->hb; 107*e7c033c3SPaolo Bonzini unsigned i = HBITMAP_LEVELS - 1; 108*e7c033c3SPaolo Bonzini 109*e7c033c3SPaolo Bonzini unsigned long cur; 110*e7c033c3SPaolo Bonzini do { 111*e7c033c3SPaolo Bonzini cur = hbi->cur[--i]; 112*e7c033c3SPaolo Bonzini pos >>= BITS_PER_LEVEL; 113*e7c033c3SPaolo Bonzini } while (cur == 0); 114*e7c033c3SPaolo Bonzini 115*e7c033c3SPaolo Bonzini /* Check for end of iteration. We always use fewer than BITS_PER_LONG 116*e7c033c3SPaolo Bonzini * bits in the level 0 bitmap; thus we can repurpose the most significant 117*e7c033c3SPaolo Bonzini * bit as a sentinel. The sentinel is set in hbitmap_alloc and ensures 118*e7c033c3SPaolo Bonzini * that the above loop ends even without an explicit check on i. 119*e7c033c3SPaolo Bonzini */ 120*e7c033c3SPaolo Bonzini 121*e7c033c3SPaolo Bonzini if (i == 0 && cur == (1UL << (BITS_PER_LONG - 1))) { 122*e7c033c3SPaolo Bonzini return 0; 123*e7c033c3SPaolo Bonzini } 124*e7c033c3SPaolo Bonzini for (; i < HBITMAP_LEVELS - 1; i++) { 125*e7c033c3SPaolo Bonzini /* Shift back pos to the left, matching the right shifts above. 126*e7c033c3SPaolo Bonzini * The index of this word's least significant set bit provides 127*e7c033c3SPaolo Bonzini * the low-order bits. 128*e7c033c3SPaolo Bonzini */ 129*e7c033c3SPaolo Bonzini pos = (pos << BITS_PER_LEVEL) + ffsl(cur) - 1; 130*e7c033c3SPaolo Bonzini hbi->cur[i] = cur & (cur - 1); 131*e7c033c3SPaolo Bonzini 132*e7c033c3SPaolo Bonzini /* Set up next level for iteration. */ 133*e7c033c3SPaolo Bonzini cur = hb->levels[i + 1][pos]; 134*e7c033c3SPaolo Bonzini } 135*e7c033c3SPaolo Bonzini 136*e7c033c3SPaolo Bonzini hbi->pos = pos; 137*e7c033c3SPaolo Bonzini trace_hbitmap_iter_skip_words(hbi->hb, hbi, pos, cur); 138*e7c033c3SPaolo Bonzini 139*e7c033c3SPaolo Bonzini assert(cur); 140*e7c033c3SPaolo Bonzini return cur; 141*e7c033c3SPaolo Bonzini } 142*e7c033c3SPaolo Bonzini 143*e7c033c3SPaolo Bonzini void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first) 144*e7c033c3SPaolo Bonzini { 145*e7c033c3SPaolo Bonzini unsigned i, bit; 146*e7c033c3SPaolo Bonzini uint64_t pos; 147*e7c033c3SPaolo Bonzini 148*e7c033c3SPaolo Bonzini hbi->hb = hb; 149*e7c033c3SPaolo Bonzini pos = first >> hb->granularity; 150*e7c033c3SPaolo Bonzini hbi->pos = pos >> BITS_PER_LEVEL; 151*e7c033c3SPaolo Bonzini hbi->granularity = hb->granularity; 152*e7c033c3SPaolo Bonzini 153*e7c033c3SPaolo Bonzini for (i = HBITMAP_LEVELS; i-- > 0; ) { 154*e7c033c3SPaolo Bonzini bit = pos & (BITS_PER_LONG - 1); 155*e7c033c3SPaolo Bonzini pos >>= BITS_PER_LEVEL; 156*e7c033c3SPaolo Bonzini 157*e7c033c3SPaolo Bonzini /* Drop bits representing items before first. */ 158*e7c033c3SPaolo Bonzini hbi->cur[i] = hb->levels[i][pos] & ~((1UL << bit) - 1); 159*e7c033c3SPaolo Bonzini 160*e7c033c3SPaolo Bonzini /* We have already added level i+1, so the lowest set bit has 161*e7c033c3SPaolo Bonzini * been processed. Clear it. 162*e7c033c3SPaolo Bonzini */ 163*e7c033c3SPaolo Bonzini if (i != HBITMAP_LEVELS - 1) { 164*e7c033c3SPaolo Bonzini hbi->cur[i] &= ~(1UL << bit); 165*e7c033c3SPaolo Bonzini } 166*e7c033c3SPaolo Bonzini } 167*e7c033c3SPaolo Bonzini } 168*e7c033c3SPaolo Bonzini 169*e7c033c3SPaolo Bonzini bool hbitmap_empty(const HBitmap *hb) 170*e7c033c3SPaolo Bonzini { 171*e7c033c3SPaolo Bonzini return hb->count == 0; 172*e7c033c3SPaolo Bonzini } 173*e7c033c3SPaolo Bonzini 174*e7c033c3SPaolo Bonzini int hbitmap_granularity(const HBitmap *hb) 175*e7c033c3SPaolo Bonzini { 176*e7c033c3SPaolo Bonzini return hb->granularity; 177*e7c033c3SPaolo Bonzini } 178*e7c033c3SPaolo Bonzini 179*e7c033c3SPaolo Bonzini uint64_t hbitmap_count(const HBitmap *hb) 180*e7c033c3SPaolo Bonzini { 181*e7c033c3SPaolo Bonzini return hb->count << hb->granularity; 182*e7c033c3SPaolo Bonzini } 183*e7c033c3SPaolo Bonzini 184*e7c033c3SPaolo Bonzini /* Count the number of set bits between start and end, not accounting for 185*e7c033c3SPaolo Bonzini * the granularity. Also an example of how to use hbitmap_iter_next_word. 186*e7c033c3SPaolo Bonzini */ 187*e7c033c3SPaolo Bonzini static uint64_t hb_count_between(HBitmap *hb, uint64_t start, uint64_t last) 188*e7c033c3SPaolo Bonzini { 189*e7c033c3SPaolo Bonzini HBitmapIter hbi; 190*e7c033c3SPaolo Bonzini uint64_t count = 0; 191*e7c033c3SPaolo Bonzini uint64_t end = last + 1; 192*e7c033c3SPaolo Bonzini unsigned long cur; 193*e7c033c3SPaolo Bonzini size_t pos; 194*e7c033c3SPaolo Bonzini 195*e7c033c3SPaolo Bonzini hbitmap_iter_init(&hbi, hb, start << hb->granularity); 196*e7c033c3SPaolo Bonzini for (;;) { 197*e7c033c3SPaolo Bonzini pos = hbitmap_iter_next_word(&hbi, &cur); 198*e7c033c3SPaolo Bonzini if (pos >= (end >> BITS_PER_LEVEL)) { 199*e7c033c3SPaolo Bonzini break; 200*e7c033c3SPaolo Bonzini } 201*e7c033c3SPaolo Bonzini count += popcountl(cur); 202*e7c033c3SPaolo Bonzini } 203*e7c033c3SPaolo Bonzini 204*e7c033c3SPaolo Bonzini if (pos == (end >> BITS_PER_LEVEL)) { 205*e7c033c3SPaolo Bonzini /* Drop bits representing the END-th and subsequent items. */ 206*e7c033c3SPaolo Bonzini int bit = end & (BITS_PER_LONG - 1); 207*e7c033c3SPaolo Bonzini cur &= (1UL << bit) - 1; 208*e7c033c3SPaolo Bonzini count += popcountl(cur); 209*e7c033c3SPaolo Bonzini } 210*e7c033c3SPaolo Bonzini 211*e7c033c3SPaolo Bonzini return count; 212*e7c033c3SPaolo Bonzini } 213*e7c033c3SPaolo Bonzini 214*e7c033c3SPaolo Bonzini /* Setting starts at the last layer and propagates up if an element 215*e7c033c3SPaolo Bonzini * changes from zero to non-zero. 216*e7c033c3SPaolo Bonzini */ 217*e7c033c3SPaolo Bonzini static inline bool hb_set_elem(unsigned long *elem, uint64_t start, uint64_t last) 218*e7c033c3SPaolo Bonzini { 219*e7c033c3SPaolo Bonzini unsigned long mask; 220*e7c033c3SPaolo Bonzini bool changed; 221*e7c033c3SPaolo Bonzini 222*e7c033c3SPaolo Bonzini assert((last >> BITS_PER_LEVEL) == (start >> BITS_PER_LEVEL)); 223*e7c033c3SPaolo Bonzini assert(start <= last); 224*e7c033c3SPaolo Bonzini 225*e7c033c3SPaolo Bonzini mask = 2UL << (last & (BITS_PER_LONG - 1)); 226*e7c033c3SPaolo Bonzini mask -= 1UL << (start & (BITS_PER_LONG - 1)); 227*e7c033c3SPaolo Bonzini changed = (*elem == 0); 228*e7c033c3SPaolo Bonzini *elem |= mask; 229*e7c033c3SPaolo Bonzini return changed; 230*e7c033c3SPaolo Bonzini } 231*e7c033c3SPaolo Bonzini 232*e7c033c3SPaolo Bonzini /* The recursive workhorse (the depth is limited to HBITMAP_LEVELS)... */ 233*e7c033c3SPaolo Bonzini static void hb_set_between(HBitmap *hb, int level, uint64_t start, uint64_t last) 234*e7c033c3SPaolo Bonzini { 235*e7c033c3SPaolo Bonzini size_t pos = start >> BITS_PER_LEVEL; 236*e7c033c3SPaolo Bonzini size_t lastpos = last >> BITS_PER_LEVEL; 237*e7c033c3SPaolo Bonzini bool changed = false; 238*e7c033c3SPaolo Bonzini size_t i; 239*e7c033c3SPaolo Bonzini 240*e7c033c3SPaolo Bonzini i = pos; 241*e7c033c3SPaolo Bonzini if (i < lastpos) { 242*e7c033c3SPaolo Bonzini uint64_t next = (start | (BITS_PER_LONG - 1)) + 1; 243*e7c033c3SPaolo Bonzini changed |= hb_set_elem(&hb->levels[level][i], start, next - 1); 244*e7c033c3SPaolo Bonzini for (;;) { 245*e7c033c3SPaolo Bonzini start = next; 246*e7c033c3SPaolo Bonzini next += BITS_PER_LONG; 247*e7c033c3SPaolo Bonzini if (++i == lastpos) { 248*e7c033c3SPaolo Bonzini break; 249*e7c033c3SPaolo Bonzini } 250*e7c033c3SPaolo Bonzini changed |= (hb->levels[level][i] == 0); 251*e7c033c3SPaolo Bonzini hb->levels[level][i] = ~0UL; 252*e7c033c3SPaolo Bonzini } 253*e7c033c3SPaolo Bonzini } 254*e7c033c3SPaolo Bonzini changed |= hb_set_elem(&hb->levels[level][i], start, last); 255*e7c033c3SPaolo Bonzini 256*e7c033c3SPaolo Bonzini /* If there was any change in this layer, we may have to update 257*e7c033c3SPaolo Bonzini * the one above. 258*e7c033c3SPaolo Bonzini */ 259*e7c033c3SPaolo Bonzini if (level > 0 && changed) { 260*e7c033c3SPaolo Bonzini hb_set_between(hb, level - 1, pos, lastpos); 261*e7c033c3SPaolo Bonzini } 262*e7c033c3SPaolo Bonzini } 263*e7c033c3SPaolo Bonzini 264*e7c033c3SPaolo Bonzini void hbitmap_set(HBitmap *hb, uint64_t start, uint64_t count) 265*e7c033c3SPaolo Bonzini { 266*e7c033c3SPaolo Bonzini /* Compute range in the last layer. */ 267*e7c033c3SPaolo Bonzini uint64_t last = start + count - 1; 268*e7c033c3SPaolo Bonzini 269*e7c033c3SPaolo Bonzini trace_hbitmap_set(hb, start, count, 270*e7c033c3SPaolo Bonzini start >> hb->granularity, last >> hb->granularity); 271*e7c033c3SPaolo Bonzini 272*e7c033c3SPaolo Bonzini start >>= hb->granularity; 273*e7c033c3SPaolo Bonzini last >>= hb->granularity; 274*e7c033c3SPaolo Bonzini count = last - start + 1; 275*e7c033c3SPaolo Bonzini 276*e7c033c3SPaolo Bonzini hb->count += count - hb_count_between(hb, start, last); 277*e7c033c3SPaolo Bonzini hb_set_between(hb, HBITMAP_LEVELS - 1, start, last); 278*e7c033c3SPaolo Bonzini } 279*e7c033c3SPaolo Bonzini 280*e7c033c3SPaolo Bonzini /* Resetting works the other way round: propagate up if the new 281*e7c033c3SPaolo Bonzini * value is zero. 282*e7c033c3SPaolo Bonzini */ 283*e7c033c3SPaolo Bonzini static inline bool hb_reset_elem(unsigned long *elem, uint64_t start, uint64_t last) 284*e7c033c3SPaolo Bonzini { 285*e7c033c3SPaolo Bonzini unsigned long mask; 286*e7c033c3SPaolo Bonzini bool blanked; 287*e7c033c3SPaolo Bonzini 288*e7c033c3SPaolo Bonzini assert((last >> BITS_PER_LEVEL) == (start >> BITS_PER_LEVEL)); 289*e7c033c3SPaolo Bonzini assert(start <= last); 290*e7c033c3SPaolo Bonzini 291*e7c033c3SPaolo Bonzini mask = 2UL << (last & (BITS_PER_LONG - 1)); 292*e7c033c3SPaolo Bonzini mask -= 1UL << (start & (BITS_PER_LONG - 1)); 293*e7c033c3SPaolo Bonzini blanked = *elem != 0 && ((*elem & ~mask) == 0); 294*e7c033c3SPaolo Bonzini *elem &= ~mask; 295*e7c033c3SPaolo Bonzini return blanked; 296*e7c033c3SPaolo Bonzini } 297*e7c033c3SPaolo Bonzini 298*e7c033c3SPaolo Bonzini /* The recursive workhorse (the depth is limited to HBITMAP_LEVELS)... */ 299*e7c033c3SPaolo Bonzini static void hb_reset_between(HBitmap *hb, int level, uint64_t start, uint64_t last) 300*e7c033c3SPaolo Bonzini { 301*e7c033c3SPaolo Bonzini size_t pos = start >> BITS_PER_LEVEL; 302*e7c033c3SPaolo Bonzini size_t lastpos = last >> BITS_PER_LEVEL; 303*e7c033c3SPaolo Bonzini bool changed = false; 304*e7c033c3SPaolo Bonzini size_t i; 305*e7c033c3SPaolo Bonzini 306*e7c033c3SPaolo Bonzini i = pos; 307*e7c033c3SPaolo Bonzini if (i < lastpos) { 308*e7c033c3SPaolo Bonzini uint64_t next = (start | (BITS_PER_LONG - 1)) + 1; 309*e7c033c3SPaolo Bonzini 310*e7c033c3SPaolo Bonzini /* Here we need a more complex test than when setting bits. Even if 311*e7c033c3SPaolo Bonzini * something was changed, we must not blank bits in the upper level 312*e7c033c3SPaolo Bonzini * unless the lower-level word became entirely zero. So, remove pos 313*e7c033c3SPaolo Bonzini * from the upper-level range if bits remain set. 314*e7c033c3SPaolo Bonzini */ 315*e7c033c3SPaolo Bonzini if (hb_reset_elem(&hb->levels[level][i], start, next - 1)) { 316*e7c033c3SPaolo Bonzini changed = true; 317*e7c033c3SPaolo Bonzini } else { 318*e7c033c3SPaolo Bonzini pos++; 319*e7c033c3SPaolo Bonzini } 320*e7c033c3SPaolo Bonzini 321*e7c033c3SPaolo Bonzini for (;;) { 322*e7c033c3SPaolo Bonzini start = next; 323*e7c033c3SPaolo Bonzini next += BITS_PER_LONG; 324*e7c033c3SPaolo Bonzini if (++i == lastpos) { 325*e7c033c3SPaolo Bonzini break; 326*e7c033c3SPaolo Bonzini } 327*e7c033c3SPaolo Bonzini changed |= (hb->levels[level][i] != 0); 328*e7c033c3SPaolo Bonzini hb->levels[level][i] = 0UL; 329*e7c033c3SPaolo Bonzini } 330*e7c033c3SPaolo Bonzini } 331*e7c033c3SPaolo Bonzini 332*e7c033c3SPaolo Bonzini /* Same as above, this time for lastpos. */ 333*e7c033c3SPaolo Bonzini if (hb_reset_elem(&hb->levels[level][i], start, last)) { 334*e7c033c3SPaolo Bonzini changed = true; 335*e7c033c3SPaolo Bonzini } else { 336*e7c033c3SPaolo Bonzini lastpos--; 337*e7c033c3SPaolo Bonzini } 338*e7c033c3SPaolo Bonzini 339*e7c033c3SPaolo Bonzini if (level > 0 && changed) { 340*e7c033c3SPaolo Bonzini hb_reset_between(hb, level - 1, pos, lastpos); 341*e7c033c3SPaolo Bonzini } 342*e7c033c3SPaolo Bonzini } 343*e7c033c3SPaolo Bonzini 344*e7c033c3SPaolo Bonzini void hbitmap_reset(HBitmap *hb, uint64_t start, uint64_t count) 345*e7c033c3SPaolo Bonzini { 346*e7c033c3SPaolo Bonzini /* Compute range in the last layer. */ 347*e7c033c3SPaolo Bonzini uint64_t last = start + count - 1; 348*e7c033c3SPaolo Bonzini 349*e7c033c3SPaolo Bonzini trace_hbitmap_reset(hb, start, count, 350*e7c033c3SPaolo Bonzini start >> hb->granularity, last >> hb->granularity); 351*e7c033c3SPaolo Bonzini 352*e7c033c3SPaolo Bonzini start >>= hb->granularity; 353*e7c033c3SPaolo Bonzini last >>= hb->granularity; 354*e7c033c3SPaolo Bonzini 355*e7c033c3SPaolo Bonzini hb->count -= hb_count_between(hb, start, last); 356*e7c033c3SPaolo Bonzini hb_reset_between(hb, HBITMAP_LEVELS - 1, start, last); 357*e7c033c3SPaolo Bonzini } 358*e7c033c3SPaolo Bonzini 359*e7c033c3SPaolo Bonzini bool hbitmap_get(const HBitmap *hb, uint64_t item) 360*e7c033c3SPaolo Bonzini { 361*e7c033c3SPaolo Bonzini /* Compute position and bit in the last layer. */ 362*e7c033c3SPaolo Bonzini uint64_t pos = item >> hb->granularity; 363*e7c033c3SPaolo Bonzini unsigned long bit = 1UL << (pos & (BITS_PER_LONG - 1)); 364*e7c033c3SPaolo Bonzini 365*e7c033c3SPaolo Bonzini return (hb->levels[HBITMAP_LEVELS - 1][pos >> BITS_PER_LEVEL] & bit) != 0; 366*e7c033c3SPaolo Bonzini } 367*e7c033c3SPaolo Bonzini 368*e7c033c3SPaolo Bonzini void hbitmap_free(HBitmap *hb) 369*e7c033c3SPaolo Bonzini { 370*e7c033c3SPaolo Bonzini unsigned i; 371*e7c033c3SPaolo Bonzini for (i = HBITMAP_LEVELS; i-- > 0; ) { 372*e7c033c3SPaolo Bonzini g_free(hb->levels[i]); 373*e7c033c3SPaolo Bonzini } 374*e7c033c3SPaolo Bonzini g_free(hb); 375*e7c033c3SPaolo Bonzini } 376*e7c033c3SPaolo Bonzini 377*e7c033c3SPaolo Bonzini HBitmap *hbitmap_alloc(uint64_t size, int granularity) 378*e7c033c3SPaolo Bonzini { 379*e7c033c3SPaolo Bonzini HBitmap *hb = g_malloc0(sizeof (struct HBitmap)); 380*e7c033c3SPaolo Bonzini unsigned i; 381*e7c033c3SPaolo Bonzini 382*e7c033c3SPaolo Bonzini assert(granularity >= 0 && granularity < 64); 383*e7c033c3SPaolo Bonzini size = (size + (1ULL << granularity) - 1) >> granularity; 384*e7c033c3SPaolo Bonzini assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE)); 385*e7c033c3SPaolo Bonzini 386*e7c033c3SPaolo Bonzini hb->size = size; 387*e7c033c3SPaolo Bonzini hb->granularity = granularity; 388*e7c033c3SPaolo Bonzini for (i = HBITMAP_LEVELS; i-- > 0; ) { 389*e7c033c3SPaolo Bonzini size = MAX((size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL, 1); 390*e7c033c3SPaolo Bonzini hb->levels[i] = g_malloc0(size * sizeof(unsigned long)); 391*e7c033c3SPaolo Bonzini } 392*e7c033c3SPaolo Bonzini 393*e7c033c3SPaolo Bonzini /* We necessarily have free bits in level 0 due to the definition 394*e7c033c3SPaolo Bonzini * of HBITMAP_LEVELS, so use one for a sentinel. This speeds up 395*e7c033c3SPaolo Bonzini * hbitmap_iter_skip_words. 396*e7c033c3SPaolo Bonzini */ 397*e7c033c3SPaolo Bonzini assert(size == 1); 398*e7c033c3SPaolo Bonzini hb->levels[0][0] |= 1UL << (BITS_PER_LONG - 1); 399*e7c033c3SPaolo Bonzini return hb; 400*e7c033c3SPaolo Bonzini } 401