xfs_bmap_btree.c

linux 内核源代码

/*
 * Copyright (c) 2000-2003,2005 Silicon Graphics, Inc.
 * All Rights Reserved.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms 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.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write the Free Software Foundation,
 * Inc.,  51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 */
#include "xfs.h"
#include "xfs_fs.h"
#include "xfs_types.h"
#include "xfs_bit.h"
#include "xfs_log.h"
#include "xfs_inum.h"
#include "xfs_trans.h"
#include "xfs_sb.h"
#include "xfs_ag.h"
#include "xfs_dir2.h"
#include "xfs_dmapi.h"
#include "xfs_mount.h"
#include "xfs_bmap_btree.h"
#include "xfs_alloc_btree.h"
#include "xfs_ialloc_btree.h"
#include "xfs_dir2_sf.h"
#include "xfs_attr_sf.h"
#include "xfs_dinode.h"
#include "xfs_inode.h"
#include "xfs_inode_item.h"
#include "xfs_alloc.h"
#include "xfs_btree.h"
#include "xfs_ialloc.h"
#include "xfs_itable.h"
#include "xfs_bmap.h"
#include "xfs_error.h"
#include "xfs_quota.h"

#if defined(XFS_BMBT_TRACE)
ktrace_t	*xfs_bmbt_trace_buf;
#endif

/*
 * Prototypes for internal btree functions.
 */


STATIC int xfs_bmbt_killroot(xfs_btree_cur_t *);
STATIC void xfs_bmbt_log_keys(xfs_btree_cur_t *, xfs_buf_t *, int, int);
STATIC void xfs_bmbt_log_ptrs(xfs_btree_cur_t *, xfs_buf_t *, int, int);
STATIC int xfs_bmbt_lshift(xfs_btree_cur_t *, int, int *);
STATIC int xfs_bmbt_rshift(xfs_btree_cur_t *, int, int *);
STATIC int xfs_bmbt_split(xfs_btree_cur_t *, int, xfs_fsblock_t *,
		__uint64_t *, xfs_btree_cur_t **, int *);
STATIC int xfs_bmbt_updkey(xfs_btree_cur_t *, xfs_bmbt_key_t *, int);


#if defined(XFS_BMBT_TRACE)

static char	ARGS[] = "args";
static char	ENTRY[] = "entry";
static char	ERROR[] = "error";
#undef EXIT
static char	EXIT[] = "exit";

/*
 * Add a trace buffer entry for the arguments given to the routine,
 * generic form.
 */
STATIC void
xfs_bmbt_trace_enter(
	const char	*func,
	xfs_btree_cur_t	*cur,
	char		*s,
	int		type,
	int		line,
	__psunsigned_t	a0,
	__psunsigned_t	a1,
	__psunsigned_t	a2,
	__psunsigned_t	a3,
	__psunsigned_t	a4,
	__psunsigned_t	a5,
	__psunsigned_t	a6,
	__psunsigned_t	a7,
	__psunsigned_t	a8,
	__psunsigned_t	a9,
	__psunsigned_t	a10)
{
	xfs_inode_t	*ip;
	int		whichfork;

	ip = cur->bc_private.b.ip;
	whichfork = cur->bc_private.b.whichfork;
	ktrace_enter(xfs_bmbt_trace_buf,
		(void *)((__psint_t)type | (whichfork << 8) | (line << 16)),
		(void *)func, (void *)s, (void *)ip, (void *)cur,
		(void *)a0, (void *)a1, (void *)a2, (void *)a3,
		(void *)a4, (void *)a5, (void *)a6, (void *)a7,
		(void *)a8, (void *)a9, (void *)a10);
	ASSERT(ip->i_btrace);
	ktrace_enter(ip->i_btrace,
		(void *)((__psint_t)type | (whichfork << 8) | (line << 16)),
		(void *)func, (void *)s, (void *)ip, (void *)cur,
		(void *)a0, (void *)a1, (void *)a2, (void *)a3,
		(void *)a4, (void *)a5, (void *)a6, (void *)a7,
		(void *)a8, (void *)a9, (void *)a10);
}
/*
 * Add a trace buffer entry for arguments, for a buffer & 1 integer arg.
 */
STATIC void
xfs_bmbt_trace_argbi(
	const char	*func,
	xfs_btree_cur_t	*cur,
	xfs_buf_t	*b,
	int		i,
	int		line)
{
	xfs_bmbt_trace_enter(func, cur, ARGS, XFS_BMBT_KTRACE_ARGBI, line,
		(__psunsigned_t)b, i, 0, 0,
		0, 0, 0, 0,
		0, 0, 0);
}

