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 14 15 #include "bitops.h" 16 #include "host-utils.h" 17 18 typedef struct HBitmap HBitmap; 19 typedef struct HBitmapIter HBitmapIter; 20 21 #define BITS_PER_LEVEL (BITS_PER_LONG == 32 ? 5 : 6) 22 23 /* For 32-bit, the largest that fits in a 4 GiB address space. 24 * For 64-bit, the number of sectors in 1 PiB. Good luck, in 25 * either case... :) 26 */ 27 #define HBITMAP_LOG_MAX_SIZE (BITS_PER_LONG == 32 ? 34 : 41) 28 29 /* We need to place a sentinel in level 0 to speed up iteration. Thus, 30 * we do this instead of HBITMAP_LOG_MAX_SIZE / BITS_PER_LEVEL. The 31 * difference is that it allocates an extra level when HBITMAP_LOG_MAX_SIZE 32 * is an exact multiple of BITS_PER_LEVEL. 33 */ 34 #define HBITMAP_LEVELS ((HBITMAP_LOG_MAX_SIZE / BITS_PER_LEVEL) + 1) 35 36 struct HBitmapIter { 37 const HBitmap *hb; 38 39 /* Copied from hb for access in the inline functions (hb is opaque). */ 40 int granularity; 41 42 /* Entry offset into the last-level array of longs. */ 43 size_t pos; 44 45 /* The currently-active path in the tree. Each item of cur[i] stores 46 * the bits (i.e. the subtrees) yet to be processed under that node. 47 */ 48 unsigned long cur[HBITMAP_LEVELS]; 49 }; 50 51 /** 52 * hbitmap_alloc: 53 * @size: Number of bits in the bitmap. 54 * @granularity: Granularity of the bitmap. Aligned groups of 2^@granularity 55 * bits will be represented by a single bit. Each operation on a 56 * range of bits first rounds the bits to determine which group they land 57 * in, and then affect the entire set; iteration will only visit the first 58 * bit of each group. 59 * 60 * Allocate a new HBitmap. 61 */ 62 HBitmap *hbitmap_alloc(uint64_t size, int granularity); 63 64 /** 65 * hbitmap_truncate: 66 * @hb: The bitmap to change the size of. 67 * @size: The number of elements to change the bitmap to accommodate. 68 * 69 * truncate or grow an existing bitmap to accommodate a new number of elements. 70 * This may invalidate existing HBitmapIterators. 71 */ 72 void hbitmap_truncate(HBitmap *hb, uint64_t size); 73 74 /** 75 * hbitmap_merge: 76 * @a: The bitmap to store the result in. 77 * @b: The bitmap to merge into @a. 78 * @return true if the merge was successful, 79 * false if it was not attempted. 80 * 81 * Merge two bitmaps together. 82 * A := A (BITOR) B. 83 * B is left unmodified. 84 */ 85 bool hbitmap_merge(HBitmap *a, const HBitmap *b); 86 87 /** 88 * hbitmap_empty: 89 * @hb: HBitmap to operate on. 90 * 91 * Return whether the bitmap is empty. 92 */ 93 bool hbitmap_empty(const HBitmap *hb); 94 95 /** 96 * hbitmap_granularity: 97 * @hb: HBitmap to operate on. 98 * 99 * Return the granularity of the HBitmap. 100 */ 101 int hbitmap_granularity(const HBitmap *hb); 102 103 /** 104 * hbitmap_count: 105 * @hb: HBitmap to operate on. 106 * 107 * Return the number of bits set in the HBitmap. 108 */ 109 uint64_t hbitmap_count(const HBitmap *hb); 110 111 /** 112 * hbitmap_set: 113 * @hb: HBitmap to operate on. 114 * @start: First bit to set (0-based). 115 * @count: Number of bits to set. 116 * 117 * Set a consecutive range of bits in an HBitmap. 118 */ 119 void hbitmap_set(HBitmap *hb, uint64_t start, uint64_t count); 120 121 /** 122 * hbitmap_reset: 123 * @hb: HBitmap to operate on. 124 * @start: First bit to reset (0-based). 125 * @count: Number of bits to reset. 126 * 127 * Reset a consecutive range of bits in an HBitmap. 128 */ 129 void hbitmap_reset(HBitmap *hb, uint64_t start, uint64_t count); 130 131 /** 132 * hbitmap_reset_all: 133 * @hb: HBitmap to operate on. 134 * 135 * Reset all bits in an HBitmap. 136 */ 137 void hbitmap_reset_all(HBitmap *hb); 138 139 /** 140 * hbitmap_get: 141 * @hb: HBitmap to operate on. 142 * @item: Bit to query (0-based). 143 * 144 * Return whether the @item-th bit in an HBitmap is set. 145 */ 146 bool hbitmap_get(const HBitmap *hb, uint64_t item); 147 148 /** 149 * hbitmap_is_serializable: 150 * @hb: HBitmap which should be (de-)serialized. 151 * 152 * Returns whether the bitmap can actually be (de-)serialized. Other 153 * (de-)serialization functions may only be invoked if this function returns 154 * true. 155 * 156 * Calling (de-)serialization functions does not affect a bitmap's 157 * (de-)serializability. 158 */ 159 bool hbitmap_is_serializable(const HBitmap *hb); 160 161 /** 162 * hbitmap_serialization_align: 163 * @hb: HBitmap to operate on. 164 * 165 * Required alignment of serialization chunks, used by other serialization 166 * functions. For every chunk: 167 * 1. Chunk start should be aligned to this granularity. 168 * 2. Chunk size should be aligned too, except for last chunk (for which 169 * start + count == hb->size) 170 */ 171 uint64_t hbitmap_serialization_align(const HBitmap *hb); 172 173 /** 174 * hbitmap_serialization_size: 175 * @hb: HBitmap to operate on. 176 * @start: Starting bit 177 * @count: Number of bits 178 * 179 * Return number of bytes hbitmap_(de)serialize_part needs 180 */ 181 uint64_t hbitmap_serialization_size(const HBitmap *hb, 182 uint64_t start, uint64_t count); 183 184 /** 185 * hbitmap_serialize_part 186 * @hb: HBitmap to operate on. 187 * @buf: Buffer to store serialized bitmap. 188 * @start: First bit to store. 189 * @count: Number of bits to store. 190 * 191 * Stores HBitmap data corresponding to given region. The format of saved data 192 * is linear sequence of bits, so it can be used by hbitmap_deserialize_part 193 * independently of endianness and size of HBitmap level array elements 194 */ 195 void hbitmap_serialize_part(const HBitmap *hb, uint8_t *buf, 196 uint64_t start, uint64_t count); 197 198 /** 199 * hbitmap_deserialize_part 200 * @hb: HBitmap to operate on. 201 * @buf: Buffer to restore bitmap data from. 202 * @start: First bit to restore. 203 * @count: Number of bits to restore. 204 * @finish: Whether to call hbitmap_deserialize_finish automatically. 205 * 206 * Restores HBitmap data corresponding to given region. The format is the same 207 * as for hbitmap_serialize_part. 208 * 209 * If @finish is false, caller must call hbitmap_serialize_finish before using 210 * the bitmap. 211 */ 212 void hbitmap_deserialize_part(HBitmap *hb, uint8_t *buf, 213 uint64_t start, uint64_t count, 214 bool finish); 215 216 /** 217 * hbitmap_deserialize_zeroes 218 * @hb: HBitmap to operate on. 219 * @start: First bit to restore. 220 * @count: Number of bits to restore. 221 * @finish: Whether to call hbitmap_deserialize_finish automatically. 222 * 223 * Fills the bitmap with zeroes. 224 * 225 * If @finish is false, caller must call hbitmap_serialize_finish before using 226 * the bitmap. 227 */ 228 void hbitmap_deserialize_zeroes(HBitmap *hb, uint64_t start, uint64_t count, 229 bool finish); 230 231 /** 232 * hbitmap_deserialize_ones 233 * @hb: HBitmap to operate on. 234 * @start: First bit to restore. 235 * @count: Number of bits to restore. 236 * @finish: Whether to call hbitmap_deserialize_finish automatically. 237 * 238 * Fills the bitmap with ones. 239 * 240 * If @finish is false, caller must call hbitmap_serialize_finish before using 241 * the bitmap. 242 */ 243 void hbitmap_deserialize_ones(HBitmap *hb, uint64_t start, uint64_t count, 244 bool finish); 245 246 /** 247 * hbitmap_deserialize_finish 248 * @hb: HBitmap to operate on. 249 * 250 * Repair HBitmap after calling hbitmap_deserialize_data. Actually, all HBitmap 251 * layers are restored here. 252 */ 253 void hbitmap_deserialize_finish(HBitmap *hb); 254 255 /** 256 * hbitmap_sha256: 257 * @bitmap: HBitmap to operate on. 258 * 259 * Returns SHA256 hash of the last level. 260 */ 261 char *hbitmap_sha256(const HBitmap *bitmap, Error **errp); 262 263 /** 264 * hbitmap_free: 265 * @hb: HBitmap to operate on. 266 * 267 * Free an HBitmap and all of its associated memory. 268 */ 269 void hbitmap_free(HBitmap *hb); 270 271 /** 272 * hbitmap_iter_init: 273 * @hbi: HBitmapIter to initialize. 274 * @hb: HBitmap to iterate on. 275 * @first: First bit to visit (0-based, must be strictly less than the 276 * size of the bitmap). 277 * 278 * Set up @hbi to iterate on the HBitmap @hb. hbitmap_iter_next will return 279 * the lowest-numbered bit that is set in @hb, starting at @first. 280 * 281 * Concurrent setting of bits is acceptable, and will at worst cause the 282 * iteration to miss some of those bits. 283 * 284 * The concurrent resetting of bits is OK. 285 */ 286 void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first); 287 288 /* hbitmap_iter_skip_words: 289 * @hbi: HBitmapIter to operate on. 290 * 291 * Internal function used by hbitmap_iter_next and hbitmap_iter_next_word. 292 */ 293 unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi); 294 295 /* hbitmap_create_meta: 296 * Create a "meta" hbitmap to track dirtiness of the bits in this HBitmap. 297 * The caller owns the created bitmap and must call hbitmap_free_meta(hb) to 298 * free it. 299 * 300 * Currently, we only guarantee that if a bit in the hbitmap is changed it 301 * will be reflected in the meta bitmap, but we do not yet guarantee the 302 * opposite. 303 * 304 * @hb: The HBitmap to operate on. 305 * @chunk_size: How many bits in @hb does one bit in the meta track. 306 */ 307 HBitmap *hbitmap_create_meta(HBitmap *hb, int chunk_size); 308 309 /* hbitmap_free_meta: 310 * Free the meta bitmap of @hb. 311 * 312 * @hb: The HBitmap whose meta bitmap should be freed. 313 */ 314 void hbitmap_free_meta(HBitmap *hb); 315 316 /** 317 * hbitmap_iter_next: 318 * @hbi: HBitmapIter to operate on. 319 * 320 * Return the next bit that is set in @hbi's associated HBitmap, 321 * or -1 if all remaining bits are zero. 322 */ 323 int64_t hbitmap_iter_next(HBitmapIter *hbi); 324 325 /** 326 * hbitmap_iter_next_word: 327 * @hbi: HBitmapIter to operate on. 328 * @p_cur: Location where to store the next non-zero word. 329 * 330 * Return the index of the next nonzero word that is set in @hbi's 331 * associated HBitmap, and set *p_cur to the content of that word 332 * (bits before the index that was passed to hbitmap_iter_init are 333 * trimmed on the first call). Return -1, and set *p_cur to zero, 334 * if all remaining words are zero. 335 */ 336 static inline size_t hbitmap_iter_next_word(HBitmapIter *hbi, unsigned long *p_cur) 337 { 338 unsigned long cur = hbi->cur[HBITMAP_LEVELS - 1]; 339 340 if (cur == 0) { 341 cur = hbitmap_iter_skip_words(hbi); 342 if (cur == 0) { 343 *p_cur = 0; 344 return -1; 345 } 346 } 347 348 /* The next call will resume work from the next word. */ 349 hbi->cur[HBITMAP_LEVELS - 1] = 0; 350 *p_cur = cur; 351 return hbi->pos; 352 } 353 354 355 #endif 356