xref: /openbmc/linux/fs/ntfs3/run.c (revision b18d2847)
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