/*
 * Add a trace buffer entry for arguments, for a buffer & 2 integer args.
 */
STATIC void
xfs_bmbt_trace_argbii(
	const char	*func,
	xfs_btree_cur_t	*cur,
	xfs_buf_t	*b,
	int		i0,
	int		i1,
	int		line)
{
	xfs_bmbt_trace_enter(func, cur, ARGS, XFS_BMBT_KTRACE_ARGBII, line,
		(__psunsigned_t)b, i0, i1, 0,
		0, 0, 0, 0,
		0, 0, 0);
}

/*
 * Add a trace buffer entry for arguments, for 3 block-length args
 * and an integer arg.
 */
STATIC void
xfs_bmbt_trace_argfffi(
	const char		*func,
	xfs_btree_cur_t		*cur,
	xfs_dfiloff_t		o,
	xfs_dfsbno_t		b,
	xfs_dfilblks_t		i,
	int			j,
	int			line)
{
	xfs_bmbt_trace_enter(func, cur, ARGS, XFS_BMBT_KTRACE_ARGFFFI, line,
		o >> 32, (int)o, b >> 32, (int)b,
		i >> 32, (int)i, (int)j, 0,
		0, 0, 0);
}

/*
 * Add a trace buffer entry for arguments, for one integer arg.
 */
STATIC void
xfs_bmbt_trace_argi(
	const char	*func,
	xfs_btree_cur_t	*cur,
	int		i,
	int		line)
{
	xfs_bmbt_trace_enter(func, cur, ARGS, XFS_BMBT_KTRACE_ARGI, line,
		i, 0, 0, 0,
		0, 0, 0, 0,
		0, 0, 0);
}

/*
 * Add a trace buffer entry for arguments, for int, fsblock, key.
 */
STATIC void
xfs_bmbt_trace_argifk(
	const char		*func,
	xfs_btree_cur_t		*cur,
	int			i,
	xfs_fsblock_t		f,
	xfs_dfiloff_t		o,
	int			line)
{
	xfs_bmbt_trace_enter(func, cur, ARGS, XFS_BMBT_KTRACE_ARGIFK, line,
		i, (xfs_dfsbno_t)f >> 32, (int)f, o >> 32,
		(int)o, 0, 0, 0,
		0, 0, 0);
}

/*
 * Add a trace buffer entry for arguments, for int, fsblock, rec.
 */
STATIC void
xfs_bmbt_trace_argifr(
	const char		*func,
	xfs_btree_cur_t		*cur,
	int			i,
	xfs_fsblock_t		f,
	xfs_bmbt_rec_t		*r,
	int			line)
{
	xfs_dfsbno_t		b;
	xfs_dfilblks_t		c;
	xfs_dfsbno_t		d;
	xfs_dfiloff_t		o;
	xfs_bmbt_irec_t		s;

	d = (xfs_dfsbno_t)f;
	xfs_bmbt_disk_get_all(r, &s);
	o = (xfs_dfiloff_t)s.br_startoff;
	b = (xfs_dfsbno_t)s.br_startblock;
	c = s.br_blockcount;
	xfs_bmbt_trace_enter(func, cur, ARGS, XFS_BMBT_KTRACE_ARGIFR, line,
		i, d >> 32, (int)d, o >> 32,
		(int)o, b >> 32, (int)b, c >> 32,
		(int)c, 0, 0);
}

/*
 * Add a trace buffer entry for arguments, for int, key.
 */
STATIC void
xfs_bmbt_trace_argik(
	const char		*func,
	xfs_btree_cur_t		*cur,
	int			i,
	xfs_bmbt_key_t		*k,
	int			line)
{
	xfs_dfiloff_t		o;

	o = be64_to_cpu(k->br_startoff);
	xfs_bmbt_trace_enter(func, cur, ARGS, XFS_BMBT_KTRACE_ARGIFK, line,
		i, o >> 32, (int)o, 0,
		0, 0, 0, 0,
		0, 0, 0);
}

/*
 * Add a trace buffer entry for the cursor/operation.
 */
