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