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 | ||
514 | /** | |
515 | * bitmap_find_free_region - find a contiguous aligned mem region | |
516 | * @bitmap: an array of unsigned longs corresponding to the bitmap | |
517 | * @bits: number of bits in the bitmap | |
518 | * @order: region size to find (size is actually 1<<order) | |
519 | * | |
520 | * This is used to allocate a memory region from a bitmap. The idea is | |
521 | * that the region has to be 1<<order sized and 1<<order aligned (this | |
522 | * makes the search algorithm much faster). | |
523 | * | |
524 | * The region is marked as set bits in the bitmap if a free one is | |
525 | * found. | |
526 | * | |
527 | * Returns either beginning of region or negative error | |
528 | */ | |
529 | int bitmap_find_free_region(unsigned long *bitmap, int bits, int order) | |
530 | { | |
531 | unsigned long mask; | |
532 | int pages = 1 << order; | |
533 | int i; | |
534 | ||
535 | if(pages > BITS_PER_LONG) | |
536 | return -EINVAL; | |
537 | ||
538 | /* make a mask of the order */ | |
539 | mask = (1ul << (pages - 1)); | |
540 | mask += mask - 1; | |
541 | ||
542 | /* run up the bitmap pages bits at a time */ | |
543 | for (i = 0; i < bits; i += pages) { | |
544 | int index = i/BITS_PER_LONG; | |
545 | int offset = i - (index * BITS_PER_LONG); | |
546 | if((bitmap[index] & (mask << offset)) == 0) { | |
547 | /* set region in bimap */ | |
548 | bitmap[index] |= (mask << offset); | |
549 | return i; | |
550 | } | |
551 | } | |
552 | return -ENOMEM; | |
553 | } | |
554 | EXPORT_SYMBOL(bitmap_find_free_region); | |
555 | ||
556 | /** | |
557 | * bitmap_release_region - release allocated bitmap region | |
558 | * @bitmap: a pointer to the bitmap | |
559 | * @pos: the beginning of the region | |
560 | * @order: the order of the bits to release (number is 1<<order) | |
561 | * | |
562 | * This is the complement to __bitmap_find_free_region and releases | |
563 | * the found region (by clearing it in the bitmap). | |
564 | */ | |
565 | void bitmap_release_region(unsigned long *bitmap, int pos, int order) | |
566 | { | |
567 | int pages = 1 << order; | |
568 | unsigned long mask = (1ul << (pages - 1)); | |
569 | int index = pos/BITS_PER_LONG; | |
570 | int offset = pos - (index * BITS_PER_LONG); | |
571 | mask += mask - 1; | |
572 | bitmap[index] &= ~(mask << offset); | |
573 | } | |
574 | EXPORT_SYMBOL(bitmap_release_region); | |
575 | ||
576 | int bitmap_allocate_region(unsigned long *bitmap, int pos, int order) | |
577 | { | |
578 | int pages = 1 << order; | |
579 | unsigned long mask = (1ul << (pages - 1)); | |
580 | int index = pos/BITS_PER_LONG; | |
581 | int offset = pos - (index * BITS_PER_LONG); | |
582 | ||
583 | /* We don't do regions of pages > BITS_PER_LONG. The | |
584 | * algorithm would be a simple look for multiple zeros in the | |
585 | * array, but there's no driver today that needs this. If you | |
586 | * trip this BUG(), you get to code it... */ | |
587 | BUG_ON(pages > BITS_PER_LONG); | |
588 | mask += mask - 1; | |
589 | if (bitmap[index] & (mask << offset)) | |
590 | return -EBUSY; | |
591 | bitmap[index] |= (mask << offset); | |
592 | return 0; | |
593 | } | |
594 | EXPORT_SYMBOL(bitmap_allocate_region); |