index.c

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

/**
 * ntfs_index_lookup - find a key in an index and return its index entry
 * @key:	[IN] key for which to search in the index
 * @key_len:	[IN] length of @key in bytes
 * @icx:	[IN/OUT] context describing the index and the returned entry
 *
 * Before calling ntfs_index_lookup(), @icx must have been obtained from a
 * call to ntfs_index_ctx_get().
 *
 * Look for the @key in the index specified by the index lookup context @icx.
 * ntfs_index_lookup() walks the contents of the index looking for the @key.
 *
 * If the @key is found in the index, 0 is returned and @icx is setup to
 * describe the index entry containing the matching @key.  @icx->entry is the
 * index entry and @icx->data and @icx->data_len are the index entry data and
 * its length in bytes, respectively.
 *
 * If the @key is not found in the index, -1 is returned, errno = ENOENT and
 * @icx is setup to describe the index entry whose key collates immediately
 * after the search @key, i.e. this is the position in the index at which
 * an index entry with a key of @key would need to be inserted.
 *
 * If an error occurs return -1, set errno to error code and @icx is left
 * untouched.
 *
 * When finished with the entry and its data, call ntfs_index_ctx_put() to free
 * the context and other associated resources.
 *
 * If the index entry was modified, call ntfs_index_entry_mark_dirty() before
 * the call to ntfs_index_ctx_put() to ensure that the changes are written
 * to disk.
 */
int ntfs_index_lookup(const void *key, const int key_len, ntfs_index_context *icx)
{
	VCN old_vcn, vcn;
	ntfs_inode *ni = icx->ni;
	INDEX_ROOT *ir;
	INDEX_ENTRY *ie;
	INDEX_BLOCK *ib = NULL;
	int ret, err = 0;

	ntfs_log_trace("Entering\n");
	
	if (!key || key_len <= 0) {
		errno = EINVAL;
		ntfs_log_perror("key: %p  key_len: %d", key, key_len);
		return -1;
	}

	ir = ntfs_ir_lookup(ni, icx->name, icx->name_len, &icx->actx);
	if (!ir) {
		if (errno == ENOENT)
			errno = EIO;
		return -1;
	}
	
	icx->block_size = le32_to_cpu(ir->index_block_size);
	if (icx->block_size < NTFS_BLOCK_SIZE) {
		errno = EINVAL;
		ntfs_log_perror("Index block size (%d) is smaller than the "
				"sector size (%d)", icx->block_size, NTFS_BLOCK_SIZE);
		goto err_out;
	}

	if (ni->vol->cluster_size <= icx->block_size)
		icx->vcn_size_bits = ni->vol->cluster_size_bits;
	else
		icx->vcn_size_bits = ni->vol->sector_size_bits;
		
	icx->cr = ir->collation_rule;
	if (!ntfs_is_collation_rule_supported(icx->cr)) {
		err = errno = EOPNOTSUPP;
		ntfs_log_perror("Unknown collation rule 0x%x", 
				(unsigned)le32_to_cpu(icx->cr));
		goto err_out;
	}
	
	old_vcn = VCN_INDEX_ROOT_PARENT;
	/* 
	 * FIXME: check for both ir and ib that the first index entry is
	 * within the index block.
	 */
	ret = ntfs_ie_lookup(key, key_len, icx, &ir->index, &vcn, &ie);
	if (ret == STATUS_ERROR) {
		err = errno;
		goto err_out;
	}
	
	icx->ir = ir;
	
	if (ret != STATUS_KEEP_SEARCHING) {
		/* STATUS_OK or STATUS_NOT_FOUND */
		err = errno;
		icx->is_in_root = TRUE;
		icx->parent_vcn[icx->pindex] = old_vcn;
		goto done;
	}
	
	/* Child node present, descend into it. */
	
	icx->ia_na = ntfs_ia_open(icx, ni);
	if (!icx->ia_na)
		goto err_out;
	
	ib = ntfs_malloc(icx->block_size);
	if (!ib) {
		err = errno;
		goto err_out;
	}
	
descend_into_child_node:

	icx->parent_vcn[icx->pindex] = old_vcn;
	if (ntfs_icx_parent_inc(icx)) {
		err = errno;
		goto err_out;
	}
	old_vcn = vcn;

	ntfs_log_debug("Descend into node with VCN %lld.\n", vcn);
	
	if (ntfs_ib_read(icx, vcn, ib))
		goto err_out;
	
	ret = ntfs_ie_lookup(key, key_len, icx, &ib->index, &vcn, &ie);
	if (ret != STATUS_KEEP_SEARCHING) {
		err = errno;
		if (ret == STATUS_ERROR)
			goto err_out;
		
		/* STATUS_OK or STATUS_NOT_FOUND */
		icx->is_in_root = FALSE;
		icx->ib = ib;
		icx->parent_vcn[icx->pindex] = vcn;
		goto done;
	}

	if ((ib->index.ih_flags & NODE_MASK) == LEAF_NODE) {
		ntfs_log_error("Index entry with child node found in a leaf "
			       "node in inode 0x%llx.\n",
			       (unsigned long long)ni->mft_no);
		goto err_out;
	}
	
	goto descend_into_child_node;
err_out:
	free(ib);
	if (!err)
		err = EIO;
	errno = err;
	return -1;
done:
	icx->entry = ie;
	icx->data = (u8 *)ie + offsetof(INDEX_ENTRY, key);
	icx->data_len = le16_to_cpu(ie->key_length);
	ntfs_log_trace("Done.\n");
	if (err) {
		errno = err;
		return -1;
	}
	return 0;

}

