[PATCH 15/21] implement generic xfs_btree_rshift

[PATCH 15/21] implement generic xfs_btree_rshift

[Christoph Hellwig]

[-- Attachment #1: xfs-common-btree-rshift --]
[-- Type: text/plain, Size: 33898 bytes --]

Make the btree right shift code generic.  Based on a patch from David Chinner
with lots of changes to follow the original btree implementations more
closely.  While this loses some of the generic helper routines for
inserting/moving/removing records it also solves some of the one off
bugs in the original code and makes it easier to verify.

Signed-off-by: Christoph Hellwig <hch@lst.de>


Index: linux-2.6-xfs/fs/xfs/xfs_btree.c
===================================================================
--- linux-2.6-xfs.orig/fs/xfs/xfs_btree.c	2008-07-27 17:40:52.000000000 +0200
+++ linux-2.6-xfs/fs/xfs/xfs_btree.c	2008-07-28 16:13:33.000000000 +0200
@@ -34,6 +34,7 @@
 #include "xfs_attr_sf.h"
 #include "xfs_dinode.h"
 #include "xfs_inode.h"
+#include "xfs_inode_item.h"
 #include "xfs_btree.h"
 #include "xfs_btree_trace.h"
 #include "xfs_ialloc.h"
@@ -952,6 +953,123 @@ xfs_btree_read_buf_block(
 	return xfs_btree_check_block(cur, *block, level, *bpp);
 }
 
+STATIC void
+xfs_btree_move_ptrs(
+	struct xfs_btree_cur	*cur,
+	union xfs_btree_ptr	*base,
+	int			from,
+	int			to,
+	int			numptrs)
+{
+	ASSERT(from >= 0 && from <= 1000);
+	ASSERT(to >= 0 && to <= 1000);
+	ASSERT(numptrs >= 0);
+
+	if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
+		__be64		*lpp = &base->l;
+
+		memmove(&lpp[to], &lpp[from], numptrs * sizeof(*lpp));
+	} else {
+		__be32		*spp = &base->s;
+
+		memmove(&spp[to], &spp[from], numptrs * sizeof(*spp));
+	}
+}
+
+/*
+ * Log block pointer fields from a btree block (nonleaf).
+ */
+STATIC void
+xfs_btree_log_ptrs(
+	struct xfs_btree_cur	*cur,	/* btree cursor */
+	struct xfs_buf		*bp,	/* buffer containing btree block */
+	int			pfirst,	/* index of first pointer to log */
+	int			plast)	/* index of last pointer to log */
+{
+
+	XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
+	XFS_BTREE_TRACE_ARGBII(cur, bp, pfirst, plast);
+
+	if (bp) {
+		struct xfs_btree_block	*block = XFS_BUF_TO_BLOCK(bp);
+		union xfs_btree_ptr	*pp;
+		int			first;	/* first byte offset logged */
+		int			last;	/* last byte offset logged */
+
+		pp = cur->bc_ops->ptr_addr(cur, 1, block);
+
+		if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
+			__be64		*lpp = &pp->l;
+
+			first = (int)((xfs_caddr_t)&lpp[pfirst - 1] -
+					(xfs_caddr_t)block);
+			last = (int)(((xfs_caddr_t)&lpp[plast] - 1) -
+					(xfs_caddr_t)block);
+		} else {
+			__be32		*spp = &pp->s;
+
+			first = (int)((xfs_caddr_t)&spp[pfirst - 1] -
+					(xfs_caddr_t)block);
+			last = (int)(((xfs_caddr_t)&spp[plast] - 1) -
+					(xfs_caddr_t)block);
+		}
+
+		xfs_trans_log_buf(cur->bc_tp, bp, first, last);
+	} else {
+		xfs_trans_log_inode(cur->bc_tp, cur->bc_private.b.ip,
+			XFS_ILOG_FBROOT(cur->bc_private.b.whichfork));
+	}
+
+	XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
+}
+
+/*
+ * Log fields from the short from btree block header.
+ */
+STATIC void
+xfs_btree_log_block(
+	struct xfs_btree_cur	*cur,	/* btree cursor */
+	struct xfs_buf		*bp,	/* buffer containing btree block */
+	int			fields)	/* mask of fields: XFS_BB_... */
+{
+	int			first;	/* first byte offset logged */
+	int			last;	/* last byte offset logged */
+	static const short	soffsets[] = {	/* table of offsets (short) */
+		offsetof(struct xfs_btree_sblock, bb_magic),
+		offsetof(struct xfs_btree_sblock, bb_level),
+		offsetof(struct xfs_btree_sblock, bb_numrecs),
+		offsetof(struct xfs_btree_sblock, bb_leftsib),
+		offsetof(struct xfs_btree_sblock, bb_rightsib),
+		sizeof(struct xfs_btree_sblock)
+	};
+	static const short	loffsets[] = {	/* table of offsets (long) */
+		offsetof(struct xfs_btree_lblock, bb_magic),
+		offsetof(struct xfs_btree_lblock, bb_level),
+		offsetof(struct xfs_btree_lblock, bb_numrecs),
+		offsetof(struct xfs_btree_lblock, bb_leftsib),
+		offsetof(struct xfs_btree_lblock, bb_rightsib),
+		sizeof(struct xfs_btree_lblock)
+	};
+
+	XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
+	XFS_BTREE_TRACE_ARGBI(cur, bp, fields);
+
+	if (bp) {
+		xfs_btree_offsets(fields,
+				  (cur->bc_flags & XFS_BTREE_LONG_PTRS) ?
+				  	loffsets : soffsets,
+				  XFS_BB_NUM_BITS, &first, &last);
+		xfs_trans_log_buf(cur->bc_tp, bp, first, last);
+	} else {
+		/* XXX(hch): maybe factor out into a method? */
+		xfs_trans_log_inode(cur->bc_tp, cur->bc_private.b.ip,
+			XFS_ILOG_FBROOT(cur->bc_private.b.whichfork));
+	}
+
+	XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
+}
+
+
 /*
  * Increment cursor by one record at the level.
  * For nonzero levels the leaf-ward information is untouched.
@@ -1152,7 +1270,6 @@ error0:
 	return error;
 }
 
-
 STATIC int
 xfs_btree_lookup_get_block(
 	struct xfs_btree_cur	*cur,	/* btree cursor */
@@ -1479,3 +1596,177 @@ error0:
 	return error;
 }
 
