Merge tag 'mtd/for-5.14' of git://git.kernel.org/pub/scm/linux/kernel/git/mtd/linux
[linux-2.6-microblaze.git] / lib / bitmap.c
1 // SPDX-License-Identifier: GPL-2.0-only
2 /*
3  * lib/bitmap.c
4  * Helper functions for bitmap.h.
5  */
6
7 #include <linux/bitmap.h>
8 #include <linux/bitops.h>
9 #include <linux/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
48 int __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 }
62 EXPORT_SYMBOL(__bitmap_equal);
63
64 bool __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
84 void __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 }
90 EXPORT_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  */
103 void __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 }
133 EXPORT_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
148 void __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 }
171 EXPORT_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  */
210 void 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 }
238 EXPORT_SYMBOL(bitmap_cut);
239
240 int __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 }
254 EXPORT_SYMBOL(__bitmap_and);
255
256 void __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 }
265 EXPORT_SYMBOL(__bitmap_or);
266
267 void __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 }
276 EXPORT_SYMBOL(__bitmap_xor);
277
278 int __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 }
292 EXPORT_SYMBOL(__bitmap_andnot);
293
294 void __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 }
304 EXPORT_SYMBOL(__bitmap_replace);
305
306 int __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 }
319 EXPORT_SYMBOL(__bitmap_intersects);
320
321 int __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 }
334 EXPORT_SYMBOL(__bitmap_subset);
335
336 int __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 }
349 EXPORT_SYMBOL(__bitmap_weight);
350
351 void __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 }
370 EXPORT_SYMBOL(__bitmap_set);
371
372 void __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 }
391 EXPORT_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  */
406 unsigned 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;
414 again:
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 }
430 EXPORT_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  */
446 int 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 }
462 EXPORT_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  */
480 int 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 }
488 EXPORT_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  */
497 struct region {
498         unsigned int start;
499         unsigned int off;
500         unsigned int group_len;
501         unsigned int end;
502         unsigned int nbits;
503 };
504
505 static 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
513 static 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
524 static 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
545 static inline bool end_of_str(char c)
546 {
547         return c == '\0' || c == '\n';
548 }
549
550 static inline bool __end_of_region(char c)
551 {
552         return isspace(c) || c == ',';
553 }
554
555 static 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  */
564 static 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
572 static 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
580 static const char *bitmap_parse_region(const char *str, struct region *r)
581 {
582         unsigned int lastbit = r->nbits - 1;
583
584         if (!strncasecmp(str, "all", 3)) {
585                 r->start = 0;
586                 r->end = lastbit;
587                 str += 3;
588
589                 goto check_pattern;
590         }
591
592         str = bitmap_getnum(str, &r->start, lastbit);
593         if (IS_ERR(str))
594                 return str;
595
596         if (end_of_region(*str))
597                 goto no_end;
598
599         if (*str != '-')
600                 return ERR_PTR(-EINVAL);
601
602         str = bitmap_getnum(str + 1, &r->end, lastbit);
603         if (IS_ERR(str))
604                 return str;
605
606 check_pattern:
607         if (end_of_region(*str))
608                 goto no_pattern;
609
610         if (*str != ':')
611                 return ERR_PTR(-EINVAL);
612
613         str = bitmap_getnum(str + 1, &r->off, lastbit);
614         if (IS_ERR(str))
615                 return str;
616
617         if (*str != '/')
618                 return ERR_PTR(-EINVAL);
619
620         return bitmap_getnum(str + 1, &r->group_len, lastbit);
621
622 no_end:
623         r->end = r->start;
624 no_pattern:
625         r->off = r->end + 1;
626         r->group_len = r->end + 1;
627
628         return end_of_str(*str) ? NULL : str;
629 }
630
631 /**
632  * bitmap_parselist - convert list format ASCII string to bitmap
633  * @buf: read user string from this buffer; must be terminated
634  *    with a \0 or \n.
635  * @maskp: write resulting mask here
636  * @nmaskbits: number of bits in mask to be written
637  *
638  * Input format is a comma-separated list of decimal numbers and
639  * ranges.  Consecutively set bits are shown as two hyphen-separated
640  * decimal numbers, the smallest and largest bit numbers set in
641  * the range.
642  * Optionally each range can be postfixed to denote that only parts of it
643  * should be set. The range will divided to groups of specific size.
644  * From each group will be used only defined amount of bits.
645  * Syntax: range:used_size/group_size
646  * Example: 0-1023:2/256 ==> 0,1,256,257,512,513,768,769
647  * The value 'N' can be used as a dynamically substituted token for the
648  * maximum allowed value; i.e (nmaskbits - 1).  Keep in mind that it is
649  * dynamic, so if system changes cause the bitmap width to change, such
650  * as more cores in a CPU list, then any ranges using N will also change.
651  *
652  * Returns: 0 on success, -errno on invalid input strings. Error values:
653  *
654  *   - ``-EINVAL``: wrong region format
655  *   - ``-EINVAL``: invalid character in string
656  *   - ``-ERANGE``: bit number specified too large for mask
657  *   - ``-EOVERFLOW``: integer overflow in the input parameters
658  */
659 int bitmap_parselist(const char *buf, unsigned long *maskp, int nmaskbits)
660 {
661         struct region r;
662         long ret;
663
664         r.nbits = nmaskbits;
665         bitmap_zero(maskp, r.nbits);
666
667         while (buf) {
668                 buf = bitmap_find_region(buf);
669                 if (buf == NULL)
670                         return 0;
671
672                 buf = bitmap_parse_region(buf, &r);
673                 if (IS_ERR(buf))
674                         return PTR_ERR(buf);
675
676                 ret = bitmap_check_region(&r);
677                 if (ret)
678                         return ret;
679
680                 bitmap_set_region(&r, maskp);
681         }
682
683         return 0;
684 }
685 EXPORT_SYMBOL(bitmap_parselist);
686
687
688 /**
689  * bitmap_parselist_user()
690  *
691  * @ubuf: pointer to user buffer containing string.
692  * @ulen: buffer size in bytes.  If string is smaller than this
693  *    then it must be terminated with a \0.
694  * @maskp: pointer to bitmap array that will contain result.
695  * @nmaskbits: size of bitmap, in bits.
696  *
697  * Wrapper for bitmap_parselist(), providing it with user buffer.
698  */
699 int bitmap_parselist_user(const char __user *ubuf,
700                         unsigned int ulen, unsigned long *maskp,
701                         int nmaskbits)
702 {
703         char *buf;
704         int ret;
705
706         buf = memdup_user_nul(ubuf, ulen);
707         if (IS_ERR(buf))
708                 return PTR_ERR(buf);
709
710         ret = bitmap_parselist(buf, maskp, nmaskbits);
711
712         kfree(buf);
713         return ret;
714 }
715 EXPORT_SYMBOL(bitmap_parselist_user);
716
717 static const char *bitmap_get_x32_reverse(const char *start,
718                                         const char *end, u32 *num)
719 {
720         u32 ret = 0;
721         int c, i;
722
723         for (i = 0; i < 32; i += 4) {
724                 c = hex_to_bin(*end--);
725                 if (c < 0)
726                         return ERR_PTR(-EINVAL);
727
728                 ret |= c << i;
729
730                 if (start > end || __end_of_region(*end))
731                         goto out;
732         }
733
734         if (hex_to_bin(*end--) >= 0)
735                 return ERR_PTR(-EOVERFLOW);
736 out:
737         *num = ret;
738         return end;
739 }
740
741 /**
742  * bitmap_parse - convert an ASCII hex string into a bitmap.
743  * @start: pointer to buffer containing string.
744  * @buflen: buffer size in bytes.  If string is smaller than this
745  *    then it must be terminated with a \0 or \n. In that case,
746  *    UINT_MAX may be provided instead of string length.
747  * @maskp: pointer to bitmap array that will contain result.
748  * @nmaskbits: size of bitmap, in bits.
749  *
750  * Commas group hex digits into chunks.  Each chunk defines exactly 32
751  * bits of the resultant bitmask.  No chunk may specify a value larger
752  * than 32 bits (%-EOVERFLOW), and if a chunk specifies a smaller value
753  * then leading 0-bits are prepended.  %-EINVAL is returned for illegal
754  * characters. Grouping such as "1,,5", ",44", "," or "" is allowed.
755  * Leading, embedded and trailing whitespace accepted.
756  */
757 int bitmap_parse(const char *start, unsigned int buflen,
758                 unsigned long *maskp, int nmaskbits)
759 {
760         const char *end = strnchrnul(start, buflen, '\n') - 1;
761         int chunks = BITS_TO_U32(nmaskbits);
762         u32 *bitmap = (u32 *)maskp;
763         int unset_bit;
764         int chunk;
765
766         for (chunk = 0; ; chunk++) {
767                 end = bitmap_find_region_reverse(start, end);
768                 if (start > end)
769                         break;
770
771                 if (!chunks--)
772                         return -EOVERFLOW;
773
774 #if defined(CONFIG_64BIT) && defined(__BIG_ENDIAN)
775                 end = bitmap_get_x32_reverse(start, end, &bitmap[chunk ^ 1]);
776 #else
777                 end = bitmap_get_x32_reverse(start, end, &bitmap[chunk]);
778 #endif
779                 if (IS_ERR(end))
780                         return PTR_ERR(end);
781         }
782
783         unset_bit = (BITS_TO_U32(nmaskbits) - chunks) * 32;
784         if (unset_bit < nmaskbits) {
785                 bitmap_clear(maskp, unset_bit, nmaskbits - unset_bit);
786                 return 0;
787         }
788
789         if (find_next_bit(maskp, unset_bit, nmaskbits) != unset_bit)
790                 return -EOVERFLOW;
791
792         return 0;
793 }
794 EXPORT_SYMBOL(bitmap_parse);
795
796
797 #ifdef CONFIG_NUMA
798 /**
799  * bitmap_pos_to_ord - find ordinal of set bit at given position in bitmap
800  *      @buf: pointer to a bitmap
801  *      @pos: a bit position in @buf (0 <= @pos < @nbits)
802  *      @nbits: number of valid bit positions in @buf
803  *
804  * Map the bit at position @pos in @buf (of length @nbits) to the
805  * ordinal of which set bit it is.  If it is not set or if @pos
806  * is not a valid bit position, map to -1.
807  *
808  * If for example, just bits 4 through 7 are set in @buf, then @pos
809  * values 4 through 7 will get mapped to 0 through 3, respectively,
810  * and other @pos values will get mapped to -1.  When @pos value 7
811  * gets mapped to (returns) @ord value 3 in this example, that means
812  * that bit 7 is the 3rd (starting with 0th) set bit in @buf.
813  *
814  * The bit positions 0 through @bits are valid positions in @buf.
815  */
816 static int bitmap_pos_to_ord(const unsigned long *buf, unsigned int pos, unsigned int nbits)
817 {
818         if (pos >= nbits || !test_bit(pos, buf))
819                 return -1;
820
821         return __bitmap_weight(buf, pos);
822 }
823
824 /**
825  * bitmap_ord_to_pos - find position of n-th set bit in bitmap
826  *      @buf: pointer to bitmap
827  *      @ord: ordinal bit position (n-th set bit, n >= 0)
828  *      @nbits: number of valid bit positions in @buf
829  *
830  * Map the ordinal offset of bit @ord in @buf to its position in @buf.
831  * Value of @ord should be in range 0 <= @ord < weight(buf). If @ord
832  * >= weight(buf), returns @nbits.
833  *
834  * If for example, just bits 4 through 7 are set in @buf, then @ord
835  * values 0 through 3 will get mapped to 4 through 7, respectively,
836  * and all other @ord values returns @nbits.  When @ord value 3
837  * gets mapped to (returns) @pos value 7 in this example, that means
838  * that the 3rd set bit (starting with 0th) is at position 7 in @buf.
839  *
840  * The bit positions 0 through @nbits-1 are valid positions in @buf.
841  */
842 unsigned int bitmap_ord_to_pos(const unsigned long *buf, unsigned int ord, unsigned int nbits)
843 {
844         unsigned int pos;
845
846         for (pos = find_first_bit(buf, nbits);
847              pos < nbits && ord;
848              pos = find_next_bit(buf, nbits, pos + 1))
849                 ord--;
850
851         return pos;
852 }
853
854 /**
855  * bitmap_remap - Apply map defined by a pair of bitmaps to another bitmap
856  *      @dst: remapped result
857  *      @src: subset to be remapped
858  *      @old: defines domain of map
859  *      @new: defines range of map
860  *      @nbits: number of bits in each of these bitmaps
861  *
862  * Let @old and @new define a mapping of bit positions, such that
863  * whatever position is held by the n-th set bit in @old is mapped
864  * to the n-th set bit in @new.  In the more general case, allowing
865  * for the possibility that the weight 'w' of @new is less than the
866  * weight of @old, map the position of the n-th set bit in @old to
867  * the position of the m-th set bit in @new, where m == n % w.
868  *
869  * If either of the @old and @new bitmaps are empty, or if @src and
870  * @dst point to the same location, then this routine copies @src
871  * to @dst.
872  *
873  * The positions of unset bits in @old are mapped to themselves
874  * (the identify map).
875  *
876  * Apply the above specified mapping to @src, placing the result in
877  * @dst, clearing any bits previously set in @dst.
878  *
879  * For example, lets say that @old has bits 4 through 7 set, and
880  * @new has bits 12 through 15 set.  This defines the mapping of bit
881  * position 4 to 12, 5 to 13, 6 to 14 and 7 to 15, and of all other
882  * bit positions unchanged.  So if say @src comes into this routine
883  * with bits 1, 5 and 7 set, then @dst should leave with bits 1,
884  * 13 and 15 set.
885  */
886 void bitmap_remap(unsigned long *dst, const unsigned long *src,
887                 const unsigned long *old, const unsigned long *new,
888                 unsigned int nbits)
889 {
890         unsigned int oldbit, w;
891
892         if (dst == src)         /* following doesn't handle inplace remaps */
893                 return;
894         bitmap_zero(dst, nbits);
895
896         w = bitmap_weight(new, nbits);
897         for_each_set_bit(oldbit, src, nbits) {
898                 int n = bitmap_pos_to_ord(old, oldbit, nbits);
899
900                 if (n < 0 || w == 0)
901                         set_bit(oldbit, dst);   /* identity map */
902                 else
903                         set_bit(bitmap_ord_to_pos(new, n % w, nbits), dst);
904         }
905 }
906
907 /**
908  * bitmap_bitremap - Apply map defined by a pair of bitmaps to a single bit
909  *      @oldbit: bit position to be mapped
910  *      @old: defines domain of map
911  *      @new: defines range of map
912  *      @bits: number of bits in each of these bitmaps
913  *
914  * Let @old and @new define a mapping of bit positions, such that
915  * whatever position is held by the n-th set bit in @old is mapped
916  * to the n-th set bit in @new.  In the more general case, allowing
917  * for the possibility that the weight 'w' of @new is less than the
918  * weight of @old, map the position of the n-th set bit in @old to
919  * the position of the m-th set bit in @new, where m == n % w.
920  *
921  * The positions of unset bits in @old are mapped to themselves
922  * (the identify map).
923  *
924  * Apply the above specified mapping to bit position @oldbit, returning
925  * the new bit position.
926  *
927  * For example, lets say that @old has bits 4 through 7 set, and
928  * @new has bits 12 through 15 set.  This defines the mapping of bit
929  * position 4 to 12, 5 to 13, 6 to 14 and 7 to 15, and of all other
930  * bit positions unchanged.  So if say @oldbit is 5, then this routine
931  * returns 13.
932  */
933 int bitmap_bitremap(int oldbit, const unsigned long *old,
934                                 const unsigned long *new, int bits)
935 {
936         int w = bitmap_weight(new, bits);
937         int n = bitmap_pos_to_ord(old, oldbit, bits);
938         if (n < 0 || w == 0)
939                 return oldbit;
940         else
941                 return bitmap_ord_to_pos(new, n % w, bits);
942 }
943
944 /**
945  * bitmap_onto - translate one bitmap relative to another
946  *      @dst: resulting translated bitmap
947  *      @orig: original untranslated bitmap
948  *      @relmap: bitmap relative to which translated
949  *      @bits: number of bits in each of these bitmaps
950  *
951  * Set the n-th bit of @dst iff there exists some m such that the
952  * n-th bit of @relmap is set, the m-th bit of @orig is set, and
953  * the n-th bit of @relmap is also the m-th _set_ bit of @relmap.
954  * (If you understood the previous sentence the first time your
955  * read it, you're overqualified for your current job.)
956  *
957  * In other words, @orig is mapped onto (surjectively) @dst,
958  * using the map { <n, m> | the n-th bit of @relmap is the
959  * m-th set bit of @relmap }.
960  *
961  * Any set bits in @orig above bit number W, where W is the
962  * weight of (number of set bits in) @relmap are mapped nowhere.
963  * In particular, if for all bits m set in @orig, m >= W, then
964  * @dst will end up empty.  In situations where the possibility
965  * of such an empty result is not desired, one way to avoid it is
966  * to use the bitmap_fold() operator, below, to first fold the
967  * @orig bitmap over itself so that all its set bits x are in the
968  * range 0 <= x < W.  The bitmap_fold() operator does this by
969  * setting the bit (m % W) in @dst, for each bit (m) set in @orig.
970  *
971  * Example [1] for bitmap_onto():
972  *  Let's say @relmap has bits 30-39 set, and @orig has bits
973  *  1, 3, 5, 7, 9 and 11 set.  Then on return from this routine,
974  *  @dst will have bits 31, 33, 35, 37 and 39 set.
975  *
976  *  When bit 0 is set in @orig, it means turn on the bit in
977  *  @dst corresponding to whatever is the first bit (if any)
978  *  that is turned on in @relmap.  Since bit 0 was off in the
979  *  above example, we leave off that bit (bit 30) in @dst.
980  *
981  *  When bit 1 is set in @orig (as in the above example), it
982  *  means turn on the bit in @dst corresponding to whatever
983  *  is the second bit that is turned on in @relmap.  The second
984  *  bit in @relmap that was turned on in the above example was
985  *  bit 31, so we turned on bit 31 in @dst.
986  *
987  *  Similarly, we turned on bits 33, 35, 37 and 39 in @dst,
988  *  because they were the 4th, 6th, 8th and 10th set bits
989  *  set in @relmap, and the 4th, 6th, 8th and 10th bits of
990  *  @orig (i.e. bits 3, 5, 7 and 9) were also set.
991  *
992  *  When bit 11 is set in @orig, it means turn on the bit in
993  *  @dst corresponding to whatever is the twelfth bit that is
994  *  turned on in @relmap.  In the above example, there were
995  *  only ten bits turned on in @relmap (30..39), so that bit
996  *  11 was set in @orig had no affect on @dst.
997  *
998  * Example [2] for bitmap_fold() + bitmap_onto():
999  *  Let's say @relmap has these ten bits set::
1000  *
1001  *              40 41 42 43 45 48 53 61 74 95
1002  *
1003  *  (for the curious, that's 40 plus the first ten terms of the
1004  *  Fibonacci sequence.)
1005  *
1006  *  Further lets say we use the following code, invoking
1007  *  bitmap_fold() then bitmap_onto, as suggested above to
1008  *  avoid the possibility of an empty @dst result::
1009  *
1010  *      unsigned long *tmp;     // a temporary bitmap's bits
1011  *
1012  *      bitmap_fold(tmp, orig, bitmap_weight(relmap, bits), bits);
1013  *      bitmap_onto(dst, tmp, relmap, bits);
1014  *
1015  *  Then this table shows what various values of @dst would be, for
1016  *  various @orig's.  I list the zero-based positions of each set bit.
1017  *  The tmp column shows the intermediate result, as computed by
1018  *  using bitmap_fold() to fold the @orig bitmap modulo ten
1019  *  (the weight of @relmap):
1020  *
1021  *      =============== ============== =================
1022  *      @orig           tmp            @dst
1023  *      0                0             40
1024  *      1                1             41
1025  *      9                9             95
1026  *      10               0             40 [#f1]_
1027  *      1 3 5 7          1 3 5 7       41 43 48 61
1028  *      0 1 2 3 4        0 1 2 3 4     40 41 42 43 45
1029  *      0 9 18 27        0 9 8 7       40 61 74 95
1030  *      0 10 20 30       0             40
1031  *      0 11 22 33       0 1 2 3       40 41 42 43
1032  *      0 12 24 36       0 2 4 6       40 42 45 53
1033  *      78 102 211       1 2 8         41 42 74 [#f1]_
1034  *      =============== ============== =================
1035  *
1036  * .. [#f1]
1037  *
1038  *     For these marked lines, if we hadn't first done bitmap_fold()
1039  *     into tmp, then the @dst result would have been empty.
1040  *
1041  * If either of @orig or @relmap is empty (no set bits), then @dst
1042  * will be returned empty.
1043  *
1044  * If (as explained above) the only set bits in @orig are in positions
1045  * m where m >= W, (where W is the weight of @relmap) then @dst will
1046  * once again be returned empty.
1047  *
1048  * All bits in @dst not set by the above rule are cleared.
1049  */
1050 void bitmap_onto(unsigned long *dst, const unsigned long *orig,
1051                         const unsigned long *relmap, unsigned int bits)
1052 {
1053         unsigned int n, m;      /* same meaning as in above comment */
1054
1055         if (dst == orig)        /* following doesn't handle inplace mappings */
1056                 return;
1057         bitmap_zero(dst, bits);
1058
1059         /*
1060          * The following code is a more efficient, but less
1061          * obvious, equivalent to the loop:
1062          *      for (m = 0; m < bitmap_weight(relmap, bits); m++) {
1063          *              n = bitmap_ord_to_pos(orig, m, bits);
1064          *              if (test_bit(m, orig))
1065          *                      set_bit(n, dst);
1066          *      }
1067          */
1068
1069         m = 0;
1070         for_each_set_bit(n, relmap, bits) {
1071                 /* m == bitmap_pos_to_ord(relmap, n, bits) */
1072                 if (test_bit(m, orig))
1073                         set_bit(n, dst);
1074                 m++;
1075         }
1076 }
1077
1078 /**
1079  * bitmap_fold - fold larger bitmap into smaller, modulo specified size
1080  *      @dst: resulting smaller bitmap
1081  *      @orig: original larger bitmap
1082  *      @sz: specified size
1083  *      @nbits: number of bits in each of these bitmaps
1084  *
1085  * For each bit oldbit in @orig, set bit oldbit mod @sz in @dst.
1086  * Clear all other bits in @dst.  See further the comment and
1087  * Example [2] for bitmap_onto() for why and how to use this.
1088  */
1089 void bitmap_fold(unsigned long *dst, const unsigned long *orig,
1090                         unsigned int sz, unsigned int nbits)
1091 {
1092         unsigned int oldbit;
1093
1094         if (dst == orig)        /* following doesn't handle inplace mappings */
1095                 return;
1096         bitmap_zero(dst, nbits);
1097
1098         for_each_set_bit(oldbit, orig, nbits)
1099                 set_bit(oldbit % sz, dst);
1100 }
1101 #endif /* CONFIG_NUMA */
1102
1103 /*
1104  * Common code for bitmap_*_region() routines.
1105  *      bitmap: array of unsigned longs corresponding to the bitmap
1106  *      pos: the beginning of the region
1107  *      order: region size (log base 2 of number of bits)
1108  *      reg_op: operation(s) to perform on that region of bitmap
1109  *
1110  * Can set, verify and/or release a region of bits in a bitmap,
1111  * depending on which combination of REG_OP_* flag bits is set.
1112  *
1113  * A region of a bitmap is a sequence of bits in the bitmap, of
1114  * some size '1 << order' (a power of two), aligned to that same
1115  * '1 << order' power of two.
1116  *
1117  * Returns 1 if REG_OP_ISFREE succeeds (region is all zero bits).
1118  * Returns 0 in all other cases and reg_ops.
1119  */
1120
1121 enum {
1122         REG_OP_ISFREE,          /* true if region is all zero bits */
1123         REG_OP_ALLOC,           /* set all bits in region */
1124         REG_OP_RELEASE,         /* clear all bits in region */
1125 };
1126
1127 static int __reg_op(unsigned long *bitmap, unsigned int pos, int order, int reg_op)
1128 {
1129         int nbits_reg;          /* number of bits in region */
1130         int index;              /* index first long of region in bitmap */
1131         int offset;             /* bit offset region in bitmap[index] */
1132         int nlongs_reg;         /* num longs spanned by region in bitmap */
1133         int nbitsinlong;        /* num bits of region in each spanned long */
1134         unsigned long mask;     /* bitmask for one long of region */
1135         int i;                  /* scans bitmap by longs */
1136         int ret = 0;            /* return value */
1137
1138         /*
1139          * Either nlongs_reg == 1 (for small orders that fit in one long)
1140          * or (offset == 0 && mask == ~0UL) (for larger multiword orders.)
1141          */
1142         nbits_reg = 1 << order;
1143         index = pos / BITS_PER_LONG;
1144         offset = pos - (index * BITS_PER_LONG);
1145         nlongs_reg = BITS_TO_LONGS(nbits_reg);
1146         nbitsinlong = min(nbits_reg,  BITS_PER_LONG);
1147
1148         /*
1149          * Can't do "mask = (1UL << nbitsinlong) - 1", as that
1150          * overflows if nbitsinlong == BITS_PER_LONG.
1151          */
1152         mask = (1UL << (nbitsinlong - 1));
1153         mask += mask - 1;
1154         mask <<= offset;
1155
1156         switch (reg_op) {
1157         case REG_OP_ISFREE:
1158                 for (i = 0; i < nlongs_reg; i++) {
1159                         if (bitmap[index + i] & mask)
1160                                 goto done;
1161                 }
1162                 ret = 1;        /* all bits in region free (zero) */
1163                 break;
1164
1165         case REG_OP_ALLOC:
1166                 for (i = 0; i < nlongs_reg; i++)
1167                         bitmap[index + i] |= mask;
1168                 break;
1169
1170         case REG_OP_RELEASE:
1171                 for (i = 0; i < nlongs_reg; i++)
1172                         bitmap[index + i] &= ~mask;
1173                 break;
1174         }
1175 done:
1176         return ret;
1177 }
1178
1179 /**
1180  * bitmap_find_free_region - find a contiguous aligned mem region
1181  *      @bitmap: array of unsigned longs corresponding to the bitmap
1182  *      @bits: number of bits in the bitmap
1183  *      @order: region size (log base 2 of number of bits) to find
1184  *
1185  * Find a region of free (zero) bits in a @bitmap of @bits bits and
1186  * allocate them (set them to one).  Only consider regions of length
1187  * a power (@order) of two, aligned to that power of two, which
1188  * makes the search algorithm much faster.
1189  *
1190  * Return the bit offset in bitmap of the allocated region,
1191  * or -errno on failure.
1192  */
1193 int bitmap_find_free_region(unsigned long *bitmap, unsigned int bits, int order)
1194 {
1195         unsigned int pos, end;          /* scans bitmap by regions of size order */
1196
1197         for (pos = 0 ; (end = pos + (1U << order)) <= bits; pos = end) {
1198                 if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE))
1199                         continue;
1200                 __reg_op(bitmap, pos, order, REG_OP_ALLOC);
1201                 return pos;
1202         }
1203         return -ENOMEM;
1204 }
1205 EXPORT_SYMBOL(bitmap_find_free_region);
1206
1207 /**
1208  * bitmap_release_region - release allocated bitmap region
1209  *      @bitmap: array of unsigned longs corresponding to the bitmap
1210  *      @pos: beginning of bit region to release
1211  *      @order: region size (log base 2 of number of bits) to release
1212  *
1213  * This is the complement to __bitmap_find_free_region() and releases
1214  * the found region (by clearing it in the bitmap).
1215  *
1216  * No return value.
1217  */
1218 void bitmap_release_region(unsigned long *bitmap, unsigned int pos, int order)
1219 {
1220         __reg_op(bitmap, pos, order, REG_OP_RELEASE);
1221 }
1222 EXPORT_SYMBOL(bitmap_release_region);
1223
1224 /**
1225  * bitmap_allocate_region - allocate bitmap region
1226  *      @bitmap: array of unsigned longs corresponding to the bitmap
1227  *      @pos: beginning of bit region to allocate
1228  *      @order: region size (log base 2 of number of bits) to allocate
1229  *
1230  * Allocate (set bits in) a specified region of a bitmap.
1231  *
1232  * Return 0 on success, or %-EBUSY if specified region wasn't
1233  * free (not all bits were zero).
1234  */
1235 int bitmap_allocate_region(unsigned long *bitmap, unsigned int pos, int order)
1236 {
1237         if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE))
1238                 return -EBUSY;
1239         return __reg_op(bitmap, pos, order, REG_OP_ALLOC);
1240 }
1241 EXPORT_SYMBOL(bitmap_allocate_region);
1242
1243 /**
1244  * bitmap_copy_le - copy a bitmap, putting the bits into little-endian order.
1245  * @dst:   destination buffer
1246  * @src:   bitmap to copy
1247  * @nbits: number of bits in the bitmap
1248  *
1249  * Require nbits % BITS_PER_LONG == 0.
1250  */
1251 #ifdef __BIG_ENDIAN
1252 void bitmap_copy_le(unsigned long *dst, const unsigned long *src, unsigned int nbits)
1253 {
1254         unsigned int i;
1255
1256         for (i = 0; i < nbits/BITS_PER_LONG; i++) {
1257                 if (BITS_PER_LONG == 64)
1258                         dst[i] = cpu_to_le64(src[i]);
1259                 else
1260                         dst[i] = cpu_to_le32(src[i]);
1261         }
1262 }
1263 EXPORT_SYMBOL(bitmap_copy_le);
1264 #endif
1265
1266 unsigned long *bitmap_alloc(unsigned int nbits, gfp_t flags)
1267 {
1268         return kmalloc_array(BITS_TO_LONGS(nbits), sizeof(unsigned long),
1269                              flags);
1270 }
1271 EXPORT_SYMBOL(bitmap_alloc);
1272
1273 unsigned long *bitmap_zalloc(unsigned int nbits, gfp_t flags)
1274 {
1275         return bitmap_alloc(nbits, flags | __GFP_ZERO);
1276 }
1277 EXPORT_SYMBOL(bitmap_zalloc);
1278
1279 void bitmap_free(const unsigned long *bitmap)
1280 {
1281         kfree(bitmap);
1282 }
1283 EXPORT_SYMBOL(bitmap_free);
1284
1285 static void devm_bitmap_free(void *data)
1286 {
1287         unsigned long *bitmap = data;
1288
1289         bitmap_free(bitmap);
1290 }
1291
1292 unsigned long *devm_bitmap_alloc(struct device *dev,
1293                                  unsigned int nbits, gfp_t flags)
1294 {
1295         unsigned long *bitmap;
1296         int ret;
1297
1298         bitmap = bitmap_alloc(nbits, flags);
1299         if (!bitmap)
1300                 return NULL;
1301
1302         ret = devm_add_action_or_reset(dev, devm_bitmap_free, bitmap);
1303         if (ret)
1304                 return NULL;
1305
1306         return bitmap;
1307 }
1308 EXPORT_SYMBOL_GPL(devm_bitmap_alloc);
1309
1310 unsigned long *devm_bitmap_zalloc(struct device *dev,
1311                                   unsigned int nbits, gfp_t flags)
1312 {
1313         return devm_bitmap_alloc(dev, nbits, flags | __GFP_ZERO);
1314 }
1315 EXPORT_SYMBOL_GPL(devm_bitmap_zalloc);
1316
1317 #if BITS_PER_LONG == 64
1318 /**
1319  * bitmap_from_arr32 - copy the contents of u32 array of bits to bitmap
1320  *      @bitmap: array of unsigned longs, the destination bitmap
1321  *      @buf: array of u32 (in host byte order), the source bitmap
1322  *      @nbits: number of bits in @bitmap
1323  */
1324 void bitmap_from_arr32(unsigned long *bitmap, const u32 *buf, unsigned int nbits)
1325 {
1326         unsigned int i, halfwords;
1327
1328         halfwords = DIV_ROUND_UP(nbits, 32);
1329         for (i = 0; i < halfwords; i++) {
1330                 bitmap[i/2] = (unsigned long) buf[i];
1331                 if (++i < halfwords)
1332                         bitmap[i/2] |= ((unsigned long) buf[i]) << 32;
1333         }
1334
1335         /* Clear tail bits in last word beyond nbits. */
1336         if (nbits % BITS_PER_LONG)
1337                 bitmap[(halfwords - 1) / 2] &= BITMAP_LAST_WORD_MASK(nbits);
1338 }
1339 EXPORT_SYMBOL(bitmap_from_arr32);
1340
1341 /**
1342  * bitmap_to_arr32 - copy the contents of bitmap to a u32 array of bits
1343  *      @buf: array of u32 (in host byte order), the dest bitmap
1344  *      @bitmap: array of unsigned longs, the source bitmap
1345  *      @nbits: number of bits in @bitmap
1346  */
1347 void bitmap_to_arr32(u32 *buf, const unsigned long *bitmap, unsigned int nbits)
1348 {
1349         unsigned int i, halfwords;
1350
1351         halfwords = DIV_ROUND_UP(nbits, 32);
1352         for (i = 0; i < halfwords; i++) {
1353                 buf[i] = (u32) (bitmap[i/2] & UINT_MAX);
1354                 if (++i < halfwords)
1355                         buf[i] = (u32) (bitmap[i/2] >> 32);
1356         }
1357
1358         /* Clear tail bits in last element of array beyond nbits. */
1359         if (nbits % BITS_PER_LONG)
1360                 buf[halfwords - 1] &= (u32) (UINT_MAX >> ((-nbits) & 31));
1361 }
1362 EXPORT_SYMBOL(bitmap_to_arr32);
1363
1364 #endif