static INDEX_BLOCK *ntfs_ib_alloc(VCN ib_vcn, u32 ib_size, 
				  INDEX_HEADER_FLAGS node_type)
{
	INDEX_BLOCK *ib;
	int ih_size = sizeof(INDEX_HEADER);
	
	ntfs_log_trace("Entering ib_vcn = %lld ib_size = %u\n", ib_vcn, ib_size);
	
	ib = ntfs_calloc(ib_size);
	if (!ib)
		return NULL;
	
	ib->magic = magic_INDX;
	ib->usa_ofs = cpu_to_le16(sizeof(INDEX_BLOCK));
	ib->usa_count = cpu_to_le16(ib_size / NTFS_BLOCK_SIZE + 1);
	/* Set USN to 1 */
	*(u16 *)((char *)ib + le16_to_cpu(ib->usa_ofs)) = cpu_to_le16(1);
	ib->lsn = cpu_to_le64(0);
	
	ib->index_block_vcn = cpu_to_sle64(ib_vcn);
	
	ib->index.entries_offset = cpu_to_le32((ih_size +
			le16_to_cpu(ib->usa_count) * 2 + 7) & ~7);
	ib->index.index_length = 0;
	ib->index.allocated_size = cpu_to_le32(ib_size - 
					       (sizeof(INDEX_BLOCK) - ih_size));
	ib->index.ih_flags = node_type;
	
	return ib;
}	

/** 
 *  Find the median by going through all the entries
 */
static INDEX_ENTRY *ntfs_ie_get_median(INDEX_HEADER *ih)
{
	INDEX_ENTRY *ie, *ie_start;
	u8 *ie_end;
	int i = 0, median;
	
	ntfs_log_trace("Entering\n");
	
	ie = ie_start = ntfs_ie_get_first(ih);
	ie_end   = (u8 *)ntfs_ie_get_end(ih);
	
	while ((u8 *)ie < ie_end && !ntfs_ie_end(ie)) {
		ie = ntfs_ie_get_next(ie);
		i++;
	}
	/*
	 * NOTE: this could be also the entry at the half of the index block.
	 */
	median = i / 2 - 1;
	
	ntfs_log_trace("Entries: %d  median: %d\n", i, median);
	
	for (i = 0, ie = ie_start; i <= median; i++)
		ie = ntfs_ie_get_next(ie);
	
	return ie;
}

static s64 ntfs_ibm_vcn_to_pos(ntfs_index_context *icx, VCN vcn)
{
	return ntfs_ib_vcn_to_pos(icx, vcn) / icx->block_size;
}

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

static int ntfs_ibm_add(ntfs_index_context *icx)
{
	u8 bmp[8];

	ntfs_log_trace("Entering\n");
	
	if (ntfs_attr_exist(icx->ni, AT_BITMAP, icx->name, icx->name_len))
		return STATUS_OK;
	/*
	 * AT_BITMAP must be at least 8 bytes.
	 */
	memset(bmp, 0, sizeof(bmp));
	if (ntfs_attr_add(icx->ni, AT_BITMAP, icx->name, icx->name_len,
			  bmp, sizeof(bmp))) {
		ntfs_log_perror("Failed to add AT_BITMAP");
		return STATUS_ERROR;
	}
	
	return STATUS_OK;
}

