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 len = run_unpack_s64(run_buf, size_size, 0); 1012 /* Skip size_size. */ 1013 run_buf += size_size; 1014 1015 if (!len) 1016 return -EINVAL; 1017 1018 if (!offset_size) 1019 lcn = SPARSE_LCN64; 1020 else if (offset_size <= sizeof(s64)) { 1021 s64 dlcn; 1022 1023 /* Initial value of dlcn is -1 or 0. */ 1024 dlcn = (run_buf[offset_size - 1] & 0x80) ? (s64)-1 : 0; 1025 dlcn = run_unpack_s64(run_buf, offset_size, dlcn); 1026 /* Skip offset_size. */ 1027 run_buf += offset_size; 1028 1029 if (!dlcn) 1030 return -EINVAL; 1031 1032 /* Check special combination: 0 + SPARSE_LCN64. */ 1033 if (!prev_lcn && dlcn == SPARSE_LCN64) { 1034 lcn = SPARSE_LCN64; 1035 } else if (check_add_overflow(prev_lcn, dlcn, &lcn)) { 1036 return -EINVAL; 1037 } 1038 prev_lcn = lcn; 1039 } else { 1040 /* The size of 'dlcn' can't be > 8. */ 1041 return -EINVAL; 1042 } 1043 1044 if (check_add_overflow(vcn64, len, &next_vcn)) 1045 return -EINVAL; 1046 1047 /* Check boundary. */ 1048 if (next_vcn > evcn + 1) 1049 return -EINVAL; 1050 1051 #ifndef CONFIG_NTFS3_64BIT_CLUSTER 1052 if (next_vcn > 0x100000000ull || (lcn + len) > 0x100000000ull) { 1053 ntfs_err( 1054 sbi->sb, 1055 "This driver is compiled without CONFIG_NTFS3_64BIT_CLUSTER (like windows driver).\n" 1056 "Volume contains 64 bits run: vcn %llx, lcn %llx, len %llx.\n" 1057 "Activate CONFIG_NTFS3_64BIT_CLUSTER to process this case", 1058 vcn64, lcn, len); 1059 return -EOPNOTSUPP; 1060 } 1061 #endif 1062 if (lcn != SPARSE_LCN64 && lcn + len > sbi->used.bitmap.nbits) { 1063 /* LCN range is out of volume. */ 1064 return -EINVAL; 1065 } 1066 1067 if (!run) 1068 ; /* Called from check_attr(fslog.c) to check run. */ 1069 else if (run == RUN_DEALLOCATE) { 1070 /* 1071 * Called from ni_delete_all to free clusters 1072 * without storing in run. 1073 */ 1074 if (lcn != SPARSE_LCN64) 1075 mark_as_free_ex(sbi, lcn, len, true); 1076 } else if (vcn64 >= vcn) { 1077 if (!run_add_entry(run, vcn64, lcn, len, is_mft)) 1078 return -ENOMEM; 1079 } else if (next_vcn > vcn) { 1080 u64 dlen = vcn - vcn64; 1081 1082 if (!run_add_entry(run, vcn, lcn + dlen, len - dlen, 1083 is_mft)) 1084 return -ENOMEM; 1085 } 1086 1087 vcn64 = next_vcn; 1088 } 1089 1090 if (vcn64 != evcn + 1) { 1091 /* Not expected length of unpacked runs. */ 1092 return -EINVAL; 1093 } 1094 1095 return run_buf - run_0; 1096 } 1097 1098 #ifdef NTFS3_CHECK_FREE_CLST 1099 /* 1100 * run_unpack_ex - Unpack packed runs from "run_buf". 1101 * 1102 * Checks unpacked runs to be used in bitmap. 1103 * 1104 * Return: Error if negative, or real used bytes. 1105 */ 1106 int run_unpack_ex(struct runs_tree *run, struct ntfs_sb_info *sbi, CLST ino, 1107 CLST svcn, CLST evcn, CLST vcn, const u8 *run_buf, 1108 int run_buf_size) 1109 { 1110 int ret, err; 1111 CLST next_vcn, lcn, len; 1112 size_t index, done; 1113 bool ok, zone; 1114 struct wnd_bitmap *wnd; 1115 1116 ret = run_unpack(run, sbi, ino, svcn, evcn, vcn, run_buf, run_buf_size); 1117 if (ret <= 0) 1118 return ret; 1119 1120 if (!sbi->used.bitmap.sb || !run || run == RUN_DEALLOCATE) 1121 return ret; 1122 1123 if (ino == MFT_REC_BADCLUST) 1124 return ret; 1125 1126 next_vcn = vcn = svcn; 1127 wnd = &sbi->used.bitmap; 1128 1129 for (ok = run_lookup_entry(run, vcn, &lcn, &len, &index); 1130 next_vcn <= evcn; 1131 ok = run_get_entry(run, ++index, &vcn, &lcn, &len)) { 1132 if (!ok || next_vcn != vcn) 1133 return -EINVAL; 1134 1135 next_vcn = vcn + len; 1136 1137 if (lcn == SPARSE_LCN) 1138 continue; 1139 1140 if (sbi->flags & NTFS_FLAGS_NEED_REPLAY) 1141 continue; 1142 1143 down_read_nested(&wnd->rw_lock, BITMAP_MUTEX_CLUSTERS); 1144 zone = max(wnd->zone_bit, lcn) < min(wnd->zone_end, lcn + len); 1145 /* Check for free blocks. */ 1146 ok = !zone && wnd_is_used(wnd, lcn, len); 1147 up_read(&wnd->rw_lock); 1148 if (ok) 1149 continue; 1150 1151 /* Looks like volume is corrupted. */ 1152 ntfs_set_state(sbi, NTFS_DIRTY_ERROR); 1153 1154 if (!down_write_trylock(&wnd->rw_lock)) 1155 continue; 1156 1157 if (zone) { 1158 /* 1159 * Range [lcn, lcn + len) intersects with zone. 1160 * To avoid complex with zone just turn it off. 1161 */ 1162 wnd_zone_set(wnd, 0, 0); 1163 } 1164 1165 /* Mark all zero bits as used in range [lcn, lcn+len). */ 1166 err = wnd_set_used_safe(wnd, lcn, len, &done); 1167 if (zone) { 1168 /* Restore zone. Lock mft run. */ 1169 struct rw_semaphore *lock = 1170 is_mounted(sbi) ? &sbi->mft.ni->file.run_lock : 1171 NULL; 1172 if (lock) { 1173 if (down_read_trylock(lock)) { 1174 ntfs_refresh_zone(sbi); 1175 up_read(lock); 1176 } 1177 } else { 1178 ntfs_refresh_zone(sbi); 1179 } 1180 } 1181 up_write(&wnd->rw_lock); 1182 if (err) 1183 return err; 1184 } 1185 1186 return ret; 1187 } 1188 #endif 1189 1190 /* 1191 * run_get_highest_vcn 1192 * 1193 * Return the highest vcn from a mapping pairs array 1194 * it used while replaying log file. 1195 */ 1196 int run_get_highest_vcn(CLST vcn, const u8 *run_buf, u64 *highest_vcn) 1197 { 1198 u64 vcn64 = vcn; 1199 u8 size_size; 1200 1201 while ((size_size = *run_buf & 0xF)) { 1202 u8 offset_size = *run_buf++ >> 4; 1203 u64 len; 1204 1205 if (size_size > 8 || offset_size > 8) 1206 return -EINVAL; 1207 1208 len = run_unpack_s64(run_buf, size_size, 0); 1209 if (!len) 1210 return -EINVAL; 1211 1212 run_buf += size_size + offset_size; 1213 if (check_add_overflow(vcn64, len, &vcn64)) 1214 return -EINVAL; 1215 1216 #ifndef CONFIG_NTFS3_64BIT_CLUSTER 1217 if (vcn64 > 0x100000000ull) 1218 return -EINVAL; 1219 #endif 1220 } 1221 1222 *highest_vcn = vcn64 - 1; 1223 return 0; 1224 } 1225 1226 /* 1227 * run_clone 1228 * 1229 * Make a copy of run 1230 */ 1231 int run_clone(const struct runs_tree *run, struct runs_tree *new_run) 1232 { 1233 size_t bytes = run->count * sizeof(struct ntfs_run); 1234 1235 if (bytes > new_run->allocated) { 1236 struct ntfs_run *new_ptr = kvmalloc(bytes, GFP_KERNEL); 1237 1238 if (!new_ptr) 1239 return -ENOMEM; 1240 1241 kvfree(new_run->runs); 1242 new_run->runs = new_ptr; 1243 new_run->allocated = bytes; 1244 } 1245 1246 memcpy(new_run->runs, run->runs, bytes); 1247 new_run->count = run->count; 1248 return 0; 1249 } 1250 1251 /* 1252 * run_remove_range 1253 * 1254 */ 1255 bool run_remove_range(struct runs_tree *run, CLST vcn, CLST len, CLST *done) 1256 { 1257 size_t index, eat; 1258 struct ntfs_run *r, *e, *eat_start, *eat_end; 1259 CLST end, d; 1260 1261 *done = 0; 1262 1263 /* Fast check. */ 1264 if (!run->count) 1265 return true; 1266 1267 if (!run_lookup(run, vcn, &index) && index >= run->count) { 1268 /* No entries in this run. */ 1269 return true; 1270 } 1271 1272 1273 e = run->runs + run->count; 1274 r = run->runs + index; 1275 end = vcn + len; 1276 1277 if (vcn > r->vcn) { 1278 CLST r_end = r->vcn + r->len; 1279 d = vcn - r->vcn; 1280 1281 if (r_end > end) { 1282 /* Remove a middle part, split. */ 1283 *done += len; 1284 r->len = d; 1285 return run_add_entry(run, end, r->lcn, r_end - end, 1286 false); 1287 } 1288 /* Remove tail of run .*/ 1289 *done += r->len - d; 1290 r->len = d; 1291 r += 1; 1292 } 1293 1294 eat_start = r; 1295 eat_end = r; 1296 1297 for (; r < e; r++) { 1298 if (r->vcn >= end) 1299 continue; 1300 1301 if (r->vcn + r->len <= end) { 1302 /* Eat this run. */ 1303 *done += r->len; 1304 eat_end = r + 1; 1305 continue; 1306 } 1307 1308 d = end - r->vcn; 1309 *done += d; 1310 if (r->lcn != SPARSE_LCN) 1311 r->lcn += d; 1312 r->len -= d; 1313 r->vcn = end; 1314 } 1315 1316 eat = eat_end - eat_start; 1317 memmove(eat_start, eat_end, (e - eat_end) * sizeof(*r)); 1318 run->count -= eat; 1319 1320 return true; 1321 } 1322 1323 CLST run_len(const struct runs_tree *run) 1324 { 1325 const struct ntfs_run *r, *e; 1326 CLST len = 0; 1327 1328 for (r = run->runs, e = r + run->count; r < e; r++) { 1329 len += r->len; 1330 } 1331 1332 return len; 1333 } 1334 1335 CLST run_get_max_vcn(const struct runs_tree *run) 1336 { 1337 const struct ntfs_run *r; 1338 if (!run->count) 1339 return 0; 1340 1341 r = run->runs + run->count - 1; 1342 return r->vcn + r->len; 1343 } 1344