1
2
3
4
5
6
7
8
9
10
11
12#include "qemu/osdep.h"
13#include <glib.h>
14#include "qemu/hbitmap.h"
15#include "qemu/host-utils.h"
16#include "trace.h"
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55struct HBitmap {
56
57 uint64_t size;
58
59
60 uint64_t count;
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80 int granularity;
81
82
83
84
85
86
87
88
89
90 unsigned long *levels[HBITMAP_LEVELS];
91
92
93 uint64_t sizes[HBITMAP_LEVELS];
94};
95
96
97
98
99unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi)
100{
101 size_t pos = hbi->pos;
102 const HBitmap *hb = hbi->hb;
103 unsigned i = HBITMAP_LEVELS - 1;
104
105 unsigned long cur;
106 do {
107 cur = hbi->cur[--i];
108 pos >>= BITS_PER_LEVEL;
109 } while (cur == 0);
110
111
112
113
114
115
116
117 if (i == 0 && cur == (1UL << (BITS_PER_LONG - 1))) {
118 return 0;
119 }
120 for (; i < HBITMAP_LEVELS - 1; i++) {
121
122
123
124
125 assert(cur);
126 pos = (pos << BITS_PER_LEVEL) + ctzl(cur);
127 hbi->cur[i] = cur & (cur - 1);
128
129
130 cur = hb->levels[i + 1][pos];
131 }
132
133 hbi->pos = pos;
134 trace_hbitmap_iter_skip_words(hbi->hb, hbi, pos, cur);
135
136 assert(cur);
137 return cur;
138}
139
140void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first)
141{
142 unsigned i, bit;
143 uint64_t pos;
144
145 hbi->hb = hb;
146 pos = first >> hb->granularity;
147 assert(pos < hb->size);
148 hbi->pos = pos >> BITS_PER_LEVEL;
149 hbi->granularity = hb->granularity;
150
151 for (i = HBITMAP_LEVELS; i-- > 0; ) {
152 bit = pos & (BITS_PER_LONG - 1);
153 pos >>= BITS_PER_LEVEL;
154
155
156 hbi->cur[i] = hb->levels[i][pos] & ~((1UL << bit) - 1);
157
158
159
160
161 if (i != HBITMAP_LEVELS - 1) {
162 hbi->cur[i] &= ~(1UL << bit);
163 }
164 }
165}
166
167bool hbitmap_empty(const HBitmap *hb)
168{
169 return hb->count == 0;
170}
171
172int hbitmap_granularity(const HBitmap *hb)
173{
174 return hb->granularity;
175}
176
177uint64_t hbitmap_count(const HBitmap *hb)
178{
179 return hb->count << hb->granularity;
180}
181
182
183
184
185static uint64_t hb_count_between(HBitmap *hb, uint64_t start, uint64_t last)
186{
187 HBitmapIter hbi;
188 uint64_t count = 0;
189 uint64_t end = last + 1;
190 unsigned long cur;
191 size_t pos;
192
193 hbitmap_iter_init(&hbi, hb, start << hb->granularity);
194 for (;;) {
195 pos = hbitmap_iter_next_word(&hbi, &cur);
196 if (pos >= (end >> BITS_PER_LEVEL)) {
197 break;
198 }
199 count += ctpopl(cur);
200 }
201
202 if (pos == (end >> BITS_PER_LEVEL)) {
203
204 int bit = end & (BITS_PER_LONG - 1);
205 cur &= (1UL << bit) - 1;
206 count += ctpopl(cur);
207 }
208
209 return count;
210}
211
212
213
214
215static inline bool hb_set_elem(unsigned long *elem, uint64_t start, uint64_t last)
216{
217 unsigned long mask;
218 bool changed;
219
220 assert((last >> BITS_PER_LEVEL) == (start >> BITS_PER_LEVEL));
221 assert(start <= last);
222
223 mask = 2UL << (last & (BITS_PER_LONG - 1));
224 mask -= 1UL << (start & (BITS_PER_LONG - 1));
225 changed = (*elem == 0);
226 *elem |= mask;
227 return changed;
228}
229
230
231static void hb_set_between(HBitmap *hb, int level, uint64_t start, uint64_t last)
232{
233 size_t pos = start >> BITS_PER_LEVEL;
234 size_t lastpos = last >> BITS_PER_LEVEL;
235 bool changed = false;
236 size_t i;
237
238 i = pos;
239 if (i < lastpos) {
240 uint64_t next = (start | (BITS_PER_LONG - 1)) + 1;
241 changed |= hb_set_elem(&hb->levels[level][i], start, next - 1);
242 for (;;) {
243 start = next;
244 next += BITS_PER_LONG;
245 if (++i == lastpos) {
246 break;
247 }
248 changed |= (hb->levels[level][i] == 0);
249 hb->levels[level][i] = ~0UL;
250 }
251 }
252 changed |= hb_set_elem(&hb->levels[level][i], start, last);
253
254
255
256
257 if (level > 0 && changed) {
258 hb_set_between(hb, level - 1, pos, lastpos);
259 }
260}
261
262void hbitmap_set(HBitmap *hb, uint64_t start, uint64_t count)
263{
264
265 uint64_t last = start + count - 1;
266
267 trace_hbitmap_set(hb, start, count,
268 start >> hb->granularity, last >> hb->granularity);
269
270 start >>= hb->granularity;
271 last >>= hb->granularity;
272 count = last - start + 1;
273
274 hb->count += count - hb_count_between(hb, start, last);
275 hb_set_between(hb, HBITMAP_LEVELS - 1, start, last);
276}
277
278
279
280
281static inline bool hb_reset_elem(unsigned long *elem, uint64_t start, uint64_t last)
282{
283 unsigned long mask;
284 bool blanked;
285
286 assert((last >> BITS_PER_LEVEL) == (start >> BITS_PER_LEVEL));
287 assert(start <= last);
288
289 mask = 2UL << (last & (BITS_PER_LONG - 1));
290 mask -= 1UL << (start & (BITS_PER_LONG - 1));
291 blanked = *elem != 0 && ((*elem & ~mask) == 0);
292 *elem &= ~mask;
293 return blanked;
294}
295
296
297static void hb_reset_between(HBitmap *hb, int level, uint64_t start, uint64_t last)
298{
299 size_t pos = start >> BITS_PER_LEVEL;
300 size_t lastpos = last >> BITS_PER_LEVEL;
301 bool changed = false;
302 size_t i;
303
304 i = pos;
305 if (i < lastpos) {
306 uint64_t next = (start | (BITS_PER_LONG - 1)) + 1;
307
308
309
310
311
312
313 if (hb_reset_elem(&hb->levels[level][i], start, next - 1)) {
314 changed = true;
315 } else {
316 pos++;
317 }
318
319 for (;;) {
320 start = next;
321 next += BITS_PER_LONG;
322 if (++i == lastpos) {
323 break;
324 }
325 changed |= (hb->levels[level][i] != 0);
326 hb->levels[level][i] = 0UL;
327 }
328 }
329
330
331 if (hb_reset_elem(&hb->levels[level][i], start, last)) {
332 changed = true;
333 } else {
334 lastpos--;
335 }
336
337 if (level > 0 && changed) {
338 hb_reset_between(hb, level - 1, pos, lastpos);
339 }
340}
341
342void hbitmap_reset(HBitmap *hb, uint64_t start, uint64_t count)
343{
344
345 uint64_t last = start + count - 1;
346
347 trace_hbitmap_reset(hb, start, count,
348 start >> hb->granularity, last >> hb->granularity);
349
350 start >>= hb->granularity;
351 last >>= hb->granularity;
352
353 hb->count -= hb_count_between(hb, start, last);
354 hb_reset_between(hb, HBITMAP_LEVELS - 1, start, last);
355}
356
357void hbitmap_reset_all(HBitmap *hb)
358{
359 unsigned int i;
360
361
362 for (i = HBITMAP_LEVELS; --i >= 1; ) {
363 memset(hb->levels[i], 0, hb->sizes[i] * sizeof(unsigned long));
364 }
365
366 hb->levels[0][0] = 1UL << (BITS_PER_LONG - 1);
367 hb->count = 0;
368}
369
370bool hbitmap_get(const HBitmap *hb, uint64_t item)
371{
372
373 uint64_t pos = item >> hb->granularity;
374 unsigned long bit = 1UL << (pos & (BITS_PER_LONG - 1));
375
376 return (hb->levels[HBITMAP_LEVELS - 1][pos >> BITS_PER_LEVEL] & bit) != 0;
377}
378
379void hbitmap_free(HBitmap *hb)
380{
381 unsigned i;
382 for (i = HBITMAP_LEVELS; i-- > 0; ) {
383 g_free(hb->levels[i]);
384 }
385 g_free(hb);
386}
387
388HBitmap *hbitmap_alloc(uint64_t size, int granularity)
389{
390 HBitmap *hb = g_new0(struct HBitmap, 1);
391 unsigned i;
392
393 assert(granularity >= 0 && granularity < 64);
394 size = (size + (1ULL << granularity) - 1) >> granularity;
395 assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE));
396
397 hb->size = size;
398 hb->granularity = granularity;
399 for (i = HBITMAP_LEVELS; i-- > 0; ) {
400 size = MAX((size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL, 1);
401 hb->sizes[i] = size;
402 hb->levels[i] = g_new0(unsigned long, size);
403 }
404
405
406
407
408
409 assert(size == 1);
410 hb->levels[0][0] |= 1UL << (BITS_PER_LONG - 1);
411 return hb;
412}
413
414void hbitmap_truncate(HBitmap *hb, uint64_t size)
415{
416 bool shrink;
417 unsigned i;
418 uint64_t num_elements = size;
419 uint64_t old;
420
421
422 size = (size + (1ULL << hb->granularity) - 1) >> hb->granularity;
423 assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE));
424 shrink = size < hb->size;
425
426
427 if (size == hb->size) {
428 return;
429 }
430
431
432
433
434
435 if (shrink) {
436
437
438 uint64_t start = QEMU_ALIGN_UP(num_elements, 1 << hb->granularity);
439 uint64_t fix_count = (hb->size << hb->granularity) - start;
440
441 assert(fix_count);
442 hbitmap_reset(hb, start, fix_count);
443 }
444
445 hb->size = size;
446 for (i = HBITMAP_LEVELS; i-- > 0; ) {
447 size = MAX(BITS_TO_LONGS(size), 1);
448 if (hb->sizes[i] == size) {
449 break;
450 }
451 old = hb->sizes[i];
452 hb->sizes[i] = size;
453 hb->levels[i] = g_realloc(hb->levels[i], size * sizeof(unsigned long));
454 if (!shrink) {
455 memset(&hb->levels[i][old], 0x00,
456 (size - old) * sizeof(*hb->levels[i]));
457 }
458 }
459}
460
461
462
463
464
465
466
467
468
469bool hbitmap_merge(HBitmap *a, const HBitmap *b)
470{
471 int i;
472 uint64_t j;
473
474 if ((a->size != b->size) || (a->granularity != b->granularity)) {
475 return false;
476 }
477
478 if (hbitmap_count(b) == 0) {
479 return true;
480 }
481
482
483
484
485
486 for (i = HBITMAP_LEVELS - 1; i >= 0; i--) {
487 for (j = 0; j < a->sizes[i]; j++) {
488 a->levels[i][j] |= b->levels[i][j];
489 }
490 }
491
492 return true;
493}
494