xfs_alloc_btree.c

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

/*
 * Copyright (c) 2000-2001 Silicon Graphics, Inc.  All Rights Reserved.
 *
 * This program is free software; you can redistribute it and/or modify it
 * under the terms of version 2 of the GNU General Public License as
 * published by the Free Software Foundation.
 *
 * This program is distributed in the hope that it would be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 *
 * Further, this software is distributed without any warranty that it is
 * free of the rightful claim of any third person regarding infringement
 * or the like.  Any license provided herein, whether implied or
 * otherwise, applies only to this software file.  Patent licenses, if
 * any, provided herein do not apply to combinations of this program with
 * other software, or any other product whatsoever.
 *
 * You should have received a copy of the GNU General Public License along
 * with this program; if not, write the Free Software Foundation, Inc., 59
 * Temple Place - Suite 330, Boston MA 02111-1307, USA.
 *
 * Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy,
 * Mountain View, CA  94043, or:
 *
 * http://www.sgi.com
 *
 * For further information regarding this notice, see:
 *
 * http://oss.sgi.com/projects/GenInfo/SGIGPLNoticeExplan/
 */

/*
 * Free space allocation for XFS.
 */

#include "xfs.h"
#include "xfs_macros.h"
#include "xfs_types.h"
#include "xfs_inum.h"
#include "xfs_log.h"
#include "xfs_trans.h"
#include "xfs_sb.h"
#include "xfs_ag.h"
#include "xfs_dir.h"
#include "xfs_dmapi.h"
#include "xfs_mount.h"
#include "xfs_alloc_btree.h"
#include "xfs_ialloc_btree.h"
#include "xfs_bmap_btree.h"
#include "xfs_btree.h"
#include "xfs_ialloc.h"
#include "xfs_alloc.h"
#include "xfs_error.h"

/*
 * Prototypes for internal functions.
 */

STATIC void xfs_alloc_log_block(xfs_trans_t *, xfs_buf_t *, int);
STATIC void xfs_alloc_log_keys(xfs_btree_cur_t *, xfs_buf_t *, int, int);
STATIC void xfs_alloc_log_ptrs(xfs_btree_cur_t *, xfs_buf_t *, int, int);
STATIC void xfs_alloc_log_recs(xfs_btree_cur_t *, xfs_buf_t *, int, int);
STATIC int xfs_alloc_lshift(xfs_btree_cur_t *, int, int *);
STATIC int xfs_alloc_newroot(xfs_btree_cur_t *, int *);
STATIC int xfs_alloc_rshift(xfs_btree_cur_t *, int, int *);
STATIC int xfs_alloc_split(xfs_btree_cur_t *, int, xfs_agblock_t *,
		xfs_alloc_key_t *, xfs_btree_cur_t **, int *);
STATIC int xfs_alloc_updkey(xfs_btree_cur_t *, xfs_alloc_key_t *, int);

/*
 * Internal functions.
 */

/*
 * Single level of the xfs_alloc_delete record deletion routine.
 * Delete record pointed to by cur/level.
 * Remove the record from its block then rebalance the tree.
 * Return 0 for error, 1 for done, 2 to go on to the next level.
 */
