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