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 13 #include "debug.h" 14 #include "ntfs.h" 15 #include "ntfs_fs.h" 16 17 /* runs_tree is a continues memory. Try to avoid big size. */ 18 #define NTFS3_RUN_MAX_BYTES 0x10000 19 20 struct ntfs_run { 21 CLST vcn; /* Virtual cluster number. */ 22 CLST len; /* Length in clusters. */ 23 CLST lcn; /* Logical cluster number. */ 24 }; 25 26 /* 27 * run_lookup - Lookup the index of a MCB entry that is first <= vcn. 28 * 29 * Case of success it will return non-zero value and set 30 * @index parameter to index of entry been found. 31 * Case of entry missing from list 'index' will be set to 32 * point to insertion position for the entry question. 33 */ 34 bool run_lookup(const struct runs_tree *run, CLST vcn, size_t *index) 35 { 36 size_t min_idx, max_idx, mid_idx; 37 struct ntfs_run *r; 38 39 if (!run->count) { 40 *index = 0; 41 return false; 42 } 43 44 min_idx = 0; 45 max_idx = run->count - 1; 46 47 /* Check boundary cases specially, 'cause they cover the often requests. */ 48 r = run->runs; 49 if (vcn < r->vcn) { 50 *index = 0; 51 return false; 52 } 53 54 if (vcn < r->vcn + r->len) { 55 *index = 0; 56 return true; 57 } 58 59 r += max_idx; 60 if (vcn >= r->vcn + r->len) { 61 *index = run->count; 62 return false; 63 } 64 65 if (vcn >= r->vcn) { 66 *index = max_idx; 67 return true; 68 } 69 70 do { 71 mid_idx = min_idx + ((max_idx - min_idx) >> 1); 72 r = run->runs + mid_idx; 73 74 if (vcn < r->vcn) { 75 max_idx = mid_idx - 1; 76 if (!mid_idx) 77 break; 78 } else if (vcn >= r->vcn + r->len) { 79 min_idx = mid_idx + 1; 80 } else { 81 *index = mid_idx; 82 return true; 83 } 84 } while (min_idx <= max_idx); 85 86 *index = max_idx + 1; 87 return false; 88 } 89 90 /* 91 * run_consolidate - Consolidate runs starting from a given one. 92 */ 93 static void run_consolidate(struct runs_tree *run, size_t index) 94 { 95 size_t i; 96 struct ntfs_run *r = run->runs + index; 97 98 while (index + 1 < run->count) { 99 /* 100 * I should merge current run with next 101 * if start of the next run lies inside one being tested. 102 */ 103 struct ntfs_run *n = r + 1; 104 CLST end = r->vcn + r->len; 105 CLST dl; 106 107 /* Stop if runs are not aligned one to another. */ 108 if (n->vcn > end) 109 break; 110 111 dl = end - n->vcn; 112 113 /* 114 * If range at index overlaps with next one 115 * then I will either adjust it's start position 116 * or (if completely matches) dust remove one from the list. 117 */ 118 if (dl > 0) { 119 if (n->len <= dl) 120 goto remove_next_range; 121 122 n->len -= dl; 123 n->vcn += dl; 124 if (n->lcn != SPARSE_LCN) 125 n->lcn += dl; 126 dl = 0; 127 } 128 129 /* 130 * Stop if sparse mode does not match 131 * both current and next runs. 132 */ 133 if ((n->lcn == SPARSE_LCN) != (r->lcn == SPARSE_LCN)) { 134 index += 1; 135 r = n; 136 continue; 137 } 138 139 /* 140 * Check if volume block 141 * of a next run lcn does not match 142 * last volume block of the current run. 143 */ 144 if (n->lcn != SPARSE_LCN && n->lcn != r->lcn + r->len) 145 break; 146 147 /* 148 * Next and current are siblings. 149 * Eat/join. 150 */ 151 r->len += n->len - dl; 152 153 remove_next_range: 154 i = run->count - (index + 1); 155 if (i > 1) 156 memmove(n, n + 1, sizeof(*n) * (i - 1)); 157 158 run->count -= 1; 159 } 160 } 161 162 /* 163 * run_is_mapped_full 164 * 165 * Return: True if range [svcn - evcn] is mapped. 166 */ 167 bool run_is_mapped_full(const struct runs_tree *run, CLST svcn, CLST evcn) 168 { 169 size_t i; 170 const struct ntfs_run *r, *end; 171 CLST next_vcn; 172 173 if (!run_lookup(run, svcn, &i)) 174 return false; 175 176 end = run->runs + run->count; 177 r = run->runs + i; 178 179 for (;;) { 180 next_vcn = r->vcn + r->len; 181 if (next_vcn > evcn) 182 return true; 183 184 if (++r >= end) 185 return false; 186 187 if (r->vcn != next_vcn) 188 return false; 189 } 190 } 191 192 bool run_lookup_entry(const struct runs_tree *run, CLST vcn, CLST *lcn, 193 CLST *len, size_t *index) 194 { 195 size_t idx; 196 CLST gap; 197 struct ntfs_run *r; 198 199 /* Fail immediately if nrun was not touched yet. */ 200 if (!run->runs) 201 return false; 202 203 if (!run_lookup(run, vcn, &idx)) 204 return false; 205 206 r = run->runs + idx; 207 208 if (vcn >= r->vcn + r->len) 209 return false; 210 211 gap = vcn - r->vcn; 212 if (r->len <= gap) 213 return false; 214 215 *lcn = r->lcn == SPARSE_LCN ? SPARSE_LCN : (r->lcn + gap); 216 217 if (len) 218 *len = r->len - gap; 219 if (index) 220 *index = idx; 221 222 return true; 223 } 224 225 /* 226 * run_truncate_head - Decommit the range before vcn. 227 */ 228 void run_truncate_head(struct runs_tree *run, CLST vcn) 229 { 230 size_t index; 231 struct ntfs_run *r; 232 233 if (run_lookup(run, vcn, &index)) { 234 r = run->runs + index; 235 236 if (vcn > r->vcn) { 237 CLST dlen = vcn - r->vcn; 238 239 r->vcn = vcn; 240 r->len -= dlen; 241 if (r->lcn != SPARSE_LCN) 242 r->lcn += dlen; 243 } 244 245 if (!index) 246 return; 247 } 248 r = run->runs; 249 memmove(r, r + index, sizeof(*r) * (run->count - index)); 250 251 run->count -= index; 252 253 if (!run->count) { 254 kvfree(run->runs); 255 run->runs = NULL; 256 run->allocated = 0; 257 } 258 } 259 260 /* 261 * run_truncate - Decommit the range after vcn. 262 */ 263 void run_truncate(struct runs_tree *run, CLST vcn) 264 { 265 size_t index; 266 267 /* 268 * If I hit the range then 269 * I have to truncate one. 270 * If range to be truncated is becoming empty 271 * then it will entirely be removed. 272 */ 273 if (run_lookup(run, vcn, &index)) { 274 struct ntfs_run *r = run->runs + index; 275 276 r->len = vcn - r->vcn; 277 278 if (r->len > 0) 279 index += 1; 280 } 281 282 /* 283 * At this point 'index' is set to position that 284 * should be thrown away (including index itself) 285 * Simple one - just set the limit. 286 */ 287 run->count = index; 288 289 /* Do not reallocate array 'runs'. Only free if possible. */ 290 if (!index) { 291 kvfree(run->runs); 292 run->runs = NULL; 293 run->allocated = 0; 294 } 295 } 296 297 /* 298 * run_truncate_around - Trim head and tail if necessary. 299 */ 300 void run_truncate_around(struct runs_tree *run, CLST vcn) 301 { 302 run_truncate_head(run, vcn); 303 304 if (run->count >= NTFS3_RUN_MAX_BYTES / sizeof(struct ntfs_run) / 2) 305 run_truncate(run, (run->runs + (run->count >> 1))->vcn); 306 } 307 308 /* 309 * run_add_entry 310 * 311 * Sets location to known state. 312 * Run to be added may overlap with existing location. 313 * 314 * Return: false if of memory. 315 */ 316 bool run_add_entry(struct runs_tree *run, CLST vcn, CLST lcn, CLST len, 317 bool is_mft) 318 { 319 size_t used, index; 320 struct ntfs_run *r; 321 bool inrange; 322 CLST tail_vcn = 0, tail_len = 0, tail_lcn = 0; 323 bool should_add_tail = false; 324 325 /* 326 * Lookup the insertion point. 327 * 328 * Execute bsearch for the entry containing 329 * start position question. 330 */ 331 inrange = run_lookup(run, vcn, &index); 332 333 /* 334 * Shortcut here would be case of 335 * range not been found but one been added 336 * continues previous run. 337 * This case I can directly make use of 338 * existing range as my start point. 339 */ 340 if (!inrange && index > 0) { 341 struct ntfs_run *t = run->runs + index - 1; 342 343 if (t->vcn + t->len == vcn && 344 (t->lcn == SPARSE_LCN) == (lcn == SPARSE_LCN) && 345 (lcn == SPARSE_LCN || lcn == t->lcn + t->len)) { 346 inrange = true; 347 index -= 1; 348 } 349 } 350 351 /* 352 * At this point 'index' either points to the range 353 * containing start position or to the insertion position 354 * for a new range. 355 * So first let's check if range I'm probing is here already. 356 */ 357 if (!inrange) { 358 requires_new_range: 359 /* 360 * Range was not found. 361 * Insert at position 'index' 362 */ 363 used = run->count * sizeof(struct ntfs_run); 364 365 /* 366 * Check allocated space. 367 * If one is not enough to get one more entry 368 * then it will be reallocated. 369 */ 370 if (run->allocated < used + sizeof(struct ntfs_run)) { 371 size_t bytes; 372 struct ntfs_run *new_ptr; 373 374 /* Use power of 2 for 'bytes'. */ 375 if (!used) { 376 bytes = 64; 377 } else if (used <= 16 * PAGE_SIZE) { 378 if (is_power_of_2(run->allocated)) 379 bytes = run->allocated << 1; 380 else 381 bytes = (size_t)1 382 << (2 + blksize_bits(used)); 383 } else { 384 bytes = run->allocated + (16 * PAGE_SIZE); 385 } 386 387 WARN_ON(!is_mft && bytes > NTFS3_RUN_MAX_BYTES); 388 389 new_ptr = kvmalloc(bytes, GFP_KERNEL); 390 391 if (!new_ptr) 392 return false; 393 394 r = new_ptr + index; 395 memcpy(new_ptr, run->runs, 396 index * sizeof(struct ntfs_run)); 397 memcpy(r + 1, run->runs + index, 398 sizeof(struct ntfs_run) * (run->count - index)); 399 400 kvfree(run->runs); 401 run->runs = new_ptr; 402 run->allocated = bytes; 403 404 } else { 405 size_t i = run->count - index; 406 407 r = run->runs + index; 408 409 /* memmove appears to be a bottle neck here... */ 410 if (i > 0) 411 memmove(r + 1, r, sizeof(struct ntfs_run) * i); 412 } 413 414 r->vcn = vcn; 415 r->lcn = lcn; 416 r->len = len; 417 run->count += 1; 418 } else { 419 r = run->runs + index; 420 421 /* 422 * If one of ranges was not allocated then we 423 * have to split location we just matched and 424 * insert current one. 425 * A common case this requires tail to be reinserted 426 * a recursive call. 427 */ 428 if (((lcn == SPARSE_LCN) != (r->lcn == SPARSE_LCN)) || 429 (lcn != SPARSE_LCN && lcn != r->lcn + (vcn - r->vcn))) { 430 CLST to_eat = vcn - r->vcn; 431 CLST Tovcn = to_eat + len; 432 433 should_add_tail = Tovcn < r->len; 434 435 if (should_add_tail) { 436 tail_lcn = r->lcn == SPARSE_LCN 437 ? SPARSE_LCN 438 : (r->lcn + Tovcn); 439 tail_vcn = r->vcn + Tovcn; 440 tail_len = r->len - Tovcn; 441 } 442 443 if (to_eat > 0) { 444 r->len = to_eat; 445 inrange = false; 446 index += 1; 447 goto requires_new_range; 448 } 449 450 /* lcn should match one were going to add. */ 451 r->lcn = lcn; 452 } 453 454 /* 455 * If existing range fits then were done. 456 * Otherwise extend found one and fall back to range jocode. 457 */ 458 if (r->vcn + r->len < vcn + len) 459 r->len += len - ((r->vcn + r->len) - vcn); 460 } 461 462 /* 463 * And normalize it starting from insertion point. 464 * It's possible that no insertion needed case if 465 * start point lies within the range of an entry 466 * that 'index' points to. 467 */ 468 if (inrange && index > 0) 469 index -= 1; 470 run_consolidate(run, index); 471 run_consolidate(run, index + 1); 472 473 /* 474 * A special case. 475 * We have to add extra range a tail. 476 */ 477 if (should_add_tail && 478 !run_add_entry(run, tail_vcn, tail_lcn, tail_len, is_mft)) 479 return false; 480 481 return true; 482 } 483 484 /* run_collapse_range 485 * 486 * Helper for attr_collapse_range(), 487 * which is helper for fallocate(collapse_range). 488 */ 489 bool run_collapse_range(struct runs_tree *run, CLST vcn, CLST len) 490 { 491 size_t index, eat; 492 struct ntfs_run *r, *e, *eat_start, *eat_end; 493 CLST end; 494 495 if (WARN_ON(!run_lookup(run, vcn, &index))) 496 return true; /* Should never be here. */ 497 498 e = run->runs + run->count; 499 r = run->runs + index; 500 end = vcn + len; 501 502 if (vcn > r->vcn) { 503 if (r->vcn + r->len <= end) { 504 /* Collapse tail of run .*/ 505 r->len = vcn - r->vcn; 506 } else if (r->lcn == SPARSE_LCN) { 507 /* Collapse a middle part of sparsed run. */ 508 r->len -= len; 509 } else { 510 /* Collapse a middle part of normal run, split. */ 511 if (!run_add_entry(run, vcn, SPARSE_LCN, len, false)) 512 return false; 513 return run_collapse_range(run, vcn, len); 514 } 515 516 r += 1; 517 } 518 519 eat_start = r; 520 eat_end = r; 521 522 for (; r < e; r++) { 523 CLST d; 524 525 if (r->vcn >= end) { 526 r->vcn -= len; 527 continue; 528 } 529 530 if (r->vcn + r->len <= end) { 531 /* Eat this run. */ 532 eat_end = r + 1; 533 continue; 534 } 535 536 d = end - r->vcn; 537 if (r->lcn != SPARSE_LCN) 538 r->lcn += d; 539 r->len -= d; 540 r->vcn -= len - d; 541 } 542 543 eat = eat_end - eat_start; 544 memmove(eat_start, eat_end, (e - eat_end) * sizeof(*r)); 545 run->count -= eat; 546 547 return true; 548 } 549 550 /* 551 * run_get_entry - Return index-th mapped region. 552 */ 553 bool run_get_entry(const struct runs_tree *run, size_t index, CLST *vcn, 554 CLST *lcn, CLST *len) 555 { 556 const struct ntfs_run *r; 557 558 if (index >= run->count) 559 return false; 560 561 r = run->runs + index; 562 563 if (!r->len) 564 return false; 565 566 if (vcn) 567 *vcn = r->vcn; 568 if (lcn) 569 *lcn = r->lcn; 570 if (len) 571 *len = r->len; 572 return true; 573 } 574 575 /* 576 * run_packed_size - Calculate the size of packed int64. 577 */ 578 #ifdef __BIG_ENDIAN 579 static inline int run_packed_size(const s64 n) 580 { 581 const u8 *p = (const u8 *)&n + sizeof(n) - 1; 582 583 if (n >= 0) { 584 if (p[-7] || p[-6] || p[-5] || p[-4]) 585 p -= 4; 586 if (p[-3] || p[-2]) 587 p -= 2; 588 if (p[-1]) 589 p -= 1; 590 if (p[0] & 0x80) 591 p -= 1; 592 } else { 593 if (p[-7] != 0xff || p[-6] != 0xff || p[-5] != 0xff || 594 p[-4] != 0xff) 595 p -= 4; 596 if (p[-3] != 0xff || p[-2] != 0xff) 597 p -= 2; 598 if (p[-1] != 0xff) 599 p -= 1; 600 if (!(p[0] & 0x80)) 601 p -= 1; 602 } 603 return (const u8 *)&n + sizeof(n) - p; 604 } 605 606 /* Full trusted function. It does not check 'size' for errors. */ 607 static inline void run_pack_s64(u8 *run_buf, u8 size, s64 v) 608 { 609 const u8 *p = (u8 *)&v; 610 611 switch (size) { 612 case 8: 613 run_buf[7] = p[0]; 614 fallthrough; 615 case 7: 616 run_buf[6] = p[1]; 617 fallthrough; 618 case 6: 619 run_buf[5] = p[2]; 620 fallthrough; 621 case 5: 622 run_buf[4] = p[3]; 623 fallthrough; 624 case 4: 625 run_buf[3] = p[4]; 626 fallthrough; 627 case 3: 628 run_buf[2] = p[5]; 629 fallthrough; 630 case 2: 631 run_buf[1] = p[6]; 632 fallthrough; 633 case 1: 634 run_buf[0] = p[7]; 635 } 636 } 637 638 /* Full trusted function. It does not check 'size' for errors. */ 639 static inline s64 run_unpack_s64(const u8 *run_buf, u8 size, s64 v) 640 { 641 u8 *p = (u8 *)&v; 642 643 switch (size) { 644 case 8: 645 p[0] = run_buf[7]; 646 fallthrough; 647 case 7: 648 p[1] = run_buf[6]; 649 fallthrough; 650 case 6: 651 p[2] = run_buf[5]; 652 fallthrough; 653 case 5: 654 p[3] = run_buf[4]; 655 fallthrough; 656 case 4: 657 p[4] = run_buf[3]; 658 fallthrough; 659 case 3: 660 p[5] = run_buf[2]; 661 fallthrough; 662 case 2: 663 p[6] = run_buf[1]; 664 fallthrough; 665 case 1: 666 p[7] = run_buf[0]; 667 } 668 return v; 669 } 670 671 #else 672 673 static inline int run_packed_size(const s64 n) 674 { 675 const u8 *p = (const u8 *)&n; 676 677 if (n >= 0) { 678 if (p[7] || p[6] || p[5] || p[4]) 679 p += 4; 680 if (p[3] || p[2]) 681 p += 2; 682 if (p[1]) 683 p += 1; 684 if (p[0] & 0x80) 685 p += 1; 686 } else { 687 if (p[7] != 0xff || p[6] != 0xff || p[5] != 0xff || 688 p[4] != 0xff) 689 p += 4; 690 if (p[3] != 0xff || p[2] != 0xff) 691 p += 2; 692 if (p[1] != 0xff) 693 p += 1; 694 if (!(p[0] & 0x80)) 695 p += 1; 696 } 697 698 return 1 + p - (const u8 *)&n; 699 } 700 701 /* Full trusted function. It does not check 'size' for errors. */ 702 static inline void run_pack_s64(u8 *run_buf, u8 size, s64 v) 703 { 704 const u8 *p = (u8 *)&v; 705 706 /* memcpy( run_buf, &v, size); Is it faster? */ 707 switch (size) { 708 case 8: 709 run_buf[7] = p[7]; 710 fallthrough; 711 case 7: 712 run_buf[6] = p[6]; 713 fallthrough; 714 case 6: 715 run_buf[5] = p[5]; 716 fallthrough; 717 case 5: 718 run_buf[4] = p[4]; 719 fallthrough; 720 case 4: 721 run_buf[3] = p[3]; 722 fallthrough; 723 case 3: 724 run_buf[2] = p[2]; 725 fallthrough; 726 case 2: 727 run_buf[1] = p[1]; 728 fallthrough; 729 case 1: 730 run_buf[0] = p[0]; 731 } 732 } 733 734 /* full trusted function. It does not check 'size' for errors */ 735 static inline s64 run_unpack_s64(const u8 *run_buf, u8 size, s64 v) 736 { 737 u8 *p = (u8 *)&v; 738 739 /* memcpy( &v, run_buf, size); Is it faster? */ 740 switch (size) { 741 case 8: 742 p[7] = run_buf[7]; 743 fallthrough; 744 case 7: 745 p[6] = run_buf[6]; 746 fallthrough; 747 case 6: 748 p[5] = run_buf[5]; 749 fallthrough; 750 case 5: 751 p[4] = run_buf[4]; 752 fallthrough; 753 case 4: 754 p[3] = run_buf[3]; 755 fallthrough; 756 case 3: 757 p[2] = run_buf[2]; 758 fallthrough; 759 case 2: 760 p[1] = run_buf[1]; 761 fallthrough; 762 case 1: 763 p[0] = run_buf[0]; 764 } 765 return v; 766 } 767 #endif 768 769 /* 770 * run_pack - Pack runs into buffer. 771 * 772 * packed_vcns - How much runs we have packed. 773 * packed_size - How much bytes we have used run_buf. 774 */ 775 int run_pack(const struct runs_tree *run, CLST svcn, CLST len, u8 *run_buf, 776 u32 run_buf_size, CLST *packed_vcns) 777 { 778 CLST next_vcn, vcn, lcn; 779 CLST prev_lcn = 0; 780 CLST evcn1 = svcn + len; 781 int packed_size = 0; 782 size_t i; 783 bool ok; 784 s64 dlcn; 785 int offset_size, size_size, tmp; 786 787 next_vcn = vcn = svcn; 788 789 *packed_vcns = 0; 790 791 if (!len) 792 goto out; 793 794 ok = run_lookup_entry(run, vcn, &lcn, &len, &i); 795 796 if (!ok) 797 goto error; 798 799 if (next_vcn != vcn) 800 goto error; 801 802 for (;;) { 803 next_vcn = vcn + len; 804 if (next_vcn > evcn1) 805 len = evcn1 - vcn; 806 807 /* How much bytes required to pack len. */ 808 size_size = run_packed_size(len); 809 810 /* offset_size - How much bytes is packed dlcn. */ 811 if (lcn == SPARSE_LCN) { 812 offset_size = 0; 813 dlcn = 0; 814 } else { 815 /* NOTE: lcn can be less than prev_lcn! */ 816 dlcn = (s64)lcn - prev_lcn; 817 offset_size = run_packed_size(dlcn); 818 prev_lcn = lcn; 819 } 820 821 tmp = run_buf_size - packed_size - 2 - offset_size; 822 if (tmp <= 0) 823 goto out; 824 825 /* Can we store this entire run. */ 826 if (tmp < size_size) 827 goto out; 828 829 if (run_buf) { 830 /* Pack run header. */ 831 run_buf[0] = ((u8)(size_size | (offset_size << 4))); 832 run_buf += 1; 833 834 /* Pack the length of run. */ 835 run_pack_s64(run_buf, size_size, len); 836 837 run_buf += size_size; 838 /* Pack the offset from previous LCN. */ 839 run_pack_s64(run_buf, offset_size, dlcn); 840 run_buf += offset_size; 841 } 842 843 packed_size += 1 + offset_size + size_size; 844 *packed_vcns += len; 845 846 if (packed_size + 1 >= run_buf_size || next_vcn >= evcn1) 847 goto out; 848 849 ok = run_get_entry(run, ++i, &vcn, &lcn, &len); 850 if (!ok) 851 goto error; 852 853 if (next_vcn != vcn) 854 goto error; 855 } 856 857 out: 858 /* Store last zero. */ 859 if (run_buf) 860 run_buf[0] = 0; 861 862 return packed_size + 1; 863 864 error: 865 return -EOPNOTSUPP; 866 } 867 868 /* 869 * run_unpack - Unpack packed runs from @run_buf. 870 * 871 * Return: Error if negative, or real used bytes. 872 */ 873 int run_unpack(struct runs_tree *run, struct ntfs_sb_info *sbi, CLST ino, 874 CLST svcn, CLST evcn, CLST vcn, const u8 *run_buf, 875 u32 run_buf_size) 876 { 877 u64 prev_lcn, vcn64, lcn, next_vcn; 878 const u8 *run_last, *run_0; 879 bool is_mft = ino == MFT_REC_MFT; 880 881 /* Check for empty. */ 882 if (evcn + 1 == svcn) 883 return 0; 884 885 if (evcn < svcn) 886 return -EINVAL; 887 888 run_0 = run_buf; 889 run_last = run_buf + run_buf_size; 890 prev_lcn = 0; 891 vcn64 = svcn; 892 893 /* Read all runs the chain. */ 894 /* size_size - How much bytes is packed len. */ 895 while (run_buf < run_last) { 896 /* size_size - How much bytes is packed len. */ 897 u8 size_size = *run_buf & 0xF; 898 /* offset_size - How much bytes is packed dlcn. */ 899 u8 offset_size = *run_buf++ >> 4; 900 u64 len; 901 902 if (!size_size) 903 break; 904 905 /* 906 * Unpack runs. 907 * NOTE: Runs are stored little endian order 908 * "len" is unsigned value, "dlcn" is signed. 909 * Large positive number requires to store 5 bytes 910 * e.g.: 05 FF 7E FF FF 00 00 00 911 */ 912 if (size_size > 8) 913 return -EINVAL; 914 915 len = run_unpack_s64(run_buf, size_size, 0); 916 /* Skip size_size. */ 917 run_buf += size_size; 918 919 if (!len) 920 return -EINVAL; 921 922 if (!offset_size) 923 lcn = SPARSE_LCN64; 924 else if (offset_size <= 8) { 925 s64 dlcn; 926 927 /* Initial value of dlcn is -1 or 0. */ 928 dlcn = (run_buf[offset_size - 1] & 0x80) ? (s64)-1 : 0; 929 dlcn = run_unpack_s64(run_buf, offset_size, dlcn); 930 /* Skip offset_size. */ 931 run_buf += offset_size; 932 933 if (!dlcn) 934 return -EINVAL; 935 lcn = prev_lcn + dlcn; 936 prev_lcn = lcn; 937 } else 938 return -EINVAL; 939 940 next_vcn = vcn64 + len; 941 /* Check boundary. */ 942 if (next_vcn > evcn + 1) 943 return -EINVAL; 944 945 #ifndef CONFIG_NTFS3_64BIT_CLUSTER 946 if (next_vcn > 0x100000000ull || (lcn + len) > 0x100000000ull) { 947 ntfs_err( 948 sbi->sb, 949 "This driver is compiled without CONFIG_NTFS3_64BIT_CLUSTER (like windows driver).\n" 950 "Volume contains 64 bits run: vcn %llx, lcn %llx, len %llx.\n" 951 "Activate CONFIG_NTFS3_64BIT_CLUSTER to process this case", 952 vcn64, lcn, len); 953 return -EOPNOTSUPP; 954 } 955 #endif 956 if (lcn != SPARSE_LCN64 && lcn + len > sbi->used.bitmap.nbits) { 957 /* LCN range is out of volume. */ 958 return -EINVAL; 959 } 960 961 if (!run) 962 ; /* Called from check_attr(fslog.c) to check run. */ 963 else if (run == RUN_DEALLOCATE) { 964 /* 965 * Called from ni_delete_all to free clusters 966 * without storing in run. 967 */ 968 if (lcn != SPARSE_LCN64) 969 mark_as_free_ex(sbi, lcn, len, true); 970 } else if (vcn64 >= vcn) { 971 if (!run_add_entry(run, vcn64, lcn, len, is_mft)) 972 return -ENOMEM; 973 } else if (next_vcn > vcn) { 974 u64 dlen = vcn - vcn64; 975 976 if (!run_add_entry(run, vcn, lcn + dlen, len - dlen, 977 is_mft)) 978 return -ENOMEM; 979 } 980 981 vcn64 = next_vcn; 982 } 983 984 if (vcn64 != evcn + 1) { 985 /* Not expected length of unpacked runs. */ 986 return -EINVAL; 987 } 988 989 return run_buf - run_0; 990 } 991 992 #ifdef NTFS3_CHECK_FREE_CLST 993 /* 994 * run_unpack_ex - Unpack packed runs from "run_buf". 995 * 996 * Checks unpacked runs to be used in bitmap. 997 * 998 * Return: Error if negative, or real used bytes. 999 */ 1000 int run_unpack_ex(struct runs_tree *run, struct ntfs_sb_info *sbi, CLST ino, 1001 CLST svcn, CLST evcn, CLST vcn, const u8 *run_buf, 1002 u32 run_buf_size) 1003 { 1004 int ret, err; 1005 CLST next_vcn, lcn, len; 1006 size_t index; 1007 bool ok; 1008 struct wnd_bitmap *wnd; 1009 1010 ret = run_unpack(run, sbi, ino, svcn, evcn, vcn, run_buf, run_buf_size); 1011 if (ret <= 0) 1012 return ret; 1013 1014 if (!sbi->used.bitmap.sb || !run || run == RUN_DEALLOCATE) 1015 return ret; 1016 1017 if (ino == MFT_REC_BADCLUST) 1018 return ret; 1019 1020 next_vcn = vcn = svcn; 1021 wnd = &sbi->used.bitmap; 1022 1023 for (ok = run_lookup_entry(run, vcn, &lcn, &len, &index); 1024 next_vcn <= evcn; 1025 ok = run_get_entry(run, ++index, &vcn, &lcn, &len)) { 1026 if (!ok || next_vcn != vcn) 1027 return -EINVAL; 1028 1029 next_vcn = vcn + len; 1030 1031 if (lcn == SPARSE_LCN) 1032 continue; 1033 1034 if (sbi->flags & NTFS_FLAGS_NEED_REPLAY) 1035 continue; 1036 1037 down_read_nested(&wnd->rw_lock, BITMAP_MUTEX_CLUSTERS); 1038 /* Check for free blocks. */ 1039 ok = wnd_is_used(wnd, lcn, len); 1040 up_read(&wnd->rw_lock); 1041 if (ok) 1042 continue; 1043 1044 /* Looks like volume is corrupted. */ 1045 ntfs_set_state(sbi, NTFS_DIRTY_ERROR); 1046 1047 if (down_write_trylock(&wnd->rw_lock)) { 1048 /* Mark all zero bits as used in range [lcn, lcn+len). */ 1049 CLST i, lcn_f = 0, len_f = 0; 1050 1051 err = 0; 1052 for (i = 0; i < len; i++) { 1053 if (wnd_is_free(wnd, lcn + i, 1)) { 1054 if (!len_f) 1055 lcn_f = lcn + i; 1056 len_f += 1; 1057 } else if (len_f) { 1058 err = wnd_set_used(wnd, lcn_f, len_f); 1059 len_f = 0; 1060 if (err) 1061 break; 1062 } 1063 } 1064 1065 if (len_f) 1066 err = wnd_set_used(wnd, lcn_f, len_f); 1067 1068 up_write(&wnd->rw_lock); 1069 if (err) 1070 return err; 1071 } 1072 } 1073 1074 return ret; 1075 } 1076 #endif 1077 1078 /* 1079 * run_get_highest_vcn 1080 * 1081 * Return the highest vcn from a mapping pairs array 1082 * it used while replaying log file. 1083 */ 1084 int run_get_highest_vcn(CLST vcn, const u8 *run_buf, u64 *highest_vcn) 1085 { 1086 u64 vcn64 = vcn; 1087 u8 size_size; 1088 1089 while ((size_size = *run_buf & 0xF)) { 1090 u8 offset_size = *run_buf++ >> 4; 1091 u64 len; 1092 1093 if (size_size > 8 || offset_size > 8) 1094 return -EINVAL; 1095 1096 len = run_unpack_s64(run_buf, size_size, 0); 1097 if (!len) 1098 return -EINVAL; 1099 1100 run_buf += size_size + offset_size; 1101 vcn64 += len; 1102 1103 #ifndef CONFIG_NTFS3_64BIT_CLUSTER 1104 if (vcn64 > 0x100000000ull) 1105 return -EINVAL; 1106 #endif 1107 } 1108 1109 *highest_vcn = vcn64 - 1; 1110 return 0; 1111 } 1112