runlist.c

linux 内核源代码

		/*
		 * If the logical cluster number (lcn) denotes a hole and we
		 * are on NTFS 3.0+, we don't store it at all, i.e. we need
		 * zero space.  On earlier NTFS versions we just write the lcn
		 * change.  FIXME: Do we need to write the lcn change or just
		 * the lcn in that case?  Not sure as I have never seen this
		 * case on NT4. - We assume that we just need to write the lcn
		 * change until someone tells us otherwise... (AIA)
		 */
		if (likely(rl->lcn >= 0 || vol->major_ver < 3)) {
			/* Write change in lcn. */
			lcn_len = ntfs_write_significant_bytes(dst + 1 +
					len_len, dst_max, rl->lcn - prev_lcn);
			if (unlikely(lcn_len < 0))
				goto size_err;
			prev_lcn = rl->lcn;
		} else
			lcn_len = 0;
		dst_next = dst + len_len + lcn_len + 1;
		if (unlikely(dst_next > dst_max))
			goto size_err;
		/* Update header byte. */
		*dst = lcn_len << 4 | len_len;
		/* Position at next mapping pairs array element. */
		dst = dst_next;
	}
	/* Success. */
	err = 0;
size_err:
	/* Set stop vcn. */
	if (stop_vcn)
		*stop_vcn = rl->vcn;
	/* Add terminator byte. */
	*dst = 0;
	return err;
err_out:
	if (rl->lcn == LCN_RL_NOT_MAPPED)
		err = -EINVAL;
	else
		err = -EIO;
	return err;
}

/**
 * ntfs_rl_truncate_nolock - truncate a runlist starting at a specified vcn
 * @vol:	ntfs volume (needed for error output)
 * @runlist:	runlist to truncate
 * @new_length:	the new length of the runlist in VCNs
 *
 * Truncate the runlist described by @runlist as well as the memory buffer
 * holding the runlist elements to a length of @new_length VCNs.
 *
 * If @new_length lies within the runlist, the runlist elements with VCNs of
 * @new_length and above are discarded.  As a special case if @new_length is
 * zero, the runlist is discarded and set to NULL.
 *
 * If @new_length lies beyond the runlist, a sparse runlist element is added to
 * the end of the runlist @runlist or if the last runlist element is a sparse
 * one already, this is extended.
 *
 * Note, no checking is done for unmapped runlist elements.  It is assumed that
 * the caller has mapped any elements that need to be mapped already.
 *
 * Return 0 on success and -errno on error.
 *
 * Locking: The caller must hold @runlist->lock for writing.
 */
