Commit | Line | Data |
---|---|---|
1da177e4 LT |
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/module.h> | |
9 | #include <linux/ctype.h> | |
10 | #include <linux/errno.h> | |
11 | #include <linux/bitmap.h> | |
12 | #include <linux/bitops.h> | |
13 | #include <asm/uaccess.h> | |
14 | ||
15 | /* | |
16 | * bitmaps provide an array of bits, implemented using an an | |
17 | * array of unsigned longs. The number of valid bits in a | |
18 | * given bitmap does _not_ need to be an exact multiple of | |
19 | * BITS_PER_LONG. | |
20 | * | |
21 | * The possible unused bits in the last, partially used word | |
22 | * of a bitmap are 'don't care'. The implementation makes | |
23 | * no particular effort to keep them zero. It ensures that | |
24 | * their value will not affect the results of any operation. | |
25 | * The bitmap operations that return Boolean (bitmap_empty, | |
26 | * for example) or scalar (bitmap_weight, for example) results | |
27 | * carefully filter out these unused bits from impacting their | |
28 | * results. | |
29 | * | |
30 | * These operations actually hold to a slightly stronger rule: | |
31 | * if you don't input any bitmaps to these ops that have some | |
32 | * unused bits set, then they won't output any set unused bits | |
33 | * in output bitmaps. | |
34 | * | |
35 | * The byte ordering of bitmaps is more natural on little | |
36 | * endian architectures. See the big-endian headers | |
37 | * include/asm-ppc64/bitops.h and include/asm-s390/bitops.h | |
38 | * for the best explanations of this ordering. | |
39 | */ | |
40 | ||
41 | int __bitmap_empty(const unsigned long *bitmap, int bits) | |
42 | { | |
43 | int k, lim = bits/BITS_PER_LONG; | |
44 | for (k = 0; k < lim; ++k) | |
45 | if (bitmap[k]) | |
46 | return 0; | |
47 | ||
48 | if (bits % BITS_PER_LONG) | |
49 | if (bitmap[k] & BITMAP_LAST_WORD_MASK(bits)) | |
50 | return 0; | |
51 | ||
52 | return 1; | |
53 | } | |
54 | EXPORT_SYMBOL(__bitmap_empty); | |
55 | ||
56 | int __bitmap_full(const unsigned long *bitmap, int bits) | |
57 | { | |
58 | int k, lim = bits/BITS_PER_LONG; | |
59 | for (k = 0; k < lim; ++k) | |
60 | if (~bitmap[k]) | |
61 | return 0; | |
62 | ||
63 | if (bits % BITS_PER_LONG) | |
64 | if (~bitmap[k] & BITMAP_LAST_WORD_MASK(bits)) | |
65 | return 0; | |
66 | ||
67 | return 1; | |
68 | } | |
69 | EXPORT_SYMBOL(__bitmap_full); | |
70 | ||
71 | int __bitmap_equal(const unsigned long *bitmap1, | |
72 | const unsigned long *bitmap2, int bits) | |
73 | { | |
74 | int k, lim = bits/BITS_PER_LONG; | |
75 | for (k = 0; k < lim; ++k) | |
76 | if (bitmap1[k] != bitmap2[k]) | |
77 | return 0; | |
78 | ||
79 | if (bits % BITS_PER_LONG) | |
80 | if ((bitmap1[k] ^ bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits)) | |
81 | return 0; | |
82 | ||
83 | return 1; | |
84 | } | |
85 | EXPORT_SYMBOL(__bitmap_equal); | |
86 | ||
87 | void __bitmap_complement(unsigned long *dst, const unsigned long *src, int bits) | |
88 | { | |
89 | int k, lim = bits/BITS_PER_LONG; | |
90 | for (k = 0; k < lim; ++k) | |
91 | dst[k] = ~src[k]; | |
92 | ||
93 | if (bits % BITS_PER_LONG) | |
94 | dst[k] = ~src[k] & BITMAP_LAST_WORD_MASK(bits); | |
95 | } | |
96 | EXPORT_SYMBOL(__bitmap_complement); | |
97 | ||
98 | /* | |
99 | * __bitmap_shift_right - logical right shift of the bits in a bitmap | |
100 | * @dst - destination bitmap | |
101 | * @src - source bitmap | |
102 | * @nbits - shift by this many bits | |
103 | * @bits - bitmap size, in bits | |
104 | * | |
105 | * Shifting right (dividing) means moving bits in the MS -> LS bit | |
106 | * direction. Zeros are fed into the vacated MS positions and the | |
107 | * LS bits shifted off the bottom are lost. | |
108 | */ | |
109 | void __bitmap_shift_right(unsigned long *dst, | |
110 | const unsigned long *src, int shift, int bits) | |
111 | { | |
112 | int k, lim = BITS_TO_LONGS(bits), left = bits % BITS_PER_LONG; | |
113 | int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG; | |
114 | unsigned long mask = (1UL << left) - 1; | |
115 | for (k = 0; off + k < lim; ++k) { | |
116 | unsigned long upper, lower; | |
117 | ||
118 | /* | |
119 | * If shift is not word aligned, take lower rem bits of | |
120 | * word above and make them the top rem bits of result. | |
121 | */ | |
122 | if (!rem || off + k + 1 >= lim) | |
123 | upper = 0; | |
124 | else { | |
125 | upper = src[off + k + 1]; | |
126 | if (off + k + 1 == lim - 1 && left) | |
127 | upper &= mask; | |
128 | } | |
129 | lower = src[off + k]; | |
130 | if (left && off + k == lim - 1) | |
131 | lower &= mask; | |
132 | dst[k] = upper << (BITS_PER_LONG - rem) | lower >> rem; | |
133 | if (left && k == lim - 1) | |
134 | dst[k] &= mask; | |
135 | } | |
136 | if (off) | |
137 | memset(&dst[lim - off], 0, off*sizeof(unsigned long)); | |
138 | } | |
139 | EXPORT_SYMBOL(__bitmap_shift_right); | |
140 | ||
141 | ||
142 | /* | |
143 | * __bitmap_shift_left - logical left shift of the bits in a bitmap | |
144 | * @dst - destination bitmap | |
145 | * @src - source bitmap | |
146 | * @nbits - shift by this many bits | |
147 | * @bits - bitmap size, in bits | |
148 | * | |
149 | * Shifting left (multiplying) means moving bits in the LS -> MS | |
150 | * direction. Zeros are fed into the vacated LS bit positions | |
151 | * and those MS bits shifted off the top are lost. | |
152 | */ | |
153 | ||
154 | void __bitmap_shift_left(unsigned long *dst, | |
155 | const unsigned long *src, int shift, int bits) | |
156 | { | |
157 | int k, lim = BITS_TO_LONGS(bits), left = bits % BITS_PER_LONG; | |
158 | int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG; | |
159 | for (k = lim - off - 1; k >= 0; --k) { | |
160 | unsigned long upper, lower; | |
161 | ||
162 | /* | |
163 | * If shift is not word aligned, take upper rem bits of | |
164 | * word below and make them the bottom rem bits of result. | |
165 | */ | |
166 | if (rem && k > 0) | |
167 | lower = src[k - 1]; | |
168 | else | |
169 | lower = 0; | |
170 | upper = src[k]; | |
171 | if (left && k == lim - 1) | |
172 | upper &= (1UL << left) - 1; | |
173 | dst[k + off] = lower >> (BITS_PER_LONG - rem) | upper << rem; | |
174 | if (left && k + off == lim - 1) | |
175 | dst[k + off] &= (1UL << left) - 1; | |
176 | } | |
177 | if (off) | |
178 | memset(dst, 0, off*sizeof(unsigned long)); | |
179 | } | |
180 | EXPORT_SYMBOL(__bitmap_shift_left); | |
181 | ||
182 | void __bitmap_and(unsigned long *dst, const unsigned long *bitmap1, | |
183 | const unsigned long *bitmap2, int bits) | |
184 | { | |
185 | int k; | |
186 | int nr = BITS_TO_LONGS(bits); | |
187 | ||
188 | for (k = 0; k < nr; k++) | |
189 | dst[k] = bitmap1[k] & bitmap2[k]; | |
190 | } | |
191 | EXPORT_SYMBOL(__bitmap_and); | |
192 | ||
193 | void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1, | |
194 | const unsigned long *bitmap2, int bits) | |
195 | { | |
196 | int k; | |
197 | int nr = BITS_TO_LONGS(bits); | |
198 | ||
199 | for (k = 0; k < nr; k++) | |
200 | dst[k] = bitmap1[k] | bitmap2[k]; | |
201 | } | |
202 | EXPORT_SYMBOL(__bitmap_or); | |
203 | ||
204 | void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1, | |
205 | const unsigned long *bitmap2, int bits) | |
206 | { | |
207 | int k; | |
208 | int nr = BITS_TO_LONGS(bits); | |
209 | ||
210 | for (k = 0; k < nr; k++) | |
211 | dst[k] = bitmap1[k] ^ bitmap2[k]; | |
212 | } | |
213 | EXPORT_SYMBOL(__bitmap_xor); | |
214 | ||
215 | void __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1, | |
216 | const unsigned long *bitmap2, int bits) | |
217 | { | |
218 | int k; | |
219 | int nr = BITS_TO_LONGS(bits); | |
220 | ||
221 | for (k = 0; k < nr; k++) | |
222 | dst[k] = bitmap1[k] & ~bitmap2[k]; | |
223 | } | |
224 | EXPORT_SYMBOL(__bitmap_andnot); | |
225 | ||
226 | int __bitmap_intersects(const unsigned long *bitmap1, | |
227 | const unsigned long *bitmap2, int bits) | |
228 | { | |
229 | int k, lim = bits/BITS_PER_LONG; | |
230 | for (k = 0; k < lim; ++k) | |
231 | if (bitmap1[k] & bitmap2[k]) | |
232 | return 1; | |
233 | ||
234 | if (bits % BITS_PER_LONG) | |
235 | if ((bitmap1[k] & bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits)) | |
236 | return 1; | |
237 | return 0; | |
238 | } | |
239 | EXPORT_SYMBOL(__bitmap_intersects); | |
240 | ||
241 | int __bitmap_subset(const unsigned long *bitmap1, | |
242 | const unsigned long *bitmap2, int bits) | |
243 | { | |
244 | int k, lim = bits/BITS_PER_LONG; | |
245 | for (k = 0; k < lim; ++k) | |
246 | if (bitmap1[k] & ~bitmap2[k]) | |
247 | return 0; | |
248 | ||
249 | if (bits % BITS_PER_LONG) | |
250 | if ((bitmap1[k] & ~bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits)) | |
251 | return 0; | |
252 | return 1; | |
253 | } | |
254 | EXPORT_SYMBOL(__bitmap_subset); | |
255 | ||
256 | #if BITS_PER_LONG == 32 | |
257 | int __bitmap_weight(const unsigned long *bitmap, int bits) | |
258 | { | |
259 | int k, w = 0, lim = bits/BITS_PER_LONG; | |
260 | ||
261 | for (k = 0; k < lim; k++) | |
262 | w += hweight32(bitmap[k]); | |
263 | ||
264 | if (bits % BITS_PER_LONG) | |
265 | w += hweight32(bitmap[k] & BITMAP_LAST_WORD_MASK(bits)); | |
266 | ||
267 | return w; | |
268 | } | |
269 | #else | |
270 | int __bitmap_weight(const unsigned long *bitmap, int bits) | |
271 | { | |
272 | int k, w = 0, lim = bits/BITS_PER_LONG; | |
273 | ||
274 | for (k = 0; k < lim; k++) | |
275 | w += hweight64(bitmap[k]); | |
276 | ||
277 | if (bits % BITS_PER_LONG) | |
278 | w += hweight64(bitmap[k] & BITMAP_LAST_WORD_MASK(bits)); | |
279 | ||
280 | return w; | |
281 | } | |
282 | #endif | |
283 | EXPORT_SYMBOL(__bitmap_weight); | |
284 | ||
285 | /* | |
286 | * Bitmap printing & parsing functions: first version by Bill Irwin, | |
287 | * second version by Paul Jackson, third by Joe Korty. | |
288 | */ | |
289 | ||
290 | #define CHUNKSZ 32 | |
291 | #define nbits_to_hold_value(val) fls(val) | |
1da177e4 LT |
292 | #define unhex(c) (isdigit(c) ? (c - '0') : (toupper(c) - 'A' + 10)) |
293 | #define BASEDEC 10 /* fancier cpuset lists input in decimal */ | |
294 | ||
295 | /** | |
296 | * bitmap_scnprintf - convert bitmap to an ASCII hex string. | |
297 | * @buf: byte buffer into which string is placed | |
298 | * @buflen: reserved size of @buf, in bytes | |
299 | * @maskp: pointer to bitmap to convert | |
300 | * @nmaskbits: size of bitmap, in bits | |
301 | * | |
302 | * Exactly @nmaskbits bits are displayed. Hex digits are grouped into | |
303 | * comma-separated sets of eight digits per set. | |
304 | */ | |
305 | int bitmap_scnprintf(char *buf, unsigned int buflen, | |
306 | const unsigned long *maskp, int nmaskbits) | |
307 | { | |
308 | int i, word, bit, len = 0; | |
309 | unsigned long val; | |
310 | const char *sep = ""; | |
311 | int chunksz; | |
312 | u32 chunkmask; | |
313 | ||
314 | chunksz = nmaskbits & (CHUNKSZ - 1); | |
315 | if (chunksz == 0) | |
316 | chunksz = CHUNKSZ; | |
317 | ||
8c0e33c1 | 318 | i = ALIGN(nmaskbits, CHUNKSZ) - CHUNKSZ; |
1da177e4 LT |
319 | for (; i >= 0; i -= CHUNKSZ) { |
320 | chunkmask = ((1ULL << chunksz) - 1); | |
321 | word = i / BITS_PER_LONG; | |
322 | bit = i % BITS_PER_LONG; | |
323 | val = (maskp[word] >> bit) & chunkmask; | |
324 | len += scnprintf(buf+len, buflen-len, "%s%0*lx", sep, | |
325 | (chunksz+3)/4, val); | |
326 | chunksz = CHUNKSZ; | |
327 | sep = ","; | |
328 | } | |
329 | return len; | |
330 | } | |
331 | EXPORT_SYMBOL(bitmap_scnprintf); | |
332 | ||
333 | /** | |
334 | * bitmap_parse - convert an ASCII hex string into a bitmap. | |
335 | * @buf: pointer to buffer in user space containing string. | |
336 | * @buflen: buffer size in bytes. If string is smaller than this | |
337 | * then it must be terminated with a \0. | |
338 | * @maskp: pointer to bitmap array that will contain result. | |
339 | * @nmaskbits: size of bitmap, in bits. | |
340 | * | |
341 | * Commas group hex digits into chunks. Each chunk defines exactly 32 | |
342 | * bits of the resultant bitmask. No chunk may specify a value larger | |
343 | * than 32 bits (-EOVERFLOW), and if a chunk specifies a smaller value | |
344 | * then leading 0-bits are prepended. -EINVAL is returned for illegal | |
345 | * characters and for grouping errors such as "1,,5", ",44", "," and "". | |
346 | * Leading and trailing whitespace accepted, but not embedded whitespace. | |
347 | */ | |
348 | int bitmap_parse(const char __user *ubuf, unsigned int ubuflen, | |
349 | unsigned long *maskp, int nmaskbits) | |
350 | { | |
351 | int c, old_c, totaldigits, ndigits, nchunks, nbits; | |
352 | u32 chunk; | |
353 | ||
354 | bitmap_zero(maskp, nmaskbits); | |
355 | ||
356 | nchunks = nbits = totaldigits = c = 0; | |
357 | do { | |
358 | chunk = ndigits = 0; | |
359 | ||
360 | /* Get the next chunk of the bitmap */ | |
361 | while (ubuflen) { | |
362 | old_c = c; | |
363 | if (get_user(c, ubuf++)) | |
364 | return -EFAULT; | |
365 | ubuflen--; | |
366 | if (isspace(c)) | |
367 | continue; | |
368 | ||
369 | /* | |
370 | * If the last character was a space and the current | |
371 | * character isn't '\0', we've got embedded whitespace. | |
372 | * This is a no-no, so throw an error. | |
373 | */ | |
374 | if (totaldigits && c && isspace(old_c)) | |
375 | return -EINVAL; | |
376 | ||
377 | /* A '\0' or a ',' signal the end of the chunk */ | |
378 | if (c == '\0' || c == ',') | |
379 | break; | |
380 | ||
381 | if (!isxdigit(c)) | |
382 | return -EINVAL; | |
383 | ||
384 | /* | |
385 | * Make sure there are at least 4 free bits in 'chunk'. | |
386 | * If not, this hexdigit will overflow 'chunk', so | |
387 | * throw an error. | |
388 | */ | |
389 | if (chunk & ~((1UL << (CHUNKSZ - 4)) - 1)) | |
390 | return -EOVERFLOW; | |
391 | ||
392 | chunk = (chunk << 4) | unhex(c); | |
393 | ndigits++; totaldigits++; | |
394 | } | |
395 | if (ndigits == 0) | |
396 | return -EINVAL; | |
397 | if (nchunks == 0 && chunk == 0) | |
398 | continue; | |
399 | ||
400 | __bitmap_shift_left(maskp, maskp, CHUNKSZ, nmaskbits); | |
401 | *maskp |= chunk; | |
402 | nchunks++; | |
403 | nbits += (nchunks == 1) ? nbits_to_hold_value(chunk) : CHUNKSZ; | |
404 | if (nbits > nmaskbits) | |
405 | return -EOVERFLOW; | |
406 | } while (ubuflen && c == ','); | |
407 | ||
408 | return 0; | |
409 | } | |
410 | EXPORT_SYMBOL(bitmap_parse); | |
411 | ||
412 | /* | |
413 | * bscnl_emit(buf, buflen, rbot, rtop, bp) | |
414 | * | |
415 | * Helper routine for bitmap_scnlistprintf(). Write decimal number | |
416 | * or range to buf, suppressing output past buf+buflen, with optional | |
417 | * comma-prefix. Return len of what would be written to buf, if it | |
418 | * all fit. | |
419 | */ | |
420 | static inline int bscnl_emit(char *buf, int buflen, int rbot, int rtop, int len) | |
421 | { | |
422 | if (len > 0) | |
423 | len += scnprintf(buf + len, buflen - len, ","); | |
424 | if (rbot == rtop) | |
425 | len += scnprintf(buf + len, buflen - len, "%d", rbot); | |
426 | else | |
427 | len += scnprintf(buf + len, buflen - len, "%d-%d", rbot, rtop); | |
428 | return len; | |
429 | } | |
430 | ||
431 | /** | |
432 | * bitmap_scnlistprintf - convert bitmap to list format ASCII string | |
433 | * @buf: byte buffer into which string is placed | |
434 | * @buflen: reserved size of @buf, in bytes | |
435 | * @maskp: pointer to bitmap to convert | |
436 | * @nmaskbits: size of bitmap, in bits | |
437 | * | |
438 | * Output format is a comma-separated list of decimal numbers and | |
439 | * ranges. Consecutively set bits are shown as two hyphen-separated | |
440 | * decimal numbers, the smallest and largest bit numbers set in | |
441 | * the range. Output format is compatible with the format | |
442 | * accepted as input by bitmap_parselist(). | |
443 | * | |
444 | * The return value is the number of characters which would be | |
445 | * generated for the given input, excluding the trailing '\0', as | |
446 | * per ISO C99. | |
447 | */ | |
448 | int bitmap_scnlistprintf(char *buf, unsigned int buflen, | |
449 | const unsigned long *maskp, int nmaskbits) | |
450 | { | |
451 | int len = 0; | |
452 | /* current bit is 'cur', most recently seen range is [rbot, rtop] */ | |
453 | int cur, rbot, rtop; | |
454 | ||
455 | rbot = cur = find_first_bit(maskp, nmaskbits); | |
456 | while (cur < nmaskbits) { | |
457 | rtop = cur; | |
458 | cur = find_next_bit(maskp, nmaskbits, cur+1); | |
459 | if (cur >= nmaskbits || cur > rtop + 1) { | |
460 | len = bscnl_emit(buf, buflen, rbot, rtop, len); | |
461 | rbot = cur; | |
462 | } | |
463 | } | |
464 | return len; | |
465 | } | |
466 | EXPORT_SYMBOL(bitmap_scnlistprintf); | |
467 | ||
468 | /** | |
469 | * bitmap_parselist - convert list format ASCII string to bitmap | |
470 | * @buf: read nul-terminated user string from this buffer | |
471 | * @mask: write resulting mask here | |
472 | * @nmaskbits: number of bits in mask to be written | |
473 | * | |
474 | * Input format is a comma-separated list of decimal numbers and | |
475 | * ranges. Consecutively set bits are shown as two hyphen-separated | |
476 | * decimal numbers, the smallest and largest bit numbers set in | |
477 | * the range. | |
478 | * | |
479 | * Returns 0 on success, -errno on invalid input strings: | |
480 | * -EINVAL: second number in range smaller than first | |
481 | * -EINVAL: invalid character in string | |
482 | * -ERANGE: bit number specified too large for mask | |
483 | */ | |
484 | int bitmap_parselist(const char *bp, unsigned long *maskp, int nmaskbits) | |
485 | { | |
486 | unsigned a, b; | |
487 | ||
488 | bitmap_zero(maskp, nmaskbits); | |
489 | do { | |
490 | if (!isdigit(*bp)) | |
491 | return -EINVAL; | |
492 | b = a = simple_strtoul(bp, (char **)&bp, BASEDEC); | |
493 | if (*bp == '-') { | |
494 | bp++; | |
495 | if (!isdigit(*bp)) | |
496 | return -EINVAL; | |
497 | b = simple_strtoul(bp, (char **)&bp, BASEDEC); | |
498 | } | |
499 | if (!(a <= b)) | |
500 | return -EINVAL; | |
501 | if (b >= nmaskbits) | |
502 | return -ERANGE; | |
503 | while (a <= b) { | |
504 | set_bit(a, maskp); | |
505 | a++; | |
506 | } | |
507 | if (*bp == ',') | |
508 | bp++; | |
509 | } while (*bp != '\0' && *bp != '\n'); | |
510 | return 0; | |
511 | } | |
512 | EXPORT_SYMBOL(bitmap_parselist); | |
513 | ||
fb5eeeee PJ |
514 | /* |
515 | * bitmap_pos_to_ord(buf, pos, bits) | |
516 | * @buf: pointer to a bitmap | |
517 | * @pos: a bit position in @buf (0 <= @pos < @bits) | |
518 | * @bits: number of valid bit positions in @buf | |
519 | * | |
520 | * Map the bit at position @pos in @buf (of length @bits) to the | |
521 | * ordinal of which set bit it is. If it is not set or if @pos | |
96b7f341 | 522 | * is not a valid bit position, map to -1. |
fb5eeeee PJ |
523 | * |
524 | * If for example, just bits 4 through 7 are set in @buf, then @pos | |
525 | * values 4 through 7 will get mapped to 0 through 3, respectively, | |
526 | * and other @pos values will get mapped to 0. When @pos value 7 | |
527 | * gets mapped to (returns) @ord value 3 in this example, that means | |
528 | * that bit 7 is the 3rd (starting with 0th) set bit in @buf. | |
529 | * | |
530 | * The bit positions 0 through @bits are valid positions in @buf. | |
531 | */ | |
532 | static int bitmap_pos_to_ord(const unsigned long *buf, int pos, int bits) | |
533 | { | |
96b7f341 | 534 | int i, ord; |
fb5eeeee | 535 | |
96b7f341 PJ |
536 | if (pos < 0 || pos >= bits || !test_bit(pos, buf)) |
537 | return -1; | |
fb5eeeee | 538 | |
96b7f341 PJ |
539 | i = find_first_bit(buf, bits); |
540 | ord = 0; | |
541 | while (i < pos) { | |
542 | i = find_next_bit(buf, bits, i + 1); | |
543 | ord++; | |
fb5eeeee | 544 | } |
96b7f341 PJ |
545 | BUG_ON(i != pos); |
546 | ||
fb5eeeee PJ |
547 | return ord; |
548 | } | |
549 | ||
550 | /** | |
551 | * bitmap_ord_to_pos(buf, ord, bits) | |
552 | * @buf: pointer to bitmap | |
553 | * @ord: ordinal bit position (n-th set bit, n >= 0) | |
554 | * @bits: number of valid bit positions in @buf | |
555 | * | |
556 | * Map the ordinal offset of bit @ord in @buf to its position in @buf. | |
96b7f341 PJ |
557 | * Value of @ord should be in range 0 <= @ord < weight(buf), else |
558 | * results are undefined. | |
fb5eeeee PJ |
559 | * |
560 | * If for example, just bits 4 through 7 are set in @buf, then @ord | |
561 | * values 0 through 3 will get mapped to 4 through 7, respectively, | |
96b7f341 | 562 | * and all other @ord values return undefined values. When @ord value 3 |
fb5eeeee PJ |
563 | * gets mapped to (returns) @pos value 7 in this example, that means |
564 | * that the 3rd set bit (starting with 0th) is at position 7 in @buf. | |
565 | * | |
566 | * The bit positions 0 through @bits are valid positions in @buf. | |
567 | */ | |
568 | static int bitmap_ord_to_pos(const unsigned long *buf, int ord, int bits) | |
569 | { | |
570 | int pos = 0; | |
571 | ||
572 | if (ord >= 0 && ord < bits) { | |
573 | int i; | |
574 | ||
575 | for (i = find_first_bit(buf, bits); | |
576 | i < bits && ord > 0; | |
577 | i = find_next_bit(buf, bits, i + 1)) | |
578 | ord--; | |
579 | if (i < bits && ord == 0) | |
580 | pos = i; | |
581 | } | |
582 | ||
583 | return pos; | |
584 | } | |
585 | ||
586 | /** | |
587 | * bitmap_remap - Apply map defined by a pair of bitmaps to another bitmap | |
fb5eeeee | 588 | * @dst: remapped result |
96b7f341 | 589 | * @src: subset to be remapped |
fb5eeeee PJ |
590 | * @old: defines domain of map |
591 | * @new: defines range of map | |
592 | * @bits: number of bits in each of these bitmaps | |
593 | * | |
594 | * Let @old and @new define a mapping of bit positions, such that | |
595 | * whatever position is held by the n-th set bit in @old is mapped | |
596 | * to the n-th set bit in @new. In the more general case, allowing | |
597 | * for the possibility that the weight 'w' of @new is less than the | |
598 | * weight of @old, map the position of the n-th set bit in @old to | |
599 | * the position of the m-th set bit in @new, where m == n % w. | |
600 | * | |
96b7f341 PJ |
601 | * If either of the @old and @new bitmaps are empty, or if @src and |
602 | * @dst point to the same location, then this routine copies @src | |
603 | * to @dst. | |
fb5eeeee | 604 | * |
96b7f341 PJ |
605 | * The positions of unset bits in @old are mapped to themselves |
606 | * (the identify map). | |
fb5eeeee PJ |
607 | * |
608 | * Apply the above specified mapping to @src, placing the result in | |
609 | * @dst, clearing any bits previously set in @dst. | |
610 | * | |
fb5eeeee PJ |
611 | * For example, lets say that @old has bits 4 through 7 set, and |
612 | * @new has bits 12 through 15 set. This defines the mapping of bit | |
613 | * position 4 to 12, 5 to 13, 6 to 14 and 7 to 15, and of all other | |
96b7f341 PJ |
614 | * bit positions unchanged. So if say @src comes into this routine |
615 | * with bits 1, 5 and 7 set, then @dst should leave with bits 1, | |
616 | * 13 and 15 set. | |
fb5eeeee PJ |
617 | */ |
618 | void bitmap_remap(unsigned long *dst, const unsigned long *src, | |
619 | const unsigned long *old, const unsigned long *new, | |
620 | int bits) | |
621 | { | |
96b7f341 | 622 | int oldbit, w; |
fb5eeeee | 623 | |
fb5eeeee PJ |
624 | if (dst == src) /* following doesn't handle inplace remaps */ |
625 | return; | |
fb5eeeee | 626 | bitmap_zero(dst, bits); |
96b7f341 PJ |
627 | |
628 | w = bitmap_weight(new, bits); | |
629 | for (oldbit = find_first_bit(src, bits); | |
630 | oldbit < bits; | |
631 | oldbit = find_next_bit(src, bits, oldbit + 1)) { | |
632 | int n = bitmap_pos_to_ord(old, oldbit, bits); | |
633 | if (n < 0 || w == 0) | |
634 | set_bit(oldbit, dst); /* identity map */ | |
635 | else | |
636 | set_bit(bitmap_ord_to_pos(new, n % w, bits), dst); | |
fb5eeeee PJ |
637 | } |
638 | } | |
639 | EXPORT_SYMBOL(bitmap_remap); | |
640 | ||
641 | /** | |
642 | * bitmap_bitremap - Apply map defined by a pair of bitmaps to a single bit | |
643 | * @oldbit - bit position to be mapped | |
644 | * @old: defines domain of map | |
645 | * @new: defines range of map | |
646 | * @bits: number of bits in each of these bitmaps | |
647 | * | |
648 | * Let @old and @new define a mapping of bit positions, such that | |
649 | * whatever position is held by the n-th set bit in @old is mapped | |
650 | * to the n-th set bit in @new. In the more general case, allowing | |
651 | * for the possibility that the weight 'w' of @new is less than the | |
652 | * weight of @old, map the position of the n-th set bit in @old to | |
653 | * the position of the m-th set bit in @new, where m == n % w. | |
654 | * | |
96b7f341 PJ |
655 | * The positions of unset bits in @old are mapped to themselves |
656 | * (the identify map). | |
fb5eeeee PJ |
657 | * |
658 | * Apply the above specified mapping to bit position @oldbit, returning | |
659 | * the new bit position. | |
660 | * | |
661 | * For example, lets say that @old has bits 4 through 7 set, and | |
662 | * @new has bits 12 through 15 set. This defines the mapping of bit | |
663 | * position 4 to 12, 5 to 13, 6 to 14 and 7 to 15, and of all other | |
96b7f341 PJ |
664 | * bit positions unchanged. So if say @oldbit is 5, then this routine |
665 | * returns 13. | |
fb5eeeee PJ |
666 | */ |
667 | int bitmap_bitremap(int oldbit, const unsigned long *old, | |
668 | const unsigned long *new, int bits) | |
669 | { | |
96b7f341 PJ |
670 | int w = bitmap_weight(new, bits); |
671 | int n = bitmap_pos_to_ord(old, oldbit, bits); | |
672 | if (n < 0 || w == 0) | |
673 | return oldbit; | |
674 | else | |
675 | return bitmap_ord_to_pos(new, n % w, bits); | |
fb5eeeee PJ |
676 | } |
677 | EXPORT_SYMBOL(bitmap_bitremap); | |
678 | ||
1da177e4 LT |
679 | /** |
680 | * bitmap_find_free_region - find a contiguous aligned mem region | |
681 | * @bitmap: an array of unsigned longs corresponding to the bitmap | |
682 | * @bits: number of bits in the bitmap | |
683 | * @order: region size to find (size is actually 1<<order) | |
684 | * | |
685 | * This is used to allocate a memory region from a bitmap. The idea is | |
686 | * that the region has to be 1<<order sized and 1<<order aligned (this | |
687 | * makes the search algorithm much faster). | |
688 | * | |
689 | * The region is marked as set bits in the bitmap if a free one is | |
690 | * found. | |
691 | * | |
692 | * Returns either beginning of region or negative error | |
693 | */ | |
694 | int bitmap_find_free_region(unsigned long *bitmap, int bits, int order) | |
695 | { | |
696 | unsigned long mask; | |
697 | int pages = 1 << order; | |
698 | int i; | |
699 | ||
700 | if(pages > BITS_PER_LONG) | |
701 | return -EINVAL; | |
702 | ||
703 | /* make a mask of the order */ | |
704 | mask = (1ul << (pages - 1)); | |
705 | mask += mask - 1; | |
706 | ||
707 | /* run up the bitmap pages bits at a time */ | |
708 | for (i = 0; i < bits; i += pages) { | |
709 | int index = i/BITS_PER_LONG; | |
710 | int offset = i - (index * BITS_PER_LONG); | |
711 | if((bitmap[index] & (mask << offset)) == 0) { | |
712 | /* set region in bimap */ | |
713 | bitmap[index] |= (mask << offset); | |
714 | return i; | |
715 | } | |
716 | } | |
717 | return -ENOMEM; | |
718 | } | |
719 | EXPORT_SYMBOL(bitmap_find_free_region); | |
720 | ||
721 | /** | |
722 | * bitmap_release_region - release allocated bitmap region | |
723 | * @bitmap: a pointer to the bitmap | |
724 | * @pos: the beginning of the region | |
725 | * @order: the order of the bits to release (number is 1<<order) | |
726 | * | |
727 | * This is the complement to __bitmap_find_free_region and releases | |
728 | * the found region (by clearing it in the bitmap). | |
729 | */ | |
730 | void bitmap_release_region(unsigned long *bitmap, int pos, int order) | |
731 | { | |
732 | int pages = 1 << order; | |
733 | unsigned long mask = (1ul << (pages - 1)); | |
734 | int index = pos/BITS_PER_LONG; | |
735 | int offset = pos - (index * BITS_PER_LONG); | |
736 | mask += mask - 1; | |
737 | bitmap[index] &= ~(mask << offset); | |
738 | } | |
739 | EXPORT_SYMBOL(bitmap_release_region); | |
740 | ||
741 | int bitmap_allocate_region(unsigned long *bitmap, int pos, int order) | |
742 | { | |
743 | int pages = 1 << order; | |
744 | unsigned long mask = (1ul << (pages - 1)); | |
745 | int index = pos/BITS_PER_LONG; | |
746 | int offset = pos - (index * BITS_PER_LONG); | |
747 | ||
748 | /* We don't do regions of pages > BITS_PER_LONG. The | |
749 | * algorithm would be a simple look for multiple zeros in the | |
750 | * array, but there's no driver today that needs this. If you | |
751 | * trip this BUG(), you get to code it... */ | |
752 | BUG_ON(pages > BITS_PER_LONG); | |
753 | mask += mask - 1; | |
754 | if (bitmap[index] & (mask << offset)) | |
755 | return -EBUSY; | |
756 | bitmap[index] |= (mask << offset); | |
757 | return 0; | |
758 | } | |
759 | EXPORT_SYMBOL(bitmap_allocate_region); |