xfs_alloc_btree.c

linux 内核源代码

	if (error)
		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);
		agf->agf_roots[cur->bc_btnum] = cpu_to_be32(nbno);
		be32_add(&agf->agf_levels[cur->bc_btnum], 1);
		seqno = be32_to_cpu(agf->agf_seqno);
		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 (be32_to_cpu(left->bb_rightsib) != NULLAGBLOCK) {
		/*
		 * Our block is left, pick up the right block.
		 */
		lbno = XFS_DADDR_TO_AGBNO(mp, XFS_BUF_ADDR(lbp));
		rbno = be32_to_cpu(left->bb_rightsib);
		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 = be32_to_cpu(right->bb_leftsib);
		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.
	 */
	new->bb_magic = cpu_to_be32(xfs_magics[cur->bc_btnum]);
	new->bb_level = cpu_to_be16(cur->bc_nlevels);
	new->bb_numrecs = cpu_to_be16(2);
	new->bb_leftsib = cpu_to_be32(NULLAGBLOCK);
	new->bb_rightsib = cpu_to_be32(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 (be16_to_cpu(left->bb_level) > 0) {
			kp[0] = *XFS_ALLOC_KEY_ADDR(left, 1, cur);
			kp[1] = *XFS_ALLOC_KEY_ADDR(right, 1, cur);
		} else {
			xfs_alloc_rec_t	*rp;	/* btree record pointer */

			rp = XFS_ALLOC_REC_ADDR(left, 1, cur);
			kp[0].ar_startblock = rp->ar_startblock;
			kp[0].ar_blockcount = rp->ar_blockcount;
			rp = XFS_ALLOC_REC_ADDR(right, 1, cur);
			kp[1].ar_startblock = rp->ar_startblock;
			kp[1].ar_blockcount = rp->ar_blockcount;
		}
	}
	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);
		pp[0] = cpu_to_be32(lbno);
		pp[1] = cpu_to_be32(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 (be32_to_cpu(left->bb_rightsib) == 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] >= be16_to_cpu(left->bb_numrecs)) {
		*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, be32_to_cpu(left->bb_rightsib),
			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 (be16_to_cpu(right->bb_numrecs) == 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, be16_to_cpu(left->bb_numrecs), cur);
		lpp = XFS_ALLOC_PTR_ADDR(left, be16_to_cpu(left->bb_numrecs), cur);
		rkp = XFS_ALLOC_KEY_ADDR(right, 1, cur);
		rpp = XFS_ALLOC_PTR_ADDR(right, 1, cur);
#ifdef DEBUG
		for (i = be16_to_cpu(right->bb_numrecs) - 1; i >= 0; i--) {
			if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(rpp[i]), level)))
				return error;
		}
#endif
		memmove(rkp + 1, rkp, be16_to_cpu(right->bb_numrecs) * sizeof(*rkp));
		memmove(rpp + 1, rpp, be16_to_cpu(right->bb_numrecs) * sizeof(*rpp));
#ifdef DEBUG
		if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(*lpp), level)))
			return error;
#endif
		*rkp = *lkp;
		*rpp = *lpp;
		xfs_alloc_log_keys(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
		xfs_alloc_log_ptrs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 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, be16_to_cpu(left->bb_numrecs), cur);
		rrp = XFS_ALLOC_REC_ADDR(right, 1, cur);
		memmove(rrp + 1, rrp, be16_to_cpu(right->bb_numrecs) * sizeof(*rrp));
		*rrp = *lrp;
		xfs_alloc_log_recs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
		key.ar_startblock = rrp->ar_startblock;
		key.ar_blockcount = rrp->ar_blockcount;
		rkp = &key;
		xfs_btree_check_rec(cur->bc_btnum, rrp, rrp + 1);
	}
	/*
	 * Decrement and log left's numrecs, bump and log right's numrecs.
	 */
	be16_add(&left->bb_numrecs, -1);
	xfs_alloc_log_block(cur->bc_tp, lbp, XFS_BB_NUMRECS);
	be16_add(&right->bb_numrecs, 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.
	 */
	error = xfs_alloc_get_freelist(cur->bc_tp,
					 cur->bc_private.a.agbp, &rbno, 1);
	if (error)
		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.
	 */
	right->bb_magic = cpu_to_be32(xfs_magics[cur->bc_btnum]);
	right->bb_level = left->bb_level;
	right->bb_numrecs = cpu_to_be16(be16_to_cpu(left->bb_numrecs) / 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 ((be16_to_cpu(left->bb_numrecs) & 1) &&
	    cur->bc_ptrs[level] <= be16_to_cpu(right->bb_numrecs) + 1)
		be16_add(&right->bb_numrecs, 1);
	i = be16_to_cpu(left->bb_numrecs) - be16_to_cpu(right->bb_numrecs) + 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 < be16_to_cpu(right->bb_numrecs); i++) {
			if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(lpp[i]), level)))
				return error;
		}
