runlist.c

上一个上传的有问题,这个是好的。visopsys包括系统内核和GUI的全部SOURCE code ,还包括一些基本的docs文档。里面src子目录对应所有SOURCE code.对于想研究操作系统的朋

/**
 * runlist.c - Run list handling code. Part of the Linux-NTFS project.
 *
 * Copyright (c) 2002-2005 Anton Altaparmakov
 * Copyright (c) 2002-2005 Richard Russon
 * Copyright (c) 2004 Yura Pakhuchiy
 *
 * This program/include file is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as published
 * by the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program/include file is distributed in the hope that it will be
 * useful, but WITHOUT ANY WARRANTY; without even the implied warranty
 * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program (in the main directory of the Linux-NTFS
 * distribution in the file COPYING); if not, write to the Free Software
 * Foundation,Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 * Modified 01/2007 by Andy McLaughlin for Visopsys port.
 */

#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#ifdef HAVE_STDIO_H
#include <stdio.h>
#endif
#ifdef HAVE_STRING_H
#include <string.h>
#endif
#ifdef HAVE_STDLIB_H
#include <stdlib.h>
#endif
#ifdef HAVE_ERRNO_H
#include <errno.h>
#endif

#include "compat.h"
#include "types.h"
#include "volume.h"
#include "layout.h"
#include "debug.h"
#include "device.h"
#include "logging.h"

/**
 * ntfs_rl_mm - runlist memmove
 * @base:
 * @dst:
 * @src:
 * @size:
 *
 * Description...
 *
 * Returns:
 */
static __inline__ void ntfs_rl_mm(runlist_element *base, int dst, int src,
		int size)
{
	if ((dst != src) && (size > 0))
		memmove(base + dst, base + src, size * sizeof(*base));
}

/**
 * ntfs_rl_mc - runlist memory copy
 * @dstbase:
 * @dst:
 * @srcbase:
 * @src:
 * @size:
 *
 * Description...
 *
 * Returns:
 */
static __inline__ void ntfs_rl_mc(runlist_element *dstbase, int dst,
		runlist_element *srcbase, int src, int size)
{
	if (size > 0)
		memcpy(dstbase + dst, srcbase + src, size * sizeof(*dstbase));
}

/**
 * ntfs_rl_realloc - Reallocate memory for runlists
 * @rl:		original runlist
 * @old_size:	number of runlist elements in the original runlist @rl
 * @new_size:	number of runlist elements we need space for
 *
 * As the runlists grow, more memory will be required. To prevent large
 * numbers of small reallocations of memory, this function returns a 4kiB block
 * of memory.
 *
 * N.B.	If the new allocation doesn't require a different number of 4kiB
 *	blocks in memory, the function will return the original pointer.
 *
 * On success, return a pointer to the newly allocated, or recycled, memory.
 * On error, return NULL with errno set to the error code.
 */
static __inline__ runlist_element *ntfs_rl_realloc(runlist_element *rl,
		int old_size, int new_size)
{
	old_size = (old_size * sizeof(runlist_element) + 0xfff) & ~0xfff;
	new_size = (new_size * sizeof(runlist_element) + 0xfff) & ~0xfff;
	if (old_size == new_size)
		return rl;
	return realloc(rl, new_size);
}

/**
 * ntfs_rl_are_mergeable - test if two runlists can be joined together
 * @dst:	original runlist
 * @src:	new runlist to test for mergeability with @dst
 *
 * Test if two runlists can be joined together. For this, their VCNs and LCNs
 * must be adjacent.
 *
 * Return: TRUE   Success, the runlists can be merged.
 *	   FALSE  Failure, the runlists cannot be merged.
 */
