1 // SPDX-License-Identifier: GPL-2.0
4  * Copyright (C) 2019-2021 Paragon Software GmbH, All rights reserved.
27  * run_lookup - Lookup the index of a MCB entry that is first <= vcn.
29  * Case of success it will return non-zero value and set
39 	if (!run->count) {  in run_lookup()
45 	max_idx = run->count - 1;  in run_lookup()
48 	r = run->runs;  in run_lookup()
49 	if (vcn < r->vcn) {  in run_lookup()
54 	if (vcn < r->vcn + r->len) {  in run_lookup()
60 	if (vcn >= r->vcn + r->len) {  in run_lookup()
61 		*index = run->count;  in run_lookup()
65 	if (vcn >= r->vcn) {  in run_lookup()
71 		mid_idx = min_idx + ((max_idx - min_idx) >> 1);  in run_lookup()
72 		r = run->runs + mid_idx;  in run_lookup()
74 		if (vcn < r->vcn) {  in run_lookup()
75 			max_idx = mid_idx - 1;  in run_lookup()
78 		} else if (vcn >= r->vcn + r->len) {  in run_lookup()
91  * run_consolidate - Consolidate runs starting from a given one.
96 	struct ntfs_run *r = run->runs + index;  in run_consolidate()
98 	while (index + 1 < run->count) {  in run_consolidate()
104 		CLST end = r->vcn + r->len;  in run_consolidate()
107 		/* Stop if runs are not aligned one to another. */  in run_consolidate()
108 		if (n->vcn > end)  in run_consolidate()
111 		dl = end - n->vcn;  in run_consolidate()
119 			if (n->len <= dl)  in run_consolidate()
122 			n->len -= dl;  in run_consolidate()
123 			n->vcn += dl;  in run_consolidate()
124 			if (n->lcn != SPARSE_LCN)  in run_consolidate()
125 				n->lcn += dl;  in run_consolidate()
131 		 * both current and next runs.  in run_consolidate()
133 		if ((n->lcn == SPARSE_LCN) != (r->lcn == SPARSE_LCN)) {  in run_consolidate()
144 		if (n->lcn != SPARSE_LCN && n->lcn != r->lcn + r->len)  in run_consolidate()
151 		r->len += n->len - dl;  in run_consolidate()
154 		i = run->count - (index + 1);  in run_consolidate()
156 			memmove(n, n + 1, sizeof(*n) * (i - 1));  in run_consolidate()
158 		run->count -= 1;  in run_consolidate()
165  * Return: True if range [svcn - evcn] is mapped.
176 	end = run->runs + run->count;  in run_is_mapped_full()
177 	r = run->runs + i;  in run_is_mapped_full()
180 		next_vcn = r->vcn + r->len;  in run_is_mapped_full()
187 		if (r->vcn != next_vcn)  in run_is_mapped_full()
200 	if (!run->runs)  in run_lookup_entry()
206 	r = run->runs + idx;  in run_lookup_entry()
208 	if (vcn >= r->vcn + r->len)  in run_lookup_entry()
211 	gap = vcn - r->vcn;  in run_lookup_entry()
212 	if (r->len <= gap)  in run_lookup_entry()
215 	*lcn = r->lcn == SPARSE_LCN ? SPARSE_LCN : (r->lcn + gap);  in run_lookup_entry()
218 		*len = r->len - gap;  in run_lookup_entry()
226  * run_truncate_head - Decommit the range before vcn.
234 		r = run->runs + index;  in run_truncate_head()
236 		if (vcn > r->vcn) {  in run_truncate_head()
237 			CLST dlen = vcn - r->vcn;  in run_truncate_head()
239 			r->vcn = vcn;  in run_truncate_head()
240 			r->len -= dlen;  in run_truncate_head()
241 			if (r->lcn != SPARSE_LCN)  in run_truncate_head()
242 				r->lcn += dlen;  in run_truncate_head()
248 	r = run->runs;  in run_truncate_head()
249 	memmove(r, r + index, sizeof(*r) * (run->count - index));  in run_truncate_head()
251 	run->count -= index;  in run_truncate_head()
253 	if (!run->count) {  in run_truncate_head()
254 		kvfree(run->runs);  in run_truncate_head()
255 		run->runs = NULL;  in run_truncate_head()
256 		run->allocated = 0;  in run_truncate_head()
261  * run_truncate - Decommit the range after vcn.
274 		struct ntfs_run *r = run->runs + index;  in run_truncate()
276 		r->len = vcn - r->vcn;  in run_truncate()
278 		if (r->len > 0)  in run_truncate()
285 	 * Simple one - just set the limit.  in run_truncate()
287 	run->count = index;  in run_truncate()
289 	/* Do not reallocate array 'runs'. Only free if possible. */  in run_truncate()
291 		kvfree(run->runs);  in run_truncate()
292 		run->runs = NULL;  in run_truncate()
293 		run->allocated = 0;  in run_truncate()
298  * run_truncate_around - Trim head and tail if necessary.
304 	if (run->count >= NTFS3_RUN_MAX_BYTES / sizeof(struct ntfs_run) / 2)  in run_truncate_around()
305 		run_truncate(run, (run->runs + (run->count >> 1))->vcn);  in run_truncate_around()
341 		struct ntfs_run *t = run->runs + index - 1;  in run_add_entry()
343 		if (t->vcn + t->len == vcn &&  in run_add_entry()
344 		    (t->lcn == SPARSE_LCN) == (lcn == SPARSE_LCN) &&  in run_add_entry()
345 		    (lcn == SPARSE_LCN || lcn == t->lcn + t->len)) {  in run_add_entry()
347 			index -= 1;  in run_add_entry()
363 		used = run->count * sizeof(struct ntfs_run);  in run_add_entry()
370 		if (run->allocated < used + sizeof(struct ntfs_run)) {  in run_add_entry()
378 				if (is_power_of_2(run->allocated))  in run_add_entry()
379 					bytes = run->allocated << 1;  in run_add_entry()
384 				bytes = run->allocated + (16 * PAGE_SIZE);  in run_add_entry()
395 			memcpy(new_ptr, run->runs,  in run_add_entry()
397 			memcpy(r + 1, run->runs + index,  in run_add_entry()
398 			       sizeof(struct ntfs_run) * (run->count - index));  in run_add_entry()
400 			kvfree(run->runs);  in run_add_entry()
401 			run->runs = new_ptr;  in run_add_entry()
402 			run->allocated = bytes;  in run_add_entry()
405 			size_t i = run->count - index;  in run_add_entry()
407 			r = run->runs + index;  in run_add_entry()
414 		r->vcn = vcn;  in run_add_entry()
415 		r->lcn = lcn;  in run_add_entry()
416 		r->len = len;  in run_add_entry()
417 		run->count += 1;  in run_add_entry()
419 		r = run->runs + index;  in run_add_entry()
428 		if (((lcn == SPARSE_LCN) != (r->lcn == SPARSE_LCN)) ||  in run_add_entry()
429 		    (lcn != SPARSE_LCN && lcn != r->lcn + (vcn - r->vcn))) {  in run_add_entry()
430 			CLST to_eat = vcn - r->vcn;  in run_add_entry()
433 			should_add_tail = Tovcn < r->len;  in run_add_entry()
436 				tail_lcn = r->lcn == SPARSE_LCN ?  in run_add_entry()
438 						   (r->lcn + Tovcn);  in run_add_entry()
439 				tail_vcn = r->vcn + Tovcn;  in run_add_entry()
440 				tail_len = r->len - Tovcn;  in run_add_entry()
444 				r->len = to_eat;  in run_add_entry()
451 			r->lcn = lcn;  in run_add_entry()
458 		if (r->vcn + r->len < vcn + len)  in run_add_entry()
459 			r->len += len - ((r->vcn + r->len) - vcn);  in run_add_entry()
469 		index -= 1;  in run_add_entry()
498 	e = run->runs + run->count;  in run_collapse_range()
499 	r = run->runs + index;  in run_collapse_range()
502 	if (vcn > r->vcn) {  in run_collapse_range()
503 		if (r->vcn + r->len <= end) {  in run_collapse_range()
505 			r->len = vcn - r->vcn;  in run_collapse_range()
506 		} else if (r->lcn == SPARSE_LCN) {  in run_collapse_range()
508 			r->len -= len;  in run_collapse_range()
525 		if (r->vcn >= end) {  in run_collapse_range()
526 			r->vcn -= len;  in run_collapse_range()
530 		if (r->vcn + r->len <= end) {  in run_collapse_range()
536 		d = end - r->vcn;  in run_collapse_range()
537 		if (r->lcn != SPARSE_LCN)  in run_collapse_range()
538 			r->lcn += d;  in run_collapse_range()
539 		r->len -= d;  in run_collapse_range()
540 		r->vcn -= len - d;  in run_collapse_range()
543 	eat = eat_end - eat_start;  in run_collapse_range()
544 	memmove(eat_start, eat_end, (e - eat_end) * sizeof(*r));  in run_collapse_range()
545 	run->count -= eat;  in run_collapse_range()
563 	e = run->runs + run->count;  in run_insert_range()
564 	r = run->runs + index;  in run_insert_range()
566 	if (vcn > r->vcn)  in run_insert_range()
570 		r->vcn += len;  in run_insert_range()
572 	r = run->runs + index;  in run_insert_range()
574 	if (vcn > r->vcn) {  in run_insert_range()
576 		CLST len1 = vcn - r->vcn;  in run_insert_range()
577 		CLST len2 = r->len - len1;  in run_insert_range()
578 		CLST lcn2 = r->lcn == SPARSE_LCN ? SPARSE_LCN : (r->lcn + len1);  in run_insert_range()
580 		r->len = len1;  in run_insert_range()
593  * run_get_entry - Return index-th mapped region.
600 	if (index >= run->count)  in run_get_entry()
603 	r = run->runs + index;  in run_get_entry()
605 	if (!r->len)  in run_get_entry()
609 		*vcn = r->vcn;  in run_get_entry()
611 		*lcn = r->lcn;  in run_get_entry()
613 		*len = r->len;  in run_get_entry()
618  * run_packed_size - Calculate the size of packed int64.
623 	const u8 *p = (const u8 *)&n + sizeof(n) - 1;  in run_packed_size()
626 		if (p[-7] || p[-6] || p[-5] || p[-4])  in run_packed_size()
627 			p -= 4;  in run_packed_size()
628 		if (p[-3] || p[-2])  in run_packed_size()
629 			p -= 2;  in run_packed_size()
630 		if (p[-1])  in run_packed_size()
631 			p -= 1;  in run_packed_size()
633 			p -= 1;  in run_packed_size()
635 		if (p[-7] != 0xff || p[-6] != 0xff || p[-5] != 0xff ||  in run_packed_size()
636 		    p[-4] != 0xff)  in run_packed_size()
637 			p -= 4;  in run_packed_size()
638 		if (p[-3] != 0xff || p[-2] != 0xff)  in run_packed_size()
639 			p -= 2;  in run_packed_size()
640 		if (p[-1] != 0xff)  in run_packed_size()
641 			p -= 1;  in run_packed_size()
643 			p -= 1;  in run_packed_size()
645 	return (const u8 *)&n + sizeof(n) - p;  in run_packed_size()
740 	return 1 + p - (const u8 *)&n;  in run_packed_size()
812  * run_pack - Pack runs into buffer.
814  * packed_vcns - How much runs we have packed.
815  * packed_size - How much bytes we have used run_buf.
836 		return -ENOENT;  in run_pack()
838 	r_end = run->runs + run->count;  in run_pack()
839 	r = run->runs + i;  in run_pack()
841 	for (next_vcn = r->vcn + r->len; next_vcn < evcn1;  in run_pack()
842 	     next_vcn = r->vcn + r->len) {  in run_pack()
843 		if (++r >= r_end || r->vcn != next_vcn)  in run_pack()
844 			return -ENOENT;  in run_pack()
847 	/* Repeat cycle above and pack runs. Assume no errors. */  in run_pack()
848 	r = run->runs + i;  in run_pack()
849 	len = svcn - r->vcn;  in run_pack()
851 	lcn = r->lcn == SPARSE_LCN ? SPARSE_LCN : (r->lcn + len);  in run_pack()
852 	len = r->len - len;  in run_pack()
857 			len = evcn1 - vcn;  in run_pack()
862 		/* offset_size - How much bytes is packed dlcn. */  in run_pack()
868 			dlcn = (s64)lcn - prev_lcn;  in run_pack()
873 		tmp = run_buf_size - packed_size - 2 - offset_size;  in run_pack()
902 		vcn = r->vcn;  in run_pack()
903 		lcn = r->lcn;  in run_pack()
904 		len = r->len;  in run_pack()
916  * run_unpack - Unpack packed runs from @run_buf.
929 		return -EINVAL;  in run_unpack()
936 		return -EINVAL;  in run_unpack()
943 	/* Read all runs the chain. */  in run_unpack()
944 	/* size_size - How much bytes is packed len. */  in run_unpack()
946 		/* size_size - How much bytes is packed len. */  in run_unpack()
948 		/* offset_size - How much bytes is packed dlcn. */  in run_unpack()
956 		 * Unpack runs.  in run_unpack()
957 		 * NOTE: Runs are stored little endian order  in run_unpack()
963 			return -EINVAL;  in run_unpack()
970 			return -EINVAL;  in run_unpack()
977 			/* Initial value of dlcn is -1 or 0. */  in run_unpack()
978 			dlcn = (run_buf[offset_size - 1] & 0x80) ? (s64)-1 : 0;  in run_unpack()
984 				return -EINVAL;  in run_unpack()
988 			return -EINVAL;  in run_unpack()
993 			return -EINVAL;  in run_unpack()
998 				sbi->sb,  in run_unpack()
1003 			return -EOPNOTSUPP;  in run_unpack()
1006 		if (lcn != SPARSE_LCN64 && lcn + len > sbi->used.bitmap.nbits) {  in run_unpack()
1008 			return -EINVAL;  in run_unpack()
1022 				return -ENOMEM;  in run_unpack()
1024 			u64 dlen = vcn - vcn64;  in run_unpack()
1026 			if (!run_add_entry(run, vcn, lcn + dlen, len - dlen,  in run_unpack()
1028 				return -ENOMEM;  in run_unpack()
1035 		/* Not expected length of unpacked runs. */  in run_unpack()
1036 		return -EINVAL;  in run_unpack()
1039 	return run_buf - run_0;  in run_unpack()
1044  * run_unpack_ex - Unpack packed runs from "run_buf".
1046  * Checks unpacked runs to be used in bitmap.
1064 	if (!sbi->used.bitmap.sb || !run || run == RUN_DEALLOCATE)  in run_unpack_ex()
1071 	wnd = &sbi->used.bitmap;  in run_unpack_ex()
1077 			return -EINVAL;  in run_unpack_ex()
1084 		if (sbi->flags & NTFS_FLAGS_NEED_REPLAY)  in run_unpack_ex()
1087 		down_read_nested(&wnd->rw_lock, BITMAP_MUTEX_CLUSTERS);  in run_unpack_ex()
1088 		zone = max(wnd->zone_bit, lcn) < min(wnd->zone_end, lcn + len);  in run_unpack_ex()
1091 		up_read(&wnd->rw_lock);  in run_unpack_ex()
1098 		if (!down_write_trylock(&wnd->rw_lock))  in run_unpack_ex()
1114 			lock = is_mounted(sbi) ? &sbi->mft.ni->file.run_lock :  in run_unpack_ex()
1122 		up_write(&wnd->rw_lock);  in run_unpack_ex()
1147 			return -EINVAL;  in run_get_highest_vcn()
1151 			return -EINVAL;  in run_get_highest_vcn()
1158 			return -EINVAL;  in run_get_highest_vcn()
1162 	*highest_vcn = vcn64 - 1;  in run_get_highest_vcn()
1173 	size_t bytes = run->count * sizeof(struct ntfs_run);  in run_clone()
1175 	if (bytes > new_run->allocated) {  in run_clone()
1179 			return -ENOMEM;  in run_clone()
1181 		kvfree(new_run->runs);  in run_clone()
1182 		new_run->runs = new_ptr;  in run_clone()
1183 		new_run->allocated = bytes;  in run_clone()
1186 	memcpy(new_run->runs, run->runs, bytes);  in run_clone()
1187 	new_run->count = run->count;  in run_clone()