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/bitops.h"
  13 #include "qemu/bitmap.h"
  14 #include "qemu/atomic.h"
  15
  16 /*
  17  * bitmaps provide an array of bits, implemented using an an
  18  * array of unsigned longs.  The number of valid bits in a
  19  * given bitmap does _not_ need to be an exact multiple of
  20  * BITS_PER_LONG.
  21  *
  22  * The possible unused bits in the last, partially used word
  23  * of a bitmap are 'don't care'.  The implementation makes
  24  * no particular effort to keep them zero.  It ensures that
  25  * their value will not affect the results of any operation.
  26  * The bitmap operations that return Boolean (bitmap_empty,
  27  * for example) or scalar (bitmap_weight, for example) results
  28  * carefully filter out these unused bits from impacting their
  29  * results.
  30  *
  31  * These operations actually hold to a slightly stronger rule:
  32  * if you don't input any bitmaps to these ops that have some
  33  * unused bits set, then they won't output any set unused bits
  34  * in output bitmaps.
  35  *
  36  * The byte ordering of bitmaps is more natural on little
  37  * endian architectures.
  38  */
  39
  40 int slow_bitmap_empty(const unsigned long *bitmap, long bits)
  41 {
  42     long k, lim = bits/BITS_PER_LONG;
  43
  44     for (k = 0; k < lim; ++k) {
  45         if (bitmap[k]) {
  46             return 0;
  47         }
  48     }
  49     if (bits % BITS_PER_LONG) {
  50         if (bitmap[k] & BITMAP_LAST_WORD_MASK(bits)) {
  51             return 0;
  52         }
  53     }
  54
  55     return 1;
  56 }
  57
  58 int slow_bitmap_full(const unsigned long *bitmap, long bits)
  59 {
  60     long k, lim = bits/BITS_PER_LONG;
  61
  62     for (k = 0; k < lim; ++k) {
  63         if (~bitmap[k]) {
  64             return 0;
  65         }
  66     }
  67
  68     if (bits % BITS_PER_LONG) {
  69         if (~bitmap[k] & BITMAP_LAST_WORD_MASK(bits)) {
  70             return 0;
  71         }
  72     }
  73
  74     return 1;
  75 }
  76
  77 int slow_bitmap_equal(const unsigned long *bitmap1,
  78                       const unsigned long *bitmap2, long bits)
  79 {
  80     long k, lim = bits/BITS_PER_LONG;
  81
  82     for (k = 0; k < lim; ++k) {
  83         if (bitmap1[k] != bitmap2[k]) {
  84             return 0;
  85         }
  86     }
  87
  88     if (bits % BITS_PER_LONG) {
  89         if ((bitmap1[k] ^ bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits)) {
  90             return 0;
  91         }
  92     }
  93
  94     return 1;
  95 }
  96
  97 void slow_bitmap_complement(unsigned long *dst, const unsigned long *src,
  98                             long bits)
  99 {
 100     long k, lim = bits/BITS_PER_LONG;
 101
 102     for (k = 0; k < lim; ++k) {
 103         dst[k] = ~src[k];
 104     }
 105
 106     if (bits % BITS_PER_LONG) {
 107         dst[k] = ~src[k] & BITMAP_LAST_WORD_MASK(bits);
 108     }
 109 }
 110
 111 int slow_bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
 112                     const unsigned long *bitmap2, long bits)
 113 {
 114     long k;
 115     long nr = BITS_TO_LONGS(bits);
 116     unsigned long result = 0;
 117
 118     for (k = 0; k < nr; k++) {
 119         result |= (dst[k] = bitmap1[k] & bitmap2[k]);
 120     }
 121     return result != 0;
 122 }
 123
 124 void slow_bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
 125                     const unsigned long *bitmap2, long bits)
 126 {
 127     long k;
 128     long nr = BITS_TO_LONGS(bits);
 129
 130     for (k = 0; k < nr; k++) {
 131         dst[k] = bitmap1[k] | bitmap2[k];
 132     }
 133 }
 134
 135 void slow_bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
 136                      const unsigned long *bitmap2, long bits)
 137 {
 138     long k;
 139     long nr = BITS_TO_LONGS(bits);
 140
 141     for (k = 0; k < nr; k++) {
 142         dst[k] = bitmap1[k] ^ bitmap2[k];
 143     }
 144 }
 145
 146 int slow_bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
 147                        const unsigned long *bitmap2, long bits)
 148 {
 149     long k;
 150     long nr = BITS_TO_LONGS(bits);
 151     unsigned long result = 0;
 152
 153     for (k = 0; k < nr; k++) {
 154         result |= (dst[k] = bitmap1[k] & ~bitmap2[k]);
 155     }
 156     return result != 0;
 157 }
 158
 159 #define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) % BITS_PER_LONG))
 160
 161 void bitmap_set(unsigned long *map, long start, long nr)
 162 {
 163     unsigned long *p = map + BIT_WORD(start);
 164     const long size = start + nr;
 165     int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
 166     unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);
 167
 168     while (nr - bits_to_set >= 0) {
 169         *p |= mask_to_set;
 170         nr -= bits_to_set;
 171         bits_to_set = BITS_PER_LONG;
 172         mask_to_set = ~0UL;
 173         p++;
 174     }
 175     if (nr) {
 176         mask_to_set &= BITMAP_LAST_WORD_MASK(size);
 177         *p |= mask_to_set;
 178     }
 179 }
 180
 181 void bitmap_set_atomic(unsigned long *map, long start, long nr)
 182 {
 183     unsigned long *p = map + BIT_WORD(start);
 184     const long size = start + nr;
 185     int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
 186     unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);
 187
 188     /* First word */
 189     if (nr - bits_to_set > 0) {
 190         atomic_or(p, mask_to_set);
 191         nr -= bits_to_set;
 192         bits_to_set = BITS_PER_LONG;
 193         mask_to_set = ~0UL;
 194         p++;
 195     }
 196
 197     /* Full words */
 198     if (bits_to_set == BITS_PER_LONG) {
 199         while (nr >= BITS_PER_LONG) {
 200             *p = ~0UL;
 201             nr -= BITS_PER_LONG;
 202             p++;
 203         }
 204     }
 205
 206     /* Last word */
 207     if (nr) {
 208         mask_to_set &= BITMAP_LAST_WORD_MASK(size);
 209         atomic_or(p, mask_to_set);
 210     } else {
 211         /* If we avoided the full barrier in atomic_or(), issue a
 212          * barrier to account for the assignments in the while loop.
 213          */
 214         smp_mb();
 215     }
 216 }
 217
 218 void bitmap_clear(unsigned long *map, long start, long nr)
 219 {
 220     unsigned long *p = map + BIT_WORD(start);
 221     const long size = start + nr;
 222     int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
 223     unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);
 224
 225     while (nr - bits_to_clear >= 0) {
 226         *p &= ~mask_to_clear;
 227         nr -= bits_to_clear;
 228         bits_to_clear = BITS_PER_LONG;
 229         mask_to_clear = ~0UL;
 230         p++;
 231     }
 232     if (nr) {
 233         mask_to_clear &= BITMAP_LAST_WORD_MASK(size);
 234         *p &= ~mask_to_clear;
 235     }
 236 }
 237
 238 bool bitmap_test_and_clear_atomic(unsigned long *map, long start, long nr)
 239 {
 240     unsigned long *p = map + BIT_WORD(start);
 241     const long size = start + nr;
 242     int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
 243     unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);
 244     unsigned long dirty = 0;
 245     unsigned long old_bits;
 246
 247     /* First word */
 248     if (nr - bits_to_clear > 0) {
 249         old_bits = atomic_fetch_and(p, ~mask_to_clear);
 250         dirty |= old_bits & mask_to_clear;
 251         nr -= bits_to_clear;
 252         bits_to_clear = BITS_PER_LONG;
 253         mask_to_clear = ~0UL;
 254         p++;
 255     }
 256
 257     /* Full words */
 258     if (bits_to_clear == BITS_PER_LONG) {
 259         while (nr >= BITS_PER_LONG) {
 260             if (*p) {
 261                 old_bits = atomic_xchg(p, 0);
 262                 dirty |= old_bits;
 263             }
 264             nr -= BITS_PER_LONG;
 265             p++;
 266         }
 267     }
 268
 269     /* Last word */
 270     if (nr) {
 271         mask_to_clear &= BITMAP_LAST_WORD_MASK(size);
 272         old_bits = atomic_fetch_and(p, ~mask_to_clear);
 273         dirty |= old_bits & mask_to_clear;
 274     } else {
 275         if (!dirty) {
 276             smp_mb();
 277         }
 278     }
 279
 280     return dirty != 0;
 281 }
 282
 283 #define ALIGN_MASK(x,mask)      (((x)+(mask))&~(mask))
 284
 285 /**
 286  * bitmap_find_next_zero_area - find a contiguous aligned zero area
 287  * @map: The address to base the search on
 288  * @size: The bitmap size in bits
 289  * @start: The bitnumber to start searching at
 290  * @nr: The number of zeroed bits we're looking for
 291  * @align_mask: Alignment mask for zero area
 292  *
 293  * The @align_mask should be one less than a power of 2; the effect is that
 294  * the bit offset of all zero areas this function finds is multiples of that
 295  * power of 2. A @align_mask of 0 means no alignment is required.
 296  */
 297 unsigned long bitmap_find_next_zero_area(unsigned long *map,
 298                                          unsigned long size,
 299                                          unsigned long start,
 300                                          unsigned long nr,
 301                                          unsigned long align_mask)
 302 {
 303     unsigned long index, end, i;
 304 again:
 305     index = find_next_zero_bit(map, size, start);
 306
 307     /* Align allocation */
 308     index = ALIGN_MASK(index, align_mask);
 309
 310     end = index + nr;
 311     if (end > size) {
 312         return end;
 313     }
 314     i = find_next_bit(map, end, index);
 315     if (i < end) {
 316         start = i + 1;
 317         goto again;
 318     }
 319     return index;
 320 }
 321
 322 int slow_bitmap_intersects(const unsigned long *bitmap1,
 323                            const unsigned long *bitmap2, long bits)
 324 {
 325     long k, lim = bits/BITS_PER_LONG;
 326
 327     for (k = 0; k < lim; ++k) {
 328         if (bitmap1[k] & bitmap2[k]) {
 329             return 1;
 330         }
 331     }
 332
 333     if (bits % BITS_PER_LONG) {
 334         if ((bitmap1[k] & bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits)) {
 335             return 1;
 336         }
 337     }
 338     return 0;
 339 }