static int ntfs_ibm_modify(ntfs_index_context *icx, VCN vcn, int set)
{
	u8 byte;
	s64 pos = ntfs_ibm_vcn_to_pos(icx, vcn);
	u32 bpos = pos / 8;
	u32 bit = 1 << (pos % 8);
	ntfs_attr *na;
	int ret = STATUS_ERROR;

	ntfs_log_trace("%s vcn: %lld\n", set ? "set" : "clear", vcn);
	
	na = ntfs_attr_open(icx->ni, AT_BITMAP,  icx->name, icx->name_len);
	if (!na) {
		ntfs_log_perror("Failed to open $BITMAP attribute");
		return -1;
	}

	if (set) {
		if (na->data_size < bpos + 1) {
			if (ntfs_attr_truncate(na, (na->data_size + 8) & ~7)) {
				ntfs_log_perror("Failed to truncate AT_BITMAP");
				goto err_na;
			}
		}
	}
	
	if (ntfs_attr_pread(na, bpos, 1, &byte) != 1) {
		ntfs_log_perror("Failed to read $BITMAP");
		goto err_na;
	}

	if (set) 
		byte |= bit;
	else
		byte &= ~bit;
		
	if (ntfs_attr_pwrite(na, bpos, 1, &byte) != 1) {
		ntfs_log_perror("Failed to write $Bitmap");
		goto err_na;
	}

	ret = STATUS_OK;
err_na:
	ntfs_attr_close(na);
	return ret;
}


static int ntfs_ibm_set(ntfs_index_context *icx, VCN vcn)
{
	return ntfs_ibm_modify(icx, vcn, 1);
}

static int ntfs_ibm_clear(ntfs_index_context *icx, VCN vcn)
{
	return ntfs_ibm_modify(icx, vcn, 0);
}

static VCN ntfs_ibm_get_free(ntfs_index_context *icx)
{
	u8 *bm;
	int bit;
	s64 vcn, byte, size;

	ntfs_log_trace("Entering\n");
	
	bm = ntfs_attr_readall(icx->ni, AT_BITMAP,  icx->name, icx->name_len,
			       &size);
	if (!bm)
		return (VCN)-1;
	
	for (byte = 0; byte < size; byte++) {
		
		if (bm[byte] == 255)
			continue;
		
		for (bit = 0; bit < 8; bit++) {
			if (!(bm[byte] & (1 << bit))) {
				vcn = ntfs_ibm_pos_to_vcn(icx, byte * 8 + bit);
				goto out;
			}
		}
	}
	
	vcn = ntfs_ibm_pos_to_vcn(icx, size * 8);
out:	
	ntfs_log_trace("allocated vcn: %lld\n", vcn);

	if (ntfs_ibm_set(icx, vcn))
		vcn = (VCN)-1;
	
	free(bm);
	return vcn;
}

static INDEX_BLOCK *ntfs_ir_to_ib(INDEX_ROOT *ir, VCN ib_vcn)
{
	INDEX_BLOCK *ib;
	INDEX_ENTRY *ie_last;
	char *ies_start, *ies_end;
	int i;
	
	ntfs_log_trace("Entering\n");
	
	ib = ntfs_ib_alloc(ib_vcn, le32_to_cpu(ir->index_block_size), LEAF_NODE);
	if (!ib)
		return NULL;
	
	ies_start = (char *)ntfs_ie_get_first(&ir->index);
	ies_end   = (char *)ntfs_ie_get_end(&ir->index);
	ie_last   = ntfs_ie_get_last((INDEX_ENTRY *)ies_start, ies_end);
	/* 
	 * Copy all entries, including the termination entry
	 * as well, which can never have any data.
	 */
	i = (char *)ie_last - ies_start + le16_to_cpu(ie_last->length);
	memcpy(ntfs_ie_get_first(&ib->index), ies_start, i);
	
	ib->index.ih_flags = ir->index.ih_flags;
	ib->index.index_length = cpu_to_le32(i +
			le32_to_cpu(ib->index.entries_offset));
	return ib;
}

