xfs_alloc_btree.c

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

		xfs_alloc_rec_t	*lrp;	/* record pointer for left block */

		lrp = XFS_ALLOC_REC_ADDR(left, nrec, cur);
		rrp = XFS_ALLOC_REC_ADDR(right, 1, cur);
		*lrp = *rrp;
		xfs_alloc_log_recs(cur, lbp, nrec, nrec);
		xfs_btree_check_rec(cur->bc_btnum, lrp - 1, lrp);
	}
	/*
	 * Bump and log left's numrecs, decrement and log right's numrecs.
	 */
	INT_MOD(left->bb_numrecs, ARCH_CONVERT, +1);
	xfs_alloc_log_block(cur->bc_tp, lbp, XFS_BB_NUMRECS);
	INT_MOD(right->bb_numrecs, ARCH_CONVERT, -1);
	xfs_alloc_log_block(cur->bc_tp, rbp, XFS_BB_NUMRECS);
	/*
	 * Slide the contents of right down one entry.
	 */
	if (level > 0) {
#ifdef DEBUG
		for (i = 0; i < INT_GET(right->bb_numrecs, ARCH_CONVERT); i++) {
			if ((error = xfs_btree_check_sptr(cur, INT_GET(rpp[i + 1], ARCH_CONVERT),
					level)))
				return error;
		}
#endif
		memmove(rkp, rkp + 1, INT_GET(right->bb_numrecs, ARCH_CONVERT) * sizeof(*rkp));
		memmove(rpp, rpp + 1, INT_GET(right->bb_numrecs, ARCH_CONVERT) * sizeof(*rpp));
		xfs_alloc_log_keys(cur, rbp, 1, INT_GET(right->bb_numrecs, ARCH_CONVERT));
		xfs_alloc_log_ptrs(cur, rbp, 1, INT_GET(right->bb_numrecs, ARCH_CONVERT));
	} else {
		memmove(rrp, rrp + 1, INT_GET(right->bb_numrecs, ARCH_CONVERT) * sizeof(*rrp));
		xfs_alloc_log_recs(cur, rbp, 1, INT_GET(right->bb_numrecs, ARCH_CONVERT));
		key.ar_startblock = rrp->ar_startblock; /* INT_: direct copy */
		key.ar_blockcount = rrp->ar_blockcount; /* INT_: direct copy */
		rkp = &key;
	}
	/*
	 * Update the parent key values of right.
	 */
	if ((error = xfs_alloc_updkey(cur, rkp, level + 1)))
		return error;
	/*
	 * Slide the cursor value left one.
	 */
	cur->bc_ptrs[level]--;
	*stat = 1;
	return 0;
}

/*
 * Allocate a new root block, fill it in.
 */
