xfs_da_btree.c

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

		break;
	case XFS_DA_NODE_MAGIC:
		before = xfs_da_node_order(old_blk->bp, new_blk->bp);
		break;
	}

	/*
	 * Link blocks in appropriate order.
	 */
	if (before) {
		/*
		 * Link new block in before existing block.
		 */
		INT_SET(new_info->forw, ARCH_CONVERT, old_blk->blkno);
		new_info->back = old_info->back; /* INT_: direct copy */
		if (INT_GET(old_info->back, ARCH_CONVERT)) {
			error = xfs_da_read_buf(args->trans, args->dp,
						INT_GET(old_info->back,
							ARCH_CONVERT), -1, &bp,
						args->whichfork);
			if (error)
				return(error);
			ASSERT(bp != NULL);
			tmp_info = bp->data;
			ASSERT(INT_GET(tmp_info->magic, ARCH_CONVERT) == INT_GET(old_info->magic, ARCH_CONVERT));
			ASSERT(INT_GET(tmp_info->forw, ARCH_CONVERT) == old_blk->blkno);
			INT_SET(tmp_info->forw, ARCH_CONVERT, new_blk->blkno);
			xfs_da_log_buf(args->trans, bp, 0, sizeof(*tmp_info)-1);
			xfs_da_buf_done(bp);
		}
		INT_SET(old_info->back, ARCH_CONVERT, new_blk->blkno);
	} else {
		/*
		 * Link new block in after existing block.
		 */
		new_info->forw = old_info->forw; /* INT_: direct copy */
		INT_SET(new_info->back, ARCH_CONVERT, old_blk->blkno);
		if (INT_GET(old_info->forw, ARCH_CONVERT)) {
			error = xfs_da_read_buf(args->trans, args->dp,
						INT_GET(old_info->forw, ARCH_CONVERT), -1, &bp,
						args->whichfork);
			if (error)
				return(error);
			ASSERT(bp != NULL);
			tmp_info = bp->data;
			ASSERT(INT_GET(tmp_info->magic, ARCH_CONVERT)
				    == INT_GET(old_info->magic, ARCH_CONVERT));
			ASSERT(INT_GET(tmp_info->back, ARCH_CONVERT)
				    == old_blk->blkno);
			INT_SET(tmp_info->back, ARCH_CONVERT, new_blk->blkno);
			xfs_da_log_buf(args->trans, bp, 0, sizeof(*tmp_info)-1);
			xfs_da_buf_done(bp);
		}
		INT_SET(old_info->forw, ARCH_CONVERT, new_blk->blkno);
	}

	xfs_da_log_buf(args->trans, old_blk->bp, 0, sizeof(*tmp_info) - 1);
	xfs_da_log_buf(args->trans, new_blk->bp, 0, sizeof(*tmp_info) - 1);
	return(0);
}

/*
 * Compare two intermediate nodes for "order".
 */
STATIC int
xfs_da_node_order(xfs_dabuf_t *node1_bp, xfs_dabuf_t *node2_bp)
{
	xfs_da_intnode_t *node1, *node2;

	node1 = node1_bp->data;
	node2 = node2_bp->data;
	ASSERT((INT_GET(node1->hdr.info.magic, ARCH_CONVERT) == XFS_DA_NODE_MAGIC) &&
	       (INT_GET(node2->hdr.info.magic, ARCH_CONVERT) == XFS_DA_NODE_MAGIC));
	if ((INT_GET(node1->hdr.count, ARCH_CONVERT) > 0) && (INT_GET(node2->hdr.count, ARCH_CONVERT) > 0) &&
	    ((INT_GET(node2->btree[ 0 ].hashval, ARCH_CONVERT) <
	      INT_GET(node1->btree[ 0 ].hashval, ARCH_CONVERT)) ||
	     (INT_GET(node2->btree[ INT_GET(node2->hdr.count, ARCH_CONVERT)-1 ].hashval, ARCH_CONVERT) <
	      INT_GET(node1->btree[ INT_GET(node1->hdr.count, ARCH_CONVERT)-1 ].hashval, ARCH_CONVERT)))) {
		return(1);
	}
	return(0);
}

/*
 * Pick up the last hashvalue from an intermediate node.
 */
STATIC uint
xfs_da_node_lasthash(xfs_dabuf_t *bp, int *count)
{
	xfs_da_intnode_t *node;

	node = bp->data;
	ASSERT(INT_GET(node->hdr.info.magic, ARCH_CONVERT) == XFS_DA_NODE_MAGIC);
	if (count)
		*count = INT_GET(node->hdr.count, ARCH_CONVERT);
	if (INT_ISZERO(node->hdr.count, ARCH_CONVERT))
		return(0);
	return(INT_GET(node->btree[ INT_GET(node->hdr.count, ARCH_CONVERT)-1 ].hashval, ARCH_CONVERT));
}

