fs/xfs/xfs_btree.c

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