fs/ntfs3/run.c

Source file repositories/reference/linux-study-clean/fs/ntfs3/run.c

File Facts

System
Linux kernel
Corpus path
fs/ntfs3/run.c
Extension
.c
Size
27052 bytes
Lines
1356
Domain
Core OS
Bucket
VFS And Filesystem Core
Inferred role
Core OS: implementation source
Status
source implementation candidate

Why This File Exists

Core operating-system implementation surface: boot, tasks, memory, VFS, syscall-facing interfaces, synchronization, credentials, and isolation.

Dependency Surface

Detected Declarations

Annotated Snippet

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;

Annotation

Implementation Notes