lib/bitmap.c

   1 // SPDX-License-Identifier: GPL-2.0-only
   2 /*
   3  * lib/bitmap.c
   4  * Helper functions for bitmap.h.
   5  */
   6
   7 #include <linux/bitmap.h>
   8 #include <linux/bitops.h>
   9 #include <linux/ctype.h>
  10 #include <linux/device.h>
  11 #include <linux/errno.h>
  12 #include <linux/export.h>
  13 #include <linux/slab.h>
  14
  15 /**
  16  * DOC: bitmap introduction
  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  * The byte ordering of bitmaps is more natural on little
  33  * endian architectures.  See the big-endian headers
  34  * include/asm-ppc64/bitops.h and include/asm-s390/bitops.h
  35  * for the best explanations of this ordering.
  36  */
  37
  38 bool __bitmap_equal(const unsigned long *bitmap1,
  39                     const unsigned long *bitmap2, unsigned int bits)
  40 {
  41         unsigned int k, lim = bits/BITS_PER_LONG;
  42         for (k = 0; k < lim; ++k)
  43                 if (bitmap1[k] != bitmap2[k])
  44                         return false;
  45
  46         if (bits % BITS_PER_LONG)
  47                 if ((bitmap1[k] ^ bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))
  48                         return false;
  49
  50         return true;
  51 }
  52 EXPORT_SYMBOL(__bitmap_equal);
  53
  54 bool __bitmap_or_equal(const unsigned long *bitmap1,
  55                        const unsigned long *bitmap2,
  56                        const unsigned long *bitmap3,
  57                        unsigned int bits)
  58 {
  59         unsigned int k, lim = bits / BITS_PER_LONG;
  60         unsigned long tmp;
  61
  62         for (k = 0; k < lim; ++k) {
  63                 if ((bitmap1[k] | bitmap2[k]) != bitmap3[k])
  64                         return false;
  65         }
  66
  67         if (!(bits % BITS_PER_LONG))
  68                 return true;
  69
  70         tmp = (bitmap1[k] | bitmap2[k]) ^ bitmap3[k];
  71         return (tmp & BITMAP_LAST_WORD_MASK(bits)) == 0;
  72 }
  73
  74 void __bitmap_complement(unsigned long *dst, const unsigned long *src, unsigned int bits)
  75 {
  76         unsigned int k, lim = BITS_TO_LONGS(bits);
  77         for (k = 0; k < lim; ++k)
  78                 dst[k] = ~src[k];
  79 }
  80 EXPORT_SYMBOL(__bitmap_complement);
  81
  82 /**
  83  * __bitmap_shift_right - logical right shift of the bits in a bitmap
  84  *   @dst : destination bitmap
  85  *   @src : source bitmap
  86  *   @shift : shift by this many bits
  87  *   @nbits : bitmap size, in bits
  88  *
  89  * Shifting right (dividing) means moving bits in the MS -> LS bit
  90  * direction.  Zeros are fed into the vacated MS positions and the
  91  * LS bits shifted off the bottom are lost.
  92  */
  93 void __bitmap_shift_right(unsigned long *dst, const unsigned long *src,
  94                         unsigned shift, unsigned nbits)
  95 {
  96         unsigned k, lim = BITS_TO_LONGS(nbits);
  97         unsigned off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;
  98         unsigned long mask = BITMAP_LAST_WORD_MASK(nbits);
  99         for (k = 0; off + k < lim; ++k) {
 100                 unsigned long upper, lower;
 101
 102                 /*
 103                  * If shift is not word aligned, take lower rem bits of
 104                  * word above and make them the top rem bits of result.
 105                  */
 106                 if (!rem || off + k + 1 >= lim)
 107                         upper = 0;
 108                 else {
 109                         upper = src[off + k + 1];
 110                         if (off + k + 1 == lim - 1)
 111                                 upper &= mask;
 112                         upper <<= (BITS_PER_LONG - rem);
 113                 }
 114                 lower = src[off + k];
 115                 if (off + k == lim - 1)
 116                         lower &= mask;
 117                 lower >>= rem;
 118                 dst[k] = lower | upper;
 119         }
 120         if (off)
 121                 memset(&dst[lim - off], 0, off*sizeof(unsigned long));
 122 }
 123 EXPORT_SYMBOL(__bitmap_shift_right);
 124
 125
 126 /**
 127  * __bitmap_shift_left - logical left shift of the bits in a bitmap
 128  *   @dst : destination bitmap
 129  *   @src : source bitmap
 130  *   @shift : shift by this many bits
 131  *   @nbits : bitmap size, in bits
 132  *
 133  * Shifting left (multiplying) means moving bits in the LS -> MS
 134  * direction.  Zeros are fed into the vacated LS bit positions
 135  * and those MS bits shifted off the top are lost.
 136  */
 137
 138 void __bitmap_shift_left(unsigned long *dst, const unsigned long *src,
 139                         unsigned int shift, unsigned int nbits)
 140 {
 141         int k;
 142         unsigned int lim = BITS_TO_LONGS(nbits);
 143         unsigned int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;
 144         for (k = lim - off - 1; k >= 0; --k) {
 145                 unsigned long upper, lower;
 146
 147                 /*
 148                  * If shift is not word aligned, take upper rem bits of
 149                  * word below and make them the bottom rem bits of result.
 150                  */
 151                 if (rem && k > 0)
 152                         lower = src[k - 1] >> (BITS_PER_LONG - rem);
 153                 else
 154                         lower = 0;
 155                 upper = src[k] << rem;
 156                 dst[k + off] = lower | upper;
 157         }
 158         if (off)
 159                 memset(dst, 0, off*sizeof(unsigned long));
 160 }
 161 EXPORT_SYMBOL(__bitmap_shift_left);
 162
 163 /**
 164  * bitmap_cut() - remove bit region from bitmap and right shift remaining bits
 165  * @dst: destination bitmap, might overlap with src
 166  * @src: source bitmap
 167  * @first: start bit of region to be removed
 168  * @cut: number of bits to remove
 169  * @nbits: bitmap size, in bits
 170  *
 171  * Set the n-th bit of @dst iff the n-th bit of @src is set and
 172  * n is less than @first, or the m-th bit of @src is set for any
 173  * m such that @first <= n < nbits, and m = n + @cut.
 174  *
 175  * In pictures, example for a big-endian 32-bit architecture:
 176  *
 177  * The @src bitmap is::
 178  *
 179  *   31                                   63
 180  *   |                                    |
 181  *   10000000 11000001 11110010 00010101  10000000 11000001 01110010 00010101
 182  *                   |  |              |                                    |
 183  *                  16  14             0                                   32
 184  *
 185  * if @cut is 3, and @first is 14, bits 14-16 in @src are cut and @dst is::
 186  *
 187  *   31                                   63
 188  *   |                                    |
 189  *   10110000 00011000 00110010 00010101  00010000 00011000 00101110 01000010
 190  *                      |              |                                    |
 191  *                      14 (bit 17     0                                   32
 192  *                          from @src)
 193  *
 194  * Note that @dst and @src might overlap partially or entirely.
 195  *
 196  * This is implemented in the obvious way, with a shift and carry
 197  * step for each moved bit. Optimisation is left as an exercise
 198  * for the compiler.
 199  */
 200 void bitmap_cut(unsigned long *dst, const unsigned long *src,
 201                 unsigned int first, unsigned int cut, unsigned int nbits)
 202 {
 203         unsigned int len = BITS_TO_LONGS(nbits);
 204         unsigned long keep = 0, carry;
 205         int i;
 206
 207         if (first % BITS_PER_LONG) {
 208                 keep = src[first / BITS_PER_LONG] &
 209                        (~0UL >> (BITS_PER_LONG - first % BITS_PER_LONG));
 210         }
 211
 212         memmove(dst, src, len * sizeof(*dst));
 213
 214         while (cut--) {
 215                 for (i = first / BITS_PER_LONG; i < len; i++) {
 216                         if (i < len - 1)
 217                                 carry = dst[i + 1] & 1UL;
 218                         else
 219                                 carry = 0;
 220
 221                         dst[i] = (dst[i] >> 1) | (carry << (BITS_PER_LONG - 1));
 222                 }
 223         }
 224
 225         dst[first / BITS_PER_LONG] &= ~0UL << (first % BITS_PER_LONG);
 226         dst[first / BITS_PER_LONG] |= keep;
 227 }
 228 EXPORT_SYMBOL(bitmap_cut);
 229
 230 bool __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
 231                                 const unsigned long *bitmap2, unsigned int bits)
 232 {
 233         unsigned int k;
 234         unsigned int lim = bits/BITS_PER_LONG;
 235         unsigned long result = 0;
 236
 237         for (k = 0; k < lim; k++)
 238                 result |= (dst[k] = bitmap1[k] & bitmap2[k]);
 239         if (bits % BITS_PER_LONG)
 240                 result |= (dst[k] = bitmap1[k] & bitmap2[k] &
 241                            BITMAP_LAST_WORD_MASK(bits));
 242         return result != 0;
 243 }
 244 EXPORT_SYMBOL(__bitmap_and);
 245
 246 void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
 247                                 const unsigned long *bitmap2, unsigned int bits)
 248 {
 249         unsigned int k;
 250         unsigned int nr = BITS_TO_LONGS(bits);
 251
 252         for (k = 0; k < nr; k++)
 253                 dst[k] = bitmap1[k] | bitmap2[k];
 254 }
 255 EXPORT_SYMBOL(__bitmap_or);
 256
 257 void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
 258                                 const unsigned long *bitmap2, unsigned int bits)
 259 {
 260         unsigned int k;
 261         unsigned int nr = BITS_TO_LONGS(bits);
 262
 263         for (k = 0; k < nr; k++)
 264                 dst[k] = bitmap1[k] ^ bitmap2[k];
 265 }
 266 EXPORT_SYMBOL(__bitmap_xor);
 267
 268 bool __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
 269                                 const unsigned long *bitmap2, unsigned int bits)
 270 {
 271         unsigned int k;
 272         unsigned int lim = bits/BITS_PER_LONG;
 273         unsigned long result = 0;
 274
 275         for (k = 0; k < lim; k++)
 276                 result |= (dst[k] = bitmap1[k] & ~bitmap2[k]);
 277         if (bits % BITS_PER_LONG)
 278                 result |= (dst[k] = bitmap1[k] & ~bitmap2[k] &
 279                            BITMAP_LAST_WORD_MASK(bits));
 280         return result != 0;
 281 }
 282 EXPORT_SYMBOL(__bitmap_andnot);
 283
 284 void __bitmap_replace(unsigned long *dst,
 285                       const unsigned long *old, const unsigned long *new,
 286                       const unsigned long *mask, unsigned int nbits)
 287 {
 288         unsigned int k;
 289         unsigned int nr = BITS_TO_LONGS(nbits);
 290
 291         for (k = 0; k < nr; k++)
 292                 dst[k] = (old[k] & ~mask[k]) | (new[k] & mask[k]);
 293 }
 294 EXPORT_SYMBOL(__bitmap_replace);
 295
 296 bool __bitmap_intersects(const unsigned long *bitmap1,
 297                          const unsigned long *bitmap2, unsigned int bits)
 298 {
 299         unsigned int k, lim = bits/BITS_PER_LONG;
 300         for (k = 0; k < lim; ++k)
 301                 if (bitmap1[k] & bitmap2[k])
 302                         return true;
 303
 304         if (bits % BITS_PER_LONG)
 305                 if ((bitmap1[k] & bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))
 306                         return true;
 307         return false;
 308 }
 309 EXPORT_SYMBOL(__bitmap_intersects);
 310
 311 bool __bitmap_subset(const unsigned long *bitmap1,
 312                      const unsigned long *bitmap2, unsigned int bits)
 313 {
 314         unsigned int k, lim = bits/BITS_PER_LONG;
 315         for (k = 0; k < lim; ++k)
 316                 if (bitmap1[k] & ~bitmap2[k])
 317                         return false;
 318
 319         if (bits % BITS_PER_LONG)
 320                 if ((bitmap1[k] & ~bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))
 321                         return false;
 322         return true;
 323 }
 324 EXPORT_SYMBOL(__bitmap_subset);
 325
 326 #define BITMAP_WEIGHT(FETCH, bits)      \
 327 ({                                                                              \
 328         unsigned int __bits = (bits), idx, w = 0;                               \
 329                                                                                 \
 330         for (idx = 0; idx < __bits / BITS_PER_LONG; idx++)                      \
 331                 w += hweight_long(FETCH);                                       \
 332                                                                                 \
 333         if (__bits % BITS_PER_LONG)                                             \
 334                 w += hweight_long((FETCH) & BITMAP_LAST_WORD_MASK(__bits));     \
 335                                                                                 \
 336         w;                                                                      \
 337 })
 338
 339 unsigned int __bitmap_weight(const unsigned long *bitmap, unsigned int bits)
 340 {
 341         return BITMAP_WEIGHT(bitmap[idx], bits);
 342 }
 343 EXPORT_SYMBOL(__bitmap_weight);
 344
 345 unsigned int __bitmap_weight_and(const unsigned long *bitmap1,
 346                                 const unsigned long *bitmap2, unsigned int bits)
 347 {
 348         return BITMAP_WEIGHT(bitmap1[idx] & bitmap2[idx], bits);
 349 }
 350 EXPORT_SYMBOL(__bitmap_weight_and);
 351
 352 void __bitmap_set(unsigned long *map, unsigned int start, int len)
 353 {
 354         unsigned long *p = map + BIT_WORD(start);
 355         const unsigned int size = start + len;
 356         int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
 357         unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);
 358
 359         while (len - bits_to_set >= 0) {
 360                 *p |= mask_to_set;
 361                 len -= bits_to_set;
 362                 bits_to_set = BITS_PER_LONG;
 363                 mask_to_set = ~0UL;
 364                 p++;
 365         }
 366         if (len) {
 367                 mask_to_set &= BITMAP_LAST_WORD_MASK(size);
 368                 *p |= mask_to_set;
 369         }
 370 }
 371 EXPORT_SYMBOL(__bitmap_set);
 372
 373 void __bitmap_clear(unsigned long *map, unsigned int start, int len)
 374 {
 375         unsigned long *p = map + BIT_WORD(start);
 376         const unsigned int size = start + len;
 377         int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
 378         unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);
 379
 380         while (len - bits_to_clear >= 0) {
 381                 *p &= ~mask_to_clear;
 382                 len -= bits_to_clear;
 383                 bits_to_clear = BITS_PER_LONG;
 384                 mask_to_clear = ~0UL;
 385                 p++;
 386         }
 387         if (len) {
 388                 mask_to_clear &= BITMAP_LAST_WORD_MASK(size);
 389                 *p &= ~mask_to_clear;
 390         }
 391 }
 392 EXPORT_SYMBOL(__bitmap_clear);
 393
 394 /**
 395  * bitmap_find_next_zero_area_off - find a contiguous aligned zero area
 396  * @map: The address to base the search on
 397  * @size: The bitmap size in bits
 398  * @start: The bitnumber to start searching at
 399  * @nr: The number of zeroed bits we're looking for
 400  * @align_mask: Alignment mask for zero area
 401  * @align_offset: Alignment offset for zero area.
 402  *
 403  * The @align_mask should be one less than a power of 2; the effect is that
 404  * the bit offset of all zero areas this function finds plus @align_offset
 405  * is multiple of that power of 2.
 406  */
 407 unsigned long bitmap_find_next_zero_area_off(unsigned long *map,
 408                                              unsigned long size,
 409                                              unsigned long start,
 410                                              unsigned int nr,
 411                                              unsigned long align_mask,
 412                                              unsigned long align_offset)
 413 {
 414         unsigned long index, end, i;
 415 again:
 416         index = find_next_zero_bit(map, size, start);
 417
 418         /* Align allocation */
 419         index = __ALIGN_MASK(index + align_offset, align_mask) - align_offset;
 420
 421         end = index + nr;
 422         if (end > size)
 423                 return end;
 424         i = find_next_bit(map, end, index);
 425         if (i < end) {
 426                 start = i + 1;
 427                 goto again;
 428         }
 429         return index;
 430 }
 431 EXPORT_SYMBOL(bitmap_find_next_zero_area_off);
 432
 433 /**
 434  * bitmap_pos_to_ord - find ordinal of set bit at given position in bitmap
 435  *      @buf: pointer to a bitmap
 436  *      @pos: a bit position in @buf (0 <= @pos < @nbits)
 437  *      @nbits: number of valid bit positions in @buf
 438  *
 439  * Map the bit at position @pos in @buf (of length @nbits) to the
 440  * ordinal of which set bit it is.  If it is not set or if @pos
 441  * is not a valid bit position, map to -1.
 442  *
 443  * If for example, just bits 4 through 7 are set in @buf, then @pos
 444  * values 4 through 7 will get mapped to 0 through 3, respectively,
 445  * and other @pos values will get mapped to -1.  When @pos value 7
 446  * gets mapped to (returns) @ord value 3 in this example, that means
 447  * that bit 7 is the 3rd (starting with 0th) set bit in @buf.
 448  *
 449  * The bit positions 0 through @bits are valid positions in @buf.
 450  */
 451 static int bitmap_pos_to_ord(const unsigned long *buf, unsigned int pos, unsigned int nbits)
 452 {
 453         if (pos >= nbits || !test_bit(pos, buf))
 454                 return -1;
 455
 456         return bitmap_weight(buf, pos);
 457 }
 458
 459 /**
 460  * bitmap_remap - Apply map defined by a pair of bitmaps to another bitmap
 461  *      @dst: remapped result
 462  *      @src: subset to be remapped
 463  *      @old: defines domain of map
 464  *      @new: defines range of map
 465  *      @nbits: number of bits in each of these bitmaps
 466  *
 467  * Let @old and @new define a mapping of bit positions, such that
 468  * whatever position is held by the n-th set bit in @old is mapped
 469  * to the n-th set bit in @new.  In the more general case, allowing
 470  * for the possibility that the weight 'w' of @new is less than the
 471  * weight of @old, map the position of the n-th set bit in @old to
 472  * the position of the m-th set bit in @new, where m == n % w.
 473  *
 474  * If either of the @old and @new bitmaps are empty, or if @src and
 475  * @dst point to the same location, then this routine copies @src
 476  * to @dst.
 477  *
 478  * The positions of unset bits in @old are mapped to themselves
 479  * (the identity map).
 480  *
 481  * Apply the above specified mapping to @src, placing the result in
 482  * @dst, clearing any bits previously set in @dst.
 483  *
 484  * For example, lets say that @old has bits 4 through 7 set, and
 485  * @new has bits 12 through 15 set.  This defines the mapping of bit
 486  * position 4 to 12, 5 to 13, 6 to 14 and 7 to 15, and of all other
 487  * bit positions unchanged.  So if say @src comes into this routine
 488  * with bits 1, 5 and 7 set, then @dst should leave with bits 1,
 489  * 13 and 15 set.
 490  */
 491 void bitmap_remap(unsigned long *dst, const unsigned long *src,
 492                 const unsigned long *old, const unsigned long *new,
 493                 unsigned int nbits)
 494 {
 495         unsigned int oldbit, w;
 496
 497         if (dst == src)         /* following doesn't handle inplace remaps */
 498                 return;
 499         bitmap_zero(dst, nbits);
 500
 501         w = bitmap_weight(new, nbits);
 502         for_each_set_bit(oldbit, src, nbits) {
 503                 int n = bitmap_pos_to_ord(old, oldbit, nbits);
 504
 505                 if (n < 0 || w == 0)
 506                         set_bit(oldbit, dst);   /* identity map */
 507                 else
 508                         set_bit(find_nth_bit(new, nbits, n % w), dst);
 509         }
 510 }
 511 EXPORT_SYMBOL(bitmap_remap);
 512
 513 /**
 514  * bitmap_bitremap - Apply map defined by a pair of bitmaps to a single bit
 515  *      @oldbit: bit position to be mapped
 516  *      @old: defines domain of map
 517  *      @new: defines range of map
 518  *      @bits: number of bits in each of these bitmaps
 519  *
 520  * Let @old and @new define a mapping of bit positions, such that
 521  * whatever position is held by the n-th set bit in @old is mapped
 522  * to the n-th set bit in @new.  In the more general case, allowing
 523  * for the possibility that the weight 'w' of @new is less than the
 524  * weight of @old, map the position of the n-th set bit in @old to
 525  * the position of the m-th set bit in @new, where m == n % w.
 526  *
 527  * The positions of unset bits in @old are mapped to themselves
 528  * (the identity map).
 529  *
 530  * Apply the above specified mapping to bit position @oldbit, returning
 531  * the new bit position.
 532  *
 533  * For example, lets say that @old has bits 4 through 7 set, and
 534  * @new has bits 12 through 15 set.  This defines the mapping of bit
 535  * position 4 to 12, 5 to 13, 6 to 14 and 7 to 15, and of all other
 536  * bit positions unchanged.  So if say @oldbit is 5, then this routine
 537  * returns 13.
 538  */
 539 int bitmap_bitremap(int oldbit, const unsigned long *old,
 540                                 const unsigned long *new, int bits)
 541 {
 542         int w = bitmap_weight(new, bits);
 543         int n = bitmap_pos_to_ord(old, oldbit, bits);
 544         if (n < 0 || w == 0)
 545                 return oldbit;
 546         else
 547                 return find_nth_bit(new, bits, n % w);
 548 }
 549 EXPORT_SYMBOL(bitmap_bitremap);
 550
 551 #ifdef CONFIG_NUMA
 552 /**
 553  * bitmap_onto - translate one bitmap relative to another
 554  *      @dst: resulting translated bitmap
 555  *      @orig: original untranslated bitmap
 556  *      @relmap: bitmap relative to which translated
 557  *      @bits: number of bits in each of these bitmaps
 558  *
 559  * Set the n-th bit of @dst iff there exists some m such that the
 560  * n-th bit of @relmap is set, the m-th bit of @orig is set, and
 561  * the n-th bit of @relmap is also the m-th _set_ bit of @relmap.
 562  * (If you understood the previous sentence the first time your
 563  * read it, you're overqualified for your current job.)
 564  *
 565  * In other words, @orig is mapped onto (surjectively) @dst,
 566  * using the map { <n, m> | the n-th bit of @relmap is the
 567  * m-th set bit of @relmap }.
 568  *
 569  * Any set bits in @orig above bit number W, where W is the
 570  * weight of (number of set bits in) @relmap are mapped nowhere.
 571  * In particular, if for all bits m set in @orig, m >= W, then
 572  * @dst will end up empty.  In situations where the possibility
 573  * of such an empty result is not desired, one way to avoid it is
 574  * to use the bitmap_fold() operator, below, to first fold the
 575  * @orig bitmap over itself so that all its set bits x are in the
 576  * range 0 <= x < W.  The bitmap_fold() operator does this by
 577  * setting the bit (m % W) in @dst, for each bit (m) set in @orig.
 578  *
 579  * Example [1] for bitmap_onto():
 580  *  Let's say @relmap has bits 30-39 set, and @orig has bits
 581  *  1, 3, 5, 7, 9 and 11 set.  Then on return from this routine,
 582  *  @dst will have bits 31, 33, 35, 37 and 39 set.
 583  *
 584  *  When bit 0 is set in @orig, it means turn on the bit in
 585  *  @dst corresponding to whatever is the first bit (if any)
 586  *  that is turned on in @relmap.  Since bit 0 was off in the
 587  *  above example, we leave off that bit (bit 30) in @dst.
 588  *
 589  *  When bit 1 is set in @orig (as in the above example), it
 590  *  means turn on the bit in @dst corresponding to whatever
 591  *  is the second bit that is turned on in @relmap.  The second
 592  *  bit in @relmap that was turned on in the above example was
 593  *  bit 31, so we turned on bit 31 in @dst.
 594  *
 595  *  Similarly, we turned on bits 33, 35, 37 and 39 in @dst,
 596  *  because they were the 4th, 6th, 8th and 10th set bits
 597  *  set in @relmap, and the 4th, 6th, 8th and 10th bits of
 598  *  @orig (i.e. bits 3, 5, 7 and 9) were also set.
 599  *
 600  *  When bit 11 is set in @orig, it means turn on the bit in
 601  *  @dst corresponding to whatever is the twelfth bit that is
 602  *  turned on in @relmap.  In the above example, there were
 603  *  only ten bits turned on in @relmap (30..39), so that bit
 604  *  11 was set in @orig had no affect on @dst.
 605  *
 606  * Example [2] for bitmap_fold() + bitmap_onto():
 607  *  Let's say @relmap has these ten bits set::
 608  *
 609  *              40 41 42 43 45 48 53 61 74 95
 610  *
 611  *  (for the curious, that's 40 plus the first ten terms of the
 612  *  Fibonacci sequence.)
 613  *
 614  *  Further lets say we use the following code, invoking
 615  *  bitmap_fold() then bitmap_onto, as suggested above to
 616  *  avoid the possibility of an empty @dst result::
 617  *
 618  *      unsigned long *tmp;     // a temporary bitmap's bits
 619  *
 620  *      bitmap_fold(tmp, orig, bitmap_weight(relmap, bits), bits);
 621  *      bitmap_onto(dst, tmp, relmap, bits);
 622  *
 623  *  Then this table shows what various values of @dst would be, for
 624  *  various @orig's.  I list the zero-based positions of each set bit.
 625  *  The tmp column shows the intermediate result, as computed by
 626  *  using bitmap_fold() to fold the @orig bitmap modulo ten
 627  *  (the weight of @relmap):
 628  *
 629  *      =============== ============== =================
 630  *      @orig           tmp            @dst
 631  *      0                0             40
 632  *      1                1             41
 633  *      9                9             95
 634  *      10               0             40 [#f1]_
 635  *      1 3 5 7          1 3 5 7       41 43 48 61
 636  *      0 1 2 3 4        0 1 2 3 4     40 41 42 43 45
 637  *      0 9 18 27        0 9 8 7       40 61 74 95
 638  *      0 10 20 30       0             40
 639  *      0 11 22 33       0 1 2 3       40 41 42 43
 640  *      0 12 24 36       0 2 4 6       40 42 45 53
 641  *      78 102 211       1 2 8         41 42 74 [#f1]_
 642  *      =============== ============== =================
 643  *
 644  * .. [#f1]
 645  *
 646  *     For these marked lines, if we hadn't first done bitmap_fold()
 647  *     into tmp, then the @dst result would have been empty.
 648  *
 649  * If either of @orig or @relmap is empty (no set bits), then @dst
 650  * will be returned empty.
 651  *
 652  * If (as explained above) the only set bits in @orig are in positions
 653  * m where m >= W, (where W is the weight of @relmap) then @dst will
 654  * once again be returned empty.
 655  *
 656  * All bits in @dst not set by the above rule are cleared.
 657  */
 658 void bitmap_onto(unsigned long *dst, const unsigned long *orig,
 659                         const unsigned long *relmap, unsigned int bits)
 660 {
 661         unsigned int n, m;      /* same meaning as in above comment */
 662
 663         if (dst == orig)        /* following doesn't handle inplace mappings */
 664                 return;
 665         bitmap_zero(dst, bits);
 666
 667         /*
 668          * The following code is a more efficient, but less
 669          * obvious, equivalent to the loop:
 670          *      for (m = 0; m < bitmap_weight(relmap, bits); m++) {
 671          *              n = find_nth_bit(orig, bits, m);
 672          *              if (test_bit(m, orig))
 673          *                      set_bit(n, dst);
 674          *      }
 675          */
 676
 677         m = 0;
 678         for_each_set_bit(n, relmap, bits) {
 679                 /* m == bitmap_pos_to_ord(relmap, n, bits) */
 680                 if (test_bit(m, orig))
 681                         set_bit(n, dst);
 682                 m++;
 683         }
 684 }
 685
 686 /**
 687  * bitmap_fold - fold larger bitmap into smaller, modulo specified size
 688  *      @dst: resulting smaller bitmap
 689  *      @orig: original larger bitmap
 690  *      @sz: specified size
 691  *      @nbits: number of bits in each of these bitmaps
 692  *
 693  * For each bit oldbit in @orig, set bit oldbit mod @sz in @dst.
 694  * Clear all other bits in @dst.  See further the comment and
 695  * Example [2] for bitmap_onto() for why and how to use this.
 696  */
 697 void bitmap_fold(unsigned long *dst, const unsigned long *orig,
 698                         unsigned int sz, unsigned int nbits)
 699 {
 700         unsigned int oldbit;
 701
 702         if (dst == orig)        /* following doesn't handle inplace mappings */
 703                 return;
 704         bitmap_zero(dst, nbits);
 705
 706         for_each_set_bit(oldbit, orig, nbits)
 707                 set_bit(oldbit % sz, dst);
 708 }
 709 #endif /* CONFIG_NUMA */
 710
 711 /*
 712  * Common code for bitmap_*_region() routines.
 713  *      bitmap: array of unsigned longs corresponding to the bitmap
 714  *      pos: the beginning of the region
 715  *      order: region size (log base 2 of number of bits)
 716  *      reg_op: operation(s) to perform on that region of bitmap
 717  *
 718  * Can set, verify and/or release a region of bits in a bitmap,
 719  * depending on which combination of REG_OP_* flag bits is set.
 720  *
 721  * A region of a bitmap is a sequence of bits in the bitmap, of
 722  * some size '1 << order' (a power of two), aligned to that same
 723  * '1 << order' power of two.
 724  *
 725  * Returns 1 if REG_OP_ISFREE succeeds (region is all zero bits).
 726  * Returns 0 in all other cases and reg_ops.
 727  */
 728
 729 enum {
 730         REG_OP_ISFREE,          /* true if region is all zero bits */
 731         REG_OP_ALLOC,           /* set all bits in region */
 732         REG_OP_RELEASE,         /* clear all bits in region */
 733 };
 734
 735 static int __reg_op(unsigned long *bitmap, unsigned int pos, int order, int reg_op)
 736 {
 737         int nbits_reg;          /* number of bits in region */
 738         int index;              /* index first long of region in bitmap */
 739         int offset;             /* bit offset region in bitmap[index] */
 740         int nlongs_reg;         /* num longs spanned by region in bitmap */
 741         int nbitsinlong;        /* num bits of region in each spanned long */
 742         unsigned long mask;     /* bitmask for one long of region */
 743         int i;                  /* scans bitmap by longs */
 744         int ret = 0;            /* return value */
 745
 746         /*
 747          * Either nlongs_reg == 1 (for small orders that fit in one long)
 748          * or (offset == 0 && mask == ~0UL) (for larger multiword orders.)
 749          */
 750         nbits_reg = 1 << order;
 751         index = pos / BITS_PER_LONG;
 752         offset = pos - (index * BITS_PER_LONG);
 753         nlongs_reg = BITS_TO_LONGS(nbits_reg);
 754         nbitsinlong = min(nbits_reg,  BITS_PER_LONG);
 755
 756         /*
 757          * Can't do "mask = (1UL << nbitsinlong) - 1", as that
 758          * overflows if nbitsinlong == BITS_PER_LONG.
 759          */
 760         mask = (1UL << (nbitsinlong - 1));
 761         mask += mask - 1;
 762         mask <<= offset;
 763
 764         switch (reg_op) {
 765         case REG_OP_ISFREE:
 766                 for (i = 0; i < nlongs_reg; i++) {
 767                         if (bitmap[index + i] & mask)
 768                                 goto done;
 769                 }
 770                 ret = 1;        /* all bits in region free (zero) */
 771                 break;
 772
 773         case REG_OP_ALLOC:
 774                 for (i = 0; i < nlongs_reg; i++)
 775                         bitmap[index + i] |= mask;
 776                 break;
 777
 778         case REG_OP_RELEASE:
 779                 for (i = 0; i < nlongs_reg; i++)
 780                         bitmap[index + i] &= ~mask;
 781                 break;
 782         }
 783 done:
 784         return ret;
 785 }
 786
 787 /**
 788  * bitmap_find_free_region - find a contiguous aligned mem region
 789  *      @bitmap: array of unsigned longs corresponding to the bitmap
 790  *      @bits: number of bits in the bitmap
 791  *      @order: region size (log base 2 of number of bits) to find
 792  *
 793  * Find a region of free (zero) bits in a @bitmap of @bits bits and
 794  * allocate them (set them to one).  Only consider regions of length
 795  * a power (@order) of two, aligned to that power of two, which
 796  * makes the search algorithm much faster.
 797  *
 798  * Return the bit offset in bitmap of the allocated region,
 799  * or -errno on failure.
 800  */
 801 int bitmap_find_free_region(unsigned long *bitmap, unsigned int bits, int order)
 802 {
 803         unsigned int pos, end;          /* scans bitmap by regions of size order */
 804
 805         for (pos = 0 ; (end = pos + (1U << order)) <= bits; pos = end) {
 806                 if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE))
 807                         continue;
 808                 __reg_op(bitmap, pos, order, REG_OP_ALLOC);
 809                 return pos;
 810         }
 811         return -ENOMEM;
 812 }
 813 EXPORT_SYMBOL(bitmap_find_free_region);
 814
 815 /**
 816  * bitmap_release_region - release allocated bitmap region
 817  *      @bitmap: array of unsigned longs corresponding to the bitmap
 818  *      @pos: beginning of bit region to release
 819  *      @order: region size (log base 2 of number of bits) to release
 820  *
 821  * This is the complement to __bitmap_find_free_region() and releases
 822  * the found region (by clearing it in the bitmap).
 823  *
 824  * No return value.
 825  */
 826 void bitmap_release_region(unsigned long *bitmap, unsigned int pos, int order)
 827 {
 828         __reg_op(bitmap, pos, order, REG_OP_RELEASE);
 829 }
 830 EXPORT_SYMBOL(bitmap_release_region);
 831
 832 /**
 833  * bitmap_allocate_region - allocate bitmap region
 834  *      @bitmap: array of unsigned longs corresponding to the bitmap
 835  *      @pos: beginning of bit region to allocate
 836  *      @order: region size (log base 2 of number of bits) to allocate
 837  *
 838  * Allocate (set bits in) a specified region of a bitmap.
 839  *
 840  * Return 0 on success, or %-EBUSY if specified region wasn't
 841  * free (not all bits were zero).
 842  */
 843 int bitmap_allocate_region(unsigned long *bitmap, unsigned int pos, int order)
 844 {
 845         if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE))
 846                 return -EBUSY;
 847         return __reg_op(bitmap, pos, order, REG_OP_ALLOC);
 848 }
 849 EXPORT_SYMBOL(bitmap_allocate_region);
 850
 851 unsigned long *bitmap_alloc(unsigned int nbits, gfp_t flags)
 852 {
 853         return kmalloc_array(BITS_TO_LONGS(nbits), sizeof(unsigned long),
 854                              flags);
 855 }
 856 EXPORT_SYMBOL(bitmap_alloc);
 857
 858 unsigned long *bitmap_zalloc(unsigned int nbits, gfp_t flags)
 859 {
 860         return bitmap_alloc(nbits, flags | __GFP_ZERO);
 861 }
 862 EXPORT_SYMBOL(bitmap_zalloc);
 863
 864 unsigned long *bitmap_alloc_node(unsigned int nbits, gfp_t flags, int node)
 865 {
 866         return kmalloc_array_node(BITS_TO_LONGS(nbits), sizeof(unsigned long),
 867                                   flags, node);
 868 }
 869 EXPORT_SYMBOL(bitmap_alloc_node);
 870
 871 unsigned long *bitmap_zalloc_node(unsigned int nbits, gfp_t flags, int node)
 872 {
 873         return bitmap_alloc_node(nbits, flags | __GFP_ZERO, node);
 874 }
 875 EXPORT_SYMBOL(bitmap_zalloc_node);
 876
 877 void bitmap_free(const unsigned long *bitmap)
 878 {
 879         kfree(bitmap);
 880 }
 881 EXPORT_SYMBOL(bitmap_free);
 882
 883 static void devm_bitmap_free(void *data)
 884 {
 885         unsigned long *bitmap = data;
 886
 887         bitmap_free(bitmap);
 888 }
 889
 890 unsigned long *devm_bitmap_alloc(struct device *dev,
 891                                  unsigned int nbits, gfp_t flags)
 892 {
 893         unsigned long *bitmap;
 894         int ret;
 895
 896         bitmap = bitmap_alloc(nbits, flags);
 897         if (!bitmap)
 898                 return NULL;
 899
 900         ret = devm_add_action_or_reset(dev, devm_bitmap_free, bitmap);
 901         if (ret)
 902                 return NULL;
 903
 904         return bitmap;
 905 }
 906 EXPORT_SYMBOL_GPL(devm_bitmap_alloc);
 907
 908 unsigned long *devm_bitmap_zalloc(struct device *dev,
 909                                   unsigned int nbits, gfp_t flags)
 910 {
 911         return devm_bitmap_alloc(dev, nbits, flags | __GFP_ZERO);
 912 }
 913 EXPORT_SYMBOL_GPL(devm_bitmap_zalloc);
 914
 915 #if BITS_PER_LONG == 64
 916 /**
 917  * bitmap_from_arr32 - copy the contents of u32 array of bits to bitmap
 918  *      @bitmap: array of unsigned longs, the destination bitmap
 919  *      @buf: array of u32 (in host byte order), the source bitmap
 920  *      @nbits: number of bits in @bitmap
 921  */
 922 void bitmap_from_arr32(unsigned long *bitmap, const u32 *buf, unsigned int nbits)
 923 {
 924         unsigned int i, halfwords;
 925
 926         halfwords = DIV_ROUND_UP(nbits, 32);
 927         for (i = 0; i < halfwords; i++) {
 928                 bitmap[i/2] = (unsigned long) buf[i];
 929                 if (++i < halfwords)
 930                         bitmap[i/2] |= ((unsigned long) buf[i]) << 32;
 931         }
 932
 933         /* Clear tail bits in last word beyond nbits. */
 934         if (nbits % BITS_PER_LONG)
 935                 bitmap[(halfwords - 1) / 2] &= BITMAP_LAST_WORD_MASK(nbits);
 936 }
 937 EXPORT_SYMBOL(bitmap_from_arr32);
 938
 939 /**
 940  * bitmap_to_arr32 - copy the contents of bitmap to a u32 array of bits
 941  *      @buf: array of u32 (in host byte order), the dest bitmap
 942  *      @bitmap: array of unsigned longs, the source bitmap
 943  *      @nbits: number of bits in @bitmap
 944  */
 945 void bitmap_to_arr32(u32 *buf, const unsigned long *bitmap, unsigned int nbits)
 946 {
 947         unsigned int i, halfwords;
 948
 949         halfwords = DIV_ROUND_UP(nbits, 32);
 950         for (i = 0; i < halfwords; i++) {
 951                 buf[i] = (u32) (bitmap[i/2] & UINT_MAX);
 952                 if (++i < halfwords)
 953                         buf[i] = (u32) (bitmap[i/2] >> 32);
 954         }
 955
 956         /* Clear tail bits in last element of array beyond nbits. */
 957         if (nbits % BITS_PER_LONG)
 958                 buf[halfwords - 1] &= (u32) (UINT_MAX >> ((-nbits) & 31));
 959 }
 960 EXPORT_SYMBOL(bitmap_to_arr32);
 961 #endif
 962
 963 #if BITS_PER_LONG == 32
 964 /**
 965  * bitmap_from_arr64 - copy the contents of u64 array of bits to bitmap
 966  *      @bitmap: array of unsigned longs, the destination bitmap
 967  *      @buf: array of u64 (in host byte order), the source bitmap
 968  *      @nbits: number of bits in @bitmap
 969  */
 970 void bitmap_from_arr64(unsigned long *bitmap, const u64 *buf, unsigned int nbits)
 971 {
 972         int n;
 973
 974         for (n = nbits; n > 0; n -= 64) {
 975                 u64 val = *buf++;
 976
 977                 *bitmap++ = val;
 978                 if (n > 32)
 979                         *bitmap++ = val >> 32;
 980         }
 981
 982         /*
 983          * Clear tail bits in the last word beyond nbits.
 984          *
 985          * Negative index is OK because here we point to the word next
 986          * to the last word of the bitmap, except for nbits == 0, which
 987          * is tested implicitly.
 988          */
 989         if (nbits % BITS_PER_LONG)
 990                 bitmap[-1] &= BITMAP_LAST_WORD_MASK(nbits);
 991 }
 992 EXPORT_SYMBOL(bitmap_from_arr64);
 993
 994 /**
 995  * bitmap_to_arr64 - copy the contents of bitmap to a u64 array of bits
 996  *      @buf: array of u64 (in host byte order), the dest bitmap
 997  *      @bitmap: array of unsigned longs, the source bitmap
 998  *      @nbits: number of bits in @bitmap
 999  */
1000 void bitmap_to_arr64(u64 *buf, const unsigned long *bitmap, unsigned int nbits)
1001 {
1002         const unsigned long *end = bitmap + BITS_TO_LONGS(nbits);
1003
1004         while (bitmap < end) {
1005                 *buf = *bitmap++;
1006                 if (bitmap < end)
1007                         *buf |= (u64)(*bitmap++) << 32;
1008                 buf++;
1009         }
1010
1011         /* Clear tail bits in the last element of array beyond nbits. */
1012         if (nbits % 64)
1013                 buf[-1] &= GENMASK_ULL((nbits - 1) % 64, 0);
1014 }
1015 EXPORT_SYMBOL(bitmap_to_arr64);
1016 #endif