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