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