fs/xfs/libxfs/xfs_alloc.c

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