xref: /linux/fs/ntfs3/run.c (revision dc83d18cdd90482c70fa4320160bba70ec5c9ef8)

// SPDX-License-Identifier: GPL-2.0
/*
 *
 * Copyright (C) 2019-2021 Paragon Software GmbH, All rights reserved.
 *
 * TODO: try to use extents tree (instead of array)
 */

#include <linux/blkdev.h>
#include <linux/fs.h>
#include <linux/log2.h>
#include <linux/overflow.h>

#include "debug.h"
#include "ntfs.h"
#include "ntfs_fs.h"

/* runs_tree is a continues memory. Try to avoid big size. */
#define NTFS3_RUN_MAX_BYTES 0x10000

struct ntfs_run {
	CLST vcn; /* Virtual cluster number. */
	CLST len; /* Length in clusters. */
	CLST lcn; /* Logical cluster number. */
};

/*
 * run_lookup - Lookup the index of a MCB entry that is first <= vcn.
 *
 * Case of success it will return non-zero value and set
 * @index parameter to index of entry been found.
 * Case of entry missing from list 'index' will be set to
 * point to insertion position for the entry question.
 */
static bool run_lookup(const struct runs_tree *run, CLST vcn, size_t *index)
{
	size_t min_idx, max_idx, mid_idx;
	struct ntfs_run *r;

	if (!run->count) {
		*index = 0;
		return false;
	}

	min_idx = 0;
	max_idx = run->count - 1;

	/* Check boundary cases specially, 'cause they cover the often requests. */
	r = run->runs;
	if (vcn < r->vcn) {
		*index = 0;
		return false;
	}

	if (vcn < r->vcn + r->len) {
		*index = 0;
		return true;
	}

	r += max_idx;
	if (vcn >= r->vcn + r->len) {
		*index = run->count;
		return false;
	}

	if (vcn >= r->vcn) {
		*index = max_idx;
		return true;
	}

	do {
		mid_idx = min_idx + ((max_idx - min_idx) >> 1);
		r = run->runs + mid_idx;

		if (vcn < r->vcn) {
			max_idx = mid_idx - 1;
			if (!mid_idx)
				break;
		} else if (vcn >= r->vcn + r->len) {
			min_idx = mid_idx + 1;
		} else {
			*index = mid_idx;
			return true;
		}
	} while (min_idx <= max_idx);

	*index = max_idx + 1;
	return false;
}

/*
 * run_consolidate - Consolidate runs starting from a given one.
 */
static void run_consolidate(struct runs_tree *run, size_t index)
{
	size_t i;
	struct ntfs_run *r = run->runs + index;

	while (index + 1 < run->count) {
		/*
		 * I should merge current run with next
		 * if start of the next run lies inside one being tested.
		 */
		struct ntfs_run *n = r + 1;
		CLST end = r->vcn + r->len;
		CLST dl;

		/* Stop if runs are not aligned one to another. */
		if (n->vcn > end)
			break;

		dl = end - n->vcn;

		/*
		 * If range at index overlaps with next one
		 * then I will either adjust it's start position
		 * or (if completely matches) dust remove one from the list.
		 */
		if (dl > 0) {
			if (n->len <= dl)
				goto remove_next_range;

			n->len -= dl;
			n->vcn += dl;
			if (n->lcn != SPARSE_LCN)
				n->lcn += dl;
			dl = 0;
		}

		/*
		 * Stop if sparse mode does not match
		 * both current and next runs.
		 */
		if ((n->lcn == SPARSE_LCN) != (r->lcn == SPARSE_LCN)) {
			index += 1;
			r = n;
			continue;
		}

		/*
		 * Check if volume block
		 * of a next run lcn does not match
		 * last volume block of the current run.
		 */
		if (n->lcn != SPARSE_LCN && n->lcn != r->lcn + r->len)
			break;

		/*
		 * Next and current are siblings.
		 * Eat/join.
		 */
		r->len += n->len - dl;

remove_next_range:
		i = run->count - (index + 1);
		if (i > 1)
			memmove(n, n + 1, sizeof(*n) * (i - 1));

		run->count -= 1;
	}
}

/*
 * run_is_mapped_full
 *
 * Return: True if range [svcn - evcn] is mapped.
 */
bool run_is_mapped_full(const struct runs_tree *run, CLST svcn, CLST evcn)
{
	size_t i;
	const struct ntfs_run *r, *end;
	CLST next_vcn;

	if (!run_lookup(run, svcn, &i))
		return false;

	end = run->runs + run->count;
	r = run->runs + i;

	for (;;) {
		next_vcn = r->vcn + r->len;
		if (next_vcn > evcn)
			return true;

		if (++r >= end)
			return false;

		if (r->vcn != next_vcn)
			return false;
	}
}

