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 <xfs.h>
  19
  20 /*
  21  * Determine the extent state.
  22  */
  23 /* ARGSUSED */
  24 STATIC xfs_exntst_t
  25 xfs_extent_state(
  26         xfs_filblks_t           blks,
  27         int                     extent_flag)
  28 {
  29         if (extent_flag) {
  30                 ASSERT(blks != 0);      /* saved for DMIG */
  31                 return XFS_EXT_UNWRITTEN;
  32         }
  33         return XFS_EXT_NORM;
  34 }
  35
  36 /*
  37  * Convert on-disk form of btree root to in-memory form.
  38  */
  39 void
  40 xfs_bmdr_to_bmbt(
  41         struct xfs_mount        *mp,
  42         xfs_bmdr_block_t        *dblock,
  43         int                     dblocklen,
  44         struct xfs_btree_block  *rblock,
  45         int                     rblocklen)
  46 {
  47         int                     dmxr;
  48         xfs_bmbt_key_t          *fkp;
  49         __be64                  *fpp;
  50         xfs_bmbt_key_t          *tkp;
  51         __be64                  *tpp;
  52
  53         rblock->bb_magic = cpu_to_be32(XFS_BMAP_MAGIC);
  54         rblock->bb_level = dblock->bb_level;
  55         ASSERT(be16_to_cpu(rblock->bb_level) > 0);
  56         rblock->bb_numrecs = dblock->bb_numrecs;
  57         rblock->bb_u.l.bb_leftsib = cpu_to_be64(NULLDFSBNO);
  58         rblock->bb_u.l.bb_rightsib = cpu_to_be64(NULLDFSBNO);
  59         dmxr = xfs_bmdr_maxrecs(mp, dblocklen, 0);
  60         fkp = XFS_BMDR_KEY_ADDR(dblock, 1);
  61         tkp = XFS_BMBT_KEY_ADDR(mp, rblock, 1);
  62         fpp = XFS_BMDR_PTR_ADDR(dblock, 1, dmxr);
  63         tpp = XFS_BMAP_BROOT_PTR_ADDR(mp, rblock, 1, rblocklen);
  64         dmxr = be16_to_cpu(dblock->bb_numrecs);
  65         memcpy(tkp, fkp, sizeof(*fkp) * dmxr);
  66         memcpy(tpp, fpp, sizeof(*fpp) * dmxr);
  67 }
  68
  69 /*
  70  * Convert a compressed bmap extent record to an uncompressed form.
  71  * This code must be in sync with the routines xfs_bmbt_get_startoff,
  72  * xfs_bmbt_get_startblock, xfs_bmbt_get_blockcount and xfs_bmbt_get_state.
  73  */
  74
  75 STATIC_INLINE void
  76 __xfs_bmbt_get_all(
  77                 __uint64_t l0,
  78                 __uint64_t l1,
  79                 xfs_bmbt_irec_t *s)
  80 {
  81         int     ext_flag;
  82         xfs_exntst_t st;
  83
  84         ext_flag = (int)(l0 >> (64 - BMBT_EXNTFLAG_BITLEN));
  85         s->br_startoff = ((xfs_fileoff_t)l0 &
  86                            XFS_MASK64LO(64 - BMBT_EXNTFLAG_BITLEN)) >> 9;
  87 #if XFS_BIG_BLKNOS
  88         s->br_startblock = (((xfs_fsblock_t)l0 & XFS_MASK64LO(9)) << 43) |
  89                            (((xfs_fsblock_t)l1) >> 21);
  90 #else
  91 #ifdef DEBUG
  92         {
  93                 xfs_dfsbno_t    b;
  94
  95                 b = (((xfs_dfsbno_t)l0 & XFS_MASK64LO(9)) << 43) |
  96                     (((xfs_dfsbno_t)l1) >> 21);
  97                 ASSERT((b >> 32) == 0 || ISNULLDSTARTBLOCK(b));
  98                 s->br_startblock = (xfs_fsblock_t)b;
  99         }
 100 #else   /* !DEBUG */
 101         s->br_startblock = (xfs_fsblock_t)(((xfs_dfsbno_t)l1) >> 21);
 102 #endif  /* DEBUG */
 103 #endif  /* XFS_BIG_BLKNOS */
 104         s->br_blockcount = (xfs_filblks_t)(l1 & XFS_MASK64LO(21));
 105         /* This is xfs_extent_state() in-line */
 106         if (ext_flag) {
 107                 ASSERT(s->br_blockcount != 0);  /* saved for DMIG */
 108                 st = XFS_EXT_UNWRITTEN;
 109         } else
 110                 st = XFS_EXT_NORM;
 111         s->br_state = st;
 112 }
 113
 114 void
 115 xfs_bmbt_get_all(
 116         xfs_bmbt_rec_host_t *r,
 117         xfs_bmbt_irec_t *s)
 118 {
 119         __xfs_bmbt_get_all(r->l0, r->l1, s);
 120 }
 121
 122 /*
 123  * Extract the blockcount field from an in memory bmap extent record.
 124  */
 125 xfs_filblks_t
 126 xfs_bmbt_get_blockcount(
 127         xfs_bmbt_rec_host_t     *r)
 128 {
 129         return (xfs_filblks_t)(r->l1 & XFS_MASK64LO(21));
 130 }
 131
 132 /*
 133  * Extract the startblock field from an in memory bmap extent record.
 134  */
 135 xfs_fsblock_t
 136 xfs_bmbt_get_startblock(
 137         xfs_bmbt_rec_host_t     *r)
 138 {
 139 #if XFS_BIG_BLKNOS
 140         return (((xfs_fsblock_t)r->l0 & XFS_MASK64LO(9)) << 43) |
 141                (((xfs_fsblock_t)r->l1) >> 21);
 142 #else
 143 #ifdef DEBUG
 144         xfs_dfsbno_t    b;
 145
 146         b = (((xfs_dfsbno_t)r->l0 & XFS_MASK64LO(9)) << 43) |
 147             (((xfs_dfsbno_t)r->l1) >> 21);
 148         ASSERT((b >> 32) == 0 || ISNULLDSTARTBLOCK(b));
 149         return (xfs_fsblock_t)b;
 150 #else   /* !DEBUG */
 151         return (xfs_fsblock_t)(((xfs_dfsbno_t)r->l1) >> 21);
 152 #endif  /* DEBUG */
 153 #endif  /* XFS_BIG_BLKNOS */
 154 }
 155
 156 /*
 157  * Extract the startoff field from an in memory bmap extent record.
 158  */
 159 xfs_fileoff_t
 160 xfs_bmbt_get_startoff(
 161         xfs_bmbt_rec_host_t     *r)
 162 {
 163         return ((xfs_fileoff_t)r->l0 &
 164                  XFS_MASK64LO(64 - BMBT_EXNTFLAG_BITLEN)) >> 9;
 165 }
 166
 167 xfs_exntst_t
 168 xfs_bmbt_get_state(
 169         xfs_bmbt_rec_host_t     *r)
 170 {
 171         int     ext_flag;
 172
 173         ext_flag = (int)((r->l0) >> (64 - BMBT_EXNTFLAG_BITLEN));
 174         return xfs_extent_state(xfs_bmbt_get_blockcount(r),
 175                                 ext_flag);
 176 }
 177
 178 /* Endian flipping versions of the bmbt extraction functions */
 179 void
 180 xfs_bmbt_disk_get_all(
 181         xfs_bmbt_rec_t  *r,
 182         xfs_bmbt_irec_t *s)
 183 {
 184         __xfs_bmbt_get_all(be64_to_cpu(r->l0), be64_to_cpu(r->l1), s);
 185 }
 186
 187 /*
 188  * Extract the blockcount field from an on disk bmap extent record.
 189  */
 190 xfs_filblks_t
 191 xfs_bmbt_disk_get_blockcount(
 192         xfs_bmbt_rec_t  *r)
 193 {
 194         return (xfs_filblks_t)(be64_to_cpu(r->l1) & XFS_MASK64LO(21));
 195 }
 196
 197 /*
 198  * Extract the startoff field from a disk format bmap extent record.
 199  */
 200 xfs_fileoff_t
 201 xfs_bmbt_disk_get_startoff(
 202         xfs_bmbt_rec_t  *r)
 203 {
 204         return ((xfs_fileoff_t)be64_to_cpu(r->l0) &
 205                  XFS_MASK64LO(64 - BMBT_EXNTFLAG_BITLEN)) >> 9;
 206 }
 207
 208
 209 /*
 210  * Set all the fields in a bmap extent record from the arguments.
 211  */
 212 void
 213 xfs_bmbt_set_allf(
 214         xfs_bmbt_rec_host_t     *r,
 215         xfs_fileoff_t           startoff,
 216         xfs_fsblock_t           startblock,
 217         xfs_filblks_t           blockcount,
 218         xfs_exntst_t            state)
 219 {
 220         int             extent_flag = (state == XFS_EXT_NORM) ? 0 : 1;
 221
 222         ASSERT(state == XFS_EXT_NORM || state == XFS_EXT_UNWRITTEN);
 223         ASSERT((startoff & XFS_MASK64HI(64-BMBT_STARTOFF_BITLEN)) == 0);
 224         ASSERT((blockcount & XFS_MASK64HI(64-BMBT_BLOCKCOUNT_BITLEN)) == 0);
 225
 226 #if XFS_BIG_BLKNOS
 227         ASSERT((startblock & XFS_MASK64HI(64-BMBT_STARTBLOCK_BITLEN)) == 0);
 228
 229         r->l0 = ((xfs_bmbt_rec_base_t)extent_flag << 63) |
 230                 ((xfs_bmbt_rec_base_t)startoff << 9) |
 231                 ((xfs_bmbt_rec_base_t)startblock >> 43);
 232         r->l1 = ((xfs_bmbt_rec_base_t)startblock << 21) |
 233                 ((xfs_bmbt_rec_base_t)blockcount &
 234                 (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
 235 #else   /* !XFS_BIG_BLKNOS */
 236         if (ISNULLSTARTBLOCK(startblock)) {
 237                 r->l0 = ((xfs_bmbt_rec_base_t)extent_flag << 63) |
 238                         ((xfs_bmbt_rec_base_t)startoff << 9) |
 239                          (xfs_bmbt_rec_base_t)XFS_MASK64LO(9);
 240                 r->l1 = XFS_MASK64HI(11) |
 241                           ((xfs_bmbt_rec_base_t)startblock << 21) |
 242                           ((xfs_bmbt_rec_base_t)blockcount &
 243                            (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
 244         } else {
 245                 r->l0 = ((xfs_bmbt_rec_base_t)extent_flag << 63) |
 246                         ((xfs_bmbt_rec_base_t)startoff << 9);
 247                 r->l1 = ((xfs_bmbt_rec_base_t)startblock << 21) |
 248                          ((xfs_bmbt_rec_base_t)blockcount &
 249                          (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
 250         }
 251 #endif  /* XFS_BIG_BLKNOS */
 252 }
 253
 254 /*
 255  * Set all the fields in a bmap extent record from the uncompressed form.
 256  */
 257 void
 258 xfs_bmbt_set_all(
 259         xfs_bmbt_rec_host_t *r,
 260         xfs_bmbt_irec_t *s)
 261 {
 262         xfs_bmbt_set_allf(r, s->br_startoff, s->br_startblock,
 263                              s->br_blockcount, s->br_state);
 264 }
 265
 266
 267 /*
 268  * Set all the fields in a disk format bmap extent record from the arguments.
 269  */
 270 void
 271 xfs_bmbt_disk_set_allf(
 272         xfs_bmbt_rec_t          *r,
 273         xfs_fileoff_t           startoff,
 274         xfs_fsblock_t           startblock,
 275         xfs_filblks_t           blockcount,
 276         xfs_exntst_t            state)
 277 {
 278         int                     extent_flag = (state == XFS_EXT_NORM) ? 0 : 1;
 279
 280         ASSERT(state == XFS_EXT_NORM || state == XFS_EXT_UNWRITTEN);
 281         ASSERT((startoff & XFS_MASK64HI(64-BMBT_STARTOFF_BITLEN)) == 0);
 282         ASSERT((blockcount & XFS_MASK64HI(64-BMBT_BLOCKCOUNT_BITLEN)) == 0);
 283
 284 #if XFS_BIG_BLKNOS
 285         ASSERT((startblock & XFS_MASK64HI(64-BMBT_STARTBLOCK_BITLEN)) == 0);
 286
 287         r->l0 = cpu_to_be64(
 288                 ((xfs_bmbt_rec_base_t)extent_flag << 63) |
 289                  ((xfs_bmbt_rec_base_t)startoff << 9) |
 290                  ((xfs_bmbt_rec_base_t)startblock >> 43));
 291         r->l1 = cpu_to_be64(
 292                 ((xfs_bmbt_rec_base_t)startblock << 21) |
 293                  ((xfs_bmbt_rec_base_t)blockcount &
 294                   (xfs_bmbt_rec_base_t)XFS_MASK64LO(21)));
 295 #else   /* !XFS_BIG_BLKNOS */
 296         if (ISNULLSTARTBLOCK(startblock)) {
 297                 r->l0 = cpu_to_be64(
 298                         ((xfs_bmbt_rec_base_t)extent_flag << 63) |
 299                          ((xfs_bmbt_rec_base_t)startoff << 9) |
 300                           (xfs_bmbt_rec_base_t)XFS_MASK64LO(9));
 301                 r->l1 = cpu_to_be64(XFS_MASK64HI(11) |
 302                           ((xfs_bmbt_rec_base_t)startblock << 21) |
 303                           ((xfs_bmbt_rec_base_t)blockcount &
 304                            (xfs_bmbt_rec_base_t)XFS_MASK64LO(21)));
 305         } else {
 306                 r->l0 = cpu_to_be64(
 307                         ((xfs_bmbt_rec_base_t)extent_flag << 63) |
 308                          ((xfs_bmbt_rec_base_t)startoff << 9));
 309                 r->l1 = cpu_to_be64(
 310                         ((xfs_bmbt_rec_base_t)startblock << 21) |
 311                          ((xfs_bmbt_rec_base_t)blockcount &
 312                           (xfs_bmbt_rec_base_t)XFS_MASK64LO(21)));
 313         }
 314 #endif  /* XFS_BIG_BLKNOS */
 315 }
 316
 317 /*
 318  * Set all the fields in a bmap extent record from the uncompressed form.
 319  */
 320 void
 321 xfs_bmbt_disk_set_all(
 322         xfs_bmbt_rec_t  *r,
 323         xfs_bmbt_irec_t *s)
 324 {
 325         xfs_bmbt_disk_set_allf(r, s->br_startoff, s->br_startblock,
 326                                   s->br_blockcount, s->br_state);
 327 }
 328
 329 /*
 330  * Set the blockcount field in a bmap extent record.
 331  */
 332 void
 333 xfs_bmbt_set_blockcount(
 334         xfs_bmbt_rec_host_t *r,
 335         xfs_filblks_t   v)
 336 {
 337         ASSERT((v & XFS_MASK64HI(43)) == 0);
 338         r->l1 = (r->l1 & (xfs_bmbt_rec_base_t)XFS_MASK64HI(43)) |
 339                   (xfs_bmbt_rec_base_t)(v & XFS_MASK64LO(21));
 340 }
 341
 342 /*
 343  * Set the startblock field in a bmap extent record.
 344  */
 345 void
 346 xfs_bmbt_set_startblock(
 347         xfs_bmbt_rec_host_t *r,
 348         xfs_fsblock_t   v)
 349 {
 350 #if XFS_BIG_BLKNOS
 351         ASSERT((v & XFS_MASK64HI(12)) == 0);
 352         r->l0 = (r->l0 & (xfs_bmbt_rec_base_t)XFS_MASK64HI(55)) |
 353                   (xfs_bmbt_rec_base_t)(v >> 43);
 354         r->l1 = (r->l1 & (xfs_bmbt_rec_base_t)XFS_MASK64LO(21)) |
 355                   (xfs_bmbt_rec_base_t)(v << 21);
 356 #else   /* !XFS_BIG_BLKNOS */
 357         if (ISNULLSTARTBLOCK(v)) {
 358                 r->l0 |= (xfs_bmbt_rec_base_t)XFS_MASK64LO(9);
 359                 r->l1 = (xfs_bmbt_rec_base_t)XFS_MASK64HI(11) |
 360                           ((xfs_bmbt_rec_base_t)v << 21) |
 361                           (r->l1 & (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
 362         } else {
 363                 r->l0 &= ~(xfs_bmbt_rec_base_t)XFS_MASK64LO(9);
 364                 r->l1 = ((xfs_bmbt_rec_base_t)v << 21) |
 365                           (r->l1 & (xfs_bmbt_rec_base_t)XFS_MASK64LO(21));
 366         }
 367 #endif  /* XFS_BIG_BLKNOS */
 368 }
 369
 370 /*
 371  * Set the startoff field in a bmap extent record.
 372  */
 373 void
 374 xfs_bmbt_set_startoff(
 375         xfs_bmbt_rec_host_t *r,
 376         xfs_fileoff_t   v)
 377 {
 378         ASSERT((v & XFS_MASK64HI(9)) == 0);
 379         r->l0 = (r->l0 & (xfs_bmbt_rec_base_t) XFS_MASK64HI(1)) |
 380                 ((xfs_bmbt_rec_base_t)v << 9) |
 381                   (r->l0 & (xfs_bmbt_rec_base_t)XFS_MASK64LO(9));
 382 }
 383
 384 /*
 385  * Set the extent state field in a bmap extent record.
 386  */
 387 void
 388 xfs_bmbt_set_state(
 389         xfs_bmbt_rec_host_t *r,
 390         xfs_exntst_t    v)
 391 {
 392         ASSERT(v == XFS_EXT_NORM || v == XFS_EXT_UNWRITTEN);
 393         if (v == XFS_EXT_NORM)
 394                 r->l0 &= XFS_MASK64LO(64 - BMBT_EXNTFLAG_BITLEN);
 395         else
 396                 r->l0 |= XFS_MASK64HI(BMBT_EXNTFLAG_BITLEN);
 397 }
 398
 399 /*
 400  * Convert in-memory form of btree root to on-disk form.
 401  */
 402 void
 403 xfs_bmbt_to_bmdr(
 404         struct xfs_mount        *mp,
 405         struct xfs_btree_block  *rblock,
 406         int                     rblocklen,
 407         xfs_bmdr_block_t        *dblock,
 408         int                     dblocklen)
 409 {
 410         int                     dmxr;
 411         xfs_bmbt_key_t          *fkp;
 412         __be64                  *fpp;
 413         xfs_bmbt_key_t          *tkp;
 414         __be64                  *tpp;
 415
 416         ASSERT(be32_to_cpu(rblock->bb_magic) == XFS_BMAP_MAGIC);
 417         ASSERT(be64_to_cpu(rblock->bb_u.l.bb_leftsib) == NULLDFSBNO);
 418         ASSERT(be64_to_cpu(rblock->bb_u.l.bb_rightsib) == NULLDFSBNO);
 419         ASSERT(be16_to_cpu(rblock->bb_level) > 0);
 420         dblock->bb_level = rblock->bb_level;
 421         dblock->bb_numrecs = rblock->bb_numrecs;
 422         dmxr = xfs_bmdr_maxrecs(mp, dblocklen, 0);
 423         fkp = XFS_BMBT_KEY_ADDR(mp, rblock, 1);
 424         tkp = XFS_BMDR_KEY_ADDR(dblock, 1);
 425         fpp = XFS_BMAP_BROOT_PTR_ADDR(mp, rblock, 1, rblocklen);
 426         tpp = XFS_BMDR_PTR_ADDR(dblock, 1, dmxr);
 427         dmxr = be16_to_cpu(dblock->bb_numrecs);
 428         memcpy(tkp, fkp, sizeof(*fkp) * dmxr);
 429         memcpy(tpp, fpp, sizeof(*fpp) * dmxr);
 430 }
 431
 432 /*
 433  * Check extent records, which have just been read, for
 434  * any bit in the extent flag field. ASSERT on debug
 435  * kernels, as this condition should not occur.
 436  * Return an error condition (1) if any flags found,
 437  * otherwise return 0.
 438  */
 439
 440 int
 441 xfs_check_nostate_extents(
 442         xfs_ifork_t             *ifp,
 443         xfs_extnum_t            idx,
 444         xfs_extnum_t            num)
 445 {
 446         for (; num > 0; num--, idx++) {
 447                 xfs_bmbt_rec_host_t *ep = xfs_iext_get_ext(ifp, idx);
 448                 if ((ep->l0 >>
 449                      (64 - BMBT_EXNTFLAG_BITLEN)) != 0) {
 450                         ASSERT(0);
 451                         return 1;
 452                 }
 453         }
 454         return 0;
 455 }
 456
 457
 458 STATIC struct xfs_btree_cur *
 459 xfs_bmbt_dup_cursor(
 460         struct xfs_btree_cur    *cur)
 461 {
 462         struct xfs_btree_cur    *new;
 463
 464         new = xfs_bmbt_init_cursor(cur->bc_mp, cur->bc_tp,
 465                         cur->bc_private.b.ip, cur->bc_private.b.whichfork);
 466
 467         /*
 468          * Copy the firstblock, flist, and flags values,
 469          * since init cursor doesn't get them.
 470          */
 471         new->bc_private.b.firstblock = cur->bc_private.b.firstblock;
 472         new->bc_private.b.flist = cur->bc_private.b.flist;
 473         new->bc_private.b.flags = cur->bc_private.b.flags;
 474
 475         return new;
 476 }
 477
 478 STATIC void
 479 xfs_bmbt_update_cursor(
 480         struct xfs_btree_cur    *src,
 481         struct xfs_btree_cur    *dst)
 482 {
 483         ASSERT((dst->bc_private.b.firstblock != NULLFSBLOCK) ||
 484                (dst->bc_private.b.ip->i_d.di_flags & XFS_DIFLAG_REALTIME));
 485         ASSERT(dst->bc_private.b.flist == src->bc_private.b.flist);
 486
 487         dst->bc_private.b.allocated += src->bc_private.b.allocated;
 488         dst->bc_private.b.firstblock = src->bc_private.b.firstblock;
 489
 490         src->bc_private.b.allocated = 0;
 491 }
 492
 493 STATIC int
 494 xfs_bmbt_alloc_block(
 495         struct xfs_btree_cur    *cur,
 496         union xfs_btree_ptr     *start,
 497         union xfs_btree_ptr     *new,
 498         int                     length,
 499         int                     *stat)
 500 {
 501         xfs_alloc_arg_t         args;           /* block allocation args */
 502         int                     error;          /* error return value */
 503
 504         memset(&args, 0, sizeof(args));
 505         args.tp = cur->bc_tp;
 506         args.mp = cur->bc_mp;
 507         args.fsbno = cur->bc_private.b.firstblock;
 508         args.firstblock = args.fsbno;
 509
 510         if (args.fsbno == NULLFSBLOCK) {
 511                 args.fsbno = be64_to_cpu(start->l);
 512                 args.type = XFS_ALLOCTYPE_START_BNO;
 513                 /*
 514                  * Make sure there is sufficient room left in the AG to
 515                  * complete a full tree split for an extent insert.  If
 516                  * we are converting the middle part of an extent then
 517                  * we may need space for two tree splits.
 518                  *
 519                  * We are relying on the caller to make the correct block
 520                  * reservation for this operation to succeed.  If the
 521                  * reservation amount is insufficient then we may fail a
 522                  * block allocation here and corrupt the filesystem.
 523                  */
 524                 args.minleft = xfs_trans_get_block_res(args.tp);
 525         } else if (cur->bc_private.b.flist->xbf_low) {
 526                 args.type = XFS_ALLOCTYPE_START_BNO;
 527         } else {
 528                 args.type = XFS_ALLOCTYPE_NEAR_BNO;
 529         }
 530
 531         args.minlen = args.maxlen = args.prod = 1;
 532         args.wasdel = cur->bc_private.b.flags & XFS_BTCUR_BPRV_WASDEL;
 533         if (!args.wasdel && xfs_trans_get_block_res(args.tp) == 0) {
 534                 error = XFS_ERROR(ENOSPC);
 535                 goto error0;
 536         }
 537         error = xfs_alloc_vextent(&args);
 538         if (error)
 539                 goto error0;
 540
 541         if (args.fsbno == NULLFSBLOCK && args.minleft) {
 542                 /*
 543                  * Could not find an AG with enough free space to satisfy
 544                  * a full btree split.  Try again without minleft and if
 545                  * successful activate the lowspace algorithm.
 546                  */
 547                 args.fsbno = 0;
 548                 args.type = XFS_ALLOCTYPE_FIRST_AG;
 549                 args.minleft = 0;
 550                 error = xfs_alloc_vextent(&args);
 551                 if (error)
 552                         goto error0;
 553                 cur->bc_private.b.flist->xbf_low = 1;
 554         }
 555         if (args.fsbno == NULLFSBLOCK) {
 556                 XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
 557                 *stat = 0;
 558                 return 0;
 559         }
 560         ASSERT(args.len == 1);
 561         cur->bc_private.b.firstblock = args.fsbno;
 562         cur->bc_private.b.allocated++;
 563         cur->bc_private.b.ip->i_d.di_nblocks++;
 564         xfs_trans_log_inode(args.tp, cur->bc_private.b.ip, XFS_ILOG_CORE);
 565         XFS_TRANS_MOD_DQUOT_BYINO(args.mp, args.tp, cur->bc_private.b.ip,
 566                         XFS_TRANS_DQ_BCOUNT, 1L);
 567
 568         new->l = cpu_to_be64(args.fsbno);
 569
 570         XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
 571         *stat = 1;
 572         return 0;
 573
 574  error0:
 575         XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
 576         return error;
 577 }
 578
 579 STATIC int
 580 xfs_bmbt_free_block(
 581         struct xfs_btree_cur    *cur,
 582         struct xfs_buf          *bp)
 583 {
 584         struct xfs_mount        *mp = cur->bc_mp;
 585         struct xfs_inode        *ip = cur->bc_private.b.ip;
 586         struct xfs_trans        *tp = cur->bc_tp;
 587         xfs_fsblock_t           fsbno = XFS_DADDR_TO_FSB(mp, XFS_BUF_ADDR(bp));
 588
 589         xfs_bmap_add_free(fsbno, 1, cur->bc_private.b.flist, mp);
 590         ip->i_d.di_nblocks--;
 591
 592         xfs_trans_log_inode(tp, ip, XFS_ILOG_CORE);
 593         XFS_TRANS_MOD_DQUOT_BYINO(mp, tp, ip, XFS_TRANS_DQ_BCOUNT, -1L);
 594         xfs_trans_binval(tp, bp);
 595         return 0;
 596 }
 597
 598 STATIC int
 599 xfs_bmbt_get_minrecs(
 600         struct xfs_btree_cur    *cur,
 601         int                     level)
 602 {
 603         if (level == cur->bc_nlevels - 1) {
 604                 struct xfs_ifork        *ifp;
 605
 606                 ifp = XFS_IFORK_PTR(cur->bc_private.b.ip,
 607                                     cur->bc_private.b.whichfork);
 608
 609                 return xfs_bmbt_maxrecs(cur->bc_mp,
 610                                         ifp->if_broot_bytes, level == 0) / 2;
 611         }
 612
 613         return cur->bc_mp->m_bmap_dmnr[level != 0];
 614 }
 615
 616 int
 617 xfs_bmbt_get_maxrecs(
 618         struct xfs_btree_cur    *cur,
 619         int                     level)
 620 {
 621         if (level == cur->bc_nlevels - 1) {
 622                 struct xfs_ifork        *ifp;
 623
 624                 ifp = XFS_IFORK_PTR(cur->bc_private.b.ip,
 625                                     cur->bc_private.b.whichfork);
 626
 627                 return xfs_bmbt_maxrecs(cur->bc_mp,
 628                                         ifp->if_broot_bytes, level == 0);
 629         }
 630
 631         return cur->bc_mp->m_bmap_dmxr[level != 0];
 632
 633 }
 634
 635 /*
 636  * Get the maximum records we could store in the on-disk format.
 637  *
 638  * For non-root nodes this is equivalent to xfs_bmbt_get_maxrecs, but
 639  * for the root node this checks the available space in the dinode fork
 640  * so that we can resize the in-memory buffer to match it.  After a
 641  * resize to the maximum size this function returns the same value
 642  * as xfs_bmbt_get_maxrecs for the root node, too.
 643  */
 644 STATIC int
 645 xfs_bmbt_get_dmaxrecs(
 646         struct xfs_btree_cur    *cur,
 647         int                     level)
 648 {
 649         if (level != cur->bc_nlevels - 1)
 650                 return cur->bc_mp->m_bmap_dmxr[level != 0];
 651         return xfs_bmdr_maxrecs(cur->bc_mp, cur->bc_private.b.forksize,
 652                                 level == 0);
 653 }
 654
 655 STATIC void
 656 xfs_bmbt_init_key_from_rec(
 657         union xfs_btree_key     *key,
 658         union xfs_btree_rec     *rec)
 659 {
 660         key->bmbt.br_startoff =
 661                 cpu_to_be64(xfs_bmbt_disk_get_startoff(&rec->bmbt));
 662 }
 663
 664 STATIC void
 665 xfs_bmbt_init_rec_from_key(
 666         union xfs_btree_key     *key,
 667         union xfs_btree_rec     *rec)
 668 {
 669         ASSERT(key->bmbt.br_startoff != 0);
 670
 671         xfs_bmbt_disk_set_allf(&rec->bmbt, be64_to_cpu(key->bmbt.br_startoff),
 672                                0, 0, XFS_EXT_NORM);
 673 }
 674
 675 STATIC void
 676 xfs_bmbt_init_rec_from_cur(
 677         struct xfs_btree_cur    *cur,
 678         union xfs_btree_rec     *rec)
 679 {
 680         xfs_bmbt_disk_set_all(&rec->bmbt, &cur->bc_rec.b);
 681 }
 682
 683 STATIC void
 684 xfs_bmbt_init_ptr_from_cur(
 685         struct xfs_btree_cur    *cur,
 686         union xfs_btree_ptr     *ptr)
 687 {
 688         ptr->l = 0;
 689 }
 690
 691 STATIC __int64_t
 692 xfs_bmbt_key_diff(
 693         struct xfs_btree_cur    *cur,
 694         union xfs_btree_key     *key)
 695 {
 696         return (__int64_t)be64_to_cpu(key->bmbt.br_startoff) -
 697                                       cur->bc_rec.b.br_startoff;
 698 }
 699
 700 #ifdef DEBUG
 701 STATIC int
 702 xfs_bmbt_keys_inorder(
 703         struct xfs_btree_cur    *cur,
 704         union xfs_btree_key     *k1,
 705         union xfs_btree_key     *k2)
 706 {
 707         return be64_to_cpu(k1->bmbt.br_startoff) <
 708                 be64_to_cpu(k2->bmbt.br_startoff);
 709 }
 710
 711 STATIC int
 712 xfs_bmbt_recs_inorder(
 713         struct xfs_btree_cur    *cur,
 714         union xfs_btree_rec     *r1,
 715         union xfs_btree_rec     *r2)
 716 {
 717         return xfs_bmbt_disk_get_startoff(&r1->bmbt) +
 718                 xfs_bmbt_disk_get_blockcount(&r1->bmbt) <=
 719                 xfs_bmbt_disk_get_startoff(&r2->bmbt);
 720 }
 721 #endif  /* DEBUG */
 722
 723 #ifdef XFS_BTREE_TRACE
 724 ktrace_t        *xfs_bmbt_trace_buf;
 725
 726 STATIC void
 727 xfs_bmbt_trace_enter(
 728         struct xfs_btree_cur    *cur,
 729         const char              *func,
 730         char                    *s,
 731         int                     type,
 732         int                     line,
 733         __psunsigned_t          a0,
 734         __psunsigned_t          a1,
 735         __psunsigned_t          a2,
 736         __psunsigned_t          a3,
 737         __psunsigned_t          a4,
 738         __psunsigned_t          a5,
 739         __psunsigned_t          a6,
 740         __psunsigned_t          a7,
 741         __psunsigned_t          a8,
 742         __psunsigned_t          a9,
 743         __psunsigned_t          a10)
 744 {
 745         struct xfs_inode        *ip = cur->bc_private.b.ip;
 746         int                     whichfork = cur->bc_private.b.whichfork;
 747
 748         ktrace_enter(xfs_bmbt_trace_buf,
 749                 (void *)((__psint_t)type | (whichfork << 8) | (line << 16)),
 750                 (void *)func, (void *)s, (void *)ip, (void *)cur,
 751                 (void *)a0, (void *)a1, (void *)a2, (void *)a3,
 752                 (void *)a4, (void *)a5, (void *)a6, (void *)a7,
 753                 (void *)a8, (void *)a9, (void *)a10);
 754         ktrace_enter(ip->i_btrace,
 755                 (void *)((__psint_t)type | (whichfork << 8) | (line << 16)),
 756                 (void *)func, (void *)s, (void *)ip, (void *)cur,
 757                 (void *)a0, (void *)a1, (void *)a2, (void *)a3,
 758                 (void *)a4, (void *)a5, (void *)a6, (void *)a7,
 759                 (void *)a8, (void *)a9, (void *)a10);
 760 }
 761
 762 STATIC void
 763 xfs_bmbt_trace_cursor(
 764         struct xfs_btree_cur    *cur,
 765         __uint32_t              *s0,
 766         __uint64_t              *l0,
 767         __uint64_t              *l1)
 768 {
 769         struct xfs_bmbt_rec_host r;
 770
 771         xfs_bmbt_set_all(&r, &cur->bc_rec.b);
 772
 773         *s0 = (cur->bc_nlevels << 24) |
 774               (cur->bc_private.b.flags << 16) |
 775                cur->bc_private.b.allocated;
 776         *l0 = r.l0;
 777         *l1 = r.l1;
 778 }
 779
 780 STATIC void
 781 xfs_bmbt_trace_key(
 782         struct xfs_btree_cur    *cur,
 783         union xfs_btree_key     *key,
 784         __uint64_t              *l0,
 785         __uint64_t              *l1)
 786 {
 787         *l0 = be64_to_cpu(key->bmbt.br_startoff);
 788         *l1 = 0;
 789 }
 790
 791 STATIC void
 792 xfs_bmbt_trace_record(
 793         struct xfs_btree_cur    *cur,
 794         union xfs_btree_rec     *rec,
 795         __uint64_t              *l0,
 796         __uint64_t              *l1,
 797         __uint64_t              *l2)
 798 {
 799         struct xfs_bmbt_irec    irec;
 800
 801         xfs_bmbt_disk_get_all(&rec->bmbt, &irec);
 802         *l0 = irec.br_startoff;
 803         *l1 = irec.br_startblock;
 804         *l2 = irec.br_blockcount;
 805 }
 806 #endif /* XFS_BTREE_TRACE */
 807
 808 static const struct xfs_btree_ops xfs_bmbt_ops = {
 809         .rec_len                = sizeof(xfs_bmbt_rec_t),
 810         .key_len                = sizeof(xfs_bmbt_key_t),
 811
 812         .dup_cursor             = xfs_bmbt_dup_cursor,
 813         .update_cursor          = xfs_bmbt_update_cursor,
 814         .alloc_block            = xfs_bmbt_alloc_block,
 815         .free_block             = xfs_bmbt_free_block,
 816         .get_maxrecs            = xfs_bmbt_get_maxrecs,
 817         .get_minrecs            = xfs_bmbt_get_minrecs,
 818         .get_dmaxrecs           = xfs_bmbt_get_dmaxrecs,
 819         .init_key_from_rec      = xfs_bmbt_init_key_from_rec,
 820         .init_rec_from_key      = xfs_bmbt_init_rec_from_key,
 821         .init_rec_from_cur      = xfs_bmbt_init_rec_from_cur,
 822         .init_ptr_from_cur      = xfs_bmbt_init_ptr_from_cur,
 823         .key_diff               = xfs_bmbt_key_diff,
 824
 825 #ifdef DEBUG
 826         .keys_inorder           = xfs_bmbt_keys_inorder,
 827         .recs_inorder           = xfs_bmbt_recs_inorder,
 828 #endif
 829
 830 #ifdef XFS_BTREE_TRACE
 831         .trace_enter            = xfs_bmbt_trace_enter,
 832         .trace_cursor           = xfs_bmbt_trace_cursor,
 833         .trace_key              = xfs_bmbt_trace_key,
 834         .trace_record           = xfs_bmbt_trace_record,
 835 #endif
 836 };
 837
 838 /*
 839  * Allocate a new bmap btree cursor.
 840  */
 841 struct xfs_btree_cur *                          /* new bmap btree cursor */
 842 xfs_bmbt_init_cursor(
 843         struct xfs_mount        *mp,            /* file system mount point */
 844         struct xfs_trans        *tp,            /* transaction pointer */
 845         struct xfs_inode        *ip,            /* inode owning the btree */
 846         int                     whichfork)      /* data or attr fork */
 847 {
 848         struct xfs_ifork        *ifp = XFS_IFORK_PTR(ip, whichfork);
 849         struct xfs_btree_cur    *cur;
 850
 851         cur = kmem_zone_zalloc(xfs_btree_cur_zone, KM_SLEEP);
 852
 853         cur->bc_tp = tp;
 854         cur->bc_mp = mp;
 855         cur->bc_nlevels = be16_to_cpu(ifp->if_broot->bb_level) + 1;
 856         cur->bc_btnum = XFS_BTNUM_BMAP;
 857         cur->bc_blocklog = mp->m_sb.sb_blocklog;
 858
 859         cur->bc_ops = &xfs_bmbt_ops;
 860         cur->bc_flags = XFS_BTREE_LONG_PTRS | XFS_BTREE_ROOT_IN_INODE;
 861
 862         cur->bc_private.b.forksize = XFS_IFORK_SIZE(ip, whichfork);
 863         cur->bc_private.b.ip = ip;
 864         cur->bc_private.b.firstblock = NULLFSBLOCK;
 865         cur->bc_private.b.flist = NULL;
 866         cur->bc_private.b.allocated = 0;
 867         cur->bc_private.b.flags = 0;
 868         cur->bc_private.b.whichfork = whichfork;
 869
 870         return cur;
 871 }
 872
 873 /*
 874  * Calculate number of records in a bmap btree block.
 875  */
 876 int
 877 xfs_bmbt_maxrecs(
 878         struct xfs_mount        *mp,
 879         int                     blocklen,
 880         int                     leaf)
 881 {
 882         blocklen -= XFS_BMBT_BLOCK_LEN(mp);
 883
 884         if (leaf)
 885                 return blocklen / sizeof(xfs_bmbt_rec_t);
 886         return blocklen / (sizeof(xfs_bmbt_key_t) + sizeof(xfs_bmbt_ptr_t));
 887 }
 888
 889 /*
 890  * Calculate number of records in a bmap btree inode root.
 891  */
 892 int
 893 xfs_bmdr_maxrecs(
 894         struct xfs_mount        *mp,
 895         int                     blocklen,
 896         int                     leaf)
 897 {
 898         blocklen -= sizeof(xfs_bmdr_block_t);
 899
 900         if (leaf)
 901                 return blocklen / sizeof(xfs_bmdr_rec_t);
 902         return blocklen / (sizeof(xfs_bmdr_key_t) + sizeof(xfs_bmdr_ptr_t));
 903 }