+/*
+ * Move 1 record right from cur/level if possible.
+ * Update cur to reflect the new path.
+ */
+int					/* error */
+xfs_btree_rshift(
+	struct xfs_btree_cur	*cur,
+	int			level,
+	int			*stat)		/* success/failure */
+{
+	union xfs_btree_key	key;		/* btree key */
+	struct xfs_buf		*lbp;		/* left buffer pointer */
+	struct xfs_btree_block	*left;		/* left btree block */
+	struct xfs_buf		*rbp;		/* right buffer pointer */
+	struct xfs_btree_block	*right;		/* right btree block */
+	struct xfs_btree_cur	*tcur;		/* temporary btree cursor */
+	union xfs_btree_ptr	rptr;		/* right block pointer */
+	union xfs_btree_key	*rkp;		/* right btree key */
+	int			rrecs;		/* right record count */
+	int			lrecs;		/* left record count */
+	int			error;		/* error return value */
+	int			i;		/* loop counter */
+
+	XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
+	XFS_BTREE_TRACE_ARGI(cur, level);
+
+	if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
+	    (level == cur->bc_nlevels - 1))
+		goto out0;
+
+	/* Set up variables for this block as "left". */
+	left = xfs_btree_get_block(cur, level, &lbp);
+
+#ifdef DEBUG
+	error = xfs_btree_check_block(cur, left, level, lbp);
+	if (error)
+		goto error0;
+#endif
+
+	/* If we've got no right sibling then we can't shift an entry right. */
+	xfs_btree_get_sibling(cur, left, &rptr, XFS_BB_RIGHTSIB);
+	if (xfs_btree_ptr_is_null(cur, &rptr))
+		goto out0;
+
+	/*
+	 * If the cursor entry is the one that would be moved, don't
+	 * do it... it's too complicated.
+	 */
+	lrecs = xfs_btree_get_numrecs(left);
+	if (cur->bc_ptrs[level] >= lrecs)
+		goto out0;
+
+	/* Set up the right neighbor as "right". */
+	error = xfs_btree_read_buf_block(cur, &rptr, level, 0, &right, &rbp);
+	if (error)
+		goto error0;
+
+	/* If it's full, it can't take another entry. */
+	rrecs = xfs_btree_get_numrecs(right);
+	if (rrecs == cur->bc_ops->get_maxrecs(cur, level))
+		goto out0;
+
+	XFS_BTREE_STATS_INC(cur, rshift);
+	XFS_BTREE_STATS_ADD(cur, moves, rrecs);
+
+	/*
+	 * Make a hole at the start of the right neighbor block, then
+	 * copy the last left block entry to the hole.
+	 */
+	if (level > 0) {
+		/* It's a nonleaf. make a hole in the keys and ptrs */
+		union xfs_btree_key	*lkp;
+		union xfs_btree_ptr	*lpp;
+		union xfs_btree_ptr	*rpp;
+
+		lkp = cur->bc_ops->key_addr(cur, lrecs, left);
+		lpp = cur->bc_ops->ptr_addr(cur, lrecs, left);
+		rkp = cur->bc_ops->key_addr(cur, 1, right);
+		rpp = cur->bc_ops->ptr_addr(cur, 1, right);
+
+#ifdef DEBUG
+		for (i = rrecs - 1; i >= 0; i--) {
+			error = xfs_btree_check_ptr(cur, rpp, i, level);
+			if (error)
+				goto error0;
+		}
+#endif
+
+		cur->bc_ops->move_keys(cur, rkp, 0, 1, rrecs);
+		xfs_btree_move_ptrs(cur, rpp, 0, 1, rrecs);
+
+#ifdef DEBUG
+		error = xfs_btree_check_ptr(cur, lpp, 0, level);
+		if (error)
+			goto error0;
+#endif
+
+		/* Now put the new data in, and log it. */
+		cur->bc_ops->set_key(cur, rkp, 0, lkp);
+		*rpp = *lpp;
+
+		cur->bc_ops->log_keys(cur, rbp, 1, rrecs + 1);
+		xfs_btree_log_ptrs(cur, rbp, 1, rrecs + 1);
+
+		xfs_btree_check_key(cur->bc_btnum, rkp,
+				    cur->bc_ops->key_addr(cur, 2, right));
+	} else {
+		/* It's a leaf. make a hole in the records */
+		union xfs_btree_rec	*lrp;
+		union xfs_btree_rec	*rrp;
+
+		lrp = cur->bc_ops->rec_addr(cur, lrecs, left);
+		rrp = cur->bc_ops->rec_addr(cur, 1, right);
+
+		cur->bc_ops->move_recs(cur, rrp, 0, 1, rrecs);
+
+		/* Now put the new data in, and log it. */
+		cur->bc_ops->set_rec(cur, rrp, 0, lrp);
+		cur->bc_ops->log_recs(cur, rbp, 1, rrecs + 1);
+
+		cur->bc_ops->init_key_from_rec(cur, &key, rrp);
+		rkp = &key;
+
+		xfs_btree_check_rec(cur->bc_btnum, rrp,
+				    cur->bc_ops->rec_addr(cur, 2, right));
+	}
+
+	/*
+	 * Decrement and log left's numrecs, bump and log right's numrecs.
+	 */
+	xfs_btree_set_numrecs(left, --lrecs);
+	xfs_btree_log_block(cur, lbp, XFS_BB_NUMRECS);
+
+	xfs_btree_set_numrecs(right, ++rrecs);
+	xfs_btree_log_block(cur, rbp, XFS_BB_NUMRECS);
+
+	/*
+	 * Using a temporary cursor, update the parent key values of the
+	 * block on the right.
+	 */
+	error = xfs_btree_dup_cursor(cur, &tcur);
+	if (error)
+		goto error0;
+	i = xfs_btree_lastrec(tcur, level);
+	XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
+
+	error = xfs_btree_increment(tcur, level, &i);
+	if (error)
+		goto error1;
+
+	error = xfs_btree_updkey(tcur, rkp, level + 1);
+	if (error)
+		goto error1;
+
+	xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
+
+	XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
+	*stat = 1;
+	return 0;
+
+out0:
+	XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
+	*stat = 0;
+	return 0;
+
+error0:
+	XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
+	return error;
+
+error1:
+	XFS_BTREE_TRACE_CURSOR(tcur, XBT_ERROR);
+	xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
+	return error;
+}
Index: linux-2.6-xfs/fs/xfs/xfs_btree.h
===================================================================
--- linux-2.6-xfs.orig/fs/xfs/xfs_btree.h	2008-07-27 17:40:52.000000000 +0200
+++ linux-2.6-xfs/fs/xfs/xfs_btree.h	2008-07-27 17:48:40.000000000 +0200
@@ -218,6 +218,22 @@ struct xfs_btree_ops {
 	__int64_t (*key_diff)(struct xfs_btree_cur *cur,
 			      union xfs_btree_key *key);
 
+	/* set values of btree structures */
+	void	(*set_key)(struct xfs_btree_cur *cur,
+			   union xfs_btree_key *oldkey, int index,
+			   union xfs_btree_key *newkey);
+	void	(*set_rec)(struct xfs_btree_cur *cur,
+			   union xfs_btree_rec *oldrec, int index,
+			   union xfs_btree_rec *newrec);
+
+	/* move bits of btree blocks within a block */
+	void	(*move_keys)(struct xfs_btree_cur *cur,
+			     union xfs_btree_key *base, int src_index,
+			     int dst_index, int numkeys);
+	void	(*move_recs)(struct xfs_btree_cur *cur,
+			     union xfs_btree_rec *base, int src_index,
+			     int dst_index, int numrecs);
+
 	/* copy bits of btree blocks between blocks */
 	void	(*copy_keys)(struct xfs_btree_cur *cur,
 			     union xfs_btree_key *src_key,
@@ -559,6 +575,7 @@ int xfs_btree_decrement(struct xfs_btree
 int xfs_btree_lookup(struct xfs_btree_cur *, xfs_lookup_t, int *);
 int xfs_btree_updkey(struct xfs_btree_cur *, union xfs_btree_key *, int);
 int xfs_btree_update(struct xfs_btree_cur *, union xfs_btree_rec *);
+int xfs_btree_rshift(struct xfs_btree_cur *, int, int *);
 
 
 /*
@@ -571,6 +588,12 @@ xfs_btree_get_numrecs(struct xfs_btree_b
 	return be16_to_cpu(block->bb_h.bb_numrecs);
 }
 
+static inline void
+xfs_btree_set_numrecs(struct xfs_btree_block *block, __uint16_t numrecs)
+{
+	block->bb_h.bb_numrecs = cpu_to_be16(numrecs);
+}
+
 #endif	/* __KERNEL__ */
 
 
Index: linux-2.6-xfs/fs/xfs/xfs_alloc_btree.c
===================================================================
--- linux-2.6-xfs.orig/fs/xfs/xfs_alloc_btree.c	2008-07-27 17:40:52.000000000 +0200
+++ linux-2.6-xfs/fs/xfs/xfs_alloc_btree.c	2008-07-27 17:49:24.000000000 +0200
@@ -54,7 +54,6 @@ STATIC void xfs_allocbt_log_recs(xfs_btr
 	xfs_allocbt_log_recs(c, b, i, j)
 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 *);
 
@@ -396,7 +395,7 @@ xfs_alloc_delrec(
 		 */
 		if (be16_to_cpu(left->bb_numrecs) - 1 >=
 		     XFS_ALLOC_BLOCK_MINRECS(level, cur)) {
-			if ((error = xfs_alloc_rshift(tcur, level, &i)))
+			if ((error = xfs_btree_rshift(tcur, level, &i)))
 				goto error0;
 			if (i) {
 				ASSERT(be16_to_cpu(block->bb_numrecs) >=
@@ -688,7 +687,7 @@ xfs_alloc_insrec(
 		/*
 		 * First, try shifting an entry to the right neighbor.
 		 */
-		if ((error = xfs_alloc_rshift(cur, level, &i)))
+		if ((error = xfs_btree_rshift(cur, level, &i)))
 			return error;
 		if (i) {
 			/* nothing */
@@ -1181,137 +1180,6 @@ xfs_alloc_newroot(
 }
 
 /*
- * Move 1 record right from cur/level if possible.
- * Update cur to reflect the new path.
- */
-STATIC int				/* error */
-xfs_alloc_rshift(
-	xfs_btree_cur_t		*cur,	/* btree cursor */
-	int			level,	/* level to shift record on */
-	int			*stat)	/* success/failure */
-{
-	int			error;	/* error return value */
-	int			i;	/* loop index */
-	xfs_alloc_key_t		key;	/* key value for leaf level upward */
-	xfs_buf_t		*lbp;	/* buffer for left (current) block */
-	xfs_alloc_block_t	*left;	/* left (current) btree block */
-	xfs_buf_t		*rbp;	/* buffer for right neighbor block */
-	xfs_alloc_block_t	*right;	/* right neighbor btree block */
-	xfs_alloc_key_t		*rkp;	/* key pointer for right block */
-	xfs_btree_cur_t		*tcur;	/* temporary cursor */
-
-	/*
-	 * Set up variables for this block as "left".
-	 */
-	lbp = cur->bc_bufs[level];
-	left = XFS_BUF_TO_ALLOC_BLOCK(lbp);
-#ifdef DEBUG
-	if ((error = xfs_btree_check_sblock(cur, left, level, lbp)))
-		return error;
-#endif
-	/*
-	 * If we've got no right sibling then we can't shift an entry right.
-	 */
-	if (be32_to_cpu(left->bb_rightsib) == NULLAGBLOCK) {
-		*stat = 0;
-		return 0;
-	}
-	/*
-	 * If the cursor entry is the one that would be moved, don't
-	 * do it... it's too complicated.
-	 */
-	if (cur->bc_ptrs[level] >= be16_to_cpu(left->bb_numrecs)) {
-		*stat = 0;
-		return 0;
-	}
-	/*
-	 * Set up the right neighbor as "right".
-	 */
-	if ((error = xfs_btree_read_bufs(cur->bc_mp, cur->bc_tp,
-			cur->bc_private.a.agno, be32_to_cpu(left->bb_rightsib),
-			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;
-	/*
-	 * If it's full, it can't take another entry.
-	 */
-	if (be16_to_cpu(right->bb_numrecs) == XFS_ALLOC_BLOCK_MAXRECS(level, cur)) {
-		*stat = 0;
-		return 0;
-	}
-	/*
-	 * Make a hole at the start of the right neighbor block, then
-	 * copy the last left block entry to the hole.
-	 */
-	if (level > 0) {
-		xfs_alloc_key_t	*lkp;	/* key pointer for left block */
-		xfs_alloc_ptr_t	*lpp;	/* address pointer for left block */
-		xfs_alloc_ptr_t	*rpp;	/* address pointer for right block */
-
-		lkp = XFS_ALLOC_KEY_ADDR(left, be16_to_cpu(left->bb_numrecs), cur);
-		lpp = XFS_ALLOC_PTR_ADDR(left, be16_to_cpu(left->bb_numrecs), cur);
-		rkp = XFS_ALLOC_KEY_ADDR(right, 1, cur);
-		rpp = XFS_ALLOC_PTR_ADDR(right, 1, cur);
-#ifdef DEBUG
-		for (i = be16_to_cpu(right->bb_numrecs) - 1; i >= 0; i--) {
-			if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(rpp[i]), level)))
-				return error;
-		}
-#endif
-		memmove(rkp + 1, rkp, be16_to_cpu(right->bb_numrecs) * sizeof(*rkp));
-		memmove(rpp + 1, rpp, be16_to_cpu(right->bb_numrecs) * sizeof(*rpp));
-#ifdef DEBUG
-		if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(*lpp), level)))
-			return error;
-#endif
-		*rkp = *lkp;
-		*rpp = *lpp;
-		xfs_alloc_log_keys(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
-		xfs_alloc_log_ptrs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
-		xfs_btree_check_key(cur->bc_btnum, rkp, rkp + 1);
-	} else {
-		xfs_alloc_rec_t	*lrp;	/* record pointer for left block */
-		xfs_alloc_rec_t	*rrp;	/* record pointer for right block */
-
-		lrp = XFS_ALLOC_REC_ADDR(left, be16_to_cpu(left->bb_numrecs), cur);
-		rrp = XFS_ALLOC_REC_ADDR(right, 1, cur);
-		memmove(rrp + 1, rrp, be16_to_cpu(right->bb_numrecs) * sizeof(*rrp));
-		*rrp = *lrp;
-		xfs_alloc_log_recs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
-		key.ar_startblock = rrp->ar_startblock;
-		key.ar_blockcount = rrp->ar_blockcount;
-		rkp = &key;
-		xfs_btree_check_rec(cur->bc_btnum, rrp, rrp + 1);
-	}
-	/*
-	 * Decrement and log left's numrecs, bump and log right's numrecs.
-	 */
-	be16_add(&left->bb_numrecs, -1);
-	xfs_alloc_log_block(cur->bc_tp, lbp, XFS_BB_NUMRECS);
-	be16_add(&right->bb_numrecs, 1);
-	xfs_alloc_log_block(cur->bc_tp, rbp, XFS_BB_NUMRECS);
-	/*
-	 * Using a temporary cursor, update the parent key values of the
-	 * block on the right.
-	 */
-	if ((error = xfs_btree_dup_cursor(cur, &tcur)))
-		return error;
-	i = xfs_btree_lastrec(tcur, level);
-	XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
-	if ((error = xfs_btree_increment(tcur, level, &i)) ||
-	    (error = xfs_btree_updkey(tcur, (union xfs_btree_key *)rkp, level + 1)))
-		goto error0;
-	xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
-	*stat = 1;
-	return 0;
-error0:
-	xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
-	return error;
-}
-
-/*
  * Split cur/level block in half.
  * Return new block number and its first record (to be inserted into parent).
  */
@@ -1740,6 +1608,64 @@ xfs_allocbt_key_diff(
 }
 
 STATIC void
+xfs_allocbt_set_key(
+	struct xfs_btree_cur	*cur,
+	union xfs_btree_key	*key_addr,
+	int			index,
+	union xfs_btree_key	*newkey)
+{
+	xfs_alloc_key_t		*kp = &key_addr->alloc;
+
+	kp[index] = newkey->alloc;
+}
+
+STATIC void
+xfs_allocbt_set_rec(
+	struct xfs_btree_cur	*cur,
+	union xfs_btree_rec	*rec_addr,
+	int			index,
+	union xfs_btree_rec	*newrec)
+{
+	xfs_alloc_rec_t		*rp = &rec_addr->alloc;
+
+	rp[index] = newrec->alloc;
+}
+
+STATIC void
+xfs_allocbt_move_keys(
+	struct xfs_btree_cur	*cur,
+	union xfs_btree_key	*base,
+	int			from,
+	int			to,
+	int			numkeys)
+{
+	xfs_alloc_key_t		*kp = &base->alloc;
+
+	ASSERT(from >= 0 && from <= 1000);
+	ASSERT(to >= 0 && to <= 1000);
+	ASSERT(numkeys >= 0);
+
+	memmove(&kp[to], &kp[from], numkeys * sizeof(*kp));
+}
+
+STATIC void
+xfs_allocbt_move_recs(
+	struct xfs_btree_cur	*cur,
+	union xfs_btree_rec	*base,
+	int			from,
+	int			to,
+	int			numrecs)
+{
+	xfs_alloc_rec_t		*rp = &base->alloc;
+
+	ASSERT(from >= 0 && from <= 1000);
+	ASSERT(to >= 0 && to <= 1000);
+	ASSERT(numrecs >= 0);
+
+	memmove(&rp[to], &rp[from], numrecs * sizeof(*rp));
+}
+
+STATIC void
 xfs_allocbt_copy_keys(
 	struct xfs_btree_cur	*cur,
 	union xfs_btree_key	*src_key,
@@ -1904,6 +1830,10 @@ static const struct xfs_btree_ops xfs_al
 	.key_addr		= xfs_allocbt_key_addr,
 	.rec_addr		= xfs_allocbt_rec_addr,
 	.key_diff		= xfs_allocbt_key_diff,
+	.set_key		= xfs_allocbt_set_key,
+	.set_rec		= xfs_allocbt_set_rec,
+	.move_keys		= xfs_allocbt_move_keys,
+	.move_recs		= xfs_allocbt_move_recs,
 	.copy_keys		= xfs_allocbt_copy_keys,
 	.copy_recs		= xfs_allocbt_copy_recs,
 	.log_keys		= xfs_allocbt_log_keys,
Index: linux-2.6-xfs/fs/xfs/xfs_ialloc_btree.c
===================================================================
--- linux-2.6-xfs.orig/fs/xfs/xfs_ialloc_btree.c	2008-07-27 17:49:43.000000000 +0200
+++ linux-2.6-xfs/fs/xfs/xfs_ialloc_btree.c	2008-07-27 17:53:33.000000000 +0200
@@ -46,7 +46,6 @@ STATIC void xfs_inobt_log_ptrs(xfs_btree
 STATIC void xfs_inobt_log_recs(xfs_btree_cur_t *, xfs_buf_t *, int, int);
 STATIC int xfs_inobt_lshift(xfs_btree_cur_t *, int, int *);
 STATIC int xfs_inobt_newroot(xfs_btree_cur_t *, int *);
-STATIC int xfs_inobt_rshift(xfs_btree_cur_t *, int, int *);
 STATIC int xfs_inobt_split(xfs_btree_cur_t *, int, xfs_agblock_t *,
 		xfs_inobt_key_t *, xfs_btree_cur_t **, int *);
 
@@ -338,7 +337,7 @@ xfs_inobt_delrec(
 		 */
 		if (be16_to_cpu(left->bb_numrecs) - 1 >=
 		     XFS_INOBT_BLOCK_MINRECS(level, cur)) {
-			if ((error = xfs_inobt_rshift(tcur, level, &i)))
+			if ((error = xfs_btree_rshift(tcur, level, &i)))
 				goto error0;
 			if (i) {
 				ASSERT(be16_to_cpu(block->bb_numrecs) >=
@@ -609,7 +608,7 @@ xfs_inobt_insrec(
 		/*
 		 * First, try shifting an entry to the right neighbor.
 		 */
-		if ((error = xfs_inobt_rshift(cur, level, &i)))
+		if ((error = xfs_btree_rshift(cur, level, &i)))
 			return error;
 		if (i) {
 			/* nothing */
@@ -1074,136 +1073,6 @@ xfs_inobt_newroot(
 }
 
 /*
- * Move 1 record right from cur/level if possible.
- * Update cur to reflect the new path.
- */
-STATIC int				/* error */
-xfs_inobt_rshift(
-	xfs_btree_cur_t		*cur,	/* btree cursor */
-	int			level,	/* level to shift record on */
-	int			*stat)	/* success/failure */
-{
-	int			error;	/* error return value */
-	int			i;	/* loop index */
-	xfs_inobt_key_t		key;	/* key value for leaf level upward */
-	xfs_buf_t		*lbp;	/* buffer for left (current) block */
-	xfs_inobt_block_t	*left;	/* left (current) btree block */
-	xfs_inobt_key_t		*lkp;	/* key pointer for left block */
-	xfs_inobt_ptr_t		*lpp;	/* address pointer for left block */
-	xfs_inobt_rec_t		*lrp;	/* record pointer for left block */
-	xfs_buf_t		*rbp;	/* buffer for right neighbor block */
-	xfs_inobt_block_t	*right;	/* right neighbor btree block */
-	xfs_inobt_key_t		*rkp;	/* key pointer for right block */
-	xfs_inobt_ptr_t		*rpp;	/* address pointer for right block */
-	xfs_inobt_rec_t		*rrp=NULL;	/* record pointer for right block */
-	xfs_btree_cur_t		*tcur;	/* temporary cursor */
-
-	/*
-	 * Set up variables for this block as "left".
-	 */
-	lbp = cur->bc_bufs[level];
-	left = XFS_BUF_TO_INOBT_BLOCK(lbp);
-#ifdef DEBUG
-	if ((error = xfs_btree_check_sblock(cur, left, level, lbp)))
-		return error;
-#endif
-	/*
-	 * If we've got no right sibling then we can't shift an entry right.
-	 */
-	if (be32_to_cpu(left->bb_rightsib) == NULLAGBLOCK) {
-		*stat = 0;
-		return 0;
-	}
-	/*
-	 * If the cursor entry is the one that would be moved, don't
-	 * do it... it's too complicated.
-	 */
-	if (cur->bc_ptrs[level] >= be16_to_cpu(left->bb_numrecs)) {
-		*stat = 0;
-		return 0;
-	}
-	/*
-	 * Set up the right neighbor as "right".
-	 */
-	if ((error = xfs_btree_read_bufs(cur->bc_mp, cur->bc_tp,
-			cur->bc_private.a.agno, be32_to_cpu(left->bb_rightsib),
-			0, &rbp, XFS_INO_BTREE_REF)))
-		return error;
-	right = XFS_BUF_TO_INOBT_BLOCK(rbp);
-	if ((error = xfs_btree_check_sblock(cur, right, level, rbp)))
-		return error;
-	/*
-	 * If it's full, it can't take another entry.
-	 */
-	if (be16_to_cpu(right->bb_numrecs) == XFS_INOBT_BLOCK_MAXRECS(level, cur)) {
-		*stat = 0;
-		return 0;
-	}
-	/*
-	 * Make a hole at the start of the right neighbor block, then
-	 * copy the last left block entry to the hole.
-	 */
-	if (level > 0) {
-		lkp = XFS_INOBT_KEY_ADDR(left, be16_to_cpu(left->bb_numrecs), cur);
-		lpp = XFS_INOBT_PTR_ADDR(left, be16_to_cpu(left->bb_numrecs), cur);
-		rkp = XFS_INOBT_KEY_ADDR(right, 1, cur);
-		rpp = XFS_INOBT_PTR_ADDR(right, 1, cur);
-#ifdef DEBUG
-		for (i = be16_to_cpu(right->bb_numrecs) - 1; i >= 0; i--) {
-			if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(rpp[i]), level)))
-				return error;
-		}
-#endif
-		memmove(rkp + 1, rkp, be16_to_cpu(right->bb_numrecs) * sizeof(*rkp));
-		memmove(rpp + 1, rpp, be16_to_cpu(right->bb_numrecs) * sizeof(*rpp));
-#ifdef DEBUG
-		if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(*lpp), level)))
-			return error;
-#endif
-		*rkp = *lkp;
-		*rpp = *lpp;
-		xfs_inobt_log_keys(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
-		xfs_inobt_log_ptrs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
-	} else {
-		lrp = XFS_INOBT_REC_ADDR(left, be16_to_cpu(left->bb_numrecs), cur);
-		rrp = XFS_INOBT_REC_ADDR(right, 1, cur);
-		memmove(rrp + 1, rrp, be16_to_cpu(right->bb_numrecs) * sizeof(*rrp));
-		*rrp = *lrp;
-		xfs_inobt_log_recs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
-		key.ir_startino = rrp->ir_startino;
-		rkp = &key;
-	}
-	/*
-	 * Decrement and log left's numrecs, bump and log right's numrecs.
-	 */
-	be16_add(&left->bb_numrecs, -1);
-	xfs_inobt_log_block(cur->bc_tp, lbp, XFS_BB_NUMRECS);
-	be16_add(&right->bb_numrecs, 1);
-#ifdef DEBUG
-	if (level > 0)
-		xfs_btree_check_key(cur->bc_btnum, rkp, rkp + 1);
-	else
-		xfs_btree_check_rec(cur->bc_btnum, rrp, rrp + 1);
-#endif
-	xfs_inobt_log_block(cur->bc_tp, rbp, XFS_BB_NUMRECS);
-	/*
-	 * Using a temporary cursor, update the parent key values of the
-	 * block on the right.
-	 */
-	if ((error = xfs_btree_dup_cursor(cur, &tcur)))
-		return error;
-	xfs_btree_lastrec(tcur, level);
-	if ((error = xfs_btree_increment(tcur, level, &i)) ||
-	    (error = xfs_btree_updkey(tcur, (union xfs_btree_key *)rkp, level + 1))) {
-		xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
-		return error;
-	}
-	xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
-	*stat = 1;
-	return 0;
-}
-
-/*
  * Split cur/level block in half.
  * Return new block number and its first record (to be inserted into parent).
  */
@@ -1588,6 +1457,64 @@ xfs_inobt_key_diff(
 }
 
 STATIC void
+xfs_inobt_set_key(
+	struct xfs_btree_cur	*cur,
+	union xfs_btree_key	*key_addr,
+	int			index,
+	union xfs_btree_key	*newkey)
+{
+	xfs_inobt_key_t		*kp = &key_addr->inobt;
+
+	kp[index] = newkey->inobt;
+}
+
+STATIC void
+xfs_inobt_set_rec(
+	struct xfs_btree_cur	*cur,
+	union xfs_btree_rec	*rec_addr,
+	int			index,
+	union xfs_btree_rec	*newrec)
+{
+	xfs_inobt_rec_t		*rp = &rec_addr->inobt;
+
+	rp[index] = newrec->inobt;
+}
+
+STATIC void
+xfs_inobt_move_keys(
+	struct xfs_btree_cur	*cur,
+	union xfs_btree_key	*base,
+	int			from,
+	int			to,
+	int			numkeys)
+{
+	xfs_inobt_key_t		*kp = &base->inobt;
+
+	ASSERT(from >= 0 && from <= 1000);
+	ASSERT(to >= 0 && to <= 1000);
+	ASSERT(numkeys >= 0);
+
+	memmove(&kp[to], &kp[from], numkeys * sizeof(*kp));
+}
+
+STATIC void
+xfs_inobt_move_recs(
+	struct xfs_btree_cur	*cur,
+	union xfs_btree_rec	*base,
+	int			from,
+	int			to,
+	int			numrecs)
+{
+	xfs_inobt_rec_t		*rp = &base->inobt;
+
+	ASSERT(from >= 0 && from <= 1000);
+	ASSERT(to >= 0 && to <= 1000);
+	ASSERT(numrecs >= 0);
+
+	memmove(&rp[to], &rp[from], numrecs * sizeof(*rp));
+}
+
+STATIC void
 xfs_inobt_copy_keys(
 	struct xfs_btree_cur	*cur,
 	union xfs_btree_key	*src_key,
@@ -1740,6 +1667,11 @@ static const struct xfs_btree_ops xfs_in
 	.key_addr		= xfs_inobt_key_addr,
 	.rec_addr		= xfs_inobt_rec_addr,
 	.key_diff		= xfs_inobt_key_diff,
+	.set_key		= xfs_inobt_set_key,
+	.set_rec		= xfs_inobt_set_rec,
+	.move_keys		= xfs_inobt_move_keys,
+	.move_recs		= xfs_inobt_move_recs,
+
 	.copy_keys		= xfs_inobt_copy_keys,
 	.copy_recs		= xfs_inobt_copy_recs,
 	.log_keys		= xfs_inobt_log_keys,
Index: linux-2.6-xfs/fs/xfs/xfs_bmap_btree.c
===================================================================
--- linux-2.6-xfs.orig/fs/xfs/xfs_bmap_btree.c	2008-07-27 17:53:50.000000000 +0200
+++ linux-2.6-xfs/fs/xfs/xfs_bmap_btree.c	2008-07-27 17:57:11.000000000 +0200
@@ -53,7 +53,6 @@ STATIC int xfs_bmbt_killroot(xfs_btree_c
 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 *);
 
@@ -326,7 +325,7 @@ xfs_bmbt_delrec(
 		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))) {
+			if ((error = xfs_btree_rshift(tcur, level, &i))) {
 				XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 				goto error0;
 			}
@@ -537,7 +536,7 @@ xfs_bmbt_insrec(
 				logflags);
 			block = xfs_bmbt_get_block(cur, level, &bp);
 		} else {
-			if ((error = xfs_bmbt_rshift(cur, level, &i))) {
+			if ((error = xfs_btree_rshift(cur, level, &i))) {
 				XFS_BMBT_TRACE_CURSOR(cur, ERROR);
 				return error;
 			}
@@ -908,143 +907,6 @@ xfs_bmbt_lshift(
 }
 
 /*
- * Move 1 record right from cur/level if possible.
- * Update cur to reflect the new path.
- */
-STATIC int					/* error */
-xfs_bmbt_rshift(
-	xfs_btree_cur_t		*cur,
-	int			level,
-	int			*stat)		/* success/failure */
-{
-	int			error;		/* error return value */
-	int			i;		/* loop counter */
-	xfs_bmbt_key_t		key;		/* bmap btree key */
-	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 */
-	xfs_bmbt_rec_t		*lrp;		/* left record pointer */
-	xfs_mount_t		*mp;		/* file system mount point */
-	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_ptr_t		*rpp;		/* right address pointer */
-	xfs_bmbt_rec_t		*rrp=NULL;	/* right record pointer */
-	struct xfs_btree_cur	*tcur;		/* temporary btree cursor */
-
-	XFS_BMBT_TRACE_CURSOR(cur, ENTRY);
-	XFS_BMBT_TRACE_ARGI(cur, level);
-	if (level == cur->bc_nlevels - 1) {
-		XFS_BMBT_TRACE_CURSOR(cur, EXIT);
-		*stat = 0;
-		return 0;
-	}
-	lbp = cur->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);
-		return error;
-	}
-#endif
-	if (be64_to_cpu(left->bb_rightsib) == NULLDFSBNO) {
-		XFS_BMBT_TRACE_CURSOR(cur, EXIT);
-		*stat = 0;
-		return 0;
-	}
-	if (cur->bc_ptrs[level] >= be16_to_cpu(left->bb_numrecs)) {
-		XFS_BMBT_TRACE_CURSOR(cur, EXIT);
-		*stat = 0;
-		return 0;
-	}
-	mp = cur->bc_mp;
-	if ((error = xfs_btree_read_bufl(mp, cur->bc_tp, be64_to_cpu(left->bb_rightsib), 0,
-			&rbp, XFS_BMAP_BTREE_REF))) {
-		XFS_BMBT_TRACE_CURSOR(cur, ERROR);
-		return error;
-	}
-	right = XFS_BUF_TO_BMBT_BLOCK(rbp);
-	if ((error = xfs_btree_check_lblock(cur, right, level, rbp))) {
-		XFS_BMBT_TRACE_CURSOR(cur, ERROR);
-		return error;
-	}
-	if (be16_to_cpu(right->bb_numrecs) == XFS_BMAP_BLOCK_IMAXRECS(level, cur)) {
-		XFS_BMBT_TRACE_CURSOR(cur, EXIT);
-		*stat = 0;
-		return 0;
-	}
-	if (level > 0) {
-		lkp = XFS_BMAP_KEY_IADDR(left, be16_to_cpu(left->bb_numrecs), cur);
-		lpp = XFS_BMAP_PTR_IADDR(left, be16_to_cpu(left->bb_numrecs), cur);
-		rkp = XFS_BMAP_KEY_IADDR(right, 1, cur);
-		rpp = XFS_BMAP_PTR_IADDR(right, 1, cur);
-#ifdef DEBUG
-		for (i = be16_to_cpu(right->bb_numrecs) - 1; i >= 0; i--) {
-			if ((error = xfs_btree_check_lptr_disk(cur, rpp[i], level))) {
-				XFS_BMBT_TRACE_CURSOR(cur, ERROR);
-				return error;
-			}
-		}
-#endif
-		memmove(rkp + 1, rkp, be16_to_cpu(right->bb_numrecs) * sizeof(*rkp));
-		memmove(rpp + 1, rpp, be16_to_cpu(right->bb_numrecs) * sizeof(*rpp));
-#ifdef DEBUG
-		if ((error = xfs_btree_check_lptr_disk(cur, *lpp, level))) {
-			XFS_BMBT_TRACE_CURSOR(cur, ERROR);
-			return error;
-		}
-#endif
-		*rkp = *lkp;
-		*rpp = *lpp;
-		xfs_bmbt_log_keys(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
-		xfs_bmbt_log_ptrs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
-	} else {
-		lrp = XFS_BMAP_REC_IADDR(left, be16_to_cpu(left->bb_numrecs), cur);
-		rrp = XFS_BMAP_REC_IADDR(right, 1, cur);
-		memmove(rrp + 1, rrp, be16_to_cpu(right->bb_numrecs) * sizeof(*rrp));
-		*rrp = *lrp;
-		xfs_bmbt_log_recs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
-		key.br_startoff = cpu_to_be64(xfs_bmbt_disk_get_startoff(rrp));
-		rkp = &key;
-	}
-	be16_add(&left->bb_numrecs, -1);
-	xfs_bmbt_log_block(cur, lbp, XFS_BB_NUMRECS);
-	be16_add(&right->bb_numrecs, 1);
-#ifdef DEBUG
-	if (level > 0)
-		xfs_btree_check_key(XFS_BTNUM_BMAP, rkp, rkp + 1);
-	else
-		xfs_btree_check_rec(XFS_BTNUM_BMAP, rrp, rrp + 1);
-#endif
-	xfs_bmbt_log_block(cur, rbp, XFS_BB_NUMRECS);
-	if ((error = xfs_btree_dup_cursor(cur, &tcur))) {
-		XFS_BMBT_TRACE_CURSOR(cur, ERROR);
-		return error;
-	}
-	i = xfs_btree_lastrec(tcur, level);
-	XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
-	if ((error = xfs_btree_increment(tcur, level, &i))) {
-		XFS_BMBT_TRACE_CURSOR(tcur, ERROR);
-		goto error1;
-	}
-	XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
-	if ((error = xfs_btree_updkey(tcur, (union xfs_btree_key *)rkp, level + 1))) {
-		XFS_BMBT_TRACE_CURSOR(tcur, ERROR);
-		goto error1;
-	}
-	xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
-	XFS_BMBT_TRACE_CURSOR(cur, EXIT);
-	*stat = 1;
-	return 0;
-error0:
-	XFS_BMBT_TRACE_CURSOR(cur, ERROR);
-error1:
-	xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
-	return error;
-}
-
-/*
  * Determine the extent state.
  */
 /* ARGSUSED */
@@ -2019,6 +1881,64 @@ xfs_bmbt_key_diff(
 }
 
 STATIC void
+xfs_bmbt_set_key(
+	struct xfs_btree_cur	*cur,
+	union xfs_btree_key	*key_addr,
+	int			index,
+	union xfs_btree_key	*newkey)
+{
+	xfs_bmbt_key_t		*kp = &key_addr->bmbt;
+
+	kp[index] = newkey->bmbt;
+}
+
+STATIC void
+xfs_bmbt_set_rec(
+	struct xfs_btree_cur	*cur,
+	union xfs_btree_rec	*rec_addr,
+	int			index,
+	union xfs_btree_rec	*newrec)
+{
+	xfs_bmbt_rec_t		*rp = &rec_addr->bmbt;
+
+	rp[index] = newrec->bmbt;
+}
+
+STATIC void
+xfs_bmbt_move_keys(
+	struct xfs_btree_cur	*cur,
+	union xfs_btree_key	*base,
+	int			from,
+	int			to,
+	int			numkeys)
+{
+	xfs_bmbt_key_t		*kp = &base->bmbt;
+
+	ASSERT(from >= 0 && from <= 1000);
+	ASSERT(to >= 0 && to <= 1000);
+	ASSERT(numkeys >= 0);
+
+	memmove(&kp[to], &kp[from], numkeys * sizeof(*kp));
+}
+
+STATIC void
+xfs_bmbt_move_recs(
+	struct xfs_btree_cur	*cur,
+	union xfs_btree_rec	*base,
+	int			from,
+	int			to,
+	int			numrecs)
+{
+	xfs_bmbt_rec_t		*rp = &base->bmbt;
+
+	ASSERT(from >= 0 && from <= 1000);
+	ASSERT(to >= 0 && to <= 1000);
+	ASSERT(numrecs >= 0);
+
+	memmove(&rp[to], &rp[from], numrecs * sizeof(*rp));
+}
+
+STATIC void
 xfs_bmbt_copy_keys(
 	struct xfs_btree_cur	*cur,
 	union xfs_btree_key	*src_key,
@@ -2195,6 +2115,10 @@ static const struct xfs_btree_ops xfs_bm
 	.key_addr		= xfs_bmbt_key_addr,
 	.rec_addr		= xfs_bmbt_rec_addr,
 	.key_diff		= xfs_bmbt_key_diff,
+	.set_key		= xfs_bmbt_set_key,
+	.set_rec		= xfs_bmbt_set_rec,
+	.move_keys		= xfs_bmbt_move_keys,
+	.move_recs		= xfs_bmbt_move_recs,
 	.copy_keys		= xfs_bmbt_copy_keys,
 	.copy_recs		= xfs_bmbt_copy_recs,
 	.log_keys		= xfs_bmbt_log_keys,

-- 

Re: [PATCH 15/21] implement generic xfs_btree_rshift

[Dave Chinner]

On Tue, Jul 29, 2008 at 09:31:25PM +0200, Christoph Hellwig wrote:
> Make the btree right shift code generic.  Based on a patch from David Chinner
> with lots of changes to follow the original btree implementations more
> closely.  While this loses some of the generic helper routines for
> inserting/moving/removing records it also solves some of the one off
> bugs in the original code and makes it easier to verify.

Looks good. A few comments below.

> 
> Signed-off-by: Christoph Hellwig <hch@lst.de>
> 
> 
> Index: linux-2.6-xfs/fs/xfs/xfs_btree.c
> ===================================================================
> --- linux-2.6-xfs.orig/fs/xfs/xfs_btree.c	2008-07-27 17:40:52.000000000 +0200
> +++ linux-2.6-xfs/fs/xfs/xfs_btree.c	2008-07-28 16:13:33.000000000 +0200
> @@ -34,6 +34,7 @@
>  #include "xfs_attr_sf.h"
>  #include "xfs_dinode.h"
>  #include "xfs_inode.h"
> +#include "xfs_inode_item.h"
>  #include "xfs_btree.h"
>  #include "xfs_btree_trace.h"
>  #include "xfs_ialloc.h"
> @@ -952,6 +953,123 @@ xfs_btree_read_buf_block(
>  	return xfs_btree_check_block(cur, *block, level, *bpp);
>  }
>  
> +STATIC void
> +xfs_btree_move_ptrs(
> +	struct xfs_btree_cur	*cur,
> +	union xfs_btree_ptr	*base,
> +	int			from,
> +	int			to,
> +	int			numptrs)
> +{
> +	ASSERT(from >= 0 && from <= 1000);
> +	ASSERT(to >= 0 && to <= 1000);
> +	ASSERT(numptrs >= 0);

Those numbers are not safe. I plucked them out of thin air to verify
validity on 4k block size filesystem which had (IIRC) a max of about
500 ptrs to a block. It was throwaway debug code to find a problem.
Larger block sizes can well exceed 1000. So realistically, the only
valid assert there is this one:

	ASSERT(numptrs >= 0);

> +/*
> + * Log block pointer fields from a btree block (nonleaf).
> + */
> +STATIC void
> +xfs_btree_log_ptrs(
> +	struct xfs_btree_cur	*cur,	/* btree cursor */
> +	struct xfs_buf		*bp,	/* buffer containing btree block */
> +	int			pfirst,	/* index of first pointer to log */
> +	int			plast)	/* index of last pointer to log */

I'd call these first/last (being indexes), and these:

> +{
> +
> +	XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
> +	XFS_BTREE_TRACE_ARGBII(cur, bp, pfirst, plast);
> +
> +	if (bp) {
> +		struct xfs_btree_block	*block = XFS_BUF_TO_BLOCK(bp);
> +		union xfs_btree_ptr	*pp;
> +		int			first;	/* first byte offset logged */
> +		int			last;	/* last byte offset logged */

start/end because they are byte range identifiers.

> +
> +		pp = cur->bc_ops->ptr_addr(cur, 1, block);
> +
> +		if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
> +			__be64		*lpp = &pp->l;
> +
> +			first = (int)((xfs_caddr_t)&lpp[pfirst - 1] -
> +					(xfs_caddr_t)block);
> +			last = (int)(((xfs_caddr_t)&lpp[plast] - 1) -
> +					(xfs_caddr_t)block);
> +		} else {
> +			__be32		*spp = &pp->s;
> +
> +			first = (int)((xfs_caddr_t)&spp[pfirst - 1] -
> +					(xfs_caddr_t)block);
> +			last = (int)(((xfs_caddr_t)&spp[plast] - 1) -
> +					(xfs_caddr_t)block);

Hmmmm. That's not very nice with all those casts. It's clear that
it's pointer arithmetic, but rather messy.

> +		}
> +
> +		xfs_trans_log_buf(cur->bc_tp, bp, first, last);

How about:

		union xfs_btree_ptr	*pp;
		xfs_caddr_t		*block = XFS_BUF_TO_BLOCK(bp);
		xfs_caddr_t		start;	/* first byte offset logged */
		xfs_caddr_t		end;	/* last byte offset logged */

		pp = cur->bc_ops->ptr_addr(cur, 1, XFS_BUF_TO_BLOCK(bp));

		if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
			__be64		*lpp = &pp->l;

			start = (xfs_caddr_t)&lpp[first - 1] - block;
			end  = ((xfs_caddr_t)&lpp[last] - 1) - block;
		} else {
			__be32		*spp = &pp->s;

			start = (xfs_caddr_t)&spp[first - 1] - block;
			end  = ((xfs_caddr_t)&spp[last] - 1) - block;
		}

		xfs_trans_log_buf(cur->bc_tp, bp, (int)start, (int)end);

That makes it much easier to read (to me, anyway).

> +	XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
> +	XFS_BTREE_TRACE_ARGBI(cur, bp, fields);
> +
> +	if (bp) {
> +		xfs_btree_offsets(fields,
> +				  (cur->bc_flags & XFS_BTREE_LONG_PTRS) ?
> +				  	loffsets : soffsets,
                                ^^
Some stray whitespace there.

> +				  XFS_BB_NUM_BITS, &first, &last);
> +		xfs_trans_log_buf(cur->bc_tp, bp, first, last);
> +	} else {
> +		/* XXX(hch): maybe factor out into a method? */
> +		xfs_trans_log_inode(cur->bc_tp, cur->bc_private.b.ip,
> +			XFS_ILOG_FBROOT(cur->bc_private.b.whichfork));

I don't think it is necessary at this point.

Cheers,

Dave.
-- 
Dave Chinner
david@fromorbit.com

Re: [PATCH 15/21] implement generic xfs_btree_rshift

[Christoph Hellwig]

> > +{
> > +	ASSERT(from >= 0 && from <= 1000);
> > +	ASSERT(to >= 0 && to <= 1000);
> > +	ASSERT(numptrs >= 0);
> 
> Those numbers are not safe. I plucked them out of thin air to verify
> validity on 4k block size filesystem which had (IIRC) a max of about
> 500 ptrs to a block. It was throwaway debug code to find a problem.
> Larger block sizes can well exceed 1000. So realistically, the only
> valid assert there is this one:
> 
> 	ASSERT(numptrs >= 0);

Yeah, I've actually managed to trigger it now.  The >=0 checks
for from and to still make sense, although they might be overkill.

> How about:
> 
> 		union xfs_btree_ptr	*pp;
> 		xfs_caddr_t		*block = XFS_BUF_TO_BLOCK(bp);
> 		xfs_caddr_t		start;	/* first byte offset logged */
> 		xfs_caddr_t		end;	/* last byte offset logged */
> 
> 		pp = cur->bc_ops->ptr_addr(cur, 1, XFS_BUF_TO_BLOCK(bp));
> 
> 		if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
> 			__be64		*lpp = &pp->l;
> 
> 			start = (xfs_caddr_t)&lpp[first - 1] - block;
> 			end  = ((xfs_caddr_t)&lpp[last] - 1) - block;
> 		} else {
> 			__be32		*spp = &pp->s;
> 
> 			start = (xfs_caddr_t)&spp[first - 1] - block;
> 			end  = ((xfs_caddr_t)&spp[last] - 1) - block;
> 		}
> 
> 		xfs_trans_log_buf(cur->bc_tp, bp, (int)start, (int)end);
> 
> That makes it much easier to read (to me, anyway).

Yes, absolutely.  And there's also another set of useless braces.
I've also applied a similar cleanup to the log_keys and log_recs
implementations.

> > +	XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
> > +	XFS_BTREE_TRACE_ARGBI(cur, bp, fields);
> > +
> > +	if (bp) {
> > +		xfs_btree_offsets(fields,
> > +				  (cur->bc_flags & XFS_BTREE_LONG_PTRS) ?
> > +				  	loffsets : soffsets,
>                                 ^^
> Some stray whitespace there.

Fixed.

> > +				  XFS_BB_NUM_BITS, &first, &last);
> > +		xfs_trans_log_buf(cur->bc_tp, bp, first, last);
> > +	} else {
> > +		/* XXX(hch): maybe factor out into a method? */
> > +		xfs_trans_log_inode(cur->bc_tp, cur->bc_private.b.ip,
> > +			XFS_ILOG_FBROOT(cur->bc_private.b.whichfork));
> 
> I don't think it is necessary at this point.

It's the only leakage of the detailed inode root implementation into
the generic code, so I'm still wondering whether a method would be
better.

Re: [PATCH 15/21] implement generic xfs_btree_rshift

[Dave Chinner]

On Fri, Aug 01, 2008 at 09:49:14PM +0200, Christoph Hellwig wrote:
> > > +				  XFS_BB_NUM_BITS, &first, &last);
> > > +		xfs_trans_log_buf(cur->bc_tp, bp, first, last);
> > > +	} else {
> > > +		/* XXX(hch): maybe factor out into a method? */
> > > +		xfs_trans_log_inode(cur->bc_tp, cur->bc_private.b.ip,
> > > +			XFS_ILOG_FBROOT(cur->bc_private.b.whichfork));
> > 
> > I don't think it is necessary at this point.
> 
> It's the only leakage of the detailed inode root implementation into
> the generic code, so I'm still wondering whether a method would be
> better.

Ah, right. yes, it probably would be cleaner to do it as a
separate method, but Ǐ don't think it's that important right now.

Cheers,

Dave.
-- 
Dave Chinner
david@fromorbit.com

Re: [PATCH 15/21] implement generic xfs_btree_rshift

[Christoph Hellwig]

On Sat, Aug 02, 2008 at 11:20:42AM +1000, Dave Chinner wrote:
> > It's the only leakage of the detailed inode root implementation into
> > the generic code, so I'm still wondering whether a method would be
> > better.
> 
> Ah, right. yes, it probably would be cleaner to do it as a
> separate method, but ?? don't think it's that important right now.

That's why I left the XXX in, this is something to get right eventually,
just not now :)