bool run_lookup_entry(const struct runs_tree *run, CLST vcn, CLST *lcn,
		      CLST *len, size_t *index)
{
	size_t idx;
	CLST gap;
	struct ntfs_run *r;

	/* Fail immediately if nrun was not touched yet. */
	if (!run->runs)
		return false;

	if (!run_lookup(run, vcn, &idx))
		return false;

	r = run->runs + idx;

	if (vcn >= r->vcn + r->len)
		return false;

	gap = vcn - r->vcn;
	if (r->len <= gap)
		return false;

	*lcn = r->lcn == SPARSE_LCN ? SPARSE_LCN : (r->lcn + gap);

	if (len)
		*len = r->len - gap;
	if (index)
		*index = idx;

	return true;
}

/*
 * run_overlaps
 *
 * true if run overlaps with range [svcn, svcn + len)
 */
static bool run_overlaps(const struct runs_tree *run, CLST svcn, CLST len,
			 CLST *vcn, CLST *clen)
{
	size_t i;
	const struct ntfs_run *r = run->runs;
	CLST end = svcn + len;

	for (i = 0; i < run->count; i++, r++) {
		/* Check if [r->vcn, r->vcn+r->len) overlaps [svcn, end). */
		if (r->vcn < end && svcn < r->vcn + r->len) {
			if (vcn)
				*vcn = r->vcn;
			if (clen)
				*clen = r->len;
			return true;
		}
	}

	return false;
}

/*
 * run_lookup_entry_da
 *
 * - lookup vcn in delalloc run
 * - lookup vcn in real run
 * - correct result if real run overlaps with delalloc
 */
bool run_lookup_entry_da(const struct runs_tree *run,
			 const struct runs_tree *run_da, CLST vcn, CLST *lcn,
			 CLST *len)
{
	CLST vcn1, len1;

	if (run_da && run_lookup_entry(run_da, vcn, lcn, len, NULL)) {
		*lcn = DELALLOC_LCN;
		return true;
	}

	if (!run_lookup_entry(run, vcn, lcn, len, NULL))
		return false;

	if (run_da && run_overlaps(run_da, vcn, *len, &vcn1, &len1)) {
		/* Correct return value. */
		if (vcn1 > vcn) {
			*len = vcn1 - vcn;
		} else {
			*lcn = DELALLOC_LCN;
			*len = len1;
		}
	}

	return true;
}

/*
 * run_truncate_head - Decommit the range before vcn.
 */
void run_truncate_head(struct runs_tree *run, CLST vcn)
{
	size_t index;
	struct ntfs_run *r;

	if (run_lookup(run, vcn, &index)) {
		r = run->runs + index;

		if (vcn > r->vcn) {
			CLST dlen = vcn - r->vcn;

			r->vcn = vcn;
			r->len -= dlen;
			if (r->lcn != SPARSE_LCN)
				r->lcn += dlen;
		}

		if (!index)
			return;
	}
	r = run->runs;
	memmove(r, r + index, sizeof(*r) * (run->count - index));

	run->count -= index;

	if (!run->count) {
		kvfree(run->runs);
		run->runs = NULL;
		run->allocated = 0;
	}
}

/*
 * run_truncate - Decommit the range after vcn.
 */
void run_truncate(struct runs_tree *run, CLST vcn)
{
	size_t index;

	/*
	 * If I hit the range then
	 * I have to truncate one.
	 * If range to be truncated is becoming empty
	 * then it will entirely be removed.
	 */
	if (run_lookup(run, vcn, &index)) {
		struct ntfs_run *r = run->runs + index;

		r->len = vcn - r->vcn;

		if (r->len > 0)
			index += 1;
	}

	/*
	 * At this point 'index' is set to position that
	 * should be thrown away (including index itself)
	 * Simple one - just set the limit.
	 */
	run->count = index;

	/* Do not reallocate array 'runs'. Only free if possible. */
	if (!index) {
		kvfree(run->runs);
		run->runs = NULL;
		run->allocated = 0;
	}
}

/*
 * run_truncate_around - Trim head and tail if necessary.
 */
void run_truncate_around(struct runs_tree *run, CLST vcn)
{
	run_truncate_head(run, vcn);

	if (run->count >= NTFS3_RUN_MAX_BYTES / sizeof(struct ntfs_run) / 2)
		run_truncate(run, (run->runs + (run->count >> 1))->vcn);
}

/*
 * run_add_entry
 *
 * Sets location to known state.
 * Run to be added may overlap with existing location.
 *
 * Return: false if of memory.
 */
