btree test harness

Index: linux-2.6-xfs/fs/xfs/xfs_btree_test.c
===================================================================
@@ -0,0 +1,1283 @@
+/*
+ * Copyright (c) 2008 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_btree.h"
+#include "xfs_btree_trace.h"
+#include "xfs_ialloc.h"
+#include "xfs_alloc.h"
+#include "xfs_error.h"
+#include "xfs_trans_space.h"
+#include "xfs_rw.h"
+
+/*
+ * Btree test harness.
+ *
+ * The idea is we implement a btree not that we can freely excercise
+ * without the rest of the filesystem involed.  It basically mirrors
+ * the alloc by block number btree, just with a separate root block
+ * and dummy agf, and a "special" allocator.  The allocator here
+ * just takes over the whole allocation group from a start offset
+ * and uses a simple bitmap - that way we can stree the btree without
+ * having to call into the XFS allocator (and this another btree).
+ * This is of course very dangerous on a real live filesystem, but
+ * this code shouldn't be used on those anyway.
+ *
+ * Initially this is based on the alloc btree code because it is
+ * the simplest. Ideally this also needs to be expanded to handle
+ * inode rooted btrees and all the other features of the btrees
+ * (e.g. longest extent tracking).
+ *
+ * The test harness itself is at the bottom of the file. It
+ * gets invoked in a debug build on XFS initialisation, and
+ * when it is complete it is never referenced again.
+ *
+ * Test harness
+ *
+ * The following tests are necessary:
+ *
+ *	- split test
+ *	- merge test
+ *	- sparse tree test
+ *	- depth test
+ *
+ * Ideally the tests should grow and shrink the tree, thereby
+ * exercising root splitting and merging.
+ *
+ * what we need:
+ *
+ *	- a fake struct xfs_mount
+ *	- a fake struct xfs_trans
+ *	- a fake agf
+ *	- a fake agf struct xfs_buf
+ *	- special cursor init
+ */
+
+/* We need to start a little after 0 to avoid hardcoded assumptions */
+#define XFS_TBT_FIRST_FREE_BLOCK	8
+
+
+static unsigned long *xfs_tbt_allocmap;
+static size_t xfs_tbt_allomap_size;
+
+STATIC int
+xfs_tbt_init_freelist(
+	struct xfs_mount	*mp,
+	xfs_agnumber_t		agno)
+{
+	struct xfs_buf		*agbp;
+	struct xfs_agf		*agf;
+	int			error;
+	__uint32_t		freeblks, startblk;
+	int			i;
+
+	error = xfs_alloc_read_agf(mp, NULL, agno, 0, &agbp);
+	if (error || agbp == NULL) {
+		cmn_err(CE_WARN, "xfs_alloc_read_agf failed (%d).\n", error);
+		return error ? error : ENOMEM;
+	}
+
+	/*
+	 * See what the largest free space is and used for us.
+	 *
+	 * XXX(hch): this assumes it's clustered at the end..
+	 */
+	agf = XFS_BUF_TO_AGF(agbp);
+	freeblks = be32_to_cpu(agf->agf_longest);
+	startblk = be32_to_cpu(agf->agf_length) - freeblks;
+	xfs_buf_relse(agbp);
+
+	cmn_err(CE_NOTE, "%s: using %d blocks, starting at %d\n",
+			__func__, freeblks, startblk);
+
+	/* just us a simple bitmap array indexed by blockno */
+	xfs_tbt_allomap_size = freeblks / NBBY;
+	xfs_tbt_allocmap = kmalloc(xfs_tbt_allomap_size, GFP_KERNEL);
+	if (!xfs_tbt_allocmap) {
+		cmn_err(CE_WARN, "xfs_tbt_init_freelist: ENOMEM");
+		return ENOMEM;
+	}
+
+	memset(xfs_tbt_allocmap, 0xff, xfs_tbt_allomap_size); /* all free */
+	for (i = 0; i < startblk; i++)
+		clear_bit(i, xfs_tbt_allocmap);	/* except for used blocks */
+
+	return 0;
+}
+
+STATIC void
+xfs_tbt_destroy_freelist(
+	struct xfs_mount	*mp)
+{
+	kfree(xfs_tbt_allocmap);
+}
+
+STATIC int
+xfs_tbt_alloc(
+	xfs_agblock_t		*bnop)
+{
+	xfs_agblock_t		bno;
+	int			val;
+
+	bno = find_first_bit(xfs_tbt_allocmap,
+			xfs_tbt_allomap_size/sizeof(long));
+	if (bno >= xfs_tbt_allomap_size/sizeof(long)) {
+		cmn_err(CE_WARN, "%s: ran out of space\n", __func__);
+		return ENOSPC;
+	}
+
+	val = test_and_clear_bit(bno, xfs_tbt_allocmap);
+
+	ASSERT(val);
+	ASSERT(find_first_bit(xfs_tbt_allocmap,
+		xfs_tbt_allomap_size/sizeof(long)) > bno);
+	ASSERT(bno != NULLAGBLOCK);
+
+	*bnop = bno;
+	return 0;
+}
+
+STATIC int
+xfs_tbt_free(
+	xfs_agblock_t		bno)
+{
+	int			val;
+
+	ASSERT(bno <= xfs_tbt_allomap_size);
+
+	val = test_and_set_bit(bno, xfs_tbt_allocmap);
+	ASSERT(val == 0);
+
+	return 0;
+}
+
+STATIC int
+xfs_tbt_alloc_block(
+	struct xfs_btree_cur	*cur,
+	union xfs_btree_ptr	*start,
+	union xfs_btree_ptr	*new,
+	int			length,
+	int			*stat)
+{
+	xfs_agblock_t		bno;
+	int			error;
+
+	XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
+
+	error = xfs_tbt_alloc(&bno);
+	if (error) {
+		XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
+		return error;
+	}
+
+	new->s = cpu_to_be32(bno);
+
+	XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
+	*stat = 1;
+	return 0;
+}
+
+STATIC int
+xfs_tbt_free_block(
+	struct xfs_btree_cur	*cur,
+	struct xfs_buf		*bp)
+{
+	xfs_tbt_free(XFS_DADDR_TO_AGBNO(cur->bc_mp, XFS_BUF_ADDR(bp)));
+	return 0;
+}
+
+STATIC struct xfs_btree_cur *
+xfs_tbt_dup_cursor(
+	struct xfs_btree_cur	*cur)
+{
+	struct xfs_btree_cur	*new;
+
+	new = kmem_zone_zalloc(xfs_btree_cur_zone, KM_SLEEP);
+
+	new->bc_mp = cur->bc_mp;
+	new->bc_tp = cur->bc_tp;
+	new->bc_nlevels = cur->bc_nlevels;
+	new->bc_btnum = XFS_BTNUM_BNO;
+	new->bc_blocklog = cur->bc_mp->m_sb.sb_blocklog;
+
+	new->bc_ops = cur->bc_ops;
+
+	new->bc_private.a.agbp = cur->bc_private.a.agbp;
+	new->bc_private.a.agno = cur->bc_private.a.agno;
+
+	return new;
+}
+
+STATIC void
+xfs_tbt_set_root(
+	struct xfs_btree_cur	*cur,
+	union xfs_btree_ptr	*ptr,
+	int			inc)
+{
+	struct xfs_buf		*agbp = cur->bc_private.a.agbp;
+	struct xfs_agf		*agf = XFS_BUF_TO_AGF(agbp);
+	xfs_agnumber_t		seqno = be32_to_cpu(agf->agf_seqno);
+	int			btnum = cur->bc_btnum;
+
+	ASSERT(ptr->s != 0);
+
+	agf->agf_roots[btnum] = ptr->s;
+	be32_add_cpu(&agf->agf_levels[btnum], inc);
+	cur->bc_mp->m_perag[seqno].pagf_levels[btnum] += inc;
+}
+
+STATIC int
+xfs_tbt_get_minrecs(
+	struct xfs_btree_cur	*cur,
+	int			level)
+{
+	return cur->bc_mp->m_alloc_mnr[level != 0];
+}
+
+STATIC int
+xfs_tbt_get_maxrecs(
+	struct xfs_btree_cur	*cur,
+	int			level)
+{
+	return cur->bc_mp->m_alloc_mxr[level != 0];
+}
+
+STATIC void
+xfs_tbt_init_key_from_rec(
+	union xfs_btree_key	*key,
+	union xfs_btree_rec	*rec)
+{
+	key->alloc.ar_startblock = rec->alloc.ar_startblock;
+	key->alloc.ar_blockcount = rec->alloc.ar_blockcount;
+}
+
+STATIC void
+xfs_tbt_init_rec_from_key(
+	union xfs_btree_key	*key,
+	union xfs_btree_rec	*rec)
+{
+	rec->alloc.ar_startblock = key->alloc.ar_startblock;
+	rec->alloc.ar_blockcount = key->alloc.ar_blockcount;
+}
+
+STATIC void
+xfs_tbt_init_rec_from_cur(
+	struct xfs_btree_cur	*cur,
+	union xfs_btree_rec	*rec)
+{
+	rec->alloc.ar_startblock = cpu_to_be32(cur->bc_rec.a.ar_startblock);
+	rec->alloc.ar_blockcount = cpu_to_be32(cur->bc_rec.a.ar_blockcount);
+}
+
+STATIC void
+xfs_tbt_init_ptr_from_cur(
+	struct xfs_btree_cur	*cur,
+	union xfs_btree_ptr	*ptr)
+{
+	struct xfs_agf		*agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
+
+	ASSERT(cur->bc_private.a.agno == be32_to_cpu(agf->agf_seqno));
+	ASSERT(agf->agf_roots[cur->bc_btnum] != 0);
+
+	ptr->s = agf->agf_roots[cur->bc_btnum];
+}
+
+STATIC __int64_t
+xfs_tbt_key_diff(
+	struct xfs_btree_cur	*cur,
+	union xfs_btree_key	*key)
+{
+	xfs_alloc_rec_incore_t	*rec = &cur->bc_rec.a;
+	xfs_alloc_key_t		*kp = &key->alloc;
+
+	return (__int64_t)be32_to_cpu(kp->ar_startblock) - rec->ar_startblock;
+}
+
+STATIC int
+xfs_tbt_kill_root(
+	struct xfs_btree_cur	*cur,
+	struct xfs_buf		*bp,
+	int			level,
+	union xfs_btree_ptr	*newroot)
+{
+	int			error;
+
+	XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
+	XFS_BTREE_STATS_INC(cur, killroot);
+
+	/*
+	 * Update the root pointer, decreasing the level by 1 and then
+	 * free the old root.
+	 */
+	xfs_tbt_set_root(cur, newroot, -1);
+	error = xfs_tbt_free_block(cur, bp);
+	if (error) {
+		XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
+		return error;
+	}
+
+	XFS_BTREE_STATS_INC(cur, free);
+
+	xfs_btree_setbuf(cur, level, NULL);
+	cur->bc_nlevels--;
+
+	XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
+	return 0;
+}
+
+#ifdef DEBUG
+STATIC int
+xfs_tbt_keys_inorder(
+	struct xfs_btree_cur	*cur,
+	union xfs_btree_key	*k1,
+	union xfs_btree_key	*k2)
+{
+	return be32_to_cpu(k1->alloc.ar_startblock) <
+	       be32_to_cpu(k2->alloc.ar_startblock);
+}
+
+STATIC int
+xfs_tbt_recs_inorder(
+	struct xfs_btree_cur	*cur,
+	union xfs_btree_rec	*r1,
+	union xfs_btree_rec	*r2)
+{
+	return be32_to_cpu(r1->alloc.ar_startblock) +
+		be32_to_cpu(r1->alloc.ar_blockcount) <=
+		be32_to_cpu(r2->alloc.ar_startblock);
+}
+#endif	/* DEBUG */
+
+#ifdef XFS_BTREE_TRACE
+ktrace_t	*xfs_tbt_trace_buf;
+
+STATIC void
+xfs_tbt_trace_enter(
+	struct xfs_btree_cur	*cur,
+	const char		*func,
+	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)
+{
+	/* do nothing for now */
+}
+
+STATIC void
+xfs_tbt_trace_cursor(
+	struct xfs_btree_cur	*cur,
+	__uint32_t		*s0,
+	__uint64_t		*l0,
+	__uint64_t		*l1)
+{
+	*s0 = cur->bc_private.a.agno;
+	*l0 = cur->bc_rec.a.ar_startblock;
+	*l1 = cur->bc_rec.a.ar_blockcount;
+}
+
+STATIC void
+xfs_tbt_trace_key(
+	struct xfs_btree_cur	*cur,
+	union xfs_btree_key	*key,
+	__uint64_t		*l0,
+	__uint64_t		*l1)
+{
+	*l0 = be32_to_cpu(key->alloc.ar_startblock);
+	*l1 = be32_to_cpu(key->alloc.ar_blockcount);
+}
+
+STATIC void
+xfs_tbt_trace_record(
+	struct xfs_btree_cur	*cur,
+	union xfs_btree_rec	*rec,
+	__uint64_t		*l0,
+	__uint64_t		*l1,
+	__uint64_t		*l2)
+{
+	*l0 = be32_to_cpu(rec->alloc.ar_startblock);
+	*l1 = be32_to_cpu(rec->alloc.ar_blockcount);
+	*l2 = 0;
+}
+#endif /* XFS_BTREE_TRACE */
+
+static const struct xfs_btree_ops xfs_tbt_ops = {
+	.rec_len		= sizeof(xfs_alloc_rec_t),
+	.key_len		= sizeof(xfs_alloc_key_t),
+
+	.dup_cursor		= xfs_tbt_dup_cursor,
+	.set_root		= xfs_tbt_set_root,
+	.kill_root		= xfs_tbt_kill_root,
+	.alloc_block		= xfs_tbt_alloc_block,
+	.free_block		= xfs_tbt_free_block,
+	.get_minrecs		= xfs_tbt_get_minrecs,
+	.get_maxrecs		= xfs_tbt_get_maxrecs,
+	.init_key_from_rec	= xfs_tbt_init_key_from_rec,
+	.init_rec_from_key	= xfs_tbt_init_rec_from_key,
+	.init_rec_from_cur	= xfs_tbt_init_rec_from_cur,
+	.init_ptr_from_cur	= xfs_tbt_init_ptr_from_cur,
+	.key_diff		= xfs_tbt_key_diff,
+
+#ifdef DEBUG
+	.keys_inorder		= xfs_tbt_keys_inorder,
+	.recs_inorder		= xfs_tbt_recs_inorder,
+#endif
+
+#ifdef XFS_BTREE_TRACE
+	.trace_enter		= xfs_tbt_trace_enter,
+	.trace_cursor		= xfs_tbt_trace_cursor,
+	.trace_key		= xfs_tbt_trace_key,
+	.trace_record		= xfs_tbt_trace_record,
+#endif
+};
+
+/*
+ * Allocate a new allocation btree cursor.
+ */
+STATIC struct xfs_btree_cur *
+xfs_tbt_init_cursor(
+	struct xfs_mount	*mp,
+	xfs_agnumber_t		agno,
+	struct xfs_buf		*agbp)
+{
+	struct xfs_agf		*agf = XFS_BUF_TO_AGF(agbp);
+	struct xfs_btree_cur	*cur;
+	struct xfs_trans	*tp;
+	int			error;
+	uint			resblks;
+
+	resblks = XFS_DIOSTRAT_SPACE_RES(mp, 0) << 1;
+	tp = xfs_trans_alloc(mp, XFS_TRANS_STRAT_WRITE);
+	tp->t_flags |= XFS_TRANS_RESERVE;
+	error = xfs_trans_reserve(tp, resblks,
+			XFS_WRITE_LOG_RES(mp), 0,
+			XFS_TRANS_PERM_LOG_RES,
+			XFS_WRITE_LOG_COUNT);
+	if (error) {
+		xfs_trans_cancel(tp, 0);
+		return NULL;
+	}
+
+	cur = kmem_zone_zalloc(xfs_btree_cur_zone, KM_SLEEP);
+
+	cur->bc_mp = mp;
+	cur->bc_tp = tp;
+	cur->bc_nlevels = be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNO]);
+	cur->bc_btnum = XFS_BTNUM_BNO;
+	cur->bc_blocklog = mp->m_sb.sb_blocklog;
+
+	cur->bc_ops = &xfs_tbt_ops;
+
+	cur->bc_private.a.agbp = agbp;
+	cur->bc_private.a.agno = agno;
+
+	return cur;
+}
+
+/*
+ * Lookup the record equal to [bno, len] in the btree given by cur.
+ */
+STATIC int				/* error */
+xfs_tbt_lookup_eq(
+	struct xfs_btree_cur	*cur,	/* btree cursor */
+	xfs_agblock_t		bno,	/* starting block of extent */
+	xfs_extlen_t		len,	/* length of extent */
+	int			*stat)	/* success/failure */
+{
+	cur->bc_rec.a.ar_startblock = bno;
+	cur->bc_rec.a.ar_blockcount = len;
+	return xfs_btree_lookup(cur, XFS_LOOKUP_EQ, stat);
+}
+
+/*
+ * Lookup the first record greater than or equal to [bno, len]
+ * in the btree given by cur.
+ */
+STATIC int				/* error */
+xfs_tbt_lookup_ge(
+	struct xfs_btree_cur	*cur,	/* btree cursor */
+	xfs_agblock_t		bno,	/* starting block of extent */
+	xfs_extlen_t		len,	/* length of extent */
+	int			*stat)	/* success/failure */
+{
+	cur->bc_rec.a.ar_startblock = bno;
+	cur->bc_rec.a.ar_blockcount = len;
+	return xfs_btree_lookup(cur, XFS_LOOKUP_GE, stat);
+}
+
+/*
+ * Lookup the first record less than or equal to [bno, len]
+ * in the btree given by cur.
+ */
+STATIC int				/* error */
+xfs_tbt_lookup_le(
+	struct xfs_btree_cur	*cur,	/* btree cursor */
+	xfs_agblock_t		bno,	/* starting block of extent */
+	xfs_extlen_t		len,	/* length of extent */
+	int			*stat)	/* success/failure */
+{
+	cur->bc_rec.a.ar_startblock = bno;
+	cur->bc_rec.a.ar_blockcount = len;
+	return xfs_btree_lookup(cur, XFS_LOOKUP_LE, stat);
+}
+
+/*
+ * Update the record referred to by cur to the value given
+ * by [bno, len].
+ * This either works (return 0) or gets an EFSCORRUPTED error.
+ */
+STATIC int				/* error */
+xfs_tbt_update(
+	struct xfs_btree_cur	*cur,	/* btree cursor */
+	xfs_agblock_t		bno,	/* starting block of extent */
+	xfs_extlen_t		len)	/* length of extent */
+{
+	union xfs_btree_rec	rec;
+
+	rec.alloc.ar_startblock = cpu_to_be32(bno);
+	rec.alloc.ar_blockcount = cpu_to_be32(len);
+	return xfs_btree_update(cur, &rec);
+}
+
+/*
+ * Get the data from the pointed-to record.
+ */
+STATIC int				/* error */
+xfs_tbt_get_rec(
+	struct xfs_btree_cur	*cur,	/* btree cursor */
+	xfs_agblock_t		*bno,	/* output: starting block of extent */
+	xfs_extlen_t		*len,	/* output: length of extent */
+	int			*stat)	/* output: success/failure */
+{
+	union xfs_btree_rec	*rec;
+	int			error;
+
+	error = xfs_btree_get_rec(cur, &rec, stat);
+	if (!error && *stat == 1) {
+		*bno = be32_to_cpu(rec->alloc.ar_startblock);
+		*len = be32_to_cpu(rec->alloc.ar_blockcount);
+	}
+	return error;
+}
+
+STATIC int
+xfs_tbt_destroy_cursor(
+	struct xfs_btree_cur	*cur)
+{
+	struct xfs_trans	*tp = cur->bc_tp;
+
+	xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR);
+	return xfs_trans_commit(tp, XFS_TRANS_RELEASE_LOG_RES);
+}
+
+/*
+ * Build a full tree of the required depth of single block extents
+ * separated by a single block. We want discrete reecords to be
+ * built here.
+ *
+ * XXX: we probably want to create larger holes as well to be able
+ * to do more coverage on left and right merging and splitting.
+ * However, that is really a function of the specific implementation,
+ * not the core btree code which
+ */
+STATIC int
+xfs_tbt_build_sparse_tree(
+	struct xfs_mount	*mp,
+	xfs_agnumber_t		agno,
+	struct xfs_buf		*agbp,
+	int			levels)
+{
+	struct xfs_btree_cur	*cur;
+	int			i;
+	xfs_agblock_t		offset = XFS_TBT_FIRST_FREE_BLOCK;
+	xfs_extlen_t		len = 1;
+	struct xfs_agf		*agf;
+	int			error = 0, error2;
+
+	agf = XFS_BUF_TO_AGF(agbp);
+	while (be32_to_cpu(agf->agf_levels[0]) < levels) {
+		cur = xfs_tbt_init_cursor(mp, agno, agbp);
+		if (!cur)
+			return ENOMEM;
+
+		i = 0;
+		/* Check the extent does not exist */
+		error = xfs_tbt_lookup_eq(cur, offset, len, &i);
+		if (error) {
+			cmn_err(CE_ALERT, "%s: lookup error at offset %u (%d)",
+				__func__, offset, error);
+			goto out_error;
+		}
+		XFS_WANT_CORRUPTED_RETURN(i == 0);
+
+		/* Insert the extent */
+		cur->bc_rec.a.ar_startblock = offset;
+		cur->bc_rec.a.ar_blockcount = len;
+		i = 0;
+		error = xfs_btree_insert(cur, &i);
+		if (error) {
+			cmn_err(CE_ALERT, "%s: insert failed at offset %u (%d)",
+				__func__, offset, error);
+			goto out_error;
+		}
+		XFS_WANT_CORRUPTED_RETURN(i == 1);
+
+		/* keep a count of records in the tree */
+		be32_add_cpu(&agf->agf_spare0, 1);
+
+		/* move on to new extent */
+		offset += 2;
+
+out_error:
+		error2 = xfs_tbt_destroy_cursor(cur);
+		if (error2) {
+			cmn_err(CE_ALERT,
+				"%s: failed to commit transaction (%d)",
+				__func__, error);
+			if (!error)
+				error = error2;
+		}
+
+		if (error)
+			return error;
+	}
+
+	/* record largest offset added */
+	agf->agf_spare1 = cpu_to_be32(offset);
+	return error;
+}
+
+STATIC int
+xfs_tbt_empty_sparse_tree(
+	struct xfs_mount	*mp,
+	xfs_agnumber_t		agno,
+	struct xfs_buf		*agbp,
+	int			levels)
+{
+	int			error = 0, error2;
+	int			i;
+	struct xfs_btree_cur	*cur;
+	struct xfs_agf		*agf;
+
+	agf = XFS_BUF_TO_AGF(agbp);
+	while (be32_to_cpu(agf->agf_spare0) > 0) {
+		cur = xfs_tbt_init_cursor(mp, agno, agbp);
+		if (!cur)
+			return ENOMEM;
+		i = 0;
+
+		/* find the extent that spans this offset/len */
+		error = xfs_tbt_lookup_ge(cur, XFS_TBT_FIRST_FREE_BLOCK, 1, &i);
+		if (error) {
+			cmn_err(CE_ALERT, "%s: lookup error at offset %u (%d)",
+				__func__, XFS_TBT_FIRST_FREE_BLOCK, error);
+			goto out_error;
+		}
+		XFS_WANT_CORRUPTED_RETURN(i == 1);
+
+		error = xfs_btree_delete(cur, &i);
+		if (error) {
+			cmn_err(CE_ALERT, "%s: "
+				"%s error at offset %u (%d)",
+				__func__, "xfs_btree_delete",
+				XFS_TBT_FIRST_FREE_BLOCK, error);
+			goto out_error;
+		}
+		XFS_WANT_CORRUPTED_RETURN(i == 1);
+		be32_add_cpu(&agf->agf_spare0, -1);
+out_error:
+		error2 = xfs_tbt_destroy_cursor(cur);
+		if (error2) {
+			cmn_err(CE_ALERT,
+				"%s: failed to commit transaction (%d)",
+				__func__, error);
+			if (!error)
+				error = error2;
+		}
+
+		if (error)
+			return error;
+	}
+
+	return error;
+}
+
+/*
+ * Take a tree and punch alternate blocks out of it until it
+ * reaches the required depth. The will split records apart.
+ *
+ * Hacked out of xfs_tbt_fixup_trees()
+ */
+STATIC int
+xfs_tbt_punch_sparse_tree(
+	struct xfs_mount	*mp,
+	xfs_agnumber_t		agno,
+	struct xfs_buf		*agbp,
+	int			levels,
+	int			dir)
+{
+	int			error = 0, error2;
+	int			i;
+	xfs_agblock_t		fbno;
+	xfs_agblock_t		nfbno1;
+	xfs_agblock_t		nfbno2;
+	xfs_extlen_t		flen = 0;
+	xfs_extlen_t		nflen1 = 0;
+	xfs_extlen_t		nflen2 = 0;
+	xfs_agblock_t		offset;
+	xfs_extlen_t		len;
+	xfs_agblock_t		delta;
+	struct xfs_btree_cur	*cur;
+	struct xfs_agf		*agf;
+
+	agf = XFS_BUF_TO_AGF(agbp);
+
+	switch (dir) {
+	default:
+	case 0:	/* r to l */
+		offset = XFS_TBT_FIRST_FREE_BLOCK + 1;
+		len = 1;
+		delta = 2;
+		break;
+	case 1:	/* l to r */
+		offset = be32_to_cpu(agf->agf_spare1) - 3; // why??
+		len = 1;
+		delta = -2;
+		break;
+	case 2:	/* middle to r/l */
+		/* XXX: not implemented yet */
+		return 0;
+		break;
+	}
+
+	while (be32_to_cpu(agf->agf_levels[0]) < levels) {
+		cur = xfs_tbt_init_cursor(mp, agno, agbp);
+		if (!cur)
+			return ENOMEM;
+
+		i = 0;
+		/* find the extent that spans this offset/len */
+		error = xfs_tbt_lookup_le(cur, offset, 1, &i);
+		if (error) {
+			cmn_err(CE_ALERT, "%s: lookup error at offset %u (%d)",
+				__func__, offset, error);
+			goto out_error;
+		}
+		XFS_WANT_CORRUPTED_RETURN(i == 1);
+
+		/* get the range of the extent */
+		error = xfs_tbt_get_rec(cur, &fbno, &flen, &i);
+		if (error) {
+			cmn_err(CE_ALERT, "%s: get_rec error at offset %u (%d)",
+				__func__, offset, error);
+			goto out_error;
+		}
+		XFS_WANT_CORRUPTED_RETURN(i == 1 && fbno <= offset && flen >= len);
+
+		if (fbno == offset && flen == len)
+			/* just delete the record under the cursor */
+			nfbno1 = nfbno2 = NULLAGBLOCK;
+		else if (fbno == offset) {
+			/* punching out left edge */
+			nfbno1 = fbno + len;
+			nflen1 = flen - len;
+			nfbno2 = NULLAGBLOCK;
+		} else if (fbno + flen == offset + len) {
+			/* punching out right edge */
+			nfbno1 = fbno;
+			nflen1 = flen - len;
+			nfbno2 = NULLAGBLOCK;
+		} else {
+			/* punching out left and right edge */
+			nfbno1 = fbno;
+			nflen1 = offset - fbno;
+			nfbno2 = offset + len;
+			nflen2 = (fbno + flen) - nfbno2;
+		}
+
+		if (nfbno1 == NULLAGBLOCK) {
+			error = xfs_btree_delete(cur, &i);
+			if (error) {
+				cmn_err(CE_ALERT, "%s: "
+					"%s error at offset %u (%d)",
+					__func__, "xfs_btree_delete",
+					offset, error);
+				goto out_error;
+			}
+			XFS_WANT_CORRUPTED_RETURN(i == 1);
+			be32_add_cpu(&agf->agf_spare0, -1);
+		} else {
+			/*
+			 * Update the by-block entry to start later|be shorter.
+			 */
+			error = xfs_tbt_update(cur, nfbno1, nflen1);
+			if (error) {
+				cmn_err(CE_ALERT, "%s: "
+				"xfs_btree_update error at offset %u (%d)",
+				__func__, offset, error);
+				goto out_error;
+			}
+		}
+		if (nfbno2 != NULLAGBLOCK) {
+			/*
+			 * Need to add the second entry. Confirm it does not
+			 * exist first
+			 */
+			error = xfs_tbt_lookup_eq(cur, nfbno2, nflen2, &i);
+			if (error) {
+				cmn_err(CE_ALERT, "%s: "
+				"lookup equal error at nfbno2 %u (%d)",
+				__func__, nfbno2, error);
+				goto out_error;
+			}
+			XFS_WANT_CORRUPTED_RETURN(i == 0);
+			error = xfs_btree_insert(cur, &i);
+			if (error) {
+				cmn_err(CE_ALERT,
+					"%s: insert error at nfbno2 %u (%d)",
+					__func__, nfbno2, error);
+				goto out_error;
+			}
+			XFS_WANT_CORRUPTED_RETURN(i == 1);
+
+			/* keep a count of records in the tree */
+			be32_add_cpu(&agf->agf_spare0, 1);
+		}
+
+		/* move on to new extent */
+		offset += delta;
+
+out_error:
+		error2 = xfs_tbt_destroy_cursor(cur);
+		if (error2) {
+			cmn_err(CE_ALERT,
+				"%s: failed to commit transaction (%d)",
+				__func__, error);
+			if (!error)
+				error = error2;
+		}
+
+		if (error)
+			return error;
+	}
+
+	return error;
+}
+
+/*
+ * Take a sparse tree and fill the holes in it until there are
+ * no holes left. This requires finding the hole and it's adjacent
+ * extent(s) and updating extents in place and deleting old
+ * overlapping extents.
+ *
+ * XXX: only handles single extent holes in the tree
+ */
+STATIC int
+xfs_tbt_fill_sparse_tree(
+	struct xfs_mount	*mp,
+	xfs_agnumber_t		agno,
+	struct xfs_buf		*agbp,
+	int			levels,
+	int			dir)
+{
+	int			error = 0, error2;
+	int			i;
+	xfs_agblock_t		lbno;
+	xfs_agblock_t		rbno;
+	xfs_extlen_t		llen = 0;
+	xfs_extlen_t		rlen = 0;
+	xfs_agblock_t		offset;
+	xfs_extlen_t		len;
+	struct xfs_btree_cur	*cur;
+	struct xfs_agf		*agf;
+	int			delta;
+
+	agf = XFS_BUF_TO_AGF(agbp);
+
+	switch (dir) {
+	default:
+	case 0:	/* r to l */
+		offset = XFS_TBT_FIRST_FREE_BLOCK + 1;
+		len = 1;
+		delta = 2;
+		break;
+	case 1:	/* l to r */
+		offset = be32_to_cpu(agf->agf_spare1) - 3; // why??
+		len = 1;
+		delta = -2;
+		break;
+	case 2:	/* middle to r/l */
+		/* XXX: not implemented yet */
+		return 0;
+		break;
+	}
+
+	while (be32_to_cpu(agf->agf_spare0) > 1) {
+		cur = xfs_tbt_init_cursor(mp, agno, agbp);
+		if (!cur)
+			return ENOMEM;
+
+		/* are we in a hole? (should be) */
+		error = xfs_tbt_lookup_eq(cur, offset, len, &i);
+		if (error) {
+			cmn_err(CE_ALERT,
+				"%s: eqlookup error at offset %u (%d)",
+				__func__, offset, error);
+			goto out_error;
+		}
+		XFS_WANT_CORRUPTED_RETURN(i == 0);
+
+		/* find left neighbour */
+		error = xfs_tbt_lookup_le(cur, offset, len, &i);
+		if (error) {
+			cmn_err(CE_ALERT,
+				"%s: lelookup error at offset %u (%d)",
+				__func__, offset, error);
+			goto out_error;
+		}
+		XFS_WANT_CORRUPTED_RETURN(i == 1);
+
+		/* get the range of the extent */
+		error = xfs_tbt_get_rec(cur, &lbno, &llen, &i);
+		if (error) {
+			cmn_err(CE_ALERT,
+				"%s: leget_rec error at offset %u (%d)",
+				__func__, offset, error);
+			goto out_error;
+		}
+		XFS_WANT_CORRUPTED_RETURN(i == 1);
+
+		/* find right neighbour */
+		error = xfs_tbt_lookup_ge(cur, offset, len, &i);
+		if (error) {
+			cmn_err(CE_ALERT,
+				"%s: gelookup error at offset %u (%d)",
+				__func__, offset, error);
+			goto out_error;
+		}
+		XFS_WANT_CORRUPTED_RETURN(i == 1);
+
+		/* get the range of the extent */
+		error = xfs_tbt_get_rec(cur, &rbno, &rlen, &i);
+		if (error) {
+			cmn_err(CE_ALERT,
+				"%s: geget_rec error at offset %u (%d)",
+				__func__, offset, error);
+			goto out_error;
+		}
+		XFS_WANT_CORRUPTED_RETURN(i == 1);
+
+		error = EIO;
+		if (lbno + llen != offset) {
+			cmn_err(CE_ALERT,
+				"%s: left record not correct at %u (%u,%u)",
+				__func__, offset, lbno, llen);
+			goto out_error;
+		} else if (offset + len != rbno) {
+			cmn_err(CE_ALERT,
+				"%s: right record not correct at %u (%u,%u)",
+				__func__, offset, rbno, rlen);
+			goto out_error;
+		}
+
+		/*
+		 * fill hole: update one record, delete the other.
+		 * The cursor currently points at the right record,
+		 * so delete it and update the left record. Technically
+		 * this is correct as the index of the left record does
+		 * not change - only it's length
+		 */
+		llen = llen + len + rlen;
+		error = xfs_btree_delete(cur, &i);
+		if (error) {
+			cmn_err(CE_ALERT,
+				"%s: xfs_btree_delete error at offset %u (%d)",
+				__func__, rbno, error);
+			goto out_error;
+		}
+		XFS_WANT_CORRUPTED_RETURN(i == 1);
+		be32_add_cpu(&agf->agf_spare0, -1);
+
+		/* find left neighbour (again) */
+		error = xfs_tbt_lookup_le(cur, offset, len, &i);
+		if (error) {
+			cmn_err(CE_ALERT,
+				"%s: lelookup error at offset %u (%d)",
+				__func__, offset, error);
+			goto out_error;
+		}
+		XFS_WANT_CORRUPTED_RETURN(i == 1);
+
+		/* Update the left entry */
+		error = xfs_tbt_update(cur, lbno, llen);
+		if (error) {
+			cmn_err(CE_ALERT,
+				"%s: xfs_btree_update error at offset %u (%d)",
+				__func__, lbno, error);
+			goto out_error;
+		}
+
+		/* move on to new extent */
+		offset += delta;
+
+out_error:
+		error2 = xfs_tbt_destroy_cursor(cur);
+		if (error2) {
+			cmn_err(CE_ALERT,
+				"%s: failed to commit transaction (%d)",
+				__func__, error);
+			if (!error)
+				error = error2;
+		}
+
+		if (error)
+			return error;
+	}
+
+	return error;
+}
+
+STATIC int
+xfs_tbt_init_ag(
+	struct xfs_mount	*mp,
+	xfs_agnumber_t		agno,
+	xfs_agblock_t		*agbnop)
+{
+	xfs_extlen_t		agsize = mp->m_sb.sb_agblocks;
+	struct xfs_buf		*bp;
+	struct xfs_btree_block	*block;
+	struct xfs_alloc_rec	*arec;
+	xfs_agblock_t		agbno;
+	xfs_agblock_t		rbno;
+	int			error;
+	struct xfs_agf		*agf;
+
+	/* Allocate a btree root block */
+	error = xfs_tbt_alloc(&rbno);
+	if (error) {
+		printk("xfs_tbt_alloc failed\n");
+		return error;
+	}
+
+	bp = xfs_buf_get(mp->m_ddev_targp,
+			 XFS_AGB_TO_DADDR(mp, agno, rbno),
+			 BTOBB(mp->m_sb.sb_blocksize), 0);
+
+	block = XFS_BUF_TO_BLOCK(bp);
+	memset(block, 0, mp->m_sb.sb_blocksize);
+	block->bb_magic = cpu_to_be32(XFS_ABTB_MAGIC);
+	block->bb_level = 0;
+	block->bb_numrecs = cpu_to_be16(1);
+	block->bb_u.s.bb_leftsib = cpu_to_be32(NULLAGBLOCK);
+	block->bb_u.s.bb_rightsib = cpu_to_be32(NULLAGBLOCK);
+
+	arec = XFS_BTREE_REC_ADDR(xfs_alloc, block, 1);
+	arec->ar_startblock = cpu_to_be32(2); /* don't start at the beginning */
+	arec->ar_blockcount = cpu_to_be32(mp->m_sb.sb_agblocks -
+					  be32_to_cpu(arec->ar_startblock));
+
+	error = xfs_bwrite(mp, bp);
+	if (error)
+		return error;
+
+	/*
+	 * AG freelist header block
+	 */
+	error = xfs_tbt_alloc(&agbno);
+	if (error) {
+		printk("xfs_tbt_alloc failed\n");
+		return error;
+	}
+
+	bp = xfs_buf_get(mp->m_ddev_targp,
+			  XFS_AG_DADDR(mp, agno, agbno),
+			  XFS_FSS_TO_BB(mp, 1), 0);
+
+	agf = XFS_BUF_TO_AGF(bp);
+	memset(agf, 0, mp->m_sb.sb_sectsize);
+	agf->agf_magicnum = cpu_to_be32(XFS_AGF_MAGIC);
+	agf->agf_versionnum = cpu_to_be32(XFS_AGF_VERSION);
+	agf->agf_seqno = cpu_to_be32(agno);
+	agf->agf_length = cpu_to_be32(agsize);
+	agf->agf_roots[XFS_BTNUM_BNOi] = cpu_to_be32(rbno); //
+	agf->agf_roots[XFS_BTNUM_CNTi] = cpu_to_be32(rbno); //
+	agf->agf_levels[XFS_BTNUM_BNOi] = cpu_to_be32(1);
+	agf->agf_levels[XFS_BTNUM_CNTi] = cpu_to_be32(1);
+	agf->agf_flfirst = 0;
+	agf->agf_fllast = cpu_to_be32(XFS_AGFL_SIZE(mp) - 1);
+	agf->agf_flcount = 0;
+	/* don't start at the beginning */
+	agf->agf_freeblks = cpu_to_be32(agsize - 2);
+	agf->agf_longest = cpu_to_be32(agsize - 2);
+
+	error = xfs_bwrite(mp, bp);
+	if (error)
+		return error;
+
+	*agbnop = agbno;
+	return 0;
+}
+
+STATIC int
+xfs_tbt_read_agf(
+	struct xfs_mount	*mp,
+	struct xfs_trans	*tp,
+	xfs_agnumber_t		agno,
+	xfs_agblock_t		agbno,
+	struct xfs_buf		**bpp)
+{
+	int			error;
+
+	ASSERT(agno != NULLAGNUMBER);
+	error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp,
+			XFS_AG_DADDR(mp, agno, agbno),
+			XFS_FSS_TO_BB(mp, 1), 0, bpp);
+	if (error)
+		return error;
+
+	ASSERT(*bpp);
+	ASSERT(!XFS_BUF_GETERROR(*bpp));
+	return 0;
+}
+
+int
+xfs_tbt_test_one(
+	struct xfs_mount	*mp,
+	xfs_agnumber_t		agno,
+	int			levels)
+{
+	struct xfs_buf		*agbp = NULL;
+	int			error;
+	xfs_agblock_t		agbno;
+
+	if (levels > XFS_AG_MAXLEVELS(mp)) {
+		cmn_err(CE_WARN, "filesystem only supports %d btree levels\n",
+				 XFS_AG_MAXLEVELS(mp));
+		return -EINVAL;
+	}
+
+	cmn_err(CE_NOTE, "xfs_tbt_test_all: Testing %d levels", levels);
+
+	error = xfs_tbt_init_freelist(mp, agno);
+	if (error) {
+		cmn_err(CE_WARN, "xfs_tbt_init_freelist failed (%d).\n", error);
+		goto out;
+	}
+
+	error = xfs_tbt_init_ag(mp, agno, &agbno);
+	if (error) {
+		cmn_err(CE_WARN, "xfs_tbt_init_ag failed (%d).\n", error);
+		goto out_free_freelist;
+	}
+
+	error = xfs_tbt_read_agf(mp, NULL, agno, agbno, &agbp);
+	if (error || agbp == NULL) {
+		cmn_err(CE_WARN, "xfs_alloc_read_agf failed (%d).\n", error);
+		goto out_free_ag;
+	}
+
+
+	error = xfs_tbt_build_sparse_tree(mp, agno, agbp, levels);
+	if (error)
+		goto out_free_ag;
+	error = xfs_tbt_fill_sparse_tree(mp, agno, agbp, levels,
+					 0 /* left to right */);
+	if (error)
+		goto out_free_ag;
+	error = xfs_tbt_punch_sparse_tree(mp, agno, agbp, levels,
+					  0 /* l to r */);
+	if (error)
+		goto out_free_ag;
+	error = xfs_tbt_fill_sparse_tree(mp, agno, agbp, levels,
+					 1 /* r to l */);
+	if (error)
+		goto out_free_ag;
+	error = xfs_tbt_punch_sparse_tree(mp, agno, agbp, levels,
+					  1 /* r to l */);
+	if (error)
+		goto out_free_ag;
+#ifdef notyet
+	error = xfs_tbt_fill_sparse_tree(mp, agno, agbp, levels,
+					 2 /* middle to r/l */);
+	if (error)
+		goto out_free_ag;
+	error = xfs_tbt_punch_sparse_tree(mp, agno, agbp, levels,
+					  2 /* middle to r/l */);
+	if (error)
+		goto out_free_ag;
+#endif
+
+	error = xfs_tbt_empty_sparse_tree(mp, agno, agbp, levels);
+	if (error)
+		goto out_free_ag;
+
+	cmn_err(CE_NOTE, "xfs_tbt_test_all: Tested %d levels OK", levels);
+
+ out_free_ag:
+ 	xfs_buf_relse(agbp);
+ out_free_freelist:
+	xfs_tbt_destroy_freelist(mp);
+ out:
+ 	if (error) {
+		cmn_err(CE_WARN,
+			"xfs_tbt_test_all: fail with error %d\n", error);
+		return error;
+	}
+	cmn_err(CE_NOTE, "xfs_tbt_test_all: passed successfully\n");
+	return 0;
+}
+
+int
+xfs_ioc_test_btree(
+	struct xfs_mount	*mp,
+	void __user		*argp)
+{
+	struct xfs_ioc_test_btree tb;
+
+	if (copy_from_user(&tb, argp, sizeof(tb)))
+		return -EFAULT;
+	if (tb.flags != 0)
+		return -EINVAL;
+	return xfs_tbt_test_one(mp, tb.agno, tb.levels);
+}