static __inline__ BOOL ntfs_rl_are_mergeable(runlist_element *dst,
		runlist_element *src)
{
	if (!dst || !src) {
		ntfs_log_debug("Eeek. ntfs_rl_are_mergeable() invoked with NULL "
				"pointer!\n");
		return FALSE;
	}

	/* We can merge unmapped regions even if they are misaligned. */
	if ((dst->lcn == LCN_RL_NOT_MAPPED) && (src->lcn == LCN_RL_NOT_MAPPED))
		return TRUE;
	/* If the runs are misaligned, we cannot merge them. */
	if ((dst->vcn + dst->length) != src->vcn)
		return FALSE;
	/* If both runs are non-sparse and contiguous, we can merge them. */
	if ((dst->lcn >= 0) && (src->lcn >= 0) &&
		((dst->lcn + dst->length) == src->lcn))
		return TRUE;
	/* If we are merging two holes, we can merge them. */
	if ((dst->lcn == LCN_HOLE) && (src->lcn == LCN_HOLE))
		return TRUE;
	/* Cannot merge. */
	return FALSE;
}

/**
 * __ntfs_rl_merge - merge two runlists without testing if they can be merged
 * @dst:	original, destination runlist
 * @src:	new runlist to merge with @dst
 *
 * Merge the two runlists, writing into the destination runlist @dst. The
 * caller must make sure the runlists can be merged or this will corrupt the
 * destination runlist.
 */
static __inline__ void __ntfs_rl_merge(runlist_element *dst,
		runlist_element *src)
{
	dst->length += src->length;
}

/**
 * ntfs_rl_append - append a runlist after a given element
 * @dst:	original runlist to be worked on
 * @dsize:	number of elements in @dst (including end marker)
 * @src:	runlist to be inserted into @dst
 * @ssize:	number of elements in @src (excluding end marker)
 * @loc:	append the new runlist @src after this element in @dst
 *
 * Append the runlist @src after element @loc in @dst.  Merge the right end of
 * the new runlist, if necessary. Adjust the size of the hole before the
 * appended runlist.
 *
 * On success, return a pointer to the new, combined, runlist. Note, both
 * runlists @dst and @src are deallocated before returning so you cannot use
 * the pointers for anything any more. (Strictly speaking the returned runlist
 * may be the same as @dst but this is irrelevant.)
 *
 * On error, return NULL, with errno set to the error code. Both runlists are
 * left unmodified.
 */
static __inline__ runlist_element *ntfs_rl_append(runlist_element *dst,
		int dsize, runlist_element *src, int ssize, int loc)
{
	BOOL right = FALSE;	/* Right end of @src needs merging */
	int marker;		/* End of the inserted runs */

	if (!dst || !src) {
		ntfs_log_debug("Eeek. ntfs_rl_append() invoked with NULL "
				"pointer!\n");
		errno = EINVAL;
		return NULL;
	}

	/* First, check if the right hand end needs merging. */
	if ((loc + 1) < dsize)
		right = ntfs_rl_are_mergeable(src + ssize - 1, dst + loc + 1);

	/* Space required: @dst size + @src size, less one if we merged. */
	dst = ntfs_rl_realloc(dst, dsize, dsize + ssize - right);
	if (!dst)
		return NULL;
	/*
	 * We are guaranteed to succeed from here so can start modifying the
	 * original runlists.
	 */

	/* First, merge the right hand end, if necessary. */
	if (right)
		__ntfs_rl_merge(src + ssize - 1, dst + loc + 1);

	/* marker - First run after the @src runs that have been inserted */
	marker = loc + ssize + 1;

	/* Move the tail of @dst out of the way, then copy in @src. */
	ntfs_rl_mm(dst, marker, loc + 1 + right, dsize - loc - 1 - right);
	ntfs_rl_mc(dst, loc + 1, src, 0, ssize);

	/* Adjust the size of the preceding hole. */
	dst[loc].length = dst[loc + 1].vcn - dst[loc].vcn;

	/* We may have changed the length of the file, so fix the end marker */
	if (dst[marker].lcn == LCN_ENOENT)
		dst[marker].vcn = dst[marker-1].vcn + dst[marker-1].length;

	return dst;
}

