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