index.c

LINUX下读写NTFS分区的工具。 已经集成了通过LIBCONV库支持中文的代码。

/**
 * index.c - NTFS index handling.  Originated from the Linux-NTFS project.
 *
 * Copyright (c) 2004-2005 Anton Altaparmakov
 * Copyright (c) 2004-2005 Richard Russon
 * Copyright (c) 2005-2006 Yura Pakhuchiy
 * Copyright (c) 2005-2008 Szabolcs Szakacsits
 *
 * 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 NTFS-3G
 * distribution in the file COPYING); if not, write to the Free Software
 * Foundation,Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

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

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

#include "attrib.h"
#include "collate.h"
#include "debug.h"
#include "index.h"
#include "mst.h"
#include "dir.h"
#include "logging.h"
#include "bitmap.h"
#include "misc.h"

/**
 * ntfs_index_entry_mark_dirty - mark an index entry dirty
 * @ictx:	ntfs index context describing the index entry
 *
 * Mark the index entry described by the index entry context @ictx dirty.
 *
 * If the index entry is in the index root attribute, simply mark the inode
 * containing the index root attribute dirty.  This ensures the mftrecord, and
 * hence the index root attribute, will be written out to disk later.
 *
 * If the index entry is in an index block belonging to the index allocation
 * attribute, set ib_dirty to TRUE, thus index block will be updated during
 * ntfs_index_ctx_put.
 */
void ntfs_index_entry_mark_dirty(ntfs_index_context *ictx)
{
	if (ictx->is_in_root)
		ntfs_inode_mark_dirty(ictx->actx->ntfs_ino);
	else
		ictx->ib_dirty = TRUE;
}

static s64 ntfs_ib_vcn_to_pos(ntfs_index_context *icx, VCN vcn)
{
	return vcn << icx->vcn_size_bits;
}

static VCN ntfs_ib_pos_to_vcn(ntfs_index_context *icx, s64 pos)
{
	return pos >> icx->vcn_size_bits;
}

static int ntfs_ib_write(ntfs_index_context *icx, INDEX_BLOCK *ib)
{
	s64 ret, vcn = sle64_to_cpu(ib->index_block_vcn);
	
	ntfs_log_trace("vcn: %lld\n", vcn);
	
	ret = ntfs_attr_mst_pwrite(icx->ia_na, ntfs_ib_vcn_to_pos(icx, vcn),
				   1, icx->block_size, ib);
	if (ret != 1) {
		ntfs_log_perror("Failed to write index block %lld, inode %llu",
			(long long)vcn, (unsigned long long)icx->ni->mft_no);
		return STATUS_ERROR;
	}
	
	return STATUS_OK;
}

static int ntfs_icx_ib_write(ntfs_index_context *icx)
{
		if (ntfs_ib_write(icx, icx->ib))
			return STATUS_ERROR;
		
		icx->ib_dirty = FALSE;
		
		return STATUS_OK;
}

/**
 * ntfs_index_ctx_get - allocate and initialize a new index context
 * @ni:		ntfs inode with which to initialize the context
 * @name:	name of the which context describes
 * @name_len:	length of the index name
 *
 * Allocate a new index context, initialize it with @ni and return it.
 * Return NULL if allocation failed.
 */
ntfs_index_context *ntfs_index_ctx_get(ntfs_inode *ni,
				       ntfschar *name, u32 name_len)
{
	ntfs_index_context *icx;

	ntfs_log_trace("Entering\n");
	
	if (!ni) {
		errno = EINVAL;
		return NULL;
	}
	if (ni->nr_extents == -1)
		ni = ni->base_ni;
	icx = ntfs_calloc(sizeof(ntfs_index_context));
	if (icx)
		*icx = (ntfs_index_context) {
			.ni = ni,
			.name = name,
			.name_len = name_len,
		};
	return icx;
}

