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