xfs_alloc_btree.c

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

				return 0;
			}
		}
		/*
		 * Otherwise, grab the number of records in right for
		 * future reference.
		 */
		lrecs = INT_GET(left->bb_numrecs, ARCH_CONVERT);
	}
	/*
	 * Delete the temp cursor, we're done with it.
	 */
	xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
	/*
	 * If here, we need to do a join to keep the tree balanced.
	 */
	ASSERT(bno != NULLAGBLOCK);
	/*
	 * See if we can join with the left neighbor block.
	 */
	if (lbno != NULLAGBLOCK &&
	    lrecs + INT_GET(block->bb_numrecs, ARCH_CONVERT) <= XFS_ALLOC_BLOCK_MAXRECS(level, cur)) {
		/*
		 * Set "right" to be the starting block,
		 * "left" to be the left neighbor.
		 */
		rbno = bno;
		right = block;
		rbp = bp;
		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, level, lbp)))
			return error;
	}
	/*
	 * If that won't work, see if we can join with the right neighbor block.
	 */
	else if (rbno != NULLAGBLOCK &&
		 rrecs + INT_GET(block->bb_numrecs, ARCH_CONVERT) <=
		  XFS_ALLOC_BLOCK_MAXRECS(level, cur)) {
		/*
		 * Set "left" to be the starting block,
		 * "right" to be the right neighbor.
		 */
		lbno = bno;
		left = block;
		lbp = bp;
		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, level, rbp)))
			return error;
	}
	/*
	 * Otherwise, we can't fix the imbalance.
	 * Just return.  This is probably a logic error, but it's not fatal.
	 */
	else {
		if (level > 0 && (error = xfs_alloc_decrement(cur, level, &i)))
			return error;
		*stat = 1;
		return 0;
	}
	/*
	 * We're now going to join "left" and "right" by moving all the stuff
	 * in "right" to "left" and deleting "right".
	 */
	if (level > 0) {
		/*
		 * It's a non-leaf.  Move keys and pointers.
		 */
		lkp = XFS_ALLOC_KEY_ADDR(left, INT_GET(left->bb_numrecs, ARCH_CONVERT) + 1, cur);
		lpp = XFS_ALLOC_PTR_ADDR(left, INT_GET(left->bb_numrecs, ARCH_CONVERT) + 1, cur);
		rkp = XFS_ALLOC_KEY_ADDR(right, 1, cur);
		rpp = XFS_ALLOC_PTR_ADDR(right, 1, cur);
#ifdef DEBUG
		for (i = 0; i < INT_GET(right->bb_numrecs, ARCH_CONVERT); i++) {
			if ((error = xfs_btree_check_sptr(cur, INT_GET(rpp[i], ARCH_CONVERT), level)))
				return error;
		}
#endif
		memcpy(lkp, rkp, INT_GET(right->bb_numrecs, ARCH_CONVERT) * sizeof(*lkp)); /* INT_: structure copy */
		memcpy(lpp, rpp, INT_GET(right->bb_numrecs, ARCH_CONVERT) * sizeof(*lpp)); /* INT_: structure copy */
		xfs_alloc_log_keys(cur, lbp, INT_GET(left->bb_numrecs, ARCH_CONVERT) + 1,
				   INT_GET(left->bb_numrecs, ARCH_CONVERT) + INT_GET(right->bb_numrecs, ARCH_CONVERT));
		xfs_alloc_log_ptrs(cur, lbp, INT_GET(left->bb_numrecs, ARCH_CONVERT) + 1,
				   INT_GET(left->bb_numrecs, ARCH_CONVERT) + INT_GET(right->bb_numrecs, ARCH_CONVERT));
	} else {
		/*
		 * It's a leaf.  Move records.
		 */
		lrp = XFS_ALLOC_REC_ADDR(left, INT_GET(left->bb_numrecs, ARCH_CONVERT) + 1, cur);
		rrp = XFS_ALLOC_REC_ADDR(right, 1, cur);
		memcpy(lrp, rrp, INT_GET(right->bb_numrecs, ARCH_CONVERT) * sizeof(*lrp));
		xfs_alloc_log_recs(cur, lbp, INT_GET(left->bb_numrecs, ARCH_CONVERT) + 1,
				   INT_GET(left->bb_numrecs, ARCH_CONVERT) + INT_GET(right->bb_numrecs, ARCH_CONVERT));
	}
	/*
	 * If we joined with the left neighbor, set the buffer in the
	 * cursor to the left block, and fix up the index.
	 */
	if (bp != lbp) {
		xfs_btree_setbuf(cur, level, lbp);
		cur->bc_ptrs[level] += INT_GET(left->bb_numrecs, ARCH_CONVERT);
	}
	/*
	 * If we joined with the right neighbor and there's a level above
	 * us, increment the cursor at that level.
	 */
	else if (level + 1 < cur->bc_nlevels &&
		 (error = xfs_alloc_increment(cur, level + 1, &i)))
		return error;
	/*
	 * Fix up the number of records in the surviving block.
	 */
	INT_MOD(left->bb_numrecs, ARCH_CONVERT, INT_GET(right->bb_numrecs, ARCH_CONVERT));
	/*
	 * Fix up the right block pointer in the surviving block, and log it.
	 */
	left->bb_rightsib = right->bb_rightsib; /* INT_: direct copy */
	xfs_alloc_log_block(cur->bc_tp, lbp, XFS_BB_NUMRECS | XFS_BB_RIGHTSIB);
	/*
	 * If there is a right sibling now, make it point to the
	 * remaining block.
	 */
	if (INT_GET(left->bb_rightsib, ARCH_CONVERT) != NULLAGBLOCK) {
		xfs_alloc_block_t	*rrblock;
		xfs_buf_t		*rrbp;

		if ((error = xfs_btree_read_bufs(mp, cur->bc_tp,
				cur->bc_private.a.agno, INT_GET(left->bb_rightsib, ARCH_CONVERT), 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;
		INT_SET(rrblock->bb_leftsib, ARCH_CONVERT, lbno);
		xfs_alloc_log_block(cur->bc_tp, rrbp, XFS_BB_LEFTSIB);
	}
	/*
	 * Free the deleting block by putting it on the freelist.
	 */
	if ((error = xfs_alloc_put_freelist(cur->bc_tp, cur->bc_private.a.agbp,
			NULL, rbno)))
		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);
	/*
	 * Adjust the current level's cursor so that we're left referring
	 * to the right node, after we're done.
	 * If this leaves the ptr value 0 our caller will fix it up.
	 */
	if (level > 0)
		cur->bc_ptrs[level]--;
	/*
	 * Return value means the next level up has something to do.
	 */
	*stat = 2;
	return 0;

error0:
	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_alloc_insrec(
	xfs_btree_cur_t		*cur,	/* btree cursor */
	int			level,	/* level to insert record at */
	xfs_agblock_t		*bnop,	/* i/o: block number inserted */
	xfs_alloc_rec_t		*recp,	/* i/o: record data inserted */
	xfs_btree_cur_t		**curp,	/* output: new cursor replacing cur */
	int			*stat)	/* output: success/failure */
{
	xfs_agf_t		*agf;	/* allocation group freelist header */
	xfs_alloc_block_t	*block;	/* btree block record/key lives in */
	xfs_buf_t		*bp;	/* buffer for block */
	int			error;	/* error return value */
	int			i;	/* loop index */
	xfs_alloc_key_t		key;	/* key value being inserted */
	xfs_alloc_key_t		*kp;	/* pointer to btree keys */
	xfs_agblock_t		nbno;	/* block number of allocated block */
	xfs_btree_cur_t		*ncur;	/* new cursor to be used at next lvl */
	xfs_alloc_key_t		nkey;	/* new key value, from split */
	xfs_alloc_rec_t		nrec;	/* new record value, for caller */
	int			optr;	/* old ptr value */
	xfs_alloc_ptr_t		*pp;	/* pointer to btree addresses */
	int			ptr;	/* index in btree block for this rec */
	xfs_alloc_rec_t		*rp;	/* pointer to btree records */

	ASSERT(INT_GET(recp->ar_blockcount, ARCH_CONVERT) > 0);
	/*
	 * If we made it to the root level, allocate a new root block
	 * and we're done.
	 */
	if (level >= cur->bc_nlevels) {
		XFS_STATS_INC(xs_abt_insrec);
		if ((error = xfs_alloc_newroot(cur, &i)))
			return error;
		*bnop = NULLAGBLOCK;
		*stat = i;
		return 0;
	}
	/*
	 * Make a key out of the record data to be inserted, and save it.
	 */
	key.ar_startblock = recp->ar_startblock; /* INT_: direct copy */
	key.ar_blockcount = recp->ar_blockcount; /* INT_: direct copy */
	optr = ptr = cur->bc_ptrs[level];
	/*
	 * If we're off the left edge, return failure.
	 */
	if (ptr == 0) {
		*stat = 0;
		return 0;
	}
	XFS_STATS_INC(xs_abt_insrec);
	/*
	 * Get pointers to the btree buffer and block.
	 */
	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;
	/*
	 * Check that the new entry is being inserted in the right place.
	 */
	if (ptr <= INT_GET(block->bb_numrecs, ARCH_CONVERT)) {
		if (level == 0) {
			rp = XFS_ALLOC_REC_ADDR(block, ptr, cur);
			xfs_btree_check_rec(cur->bc_btnum, recp, rp);
		} else {
			kp = XFS_ALLOC_KEY_ADDR(block, ptr, cur);
			xfs_btree_check_key(cur->bc_btnum, &key, kp);
		}
	}
#endif
	nbno = NULLAGBLOCK;
	ncur = (xfs_btree_cur_t *)0;
	/*
	 * If the block is full, we can't insert the new entry until we
	 * make the block un-full.
	 */
	if (INT_GET(block->bb_numrecs, ARCH_CONVERT) == XFS_ALLOC_BLOCK_MAXRECS(level, cur)) {
		/*
		 * First, try shifting an entry to the right neighbor.
		 */
		if ((error = xfs_alloc_rshift(cur, level, &i)))
			return error;
		if (i) {
			/* nothing */
		}
		/*
		 * Next, try shifting an entry to the left neighbor.
		 */
		else {
			if ((error = xfs_alloc_lshift(cur, level, &i)))
				return error;
			if (i)
				optr = ptr = cur->bc_ptrs[level];
			else {
				/*
				 * Next, try splitting the current block in
				 * half. If this works we have to re-set our
				 * variables because we could be in a
				 * different block now.
				 */
				if ((error = xfs_alloc_split(cur, level, &nbno,
						&nkey, &ncur, &i)))
					return error;
				if (i) {
					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
					ptr = cur->bc_ptrs[level];
					nrec.ar_startblock = nkey.ar_startblock; /* INT_: direct copy */
					nrec.ar_blockcount = nkey.ar_blockcount; /* INT_: direct copy */
				}
				/*
				 * Otherwise the insert fails.
				 */
				else {
					*stat = 0;
					return 0;
				}
			}
		}
	}
	/*
	 * At this point we know there's room for our new entry in the block
	 * we're pointing at.
	 */
	if (level > 0) {
		/*
		 * It's a non-leaf entry.  Make a hole for the new data
		 * in the key and ptr regions of the block.
		 */
		kp = XFS_ALLOC_KEY_ADDR(block, 1, cur);
		pp = XFS_ALLOC_PTR_ADDR(block, 1, cur);
#ifdef DEBUG
		for (i = INT_GET(block->bb_numrecs, ARCH_CONVERT); i >= ptr; i--) {
			if ((error = xfs_btree_check_sptr(cur, INT_GET(pp[i - 1], ARCH_CONVERT), level)))
				return error;
		}
#endif
		memmove(&kp[ptr], &kp[ptr - 1],
			(INT_GET(block->bb_numrecs, ARCH_CONVERT) - ptr + 1) * sizeof(*kp)); /* INT_: copy */
		memmove(&pp[ptr], &pp[ptr - 1],
			(INT_GET(block->bb_numrecs, ARCH_CONVERT) - ptr + 1) * sizeof(*pp)); /* INT_: copy */
#ifdef DEBUG
		if ((error = xfs_btree_check_sptr(cur, *bnop, level)))
			return error;
#endif
		/*
		 * Now stuff the new data in, bump numrecs and log the new data.
		 */
		kp[ptr - 1] = key;
		INT_SET(pp[ptr - 1], ARCH_CONVERT, *bnop);
		INT_MOD(block->bb_numrecs, ARCH_CONVERT, +1);
		xfs_alloc_log_keys(cur, bp, ptr, INT_GET(block->bb_numrecs, ARCH_CONVERT));
		xfs_alloc_log_ptrs(cur, bp, ptr, INT_GET(block->bb_numrecs, ARCH_CONVERT));
#ifdef DEBUG
		if (ptr < INT_GET(block->bb_numrecs, ARCH_CONVERT))
			xfs_btree_check_key(cur->bc_btnum, kp + ptr - 1,
				kp + ptr);
#endif
	} else {
		/*
		 * It's a leaf entry.  Make a hole for the new record.
		 */
		rp = XFS_ALLOC_REC_ADDR(block, 1, cur);
		memmove(&rp[ptr], &rp[ptr - 1],
			(INT_GET(block->bb_numrecs, ARCH_CONVERT) - ptr + 1) * sizeof(*rp));
		/*
		 * Now stuff the new record in, bump numrecs
		 * and log the new data.
		 */
		rp[ptr - 1] = *recp; /* INT_: struct copy */
		INT_MOD(block->bb_numrecs, ARCH_CONVERT, +1);
		xfs_alloc_log_recs(cur, bp, ptr, INT_GET(block->bb_numrecs, ARCH_CONVERT));
#ifdef DEBUG
		if (ptr < INT_GET(block->bb_numrecs, ARCH_CONVERT))
			xfs_btree_check_rec(cur->bc_btnum, rp + ptr - 1,
				rp + ptr);
#endif
	}
	/*
	 * Log the new number of records in the btree header.
	 */
	xfs_alloc_log_block(cur->bc_tp, bp, XFS_BB_NUMRECS);
	/*
	 * If we inserted at the start of a block, update the parents' keys.
	 */
	if (optr == 1 && (error = xfs_alloc_updkey(cur, &key, level + 1)))
		return error;
	/*
	 * Look to see if the longest extent in the allocation group
	 * needs to be updated.
	 */

	agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
	if (level == 0 &&
	    cur->bc_btnum == XFS_BTNUM_CNT &&
	    INT_GET(block->bb_rightsib, ARCH_CONVERT) == NULLAGBLOCK &&
	    INT_GET(recp->ar_blockcount, ARCH_CONVERT) > INT_GET(agf->agf_longest, ARCH_CONVERT)) {
		/*
		 * If this is a leaf in the by-size btree and there
		 * is no right sibling block and this block is bigger
		 * than the previous longest block, update it.
		 */
		INT_COPY(agf->agf_longest, recp->ar_blockcount, ARCH_CONVERT);
		cur->bc_mp->m_perag[INT_GET(agf->agf_seqno, ARCH_CONVERT)].pagf_longest
			= INT_GET(recp->ar_blockcount, ARCH_CONVERT);
		xfs_alloc_log_agf(cur->bc_tp, cur->bc_private.a.agbp,
			XFS_AGF_LONGEST);
	}
	/*
	 * Return the new block number, if any.
	 * If there is one, give back a record value and a cursor too.
	 */
	*bnop = nbno;
	if (nbno != NULLAGBLOCK) {
		*recp = nrec; /* INT_: struct copy */
		*curp = ncur; /* INT_: struct copy */
	}