xfs_bmap_btree.c

linux 内核源代码

		XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
		i = xfs_btree_lastrec(tcur, level);
		XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
		rbp = tcur->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);
			goto error0;
		}
#endif
		bno = be64_to_cpu(right->bb_leftsib);
		if (be16_to_cpu(right->bb_numrecs) - 1 >=
		    XFS_BMAP_BLOCK_IMINRECS(level, cur)) {
			if ((error = xfs_bmbt_lshift(tcur, level, &i))) {
				XFS_BMBT_TRACE_CURSOR(cur, ERROR);
				goto error0;
			}
			if (i) {
				ASSERT(be16_to_cpu(block->bb_numrecs) >=
				       XFS_BMAP_BLOCK_IMINRECS(level, tcur));
				xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
				tcur = NULL;
				if (level > 0) {
					if ((error = xfs_bmbt_decrement(cur,
							level, &i))) {
						XFS_BMBT_TRACE_CURSOR(cur,
							ERROR);
						goto error0;
					}
				}
				XFS_BMBT_TRACE_CURSOR(cur, EXIT);
				*stat = 1;
				return 0;
			}
		}
		rrecs = be16_to_cpu(right->bb_numrecs);
		if (lbno != NULLFSBLOCK) {
			i = xfs_btree_firstrec(tcur, level);
			XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
			if ((error = xfs_bmbt_decrement(tcur, level, &i))) {
				XFS_BMBT_TRACE_CURSOR(cur, ERROR);
				goto error0;
			}
			XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
		}
	}
	if (lbno != NULLFSBLOCK) {
		i = xfs_btree_firstrec(tcur, level);
		XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
		/*
		 * decrement to last in block
		 */
		if ((error = xfs_bmbt_decrement(tcur, level, &i))) {
			XFS_BMBT_TRACE_CURSOR(cur, ERROR);
			goto error0;
		}
		i = xfs_btree_firstrec(tcur, level);
		XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
		lbp = tcur->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);
			goto error0;
		}
