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