1 // SPDX-License-Identifier: GPL-2.0 2 /* 3 * 4 * Copyright (C) 2019-2021 Paragon Software GmbH, All rights reserved. 5 * 6 * TODO: try to use extents tree (instead of array) 7 */ 8 9 #include <linux/blkdev.h> 10 #include <linux/fs.h> 11 #include <linux/log2.h> 12 #include <linux/overflow.h> 13 14 #include "debug.h" 15 #include "ntfs.h" 16 #include "ntfs_fs.h" 17 18 /* runs_tree is a continues memory. Try to avoid big size. */ 19 #define NTFS3_RUN_MAX_BYTES 0x10000 20 21 struct ntfs_run { 22 CLST vcn; /* Virtual cluster number. */ 23 CLST len; /* Length in clusters. */ 24 CLST lcn; /* Logical cluster number. */ 25 }; 26 27 /* 28 * run_lookup - Lookup the index of a MCB entry that is first <= vcn. 29 * 30 * Case of success it will return non-zero value and set 31 * @index parameter to index of entry been found. 32 * Case of entry missing from list 'index' will be set to 33 * point to insertion position for the entry question. 34 */ 35 static bool run_lookup(const struct runs_tree *run, CLST vcn, size_t *index) 36 { 37 size_t min_idx, max_idx, mid_idx; 38 struct ntfs_run *r; 39 40 if (!run->count) { 41 *index = 0; 42 return false; 43 } 44 45 min_idx = 0; 46 max_idx = run->count - 1; 47 48 /* Check boundary cases specially, 'cause they cover the often requests. */ 49 r = run->runs; 50 if (vcn < r->vcn) { 51 *index = 0; 52 return false; 53 } 54 55 if (vcn < r->vcn + r->len) { 56 *index = 0; 57 return true; 58 } 59 60 r += max_idx; 61 if (vcn >= r->vcn + r->len) { 62 *index = run->count; 63 return false; 64 } 65 66 if (vcn >= r->vcn) { 67 *index = max_idx; 68 return true; 69 } 70 71 do { 72 mid_idx = min_idx + ((max_idx - min_idx) >> 1); 73 r = run->runs + mid_idx; 74 75 if (vcn < r->vcn) { 76 max_idx = mid_idx - 1; 77 if (!mid_idx) 78 break; 79 } else if (vcn >= r->vcn + r->len) { 80 min_idx = mid_idx + 1; 81 } else { 82 *index = mid_idx; 83 return true; 84 } 85 } while (min_idx <= max_idx); 86 87 *index = max_idx + 1; 88 return false; 89 } 90 91 /* 92 * run_consolidate - Consolidate runs starting from a given one. 93 */ 94 static void run_consolidate(struct runs_tree *run, size_t index) 95 { 96 size_t i; 97 struct ntfs_run *r = run->runs + index; 98 99 while (index + 1 < run->count) { 100 /* 101 * I should merge current run with next 102 * if start of the next run lies inside one being tested. 103 */ 104 struct ntfs_run *n = r + 1; 105 CLST end = r->vcn + r->len; 106 CLST dl; 107 108 /* Stop if runs are not aligned one to another. */ 109 if (n->vcn > end) 110 break; 111 112 dl = end - n->vcn; 113 114 /* 115 * If range at index overlaps with next one 116 * then I will either adjust it's start position 117 * or (if completely matches) dust remove one from the list. 118 */ 119 if (dl > 0) { 120 if (n->len <= dl) 121 goto remove_next_range; 122 123 n->len -= dl; 124 n->vcn += dl; 125 if (n->lcn != SPARSE_LCN) 126 n->lcn += dl; 127 dl = 0; 128 } 129 130 /* 131 * Stop if sparse mode does not match 132 * both current and next runs. 133 */ 134 if ((n->lcn == SPARSE_LCN) != (r->lcn == SPARSE_LCN)) { 135 index += 1; 136 r = n; 137 continue; 138 } 139 140 /* 141 * Check if volume block 142 * of a next run lcn does not match 143 * last volume block of the current run. 144 */ 145 if (n->lcn != SPARSE_LCN && n->lcn != r->lcn + r->len) 146 break; 147 148 /* 149 * Next and current are siblings. 150 * Eat/join. 151 */ 152 r->len += n->len - dl; 153 154 remove_next_range: 155 i = run->count - (index + 1); 156 if (i > 1) 157 memmove(n, n + 1, sizeof(*n) * (i - 1)); 158 159 run->count -= 1; 160 } 161 } 162 163 /* 164 * run_is_mapped_full 165 * 166 * Return: True if range [svcn - evcn] is mapped. 167 */ 168 bool run_is_mapped_full(const struct runs_tree *run, CLST svcn, CLST evcn) 169 { 170 size_t i; 171 const struct ntfs_run *r, *end; 172 CLST next_vcn; 173 174 if (!run_lookup(run, svcn, &i)) 175 return false; 176 177 end = run->runs + run->count; 178 r = run->runs + i; 179 180 for (;;) { 181 next_vcn = r->vcn + r->len; 182 if (next_vcn > evcn) 183 return true; 184 185 if (++r >= end) 186 return false; 187 188 if (r->vcn != next_vcn) 189 return false; 190 } 191 } 192 193 bool run_lookup_entry(const struct runs_tree *run, CLST vcn, CLST *lcn, 194 CLST *len, size_t *index) 195 { 196 size_t idx; 197 CLST gap; 198 struct ntfs_run *r; 199 200 /* Fail immediately if nrun was not touched yet. */ 201 if (!run->runs) 202 return false; 203 204 if (!run_lookup(run, vcn, &idx)) 205 return false; 206 207 r = run->runs + idx; 208 209 if (vcn >= r->vcn + r->len) 210 return false; 211 212 gap = vcn - r->vcn; 213 if (r->len <= gap) 214 return false; 215 216 *lcn = r->lcn == SPARSE_LCN ? SPARSE_LCN : (r->lcn + gap); 217 218 if (len) 219 *len = r->len - gap; 220 if (index) 221 *index = idx; 222 223 return true; 224 } 225 226 /* 227 * run_overlaps 228 * 229 * true if run overlaps with range [svcn, svcn + len) 230 */ 231 static bool run_overlaps(const struct runs_tree *run, CLST svcn, CLST len, 232 CLST *vcn, CLST *clen) 233 { 234 size_t i; 235 const struct ntfs_run *r = run->runs; 236 CLST end = svcn + len; 237 238 for (i = 0; i < run->count; i++, r++) { 239 /* Check if [r->vcn, r->vcn+r->len) overlaps [svcn, end). */ 240 if (r->vcn < end && svcn < r->vcn + r->len) { 241 if (vcn) 242 *vcn = r->vcn; 243 if (clen) 244 *clen = r->len; 245 return true; 246 } 247 } 248 249 return false; 250 } 251 252 /* 253 * run_lookup_entry_da 254 * 255 * - lookup vcn in delalloc run 256 * - lookup vcn in real run 257 * - correct result if real run overlaps with delalloc 258 */ 259 bool run_lookup_entry_da(const struct runs_tree *run, 260 const struct runs_tree *run_da, CLST vcn, CLST *lcn, 261 CLST *len) 262 { 263 CLST vcn1, len1; 264 265 if (run_da && run_lookup_entry(run_da, vcn, lcn, len, NULL)) { 266 *lcn = DELALLOC_LCN; 267 return true; 268 } 269 270 if (!run_lookup_entry(run, vcn, lcn, len, NULL)) 271 return false; 272 273 if (run_da && run_overlaps(run_da, vcn, *len, &vcn1, &len1)) { 274 /* Correct return value. */ 275 if (vcn1 > vcn) { 276 *len = vcn1 - vcn; 277 } else { 278 *lcn = DELALLOC_LCN; 279 *len = len1; 280 } 281 } 282 283 return true; 284 } 285 286 /* 287 * run_truncate_head - Decommit the range before vcn. 288 */ 289 void run_truncate_head(struct runs_tree *run, CLST vcn) 290 { 291 size_t index; 292 struct ntfs_run *r; 293 294 if (run_lookup(run, vcn, &index)) { 295 r = run->runs + index; 296 297 if (vcn > r->vcn) { 298 CLST dlen = vcn - r->vcn; 299 300 r->vcn = vcn; 301 r->len -= dlen; 302 if (r->lcn != SPARSE_LCN) 303 r->lcn += dlen; 304 } 305 306 if (!index) 307 return; 308 } 309 r = run->runs; 310 memmove(r, r + index, sizeof(*r) * (run->count - index)); 311 312 run->count -= index; 313 314 if (!run->count) { 315 kvfree(run->runs); 316 run->runs = NULL; 317 run->allocated = 0; 318 } 319 } 320 321 /* 322 * run_truncate - Decommit the range after vcn. 323 */ 324 void run_truncate(struct runs_tree *run, CLST vcn) 325 { 326 size_t index; 327 328 /* 329 * If I hit the range then 330 * I have to truncate one. 331 * If range to be truncated is becoming empty 332 * then it will entirely be removed. 333 */ 334 if (run_lookup(run, vcn, &index)) { 335 struct ntfs_run *r = run->runs + index; 336 337 r->len = vcn - r->vcn; 338 339 if (r->len > 0) 340 index += 1; 341 } 342 343 /* 344 * At this point 'index' is set to position that 345 * should be thrown away (including index itself) 346 * Simple one - just set the limit. 347 */ 348 run->count = index; 349 350 /* Do not reallocate array 'runs'. Only free if possible. */ 351 if (!index) { 352 kvfree(run->runs); 353 run->runs = NULL; 354 run->allocated = 0; 355 } 356 } 357 358 /* 359 * run_truncate_around - Trim head and tail if necessary. 360 */ 361 void run_truncate_around(struct runs_tree *run, CLST vcn) 362 { 363 run_truncate_head(run, vcn); 364 365 if (run->count >= NTFS3_RUN_MAX_BYTES / sizeof(struct ntfs_run) / 2) 366 run_truncate(run, (run->runs + (run->count >> 1))->vcn); 367 } 368 369 /* 370 * run_add_entry 371 * 372 * Sets location to known state. 373 * Run to be added may overlap with existing location. 374 * 375 * Return: false if of memory. 376 */ 377 bool run_add_entry(struct runs_tree *run, CLST vcn, CLST lcn, CLST len, 378 bool is_mft) 379 { 380 size_t used, index; 381 struct ntfs_run *r; 382 bool inrange; 383 CLST tail_vcn = 0, tail_len = 0, tail_lcn = 0; 384 bool should_add_tail = false; 385 386 /* 387 * Lookup the insertion point. 388 * 389 * Execute bsearch for the entry containing 390 * start position question. 391 */ 392 inrange = run_lookup(run, vcn, &index); 393 394 /* 395 * Shortcut here would be case of 396 * range not been found but one been added 397 * continues previous run. 398 * This case I can directly make use of 399 * existing range as my start point. 400 */ 401 if (!inrange && index > 0) { 402 struct ntfs_run *t = run->runs + index - 1; 403 404 if (t->vcn + t->len == vcn && 405 (t->lcn == SPARSE_LCN) == (lcn == SPARSE_LCN) && 406 (lcn == SPARSE_LCN || lcn == t->lcn + t->len)) { 407 inrange = true; 408 index -= 1; 409 } 410 } 411 412 /* 413 * At this point 'index' either points to the range 414 * containing start position or to the insertion position 415 * for a new range. 416 * So first let's check if range I'm probing is here already. 417 */ 418 if (!inrange) { 419 requires_new_range: 420 /* 421 * Range was not found. 422 * Insert at position 'index' 423 */ 424 used = run->count * sizeof(struct ntfs_run); 425 426 /* 427 * Check allocated space. 428 * If one is not enough to get one more entry 429 * then it will be reallocated. 430 */ 431 if (run->allocated < used + sizeof(struct ntfs_run)) { 432 size_t bytes; 433 struct ntfs_run *new_ptr; 434 435 /* Use power of 2 for 'bytes'. */ 436 if (!used) { 437 bytes = 64; 438 } else if (used <= 16 * PAGE_SIZE) { 439 if (is_power_of_2(run->allocated)) 440 bytes = run->allocated << 1; 441 else 442 bytes = (size_t)1 443 << (2 + blksize_bits(used)); 444 } else { 445 bytes = run->allocated + (16 * PAGE_SIZE); 446 } 447 448 WARN_ON(!is_mft && bytes > NTFS3_RUN_MAX_BYTES); 449 450 new_ptr = kvmalloc(bytes, GFP_KERNEL); 451 452 if (!new_ptr) 453 return false; 454 455 r = new_ptr + index; 456 memcpy(new_ptr, run->runs, 457 index * sizeof(struct ntfs_run)); 458 memcpy(r + 1, run->runs + index, 459 sizeof(struct ntfs_run) * (run->count - index)); 460 461 kvfree(run->runs); 462 run->runs = new_ptr; 463 run->allocated = bytes; 464 465 } else { 466 size_t i = run->count - index; 467 468 r = run->runs + index; 469 470 /* memmove appears to be a bottle neck here... */ 471 if (i > 0) 472 memmove(r + 1, r, sizeof(struct ntfs_run) * i); 473 } 474 475 r->vcn = vcn; 476 r->lcn = lcn; 477 r->len = len; 478 run->count += 1; 479 } else { 480 r = run->runs + index; 481 482 /* 483 * If one of ranges was not allocated then we 484 * have to split location we just matched and 485 * insert current one. 486 * A common case this requires tail to be reinserted 487 * a recursive call. 488 */ 489 if (((lcn == SPARSE_LCN) != (r->lcn == SPARSE_LCN)) || 490 (lcn != SPARSE_LCN && lcn != r->lcn + (vcn - r->vcn))) { 491 CLST to_eat = vcn - r->vcn; 492 CLST Tovcn = to_eat + len; 493 494 should_add_tail = Tovcn < r->len; 495 496 if (should_add_tail) { 497 tail_lcn = r->lcn == SPARSE_LCN ? 498 SPARSE_LCN : 499 (r->lcn + Tovcn); 500 tail_vcn = r->vcn + Tovcn; 501 tail_len = r->len - Tovcn; 502 } 503 504 if (to_eat > 0) { 505 r->len = to_eat; 506 inrange = false; 507 index += 1; 508 goto requires_new_range; 509 } 510 511 /* lcn should match one were going to add. */ 512 r->lcn = lcn; 513 } 514 515 /* 516 * If existing range fits then were done. 517 * Otherwise extend found one and fall back to range join code. 518 */ 519 if (r->vcn + r->len < vcn + len) 520 r->len += len - ((r->vcn + r->len) - vcn); 521 } 522 523 /* 524 * And normalize it starting from insertion point. 525 * It's possible that no insertion needed case if 526 * start point lies within the range of an entry 527 * that 'index' points to. 528 */ 529 if (inrange && index > 0) 530 index -= 1; 531 run_consolidate(run, index); 532 run_consolidate(run, index + 1); 533 534 /* 535 * A special case. 536 * We have to add extra range a tail. 537 */ 538 if (should_add_tail && 539 !run_add_entry(run, tail_vcn, tail_lcn, tail_len, is_mft)) 540 return false; 541 542 return true; 543 } 544 545 /* 546 * run_collapse_range 547 * 548 * Helper for attr_collapse_range(), 549 * which is helper for fallocate(collapse_range). 550 */ 551 bool run_collapse_range(struct runs_tree *run, CLST vcn, CLST len, CLST sub) 552 { 553 size_t index, eat; 554 struct ntfs_run *r, *e, *eat_start, *eat_end; 555 CLST end; 556 557 if (!run_lookup(run, vcn, &index) && index >= run->count) { 558 return true; 559 } 560 561 e = run->runs + run->count; 562 r = run->runs + index; 563 end = vcn + len; 564 565 if (vcn > r->vcn) { 566 if (r->vcn + r->len <= end) { 567 /* Collapse tail of run .*/ 568 r->len = vcn - r->vcn; 569 } else if (r->lcn == SPARSE_LCN) { 570 /* Collapse a middle part of sparsed run. */ 571 r->len -= len; 572 } else { 573 /* Collapse a middle part of normal run, split. */ 574 if (!run_add_entry(run, vcn, SPARSE_LCN, len, false)) 575 return false; 576 return run_collapse_range(run, vcn, len, sub); 577 } 578 579 r += 1; 580 } 581 582 eat_start = r; 583 eat_end = r; 584 585 for (; r < e; r++) { 586 CLST d; 587 588 if (r->vcn >= end) { 589 r->vcn -= len; 590 continue; 591 } 592 593 if (r->vcn + r->len <= end) { 594 /* Eat this run. */ 595 eat_end = r + 1; 596 continue; 597 } 598 599 d = end - r->vcn; 600 if (r->lcn != SPARSE_LCN) 601 r->lcn += d; 602 r->len -= d; 603 r->vcn -= len - d; 604 } 605 606 eat = eat_end - eat_start; 607 memmove(eat_start, eat_end, (e - eat_end) * sizeof(*r)); 608 run->count -= eat; 609 610 if (sub) { 611 e -= eat; 612 for (r = run->runs; r < e; r++) { 613 r->vcn -= sub; 614 } 615 } 616 617 return true; 618 } 619 620 /* run_insert_range 621 * 622 * Helper for attr_insert_range(), 623 * which is helper for fallocate(insert_range). 624 */ 625 int run_insert_range(struct runs_tree *run, CLST vcn, CLST len) 626 { 627 size_t index; 628 struct ntfs_run *r, *e; 629 630 if (WARN_ON(!run_lookup(run, vcn, &index))) 631 return -EINVAL; /* Should never be here. */ 632 633 e = run->runs + run->count; 634 r = run->runs + index; 635 636 if (vcn > r->vcn) 637 r += 1; 638 639 for (; r < e; r++) 640 r->vcn += len; 641 642 r = run->runs + index; 643 644 if (vcn > r->vcn) { 645 /* split fragment. */ 646 CLST len1 = vcn - r->vcn; 647 CLST len2 = r->len - len1; 648 CLST lcn2 = r->lcn == SPARSE_LCN ? SPARSE_LCN : (r->lcn + len1); 649 650 r->len = len1; 651 652 if (!run_add_entry(run, vcn + len, lcn2, len2, false)) 653 return -ENOMEM; 654 } 655 656 if (!run_add_entry(run, vcn, SPARSE_LCN, len, false)) 657 return -ENOMEM; 658 659 return 0; 660 } 661 662 /* run_insert_range_da 663 * 664 * Helper for attr_insert_range(), 665 * which is helper for fallocate(insert_range). 666 */ 667 int run_insert_range_da(struct runs_tree *run, CLST vcn, CLST len) 668 { 669 struct ntfs_run *r, *r0 = NULL, *e = run->runs + run->count; 670 ; 671 672 for (r = run->runs; r < e; r++) { 673 CLST end = r->vcn + r->len; 674 675 if (vcn >= end) 676 continue; 677 678 if (!r0 && r->vcn < vcn) { 679 r0 = r; 680 } else { 681 r->vcn += len; 682 } 683 } 684 685 if (r0) { 686 /* split fragment. */ 687 CLST len1 = vcn - r0->vcn; 688 CLST len2 = r0->len - len1; 689 690 r0->len = len1; 691 if (!run_add_entry(run, vcn + len, SPARSE_LCN, len2, false)) 692 return -ENOMEM; 693 } 694 695 return 0; 696 } 697 698 /* 699 * run_get_entry - Return index-th mapped region. 700 */ 701 bool run_get_entry(const struct runs_tree *run, size_t index, CLST *vcn, 702 CLST *lcn, CLST *len) 703 { 704 const struct ntfs_run *r; 705 706 if (index >= run->count) 707 return false; 708 709 r = run->runs + index; 710 711 if (!r->len) 712 return false; 713 714 if (vcn) 715 *vcn = r->vcn; 716 if (lcn) 717 *lcn = r->lcn; 718 if (len) 719 *len = r->len; 720 return true; 721 } 722 723 /* 724 * run_packed_size - Calculate the size of packed int64. 725 */ 726 #ifdef __BIG_ENDIAN 727 static inline int run_packed_size(const s64 n) 728 { 729 const u8 *p = (const u8 *)&n + sizeof(n) - 1; 730 731 if (n >= 0) { 732 if (p[-7] || p[-6] || p[-5] || p[-4]) 733 p -= 4; 734 if (p[-3] || p[-2]) 735 p -= 2; 736 if (p[-1]) 737 p -= 1; 738 if (p[0] & 0x80) 739 p -= 1; 740 } else { 741 if (p[-7] != 0xff || p[-6] != 0xff || p[-5] != 0xff || 742 p[-4] != 0xff) 743 p -= 4; 744 if (p[-3] != 0xff || p[-2] != 0xff) 745 p -= 2; 746 if (p[-1] != 0xff) 747 p -= 1; 748 if (!(p[0] & 0x80)) 749 p -= 1; 750 } 751 return (const u8 *)&n + sizeof(n) - p; 752 } 753 754 /* Full trusted function. It does not check 'size' for errors. */ 755 static inline void run_pack_s64(u8 *run_buf, u8 size, s64 v) 756 { 757 const u8 *p = (u8 *)&v; 758 759 switch (size) { 760 case 8: 761 run_buf[7] = p[0]; 762 fallthrough; 763 case 7: 764 run_buf[6] = p[1]; 765 fallthrough; 766 case 6: 767 run_buf[5] = p[2]; 768 fallthrough; 769 case 5: 770 run_buf[4] = p[3]; 771 fallthrough; 772 case 4: 773 run_buf[3] = p[4]; 774 fallthrough; 775 case 3: 776 run_buf[2] = p[5]; 777 fallthrough; 778 case 2: 779 run_buf[1] = p[6]; 780 fallthrough; 781 case 1: 782 run_buf[0] = p[7]; 783 } 784 } 785 786 /* Full trusted function. It does not check 'size' for errors. */ 787 static inline s64 run_unpack_s64(const u8 *run_buf, u8 size, s64 v) 788 { 789 u8 *p = (u8 *)&v; 790 791 switch (size) { 792 case 8: 793 p[0] = run_buf[7]; 794 fallthrough; 795 case 7: 796 p[1] = run_buf[6]; 797 fallthrough; 798 case 6: 799 p[2] = run_buf[5]; 800 fallthrough; 801 case 5: 802 p[3] = run_buf[4]; 803 fallthrough; 804 case 4: 805 p[4] = run_buf[3]; 806 fallthrough; 807 case 3: 808 p[5] = run_buf[2]; 809 fallthrough; 810 case 2: 811 p[6] = run_buf[1]; 812 fallthrough; 813 case 1: 814 p[7] = run_buf[0]; 815 } 816 return v; 817 } 818 819 #else 820 821 static inline int run_packed_size(const s64 n) 822 { 823 const u8 *p = (const u8 *)&n; 824 825 if (n >= 0) { 826 if (p[7] || p[6] || p[5] || p[4]) 827 p += 4; 828 if (p[3] || p[2]) 829 p += 2; 830 if (p[1]) 831 p += 1; 832 if (p[0] & 0x80) 833 p += 1; 834 } else { 835 if (p[7] != 0xff || p[6] != 0xff || p[5] != 0xff || 836 p[4] != 0xff) 837 p += 4; 838 if (p[3] != 0xff || p[2] != 0xff) 839 p += 2; 840 if (p[1] != 0xff) 841 p += 1; 842 if (!(p[0] & 0x80)) 843 p += 1; 844 } 845 846 return 1 + p - (const u8 *)&n; 847 } 848 849 /* Full trusted function. It does not check 'size' for errors. */ 850 static inline void run_pack_s64(u8 *run_buf, u8 size, s64 v) 851 { 852 const u8 *p = (u8 *)&v; 853 854 /* memcpy( run_buf, &v, size); Is it faster? */ 855 switch (size) { 856 case 8: 857 run_buf[7] = p[7]; 858 fallthrough; 859 case 7: 860 run_buf[6] = p[6]; 861 fallthrough; 862 case 6: 863 run_buf[5] = p[5]; 864 fallthrough; 865 case 5: 866 run_buf[4] = p[4]; 867 fallthrough; 868 case 4: 869 run_buf[3] = p[3]; 870 fallthrough; 871 case 3: 872 run_buf[2] = p[2]; 873 fallthrough; 874 case 2: 875 run_buf[1] = p[1]; 876 fallthrough; 877 case 1: 878 run_buf[0] = p[0]; 879 } 880 } 881 882 /* full trusted function. It does not check 'size' for errors */ 883 static inline s64 run_unpack_s64(const u8 *run_buf, u8 size, s64 v) 884 { 885 u8 *p = (u8 *)&v; 886 887 /* memcpy( &v, run_buf, size); Is it faster? */ 888 switch (size) { 889 case 8: 890 p[7] = run_buf[7]; 891 fallthrough; 892 case 7: 893 p[6] = run_buf[6]; 894 fallthrough; 895 case 6: 896 p[5] = run_buf[5]; 897 fallthrough; 898 case 5: 899 p[4] = run_buf[4]; 900 fallthrough; 901 case 4: 902 p[3] = run_buf[3]; 903 fallthrough; 904 case 3: 905 p[2] = run_buf[2]; 906 fallthrough; 907 case 2: 908 p[1] = run_buf[1]; 909 fallthrough; 910 case 1: 911 p[0] = run_buf[0]; 912 } 913 return v; 914 } 915 #endif 916 917 /* 918 * run_pack - Pack runs into buffer. 919 * 920 * packed_vcns - How much runs we have packed. 921 * packed_size - How much bytes we have used run_buf. 922 */ 923 int run_pack(const struct runs_tree *run, CLST svcn, CLST len, u8 *run_buf, 924 u32 run_buf_size, CLST *packed_vcns) 925 { 926 CLST next_vcn, vcn, lcn; 927 CLST prev_lcn = 0; 928 CLST evcn1 = svcn + len; 929 const struct ntfs_run *r, *r_end; 930 int packed_size = 0; 931 size_t i; 932 s64 dlcn; 933 int offset_size, size_size, tmp; 934 935 *packed_vcns = 0; 936 937 if (!len) 938 goto out; 939 940 /* Check all required entries [svcn, encv1) available. */ 941 if (!run_lookup(run, svcn, &i)) 942 return -ENOENT; 943 944 r_end = run->runs + run->count; 945 r = run->runs + i; 946 947 for (next_vcn = r->vcn + r->len; next_vcn < evcn1; 948 next_vcn = r->vcn + r->len) { 949 if (++r >= r_end || r->vcn != next_vcn) 950 return -ENOENT; 951 } 952 953 /* Repeat cycle above and pack runs. Assume no errors. */ 954 r = run->runs + i; 955 len = svcn - r->vcn; 956 vcn = svcn; 957 lcn = r->lcn == SPARSE_LCN ? SPARSE_LCN : (r->lcn + len); 958 len = r->len - len; 959 960 for (;;) { 961 next_vcn = vcn + len; 962 if (next_vcn > evcn1) 963 len = evcn1 - vcn; 964 965 /* How much bytes required to pack len. */ 966 size_size = run_packed_size(len); 967 968 /* offset_size - How much bytes is packed dlcn. */ 969 if (lcn == SPARSE_LCN) { 970 offset_size = 0; 971 dlcn = 0; 972 } else { 973 /* NOTE: lcn can be less than prev_lcn! */ 974 dlcn = (s64)lcn - prev_lcn; 975 offset_size = run_packed_size(dlcn); 976 prev_lcn = lcn; 977 } 978 979 tmp = run_buf_size - packed_size - 2 - offset_size; 980 if (tmp <= 0) 981 goto out; 982 983 /* Can we store this entire run. */ 984 if (tmp < size_size) 985 goto out; 986 987 if (run_buf) { 988 /* Pack run header. */ 989 run_buf[0] = ((u8)(size_size | (offset_size << 4))); 990 run_buf += 1; 991 992 /* Pack the length of run. */ 993 run_pack_s64(run_buf, size_size, len); 994 995 run_buf += size_size; 996 /* Pack the offset from previous LCN. */ 997 run_pack_s64(run_buf, offset_size, dlcn); 998 run_buf += offset_size; 999 } 1000 1001 packed_size += 1 + offset_size + size_size; 1002 *packed_vcns += len; 1003 1004 if (packed_size + 1 >= run_buf_size || next_vcn >= evcn1) 1005 goto out; 1006 1007 r += 1; 1008 vcn = r->vcn; 1009 lcn = r->lcn; 1010 len = r->len; 1011 } 1012 1013 out: 1014 /* Store last zero. */ 1015 if (run_buf) 1016 run_buf[0] = 0; 1017 1018 return packed_size + 1; 1019 } 1020 1021 /* 1022 * run_unpack - Unpack packed runs from @run_buf. 1023 * 1024 * Return: Error if negative, or real used bytes. 1025 */ 1026 int run_unpack(struct runs_tree *run, struct ntfs_sb_info *sbi, CLST ino, 1027 CLST svcn, CLST evcn, CLST vcn, const u8 *run_buf, 1028 int run_buf_size) 1029 { 1030 u64 prev_lcn, vcn64, lcn, next_vcn; 1031 const u8 *run_last, *run_0; 1032 bool is_mft = ino == MFT_REC_MFT; 1033 1034 if (run_buf_size < 0) 1035 return -EINVAL; 1036 1037 /* Check for empty. */ 1038 if (evcn + 1 == svcn) 1039 return 0; 1040 1041 if (evcn < svcn) 1042 return -EINVAL; 1043 1044 run_0 = run_buf; 1045 run_last = run_buf + run_buf_size; 1046 prev_lcn = 0; 1047 vcn64 = svcn; 1048 1049 /* Read all runs the chain. */ 1050 /* size_size - How much bytes is packed len. */ 1051 while (run_buf < run_last) { 1052 /* size_size - How much bytes is packed len. */ 1053 u8 size_size = *run_buf & 0xF; 1054 /* offset_size - How much bytes is packed dlcn. */ 1055 u8 offset_size = *run_buf++ >> 4; 1056 u64 len; 1057 1058 if (!size_size) 1059 break; 1060 1061 /* 1062 * Unpack runs. 1063 * NOTE: Runs are stored little endian order 1064 * "len" is unsigned value, "dlcn" is signed. 1065 * Large positive number requires to store 5 bytes 1066 * e.g.: 05 FF 7E FF FF 00 00 00 1067 */ 1068 if (size_size > sizeof(len)) 1069 return -EINVAL; 1070 1071 if (run_buf + size_size > run_last) 1072 return -EINVAL; 1073 1074 len = run_unpack_s64(run_buf, size_size, 0); 1075 /* Skip size_size. */ 1076 run_buf += size_size; 1077 1078 if (!len) 1079 return -EINVAL; 1080 1081 if (!offset_size) 1082 lcn = SPARSE_LCN64; 1083 else if (offset_size <= sizeof(s64)) { 1084 s64 dlcn; 1085 1086 if (run_buf + offset_size > run_last) 1087 return -EINVAL; 1088 1089 /* Initial value of dlcn is -1 or 0. */ 1090 dlcn = (run_buf[offset_size - 1] & 0x80) ? (s64)-1 : 0; 1091 dlcn = run_unpack_s64(run_buf, offset_size, dlcn); 1092 /* Skip offset_size. */ 1093 run_buf += offset_size; 1094 1095 if (!dlcn) 1096 return -EINVAL; 1097 1098 /* Check special combination: 0 + SPARSE_LCN64. */ 1099 if (!prev_lcn && dlcn == SPARSE_LCN64) { 1100 lcn = SPARSE_LCN64; 1101 } else if (check_add_overflow(prev_lcn, dlcn, &lcn)) { 1102 return -EINVAL; 1103 } 1104 prev_lcn = lcn; 1105 } else { 1106 /* The size of 'dlcn' can't be > 8. */ 1107 return -EINVAL; 1108 } 1109 1110 if (check_add_overflow(vcn64, len, &next_vcn)) 1111 return -EINVAL; 1112 1113 /* Check boundary. */ 1114 if (next_vcn > evcn + 1) 1115 return -EINVAL; 1116 1117 #ifndef CONFIG_NTFS3_64BIT_CLUSTER 1118 if (next_vcn > 0x100000000ull || (lcn + len) > 0x100000000ull) { 1119 ntfs_err( 1120 sbi->sb, 1121 "This driver is compiled without CONFIG_NTFS3_64BIT_CLUSTER (like windows driver).\n" 1122 "Volume contains 64 bits run: vcn %llx, lcn %llx, len %llx.\n" 1123 "Activate CONFIG_NTFS3_64BIT_CLUSTER to process this case", 1124 vcn64, lcn, len); 1125 return -EOPNOTSUPP; 1126 } 1127 #endif 1128 if (lcn != SPARSE_LCN64) { 1129 u64 lcn_end; 1130 1131 if (check_add_overflow(lcn, len, &lcn_end)) 1132 return -EINVAL; 1133 if (lcn_end > sbi->used.bitmap.nbits) { 1134 /* LCN range is out of volume. */ 1135 return -EINVAL; 1136 } 1137 } 1138 1139 if (!run) 1140 ; /* Called from check_attr(fslog.c) to check run. */ 1141 else if (run == RUN_DEALLOCATE) { 1142 /* 1143 * Called from ni_delete_all to free clusters 1144 * without storing in run. 1145 */ 1146 if (lcn != SPARSE_LCN64) 1147 mark_as_free_ex(sbi, lcn, len, true); 1148 } else if (vcn64 >= vcn) { 1149 if (!run_add_entry(run, vcn64, lcn, len, is_mft)) 1150 return -ENOMEM; 1151 } else if (next_vcn > vcn) { 1152 u64 dlen = vcn - vcn64; 1153 1154 if (!run_add_entry(run, vcn, lcn + dlen, len - dlen, 1155 is_mft)) 1156 return -ENOMEM; 1157 } 1158 1159 vcn64 = next_vcn; 1160 } 1161 1162 if (vcn64 != evcn + 1) { 1163 /* Not expected length of unpacked runs. */ 1164 return -EINVAL; 1165 } 1166 1167 return run_buf - run_0; 1168 } 1169 1170 #ifdef NTFS3_CHECK_FREE_CLST 1171 /* 1172 * run_unpack_ex - Unpack packed runs from "run_buf". 1173 * 1174 * Checks unpacked runs to be used in bitmap. 1175 * 1176 * Return: Error if negative, or real used bytes. 1177 */ 1178 int run_unpack_ex(struct runs_tree *run, struct ntfs_sb_info *sbi, CLST ino, 1179 CLST svcn, CLST evcn, CLST vcn, const u8 *run_buf, 1180 int run_buf_size) 1181 { 1182 int ret, err; 1183 CLST next_vcn, lcn, len; 1184 size_t index, done; 1185 bool ok, zone; 1186 struct wnd_bitmap *wnd; 1187 1188 ret = run_unpack(run, sbi, ino, svcn, evcn, vcn, run_buf, run_buf_size); 1189 if (ret <= 0) 1190 return ret; 1191 1192 if (!sbi->used.bitmap.sb || !run || run == RUN_DEALLOCATE) 1193 return ret; 1194 1195 if (ino == MFT_REC_BADCLUST) 1196 return ret; 1197 1198 next_vcn = vcn = svcn; 1199 wnd = &sbi->used.bitmap; 1200 1201 for (ok = run_lookup_entry(run, vcn, &lcn, &len, &index); 1202 next_vcn <= evcn; 1203 ok = run_get_entry(run, ++index, &vcn, &lcn, &len)) { 1204 if (!ok || next_vcn != vcn) 1205 return -EINVAL; 1206 1207 next_vcn = vcn + len; 1208 1209 if (lcn == SPARSE_LCN) 1210 continue; 1211 1212 if (sbi->flags & NTFS_FLAGS_NEED_REPLAY) 1213 continue; 1214 1215 down_read_nested(&wnd->rw_lock, BITMAP_MUTEX_CLUSTERS); 1216 zone = max(wnd->zone_bit, lcn) < min(wnd->zone_end, lcn + len); 1217 /* Check for free blocks. */ 1218 ok = !zone && wnd_is_used(wnd, lcn, len); 1219 up_read(&wnd->rw_lock); 1220 if (ok) 1221 continue; 1222 1223 /* Looks like volume is corrupted. */ 1224 ntfs_set_state(sbi, NTFS_DIRTY_ERROR); 1225 1226 if (!down_write_trylock(&wnd->rw_lock)) 1227 continue; 1228 1229 if (zone) { 1230 /* 1231 * Range [lcn, lcn + len) intersects with zone. 1232 * To avoid complex with zone just turn it off. 1233 */ 1234 wnd_zone_set(wnd, 0, 0); 1235 } 1236 1237 /* Mark all zero bits as used in range [lcn, lcn+len). */ 1238 err = wnd_set_used_safe(wnd, lcn, len, &done); 1239 if (zone) { 1240 /* Restore zone. Lock mft run. */ 1241 struct rw_semaphore *lock = 1242 is_mounted(sbi) ? &sbi->mft.ni->file.run_lock : 1243 NULL; 1244 if (lock) { 1245 if (down_read_trylock(lock)) { 1246 ntfs_refresh_zone(sbi); 1247 up_read(lock); 1248 } 1249 } else { 1250 ntfs_refresh_zone(sbi); 1251 } 1252 } 1253 up_write(&wnd->rw_lock); 1254 if (err) 1255 return err; 1256 } 1257 1258 return ret; 1259 } 1260 #endif 1261 1262 /* 1263 * run_get_highest_vcn 1264 * 1265 * Return the highest vcn from a mapping pairs array 1266 * it used while replaying log file. 1267 */ 1268 int run_get_highest_vcn(CLST vcn, const u8 *run_buf, size_t run_buf_size, 1269 u64 *highest_vcn) 1270 { 1271 const u8 *run_last = run_buf + run_buf_size; 1272 u64 vcn64 = vcn; 1273 u8 size_size; 1274 1275 while (run_buf < run_last && (size_size = *run_buf & 0xF)) { 1276 u8 offset_size = *run_buf++ >> 4; 1277 u64 len; 1278 1279 if (size_size > 8 || offset_size > 8) 1280 return -EINVAL; 1281 1282 if (run_buf + size_size + offset_size > run_last) 1283 return -EINVAL; 1284 1285 len = run_unpack_s64(run_buf, size_size, 0); 1286 if (!len) 1287 return -EINVAL; 1288 1289 run_buf += size_size + offset_size; 1290 if (check_add_overflow(vcn64, len, &vcn64)) 1291 return -EINVAL; 1292 1293 #ifndef CONFIG_NTFS3_64BIT_CLUSTER 1294 if (vcn64 > 0x100000000ull) 1295 return -EINVAL; 1296 #endif 1297 } 1298 1299 *highest_vcn = vcn64 - 1; 1300 return 0; 1301 } 1302 1303 /* 1304 * run_clone 1305 * 1306 * Make a copy of run 1307 */ 1308 int run_clone(const struct runs_tree *run, struct runs_tree *new_run) 1309 { 1310 size_t bytes = run->count * sizeof(struct ntfs_run); 1311 1312 if (bytes > new_run->allocated) { 1313 struct ntfs_run *new_ptr = kvmalloc(bytes, GFP_KERNEL); 1314 1315 if (!new_ptr) 1316 return -ENOMEM; 1317 1318 kvfree(new_run->runs); 1319 new_run->runs = new_ptr; 1320 new_run->allocated = bytes; 1321 } 1322 1323 memcpy(new_run->runs, run->runs, bytes); 1324 new_run->count = run->count; 1325 return 0; 1326 } 1327 1328 /* 1329 * run_remove_range 1330 * 1331 */ 1332 bool run_remove_range(struct runs_tree *run, CLST vcn, CLST len, CLST *done) 1333 { 1334 size_t index, eat; 1335 struct ntfs_run *r, *e, *eat_start, *eat_end; 1336 CLST end, d; 1337 1338 *done = 0; 1339 1340 /* Fast check. */ 1341 if (!run->count) 1342 return true; 1343 1344 if (!run_lookup(run, vcn, &index) && index >= run->count) { 1345 /* No entries in this run. */ 1346 return true; 1347 } 1348 1349 e = run->runs + run->count; 1350 r = run->runs + index; 1351 end = vcn + len; 1352 1353 if (vcn > r->vcn) { 1354 CLST r_end = r->vcn + r->len; 1355 d = vcn - r->vcn; 1356 1357 if (r_end > end) { 1358 /* Remove a middle part, split. */ 1359 CLST tail_lcn = r->lcn == SPARSE_LCN ? 1360 SPARSE_LCN : 1361 (r->lcn + (end - r->vcn)); 1362 1363 *done += len; 1364 r->len = d; 1365 return run_add_entry(run, end, tail_lcn, r_end - end, 1366 false); 1367 } 1368 /* Remove tail of run .*/ 1369 *done += r->len - d; 1370 r->len = d; 1371 r += 1; 1372 } 1373 1374 eat_start = r; 1375 eat_end = r; 1376 1377 for (; r < e; r++) { 1378 if (r->vcn >= end) 1379 continue; 1380 1381 if (r->vcn + r->len <= end) { 1382 /* Eat this run. */ 1383 *done += r->len; 1384 eat_end = r + 1; 1385 continue; 1386 } 1387 1388 d = end - r->vcn; 1389 *done += d; 1390 if (r->lcn != SPARSE_LCN) 1391 r->lcn += d; 1392 r->len -= d; 1393 r->vcn = end; 1394 } 1395 1396 eat = eat_end - eat_start; 1397 memmove(eat_start, eat_end, (e - eat_end) * sizeof(*r)); 1398 run->count -= eat; 1399 1400 return true; 1401 } 1402 1403 CLST run_len(const struct runs_tree *run) 1404 { 1405 const struct ntfs_run *r, *e; 1406 CLST len = 0; 1407 1408 for (r = run->runs, e = r + run->count; r < e; r++) { 1409 len += r->len; 1410 } 1411 1412 return len; 1413 } 1414 1415 CLST run_get_max_vcn(const struct runs_tree *run) 1416 { 1417 const struct ntfs_run *r; 1418 if (!run->count) 1419 return 0; 1420 1421 r = run->runs + run->count - 1; 1422 return r->vcn + r->len; 1423 } 1424