#endif
		bno = be64_to_cpu(left->bb_rightsib);
		if (be16_to_cpu(left->bb_numrecs) - 1 >=
		    XFS_BMAP_BLOCK_IMINRECS(level, cur)) {
			if ((error = xfs_bmbt_rshift(tcur, level, &i))) {
				XFS_BMBT_TRACE_CURSOR(cur, ERROR);
				goto error0;
			}
			if (i) {
				ASSERT(be16_to_cpu(block->bb_numrecs) >=
				       XFS_BMAP_BLOCK_IMINRECS(level, tcur));
				xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
				tcur = NULL;
				if (level == 0)
					cur->bc_ptrs[0]++;
				XFS_BMBT_TRACE_CURSOR(cur, EXIT);
				*stat = 1;
				return 0;
			}
		}
		lrecs = be16_to_cpu(left->bb_numrecs);
	}
	xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
	tcur = NULL;
	mp = cur->bc_mp;
	ASSERT(bno != NULLFSBLOCK);
	if (lbno != NULLFSBLOCK &&
	    lrecs + be16_to_cpu(block->bb_numrecs) <= XFS_BMAP_BLOCK_IMAXRECS(level, cur)) {
		rbno = bno;
		right = block;
		rbp = bp;
		if ((error = xfs_btree_read_bufl(mp, cur->bc_tp, lbno, 0, &lbp,
				XFS_BMAP_BTREE_REF))) {
			XFS_BMBT_TRACE_CURSOR(cur, ERROR);
			goto error0;
		}
		left = XFS_BUF_TO_BMBT_BLOCK(lbp);
		if ((error = xfs_btree_check_lblock(cur, left, level, lbp))) {
			XFS_BMBT_TRACE_CURSOR(cur, ERROR);
			goto error0;
		}
	} else if (rbno != NULLFSBLOCK &&
		   rrecs + be16_to_cpu(block->bb_numrecs) <=
		   XFS_BMAP_BLOCK_IMAXRECS(level, cur)) {
		lbno = bno;
		left = block;
		lbp = bp;
		if ((error = xfs_btree_read_bufl(mp, cur->bc_tp, rbno, 0, &rbp,
				XFS_BMAP_BTREE_REF))) {
			XFS_BMBT_TRACE_CURSOR(cur, ERROR);
			goto error0;
		}
		right = XFS_BUF_TO_BMBT_BLOCK(rbp);
		if ((error = xfs_btree_check_lblock(cur, right, level, rbp))) {
			XFS_BMBT_TRACE_CURSOR(cur, ERROR);
			goto error0;
		}
		lrecs = be16_to_cpu(left->bb_numrecs);
	} else {
		if (level > 0 && (error = xfs_bmbt_decrement(cur, level, &i))) {
			XFS_BMBT_TRACE_CURSOR(cur, ERROR);
			goto error0;
		}
		XFS_BMBT_TRACE_CURSOR(cur, EXIT);
		*stat = 1;
		return 0;
	}
	numlrecs = be16_to_cpu(left->bb_numrecs);
	numrrecs = be16_to_cpu(right->bb_numrecs);
	if (level > 0) {
		lkp = XFS_BMAP_KEY_IADDR(left, numlrecs + 1, cur);
		lpp = XFS_BMAP_PTR_IADDR(left, numlrecs + 1, cur);
		rkp = XFS_BMAP_KEY_IADDR(right, 1, cur);
		rpp = XFS_BMAP_PTR_IADDR(right, 1, cur);
#ifdef DEBUG
		for (i = 0; i < numrrecs; i++) {
			if ((error = xfs_btree_check_lptr_disk(cur, rpp[i], level))) {
				XFS_BMBT_TRACE_CURSOR(cur, ERROR);
				goto error0;
			}
		}
#endif
		memcpy(lkp, rkp, numrrecs * sizeof(*lkp));
		memcpy(lpp, rpp, numrrecs * sizeof(*lpp));
		xfs_bmbt_log_keys(cur, lbp, numlrecs + 1, numlrecs + numrrecs);
		xfs_bmbt_log_ptrs(cur, lbp, numlrecs + 1, numlrecs + numrrecs);
	} else {
		lrp = XFS_BMAP_REC_IADDR(left, numlrecs + 1, cur);
		rrp = XFS_BMAP_REC_IADDR(right, 1, cur);
		memcpy(lrp, rrp, numrrecs * sizeof(*lrp));
		xfs_bmbt_log_recs(cur, lbp, numlrecs + 1, numlrecs + numrrecs);
	}
	be16_add(&left->bb_numrecs, numrrecs);
	left->bb_rightsib = right->bb_rightsib;
	xfs_bmbt_log_block(cur, lbp, XFS_BB_RIGHTSIB | XFS_BB_NUMRECS);
	if (be64_to_cpu(left->bb_rightsib) != NULLDFSBNO) {
		if ((error = xfs_btree_read_bufl(mp, cur->bc_tp,
				be64_to_cpu(left->bb_rightsib),
				0, &rrbp, XFS_BMAP_BTREE_REF))) {
			XFS_BMBT_TRACE_CURSOR(cur, ERROR);
			goto error0;
		}
		rrblock = XFS_BUF_TO_BMBT_BLOCK(rrbp);
		if ((error = xfs_btree_check_lblock(cur, rrblock, level, rrbp))) {
			XFS_BMBT_TRACE_CURSOR(cur, ERROR);
			goto error0;
		}
		rrblock->bb_leftsib = cpu_to_be64(lbno);
		xfs_bmbt_log_block(cur, rrbp, XFS_BB_LEFTSIB);
	}
	xfs_bmap_add_free(XFS_DADDR_TO_FSB(mp, XFS_BUF_ADDR(rbp)), 1,
		cur->bc_private.b.flist, mp);
	cur->bc_private.b.ip->i_d.di_nblocks--;
	xfs_trans_log_inode(cur->bc_tp, cur->bc_private.b.ip, XFS_ILOG_CORE);
	XFS_TRANS_MOD_DQUOT_BYINO(mp, cur->bc_tp, cur->bc_private.b.ip,
			XFS_TRANS_DQ_BCOUNT, -1L);
	xfs_trans_binval(cur->bc_tp, rbp);
	if (bp != lbp) {
		cur->bc_bufs[level] = lbp;
		cur->bc_ptrs[level] += lrecs;
		cur->bc_ra[level] = 0;
	} else if ((error = xfs_bmbt_increment(cur, level + 1, &i))) {
		XFS_BMBT_TRACE_CURSOR(cur, ERROR);
		goto error0;
	}
	if (level > 0)
		cur->bc_ptrs[level]--;
	XFS_BMBT_TRACE_CURSOR(cur, EXIT);
	*stat = 2;
	return 0;