int ntfs_rl_truncate_nolock(const ntfs_volume *vol, runlist *const runlist,
		const s64 new_length)
{
	runlist_element *rl;
	int old_size;

	ntfs_debug("Entering for new_length 0x%llx.", (long long)new_length);
	BUG_ON(!runlist);
	BUG_ON(new_length < 0);
	rl = runlist->rl;
	if (!new_length) {
		ntfs_debug("Freeing runlist.");
		runlist->rl = NULL;
		if (rl)
			ntfs_free(rl);
		return 0;
	}
	if (unlikely(!rl)) {
		/*
		 * Create a runlist consisting of a sparse runlist element of
		 * length @new_length followed by a terminator runlist element.
		 */
		rl = ntfs_malloc_nofs(PAGE_SIZE);
		if (unlikely(!rl)) {
			ntfs_error(vol->sb, "Not enough memory to allocate "
					"runlist element buffer.");
			return -ENOMEM;
		}
		runlist->rl = rl;
		rl[1].length = rl->vcn = 0;
		rl->lcn = LCN_HOLE;
		rl[1].vcn = rl->length = new_length;
		rl[1].lcn = LCN_ENOENT;
		return 0;
	}
	BUG_ON(new_length < rl->vcn);
	/* Find @new_length in the runlist. */
	while (likely(rl->length && new_length >= rl[1].vcn))
		rl++;
	/*
	 * If not at the end of the runlist we need to shrink it.
	 * If at the end of the runlist we need to expand it.
	 */
	if (rl->length) {
		runlist_element *trl;
		bool is_end;

		ntfs_debug("Shrinking runlist.");
		/* Determine the runlist size. */
		trl = rl + 1;
		while (likely(trl->length))
			trl++;
		old_size = trl - runlist->rl + 1;
		/* Truncate the run. */
		rl->length = new_length - rl->vcn;
		/*
		 * If a run was partially truncated, make the following runlist
		 * element a terminator.
		 */
		is_end = false;
		if (rl->length) {
			rl++;
			if (!rl->length)
				is_end = true;
			rl->vcn = new_length;
			rl->length = 0;
		}
		rl->lcn = LCN_ENOENT;
		/* Reallocate memory if necessary. */
		if (!is_end) {
			int new_size = rl - runlist->rl + 1;
			rl = ntfs_rl_realloc(runlist->rl, old_size, new_size);
			if (IS_ERR(rl))
				ntfs_warning(vol->sb, "Failed to shrink "
						"runlist buffer.  This just "
						"wastes a bit of memory "
						"temporarily so we ignore it "
						"and return success.");
			else
				runlist->rl = rl;
		}
	} else if (likely(/* !rl->length && */ new_length > rl->vcn)) {
		ntfs_debug("Expanding runlist.");
		/*
		 * If there is a previous runlist element and it is a sparse
		 * one, extend it.  Otherwise need to add a new, sparse runlist
		 * element.
		 */
		if ((rl > runlist->rl) && ((rl - 1)->lcn == LCN_HOLE))
			(rl - 1)->length = new_length - (rl - 1)->vcn;
		else {
			/* Determine the runlist size. */
			old_size = rl - runlist->rl + 1;
			/* Reallocate memory if necessary. */
			rl = ntfs_rl_realloc(runlist->rl, old_size,
					old_size + 1);
			if (IS_ERR(rl)) {
				ntfs_error(vol->sb, "Failed to expand runlist "
						"buffer, aborting.");
				return PTR_ERR(rl);
			}
			runlist->rl = rl;
			/*
			 * Set @rl to the same runlist element in the new
			 * runlist as before in the old runlist.
			 */
			rl += old_size - 1;
			/* Add a new, sparse runlist element. */
			rl->lcn = LCN_HOLE;
			rl->length = new_length - rl->vcn;
			/* Add a new terminator runlist element. */
			rl++;
			rl->length = 0;
		}
		rl->vcn = new_length;
		rl->lcn = LCN_ENOENT;
	} else /* if (unlikely(!rl->length && new_length == rl->vcn)) */ {
		/* Runlist already has same size as requested. */
		rl->lcn = LCN_ENOENT;
	}
	ntfs_debug("Done.");
	return 0;
}

/**
 * ntfs_rl_punch_nolock - punch a hole into a runlist
 * @vol:	ntfs volume (needed for error output)
 * @runlist:	runlist to punch a hole into
 * @start:	starting VCN of the hole to be created
 * @length:	size of the hole to be created in units of clusters
 *
 * Punch a hole into the runlist @runlist starting at VCN @start and of size
 * @length clusters.
 *
 * Return 0 on success and -errno on error, in which case @runlist has not been
 * modified.
 *
 * If @start and/or @start + @length are outside the runlist return error code
 * -ENOENT.
 *
 * If the runlist contains unmapped or error elements between @start and @start
 * + @length return error code -EINVAL.
 *
 * Locking: The caller must hold @runlist->lock for writing.
 */
