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