bool run_add_entry(struct runs_tree *run, CLST vcn, CLST lcn, CLST len,
		   bool is_mft)
{
	size_t used, index;
	struct ntfs_run *r;
	bool inrange;
	CLST tail_vcn = 0, tail_len = 0, tail_lcn = 0;
	bool should_add_tail = false;

	/*
	 * Lookup the insertion point.
	 *
	 * Execute bsearch for the entry containing
	 * start position question.
	 */
	inrange = run_lookup(run, vcn, &index);

	/*
	 * Shortcut here would be case of
	 * range not been found but one been added
	 * continues previous run.
	 * This case I can directly make use of
	 * existing range as my start point.
	 */
	if (!inrange && index > 0) {
		struct ntfs_run *t = run->runs + index - 1;

		if (t->vcn + t->len == vcn &&
		    (t->lcn == SPARSE_LCN) == (lcn == SPARSE_LCN) &&
		    (lcn == SPARSE_LCN || lcn == t->lcn + t->len)) {
			inrange = true;
			index -= 1;
		}
	}

	/*
	 * At this point 'index' either points to the range
	 * containing start position or to the insertion position
	 * for a new range.
	 * So first let's check if range I'm probing is here already.
	 */
	if (!inrange) {
requires_new_range:
		/*
		 * Range was not found.
		 * Insert at position 'index'
		 */
		used = run->count * sizeof(struct ntfs_run);

		/*
		 * Check allocated space.
		 * If one is not enough to get one more entry
		 * then it will be reallocated.
		 */
		if (run->allocated < used + sizeof(struct ntfs_run)) {
			size_t bytes;
			struct ntfs_run *new_ptr;

			/* Use power of 2 for 'bytes'. */
			if (!used) {
				bytes = 64;
			} else if (used <= 16 * PAGE_SIZE) {
				if (is_power_of_2(run->allocated))
					bytes = run->allocated << 1;
				else
					bytes = (size_t)1
						<< (2 + blksize_bits(used));
			} else {
				bytes = run->allocated + (16 * PAGE_SIZE);
			}

			WARN_ON(!is_mft && bytes > NTFS3_RUN_MAX_BYTES);

			new_ptr = kvmalloc(bytes, GFP_KERNEL);

			if (!new_ptr)
				return false;

			r = new_ptr + index;
			memcpy(new_ptr, run->runs,
			       index * sizeof(struct ntfs_run));
			memcpy(r + 1, run->runs + index,
			       sizeof(struct ntfs_run) * (run->count - index));

			kvfree(run->runs);
			run->runs = new_ptr;
			run->allocated = bytes;

		} else {
			size_t i = run->count - index;

			r = run->runs + index;

			/* memmove appears to be a bottle neck here... */
			if (i > 0)
				memmove(r + 1, r, sizeof(struct ntfs_run) * i);
		}

		r->vcn = vcn;
		r->lcn = lcn;
		r->len = len;
		run->count += 1;
	} else {
		r = run->runs + index;

		/*
		 * If one of ranges was not allocated then we
		 * have to split location we just matched and
		 * insert current one.
		 * A common case this requires tail to be reinserted
		 * a recursive call.
		 */
		if (((lcn == SPARSE_LCN) != (r->lcn == SPARSE_LCN)) ||
		    (lcn != SPARSE_LCN && lcn != r->lcn + (vcn - r->vcn))) {
			CLST to_eat = vcn - r->vcn;
			CLST Tovcn = to_eat + len;

			should_add_tail = Tovcn < r->len;

			if (should_add_tail) {
				tail_lcn = r->lcn == SPARSE_LCN ?
						   SPARSE_LCN :
						   (r->lcn + Tovcn);
				tail_vcn = r->vcn + Tovcn;
				tail_len = r->len - Tovcn;
			}

			if (to_eat > 0) {
				r->len = to_eat;
				inrange = false;
				index += 1;
				goto requires_new_range;
			}

			/* lcn should match one were going to add. */
			r->lcn = lcn;
		}

		/*
		 * If existing range fits then were done.
		 * Otherwise extend found one and fall back to range join code.
		 */
		if (r->vcn + r->len < vcn + len)
			r->len += len - ((r->vcn + r->len) - vcn);
	}

	/*
	 * And normalize it starting from insertion point.
	 * It's possible that no insertion needed case if
	 * start point lies within the range of an entry
	 * that 'index' points to.
	 */
	if (inrange && index > 0)
		index -= 1;
	run_consolidate(run, index);
	run_consolidate(run, index + 1);

	/*
	 * A special case.
	 * We have to add extra range a tail.
	 */
	if (should_add_tail &&
	    !run_add_entry(run, tail_vcn, tail_lcn, tail_len, is_mft))
		return false;

	return true;
}

/*
 * run_collapse_range
 *
 * Helper for attr_collapse_range(),
 * which is helper for fallocate(collapse_range).
 */
