ia64/linux-2.6.18-xen.hg

view lib/bitmap.c @ 897:329ea0ccb344

balloon: try harder to balloon up under memory pressure.

Currently if the balloon driver is unable to increase the guest's
reservation it assumes the failure was due to reaching its full
allocation, gives up on the ballooning operation and records the limit
it reached as the "hard limit". The driver will not try again until
the target is set again (even to the same value).

However it is possible that ballooning has in fact failed due to
memory pressure in the host and therefore it is desirable to keep
attempting to reach the target in case memory becomes available. The
most likely scenario is that some guests are ballooning down while
others are ballooning up and therefore there is temporary memory
pressure while things stabilise. You would not expect a well behaved
toolstack to ask a domain to balloon to more than its allocation nor
would you expect it to deliberately over-commit memory by setting
balloon targets which exceed the total host memory.

This patch drops the concept of a hard limit and causes the balloon
driver to retry increasing the reservation on a timer in the same
manner as when decreasing the reservation.

Also if we partially succeed in increasing the reservation
(i.e. receive less pages than we asked for) then we may as well keep
those pages rather than returning them to Xen.

Signed-off-by: Ian Campbell <ian.campbell@citrix.com>
author Keir Fraser <keir.fraser@citrix.com>
date Fri Jun 05 14:01:20 2009 +0100 (2009-06-05)
parents 831230e53067
children
line source
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>
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 */
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;
48 if (bits % BITS_PER_LONG)
49 if (bitmap[k] & BITMAP_LAST_WORD_MASK(bits))
50 return 0;
52 return 1;
53 }
54 EXPORT_SYMBOL(__bitmap_empty);
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;
63 if (bits % BITS_PER_LONG)
64 if (~bitmap[k] & BITMAP_LAST_WORD_MASK(bits))
65 return 0;
67 return 1;
68 }
69 EXPORT_SYMBOL(__bitmap_full);
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;
79 if (bits % BITS_PER_LONG)
80 if ((bitmap1[k] ^ bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))
81 return 0;
83 return 1;
84 }
85 EXPORT_SYMBOL(__bitmap_equal);
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];
93 if (bits % BITS_PER_LONG)
94 dst[k] = ~src[k] & BITMAP_LAST_WORD_MASK(bits);
95 }
96 EXPORT_SYMBOL(__bitmap_complement);
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;
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);
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 */
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;
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);
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);
188 for (k = 0; k < nr; k++)
189 dst[k] = bitmap1[k] & bitmap2[k];
190 }
191 EXPORT_SYMBOL(__bitmap_and);
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);
199 for (k = 0; k < nr; k++)
200 dst[k] = bitmap1[k] | bitmap2[k];
201 }
202 EXPORT_SYMBOL(__bitmap_or);
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);
210 for (k = 0; k < nr; k++)
211 dst[k] = bitmap1[k] ^ bitmap2[k];
212 }
213 EXPORT_SYMBOL(__bitmap_xor);
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);
221 for (k = 0; k < nr; k++)
222 dst[k] = bitmap1[k] & ~bitmap2[k];
223 }
224 EXPORT_SYMBOL(__bitmap_andnot);
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;
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);
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;
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);
256 int __bitmap_weight(const unsigned long *bitmap, int bits)
257 {
258 int k, w = 0, lim = bits/BITS_PER_LONG;
260 for (k = 0; k < lim; k++)
261 w += hweight_long(bitmap[k]);
263 if (bits % BITS_PER_LONG)
264 w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits));
266 return w;
267 }
268 EXPORT_SYMBOL(__bitmap_weight);
270 /*
271 * Bitmap printing & parsing functions: first version by Bill Irwin,
272 * second version by Paul Jackson, third by Joe Korty.
273 */
275 #define CHUNKSZ 32
276 #define nbits_to_hold_value(val) fls(val)
277 #define unhex(c) (isdigit(c) ? (c - '0') : (toupper(c) - 'A' + 10))
278 #define BASEDEC 10 /* fancier cpuset lists input in decimal */
280 /**
281 * bitmap_scnprintf - convert bitmap to an ASCII hex string.
282 * @buf: byte buffer into which string is placed
283 * @buflen: reserved size of @buf, in bytes
284 * @maskp: pointer to bitmap to convert
285 * @nmaskbits: size of bitmap, in bits
286 *
287 * Exactly @nmaskbits bits are displayed. Hex digits are grouped into
288 * comma-separated sets of eight digits per set.
289 */
290 int bitmap_scnprintf(char *buf, unsigned int buflen,
291 const unsigned long *maskp, int nmaskbits)
292 {
293 int i, word, bit, len = 0;
294 unsigned long val;
295 const char *sep = "";
296 int chunksz;
297 u32 chunkmask;
299 chunksz = nmaskbits & (CHUNKSZ - 1);
300 if (chunksz == 0)
301 chunksz = CHUNKSZ;
303 i = ALIGN(nmaskbits, CHUNKSZ) - CHUNKSZ;
304 for (; i >= 0; i -= CHUNKSZ) {
305 chunkmask = ((1ULL << chunksz) - 1);
306 word = i / BITS_PER_LONG;
307 bit = i % BITS_PER_LONG;
308 val = (maskp[word] >> bit) & chunkmask;
309 len += scnprintf(buf+len, buflen-len, "%s%0*lx", sep,
310 (chunksz+3)/4, val);
311 chunksz = CHUNKSZ;
312 sep = ",";
313 }
314 return len;
315 }
316 EXPORT_SYMBOL(bitmap_scnprintf);
318 /**
319 * bitmap_parse - convert an ASCII hex string into a bitmap.
320 * @ubuf: pointer to buffer in user space containing string.
321 * @ubuflen: buffer size in bytes. If string is smaller than this
322 * then it must be terminated with a \0.
323 * @maskp: pointer to bitmap array that will contain result.
324 * @nmaskbits: size of bitmap, in bits.
325 *
326 * Commas group hex digits into chunks. Each chunk defines exactly 32
327 * bits of the resultant bitmask. No chunk may specify a value larger
328 * than 32 bits (%-EOVERFLOW), and if a chunk specifies a smaller value
329 * then leading 0-bits are prepended. %-EINVAL is returned for illegal
330 * characters and for grouping errors such as "1,,5", ",44", "," and "".
331 * Leading and trailing whitespace accepted, but not embedded whitespace.
332 */
333 int bitmap_parse(const char __user *ubuf, unsigned int ubuflen,
334 unsigned long *maskp, int nmaskbits)
335 {
336 int c, old_c, totaldigits, ndigits, nchunks, nbits;
337 u32 chunk;
339 bitmap_zero(maskp, nmaskbits);
341 nchunks = nbits = totaldigits = c = 0;
342 do {
343 chunk = ndigits = 0;
345 /* Get the next chunk of the bitmap */
346 while (ubuflen) {
347 old_c = c;
348 if (get_user(c, ubuf++))
349 return -EFAULT;
350 ubuflen--;
351 if (isspace(c))
352 continue;
354 /*
355 * If the last character was a space and the current
356 * character isn't '\0', we've got embedded whitespace.
357 * This is a no-no, so throw an error.
358 */
359 if (totaldigits && c && isspace(old_c))
360 return -EINVAL;
362 /* A '\0' or a ',' signal the end of the chunk */
363 if (c == '\0' || c == ',')
364 break;
366 if (!isxdigit(c))
367 return -EINVAL;
369 /*
370 * Make sure there are at least 4 free bits in 'chunk'.
371 * If not, this hexdigit will overflow 'chunk', so
372 * throw an error.
373 */
374 if (chunk & ~((1UL << (CHUNKSZ - 4)) - 1))
375 return -EOVERFLOW;
377 chunk = (chunk << 4) | unhex(c);
378 ndigits++; totaldigits++;
379 }
380 if (ndigits == 0)
381 return -EINVAL;
382 if (nchunks == 0 && chunk == 0)
383 continue;
385 __bitmap_shift_left(maskp, maskp, CHUNKSZ, nmaskbits);
386 *maskp |= chunk;
387 nchunks++;
388 nbits += (nchunks == 1) ? nbits_to_hold_value(chunk) : CHUNKSZ;
389 if (nbits > nmaskbits)
390 return -EOVERFLOW;
391 } while (ubuflen && c == ',');
393 return 0;
394 }
395 EXPORT_SYMBOL(bitmap_parse);
397 /*
398 * bscnl_emit(buf, buflen, rbot, rtop, bp)
399 *
400 * Helper routine for bitmap_scnlistprintf(). Write decimal number
401 * or range to buf, suppressing output past buf+buflen, with optional
402 * comma-prefix. Return len of what would be written to buf, if it
403 * all fit.
404 */
405 static inline int bscnl_emit(char *buf, int buflen, int rbot, int rtop, int len)
406 {
407 if (len > 0)
408 len += scnprintf(buf + len, buflen - len, ",");
409 if (rbot == rtop)
410 len += scnprintf(buf + len, buflen - len, "%d", rbot);
411 else
412 len += scnprintf(buf + len, buflen - len, "%d-%d", rbot, rtop);
413 return len;
414 }
416 /**
417 * bitmap_scnlistprintf - convert bitmap to list format ASCII string
418 * @buf: byte buffer into which string is placed
419 * @buflen: reserved size of @buf, in bytes
420 * @maskp: pointer to bitmap to convert
421 * @nmaskbits: size of bitmap, in bits
422 *
423 * Output format is a comma-separated list of decimal numbers and
424 * ranges. Consecutively set bits are shown as two hyphen-separated
425 * decimal numbers, the smallest and largest bit numbers set in
426 * the range. Output format is compatible with the format
427 * accepted as input by bitmap_parselist().
428 *
429 * The return value is the number of characters which would be
430 * generated for the given input, excluding the trailing '\0', as
431 * per ISO C99.
432 */
433 int bitmap_scnlistprintf(char *buf, unsigned int buflen,
434 const unsigned long *maskp, int nmaskbits)
435 {
436 int len = 0;
437 /* current bit is 'cur', most recently seen range is [rbot, rtop] */
438 int cur, rbot, rtop;
440 rbot = cur = find_first_bit(maskp, nmaskbits);
441 while (cur < nmaskbits) {
442 rtop = cur;
443 cur = find_next_bit(maskp, nmaskbits, cur+1);
444 if (cur >= nmaskbits || cur > rtop + 1) {
445 len = bscnl_emit(buf, buflen, rbot, rtop, len);
446 rbot = cur;
447 }
448 }
449 return len;
450 }
451 EXPORT_SYMBOL(bitmap_scnlistprintf);
453 /**
454 * bitmap_parselist - convert list format ASCII string to bitmap
455 * @bp: read nul-terminated user string from this buffer
456 * @maskp: write resulting mask here
457 * @nmaskbits: number of bits in mask to be written
458 *
459 * Input format is a comma-separated list of decimal numbers and
460 * ranges. Consecutively set bits are shown as two hyphen-separated
461 * decimal numbers, the smallest and largest bit numbers set in
462 * the range.
463 *
464 * Returns 0 on success, -errno on invalid input strings.
465 * Error values:
466 * %-EINVAL: second number in range smaller than first
467 * %-EINVAL: invalid character in string
468 * %-ERANGE: bit number specified too large for mask
469 */
470 int bitmap_parselist(const char *bp, unsigned long *maskp, int nmaskbits)
471 {
472 unsigned a, b;
474 bitmap_zero(maskp, nmaskbits);
475 do {
476 if (!isdigit(*bp))
477 return -EINVAL;
478 b = a = simple_strtoul(bp, (char **)&bp, BASEDEC);
479 if (*bp == '-') {
480 bp++;
481 if (!isdigit(*bp))
482 return -EINVAL;
483 b = simple_strtoul(bp, (char **)&bp, BASEDEC);
484 }
485 if (!(a <= b))
486 return -EINVAL;
487 if (b >= nmaskbits)
488 return -ERANGE;
489 while (a <= b) {
490 set_bit(a, maskp);
491 a++;
492 }
493 if (*bp == ',')
494 bp++;
495 } while (*bp != '\0' && *bp != '\n');
496 return 0;
497 }
498 EXPORT_SYMBOL(bitmap_parselist);
500 /*
501 * bitmap_pos_to_ord(buf, pos, bits)
502 * @buf: pointer to a bitmap
503 * @pos: a bit position in @buf (0 <= @pos < @bits)
504 * @bits: number of valid bit positions in @buf
505 *
506 * Map the bit at position @pos in @buf (of length @bits) to the
507 * ordinal of which set bit it is. If it is not set or if @pos
508 * is not a valid bit position, map to -1.
509 *
510 * If for example, just bits 4 through 7 are set in @buf, then @pos
511 * values 4 through 7 will get mapped to 0 through 3, respectively,
512 * and other @pos values will get mapped to 0. When @pos value 7
513 * gets mapped to (returns) @ord value 3 in this example, that means
514 * that bit 7 is the 3rd (starting with 0th) set bit in @buf.
515 *
516 * The bit positions 0 through @bits are valid positions in @buf.
517 */
518 static int bitmap_pos_to_ord(const unsigned long *buf, int pos, int bits)
519 {
520 int i, ord;
522 if (pos < 0 || pos >= bits || !test_bit(pos, buf))
523 return -1;
525 i = find_first_bit(buf, bits);
526 ord = 0;
527 while (i < pos) {
528 i = find_next_bit(buf, bits, i + 1);
529 ord++;
530 }
531 BUG_ON(i != pos);
533 return ord;
534 }
536 /**
537 * bitmap_ord_to_pos(buf, ord, bits)
538 * @buf: pointer to bitmap
539 * @ord: ordinal bit position (n-th set bit, n >= 0)
540 * @bits: number of valid bit positions in @buf
541 *
542 * Map the ordinal offset of bit @ord in @buf to its position in @buf.
543 * Value of @ord should be in range 0 <= @ord < weight(buf), else
544 * results are undefined.
545 *
546 * If for example, just bits 4 through 7 are set in @buf, then @ord
547 * values 0 through 3 will get mapped to 4 through 7, respectively,
548 * and all other @ord values return undefined values. When @ord value 3
549 * gets mapped to (returns) @pos value 7 in this example, that means
550 * that the 3rd set bit (starting with 0th) is at position 7 in @buf.
551 *
552 * The bit positions 0 through @bits are valid positions in @buf.
553 */
554 static int bitmap_ord_to_pos(const unsigned long *buf, int ord, int bits)
555 {
556 int pos = 0;
558 if (ord >= 0 && ord < bits) {
559 int i;
561 for (i = find_first_bit(buf, bits);
562 i < bits && ord > 0;
563 i = find_next_bit(buf, bits, i + 1))
564 ord--;
565 if (i < bits && ord == 0)
566 pos = i;
567 }
569 return pos;
570 }
572 /**
573 * bitmap_remap - Apply map defined by a pair of bitmaps to another bitmap
574 * @dst: remapped result
575 * @src: subset to be remapped
576 * @old: defines domain of map
577 * @new: defines range of map
578 * @bits: number of bits in each of these bitmaps
579 *
580 * Let @old and @new define a mapping of bit positions, such that
581 * whatever position is held by the n-th set bit in @old is mapped
582 * to the n-th set bit in @new. In the more general case, allowing
583 * for the possibility that the weight 'w' of @new is less than the
584 * weight of @old, map the position of the n-th set bit in @old to
585 * the position of the m-th set bit in @new, where m == n % w.
586 *
587 * If either of the @old and @new bitmaps are empty, or if @src and
588 * @dst point to the same location, then this routine copies @src
589 * to @dst.
590 *
591 * The positions of unset bits in @old are mapped to themselves
592 * (the identify map).
593 *
594 * Apply the above specified mapping to @src, placing the result in
595 * @dst, clearing any bits previously set in @dst.
596 *
597 * For example, lets say that @old has bits 4 through 7 set, and
598 * @new has bits 12 through 15 set. This defines the mapping of bit
599 * position 4 to 12, 5 to 13, 6 to 14 and 7 to 15, and of all other
600 * bit positions unchanged. So if say @src comes into this routine
601 * with bits 1, 5 and 7 set, then @dst should leave with bits 1,
602 * 13 and 15 set.
603 */
604 void bitmap_remap(unsigned long *dst, const unsigned long *src,
605 const unsigned long *old, const unsigned long *new,
606 int bits)
607 {
608 int oldbit, w;
610 if (dst == src) /* following doesn't handle inplace remaps */
611 return;
612 bitmap_zero(dst, bits);
614 w = bitmap_weight(new, bits);
615 for (oldbit = find_first_bit(src, bits);
616 oldbit < bits;
617 oldbit = find_next_bit(src, bits, oldbit + 1)) {
618 int n = bitmap_pos_to_ord(old, oldbit, bits);
619 if (n < 0 || w == 0)
620 set_bit(oldbit, dst); /* identity map */
621 else
622 set_bit(bitmap_ord_to_pos(new, n % w, bits), dst);
623 }
624 }
625 EXPORT_SYMBOL(bitmap_remap);
627 /**
628 * bitmap_bitremap - Apply map defined by a pair of bitmaps to a single bit
629 * @oldbit: bit position to be mapped
630 * @old: defines domain of map
631 * @new: defines range of map
632 * @bits: number of bits in each of these bitmaps
633 *
634 * Let @old and @new define a mapping of bit positions, such that
635 * whatever position is held by the n-th set bit in @old is mapped
636 * to the n-th set bit in @new. In the more general case, allowing
637 * for the possibility that the weight 'w' of @new is less than the
638 * weight of @old, map the position of the n-th set bit in @old to
639 * the position of the m-th set bit in @new, where m == n % w.
640 *
641 * The positions of unset bits in @old are mapped to themselves
642 * (the identify map).
643 *
644 * Apply the above specified mapping to bit position @oldbit, returning
645 * the new bit position.
646 *
647 * For example, lets say that @old has bits 4 through 7 set, and
648 * @new has bits 12 through 15 set. This defines the mapping of bit
649 * position 4 to 12, 5 to 13, 6 to 14 and 7 to 15, and of all other
650 * bit positions unchanged. So if say @oldbit is 5, then this routine
651 * returns 13.
652 */
653 int bitmap_bitremap(int oldbit, const unsigned long *old,
654 const unsigned long *new, int bits)
655 {
656 int w = bitmap_weight(new, bits);
657 int n = bitmap_pos_to_ord(old, oldbit, bits);
658 if (n < 0 || w == 0)
659 return oldbit;
660 else
661 return bitmap_ord_to_pos(new, n % w, bits);
662 }
663 EXPORT_SYMBOL(bitmap_bitremap);
665 /*
666 * Common code for bitmap_*_region() routines.
667 * bitmap: array of unsigned longs corresponding to the bitmap
668 * pos: the beginning of the region
669 * order: region size (log base 2 of number of bits)
670 * reg_op: operation(s) to perform on that region of bitmap
671 *
672 * Can set, verify and/or release a region of bits in a bitmap,
673 * depending on which combination of REG_OP_* flag bits is set.
674 *
675 * A region of a bitmap is a sequence of bits in the bitmap, of
676 * some size '1 << order' (a power of two), aligned to that same
677 * '1 << order' power of two.
678 *
679 * Returns 1 if REG_OP_ISFREE succeeds (region is all zero bits).
680 * Returns 0 in all other cases and reg_ops.
681 */
683 enum {
684 REG_OP_ISFREE, /* true if region is all zero bits */
685 REG_OP_ALLOC, /* set all bits in region */
686 REG_OP_RELEASE, /* clear all bits in region */
687 };
689 static int __reg_op(unsigned long *bitmap, int pos, int order, int reg_op)
690 {
691 int nbits_reg; /* number of bits in region */
692 int index; /* index first long of region in bitmap */
693 int offset; /* bit offset region in bitmap[index] */
694 int nlongs_reg; /* num longs spanned by region in bitmap */
695 int nbitsinlong; /* num bits of region in each spanned long */
696 unsigned long mask; /* bitmask for one long of region */
697 int i; /* scans bitmap by longs */
698 int ret = 0; /* return value */
700 /*
701 * Either nlongs_reg == 1 (for small orders that fit in one long)
702 * or (offset == 0 && mask == ~0UL) (for larger multiword orders.)
703 */
704 nbits_reg = 1 << order;
705 index = pos / BITS_PER_LONG;
706 offset = pos - (index * BITS_PER_LONG);
707 nlongs_reg = BITS_TO_LONGS(nbits_reg);
708 nbitsinlong = min(nbits_reg, BITS_PER_LONG);
710 /*
711 * Can't do "mask = (1UL << nbitsinlong) - 1", as that
712 * overflows if nbitsinlong == BITS_PER_LONG.
713 */
714 mask = (1UL << (nbitsinlong - 1));
715 mask += mask - 1;
716 mask <<= offset;
718 switch (reg_op) {
719 case REG_OP_ISFREE:
720 for (i = 0; i < nlongs_reg; i++) {
721 if (bitmap[index + i] & mask)
722 goto done;
723 }
724 ret = 1; /* all bits in region free (zero) */
725 break;
727 case REG_OP_ALLOC:
728 for (i = 0; i < nlongs_reg; i++)
729 bitmap[index + i] |= mask;
730 break;
732 case REG_OP_RELEASE:
733 for (i = 0; i < nlongs_reg; i++)
734 bitmap[index + i] &= ~mask;
735 break;
736 }
737 done:
738 return ret;
739 }
741 /**
742 * bitmap_find_free_region - find a contiguous aligned mem region
743 * @bitmap: array of unsigned longs corresponding to the bitmap
744 * @bits: number of bits in the bitmap
745 * @order: region size (log base 2 of number of bits) to find
746 *
747 * Find a region of free (zero) bits in a @bitmap of @bits bits and
748 * allocate them (set them to one). Only consider regions of length
749 * a power (@order) of two, aligned to that power of two, which
750 * makes the search algorithm much faster.
751 *
752 * Return the bit offset in bitmap of the allocated region,
753 * or -errno on failure.
754 */
755 int bitmap_find_free_region(unsigned long *bitmap, int bits, int order)
756 {
757 int pos; /* scans bitmap by regions of size order */
759 for (pos = 0; pos < bits; pos += (1 << order))
760 if (__reg_op(bitmap, pos, order, REG_OP_ISFREE))
761 break;
762 if (pos == bits)
763 return -ENOMEM;
764 __reg_op(bitmap, pos, order, REG_OP_ALLOC);
765 return pos;
766 }
767 EXPORT_SYMBOL(bitmap_find_free_region);
769 /**
770 * bitmap_release_region - release allocated bitmap region
771 * @bitmap: array of unsigned longs corresponding to the bitmap
772 * @pos: beginning of bit region to release
773 * @order: region size (log base 2 of number of bits) to release
774 *
775 * This is the complement to __bitmap_find_free_region and releases
776 * the found region (by clearing it in the bitmap).
777 *
778 * No return value.
779 */
780 void bitmap_release_region(unsigned long *bitmap, int pos, int order)
781 {
782 __reg_op(bitmap, pos, order, REG_OP_RELEASE);
783 }
784 EXPORT_SYMBOL(bitmap_release_region);
786 /**
787 * bitmap_allocate_region - allocate bitmap region
788 * @bitmap: array of unsigned longs corresponding to the bitmap
789 * @pos: beginning of bit region to allocate
790 * @order: region size (log base 2 of number of bits) to allocate
791 *
792 * Allocate (set bits in) a specified region of a bitmap.
793 *
794 * Return 0 on success, or %-EBUSY if specified region wasn't
795 * free (not all bits were zero).
796 */
797 int bitmap_allocate_region(unsigned long *bitmap, int pos, int order)
798 {
799 if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE))
800 return -EBUSY;
801 __reg_op(bitmap, pos, order, REG_OP_ALLOC);
802 return 0;
803 }
804 EXPORT_SYMBOL(bitmap_allocate_region);