util/bitmap.c

   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
  12 #include "qemu/osdep.h"
  13 #include "qemu/bitops.h"
  14 #include "qemu/bitmap.h"
  15 #include "qemu/atomic.h"
  16
  17 /*
  18  * bitmaps provide an array of bits, implemented using an
  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
  41 int slow_bitmap_empty(const unsigned long *bitmap, long bits)
  42 {
  43     long k, lim = bits/BITS_PER_LONG;
  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
  59 int slow_bitmap_full(const unsigned long *bitmap, long bits)
  60 {
  61     long k, lim = bits/BITS_PER_LONG;
  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,
  79                       const unsigned long *bitmap2, long bits)
  80 {
  81     long k, lim = bits/BITS_PER_LONG;
  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,
  99                             long bits)
 100 {
 101     long k, lim = bits/BITS_PER_LONG;
 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,
 113                     const unsigned long *bitmap2, long bits)
 114 {
 115     long k;
 116     long nr = BITS_TO_LONGS(bits);
 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,
 126                     const unsigned long *bitmap2, long bits)
 127 {
 128     long k;
 129     long nr = BITS_TO_LONGS(bits);
 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,
 137                      const unsigned long *bitmap2, long bits)
 138 {
 139     long k;
 140     long nr = BITS_TO_LONGS(bits);
 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,
 148                        const unsigned long *bitmap2, long bits)
 149 {
 150     long k;
 151     long nr = BITS_TO_LONGS(bits);
 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
 160 #define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) % BITS_PER_LONG))
 161
 162 void bitmap_set(unsigned long *map, long start, long nr)
 163 {
 164     unsigned long *p = map + BIT_WORD(start);
 165     const long size = start + nr;
 166     int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
 167     unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);
 168
 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
 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
 189     /* First word */
 190     if (nr - bits_to_set > 0) {
 191         atomic_or(p, mask_to_set);
 192         nr -= bits_to_set;
 193         bits_to_set = BITS_PER_LONG;
 194         mask_to_set = ~0UL;
 195         p++;
 196     }
 197
 198     /* Full words */
 199     if (bits_to_set == BITS_PER_LONG) {
 200         while (nr >= BITS_PER_LONG) {
 201             *p = ~0UL;
 202             nr -= BITS_PER_LONG;
 203             p++;
 204         }
 205     }
 206
 207     /* Last word */
 208     if (nr) {
 209         mask_to_set &= BITMAP_LAST_WORD_MASK(size);
 210         atomic_or(p, mask_to_set);
 211     } else {
 212         /* If we avoided the full barrier in atomic_or(), issue a
 213          * barrier to account for the assignments in the while loop.
 214          */
 215         smp_mb();
 216     }
 217 }
 218
 219 void bitmap_clear(unsigned long *map, long start, long nr)
 220 {
 221     unsigned long *p = map + BIT_WORD(start);
 222     const long size = start + nr;
 223     int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
 224     unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);
 225
 226     while (nr - bits_to_clear >= 0) {
 227         *p &= ~mask_to_clear;
 228         nr -= bits_to_clear;
 229         bits_to_clear = BITS_PER_LONG;
 230         mask_to_clear = ~0UL;
 231         p++;
 232     }
 233     if (nr) {
 234         mask_to_clear &= BITMAP_LAST_WORD_MASK(size);
 235         *p &= ~mask_to_clear;
 236     }
 237 }
 238
 239 bool bitmap_test_and_clear_atomic(unsigned long *map, long start, long nr)
 240 {
 241     unsigned long *p = map + BIT_WORD(start);
 242     const long size = start + nr;
 243     int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
 244     unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);
 245     unsigned long dirty = 0;
 246     unsigned long old_bits;
 247
 248     /* First word */
 249     if (nr - bits_to_clear > 0) {
 250         old_bits = atomic_fetch_and(p, ~mask_to_clear);
 251         dirty |= old_bits & mask_to_clear;
 252         nr -= bits_to_clear;
 253         bits_to_clear = BITS_PER_LONG;
 254         mask_to_clear = ~0UL;
 255         p++;
 256     }
 257
 258     /* Full words */
 259     if (bits_to_clear == BITS_PER_LONG) {
 260         while (nr >= BITS_PER_LONG) {
 261             if (*p) {
 262                 old_bits = atomic_xchg(p, 0);
 263                 dirty |= old_bits;
 264             }
 265             nr -= BITS_PER_LONG;
 266             p++;
 267         }
 268     }
 269
 270     /* Last word */
 271     if (nr) {
 272         mask_to_clear &= BITMAP_LAST_WORD_MASK(size);
 273         old_bits = atomic_fetch_and(p, ~mask_to_clear);
 274         dirty |= old_bits & mask_to_clear;
 275     } else {
 276         if (!dirty) {
 277             smp_mb();
 278         }
 279     }
 280
 281     return dirty != 0;
 282 }
 283
 284 #define ALIGN_MASK(x,mask)      (((x)+(mask))&~(mask))
 285
 286 /**
 287  * bitmap_find_next_zero_area - find a contiguous aligned zero area
 288  * @map: The address to base the search on
 289  * @size: The bitmap size in bits
 290  * @start: The bitnumber to start searching at
 291  * @nr: The number of zeroed bits we're looking for
 292  * @align_mask: Alignment mask for zero area
 293  *
 294  * The @align_mask should be one less than a power of 2; the effect is that
 295  * the bit offset of all zero areas this function finds is multiples of that
 296  * power of 2. A @align_mask of 0 means no alignment is required.
 297  */
 298 unsigned long bitmap_find_next_zero_area(unsigned long *map,
 299                                          unsigned long size,
 300                                          unsigned long start,
 301                                          unsigned long nr,
 302                                          unsigned long align_mask)
 303 {
 304     unsigned long index, end, i;
 305 again:
 306     index = find_next_zero_bit(map, size, start);
 307
 308     /* Align allocation */
 309     index = ALIGN_MASK(index, align_mask);
 310
 311     end = index + nr;
 312     if (end > size) {
 313         return end;
 314     }
 315     i = find_next_bit(map, end, index);
 316     if (i < end) {
 317         start = i + 1;
 318         goto again;
 319     }
 320     return index;
 321 }
 322
 323 int slow_bitmap_intersects(const unsigned long *bitmap1,
 324                            const unsigned long *bitmap2, long bits)
 325 {
 326     long k, lim = bits/BITS_PER_LONG;
 327
 328     for (k = 0; k < lim; ++k) {
 329         if (bitmap1[k] & bitmap2[k]) {
 330             return 1;
 331         }
 332     }
 333
 334     if (bits % BITS_PER_LONG) {
 335         if ((bitmap1[k] & bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits)) {
 336             return 1;
 337         }
 338     }
 339     return 0;
 340 }