Pileus Git - ~andy/linux/blob - fs/xfs/xfs_btree.c

   1 /*
   2  * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc.
   3  * All Rights Reserved.
   4  *
   5  * This program is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU General Public License as
   7  * published by the Free Software Foundation.
   8  *
   9  * This program is distributed in the hope that it would be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write the Free Software Foundation,
  16  * Inc.,  51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  17  */
  18 #include "xfs.h"
  19 #include "xfs_fs.h"
  20 #include "xfs_types.h"
  21 #include "xfs_bit.h"
  22 #include "xfs_log.h"
  23 #include "xfs_inum.h"
  24 #include "xfs_trans.h"
  25 #include "xfs_sb.h"
  26 #include "xfs_ag.h"
  27 #include "xfs_dir2.h"
  28 #include "xfs_dmapi.h"
  29 #include "xfs_mount.h"
  30 #include "xfs_bmap_btree.h"
  31 #include "xfs_alloc_btree.h"
  32 #include "xfs_ialloc_btree.h"
  33 #include "xfs_dir2_sf.h"
  34 #include "xfs_attr_sf.h"
  35 #include "xfs_dinode.h"
  36 #include "xfs_inode.h"
  37 #include "xfs_inode_item.h"
  38 #include "xfs_btree.h"
  39 #include "xfs_btree_trace.h"
  40 #include "xfs_ialloc.h"
  41 #include "xfs_error.h"
  42
  43 /*
  44  * Cursor allocation zone.
  45  */
  46 kmem_zone_t     *xfs_btree_cur_zone;
  47
  48 /*
  49  * Btree magic numbers.
  50  */
  51 const __uint32_t xfs_magics[XFS_BTNUM_MAX] = {
  52         XFS_ABTB_MAGIC, XFS_ABTC_MAGIC, XFS_BMAP_MAGIC, XFS_IBT_MAGIC
  53 };
  54
  55
  56 int                                     /* error (0 or EFSCORRUPTED) */
  57 xfs_btree_check_lblock(
  58         struct xfs_btree_cur    *cur,   /* btree cursor */
  59         struct xfs_btree_lblock *block, /* btree long form block pointer */
  60         int                     level,  /* level of the btree block */
  61         struct xfs_buf          *bp)    /* buffer for block, if any */
  62 {
  63         int                     lblock_ok; /* block passes checks */
  64         struct xfs_mount        *mp;    /* file system mount point */
  65
  66         mp = cur->bc_mp;
  67         lblock_ok =
  68                 be32_to_cpu(block->bb_magic) == xfs_magics[cur->bc_btnum] &&
  69                 be16_to_cpu(block->bb_level) == level &&
  70                 be16_to_cpu(block->bb_numrecs) <=
  71                         cur->bc_ops->get_maxrecs(cur, level) &&
  72                 block->bb_leftsib &&
  73                 (be64_to_cpu(block->bb_leftsib) == NULLDFSBNO ||
  74                  XFS_FSB_SANITY_CHECK(mp, be64_to_cpu(block->bb_leftsib))) &&
  75                 block->bb_rightsib &&
  76                 (be64_to_cpu(block->bb_rightsib) == NULLDFSBNO ||
  77                  XFS_FSB_SANITY_CHECK(mp, be64_to_cpu(block->bb_rightsib)));
  78         if (unlikely(XFS_TEST_ERROR(!lblock_ok, mp,
  79                         XFS_ERRTAG_BTREE_CHECK_LBLOCK,
  80                         XFS_RANDOM_BTREE_CHECK_LBLOCK))) {
  81                 if (bp)
  82                         xfs_buftrace("LBTREE ERROR", bp);
  83                 XFS_ERROR_REPORT("xfs_btree_check_lblock", XFS_ERRLEVEL_LOW,
  84                                  mp);
  85                 return XFS_ERROR(EFSCORRUPTED);
  86         }
  87         return 0;
  88 }
  89
  90 STATIC int                              /* error (0 or EFSCORRUPTED) */
  91 xfs_btree_check_sblock(
  92         struct xfs_btree_cur    *cur,   /* btree cursor */
  93         struct xfs_btree_sblock *block, /* btree short form block pointer */
  94         int                     level,  /* level of the btree block */
  95         struct xfs_buf          *bp)    /* buffer containing block */
  96 {
  97         struct xfs_buf          *agbp;  /* buffer for ag. freespace struct */
  98         struct xfs_agf          *agf;   /* ag. freespace structure */
  99         xfs_agblock_t           agflen; /* native ag. freespace length */
 100         int                     sblock_ok; /* block passes checks */
 101
 102         agbp = cur->bc_private.a.agbp;
 103         agf = XFS_BUF_TO_AGF(agbp);
 104         agflen = be32_to_cpu(agf->agf_length);
 105         sblock_ok =
 106                 be32_to_cpu(block->bb_magic) == xfs_magics[cur->bc_btnum] &&
 107                 be16_to_cpu(block->bb_level) == level &&
 108                 be16_to_cpu(block->bb_numrecs) <=
 109                         cur->bc_ops->get_maxrecs(cur, level) &&
 110                 (be32_to_cpu(block->bb_leftsib) == NULLAGBLOCK ||
 111                  be32_to_cpu(block->bb_leftsib) < agflen) &&
 112                 block->bb_leftsib &&
 113                 (be32_to_cpu(block->bb_rightsib) == NULLAGBLOCK ||
 114                  be32_to_cpu(block->bb_rightsib) < agflen) &&
 115                 block->bb_rightsib;
 116         if (unlikely(XFS_TEST_ERROR(!sblock_ok, cur->bc_mp,
 117                         XFS_ERRTAG_BTREE_CHECK_SBLOCK,
 118                         XFS_RANDOM_BTREE_CHECK_SBLOCK))) {
 119                 if (bp)
 120                         xfs_buftrace("SBTREE ERROR", bp);
 121                 XFS_ERROR_REPORT("xfs_btree_check_sblock", XFS_ERRLEVEL_LOW,
 122                                  cur->bc_mp);
 123                 return XFS_ERROR(EFSCORRUPTED);
 124         }
 125         return 0;
 126 }
 127
 128 /*
 129  * Debug routine: check that block header is ok.
 130  */
 131 int
 132 xfs_btree_check_block(
 133         struct xfs_btree_cur    *cur,   /* btree cursor */
 134         struct xfs_btree_block  *block, /* generic btree block pointer */
 135         int                     level,  /* level of the btree block */
 136         struct xfs_buf          *bp)    /* buffer containing block, if any */
 137 {
 138         if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
 139                 return xfs_btree_check_lblock(cur,
 140                                 (struct xfs_btree_lblock *)block, level, bp);
 141         } else {
 142                 return xfs_btree_check_sblock(cur,
 143                                 (struct xfs_btree_sblock *)block, level, bp);
 144         }
 145 }
 146
 147 /*
 148  * Check that (long) pointer is ok.
 149  */
 150 int                                     /* error (0 or EFSCORRUPTED) */
 151 xfs_btree_check_lptr(
 152         struct xfs_btree_cur    *cur,   /* btree cursor */
 153         xfs_dfsbno_t            bno,    /* btree block disk address */
 154         int                     level)  /* btree block level */
 155 {
 156         XFS_WANT_CORRUPTED_RETURN(
 157                 level > 0 &&
 158                 bno != NULLDFSBNO &&
 159                 XFS_FSB_SANITY_CHECK(cur->bc_mp, bno));
 160         return 0;
 161 }
 162
 163 /*
 164  * Check that (short) pointer is ok.
 165  */
 166 STATIC int                              /* error (0 or EFSCORRUPTED) */
 167 xfs_btree_check_sptr(
 168         struct xfs_btree_cur    *cur,   /* btree cursor */
 169         xfs_agblock_t           bno,    /* btree block disk address */
 170         int                     level)  /* btree block level */
 171 {
 172         xfs_agblock_t           agblocks = cur->bc_mp->m_sb.sb_agblocks;
 173
 174         XFS_WANT_CORRUPTED_RETURN(
 175                 level > 0 &&
 176                 bno != NULLAGBLOCK &&
 177                 bno != 0 &&
 178                 bno < agblocks);
 179         return 0;
 180 }
 181
 182 /*
 183  * Check that block ptr is ok.
 184  */
 185 STATIC int                              /* error (0 or EFSCORRUPTED) */
 186 xfs_btree_check_ptr(
 187         struct xfs_btree_cur    *cur,   /* btree cursor */
 188         union xfs_btree_ptr     *ptr,   /* btree block disk address */
 189         int                     index,  /* offset from ptr to check */
 190         int                     level)  /* btree block level */
 191 {
 192         if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
 193                 return xfs_btree_check_lptr(cur,
 194                                 be64_to_cpu((&ptr->l)[index]), level);
 195         } else {
 196                 return xfs_btree_check_sptr(cur,
 197                                 be32_to_cpu((&ptr->s)[index]), level);
 198         }
 199 }
 200
 201 /*
 202  * Delete the btree cursor.
 203  */
 204 void
 205 xfs_btree_del_cursor(
 206         xfs_btree_cur_t *cur,           /* btree cursor */
 207         int             error)          /* del because of error */
 208 {
 209         int             i;              /* btree level */
 210
 211         /*
 212          * Clear the buffer pointers, and release the buffers.
 213          * If we're doing this in the face of an error, we
 214          * need to make sure to inspect all of the entries
 215          * in the bc_bufs array for buffers to be unlocked.
 216          * This is because some of the btree code works from
 217          * level n down to 0, and if we get an error along
 218          * the way we won't have initialized all the entries
 219          * down to 0.
 220          */
 221         for (i = 0; i < cur->bc_nlevels; i++) {
 222                 if (cur->bc_bufs[i])
 223                         xfs_btree_setbuf(cur, i, NULL);
 224                 else if (!error)
 225                         break;
 226         }
 227         /*
 228          * Can't free a bmap cursor without having dealt with the
 229          * allocated indirect blocks' accounting.
 230          */
 231         ASSERT(cur->bc_btnum != XFS_BTNUM_BMAP ||
 232                cur->bc_private.b.allocated == 0);
 233         /*
 234          * Free the cursor.
 235          */
 236         kmem_zone_free(xfs_btree_cur_zone, cur);
 237 }
 238
 239 /*
 240  * Duplicate the btree cursor.
 241  * Allocate a new one, copy the record, re-get the buffers.
 242  */
 243 int                                     /* error */
 244 xfs_btree_dup_cursor(
 245         xfs_btree_cur_t *cur,           /* input cursor */
 246         xfs_btree_cur_t **ncur)         /* output cursor */
 247 {
 248         xfs_buf_t       *bp;            /* btree block's buffer pointer */
 249         int             error;          /* error return value */
 250         int             i;              /* level number of btree block */
 251         xfs_mount_t     *mp;            /* mount structure for filesystem */
 252         xfs_btree_cur_t *new;           /* new cursor value */
 253         xfs_trans_t     *tp;            /* transaction pointer, can be NULL */
 254
 255         tp = cur->bc_tp;
 256         mp = cur->bc_mp;
 257
 258         /*
 259          * Allocate a new cursor like the old one.
 260          */
 261         new = cur->bc_ops->dup_cursor(cur);
 262
 263         /*
 264          * Copy the record currently in the cursor.
 265          */
 266         new->bc_rec = cur->bc_rec;
 267
 268         /*
 269          * For each level current, re-get the buffer and copy the ptr value.
 270          */
 271         for (i = 0; i < new->bc_nlevels; i++) {
 272                 new->bc_ptrs[i] = cur->bc_ptrs[i];
 273                 new->bc_ra[i] = cur->bc_ra[i];
 274                 if ((bp = cur->bc_bufs[i])) {
 275                         if ((error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp,
 276                                 XFS_BUF_ADDR(bp), mp->m_bsize, 0, &bp))) {
 277                                 xfs_btree_del_cursor(new, error);
 278                                 *ncur = NULL;
 279                                 return error;
 280                         }
 281                         new->bc_bufs[i] = bp;
 282                         ASSERT(bp);
 283                         ASSERT(!XFS_BUF_GETERROR(bp));
 284                 } else
 285                         new->bc_bufs[i] = NULL;
 286         }
 287         *ncur = new;
 288         return 0;
 289 }
 290
 291 /*
 292  * XFS btree block layout and addressing:
 293  *
 294  * There are two types of blocks in the btree: leaf and non-leaf blocks.
 295  *
 296  * The leaf record start with a header then followed by records containing
 297  * the values.  A non-leaf block also starts with the same header, and
 298  * then first contains lookup keys followed by an equal number of pointers
 299  * to the btree blocks at the previous level.
 300  *
 301  *              +--------+-------+-------+-------+-------+-------+-------+
 302  * Leaf:        | header | rec 1 | rec 2 | rec 3 | rec 4 | rec 5 | rec N |
 303  *              +--------+-------+-------+-------+-------+-------+-------+
 304  *
 305  *              +--------+-------+-------+-------+-------+-------+-------+
 306  * Non-Leaf:    | header | key 1 | key 2 | key N | ptr 1 | ptr 2 | ptr N |
 307  *              +--------+-------+-------+-------+-------+-------+-------+
 308  *
 309  * The header is called struct xfs_btree_block for reasons better left unknown
 310  * and comes in different versions for short (32bit) and long (64bit) block
 311  * pointers.  The record and key structures are defined by the btree instances
 312  * and opaque to the btree core.  The block pointers are simple disk endian
 313  * integers, available in a short (32bit) and long (64bit) variant.
 314  *
 315  * The helpers below calculate the offset of a given record, key or pointer
 316  * into a btree block (xfs_btree_*_offset) or return a pointer to the given
 317  * record, key or pointer (xfs_btree_*_addr).  Note that all addressing
 318  * inside the btree block is done using indices starting at one, not zero!
 319  */
 320
 321 /*
 322  * Return size of the btree block header for this btree instance.
 323  */
 324 static inline size_t xfs_btree_block_len(struct xfs_btree_cur *cur)
 325 {
 326         return (cur->bc_flags & XFS_BTREE_LONG_PTRS) ?
 327                 sizeof(struct xfs_btree_lblock) :
 328                 sizeof(struct xfs_btree_sblock);
 329 }
 330
 331 /*
 332  * Return size of btree block pointers for this btree instance.
 333  */
 334 static inline size_t xfs_btree_ptr_len(struct xfs_btree_cur *cur)
 335 {
 336         return (cur->bc_flags & XFS_BTREE_LONG_PTRS) ?
 337                 sizeof(__be64) : sizeof(__be32);
 338 }
 339
 340 /*
 341  * Calculate offset of the n-th record in a btree block.
 342  */
 343 STATIC size_t
 344 xfs_btree_rec_offset(
 345         struct xfs_btree_cur    *cur,
 346         int                     n)
 347 {
 348         return xfs_btree_block_len(cur) +
 349                 (n - 1) * cur->bc_ops->rec_len;
 350 }
 351
 352 /*
 353  * Calculate offset of the n-th key in a btree block.
 354  */
 355 STATIC size_t
 356 xfs_btree_key_offset(
 357         struct xfs_btree_cur    *cur,
 358         int                     n)
 359 {
 360         return xfs_btree_block_len(cur) +
 361                 (n - 1) * cur->bc_ops->key_len;
 362 }
 363
 364 /*
 365  * Calculate offset of the n-th block pointer in a btree block.
 366  */
 367 STATIC size_t
 368 xfs_btree_ptr_offset(
 369         struct xfs_btree_cur    *cur,
 370         int                     n,
 371         int                     level)
 372 {
 373         return xfs_btree_block_len(cur) +
 374                 cur->bc_ops->get_maxrecs(cur, level) * cur->bc_ops->key_len +
 375                 (n - 1) * xfs_btree_ptr_len(cur);
 376 }
 377
 378 /*
 379  * Return a pointer to the n-th record in the btree block.
 380  */
 381 STATIC union xfs_btree_rec *
 382 xfs_btree_rec_addr(
 383         struct xfs_btree_cur    *cur,
 384         int                     n,
 385         struct xfs_btree_block  *block)
 386 {
 387         return (union xfs_btree_rec *)
 388                 ((char *)block + xfs_btree_rec_offset(cur, n));
 389 }
 390
 391 /*
 392  * Return a pointer to the n-th key in the btree block.
 393  */
 394 STATIC union xfs_btree_key *
 395 xfs_btree_key_addr(
 396         struct xfs_btree_cur    *cur,
 397         int                     n,
 398         struct xfs_btree_block  *block)
 399 {
 400         return (union xfs_btree_key *)
 401                 ((char *)block + xfs_btree_key_offset(cur, n));
 402 }
 403
 404 /*
 405  * Return a pointer to the n-th block pointer in the btree block.
 406  */
 407 STATIC union xfs_btree_ptr *
 408 xfs_btree_ptr_addr(
 409         struct xfs_btree_cur    *cur,
 410         int                     n,
 411         struct xfs_btree_block  *block)
 412 {
 413         int                     level = xfs_btree_get_level(block);
 414
 415         ASSERT(block->bb_level != 0);
 416
 417         return (union xfs_btree_ptr *)
 418                 ((char *)block + xfs_btree_ptr_offset(cur, n, level));
 419 }
 420
 421 /*
 422  * Get a the root block which is stored in the inode.
 423  *
 424  * For now this btree implementation assumes the btree root is always
 425  * stored in the if_broot field of an inode fork.
 426  */
 427 STATIC struct xfs_btree_block *
 428 xfs_btree_get_iroot(
 429        struct xfs_btree_cur    *cur)
 430 {
 431        struct xfs_ifork        *ifp;
 432
 433        ifp = XFS_IFORK_PTR(cur->bc_private.b.ip, cur->bc_private.b.whichfork);
 434        return (struct xfs_btree_block *)ifp->if_broot;
 435 }
 436
 437 /*
 438  * Retrieve the block pointer from the cursor at the given level.
 439  * This may be an inode btree root or from a buffer.
 440  */
 441 STATIC struct xfs_btree_block *         /* generic btree block pointer */
 442 xfs_btree_get_block(
 443         struct xfs_btree_cur    *cur,   /* btree cursor */
 444         int                     level,  /* level in btree */
 445         struct xfs_buf          **bpp)  /* buffer containing the block */
 446 {
 447         if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
 448             (level == cur->bc_nlevels - 1)) {
 449                 *bpp = NULL;
 450                 return xfs_btree_get_iroot(cur);
 451         }
 452
 453         *bpp = cur->bc_bufs[level];
 454         return XFS_BUF_TO_BLOCK(*bpp);
 455 }
 456
 457 /*
 458  * Get a buffer for the block, return it with no data read.
 459  * Long-form addressing.
 460  */
 461 xfs_buf_t *                             /* buffer for fsbno */
 462 xfs_btree_get_bufl(
 463         xfs_mount_t     *mp,            /* file system mount point */
 464         xfs_trans_t     *tp,            /* transaction pointer */
 465         xfs_fsblock_t   fsbno,          /* file system block number */
 466         uint            lock)           /* lock flags for get_buf */
 467 {
 468         xfs_buf_t       *bp;            /* buffer pointer (return value) */
 469         xfs_daddr_t             d;              /* real disk block address */
 470
 471         ASSERT(fsbno != NULLFSBLOCK);
 472         d = XFS_FSB_TO_DADDR(mp, fsbno);
 473         bp = xfs_trans_get_buf(tp, mp->m_ddev_targp, d, mp->m_bsize, lock);
 474         ASSERT(bp);
 475         ASSERT(!XFS_BUF_GETERROR(bp));
 476         return bp;
 477 }
 478
 479 /*
 480  * Get a buffer for the block, return it with no data read.
 481  * Short-form addressing.
 482  */
 483 xfs_buf_t *                             /* buffer for agno/agbno */
 484 xfs_btree_get_bufs(
 485         xfs_mount_t     *mp,            /* file system mount point */
 486         xfs_trans_t     *tp,            /* transaction pointer */
 487         xfs_agnumber_t  agno,           /* allocation group number */
 488         xfs_agblock_t   agbno,          /* allocation group block number */
 489         uint            lock)           /* lock flags for get_buf */
 490 {
 491         xfs_buf_t       *bp;            /* buffer pointer (return value) */
 492         xfs_daddr_t             d;              /* real disk block address */
 493
 494         ASSERT(agno != NULLAGNUMBER);
 495         ASSERT(agbno != NULLAGBLOCK);
 496         d = XFS_AGB_TO_DADDR(mp, agno, agbno);
 497         bp = xfs_trans_get_buf(tp, mp->m_ddev_targp, d, mp->m_bsize, lock);
 498         ASSERT(bp);
 499         ASSERT(!XFS_BUF_GETERROR(bp));
 500         return bp;
 501 }
 502
 503 /*
 504  * Check for the cursor referring to the last block at the given level.
 505  */
 506 int                                     /* 1=is last block, 0=not last block */
 507 xfs_btree_islastblock(
 508         xfs_btree_cur_t         *cur,   /* btree cursor */
 509         int                     level)  /* level to check */
 510 {
 511         xfs_btree_block_t       *block; /* generic btree block pointer */
 512         xfs_buf_t               *bp;    /* buffer containing block */
 513
 514         block = xfs_btree_get_block(cur, level, &bp);
 515         xfs_btree_check_block(cur, block, level, bp);
 516         if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
 517                 return be64_to_cpu(block->bb_u.l.bb_rightsib) == NULLDFSBNO;
 518         else
 519                 return be32_to_cpu(block->bb_u.s.bb_rightsib) == NULLAGBLOCK;
 520 }
 521
 522 /*
 523  * Change the cursor to point to the first record at the given level.
 524  * Other levels are unaffected.
 525  */
 526 STATIC int                              /* success=1, failure=0 */
 527 xfs_btree_firstrec(
 528         xfs_btree_cur_t         *cur,   /* btree cursor */
 529         int                     level)  /* level to change */
 530 {
 531         xfs_btree_block_t       *block; /* generic btree block pointer */
 532         xfs_buf_t               *bp;    /* buffer containing block */
 533
 534         /*
 535          * Get the block pointer for this level.
 536          */
 537         block = xfs_btree_get_block(cur, level, &bp);
 538         xfs_btree_check_block(cur, block, level, bp);
 539         /*
 540          * It's empty, there is no such record.
 541          */
 542         if (!block->bb_numrecs)
 543                 return 0;
 544         /*
 545          * Set the ptr value to 1, that's the first record/key.
 546          */
 547         cur->bc_ptrs[level] = 1;
 548         return 1;
 549 }
 550
 551 /*
 552  * Change the cursor to point to the last record in the current block
 553  * at the given level.  Other levels are unaffected.
 554  */
 555 STATIC int                              /* success=1, failure=0 */
 556 xfs_btree_lastrec(
 557         xfs_btree_cur_t         *cur,   /* btree cursor */
 558         int                     level)  /* level to change */
 559 {
 560         xfs_btree_block_t       *block; /* generic btree block pointer */
 561         xfs_buf_t               *bp;    /* buffer containing block */
 562
 563         /*
 564          * Get the block pointer for this level.
 565          */
 566         block = xfs_btree_get_block(cur, level, &bp);
 567         xfs_btree_check_block(cur, block, level, bp);
 568         /*
 569          * It's empty, there is no such record.
 570          */
 571         if (!block->bb_numrecs)
 572                 return 0;
 573         /*
 574          * Set the ptr value to numrecs, that's the last record/key.
 575          */
 576         cur->bc_ptrs[level] = be16_to_cpu(block->bb_numrecs);
 577         return 1;
 578 }
 579
 580 /*
 581  * Compute first and last byte offsets for the fields given.
 582  * Interprets the offsets table, which contains struct field offsets.
 583  */
 584 void
 585 xfs_btree_offsets(
 586         __int64_t       fields,         /* bitmask of fields */
 587         const short     *offsets,       /* table of field offsets */
 588         int             nbits,          /* number of bits to inspect */
 589         int             *first,         /* output: first byte offset */
 590         int             *last)          /* output: last byte offset */
 591 {
 592         int             i;              /* current bit number */
 593         __int64_t       imask;          /* mask for current bit number */
 594
 595         ASSERT(fields != 0);
 596         /*
 597          * Find the lowest bit, so the first byte offset.
 598          */
 599         for (i = 0, imask = 1LL; ; i++, imask <<= 1) {
 600                 if (imask & fields) {
 601                         *first = offsets[i];
 602                         break;
 603                 }
 604         }
 605         /*
 606          * Find the highest bit, so the last byte offset.
 607          */
 608         for (i = nbits - 1, imask = 1LL << i; ; i--, imask >>= 1) {
 609                 if (imask & fields) {
 610                         *last = offsets[i + 1] - 1;
 611                         break;
 612                 }
 613         }
 614 }
 615
 616 /*
 617  * Get a buffer for the block, return it read in.
 618  * Long-form addressing.
 619  */
 620 int                                     /* error */
 621 xfs_btree_read_bufl(
 622         xfs_mount_t     *mp,            /* file system mount point */
 623         xfs_trans_t     *tp,            /* transaction pointer */
 624         xfs_fsblock_t   fsbno,          /* file system block number */
 625         uint            lock,           /* lock flags for read_buf */
 626         xfs_buf_t       **bpp,          /* buffer for fsbno */
 627         int             refval)         /* ref count value for buffer */
 628 {
 629         xfs_buf_t       *bp;            /* return value */
 630         xfs_daddr_t             d;              /* real disk block address */
 631         int             error;
 632
 633         ASSERT(fsbno != NULLFSBLOCK);
 634         d = XFS_FSB_TO_DADDR(mp, fsbno);
 635         if ((error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp, d,
 636                         mp->m_bsize, lock, &bp))) {
 637                 return error;
 638         }
 639         ASSERT(!bp || !XFS_BUF_GETERROR(bp));
 640         if (bp != NULL) {
 641                 XFS_BUF_SET_VTYPE_REF(bp, B_FS_MAP, refval);
 642         }
 643         *bpp = bp;
 644         return 0;
 645 }
 646
 647 /*
 648  * Get a buffer for the block, return it read in.
 649  * Short-form addressing.
 650  */
 651 int                                     /* error */
 652 xfs_btree_read_bufs(
 653         xfs_mount_t     *mp,            /* file system mount point */
 654         xfs_trans_t     *tp,            /* transaction pointer */
 655         xfs_agnumber_t  agno,           /* allocation group number */
 656         xfs_agblock_t   agbno,          /* allocation group block number */
 657         uint            lock,           /* lock flags for read_buf */
 658         xfs_buf_t       **bpp,          /* buffer for agno/agbno */
 659         int             refval)         /* ref count value for buffer */
 660 {
 661         xfs_buf_t       *bp;            /* return value */
 662         xfs_daddr_t     d;              /* real disk block address */
 663         int             error;
 664
 665         ASSERT(agno != NULLAGNUMBER);
 666         ASSERT(agbno != NULLAGBLOCK);
 667         d = XFS_AGB_TO_DADDR(mp, agno, agbno);
 668         if ((error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp, d,
 669                                         mp->m_bsize, lock, &bp))) {
 670                 return error;
 671         }
 672         ASSERT(!bp || !XFS_BUF_GETERROR(bp));
 673         if (bp != NULL) {
 674                 switch (refval) {
 675                 case XFS_ALLOC_BTREE_REF:
 676                         XFS_BUF_SET_VTYPE_REF(bp, B_FS_MAP, refval);
 677                         break;
 678                 case XFS_INO_BTREE_REF:
 679                         XFS_BUF_SET_VTYPE_REF(bp, B_FS_INOMAP, refval);
 680                         break;
 681                 }
 682         }
 683         *bpp = bp;
 684         return 0;
 685 }
 686
 687 /*
 688  * Read-ahead the block, don't wait for it, don't return a buffer.
 689  * Long-form addressing.
 690  */
 691 /* ARGSUSED */
 692 void
 693 xfs_btree_reada_bufl(
 694         xfs_mount_t     *mp,            /* file system mount point */
 695         xfs_fsblock_t   fsbno,          /* file system block number */
 696         xfs_extlen_t    count)          /* count of filesystem blocks */
 697 {
 698         xfs_daddr_t             d;
 699
 700         ASSERT(fsbno != NULLFSBLOCK);
 701         d = XFS_FSB_TO_DADDR(mp, fsbno);
 702         xfs_baread(mp->m_ddev_targp, d, mp->m_bsize * count);
 703 }
 704
 705 /*
 706  * Read-ahead the block, don't wait for it, don't return a buffer.
 707  * Short-form addressing.
 708  */
 709 /* ARGSUSED */
 710 void
 711 xfs_btree_reada_bufs(
 712         xfs_mount_t     *mp,            /* file system mount point */
 713         xfs_agnumber_t  agno,           /* allocation group number */
 714         xfs_agblock_t   agbno,          /* allocation group block number */
 715         xfs_extlen_t    count)          /* count of filesystem blocks */
 716 {
 717         xfs_daddr_t             d;
 718
 719         ASSERT(agno != NULLAGNUMBER);
 720         ASSERT(agbno != NULLAGBLOCK);
 721         d = XFS_AGB_TO_DADDR(mp, agno, agbno);
 722         xfs_baread(mp->m_ddev_targp, d, mp->m_bsize * count);
 723 }
 724
 725 STATIC int
 726 xfs_btree_readahead_lblock(
 727         struct xfs_btree_cur    *cur,
 728         int                     lr,
 729         struct xfs_btree_block  *block)
 730 {
 731         int                     rval = 0;
 732         xfs_fsblock_t           left = be64_to_cpu(block->bb_u.l.bb_leftsib);
 733         xfs_fsblock_t           right = be64_to_cpu(block->bb_u.l.bb_rightsib);
 734
 735         if ((lr & XFS_BTCUR_LEFTRA) && left != NULLDFSBNO) {
 736                 xfs_btree_reada_bufl(cur->bc_mp, left, 1);
 737                 rval++;
 738         }
 739
 740         if ((lr & XFS_BTCUR_RIGHTRA) && right != NULLDFSBNO) {
 741                 xfs_btree_reada_bufl(cur->bc_mp, right, 1);
 742                 rval++;
 743         }
 744
 745         return rval;
 746 }
 747
 748 STATIC int
 749 xfs_btree_readahead_sblock(
 750         struct xfs_btree_cur    *cur,
 751         int                     lr,
 752         struct xfs_btree_block *block)
 753 {
 754         int                     rval = 0;
 755         xfs_agblock_t           left = be32_to_cpu(block->bb_u.s.bb_leftsib);
 756         xfs_agblock_t           right = be32_to_cpu(block->bb_u.s.bb_rightsib);
 757
 758
 759         if ((lr & XFS_BTCUR_LEFTRA) && left != NULLAGBLOCK) {
 760                 xfs_btree_reada_bufs(cur->bc_mp, cur->bc_private.a.agno,
 761                                      left, 1);
 762                 rval++;
 763         }
 764
 765         if ((lr & XFS_BTCUR_RIGHTRA) && right != NULLAGBLOCK) {
 766                 xfs_btree_reada_bufs(cur->bc_mp, cur->bc_private.a.agno,
 767                                      right, 1);
 768                 rval++;
 769         }
 770
 771         return rval;
 772 }
 773
 774 /*
 775  * Read-ahead btree blocks, at the given level.
 776  * Bits in lr are set from XFS_BTCUR_{LEFT,RIGHT}RA.
 777  */
 778 STATIC int
 779 xfs_btree_readahead(
 780         struct xfs_btree_cur    *cur,           /* btree cursor */
 781         int                     lev,            /* level in btree */
 782         int                     lr)             /* left/right bits */
 783 {
 784         struct xfs_btree_block  *block;
 785
 786         /*
 787          * No readahead needed if we are at the root level and the
 788          * btree root is stored in the inode.
 789          */
 790         if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
 791             (lev == cur->bc_nlevels - 1))
 792                 return 0;
 793
 794         if ((cur->bc_ra[lev] | lr) == cur->bc_ra[lev])
 795                 return 0;
 796
 797         cur->bc_ra[lev] |= lr;
 798         block = XFS_BUF_TO_BLOCK(cur->bc_bufs[lev]);
 799
 800         if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
 801                 return xfs_btree_readahead_lblock(cur, lr, block);
 802         return xfs_btree_readahead_sblock(cur, lr, block);
 803 }
 804
 805 /*
 806  * Set the buffer for level "lev" in the cursor to bp, releasing
 807  * any previous buffer.
 808  */
 809 void
 810 xfs_btree_setbuf(
 811         xfs_btree_cur_t         *cur,   /* btree cursor */
 812         int                     lev,    /* level in btree */
 813         xfs_buf_t               *bp)    /* new buffer to set */
 814 {
 815         xfs_btree_block_t       *b;     /* btree block */
 816         xfs_buf_t               *obp;   /* old buffer pointer */
 817
 818         obp = cur->bc_bufs[lev];
 819         if (obp)
 820                 xfs_trans_brelse(cur->bc_tp, obp);
 821         cur->bc_bufs[lev] = bp;
 822         cur->bc_ra[lev] = 0;
 823         if (!bp)
 824                 return;
 825         b = XFS_BUF_TO_BLOCK(bp);
 826         if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
 827                 if (be64_to_cpu(b->bb_u.l.bb_leftsib) == NULLDFSBNO)
 828                         cur->bc_ra[lev] |= XFS_BTCUR_LEFTRA;
 829                 if (be64_to_cpu(b->bb_u.l.bb_rightsib) == NULLDFSBNO)
 830                         cur->bc_ra[lev] |= XFS_BTCUR_RIGHTRA;
 831         } else {
 832                 if (be32_to_cpu(b->bb_u.s.bb_leftsib) == NULLAGBLOCK)
 833                         cur->bc_ra[lev] |= XFS_BTCUR_LEFTRA;
 834                 if (be32_to_cpu(b->bb_u.s.bb_rightsib) == NULLAGBLOCK)
 835                         cur->bc_ra[lev] |= XFS_BTCUR_RIGHTRA;
 836         }
 837 }
 838
 839 STATIC int
 840 xfs_btree_ptr_is_null(
 841         struct xfs_btree_cur    *cur,
 842         union xfs_btree_ptr     *ptr)
 843 {
 844         if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
 845                 return be64_to_cpu(ptr->l) == NULLFSBLOCK;
 846         else
 847                 return be32_to_cpu(ptr->s) == NULLAGBLOCK;
 848 }
 849
 850 STATIC void
 851 xfs_btree_set_ptr_null(
 852         struct xfs_btree_cur    *cur,
 853         union xfs_btree_ptr     *ptr)
 854 {
 855         if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
 856                 ptr->l = cpu_to_be64(NULLFSBLOCK);
 857         else
 858                 ptr->s = cpu_to_be32(NULLAGBLOCK);
 859 }
 860
 861 /*
 862  * Get/set/init sibling pointers
 863  */
 864 STATIC void
 865 xfs_btree_get_sibling(
 866         struct xfs_btree_cur    *cur,
 867         struct xfs_btree_block  *block,
 868         union xfs_btree_ptr     *ptr,
 869         int                     lr)
 870 {
 871         ASSERT(lr == XFS_BB_LEFTSIB || lr == XFS_BB_RIGHTSIB);
 872
 873         if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
 874                 if (lr == XFS_BB_RIGHTSIB)
 875                         ptr->l = block->bb_u.l.bb_rightsib;
 876                 else
 877                         ptr->l = block->bb_u.l.bb_leftsib;
 878         } else {
 879                 if (lr == XFS_BB_RIGHTSIB)
 880                         ptr->s = block->bb_u.s.bb_rightsib;
 881                 else
 882                         ptr->s = block->bb_u.s.bb_leftsib;
 883         }
 884 }
 885
 886 STATIC void
 887 xfs_btree_set_sibling(
 888         struct xfs_btree_cur    *cur,
 889         struct xfs_btree_block  *block,
 890         union xfs_btree_ptr     *ptr,
 891         int                     lr)
 892 {
 893         ASSERT(lr == XFS_BB_LEFTSIB || lr == XFS_BB_RIGHTSIB);
 894
 895         if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
 896                 if (lr == XFS_BB_RIGHTSIB)
 897                         block->bb_u.l.bb_rightsib = ptr->l;
 898                 else
 899                         block->bb_u.l.bb_leftsib = ptr->l;
 900         } else {
 901                 if (lr == XFS_BB_RIGHTSIB)
 902                         block->bb_u.s.bb_rightsib = ptr->s;
 903                 else
 904                         block->bb_u.s.bb_leftsib = ptr->s;
 905         }
 906 }
 907
 908 STATIC void
 909 xfs_btree_init_block(
 910         struct xfs_btree_cur    *cur,
 911         int                     level,
 912         int                     numrecs,
 913         struct xfs_btree_block  *new)   /* new block */
 914 {
 915         new->bb_magic = cpu_to_be32(xfs_magics[cur->bc_btnum]);
 916         new->bb_level = cpu_to_be16(level);
 917         new->bb_numrecs = cpu_to_be16(numrecs);
 918
 919         if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
 920                 new->bb_u.l.bb_leftsib = cpu_to_be64(NULLFSBLOCK);
 921                 new->bb_u.l.bb_rightsib = cpu_to_be64(NULLFSBLOCK);
 922         } else {
 923                 new->bb_u.s.bb_leftsib = cpu_to_be32(NULLAGBLOCK);
 924                 new->bb_u.s.bb_rightsib = cpu_to_be32(NULLAGBLOCK);
 925         }
 926 }
 927
 928 /*
 929  * Return true if ptr is the last record in the btree and
 930  * we need to track updateѕ to this record.  The decision
 931  * will be further refined in the update_lastrec method.
 932  */
 933 STATIC int
 934 xfs_btree_is_lastrec(
 935         struct xfs_btree_cur    *cur,
 936         struct xfs_btree_block  *block,
 937         int                     level)
 938 {
 939         union xfs_btree_ptr     ptr;
 940
 941         if (level > 0)
 942                 return 0;
 943         if (!(cur->bc_flags & XFS_BTREE_LASTREC_UPDATE))
 944                 return 0;
 945
 946         xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB);
 947         if (!xfs_btree_ptr_is_null(cur, &ptr))
 948                 return 0;
 949         return 1;
 950 }
 951
 952 STATIC void
 953 xfs_btree_buf_to_ptr(
 954         struct xfs_btree_cur    *cur,
 955         struct xfs_buf          *bp,
 956         union xfs_btree_ptr     *ptr)
 957 {
 958         if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
 959                 ptr->l = cpu_to_be64(XFS_DADDR_TO_FSB(cur->bc_mp,
 960                                         XFS_BUF_ADDR(bp)));
 961         else {
 962                 ptr->s = cpu_to_be32(XFS_DADDR_TO_AGBNO(cur->bc_mp,
 963                                         XFS_BUF_ADDR(bp)));
 964         }
 965 }
 966
 967 STATIC xfs_daddr_t
 968 xfs_btree_ptr_to_daddr(
 969         struct xfs_btree_cur    *cur,
 970         union xfs_btree_ptr     *ptr)
 971 {
 972         if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
 973                 ASSERT(be64_to_cpu(ptr->l) != NULLFSBLOCK);
 974
 975                 return XFS_FSB_TO_DADDR(cur->bc_mp, be64_to_cpu(ptr->l));
 976         } else {
 977                 ASSERT(cur->bc_private.a.agno != NULLAGNUMBER);
 978                 ASSERT(be32_to_cpu(ptr->s) != NULLAGBLOCK);
 979
 980                 return XFS_AGB_TO_DADDR(cur->bc_mp, cur->bc_private.a.agno,
 981                                         be32_to_cpu(ptr->s));
 982         }
 983 }
 984
 985 STATIC void
 986 xfs_btree_set_refs(
 987         struct xfs_btree_cur    *cur,
 988         struct xfs_buf          *bp)
 989 {
 990         switch (cur->bc_btnum) {
 991         case XFS_BTNUM_BNO:
 992         case XFS_BTNUM_CNT:
 993                 XFS_BUF_SET_VTYPE_REF(*bpp, B_FS_MAP, XFS_ALLOC_BTREE_REF);
 994                 break;
 995         case XFS_BTNUM_INO:
 996                 XFS_BUF_SET_VTYPE_REF(*bpp, B_FS_INOMAP, XFS_INO_BTREE_REF);
 997                 break;
 998         case XFS_BTNUM_BMAP:
 999                 XFS_BUF_SET_VTYPE_REF(*bpp, B_FS_MAP, XFS_BMAP_BTREE_REF);
1000                 break;
1001         default:
1002                 ASSERT(0);
1003         }
1004 }
1005
1006 STATIC int
1007 xfs_btree_get_buf_block(
1008         struct xfs_btree_cur    *cur,
1009         union xfs_btree_ptr     *ptr,
1010         int                     flags,
1011         struct xfs_btree_block  **block,
1012         struct xfs_buf          **bpp)
1013 {
1014         struct xfs_mount        *mp = cur->bc_mp;
1015         xfs_daddr_t             d;
1016
1017         /* need to sort out how callers deal with failures first */
1018         ASSERT(!(flags & XFS_BUF_TRYLOCK));
1019
1020         d = xfs_btree_ptr_to_daddr(cur, ptr);
1021         *bpp = xfs_trans_get_buf(cur->bc_tp, mp->m_ddev_targp, d,
1022                                  mp->m_bsize, flags);
1023
1024         ASSERT(*bpp);
1025         ASSERT(!XFS_BUF_GETERROR(*bpp));
1026
1027         *block = XFS_BUF_TO_BLOCK(*bpp);
1028         return 0;
1029 }
1030
1031 /*
1032  * Read in the buffer at the given ptr and return the buffer and
1033  * the block pointer within the buffer.
1034  */
1035 STATIC int
1036 xfs_btree_read_buf_block(
1037         struct xfs_btree_cur    *cur,
1038         union xfs_btree_ptr     *ptr,
1039         int                     level,
1040         int                     flags,
1041         struct xfs_btree_block  **block,
1042         struct xfs_buf          **bpp)
1043 {
1044         struct xfs_mount        *mp = cur->bc_mp;
1045         xfs_daddr_t             d;
1046         int                     error;
1047
1048         /* need to sort out how callers deal with failures first */
1049         ASSERT(!(flags & XFS_BUF_TRYLOCK));
1050
1051         d = xfs_btree_ptr_to_daddr(cur, ptr);
1052         error = xfs_trans_read_buf(mp, cur->bc_tp, mp->m_ddev_targp, d,
1053                                    mp->m_bsize, flags, bpp);
1054         if (error)
1055                 return error;
1056
1057         ASSERT(*bpp != NULL);
1058         ASSERT(!XFS_BUF_GETERROR(*bpp));
1059
1060         xfs_btree_set_refs(cur, *bpp);
1061         *block = XFS_BUF_TO_BLOCK(*bpp);
1062
1063         error = xfs_btree_check_block(cur, *block, level, *bpp);
1064         if (error)
1065                 xfs_trans_brelse(cur->bc_tp, *bpp);
1066         return error;
1067 }
1068
1069 /*
1070  * Copy keys from one btree block to another.
1071  */
1072 STATIC void
1073 xfs_btree_copy_keys(
1074         struct xfs_btree_cur    *cur,
1075         union xfs_btree_key     *dst_key,
1076         union xfs_btree_key     *src_key,
1077         int                     numkeys)
1078 {
1079         ASSERT(numkeys >= 0);
1080         memcpy(dst_key, src_key, numkeys * cur->bc_ops->key_len);
1081 }
1082
1083 /*
1084  * Copy records from one btree block to another.
1085  */
1086 STATIC void
1087 xfs_btree_copy_recs(
1088         struct xfs_btree_cur    *cur,
1089         union xfs_btree_rec     *dst_rec,
1090         union xfs_btree_rec     *src_rec,
1091         int                     numrecs)
1092 {
1093         ASSERT(numrecs >= 0);
1094         memcpy(dst_rec, src_rec, numrecs * cur->bc_ops->rec_len);
1095 }
1096
1097 /*
1098  * Copy block pointers from one btree block to another.
1099  */
1100 STATIC void
1101 xfs_btree_copy_ptrs(
1102         struct xfs_btree_cur    *cur,
1103         union xfs_btree_ptr     *dst_ptr,
1104         union xfs_btree_ptr     *src_ptr,
1105         int                     numptrs)
1106 {
1107         ASSERT(numptrs >= 0);
1108         memcpy(dst_ptr, src_ptr, numptrs * xfs_btree_ptr_len(cur));
1109 }
1110
1111 /*
1112  * Shift keys one index left/right inside a single btree block.
1113  */
1114 STATIC void
1115 xfs_btree_shift_keys(
1116         struct xfs_btree_cur    *cur,
1117         union xfs_btree_key     *key,
1118         int                     dir,
1119         int                     numkeys)
1120 {
1121         char                    *dst_key;
1122
1123         ASSERT(numkeys >= 0);
1124         ASSERT(dir == 1 || dir == -1);
1125
1126         dst_key = (char *)key + (dir * cur->bc_ops->key_len);
1127         memmove(dst_key, key, numkeys * cur->bc_ops->key_len);
1128 }
1129
1130 /*
1131  * Shift records one index left/right inside a single btree block.
1132  */
1133 STATIC void
1134 xfs_btree_shift_recs(
1135         struct xfs_btree_cur    *cur,
1136         union xfs_btree_rec     *rec,
1137         int                     dir,
1138         int                     numrecs)
1139 {
1140         char                    *dst_rec;
1141
1142         ASSERT(numrecs >= 0);
1143         ASSERT(dir == 1 || dir == -1);
1144
1145         dst_rec = (char *)rec + (dir * cur->bc_ops->rec_len);
1146         memmove(dst_rec, rec, numrecs * cur->bc_ops->rec_len);
1147 }
1148
1149 /*
1150  * Shift block pointers one index left/right inside a single btree block.
1151  */
1152 STATIC void
1153 xfs_btree_shift_ptrs(
1154         struct xfs_btree_cur    *cur,
1155         union xfs_btree_ptr     *ptr,
1156         int                     dir,
1157         int                     numptrs)
1158 {
1159         char                    *dst_ptr;
1160
1161         ASSERT(numptrs >= 0);
1162         ASSERT(dir == 1 || dir == -1);
1163
1164         dst_ptr = (char *)ptr + (dir * xfs_btree_ptr_len(cur));
1165         memmove(dst_ptr, ptr, numptrs * xfs_btree_ptr_len(cur));
1166 }
1167
1168 /*
1169  * Log key values from the btree block.
1170  */
1171 STATIC void
1172 xfs_btree_log_keys(
1173         struct xfs_btree_cur    *cur,
1174         struct xfs_buf          *bp,
1175         int                     first,
1176         int                     last)
1177 {
1178         XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
1179         XFS_BTREE_TRACE_ARGBII(cur, bp, first, last);
1180
1181         if (bp) {
1182                 xfs_trans_log_buf(cur->bc_tp, bp,
1183                                   xfs_btree_key_offset(cur, first),
1184                                   xfs_btree_key_offset(cur, last + 1) - 1);
1185         } else {
1186                 xfs_trans_log_inode(cur->bc_tp, cur->bc_private.b.ip,
1187                                 xfs_ilog_fbroot(cur->bc_private.b.whichfork));
1188         }
1189
1190         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1191 }
1192
1193 /*
1194  * Log record values from the btree block.
1195  */
1196 void
1197 xfs_btree_log_recs(
1198         struct xfs_btree_cur    *cur,
1199         struct xfs_buf          *bp,
1200         int                     first,
1201         int                     last)
1202 {
1203         XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
1204         XFS_BTREE_TRACE_ARGBII(cur, bp, first, last);
1205
1206         xfs_trans_log_buf(cur->bc_tp, bp,
1207                           xfs_btree_rec_offset(cur, first),
1208                           xfs_btree_rec_offset(cur, last + 1) - 1);
1209
1210         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1211 }
1212
1213 /*
1214  * Log block pointer fields from a btree block (nonleaf).
1215  */
1216 STATIC void
1217 xfs_btree_log_ptrs(
1218         struct xfs_btree_cur    *cur,   /* btree cursor */
1219         struct xfs_buf          *bp,    /* buffer containing btree block */
1220         int                     first,  /* index of first pointer to log */
1221         int                     last)   /* index of last pointer to log */
1222 {
1223         XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
1224         XFS_BTREE_TRACE_ARGBII(cur, bp, first, last);
1225
1226         if (bp) {
1227                 struct xfs_btree_block  *block = XFS_BUF_TO_BLOCK(bp);
1228                 int                     level = xfs_btree_get_level(block);
1229
1230                 xfs_trans_log_buf(cur->bc_tp, bp,
1231                                 xfs_btree_ptr_offset(cur, first, level),
1232                                 xfs_btree_ptr_offset(cur, last + 1, level) - 1);
1233         } else {
1234                 xfs_trans_log_inode(cur->bc_tp, cur->bc_private.b.ip,
1235                         xfs_ilog_fbroot(cur->bc_private.b.whichfork));
1236         }
1237
1238         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1239 }
1240
1241 /*
1242  * Log fields from a btree block header.
1243  */
1244 void
1245 xfs_btree_log_block(
1246         struct xfs_btree_cur    *cur,   /* btree cursor */
1247         struct xfs_buf          *bp,    /* buffer containing btree block */
1248         int                     fields) /* mask of fields: XFS_BB_... */
1249 {
1250         int                     first;  /* first byte offset logged */
1251         int                     last;   /* last byte offset logged */
1252         static const short      soffsets[] = {  /* table of offsets (short) */
1253                 offsetof(struct xfs_btree_sblock, bb_magic),
1254                 offsetof(struct xfs_btree_sblock, bb_level),
1255                 offsetof(struct xfs_btree_sblock, bb_numrecs),
1256                 offsetof(struct xfs_btree_sblock, bb_leftsib),
1257                 offsetof(struct xfs_btree_sblock, bb_rightsib),
1258                 sizeof(struct xfs_btree_sblock)
1259         };
1260         static const short      loffsets[] = {  /* table of offsets (long) */
1261                 offsetof(struct xfs_btree_lblock, bb_magic),
1262                 offsetof(struct xfs_btree_lblock, bb_level),
1263                 offsetof(struct xfs_btree_lblock, bb_numrecs),
1264                 offsetof(struct xfs_btree_lblock, bb_leftsib),
1265                 offsetof(struct xfs_btree_lblock, bb_rightsib),
1266                 sizeof(struct xfs_btree_lblock)
1267         };
1268
1269         XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
1270         XFS_BTREE_TRACE_ARGBI(cur, bp, fields);
1271
1272         if (bp) {
1273                 xfs_btree_offsets(fields,
1274                                   (cur->bc_flags & XFS_BTREE_LONG_PTRS) ?
1275                                         loffsets : soffsets,
1276                                   XFS_BB_NUM_BITS, &first, &last);
1277                 xfs_trans_log_buf(cur->bc_tp, bp, first, last);
1278         } else {
1279                 xfs_trans_log_inode(cur->bc_tp, cur->bc_private.b.ip,
1280                         xfs_ilog_fbroot(cur->bc_private.b.whichfork));
1281         }
1282
1283         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1284 }
1285
1286 /*
1287  * Increment cursor by one record at the level.
1288  * For nonzero levels the leaf-ward information is untouched.
1289  */
1290 int                                             /* error */
1291 xfs_btree_increment(
1292         struct xfs_btree_cur    *cur,
1293         int                     level,
1294         int                     *stat)          /* success/failure */
1295 {
1296         struct xfs_btree_block  *block;
1297         union xfs_btree_ptr     ptr;
1298         struct xfs_buf          *bp;
1299         int                     error;          /* error return value */
1300         int                     lev;
1301
1302         XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
1303         XFS_BTREE_TRACE_ARGI(cur, level);
1304
1305         ASSERT(level < cur->bc_nlevels);
1306
1307         /* Read-ahead to the right at this level. */
1308         xfs_btree_readahead(cur, level, XFS_BTCUR_RIGHTRA);
1309
1310         /* Get a pointer to the btree block. */
1311         block = xfs_btree_get_block(cur, level, &bp);
1312
1313 #ifdef DEBUG
1314         error = xfs_btree_check_block(cur, block, level, bp);
1315         if (error)
1316                 goto error0;
1317 #endif
1318
1319         /* We're done if we remain in the block after the increment. */
1320         if (++cur->bc_ptrs[level] <= xfs_btree_get_numrecs(block))
1321                 goto out1;
1322
1323         /* Fail if we just went off the right edge of the tree. */
1324         xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB);
1325         if (xfs_btree_ptr_is_null(cur, &ptr))
1326                 goto out0;
1327
1328         XFS_BTREE_STATS_INC(cur, increment);
1329
1330         /*
1331          * March up the tree incrementing pointers.
1332          * Stop when we don't go off the right edge of a block.
1333          */
1334         for (lev = level + 1; lev < cur->bc_nlevels; lev++) {
1335                 block = xfs_btree_get_block(cur, lev, &bp);
1336
1337 #ifdef DEBUG
1338                 error = xfs_btree_check_block(cur, block, lev, bp);
1339                 if (error)
1340                         goto error0;
1341 #endif
1342
1343                 if (++cur->bc_ptrs[lev] <= xfs_btree_get_numrecs(block))
1344                         break;
1345
1346                 /* Read-ahead the right block for the next loop. */
1347                 xfs_btree_readahead(cur, lev, XFS_BTCUR_RIGHTRA);
1348         }
1349
1350         /*
1351          * If we went off the root then we are either seriously
1352          * confused or have the tree root in an inode.
1353          */
1354         if (lev == cur->bc_nlevels) {
1355                 if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE)
1356                         goto out0;
1357                 ASSERT(0);
1358                 error = EFSCORRUPTED;
1359                 goto error0;
1360         }
1361         ASSERT(lev < cur->bc_nlevels);
1362
1363         /*
1364          * Now walk back down the tree, fixing up the cursor's buffer
1365          * pointers and key numbers.
1366          */
1367         for (block = xfs_btree_get_block(cur, lev, &bp); lev > level; ) {
1368                 union xfs_btree_ptr     *ptrp;
1369
1370                 ptrp = xfs_btree_ptr_addr(cur, cur->bc_ptrs[lev], block);
1371                 error = xfs_btree_read_buf_block(cur, ptrp, --lev,
1372                                                         0, &block, &bp);
1373                 if (error)
1374                         goto error0;
1375
1376                 xfs_btree_setbuf(cur, lev, bp);
1377                 cur->bc_ptrs[lev] = 1;
1378         }
1379 out1:
1380         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1381         *stat = 1;
1382         return 0;
1383
1384 out0:
1385         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1386         *stat = 0;
1387         return 0;
1388
1389 error0:
1390         XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
1391         return error;
1392 }
1393
1394 /*
1395  * Decrement cursor by one record at the level.
1396  * For nonzero levels the leaf-ward information is untouched.
1397  */
1398 int                                             /* error */
1399 xfs_btree_decrement(
1400         struct xfs_btree_cur    *cur,
1401         int                     level,
1402         int                     *stat)          /* success/failure */
1403 {
1404         struct xfs_btree_block  *block;
1405         xfs_buf_t               *bp;
1406         int                     error;          /* error return value */
1407         int                     lev;
1408         union xfs_btree_ptr     ptr;
1409
1410         XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
1411         XFS_BTREE_TRACE_ARGI(cur, level);
1412
1413         ASSERT(level < cur->bc_nlevels);
1414
1415         /* Read-ahead to the left at this level. */
1416         xfs_btree_readahead(cur, level, XFS_BTCUR_LEFTRA);
1417
1418         /* We're done if we remain in the block after the decrement. */
1419         if (--cur->bc_ptrs[level] > 0)
1420                 goto out1;
1421
1422         /* Get a pointer to the btree block. */
1423         block = xfs_btree_get_block(cur, level, &bp);
1424
1425 #ifdef DEBUG
1426         error = xfs_btree_check_block(cur, block, level, bp);
1427         if (error)
1428                 goto error0;
1429 #endif
1430
1431         /* Fail if we just went off the left edge of the tree. */
1432         xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_LEFTSIB);
1433         if (xfs_btree_ptr_is_null(cur, &ptr))
1434                 goto out0;
1435
1436         XFS_BTREE_STATS_INC(cur, decrement);
1437
1438         /*
1439          * March up the tree decrementing pointers.
1440          * Stop when we don't go off the left edge of a block.
1441          */
1442         for (lev = level + 1; lev < cur->bc_nlevels; lev++) {
1443                 if (--cur->bc_ptrs[lev] > 0)
1444                         break;
1445                 /* Read-ahead the left block for the next loop. */
1446                 xfs_btree_readahead(cur, lev, XFS_BTCUR_LEFTRA);
1447         }
1448
1449         /*
1450          * If we went off the root then we are seriously confused.
1451          * or the root of the tree is in an inode.
1452          */
1453         if (lev == cur->bc_nlevels) {
1454                 if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE)
1455                         goto out0;
1456                 ASSERT(0);
1457                 error = EFSCORRUPTED;
1458                 goto error0;
1459         }
1460         ASSERT(lev < cur->bc_nlevels);
1461
1462         /*
1463          * Now walk back down the tree, fixing up the cursor's buffer
1464          * pointers and key numbers.
1465          */
1466         for (block = xfs_btree_get_block(cur, lev, &bp); lev > level; ) {
1467                 union xfs_btree_ptr     *ptrp;
1468
1469                 ptrp = xfs_btree_ptr_addr(cur, cur->bc_ptrs[lev], block);
1470                 error = xfs_btree_read_buf_block(cur, ptrp, --lev,
1471                                                         0, &block, &bp);
1472                 if (error)
1473                         goto error0;
1474                 xfs_btree_setbuf(cur, lev, bp);
1475                 cur->bc_ptrs[lev] = xfs_btree_get_numrecs(block);
1476         }
1477 out1:
1478         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1479         *stat = 1;
1480         return 0;
1481
1482 out0:
1483         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1484         *stat = 0;
1485         return 0;
1486
1487 error0:
1488         XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
1489         return error;
1490 }
1491
1492 STATIC int
1493 xfs_btree_lookup_get_block(
1494         struct xfs_btree_cur    *cur,   /* btree cursor */
1495         int                     level,  /* level in the btree */
1496         union xfs_btree_ptr     *pp,    /* ptr to btree block */
1497         struct xfs_btree_block  **blkp) /* return btree block */
1498 {
1499         struct xfs_buf          *bp;    /* buffer pointer for btree block */
1500         int                     error = 0;
1501
1502         /* special case the root block if in an inode */
1503         if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
1504             (level == cur->bc_nlevels - 1)) {
1505                 *blkp = xfs_btree_get_iroot(cur);
1506                 return 0;
1507         }
1508
1509         /*
1510          * If the old buffer at this level for the disk address we are
1511          * looking for re-use it.
1512          *
1513          * Otherwise throw it away and get a new one.
1514          */
1515         bp = cur->bc_bufs[level];
1516         if (bp && XFS_BUF_ADDR(bp) == xfs_btree_ptr_to_daddr(cur, pp)) {
1517                 *blkp = XFS_BUF_TO_BLOCK(bp);
1518                 return 0;
1519         }
1520
1521         error = xfs_btree_read_buf_block(cur, pp, level, 0, blkp, &bp);
1522         if (error)
1523                 return error;
1524
1525         xfs_btree_setbuf(cur, level, bp);
1526         return 0;
1527 }
1528
1529 /*
1530  * Get current search key.  For level 0 we don't actually have a key
1531  * structure so we make one up from the record.  For all other levels
1532  * we just return the right key.
1533  */
1534 STATIC union xfs_btree_key *
1535 xfs_lookup_get_search_key(
1536         struct xfs_btree_cur    *cur,
1537         int                     level,
1538         int                     keyno,
1539         struct xfs_btree_block  *block,
1540         union xfs_btree_key     *kp)
1541 {
1542         if (level == 0) {
1543                 cur->bc_ops->init_key_from_rec(kp,
1544                                 xfs_btree_rec_addr(cur, keyno, block));
1545                 return kp;
1546         }
1547
1548         return xfs_btree_key_addr(cur, keyno, block);
1549 }
1550
1551 /*
1552  * Lookup the record.  The cursor is made to point to it, based on dir.
1553  * Return 0 if can't find any such record, 1 for success.
1554  */
1555 int                                     /* error */
1556 xfs_btree_lookup(
1557         struct xfs_btree_cur    *cur,   /* btree cursor */
1558         xfs_lookup_t            dir,    /* <=, ==, or >= */
1559         int                     *stat)  /* success/failure */
1560 {
1561         struct xfs_btree_block  *block; /* current btree block */
1562         __int64_t               diff;   /* difference for the current key */
1563         int                     error;  /* error return value */
1564         int                     keyno;  /* current key number */
1565         int                     level;  /* level in the btree */
1566         union xfs_btree_ptr     *pp;    /* ptr to btree block */
1567         union xfs_btree_ptr     ptr;    /* ptr to btree block */
1568
1569         XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
1570         XFS_BTREE_TRACE_ARGI(cur, dir);
1571
1572         XFS_BTREE_STATS_INC(cur, lookup);
1573
1574         block = NULL;
1575         keyno = 0;
1576
1577         /* initialise start pointer from cursor */
1578         cur->bc_ops->init_ptr_from_cur(cur, &ptr);
1579         pp = &ptr;
1580
1581         /*
1582          * Iterate over each level in the btree, starting at the root.
1583          * For each level above the leaves, find the key we need, based
1584          * on the lookup record, then follow the corresponding block
1585          * pointer down to the next level.
1586          */
1587         for (level = cur->bc_nlevels - 1, diff = 1; level >= 0; level--) {
1588                 /* Get the block we need to do the lookup on. */
1589                 error = xfs_btree_lookup_get_block(cur, level, pp, &block);
1590                 if (error)
1591                         goto error0;
1592
1593                 if (diff == 0) {
1594                         /*
1595                          * If we already had a key match at a higher level, we
1596                          * know we need to use the first entry in this block.
1597                          */
1598                         keyno = 1;
1599                 } else {
1600                         /* Otherwise search this block. Do a binary search. */
1601
1602                         int     high;   /* high entry number */
1603                         int     low;    /* low entry number */
1604
1605                         /* Set low and high entry numbers, 1-based. */
1606                         low = 1;
1607                         high = xfs_btree_get_numrecs(block);
1608                         if (!high) {
1609                                 /* Block is empty, must be an empty leaf. */
1610                                 ASSERT(level == 0 && cur->bc_nlevels == 1);
1611
1612                                 cur->bc_ptrs[0] = dir != XFS_LOOKUP_LE;
1613                                 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1614                                 *stat = 0;
1615                                 return 0;
1616                         }
1617
1618                         /* Binary search the block. */
1619                         while (low <= high) {
1620                                 union xfs_btree_key     key;
1621                                 union xfs_btree_key     *kp;
1622
1623                                 XFS_BTREE_STATS_INC(cur, compare);
1624
1625                                 /* keyno is average of low and high. */
1626                                 keyno = (low + high) >> 1;
1627
1628                                 /* Get current search key */
1629                                 kp = xfs_lookup_get_search_key(cur, level,
1630                                                 keyno, block, &key);
1631
1632                                 /*
1633                                  * Compute difference to get next direction:
1634                                  *  - less than, move right
1635                                  *  - greater than, move left
1636                                  *  - equal, we're done
1637                                  */
1638                                 diff = cur->bc_ops->key_diff(cur, kp);
1639                                 if (diff < 0)
1640                                         low = keyno + 1;
1641                                 else if (diff > 0)
1642                                         high = keyno - 1;
1643                                 else
1644                                         break;
1645                         }
1646                 }
1647
1648                 /*
1649                  * If there are more levels, set up for the next level
1650                  * by getting the block number and filling in the cursor.
1651                  */
1652                 if (level > 0) {
1653                         /*
1654                          * If we moved left, need the previous key number,
1655                          * unless there isn't one.
1656                          */
1657                         if (diff > 0 && --keyno < 1)
1658                                 keyno = 1;
1659                         pp = xfs_btree_ptr_addr(cur, keyno, block);
1660
1661 #ifdef DEBUG
1662                         error = xfs_btree_check_ptr(cur, pp, 0, level);
1663                         if (error)
1664                                 goto error0;
1665 #endif
1666                         cur->bc_ptrs[level] = keyno;
1667                 }
1668         }
1669
1670         /* Done with the search. See if we need to adjust the results. */
1671         if (dir != XFS_LOOKUP_LE && diff < 0) {
1672                 keyno++;
1673                 /*
1674                  * If ge search and we went off the end of the block, but it's
1675                  * not the last block, we're in the wrong block.
1676                  */
1677                 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB);
1678                 if (dir == XFS_LOOKUP_GE &&
1679                     keyno > xfs_btree_get_numrecs(block) &&
1680                     !xfs_btree_ptr_is_null(cur, &ptr)) {
1681                         int     i;
1682
1683                         cur->bc_ptrs[0] = keyno;
1684                         error = xfs_btree_increment(cur, 0, &i);
1685                         if (error)
1686                                 goto error0;
1687                         XFS_WANT_CORRUPTED_RETURN(i == 1);
1688                         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1689                         *stat = 1;
1690                         return 0;
1691                 }
1692         } else if (dir == XFS_LOOKUP_LE && diff > 0)
1693                 keyno--;
1694         cur->bc_ptrs[0] = keyno;
1695
1696         /* Return if we succeeded or not. */
1697         if (keyno == 0 || keyno > xfs_btree_get_numrecs(block))
1698                 *stat = 0;
1699         else if (dir != XFS_LOOKUP_EQ || diff == 0)
1700                 *stat = 1;
1701         else
1702                 *stat = 0;
1703         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1704         return 0;
1705
1706 error0:
1707         XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
1708         return error;
1709 }
1710
1711 /*
1712  * Update keys at all levels from here to the root along the cursor's path.
1713  */
1714 STATIC int
1715 xfs_btree_updkey(
1716         struct xfs_btree_cur    *cur,
1717         union xfs_btree_key     *keyp,
1718         int                     level)
1719 {
1720         struct xfs_btree_block  *block;
1721         struct xfs_buf          *bp;
1722         union xfs_btree_key     *kp;
1723         int                     ptr;
1724
1725         XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
1726         XFS_BTREE_TRACE_ARGIK(cur, level, keyp);
1727
1728         ASSERT(!(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) || level >= 1);
1729
1730         /*
1731          * Go up the tree from this level toward the root.
1732          * At each level, update the key value to the value input.
1733          * Stop when we reach a level where the cursor isn't pointing
1734          * at the first entry in the block.
1735          */
1736         for (ptr = 1; ptr == 1 && level < cur->bc_nlevels; level++) {
1737 #ifdef DEBUG
1738                 int             error;
1739 #endif
1740                 block = xfs_btree_get_block(cur, level, &bp);
1741 #ifdef DEBUG
1742                 error = xfs_btree_check_block(cur, block, level, bp);
1743                 if (error) {
1744                         XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
1745                         return error;
1746                 }
1747 #endif
1748                 ptr = cur->bc_ptrs[level];
1749                 kp = xfs_btree_key_addr(cur, ptr, block);
1750                 xfs_btree_copy_keys(cur, kp, keyp, 1);
1751                 xfs_btree_log_keys(cur, bp, ptr, ptr);
1752         }
1753
1754         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1755         return 0;
1756 }
1757
1758 /*
1759  * Update the record referred to by cur to the value in the
1760  * given record. This either works (return 0) or gets an
1761  * EFSCORRUPTED error.
1762  */
1763 int
1764 xfs_btree_update(
1765         struct xfs_btree_cur    *cur,
1766         union xfs_btree_rec     *rec)
1767 {
1768         struct xfs_btree_block  *block;
1769         struct xfs_buf          *bp;
1770         int                     error;
1771         int                     ptr;
1772         union xfs_btree_rec     *rp;
1773
1774         XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
1775         XFS_BTREE_TRACE_ARGR(cur, rec);
1776
1777         /* Pick up the current block. */
1778         block = xfs_btree_get_block(cur, 0, &bp);
1779
1780 #ifdef DEBUG
1781         error = xfs_btree_check_block(cur, block, 0, bp);
1782         if (error)
1783                 goto error0;
1784 #endif
1785         /* Get the address of the rec to be updated. */
1786         ptr = cur->bc_ptrs[0];
1787         rp = xfs_btree_rec_addr(cur, ptr, block);
1788
1789         /* Fill in the new contents and log them. */
1790         xfs_btree_copy_recs(cur, rp, rec, 1);
1791         xfs_btree_log_recs(cur, bp, ptr, ptr);
1792
1793         /*
1794          * If we are tracking the last record in the tree and
1795          * we are at the far right edge of the tree, update it.
1796          */
1797         if (xfs_btree_is_lastrec(cur, block, 0)) {
1798                 cur->bc_ops->update_lastrec(cur, block, rec,
1799                                             ptr, LASTREC_UPDATE);
1800         }
1801
1802         /* Updating first rec in leaf. Pass new key value up to our parent. */
1803         if (ptr == 1) {
1804                 union xfs_btree_key     key;
1805
1806                 cur->bc_ops->init_key_from_rec(&key, rec);
1807                 error = xfs_btree_updkey(cur, &key, 1);
1808                 if (error)
1809                         goto error0;
1810         }
1811
1812         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1813         return 0;
1814
1815 error0:
1816         XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
1817         return error;
1818 }
1819
1820 /*
1821  * Move 1 record left from cur/level if possible.
1822  * Update cur to reflect the new path.
1823  */
1824 STATIC int                                      /* error */
1825 xfs_btree_lshift(
1826         struct xfs_btree_cur    *cur,
1827         int                     level,
1828         int                     *stat)          /* success/failure */
1829 {
1830         union xfs_btree_key     key;            /* btree key */
1831         struct xfs_buf          *lbp;           /* left buffer pointer */
1832         struct xfs_btree_block  *left;          /* left btree block */
1833         int                     lrecs;          /* left record count */
1834         struct xfs_buf          *rbp;           /* right buffer pointer */
1835         struct xfs_btree_block  *right;         /* right btree block */
1836         int                     rrecs;          /* right record count */
1837         union xfs_btree_ptr     lptr;           /* left btree pointer */
1838         union xfs_btree_key     *rkp = NULL;    /* right btree key */
1839         union xfs_btree_ptr     *rpp = NULL;    /* right address pointer */
1840         union xfs_btree_rec     *rrp = NULL;    /* right record pointer */
1841         int                     error;          /* error return value */
1842
1843         XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
1844         XFS_BTREE_TRACE_ARGI(cur, level);
1845
1846         if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
1847             level == cur->bc_nlevels - 1)
1848                 goto out0;
1849
1850         /* Set up variables for this block as "right". */
1851         right = xfs_btree_get_block(cur, level, &rbp);
1852
1853 #ifdef DEBUG
1854         error = xfs_btree_check_block(cur, right, level, rbp);
1855         if (error)
1856                 goto error0;
1857 #endif
1858
1859         /* If we've got no left sibling then we can't shift an entry left. */
1860         xfs_btree_get_sibling(cur, right, &lptr, XFS_BB_LEFTSIB);
1861         if (xfs_btree_ptr_is_null(cur, &lptr))
1862                 goto out0;
1863
1864         /*
1865          * If the cursor entry is the one that would be moved, don't
1866          * do it... it's too complicated.
1867          */
1868         if (cur->bc_ptrs[level] <= 1)
1869                 goto out0;
1870
1871         /* Set up the left neighbor as "left". */
1872         error = xfs_btree_read_buf_block(cur, &lptr, level, 0, &left, &lbp);
1873         if (error)
1874                 goto error0;
1875
1876         /* If it's full, it can't take another entry. */
1877         lrecs = xfs_btree_get_numrecs(left);
1878         if (lrecs == cur->bc_ops->get_maxrecs(cur, level))
1879                 goto out0;
1880
1881         rrecs = xfs_btree_get_numrecs(right);
1882
1883         /*
1884          * We add one entry to the left side and remove one for the right side.
1885          * Accout for it here, the changes will be updated on disk and logged
1886          * later.
1887          */
1888         lrecs++;
1889         rrecs--;
1890
1891         XFS_BTREE_STATS_INC(cur, lshift);
1892         XFS_BTREE_STATS_ADD(cur, moves, 1);
1893
1894         /*
1895          * If non-leaf, copy a key and a ptr to the left block.
1896          * Log the changes to the left block.
1897          */
1898         if (level > 0) {
1899                 /* It's a non-leaf.  Move keys and pointers. */
1900                 union xfs_btree_key     *lkp;   /* left btree key */
1901                 union xfs_btree_ptr     *lpp;   /* left address pointer */
1902
1903                 lkp = xfs_btree_key_addr(cur, lrecs, left);
1904                 rkp = xfs_btree_key_addr(cur, 1, right);
1905
1906                 lpp = xfs_btree_ptr_addr(cur, lrecs, left);
1907                 rpp = xfs_btree_ptr_addr(cur, 1, right);
1908 #ifdef DEBUG
1909                 error = xfs_btree_check_ptr(cur, rpp, 0, level);
1910                 if (error)
1911                         goto error0;
1912 #endif
1913                 xfs_btree_copy_keys(cur, lkp, rkp, 1);
1914                 xfs_btree_copy_ptrs(cur, lpp, rpp, 1);
1915
1916                 xfs_btree_log_keys(cur, lbp, lrecs, lrecs);
1917                 xfs_btree_log_ptrs(cur, lbp, lrecs, lrecs);
1918
1919                 ASSERT(cur->bc_ops->keys_inorder(cur,
1920                         xfs_btree_key_addr(cur, lrecs - 1, left), lkp));
1921         } else {
1922                 /* It's a leaf.  Move records.  */
1923                 union xfs_btree_rec     *lrp;   /* left record pointer */
1924
1925                 lrp = xfs_btree_rec_addr(cur, lrecs, left);
1926                 rrp = xfs_btree_rec_addr(cur, 1, right);
1927
1928                 xfs_btree_copy_recs(cur, lrp, rrp, 1);
1929                 xfs_btree_log_recs(cur, lbp, lrecs, lrecs);
1930
1931                 ASSERT(cur->bc_ops->recs_inorder(cur,
1932                         xfs_btree_rec_addr(cur, lrecs - 1, left), lrp));
1933         }
1934
1935         xfs_btree_set_numrecs(left, lrecs);
1936         xfs_btree_log_block(cur, lbp, XFS_BB_NUMRECS);
1937
1938         xfs_btree_set_numrecs(right, rrecs);
1939         xfs_btree_log_block(cur, rbp, XFS_BB_NUMRECS);
1940
1941         /*
1942          * Slide the contents of right down one entry.
1943          */
1944         XFS_BTREE_STATS_ADD(cur, moves, rrecs - 1);
1945         if (level > 0) {
1946                 /* It's a nonleaf. operate on keys and ptrs */
1947 #ifdef DEBUG
1948                 int                     i;              /* loop index */
1949
1950                 for (i = 0; i < rrecs; i++) {
1951                         error = xfs_btree_check_ptr(cur, rpp, i + 1, level);
1952                         if (error)
1953                                 goto error0;
1954                 }
1955 #endif
1956                 xfs_btree_shift_keys(cur,
1957                                 xfs_btree_key_addr(cur, 2, right),
1958                                 -1, rrecs);
1959                 xfs_btree_shift_ptrs(cur,
1960                                 xfs_btree_ptr_addr(cur, 2, right),
1961                                 -1, rrecs);
1962
1963                 xfs_btree_log_keys(cur, rbp, 1, rrecs);
1964                 xfs_btree_log_ptrs(cur, rbp, 1, rrecs);
1965         } else {
1966                 /* It's a leaf. operate on records */
1967                 xfs_btree_shift_recs(cur,
1968                         xfs_btree_rec_addr(cur, 2, right),
1969                         -1, rrecs);
1970                 xfs_btree_log_recs(cur, rbp, 1, rrecs);
1971
1972                 /*
1973                  * If it's the first record in the block, we'll need a key
1974                  * structure to pass up to the next level (updkey).
1975                  */
1976                 cur->bc_ops->init_key_from_rec(&key,
1977                         xfs_btree_rec_addr(cur, 1, right));
1978                 rkp = &key;
1979         }
1980
1981         /* Update the parent key values of right. */
1982         error = xfs_btree_updkey(cur, rkp, level + 1);
1983         if (error)
1984                 goto error0;
1985
1986         /* Slide the cursor value left one. */
1987         cur->bc_ptrs[level]--;
1988
1989         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1990         *stat = 1;
1991         return 0;
1992
1993 out0:
1994         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
1995         *stat = 0;
1996         return 0;
1997
1998 error0:
1999         XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
2000         return error;
2001 }
2002
2003 /*
2004  * Move 1 record right from cur/level if possible.
2005  * Update cur to reflect the new path.
2006  */
2007 STATIC int                                      /* error */
2008 xfs_btree_rshift(
2009         struct xfs_btree_cur    *cur,
2010         int                     level,
2011         int                     *stat)          /* success/failure */
2012 {
2013         union xfs_btree_key     key;            /* btree key */
2014         struct xfs_buf          *lbp;           /* left buffer pointer */
2015         struct xfs_btree_block  *left;          /* left btree block */
2016         struct xfs_buf          *rbp;           /* right buffer pointer */
2017         struct xfs_btree_block  *right;         /* right btree block */
2018         struct xfs_btree_cur    *tcur;          /* temporary btree cursor */
2019         union xfs_btree_ptr     rptr;           /* right block pointer */
2020         union xfs_btree_key     *rkp;           /* right btree key */
2021         int                     rrecs;          /* right record count */
2022         int                     lrecs;          /* left record count */
2023         int                     error;          /* error return value */
2024         int                     i;              /* loop counter */
2025
2026         XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
2027         XFS_BTREE_TRACE_ARGI(cur, level);
2028
2029         if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
2030             (level == cur->bc_nlevels - 1))
2031                 goto out0;
2032
2033         /* Set up variables for this block as "left". */
2034         left = xfs_btree_get_block(cur, level, &lbp);
2035
2036 #ifdef DEBUG
2037         error = xfs_btree_check_block(cur, left, level, lbp);
2038         if (error)
2039                 goto error0;
2040 #endif
2041
2042         /* If we've got no right sibling then we can't shift an entry right. */
2043         xfs_btree_get_sibling(cur, left, &rptr, XFS_BB_RIGHTSIB);
2044         if (xfs_btree_ptr_is_null(cur, &rptr))
2045                 goto out0;
2046
2047         /*
2048          * If the cursor entry is the one that would be moved, don't
2049          * do it... it's too complicated.
2050          */
2051         lrecs = xfs_btree_get_numrecs(left);
2052         if (cur->bc_ptrs[level] >= lrecs)
2053                 goto out0;
2054
2055         /* Set up the right neighbor as "right". */
2056         error = xfs_btree_read_buf_block(cur, &rptr, level, 0, &right, &rbp);
2057         if (error)
2058                 goto error0;
2059
2060         /* If it's full, it can't take another entry. */
2061         rrecs = xfs_btree_get_numrecs(right);
2062         if (rrecs == cur->bc_ops->get_maxrecs(cur, level))
2063                 goto out0;
2064
2065         XFS_BTREE_STATS_INC(cur, rshift);
2066         XFS_BTREE_STATS_ADD(cur, moves, rrecs);
2067
2068         /*
2069          * Make a hole at the start of the right neighbor block, then
2070          * copy the last left block entry to the hole.
2071          */
2072         if (level > 0) {
2073                 /* It's a nonleaf. make a hole in the keys and ptrs */
2074                 union xfs_btree_key     *lkp;
2075                 union xfs_btree_ptr     *lpp;
2076                 union xfs_btree_ptr     *rpp;
2077
2078                 lkp = xfs_btree_key_addr(cur, lrecs, left);
2079                 lpp = xfs_btree_ptr_addr(cur, lrecs, left);
2080                 rkp = xfs_btree_key_addr(cur, 1, right);
2081                 rpp = xfs_btree_ptr_addr(cur, 1, right);
2082
2083 #ifdef DEBUG
2084                 for (i = rrecs - 1; i >= 0; i--) {
2085                         error = xfs_btree_check_ptr(cur, rpp, i, level);
2086                         if (error)
2087                                 goto error0;
2088                 }
2089 #endif
2090
2091                 xfs_btree_shift_keys(cur, rkp, 1, rrecs);
2092                 xfs_btree_shift_ptrs(cur, rpp, 1, rrecs);
2093
2094 #ifdef DEBUG
2095                 error = xfs_btree_check_ptr(cur, lpp, 0, level);
2096                 if (error)
2097                         goto error0;
2098 #endif
2099
2100                 /* Now put the new data in, and log it. */
2101                 xfs_btree_copy_keys(cur, rkp, lkp, 1);
2102                 xfs_btree_copy_ptrs(cur, rpp, lpp, 1);
2103
2104                 xfs_btree_log_keys(cur, rbp, 1, rrecs + 1);
2105                 xfs_btree_log_ptrs(cur, rbp, 1, rrecs + 1);
2106
2107                 ASSERT(cur->bc_ops->keys_inorder(cur, rkp,
2108                         xfs_btree_key_addr(cur, 2, right)));
2109         } else {
2110                 /* It's a leaf. make a hole in the records */
2111                 union xfs_btree_rec     *lrp;
2112                 union xfs_btree_rec     *rrp;
2113
2114                 lrp = xfs_btree_rec_addr(cur, lrecs, left);
2115                 rrp = xfs_btree_rec_addr(cur, 1, right);
2116
2117                 xfs_btree_shift_recs(cur, rrp, 1, rrecs);
2118
2119                 /* Now put the new data in, and log it. */
2120                 xfs_btree_copy_recs(cur, rrp, lrp, 1);
2121                 xfs_btree_log_recs(cur, rbp, 1, rrecs + 1);
2122
2123                 cur->bc_ops->init_key_from_rec(&key, rrp);
2124                 rkp = &key;
2125
2126                 ASSERT(cur->bc_ops->recs_inorder(cur, rrp,
2127                         xfs_btree_rec_addr(cur, 2, right)));
2128         }
2129
2130         /*
2131          * Decrement and log left's numrecs, bump and log right's numrecs.
2132          */
2133         xfs_btree_set_numrecs(left, --lrecs);
2134         xfs_btree_log_block(cur, lbp, XFS_BB_NUMRECS);
2135
2136         xfs_btree_set_numrecs(right, ++rrecs);
2137         xfs_btree_log_block(cur, rbp, XFS_BB_NUMRECS);
2138
2139         /*
2140          * Using a temporary cursor, update the parent key values of the
2141          * block on the right.
2142          */
2143         error = xfs_btree_dup_cursor(cur, &tcur);
2144         if (error)
2145                 goto error0;
2146         i = xfs_btree_lastrec(tcur, level);
2147         XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
2148
2149         error = xfs_btree_increment(tcur, level, &i);
2150         if (error)
2151                 goto error1;
2152
2153         error = xfs_btree_updkey(tcur, rkp, level + 1);
2154         if (error)
2155                 goto error1;
2156
2157         xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
2158
2159         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
2160         *stat = 1;
2161         return 0;
2162
2163 out0:
2164         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
2165         *stat = 0;
2166         return 0;
2167
2168 error0:
2169         XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
2170         return error;
2171
2172 error1:
2173         XFS_BTREE_TRACE_CURSOR(tcur, XBT_ERROR);
2174         xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
2175         return error;
2176 }
2177
2178 /*
2179  * Split cur/level block in half.
2180  * Return new block number and the key to its first
2181  * record (to be inserted into parent).
2182  */
2183 STATIC int                                      /* error */
2184 xfs_btree_split(
2185         struct xfs_btree_cur    *cur,
2186         int                     level,
2187         union xfs_btree_ptr     *ptrp,
2188         union xfs_btree_key     *key,
2189         struct xfs_btree_cur    **curp,
2190         int                     *stat)          /* success/failure */
2191 {
2192         union xfs_btree_ptr     lptr;           /* left sibling block ptr */
2193         struct xfs_buf          *lbp;           /* left buffer pointer */
2194         struct xfs_btree_block  *left;          /* left btree block */
2195         union xfs_btree_ptr     rptr;           /* right sibling block ptr */
2196         struct xfs_buf          *rbp;           /* right buffer pointer */
2197         struct xfs_btree_block  *right;         /* right btree block */
2198         union xfs_btree_ptr     rrptr;          /* right-right sibling ptr */
2199         struct xfs_buf          *rrbp;          /* right-right buffer pointer */
2200         struct xfs_btree_block  *rrblock;       /* right-right btree block */
2201         int                     lrecs;
2202         int                     rrecs;
2203         int                     src_index;
2204         int                     error;          /* error return value */
2205 #ifdef DEBUG
2206         int                     i;
2207 #endif
2208
2209         XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
2210         XFS_BTREE_TRACE_ARGIPK(cur, level, *ptrp, key);
2211
2212         XFS_BTREE_STATS_INC(cur, split);
2213
2214         /* Set up left block (current one). */
2215         left = xfs_btree_get_block(cur, level, &lbp);
2216
2217 #ifdef DEBUG
2218         error = xfs_btree_check_block(cur, left, level, lbp);
2219         if (error)
2220                 goto error0;
2221 #endif
2222
2223         xfs_btree_buf_to_ptr(cur, lbp, &lptr);
2224
2225         /* Allocate the new block. If we can't do it, we're toast. Give up. */
2226         error = cur->bc_ops->alloc_block(cur, &lptr, &rptr, 1, stat);
2227         if (error)
2228                 goto error0;
2229         if (*stat == 0)
2230                 goto out0;
2231         XFS_BTREE_STATS_INC(cur, alloc);
2232
2233         /* Set up the new block as "right". */
2234         error = xfs_btree_get_buf_block(cur, &rptr, 0, &right, &rbp);
2235         if (error)
2236                 goto error0;
2237
2238         /* Fill in the btree header for the new right block. */
2239         xfs_btree_init_block(cur, xfs_btree_get_level(left), 0, right);
2240
2241         /*
2242          * Split the entries between the old and the new block evenly.
2243          * Make sure that if there's an odd number of entries now, that
2244          * each new block will have the same number of entries.
2245          */
2246         lrecs = xfs_btree_get_numrecs(left);
2247         rrecs = lrecs / 2;
2248         if ((lrecs & 1) && cur->bc_ptrs[level] <= rrecs + 1)
2249                 rrecs++;
2250         src_index = (lrecs - rrecs + 1);
2251
2252         XFS_BTREE_STATS_ADD(cur, moves, rrecs);
2253
2254         /*
2255          * Copy btree block entries from the left block over to the
2256          * new block, the right. Update the right block and log the
2257          * changes.
2258          */
2259         if (level > 0) {
2260                 /* It's a non-leaf.  Move keys and pointers. */
2261                 union xfs_btree_key     *lkp;   /* left btree key */
2262                 union xfs_btree_ptr     *lpp;   /* left address pointer */
2263                 union xfs_btree_key     *rkp;   /* right btree key */
2264                 union xfs_btree_ptr     *rpp;   /* right address pointer */
2265
2266                 lkp = xfs_btree_key_addr(cur, src_index, left);
2267                 lpp = xfs_btree_ptr_addr(cur, src_index, left);
2268                 rkp = xfs_btree_key_addr(cur, 1, right);
2269                 rpp = xfs_btree_ptr_addr(cur, 1, right);
2270
2271 #ifdef DEBUG
2272                 for (i = src_index; i < rrecs; i++) {
2273                         error = xfs_btree_check_ptr(cur, lpp, i, level);
2274                         if (error)
2275                                 goto error0;
2276                 }
2277 #endif
2278
2279                 xfs_btree_copy_keys(cur, rkp, lkp, rrecs);
2280                 xfs_btree_copy_ptrs(cur, rpp, lpp, rrecs);
2281
2282                 xfs_btree_log_keys(cur, rbp, 1, rrecs);
2283                 xfs_btree_log_ptrs(cur, rbp, 1, rrecs);
2284
2285                 /* Grab the keys to the entries moved to the right block */
2286                 xfs_btree_copy_keys(cur, key, rkp, 1);
2287         } else {
2288                 /* It's a leaf.  Move records.  */
2289                 union xfs_btree_rec     *lrp;   /* left record pointer */
2290                 union xfs_btree_rec     *rrp;   /* right record pointer */
2291
2292                 lrp = xfs_btree_rec_addr(cur, src_index, left);
2293                 rrp = xfs_btree_rec_addr(cur, 1, right);
2294
2295                 xfs_btree_copy_recs(cur, rrp, lrp, rrecs);
2296                 xfs_btree_log_recs(cur, rbp, 1, rrecs);
2297
2298                 cur->bc_ops->init_key_from_rec(key,
2299                         xfs_btree_rec_addr(cur, 1, right));
2300         }
2301
2302
2303         /*
2304          * Find the left block number by looking in the buffer.
2305          * Adjust numrecs, sibling pointers.
2306          */
2307         xfs_btree_get_sibling(cur, left, &rrptr, XFS_BB_RIGHTSIB);
2308         xfs_btree_set_sibling(cur, right, &rrptr, XFS_BB_RIGHTSIB);
2309         xfs_btree_set_sibling(cur, right, &lptr, XFS_BB_LEFTSIB);
2310         xfs_btree_set_sibling(cur, left, &rptr, XFS_BB_RIGHTSIB);
2311
2312         lrecs -= rrecs;
2313         xfs_btree_set_numrecs(left, lrecs);
2314         xfs_btree_set_numrecs(right, xfs_btree_get_numrecs(right) + rrecs);
2315
2316         xfs_btree_log_block(cur, rbp, XFS_BB_ALL_BITS);
2317         xfs_btree_log_block(cur, lbp, XFS_BB_NUMRECS | XFS_BB_RIGHTSIB);
2318
2319         /*
2320          * If there's a block to the new block's right, make that block
2321          * point back to right instead of to left.
2322          */
2323         if (!xfs_btree_ptr_is_null(cur, &rrptr)) {
2324                 error = xfs_btree_read_buf_block(cur, &rrptr, level,
2325                                                         0, &rrblock, &rrbp);
2326                 if (error)
2327                         goto error0;
2328                 xfs_btree_set_sibling(cur, rrblock, &rptr, XFS_BB_LEFTSIB);
2329                 xfs_btree_log_block(cur, rrbp, XFS_BB_LEFTSIB);
2330         }
2331         /*
2332          * If the cursor is really in the right block, move it there.
2333          * If it's just pointing past the last entry in left, then we'll
2334          * insert there, so don't change anything in that case.
2335          */
2336         if (cur->bc_ptrs[level] > lrecs + 1) {
2337                 xfs_btree_setbuf(cur, level, rbp);
2338                 cur->bc_ptrs[level] -= lrecs;
2339         }
2340         /*
2341          * If there are more levels, we'll need another cursor which refers
2342          * the right block, no matter where this cursor was.
2343          */
2344         if (level + 1 < cur->bc_nlevels) {
2345                 error = xfs_btree_dup_cursor(cur, curp);
2346                 if (error)
2347                         goto error0;
2348                 (*curp)->bc_ptrs[level + 1]++;
2349         }
2350         *ptrp = rptr;
2351         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
2352         *stat = 1;
2353         return 0;
2354 out0:
2355         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
2356         *stat = 0;
2357         return 0;
2358
2359 error0:
2360         XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
2361         return error;
2362 }
2363
2364 /*
2365  * Copy the old inode root contents into a real block and make the
2366  * broot point to it.
2367  */
2368 int                                             /* error */
2369 xfs_btree_new_iroot(
2370         struct xfs_btree_cur    *cur,           /* btree cursor */
2371         int                     *logflags,      /* logging flags for inode */
2372         int                     *stat)          /* return status - 0 fail */
2373 {
2374         struct xfs_buf          *cbp;           /* buffer for cblock */
2375         struct xfs_btree_block  *block;         /* btree block */
2376         struct xfs_btree_block  *cblock;        /* child btree block */
2377         union xfs_btree_key     *ckp;           /* child key pointer */
2378         union xfs_btree_ptr     *cpp;           /* child ptr pointer */
2379         union xfs_btree_key     *kp;            /* pointer to btree key */
2380         union xfs_btree_ptr     *pp;            /* pointer to block addr */
2381         union xfs_btree_ptr     nptr;           /* new block addr */
2382         int                     level;          /* btree level */
2383         int                     error;          /* error return code */
2384 #ifdef DEBUG
2385         int                     i;              /* loop counter */
2386 #endif
2387
2388         XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
2389         XFS_BTREE_STATS_INC(cur, newroot);
2390
2391         ASSERT(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE);
2392
2393         level = cur->bc_nlevels - 1;
2394
2395         block = xfs_btree_get_iroot(cur);
2396         pp = xfs_btree_ptr_addr(cur, 1, block);
2397
2398         /* Allocate the new block. If we can't do it, we're toast. Give up. */
2399         error = cur->bc_ops->alloc_block(cur, pp, &nptr, 1, stat);
2400         if (error)
2401                 goto error0;
2402         if (*stat == 0) {
2403                 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
2404                 return 0;
2405         }
2406         XFS_BTREE_STATS_INC(cur, alloc);
2407
2408         /* Copy the root into a real block. */
2409         error = xfs_btree_get_buf_block(cur, &nptr, 0, &cblock, &cbp);
2410         if (error)
2411                 goto error0;
2412
2413         memcpy(cblock, block, xfs_btree_block_len(cur));
2414
2415         be16_add_cpu(&block->bb_level, 1);
2416         xfs_btree_set_numrecs(block, 1);
2417         cur->bc_nlevels++;
2418         cur->bc_ptrs[level + 1] = 1;
2419
2420         kp = xfs_btree_key_addr(cur, 1, block);
2421         ckp = xfs_btree_key_addr(cur, 1, cblock);
2422         xfs_btree_copy_keys(cur, ckp, kp, xfs_btree_get_numrecs(cblock));
2423
2424         cpp = xfs_btree_ptr_addr(cur, 1, cblock);
2425 #ifdef DEBUG
2426         for (i = 0; i < be16_to_cpu(cblock->bb_numrecs); i++) {
2427                 error = xfs_btree_check_ptr(cur, pp, i, level);
2428                 if (error)
2429                         goto error0;
2430         }
2431 #endif
2432         xfs_btree_copy_ptrs(cur, cpp, pp, xfs_btree_get_numrecs(cblock));
2433
2434 #ifdef DEBUG
2435         error = xfs_btree_check_ptr(cur, &nptr, 0, level);
2436         if (error)
2437                 goto error0;
2438 #endif
2439         xfs_btree_copy_ptrs(cur, pp, &nptr, 1);
2440
2441         xfs_iroot_realloc(cur->bc_private.b.ip,
2442                           1 - xfs_btree_get_numrecs(cblock),
2443                           cur->bc_private.b.whichfork);
2444
2445         xfs_btree_setbuf(cur, level, cbp);
2446
2447         /*
2448          * Do all this logging at the end so that
2449          * the root is at the right level.
2450          */
2451         xfs_btree_log_block(cur, cbp, XFS_BB_ALL_BITS);
2452         xfs_btree_log_keys(cur, cbp, 1, be16_to_cpu(cblock->bb_numrecs));
2453         xfs_btree_log_ptrs(cur, cbp, 1, be16_to_cpu(cblock->bb_numrecs));
2454
2455         *logflags |=
2456                 XFS_ILOG_CORE | XFS_ILOG_FBROOT(cur->bc_private.b.whichfork);
2457         *stat = 1;
2458         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
2459         return 0;
2460 error0:
2461         XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
2462         return error;
2463 }
2464
2465 /*
2466  * Allocate a new root block, fill it in.
2467  */
2468 STATIC int                              /* error */
2469 xfs_btree_new_root(
2470         struct xfs_btree_cur    *cur,   /* btree cursor */
2471         int                     *stat)  /* success/failure */
2472 {
2473         struct xfs_btree_block  *block; /* one half of the old root block */
2474         struct xfs_buf          *bp;    /* buffer containing block */
2475         int                     error;  /* error return value */
2476         struct xfs_buf          *lbp;   /* left buffer pointer */
2477         struct xfs_btree_block  *left;  /* left btree block */
2478         struct xfs_buf          *nbp;   /* new (root) buffer */
2479         struct xfs_btree_block  *new;   /* new (root) btree block */
2480         int                     nptr;   /* new value for key index, 1 or 2 */
2481         struct xfs_buf          *rbp;   /* right buffer pointer */
2482         struct xfs_btree_block  *right; /* right btree block */
2483         union xfs_btree_ptr     rptr;
2484         union xfs_btree_ptr     lptr;
2485
2486         XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
2487         XFS_BTREE_STATS_INC(cur, newroot);
2488
2489         /* initialise our start point from the cursor */
2490         cur->bc_ops->init_ptr_from_cur(cur, &rptr);
2491
2492         /* Allocate the new block. If we can't do it, we're toast. Give up. */
2493         error = cur->bc_ops->alloc_block(cur, &rptr, &lptr, 1, stat);
2494         if (error)
2495                 goto error0;
2496         if (*stat == 0)
2497                 goto out0;
2498         XFS_BTREE_STATS_INC(cur, alloc);
2499
2500         /* Set up the new block. */
2501         error = xfs_btree_get_buf_block(cur, &lptr, 0, &new, &nbp);
2502         if (error)
2503                 goto error0;
2504
2505         /* Set the root in the holding structure  increasing the level by 1. */
2506         cur->bc_ops->set_root(cur, &lptr, 1);
2507
2508         /*
2509          * At the previous root level there are now two blocks: the old root,
2510          * and the new block generated when it was split.  We don't know which
2511          * one the cursor is pointing at, so we set up variables "left" and
2512          * "right" for each case.
2513          */
2514         block = xfs_btree_get_block(cur, cur->bc_nlevels - 1, &bp);
2515
2516 #ifdef DEBUG
2517         error = xfs_btree_check_block(cur, block, cur->bc_nlevels - 1, bp);
2518         if (error)
2519                 goto error0;
2520 #endif
2521
2522         xfs_btree_get_sibling(cur, block, &rptr, XFS_BB_RIGHTSIB);
2523         if (!xfs_btree_ptr_is_null(cur, &rptr)) {
2524                 /* Our block is left, pick up the right block. */
2525                 lbp = bp;
2526                 xfs_btree_buf_to_ptr(cur, lbp, &lptr);
2527                 left = block;
2528                 error = xfs_btree_read_buf_block(cur, &rptr,
2529                                         cur->bc_nlevels - 1, 0, &right, &rbp);
2530                 if (error)
2531                         goto error0;
2532                 bp = rbp;
2533                 nptr = 1;
2534         } else {
2535                 /* Our block is right, pick up the left block. */
2536                 rbp = bp;
2537                 xfs_btree_buf_to_ptr(cur, rbp, &rptr);
2538                 right = block;
2539                 xfs_btree_get_sibling(cur, right, &lptr, XFS_BB_LEFTSIB);
2540                 error = xfs_btree_read_buf_block(cur, &lptr,
2541                                         cur->bc_nlevels - 1, 0, &left, &lbp);
2542                 if (error)
2543                         goto error0;
2544                 bp = lbp;
2545                 nptr = 2;
2546         }
2547         /* Fill in the new block's btree header and log it. */
2548         xfs_btree_init_block(cur, cur->bc_nlevels, 2, new);
2549         xfs_btree_log_block(cur, nbp, XFS_BB_ALL_BITS);
2550         ASSERT(!xfs_btree_ptr_is_null(cur, &lptr) &&
2551                         !xfs_btree_ptr_is_null(cur, &rptr));
2552
2553         /* Fill in the key data in the new root. */
2554         if (xfs_btree_get_level(left) > 0) {
2555                 xfs_btree_copy_keys(cur,
2556                                 xfs_btree_key_addr(cur, 1, new),
2557                                 xfs_btree_key_addr(cur, 1, left), 1);
2558                 xfs_btree_copy_keys(cur,
2559                                 xfs_btree_key_addr(cur, 2, new),
2560                                 xfs_btree_key_addr(cur, 1, right), 1);
2561         } else {
2562                 cur->bc_ops->init_key_from_rec(
2563                                 xfs_btree_key_addr(cur, 1, new),
2564                                 xfs_btree_rec_addr(cur, 1, left));
2565                 cur->bc_ops->init_key_from_rec(
2566                                 xfs_btree_key_addr(cur, 2, new),
2567                                 xfs_btree_rec_addr(cur, 1, right));
2568         }
2569         xfs_btree_log_keys(cur, nbp, 1, 2);
2570
2571         /* Fill in the pointer data in the new root. */
2572         xfs_btree_copy_ptrs(cur,
2573                 xfs_btree_ptr_addr(cur, 1, new), &lptr, 1);
2574         xfs_btree_copy_ptrs(cur,
2575                 xfs_btree_ptr_addr(cur, 2, new), &rptr, 1);
2576         xfs_btree_log_ptrs(cur, nbp, 1, 2);
2577
2578         /* Fix up the cursor. */
2579         xfs_btree_setbuf(cur, cur->bc_nlevels, nbp);
2580         cur->bc_ptrs[cur->bc_nlevels] = nptr;
2581         cur->bc_nlevels++;
2582         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
2583         *stat = 1;
2584         return 0;
2585 error0:
2586         XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
2587         return error;
2588 out0:
2589         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
2590         *stat = 0;
2591         return 0;
2592 }
2593
2594 STATIC int
2595 xfs_btree_make_block_unfull(
2596         struct xfs_btree_cur    *cur,   /* btree cursor */
2597         int                     level,  /* btree level */
2598         int                     numrecs,/* # of recs in block */
2599         int                     *oindex,/* old tree index */
2600         int                     *index, /* new tree index */
2601         union xfs_btree_ptr     *nptr,  /* new btree ptr */
2602         struct xfs_btree_cur    **ncur, /* new btree cursor */
2603         union xfs_btree_rec     *nrec,  /* new record */
2604         int                     *stat)
2605 {
2606         union xfs_btree_key     key;    /* new btree key value */
2607         int                     error = 0;
2608
2609         if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
2610             level == cur->bc_nlevels - 1) {
2611                 struct xfs_inode *ip = cur->bc_private.b.ip;
2612
2613                 if (numrecs < cur->bc_ops->get_dmaxrecs(cur, level)) {
2614                         /* A root block that can be made bigger. */
2615
2616                         xfs_iroot_realloc(ip, 1, cur->bc_private.b.whichfork);
2617                 } else {
2618                         /* A root block that needs replacing */
2619                         int     logflags = 0;
2620
2621                         error = xfs_btree_new_iroot(cur, &logflags, stat);
2622                         if (error || *stat == 0)
2623                                 return error;
2624
2625                         xfs_trans_log_inode(cur->bc_tp, ip, logflags);
2626                 }
2627
2628                 return 0;
2629         }
2630
2631         /* First, try shifting an entry to the right neighbor. */
2632         error = xfs_btree_rshift(cur, level, stat);
2633         if (error || *stat)
2634                 return error;
2635
2636         /* Next, try shifting an entry to the left neighbor. */
2637         error = xfs_btree_lshift(cur, level, stat);
2638         if (error)
2639                 return error;
2640
2641         if (*stat) {
2642                 *oindex = *index = cur->bc_ptrs[level];
2643                 return 0;
2644         }
2645
2646         /*
2647          * Next, try splitting the current block in half.
2648          *
2649          * If this works we have to re-set our variables because we
2650          * could be in a different block now.
2651          */
2652         error = xfs_btree_split(cur, level, nptr, &key, ncur, stat);
2653         if (error || *stat == 0)
2654                 return error;
2655
2656
2657         *index = cur->bc_ptrs[level];
2658         cur->bc_ops->init_rec_from_key(&key, nrec);
2659         return 0;
2660 }
2661
2662 /*
2663  * Insert one record/level.  Return information to the caller
2664  * allowing the next level up to proceed if necessary.
2665  */
2666 STATIC int
2667 xfs_btree_insrec(
2668         struct xfs_btree_cur    *cur,   /* btree cursor */
2669         int                     level,  /* level to insert record at */
2670         union xfs_btree_ptr     *ptrp,  /* i/o: block number inserted */
2671         union xfs_btree_rec     *recp,  /* i/o: record data inserted */
2672         struct xfs_btree_cur    **curp, /* output: new cursor replacing cur */
2673         int                     *stat)  /* success/failure */
2674 {
2675         struct xfs_btree_block  *block; /* btree block */
2676         struct xfs_buf          *bp;    /* buffer for block */
2677         union xfs_btree_key     key;    /* btree key */
2678         union xfs_btree_ptr     nptr;   /* new block ptr */
2679         struct xfs_btree_cur    *ncur;  /* new btree cursor */
2680         union xfs_btree_rec     nrec;   /* new record count */
2681         int                     optr;   /* old key/record index */
2682         int                     ptr;    /* key/record index */
2683         int                     numrecs;/* number of records */
2684         int                     error;  /* error return value */
2685 #ifdef DEBUG
2686         int                     i;
2687 #endif
2688
2689         XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
2690         XFS_BTREE_TRACE_ARGIPR(cur, level, *ptrp, recp);
2691
2692         ncur = NULL;
2693
2694         /*
2695          * If we have an external root pointer, and we've made it to the
2696          * root level, allocate a new root block and we're done.
2697          */
2698         if (!(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
2699             (level >= cur->bc_nlevels)) {
2700                 error = xfs_btree_new_root(cur, stat);
2701                 xfs_btree_set_ptr_null(cur, ptrp);
2702
2703                 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
2704                 return error;
2705         }
2706
2707         /* If we're off the left edge, return failure. */
2708         ptr = cur->bc_ptrs[level];
2709         if (ptr == 0) {
2710                 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
2711                 *stat = 0;
2712                 return 0;
2713         }
2714
2715         /* Make a key out of the record data to be inserted, and save it. */
2716         cur->bc_ops->init_key_from_rec(&key, recp);
2717
2718         optr = ptr;
2719
2720         XFS_BTREE_STATS_INC(cur, insrec);
2721
2722         /* Get pointers to the btree buffer and block. */
2723         block = xfs_btree_get_block(cur, level, &bp);
2724         numrecs = xfs_btree_get_numrecs(block);
2725
2726 #ifdef DEBUG
2727         error = xfs_btree_check_block(cur, block, level, bp);
2728         if (error)
2729                 goto error0;
2730
2731         /* Check that the new entry is being inserted in the right place. */
2732         if (ptr <= numrecs) {
2733                 if (level == 0) {
2734                         ASSERT(cur->bc_ops->recs_inorder(cur, recp,
2735                                 xfs_btree_rec_addr(cur, ptr, block)));
2736                 } else {
2737                         ASSERT(cur->bc_ops->keys_inorder(cur, &key,
2738                                 xfs_btree_key_addr(cur, ptr, block)));
2739                 }
2740         }
2741 #endif
2742
2743         /*
2744          * If the block is full, we can't insert the new entry until we
2745          * make the block un-full.
2746          */
2747         xfs_btree_set_ptr_null(cur, &nptr);
2748         if (numrecs == cur->bc_ops->get_maxrecs(cur, level)) {
2749                 error = xfs_btree_make_block_unfull(cur, level, numrecs,
2750                                         &optr, &ptr, &nptr, &ncur, &nrec, stat);
2751                 if (error || *stat == 0)
2752                         goto error0;
2753         }
2754
2755         /*
2756          * The current block may have changed if the block was
2757          * previously full and we have just made space in it.
2758          */
2759         block = xfs_btree_get_block(cur, level, &bp);
2760         numrecs = xfs_btree_get_numrecs(block);
2761
2762 #ifdef DEBUG
2763         error = xfs_btree_check_block(cur, block, level, bp);
2764         if (error)
2765                 return error;
2766 #endif
2767
2768         /*
2769          * At this point we know there's room for our new entry in the block
2770          * we're pointing at.
2771          */
2772         XFS_BTREE_STATS_ADD(cur, moves, numrecs - ptr + 1);
2773
2774         if (level > 0) {
2775                 /* It's a nonleaf. make a hole in the keys and ptrs */
2776                 union xfs_btree_key     *kp;
2777                 union xfs_btree_ptr     *pp;
2778
2779                 kp = xfs_btree_key_addr(cur, ptr, block);
2780                 pp = xfs_btree_ptr_addr(cur, ptr, block);
2781
2782 #ifdef DEBUG
2783                 for (i = numrecs - ptr; i >= 0; i--) {
2784                         error = xfs_btree_check_ptr(cur, pp, i, level);
2785                         if (error)
2786                                 return error;
2787                 }
2788 #endif
2789
2790                 xfs_btree_shift_keys(cur, kp, 1, numrecs - ptr + 1);
2791                 xfs_btree_shift_ptrs(cur, pp, 1, numrecs - ptr + 1);
2792
2793 #ifdef DEBUG
2794                 error = xfs_btree_check_ptr(cur, ptrp, 0, level);
2795                 if (error)
2796                         goto error0;
2797 #endif
2798
2799                 /* Now put the new data in, bump numrecs and log it. */
2800                 xfs_btree_copy_keys(cur, kp, &key, 1);
2801                 xfs_btree_copy_ptrs(cur, pp, ptrp, 1);
2802                 numrecs++;
2803                 xfs_btree_set_numrecs(block, numrecs);
2804                 xfs_btree_log_ptrs(cur, bp, ptr, numrecs);
2805                 xfs_btree_log_keys(cur, bp, ptr, numrecs);
2806 #ifdef DEBUG
2807                 if (ptr < numrecs) {
2808                         ASSERT(cur->bc_ops->keys_inorder(cur, kp,
2809                                 xfs_btree_key_addr(cur, ptr + 1, block)));
2810                 }
2811 #endif
2812         } else {
2813                 /* It's a leaf. make a hole in the records */
2814                 union xfs_btree_rec             *rp;
2815
2816                 rp = xfs_btree_rec_addr(cur, ptr, block);
2817
2818                 xfs_btree_shift_recs(cur, rp, 1, numrecs - ptr + 1);
2819
2820                 /* Now put the new data in, bump numrecs and log it. */
2821                 xfs_btree_copy_recs(cur, rp, recp, 1);
2822                 xfs_btree_set_numrecs(block, ++numrecs);
2823                 xfs_btree_log_recs(cur, bp, ptr, numrecs);
2824 #ifdef DEBUG
2825                 if (ptr < numrecs) {
2826                         ASSERT(cur->bc_ops->recs_inorder(cur, rp,
2827                                 xfs_btree_rec_addr(cur, ptr + 1, block)));
2828                 }
2829 #endif
2830         }
2831
2832         /* Log the new number of records in the btree header. */
2833         xfs_btree_log_block(cur, bp, XFS_BB_NUMRECS);
2834
2835         /* If we inserted at the start of a block, update the parents' keys. */
2836         if (optr == 1) {
2837                 error = xfs_btree_updkey(cur, &key, level + 1);
2838                 if (error)
2839                         goto error0;
2840         }
2841
2842         /*
2843          * If we are tracking the last record in the tree and
2844          * we are at the far right edge of the tree, update it.
2845          */
2846         if (xfs_btree_is_lastrec(cur, block, level)) {
2847                 cur->bc_ops->update_lastrec(cur, block, recp,
2848                                             ptr, LASTREC_INSREC);
2849         }
2850
2851         /*
2852          * Return the new block number, if any.
2853          * If there is one, give back a record value and a cursor too.
2854          */
2855         *ptrp = nptr;
2856         if (!xfs_btree_ptr_is_null(cur, &nptr)) {
2857                 *recp = nrec;
2858                 *curp = ncur;
2859         }
2860
2861         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
2862         *stat = 1;
2863         return 0;
2864
2865 error0:
2866         XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
2867         return error;
2868 }
2869
2870 /*
2871  * Insert the record at the point referenced by cur.
2872  *
2873  * A multi-level split of the tree on insert will invalidate the original
2874  * cursor.  All callers of this function should assume that the cursor is
2875  * no longer valid and revalidate it.
2876  */
2877 int
2878 xfs_btree_insert(
2879         struct xfs_btree_cur    *cur,
2880         int                     *stat)
2881 {
2882         int                     error;  /* error return value */
2883         int                     i;      /* result value, 0 for failure */
2884         int                     level;  /* current level number in btree */
2885         union xfs_btree_ptr     nptr;   /* new block number (split result) */
2886         struct xfs_btree_cur    *ncur;  /* new cursor (split result) */
2887         struct xfs_btree_cur    *pcur;  /* previous level's cursor */
2888         union xfs_btree_rec     rec;    /* record to insert */
2889
2890         level = 0;
2891         ncur = NULL;
2892         pcur = cur;
2893
2894         xfs_btree_set_ptr_null(cur, &nptr);
2895         cur->bc_ops->init_rec_from_cur(cur, &rec);
2896
2897         /*
2898          * Loop going up the tree, starting at the leaf level.
2899          * Stop when we don't get a split block, that must mean that
2900          * the insert is finished with this level.
2901          */
2902         do {
2903                 /*
2904                  * Insert nrec/nptr into this level of the tree.
2905                  * Note if we fail, nptr will be null.
2906                  */
2907                 error = xfs_btree_insrec(pcur, level, &nptr, &rec, &ncur, &i);
2908                 if (error) {
2909                         if (pcur != cur)
2910                                 xfs_btree_del_cursor(pcur, XFS_BTREE_ERROR);
2911                         goto error0;
2912                 }
2913
2914                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
2915                 level++;
2916
2917                 /*
2918                  * See if the cursor we just used is trash.
2919                  * Can't trash the caller's cursor, but otherwise we should
2920                  * if ncur is a new cursor or we're about to be done.
2921                  */
2922                 if (pcur != cur &&
2923                     (ncur || xfs_btree_ptr_is_null(cur, &nptr))) {
2924                         /* Save the state from the cursor before we trash it */
2925                         if (cur->bc_ops->update_cursor)
2926                                 cur->bc_ops->update_cursor(pcur, cur);
2927                         cur->bc_nlevels = pcur->bc_nlevels;
2928                         xfs_btree_del_cursor(pcur, XFS_BTREE_NOERROR);
2929                 }
2930                 /* If we got a new cursor, switch to it. */
2931                 if (ncur) {
2932                         pcur = ncur;
2933                         ncur = NULL;
2934                 }
2935         } while (!xfs_btree_ptr_is_null(cur, &nptr));
2936
2937         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
2938         *stat = i;
2939         return 0;
2940 error0:
2941         XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
2942         return error;
2943 }
2944
2945 /*
2946  * Try to merge a non-leaf block back into the inode root.
2947  *
2948  * Note: the killroot names comes from the fact that we're effectively
2949  * killing the old root block.  But because we can't just delete the
2950  * inode we have to copy the single block it was pointing to into the
2951  * inode.
2952  */
2953 int
2954 xfs_btree_kill_iroot(
2955         struct xfs_btree_cur    *cur)
2956 {
2957         int                     whichfork = cur->bc_private.b.whichfork;
2958         struct xfs_inode        *ip = cur->bc_private.b.ip;
2959         struct xfs_ifork        *ifp = XFS_IFORK_PTR(ip, whichfork);
2960         struct xfs_btree_block  *block;
2961         struct xfs_btree_block  *cblock;
2962         union xfs_btree_key     *kp;
2963         union xfs_btree_key     *ckp;
2964         union xfs_btree_ptr     *pp;
2965         union xfs_btree_ptr     *cpp;
2966         struct xfs_buf          *cbp;
2967         int                     level;
2968         int                     index;
2969         int                     numrecs;
2970 #ifdef DEBUG
2971         union xfs_btree_ptr     ptr;
2972         int                     i;
2973 #endif
2974
2975         XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
2976
2977         ASSERT(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE);
2978         ASSERT(cur->bc_nlevels > 1);
2979
2980         /*
2981          * Don't deal with the root block needs to be a leaf case.
2982          * We're just going to turn the thing back into extents anyway.
2983          */
2984         level = cur->bc_nlevels - 1;
2985         if (level == 1)
2986                 goto out0;
2987
2988         /*
2989          * Give up if the root has multiple children.
2990          */
2991         block = xfs_btree_get_iroot(cur);
2992         if (xfs_btree_get_numrecs(block) != 1)
2993                 goto out0;
2994
2995         cblock = xfs_btree_get_block(cur, level - 1, &cbp);
2996         numrecs = xfs_btree_get_numrecs(cblock);
2997
2998         /*
2999          * Only do this if the next level will fit.
3000          * Then the data must be copied up to the inode,
3001          * instead of freeing the root you free the next level.
3002          */
3003         if (numrecs > cur->bc_ops->get_dmaxrecs(cur, level))
3004                 goto out0;
3005
3006         XFS_BTREE_STATS_INC(cur, killroot);
3007
3008 #ifdef DEBUG
3009         xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_LEFTSIB);
3010         ASSERT(xfs_btree_ptr_is_null(cur, &ptr));
3011         xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB);
3012         ASSERT(xfs_btree_ptr_is_null(cur, &ptr));
3013 #endif
3014
3015         index = numrecs - cur->bc_ops->get_maxrecs(cur, level);
3016         if (index) {
3017                 xfs_iroot_realloc(cur->bc_private.b.ip, index,
3018                                   cur->bc_private.b.whichfork);
3019                 block = (struct xfs_btree_block *)ifp->if_broot;
3020         }
3021
3022         be16_add_cpu(&block->bb_numrecs, index);
3023         ASSERT(block->bb_numrecs == cblock->bb_numrecs);
3024
3025         kp = xfs_btree_key_addr(cur, 1, block);
3026         ckp = xfs_btree_key_addr(cur, 1, cblock);
3027         xfs_btree_copy_keys(cur, kp, ckp, numrecs);
3028
3029         pp = xfs_btree_ptr_addr(cur, 1, block);
3030         cpp = xfs_btree_ptr_addr(cur, 1, cblock);
3031 #ifdef DEBUG
3032         for (i = 0; i < numrecs; i++) {
3033                 int             error;
3034
3035                 error = xfs_btree_check_ptr(cur, cpp, i, level - 1);
3036                 if (error) {
3037                         XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
3038                         return error;
3039                 }
3040         }
3041 #endif
3042         xfs_btree_copy_ptrs(cur, pp, cpp, numrecs);
3043
3044         cur->bc_ops->free_block(cur, cbp);
3045         XFS_BTREE_STATS_INC(cur, free);
3046
3047         cur->bc_bufs[level - 1] = NULL;
3048         be16_add_cpu(&block->bb_level, -1);
3049         xfs_trans_log_inode(cur->bc_tp, ip,
3050                 XFS_ILOG_CORE | XFS_ILOG_FBROOT(cur->bc_private.b.whichfork));
3051         cur->bc_nlevels--;
3052 out0:
3053         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
3054         return 0;
3055 }
3056
3057 STATIC int
3058 xfs_btree_dec_cursor(
3059         struct xfs_btree_cur    *cur,
3060         int                     level,
3061         int                     *stat)
3062 {
3063         int                     error;
3064         int                     i;
3065
3066         if (level > 0) {
3067                 error = xfs_btree_decrement(cur, level, &i);
3068                 if (error)
3069                         return error;
3070         }
3071
3072         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
3073         *stat = 1;
3074         return 0;
3075 }
3076
3077 /*
3078  * Single level of the btree record deletion routine.
3079  * Delete record pointed to by cur/level.
3080  * Remove the record from its block then rebalance the tree.
3081  * Return 0 for error, 1 for done, 2 to go on to the next level.
3082  */
3083 STATIC int                                      /* error */
3084 xfs_btree_delrec(
3085         struct xfs_btree_cur    *cur,           /* btree cursor */
3086         int                     level,          /* level removing record from */
3087         int                     *stat)          /* fail/done/go-on */
3088 {
3089         struct xfs_btree_block  *block;         /* btree block */
3090         union xfs_btree_ptr     cptr;           /* current block ptr */
3091         struct xfs_buf          *bp;            /* buffer for block */
3092         int                     error;          /* error return value */
3093         int                     i;              /* loop counter */
3094         union xfs_btree_key     key;            /* storage for keyp */
3095         union xfs_btree_key     *keyp = &key;   /* passed to the next level */
3096         union xfs_btree_ptr     lptr;           /* left sibling block ptr */
3097         struct xfs_buf          *lbp;           /* left buffer pointer */
3098         struct xfs_btree_block  *left;          /* left btree block */
3099         int                     lrecs = 0;      /* left record count */
3100         int                     ptr;            /* key/record index */
3101         union xfs_btree_ptr     rptr;           /* right sibling block ptr */
3102         struct xfs_buf          *rbp;           /* right buffer pointer */
3103         struct xfs_btree_block  *right;         /* right btree block */
3104         struct xfs_btree_block  *rrblock;       /* right-right btree block */
3105         struct xfs_buf          *rrbp;          /* right-right buffer pointer */
3106         int                     rrecs = 0;      /* right record count */
3107         struct xfs_btree_cur    *tcur;          /* temporary btree cursor */
3108         int                     numrecs;        /* temporary numrec count */
3109
3110         XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
3111         XFS_BTREE_TRACE_ARGI(cur, level);
3112
3113         tcur = NULL;
3114
3115         /* Get the index of the entry being deleted, check for nothing there. */
3116         ptr = cur->bc_ptrs[level];
3117         if (ptr == 0) {
3118                 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
3119                 *stat = 0;
3120                 return 0;
3121         }
3122
3123         /* Get the buffer & block containing the record or key/ptr. */
3124         block = xfs_btree_get_block(cur, level, &bp);
3125         numrecs = xfs_btree_get_numrecs(block);
3126
3127 #ifdef DEBUG
3128         error = xfs_btree_check_block(cur, block, level, bp);
3129         if (error)
3130                 goto error0;
3131 #endif
3132
3133         /* Fail if we're off the end of the block. */
3134         if (ptr > numrecs) {
3135                 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
3136                 *stat = 0;
3137                 return 0;
3138         }
3139
3140         XFS_BTREE_STATS_INC(cur, delrec);
3141         XFS_BTREE_STATS_ADD(cur, moves, numrecs - ptr);
3142
3143         /* Excise the entries being deleted. */
3144         if (level > 0) {
3145                 /* It's a nonleaf. operate on keys and ptrs */
3146                 union xfs_btree_key     *lkp;
3147                 union xfs_btree_ptr     *lpp;
3148
3149                 lkp = xfs_btree_key_addr(cur, ptr + 1, block);
3150                 lpp = xfs_btree_ptr_addr(cur, ptr + 1, block);
3151
3152 #ifdef DEBUG
3153                 for (i = 0; i < numrecs - ptr; i++) {
3154                         error = xfs_btree_check_ptr(cur, lpp, i, level);
3155                         if (error)
3156                                 goto error0;
3157                 }
3158 #endif
3159
3160                 if (ptr < numrecs) {
3161                         xfs_btree_shift_keys(cur, lkp, -1, numrecs - ptr);
3162                         xfs_btree_shift_ptrs(cur, lpp, -1, numrecs - ptr);
3163                         xfs_btree_log_keys(cur, bp, ptr, numrecs - 1);
3164                         xfs_btree_log_ptrs(cur, bp, ptr, numrecs - 1);
3165                 }
3166
3167                 /*
3168                  * If it's the first record in the block, we'll need to pass a
3169                  * key up to the next level (updkey).
3170                  */
3171                 if (ptr == 1)
3172                         keyp = xfs_btree_key_addr(cur, 1, block);
3173         } else {
3174                 /* It's a leaf. operate on records */
3175                 if (ptr < numrecs) {
3176                         xfs_btree_shift_recs(cur,
3177                                 xfs_btree_rec_addr(cur, ptr + 1, block),
3178                                 -1, numrecs - ptr);
3179                         xfs_btree_log_recs(cur, bp, ptr, numrecs - 1);
3180                 }
3181
3182                 /*
3183                  * If it's the first record in the block, we'll need a key
3184                  * structure to pass up to the next level (updkey).
3185                  */
3186                 if (ptr == 1) {
3187                         cur->bc_ops->init_key_from_rec(&key,
3188                                         xfs_btree_rec_addr(cur, 1, block));
3189                         keyp = &key;
3190                 }
3191         }
3192
3193         /*
3194          * Decrement and log the number of entries in the block.
3195          */
3196         xfs_btree_set_numrecs(block, --numrecs);
3197         xfs_btree_log_block(cur, bp, XFS_BB_NUMRECS);
3198
3199         /*
3200          * If we are tracking the last record in the tree and
3201          * we are at the far right edge of the tree, update it.
3202          */
3203         if (xfs_btree_is_lastrec(cur, block, level)) {
3204                 cur->bc_ops->update_lastrec(cur, block, NULL,
3205                                             ptr, LASTREC_DELREC);
3206         }
3207
3208         /*
3209          * We're at the root level.  First, shrink the root block in-memory.
3210          * Try to get rid of the next level down.  If we can't then there's
3211          * nothing left to do.
3212          */
3213         if (level == cur->bc_nlevels - 1) {
3214                 if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) {
3215                         xfs_iroot_realloc(cur->bc_private.b.ip, -1,
3216                                           cur->bc_private.b.whichfork);
3217
3218                         error = xfs_btree_kill_iroot(cur);
3219                         if (error)
3220                                 goto error0;
3221
3222                         error = xfs_btree_dec_cursor(cur, level, stat);
3223                         if (error)
3224                                 goto error0;
3225                         *stat = 1;
3226                         return 0;
3227                 }
3228
3229                 /*
3230                  * If this is the root level, and there's only one entry left,
3231                  * and it's NOT the leaf level, then we can get rid of this
3232                  * level.
3233                  */
3234                 if (numrecs == 1 && level > 0) {
3235                         union xfs_btree_ptr     *pp;
3236                         /*
3237                          * pp is still set to the first pointer in the block.
3238                          * Make it the new root of the btree.
3239                          */
3240                         pp = xfs_btree_ptr_addr(cur, 1, block);
3241                         error = cur->bc_ops->kill_root(cur, bp, level, pp);
3242                         if (error)
3243                                 goto error0;
3244                 } else if (level > 0) {
3245                         error = xfs_btree_dec_cursor(cur, level, stat);
3246                         if (error)
3247                                 goto error0;
3248                 }
3249                 *stat = 1;
3250                 return 0;
3251         }
3252
3253         /*
3254          * If we deleted the leftmost entry in the block, update the
3255          * key values above us in the tree.
3256          */
3257         if (ptr == 1) {
3258                 error = xfs_btree_updkey(cur, keyp, level + 1);
3259                 if (error)
3260                         goto error0;
3261         }
3262
3263         /*
3264          * If the number of records remaining in the block is at least
3265          * the minimum, we're done.
3266          */
3267         if (numrecs >= cur->bc_ops->get_minrecs(cur, level)) {
3268                 error = xfs_btree_dec_cursor(cur, level, stat);
3269                 if (error)
3270                         goto error0;
3271                 return 0;
3272         }
3273
3274         /*
3275          * Otherwise, we have to move some records around to keep the
3276          * tree balanced.  Look at the left and right sibling blocks to
3277          * see if we can re-balance by moving only one record.
3278          */
3279         xfs_btree_get_sibling(cur, block, &rptr, XFS_BB_RIGHTSIB);
3280         xfs_btree_get_sibling(cur, block, &lptr, XFS_BB_LEFTSIB);
3281
3282         if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) {
3283                 /*
3284                  * One child of root, need to get a chance to copy its contents
3285                  * into the root and delete it. Can't go up to next level,
3286                  * there's nothing to delete there.
3287                  */
3288                 if (xfs_btree_ptr_is_null(cur, &rptr) &&
3289                     xfs_btree_ptr_is_null(cur, &lptr) &&
3290                     level == cur->bc_nlevels - 2) {
3291                         error = xfs_btree_kill_iroot(cur);
3292                         if (!error)
3293                                 error = xfs_btree_dec_cursor(cur, level, stat);
3294                         if (error)
3295                                 goto error0;
3296                         return 0;
3297                 }
3298         }
3299
3300         ASSERT(!xfs_btree_ptr_is_null(cur, &rptr) ||
3301                !xfs_btree_ptr_is_null(cur, &lptr));
3302
3303         /*
3304          * Duplicate the cursor so our btree manipulations here won't
3305          * disrupt the next level up.
3306          */
3307         error = xfs_btree_dup_cursor(cur, &tcur);
3308         if (error)
3309                 goto error0;
3310
3311         /*
3312          * If there's a right sibling, see if it's ok to shift an entry
3313          * out of it.
3314          */
3315         if (!xfs_btree_ptr_is_null(cur, &rptr)) {
3316                 /*
3317                  * Move the temp cursor to the last entry in the next block.
3318                  * Actually any entry but the first would suffice.
3319                  */
3320                 i = xfs_btree_lastrec(tcur, level);
3321                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
3322
3323                 error = xfs_btree_increment(tcur, level, &i);
3324                 if (error)
3325                         goto error0;
3326                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
3327
3328                 i = xfs_btree_lastrec(tcur, level);
3329                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
3330
3331                 /* Grab a pointer to the block. */
3332                 right = xfs_btree_get_block(tcur, level, &rbp);
3333 #ifdef DEBUG
3334                 error = xfs_btree_check_block(tcur, right, level, rbp);
3335                 if (error)
3336                         goto error0;
3337 #endif
3338                 /* Grab the current block number, for future use. */
3339                 xfs_btree_get_sibling(tcur, right, &cptr, XFS_BB_LEFTSIB);
3340
3341                 /*
3342                  * If right block is full enough so that removing one entry
3343                  * won't make it too empty, and left-shifting an entry out
3344                  * of right to us works, we're done.
3345                  */
3346                 if (xfs_btree_get_numrecs(right) - 1 >=
3347                     cur->bc_ops->get_minrecs(tcur, level)) {
3348                         error = xfs_btree_lshift(tcur, level, &i);
3349                         if (error)
3350                                 goto error0;
3351                         if (i) {
3352                                 ASSERT(xfs_btree_get_numrecs(block) >=
3353                                        cur->bc_ops->get_minrecs(tcur, level));
3354
3355                                 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
3356                                 tcur = NULL;
3357
3358                                 error = xfs_btree_dec_cursor(cur, level, stat);
3359                                 if (error)
3360                                         goto error0;
3361                                 return 0;
3362                         }
3363                 }
3364
3365                 /*
3366                  * Otherwise, grab the number of records in right for
3367                  * future reference, and fix up the temp cursor to point
3368                  * to our block again (last record).
3369                  */
3370                 rrecs = xfs_btree_get_numrecs(right);
3371                 if (!xfs_btree_ptr_is_null(cur, &lptr)) {
3372                         i = xfs_btree_firstrec(tcur, level);
3373                         XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
3374
3375                         error = xfs_btree_decrement(tcur, level, &i);
3376                         if (error)
3377                                 goto error0;
3378                         XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
3379                 }
3380         }
3381
3382         /*
3383          * If there's a left sibling, see if it's ok to shift an entry
3384          * out of it.
3385          */
3386         if (!xfs_btree_ptr_is_null(cur, &lptr)) {
3387                 /*
3388                  * Move the temp cursor to the first entry in the
3389                  * previous block.
3390                  */
3391                 i = xfs_btree_firstrec(tcur, level);
3392                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
3393
3394                 error = xfs_btree_decrement(tcur, level, &i);
3395                 if (error)
3396                         goto error0;
3397                 i = xfs_btree_firstrec(tcur, level);
3398                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
3399
3400                 /* Grab a pointer to the block. */
3401                 left = xfs_btree_get_block(tcur, level, &lbp);
3402 #ifdef DEBUG
3403                 error = xfs_btree_check_block(cur, left, level, lbp);
3404                 if (error)
3405                         goto error0;
3406 #endif
3407                 /* Grab the current block number, for future use. */
3408                 xfs_btree_get_sibling(tcur, left, &cptr, XFS_BB_RIGHTSIB);
3409
3410                 /*
3411                  * If left block is full enough so that removing one entry
3412                  * won't make it too empty, and right-shifting an entry out
3413                  * of left to us works, we're done.
3414                  */
3415                 if (xfs_btree_get_numrecs(left) - 1 >=
3416                     cur->bc_ops->get_minrecs(tcur, level)) {
3417                         error = xfs_btree_rshift(tcur, level, &i);
3418                         if (error)
3419                                 goto error0;
3420                         if (i) {
3421                                 ASSERT(xfs_btree_get_numrecs(block) >=
3422                                        cur->bc_ops->get_minrecs(tcur, level));
3423                                 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
3424                                 tcur = NULL;
3425                                 if (level == 0)
3426                                         cur->bc_ptrs[0]++;
3427                                 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
3428                                 *stat = 1;
3429                                 return 0;
3430                         }
3431                 }
3432
3433                 /*
3434                  * Otherwise, grab the number of records in right for
3435                  * future reference.
3436                  */
3437                 lrecs = xfs_btree_get_numrecs(left);
3438         }
3439
3440         /* Delete the temp cursor, we're done with it. */
3441         xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
3442         tcur = NULL;
3443
3444         /* If here, we need to do a join to keep the tree balanced. */
3445         ASSERT(!xfs_btree_ptr_is_null(cur, &cptr));
3446
3447         if (!xfs_btree_ptr_is_null(cur, &lptr) &&
3448             lrecs + xfs_btree_get_numrecs(block) <=
3449                         cur->bc_ops->get_maxrecs(cur, level)) {
3450                 /*
3451                  * Set "right" to be the starting block,
3452                  * "left" to be the left neighbor.
3453                  */
3454                 rptr = cptr;
3455                 right = block;
3456                 rbp = bp;
3457                 error = xfs_btree_read_buf_block(cur, &lptr, level,
3458                                                         0, &left, &lbp);
3459                 if (error)
3460                         goto error0;
3461
3462         /*
3463          * If that won't work, see if we can join with the right neighbor block.
3464          */
3465         } else if (!xfs_btree_ptr_is_null(cur, &rptr) &&
3466                    rrecs + xfs_btree_get_numrecs(block) <=
3467                         cur->bc_ops->get_maxrecs(cur, level)) {
3468                 /*
3469                  * Set "left" to be the starting block,
3470                  * "right" to be the right neighbor.
3471                  */
3472                 lptr = cptr;
3473                 left = block;
3474                 lbp = bp;
3475                 error = xfs_btree_read_buf_block(cur, &rptr, level,
3476                                                         0, &right, &rbp);
3477                 if (error)
3478                         goto error0;
3479
3480         /*
3481          * Otherwise, we can't fix the imbalance.
3482          * Just return.  This is probably a logic error, but it's not fatal.
3483          */
3484         } else {
3485                 error = xfs_btree_dec_cursor(cur, level, stat);
3486                 if (error)
3487                         goto error0;
3488                 return 0;
3489         }
3490
3491         rrecs = xfs_btree_get_numrecs(right);
3492         lrecs = xfs_btree_get_numrecs(left);
3493
3494         /*
3495          * We're now going to join "left" and "right" by moving all the stuff
3496          * in "right" to "left" and deleting "right".
3497          */
3498         XFS_BTREE_STATS_ADD(cur, moves, rrecs);
3499         if (level > 0) {
3500                 /* It's a non-leaf.  Move keys and pointers. */
3501                 union xfs_btree_key     *lkp;   /* left btree key */
3502                 union xfs_btree_ptr     *lpp;   /* left address pointer */
3503                 union xfs_btree_key     *rkp;   /* right btree key */
3504                 union xfs_btree_ptr     *rpp;   /* right address pointer */
3505
3506                 lkp = xfs_btree_key_addr(cur, lrecs + 1, left);
3507                 lpp = xfs_btree_ptr_addr(cur, lrecs + 1, left);
3508                 rkp = xfs_btree_key_addr(cur, 1, right);
3509                 rpp = xfs_btree_ptr_addr(cur, 1, right);
3510 #ifdef DEBUG
3511                 for (i = 1; i < rrecs; i++) {
3512                         error = xfs_btree_check_ptr(cur, rpp, i, level);
3513                         if (error)
3514                                 goto error0;
3515                 }
3516 #endif
3517                 xfs_btree_copy_keys(cur, lkp, rkp, rrecs);
3518                 xfs_btree_copy_ptrs(cur, lpp, rpp, rrecs);
3519
3520                 xfs_btree_log_keys(cur, lbp, lrecs + 1, lrecs + rrecs);
3521                 xfs_btree_log_ptrs(cur, lbp, lrecs + 1, lrecs + rrecs);
3522         } else {
3523                 /* It's a leaf.  Move records.  */
3524                 union xfs_btree_rec     *lrp;   /* left record pointer */
3525                 union xfs_btree_rec     *rrp;   /* right record pointer */
3526
3527                 lrp = xfs_btree_rec_addr(cur, lrecs + 1, left);
3528                 rrp = xfs_btree_rec_addr(cur, 1, right);
3529
3530                 xfs_btree_copy_recs(cur, lrp, rrp, rrecs);
3531                 xfs_btree_log_recs(cur, lbp, lrecs + 1, lrecs + rrecs);
3532         }
3533
3534         XFS_BTREE_STATS_INC(cur, join);
3535
3536         /*
3537          * Fix up the the number of records and right block pointer in the
3538          * surviving block, and log it.
3539          */
3540         xfs_btree_set_numrecs(left, lrecs + rrecs);
3541         xfs_btree_get_sibling(cur, right, &cptr, XFS_BB_RIGHTSIB),
3542         xfs_btree_set_sibling(cur, left, &cptr, XFS_BB_RIGHTSIB);
3543         xfs_btree_log_block(cur, lbp, XFS_BB_NUMRECS | XFS_BB_RIGHTSIB);
3544
3545         /* If there is a right sibling, point it to the remaining block. */
3546         xfs_btree_get_sibling(cur, left, &cptr, XFS_BB_RIGHTSIB);
3547         if (!xfs_btree_ptr_is_null(cur, &cptr)) {
3548                 error = xfs_btree_read_buf_block(cur, &cptr, level,
3549                                                         0, &rrblock, &rrbp);
3550                 if (error)
3551                         goto error0;
3552                 xfs_btree_set_sibling(cur, rrblock, &lptr, XFS_BB_LEFTSIB);
3553                 xfs_btree_log_block(cur, rrbp, XFS_BB_LEFTSIB);
3554         }
3555
3556         /* Free the deleted block. */
3557         error = cur->bc_ops->free_block(cur, rbp);
3558         if (error)
3559                 goto error0;
3560         XFS_BTREE_STATS_INC(cur, free);
3561
3562         /*
3563          * If we joined with the left neighbor, set the buffer in the
3564          * cursor to the left block, and fix up the index.
3565          */
3566         if (bp != lbp) {
3567                 cur->bc_bufs[level] = lbp;
3568                 cur->bc_ptrs[level] += lrecs;
3569                 cur->bc_ra[level] = 0;
3570         }
3571         /*
3572          * If we joined with the right neighbor and there's a level above
3573          * us, increment the cursor at that level.
3574          */
3575         else if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) ||
3576                    (level + 1 < cur->bc_nlevels)) {
3577                 error = xfs_btree_increment(cur, level + 1, &i);
3578                 if (error)
3579                         goto error0;
3580         }
3581
3582         /*
3583          * Readjust the ptr at this level if it's not a leaf, since it's
3584          * still pointing at the deletion point, which makes the cursor
3585          * inconsistent.  If this makes the ptr 0, the caller fixes it up.
3586          * We can't use decrement because it would change the next level up.
3587          */
3588         if (level > 0)
3589                 cur->bc_ptrs[level]--;
3590
3591         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
3592         /* Return value means the next level up has something to do. */
3593         *stat = 2;
3594         return 0;
3595
3596 error0:
3597         XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
3598         if (tcur)
3599                 xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
3600         return error;
3601 }
3602
3603 /*
3604  * Delete the record pointed to by cur.
3605  * The cursor refers to the place where the record was (could be inserted)
3606  * when the operation returns.
3607  */
3608 int                                     /* error */
3609 xfs_btree_delete(
3610         struct xfs_btree_cur    *cur,
3611         int                     *stat)  /* success/failure */
3612 {
3613         int                     error;  /* error return value */
3614         int                     level;
3615         int                     i;
3616
3617         XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
3618
3619         /*
3620          * Go up the tree, starting at leaf level.
3621          *
3622          * If 2 is returned then a join was done; go to the next level.
3623          * Otherwise we are done.
3624          */
3625         for (level = 0, i = 2; i == 2; level++) {
3626                 error = xfs_btree_delrec(cur, level, &i);
3627                 if (error)
3628                         goto error0;
3629         }
3630
3631         if (i == 0) {
3632                 for (level = 1; level < cur->bc_nlevels; level++) {
3633                         if (cur->bc_ptrs[level] == 0) {
3634                                 error = xfs_btree_decrement(cur, level, &i);
3635                                 if (error)
3636                                         goto error0;
3637                                 break;
3638                         }
3639                 }
3640         }
3641
3642         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
3643         *stat = i;
3644         return 0;
3645 error0:
3646         XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
3647         return error;
3648 }
3649
3650 /*
3651  * Get the data from the pointed-to record.
3652  */
3653 int                                     /* error */
3654 xfs_btree_get_rec(
3655         struct xfs_btree_cur    *cur,   /* btree cursor */
3656         union xfs_btree_rec     **recp, /* output: btree record */
3657         int                     *stat)  /* output: success/failure */
3658 {
3659         struct xfs_btree_block  *block; /* btree block */
3660         struct xfs_buf          *bp;    /* buffer pointer */
3661         int                     ptr;    /* record number */
3662 #ifdef DEBUG
3663         int                     error;  /* error return value */
3664 #endif
3665
3666         ptr = cur->bc_ptrs[0];
3667         block = xfs_btree_get_block(cur, 0, &bp);
3668
3669 #ifdef DEBUG
3670         error = xfs_btree_check_block(cur, block, 0, bp);
3671         if (error)
3672                 return error;
3673 #endif
3674
3675         /*
3676          * Off the right end or left end, return failure.
3677          */
3678         if (ptr > xfs_btree_get_numrecs(block) || ptr <= 0) {
3679                 *stat = 0;
3680                 return 0;
3681         }
3682
3683         /*
3684          * Point to the record and extract its data.
3685          */
3686         *recp = xfs_btree_rec_addr(cur, ptr, block);
3687         *stat = 1;
3688         return 0;
3689 }