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