error0:
	if (tcur)
		xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
	return error;
}

/*
 * Insert one record/level.  Return information to the caller
 * allowing the next level up to proceed if necessary.
 */
STATIC int					/* error */
xfs_bmbt_insrec(
	xfs_btree_cur_t		*cur,
	int			level,
	xfs_fsblock_t		*bnop,
	xfs_bmbt_rec_t		*recp,
	xfs_btree_cur_t		**curp,
	int			*stat)		/* no-go/done/continue */
{
	xfs_bmbt_block_t	*block;		/* bmap btree block */
	xfs_buf_t		*bp;		/* buffer for block */
	int			error;		/* error return value */
	int			i;		/* loop index */
	xfs_bmbt_key_t		key;		/* bmap btree key */
	xfs_bmbt_key_t		*kp=NULL;	/* pointer to bmap btree key */
	int			logflags;	/* inode logging flags */
	xfs_fsblock_t		nbno;		/* new block number */
	struct xfs_btree_cur	*ncur;		/* new btree cursor */
	__uint64_t		startoff;	/* new btree key value */
	xfs_bmbt_rec_t		nrec;		/* new record count */
	int			optr;		/* old key/record index */
	xfs_bmbt_ptr_t		*pp;		/* pointer to bmap block addr */
	int			ptr;		/* key/record index */
	xfs_bmbt_rec_t		*rp=NULL;	/* pointer to bmap btree rec */
	int			numrecs;

	ASSERT(level < cur->bc_nlevels);
	XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
	XFS_BMBT_TRACE_ARGIFR(cur, level, *bnop, recp);
	ncur = NULL;
	key.br_startoff = cpu_to_be64(xfs_bmbt_disk_get_startoff(recp));
	optr = ptr = cur->bc_ptrs[level];
	if (ptr == 0) {
		XFS_BMBT_TRACE_CURSOR(cur, EXIT);
		*stat = 0;
		return 0;
	}
	XFS_STATS_INC(xs_bmbt_insrec);
	block = xfs_bmbt_get_block(cur, level, &bp);
	numrecs = be16_to_cpu(block->bb_numrecs);
#ifdef DEBUG
	if ((error = xfs_btree_check_lblock(cur, block, level, bp))) {
		XFS_BMBT_TRACE_CURSOR(cur, ERROR);
		return error;
	}
	if (ptr <= numrecs) {
		if (level == 0) {
			rp = XFS_BMAP_REC_IADDR(block, ptr, cur);
			xfs_btree_check_rec(XFS_BTNUM_BMAP, recp, rp);
		} else {
			kp = XFS_BMAP_KEY_IADDR(block, ptr, cur);
			xfs_btree_check_key(XFS_BTNUM_BMAP, &key, kp);
		}
	}
#endif
	nbno = NULLFSBLOCK;
	if (numrecs == XFS_BMAP_BLOCK_IMAXRECS(level, cur)) {
		if (numrecs < XFS_BMAP_BLOCK_DMAXRECS(level, cur)) {
			/*
			 * A root block, that can be made bigger.
			 */
			xfs_iroot_realloc(cur->bc_private.b.ip, 1,
				cur->bc_private.b.whichfork);
			block = xfs_bmbt_get_block(cur, level, &bp);
		} else if (level == cur->bc_nlevels - 1) {
			if ((error = xfs_bmbt_newroot(cur, &logflags, stat)) ||
			    *stat == 0) {
				XFS_BMBT_TRACE_CURSOR(cur, ERROR);
				return error;
			}
			xfs_trans_log_inode(cur->bc_tp, cur->bc_private.b.ip,
				logflags);
			block = xfs_bmbt_get_block(cur, level, &bp);
		} else {
			if ((error = xfs_bmbt_rshift(cur, level, &i))) {
				XFS_BMBT_TRACE_CURSOR(cur, ERROR);
				return error;
			}
			if (i) {
				/* nothing */
			} else {
				if ((error = xfs_bmbt_lshift(cur, level, &i))) {
					XFS_BMBT_TRACE_CURSOR(cur, ERROR);
					return error;
				}
				if (i) {
					optr = ptr = cur->bc_ptrs[level];
				} else {
					if ((error = xfs_bmbt_split(cur, level,
							&nbno, &startoff, &ncur,
							&i))) {
						XFS_BMBT_TRACE_CURSOR(cur,
							ERROR);
						return error;
					}
					if (i) {
						block = xfs_bmbt_get_block(
							    cur, level, &bp);
#ifdef DEBUG
						if ((error =
						    xfs_btree_check_lblock(cur,
							    block, level, bp))) {
							XFS_BMBT_TRACE_CURSOR(
								cur, ERROR);
							return error;
						}
#endif
						ptr = cur->bc_ptrs[level];
						xfs_bmbt_disk_set_allf(&nrec,
							startoff, 0, 0,
							XFS_EXT_NORM);
					} else {
						XFS_BMBT_TRACE_CURSOR(cur,
							EXIT);
						*stat = 0;
						return 0;
					}
				}
			}
		}
	}
	numrecs = be16_to_cpu(block->bb_numrecs);
	if (level > 0) {
		kp = XFS_BMAP_KEY_IADDR(block, 1, cur);
		pp = XFS_BMAP_PTR_IADDR(block, 1, cur);
#ifdef DEBUG
		for (i = numrecs; i >= ptr; i--) {
			if ((error = xfs_btree_check_lptr_disk(cur, pp[i - 1],
					level))) {
				XFS_BMBT_TRACE_CURSOR(cur, ERROR);
				return error;
			}
		}
#endif
		memmove(&kp[ptr], &kp[ptr - 1],
			(numrecs - ptr + 1) * sizeof(*kp));
		memmove(&pp[ptr], &pp[ptr - 1],
			(numrecs - ptr + 1) * sizeof(*pp));
#ifdef DEBUG
		if ((error = xfs_btree_check_lptr(cur, *bnop, level))) {
			XFS_BMBT_TRACE_CURSOR(cur, ERROR);
			return error;
		}
#endif
		kp[ptr - 1] = key;
		pp[ptr - 1] = cpu_to_be64(*bnop);
		numrecs++;
		block->bb_numrecs = cpu_to_be16(numrecs);
		xfs_bmbt_log_keys(cur, bp, ptr, numrecs);
		xfs_bmbt_log_ptrs(cur, bp, ptr, numrecs);
	} else {
		rp = XFS_BMAP_REC_IADDR(block, 1, cur);
		memmove(&rp[ptr], &rp[ptr - 1],
			(numrecs - ptr + 1) * sizeof(*rp));
		rp[ptr - 1] = *recp;
		numrecs++;
		block->bb_numrecs = cpu_to_be16(numrecs);
		xfs_bmbt_log_recs(cur, bp, ptr, numrecs);
	}
	xfs_bmbt_log_block(cur, bp, XFS_BB_NUMRECS);
#ifdef DEBUG
	if (ptr < numrecs) {
		if (level == 0)
			xfs_btree_check_rec(XFS_BTNUM_BMAP, rp + ptr - 1,
				rp + ptr);
		else
			xfs_btree_check_key(XFS_BTNUM_BMAP, kp + ptr - 1,
				kp + ptr);
	}
#endif
	if (optr == 1 && (error = xfs_bmbt_updkey(cur, &key, level + 1))) {
		XFS_BMBT_TRACE_CURSOR(cur, ERROR);
		return error;
	}
	*bnop = nbno;
	if (nbno != NULLFSBLOCK) {
		*recp = nrec;
		*curp = ncur;
	}
	XFS_BMBT_TRACE_CURSOR(cur, EXIT);
	*stat = 1;
	return 0;
}

