[XFS] implement generic xfs_btree_rshift

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.

SGI-PV: 985583

SGI-Modid: xfs-linux-melb:xfs-kern:32196a

Signed-off-by: Christoph Hellwig <hch@infradead.org>
Signed-off-by: Lachlan McIlroy <lachlan@sgi.com>
Signed-off-by: Bill O'Donnell <billodo@sgi.com>
Signed-off-by: David Chinner <david@fromorbit.com>

5 files changed, 331 insertions, 408 deletions

diff --git a/fs/xfs/xfs_alloc_btree.c b/fs/xfs/xfs_alloc_btree.c
index c5c32999b810..31e42891fc9a 100644
--- a/fs/xfs/xfs_alloc_btree.c
+++ b/fs/xfs/xfs_alloc_btree.c
@@ -49,7 +49,6 @@ STATIC void xfs_alloc_log_ptrs(xfs_btree_cur_t *, xfs_buf_t *, int, int);
 STATIC void xfs_alloc_log_recs(xfs_btree_cur_t *, xfs_buf_t *, int, int);
 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 *);
 
@@ -391,7 +390,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) >=
@@ -683,7 +682,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 */
@@ -1233,137 +1232,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_cpu(&left->bb_numrecs, -1);
-        xfs_alloc_log_block(cur->bc_tp, lbp, XFS_BB_NUMRECS);
-        be16_add_cpu(&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).
  */
diff --git a/fs/xfs/xfs_bmap_btree.c b/fs/xfs/xfs_bmap_btree.c
index 99200a9898f7..9d18fa8aa1da 100644
--- a/fs/xfs/xfs_bmap_btree.c
+++ b/fs/xfs/xfs_bmap_btree.c
@@ -53,7 +53,6 @@ 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 *);
 
@@ -327,7 +326,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;
                         }
@@ -538,7 +537,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;
                         }
