xfs_bmap_btree.c

linux 内核源代码

	xfs_trans_log_inode(cur->bc_tp, ip,
		XFS_ILOG_CORE | XFS_ILOG_FBROOT(cur->bc_private.b.whichfork));
	cur->bc_nlevels--;
	XFS_BMBT_TRACE_CURSOR(cur, EXIT);
	return 0;
}

/*
 * Log key values from the btree block.
 */
STATIC void
xfs_bmbt_log_keys(
	xfs_btree_cur_t	*cur,
	xfs_buf_t	*bp,
	int		kfirst,
	int		klast)
{
	xfs_trans_t	*tp;

	XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
	XFS_BMBT_TRACE_ARGBII(cur, bp, kfirst, klast);
	tp = cur->bc_tp;
	if (bp) {
		xfs_bmbt_block_t	*block;
		int			first;
		xfs_bmbt_key_t		*kp;
		int			last;

		block = XFS_BUF_TO_BMBT_BLOCK(bp);
		kp = XFS_BMAP_KEY_DADDR(block, 1, cur);
		first = (int)((xfs_caddr_t)&kp[kfirst - 1] - (xfs_caddr_t)block);
		last = (int)(((xfs_caddr_t)&kp[klast] - 1) - (xfs_caddr_t)block);
		xfs_trans_log_buf(tp, bp, first, last);
	} else {
		xfs_inode_t		 *ip;

		ip = cur->bc_private.b.ip;
		xfs_trans_log_inode(tp, ip,
			XFS_ILOG_FBROOT(cur->bc_private.b.whichfork));
	}
	XFS_BMBT_TRACE_CURSOR(cur, EXIT);
}

/*
 * Log pointer values from the btree block.
 */
STATIC void
xfs_bmbt_log_ptrs(
	xfs_btree_cur_t	*cur,
	xfs_buf_t	*bp,
	int		pfirst,
	int		plast)
{
	xfs_trans_t	*tp;

	XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
	XFS_BMBT_TRACE_ARGBII(cur, bp, pfirst, plast);
	tp = cur->bc_tp;
	if (bp) {
		xfs_bmbt_block_t	*block;
		int			first;
		int			last;
		xfs_bmbt_ptr_t		*pp;

		block = XFS_BUF_TO_BMBT_BLOCK(bp);
		pp = XFS_BMAP_PTR_DADDR(block, 1, cur);
		first = (int)((xfs_caddr_t)&pp[pfirst - 1] - (xfs_caddr_t)block);
		last = (int)(((xfs_caddr_t)&pp[plast] - 1) - (xfs_caddr_t)block);
		xfs_trans_log_buf(tp, bp, first, last);
	} else {
		xfs_inode_t		*ip;

		ip = cur->bc_private.b.ip;
		xfs_trans_log_inode(tp, ip,
			XFS_ILOG_FBROOT(cur->bc_private.b.whichfork));
	}
	XFS_BMBT_TRACE_CURSOR(cur, EXIT);
}

/*
 * Lookup the record.  The cursor is made to point to it, based on dir.
 */
