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 18typedef struct HBitmap HBitmap; 19typedef 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 36struct 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 */ 62HBitmap *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 */ 72void hbitmap_truncate(HBitmap *hb, uint64_t size); 73 74/** 75 * hbitmap_merge: 76 * 77 * Store result of merging @a and @b into @result. 78 * @result is allowed to be equal to @a or @b. 79 * 80 * Return true if the merge was successful, 81 * false if it was not attempted. 82 */ 83bool hbitmap_merge(const HBitmap *a, const HBitmap *b, HBitmap *result); 84 85/** 86 * hbitmap_can_merge: 87 * 88 * hbitmap_can_merge(a, b) && hbitmap_can_merge(a, result) is sufficient and 89 * necessary for hbitmap_merge will not fail. 90 * 91 */ 92bool hbitmap_can_merge(const HBitmap *a, const HBitmap *b); 93 94/** 95 * hbitmap_empty: 96 * @hb: HBitmap to operate on. 97 * 98 * Return whether the bitmap is empty. 99 */ 100bool hbitmap_empty(const HBitmap *hb); 101 102/** 103 * hbitmap_granularity: 104 * @hb: HBitmap to operate on. 105 * 106 * Return the granularity of the HBitmap. 107 */ 108int hbitmap_granularity(const HBitmap *hb); 109 110/** 111 * hbitmap_count: 112 * @hb: HBitmap to operate on. 113 * 114 * Return the number of bits set in the HBitmap. 115 */ 116uint64_t hbitmap_count(const HBitmap *hb); 117 118/** 119 * hbitmap_set: 120 * @hb: HBitmap to operate on. 121 * @start: First bit to set (0-based). 122 * @count: Number of bits to set. 123 * 124 * Set a consecutive range of bits in an HBitmap. 125 */ 126void hbitmap_set(HBitmap *hb, uint64_t start, uint64_t count); 127 128/** 129 * hbitmap_reset: 130 * @hb: HBitmap to operate on. 131 * @start: First bit to reset (0-based). 132 * @count: Number of bits to reset. 133 * 134 * Reset a consecutive range of bits in an HBitmap. 135 */ 136void hbitmap_reset(HBitmap *hb, uint64_t start, uint64_t count); 137 138/** 139 * hbitmap_reset_all: 140 * @hb: HBitmap to operate on. 141 * 142 * Reset all bits in an HBitmap. 143 */ 144void hbitmap_reset_all(HBitmap *hb); 145 146/** 147 * hbitmap_get: 148 * @hb: HBitmap to operate on. 149 * @item: Bit to query (0-based). 150 * 151 * Return whether the @item-th bit in an HBitmap is set. 152 */ 153bool hbitmap_get(const HBitmap *hb, uint64_t item); 154 155/** 156 * hbitmap_is_serializable: 157 * @hb: HBitmap which should be (de-)serialized. 158 * 159 * Returns whether the bitmap can actually be (de-)serialized. Other 160 * (de-)serialization functions may only be invoked if this function returns 161 * true. 162 * 163 * Calling (de-)serialization functions does not affect a bitmap's 164 * (de-)serializability. 165 */ 166bool hbitmap_is_serializable(const HBitmap *hb); 167 168/** 169 * hbitmap_serialization_align: 170 * @hb: HBitmap to operate on. 171 * 172 * Required alignment of serialization chunks, used by other serialization 173 * functions. For every chunk: 174 * 1. Chunk start should be aligned to this granularity. 175 * 2. Chunk size should be aligned too, except for last chunk (for which 176 * start + count == hb->size) 177 */ 178uint64_t hbitmap_serialization_align(const HBitmap *hb); 179 180/** 181 * hbitmap_serialization_size: 182 * @hb: HBitmap to operate on. 183 * @start: Starting bit 184 * @count: Number of bits 185 * 186 * Return number of bytes hbitmap_(de)serialize_part needs 187 */ 188uint64_t hbitmap_serialization_size(const HBitmap *hb, 189 uint64_t start, uint64_t count); 190 191/** 192 * hbitmap_serialize_part 193 * @hb: HBitmap to operate on. 194 * @buf: Buffer to store serialized bitmap. 195 * @start: First bit to store. 196 * @count: Number of bits to store. 197 * 198 * Stores HBitmap data corresponding to given region. The format of saved data 199 * is linear sequence of bits, so it can be used by hbitmap_deserialize_part 200 * independently of endianness and size of HBitmap level array elements 201 */ 202void hbitmap_serialize_part(const HBitmap *hb, uint8_t *buf, 203 uint64_t start, uint64_t count); 204 205/** 206 * hbitmap_deserialize_part 207 * @hb: HBitmap to operate on. 208 * @buf: Buffer to restore bitmap data from. 209 * @start: First bit to restore. 210 * @count: Number of bits to restore. 211 * @finish: Whether to call hbitmap_deserialize_finish automatically. 212 * 213 * Restores HBitmap data corresponding to given region. The format is the same 214 * as for hbitmap_serialize_part. 215 * 216 * If @finish is false, caller must call hbitmap_serialize_finish before using 217 * the bitmap. 218 */ 219void hbitmap_deserialize_part(HBitmap *hb, uint8_t *buf, 220 uint64_t start, uint64_t count, 221 bool finish); 222 223/** 224 * hbitmap_deserialize_zeroes 225 * @hb: HBitmap to operate on. 226 * @start: First bit to restore. 227 * @count: Number of bits to restore. 228 * @finish: Whether to call hbitmap_deserialize_finish automatically. 229 * 230 * Fills the bitmap with zeroes. 231 * 232 * If @finish is false, caller must call hbitmap_serialize_finish before using 233 * the bitmap. 234 */ 235void hbitmap_deserialize_zeroes(HBitmap *hb, uint64_t start, uint64_t count, 236 bool finish); 237 238/** 239 * hbitmap_deserialize_ones 240 * @hb: HBitmap to operate on. 241 * @start: First bit to restore. 242 * @count: Number of bits to restore. 243 * @finish: Whether to call hbitmap_deserialize_finish automatically. 244 * 245 * Fills the bitmap with ones. 246 * 247 * If @finish is false, caller must call hbitmap_serialize_finish before using 248 * the bitmap. 249 */ 250void hbitmap_deserialize_ones(HBitmap *hb, uint64_t start, uint64_t count, 251 bool finish); 252 253/** 254 * hbitmap_deserialize_finish 255 * @hb: HBitmap to operate on. 256 * 257 * Repair HBitmap after calling hbitmap_deserialize_data. Actually, all HBitmap 258 * layers are restored here. 259 */ 260void hbitmap_deserialize_finish(HBitmap *hb); 261 262/** 263 * hbitmap_sha256: 264 * @bitmap: HBitmap to operate on. 265 * 266 * Returns SHA256 hash of the last level. 267 */ 268char *hbitmap_sha256(const HBitmap *bitmap, Error **errp); 269 270/** 271 * hbitmap_free: 272 * @hb: HBitmap to operate on. 273 * 274 * Free an HBitmap and all of its associated memory. 275 */ 276void hbitmap_free(HBitmap *hb); 277 278/** 279 * hbitmap_iter_init: 280 * @hbi: HBitmapIter to initialize. 281 * @hb: HBitmap to iterate on. 282 * @first: First bit to visit (0-based, must be strictly less than the 283 * size of the bitmap). 284 * 285 * Set up @hbi to iterate on the HBitmap @hb. hbitmap_iter_next will return 286 * the lowest-numbered bit that is set in @hb, starting at @first. 287 * 288 * Concurrent setting of bits is acceptable, and will at worst cause the 289 * iteration to miss some of those bits. 290 * 291 * The concurrent resetting of bits is OK. 292 */ 293void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first); 294 295/* hbitmap_iter_skip_words: 296 * @hbi: HBitmapIter to operate on. 297 * 298 * Internal function used by hbitmap_iter_next and hbitmap_iter_next_word. 299 */ 300unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi); 301 302/* hbitmap_next_zero: 303 * 304 * Find next not dirty bit within selected range. If not found, return -1. 305 * 306 * @hb: The HBitmap to operate on 307 * @start: The bit to start from. 308 * @count: Number of bits to proceed. If @start+@count > bitmap size, the whole 309 * bitmap is looked through. You can use UINT64_MAX as @count to search up to 310 * the bitmap end. 311 */ 312int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start, uint64_t count); 313 314/* hbitmap_next_dirty_area: 315 * @hb: The HBitmap to operate on 316 * @start: in-out parameter. 317 * in: the offset to start from 318 * out: (if area found) start of found area 319 * @count: in-out parameter. 320 * in: length of requested region 321 * out: length of found area 322 * 323 * If dirty area found within [@start, @start + @count), returns true and sets 324 * @offset and @bytes appropriately. Otherwise returns false and leaves @offset 325 * and @bytes unchanged. 326 */ 327bool hbitmap_next_dirty_area(const HBitmap *hb, uint64_t *start, 328 uint64_t *count); 329 330/* hbitmap_create_meta: 331 * Create a "meta" hbitmap to track dirtiness of the bits in this HBitmap. 332 * The caller owns the created bitmap and must call hbitmap_free_meta(hb) to 333 * free it. 334 * 335 * Currently, we only guarantee that if a bit in the hbitmap is changed it 336 * will be reflected in the meta bitmap, but we do not yet guarantee the 337 * opposite. 338 * 339 * @hb: The HBitmap to operate on. 340 * @chunk_size: How many bits in @hb does one bit in the meta track. 341 */ 342HBitmap *hbitmap_create_meta(HBitmap *hb, int chunk_size); 343 344/* hbitmap_free_meta: 345 * Free the meta bitmap of @hb. 346 * 347 * @hb: The HBitmap whose meta bitmap should be freed. 348 */ 349void hbitmap_free_meta(HBitmap *hb); 350 351/** 352 * hbitmap_iter_next: 353 * @hbi: HBitmapIter to operate on. 354 * 355 * Return the next bit that is set in @hbi's associated HBitmap, 356 * or -1 if all remaining bits are zero. 357 */ 358int64_t hbitmap_iter_next(HBitmapIter *hbi); 359 360/** 361 * hbitmap_iter_next_word: 362 * @hbi: HBitmapIter to operate on. 363 * @p_cur: Location where to store the next non-zero word. 364 * 365 * Return the index of the next nonzero word that is set in @hbi's 366 * associated HBitmap, and set *p_cur to the content of that word 367 * (bits before the index that was passed to hbitmap_iter_init are 368 * trimmed on the first call). Return -1, and set *p_cur to zero, 369 * if all remaining words are zero. 370 */ 371static inline size_t hbitmap_iter_next_word(HBitmapIter *hbi, unsigned long *p_cur) 372{ 373 unsigned long cur = hbi->cur[HBITMAP_LEVELS - 1]; 374 375 if (cur == 0) { 376 cur = hbitmap_iter_skip_words(hbi); 377 if (cur == 0) { 378 *p_cur = 0; 379 return -1; 380 } 381 } 382 383 /* The next call will resume work from the next word. */ 384 hbi->cur[HBITMAP_LEVELS - 1] = 0; 385 *p_cur = cur; 386 return hbi->pos; 387} 388 389 390#endif 391