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