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 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 318 i = ALIGN(nmaskbits, CHUNKSZ) - CHUNKSZ; 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_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 522 * is not a valid bit position, map to zero (0). 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 { 534 int ord = 0; 535 536 if (pos >= 0 && pos < bits) { 537 int i; 538 539 for (i = find_first_bit(buf, bits); 540 i < pos; 541 i = find_next_bit(buf, bits, i + 1)) 542 ord++; 543 if (i > pos) 544 ord = 0; 545 } 546 return ord; 547 } 548 549 /** 550 * bitmap_ord_to_pos(buf, ord, bits) 551 * @buf: pointer to bitmap 552 * @ord: ordinal bit position (n-th set bit, n >= 0) 553 * @bits: number of valid bit positions in @buf 554 * 555 * Map the ordinal offset of bit @ord in @buf to its position in @buf. 556 * If @ord is not the ordinal offset of a set bit in @buf, map to zero (0). 557 * 558 * If for example, just bits 4 through 7 are set in @buf, then @ord 559 * values 0 through 3 will get mapped to 4 through 7, respectively, 560 * and all other @ord valuds will get mapped to 0. When @ord value 3 561 * gets mapped to (returns) @pos value 7 in this example, that means 562 * that the 3rd set bit (starting with 0th) is at position 7 in @buf. 563 * 564 * The bit positions 0 through @bits are valid positions in @buf. 565 */ 566 static int bitmap_ord_to_pos(const unsigned long *buf, int ord, int bits) 567 { 568 int pos = 0; 569 570 if (ord >= 0 && ord < bits) { 571 int i; 572 573 for (i = find_first_bit(buf, bits); 574 i < bits && ord > 0; 575 i = find_next_bit(buf, bits, i + 1)) 576 ord--; 577 if (i < bits && ord == 0) 578 pos = i; 579 } 580 581 return pos; 582 } 583 584 /** 585 * bitmap_remap - Apply map defined by a pair of bitmaps to another bitmap 586 * @src: subset to be remapped 587 * @dst: remapped result 588 * @old: defines domain of map 589 * @new: defines range of map 590 * @bits: number of bits in each of these bitmaps 591 * 592 * Let @old and @new define a mapping of bit positions, such that 593 * whatever position is held by the n-th set bit in @old is mapped 594 * to the n-th set bit in @new. In the more general case, allowing 595 * for the possibility that the weight 'w' of @new is less than the 596 * weight of @old, map the position of the n-th set bit in @old to 597 * the position of the m-th set bit in @new, where m == n % w. 598 * 599 * If either of the @old and @new bitmaps are empty, or if@src and @dst 600 * point to the same location, then this routine does nothing. 601 * 602 * The positions of unset bits in @old are mapped to the position of 603 * the first set bit in @new. 604 * 605 * Apply the above specified mapping to @src, placing the result in 606 * @dst, clearing any bits previously set in @dst. 607 * 608 * The resulting value of @dst will have either the same weight as 609 * @src, or less weight in the general case that the mapping wasn't 610 * injective due to the weight of @new being less than that of @old. 611 * The resulting value of @dst will never have greater weight than 612 * that of @src, except perhaps in the case that one of the above 613 * conditions was not met and this routine just returned. 614 * 615 * For example, lets say that @old has bits 4 through 7 set, and 616 * @new has bits 12 through 15 set. This defines the mapping of bit 617 * position 4 to 12, 5 to 13, 6 to 14 and 7 to 15, and of all other 618 * bit positions to 12 (the first set bit in @new. So if say @src 619 * comes into this routine with bits 1, 5 and 7 set, then @dst should 620 * leave with bits 12, 13 and 15 set. 621 */ 622 void bitmap_remap(unsigned long *dst, const unsigned long *src, 623 const unsigned long *old, const unsigned long *new, 624 int bits) 625 { 626 int s; 627 628 if (bitmap_weight(old, bits) == 0) 629 return; 630 if (bitmap_weight(new, bits) == 0) 631 return; 632 if (dst == src) /* following doesn't handle inplace remaps */ 633 return; 634 635 bitmap_zero(dst, bits); 636 for (s = find_first_bit(src, bits); 637 s < bits; 638 s = find_next_bit(src, bits, s + 1)) { 639 int x = bitmap_pos_to_ord(old, s, bits); 640 int y = bitmap_ord_to_pos(new, x, bits); 641 set_bit(y, dst); 642 } 643 } 644 EXPORT_SYMBOL(bitmap_remap); 645 646 /** 647 * bitmap_bitremap - Apply map defined by a pair of bitmaps to a single bit 648 * @oldbit - bit position to be mapped 649 * @old: defines domain of map 650 * @new: defines range of map 651 * @bits: number of bits in each of these bitmaps 652 * 653 * Let @old and @new define a mapping of bit positions, such that 654 * whatever position is held by the n-th set bit in @old is mapped 655 * to the n-th set bit in @new. In the more general case, allowing 656 * for the possibility that the weight 'w' of @new is less than the 657 * weight of @old, map the position of the n-th set bit in @old to 658 * the position of the m-th set bit in @new, where m == n % w. 659 * 660 * The positions of unset bits in @old are mapped to the position of 661 * the first set bit in @new. 662 * 663 * Apply the above specified mapping to bit position @oldbit, returning 664 * the new bit position. 665 * 666 * For example, lets say that @old has bits 4 through 7 set, and 667 * @new has bits 12 through 15 set. This defines the mapping of bit 668 * position 4 to 12, 5 to 13, 6 to 14 and 7 to 15, and of all other 669 * bit positions to 12 (the first set bit in @new. So if say @oldbit 670 * is 5, then this routine returns 13. 671 */ 672 int bitmap_bitremap(int oldbit, const unsigned long *old, 673 const unsigned long *new, int bits) 674 { 675 int x = bitmap_pos_to_ord(old, oldbit, bits); 676 return bitmap_ord_to_pos(new, x, bits); 677 } 678 EXPORT_SYMBOL(bitmap_bitremap); 679 680 /** 681 * bitmap_find_free_region - find a contiguous aligned mem region 682 * @bitmap: an array of unsigned longs corresponding to the bitmap 683 * @bits: number of bits in the bitmap 684 * @order: region size to find (size is actually 1<<order) 685 * 686 * This is used to allocate a memory region from a bitmap. The idea is 687 * that the region has to be 1<<order sized and 1<<order aligned (this 688 * makes the search algorithm much faster). 689 * 690 * The region is marked as set bits in the bitmap if a free one is 691 * found. 692 * 693 * Returns either beginning of region or negative error 694 */ 695 int bitmap_find_free_region(unsigned long *bitmap, int bits, int order) 696 { 697 unsigned long mask; 698 int pages = 1 << order; 699 int i; 700 701 if(pages > BITS_PER_LONG) 702 return -EINVAL; 703 704 /* make a mask of the order */ 705 mask = (1ul << (pages - 1)); 706 mask += mask - 1; 707 708 /* run up the bitmap pages bits at a time */ 709 for (i = 0; i < bits; i += pages) { 710 int index = i/BITS_PER_LONG; 711 int offset = i - (index * BITS_PER_LONG); 712 if((bitmap[index] & (mask << offset)) == 0) { 713 /* set region in bimap */ 714 bitmap[index] |= (mask << offset); 715 return i; 716 } 717 } 718 return -ENOMEM; 719 } 720 EXPORT_SYMBOL(bitmap_find_free_region); 721 722 /** 723 * bitmap_release_region - release allocated bitmap region 724 * @bitmap: a pointer to the bitmap 725 * @pos: the beginning of the region 726 * @order: the order of the bits to release (number is 1<<order) 727 * 728 * This is the complement to __bitmap_find_free_region and releases 729 * the found region (by clearing it in the bitmap). 730 */ 731 void bitmap_release_region(unsigned long *bitmap, int pos, int order) 732 { 733 int pages = 1 << order; 734 unsigned long mask = (1ul << (pages - 1)); 735 int index = pos/BITS_PER_LONG; 736 int offset = pos - (index * BITS_PER_LONG); 737 mask += mask - 1; 738 bitmap[index] &= ~(mask << offset); 739 } 740 EXPORT_SYMBOL(bitmap_release_region); 741 742 int bitmap_allocate_region(unsigned long *bitmap, int pos, int order) 743 { 744 int pages = 1 << order; 745 unsigned long mask = (1ul << (pages - 1)); 746 int index = pos/BITS_PER_LONG; 747 int offset = pos - (index * BITS_PER_LONG); 748 749 /* We don't do regions of pages > BITS_PER_LONG. The 750 * algorithm would be a simple look for multiple zeros in the 751 * array, but there's no driver today that needs this. If you 752 * trip this BUG(), you get to code it... */ 753 BUG_ON(pages > BITS_PER_LONG); 754 mask += mask - 1; 755 if (bitmap[index] & (mask << offset)) 756 return -EBUSY; 757 bitmap[index] |= (mask << offset); 758 return 0; 759 } 760 EXPORT_SYMBOL(bitmap_allocate_region); 761