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 = 44 kmem_cache_create("ntfs3_enode_cache", 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 = kcalloc(wnd->nwnd, sizeof(u16), GFP_NOFS | __GFP_NOWARN); 662 if (!wnd->free_bits) 663 return -ENOMEM; 664 665 err = wnd_rescan(wnd); 666 if (err) 667 return err; 668 669 wnd->inited = true; 670 671 return 0; 672 } 673 674 /* 675 * wnd_map - Call sb_bread for requested window. 676 */ 677 static struct buffer_head *wnd_map(struct wnd_bitmap *wnd, size_t iw) 678 { 679 size_t vbo; 680 CLST lcn, clen; 681 struct super_block *sb = wnd->sb; 682 struct ntfs_sb_info *sbi; 683 struct buffer_head *bh; 684 u64 lbo; 685 686 sbi = sb->s_fs_info; 687 vbo = (u64)iw << sb->s_blocksize_bits; 688 689 if (!run_lookup_entry(&wnd->run, vbo >> sbi->cluster_bits, &lcn, &clen, 690 NULL)) { 691 return ERR_PTR(-ENOENT); 692 } 693 694 lbo = ((u64)lcn << sbi->cluster_bits) + (vbo & sbi->cluster_mask); 695 696 bh = ntfs_bread(wnd->sb, lbo >> sb->s_blocksize_bits); 697 if (!bh) 698 return ERR_PTR(-EIO); 699 700 return bh; 701 } 702 703 /* 704 * wnd_set_free - Mark the bits range from bit to bit + bits as free. 705 */ 706 int wnd_set_free(struct wnd_bitmap *wnd, size_t bit, size_t bits) 707 { 708 int err = 0; 709 struct super_block *sb = wnd->sb; 710 size_t bits0 = bits; 711 u32 wbits = 8 * sb->s_blocksize; 712 size_t iw = bit >> (sb->s_blocksize_bits + 3); 713 u32 wbit = bit & (wbits - 1); 714 struct buffer_head *bh; 715 716 while (iw < wnd->nwnd && bits) { 717 u32 tail, op; 718 719 if (iw + 1 == wnd->nwnd) 720 wbits = wnd->bits_last; 721 722 tail = wbits - wbit; 723 op = min_t(u32, tail, 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 737 set_buffer_uptodate(bh); 738 mark_buffer_dirty(bh); 739 unlock_buffer(bh); 740 put_bh(bh); 741 742 wnd->total_zeroes += op; 743 bits -= op; 744 wbit = 0; 745 iw += 1; 746 } 747 748 wnd_add_free_ext(wnd, bit, bits0, false); 749 750 return err; 751 } 752 753 /* 754 * wnd_set_used - Mark the bits range from bit to bit + bits as used. 755 */ 756 int wnd_set_used(struct wnd_bitmap *wnd, size_t bit, size_t bits) 757 { 758 int err = 0; 759 struct super_block *sb = wnd->sb; 760 size_t bits0 = bits; 761 size_t iw = bit >> (sb->s_blocksize_bits + 3); 762 u32 wbits = 8 * sb->s_blocksize; 763 u32 wbit = bit & (wbits - 1); 764 struct buffer_head *bh; 765 766 while (iw < wnd->nwnd && bits) { 767 u32 tail, op; 768 769 if (unlikely(iw + 1 == wnd->nwnd)) 770 wbits = wnd->bits_last; 771 772 tail = wbits - wbit; 773 op = min_t(u32, tail, bits); 774 775 bh = wnd_map(wnd, iw); 776 if (IS_ERR(bh)) { 777 err = PTR_ERR(bh); 778 break; 779 } 780 781 lock_buffer(bh); 782 783 ntfs_bitmap_set_le(bh->b_data, wbit, op); 784 wnd->free_bits[iw] -= op; 785 786 set_buffer_uptodate(bh); 787 mark_buffer_dirty(bh); 788 unlock_buffer(bh); 789 put_bh(bh); 790 791 wnd->total_zeroes -= op; 792 bits -= op; 793 wbit = 0; 794 iw += 1; 795 } 796 797 if (!RB_EMPTY_ROOT(&wnd->start_tree)) 798 wnd_remove_free_ext(wnd, bit, bits0); 799 800 return err; 801 } 802 803 /* 804 * wnd_is_free_hlp 805 * 806 * Return: True if all clusters [bit, bit+bits) are free (bitmap only). 807 */ 808 static bool wnd_is_free_hlp(struct wnd_bitmap *wnd, size_t bit, size_t bits) 809 { 810 struct super_block *sb = wnd->sb; 811 size_t iw = bit >> (sb->s_blocksize_bits + 3); 812 u32 wbits = 8 * sb->s_blocksize; 813 u32 wbit = bit & (wbits - 1); 814 815 while (iw < wnd->nwnd && bits) { 816 u32 tail, op; 817 818 if (unlikely(iw + 1 == wnd->nwnd)) 819 wbits = wnd->bits_last; 820 821 tail = wbits - wbit; 822 op = min_t(u32, tail, bits); 823 824 if (wbits != wnd->free_bits[iw]) { 825 bool ret; 826 struct buffer_head *bh = wnd_map(wnd, iw); 827 828 if (IS_ERR(bh)) 829 return false; 830 831 ret = are_bits_clear(bh->b_data, wbit, op); 832 833 put_bh(bh); 834 if (!ret) 835 return false; 836 } 837 838 bits -= op; 839 wbit = 0; 840 iw += 1; 841 } 842 843 return true; 844 } 845 846 /* 847 * wnd_is_free 848 * 849 * Return: True if all clusters [bit, bit+bits) are free. 850 */ 851 bool wnd_is_free(struct wnd_bitmap *wnd, size_t bit, size_t bits) 852 { 853 bool ret; 854 struct rb_node *n; 855 size_t end; 856 struct e_node *e; 857 858 if (RB_EMPTY_ROOT(&wnd->start_tree)) 859 goto use_wnd; 860 861 n = rb_lookup(&wnd->start_tree, bit); 862 if (!n) 863 goto use_wnd; 864 865 e = rb_entry(n, struct e_node, start.node); 866 867 end = e->start.key + e->count.key; 868 869 if (bit < end && bit + bits <= end) 870 return true; 871 872 use_wnd: 873 ret = wnd_is_free_hlp(wnd, bit, bits); 874 875 return ret; 876 } 877 878 /* 879 * wnd_is_used 880 * 881 * Return: True if all clusters [bit, bit+bits) are used. 882 */ 883 bool wnd_is_used(struct wnd_bitmap *wnd, size_t bit, size_t bits) 884 { 885 bool ret = false; 886 struct super_block *sb = wnd->sb; 887 size_t iw = bit >> (sb->s_blocksize_bits + 3); 888 u32 wbits = 8 * sb->s_blocksize; 889 u32 wbit = bit & (wbits - 1); 890 size_t end; 891 struct rb_node *n; 892 struct e_node *e; 893 894 if (RB_EMPTY_ROOT(&wnd->start_tree)) 895 goto use_wnd; 896 897 end = bit + bits; 898 n = rb_lookup(&wnd->start_tree, end - 1); 899 if (!n) 900 goto use_wnd; 901 902 e = rb_entry(n, struct e_node, start.node); 903 if (e->start.key + e->count.key > bit) 904 return false; 905 906 use_wnd: 907 while (iw < wnd->nwnd && bits) { 908 u32 tail, op; 909 910 if (unlikely(iw + 1 == wnd->nwnd)) 911 wbits = wnd->bits_last; 912 913 tail = wbits - wbit; 914 op = min_t(u32, tail, bits); 915 916 if (wnd->free_bits[iw]) { 917 bool ret; 918 struct buffer_head *bh = wnd_map(wnd, iw); 919 920 if (IS_ERR(bh)) 921 goto out; 922 923 ret = are_bits_set(bh->b_data, wbit, op); 924 put_bh(bh); 925 if (!ret) 926 goto out; 927 } 928 929 bits -= op; 930 wbit = 0; 931 iw += 1; 932 } 933 ret = true; 934 935 out: 936 return ret; 937 } 938 939 /* 940 * wnd_find - Look for free space. 941 * 942 * - flags - BITMAP_FIND_XXX flags 943 * 944 * Return: 0 if not found. 945 */ 946 size_t wnd_find(struct wnd_bitmap *wnd, size_t to_alloc, size_t hint, 947 size_t flags, size_t *allocated) 948 { 949 struct super_block *sb; 950 u32 wbits, wpos, wzbit, wzend; 951 size_t fnd, max_alloc, b_len, b_pos; 952 size_t iw, prev_tail, nwnd, wbit, ebit, zbit, zend; 953 size_t to_alloc0 = to_alloc; 954 const struct e_node *e; 955 const struct rb_node *pr, *cr; 956 u8 log2_bits; 957 bool fbits_valid; 958 struct buffer_head *bh; 959 960 /* Fast checking for available free space. */ 961 if (flags & BITMAP_FIND_FULL) { 962 size_t zeroes = wnd_zeroes(wnd); 963 964 zeroes -= wnd->zone_end - wnd->zone_bit; 965 if (zeroes < to_alloc0) 966 goto no_space; 967 968 if (to_alloc0 > wnd->extent_max) 969 goto no_space; 970 } else { 971 if (to_alloc > wnd->extent_max) 972 to_alloc = wnd->extent_max; 973 } 974 975 if (wnd->zone_bit <= hint && hint < wnd->zone_end) 976 hint = wnd->zone_end; 977 978 max_alloc = wnd->nbits; 979 b_len = b_pos = 0; 980 981 if (hint >= max_alloc) 982 hint = 0; 983 984 if (RB_EMPTY_ROOT(&wnd->start_tree)) { 985 if (wnd->uptodated == 1) { 986 /* Extents tree is updated -> No free space. */ 987 goto no_space; 988 } 989 goto scan_bitmap; 990 } 991 992 e = NULL; 993 if (!hint) 994 goto allocate_biggest; 995 996 /* Use hint: Enumerate extents by start >= hint. */ 997 pr = NULL; 998 cr = wnd->start_tree.rb_node; 999 1000 for (;;) { 1001 e = rb_entry(cr, struct e_node, start.node); 1002 1003 if (e->start.key == hint) 1004 break; 1005 1006 if (e->start.key < hint) { 1007 pr = cr; 1008 cr = cr->rb_right; 1009 if (!cr) 1010 break; 1011 continue; 1012 } 1013 1014 cr = cr->rb_left; 1015 if (!cr) { 1016 e = pr ? rb_entry(pr, struct e_node, start.node) : NULL; 1017 break; 1018 } 1019 } 1020 1021 if (!e) 1022 goto allocate_biggest; 1023 1024 if (e->start.key + e->count.key > hint) { 1025 /* We have found extension with 'hint' inside. */ 1026 size_t len = e->start.key + e->count.key - hint; 1027 1028 if (len >= to_alloc && hint + to_alloc <= max_alloc) { 1029 fnd = hint; 1030 goto found; 1031 } 1032 1033 if (!(flags & BITMAP_FIND_FULL)) { 1034 if (len > to_alloc) 1035 len = to_alloc; 1036 1037 if (hint + len <= max_alloc) { 1038 fnd = hint; 1039 to_alloc = len; 1040 goto found; 1041 } 1042 } 1043 } 1044 1045 allocate_biggest: 1046 /* Allocate from biggest free extent. */ 1047 e = rb_entry(rb_first(&wnd->count_tree), struct e_node, count.node); 1048 if (e->count.key != wnd->extent_max) 1049 wnd->extent_max = e->count.key; 1050 1051 if (e->count.key < max_alloc) { 1052 if (e->count.key >= to_alloc) { 1053 ; 1054 } else if (flags & BITMAP_FIND_FULL) { 1055 if (e->count.key < to_alloc0) { 1056 /* Biggest free block is less then requested. */ 1057 goto no_space; 1058 } 1059 to_alloc = e->count.key; 1060 } else if (-1 != wnd->uptodated) { 1061 to_alloc = e->count.key; 1062 } else { 1063 /* Check if we can use more bits. */ 1064 size_t op, max_check; 1065 struct rb_root start_tree; 1066 1067 memcpy(&start_tree, &wnd->start_tree, 1068 sizeof(struct rb_root)); 1069 memset(&wnd->start_tree, 0, sizeof(struct rb_root)); 1070 1071 max_check = e->start.key + to_alloc; 1072 if (max_check > max_alloc) 1073 max_check = max_alloc; 1074 for (op = e->start.key + e->count.key; op < max_check; 1075 op++) { 1076 if (!wnd_is_free(wnd, op, 1)) 1077 break; 1078 } 1079 memcpy(&wnd->start_tree, &start_tree, 1080 sizeof(struct rb_root)); 1081 to_alloc = op - e->start.key; 1082 } 1083 1084 /* Prepare to return. */ 1085 fnd = e->start.key; 1086 if (e->start.key + to_alloc > max_alloc) 1087 to_alloc = max_alloc - e->start.key; 1088 goto found; 1089 } 1090 1091 if (wnd->uptodated == 1) { 1092 /* Extents tree is updated -> no free space. */ 1093 goto no_space; 1094 } 1095 1096 b_len = e->count.key; 1097 b_pos = e->start.key; 1098 1099 scan_bitmap: 1100 sb = wnd->sb; 1101 log2_bits = sb->s_blocksize_bits + 3; 1102 1103 /* At most two ranges [hint, max_alloc) + [0, hint). */ 1104 Again: 1105 1106 /* TODO: Optimize request for case nbits > wbits. */ 1107 iw = hint >> log2_bits; 1108 wbits = sb->s_blocksize * 8; 1109 wpos = hint & (wbits - 1); 1110 prev_tail = 0; 1111 fbits_valid = true; 1112 1113 if (max_alloc == wnd->nbits) { 1114 nwnd = wnd->nwnd; 1115 } else { 1116 size_t t = max_alloc + wbits - 1; 1117 1118 nwnd = likely(t > max_alloc) ? (t >> log2_bits) : wnd->nwnd; 1119 } 1120 1121 /* Enumerate all windows. */ 1122 for (; iw < nwnd; iw++) { 1123 wbit = iw << log2_bits; 1124 1125 if (!wnd->free_bits[iw]) { 1126 if (prev_tail > b_len) { 1127 b_pos = wbit - prev_tail; 1128 b_len = prev_tail; 1129 } 1130 1131 /* Skip full used window. */ 1132 prev_tail = 0; 1133 wpos = 0; 1134 continue; 1135 } 1136 1137 if (unlikely(iw + 1 == nwnd)) { 1138 if (max_alloc == wnd->nbits) { 1139 wbits = wnd->bits_last; 1140 } else { 1141 size_t t = max_alloc & (wbits - 1); 1142 1143 if (t) { 1144 wbits = t; 1145 fbits_valid = false; 1146 } 1147 } 1148 } 1149 1150 if (wnd->zone_end > wnd->zone_bit) { 1151 ebit = wbit + wbits; 1152 zbit = max(wnd->zone_bit, wbit); 1153 zend = min(wnd->zone_end, ebit); 1154 1155 /* Here we have a window [wbit, ebit) and zone [zbit, zend). */ 1156 if (zend <= zbit) { 1157 /* Zone does not overlap window. */ 1158 } else { 1159 wzbit = zbit - wbit; 1160 wzend = zend - wbit; 1161 1162 /* Zone overlaps window. */ 1163 if (wnd->free_bits[iw] == wzend - wzbit) { 1164 prev_tail = 0; 1165 wpos = 0; 1166 continue; 1167 } 1168 1169 /* Scan two ranges window: [wbit, zbit) and [zend, ebit). */ 1170 bh = wnd_map(wnd, iw); 1171 1172 if (IS_ERR(bh)) { 1173 /* TODO: Error */ 1174 prev_tail = 0; 1175 wpos = 0; 1176 continue; 1177 } 1178 1179 /* Scan range [wbit, zbit). */ 1180 if (wpos < wzbit) { 1181 /* Scan range [wpos, zbit). */ 1182 fnd = wnd_scan(bh->b_data, wbit, wpos, 1183 wzbit, to_alloc, 1184 &prev_tail, &b_pos, 1185 &b_len); 1186 if (fnd != MINUS_ONE_T) { 1187 put_bh(bh); 1188 goto found; 1189 } 1190 } 1191 1192 prev_tail = 0; 1193 1194 /* Scan range [zend, ebit). */ 1195 if (wzend < wbits) { 1196 fnd = wnd_scan(bh->b_data, wbit, 1197 max(wzend, wpos), wbits, 1198 to_alloc, &prev_tail, 1199 &b_pos, &b_len); 1200 if (fnd != MINUS_ONE_T) { 1201 put_bh(bh); 1202 goto found; 1203 } 1204 } 1205 1206 wpos = 0; 1207 put_bh(bh); 1208 continue; 1209 } 1210 } 1211 1212 /* Current window does not overlap zone. */ 1213 if (!wpos && fbits_valid && wnd->free_bits[iw] == wbits) { 1214 /* Window is empty. */ 1215 if (prev_tail + wbits >= to_alloc) { 1216 fnd = wbit + wpos - prev_tail; 1217 goto found; 1218 } 1219 1220 /* Increase 'prev_tail' and process next window. */ 1221 prev_tail += wbits; 1222 wpos = 0; 1223 continue; 1224 } 1225 1226 /* Read window. */ 1227 bh = wnd_map(wnd, iw); 1228 if (IS_ERR(bh)) { 1229 // TODO: Error. 1230 prev_tail = 0; 1231 wpos = 0; 1232 continue; 1233 } 1234 1235 /* Scan range [wpos, eBits). */ 1236 fnd = wnd_scan(bh->b_data, wbit, wpos, wbits, to_alloc, 1237 &prev_tail, &b_pos, &b_len); 1238 put_bh(bh); 1239 if (fnd != MINUS_ONE_T) 1240 goto found; 1241 } 1242 1243 if (b_len < prev_tail) { 1244 /* The last fragment. */ 1245 b_len = prev_tail; 1246 b_pos = max_alloc - prev_tail; 1247 } 1248 1249 if (hint) { 1250 /* 1251 * We have scanned range [hint max_alloc). 1252 * Prepare to scan range [0 hint + to_alloc). 1253 */ 1254 size_t nextmax = hint + to_alloc; 1255 1256 if (likely(nextmax >= hint) && nextmax < max_alloc) 1257 max_alloc = nextmax; 1258 hint = 0; 1259 goto Again; 1260 } 1261 1262 if (!b_len) 1263 goto no_space; 1264 1265 wnd->extent_max = b_len; 1266 1267 if (flags & BITMAP_FIND_FULL) 1268 goto no_space; 1269 1270 fnd = b_pos; 1271 to_alloc = b_len; 1272 1273 found: 1274 if (flags & BITMAP_FIND_MARK_AS_USED) { 1275 /* TODO: Optimize remove extent (pass 'e'?). */ 1276 if (wnd_set_used(wnd, fnd, to_alloc)) 1277 goto no_space; 1278 } else if (wnd->extent_max != MINUS_ONE_T && 1279 to_alloc > wnd->extent_max) { 1280 wnd->extent_max = to_alloc; 1281 } 1282 1283 *allocated = fnd; 1284 return to_alloc; 1285 1286 no_space: 1287 return 0; 1288 } 1289 1290 /* 1291 * wnd_extend - Extend bitmap ($MFT bitmap). 1292 */ 1293 int wnd_extend(struct wnd_bitmap *wnd, size_t new_bits) 1294 { 1295 int err; 1296 struct super_block *sb = wnd->sb; 1297 struct ntfs_sb_info *sbi = sb->s_fs_info; 1298 u32 blocksize = sb->s_blocksize; 1299 u32 wbits = blocksize * 8; 1300 u32 b0, new_last; 1301 size_t bits, iw, new_wnd; 1302 size_t old_bits = wnd->nbits; 1303 u16 *new_free; 1304 1305 if (new_bits <= old_bits) 1306 return -EINVAL; 1307 1308 /* Align to 8 byte boundary. */ 1309 new_wnd = bytes_to_block(sb, bitmap_size(new_bits)); 1310 new_last = new_bits & (wbits - 1); 1311 if (!new_last) 1312 new_last = wbits; 1313 1314 if (new_wnd != wnd->nwnd) { 1315 new_free = kmalloc_array(new_wnd, sizeof(u16), GFP_NOFS); 1316 if (!new_free) 1317 return -ENOMEM; 1318 1319 memcpy(new_free, wnd->free_bits, wnd->nwnd * sizeof(short)); 1320 memset(new_free + wnd->nwnd, 0, 1321 (new_wnd - wnd->nwnd) * sizeof(short)); 1322 kfree(wnd->free_bits); 1323 wnd->free_bits = new_free; 1324 } 1325 1326 /* Zero bits [old_bits,new_bits). */ 1327 bits = new_bits - old_bits; 1328 b0 = old_bits & (wbits - 1); 1329 1330 for (iw = old_bits >> (sb->s_blocksize_bits + 3); bits; iw += 1) { 1331 u32 op; 1332 size_t frb; 1333 u64 vbo, lbo, bytes; 1334 struct buffer_head *bh; 1335 1336 if (iw + 1 == new_wnd) 1337 wbits = new_last; 1338 1339 op = b0 + bits > wbits ? wbits - b0 : bits; 1340 vbo = (u64)iw * blocksize; 1341 1342 err = ntfs_vbo_to_lbo(sbi, &wnd->run, vbo, &lbo, &bytes); 1343 if (err) 1344 break; 1345 1346 bh = ntfs_bread(sb, lbo >> sb->s_blocksize_bits); 1347 if (!bh) 1348 return -EIO; 1349 1350 lock_buffer(bh); 1351 1352 ntfs_bitmap_clear_le(bh->b_data, b0, blocksize * 8 - b0); 1353 frb = wbits - ntfs_bitmap_weight_le(bh->b_data, wbits); 1354 wnd->total_zeroes += frb - wnd->free_bits[iw]; 1355 wnd->free_bits[iw] = frb; 1356 1357 set_buffer_uptodate(bh); 1358 mark_buffer_dirty(bh); 1359 unlock_buffer(bh); 1360 /* err = sync_dirty_buffer(bh); */ 1361 1362 b0 = 0; 1363 bits -= op; 1364 } 1365 1366 wnd->nbits = new_bits; 1367 wnd->nwnd = new_wnd; 1368 wnd->bits_last = new_last; 1369 1370 wnd_add_free_ext(wnd, old_bits, new_bits - old_bits, false); 1371 1372 return 0; 1373 } 1374 1375 void wnd_zone_set(struct wnd_bitmap *wnd, size_t lcn, size_t len) 1376 { 1377 size_t zlen = wnd->zone_end - wnd->zone_bit; 1378 1379 if (zlen) 1380 wnd_add_free_ext(wnd, wnd->zone_bit, zlen, false); 1381 1382 if (!RB_EMPTY_ROOT(&wnd->start_tree) && len) 1383 wnd_remove_free_ext(wnd, lcn, len); 1384 1385 wnd->zone_bit = lcn; 1386 wnd->zone_end = lcn + len; 1387 } 1388 1389 int ntfs_trim_fs(struct ntfs_sb_info *sbi, struct fstrim_range *range) 1390 { 1391 int err = 0; 1392 struct super_block *sb = sbi->sb; 1393 struct wnd_bitmap *wnd = &sbi->used.bitmap; 1394 u32 wbits = 8 * sb->s_blocksize; 1395 CLST len = 0, lcn = 0, done = 0; 1396 CLST minlen = bytes_to_cluster(sbi, range->minlen); 1397 CLST lcn_from = bytes_to_cluster(sbi, range->start); 1398 size_t iw = lcn_from >> (sb->s_blocksize_bits + 3); 1399 u32 wbit = lcn_from & (wbits - 1); 1400 CLST lcn_to; 1401 1402 if (!minlen) 1403 minlen = 1; 1404 1405 if (range->len == (u64)-1) 1406 lcn_to = wnd->nbits; 1407 else 1408 lcn_to = bytes_to_cluster(sbi, range->start + range->len); 1409 1410 down_read_nested(&wnd->rw_lock, BITMAP_MUTEX_CLUSTERS); 1411 1412 for (; iw < wnd->nwnd; iw++, wbit = 0) { 1413 CLST lcn_wnd = iw * wbits; 1414 struct buffer_head *bh; 1415 1416 if (lcn_wnd > lcn_to) 1417 break; 1418 1419 if (!wnd->free_bits[iw]) 1420 continue; 1421 1422 if (iw + 1 == wnd->nwnd) 1423 wbits = wnd->bits_last; 1424 1425 if (lcn_wnd + wbits > lcn_to) 1426 wbits = lcn_to - lcn_wnd; 1427 1428 bh = wnd_map(wnd, iw); 1429 if (IS_ERR(bh)) { 1430 err = PTR_ERR(bh); 1431 break; 1432 } 1433 1434 for (; wbit < wbits; wbit++) { 1435 if (!test_bit_le(wbit, bh->b_data)) { 1436 if (!len) 1437 lcn = lcn_wnd + wbit; 1438 len += 1; 1439 continue; 1440 } 1441 if (len >= minlen) { 1442 err = ntfs_discard(sbi, lcn, len); 1443 if (err) 1444 goto out; 1445 done += len; 1446 } 1447 len = 0; 1448 } 1449 put_bh(bh); 1450 } 1451 1452 /* Process the last fragment. */ 1453 if (len >= minlen) { 1454 err = ntfs_discard(sbi, lcn, len); 1455 if (err) 1456 goto out; 1457 done += len; 1458 } 1459 1460 out: 1461 range->len = (u64)done << sbi->cluster_bits; 1462 1463 up_read(&wnd->rw_lock); 1464 1465 return err; 1466 } 1467 1468 #if BITS_PER_LONG == 64 1469 typedef __le64 bitmap_ulong; 1470 #define cpu_to_ul(x) cpu_to_le64(x) 1471 #define ul_to_cpu(x) le64_to_cpu(x) 1472 #else 1473 typedef __le32 bitmap_ulong; 1474 #define cpu_to_ul(x) cpu_to_le32(x) 1475 #define ul_to_cpu(x) le32_to_cpu(x) 1476 #endif 1477 1478 void ntfs_bitmap_set_le(void *map, unsigned int start, int len) 1479 { 1480 bitmap_ulong *p = (bitmap_ulong *)map + BIT_WORD(start); 1481 const unsigned int size = start + len; 1482 int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG); 1483 bitmap_ulong mask_to_set = cpu_to_ul(BITMAP_FIRST_WORD_MASK(start)); 1484 1485 while (len - bits_to_set >= 0) { 1486 *p |= mask_to_set; 1487 len -= bits_to_set; 1488 bits_to_set = BITS_PER_LONG; 1489 mask_to_set = cpu_to_ul(~0UL); 1490 p++; 1491 } 1492 if (len) { 1493 mask_to_set &= cpu_to_ul(BITMAP_LAST_WORD_MASK(size)); 1494 *p |= mask_to_set; 1495 } 1496 } 1497 1498 void ntfs_bitmap_clear_le(void *map, unsigned int start, int len) 1499 { 1500 bitmap_ulong *p = (bitmap_ulong *)map + BIT_WORD(start); 1501 const unsigned int size = start + len; 1502 int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG); 1503 bitmap_ulong mask_to_clear = cpu_to_ul(BITMAP_FIRST_WORD_MASK(start)); 1504 1505 while (len - bits_to_clear >= 0) { 1506 *p &= ~mask_to_clear; 1507 len -= bits_to_clear; 1508 bits_to_clear = BITS_PER_LONG; 1509 mask_to_clear = cpu_to_ul(~0UL); 1510 p++; 1511 } 1512 if (len) { 1513 mask_to_clear &= cpu_to_ul(BITMAP_LAST_WORD_MASK(size)); 1514 *p &= ~mask_to_clear; 1515 } 1516 } 1517 1518 unsigned int ntfs_bitmap_weight_le(const void *bitmap, int bits) 1519 { 1520 const ulong *bmp = bitmap; 1521 unsigned int k, lim = bits / BITS_PER_LONG; 1522 unsigned int w = 0; 1523 1524 for (k = 0; k < lim; k++) 1525 w += hweight_long(bmp[k]); 1526 1527 if (bits % BITS_PER_LONG) { 1528 w += hweight_long(ul_to_cpu(((bitmap_ulong *)bitmap)[k]) & 1529 BITMAP_LAST_WORD_MASK(bits)); 1530 } 1531 1532 return w; 1533 } 1534