kernel/fs/xfs/libxfs/xfs_alloc.c

   1 /*
   2  * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc.
   3  * All Rights Reserved.
   4  *
   5  * This program is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU General Public License as
   7  * published by the Free Software Foundation.
   8  *
   9  * This program is distributed in the hope that it would be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write the Free Software Foundation,
  16  * Inc.,  51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  17  */
  18 #include "xfs.h"
  19 #include "xfs_fs.h"
  20 #include "xfs_format.h"
  21 #include "xfs_log_format.h"
  22 #include "xfs_shared.h"
  23 #include "xfs_trans_resv.h"
  24 #include "xfs_bit.h"
  25 #include "xfs_sb.h"
  26 #include "xfs_mount.h"
  27 #include "xfs_inode.h"
  28 #include "xfs_btree.h"
  29 #include "xfs_alloc_btree.h"
  30 #include "xfs_alloc.h"
  31 #include "xfs_extent_busy.h"
  32 #include "xfs_error.h"
  33 #include "xfs_cksum.h"
  34 #include "xfs_trace.h"
  35 #include "xfs_trans.h"
  36 #include "xfs_buf_item.h"
  37 #include "xfs_log.h"
  38
  39 struct workqueue_struct *xfs_alloc_wq;
  40
  41 #define XFS_ABSDIFF(a,b)        (((a) <= (b)) ? ((b) - (a)) : ((a) - (b)))
  42
  43 #define XFSA_FIXUP_BNO_OK       1
  44 #define XFSA_FIXUP_CNT_OK       2
  45
  46 STATIC int xfs_alloc_ag_vextent_exact(xfs_alloc_arg_t *);
  47 STATIC int xfs_alloc_ag_vextent_near(xfs_alloc_arg_t *);
  48 STATIC int xfs_alloc_ag_vextent_size(xfs_alloc_arg_t *);
  49 STATIC int xfs_alloc_ag_vextent_small(xfs_alloc_arg_t *,
  50                 xfs_btree_cur_t *, xfs_agblock_t *, xfs_extlen_t *, int *);
  51
  52 /*
  53  * Lookup the record equal to [bno, len] in the btree given by cur.
  54  */
  55 STATIC int                              /* error */
  56 xfs_alloc_lookup_eq(
  57         struct xfs_btree_cur    *cur,   /* btree cursor */
  58         xfs_agblock_t           bno,    /* starting block of extent */
  59         xfs_extlen_t            len,    /* length of extent */
  60         int                     *stat)  /* success/failure */
  61 {
  62         cur->bc_rec.a.ar_startblock = bno;
  63         cur->bc_rec.a.ar_blockcount = len;
  64         return xfs_btree_lookup(cur, XFS_LOOKUP_EQ, stat);
  65 }
  66
  67 /*
  68  * Lookup the first record greater than or equal to [bno, len]
  69  * in the btree given by cur.
  70  */
  71 int                             /* error */
  72 xfs_alloc_lookup_ge(
  73         struct xfs_btree_cur    *cur,   /* btree cursor */
  74         xfs_agblock_t           bno,    /* starting block of extent */
  75         xfs_extlen_t            len,    /* length of extent */
  76         int                     *stat)  /* success/failure */
  77 {
  78         cur->bc_rec.a.ar_startblock = bno;
  79         cur->bc_rec.a.ar_blockcount = len;
  80         return xfs_btree_lookup(cur, XFS_LOOKUP_GE, stat);
  81 }
  82
  83 /*
  84  * Lookup the first record less than or equal to [bno, len]
  85  * in the btree given by cur.
  86  */
  87 int                                     /* error */
  88 xfs_alloc_lookup_le(
  89         struct xfs_btree_cur    *cur,   /* btree cursor */
  90         xfs_agblock_t           bno,    /* starting block of extent */
  91         xfs_extlen_t            len,    /* length of extent */
  92         int                     *stat)  /* success/failure */
  93 {
  94         cur->bc_rec.a.ar_startblock = bno;
  95         cur->bc_rec.a.ar_blockcount = len;
  96         return xfs_btree_lookup(cur, XFS_LOOKUP_LE, stat);
  97 }
  98
  99 /*
 100  * Update the record referred to by cur to the value given
 101  * by [bno, len].
 102  * This either works (return 0) or gets an EFSCORRUPTED error.
 103  */
 104 STATIC int                              /* error */
 105 xfs_alloc_update(
 106         struct xfs_btree_cur    *cur,   /* btree cursor */
 107         xfs_agblock_t           bno,    /* starting block of extent */
 108         xfs_extlen_t            len)    /* length of extent */
 109 {
 110         union xfs_btree_rec     rec;
 111
 112         rec.alloc.ar_startblock = cpu_to_be32(bno);
 113         rec.alloc.ar_blockcount = cpu_to_be32(len);
 114         return xfs_btree_update(cur, &rec);
 115 }
 116
 117 /*
 118  * Get the data from the pointed-to record.
 119  */
 120 int                                     /* error */
 121 xfs_alloc_get_rec(
 122         struct xfs_btree_cur    *cur,   /* btree cursor */
 123         xfs_agblock_t           *bno,   /* output: starting block of extent */
 124         xfs_extlen_t            *len,   /* output: length of extent */
 125         int                     *stat)  /* output: success/failure */
 126 {
 127         union xfs_btree_rec     *rec;
 128         int                     error;
 129
 130         error = xfs_btree_get_rec(cur, &rec, stat);
 131         if (!error && *stat == 1) {
 132                 *bno = be32_to_cpu(rec->alloc.ar_startblock);
 133                 *len = be32_to_cpu(rec->alloc.ar_blockcount);
 134         }
 135         return error;
 136 }
 137
 138 /*
 139  * Compute aligned version of the found extent.
 140  * Takes alignment and min length into account.
 141  */
 142 STATIC void
 143 xfs_alloc_compute_aligned(
 144         xfs_alloc_arg_t *args,          /* allocation argument structure */
 145         xfs_agblock_t   foundbno,       /* starting block in found extent */
 146         xfs_extlen_t    foundlen,       /* length in found extent */
 147         xfs_agblock_t   *resbno,        /* result block number */
 148         xfs_extlen_t    *reslen)        /* result length */
 149 {
 150         xfs_agblock_t   bno;
 151         xfs_extlen_t    len;
 152
 153         /* Trim busy sections out of found extent */
 154         xfs_extent_busy_trim(args, foundbno, foundlen, &bno, &len);
 155
 156         if (args->alignment > 1 && len >= args->minlen) {
 157                 xfs_agblock_t   aligned_bno = roundup(bno, args->alignment);
 158                 xfs_extlen_t    diff = aligned_bno - bno;
 159
 160                 *resbno = aligned_bno;
 161                 *reslen = diff >= len ? 0 : len - diff;
 162         } else {
 163                 *resbno = bno;
 164                 *reslen = len;
 165         }
 166 }
 167
 168 /*
 169  * Compute best start block and diff for "near" allocations.
 170  * freelen >= wantlen already checked by caller.
 171  */
 172 STATIC xfs_extlen_t                     /* difference value (absolute) */
 173 xfs_alloc_compute_diff(
 174         xfs_agblock_t   wantbno,        /* target starting block */
 175         xfs_extlen_t    wantlen,        /* target length */
 176         xfs_extlen_t    alignment,      /* target alignment */
 177         char            userdata,       /* are we allocating data? */
 178         xfs_agblock_t   freebno,        /* freespace's starting block */
 179         xfs_extlen_t    freelen,        /* freespace's length */
 180         xfs_agblock_t   *newbnop)       /* result: best start block from free */
 181 {
 182         xfs_agblock_t   freeend;        /* end of freespace extent */
 183         xfs_agblock_t   newbno1;        /* return block number */
 184         xfs_agblock_t   newbno2;        /* other new block number */
 185         xfs_extlen_t    newlen1=0;      /* length with newbno1 */
 186         xfs_extlen_t    newlen2=0;      /* length with newbno2 */
 187         xfs_agblock_t   wantend;        /* end of target extent */
 188
 189         ASSERT(freelen >= wantlen);
 190         freeend = freebno + freelen;
 191         wantend = wantbno + wantlen;
 192         /*
 193          * We want to allocate from the start of a free extent if it is past
 194          * the desired block or if we are allocating user data and the free
 195          * extent is before desired block. The second case is there to allow
 196          * for contiguous allocation from the remaining free space if the file
 197          * grows in the short term.
 198          */
 199         if (freebno >= wantbno || (userdata && freeend < wantend)) {
 200                 if ((newbno1 = roundup(freebno, alignment)) >= freeend)
 201                         newbno1 = NULLAGBLOCK;
 202         } else if (freeend >= wantend && alignment > 1) {
 203                 newbno1 = roundup(wantbno, alignment);
 204                 newbno2 = newbno1 - alignment;
 205                 if (newbno1 >= freeend)
 206                         newbno1 = NULLAGBLOCK;
 207                 else
 208                         newlen1 = XFS_EXTLEN_MIN(wantlen, freeend - newbno1);
 209                 if (newbno2 < freebno)
 210                         newbno2 = NULLAGBLOCK;
 211                 else
 212                         newlen2 = XFS_EXTLEN_MIN(wantlen, freeend - newbno2);
 213                 if (newbno1 != NULLAGBLOCK && newbno2 != NULLAGBLOCK) {
 214                         if (newlen1 < newlen2 ||
 215                             (newlen1 == newlen2 &&
 216                              XFS_ABSDIFF(newbno1, wantbno) >
 217                              XFS_ABSDIFF(newbno2, wantbno)))
 218                                 newbno1 = newbno2;
 219                 } else if (newbno2 != NULLAGBLOCK)
 220                         newbno1 = newbno2;
 221         } else if (freeend >= wantend) {
 222                 newbno1 = wantbno;
 223         } else if (alignment > 1) {
 224                 newbno1 = roundup(freeend - wantlen, alignment);
 225                 if (newbno1 > freeend - wantlen &&
 226                     newbno1 - alignment >= freebno)
 227                         newbno1 -= alignment;
 228                 else if (newbno1 >= freeend)
 229                         newbno1 = NULLAGBLOCK;
 230         } else
 231                 newbno1 = freeend - wantlen;
 232         *newbnop = newbno1;
 233         return newbno1 == NULLAGBLOCK ? 0 : XFS_ABSDIFF(newbno1, wantbno);
 234 }
 235
 236 /*
 237  * Fix up the length, based on mod and prod.
 238  * len should be k * prod + mod for some k.
 239  * If len is too small it is returned unchanged.
 240  * If len hits maxlen it is left alone.
 241  */
 242 STATIC void
 243 xfs_alloc_fix_len(
 244         xfs_alloc_arg_t *args)          /* allocation argument structure */
 245 {
 246         xfs_extlen_t    k;
 247         xfs_extlen_t    rlen;
 248
 249         ASSERT(args->mod < args->prod);
 250         rlen = args->len;
 251         ASSERT(rlen >= args->minlen);
 252         ASSERT(rlen <= args->maxlen);
 253         if (args->prod <= 1 || rlen < args->mod || rlen == args->maxlen ||
 254             (args->mod == 0 && rlen < args->prod))
 255                 return;
 256         k = rlen % args->prod;
 257         if (k == args->mod)
 258                 return;
 259         if (k > args->mod)
 260                 rlen = rlen - (k - args->mod);
 261         else
 262                 rlen = rlen - args->prod + (args->mod - k);
 263         /* casts to (int) catch length underflows */
 264         if ((int)rlen < (int)args->minlen)
 265                 return;
 266         ASSERT(rlen >= args->minlen && rlen <= args->maxlen);
 267         ASSERT(rlen % args->prod == args->mod);
 268         args->len = rlen;
 269 }
 270
 271 /*
 272  * Fix up length if there is too little space left in the a.g.
 273  * Return 1 if ok, 0 if too little, should give up.
 274  */
 275 STATIC int
 276 xfs_alloc_fix_minleft(
 277         xfs_alloc_arg_t *args)          /* allocation argument structure */
 278 {
 279         xfs_agf_t       *agf;           /* a.g. freelist header */
 280         int             diff;           /* free space difference */
 281
 282         if (args->minleft == 0)
 283                 return 1;
 284         agf = XFS_BUF_TO_AGF(args->agbp);
 285         diff = be32_to_cpu(agf->agf_freeblks)
 286                 - args->len - args->minleft;
 287         if (diff >= 0)
 288                 return 1;
 289         args->len += diff;              /* shrink the allocated space */
 290         /* casts to (int) catch length underflows */
 291         if ((int)args->len >= (int)args->minlen)
 292                 return 1;
 293         args->agbno = NULLAGBLOCK;
 294         return 0;
 295 }
 296
 297 /*
 298  * Update the two btrees, logically removing from freespace the extent
 299  * starting at rbno, rlen blocks.  The extent is contained within the
 300  * actual (current) free extent fbno for flen blocks.
 301  * Flags are passed in indicating whether the cursors are set to the
 302  * relevant records.
 303  */
 304 STATIC int                              /* error code */
 305 xfs_alloc_fixup_trees(
 306         xfs_btree_cur_t *cnt_cur,       /* cursor for by-size btree */
 307         xfs_btree_cur_t *bno_cur,       /* cursor for by-block btree */
 308         xfs_agblock_t   fbno,           /* starting block of free extent */
 309         xfs_extlen_t    flen,           /* length of free extent */
 310         xfs_agblock_t   rbno,           /* starting block of returned extent */
 311         xfs_extlen_t    rlen,           /* length of returned extent */
 312         int             flags)          /* flags, XFSA_FIXUP_... */
 313 {
 314         int             error;          /* error code */
 315         int             i;              /* operation results */
 316         xfs_agblock_t   nfbno1;         /* first new free startblock */
 317         xfs_agblock_t   nfbno2;         /* second new free startblock */
 318         xfs_extlen_t    nflen1=0;       /* first new free length */
 319         xfs_extlen_t    nflen2=0;       /* second new free length */
 320         struct xfs_mount *mp;
 321
 322         mp = cnt_cur->bc_mp;
 323
 324         /*
 325          * Look up the record in the by-size tree if necessary.
 326          */
 327         if (flags & XFSA_FIXUP_CNT_OK) {
 328 #ifdef DEBUG
 329                 if ((error = xfs_alloc_get_rec(cnt_cur, &nfbno1, &nflen1, &i)))
 330                         return error;
 331                 XFS_WANT_CORRUPTED_RETURN(mp,
 332                         i == 1 && nfbno1 == fbno && nflen1 == flen);
 333 #endif
 334         } else {
 335                 if ((error = xfs_alloc_lookup_eq(cnt_cur, fbno, flen, &i)))
 336                         return error;
 337                 XFS_WANT_CORRUPTED_RETURN(mp, i == 1);
 338         }
 339         /*
 340          * Look up the record in the by-block tree if necessary.
 341          */
 342         if (flags & XFSA_FIXUP_BNO_OK) {
 343 #ifdef DEBUG
 344                 if ((error = xfs_alloc_get_rec(bno_cur, &nfbno1, &nflen1, &i)))
 345                         return error;
 346                 XFS_WANT_CORRUPTED_RETURN(mp,
 347                         i == 1 && nfbno1 == fbno && nflen1 == flen);
 348 #endif
 349         } else {
 350                 if ((error = xfs_alloc_lookup_eq(bno_cur, fbno, flen, &i)))
 351                         return error;
 352                 XFS_WANT_CORRUPTED_RETURN(mp, i == 1);
 353         }
 354
 355 #ifdef DEBUG
 356         if (bno_cur->bc_nlevels == 1 && cnt_cur->bc_nlevels == 1) {
 357                 struct xfs_btree_block  *bnoblock;
 358                 struct xfs_btree_block  *cntblock;
 359
 360                 bnoblock = XFS_BUF_TO_BLOCK(bno_cur->bc_bufs[0]);
 361                 cntblock = XFS_BUF_TO_BLOCK(cnt_cur->bc_bufs[0]);
 362
 363                 XFS_WANT_CORRUPTED_RETURN(mp,
 364                         bnoblock->bb_numrecs == cntblock->bb_numrecs);
 365         }
 366 #endif
 367
 368         /*
 369          * Deal with all four cases: the allocated record is contained
 370          * within the freespace record, so we can have new freespace
 371          * at either (or both) end, or no freespace remaining.
 372          */
 373         if (rbno == fbno && rlen == flen)
 374                 nfbno1 = nfbno2 = NULLAGBLOCK;
 375         else if (rbno == fbno) {
 376                 nfbno1 = rbno + rlen;
 377                 nflen1 = flen - rlen;
 378                 nfbno2 = NULLAGBLOCK;
 379         } else if (rbno + rlen == fbno + flen) {
 380                 nfbno1 = fbno;
 381                 nflen1 = flen - rlen;
 382                 nfbno2 = NULLAGBLOCK;
 383         } else {
 384                 nfbno1 = fbno;
 385                 nflen1 = rbno - fbno;
 386                 nfbno2 = rbno + rlen;
 387                 nflen2 = (fbno + flen) - nfbno2;
 388         }
 389         /*
 390          * Delete the entry from the by-size btree.
 391          */
 392         if ((error = xfs_btree_delete(cnt_cur, &i)))
 393                 return error;
 394         XFS_WANT_CORRUPTED_RETURN(mp, i == 1);
 395         /*
 396          * Add new by-size btree entry(s).
 397          */
 398         if (nfbno1 != NULLAGBLOCK) {
 399                 if ((error = xfs_alloc_lookup_eq(cnt_cur, nfbno1, nflen1, &i)))
 400                         return error;
 401                 XFS_WANT_CORRUPTED_RETURN(mp, i == 0);
 402                 if ((error = xfs_btree_insert(cnt_cur, &i)))
 403                         return error;
 404                 XFS_WANT_CORRUPTED_RETURN(mp, i == 1);
 405         }
 406         if (nfbno2 != NULLAGBLOCK) {
 407                 if ((error = xfs_alloc_lookup_eq(cnt_cur, nfbno2, nflen2, &i)))
 408                         return error;
 409                 XFS_WANT_CORRUPTED_RETURN(mp, i == 0);
 410                 if ((error = xfs_btree_insert(cnt_cur, &i)))
 411                         return error;
 412                 XFS_WANT_CORRUPTED_RETURN(mp, i == 1);
 413         }
 414         /*
 415          * Fix up the by-block btree entry(s).
 416          */
 417         if (nfbno1 == NULLAGBLOCK) {
 418                 /*
 419                  * No remaining freespace, just delete the by-block tree entry.
 420                  */
 421                 if ((error = xfs_btree_delete(bno_cur, &i)))
 422                         return error;
 423                 XFS_WANT_CORRUPTED_RETURN(mp, i == 1);
 424         } else {
 425                 /*
 426                  * Update the by-block entry to start later|be shorter.
 427                  */
 428                 if ((error = xfs_alloc_update(bno_cur, nfbno1, nflen1)))
 429                         return error;
 430         }
 431         if (nfbno2 != NULLAGBLOCK) {
 432                 /*
 433                  * 2 resulting free entries, need to add one.
 434                  */
 435                 if ((error = xfs_alloc_lookup_eq(bno_cur, nfbno2, nflen2, &i)))
 436                         return error;
 437                 XFS_WANT_CORRUPTED_RETURN(mp, i == 0);
 438                 if ((error = xfs_btree_insert(bno_cur, &i)))
 439                         return error;
 440                 XFS_WANT_CORRUPTED_RETURN(mp, i == 1);
 441         }
 442         return 0;
 443 }
 444
 445 static bool
 446 xfs_agfl_verify(
 447         struct xfs_buf  *bp)
 448 {
 449         struct xfs_mount *mp = bp->b_target->bt_mount;
 450         struct xfs_agfl *agfl = XFS_BUF_TO_AGFL(bp);
 451         int             i;
 452
 453         if (!uuid_equal(&agfl->agfl_uuid, &mp->m_sb.sb_uuid))
 454                 return false;
 455         if (be32_to_cpu(agfl->agfl_magicnum) != XFS_AGFL_MAGIC)
 456                 return false;
 457         /*
 458          * during growfs operations, the perag is not fully initialised,
 459          * so we can't use it for any useful checking. growfs ensures we can't
 460          * use it by using uncached buffers that don't have the perag attached
 461          * so we can detect and avoid this problem.
 462          */
 463         if (bp->b_pag && be32_to_cpu(agfl->agfl_seqno) != bp->b_pag->pag_agno)
 464                 return false;
 465
 466         for (i = 0; i < XFS_AGFL_SIZE(mp); i++) {
 467                 if (be32_to_cpu(agfl->agfl_bno[i]) != NULLAGBLOCK &&
 468                     be32_to_cpu(agfl->agfl_bno[i]) >= mp->m_sb.sb_agblocks)
 469                         return false;
 470         }
 471         return true;
 472 }
 473
 474 static void
 475 xfs_agfl_read_verify(
 476         struct xfs_buf  *bp)
 477 {
 478         struct xfs_mount *mp = bp->b_target->bt_mount;
 479
 480         /*
 481          * There is no verification of non-crc AGFLs because mkfs does not
 482          * initialise the AGFL to zero or NULL. Hence the only valid part of the
 483          * AGFL is what the AGF says is active. We can't get to the AGF, so we
 484          * can't verify just those entries are valid.
 485          */
 486         if (!xfs_sb_version_hascrc(&mp->m_sb))
 487                 return;
 488
 489         if (!xfs_buf_verify_cksum(bp, XFS_AGFL_CRC_OFF))
 490                 xfs_buf_ioerror(bp, -EFSBADCRC);
 491         else if (!xfs_agfl_verify(bp))
 492                 xfs_buf_ioerror(bp, -EFSCORRUPTED);
 493
 494         if (bp->b_error)
 495                 xfs_verifier_error(bp);
 496 }
 497
 498 static void
 499 xfs_agfl_write_verify(
 500         struct xfs_buf  *bp)
 501 {
 502         struct xfs_mount *mp = bp->b_target->bt_mount;
 503         struct xfs_buf_log_item *bip = bp->b_fspriv;
 504
 505         /* no verification of non-crc AGFLs */
 506         if (!xfs_sb_version_hascrc(&mp->m_sb))
 507                 return;
 508
 509         if (!xfs_agfl_verify(bp)) {
 510                 xfs_buf_ioerror(bp, -EFSCORRUPTED);
 511                 xfs_verifier_error(bp);
 512                 return;
 513         }
 514
 515         if (bip)
 516                 XFS_BUF_TO_AGFL(bp)->agfl_lsn = cpu_to_be64(bip->bli_item.li_lsn);
 517
 518         xfs_buf_update_cksum(bp, XFS_AGFL_CRC_OFF);
 519 }
 520
 521 const struct xfs_buf_ops xfs_agfl_buf_ops = {
 522         .verify_read = xfs_agfl_read_verify,
 523         .verify_write = xfs_agfl_write_verify,
 524 };
 525
 526 /*
 527  * Read in the allocation group free block array.
 528  */
 529 STATIC int                              /* error */
 530 xfs_alloc_read_agfl(
 531         xfs_mount_t     *mp,            /* mount point structure */
 532         xfs_trans_t     *tp,            /* transaction pointer */
 533         xfs_agnumber_t  agno,           /* allocation group number */
 534         xfs_buf_t       **bpp)          /* buffer for the ag free block array */
 535 {
 536         xfs_buf_t       *bp;            /* return value */
 537         int             error;
 538
 539         ASSERT(agno != NULLAGNUMBER);
 540         error = xfs_trans_read_buf(
 541                         mp, tp, mp->m_ddev_targp,
 542                         XFS_AG_DADDR(mp, agno, XFS_AGFL_DADDR(mp)),
 543                         XFS_FSS_TO_BB(mp, 1), 0, &bp, &xfs_agfl_buf_ops);
 544         if (error)
 545                 return error;
 546         xfs_buf_set_ref(bp, XFS_AGFL_REF);
 547         *bpp = bp;
 548         return 0;
 549 }
 550
 551 STATIC int
 552 xfs_alloc_update_counters(
 553         struct xfs_trans        *tp,
 554         struct xfs_perag        *pag,
 555         struct xfs_buf          *agbp,
 556         long                    len)
 557 {
 558         struct xfs_agf          *agf = XFS_BUF_TO_AGF(agbp);
 559
 560         pag->pagf_freeblks += len;
 561         be32_add_cpu(&agf->agf_freeblks, len);
 562
 563         xfs_trans_agblocks_delta(tp, len);
 564         if (unlikely(be32_to_cpu(agf->agf_freeblks) >
 565                      be32_to_cpu(agf->agf_length)))
 566                 return -EFSCORRUPTED;
 567
 568         xfs_alloc_log_agf(tp, agbp, XFS_AGF_FREEBLKS);
 569         return 0;
 570 }
 571
 572 /*
 573  * Allocation group level functions.
 574  */
 575
 576 /*
 577  * Allocate a variable extent in the allocation group agno.
 578  * Type and bno are used to determine where in the allocation group the
 579  * extent will start.
 580  * Extent's length (returned in *len) will be between minlen and maxlen,
 581  * and of the form k * prod + mod unless there's nothing that large.
 582  * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
 583  */
 584 STATIC int                      /* error */
 585 xfs_alloc_ag_vextent(
 586         xfs_alloc_arg_t *args)  /* argument structure for allocation */
 587 {
 588         int             error=0;
 589
 590         ASSERT(args->minlen > 0);
 591         ASSERT(args->maxlen > 0);
 592         ASSERT(args->minlen <= args->maxlen);
 593         ASSERT(args->mod < args->prod);
 594         ASSERT(args->alignment > 0);
 595         /*
 596          * Branch to correct routine based on the type.
 597          */
 598         args->wasfromfl = 0;
 599         switch (args->type) {
 600         case XFS_ALLOCTYPE_THIS_AG:
 601                 error = xfs_alloc_ag_vextent_size(args);
 602                 break;
 603         case XFS_ALLOCTYPE_NEAR_BNO:
 604                 error = xfs_alloc_ag_vextent_near(args);
 605                 break;
 606         case XFS_ALLOCTYPE_THIS_BNO:
 607                 error = xfs_alloc_ag_vextent_exact(args);
 608                 break;
 609         default:
 610                 ASSERT(0);
 611                 /* NOTREACHED */
 612         }
 613
 614         if (error || args->agbno == NULLAGBLOCK)
 615                 return error;
 616
 617         ASSERT(args->len >= args->minlen);
 618         ASSERT(args->len <= args->maxlen);
 619         ASSERT(!args->wasfromfl || !args->isfl);
 620         ASSERT(args->agbno % args->alignment == 0);
 621
 622         if (!args->wasfromfl) {
 623                 error = xfs_alloc_update_counters(args->tp, args->pag,
 624                                                   args->agbp,
 625                                                   -((long)(args->len)));
 626                 if (error)
 627                         return error;
 628
 629                 ASSERT(!xfs_extent_busy_search(args->mp, args->agno,
 630                                               args->agbno, args->len));
 631         }
 632
 633         if (!args->isfl) {
 634                 xfs_trans_mod_sb(args->tp, args->wasdel ?
 635                                  XFS_TRANS_SB_RES_FDBLOCKS :
 636                                  XFS_TRANS_SB_FDBLOCKS,
 637                                  -((long)(args->len)));
 638         }
 639
 640         XFS_STATS_INC(xs_allocx);
 641         XFS_STATS_ADD(xs_allocb, args->len);
 642         return error;
 643 }
 644
 645 /*
 646  * Allocate a variable extent at exactly agno/bno.
 647  * Extent's length (returned in *len) will be between minlen and maxlen,
 648  * and of the form k * prod + mod unless there's nothing that large.
 649  * Return the starting a.g. block (bno), or NULLAGBLOCK if we can't do it.
 650  */
 651 STATIC int                      /* error */
 652 xfs_alloc_ag_vextent_exact(
 653         xfs_alloc_arg_t *args)  /* allocation argument structure */
 654 {
 655         xfs_btree_cur_t *bno_cur;/* by block-number btree cursor */
 656         xfs_btree_cur_t *cnt_cur;/* by count btree cursor */
 657         int             error;
 658         xfs_agblock_t   fbno;   /* start block of found extent */
 659         xfs_extlen_t    flen;   /* length of found extent */
 660         xfs_agblock_t   tbno;   /* start block of trimmed extent */
 661         xfs_extlen_t    tlen;   /* length of trimmed extent */
 662         xfs_agblock_t   tend;   /* end block of trimmed extent */
 663         int             i;      /* success/failure of operation */
 664
 665         ASSERT(args->alignment == 1);
 666
 667         /*
 668          * Allocate/initialize a cursor for the by-number freespace btree.
 669          */
 670         bno_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
 671                                           args->agno, XFS_BTNUM_BNO);
 672
 673         /*
 674          * Lookup bno and minlen in the btree (minlen is irrelevant, really).
 675          * Look for the closest free block <= bno, it must contain bno
 676          * if any free block does.
 677          */
 678         error = xfs_alloc_lookup_le(bno_cur, args->agbno, args->minlen, &i);
 679         if (error)
 680                 goto error0;
 681         if (!i)
 682                 goto not_found;
 683
 684         /*
 685          * Grab the freespace record.
 686          */
 687         error = xfs_alloc_get_rec(bno_cur, &fbno, &flen, &i);
 688         if (error)
 689                 goto error0;
 690         XFS_WANT_CORRUPTED_GOTO(args->mp, i == 1, error0);
 691         ASSERT(fbno <= args->agbno);
 692
 693         /*
 694          * Check for overlapping busy extents.
 695          */
 696         xfs_extent_busy_trim(args, fbno, flen, &tbno, &tlen);
 697
 698         /*
 699          * Give up if the start of the extent is busy, or the freespace isn't
 700          * long enough for the minimum request.
 701          */
 702         if (tbno > args->agbno)
 703                 goto not_found;
 704         if (tlen < args->minlen)
 705                 goto not_found;
 706         tend = tbno + tlen;
 707         if (tend < args->agbno + args->minlen)
 708                 goto not_found;
 709
 710         /*
 711          * End of extent will be smaller of the freespace end and the
 712          * maximal requested end.
 713          *
 714          * Fix the length according to mod and prod if given.
 715          */
 716         args->len = XFS_AGBLOCK_MIN(tend, args->agbno + args->maxlen)
 717                                                 - args->agbno;
 718         xfs_alloc_fix_len(args);
 719         if (!xfs_alloc_fix_minleft(args))
 720                 goto not_found;
 721
 722         ASSERT(args->agbno + args->len <= tend);
 723
 724         /*
 725          * We are allocating agbno for args->len
 726          * Allocate/initialize a cursor for the by-size btree.
 727          */
 728         cnt_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
 729                 args->agno, XFS_BTNUM_CNT);
 730         ASSERT(args->agbno + args->len <=
 731                 be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length));
 732         error = xfs_alloc_fixup_trees(cnt_cur, bno_cur, fbno, flen, args->agbno,
 733                                       args->len, XFSA_FIXUP_BNO_OK);
 734         if (error) {
 735                 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
 736                 goto error0;
 737         }
 738
 739         xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
 740         xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
 741
 742         args->wasfromfl = 0;
 743         trace_xfs_alloc_exact_done(args);
 744         return 0;
 745
 746 not_found:
 747         /* Didn't find it, return null. */
 748         xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
 749         args->agbno = NULLAGBLOCK;
 750         trace_xfs_alloc_exact_notfound(args);
 751         return 0;
 752
 753 error0:
 754         xfs_btree_del_cursor(bno_cur, XFS_BTREE_ERROR);
 755         trace_xfs_alloc_exact_error(args);
 756         return error;
 757 }
 758
 759 /*
 760  * Search the btree in a given direction via the search cursor and compare
 761  * the records found against the good extent we've already found.
 762  */
 763 STATIC int
 764 xfs_alloc_find_best_extent(
 765         struct xfs_alloc_arg    *args,  /* allocation argument structure */
 766         struct xfs_btree_cur    **gcur, /* good cursor */
 767         struct xfs_btree_cur    **scur, /* searching cursor */
 768         xfs_agblock_t           gdiff,  /* difference for search comparison */
 769         xfs_agblock_t           *sbno,  /* extent found by search */
 770         xfs_extlen_t            *slen,  /* extent length */
 771         xfs_agblock_t           *sbnoa, /* aligned extent found by search */
 772         xfs_extlen_t            *slena, /* aligned extent length */
 773         int                     dir)    /* 0 = search right, 1 = search left */
 774 {
 775         xfs_agblock_t           new;
 776         xfs_agblock_t           sdiff;
 777         int                     error;
 778         int                     i;
 779
 780         /* The good extent is perfect, no need to  search. */
 781         if (!gdiff)
 782                 goto out_use_good;
 783
 784         /*
 785          * Look until we find a better one, run out of space or run off the end.
 786          */
 787         do {
 788                 error = xfs_alloc_get_rec(*scur, sbno, slen, &i);
 789                 if (error)
 790                         goto error0;
 791                 XFS_WANT_CORRUPTED_GOTO(args->mp, i == 1, error0);
 792                 xfs_alloc_compute_aligned(args, *sbno, *slen, sbnoa, slena);
 793
 794                 /*
 795                  * The good extent is closer than this one.
 796                  */
 797                 if (!dir) {
 798                         if (*sbnoa >= args->agbno + gdiff)
 799                                 goto out_use_good;
 800                 } else {
 801                         if (*sbnoa <= args->agbno - gdiff)
 802                                 goto out_use_good;
 803                 }
 804
 805                 /*
 806                  * Same distance, compare length and pick the best.
 807                  */
 808                 if (*slena >= args->minlen) {
 809                         args->len = XFS_EXTLEN_MIN(*slena, args->maxlen);
 810                         xfs_alloc_fix_len(args);
 811
 812                         sdiff = xfs_alloc_compute_diff(args->agbno, args->len,
 813                                                        args->alignment,
 814                                                        args->userdata, *sbnoa,
 815                                                        *slena, &new);
 816
 817                         /*
 818                          * Choose closer size and invalidate other cursor.
 819                          */
 820                         if (sdiff < gdiff)
 821                                 goto out_use_search;
 822                         goto out_use_good;
 823                 }
 824
 825                 if (!dir)
 826                         error = xfs_btree_increment(*scur, 0, &i);
 827                 else
 828                         error = xfs_btree_decrement(*scur, 0, &i);
 829                 if (error)
 830                         goto error0;
 831         } while (i);
 832
 833 out_use_good:
 834         xfs_btree_del_cursor(*scur, XFS_BTREE_NOERROR);
 835         *scur = NULL;
 836         return 0;
 837
 838 out_use_search:
 839         xfs_btree_del_cursor(*gcur, XFS_BTREE_NOERROR);
 840         *gcur = NULL;
 841         return 0;
 842
 843 error0:
 844         /* caller invalidates cursors */
 845         return error;
 846 }
 847
 848 /*
 849  * Allocate a variable extent near bno in the allocation group agno.
 850  * Extent's length (returned in len) will be between minlen and maxlen,
 851  * and of the form k * prod + mod unless there's nothing that large.
 852  * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
 853  */
 854 STATIC int                              /* error */
 855 xfs_alloc_ag_vextent_near(
 856         xfs_alloc_arg_t *args)          /* allocation argument structure */
 857 {
 858         xfs_btree_cur_t *bno_cur_gt;    /* cursor for bno btree, right side */
 859         xfs_btree_cur_t *bno_cur_lt;    /* cursor for bno btree, left side */
 860         xfs_btree_cur_t *cnt_cur;       /* cursor for count btree */
 861         xfs_agblock_t   gtbno;          /* start bno of right side entry */
 862         xfs_agblock_t   gtbnoa;         /* aligned ... */
 863         xfs_extlen_t    gtdiff;         /* difference to right side entry */
 864         xfs_extlen_t    gtlen;          /* length of right side entry */
 865         xfs_extlen_t    gtlena;         /* aligned ... */
 866         xfs_agblock_t   gtnew;          /* useful start bno of right side */
 867         int             error;          /* error code */
 868         int             i;              /* result code, temporary */
 869         int             j;              /* result code, temporary */
 870         xfs_agblock_t   ltbno;          /* start bno of left side entry */
 871         xfs_agblock_t   ltbnoa;         /* aligned ... */
 872         xfs_extlen_t    ltdiff;         /* difference to left side entry */
 873         xfs_extlen_t    ltlen;          /* length of left side entry */
 874         xfs_extlen_t    ltlena;         /* aligned ... */
 875         xfs_agblock_t   ltnew;          /* useful start bno of left side */
 876         xfs_extlen_t    rlen;           /* length of returned extent */
 877         int             forced = 0;
 878 #ifdef DEBUG
 879         /*
 880          * Randomly don't execute the first algorithm.
 881          */
 882         int             dofirst;        /* set to do first algorithm */
 883
 884         dofirst = prandom_u32() & 1;
 885 #endif
 886
 887 restart:
 888         bno_cur_lt = NULL;
 889         bno_cur_gt = NULL;
 890         ltlen = 0;
 891         gtlena = 0;
 892         ltlena = 0;
 893
 894         /*
 895          * Get a cursor for the by-size btree.
 896          */
 897         cnt_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
 898                 args->agno, XFS_BTNUM_CNT);
 899
 900         /*
 901          * See if there are any free extents as big as maxlen.
 902          */
 903         if ((error = xfs_alloc_lookup_ge(cnt_cur, 0, args->maxlen, &i)))
 904                 goto error0;
 905         /*
 906          * If none, then pick up the last entry in the tree unless the
 907          * tree is empty.
 908          */
 909         if (!i) {
 910                 if ((error = xfs_alloc_ag_vextent_small(args, cnt_cur, &ltbno,
 911                                 &ltlen, &i)))
 912                         goto error0;
 913                 if (i == 0 || ltlen == 0) {
 914                         xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
 915                         trace_xfs_alloc_near_noentry(args);
 916                         return 0;
 917                 }
 918                 ASSERT(i == 1);
 919         }
 920         args->wasfromfl = 0;
 921
 922         /*
 923          * First algorithm.
 924          * If the requested extent is large wrt the freespaces available
 925          * in this a.g., then the cursor will be pointing to a btree entry
 926          * near the right edge of the tree.  If it's in the last btree leaf
 927          * block, then we just examine all the entries in that block
 928          * that are big enough, and pick the best one.
 929          * This is written as a while loop so we can break out of it,
 930          * but we never loop back to the top.
 931          */
 932         while (xfs_btree_islastblock(cnt_cur, 0)) {
 933                 xfs_extlen_t    bdiff;
 934                 int             besti=0;
 935                 xfs_extlen_t    blen=0;
 936                 xfs_agblock_t   bnew=0;
 937
 938 #ifdef DEBUG
 939                 if (dofirst)
 940                         break;
 941 #endif
 942                 /*
 943                  * Start from the entry that lookup found, sequence through
 944                  * all larger free blocks.  If we're actually pointing at a
 945                  * record smaller than maxlen, go to the start of this block,
 946                  * and skip all those smaller than minlen.
 947                  */
 948                 if (ltlen || args->alignment > 1) {
 949                         cnt_cur->bc_ptrs[0] = 1;
 950                         do {
 951                                 if ((error = xfs_alloc_get_rec(cnt_cur, &ltbno,
 952                                                 &ltlen, &i)))
 953                                         goto error0;
 954                                 XFS_WANT_CORRUPTED_GOTO(args->mp, i == 1, error0);
 955                                 if (ltlen >= args->minlen)
 956                                         break;
 957                                 if ((error = xfs_btree_increment(cnt_cur, 0, &i)))
 958                                         goto error0;
 959                         } while (i);
 960                         ASSERT(ltlen >= args->minlen);
 961                         if (!i)
 962                                 break;
 963                 }
 964                 i = cnt_cur->bc_ptrs[0];
 965                 for (j = 1, blen = 0, bdiff = 0;
 966                      !error && j && (blen < args->maxlen || bdiff > 0);
 967                      error = xfs_btree_increment(cnt_cur, 0, &j)) {
 968                         /*
 969                          * For each entry, decide if it's better than
 970                          * the previous best entry.
 971                          */
 972                         if ((error = xfs_alloc_get_rec(cnt_cur, &ltbno, &ltlen, &i)))
 973                                 goto error0;
 974                         XFS_WANT_CORRUPTED_GOTO(args->mp, i == 1, error0);
 975                         xfs_alloc_compute_aligned(args, ltbno, ltlen,
 976                                                   &ltbnoa, &ltlena);
 977                         if (ltlena < args->minlen)
 978                                 continue;
 979                         args->len = XFS_EXTLEN_MIN(ltlena, args->maxlen);
 980                         xfs_alloc_fix_len(args);
 981                         ASSERT(args->len >= args->minlen);
 982                         if (args->len < blen)
 983                                 continue;
 984                         ltdiff = xfs_alloc_compute_diff(args->agbno, args->len,
 985                                 args->alignment, args->userdata, ltbnoa,
 986                                 ltlena, &ltnew);
 987                         if (ltnew != NULLAGBLOCK &&
 988                             (args->len > blen || ltdiff < bdiff)) {
 989                                 bdiff = ltdiff;
 990                                 bnew = ltnew;
 991                                 blen = args->len;
 992                                 besti = cnt_cur->bc_ptrs[0];
 993                         }
 994                 }
 995                 /*
 996                  * It didn't work.  We COULD be in a case where
 997                  * there's a good record somewhere, so try again.
 998                  */
 999                 if (blen == 0)
1000                         break;
1001                 /*
1002                  * Point at the best entry, and retrieve it again.
1003                  */
1004                 cnt_cur->bc_ptrs[0] = besti;
1005                 if ((error = xfs_alloc_get_rec(cnt_cur, &ltbno, &ltlen, &i)))
1006                         goto error0;
1007                 XFS_WANT_CORRUPTED_GOTO(args->mp, i == 1, error0);
1008                 ASSERT(ltbno + ltlen <= be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length));
1009                 args->len = blen;
1010                 if (!xfs_alloc_fix_minleft(args)) {
1011                         xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1012                         trace_xfs_alloc_near_nominleft(args);
1013                         return 0;
1014                 }
1015                 blen = args->len;
1016                 /*
1017                  * We are allocating starting at bnew for blen blocks.
1018                  */
1019                 args->agbno = bnew;
1020                 ASSERT(bnew >= ltbno);
1021                 ASSERT(bnew + blen <= ltbno + ltlen);
1022                 /*
1023                  * Set up a cursor for the by-bno tree.
1024                  */
1025                 bno_cur_lt = xfs_allocbt_init_cursor(args->mp, args->tp,
1026                         args->agbp, args->agno, XFS_BTNUM_BNO);
1027                 /*
1028                  * Fix up the btree entries.
1029                  */
1030                 if ((error = xfs_alloc_fixup_trees(cnt_cur, bno_cur_lt, ltbno,
1031                                 ltlen, bnew, blen, XFSA_FIXUP_CNT_OK)))
1032                         goto error0;
1033                 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1034                 xfs_btree_del_cursor(bno_cur_lt, XFS_BTREE_NOERROR);
1035
1036                 trace_xfs_alloc_near_first(args);
1037                 return 0;
1038         }
1039         /*
1040          * Second algorithm.
1041          * Search in the by-bno tree to the left and to the right
1042          * simultaneously, until in each case we find a space big enough,
1043          * or run into the edge of the tree.  When we run into the edge,
1044          * we deallocate that cursor.
1045          * If both searches succeed, we compare the two spaces and pick
1046          * the better one.
1047          * With alignment, it's possible for both to fail; the upper
1048          * level algorithm that picks allocation groups for allocations
1049          * is not supposed to do this.
1050          */
1051         /*
1052          * Allocate and initialize the cursor for the leftward search.
1053          */
1054         bno_cur_lt = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
1055                 args->agno, XFS_BTNUM_BNO);
1056         /*
1057          * Lookup <= bno to find the leftward search's starting point.
1058          */
1059         if ((error = xfs_alloc_lookup_le(bno_cur_lt, args->agbno, args->maxlen, &i)))
1060                 goto error0;
1061         if (!i) {
1062                 /*
1063                  * Didn't find anything; use this cursor for the rightward
1064                  * search.
1065                  */
1066                 bno_cur_gt = bno_cur_lt;
1067                 bno_cur_lt = NULL;
1068         }
1069         /*
1070          * Found something.  Duplicate the cursor for the rightward search.
1071          */
1072         else if ((error = xfs_btree_dup_cursor(bno_cur_lt, &bno_cur_gt)))
1073                 goto error0;
1074         /*
1075          * Increment the cursor, so we will point at the entry just right
1076          * of the leftward entry if any, or to the leftmost entry.
1077          */
1078         if ((error = xfs_btree_increment(bno_cur_gt, 0, &i)))
1079                 goto error0;
1080         if (!i) {
1081                 /*
1082                  * It failed, there are no rightward entries.
1083                  */
1084                 xfs_btree_del_cursor(bno_cur_gt, XFS_BTREE_NOERROR);
1085                 bno_cur_gt = NULL;
1086         }
1087         /*
1088          * Loop going left with the leftward cursor, right with the
1089          * rightward cursor, until either both directions give up or
1090          * we find an entry at least as big as minlen.
1091          */
1092         do {
1093                 if (bno_cur_lt) {
1094                         if ((error = xfs_alloc_get_rec(bno_cur_lt, &ltbno, &ltlen, &i)))
1095                                 goto error0;
1096                         XFS_WANT_CORRUPTED_GOTO(args->mp, i == 1, error0);
1097                         xfs_alloc_compute_aligned(args, ltbno, ltlen,
1098                                                   &ltbnoa, &ltlena);
1099                         if (ltlena >= args->minlen)
1100                                 break;
1101                         if ((error = xfs_btree_decrement(bno_cur_lt, 0, &i)))
1102                                 goto error0;
1103                         if (!i) {
1104                                 xfs_btree_del_cursor(bno_cur_lt,
1105                                                      XFS_BTREE_NOERROR);
1106                                 bno_cur_lt = NULL;
1107                         }
1108                 }
1109                 if (bno_cur_gt) {
1110                         if ((error = xfs_alloc_get_rec(bno_cur_gt, &gtbno, &gtlen, &i)))
1111                                 goto error0;
1112                         XFS_WANT_CORRUPTED_GOTO(args->mp, i == 1, error0);
1113                         xfs_alloc_compute_aligned(args, gtbno, gtlen,
1114                                                   &gtbnoa, &gtlena);
1115                         if (gtlena >= args->minlen)
1116                                 break;
1117                         if ((error = xfs_btree_increment(bno_cur_gt, 0, &i)))
1118                                 goto error0;
1119                         if (!i) {
1120                                 xfs_btree_del_cursor(bno_cur_gt,
1121                                                      XFS_BTREE_NOERROR);
1122                                 bno_cur_gt = NULL;
1123                         }
1124                 }
1125         } while (bno_cur_lt || bno_cur_gt);
1126
1127         /*
1128          * Got both cursors still active, need to find better entry.
1129          */
1130         if (bno_cur_lt && bno_cur_gt) {
1131                 if (ltlena >= args->minlen) {
1132                         /*
1133                          * Left side is good, look for a right side entry.
1134                          */
1135                         args->len = XFS_EXTLEN_MIN(ltlena, args->maxlen);
1136                         xfs_alloc_fix_len(args);
1137                         ltdiff = xfs_alloc_compute_diff(args->agbno, args->len,
1138                                 args->alignment, args->userdata, ltbnoa,
1139                                 ltlena, &ltnew);
1140
1141                         error = xfs_alloc_find_best_extent(args,
1142                                                 &bno_cur_lt, &bno_cur_gt,
1143                                                 ltdiff, &gtbno, &gtlen,
1144                                                 &gtbnoa, &gtlena,
1145                                                 0 /* search right */);
1146                 } else {
1147                         ASSERT(gtlena >= args->minlen);
1148
1149                         /*
1150                          * Right side is good, look for a left side entry.
1151                          */
1152                         args->len = XFS_EXTLEN_MIN(gtlena, args->maxlen);
1153                         xfs_alloc_fix_len(args);
1154                         gtdiff = xfs_alloc_compute_diff(args->agbno, args->len,
1155                                 args->alignment, args->userdata, gtbnoa,
1156                                 gtlena, &gtnew);
1157
1158                         error = xfs_alloc_find_best_extent(args,
1159                                                 &bno_cur_gt, &bno_cur_lt,
1160                                                 gtdiff, &ltbno, &ltlen,
1161                                                 &ltbnoa, &ltlena,
1162                                                 1 /* search left */);
1163                 }
1164
1165                 if (error)
1166                         goto error0;
1167         }
1168
1169         /*
1170          * If we couldn't get anything, give up.
1171          */
1172         if (bno_cur_lt == NULL && bno_cur_gt == NULL) {
1173                 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1174
1175                 if (!forced++) {
1176                         trace_xfs_alloc_near_busy(args);
1177                         xfs_log_force(args->mp, XFS_LOG_SYNC);
1178                         goto restart;
1179                 }
1180                 trace_xfs_alloc_size_neither(args);
1181                 args->agbno = NULLAGBLOCK;
1182                 return 0;
1183         }
1184
1185         /*
1186          * At this point we have selected a freespace entry, either to the
1187          * left or to the right.  If it's on the right, copy all the
1188          * useful variables to the "left" set so we only have one
1189          * copy of this code.
1190          */
1191         if (bno_cur_gt) {
1192                 bno_cur_lt = bno_cur_gt;
1193                 bno_cur_gt = NULL;
1194                 ltbno = gtbno;
1195                 ltbnoa = gtbnoa;
1196                 ltlen = gtlen;
1197                 ltlena = gtlena;
1198                 j = 1;
1199         } else
1200                 j = 0;
1201
1202         /*
1203          * Fix up the length and compute the useful address.
1204          */
1205         args->len = XFS_EXTLEN_MIN(ltlena, args->maxlen);
1206         xfs_alloc_fix_len(args);
1207         if (!xfs_alloc_fix_minleft(args)) {
1208                 trace_xfs_alloc_near_nominleft(args);
1209                 xfs_btree_del_cursor(bno_cur_lt, XFS_BTREE_NOERROR);
1210                 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1211                 return 0;
1212         }
1213         rlen = args->len;
1214         (void)xfs_alloc_compute_diff(args->agbno, rlen, args->alignment,
1215                                      args->userdata, ltbnoa, ltlena, &ltnew);
1216         ASSERT(ltnew >= ltbno);
1217         ASSERT(ltnew + rlen <= ltbnoa + ltlena);
1218         ASSERT(ltnew + rlen <= be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length));
1219         args->agbno = ltnew;
1220
1221         if ((error = xfs_alloc_fixup_trees(cnt_cur, bno_cur_lt, ltbno, ltlen,
1222                         ltnew, rlen, XFSA_FIXUP_BNO_OK)))
1223                 goto error0;
1224
1225         if (j)
1226                 trace_xfs_alloc_near_greater(args);
1227         else
1228                 trace_xfs_alloc_near_lesser(args);
1229
1230         xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1231         xfs_btree_del_cursor(bno_cur_lt, XFS_BTREE_NOERROR);
1232         return 0;
1233
1234  error0:
1235         trace_xfs_alloc_near_error(args);
1236         if (cnt_cur != NULL)
1237                 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
1238         if (bno_cur_lt != NULL)
1239                 xfs_btree_del_cursor(bno_cur_lt, XFS_BTREE_ERROR);
1240         if (bno_cur_gt != NULL)
1241                 xfs_btree_del_cursor(bno_cur_gt, XFS_BTREE_ERROR);
1242         return error;
1243 }
1244
1245 /*
1246  * Allocate a variable extent anywhere in the allocation group agno.
1247  * Extent's length (returned in len) will be between minlen and maxlen,
1248  * and of the form k * prod + mod unless there's nothing that large.
1249  * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
1250  */
1251 STATIC int                              /* error */
1252 xfs_alloc_ag_vextent_size(
1253         xfs_alloc_arg_t *args)          /* allocation argument structure */
1254 {
1255         xfs_btree_cur_t *bno_cur;       /* cursor for bno btree */
1256         xfs_btree_cur_t *cnt_cur;       /* cursor for cnt btree */
1257         int             error;          /* error result */
1258         xfs_agblock_t   fbno;           /* start of found freespace */
1259         xfs_extlen_t    flen;           /* length of found freespace */
1260         int             i;              /* temp status variable */
1261         xfs_agblock_t   rbno;           /* returned block number */
1262         xfs_extlen_t    rlen;           /* length of returned extent */
1263         int             forced = 0;
1264
1265 restart:
1266         /*
1267          * Allocate and initialize a cursor for the by-size btree.
1268          */
1269         cnt_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
1270                 args->agno, XFS_BTNUM_CNT);
1271         bno_cur = NULL;
1272
1273         /*
1274          * Look for an entry >= maxlen+alignment-1 blocks.
1275          */
1276         if ((error = xfs_alloc_lookup_ge(cnt_cur, 0,
1277                         args->maxlen + args->alignment - 1, &i)))
1278                 goto error0;
1279
1280         /*
1281          * If none or we have busy extents that we cannot allocate from, then
1282          * we have to settle for a smaller extent. In the case that there are
1283          * no large extents, this will return the last entry in the tree unless
1284          * the tree is empty. In the case that there are only busy large
1285          * extents, this will return the largest small extent unless there
1286          * are no smaller extents available.
1287          */
1288         if (!i || forced > 1) {
1289                 error = xfs_alloc_ag_vextent_small(args, cnt_cur,
1290                                                    &fbno, &flen, &i);
1291                 if (error)
1292                         goto error0;
1293                 if (i == 0 || flen == 0) {
1294                         xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1295                         trace_xfs_alloc_size_noentry(args);
1296                         return 0;
1297                 }
1298                 ASSERT(i == 1);
1299                 xfs_alloc_compute_aligned(args, fbno, flen, &rbno, &rlen);
1300         } else {
1301                 /*
1302                  * Search for a non-busy extent that is large enough.
1303                  * If we are at low space, don't check, or if we fall of
1304                  * the end of the btree, turn off the busy check and
1305                  * restart.
1306                  */
1307                 for (;;) {
1308                         error = xfs_alloc_get_rec(cnt_cur, &fbno, &flen, &i);
1309                         if (error)
1310                                 goto error0;
1311                         XFS_WANT_CORRUPTED_GOTO(args->mp, i == 1, error0);
1312
1313                         xfs_alloc_compute_aligned(args, fbno, flen,
1314                                                   &rbno, &rlen);
1315
1316                         if (rlen >= args->maxlen)
1317                                 break;
1318
1319                         error = xfs_btree_increment(cnt_cur, 0, &i);
1320                         if (error)
1321                                 goto error0;
1322                         if (i == 0) {
1323                                 /*
1324                                  * Our only valid extents must have been busy.
1325                                  * Make it unbusy by forcing the log out and
1326                                  * retrying. If we've been here before, forcing
1327                                  * the log isn't making the extents available,
1328                                  * which means they have probably been freed in
1329                                  * this transaction.  In that case, we have to
1330                                  * give up on them and we'll attempt a minlen
1331                                  * allocation the next time around.
1332                                  */
1333                                 xfs_btree_del_cursor(cnt_cur,
1334                                                      XFS_BTREE_NOERROR);
1335                                 trace_xfs_alloc_size_busy(args);
1336                                 if (!forced++)
1337                                         xfs_log_force(args->mp, XFS_LOG_SYNC);
1338                                 goto restart;
1339                         }
1340                 }
1341         }
1342
1343         /*
1344          * In the first case above, we got the last entry in the
1345          * by-size btree.  Now we check to see if the space hits maxlen
1346          * once aligned; if not, we search left for something better.
1347          * This can't happen in the second case above.
1348          */
1349         rlen = XFS_EXTLEN_MIN(args->maxlen, rlen);
1350         XFS_WANT_CORRUPTED_GOTO(args->mp, rlen == 0 ||
1351                         (rlen <= flen && rbno + rlen <= fbno + flen), error0);
1352         if (rlen < args->maxlen) {
1353                 xfs_agblock_t   bestfbno;
1354                 xfs_extlen_t    bestflen;
1355                 xfs_agblock_t   bestrbno;
1356                 xfs_extlen_t    bestrlen;
1357
1358                 bestrlen = rlen;
1359                 bestrbno = rbno;
1360                 bestflen = flen;
1361                 bestfbno = fbno;
1362                 for (;;) {
1363                         if ((error = xfs_btree_decrement(cnt_cur, 0, &i)))
1364                                 goto error0;
1365                         if (i == 0)
1366                                 break;
1367                         if ((error = xfs_alloc_get_rec(cnt_cur, &fbno, &flen,
1368                                         &i)))
1369                                 goto error0;
1370                         XFS_WANT_CORRUPTED_GOTO(args->mp, i == 1, error0);
1371                         if (flen < bestrlen)
1372                                 break;
1373                         xfs_alloc_compute_aligned(args, fbno, flen,
1374                                                   &rbno, &rlen);
1375                         rlen = XFS_EXTLEN_MIN(args->maxlen, rlen);
1376                         XFS_WANT_CORRUPTED_GOTO(args->mp, rlen == 0 ||
1377                                 (rlen <= flen && rbno + rlen <= fbno + flen),
1378                                 error0);
1379                         if (rlen > bestrlen) {
1380                                 bestrlen = rlen;
1381                                 bestrbno = rbno;
1382                                 bestflen = flen;
1383                                 bestfbno = fbno;
1384                                 if (rlen == args->maxlen)
1385                                         break;
1386                         }
1387                 }
1388                 if ((error = xfs_alloc_lookup_eq(cnt_cur, bestfbno, bestflen,
1389                                 &i)))
1390                         goto error0;
1391                 XFS_WANT_CORRUPTED_GOTO(args->mp, i == 1, error0);
1392                 rlen = bestrlen;
1393                 rbno = bestrbno;
1394                 flen = bestflen;
1395                 fbno = bestfbno;
1396         }
1397         args->wasfromfl = 0;
1398         /*
1399          * Fix up the length.
1400          */
1401         args->len = rlen;
1402         if (rlen < args->minlen) {
1403                 if (!forced++) {
1404                         xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1405                         trace_xfs_alloc_size_busy(args);
1406                         xfs_log_force(args->mp, XFS_LOG_SYNC);
1407                         goto restart;
1408                 }
1409                 goto out_nominleft;
1410         }
1411         xfs_alloc_fix_len(args);
1412
1413         if (!xfs_alloc_fix_minleft(args))
1414                 goto out_nominleft;
1415         rlen = args->len;
1416         XFS_WANT_CORRUPTED_GOTO(args->mp, rlen <= flen, error0);
1417         /*
1418          * Allocate and initialize a cursor for the by-block tree.
1419          */
1420         bno_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
1421                 args->agno, XFS_BTNUM_BNO);
1422         if ((error = xfs_alloc_fixup_trees(cnt_cur, bno_cur, fbno, flen,
1423                         rbno, rlen, XFSA_FIXUP_CNT_OK)))
1424                 goto error0;
1425         xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1426         xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
1427         cnt_cur = bno_cur = NULL;
1428         args->len = rlen;
1429         args->agbno = rbno;
1430         XFS_WANT_CORRUPTED_GOTO(args->mp,
1431                 args->agbno + args->len <=
1432                         be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length),
1433                 error0);
1434         trace_xfs_alloc_size_done(args);
1435         return 0;
1436
1437 error0:
1438         trace_xfs_alloc_size_error(args);
1439         if (cnt_cur)
1440                 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
1441         if (bno_cur)
1442                 xfs_btree_del_cursor(bno_cur, XFS_BTREE_ERROR);
1443         return error;
1444
1445 out_nominleft:
1446         xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1447         trace_xfs_alloc_size_nominleft(args);
1448         args->agbno = NULLAGBLOCK;
1449         return 0;
1450 }
1451
1452 /*
1453  * Deal with the case where only small freespaces remain.
1454  * Either return the contents of the last freespace record,
1455  * or allocate space from the freelist if there is nothing in the tree.
1456  */
1457 STATIC int                      /* error */
1458 xfs_alloc_ag_vextent_small(
1459         xfs_alloc_arg_t *args,  /* allocation argument structure */
1460         xfs_btree_cur_t *ccur,  /* by-size cursor */
1461         xfs_agblock_t   *fbnop, /* result block number */
1462         xfs_extlen_t    *flenp, /* result length */
1463         int             *stat)  /* status: 0-freelist, 1-normal/none */
1464 {
1465         int             error;
1466         xfs_agblock_t   fbno;
1467         xfs_extlen_t    flen;
1468         int             i;
1469
1470         if ((error = xfs_btree_decrement(ccur, 0, &i)))
1471                 goto error0;
1472         if (i) {
1473                 if ((error = xfs_alloc_get_rec(ccur, &fbno, &flen, &i)))
1474                         goto error0;
1475                 XFS_WANT_CORRUPTED_GOTO(args->mp, i == 1, error0);
1476         }
1477         /*
1478          * Nothing in the btree, try the freelist.  Make sure
1479          * to respect minleft even when pulling from the
1480          * freelist.
1481          */
1482         else if (args->minlen == 1 && args->alignment == 1 && !args->isfl &&
1483                  (be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_flcount)
1484                   > args->minleft)) {
1485                 error = xfs_alloc_get_freelist(args->tp, args->agbp, &fbno, 0);
1486                 if (error)
1487                         goto error0;
1488                 if (fbno != NULLAGBLOCK) {
1489                         xfs_extent_busy_reuse(args->mp, args->agno, fbno, 1,
1490                                              args->userdata);
1491
1492                         if (args->userdata) {
1493                                 xfs_buf_t       *bp;
1494
1495                                 bp = xfs_btree_get_bufs(args->mp, args->tp,
1496                                         args->agno, fbno, 0);
1497                                 xfs_trans_binval(args->tp, bp);
1498                         }
1499                         args->len = 1;
1500                         args->agbno = fbno;
1501                         XFS_WANT_CORRUPTED_GOTO(args->mp,
1502                                 args->agbno + args->len <=
1503                                 be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length),
1504                                 error0);
1505                         args->wasfromfl = 1;
1506                         trace_xfs_alloc_small_freelist(args);
1507                         *stat = 0;
1508                         return 0;
1509                 }
1510                 /*
1511                  * Nothing in the freelist.
1512                  */
1513                 else
1514                         flen = 0;
1515         }
1516         /*
1517          * Can't allocate from the freelist for some reason.
1518          */
1519         else {
1520                 fbno = NULLAGBLOCK;
1521                 flen = 0;
1522         }
1523         /*
1524          * Can't do the allocation, give up.
1525          */
1526         if (flen < args->minlen) {
1527                 args->agbno = NULLAGBLOCK;
1528                 trace_xfs_alloc_small_notenough(args);
1529                 flen = 0;
1530         }
1531         *fbnop = fbno;
1532         *flenp = flen;
1533         *stat = 1;
1534         trace_xfs_alloc_small_done(args);
1535         return 0;
1536
1537 error0:
1538         trace_xfs_alloc_small_error(args);
1539         return error;
1540 }
1541
1542 /*
1543  * Free the extent starting at agno/bno for length.
1544  */
1545 STATIC int                      /* error */
1546 xfs_free_ag_extent(
1547         xfs_trans_t     *tp,    /* transaction pointer */
1548         xfs_buf_t       *agbp,  /* buffer for a.g. freelist header */
1549         xfs_agnumber_t  agno,   /* allocation group number */
1550         xfs_agblock_t   bno,    /* starting block number */
1551         xfs_extlen_t    len,    /* length of extent */
1552         int             isfl)   /* set if is freelist blocks - no sb acctg */
1553 {
1554         xfs_btree_cur_t *bno_cur;       /* cursor for by-block btree */
1555         xfs_btree_cur_t *cnt_cur;       /* cursor for by-size btree */
1556         int             error;          /* error return value */
1557         xfs_agblock_t   gtbno;          /* start of right neighbor block */
1558         xfs_extlen_t    gtlen;          /* length of right neighbor block */
1559         int             haveleft;       /* have a left neighbor block */
1560         int             haveright;      /* have a right neighbor block */
1561         int             i;              /* temp, result code */
1562         xfs_agblock_t   ltbno;          /* start of left neighbor block */
1563         xfs_extlen_t    ltlen;          /* length of left neighbor block */
1564         xfs_mount_t     *mp;            /* mount point struct for filesystem */
1565         xfs_agblock_t   nbno;           /* new starting block of freespace */
1566         xfs_extlen_t    nlen;           /* new length of freespace */
1567         xfs_perag_t     *pag;           /* per allocation group data */
1568
1569         mp = tp->t_mountp;
1570         /*
1571          * Allocate and initialize a cursor for the by-block btree.
1572          */
1573         bno_cur = xfs_allocbt_init_cursor(mp, tp, agbp, agno, XFS_BTNUM_BNO);
1574         cnt_cur = NULL;
1575         /*
1576          * Look for a neighboring block on the left (lower block numbers)
1577          * that is contiguous with this space.
1578          */
1579         if ((error = xfs_alloc_lookup_le(bno_cur, bno, len, &haveleft)))
1580                 goto error0;
1581         if (haveleft) {
1582                 /*
1583                  * There is a block to our left.
1584                  */
1585                 if ((error = xfs_alloc_get_rec(bno_cur, &ltbno, &ltlen, &i)))
1586                         goto error0;
1587                 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, error0);
1588                 /*
1589                  * It's not contiguous, though.
1590                  */
1591                 if (ltbno + ltlen < bno)
1592                         haveleft = 0;
1593                 else {
1594                         /*
1595                          * If this failure happens the request to free this
1596                          * space was invalid, it's (partly) already free.
1597                          * Very bad.
1598                          */
1599                         XFS_WANT_CORRUPTED_GOTO(mp,
1600                                                 ltbno + ltlen <= bno, error0);
1601                 }
1602         }
1603         /*
1604          * Look for a neighboring block on the right (higher block numbers)
1605          * that is contiguous with this space.
1606          */
1607         if ((error = xfs_btree_increment(bno_cur, 0, &haveright)))
1608                 goto error0;
1609         if (haveright) {
1610                 /*
1611                  * There is a block to our right.
1612                  */
1613                 if ((error = xfs_alloc_get_rec(bno_cur, &gtbno, &gtlen, &i)))
1614                         goto error0;
1615                 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, error0);
1616                 /*
1617                  * It's not contiguous, though.
1618                  */
1619                 if (bno + len < gtbno)
1620                         haveright = 0;
1621                 else {
1622                         /*
1623                          * If this failure happens the request to free this
1624                          * space was invalid, it's (partly) already free.
1625                          * Very bad.
1626                          */
1627                         XFS_WANT_CORRUPTED_GOTO(mp, gtbno >= bno + len, error0);
1628                 }
1629         }
1630         /*
1631          * Now allocate and initialize a cursor for the by-size tree.
1632          */
1633         cnt_cur = xfs_allocbt_init_cursor(mp, tp, agbp, agno, XFS_BTNUM_CNT);
1634         /*
1635          * Have both left and right contiguous neighbors.
1636          * Merge all three into a single free block.
1637          */
1638         if (haveleft && haveright) {
1639                 /*
1640                  * Delete the old by-size entry on the left.
1641                  */
1642                 if ((error = xfs_alloc_lookup_eq(cnt_cur, ltbno, ltlen, &i)))
1643                         goto error0;
1644                 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, error0);
1645                 if ((error = xfs_btree_delete(cnt_cur, &i)))
1646                         goto error0;
1647                 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, error0);
1648                 /*
1649                  * Delete the old by-size entry on the right.
1650                  */
1651                 if ((error = xfs_alloc_lookup_eq(cnt_cur, gtbno, gtlen, &i)))
1652                         goto error0;
1653                 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, error0);
1654                 if ((error = xfs_btree_delete(cnt_cur, &i)))
1655                         goto error0;
1656                 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, error0);
1657                 /*
1658                  * Delete the old by-block entry for the right block.
1659                  */
1660                 if ((error = xfs_btree_delete(bno_cur, &i)))
1661                         goto error0;
1662                 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, error0);
1663                 /*
1664                  * Move the by-block cursor back to the left neighbor.
1665                  */
1666                 if ((error = xfs_btree_decrement(bno_cur, 0, &i)))
1667                         goto error0;
1668                 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, error0);
1669 #ifdef DEBUG
1670                 /*
1671                  * Check that this is the right record: delete didn't
1672                  * mangle the cursor.
1673                  */
1674                 {
1675                         xfs_agblock_t   xxbno;
1676                         xfs_extlen_t    xxlen;
1677
1678                         if ((error = xfs_alloc_get_rec(bno_cur, &xxbno, &xxlen,
1679                                         &i)))
1680                                 goto error0;
1681                         XFS_WANT_CORRUPTED_GOTO(mp,
1682                                 i == 1 && xxbno == ltbno && xxlen == ltlen,
1683                                 error0);
1684                 }
1685 #endif
1686                 /*
1687                  * Update remaining by-block entry to the new, joined block.
1688                  */
1689                 nbno = ltbno;
1690                 nlen = len + ltlen + gtlen;
1691                 if ((error = xfs_alloc_update(bno_cur, nbno, nlen)))
1692                         goto error0;
1693         }
1694         /*
1695          * Have only a left contiguous neighbor.
1696          * Merge it together with the new freespace.
1697          */
1698         else if (haveleft) {
1699                 /*
1700                  * Delete the old by-size entry on the left.
1701                  */
1702                 if ((error = xfs_alloc_lookup_eq(cnt_cur, ltbno, ltlen, &i)))
1703                         goto error0;
1704                 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, error0);
1705                 if ((error = xfs_btree_delete(cnt_cur, &i)))
1706                         goto error0;
1707                 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, error0);
1708                 /*
1709                  * Back up the by-block cursor to the left neighbor, and
1710                  * update its length.
1711                  */
1712                 if ((error = xfs_btree_decrement(bno_cur, 0, &i)))
1713                         goto error0;
1714                 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, error0);
1715                 nbno = ltbno;
1716                 nlen = len + ltlen;
1717                 if ((error = xfs_alloc_update(bno_cur, nbno, nlen)))
1718                         goto error0;
1719         }
1720         /*
1721          * Have only a right contiguous neighbor.
1722          * Merge it together with the new freespace.
1723          */
1724         else if (haveright) {
1725                 /*
1726                  * Delete the old by-size entry on the right.
1727                  */
1728                 if ((error = xfs_alloc_lookup_eq(cnt_cur, gtbno, gtlen, &i)))
1729                         goto error0;
1730                 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, error0);
1731                 if ((error = xfs_btree_delete(cnt_cur, &i)))
1732                         goto error0;
1733                 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, error0);
1734                 /*
1735                  * Update the starting block and length of the right
1736                  * neighbor in the by-block tree.
1737                  */
1738                 nbno = bno;
1739                 nlen = len + gtlen;
1740                 if ((error = xfs_alloc_update(bno_cur, nbno, nlen)))
1741                         goto error0;
1742         }
1743         /*
1744          * No contiguous neighbors.
1745          * Insert the new freespace into the by-block tree.
1746          */
1747         else {
1748                 nbno = bno;
1749                 nlen = len;
1750                 if ((error = xfs_btree_insert(bno_cur, &i)))
1751                         goto error0;
1752                 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, error0);
1753         }
1754         xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
1755         bno_cur = NULL;
1756         /*
1757          * In all cases we need to insert the new freespace in the by-size tree.
1758          */
1759         if ((error = xfs_alloc_lookup_eq(cnt_cur, nbno, nlen, &i)))
1760                 goto error0;
1761         XFS_WANT_CORRUPTED_GOTO(mp, i == 0, error0);
1762         if ((error = xfs_btree_insert(cnt_cur, &i)))
1763                 goto error0;
1764         XFS_WANT_CORRUPTED_GOTO(mp, i == 1, error0);
1765         xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1766         cnt_cur = NULL;
1767
1768         /*
1769          * Update the freespace totals in the ag and superblock.
1770          */
1771         pag = xfs_perag_get(mp, agno);
1772         error = xfs_alloc_update_counters(tp, pag, agbp, len);
1773         xfs_perag_put(pag);
1774         if (error)
1775                 goto error0;
1776
1777         if (!isfl)
1778                 xfs_trans_mod_sb(tp, XFS_TRANS_SB_FDBLOCKS, (long)len);
1779         XFS_STATS_INC(xs_freex);
1780         XFS_STATS_ADD(xs_freeb, len);
1781
1782         trace_xfs_free_extent(mp, agno, bno, len, isfl, haveleft, haveright);
1783
1784         return 0;
1785
1786  error0:
1787         trace_xfs_free_extent(mp, agno, bno, len, isfl, -1, -1);
1788         if (bno_cur)
1789                 xfs_btree_del_cursor(bno_cur, XFS_BTREE_ERROR);
1790         if (cnt_cur)
1791                 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
1792         return error;
1793 }
1794
1795 /*
1796  * Visible (exported) allocation/free functions.
1797  * Some of these are used just by xfs_alloc_btree.c and this file.
1798  */
1799
1800 /*
1801  * Compute and fill in value of m_ag_maxlevels.
1802  */
1803 void
1804 xfs_alloc_compute_maxlevels(
1805         xfs_mount_t     *mp)    /* file system mount structure */
1806 {
1807         int             level;
1808         uint            maxblocks;
1809         uint            maxleafents;
1810         int             minleafrecs;
1811         int             minnoderecs;
1812
1813         maxleafents = (mp->m_sb.sb_agblocks + 1) / 2;
1814         minleafrecs = mp->m_alloc_mnr[0];
1815         minnoderecs = mp->m_alloc_mnr[1];
1816         maxblocks = (maxleafents + minleafrecs - 1) / minleafrecs;
1817         for (level = 1; maxblocks > 1; level++)
1818                 maxblocks = (maxblocks + minnoderecs - 1) / minnoderecs;
1819         mp->m_ag_maxlevels = level;
1820 }
1821
1822 /*
1823  * Find the length of the longest extent in an AG.
1824  */
1825 xfs_extlen_t
1826 xfs_alloc_longest_free_extent(
1827         struct xfs_mount        *mp,
1828         struct xfs_perag        *pag)
1829 {
1830         xfs_extlen_t            need, delta = 0;
1831
1832         need = XFS_MIN_FREELIST_PAG(pag, mp);
1833         if (need > pag->pagf_flcount)
1834                 delta = need - pag->pagf_flcount;
1835
1836         if (pag->pagf_longest > delta)
1837                 return pag->pagf_longest - delta;
1838         return pag->pagf_flcount > 0 || pag->pagf_longest > 0;
1839 }
1840
1841 /*
1842  * Decide whether to use this allocation group for this allocation.
1843  * If so, fix up the btree freelist's size.
1844  */
1845 STATIC int                      /* error */
1846 xfs_alloc_fix_freelist(
1847         xfs_alloc_arg_t *args,  /* allocation argument structure */
1848         int             flags)  /* XFS_ALLOC_FLAG_... */
1849 {
1850         xfs_buf_t       *agbp;  /* agf buffer pointer */
1851         xfs_agf_t       *agf;   /* a.g. freespace structure pointer */
1852         xfs_buf_t       *agflbp;/* agfl buffer pointer */
1853         xfs_agblock_t   bno;    /* freelist block */
1854         xfs_extlen_t    delta;  /* new blocks needed in freelist */
1855         int             error;  /* error result code */
1856         xfs_extlen_t    longest;/* longest extent in allocation group */
1857         xfs_mount_t     *mp;    /* file system mount point structure */
1858         xfs_extlen_t    need;   /* total blocks needed in freelist */
1859         xfs_perag_t     *pag;   /* per-ag information structure */
1860         xfs_alloc_arg_t targs;  /* local allocation arguments */
1861         xfs_trans_t     *tp;    /* transaction pointer */
1862
1863         mp = args->mp;
1864
1865         pag = args->pag;
1866         tp = args->tp;
1867         if (!pag->pagf_init) {
1868                 if ((error = xfs_alloc_read_agf(mp, tp, args->agno, flags,
1869                                 &agbp)))
1870                         return error;
1871                 if (!pag->pagf_init) {
1872                         ASSERT(flags & XFS_ALLOC_FLAG_TRYLOCK);
1873                         ASSERT(!(flags & XFS_ALLOC_FLAG_FREEING));
1874                         args->agbp = NULL;
1875                         return 0;
1876                 }
1877         } else
1878                 agbp = NULL;
1879
1880         /*
1881          * If this is a metadata preferred pag and we are user data
1882          * then try somewhere else if we are not being asked to
1883          * try harder at this point
1884          */
1885         if (pag->pagf_metadata && args->userdata &&
1886             (flags & XFS_ALLOC_FLAG_TRYLOCK)) {
1887                 ASSERT(!(flags & XFS_ALLOC_FLAG_FREEING));
1888                 args->agbp = NULL;
1889                 return 0;
1890         }
1891
1892         if (!(flags & XFS_ALLOC_FLAG_FREEING)) {
1893                 /*
1894                  * If it looks like there isn't a long enough extent, or enough
1895                  * total blocks, reject it.
1896                  */
1897                 need = XFS_MIN_FREELIST_PAG(pag, mp);
1898                 longest = xfs_alloc_longest_free_extent(mp, pag);
1899                 if ((args->minlen + args->alignment + args->minalignslop - 1) >
1900                                 longest ||
1901                     ((int)(pag->pagf_freeblks + pag->pagf_flcount -
1902                            need - args->total) < (int)args->minleft)) {
1903                         if (agbp)
1904                                 xfs_trans_brelse(tp, agbp);
1905                         args->agbp = NULL;
1906                         return 0;
1907                 }
1908         }
1909
1910         /*
1911          * Get the a.g. freespace buffer.
1912          * Can fail if we're not blocking on locks, and it's held.
1913          */
1914         if (agbp == NULL) {
1915                 if ((error = xfs_alloc_read_agf(mp, tp, args->agno, flags,
1916                                 &agbp)))
1917                         return error;
1918                 if (agbp == NULL) {
1919                         ASSERT(flags & XFS_ALLOC_FLAG_TRYLOCK);
1920                         ASSERT(!(flags & XFS_ALLOC_FLAG_FREEING));
1921                         args->agbp = NULL;
1922                         return 0;
1923                 }
1924         }
1925         /*
1926          * Figure out how many blocks we should have in the freelist.
1927          */
1928         agf = XFS_BUF_TO_AGF(agbp);
1929         need = XFS_MIN_FREELIST(agf, mp);
1930         /*
1931          * If there isn't enough total or single-extent, reject it.
1932          */
1933         if (!(flags & XFS_ALLOC_FLAG_FREEING)) {
1934                 delta = need > be32_to_cpu(agf->agf_flcount) ?
1935                         (need - be32_to_cpu(agf->agf_flcount)) : 0;
1936                 longest = be32_to_cpu(agf->agf_longest);
1937                 longest = (longest > delta) ? (longest - delta) :
1938                         (be32_to_cpu(agf->agf_flcount) > 0 || longest > 0);
1939                 if ((args->minlen + args->alignment + args->minalignslop - 1) >
1940                                 longest ||
1941                     ((int)(be32_to_cpu(agf->agf_freeblks) +
1942                      be32_to_cpu(agf->agf_flcount) - need - args->total) <
1943                                 (int)args->minleft)) {
1944                         xfs_trans_brelse(tp, agbp);
1945                         args->agbp = NULL;
1946                         return 0;
1947                 }
1948         }
1949         /*
1950          * Make the freelist shorter if it's too long.
1951          */
1952         while (be32_to_cpu(agf->agf_flcount) > need) {
1953                 xfs_buf_t       *bp;
1954
1955                 error = xfs_alloc_get_freelist(tp, agbp, &bno, 0);
1956                 if (error)
1957                         return error;
1958                 if ((error = xfs_free_ag_extent(tp, agbp, args->agno, bno, 1, 1)))
1959                         return error;
1960                 bp = xfs_btree_get_bufs(mp, tp, args->agno, bno, 0);
1961                 xfs_trans_binval(tp, bp);
1962         }
1963         /*
1964          * Initialize the args structure.
1965          */
1966         memset(&targs, 0, sizeof(targs));
1967         targs.tp = tp;
1968         targs.mp = mp;
1969         targs.agbp = agbp;
1970         targs.agno = args->agno;
1971         targs.alignment = targs.minlen = targs.prod = targs.isfl = 1;
1972         targs.type = XFS_ALLOCTYPE_THIS_AG;
1973         targs.pag = pag;
1974         if ((error = xfs_alloc_read_agfl(mp, tp, targs.agno, &agflbp)))
1975                 return error;
1976         /*
1977          * Make the freelist longer if it's too short.
1978          */
1979         while (be32_to_cpu(agf->agf_flcount) < need) {
1980                 targs.agbno = 0;
1981                 targs.maxlen = need - be32_to_cpu(agf->agf_flcount);
1982                 /*
1983                  * Allocate as many blocks as possible at once.
1984                  */
1985                 if ((error = xfs_alloc_ag_vextent(&targs))) {
1986                         xfs_trans_brelse(tp, agflbp);
1987                         return error;
1988                 }
1989                 /*
1990                  * Stop if we run out.  Won't happen if callers are obeying
1991                  * the restrictions correctly.  Can happen for free calls
1992                  * on a completely full ag.
1993                  */
1994                 if (targs.agbno == NULLAGBLOCK) {
1995                         if (flags & XFS_ALLOC_FLAG_FREEING)
1996                                 break;
1997                         xfs_trans_brelse(tp, agflbp);
1998                         args->agbp = NULL;
1999                         return 0;
2000                 }
2001                 /*
2002                  * Put each allocated block on the list.
2003                  */
2004                 for (bno = targs.agbno; bno < targs.agbno + targs.len; bno++) {
2005                         error = xfs_alloc_put_freelist(tp, agbp,
2006                                                         agflbp, bno, 0);
2007                         if (error)
2008                                 return error;
2009                 }
2010         }
2011         xfs_trans_brelse(tp, agflbp);
2012         args->agbp = agbp;
2013         return 0;
2014 }
2015
2016 /*
2017  * Get a block from the freelist.
2018  * Returns with the buffer for the block gotten.
2019  */
2020 int                             /* error */
2021 xfs_alloc_get_freelist(
2022         xfs_trans_t     *tp,    /* transaction pointer */
2023         xfs_buf_t       *agbp,  /* buffer containing the agf structure */
2024         xfs_agblock_t   *bnop,  /* block address retrieved from freelist */
2025         int             btreeblk) /* destination is a AGF btree */
2026 {
2027         xfs_agf_t       *agf;   /* a.g. freespace structure */
2028         xfs_buf_t       *agflbp;/* buffer for a.g. freelist structure */
2029         xfs_agblock_t   bno;    /* block number returned */
2030         __be32          *agfl_bno;
2031         int             error;
2032         int             logflags;
2033         xfs_mount_t     *mp = tp->t_mountp;
2034         xfs_perag_t     *pag;   /* per allocation group data */
2035
2036         /*
2037          * Freelist is empty, give up.
2038          */
2039         agf = XFS_BUF_TO_AGF(agbp);
2040         if (!agf->agf_flcount) {
2041                 *bnop = NULLAGBLOCK;
2042                 return 0;
2043         }
2044         /*
2045          * Read the array of free blocks.
2046          */
2047         error = xfs_alloc_read_agfl(mp, tp, be32_to_cpu(agf->agf_seqno),
2048                                     &agflbp);
2049         if (error)
2050                 return error;
2051
2052
2053         /*
2054          * Get the block number and update the data structures.
2055          */
2056         agfl_bno = XFS_BUF_TO_AGFL_BNO(mp, agflbp);
2057         bno = be32_to_cpu(agfl_bno[be32_to_cpu(agf->agf_flfirst)]);
2058         be32_add_cpu(&agf->agf_flfirst, 1);
2059         xfs_trans_brelse(tp, agflbp);
2060         if (be32_to_cpu(agf->agf_flfirst) == XFS_AGFL_SIZE(mp))
2061                 agf->agf_flfirst = 0;
2062
2063         pag = xfs_perag_get(mp, be32_to_cpu(agf->agf_seqno));
2064         be32_add_cpu(&agf->agf_flcount, -1);
2065         xfs_trans_agflist_delta(tp, -1);
2066         pag->pagf_flcount--;
2067         xfs_perag_put(pag);
2068
2069         logflags = XFS_AGF_FLFIRST | XFS_AGF_FLCOUNT;
2070         if (btreeblk) {
2071                 be32_add_cpu(&agf->agf_btreeblks, 1);
2072                 pag->pagf_btreeblks++;
2073                 logflags |= XFS_AGF_BTREEBLKS;
2074         }
2075
2076         xfs_alloc_log_agf(tp, agbp, logflags);
2077         *bnop = bno;
2078
2079         return 0;
2080 }
2081
2082 /*
2083  * Log the given fields from the agf structure.
2084  */
2085 void
2086 xfs_alloc_log_agf(
2087         xfs_trans_t     *tp,    /* transaction pointer */
2088         xfs_buf_t       *bp,    /* buffer for a.g. freelist header */
2089         int             fields) /* mask of fields to be logged (XFS_AGF_...) */
2090 {
2091         int     first;          /* first byte offset */
2092         int     last;           /* last byte offset */
2093         static const short      offsets[] = {
2094                 offsetof(xfs_agf_t, agf_magicnum),
2095                 offsetof(xfs_agf_t, agf_versionnum),
2096                 offsetof(xfs_agf_t, agf_seqno),
2097                 offsetof(xfs_agf_t, agf_length),
2098                 offsetof(xfs_agf_t, agf_roots[0]),
2099                 offsetof(xfs_agf_t, agf_levels[0]),
2100                 offsetof(xfs_agf_t, agf_flfirst),
2101                 offsetof(xfs_agf_t, agf_fllast),
2102                 offsetof(xfs_agf_t, agf_flcount),
2103                 offsetof(xfs_agf_t, agf_freeblks),
2104                 offsetof(xfs_agf_t, agf_longest),
2105                 offsetof(xfs_agf_t, agf_btreeblks),
2106                 offsetof(xfs_agf_t, agf_uuid),
2107                 sizeof(xfs_agf_t)
2108         };
2109
2110         trace_xfs_agf(tp->t_mountp, XFS_BUF_TO_AGF(bp), fields, _RET_IP_);
2111
2112         xfs_trans_buf_set_type(tp, bp, XFS_BLFT_AGF_BUF);
2113
2114         xfs_btree_offsets(fields, offsets, XFS_AGF_NUM_BITS, &first, &last);
2115         xfs_trans_log_buf(tp, bp, (uint)first, (uint)last);
2116 }
2117
2118 /*
2119  * Interface for inode allocation to force the pag data to be initialized.
2120  */
2121 int                                     /* error */
2122 xfs_alloc_pagf_init(
2123         xfs_mount_t             *mp,    /* file system mount structure */
2124         xfs_trans_t             *tp,    /* transaction pointer */
2125         xfs_agnumber_t          agno,   /* allocation group number */
2126         int                     flags)  /* XFS_ALLOC_FLAGS_... */
2127 {
2128         xfs_buf_t               *bp;
2129         int                     error;
2130
2131         if ((error = xfs_alloc_read_agf(mp, tp, agno, flags, &bp)))
2132                 return error;
2133         if (bp)
2134                 xfs_trans_brelse(tp, bp);
2135         return 0;
2136 }
2137
2138 /*
2139  * Put the block on the freelist for the allocation group.
2140  */
2141 int                                     /* error */
2142 xfs_alloc_put_freelist(
2143         xfs_trans_t             *tp,    /* transaction pointer */
2144         xfs_buf_t               *agbp,  /* buffer for a.g. freelist header */
2145         xfs_buf_t               *agflbp,/* buffer for a.g. free block array */
2146         xfs_agblock_t           bno,    /* block being freed */
2147         int                     btreeblk) /* block came from a AGF btree */
2148 {
2149         xfs_agf_t               *agf;   /* a.g. freespace structure */
2150         __be32                  *blockp;/* pointer to array entry */
2151         int                     error;
2152         int                     logflags;
2153         xfs_mount_t             *mp;    /* mount structure */
2154         xfs_perag_t             *pag;   /* per allocation group data */
2155         __be32                  *agfl_bno;
2156         int                     startoff;
2157
2158         agf = XFS_BUF_TO_AGF(agbp);
2159         mp = tp->t_mountp;
2160
2161         if (!agflbp && (error = xfs_alloc_read_agfl(mp, tp,
2162                         be32_to_cpu(agf->agf_seqno), &agflbp)))
2163                 return error;
2164         be32_add_cpu(&agf->agf_fllast, 1);
2165         if (be32_to_cpu(agf->agf_fllast) == XFS_AGFL_SIZE(mp))
2166                 agf->agf_fllast = 0;
2167
2168         pag = xfs_perag_get(mp, be32_to_cpu(agf->agf_seqno));
2169         be32_add_cpu(&agf->agf_flcount, 1);
2170         xfs_trans_agflist_delta(tp, 1);
2171         pag->pagf_flcount++;
2172
2173         logflags = XFS_AGF_FLLAST | XFS_AGF_FLCOUNT;
2174         if (btreeblk) {
2175                 be32_add_cpu(&agf->agf_btreeblks, -1);
2176                 pag->pagf_btreeblks--;
2177                 logflags |= XFS_AGF_BTREEBLKS;
2178         }
2179         xfs_perag_put(pag);
2180
2181         xfs_alloc_log_agf(tp, agbp, logflags);
2182
2183         ASSERT(be32_to_cpu(agf->agf_flcount) <= XFS_AGFL_SIZE(mp));
2184
2185         agfl_bno = XFS_BUF_TO_AGFL_BNO(mp, agflbp);
2186         blockp = &agfl_bno[be32_to_cpu(agf->agf_fllast)];
2187         *blockp = cpu_to_be32(bno);
2188         startoff = (char *)blockp - (char *)agflbp->b_addr;
2189
2190         xfs_alloc_log_agf(tp, agbp, logflags);
2191
2192         xfs_trans_buf_set_type(tp, agflbp, XFS_BLFT_AGFL_BUF);
2193         xfs_trans_log_buf(tp, agflbp, startoff,
2194                           startoff + sizeof(xfs_agblock_t) - 1);
2195         return 0;
2196 }
2197
2198 static bool
2199 xfs_agf_verify(
2200         struct xfs_mount *mp,
2201         struct xfs_buf  *bp)
2202  {
2203         struct xfs_agf  *agf = XFS_BUF_TO_AGF(bp);
2204
2205         if (xfs_sb_version_hascrc(&mp->m_sb) &&
2206             !uuid_equal(&agf->agf_uuid, &mp->m_sb.sb_uuid))
2207                         return false;
2208
2209         if (!(agf->agf_magicnum == cpu_to_be32(XFS_AGF_MAGIC) &&
2210               XFS_AGF_GOOD_VERSION(be32_to_cpu(agf->agf_versionnum)) &&
2211               be32_to_cpu(agf->agf_freeblks) <= be32_to_cpu(agf->agf_length) &&
2212               be32_to_cpu(agf->agf_flfirst) < XFS_AGFL_SIZE(mp) &&
2213               be32_to_cpu(agf->agf_fllast) < XFS_AGFL_SIZE(mp) &&
2214               be32_to_cpu(agf->agf_flcount) <= XFS_AGFL_SIZE(mp)))
2215                 return false;
2216
2217         if (be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNO]) > XFS_BTREE_MAXLEVELS ||
2218             be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNT]) > XFS_BTREE_MAXLEVELS)
2219                 return false;
2220
2221         /*
2222          * during growfs operations, the perag is not fully initialised,
2223          * so we can't use it for any useful checking. growfs ensures we can't
2224          * use it by using uncached buffers that don't have the perag attached
2225          * so we can detect and avoid this problem.
2226          */
2227         if (bp->b_pag && be32_to_cpu(agf->agf_seqno) != bp->b_pag->pag_agno)
2228                 return false;
2229
2230         if (xfs_sb_version_haslazysbcount(&mp->m_sb) &&
2231             be32_to_cpu(agf->agf_btreeblks) > be32_to_cpu(agf->agf_length))
2232                 return false;
2233
2234         return true;;
2235
2236 }
2237
2238 static void
2239 xfs_agf_read_verify(
2240         struct xfs_buf  *bp)
2241 {
2242         struct xfs_mount *mp = bp->b_target->bt_mount;
2243
2244         if (xfs_sb_version_hascrc(&mp->m_sb) &&
2245             !xfs_buf_verify_cksum(bp, XFS_AGF_CRC_OFF))
2246                 xfs_buf_ioerror(bp, -EFSBADCRC);
2247         else if (XFS_TEST_ERROR(!xfs_agf_verify(mp, bp), mp,
2248                                 XFS_ERRTAG_ALLOC_READ_AGF,
2249                                 XFS_RANDOM_ALLOC_READ_AGF))
2250                 xfs_buf_ioerror(bp, -EFSCORRUPTED);
2251
2252         if (bp->b_error)
2253                 xfs_verifier_error(bp);
2254 }
2255
2256 static void
2257 xfs_agf_write_verify(
2258         struct xfs_buf  *bp)
2259 {
2260         struct xfs_mount *mp = bp->b_target->bt_mount;
2261         struct xfs_buf_log_item *bip = bp->b_fspriv;
2262
2263         if (!xfs_agf_verify(mp, bp)) {
2264                 xfs_buf_ioerror(bp, -EFSCORRUPTED);
2265                 xfs_verifier_error(bp);
2266                 return;
2267         }
2268
2269         if (!xfs_sb_version_hascrc(&mp->m_sb))
2270                 return;
2271
2272         if (bip)
2273                 XFS_BUF_TO_AGF(bp)->agf_lsn = cpu_to_be64(bip->bli_item.li_lsn);
2274
2275         xfs_buf_update_cksum(bp, XFS_AGF_CRC_OFF);
2276 }
2277
2278 const struct xfs_buf_ops xfs_agf_buf_ops = {
2279         .verify_read = xfs_agf_read_verify,
2280         .verify_write = xfs_agf_write_verify,
2281 };
2282
2283 /*
2284  * Read in the allocation group header (free/alloc section).
2285  */
2286 int                                     /* error */
2287 xfs_read_agf(
2288         struct xfs_mount        *mp,    /* mount point structure */
2289         struct xfs_trans        *tp,    /* transaction pointer */
2290         xfs_agnumber_t          agno,   /* allocation group number */
2291         int                     flags,  /* XFS_BUF_ */
2292         struct xfs_buf          **bpp)  /* buffer for the ag freelist header */
2293 {
2294         int             error;
2295
2296         trace_xfs_read_agf(mp, agno);
2297
2298         ASSERT(agno != NULLAGNUMBER);
2299         error = xfs_trans_read_buf(
2300                         mp, tp, mp->m_ddev_targp,
2301                         XFS_AG_DADDR(mp, agno, XFS_AGF_DADDR(mp)),
2302                         XFS_FSS_TO_BB(mp, 1), flags, bpp, &xfs_agf_buf_ops);
2303         if (error)
2304                 return error;
2305         if (!*bpp)
2306                 return 0;
2307
2308         ASSERT(!(*bpp)->b_error);
2309         xfs_buf_set_ref(*bpp, XFS_AGF_REF);
2310         return 0;
2311 }
2312
2313 /*
2314  * Read in the allocation group header (free/alloc section).
2315  */
2316 int                                     /* error */
2317 xfs_alloc_read_agf(
2318         struct xfs_mount        *mp,    /* mount point structure */
2319         struct xfs_trans        *tp,    /* transaction pointer */
2320         xfs_agnumber_t          agno,   /* allocation group number */
2321         int                     flags,  /* XFS_ALLOC_FLAG_... */
2322         struct xfs_buf          **bpp)  /* buffer for the ag freelist header */
2323 {
2324         struct xfs_agf          *agf;           /* ag freelist header */
2325         struct xfs_perag        *pag;           /* per allocation group data */
2326         int                     error;
2327
2328         trace_xfs_alloc_read_agf(mp, agno);
2329
2330         ASSERT(agno != NULLAGNUMBER);
2331         error = xfs_read_agf(mp, tp, agno,
2332                         (flags & XFS_ALLOC_FLAG_TRYLOCK) ? XBF_TRYLOCK : 0,
2333                         bpp);
2334         if (error)
2335                 return error;
2336         if (!*bpp)
2337                 return 0;
2338         ASSERT(!(*bpp)->b_error);
2339
2340         agf = XFS_BUF_TO_AGF(*bpp);
2341         pag = xfs_perag_get(mp, agno);
2342         if (!pag->pagf_init) {
2343                 pag->pagf_freeblks = be32_to_cpu(agf->agf_freeblks);
2344                 pag->pagf_btreeblks = be32_to_cpu(agf->agf_btreeblks);
2345                 pag->pagf_flcount = be32_to_cpu(agf->agf_flcount);
2346                 pag->pagf_longest = be32_to_cpu(agf->agf_longest);
2347                 pag->pagf_levels[XFS_BTNUM_BNOi] =
2348                         be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNOi]);
2349                 pag->pagf_levels[XFS_BTNUM_CNTi] =
2350                         be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNTi]);
2351                 spin_lock_init(&pag->pagb_lock);
2352                 pag->pagb_count = 0;
2353                 pag->pagb_tree = RB_ROOT;
2354                 pag->pagf_init = 1;
2355         }
2356 #ifdef DEBUG
2357         else if (!XFS_FORCED_SHUTDOWN(mp)) {
2358                 ASSERT(pag->pagf_freeblks == be32_to_cpu(agf->agf_freeblks));
2359                 ASSERT(pag->pagf_btreeblks == be32_to_cpu(agf->agf_btreeblks));
2360                 ASSERT(pag->pagf_flcount == be32_to_cpu(agf->agf_flcount));
2361                 ASSERT(pag->pagf_longest == be32_to_cpu(agf->agf_longest));
2362                 ASSERT(pag->pagf_levels[XFS_BTNUM_BNOi] ==
2363                        be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNOi]));
2364                 ASSERT(pag->pagf_levels[XFS_BTNUM_CNTi] ==
2365                        be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNTi]));
2366         }
2367 #endif
2368         xfs_perag_put(pag);
2369         return 0;
2370 }
2371
2372 /*
2373  * Allocate an extent (variable-size).
2374  * Depending on the allocation type, we either look in a single allocation
2375  * group or loop over the allocation groups to find the result.
2376  */
2377 int                             /* error */
2378 xfs_alloc_vextent(
2379         xfs_alloc_arg_t *args)  /* allocation argument structure */
2380 {
2381         xfs_agblock_t   agsize; /* allocation group size */
2382         int             error;
2383         int             flags;  /* XFS_ALLOC_FLAG_... locking flags */
2384         xfs_extlen_t    minleft;/* minimum left value, temp copy */
2385         xfs_mount_t     *mp;    /* mount structure pointer */
2386         xfs_agnumber_t  sagno;  /* starting allocation group number */
2387         xfs_alloctype_t type;   /* input allocation type */
2388         int             bump_rotor = 0;
2389         int             no_min = 0;
2390         xfs_agnumber_t  rotorstep = xfs_rotorstep; /* inode32 agf stepper */
2391
2392         mp = args->mp;
2393         type = args->otype = args->type;
2394         args->agbno = NULLAGBLOCK;
2395         /*
2396          * Just fix this up, for the case where the last a.g. is shorter
2397          * (or there's only one a.g.) and the caller couldn't easily figure
2398          * that out (xfs_bmap_alloc).
2399          */
2400         agsize = mp->m_sb.sb_agblocks;
2401         if (args->maxlen > agsize)
2402                 args->maxlen = agsize;
2403         if (args->alignment == 0)
2404                 args->alignment = 1;
2405         ASSERT(XFS_FSB_TO_AGNO(mp, args->fsbno) < mp->m_sb.sb_agcount);
2406         ASSERT(XFS_FSB_TO_AGBNO(mp, args->fsbno) < agsize);
2407         ASSERT(args->minlen <= args->maxlen);
2408         ASSERT(args->minlen <= agsize);
2409         ASSERT(args->mod < args->prod);
2410         if (XFS_FSB_TO_AGNO(mp, args->fsbno) >= mp->m_sb.sb_agcount ||
2411             XFS_FSB_TO_AGBNO(mp, args->fsbno) >= agsize ||
2412             args->minlen > args->maxlen || args->minlen > agsize ||
2413             args->mod >= args->prod) {
2414                 args->fsbno = NULLFSBLOCK;
2415                 trace_xfs_alloc_vextent_badargs(args);
2416                 return 0;
2417         }
2418         minleft = args->minleft;
2419
2420         switch (type) {
2421         case XFS_ALLOCTYPE_THIS_AG:
2422         case XFS_ALLOCTYPE_NEAR_BNO:
2423         case XFS_ALLOCTYPE_THIS_BNO:
2424                 /*
2425                  * These three force us into a single a.g.
2426                  */
2427                 args->agno = XFS_FSB_TO_AGNO(mp, args->fsbno);
2428                 args->pag = xfs_perag_get(mp, args->agno);
2429                 args->minleft = 0;
2430                 error = xfs_alloc_fix_freelist(args, 0);
2431                 args->minleft = minleft;
2432                 if (error) {
2433                         trace_xfs_alloc_vextent_nofix(args);
2434                         goto error0;
2435                 }
2436                 if (!args->agbp) {
2437                         trace_xfs_alloc_vextent_noagbp(args);
2438                         break;
2439                 }
2440                 args->agbno = XFS_FSB_TO_AGBNO(mp, args->fsbno);
2441                 if ((error = xfs_alloc_ag_vextent(args)))
2442                         goto error0;
2443                 break;
2444         case XFS_ALLOCTYPE_START_BNO:
2445                 /*
2446                  * Try near allocation first, then anywhere-in-ag after
2447                  * the first a.g. fails.
2448                  */
2449                 if ((args->userdata  == XFS_ALLOC_INITIAL_USER_DATA) &&
2450                     (mp->m_flags & XFS_MOUNT_32BITINODES)) {
2451                         args->fsbno = XFS_AGB_TO_FSB(mp,
2452                                         ((mp->m_agfrotor / rotorstep) %
2453                                         mp->m_sb.sb_agcount), 0);
2454                         bump_rotor = 1;
2455                 }
2456                 args->agbno = XFS_FSB_TO_AGBNO(mp, args->fsbno);
2457                 args->type = XFS_ALLOCTYPE_NEAR_BNO;
2458                 /* FALLTHROUGH */
2459         case XFS_ALLOCTYPE_ANY_AG:
2460         case XFS_ALLOCTYPE_START_AG:
2461         case XFS_ALLOCTYPE_FIRST_AG:
2462                 /*
2463                  * Rotate through the allocation groups looking for a winner.
2464                  */
2465                 if (type == XFS_ALLOCTYPE_ANY_AG) {
2466                         /*
2467                          * Start with the last place we left off.
2468                          */
2469                         args->agno = sagno = (mp->m_agfrotor / rotorstep) %
2470                                         mp->m_sb.sb_agcount;
2471                         args->type = XFS_ALLOCTYPE_THIS_AG;
2472                         flags = XFS_ALLOC_FLAG_TRYLOCK;
2473                 } else if (type == XFS_ALLOCTYPE_FIRST_AG) {
2474                         /*
2475                          * Start with allocation group given by bno.
2476                          */
2477                         args->agno = XFS_FSB_TO_AGNO(mp, args->fsbno);
2478                         args->type = XFS_ALLOCTYPE_THIS_AG;
2479                         sagno = 0;
2480                         flags = 0;
2481                 } else {
2482                         if (type == XFS_ALLOCTYPE_START_AG)
2483                                 args->type = XFS_ALLOCTYPE_THIS_AG;
2484                         /*
2485                          * Start with the given allocation group.
2486                          */
2487                         args->agno = sagno = XFS_FSB_TO_AGNO(mp, args->fsbno);
2488                         flags = XFS_ALLOC_FLAG_TRYLOCK;
2489                 }
2490                 /*
2491                  * Loop over allocation groups twice; first time with
2492                  * trylock set, second time without.
2493                  */
2494                 for (;;) {
2495                         args->pag = xfs_perag_get(mp, args->agno);
2496                         if (no_min) args->minleft = 0;
2497                         error = xfs_alloc_fix_freelist(args, flags);
2498                         args->minleft = minleft;
2499                         if (error) {
2500                                 trace_xfs_alloc_vextent_nofix(args);
2501                                 goto error0;
2502                         }
2503                         /*
2504                          * If we get a buffer back then the allocation will fly.
2505                          */
2506                         if (args->agbp) {
2507                                 if ((error = xfs_alloc_ag_vextent(args)))
2508                                         goto error0;
2509                                 break;
2510                         }
2511
2512                         trace_xfs_alloc_vextent_loopfailed(args);
2513
2514                         /*
2515                          * Didn't work, figure out the next iteration.
2516                          */
2517                         if (args->agno == sagno &&
2518                             type == XFS_ALLOCTYPE_START_BNO)
2519                                 args->type = XFS_ALLOCTYPE_THIS_AG;
2520                         /*
2521                         * For the first allocation, we can try any AG to get
2522                         * space.  However, if we already have allocated a
2523                         * block, we don't want to try AGs whose number is below
2524                         * sagno. Otherwise, we may end up with out-of-order
2525                         * locking of AGF, which might cause deadlock.
2526                         */
2527                         if (++(args->agno) == mp->m_sb.sb_agcount) {
2528                                 if (args->firstblock != NULLFSBLOCK)
2529                                         args->agno = sagno;
2530                                 else
2531                                         args->agno = 0;
2532                         }
2533                         /*
2534                          * Reached the starting a.g., must either be done
2535                          * or switch to non-trylock mode.
2536                          */
2537                         if (args->agno == sagno) {
2538                                 if (no_min == 1) {
2539                                         args->agbno = NULLAGBLOCK;
2540                                         trace_xfs_alloc_vextent_allfailed(args);
2541                                         break;
2542                                 }
2543                                 if (flags == 0) {
2544                                         no_min = 1;
2545                                 } else {
2546                                         flags = 0;
2547                                         if (type == XFS_ALLOCTYPE_START_BNO) {
2548                                                 args->agbno = XFS_FSB_TO_AGBNO(mp,
2549                                                         args->fsbno);
2550                                                 args->type = XFS_ALLOCTYPE_NEAR_BNO;
2551                                         }
2552                                 }
2553                         }
2554                         xfs_perag_put(args->pag);
2555                 }
2556                 if (bump_rotor || (type == XFS_ALLOCTYPE_ANY_AG)) {
2557                         if (args->agno == sagno)
2558                                 mp->m_agfrotor = (mp->m_agfrotor + 1) %
2559                                         (mp->m_sb.sb_agcount * rotorstep);
2560                         else
2561                                 mp->m_agfrotor = (args->agno * rotorstep + 1) %
2562                                         (mp->m_sb.sb_agcount * rotorstep);
2563                 }
2564                 break;
2565         default:
2566                 ASSERT(0);
2567                 /* NOTREACHED */
2568         }
2569         if (args->agbno == NULLAGBLOCK)
2570                 args->fsbno = NULLFSBLOCK;
2571         else {
2572                 args->fsbno = XFS_AGB_TO_FSB(mp, args->agno, args->agbno);
2573 #ifdef DEBUG
2574                 ASSERT(args->len >= args->minlen);
2575                 ASSERT(args->len <= args->maxlen);
2576                 ASSERT(args->agbno % args->alignment == 0);
2577                 XFS_AG_CHECK_DADDR(mp, XFS_FSB_TO_DADDR(mp, args->fsbno),
2578                         args->len);
2579 #endif
2580         }
2581         xfs_perag_put(args->pag);
2582         return 0;
2583 error0:
2584         xfs_perag_put(args->pag);
2585         return error;
2586 }
2587
2588 /*
2589  * Free an extent.
2590  * Just break up the extent address and hand off to xfs_free_ag_extent
2591  * after fixing up the freelist.
2592  */
2593 int                             /* error */
2594 xfs_free_extent(
2595         xfs_trans_t     *tp,    /* transaction pointer */
2596         xfs_fsblock_t   bno,    /* starting block number of extent */
2597         xfs_extlen_t    len)    /* length of extent */
2598 {
2599         xfs_alloc_arg_t args;
2600         int             error;
2601
2602         ASSERT(len != 0);
2603         memset(&args, 0, sizeof(xfs_alloc_arg_t));
2604         args.tp = tp;
2605         args.mp = tp->t_mountp;
2606
2607         /*
2608          * validate that the block number is legal - the enables us to detect
2609          * and handle a silent filesystem corruption rather than crashing.
2610          */
2611         args.agno = XFS_FSB_TO_AGNO(args.mp, bno);
2612         if (args.agno >= args.mp->m_sb.sb_agcount)
2613                 return -EFSCORRUPTED;
2614
2615         args.agbno = XFS_FSB_TO_AGBNO(args.mp, bno);
2616         if (args.agbno >= args.mp->m_sb.sb_agblocks)
2617                 return -EFSCORRUPTED;
2618
2619         args.pag = xfs_perag_get(args.mp, args.agno);
2620         ASSERT(args.pag);
2621
2622         error = xfs_alloc_fix_freelist(&args, XFS_ALLOC_FLAG_FREEING);
2623         if (error)
2624                 goto error0;
2625
2626         /* validate the extent size is legal now we have the agf locked */
2627         if (args.agbno + len >
2628                         be32_to_cpu(XFS_BUF_TO_AGF(args.agbp)->agf_length)) {
2629                 error = -EFSCORRUPTED;
2630                 goto error0;
2631         }
2632
2633         error = xfs_free_ag_extent(tp, args.agbp, args.agno, args.agbno, len, 0);
2634         if (!error)
2635                 xfs_extent_busy_insert(tp, args.agno, args.agbno, len, 0);
2636 error0:
2637         xfs_perag_put(args.pag);
2638         return error;
2639 }