path: root/fs/ntfs3/run.c

// 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 "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
 *
 *