STATIC int				/* error */
xfs_bmbt_lookup(
	xfs_btree_cur_t		*cur,
	xfs_lookup_t		dir,
	int			*stat)		/* success/failure */
{
	xfs_bmbt_block_t	*block=NULL;
	xfs_buf_t		*bp;
	xfs_daddr_t		d;
	xfs_sfiloff_t		diff;
	int			error;		/* error return value */
	xfs_fsblock_t		fsbno=0;
	int			high;
	int			i;
	int			keyno=0;
	xfs_bmbt_key_t		*kkbase=NULL;
	xfs_bmbt_key_t		*kkp;
	xfs_bmbt_rec_t		*krbase=NULL;
	xfs_bmbt_rec_t		*krp;
	int			level;
	int			low;
	xfs_mount_t		*mp;
	xfs_bmbt_ptr_t		*pp;
	xfs_bmbt_irec_t		*rp;
	xfs_fileoff_t		startoff;
	xfs_trans_t		*tp;

	XFS_STATS_INC(xs_bmbt_lookup);
	XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
	XFS_BMBT_TRACE_ARGI(cur, (int)dir);
	tp = cur->bc_tp;
	mp = cur->bc_mp;
	rp = &cur->bc_rec.b;
	for (level = cur->bc_nlevels - 1, diff = 1; level >= 0; level--) {
		if (level < cur->bc_nlevels - 1) {
			d = XFS_FSB_TO_DADDR(mp, fsbno);
			bp = cur->bc_bufs[level];
			if (bp && XFS_BUF_ADDR(bp) != d)
				bp = NULL;
			if (!bp) {
				if ((error = xfs_btree_read_bufl(mp, tp, fsbno,
						0, &bp, XFS_BMAP_BTREE_REF))) {
					XFS_BMBT_TRACE_CURSOR(cur, ERROR);
					return error;
				}
				xfs_btree_setbuf(cur, level, bp);
				block = XFS_BUF_TO_BMBT_BLOCK(bp);
				if ((error = xfs_btree_check_lblock(cur, block,
						level, bp))) {
					XFS_BMBT_TRACE_CURSOR(cur, ERROR);
					return error;
				}
			} else
				block = XFS_BUF_TO_BMBT_BLOCK(bp);
		} else
			block = xfs_bmbt_get_block(cur, level, &bp);
		if (diff == 0)
			keyno = 1;
		else {
			if (level > 0)
				kkbase = XFS_BMAP_KEY_IADDR(block, 1, cur);
			else
				krbase = XFS_BMAP_REC_IADDR(block, 1, cur);
			low = 1;
			if (!(high = be16_to_cpu(block->bb_numrecs))) {
				ASSERT(level == 0);
				cur->bc_ptrs[0] = dir != XFS_LOOKUP_LE;
				XFS_BMBT_TRACE_CURSOR(cur, EXIT);
				*stat = 0;
				return 0;
			}
			while (low <= high) {
				XFS_STATS_INC(xs_bmbt_compare);
				keyno = (low + high) >> 1;
				if (level > 0) {
					kkp = kkbase + keyno - 1;
					startoff = be64_to_cpu(kkp->br_startoff);
				} else {
					krp = krbase + keyno - 1;
					startoff = xfs_bmbt_disk_get_startoff(krp);
				}
				diff = (xfs_sfiloff_t)
						(startoff - rp->br_startoff);
				if (diff < 0)
					low = keyno + 1;
				else if (diff > 0)
					high = keyno - 1;
				else
					break;
			}
		}
		if (level > 0) {
			if (diff > 0 && --keyno < 1)
				keyno = 1;
			pp = XFS_BMAP_PTR_IADDR(block, keyno, cur);
			fsbno = be64_to_cpu(*pp);
#ifdef DEBUG
			if ((error = xfs_btree_check_lptr(cur, fsbno, level))) {
				XFS_BMBT_TRACE_CURSOR(cur, ERROR);
				return error;
			}
#endif
			cur->bc_ptrs[level] = keyno;
		}
	}
	if (dir != XFS_LOOKUP_LE && diff < 0) {
		keyno++;
		/*
		 * If ge search and we went off the end of the block, but it's
		 * not the last block, we're in the wrong block.
		 */
		if (dir == XFS_LOOKUP_GE && keyno > be16_to_cpu(block->bb_numrecs) &&
		    be64_to_cpu(block->bb_rightsib) != NULLDFSBNO) {
			cur->bc_ptrs[0] = keyno;
			if ((error = xfs_bmbt_increment(cur, 0, &i))) {
				XFS_BMBT_TRACE_CURSOR(cur, ERROR);
				return error;
			}
			XFS_WANT_CORRUPTED_RETURN(i == 1);
			XFS_BMBT_TRACE_CURSOR(cur, EXIT);
			*stat = 1;
			return 0;
		}
	}
	else if (dir == XFS_LOOKUP_LE && diff > 0)
		keyno--;
	cur->bc_ptrs[0] = keyno;
	if (keyno == 0 || keyno > be16_to_cpu(block->bb_numrecs)) {
		XFS_BMBT_TRACE_CURSOR(cur, EXIT);
		*stat = 0;
	} else {
		XFS_BMBT_TRACE_CURSOR(cur, EXIT);
		*stat = ((dir != XFS_LOOKUP_EQ) || (diff == 0));
	}
	return 0;
}

