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