fs/xfs/xfs_btree.c

   1 /*
   2  * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc.
   3  * All Rights Reserved.
   4  *
   5  * This program is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU General Public License as
   7  * published by the Free Software Foundation.
   8  *
   9  * This program is distributed in the hope that it would be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write the Free Software Foundation,
  16  * Inc.,  51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  17  */
  18 #include "xfs.h"
  19 #include "xfs_fs.h"
  20 #include "xfs_types.h"
  21 #include "xfs_bit.h"
  22 #include "xfs_log.h"
  23 #include "xfs_inum.h"
  24 #include "xfs_trans.h"
  25 #include "xfs_sb.h"
  26 #include "xfs_ag.h"
  27 #include "xfs_dir.h"
  28 #include "xfs_dir2.h"
  29 #include "xfs_dmapi.h"
  30 #include "xfs_mount.h"
  31 #include "xfs_bmap_btree.h"
  32 #include "xfs_alloc_btree.h"
  33 #include "xfs_ialloc_btree.h"
  34 #include "xfs_dir_sf.h"
  35 #include "xfs_dir2_sf.h"
  36 #include "xfs_attr_sf.h"
  37 #include "xfs_dinode.h"
  38 #include "xfs_inode.h"
  39 #include "xfs_btree.h"
  40 #include "xfs_ialloc.h"
  41 #include "xfs_error.h"
  42
  43 /*
  44  * Cursor allocation zone.
  45  */
  46 kmem_zone_t     *xfs_btree_cur_zone;
  47
  48 /*
  49  * Btree magic numbers.
  50  */
  51 const __uint32_t xfs_magics[XFS_BTNUM_MAX] =
  52 {
  53         XFS_ABTB_MAGIC, XFS_ABTC_MAGIC, XFS_BMAP_MAGIC, XFS_IBT_MAGIC
  54 };
  55
  56 /*
  57  * Prototypes for internal routines.
  58  */
  59
  60 /*
  61  * Checking routine: return maxrecs for the block.
  62  */
  63 STATIC int                              /* number of records fitting in block */
  64 xfs_btree_maxrecs(
  65         xfs_btree_cur_t         *cur,   /* btree cursor */
  66         xfs_btree_block_t       *block);/* generic btree block pointer */
  67
  68 /*
  69  * Internal routines.
  70  */
  71
  72 /*
  73  * Retrieve the block pointer from the cursor at the given level.
  74  * This may be a bmap btree root or from a buffer.
  75  */
  76 STATIC xfs_btree_block_t *                      /* generic btree block pointer */
  77 xfs_btree_get_block(
  78         xfs_btree_cur_t         *cur,   /* btree cursor */
  79         int                     level,  /* level in btree */
  80         struct xfs_buf          **bpp); /* buffer containing the block */
  81
  82 /*
  83  * Checking routine: return maxrecs for the block.
  84  */
  85 STATIC int                              /* number of records fitting in block */
  86 xfs_btree_maxrecs(
  87         xfs_btree_cur_t         *cur,   /* btree cursor */
  88         xfs_btree_block_t       *block) /* generic btree block pointer */
  89 {
  90         switch (cur->bc_btnum) {
  91         case XFS_BTNUM_BNO:
  92         case XFS_BTNUM_CNT:
  93                 return (int)XFS_ALLOC_BLOCK_MAXRECS(INT_GET(block->bb_h.bb_level, ARCH_CONVERT), cur);
  94         case XFS_BTNUM_BMAP:
  95                 return (int)XFS_BMAP_BLOCK_IMAXRECS(INT_GET(block->bb_h.bb_level, ARCH_CONVERT), cur);
  96         case XFS_BTNUM_INO:
  97                 return (int)XFS_INOBT_BLOCK_MAXRECS(INT_GET(block->bb_h.bb_level, ARCH_CONVERT), cur);
  98         default:
  99                 ASSERT(0);
 100                 return 0;
 101         }
 102 }
 103
 104 /*
 105  * External routines.
 106  */
 107
 108 #ifdef DEBUG
 109 /*
 110  * Debug routine: check that block header is ok.
 111  */
 112 void
 113 xfs_btree_check_block(
 114         xfs_btree_cur_t         *cur,   /* btree cursor */
 115         xfs_btree_block_t       *block, /* generic btree block pointer */
 116         int                     level,  /* level of the btree block */
 117         xfs_buf_t               *bp)    /* buffer containing block, if any */
 118 {
 119         if (XFS_BTREE_LONG_PTRS(cur->bc_btnum))
 120                 xfs_btree_check_lblock(cur, (xfs_btree_lblock_t *)block, level,
 121                         bp);
 122         else
 123                 xfs_btree_check_sblock(cur, (xfs_btree_sblock_t *)block, level,
 124                         bp);
 125 }
 126
 127 /*
 128  * Debug routine: check that keys are in the right order.
 129  */
 130 void
 131 xfs_btree_check_key(
 132         xfs_btnum_t     btnum,          /* btree identifier */
 133         void            *ak1,           /* pointer to left (lower) key */
 134         void            *ak2)           /* pointer to right (higher) key */
 135 {
 136         switch (btnum) {
 137         case XFS_BTNUM_BNO: {
 138                 xfs_alloc_key_t *k1;
 139                 xfs_alloc_key_t *k2;
 140
 141                 k1 = ak1;
 142                 k2 = ak2;
 143                 ASSERT(INT_GET(k1->ar_startblock, ARCH_CONVERT) < INT_GET(k2->ar_startblock, ARCH_CONVERT));
 144                 break;
 145             }
 146         case XFS_BTNUM_CNT: {
 147                 xfs_alloc_key_t *k1;
 148                 xfs_alloc_key_t *k2;
 149
 150                 k1 = ak1;
 151                 k2 = ak2;
 152                 ASSERT(INT_GET(k1->ar_blockcount, ARCH_CONVERT) < INT_GET(k2->ar_blockcount, ARCH_CONVERT) ||
 153                        (INT_GET(k1->ar_blockcount, ARCH_CONVERT) == INT_GET(k2->ar_blockcount, ARCH_CONVERT) &&
 154                         INT_GET(k1->ar_startblock, ARCH_CONVERT) < INT_GET(k2->ar_startblock, ARCH_CONVERT)));
 155                 break;
 156             }
 157         case XFS_BTNUM_BMAP: {
 158                 xfs_bmbt_key_t  *k1;
 159                 xfs_bmbt_key_t  *k2;
 160
 161                 k1 = ak1;
 162                 k2 = ak2;
 163                 ASSERT(INT_GET(k1->br_startoff, ARCH_CONVERT) < INT_GET(k2->br_startoff, ARCH_CONVERT));
 164                 break;
 165             }
 166         case XFS_BTNUM_INO: {
 167                 xfs_inobt_key_t *k1;
 168                 xfs_inobt_key_t *k2;
 169
 170                 k1 = ak1;
 171                 k2 = ak2;
 172                 ASSERT(INT_GET(k1->ir_startino, ARCH_CONVERT) < INT_GET(k2->ir_startino, ARCH_CONVERT));
 173                 break;
 174             }
 175         default:
 176                 ASSERT(0);
 177         }
 178 }
 179 #endif  /* DEBUG */
 180
 181 /*
 182  * Checking routine: check that long form block header is ok.
 183  */
 184 /* ARGSUSED */
 185 int                                     /* error (0 or EFSCORRUPTED) */
 186 xfs_btree_check_lblock(
 187         xfs_btree_cur_t         *cur,   /* btree cursor */
 188         xfs_btree_lblock_t      *block, /* btree long form block pointer */
 189         int                     level,  /* level of the btree block */
 190         xfs_buf_t               *bp)    /* buffer for block, if any */
 191 {
 192         int                     lblock_ok; /* block passes checks */
 193         xfs_mount_t             *mp;    /* file system mount point */
 194
 195         mp = cur->bc_mp;
 196         lblock_ok =
 197                 INT_GET(block->bb_magic, ARCH_CONVERT) == xfs_magics[cur->bc_btnum] &&
 198                 INT_GET(block->bb_level, ARCH_CONVERT) == level &&
 199                 INT_GET(block->bb_numrecs, ARCH_CONVERT) <=
 200                         xfs_btree_maxrecs(cur, (xfs_btree_block_t *)block) &&
 201                 block->bb_leftsib &&
 202                 (INT_GET(block->bb_leftsib, ARCH_CONVERT) == NULLDFSBNO ||
 203                  XFS_FSB_SANITY_CHECK(mp, INT_GET(block->bb_leftsib, ARCH_CONVERT))) &&
 204                 block->bb_rightsib &&
 205                 (INT_GET(block->bb_rightsib, ARCH_CONVERT) == NULLDFSBNO ||
 206                  XFS_FSB_SANITY_CHECK(mp, INT_GET(block->bb_rightsib, ARCH_CONVERT)));
 207         if (unlikely(XFS_TEST_ERROR(!lblock_ok, mp, XFS_ERRTAG_BTREE_CHECK_LBLOCK,
 208                         XFS_RANDOM_BTREE_CHECK_LBLOCK))) {
 209                 if (bp)
 210                         xfs_buftrace("LBTREE ERROR", bp);
 211                 XFS_ERROR_REPORT("xfs_btree_check_lblock", XFS_ERRLEVEL_LOW,
 212                                  mp);
 213                 return XFS_ERROR(EFSCORRUPTED);
 214         }
 215         return 0;
 216 }
 217
 218 /*
 219  * Checking routine: check that (long) pointer is ok.
 220  */
 221 int                                     /* error (0 or EFSCORRUPTED) */
 222 xfs_btree_check_lptr(
 223         xfs_btree_cur_t *cur,           /* btree cursor */
 224         xfs_dfsbno_t    ptr,            /* btree block disk address */
 225         int             level)          /* btree block level */
 226 {
 227         xfs_mount_t     *mp;            /* file system mount point */
 228
 229         mp = cur->bc_mp;
 230         XFS_WANT_CORRUPTED_RETURN(
 231                 level > 0 &&
 232                 ptr != NULLDFSBNO &&
 233                 XFS_FSB_SANITY_CHECK(mp, ptr));
 234         return 0;
 235 }
 236
 237 #ifdef DEBUG
 238 /*
 239  * Debug routine: check that records are in the right order.
 240  */
 241 void
 242 xfs_btree_check_rec(
 243         xfs_btnum_t     btnum,          /* btree identifier */
 244         void            *ar1,           /* pointer to left (lower) record */
 245         void            *ar2)           /* pointer to right (higher) record */
 246 {
 247         switch (btnum) {
 248         case XFS_BTNUM_BNO: {
 249                 xfs_alloc_rec_t *r1;
 250                 xfs_alloc_rec_t *r2;
 251
 252                 r1 = ar1;
 253                 r2 = ar2;
 254                 ASSERT(INT_GET(r1->ar_startblock, ARCH_CONVERT) + INT_GET(r1->ar_blockcount, ARCH_CONVERT) <=
 255                        INT_GET(r2->ar_startblock, ARCH_CONVERT));
 256                 break;
 257             }
 258         case XFS_BTNUM_CNT: {
 259                 xfs_alloc_rec_t *r1;
 260                 xfs_alloc_rec_t *r2;
 261
 262                 r1 = ar1;
 263                 r2 = ar2;
 264                 ASSERT(INT_GET(r1->ar_blockcount, ARCH_CONVERT) < INT_GET(r2->ar_blockcount, ARCH_CONVERT) ||
 265                        (INT_GET(r1->ar_blockcount, ARCH_CONVERT) == INT_GET(r2->ar_blockcount, ARCH_CONVERT) &&
 266                         INT_GET(r1->ar_startblock, ARCH_CONVERT) < INT_GET(r2->ar_startblock, ARCH_CONVERT)));
 267                 break;
 268             }
 269         case XFS_BTNUM_BMAP: {
 270                 xfs_bmbt_rec_t  *r1;
 271                 xfs_bmbt_rec_t  *r2;
 272
 273                 r1 = ar1;
 274                 r2 = ar2;
 275                 ASSERT(xfs_bmbt_disk_get_startoff(r1) +
 276                        xfs_bmbt_disk_get_blockcount(r1) <=
 277                        xfs_bmbt_disk_get_startoff(r2));
 278                 break;
 279             }
 280         case XFS_BTNUM_INO: {
 281                 xfs_inobt_rec_t *r1;
 282                 xfs_inobt_rec_t *r2;
 283
 284                 r1 = ar1;
 285                 r2 = ar2;
 286                 ASSERT(INT_GET(r1->ir_startino, ARCH_CONVERT) + XFS_INODES_PER_CHUNK <=
 287                        INT_GET(r2->ir_startino, ARCH_CONVERT));
 288                 break;
 289             }
 290         default:
 291                 ASSERT(0);
 292         }
 293 }
 294 #endif  /* DEBUG */
 295
 296 /*
 297  * Checking routine: check that block header is ok.
 298  */
 299 /* ARGSUSED */
 300 int                                     /* error (0 or EFSCORRUPTED) */
 301 xfs_btree_check_sblock(
 302         xfs_btree_cur_t         *cur,   /* btree cursor */
 303         xfs_btree_sblock_t      *block, /* btree short form block pointer */
 304         int                     level,  /* level of the btree block */
 305         xfs_buf_t               *bp)    /* buffer containing block */
 306 {
 307         xfs_buf_t               *agbp;  /* buffer for ag. freespace struct */
 308         xfs_agf_t               *agf;   /* ag. freespace structure */
 309         xfs_agblock_t           agflen; /* native ag. freespace length */
 310         int                     sblock_ok; /* block passes checks */
 311
 312         agbp = cur->bc_private.a.agbp;
 313         agf = XFS_BUF_TO_AGF(agbp);
 314         agflen = INT_GET(agf->agf_length, ARCH_CONVERT);
 315         sblock_ok =
 316                 INT_GET(block->bb_magic, ARCH_CONVERT) == xfs_magics[cur->bc_btnum] &&
 317                 INT_GET(block->bb_level, ARCH_CONVERT) == level &&
 318                 INT_GET(block->bb_numrecs, ARCH_CONVERT) <=
 319                         xfs_btree_maxrecs(cur, (xfs_btree_block_t *)block) &&
 320                 (INT_GET(block->bb_leftsib, ARCH_CONVERT) == NULLAGBLOCK ||
 321                  INT_GET(block->bb_leftsib, ARCH_CONVERT) < agflen) &&
 322                 block->bb_leftsib &&
 323                 (INT_GET(block->bb_rightsib, ARCH_CONVERT) == NULLAGBLOCK ||
 324                  INT_GET(block->bb_rightsib, ARCH_CONVERT) < agflen) &&
 325                 block->bb_rightsib;
 326         if (unlikely(XFS_TEST_ERROR(!sblock_ok, cur->bc_mp,
 327                         XFS_ERRTAG_BTREE_CHECK_SBLOCK,
 328                         XFS_RANDOM_BTREE_CHECK_SBLOCK))) {
 329                 if (bp)
 330                         xfs_buftrace("SBTREE ERROR", bp);
 331                 XFS_ERROR_REPORT("xfs_btree_check_sblock", XFS_ERRLEVEL_LOW,
 332                                  cur->bc_mp);
 333                 return XFS_ERROR(EFSCORRUPTED);
 334         }
 335         return 0;
 336 }
 337
 338 /*
 339  * Checking routine: check that (short) pointer is ok.
 340  */
 341 int                                     /* error (0 or EFSCORRUPTED) */
 342 xfs_btree_check_sptr(
 343         xfs_btree_cur_t *cur,           /* btree cursor */
 344         xfs_agblock_t   ptr,            /* btree block disk address */
 345         int             level)          /* btree block level */
 346 {
 347         xfs_buf_t       *agbp;          /* buffer for ag. freespace struct */
 348         xfs_agf_t       *agf;           /* ag. freespace structure */
 349
 350         agbp = cur->bc_private.a.agbp;
 351         agf = XFS_BUF_TO_AGF(agbp);
 352         XFS_WANT_CORRUPTED_RETURN(
 353                 level > 0 &&
 354                 ptr != NULLAGBLOCK && ptr != 0 &&
 355                 ptr < INT_GET(agf->agf_length, ARCH_CONVERT));
 356         return 0;
 357 }
 358
 359 /*
 360  * Delete the btree cursor.
 361  */
 362 void
 363 xfs_btree_del_cursor(
 364         xfs_btree_cur_t *cur,           /* btree cursor */
 365         int             error)          /* del because of error */
 366 {
 367         int             i;              /* btree level */
 368
 369         /*
 370          * Clear the buffer pointers, and release the buffers.
 371          * If we're doing this in the face of an error, we
 372          * need to make sure to inspect all of the entries
 373          * in the bc_bufs array for buffers to be unlocked.
 374          * This is because some of the btree code works from
 375          * level n down to 0, and if we get an error along
 376          * the way we won't have initialized all the entries
 377          * down to 0.
 378          */
 379         for (i = 0; i < cur->bc_nlevels; i++) {
 380                 if (cur->bc_bufs[i])
 381                         xfs_btree_setbuf(cur, i, NULL);
 382                 else if (!error)
 383                         break;
 384         }
 385         /*
 386          * Can't free a bmap cursor without having dealt with the
 387          * allocated indirect blocks' accounting.
 388          */
 389         ASSERT(cur->bc_btnum != XFS_BTNUM_BMAP ||
 390                cur->bc_private.b.allocated == 0);
 391         /*
 392          * Free the cursor.
 393          */
 394         kmem_zone_free(xfs_btree_cur_zone, cur);
 395 }
 396
 397 /*
 398  * Duplicate the btree cursor.
 399  * Allocate a new one, copy the record, re-get the buffers.
 400  */
 401 int                                     /* error */
 402 xfs_btree_dup_cursor(
 403         xfs_btree_cur_t *cur,           /* input cursor */
 404         xfs_btree_cur_t **ncur)         /* output cursor */
 405 {
 406         xfs_buf_t       *bp;            /* btree block's buffer pointer */
 407         int             error;          /* error return value */
 408         int             i;              /* level number of btree block */
 409         xfs_mount_t     *mp;            /* mount structure for filesystem */
 410         xfs_btree_cur_t *new;           /* new cursor value */
 411         xfs_trans_t     *tp;            /* transaction pointer, can be NULL */
 412
 413         tp = cur->bc_tp;
 414         mp = cur->bc_mp;
 415         /*
 416          * Allocate a new cursor like the old one.
 417          */
 418         new = xfs_btree_init_cursor(mp, tp, cur->bc_private.a.agbp,
 419                 cur->bc_private.a.agno, cur->bc_btnum, cur->bc_private.b.ip,
 420                 cur->bc_private.b.whichfork);
 421         /*
 422          * Copy the record currently in the cursor.
 423          */
 424         new->bc_rec = cur->bc_rec;
 425         /*
 426          * For each level current, re-get the buffer and copy the ptr value.
 427          */
 428         for (i = 0; i < new->bc_nlevels; i++) {
 429                 new->bc_ptrs[i] = cur->bc_ptrs[i];
 430                 new->bc_ra[i] = cur->bc_ra[i];
 431                 if ((bp = cur->bc_bufs[i])) {
 432                         if ((error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp,
 433                                 XFS_BUF_ADDR(bp), mp->m_bsize, 0, &bp))) {
 434                                 xfs_btree_del_cursor(new, error);
 435                                 *ncur = NULL;
 436                                 return error;
 437                         }
 438                         new->bc_bufs[i] = bp;
 439                         ASSERT(bp);
 440                         ASSERT(!XFS_BUF_GETERROR(bp));
 441                 } else
 442                         new->bc_bufs[i] = NULL;
 443         }
 444         /*
 445          * For bmap btrees, copy the firstblock, flist, and flags values,
 446          * since init cursor doesn't get them.
 447          */
 448         if (new->bc_btnum == XFS_BTNUM_BMAP) {
 449                 new->bc_private.b.firstblock = cur->bc_private.b.firstblock;
 450                 new->bc_private.b.flist = cur->bc_private.b.flist;
 451                 new->bc_private.b.flags = cur->bc_private.b.flags;
 452         }
 453         *ncur = new;
 454         return 0;
 455 }
 456
 457 /*
 458  * Change the cursor to point to the first record at the given level.
 459  * Other levels are unaffected.
 460  */
 461 int                                     /* success=1, failure=0 */
 462 xfs_btree_firstrec(
 463         xfs_btree_cur_t         *cur,   /* btree cursor */
 464         int                     level)  /* level to change */
 465 {
 466         xfs_btree_block_t       *block; /* generic btree block pointer */
 467         xfs_buf_t               *bp;    /* buffer containing block */
 468
 469         /*
 470          * Get the block pointer for this level.
 471          */
 472         block = xfs_btree_get_block(cur, level, &bp);
 473         xfs_btree_check_block(cur, block, level, bp);
 474         /*
 475          * It's empty, there is no such record.
 476          */
 477         if (!block->bb_h.bb_numrecs)
 478                 return 0;
 479         /*
 480          * Set the ptr value to 1, that's the first record/key.
 481          */
 482         cur->bc_ptrs[level] = 1;
 483         return 1;
 484 }
 485
 486 /*
 487  * Retrieve the block pointer from the cursor at the given level.
 488  * This may be a bmap btree root or from a buffer.
 489  */
 490 STATIC xfs_btree_block_t *              /* generic btree block pointer */
 491 xfs_btree_get_block(
 492         xfs_btree_cur_t         *cur,   /* btree cursor */
 493         int                     level,  /* level in btree */
 494         xfs_buf_t               **bpp)  /* buffer containing the block */
 495 {
 496         xfs_btree_block_t       *block; /* return value */
 497         xfs_buf_t               *bp;    /* return buffer */
 498         xfs_ifork_t             *ifp;   /* inode fork pointer */
 499         int                     whichfork; /* data or attr fork */
 500
 501         if (cur->bc_btnum == XFS_BTNUM_BMAP && level == cur->bc_nlevels - 1) {
 502                 whichfork = cur->bc_private.b.whichfork;
 503                 ifp = XFS_IFORK_PTR(cur->bc_private.b.ip, whichfork);
 504                 block = (xfs_btree_block_t *)ifp->if_broot;
 505                 bp = NULL;
 506         } else {
 507                 bp = cur->bc_bufs[level];
 508                 block = XFS_BUF_TO_BLOCK(bp);
 509         }
 510         ASSERT(block != NULL);
 511         *bpp = bp;
 512         return block;
 513 }
 514
 515 /*
 516  * Get a buffer for the block, return it with no data read.
 517  * Long-form addressing.
 518  */
 519 xfs_buf_t *                             /* buffer for fsbno */
 520 xfs_btree_get_bufl(
 521         xfs_mount_t     *mp,            /* file system mount point */
 522         xfs_trans_t     *tp,            /* transaction pointer */
 523         xfs_fsblock_t   fsbno,          /* file system block number */
 524         uint            lock)           /* lock flags for get_buf */
 525 {
 526         xfs_buf_t       *bp;            /* buffer pointer (return value) */
 527         xfs_daddr_t             d;              /* real disk block address */
 528
 529         ASSERT(fsbno != NULLFSBLOCK);
 530         d = XFS_FSB_TO_DADDR(mp, fsbno);
 531         bp = xfs_trans_get_buf(tp, mp->m_ddev_targp, d, mp->m_bsize, lock);
 532         ASSERT(bp);
 533         ASSERT(!XFS_BUF_GETERROR(bp));
 534         return bp;
 535 }
 536
 537 /*
 538  * Get a buffer for the block, return it with no data read.
 539  * Short-form addressing.
 540  */
 541 xfs_buf_t *                             /* buffer for agno/agbno */
 542 xfs_btree_get_bufs(
 543         xfs_mount_t     *mp,            /* file system mount point */
 544         xfs_trans_t     *tp,            /* transaction pointer */
 545         xfs_agnumber_t  agno,           /* allocation group number */
 546         xfs_agblock_t   agbno,          /* allocation group block number */
 547         uint            lock)           /* lock flags for get_buf */
 548 {
 549         xfs_buf_t       *bp;            /* buffer pointer (return value) */
 550         xfs_daddr_t             d;              /* real disk block address */
 551
 552         ASSERT(agno != NULLAGNUMBER);
 553         ASSERT(agbno != NULLAGBLOCK);
 554         d = XFS_AGB_TO_DADDR(mp, agno, agbno);
 555         bp = xfs_trans_get_buf(tp, mp->m_ddev_targp, d, mp->m_bsize, lock);
 556         ASSERT(bp);
 557         ASSERT(!XFS_BUF_GETERROR(bp));
 558         return bp;
 559 }
 560
 561 /*
 562  * Allocate a new btree cursor.
 563  * The cursor is either for allocation (A) or bmap (B) or inodes (I).
 564  */
 565 xfs_btree_cur_t *                       /* new btree cursor */
 566 xfs_btree_init_cursor(
 567         xfs_mount_t     *mp,            /* file system mount point */
 568         xfs_trans_t     *tp,            /* transaction pointer */
 569         xfs_buf_t       *agbp,          /* (A only) buffer for agf structure */
 570                                         /* (I only) buffer for agi structure */
 571         xfs_agnumber_t  agno,           /* (AI only) allocation group number */
 572         xfs_btnum_t     btnum,          /* btree identifier */
 573         xfs_inode_t     *ip,            /* (B only) inode owning the btree */
 574         int             whichfork)      /* (B only) data or attr fork */
 575 {
 576         xfs_agf_t       *agf;           /* (A) allocation group freespace */
 577         xfs_agi_t       *agi;           /* (I) allocation group inodespace */
 578         xfs_btree_cur_t *cur;           /* return value */
 579         xfs_ifork_t     *ifp;           /* (I) inode fork pointer */
 580         int             nlevels=0;      /* number of levels in the btree */
 581
 582         ASSERT(xfs_btree_cur_zone != NULL);
 583         /*
 584          * Allocate a new cursor.
 585          */
 586         cur = kmem_zone_zalloc(xfs_btree_cur_zone, KM_SLEEP);
 587         /*
 588          * Deduce the number of btree levels from the arguments.
 589          */
 590         switch (btnum) {
 591         case XFS_BTNUM_BNO:
 592         case XFS_BTNUM_CNT:
 593                 agf = XFS_BUF_TO_AGF(agbp);
 594                 nlevels = INT_GET(agf->agf_levels[btnum], ARCH_CONVERT);
 595                 break;
 596         case XFS_BTNUM_BMAP:
 597                 ifp = XFS_IFORK_PTR(ip, whichfork);
 598                 nlevels = INT_GET(ifp->if_broot->bb_level, ARCH_CONVERT) + 1;
 599                 break;
 600         case XFS_BTNUM_INO:
 601                 agi = XFS_BUF_TO_AGI(agbp);
 602                 nlevels = INT_GET(agi->agi_level, ARCH_CONVERT);
 603                 break;
 604         default:
 605                 ASSERT(0);
 606         }
 607         /*
 608          * Fill in the common fields.
 609          */
 610         cur->bc_tp = tp;
 611         cur->bc_mp = mp;
 612         cur->bc_nlevels = nlevels;
 613         cur->bc_btnum = btnum;
 614         cur->bc_blocklog = mp->m_sb.sb_blocklog;
 615         /*
 616          * Fill in private fields.
 617          */
 618         switch (btnum) {
 619         case XFS_BTNUM_BNO:
 620         case XFS_BTNUM_CNT:
 621                 /*
 622                  * Allocation btree fields.
 623                  */
 624                 cur->bc_private.a.agbp = agbp;
 625                 cur->bc_private.a.agno = agno;
 626                 break;
 627         case XFS_BTNUM_BMAP:
 628                 /*
 629                  * Bmap btree fields.
 630                  */
 631                 cur->bc_private.b.forksize = XFS_IFORK_SIZE(ip, whichfork);
 632                 cur->bc_private.b.ip = ip;
 633                 cur->bc_private.b.firstblock = NULLFSBLOCK;
 634                 cur->bc_private.b.flist = NULL;
 635                 cur->bc_private.b.allocated = 0;
 636                 cur->bc_private.b.flags = 0;
 637                 cur->bc_private.b.whichfork = whichfork;
 638                 break;
 639         case XFS_BTNUM_INO:
 640                 /*
 641                  * Inode allocation btree fields.
 642                  */
 643                 cur->bc_private.i.agbp = agbp;
 644                 cur->bc_private.i.agno = agno;
 645                 break;
 646         default:
 647                 ASSERT(0);
 648         }
 649         return cur;
 650 }
 651
 652 /*
 653  * Check for the cursor referring to the last block at the given level.
 654  */
 655 int                                     /* 1=is last block, 0=not last block */
 656 xfs_btree_islastblock(
 657         xfs_btree_cur_t         *cur,   /* btree cursor */
 658         int                     level)  /* level to check */
 659 {
 660         xfs_btree_block_t       *block; /* generic btree block pointer */
 661         xfs_buf_t               *bp;    /* buffer containing block */
 662
 663         block = xfs_btree_get_block(cur, level, &bp);
 664         xfs_btree_check_block(cur, block, level, bp);
 665         if (XFS_BTREE_LONG_PTRS(cur->bc_btnum))
 666                 return INT_GET(block->bb_u.l.bb_rightsib, ARCH_CONVERT) == NULLDFSBNO;
 667         else
 668                 return INT_GET(block->bb_u.s.bb_rightsib, ARCH_CONVERT) == NULLAGBLOCK;
 669 }
 670
 671 /*
 672  * Change the cursor to point to the last record in the current block
 673  * at the given level.  Other levels are unaffected.
 674  */
 675 int                                     /* success=1, failure=0 */
 676 xfs_btree_lastrec(
 677         xfs_btree_cur_t         *cur,   /* btree cursor */
 678         int                     level)  /* level to change */
 679 {
 680         xfs_btree_block_t       *block; /* generic btree block pointer */
 681         xfs_buf_t               *bp;    /* buffer containing block */
 682
 683         /*
 684          * Get the block pointer for this level.
 685          */
 686         block = xfs_btree_get_block(cur, level, &bp);
 687         xfs_btree_check_block(cur, block, level, bp);
 688         /*
 689          * It's empty, there is no such record.
 690          */
 691         if (!block->bb_h.bb_numrecs)
 692                 return 0;
 693         /*
 694          * Set the ptr value to numrecs, that's the last record/key.
 695          */
 696         cur->bc_ptrs[level] = INT_GET(block->bb_h.bb_numrecs, ARCH_CONVERT);
 697         return 1;
 698 }
 699
 700 /*
 701  * Compute first and last byte offsets for the fields given.
 702  * Interprets the offsets table, which contains struct field offsets.
 703  */
 704 void
 705 xfs_btree_offsets(
 706         __int64_t       fields,         /* bitmask of fields */
 707         const short     *offsets,       /* table of field offsets */
 708         int             nbits,          /* number of bits to inspect */
 709         int             *first,         /* output: first byte offset */
 710         int             *last)          /* output: last byte offset */
 711 {
 712         int             i;              /* current bit number */
 713         __int64_t       imask;          /* mask for current bit number */
 714
 715         ASSERT(fields != 0);
 716         /*
 717          * Find the lowest bit, so the first byte offset.
 718          */
 719         for (i = 0, imask = 1LL; ; i++, imask <<= 1) {
 720                 if (imask & fields) {
 721                         *first = offsets[i];
 722                         break;
 723                 }
 724         }
 725         /*
 726          * Find the highest bit, so the last byte offset.
 727          */
 728         for (i = nbits - 1, imask = 1LL << i; ; i--, imask >>= 1) {
 729                 if (imask & fields) {
 730                         *last = offsets[i + 1] - 1;
 731                         break;
 732                 }
 733         }
 734 }
 735
 736 /*
 737  * Get a buffer for the block, return it read in.
 738  * Long-form addressing.
 739  */
 740 int                                     /* error */
 741 xfs_btree_read_bufl(
 742         xfs_mount_t     *mp,            /* file system mount point */
 743         xfs_trans_t     *tp,            /* transaction pointer */
 744         xfs_fsblock_t   fsbno,          /* file system block number */
 745         uint            lock,           /* lock flags for read_buf */
 746         xfs_buf_t       **bpp,          /* buffer for fsbno */
 747         int             refval)         /* ref count value for buffer */
 748 {
 749         xfs_buf_t       *bp;            /* return value */
 750         xfs_daddr_t             d;              /* real disk block address */
 751         int             error;
 752
 753         ASSERT(fsbno != NULLFSBLOCK);
 754         d = XFS_FSB_TO_DADDR(mp, fsbno);
 755         if ((error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp, d,
 756                         mp->m_bsize, lock, &bp))) {
 757                 return error;
 758         }
 759         ASSERT(!bp || !XFS_BUF_GETERROR(bp));
 760         if (bp != NULL) {
 761                 XFS_BUF_SET_VTYPE_REF(bp, B_FS_MAP, refval);
 762         }
 763         *bpp = bp;
 764         return 0;
 765 }
 766
 767 /*
 768  * Get a buffer for the block, return it read in.
 769  * Short-form addressing.
 770  */
 771 int                                     /* error */
 772 xfs_btree_read_bufs(
 773         xfs_mount_t     *mp,            /* file system mount point */
 774         xfs_trans_t     *tp,            /* transaction pointer */
 775         xfs_agnumber_t  agno,           /* allocation group number */
 776         xfs_agblock_t   agbno,          /* allocation group block number */
 777         uint            lock,           /* lock flags for read_buf */
 778         xfs_buf_t       **bpp,          /* buffer for agno/agbno */
 779         int             refval)         /* ref count value for buffer */
 780 {
 781         xfs_buf_t       *bp;            /* return value */
 782         xfs_daddr_t     d;              /* real disk block address */
 783         int             error;
 784
 785         ASSERT(agno != NULLAGNUMBER);
 786         ASSERT(agbno != NULLAGBLOCK);
 787         d = XFS_AGB_TO_DADDR(mp, agno, agbno);
 788         if ((error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp, d,
 789                                         mp->m_bsize, lock, &bp))) {
 790                 return error;
 791         }
 792         ASSERT(!bp || !XFS_BUF_GETERROR(bp));
 793         if (bp != NULL) {
 794                 switch (refval) {
 795                 case XFS_ALLOC_BTREE_REF:
 796                         XFS_BUF_SET_VTYPE_REF(bp, B_FS_MAP, refval);
 797                         break;
 798                 case XFS_INO_BTREE_REF:
 799                         XFS_BUF_SET_VTYPE_REF(bp, B_FS_INOMAP, refval);
 800                         break;
 801                 }
 802         }
 803         *bpp = bp;
 804         return 0;
 805 }
 806
 807 /*
 808  * Read-ahead the block, don't wait for it, don't return a buffer.
 809  * Long-form addressing.
 810  */
 811 /* ARGSUSED */
 812 void
 813 xfs_btree_reada_bufl(
 814         xfs_mount_t     *mp,            /* file system mount point */
 815         xfs_fsblock_t   fsbno,          /* file system block number */
 816         xfs_extlen_t    count)          /* count of filesystem blocks */
 817 {
 818         xfs_daddr_t             d;
 819
 820         ASSERT(fsbno != NULLFSBLOCK);
 821         d = XFS_FSB_TO_DADDR(mp, fsbno);
 822         xfs_baread(mp->m_ddev_targp, d, mp->m_bsize * count);
 823 }
 824
 825 /*
 826  * Read-ahead the block, don't wait for it, don't return a buffer.
 827  * Short-form addressing.
 828  */
 829 /* ARGSUSED */
 830 void
 831 xfs_btree_reada_bufs(
 832         xfs_mount_t     *mp,            /* file system mount point */
 833         xfs_agnumber_t  agno,           /* allocation group number */
 834         xfs_agblock_t   agbno,          /* allocation group block number */
 835         xfs_extlen_t    count)          /* count of filesystem blocks */
 836 {
 837         xfs_daddr_t             d;
 838
 839         ASSERT(agno != NULLAGNUMBER);
 840         ASSERT(agbno != NULLAGBLOCK);
 841         d = XFS_AGB_TO_DADDR(mp, agno, agbno);
 842         xfs_baread(mp->m_ddev_targp, d, mp->m_bsize * count);
 843 }
 844
 845 /*
 846  * Read-ahead btree blocks, at the given level.
 847  * Bits in lr are set from XFS_BTCUR_{LEFT,RIGHT}RA.
 848  */
 849 int
 850 xfs_btree_readahead_core(
 851         xfs_btree_cur_t         *cur,           /* btree cursor */
 852         int                     lev,            /* level in btree */
 853         int                     lr)             /* left/right bits */
 854 {
 855         xfs_alloc_block_t       *a;
 856         xfs_bmbt_block_t        *b;
 857         xfs_inobt_block_t       *i;
 858         int                     rval = 0;
 859
 860         ASSERT(cur->bc_bufs[lev] != NULL);
 861         cur->bc_ra[lev] |= lr;
 862         switch (cur->bc_btnum) {
 863         case XFS_BTNUM_BNO:
 864         case XFS_BTNUM_CNT:
 865                 a = XFS_BUF_TO_ALLOC_BLOCK(cur->bc_bufs[lev]);
 866                 if ((lr & XFS_BTCUR_LEFTRA) && INT_GET(a->bb_leftsib, ARCH_CONVERT) != NULLAGBLOCK) {
 867                         xfs_btree_reada_bufs(cur->bc_mp, cur->bc_private.a.agno,
 868                                 INT_GET(a->bb_leftsib, ARCH_CONVERT), 1);
 869                         rval++;
 870                 }
 871                 if ((lr & XFS_BTCUR_RIGHTRA) && INT_GET(a->bb_rightsib, ARCH_CONVERT) != NULLAGBLOCK) {
 872                         xfs_btree_reada_bufs(cur->bc_mp, cur->bc_private.a.agno,
 873                                 INT_GET(a->bb_rightsib, ARCH_CONVERT), 1);
 874                         rval++;
 875                 }
 876                 break;
 877         case XFS_BTNUM_BMAP:
 878                 b = XFS_BUF_TO_BMBT_BLOCK(cur->bc_bufs[lev]);
 879                 if ((lr & XFS_BTCUR_LEFTRA) && INT_GET(b->bb_leftsib, ARCH_CONVERT) != NULLDFSBNO) {
 880                         xfs_btree_reada_bufl(cur->bc_mp, INT_GET(b->bb_leftsib, ARCH_CONVERT), 1);
 881                         rval++;
 882                 }
 883                 if ((lr & XFS_BTCUR_RIGHTRA) && INT_GET(b->bb_rightsib, ARCH_CONVERT) != NULLDFSBNO) {
 884                         xfs_btree_reada_bufl(cur->bc_mp, INT_GET(b->bb_rightsib, ARCH_CONVERT), 1);
 885                         rval++;
 886                 }
 887                 break;
 888         case XFS_BTNUM_INO:
 889                 i = XFS_BUF_TO_INOBT_BLOCK(cur->bc_bufs[lev]);
 890                 if ((lr & XFS_BTCUR_LEFTRA) && INT_GET(i->bb_leftsib, ARCH_CONVERT) != NULLAGBLOCK) {
 891                         xfs_btree_reada_bufs(cur->bc_mp, cur->bc_private.i.agno,
 892                                 INT_GET(i->bb_leftsib, ARCH_CONVERT), 1);
 893                         rval++;
 894                 }
 895                 if ((lr & XFS_BTCUR_RIGHTRA) && INT_GET(i->bb_rightsib, ARCH_CONVERT) != NULLAGBLOCK) {
 896                         xfs_btree_reada_bufs(cur->bc_mp, cur->bc_private.i.agno,
 897                                 INT_GET(i->bb_rightsib, ARCH_CONVERT), 1);
 898                         rval++;
 899                 }
 900                 break;
 901         default:
 902                 ASSERT(0);
 903         }
 904         return rval;
 905 }
 906
 907 /*
 908  * Set the buffer for level "lev" in the cursor to bp, releasing
 909  * any previous buffer.
 910  */
 911 void
 912 xfs_btree_setbuf(
 913         xfs_btree_cur_t         *cur,   /* btree cursor */
 914         int                     lev,    /* level in btree */
 915         xfs_buf_t               *bp)    /* new buffer to set */
 916 {
 917         xfs_btree_block_t       *b;     /* btree block */
 918         xfs_buf_t               *obp;   /* old buffer pointer */
 919
 920         obp = cur->bc_bufs[lev];
 921         if (obp)
 922                 xfs_trans_brelse(cur->bc_tp, obp);
 923         cur->bc_bufs[lev] = bp;
 924         cur->bc_ra[lev] = 0;
 925         if (!bp)
 926                 return;
 927         b = XFS_BUF_TO_BLOCK(bp);
 928         if (XFS_BTREE_LONG_PTRS(cur->bc_btnum)) {
 929                 if (INT_GET(b->bb_u.l.bb_leftsib, ARCH_CONVERT) == NULLDFSBNO)
 930                         cur->bc_ra[lev] |= XFS_BTCUR_LEFTRA;
 931                 if (INT_GET(b->bb_u.l.bb_rightsib, ARCH_CONVERT) == NULLDFSBNO)
 932                         cur->bc_ra[lev] |= XFS_BTCUR_RIGHTRA;
 933         } else {
 934                 if (INT_GET(b->bb_u.s.bb_leftsib, ARCH_CONVERT) == NULLAGBLOCK)
 935                         cur->bc_ra[lev] |= XFS_BTCUR_LEFTRA;
 936                 if (INT_GET(b->bb_u.s.bb_rightsib, ARCH_CONVERT) == NULLAGBLOCK)
 937                         cur->bc_ra[lev] |= XFS_BTCUR_RIGHTRA;
 938         }
 939 }