/*
 * Unlink a block from a doubly linked list of blocks.
 */
int							/* error */
xfs_da_blk_unlink(xfs_da_state_t *state, xfs_da_state_blk_t *drop_blk,
				 xfs_da_state_blk_t *save_blk)
{
	xfs_da_blkinfo_t *drop_info, *save_info, *tmp_info;
	xfs_da_args_t *args;
	xfs_dabuf_t *bp;
	int error;

	/*
	 * Set up environment.
	 */
	args = state->args;
	ASSERT(args != NULL);
	save_info = save_blk->bp->data;
	drop_info = drop_blk->bp->data;
	ASSERT(save_blk->magic == XFS_DA_NODE_MAGIC ||
	       save_blk->magic == XFS_DIRX_LEAF_MAGIC(state->mp) ||
	       save_blk->magic == XFS_ATTR_LEAF_MAGIC);
	ASSERT(save_blk->magic == INT_GET(save_info->magic, ARCH_CONVERT));
	ASSERT(drop_blk->magic == INT_GET(drop_info->magic, ARCH_CONVERT));
	ASSERT(save_blk->magic == drop_blk->magic);
	ASSERT((INT_GET(save_info->forw, ARCH_CONVERT) == drop_blk->blkno) ||
	       (INT_GET(save_info->back, ARCH_CONVERT) == drop_blk->blkno));
	ASSERT((INT_GET(drop_info->forw, ARCH_CONVERT) == save_blk->blkno) ||
	       (INT_GET(drop_info->back, ARCH_CONVERT) == save_blk->blkno));

	/*
	 * Unlink the leaf block from the doubly linked chain of leaves.
	 */
	if (INT_GET(save_info->back, ARCH_CONVERT) == drop_blk->blkno) {
		save_info->back = drop_info->back; /* INT_: direct copy */
		if (INT_GET(drop_info->back, ARCH_CONVERT)) {
			error = xfs_da_read_buf(args->trans, args->dp,
						INT_GET(drop_info->back,
							ARCH_CONVERT), -1, &bp,
						args->whichfork);
			if (error)
				return(error);
			ASSERT(bp != NULL);
			tmp_info = bp->data;
			ASSERT(INT_GET(tmp_info->magic, ARCH_CONVERT) == INT_GET(save_info->magic, ARCH_CONVERT));
			ASSERT(INT_GET(tmp_info->forw, ARCH_CONVERT) == drop_blk->blkno);
			INT_SET(tmp_info->forw, ARCH_CONVERT, save_blk->blkno);
			xfs_da_log_buf(args->trans, bp, 0,
						    sizeof(*tmp_info) - 1);
			xfs_da_buf_done(bp);
		}
	} else {
		save_info->forw = drop_info->forw; /* INT_: direct copy */
		if (INT_GET(drop_info->forw, ARCH_CONVERT)) {
			error = xfs_da_read_buf(args->trans, args->dp,
						INT_GET(drop_info->forw, ARCH_CONVERT), -1, &bp,
						args->whichfork);
			if (error)
				return(error);
			ASSERT(bp != NULL);
			tmp_info = bp->data;
			ASSERT(INT_GET(tmp_info->magic, ARCH_CONVERT)
				    == INT_GET(save_info->magic, ARCH_CONVERT));
			ASSERT(INT_GET(tmp_info->back, ARCH_CONVERT)
				    == drop_blk->blkno);
			INT_SET(tmp_info->back, ARCH_CONVERT, save_blk->blkno);
			xfs_da_log_buf(args->trans, bp, 0,
						    sizeof(*tmp_info) - 1);
			xfs_da_buf_done(bp);
		}
	}

	xfs_da_log_buf(args->trans, save_blk->bp, 0, sizeof(*save_info) - 1);
	return(0);
}

/*
 * Move a path "forward" or "!forward" one block at the current level.
 *
 * This routine will adjust a "path" to point to the next block
 * "forward" (higher hashvalues) or "!forward" (lower hashvals) in the
 * Btree, including updating pointers to the intermediate nodes between
 * the new bottom and the root.
 */
