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