Merge git://github.com/Paragon-Software-Group/linux-ntfs3

Merge NTFSv3 filesystem from Konstantin Komarov:
 "This patch adds NTFS Read-Write driver to fs/ntfs3.

  Having decades of expertise in commercial file systems development and
  huge test coverage, we at Paragon Software GmbH want to make our
  contribution to the Open Source Community by providing implementation
  of NTFS Read-Write driver for the Linux Kernel.

  This is fully functional NTFS Read-Write driver. Current version works
  with NTFS (including v3.1) and normal/compressed/sparse files and
  supports journal replaying.

  We plan to support this version after the codebase once merged, and
  add new features and fix bugs. For example, full journaling support
  over JBD will be added in later updates"

Link: https://lore.kernel.org/lkml/20210729134943.778917-1-almaz.alexandrovich@paragon-software.com/
Link: https://lore.kernel.org/lkml/aa4aa155-b9b2-9099-b7a2-349d8d9d8fbd@paragon-software.com/

* git://github.com/Paragon-Software-Group/linux-ntfs3: (35 commits)
  fs/ntfs3: Change how module init/info messages are displayed
  fs/ntfs3: Remove GPL boilerplates from decompress lib files
  fs/ntfs3: Remove unnecessary condition checking from ntfs_file_read_iter
  fs/ntfs3: Fix integer overflow in ni_fiemap with fiemap_prep()
  fs/ntfs3: Restyle comments to better align with kernel-doc
  fs/ntfs3: Rework file operations
  fs/ntfs3: Remove fat ioctl's from ntfs3 driver for now
  fs/ntfs3: Restyle comments to better align with kernel-doc
  fs/ntfs3: Fix error handling in indx_insert_into_root()
  fs/ntfs3: Potential NULL dereference in hdr_find_split()
  fs/ntfs3: Fix error code in indx_add_allocate()
  fs/ntfs3: fix an error code in ntfs_get_acl_ex()
  fs/ntfs3: add checks for allocation failure
  fs/ntfs3: Use kcalloc/kmalloc_array over kzalloc/kmalloc
  fs/ntfs3: Do not use driver own alloc wrappers
  fs/ntfs3: Use kernel ALIGN macros over driver specific
  fs/ntfs3: Restyle comment block in ni_parse_reparse()
  fs/ntfs3: Remove unused including <linux/version.h>
  fs/ntfs3: Fix fall-through warnings for Clang
  fs/ntfs3: Fix one none utf8 char in source file
  ...

1 files changed, 1113 insertions, 0 deletions

diff --git a/fs/ntfs3/run.c b/fs/ntfs3/run.c
new file mode 100644
index 000000000000..26ed2b64345e
--- /dev/null
+++ b/fs/ntfs3/run.c
@@ -0,0 +1,1113 @@
+// 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/buffer_head.h>
+#include <linux/fs.h>
+#include <linux/log2.h>
+#include <linux/nls.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.
+ */
+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_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 jocode.
+		 */
+		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)
+{
+	size_t index, eat;
+	struct ntfs_run *r, *e, *eat_start, *eat_end;
+	CLST end;
+
+	if (WARN_ON(!run_lookup(run, vcn, &index)))
+		return true; /* Should never be here. */
+
+	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);
+		}
+
+		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;
+
+	return true;
+}
+
+/*
+ * 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;
+	int packed_size = 0;
+	size_t i;
+	bool ok;
+	s64 dlcn;
+	int offset_size, size_size, tmp;
+
+	next_vcn = vcn = svcn;
+
+	*packed_vcns = 0;
+
+	if (!len)
+		goto out;
+
+	ok = run_lookup_entry(run, vcn, &lcn, &len, &i);
+
+	if (!ok)
+		goto error;
+
+	if (next_vcn != vcn)
+		goto error;
+
+	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;
+
+		ok = run_get_entry(run, ++i, &vcn, &lcn, &len);
+		if (!ok)
+			goto error;
+
+		if (next_vcn != vcn)
+			goto error;
+	}
+
+out:
+	/* Store last zero. */
+	if (run_buf)
+		run_buf[0] = 0;
+
+	return packed_size + 1;
+
+error:
+	return -EOPNOTSUPP;
+}
+
+/*
+ * 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,
+	       u32 run_buf_size)
+{
+	u64 prev_lcn, vcn64, lcn, next_vcn;
+	const u8 *run_last, *run_0;
+	bool is_mft = ino == MFT_REC_MFT;
+
+	/* 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 > 8)
+			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 <= 8) {
+			s64 dlcn;
+
+			/* 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;
+			lcn = prev_lcn + dlcn;
+			prev_lcn = lcn;
+		} else
+			return -EINVAL;
+
+		next_vcn = vcn64 + len;
+		/* 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 && lcn + len > 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,
+		  u32 run_buf_size)
+{
+	int ret, err;
+	CLST next_vcn, lcn, len;
+	size_t index;
+	bool ok;
+	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);
+		/* Check for free blocks. */
+		ok = 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)) {
+			/* Mark all zero bits as used in range [lcn, lcn+len). */
+			CLST i, lcn_f = 0, len_f = 0;
+
+			err = 0;
+			for (i = 0; i < len; i++) {
+				if (wnd_is_free(wnd, lcn + i, 1)) {
+					if (!len_f)
+						lcn_f = lcn + i;
+					len_f += 1;
+				} else if (len_f) {
+					err = wnd_set_used(wnd, lcn_f, len_f);
+					len_f = 0;
+					if (err)
+						break;
+				}
+			}
+
+			if (len_f)
+				err = wnd_set_used(wnd, lcn_f, len_f);
+
+			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, u64 *highest_vcn)
+{
+	u64 vcn64 = vcn;
+	u8 size_size;
+
+	while ((size_size = *run_buf & 0xF)) {
+		u8 offset_size = *run_buf++ >> 4;
+		u64 len;
+
+		if (size_size > 8 || offset_size > 8)
+			return -EINVAL;
+
+		len = run_unpack_s64(run_buf, size_size, 0);
+		if (!len)
+			return -EINVAL;
+
+		run_buf += size_size + offset_size;
+		vcn64 += len;
+
+#ifndef CONFIG_NTFS3_64BIT_CLUSTER
+		if (vcn64 > 0x100000000ull)
+			return -EINVAL;
+#endif
+	}
+
+	*highest_vcn = vcn64 - 1;
+	return 0;
+}