bool run_collapse_range(struct runs_tree *run, CLST vcn, CLST len, CLST sub)
{
	size_t index, eat;
	struct ntfs_run *r, *e, *eat_start, *eat_end;
	CLST end;

	if (!run_lookup(run, vcn, &index) && index >= run->count) {
		return true;
	}

	e = run->runs + run->count;
	r = run->runs + index;
	end = vcn + len;

	if (vcn > r->vcn) {
		if (r->vcn + r->len <= end) {
			/* Collapse tail of run .*/
			r->len = vcn - r->vcn;
		} else if (r->lcn == SPARSE_LCN) {
			/* Collapse a middle part of sparsed run. */
			r->len -= len;
		} else {
			/* Collapse a middle part of normal run, split. */
			if (!run_add_entry(run, vcn, SPARSE_LCN, len, false))
				return false;
			return run_collapse_range(run, vcn, len, sub);
		}

		r += 1;
	}

	eat_start = r;
	eat_end = r;

	for (; r < e; r++) {
		CLST d;

		if (r->vcn >= end) {
			r->vcn -= len;
			continue;
		}

		if (r->vcn + r->len <= end) {
			/* Eat this run. */
			eat_end = r + 1;
			continue;
		}

		d = end - r->vcn;
		if (r->lcn != SPARSE_LCN)
			r->lcn += d;
		r->len -= d;
		r->vcn -= len - d;
	}

	eat = eat_end - eat_start;
	memmove(eat_start, eat_end, (e - eat_end) * sizeof(*r));
	run->count -= eat;

	if (sub) {
		e -= eat;
		for (r = run->runs; r < e; r++) {
			r->vcn -= sub;
		}
	}

	return true;
}

/* run_insert_range
 *
 * Helper for attr_insert_range(),
 * which is helper for fallocate(insert_range).
 */
int run_insert_range(struct runs_tree *run, CLST vcn, CLST len)
{
	size_t index;
	struct ntfs_run *r, *e;

	if (WARN_ON(!run_lookup(run, vcn, &index)))
		return -EINVAL; /* Should never be here. */

	e = run->runs + run->count;
	r = run->runs + index;

	if (vcn > r->vcn)
		r += 1;

	for (; r < e; r++)
		r->vcn += len;

	r = run->runs + index;

	if (vcn > r->vcn) {
		/* split fragment. */
		CLST len1 = vcn - r->vcn;
		CLST len2 = r->len - len1;
		CLST lcn2 = r->lcn == SPARSE_LCN ? SPARSE_LCN : (r->lcn + len1);

		r->len = len1;

		if (!run_add_entry(run, vcn + len, lcn2, len2, false))
			return -ENOMEM;
	}

	if (!run_add_entry(run, vcn, SPARSE_LCN, len, false))
		return -ENOMEM;

	return 0;
}

/* run_insert_range_da
 *
 * Helper for attr_insert_range(),
 * which is helper for fallocate(insert_range).
 */
int run_insert_range_da(struct runs_tree *run, CLST vcn, CLST len)
{
	struct ntfs_run *r, *r0 = NULL, *e = run->runs + run->count;
	;

	for (r = run->runs; r < e; r++) {
		CLST end = r->vcn + r->len;

		if (vcn >= end)
			continue;

		if (!r0 && r->vcn < vcn) {
			r0 = r;
		} else {
			r->vcn += len;
		}
	}

	if (r0) {
		/* split fragment. */
		CLST len1 = vcn - r0->vcn;
		CLST len2 = r0->len - len1;

		r0->len = len1;
		if (!run_add_entry(run, vcn + len, SPARSE_LCN, len2, false))
			return -ENOMEM;
	}

	return 0;
}

/*
 * run_get_entry - Return index-th mapped region.
 */
bool run_get_entry(const struct runs_tree *run, size_t index, CLST *vcn,
		   CLST *lcn, CLST *len)
{
	const struct ntfs_run *r;

	if (index >= run->count)
		return false;

	r = run->runs + index;

	if (!r->len)
		return false;

	if (vcn)
		*vcn = r->vcn;
	if (lcn)
		*lcn = r->lcn;
	if (len)
		*len = r->len;
	return true;
}

/*
 * run_packed_size - Calculate the size of packed int64.
 */
#ifdef __BIG_ENDIAN
static inline int run_packed_size(const s64 n)
{
	const u8 *p = (const u8 *)&n + sizeof(n) - 1;

	if (n >= 0) {
		if (p[-7] || p[-6] || p[-5] || p[-4])
			p -= 4;
		if (p[-3] || p[-2])
			p -= 2;
		if (p[-1])
			p -= 1;
		if (p[0] & 0x80)
			p -= 1;
	} else {
		if (p[-7] != 0xff || p[-6] != 0xff || p[-5] != 0xff ||
		    p[-4] != 0xff)
			p -= 4;
		if (p[-3] != 0xff || p[-2] != 0xff)
			p -= 2;
		if (p[-1] != 0xff)
			p -= 1;
		if (!(p[0] & 0x80))
			p -= 1;
	}
	return (const u8 *)&n + sizeof(n) - p;
}

