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