xfs_ialloc_btree.c

linux 内核源代码

STATIC int				/* error */
xfs_inobt_lshift(
	xfs_btree_cur_t		*cur,	/* btree cursor */
	int			level,	/* level to shift record on */
	int			*stat)	/* success/failure */
{
	int			error;	/* error return value */
#ifdef DEBUG
	int			i;	/* loop index */
#endif
	xfs_inobt_key_t		key;	/* key value for leaf level upward */
	xfs_buf_t		*lbp;	/* buffer for left neighbor block */
	xfs_inobt_block_t	*left;	/* left neighbor btree block */
	xfs_inobt_key_t		*lkp=NULL;	/* key pointer for left block */
	xfs_inobt_ptr_t		*lpp;	/* address pointer for left block */
	xfs_inobt_rec_t		*lrp=NULL;	/* record pointer for left block */
	int			nrec;	/* new number of left block entries */
	xfs_buf_t		*rbp;	/* buffer for right (current) block */
	xfs_inobt_block_t	*right;	/* right (current) btree block */
	xfs_inobt_key_t		*rkp=NULL;	/* key pointer for right block */
	xfs_inobt_ptr_t		*rpp=NULL;	/* address pointer for right block */
	xfs_inobt_rec_t		*rrp=NULL;	/* record pointer for right block */

	/*
	 * Set up variables for this block as "right".
	 */
	rbp = cur->bc_bufs[level];
	right = XFS_BUF_TO_INOBT_BLOCK(rbp);
#ifdef DEBUG
	if ((error = xfs_btree_check_sblock(cur, right, level, rbp)))
		return error;
#endif
	/*
	 * If we've got no left sibling then we can't shift an entry left.
	 */
	if (be32_to_cpu(right->bb_leftsib) == 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] <= 1) {
		*stat = 0;
		return 0;
	}
	/*
	 * Set up the left neighbor as "left".
	 */
	if ((error = xfs_btree_read_bufs(cur->bc_mp, cur->bc_tp,
			cur->bc_private.i.agno, be32_to_cpu(right->bb_leftsib),
			0, &lbp, XFS_INO_BTREE_REF)))
		return error;
	left = XFS_BUF_TO_INOBT_BLOCK(lbp);
	if ((error = xfs_btree_check_sblock(cur, left, level, lbp)))
		return error;
	/*
	 * If it's full, it can't take another entry.
	 */
	if (be16_to_cpu(left->bb_numrecs) == XFS_INOBT_BLOCK_MAXRECS(level, cur)) {
		*stat = 0;
		return 0;
	}
	nrec = be16_to_cpu(left->bb_numrecs) + 1;
	/*
	 * If non-leaf, copy a key and a ptr to the left block.
	 */
	if (level > 0) {
		lkp = XFS_INOBT_KEY_ADDR(left, nrec, cur);
		rkp = XFS_INOBT_KEY_ADDR(right, 1, cur);
		*lkp = *rkp;
		xfs_inobt_log_keys(cur, lbp, nrec, nrec);
		lpp = XFS_INOBT_PTR_ADDR(left, nrec, cur);
		rpp = XFS_INOBT_PTR_ADDR(right, 1, cur);
#ifdef DEBUG
		if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(*rpp), level)))
			return error;
#endif
		*lpp = *rpp;
		xfs_inobt_log_ptrs(cur, lbp, nrec, nrec);
	}
	/*
	 * If leaf, copy a record to the left block.
	 */
	else {
		lrp = XFS_INOBT_REC_ADDR(left, nrec, cur);
		rrp = XFS_INOBT_REC_ADDR(right, 1, cur);
		*lrp = *rrp;
		xfs_inobt_log_recs(cur, lbp, nrec, nrec);
	}
	/*
	 * Bump and log left's numrecs, decrement and log right's numrecs.
	 */
	be16_add(&left->bb_numrecs, 1);
	xfs_inobt_log_block(cur->bc_tp, lbp, XFS_BB_NUMRECS);
#ifdef DEBUG
	if (level > 0)
		xfs_btree_check_key(cur->bc_btnum, lkp - 1, lkp);
	else
		xfs_btree_check_rec(cur->bc_btnum, lrp - 1, lrp);