static void ntfs_index_ctx_free(ntfs_index_context *icx)
{
	ntfs_log_trace("Entering\n");
	
	if (!icx->entry)
		return;

	if (icx->actx)
		ntfs_attr_put_search_ctx(icx->actx);

	if (!icx->is_in_root) {
		if (icx->ib_dirty) {
			/* FIXME: Error handling!!! */
			ntfs_ib_write(icx, icx->ib);
		}
		free(icx->ib);
	}
	
	ntfs_attr_close(icx->ia_na);
}

/**
 * ntfs_index_ctx_put - release an index context
 * @icx:	index context to free
 *
 * Release the index context @icx, releasing all associated resources.
 */
void ntfs_index_ctx_put(ntfs_index_context *icx)
{
	ntfs_index_ctx_free(icx);
	free(icx);
}

/**
 * ntfs_index_ctx_reinit - reinitialize an index context
 * @icx:	index context to reinitialize
 *
 * Reinitialize the index context @icx so it can be used for ntfs_index_lookup.
 */
void ntfs_index_ctx_reinit(ntfs_index_context *icx)
{
	ntfs_log_trace("Entering\n");
	
	ntfs_index_ctx_free(icx);
	
	*icx = (ntfs_index_context) {
		.ni = icx->ni,
		.name = icx->name,
		.name_len = icx->name_len,
	};
}

static VCN *ntfs_ie_get_vcn_addr(INDEX_ENTRY *ie)
{
	return (VCN *)((u8 *)ie + le16_to_cpu(ie->length) - sizeof(VCN));
}

/**
 *  Get the subnode vcn to which the index entry refers.
 */
VCN ntfs_ie_get_vcn(INDEX_ENTRY *ie)
{
	return sle64_to_cpup(ntfs_ie_get_vcn_addr(ie));
}

static INDEX_ENTRY *ntfs_ie_get_first(INDEX_HEADER *ih)
{
	return (INDEX_ENTRY *)((u8 *)ih + le32_to_cpu(ih->entries_offset));
}

static INDEX_ENTRY *ntfs_ie_get_next(INDEX_ENTRY *ie)
{
	return (INDEX_ENTRY *)((char *)ie + le16_to_cpu(ie->length));
}

static u8 *ntfs_ie_get_end(INDEX_HEADER *ih)
{
	/* FIXME: check if it isn't overflowing the index block size */
	return (u8 *)ih + le32_to_cpu(ih->index_length);
}

static int ntfs_ie_end(INDEX_ENTRY *ie)
{
	return ie->ie_flags & INDEX_ENTRY_END || !ie->length;
}

/** 
 *  Find the last entry in the index block
 */
static INDEX_ENTRY *ntfs_ie_get_last(INDEX_ENTRY *ie, char *ies_end)
{
	ntfs_log_trace("Entering\n");
	
	while ((char *)ie < ies_end && !ntfs_ie_end(ie))
		ie = ntfs_ie_get_next(ie);
	
	return ie;
}

static INDEX_ENTRY *ntfs_ie_get_by_pos(INDEX_HEADER *ih, int pos)
{
	INDEX_ENTRY *ie;
	
	ntfs_log_trace("pos: %d\n", pos);
	
	ie = ntfs_ie_get_first(ih);
	
	while (pos-- > 0)
		ie = ntfs_ie_get_next(ie);
	
	return ie;
}

static INDEX_ENTRY *ntfs_ie_prev(INDEX_HEADER *ih, INDEX_ENTRY *ie)
{
	INDEX_ENTRY *ie_prev = NULL;
	INDEX_ENTRY *tmp;
	
	ntfs_log_trace("Entering\n");
	
	tmp = ntfs_ie_get_first(ih);
	
	while (tmp != ie) {
		ie_prev = tmp;
		tmp = ntfs_ie_get_next(tmp);
	}
	
	return ie_prev;
}

char *ntfs_ie_filename_get(INDEX_ENTRY *ie)
{
	FILE_NAME_ATTR *fn;

	fn = (FILE_NAME_ATTR *)&ie->key;
	return ntfs_attr_name_get(fn->file_name, fn->file_name_length);
}