/**
 * ntfs_rl_insert - insert a runlist into another
 * @dst:	original runlist to be worked on
 * @dsize:	number of elements in @dst (including end marker)
 * @src:	new runlist to be inserted
 * @ssize:	number of elements in @src (excluding end marker)
 * @loc:	insert the new runlist @src before this element in @dst
 *
 * Insert the runlist @src before element @loc in the runlist @dst. Merge the
 * left end of the new runlist, if necessary. Adjust the size of the hole
 * after the inserted runlist.
 *
 * On success, return a pointer to the new, combined, runlist. Note, both
 * runlists @dst and @src are deallocated before returning so you cannot use
 * the pointers for anything any more. (Strictly speaking the returned runlist
 * may be the same as @dst but this is irrelevant.)
 *
 * On error, return NULL, with errno set to the error code. Both runlists are
 * left unmodified.
 */
static __inline__ runlist_element *ntfs_rl_insert(runlist_element *dst,
		int dsize, runlist_element *src, int ssize, int loc)
{
	BOOL left = FALSE;	/* Left end of @src needs merging */
	BOOL disc = FALSE;	/* Discontinuity between @dst and @src */
	int marker;		/* End of the inserted runs */

	if (!dst || !src) {
		ntfs_log_debug("Eeek. ntfs_rl_insert() invoked with NULL "
				"pointer!\n");
		errno = EINVAL;
		return NULL;
	}

	/* disc => Discontinuity between the end of @dst and the start of @src.
	 *	   This means we might need to insert a "notmapped" run.
	 */
	if (loc == 0)
		disc = (src[0].vcn > 0);
	else {
		s64 merged_length;

		left = ntfs_rl_are_mergeable(dst + loc - 1, src);

		merged_length = dst[loc - 1].length;
		if (left)
			merged_length += src->length;

		disc = (src[0].vcn > dst[loc - 1].vcn + merged_length);
	}

	/* Space required: @dst size + @src size, less one if we merged, plus
	 * one if there was a discontinuity.
	 */
	dst = ntfs_rl_realloc(dst, dsize, dsize + ssize - left + disc);
	if (!dst)
		return NULL;
	/*
	 * We are guaranteed to succeed from here so can start modifying the
	 * original runlist.
	 */

	if (left)
		__ntfs_rl_merge(dst + loc - 1, src);

	/*
	 * marker - First run after the @src runs that have been inserted
	 * Nominally: marker = @loc + @ssize (location + number of runs in @src)
	 * If "left", then the first run in @src has been merged with one in @dst.
	 * If "disc", then @dst and @src don't meet and we need an extra run to fill the gap.
	 */
	marker = loc + ssize - left + disc;

	/* Move the tail of @dst out of the way, then copy in @src. */
	ntfs_rl_mm(dst, marker, loc, dsize - loc);
	ntfs_rl_mc(dst, loc + disc, src, left, ssize - left);

	/* Adjust the VCN of the first run after the insertion ... */
	dst[marker].vcn = dst[marker - 1].vcn + dst[marker - 1].length;
	/* ... and the length. */
	if (dst[marker].lcn == LCN_HOLE || dst[marker].lcn == LCN_RL_NOT_MAPPED)
		dst[marker].length = dst[marker + 1].vcn - dst[marker].vcn;

	/* Writing beyond the end of the file and there's a discontinuity. */
	if (disc) {
		if (loc > 0) {
			dst[loc].vcn = dst[loc - 1].vcn + dst[loc - 1].length;
			dst[loc].length = dst[loc + 1].vcn - dst[loc].vcn;
		} else {
			dst[loc].vcn = 0;
			dst[loc].length = dst[loc + 1].vcn;
		}
		dst[loc].lcn = LCN_RL_NOT_MAPPED;
	}
	return dst;
}

