fs/xfs/xfs_alloc.c

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