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