Index: linux-2.6-xfs/fs/xfs/linux-2.6/xfs_ioctl.c
===================================================================
@@ -1578,7 +1578,13 @@ xfs_ioctl(
 
 		error = xfs_errortag_clearall(mp, 1);
 		return -error;
+#ifdef DEBUG
+	case XFS_IOC_TEST_BTREE:
+		if (!capable(CAP_SYS_ADMIN))
+			return -EPERM;
 
+		return xfs_ioc_test_btree(mp, (void __user *)arg);
+#endif
 	default:
 		return -ENOTTY;
 	}

Index: linux-2.6-xfs/fs/xfs/linux-2.6/xfs_lrw.h
===================================================================
@@ -74,4 +74,6 @@ extern int xfs_dev_is_read_only(struct x
 
 extern int xfs_zero_eof(struct xfs_inode *, xfs_off_t, xfs_fsize_t);
 
+extern int xfs_ioc_test_btree(struct xfs_mount *, void __user *);
+
 #endif	/* __XFS_LRW_H__ */

Index: linux-2.6-xfs/fs/xfs/xfs_fs.h
===================================================================
@@ -421,6 +421,15 @@ typedef struct xfs_handle {
 #define XFS_FSOP_GOING_FLAGS_NOLOGFLUSH		0x2	/* don't flush log nor data */
 
 /*
+ * Arguments for the btree test suite (debug builds only).
+ */
+struct xfs_ioc_test_btree {
+	__u32		agno;
+	__u32		levels;
+	__u32		flags;
+};
+
+/*
  * ioctl commands that are used by Linux filesystems
  */
 #define XFS_IOC_GETXFLAGS	FS_IOC_GETFLAGS

@@ -485,6 +494,7 @@ typedef struct xfs_handle {
 #define XFS_IOC_FSGEOMETRY	     _IOR ('X', 124, struct xfs_fsop_geom)
 #define XFS_IOC_GOINGDOWN	     _IOR ('X', 125, __uint32_t)
 /*	XFS_IOC_GETFSUUID ---------- deprecated 140	 */
+#define XFS_IOC_TEST_BTREE	     _IOW ('X', 126, struct xfs_ioc_test_btree)
 
 
 #ifndef HAVE_BBMACROS

48 lines not on this page · raw message