root/lib/bitmap.c

/* [<][>][^][v][top][bottom][index][help] */

DEFINITIONS

This source file includes following definitions.
  1. __bitmap_equal
  2. __bitmap_or_equal
  3. __bitmap_complement
  4. __bitmap_shift_right
  5. __bitmap_shift_left
  6. __bitmap_and
  7. __bitmap_or
  8. __bitmap_xor
  9. __bitmap_andnot
  10. __bitmap_intersects
  11. __bitmap_subset
  12. __bitmap_weight
  13. __bitmap_set
  14. __bitmap_clear
  15. bitmap_find_next_zero_area_off
  16. __bitmap_parse
  17. bitmap_parse_user
  18. bitmap_print_to_pagebuf
  19. bitmap_set_region
  20. bitmap_check_region
  21. bitmap_getnum
  22. end_of_str
  23. __end_of_region
  24. end_of_region
  25. bitmap_find_region
  26. bitmap_parse_region
  27. bitmap_parselist
  28. bitmap_parselist_user
  29. bitmap_pos_to_ord
  30. bitmap_ord_to_pos
  31. bitmap_remap
  32. bitmap_bitremap
  33. bitmap_onto
  34. bitmap_fold
  35. __reg_op
  36. bitmap_find_free_region
  37. bitmap_release_region
  38. bitmap_allocate_region
  39. bitmap_copy_le
  40. bitmap_alloc
  41. bitmap_zalloc
  42. bitmap_free
  43. bitmap_from_arr32
  44. bitmap_to_arr32

   1 // SPDX-License-Identifier: GPL-2.0-only
   2 /*
   3  * lib/bitmap.c
   4  * Helper functions for bitmap.h.
   5  */
   6 #include <linux/export.h>
   7 #include <linux/thread_info.h>
   8 #include <linux/ctype.h>
   9 #include <linux/errno.h>
  10 #include <linux/bitmap.h>
  11 #include <linux/bitops.h>
  12 #include <linux/bug.h>
  13 #include <linux/kernel.h>
  14 #include <linux/mm.h>
  15 #include <linux/slab.h>
  16 #include <linux/string.h>
  17 #include <linux/uaccess.h>
  18 
  19 #include <asm/page.h>
  20 
  21 #include "kstrtox.h"
  22 
  23 /**
  24  * DOC: bitmap introduction
  25  *
  26  * bitmaps provide an array of bits, implemented using an an
  27  * array of unsigned longs.  The number of valid bits in a
  28  * given bitmap does _not_ need to be an exact multiple of
  29  * BITS_PER_LONG.
  30  *
  31  * The possible unused bits in the last, partially used word
  32  * of a bitmap are 'don't care'.  The implementation makes
  33  * no particular effort to keep them zero.  It ensures that
  34  * their value will not affect the results of any operation.
  35  * The bitmap operations that return Boolean (bitmap_empty,
  36  * for example) or scalar (bitmap_weight, for example) results
  37  * carefully filter out these unused bits from impacting their
  38  * results.
  39  *
  40  * The byte ordering of bitmaps is more natural on little
  41  * endian architectures.  See the big-endian headers
  42  * include/asm-ppc64/bitops.h and include/asm-s390/bitops.h
  43  * for the best explanations of this ordering.
  44  */
  45 
  46 int __bitmap_equal(const unsigned long *bitmap1,
  47                 const unsigned long *bitmap2, unsigned int bits)
  48 {
  49         unsigned int k, lim = bits/BITS_PER_LONG;
  50         for (k = 0; k < lim; ++k)
  51                 if (bitmap1[k] != bitmap2[k])
  52                         return 0;
  53 
  54         if (bits % BITS_PER_LONG)
  55                 if ((bitmap1[k] ^ bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))
  56                         return 0;
  57 
  58         return 1;
  59 }
  60 EXPORT_SYMBOL(__bitmap_equal);
  61 
  62 bool __bitmap_or_equal(const unsigned long *bitmap1,
  63                        const unsigned long *bitmap2,
  64                        const unsigned long *bitmap3,
  65                        unsigned int bits)
  66 {
  67         unsigned int k, lim = bits / BITS_PER_LONG;
  68         unsigned long tmp;
  69 
  70         for (k = 0; k < lim; ++k) {
  71                 if ((bitmap1[k] | bitmap2[k]) != bitmap3[k])
  72                         return false;
  73         }
  74 
  75         if (!(bits % BITS_PER_LONG))
  76                 return true;
  77 
  78         tmp = (bitmap1[k] | bitmap2[k]) ^ bitmap3[k];
  79         return (tmp & BITMAP_LAST_WORD_MASK(bits)) == 0;
  80 }
  81 
  82 void __bitmap_complement(unsigned long *dst, const unsigned long *src, unsigned int bits)
  83 {
  84         unsigned int k, lim = BITS_TO_LONGS(bits);
  85         for (k = 0; k < lim; ++k)
  86                 dst[k] = ~src[k];
  87 }
  88 EXPORT_SYMBOL(__bitmap_complement);
  89 
  90 /**
  91  * __bitmap_shift_right - logical right shift of the bits in a bitmap
  92  *   @dst : destination bitmap
  93  *   @src : source bitmap
  94  *   @shift : shift by this many bits
  95  *   @nbits : bitmap size, in bits
  96  *
  97  * Shifting right (dividing) means moving bits in the MS -> LS bit
  98  * direction.  Zeros are fed into the vacated MS positions and the
  99  * LS bits shifted off the bottom are lost.
 100  */
 101 void __bitmap_shift_right(unsigned long *dst, const unsigned long *src,
 102                         unsigned shift, unsigned nbits)
 103 {
 104         unsigned k, lim = BITS_TO_LONGS(nbits);
 105         unsigned off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;
 106         unsigned long mask = BITMAP_LAST_WORD_MASK(nbits);
 107         for (k = 0; off + k < lim; ++k) {
 108                 unsigned long upper, lower;
 109 
 110                 /*
 111                  * If shift is not word aligned, take lower rem bits of
 112                  * word above and make them the top rem bits of result.
 113                  */
 114                 if (!rem || off + k + 1 >= lim)
 115                         upper = 0;
 116                 else {
 117                         upper = src[off + k + 1];
 118                         if (off + k + 1 == lim - 1)
 119                                 upper &= mask;
 120                         upper <<= (BITS_PER_LONG - rem);
 121                 }
 122                 lower = src[off + k];
 123                 if (off + k == lim - 1)
 124                         lower &= mask;
 125                 lower >>= rem;
 126                 dst[k] = lower | upper;
 127         }
 128         if (off)
 129                 memset(&dst[lim - off], 0, off*sizeof(unsigned long));
 130 }
 131 EXPORT_SYMBOL(__bitmap_shift_right);
 132 
 133 
 134 /**
 135  * __bitmap_shift_left - logical left shift of the bits in a bitmap
 136  *   @dst : destination bitmap
 137  *   @src : source bitmap
 138  *   @shift : shift by this many bits
 139  *   @nbits : bitmap size, in bits
 140  *
 141  * Shifting left (multiplying) means moving bits in the LS -> MS
 142  * direction.  Zeros are fed into the vacated LS bit positions
 143  * and those MS bits shifted off the top are lost.
 144  */
 145 
 146 void __bitmap_shift_left(unsigned long *dst, const unsigned long *src,
 147                         unsigned int shift, unsigned int nbits)
 148 {
 149         int k;
 150         unsigned int lim = BITS_TO_LONGS(nbits);
 151         unsigned int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;
 152         for (k = lim - off - 1; k >= 0; --k) {
 153                 unsigned long upper, lower;
 154 
 155                 /*
 156                  * If shift is not word aligned, take upper rem bits of
 157                  * word below and make them the bottom rem bits of result.
 158                  */
 159                 if (rem && k > 0)
 160                         lower = src[k - 1] >> (BITS_PER_LONG - rem);
 161                 else
 162                         lower = 0;
 163                 upper = src[k] << rem;
 164                 dst[k + off] = lower | upper;
 165         }
 166         if (off)
 167                 memset(dst, 0, off*sizeof(unsigned long));
 168 }
 169 EXPORT_SYMBOL(__bitmap_shift_left);
 170 
 171 int __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
 172                                 const unsigned long *bitmap2, unsigned int bits)
 173 {
 174         unsigned int k;
 175         unsigned int lim = bits/BITS_PER_LONG;
 176         unsigned long result = 0;
 177 
 178         for (k = 0; k < lim; k++)
 179                 result |= (dst[k] = bitmap1[k] & bitmap2[k]);
 180         if (bits % BITS_PER_LONG)
 181                 result |= (dst[k] = bitmap1[k] & bitmap2[k] &
 182                            BITMAP_LAST_WORD_MASK(bits));
 183         return result != 0;
 184 }
 185 EXPORT_SYMBOL(__bitmap_and);
 186 
 187 void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
 188                                 const unsigned long *bitmap2, unsigned int bits)
 189 {
 190         unsigned int k;
 191         unsigned int nr = BITS_TO_LONGS(bits);
 192 
 193         for (k = 0; k < nr; k++)
 194                 dst[k] = bitmap1[k] | bitmap2[k];
 195 }
 196 EXPORT_SYMBOL(__bitmap_or);
 197 
 198 void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
 199                                 const unsigned long *bitmap2, unsigned int bits)
 200 {
 201         unsigned int k;
 202         unsigned int nr = BITS_TO_LONGS(bits);
 203 
 204         for (k = 0; k < nr; k++)
 205                 dst[k] = bitmap1[k] ^ bitmap2[k];
 206 }
 207 EXPORT_SYMBOL(__bitmap_xor);
 208 
 209 int __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
 210                                 const unsigned long *bitmap2, unsigned int bits)
 211 {
 212         unsigned int k;
 213         unsigned int lim = bits/BITS_PER_LONG;
 214         unsigned long result = 0;
 215 
 216         for (k = 0; k < lim; k++)
 217                 result |= (dst[k] = bitmap1[k] & ~bitmap2[k]);
 218         if (bits % BITS_PER_LONG)
 219                 result |= (dst[k] = bitmap1[k] & ~bitmap2[k] &
 220                            BITMAP_LAST_WORD_MASK(bits));
 221         return result != 0;
 222 }
 223 EXPORT_SYMBOL(__bitmap_andnot);
 224 
 225 int __bitmap_intersects(const unsigned long *bitmap1,
 226                         const unsigned long *bitmap2, unsigned int bits)
 227 {
 228         unsigned int k, lim = bits/BITS_PER_LONG;
 229         for (k = 0; k < lim; ++k)
 230                 if (bitmap1[k] & bitmap2[k])
 231                         return 1;
 232 
 233         if (bits % BITS_PER_LONG)
 234                 if ((bitmap1[k] & bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))
 235                         return 1;
 236         return 0;
 237 }
 238 EXPORT_SYMBOL(__bitmap_intersects);
 239 
 240 int __bitmap_subset(const unsigned long *bitmap1,
 241                     const unsigned long *bitmap2, unsigned int bits)
 242 {
 243         unsigned int k, lim = bits/BITS_PER_LONG;
 244         for (k = 0; k < lim; ++k)
 245                 if (bitmap1[k] & ~bitmap2[k])
 246                         return 0;
 247 
 248         if (bits % BITS_PER_LONG)
 249                 if ((bitmap1[k] & ~bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))
 250                         return 0;
 251         return 1;
 252 }
 253 EXPORT_SYMBOL(__bitmap_subset);
 254 
 255 int __bitmap_weight(const unsigned long *bitmap, unsigned int bits)
 256 {
 257         unsigned int k, lim = bits/BITS_PER_LONG;
 258         int w = 0;
 259 
 260         for (k = 0; k < lim; k++)
 261                 w += hweight_long(bitmap[k]);
 262 
 263         if (bits % BITS_PER_LONG)
 264                 w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits));
 265 
 266         return w;
 267 }
 268 EXPORT_SYMBOL(__bitmap_weight);
 269 
 270 void __bitmap_set(unsigned long *map, unsigned int start, int len)
 271 {
 272         unsigned long *p = map + BIT_WORD(start);
 273         const unsigned int size = start + len;
 274         int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
 275         unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);
 276 
 277         while (len - bits_to_set >= 0) {
 278                 *p |= mask_to_set;
 279                 len -= bits_to_set;
 280                 bits_to_set = BITS_PER_LONG;
 281                 mask_to_set = ~0UL;
 282                 p++;
 283         }
 284         if (len) {
 285                 mask_to_set &= BITMAP_LAST_WORD_MASK(size);
 286                 *p |= mask_to_set;
 287         }
 288 }
 289 EXPORT_SYMBOL(__bitmap_set);
 290 
 291 void __bitmap_clear(unsigned long *map, unsigned int start, int len)
 292 {
 293         unsigned long *p = map + BIT_WORD(start);
 294         const unsigned int size = start + len;
 295         int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
 296         unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);
 297 
 298         while (len - bits_to_clear >= 0) {
 299                 *p &= ~mask_to_clear;
 300                 len -= bits_to_clear;
 301                 bits_to_clear = BITS_PER_LONG;
 302                 mask_to_clear = ~0UL;
 303                 p++;
 304         }
 305         if (len) {
 306                 mask_to_clear &= BITMAP_LAST_WORD_MASK(size);
 307                 *p &= ~mask_to_clear;
 308         }
 309 }
 310 EXPORT_SYMBOL(__bitmap_clear);
 311 
 312 /**
 313  * bitmap_find_next_zero_area_off - find a contiguous aligned zero area
 314  * @map: The address to base the search on
 315  * @size: The bitmap size in bits
 316  * @start: The bitnumber to start searching at
 317  * @nr: The number of zeroed bits we're looking for
 318  * @align_mask: Alignment mask for zero area
 319  * @align_offset: Alignment offset for zero area.
 320  *
 321  * The @align_mask should be one less than a power of 2; the effect is that
 322  * the bit offset of all zero areas this function finds plus @align_offset
 323  * is multiple of that power of 2.
 324  */
 325 unsigned long bitmap_find_next_zero_area_off(unsigned long *map,
 326                                              unsigned long size,
 327                                              unsigned long start,
 328                                              unsigned int nr,
 329                                              unsigned long align_mask,
 330                                              unsigned long align_offset)
 331 {
 332         unsigned long index, end, i;
 333 again:
 334         index = find_next_zero_bit(map, size, start);
 335 
 336         /* Align allocation */
 337         index = __ALIGN_MASK(index + align_offset, align_mask) - align_offset;
 338 
 339         end = index + nr;
 340         if (end > size)
 341                 return end;
 342         i = find_next_bit(map, end, index);
 343         if (i < end) {
 344                 start = i + 1;
 345                 goto again;
 346         }
 347         return index;
 348 }
 349 EXPORT_SYMBOL(bitmap_find_next_zero_area_off);
 350 
 351 /*
 352  * Bitmap printing & parsing functions: first version by Nadia Yvette Chambers,
 353  * second version by Paul Jackson, third by Joe Korty.
 354  */
 355 
 356 #define CHUNKSZ                         32
 357 #define nbits_to_hold_value(val)        fls(val)
 358 #define BASEDEC 10              /* fancier cpuset lists input in decimal */
 359 
 360 /**
 361  * __bitmap_parse - convert an ASCII hex string into a bitmap.
 362  * @buf: pointer to buffer containing string.
 363  * @buflen: buffer size in bytes.  If string is smaller than this
 364  *    then it must be terminated with a \0.
 365  * @is_user: location of buffer, 0 indicates kernel space
 366  * @maskp: pointer to bitmap array that will contain result.
 367  * @nmaskbits: size of bitmap, in bits.
 368  *
 369  * Commas group hex digits into chunks.  Each chunk defines exactly 32
 370  * bits of the resultant bitmask.  No chunk may specify a value larger
 371  * than 32 bits (%-EOVERFLOW), and if a chunk specifies a smaller value
 372  * then leading 0-bits are prepended.  %-EINVAL is returned for illegal
 373  * characters and for grouping errors such as "1,,5", ",44", "," and "".
 374  * Leading and trailing whitespace accepted, but not embedded whitespace.
 375  */
 376 int __bitmap_parse(const char *buf, unsigned int buflen,
 377                 int is_user, unsigned long *maskp,
 378                 int nmaskbits)
 379 {
 380         int c, old_c, totaldigits, ndigits, nchunks, nbits;
 381         u32 chunk;
 382         const char __user __force *ubuf = (const char __user __force *)buf;
 383 
 384         bitmap_zero(maskp, nmaskbits);
 385 
 386         nchunks = nbits = totaldigits = c = 0;
 387         do {
 388                 chunk = 0;
 389                 ndigits = totaldigits;
 390 
 391                 /* Get the next chunk of the bitmap */
 392                 while (buflen) {
 393                         old_c = c;
 394                         if (is_user) {
 395                                 if (__get_user(c, ubuf++))
 396                                         return -EFAULT;
 397                         }
 398                         else
 399                                 c = *buf++;
 400                         buflen--;
 401                         if (isspace(c))
 402                                 continue;
 403 
 404                         /*
 405                          * If the last character was a space and the current
 406                          * character isn't '\0', we've got embedded whitespace.
 407                          * This is a no-no, so throw an error.
 408                          */
 409                         if (totaldigits && c && isspace(old_c))
 410                                 return -EINVAL;
 411 
 412                         /* A '\0' or a ',' signal the end of the chunk */
 413                         if (c == '\0' || c == ',')
 414                                 break;
 415 
 416                         if (!isxdigit(c))
 417                                 return -EINVAL;
 418 
 419                         /*
 420                          * Make sure there are at least 4 free bits in 'chunk'.
 421                          * If not, this hexdigit will overflow 'chunk', so
 422                          * throw an error.
 423                          */
 424                         if (chunk & ~((1UL << (CHUNKSZ - 4)) - 1))
 425                                 return -EOVERFLOW;
 426 
 427                         chunk = (chunk << 4) | hex_to_bin(c);
 428                         totaldigits++;
 429                 }
 430                 if (ndigits == totaldigits)
 431                         return -EINVAL;
 432                 if (nchunks == 0 && chunk == 0)
 433                         continue;
 434 
 435                 __bitmap_shift_left(maskp, maskp, CHUNKSZ, nmaskbits);
 436                 *maskp |= chunk;
 437                 nchunks++;
 438                 nbits += (nchunks == 1) ? nbits_to_hold_value(chunk) : CHUNKSZ;
 439                 if (nbits > nmaskbits)
 440                         return -EOVERFLOW;
 441         } while (buflen && c == ',');
 442 
 443         return 0;
 444 }
 445 EXPORT_SYMBOL(__bitmap_parse);
 446 
 447 /**
 448  * bitmap_parse_user - convert an ASCII hex string in a user buffer into a bitmap
 449  *
 450  * @ubuf: pointer to user buffer containing string.
 451  * @ulen: buffer size in bytes.  If string is smaller than this
 452  *    then it must be terminated with a \0.
 453  * @maskp: pointer to bitmap array that will contain result.
 454  * @nmaskbits: size of bitmap, in bits.
 455  *
 456  * Wrapper for __bitmap_parse(), providing it with user buffer.
 457  *
 458  * We cannot have this as an inline function in bitmap.h because it needs
 459  * linux/uaccess.h to get the access_ok() declaration and this causes
 460  * cyclic dependencies.
 461  */
 462 int bitmap_parse_user(const char __user *ubuf,
 463                         unsigned int ulen, unsigned long *maskp,
 464                         int nmaskbits)
 465 {
 466         if (!access_ok(ubuf, ulen))
 467                 return -EFAULT;
 468         return __bitmap_parse((const char __force *)ubuf,
 469                                 ulen, 1, maskp, nmaskbits);
 470 
 471 }
 472 EXPORT_SYMBOL(bitmap_parse_user);
 473 
 474 /**
 475  * bitmap_print_to_pagebuf - convert bitmap to list or hex format ASCII string
 476  * @list: indicates whether the bitmap must be list
 477  * @buf: page aligned buffer into which string is placed
 478  * @maskp: pointer to bitmap to convert
 479  * @nmaskbits: size of bitmap, in bits
 480  *
 481  * Output format is a comma-separated list of decimal numbers and
 482  * ranges if list is specified or hex digits grouped into comma-separated
 483  * sets of 8 digits/set. Returns the number of characters written to buf.
 484  *
 485  * It is assumed that @buf is a pointer into a PAGE_SIZE, page-aligned
 486  * area and that sufficient storage remains at @buf to accommodate the
 487  * bitmap_print_to_pagebuf() output. Returns the number of characters
 488  * actually printed to @buf, excluding terminating '\0'.
 489  */
 490 int bitmap_print_to_pagebuf(bool list, char *buf, const unsigned long *maskp,
 491                             int nmaskbits)
 492 {
 493         ptrdiff_t len = PAGE_SIZE - offset_in_page(buf);
 494 
 495         return list ? scnprintf(buf, len, "%*pbl\n", nmaskbits, maskp) :
 496                       scnprintf(buf, len, "%*pb\n", nmaskbits, maskp);
 497 }
 498 EXPORT_SYMBOL(bitmap_print_to_pagebuf);
 499 
 500 /*
 501  * Region 9-38:4/10 describes the following bitmap structure:
 502  * 0       9  12    18                  38
 503  * .........****......****......****......
 504  *          ^  ^     ^                   ^
 505  *      start  off   group_len         end
 506  */
 507 struct region {
 508         unsigned int start;
 509         unsigned int off;
 510         unsigned int group_len;
 511         unsigned int end;
 512 };
 513 
 514 static int bitmap_set_region(const struct region *r,
 515                                 unsigned long *bitmap, int nbits)
 516 {
 517         unsigned int start;
 518 
 519         if (r->end >= nbits)
 520                 return -ERANGE;
 521 
 522         for (start = r->start; start <= r->end; start += r->group_len)
 523                 bitmap_set(bitmap, start, min(r->end - start + 1, r->off));
 524 
 525         return 0;
 526 }
 527 
 528 static int bitmap_check_region(const struct region *r)
 529 {
 530         if (r->start > r->end || r->group_len == 0 || r->off > r->group_len)
 531                 return -EINVAL;
 532 
 533         return 0;
 534 }
 535 
 536 static const char *bitmap_getnum(const char *str, unsigned int *num)
 537 {
 538         unsigned long long n;
 539         unsigned int len;
 540 
 541         len = _parse_integer(str, 10, &n);
 542         if (!len)
 543                 return ERR_PTR(-EINVAL);
 544         if (len & KSTRTOX_OVERFLOW || n != (unsigned int)n)
 545                 return ERR_PTR(-EOVERFLOW);
 546 
 547         *num = n;
 548         return str + len;
 549 }
 550 
 551 static inline bool end_of_str(char c)
 552 {
 553         return c == '\0' || c == '\n';
 554 }
 555 
 556 static inline bool __end_of_region(char c)
 557 {
 558         return isspace(c) || c == ',';
 559 }
 560 
 561 static inline bool end_of_region(char c)
 562 {
 563         return __end_of_region(c) || end_of_str(c);
 564 }
 565 
 566 /*
 567  * The format allows commas and whitespases at the beginning
 568  * of the region.
 569  */
 570 static const char *bitmap_find_region(const char *str)
 571 {
 572         while (__end_of_region(*str))
 573                 str++;
 574 
 575         return end_of_str(*str) ? NULL : str;
 576 }
 577 
 578 static const char *bitmap_parse_region(const char *str, struct region *r)
 579 {
 580         str = bitmap_getnum(str, &r->start);
 581         if (IS_ERR(str))
 582                 return str;
 583 
 584         if (end_of_region(*str))
 585                 goto no_end;
 586 
 587         if (*str != '-')
 588                 return ERR_PTR(-EINVAL);
 589 
 590         str = bitmap_getnum(str + 1, &r->end);
 591         if (IS_ERR(str))
 592                 return str;
 593 
 594         if (end_of_region(*str))
 595                 goto no_pattern;
 596 
 597         if (*str != ':')
 598                 return ERR_PTR(-EINVAL);
 599 
 600         str = bitmap_getnum(str + 1, &r->off);
 601         if (IS_ERR(str))
 602                 return str;
 603 
 604         if (*str != '/')
 605                 return ERR_PTR(-EINVAL);
 606 
 607         return bitmap_getnum(str + 1, &r->group_len);
 608 
 609 no_end:
 610         r->end = r->start;
 611 no_pattern:
 612         r->off = r->end + 1;
 613         r->group_len = r->end + 1;
 614 
 615         return end_of_str(*str) ? NULL : str;
 616 }
 617 
 618 /**
 619  * bitmap_parselist - convert list format ASCII string to bitmap
 620  * @buf: read user string from this buffer; must be terminated
 621  *    with a \0 or \n.
 622  * @maskp: write resulting mask here
 623  * @nmaskbits: number of bits in mask to be written
 624  *
 625  * Input format is a comma-separated list of decimal numbers and
 626  * ranges.  Consecutively set bits are shown as two hyphen-separated
 627  * decimal numbers, the smallest and largest bit numbers set in
 628  * the range.
 629  * Optionally each range can be postfixed to denote that only parts of it
 630  * should be set. The range will divided to groups of specific size.
 631  * From each group will be used only defined amount of bits.
 632  * Syntax: range:used_size/group_size
 633  * Example: 0-1023:2/256 ==> 0,1,256,257,512,513,768,769
 634  *
 635  * Returns: 0 on success, -errno on invalid input strings. Error values:
 636  *
 637  *   - ``-EINVAL``: wrong region format
 638  *   - ``-EINVAL``: invalid character in string
 639  *   - ``-ERANGE``: bit number specified too large for mask
 640  *   - ``-EOVERFLOW``: integer overflow in the input parameters
 641  */
 642 int bitmap_parselist(const char *buf, unsigned long *maskp, int nmaskbits)
 643 {
 644         struct region r;
 645         long ret;
 646 
 647         bitmap_zero(maskp, nmaskbits);
 648 
 649         while (buf) {
 650                 buf = bitmap_find_region(buf);
 651                 if (buf == NULL)
 652                         return 0;
 653 
 654                 buf = bitmap_parse_region(buf, &r);
 655                 if (IS_ERR(buf))
 656                         return PTR_ERR(buf);
 657 
 658                 ret = bitmap_check_region(&r);
 659                 if (ret)
 660                         return ret;
 661 
 662                 ret = bitmap_set_region(&r, maskp, nmaskbits);
 663                 if (ret)
 664                         return ret;
 665         }
 666 
 667         return 0;
 668 }
 669 EXPORT_SYMBOL(bitmap_parselist);
 670 
 671 
 672 /**
 673  * bitmap_parselist_user()
 674  *
 675  * @ubuf: pointer to user buffer containing string.
 676  * @ulen: buffer size in bytes.  If string is smaller than this
 677  *    then it must be terminated with a \0.
 678  * @maskp: pointer to bitmap array that will contain result.
 679  * @nmaskbits: size of bitmap, in bits.
 680  *
 681  * Wrapper for bitmap_parselist(), providing it with user buffer.
 682  */
 683 int bitmap_parselist_user(const char __user *ubuf,
 684                         unsigned int ulen, unsigned long *maskp,
 685                         int nmaskbits)
 686 {
 687         char *buf;
 688         int ret;
 689 
 690         buf = memdup_user_nul(ubuf, ulen);
 691         if (IS_ERR(buf))
 692                 return PTR_ERR(buf);
 693 
 694         ret = bitmap_parselist(buf, maskp, nmaskbits);
 695 
 696         kfree(buf);
 697         return ret;
 698 }
 699 EXPORT_SYMBOL(bitmap_parselist_user);
 700 
 701 
 702 #ifdef CONFIG_NUMA
 703 /**
 704  * bitmap_pos_to_ord - find ordinal of set bit at given position in bitmap
 705  *      @buf: pointer to a bitmap
 706  *      @pos: a bit position in @buf (0 <= @pos < @nbits)
 707  *      @nbits: number of valid bit positions in @buf
 708  *
 709  * Map the bit at position @pos in @buf (of length @nbits) to the
 710  * ordinal of which set bit it is.  If it is not set or if @pos
 711  * is not a valid bit position, map to -1.
 712  *
 713  * If for example, just bits 4 through 7 are set in @buf, then @pos
 714  * values 4 through 7 will get mapped to 0 through 3, respectively,
 715  * and other @pos values will get mapped to -1.  When @pos value 7
 716  * gets mapped to (returns) @ord value 3 in this example, that means
 717  * that bit 7 is the 3rd (starting with 0th) set bit in @buf.
 718  *
 719  * The bit positions 0 through @bits are valid positions in @buf.
 720  */
 721 static int bitmap_pos_to_ord(const unsigned long *buf, unsigned int pos, unsigned int nbits)
 722 {
 723         if (pos >= nbits || !test_bit(pos, buf))
 724                 return -1;
 725 
 726         return __bitmap_weight(buf, pos);
 727 }
 728 
 729 /**
 730  * bitmap_ord_to_pos - find position of n-th set bit in bitmap
 731  *      @buf: pointer to bitmap
 732  *      @ord: ordinal bit position (n-th set bit, n >= 0)
 733  *      @nbits: number of valid bit positions in @buf
 734  *
 735  * Map the ordinal offset of bit @ord in @buf to its position in @buf.
 736  * Value of @ord should be in range 0 <= @ord < weight(buf). If @ord
 737  * >= weight(buf), returns @nbits.
 738  *
 739  * If for example, just bits 4 through 7 are set in @buf, then @ord
 740  * values 0 through 3 will get mapped to 4 through 7, respectively,
 741  * and all other @ord values returns @nbits.  When @ord value 3
 742  * gets mapped to (returns) @pos value 7 in this example, that means
 743  * that the 3rd set bit (starting with 0th) is at position 7 in @buf.
 744  *
 745  * The bit positions 0 through @nbits-1 are valid positions in @buf.
 746  */
 747 unsigned int bitmap_ord_to_pos(const unsigned long *buf, unsigned int ord, unsigned int nbits)
 748 {
 749         unsigned int pos;
 750 
 751         for (pos = find_first_bit(buf, nbits);
 752              pos < nbits && ord;
 753              pos = find_next_bit(buf, nbits, pos + 1))
 754                 ord--;
 755 
 756         return pos;
 757 }
 758 
 759 /**
 760  * bitmap_remap - Apply map defined by a pair of bitmaps to another bitmap
 761  *      @dst: remapped result
 762  *      @src: subset to be remapped
 763  *      @old: defines domain of map
 764  *      @new: defines range of map
 765  *      @nbits: number of bits in each of these bitmaps
 766  *
 767  * Let @old and @new define a mapping of bit positions, such that
 768  * whatever position is held by the n-th set bit in @old is mapped
 769  * to the n-th set bit in @new.  In the more general case, allowing
 770  * for the possibility that the weight 'w' of @new is less than the
 771  * weight of @old, map the position of the n-th set bit in @old to
 772  * the position of the m-th set bit in @new, where m == n % w.
 773  *
 774  * If either of the @old and @new bitmaps are empty, or if @src and
 775  * @dst point to the same location, then this routine copies @src
 776  * to @dst.
 777  *
 778  * The positions of unset bits in @old are mapped to themselves
 779  * (the identify map).
 780  *
 781  * Apply the above specified mapping to @src, placing the result in
 782  * @dst, clearing any bits previously set in @dst.
 783  *
 784  * For example, lets say that @old has bits 4 through 7 set, and
 785  * @new has bits 12 through 15 set.  This defines the mapping of bit
 786  * position 4 to 12, 5 to 13, 6 to 14 and 7 to 15, and of all other
 787  * bit positions unchanged.  So if say @src comes into this routine
 788  * with bits 1, 5 and 7 set, then @dst should leave with bits 1,
 789  * 13 and 15 set.
 790  */
 791 void bitmap_remap(unsigned long *dst, const unsigned long *src,
 792                 const unsigned long *old, const unsigned long *new,
 793                 unsigned int nbits)
 794 {
 795         unsigned int oldbit, w;
 796 
 797         if (dst == src)         /* following doesn't handle inplace remaps */
 798                 return;
 799         bitmap_zero(dst, nbits);
 800 
 801         w = bitmap_weight(new, nbits);
 802         for_each_set_bit(oldbit, src, nbits) {
 803                 int n = bitmap_pos_to_ord(old, oldbit, nbits);
 804 
 805                 if (n < 0 || w == 0)
 806                         set_bit(oldbit, dst);   /* identity map */
 807                 else
 808                         set_bit(bitmap_ord_to_pos(new, n % w, nbits), dst);
 809         }
 810 }
 811 
 812 /**
 813  * bitmap_bitremap - Apply map defined by a pair of bitmaps to a single bit
 814  *      @oldbit: bit position to be mapped
 815  *      @old: defines domain of map
 816  *      @new: defines range of map
 817  *      @bits: number of bits in each of these bitmaps
 818  *
 819  * Let @old and @new define a mapping of bit positions, such that
 820  * whatever position is held by the n-th set bit in @old is mapped
 821  * to the n-th set bit in @new.  In the more general case, allowing
 822  * for the possibility that the weight 'w' of @new is less than the
 823  * weight of @old, map the position of the n-th set bit in @old to
 824  * the position of the m-th set bit in @new, where m == n % w.
 825  *
 826  * The positions of unset bits in @old are mapped to themselves
 827  * (the identify map).
 828  *
 829  * Apply the above specified mapping to bit position @oldbit, returning
 830  * the new bit position.
 831  *
 832  * For example, lets say that @old has bits 4 through 7 set, and
 833  * @new has bits 12 through 15 set.  This defines the mapping of bit
 834  * position 4 to 12, 5 to 13, 6 to 14 and 7 to 15, and of all other
 835  * bit positions unchanged.  So if say @oldbit is 5, then this routine
 836  * returns 13.
 837  */
 838 int bitmap_bitremap(int oldbit, const unsigned long *old,
 839                                 const unsigned long *new, int bits)
 840 {
 841         int w = bitmap_weight(new, bits);
 842         int n = bitmap_pos_to_ord(old, oldbit, bits);
 843         if (n < 0 || w == 0)
 844                 return oldbit;
 845         else
 846                 return bitmap_ord_to_pos(new, n % w, bits);
 847 }
 848 
 849 /**
 850  * bitmap_onto - translate one bitmap relative to another
 851  *      @dst: resulting translated bitmap
 852  *      @orig: original untranslated bitmap
 853  *      @relmap: bitmap relative to which translated
 854  *      @bits: number of bits in each of these bitmaps
 855  *
 856  * Set the n-th bit of @dst iff there exists some m such that the
 857  * n-th bit of @relmap is set, the m-th bit of @orig is set, and
 858  * the n-th bit of @relmap is also the m-th _set_ bit of @relmap.
 859  * (If you understood the previous sentence the first time your
 860  * read it, you're overqualified for your current job.)
 861  *
 862  * In other words, @orig is mapped onto (surjectively) @dst,
 863  * using the map { <n, m> | the n-th bit of @relmap is the
 864  * m-th set bit of @relmap }.
 865  *
 866  * Any set bits in @orig above bit number W, where W is the
 867  * weight of (number of set bits in) @relmap are mapped nowhere.
 868  * In particular, if for all bits m set in @orig, m >= W, then
 869  * @dst will end up empty.  In situations where the possibility
 870  * of such an empty result is not desired, one way to avoid it is
 871  * to use the bitmap_fold() operator, below, to first fold the
 872  * @orig bitmap over itself so that all its set bits x are in the
 873  * range 0 <= x < W.  The bitmap_fold() operator does this by
 874  * setting the bit (m % W) in @dst, for each bit (m) set in @orig.
 875  *
 876  * Example [1] for bitmap_onto():
 877  *  Let's say @relmap has bits 30-39 set, and @orig has bits
 878  *  1, 3, 5, 7, 9 and 11 set.  Then on return from this routine,
 879  *  @dst will have bits 31, 33, 35, 37 and 39 set.
 880  *
 881  *  When bit 0 is set in @orig, it means turn on the bit in
 882  *  @dst corresponding to whatever is the first bit (if any)
 883  *  that is turned on in @relmap.  Since bit 0 was off in the
 884  *  above example, we leave off that bit (bit 30) in @dst.
 885  *
 886  *  When bit 1 is set in @orig (as in the above example), it
 887  *  means turn on the bit in @dst corresponding to whatever
 888  *  is the second bit that is turned on in @relmap.  The second
 889  *  bit in @relmap that was turned on in the above example was
 890  *  bit 31, so we turned on bit 31 in @dst.
 891  *
 892  *  Similarly, we turned on bits 33, 35, 37 and 39 in @dst,
 893  *  because they were the 4th, 6th, 8th and 10th set bits
 894  *  set in @relmap, and the 4th, 6th, 8th and 10th bits of
 895  *  @orig (i.e. bits 3, 5, 7 and 9) were also set.
 896  *
 897  *  When bit 11 is set in @orig, it means turn on the bit in
 898  *  @dst corresponding to whatever is the twelfth bit that is
 899  *  turned on in @relmap.  In the above example, there were
 900  *  only ten bits turned on in @relmap (30..39), so that bit
 901  *  11 was set in @orig had no affect on @dst.
 902  *
 903  * Example [2] for bitmap_fold() + bitmap_onto():
 904  *  Let's say @relmap has these ten bits set::
 905  *
 906  *              40 41 42 43 45 48 53 61 74 95
 907  *
 908  *  (for the curious, that's 40 plus the first ten terms of the
 909  *  Fibonacci sequence.)
 910  *
 911  *  Further lets say we use the following code, invoking
 912  *  bitmap_fold() then bitmap_onto, as suggested above to
 913  *  avoid the possibility of an empty @dst result::
 914  *
 915  *      unsigned long *tmp;     // a temporary bitmap's bits
 916  *
 917  *      bitmap_fold(tmp, orig, bitmap_weight(relmap, bits), bits);
 918  *      bitmap_onto(dst, tmp, relmap, bits);
 919  *
 920  *  Then this table shows what various values of @dst would be, for
 921  *  various @orig's.  I list the zero-based positions of each set bit.
 922  *  The tmp column shows the intermediate result, as computed by
 923  *  using bitmap_fold() to fold the @orig bitmap modulo ten
 924  *  (the weight of @relmap):
 925  *
 926  *      =============== ============== =================
 927  *      @orig           tmp            @dst
 928  *      0                0             40
 929  *      1                1             41
 930  *      9                9             95
 931  *      10               0             40 [#f1]_
 932  *      1 3 5 7          1 3 5 7       41 43 48 61
 933  *      0 1 2 3 4        0 1 2 3 4     40 41 42 43 45
 934  *      0 9 18 27        0 9 8 7       40 61 74 95
 935  *      0 10 20 30       0             40
 936  *      0 11 22 33       0 1 2 3       40 41 42 43
 937  *      0 12 24 36       0 2 4 6       40 42 45 53
 938  *      78 102 211       1 2 8         41 42 74 [#f1]_
 939  *      =============== ============== =================
 940  *
 941  * .. [#f1]
 942  *
 943  *     For these marked lines, if we hadn't first done bitmap_fold()
 944  *     into tmp, then the @dst result would have been empty.
 945  *
 946  * If either of @orig or @relmap is empty (no set bits), then @dst
 947  * will be returned empty.
 948  *
 949  * If (as explained above) the only set bits in @orig are in positions
 950  * m where m >= W, (where W is the weight of @relmap) then @dst will
 951  * once again be returned empty.
 952  *
 953  * All bits in @dst not set by the above rule are cleared.
 954  */
 955 void bitmap_onto(unsigned long *dst, const unsigned long *orig,
 956                         const unsigned long *relmap, unsigned int bits)
 957 {
 958         unsigned int n, m;      /* same meaning as in above comment */
 959 
 960         if (dst == orig)        /* following doesn't handle inplace mappings */
 961                 return;
 962         bitmap_zero(dst, bits);
 963 
 964         /*
 965          * The following code is a more efficient, but less
 966          * obvious, equivalent to the loop:
 967          *      for (m = 0; m < bitmap_weight(relmap, bits); m++) {
 968          *              n = bitmap_ord_to_pos(orig, m, bits);
 969          *              if (test_bit(m, orig))
 970          *                      set_bit(n, dst);
 971          *      }
 972          */
 973 
 974         m = 0;
 975         for_each_set_bit(n, relmap, bits) {
 976                 /* m == bitmap_pos_to_ord(relmap, n, bits) */
 977                 if (test_bit(m, orig))
 978                         set_bit(n, dst);
 979                 m++;
 980         }
 981 }
 982 
 983 /**
 984  * bitmap_fold - fold larger bitmap into smaller, modulo specified size
 985  *      @dst: resulting smaller bitmap
 986  *      @orig: original larger bitmap
 987  *      @sz: specified size
 988  *      @nbits: number of bits in each of these bitmaps
 989  *
 990  * For each bit oldbit in @orig, set bit oldbit mod @sz in @dst.
 991  * Clear all other bits in @dst.  See further the comment and
 992  * Example [2] for bitmap_onto() for why and how to use this.
 993  */
 994 void bitmap_fold(unsigned long *dst, const unsigned long *orig,
 995                         unsigned int sz, unsigned int nbits)
 996 {
 997         unsigned int oldbit;
 998 
 999         if (dst == orig)        /* following doesn't handle inplace mappings */
1000                 return;
1001         bitmap_zero(dst, nbits);
1002 
1003         for_each_set_bit(oldbit, orig, nbits)
1004                 set_bit(oldbit % sz, dst);
1005 }
1006 #endif /* CONFIG_NUMA */
1007 
1008 /*
1009  * Common code for bitmap_*_region() routines.
1010  *      bitmap: array of unsigned longs corresponding to the bitmap
1011  *      pos: the beginning of the region
1012  *      order: region size (log base 2 of number of bits)
1013  *      reg_op: operation(s) to perform on that region of bitmap
1014  *
1015  * Can set, verify and/or release a region of bits in a bitmap,
1016  * depending on which combination of REG_OP_* flag bits is set.
1017  *
1018  * A region of a bitmap is a sequence of bits in the bitmap, of
1019  * some size '1 << order' (a power of two), aligned to that same
1020  * '1 << order' power of two.
1021  *
1022  * Returns 1 if REG_OP_ISFREE succeeds (region is all zero bits).
1023  * Returns 0 in all other cases and reg_ops.
1024  */
1025 
1026 enum {
1027         REG_OP_ISFREE,          /* true if region is all zero bits */
1028         REG_OP_ALLOC,           /* set all bits in region */
1029         REG_OP_RELEASE,         /* clear all bits in region */
1030 };
1031 
1032 static int __reg_op(unsigned long *bitmap, unsigned int pos, int order, int reg_op)
1033 {
1034         int nbits_reg;          /* number of bits in region */
1035         int index;              /* index first long of region in bitmap */
1036         int offset;             /* bit offset region in bitmap[index] */
1037         int nlongs_reg;         /* num longs spanned by region in bitmap */
1038         int nbitsinlong;        /* num bits of region in each spanned long */
1039         unsigned long mask;     /* bitmask for one long of region */
1040         int i;                  /* scans bitmap by longs */
1041         int ret = 0;            /* return value */
1042 
1043         /*
1044          * Either nlongs_reg == 1 (for small orders that fit in one long)
1045          * or (offset == 0 && mask == ~0UL) (for larger multiword orders.)
1046          */
1047         nbits_reg = 1 << order;
1048         index = pos / BITS_PER_LONG;
1049         offset = pos - (index * BITS_PER_LONG);
1050         nlongs_reg = BITS_TO_LONGS(nbits_reg);
1051         nbitsinlong = min(nbits_reg,  BITS_PER_LONG);
1052 
1053         /*
1054          * Can't do "mask = (1UL << nbitsinlong) - 1", as that
1055          * overflows if nbitsinlong == BITS_PER_LONG.
1056          */
1057         mask = (1UL << (nbitsinlong - 1));
1058         mask += mask - 1;
1059         mask <<= offset;
1060 
1061         switch (reg_op) {
1062         case REG_OP_ISFREE:
1063                 for (i = 0; i < nlongs_reg; i++) {
1064                         if (bitmap[index + i] & mask)
1065                                 goto done;
1066                 }
1067                 ret = 1;        /* all bits in region free (zero) */
1068                 break;
1069 
1070         case REG_OP_ALLOC:
1071                 for (i = 0; i < nlongs_reg; i++)
1072                         bitmap[index + i] |= mask;
1073                 break;
1074 
1075         case REG_OP_RELEASE:
1076                 for (i = 0; i < nlongs_reg; i++)
1077                         bitmap[index + i] &= ~mask;
1078                 break;
1079         }
1080 done:
1081         return ret;
1082 }
1083 
1084 /**
1085  * bitmap_find_free_region - find a contiguous aligned mem region
1086  *      @bitmap: array of unsigned longs corresponding to the bitmap
1087  *      @bits: number of bits in the bitmap
1088  *      @order: region size (log base 2 of number of bits) to find
1089  *
1090  * Find a region of free (zero) bits in a @bitmap of @bits bits and
1091  * allocate them (set them to one).  Only consider regions of length
1092  * a power (@order) of two, aligned to that power of two, which
1093  * makes the search algorithm much faster.
1094  *
1095  * Return the bit offset in bitmap of the allocated region,
1096  * or -errno on failure.
1097  */
1098 int bitmap_find_free_region(unsigned long *bitmap, unsigned int bits, int order)
1099 {
1100         unsigned int pos, end;          /* scans bitmap by regions of size order */
1101 
1102         for (pos = 0 ; (end = pos + (1U << order)) <= bits; pos = end) {
1103                 if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE))
1104                         continue;
1105                 __reg_op(bitmap, pos, order, REG_OP_ALLOC);
1106                 return pos;
1107         }
1108         return -ENOMEM;
1109 }
1110 EXPORT_SYMBOL(bitmap_find_free_region);
1111 
1112 /**
1113  * bitmap_release_region - release allocated bitmap region
1114  *      @bitmap: array of unsigned longs corresponding to the bitmap
1115  *      @pos: beginning of bit region to release
1116  *      @order: region size (log base 2 of number of bits) to release
1117  *
1118  * This is the complement to __bitmap_find_free_region() and releases
1119  * the found region (by clearing it in the bitmap).
1120  *
1121  * No return value.
1122  */
1123 void bitmap_release_region(unsigned long *bitmap, unsigned int pos, int order)
1124 {
1125         __reg_op(bitmap, pos, order, REG_OP_RELEASE);
1126 }
1127 EXPORT_SYMBOL(bitmap_release_region);
1128 
1129 /**
1130  * bitmap_allocate_region - allocate bitmap region
1131  *      @bitmap: array of unsigned longs corresponding to the bitmap
1132  *      @pos: beginning of bit region to allocate
1133  *      @order: region size (log base 2 of number of bits) to allocate
1134  *
1135  * Allocate (set bits in) a specified region of a bitmap.
1136  *
1137  * Return 0 on success, or %-EBUSY if specified region wasn't
1138  * free (not all bits were zero).
1139  */
1140 int bitmap_allocate_region(unsigned long *bitmap, unsigned int pos, int order)
1141 {
1142         if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE))
1143                 return -EBUSY;
1144         return __reg_op(bitmap, pos, order, REG_OP_ALLOC);
1145 }
1146 EXPORT_SYMBOL(bitmap_allocate_region);
1147 
1148 /**
1149  * bitmap_copy_le - copy a bitmap, putting the bits into little-endian order.
1150  * @dst:   destination buffer
1151  * @src:   bitmap to copy
1152  * @nbits: number of bits in the bitmap
1153  *
1154  * Require nbits % BITS_PER_LONG == 0.
1155  */
1156 #ifdef __BIG_ENDIAN
1157 void bitmap_copy_le(unsigned long *dst, const unsigned long *src, unsigned int nbits)
1158 {
1159         unsigned int i;
1160 
1161         for (i = 0; i < nbits/BITS_PER_LONG; i++) {
1162                 if (BITS_PER_LONG == 64)
1163                         dst[i] = cpu_to_le64(src[i]);
1164                 else
1165                         dst[i] = cpu_to_le32(src[i]);
1166         }
1167 }
1168 EXPORT_SYMBOL(bitmap_copy_le);
1169 #endif
1170 
1171 unsigned long *bitmap_alloc(unsigned int nbits, gfp_t flags)
1172 {
1173         return kmalloc_array(BITS_TO_LONGS(nbits), sizeof(unsigned long),
1174                              flags);
1175 }
1176 EXPORT_SYMBOL(bitmap_alloc);
1177 
1178 unsigned long *bitmap_zalloc(unsigned int nbits, gfp_t flags)
1179 {
1180         return bitmap_alloc(nbits, flags | __GFP_ZERO);
1181 }
1182 EXPORT_SYMBOL(bitmap_zalloc);
1183 
1184 void bitmap_free(const unsigned long *bitmap)
1185 {
1186         kfree(bitmap);
1187 }
1188 EXPORT_SYMBOL(bitmap_free);
1189 
1190 #if BITS_PER_LONG == 64
1191 /**
1192  * bitmap_from_arr32 - copy the contents of u32 array of bits to bitmap
1193  *      @bitmap: array of unsigned longs, the destination bitmap
1194  *      @buf: array of u32 (in host byte order), the source bitmap
1195  *      @nbits: number of bits in @bitmap
1196  */
1197 void bitmap_from_arr32(unsigned long *bitmap, const u32 *buf, unsigned int nbits)
1198 {
1199         unsigned int i, halfwords;
1200 
1201         halfwords = DIV_ROUND_UP(nbits, 32);
1202         for (i = 0; i < halfwords; i++) {
1203                 bitmap[i/2] = (unsigned long) buf[i];
1204                 if (++i < halfwords)
1205                         bitmap[i/2] |= ((unsigned long) buf[i]) << 32;
1206         }
1207 
1208         /* Clear tail bits in last word beyond nbits. */
1209         if (nbits % BITS_PER_LONG)
1210                 bitmap[(halfwords - 1) / 2] &= BITMAP_LAST_WORD_MASK(nbits);
1211 }
1212 EXPORT_SYMBOL(bitmap_from_arr32);
1213 
1214 /**
1215  * bitmap_to_arr32 - copy the contents of bitmap to a u32 array of bits
1216  *      @buf: array of u32 (in host byte order), the dest bitmap
1217  *      @bitmap: array of unsigned longs, the source bitmap
1218  *      @nbits: number of bits in @bitmap
1219  */
1220 void bitmap_to_arr32(u32 *buf, const unsigned long *bitmap, unsigned int nbits)
1221 {
1222         unsigned int i, halfwords;
1223 
1224         halfwords = DIV_ROUND_UP(nbits, 32);
1225         for (i = 0; i < halfwords; i++) {
1226                 buf[i] = (u32) (bitmap[i/2] & UINT_MAX);
1227                 if (++i < halfwords)
1228                         buf[i] = (u32) (bitmap[i/2] >> 32);
1229         }
1230 
1231         /* Clear tail bits in last element of array beyond nbits. */
1232         if (nbits % BITS_PER_LONG)
1233                 buf[halfwords - 1] &= (u32) (UINT_MAX >> ((-nbits) & 31));
1234 }
1235 EXPORT_SYMBOL(bitmap_to_arr32);
1236 
1237 #endif

/* [<][>][^][v][top][bottom][index][help] */