STATIC void
xfs_bmbt_trace_cursor(
	const char	*func,
	xfs_btree_cur_t	*cur,
	char		*s,
	int		line)
{
	xfs_bmbt_rec_host_t	r;

	xfs_bmbt_set_all(&r, &cur->bc_rec.b);
	xfs_bmbt_trace_enter(func, cur, s, XFS_BMBT_KTRACE_CUR, line,
		(cur->bc_nlevels << 24) | (cur->bc_private.b.flags << 16) |
		cur->bc_private.b.allocated,
		r.l0 >> 32, (int)r.l0,
		r.l1 >> 32, (int)r.l1,
		(unsigned long)cur->bc_bufs[0], (unsigned long)cur->bc_bufs[1],
		(unsigned long)cur->bc_bufs[2], (unsigned long)cur->bc_bufs[3],
		(cur->bc_ptrs[0] << 16) | cur->bc_ptrs[1],
		(cur->bc_ptrs[2] << 16) | cur->bc_ptrs[3]);
}

#define	XFS_BMBT_TRACE_ARGBI(c,b,i)	\
	xfs_bmbt_trace_argbi(__FUNCTION__, c, b, i, __LINE__)
#define	XFS_BMBT_TRACE_ARGBII(c,b,i,j)	\
	xfs_bmbt_trace_argbii(__FUNCTION__, c, b, i, j, __LINE__)
#define	XFS_BMBT_TRACE_ARGFFFI(c,o,b,i,j)	\
	xfs_bmbt_trace_argfffi(__FUNCTION__, c, o, b, i, j, __LINE__)
#define	XFS_BMBT_TRACE_ARGI(c,i)	\
	xfs_bmbt_trace_argi(__FUNCTION__, c, i, __LINE__)
#define	XFS_BMBT_TRACE_ARGIFK(c,i,f,s)	\
	xfs_bmbt_trace_argifk(__FUNCTION__, c, i, f, s, __LINE__)
#define	XFS_BMBT_TRACE_ARGIFR(c,i,f,r)	\
	xfs_bmbt_trace_argifr(__FUNCTION__, c, i, f, r, __LINE__)
#define	XFS_BMBT_TRACE_ARGIK(c,i,k)	\
	xfs_bmbt_trace_argik(__FUNCTION__, c, i, k, __LINE__)
#define	XFS_BMBT_TRACE_CURSOR(c,s)	\
	xfs_bmbt_trace_cursor(__FUNCTION__, c, s, __LINE__)
#else
#define	XFS_BMBT_TRACE_ARGBI(c,b,i)
#define	XFS_BMBT_TRACE_ARGBII(c,b,i,j)
#define	XFS_BMBT_TRACE_ARGFFFI(c,o,b,i,j)
#define	XFS_BMBT_TRACE_ARGI(c,i)
#define	XFS_BMBT_TRACE_ARGIFK(c,i,f,s)
#define	XFS_BMBT_TRACE_ARGIFR(c,i,f,r)
#define	XFS_BMBT_TRACE_ARGIK(c,i,k)
#define	XFS_BMBT_TRACE_CURSOR(c,s)
#endif	/* XFS_BMBT_TRACE */


/*
 * Internal functions.
 */

/*
 * Delete record pointed to by cur/level.
 */
STATIC int					/* error */
xfs_bmbt_delrec(
	xfs_btree_cur_t		*cur,
	int			level,
	int			*stat)		/* success/failure */
{
	xfs_bmbt_block_t	*block;		/* bmap btree block */
	xfs_fsblock_t		bno;		/* fs-relative block number */
	xfs_buf_t		*bp;		/* buffer for block */
	int			error;		/* error return value */
	int			i;		/* loop counter */
	int			j;		/* temp state */
	xfs_bmbt_key_t		key;		/* bmap btree key */
	xfs_bmbt_key_t		*kp=NULL;	/* pointer to bmap btree key */
	xfs_fsblock_t		lbno;		/* left sibling block number */
	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 */
	int			lrecs=0;	/* left record count */
	xfs_bmbt_rec_t		*lrp;		/* left record pointer */
	xfs_mount_t		*mp;		/* file system mount point */
	xfs_bmbt_ptr_t		*pp;		/* pointer to bmap block addr */
	int			ptr;		/* key/record index */
	xfs_fsblock_t		rbno;		/* right sibling block number */
	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_rec_t		*rp;		/* pointer to bmap btree rec */
	xfs_bmbt_ptr_t		*rpp;		/* right address pointer */
	xfs_bmbt_block_t	*rrblock;	/* right-right btree block */
	xfs_buf_t		*rrbp;		/* right-right buffer pointer */
	int			rrecs=0;	/* right record count */
	xfs_bmbt_rec_t		*rrp;		/* right record pointer */
	xfs_btree_cur_t		*tcur;		/* temporary btree cursor */
	int			numrecs;	/* temporary numrec count */
	int			numlrecs, numrrecs;

	XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
	XFS_BMBT_TRACE_ARGI(cur, level);
	ptr = cur->bc_ptrs[level];
	tcur = NULL;
	if (ptr == 0) {
		XFS_BMBT_TRACE_CURSOR(cur, EXIT);
		*stat = 0;
		return 0;
	}
	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);
		goto error0;
	}
