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