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