/*
 * Move 1 record left from cur/level if possible.
 * Update cur to reflect the new path.
 */
STATIC int					/* error */
xfs_bmbt_lshift(
	xfs_btree_cur_t		*cur,
	int			level,
	int			*stat)		/* success/failure */
{
	int			error;		/* error return value */
#ifdef DEBUG
	int			i;		/* loop counter */
#endif
	xfs_bmbt_key_t		key;		/* bmap btree key */
	xfs_buf_t		*lbp;		/* left buffer pointer */
	xfs_bmbt_block_t	*left;		/* left btree block */
	xfs_bmbt_key_t		*lkp=NULL;	/* left btree key */
	xfs_bmbt_ptr_t		*lpp;		/* left address pointer */
	int			lrecs;		/* left record count */
	xfs_bmbt_rec_t		*lrp=NULL;	/* left record pointer */
	xfs_mount_t		*mp;		/* file system mount point */
	xfs_buf_t		*rbp;		/* right buffer pointer */
	xfs_bmbt_block_t	*right;		/* right btree block */
	xfs_bmbt_key_t		*rkp=NULL;	/* right btree key */
	xfs_bmbt_ptr_t		*rpp=NULL;	/* right address pointer */
	xfs_bmbt_rec_t		*rrp=NULL;	/* right record pointer */
	int			rrecs;		/* right record count */

	XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
	XFS_BMBT_TRACE_ARGI(cur, level);
	if (level == cur->bc_nlevels - 1) {
		XFS_BMBT_TRACE_CURSOR(cur, EXIT);
		*stat = 0;
		return 0;
	}
	rbp = cur->bc_bufs[level];
	right = XFS_BUF_TO_BMBT_BLOCK(rbp);
#ifdef DEBUG
	if ((error = xfs_btree_check_lblock(cur, right, level, rbp))) {
		XFS_BMBT_TRACE_CURSOR(cur, ERROR);
		return error;
	}
#endif
	if (be64_to_cpu(right->bb_leftsib) == NULLDFSBNO) {
		XFS_BMBT_TRACE_CURSOR(cur, EXIT);
		*stat = 0;
		return 0;
	}
	if (cur->bc_ptrs[level] <= 1) {
		XFS_BMBT_TRACE_CURSOR(cur, EXIT);
		*stat = 0;
		return 0;
	}
	mp = cur->bc_mp;
	if ((error = xfs_btree_read_bufl(mp, cur->bc_tp, be64_to_cpu(right->bb_leftsib), 0,
			&lbp, XFS_BMAP_BTREE_REF))) {
		XFS_BMBT_TRACE_CURSOR(cur, ERROR);
		return error;
	}
	left = XFS_BUF_TO_BMBT_BLOCK(lbp);
	if ((error = xfs_btree_check_lblock(cur, left, level, lbp))) {
		XFS_BMBT_TRACE_CURSOR(cur, ERROR);
		return error;
	}
	if (be16_to_cpu(left->bb_numrecs) == XFS_BMAP_BLOCK_IMAXRECS(level, cur)) {
		XFS_BMBT_TRACE_CURSOR(cur, EXIT);
		*stat = 0;
		return 0;
	}
	lrecs = be16_to_cpu(left->bb_numrecs) + 1;
	if (level > 0) {
		lkp = XFS_BMAP_KEY_IADDR(left, lrecs, cur);
		rkp = XFS_BMAP_KEY_IADDR(right, 1, cur);
		*lkp = *rkp;
		xfs_bmbt_log_keys(cur, lbp, lrecs, lrecs);
		lpp = XFS_BMAP_PTR_IADDR(left, lrecs, cur);
		rpp = XFS_BMAP_PTR_IADDR(right, 1, cur);
#ifdef DEBUG
		if ((error = xfs_btree_check_lptr_disk(cur, *rpp, level))) {
			XFS_BMBT_TRACE_CURSOR(cur, ERROR);
			return error;
		}
#endif
		*lpp = *rpp;
		xfs_bmbt_log_ptrs(cur, lbp, lrecs, lrecs);
	} else {
		lrp = XFS_BMAP_REC_IADDR(left, lrecs, cur);
		rrp = XFS_BMAP_REC_IADDR(right, 1, cur);
		*lrp = *rrp;
		xfs_bmbt_log_recs(cur, lbp, lrecs, lrecs);
	}
	left->bb_numrecs = cpu_to_be16(lrecs);
	xfs_bmbt_log_block(cur, lbp, XFS_BB_NUMRECS);
#ifdef DEBUG
	if (level > 0)
		xfs_btree_check_key(XFS_BTNUM_BMAP, lkp - 1, lkp);
	else
		xfs_btree_check_rec(XFS_BTNUM_BMAP, lrp - 1, lrp);
#endif
	rrecs = be16_to_cpu(right->bb_numrecs) - 1;
	right->bb_numrecs = cpu_to_be16(rrecs);
	xfs_bmbt_log_block(cur, rbp, XFS_BB_NUMRECS);
	if (level > 0) {
#ifdef DEBUG
		for (i = 0; i < rrecs; i++) {
			if ((error = xfs_btree_check_lptr_disk(cur, rpp[i + 1],
					level))) {
				XFS_BMBT_TRACE_CURSOR(cur, ERROR);
				return error;
			}
		}
#endif
		memmove(rkp, rkp + 1, rrecs * sizeof(*rkp));
		memmove(rpp, rpp + 1, rrecs * sizeof(*rpp));
		xfs_bmbt_log_keys(cur, rbp, 1, rrecs);
		xfs_bmbt_log_ptrs(cur, rbp, 1, rrecs);
	} else {
		memmove(rrp, rrp + 1, rrecs * sizeof(*rrp));
		xfs_bmbt_log_recs(cur, rbp, 1, rrecs);
		key.br_startoff = cpu_to_be64(xfs_bmbt_disk_get_startoff(rrp));
		rkp = &key;
	}
	if ((error = xfs_bmbt_updkey(cur, rkp, level + 1))) {
		XFS_BMBT_TRACE_CURSOR(cur, ERROR);
		return error;
	}
	cur->bc_ptrs[level]--;
	XFS_BMBT_TRACE_CURSOR(cur, EXIT);
	*stat = 1;
	return 0;
}

