scsi: pvscsi: check command descriptor ring buffer size (CVE-2016-4952)
[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 <glib.h>
14 #include "qemu/hbitmap.h"
15 #include "qemu/host-utils.h"
16 #include "trace.h"
17
18 /* HBitmaps provides an array of bits. The bits are stored as usual in an
19 * array of unsigned longs, but HBitmap is also optimized to provide fast
20 * iteration over set bits; going from one bit to the next is O(logB n)
21 * worst case, with B = sizeof(long) * CHAR_BIT: the result is low enough
22 * that the number of levels is in fact fixed.
23 *
24 * In order to do this, it stacks multiple bitmaps with progressively coarser
25 * granularity; in all levels except the last, bit N is set iff the N-th
26 * unsigned long is nonzero in the immediately next level. When iteration
27 * completes on the last level it can examine the 2nd-last level to quickly
28 * skip entire words, and even do so recursively to skip blocks of 64 words or
29 * powers thereof (32 on 32-bit machines).
30 *
31 * Given an index in the bitmap, it can be split in group of bits like
32 * this (for the 64-bit case):
33 *
34 * bits 0-57 => word in the last bitmap | bits 58-63 => bit in the word
35 * bits 0-51 => word in the 2nd-last bitmap | bits 52-57 => bit in the word
36 * bits 0-45 => word in the 3rd-last bitmap | bits 46-51 => bit in the word
37 *
38 * So it is easy to move up simply by shifting the index right by
39 * log2(BITS_PER_LONG) bits. To move down, you shift the index left
40 * similarly, and add the word index within the group. Iteration uses
41 * ffs (find first set bit) to find the next word to examine; this
42 * operation can be done in constant time in most current architectures.
43 *
44 * Setting or clearing a range of m bits on all levels, the work to perform
45 * is O(m + m/W + m/W^2 + ...), which is O(m) like on a regular bitmap.
46 *
47 * When iterating on a bitmap, each bit (on any level) is only visited
48 * once. Hence, The total cost of visiting a bitmap with m bits in it is
49 * the number of bits that are set in all bitmaps. Unless the bitmap is
50 * extremely sparse, this is also O(m + m/W + m/W^2 + ...), so the amortized
51 * cost of advancing from one bit to the next is usually constant (worst case
52 * O(logB n) as in the non-amortized complexity).
53 */
54
55 struct HBitmap {
56 /* Number of total bits in the bottom level. */
57 uint64_t size;
58
59 /* Number of set bits in the bottom level. */
60 uint64_t count;
61
62 /* A scaling factor. Given a granularity of G, each bit in the bitmap will
63 * will actually represent a group of 2^G elements. Each operation on a
64 * range of bits first rounds the bits to determine which group they land
65 * in, and then affect the entire page; iteration will only visit the first
66 * bit of each group. Here is an example of operations in a size-16,
67 * granularity-1 HBitmap:
68 *
69 * initial state 00000000
70 * set(start=0, count=9) 11111000 (iter: 0, 2, 4, 6, 8)
71 * reset(start=1, count=3) 00111000 (iter: 4, 6, 8)
72 * set(start=9, count=2) 00111100 (iter: 4, 6, 8, 10)
73 * reset(start=5, count=5) 00000000
74 *
75 * From an implementation point of view, when setting or resetting bits,
76 * the bitmap will scale bit numbers right by this amount of bits. When
77 * iterating, the bitmap will scale bit numbers left by this amount of
78 * bits.
79 */
80 int granularity;
81
82 /* A number of progressively less coarse bitmaps (i.e. level 0 is the
83 * coarsest). Each bit in level N represents a word in level N+1 that
84 * has a set bit, except the last level where each bit represents the
85 * actual bitmap.
86 *
87 * Note that all bitmaps have the same number of levels. Even a 1-bit
88 * bitmap will still allocate HBITMAP_LEVELS arrays.
89 */
90 unsigned long *levels[HBITMAP_LEVELS];
91
92 /* The length of each levels[] array. */
93 uint64_t sizes[HBITMAP_LEVELS];
94 };
95
96 /* Advance hbi to the next nonzero word and return it. hbi->pos
97 * is updated. Returns zero if we reach the end of the bitmap.
98 */
99 unsigned 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 /* Check for end of iteration. We always use fewer than BITS_PER_LONG
112 * bits in the level 0 bitmap; thus we can repurpose the most significant
113 * bit as a sentinel. The sentinel is set in hbitmap_alloc and ensures
114 * that the above loop ends even without an explicit check on i.
115 */
116
117 if (i == 0 && cur == (1UL << (BITS_PER_LONG - 1))) {
118 return 0;
119 }
120 for (; i < HBITMAP_LEVELS - 1; i++) {
121 /* Shift back pos to the left, matching the right shifts above.
122 * The index of this word's least significant set bit provides
123 * the low-order bits.
124 */
125 assert(cur);
126 pos = (pos << BITS_PER_LEVEL) + ctzl(cur);
127 hbi->cur[i] = cur & (cur - 1);
128
129 /* Set up next level for iteration. */
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
140 void 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 /* Drop bits representing items before first. */
156 hbi->cur[i] = hb->levels[i][pos] & ~((1UL << bit) - 1);
157
158 /* We have already added level i+1, so the lowest set bit has
159 * been processed. Clear it.
160 */
161 if (i != HBITMAP_LEVELS - 1) {
162 hbi->cur[i] &= ~(1UL << bit);
163 }
164 }
165 }
166
167 bool hbitmap_empty(const HBitmap *hb)
168 {
169 return hb->count == 0;
170 }
171
172 int hbitmap_granularity(const HBitmap *hb)
173 {
174 return hb->granularity;
175 }
176
177 uint64_t hbitmap_count(const HBitmap *hb)
178 {
179 return hb->count << hb->granularity;
180 }
181
182 /* Count the number of set bits between start and end, not accounting for
183 * the granularity. Also an example of how to use hbitmap_iter_next_word.
184 */
185 static 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 /* Drop bits representing the END-th and subsequent items. */
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 /* Setting starts at the last layer and propagates up if an element
213 * changes from zero to non-zero.
214 */
215 static 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 /* The recursive workhorse (the depth is limited to HBITMAP_LEVELS)... */
231 static 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 /* If there was any change in this layer, we may have to update
255 * the one above.
256 */
257 if (level > 0 && changed) {
258 hb_set_between(hb, level - 1, pos, lastpos);
259 }
260 }
261
262 void hbitmap_set(HBitmap *hb, uint64_t start, uint64_t count)
263 {
264 /* Compute range in the last layer. */
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 /* Resetting works the other way round: propagate up if the new
279 * value is zero.
280 */
281 static 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 /* The recursive workhorse (the depth is limited to HBITMAP_LEVELS)... */
297 static 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 /* Here we need a more complex test than when setting bits. Even if
309 * something was changed, we must not blank bits in the upper level
310 * unless the lower-level word became entirely zero. So, remove pos
311 * from the upper-level range if bits remain set.
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 /* Same as above, this time for lastpos. */
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
342 void hbitmap_reset(HBitmap *hb, uint64_t start, uint64_t count)
343 {
344 /* Compute range in the last layer. */
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
357 void hbitmap_reset_all(HBitmap *hb)
358 {
359 unsigned int i;
360
361 /* Same as hbitmap_alloc() except for memset() instead of malloc() */
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
370 bool hbitmap_get(const HBitmap *hb, uint64_t item)
371 {
372 /* Compute position and bit in the last layer. */
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
379 void 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
388 HBitmap *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 /* We necessarily have free bits in level 0 due to the definition
406 * of HBITMAP_LEVELS, so use one for a sentinel. This speeds up
407 * hbitmap_iter_skip_words.
408 */
409 assert(size == 1);
410 hb->levels[0][0] |= 1UL << (BITS_PER_LONG - 1);
411 return hb;
412 }
413
414 void 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 /* Size comes in as logical elements, adjust for granularity. */
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 /* bit sizes are identical; nothing to do. */
427 if (size == hb->size) {
428 return;
429 }
430
431 /* If we're losing bits, let's clear those bits before we invalidate all of
432 * our invariants. This helps keep the bitcount consistent, and will prevent
433 * us from carrying around garbage bits beyond the end of the map.
434 */
435 if (shrink) {
436 /* Don't clear partial granularity groups;
437 * start at the first full one. */
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 * Given HBitmaps A and B, let A := A (BITOR) B.
464 * Bitmap B will not be modified.
465 *
466 * @return true if the merge was successful,
467 * false if it was not attempted.
468 */
469 bool 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 /* This merge is O(size), as BITS_PER_LONG and HBITMAP_LEVELS are constant.
483 * It may be possible to improve running times for sparsely populated maps
484 * by using hbitmap_iter_next, but this is suboptimal for dense maps.
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 }