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