]>
Commit | Line | Data |
---|---|---|
e0e53b2f CC |
1 | /* |
2 | * Bitmap Module | |
3 | * | |
4 | * Stolen from linux/src/lib/bitmap.c | |
5 | * | |
6 | * Copyright (C) 2010 Corentin Chary | |
7 | * | |
8 | * This source code is licensed under the GNU General Public License, | |
9 | * Version 2. | |
10 | */ | |
11 | ||
aafd7584 | 12 | #include "qemu/osdep.h" |
1de7afc9 PB |
13 | #include "qemu/bitops.h" |
14 | #include "qemu/bitmap.h" | |
9f02cfc8 | 15 | #include "qemu/atomic.h" |
e0e53b2f CC |
16 | |
17 | /* | |
b6af0975 | 18 | * bitmaps provide an array of bits, implemented using an |
e0e53b2f CC |
19 | * array of unsigned longs. The number of valid bits in a |
20 | * given bitmap does _not_ need to be an exact multiple of | |
21 | * BITS_PER_LONG. | |
22 | * | |
23 | * The possible unused bits in the last, partially used word | |
24 | * of a bitmap are 'don't care'. The implementation makes | |
25 | * no particular effort to keep them zero. It ensures that | |
26 | * their value will not affect the results of any operation. | |
27 | * The bitmap operations that return Boolean (bitmap_empty, | |
28 | * for example) or scalar (bitmap_weight, for example) results | |
29 | * carefully filter out these unused bits from impacting their | |
30 | * results. | |
31 | * | |
32 | * These operations actually hold to a slightly stronger rule: | |
33 | * if you don't input any bitmaps to these ops that have some | |
34 | * unused bits set, then they won't output any set unused bits | |
35 | * in output bitmaps. | |
36 | * | |
37 | * The byte ordering of bitmaps is more natural on little | |
38 | * endian architectures. | |
39 | */ | |
40 | ||
9c22687e | 41 | int slow_bitmap_empty(const unsigned long *bitmap, long bits) |
e0e53b2f | 42 | { |
9c22687e | 43 | long k, lim = bits/BITS_PER_LONG; |
e0e53b2f CC |
44 | |
45 | for (k = 0; k < lim; ++k) { | |
46 | if (bitmap[k]) { | |
47 | return 0; | |
48 | } | |
49 | } | |
50 | if (bits % BITS_PER_LONG) { | |
51 | if (bitmap[k] & BITMAP_LAST_WORD_MASK(bits)) { | |
52 | return 0; | |
53 | } | |
54 | } | |
55 | ||
56 | return 1; | |
57 | } | |
58 | ||
9c22687e | 59 | int slow_bitmap_full(const unsigned long *bitmap, long bits) |
e0e53b2f | 60 | { |
9c22687e | 61 | long k, lim = bits/BITS_PER_LONG; |
e0e53b2f CC |
62 | |
63 | for (k = 0; k < lim; ++k) { | |
64 | if (~bitmap[k]) { | |
65 | return 0; | |
66 | } | |
67 | } | |
68 | ||
69 | if (bits % BITS_PER_LONG) { | |
70 | if (~bitmap[k] & BITMAP_LAST_WORD_MASK(bits)) { | |
71 | return 0; | |
72 | } | |
73 | } | |
74 | ||
75 | return 1; | |
76 | } | |
77 | ||
78 | int slow_bitmap_equal(const unsigned long *bitmap1, | |
9c22687e | 79 | const unsigned long *bitmap2, long bits) |
e0e53b2f | 80 | { |
9c22687e | 81 | long k, lim = bits/BITS_PER_LONG; |
e0e53b2f CC |
82 | |
83 | for (k = 0; k < lim; ++k) { | |
84 | if (bitmap1[k] != bitmap2[k]) { | |
85 | return 0; | |
86 | } | |
87 | } | |
88 | ||
89 | if (bits % BITS_PER_LONG) { | |
90 | if ((bitmap1[k] ^ bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits)) { | |
91 | return 0; | |
92 | } | |
93 | } | |
94 | ||
95 | return 1; | |
96 | } | |
97 | ||
98 | void slow_bitmap_complement(unsigned long *dst, const unsigned long *src, | |
9c22687e | 99 | long bits) |
e0e53b2f | 100 | { |
9c22687e | 101 | long k, lim = bits/BITS_PER_LONG; |
e0e53b2f CC |
102 | |
103 | for (k = 0; k < lim; ++k) { | |
104 | dst[k] = ~src[k]; | |
105 | } | |
106 | ||
107 | if (bits % BITS_PER_LONG) { | |
108 | dst[k] = ~src[k] & BITMAP_LAST_WORD_MASK(bits); | |
109 | } | |
110 | } | |
111 | ||
112 | int slow_bitmap_and(unsigned long *dst, const unsigned long *bitmap1, | |
9c22687e | 113 | const unsigned long *bitmap2, long bits) |
e0e53b2f | 114 | { |
9c22687e JQ |
115 | long k; |
116 | long nr = BITS_TO_LONGS(bits); | |
e0e53b2f CC |
117 | unsigned long result = 0; |
118 | ||
119 | for (k = 0; k < nr; k++) { | |
120 | result |= (dst[k] = bitmap1[k] & bitmap2[k]); | |
121 | } | |
122 | return result != 0; | |
123 | } | |
124 | ||
125 | void slow_bitmap_or(unsigned long *dst, const unsigned long *bitmap1, | |
9c22687e | 126 | const unsigned long *bitmap2, long bits) |
e0e53b2f | 127 | { |
9c22687e JQ |
128 | long k; |
129 | long nr = BITS_TO_LONGS(bits); | |
e0e53b2f CC |
130 | |
131 | for (k = 0; k < nr; k++) { | |
132 | dst[k] = bitmap1[k] | bitmap2[k]; | |
133 | } | |
134 | } | |
135 | ||
136 | void slow_bitmap_xor(unsigned long *dst, const unsigned long *bitmap1, | |
9c22687e | 137 | const unsigned long *bitmap2, long bits) |
e0e53b2f | 138 | { |
9c22687e JQ |
139 | long k; |
140 | long nr = BITS_TO_LONGS(bits); | |
e0e53b2f CC |
141 | |
142 | for (k = 0; k < nr; k++) { | |
143 | dst[k] = bitmap1[k] ^ bitmap2[k]; | |
144 | } | |
145 | } | |
146 | ||
147 | int slow_bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1, | |
9c22687e | 148 | const unsigned long *bitmap2, long bits) |
e0e53b2f | 149 | { |
9c22687e JQ |
150 | long k; |
151 | long nr = BITS_TO_LONGS(bits); | |
e0e53b2f CC |
152 | unsigned long result = 0; |
153 | ||
154 | for (k = 0; k < nr; k++) { | |
155 | result |= (dst[k] = bitmap1[k] & ~bitmap2[k]); | |
156 | } | |
157 | return result != 0; | |
158 | } | |
159 | ||
9c22687e | 160 | void bitmap_set(unsigned long *map, long start, long nr) |
e0e53b2f CC |
161 | { |
162 | unsigned long *p = map + BIT_WORD(start); | |
9c22687e | 163 | const long size = start + nr; |
e0e53b2f CC |
164 | int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG); |
165 | unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start); | |
166 | ||
e12ed72e PL |
167 | assert(start >= 0 && nr >= 0); |
168 | ||
e0e53b2f CC |
169 | while (nr - bits_to_set >= 0) { |
170 | *p |= mask_to_set; | |
171 | nr -= bits_to_set; | |
172 | bits_to_set = BITS_PER_LONG; | |
173 | mask_to_set = ~0UL; | |
174 | p++; | |
175 | } | |
176 | if (nr) { | |
177 | mask_to_set &= BITMAP_LAST_WORD_MASK(size); | |
178 | *p |= mask_to_set; | |
179 | } | |
180 | } | |
181 | ||
9f02cfc8 SH |
182 | void bitmap_set_atomic(unsigned long *map, long start, long nr) |
183 | { | |
184 | unsigned long *p = map + BIT_WORD(start); | |
185 | const long size = start + nr; | |
186 | int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG); | |
187 | unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start); | |
188 | ||
e12ed72e PL |
189 | assert(start >= 0 && nr >= 0); |
190 | ||
9f02cfc8 SH |
191 | /* First word */ |
192 | if (nr - bits_to_set > 0) { | |
d73415a3 | 193 | qatomic_or(p, mask_to_set); |
9f02cfc8 SH |
194 | nr -= bits_to_set; |
195 | bits_to_set = BITS_PER_LONG; | |
196 | mask_to_set = ~0UL; | |
197 | p++; | |
198 | } | |
199 | ||
200 | /* Full words */ | |
201 | if (bits_to_set == BITS_PER_LONG) { | |
202 | while (nr >= BITS_PER_LONG) { | |
203 | *p = ~0UL; | |
204 | nr -= BITS_PER_LONG; | |
205 | p++; | |
206 | } | |
207 | } | |
208 | ||
209 | /* Last word */ | |
210 | if (nr) { | |
211 | mask_to_set &= BITMAP_LAST_WORD_MASK(size); | |
d73415a3 | 212 | qatomic_or(p, mask_to_set); |
9f02cfc8 | 213 | } else { |
d73415a3 | 214 | /* If we avoided the full barrier in qatomic_or(), issue a |
9f02cfc8 SH |
215 | * barrier to account for the assignments in the while loop. |
216 | */ | |
217 | smp_mb(); | |
218 | } | |
219 | } | |
220 | ||
9c22687e | 221 | void bitmap_clear(unsigned long *map, long start, long nr) |
e0e53b2f CC |
222 | { |
223 | unsigned long *p = map + BIT_WORD(start); | |
9c22687e | 224 | const long size = start + nr; |
e0e53b2f CC |
225 | int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG); |
226 | unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start); | |
227 | ||
e12ed72e PL |
228 | assert(start >= 0 && nr >= 0); |
229 | ||
e0e53b2f CC |
230 | while (nr - bits_to_clear >= 0) { |
231 | *p &= ~mask_to_clear; | |
232 | nr -= bits_to_clear; | |
233 | bits_to_clear = BITS_PER_LONG; | |
234 | mask_to_clear = ~0UL; | |
235 | p++; | |
236 | } | |
237 | if (nr) { | |
238 | mask_to_clear &= BITMAP_LAST_WORD_MASK(size); | |
239 | *p &= ~mask_to_clear; | |
240 | } | |
241 | } | |
242 | ||
cedb70ea PX |
243 | bool bitmap_test_and_clear(unsigned long *map, long start, long nr) |
244 | { | |
245 | unsigned long *p = map + BIT_WORD(start); | |
246 | const long size = start + nr; | |
247 | int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG); | |
248 | unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start); | |
249 | bool dirty = false; | |
250 | ||
251 | assert(start >= 0 && nr >= 0); | |
252 | ||
253 | /* First word */ | |
254 | if (nr - bits_to_clear > 0) { | |
255 | if ((*p) & mask_to_clear) { | |
256 | dirty = true; | |
257 | } | |
258 | *p &= ~mask_to_clear; | |
259 | nr -= bits_to_clear; | |
260 | bits_to_clear = BITS_PER_LONG; | |
261 | p++; | |
262 | } | |
263 | ||
264 | /* Full words */ | |
265 | if (bits_to_clear == BITS_PER_LONG) { | |
266 | while (nr >= BITS_PER_LONG) { | |
267 | if (*p) { | |
268 | dirty = true; | |
269 | *p = 0; | |
270 | } | |
271 | nr -= BITS_PER_LONG; | |
272 | p++; | |
273 | } | |
274 | } | |
275 | ||
276 | /* Last word */ | |
277 | if (nr) { | |
278 | mask_to_clear &= BITMAP_LAST_WORD_MASK(size); | |
279 | if ((*p) & mask_to_clear) { | |
280 | dirty = true; | |
281 | } | |
282 | *p &= ~mask_to_clear; | |
283 | } | |
284 | ||
285 | return dirty; | |
286 | } | |
287 | ||
36546e5b SH |
288 | bool bitmap_test_and_clear_atomic(unsigned long *map, long start, long nr) |
289 | { | |
290 | unsigned long *p = map + BIT_WORD(start); | |
291 | const long size = start + nr; | |
292 | int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG); | |
293 | unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start); | |
294 | unsigned long dirty = 0; | |
295 | unsigned long old_bits; | |
296 | ||
e12ed72e PL |
297 | assert(start >= 0 && nr >= 0); |
298 | ||
36546e5b SH |
299 | /* First word */ |
300 | if (nr - bits_to_clear > 0) { | |
d73415a3 | 301 | old_bits = qatomic_fetch_and(p, ~mask_to_clear); |
36546e5b SH |
302 | dirty |= old_bits & mask_to_clear; |
303 | nr -= bits_to_clear; | |
304 | bits_to_clear = BITS_PER_LONG; | |
305 | mask_to_clear = ~0UL; | |
306 | p++; | |
307 | } | |
308 | ||
309 | /* Full words */ | |
310 | if (bits_to_clear == BITS_PER_LONG) { | |
311 | while (nr >= BITS_PER_LONG) { | |
312 | if (*p) { | |
d73415a3 | 313 | old_bits = qatomic_xchg(p, 0); |
36546e5b SH |
314 | dirty |= old_bits; |
315 | } | |
316 | nr -= BITS_PER_LONG; | |
317 | p++; | |
318 | } | |
319 | } | |
320 | ||
321 | /* Last word */ | |
322 | if (nr) { | |
323 | mask_to_clear &= BITMAP_LAST_WORD_MASK(size); | |
d73415a3 | 324 | old_bits = qatomic_fetch_and(p, ~mask_to_clear); |
36546e5b SH |
325 | dirty |= old_bits & mask_to_clear; |
326 | } else { | |
327 | if (!dirty) { | |
328 | smp_mb(); | |
329 | } | |
330 | } | |
331 | ||
332 | return dirty != 0; | |
333 | } | |
334 | ||
d6eb1413 GH |
335 | void bitmap_copy_and_clear_atomic(unsigned long *dst, unsigned long *src, |
336 | long nr) | |
337 | { | |
338 | while (nr > 0) { | |
d73415a3 | 339 | *dst = qatomic_xchg(src, 0); |
d6eb1413 GH |
340 | dst++; |
341 | src++; | |
342 | nr -= BITS_PER_LONG; | |
343 | } | |
344 | } | |
345 | ||
e0e53b2f CC |
346 | #define ALIGN_MASK(x,mask) (((x)+(mask))&~(mask)) |
347 | ||
348 | /** | |
349 | * bitmap_find_next_zero_area - find a contiguous aligned zero area | |
350 | * @map: The address to base the search on | |
351 | * @size: The bitmap size in bits | |
352 | * @start: The bitnumber to start searching at | |
353 | * @nr: The number of zeroed bits we're looking for | |
354 | * @align_mask: Alignment mask for zero area | |
355 | * | |
356 | * The @align_mask should be one less than a power of 2; the effect is that | |
357 | * the bit offset of all zero areas this function finds is multiples of that | |
358 | * power of 2. A @align_mask of 0 means no alignment is required. | |
359 | */ | |
360 | unsigned long bitmap_find_next_zero_area(unsigned long *map, | |
9c22687e JQ |
361 | unsigned long size, |
362 | unsigned long start, | |
363 | unsigned long nr, | |
364 | unsigned long align_mask) | |
e0e53b2f CC |
365 | { |
366 | unsigned long index, end, i; | |
367 | again: | |
368 | index = find_next_zero_bit(map, size, start); | |
369 | ||
370 | /* Align allocation */ | |
371 | index = ALIGN_MASK(index, align_mask); | |
372 | ||
373 | end = index + nr; | |
374 | if (end > size) { | |
375 | return end; | |
376 | } | |
377 | i = find_next_bit(map, end, index); | |
378 | if (i < end) { | |
379 | start = i + 1; | |
380 | goto again; | |
381 | } | |
382 | return index; | |
383 | } | |
384 | ||
385 | int slow_bitmap_intersects(const unsigned long *bitmap1, | |
9c22687e | 386 | const unsigned long *bitmap2, long bits) |
e0e53b2f | 387 | { |
9c22687e | 388 | long k, lim = bits/BITS_PER_LONG; |
e0e53b2f CC |
389 | |
390 | for (k = 0; k < lim; ++k) { | |
391 | if (bitmap1[k] & bitmap2[k]) { | |
392 | return 1; | |
393 | } | |
394 | } | |
395 | ||
396 | if (bits % BITS_PER_LONG) { | |
397 | if ((bitmap1[k] & bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits)) { | |
398 | return 1; | |
399 | } | |
400 | } | |
401 | return 0; | |
402 | } | |
fc7deeea PX |
403 | |
404 | long slow_bitmap_count_one(const unsigned long *bitmap, long nbits) | |
405 | { | |
406 | long k, lim = nbits / BITS_PER_LONG, result = 0; | |
407 | ||
408 | for (k = 0; k < lim; k++) { | |
409 | result += ctpopl(bitmap[k]); | |
410 | } | |
411 | ||
412 | if (nbits % BITS_PER_LONG) { | |
413 | result += ctpopl(bitmap[k] & BITMAP_LAST_WORD_MASK(nbits)); | |
414 | } | |
415 | ||
416 | return result; | |
417 | } | |
d7788151 PX |
418 | |
419 | static void bitmap_to_from_le(unsigned long *dst, | |
420 | const unsigned long *src, long nbits) | |
421 | { | |
422 | long len = BITS_TO_LONGS(nbits); | |
423 | ||
e03b5686 | 424 | #if HOST_BIG_ENDIAN |
d7788151 PX |
425 | long index; |
426 | ||
427 | for (index = 0; index < len; index++) { | |
428 | # if HOST_LONG_BITS == 64 | |
429 | dst[index] = bswap64(src[index]); | |
430 | # else | |
431 | dst[index] = bswap32(src[index]); | |
432 | # endif | |
433 | } | |
434 | #else | |
435 | memcpy(dst, src, len * sizeof(unsigned long)); | |
436 | #endif | |
437 | } | |
438 | ||
439 | void bitmap_from_le(unsigned long *dst, const unsigned long *src, | |
440 | long nbits) | |
441 | { | |
442 | bitmap_to_from_le(dst, src, nbits); | |
443 | } | |
444 | ||
445 | void bitmap_to_le(unsigned long *dst, const unsigned long *src, | |
446 | long nbits) | |
447 | { | |
448 | bitmap_to_from_le(dst, src, nbits); | |
449 | } | |
ad37f24d PX |
450 | |
451 | /* | |
452 | * Copy "src" bitmap with a positive offset and put it into the "dst" | |
453 | * bitmap. The caller needs to make sure the bitmap size of "src" | |
454 | * is bigger than (shift + nbits). | |
455 | */ | |
456 | void bitmap_copy_with_src_offset(unsigned long *dst, const unsigned long *src, | |
457 | unsigned long shift, unsigned long nbits) | |
458 | { | |
459 | unsigned long left_mask, right_mask, last_mask; | |
460 | ||
461 | /* Proper shift src pointer to the first word to copy from */ | |
462 | src += BIT_WORD(shift); | |
463 | shift %= BITS_PER_LONG; | |
464 | ||
465 | if (!shift) { | |
466 | /* Fast path */ | |
467 | bitmap_copy(dst, src, nbits); | |
468 | return; | |
469 | } | |
470 | ||
471 | right_mask = (1ul << shift) - 1; | |
472 | left_mask = ~right_mask; | |
473 | ||
474 | while (nbits >= BITS_PER_LONG) { | |
475 | *dst = (*src & left_mask) >> shift; | |
476 | *dst |= (src[1] & right_mask) << (BITS_PER_LONG - shift); | |
477 | dst++; | |
478 | src++; | |
479 | nbits -= BITS_PER_LONG; | |
480 | } | |
481 | ||
482 | if (nbits > BITS_PER_LONG - shift) { | |
483 | *dst = (*src & left_mask) >> shift; | |
484 | nbits -= BITS_PER_LONG - shift; | |
485 | last_mask = (1ul << nbits) - 1; | |
486 | *dst |= (src[1] & last_mask) << (BITS_PER_LONG - shift); | |
487 | } else if (nbits) { | |
488 | last_mask = (1ul << nbits) - 1; | |
489 | *dst = (*src >> shift) & last_mask; | |
490 | } | |
491 | } | |
492 | ||
493 | /* | |
494 | * Copy "src" bitmap into the "dst" bitmap with an offset in the | |
495 | * "dst". The caller needs to make sure the bitmap size of "dst" is | |
496 | * bigger than (shift + nbits). | |
497 | */ | |
498 | void bitmap_copy_with_dst_offset(unsigned long *dst, const unsigned long *src, | |
499 | unsigned long shift, unsigned long nbits) | |
500 | { | |
501 | unsigned long left_mask, right_mask, last_mask; | |
502 | ||
503 | /* Proper shift dst pointer to the first word to copy from */ | |
504 | dst += BIT_WORD(shift); | |
505 | shift %= BITS_PER_LONG; | |
506 | ||
507 | if (!shift) { | |
508 | /* Fast path */ | |
509 | bitmap_copy(dst, src, nbits); | |
510 | return; | |
511 | } | |
512 | ||
513 | right_mask = (1ul << (BITS_PER_LONG - shift)) - 1; | |
514 | left_mask = ~right_mask; | |
515 | ||
516 | *dst &= (1ul << shift) - 1; | |
517 | while (nbits >= BITS_PER_LONG) { | |
518 | *dst |= (*src & right_mask) << shift; | |
519 | dst[1] = (*src & left_mask) >> (BITS_PER_LONG - shift); | |
520 | dst++; | |
521 | src++; | |
522 | nbits -= BITS_PER_LONG; | |
523 | } | |
524 | ||
525 | if (nbits > BITS_PER_LONG - shift) { | |
526 | *dst |= (*src & right_mask) << shift; | |
527 | nbits -= BITS_PER_LONG - shift; | |
528 | last_mask = ((1ul << nbits) - 1) << (BITS_PER_LONG - shift); | |
529 | dst[1] = (*src & last_mask) >> (BITS_PER_LONG - shift); | |
530 | } else if (nbits) { | |
531 | last_mask = (1ul << nbits) - 1; | |
532 | *dst |= (*src & last_mask) << shift; | |
533 | } | |
534 | } |