/* Full trusted function. It does not check 'size' for errors. */
static inline void run_pack_s64(u8 *run_buf, u8 size, s64 v)
{
	const u8 *p = (u8 *)&v;

	switch (size) {
	case 8:
		run_buf[7] = p[0];
		fallthrough;
	case 7:
		run_buf[6] = p[1];
		fallthrough;
	case 6:
		run_buf[5] = p[2];
		fallthrough;
	case 5:
		run_buf[4] = p[3];
		fallthrough;
	case 4:
		run_buf[3] = p[4];
		fallthrough;
	case 3:
		run_buf[2] = p[5];
		fallthrough;
	case 2:
		run_buf[1] = p[6];
		fallthrough;
	case 1:
		run_buf[0] = p[7];
	}
}

/* Full trusted function. It does not check 'size' for errors. */
static inline s64 run_unpack_s64(const u8 *run_buf, u8 size, s64 v)
{
	u8 *p = (u8 *)&v;

	switch (size) {
	case 8:
		p[0] = run_buf[7];
		fallthrough;
	case 7:
		p[1] = run_buf[6];
		fallthrough;
	case 6:
		p[2] = run_buf[5];
		fallthrough;
	case 5:
		p[3] = run_buf[4];
		fallthrough;
	case 4:
		p[4] = run_buf[3];
		fallthrough;
	case 3:
		p[5] = run_buf[2];
		fallthrough;
	case 2:
		p[6] = run_buf[1];
		fallthrough;
	case 1:
		p[7] = run_buf[0];
	}
	return v;
}

#else

static inline int run_packed_size(const s64 n)
{
	const u8 *p = (const u8 *)&n;

	if (n >= 0) {
		if (p[7] || p[6] || p[5] || p[4])
			p += 4;
		if (p[3] || p[2])
			p += 2;
		if (p[1])
			p += 1;
		if (p[0] & 0x80)
			p += 1;
	} else {
		if (p[7] != 0xff || p[6] != 0xff || p[5] != 0xff ||
		    p[4] != 0xff)
			p += 4;
		if (p[3] != 0xff || p[2] != 0xff)
			p += 2;
		if (p[1] != 0xff)
			p += 1;
		if (!(p[0] & 0x80))
			p += 1;
	}

	return 1 + p - (const u8 *)&n;
}

/* Full trusted function. It does not check 'size' for errors. */
static inline void run_pack_s64(u8 *run_buf, u8 size, s64 v)
{
	const u8 *p = (u8 *)&v;

	/* memcpy( run_buf, &v, size); Is it faster? */
	switch (size) {
	case 8:
		run_buf[7] = p[7];
		fallthrough;
	case 7:
		run_buf[6] = p[6];
		fallthrough;
	case 6:
		run_buf[5] = p[5];
		fallthrough;
	case 5:
		run_buf[4] = p[4];
		fallthrough;
	case 4:
		run_buf[3] = p[3];
		fallthrough;
	case 3:
		run_buf[2] = p[2];
		fallthrough;
	case 2:
		run_buf[1] = p[1];
		fallthrough;
	case 1:
		run_buf[0] = p[0];
	}
}

/* full trusted function. It does not check 'size' for errors */
static inline s64 run_unpack_s64(const u8 *run_buf, u8 size, s64 v)
{
	u8 *p = (u8 *)&v;

	/* memcpy( &v, run_buf, size); Is it faster? */
	switch (size) {
	case 8:
		p[7] = run_buf[7];
		fallthrough;
	case 7:
		p[6] = run_buf[6];
		fallthrough;
	case 6:
		p[5] = run_buf[5];
		fallthrough;
	case 5:
		p[4] = run_buf[4];
		fallthrough;
	case 4:
		p[3] = run_buf[3];
		fallthrough;
	case 3:
		p[2] = run_buf[2];
		fallthrough;
	case 2:
		p[1] = run_buf[1];
		fallthrough;
	case 1:
		p[0] = run_buf[0];
	}
	return v;
}
#endif

/*
 * run_pack - Pack runs into buffer.
 *
 * packed_vcns - How much runs we have packed.
 * packed_size - How much bytes we have used run_buf.
 */
