xref: /openbmc/linux/lib/bitmap.c (revision acf50233)
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 bool __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 false;
55 
56 	if (bits % BITS_PER_LONG)
57 		if ((bitmap1[k] ^ bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))
58 			return false;
59 
60 	return true;
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 bool __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 true;
313 
314 	if (bits % BITS_PER_LONG)
315 		if ((bitmap1[k] & bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))
316 			return true;
317 	return false;
318 }
319 EXPORT_SYMBOL(__bitmap_intersects);
320 
321 bool __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 false;
328 
329 	if (bits % BITS_PER_LONG)
330 		if ((bitmap1[k] & ~bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))
331 			return false;
332 	return true;
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  * bitmap_print_to_buf  - convert bitmap to list or hex format ASCII string
492  * @list: indicates whether the bitmap must be list
493  *      true:  print in decimal list format
494  *      false: print in hexadecimal bitmask format
495  * @buf: buffer into which string is placed
496  * @maskp: pointer to bitmap to convert
497  * @nmaskbits: size of bitmap, in bits
498  * @off: in the string from which we are copying, We copy to @buf
499  * @count: the maximum number of bytes to print
500  */
501 static int bitmap_print_to_buf(bool list, char *buf, const unsigned long *maskp,
502 		int nmaskbits, loff_t off, size_t count)
503 {
504 	const char *fmt = list ? "%*pbl\n" : "%*pb\n";
505 	ssize_t size;
506 	void *data;
507 
508 	data = kasprintf(GFP_KERNEL, fmt, nmaskbits, maskp);
509 	if (!data)
510 		return -ENOMEM;
511 
512 	size = memory_read_from_buffer(buf, count, &off, data, strlen(data) + 1);
513 	kfree(data);
514 
515 	return size;
516 }
517 
518 /**
519  * bitmap_print_bitmask_to_buf  - convert bitmap to hex bitmask format ASCII string
520  * @buf: buffer into which string is placed
521  * @maskp: pointer to bitmap to convert
522  * @nmaskbits: size of bitmap, in bits
523  * @off: in the string from which we are copying, We copy to @buf
524  * @count: the maximum number of bytes to print
525  *
526  * The bitmap_print_to_pagebuf() is used indirectly via its cpumap wrapper
527  * cpumap_print_to_pagebuf() or directly by drivers to export hexadecimal
528  * bitmask and decimal list to userspace by sysfs ABI.
529  * Drivers might be using a normal attribute for this kind of ABIs. A
530  * normal attribute typically has show entry as below::
531  *
532  *   static ssize_t example_attribute_show(struct device *dev,
533  * 		struct device_attribute *attr, char *buf)
534  *   {
535  * 	...
536  * 	return bitmap_print_to_pagebuf(true, buf, &mask, nr_trig_max);
537  *   }
538  *
539  * show entry of attribute has no offset and count parameters and this
540  * means the file is limited to one page only.
541  * bitmap_print_to_pagebuf() API works terribly well for this kind of
542  * normal attribute with buf parameter and without offset, count::
543  *
544  *   bitmap_print_to_pagebuf(bool list, char *buf, const unsigned long *maskp,
545  * 			   int nmaskbits)
546  *   {
547  *   }
548  *
549  * The problem is once we have a large bitmap, we have a chance to get a
550  * bitmask or list more than one page. Especially for list, it could be
551  * as complex as 0,3,5,7,9,... We have no simple way to know it exact size.
552  * It turns out bin_attribute is a way to break this limit. bin_attribute
553  * has show entry as below::
554  *
555  *   static ssize_t
556  *   example_bin_attribute_show(struct file *filp, struct kobject *kobj,
557  * 		struct bin_attribute *attr, char *buf,
558  * 		loff_t offset, size_t count)
559  *   {
560  * 	...
561  *   }
562  *
563  * With the new offset and count parameters, this makes sysfs ABI be able
564  * to support file size more than one page. For example, offset could be
565  * >= 4096.
566  * bitmap_print_bitmask_to_buf(), bitmap_print_list_to_buf() wit their
567  * cpumap wrapper cpumap_print_bitmask_to_buf(), cpumap_print_list_to_buf()
568  * make those drivers be able to support large bitmask and list after they
569  * move to use bin_attribute. In result, we have to pass the corresponding
570  * parameters such as off, count from bin_attribute show entry to this API.
571  *
572  * The role of cpumap_print_bitmask_to_buf() and cpumap_print_list_to_buf()
573  * is similar with cpumap_print_to_pagebuf(),  the difference is that
574  * bitmap_print_to_pagebuf() mainly serves sysfs attribute with the assumption
575  * the destination buffer is exactly one page and won't be more than one page.
576  * cpumap_print_bitmask_to_buf() and cpumap_print_list_to_buf(), on the other
577  * hand, mainly serves bin_attribute which doesn't work with exact one page,
578  * and it can break the size limit of converted decimal list and hexadecimal
579  * bitmask.
580  *
581  * WARNING!
582  *
583  * This function is not a replacement for sprintf() or bitmap_print_to_pagebuf().
584  * It is intended to workaround sysfs limitations discussed above and should be
585  * used carefully in general case for the following reasons:
586  *
587  *  - Time complexity is O(nbits^2/count), comparing to O(nbits) for snprintf().
588  *  - Memory complexity is O(nbits), comparing to O(1) for snprintf().
589  *  - @off and @count are NOT offset and number of bits to print.
590  *  - If printing part of bitmap as list, the resulting string is not a correct
591  *    list representation of bitmap. Particularly, some bits within or out of
592  *    related interval may be erroneously set or unset. The format of the string
593  *    may be broken, so bitmap_parselist-like parser may fail parsing it.
594  *  - If printing the whole bitmap as list by parts, user must ensure the order
595  *    of calls of the function such that the offset is incremented linearly.
596  *  - If printing the whole bitmap as list by parts, user must keep bitmap
597  *    unchanged between the very first and very last call. Otherwise concatenated
598  *    result may be incorrect, and format may be broken.
599  *
600  * Returns the number of characters actually printed to @buf
601  */
602 int bitmap_print_bitmask_to_buf(char *buf, const unsigned long *maskp,
603 				int nmaskbits, loff_t off, size_t count)
604 {
605 	return bitmap_print_to_buf(false, buf, maskp, nmaskbits, off, count);
606 }
607 EXPORT_SYMBOL(bitmap_print_bitmask_to_buf);
608 
609 /**
610  * bitmap_print_list_to_buf  - convert bitmap to decimal list format ASCII string
611  * @buf: buffer into which string is placed
612  * @maskp: pointer to bitmap to convert
613  * @nmaskbits: size of bitmap, in bits
614  * @off: in the string from which we are copying, We copy to @buf
615  * @count: the maximum number of bytes to print
616  *
617  * Everything is same with the above bitmap_print_bitmask_to_buf() except
618  * the print format.
619  */
620 int bitmap_print_list_to_buf(char *buf, const unsigned long *maskp,
621 			     int nmaskbits, loff_t off, size_t count)
622 {
623 	return bitmap_print_to_buf(true, buf, maskp, nmaskbits, off, count);
624 }
625 EXPORT_SYMBOL(bitmap_print_list_to_buf);
626 
627 /*
628  * Region 9-38:4/10 describes the following bitmap structure:
629  * 0	   9  12    18			38	     N
630  * .........****......****......****..................
631  *	    ^  ^     ^			 ^	     ^
632  *      start  off   group_len	       end	 nbits
633  */
634 struct region {
635 	unsigned int start;
636 	unsigned int off;
637 	unsigned int group_len;
638 	unsigned int end;
639 	unsigned int nbits;
640 };
641 
642 static void bitmap_set_region(const struct region *r, unsigned long *bitmap)
643 {
644 	unsigned int start;
645 
646 	for (start = r->start; start <= r->end; start += r->group_len)
647 		bitmap_set(bitmap, start, min(r->end - start + 1, r->off));
648 }
649 
650 static int bitmap_check_region(const struct region *r)
651 {
652 	if (r->start > r->end || r->group_len == 0 || r->off > r->group_len)
653 		return -EINVAL;
654 
655 	if (r->end >= r->nbits)
656 		return -ERANGE;
657 
658 	return 0;
659 }
660 
661 static const char *bitmap_getnum(const char *str, unsigned int *num,
662 				 unsigned int lastbit)
663 {
664 	unsigned long long n;
665 	unsigned int len;
666 
667 	if (str[0] == 'N') {
668 		*num = lastbit;
669 		return str + 1;
670 	}
671 
672 	len = _parse_integer(str, 10, &n);
673 	if (!len)
674 		return ERR_PTR(-EINVAL);
675 	if (len & KSTRTOX_OVERFLOW || n != (unsigned int)n)
676 		return ERR_PTR(-EOVERFLOW);
677 
678 	*num = n;
679 	return str + len;
680 }
681 
682 static inline bool end_of_str(char c)
683 {
684 	return c == '\0' || c == '\n';
685 }
686 
687 static inline bool __end_of_region(char c)
688 {
689 	return isspace(c) || c == ',';
690 }
691 
692 static inline bool end_of_region(char c)
693 {
694 	return __end_of_region(c) || end_of_str(c);
695 }
696 
697 /*
698  * The format allows commas and whitespaces at the beginning
699  * of the region.
700  */
701 static const char *bitmap_find_region(const char *str)
702 {
703 	while (__end_of_region(*str))
704 		str++;
705 
706 	return end_of_str(*str) ? NULL : str;
707 }
708 
709 static const char *bitmap_find_region_reverse(const char *start, const char *end)
710 {
711 	while (start <= end && __end_of_region(*end))
712 		end--;
713 
714 	return end;
715 }
716 
717 static const char *bitmap_parse_region(const char *str, struct region *r)
718 {
719 	unsigned int lastbit = r->nbits - 1;
720 
721 	if (!strncasecmp(str, "all", 3)) {
722 		r->start = 0;
723 		r->end = lastbit;
724 		str += 3;
725 
726 		goto check_pattern;
727 	}
728 
729 	str = bitmap_getnum(str, &r->start, lastbit);
730 	if (IS_ERR(str))
731 		return str;
732 
733 	if (end_of_region(*str))
734 		goto no_end;
735 
736 	if (*str != '-')
737 		return ERR_PTR(-EINVAL);
738 
739 	str = bitmap_getnum(str + 1, &r->end, lastbit);
740 	if (IS_ERR(str))
741 		return str;
742 
743 check_pattern:
744 	if (end_of_region(*str))
745 		goto no_pattern;
746 
747 	if (*str != ':')
748 		return ERR_PTR(-EINVAL);
749 
750 	str = bitmap_getnum(str + 1, &r->off, lastbit);
751 	if (IS_ERR(str))
752 		return str;
753 
754 	if (*str != '/')
755 		return ERR_PTR(-EINVAL);
756 
757 	return bitmap_getnum(str + 1, &r->group_len, lastbit);
758 
759 no_end:
760 	r->end = r->start;
761 no_pattern:
762 	r->off = r->end + 1;
763 	r->group_len = r->end + 1;
764 
765 	return end_of_str(*str) ? NULL : str;
766 }
767 
768 /**
769  * bitmap_parselist - convert list format ASCII string to bitmap
770  * @buf: read user string from this buffer; must be terminated
771  *    with a \0 or \n.
772  * @maskp: write resulting mask here
773  * @nmaskbits: number of bits in mask to be written
774  *
775  * Input format is a comma-separated list of decimal numbers and
776  * ranges.  Consecutively set bits are shown as two hyphen-separated
777  * decimal numbers, the smallest and largest bit numbers set in
778  * the range.
779  * Optionally each range can be postfixed to denote that only parts of it
780  * should be set. The range will divided to groups of specific size.
781  * From each group will be used only defined amount of bits.
782  * Syntax: range:used_size/group_size
783  * Example: 0-1023:2/256 ==> 0,1,256,257,512,513,768,769
784  * The value 'N' can be used as a dynamically substituted token for the
785  * maximum allowed value; i.e (nmaskbits - 1).  Keep in mind that it is
786  * dynamic, so if system changes cause the bitmap width to change, such
787  * as more cores in a CPU list, then any ranges using N will also change.
788  *
789  * Returns: 0 on success, -errno on invalid input strings. Error values:
790  *
791  *   - ``-EINVAL``: wrong region format
792  *   - ``-EINVAL``: invalid character in string
793  *   - ``-ERANGE``: bit number specified too large for mask
794  *   - ``-EOVERFLOW``: integer overflow in the input parameters
795  */
796 int bitmap_parselist(const char *buf, unsigned long *maskp, int nmaskbits)
797 {
798 	struct region r;
799 	long ret;
800 
801 	r.nbits = nmaskbits;
802 	bitmap_zero(maskp, r.nbits);
803 
804 	while (buf) {
805 		buf = bitmap_find_region(buf);
806 		if (buf == NULL)
807 			return 0;
808 
809 		buf = bitmap_parse_region(buf, &r);
810 		if (IS_ERR(buf))
811 			return PTR_ERR(buf);
812 
813 		ret = bitmap_check_region(&r);
814 		if (ret)
815 			return ret;
816 
817 		bitmap_set_region(&r, maskp);
818 	}
819 
820 	return 0;
821 }
822 EXPORT_SYMBOL(bitmap_parselist);
823 
824 
825 /**
826  * bitmap_parselist_user() - convert user buffer's list format ASCII
827  * string to bitmap
828  *
829  * @ubuf: pointer to user buffer containing string.
830  * @ulen: buffer size in bytes.  If string is smaller than this
831  *    then it must be terminated with a \0.
832  * @maskp: pointer to bitmap array that will contain result.
833  * @nmaskbits: size of bitmap, in bits.
834  *
835  * Wrapper for bitmap_parselist(), providing it with user buffer.
836  */
837 int bitmap_parselist_user(const char __user *ubuf,
838 			unsigned int ulen, unsigned long *maskp,
839 			int nmaskbits)
840 {
841 	char *buf;
842 	int ret;
843 
844 	buf = memdup_user_nul(ubuf, ulen);
845 	if (IS_ERR(buf))
846 		return PTR_ERR(buf);
847 
848 	ret = bitmap_parselist(buf, maskp, nmaskbits);
849 
850 	kfree(buf);
851 	return ret;
852 }
853 EXPORT_SYMBOL(bitmap_parselist_user);
854 
855 static const char *bitmap_get_x32_reverse(const char *start,
856 					const char *end, u32 *num)
857 {
858 	u32 ret = 0;
859 	int c, i;
860 
861 	for (i = 0; i < 32; i += 4) {
862 		c = hex_to_bin(*end--);
863 		if (c < 0)
864 			return ERR_PTR(-EINVAL);
865 
866 		ret |= c << i;
867 
868 		if (start > end || __end_of_region(*end))
869 			goto out;
870 	}
871 
872 	if (hex_to_bin(*end--) >= 0)
873 		return ERR_PTR(-EOVERFLOW);
874 out:
875 	*num = ret;
876 	return end;
877 }
878 
879 /**
880  * bitmap_parse - convert an ASCII hex string into a bitmap.
881  * @start: pointer to buffer containing string.
882  * @buflen: buffer size in bytes.  If string is smaller than this
883  *    then it must be terminated with a \0 or \n. In that case,
884  *    UINT_MAX may be provided instead of string length.
885  * @maskp: pointer to bitmap array that will contain result.
886  * @nmaskbits: size of bitmap, in bits.
887  *
888  * Commas group hex digits into chunks.  Each chunk defines exactly 32
889  * bits of the resultant bitmask.  No chunk may specify a value larger
890  * than 32 bits (%-EOVERFLOW), and if a chunk specifies a smaller value
891  * then leading 0-bits are prepended.  %-EINVAL is returned for illegal
892  * characters. Grouping such as "1,,5", ",44", "," or "" is allowed.
893  * Leading, embedded and trailing whitespace accepted.
894  */
895 int bitmap_parse(const char *start, unsigned int buflen,
896 		unsigned long *maskp, int nmaskbits)
897 {
898 	const char *end = strnchrnul(start, buflen, '\n') - 1;
899 	int chunks = BITS_TO_U32(nmaskbits);
900 	u32 *bitmap = (u32 *)maskp;
901 	int unset_bit;
902 	int chunk;
903 
904 	for (chunk = 0; ; chunk++) {
905 		end = bitmap_find_region_reverse(start, end);
906 		if (start > end)
907 			break;
908 
909 		if (!chunks--)
910 			return -EOVERFLOW;
911 
912 #if defined(CONFIG_64BIT) && defined(__BIG_ENDIAN)
913 		end = bitmap_get_x32_reverse(start, end, &bitmap[chunk ^ 1]);
914 #else
915 		end = bitmap_get_x32_reverse(start, end, &bitmap[chunk]);
916 #endif
917 		if (IS_ERR(end))
918 			return PTR_ERR(end);
919 	}
920 
921 	unset_bit = (BITS_TO_U32(nmaskbits) - chunks) * 32;
922 	if (unset_bit < nmaskbits) {
923 		bitmap_clear(maskp, unset_bit, nmaskbits - unset_bit);
924 		return 0;
925 	}
926 
927 	if (find_next_bit(maskp, unset_bit, nmaskbits) != unset_bit)
928 		return -EOVERFLOW;
929 
930 	return 0;
931 }
932 EXPORT_SYMBOL(bitmap_parse);
933 
934 /**
935  * bitmap_pos_to_ord - find ordinal of set bit at given position in bitmap
936  *	@buf: pointer to a bitmap
937  *	@pos: a bit position in @buf (0 <= @pos < @nbits)
938  *	@nbits: number of valid bit positions in @buf
939  *
940  * Map the bit at position @pos in @buf (of length @nbits) to the
941  * ordinal of which set bit it is.  If it is not set or if @pos
942  * is not a valid bit position, map to -1.
943  *
944  * If for example, just bits 4 through 7 are set in @buf, then @pos
945  * values 4 through 7 will get mapped to 0 through 3, respectively,
946  * and other @pos values will get mapped to -1.  When @pos value 7
947  * gets mapped to (returns) @ord value 3 in this example, that means
948  * that bit 7 is the 3rd (starting with 0th) set bit in @buf.
949  *
950  * The bit positions 0 through @bits are valid positions in @buf.
951  */
952 static int bitmap_pos_to_ord(const unsigned long *buf, unsigned int pos, unsigned int nbits)
953 {
954 	if (pos >= nbits || !test_bit(pos, buf))
955 		return -1;
956 
957 	return __bitmap_weight(buf, pos);
958 }
959 
960 /**
961  * bitmap_ord_to_pos - find position of n-th set bit in bitmap
962  *	@buf: pointer to bitmap
963  *	@ord: ordinal bit position (n-th set bit, n >= 0)
964  *	@nbits: number of valid bit positions in @buf
965  *
966  * Map the ordinal offset of bit @ord in @buf to its position in @buf.
967  * Value of @ord should be in range 0 <= @ord < weight(buf). If @ord
968  * >= weight(buf), returns @nbits.
969  *
970  * If for example, just bits 4 through 7 are set in @buf, then @ord
971  * values 0 through 3 will get mapped to 4 through 7, respectively,
972  * and all other @ord values returns @nbits.  When @ord value 3
973  * gets mapped to (returns) @pos value 7 in this example, that means
974  * that the 3rd set bit (starting with 0th) is at position 7 in @buf.
975  *
976  * The bit positions 0 through @nbits-1 are valid positions in @buf.
977  */
978 unsigned int bitmap_ord_to_pos(const unsigned long *buf, unsigned int ord, unsigned int nbits)
979 {
980 	unsigned int pos;
981 
982 	for (pos = find_first_bit(buf, nbits);
983 	     pos < nbits && ord;
984 	     pos = find_next_bit(buf, nbits, pos + 1))
985 		ord--;
986 
987 	return pos;
988 }
989 
990 /**
991  * bitmap_remap - Apply map defined by a pair of bitmaps to another bitmap
992  *	@dst: remapped result
993  *	@src: subset to be remapped
994  *	@old: defines domain of map
995  *	@new: defines range of map
996  *	@nbits: number of bits in each of these bitmaps
997  *
998  * Let @old and @new define a mapping of bit positions, such that
999  * whatever position is held by the n-th set bit in @old is mapped
1000  * to the n-th set bit in @new.  In the more general case, allowing
1001  * for the possibility that the weight 'w' of @new is less than the
1002  * weight of @old, map the position of the n-th set bit in @old to
1003  * the position of the m-th set bit in @new, where m == n % w.
1004  *
1005  * If either of the @old and @new bitmaps are empty, or if @src and
1006  * @dst point to the same location, then this routine copies @src
1007  * to @dst.
1008  *
1009  * The positions of unset bits in @old are mapped to themselves
1010  * (the identify map).
1011  *
1012  * Apply the above specified mapping to @src, placing the result in
1013  * @dst, clearing any bits previously set in @dst.
1014  *
1015  * For example, lets say that @old has bits 4 through 7 set, and
1016  * @new has bits 12 through 15 set.  This defines the mapping of bit
1017  * position 4 to 12, 5 to 13, 6 to 14 and 7 to 15, and of all other
1018  * bit positions unchanged.  So if say @src comes into this routine
1019  * with bits 1, 5 and 7 set, then @dst should leave with bits 1,
1020  * 13 and 15 set.
1021  */
1022 void bitmap_remap(unsigned long *dst, const unsigned long *src,
1023 		const unsigned long *old, const unsigned long *new,
1024 		unsigned int nbits)
1025 {
1026 	unsigned int oldbit, w;
1027 
1028 	if (dst == src)		/* following doesn't handle inplace remaps */
1029 		return;
1030 	bitmap_zero(dst, nbits);
1031 
1032 	w = bitmap_weight(new, nbits);
1033 	for_each_set_bit(oldbit, src, nbits) {
1034 		int n = bitmap_pos_to_ord(old, oldbit, nbits);
1035 
1036 		if (n < 0 || w == 0)
1037 			set_bit(oldbit, dst);	/* identity map */
1038 		else
1039 			set_bit(bitmap_ord_to_pos(new, n % w, nbits), dst);
1040 	}
1041 }
1042 EXPORT_SYMBOL(bitmap_remap);
1043 
1044 /**
1045  * bitmap_bitremap - Apply map defined by a pair of bitmaps to a single bit
1046  *	@oldbit: bit position to be mapped
1047  *	@old: defines domain of map
1048  *	@new: defines range of map
1049  *	@bits: number of bits in each of these bitmaps
1050  *
1051  * Let @old and @new define a mapping of bit positions, such that
1052  * whatever position is held by the n-th set bit in @old is mapped
1053  * to the n-th set bit in @new.  In the more general case, allowing
1054  * for the possibility that the weight 'w' of @new is less than the
1055  * weight of @old, map the position of the n-th set bit in @old to
1056  * the position of the m-th set bit in @new, where m == n % w.
1057  *
1058  * The positions of unset bits in @old are mapped to themselves
1059  * (the identify map).
1060  *
1061  * Apply the above specified mapping to bit position @oldbit, returning
1062  * the new bit position.
1063  *
1064  * For example, lets say that @old has bits 4 through 7 set, and
1065  * @new has bits 12 through 15 set.  This defines the mapping of bit
1066  * position 4 to 12, 5 to 13, 6 to 14 and 7 to 15, and of all other
1067  * bit positions unchanged.  So if say @oldbit is 5, then this routine
1068  * returns 13.
1069  */
1070 int bitmap_bitremap(int oldbit, const unsigned long *old,
1071 				const unsigned long *new, int bits)
1072 {
1073 	int w = bitmap_weight(new, bits);
1074 	int n = bitmap_pos_to_ord(old, oldbit, bits);
1075 	if (n < 0 || w == 0)
1076 		return oldbit;
1077 	else
1078 		return bitmap_ord_to_pos(new, n % w, bits);
1079 }
1080 EXPORT_SYMBOL(bitmap_bitremap);
1081 
1082 #ifdef CONFIG_NUMA
1083 /**
1084  * bitmap_onto - translate one bitmap relative to another
1085  *	@dst: resulting translated bitmap
1086  * 	@orig: original untranslated bitmap
1087  * 	@relmap: bitmap relative to which translated
1088  *	@bits: number of bits in each of these bitmaps
1089  *
1090  * Set the n-th bit of @dst iff there exists some m such that the
1091  * n-th bit of @relmap is set, the m-th bit of @orig is set, and
1092  * the n-th bit of @relmap is also the m-th _set_ bit of @relmap.
1093  * (If you understood the previous sentence the first time your
1094  * read it, you're overqualified for your current job.)
1095  *
1096  * In other words, @orig is mapped onto (surjectively) @dst,
1097  * using the map { <n, m> | the n-th bit of @relmap is the
1098  * m-th set bit of @relmap }.
1099  *
1100  * Any set bits in @orig above bit number W, where W is the
1101  * weight of (number of set bits in) @relmap are mapped nowhere.
1102  * In particular, if for all bits m set in @orig, m >= W, then
1103  * @dst will end up empty.  In situations where the possibility
1104  * of such an empty result is not desired, one way to avoid it is
1105  * to use the bitmap_fold() operator, below, to first fold the
1106  * @orig bitmap over itself so that all its set bits x are in the
1107  * range 0 <= x < W.  The bitmap_fold() operator does this by
1108  * setting the bit (m % W) in @dst, for each bit (m) set in @orig.
1109  *
1110  * Example [1] for bitmap_onto():
1111  *  Let's say @relmap has bits 30-39 set, and @orig has bits
1112  *  1, 3, 5, 7, 9 and 11 set.  Then on return from this routine,
1113  *  @dst will have bits 31, 33, 35, 37 and 39 set.
1114  *
1115  *  When bit 0 is set in @orig, it means turn on the bit in
1116  *  @dst corresponding to whatever is the first bit (if any)
1117  *  that is turned on in @relmap.  Since bit 0 was off in the
1118  *  above example, we leave off that bit (bit 30) in @dst.
1119  *
1120  *  When bit 1 is set in @orig (as in the above example), it
1121  *  means turn on the bit in @dst corresponding to whatever
1122  *  is the second bit that is turned on in @relmap.  The second
1123  *  bit in @relmap that was turned on in the above example was
1124  *  bit 31, so we turned on bit 31 in @dst.
1125  *
1126  *  Similarly, we turned on bits 33, 35, 37 and 39 in @dst,
1127  *  because they were the 4th, 6th, 8th and 10th set bits
1128  *  set in @relmap, and the 4th, 6th, 8th and 10th bits of
1129  *  @orig (i.e. bits 3, 5, 7 and 9) were also set.
1130  *
1131  *  When bit 11 is set in @orig, it means turn on the bit in
1132  *  @dst corresponding to whatever is the twelfth bit that is
1133  *  turned on in @relmap.  In the above example, there were
1134  *  only ten bits turned on in @relmap (30..39), so that bit
1135  *  11 was set in @orig had no affect on @dst.
1136  *
1137  * Example [2] for bitmap_fold() + bitmap_onto():
1138  *  Let's say @relmap has these ten bits set::
1139  *
1140  *		40 41 42 43 45 48 53 61 74 95
1141  *
1142  *  (for the curious, that's 40 plus the first ten terms of the
1143  *  Fibonacci sequence.)
1144  *
1145  *  Further lets say we use the following code, invoking
1146  *  bitmap_fold() then bitmap_onto, as suggested above to
1147  *  avoid the possibility of an empty @dst result::
1148  *
1149  *	unsigned long *tmp;	// a temporary bitmap's bits
1150  *
1151  *	bitmap_fold(tmp, orig, bitmap_weight(relmap, bits), bits);
1152  *	bitmap_onto(dst, tmp, relmap, bits);
1153  *
1154  *  Then this table shows what various values of @dst would be, for
1155  *  various @orig's.  I list the zero-based positions of each set bit.
1156  *  The tmp column shows the intermediate result, as computed by
1157  *  using bitmap_fold() to fold the @orig bitmap modulo ten
1158  *  (the weight of @relmap):
1159  *
1160  *      =============== ============== =================
1161  *      @orig           tmp            @dst
1162  *      0                0             40
1163  *      1                1             41
1164  *      9                9             95
1165  *      10               0             40 [#f1]_
1166  *      1 3 5 7          1 3 5 7       41 43 48 61
1167  *      0 1 2 3 4        0 1 2 3 4     40 41 42 43 45
1168  *      0 9 18 27        0 9 8 7       40 61 74 95
1169  *      0 10 20 30       0             40
1170  *      0 11 22 33       0 1 2 3       40 41 42 43
1171  *      0 12 24 36       0 2 4 6       40 42 45 53
1172  *      78 102 211       1 2 8         41 42 74 [#f1]_
1173  *      =============== ============== =================
1174  *
1175  * .. [#f1]
1176  *
1177  *     For these marked lines, if we hadn't first done bitmap_fold()
1178  *     into tmp, then the @dst result would have been empty.
1179  *
1180  * If either of @orig or @relmap is empty (no set bits), then @dst
1181  * will be returned empty.
1182  *
1183  * If (as explained above) the only set bits in @orig are in positions
1184  * m where m >= W, (where W is the weight of @relmap) then @dst will
1185  * once again be returned empty.
1186  *
1187  * All bits in @dst not set by the above rule are cleared.
1188  */
1189 void bitmap_onto(unsigned long *dst, const unsigned long *orig,
1190 			const unsigned long *relmap, unsigned int bits)
1191 {
1192 	unsigned int n, m;	/* same meaning as in above comment */
1193 
1194 	if (dst == orig)	/* following doesn't handle inplace mappings */
1195 		return;
1196 	bitmap_zero(dst, bits);
1197 
1198 	/*
1199 	 * The following code is a more efficient, but less
1200 	 * obvious, equivalent to the loop:
1201 	 *	for (m = 0; m < bitmap_weight(relmap, bits); m++) {
1202 	 *		n = bitmap_ord_to_pos(orig, m, bits);
1203 	 *		if (test_bit(m, orig))
1204 	 *			set_bit(n, dst);
1205 	 *	}
1206 	 */
1207 
1208 	m = 0;
1209 	for_each_set_bit(n, relmap, bits) {
1210 		/* m == bitmap_pos_to_ord(relmap, n, bits) */
1211 		if (test_bit(m, orig))
1212 			set_bit(n, dst);
1213 		m++;
1214 	}
1215 }
1216 
1217 /**
1218  * bitmap_fold - fold larger bitmap into smaller, modulo specified size
1219  *	@dst: resulting smaller bitmap
1220  *	@orig: original larger bitmap
1221  *	@sz: specified size
1222  *	@nbits: number of bits in each of these bitmaps
1223  *
1224  * For each bit oldbit in @orig, set bit oldbit mod @sz in @dst.
1225  * Clear all other bits in @dst.  See further the comment and
1226  * Example [2] for bitmap_onto() for why and how to use this.
1227  */
1228 void bitmap_fold(unsigned long *dst, const unsigned long *orig,
1229 			unsigned int sz, unsigned int nbits)
1230 {
1231 	unsigned int oldbit;
1232 
1233 	if (dst == orig)	/* following doesn't handle inplace mappings */
1234 		return;
1235 	bitmap_zero(dst, nbits);
1236 
1237 	for_each_set_bit(oldbit, orig, nbits)
1238 		set_bit(oldbit % sz, dst);
1239 }
1240 #endif /* CONFIG_NUMA */
1241 
1242 /*
1243  * Common code for bitmap_*_region() routines.
1244  *	bitmap: array of unsigned longs corresponding to the bitmap
1245  *	pos: the beginning of the region
1246  *	order: region size (log base 2 of number of bits)
1247  *	reg_op: operation(s) to perform on that region of bitmap
1248  *
1249  * Can set, verify and/or release a region of bits in a bitmap,
1250  * depending on which combination of REG_OP_* flag bits is set.
1251  *
1252  * A region of a bitmap is a sequence of bits in the bitmap, of
1253  * some size '1 << order' (a power of two), aligned to that same
1254  * '1 << order' power of two.
1255  *
1256  * Returns 1 if REG_OP_ISFREE succeeds (region is all zero bits).
1257  * Returns 0 in all other cases and reg_ops.
1258  */
1259 
1260 enum {
1261 	REG_OP_ISFREE,		/* true if region is all zero bits */
1262 	REG_OP_ALLOC,		/* set all bits in region */
1263 	REG_OP_RELEASE,		/* clear all bits in region */
1264 };
1265 
1266 static int __reg_op(unsigned long *bitmap, unsigned int pos, int order, int reg_op)
1267 {
1268 	int nbits_reg;		/* number of bits in region */
1269 	int index;		/* index first long of region in bitmap */
1270 	int offset;		/* bit offset region in bitmap[index] */
1271 	int nlongs_reg;		/* num longs spanned by region in bitmap */
1272 	int nbitsinlong;	/* num bits of region in each spanned long */
1273 	unsigned long mask;	/* bitmask for one long of region */
1274 	int i;			/* scans bitmap by longs */
1275 	int ret = 0;		/* return value */
1276 
1277 	/*
1278 	 * Either nlongs_reg == 1 (for small orders that fit in one long)
1279 	 * or (offset == 0 && mask == ~0UL) (for larger multiword orders.)
1280 	 */
1281 	nbits_reg = 1 << order;
1282 	index = pos / BITS_PER_LONG;
1283 	offset = pos - (index * BITS_PER_LONG);
1284 	nlongs_reg = BITS_TO_LONGS(nbits_reg);
1285 	nbitsinlong = min(nbits_reg,  BITS_PER_LONG);
1286 
1287 	/*
1288 	 * Can't do "mask = (1UL << nbitsinlong) - 1", as that
1289 	 * overflows if nbitsinlong == BITS_PER_LONG.
1290 	 */
1291 	mask = (1UL << (nbitsinlong - 1));
1292 	mask += mask - 1;
1293 	mask <<= offset;
1294 
1295 	switch (reg_op) {
1296 	case REG_OP_ISFREE:
1297 		for (i = 0; i < nlongs_reg; i++) {
1298 			if (bitmap[index + i] & mask)
1299 				goto done;
1300 		}
1301 		ret = 1;	/* all bits in region free (zero) */
1302 		break;
1303 
1304 	case REG_OP_ALLOC:
1305 		for (i = 0; i < nlongs_reg; i++)
1306 			bitmap[index + i] |= mask;
1307 		break;
1308 
1309 	case REG_OP_RELEASE:
1310 		for (i = 0; i < nlongs_reg; i++)
1311 			bitmap[index + i] &= ~mask;
1312 		break;
1313 	}
1314 done:
1315 	return ret;
1316 }
1317 
1318 /**
1319  * bitmap_find_free_region - find a contiguous aligned mem region
1320  *	@bitmap: array of unsigned longs corresponding to the bitmap
1321  *	@bits: number of bits in the bitmap
1322  *	@order: region size (log base 2 of number of bits) to find
1323  *
1324  * Find a region of free (zero) bits in a @bitmap of @bits bits and
1325  * allocate them (set them to one).  Only consider regions of length
1326  * a power (@order) of two, aligned to that power of two, which
1327  * makes the search algorithm much faster.
1328  *
1329  * Return the bit offset in bitmap of the allocated region,
1330  * or -errno on failure.
1331  */
1332 int bitmap_find_free_region(unsigned long *bitmap, unsigned int bits, int order)
1333 {
1334 	unsigned int pos, end;		/* scans bitmap by regions of size order */
1335 
1336 	for (pos = 0 ; (end = pos + (1U << order)) <= bits; pos = end) {
1337 		if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE))
1338 			continue;
1339 		__reg_op(bitmap, pos, order, REG_OP_ALLOC);
1340 		return pos;
1341 	}
1342 	return -ENOMEM;
1343 }
1344 EXPORT_SYMBOL(bitmap_find_free_region);
1345 
1346 /**
1347  * bitmap_release_region - release allocated bitmap region
1348  *	@bitmap: array of unsigned longs corresponding to the bitmap
1349  *	@pos: beginning of bit region to release
1350  *	@order: region size (log base 2 of number of bits) to release
1351  *
1352  * This is the complement to __bitmap_find_free_region() and releases
1353  * the found region (by clearing it in the bitmap).
1354  *
1355  * No return value.
1356  */
1357 void bitmap_release_region(unsigned long *bitmap, unsigned int pos, int order)
1358 {
1359 	__reg_op(bitmap, pos, order, REG_OP_RELEASE);
1360 }
1361 EXPORT_SYMBOL(bitmap_release_region);
1362 
1363 /**
1364  * bitmap_allocate_region - allocate bitmap region
1365  *	@bitmap: array of unsigned longs corresponding to the bitmap
1366  *	@pos: beginning of bit region to allocate
1367  *	@order: region size (log base 2 of number of bits) to allocate
1368  *
1369  * Allocate (set bits in) a specified region of a bitmap.
1370  *
1371  * Return 0 on success, or %-EBUSY if specified region wasn't
1372  * free (not all bits were zero).
1373  */
1374 int bitmap_allocate_region(unsigned long *bitmap, unsigned int pos, int order)
1375 {
1376 	if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE))
1377 		return -EBUSY;
1378 	return __reg_op(bitmap, pos, order, REG_OP_ALLOC);
1379 }
1380 EXPORT_SYMBOL(bitmap_allocate_region);
1381 
1382 /**
1383  * bitmap_copy_le - copy a bitmap, putting the bits into little-endian order.
1384  * @dst:   destination buffer
1385  * @src:   bitmap to copy
1386  * @nbits: number of bits in the bitmap
1387  *
1388  * Require nbits % BITS_PER_LONG == 0.
1389  */
1390 #ifdef __BIG_ENDIAN
1391 void bitmap_copy_le(unsigned long *dst, const unsigned long *src, unsigned int nbits)
1392 {
1393 	unsigned int i;
1394 
1395 	for (i = 0; i < nbits/BITS_PER_LONG; i++) {
1396 		if (BITS_PER_LONG == 64)
1397 			dst[i] = cpu_to_le64(src[i]);
1398 		else
1399 			dst[i] = cpu_to_le32(src[i]);
1400 	}
1401 }
1402 EXPORT_SYMBOL(bitmap_copy_le);
1403 #endif
1404 
1405 unsigned long *bitmap_alloc(unsigned int nbits, gfp_t flags)
1406 {
1407 	return kmalloc_array(BITS_TO_LONGS(nbits), sizeof(unsigned long),
1408 			     flags);
1409 }
1410 EXPORT_SYMBOL(bitmap_alloc);
1411 
1412 unsigned long *bitmap_zalloc(unsigned int nbits, gfp_t flags)
1413 {
1414 	return bitmap_alloc(nbits, flags | __GFP_ZERO);
1415 }
1416 EXPORT_SYMBOL(bitmap_zalloc);
1417 
1418 unsigned long *bitmap_alloc_node(unsigned int nbits, gfp_t flags, int node)
1419 {
1420 	return kmalloc_array_node(BITS_TO_LONGS(nbits), sizeof(unsigned long),
1421 				  flags, node);
1422 }
1423 EXPORT_SYMBOL(bitmap_alloc_node);
1424 
1425 unsigned long *bitmap_zalloc_node(unsigned int nbits, gfp_t flags, int node)
1426 {
1427 	return bitmap_alloc_node(nbits, flags | __GFP_ZERO, node);
1428 }
1429 EXPORT_SYMBOL(bitmap_zalloc_node);
1430 
1431 void bitmap_free(const unsigned long *bitmap)
1432 {
1433 	kfree(bitmap);
1434 }
1435 EXPORT_SYMBOL(bitmap_free);
1436 
1437 static void devm_bitmap_free(void *data)
1438 {
1439 	unsigned long *bitmap = data;
1440 
1441 	bitmap_free(bitmap);
1442 }
1443 
1444 unsigned long *devm_bitmap_alloc(struct device *dev,
1445 				 unsigned int nbits, gfp_t flags)
1446 {
1447 	unsigned long *bitmap;
1448 	int ret;
1449 
1450 	bitmap = bitmap_alloc(nbits, flags);
1451 	if (!bitmap)
1452 		return NULL;
1453 
1454 	ret = devm_add_action_or_reset(dev, devm_bitmap_free, bitmap);
1455 	if (ret)
1456 		return NULL;
1457 
1458 	return bitmap;
1459 }
1460 EXPORT_SYMBOL_GPL(devm_bitmap_alloc);
1461 
1462 unsigned long *devm_bitmap_zalloc(struct device *dev,
1463 				  unsigned int nbits, gfp_t flags)
1464 {
1465 	return devm_bitmap_alloc(dev, nbits, flags | __GFP_ZERO);
1466 }
1467 EXPORT_SYMBOL_GPL(devm_bitmap_zalloc);
1468 
1469 #if BITS_PER_LONG == 64
1470 /**
1471  * bitmap_from_arr32 - copy the contents of u32 array of bits to bitmap
1472  *	@bitmap: array of unsigned longs, the destination bitmap
1473  *	@buf: array of u32 (in host byte order), the source bitmap
1474  *	@nbits: number of bits in @bitmap
1475  */
1476 void bitmap_from_arr32(unsigned long *bitmap, const u32 *buf, unsigned int nbits)
1477 {
1478 	unsigned int i, halfwords;
1479 
1480 	halfwords = DIV_ROUND_UP(nbits, 32);
1481 	for (i = 0; i < halfwords; i++) {
1482 		bitmap[i/2] = (unsigned long) buf[i];
1483 		if (++i < halfwords)
1484 			bitmap[i/2] |= ((unsigned long) buf[i]) << 32;
1485 	}
1486 
1487 	/* Clear tail bits in last word beyond nbits. */
1488 	if (nbits % BITS_PER_LONG)
1489 		bitmap[(halfwords - 1) / 2] &= BITMAP_LAST_WORD_MASK(nbits);
1490 }
1491 EXPORT_SYMBOL(bitmap_from_arr32);
1492 
1493 /**
1494  * bitmap_to_arr32 - copy the contents of bitmap to a u32 array of bits
1495  *	@buf: array of u32 (in host byte order), the dest bitmap
1496  *	@bitmap: array of unsigned longs, the source bitmap
1497  *	@nbits: number of bits in @bitmap
1498  */
1499 void bitmap_to_arr32(u32 *buf, const unsigned long *bitmap, unsigned int nbits)
1500 {
1501 	unsigned int i, halfwords;
1502 
1503 	halfwords = DIV_ROUND_UP(nbits, 32);
1504 	for (i = 0; i < halfwords; i++) {
1505 		buf[i] = (u32) (bitmap[i/2] & UINT_MAX);
1506 		if (++i < halfwords)
1507 			buf[i] = (u32) (bitmap[i/2] >> 32);
1508 	}
1509 
1510 	/* Clear tail bits in last element of array beyond nbits. */
1511 	if (nbits % BITS_PER_LONG)
1512 		buf[halfwords - 1] &= (u32) (UINT_MAX >> ((-nbits) & 31));
1513 }
1514 EXPORT_SYMBOL(bitmap_to_arr32);
1515 #endif
1516 
1517 #if (BITS_PER_LONG == 32) && defined(__BIG_ENDIAN)
1518 /**
1519  * bitmap_from_arr64 - copy the contents of u64 array of bits to bitmap
1520  *	@bitmap: array of unsigned longs, the destination bitmap
1521  *	@buf: array of u64 (in host byte order), the source bitmap
1522  *	@nbits: number of bits in @bitmap
1523  */
1524 void bitmap_from_arr64(unsigned long *bitmap, const u64 *buf, unsigned int nbits)
1525 {
1526 	int n;
1527 
1528 	for (n = nbits; n > 0; n -= 64) {
1529 		u64 val = *buf++;
1530 
1531 		*bitmap++ = val;
1532 		if (n > 32)
1533 			*bitmap++ = val >> 32;
1534 	}
1535 
1536 	/*
1537 	 * Clear tail bits in the last word beyond nbits.
1538 	 *
1539 	 * Negative index is OK because here we point to the word next
1540 	 * to the last word of the bitmap, except for nbits == 0, which
1541 	 * is tested implicitly.
1542 	 */
1543 	if (nbits % BITS_PER_LONG)
1544 		bitmap[-1] &= BITMAP_LAST_WORD_MASK(nbits);
1545 }
1546 EXPORT_SYMBOL(bitmap_from_arr64);
1547 
1548 /**
1549  * bitmap_to_arr64 - copy the contents of bitmap to a u64 array of bits
1550  *	@buf: array of u64 (in host byte order), the dest bitmap
1551  *	@bitmap: array of unsigned longs, the source bitmap
1552  *	@nbits: number of bits in @bitmap
1553  */
1554 void bitmap_to_arr64(u64 *buf, const unsigned long *bitmap, unsigned int nbits)
1555 {
1556 	const unsigned long *end = bitmap + BITS_TO_LONGS(nbits);
1557 
1558 	while (bitmap < end) {
1559 		*buf = *bitmap++;
1560 		if (bitmap < end)
1561 			*buf |= (u64)(*bitmap++) << 32;
1562 		buf++;
1563 	}
1564 
1565 	/* Clear tail bits in the last element of array beyond nbits. */
1566 	if (nbits % 64)
1567 		buf[-1] &= GENMASK_ULL(nbits % 64, 0);
1568 }
1569 EXPORT_SYMBOL(bitmap_to_arr64);
1570 #endif
1571