hbitmap: move hbitmap_iter_next_word to hbitmap.c
[qemu.git] / 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
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 *
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 */
83 bool 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 */
92 bool 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 */
100 bool 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 */
108 int 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 */
116 uint64_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 */
126 void 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 */
141 void 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 */
149 void 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 */
158 bool 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 */
171 bool 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 */
183 uint64_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 */
193 uint64_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 */
207 void 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 */
224 void 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 */
240 void 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 */
255 void 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 */
265 void 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 */
273 char *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 */
281 void 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 */
298 void 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 */
305 unsigned 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 */
317 int64_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 */
332 bool 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 */
347 HBitmap *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 */
354 void 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 */
363 int64_t hbitmap_iter_next(HBitmapIter *hbi);
364
365 #endif