int							/* error */
xfs_da_path_shift(xfs_da_state_t *state, xfs_da_state_path_t *path,
				 int forward, int release, int *result)
{
	xfs_da_state_blk_t *blk;
	xfs_da_blkinfo_t *info;
	xfs_da_intnode_t *node;
	xfs_da_args_t *args;
	xfs_dablk_t blkno=0;
	int level, error;

	/*
	 * Roll up the Btree looking for the first block where our
	 * current index is not at the edge of the block.  Note that
	 * we skip the bottom layer because we want the sibling block.
	 */
	args = state->args;
	ASSERT(args != NULL);
	ASSERT(path != NULL);
	ASSERT((path->active > 0) && (path->active < XFS_DA_NODE_MAXDEPTH));
	level = (path->active-1) - 1;	/* skip bottom layer in path */
	for (blk = &path->blk[level]; level >= 0; blk--, level--) {
		ASSERT(blk->bp != NULL);
		node = blk->bp->data;
		ASSERT(INT_GET(node->hdr.info.magic, ARCH_CONVERT) == XFS_DA_NODE_MAGIC);
		if (forward && (blk->index < INT_GET(node->hdr.count, ARCH_CONVERT)-1)) {
			blk->index++;
			blkno = INT_GET(node->btree[ blk->index ].before, ARCH_CONVERT);
			break;
		} else if (!forward && (blk->index > 0)) {
			blk->index--;
			blkno = INT_GET(node->btree[ blk->index ].before, ARCH_CONVERT);
			break;
		}
	}
	if (level < 0) {
		*result = XFS_ERROR(ENOENT);	/* we're out of our tree */
		ASSERT(args->oknoent);
		return(0);
	}

	/*
	 * Roll down the edge of the subtree until we reach the
	 * same depth we were at originally.
	 */
	for (blk++, level++; level < path->active; blk++, level++) {
		/*
		 * Release the old block.
		 * (if it's dirty, trans won't actually let go)
		 */
		if (release)
			xfs_da_brelse(args->trans, blk->bp);

		/*
		 * Read the next child block.
		 */
		blk->blkno = blkno;
		error = xfs_da_read_buf(args->trans, args->dp, blkno, -1,
						     &blk->bp, args->whichfork);
		if (error)
			return(error);
		ASSERT(blk->bp != NULL);
		info = blk->bp->data;
		ASSERT(INT_GET(info->magic, ARCH_CONVERT) == XFS_DA_NODE_MAGIC ||
		       INT_GET(info->magic, ARCH_CONVERT) == XFS_DIRX_LEAF_MAGIC(state->mp) ||
		       INT_GET(info->magic, ARCH_CONVERT) == XFS_ATTR_LEAF_MAGIC);
		blk->magic = INT_GET(info->magic, ARCH_CONVERT);
		if (INT_GET(info->magic, ARCH_CONVERT) == XFS_DA_NODE_MAGIC) {
			node = (xfs_da_intnode_t *)info;
			blk->hashval = INT_GET(node->btree[ INT_GET(node->hdr.count, ARCH_CONVERT)-1 ].hashval, ARCH_CONVERT);
			if (forward)
				blk->index = 0;
			else
				blk->index = INT_GET(node->hdr.count, ARCH_CONVERT)-1;
			blkno = INT_GET(node->btree[ blk->index ].before, ARCH_CONVERT);
		} else {
			ASSERT(level == path->active-1);
			blk->index = 0;
			switch(blk->magic) {
#ifdef __KERNEL__
			case XFS_ATTR_LEAF_MAGIC:
				blk->hashval = xfs_attr_leaf_lasthash(blk->bp,
								      NULL);
				break;
#endif
			case XFS_DIR_LEAF_MAGIC:
				ASSERT(XFS_DIR_IS_V1(state->mp));
				blk->hashval = xfs_dir_leaf_lasthash(blk->bp,
								     NULL);
				break;
			case XFS_DIR2_LEAFN_MAGIC:
				ASSERT(XFS_DIR_IS_V2(state->mp));
				blk->hashval = xfs_dir2_leafn_lasthash(blk->bp,
								       NULL);
				break;
			default:
				ASSERT(blk->magic == XFS_ATTR_LEAF_MAGIC ||
				       blk->magic ==
				       XFS_DIRX_LEAF_MAGIC(state->mp));
				break;
			}
		}
	}
	*result = 0;
	return(0);
}


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

/*
 * Implement a simple hash on a character string.
 * Rotate the hash value by 7 bits, then XOR each character in.
 * This is implemented with some source-level loop unrolling.
 */