static void ntfs_ir_nill(INDEX_ROOT *ir)
{
	INDEX_ENTRY *ie_last;
	char *ies_start, *ies_end;
	
	ntfs_log_trace("Entering\n");
	/*
	 * TODO: This function could be much simpler.
	 */
	ies_start = (char *)ntfs_ie_get_first(&ir->index);
	ies_end   = (char *)ntfs_ie_get_end(&ir->index);
	ie_last   = ntfs_ie_get_last((INDEX_ENTRY *)ies_start, ies_end);
	/* 
	 * Move the index root termination entry forward
	 */
	if ((char *)ie_last > ies_start) {
		memmove(ies_start, (char *)ie_last, le16_to_cpu(ie_last->length));
		ie_last = (INDEX_ENTRY *)ies_start;
	}
}

static int ntfs_ib_copy_tail(ntfs_index_context *icx, INDEX_BLOCK *src,
			     INDEX_ENTRY *median, VCN new_vcn)
{
	u8 *ies_end;
	INDEX_ENTRY *ie_head;		/* first entry after the median */
	int tail_size, ret;
	INDEX_BLOCK *dst;
	
	ntfs_log_trace("Entering\n");
	
	dst = ntfs_ib_alloc(new_vcn, icx->block_size, 
			    src->index.ih_flags & NODE_MASK);
	if (!dst)
		return STATUS_ERROR;
	
	ie_head = ntfs_ie_get_next(median);
	
	ies_end = (u8 *)ntfs_ie_get_end(&src->index);
	tail_size = ies_end - (u8 *)ie_head;
	memcpy(ntfs_ie_get_first(&dst->index), ie_head, tail_size);
	
	dst->index.index_length = cpu_to_le32(tail_size + 
					      le32_to_cpu(dst->index.entries_offset));
	ret = ntfs_ib_write(icx, dst);

	free(dst);
	return ret;
}

static int ntfs_ib_cut_tail(ntfs_index_context *icx, INDEX_BLOCK *ib,
			    INDEX_ENTRY *ie)
{
	char *ies_start, *ies_end;
	INDEX_ENTRY *ie_last;
	
	ntfs_log_trace("Entering\n");
	
	ies_start = (char *)ntfs_ie_get_first(&ib->index);
	ies_end   = (char *)ntfs_ie_get_end(&ib->index);
	
	ie_last   = ntfs_ie_get_last((INDEX_ENTRY *)ies_start, ies_end);
	if (ie_last->ie_flags & INDEX_ENTRY_NODE)
		ntfs_ie_set_vcn(ie_last, ntfs_ie_get_vcn(ie));
	
	memcpy(ie, ie_last, le16_to_cpu(ie_last->length));
	
	ib->index.index_length = cpu_to_le32(((char *)ie - ies_start) + 
		le16_to_cpu(ie->length) + le32_to_cpu(ib->index.entries_offset));
	
	if (ntfs_ib_write(icx, ib))
		return STATUS_ERROR;
	
	return STATUS_OK;
}
	
static int ntfs_ia_add(ntfs_index_context *icx)
{
	ntfs_log_trace("Entering\n");

	if (ntfs_ibm_add(icx))
		return -1;
	
	if (!ntfs_attr_exist(icx->ni, AT_INDEX_ALLOCATION, icx->name, icx->name_len)) {
	
		if (ntfs_attr_add(icx->ni, AT_INDEX_ALLOCATION, icx->name,
				  icx->name_len, NULL, 0)) {
			ntfs_log_perror("Failed to add AT_INDEX_ALLOCATION");
			return -1;
		}
	}
	
	icx->ia_na = ntfs_ia_open(icx, icx->ni);
	if (!icx->ia_na)
		return -1;

	return 0;
}

