include/qemu/hbitmap.h

   1 /*
   2  * Hierarchical Bitmap Data Type
   3  *
   4  * Copyright Red Hat, Inc., 2012
   5  *
   6  * Author: Paolo Bonzini <pbonzini@redhat.com>
   7  *
   8  * This work is licensed under the terms of the GNU GPL, version 2 or
   9  * later.  See the COPYING file in the top-level directory.
  10  */
  11
  12 #ifndef HBITMAP_H
  13 #define HBITMAP_H 1
  14
  15 #include <limits.h>
  16 #include <stdint.h>
  17 #include <stdbool.h>
  18 #include "bitops.h"
  19 #include "host-utils.h"
  20
  21 typedef struct HBitmap HBitmap;
  22 typedef struct HBitmapIter HBitmapIter;
  23
  24 #define BITS_PER_LEVEL         (BITS_PER_LONG == 32 ? 5 : 6)
  25
  26 /* For 32-bit, the largest that fits in a 4 GiB address space.
  27  * For 64-bit, the number of sectors in 1 PiB.  Good luck, in
  28  * either case... :)
  29  */
  30 #define HBITMAP_LOG_MAX_SIZE   (BITS_PER_LONG == 32 ? 34 : 41)
  31
  32 /* We need to place a sentinel in level 0 to speed up iteration.  Thus,
  33  * we do this instead of HBITMAP_LOG_MAX_SIZE / BITS_PER_LEVEL.  The
  34  * difference is that it allocates an extra level when HBITMAP_LOG_MAX_SIZE
  35  * is an exact multiple of BITS_PER_LEVEL.
  36  */
  37 #define HBITMAP_LEVELS         ((HBITMAP_LOG_MAX_SIZE / BITS_PER_LEVEL) + 1)
  38
  39 struct HBitmapIter {
  40     const HBitmap *hb;
  41
  42     /* Copied from hb for access in the inline functions (hb is opaque).  */
  43     int granularity;
  44
  45     /* Entry offset into the last-level array of longs.  */
  46     size_t pos;
  47
  48     /* The currently-active path in the tree.  Each item of cur[i] stores
  49      * the bits (i.e. the subtrees) yet to be processed under that node.
  50      */
  51     unsigned long cur[HBITMAP_LEVELS];
  52 };
  53
  54 /**
  55  * hbitmap_alloc:
  56  * @size: Number of bits in the bitmap.
  57  * @granularity: Granularity of the bitmap.  Aligned groups of 2^@granularity
  58  * bits will be represented by a single bit.  Each operation on a
  59  * range of bits first rounds the bits to determine which group they land
  60  * in, and then affect the entire set; iteration will only visit the first
  61  * bit of each group.
  62  *
  63  * Allocate a new HBitmap.
  64  */
  65 HBitmap *hbitmap_alloc(uint64_t size, int granularity);
  66
  67 /**
  68  * hbitmap_truncate:
  69  * @hb: The bitmap to change the size of.
  70  * @size: The number of elements to change the bitmap to accommodate.
  71  *
  72  * truncate or grow an existing bitmap to accommodate a new number of elements.
  73  * This may invalidate existing HBitmapIterators.
  74  */
  75 void hbitmap_truncate(HBitmap *hb, uint64_t size);
  76
  77 /**
  78  * hbitmap_merge:
  79  * @a: The bitmap to store the result in.
  80  * @b: The bitmap to merge into @a.
  81  * @return true if the merge was successful,
  82  *         false if it was not attempted.
  83  *
  84  * Merge two bitmaps together.
  85  * A := A (BITOR) B.
  86  * B is left unmodified.
  87  */
  88 bool hbitmap_merge(HBitmap *a, const HBitmap *b);
  89
  90 /**
  91  * hbitmap_empty:
  92  * @hb: HBitmap to operate on.
  93  *
  94  * Return whether the bitmap is empty.
  95  */
  96 bool hbitmap_empty(const HBitmap *hb);
  97
  98 /**
  99  * hbitmap_granularity:
 100  * @hb: HBitmap to operate on.
 101  *
 102  * Return the granularity of the HBitmap.
 103  */
 104 int hbitmap_granularity(const HBitmap *hb);
 105
 106 /**
 107  * hbitmap_count:
 108  * @hb: HBitmap to operate on.
 109  *
 110  * Return the number of bits set in the HBitmap.
 111  */
 112 uint64_t hbitmap_count(const HBitmap *hb);
 113
 114 /**
 115  * hbitmap_set:
 116  * @hb: HBitmap to operate on.
 117  * @start: First bit to set (0-based).
 118  * @count: Number of bits to set.
 119  *
 120  * Set a consecutive range of bits in an HBitmap.
 121  */
 122 void hbitmap_set(HBitmap *hb, uint64_t start, uint64_t count);
 123
 124 /**
 125  * hbitmap_reset:
 126  * @hb: HBitmap to operate on.
 127  * @start: First bit to reset (0-based).
 128  * @count: Number of bits to reset.
 129  *
 130  * Reset a consecutive range of bits in an HBitmap.
 131  */
 132 void hbitmap_reset(HBitmap *hb, uint64_t start, uint64_t count);
 133
 134 /**
 135  * hbitmap_reset_all:
 136  * @hb: HBitmap to operate on.
 137  *
 138  * Reset all bits in an HBitmap.
 139  */
 140 void hbitmap_reset_all(HBitmap *hb);
 141
 142 /**
 143  * hbitmap_get:
 144  * @hb: HBitmap to operate on.
 145  * @item: Bit to query (0-based).
 146  *
 147  * Return whether the @item-th bit in an HBitmap is set.
 148  */
 149 bool hbitmap_get(const HBitmap *hb, uint64_t item);
 150
 151 /**
 152  * hbitmap_free:
 153  * @hb: HBitmap to operate on.
 154  *
 155  * Free an HBitmap and all of its associated memory.
 156  */
 157 void hbitmap_free(HBitmap *hb);
 158
 159 /**
 160  * hbitmap_iter_init:
 161  * @hbi: HBitmapIter to initialize.
 162  * @hb: HBitmap to iterate on.
 163  * @first: First bit to visit (0-based, must be strictly less than the
 164  * size of the bitmap).
 165  *
 166  * Set up @hbi to iterate on the HBitmap @hb.  hbitmap_iter_next will return
 167  * the lowest-numbered bit that is set in @hb, starting at @first.
 168  *
 169  * Concurrent setting of bits is acceptable, and will at worst cause the
 170  * iteration to miss some of those bits.  Resetting bits before the current
 171  * position of the iterator is also okay.  However, concurrent resetting of
 172  * bits can lead to unexpected behavior if the iterator has not yet reached
 173  * those bits.
 174  */
 175 void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first);
 176
 177 /* hbitmap_iter_skip_words:
 178  * @hbi: HBitmapIter to operate on.
 179  *
 180  * Internal function used by hbitmap_iter_next and hbitmap_iter_next_word.
 181  */
 182 unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi);
 183
 184 /**
 185  * hbitmap_iter_next:
 186  * @hbi: HBitmapIter to operate on.
 187  *
 188  * Return the next bit that is set in @hbi's associated HBitmap,
 189  * or -1 if all remaining bits are zero.
 190  */
 191 static inline int64_t hbitmap_iter_next(HBitmapIter *hbi)
 192 {
 193     unsigned long cur = hbi->cur[HBITMAP_LEVELS - 1];
 194     int64_t item;
 195
 196     if (cur == 0) {
 197         cur = hbitmap_iter_skip_words(hbi);
 198         if (cur == 0) {
 199             return -1;
 200         }
 201     }
 202
 203     /* The next call will resume work from the next bit.  */
 204     hbi->cur[HBITMAP_LEVELS - 1] = cur & (cur - 1);
 205     item = ((uint64_t)hbi->pos << BITS_PER_LEVEL) + ctzl(cur);
 206
 207     return item << hbi->granularity;
 208 }
 209
 210 /**
 211  * hbitmap_iter_next_word:
 212  * @hbi: HBitmapIter to operate on.
 213  * @p_cur: Location where to store the next non-zero word.
 214  *
 215  * Return the index of the next nonzero word that is set in @hbi's
 216  * associated HBitmap, and set *p_cur to the content of that word
 217  * (bits before the index that was passed to hbitmap_iter_init are
 218  * trimmed on the first call).  Return -1, and set *p_cur to zero,
 219  * if all remaining words are zero.
 220  */
 221 static inline size_t hbitmap_iter_next_word(HBitmapIter *hbi, unsigned long *p_cur)
 222 {
 223     unsigned long cur = hbi->cur[HBITMAP_LEVELS - 1];
 224
 225     if (cur == 0) {
 226         cur = hbitmap_iter_skip_words(hbi);
 227         if (cur == 0) {
 228             *p_cur = 0;
 229             return -1;
 230         }
 231     }
 232
 233     /* The next call will resume work from the next word.  */
 234     hbi->cur[HBITMAP_LEVELS - 1] = 0;
 235     *p_cur = cur;
 236     return hbi->pos;
 237 }
 238
 239
 240 #endif