fs/xfs/libxfs/xfs_btree.c

   1 // SPDX-License-Identifier: GPL-2.0
   2 /*
   3  * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc.
   4  * All Rights Reserved.
   5  */
   6 #include "xfs.h"
   7 #include "xfs_fs.h"
   8 #include "xfs_shared.h"
   9 #include "xfs_format.h"
  10 #include "xfs_log_format.h"
  11 #include "xfs_trans_resv.h"
  12 #include "xfs_bit.h"
  13 #include "xfs_mount.h"
  14 #include "xfs_inode.h"
  15 #include "xfs_trans.h"
  16 #include "xfs_buf_item.h"
  17 #include "xfs_btree.h"
  18 #include "xfs_errortag.h"
  19 #include "xfs_error.h"
  20 #include "xfs_trace.h"
  21 #include "xfs_alloc.h"
  22 #include "xfs_log.h"
  23 #include "xfs_btree_staging.h"
  24 #include "xfs_ag.h"
  25
  26 /*
  27  * Cursor allocation zone.
  28  */
  29 kmem_zone_t     *xfs_btree_cur_zone;
  30
  31 /*
  32  * Btree magic numbers.
  33  */
  34 static const uint32_t xfs_magics[2][XFS_BTNUM_MAX] = {
  35         { XFS_ABTB_MAGIC, XFS_ABTC_MAGIC, 0, XFS_BMAP_MAGIC, XFS_IBT_MAGIC,
  36           XFS_FIBT_MAGIC, 0 },
  37         { XFS_ABTB_CRC_MAGIC, XFS_ABTC_CRC_MAGIC, XFS_RMAP_CRC_MAGIC,
  38           XFS_BMAP_CRC_MAGIC, XFS_IBT_CRC_MAGIC, XFS_FIBT_CRC_MAGIC,
  39           XFS_REFC_CRC_MAGIC }
  40 };
  41
  42 uint32_t
  43 xfs_btree_magic(
  44         int                     crc,
  45         xfs_btnum_t             btnum)
  46 {
  47         uint32_t                magic = xfs_magics[crc][btnum];
  48
  49         /* Ensure we asked for crc for crc-only magics. */
  50         ASSERT(magic != 0);
  51         return magic;
  52 }
  53
  54 /*
  55  * These sibling pointer checks are optimised for null sibling pointers. This
  56  * happens a lot, and we don't need to byte swap at runtime if the sibling
  57  * pointer is NULL.
  58  *
  59  * These are explicitly marked at inline because the cost of calling them as
  60  * functions instead of inlining them is about 36 bytes extra code per call site
  61  * on x86-64. Yes, gcc-11 fails to inline them, and explicit inlining of these
  62  * two sibling check functions reduces the compiled code size by over 300
  63  * bytes.
  64  */
  65 static inline xfs_failaddr_t
  66 xfs_btree_check_lblock_siblings(
  67         struct xfs_mount        *mp,
  68         struct xfs_btree_cur    *cur,
  69         int                     level,
  70         xfs_fsblock_t           fsb,
  71         __be64                  dsibling)
  72 {
  73         xfs_fsblock_t           sibling;
  74
  75         if (dsibling == cpu_to_be64(NULLFSBLOCK))
  76                 return NULL;
  77
  78         sibling = be64_to_cpu(dsibling);
  79         if (sibling == fsb)
  80                 return __this_address;
  81         if (level >= 0) {
  82                 if (!xfs_btree_check_lptr(cur, sibling, level + 1))
  83                         return __this_address;
  84         } else {
  85                 if (!xfs_verify_fsbno(mp, sibling))
  86                         return __this_address;
  87         }
  88
  89         return NULL;
  90 }
  91
  92 static inline xfs_failaddr_t
  93 xfs_btree_check_sblock_siblings(
  94         struct xfs_mount        *mp,
  95         struct xfs_btree_cur    *cur,
  96         int                     level,
  97         xfs_agnumber_t          agno,
  98         xfs_agblock_t           agbno,
  99         __be32                  dsibling)
 100 {
 101         xfs_agblock_t           sibling;
 102
 103         if (dsibling == cpu_to_be32(NULLAGBLOCK))
 104                 return NULL;
 105
 106         sibling = be32_to_cpu(dsibling);
 107         if (sibling == agbno)
 108                 return __this_address;
 109         if (level >= 0) {
 110                 if (!xfs_btree_check_sptr(cur, sibling, level + 1))
 111                         return __this_address;
 112         } else {
 113                 if (!xfs_verify_agbno(mp, agno, sibling))
 114                         return __this_address;
 115         }
 116         return NULL;
 117 }
 118
 119 /*
 120  * Check a long btree block header.  Return the address of the failing check,
 121  * or NULL if everything is ok.
 122  */
 123 xfs_failaddr_t
 124 __xfs_btree_check_lblock(
 125         struct xfs_btree_cur    *cur,
 126         struct xfs_btree_block  *block,
 127         int                     level,
 128         struct xfs_buf          *bp)
 129 {
 130         struct xfs_mount        *mp = cur->bc_mp;
 131         xfs_btnum_t             btnum = cur->bc_btnum;
 132         int                     crc = xfs_has_crc(mp);
 133         xfs_failaddr_t          fa;
 134         xfs_fsblock_t           fsb = NULLFSBLOCK;
 135
 136         if (crc) {
 137                 if (!uuid_equal(&block->bb_u.l.bb_uuid, &mp->m_sb.sb_meta_uuid))
 138                         return __this_address;
 139                 if (block->bb_u.l.bb_blkno !=
 140                     cpu_to_be64(bp ? xfs_buf_daddr(bp) : XFS_BUF_DADDR_NULL))
 141                         return __this_address;
 142                 if (block->bb_u.l.bb_pad != cpu_to_be32(0))
 143                         return __this_address;
 144         }
 145
 146         if (be32_to_cpu(block->bb_magic) != xfs_btree_magic(crc, btnum))
 147                 return __this_address;
 148         if (be16_to_cpu(block->bb_level) != level)
 149                 return __this_address;
 150         if (be16_to_cpu(block->bb_numrecs) >
 151             cur->bc_ops->get_maxrecs(cur, level))
 152                 return __this_address;
 153
 154         if (bp)
 155                 fsb = XFS_DADDR_TO_FSB(mp, xfs_buf_daddr(bp));
 156
 157         fa = xfs_btree_check_lblock_siblings(mp, cur, level, fsb,
 158                         block->bb_u.l.bb_leftsib);
 159         if (!fa)
 160                 fa = xfs_btree_check_lblock_siblings(mp, cur, level, fsb,
 161                                 block->bb_u.l.bb_rightsib);
 162         return fa;
 163 }
 164
 165 /* Check a long btree block header. */
 166 static int
 167 xfs_btree_check_lblock(
 168         struct xfs_btree_cur    *cur,
 169         struct xfs_btree_block  *block,
 170         int                     level,
 171         struct xfs_buf          *bp)
 172 {
 173         struct xfs_mount        *mp = cur->bc_mp;
 174         xfs_failaddr_t          fa;
 175
 176         fa = __xfs_btree_check_lblock(cur, block, level, bp);
 177         if (XFS_IS_CORRUPT(mp, fa != NULL) ||
 178             XFS_TEST_ERROR(false, mp, XFS_ERRTAG_BTREE_CHECK_LBLOCK)) {
 179                 if (bp)
 180                         trace_xfs_btree_corrupt(bp, _RET_IP_);
 181                 return -EFSCORRUPTED;
 182         }
 183         return 0;
 184 }
 185
 186 /*
 187  * Check a short btree block header.  Return the address of the failing check,
 188  * or NULL if everything is ok.
 189  */
 190 xfs_failaddr_t
 191 __xfs_btree_check_sblock(
 192         struct xfs_btree_cur    *cur,
 193         struct xfs_btree_block  *block,
 194         int                     level,
 195         struct xfs_buf          *bp)
 196 {
 197         struct xfs_mount        *mp = cur->bc_mp;
 198         xfs_btnum_t             btnum = cur->bc_btnum;
 199         int                     crc = xfs_has_crc(mp);
 200         xfs_failaddr_t          fa;
 201         xfs_agblock_t           agbno = NULLAGBLOCK;
 202         xfs_agnumber_t          agno = NULLAGNUMBER;
 203
 204         if (crc) {
 205                 if (!uuid_equal(&block->bb_u.s.bb_uuid, &mp->m_sb.sb_meta_uuid))
 206                         return __this_address;
 207                 if (block->bb_u.s.bb_blkno !=
 208                     cpu_to_be64(bp ? xfs_buf_daddr(bp) : XFS_BUF_DADDR_NULL))
 209                         return __this_address;
 210         }
 211
 212         if (be32_to_cpu(block->bb_magic) != xfs_btree_magic(crc, btnum))
 213                 return __this_address;
 214         if (be16_to_cpu(block->bb_level) != level)
 215                 return __this_address;
 216         if (be16_to_cpu(block->bb_numrecs) >
 217             cur->bc_ops->get_maxrecs(cur, level))
 218                 return __this_address;
 219
 220         if (bp) {
 221                 agbno = xfs_daddr_to_agbno(mp, xfs_buf_daddr(bp));
 222                 agno = xfs_daddr_to_agno(mp, xfs_buf_daddr(bp));
 223         }
 224
 225         fa = xfs_btree_check_sblock_siblings(mp, cur, level, agno, agbno,
 226                         block->bb_u.s.bb_leftsib);
 227         if (!fa)
 228                 fa = xfs_btree_check_sblock_siblings(mp, cur, level, agno,
 229                                  agbno, block->bb_u.s.bb_rightsib);
 230         return fa;
 231 }
 232
 233 /* Check a short btree block header. */
 234 STATIC int
 235 xfs_btree_check_sblock(
 236         struct xfs_btree_cur    *cur,
 237         struct xfs_btree_block  *block,
 238         int                     level,
 239         struct xfs_buf          *bp)
 240 {
 241         struct xfs_mount        *mp = cur->bc_mp;
 242         xfs_failaddr_t          fa;
 243
 244         fa = __xfs_btree_check_sblock(cur, block, level, bp);
 245         if (XFS_IS_CORRUPT(mp, fa != NULL) ||
 246             XFS_TEST_ERROR(false, mp, XFS_ERRTAG_BTREE_CHECK_SBLOCK)) {
 247                 if (bp)
 248                         trace_xfs_btree_corrupt(bp, _RET_IP_);
 249                 return -EFSCORRUPTED;
 250         }
 251         return 0;
 252 }
 253
 254 /*
 255  * Debug routine: check that block header is ok.
 256  */
 257 int
 258 xfs_btree_check_block(
 259         struct xfs_btree_cur    *cur,   /* btree cursor */
 260         struct xfs_btree_block  *block, /* generic btree block pointer */
 261         int                     level,  /* level of the btree block */
 262         struct xfs_buf          *bp)    /* buffer containing block, if any */
 263 {
 264         if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
 265                 return xfs_btree_check_lblock(cur, block, level, bp);
 266         else
 267                 return xfs_btree_check_sblock(cur, block, level, bp);
 268 }
 269
 270 /* Check that this long pointer is valid and points within the fs. */
 271 bool
 272 xfs_btree_check_lptr(
 273         struct xfs_btree_cur    *cur,
 274         xfs_fsblock_t           fsbno,
 275         int                     level)
 276 {
 277         if (level <= 0)
 278                 return false;
 279         return xfs_verify_fsbno(cur->bc_mp, fsbno);
 280 }
 281
 282 /* Check that this short pointer is valid and points within the AG. */
 283 bool
 284 xfs_btree_check_sptr(
 285         struct xfs_btree_cur    *cur,
 286         xfs_agblock_t           agbno,
 287         int                     level)
 288 {
 289         if (level <= 0)
 290                 return false;
 291         return xfs_verify_agbno(cur->bc_mp, cur->bc_ag.pag->pag_agno, agbno);
 292 }
 293
 294 /*
 295  * Check that a given (indexed) btree pointer at a certain level of a
 296  * btree is valid and doesn't point past where it should.
 297  */
 298 static int
 299 xfs_btree_check_ptr(
 300         struct xfs_btree_cur            *cur,
 301         const union xfs_btree_ptr       *ptr,
 302         int                             index,
 303         int                             level)
 304 {
 305         if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
 306                 if (xfs_btree_check_lptr(cur, be64_to_cpu((&ptr->l)[index]),
 307                                 level))
 308                         return 0;
 309                 xfs_err(cur->bc_mp,
 310 "Inode %llu fork %d: Corrupt btree %d pointer at level %d index %d.",
 311                                 cur->bc_ino.ip->i_ino,
 312                                 cur->bc_ino.whichfork, cur->bc_btnum,
 313                                 level, index);
 314         } else {
 315                 if (xfs_btree_check_sptr(cur, be32_to_cpu((&ptr->s)[index]),
 316                                 level))
 317                         return 0;
 318                 xfs_err(cur->bc_mp,
 319 "AG %u: Corrupt btree %d pointer at level %d index %d.",
 320                                 cur->bc_ag.pag->pag_agno, cur->bc_btnum,
 321                                 level, index);
 322         }
 323
 324         return -EFSCORRUPTED;
 325 }
 326
 327 #ifdef DEBUG
 328 # define xfs_btree_debug_check_ptr      xfs_btree_check_ptr
 329 #else
 330 # define xfs_btree_debug_check_ptr(...) (0)
 331 #endif
 332
 333 /*
 334  * Calculate CRC on the whole btree block and stuff it into the
 335  * long-form btree header.
 336  *
 337  * Prior to calculting the CRC, pull the LSN out of the buffer log item and put
 338  * it into the buffer so recovery knows what the last modification was that made
 339  * it to disk.
 340  */
 341 void
 342 xfs_btree_lblock_calc_crc(
 343         struct xfs_buf          *bp)
 344 {
 345         struct xfs_btree_block  *block = XFS_BUF_TO_BLOCK(bp);
 346         struct xfs_buf_log_item *bip = bp->b_log_item;
 347
 348         if (!xfs_has_crc(bp->b_mount))
 349                 return;
 350         if (bip)
 351                 block->bb_u.l.bb_lsn = cpu_to_be64(bip->bli_item.li_lsn);
 352         xfs_buf_update_cksum(bp, XFS_BTREE_LBLOCK_CRC_OFF);
 353 }
 354
 355 bool
 356 xfs_btree_lblock_verify_crc(
 357         struct xfs_buf          *bp)
 358 {
 359         struct xfs_btree_block  *block = XFS_BUF_TO_BLOCK(bp);
 360         struct xfs_mount        *mp = bp->b_mount;
 361
 362         if (xfs_has_crc(mp)) {
 363                 if (!xfs_log_check_lsn(mp, be64_to_cpu(block->bb_u.l.bb_lsn)))
 364                         return false;
 365                 return xfs_buf_verify_cksum(bp, XFS_BTREE_LBLOCK_CRC_OFF);
 366         }
 367
 368         return true;
 369 }
 370
 371 /*
 372  * Calculate CRC on the whole btree block and stuff it into the
 373  * short-form btree header.
 374  *
 375  * Prior to calculting the CRC, pull the LSN out of the buffer log item and put
 376  * it into the buffer so recovery knows what the last modification was that made
 377  * it to disk.
 378  */
 379 void
 380 xfs_btree_sblock_calc_crc(
 381         struct xfs_buf          *bp)
 382 {
 383         struct xfs_btree_block  *block = XFS_BUF_TO_BLOCK(bp);
 384         struct xfs_buf_log_item *bip = bp->b_log_item;
 385
 386         if (!xfs_has_crc(bp->b_mount))
 387                 return;
 388         if (bip)
 389                 block->bb_u.s.bb_lsn = cpu_to_be64(bip->bli_item.li_lsn);
 390         xfs_buf_update_cksum(bp, XFS_BTREE_SBLOCK_CRC_OFF);
 391 }
 392
 393 bool
 394 xfs_btree_sblock_verify_crc(
 395         struct xfs_buf          *bp)
 396 {
 397         struct xfs_btree_block  *block = XFS_BUF_TO_BLOCK(bp);
 398         struct xfs_mount        *mp = bp->b_mount;
 399
 400         if (xfs_has_crc(mp)) {
 401                 if (!xfs_log_check_lsn(mp, be64_to_cpu(block->bb_u.s.bb_lsn)))
 402                         return false;
 403                 return xfs_buf_verify_cksum(bp, XFS_BTREE_SBLOCK_CRC_OFF);
 404         }
 405
 406         return true;
 407 }
 408
 409 static int
 410 xfs_btree_free_block(
 411         struct xfs_btree_cur    *cur,
 412         struct xfs_buf          *bp)
 413 {
 414         int                     error;
 415
 416         error = cur->bc_ops->free_block(cur, bp);
 417         if (!error) {
 418                 xfs_trans_binval(cur->bc_tp, bp);
 419                 XFS_BTREE_STATS_INC(cur, free);
 420         }
 421         return error;
 422 }
 423
 424 /*
 425  * Delete the btree cursor.
 426  */
 427 void
 428 xfs_btree_del_cursor(
 429         struct xfs_btree_cur    *cur,           /* btree cursor */
 430         int                     error)          /* del because of error */
 431 {
 432         int                     i;              /* btree level */
 433
 434         /*
 435          * Clear the buffer pointers and release the buffers. If we're doing
 436          * this because of an error, inspect all of the entries in the bc_bufs
 437          * array for buffers to be unlocked. This is because some of the btree
 438          * code works from level n down to 0, and if we get an error along the
 439          * way we won't have initialized all the entries down to 0.
 440          */
 441         for (i = 0; i < cur->bc_nlevels; i++) {
 442                 if (cur->bc_bufs[i])
 443                         xfs_trans_brelse(cur->bc_tp, cur->bc_bufs[i]);
 444                 else if (!error)
 445                         break;
 446         }
 447
 448         /*
 449          * If we are doing a BMBT update, the number of unaccounted blocks
 450          * allocated during this cursor life time should be zero. If it's not
 451          * zero, then we should be shut down or on our way to shutdown due to
 452          * cancelling a dirty transaction on error.
 453          */
 454         ASSERT(cur->bc_btnum != XFS_BTNUM_BMAP || cur->bc_ino.allocated == 0 ||
 455                xfs_is_shutdown(cur->bc_mp) || error != 0);
 456         if (unlikely(cur->bc_flags & XFS_BTREE_STAGING))
 457                 kmem_free(cur->bc_ops);
 458         if (!(cur->bc_flags & XFS_BTREE_LONG_PTRS) && cur->bc_ag.pag)
 459                 xfs_perag_put(cur->bc_ag.pag);
 460         kmem_cache_free(xfs_btree_cur_zone, cur);
 461 }
 462
 463 /*
 464  * Duplicate the btree cursor.
 465  * Allocate a new one, copy the record, re-get the buffers.
 466  */
 467 int                                     /* error */
 468 xfs_btree_dup_cursor(
 469         xfs_btree_cur_t *cur,           /* input cursor */
 470         xfs_btree_cur_t **ncur)         /* output cursor */
 471 {
 472         struct xfs_buf  *bp;            /* btree block's buffer pointer */
 473         int             error;          /* error return value */
 474         int             i;              /* level number of btree block */
 475         xfs_mount_t     *mp;            /* mount structure for filesystem */
 476         xfs_btree_cur_t *new;           /* new cursor value */
 477         xfs_trans_t     *tp;            /* transaction pointer, can be NULL */
 478
 479         tp = cur->bc_tp;
 480         mp = cur->bc_mp;
 481
 482         /*
 483          * Allocate a new cursor like the old one.
 484          */
 485         new = cur->bc_ops->dup_cursor(cur);
 486
 487         /*
 488          * Copy the record currently in the cursor.
 489          */
 490         new->bc_rec = cur->bc_rec;
 491
 492         /*
 493          * For each level current, re-get the buffer and copy the ptr value.
 494          */
 495         for (i = 0; i < new->bc_nlevels; i++) {
 496                 new->bc_ptrs[i] = cur->bc_ptrs[i];
 497                 new->bc_ra[i] = cur->bc_ra[i];
 498                 bp = cur->bc_bufs[i];
 499                 if (bp) {
 500                         error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp,
 501                                                    xfs_buf_daddr(bp), mp->m_bsize,
 502                                                    0, &bp,
 503                                                    cur->bc_ops->buf_ops);
 504                         if (error) {
 505                                 xfs_btree_del_cursor(new, error);
 506                                 *ncur = NULL;
 507                                 return error;
 508                         }
 509                 }
 510                 new->bc_bufs[i] = bp;
 511         }
 512         *ncur = new;
 513         return 0;
 514 }
 515
 516 /*
 517  * XFS btree block layout and addressing:
 518  *
 519  * There are two types of blocks in the btree: leaf and non-leaf blocks.
 520  *
 521  * The leaf record start with a header then followed by records containing
 522  * the values.  A non-leaf block also starts with the same header, and
 523  * then first contains lookup keys followed by an equal number of pointers
 524  * to the btree blocks at the previous level.
 525  *
 526  *              +--------+-------+-------+-------+-------+-------+-------+
 527  * Leaf:        | header | rec 1 | rec 2 | rec 3 | rec 4 | rec 5 | rec N |
 528  *              +--------+-------+-------+-------+-------+-------+-------+
 529  *
 530  *              +--------+-------+-------+-------+-------+-------+-------+
 531  * Non-Leaf:    | header | key 1 | key 2 | key N | ptr 1 | ptr 2 | ptr N |
 532  *              +--------+-------+-------+-------+-------+-------+-------+
 533  *
 534  * The header is called struct xfs_btree_block for reasons better left unknown
 535  * and comes in different versions for short (32bit) and long (64bit) block
 536  * pointers.  The record and key structures are defined by the btree instances
 537  * and opaque to the btree core.  The block pointers are simple disk endian
 538  * integers, available in a short (32bit) and long (64bit) variant.
 539  *
 540  * The helpers below calculate the offset of a given record, key or pointer
 541  * into a btree block (xfs_btree_*_offset) or return a pointer to the given
 542  * record, key or pointer (xfs_btree_*_addr).  Note that all addressing
 543  * inside the btree block is done using indices starting at one, not zero!
 544  *
 545  * If XFS_BTREE_OVERLAPPING is set, then this btree supports keys containing
 546  * overlapping intervals.  In such a tree, records are still sorted lowest to
 547  * highest and indexed by the smallest key value that refers to the record.
 548  * However, nodes are different: each pointer has two associated keys -- one
 549  * indexing the lowest key available in the block(s) below (the same behavior
 550  * as the key in a regular btree) and another indexing the highest key
 551  * available in the block(s) below.  Because records are /not/ sorted by the
 552  * highest key, all leaf block updates require us to compute the highest key
 553  * that matches any record in the leaf and to recursively update the high keys
 554  * in the nodes going further up in the tree, if necessary.  Nodes look like
 555  * this:
 556  *
 557  *              +--------+-----+-----+-----+-----+-----+-------+-------+-----+
 558  * Non-Leaf:    | header | lo1 | hi1 | lo2 | hi2 | ... | ptr 1 | ptr 2 | ... |
 559  *              +--------+-----+-----+-----+-----+-----+-------+-------+-----+
 560  *
 561  * To perform an interval query on an overlapped tree, perform the usual
 562  * depth-first search and use the low and high keys to decide if we can skip
 563  * that particular node.  If a leaf node is reached, return the records that
 564  * intersect the interval.  Note that an interval query may return numerous
 565  * entries.  For a non-overlapped tree, simply search for the record associated
 566  * with the lowest key and iterate forward until a non-matching record is
 567  * found.  Section 14.3 ("Interval Trees") of _Introduction to Algorithms_ by
 568  * Cormen, Leiserson, Rivest, and Stein (2nd or 3rd ed. only) discuss this in
 569  * more detail.
 570  *
 571  * Why do we care about overlapping intervals?  Let's say you have a bunch of
 572  * reverse mapping records on a reflink filesystem:
 573  *
 574  * 1: +- file A startblock B offset C length D -----------+
 575  * 2:      +- file E startblock F offset G length H --------------+
 576  * 3:      +- file I startblock F offset J length K --+
 577  * 4:                                                        +- file L... --+
 578  *
 579  * Now say we want to map block (B+D) into file A at offset (C+D).  Ideally,
 580  * we'd simply increment the length of record 1.  But how do we find the record
 581  * that ends at (B+D-1) (i.e. record 1)?  A LE lookup of (B+D-1) would return
 582  * record 3 because the keys are ordered first by startblock.  An interval
 583  * query would return records 1 and 2 because they both overlap (B+D-1), and
 584  * from that we can pick out record 1 as the appropriate left neighbor.
 585  *
 586  * In the non-overlapped case you can do a LE lookup and decrement the cursor
 587  * because a record's interval must end before the next record.
 588  */
 589
 590 /*
 591  * Return size of the btree block header for this btree instance.
 592  */
 593 static inline size_t xfs_btree_block_len(struct xfs_btree_cur *cur)
 594 {
 595         if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
 596                 if (cur->bc_flags & XFS_BTREE_CRC_BLOCKS)
 597                         return XFS_BTREE_LBLOCK_CRC_LEN;
 598                 return XFS_BTREE_LBLOCK_LEN;
 599         }
 600         if (cur->bc_flags & XFS_BTREE_CRC_BLOCKS)
 601                 return XFS_BTREE_SBLOCK_CRC_LEN;
 602         return XFS_BTREE_SBLOCK_LEN;
 603 }
 604
 605 /*
 606  * Return size of btree block pointers for this btree instance.
 607  */
 608 static inline size_t xfs_btree_ptr_len(struct xfs_btree_cur *cur)
 609 {
 610         return (cur->bc_flags & XFS_BTREE_LONG_PTRS) ?
 611                 sizeof(__be64) : sizeof(__be32);
 612 }
 613
 614 /*
 615  * Calculate offset of the n-th record in a btree block.
 616  */
 617 STATIC size_t
 618 xfs_btree_rec_offset(
 619         struct xfs_btree_cur    *cur,
 620         int                     n)
 621 {
 622         return xfs_btree_block_len(cur) +
 623                 (n - 1) * cur->bc_ops->rec_len;
 624 }
 625
 626 /*
 627  * Calculate offset of the n-th key in a btree block.
 628  */
 629 STATIC size_t
 630 xfs_btree_key_offset(
 631         struct xfs_btree_cur    *cur,
 632         int                     n)
 633 {
 634         return xfs_btree_block_len(cur) +
 635                 (n - 1) * cur->bc_ops->key_len;
 636 }
 637
 638 /*
 639  * Calculate offset of the n-th high key in a btree block.
 640  */
 641 STATIC size_t
 642 xfs_btree_high_key_offset(
 643         struct xfs_btree_cur    *cur,
 644         int                     n)
 645 {
 646         return xfs_btree_block_len(cur) +
 647                 (n - 1) * cur->bc_ops->key_len + (cur->bc_ops->key_len / 2);
 648 }
 649
 650 /*
 651  * Calculate offset of the n-th block pointer in a btree block.
 652  */
 653 STATIC size_t
 654 xfs_btree_ptr_offset(
 655         struct xfs_btree_cur    *cur,
 656         int                     n,
 657         int                     level)
 658 {
 659         return xfs_btree_block_len(cur) +
 660                 cur->bc_ops->get_maxrecs(cur, level) * cur->bc_ops->key_len +
 661                 (n - 1) * xfs_btree_ptr_len(cur);
 662 }
 663
 664 /*
 665  * Return a pointer to the n-th record in the btree block.
 666  */
 667 union xfs_btree_rec *
 668 xfs_btree_rec_addr(
 669         struct xfs_btree_cur    *cur,
 670         int                     n,
 671         struct xfs_btree_block  *block)
 672 {
 673         return (union xfs_btree_rec *)
 674                 ((char *)block + xfs_btree_rec_offset(cur, n));
 675 }
 676
 677 /*
 678  * Return a pointer to the n-th key in the btree block.
 679  */
 680 union xfs_btree_key *
 681 xfs_btree_key_addr(
 682         struct xfs_btree_cur    *cur,
 683         int                     n,
 684         struct xfs_btree_block  *block)
 685 {
 686         return (union xfs_btree_key *)
 687                 ((char *)block + xfs_btree_key_offset(cur, n));
 688 }
 689
 690 /*
 691  * Return a pointer to the n-th high key in the btree block.
 692  */
 693 union xfs_btree_key *
 694 xfs_btree_high_key_addr(
 695         struct xfs_btree_cur    *cur,
 696         int                     n,
 697         struct xfs_btree_block  *block)
 698 {
 699         return (union xfs_btree_key *)
 700                 ((char *)block + xfs_btree_high_key_offset(cur, n));
 701 }
 702
 703 /*
 704  * Return a pointer to the n-th block pointer in the btree block.
 705  */
 706 union xfs_btree_ptr *
 707 xfs_btree_ptr_addr(
 708         struct xfs_btree_cur    *cur,
 709         int                     n,
 710         struct xfs_btree_block  *block)
 711 {
 712         int                     level = xfs_btree_get_level(block);
 713
 714         ASSERT(block->bb_level != 0);
 715
 716         return (union xfs_btree_ptr *)
 717                 ((char *)block + xfs_btree_ptr_offset(cur, n, level));
 718 }
 719
 720 struct xfs_ifork *
 721 xfs_btree_ifork_ptr(
 722         struct xfs_btree_cur    *cur)
 723 {
 724         ASSERT(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE);
 725
 726         if (cur->bc_flags & XFS_BTREE_STAGING)
 727                 return cur->bc_ino.ifake->if_fork;
 728         return XFS_IFORK_PTR(cur->bc_ino.ip, cur->bc_ino.whichfork);
 729 }
 730
 731 /*
 732  * Get the root block which is stored in the inode.
 733  *
 734  * For now this btree implementation assumes the btree root is always
 735  * stored in the if_broot field of an inode fork.
 736  */
 737 STATIC struct xfs_btree_block *
 738 xfs_btree_get_iroot(
 739         struct xfs_btree_cur    *cur)
 740 {
 741         struct xfs_ifork        *ifp = xfs_btree_ifork_ptr(cur);
 742
 743         return (struct xfs_btree_block *)ifp->if_broot;
 744 }
 745
 746 /*
 747  * Retrieve the block pointer from the cursor at the given level.
 748  * This may be an inode btree root or from a buffer.
 749  */
 750 struct xfs_btree_block *                /* generic btree block pointer */
 751 xfs_btree_get_block(
 752         struct xfs_btree_cur    *cur,   /* btree cursor */
 753         int                     level,  /* level in btree */
 754         struct xfs_buf          **bpp)  /* buffer containing the block */
 755 {
 756         if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
 757             (level == cur->bc_nlevels - 1)) {
 758                 *bpp = NULL;
 759                 return xfs_btree_get_iroot(cur);
 760         }
 761
 762         *bpp = cur->bc_bufs[level];
 763         return XFS_BUF_TO_BLOCK(*bpp);
 764 }
 765
 766 /*
 767  * Change the cursor to point to the first record at the given level.
 768  * Other levels are unaffected.
 769  */
 770 STATIC int                              /* success=1, failure=0 */
 771 xfs_btree_firstrec(
 772         xfs_btree_cur_t         *cur,   /* btree cursor */
 773         int                     level)  /* level to change */
 774 {
 775         struct xfs_btree_block  *block; /* generic btree block pointer */
 776         struct xfs_buf          *bp;    /* buffer containing block */
 777
 778         /*
 779          * Get the block pointer for this level.
 780          */
 781         block = xfs_btree_get_block(cur, level, &bp);
 782         if (xfs_btree_check_block(cur, block, level, bp))
 783                 return 0;
 784         /*
 785          * It's empty, there is no such record.
 786          */
 787         if (!block->bb_numrecs)
 788                 return 0;
 789         /*
 790          * Set the ptr value to 1, that's the first record/key.
 791          */
 792         cur->bc_ptrs[level] = 1;
 793         return 1;
 794 }
 795
 796 /*
 797  * Change the cursor to point to the last record in the current block
 798  * at the given level.  Other levels are unaffected.
 799  */
 800 STATIC int                              /* success=1, failure=0 */
 801 xfs_btree_lastrec(
 802         xfs_btree_cur_t         *cur,   /* btree cursor */
 803         int                     level)  /* level to change */
 804 {
 805         struct xfs_btree_block  *block; /* generic btree block pointer */
 806         struct xfs_buf          *bp;    /* buffer containing block */
 807
 808         /*
 809          * Get the block pointer for this level.
 810          */
 811         block = xfs_btree_get_block(cur, level, &bp);
 812         if (xfs_btree_check_block(cur, block, level, bp))
 813                 return 0;
 814         /*
 815          * It's empty, there is no such record.
 816          */
 817         if (!block->bb_numrecs)
 818                 return 0;
 819         /*
 820          * Set the ptr value to numrecs, that's the last record/key.
 821          */
 822         cur->bc_ptrs[level] = be16_to_cpu(block->bb_numrecs);
 823         return 1;
 824 }
 825
 826 /*
 827  * Compute first and last byte offsets for the fields given.
 828  * Interprets the offsets table, which contains struct field offsets.
 829  */
 830 void
 831 xfs_btree_offsets(
 832         int64_t         fields,         /* bitmask of fields */
 833         const short     *offsets,       /* table of field offsets */
 834         int             nbits,          /* number of bits to inspect */
 835         int             *first,         /* output: first byte offset */
 836         int             *last)          /* output: last byte offset */
 837 {
 838         int             i;              /* current bit number */
 839         int64_t         imask;          /* mask for current bit number */
 840
 841         ASSERT(fields != 0);
 842         /*
 843          * Find the lowest bit, so the first byte offset.
 844          */
 845         for (i = 0, imask = 1LL; ; i++, imask <<= 1) {
 846                 if (imask & fields) {
 847                         *first = offsets[i];
 848                         break;
 849                 }
 850         }
 851         /*
 852          * Find the highest bit, so the last byte offset.
 853          */
 854         for (i = nbits - 1, imask = 1LL << i; ; i--, imask >>= 1) {
 855                 if (imask & fields) {
 856                         *last = offsets[i + 1] - 1;
 857                         break;
 858                 }
 859         }
 860 }
 861
 862 /*
 863  * Get a buffer for the block, return it read in.
 864  * Long-form addressing.
 865  */
 866 int
 867 xfs_btree_read_bufl(
 868         struct xfs_mount        *mp,            /* file system mount point */
 869         struct xfs_trans        *tp,            /* transaction pointer */
 870         xfs_fsblock_t           fsbno,          /* file system block number */
 871         struct xfs_buf          **bpp,          /* buffer for fsbno */
 872         int                     refval,         /* ref count value for buffer */
 873         const struct xfs_buf_ops *ops)
 874 {
 875         struct xfs_buf          *bp;            /* return value */
 876         xfs_daddr_t             d;              /* real disk block address */
 877         int                     error;
 878
 879         if (!xfs_verify_fsbno(mp, fsbno))
 880                 return -EFSCORRUPTED;
 881         d = XFS_FSB_TO_DADDR(mp, fsbno);
 882         error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp, d,
 883                                    mp->m_bsize, 0, &bp, ops);
 884         if (error)
 885                 return error;
 886         if (bp)
 887                 xfs_buf_set_ref(bp, refval);
 888         *bpp = bp;
 889         return 0;
 890 }
 891
 892 /*
 893  * Read-ahead the block, don't wait for it, don't return a buffer.
 894  * Long-form addressing.
 895  */
 896 /* ARGSUSED */
 897 void
 898 xfs_btree_reada_bufl(
 899         struct xfs_mount        *mp,            /* file system mount point */
 900         xfs_fsblock_t           fsbno,          /* file system block number */
 901         xfs_extlen_t            count,          /* count of filesystem blocks */
 902         const struct xfs_buf_ops *ops)
 903 {
 904         xfs_daddr_t             d;
 905
 906         ASSERT(fsbno != NULLFSBLOCK);
 907         d = XFS_FSB_TO_DADDR(mp, fsbno);
 908         xfs_buf_readahead(mp->m_ddev_targp, d, mp->m_bsize * count, ops);
 909 }
 910
 911 /*
 912  * Read-ahead the block, don't wait for it, don't return a buffer.
 913  * Short-form addressing.
 914  */
 915 /* ARGSUSED */
 916 void
 917 xfs_btree_reada_bufs(
 918         struct xfs_mount        *mp,            /* file system mount point */
 919         xfs_agnumber_t          agno,           /* allocation group number */
 920         xfs_agblock_t           agbno,          /* allocation group block number */
 921         xfs_extlen_t            count,          /* count of filesystem blocks */
 922         const struct xfs_buf_ops *ops)
 923 {
 924         xfs_daddr_t             d;
 925
 926         ASSERT(agno != NULLAGNUMBER);
 927         ASSERT(agbno != NULLAGBLOCK);
 928         d = XFS_AGB_TO_DADDR(mp, agno, agbno);
 929         xfs_buf_readahead(mp->m_ddev_targp, d, mp->m_bsize * count, ops);
 930 }
 931
 932 STATIC int
 933 xfs_btree_readahead_lblock(
 934         struct xfs_btree_cur    *cur,
 935         int                     lr,
 936         struct xfs_btree_block  *block)
 937 {
 938         int                     rval = 0;
 939         xfs_fsblock_t           left = be64_to_cpu(block->bb_u.l.bb_leftsib);
 940         xfs_fsblock_t           right = be64_to_cpu(block->bb_u.l.bb_rightsib);
 941
 942         if ((lr & XFS_BTCUR_LEFTRA) && left != NULLFSBLOCK) {
 943                 xfs_btree_reada_bufl(cur->bc_mp, left, 1,
 944                                      cur->bc_ops->buf_ops);
 945                 rval++;
 946         }
 947
 948         if ((lr & XFS_BTCUR_RIGHTRA) && right != NULLFSBLOCK) {
 949                 xfs_btree_reada_bufl(cur->bc_mp, right, 1,
 950                                      cur->bc_ops->buf_ops);
 951                 rval++;
 952         }
 953
 954         return rval;
 955 }
 956
 957 STATIC int
 958 xfs_btree_readahead_sblock(
 959         struct xfs_btree_cur    *cur,
 960         int                     lr,
 961         struct xfs_btree_block *block)
 962 {
 963         int                     rval = 0;
 964         xfs_agblock_t           left = be32_to_cpu(block->bb_u.s.bb_leftsib);
 965         xfs_agblock_t           right = be32_to_cpu(block->bb_u.s.bb_rightsib);
 966
 967
 968         if ((lr & XFS_BTCUR_LEFTRA) && left != NULLAGBLOCK) {
 969                 xfs_btree_reada_bufs(cur->bc_mp, cur->bc_ag.pag->pag_agno,
 970                                      left, 1, cur->bc_ops->buf_ops);
 971                 rval++;
 972         }
 973
 974         if ((lr & XFS_BTCUR_RIGHTRA) && right != NULLAGBLOCK) {
 975                 xfs_btree_reada_bufs(cur->bc_mp, cur->bc_ag.pag->pag_agno,
 976                                      right, 1, cur->bc_ops->buf_ops);
 977                 rval++;
 978         }
 979
 980         return rval;
 981 }
 982
 983 /*
 984  * Read-ahead btree blocks, at the given level.
 985  * Bits in lr are set from XFS_BTCUR_{LEFT,RIGHT}RA.
 986  */
 987 STATIC int
 988 xfs_btree_readahead(
 989         struct xfs_btree_cur    *cur,           /* btree cursor */
 990         int                     lev,            /* level in btree */
 991         int                     lr)             /* left/right bits */
 992 {
 993         struct xfs_btree_block  *block;
 994
 995         /*
 996          * No readahead needed if we are at the root level and the
 997          * btree root is stored in the inode.
 998          */
 999         if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
1000             (lev == cur->bc_nlevels - 1))
1001                 return 0;
1002
1003         if ((cur->bc_ra[lev] | lr) == cur->bc_ra[lev])
1004                 return 0;
1005
1006         cur->bc_ra[lev] |= lr;
1007         block = XFS_BUF_TO_BLOCK(cur->bc_bufs[lev]);
1008
1009         if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
1010                 return xfs_btree_readahead_lblock(cur, lr, block);
1011         return xfs_btree_readahead_sblock(cur, lr, block);
1012 }
1013
1014 STATIC int
1015 xfs_btree_ptr_to_daddr(
1016         struct xfs_btree_cur            *cur,
1017         const union xfs_btree_ptr       *ptr,
1018         xfs_daddr_t                     *daddr)
1019 {
1020         xfs_fsblock_t           fsbno;
1021         xfs_agblock_t           agbno;
1022         int                     error;
1023
1024         error = xfs_btree_check_ptr(cur, ptr, 0, 1);
1025         if (error)
1026                 return error;
1027
1028         if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
1029                 fsbno = be64_to_cpu(ptr->l);
1030                 *daddr = XFS_FSB_TO_DADDR(cur->bc_mp, fsbno);
1031         } else {
1032                 agbno = be32_to_cpu(ptr->s);
1033                 *daddr = XFS_AGB_TO_DADDR(cur->bc_mp, cur->bc_ag.pag->pag_agno,
1034                                 agbno);
1035         }
1036
1037         return 0;
1038 }
1039
1040 /*
1041  * Readahead @count btree blocks at the given @ptr location.
1042  *
1043  * We don't need to care about long or short form btrees here as we have a
1044  * method of converting the ptr directly to a daddr available to us.
1045  */
1046 STATIC void
1047 xfs_btree_readahead_ptr(
1048         struct xfs_btree_cur    *cur,
1049         union xfs_btree_ptr     *ptr,
1050         xfs_extlen_t            count)
1051 {
1052         xfs_daddr_t             daddr;
1053
1054         if (xfs_btree_ptr_to_daddr(cur, ptr, &daddr))
1055                 return;
1056         xfs_buf_readahead(cur->bc_mp->m_ddev_targp, daddr,
1057                           cur->bc_mp->m_bsize * count, cur->bc_ops->buf_ops);
1058 }
1059
1060 /*
1061  * Set the buffer for level "lev" in the cursor to bp, releasing
1062  * any previous buffer.
1063  */
1064 STATIC void
1065 xfs_btree_setbuf(
1066         xfs_btree_cur_t         *cur,   /* btree cursor */
1067         int                     lev,    /* level in btree */
1068         struct xfs_buf          *bp)    /* new buffer to set */
1069 {
1070         struct xfs_btree_block  *b;     /* btree block */
1071
1072         if (cur->bc_bufs[lev])
1073                 xfs_trans_brelse(cur->bc_tp, cur->bc_bufs[lev]);
1074         cur->bc_bufs[lev] = bp;
1075         cur->bc_ra[lev] = 0;
1076
1077         b = XFS_BUF_TO_BLOCK(bp);
1078         if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
1079                 if (b->bb_u.l.bb_leftsib == cpu_to_be64(NULLFSBLOCK))
1080                         cur->bc_ra[lev] |= XFS_BTCUR_LEFTRA;
1081                 if (b->bb_u.l.bb_rightsib == cpu_to_be64(NULLFSBLOCK))
1082                         cur->bc_ra[lev] |= XFS_BTCUR_RIGHTRA;
1083         } else {
1084                 if (b->bb_u.s.bb_leftsib == cpu_to_be32(NULLAGBLOCK))
1085                         cur->bc_ra[lev] |= XFS_BTCUR_LEFTRA;
1086                 if (b->bb_u.s.bb_rightsib == cpu_to_be32(NULLAGBLOCK))
1087                         cur->bc_ra[lev] |= XFS_BTCUR_RIGHTRA;
1088         }
1089 }
1090
1091 bool
1092 xfs_btree_ptr_is_null(
1093         struct xfs_btree_cur            *cur,
1094         const union xfs_btree_ptr       *ptr)
1095 {
1096         if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
1097                 return ptr->l == cpu_to_be64(NULLFSBLOCK);
1098         else
1099                 return ptr->s == cpu_to_be32(NULLAGBLOCK);
1100 }
1101
1102 void
1103 xfs_btree_set_ptr_null(
1104         struct xfs_btree_cur    *cur,
1105         union xfs_btree_ptr     *ptr)
1106 {
1107         if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
1108                 ptr->l = cpu_to_be64(NULLFSBLOCK);
1109         else
1110                 ptr->s = cpu_to_be32(NULLAGBLOCK);
1111 }
1112
1113 /*
1114  * Get/set/init sibling pointers
1115  */
1116 void
1117 xfs_btree_get_sibling(
1118         struct xfs_btree_cur    *cur,
1119         struct xfs_btree_block  *block,
1120         union xfs_btree_ptr     *ptr,
1121         int                     lr)
1122 {
1123         ASSERT(lr == XFS_BB_LEFTSIB || lr == XFS_BB_RIGHTSIB);
1124
1125         if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
1126                 if (lr == XFS_BB_RIGHTSIB)
1127                         ptr->l = block->bb_u.l.bb_rightsib;
1128                 else
1129                         ptr->l = block->bb_u.l.bb_leftsib;
1130         } else {
1131                 if (lr == XFS_BB_RIGHTSIB)
1132                         ptr->s = block->bb_u.s.bb_rightsib;
1133                 else
1134                         ptr->s = block->bb_u.s.bb_leftsib;
1135         }
1136 }
1137
1138 void
1139 xfs_btree_set_sibling(
1140         struct xfs_btree_cur            *cur,
1141         struct xfs_btree_block          *block,
1142         const union xfs_btree_ptr       *ptr,
1143         int                             lr)
1144 {
1145         ASSERT(lr == XFS_BB_LEFTSIB || lr == XFS_BB_RIGHTSIB);
1146
1147         if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
1148                 if (lr == XFS_BB_RIGHTSIB)
1149                         block->bb_u.l.bb_rightsib = ptr->l;
1150                 else
1151                         block->bb_u.l.bb_leftsib = ptr->l;
1152         } else {
1153                 if (lr == XFS_BB_RIGHTSIB)
1154                         block->bb_u.s.bb_rightsib = ptr->s;
1155                 else
1156                         block->bb_u.s.bb_leftsib = ptr->s;
1157         }
1158 }
1159
1160 void
1161 xfs_btree_init_block_int(
1162         struct xfs_mount        *mp,
1163         struct xfs_btree_block  *buf,
1164         xfs_daddr_t             blkno,
1165         xfs_btnum_t             btnum,
1166         __u16                   level,
1167         __u16                   numrecs,
1168         __u64                   owner,
1169         unsigned int            flags)
1170 {
1171         int                     crc = xfs_has_crc(mp);
1172         __u32                   magic = xfs_btree_magic(crc, btnum);
1173
1174         buf->bb_magic = cpu_to_be32(magic);
1175         buf->bb_level = cpu_to_be16(level);
1176         buf->bb_numrecs = cpu_to_be16(numrecs);
1177
1178         if (flags & XFS_BTREE_LONG_PTRS) {
1179                 buf->bb_u.l.bb_leftsib = cpu_to_be64(NULLFSBLOCK);
1180                 buf->bb_u.l.bb_rightsib = cpu_to_be64(NULLFSBLOCK);
1181                 if (crc) {
1182                         buf->bb_u.l.bb_blkno = cpu_to_be64(blkno);
1183                         buf->bb_u.l.bb_owner = cpu_to_be64(owner);
1184                         uuid_copy(&buf->bb_u.l.bb_uuid, &mp->m_sb.sb_meta_uuid);
1185                         buf->bb_u.l.bb_pad = 0;
1186                         buf->bb_u.l.bb_lsn = 0;
1187                 }
1188         } else {
1189                 /* owner is a 32 bit value on short blocks */
1190                 __u32 __owner = (__u32)owner;
1191
1192                 buf->bb_u.s.bb_leftsib = cpu_to_be32(NULLAGBLOCK);
1193                 buf->bb_u.s.bb_rightsib = cpu_to_be32(NULLAGBLOCK);
1194                 if (crc) {
1195                         buf->bb_u.s.bb_blkno = cpu_to_be64(blkno);
1196                         buf->bb_u.s.bb_owner = cpu_to_be32(__owner);
1197                         uuid_copy(&buf->bb_u.s.bb_uuid, &mp->m_sb.sb_meta_uuid);
1198                         buf->bb_u.s.bb_lsn = 0;
1199                 }
1200         }
1201 }
1202
1203 void
1204 xfs_btree_init_block(
1205         struct xfs_mount *mp,
1206         struct xfs_buf  *bp,
1207         xfs_btnum_t     btnum,
1208         __u16           level,
1209         __u16           numrecs,
1210         __u64           owner)
1211 {
1212         xfs_btree_init_block_int(mp, XFS_BUF_TO_BLOCK(bp), xfs_buf_daddr(bp),
1213                                  btnum, level, numrecs, owner, 0);
1214 }
1215
1216 void
1217 xfs_btree_init_block_cur(
1218         struct xfs_btree_cur    *cur,
1219         struct xfs_buf          *bp,
1220         int                     level,
1221         int                     numrecs)
1222 {
1223         __u64                   owner;
1224
1225         /*
1226          * we can pull the owner from the cursor right now as the different
1227          * owners align directly with the pointer size of the btree. This may
1228          * change in future, but is safe for current users of the generic btree
1229          * code.
1230          */
1231         if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
1232                 owner = cur->bc_ino.ip->i_ino;
1233         else
1234                 owner = cur->bc_ag.pag->pag_agno;
1235
1236         xfs_btree_init_block_int(cur->bc_mp, XFS_BUF_TO_BLOCK(bp),
1237                                 xfs_buf_daddr(bp), cur->bc_btnum, level,
1238                                 numrecs, owner, cur->bc_flags);
1239 }
1240
1241 /*
1242  * Return true if ptr is the last record in the btree and
1243  * we need to track updates to this record.  The decision
1244  * will be further refined in the update_lastrec method.
1245  */
1246 STATIC int
1247 xfs_btree_is_lastrec(
1248         struct xfs_btree_cur    *cur,
1249         struct xfs_btree_block  *block,
1250         int                     level)
1251 {
1252         union xfs_btree_ptr     ptr;
1253
1254         if (level > 0)
1255                 return 0;
1256         if (!(cur->bc_flags & XFS_BTREE_LASTREC_UPDATE))
1257                 return 0;
1258
1259         xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB);
1260         if (!xfs_btree_ptr_is_null(cur, &ptr))
1261                 return 0;
1262         return 1;
1263 }
1264
1265 STATIC void
1266 xfs_btree_buf_to_ptr(
1267         struct xfs_btree_cur    *cur,
1268         struct xfs_buf          *bp,
1269         union xfs_btree_ptr     *ptr)
1270 {
1271         if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
1272                 ptr->l = cpu_to_be64(XFS_DADDR_TO_FSB(cur->bc_mp,
1273                                         xfs_buf_daddr(bp)));
1274         else {
1275                 ptr->s = cpu_to_be32(xfs_daddr_to_agbno(cur->bc_mp,
1276                                         xfs_buf_daddr(bp)));
1277         }
1278 }
1279
1280 STATIC void
1281 xfs_btree_set_refs(
1282         struct xfs_btree_cur    *cur,
1283         struct xfs_buf          *bp)
1284 {
1285         switch (cur->bc_btnum) {
1286         case XFS_BTNUM_BNO:
1287         case XFS_BTNUM_CNT:
1288                 xfs_buf_set_ref(bp, XFS_ALLOC_BTREE_REF);
1289                 break;
1290         case XFS_BTNUM_INO:
1291         case XFS_BTNUM_FINO:
1292                 xfs_buf_set_ref(bp, XFS_INO_BTREE_REF);
1293                 break;
1294         case XFS_BTNUM_BMAP:
1295                 xfs_buf_set_ref(bp, XFS_BMAP_BTREE_REF);
1296                 break;
1297         case XFS_BTNUM_RMAP:
1298                 xfs_buf_set_ref(bp, XFS_RMAP_BTREE_REF);
1299                 break;
1300         case XFS_BTNUM_REFC:
1301                 xfs_buf_set_ref(bp, XFS_REFC_BTREE_REF);
1302                 break;
1303         default:
1304                 ASSERT(0);
1305         }
1306 }
1307
1308 int
1309 xfs_btree_get_buf_block(
1310         struct xfs_btree_cur            *cur,
1311         const union xfs_btree_ptr       *ptr,
1312         struct xfs_btree_block          **block,
1313         struct xfs_buf                  **bpp)
1314 {
1315         struct xfs_mount        *mp = cur->bc_mp;
1316         xfs_daddr_t             d;
1317         int                     error;
1318
1319         error = xfs_btree_ptr_to_daddr(cur, ptr, &d);
1320         if (error)
1321                 return error;
1322         error = xfs_trans_get_buf(cur->bc_tp, mp->m_ddev_targp, d, mp->m_bsize,
1323                         0, bpp);
1324         if (error)
1325                 return error;
1326
1327         (*bpp)->b_ops = cur->bc_ops->buf_ops;
1328         *block = XFS_BUF_TO_BLOCK(*bpp);
1329         return 0;
1330 }
1331
1332 /*
1333  * Read in the buffer at the given ptr and return the buffer and
1334  * the block pointer within the buffer.
1335  */
1336 STATIC int
1337 xfs_btree_read_buf_block(
1338         struct xfs_btree_cur            *cur,
1339         const union xfs_btree_ptr       *ptr,
1340         int                             flags,
1341         struct xfs_btree_block          **block,
1342         struct xfs_buf                  **bpp)
1343 {
1344         struct xfs_mount        *mp = cur->bc_mp;
1345         xfs_daddr_t             d;
1346         int                     error;
1347
1348         /* need to sort out how callers deal with failures first */
1349         ASSERT(!(flags & XBF_TRYLOCK));
1350
1351         error = xfs_btree_ptr_to_daddr(cur, ptr, &d);
1352         if (error)
1353                 return error;
1354         error = xfs_trans_read_buf(mp, cur->bc_tp, mp->m_ddev_targp, d,
1355                                    mp->m_bsize, flags, bpp,
1356                                    cur->bc_ops->buf_ops);
1357         if (error)
1358                 return error;
1359
1360         xfs_btree_set_refs(cur, *bpp);
1361         *block = XFS_BUF_TO_BLOCK(*bpp);
1362         return 0;
1363 }
1364
1365 /*
1366  * Copy keys from one btree block to another.
1367  */
1368 void
1369 xfs_btree_copy_keys(
1370         struct xfs_btree_cur            *cur,
1371         union xfs_btree_key             *dst_key,
1372         const union xfs_btree_key       *src_key,
1373         int                             numkeys)
1374 {
1375         ASSERT(numkeys >= 0);
1376         memcpy(dst_key, src_key, numkeys * cur->bc_ops->key_len);
1377 }
1378
1379 /*
1380  * Copy records from one btree block to another.
1381  */
1382 STATIC void
1383 xfs_btree_copy_recs(
1384         struct xfs_btree_cur    *cur,
1385         union xfs_btree_rec     *dst_rec,
1386         union xfs_btree_rec     *src_rec,
1387         int                     numrecs)
1388 {
1389         ASSERT(numrecs >= 0);
1390         memcpy(dst_rec, src_rec, numrecs * cur->bc_ops->rec_len);
1391 }
1392
1393 /*
1394  * Copy block pointers from one btree block to another.
1395  */
1396 void
1397 xfs_btree_copy_ptrs(
1398         struct xfs_btree_cur    *cur,
1399         union xfs_btree_ptr     *dst_ptr,
1400         const union xfs_btree_ptr *src_ptr,
1401         int                     numptrs)
1402 {
1403         ASSERT(numptrs >= 0);
1404         memcpy(dst_ptr, src_ptr, numptrs * xfs_btree_ptr_len(cur));
1405 }
1406
1407 /*
1408  * Shift keys one index left/right inside a single btree block.
1409  */
1410 STATIC void
1411 xfs_btree_shift_keys(
1412         struct xfs_btree_cur    *cur,
1413         union xfs_btree_key     *key,
1414         int                     dir,
1415         int                     numkeys)
1416 {
1417         char                    *dst_key;
1418
1419         ASSERT(numkeys >= 0);
1420         ASSERT(dir == 1 || dir == -1);
1421
1422         dst_key = (char *)key + (dir * cur->bc_ops->key_len);
1423         memmove(dst_key, key, numkeys * cur->bc_ops->key_len);
1424 }
1425
1426 /*
1427  * Shift records one index left/right inside a single btree block.
1428  */
1429 STATIC void
1430 xfs_btree_shift_recs(
1431         struct xfs_btree_cur    *cur,
1432         union xfs_btree_rec     *rec,
1433         int                     dir,
1434         int                     numrecs)
1435 {
1436         char                    *dst_rec;
1437
1438         ASSERT(numrecs >= 0);
1439         ASSERT(dir == 1 || dir == -1);
1440
1441         dst_rec = (char *)rec + (dir * cur->bc_ops->rec_len);
1442         memmove(dst_rec, rec, numrecs * cur->bc_ops->rec_len);
1443 }
1444
1445 /*
1446  * Shift block pointers one index left/right inside a single btree block.
1447  */
1448 STATIC void
1449 xfs_btree_shift_ptrs(
1450         struct xfs_btree_cur    *cur,
1451         union xfs_btree_ptr     *ptr,
1452         int                     dir,
1453         int                     numptrs)
1454 {
1455         char                    *dst_ptr;
1456
1457         ASSERT(numptrs >= 0);
1458         ASSERT(dir == 1 || dir == -1);
1459
1460         dst_ptr = (char *)ptr + (dir * xfs_btree_ptr_len(cur));
1461         memmove(dst_ptr, ptr, numptrs * xfs_btree_ptr_len(cur));
1462 }
1463
1464 /*
1465  * Log key values from the btree block.
1466  */
1467 STATIC void
1468 xfs_btree_log_keys(
1469         struct xfs_btree_cur    *cur,
1470         struct xfs_buf          *bp,
1471         int                     first,
1472         int                     last)
1473 {
1474
1475         if (bp) {
1476                 xfs_trans_buf_set_type(cur->bc_tp, bp, XFS_BLFT_BTREE_BUF);
1477                 xfs_trans_log_buf(cur->bc_tp, bp,
1478                                   xfs_btree_key_offset(cur, first),
1479                                   xfs_btree_key_offset(cur, last + 1) - 1);
1480         } else {
1481                 xfs_trans_log_inode(cur->bc_tp, cur->bc_ino.ip,
1482                                 xfs_ilog_fbroot(cur->bc_ino.whichfork));
1483         }
1484 }
1485
1486 /*
1487  * Log record values from the btree block.
1488  */
1489 void
1490 xfs_btree_log_recs(
1491         struct xfs_btree_cur    *cur,
1492         struct xfs_buf          *bp,
1493         int                     first,
1494         int                     last)
1495 {
1496
1497         xfs_trans_buf_set_type(cur->bc_tp, bp, XFS_BLFT_BTREE_BUF);
1498         xfs_trans_log_buf(cur->bc_tp, bp,
1499                           xfs_btree_rec_offset(cur, first),
1500                           xfs_btree_rec_offset(cur, last + 1) - 1);
1501
1502 }
1503
1504 /*
1505  * Log block pointer fields from a btree block (nonleaf).
1506  */
1507 STATIC void
1508 xfs_btree_log_ptrs(
1509         struct xfs_btree_cur    *cur,   /* btree cursor */
1510         struct xfs_buf          *bp,    /* buffer containing btree block */
1511         int                     first,  /* index of first pointer to log */
1512         int                     last)   /* index of last pointer to log */
1513 {
1514
1515         if (bp) {
1516                 struct xfs_btree_block  *block = XFS_BUF_TO_BLOCK(bp);
1517                 int                     level = xfs_btree_get_level(block);
1518
1519                 xfs_trans_buf_set_type(cur->bc_tp, bp, XFS_BLFT_BTREE_BUF);
1520                 xfs_trans_log_buf(cur->bc_tp, bp,
1521                                 xfs_btree_ptr_offset(cur, first, level),
1522                                 xfs_btree_ptr_offset(cur, last + 1, level) - 1);
1523         } else {
1524                 xfs_trans_log_inode(cur->bc_tp, cur->bc_ino.ip,
1525                         xfs_ilog_fbroot(cur->bc_ino.whichfork));
1526         }
1527
1528 }
1529
1530 /*
1531  * Log fields from a btree block header.
1532  */
1533 void
1534 xfs_btree_log_block(
1535         struct xfs_btree_cur    *cur,   /* btree cursor */
1536         struct xfs_buf          *bp,    /* buffer containing btree block */
1537         int                     fields) /* mask of fields: XFS_BB_... */
1538 {
1539         int                     first;  /* first byte offset logged */
1540         int                     last;   /* last byte offset logged */
1541         static const short      soffsets[] = {  /* table of offsets (short) */
1542                 offsetof(struct xfs_btree_block, bb_magic),
1543                 offsetof(struct xfs_btree_block, bb_level),
1544                 offsetof(struct xfs_btree_block, bb_numrecs),
1545                 offsetof(struct xfs_btree_block, bb_u.s.bb_leftsib),
1546                 offsetof(struct xfs_btree_block, bb_u.s.bb_rightsib),
1547                 offsetof(struct xfs_btree_block, bb_u.s.bb_blkno),
1548                 offsetof(struct xfs_btree_block, bb_u.s.bb_lsn),
1549                 offsetof(struct xfs_btree_block, bb_u.s.bb_uuid),
1550                 offsetof(struct xfs_btree_block, bb_u.s.bb_owner),
1551                 offsetof(struct xfs_btree_block, bb_u.s.bb_crc),
1552                 XFS_BTREE_SBLOCK_CRC_LEN
1553         };
1554         static const short      loffsets[] = {  /* table of offsets (long) */
1555                 offsetof(struct xfs_btree_block, bb_magic),
1556                 offsetof(struct xfs_btree_block, bb_level),
1557                 offsetof(struct xfs_btree_block, bb_numrecs),
1558                 offsetof(struct xfs_btree_block, bb_u.l.bb_leftsib),
1559                 offsetof(struct xfs_btree_block, bb_u.l.bb_rightsib),
1560                 offsetof(struct xfs_btree_block, bb_u.l.bb_blkno),
1561                 offsetof(struct xfs_btree_block, bb_u.l.bb_lsn),
1562                 offsetof(struct xfs_btree_block, bb_u.l.bb_uuid),
1563                 offsetof(struct xfs_btree_block, bb_u.l.bb_owner),
1564                 offsetof(struct xfs_btree_block, bb_u.l.bb_crc),
1565                 offsetof(struct xfs_btree_block, bb_u.l.bb_pad),
1566                 XFS_BTREE_LBLOCK_CRC_LEN
1567         };
1568
1569         if (bp) {
1570                 int nbits;
1571
1572                 if (cur->bc_flags & XFS_BTREE_CRC_BLOCKS) {
1573                         /*
1574                          * We don't log the CRC when updating a btree
1575                          * block but instead recreate it during log
1576                          * recovery.  As the log buffers have checksums
1577                          * of their own this is safe and avoids logging a crc
1578                          * update in a lot of places.
1579                          */
1580                         if (fields == XFS_BB_ALL_BITS)
1581                                 fields = XFS_BB_ALL_BITS_CRC;
1582                         nbits = XFS_BB_NUM_BITS_CRC;
1583                 } else {
1584                         nbits = XFS_BB_NUM_BITS;
1585                 }
1586                 xfs_btree_offsets(fields,
1587                                   (cur->bc_flags & XFS_BTREE_LONG_PTRS) ?
1588                                         loffsets : soffsets,
1589                                   nbits, &first, &last);
1590                 xfs_trans_buf_set_type(cur->bc_tp, bp, XFS_BLFT_BTREE_BUF);
1591                 xfs_trans_log_buf(cur->bc_tp, bp, first, last);
1592         } else {
1593                 xfs_trans_log_inode(cur->bc_tp, cur->bc_ino.ip,
1594                         xfs_ilog_fbroot(cur->bc_ino.whichfork));
1595         }
1596 }
1597
1598 /*
1599  * Increment cursor by one record at the level.
1600  * For nonzero levels the leaf-ward information is untouched.
1601  */
1602 int                                             /* error */
1603 xfs_btree_increment(
1604         struct xfs_btree_cur    *cur,
1605         int                     level,
1606         int                     *stat)          /* success/failure */
1607 {
1608         struct xfs_btree_block  *block;
1609         union xfs_btree_ptr     ptr;
1610         struct xfs_buf          *bp;
1611         int                     error;          /* error return value */
1612         int                     lev;
1613
1614         ASSERT(level < cur->bc_nlevels);
1615
1616         /* Read-ahead to the right at this level. */
1617         xfs_btree_readahead(cur, level, XFS_BTCUR_RIGHTRA);
1618
1619         /* Get a pointer to the btree block. */
1620         block = xfs_btree_get_block(cur, level, &bp);
1621
1622 #ifdef DEBUG
1623         error = xfs_btree_check_block(cur, block, level, bp);
1624         if (error)
1625                 goto error0;
1626 #endif
1627
1628         /* We're done if we remain in the block after the increment. */
1629         if (++cur->bc_ptrs[level] <= xfs_btree_get_numrecs(block))
1630                 goto out1;
1631
1632         /* Fail if we just went off the right edge of the tree. */
1633         xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB);
1634         if (xfs_btree_ptr_is_null(cur, &ptr))
1635                 goto out0;
1636
1637         XFS_BTREE_STATS_INC(cur, increment);
1638
1639         /*
1640          * March up the tree incrementing pointers.
1641          * Stop when we don't go off the right edge of a block.
1642          */
1643         for (lev = level + 1; lev < cur->bc_nlevels; lev++) {
1644                 block = xfs_btree_get_block(cur, lev, &bp);
1645
1646 #ifdef DEBUG
1647                 error = xfs_btree_check_block(cur, block, lev, bp);
1648                 if (error)
1649                         goto error0;
1650 #endif
1651
1652                 if (++cur->bc_ptrs[lev] <= xfs_btree_get_numrecs(block))
1653                         break;
1654
1655                 /* Read-ahead the right block for the next loop. */
1656                 xfs_btree_readahead(cur, lev, XFS_BTCUR_RIGHTRA);
1657         }
1658
1659         /*
1660          * If we went off the root then we are either seriously
1661          * confused or have the tree root in an inode.
1662          */
1663         if (lev == cur->bc_nlevels) {
1664                 if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE)
1665                         goto out0;
1666                 ASSERT(0);
1667                 error = -EFSCORRUPTED;
1668                 goto error0;
1669         }
1670         ASSERT(lev < cur->bc_nlevels);
1671
1672         /*
1673          * Now walk back down the tree, fixing up the cursor's buffer
1674          * pointers and key numbers.
1675          */
1676         for (block = xfs_btree_get_block(cur, lev, &bp); lev > level; ) {
1677                 union xfs_btree_ptr     *ptrp;
1678
1679                 ptrp = xfs_btree_ptr_addr(cur, cur->bc_ptrs[lev], block);
1680                 --lev;
1681                 error = xfs_btree_read_buf_block(cur, ptrp, 0, &block, &bp);
1682                 if (error)
1683                         goto error0;
1684
1685                 xfs_btree_setbuf(cur, lev, bp);
1686                 cur->bc_ptrs[lev] = 1;
1687         }
1688 out1:
1689         *stat = 1;
1690         return 0;
1691
1692 out0:
1693         *stat = 0;
1694         return 0;
1695
1696 error0:
1697         return error;
1698 }
1699
1700 /*
1701  * Decrement cursor by one record at the level.
1702  * For nonzero levels the leaf-ward information is untouched.
1703  */
1704 int                                             /* error */
1705 xfs_btree_decrement(
1706         struct xfs_btree_cur    *cur,
1707         int                     level,
1708         int                     *stat)          /* success/failure */
1709 {
1710         struct xfs_btree_block  *block;
1711         struct xfs_buf          *bp;
1712         int                     error;          /* error return value */
1713         int                     lev;
1714         union xfs_btree_ptr     ptr;
1715
1716         ASSERT(level < cur->bc_nlevels);
1717
1718         /* Read-ahead to the left at this level. */
1719         xfs_btree_readahead(cur, level, XFS_BTCUR_LEFTRA);
1720
1721         /* We're done if we remain in the block after the decrement. */
1722         if (--cur->bc_ptrs[level] > 0)
1723                 goto out1;
1724
1725         /* Get a pointer to the btree block. */
1726         block = xfs_btree_get_block(cur, level, &bp);
1727
1728 #ifdef DEBUG
1729         error = xfs_btree_check_block(cur, block, level, bp);
1730         if (error)
1731                 goto error0;
1732 #endif
1733
1734         /* Fail if we just went off the left edge of the tree. */
1735         xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_LEFTSIB);
1736         if (xfs_btree_ptr_is_null(cur, &ptr))
1737                 goto out0;
1738
1739         XFS_BTREE_STATS_INC(cur, decrement);
1740
1741         /*
1742          * March up the tree decrementing pointers.
1743          * Stop when we don't go off the left edge of a block.
1744          */
1745         for (lev = level + 1; lev < cur->bc_nlevels; lev++) {
1746                 if (--cur->bc_ptrs[lev] > 0)
1747                         break;
1748                 /* Read-ahead the left block for the next loop. */
1749                 xfs_btree_readahead(cur, lev, XFS_BTCUR_LEFTRA);
1750         }
1751
1752         /*
1753          * If we went off the root then we are seriously confused.
1754          * or the root of the tree is in an inode.
1755          */
1756         if (lev == cur->bc_nlevels) {
1757                 if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE)
1758                         goto out0;
1759                 ASSERT(0);
1760                 error = -EFSCORRUPTED;
1761                 goto error0;
1762         }
1763         ASSERT(lev < cur->bc_nlevels);
1764
1765         /*
1766          * Now walk back down the tree, fixing up the cursor's buffer
1767          * pointers and key numbers.
1768          */
1769         for (block = xfs_btree_get_block(cur, lev, &bp); lev > level; ) {
1770                 union xfs_btree_ptr     *ptrp;
1771
1772                 ptrp = xfs_btree_ptr_addr(cur, cur->bc_ptrs[lev], block);
1773                 --lev;
1774                 error = xfs_btree_read_buf_block(cur, ptrp, 0, &block, &bp);
1775                 if (error)
1776                         goto error0;
1777                 xfs_btree_setbuf(cur, lev, bp);
1778                 cur->bc_ptrs[lev] = xfs_btree_get_numrecs(block);
1779         }
1780 out1:
1781         *stat = 1;
1782         return 0;
1783
1784 out0:
1785         *stat = 0;
1786         return 0;
1787
1788 error0:
1789         return error;
1790 }
1791
1792 int
1793 xfs_btree_lookup_get_block(
1794         struct xfs_btree_cur            *cur,   /* btree cursor */
1795         int                             level,  /* level in the btree */
1796         const union xfs_btree_ptr       *pp,    /* ptr to btree block */
1797         struct xfs_btree_block          **blkp) /* return btree block */
1798 {
1799         struct xfs_buf          *bp;    /* buffer pointer for btree block */
1800         xfs_daddr_t             daddr;
1801         int                     error = 0;
1802
1803         /* special case the root block if in an inode */
1804         if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
1805             (level == cur->bc_nlevels - 1)) {
1806                 *blkp = xfs_btree_get_iroot(cur);
1807                 return 0;
1808         }
1809
1810         /*
1811          * If the old buffer at this level for the disk address we are
1812          * looking for re-use it.
1813          *
1814          * Otherwise throw it away and get a new one.
1815          */
1816         bp = cur->bc_bufs[level];
1817         error = xfs_btree_ptr_to_daddr(cur, pp, &daddr);
1818         if (error)
1819                 return error;
1820         if (bp && xfs_buf_daddr(bp) == daddr) {
1821                 *blkp = XFS_BUF_TO_BLOCK(bp);
1822                 return 0;
1823         }
1824
1825         error = xfs_btree_read_buf_block(cur, pp, 0, blkp, &bp);
1826         if (error)
1827                 return error;
1828
1829         /* Check the inode owner since the verifiers don't. */
1830         if (xfs_has_crc(cur->bc_mp) &&
1831             !(cur->bc_ino.flags & XFS_BTCUR_BMBT_INVALID_OWNER) &&
1832             (cur->bc_flags & XFS_BTREE_LONG_PTRS) &&
1833             be64_to_cpu((*blkp)->bb_u.l.bb_owner) !=
1834                         cur->bc_ino.ip->i_ino)
1835                 goto out_bad;
1836
1837         /* Did we get the level we were looking for? */
1838         if (be16_to_cpu((*blkp)->bb_level) != level)
1839                 goto out_bad;
1840
1841         /* Check that internal nodes have at least one record. */
1842         if (level != 0 && be16_to_cpu((*blkp)->bb_numrecs) == 0)
1843                 goto out_bad;
1844
1845         xfs_btree_setbuf(cur, level, bp);
1846         return 0;
1847
1848 out_bad:
1849         *blkp = NULL;
1850         xfs_buf_mark_corrupt(bp);
1851         xfs_trans_brelse(cur->bc_tp, bp);
1852         return -EFSCORRUPTED;
1853 }
1854
1855 /*
1856  * Get current search key.  For level 0 we don't actually have a key
1857  * structure so we make one up from the record.  For all other levels
1858  * we just return the right key.
1859  */
1860 STATIC union xfs_btree_key *
1861 xfs_lookup_get_search_key(
1862         struct xfs_btree_cur    *cur,
1863         int                     level,
1864         int                     keyno,
1865         struct xfs_btree_block  *block,
1866         union xfs_btree_key     *kp)
1867 {
1868         if (level == 0) {
1869                 cur->bc_ops->init_key_from_rec(kp,
1870                                 xfs_btree_rec_addr(cur, keyno, block));
1871                 return kp;
1872         }
1873
1874         return xfs_btree_key_addr(cur, keyno, block);
1875 }
1876
1877 /*
1878  * Lookup the record.  The cursor is made to point to it, based on dir.
1879  * stat is set to 0 if can't find any such record, 1 for success.
1880  */
1881 int                                     /* error */
1882 xfs_btree_lookup(
1883         struct xfs_btree_cur    *cur,   /* btree cursor */
1884         xfs_lookup_t            dir,    /* <=, ==, or >= */
1885         int                     *stat)  /* success/failure */
1886 {
1887         struct xfs_btree_block  *block; /* current btree block */
1888         int64_t                 diff;   /* difference for the current key */
1889         int                     error;  /* error return value */
1890         int                     keyno;  /* current key number */
1891         int                     level;  /* level in the btree */
1892         union xfs_btree_ptr     *pp;    /* ptr to btree block */
1893         union xfs_btree_ptr     ptr;    /* ptr to btree block */
1894
1895         XFS_BTREE_STATS_INC(cur, lookup);
1896
1897         /* No such thing as a zero-level tree. */
1898         if (XFS_IS_CORRUPT(cur->bc_mp, cur->bc_nlevels == 0))
1899                 return -EFSCORRUPTED;
1900
1901         block = NULL;
1902         keyno = 0;
1903
1904         /* initialise start pointer from cursor */
1905         cur->bc_ops->init_ptr_from_cur(cur, &ptr);
1906         pp = &ptr;
1907
1908         /*
1909          * Iterate over each level in the btree, starting at the root.
1910          * For each level above the leaves, find the key we need, based
1911          * on the lookup record, then follow the corresponding block
1912          * pointer down to the next level.
1913          */
1914         for (level = cur->bc_nlevels - 1, diff = 1; level >= 0; level--) {
1915                 /* Get the block we need to do the lookup on. */
1916                 error = xfs_btree_lookup_get_block(cur, level, pp, &block);
1917                 if (error)
1918                         goto error0;
1919
1920                 if (diff == 0) {
1921                         /*
1922                          * If we already had a key match at a higher level, we
1923                          * know we need to use the first entry in this block.
1924                          */
1925                         keyno = 1;
1926                 } else {
1927                         /* Otherwise search this block. Do a binary search. */
1928
1929                         int     high;   /* high entry number */
1930                         int     low;    /* low entry number */
1931
1932                         /* Set low and high entry numbers, 1-based. */
1933                         low = 1;
1934                         high = xfs_btree_get_numrecs(block);
1935                         if (!high) {
1936                                 /* Block is empty, must be an empty leaf. */
1937                                 if (level != 0 || cur->bc_nlevels != 1) {
1938                                         XFS_CORRUPTION_ERROR(__func__,
1939                                                         XFS_ERRLEVEL_LOW,
1940                                                         cur->bc_mp, block,
1941                                                         sizeof(*block));
1942                                         return -EFSCORRUPTED;
1943                                 }
1944
1945                                 cur->bc_ptrs[0] = dir != XFS_LOOKUP_LE;
1946                                 *stat = 0;
1947                                 return 0;
1948                         }
1949
1950                         /* Binary search the block. */
1951                         while (low <= high) {
1952                                 union xfs_btree_key     key;
1953                                 union xfs_btree_key     *kp;
1954
1955                                 XFS_BTREE_STATS_INC(cur, compare);
1956
1957                                 /* keyno is average of low and high. */
1958                                 keyno = (low + high) >> 1;
1959
1960                                 /* Get current search key */
1961                                 kp = xfs_lookup_get_search_key(cur, level,
1962                                                 keyno, block, &key);
1963
1964                                 /*
1965                                  * Compute difference to get next direction:
1966                                  *  - less than, move right
1967                                  *  - greater than, move left
1968                                  *  - equal, we're done
1969                                  */
1970                                 diff = cur->bc_ops->key_diff(cur, kp);
1971                                 if (diff < 0)
1972                                         low = keyno + 1;
1973                                 else if (diff > 0)
1974                                         high = keyno - 1;
1975                                 else
1976                                         break;
1977                         }
1978                 }
1979
1980                 /*
1981                  * If there are more levels, set up for the next level
1982                  * by getting the block number and filling in the cursor.
1983                  */
1984                 if (level > 0) {
1985                         /*
1986                          * If we moved left, need the previous key number,
1987                          * unless there isn't one.
1988                          */
1989                         if (diff > 0 && --keyno < 1)
1990                                 keyno = 1;
1991                         pp = xfs_btree_ptr_addr(cur, keyno, block);
1992
1993                         error = xfs_btree_debug_check_ptr(cur, pp, 0, level);
1994                         if (error)
1995                                 goto error0;
1996
1997                         cur->bc_ptrs[level] = keyno;
1998                 }
1999         }
2000
2001         /* Done with the search. See if we need to adjust the results. */
2002         if (dir != XFS_LOOKUP_LE && diff < 0) {
2003                 keyno++;
2004                 /*
2005                  * If ge search and we went off the end of the block, but it's
2006                  * not the last block, we're in the wrong block.
2007                  */
2008                 xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB);
2009                 if (dir == XFS_LOOKUP_GE &&
2010                     keyno > xfs_btree_get_numrecs(block) &&
2011                     !xfs_btree_ptr_is_null(cur, &ptr)) {
2012                         int     i;
2013
2014                         cur->bc_ptrs[0] = keyno;
2015                         error = xfs_btree_increment(cur, 0, &i);
2016                         if (error)
2017                                 goto error0;
2018                         if (XFS_IS_CORRUPT(cur->bc_mp, i != 1))
2019                                 return -EFSCORRUPTED;
2020                         *stat = 1;
2021                         return 0;
2022                 }
2023         } else if (dir == XFS_LOOKUP_LE && diff > 0)
2024                 keyno--;
2025         cur->bc_ptrs[0] = keyno;
2026
2027         /* Return if we succeeded or not. */
2028         if (keyno == 0 || keyno > xfs_btree_get_numrecs(block))
2029                 *stat = 0;
2030         else if (dir != XFS_LOOKUP_EQ || diff == 0)
2031                 *stat = 1;
2032         else
2033                 *stat = 0;
2034         return 0;
2035
2036 error0:
2037         return error;
2038 }
2039
2040 /* Find the high key storage area from a regular key. */
2041 union xfs_btree_key *
2042 xfs_btree_high_key_from_key(
2043         struct xfs_btree_cur    *cur,
2044         union xfs_btree_key     *key)
2045 {
2046         ASSERT(cur->bc_flags & XFS_BTREE_OVERLAPPING);
2047         return (union xfs_btree_key *)((char *)key +
2048                         (cur->bc_ops->key_len / 2));
2049 }
2050
2051 /* Determine the low (and high if overlapped) keys of a leaf block */
2052 STATIC void
2053 xfs_btree_get_leaf_keys(
2054         struct xfs_btree_cur    *cur,
2055         struct xfs_btree_block  *block,
2056         union xfs_btree_key     *key)
2057 {
2058         union xfs_btree_key     max_hkey;
2059         union xfs_btree_key     hkey;
2060         union xfs_btree_rec     *rec;
2061         union xfs_btree_key     *high;
2062         int                     n;
2063
2064         rec = xfs_btree_rec_addr(cur, 1, block);
2065         cur->bc_ops->init_key_from_rec(key, rec);
2066
2067         if (cur->bc_flags & XFS_BTREE_OVERLAPPING) {
2068
2069                 cur->bc_ops->init_high_key_from_rec(&max_hkey, rec);
2070                 for (n = 2; n <= xfs_btree_get_numrecs(block); n++) {
2071                         rec = xfs_btree_rec_addr(cur, n, block);
2072                         cur->bc_ops->init_high_key_from_rec(&hkey, rec);
2073                         if (cur->bc_ops->diff_two_keys(cur, &hkey, &max_hkey)
2074                                         > 0)
2075                                 max_hkey = hkey;
2076                 }
2077
2078                 high = xfs_btree_high_key_from_key(cur, key);
2079                 memcpy(high, &max_hkey, cur->bc_ops->key_len / 2);
2080         }
2081 }
2082
2083 /* Determine the low (and high if overlapped) keys of a node block */
2084 STATIC void
2085 xfs_btree_get_node_keys(
2086         struct xfs_btree_cur    *cur,
2087         struct xfs_btree_block  *block,
2088         union xfs_btree_key     *key)
2089 {
2090         union xfs_btree_key     *hkey;
2091         union xfs_btree_key     *max_hkey;
2092         union xfs_btree_key     *high;
2093         int                     n;
2094
2095         if (cur->bc_flags & XFS_BTREE_OVERLAPPING) {
2096                 memcpy(key, xfs_btree_key_addr(cur, 1, block),
2097                                 cur->bc_ops->key_len / 2);
2098
2099                 max_hkey = xfs_btree_high_key_addr(cur, 1, block);
2100                 for (n = 2; n <= xfs_btree_get_numrecs(block); n++) {
2101                         hkey = xfs_btree_high_key_addr(cur, n, block);
2102                         if (cur->bc_ops->diff_two_keys(cur, hkey, max_hkey) > 0)
2103                                 max_hkey = hkey;
2104                 }
2105
2106                 high = xfs_btree_high_key_from_key(cur, key);
2107                 memcpy(high, max_hkey, cur->bc_ops->key_len / 2);
2108         } else {
2109                 memcpy(key, xfs_btree_key_addr(cur, 1, block),
2110                                 cur->bc_ops->key_len);
2111         }
2112 }
2113
2114 /* Derive the keys for any btree block. */
2115 void
2116 xfs_btree_get_keys(
2117         struct xfs_btree_cur    *cur,
2118         struct xfs_btree_block  *block,
2119         union xfs_btree_key     *key)
2120 {
2121         if (be16_to_cpu(block->bb_level) == 0)
2122                 xfs_btree_get_leaf_keys(cur, block, key);
2123         else
2124                 xfs_btree_get_node_keys(cur, block, key);
2125 }
2126
2127 /*
2128  * Decide if we need to update the parent keys of a btree block.  For
2129  * a standard btree this is only necessary if we're updating the first
2130  * record/key.  For an overlapping btree, we must always update the
2131  * keys because the highest key can be in any of the records or keys
2132  * in the block.
2133  */
2134 static inline bool
2135 xfs_btree_needs_key_update(
2136         struct xfs_btree_cur    *cur,
2137         int                     ptr)
2138 {
2139         return (cur->bc_flags & XFS_BTREE_OVERLAPPING) || ptr == 1;
2140 }
2141
2142 /*
2143  * Update the low and high parent keys of the given level, progressing
2144  * towards the root.  If force_all is false, stop if the keys for a given
2145  * level do not need updating.
2146  */
2147 STATIC int
2148 __xfs_btree_updkeys(
2149         struct xfs_btree_cur    *cur,
2150         int                     level,
2151         struct xfs_btree_block  *block,
2152         struct xfs_buf          *bp0,
2153         bool                    force_all)
2154 {
2155         union xfs_btree_key     key;    /* keys from current level */
2156         union xfs_btree_key     *lkey;  /* keys from the next level up */
2157         union xfs_btree_key     *hkey;
2158         union xfs_btree_key     *nlkey; /* keys from the next level up */
2159         union xfs_btree_key     *nhkey;
2160         struct xfs_buf          *bp;
2161         int                     ptr;
2162
2163         ASSERT(cur->bc_flags & XFS_BTREE_OVERLAPPING);
2164
2165         /* Exit if there aren't any parent levels to update. */
2166         if (level + 1 >= cur->bc_nlevels)
2167                 return 0;
2168
2169         trace_xfs_btree_updkeys(cur, level, bp0);
2170
2171         lkey = &key;
2172         hkey = xfs_btree_high_key_from_key(cur, lkey);
2173         xfs_btree_get_keys(cur, block, lkey);
2174         for (level++; level < cur->bc_nlevels; level++) {
2175 #ifdef DEBUG
2176                 int             error;
2177 #endif
2178                 block = xfs_btree_get_block(cur, level, &bp);
2179                 trace_xfs_btree_updkeys(cur, level, bp);
2180 #ifdef DEBUG
2181                 error = xfs_btree_check_block(cur, block, level, bp);
2182                 if (error)
2183                         return error;
2184 #endif
2185                 ptr = cur->bc_ptrs[level];
2186                 nlkey = xfs_btree_key_addr(cur, ptr, block);
2187                 nhkey = xfs_btree_high_key_addr(cur, ptr, block);
2188                 if (!force_all &&
2189                     !(cur->bc_ops->diff_two_keys(cur, nlkey, lkey) != 0 ||
2190                       cur->bc_ops->diff_two_keys(cur, nhkey, hkey) != 0))
2191                         break;
2192                 xfs_btree_copy_keys(cur, nlkey, lkey, 1);
2193                 xfs_btree_log_keys(cur, bp, ptr, ptr);
2194                 if (level + 1 >= cur->bc_nlevels)
2195                         break;
2196                 xfs_btree_get_node_keys(cur, block, lkey);
2197         }
2198
2199         return 0;
2200 }
2201
2202 /* Update all the keys from some level in cursor back to the root. */
2203 STATIC int
2204 xfs_btree_updkeys_force(
2205         struct xfs_btree_cur    *cur,
2206         int                     level)
2207 {
2208         struct xfs_buf          *bp;
2209         struct xfs_btree_block  *block;
2210
2211         block = xfs_btree_get_block(cur, level, &bp);
2212         return __xfs_btree_updkeys(cur, level, block, bp, true);
2213 }
2214
2215 /*
2216  * Update the parent keys of the given level, progressing towards the root.
2217  */
2218 STATIC int
2219 xfs_btree_update_keys(
2220         struct xfs_btree_cur    *cur,
2221         int                     level)
2222 {
2223         struct xfs_btree_block  *block;
2224         struct xfs_buf          *bp;
2225         union xfs_btree_key     *kp;
2226         union xfs_btree_key     key;
2227         int                     ptr;
2228
2229         ASSERT(level >= 0);
2230
2231         block = xfs_btree_get_block(cur, level, &bp);
2232         if (cur->bc_flags & XFS_BTREE_OVERLAPPING)
2233                 return __xfs_btree_updkeys(cur, level, block, bp, false);
2234
2235         /*
2236          * Go up the tree from this level toward the root.
2237          * At each level, update the key value to the value input.
2238          * Stop when we reach a level where the cursor isn't pointing
2239          * at the first entry in the block.
2240          */
2241         xfs_btree_get_keys(cur, block, &key);
2242         for (level++, ptr = 1; ptr == 1 && level < cur->bc_nlevels; level++) {
2243 #ifdef DEBUG
2244                 int             error;
2245 #endif
2246                 block = xfs_btree_get_block(cur, level, &bp);
2247 #ifdef DEBUG
2248                 error = xfs_btree_check_block(cur, block, level, bp);
2249                 if (error)
2250                         return error;
2251 #endif
2252                 ptr = cur->bc_ptrs[level];
2253                 kp = xfs_btree_key_addr(cur, ptr, block);
2254                 xfs_btree_copy_keys(cur, kp, &key, 1);
2255                 xfs_btree_log_keys(cur, bp, ptr, ptr);
2256         }
2257
2258         return 0;
2259 }
2260
2261 /*
2262  * Update the record referred to by cur to the value in the
2263  * given record. This either works (return 0) or gets an
2264  * EFSCORRUPTED error.
2265  */
2266 int
2267 xfs_btree_update(
2268         struct xfs_btree_cur    *cur,
2269         union xfs_btree_rec     *rec)
2270 {
2271         struct xfs_btree_block  *block;
2272         struct xfs_buf          *bp;
2273         int                     error;
2274         int                     ptr;
2275         union xfs_btree_rec     *rp;
2276
2277         /* Pick up the current block. */
2278         block = xfs_btree_get_block(cur, 0, &bp);
2279
2280 #ifdef DEBUG
2281         error = xfs_btree_check_block(cur, block, 0, bp);
2282         if (error)
2283                 goto error0;
2284 #endif
2285         /* Get the address of the rec to be updated. */
2286         ptr = cur->bc_ptrs[0];
2287         rp = xfs_btree_rec_addr(cur, ptr, block);
2288
2289         /* Fill in the new contents and log them. */
2290         xfs_btree_copy_recs(cur, rp, rec, 1);
2291         xfs_btree_log_recs(cur, bp, ptr, ptr);
2292
2293         /*
2294          * If we are tracking the last record in the tree and
2295          * we are at the far right edge of the tree, update it.
2296          */
2297         if (xfs_btree_is_lastrec(cur, block, 0)) {
2298                 cur->bc_ops->update_lastrec(cur, block, rec,
2299                                             ptr, LASTREC_UPDATE);
2300         }
2301
2302         /* Pass new key value up to our parent. */
2303         if (xfs_btree_needs_key_update(cur, ptr)) {
2304                 error = xfs_btree_update_keys(cur, 0);
2305                 if (error)
2306                         goto error0;
2307         }
2308
2309         return 0;
2310
2311 error0:
2312         return error;
2313 }
2314
2315 /*
2316  * Move 1 record left from cur/level if possible.
2317  * Update cur to reflect the new path.
2318  */
2319 STATIC int                                      /* error */
2320 xfs_btree_lshift(
2321         struct xfs_btree_cur    *cur,
2322         int                     level,
2323         int                     *stat)          /* success/failure */
2324 {
2325         struct xfs_buf          *lbp;           /* left buffer pointer */
2326         struct xfs_btree_block  *left;          /* left btree block */
2327         int                     lrecs;          /* left record count */
2328         struct xfs_buf          *rbp;           /* right buffer pointer */
2329         struct xfs_btree_block  *right;         /* right btree block */
2330         struct xfs_btree_cur    *tcur;          /* temporary btree cursor */
2331         int                     rrecs;          /* right record count */
2332         union xfs_btree_ptr     lptr;           /* left btree pointer */
2333         union xfs_btree_key     *rkp = NULL;    /* right btree key */
2334         union xfs_btree_ptr     *rpp = NULL;    /* right address pointer */
2335         union xfs_btree_rec     *rrp = NULL;    /* right record pointer */
2336         int                     error;          /* error return value */
2337         int                     i;
2338
2339         if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
2340             level == cur->bc_nlevels - 1)
2341                 goto out0;
2342
2343         /* Set up variables for this block as "right". */
2344         right = xfs_btree_get_block(cur, level, &rbp);
2345
2346 #ifdef DEBUG
2347         error = xfs_btree_check_block(cur, right, level, rbp);
2348         if (error)
2349                 goto error0;
2350 #endif
2351
2352         /* If we've got no left sibling then we can't shift an entry left. */
2353         xfs_btree_get_sibling(cur, right, &lptr, XFS_BB_LEFTSIB);
2354         if (xfs_btree_ptr_is_null(cur, &lptr))
2355                 goto out0;
2356
2357         /*
2358          * If the cursor entry is the one that would be moved, don't
2359          * do it... it's too complicated.
2360          */
2361         if (cur->bc_ptrs[level] <= 1)
2362                 goto out0;
2363
2364         /* Set up the left neighbor as "left". */
2365         error = xfs_btree_read_buf_block(cur, &lptr, 0, &left, &lbp);
2366         if (error)
2367                 goto error0;
2368
2369         /* If it's full, it can't take another entry. */
2370         lrecs = xfs_btree_get_numrecs(left);
2371         if (lrecs == cur->bc_ops->get_maxrecs(cur, level))
2372                 goto out0;
2373
2374         rrecs = xfs_btree_get_numrecs(right);
2375
2376         /*
2377          * We add one entry to the left side and remove one for the right side.
2378          * Account for it here, the changes will be updated on disk and logged
2379          * later.
2380          */
2381         lrecs++;
2382         rrecs--;
2383
2384         XFS_BTREE_STATS_INC(cur, lshift);
2385         XFS_BTREE_STATS_ADD(cur, moves, 1);
2386
2387         /*
2388          * If non-leaf, copy a key and a ptr to the left block.
2389          * Log the changes to the left block.
2390          */
2391         if (level > 0) {
2392                 /* It's a non-leaf.  Move keys and pointers. */
2393                 union xfs_btree_key     *lkp;   /* left btree key */
2394                 union xfs_btree_ptr     *lpp;   /* left address pointer */
2395
2396                 lkp = xfs_btree_key_addr(cur, lrecs, left);
2397                 rkp = xfs_btree_key_addr(cur, 1, right);
2398
2399                 lpp = xfs_btree_ptr_addr(cur, lrecs, left);
2400                 rpp = xfs_btree_ptr_addr(cur, 1, right);
2401
2402                 error = xfs_btree_debug_check_ptr(cur, rpp, 0, level);
2403                 if (error)
2404                         goto error0;
2405
2406                 xfs_btree_copy_keys(cur, lkp, rkp, 1);
2407                 xfs_btree_copy_ptrs(cur, lpp, rpp, 1);
2408
2409                 xfs_btree_log_keys(cur, lbp, lrecs, lrecs);
2410                 xfs_btree_log_ptrs(cur, lbp, lrecs, lrecs);
2411
2412                 ASSERT(cur->bc_ops->keys_inorder(cur,
2413                         xfs_btree_key_addr(cur, lrecs - 1, left), lkp));
2414         } else {
2415                 /* It's a leaf.  Move records.  */
2416                 union xfs_btree_rec     *lrp;   /* left record pointer */
2417
2418                 lrp = xfs_btree_rec_addr(cur, lrecs, left);
2419                 rrp = xfs_btree_rec_addr(cur, 1, right);
2420
2421                 xfs_btree_copy_recs(cur, lrp, rrp, 1);
2422                 xfs_btree_log_recs(cur, lbp, lrecs, lrecs);
2423
2424                 ASSERT(cur->bc_ops->recs_inorder(cur,
2425                         xfs_btree_rec_addr(cur, lrecs - 1, left), lrp));
2426         }
2427
2428         xfs_btree_set_numrecs(left, lrecs);
2429         xfs_btree_log_block(cur, lbp, XFS_BB_NUMRECS);
2430
2431         xfs_btree_set_numrecs(right, rrecs);
2432         xfs_btree_log_block(cur, rbp, XFS_BB_NUMRECS);
2433
2434         /*
2435          * Slide the contents of right down one entry.
2436          */
2437         XFS_BTREE_STATS_ADD(cur, moves, rrecs - 1);
2438         if (level > 0) {
2439                 /* It's a nonleaf. operate on keys and ptrs */
2440                 for (i = 0; i < rrecs; i++) {
2441                         error = xfs_btree_debug_check_ptr(cur, rpp, i + 1, level);
2442                         if (error)
2443                                 goto error0;
2444                 }
2445
2446                 xfs_btree_shift_keys(cur,
2447                                 xfs_btree_key_addr(cur, 2, right),
2448                                 -1, rrecs);
2449                 xfs_btree_shift_ptrs(cur,
2450                                 xfs_btree_ptr_addr(cur, 2, right),
2451                                 -1, rrecs);
2452
2453                 xfs_btree_log_keys(cur, rbp, 1, rrecs);
2454                 xfs_btree_log_ptrs(cur, rbp, 1, rrecs);
2455         } else {
2456                 /* It's a leaf. operate on records */
2457                 xfs_btree_shift_recs(cur,
2458                         xfs_btree_rec_addr(cur, 2, right),
2459                         -1, rrecs);
2460                 xfs_btree_log_recs(cur, rbp, 1, rrecs);
2461         }
2462
2463         /*
2464          * Using a temporary cursor, update the parent key values of the
2465          * block on the left.
2466          */
2467         if (cur->bc_flags & XFS_BTREE_OVERLAPPING) {
2468                 error = xfs_btree_dup_cursor(cur, &tcur);
2469                 if (error)
2470                         goto error0;
2471                 i = xfs_btree_firstrec(tcur, level);
2472                 if (XFS_IS_CORRUPT(tcur->bc_mp, i != 1)) {
2473                         error = -EFSCORRUPTED;
2474                         goto error0;
2475                 }
2476
2477                 error = xfs_btree_decrement(tcur, level, &i);
2478                 if (error)
2479                         goto error1;
2480
2481                 /* Update the parent high keys of the left block, if needed. */
2482                 error = xfs_btree_update_keys(tcur, level);
2483                 if (error)
2484                         goto error1;
2485
2486                 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
2487         }
2488
2489         /* Update the parent keys of the right block. */
2490         error = xfs_btree_update_keys(cur, level);
2491         if (error)
2492                 goto error0;
2493
2494         /* Slide the cursor value left one. */
2495         cur->bc_ptrs[level]--;
2496
2497         *stat = 1;
2498         return 0;
2499
2500 out0:
2501         *stat = 0;
2502         return 0;
2503
2504 error0:
2505         return error;
2506
2507 error1:
2508         xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
2509         return error;
2510 }
2511
2512 /*
2513  * Move 1 record right from cur/level if possible.
2514  * Update cur to reflect the new path.
2515  */
2516 STATIC int                                      /* error */
2517 xfs_btree_rshift(
2518         struct xfs_btree_cur    *cur,
2519         int                     level,
2520         int                     *stat)          /* success/failure */
2521 {
2522         struct xfs_buf          *lbp;           /* left buffer pointer */
2523         struct xfs_btree_block  *left;          /* left btree block */
2524         struct xfs_buf          *rbp;           /* right buffer pointer */
2525         struct xfs_btree_block  *right;         /* right btree block */
2526         struct xfs_btree_cur    *tcur;          /* temporary btree cursor */
2527         union xfs_btree_ptr     rptr;           /* right block pointer */
2528         union xfs_btree_key     *rkp;           /* right btree key */
2529         int                     rrecs;          /* right record count */
2530         int                     lrecs;          /* left record count */
2531         int                     error;          /* error return value */
2532         int                     i;              /* loop counter */
2533
2534         if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
2535             (level == cur->bc_nlevels - 1))
2536                 goto out0;
2537
2538         /* Set up variables for this block as "left". */
2539         left = xfs_btree_get_block(cur, level, &lbp);
2540
2541 #ifdef DEBUG
2542         error = xfs_btree_check_block(cur, left, level, lbp);
2543         if (error)
2544                 goto error0;
2545 #endif
2546
2547         /* If we've got no right sibling then we can't shift an entry right. */
2548         xfs_btree_get_sibling(cur, left, &rptr, XFS_BB_RIGHTSIB);
2549         if (xfs_btree_ptr_is_null(cur, &rptr))
2550                 goto out0;
2551
2552         /*
2553          * If the cursor entry is the one that would be moved, don't
2554          * do it... it's too complicated.
2555          */
2556         lrecs = xfs_btree_get_numrecs(left);
2557         if (cur->bc_ptrs[level] >= lrecs)
2558                 goto out0;
2559
2560         /* Set up the right neighbor as "right". */
2561         error = xfs_btree_read_buf_block(cur, &rptr, 0, &right, &rbp);
2562         if (error)
2563                 goto error0;
2564
2565         /* If it's full, it can't take another entry. */
2566         rrecs = xfs_btree_get_numrecs(right);
2567         if (rrecs == cur->bc_ops->get_maxrecs(cur, level))
2568                 goto out0;
2569
2570         XFS_BTREE_STATS_INC(cur, rshift);
2571         XFS_BTREE_STATS_ADD(cur, moves, rrecs);
2572
2573         /*
2574          * Make a hole at the start of the right neighbor block, then
2575          * copy the last left block entry to the hole.
2576          */
2577         if (level > 0) {
2578                 /* It's a nonleaf. make a hole in the keys and ptrs */
2579                 union xfs_btree_key     *lkp;
2580                 union xfs_btree_ptr     *lpp;
2581                 union xfs_btree_ptr     *rpp;
2582
2583                 lkp = xfs_btree_key_addr(cur, lrecs, left);
2584                 lpp = xfs_btree_ptr_addr(cur, lrecs, left);
2585                 rkp = xfs_btree_key_addr(cur, 1, right);
2586                 rpp = xfs_btree_ptr_addr(cur, 1, right);
2587
2588                 for (i = rrecs - 1; i >= 0; i--) {
2589                         error = xfs_btree_debug_check_ptr(cur, rpp, i, level);
2590                         if (error)
2591                                 goto error0;
2592                 }
2593
2594                 xfs_btree_shift_keys(cur, rkp, 1, rrecs);
2595                 xfs_btree_shift_ptrs(cur, rpp, 1, rrecs);
2596
2597                 error = xfs_btree_debug_check_ptr(cur, lpp, 0, level);
2598                 if (error)
2599                         goto error0;
2600
2601                 /* Now put the new data in, and log it. */
2602                 xfs_btree_copy_keys(cur, rkp, lkp, 1);
2603                 xfs_btree_copy_ptrs(cur, rpp, lpp, 1);
2604
2605                 xfs_btree_log_keys(cur, rbp, 1, rrecs + 1);
2606                 xfs_btree_log_ptrs(cur, rbp, 1, rrecs + 1);
2607
2608                 ASSERT(cur->bc_ops->keys_inorder(cur, rkp,
2609                         xfs_btree_key_addr(cur, 2, right)));
2610         } else {
2611                 /* It's a leaf. make a hole in the records */
2612                 union xfs_btree_rec     *lrp;
2613                 union xfs_btree_rec     *rrp;
2614
2615                 lrp = xfs_btree_rec_addr(cur, lrecs, left);
2616                 rrp = xfs_btree_rec_addr(cur, 1, right);
2617
2618                 xfs_btree_shift_recs(cur, rrp, 1, rrecs);
2619
2620                 /* Now put the new data in, and log it. */
2621                 xfs_btree_copy_recs(cur, rrp, lrp, 1);
2622                 xfs_btree_log_recs(cur, rbp, 1, rrecs + 1);
2623         }
2624
2625         /*
2626          * Decrement and log left's numrecs, bump and log right's numrecs.
2627          */
2628         xfs_btree_set_numrecs(left, --lrecs);
2629         xfs_btree_log_block(cur, lbp, XFS_BB_NUMRECS);
2630
2631         xfs_btree_set_numrecs(right, ++rrecs);
2632         xfs_btree_log_block(cur, rbp, XFS_BB_NUMRECS);
2633
2634         /*
2635          * Using a temporary cursor, update the parent key values of the
2636          * block on the right.
2637          */
2638         error = xfs_btree_dup_cursor(cur, &tcur);
2639         if (error)
2640                 goto error0;
2641         i = xfs_btree_lastrec(tcur, level);
2642         if (XFS_IS_CORRUPT(tcur->bc_mp, i != 1)) {
2643                 error = -EFSCORRUPTED;
2644                 goto error0;
2645         }
2646
2647         error = xfs_btree_increment(tcur, level, &i);
2648         if (error)
2649                 goto error1;
2650
2651         /* Update the parent high keys of the left block, if needed. */
2652         if (cur->bc_flags & XFS_BTREE_OVERLAPPING) {
2653                 error = xfs_btree_update_keys(cur, level);
2654                 if (error)
2655                         goto error1;
2656         }
2657
2658         /* Update the parent keys of the right block. */
2659         error = xfs_btree_update_keys(tcur, level);
2660         if (error)
2661                 goto error1;
2662
2663         xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
2664
2665         *stat = 1;
2666         return 0;
2667
2668 out0:
2669         *stat = 0;
2670         return 0;
2671
2672 error0:
2673         return error;
2674
2675 error1:
2676         xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
2677         return error;
2678 }
2679
2680 /*
2681  * Split cur/level block in half.
2682  * Return new block number and the key to its first
2683  * record (to be inserted into parent).
2684  */
2685 STATIC int                                      /* error */
2686 __xfs_btree_split(
2687         struct xfs_btree_cur    *cur,
2688         int                     level,
2689         union xfs_btree_ptr     *ptrp,
2690         union xfs_btree_key     *key,
2691         struct xfs_btree_cur    **curp,
2692         int                     *stat)          /* success/failure */
2693 {
2694         union xfs_btree_ptr     lptr;           /* left sibling block ptr */
2695         struct xfs_buf          *lbp;           /* left buffer pointer */
2696         struct xfs_btree_block  *left;          /* left btree block */
2697         union xfs_btree_ptr     rptr;           /* right sibling block ptr */
2698         struct xfs_buf          *rbp;           /* right buffer pointer */
2699         struct xfs_btree_block  *right;         /* right btree block */
2700         union xfs_btree_ptr     rrptr;          /* right-right sibling ptr */
2701         struct xfs_buf          *rrbp;          /* right-right buffer pointer */
2702         struct xfs_btree_block  *rrblock;       /* right-right btree block */
2703         int                     lrecs;
2704         int                     rrecs;
2705         int                     src_index;
2706         int                     error;          /* error return value */
2707         int                     i;
2708
2709         XFS_BTREE_STATS_INC(cur, split);
2710
2711         /* Set up left block (current one). */
2712         left = xfs_btree_get_block(cur, level, &lbp);
2713
2714 #ifdef DEBUG
2715         error = xfs_btree_check_block(cur, left, level, lbp);
2716         if (error)
2717                 goto error0;
2718 #endif
2719
2720         xfs_btree_buf_to_ptr(cur, lbp, &lptr);
2721
2722         /* Allocate the new block. If we can't do it, we're toast. Give up. */
2723         error = cur->bc_ops->alloc_block(cur, &lptr, &rptr, stat);
2724         if (error)
2725                 goto error0;
2726         if (*stat == 0)
2727                 goto out0;
2728         XFS_BTREE_STATS_INC(cur, alloc);
2729
2730         /* Set up the new block as "right". */
2731         error = xfs_btree_get_buf_block(cur, &rptr, &right, &rbp);
2732         if (error)
2733                 goto error0;
2734
2735         /* Fill in the btree header for the new right block. */
2736         xfs_btree_init_block_cur(cur, rbp, xfs_btree_get_level(left), 0);
2737
2738         /*
2739          * Split the entries between the old and the new block evenly.
2740          * Make sure that if there's an odd number of entries now, that
2741          * each new block will have the same number of entries.
2742          */
2743         lrecs = xfs_btree_get_numrecs(left);
2744         rrecs = lrecs / 2;
2745         if ((lrecs & 1) && cur->bc_ptrs[level] <= rrecs + 1)
2746                 rrecs++;
2747         src_index = (lrecs - rrecs + 1);
2748
2749         XFS_BTREE_STATS_ADD(cur, moves, rrecs);
2750
2751         /* Adjust numrecs for the later get_*_keys() calls. */
2752         lrecs -= rrecs;
2753         xfs_btree_set_numrecs(left, lrecs);
2754         xfs_btree_set_numrecs(right, xfs_btree_get_numrecs(right) + rrecs);
2755
2756         /*
2757          * Copy btree block entries from the left block over to the
2758          * new block, the right. Update the right block and log the
2759          * changes.
2760          */
2761         if (level > 0) {
2762                 /* It's a non-leaf.  Move keys and pointers. */
2763                 union xfs_btree_key     *lkp;   /* left btree key */
2764                 union xfs_btree_ptr     *lpp;   /* left address pointer */
2765                 union xfs_btree_key     *rkp;   /* right btree key */
2766                 union xfs_btree_ptr     *rpp;   /* right address pointer */
2767
2768                 lkp = xfs_btree_key_addr(cur, src_index, left);
2769                 lpp = xfs_btree_ptr_addr(cur, src_index, left);
2770                 rkp = xfs_btree_key_addr(cur, 1, right);
2771                 rpp = xfs_btree_ptr_addr(cur, 1, right);
2772
2773                 for (i = src_index; i < rrecs; i++) {
2774                         error = xfs_btree_debug_check_ptr(cur, lpp, i, level);
2775                         if (error)
2776                                 goto error0;
2777                 }
2778
2779                 /* Copy the keys & pointers to the new block. */
2780                 xfs_btree_copy_keys(cur, rkp, lkp, rrecs);
2781                 xfs_btree_copy_ptrs(cur, rpp, lpp, rrecs);
2782
2783                 xfs_btree_log_keys(cur, rbp, 1, rrecs);
2784                 xfs_btree_log_ptrs(cur, rbp, 1, rrecs);
2785
2786                 /* Stash the keys of the new block for later insertion. */
2787                 xfs_btree_get_node_keys(cur, right, key);
2788         } else {
2789                 /* It's a leaf.  Move records.  */
2790                 union xfs_btree_rec     *lrp;   /* left record pointer */
2791                 union xfs_btree_rec     *rrp;   /* right record pointer */
2792
2793                 lrp = xfs_btree_rec_addr(cur, src_index, left);
2794                 rrp = xfs_btree_rec_addr(cur, 1, right);
2795
2796                 /* Copy records to the new block. */
2797                 xfs_btree_copy_recs(cur, rrp, lrp, rrecs);
2798                 xfs_btree_log_recs(cur, rbp, 1, rrecs);
2799
2800                 /* Stash the keys of the new block for later insertion. */
2801                 xfs_btree_get_leaf_keys(cur, right, key);
2802         }
2803
2804         /*
2805          * Find the left block number by looking in the buffer.
2806          * Adjust sibling pointers.
2807          */
2808         xfs_btree_get_sibling(cur, left, &rrptr, XFS_BB_RIGHTSIB);
2809         xfs_btree_set_sibling(cur, right, &rrptr, XFS_BB_RIGHTSIB);
2810         xfs_btree_set_sibling(cur, right, &lptr, XFS_BB_LEFTSIB);
2811         xfs_btree_set_sibling(cur, left, &rptr, XFS_BB_RIGHTSIB);
2812
2813         xfs_btree_log_block(cur, rbp, XFS_BB_ALL_BITS);
2814         xfs_btree_log_block(cur, lbp, XFS_BB_NUMRECS | XFS_BB_RIGHTSIB);
2815
2816         /*
2817          * If there's a block to the new block's right, make that block
2818          * point back to right instead of to left.
2819          */
2820         if (!xfs_btree_ptr_is_null(cur, &rrptr)) {
2821                 error = xfs_btree_read_buf_block(cur, &rrptr,
2822                                                         0, &rrblock, &rrbp);
2823                 if (error)
2824                         goto error0;
2825                 xfs_btree_set_sibling(cur, rrblock, &rptr, XFS_BB_LEFTSIB);
2826                 xfs_btree_log_block(cur, rrbp, XFS_BB_LEFTSIB);
2827         }
2828
2829         /* Update the parent high keys of the left block, if needed. */
2830         if (cur->bc_flags & XFS_BTREE_OVERLAPPING) {
2831                 error = xfs_btree_update_keys(cur, level);
2832                 if (error)
2833                         goto error0;
2834         }
2835
2836         /*
2837          * If the cursor is really in the right block, move it there.
2838          * If it's just pointing past the last entry in left, then we'll
2839          * insert there, so don't change anything in that case.
2840          */
2841         if (cur->bc_ptrs[level] > lrecs + 1) {
2842                 xfs_btree_setbuf(cur, level, rbp);
2843                 cur->bc_ptrs[level] -= lrecs;
2844         }
2845         /*
2846          * If there are more levels, we'll need another cursor which refers
2847          * the right block, no matter where this cursor was.
2848          */
2849         if (level + 1 < cur->bc_nlevels) {
2850                 error = xfs_btree_dup_cursor(cur, curp);
2851                 if (error)
2852                         goto error0;
2853                 (*curp)->bc_ptrs[level + 1]++;
2854         }
2855         *ptrp = rptr;
2856         *stat = 1;
2857         return 0;
2858 out0:
2859         *stat = 0;
2860         return 0;
2861
2862 error0:
2863         return error;
2864 }
2865
2866 struct xfs_btree_split_args {
2867         struct xfs_btree_cur    *cur;
2868         int                     level;
2869         union xfs_btree_ptr     *ptrp;
2870         union xfs_btree_key     *key;
2871         struct xfs_btree_cur    **curp;
2872         int                     *stat;          /* success/failure */
2873         int                     result;
2874         bool                    kswapd; /* allocation in kswapd context */
2875         struct completion       *done;
2876         struct work_struct      work;
2877 };
2878
2879 /*
2880  * Stack switching interfaces for allocation
2881  */
2882 static void
2883 xfs_btree_split_worker(
2884         struct work_struct      *work)
2885 {
2886         struct xfs_btree_split_args     *args = container_of(work,
2887                                                 struct xfs_btree_split_args, work);
2888         unsigned long           pflags;
2889         unsigned long           new_pflags = 0;
2890
2891         /*
2892          * we are in a transaction context here, but may also be doing work
2893          * in kswapd context, and hence we may need to inherit that state
2894          * temporarily to ensure that we don't block waiting for memory reclaim
2895          * in any way.
2896          */
2897         if (args->kswapd)
2898                 new_pflags |= PF_MEMALLOC | PF_SWAPWRITE | PF_KSWAPD;
2899
2900         current_set_flags_nested(&pflags, new_pflags);
2901         xfs_trans_set_context(args->cur->bc_tp);
2902
2903         args->result = __xfs_btree_split(args->cur, args->level, args->ptrp,
2904                                          args->key, args->curp, args->stat);
2905
2906         xfs_trans_clear_context(args->cur->bc_tp);
2907         current_restore_flags_nested(&pflags, new_pflags);
2908
2909         /*
2910          * Do not access args after complete() has run here. We don't own args
2911          * and the owner may run and free args before we return here.
2912          */
2913         complete(args->done);
2914
2915 }
2916
2917 /*
2918  * BMBT split requests often come in with little stack to work on. Push
2919  * them off to a worker thread so there is lots of stack to use. For the other
2920  * btree types, just call directly to avoid the context switch overhead here.
2921  */
2922 STATIC int                                      /* error */
2923 xfs_btree_split(
2924         struct xfs_btree_cur    *cur,
2925         int                     level,
2926         union xfs_btree_ptr     *ptrp,
2927         union xfs_btree_key     *key,
2928         struct xfs_btree_cur    **curp,
2929         int                     *stat)          /* success/failure */
2930 {
2931         struct xfs_btree_split_args     args;
2932         DECLARE_COMPLETION_ONSTACK(done);
2933
2934         if (cur->bc_btnum != XFS_BTNUM_BMAP)
2935                 return __xfs_btree_split(cur, level, ptrp, key, curp, stat);
2936
2937         args.cur = cur;
2938         args.level = level;
2939         args.ptrp = ptrp;
2940         args.key = key;
2941         args.curp = curp;
2942         args.stat = stat;
2943         args.done = &done;
2944         args.kswapd = current_is_kswapd();
2945         INIT_WORK_ONSTACK(&args.work, xfs_btree_split_worker);
2946         queue_work(xfs_alloc_wq, &args.work);
2947         wait_for_completion(&done);
2948         destroy_work_on_stack(&args.work);
2949         return args.result;
2950 }
2951
2952
2953 /*
2954  * Copy the old inode root contents into a real block and make the
2955  * broot point to it.
2956  */
2957 int                                             /* error */
2958 xfs_btree_new_iroot(
2959         struct xfs_btree_cur    *cur,           /* btree cursor */
2960         int                     *logflags,      /* logging flags for inode */
2961         int                     *stat)          /* return status - 0 fail */
2962 {
2963         struct xfs_buf          *cbp;           /* buffer for cblock */
2964         struct xfs_btree_block  *block;         /* btree block */
2965         struct xfs_btree_block  *cblock;        /* child btree block */
2966         union xfs_btree_key     *ckp;           /* child key pointer */
2967         union xfs_btree_ptr     *cpp;           /* child ptr pointer */
2968         union xfs_btree_key     *kp;            /* pointer to btree key */
2969         union xfs_btree_ptr     *pp;            /* pointer to block addr */
2970         union xfs_btree_ptr     nptr;           /* new block addr */
2971         int                     level;          /* btree level */
2972         int                     error;          /* error return code */
2973         int                     i;              /* loop counter */
2974
2975         XFS_BTREE_STATS_INC(cur, newroot);
2976
2977         ASSERT(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE);
2978
2979         level = cur->bc_nlevels - 1;
2980
2981         block = xfs_btree_get_iroot(cur);
2982         pp = xfs_btree_ptr_addr(cur, 1, block);
2983
2984         /* Allocate the new block. If we can't do it, we're toast. Give up. */
2985         error = cur->bc_ops->alloc_block(cur, pp, &nptr, stat);
2986         if (error)
2987                 goto error0;
2988         if (*stat == 0)
2989                 return 0;
2990
2991         XFS_BTREE_STATS_INC(cur, alloc);
2992
2993         /* Copy the root into a real block. */
2994         error = xfs_btree_get_buf_block(cur, &nptr, &cblock, &cbp);
2995         if (error)
2996                 goto error0;
2997
2998         /*
2999          * we can't just memcpy() the root in for CRC enabled btree blocks.
3000          * In that case have to also ensure the blkno remains correct
3001          */
3002         memcpy(cblock, block, xfs_btree_block_len(cur));
3003         if (cur->bc_flags & XFS_BTREE_CRC_BLOCKS) {
3004                 __be64 bno = cpu_to_be64(xfs_buf_daddr(cbp));
3005                 if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
3006                         cblock->bb_u.l.bb_blkno = bno;
3007                 else
3008                         cblock->bb_u.s.bb_blkno = bno;
3009         }
3010
3011         be16_add_cpu(&block->bb_level, 1);
3012         xfs_btree_set_numrecs(block, 1);
3013         cur->bc_nlevels++;
3014         cur->bc_ptrs[level + 1] = 1;
3015
3016         kp = xfs_btree_key_addr(cur, 1, block);
3017         ckp = xfs_btree_key_addr(cur, 1, cblock);
3018         xfs_btree_copy_keys(cur, ckp, kp, xfs_btree_get_numrecs(cblock));
3019
3020         cpp = xfs_btree_ptr_addr(cur, 1, cblock);
3021         for (i = 0; i < be16_to_cpu(cblock->bb_numrecs); i++) {
3022                 error = xfs_btree_debug_check_ptr(cur, pp, i, level);
3023                 if (error)
3024                         goto error0;
3025         }
3026
3027         xfs_btree_copy_ptrs(cur, cpp, pp, xfs_btree_get_numrecs(cblock));
3028
3029         error = xfs_btree_debug_check_ptr(cur, &nptr, 0, level);
3030         if (error)
3031                 goto error0;
3032
3033         xfs_btree_copy_ptrs(cur, pp, &nptr, 1);
3034
3035         xfs_iroot_realloc(cur->bc_ino.ip,
3036                           1 - xfs_btree_get_numrecs(cblock),
3037                           cur->bc_ino.whichfork);
3038
3039         xfs_btree_setbuf(cur, level, cbp);
3040
3041         /*
3042          * Do all this logging at the end so that
3043          * the root is at the right level.
3044          */
3045         xfs_btree_log_block(cur, cbp, XFS_BB_ALL_BITS);
3046         xfs_btree_log_keys(cur, cbp, 1, be16_to_cpu(cblock->bb_numrecs));
3047         xfs_btree_log_ptrs(cur, cbp, 1, be16_to_cpu(cblock->bb_numrecs));
3048
3049         *logflags |=
3050                 XFS_ILOG_CORE | xfs_ilog_fbroot(cur->bc_ino.whichfork);
3051         *stat = 1;
3052         return 0;
3053 error0:
3054         return error;
3055 }
3056
3057 /*
3058  * Allocate a new root block, fill it in.
3059  */
3060 STATIC int                              /* error */
3061 xfs_btree_new_root(
3062         struct xfs_btree_cur    *cur,   /* btree cursor */
3063         int                     *stat)  /* success/failure */
3064 {
3065         struct xfs_btree_block  *block; /* one half of the old root block */
3066         struct xfs_buf          *bp;    /* buffer containing block */
3067         int                     error;  /* error return value */
3068         struct xfs_buf          *lbp;   /* left buffer pointer */
3069         struct xfs_btree_block  *left;  /* left btree block */
3070         struct xfs_buf          *nbp;   /* new (root) buffer */
3071         struct xfs_btree_block  *new;   /* new (root) btree block */
3072         int                     nptr;   /* new value for key index, 1 or 2 */
3073         struct xfs_buf          *rbp;   /* right buffer pointer */
3074         struct xfs_btree_block  *right; /* right btree block */
3075         union xfs_btree_ptr     rptr;
3076         union xfs_btree_ptr     lptr;
3077
3078         XFS_BTREE_STATS_INC(cur, newroot);
3079
3080         /* initialise our start point from the cursor */
3081         cur->bc_ops->init_ptr_from_cur(cur, &rptr);
3082
3083         /* Allocate the new block. If we can't do it, we're toast. Give up. */
3084         error = cur->bc_ops->alloc_block(cur, &rptr, &lptr, stat);
3085         if (error)
3086                 goto error0;
3087         if (*stat == 0)
3088                 goto out0;
3089         XFS_BTREE_STATS_INC(cur, alloc);
3090
3091         /* Set up the new block. */
3092         error = xfs_btree_get_buf_block(cur, &lptr, &new, &nbp);
3093         if (error)
3094                 goto error0;
3095
3096         /* Set the root in the holding structure  increasing the level by 1. */
3097         cur->bc_ops->set_root(cur, &lptr, 1);
3098
3099         /*
3100          * At the previous root level there are now two blocks: the old root,
3101          * and the new block generated when it was split.  We don't know which
3102          * one the cursor is pointing at, so we set up variables "left" and
3103          * "right" for each case.
3104          */
3105         block = xfs_btree_get_block(cur, cur->bc_nlevels - 1, &bp);
3106
3107 #ifdef DEBUG
3108         error = xfs_btree_check_block(cur, block, cur->bc_nlevels - 1, bp);
3109         if (error)
3110                 goto error0;
3111 #endif
3112
3113         xfs_btree_get_sibling(cur, block, &rptr, XFS_BB_RIGHTSIB);
3114         if (!xfs_btree_ptr_is_null(cur, &rptr)) {
3115                 /* Our block is left, pick up the right block. */
3116                 lbp = bp;
3117                 xfs_btree_buf_to_ptr(cur, lbp, &lptr);
3118                 left = block;
3119                 error = xfs_btree_read_buf_block(cur, &rptr, 0, &right, &rbp);
3120                 if (error)
3121                         goto error0;
3122                 bp = rbp;
3123                 nptr = 1;
3124         } else {
3125                 /* Our block is right, pick up the left block. */
3126                 rbp = bp;
3127                 xfs_btree_buf_to_ptr(cur, rbp, &rptr);
3128                 right = block;
3129                 xfs_btree_get_sibling(cur, right, &lptr, XFS_BB_LEFTSIB);
3130                 error = xfs_btree_read_buf_block(cur, &lptr, 0, &left, &lbp);
3131                 if (error)
3132                         goto error0;
3133                 bp = lbp;
3134                 nptr = 2;
3135         }
3136
3137         /* Fill in the new block's btree header and log it. */
3138         xfs_btree_init_block_cur(cur, nbp, cur->bc_nlevels, 2);
3139         xfs_btree_log_block(cur, nbp, XFS_BB_ALL_BITS);
3140         ASSERT(!xfs_btree_ptr_is_null(cur, &lptr) &&
3141                         !xfs_btree_ptr_is_null(cur, &rptr));
3142
3143         /* Fill in the key data in the new root. */
3144         if (xfs_btree_get_level(left) > 0) {
3145                 /*
3146                  * Get the keys for the left block's keys and put them directly
3147                  * in the parent block.  Do the same for the right block.
3148                  */
3149                 xfs_btree_get_node_keys(cur, left,
3150                                 xfs_btree_key_addr(cur, 1, new));
3151                 xfs_btree_get_node_keys(cur, right,
3152                                 xfs_btree_key_addr(cur, 2, new));
3153         } else {
3154                 /*
3155                  * Get the keys for the left block's records and put them
3156                  * directly in the parent block.  Do the same for the right
3157                  * block.
3158                  */
3159                 xfs_btree_get_leaf_keys(cur, left,
3160                         xfs_btree_key_addr(cur, 1, new));
3161                 xfs_btree_get_leaf_keys(cur, right,
3162                         xfs_btree_key_addr(cur, 2, new));
3163         }
3164         xfs_btree_log_keys(cur, nbp, 1, 2);
3165
3166         /* Fill in the pointer data in the new root. */
3167         xfs_btree_copy_ptrs(cur,
3168                 xfs_btree_ptr_addr(cur, 1, new), &lptr, 1);
3169         xfs_btree_copy_ptrs(cur,
3170                 xfs_btree_ptr_addr(cur, 2, new), &rptr, 1);
3171         xfs_btree_log_ptrs(cur, nbp, 1, 2);
3172
3173         /* Fix up the cursor. */
3174         xfs_btree_setbuf(cur, cur->bc_nlevels, nbp);
3175         cur->bc_ptrs[cur->bc_nlevels] = nptr;
3176         cur->bc_nlevels++;
3177         *stat = 1;
3178         return 0;
3179 error0:
3180         return error;
3181 out0:
3182         *stat = 0;
3183         return 0;
3184 }
3185
3186 STATIC int
3187 xfs_btree_make_block_unfull(
3188         struct xfs_btree_cur    *cur,   /* btree cursor */
3189         int                     level,  /* btree level */
3190         int                     numrecs,/* # of recs in block */
3191         int                     *oindex,/* old tree index */
3192         int                     *index, /* new tree index */
3193         union xfs_btree_ptr     *nptr,  /* new btree ptr */
3194         struct xfs_btree_cur    **ncur, /* new btree cursor */
3195         union xfs_btree_key     *key,   /* key of new block */
3196         int                     *stat)
3197 {
3198         int                     error = 0;
3199
3200         if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
3201             level == cur->bc_nlevels - 1) {
3202                 struct xfs_inode *ip = cur->bc_ino.ip;
3203
3204                 if (numrecs < cur->bc_ops->get_dmaxrecs(cur, level)) {
3205                         /* A root block that can be made bigger. */
3206                         xfs_iroot_realloc(ip, 1, cur->bc_ino.whichfork);
3207                         *stat = 1;
3208                 } else {
3209                         /* A root block that needs replacing */
3210                         int     logflags = 0;
3211
3212                         error = xfs_btree_new_iroot(cur, &logflags, stat);
3213                         if (error || *stat == 0)
3214                                 return error;
3215
3216                         xfs_trans_log_inode(cur->bc_tp, ip, logflags);
3217                 }
3218
3219                 return 0;
3220         }
3221
3222         /* First, try shifting an entry to the right neighbor. */
3223         error = xfs_btree_rshift(cur, level, stat);
3224         if (error || *stat)
3225                 return error;
3226
3227         /* Next, try shifting an entry to the left neighbor. */
3228         error = xfs_btree_lshift(cur, level, stat);
3229         if (error)
3230                 return error;
3231
3232         if (*stat) {
3233                 *oindex = *index = cur->bc_ptrs[level];
3234                 return 0;
3235         }
3236
3237         /*
3238          * Next, try splitting the current block in half.
3239          *
3240          * If this works we have to re-set our variables because we
3241          * could be in a different block now.
3242          */
3243         error = xfs_btree_split(cur, level, nptr, key, ncur, stat);
3244         if (error || *stat == 0)
3245                 return error;
3246
3247
3248         *index = cur->bc_ptrs[level];
3249         return 0;
3250 }
3251
3252 /*
3253  * Insert one record/level.  Return information to the caller
3254  * allowing the next level up to proceed if necessary.
3255  */
3256 STATIC int
3257 xfs_btree_insrec(
3258         struct xfs_btree_cur    *cur,   /* btree cursor */
3259         int                     level,  /* level to insert record at */
3260         union xfs_btree_ptr     *ptrp,  /* i/o: block number inserted */
3261         union xfs_btree_rec     *rec,   /* record to insert */
3262         union xfs_btree_key     *key,   /* i/o: block key for ptrp */
3263         struct xfs_btree_cur    **curp, /* output: new cursor replacing cur */
3264         int                     *stat)  /* success/failure */
3265 {
3266         struct xfs_btree_block  *block; /* btree block */
3267         struct xfs_buf          *bp;    /* buffer for block */
3268         union xfs_btree_ptr     nptr;   /* new block ptr */
3269         struct xfs_btree_cur    *ncur = NULL;   /* new btree cursor */
3270         union xfs_btree_key     nkey;   /* new block key */
3271         union xfs_btree_key     *lkey;
3272         int                     optr;   /* old key/record index */
3273         int                     ptr;    /* key/record index */
3274         int                     numrecs;/* number of records */
3275         int                     error;  /* error return value */
3276         int                     i;
3277         xfs_daddr_t             old_bn;
3278
3279         ncur = NULL;
3280         lkey = &nkey;
3281
3282         /*
3283          * If we have an external root pointer, and we've made it to the
3284          * root level, allocate a new root block and we're done.
3285          */
3286         if (!(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
3287             (level >= cur->bc_nlevels)) {
3288                 error = xfs_btree_new_root(cur, stat);
3289                 xfs_btree_set_ptr_null(cur, ptrp);
3290
3291                 return error;
3292         }
3293
3294         /* If we're off the left edge, return failure. */
3295         ptr = cur->bc_ptrs[level];
3296         if (ptr == 0) {
3297                 *stat = 0;
3298                 return 0;
3299         }
3300
3301         optr = ptr;
3302
3303         XFS_BTREE_STATS_INC(cur, insrec);
3304
3305         /* Get pointers to the btree buffer and block. */
3306         block = xfs_btree_get_block(cur, level, &bp);
3307         old_bn = bp ? xfs_buf_daddr(bp) : XFS_BUF_DADDR_NULL;
3308         numrecs = xfs_btree_get_numrecs(block);
3309
3310 #ifdef DEBUG
3311         error = xfs_btree_check_block(cur, block, level, bp);
3312         if (error)
3313                 goto error0;
3314
3315         /* Check that the new entry is being inserted in the right place. */
3316         if (ptr <= numrecs) {
3317                 if (level == 0) {
3318                         ASSERT(cur->bc_ops->recs_inorder(cur, rec,
3319                                 xfs_btree_rec_addr(cur, ptr, block)));
3320                 } else {
3321                         ASSERT(cur->bc_ops->keys_inorder(cur, key,
3322                                 xfs_btree_key_addr(cur, ptr, block)));
3323                 }
3324         }
3325 #endif
3326
3327         /*
3328          * If the block is full, we can't insert the new entry until we
3329          * make the block un-full.
3330          */
3331         xfs_btree_set_ptr_null(cur, &nptr);
3332         if (numrecs == cur->bc_ops->get_maxrecs(cur, level)) {
3333                 error = xfs_btree_make_block_unfull(cur, level, numrecs,
3334                                         &optr, &ptr, &nptr, &ncur, lkey, stat);
3335                 if (error || *stat == 0)
3336                         goto error0;
3337         }
3338
3339         /*
3340          * The current block may have changed if the block was
3341          * previously full and we have just made space in it.
3342          */
3343         block = xfs_btree_get_block(cur, level, &bp);
3344         numrecs = xfs_btree_get_numrecs(block);
3345
3346 #ifdef DEBUG
3347         error = xfs_btree_check_block(cur, block, level, bp);
3348         if (error)
3349                 goto error0;
3350 #endif
3351
3352         /*
3353          * At this point we know there's room for our new entry in the block
3354          * we're pointing at.
3355          */
3356         XFS_BTREE_STATS_ADD(cur, moves, numrecs - ptr + 1);
3357
3358         if (level > 0) {
3359                 /* It's a nonleaf. make a hole in the keys and ptrs */
3360                 union xfs_btree_key     *kp;
3361                 union xfs_btree_ptr     *pp;
3362
3363                 kp = xfs_btree_key_addr(cur, ptr, block);
3364                 pp = xfs_btree_ptr_addr(cur, ptr, block);
3365
3366                 for (i = numrecs - ptr; i >= 0; i--) {
3367                         error = xfs_btree_debug_check_ptr(cur, pp, i, level);
3368                         if (error)
3369                                 goto error0;
3370                 }
3371
3372                 xfs_btree_shift_keys(cur, kp, 1, numrecs - ptr + 1);
3373                 xfs_btree_shift_ptrs(cur, pp, 1, numrecs - ptr + 1);
3374
3375                 error = xfs_btree_debug_check_ptr(cur, ptrp, 0, level);
3376                 if (error)
3377                         goto error0;
3378
3379                 /* Now put the new data in, bump numrecs and log it. */
3380                 xfs_btree_copy_keys(cur, kp, key, 1);
3381                 xfs_btree_copy_ptrs(cur, pp, ptrp, 1);
3382                 numrecs++;
3383                 xfs_btree_set_numrecs(block, numrecs);
3384                 xfs_btree_log_ptrs(cur, bp, ptr, numrecs);
3385                 xfs_btree_log_keys(cur, bp, ptr, numrecs);
3386 #ifdef DEBUG
3387                 if (ptr < numrecs) {
3388                         ASSERT(cur->bc_ops->keys_inorder(cur, kp,
3389                                 xfs_btree_key_addr(cur, ptr + 1, block)));
3390                 }
3391 #endif
3392         } else {
3393                 /* It's a leaf. make a hole in the records */
3394                 union xfs_btree_rec             *rp;
3395
3396                 rp = xfs_btree_rec_addr(cur, ptr, block);
3397
3398                 xfs_btree_shift_recs(cur, rp, 1, numrecs - ptr + 1);
3399
3400                 /* Now put the new data in, bump numrecs and log it. */
3401                 xfs_btree_copy_recs(cur, rp, rec, 1);
3402                 xfs_btree_set_numrecs(block, ++numrecs);
3403                 xfs_btree_log_recs(cur, bp, ptr, numrecs);
3404 #ifdef DEBUG
3405                 if (ptr < numrecs) {
3406                         ASSERT(cur->bc_ops->recs_inorder(cur, rp,
3407                                 xfs_btree_rec_addr(cur, ptr + 1, block)));
3408                 }
3409 #endif
3410         }
3411
3412         /* Log the new number of records in the btree header. */
3413         xfs_btree_log_block(cur, bp, XFS_BB_NUMRECS);
3414
3415         /*
3416          * If we just inserted into a new tree block, we have to
3417          * recalculate nkey here because nkey is out of date.
3418          *
3419          * Otherwise we're just updating an existing block (having shoved
3420          * some records into the new tree block), so use the regular key
3421          * update mechanism.
3422          */
3423         if (bp && xfs_buf_daddr(bp) != old_bn) {
3424                 xfs_btree_get_keys(cur, block, lkey);
3425         } else if (xfs_btree_needs_key_update(cur, optr)) {
3426                 error = xfs_btree_update_keys(cur, level);
3427                 if (error)
3428                         goto error0;
3429         }
3430
3431         /*
3432          * If we are tracking the last record in the tree and
3433          * we are at the far right edge of the tree, update it.
3434          */
3435         if (xfs_btree_is_lastrec(cur, block, level)) {
3436                 cur->bc_ops->update_lastrec(cur, block, rec,
3437                                             ptr, LASTREC_INSREC);
3438         }
3439
3440         /*
3441          * Return the new block number, if any.
3442          * If there is one, give back a record value and a cursor too.
3443          */
3444         *ptrp = nptr;
3445         if (!xfs_btree_ptr_is_null(cur, &nptr)) {
3446                 xfs_btree_copy_keys(cur, key, lkey, 1);
3447                 *curp = ncur;
3448         }
3449
3450         *stat = 1;
3451         return 0;
3452
3453 error0:
3454         if (ncur)
3455                 xfs_btree_del_cursor(ncur, error);
3456         return error;
3457 }
3458
3459 /*
3460  * Insert the record at the point referenced by cur.
3461  *
3462  * A multi-level split of the tree on insert will invalidate the original
3463  * cursor.  All callers of this function should assume that the cursor is
3464  * no longer valid and revalidate it.
3465  */
3466 int
3467 xfs_btree_insert(
3468         struct xfs_btree_cur    *cur,
3469         int                     *stat)
3470 {
3471         int                     error;  /* error return value */
3472         int                     i;      /* result value, 0 for failure */
3473         int                     level;  /* current level number in btree */
3474         union xfs_btree_ptr     nptr;   /* new block number (split result) */
3475         struct xfs_btree_cur    *ncur;  /* new cursor (split result) */
3476         struct xfs_btree_cur    *pcur;  /* previous level's cursor */
3477         union xfs_btree_key     bkey;   /* key of block to insert */
3478         union xfs_btree_key     *key;
3479         union xfs_btree_rec     rec;    /* record to insert */
3480
3481         level = 0;
3482         ncur = NULL;
3483         pcur = cur;
3484         key = &bkey;
3485
3486         xfs_btree_set_ptr_null(cur, &nptr);
3487
3488         /* Make a key out of the record data to be inserted, and save it. */
3489         cur->bc_ops->init_rec_from_cur(cur, &rec);
3490         cur->bc_ops->init_key_from_rec(key, &rec);
3491
3492         /*
3493          * Loop going up the tree, starting at the leaf level.
3494          * Stop when we don't get a split block, that must mean that
3495          * the insert is finished with this level.
3496          */
3497         do {
3498                 /*
3499                  * Insert nrec/nptr into this level of the tree.
3500                  * Note if we fail, nptr will be null.
3501                  */
3502                 error = xfs_btree_insrec(pcur, level, &nptr, &rec, key,
3503                                 &ncur, &i);
3504                 if (error) {
3505                         if (pcur != cur)
3506                                 xfs_btree_del_cursor(pcur, XFS_BTREE_ERROR);
3507                         goto error0;
3508                 }
3509
3510                 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) {
3511                         error = -EFSCORRUPTED;
3512                         goto error0;
3513                 }
3514                 level++;
3515
3516                 /*
3517                  * See if the cursor we just used is trash.
3518                  * Can't trash the caller's cursor, but otherwise we should
3519                  * if ncur is a new cursor or we're about to be done.
3520                  */
3521                 if (pcur != cur &&
3522                     (ncur || xfs_btree_ptr_is_null(cur, &nptr))) {
3523                         /* Save the state from the cursor before we trash it */
3524                         if (cur->bc_ops->update_cursor)
3525                                 cur->bc_ops->update_cursor(pcur, cur);
3526                         cur->bc_nlevels = pcur->bc_nlevels;
3527                         xfs_btree_del_cursor(pcur, XFS_BTREE_NOERROR);
3528                 }
3529                 /* If we got a new cursor, switch to it. */
3530                 if (ncur) {
3531                         pcur = ncur;
3532                         ncur = NULL;
3533                 }
3534         } while (!xfs_btree_ptr_is_null(cur, &nptr));
3535
3536         *stat = i;
3537         return 0;
3538 error0:
3539         return error;
3540 }
3541
3542 /*
3543  * Try to merge a non-leaf block back into the inode root.
3544  *
3545  * Note: the killroot names comes from the fact that we're effectively
3546  * killing the old root block.  But because we can't just delete the
3547  * inode we have to copy the single block it was pointing to into the
3548  * inode.
3549  */
3550 STATIC int
3551 xfs_btree_kill_iroot(
3552         struct xfs_btree_cur    *cur)
3553 {
3554         int                     whichfork = cur->bc_ino.whichfork;
3555         struct xfs_inode        *ip = cur->bc_ino.ip;
3556         struct xfs_ifork        *ifp = XFS_IFORK_PTR(ip, whichfork);
3557         struct xfs_btree_block  *block;
3558         struct xfs_btree_block  *cblock;
3559         union xfs_btree_key     *kp;
3560         union xfs_btree_key     *ckp;
3561         union xfs_btree_ptr     *pp;
3562         union xfs_btree_ptr     *cpp;
3563         struct xfs_buf          *cbp;
3564         int                     level;
3565         int                     index;
3566         int                     numrecs;
3567         int                     error;
3568 #ifdef DEBUG
3569         union xfs_btree_ptr     ptr;
3570 #endif
3571         int                     i;
3572
3573         ASSERT(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE);
3574         ASSERT(cur->bc_nlevels > 1);
3575
3576         /*
3577          * Don't deal with the root block needs to be a leaf case.
3578          * We're just going to turn the thing back into extents anyway.
3579          */
3580         level = cur->bc_nlevels - 1;
3581         if (level == 1)
3582                 goto out0;
3583
3584         /*
3585          * Give up if the root has multiple children.
3586          */
3587         block = xfs_btree_get_iroot(cur);
3588         if (xfs_btree_get_numrecs(block) != 1)
3589                 goto out0;
3590
3591         cblock = xfs_btree_get_block(cur, level - 1, &cbp);
3592         numrecs = xfs_btree_get_numrecs(cblock);
3593
3594         /*
3595          * Only do this if the next level will fit.
3596          * Then the data must be copied up to the inode,
3597          * instead of freeing the root you free the next level.
3598          */
3599         if (numrecs > cur->bc_ops->get_dmaxrecs(cur, level))
3600                 goto out0;
3601
3602         XFS_BTREE_STATS_INC(cur, killroot);
3603
3604 #ifdef DEBUG
3605         xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_LEFTSIB);
3606         ASSERT(xfs_btree_ptr_is_null(cur, &ptr));
3607         xfs_btree_get_sibling(cur, block, &ptr, XFS_BB_RIGHTSIB);
3608         ASSERT(xfs_btree_ptr_is_null(cur, &ptr));
3609 #endif
3610
3611         index = numrecs - cur->bc_ops->get_maxrecs(cur, level);
3612         if (index) {
3613                 xfs_iroot_realloc(cur->bc_ino.ip, index,
3614                                   cur->bc_ino.whichfork);
3615                 block = ifp->if_broot;
3616         }
3617
3618         be16_add_cpu(&block->bb_numrecs, index);
3619         ASSERT(block->bb_numrecs == cblock->bb_numrecs);
3620
3621         kp = xfs_btree_key_addr(cur, 1, block);
3622         ckp = xfs_btree_key_addr(cur, 1, cblock);
3623         xfs_btree_copy_keys(cur, kp, ckp, numrecs);
3624
3625         pp = xfs_btree_ptr_addr(cur, 1, block);
3626         cpp = xfs_btree_ptr_addr(cur, 1, cblock);
3627
3628         for (i = 0; i < numrecs; i++) {
3629                 error = xfs_btree_debug_check_ptr(cur, cpp, i, level - 1);
3630                 if (error)
3631                         return error;
3632         }
3633
3634         xfs_btree_copy_ptrs(cur, pp, cpp, numrecs);
3635
3636         error = xfs_btree_free_block(cur, cbp);
3637         if (error)
3638                 return error;
3639
3640         cur->bc_bufs[level - 1] = NULL;
3641         be16_add_cpu(&block->bb_level, -1);
3642         xfs_trans_log_inode(cur->bc_tp, ip,
3643                 XFS_ILOG_CORE | xfs_ilog_fbroot(cur->bc_ino.whichfork));
3644         cur->bc_nlevels--;
3645 out0:
3646         return 0;
3647 }
3648
3649 /*
3650  * Kill the current root node, and replace it with it's only child node.
3651  */
3652 STATIC int
3653 xfs_btree_kill_root(
3654         struct xfs_btree_cur    *cur,
3655         struct xfs_buf          *bp,
3656         int                     level,
3657         union xfs_btree_ptr     *newroot)
3658 {
3659         int                     error;
3660
3661         XFS_BTREE_STATS_INC(cur, killroot);
3662
3663         /*
3664          * Update the root pointer, decreasing the level by 1 and then
3665          * free the old root.
3666          */
3667         cur->bc_ops->set_root(cur, newroot, -1);
3668
3669         error = xfs_btree_free_block(cur, bp);
3670         if (error)
3671                 return error;
3672
3673         cur->bc_bufs[level] = NULL;
3674         cur->bc_ra[level] = 0;
3675         cur->bc_nlevels--;
3676
3677         return 0;
3678 }
3679
3680 STATIC int
3681 xfs_btree_dec_cursor(
3682         struct xfs_btree_cur    *cur,
3683         int                     level,
3684         int                     *stat)
3685 {
3686         int                     error;
3687         int                     i;
3688
3689         if (level > 0) {
3690                 error = xfs_btree_decrement(cur, level, &i);
3691                 if (error)
3692                         return error;
3693         }
3694
3695         *stat = 1;
3696         return 0;
3697 }
3698
3699 /*
3700  * Single level of the btree record deletion routine.
3701  * Delete record pointed to by cur/level.
3702  * Remove the record from its block then rebalance the tree.
3703  * Return 0 for error, 1 for done, 2 to go on to the next level.
3704  */
3705 STATIC int                                      /* error */
3706 xfs_btree_delrec(
3707         struct xfs_btree_cur    *cur,           /* btree cursor */
3708         int                     level,          /* level removing record from */
3709         int                     *stat)          /* fail/done/go-on */
3710 {
3711         struct xfs_btree_block  *block;         /* btree block */
3712         union xfs_btree_ptr     cptr;           /* current block ptr */
3713         struct xfs_buf          *bp;            /* buffer for block */
3714         int                     error;          /* error return value */
3715         int                     i;              /* loop counter */
3716         union xfs_btree_ptr     lptr;           /* left sibling block ptr */
3717         struct xfs_buf          *lbp;           /* left buffer pointer */
3718         struct xfs_btree_block  *left;          /* left btree block */
3719         int                     lrecs = 0;      /* left record count */
3720         int                     ptr;            /* key/record index */
3721         union xfs_btree_ptr     rptr;           /* right sibling block ptr */
3722         struct xfs_buf          *rbp;           /* right buffer pointer */
3723         struct xfs_btree_block  *right;         /* right btree block */
3724         struct xfs_btree_block  *rrblock;       /* right-right btree block */
3725         struct xfs_buf          *rrbp;          /* right-right buffer pointer */
3726         int                     rrecs = 0;      /* right record count */
3727         struct xfs_btree_cur    *tcur;          /* temporary btree cursor */
3728         int                     numrecs;        /* temporary numrec count */
3729
3730         tcur = NULL;
3731
3732         /* Get the index of the entry being deleted, check for nothing there. */
3733         ptr = cur->bc_ptrs[level];
3734         if (ptr == 0) {
3735                 *stat = 0;
3736                 return 0;
3737         }
3738
3739         /* Get the buffer & block containing the record or key/ptr. */
3740         block = xfs_btree_get_block(cur, level, &bp);
3741         numrecs = xfs_btree_get_numrecs(block);
3742
3743 #ifdef DEBUG
3744         error = xfs_btree_check_block(cur, block, level, bp);
3745         if (error)
3746                 goto error0;
3747 #endif
3748
3749         /* Fail if we're off the end of the block. */
3750         if (ptr > numrecs) {
3751                 *stat = 0;
3752                 return 0;
3753         }
3754
3755         XFS_BTREE_STATS_INC(cur, delrec);
3756         XFS_BTREE_STATS_ADD(cur, moves, numrecs - ptr);
3757
3758         /* Excise the entries being deleted. */
3759         if (level > 0) {
3760                 /* It's a nonleaf. operate on keys and ptrs */
3761                 union xfs_btree_key     *lkp;
3762                 union xfs_btree_ptr     *lpp;
3763
3764                 lkp = xfs_btree_key_addr(cur, ptr + 1, block);
3765                 lpp = xfs_btree_ptr_addr(cur, ptr + 1, block);
3766
3767                 for (i = 0; i < numrecs - ptr; i++) {
3768                         error = xfs_btree_debug_check_ptr(cur, lpp, i, level);
3769                         if (error)
3770                                 goto error0;
3771                 }
3772
3773                 if (ptr < numrecs) {
3774                         xfs_btree_shift_keys(cur, lkp, -1, numrecs - ptr);
3775                         xfs_btree_shift_ptrs(cur, lpp, -1, numrecs - ptr);
3776                         xfs_btree_log_keys(cur, bp, ptr, numrecs - 1);
3777                         xfs_btree_log_ptrs(cur, bp, ptr, numrecs - 1);
3778                 }
3779         } else {
3780                 /* It's a leaf. operate on records */
3781                 if (ptr < numrecs) {
3782                         xfs_btree_shift_recs(cur,
3783                                 xfs_btree_rec_addr(cur, ptr + 1, block),
3784                                 -1, numrecs - ptr);
3785                         xfs_btree_log_recs(cur, bp, ptr, numrecs - 1);
3786                 }
3787         }
3788
3789         /*
3790          * Decrement and log the number of entries in the block.
3791          */
3792         xfs_btree_set_numrecs(block, --numrecs);
3793         xfs_btree_log_block(cur, bp, XFS_BB_NUMRECS);
3794
3795         /*
3796          * If we are tracking the last record in the tree and
3797          * we are at the far right edge of the tree, update it.
3798          */
3799         if (xfs_btree_is_lastrec(cur, block, level)) {
3800                 cur->bc_ops->update_lastrec(cur, block, NULL,
3801                                             ptr, LASTREC_DELREC);
3802         }
3803
3804         /*
3805          * We're at the root level.  First, shrink the root block in-memory.
3806          * Try to get rid of the next level down.  If we can't then there's
3807          * nothing left to do.
3808          */
3809         if (level == cur->bc_nlevels - 1) {
3810                 if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) {
3811                         xfs_iroot_realloc(cur->bc_ino.ip, -1,
3812                                           cur->bc_ino.whichfork);
3813
3814                         error = xfs_btree_kill_iroot(cur);
3815                         if (error)
3816                                 goto error0;
3817
3818                         error = xfs_btree_dec_cursor(cur, level, stat);
3819                         if (error)
3820                                 goto error0;
3821                         *stat = 1;
3822                         return 0;
3823                 }
3824
3825                 /*
3826                  * If this is the root level, and there's only one entry left,
3827                  * and it's NOT the leaf level, then we can get rid of this
3828                  * level.
3829                  */
3830                 if (numrecs == 1 && level > 0) {
3831                         union xfs_btree_ptr     *pp;
3832                         /*
3833                          * pp is still set to the first pointer in the block.
3834                          * Make it the new root of the btree.
3835                          */
3836                         pp = xfs_btree_ptr_addr(cur, 1, block);
3837                         error = xfs_btree_kill_root(cur, bp, level, pp);
3838                         if (error)
3839                                 goto error0;
3840                 } else if (level > 0) {
3841                         error = xfs_btree_dec_cursor(cur, level, stat);
3842                         if (error)
3843                                 goto error0;
3844                 }
3845                 *stat = 1;
3846                 return 0;
3847         }
3848
3849         /*
3850          * If we deleted the leftmost entry in the block, update the
3851          * key values above us in the tree.
3852          */
3853         if (xfs_btree_needs_key_update(cur, ptr)) {
3854                 error = xfs_btree_update_keys(cur, level);
3855                 if (error)
3856                         goto error0;
3857         }
3858
3859         /*
3860          * If the number of records remaining in the block is at least
3861          * the minimum, we're done.
3862          */
3863         if (numrecs >= cur->bc_ops->get_minrecs(cur, level)) {
3864                 error = xfs_btree_dec_cursor(cur, level, stat);
3865                 if (error)
3866                         goto error0;
3867                 return 0;
3868         }
3869
3870         /*
3871          * Otherwise, we have to move some records around to keep the
3872          * tree balanced.  Look at the left and right sibling blocks to
3873          * see if we can re-balance by moving only one record.
3874          */
3875         xfs_btree_get_sibling(cur, block, &rptr, XFS_BB_RIGHTSIB);
3876         xfs_btree_get_sibling(cur, block, &lptr, XFS_BB_LEFTSIB);
3877
3878         if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) {
3879                 /*
3880                  * One child of root, need to get a chance to copy its contents
3881                  * into the root and delete it. Can't go up to next level,
3882                  * there's nothing to delete there.
3883                  */
3884                 if (xfs_btree_ptr_is_null(cur, &rptr) &&
3885                     xfs_btree_ptr_is_null(cur, &lptr) &&
3886                     level == cur->bc_nlevels - 2) {
3887                         error = xfs_btree_kill_iroot(cur);
3888                         if (!error)
3889                                 error = xfs_btree_dec_cursor(cur, level, stat);
3890                         if (error)
3891                                 goto error0;
3892                         return 0;
3893                 }
3894         }
3895
3896         ASSERT(!xfs_btree_ptr_is_null(cur, &rptr) ||
3897                !xfs_btree_ptr_is_null(cur, &lptr));
3898
3899         /*
3900          * Duplicate the cursor so our btree manipulations here won't
3901          * disrupt the next level up.
3902          */
3903         error = xfs_btree_dup_cursor(cur, &tcur);
3904         if (error)
3905                 goto error0;
3906
3907         /*
3908          * If there's a right sibling, see if it's ok to shift an entry
3909          * out of it.
3910          */
3911         if (!xfs_btree_ptr_is_null(cur, &rptr)) {
3912                 /*
3913                  * Move the temp cursor to the last entry in the next block.
3914                  * Actually any entry but the first would suffice.
3915                  */
3916                 i = xfs_btree_lastrec(tcur, level);
3917                 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) {
3918                         error = -EFSCORRUPTED;
3919                         goto error0;
3920                 }
3921
3922                 error = xfs_btree_increment(tcur, level, &i);
3923                 if (error)
3924                         goto error0;
3925                 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) {
3926                         error = -EFSCORRUPTED;
3927                         goto error0;
3928                 }
3929
3930                 i = xfs_btree_lastrec(tcur, level);
3931                 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) {
3932                         error = -EFSCORRUPTED;
3933                         goto error0;
3934                 }
3935
3936                 /* Grab a pointer to the block. */
3937                 right = xfs_btree_get_block(tcur, level, &rbp);
3938 #ifdef DEBUG
3939                 error = xfs_btree_check_block(tcur, right, level, rbp);
3940                 if (error)
3941                         goto error0;
3942 #endif
3943                 /* Grab the current block number, for future use. */
3944                 xfs_btree_get_sibling(tcur, right, &cptr, XFS_BB_LEFTSIB);
3945
3946                 /*
3947                  * If right block is full enough so that removing one entry
3948                  * won't make it too empty, and left-shifting an entry out
3949                  * of right to us works, we're done.
3950                  */
3951                 if (xfs_btree_get_numrecs(right) - 1 >=
3952                     cur->bc_ops->get_minrecs(tcur, level)) {
3953                         error = xfs_btree_lshift(tcur, level, &i);
3954                         if (error)
3955                                 goto error0;
3956                         if (i) {
3957                                 ASSERT(xfs_btree_get_numrecs(block) >=
3958                                        cur->bc_ops->get_minrecs(tcur, level));
3959
3960                                 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
3961                                 tcur = NULL;
3962
3963                                 error = xfs_btree_dec_cursor(cur, level, stat);
3964                                 if (error)
3965                                         goto error0;
3966                                 return 0;
3967                         }
3968                 }
3969
3970                 /*
3971                  * Otherwise, grab the number of records in right for
3972                  * future reference, and fix up the temp cursor to point
3973                  * to our block again (last record).
3974                  */
3975                 rrecs = xfs_btree_get_numrecs(right);
3976                 if (!xfs_btree_ptr_is_null(cur, &lptr)) {
3977                         i = xfs_btree_firstrec(tcur, level);
3978                         if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) {
3979                                 error = -EFSCORRUPTED;
3980                                 goto error0;
3981                         }
3982
3983                         error = xfs_btree_decrement(tcur, level, &i);
3984                         if (error)
3985                                 goto error0;
3986                         if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) {
3987                                 error = -EFSCORRUPTED;
3988                                 goto error0;
3989                         }
3990                 }
3991         }
3992
3993         /*
3994          * If there's a left sibling, see if it's ok to shift an entry
3995          * out of it.
3996          */
3997         if (!xfs_btree_ptr_is_null(cur, &lptr)) {
3998                 /*
3999                  * Move the temp cursor to the first entry in the
4000                  * previous block.
4001                  */
4002                 i = xfs_btree_firstrec(tcur, level);
4003                 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) {
4004                         error = -EFSCORRUPTED;
4005                         goto error0;
4006                 }
4007
4008                 error = xfs_btree_decrement(tcur, level, &i);
4009                 if (error)
4010                         goto error0;
4011                 i = xfs_btree_firstrec(tcur, level);
4012                 if (XFS_IS_CORRUPT(cur->bc_mp, i != 1)) {
4013                         error = -EFSCORRUPTED;
4014                         goto error0;
4015                 }
4016
4017                 /* Grab a pointer to the block. */
4018                 left = xfs_btree_get_block(tcur, level, &lbp);
4019 #ifdef DEBUG
4020                 error = xfs_btree_check_block(cur, left, level, lbp);
4021                 if (error)
4022                         goto error0;
4023 #endif
4024                 /* Grab the current block number, for future use. */
4025                 xfs_btree_get_sibling(tcur, left, &cptr, XFS_BB_RIGHTSIB);
4026
4027                 /*
4028                  * If left block is full enough so that removing one entry
4029                  * won't make it too empty, and right-shifting an entry out
4030                  * of left to us works, we're done.
4031                  */
4032                 if (xfs_btree_get_numrecs(left) - 1 >=
4033                     cur->bc_ops->get_minrecs(tcur, level)) {
4034                         error = xfs_btree_rshift(tcur, level, &i);
4035                         if (error)
4036                                 goto error0;
4037                         if (i) {
4038                                 ASSERT(xfs_btree_get_numrecs(block) >=
4039                                        cur->bc_ops->get_minrecs(tcur, level));
4040                                 xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
4041                                 tcur = NULL;
4042                                 if (level == 0)
4043                                         cur->bc_ptrs[0]++;
4044
4045                                 *stat = 1;
4046                                 return 0;
4047                         }
4048                 }
4049
4050                 /*
4051                  * Otherwise, grab the number of records in right for
4052                  * future reference.
4053                  */
4054                 lrecs = xfs_btree_get_numrecs(left);
4055         }
4056
4057         /* Delete the temp cursor, we're done with it. */
4058         xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
4059         tcur = NULL;
4060
4061         /* If here, we need to do a join to keep the tree balanced. */
4062         ASSERT(!xfs_btree_ptr_is_null(cur, &cptr));
4063
4064         if (!xfs_btree_ptr_is_null(cur, &lptr) &&
4065             lrecs + xfs_btree_get_numrecs(block) <=
4066                         cur->bc_ops->get_maxrecs(cur, level)) {
4067                 /*
4068                  * Set "right" to be the starting block,
4069                  * "left" to be the left neighbor.
4070                  */
4071                 rptr = cptr;
4072                 right = block;
4073                 rbp = bp;
4074                 error = xfs_btree_read_buf_block(cur, &lptr, 0, &left, &lbp);
4075                 if (error)
4076                         goto error0;
4077
4078         /*
4079          * If that won't work, see if we can join with the right neighbor block.
4080          */
4081         } else if (!xfs_btree_ptr_is_null(cur, &rptr) &&
4082                    rrecs + xfs_btree_get_numrecs(block) <=
4083                         cur->bc_ops->get_maxrecs(cur, level)) {
4084                 /*
4085                  * Set "left" to be the starting block,
4086                  * "right" to be the right neighbor.
4087                  */
4088                 lptr = cptr;
4089                 left = block;
4090                 lbp = bp;
4091                 error = xfs_btree_read_buf_block(cur, &rptr, 0, &right, &rbp);
4092                 if (error)
4093                         goto error0;
4094
4095         /*
4096          * Otherwise, we can't fix the imbalance.
4097          * Just return.  This is probably a logic error, but it's not fatal.
4098          */
4099         } else {
4100                 error = xfs_btree_dec_cursor(cur, level, stat);
4101                 if (error)
4102                         goto error0;
4103                 return 0;
4104         }
4105
4106         rrecs = xfs_btree_get_numrecs(right);
4107         lrecs = xfs_btree_get_numrecs(left);
4108
4109         /*
4110          * We're now going to join "left" and "right" by moving all the stuff
4111          * in "right" to "left" and deleting "right".
4112          */
4113         XFS_BTREE_STATS_ADD(cur, moves, rrecs);
4114         if (level > 0) {
4115                 /* It's a non-leaf.  Move keys and pointers. */
4116                 union xfs_btree_key     *lkp;   /* left btree key */
4117                 union xfs_btree_ptr     *lpp;   /* left address pointer */
4118                 union xfs_btree_key     *rkp;   /* right btree key */
4119                 union xfs_btree_ptr     *rpp;   /* right address pointer */
4120
4121                 lkp = xfs_btree_key_addr(cur, lrecs + 1, left);
4122                 lpp = xfs_btree_ptr_addr(cur, lrecs + 1, left);
4123                 rkp = xfs_btree_key_addr(cur, 1, right);
4124                 rpp = xfs_btree_ptr_addr(cur, 1, right);
4125
4126                 for (i = 1; i < rrecs; i++) {
4127                         error = xfs_btree_debug_check_ptr(cur, rpp, i, level);
4128                         if (error)
4129                                 goto error0;
4130                 }
4131
4132                 xfs_btree_copy_keys(cur, lkp, rkp, rrecs);
4133                 xfs_btree_copy_ptrs(cur, lpp, rpp, rrecs);
4134
4135                 xfs_btree_log_keys(cur, lbp, lrecs + 1, lrecs + rrecs);
4136                 xfs_btree_log_ptrs(cur, lbp, lrecs + 1, lrecs + rrecs);
4137         } else {
4138                 /* It's a leaf.  Move records.  */
4139                 union xfs_btree_rec     *lrp;   /* left record pointer */
4140                 union xfs_btree_rec     *rrp;   /* right record pointer */
4141
4142                 lrp = xfs_btree_rec_addr(cur, lrecs + 1, left);
4143                 rrp = xfs_btree_rec_addr(cur, 1, right);
4144
4145                 xfs_btree_copy_recs(cur, lrp, rrp, rrecs);
4146                 xfs_btree_log_recs(cur, lbp, lrecs + 1, lrecs + rrecs);
4147         }
4148
4149         XFS_BTREE_STATS_INC(cur, join);
4150
4151         /*
4152          * Fix up the number of records and right block pointer in the
4153          * surviving block, and log it.
4154          */
4155         xfs_btree_set_numrecs(left, lrecs + rrecs);
4156         xfs_btree_get_sibling(cur, right, &cptr, XFS_BB_RIGHTSIB);
4157         xfs_btree_set_sibling(cur, left, &cptr, XFS_BB_RIGHTSIB);
4158         xfs_btree_log_block(cur, lbp, XFS_BB_NUMRECS | XFS_BB_RIGHTSIB);
4159
4160         /* If there is a right sibling, point it to the remaining block. */
4161         xfs_btree_get_sibling(cur, left, &cptr, XFS_BB_RIGHTSIB);
4162         if (!xfs_btree_ptr_is_null(cur, &cptr)) {
4163                 error = xfs_btree_read_buf_block(cur, &cptr, 0, &rrblock, &rrbp);
4164                 if (error)
4165                         goto error0;
4166                 xfs_btree_set_sibling(cur, rrblock, &lptr, XFS_BB_LEFTSIB);
4167                 xfs_btree_log_block(cur, rrbp, XFS_BB_LEFTSIB);
4168         }
4169
4170         /* Free the deleted block. */
4171         error = xfs_btree_free_block(cur, rbp);
4172         if (error)
4173                 goto error0;
4174
4175         /*
4176          * If we joined with the left neighbor, set the buffer in the
4177          * cursor to the left block, and fix up the index.
4178          */
4179         if (bp != lbp) {
4180                 cur->bc_bufs[level] = lbp;
4181                 cur->bc_ptrs[level] += lrecs;
4182                 cur->bc_ra[level] = 0;
4183         }
4184         /*
4185          * If we joined with the right neighbor and there's a level above
4186          * us, increment the cursor at that level.
4187          */
4188         else if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) ||
4189                    (level + 1 < cur->bc_nlevels)) {
4190                 error = xfs_btree_increment(cur, level + 1, &i);
4191                 if (error)
4192                         goto error0;
4193         }
4194
4195         /*
4196          * Readjust the ptr at this level if it's not a leaf, since it's
4197          * still pointing at the deletion point, which makes the cursor
4198          * inconsistent.  If this makes the ptr 0, the caller fixes it up.
4199          * We can't use decrement because it would change the next level up.
4200          */
4201         if (level > 0)
4202                 cur->bc_ptrs[level]--;
4203
4204         /*
4205          * We combined blocks, so we have to update the parent keys if the
4206          * btree supports overlapped intervals.  However, bc_ptrs[level + 1]
4207          * points to the old block so that the caller knows which record to
4208          * delete.  Therefore, the caller must be savvy enough to call updkeys
4209          * for us if we return stat == 2.  The other exit points from this
4210          * function don't require deletions further up the tree, so they can
4211          * call updkeys directly.
4212          */
4213
4214         /* Return value means the next level up has something to do. */
4215         *stat = 2;
4216         return 0;
4217
4218 error0:
4219         if (tcur)
4220                 xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
4221         return error;
4222 }
4223
4224 /*
4225  * Delete the record pointed to by cur.
4226  * The cursor refers to the place where the record was (could be inserted)
4227  * when the operation returns.
4228  */
4229 int                                     /* error */
4230 xfs_btree_delete(
4231         struct xfs_btree_cur    *cur,
4232         int                     *stat)  /* success/failure */
4233 {
4234         int                     error;  /* error return value */
4235         int                     level;
4236         int                     i;
4237         bool                    joined = false;
4238
4239         /*
4240          * Go up the tree, starting at leaf level.
4241          *
4242          * If 2 is returned then a join was done; go to the next level.
4243          * Otherwise we are done.
4244          */
4245         for (level = 0, i = 2; i == 2; level++) {
4246                 error = xfs_btree_delrec(cur, level, &i);
4247                 if (error)
4248                         goto error0;
4249                 if (i == 2)
4250                         joined = true;
4251         }
4252
4253         /*
4254          * If we combined blocks as part of deleting the record, delrec won't
4255          * have updated the parent high keys so we have to do that here.
4256          */
4257         if (joined && (cur->bc_flags & XFS_BTREE_OVERLAPPING)) {
4258                 error = xfs_btree_updkeys_force(cur, 0);
4259                 if (error)
4260                         goto error0;
4261         }
4262
4263         if (i == 0) {
4264                 for (level = 1; level < cur->bc_nlevels; level++) {
4265                         if (cur->bc_ptrs[level] == 0) {
4266                                 error = xfs_btree_decrement(cur, level, &i);
4267                                 if (error)
4268                                         goto error0;
4269                                 break;
4270                         }
4271                 }
4272         }
4273
4274         *stat = i;
4275         return 0;
4276 error0:
4277         return error;
4278 }
4279
4280 /*
4281  * Get the data from the pointed-to record.
4282  */
4283 int                                     /* error */
4284 xfs_btree_get_rec(
4285         struct xfs_btree_cur    *cur,   /* btree cursor */
4286         union xfs_btree_rec     **recp, /* output: btree record */
4287         int                     *stat)  /* output: success/failure */
4288 {
4289         struct xfs_btree_block  *block; /* btree block */
4290         struct xfs_buf          *bp;    /* buffer pointer */
4291         int                     ptr;    /* record number */
4292 #ifdef DEBUG
4293         int                     error;  /* error return value */
4294 #endif
4295
4296         ptr = cur->bc_ptrs[0];
4297         block = xfs_btree_get_block(cur, 0, &bp);
4298
4299 #ifdef DEBUG
4300         error = xfs_btree_check_block(cur, block, 0, bp);
4301         if (error)
4302                 return error;
4303 #endif
4304
4305         /*
4306          * Off the right end or left end, return failure.
4307          */
4308         if (ptr > xfs_btree_get_numrecs(block) || ptr <= 0) {
4309                 *stat = 0;
4310                 return 0;
4311         }
4312
4313         /*
4314          * Point to the record and extract its data.
4315          */
4316         *recp = xfs_btree_rec_addr(cur, ptr, block);
4317         *stat = 1;
4318         return 0;
4319 }
4320
4321 /* Visit a block in a btree. */
4322 STATIC int
4323 xfs_btree_visit_block(
4324         struct xfs_btree_cur            *cur,
4325         int                             level,
4326         xfs_btree_visit_blocks_fn       fn,
4327         void                            *data)
4328 {
4329         struct xfs_btree_block          *block;
4330         struct xfs_buf                  *bp;
4331         union xfs_btree_ptr             rptr;
4332         int                             error;
4333
4334         /* do right sibling readahead */
4335         xfs_btree_readahead(cur, level, XFS_BTCUR_RIGHTRA);
4336         block = xfs_btree_get_block(cur, level, &bp);
4337
4338         /* process the block */
4339         error = fn(cur, level, data);
4340         if (error)
4341                 return error;
4342
4343         /* now read rh sibling block for next iteration */
4344         xfs_btree_get_sibling(cur, block, &rptr, XFS_BB_RIGHTSIB);
4345         if (xfs_btree_ptr_is_null(cur, &rptr))
4346                 return -ENOENT;
4347
4348         /*
4349          * We only visit blocks once in this walk, so we have to avoid the
4350          * internal xfs_btree_lookup_get_block() optimisation where it will
4351          * return the same block without checking if the right sibling points
4352          * back to us and creates a cyclic reference in the btree.
4353          */
4354         if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
4355                 if (be64_to_cpu(rptr.l) == XFS_DADDR_TO_FSB(cur->bc_mp,
4356                                                         xfs_buf_daddr(bp)))
4357                         return -EFSCORRUPTED;
4358         } else {
4359                 if (be32_to_cpu(rptr.s) == xfs_daddr_to_agbno(cur->bc_mp,
4360                                                         xfs_buf_daddr(bp)))
4361                         return -EFSCORRUPTED;
4362         }
4363         return xfs_btree_lookup_get_block(cur, level, &rptr, &block);
4364 }
4365
4366
4367 /* Visit every block in a btree. */
4368 int
4369 xfs_btree_visit_blocks(
4370         struct xfs_btree_cur            *cur,
4371         xfs_btree_visit_blocks_fn       fn,
4372         unsigned int                    flags,
4373         void                            *data)
4374 {
4375         union xfs_btree_ptr             lptr;
4376         int                             level;
4377         struct xfs_btree_block          *block = NULL;
4378         int                             error = 0;
4379
4380         cur->bc_ops->init_ptr_from_cur(cur, &lptr);
4381
4382         /* for each level */
4383         for (level = cur->bc_nlevels - 1; level >= 0; level--) {
4384                 /* grab the left hand block */
4385                 error = xfs_btree_lookup_get_block(cur, level, &lptr, &block);
4386                 if (error)
4387                         return error;
4388
4389                 /* readahead the left most block for the next level down */
4390                 if (level > 0) {
4391                         union xfs_btree_ptr     *ptr;
4392
4393                         ptr = xfs_btree_ptr_addr(cur, 1, block);
4394                         xfs_btree_readahead_ptr(cur, ptr, 1);
4395
4396                         /* save for the next iteration of the loop */
4397                         xfs_btree_copy_ptrs(cur, &lptr, ptr, 1);
4398
4399                         if (!(flags & XFS_BTREE_VISIT_LEAVES))
4400                                 continue;
4401                 } else if (!(flags & XFS_BTREE_VISIT_RECORDS)) {
4402                         continue;
4403                 }
4404
4405                 /* for each buffer in the level */
4406                 do {
4407                         error = xfs_btree_visit_block(cur, level, fn, data);
4408                 } while (!error);
4409
4410                 if (error != -ENOENT)
4411                         return error;
4412         }
4413
4414         return 0;
4415 }
4416
4417 /*
4418  * Change the owner of a btree.
4419  *
4420  * The mechanism we use here is ordered buffer logging. Because we don't know
4421  * how many buffers were are going to need to modify, we don't really want to
4422  * have to make transaction reservations for the worst case of every buffer in a
4423  * full size btree as that may be more space that we can fit in the log....
4424  *
4425  * We do the btree walk in the most optimal manner possible - we have sibling
4426  * pointers so we can just walk all the blocks on each level from left to right
4427  * in a single pass, and then move to the next level and do the same. We can
4428  * also do readahead on the sibling pointers to get IO moving more quickly,
4429  * though for slow disks this is unlikely to make much difference to performance
4430  * as the amount of CPU work we have to do before moving to the next block is
4431  * relatively small.
4432  *
4433  * For each btree block that we load, modify the owner appropriately, set the
4434  * buffer as an ordered buffer and log it appropriately. We need to ensure that
4435  * we mark the region we change dirty so that if the buffer is relogged in
4436  * a subsequent transaction the changes we make here as an ordered buffer are
4437  * correctly relogged in that transaction.  If we are in recovery context, then
4438  * just queue the modified buffer as delayed write buffer so the transaction
4439  * recovery completion writes the changes to disk.
4440  */
4441 struct xfs_btree_block_change_owner_info {
4442         uint64_t                new_owner;
4443         struct list_head        *buffer_list;
4444 };
4445
4446 static int
4447 xfs_btree_block_change_owner(
4448         struct xfs_btree_cur    *cur,
4449         int                     level,
4450         void                    *data)
4451 {
4452         struct xfs_btree_block_change_owner_info        *bbcoi = data;
4453         struct xfs_btree_block  *block;
4454         struct xfs_buf          *bp;
4455
4456         /* modify the owner */
4457         block = xfs_btree_get_block(cur, level, &bp);
4458         if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
4459                 if (block->bb_u.l.bb_owner == cpu_to_be64(bbcoi->new_owner))
4460                         return 0;
4461                 block->bb_u.l.bb_owner = cpu_to_be64(bbcoi->new_owner);
4462         } else {
4463                 if (block->bb_u.s.bb_owner == cpu_to_be32(bbcoi->new_owner))
4464                         return 0;
4465                 block->bb_u.s.bb_owner = cpu_to_be32(bbcoi->new_owner);
4466         }
4467
4468         /*
4469          * If the block is a root block hosted in an inode, we might not have a
4470          * buffer pointer here and we shouldn't attempt to log the change as the
4471          * information is already held in the inode and discarded when the root
4472          * block is formatted into the on-disk inode fork. We still change it,
4473          * though, so everything is consistent in memory.
4474          */
4475         if (!bp) {
4476                 ASSERT(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE);
4477                 ASSERT(level == cur->bc_nlevels - 1);
4478                 return 0;
4479         }
4480
4481         if (cur->bc_tp) {
4482                 if (!xfs_trans_ordered_buf(cur->bc_tp, bp)) {
4483                         xfs_btree_log_block(cur, bp, XFS_BB_OWNER);
4484                         return -EAGAIN;
4485                 }
4486         } else {
4487                 xfs_buf_delwri_queue(bp, bbcoi->buffer_list);
4488         }
4489
4490         return 0;
4491 }
4492
4493 int
4494 xfs_btree_change_owner(
4495         struct xfs_btree_cur    *cur,
4496         uint64_t                new_owner,
4497         struct list_head        *buffer_list)
4498 {
4499         struct xfs_btree_block_change_owner_info        bbcoi;
4500
4501         bbcoi.new_owner = new_owner;
4502         bbcoi.buffer_list = buffer_list;
4503
4504         return xfs_btree_visit_blocks(cur, xfs_btree_block_change_owner,
4505                         XFS_BTREE_VISIT_ALL, &bbcoi);
4506 }
4507
4508 /* Verify the v5 fields of a long-format btree block. */
4509 xfs_failaddr_t
4510 xfs_btree_lblock_v5hdr_verify(
4511         struct xfs_buf          *bp,
4512         uint64_t                owner)
4513 {
4514         struct xfs_mount        *mp = bp->b_mount;
4515         struct xfs_btree_block  *block = XFS_BUF_TO_BLOCK(bp);
4516
4517         if (!xfs_has_crc(mp))
4518                 return __this_address;
4519         if (!uuid_equal(&block->bb_u.l.bb_uuid, &mp->m_sb.sb_meta_uuid))
4520                 return __this_address;
4521         if (block->bb_u.l.bb_blkno != cpu_to_be64(xfs_buf_daddr(bp)))
4522                 return __this_address;
4523         if (owner != XFS_RMAP_OWN_UNKNOWN &&
4524             be64_to_cpu(block->bb_u.l.bb_owner) != owner)
4525                 return __this_address;
4526         return NULL;
4527 }
4528
4529 /* Verify a long-format btree block. */
4530 xfs_failaddr_t
4531 xfs_btree_lblock_verify(
4532         struct xfs_buf          *bp,
4533         unsigned int            max_recs)
4534 {
4535         struct xfs_mount        *mp = bp->b_mount;
4536         struct xfs_btree_block  *block = XFS_BUF_TO_BLOCK(bp);
4537         xfs_fsblock_t           fsb;
4538         xfs_failaddr_t          fa;
4539
4540         /* numrecs verification */
4541         if (be16_to_cpu(block->bb_numrecs) > max_recs)
4542                 return __this_address;
4543
4544         /* sibling pointer verification */
4545         fsb = XFS_DADDR_TO_FSB(mp, xfs_buf_daddr(bp));
4546         fa = xfs_btree_check_lblock_siblings(mp, NULL, -1, fsb,
4547                         block->bb_u.l.bb_leftsib);
4548         if (!fa)
4549                 fa = xfs_btree_check_lblock_siblings(mp, NULL, -1, fsb,
4550                                 block->bb_u.l.bb_rightsib);
4551         return fa;
4552 }
4553
4554 /**
4555  * xfs_btree_sblock_v5hdr_verify() -- verify the v5 fields of a short-format
4556  *                                    btree block
4557  *
4558  * @bp: buffer containing the btree block
4559  */
4560 xfs_failaddr_t
4561 xfs_btree_sblock_v5hdr_verify(
4562         struct xfs_buf          *bp)
4563 {
4564         struct xfs_mount        *mp = bp->b_mount;
4565         struct xfs_btree_block  *block = XFS_BUF_TO_BLOCK(bp);
4566         struct xfs_perag        *pag = bp->b_pag;
4567
4568         if (!xfs_has_crc(mp))
4569                 return __this_address;
4570         if (!uuid_equal(&block->bb_u.s.bb_uuid, &mp->m_sb.sb_meta_uuid))
4571                 return __this_address;
4572         if (block->bb_u.s.bb_blkno != cpu_to_be64(xfs_buf_daddr(bp)))
4573                 return __this_address;
4574         if (pag && be32_to_cpu(block->bb_u.s.bb_owner) != pag->pag_agno)
4575                 return __this_address;
4576         return NULL;
4577 }
4578
4579 /**
4580  * xfs_btree_sblock_verify() -- verify a short-format btree block
4581  *
4582  * @bp: buffer containing the btree block
4583  * @max_recs: maximum records allowed in this btree node
4584  */
4585 xfs_failaddr_t
4586 xfs_btree_sblock_verify(
4587         struct xfs_buf          *bp,
4588         unsigned int            max_recs)
4589 {
4590         struct xfs_mount        *mp = bp->b_mount;
4591         struct xfs_btree_block  *block = XFS_BUF_TO_BLOCK(bp);
4592         xfs_agnumber_t          agno;
4593         xfs_agblock_t           agbno;
4594         xfs_failaddr_t          fa;
4595
4596         /* numrecs verification */
4597         if (be16_to_cpu(block->bb_numrecs) > max_recs)
4598                 return __this_address;
4599
4600         /* sibling pointer verification */
4601         agno = xfs_daddr_to_agno(mp, xfs_buf_daddr(bp));
4602         agbno = xfs_daddr_to_agbno(mp, xfs_buf_daddr(bp));
4603         fa = xfs_btree_check_sblock_siblings(mp, NULL, -1, agno, agbno,
4604                         block->bb_u.s.bb_leftsib);
4605         if (!fa)
4606                 fa = xfs_btree_check_sblock_siblings(mp, NULL, -1, agno, agbno,
4607                                 block->bb_u.s.bb_rightsib);
4608         return fa;
4609 }
4610
4611 /*
4612  * Calculate the number of btree levels needed to store a given number of
4613  * records in a short-format btree.
4614  */
4615 uint
4616 xfs_btree_compute_maxlevels(
4617         uint                    *limits,
4618         unsigned long           len)
4619 {
4620         uint                    level;
4621         unsigned long           maxblocks;
4622
4623         maxblocks = (len + limits[0] - 1) / limits[0];
4624         for (level = 1; maxblocks > 1; level++)
4625                 maxblocks = (maxblocks + limits[1] - 1) / limits[1];
4626         return level;
4627 }
4628
4629 /*
4630  * Query a regular btree for all records overlapping a given interval.
4631  * Start with a LE lookup of the key of low_rec and return all records
4632  * until we find a record with a key greater than the key of high_rec.
4633  */
4634 STATIC int
4635 xfs_btree_simple_query_range(
4636         struct xfs_btree_cur            *cur,
4637         const union xfs_btree_key       *low_key,
4638         const union xfs_btree_key       *high_key,
4639         xfs_btree_query_range_fn        fn,
4640         void                            *priv)
4641 {
4642         union xfs_btree_rec             *recp;
4643         union xfs_btree_key             rec_key;
4644         int64_t                         diff;
4645         int                             stat;
4646         bool                            firstrec = true;
4647         int                             error;
4648
4649         ASSERT(cur->bc_ops->init_high_key_from_rec);
4650         ASSERT(cur->bc_ops->diff_two_keys);
4651
4652         /*
4653          * Find the leftmost record.  The btree cursor must be set
4654          * to the low record used to generate low_key.
4655          */
4656         stat = 0;
4657         error = xfs_btree_lookup(cur, XFS_LOOKUP_LE, &stat);
4658         if (error)
4659                 goto out;
4660
4661         /* Nothing?  See if there's anything to the right. */
4662         if (!stat) {
4663                 error = xfs_btree_increment(cur, 0, &stat);
4664                 if (error)
4665                         goto out;
4666         }
4667
4668         while (stat) {
4669                 /* Find the record. */
4670                 error = xfs_btree_get_rec(cur, &recp, &stat);
4671                 if (error || !stat)
4672                         break;
4673
4674                 /* Skip if high_key(rec) < low_key. */
4675                 if (firstrec) {
4676                         cur->bc_ops->init_high_key_from_rec(&rec_key, recp);
4677                         firstrec = false;
4678                         diff = cur->bc_ops->diff_two_keys(cur, low_key,
4679                                         &rec_key);
4680                         if (diff > 0)
4681                                 goto advloop;
4682                 }
4683
4684                 /* Stop if high_key < low_key(rec). */
4685                 cur->bc_ops->init_key_from_rec(&rec_key, recp);
4686                 diff = cur->bc_ops->diff_two_keys(cur, &rec_key, high_key);
4687                 if (diff > 0)
4688                         break;
4689
4690                 /* Callback */
4691                 error = fn(cur, recp, priv);
4692                 if (error)
4693                         break;
4694
4695 advloop:
4696                 /* Move on to the next record. */
4697                 error = xfs_btree_increment(cur, 0, &stat);
4698                 if (error)
4699                         break;
4700         }
4701
4702 out:
4703         return error;
4704 }
4705
4706 /*
4707  * Query an overlapped interval btree for all records overlapping a given
4708  * interval.  This function roughly follows the algorithm given in
4709  * "Interval Trees" of _Introduction to Algorithms_, which is section
4710  * 14.3 in the 2nd and 3rd editions.
4711  *
4712  * First, generate keys for the low and high records passed in.
4713  *
4714  * For any leaf node, generate the high and low keys for the record.
4715  * If the record keys overlap with the query low/high keys, pass the
4716  * record to the function iterator.
4717  *
4718  * For any internal node, compare the low and high keys of each
4719  * pointer against the query low/high keys.  If there's an overlap,
4720  * follow the pointer.
4721  *
4722  * As an optimization, we stop scanning a block when we find a low key
4723  * that is greater than the query's high key.
4724  */
4725 STATIC int
4726 xfs_btree_overlapped_query_range(
4727         struct xfs_btree_cur            *cur,
4728         const union xfs_btree_key       *low_key,
4729         const union xfs_btree_key       *high_key,
4730         xfs_btree_query_range_fn        fn,
4731         void                            *priv)
4732 {
4733         union xfs_btree_ptr             ptr;
4734         union xfs_btree_ptr             *pp;
4735         union xfs_btree_key             rec_key;
4736         union xfs_btree_key             rec_hkey;
4737         union xfs_btree_key             *lkp;
4738         union xfs_btree_key             *hkp;
4739         union xfs_btree_rec             *recp;
4740         struct xfs_btree_block          *block;
4741         int64_t                         ldiff;
4742         int64_t                         hdiff;
4743         int                             level;
4744         struct xfs_buf                  *bp;
4745         int                             i;
4746         int                             error;
4747
4748         /* Load the root of the btree. */
4749         level = cur->bc_nlevels - 1;
4750         cur->bc_ops->init_ptr_from_cur(cur, &ptr);
4751         error = xfs_btree_lookup_get_block(cur, level, &ptr, &block);
4752         if (error)
4753                 return error;
4754         xfs_btree_get_block(cur, level, &bp);
4755         trace_xfs_btree_overlapped_query_range(cur, level, bp);
4756 #ifdef DEBUG
4757         error = xfs_btree_check_block(cur, block, level, bp);
4758         if (error)
4759                 goto out;
4760 #endif
4761         cur->bc_ptrs[level] = 1;
4762
4763         while (level < cur->bc_nlevels) {
4764                 block = xfs_btree_get_block(cur, level, &bp);
4765
4766                 /* End of node, pop back towards the root. */
4767                 if (cur->bc_ptrs[level] > be16_to_cpu(block->bb_numrecs)) {
4768 pop_up:
4769                         if (level < cur->bc_nlevels - 1)
4770                                 cur->bc_ptrs[level + 1]++;
4771                         level++;
4772                         continue;
4773                 }
4774
4775                 if (level == 0) {
4776                         /* Handle a leaf node. */
4777                         recp = xfs_btree_rec_addr(cur, cur->bc_ptrs[0], block);
4778
4779                         cur->bc_ops->init_high_key_from_rec(&rec_hkey, recp);
4780                         ldiff = cur->bc_ops->diff_two_keys(cur, &rec_hkey,
4781                                         low_key);
4782
4783                         cur->bc_ops->init_key_from_rec(&rec_key, recp);
4784                         hdiff = cur->bc_ops->diff_two_keys(cur, high_key,
4785                                         &rec_key);
4786
4787                         /*
4788                          * If (record's high key >= query's low key) and
4789                          *    (query's high key >= record's low key), then
4790                          * this record overlaps the query range; callback.
4791                          */
4792                         if (ldiff >= 0 && hdiff >= 0) {
4793                                 error = fn(cur, recp, priv);
4794                                 if (error)
4795                                         break;
4796                         } else if (hdiff < 0) {
4797                                 /* Record is larger than high key; pop. */
4798                                 goto pop_up;
4799                         }
4800                         cur->bc_ptrs[level]++;
4801                         continue;
4802                 }
4803
4804                 /* Handle an internal node. */
4805                 lkp = xfs_btree_key_addr(cur, cur->bc_ptrs[level], block);
4806                 hkp = xfs_btree_high_key_addr(cur, cur->bc_ptrs[level], block);
4807                 pp = xfs_btree_ptr_addr(cur, cur->bc_ptrs[level], block);
4808
4809                 ldiff = cur->bc_ops->diff_two_keys(cur, hkp, low_key);
4810                 hdiff = cur->bc_ops->diff_two_keys(cur, high_key, lkp);
4811
4812                 /*
4813                  * If (pointer's high key >= query's low key) and
4814                  *    (query's high key >= pointer's low key), then
4815                  * this record overlaps the query range; follow pointer.
4816                  */
4817                 if (ldiff >= 0 && hdiff >= 0) {
4818                         level--;
4819                         error = xfs_btree_lookup_get_block(cur, level, pp,
4820                                         &block);
4821                         if (error)
4822                                 goto out;
4823                         xfs_btree_get_block(cur, level, &bp);
4824                         trace_xfs_btree_overlapped_query_range(cur, level, bp);
4825 #ifdef DEBUG
4826                         error = xfs_btree_check_block(cur, block, level, bp);
4827                         if (error)
4828                                 goto out;
4829 #endif
4830                         cur->bc_ptrs[level] = 1;
4831                         continue;
4832                 } else if (hdiff < 0) {
4833                         /* The low key is larger than the upper range; pop. */
4834                         goto pop_up;
4835                 }
4836                 cur->bc_ptrs[level]++;
4837         }
4838
4839 out:
4840         /*
4841          * If we don't end this function with the cursor pointing at a record
4842          * block, a subsequent non-error cursor deletion will not release
4843          * node-level buffers, causing a buffer leak.  This is quite possible
4844          * with a zero-results range query, so release the buffers if we
4845          * failed to return any results.
4846          */
4847         if (cur->bc_bufs[0] == NULL) {
4848                 for (i = 0; i < cur->bc_nlevels; i++) {
4849                         if (cur->bc_bufs[i]) {
4850                                 xfs_trans_brelse(cur->bc_tp, cur->bc_bufs[i]);
4851                                 cur->bc_bufs[i] = NULL;
4852                                 cur->bc_ptrs[i] = 0;
4853                                 cur->bc_ra[i] = 0;
4854                         }
4855                 }
4856         }
4857
4858         return error;
4859 }
4860
4861 /*
4862  * Query a btree for all records overlapping a given interval of keys.  The
4863  * supplied function will be called with each record found; return one of the
4864  * XFS_BTREE_QUERY_RANGE_{CONTINUE,ABORT} values or the usual negative error
4865  * code.  This function returns -ECANCELED, zero, or a negative error code.
4866  */
4867 int
4868 xfs_btree_query_range(
4869         struct xfs_btree_cur            *cur,
4870         const union xfs_btree_irec      *low_rec,
4871         const union xfs_btree_irec      *high_rec,
4872         xfs_btree_query_range_fn        fn,
4873         void                            *priv)
4874 {
4875         union xfs_btree_rec             rec;
4876         union xfs_btree_key             low_key;
4877         union xfs_btree_key             high_key;
4878
4879         /* Find the keys of both ends of the interval. */
4880         cur->bc_rec = *high_rec;
4881         cur->bc_ops->init_rec_from_cur(cur, &rec);
4882         cur->bc_ops->init_key_from_rec(&high_key, &rec);
4883
4884         cur->bc_rec = *low_rec;
4885         cur->bc_ops->init_rec_from_cur(cur, &rec);
4886         cur->bc_ops->init_key_from_rec(&low_key, &rec);
4887
4888         /* Enforce low key < high key. */
4889         if (cur->bc_ops->diff_two_keys(cur, &low_key, &high_key) > 0)
4890                 return -EINVAL;
4891
4892         if (!(cur->bc_flags & XFS_BTREE_OVERLAPPING))
4893                 return xfs_btree_simple_query_range(cur, &low_key,
4894                                 &high_key, fn, priv);
4895         return xfs_btree_overlapped_query_range(cur, &low_key, &high_key,
4896                         fn, priv);
4897 }
4898
4899 /* Query a btree for all records. */
4900 int
4901 xfs_btree_query_all(
4902         struct xfs_btree_cur            *cur,
4903         xfs_btree_query_range_fn        fn,
4904         void                            *priv)
4905 {
4906         union xfs_btree_key             low_key;
4907         union xfs_btree_key             high_key;
4908
4909         memset(&cur->bc_rec, 0, sizeof(cur->bc_rec));
4910         memset(&low_key, 0, sizeof(low_key));
4911         memset(&high_key, 0xFF, sizeof(high_key));
4912
4913         return xfs_btree_simple_query_range(cur, &low_key, &high_key, fn, priv);
4914 }
4915
4916 /*
4917  * Calculate the number of blocks needed to store a given number of records
4918  * in a short-format (per-AG metadata) btree.
4919  */
4920 unsigned long long
4921 xfs_btree_calc_size(
4922         uint                    *limits,
4923         unsigned long long      len)
4924 {
4925         int                     level;
4926         int                     maxrecs;
4927         unsigned long long      rval;
4928
4929         maxrecs = limits[0];
4930         for (level = 0, rval = 0; len > 1; level++) {
4931                 len += maxrecs - 1;
4932                 do_div(len, maxrecs);
4933                 maxrecs = limits[1];
4934                 rval += len;
4935         }
4936         return rval;
4937 }
4938
4939 static int
4940 xfs_btree_count_blocks_helper(
4941         struct xfs_btree_cur    *cur,
4942         int                     level,
4943         void                    *data)
4944 {
4945         xfs_extlen_t            *blocks = data;
4946         (*blocks)++;
4947
4948         return 0;
4949 }
4950
4951 /* Count the blocks in a btree and return the result in *blocks. */
4952 int
4953 xfs_btree_count_blocks(
4954         struct xfs_btree_cur    *cur,
4955         xfs_extlen_t            *blocks)
4956 {
4957         *blocks = 0;
4958         return xfs_btree_visit_blocks(cur, xfs_btree_count_blocks_helper,
4959                         XFS_BTREE_VISIT_ALL, blocks);
4960 }
4961
4962 /* Compare two btree pointers. */
4963 int64_t
4964 xfs_btree_diff_two_ptrs(
4965         struct xfs_btree_cur            *cur,
4966         const union xfs_btree_ptr       *a,
4967         const union xfs_btree_ptr       *b)
4968 {
4969         if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
4970                 return (int64_t)be64_to_cpu(a->l) - be64_to_cpu(b->l);
4971         return (int64_t)be32_to_cpu(a->s) - be32_to_cpu(b->s);
4972 }
4973
4974 /* If there's an extent, we're done. */
4975 STATIC int
4976 xfs_btree_has_record_helper(
4977         struct xfs_btree_cur            *cur,
4978         const union xfs_btree_rec       *rec,
4979         void                            *priv)
4980 {
4981         return -ECANCELED;
4982 }
4983
4984 /* Is there a record covering a given range of keys? */
4985 int
4986 xfs_btree_has_record(
4987         struct xfs_btree_cur            *cur,
4988         const union xfs_btree_irec      *low,
4989         const union xfs_btree_irec      *high,
4990         bool                            *exists)
4991 {
4992         int                             error;
4993
4994         error = xfs_btree_query_range(cur, low, high,
4995                         &xfs_btree_has_record_helper, NULL);
4996         if (error == -ECANCELED) {
4997                 *exists = true;
4998                 return 0;
4999         }
5000         *exists = false;
5001         return error;
5002 }
5003
5004 /* Are there more records in this btree? */
5005 bool
5006 xfs_btree_has_more_records(
5007         struct xfs_btree_cur    *cur)
5008 {
5009         struct xfs_btree_block  *block;
5010         struct xfs_buf          *bp;
5011
5012         block = xfs_btree_get_block(cur, 0, &bp);
5013
5014         /* There are still records in this block. */
5015         if (cur->bc_ptrs[0] < xfs_btree_get_numrecs(block))
5016                 return true;
5017
5018         /* There are more record blocks. */
5019         if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
5020                 return block->bb_u.l.bb_rightsib != cpu_to_be64(NULLFSBLOCK);
5021         else
5022                 return block->bb_u.s.bb_rightsib != cpu_to_be32(NULLAGBLOCK);
5023 }