1
2
3
4
5
6
7
8
9
10
11
12#include "qemu/osdep.h"
13#include "qemu/hbitmap.h"
14#include "qemu/host-utils.h"
15#include "trace.h"
16
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
54struct HBitmap {
55
56 uint64_t size;
57
58
59 uint64_t count;
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79 int granularity;
80
81
82
83
84
85
86
87
88
89 unsigned long *levels[HBITMAP_LEVELS];
90
91
92 uint64_t sizes[HBITMAP_LEVELS];
93};
94
95
96
97
98unsigned 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
111
112
113
114
115
116 if (i == 0 && cur == (1UL << (BITS_PER_LONG - 1))) {
117 return 0;
118 }
119 for (; i < HBITMAP_LEVELS - 1; i++) {
120
121
122
123
124 assert(cur);
125 pos = (pos << BITS_PER_LEVEL) + ctzl(cur);
126 hbi->cur[i] = cur & (cur - 1);
127
128
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
139void 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
155 hbi->cur[i] = hb->levels[i][pos] & ~((1UL << bit) - 1);
156
157
158
159
160 if (i != HBITMAP_LEVELS - 1) {
161 hbi->cur[i] &= ~(1UL << bit);
162 }
163 }
164}
165
166bool hbitmap_empty(const HBitmap *hb)
167{
168 return hb->count == 0;
169}
170
171int hbitmap_granularity(const HBitmap *hb)
172{
173 return hb->granularity;
174}
175
176uint64_t hbitmap_count(const HBitmap *hb)
177{
178 return hb->count << hb->granularity;
179}
180
181
182
183
184static 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
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
212
213
214static 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
230static 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
254
255
256 if (level > 0 && changed) {
257 hb_set_between(hb, level - 1, pos, lastpos);
258 }
259}
260
261void hbitmap_set(HBitmap *hb, uint64_t start, uint64_t count)
262{
263
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 assert(last < hb->size);
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 assert(last < hb->size);
353
354 hb->count -= hb_count_between(hb, start, last);
355 hb_reset_between(hb, HBITMAP_LEVELS - 1, start, last);
356}
357
358void hbitmap_reset_all(HBitmap *hb)
359{
360 unsigned int i;
361
362
363 for (i = HBITMAP_LEVELS; --i >= 1; ) {
364 memset(hb->levels[i], 0, hb->sizes[i] * sizeof(unsigned long));
365 }
366
367 hb->levels[0][0] = 1UL << (BITS_PER_LONG - 1);
368 hb->count = 0;
369}
370
371bool hbitmap_get(const HBitmap *hb, uint64_t item)
372{
373
374 uint64_t pos = item >> hb->granularity;
375 unsigned long bit = 1UL << (pos & (BITS_PER_LONG - 1));
376 assert(pos < hb->size);
377
378 return (hb->levels[HBITMAP_LEVELS - 1][pos >> BITS_PER_LEVEL] & bit) != 0;
379}
380
381void hbitmap_free(HBitmap *hb)
382{
383 unsigned i;
384 for (i = HBITMAP_LEVELS; i-- > 0; ) {
385 g_free(hb->levels[i]);
386 }
387 g_free(hb);
388}
389
390HBitmap *hbitmap_alloc(uint64_t size, int granularity)
391{
392 HBitmap *hb = g_new0(struct HBitmap, 1);
393 unsigned i;
394
395 assert(granularity >= 0 && granularity < 64);
396 size = (size + (1ULL << granularity) - 1) >> granularity;
397 assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE));
398
399 hb->size = size;
400 hb->granularity = granularity;
401 for (i = HBITMAP_LEVELS; i-- > 0; ) {
402 size = MAX((size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL, 1);
403 hb->sizes[i] = size;
404 hb->levels[i] = g_new0(unsigned long, size);
405 }
406
407
408
409
410
411 assert(size == 1);
412 hb->levels[0][0] |= 1UL << (BITS_PER_LONG - 1);
413 return hb;
414}
415
416void hbitmap_truncate(HBitmap *hb, uint64_t size)
417{
418 bool shrink;
419 unsigned i;
420 uint64_t num_elements = size;
421 uint64_t old;
422
423
424 size = (size + (1ULL << hb->granularity) - 1) >> hb->granularity;
425 assert(size <= ((uint64_t)1 << HBITMAP_LOG_MAX_SIZE));
426 shrink = size < hb->size;
427
428
429 if (size == hb->size) {
430 return;
431 }
432
433
434
435
436
437 if (shrink) {
438
439
440 uint64_t start = QEMU_ALIGN_UP(num_elements, 1 << hb->granularity);
441 uint64_t fix_count = (hb->size << hb->granularity) - start;
442
443 assert(fix_count);
444 hbitmap_reset(hb, start, fix_count);
445 }
446
447 hb->size = size;
448 for (i = HBITMAP_LEVELS; i-- > 0; ) {
449 size = MAX(BITS_TO_LONGS(size), 1);
450 if (hb->sizes[i] == size) {
451 break;
452 }
453 old = hb->sizes[i];
454 hb->sizes[i] = size;
455 hb->levels[i] = g_realloc(hb->levels[i], size * sizeof(unsigned long));
456 if (!shrink) {
457 memset(&hb->levels[i][old], 0x00,
458 (size - old) * sizeof(*hb->levels[i]));
459 }
460 }
461}
462
463
464
465
466
467
468
469
470
471bool hbitmap_merge(HBitmap *a, const HBitmap *b)
472{
473 int i;
474 uint64_t j;
475
476 if ((a->size != b->size) || (a->granularity != b->granularity)) {
477 return false;
478 }
479
480 if (hbitmap_count(b) == 0) {
481 return true;
482 }
483
484
485
486
487
488 for (i = HBITMAP_LEVELS - 1; i >= 0; i--) {
489 for (j = 0; j < a->sizes[i]; j++) {
490 a->levels[i][j] |= b->levels[i][j];
491 }
492 }
493
494 return true;
495}
496