#endif
		memcpy(rkp, lkp, be16_to_cpu(right->bb_numrecs) * sizeof(*rkp));
		memcpy(rpp, lpp, be16_to_cpu(right->bb_numrecs) * sizeof(*rpp));
		xfs_alloc_log_keys(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
		xfs_alloc_log_ptrs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
		*keyp = *rkp;
	}
	/*
	 * For leaf blocks, copy records over to the new block.
	 */
	else {
		xfs_alloc_rec_t	*lrp;	/* left btree record pointer */
		xfs_alloc_rec_t	*rrp;	/* right btree record pointer */

		lrp = XFS_ALLOC_REC_ADDR(left, i, cur);
		rrp = XFS_ALLOC_REC_ADDR(right, 1, cur);
		memcpy(rrp, lrp, be16_to_cpu(right->bb_numrecs) * sizeof(*rrp));
		xfs_alloc_log_recs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
		keyp->ar_startblock = rrp->ar_startblock;
		keyp->ar_blockcount = rrp->ar_blockcount;
	}
	/*
	 * Find the left block number by looking in the buffer.
	 * Adjust numrecs, sibling pointers.
	 */
	lbno = XFS_DADDR_TO_AGBNO(cur->bc_mp, XFS_BUF_ADDR(lbp));
	be16_add(&left->bb_numrecs, -(be16_to_cpu(right->bb_numrecs)));
	right->bb_rightsib = left->bb_rightsib;
	left->bb_rightsib = cpu_to_be32(rbno);
	right->bb_leftsib = cpu_to_be32(lbno);
	xfs_alloc_log_block(cur->bc_tp, rbp, XFS_BB_ALL_BITS);
	xfs_alloc_log_block(cur->bc_tp, lbp, XFS_BB_NUMRECS | XFS_BB_RIGHTSIB);
	/*
	 * If there's a block to the new block's right, make that block
	 * point back to right instead of to left.
	 */
	if (be32_to_cpu(right->bb_rightsib) != NULLAGBLOCK) {
		xfs_alloc_block_t	*rrblock;	/* rr btree block */
		xfs_buf_t		*rrbp;		/* buffer for rrblock */

		if ((error = xfs_btree_read_bufs(cur->bc_mp, cur->bc_tp,
				cur->bc_private.a.agno, be32_to_cpu(right->bb_rightsib), 0,
				&rrbp, XFS_ALLOC_BTREE_REF)))
			return error;
		rrblock = XFS_BUF_TO_ALLOC_BLOCK(rrbp);
		if ((error = xfs_btree_check_sblock(cur, rrblock, level, rrbp)))
			return error;
		rrblock->bb_leftsib = cpu_to_be32(rbno);
		xfs_alloc_log_block(cur->bc_tp, rrbp, XFS_BB_LEFTSIB);
	}
	/*
	 * If the cursor is really in the right block, move it there.
	 * If it's just pointing past the last entry in left, then we'll
	 * insert there, so don't change anything in that case.
	 */
	if (cur->bc_ptrs[level] > be16_to_cpu(left->bb_numrecs) + 1) {
		xfs_btree_setbuf(cur, level, rbp);
		cur->bc_ptrs[level] -= be16_to_cpu(left->bb_numrecs);
	}
	/*
	 * If there are more levels, we'll need another cursor which refers to
	 * the right block, no matter where this cursor was.
	 */
	if (level + 1 < cur->bc_nlevels) {
		if ((error = xfs_btree_dup_cursor(cur, curp)))
			return error;
		(*curp)->bc_ptrs[level + 1]++;
	}
	*bnop = rbno;
	*stat = 1;
	return 0;
}

/*
 * Update keys at all levels from here to the root along the cursor's path.
 */
STATIC int				/* error */
xfs_alloc_updkey(
	xfs_btree_cur_t		*cur,	/* btree cursor */
	xfs_alloc_key_t		*keyp,	/* new key value to update to */
	int			level)	/* starting level for update */
{
	int			ptr;	/* index of key in block */

	/*
	 * Go up the tree from this level toward the root.
	 * At each level, update the key value to the value input.
	 * Stop when we reach a level where the cursor isn't pointing
	 * at the first entry in the block.
	 */
	for (ptr = 1; ptr == 1 && level < cur->bc_nlevels; level++) {
		xfs_alloc_block_t	*block;	/* btree block */
		xfs_buf_t		*bp;	/* buffer for block */
#ifdef DEBUG
		int			error;	/* error return value */
#endif
		xfs_alloc_key_t		*kp;	/* ptr to btree block keys */

		bp = cur->bc_bufs[level];
		block = XFS_BUF_TO_ALLOC_BLOCK(bp);
#ifdef DEBUG
		if ((error = xfs_btree_check_sblock(cur, block, level, bp)))
			return error;