/**
 * ntfs_rl_replace - overwrite a runlist element with another runlist
 * @dst:	original runlist to be worked on
 * @dsize:	number of elements in @dst (including end marker)
 * @src:	new runlist to be inserted
 * @ssize:	number of elements in @src (excluding end marker)
 * @loc:	index in runlist @dst to overwrite with @src
 *
 * Replace the runlist element @dst at @loc with @src. Merge the left and
 * right ends of the inserted runlist, if necessary.
 *
 * On success, return a pointer to the new, combined, runlist. Note, both
 * runlists @dst and @src are deallocated before returning so you cannot use
 * the pointers for anything any more. (Strictly speaking the returned runlist
 * may be the same as @dst but this is irrelevant.)
 *
 * On error, return NULL, with errno set to the error code. Both runlists are
 * left unmodified.
 */
static __inline__ runlist_element *ntfs_rl_replace(runlist_element *dst,
		int dsize, runlist_element *src, int ssize, int loc)
{
	signed delta;
	BOOL left  = FALSE;	/* Left end of @src needs merging */
	BOOL right = FALSE;	/* Right end of @src needs merging */
	int tail;		/* Start of tail of @dst */
	int marker;		/* End of the inserted runs */

	if (!dst || !src) {
		ntfs_log_debug("Eeek. ntfs_rl_replace() invoked with NULL "
				"pointer!\n");
		errno = EINVAL;
		return NULL;
	}

	/* First, see if the left and right ends need merging. */
	if ((loc + 1) < dsize)
		right = ntfs_rl_are_mergeable(src + ssize - 1, dst + loc + 1);
	if (loc > 0)
		left = ntfs_rl_are_mergeable(dst + loc - 1, src);

	/* Allocate some space. We'll need less if the left, right, or both
	 * ends get merged.  The -1 accounts for the run being replaced.
	 */
	delta = ssize - 1 - left - right;
	if (delta > 0) {
		dst = ntfs_rl_realloc(dst, dsize, dsize + delta);
		if (!dst)
			return NULL;
	}
	/*
	 * We are guaranteed to succeed from here so can start modifying the
	 * original runlists.
	 */

	/* First, merge the left and right ends, if necessary. */
	if (right)
		__ntfs_rl_merge(src + ssize - 1, dst + loc + 1);
	if (left)
		__ntfs_rl_merge(dst + loc - 1, src);

	/*
	 * tail - Offset of the tail of @dst
	 * Nominally: @tail = @loc + 1 (location, skipping the replaced run)
	 * If "right", then one of @dst's runs is already merged into @src.
	 */
	tail = loc + right + 1;

	/*
	 * marker - First run after the @src runs that have been inserted
	 * Nominally: @marker = @loc + @ssize (location + number of runs in @src)
	 * If "left", then the first run in @src has been merged with one in @dst.
	 */
	marker = loc + ssize - left;

	/* Move the tail of @dst out of the way, then copy in @src. */
	ntfs_rl_mm(dst, marker, tail, dsize - tail);
	ntfs_rl_mc(dst, loc, src, left, ssize - left);

	/* We may have changed the length of the file, so fix the end marker */
	if (((dsize - tail) > 0) && (dst[marker].lcn == LCN_ENOENT))
		dst[marker].vcn = dst[marker - 1].vcn + dst[marker - 1].length;

	return dst;
}

/**
 * ntfs_rl_split - insert a runlist into the centre of a hole
 * @dst:	original runlist to be worked on
 * @dsize:	number of elements in @dst (including end marker)
 * @src:	new runlist to be inserted
 * @ssize:	number of elements in @src (excluding end marker)
 * @loc:	index in runlist @dst at which to split and insert @src
 *
 * Split the runlist @dst at @loc into two and insert @new in between the two
 * fragments. No merging of runlists is necessary. Adjust the size of the
 * holes either side.
 *