int run_pack(const struct runs_tree *run, CLST svcn, CLST len, u8 *run_buf,
	     u32 run_buf_size, CLST *packed_vcns)
{
	CLST next_vcn, vcn, lcn;
	CLST prev_lcn = 0;
	CLST evcn1 = svcn + len;
	const struct ntfs_run *r, *r_end;
	int packed_size = 0;
	size_t i;
	s64 dlcn;
	int offset_size, size_size, tmp;

	*packed_vcns = 0;

	if (!len)
		goto out;

	/* Check all required entries [svcn, encv1) available. */
	if (!run_lookup(run, svcn, &i))
		return -ENOENT;

	r_end = run->runs + run->count;
	r = run->runs + i;

	for (next_vcn = r->vcn + r->len; next_vcn < evcn1;
	     next_vcn = r->vcn + r->len) {
		if (++r >= r_end || r->vcn != next_vcn)
			return -ENOENT;
	}

	/* Repeat cycle above and pack runs. Assume no errors. */
	r = run->runs + i;
	len = svcn - r->vcn;
	vcn = svcn;
	lcn = r->lcn == SPARSE_LCN ? SPARSE_LCN : (r->lcn + len);
	len = r->len - len;

	for (;;) {
		next_vcn = vcn + len;
		if (next_vcn > evcn1)
			len = evcn1 - vcn;

		/* How much bytes required to pack len. */
		size_size = run_packed_size(len);

		/* offset_size - How much bytes is packed dlcn. */
		if (lcn == SPARSE_LCN) {
			offset_size = 0;
			dlcn = 0;
		} else {
			/* NOTE: lcn can be less than prev_lcn! */
			dlcn = (s64)lcn - prev_lcn;
			offset_size = run_packed_size(dlcn);
			prev_lcn = lcn;
		}

		tmp = run_buf_size - packed_size - 2 - offset_size;
		if (tmp <= 0)
			goto out;

		/* Can we store this entire run. */
		if (tmp < size_size)
			goto out;

		if (run_buf) {
			/* Pack run header. */
			run_buf[0] = ((u8)(size_size | (offset_size << 4)));
			run_buf += 1;

			/* Pack the length of run. */
			run_pack_s64(run_buf, size_size, len);

			run_buf += size_size;
			/* Pack the offset from previous LCN. */
			run_pack_s64(run_buf, offset_size, dlcn);
			run_buf += offset_size;
		}

		packed_size += 1 + offset_size + size_size;
		*packed_vcns += len;

		if (packed_size + 1 >= run_buf_size || next_vcn >= evcn1)
			goto out;

		r += 1;
		vcn = r->vcn;
		lcn = r->lcn;
		len = r->len;
	}

out:
	/* Store last zero. */
	if (run_buf)
		run_buf[0] = 0;

	return packed_size + 1;
}

/*
 * run_unpack - Unpack packed runs from @run_buf.
 *
 * Return: Error if negative, or real used bytes.
 */
