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