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