libxfs/xfs_bmap_btree.c

   1 /*
   2  * Copyright (c) 2000-2003,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 "libxfs_priv.h"
  19 #include "xfs_fs.h"
  20 #include "xfs_shared.h"
  21 #include "xfs_format.h"
  22 #include "xfs_log_format.h"
  23 #include "xfs_trans_resv.h"
  24 #include "xfs_bit.h"
  25 #include "xfs_mount.h"
  26 #include "xfs_defer.h"
  27 #include "xfs_inode.h"
  28 #include "xfs_trans.h"
  29 #include "xfs_alloc.h"
  30 #include "xfs_btree.h"
  31 #include "xfs_bmap_btree.h"
  32 #include "xfs_bmap.h"
  33 #include "xfs_trace.h"
  34 #include "xfs_cksum.h"
  35 #include "xfs_rmap.h"
  36
  37 /*
  38  * Determine the extent state.
  39  */
  40 /* ARGSUSED */
  41 STATIC xfs_exntst_t
  42 xfs_extent_state(
  43         xfs_filblks_t           blks,
  44         int                     extent_flag)
  45 {
  46         if (extent_flag) {
  47                 ASSERT(blks != 0);      /* saved for DMIG */
  48                 return XFS_EXT_UNWRITTEN;
  49         }
  50         return XFS_EXT_NORM;
  51 }
  52
  53 /*
  54  * Convert on-disk form of btree root to in-memory form.
  55  */
  56 void
  57 xfs_bmdr_to_bmbt(
  58         struct xfs_inode        *ip,
  59         xfs_bmdr_block_t        *dblock,
  60         int                     dblocklen,
  61         struct xfs_btree_block  *rblock,
  62         int                     rblocklen)
  63 {
  64         struct xfs_mount        *mp = ip->i_mount;
  65         int                     dmxr;
  66         xfs_bmbt_key_t          *fkp;
  67         __be64                  *fpp;
  68         xfs_bmbt_key_t          *tkp;
  69         __be64                  *tpp;
  70
  71         xfs_btree_init_block_int(mp, rblock, XFS_BUF_DADDR_NULL,
  72                                  XFS_BTNUM_BMAP, 0, 0, ip->i_ino,
  73                                  XFS_BTREE_LONG_PTRS);
  74         rblock->bb_level = dblock->bb_level;
  75         ASSERT(be16_to_cpu(rblock->bb_level) > 0);
  76         rblock->bb_numrecs = dblock->bb_numrecs;
  77         dmxr = xfs_bmdr_maxrecs(dblocklen, 0);
  78         fkp = XFS_BMDR_KEY_ADDR(dblock, 1);
  79         tkp = XFS_BMBT_KEY_ADDR(mp, rblock, 1);
  80         fpp = XFS_BMDR_PTR_ADDR(dblock, 1, dmxr);
  81         tpp = XFS_BMAP_BROOT_PTR_ADDR(mp, rblock, 1, rblocklen);
  82         dmxr = be16_to_cpu(dblock->bb_numrecs);
  83         memcpy(tkp, fkp, sizeof(*fkp) * dmxr);
  84         memcpy(tpp, fpp, sizeof(*fpp) * dmxr);
  85 }
  86
  87 /*
  88  * Convert a compressed bmap extent record to an uncompressed form.
  89  * This code must be in sync with the routines xfs_bmbt_get_startoff,
  90  * xfs_bmbt_get_startblock, xfs_bmbt_get_blockcount and xfs_bmbt_get_state.
  91  */
  92 STATIC void
  93 __xfs_bmbt_get_all(
  94                 uint64_t l0,
  95                 uint64_t l1,
  96                 xfs_bmbt_irec_t *s)
  97 {
  98         int     ext_flag;
  99         xfs_exntst_t st;
 100
 101         ext_flag = (int)(l0 >> (64 - BMBT_EXNTFLAG_BITLEN));
 102         s->br_startoff = ((xfs_fileoff_t)l0 &
 103                            xfs_mask64lo(64 - BMBT_EXNTFLAG_BITLEN)) >> 9;
 104         s->br_startblock = (((xfs_fsblock_t)l0 & xfs_mask64lo(9)) << 43) |
 105                            (((xfs_fsblock_t)l1) >> 21);
 106         s->br_blockcount = (xfs_filblks_t)(l1 & xfs_mask64lo(21));
 107         /* This is xfs_extent_state() in-line */
 108         if (ext_flag) {
 109                 ASSERT(s->br_blockcount != 0);  /* saved for DMIG */
 110                 st = XFS_EXT_UNWRITTEN;
 111         } else
 112                 st = XFS_EXT_NORM;
 113         s->br_state = st;
 114 }
 115
 116 void
 117 xfs_bmbt_get_all(
 118         xfs_bmbt_rec_host_t *r,
 119         xfs_bmbt_irec_t *s)
 120 {
 121         __xfs_bmbt_get_all(r->l0, r->l1, s);
 122 }
 123
 124 /*
 125  * Extract the blockcount field from an in memory bmap extent record.
 126  */
 127 xfs_filblks_t
 128 xfs_bmbt_get_blockcount(
 129         xfs_bmbt_rec_host_t     *r)
 130 {
 131         return (xfs_filblks_t)(r->l1 & xfs_mask64lo(21));
 132 }
 133
 134 /*
 135  * Extract the startblock field from an in memory bmap extent record.
 136  */
 137 xfs_fsblock_t
 138 xfs_bmbt_get_startblock(
 139         xfs_bmbt_rec_host_t     *r)
 140 {
 141         return (((xfs_fsblock_t)r->l0 & xfs_mask64lo(9)) << 43) |
 142                (((xfs_fsblock_t)r->l1) >> 21);
 143 }
 144
 145 /*
 146  * Extract the startoff field from an in memory bmap extent record.
 147  */
 148 xfs_fileoff_t
 149 xfs_bmbt_get_startoff(
 150         xfs_bmbt_rec_host_t     *r)
 151 {
 152         return ((xfs_fileoff_t)r->l0 &
 153                  xfs_mask64lo(64 - BMBT_EXNTFLAG_BITLEN)) >> 9;
 154 }
 155
 156 xfs_exntst_t
 157 xfs_bmbt_get_state(
 158         xfs_bmbt_rec_host_t     *r)
 159 {
 160         int     ext_flag;
 161
 162         ext_flag = (int)((r->l0) >> (64 - BMBT_EXNTFLAG_BITLEN));
 163         return xfs_extent_state(xfs_bmbt_get_blockcount(r),
 164                                 ext_flag);
 165 }
 166
 167 /*
 168  * Extract the blockcount field from an on disk bmap extent record.
 169  */
 170 xfs_filblks_t
 171 xfs_bmbt_disk_get_blockcount(
 172         xfs_bmbt_rec_t  *r)
 173 {
 174         return (xfs_filblks_t)(be64_to_cpu(r->l1) & xfs_mask64lo(21));
 175 }
 176
 177 /*
 178  * Extract the startoff field from a disk format bmap extent record.
 179  */
 180 xfs_fileoff_t
 181 xfs_bmbt_disk_get_startoff(
 182         xfs_bmbt_rec_t  *r)
 183 {
 184         return ((xfs_fileoff_t)be64_to_cpu(r->l0) &
 185                  xfs_mask64lo(64 - BMBT_EXNTFLAG_BITLEN)) >> 9;
 186 }
 187
 188
 189 /*
 190  * Set all the fields in a bmap extent record from the arguments.
 191  */
 192 void
 193 xfs_bmbt_set_allf(
 194         xfs_bmbt_rec_host_t     *r,
 195         xfs_fileoff_t           startoff,
 196         xfs_fsblock_t           startblock,
 197         xfs_filblks_t           blockcount,
 198         xfs_exntst_t            state)
 199 {
 200         int             extent_flag = (state == XFS_EXT_NORM) ? 0 : 1;
 201
 202         ASSERT(state == XFS_EXT_NORM || state == XFS_EXT_UNWRITTEN);
 203         ASSERT((startoff & xfs_mask64hi(64-BMBT_STARTOFF_BITLEN)) == 0);
 204         ASSERT((blockcount & xfs_mask64hi(64-BMBT_BLOCKCOUNT_BITLEN)) == 0);
 205
 206         ASSERT((startblock & xfs_mask64hi(64-BMBT_STARTBLOCK_BITLEN)) == 0);
 207
 208         r->l0 = ((xfs_bmbt_rec_base_t)extent_flag << 63) |
 209                 ((xfs_bmbt_rec_base_t)startoff << 9) |
 210                 ((xfs_bmbt_rec_base_t)startblock >> 43);
 211         r->l1 = ((xfs_bmbt_rec_base_t)startblock << 21) |
 212                 ((xfs_bmbt_rec_base_t)blockcount &
 213                 (xfs_bmbt_rec_base_t)xfs_mask64lo(21));
 214 }
 215
 216 /*
 217  * Set all the fields in a bmap extent record from the uncompressed form.
 218  */
 219 void
 220 xfs_bmbt_set_all(
 221         xfs_bmbt_rec_host_t *r,
 222         xfs_bmbt_irec_t *s)
 223 {
 224         xfs_bmbt_set_allf(r, s->br_startoff, s->br_startblock,
 225                              s->br_blockcount, s->br_state);
 226 }
 227
 228
 229 /*
 230  * Set all the fields in a disk format bmap extent record from the arguments.
 231  */
 232 void
 233 xfs_bmbt_disk_set_allf(
 234         xfs_bmbt_rec_t          *r,
 235         xfs_fileoff_t           startoff,
 236         xfs_fsblock_t           startblock,
 237         xfs_filblks_t           blockcount,
 238         xfs_exntst_t            state)
 239 {
 240         int                     extent_flag = (state == XFS_EXT_NORM) ? 0 : 1;
 241
 242         ASSERT(state == XFS_EXT_NORM || state == XFS_EXT_UNWRITTEN);
 243         ASSERT((startoff & xfs_mask64hi(64-BMBT_STARTOFF_BITLEN)) == 0);
 244         ASSERT((blockcount & xfs_mask64hi(64-BMBT_BLOCKCOUNT_BITLEN)) == 0);
 245         ASSERT((startblock & xfs_mask64hi(64-BMBT_STARTBLOCK_BITLEN)) == 0);
 246
 247         r->l0 = cpu_to_be64(
 248                 ((xfs_bmbt_rec_base_t)extent_flag << 63) |
 249                  ((xfs_bmbt_rec_base_t)startoff << 9) |
 250                  ((xfs_bmbt_rec_base_t)startblock >> 43));
 251         r->l1 = cpu_to_be64(
 252                 ((xfs_bmbt_rec_base_t)startblock << 21) |
 253                  ((xfs_bmbt_rec_base_t)blockcount &
 254                   (xfs_bmbt_rec_base_t)xfs_mask64lo(21)));
 255 }
 256
 257 /*
 258  * Set all the fields in a bmap extent record from the uncompressed form.
 259  */
 260 STATIC void
 261 xfs_bmbt_disk_set_all(
 262         xfs_bmbt_rec_t  *r,
 263         xfs_bmbt_irec_t *s)
 264 {
 265         xfs_bmbt_disk_set_allf(r, s->br_startoff, s->br_startblock,
 266                                   s->br_blockcount, s->br_state);
 267 }
 268
 269 /*
 270  * Set the blockcount field in a bmap extent record.
 271  */
 272 void
 273 xfs_bmbt_set_blockcount(
 274         xfs_bmbt_rec_host_t *r,
 275         xfs_filblks_t   v)
 276 {
 277         ASSERT((v & xfs_mask64hi(43)) == 0);
 278         r->l1 = (r->l1 & (xfs_bmbt_rec_base_t)xfs_mask64hi(43)) |
 279                   (xfs_bmbt_rec_base_t)(v & xfs_mask64lo(21));
 280 }
 281
 282 /*
 283  * Set the startblock field in a bmap extent record.
 284  */
 285 void
 286 xfs_bmbt_set_startblock(
 287         xfs_bmbt_rec_host_t *r,
 288         xfs_fsblock_t   v)
 289 {
 290         ASSERT((v & xfs_mask64hi(12)) == 0);
 291         r->l0 = (r->l0 & (xfs_bmbt_rec_base_t)xfs_mask64hi(55)) |
 292                   (xfs_bmbt_rec_base_t)(v >> 43);
 293         r->l1 = (r->l1 & (xfs_bmbt_rec_base_t)xfs_mask64lo(21)) |
 294                   (xfs_bmbt_rec_base_t)(v << 21);
 295 }
 296
 297 /*
 298  * Set the startoff field in a bmap extent record.
 299  */
 300 void
 301 xfs_bmbt_set_startoff(
 302         xfs_bmbt_rec_host_t *r,
 303         xfs_fileoff_t   v)
 304 {
 305         ASSERT((v & xfs_mask64hi(9)) == 0);
 306         r->l0 = (r->l0 & (xfs_bmbt_rec_base_t) xfs_mask64hi(1)) |
 307                 ((xfs_bmbt_rec_base_t)v << 9) |
 308                   (r->l0 & (xfs_bmbt_rec_base_t)xfs_mask64lo(9));
 309 }
 310
 311 /*
 312  * Set the extent state field in a bmap extent record.
 313  */
 314 void
 315 xfs_bmbt_set_state(
 316         xfs_bmbt_rec_host_t *r,
 317         xfs_exntst_t    v)
 318 {
 319         ASSERT(v == XFS_EXT_NORM || v == XFS_EXT_UNWRITTEN);
 320         if (v == XFS_EXT_NORM)
 321                 r->l0 &= xfs_mask64lo(64 - BMBT_EXNTFLAG_BITLEN);
 322         else
 323                 r->l0 |= xfs_mask64hi(BMBT_EXNTFLAG_BITLEN);
 324 }
 325
 326 /*
 327  * Convert in-memory form of btree root to on-disk form.
 328  */
 329 void
 330 xfs_bmbt_to_bmdr(
 331         struct xfs_mount        *mp,
 332         struct xfs_btree_block  *rblock,
 333         int                     rblocklen,
 334         xfs_bmdr_block_t        *dblock,
 335         int                     dblocklen)
 336 {
 337         int                     dmxr;
 338         xfs_bmbt_key_t          *fkp;
 339         __be64                  *fpp;
 340         xfs_bmbt_key_t          *tkp;
 341         __be64                  *tpp;
 342
 343         if (xfs_sb_version_hascrc(&mp->m_sb)) {
 344                 ASSERT(rblock->bb_magic == cpu_to_be32(XFS_BMAP_CRC_MAGIC));
 345                 ASSERT(uuid_equal(&rblock->bb_u.l.bb_uuid,
 346                        &mp->m_sb.sb_meta_uuid));
 347                 ASSERT(rblock->bb_u.l.bb_blkno ==
 348                        cpu_to_be64(XFS_BUF_DADDR_NULL));
 349         } else
 350                 ASSERT(rblock->bb_magic == cpu_to_be32(XFS_BMAP_MAGIC));
 351         ASSERT(rblock->bb_u.l.bb_leftsib == cpu_to_be64(NULLFSBLOCK));
 352         ASSERT(rblock->bb_u.l.bb_rightsib == cpu_to_be64(NULLFSBLOCK));
 353         ASSERT(rblock->bb_level != 0);
 354         dblock->bb_level = rblock->bb_level;
 355         dblock->bb_numrecs = rblock->bb_numrecs;
 356         dmxr = xfs_bmdr_maxrecs(dblocklen, 0);
 357         fkp = XFS_BMBT_KEY_ADDR(mp, rblock, 1);
 358         tkp = XFS_BMDR_KEY_ADDR(dblock, 1);
 359         fpp = XFS_BMAP_BROOT_PTR_ADDR(mp, rblock, 1, rblocklen);
 360         tpp = XFS_BMDR_PTR_ADDR(dblock, 1, dmxr);
 361         dmxr = be16_to_cpu(dblock->bb_numrecs);
 362         memcpy(tkp, fkp, sizeof(*fkp) * dmxr);
 363         memcpy(tpp, fpp, sizeof(*fpp) * dmxr);
 364 }
 365
 366 STATIC struct xfs_btree_cur *
 367 xfs_bmbt_dup_cursor(
 368         struct xfs_btree_cur    *cur)
 369 {
 370         struct xfs_btree_cur    *new;
 371
 372         new = xfs_bmbt_init_cursor(cur->bc_mp, cur->bc_tp,
 373                         cur->bc_private.b.ip, cur->bc_private.b.whichfork);
 374
 375         /*
 376          * Copy the firstblock, dfops, and flags values,
 377          * since init cursor doesn't get them.
 378          */
 379         new->bc_private.b.firstblock = cur->bc_private.b.firstblock;
 380         new->bc_private.b.dfops = cur->bc_private.b.dfops;
 381         new->bc_private.b.flags = cur->bc_private.b.flags;
 382
 383         return new;
 384 }
 385
 386 STATIC void
 387 xfs_bmbt_update_cursor(
 388         struct xfs_btree_cur    *src,
 389         struct xfs_btree_cur    *dst)
 390 {
 391         ASSERT((dst->bc_private.b.firstblock != NULLFSBLOCK) ||
 392                (dst->bc_private.b.ip->i_d.di_flags & XFS_DIFLAG_REALTIME));
 393         ASSERT(dst->bc_private.b.dfops == src->bc_private.b.dfops);
 394
 395         dst->bc_private.b.allocated += src->bc_private.b.allocated;
 396         dst->bc_private.b.firstblock = src->bc_private.b.firstblock;
 397
 398         src->bc_private.b.allocated = 0;
 399 }
 400
 401 STATIC int
 402 xfs_bmbt_alloc_block(
 403         struct xfs_btree_cur    *cur,
 404         union xfs_btree_ptr     *start,
 405         union xfs_btree_ptr     *new,
 406         int                     *stat)
 407 {
 408         xfs_alloc_arg_t         args;           /* block allocation args */
 409         int                     error;          /* error return value */
 410
 411         memset(&args, 0, sizeof(args));
 412         args.tp = cur->bc_tp;
 413         args.mp = cur->bc_mp;
 414         args.fsbno = cur->bc_private.b.firstblock;
 415         args.firstblock = args.fsbno;
 416         xfs_rmap_ino_bmbt_owner(&args.oinfo, cur->bc_private.b.ip->i_ino,
 417                         cur->bc_private.b.whichfork);
 418
 419         if (args.fsbno == NULLFSBLOCK) {
 420                 args.fsbno = be64_to_cpu(start->l);
 421                 args.type = XFS_ALLOCTYPE_START_BNO;
 422                 /*
 423                  * Make sure there is sufficient room left in the AG to
 424                  * complete a full tree split for an extent insert.  If
 425                  * we are converting the middle part of an extent then
 426                  * we may need space for two tree splits.
 427                  *
 428                  * We are relying on the caller to make the correct block
 429                  * reservation for this operation to succeed.  If the
 430                  * reservation amount is insufficient then we may fail a
 431                  * block allocation here and corrupt the filesystem.
 432                  */
 433                 args.minleft = args.tp->t_blk_res;
 434         } else if (cur->bc_private.b.dfops->dop_low) {
 435                 args.type = XFS_ALLOCTYPE_START_BNO;
 436         } else {
 437                 args.type = XFS_ALLOCTYPE_NEAR_BNO;
 438         }
 439
 440         args.minlen = args.maxlen = args.prod = 1;
 441         args.wasdel = cur->bc_private.b.flags & XFS_BTCUR_BPRV_WASDEL;
 442         if (!args.wasdel && args.tp->t_blk_res == 0) {
 443                 error = -ENOSPC;
 444                 goto error0;
 445         }
 446         error = xfs_alloc_vextent(&args);
 447         if (error)
 448                 goto error0;
 449
 450         if (args.fsbno == NULLFSBLOCK && args.minleft) {
 451                 /*
 452                  * Could not find an AG with enough free space to satisfy
 453                  * a full btree split.  Try again and if
 454                  * successful activate the lowspace algorithm.
 455                  */
 456                 args.fsbno = 0;
 457                 args.type = XFS_ALLOCTYPE_FIRST_AG;
 458                 error = xfs_alloc_vextent(&args);
 459                 if (error)
 460                         goto error0;
 461                 cur->bc_private.b.dfops->dop_low = true;
 462         }
 463         if (WARN_ON_ONCE(args.fsbno == NULLFSBLOCK)) {
 464                 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
 465                 *stat = 0;
 466                 return 0;
 467         }
 468         ASSERT(args.len == 1);
 469         cur->bc_private.b.firstblock = args.fsbno;
 470         cur->bc_private.b.allocated++;
 471         cur->bc_private.b.ip->i_d.di_nblocks++;
 472         xfs_trans_log_inode(args.tp, cur->bc_private.b.ip, XFS_ILOG_CORE);
 473         xfs_trans_mod_dquot_byino(args.tp, cur->bc_private.b.ip,
 474                         XFS_TRANS_DQ_BCOUNT, 1L);
 475
 476         new->l = cpu_to_be64(args.fsbno);
 477
 478         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
 479         *stat = 1;
 480         return 0;
 481
 482  error0:
 483         XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
 484         return error;
 485 }
 486
 487 STATIC int
 488 xfs_bmbt_free_block(
 489         struct xfs_btree_cur    *cur,
 490         struct xfs_buf          *bp)
 491 {
 492         struct xfs_mount        *mp = cur->bc_mp;
 493         struct xfs_inode        *ip = cur->bc_private.b.ip;
 494         struct xfs_trans        *tp = cur->bc_tp;
 495         xfs_fsblock_t           fsbno = XFS_DADDR_TO_FSB(mp, XFS_BUF_ADDR(bp));
 496         struct xfs_owner_info   oinfo;
 497
 498         xfs_rmap_ino_bmbt_owner(&oinfo, ip->i_ino, cur->bc_private.b.whichfork);
 499         xfs_bmap_add_free(mp, cur->bc_private.b.dfops, fsbno, 1, &oinfo);
 500         ip->i_d.di_nblocks--;
 501
 502         xfs_trans_log_inode(tp, ip, XFS_ILOG_CORE);
 503         xfs_trans_mod_dquot_byino(tp, ip, XFS_TRANS_DQ_BCOUNT, -1L);
 504         return 0;
 505 }
 506
 507 STATIC int
 508 xfs_bmbt_get_minrecs(
 509         struct xfs_btree_cur    *cur,
 510         int                     level)
 511 {
 512         if (level == cur->bc_nlevels - 1) {
 513                 struct xfs_ifork        *ifp;
 514
 515                 ifp = XFS_IFORK_PTR(cur->bc_private.b.ip,
 516                                     cur->bc_private.b.whichfork);
 517
 518                 return xfs_bmbt_maxrecs(cur->bc_mp,
 519                                         ifp->if_broot_bytes, level == 0) / 2;
 520         }
 521
 522         return cur->bc_mp->m_bmap_dmnr[level != 0];
 523 }
 524
 525 int
 526 xfs_bmbt_get_maxrecs(
 527         struct xfs_btree_cur    *cur,
 528         int                     level)
 529 {
 530         if (level == cur->bc_nlevels - 1) {
 531                 struct xfs_ifork        *ifp;
 532
 533                 ifp = XFS_IFORK_PTR(cur->bc_private.b.ip,
 534                                     cur->bc_private.b.whichfork);
 535
 536                 return xfs_bmbt_maxrecs(cur->bc_mp,
 537                                         ifp->if_broot_bytes, level == 0);
 538         }
 539
 540         return cur->bc_mp->m_bmap_dmxr[level != 0];
 541
 542 }
 543
 544 /*
 545  * Get the maximum records we could store in the on-disk format.
 546  *
 547  * For non-root nodes this is equivalent to xfs_bmbt_get_maxrecs, but
 548  * for the root node this checks the available space in the dinode fork
 549  * so that we can resize the in-memory buffer to match it.  After a
 550  * resize to the maximum size this function returns the same value
 551  * as xfs_bmbt_get_maxrecs for the root node, too.
 552  */
 553 STATIC int
 554 xfs_bmbt_get_dmaxrecs(
 555         struct xfs_btree_cur    *cur,
 556         int                     level)
 557 {
 558         if (level != cur->bc_nlevels - 1)
 559                 return cur->bc_mp->m_bmap_dmxr[level != 0];
 560         return xfs_bmdr_maxrecs(cur->bc_private.b.forksize, level == 0);
 561 }
 562
 563 STATIC void
 564 xfs_bmbt_init_key_from_rec(
 565         union xfs_btree_key     *key,
 566         union xfs_btree_rec     *rec)
 567 {
 568         key->bmbt.br_startoff =
 569                 cpu_to_be64(xfs_bmbt_disk_get_startoff(&rec->bmbt));
 570 }
 571
 572 STATIC void
 573 xfs_bmbt_init_rec_from_cur(
 574         struct xfs_btree_cur    *cur,
 575         union xfs_btree_rec     *rec)
 576 {
 577         xfs_bmbt_disk_set_all(&rec->bmbt, &cur->bc_rec.b);
 578 }
 579
 580 STATIC void
 581 xfs_bmbt_init_ptr_from_cur(
 582         struct xfs_btree_cur    *cur,
 583         union xfs_btree_ptr     *ptr)
 584 {
 585         ptr->l = 0;
 586 }
 587
 588 STATIC int64_t
 589 xfs_bmbt_key_diff(
 590         struct xfs_btree_cur    *cur,
 591         union xfs_btree_key     *key)
 592 {
 593         return (int64_t)be64_to_cpu(key->bmbt.br_startoff) -
 594                                       cur->bc_rec.b.br_startoff;
 595 }
 596
 597 static bool
 598 xfs_bmbt_verify(
 599         struct xfs_buf          *bp)
 600 {
 601         struct xfs_mount        *mp = bp->b_target->bt_mount;
 602         struct xfs_btree_block  *block = XFS_BUF_TO_BLOCK(bp);
 603         unsigned int            level;
 604
 605         switch (block->bb_magic) {
 606         case cpu_to_be32(XFS_BMAP_CRC_MAGIC):
 607                 if (!xfs_sb_version_hascrc(&mp->m_sb))
 608                         return false;
 609                 if (!uuid_equal(&block->bb_u.l.bb_uuid, &mp->m_sb.sb_meta_uuid))
 610                         return false;
 611                 if (be64_to_cpu(block->bb_u.l.bb_blkno) != bp->b_bn)
 612                         return false;
 613                 /*
 614                  * XXX: need a better way of verifying the owner here. Right now
 615                  * just make sure there has been one set.
 616                  */
 617                 if (be64_to_cpu(block->bb_u.l.bb_owner) == 0)
 618                         return false;
 619                 /* fall through */
 620         case cpu_to_be32(XFS_BMAP_MAGIC):
 621                 break;
 622         default:
 623                 return false;
 624         }
 625
 626         /*
 627          * numrecs and level verification.
 628          *
 629          * We don't know what fork we belong to, so just verify that the level
 630          * is less than the maximum of the two. Later checks will be more
 631          * precise.
 632          */
 633         level = be16_to_cpu(block->bb_level);
 634         if (level > max(mp->m_bm_maxlevels[0], mp->m_bm_maxlevels[1]))
 635                 return false;
 636         if (be16_to_cpu(block->bb_numrecs) > mp->m_bmap_dmxr[level != 0])
 637                 return false;
 638
 639         /* sibling pointer verification */
 640         if (!block->bb_u.l.bb_leftsib ||
 641             (block->bb_u.l.bb_leftsib != cpu_to_be64(NULLFSBLOCK) &&
 642              !XFS_FSB_SANITY_CHECK(mp, be64_to_cpu(block->bb_u.l.bb_leftsib))))
 643                 return false;
 644         if (!block->bb_u.l.bb_rightsib ||
 645             (block->bb_u.l.bb_rightsib != cpu_to_be64(NULLFSBLOCK) &&
 646              !XFS_FSB_SANITY_CHECK(mp, be64_to_cpu(block->bb_u.l.bb_rightsib))))
 647                 return false;
 648
 649         return true;
 650 }
 651
 652 static void
 653 xfs_bmbt_read_verify(
 654         struct xfs_buf  *bp)
 655 {
 656         if (!xfs_btree_lblock_verify_crc(bp))
 657                 xfs_buf_ioerror(bp, -EFSBADCRC);
 658         else if (!xfs_bmbt_verify(bp))
 659                 xfs_buf_ioerror(bp, -EFSCORRUPTED);
 660
 661         if (bp->b_error) {
 662                 trace_xfs_btree_corrupt(bp, _RET_IP_);
 663                 xfs_verifier_error(bp);
 664         }
 665 }
 666
 667 static void
 668 xfs_bmbt_write_verify(
 669         struct xfs_buf  *bp)
 670 {
 671         if (!xfs_bmbt_verify(bp)) {
 672                 trace_xfs_btree_corrupt(bp, _RET_IP_);
 673                 xfs_buf_ioerror(bp, -EFSCORRUPTED);
 674                 xfs_verifier_error(bp);
 675                 return;
 676         }
 677         xfs_btree_lblock_calc_crc(bp);
 678 }
 679
 680 const struct xfs_buf_ops xfs_bmbt_buf_ops = {
 681         .name = "xfs_bmbt",
 682         .verify_read = xfs_bmbt_read_verify,
 683         .verify_write = xfs_bmbt_write_verify,
 684 };
 685
 686
 687 #if defined(DEBUG) || defined(XFS_WARN)
 688 STATIC int
 689 xfs_bmbt_keys_inorder(
 690         struct xfs_btree_cur    *cur,
 691         union xfs_btree_key     *k1,
 692         union xfs_btree_key     *k2)
 693 {
 694         return be64_to_cpu(k1->bmbt.br_startoff) <
 695                 be64_to_cpu(k2->bmbt.br_startoff);
 696 }
 697
 698 STATIC int
 699 xfs_bmbt_recs_inorder(
 700         struct xfs_btree_cur    *cur,
 701         union xfs_btree_rec     *r1,
 702         union xfs_btree_rec     *r2)
 703 {
 704         return xfs_bmbt_disk_get_startoff(&r1->bmbt) +
 705                 xfs_bmbt_disk_get_blockcount(&r1->bmbt) <=
 706                 xfs_bmbt_disk_get_startoff(&r2->bmbt);
 707 }
 708 #endif  /* DEBUG */
 709
 710 static const struct xfs_btree_ops xfs_bmbt_ops = {
 711         .rec_len                = sizeof(xfs_bmbt_rec_t),
 712         .key_len                = sizeof(xfs_bmbt_key_t),
 713
 714         .dup_cursor             = xfs_bmbt_dup_cursor,
 715         .update_cursor          = xfs_bmbt_update_cursor,
 716         .alloc_block            = xfs_bmbt_alloc_block,
 717         .free_block             = xfs_bmbt_free_block,
 718         .get_maxrecs            = xfs_bmbt_get_maxrecs,
 719         .get_minrecs            = xfs_bmbt_get_minrecs,
 720         .get_dmaxrecs           = xfs_bmbt_get_dmaxrecs,
 721         .init_key_from_rec      = xfs_bmbt_init_key_from_rec,
 722         .init_rec_from_cur      = xfs_bmbt_init_rec_from_cur,
 723         .init_ptr_from_cur      = xfs_bmbt_init_ptr_from_cur,
 724         .key_diff               = xfs_bmbt_key_diff,
 725         .buf_ops                = &xfs_bmbt_buf_ops,
 726 #if defined(DEBUG) || defined(XFS_WARN)
 727         .keys_inorder           = xfs_bmbt_keys_inorder,
 728         .recs_inorder           = xfs_bmbt_recs_inorder,
 729 #endif
 730 };
 731
 732 /*
 733  * Allocate a new bmap btree cursor.
 734  */
 735 struct xfs_btree_cur *                          /* new bmap btree cursor */
 736 xfs_bmbt_init_cursor(
 737         struct xfs_mount        *mp,            /* file system mount point */
 738         struct xfs_trans        *tp,            /* transaction pointer */
 739         struct xfs_inode        *ip,            /* inode owning the btree */
 740         int                     whichfork)      /* data or attr fork */
 741 {
 742         struct xfs_ifork        *ifp = XFS_IFORK_PTR(ip, whichfork);
 743         struct xfs_btree_cur    *cur;
 744         ASSERT(whichfork != XFS_COW_FORK);
 745
 746         cur = kmem_zone_zalloc(xfs_btree_cur_zone, KM_NOFS);
 747
 748         cur->bc_tp = tp;
 749         cur->bc_mp = mp;
 750         cur->bc_nlevels = be16_to_cpu(ifp->if_broot->bb_level) + 1;
 751         cur->bc_btnum = XFS_BTNUM_BMAP;
 752         cur->bc_blocklog = mp->m_sb.sb_blocklog;
 753         cur->bc_statoff = XFS_STATS_CALC_INDEX(xs_bmbt_2);
 754
 755         cur->bc_ops = &xfs_bmbt_ops;
 756         cur->bc_flags = XFS_BTREE_LONG_PTRS | XFS_BTREE_ROOT_IN_INODE;
 757         if (xfs_sb_version_hascrc(&mp->m_sb))
 758                 cur->bc_flags |= XFS_BTREE_CRC_BLOCKS;
 759
 760         cur->bc_private.b.forksize = XFS_IFORK_SIZE(ip, whichfork);
 761         cur->bc_private.b.ip = ip;
 762         cur->bc_private.b.firstblock = NULLFSBLOCK;
 763         cur->bc_private.b.dfops = NULL;
 764         cur->bc_private.b.allocated = 0;
 765         cur->bc_private.b.flags = 0;
 766         cur->bc_private.b.whichfork = whichfork;
 767
 768         return cur;
 769 }
 770
 771 /*
 772  * Calculate number of records in a bmap btree block.
 773  */
 774 int
 775 xfs_bmbt_maxrecs(
 776         struct xfs_mount        *mp,
 777         int                     blocklen,
 778         int                     leaf)
 779 {
 780         blocklen -= XFS_BMBT_BLOCK_LEN(mp);
 781
 782         if (leaf)
 783                 return blocklen / sizeof(xfs_bmbt_rec_t);
 784         return blocklen / (sizeof(xfs_bmbt_key_t) + sizeof(xfs_bmbt_ptr_t));
 785 }
 786
 787 /*
 788  * Calculate number of records in a bmap btree inode root.
 789  */
 790 int
 791 xfs_bmdr_maxrecs(
 792         int                     blocklen,
 793         int                     leaf)
 794 {
 795         blocklen -= sizeof(xfs_bmdr_block_t);
 796
 797         if (leaf)
 798                 return blocklen / sizeof(xfs_bmdr_rec_t);
 799         return blocklen / (sizeof(xfs_bmdr_key_t) + sizeof(xfs_bmdr_ptr_t));
 800 }
 801
 802 /*
 803  * Change the owner of a btree format fork fo the inode passed in. Change it to
 804  * the owner of that is passed in so that we can change owners before or after
 805  * we switch forks between inodes. The operation that the caller is doing will
 806  * determine whether is needs to change owner before or after the switch.
 807  *
 808  * For demand paged transactional modification, the fork switch should be done
 809  * after reading in all the blocks, modifying them and pinning them in the
 810  * transaction. For modification when the buffers are already pinned in memory,
 811  * the fork switch can be done before changing the owner as we won't need to
 812  * validate the owner until the btree buffers are unpinned and writes can occur
 813  * again.
 814  *
 815  * For recovery based ownership change, there is no transactional context and
 816  * so a buffer list must be supplied so that we can record the buffers that we
 817  * modified for the caller to issue IO on.
 818  */
 819 int
 820 xfs_bmbt_change_owner(
 821         struct xfs_trans        *tp,
 822         struct xfs_inode        *ip,
 823         int                     whichfork,
 824         xfs_ino_t               new_owner,
 825         struct list_head        *buffer_list)
 826 {
 827         struct xfs_btree_cur    *cur;
 828         int                     error;
 829
 830         ASSERT(tp || buffer_list);
 831         ASSERT(!(tp && buffer_list));
 832         if (whichfork == XFS_DATA_FORK)
 833                 ASSERT(ip->i_d.di_format == XFS_DINODE_FMT_BTREE);
 834         else
 835                 ASSERT(ip->i_d.di_aformat == XFS_DINODE_FMT_BTREE);
 836
 837         cur = xfs_bmbt_init_cursor(ip->i_mount, tp, ip, whichfork);
 838         if (!cur)
 839                 return -ENOMEM;
 840
 841         error = xfs_btree_change_owner(cur, new_owner, buffer_list);
 842         xfs_btree_del_cursor(cur, error ? XFS_BTREE_ERROR : XFS_BTREE_NOERROR);
 843         return error;
 844 }