STATIC int				/* error */
xfs_alloc_newroot(
	xfs_btree_cur_t		*cur,	/* btree cursor */
	int			*stat)	/* success/failure */
{
	int			error;	/* error return value */
	xfs_agblock_t		lbno;	/* left block number */
	xfs_buf_t		*lbp;	/* left btree buffer */
	xfs_alloc_block_t	*left;	/* left btree block */
	xfs_mount_t		*mp;	/* mount structure */
	xfs_agblock_t		nbno;	/* new block number */
	xfs_buf_t		*nbp;	/* new (root) buffer */
	xfs_alloc_block_t	*new;	/* new (root) btree block */
	int			nptr;	/* new value for key index, 1 or 2 */
	xfs_agblock_t		rbno;	/* right block number */
	xfs_buf_t		*rbp;	/* right btree buffer */
	xfs_alloc_block_t	*right;	/* right btree block */

	mp = cur->bc_mp;

	ASSERT(cur->bc_nlevels < XFS_AG_MAXLEVELS(mp));
	/*
	 * Get a buffer from the freelist blocks, for the new root.
	 */
	if ((error = xfs_alloc_get_freelist(cur->bc_tp, cur->bc_private.a.agbp,
			&nbno)))
		return error;
	/*
	 * None available, we fail.
	 */
	if (nbno == NULLAGBLOCK) {
		*stat = 0;
		return 0;
	}
	xfs_trans_agbtree_delta(cur->bc_tp, 1);
	nbp = xfs_btree_get_bufs(mp, cur->bc_tp, cur->bc_private.a.agno, nbno,
		0);
	new = XFS_BUF_TO_ALLOC_BLOCK(nbp);
	/*
	 * Set the root data in the a.g. freespace structure.
	 */
	{
		xfs_agf_t	*agf;	/* a.g. freespace header */
		xfs_agnumber_t	seqno;

		agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
		INT_SET(agf->agf_roots[cur->bc_btnum], ARCH_CONVERT, nbno);
		INT_MOD(agf->agf_levels[cur->bc_btnum], ARCH_CONVERT, 1);
		seqno = INT_GET(agf->agf_seqno, ARCH_CONVERT);
		mp->m_perag[seqno].pagf_levels[cur->bc_btnum]++;
		xfs_alloc_log_agf(cur->bc_tp, cur->bc_private.a.agbp,
			XFS_AGF_ROOTS | XFS_AGF_LEVELS);
	}
	/*
	 * At the previous root level there are now two blocks: the old
	 * root, and the new block generated when it was split.
	 * We don't know which one the cursor is pointing at, so we
	 * set up variables "left" and "right" for each case.
	 */
	lbp = cur->bc_bufs[cur->bc_nlevels - 1];
	left = XFS_BUF_TO_ALLOC_BLOCK(lbp);
#ifdef DEBUG
	if ((error = xfs_btree_check_sblock(cur, left, cur->bc_nlevels - 1, lbp)))
		return error;
#endif
	if (INT_GET(left->bb_rightsib, ARCH_CONVERT) != NULLAGBLOCK) {
		/*
		 * Our block is left, pick up the right block.
		 */
		lbno = XFS_DADDR_TO_AGBNO(mp, XFS_BUF_ADDR(lbp));
		rbno = INT_GET(left->bb_rightsib, ARCH_CONVERT);
		if ((error = xfs_btree_read_bufs(mp, cur->bc_tp,
				cur->bc_private.a.agno, rbno, 0, &rbp,
				XFS_ALLOC_BTREE_REF)))
			return error;
		right = XFS_BUF_TO_ALLOC_BLOCK(rbp);
		if ((error = xfs_btree_check_sblock(cur, right,
				cur->bc_nlevels - 1, rbp)))
			return error;
		nptr = 1;
	} else {
		/*
		 * Our block is right, pick up the left block.
		 */
		rbp = lbp;
		right = left;
		rbno = XFS_DADDR_TO_AGBNO(mp, XFS_BUF_ADDR(rbp));
		lbno = INT_GET(right->bb_leftsib, ARCH_CONVERT);
		if ((error = xfs_btree_read_bufs(mp, cur->bc_tp,
				cur->bc_private.a.agno, lbno, 0, &lbp,
				XFS_ALLOC_BTREE_REF)))
			return error;
		left = XFS_BUF_TO_ALLOC_BLOCK(lbp);
		if ((error = xfs_btree_check_sblock(cur, left,
				cur->bc_nlevels - 1, lbp)))
			return error;
		nptr = 2;
	}
	/*
	 * Fill in the new block's btree header and log it.
	 */
	INT_SET(new->bb_magic, ARCH_CONVERT, xfs_magics[cur->bc_btnum]);
	INT_SET(new->bb_level, ARCH_CONVERT, (__uint16_t)cur->bc_nlevels);
	INT_SET(new->bb_numrecs, ARCH_CONVERT, 2);
	INT_SET(new->bb_leftsib, ARCH_CONVERT, NULLAGBLOCK);
	INT_SET(new->bb_rightsib, ARCH_CONVERT, NULLAGBLOCK);
	xfs_alloc_log_block(cur->bc_tp, nbp, XFS_BB_ALL_BITS);
	ASSERT(lbno != NULLAGBLOCK && rbno != NULLAGBLOCK);
	/*
	 * Fill in the key data in the new root.
	 */
	{
		xfs_alloc_key_t		*kp;	/* btree key pointer */

		kp = XFS_ALLOC_KEY_ADDR(new, 1, cur);
		if (INT_GET(left->bb_level, ARCH_CONVERT) > 0) {
			kp[0] = *XFS_ALLOC_KEY_ADDR(left, 1, cur); /* INT_: structure copy */
			kp[1] = *XFS_ALLOC_KEY_ADDR(right, 1, cur);/* INT_: structure copy */
		} else {
			xfs_alloc_rec_t	*rp;	/* btree record pointer */

			rp = XFS_ALLOC_REC_ADDR(left, 1, cur);
			kp[0].ar_startblock = rp->ar_startblock; /* INT_: direct copy */
			kp[0].ar_blockcount = rp->ar_blockcount; /* INT_: direct copy */
			rp = XFS_ALLOC_REC_ADDR(right, 1, cur);
			kp[1].ar_startblock = rp->ar_startblock; /* INT_: direct copy */
			kp[1].ar_blockcount = rp->ar_blockcount; /* INT_: direct copy */
		}
	}
	xfs_alloc_log_keys(cur, nbp, 1, 2);
	/*
	 * Fill in the pointer data in the new root.
	 */
	{
		xfs_alloc_ptr_t		*pp;	/* btree address pointer */

		pp = XFS_ALLOC_PTR_ADDR(new, 1, cur);
		INT_SET(pp[0], ARCH_CONVERT, lbno);
		INT_SET(pp[1], ARCH_CONVERT, rbno);
	}
	xfs_alloc_log_ptrs(cur, nbp, 1, 2);
	/*
	 * Fix up the cursor.
	 */
	xfs_btree_setbuf(cur, cur->bc_nlevels, nbp);
	cur->bc_ptrs[cur->bc_nlevels] = nptr;
	cur->bc_nlevels++;
	*stat = 1;
	return 0;
}