void ntfs_ie_filename_dump(INDEX_ENTRY *ie)
{
	char *s;

	s = ntfs_ie_filename_get(ie);
	ntfs_log_debug("'%s' ", s);
	ntfs_attr_name_free(&s);
}

void ntfs_ih_filename_dump(INDEX_HEADER *ih)
{
	INDEX_ENTRY *ie;
	
	ntfs_log_trace("Entering\n");
	
	ie = ntfs_ie_get_first(ih);
	while (!ntfs_ie_end(ie)) {
		ntfs_ie_filename_dump(ie);
		ie = ntfs_ie_get_next(ie);
	}
}

static int ntfs_ih_numof_entries(INDEX_HEADER *ih)
{
	int n;
	INDEX_ENTRY *ie;
	u8 *end;
	
	ntfs_log_trace("Entering\n");
	
	end = ntfs_ie_get_end(ih);
	ie = ntfs_ie_get_first(ih);
	for (n = 0; !ntfs_ie_end(ie) && (u8 *)ie < end; n++)
		ie = ntfs_ie_get_next(ie);
	return n;
}

static int ntfs_ih_one_entry(INDEX_HEADER *ih)
{
	return (ntfs_ih_numof_entries(ih) == 1);
}

static int ntfs_ih_zero_entry(INDEX_HEADER *ih)
{
	return (ntfs_ih_numof_entries(ih) == 0);
}

static void ntfs_ie_delete(INDEX_HEADER *ih, INDEX_ENTRY *ie)
{
	u32 new_size;
	
	ntfs_log_trace("Entering\n");
	
	new_size = le32_to_cpu(ih->index_length) - le16_to_cpu(ie->length);
	ih->index_length = cpu_to_le32(new_size);
	memmove(ie, (u8 *)ie + le16_to_cpu(ie->length),
		new_size - ((u8 *)ie - (u8 *)ih));
}

static void ntfs_ie_set_vcn(INDEX_ENTRY *ie, VCN vcn)
{
	*ntfs_ie_get_vcn_addr(ie) = cpu_to_le64(vcn);
}

/**
 *  Insert @ie index entry at @pos entry. Used @ih values should be ok already.
 */
static void ntfs_ie_insert(INDEX_HEADER *ih, INDEX_ENTRY *ie, INDEX_ENTRY *pos)
{
	int ie_size = le16_to_cpu(ie->length);
	
	ntfs_log_trace("Entering\n");
	
	ih->index_length = cpu_to_le32(le32_to_cpu(ih->index_length) + ie_size);
	memmove((u8 *)pos + ie_size, pos,
		le32_to_cpu(ih->index_length) - ((u8 *)pos - (u8 *)ih) - ie_size);
	memcpy(pos, ie, ie_size);
}

static INDEX_ENTRY *ntfs_ie_dup(INDEX_ENTRY *ie)
{
	INDEX_ENTRY *dup;
	
	ntfs_log_trace("Entering\n");
	
	dup = ntfs_malloc(le16_to_cpu(ie->length));
	if (dup)
		memcpy(dup, ie, le16_to_cpu(ie->length));
	
	return dup;
}

static INDEX_ENTRY *ntfs_ie_dup_novcn(INDEX_ENTRY *ie)
{
	INDEX_ENTRY *dup;
	int size = le16_to_cpu(ie->length);
	
	ntfs_log_trace("Entering\n");
	
	if (ie->ie_flags & INDEX_ENTRY_NODE)
		size -= sizeof(VCN);
	
	dup = ntfs_malloc(size);
	if (dup) {
		memcpy(dup, ie, size);
		dup->ie_flags &= ~INDEX_ENTRY_NODE;
		dup->length = cpu_to_le16(size);
	}
	return dup;
}