int ntfs_rl_punch_nolock(const ntfs_volume *vol, runlist *const runlist,
		const VCN start, const s64 length)
{
	const VCN end = start + length;
	s64 delta;
	runlist_element *rl, *rl_end, *rl_real_end, *trl;
	int old_size;
	bool lcn_fixup = false;

	ntfs_debug("Entering for start 0x%llx, length 0x%llx.",
			(long long)start, (long long)length);
	BUG_ON(!runlist);
	BUG_ON(start < 0);
	BUG_ON(length < 0);
	BUG_ON(end < 0);
	rl = runlist->rl;
	if (unlikely(!rl)) {
		if (likely(!start && !length))
			return 0;
		return -ENOENT;
	}
	/* Find @start in the runlist. */
	while (likely(rl->length && start >= rl[1].vcn))
		rl++;
	rl_end = rl;
	/* Find @end in the runlist. */
	while (likely(rl_end->length && end >= rl_end[1].vcn)) {
		/* Verify there are no unmapped or error elements. */
		if (unlikely(rl_end->lcn < LCN_HOLE))
			return -EINVAL;
		rl_end++;
	}
	/* Check the last element. */
	if (unlikely(rl_end->length && rl_end->lcn < LCN_HOLE))
		return -EINVAL;
	/* This covers @start being out of bounds, too. */
	if (!rl_end->length && end > rl_end->vcn)
		return -ENOENT;
	if (!length)
		return 0;
	if (!rl->length)
		return -ENOENT;
	rl_real_end = rl_end;
	/* Determine the runlist size. */
	while (likely(rl_real_end->length))
		rl_real_end++;
	old_size = rl_real_end - runlist->rl + 1;
	/* If @start is in a hole simply extend the hole. */
	if (rl->lcn == LCN_HOLE) {
		/*
		 * If both @start and @end are in the same sparse run, we are
		 * done.
		 */
		if (end <= rl[1].vcn) {
			ntfs_debug("Done (requested hole is already sparse).");
			return 0;
		}
extend_hole:
		/* Extend the hole. */
		rl->length = end - rl->vcn;
		/* If @end is in a hole, merge it with the current one. */
		if (rl_end->lcn == LCN_HOLE) {
			rl_end++;
			rl->length = rl_end->vcn - rl->vcn;
		}
		/* We have done the hole.  Now deal with the remaining tail. */
		rl++;
		/* Cut out all runlist elements up to @end. */
		if (rl < rl_end)
			memmove(rl, rl_end, (rl_real_end - rl_end + 1) *
					sizeof(*rl));
		/* Adjust the beginning of the tail if necessary. */
		if (end > rl->vcn) {
			delta = end - rl->vcn;
			rl->vcn = end;
			rl->length -= delta;
			/* Only adjust the lcn if it is real. */
			if (rl->lcn >= 0)
				rl->lcn += delta;
		}
shrink_allocation:
		/* Reallocate memory if the allocation changed. */
		if (rl < rl_end) {
			rl = ntfs_rl_realloc(runlist->rl, old_size,
					old_size - (rl_end - rl));
			if (IS_ERR(rl))
				ntfs_warning(vol->sb, "Failed to shrink "
						"runlist buffer.  This just "
						"wastes a bit of memory "
						"temporarily so we ignore it "
						"and return success.");
			else
				runlist->rl = rl;
		}
		ntfs_debug("Done (extend hole).");
		return 0;
	}
	/*
	 * If @start is at the beginning of a run things are easier as there is
	 * no need to split the first run.
	 */
	if (start == rl->vcn) {
		/*
		 * @start is at the beginning of a run.
		 *
		 * If the previous run is sparse, extend its hole.
		 *
		 * If @end is not in the same run, switch the run to be sparse
		 * and extend the newly created hole.
		 *
		 * Thus both of these cases reduce the problem to the above
		 * case of "@start is in a hole".
		 */
		if (rl > runlist->rl && (rl - 1)->lcn == LCN_HOLE) {
			rl--;
			goto extend_hole;
		}
		if (end >= rl[1].vcn) {
			rl->lcn = LCN_HOLE;
			goto extend_hole;
		}
		/*
		 * The final case is when @end is in the same run as @start.
		 * For this need to split the run into two.  One run for the
		 * sparse region between the beginning of the old run, i.e.
		 * @start, and @end and one for the remaining non-sparse
		 * region, i.e. between @end and the end of the old run.
		 */
		trl = ntfs_rl_realloc(runlist->rl, old_size, old_size + 1);
		if (IS_ERR(trl))
			goto enomem_out;
		old_size++;
		if (runlist->rl != trl) {
			rl = trl + (rl - runlist->rl);
			rl_end = trl + (rl_end - runlist->rl);
			rl_real_end = trl + (rl_real_end - runlist->rl);
			runlist->rl = trl;
		}
split_end:
		/* Shift all the runs up by one. */
		memmove(rl + 1, rl, (rl_real_end - rl + 1) * sizeof(*rl));
		/* Finally, setup the two split runs. */
		rl->lcn = LCN_HOLE;
		rl->length = length;
		rl++;
		rl->vcn += length;
		/* Only adjust the lcn if it is real. */
		if (rl->lcn >= 0 || lcn_fixup)
			rl->lcn += length;
		rl->length -= length;
		ntfs_debug("Done (split one).");
		return 0;
	}
	/*
	 * @start is neither in a hole nor at the beginning of a run.
	 *
	 * If @end is in a hole, things are easier as simply truncating the run
	 * @start is in to end at @start - 1, deleting all runs after that up
	 * to @end, and finally extending the beginning of the run @end is in
	 * to be @start is all that is needed.
	 */
	if (rl_end->lcn == LCN_HOLE) {
		/* Truncate the run containing @start. */
		rl->length = start - rl->vcn;
		rl++;
		/* Cut out all runlist elements up to @end. */
		if (rl < rl_end)
			memmove(rl, rl_end, (rl_real_end - rl_end + 1) *
					sizeof(*rl));
		/* Extend the beginning of the run @end is in to be @start. */
		rl->vcn = start;
		rl->length = rl[1].vcn - start;
		goto shrink_allocation;
	}
	/* 
	 * If @end is not in a hole there are still two cases to distinguish.
	 * Either @end is or is not in the same run as @start.
	 *
	 * The second case is easier as it can be reduced to an already solved
	 * problem by truncating the run @start is in to end at @start - 1.
	 * Then, if @end is in the next run need to split the run into a sparse
	 * run followed by a non-sparse run (already covered above) and if @end
	 * is not in the next run switching it to be sparse, again reduces the
	 * problem to the already covered case of "@start is in a hole".
	 */
	if (end >= rl[1].vcn) {
		/*
		 * If @end is not in the next run, reduce the problem to the
		 * case of "@start is in a hole".
		 */
		if (rl[1].length && end >= rl[2].vcn) {
			/* Truncate the run containing @start. */
			rl->length = start - rl->vcn;
			rl++;
			rl->vcn = start;
			rl->lcn = LCN_HOLE;
			goto extend_hole;
		}
		trl = ntfs_rl_realloc(runlist->rl, old_size, old_size + 1);
		if (IS_ERR(trl))
			goto enomem_out;
		old_size++;
		if (runlist->rl != trl) {
			rl = trl + (rl - runlist->rl);
			rl_end = trl + (rl_end - runlist->rl);
			rl_real_end = trl + (rl_real_end - runlist->rl);
			runlist->rl = trl;
		}
		/* Truncate the run containing @start. */
		rl->length = start - rl->vcn;
		rl++;
		/*
		 * @end is in the next run, reduce the problem to the case
		 * where "@start is at the beginning of a run and @end is in
		 * the same run as @start".
		 */
		delta = rl->vcn - start;
		rl->vcn = start;
		if (rl->lcn >= 0) {
			rl->lcn -= delta;
			/* Need this in case the lcn just became negative. */
			lcn_fixup = true;
		}
		rl->length += delta;
		goto split_end;
	}
	/*
	 * The first case from above, i.e. @end is in the same run as @start.
	 * We need to split the run into three.  One run for the non-sparse
	 * region between the beginning of the old run and @start, one for the
	 * sparse region between @start and @end, and one for the remaining
	 * non-sparse region, i.e. between @end and the end of the old run.
	 */
	trl = ntfs_rl_realloc(runlist->rl, old_size, old_size + 2);
	if (IS_ERR(trl))
		goto enomem_out;
	old_size += 2;
	if (runlist->rl != trl) {
		rl = trl + (rl - runlist->rl);
		rl_end = trl + (rl_end - runlist->rl);
		rl_real_end = trl + (rl_real_end - runlist->rl);
		runlist->rl = trl;
	}
	/* Shift all the runs up by two. */
	memmove(rl + 2, rl, (rl_real_end - rl + 1) * sizeof(*rl));
	/* Finally, setup the three split runs. */
	rl->length = start - rl->vcn;
	rl++;
	rl->vcn = start;
	rl->lcn = LCN_HOLE;
	rl->length = length;
	rl++;
	delta = end - rl->vcn;
	rl->vcn = end;
	rl->lcn += delta;
	rl->length -= delta;
	ntfs_debug("Done (split both).");
	return 0;
enomem_out:
	ntfs_error(vol->sb, "Not enough memory to extend runlist buffer.");
	return -ENOMEM;
}

#endif /* NTFS_RW */