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