static int ntfs_ia_check(ntfs_index_context *icx, INDEX_BLOCK *ib, VCN vcn)
{
	u32 ib_size = (unsigned)le32_to_cpu(ib->index.allocated_size) + 0x18;
	
	ntfs_log_trace("Entering\n");
	
	if (!ntfs_is_indx_record(ib->magic)) {
		
		ntfs_log_error("Corrupt index block signature: vcn %lld inode "
			       "%llu\n", (long long)vcn,
			       (unsigned long long)icx->ni->mft_no);
		return -1;
	}
	
	if (sle64_to_cpu(ib->index_block_vcn) != vcn) {
		
		ntfs_log_error("Corrupt index block: VCN (%lld) is different "
			       "from expected VCN (%lld) in inode %llu\n",
			       (long long)sle64_to_cpu(ib->index_block_vcn),
			       (long long)vcn,
			       (unsigned long long)icx->ni->mft_no);
		return -1;
	}
	
	if (ib_size != icx->block_size) {
		
		ntfs_log_error("Corrupt index block : VCN (%lld) of inode %llu "
			       "has a size (%u) differing from the index "
			       "specified size (%u)\n", (long long)vcn, 
			       (unsigned long long)icx->ni->mft_no, ib_size,
			       icx->block_size);
		return -1;
	}
	return 0;
}

static INDEX_ROOT *ntfs_ir_lookup(ntfs_inode *ni, ntfschar *name,
				  u32 name_len, ntfs_attr_search_ctx **ctx)
{
	ATTR_RECORD *a;
	INDEX_ROOT *ir = NULL;

	ntfs_log_trace("Entering\n");
	
	*ctx = ntfs_attr_get_search_ctx(ni, NULL);
	if (!*ctx)
		return NULL;
	
	if (ntfs_attr_lookup(AT_INDEX_ROOT, name, name_len, CASE_SENSITIVE, 
			     0, NULL, 0, *ctx)) {
		ntfs_log_perror("Failed to lookup $INDEX_ROOT");
		goto err_out;
	}
	
	a = (*ctx)->attr;
	if (a->non_resident) {
		errno = EINVAL;
		ntfs_log_perror("Non-resident $INDEX_ROOT detected");
		goto err_out;
	}
	
	ir = (INDEX_ROOT *)((char *)a + le16_to_cpu(a->value_offset));
err_out:
	if (!ir) {
		ntfs_attr_put_search_ctx(*ctx);
		*ctx = NULL;
	}
	return ir;
}

static INDEX_ROOT *ntfs_ir_lookup2(ntfs_inode *ni, ntfschar *name, u32 len)
{
	ntfs_attr_search_ctx *ctx;
	INDEX_ROOT *ir;

	ir = ntfs_ir_lookup(ni, name, len, &ctx);
	if (ir)
		ntfs_attr_put_search_ctx(ctx);
	return ir;
}

/** 
 * Find a key in the index block.
 * 
 * Return values:
 *   STATUS_OK with errno set to ESUCCESS if we know for sure that the 
 *             entry exists and @ie_out points to this entry.
 *   STATUS_NOT_FOUND with errno set to ENOENT if we know for sure the
 *                    entry doesn't exist and @ie_out is the insertion point.
 *   STATUS_KEEP_SEARCHING if we can't answer the above question and
 *                         @vcn will contain the node index block.
 *   STATUS_ERROR with errno set if on unexpected error during lookup.
 */
