Loading...
Note: File does not exist in v3.1.
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
20struct 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 */
34static 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 */
93static 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
153remove_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 */
167bool 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
192bool 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 */
228void 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 */
263void 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 */
300void 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 */
316bool 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) {
358requires_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 */
489bool 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/* run_insert_range
551 *
552 * Helper for attr_insert_range(),
553 * which is helper for fallocate(insert_range).
554 */
555bool run_insert_range(struct runs_tree *run, CLST vcn, CLST len)
556{
557 size_t index;
558 struct ntfs_run *r, *e;
559
560 if (WARN_ON(!run_lookup(run, vcn, &index)))
561 return false; /* Should never be here. */
562
563 e = run->runs + run->count;
564 r = run->runs + index;
565
566 if (vcn > r->vcn)
567 r += 1;
568
569 for (; r < e; r++)
570 r->vcn += len;
571
572 r = run->runs + index;
573
574 if (vcn > r->vcn) {
575 /* split fragment. */
576 CLST len1 = vcn - r->vcn;
577 CLST len2 = r->len - len1;
578 CLST lcn2 = r->lcn == SPARSE_LCN ? SPARSE_LCN : (r->lcn + len1);
579
580 r->len = len1;
581
582 if (!run_add_entry(run, vcn + len, lcn2, len2, false))
583 return false;
584 }
585
586 if (!run_add_entry(run, vcn, SPARSE_LCN, len, false))
587 return false;
588
589 return true;
590}
591
592/*
593 * run_get_entry - Return index-th mapped region.
594 */
595bool run_get_entry(const struct runs_tree *run, size_t index, CLST *vcn,
596 CLST *lcn, CLST *len)
597{
598 const struct ntfs_run *r;
599
600 if (index >= run->count)
601 return false;
602
603 r = run->runs + index;
604
605 if (!r->len)
606 return false;
607
608 if (vcn)
609 *vcn = r->vcn;
610 if (lcn)
611 *lcn = r->lcn;
612 if (len)
613 *len = r->len;
614 return true;
615}
616
617/*
618 * run_packed_size - Calculate the size of packed int64.
619 */
620#ifdef __BIG_ENDIAN
621static inline int run_packed_size(const s64 n)
622{
623 const u8 *p = (const u8 *)&n + sizeof(n) - 1;
624
625 if (n >= 0) {
626 if (p[-7] || p[-6] || p[-5] || p[-4])
627 p -= 4;
628 if (p[-3] || p[-2])
629 p -= 2;
630 if (p[-1])
631 p -= 1;
632 if (p[0] & 0x80)
633 p -= 1;
634 } else {
635 if (p[-7] != 0xff || p[-6] != 0xff || p[-5] != 0xff ||
636 p[-4] != 0xff)
637 p -= 4;
638 if (p[-3] != 0xff || p[-2] != 0xff)
639 p -= 2;
640 if (p[-1] != 0xff)
641 p -= 1;
642 if (!(p[0] & 0x80))
643 p -= 1;
644 }
645 return (const u8 *)&n + sizeof(n) - p;
646}
647
648/* Full trusted function. It does not check 'size' for errors. */
649static inline void run_pack_s64(u8 *run_buf, u8 size, s64 v)
650{
651 const u8 *p = (u8 *)&v;
652
653 switch (size) {
654 case 8:
655 run_buf[7] = p[0];
656 fallthrough;
657 case 7:
658 run_buf[6] = p[1];
659 fallthrough;
660 case 6:
661 run_buf[5] = p[2];
662 fallthrough;
663 case 5:
664 run_buf[4] = p[3];
665 fallthrough;
666 case 4:
667 run_buf[3] = p[4];
668 fallthrough;
669 case 3:
670 run_buf[2] = p[5];
671 fallthrough;
672 case 2:
673 run_buf[1] = p[6];
674 fallthrough;
675 case 1:
676 run_buf[0] = p[7];
677 }
678}
679
680/* Full trusted function. It does not check 'size' for errors. */
681static inline s64 run_unpack_s64(const u8 *run_buf, u8 size, s64 v)
682{
683 u8 *p = (u8 *)&v;
684
685 switch (size) {
686 case 8:
687 p[0] = run_buf[7];
688 fallthrough;
689 case 7:
690 p[1] = run_buf[6];
691 fallthrough;
692 case 6:
693 p[2] = run_buf[5];
694 fallthrough;
695 case 5:
696 p[3] = run_buf[4];
697 fallthrough;
698 case 4:
699 p[4] = run_buf[3];
700 fallthrough;
701 case 3:
702 p[5] = run_buf[2];
703 fallthrough;
704 case 2:
705 p[6] = run_buf[1];
706 fallthrough;
707 case 1:
708 p[7] = run_buf[0];
709 }
710 return v;
711}
712
713#else
714
715static inline int run_packed_size(const s64 n)
716{
717 const u8 *p = (const u8 *)&n;
718
719 if (n >= 0) {
720 if (p[7] || p[6] || p[5] || p[4])
721 p += 4;
722 if (p[3] || p[2])
723 p += 2;
724 if (p[1])
725 p += 1;
726 if (p[0] & 0x80)
727 p += 1;
728 } else {
729 if (p[7] != 0xff || p[6] != 0xff || p[5] != 0xff ||
730 p[4] != 0xff)
731 p += 4;
732 if (p[3] != 0xff || p[2] != 0xff)
733 p += 2;
734 if (p[1] != 0xff)
735 p += 1;
736 if (!(p[0] & 0x80))
737 p += 1;
738 }
739
740 return 1 + p - (const u8 *)&n;
741}
742
743/* Full trusted function. It does not check 'size' for errors. */
744static inline void run_pack_s64(u8 *run_buf, u8 size, s64 v)
745{
746 const u8 *p = (u8 *)&v;
747
748 /* memcpy( run_buf, &v, size); Is it faster? */
749 switch (size) {
750 case 8:
751 run_buf[7] = p[7];
752 fallthrough;
753 case 7:
754 run_buf[6] = p[6];
755 fallthrough;
756 case 6:
757 run_buf[5] = p[5];
758 fallthrough;
759 case 5:
760 run_buf[4] = p[4];
761 fallthrough;
762 case 4:
763 run_buf[3] = p[3];
764 fallthrough;
765 case 3:
766 run_buf[2] = p[2];
767 fallthrough;
768 case 2:
769 run_buf[1] = p[1];
770 fallthrough;
771 case 1:
772 run_buf[0] = p[0];
773 }
774}
775
776/* full trusted function. It does not check 'size' for errors */
777static inline s64 run_unpack_s64(const u8 *run_buf, u8 size, s64 v)
778{
779 u8 *p = (u8 *)&v;
780
781 /* memcpy( &v, run_buf, size); Is it faster? */
782 switch (size) {
783 case 8:
784 p[7] = run_buf[7];
785 fallthrough;
786 case 7:
787 p[6] = run_buf[6];
788 fallthrough;
789 case 6:
790 p[5] = run_buf[5];
791 fallthrough;
792 case 5:
793 p[4] = run_buf[4];
794 fallthrough;
795 case 4:
796 p[3] = run_buf[3];
797 fallthrough;
798 case 3:
799 p[2] = run_buf[2];
800 fallthrough;
801 case 2:
802 p[1] = run_buf[1];
803 fallthrough;
804 case 1:
805 p[0] = run_buf[0];
806 }
807 return v;
808}
809#endif
810
811/*
812 * run_pack - Pack runs into buffer.
813 *
814 * packed_vcns - How much runs we have packed.
815 * packed_size - How much bytes we have used run_buf.
816 */
817int run_pack(const struct runs_tree *run, CLST svcn, CLST len, u8 *run_buf,
818 u32 run_buf_size, CLST *packed_vcns)
819{
820 CLST next_vcn, vcn, lcn;
821 CLST prev_lcn = 0;
822 CLST evcn1 = svcn + len;
823 const struct ntfs_run *r, *r_end;
824 int packed_size = 0;
825 size_t i;
826 s64 dlcn;
827 int offset_size, size_size, tmp;
828
829 *packed_vcns = 0;
830
831 if (!len)
832 goto out;
833
834 /* Check all required entries [svcn, encv1) available. */
835 if (!run_lookup(run, svcn, &i))
836 return -ENOENT;
837
838 r_end = run->runs + run->count;
839 r = run->runs + i;
840
841 for (next_vcn = r->vcn + r->len; next_vcn < evcn1;
842 next_vcn = r->vcn + r->len) {
843 if (++r >= r_end || r->vcn != next_vcn)
844 return -ENOENT;
845 }
846
847 /* Repeat cycle above and pack runs. Assume no errors. */
848 r = run->runs + i;
849 len = svcn - r->vcn;
850 vcn = svcn;
851 lcn = r->lcn == SPARSE_LCN ? SPARSE_LCN : (r->lcn + len);
852 len = r->len - len;
853
854 for (;;) {
855 next_vcn = vcn + len;
856 if (next_vcn > evcn1)
857 len = evcn1 - vcn;
858
859 /* How much bytes required to pack len. */
860 size_size = run_packed_size(len);
861
862 /* offset_size - How much bytes is packed dlcn. */
863 if (lcn == SPARSE_LCN) {
864 offset_size = 0;
865 dlcn = 0;
866 } else {
867 /* NOTE: lcn can be less than prev_lcn! */
868 dlcn = (s64)lcn - prev_lcn;
869 offset_size = run_packed_size(dlcn);
870 prev_lcn = lcn;
871 }
872
873 tmp = run_buf_size - packed_size - 2 - offset_size;
874 if (tmp <= 0)
875 goto out;
876
877 /* Can we store this entire run. */
878 if (tmp < size_size)
879 goto out;
880
881 if (run_buf) {
882 /* Pack run header. */
883 run_buf[0] = ((u8)(size_size | (offset_size << 4)));
884 run_buf += 1;
885
886 /* Pack the length of run. */
887 run_pack_s64(run_buf, size_size, len);
888
889 run_buf += size_size;
890 /* Pack the offset from previous LCN. */
891 run_pack_s64(run_buf, offset_size, dlcn);
892 run_buf += offset_size;
893 }
894
895 packed_size += 1 + offset_size + size_size;
896 *packed_vcns += len;
897
898 if (packed_size + 1 >= run_buf_size || next_vcn >= evcn1)
899 goto out;
900
901 r += 1;
902 vcn = r->vcn;
903 lcn = r->lcn;
904 len = r->len;
905 }
906
907out:
908 /* Store last zero. */
909 if (run_buf)
910 run_buf[0] = 0;
911
912 return packed_size + 1;
913}
914
915/*
916 * run_unpack - Unpack packed runs from @run_buf.
917 *
918 * Return: Error if negative, or real used bytes.
919 */
920int run_unpack(struct runs_tree *run, struct ntfs_sb_info *sbi, CLST ino,
921 CLST svcn, CLST evcn, CLST vcn, const u8 *run_buf,
922 int run_buf_size)
923{
924 u64 prev_lcn, vcn64, lcn, next_vcn;
925 const u8 *run_last, *run_0;
926 bool is_mft = ino == MFT_REC_MFT;
927
928 if (run_buf_size < 0)
929 return -EINVAL;
930
931 /* Check for empty. */
932 if (evcn + 1 == svcn)
933 return 0;
934
935 if (evcn < svcn)
936 return -EINVAL;
937
938 run_0 = run_buf;
939 run_last = run_buf + run_buf_size;
940 prev_lcn = 0;
941 vcn64 = svcn;
942
943 /* Read all runs the chain. */
944 /* size_size - How much bytes is packed len. */
945 while (run_buf < run_last) {
946 /* size_size - How much bytes is packed len. */
947 u8 size_size = *run_buf & 0xF;
948 /* offset_size - How much bytes is packed dlcn. */
949 u8 offset_size = *run_buf++ >> 4;
950 u64 len;
951
952 if (!size_size)
953 break;
954
955 /*
956 * Unpack runs.
957 * NOTE: Runs are stored little endian order
958 * "len" is unsigned value, "dlcn" is signed.
959 * Large positive number requires to store 5 bytes
960 * e.g.: 05 FF 7E FF FF 00 00 00
961 */
962 if (size_size > 8)
963 return -EINVAL;
964
965 len = run_unpack_s64(run_buf, size_size, 0);
966 /* Skip size_size. */
967 run_buf += size_size;
968
969 if (!len)
970 return -EINVAL;
971
972 if (!offset_size)
973 lcn = SPARSE_LCN64;
974 else if (offset_size <= 8) {
975 s64 dlcn;
976
977 /* Initial value of dlcn is -1 or 0. */
978 dlcn = (run_buf[offset_size - 1] & 0x80) ? (s64)-1 : 0;
979 dlcn = run_unpack_s64(run_buf, offset_size, dlcn);
980 /* Skip offset_size. */
981 run_buf += offset_size;
982
983 if (!dlcn)
984 return -EINVAL;
985 lcn = prev_lcn + dlcn;
986 prev_lcn = lcn;
987 } else
988 return -EINVAL;
989
990 next_vcn = vcn64 + len;
991 /* Check boundary. */
992 if (next_vcn > evcn + 1)
993 return -EINVAL;
994
995#ifndef CONFIG_NTFS3_64BIT_CLUSTER
996 if (next_vcn > 0x100000000ull || (lcn + len) > 0x100000000ull) {
997 ntfs_err(
998 sbi->sb,
999 "This driver is compiled without CONFIG_NTFS3_64BIT_CLUSTER (like windows driver).\n"
1000 "Volume contains 64 bits run: vcn %llx, lcn %llx, len %llx.\n"
1001 "Activate CONFIG_NTFS3_64BIT_CLUSTER to process this case",
1002 vcn64, lcn, len);
1003 return -EOPNOTSUPP;
1004 }
1005#endif
1006 if (lcn != SPARSE_LCN64 && lcn + len > sbi->used.bitmap.nbits) {
1007 /* LCN range is out of volume. */
1008 return -EINVAL;
1009 }
1010
1011 if (!run)
1012 ; /* Called from check_attr(fslog.c) to check run. */
1013 else if (run == RUN_DEALLOCATE) {
1014 /*
1015 * Called from ni_delete_all to free clusters
1016 * without storing in run.
1017 */
1018 if (lcn != SPARSE_LCN64)
1019 mark_as_free_ex(sbi, lcn, len, true);
1020 } else if (vcn64 >= vcn) {
1021 if (!run_add_entry(run, vcn64, lcn, len, is_mft))
1022 return -ENOMEM;
1023 } else if (next_vcn > vcn) {
1024 u64 dlen = vcn - vcn64;
1025
1026 if (!run_add_entry(run, vcn, lcn + dlen, len - dlen,
1027 is_mft))
1028 return -ENOMEM;
1029 }
1030
1031 vcn64 = next_vcn;
1032 }
1033
1034 if (vcn64 != evcn + 1) {
1035 /* Not expected length of unpacked runs. */
1036 return -EINVAL;
1037 }
1038
1039 return run_buf - run_0;
1040}
1041
1042#ifdef NTFS3_CHECK_FREE_CLST
1043/*
1044 * run_unpack_ex - Unpack packed runs from "run_buf".
1045 *
1046 * Checks unpacked runs to be used in bitmap.
1047 *
1048 * Return: Error if negative, or real used bytes.
1049 */
1050int run_unpack_ex(struct runs_tree *run, struct ntfs_sb_info *sbi, CLST ino,
1051 CLST svcn, CLST evcn, CLST vcn, const u8 *run_buf,
1052 int run_buf_size)
1053{
1054 int ret, err;
1055 CLST next_vcn, lcn, len;
1056 size_t index;
1057 bool ok;
1058 struct wnd_bitmap *wnd;
1059
1060 ret = run_unpack(run, sbi, ino, svcn, evcn, vcn, run_buf, run_buf_size);
1061 if (ret <= 0)
1062 return ret;
1063
1064 if (!sbi->used.bitmap.sb || !run || run == RUN_DEALLOCATE)
1065 return ret;
1066
1067 if (ino == MFT_REC_BADCLUST)
1068 return ret;
1069
1070 next_vcn = vcn = svcn;
1071 wnd = &sbi->used.bitmap;
1072
1073 for (ok = run_lookup_entry(run, vcn, &lcn, &len, &index);
1074 next_vcn <= evcn;
1075 ok = run_get_entry(run, ++index, &vcn, &lcn, &len)) {
1076 if (!ok || next_vcn != vcn)
1077 return -EINVAL;
1078
1079 next_vcn = vcn + len;
1080
1081 if (lcn == SPARSE_LCN)
1082 continue;
1083
1084 if (sbi->flags & NTFS_FLAGS_NEED_REPLAY)
1085 continue;
1086
1087 down_read_nested(&wnd->rw_lock, BITMAP_MUTEX_CLUSTERS);
1088 /* Check for free blocks. */
1089 ok = wnd_is_used(wnd, lcn, len);
1090 up_read(&wnd->rw_lock);
1091 if (ok)
1092 continue;
1093
1094 /* Looks like volume is corrupted. */
1095 ntfs_set_state(sbi, NTFS_DIRTY_ERROR);
1096
1097 if (down_write_trylock(&wnd->rw_lock)) {
1098 /* Mark all zero bits as used in range [lcn, lcn+len). */
1099 size_t done;
1100 err = wnd_set_used_safe(wnd, lcn, len, &done);
1101 up_write(&wnd->rw_lock);
1102 if (err)
1103 return err;
1104 }
1105 }
1106
1107 return ret;
1108}
1109#endif
1110
1111/*
1112 * run_get_highest_vcn
1113 *
1114 * Return the highest vcn from a mapping pairs array
1115 * it used while replaying log file.
1116 */
1117int run_get_highest_vcn(CLST vcn, const u8 *run_buf, u64 *highest_vcn)
1118{
1119 u64 vcn64 = vcn;
1120 u8 size_size;
1121
1122 while ((size_size = *run_buf & 0xF)) {
1123 u8 offset_size = *run_buf++ >> 4;
1124 u64 len;
1125
1126 if (size_size > 8 || offset_size > 8)
1127 return -EINVAL;
1128
1129 len = run_unpack_s64(run_buf, size_size, 0);
1130 if (!len)
1131 return -EINVAL;
1132
1133 run_buf += size_size + offset_size;
1134 vcn64 += len;
1135
1136#ifndef CONFIG_NTFS3_64BIT_CLUSTER
1137 if (vcn64 > 0x100000000ull)
1138 return -EINVAL;
1139#endif
1140 }
1141
1142 *highest_vcn = vcn64 - 1;
1143 return 0;
1144}
1145
1146/*
1147 * run_clone
1148 *
1149 * Make a copy of run
1150 */
1151int run_clone(const struct runs_tree *run, struct runs_tree *new_run)
1152{
1153 size_t bytes = run->count * sizeof(struct ntfs_run);
1154
1155 if (bytes > new_run->allocated) {
1156 struct ntfs_run *new_ptr = kvmalloc(bytes, GFP_KERNEL);
1157
1158 if (!new_ptr)
1159 return -ENOMEM;
1160
1161 kvfree(new_run->runs);
1162 new_run->runs = new_ptr;
1163 new_run->allocated = bytes;
1164 }
1165
1166 memcpy(new_run->runs, run->runs, bytes);
1167 new_run->count = run->count;
1168 return 0;
1169}