xfs_da_btree.c

来自「Linux Kernel 2.6.9 for OMAP1710」· C语言 代码 · 共 2,203 行 · 第 1/5 页

			*action = 2;
		}
		return(0);
	}

	/*
	 * Examine each sibling block to see if we can coalesce with
	 * at least 25% free space to spare.  We need to figure out
	 * whether to merge with the forward or the backward block.
	 * We prefer coalescing with the lower numbered sibling so as
	 * to shrink a directory over time.
	 */
	/* start with smaller blk num */
	forward = (INT_GET(info->forw, ARCH_CONVERT)
				< INT_GET(info->back, ARCH_CONVERT));
	for (i = 0; i < 2; forward = !forward, i++) {
		if (forward)
			blkno = INT_GET(info->forw, ARCH_CONVERT);
		else
			blkno = INT_GET(info->back, ARCH_CONVERT);
		if (blkno == 0)
			continue;
		error = xfs_da_read_buf(state->args->trans, state->args->dp,
					blkno, -1, &bp, state->args->whichfork);
		if (error)
			return(error);
		ASSERT(bp != NULL);

		node = (xfs_da_intnode_t *)info;
		count  = state->node_ents;
		count -= state->node_ents >> 2;
		count -= INT_GET(node->hdr.count, ARCH_CONVERT);
		node = bp->data;
		ASSERT(INT_GET(node->hdr.info.magic, ARCH_CONVERT) == XFS_DA_NODE_MAGIC);
		count -= INT_GET(node->hdr.count, ARCH_CONVERT);
		xfs_da_brelse(state->args->trans, bp);
		if (count >= 0)
			break;	/* fits with at least 25% to spare */
	}
	if (i >= 2) {
		*action = 0;
		return(0);
	}

	/*
	 * Make altpath point to the block we want to keep (the lower
	 * numbered block) and path point to the block we want to drop.
	 */
	memcpy(&state->altpath, &state->path, sizeof(state->path));
	if (blkno < blk->blkno) {
		error = xfs_da_path_shift(state, &state->altpath, forward,
						 0, &retval);
		if (error) {
			return(error);
		}
		if (retval) {
			*action = 0;
			return(0);
		}
	} else {
		error = xfs_da_path_shift(state, &state->path, forward,
						 0, &retval);
		if (error) {
			return(error);
		}
		if (retval) {
			*action = 0;
			return(0);
		}
	}
	*action = 1;
	return(0);
}

/*
 * Walk back up the tree adjusting hash values as necessary,
 * when we stop making changes, return.
 */
void
xfs_da_fixhashpath(xfs_da_state_t *state, xfs_da_state_path_t *path)
{
	xfs_da_state_blk_t *blk;
	xfs_da_intnode_t *node;
	xfs_da_node_entry_t *btree;
	xfs_dahash_t lasthash=0;
	int level, count;

	level = path->active-1;
	blk = &path->blk[ level ];
	switch (blk->magic) {
#ifdef __KERNEL__
	case XFS_ATTR_LEAF_MAGIC:
		lasthash = xfs_attr_leaf_lasthash(blk->bp, &count);
		if (count == 0)
			return;
		break;
#endif
	case XFS_DIR_LEAF_MAGIC:
		ASSERT(XFS_DIR_IS_V1(state->mp));
		lasthash = xfs_dir_leaf_lasthash(blk->bp, &count);
		if (count == 0)
			return;
		break;
	case XFS_DIR2_LEAFN_MAGIC:
		ASSERT(XFS_DIR_IS_V2(state->mp));
		lasthash = xfs_dir2_leafn_lasthash(blk->bp, &count);
		if (count == 0)
			return;
		break;
	case XFS_DA_NODE_MAGIC:
		lasthash = xfs_da_node_lasthash(blk->bp, &count);
		if (count == 0)
			return;
		break;
	}
	for (blk--, level--; level >= 0; blk--, level--) {
		node = blk->bp->data;
		ASSERT(INT_GET(node->hdr.info.magic, ARCH_CONVERT) == XFS_DA_NODE_MAGIC);
		btree = &node->btree[ blk->index ];
		if (INT_GET(btree->hashval, ARCH_CONVERT) == lasthash)
			break;
		blk->hashval = lasthash;
		INT_SET(btree->hashval, ARCH_CONVERT, lasthash);
		xfs_da_log_buf(state->args->trans, blk->bp,
				  XFS_DA_LOGRANGE(node, btree, sizeof(*btree)));

		lasthash = INT_GET(node->btree[ INT_GET(node->hdr.count, ARCH_CONVERT)-1 ].hashval, ARCH_CONVERT);
	}
}

