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_empty:
  69  * @hb: HBitmap to operate on.
  70  *
  71  * Return whether the bitmap is empty.
  72  */
  73 bool hbitmap_empty(const HBitmap *hb);
  74
  75 /**
  76  * hbitmap_granularity:
  77  * @hb: HBitmap to operate on.
  78  *
  79  * Return the granularity of the HBitmap.
  80  */
  81 int hbitmap_granularity(const HBitmap *hb);
  82
  83 /**
  84  * hbitmap_count:
  85  * @hb: HBitmap to operate on.
  86  *
  87  * Return the number of bits set in the HBitmap.
  88  */
  89 uint64_t hbitmap_count(const HBitmap *hb);
  90
  91 /**
  92  * hbitmap_set:
  93  * @hb: HBitmap to operate on.
  94  * @start: First bit to set (0-based).
  95  * @count: Number of bits to set.
  96  *
  97  * Set a consecutive range of bits in an HBitmap.
  98  */
  99 void hbitmap_set(HBitmap *hb, uint64_t start, uint64_t count);
 100
 101 /**
 102  * hbitmap_reset:
 103  * @hb: HBitmap to operate on.
 104  * @start: First bit to reset (0-based).
 105  * @count: Number of bits to reset.
 106  *
 107  * Reset a consecutive range of bits in an HBitmap.
 108  */
 109 void hbitmap_reset(HBitmap *hb, uint64_t start, uint64_t count);
 110
 111 /**
 112  * hbitmap_get:
 113  * @hb: HBitmap to operate on.
 114  * @item: Bit to query (0-based).
 115  *
 116  * Return whether the @item-th bit in an HBitmap is set.
 117  */
 118 bool hbitmap_get(const HBitmap *hb, uint64_t item);
 119
 120 /**
 121  * hbitmap_free:
 122  * @hb: HBitmap to operate on.
 123  *
 124  * Free an HBitmap and all of its associated memory.
 125  */
 126 void hbitmap_free(HBitmap *hb);
 127
 128 /**
 129  * hbitmap_iter_init:
 130  * @hbi: HBitmapIter to initialize.
 131  * @hb: HBitmap to iterate on.
 132  * @first: First bit to visit (0-based, must be strictly less than the
 133  * size of the bitmap).
 134  *
 135  * Set up @hbi to iterate on the HBitmap @hb.  hbitmap_iter_next will return
 136  * the lowest-numbered bit that is set in @hb, starting at @first.
 137  *
 138  * Concurrent setting of bits is acceptable, and will at worst cause the
 139  * iteration to miss some of those bits.  Resetting bits before the current
 140  * position of the iterator is also okay.  However, concurrent resetting of
 141  * bits can lead to unexpected behavior if the iterator has not yet reached
 142  * those bits.
 143  */
 144 void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first);
 145
 146 /* hbitmap_iter_skip_words:
 147  * @hbi: HBitmapIter to operate on.
 148  *
 149  * Internal function used by hbitmap_iter_next and hbitmap_iter_next_word.
 150  */
 151 unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi);
 152
 153 /**
 154  * hbitmap_iter_next:
 155  * @hbi: HBitmapIter to operate on.
 156  *
 157  * Return the next bit that is set in @hbi's associated HBitmap,
 158  * or -1 if all remaining bits are zero.
 159  */
 160 static inline int64_t hbitmap_iter_next(HBitmapIter *hbi)
 161 {
 162     unsigned long cur = hbi->cur[HBITMAP_LEVELS - 1];
 163     int64_t item;
 164
 165     if (cur == 0) {
 166         cur = hbitmap_iter_skip_words(hbi);
 167         if (cur == 0) {
 168             return -1;
 169         }
 170     }
 171
 172     /* The next call will resume work from the next bit.  */
 173     hbi->cur[HBITMAP_LEVELS - 1] = cur & (cur - 1);
 174     item = ((uint64_t)hbi->pos << BITS_PER_LEVEL) + ctzl(cur);
 175
 176     return item << hbi->granularity;
 177 }
 178
 179 /**
 180  * hbitmap_iter_next_word:
 181  * @hbi: HBitmapIter to operate on.
 182  * @p_cur: Location where to store the next non-zero word.
 183  *
 184  * Return the index of the next nonzero word that is set in @hbi's
 185  * associated HBitmap, and set *p_cur to the content of that word
 186  * (bits before the index that was passed to hbitmap_iter_init are
 187  * trimmed on the first call).  Return -1, and set *p_cur to zero,
 188  * if all remaining words are zero.
 189  */
 190 static inline size_t hbitmap_iter_next_word(HBitmapIter *hbi, unsigned long *p_cur)
 191 {
 192     unsigned long cur = hbi->cur[HBITMAP_LEVELS - 1];
 193
 194     if (cur == 0) {
 195         cur = hbitmap_iter_skip_words(hbi);
 196         if (cur == 0) {
 197             *p_cur = 0;
 198             return -1;
 199         }
 200     }
 201
 202     /* The next call will resume work from the next word.  */
 203     hbi->cur[HBITMAP_LEVELS - 1] = 0;
 204     *p_cur = cur;
 205     return hbi->pos;
 206 }
 207
 208
 209 #endif