1 // SPDX-License-Identifier: GPL-2.0 2 /* 3 * 4 * Copyright (C) 2019-2021 Paragon Software GmbH, All rights reserved. 5 * 6 * This code builds two trees of free clusters extents. 7 * Trees are sorted by start of extent and by length of extent. 8 * NTFS_MAX_WND_EXTENTS defines the maximum number of elements in trees. 9 * In extreme case code reads on-disk bitmap to find free clusters. 10 * 11 */ 12 13 #include <linux/buffer_head.h> 14 #include <linux/fs.h> 15 #include <linux/kernel.h> 16 17 #include "ntfs.h" 18 #include "ntfs_fs.h" 19 20 /* 21 * Maximum number of extents in tree. 22 */ 23 #define NTFS_MAX_WND_EXTENTS (32u * 1024u) 24 25 struct rb_node_key { 26 struct rb_node node; 27 size_t key; 28 }; 29 30 struct e_node { 31 struct rb_node_key start; /* Tree sorted by start. */ 32 struct rb_node_key count; /* Tree sorted by len. */ 33 }; 34 35 static int wnd_rescan(struct wnd_bitmap *wnd); 36 static struct buffer_head *wnd_map(struct wnd_bitmap *wnd, size_t iw); 37 static bool wnd_is_free_hlp(struct wnd_bitmap *wnd, size_t bit, size_t bits); 38 39 static struct kmem_cache *ntfs_enode_cachep; 40 41 int __init ntfs3_init_bitmap(void) 42 { 43 ntfs_enode_cachep = kmem_cache_create("ntfs3_enode_cache", 44 sizeof(struct e_node), 0, 45 SLAB_RECLAIM_ACCOUNT, NULL); 46 return ntfs_enode_cachep ? 0 : -ENOMEM; 47 } 48 49 void ntfs3_exit_bitmap(void) 50 { 51 kmem_cache_destroy(ntfs_enode_cachep); 52 } 53 54 /* 55 * wnd_scan 56 * 57 * b_pos + b_len - biggest fragment. 58 * Scan range [wpos wbits) window @buf. 59 * 60 * Return: -1 if not found. 61 */ 62 static size_t wnd_scan(const void *buf, size_t wbit, u32 wpos, u32 wend, 63 size_t to_alloc, size_t *prev_tail, size_t *b_pos, 64 size_t *b_len) 65 { 66 while (wpos < wend) { 67 size_t free_len; 68 u32 free_bits, end; 69 u32 used = find_next_zero_bit_le(buf, wend, wpos); 70 71 if (used >= wend) { 72 if (*b_len < *prev_tail) { 73 *b_pos = wbit - *prev_tail; 74 *b_len = *prev_tail; 75 } 76 77 *prev_tail = 0; 78 return -1; 79 } 80 81 if (used > wpos) { 82 wpos = used; 83 if (*b_len < *prev_tail) { 84 *b_pos = wbit - *prev_tail; 85 *b_len = *prev_tail; 86 } 87 88 *prev_tail = 0; 89 } 90 91 /* 92 * Now we have a fragment [wpos, wend) staring with 0. 93 */ 94 end = wpos + to_alloc - *prev_tail; 95 free_bits = find_next_bit_le(buf, min(end, wend), wpos); 96 97 free_len = *prev_tail + free_bits - wpos; 98 99 if (*b_len < free_len) { 100 *b_pos = wbit + wpos - *prev_tail; 101 *b_len = free_len; 102 } 103 104 if (free_len >= to_alloc) 105 return wbit + wpos - *prev_tail; 106 107 if (free_bits >= wend) { 108 *prev_tail += free_bits - wpos; 109 return -1; 110 } 111 112 wpos = free_bits + 1; 113 114 *prev_tail = 0; 115 } 116 117 return -1; 118 } 119 120 /* 121 * wnd_close - Frees all resources. 122 */ 123 void wnd_close(struct wnd_bitmap *wnd) 124 { 125 struct rb_node *node, *next; 126 127 kvfree(wnd->free_bits); 128 wnd->free_bits = NULL; 129 run_close(&wnd->run); 130 131 node = rb_first(&wnd->start_tree); 132 133 while (node) { 134 next = rb_next(node); 135 rb_erase(node, &wnd->start_tree); 136 kmem_cache_free(ntfs_enode_cachep, 137 rb_entry(node, struct e_node, start.node)); 138 node = next; 139 } 140 } 141 142 static struct rb_node *rb_lookup(struct rb_root *root, size_t v) 143 { 144 struct rb_node **p = &root->rb_node; 145 struct rb_node *r = NULL; 146 147 while (*p) { 148 struct rb_node_key *k; 149 150 k = rb_entry(*p, struct rb_node_key, node); 151 if (v < k->key) { 152 p = &(*p)->rb_left; 153 } else if (v > k->key) { 154 r = &k->node; 155 p = &(*p)->rb_right; 156 } else { 157 return &k->node; 158 } 159 } 160 161 return r; 162 } 163 164 /* 165 * rb_insert_count - Helper function to insert special kind of 'count' tree. 166 */ 167 static inline bool rb_insert_count(struct rb_root *root, struct e_node *e) 168 { 169 struct rb_node **p = &root->rb_node; 170 struct rb_node *parent = NULL; 171 size_t e_ckey = e->count.key; 172 size_t e_skey = e->start.key; 173 174 while (*p) { 175 struct e_node *k = 176 rb_entry(parent = *p, struct e_node, count.node); 177 178 if (e_ckey > k->count.key) { 179 p = &(*p)->rb_left; 180 } else if (e_ckey < k->count.key) { 181 p = &(*p)->rb_right; 182 } else if (e_skey < k->start.key) { 183 p = &(*p)->rb_left; 184 } else if (e_skey > k->start.key) { 185 p = &(*p)->rb_right; 186 } else { 187 WARN_ON(1); 188 return false; 189 } 190 } 191 192 rb_link_node(&e->count.node, parent, p); 193 rb_insert_color(&e->count.node, root); 194 return true; 195 } 196 197 /* 198 * rb_insert_start - Helper function to insert special kind of 'count' tree. 199 */ 200 static inline bool rb_insert_start(struct rb_root *root, struct e_node *e) 201 { 202 struct rb_node **p = &root->rb_node; 203 struct rb_node *parent = NULL; 204 size_t e_skey = e->start.key; 205 206 while (*p) { 207 struct e_node *k; 208 209 parent = *p; 210 211 k = rb_entry(parent, struct e_node, start.node); 212 if (e_skey < k->start.key) { 213 p = &(*p)->rb_left; 214 } else if (e_skey > k->start.key) { 215 p = &(*p)->rb_right; 216 } else { 217 WARN_ON(1); 218 return false; 219 } 220 } 221 222 rb_link_node(&e->start.node, parent, p); 223 rb_insert_color(&e->start.node, root); 224 return true; 225 } 226 227 /* 228 * wnd_add_free_ext - Adds a new extent of free space. 229 * @build: 1 when building tree. 230 */ 231 static void wnd_add_free_ext(struct wnd_bitmap *wnd, size_t bit, size_t len, 232 bool build) 233 { 234 struct e_node *e, *e0 = NULL; 235 size_t ib, end_in = bit + len; 236 struct rb_node *n; 237 238 if (build) { 239 /* Use extent_min to filter too short extents. */ 240 if (wnd->count >= NTFS_MAX_WND_EXTENTS && 241 len <= wnd->extent_min) { 242 wnd->uptodated = -1; 243 return; 244 } 245 } else { 246 /* Try to find extent before 'bit'. */ 247 n = rb_lookup(&wnd->start_tree, bit); 248 249 if (!n) { 250 n = rb_first(&wnd->start_tree); 251 } else { 252 e = rb_entry(n, struct e_node, start.node); 253 n = rb_next(n); 254 if (e->start.key + e->count.key == bit) { 255 /* Remove left. */ 256 bit = e->start.key; 257 len += e->count.key; 258 rb_erase(&e->start.node, &wnd->start_tree); 259 rb_erase(&e->count.node, &wnd->count_tree); 260 wnd->count -= 1; 261 e0 = e; 262 } 263 } 264 265 while (n) { 266 size_t next_end; 267 268 e = rb_entry(n, struct e_node, start.node); 269 next_end = e->start.key + e->count.key; 270 if (e->start.key > end_in) 271 break; 272 273 /* Remove right. */ 274 n = rb_next(n); 275 len += next_end - end_in; 276 end_in = next_end; 277 rb_erase(&e->start.node, &wnd->start_tree); 278 rb_erase(&e->count.node, &wnd->count_tree); 279 wnd->count -= 1; 280 281 if (!e0) 282 e0 = e; 283 else 284 kmem_cache_free(ntfs_enode_cachep, e); 285 } 286 287 if (wnd->uptodated != 1) { 288 /* Check bits before 'bit'. */ 289 ib = wnd->zone_bit == wnd->zone_end || 290 bit < wnd->zone_end ? 291 0 : 292 wnd->zone_end; 293 294 while (bit > ib && wnd_is_free_hlp(wnd, bit - 1, 1)) { 295 bit -= 1; 296 len += 1; 297 } 298 299 /* Check bits after 'end_in'. */ 300 ib = wnd->zone_bit == wnd->zone_end || 301 end_in > wnd->zone_bit ? 302 wnd->nbits : 303 wnd->zone_bit; 304 305 while (end_in < ib && wnd_is_free_hlp(wnd, end_in, 1)) { 306 end_in += 1; 307 len += 1; 308 } 309 } 310 } 311 /* Insert new fragment. */ 312 if (wnd->count >= NTFS_MAX_WND_EXTENTS) { 313 if (e0) 314 kmem_cache_free(ntfs_enode_cachep, e0); 315 316 wnd->uptodated = -1; 317 318 /* Compare with smallest fragment. */ 319 n = rb_last(&wnd->count_tree); 320 e = rb_entry(n, struct e_node, count.node); 321 if (len <= e->count.key) 322 goto out; /* Do not insert small fragments. */ 323 324 if (build) { 325 struct e_node *e2; 326 327 n = rb_prev(n); 328 e2 = rb_entry(n, struct e_node, count.node); 329 /* Smallest fragment will be 'e2->count.key'. */ 330 wnd->extent_min = e2->count.key; 331 } 332 333 /* Replace smallest fragment by new one. */ 334 rb_erase(&e->start.node, &wnd->start_tree); 335 rb_erase(&e->count.node, &wnd->count_tree); 336 wnd->count -= 1; 337 } else { 338 e = e0 ? e0 : kmem_cache_alloc(ntfs_enode_cachep, GFP_ATOMIC); 339 if (!e) { 340 wnd->uptodated = -1; 341 goto out; 342 } 343 344 if (build && len <= wnd->extent_min) 345 wnd->extent_min = len; 346 } 347 e->start.key = bit; 348 e->count.key = len; 349 if (len > wnd->extent_max) 350 wnd->extent_max = len; 351 352 rb_insert_start(&wnd->start_tree, e); 353 rb_insert_count(&wnd->count_tree, e); 354 wnd->count += 1; 355 356 out:; 357 } 358 359 /* 360 * wnd_remove_free_ext - Remove a run from the cached free space. 361 */ 362 static void wnd_remove_free_ext(struct wnd_bitmap *wnd, size_t bit, size_t len) 363 { 364 struct rb_node *n, *n3; 365 struct e_node *e, *e3; 366 size_t end_in = bit + len; 367 size_t end3, end, new_key, new_len, max_new_len; 368 369 /* Try to find extent before 'bit'. */ 370 n = rb_lookup(&wnd->start_tree, bit); 371 372 if (!n) 373 return; 374 375 e = rb_entry(n, struct e_node, start.node); 376 end = e->start.key + e->count.key; 377 378 new_key = new_len = 0; 379 len = e->count.key; 380 381 /* Range [bit,end_in) must be inside 'e' or outside 'e' and 'n'. */ 382 if (e->start.key > bit) 383 ; 384 else if (end_in <= end) { 385 /* Range [bit,end_in) inside 'e'. */ 386 new_key = end_in; 387 new_len = end - end_in; 388 len = bit - e->start.key; 389 } else if (bit > end) { 390 bool bmax = false; 391 392 n3 = rb_next(n); 393 394 while (n3) { 395 e3 = rb_entry(n3, struct e_node, start.node); 396 if (e3->start.key >= end_in) 397 break; 398 399 if (e3->count.key == wnd->extent_max) 400 bmax = true; 401 402 end3 = e3->start.key + e3->count.key; 403 if (end3 > end_in) { 404 e3->start.key = end_in; 405 rb_erase(&e3->count.node, &wnd->count_tree); 406 e3->count.key = end3 - end_in; 407 rb_insert_count(&wnd->count_tree, e3); 408 break; 409 } 410 411 n3 = rb_next(n3); 412 rb_erase(&e3->start.node, &wnd->start_tree); 413 rb_erase(&e3->count.node, &wnd->count_tree); 414 wnd->count -= 1; 415 kmem_cache_free(ntfs_enode_cachep, e3); 416 } 417 if (!bmax) 418 return; 419 n3 = rb_first(&wnd->count_tree); 420 wnd->extent_max = 421 n3 ? rb_entry(n3, struct e_node, count.node)->count.key : 422 0; 423 return; 424 } 425 426 if (e->count.key != wnd->extent_max) { 427 ; 428 } else if (rb_prev(&e->count.node)) { 429 ; 430 } else { 431 n3 = rb_next(&e->count.node); 432 max_new_len = max(len, new_len); 433 if (!n3) { 434 wnd->extent_max = max_new_len; 435 } else { 436 e3 = rb_entry(n3, struct e_node, count.node); 437 wnd->extent_max = max(e3->count.key, max_new_len); 438 } 439 } 440 441 if (!len) { 442 if (new_len) { 443 e->start.key = new_key; 444 rb_erase(&e->count.node, &wnd->count_tree); 445 e->count.key = new_len; 446 rb_insert_count(&wnd->count_tree, e); 447 } else { 448 rb_erase(&e->start.node, &wnd->start_tree); 449 rb_erase(&e->count.node, &wnd->count_tree); 450 wnd->count -= 1; 451 kmem_cache_free(ntfs_enode_cachep, e); 452 } 453 goto out; 454 } 455 rb_erase(&e->count.node, &wnd->count_tree); 456 e->count.key = len; 457 rb_insert_count(&wnd->count_tree, e); 458 459 if (!new_len) 460 goto out; 461 462 if (wnd->count >= NTFS_MAX_WND_EXTENTS) { 463 wnd->uptodated = -1; 464 465 /* Get minimal extent. */ 466 e = rb_entry(rb_last(&wnd->count_tree), struct e_node, 467 count.node); 468 if (e->count.key > new_len) 469 goto out; 470 471 /* Replace minimum. */ 472 rb_erase(&e->start.node, &wnd->start_tree); 473 rb_erase(&e->count.node, &wnd->count_tree); 474 wnd->count -= 1; 475 } else { 476 e = kmem_cache_alloc(ntfs_enode_cachep, GFP_ATOMIC); 477 if (!e) 478 wnd->uptodated = -1; 479 } 480 481 if (e) { 482 e->start.key = new_key; 483 e->count.key = new_len; 484 rb_insert_start(&wnd->start_tree, e); 485 rb_insert_count(&wnd->count_tree, e); 486 wnd->count += 1; 487 } 488 489 out: 490 if (!wnd->count && 1 != wnd->uptodated) 491 wnd_rescan(wnd); 492 } 493 494 /* 495 * wnd_rescan - Scan all bitmap. Used while initialization. 496 */ 497 static int wnd_rescan(struct wnd_bitmap *wnd) 498 { 499 int err = 0; 500 size_t prev_tail = 0; 501 struct super_block *sb = wnd->sb; 502 struct ntfs_sb_info *sbi = sb->s_fs_info; 503 u64 lbo, len = 0; 504 u32 blocksize = sb->s_blocksize; 505 u8 cluster_bits = sbi->cluster_bits; 506 u32 wbits = 8 * sb->s_blocksize; 507 u32 used, frb; 508 size_t wpos, wbit, iw, vbo; 509 struct buffer_head *bh = NULL; 510 CLST lcn, clen; 511 512 wnd->uptodated = 0; 513 wnd->extent_max = 0; 514 wnd->extent_min = MINUS_ONE_T; 515 wnd->total_zeroes = 0; 516 517 vbo = 0; 518 519 for (iw = 0; iw < wnd->nwnd; iw++) { 520 if (iw + 1 == wnd->nwnd) 521 wbits = wnd->bits_last; 522 523 if (wnd->inited) { 524 if (!wnd->free_bits[iw]) { 525 /* All ones. */ 526 if (prev_tail) { 527 wnd_add_free_ext(wnd, 528 vbo * 8 - prev_tail, 529 prev_tail, true); 530 prev_tail = 0; 531 } 532 goto next_wnd; 533 } 534 if (wbits == wnd->free_bits[iw]) { 535 /* All zeroes. */ 536 prev_tail += wbits; 537 wnd->total_zeroes += wbits; 538 goto next_wnd; 539 } 540 } 541 542 if (!len) { 543 u32 off = vbo & sbi->cluster_mask; 544 545 if (!run_lookup_entry(&wnd->run, vbo >> cluster_bits, 546 &lcn, &clen, NULL)) { 547 err = -ENOENT; 548 goto out; 549 } 550 551 lbo = ((u64)lcn << cluster_bits) + off; 552 len = ((u64)clen << cluster_bits) - off; 553 } 554 555 bh = ntfs_bread(sb, lbo >> sb->s_blocksize_bits); 556 if (!bh) { 557 err = -EIO; 558 goto out; 559 } 560 561 used = ntfs_bitmap_weight_le(bh->b_data, wbits); 562 if (used < wbits) { 563 frb = wbits - used; 564 wnd->free_bits[iw] = frb; 565 wnd->total_zeroes += frb; 566 } 567 568 wpos = 0; 569 wbit = vbo * 8; 570 571 if (wbit + wbits > wnd->nbits) 572 wbits = wnd->nbits - wbit; 573 574 do { 575 used = find_next_zero_bit_le(bh->b_data, wbits, wpos); 576 577 if (used > wpos && prev_tail) { 578 wnd_add_free_ext(wnd, wbit + wpos - prev_tail, 579 prev_tail, true); 580 prev_tail = 0; 581 } 582 583 wpos = used; 584 585 if (wpos >= wbits) { 586 /* No free blocks. */ 587 prev_tail = 0; 588 break; 589 } 590 591 frb = find_next_bit_le(bh->b_data, wbits, wpos); 592 if (frb >= wbits) { 593 /* Keep last free block. */ 594 prev_tail += frb - wpos; 595 break; 596 } 597 598 wnd_add_free_ext(wnd, wbit + wpos - prev_tail, 599 frb + prev_tail - wpos, true); 600 601 /* Skip free block and first '1'. */ 602 wpos = frb + 1; 603 /* Reset previous tail. */ 604 prev_tail = 0; 605 } while (wpos < wbits); 606 607 next_wnd: 608 609 if (bh) 610 put_bh(bh); 611 bh = NULL; 612 613 vbo += blocksize; 614 if (len) { 615 len -= blocksize; 616 lbo += blocksize; 617 } 618 } 619 620 /* Add last block. */ 621 if (prev_tail) 622 wnd_add_free_ext(wnd, wnd->nbits - prev_tail, prev_tail, true); 623 624 /* 625 * Before init cycle wnd->uptodated was 0. 626 * If any errors or limits occurs while initialization then 627 * wnd->uptodated will be -1. 628 * If 'uptodated' is still 0 then Tree is really updated. 629 */ 630 if (!wnd->uptodated) 631 wnd->uptodated = 1; 632 633 if (wnd->zone_bit != wnd->zone_end) { 634 size_t zlen = wnd->zone_end - wnd->zone_bit; 635 636 wnd->zone_end = wnd->zone_bit; 637 wnd_zone_set(wnd, wnd->zone_bit, zlen); 638 } 639 640 out: 641 return err; 642 } 643 644 int wnd_init(struct wnd_bitmap *wnd, struct super_block *sb, size_t nbits) 645 { 646 int err; 647 u32 blocksize = sb->s_blocksize; 648 u32 wbits = blocksize * 8; 649 650 init_rwsem(&wnd->rw_lock); 651 652 wnd->sb = sb; 653 wnd->nbits = nbits; 654 wnd->total_zeroes = nbits; 655 wnd->extent_max = MINUS_ONE_T; 656 wnd->zone_bit = wnd->zone_end = 0; 657 wnd->nwnd = bytes_to_block(sb, ntfs3_bitmap_size(nbits)); 658 wnd->bits_last = nbits & (wbits - 1); 659 if (!wnd->bits_last) 660 wnd->bits_last = wbits; 661 662 wnd->free_bits = 663 kvmalloc_array(wnd->nwnd, sizeof(u16), GFP_KERNEL | __GFP_ZERO); 664 665 if (!wnd->free_bits) 666 return -ENOMEM; 667 668 err = wnd_rescan(wnd); 669 if (err) 670 return err; 671 672 wnd->inited = true; 673 674 return 0; 675 } 676 677 /* 678 * wnd_map - Call sb_bread for requested window. 679 */ 680 static struct buffer_head *wnd_map(struct wnd_bitmap *wnd, size_t iw) 681 { 682 size_t vbo; 683 CLST lcn, clen; 684 struct super_block *sb = wnd->sb; 685 struct ntfs_sb_info *sbi; 686 struct buffer_head *bh; 687 u64 lbo; 688 689 sbi = sb->s_fs_info; 690 vbo = (u64)iw << sb->s_blocksize_bits; 691 692 if (!run_lookup_entry(&wnd->run, vbo >> sbi->cluster_bits, &lcn, &clen, 693 NULL)) { 694 return ERR_PTR(-ENOENT); 695 } 696 697 lbo = ((u64)lcn << sbi->cluster_bits) + (vbo & sbi->cluster_mask); 698 699 bh = ntfs_bread(wnd->sb, lbo >> sb->s_blocksize_bits); 700 if (!bh) 701 return ERR_PTR(-EIO); 702 703 return bh; 704 } 705 706 /* 707 * wnd_set_free - Mark the bits range from bit to bit + bits as free. 708 */ 709 int wnd_set_free(struct wnd_bitmap *wnd, size_t bit, size_t bits) 710 { 711 int err = 0; 712 struct super_block *sb = wnd->sb; 713 u32 wbits = 8 * sb->s_blocksize; 714 size_t iw = bit >> (sb->s_blocksize_bits + 3); 715 u32 wbit = bit & (wbits - 1); 716 struct buffer_head *bh; 717 u32 op; 718 719 for (; iw < wnd->nwnd && bits; iw++, bit += op, bits -= op, wbit = 0) { 720 if (iw + 1 == wnd->nwnd) 721 wbits = wnd->bits_last; 722 723 op = min_t(u32, wbits - wbit, bits); 724 725 bh = wnd_map(wnd, iw); 726 if (IS_ERR(bh)) { 727 err = PTR_ERR(bh); 728 break; 729 } 730 731 lock_buffer(bh); 732 733 ntfs_bitmap_clear_le(bh->b_data, wbit, op); 734 735 wnd->free_bits[iw] += op; 736 wnd->total_zeroes += op; 737 738 set_buffer_uptodate(bh); 739 mark_buffer_dirty(bh); 740 unlock_buffer(bh); 741 put_bh(bh); 742 743 wnd_add_free_ext(wnd, bit, op, false); 744 } 745 return err; 746 } 747 748 /* 749 * wnd_set_used - Mark the bits range from bit to bit + bits as used. 750 */ 751 int wnd_set_used(struct wnd_bitmap *wnd, size_t bit, size_t bits) 752 { 753 int err = 0; 754 struct super_block *sb = wnd->sb; 755 size_t iw = bit >> (sb->s_blocksize_bits + 3); 756 u32 wbits = 8 * sb->s_blocksize; 757 u32 wbit = bit & (wbits - 1); 758 struct buffer_head *bh; 759 u32 op; 760 761 for (; iw < wnd->nwnd && bits; iw++, bit += op, bits -= op, wbit = 0) { 762 if (unlikely(iw + 1 == wnd->nwnd)) 763 wbits = wnd->bits_last; 764 765 op = min_t(u32, wbits - wbit, bits); 766 767 bh = wnd_map(wnd, iw); 768 if (IS_ERR(bh)) { 769 err = PTR_ERR(bh); 770 break; 771 } 772 773 lock_buffer(bh); 774 775 ntfs_bitmap_set_le(bh->b_data, wbit, op); 776 wnd->free_bits[iw] -= op; 777 wnd->total_zeroes -= op; 778 779 set_buffer_uptodate(bh); 780 mark_buffer_dirty(bh); 781 unlock_buffer(bh); 782 put_bh(bh); 783 784 if (!RB_EMPTY_ROOT(&wnd->start_tree)) 785 wnd_remove_free_ext(wnd, bit, op); 786 } 787 return err; 788 } 789 790 /* 791 * wnd_set_used_safe - Mark the bits range from bit to bit + bits as used. 792 * 793 * Unlikely wnd_set_used/wnd_set_free this function is not full trusted. 794 * It scans every bit in bitmap and marks free bit as used. 795 * @done - how many bits were marked as used. 796 * 797 * NOTE: normally *done should be 0. 798 */ 799 int wnd_set_used_safe(struct wnd_bitmap *wnd, size_t bit, size_t bits, 800 size_t *done) 801 { 802 size_t i, from = 0, len = 0; 803 int err = 0; 804 805 *done = 0; 806 for (i = 0; i < bits; i++) { 807 if (wnd_is_free(wnd, bit + i, 1)) { 808 if (!len) 809 from = bit + i; 810 len += 1; 811 } else if (len) { 812 err = wnd_set_used(wnd, from, len); 813 *done += len; 814 len = 0; 815 if (err) 816 break; 817 } 818 } 819 820 if (len) { 821 /* last fragment. */ 822 err = wnd_set_used(wnd, from, len); 823 *done += len; 824 } 825 return err; 826 } 827 828 /* 829 * wnd_is_free_hlp 830 * 831 * Return: True if all clusters [bit, bit+bits) are free (bitmap only). 832 */ 833 static bool wnd_is_free_hlp(struct wnd_bitmap *wnd, size_t bit, size_t bits) 834 { 835 struct super_block *sb = wnd->sb; 836 size_t iw = bit >> (sb->s_blocksize_bits + 3); 837 u32 wbits = 8 * sb->s_blocksize; 838 u32 wbit = bit & (wbits - 1); 839 u32 op; 840 841 for (; iw < wnd->nwnd && bits; iw++, bits -= op, wbit = 0) { 842 if (unlikely(iw + 1 == wnd->nwnd)) 843 wbits = wnd->bits_last; 844 845 op = min_t(u32, wbits - wbit, bits); 846 847 if (wbits != wnd->free_bits[iw]) { 848 bool ret; 849 struct buffer_head *bh = wnd_map(wnd, iw); 850 851 if (IS_ERR(bh)) 852 return false; 853 854 ret = are_bits_clear(bh->b_data, wbit, op); 855 856 put_bh(bh); 857 if (!ret) 858 return false; 859 } 860 } 861 862 return true; 863 } 864 865 /* 866 * wnd_is_free 867 * 868 * Return: True if all clusters [bit, bit+bits) are free. 869 */ 870 bool wnd_is_free(struct wnd_bitmap *wnd, size_t bit, size_t bits) 871 { 872 bool ret; 873 struct rb_node *n; 874 size_t end; 875 struct e_node *e; 876 877 if (RB_EMPTY_ROOT(&wnd->start_tree)) 878 goto use_wnd; 879 880 n = rb_lookup(&wnd->start_tree, bit); 881 if (!n) 882 goto use_wnd; 883 884 e = rb_entry(n, struct e_node, start.node); 885 886 end = e->start.key + e->count.key; 887 888 if (bit < end && bit + bits <= end) 889 return true; 890 891 use_wnd: 892 ret = wnd_is_free_hlp(wnd, bit, bits); 893 894 return ret; 895 } 896 897 /* 898 * wnd_is_used 899 * 900 * Return: True if all clusters [bit, bit+bits) are used. 901 */ 902 bool wnd_is_used(struct wnd_bitmap *wnd, size_t bit, size_t bits) 903 { 904 bool ret = false; 905 struct super_block *sb = wnd->sb; 906 size_t iw = bit >> (sb->s_blocksize_bits + 3); 907 u32 wbits = 8 * sb->s_blocksize; 908 u32 wbit = bit & (wbits - 1); 909 u32 op; 910 size_t end; 911 struct rb_node *n; 912 struct e_node *e; 913 914 if (RB_EMPTY_ROOT(&wnd->start_tree)) 915 goto use_wnd; 916 917 end = bit + bits; 918 n = rb_lookup(&wnd->start_tree, end - 1); 919 if (!n) 920 goto use_wnd; 921 922 e = rb_entry(n, struct e_node, start.node); 923 if (e->start.key + e->count.key > bit) 924 return false; 925 926 use_wnd: 927 for (; iw < wnd->nwnd && bits; iw++, bits -= op, wbit = 0) { 928 if (unlikely(iw + 1 == wnd->nwnd)) 929 wbits = wnd->bits_last; 930 931 op = min_t(u32, wbits - wbit, bits); 932 933 if (wnd->free_bits[iw]) { 934 bool ret; 935 struct buffer_head *bh = wnd_map(wnd, iw); 936 937 if (IS_ERR(bh)) 938 goto out; 939 940 ret = are_bits_set(bh->b_data, wbit, op); 941 put_bh(bh); 942 if (!ret) 943 goto out; 944 } 945 } 946 ret = true; 947 948 out: 949 return ret; 950 } 951 952 /* 953 * wnd_find - Look for free space. 954 * 955 * - flags - BITMAP_FIND_XXX flags 956 * 957 * Return: 0 if not found. 958 */ 959 size_t wnd_find(struct wnd_bitmap *wnd, size_t to_alloc, size_t hint, 960 size_t flags, size_t *allocated) 961 { 962 struct super_block *sb; 963 u32 wbits, wpos, wzbit, wzend; 964 size_t fnd, max_alloc, b_len, b_pos; 965 size_t iw, prev_tail, nwnd, wbit, ebit, zbit, zend; 966 size_t to_alloc0 = to_alloc; 967 const struct e_node *e; 968 const struct rb_node *pr, *cr; 969 u8 log2_bits; 970 bool fbits_valid; 971 struct buffer_head *bh; 972 973 /* Fast checking for available free space. */ 974 if (flags & BITMAP_FIND_FULL) { 975 size_t zeroes = wnd_zeroes(wnd); 976 977 zeroes -= wnd->zone_end - wnd->zone_bit; 978 if (zeroes < to_alloc0) 979 goto no_space; 980 981 if (to_alloc0 > wnd->extent_max) 982 goto no_space; 983 } else { 984 if (to_alloc > wnd->extent_max) 985 to_alloc = wnd->extent_max; 986 } 987 988 if (wnd->zone_bit <= hint && hint < wnd->zone_end) 989 hint = wnd->zone_end; 990 991 max_alloc = wnd->nbits; 992 b_len = b_pos = 0; 993 994 if (hint >= max_alloc) 995 hint = 0; 996 997 if (RB_EMPTY_ROOT(&wnd->start_tree)) { 998 if (wnd->uptodated == 1) { 999 /* Extents tree is updated -> No free space. */ 1000 goto no_space; 1001 } 1002 goto scan_bitmap; 1003 } 1004 1005 e = NULL; 1006 if (!hint) 1007 goto allocate_biggest; 1008 1009 /* Use hint: Enumerate extents by start >= hint. */ 1010 pr = NULL; 1011 cr = wnd->start_tree.rb_node; 1012 1013 for (;;) { 1014 e = rb_entry(cr, struct e_node, start.node); 1015 1016 if (e->start.key == hint) 1017 break; 1018 1019 if (e->start.key < hint) { 1020 pr = cr; 1021 cr = cr->rb_right; 1022 if (!cr) 1023 break; 1024 continue; 1025 } 1026 1027 cr = cr->rb_left; 1028 if (!cr) { 1029 e = pr ? rb_entry(pr, struct e_node, start.node) : NULL; 1030 break; 1031 } 1032 } 1033 1034 if (!e) 1035 goto allocate_biggest; 1036 1037 if (e->start.key + e->count.key > hint) { 1038 /* We have found extension with 'hint' inside. */ 1039 size_t len = e->start.key + e->count.key - hint; 1040 1041 if (len >= to_alloc && hint + to_alloc <= max_alloc) { 1042 fnd = hint; 1043 goto found; 1044 } 1045 1046 if (!(flags & BITMAP_FIND_FULL)) { 1047 if (len > to_alloc) 1048 len = to_alloc; 1049 1050 if (hint + len <= max_alloc) { 1051 fnd = hint; 1052 to_alloc = len; 1053 goto found; 1054 } 1055 } 1056 } 1057 1058 allocate_biggest: 1059 /* Allocate from biggest free extent. */ 1060 e = rb_entry(rb_first(&wnd->count_tree), struct e_node, count.node); 1061 if (e->count.key != wnd->extent_max) 1062 wnd->extent_max = e->count.key; 1063 1064 if (e->count.key < max_alloc) { 1065 if (e->count.key >= to_alloc) { 1066 ; 1067 } else if (flags & BITMAP_FIND_FULL) { 1068 if (e->count.key < to_alloc0) { 1069 /* Biggest free block is less then requested. */ 1070 goto no_space; 1071 } 1072 to_alloc = e->count.key; 1073 } else if (-1 != wnd->uptodated) { 1074 to_alloc = e->count.key; 1075 } else { 1076 /* Check if we can use more bits. */ 1077 size_t op, max_check; 1078 struct rb_root start_tree; 1079 1080 memcpy(&start_tree, &wnd->start_tree, 1081 sizeof(struct rb_root)); 1082 memset(&wnd->start_tree, 0, sizeof(struct rb_root)); 1083 1084 max_check = e->start.key + to_alloc; 1085 if (max_check > max_alloc) 1086 max_check = max_alloc; 1087 for (op = e->start.key + e->count.key; op < max_check; 1088 op++) { 1089 if (!wnd_is_free(wnd, op, 1)) 1090 break; 1091 } 1092 memcpy(&wnd->start_tree, &start_tree, 1093 sizeof(struct rb_root)); 1094 to_alloc = op - e->start.key; 1095 } 1096 1097 /* Prepare to return. */ 1098 fnd = e->start.key; 1099 if (e->start.key + to_alloc > max_alloc) 1100 to_alloc = max_alloc - e->start.key; 1101 goto found; 1102 } 1103 1104 if (wnd->uptodated == 1) { 1105 /* Extents tree is updated -> no free space. */ 1106 goto no_space; 1107 } 1108 1109 b_len = e->count.key; 1110 b_pos = e->start.key; 1111 1112 scan_bitmap: 1113 sb = wnd->sb; 1114 log2_bits = sb->s_blocksize_bits + 3; 1115 1116 /* At most two ranges [hint, max_alloc) + [0, hint). */ 1117 Again: 1118 1119 /* TODO: Optimize request for case nbits > wbits. */ 1120 iw = hint >> log2_bits; 1121 wbits = sb->s_blocksize * 8; 1122 wpos = hint & (wbits - 1); 1123 prev_tail = 0; 1124 fbits_valid = true; 1125 1126 if (max_alloc == wnd->nbits) { 1127 nwnd = wnd->nwnd; 1128 } else { 1129 size_t t = max_alloc + wbits - 1; 1130 1131 nwnd = likely(t > max_alloc) ? (t >> log2_bits) : wnd->nwnd; 1132 } 1133 1134 /* Enumerate all windows. */ 1135 for (; iw < nwnd; iw++) { 1136 wbit = iw << log2_bits; 1137 1138 if (!wnd->free_bits[iw]) { 1139 if (prev_tail > b_len) { 1140 b_pos = wbit - prev_tail; 1141 b_len = prev_tail; 1142 } 1143 1144 /* Skip full used window. */ 1145 prev_tail = 0; 1146 wpos = 0; 1147 continue; 1148 } 1149 1150 if (unlikely(iw + 1 == nwnd)) { 1151 if (max_alloc == wnd->nbits) { 1152 wbits = wnd->bits_last; 1153 } else { 1154 size_t t = max_alloc & (wbits - 1); 1155 1156 if (t) { 1157 wbits = t; 1158 fbits_valid = false; 1159 } 1160 } 1161 } 1162 1163 if (wnd->zone_end > wnd->zone_bit) { 1164 ebit = wbit + wbits; 1165 zbit = max(wnd->zone_bit, wbit); 1166 zend = min(wnd->zone_end, ebit); 1167 1168 /* Here we have a window [wbit, ebit) and zone [zbit, zend). */ 1169 if (zend <= zbit) { 1170 /* Zone does not overlap window. */ 1171 } else { 1172 wzbit = zbit - wbit; 1173 wzend = zend - wbit; 1174 1175 /* Zone overlaps window. */ 1176 if (wnd->free_bits[iw] == wzend - wzbit) { 1177 prev_tail = 0; 1178 wpos = 0; 1179 continue; 1180 } 1181 1182 /* Scan two ranges window: [wbit, zbit) and [zend, ebit). */ 1183 bh = wnd_map(wnd, iw); 1184 1185 if (IS_ERR(bh)) { 1186 /* TODO: Error */ 1187 prev_tail = 0; 1188 wpos = 0; 1189 continue; 1190 } 1191 1192 /* Scan range [wbit, zbit). */ 1193 if (wpos < wzbit) { 1194 /* Scan range [wpos, zbit). */ 1195 fnd = wnd_scan(bh->b_data, wbit, wpos, 1196 wzbit, to_alloc, 1197 &prev_tail, &b_pos, 1198 &b_len); 1199 if (fnd != MINUS_ONE_T) { 1200 put_bh(bh); 1201 goto found; 1202 } 1203 } 1204 1205 prev_tail = 0; 1206 1207 /* Scan range [zend, ebit). */ 1208 if (wzend < wbits) { 1209 fnd = wnd_scan(bh->b_data, wbit, 1210 max(wzend, wpos), wbits, 1211 to_alloc, &prev_tail, 1212 &b_pos, &b_len); 1213 if (fnd != MINUS_ONE_T) { 1214 put_bh(bh); 1215 goto found; 1216 } 1217 } 1218 1219 wpos = 0; 1220 put_bh(bh); 1221 continue; 1222 } 1223 } 1224 1225 /* Current window does not overlap zone. */ 1226 if (!wpos && fbits_valid && wnd->free_bits[iw] == wbits) { 1227 /* Window is empty. */ 1228 if (prev_tail + wbits >= to_alloc) { 1229 fnd = wbit + wpos - prev_tail; 1230 goto found; 1231 } 1232 1233 /* Increase 'prev_tail' and process next window. */ 1234 prev_tail += wbits; 1235 wpos = 0; 1236 continue; 1237 } 1238 1239 /* Read window. */ 1240 bh = wnd_map(wnd, iw); 1241 if (IS_ERR(bh)) { 1242 // TODO: Error. 1243 prev_tail = 0; 1244 wpos = 0; 1245 continue; 1246 } 1247 1248 /* Scan range [wpos, eBits). */ 1249 fnd = wnd_scan(bh->b_data, wbit, wpos, wbits, to_alloc, 1250 &prev_tail, &b_pos, &b_len); 1251 put_bh(bh); 1252 if (fnd != MINUS_ONE_T) 1253 goto found; 1254 } 1255 1256 if (b_len < prev_tail) { 1257 /* The last fragment. */ 1258 b_len = prev_tail; 1259 b_pos = max_alloc - prev_tail; 1260 } 1261 1262 if (hint) { 1263 /* 1264 * We have scanned range [hint max_alloc). 1265 * Prepare to scan range [0 hint + to_alloc). 1266 */ 1267 size_t nextmax = hint + to_alloc; 1268 1269 if (likely(nextmax >= hint) && nextmax < max_alloc) 1270 max_alloc = nextmax; 1271 hint = 0; 1272 goto Again; 1273 } 1274 1275 if (!b_len) 1276 goto no_space; 1277 1278 wnd->extent_max = b_len; 1279 1280 if (flags & BITMAP_FIND_FULL) 1281 goto no_space; 1282 1283 fnd = b_pos; 1284 to_alloc = b_len; 1285 1286 found: 1287 if (flags & BITMAP_FIND_MARK_AS_USED) { 1288 /* TODO: Optimize remove extent (pass 'e'?). */ 1289 if (wnd_set_used(wnd, fnd, to_alloc)) 1290 goto no_space; 1291 } else if (wnd->extent_max != MINUS_ONE_T && 1292 to_alloc > wnd->extent_max) { 1293 wnd->extent_max = to_alloc; 1294 } 1295 1296 *allocated = fnd; 1297 return to_alloc; 1298 1299 no_space: 1300 return 0; 1301 } 1302 1303 /* 1304 * wnd_extend - Extend bitmap ($MFT bitmap). 1305 */ 1306 int wnd_extend(struct wnd_bitmap *wnd, size_t new_bits) 1307 { 1308 int err; 1309 struct super_block *sb = wnd->sb; 1310 struct ntfs_sb_info *sbi = sb->s_fs_info; 1311 u32 blocksize = sb->s_blocksize; 1312 u32 wbits = blocksize * 8; 1313 u32 b0, new_last; 1314 size_t bits, iw, new_wnd; 1315 size_t old_bits = wnd->nbits; 1316 u16 *new_free; 1317 1318 if (new_bits <= old_bits) 1319 return -EINVAL; 1320 1321 /* Align to 8 byte boundary. */ 1322 new_wnd = bytes_to_block(sb, ntfs3_bitmap_size(new_bits)); 1323 new_last = new_bits & (wbits - 1); 1324 if (!new_last) 1325 new_last = wbits; 1326 1327 if (new_wnd != wnd->nwnd) { 1328 new_free = kmalloc_array(new_wnd, sizeof(u16), GFP_NOFS); 1329 if (!new_free) 1330 return -ENOMEM; 1331 1332 memcpy(new_free, wnd->free_bits, wnd->nwnd * sizeof(short)); 1333 memset(new_free + wnd->nwnd, 0, 1334 (new_wnd - wnd->nwnd) * sizeof(short)); 1335 kvfree(wnd->free_bits); 1336 wnd->free_bits = new_free; 1337 } 1338 1339 /* Zero bits [old_bits,new_bits). */ 1340 bits = new_bits - old_bits; 1341 b0 = old_bits & (wbits - 1); 1342 1343 for (iw = old_bits >> (sb->s_blocksize_bits + 3); bits; iw += 1) { 1344 u32 op; 1345 size_t frb; 1346 u64 vbo, lbo, bytes; 1347 struct buffer_head *bh; 1348 1349 if (iw + 1 == new_wnd) 1350 wbits = new_last; 1351 1352 op = b0 + bits > wbits ? wbits - b0 : bits; 1353 vbo = (u64)iw * blocksize; 1354 1355 err = ntfs_vbo_to_lbo(sbi, &wnd->run, vbo, &lbo, &bytes); 1356 if (err) 1357 return err; 1358 1359 bh = ntfs_bread(sb, lbo >> sb->s_blocksize_bits); 1360 if (!bh) 1361 return -EIO; 1362 1363 lock_buffer(bh); 1364 1365 ntfs_bitmap_clear_le(bh->b_data, b0, blocksize * 8 - b0); 1366 frb = wbits - ntfs_bitmap_weight_le(bh->b_data, wbits); 1367 wnd->total_zeroes += frb - wnd->free_bits[iw]; 1368 wnd->free_bits[iw] = frb; 1369 1370 set_buffer_uptodate(bh); 1371 mark_buffer_dirty(bh); 1372 unlock_buffer(bh); 1373 /* err = sync_dirty_buffer(bh); */ 1374 1375 b0 = 0; 1376 bits -= op; 1377 } 1378 1379 wnd->nbits = new_bits; 1380 wnd->nwnd = new_wnd; 1381 wnd->bits_last = new_last; 1382 1383 wnd_add_free_ext(wnd, old_bits, new_bits - old_bits, false); 1384 1385 return 0; 1386 } 1387 1388 void wnd_zone_set(struct wnd_bitmap *wnd, size_t lcn, size_t len) 1389 { 1390 size_t zlen = wnd->zone_end - wnd->zone_bit; 1391 1392 if (zlen) 1393 wnd_add_free_ext(wnd, wnd->zone_bit, zlen, false); 1394 1395 if (!RB_EMPTY_ROOT(&wnd->start_tree) && len) 1396 wnd_remove_free_ext(wnd, lcn, len); 1397 1398 wnd->zone_bit = lcn; 1399 wnd->zone_end = lcn + len; 1400 } 1401 1402 int ntfs_trim_fs(struct ntfs_sb_info *sbi, struct fstrim_range *range) 1403 { 1404 int err = 0; 1405 struct super_block *sb = sbi->sb; 1406 struct wnd_bitmap *wnd = &sbi->used.bitmap; 1407 u32 wbits = 8 * sb->s_blocksize; 1408 CLST len = 0, lcn = 0, done = 0; 1409 CLST minlen = bytes_to_cluster(sbi, range->minlen); 1410 CLST lcn_from = bytes_to_cluster(sbi, range->start); 1411 size_t iw = lcn_from >> (sb->s_blocksize_bits + 3); 1412 u32 wbit = lcn_from & (wbits - 1); 1413 CLST lcn_to; 1414 1415 if (!minlen) 1416 minlen = 1; 1417 1418 if (range->len == (u64)-1) 1419 lcn_to = wnd->nbits; 1420 else 1421 lcn_to = bytes_to_cluster(sbi, range->start + range->len); 1422 1423 down_read_nested(&wnd->rw_lock, BITMAP_MUTEX_CLUSTERS); 1424 1425 for (; iw < wnd->nwnd; iw++, wbit = 0) { 1426 CLST lcn_wnd = iw * wbits; 1427 struct buffer_head *bh; 1428 1429 if (lcn_wnd > lcn_to) 1430 break; 1431 1432 if (!wnd->free_bits[iw]) 1433 continue; 1434 1435 if (iw + 1 == wnd->nwnd) 1436 wbits = wnd->bits_last; 1437 1438 if (lcn_wnd + wbits > lcn_to) 1439 wbits = lcn_to - lcn_wnd; 1440 1441 bh = wnd_map(wnd, iw); 1442 if (IS_ERR(bh)) { 1443 err = PTR_ERR(bh); 1444 break; 1445 } 1446 1447 for (; wbit < wbits; wbit++) { 1448 if (!test_bit_le(wbit, bh->b_data)) { 1449 if (!len) 1450 lcn = lcn_wnd + wbit; 1451 len += 1; 1452 continue; 1453 } 1454 if (len >= minlen) { 1455 err = ntfs_discard(sbi, lcn, len); 1456 if (err) 1457 goto out; 1458 done += len; 1459 } 1460 len = 0; 1461 } 1462 put_bh(bh); 1463 } 1464 1465 /* Process the last fragment. */ 1466 if (len >= minlen) { 1467 err = ntfs_discard(sbi, lcn, len); 1468 if (err) 1469 goto out; 1470 done += len; 1471 } 1472 1473 out: 1474 range->len = (u64)done << sbi->cluster_bits; 1475 1476 up_read(&wnd->rw_lock); 1477 1478 return err; 1479 } 1480 1481 #if BITS_PER_LONG == 64 1482 typedef __le64 bitmap_ulong; 1483 #define cpu_to_ul(x) cpu_to_le64(x) 1484 #define ul_to_cpu(x) le64_to_cpu(x) 1485 #else 1486 typedef __le32 bitmap_ulong; 1487 #define cpu_to_ul(x) cpu_to_le32(x) 1488 #define ul_to_cpu(x) le32_to_cpu(x) 1489 #endif 1490 1491 void ntfs_bitmap_set_le(void *map, unsigned int start, int len) 1492 { 1493 bitmap_ulong *p = (bitmap_ulong *)map + BIT_WORD(start); 1494 const unsigned int size = start + len; 1495 int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG); 1496 bitmap_ulong mask_to_set = cpu_to_ul(BITMAP_FIRST_WORD_MASK(start)); 1497 1498 while (len - bits_to_set >= 0) { 1499 *p |= mask_to_set; 1500 len -= bits_to_set; 1501 bits_to_set = BITS_PER_LONG; 1502 mask_to_set = cpu_to_ul(~0UL); 1503 p++; 1504 } 1505 if (len) { 1506 mask_to_set &= cpu_to_ul(BITMAP_LAST_WORD_MASK(size)); 1507 *p |= mask_to_set; 1508 } 1509 } 1510 1511 void ntfs_bitmap_clear_le(void *map, unsigned int start, int len) 1512 { 1513 bitmap_ulong *p = (bitmap_ulong *)map + BIT_WORD(start); 1514 const unsigned int size = start + len; 1515 int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG); 1516 bitmap_ulong mask_to_clear = cpu_to_ul(BITMAP_FIRST_WORD_MASK(start)); 1517 1518 while (len - bits_to_clear >= 0) { 1519 *p &= ~mask_to_clear; 1520 len -= bits_to_clear; 1521 bits_to_clear = BITS_PER_LONG; 1522 mask_to_clear = cpu_to_ul(~0UL); 1523 p++; 1524 } 1525 if (len) { 1526 mask_to_clear &= cpu_to_ul(BITMAP_LAST_WORD_MASK(size)); 1527 *p &= ~mask_to_clear; 1528 } 1529 } 1530 1531 unsigned int ntfs_bitmap_weight_le(const void *bitmap, int bits) 1532 { 1533 const ulong *bmp = bitmap; 1534 unsigned int k, lim = bits / BITS_PER_LONG; 1535 unsigned int w = 0; 1536 1537 for (k = 0; k < lim; k++) 1538 w += hweight_long(bmp[k]); 1539 1540 if (bits % BITS_PER_LONG) { 1541 w += hweight_long(ul_to_cpu(((bitmap_ulong *)bitmap)[k]) & 1542 BITMAP_LAST_WORD_MASK(bits)); 1543 } 1544 1545 return w; 1546 } 1547