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