static int ntfs_ir_reparent(ntfs_index_context *icx)
{
	ntfs_attr_search_ctx *ctx = NULL;
	INDEX_ROOT *ir;
	INDEX_ENTRY *ie;
	INDEX_BLOCK *ib = NULL;
	VCN new_ib_vcn;
	int ret = STATUS_ERROR;

	ntfs_log_trace("Entering\n");
	
	ir = ntfs_ir_lookup2(icx->ni, icx->name, icx->name_len);
	if (!ir)
		goto out;
	
	if ((ir->index.ih_flags & NODE_MASK) == SMALL_INDEX)
		if (ntfs_ia_add(icx))
			goto out;
	
	new_ib_vcn = ntfs_ibm_get_free(icx);
	if (new_ib_vcn == -1)
		goto out;
		
	ir = ntfs_ir_lookup2(icx->ni, icx->name, icx->name_len);
	if (!ir)
		goto clear_bmp;
	
	ib = ntfs_ir_to_ib(ir, new_ib_vcn);
	if (ib == NULL) {
		ntfs_log_perror("Failed to move index root to index block");
		goto clear_bmp;
	}
		
	if (ntfs_ib_write(icx, ib))
		goto clear_bmp;
	
	ir = ntfs_ir_lookup(icx->ni, icx->name, icx->name_len, &ctx);
	if (!ir)
		goto clear_bmp;
	
	ntfs_ir_nill(ir);
	
	ie = ntfs_ie_get_first(&ir->index);
	ie->ie_flags |= INDEX_ENTRY_NODE;
	ie->length = cpu_to_le16(sizeof(INDEX_ENTRY_HEADER) + sizeof(VCN));
	
	ir->index.ih_flags = LARGE_INDEX;
	ir->index.index_length = cpu_to_le32(le32_to_cpu(ir->index.entries_offset)
					     + le16_to_cpu(ie->length));
	ir->index.allocated_size = ir->index.index_length;
	
	if (ntfs_resident_attr_value_resize(ctx->mrec, ctx->attr,
			sizeof(INDEX_ROOT) - sizeof(INDEX_HEADER) +
			le32_to_cpu(ir->index.allocated_size)))
		/* FIXME: revert index root */
		goto clear_bmp;
	/*
	 *  FIXME: do it earlier if we have enough space in IR (should always),
	 *  so in error case we wouldn't lose the IB.
	 */
	ntfs_ie_set_vcn(ie, new_ib_vcn);
	
	ret = STATUS_OK;
err_out:
	free(ib);
	ntfs_attr_put_search_ctx(ctx);
out:
	return ret;
clear_bmp:
	ntfs_ibm_clear(icx, new_ib_vcn);
	goto err_out;
}

/**
 * ntfs_ir_truncate - Truncate index root attribute
 * 
 * Returns STATUS_OK, STATUS_RESIDENT_ATTRIBUTE_FILLED_MFT or STATUS_ERROR.
 */
static int ntfs_ir_truncate(ntfs_index_context *icx, int data_size)
{			  
	ntfs_attr *na;
	int ret;

	ntfs_log_trace("Entering\n");
	
	na = ntfs_attr_open(icx->ni, AT_INDEX_ROOT, icx->name, icx->name_len);
	if (!na) {
		ntfs_log_perror("Failed to open INDEX_ROOT");
		return STATUS_ERROR;
	}
	/*
	 *  INDEX_ROOT must be resident and its entries can be moved to 
	 *  INDEX_BLOCK, so ENOSPC isn't a real error.
	 */
	ret = ntfs_attr_truncate(na, data_size + offsetof(INDEX_ROOT, index));
	if (ret == STATUS_OK) {
		
		icx->ir = ntfs_ir_lookup2(icx->ni, icx->name, icx->name_len);
		if (!icx->ir)
			return STATUS_ERROR;
	
		icx->ir->index.allocated_size = cpu_to_le32(data_size);
		
	} else if (ret == STATUS_ERROR)
		ntfs_log_perror("Failed to truncate INDEX_ROOT");
	
	ntfs_attr_close(na);
	return ret;
}
		
/**
 * ntfs_ir_make_space - Make more space for the index root attribute
 * 
 * On success return STATUS_OK or STATUS_KEEP_SEARCHING.
 * On error return STATUS_ERROR.
 */
static int ntfs_ir_make_space(ntfs_index_context *icx, int data_size)
{			  
	int ret;

	ntfs_log_trace("Entering\n");
	
	ret = ntfs_ir_truncate(icx, data_size);
	if (ret == STATUS_RESIDENT_ATTRIBUTE_FILLED_MFT) {
		
		ret = ntfs_ir_reparent(icx);
		if (ret == STATUS_OK)
			ret = STATUS_KEEP_SEARCHING;
		else
			ntfs_log_perror("Failed to nodify INDEX_ROOT");
	} 

	return ret;
}

/*
 * NOTE: 'ie' must be a copy of a real index entry.
 */
static int ntfs_ie_add_vcn(INDEX_ENTRY **ie)
{
	INDEX_ENTRY *p, *old = *ie;
	 
	old->length = cpu_to_le16(le16_to_cpu(old->length) + sizeof(VCN));
	p = realloc(old, le16_to_cpu(old->length));
	if (!p)
		return STATUS_ERROR;
	
	p->ie_flags |= INDEX_ENTRY_NODE;
	*ie = p;