STATIC int
xfs_bmbt_killroot(
	xfs_btree_cur_t		*cur)
{
	xfs_bmbt_block_t	*block;
	xfs_bmbt_block_t	*cblock;
	xfs_buf_t		*cbp;
	xfs_bmbt_key_t		*ckp;
	xfs_bmbt_ptr_t		*cpp;
#ifdef DEBUG
	int			error;
#endif
	int			i;
	xfs_bmbt_key_t		*kp;
	xfs_inode_t		*ip;
	xfs_ifork_t		*ifp;
	int			level;
	xfs_bmbt_ptr_t		*pp;

	XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
	level = cur->bc_nlevels - 1;
	ASSERT(level >= 1);
	/*
	 * Don't deal with the root block needs to be a leaf case.
	 * We're just going to turn the thing back into extents anyway.
	 */
	if (level == 1) {
		XFS_BMBT_TRACE_CURSOR(cur, EXIT);
		return 0;
	}
	block = xfs_bmbt_get_block(cur, level, &cbp);
	/*
	 * Give up if the root has multiple children.
	 */
	if (be16_to_cpu(block->bb_numrecs) != 1) {
		XFS_BMBT_TRACE_CURSOR(cur, EXIT);
		return 0;
	}
	/*
	 * Only do this if the next level will fit.
	 * Then the data must be copied up to the inode,
	 * instead of freeing the root you free the next level.
	 */
	cbp = cur->bc_bufs[level - 1];
	cblock = XFS_BUF_TO_BMBT_BLOCK(cbp);
	if (be16_to_cpu(cblock->bb_numrecs) > XFS_BMAP_BLOCK_DMAXRECS(level, cur)) {
		XFS_BMBT_TRACE_CURSOR(cur, EXIT);
		return 0;
	}
	ASSERT(be64_to_cpu(cblock->bb_leftsib) == NULLDFSBNO);
	ASSERT(be64_to_cpu(cblock->bb_rightsib) == NULLDFSBNO);
	ip = cur->bc_private.b.ip;
	ifp = XFS_IFORK_PTR(ip, cur->bc_private.b.whichfork);
	ASSERT(XFS_BMAP_BLOCK_IMAXRECS(level, cur) ==
	       XFS_BMAP_BROOT_MAXRECS(ifp->if_broot_bytes));
	i = (int)(be16_to_cpu(cblock->bb_numrecs) - XFS_BMAP_BLOCK_IMAXRECS(level, cur));
	if (i) {
		xfs_iroot_realloc(ip, i, cur->bc_private.b.whichfork);
		block = ifp->if_broot;
	}
	be16_add(&block->bb_numrecs, i);
	ASSERT(block->bb_numrecs == cblock->bb_numrecs);
	kp = XFS_BMAP_KEY_IADDR(block, 1, cur);
	ckp = XFS_BMAP_KEY_IADDR(cblock, 1, cur);
	memcpy(kp, ckp, be16_to_cpu(block->bb_numrecs) * sizeof(*kp));
	pp = XFS_BMAP_PTR_IADDR(block, 1, cur);
	cpp = XFS_BMAP_PTR_IADDR(cblock, 1, cur);
#ifdef DEBUG
	for (i = 0; i < be16_to_cpu(cblock->bb_numrecs); i++) {
		if ((error = xfs_btree_check_lptr_disk(cur, cpp[i], level - 1))) {
			XFS_BMBT_TRACE_CURSOR(cur, ERROR);
			return error;
		}
	}
#endif
	memcpy(pp, cpp, be16_to_cpu(block->bb_numrecs) * sizeof(*pp));
	xfs_bmap_add_free(XFS_DADDR_TO_FSB(cur->bc_mp, XFS_BUF_ADDR(cbp)), 1,
			cur->bc_private.b.flist, cur->bc_mp);
	ip->i_d.di_nblocks--;
	XFS_TRANS_MOD_DQUOT_BYINO(cur->bc_mp, cur->bc_tp, ip,
			XFS_TRANS_DQ_BCOUNT, -1L);
	xfs_trans_binval(cur->bc_tp, cbp);
	cur->bc_bufs[level - 1] = NULL;
	be16_add(&block->bb_level, -1);