STATIC int				/* error */
xfs_alloc_delrec(
	xfs_btree_cur_t		*cur,	/* btree cursor */
	int			level,	/* level removing record from */
	int			*stat)	/* fail/done/go-on */
{
	xfs_agf_t		*agf;	/* allocation group freelist header */
	xfs_alloc_block_t	*block;	/* btree block record/key lives in */
	xfs_agblock_t		bno;	/* btree block number */
	xfs_buf_t		*bp;	/* buffer for block */
	int			error;	/* error return value */
	int			i;	/* loop index */
	xfs_alloc_key_t		key;	/* kp points here if block is level 0 */
	xfs_agblock_t		lbno;	/* left block's block number */
	xfs_buf_t		*lbp;	/* left block's buffer pointer */
	xfs_alloc_block_t	*left;	/* left btree block */
	xfs_alloc_key_t		*lkp=NULL;	/* left block key pointer */
	xfs_alloc_ptr_t		*lpp=NULL;	/* left block address pointer */
	int			lrecs=0;	/* number of records in left block */
	xfs_alloc_rec_t		*lrp;	/* left block record pointer */
	xfs_mount_t		*mp;	/* mount structure */
	int			ptr;	/* index in btree block for this rec */
	xfs_agblock_t		rbno;	/* right block's block number */
	xfs_buf_t		*rbp;	/* right block's buffer pointer */
	xfs_alloc_block_t	*right;	/* right btree block */
	xfs_alloc_key_t		*rkp;	/* right block key pointer */
	xfs_alloc_ptr_t		*rpp;	/* right block address pointer */
	int			rrecs=0;	/* number of records in right block */
	xfs_alloc_rec_t		*rrp;	/* right block record pointer */
	xfs_btree_cur_t		*tcur;	/* temporary btree cursor */

	/*
	 * Get the index of the entry being deleted, check for nothing there.
	 */
	ptr = cur->bc_ptrs[level];
	if (ptr == 0) {
		*stat = 0;
		return 0;
	}
	/*
	 * Get the buffer & block containing the record or key/ptr.
	 */
	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;
#endif
	/*
	 * Fail if we're off the end of the block.
	 */
	if (ptr > INT_GET(block->bb_numrecs, ARCH_CONVERT)) {
		*stat = 0;
		return 0;
	}
	XFS_STATS_INC(xs_abt_delrec);
	/*
	 * It's a nonleaf.  Excise the key and ptr being deleted, by
	 * sliding the entries past them down one.
	 * Log the changed areas of the block.
	 */
	if (level > 0) {
		lkp = XFS_ALLOC_KEY_ADDR(block, 1, cur);
		lpp = XFS_ALLOC_PTR_ADDR(block, 1, cur);
#ifdef DEBUG
		for (i = ptr; i < INT_GET(block->bb_numrecs, ARCH_CONVERT); i++) {
			if ((error = xfs_btree_check_sptr(cur, INT_GET(lpp[i], ARCH_CONVERT), level)))
				return error;
		}
#endif
		if (ptr < INT_GET(block->bb_numrecs, ARCH_CONVERT)) {
			memmove(&lkp[ptr - 1], &lkp[ptr],
				(INT_GET(block->bb_numrecs, ARCH_CONVERT) - ptr) * sizeof(*lkp)); /* INT_: mem copy */
			memmove(&lpp[ptr - 1], &lpp[ptr],
				(INT_GET(block->bb_numrecs, ARCH_CONVERT) - ptr) * sizeof(*lpp)); /* INT_: mem copy */
			xfs_alloc_log_ptrs(cur, bp, ptr, INT_GET(block->bb_numrecs, ARCH_CONVERT) - 1);
			xfs_alloc_log_keys(cur, bp, ptr, INT_GET(block->bb_numrecs, ARCH_CONVERT) - 1);
		}
	}
	/*
	 * It's a leaf.  Excise the record being deleted, by sliding the
	 * entries past it down one.  Log the changed areas of the block.
	 */
	else {
		lrp = XFS_ALLOC_REC_ADDR(block, 1, cur);
		if (ptr < INT_GET(block->bb_numrecs, ARCH_CONVERT)) {
			memmove(&lrp[ptr - 1], &lrp[ptr],
				(INT_GET(block->bb_numrecs, ARCH_CONVERT) - ptr) * sizeof(*lrp));
			xfs_alloc_log_recs(cur, bp, ptr, INT_GET(block->bb_numrecs, ARCH_CONVERT) - 1);
		}
		/*
		 * If it's the first record in the block, we'll need a key
		 * structure to pass up to the next level (updkey).
		 */
		if (ptr == 1) {
			key.ar_startblock = lrp->ar_startblock; /* INT_: direct copy */
			key.ar_blockcount = lrp->ar_blockcount; /* INT_: direct copy */
			lkp = &key;
		}
	}
	/*
	 * Decrement and log the number of entries in the block.
	 */
	INT_MOD(block->bb_numrecs, ARCH_CONVERT, -1);
	xfs_alloc_log_block(cur->bc_tp, bp, XFS_BB_NUMRECS);
	/*
	 * See if the longest free extent in the allocation group was
	 * changed by this operation.  True if it's the by-size btree, and
	 * this is the leaf level, and there is no right sibling block,
	 * and this was the last record.
	 */
	agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
	mp = cur->bc_mp;

	if (level == 0 &&
	    cur->bc_btnum == XFS_BTNUM_CNT &&
	    INT_GET(block->bb_rightsib, ARCH_CONVERT) == NULLAGBLOCK &&
	    ptr > INT_GET(block->bb_numrecs, ARCH_CONVERT)) {
		ASSERT(ptr == INT_GET(block->bb_numrecs, ARCH_CONVERT) + 1);
		/*
		 * There are still records in the block.  Grab the size
		 * from the last one.
		 */
		if (INT_GET(block->bb_numrecs, ARCH_CONVERT)) {
			rrp = XFS_ALLOC_REC_ADDR(block, INT_GET(block->bb_numrecs, ARCH_CONVERT), cur);
			INT_COPY(agf->agf_longest, rrp->ar_blockcount, ARCH_CONVERT);
		}
		/*
		 * No free extents left.
		 */
		else
			INT_ZERO(agf->agf_longest, ARCH_CONVERT);
		mp->m_perag[INT_GET(agf->agf_seqno, ARCH_CONVERT)].pagf_longest =
			INT_GET(agf->agf_longest, ARCH_CONVERT);
		xfs_alloc_log_agf(cur->bc_tp, cur->bc_private.a.agbp,
			XFS_AGF_LONGEST);
	}
	/*
	 * Is this the root level?  If so, we're almost done.
	 */
	if (level == cur->bc_nlevels - 1) {
		/*
		 * If this is the root level,
		 * and there's only one entry left,
		 * and it's NOT the leaf level,
		 * then we can get rid of this level.
		 */
		if (INT_GET(block->bb_numrecs, ARCH_CONVERT) == 1 && level > 0) {
			/*
			 * lpp is still set to the first pointer in the block.
			 * Make it the new root of the btree.
			 */
			bno = INT_GET(agf->agf_roots[cur->bc_btnum], ARCH_CONVERT);
			INT_COPY(agf->agf_roots[cur->bc_btnum], *lpp, ARCH_CONVERT);
			INT_MOD(agf->agf_levels[cur->bc_btnum], ARCH_CONVERT, -1);
			mp->m_perag[INT_GET(agf->agf_seqno, ARCH_CONVERT)].pagf_levels[cur->bc_btnum]--;
			/*
			 * Put this buffer/block on the ag's freelist.
			 */
			if ((error = xfs_alloc_put_freelist(cur->bc_tp,
					cur->bc_private.a.agbp, NULL, bno)))
				return error;
			/*
			 * Since blocks move to the free list without the
			 * coordination used in xfs_bmap_finish, we can't allow
			 * block to be available for reallocation and
			 * non-transaction writing (user data) until we know
			 * that the transaction that moved it to the free list
			 * is permanently on disk. We track the blocks by
			 * declaring these blocks as "busy"; the busy list is
			 * maintained on a per-ag basis and each transaction
			 * records which entries should be removed when the
			 * iclog commits to disk. If a busy block is
			 * allocated, the iclog is pushed up to the LSN
			 * that freed the block.
			 */
			xfs_alloc_mark_busy(cur->bc_tp,
				INT_GET(agf->agf_seqno, ARCH_CONVERT), bno, 1);

			xfs_trans_agbtree_delta(cur->bc_tp, -1);
			xfs_alloc_log_agf(cur->bc_tp, cur->bc_private.a.agbp,
				XFS_AGF_ROOTS | XFS_AGF_LEVELS);
			/*
			 * Update the cursor so there's one fewer level.
			 */
			xfs_btree_setbuf(cur, level, NULL);
			cur->bc_nlevels--;
		} else if (level > 0 &&
			   (error = xfs_alloc_decrement(cur, level, &i)))
			return error;
		*stat = 1;
		return 0;
	}
	/*
	 * If we deleted the leftmost entry in the block, update the
	 * key values above us in the tree.
	 */
	if (ptr == 1 && (error = xfs_alloc_updkey(cur, lkp, level + 1)))
		return error;
	/*
	 * If the number of records remaining in the block is at least
	 * the minimum, we're done.
	 */
	if (INT_GET(block->bb_numrecs, ARCH_CONVERT) >= XFS_ALLOC_BLOCK_MINRECS(level, cur)) {
		if (level > 0 && (error = xfs_alloc_decrement(cur, level, &i)))
			return error;
		*stat = 1;
		return 0;
	}
	/*
	 * Otherwise, we have to move some records around to keep the
	 * tree balanced.  Look at the left and right sibling blocks to
	 * see if we can re-balance by moving only one record.
	 */
	rbno = INT_GET(block->bb_rightsib, ARCH_CONVERT);
	lbno = INT_GET(block->bb_leftsib, ARCH_CONVERT);
	bno = NULLAGBLOCK;
	ASSERT(rbno != NULLAGBLOCK || lbno != NULLAGBLOCK);
	/*
	 * Duplicate the cursor so our btree manipulations here won't
	 * disrupt the next level up.
	 */
	if ((error = xfs_btree_dup_cursor(cur, &tcur)))
		return error;
	/*
	 * If there's a right sibling, see if it's ok to shift an entry
	 * out of it.
	 */
	if (rbno != NULLAGBLOCK) {
		/*
		 * Move the temp cursor to the last entry in the next block.
		 * Actually any entry but the first would suffice.
		 */
		i = xfs_btree_lastrec(tcur, level);
		XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
		if ((error = xfs_alloc_increment(tcur, level, &i)))
			goto error0;
		XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
		i = xfs_btree_lastrec(tcur, level);
		XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
		/*
		 * Grab a pointer to the block.
		 */
		rbp = tcur->bc_bufs[level];
		right = XFS_BUF_TO_ALLOC_BLOCK(rbp);
#ifdef DEBUG
		if ((error = xfs_btree_check_sblock(cur, right, level, rbp)))
			goto error0;
#endif
		/*
		 * Grab the current block number, for future use.
		 */
		bno = INT_GET(right->bb_leftsib, ARCH_CONVERT);
		/*
		 * If right block is full enough so that removing one entry
		 * won't make it too empty, and left-shifting an entry out
		 * of right to us works, we're done.
		 */
		if (INT_GET(right->bb_numrecs, ARCH_CONVERT) - 1 >=
		     XFS_ALLOC_BLOCK_MINRECS(level, cur)) {
			if ((error = xfs_alloc_lshift(tcur, level, &i)))
				goto error0;
			if (i) {
				ASSERT(INT_GET(block->bb_numrecs, ARCH_CONVERT) >=
				       XFS_ALLOC_BLOCK_MINRECS(level, cur));
				xfs_btree_del_cursor(tcur,
						     XFS_BTREE_NOERROR);
				if (level > 0 &&
				    (error = xfs_alloc_decrement(cur, level,
					    &i)))
					return error;
				*stat = 1;
				return 0;
			}
		}
		/*
		 * Otherwise, grab the number of records in right for
		 * future reference, and fix up the temp cursor to point
		 * to our block again (last record).
		 */
		rrecs = INT_GET(right->bb_numrecs, ARCH_CONVERT);
		if (lbno != NULLAGBLOCK) {
			i = xfs_btree_firstrec(tcur, level);
			XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
			if ((error = xfs_alloc_decrement(tcur, level, &i)))
				goto error0;
			XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
		}
	}
	/*
	 * If there's a left sibling, see if it's ok to shift an entry
	 * out of it.
	 */
	if (lbno != NULLAGBLOCK) {
		/*
		 * Move the temp cursor to the first entry in the
		 * previous block.
		 */
		i = xfs_btree_firstrec(tcur, level);
		XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
		if ((error = xfs_alloc_decrement(tcur, level, &i)))
			goto error0;
		XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
		xfs_btree_firstrec(tcur, level);
		/*
		 * Grab a pointer to the block.
		 */
		lbp = tcur->bc_bufs[level];
		left = XFS_BUF_TO_ALLOC_BLOCK(lbp);
#ifdef DEBUG
		if ((error = xfs_btree_check_sblock(cur, left, level, lbp)))
			goto error0;
#endif
		/*
		 * Grab the current block number, for future use.
		 */
		bno = INT_GET(left->bb_rightsib, ARCH_CONVERT);
		/*
		 * If left block is full enough so that removing one entry
		 * won't make it too empty, and right-shifting an entry out
		 * of left to us works, we're done.
		 */
		if (INT_GET(left->bb_numrecs, ARCH_CONVERT) - 1 >=
		     XFS_ALLOC_BLOCK_MINRECS(level, cur)) {
			if ((error = xfs_alloc_rshift(tcur, level, &i)))
				goto error0;
			if (i) {
				ASSERT(INT_GET(block->bb_numrecs, ARCH_CONVERT) >=
				       XFS_ALLOC_BLOCK_MINRECS(level, cur));
				xfs_btree_del_cursor(tcur,
						     XFS_BTREE_NOERROR);
				if (level == 0)
					cur->bc_ptrs[0]++;
				*stat = 1;