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