Postcopy: Add stats on page requests
[qemu.git] / util / hbitmap.c
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 #include "qemu/osdep.h"
13 #include "qemu/hbitmap.h"
14 #include "qemu/host-utils.h"
15 #include "trace.h"
16
17 /* HBitmaps provides an array of bits. The bits are stored as usual in an
18 * array of unsigned longs, but HBitmap is also optimized to provide fast
19 * iteration over set bits; going from one bit to the next is O(logB n)
20 * worst case, with B = sizeof(long) * CHAR_BIT: the result is low enough
21 * that the number of levels is in fact fixed.
22 *
23 * In order to do this, it stacks multiple bitmaps with progressively coarser
24 * granularity; in all levels except the last, bit N is set iff the N-th
25 * unsigned long is nonzero in the immediately next level. When iteration
26 * completes on the last level it can examine the 2nd-last level to quickly
27 * skip entire words, and even do so recursively to skip blocks of 64 words or
28 * powers thereof (32 on 32-bit machines).
29 *
30 * Given an index in the bitmap, it can be split in group of bits like
31 * this (for the 64-bit case):
32 *
33 * bits 0-57 => word in the last bitmap | bits 58-63 => bit in the word
34 * bits 0-51 => word in the 2nd-last bitmap | bits 52-57 => bit in the word
35 * bits 0-45 => word in the 3rd-last bitmap | bits 46-51 => bit in the word
36 *
37 * So it is easy to move up simply by shifting the index right by
38 * log2(BITS_PER_LONG) bits. To move down, you shift the index left
39 * similarly, and add the word index within the group. Iteration uses
40 * ffs (find first set bit) to find the next word to examine; this
41 * operation can be done in constant time in most current architectures.
42 *
43 * Setting or clearing a range of m bits on all levels, the work to perform
44 * is O(m + m/W + m/W^2 + ...), which is O(m) like on a regular bitmap.
45 *
46 * When iterating on a bitmap, each bit (on any level) is only visited
47 * once. Hence, The total cost of visiting a bitmap with m bits in it is
48 * the number of bits that are set in all bitmaps. Unless the bitmap is
49 * extremely sparse, this is also O(m + m/W + m/W^2 + ...), so the amortized
50 * cost of advancing from one bit to the next is usually constant (worst case
51 * O(logB n) as in the non-amortized complexity).
52 */
53
54 struct HBitmap {
55 /* Number of total bits in the bottom level. */
56 uint64_t size;
57
58 /* Number of set bits in the bottom level. */
59 uint64_t count;
60
61 /* A scaling factor. Given a granularity of G, each bit in the bitmap will
62 * will actually represent a group of 2^G elements. Each operation on a
63 * range of bits first rounds the bits to determine which group they land
64 * in, and then affect the entire page; iteration will only visit the first
65 * bit of each group. Here is an example of operations in a size-16,
66 * granularity-1 HBitmap:
67 *
68 * initial state 00000000
69 * set(start=0, count=9) 11111000 (iter: 0, 2, 4, 6, 8)
70 * reset(start=1, count=3) 00111000 (iter: 4, 6, 8)
71 * set(start=9, count=2) 00111100 (iter: 4, 6, 8, 10)
72 * reset(start=5, count=5) 00000000
73 *
74 * From an implementation point of view, when setting or resetting bits,
75 * the bitmap will scale bit numbers right by this amount of bits. When
76 * iterating, the bitmap will scale bit numbers left by this amount of
77 * bits.
78 */
79 int granularity;
80
81 /* A number of progressively less coarse bitmaps (i.e. level 0 is the
82 * coarsest). Each bit in level N represents a word in level N+1 that
83 * has a set bit, except the last level where each bit represents the
84 * actual bitmap.
85 *
86 * Note that all bitmaps have the same number of levels. Even a 1-bit
87 * bitmap will still allocate HBITMAP_LEVELS arrays.
88 */
89 unsigned long *levels[HBITMAP_LEVELS];
90
91 /* The length of each levels[] array. */
92 uint64_t sizes[HBITMAP_LEVELS];
93 };
94
95 /* Advance hbi to the next nonzero word and return it. hbi->pos
96 * is updated. Returns zero if we reach the end of the bitmap.
97 */
98 unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi)
99 {
100 size_t pos = hbi->pos;
101 const HBitmap *hb = hbi->hb;
102 unsigned i = HBITMAP_LEVELS - 1;
103
104 unsigned long cur;
105 do {
106 cur = hbi->cur[--i];
107 pos >>= BITS_PER_LEVEL;
108 } while (cur == 0);
109
110 /* Check for end of iteration. We always use fewer than BITS_PER_LONG
111 * bits in the level 0 bitmap; thus we can repurpose the most significant
112 * bit as a sentinel. The sentinel is set in hbitmap_alloc and ensures
113 * that the above loop ends even without an explicit check on i.
114 */
115
116 if (i == 0 && cur == (1UL << (BITS_PER_LONG - 1))) {
117 return 0;
118 }
119 for (; i < HBITMAP_LEVELS - 1; i++) {
120 /* Shift back pos to the left, matching the right shifts above.
121 * The index of this word's least significant set bit provides
122 * the low-order bits.
123 */
124 assert(cur);
125 pos = (pos << BITS_PER_LEVEL) + ctzl(cur);
126 hbi->cur[i] = cur & (cur - 1);
127
128 /* Set up next level for iteration. */
129 cur = hb->levels[i + 1][pos];
130 }
131
132 hbi->pos = pos;
133 trace_hbitmap_iter_skip_words(hbi->hb, hbi, pos, cur);
134
135 assert(cur);
136 return cur;
137 }
138
139 void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first)
140 {
141 unsigned i, bit;
142 uint64_t pos;
143
144 hbi->hb = hb;
145 pos = first >> hb->granularity;
146 assert(pos < hb->size);
147 hbi->pos = pos >> BITS_PER_LEVEL;
148 hbi->granularity = hb->granularity;
149
150 for (i = HBITMAP_LEVELS; i-- > 0; ) {
151 bit = pos & (BITS_PER_LONG - 1);
152 pos >>= BITS_PER_LEVEL;
153
154 /* Drop bits representing items before first. */
155 hbi->cur[i] = hb->levels[i][pos] & ~((1UL << bit) - 1);
156
157 /* We have already added level i+1, so the lowest set bit has
158 * been processed. Clear it.
159 */
160 if (i != HBITMAP_LEVELS - 1) {
161 hbi->cur[i] &= ~(1UL << bit);
162 }
163 }
164 }
165
166 bool hbitmap_empty(const HBitmap *hb)
167 {
168 return hb->count == 0;
169 }
170
171 int hbitmap_granularity(const HBitmap *hb)
172 {
173 return hb->granularity;
174 }
175
176 uint64_t hbitmap_count(const HBitmap *hb)
177 {
178 return hb->count << hb->granularity;
179 }
180
181 /* Count the number of set bits between start and end, not accounting for
182 * the granularity. Also an example of how to use hbitmap_iter_next_word.
183 */
184 static uint64_t hb_count_between(HBitmap *hb, uint64_t start, uint64_t last)
185 {
186 HBitmapIter hbi;
187 uint64_t count = 0;
188 uint64_t end = last + 1;
189 unsigned long cur;
190 size_t pos;
191
192 hbitmap_iter_init(&hbi, hb, start << hb->granularity);
193 for (;;) {
194 pos = hbitmap_iter_next_word(&hbi, &cur);
195 if (pos >= (end >> BITS_PER_LEVEL)) {
196 break;
197 }
198 count += ctpopl(cur);
199 }
200
201 if (pos == (end >> BITS_PER_LEVEL)) {
202 /* Drop bits representing the END-th and subsequent items. */
203 int bit = end & (BITS_PER_LONG - 1);
204 cur &= (1UL << bit) - 1;
205 count += ctpopl(cur);
206 }
207
208 return count;
209 }
210
211 /* Setting starts at the last layer and propagates up if an element
212 * changes from zero to non-zero.
213 */
214 static inline bool hb_set_elem(unsigned long *elem, uint64_t start, uint64_t last)
215 {
216 unsigned long mask;
217 bool changed;
218
219 assert((last >> BITS_PER_LEVEL) == (start >> BITS_PER_LEVEL));
220 assert(start <= last);
221
222 mask = 2UL << (last & (BITS_PER_LONG - 1));
223 mask -= 1UL << (start & (BITS_PER_LONG - 1));
224 changed = (*elem == 0);
225 *elem |= mask;
226 return changed;
227 }
228
229 /* The recursive workhorse (the depth is limited to HBITMAP_LEVELS)... */
230 static void hb_set_between(HBitmap *hb, int level, uint64_t start, uint64_t last)
231 {
232 size_t pos = start >> BITS_PER_LEVEL;
233 size_t lastpos = last >> BITS_PER_LEVEL;
234 bool changed = false;
235 size_t i;
236
237 i = pos;
238 if (i < lastpos) {
239 uint64_t next = (start | (BITS_PER_LONG - 1)) + 1;
240 changed |= hb_set_elem(&hb->levels[level][i], start, next - 1);
241 for (;;) {
242 start = next;
243 next += BITS_PER_LONG;
244 if (++i == lastpos) {
245 break;
246 }
247 changed |= (hb->levels[level][i] == 0);
248 hb->levels[level][i] = ~0UL;
249 }
250 }
251 changed |= hb_set_elem(&hb->levels[level][i], start, last);
252
253 /* If there was any change in this layer, we may have to update
254 * the one above.
255 */
256 if (level > 0 && changed) {
257 hb_set_between(hb, level - 1, pos, lastpos);
258 }
259 }
260
261 void hbitmap_set(HBitmap *hb, uint64_t start, uint64_t count)
262 {
263 /* Compute range in the last layer. */
264 uint64_t last = start + count - 1;
265
266 trace_hbitmap_set(hb, start, count,
267 start >> hb->granularity, last >> hb->granularity);
268
269 start >>= hb->granularity;
270 last >>= hb->granularity;
271 count = last - start + 1;
272
273 hb->count += count - hb_count_between(hb, start, last);
274 hb_set_between(hb, HBITMAP_LEVELS - 1, start, last);
275 }
276
277 /* Resetting works the other way round: propagate up if the new
278 * value is zero.
279 */
280 static inline bool hb_reset_elem(unsigned long *elem, uint64_t start, uint64_t last)
281 {
282 unsigned long mask;
283 bool blanked;
284
285 assert((last >> BITS_PER_LEVEL) == (start >> BITS_PER_LEVEL));
286 assert(start <= last);
287
288 mask = 2UL << (last & (BITS_PER_LONG - 1));
289 mask -= 1UL << (start & (BITS_PER_LONG - 1));
290 blanked = *elem != 0 && ((*elem & ~mask) == 0);
291 *elem &= ~mask;
292 return blanked;
293 }
294
295 /* The recursive workhorse (the depth is limited to HBITMAP_LEVELS)... */
296 static void hb_reset_between(HBitmap *hb, int level, uint64_t start, uint64_t last)
297 {
298 size_t pos = start >> BITS_PER_LEVEL;
299 size_t lastpos = last >> BITS_PER_LEVEL;
300 bool changed = false;
301 size_t i;
302
303 i = pos;
304 if (i < lastpos) {
305 uint64_t next = (start | (BITS_PER_LONG - 1)) + 1;
306
307 /* Here we need a more complex test than when setting bits. Even if
308 * something was changed, we must not blank bits in the upper level
309 * unless the lower-level word became entirely zero. So, remove pos
310 * from the upper-level range if bits remain set.
311 */
312 if (hb_reset_elem(&hb->levels[level][i], start, next - 1)) {
313 changed = true;
314 } else {
315 pos++;
316 }
317
318 for (;;) {
319 start = next;
320 next += BITS_PER_LONG;
321 if (++i == lastpos) {
322 break;
323 }
324 changed |= (hb->levels[level][i] != 0);
325 hb->levels[level][i] = 0UL;
326 }
327 }
328
329 /* Same as above, this time for lastpos. */
330 if (hb_reset_elem(&hb->levels[level][i], start, last)) {
331 changed = true;
332 } else {
333 lastpos--;
334 }
335
336 if (level > 0 && changed) {
337 hb_reset_between(hb, level - 1, pos, lastpos);
338 }
339 }
340
341 void hbitmap_reset(HBitmap *hb, uint64_t start, uint64_t count)
342 {
343 /* Compute range in the last layer. */
344 uint64_t last = start + count - 1;
345
346 trace_hbitmap_reset(hb, start, count,
347 start >> hb->granularity, last >> hb->granularity);
348
349 start >>= hb->granularity;
350 last >>= hb->granularity;
351
352 hb->count -= hb_count_between(hb, start, last);
353 hb_reset_between(hb, HBITMAP_LEVELS - 1, start, last);
354 }
355
356 void hbitmap_reset_all(HBitmap *hb)
357 {
358 unsigned int i;
359
360 /* Same as hbitmap_alloc() except for memset() instead of malloc() */
361 for (i = HBITMAP_LEVELS; --i >= 1; ) {
362 memset(hb->levels[i], 0, hb->sizes[i] * sizeof(unsigned long));
363 }
364
365 hb->levels[0][0] = 1UL << (BITS_PER_LONG - 1);
366 hb->count = 0;
367 }
368
369 bool hbitmap_get(const HBitmap *hb, uint64_t item)
370 {
371 /* Compute position and bit in the last layer. */
372 uint64_t pos = item >> hb->granularity;
373 unsigned long bit = 1UL << (pos & (BITS_PER_LONG - 1));
374
375 return (hb->levels[HBITMAP_LEVELS - 1][pos >> BITS_PER_LEVEL] & bit) != 0;
376 }
377
378 void hbitmap_free(HBitmap *hb)
379 {
380 unsigned i;
381 for (i = HBITMAP_LEVELS; i-- > 0; ) {
382 g_free(hb->levels[i]);
383 }
384 g_free(hb);
385 }
386
387 HBitmap *hbitmap_alloc(uint64_t size, int granularity)
388 {
389 HBitmap *hb = g_new0(struct HBitmap, 1);
390 unsigned i;
391
392 assert(granularity >= 0 && granularity < 64);
393 size = (size + (1ULL << granularity) - 1) >> granularity;
394 assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE));
395
396 hb->size = size;
397 hb->granularity = granularity;
398 for (i = HBITMAP_LEVELS; i-- > 0; ) {
399 size = MAX((size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL, 1);
400 hb->sizes[i] = size;
401 hb->levels[i] = g_new0(unsigned long, size);
402 }
403
404 /* We necessarily have free bits in level 0 due to the definition
405 * of HBITMAP_LEVELS, so use one for a sentinel. This speeds up
406 * hbitmap_iter_skip_words.
407 */
408 assert(size == 1);
409 hb->levels[0][0] |= 1UL << (BITS_PER_LONG - 1);
410 return hb;
411 }
412
413 void hbitmap_truncate(HBitmap *hb, uint64_t size)
414 {
415 bool shrink;
416 unsigned i;
417 uint64_t num_elements = size;
418 uint64_t old;
419
420 /* Size comes in as logical elements, adjust for granularity. */
421 size = (size + (1ULL << hb->granularity) - 1) >> hb->granularity;
422 assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE));
423 shrink = size < hb->size;
424
425 /* bit sizes are identical; nothing to do. */
426 if (size == hb->size) {
427 return;
428 }
429
430 /* If we're losing bits, let's clear those bits before we invalidate all of
431 * our invariants. This helps keep the bitcount consistent, and will prevent
432 * us from carrying around garbage bits beyond the end of the map.
433 */
434 if (shrink) {
435 /* Don't clear partial granularity groups;
436 * start at the first full one. */
437 uint64_t start = QEMU_ALIGN_UP(num_elements, 1 << hb->granularity);
438 uint64_t fix_count = (hb->size << hb->granularity) - start;
439
440 assert(fix_count);
441 hbitmap_reset(hb, start, fix_count);
442 }
443
444 hb->size = size;
445 for (i = HBITMAP_LEVELS; i-- > 0; ) {
446 size = MAX(BITS_TO_LONGS(size), 1);
447 if (hb->sizes[i] == size) {
448 break;
449 }
450 old = hb->sizes[i];
451 hb->sizes[i] = size;
452 hb->levels[i] = g_realloc(hb->levels[i], size * sizeof(unsigned long));
453 if (!shrink) {
454 memset(&hb->levels[i][old], 0x00,
455 (size - old) * sizeof(*hb->levels[i]));
456 }
457 }
458 }
459
460
461 /**
462 * Given HBitmaps A and B, let A := A (BITOR) B.
463 * Bitmap B will not be modified.
464 *
465 * @return true if the merge was successful,
466 * false if it was not attempted.
467 */
468 bool hbitmap_merge(HBitmap *a, const HBitmap *b)
469 {
470 int i;
471 uint64_t j;
472
473 if ((a->size != b->size) || (a->granularity != b->granularity)) {
474 return false;
475 }
476
477 if (hbitmap_count(b) == 0) {
478 return true;
479 }
480
481 /* This merge is O(size), as BITS_PER_LONG and HBITMAP_LEVELS are constant.
482 * It may be possible to improve running times for sparsely populated maps
483 * by using hbitmap_iter_next, but this is suboptimal for dense maps.
484 */
485 for (i = HBITMAP_LEVELS - 1; i >= 0; i--) {
486 for (j = 0; j < a->sizes[i]; j++) {
487 a->levels[i][j] |= b->levels[i][j];
488 }
489 }
490
491 return true;
492 }