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