xfs_dahash_t
xfs_da_hashname(uchar_t *name, int namelen)
{
	xfs_dahash_t hash;

#define	ROTL(x,y)	(((x) << (y)) | ((x) >> (32 - (y))))
#ifdef SLOWVERSION
	/*
	 * This is the old one-byte-at-a-time version.
	 */
	for (hash = 0; namelen > 0; namelen--) {
		hash = *name++ ^ ROTL(hash, 7);
	}
	return(hash);
#else
	/*
	 * Do four characters at a time as long as we can.
	 */
	for (hash = 0; namelen >= 4; namelen -= 4, name += 4) {
		hash = (name[0] << 21) ^ (name[1] << 14) ^ (name[2] << 7) ^
		       (name[3] << 0) ^ ROTL(hash, 7 * 4);
	}
	/*
	 * Now do the rest of the characters.
	 */
	switch (namelen) {
	case 3:
		return (name[0] << 14) ^ (name[1] << 7) ^ (name[2] << 0) ^
		       ROTL(hash, 7 * 3);
	case 2:
		return (name[0] << 7) ^ (name[1] << 0) ^ ROTL(hash, 7 * 2);
	case 1:
		return (name[0] << 0) ^ ROTL(hash, 7 * 1);
	case 0:
		return hash;
	}
	/* NOTREACHED */
#endif
#undef ROTL
	return 0; /* keep gcc happy */
}

/*
 * Add a block to the btree ahead of the file.
 * Return the new block number to the caller.
 */
int
xfs_da_grow_inode(xfs_da_args_t *args, xfs_dablk_t *new_blkno)
{
	xfs_fileoff_t bno, b;
	xfs_bmbt_irec_t map;
	xfs_bmbt_irec_t	*mapp;
	xfs_inode_t *dp;
	int nmap, error, w, count, c, got, i, mapi;
	xfs_fsize_t size;
	xfs_trans_t *tp;
	xfs_mount_t *mp;

	dp = args->dp;
	mp = dp->i_mount;
	w = args->whichfork;
	tp = args->trans;
	/*
	 * For new directories adjust the file offset and block count.
	 */
	if (w == XFS_DATA_FORK && XFS_DIR_IS_V2(mp)) {
		bno = mp->m_dirleafblk;
		count = mp->m_dirblkfsbs;
	} else {
		bno = 0;
		count = 1;
	}
	/*
	 * Find a spot in the file space to put the new block.
	 */
	if ((error = xfs_bmap_first_unused(tp, dp, count, &bno, w))) {
		return error;
	}
	if (w == XFS_DATA_FORK && XFS_DIR_IS_V2(mp))
		ASSERT(bno >= mp->m_dirleafblk && bno < mp->m_dirfreeblk);
	/*
	 * Try mapping it in one filesystem block.
	 */
	nmap = 1;
	ASSERT(args->firstblock != NULL);
	if ((error = xfs_bmapi(tp, dp, bno, count,
			XFS_BMAPI_AFLAG(w)|XFS_BMAPI_WRITE|XFS_BMAPI_METADATA|
			XFS_BMAPI_CONTIG,
			args->firstblock, args->total, &map, &nmap,
			args->flist))) {
		return error;
	}
	ASSERT(nmap <= 1);
	if (nmap == 1) {
		mapp = &map;
		mapi = 1;
	}
	/*
	 * If we didn't get it and the block might work if fragmented,
	 * try without the CONTIG flag.  Loop until we get it all.
	 */
	else if (nmap == 0 && count > 1) {
		mapp = kmem_alloc(sizeof(*mapp) * count, KM_SLEEP);
		for (b = bno, mapi = 0; b < bno + count; ) {
			nmap = MIN(XFS_BMAP_MAX_NMAP, count);
			c = (int)(bno + count - b);
			if ((error = xfs_bmapi(tp, dp, b, c,
					XFS_BMAPI_AFLAG(w)|XFS_BMAPI_WRITE|
					XFS_BMAPI_METADATA,
					args->firstblock, args->total,
					&mapp[mapi], &nmap, args->flist))) {
				kmem_free(mapp, sizeof(*mapp) * count);
				return error;
			}
			if (nmap < 1)
				break;
			mapi += nmap;
			b = mapp[mapi - 1].br_startoff +
			    mapp[mapi - 1].br_blockcount;
		}
	} else {
		mapi = 0;
		mapp = NULL;
	}
	/*
	 * Count the blocks we got, make sure it matches the total.
	 */
	for (i = 0, got = 0; i < mapi; i++)
		got += mapp[i].br_blockcount;
	if (got != count || mapp[0].br_startoff != bno ||
	    mapp[mapi - 1].br_startoff + mapp[mapi - 1].br_blockcount !=
	    bno + count) {
		if (mapp != &map)
			kmem_free(mapp, sizeof(*mapp) * count);
		return XFS_ERROR(ENOSPC);
	}
	if (mapp != &map)
		kmem_free(mapp, sizeof(*mapp) * count);
	*new_blkno = (xfs_dablk_t)bno;
	/*