#endif
	be16_add(&right->bb_numrecs, -1);
	xfs_inobt_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 < be16_to_cpu(right->bb_numrecs); i++) {
			if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(rpp[i + 1]),
					level)))
				return error;
		}
#endif
		memmove(rkp, rkp + 1, be16_to_cpu(right->bb_numrecs) * sizeof(*rkp));
		memmove(rpp, rpp + 1, be16_to_cpu(right->bb_numrecs) * sizeof(*rpp));
		xfs_inobt_log_keys(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
		xfs_inobt_log_ptrs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
	} else {
		memmove(rrp, rrp + 1, be16_to_cpu(right->bb_numrecs) * sizeof(*rrp));
		xfs_inobt_log_recs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
		key.ir_startino = rrp->ir_startino;
		rkp = &key;
	}
	/*
	 * Update the parent key values of right.
	 */
	if ((error = xfs_inobt_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_inobt_newroot(
	xfs_btree_cur_t		*cur,	/* btree cursor */
	int			*stat)	/* success/failure */
{
	xfs_agi_t		*agi;	/* a.g. inode header */
	xfs_alloc_arg_t		args;	/* allocation argument structure */
	xfs_inobt_block_t	*block;	/* one half of the old root block */
	xfs_buf_t		*bp;	/* buffer containing block */
	int			error;	/* error return value */
	xfs_inobt_key_t		*kp;	/* btree key pointer */
	xfs_agblock_t		lbno;	/* left block number */
	xfs_buf_t		*lbp;	/* left buffer pointer */
	xfs_inobt_block_t	*left;	/* left btree block */
	xfs_buf_t		*nbp;	/* new (root) buffer */
	xfs_inobt_block_t	*new;	/* new (root) btree block */
	int			nptr;	/* new value for key index, 1 or 2 */
	xfs_inobt_ptr_t		*pp;	/* btree address pointer */
	xfs_agblock_t		rbno;	/* right block number */
	xfs_buf_t		*rbp;	/* right buffer pointer */
	xfs_inobt_block_t	*right;	/* right btree block */
	xfs_inobt_rec_t		*rp;	/* btree record pointer */

	ASSERT(cur->bc_nlevels < XFS_IN_MAXLEVELS(cur->bc_mp));

	/*
	 * Get a block & a buffer.
	 */
	agi = XFS_BUF_TO_AGI(cur->bc_private.i.agbp);
	args.tp = cur->bc_tp;
	args.mp = cur->bc_mp;
	args.fsbno = XFS_AGB_TO_FSB(args.mp, cur->bc_private.i.agno,
		be32_to_cpu(agi->agi_root));
	args.mod = args.minleft = args.alignment = args.total = args.wasdel =
		args.isfl = args.userdata = args.minalignslop = 0;
	args.minlen = args.maxlen = args.prod = 1;
	args.type = XFS_ALLOCTYPE_NEAR_BNO;
	if ((error = xfs_alloc_vextent(&args)))
		return error;
	/*
	 * None available, we fail.
	 */
	if (args.fsbno == NULLFSBLOCK) {
		*stat = 0;
		return 0;
	}
	ASSERT(args.len == 1);
	nbp = xfs_btree_get_bufs(args.mp, args.tp, args.agno, args.agbno, 0);
	new = XFS_BUF_TO_INOBT_BLOCK(nbp);
	/*
	 * Set the root data in the a.g. inode structure.
	 */
	agi->agi_root = cpu_to_be32(args.agbno);
	be32_add(&agi->agi_level, 1);
	xfs_ialloc_log_agi(args.tp, cur->bc_private.i.agbp,
		XFS_AGI_ROOT | XFS_AGI_LEVEL);
	/*
	 * 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.
	 */
	bp = cur->bc_bufs[cur->bc_nlevels - 1];
	block = XFS_BUF_TO_INOBT_BLOCK(bp);
#ifdef DEBUG
	if ((error = xfs_btree_check_sblock(cur, block, cur->bc_nlevels - 1, bp)))
		return error;
#endif
	if (be32_to_cpu(block->bb_rightsib) != NULLAGBLOCK) {
		/*
		 * Our block is left, pick up the right block.
		 */
		lbp = bp;
		lbno = XFS_DADDR_TO_AGBNO(args.mp, XFS_BUF_ADDR(lbp));
		left = block;
		rbno = be32_to_cpu(left->bb_rightsib);
		if ((error = xfs_btree_read_bufs(args.mp, args.tp, args.agno,
				rbno, 0, &rbp, XFS_INO_BTREE_REF)))
			return error;
		bp = rbp;
		right = XFS_BUF_TO_INOBT_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 = bp;
		rbno = XFS_DADDR_TO_AGBNO(args.mp, XFS_BUF_ADDR(rbp));
		right = block;
		lbno = be32_to_cpu(right->bb_leftsib);
		if ((error = xfs_btree_read_bufs(args.mp, args.tp, args.agno,
				lbno, 0, &lbp, XFS_INO_BTREE_REF)))
			return error;
		bp = lbp;
		left = XFS_BUF_TO_INOBT_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_inobt_log_block(args.tp, nbp, XFS_BB_ALL_BITS);
	ASSERT(lbno != NULLAGBLOCK && rbno != NULLAGBLOCK);
	/*
	 * Fill in the key data in the new root.
	 */
	kp = XFS_INOBT_KEY_ADDR(new, 1, cur);
	if (be16_to_cpu(left->bb_level) > 0) {
		kp[0] = *XFS_INOBT_KEY_ADDR(left, 1, cur);
		kp[1] = *XFS_INOBT_KEY_ADDR(right, 1, cur);
	} else {
		rp = XFS_INOBT_REC_ADDR(left, 1, cur);
		kp[0].ir_startino = rp->ir_startino;
		rp = XFS_INOBT_REC_ADDR(right, 1, cur);
		kp[1].ir_startino = rp->ir_startino;
	}
	xfs_inobt_log_keys(cur, nbp, 1, 2);
	/*
	 * Fill in the pointer data in the new root.
	 */
	pp = XFS_INOBT_PTR_ADDR(new, 1, cur);
	pp[0] = cpu_to_be32(lbno);
	pp[1] = cpu_to_be32(rbno);
	xfs_inobt_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_inobt_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_inobt_key_t		key;	/* key value for leaf level upward */
	xfs_buf_t		*lbp;	/* buffer for left (current) block */
	xfs_inobt_block_t	*left;	/* left (current) btree block */
	xfs_inobt_key_t		*lkp;	/* key pointer for left block */
	xfs_inobt_ptr_t		*lpp;	/* address pointer for left block */
	xfs_inobt_rec_t		*lrp;	/* record pointer for left block */
	xfs_buf_t		*rbp;	/* buffer for right neighbor block */
	xfs_inobt_block_t	*right;	/* right neighbor btree block */
	xfs_inobt_key_t		*rkp;	/* key pointer for right block */
	xfs_inobt_ptr_t		*rpp;	/* address pointer for right block */
	xfs_inobt_rec_t		*rrp=NULL;	/* record 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_INOBT_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.i.agno, be32_to_cpu(left->bb_rightsib),
			0, &rbp, XFS_INO_BTREE_REF)))
		return error;
	right = XFS_BUF_TO_INOBT_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_INOBT_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) {
		lkp = XFS_INOBT_KEY_ADDR(left, be16_to_cpu(left->bb_numrecs), cur);
		lpp = XFS_INOBT_PTR_ADDR(left, be16_to_cpu(left->bb_numrecs), cur);
		rkp = XFS_INOBT_KEY_ADDR(right, 1, cur);
		rpp = XFS_INOBT_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_inobt_log_keys(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
		xfs_inobt_log_ptrs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
	} else {
		lrp = XFS_INOBT_REC_ADDR(left, be16_to_cpu(left->bb_numrecs), cur);
		rrp = XFS_INOBT_REC_ADDR(right, 1, cur);
		memmove(rrp + 1, rrp, be16_to_cpu(right->bb_numrecs) * sizeof(*rrp));
		*rrp = *lrp;
		xfs_inobt_log_recs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
		key.ir_startino = rrp->ir_startino;
		rkp = &key;
	}
	/*
	 * Decrement and log left's numrecs, bump and log right's numrecs.
	 */
	be16_add(&left->bb_numrecs, -1);
	xfs_inobt_log_block(cur->bc_tp, lbp, XFS_BB_NUMRECS);
	be16_add(&right->bb_numrecs, 1);
#ifdef DEBUG
	if (level > 0)
		xfs_btree_check_key(cur->bc_btnum, rkp, rkp + 1);
	else
		xfs_btree_check_rec(cur->bc_btnum, rrp, rrp + 1);
#endif
	xfs_inobt_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;
	xfs_btree_lastrec(tcur, level);
	if ((error = xfs_inobt_increment(tcur, level, &i)) ||
	    (error = xfs_inobt_updkey(tcur, rkp, level + 1))) {
		xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
		return error;
	}
	xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
	*stat = 1;
	return 0;
}

/*
 * Split cur/level block in half.
 * Return new block number and its first record (to be inserted into parent).
 */
STATIC int				/* error */
xfs_inobt_split(
	xfs_btree_cur_t		*cur,	/* btree cursor */
	int			level,	/* level to split */
	xfs_agblock_t		*bnop,	/* output: block number allocated */
	xfs_inobt_key_t		*keyp,	/* output: first key of new block */
	xfs_btree_cur_t		**curp,	/* output: new cursor */
	int			*stat)	/* success/failure */
{
	xfs_alloc_arg_t		args;	/* allocation argument structure */
	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_inobt_block_t	*left;	/* left (current) btree block */
	xfs_inobt_key_t		*lkp;	/* left btree key pointer */
	xfs_inobt_ptr_t		*lpp;	/* left btree address pointer */
	xfs_inobt_rec_t		*lrp;	/* left btree record pointer */
	xfs_buf_t		*rbp;	/* buffer for right block */
	xfs_inobt_block_t	*right;	/* right (new) btree block */
	xfs_inobt_key_t		*rkp;	/* right btree key pointer */
	xfs_inobt_ptr_t		*rpp;	/* right btree address pointer */
	xfs_inobt_rec_t		*rrp;	/* right btree record pointer */

	/*
	 * Set up left block (current one).
	 */
	lbp = cur->bc_bufs[level];
	args.tp = cur->bc_tp;
	args.mp = cur->bc_mp;
	lbno = XFS_DADDR_TO_AGBNO(args.mp, XFS_BUF_ADDR(lbp));
	/*
	 * Allocate the new block.
	 * If we can't do it, we're toast.  Give up.
	 */
	args.fsbno = XFS_AGB_TO_FSB(args.mp, cur->bc_private.i.agno, lbno);
	args.mod = args.minleft = args.alignment = args.total = args.wasdel =
		args.isfl = args.userdata = args.minalignslop = 0;
	args.minlen = args.maxlen = args.prod = 1;
	args.type = XFS_ALLOCTYPE_NEAR_BNO;
	if ((error = xfs_alloc_vextent(&args)))
		return error;
	if (args.fsbno == NULLFSBLOCK) {
		*stat = 0;
		return 0;
	}
	ASSERT(args.len == 1);
	rbp = xfs_btree_get_bufs(args.mp, args.tp, args.agno, args.agbno, 0);
	/*
	 * Set up the new block as "right".
	 */
	right = XFS_BUF_TO_INOBT_BLOCK(rbp);
	/*
	 * "Left" is the current (according to the cursor) block.
	 */
	left = XFS_BUF_TO_INOBT_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) {
		lkp = XFS_INOBT_KEY_ADDR(left, i, cur);
		lpp = XFS_INOBT_PTR_ADDR(left, i, cur);
		rkp = XFS_INOBT_KEY_ADDR(right, 1, cur);
		rpp = XFS_INOBT_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_inobt_log_keys(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
		xfs_inobt_log_ptrs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
		*keyp = *rkp;
	}
	/*
	 * For leaf blocks, copy records over to the new block.
	 */
	else {
		lrp = XFS_INOBT_REC_ADDR(left, i, cur);
		rrp = XFS_INOBT_REC_ADDR(right, 1, cur);
		memcpy(rrp, lrp, be16_to_cpu(right->bb_numrecs) * sizeof(*rrp));