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/export.h> 9 #include <linux/thread_info.h> 10 #include <linux/ctype.h> 11 #include <linux/errno.h> 12 #include <linux/bitmap.h> 13 #include <linux/bitops.h> 14 #include <linux/bug.h> 15 #include <linux/kernel.h> 16 #include <linux/string.h> 17 #include <linux/uaccess.h> 18 19 #include <asm/page.h> 20 21 /* 22 * bitmaps provide an array of bits, implemented using an an 23 * array of unsigned longs. The number of valid bits in a 24 * given bitmap does _not_ need to be an exact multiple of 25 * BITS_PER_LONG. 26 * 27 * The possible unused bits in the last, partially used word 28 * of a bitmap are 'don't care'. The implementation makes 29 * no particular effort to keep them zero. It ensures that 30 * their value will not affect the results of any operation. 31 * The bitmap operations that return Boolean (bitmap_empty, 32 * for example) or scalar (bitmap_weight, for example) results 33 * carefully filter out these unused bits from impacting their 34 * results. 35 * 36 * These operations actually hold to a slightly stronger rule: 37 * if you don't input any bitmaps to these ops that have some 38 * unused bits set, then they won't output any set unused bits 39 * in output bitmaps. 40 * 41 * The byte ordering of bitmaps is more natural on little 42 * endian architectures. See the big-endian headers 43 * include/asm-ppc64/bitops.h and include/asm-s390/bitops.h 44 * for the best explanations of this ordering. 45 */ 46 47 int __bitmap_equal(const unsigned long *bitmap1, 48 const unsigned long *bitmap2, unsigned int bits) 49 { 50 unsigned int k, lim = bits/BITS_PER_LONG; 51 for (k = 0; k < lim; ++k) 52 if (bitmap1[k] != bitmap2[k]) 53 return 0; 54 55 if (bits % BITS_PER_LONG) 56 if ((bitmap1[k] ^ bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits)) 57 return 0; 58 59 return 1; 60 } 61 EXPORT_SYMBOL(__bitmap_equal); 62 63 void __bitmap_complement(unsigned long *dst, const unsigned long *src, unsigned int bits) 64 { 65 unsigned int k, lim = bits/BITS_PER_LONG; 66 for (k = 0; k < lim; ++k) 67 dst[k] = ~src[k]; 68 69 if (bits % BITS_PER_LONG) 70 dst[k] = ~src[k]; 71 } 72 EXPORT_SYMBOL(__bitmap_complement); 73 74 /** 75 * __bitmap_shift_right - logical right shift of the bits in a bitmap 76 * @dst : destination bitmap 77 * @src : source bitmap 78 * @shift : shift by this many bits 79 * @nbits : bitmap size, in bits 80 * 81 * Shifting right (dividing) means moving bits in the MS -> LS bit 82 * direction. Zeros are fed into the vacated MS positions and the 83 * LS bits shifted off the bottom are lost. 84 */ 85 void __bitmap_shift_right(unsigned long *dst, const unsigned long *src, 86 unsigned shift, unsigned nbits) 87 { 88 unsigned k, lim = BITS_TO_LONGS(nbits); 89 unsigned off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG; 90 unsigned long mask = BITMAP_LAST_WORD_MASK(nbits); 91 for (k = 0; off + k < lim; ++k) { 92 unsigned long upper, lower; 93 94 /* 95 * If shift is not word aligned, take lower rem bits of 96 * word above and make them the top rem bits of result. 97 */ 98 if (!rem || off + k + 1 >= lim) 99 upper = 0; 100 else { 101 upper = src[off + k + 1]; 102 if (off + k + 1 == lim - 1) 103 upper &= mask; 104 upper <<= (BITS_PER_LONG - rem); 105 } 106 lower = src[off + k]; 107 if (off + k == lim - 1) 108 lower &= mask; 109 lower >>= rem; 110 dst[k] = lower | upper; 111 } 112 if (off) 113 memset(&dst[lim - off], 0, off*sizeof(unsigned long)); 114 } 115 EXPORT_SYMBOL(__bitmap_shift_right); 116 117 118 /** 119 * __bitmap_shift_left - logical left shift of the bits in a bitmap 120 * @dst : destination bitmap 121 * @src : source bitmap 122 * @shift : shift by this many bits 123 * @nbits : bitmap size, in bits 124 * 125 * Shifting left (multiplying) means moving bits in the LS -> MS 126 * direction. Zeros are fed into the vacated LS bit positions 127 * and those MS bits shifted off the top are lost. 128 */ 129 130 void __bitmap_shift_left(unsigned long *dst, const unsigned long *src, 131 unsigned int shift, unsigned int nbits) 132 { 133 int k; 134 unsigned int lim = BITS_TO_LONGS(nbits); 135 unsigned int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG; 136 for (k = lim - off - 1; k >= 0; --k) { 137 unsigned long upper, lower; 138 139 /* 140 * If shift is not word aligned, take upper rem bits of 141 * word below and make them the bottom rem bits of result. 142 */ 143 if (rem && k > 0) 144 lower = src[k - 1] >> (BITS_PER_LONG - rem); 145 else 146 lower = 0; 147 upper = src[k] << rem; 148 dst[k + off] = lower | upper; 149 } 150 if (off) 151 memset(dst, 0, off*sizeof(unsigned long)); 152 } 153 EXPORT_SYMBOL(__bitmap_shift_left); 154 155 int __bitmap_and(unsigned long *dst, const unsigned long *bitmap1, 156 const unsigned long *bitmap2, unsigned int bits) 157 { 158 unsigned int k; 159 unsigned int lim = bits/BITS_PER_LONG; 160 unsigned long result = 0; 161 162 for (k = 0; k < lim; k++) 163 result |= (dst[k] = bitmap1[k] & bitmap2[k]); 164 if (bits % BITS_PER_LONG) 165 result |= (dst[k] = bitmap1[k] & bitmap2[k] & 166 BITMAP_LAST_WORD_MASK(bits)); 167 return result != 0; 168 } 169 EXPORT_SYMBOL(__bitmap_and); 170 171 void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1, 172 const unsigned long *bitmap2, unsigned int bits) 173 { 174 unsigned int k; 175 unsigned int nr = BITS_TO_LONGS(bits); 176 177 for (k = 0; k < nr; k++) 178 dst[k] = bitmap1[k] | bitmap2[k]; 179 } 180 EXPORT_SYMBOL(__bitmap_or); 181 182 void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1, 183 const unsigned long *bitmap2, unsigned int bits) 184 { 185 unsigned int k; 186 unsigned 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_xor); 192 193 int __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1, 194 const unsigned long *bitmap2, unsigned int bits) 195 { 196 unsigned int k; 197 unsigned int lim = bits/BITS_PER_LONG; 198 unsigned long result = 0; 199 200 for (k = 0; k < lim; k++) 201 result |= (dst[k] = bitmap1[k] & ~bitmap2[k]); 202 if (bits % BITS_PER_LONG) 203 result |= (dst[k] = bitmap1[k] & ~bitmap2[k] & 204 BITMAP_LAST_WORD_MASK(bits)); 205 return result != 0; 206 } 207 EXPORT_SYMBOL(__bitmap_andnot); 208 209 int __bitmap_intersects(const unsigned long *bitmap1, 210 const unsigned long *bitmap2, unsigned int bits) 211 { 212 unsigned int k, lim = bits/BITS_PER_LONG; 213 for (k = 0; k < lim; ++k) 214 if (bitmap1[k] & bitmap2[k]) 215 return 1; 216 217 if (bits % BITS_PER_LONG) 218 if ((bitmap1[k] & bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits)) 219 return 1; 220 return 0; 221 } 222 EXPORT_SYMBOL(__bitmap_intersects); 223 224 int __bitmap_subset(const unsigned long *bitmap1, 225 const unsigned long *bitmap2, unsigned int bits) 226 { 227 unsigned int k, lim = bits/BITS_PER_LONG; 228 for (k = 0; k < lim; ++k) 229 if (bitmap1[k] & ~bitmap2[k]) 230 return 0; 231 232 if (bits % BITS_PER_LONG) 233 if ((bitmap1[k] & ~bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits)) 234 return 0; 235 return 1; 236 } 237 EXPORT_SYMBOL(__bitmap_subset); 238 239 int __bitmap_weight(const unsigned long *bitmap, unsigned int bits) 240 { 241 unsigned int k, lim = bits/BITS_PER_LONG; 242 int w = 0; 243 244 for (k = 0; k < lim; k++) 245 w += hweight_long(bitmap[k]); 246 247 if (bits % BITS_PER_LONG) 248 w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits)); 249 250 return w; 251 } 252 EXPORT_SYMBOL(__bitmap_weight); 253 254 void bitmap_set(unsigned long *map, unsigned int start, int len) 255 { 256 unsigned long *p = map + BIT_WORD(start); 257 const unsigned int size = start + len; 258 int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG); 259 unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start); 260 261 while (len - bits_to_set >= 0) { 262 *p |= mask_to_set; 263 len -= bits_to_set; 264 bits_to_set = BITS_PER_LONG; 265 mask_to_set = ~0UL; 266 p++; 267 } 268 if (len) { 269 mask_to_set &= BITMAP_LAST_WORD_MASK(size); 270 *p |= mask_to_set; 271 } 272 } 273 EXPORT_SYMBOL(bitmap_set); 274 275 void bitmap_clear(unsigned long *map, unsigned int start, int len) 276 { 277 unsigned long *p = map + BIT_WORD(start); 278 const unsigned int size = start + len; 279 int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG); 280 unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start); 281 282 while (len - bits_to_clear >= 0) { 283 *p &= ~mask_to_clear; 284 len -= bits_to_clear; 285 bits_to_clear = BITS_PER_LONG; 286 mask_to_clear = ~0UL; 287 p++; 288 } 289 if (len) { 290 mask_to_clear &= BITMAP_LAST_WORD_MASK(size); 291 *p &= ~mask_to_clear; 292 } 293 } 294 EXPORT_SYMBOL(bitmap_clear); 295 296 /** 297 * bitmap_find_next_zero_area_off - find a contiguous aligned zero area 298 * @map: The address to base the search on 299 * @size: The bitmap size in bits 300 * @start: The bitnumber to start searching at 301 * @nr: The number of zeroed bits we're looking for 302 * @align_mask: Alignment mask for zero area 303 * @align_offset: Alignment offset for zero area. 304 * 305 * The @align_mask should be one less than a power of 2; the effect is that 306 * the bit offset of all zero areas this function finds plus @align_offset 307 * is multiple of that power of 2. 308 */ 309 unsigned long bitmap_find_next_zero_area_off(unsigned long *map, 310 unsigned long size, 311 unsigned long start, 312 unsigned int nr, 313 unsigned long align_mask, 314 unsigned long align_offset) 315 { 316 unsigned long index, end, i; 317 again: 318 index = find_next_zero_bit(map, size, start); 319 320 /* Align allocation */ 321 index = __ALIGN_MASK(index + align_offset, align_mask) - align_offset; 322 323 end = index + nr; 324 if (end > size) 325 return end; 326 i = find_next_bit(map, end, index); 327 if (i < end) { 328 start = i + 1; 329 goto again; 330 } 331 return index; 332 } 333 EXPORT_SYMBOL(bitmap_find_next_zero_area_off); 334 335 /* 336 * Bitmap printing & parsing functions: first version by Nadia Yvette Chambers, 337 * second version by Paul Jackson, third by Joe Korty. 338 */ 339 340 #define CHUNKSZ 32 341 #define nbits_to_hold_value(val) fls(val) 342 #define BASEDEC 10 /* fancier cpuset lists input in decimal */ 343 344 /** 345 * __bitmap_parse - convert an ASCII hex string into a bitmap. 346 * @buf: pointer to buffer containing string. 347 * @buflen: buffer size in bytes. If string is smaller than this 348 * then it must be terminated with a \0. 349 * @is_user: location of buffer, 0 indicates kernel space 350 * @maskp: pointer to bitmap array that will contain result. 351 * @nmaskbits: size of bitmap, in bits. 352 * 353 * Commas group hex digits into chunks. Each chunk defines exactly 32 354 * bits of the resultant bitmask. No chunk may specify a value larger 355 * than 32 bits (%-EOVERFLOW), and if a chunk specifies a smaller value 356 * then leading 0-bits are prepended. %-EINVAL is returned for illegal 357 * characters and for grouping errors such as "1,,5", ",44", "," and "". 358 * Leading and trailing whitespace accepted, but not embedded whitespace. 359 */ 360 int __bitmap_parse(const char *buf, unsigned int buflen, 361 int is_user, unsigned long *maskp, 362 int nmaskbits) 363 { 364 int c, old_c, totaldigits, ndigits, nchunks, nbits; 365 u32 chunk; 366 const char __user __force *ubuf = (const char __user __force *)buf; 367 368 bitmap_zero(maskp, nmaskbits); 369 370 nchunks = nbits = totaldigits = c = 0; 371 do { 372 chunk = 0; 373 ndigits = totaldigits; 374 375 /* Get the next chunk of the bitmap */ 376 while (buflen) { 377 old_c = c; 378 if (is_user) { 379 if (__get_user(c, ubuf++)) 380 return -EFAULT; 381 } 382 else 383 c = *buf++; 384 buflen--; 385 if (isspace(c)) 386 continue; 387 388 /* 389 * If the last character was a space and the current 390 * character isn't '\0', we've got embedded whitespace. 391 * This is a no-no, so throw an error. 392 */ 393 if (totaldigits && c && isspace(old_c)) 394 return -EINVAL; 395 396 /* A '\0' or a ',' signal the end of the chunk */ 397 if (c == '\0' || c == ',') 398 break; 399 400 if (!isxdigit(c)) 401 return -EINVAL; 402 403 /* 404 * Make sure there are at least 4 free bits in 'chunk'. 405 * If not, this hexdigit will overflow 'chunk', so 406 * throw an error. 407 */ 408 if (chunk & ~((1UL << (CHUNKSZ - 4)) - 1)) 409 return -EOVERFLOW; 410 411 chunk = (chunk << 4) | hex_to_bin(c); 412 totaldigits++; 413 } 414 if (ndigits == totaldigits) 415 return -EINVAL; 416 if (nchunks == 0 && chunk == 0) 417 continue; 418 419 __bitmap_shift_left(maskp, maskp, CHUNKSZ, nmaskbits); 420 *maskp |= chunk; 421 nchunks++; 422 nbits += (nchunks == 1) ? nbits_to_hold_value(chunk) : CHUNKSZ; 423 if (nbits > nmaskbits) 424 return -EOVERFLOW; 425 } while (buflen && c == ','); 426 427 return 0; 428 } 429 EXPORT_SYMBOL(__bitmap_parse); 430 431 /** 432 * bitmap_parse_user - convert an ASCII hex string in a user buffer into a bitmap 433 * 434 * @ubuf: pointer to user buffer containing string. 435 * @ulen: buffer size in bytes. If string is smaller than this 436 * then it must be terminated with a \0. 437 * @maskp: pointer to bitmap array that will contain result. 438 * @nmaskbits: size of bitmap, in bits. 439 * 440 * Wrapper for __bitmap_parse(), providing it with user buffer. 441 * 442 * We cannot have this as an inline function in bitmap.h because it needs 443 * linux/uaccess.h to get the access_ok() declaration and this causes 444 * cyclic dependencies. 445 */ 446 int bitmap_parse_user(const char __user *ubuf, 447 unsigned int ulen, unsigned long *maskp, 448 int nmaskbits) 449 { 450 if (!access_ok(VERIFY_READ, ubuf, ulen)) 451 return -EFAULT; 452 return __bitmap_parse((const char __force *)ubuf, 453 ulen, 1, maskp, nmaskbits); 454 455 } 456 EXPORT_SYMBOL(bitmap_parse_user); 457 458 /** 459 * bitmap_print_to_pagebuf - convert bitmap to list or hex format ASCII string 460 * @list: indicates whether the bitmap must be list 461 * @buf: page aligned buffer into which string is placed 462 * @maskp: pointer to bitmap to convert 463 * @nmaskbits: size of bitmap, in bits 464 * 465 * Output format is a comma-separated list of decimal numbers and 466 * ranges if list is specified or hex digits grouped into comma-separated 467 * sets of 8 digits/set. Returns the number of characters written to buf. 468 * 469 * It is assumed that @buf is a pointer into a PAGE_SIZE area and that 470 * sufficient storage remains at @buf to accommodate the 471 * bitmap_print_to_pagebuf() output. 472 */ 473 int bitmap_print_to_pagebuf(bool list, char *buf, const unsigned long *maskp, 474 int nmaskbits) 475 { 476 ptrdiff_t len = PTR_ALIGN(buf + PAGE_SIZE - 1, PAGE_SIZE) - buf; 477 int n = 0; 478 479 if (len > 1) 480 n = list ? scnprintf(buf, len, "%*pbl\n", nmaskbits, maskp) : 481 scnprintf(buf, len, "%*pb\n", nmaskbits, maskp); 482 return n; 483 } 484 EXPORT_SYMBOL(bitmap_print_to_pagebuf); 485 486 /** 487 * __bitmap_parselist - convert list format ASCII string to bitmap 488 * @buf: read nul-terminated user string from this buffer 489 * @buflen: buffer size in bytes. If string is smaller than this 490 * then it must be terminated with a \0. 491 * @is_user: location of buffer, 0 indicates kernel space 492 * @maskp: write resulting mask here 493 * @nmaskbits: number of bits in mask to be written 494 * 495 * Input format is a comma-separated list of decimal numbers and 496 * ranges. Consecutively set bits are shown as two hyphen-separated 497 * decimal numbers, the smallest and largest bit numbers set in 498 * the range. 499 * 500 * Returns 0 on success, -errno on invalid input strings. 501 * Error values: 502 * %-EINVAL: second number in range smaller than first 503 * %-EINVAL: invalid character in string 504 * %-ERANGE: bit number specified too large for mask 505 */ 506 static int __bitmap_parselist(const char *buf, unsigned int buflen, 507 int is_user, unsigned long *maskp, 508 int nmaskbits) 509 { 510 unsigned a, b; 511 int c, old_c, totaldigits, ndigits; 512 const char __user __force *ubuf = (const char __user __force *)buf; 513 int at_start, in_range; 514 515 totaldigits = c = 0; 516 bitmap_zero(maskp, nmaskbits); 517 do { 518 at_start = 1; 519 in_range = 0; 520 a = b = 0; 521 ndigits = totaldigits; 522 523 /* Get the next cpu# or a range of cpu#'s */ 524 while (buflen) { 525 old_c = c; 526 if (is_user) { 527 if (__get_user(c, ubuf++)) 528 return -EFAULT; 529 } else 530 c = *buf++; 531 buflen--; 532 if (isspace(c)) 533 continue; 534 535 /* A '\0' or a ',' signal the end of a cpu# or range */ 536 if (c == '\0' || c == ',') 537 break; 538 /* 539 * whitespaces between digits are not allowed, 540 * but it's ok if whitespaces are on head or tail. 541 * when old_c is whilespace, 542 * if totaldigits == ndigits, whitespace is on head. 543 * if whitespace is on tail, it should not run here. 544 * as c was ',' or '\0', 545 * the last code line has broken the current loop. 546 */ 547 if ((totaldigits != ndigits) && isspace(old_c)) 548 return -EINVAL; 549 550 if (c == '-') { 551 if (at_start || in_range) 552 return -EINVAL; 553 b = 0; 554 in_range = 1; 555 at_start = 1; 556 continue; 557 } 558 559 if (!isdigit(c)) 560 return -EINVAL; 561 562 b = b * 10 + (c - '0'); 563 if (!in_range) 564 a = b; 565 at_start = 0; 566 totaldigits++; 567 } 568 if (ndigits == totaldigits) 569 continue; 570 /* if no digit is after '-', it's wrong*/ 571 if (at_start && in_range) 572 return -EINVAL; 573 if (!(a <= b)) 574 return -EINVAL; 575 if (b >= nmaskbits) 576 return -ERANGE; 577 while (a <= b) { 578 set_bit(a, maskp); 579 a++; 580 } 581 } while (buflen && c == ','); 582 return 0; 583 } 584 585 int bitmap_parselist(const char *bp, unsigned long *maskp, int nmaskbits) 586 { 587 char *nl = strchrnul(bp, '\n'); 588 int len = nl - bp; 589 590 return __bitmap_parselist(bp, len, 0, maskp, nmaskbits); 591 } 592 EXPORT_SYMBOL(bitmap_parselist); 593 594 595 /** 596 * bitmap_parselist_user() 597 * 598 * @ubuf: pointer to user buffer containing string. 599 * @ulen: buffer size in bytes. If string is smaller than this 600 * then it must be terminated with a \0. 601 * @maskp: pointer to bitmap array that will contain result. 602 * @nmaskbits: size of bitmap, in bits. 603 * 604 * Wrapper for bitmap_parselist(), providing it with user buffer. 605 * 606 * We cannot have this as an inline function in bitmap.h because it needs 607 * linux/uaccess.h to get the access_ok() declaration and this causes 608 * cyclic dependencies. 609 */ 610 int bitmap_parselist_user(const char __user *ubuf, 611 unsigned int ulen, unsigned long *maskp, 612 int nmaskbits) 613 { 614 if (!access_ok(VERIFY_READ, ubuf, ulen)) 615 return -EFAULT; 616 return __bitmap_parselist((const char __force *)ubuf, 617 ulen, 1, maskp, nmaskbits); 618 } 619 EXPORT_SYMBOL(bitmap_parselist_user); 620 621 622 /** 623 * bitmap_pos_to_ord - find ordinal of set bit at given position in bitmap 624 * @buf: pointer to a bitmap 625 * @pos: a bit position in @buf (0 <= @pos < @nbits) 626 * @nbits: number of valid bit positions in @buf 627 * 628 * Map the bit at position @pos in @buf (of length @nbits) to the 629 * ordinal of which set bit it is. If it is not set or if @pos 630 * is not a valid bit position, map to -1. 631 * 632 * If for example, just bits 4 through 7 are set in @buf, then @pos 633 * values 4 through 7 will get mapped to 0 through 3, respectively, 634 * and other @pos values will get mapped to -1. When @pos value 7 635 * gets mapped to (returns) @ord value 3 in this example, that means 636 * that bit 7 is the 3rd (starting with 0th) set bit in @buf. 637 * 638 * The bit positions 0 through @bits are valid positions in @buf. 639 */ 640 static int bitmap_pos_to_ord(const unsigned long *buf, unsigned int pos, unsigned int nbits) 641 { 642 if (pos >= nbits || !test_bit(pos, buf)) 643 return -1; 644 645 return __bitmap_weight(buf, pos); 646 } 647 648 /** 649 * bitmap_ord_to_pos - find position of n-th set bit in bitmap 650 * @buf: pointer to bitmap 651 * @ord: ordinal bit position (n-th set bit, n >= 0) 652 * @nbits: number of valid bit positions in @buf 653 * 654 * Map the ordinal offset of bit @ord in @buf to its position in @buf. 655 * Value of @ord should be in range 0 <= @ord < weight(buf). If @ord 656 * >= weight(buf), returns @nbits. 657 * 658 * If for example, just bits 4 through 7 are set in @buf, then @ord 659 * values 0 through 3 will get mapped to 4 through 7, respectively, 660 * and all other @ord values returns @nbits. When @ord value 3 661 * gets mapped to (returns) @pos value 7 in this example, that means 662 * that the 3rd set bit (starting with 0th) is at position 7 in @buf. 663 * 664 * The bit positions 0 through @nbits-1 are valid positions in @buf. 665 */ 666 unsigned int bitmap_ord_to_pos(const unsigned long *buf, unsigned int ord, unsigned int nbits) 667 { 668 unsigned int pos; 669 670 for (pos = find_first_bit(buf, nbits); 671 pos < nbits && ord; 672 pos = find_next_bit(buf, nbits, pos + 1)) 673 ord--; 674 675 return pos; 676 } 677 678 /** 679 * bitmap_remap - Apply map defined by a pair of bitmaps to another bitmap 680 * @dst: remapped result 681 * @src: subset to be remapped 682 * @old: defines domain of map 683 * @new: defines range of map 684 * @nbits: number of bits in each of these bitmaps 685 * 686 * Let @old and @new define a mapping of bit positions, such that 687 * whatever position is held by the n-th set bit in @old is mapped 688 * to the n-th set bit in @new. In the more general case, allowing 689 * for the possibility that the weight 'w' of @new is less than the 690 * weight of @old, map the position of the n-th set bit in @old to 691 * the position of the m-th set bit in @new, where m == n % w. 692 * 693 * If either of the @old and @new bitmaps are empty, or if @src and 694 * @dst point to the same location, then this routine copies @src 695 * to @dst. 696 * 697 * The positions of unset bits in @old are mapped to themselves 698 * (the identify map). 699 * 700 * Apply the above specified mapping to @src, placing the result in 701 * @dst, clearing any bits previously set in @dst. 702 * 703 * For example, lets say that @old has bits 4 through 7 set, and 704 * @new has bits 12 through 15 set. This defines the mapping of bit 705 * position 4 to 12, 5 to 13, 6 to 14 and 7 to 15, and of all other 706 * bit positions unchanged. So if say @src comes into this routine 707 * with bits 1, 5 and 7 set, then @dst should leave with bits 1, 708 * 13 and 15 set. 709 */ 710 void bitmap_remap(unsigned long *dst, const unsigned long *src, 711 const unsigned long *old, const unsigned long *new, 712 unsigned int nbits) 713 { 714 unsigned int oldbit, w; 715 716 if (dst == src) /* following doesn't handle inplace remaps */ 717 return; 718 bitmap_zero(dst, nbits); 719 720 w = bitmap_weight(new, nbits); 721 for_each_set_bit(oldbit, src, nbits) { 722 int n = bitmap_pos_to_ord(old, oldbit, nbits); 723 724 if (n < 0 || w == 0) 725 set_bit(oldbit, dst); /* identity map */ 726 else 727 set_bit(bitmap_ord_to_pos(new, n % w, nbits), dst); 728 } 729 } 730 EXPORT_SYMBOL(bitmap_remap); 731 732 /** 733 * bitmap_bitremap - Apply map defined by a pair of bitmaps to a single bit 734 * @oldbit: bit position to be mapped 735 * @old: defines domain of map 736 * @new: defines range of map 737 * @bits: number of bits in each of these bitmaps 738 * 739 * Let @old and @new define a mapping of bit positions, such that 740 * whatever position is held by the n-th set bit in @old is mapped 741 * to the n-th set bit in @new. In the more general case, allowing 742 * for the possibility that the weight 'w' of @new is less than the 743 * weight of @old, map the position of the n-th set bit in @old to 744 * the position of the m-th set bit in @new, where m == n % w. 745 * 746 * The positions of unset bits in @old are mapped to themselves 747 * (the identify map). 748 * 749 * Apply the above specified mapping to bit position @oldbit, returning 750 * the new bit position. 751 * 752 * For example, lets say that @old has bits 4 through 7 set, and 753 * @new has bits 12 through 15 set. This defines the mapping of bit 754 * position 4 to 12, 5 to 13, 6 to 14 and 7 to 15, and of all other 755 * bit positions unchanged. So if say @oldbit is 5, then this routine 756 * returns 13. 757 */ 758 int bitmap_bitremap(int oldbit, const unsigned long *old, 759 const unsigned long *new, int bits) 760 { 761 int w = bitmap_weight(new, bits); 762 int n = bitmap_pos_to_ord(old, oldbit, bits); 763 if (n < 0 || w == 0) 764 return oldbit; 765 else 766 return bitmap_ord_to_pos(new, n % w, bits); 767 } 768 EXPORT_SYMBOL(bitmap_bitremap); 769 770 /** 771 * bitmap_onto - translate one bitmap relative to another 772 * @dst: resulting translated bitmap 773 * @orig: original untranslated bitmap 774 * @relmap: bitmap relative to which translated 775 * @bits: number of bits in each of these bitmaps 776 * 777 * Set the n-th bit of @dst iff there exists some m such that the 778 * n-th bit of @relmap is set, the m-th bit of @orig is set, and 779 * the n-th bit of @relmap is also the m-th _set_ bit of @relmap. 780 * (If you understood the previous sentence the first time your 781 * read it, you're overqualified for your current job.) 782 * 783 * In other words, @orig is mapped onto (surjectively) @dst, 784 * using the map { <n, m> | the n-th bit of @relmap is the 785 * m-th set bit of @relmap }. 786 * 787 * Any set bits in @orig above bit number W, where W is the 788 * weight of (number of set bits in) @relmap are mapped nowhere. 789 * In particular, if for all bits m set in @orig, m >= W, then 790 * @dst will end up empty. In situations where the possibility 791 * of such an empty result is not desired, one way to avoid it is 792 * to use the bitmap_fold() operator, below, to first fold the 793 * @orig bitmap over itself so that all its set bits x are in the 794 * range 0 <= x < W. The bitmap_fold() operator does this by 795 * setting the bit (m % W) in @dst, for each bit (m) set in @orig. 796 * 797 * Example [1] for bitmap_onto(): 798 * Let's say @relmap has bits 30-39 set, and @orig has bits 799 * 1, 3, 5, 7, 9 and 11 set. Then on return from this routine, 800 * @dst will have bits 31, 33, 35, 37 and 39 set. 801 * 802 * When bit 0 is set in @orig, it means turn on the bit in 803 * @dst corresponding to whatever is the first bit (if any) 804 * that is turned on in @relmap. Since bit 0 was off in the 805 * above example, we leave off that bit (bit 30) in @dst. 806 * 807 * When bit 1 is set in @orig (as in the above example), it 808 * means turn on the bit in @dst corresponding to whatever 809 * is the second bit that is turned on in @relmap. The second 810 * bit in @relmap that was turned on in the above example was 811 * bit 31, so we turned on bit 31 in @dst. 812 * 813 * Similarly, we turned on bits 33, 35, 37 and 39 in @dst, 814 * because they were the 4th, 6th, 8th and 10th set bits 815 * set in @relmap, and the 4th, 6th, 8th and 10th bits of 816 * @orig (i.e. bits 3, 5, 7 and 9) were also set. 817 * 818 * When bit 11 is set in @orig, it means turn on the bit in 819 * @dst corresponding to whatever is the twelfth bit that is 820 * turned on in @relmap. In the above example, there were 821 * only ten bits turned on in @relmap (30..39), so that bit 822 * 11 was set in @orig had no affect on @dst. 823 * 824 * Example [2] for bitmap_fold() + bitmap_onto(): 825 * Let's say @relmap has these ten bits set: 826 * 40 41 42 43 45 48 53 61 74 95 827 * (for the curious, that's 40 plus the first ten terms of the 828 * Fibonacci sequence.) 829 * 830 * Further lets say we use the following code, invoking 831 * bitmap_fold() then bitmap_onto, as suggested above to 832 * avoid the possibility of an empty @dst result: 833 * 834 * unsigned long *tmp; // a temporary bitmap's bits 835 * 836 * bitmap_fold(tmp, orig, bitmap_weight(relmap, bits), bits); 837 * bitmap_onto(dst, tmp, relmap, bits); 838 * 839 * Then this table shows what various values of @dst would be, for 840 * various @orig's. I list the zero-based positions of each set bit. 841 * The tmp column shows the intermediate result, as computed by 842 * using bitmap_fold() to fold the @orig bitmap modulo ten 843 * (the weight of @relmap). 844 * 845 * @orig tmp @dst 846 * 0 0 40 847 * 1 1 41 848 * 9 9 95 849 * 10 0 40 (*) 850 * 1 3 5 7 1 3 5 7 41 43 48 61 851 * 0 1 2 3 4 0 1 2 3 4 40 41 42 43 45 852 * 0 9 18 27 0 9 8 7 40 61 74 95 853 * 0 10 20 30 0 40 854 * 0 11 22 33 0 1 2 3 40 41 42 43 855 * 0 12 24 36 0 2 4 6 40 42 45 53 856 * 78 102 211 1 2 8 41 42 74 (*) 857 * 858 * (*) For these marked lines, if we hadn't first done bitmap_fold() 859 * into tmp, then the @dst result would have been empty. 860 * 861 * If either of @orig or @relmap is empty (no set bits), then @dst 862 * will be returned empty. 863 * 864 * If (as explained above) the only set bits in @orig are in positions 865 * m where m >= W, (where W is the weight of @relmap) then @dst will 866 * once again be returned empty. 867 * 868 * All bits in @dst not set by the above rule are cleared. 869 */ 870 void bitmap_onto(unsigned long *dst, const unsigned long *orig, 871 const unsigned long *relmap, unsigned int bits) 872 { 873 unsigned int n, m; /* same meaning as in above comment */ 874 875 if (dst == orig) /* following doesn't handle inplace mappings */ 876 return; 877 bitmap_zero(dst, bits); 878 879 /* 880 * The following code is a more efficient, but less 881 * obvious, equivalent to the loop: 882 * for (m = 0; m < bitmap_weight(relmap, bits); m++) { 883 * n = bitmap_ord_to_pos(orig, m, bits); 884 * if (test_bit(m, orig)) 885 * set_bit(n, dst); 886 * } 887 */ 888 889 m = 0; 890 for_each_set_bit(n, relmap, bits) { 891 /* m == bitmap_pos_to_ord(relmap, n, bits) */ 892 if (test_bit(m, orig)) 893 set_bit(n, dst); 894 m++; 895 } 896 } 897 EXPORT_SYMBOL(bitmap_onto); 898 899 /** 900 * bitmap_fold - fold larger bitmap into smaller, modulo specified size 901 * @dst: resulting smaller bitmap 902 * @orig: original larger bitmap 903 * @sz: specified size 904 * @nbits: number of bits in each of these bitmaps 905 * 906 * For each bit oldbit in @orig, set bit oldbit mod @sz in @dst. 907 * Clear all other bits in @dst. See further the comment and 908 * Example [2] for bitmap_onto() for why and how to use this. 909 */ 910 void bitmap_fold(unsigned long *dst, const unsigned long *orig, 911 unsigned int sz, unsigned int nbits) 912 { 913 unsigned int oldbit; 914 915 if (dst == orig) /* following doesn't handle inplace mappings */ 916 return; 917 bitmap_zero(dst, nbits); 918 919 for_each_set_bit(oldbit, orig, nbits) 920 set_bit(oldbit % sz, dst); 921 } 922 EXPORT_SYMBOL(bitmap_fold); 923 924 /* 925 * Common code for bitmap_*_region() routines. 926 * bitmap: array of unsigned longs corresponding to the bitmap 927 * pos: the beginning of the region 928 * order: region size (log base 2 of number of bits) 929 * reg_op: operation(s) to perform on that region of bitmap 930 * 931 * Can set, verify and/or release a region of bits in a bitmap, 932 * depending on which combination of REG_OP_* flag bits is set. 933 * 934 * A region of a bitmap is a sequence of bits in the bitmap, of 935 * some size '1 << order' (a power of two), aligned to that same 936 * '1 << order' power of two. 937 * 938 * Returns 1 if REG_OP_ISFREE succeeds (region is all zero bits). 939 * Returns 0 in all other cases and reg_ops. 940 */ 941 942 enum { 943 REG_OP_ISFREE, /* true if region is all zero bits */ 944 REG_OP_ALLOC, /* set all bits in region */ 945 REG_OP_RELEASE, /* clear all bits in region */ 946 }; 947 948 static int __reg_op(unsigned long *bitmap, unsigned int pos, int order, int reg_op) 949 { 950 int nbits_reg; /* number of bits in region */ 951 int index; /* index first long of region in bitmap */ 952 int offset; /* bit offset region in bitmap[index] */ 953 int nlongs_reg; /* num longs spanned by region in bitmap */ 954 int nbitsinlong; /* num bits of region in each spanned long */ 955 unsigned long mask; /* bitmask for one long of region */ 956 int i; /* scans bitmap by longs */ 957 int ret = 0; /* return value */ 958 959 /* 960 * Either nlongs_reg == 1 (for small orders that fit in one long) 961 * or (offset == 0 && mask == ~0UL) (for larger multiword orders.) 962 */ 963 nbits_reg = 1 << order; 964 index = pos / BITS_PER_LONG; 965 offset = pos - (index * BITS_PER_LONG); 966 nlongs_reg = BITS_TO_LONGS(nbits_reg); 967 nbitsinlong = min(nbits_reg, BITS_PER_LONG); 968 969 /* 970 * Can't do "mask = (1UL << nbitsinlong) - 1", as that 971 * overflows if nbitsinlong == BITS_PER_LONG. 972 */ 973 mask = (1UL << (nbitsinlong - 1)); 974 mask += mask - 1; 975 mask <<= offset; 976 977 switch (reg_op) { 978 case REG_OP_ISFREE: 979 for (i = 0; i < nlongs_reg; i++) { 980 if (bitmap[index + i] & mask) 981 goto done; 982 } 983 ret = 1; /* all bits in region free (zero) */ 984 break; 985 986 case REG_OP_ALLOC: 987 for (i = 0; i < nlongs_reg; i++) 988 bitmap[index + i] |= mask; 989 break; 990 991 case REG_OP_RELEASE: 992 for (i = 0; i < nlongs_reg; i++) 993 bitmap[index + i] &= ~mask; 994 break; 995 } 996 done: 997 return ret; 998 } 999 1000 /** 1001 * bitmap_find_free_region - find a contiguous aligned mem region 1002 * @bitmap: array of unsigned longs corresponding to the bitmap 1003 * @bits: number of bits in the bitmap 1004 * @order: region size (log base 2 of number of bits) to find 1005 * 1006 * Find a region of free (zero) bits in a @bitmap of @bits bits and 1007 * allocate them (set them to one). Only consider regions of length 1008 * a power (@order) of two, aligned to that power of two, which 1009 * makes the search algorithm much faster. 1010 * 1011 * Return the bit offset in bitmap of the allocated region, 1012 * or -errno on failure. 1013 */ 1014 int bitmap_find_free_region(unsigned long *bitmap, unsigned int bits, int order) 1015 { 1016 unsigned int pos, end; /* scans bitmap by regions of size order */ 1017 1018 for (pos = 0 ; (end = pos + (1U << order)) <= bits; pos = end) { 1019 if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE)) 1020 continue; 1021 __reg_op(bitmap, pos, order, REG_OP_ALLOC); 1022 return pos; 1023 } 1024 return -ENOMEM; 1025 } 1026 EXPORT_SYMBOL(bitmap_find_free_region); 1027 1028 /** 1029 * bitmap_release_region - release allocated bitmap region 1030 * @bitmap: array of unsigned longs corresponding to the bitmap 1031 * @pos: beginning of bit region to release 1032 * @order: region size (log base 2 of number of bits) to release 1033 * 1034 * This is the complement to __bitmap_find_free_region() and releases 1035 * the found region (by clearing it in the bitmap). 1036 * 1037 * No return value. 1038 */ 1039 void bitmap_release_region(unsigned long *bitmap, unsigned int pos, int order) 1040 { 1041 __reg_op(bitmap, pos, order, REG_OP_RELEASE); 1042 } 1043 EXPORT_SYMBOL(bitmap_release_region); 1044 1045 /** 1046 * bitmap_allocate_region - allocate bitmap region 1047 * @bitmap: array of unsigned longs corresponding to the bitmap 1048 * @pos: beginning of bit region to allocate 1049 * @order: region size (log base 2 of number of bits) to allocate 1050 * 1051 * Allocate (set bits in) a specified region of a bitmap. 1052 * 1053 * Return 0 on success, or %-EBUSY if specified region wasn't 1054 * free (not all bits were zero). 1055 */ 1056 int bitmap_allocate_region(unsigned long *bitmap, unsigned int pos, int order) 1057 { 1058 if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE)) 1059 return -EBUSY; 1060 return __reg_op(bitmap, pos, order, REG_OP_ALLOC); 1061 } 1062 EXPORT_SYMBOL(bitmap_allocate_region); 1063 1064 /** 1065 * bitmap_from_u32array - copy the contents of a u32 array of bits to bitmap 1066 * @bitmap: array of unsigned longs, the destination bitmap, non NULL 1067 * @nbits: number of bits in @bitmap 1068 * @buf: array of u32 (in host byte order), the source bitmap, non NULL 1069 * @nwords: number of u32 words in @buf 1070 * 1071 * copy min(nbits, 32*nwords) bits from @buf to @bitmap, remaining 1072 * bits between nword and nbits in @bitmap (if any) are cleared. In 1073 * last word of @bitmap, the bits beyond nbits (if any) are kept 1074 * unchanged. 1075 * 1076 * Return the number of bits effectively copied. 1077 */ 1078 unsigned int 1079 bitmap_from_u32array(unsigned long *bitmap, unsigned int nbits, 1080 const u32 *buf, unsigned int nwords) 1081 { 1082 unsigned int dst_idx, src_idx; 1083 1084 for (src_idx = dst_idx = 0; dst_idx < BITS_TO_LONGS(nbits); ++dst_idx) { 1085 unsigned long part = 0; 1086 1087 if (src_idx < nwords) 1088 part = buf[src_idx++]; 1089 1090 #if BITS_PER_LONG == 64 1091 if (src_idx < nwords) 1092 part |= ((unsigned long) buf[src_idx++]) << 32; 1093 #endif 1094 1095 if (dst_idx < nbits/BITS_PER_LONG) 1096 bitmap[dst_idx] = part; 1097 else { 1098 unsigned long mask = BITMAP_LAST_WORD_MASK(nbits); 1099 1100 bitmap[dst_idx] = (bitmap[dst_idx] & ~mask) 1101 | (part & mask); 1102 } 1103 } 1104 1105 return min_t(unsigned int, nbits, 32*nwords); 1106 } 1107 EXPORT_SYMBOL(bitmap_from_u32array); 1108 1109 /** 1110 * bitmap_to_u32array - copy the contents of bitmap to a u32 array of bits 1111 * @buf: array of u32 (in host byte order), the dest bitmap, non NULL 1112 * @nwords: number of u32 words in @buf 1113 * @bitmap: array of unsigned longs, the source bitmap, non NULL 1114 * @nbits: number of bits in @bitmap 1115 * 1116 * copy min(nbits, 32*nwords) bits from @bitmap to @buf. Remaining 1117 * bits after nbits in @buf (if any) are cleared. 1118 * 1119 * Return the number of bits effectively copied. 1120 */ 1121 unsigned int 1122 bitmap_to_u32array(u32 *buf, unsigned int nwords, 1123 const unsigned long *bitmap, unsigned int nbits) 1124 { 1125 unsigned int dst_idx = 0, src_idx = 0; 1126 1127 while (dst_idx < nwords) { 1128 unsigned long part = 0; 1129 1130 if (src_idx < BITS_TO_LONGS(nbits)) { 1131 part = bitmap[src_idx]; 1132 if (src_idx >= nbits/BITS_PER_LONG) 1133 part &= BITMAP_LAST_WORD_MASK(nbits); 1134 src_idx++; 1135 } 1136 1137 buf[dst_idx++] = part & 0xffffffffUL; 1138 1139 #if BITS_PER_LONG == 64 1140 if (dst_idx < nwords) { 1141 part >>= 32; 1142 buf[dst_idx++] = part & 0xffffffffUL; 1143 } 1144 #endif 1145 } 1146 1147 return min_t(unsigned int, nbits, 32*nwords); 1148 } 1149 EXPORT_SYMBOL(bitmap_to_u32array); 1150 1151 /** 1152 * bitmap_copy_le - copy a bitmap, putting the bits into little-endian order. 1153 * @dst: destination buffer 1154 * @src: bitmap to copy 1155 * @nbits: number of bits in the bitmap 1156 * 1157 * Require nbits % BITS_PER_LONG == 0. 1158 */ 1159 #ifdef __BIG_ENDIAN 1160 void bitmap_copy_le(unsigned long *dst, const unsigned long *src, unsigned int nbits) 1161 { 1162 unsigned int i; 1163 1164 for (i = 0; i < nbits/BITS_PER_LONG; i++) { 1165 if (BITS_PER_LONG == 64) 1166 dst[i] = cpu_to_le64(src[i]); 1167 else 1168 dst[i] = cpu_to_le32(src[i]); 1169 } 1170 } 1171 EXPORT_SYMBOL(bitmap_copy_le); 1172 #endif 1173