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