/*
 * Move 1 record right from cur/level if possible.
 * Update cur to reflect the new path.
 */
STATIC int					/* error */
xfs_bmbt_rshift(
	xfs_btree_cur_t		*cur,
	int			level,
	int			*stat)		/* success/failure */
{
	int			error;		/* error return value */
	int			i;		/* loop counter */
	xfs_bmbt_key_t		key;		/* bmap btree key */
	xfs_buf_t		*lbp;		/* left buffer pointer */
	xfs_bmbt_block_t	*left;		/* left btree block */
	xfs_bmbt_key_t		*lkp;		/* left btree key */
	xfs_bmbt_ptr_t		*lpp;		/* left address pointer */
	xfs_bmbt_rec_t		*lrp;		/* left record pointer */
	xfs_mount_t		*mp;		/* file system mount point */
	xfs_buf_t		*rbp;		/* right buffer pointer */
	xfs_bmbt_block_t	*right;		/* right btree block */
	xfs_bmbt_key_t		*rkp;		/* right btree key */
	xfs_bmbt_ptr_t		*rpp;		/* right address pointer */
	xfs_bmbt_rec_t		*rrp=NULL;	/* right record pointer */
	struct xfs_btree_cur	*tcur;		/* temporary btree cursor */

	XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
	XFS_BMBT_TRACE_ARGI(cur, level);
	if (level == cur->bc_nlevels - 1) {
		XFS_BMBT_TRACE_CURSOR(cur, EXIT);
		*stat = 0;
		return 0;
	}
	lbp = cur->bc_bufs[level];
	left = XFS_BUF_TO_BMBT_BLOCK(lbp);
#ifdef DEBUG
	if ((error = xfs_btree_check_lblock(cur, left, level, lbp))) {
		XFS_BMBT_TRACE_CURSOR(cur, ERROR);
		return error;
	}
#endif
	if (be64_to_cpu(left->bb_rightsib) == NULLDFSBNO) {
		XFS_BMBT_TRACE_CURSOR(cur, EXIT);
		*stat = 0;
		return 0;
	}
	if (cur->bc_ptrs[level] >= be16_to_cpu(left->bb_numrecs)) {
		XFS_BMBT_TRACE_CURSOR(cur, EXIT);
		*stat = 0;
		return 0;
	}
	mp = cur->bc_mp;
	if ((error = xfs_btree_read_bufl(mp, cur->bc_tp, be64_to_cpu(left->bb_rightsib), 0,
			&rbp, XFS_BMAP_BTREE_REF))) {
		XFS_BMBT_TRACE_CURSOR(cur, ERROR);
		return error;
	}
	right = XFS_BUF_TO_BMBT_BLOCK(rbp);
	if ((error = xfs_btree_check_lblock(cur, right, level, rbp))) {
		XFS_BMBT_TRACE_CURSOR(cur, ERROR);
		return error;
	}
	if (be16_to_cpu(right->bb_numrecs) == XFS_BMAP_BLOCK_IMAXRECS(level, cur)) {
		XFS_BMBT_TRACE_CURSOR(cur, EXIT);
		*stat = 0;
		return 0;
	}
	if (level > 0) {
		lkp = XFS_BMAP_KEY_IADDR(left, be16_to_cpu(left->bb_numrecs), cur);
		lpp = XFS_BMAP_PTR_IADDR(left, be16_to_cpu(left->bb_numrecs), cur);
		rkp = XFS_BMAP_KEY_IADDR(right, 1, cur);
		rpp = XFS_BMAP_PTR_IADDR(right, 1, cur);
#ifdef DEBUG
		for (i = be16_to_cpu(right->bb_numrecs) - 1; i >= 0; i--) {
			if ((error = xfs_btree_check_lptr_disk(cur, rpp[i], level))) {
				XFS_BMBT_TRACE_CURSOR(cur, ERROR);
				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_lptr_disk(cur, *lpp, level))) {
			XFS_BMBT_TRACE_CURSOR(cur, ERROR);
			return error;
		}
#endif
		*rkp = *lkp;
		*rpp = *lpp;
		xfs_bmbt_log_keys(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
		xfs_bmbt_log_ptrs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
	} else {
		lrp = XFS_BMAP_REC_IADDR(left, be16_to_cpu(left->bb_numrecs), cur);
		rrp = XFS_BMAP_REC_IADDR(right, 1, cur);
		memmove(rrp + 1, rrp, be16_to_cpu(right->bb_numrecs) * sizeof(*rrp));
		*rrp = *lrp;
		xfs_bmbt_log_recs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
		key.br_startoff = cpu_to_be64(xfs_bmbt_disk_get_startoff(rrp));
		rkp = &key;
	}
	be16_add(&left->bb_numrecs, -1);
	xfs_bmbt_log_block(cur, lbp, XFS_BB_NUMRECS);
	be16_add(&right->bb_numrecs, 1);
#ifdef DEBUG
	if (level > 0)
		xfs_btree_check_key(XFS_BTNUM_BMAP, rkp, rkp + 1);
	else
		xfs_btree_check_rec(XFS_BTNUM_BMAP, rrp, rrp + 1);
#endif
	xfs_bmbt_log_block(cur, rbp, XFS_BB_NUMRECS);
	if ((error = xfs_btree_dup_cursor(cur, &tcur))) {
		XFS_BMBT_TRACE_CURSOR(cur, ERROR);
		return error;
	}
	i = xfs_btree_lastrec(tcur, level);
	XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
	if ((error = xfs_bmbt_increment(tcur, level, &i))) {
		XFS_BMBT_TRACE_CURSOR(tcur, ERROR);
		goto error1;
	}
	XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
	if ((error = xfs_bmbt_updkey(tcur, rkp, level + 1))) {