Contents of /alx-src/tags/kernel26-2.6.12-alx-r9/lib/bitmap.c
Parent Directory | Revision Log
Revision 630 -
(show annotations)
(download)
Wed Mar 4 11:03:09 2009 UTC (15 years, 6 months ago) by niro
File MIME type: text/plain
File size: 16588 byte(s)
Wed Mar 4 11:03:09 2009 UTC (15 years, 6 months ago) by niro
File MIME type: text/plain
File size: 16588 byte(s)
Tag kernel26-2.6.12-alx-r9
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) |
292 | #define roundup_power2(val,modulus) (((val) + (modulus) - 1) & ~((modulus) - 1)) |
293 | #define unhex(c) (isdigit(c) ? (c - '0') : (toupper(c) - 'A' + 10)) |
294 | #define BASEDEC 10 /* fancier cpuset lists input in decimal */ |
295 | |
296 | /** |
297 | * bitmap_scnprintf - convert bitmap to an ASCII hex string. |
298 | * @buf: byte buffer into which string is placed |
299 | * @buflen: reserved size of @buf, in bytes |
300 | * @maskp: pointer to bitmap to convert |
301 | * @nmaskbits: size of bitmap, in bits |
302 | * |
303 | * Exactly @nmaskbits bits are displayed. Hex digits are grouped into |
304 | * comma-separated sets of eight digits per set. |
305 | */ |
306 | int bitmap_scnprintf(char *buf, unsigned int buflen, |
307 | const unsigned long *maskp, int nmaskbits) |
308 | { |
309 | int i, word, bit, len = 0; |
310 | unsigned long val; |
311 | const char *sep = ""; |
312 | int chunksz; |
313 | u32 chunkmask; |
314 | |
315 | chunksz = nmaskbits & (CHUNKSZ - 1); |
316 | if (chunksz == 0) |
317 | chunksz = CHUNKSZ; |
318 | |
319 | i = roundup_power2(nmaskbits, CHUNKSZ) - CHUNKSZ; |
320 | for (; i >= 0; i -= CHUNKSZ) { |
321 | chunkmask = ((1ULL << chunksz) - 1); |
322 | word = i / BITS_PER_LONG; |
323 | bit = i % BITS_PER_LONG; |
324 | val = (maskp[word] >> bit) & chunkmask; |
325 | len += scnprintf(buf+len, buflen-len, "%s%0*lx", sep, |
326 | (chunksz+3)/4, val); |
327 | chunksz = CHUNKSZ; |
328 | sep = ","; |
329 | } |
330 | return len; |
331 | } |
332 | EXPORT_SYMBOL(bitmap_scnprintf); |
333 | |
334 | /** |
335 | * bitmap_parse - convert an ASCII hex string into a bitmap. |
336 | * @buf: pointer to buffer in user space containing string. |
337 | * @buflen: buffer size in bytes. If string is smaller than this |
338 | * then it must be terminated with a \0. |
339 | * @maskp: pointer to bitmap array that will contain result. |
340 | * @nmaskbits: size of bitmap, in bits. |
341 | * |
342 | * Commas group hex digits into chunks. Each chunk defines exactly 32 |
343 | * bits of the resultant bitmask. No chunk may specify a value larger |
344 | * than 32 bits (-EOVERFLOW), and if a chunk specifies a smaller value |
345 | * then leading 0-bits are prepended. -EINVAL is returned for illegal |
346 | * characters and for grouping errors such as "1,,5", ",44", "," and "". |
347 | * Leading and trailing whitespace accepted, but not embedded whitespace. |
348 | */ |
349 | int bitmap_parse(const char __user *ubuf, unsigned int ubuflen, |
350 | unsigned long *maskp, int nmaskbits) |
351 | { |
352 | int c, old_c, totaldigits, ndigits, nchunks, nbits; |
353 | u32 chunk; |
354 | |
355 | bitmap_zero(maskp, nmaskbits); |
356 | |
357 | nchunks = nbits = totaldigits = c = 0; |
358 | do { |
359 | chunk = ndigits = 0; |
360 | |
361 | /* Get the next chunk of the bitmap */ |
362 | while (ubuflen) { |
363 | old_c = c; |
364 | if (get_user(c, ubuf++)) |
365 | return -EFAULT; |
366 | ubuflen--; |
367 | if (isspace(c)) |
368 | continue; |
369 | |
370 | /* |
371 | * If the last character was a space and the current |
372 | * character isn't '\0', we've got embedded whitespace. |
373 | * This is a no-no, so throw an error. |
374 | */ |
375 | if (totaldigits && c && isspace(old_c)) |
376 | return -EINVAL; |
377 | |
378 | /* A '\0' or a ',' signal the end of the chunk */ |
379 | if (c == '\0' || c == ',') |
380 | break; |
381 | |
382 | if (!isxdigit(c)) |
383 | return -EINVAL; |
384 | |
385 | /* |
386 | * Make sure there are at least 4 free bits in 'chunk'. |
387 | * If not, this hexdigit will overflow 'chunk', so |
388 | * throw an error. |
389 | */ |
390 | if (chunk & ~((1UL << (CHUNKSZ - 4)) - 1)) |
391 | return -EOVERFLOW; |
392 | |
393 | chunk = (chunk << 4) | unhex(c); |
394 | ndigits++; totaldigits++; |
395 | } |
396 | if (ndigits == 0) |
397 | return -EINVAL; |
398 | if (nchunks == 0 && chunk == 0) |
399 | continue; |
400 | |
401 | __bitmap_shift_left(maskp, maskp, CHUNKSZ, nmaskbits); |
402 | *maskp |= chunk; |
403 | nchunks++; |
404 | nbits += (nchunks == 1) ? nbits_to_hold_value(chunk) : CHUNKSZ; |
405 | if (nbits > nmaskbits) |
406 | return -EOVERFLOW; |
407 | } while (ubuflen && c == ','); |
408 | |
409 | return 0; |
410 | } |
411 | EXPORT_SYMBOL(bitmap_parse); |
412 | |
413 | /* |
414 | * bscnl_emit(buf, buflen, rbot, rtop, bp) |
415 | * |
416 | * Helper routine for bitmap_scnlistprintf(). Write decimal number |
417 | * or range to buf, suppressing output past buf+buflen, with optional |
418 | * comma-prefix. Return len of what would be written to buf, if it |
419 | * all fit. |
420 | */ |
421 | static inline int bscnl_emit(char *buf, int buflen, int rbot, int rtop, int len) |
422 | { |
423 | if (len > 0) |
424 | len += scnprintf(buf + len, buflen - len, ","); |
425 | if (rbot == rtop) |
426 | len += scnprintf(buf + len, buflen - len, "%d", rbot); |
427 | else |
428 | len += scnprintf(buf + len, buflen - len, "%d-%d", rbot, rtop); |
429 | return len; |
430 | } |
431 | |
432 | /** |
433 | * bitmap_scnlistprintf - convert bitmap to list format ASCII string |
434 | * @buf: byte buffer into which string is placed |
435 | * @buflen: reserved size of @buf, in bytes |
436 | * @maskp: pointer to bitmap to convert |
437 | * @nmaskbits: size of bitmap, in bits |
438 | * |
439 | * Output format is a comma-separated list of decimal numbers and |
440 | * ranges. Consecutively set bits are shown as two hyphen-separated |
441 | * decimal numbers, the smallest and largest bit numbers set in |
442 | * the range. Output format is compatible with the format |
443 | * accepted as input by bitmap_parselist(). |
444 | * |
445 | * The return value is the number of characters which would be |
446 | * generated for the given input, excluding the trailing '\0', as |
447 | * per ISO C99. |
448 | */ |
449 | int bitmap_scnlistprintf(char *buf, unsigned int buflen, |
450 | const unsigned long *maskp, int nmaskbits) |
451 | { |
452 | int len = 0; |
453 | /* current bit is 'cur', most recently seen range is [rbot, rtop] */ |
454 | int cur, rbot, rtop; |
455 | |
456 | rbot = cur = find_first_bit(maskp, nmaskbits); |
457 | while (cur < nmaskbits) { |
458 | rtop = cur; |
459 | cur = find_next_bit(maskp, nmaskbits, cur+1); |
460 | if (cur >= nmaskbits || cur > rtop + 1) { |
461 | len = bscnl_emit(buf, buflen, rbot, rtop, len); |
462 | rbot = cur; |
463 | } |
464 | } |
465 | return len; |
466 | } |
467 | EXPORT_SYMBOL(bitmap_scnlistprintf); |
468 | |
469 | /** |
470 | * bitmap_parselist - convert list format ASCII string to bitmap |
471 | * @buf: read nul-terminated user string from this buffer |
472 | * @mask: write resulting mask here |
473 | * @nmaskbits: number of bits in mask to be written |
474 | * |
475 | * Input format is a comma-separated list of decimal numbers and |
476 | * ranges. Consecutively set bits are shown as two hyphen-separated |
477 | * decimal numbers, the smallest and largest bit numbers set in |
478 | * the range. |
479 | * |
480 | * Returns 0 on success, -errno on invalid input strings: |
481 | * -EINVAL: second number in range smaller than first |
482 | * -EINVAL: invalid character in string |
483 | * -ERANGE: bit number specified too large for mask |
484 | */ |
485 | int bitmap_parselist(const char *bp, unsigned long *maskp, int nmaskbits) |
486 | { |
487 | unsigned a, b; |
488 | |
489 | bitmap_zero(maskp, nmaskbits); |
490 | do { |
491 | if (!isdigit(*bp)) |
492 | return -EINVAL; |
493 | b = a = simple_strtoul(bp, (char **)&bp, BASEDEC); |
494 | if (*bp == '-') { |
495 | bp++; |
496 | if (!isdigit(*bp)) |
497 | return -EINVAL; |
498 | b = simple_strtoul(bp, (char **)&bp, BASEDEC); |
499 | } |
500 | if (!(a <= b)) |
501 | return -EINVAL; |
502 | if (b >= nmaskbits) |
503 | return -ERANGE; |
504 | while (a <= b) { |
505 | set_bit(a, maskp); |
506 | a++; |
507 | } |
508 | if (*bp == ',') |
509 | bp++; |
510 | } while (*bp != '\0' && *bp != '\n'); |
511 | return 0; |
512 | } |
513 | EXPORT_SYMBOL(bitmap_parselist); |
514 | |
515 | /** |
516 | * bitmap_find_free_region - find a contiguous aligned mem region |
517 | * @bitmap: an array of unsigned longs corresponding to the bitmap |
518 | * @bits: number of bits in the bitmap |
519 | * @order: region size to find (size is actually 1<<order) |
520 | * |
521 | * This is used to allocate a memory region from a bitmap. The idea is |
522 | * that the region has to be 1<<order sized and 1<<order aligned (this |
523 | * makes the search algorithm much faster). |
524 | * |
525 | * The region is marked as set bits in the bitmap if a free one is |
526 | * found. |
527 | * |
528 | * Returns either beginning of region or negative error |
529 | */ |
530 | int bitmap_find_free_region(unsigned long *bitmap, int bits, int order) |
531 | { |
532 | unsigned long mask; |
533 | int pages = 1 << order; |
534 | int i; |
535 | |
536 | if(pages > BITS_PER_LONG) |
537 | return -EINVAL; |
538 | |
539 | /* make a mask of the order */ |
540 | mask = (1ul << (pages - 1)); |
541 | mask += mask - 1; |
542 | |
543 | /* run up the bitmap pages bits at a time */ |
544 | for (i = 0; i < bits; i += pages) { |
545 | int index = i/BITS_PER_LONG; |
546 | int offset = i - (index * BITS_PER_LONG); |
547 | if((bitmap[index] & (mask << offset)) == 0) { |
548 | /* set region in bimap */ |
549 | bitmap[index] |= (mask << offset); |
550 | return i; |
551 | } |
552 | } |
553 | return -ENOMEM; |
554 | } |
555 | EXPORT_SYMBOL(bitmap_find_free_region); |
556 | |
557 | /** |
558 | * bitmap_release_region - release allocated bitmap region |
559 | * @bitmap: a pointer to the bitmap |
560 | * @pos: the beginning of the region |
561 | * @order: the order of the bits to release (number is 1<<order) |
562 | * |
563 | * This is the complement to __bitmap_find_free_region and releases |
564 | * the found region (by clearing it in the bitmap). |
565 | */ |
566 | void bitmap_release_region(unsigned long *bitmap, int pos, int order) |
567 | { |
568 | int pages = 1 << order; |
569 | unsigned long mask = (1ul << (pages - 1)); |
570 | int index = pos/BITS_PER_LONG; |
571 | int offset = pos - (index * BITS_PER_LONG); |
572 | mask += mask - 1; |
573 | bitmap[index] &= ~(mask << offset); |
574 | } |
575 | EXPORT_SYMBOL(bitmap_release_region); |
576 | |
577 | int bitmap_allocate_region(unsigned long *bitmap, int pos, int order) |
578 | { |
579 | int pages = 1 << order; |
580 | unsigned long mask = (1ul << (pages - 1)); |
581 | int index = pos/BITS_PER_LONG; |
582 | int offset = pos - (index * BITS_PER_LONG); |
583 | |
584 | /* We don't do regions of pages > BITS_PER_LONG. The |
585 | * algorithm would be a simple look for multiple zeros in the |
586 | * array, but there's no driver today that needs this. If you |
587 | * trip this BUG(), you get to code it... */ |
588 | BUG_ON(pages > BITS_PER_LONG); |
589 | mask += mask - 1; |
590 | if (bitmap[index] & (mask << offset)) |
591 | return -EBUSY; |
592 | bitmap[index] |= (mask << offset); |
593 | return 0; |
594 | } |
595 | EXPORT_SYMBOL(bitmap_allocate_region); |