1e7c033c3SPaolo Bonzini /* 2e7c033c3SPaolo Bonzini * Hierarchical Bitmap Data Type 3e7c033c3SPaolo Bonzini * 4e7c033c3SPaolo Bonzini * Copyright Red Hat, Inc., 2012 5e7c033c3SPaolo Bonzini * 6e7c033c3SPaolo Bonzini * Author: Paolo Bonzini <pbonzini@redhat.com> 7e7c033c3SPaolo Bonzini * 8e7c033c3SPaolo Bonzini * This work is licensed under the terms of the GNU GPL, version 2 or 9e7c033c3SPaolo Bonzini * later. See the COPYING file in the top-level directory. 10e7c033c3SPaolo Bonzini */ 11e7c033c3SPaolo Bonzini 12e7c033c3SPaolo Bonzini #ifndef HBITMAP_H 13175de524SMarkus Armbruster #define HBITMAP_H 14e7c033c3SPaolo Bonzini 15e7c033c3SPaolo Bonzini #include "bitops.h" 1618331e7cSRichard Henderson #include "host-utils.h" 17e7c033c3SPaolo Bonzini 18e7c033c3SPaolo Bonzini typedef struct HBitmap HBitmap; 19e7c033c3SPaolo Bonzini typedef struct HBitmapIter HBitmapIter; 20e7c033c3SPaolo Bonzini 21e7c033c3SPaolo Bonzini #define BITS_PER_LEVEL (BITS_PER_LONG == 32 ? 5 : 6) 22e7c033c3SPaolo Bonzini 23e7c033c3SPaolo Bonzini /* For 32-bit, the largest that fits in a 4 GiB address space. 24e7c033c3SPaolo Bonzini * For 64-bit, the number of sectors in 1 PiB. Good luck, in 25e7c033c3SPaolo Bonzini * either case... :) 26e7c033c3SPaolo Bonzini */ 27e7c033c3SPaolo Bonzini #define HBITMAP_LOG_MAX_SIZE (BITS_PER_LONG == 32 ? 34 : 41) 28e7c033c3SPaolo Bonzini 29e7c033c3SPaolo Bonzini /* We need to place a sentinel in level 0 to speed up iteration. Thus, 30e7c033c3SPaolo Bonzini * we do this instead of HBITMAP_LOG_MAX_SIZE / BITS_PER_LEVEL. The 31e7c033c3SPaolo Bonzini * difference is that it allocates an extra level when HBITMAP_LOG_MAX_SIZE 32e7c033c3SPaolo Bonzini * is an exact multiple of BITS_PER_LEVEL. 33e7c033c3SPaolo Bonzini */ 34e7c033c3SPaolo Bonzini #define HBITMAP_LEVELS ((HBITMAP_LOG_MAX_SIZE / BITS_PER_LEVEL) + 1) 35e7c033c3SPaolo Bonzini 36e7c033c3SPaolo Bonzini struct HBitmapIter { 37e7c033c3SPaolo Bonzini const HBitmap *hb; 38e7c033c3SPaolo Bonzini 39e7c033c3SPaolo Bonzini /* Copied from hb for access in the inline functions (hb is opaque). */ 40e7c033c3SPaolo Bonzini int granularity; 41e7c033c3SPaolo Bonzini 42e7c033c3SPaolo Bonzini /* Entry offset into the last-level array of longs. */ 43e7c033c3SPaolo Bonzini size_t pos; 44e7c033c3SPaolo Bonzini 45e7c033c3SPaolo Bonzini /* The currently-active path in the tree. Each item of cur[i] stores 46e7c033c3SPaolo Bonzini * the bits (i.e. the subtrees) yet to be processed under that node. 47e7c033c3SPaolo Bonzini */ 48e7c033c3SPaolo Bonzini unsigned long cur[HBITMAP_LEVELS]; 49e7c033c3SPaolo Bonzini }; 50e7c033c3SPaolo Bonzini 51e7c033c3SPaolo Bonzini /** 52e7c033c3SPaolo Bonzini * hbitmap_alloc: 53e7c033c3SPaolo Bonzini * @size: Number of bits in the bitmap. 54e7c033c3SPaolo Bonzini * @granularity: Granularity of the bitmap. Aligned groups of 2^@granularity 55e7c033c3SPaolo Bonzini * bits will be represented by a single bit. Each operation on a 56e7c033c3SPaolo Bonzini * range of bits first rounds the bits to determine which group they land 57e7c033c3SPaolo Bonzini * in, and then affect the entire set; iteration will only visit the first 58e7c033c3SPaolo Bonzini * bit of each group. 59e7c033c3SPaolo Bonzini * 60e7c033c3SPaolo Bonzini * Allocate a new HBitmap. 61e7c033c3SPaolo Bonzini */ 62e7c033c3SPaolo Bonzini HBitmap *hbitmap_alloc(uint64_t size, int granularity); 63e7c033c3SPaolo Bonzini 64e7c033c3SPaolo Bonzini /** 65ce1ffea8SJohn Snow * hbitmap_truncate: 66ce1ffea8SJohn Snow * @hb: The bitmap to change the size of. 67ce1ffea8SJohn Snow * @size: The number of elements to change the bitmap to accommodate. 68ce1ffea8SJohn Snow * 69ce1ffea8SJohn Snow * truncate or grow an existing bitmap to accommodate a new number of elements. 70ce1ffea8SJohn Snow * This may invalidate existing HBitmapIterators. 71ce1ffea8SJohn Snow */ 72ce1ffea8SJohn Snow void hbitmap_truncate(HBitmap *hb, uint64_t size); 73ce1ffea8SJohn Snow 74ce1ffea8SJohn Snow /** 75be58721dSJohn Snow * hbitmap_merge: 76be58721dSJohn Snow * 77fa000f2fSVladimir Sementsov-Ogievskiy * Store result of merging @a and @b into @result. 78fa000f2fSVladimir Sementsov-Ogievskiy * @result is allowed to be equal to @a or @b. 79618af89eSVladimir Sementsov-Ogievskiy * All bitmaps must have same size. 80be58721dSJohn Snow */ 81618af89eSVladimir Sementsov-Ogievskiy void hbitmap_merge(const HBitmap *a, const HBitmap *b, HBitmap *result); 82be58721dSJohn Snow 83be58721dSJohn Snow /** 84e7c033c3SPaolo Bonzini * hbitmap_empty: 85e7c033c3SPaolo Bonzini * @hb: HBitmap to operate on. 86e7c033c3SPaolo Bonzini * 87e7c033c3SPaolo Bonzini * Return whether the bitmap is empty. 88e7c033c3SPaolo Bonzini */ 89e7c033c3SPaolo Bonzini bool hbitmap_empty(const HBitmap *hb); 90e7c033c3SPaolo Bonzini 91e7c033c3SPaolo Bonzini /** 92e7c033c3SPaolo Bonzini * hbitmap_granularity: 93e7c033c3SPaolo Bonzini * @hb: HBitmap to operate on. 94e7c033c3SPaolo Bonzini * 95e7c033c3SPaolo Bonzini * Return the granularity of the HBitmap. 96e7c033c3SPaolo Bonzini */ 97e7c033c3SPaolo Bonzini int hbitmap_granularity(const HBitmap *hb); 98e7c033c3SPaolo Bonzini 99e7c033c3SPaolo Bonzini /** 100e7c033c3SPaolo Bonzini * hbitmap_count: 101e7c033c3SPaolo Bonzini * @hb: HBitmap to operate on. 102e7c033c3SPaolo Bonzini * 103e7c033c3SPaolo Bonzini * Return the number of bits set in the HBitmap. 104e7c033c3SPaolo Bonzini */ 105e7c033c3SPaolo Bonzini uint64_t hbitmap_count(const HBitmap *hb); 106e7c033c3SPaolo Bonzini 107e7c033c3SPaolo Bonzini /** 108e7c033c3SPaolo Bonzini * hbitmap_set: 109e7c033c3SPaolo Bonzini * @hb: HBitmap to operate on. 110e7c033c3SPaolo Bonzini * @start: First bit to set (0-based). 111e7c033c3SPaolo Bonzini * @count: Number of bits to set. 112e7c033c3SPaolo Bonzini * 113e7c033c3SPaolo Bonzini * Set a consecutive range of bits in an HBitmap. 114e7c033c3SPaolo Bonzini */ 115e7c033c3SPaolo Bonzini void hbitmap_set(HBitmap *hb, uint64_t start, uint64_t count); 116e7c033c3SPaolo Bonzini 117e7c033c3SPaolo Bonzini /** 118e7c033c3SPaolo Bonzini * hbitmap_reset: 119e7c033c3SPaolo Bonzini * @hb: HBitmap to operate on. 120e7c033c3SPaolo Bonzini * @start: First bit to reset (0-based). 121e7c033c3SPaolo Bonzini * @count: Number of bits to reset. 122e7c033c3SPaolo Bonzini * 123e7c033c3SPaolo Bonzini * Reset a consecutive range of bits in an HBitmap. 12448557b13SVladimir Sementsov-Ogievskiy * @start and @count must be aligned to bitmap granularity. The only exception 12548557b13SVladimir Sementsov-Ogievskiy * is resetting the tail of the bitmap: @count may be equal to hb->orig_size - 12648557b13SVladimir Sementsov-Ogievskiy * @start, in this case @count may be not aligned. The sum of @start + @count is 12748557b13SVladimir Sementsov-Ogievskiy * allowed to be greater than hb->orig_size, but only if @start < hb->orig_size 12848557b13SVladimir Sementsov-Ogievskiy * and @start + @count = ALIGN_UP(hb->orig_size, granularity). 129e7c033c3SPaolo Bonzini */ 130e7c033c3SPaolo Bonzini void hbitmap_reset(HBitmap *hb, uint64_t start, uint64_t count); 131e7c033c3SPaolo Bonzini 132e7c033c3SPaolo Bonzini /** 133c6a8c328SWen Congyang * hbitmap_reset_all: 134c6a8c328SWen Congyang * @hb: HBitmap to operate on. 135c6a8c328SWen Congyang * 136c6a8c328SWen Congyang * Reset all bits in an HBitmap. 137c6a8c328SWen Congyang */ 138c6a8c328SWen Congyang void hbitmap_reset_all(HBitmap *hb); 139c6a8c328SWen Congyang 140c6a8c328SWen Congyang /** 141e7c033c3SPaolo Bonzini * hbitmap_get: 142e7c033c3SPaolo Bonzini * @hb: HBitmap to operate on. 143e7c033c3SPaolo Bonzini * @item: Bit to query (0-based). 144e7c033c3SPaolo Bonzini * 145e7c033c3SPaolo Bonzini * Return whether the @item-th bit in an HBitmap is set. 146e7c033c3SPaolo Bonzini */ 147e7c033c3SPaolo Bonzini bool hbitmap_get(const HBitmap *hb, uint64_t item); 148e7c033c3SPaolo Bonzini 149e7c033c3SPaolo Bonzini /** 15020a579deSMax Reitz * hbitmap_is_serializable: 15120a579deSMax Reitz * @hb: HBitmap which should be (de-)serialized. 15220a579deSMax Reitz * 15320a579deSMax Reitz * Returns whether the bitmap can actually be (de-)serialized. Other 15420a579deSMax Reitz * (de-)serialization functions may only be invoked if this function returns 15520a579deSMax Reitz * true. 15620a579deSMax Reitz * 15720a579deSMax Reitz * Calling (de-)serialization functions does not affect a bitmap's 15820a579deSMax Reitz * (de-)serializability. 15920a579deSMax Reitz */ 16020a579deSMax Reitz bool hbitmap_is_serializable(const HBitmap *hb); 16120a579deSMax Reitz 16220a579deSMax Reitz /** 163ecbfa281SEric Blake * hbitmap_serialization_align: 1648258888eSVladimir Sementsov-Ogievskiy * @hb: HBitmap to operate on. 1658258888eSVladimir Sementsov-Ogievskiy * 166ecbfa281SEric Blake * Required alignment of serialization chunks, used by other serialization 167ecbfa281SEric Blake * functions. For every chunk: 1688258888eSVladimir Sementsov-Ogievskiy * 1. Chunk start should be aligned to this granularity. 1698258888eSVladimir Sementsov-Ogievskiy * 2. Chunk size should be aligned too, except for last chunk (for which 1708258888eSVladimir Sementsov-Ogievskiy * start + count == hb->size) 1718258888eSVladimir Sementsov-Ogievskiy */ 172ecbfa281SEric Blake uint64_t hbitmap_serialization_align(const HBitmap *hb); 1738258888eSVladimir Sementsov-Ogievskiy 1748258888eSVladimir Sementsov-Ogievskiy /** 1758258888eSVladimir Sementsov-Ogievskiy * hbitmap_serialization_size: 1768258888eSVladimir Sementsov-Ogievskiy * @hb: HBitmap to operate on. 1778258888eSVladimir Sementsov-Ogievskiy * @start: Starting bit 1788258888eSVladimir Sementsov-Ogievskiy * @count: Number of bits 1798258888eSVladimir Sementsov-Ogievskiy * 1808258888eSVladimir Sementsov-Ogievskiy * Return number of bytes hbitmap_(de)serialize_part needs 1818258888eSVladimir Sementsov-Ogievskiy */ 1828258888eSVladimir Sementsov-Ogievskiy uint64_t hbitmap_serialization_size(const HBitmap *hb, 1838258888eSVladimir Sementsov-Ogievskiy uint64_t start, uint64_t count); 1848258888eSVladimir Sementsov-Ogievskiy 1858258888eSVladimir Sementsov-Ogievskiy /** 1868258888eSVladimir Sementsov-Ogievskiy * hbitmap_serialize_part 1878258888eSVladimir Sementsov-Ogievskiy * @hb: HBitmap to operate on. 1888258888eSVladimir Sementsov-Ogievskiy * @buf: Buffer to store serialized bitmap. 1898258888eSVladimir Sementsov-Ogievskiy * @start: First bit to store. 1908258888eSVladimir Sementsov-Ogievskiy * @count: Number of bits to store. 1918258888eSVladimir Sementsov-Ogievskiy * 1928258888eSVladimir Sementsov-Ogievskiy * Stores HBitmap data corresponding to given region. The format of saved data 1938258888eSVladimir Sementsov-Ogievskiy * is linear sequence of bits, so it can be used by hbitmap_deserialize_part 1948258888eSVladimir Sementsov-Ogievskiy * independently of endianness and size of HBitmap level array elements 1958258888eSVladimir Sementsov-Ogievskiy */ 1968258888eSVladimir Sementsov-Ogievskiy void hbitmap_serialize_part(const HBitmap *hb, uint8_t *buf, 1978258888eSVladimir Sementsov-Ogievskiy uint64_t start, uint64_t count); 1988258888eSVladimir Sementsov-Ogievskiy 1998258888eSVladimir Sementsov-Ogievskiy /** 2008258888eSVladimir Sementsov-Ogievskiy * hbitmap_deserialize_part 2018258888eSVladimir Sementsov-Ogievskiy * @hb: HBitmap to operate on. 2028258888eSVladimir Sementsov-Ogievskiy * @buf: Buffer to restore bitmap data from. 2038258888eSVladimir Sementsov-Ogievskiy * @start: First bit to restore. 2048258888eSVladimir Sementsov-Ogievskiy * @count: Number of bits to restore. 2058258888eSVladimir Sementsov-Ogievskiy * @finish: Whether to call hbitmap_deserialize_finish automatically. 2068258888eSVladimir Sementsov-Ogievskiy * 2078258888eSVladimir Sementsov-Ogievskiy * Restores HBitmap data corresponding to given region. The format is the same 2088258888eSVladimir Sementsov-Ogievskiy * as for hbitmap_serialize_part. 2098258888eSVladimir Sementsov-Ogievskiy * 2108258888eSVladimir Sementsov-Ogievskiy * If @finish is false, caller must call hbitmap_serialize_finish before using 2118258888eSVladimir Sementsov-Ogievskiy * the bitmap. 2128258888eSVladimir Sementsov-Ogievskiy */ 2138258888eSVladimir Sementsov-Ogievskiy void hbitmap_deserialize_part(HBitmap *hb, uint8_t *buf, 2148258888eSVladimir Sementsov-Ogievskiy uint64_t start, uint64_t count, 2158258888eSVladimir Sementsov-Ogievskiy bool finish); 2168258888eSVladimir Sementsov-Ogievskiy 2178258888eSVladimir Sementsov-Ogievskiy /** 2188258888eSVladimir Sementsov-Ogievskiy * hbitmap_deserialize_zeroes 2198258888eSVladimir Sementsov-Ogievskiy * @hb: HBitmap to operate on. 2208258888eSVladimir Sementsov-Ogievskiy * @start: First bit to restore. 2218258888eSVladimir Sementsov-Ogievskiy * @count: Number of bits to restore. 2228258888eSVladimir Sementsov-Ogievskiy * @finish: Whether to call hbitmap_deserialize_finish automatically. 2238258888eSVladimir Sementsov-Ogievskiy * 2248258888eSVladimir Sementsov-Ogievskiy * Fills the bitmap with zeroes. 2258258888eSVladimir Sementsov-Ogievskiy * 2268258888eSVladimir Sementsov-Ogievskiy * If @finish is false, caller must call hbitmap_serialize_finish before using 2278258888eSVladimir Sementsov-Ogievskiy * the bitmap. 2288258888eSVladimir Sementsov-Ogievskiy */ 2298258888eSVladimir Sementsov-Ogievskiy void hbitmap_deserialize_zeroes(HBitmap *hb, uint64_t start, uint64_t count, 2308258888eSVladimir Sementsov-Ogievskiy bool finish); 2318258888eSVladimir Sementsov-Ogievskiy 2328258888eSVladimir Sementsov-Ogievskiy /** 2336bdc8b71SVladimir Sementsov-Ogievskiy * hbitmap_deserialize_ones 2346bdc8b71SVladimir Sementsov-Ogievskiy * @hb: HBitmap to operate on. 2356bdc8b71SVladimir Sementsov-Ogievskiy * @start: First bit to restore. 2366bdc8b71SVladimir Sementsov-Ogievskiy * @count: Number of bits to restore. 2376bdc8b71SVladimir Sementsov-Ogievskiy * @finish: Whether to call hbitmap_deserialize_finish automatically. 2386bdc8b71SVladimir Sementsov-Ogievskiy * 2396bdc8b71SVladimir Sementsov-Ogievskiy * Fills the bitmap with ones. 2406bdc8b71SVladimir Sementsov-Ogievskiy * 2416bdc8b71SVladimir Sementsov-Ogievskiy * If @finish is false, caller must call hbitmap_serialize_finish before using 2426bdc8b71SVladimir Sementsov-Ogievskiy * the bitmap. 2436bdc8b71SVladimir Sementsov-Ogievskiy */ 2446bdc8b71SVladimir Sementsov-Ogievskiy void hbitmap_deserialize_ones(HBitmap *hb, uint64_t start, uint64_t count, 2456bdc8b71SVladimir Sementsov-Ogievskiy bool finish); 2466bdc8b71SVladimir Sementsov-Ogievskiy 2476bdc8b71SVladimir Sementsov-Ogievskiy /** 2488258888eSVladimir Sementsov-Ogievskiy * hbitmap_deserialize_finish 2498258888eSVladimir Sementsov-Ogievskiy * @hb: HBitmap to operate on. 2508258888eSVladimir Sementsov-Ogievskiy * 2518258888eSVladimir Sementsov-Ogievskiy * Repair HBitmap after calling hbitmap_deserialize_data. Actually, all HBitmap 2528258888eSVladimir Sementsov-Ogievskiy * layers are restored here. 2538258888eSVladimir Sementsov-Ogievskiy */ 2548258888eSVladimir Sementsov-Ogievskiy void hbitmap_deserialize_finish(HBitmap *hb); 2558258888eSVladimir Sementsov-Ogievskiy 2568258888eSVladimir Sementsov-Ogievskiy /** 257a3b52535SVladimir Sementsov-Ogievskiy * hbitmap_sha256: 258a3b52535SVladimir Sementsov-Ogievskiy * @bitmap: HBitmap to operate on. 259a3b52535SVladimir Sementsov-Ogievskiy * 260a3b52535SVladimir Sementsov-Ogievskiy * Returns SHA256 hash of the last level. 261a3b52535SVladimir Sementsov-Ogievskiy */ 262a3b52535SVladimir Sementsov-Ogievskiy char *hbitmap_sha256(const HBitmap *bitmap, Error **errp); 263a3b52535SVladimir Sementsov-Ogievskiy 264a3b52535SVladimir Sementsov-Ogievskiy /** 265e7c033c3SPaolo Bonzini * hbitmap_free: 266e7c033c3SPaolo Bonzini * @hb: HBitmap to operate on. 267e7c033c3SPaolo Bonzini * 268e7c033c3SPaolo Bonzini * Free an HBitmap and all of its associated memory. 269e7c033c3SPaolo Bonzini */ 270e7c033c3SPaolo Bonzini void hbitmap_free(HBitmap *hb); 271e7c033c3SPaolo Bonzini 272e7c033c3SPaolo Bonzini /** 273e7c033c3SPaolo Bonzini * hbitmap_iter_init: 274e7c033c3SPaolo Bonzini * @hbi: HBitmapIter to initialize. 275e7c033c3SPaolo Bonzini * @hb: HBitmap to iterate on. 2761b095244SPaolo Bonzini * @first: First bit to visit (0-based, must be strictly less than the 2771b095244SPaolo Bonzini * size of the bitmap). 278e7c033c3SPaolo Bonzini * 279e7c033c3SPaolo Bonzini * Set up @hbi to iterate on the HBitmap @hb. hbitmap_iter_next will return 280e7c033c3SPaolo Bonzini * the lowest-numbered bit that is set in @hb, starting at @first. 281e7c033c3SPaolo Bonzini * 282e7c033c3SPaolo Bonzini * Concurrent setting of bits is acceptable, and will at worst cause the 283f63ea4e9SVladimir Sementsov-Ogievskiy * iteration to miss some of those bits. 284f63ea4e9SVladimir Sementsov-Ogievskiy * 285f63ea4e9SVladimir Sementsov-Ogievskiy * The concurrent resetting of bits is OK. 286e7c033c3SPaolo Bonzini */ 287e7c033c3SPaolo Bonzini void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first); 288e7c033c3SPaolo Bonzini 2899399c54bSVladimir Sementsov-Ogievskiy /* 2909399c54bSVladimir Sementsov-Ogievskiy * hbitmap_next_dirty: 2919399c54bSVladimir Sementsov-Ogievskiy * 2929399c54bSVladimir Sementsov-Ogievskiy * Find next dirty bit within selected range. If not found, return -1. 2939399c54bSVladimir Sementsov-Ogievskiy * 2949399c54bSVladimir Sementsov-Ogievskiy * @hb: The HBitmap to operate on 2959399c54bSVladimir Sementsov-Ogievskiy * @start: The bit to start from. 2969399c54bSVladimir Sementsov-Ogievskiy * @count: Number of bits to proceed. If @start+@count > bitmap size, the whole 2979399c54bSVladimir Sementsov-Ogievskiy * bitmap is looked through. You can use INT64_MAX as @count to search up to 2989399c54bSVladimir Sementsov-Ogievskiy * the bitmap end. 2999399c54bSVladimir Sementsov-Ogievskiy */ 3009399c54bSVladimir Sementsov-Ogievskiy int64_t hbitmap_next_dirty(const HBitmap *hb, int64_t start, int64_t count); 3019399c54bSVladimir Sementsov-Ogievskiy 30256207df5SVladimir Sementsov-Ogievskiy /* hbitmap_next_zero: 30376d570dcSVladimir Sementsov-Ogievskiy * 30476d570dcSVladimir Sementsov-Ogievskiy * Find next not dirty bit within selected range. If not found, return -1. 30576d570dcSVladimir Sementsov-Ogievskiy * 30656207df5SVladimir Sementsov-Ogievskiy * @hb: The HBitmap to operate on 30756207df5SVladimir Sementsov-Ogievskiy * @start: The bit to start from. 30876d570dcSVladimir Sementsov-Ogievskiy * @count: Number of bits to proceed. If @start+@count > bitmap size, the whole 309642700fdSVladimir Sementsov-Ogievskiy * bitmap is looked through. You can use INT64_MAX as @count to search up to 31076d570dcSVladimir Sementsov-Ogievskiy * the bitmap end. 31156207df5SVladimir Sementsov-Ogievskiy */ 312642700fdSVladimir Sementsov-Ogievskiy int64_t hbitmap_next_zero(const HBitmap *hb, int64_t start, int64_t count); 31356207df5SVladimir Sementsov-Ogievskiy 314a78a1a48SVladimir Sementsov-Ogievskiy /* hbitmap_next_dirty_area: 315a78a1a48SVladimir Sementsov-Ogievskiy * @hb: The HBitmap to operate on 316299ea9ffSVladimir Sementsov-Ogievskiy * @start: the offset to start from 317299ea9ffSVladimir Sementsov-Ogievskiy * @end: end of requested area 318299ea9ffSVladimir Sementsov-Ogievskiy * @max_dirty_count: limit for out parameter dirty_count 319299ea9ffSVladimir Sementsov-Ogievskiy * @dirty_start: on success: start of found area 320299ea9ffSVladimir Sementsov-Ogievskiy * @dirty_count: on success: length of found area 321a78a1a48SVladimir Sementsov-Ogievskiy * 322299ea9ffSVladimir Sementsov-Ogievskiy * If dirty area found within [@start, @end), returns true and sets 323299ea9ffSVladimir Sementsov-Ogievskiy * @dirty_start and @dirty_count appropriately. @dirty_count will not exceed 324299ea9ffSVladimir Sementsov-Ogievskiy * @max_dirty_count. 325299ea9ffSVladimir Sementsov-Ogievskiy * If dirty area was not found, returns false and leaves @dirty_start and 326299ea9ffSVladimir Sementsov-Ogievskiy * @dirty_count unchanged. 327a78a1a48SVladimir Sementsov-Ogievskiy */ 328299ea9ffSVladimir Sementsov-Ogievskiy bool hbitmap_next_dirty_area(const HBitmap *hb, int64_t start, int64_t end, 329299ea9ffSVladimir Sementsov-Ogievskiy int64_t max_dirty_count, 330299ea9ffSVladimir Sementsov-Ogievskiy int64_t *dirty_start, int64_t *dirty_count); 331a78a1a48SVladimir Sementsov-Ogievskiy 332a6426475SVladimir Sementsov-Ogievskiy /* 333*a4d5224cSAndrey Zhadchenko * hbitmap_status: 334a6426475SVladimir Sementsov-Ogievskiy * @hb: The HBitmap to operate on 335a6426475SVladimir Sementsov-Ogievskiy * @start: The bit to start from 336a6426475SVladimir Sementsov-Ogievskiy * @count: Number of bits to proceed 337a6426475SVladimir Sementsov-Ogievskiy * @pnum: Out-parameter. How many bits has same value starting from @start 338a6426475SVladimir Sementsov-Ogievskiy * 339a6426475SVladimir Sementsov-Ogievskiy * Returns true if bitmap is dirty at @start, false otherwise. 340a6426475SVladimir Sementsov-Ogievskiy */ 341a6426475SVladimir Sementsov-Ogievskiy bool hbitmap_status(const HBitmap *hb, int64_t start, int64_t count, 342a6426475SVladimir Sementsov-Ogievskiy int64_t *pnum); 343a6426475SVladimir Sementsov-Ogievskiy 344e7c033c3SPaolo Bonzini /** 345e7c033c3SPaolo Bonzini * hbitmap_iter_next: 346e7c033c3SPaolo Bonzini * @hbi: HBitmapIter to operate on. 347e7c033c3SPaolo Bonzini * 348e7c033c3SPaolo Bonzini * Return the next bit that is set in @hbi's associated HBitmap, 349e7c033c3SPaolo Bonzini * or -1 if all remaining bits are zero. 350e7c033c3SPaolo Bonzini */ 35119c021e1SVladimir Sementsov-Ogievskiy int64_t hbitmap_iter_next(HBitmapIter *hbi); 352e7c033c3SPaolo Bonzini 353e7c033c3SPaolo Bonzini #endif 354