#endif
	if (ptr > numrecs) {
		XFS_BMBT_TRACE_CURSOR(cur, EXIT);
		*stat = 0;
		return 0;
	}
	XFS_STATS_INC(xs_bmbt_delrec);
	if (level > 0) {
		kp = XFS_BMAP_KEY_IADDR(block, 1, cur);
		pp = XFS_BMAP_PTR_IADDR(block, 1, cur);
#ifdef DEBUG
		for (i = ptr; i < numrecs; i++) {
			if ((error = xfs_btree_check_lptr_disk(cur, pp[i], level))) {
				XFS_BMBT_TRACE_CURSOR(cur, ERROR);
				goto error0;
			}
		}
#endif
		if (ptr < numrecs) {
			memmove(&kp[ptr - 1], &kp[ptr],
				(numrecs - ptr) * sizeof(*kp));
			memmove(&pp[ptr - 1], &pp[ptr],
				(numrecs - ptr) * sizeof(*pp));
			xfs_bmbt_log_ptrs(cur, bp, ptr, numrecs - 1);
			xfs_bmbt_log_keys(cur, bp, ptr, numrecs - 1);
		}
	} else {
		rp = XFS_BMAP_REC_IADDR(block, 1, cur);
		if (ptr < numrecs) {
			memmove(&rp[ptr - 1], &rp[ptr],
				(numrecs - ptr) * sizeof(*rp));
			xfs_bmbt_log_recs(cur, bp, ptr, numrecs - 1);
		}
		if (ptr == 1) {
			key.br_startoff =
				cpu_to_be64(xfs_bmbt_disk_get_startoff(rp));
			kp = &key;
		}
	}
	numrecs--;
	block->bb_numrecs = cpu_to_be16(numrecs);
	xfs_bmbt_log_block(cur, bp, XFS_BB_NUMRECS);
	/*
	 * We're at the root level.
	 * First, shrink the root block in-memory.
	 * Try to get rid of the next level down.
	 * If we can't then there's nothing left to do.
	 */
	if (level == cur->bc_nlevels - 1) {
		xfs_iroot_realloc(cur->bc_private.b.ip, -1,
			cur->bc_private.b.whichfork);
		if ((error = xfs_bmbt_killroot(cur))) {
			XFS_BMBT_TRACE_CURSOR(cur, ERROR);
			goto error0;
		}
		if (level > 0 && (error = xfs_bmbt_decrement(cur, level, &j))) {
			XFS_BMBT_TRACE_CURSOR(cur, ERROR);
			goto error0;
		}
		XFS_BMBT_TRACE_CURSOR(cur, EXIT);
		*stat = 1;
		return 0;
	}
	if (ptr == 1 && (error = xfs_bmbt_updkey(cur, kp, level + 1))) {
		XFS_BMBT_TRACE_CURSOR(cur, ERROR);
		goto error0;
	}
	if (numrecs >= XFS_BMAP_BLOCK_IMINRECS(level, cur)) {
		if (level > 0 && (error = xfs_bmbt_decrement(cur, level, &j))) {
			XFS_BMBT_TRACE_CURSOR(cur, ERROR);
			goto error0;
		}
		XFS_BMBT_TRACE_CURSOR(cur, EXIT);
		*stat = 1;
		return 0;
	}
	rbno = be64_to_cpu(block->bb_rightsib);
	lbno = be64_to_cpu(block->bb_leftsib);
	/*
	 * One child of root, need to get a chance to copy its contents
	 * into the root and delete it. Can't go up to next level,
	 * there's nothing to delete there.
	 */
	if (lbno == NULLFSBLOCK && rbno == NULLFSBLOCK &&
	    level == cur->bc_nlevels - 2) {
		if ((error = xfs_bmbt_killroot(cur))) {
			XFS_BMBT_TRACE_CURSOR(cur, ERROR);
			goto error0;
		}
		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;
	}
	ASSERT(rbno != NULLFSBLOCK || lbno != NULLFSBLOCK);
	if ((error = xfs_btree_dup_cursor(cur, &tcur))) {
		XFS_BMBT_TRACE_CURSOR(cur, ERROR);
		goto error0;
	}
	bno = NULLFSBLOCK;
	if (rbno != NULLFSBLOCK) {
		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(cur, ERROR);
			goto error0;
		}