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