/*
 * Remove an entry from an intermediate node.
 */
STATIC void
xfs_da_node_remove(xfs_da_state_t *state, xfs_da_state_blk_t *drop_blk)
{
	xfs_da_intnode_t *node;
	xfs_da_node_entry_t *btree;
	int tmp;

	node = drop_blk->bp->data;
	ASSERT(drop_blk->index < INT_GET(node->hdr.count, ARCH_CONVERT));
	ASSERT(drop_blk->index >= 0);

	/*
	 * Copy over the offending entry, or just zero it out.
	 */
	btree = &node->btree[drop_blk->index];
	if (drop_blk->index < (INT_GET(node->hdr.count, ARCH_CONVERT)-1)) {
		tmp  = INT_GET(node->hdr.count, ARCH_CONVERT) - drop_blk->index - 1;
		tmp *= (uint)sizeof(xfs_da_node_entry_t);
		memmove(btree, btree + 1, tmp);
		xfs_da_log_buf(state->args->trans, drop_blk->bp,
		    XFS_DA_LOGRANGE(node, btree, tmp));
		btree = &node->btree[ INT_GET(node->hdr.count, ARCH_CONVERT)-1 ];
	}
	memset((char *)btree, 0, sizeof(xfs_da_node_entry_t));
	xfs_da_log_buf(state->args->trans, drop_blk->bp,
	    XFS_DA_LOGRANGE(node, btree, sizeof(*btree)));
	INT_MOD(node->hdr.count, ARCH_CONVERT, -1);
	xfs_da_log_buf(state->args->trans, drop_blk->bp,
	    XFS_DA_LOGRANGE(node, &node->hdr, sizeof(node->hdr)));

	/*
	 * Copy the last hash value from the block to propagate upwards.
	 */
	btree--;
	drop_blk->hashval = INT_GET(btree->hashval, ARCH_CONVERT);
}

/*
 * Unbalance the btree elements between two intermediate nodes,
 * move all Btree elements from one node into another.
 */
STATIC void
xfs_da_node_unbalance(xfs_da_state_t *state, xfs_da_state_blk_t *drop_blk,
				     xfs_da_state_blk_t *save_blk)
{
	xfs_da_intnode_t *drop_node, *save_node;
	xfs_da_node_entry_t *btree;
	int tmp;
	xfs_trans_t *tp;

	drop_node = drop_blk->bp->data;
	save_node = save_blk->bp->data;
	ASSERT(INT_GET(drop_node->hdr.info.magic, ARCH_CONVERT) == XFS_DA_NODE_MAGIC);
	ASSERT(INT_GET(save_node->hdr.info.magic, ARCH_CONVERT) == XFS_DA_NODE_MAGIC);
	tp = state->args->trans;

	/*
	 * If the dying block has lower hashvals, then move all the
	 * elements in the remaining block up to make a hole.
	 */
	if ((INT_GET(drop_node->btree[ 0 ].hashval, ARCH_CONVERT) < INT_GET(save_node->btree[ 0 ].hashval, ARCH_CONVERT)) ||
	    (INT_GET(drop_node->btree[ INT_GET(drop_node->hdr.count, ARCH_CONVERT)-1 ].hashval, ARCH_CONVERT) <
	     INT_GET(save_node->btree[ INT_GET(save_node->hdr.count, ARCH_CONVERT)-1 ].hashval, ARCH_CONVERT)))
	{
		btree = &save_node->btree[ INT_GET(drop_node->hdr.count, ARCH_CONVERT) ];
		tmp = INT_GET(save_node->hdr.count, ARCH_CONVERT) * (uint)sizeof(xfs_da_node_entry_t);
		memmove(btree, &save_node->btree[0], tmp);
		btree = &save_node->btree[0];
		xfs_da_log_buf(tp, save_blk->bp,
			XFS_DA_LOGRANGE(save_node, btree,
				(INT_GET(save_node->hdr.count, ARCH_CONVERT) + INT_GET(drop_node->hdr.count, ARCH_CONVERT)) *
				sizeof(xfs_da_node_entry_t)));
	} else {
		btree = &save_node->btree[ INT_GET(save_node->hdr.count, ARCH_CONVERT) ];
		xfs_da_log_buf(tp, save_blk->bp,
			XFS_DA_LOGRANGE(save_node, btree,
				INT_GET(drop_node->hdr.count, ARCH_CONVERT) *
				sizeof(xfs_da_node_entry_t)));
	}

	/*
	 * Move all the B-tree elements from drop_blk to save_blk.
	 */
	tmp = INT_GET(drop_node->hdr.count, ARCH_CONVERT) * (uint)sizeof(xfs_da_node_entry_t);
	memcpy(btree, &drop_node->btree[0], tmp);
	INT_MOD(save_node->hdr.count, ARCH_CONVERT, INT_GET(drop_node->hdr.count, ARCH_CONVERT));

	xfs_da_log_buf(tp, save_blk->bp,
		XFS_DA_LOGRANGE(save_node, &save_node->hdr,
			sizeof(save_node->hdr)));

	/*
	 * Save the last hashval in the remaining block for upward propagation.
	 */
	save_blk->hashval = INT_GET(save_node->btree[ INT_GET(save_node->hdr.count, ARCH_CONVERT)-1 ].hashval, ARCH_CONVERT);
}

