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