/*
 * Move 1 record right from cur/level if possible.
 * Update cur to reflect the new path.
 */
STATIC int				/* error */
xfs_alloc_rshift(
	xfs_btree_cur_t		*cur,	/* btree cursor */
	int			level,	/* level to shift record on */
	int			*stat)	/* success/failure */
{
	int			error;	/* error return value */
	int			i;	/* loop index */
	xfs_alloc_key_t		key;	/* key value for leaf level upward */
	xfs_buf_t		*lbp;	/* buffer for left (current) block */
	xfs_alloc_block_t	*left;	/* left (current) btree block */
	xfs_buf_t		*rbp;	/* buffer for right neighbor block */
	xfs_alloc_block_t	*right;	/* right neighbor btree block */
	xfs_alloc_key_t		*rkp;	/* key pointer for right block */
	xfs_btree_cur_t		*tcur;	/* temporary cursor */

	/*
	 * Set up variables for this block as "left".
	 */
	lbp = cur->bc_bufs[level];
	left = XFS_BUF_TO_ALLOC_BLOCK(lbp);
#ifdef DEBUG
	if ((error = xfs_btree_check_sblock(cur, left, level, lbp)))
		return error;
#endif
	/*
	 * If we've got no right sibling then we can't shift an entry right.
	 */
	if (INT_GET(left->bb_rightsib, ARCH_CONVERT) == NULLAGBLOCK) {
		*stat = 0;
		return 0;
	}
	/*
	 * If the cursor entry is the one that would be moved, don't
	 * do it... it's too complicated.
	 */
	if (cur->bc_ptrs[level] >= INT_GET(left->bb_numrecs, ARCH_CONVERT)) {
		*stat = 0;
		return 0;
	}
	/*
	 * Set up the right neighbor as "right".
	 */
	if ((error = xfs_btree_read_bufs(cur->bc_mp, cur->bc_tp,
			cur->bc_private.a.agno, INT_GET(left->bb_rightsib, ARCH_CONVERT), 0, &rbp,
			XFS_ALLOC_BTREE_REF)))
		return error;
	right = XFS_BUF_TO_ALLOC_BLOCK(rbp);
	if ((error = xfs_btree_check_sblock(cur, right, level, rbp)))
		return error;
	/*
	 * If it's full, it can't take another entry.
	 */
	if (INT_GET(right->bb_numrecs, ARCH_CONVERT) == XFS_ALLOC_BLOCK_MAXRECS(level, cur)) {
		*stat = 0;
		return 0;
	}
	/*
	 * Make a hole at the start of the right neighbor block, then
	 * copy the last left block entry to the hole.
	 */
	if (level > 0) {
		xfs_alloc_key_t	*lkp;	/* key pointer for left block */
		xfs_alloc_ptr_t	*lpp;	/* address pointer for left block */
		xfs_alloc_ptr_t	*rpp;	/* address pointer for right block */

		lkp = XFS_ALLOC_KEY_ADDR(left, INT_GET(left->bb_numrecs, ARCH_CONVERT), cur);
		lpp = XFS_ALLOC_PTR_ADDR(left, INT_GET(left->bb_numrecs, ARCH_CONVERT), cur);
		rkp = XFS_ALLOC_KEY_ADDR(right, 1, cur);
		rpp = XFS_ALLOC_PTR_ADDR(right, 1, cur);
#ifdef DEBUG
		for (i = INT_GET(right->bb_numrecs, ARCH_CONVERT) - 1; i >= 0; i--) {
			if ((error = xfs_btree_check_sptr(cur, INT_GET(rpp[i], ARCH_CONVERT), level)))
				return error;
		}
#endif
		memmove(rkp + 1, rkp, INT_GET(right->bb_numrecs, ARCH_CONVERT) * sizeof(*rkp));
		memmove(rpp + 1, rpp, INT_GET(right->bb_numrecs, ARCH_CONVERT) * sizeof(*rpp));
#ifdef DEBUG
		if ((error = xfs_btree_check_sptr(cur, INT_GET(*lpp, ARCH_CONVERT), level)))
			return error;
#endif
		*rkp = *lkp; /* INT_: copy */
		*rpp = *lpp; /* INT_: copy */
		xfs_alloc_log_keys(cur, rbp, 1, INT_GET(right->bb_numrecs, ARCH_CONVERT) + 1);
		xfs_alloc_log_ptrs(cur, rbp, 1, INT_GET(right->bb_numrecs, ARCH_CONVERT) + 1);
		xfs_btree_check_key(cur->bc_btnum, rkp, rkp + 1);
	} else {
		xfs_alloc_rec_t	*lrp;	/* record pointer for left block */
		xfs_alloc_rec_t	*rrp;	/* record pointer for right block */

		lrp = XFS_ALLOC_REC_ADDR(left, INT_GET(left->bb_numrecs, ARCH_CONVERT), cur);
		rrp = XFS_ALLOC_REC_ADDR(right, 1, cur);
		memmove(rrp + 1, rrp, INT_GET(right->bb_numrecs, ARCH_CONVERT) * sizeof(*rrp));
		*rrp = *lrp;
		xfs_alloc_log_recs(cur, rbp, 1, INT_GET(right->bb_numrecs, ARCH_CONVERT) + 1);
		key.ar_startblock = rrp->ar_startblock; /* INT_: direct copy */
		key.ar_blockcount = rrp->ar_blockcount; /* INT_: direct copy */
		rkp = &key;
		xfs_btree_check_rec(cur->bc_btnum, rrp, rrp + 1);
	}
	/*
	 * Decrement and log left's numrecs, bump and log right's numrecs.
	 */
	INT_MOD(left->bb_numrecs, ARCH_CONVERT, -1);
	xfs_alloc_log_block(cur->bc_tp, lbp, XFS_BB_NUMRECS);
	INT_MOD(right->bb_numrecs, ARCH_CONVERT, +1);
	xfs_alloc_log_block(cur->bc_tp, rbp, XFS_BB_NUMRECS);
	/*
	 * Using a temporary cursor, update the parent key values of the
	 * block on the right.
	 */
	if ((error = xfs_btree_dup_cursor(cur, &tcur)))
		return error;
	i = xfs_btree_lastrec(tcur, level);
	XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
	if ((error = xfs_alloc_increment(tcur, level, &i)) ||
	    (error = xfs_alloc_updkey(tcur, rkp, level + 1)))
		goto error0;
	xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
	*stat = 1;
	return 0;
error0:
	xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
	return error;
}