static int ntfs_ie_lookup(const void *key, const int key_len,
			  ntfs_index_context *icx, INDEX_HEADER *ih,
			  VCN *vcn, INDEX_ENTRY **ie_out)
{
	INDEX_ENTRY *ie;
	u8 *index_end;
	int rc, item = 0;
	 
	ntfs_log_trace("Entering\n");
	
	index_end = ntfs_ie_get_end(ih);
	
	/*
	 * Loop until we exceed valid memory (corruption case) or until we
	 * reach the last entry.
	 */
	for (ie = ntfs_ie_get_first(ih); ; ie = ntfs_ie_get_next(ie)) {
		/* Bounds checks. */
		if ((u8 *)ie + sizeof(INDEX_ENTRY_HEADER) > index_end ||
		    (u8 *)ie + le16_to_cpu(ie->length) > index_end) {
			errno = ERANGE;
			ntfs_log_error("Index entry out of bounds in inode "
				       "%llu.\n",
				       (unsigned long long)icx->ni->mft_no);
			return STATUS_ERROR;
		}
		/*
		 * The last entry cannot contain a key.  It can however contain
		 * a pointer to a child node in the B+tree so we just break out.
		 */
		if (ntfs_ie_end(ie))
			break;
		/*
		 * Not a perfect match, need to do full blown collation so we
		 * know which way in the B+tree we have to go.
		 */
		rc = ntfs_collate(icx->ni->vol, icx->cr, key, key_len, &ie->key,
				  le16_to_cpu(ie->key_length));
		if (rc == NTFS_COLLATION_ERROR) {
			ntfs_log_error("Collation error. Perhaps a filename "
				       "contains invalid characters?\n");
			errno = ERANGE;
			return STATUS_ERROR;
		}
		/*
		 * If @key collates before the key of the current entry, there
		 * is definitely no such key in this index but we might need to
		 * descend into the B+tree so we just break out of the loop.
		 */
		if (rc == -1)
			break;
		
		if (!rc) {
			*ie_out = ie;
			errno = 0;
			icx->parent_pos[icx->pindex] = item;
			return STATUS_OK;
		}
		
		item++;
	}
	/*
	 * We have finished with this index block without success. Check for the
	 * presence of a child node and if not present return with errno ENOENT,
	 * otherwise we will keep searching in another index block.
	 */
	if (!(ie->ie_flags & INDEX_ENTRY_NODE)) {
		ntfs_log_debug("Index entry wasn't found.\n");
		*ie_out = ie;
		errno = ENOENT;
		return STATUS_NOT_FOUND;
	}
	
	/* Get the starting vcn of the index_block holding the child node. */
	*vcn = ntfs_ie_get_vcn(ie);
	if (*vcn < 0) {
		errno = EINVAL;
		ntfs_log_perror("Negative vcn in inode %llu\n",
			       	(unsigned long long)icx->ni->mft_no);
		return STATUS_ERROR;
	}

	ntfs_log_trace("Parent entry number %d\n", item);
	icx->parent_pos[icx->pindex] = item;
	
	return STATUS_KEEP_SEARCHING;
}

static ntfs_attr *ntfs_ia_open(ntfs_index_context *icx, ntfs_inode *ni)
{
	ntfs_attr *na;
	
	na = ntfs_attr_open(ni, AT_INDEX_ALLOCATION, icx->name, icx->name_len);
	if (!na) {
		ntfs_log_perror("Failed to open index allocation of inode "
				"%llu", (unsigned long long)ni->mft_no);
		return NULL;
	}
	
	return na;
}

static int ntfs_ib_read(ntfs_index_context *icx, VCN vcn, INDEX_BLOCK *dst)
{
	s64 pos, ret;

	ntfs_log_trace("vcn: %lld\n", vcn);
	
	pos = ntfs_ib_vcn_to_pos(icx, vcn);

	ret = ntfs_attr_mst_pread(icx->ia_na, pos, 1, icx->block_size, (u8 *)dst);
	if (ret != 1) {
		if (ret == -1)
			ntfs_log_perror("Failed to read index block");
		else 
			ntfs_log_error("Failed to read full index block at "
				       "%lld\n", (long long)pos);
		return -1;
	}
	
	if (ntfs_ia_check(icx, dst, vcn))
		return -1;
	
	return 0;
}

static int ntfs_icx_parent_inc(ntfs_index_context *icx)
{
	icx->pindex++;
	if (icx->pindex >= MAX_PARENT_VCN) {
		errno = EOPNOTSUPP;
		ntfs_log_perror("Index is over %d level deep", MAX_PARENT_VCN);
		return STATUS_ERROR;
	}
	return STATUS_OK;
}

static int ntfs_icx_parent_dec(ntfs_index_context *icx)
{
	icx->pindex--;
	if (icx->pindex < 0) {
		errno = EINVAL;
		ntfs_log_perror("Corrupt index pointer (%d)", icx->pindex);
		return STATUS_ERROR;
	}
	return STATUS_OK;
}