int run_unpack(struct runs_tree *run, struct ntfs_sb_info *sbi, CLST ino,
	       CLST svcn, CLST evcn, CLST vcn, const u8 *run_buf,
	       int run_buf_size)
{
	u64 prev_lcn, vcn64, lcn, next_vcn;
	const u8 *run_last, *run_0;
	bool is_mft = ino == MFT_REC_MFT;

	if (run_buf_size < 0)
		return -EINVAL;

	/* Check for empty. */
	if (evcn + 1 == svcn)
		return 0;

	if (evcn < svcn)
		return -EINVAL;

	run_0 = run_buf;
	run_last = run_buf + run_buf_size;
	prev_lcn = 0;
	vcn64 = svcn;

	/* Read all runs the chain. */
	/* size_size - How much bytes is packed len. */
	while (run_buf < run_last) {
		/* size_size - How much bytes is packed len. */
		u8 size_size = *run_buf & 0xF;
		/* offset_size - How much bytes is packed dlcn. */
		u8 offset_size = *run_buf++ >> 4;
		u64 len;

		if (!size_size)
			break;

		/*
		 * Unpack runs.
		 * NOTE: Runs are stored little endian order
		 * "len" is unsigned value, "dlcn" is signed.
		 * Large positive number requires to store 5 bytes
		 * e.g.: 05 FF 7E FF FF 00 00 00
		 */
		if (size_size > sizeof(len))
			return -EINVAL;

		if (run_buf + size_size > run_last)
			return -EINVAL;

		len = run_unpack_s64(run_buf, size_size, 0);
		/* Skip size_size. */
		run_buf += size_size;

		if (!len)
			return -EINVAL;

		if (!offset_size)
			lcn = SPARSE_LCN64;
		else if (offset_size <= sizeof(s64)) {
			s64 dlcn;

			if (run_buf + offset_size > run_last)
				return -EINVAL;

			/* Initial value of dlcn is -1 or 0. */
			dlcn = (run_buf[offset_size - 1] & 0x80) ? (s64)-1 : 0;
			dlcn = run_unpack_s64(run_buf, offset_size, dlcn);
			/* Skip offset_size. */
			run_buf += offset_size;

			if (!dlcn)
				return -EINVAL;

			/* Check special combination: 0 + SPARSE_LCN64. */
			if (!prev_lcn && dlcn == SPARSE_LCN64) {
				lcn = SPARSE_LCN64;
			} else if (check_add_overflow(prev_lcn, dlcn, &lcn)) {
				return -EINVAL;
			}
			prev_lcn = lcn;
		} else {
			/* The size of 'dlcn' can't be > 8. */
			return -EINVAL;
		}

		if (check_add_overflow(vcn64, len, &next_vcn))
			return -EINVAL;

		/* Check boundary. */
		if (next_vcn > evcn + 1)
			return -EINVAL;

#ifndef CONFIG_NTFS3_64BIT_CLUSTER
		if (next_vcn > 0x100000000ull || (lcn + len) > 0x100000000ull) {
			ntfs_err(
				sbi->sb,
				"This driver is compiled without CONFIG_NTFS3_64BIT_CLUSTER (like windows driver).\n"
				"Volume contains 64 bits run: vcn %llx, lcn %llx, len %llx.\n"
				"Activate CONFIG_NTFS3_64BIT_CLUSTER to process this case",
				vcn64, lcn, len);
			return -EOPNOTSUPP;
		}
#endif
		if (lcn != SPARSE_LCN64) {
			u64 lcn_end;

			if (check_add_overflow(lcn, len, &lcn_end))
				return -EINVAL;
			if (lcn_end > sbi->used.bitmap.nbits) {
				/* LCN range is out of volume. */
				return -EINVAL;
			}
		}

		if (!run)
			; /* Called from check_attr(fslog.c) to check run. */
		else if (run == RUN_DEALLOCATE) {
			/*
			 * Called from ni_delete_all to free clusters
			 * without storing in run.
			 */
			if (lcn != SPARSE_LCN64)
				mark_as_free_ex(sbi, lcn, len, true);
		} else if (vcn64 >= vcn) {
			if (!run_add_entry(run, vcn64, lcn, len, is_mft))
				return -ENOMEM;
		} else if (next_vcn > vcn) {
			u64 dlen = vcn - vcn64;

			if (!run_add_entry(run, vcn, lcn + dlen, len - dlen,
					   is_mft))
				return -ENOMEM;
		}

		vcn64 = next_vcn;
	}

	if (vcn64 != evcn + 1) {
		/* Not expected length of unpacked runs. */
		return -EINVAL;
	}

	return run_buf - run_0;
}

#ifdef NTFS3_CHECK_FREE_CLST
/*
 * run_unpack_ex - Unpack packed runs from "run_buf".
 *
 * Checks unpacked runs to be used in bitmap.
 *
 * Return: Error if negative, or real used bytes.
 */
int run_unpack_ex(struct runs_tree *run, struct ntfs_sb_info *sbi, CLST ino,
		  CLST svcn, CLST evcn, CLST vcn, const u8 *run_buf,
		  int run_buf_size)
{
	int ret, err;
	CLST next_vcn, lcn, len;
	size_t index, done;
	bool ok, zone;
	struct wnd_bitmap *wnd;

	ret = run_unpack(run, sbi, ino, svcn, evcn, vcn, run_buf, run_buf_size);
	if (ret <= 0)
		return ret;

	if (!sbi->used.bitmap.sb || !run || run == RUN_DEALLOCATE)
		return ret;

	if (ino == MFT_REC_BADCLUST)
		return ret;

	next_vcn = vcn = svcn;
	wnd = &sbi->used.bitmap;

	for (ok = run_lookup_entry(run, vcn, &lcn, &len, &index);
	     next_vcn <= evcn;
	     ok = run_get_entry(run, ++index, &vcn, &lcn, &len)) {
		if (!ok || next_vcn != vcn)
			return -EINVAL;

		next_vcn = vcn + len;

		if (lcn == SPARSE_LCN)
			continue;

		if (sbi->flags & NTFS_FLAGS_NEED_REPLAY)
			continue;

		down_read_nested(&wnd->rw_lock, BITMAP_MUTEX_CLUSTERS);
		zone = max(wnd->zone_bit, lcn) < min(wnd->zone_end, lcn + len);
		/* Check for free blocks. */
		ok = !zone && wnd_is_used(wnd, lcn, len);
		up_read(&wnd->rw_lock);
		if (ok)
			continue;

		/* Looks like volume is corrupted. */
		ntfs_set_state(sbi, NTFS_DIRTY_ERROR);

		if (!down_write_trylock(&wnd->rw_lock))
			continue;

		if (zone) {
			/*
			 * Range [lcn, lcn + len) intersects with zone.
			 * To avoid complex with zone just turn it off.
			 */
			wnd_zone_set(wnd, 0, 0);
		}

		/* Mark all zero bits as used in range [lcn, lcn+len). */
		err = wnd_set_used_safe(wnd, lcn, len, &done);
		if (zone) {
			/* Restore zone. Lock mft run. */
			struct rw_semaphore *lock =
				is_mounted(sbi) ? &sbi->mft.ni->file.run_lock :
						  NULL;
			if (lock) {
				if (down_read_trylock(lock)) {
					ntfs_refresh_zone(sbi);
					up_read(lock);
				}
			} else {
				ntfs_refresh_zone(sbi);
			}
		}
		up_write(&wnd->rw_lock);
		if (err)
			return err;
	}

	return ret;
}
#endif