@@ -945,143 +944,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_cpu(&left->bb_numrecs, -1);
-        xfs_bmbt_log_block(cur, lbp, XFS_BB_NUMRECS);
-        be16_add_cpu(&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 */
diff --git a/fs/xfs/xfs_btree.c b/fs/xfs/xfs_btree.c
index 205272f282d9..e1a213781849 100644
--- a/fs/xfs/xfs_btree.c
+++ b/fs/xfs/xfs_btree.c
@@ -1118,6 +1118,77 @@ xfs_btree_copy_recs(
 }
 
 /*
+ * Copy block pointers from one btree block to another.
+ */
+STATIC void
+xfs_btree_copy_ptrs(
+        struct xfs_btree_cur    *cur,
+        union xfs_btree_ptr     *dst_ptr,
+        union xfs_btree_ptr     *src_ptr,
+        int                     numptrs)
+{
+        ASSERT(numptrs >= 0);
+        memcpy(dst_ptr, src_ptr, numptrs * xfs_btree_ptr_len(cur));
+}
+
+/*
+ * Shift keys one index left/right inside a single btree block.
+ */
+STATIC void
+xfs_btree_shift_keys(
+        struct xfs_btree_cur    *cur,
+        union xfs_btree_key     *key,
+        int                     dir,
+        int                     numkeys)
+{
+        char                    *dst_key;
+
+        ASSERT(numkeys >= 0);
+        ASSERT(dir == 1 || dir == -1);
+
+        dst_key = (char *)key + (dir * cur->bc_ops->key_len);
+        memmove(dst_key, key, numkeys * cur->bc_ops->key_len);
+}
+
+/*
+ * Shift records one index left/right inside a single btree block.
+ */
+STATIC void
+xfs_btree_shift_recs(
+        struct xfs_btree_cur    *cur,
+        union xfs_btree_rec     *rec,
+        int                     dir,
+        int                     numrecs)
+{
+        char                    *dst_rec;
+
+        ASSERT(numrecs >= 0);
+        ASSERT(dir == 1 || dir == -1);
+
+        dst_rec = (char *)rec + (dir * cur->bc_ops->rec_len);
+        memmove(dst_rec, rec, numrecs * cur->bc_ops->rec_len);
+}
+
+/*
+ * Shift block pointers one index left/right inside a single btree block.
+ */
+STATIC void
+xfs_btree_shift_ptrs(
+        struct xfs_btree_cur    *cur,
+        union xfs_btree_ptr     *ptr,
+        int                     dir,
+        int                     numptrs)
+{
+        char                    *dst_ptr;
+
+        ASSERT(numptrs >= 0);
+        ASSERT(dir == 1 || dir == -1);
+
+        dst_ptr = (char *)ptr + (dir * xfs_btree_ptr_len(cur));
+        memmove(dst_ptr, ptr, numptrs * xfs_btree_ptr_len(cur));
+}
+
+/*
  * Log key values from the btree block.
  */
 STATIC void
@@ -1163,6 +1234,79 @@ xfs_btree_log_recs(
 }
 
 /*
+ * 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                     first,  /* index of first pointer to log */
+        int                     last)   /* index of last pointer to log */
+{
+        XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
+        XFS_BTREE_TRACE_ARGBII(cur, bp, first, last);
+
+        if (bp) {
+                struct xfs_btree_block  *block = XFS_BUF_TO_BLOCK(bp);
+                int                     level = xfs_btree_get_level(block);
+
+                xfs_trans_log_buf(cur->bc_tp, bp,
+                                xfs_btree_ptr_offset(cur, first, level),
+                                xfs_btree_ptr_offset(cur, last + 1, level) - 1);
+        } 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 a 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 {
+                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.
  */
@@ -1368,7 +1512,6 @@ error0:
         return error;
 }
 
-
 STATIC int
 xfs_btree_lookup_get_block(
         struct xfs_btree_cur    *cur,   /* btree cursor */
@@ -1697,3 +1840,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 = xfs_btree_key_addr(cur, lrecs, left);
+                lpp = xfs_btree_ptr_addr(cur, lrecs, left);
+                rkp = xfs_btree_key_addr(cur, 1, right);
+                rpp = xfs_btree_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
+
+                xfs_btree_shift_keys(cur, rkp, 1, rrecs);
+                xfs_btree_shift_ptrs(cur, rpp, 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. */
+                xfs_btree_copy_keys(cur, rkp, lkp, 1);
+                xfs_btree_copy_ptrs(cur, rpp, lpp, 1);
+
+                xfs_btree_log_keys(cur, rbp, 1, rrecs + 1);
+                xfs_btree_log_ptrs(cur, rbp, 1, rrecs + 1);
+
+                xfs_btree_check_key(cur->bc_btnum, rkp,
+                                    xfs_btree_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 = xfs_btree_rec_addr(cur, lrecs, left);
+                rrp = xfs_btree_rec_addr(cur, 1, right);
+
+                xfs_btree_shift_recs(cur, rrp, 1, rrecs);
+
+                /* Now put the new data in, and log it. */
+                xfs_btree_copy_recs(cur, rrp, lrp, 1);
+                xfs_btree_log_recs(cur, rbp, 1, rrecs + 1);
+
+                cur->bc_ops->init_key_from_rec(&key, rrp);
+                rkp = &key;
+
+                xfs_btree_check_rec(cur->bc_btnum, rrp,
+                                    xfs_btree_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;
+}
diff --git a/fs/xfs/xfs_btree.h b/fs/xfs/xfs_btree.h
index c3bfa5556c19..04311dbeff19 100644
--- a/fs/xfs/xfs_btree.h
+++ b/fs/xfs/xfs_btree.h
@@ -533,6 +533,7 @@ int xfs_btree_decrement(struct xfs_btree_cur *, int, int *);
 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 *);
 
 /*
  * Helpers.
@@ -542,6 +543,12 @@ static inline int xfs_btree_get_numrecs(struct xfs_btree_block *block)
         return be16_to_cpu(block->bb_numrecs);
 }
 
+static inline void xfs_btree_set_numrecs(struct xfs_btree_block *block,
+                __uint16_t numrecs)
+{
+        block->bb_numrecs = cpu_to_be16(numrecs);
+}
+
 static inline int xfs_btree_get_level(struct xfs_btree_block *block)
 {
         return be16_to_cpu(block->bb_level);
diff --git a/fs/xfs/xfs_ialloc_btree.c b/fs/xfs/xfs_ialloc_btree.c
index d080a6833a8d..457f88a76e10 100644
--- a/fs/xfs/xfs_ialloc_btree.c
+++ b/fs/xfs/xfs_ialloc_btree.c
@@ -45,7 +45,6 @@ STATIC void xfs_inobt_log_ptrs(xfs_btree_cur_t *, xfs_buf_t *, int, int);
 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 *);
 
@@ -337,7 +336,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) >=
@@ -608,7 +607,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 */
@@ -1117,136 +1116,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_cpu(&left->bb_numrecs, -1);
-        xfs_inobt_log_block(cur->bc_tp, lbp, XFS_BB_NUMRECS);
-        be16_add_cpu(&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).
  */