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