/*
 * Split cur/level block in half.
 * Return new block number and its first record (to be inserted into parent).
 */
STATIC int				/* error */
xfs_alloc_split(
	xfs_btree_cur_t		*cur,	/* btree cursor */
	int			level,	/* level to split */
	xfs_agblock_t		*bnop,	/* output: block number allocated */
	xfs_alloc_key_t		*keyp,	/* output: first key of new block */
	xfs_btree_cur_t		**curp,	/* output: new cursor */
	int			*stat)	/* success/failure */
{
	int			error;	/* error return value */
	int			i;	/* loop index/record number */
	xfs_agblock_t		lbno;	/* left (current) block number */
	xfs_buf_t		*lbp;	/* buffer for left block */
	xfs_alloc_block_t	*left;	/* left (current) btree block */
	xfs_agblock_t		rbno;	/* right (new) block number */
	xfs_buf_t		*rbp;	/* buffer for right block */
	xfs_alloc_block_t	*right;	/* right (new) btree block */

	/*
	 * Allocate the new block from the freelist.
	 * If we can't do it, we're toast.  Give up.
	 */
	if ((error = xfs_alloc_get_freelist(cur->bc_tp, cur->bc_private.a.agbp,
			&rbno)))
		return error;
	if (rbno == NULLAGBLOCK) {
		*stat = 0;
		return 0;
	}
	xfs_trans_agbtree_delta(cur->bc_tp, 1);
	rbp = xfs_btree_get_bufs(cur->bc_mp, cur->bc_tp, cur->bc_private.a.agno,
		rbno, 0);
	/*
	 * Set up the new block as "right".
	 */
	right = XFS_BUF_TO_ALLOC_BLOCK(rbp);
	/*
	 * "Left" is the current (according to the cursor) block.
	 */
	lbp = cur->bc_bufs[level];
	left = XFS_BUF_TO_ALLOC_BLOCK(lbp);
#ifdef DEBUG
	if ((error = xfs_btree_check_sblock(cur, left, level, lbp)))
		return error;
#endif
	/*
	 * Fill in the btree header for the new block.
	 */
	INT_SET(right->bb_magic, ARCH_CONVERT, xfs_magics[cur->bc_btnum]);
	right->bb_level = left->bb_level; /* INT_: direct copy */
	INT_SET(right->bb_numrecs, ARCH_CONVERT, (__uint16_t)(INT_GET(left->bb_numrecs, ARCH_CONVERT) / 2));
	/*
	 * Make sure that if there's an odd number of entries now, that
	 * each new block will have the same number of entries.
	 */
	if ((INT_GET(left->bb_numrecs, ARCH_CONVERT) & 1) &&
	    cur->bc_ptrs[level] <= INT_GET(right->bb_numrecs, ARCH_CONVERT) + 1)
		INT_MOD(right->bb_numrecs, ARCH_CONVERT, +1);
	i = INT_GET(left->bb_numrecs, ARCH_CONVERT) - INT_GET(right->bb_numrecs, ARCH_CONVERT) + 1;
	/*
	 * For non-leaf blocks, copy keys and addresses over to the new block.
	 */
	if (level > 0) {
		xfs_alloc_key_t	*lkp;	/* left btree key pointer */
		xfs_alloc_ptr_t	*lpp;	/* left btree address pointer */
		xfs_alloc_key_t	*rkp;	/* right btree key pointer */
		xfs_alloc_ptr_t	*rpp;	/* right btree address pointer */

		lkp = XFS_ALLOC_KEY_ADDR(left, i, cur);
		lpp = XFS_ALLOC_PTR_ADDR(left, i, cur);
		rkp = XFS_ALLOC_KEY_ADDR(right, 1, cur);
		rpp = XFS_ALLOC_PTR_ADDR(right, 1, cur);
#ifdef DEBUG
		for (i = 0; i < INT_GET(right->bb_numrecs, ARCH_CONVERT); i++) {
			if ((error = xfs_btree_check_sptr(cur, INT_GET(lpp[i], ARCH_CONVERT), level)))