implement generic xfs_btree_rshift

Index: linux-2.6-xfs/fs/xfs/xfs_btree.c
===================================================================
@@ -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
===================================================================
@@ -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__ */
 
 

234 lines not on this page · raw message

234 lines not on this page · raw message

240 lines not on this page · raw message