/*========================================================================
 * Routines used for finding things in the Btree.
 *========================================================================*/

/*
 * Walk down the Btree looking for a particular filename, filling
 * in the state structure as we go.
 *
 * We will set the state structure to point to each of the elements
 * in each of the nodes where either the hashval is or should be.
 *
 * We support duplicate hashval's so for each entry in the current
 * node that could contain the desired hashval, descend.  This is a
 * pruned depth-first tree search.
 */
int							/* error */
xfs_da_node_lookup_int(xfs_da_state_t *state, int *result)
{
	xfs_da_state_blk_t *blk;
	xfs_da_blkinfo_t *curr;
	xfs_da_intnode_t *node;
	xfs_da_node_entry_t *btree;
	xfs_dablk_t blkno;
	int probe, span, max, error, retval;
	xfs_dahash_t hashval;
	xfs_da_args_t *args;

	args = state->args;

	/*
	 * Descend thru the B-tree searching each level for the right
	 * node to use, until the right hashval is found.
	 */
	if (args->whichfork == XFS_DATA_FORK && XFS_DIR_IS_V2(state->mp))
		blkno = state->mp->m_dirleafblk;
	else
		blkno = 0;
	for (blk = &state->path.blk[0], state->path.active = 1;
			 state->path.active <= XFS_DA_NODE_MAXDEPTH;
			 blk++, state->path.active++) {
		/*
		 * Read the next node down in the tree.
		 */
		blk->blkno = blkno;
		error = xfs_da_read_buf(args->trans, args->dp, blkno,
					-1, &blk->bp, args->whichfork);
		if (error) {
			blk->blkno = 0;
			state->path.active--;
			return(error);
		}
		curr = blk->bp->data;
		ASSERT(INT_GET(curr->magic, ARCH_CONVERT) == XFS_DA_NODE_MAGIC ||
		       INT_GET(curr->magic, ARCH_CONVERT) == XFS_DIRX_LEAF_MAGIC(state->mp) ||
		       INT_GET(curr->magic, ARCH_CONVERT) == XFS_ATTR_LEAF_MAGIC);

		/*
		 * Search an intermediate node for a match.
		 */
		blk->magic = INT_GET(curr->magic, ARCH_CONVERT);
		if (INT_GET(curr->magic, ARCH_CONVERT) == XFS_DA_NODE_MAGIC) {
			node = blk->bp->data;
			blk->hashval = INT_GET(node->btree[ INT_GET(node->hdr.count, ARCH_CONVERT)-1 ].hashval, ARCH_CONVERT);

			/*
			 * Binary search.  (note: small blocks will skip loop)
			 */
			max = INT_GET(node->hdr.count, ARCH_CONVERT);
			probe = span = max / 2;
			hashval = args->hashval;
			for (btree = &node->btree[probe]; span > 4;
				   btree = &node->btree[probe]) {
				span /= 2;
				if (INT_GET(btree->hashval, ARCH_CONVERT) < hashval)
					probe += span;
				else if (INT_GET(btree->hashval, ARCH_CONVERT) > hashval)
					probe -= span;
				else
					break;
			}
			ASSERT((probe >= 0) && (probe < max));
			ASSERT((span <= 4) || (INT_GET(btree->hashval, ARCH_CONVERT) == hashval));

			/*
			 * Since we may have duplicate hashval's, find the first
			 * matching hashval in the node.
			 */
			while ((probe > 0) && (INT_GET(btree->hashval, ARCH_CONVERT) >= hashval)) {
				btree--;
				probe--;
			}
			while ((probe < max) && (INT_GET(btree->hashval, ARCH_CONVERT) < hashval)) {
				btree++;
				probe++;
			}

			/*
			 * Pick the right block to descend on.
			 */
			if (probe == max) {
				blk->index = max-1;
				blkno = INT_GET(node->btree[ max-1 ].before, ARCH_CONVERT);
			} else {
				blk->index = probe;
				blkno = INT_GET(btree->before, ARCH_CONVERT);
			}
		}
#ifdef __KERNEL__
		else if (INT_GET(curr->magic, ARCH_CONVERT) == XFS_ATTR_LEAF_MAGIC) {
			blk->hashval = xfs_attr_leaf_lasthash(blk->bp, NULL);
			break;
		}
#endif
		else if (INT_GET(curr->magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC) {
			blk->hashval = xfs_dir_leaf_lasthash(blk->bp, NULL);
			break;
		}
		else if (INT_GET(curr->magic, ARCH_CONVERT) == XFS_DIR2_LEAFN_MAGIC) {
			blk->hashval = xfs_dir2_leafn_lasthash(blk->bp, NULL);
			break;
		}
	}

	/*
	 * A leaf block that ends in the hashval that we are interested in
	 * (final hashval == search hashval) means that the next block may
	 * contain more entries with the same hashval, shift upward to the
	 * next leaf and keep searching.
	 */
	for (;;) {
		if (blk->magic == XFS_DIR_LEAF_MAGIC) {
			ASSERT(XFS_DIR_IS_V1(state->mp));
			retval = xfs_dir_leaf_lookup_int(blk->bp, args,
								  &blk->index);
		} else if (blk->magic == XFS_DIR2_LEAFN_MAGIC) {
			ASSERT(XFS_DIR_IS_V2(state->mp));
			retval = xfs_dir2_leafn_lookup_int(blk->bp, args,
							&blk->index, state);
		}
#ifdef __KERNEL__
		else if (blk->magic == XFS_ATTR_LEAF_MAGIC) {
			retval = xfs_attr_leaf_lookup_int(blk->bp, args);
			blk->index = args->index;
			args->blkno = blk->blkno;
		}
#endif
		if (((retval == ENOENT) || (retval == ENOATTR)) &&
		    (blk->hashval == args->hashval)) {
			error = xfs_da_path_shift(state, &state->path, 1, 1,
							 &retval);
			if (error)
				return(error);
			if (retval == 0) {
				continue;
			}
#ifdef __KERNEL__
			else if (blk->magic == XFS_ATTR_LEAF_MAGIC) {
				/* path_shift() gives ENOENT */
				retval = XFS_ERROR(ENOATTR);
			}
#endif
		}
		break;
	}
	*result = retval;
	return(0);
}

/*========================================================================
 * Utility routines.
 *========================================================================*/

/*
 * Link a new block into a doubly linked list of blocks (of whatever type).
 */
int							/* error */
xfs_da_blk_link(xfs_da_state_t *state, xfs_da_state_blk_t *old_blk,
			       xfs_da_state_blk_t *new_blk)
{
	xfs_da_blkinfo_t *old_info, *new_info, *tmp_info;
	xfs_da_args_t *args;
	int before=0, error;
	xfs_dabuf_t *bp;

	/*
	 * Set up environment.
	 */
	args = state->args;
	ASSERT(args != NULL);
	old_info = old_blk->bp->data;
	new_info = new_blk->bp->data;
	ASSERT(old_blk->magic == XFS_DA_NODE_MAGIC ||
	       old_blk->magic == XFS_DIRX_LEAF_MAGIC(state->mp) ||
	       old_blk->magic == XFS_ATTR_LEAF_MAGIC);
	ASSERT(old_blk->magic == INT_GET(old_info->magic, ARCH_CONVERT));
	ASSERT(new_blk->magic == INT_GET(new_info->magic, ARCH_CONVERT));
	ASSERT(old_blk->magic == new_blk->magic);

	switch (old_blk->magic) {
#ifdef __KERNEL__
	case XFS_ATTR_LEAF_MAGIC:
		before = xfs_attr_leaf_order(old_blk->bp, new_blk->bp);
		break;
#endif
	case XFS_DIR_LEAF_MAGIC:
		ASSERT(XFS_DIR_IS_V1(state->mp));
		before = xfs_dir_leaf_order(old_blk->bp, new_blk->bp);
		break;
	case XFS_DIR2_LEAFN_MAGIC:
		ASSERT(XFS_DIR_IS_V2(state->mp));
		before = xfs_dir2_leafn_order(old_blk->bp, new_blk->bp);