/*
 * run_get_highest_vcn
 *
 * Return the highest vcn from a mapping pairs array
 * it used while replaying log file.
 */
int run_get_highest_vcn(CLST vcn, const u8 *run_buf, size_t run_buf_size,
			u64 *highest_vcn)
{
	const u8 *run_last = run_buf + run_buf_size;
	u64 vcn64 = vcn;
	u8 size_size;

	while (run_buf < run_last && (size_size = *run_buf & 0xF)) {
		u8 offset_size = *run_buf++ >> 4;
		u64 len;

		if (size_size > 8 || offset_size > 8)
			return -EINVAL;

		if (run_buf + size_size + offset_size > run_last)
			return -EINVAL;

		len = run_unpack_s64(run_buf, size_size, 0);
		if (!len)
			return -EINVAL;

		run_buf += size_size + offset_size;
		if (check_add_overflow(vcn64, len, &vcn64))
			return -EINVAL;

#ifndef CONFIG_NTFS3_64BIT_CLUSTER
		if (vcn64 > 0x100000000ull)
			return -EINVAL;
#endif
	}

	*highest_vcn = vcn64 - 1;
	return 0;
}

/*
 * run_clone
 *
 * Make a copy of run
 */
int run_clone(const struct runs_tree *run, struct runs_tree *new_run)
{
	size_t bytes = run->count * sizeof(struct ntfs_run);

	if (bytes > new_run->allocated) {
		struct ntfs_run *new_ptr = kvmalloc(bytes, GFP_KERNEL);

		if (!new_ptr)
			return -ENOMEM;

		kvfree(new_run->runs);
		new_run->runs = new_ptr;
		new_run->allocated = bytes;
	}

	memcpy(new_run->runs, run->runs, bytes);
	new_run->count = run->count;
	return 0;
}

/*
 * run_remove_range
 *
 */
bool run_remove_range(struct runs_tree *run, CLST vcn, CLST len, CLST *done)
{
	size_t index, eat;
	struct ntfs_run *r, *e, *eat_start, *eat_end;
	CLST end, d;

	*done = 0;

	/* Fast check. */
	if (!run->count)
		return true;

	if (!run_lookup(run, vcn, &index) && index >= run->count) {
		/* No entries in this run. */
		return true;
	}

	e = run->runs + run->count;
	r = run->runs + index;
	end = vcn + len;

	if (vcn > r->vcn) {
		CLST r_end = r->vcn + r->len;
		d = vcn - r->vcn;

		if (r_end > end) {
			/* Remove a middle part, split. */
			CLST tail_lcn = r->lcn == SPARSE_LCN ?
						SPARSE_LCN :
						(r->lcn + (end - r->vcn));

			*done += len;
			r->len = d;
			return run_add_entry(run, end, tail_lcn, r_end - end,
					     false);
		}
		/* Remove tail of run .*/
		*done += r->len - d;
		r->len = d;
		r += 1;
	}

	eat_start = r;
	eat_end = r;

	for (; r < e; r++) {
		if (r->vcn >= end)
			continue;

		if (r->vcn + r->len <= end) {
			/* Eat this run. */
			*done += r->len;
			eat_end = r + 1;
			continue;
		}

		d = end - r->vcn;
		*done += d;
		if (r->lcn != SPARSE_LCN)
			r->lcn += d;
		r->len -= d;
		r->vcn = end;
	}

	eat = eat_end - eat_start;
	memmove(eat_start, eat_end, (e - eat_end) * sizeof(*r));
	run->count -= eat;

	return true;
}

CLST run_len(const struct runs_tree *run)
{
	const struct ntfs_run *r, *e;
	CLST len = 0;

	for (r = run->runs, e = r + run->count; r < e; r++) {
		len += r->len;
	}

	return len;
}

CLST run_get_max_vcn(const struct runs_tree *run)
{
	const struct ntfs_run *r;
	if (!run->count)
		return 0;

	r = run->runs + run->count - 1;
	return r->vcn + r->len;
}