fs/xfs/libxfs/xfs_alloc.c

   1 // SPDX-License-Identifier: GPL-2.0
   2 /*
   3  * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc.
   4  * All Rights Reserved.
   5  */
   6 #include "xfs.h"
   7 #include "xfs_fs.h"
   8 #include "xfs_format.h"
   9 #include "xfs_log_format.h"
  10 #include "xfs_shared.h"
  11 #include "xfs_trans_resv.h"
  12 #include "xfs_bit.h"
  13 #include "xfs_mount.h"
  14 #include "xfs_defer.h"
  15 #include "xfs_btree.h"
  16 #include "xfs_rmap.h"
  17 #include "xfs_alloc_btree.h"
  18 #include "xfs_alloc.h"
  19 #include "xfs_extent_busy.h"
  20 #include "xfs_errortag.h"
  21 #include "xfs_error.h"
  22 #include "xfs_trace.h"
  23 #include "xfs_trans.h"
  24 #include "xfs_buf_item.h"
  25 #include "xfs_log.h"
  26 #include "xfs_ag.h"
  27 #include "xfs_ag_resv.h"
  28 #include "xfs_bmap.h"
  29
  30 extern kmem_zone_t      *xfs_bmap_free_item_zone;
  31
  32 struct workqueue_struct *xfs_alloc_wq;
  33
  34 #define XFS_ABSDIFF(a,b)        (((a) <= (b)) ? ((b) - (a)) : ((a) - (b)))
  35
  36 #define XFSA_FIXUP_BNO_OK       1
  37 #define XFSA_FIXUP_CNT_OK       2
  38
  39 STATIC int xfs_alloc_ag_vextent_exact(xfs_alloc_arg_t *);
  40 STATIC int xfs_alloc_ag_vextent_near(xfs_alloc_arg_t *);
  41 STATIC int xfs_alloc_ag_vextent_size(xfs_alloc_arg_t *);
  42
  43 /*
  44  * Size of the AGFL.  For CRC-enabled filesystes we steal a couple of slots in
  45  * the beginning of the block for a proper header with the location information
  46  * and CRC.
  47  */
  48 unsigned int
  49 xfs_agfl_size(
  50         struct xfs_mount        *mp)
  51 {
  52         unsigned int            size = mp->m_sb.sb_sectsize;
  53
  54         if (xfs_sb_version_hascrc(&mp->m_sb))
  55                 size -= sizeof(struct xfs_agfl);
  56
  57         return size / sizeof(xfs_agblock_t);
  58 }
  59
  60 unsigned int
  61 xfs_refc_block(
  62         struct xfs_mount        *mp)
  63 {
  64         if (xfs_sb_version_hasrmapbt(&mp->m_sb))
  65                 return XFS_RMAP_BLOCK(mp) + 1;
  66         if (xfs_sb_version_hasfinobt(&mp->m_sb))
  67                 return XFS_FIBT_BLOCK(mp) + 1;
  68         return XFS_IBT_BLOCK(mp) + 1;
  69 }
  70
  71 xfs_extlen_t
  72 xfs_prealloc_blocks(
  73         struct xfs_mount        *mp)
  74 {
  75         if (xfs_sb_version_hasreflink(&mp->m_sb))
  76                 return xfs_refc_block(mp) + 1;
  77         if (xfs_sb_version_hasrmapbt(&mp->m_sb))
  78                 return XFS_RMAP_BLOCK(mp) + 1;
  79         if (xfs_sb_version_hasfinobt(&mp->m_sb))
  80                 return XFS_FIBT_BLOCK(mp) + 1;
  81         return XFS_IBT_BLOCK(mp) + 1;
  82 }
  83
  84 /*
  85  * In order to avoid ENOSPC-related deadlock caused by out-of-order locking of
  86  * AGF buffer (PV 947395), we place constraints on the relationship among
  87  * actual allocations for data blocks, freelist blocks, and potential file data
  88  * bmap btree blocks. However, these restrictions may result in no actual space
  89  * allocated for a delayed extent, for example, a data block in a certain AG is
  90  * allocated but there is no additional block for the additional bmap btree
  91  * block due to a split of the bmap btree of the file. The result of this may
  92  * lead to an infinite loop when the file gets flushed to disk and all delayed
  93  * extents need to be actually allocated. To get around this, we explicitly set
  94  * aside a few blocks which will not be reserved in delayed allocation.
  95  *
  96  * We need to reserve 4 fsbs _per AG_ for the freelist and 4 more to handle a
  97  * potential split of the file's bmap btree.
  98  */
  99 unsigned int
 100 xfs_alloc_set_aside(
 101         struct xfs_mount        *mp)
 102 {
 103         return mp->m_sb.sb_agcount * (XFS_ALLOC_AGFL_RESERVE + 4);
 104 }
 105
 106 /*
 107  * When deciding how much space to allocate out of an AG, we limit the
 108  * allocation maximum size to the size the AG. However, we cannot use all the
 109  * blocks in the AG - some are permanently used by metadata. These
 110  * blocks are generally:
 111  *      - the AG superblock, AGF, AGI and AGFL
 112  *      - the AGF (bno and cnt) and AGI btree root blocks, and optionally
 113  *        the AGI free inode and rmap btree root blocks.
 114  *      - blocks on the AGFL according to xfs_alloc_set_aside() limits
 115  *      - the rmapbt root block
 116  *
 117  * The AG headers are sector sized, so the amount of space they take up is
 118  * dependent on filesystem geometry. The others are all single blocks.
 119  */
 120 unsigned int
 121 xfs_alloc_ag_max_usable(
 122         struct xfs_mount        *mp)
 123 {
 124         unsigned int            blocks;
 125
 126         blocks = XFS_BB_TO_FSB(mp, XFS_FSS_TO_BB(mp, 4)); /* ag headers */
 127         blocks += XFS_ALLOC_AGFL_RESERVE;
 128         blocks += 3;                    /* AGF, AGI btree root blocks */
 129         if (xfs_sb_version_hasfinobt(&mp->m_sb))
 130                 blocks++;               /* finobt root block */
 131         if (xfs_sb_version_hasrmapbt(&mp->m_sb))
 132                 blocks++;               /* rmap root block */
 133         if (xfs_sb_version_hasreflink(&mp->m_sb))
 134                 blocks++;               /* refcount root block */
 135
 136         return mp->m_sb.sb_agblocks - blocks;
 137 }
 138
 139 /*
 140  * Lookup the record equal to [bno, len] in the btree given by cur.
 141  */
 142 STATIC int                              /* error */
 143 xfs_alloc_lookup_eq(
 144         struct xfs_btree_cur    *cur,   /* btree cursor */
 145         xfs_agblock_t           bno,    /* starting block of extent */
 146         xfs_extlen_t            len,    /* length of extent */
 147         int                     *stat)  /* success/failure */
 148 {
 149         int                     error;
 150
 151         cur->bc_rec.a.ar_startblock = bno;
 152         cur->bc_rec.a.ar_blockcount = len;
 153         error = xfs_btree_lookup(cur, XFS_LOOKUP_EQ, stat);
 154         cur->bc_ag.abt.active = (*stat == 1);
 155         return error;
 156 }
 157
 158 /*
 159  * Lookup the first record greater than or equal to [bno, len]
 160  * in the btree given by cur.
 161  */
 162 int                             /* error */
 163 xfs_alloc_lookup_ge(
 164         struct xfs_btree_cur    *cur,   /* btree cursor */
 165         xfs_agblock_t           bno,    /* starting block of extent */
 166         xfs_extlen_t            len,    /* length of extent */
 167         int                     *stat)  /* success/failure */
 168 {
 169         int                     error;
 170
 171         cur->bc_rec.a.ar_startblock = bno;
 172         cur->bc_rec.a.ar_blockcount = len;
 173         error = xfs_btree_lookup(cur, XFS_LOOKUP_GE, stat);
 174         cur->bc_ag.abt.active = (*stat == 1);
 175         return error;
 176 }
 177
 178 /*
 179  * Lookup the first record less than or equal to [bno, len]
 180  * in the btree given by cur.
 181  */
 182 int                                     /* error */
 183 xfs_alloc_lookup_le(
 184         struct xfs_btree_cur    *cur,   /* btree cursor */
 185         xfs_agblock_t           bno,    /* starting block of extent */
 186         xfs_extlen_t            len,    /* length of extent */
 187         int                     *stat)  /* success/failure */
 188 {
 189         int                     error;
 190         cur->bc_rec.a.ar_startblock = bno;
 191         cur->bc_rec.a.ar_blockcount = len;
 192         error = xfs_btree_lookup(cur, XFS_LOOKUP_LE, stat);
 193         cur->bc_ag.abt.active = (*stat == 1);
 194         return error;
 195 }
 196
 197 static inline bool
 198 xfs_alloc_cur_active(
 199         struct xfs_btree_cur    *cur)
 200 {
 201         return cur && cur->bc_ag.abt.active;
 202 }
 203
 204 /*
 205  * Update the record referred to by cur to the value given
 206  * by [bno, len].
 207  * This either works (return 0) or gets an EFSCORRUPTED error.
 208  */
 209 STATIC int                              /* error */
 210 xfs_alloc_update(
 211         struct xfs_btree_cur    *cur,   /* btree cursor */
 212         xfs_agblock_t           bno,    /* starting block of extent */
 213         xfs_extlen_t            len)    /* length of extent */
 214 {
 215         union xfs_btree_rec     rec;
 216
 217         rec.alloc.ar_startblock = cpu_to_be32(bno);
 218         rec.alloc.ar_blockcount = cpu_to_be32(len);
 219         return xfs_btree_update(cur, &rec);
 220 }
 221
 222 /*
 223  * Get the data from the pointed-to record.
 224  */
 225 int                                     /* error */
 226 xfs_alloc_get_rec(
 227         struct xfs_btree_cur    *cur,   /* btree cursor */
 228         xfs_agblock_t           *bno,   /* output: starting block of extent */
 229         xfs_extlen_t            *len,   /* output: length of extent */
 230         int                     *stat)  /* output: success/failure */
 231 {
 232         struct xfs_mount        *mp = cur->bc_mp;
 233         xfs_agnumber_t          agno = cur->bc_ag.pag->pag_agno;
 234         union xfs_btree_rec     *rec;
 235         int                     error;
 236
 237         error = xfs_btree_get_rec(cur, &rec, stat);
 238         if (error || !(*stat))
 239                 return error;
 240
 241         *bno = be32_to_cpu(rec->alloc.ar_startblock);
 242         *len = be32_to_cpu(rec->alloc.ar_blockcount);
 243
 244         if (*len == 0)
 245                 goto out_bad_rec;
 246
 247         /* check for valid extent range, including overflow */
 248         if (!xfs_verify_agbno(mp, agno, *bno))
 249                 goto out_bad_rec;
 250         if (*bno > *bno + *len)
 251                 goto out_bad_rec;
 252         if (!xfs_verify_agbno(mp, agno, *bno + *len - 1))
 253                 goto out_bad_rec;
 254
 255         return 0;
 256
 257 out_bad_rec:
 258         xfs_warn(mp,
 259                 "%s Freespace BTree record corruption in AG %d detected!",
 260                 cur->bc_btnum == XFS_BTNUM_BNO ? "Block" : "Size", agno);
 261         xfs_warn(mp,
 262                 "start block 0x%x block count 0x%x", *bno, *len);
 263         return -EFSCORRUPTED;
 264 }
 265
 266 /*
 267  * Compute aligned version of the found extent.
 268  * Takes alignment and min length into account.
 269  */
 270 STATIC bool
 271 xfs_alloc_compute_aligned(
 272         xfs_alloc_arg_t *args,          /* allocation argument structure */
 273         xfs_agblock_t   foundbno,       /* starting block in found extent */
 274         xfs_extlen_t    foundlen,       /* length in found extent */
 275         xfs_agblock_t   *resbno,        /* result block number */
 276         xfs_extlen_t    *reslen,        /* result length */
 277         unsigned        *busy_gen)
 278 {
 279         xfs_agblock_t   bno = foundbno;
 280         xfs_extlen_t    len = foundlen;
 281         xfs_extlen_t    diff;
 282         bool            busy;
 283
 284         /* Trim busy sections out of found extent */
 285         busy = xfs_extent_busy_trim(args, &bno, &len, busy_gen);
 286
 287         /*
 288          * If we have a largish extent that happens to start before min_agbno,
 289          * see if we can shift it into range...
 290          */
 291         if (bno < args->min_agbno && bno + len > args->min_agbno) {
 292                 diff = args->min_agbno - bno;
 293                 if (len > diff) {
 294                         bno += diff;
 295                         len -= diff;
 296                 }
 297         }
 298
 299         if (args->alignment > 1 && len >= args->minlen) {
 300                 xfs_agblock_t   aligned_bno = roundup(bno, args->alignment);
 301
 302                 diff = aligned_bno - bno;
 303
 304                 *resbno = aligned_bno;
 305                 *reslen = diff >= len ? 0 : len - diff;
 306         } else {
 307                 *resbno = bno;
 308                 *reslen = len;
 309         }
 310
 311         return busy;
 312 }
 313
 314 /*
 315  * Compute best start block and diff for "near" allocations.
 316  * freelen >= wantlen already checked by caller.
 317  */
 318 STATIC xfs_extlen_t                     /* difference value (absolute) */
 319 xfs_alloc_compute_diff(
 320         xfs_agblock_t   wantbno,        /* target starting block */
 321         xfs_extlen_t    wantlen,        /* target length */
 322         xfs_extlen_t    alignment,      /* target alignment */
 323         int             datatype,       /* are we allocating data? */
 324         xfs_agblock_t   freebno,        /* freespace's starting block */
 325         xfs_extlen_t    freelen,        /* freespace's length */
 326         xfs_agblock_t   *newbnop)       /* result: best start block from free */
 327 {
 328         xfs_agblock_t   freeend;        /* end of freespace extent */
 329         xfs_agblock_t   newbno1;        /* return block number */
 330         xfs_agblock_t   newbno2;        /* other new block number */
 331         xfs_extlen_t    newlen1=0;      /* length with newbno1 */
 332         xfs_extlen_t    newlen2=0;      /* length with newbno2 */
 333         xfs_agblock_t   wantend;        /* end of target extent */
 334         bool            userdata = datatype & XFS_ALLOC_USERDATA;
 335
 336         ASSERT(freelen >= wantlen);
 337         freeend = freebno + freelen;
 338         wantend = wantbno + wantlen;
 339         /*
 340          * We want to allocate from the start of a free extent if it is past
 341          * the desired block or if we are allocating user data and the free
 342          * extent is before desired block. The second case is there to allow
 343          * for contiguous allocation from the remaining free space if the file
 344          * grows in the short term.
 345          */
 346         if (freebno >= wantbno || (userdata && freeend < wantend)) {
 347                 if ((newbno1 = roundup(freebno, alignment)) >= freeend)
 348                         newbno1 = NULLAGBLOCK;
 349         } else if (freeend >= wantend && alignment > 1) {
 350                 newbno1 = roundup(wantbno, alignment);
 351                 newbno2 = newbno1 - alignment;
 352                 if (newbno1 >= freeend)
 353                         newbno1 = NULLAGBLOCK;
 354                 else
 355                         newlen1 = XFS_EXTLEN_MIN(wantlen, freeend - newbno1);
 356                 if (newbno2 < freebno)
 357                         newbno2 = NULLAGBLOCK;
 358                 else
 359                         newlen2 = XFS_EXTLEN_MIN(wantlen, freeend - newbno2);
 360                 if (newbno1 != NULLAGBLOCK && newbno2 != NULLAGBLOCK) {
 361                         if (newlen1 < newlen2 ||
 362                             (newlen1 == newlen2 &&
 363                              XFS_ABSDIFF(newbno1, wantbno) >
 364                              XFS_ABSDIFF(newbno2, wantbno)))
 365                                 newbno1 = newbno2;
 366                 } else if (newbno2 != NULLAGBLOCK)
 367                         newbno1 = newbno2;
 368         } else if (freeend >= wantend) {
 369                 newbno1 = wantbno;
 370         } else if (alignment > 1) {
 371                 newbno1 = roundup(freeend - wantlen, alignment);
 372                 if (newbno1 > freeend - wantlen &&
 373                     newbno1 - alignment >= freebno)
 374                         newbno1 -= alignment;
 375                 else if (newbno1 >= freeend)
 376                         newbno1 = NULLAGBLOCK;
 377         } else
 378                 newbno1 = freeend - wantlen;
 379         *newbnop = newbno1;
 380         return newbno1 == NULLAGBLOCK ? 0 : XFS_ABSDIFF(newbno1, wantbno);
 381 }
 382
 383 /*
 384  * Fix up the length, based on mod and prod.
 385  * len should be k * prod + mod for some k.
 386  * If len is too small it is returned unchanged.
 387  * If len hits maxlen it is left alone.
 388  */
 389 STATIC void
 390 xfs_alloc_fix_len(
 391         xfs_alloc_arg_t *args)          /* allocation argument structure */
 392 {
 393         xfs_extlen_t    k;
 394         xfs_extlen_t    rlen;
 395
 396         ASSERT(args->mod < args->prod);
 397         rlen = args->len;
 398         ASSERT(rlen >= args->minlen);
 399         ASSERT(rlen <= args->maxlen);
 400         if (args->prod <= 1 || rlen < args->mod || rlen == args->maxlen ||
 401             (args->mod == 0 && rlen < args->prod))
 402                 return;
 403         k = rlen % args->prod;
 404         if (k == args->mod)
 405                 return;
 406         if (k > args->mod)
 407                 rlen = rlen - (k - args->mod);
 408         else
 409                 rlen = rlen - args->prod + (args->mod - k);
 410         /* casts to (int) catch length underflows */
 411         if ((int)rlen < (int)args->minlen)
 412                 return;
 413         ASSERT(rlen >= args->minlen && rlen <= args->maxlen);
 414         ASSERT(rlen % args->prod == args->mod);
 415         ASSERT(args->pag->pagf_freeblks + args->pag->pagf_flcount >=
 416                 rlen + args->minleft);
 417         args->len = rlen;
 418 }
 419
 420 /*
 421  * Update the two btrees, logically removing from freespace the extent
 422  * starting at rbno, rlen blocks.  The extent is contained within the
 423  * actual (current) free extent fbno for flen blocks.
 424  * Flags are passed in indicating whether the cursors are set to the
 425  * relevant records.
 426  */
 427 STATIC int                              /* error code */
 428 xfs_alloc_fixup_trees(
 429         xfs_btree_cur_t *cnt_cur,       /* cursor for by-size btree */
 430         xfs_btree_cur_t *bno_cur,       /* cursor for by-block btree */
 431         xfs_agblock_t   fbno,           /* starting block of free extent */
 432         xfs_extlen_t    flen,           /* length of free extent */
 433         xfs_agblock_t   rbno,           /* starting block of returned extent */
 434         xfs_extlen_t    rlen,           /* length of returned extent */
 435         int             flags)          /* flags, XFSA_FIXUP_... */
 436 {
 437         int             error;          /* error code */
 438         int             i;              /* operation results */
 439         xfs_agblock_t   nfbno1;         /* first new free startblock */
 440         xfs_agblock_t   nfbno2;         /* second new free startblock */
 441         xfs_extlen_t    nflen1=0;       /* first new free length */
 442         xfs_extlen_t    nflen2=0;       /* second new free length */
 443         struct xfs_mount *mp;
 444
 445         mp = cnt_cur->bc_mp;
 446
 447         /*
 448          * Look up the record in the by-size tree if necessary.
 449          */
 450         if (flags & XFSA_FIXUP_CNT_OK) {
 451 #ifdef DEBUG
 452                 if ((error = xfs_alloc_get_rec(cnt_cur, &nfbno1, &nflen1, &i)))
 453                         return error;
 454                 if (XFS_IS_CORRUPT(mp,
 455                                    i != 1 ||
 456                                    nfbno1 != fbno ||
 457                                    nflen1 != flen))
 458                         return -EFSCORRUPTED;
 459 #endif
 460         } else {
 461                 if ((error = xfs_alloc_lookup_eq(cnt_cur, fbno, flen, &i)))
 462                         return error;
 463                 if (XFS_IS_CORRUPT(mp, i != 1))
 464                         return -EFSCORRUPTED;
 465         }
 466         /*
 467          * Look up the record in the by-block tree if necessary.
 468          */
 469         if (flags & XFSA_FIXUP_BNO_OK) {
 470 #ifdef DEBUG
 471                 if ((error = xfs_alloc_get_rec(bno_cur, &nfbno1, &nflen1, &i)))
 472                         return error;
 473                 if (XFS_IS_CORRUPT(mp,
 474                                    i != 1 ||
 475                                    nfbno1 != fbno ||
 476                                    nflen1 != flen))
 477                         return -EFSCORRUPTED;
 478 #endif
 479         } else {
 480                 if ((error = xfs_alloc_lookup_eq(bno_cur, fbno, flen, &i)))
 481                         return error;
 482                 if (XFS_IS_CORRUPT(mp, i != 1))
 483                         return -EFSCORRUPTED;
 484         }
 485
 486 #ifdef DEBUG
 487         if (bno_cur->bc_nlevels == 1 && cnt_cur->bc_nlevels == 1) {
 488                 struct xfs_btree_block  *bnoblock;
 489                 struct xfs_btree_block  *cntblock;
 490
 491                 bnoblock = XFS_BUF_TO_BLOCK(bno_cur->bc_bufs[0]);
 492                 cntblock = XFS_BUF_TO_BLOCK(cnt_cur->bc_bufs[0]);
 493
 494                 if (XFS_IS_CORRUPT(mp,
 495                                    bnoblock->bb_numrecs !=
 496                                    cntblock->bb_numrecs))
 497                         return -EFSCORRUPTED;
 498         }
 499 #endif
 500
 501         /*
 502          * Deal with all four cases: the allocated record is contained
 503          * within the freespace record, so we can have new freespace
 504          * at either (or both) end, or no freespace remaining.
 505          */
 506         if (rbno == fbno && rlen == flen)
 507                 nfbno1 = nfbno2 = NULLAGBLOCK;
 508         else if (rbno == fbno) {
 509                 nfbno1 = rbno + rlen;
 510                 nflen1 = flen - rlen;
 511                 nfbno2 = NULLAGBLOCK;
 512         } else if (rbno + rlen == fbno + flen) {
 513                 nfbno1 = fbno;
 514                 nflen1 = flen - rlen;
 515                 nfbno2 = NULLAGBLOCK;
 516         } else {
 517                 nfbno1 = fbno;
 518                 nflen1 = rbno - fbno;
 519                 nfbno2 = rbno + rlen;
 520                 nflen2 = (fbno + flen) - nfbno2;
 521         }
 522         /*
 523          * Delete the entry from the by-size btree.
 524          */
 525         if ((error = xfs_btree_delete(cnt_cur, &i)))
 526                 return error;
 527         if (XFS_IS_CORRUPT(mp, i != 1))
 528                 return -EFSCORRUPTED;
 529         /*
 530          * Add new by-size btree entry(s).
 531          */
 532         if (nfbno1 != NULLAGBLOCK) {
 533                 if ((error = xfs_alloc_lookup_eq(cnt_cur, nfbno1, nflen1, &i)))
 534                         return error;
 535                 if (XFS_IS_CORRUPT(mp, i != 0))
 536                         return -EFSCORRUPTED;
 537                 if ((error = xfs_btree_insert(cnt_cur, &i)))
 538                         return error;
 539                 if (XFS_IS_CORRUPT(mp, i != 1))
 540                         return -EFSCORRUPTED;
 541         }
 542         if (nfbno2 != NULLAGBLOCK) {
 543                 if ((error = xfs_alloc_lookup_eq(cnt_cur, nfbno2, nflen2, &i)))
 544                         return error;
 545                 if (XFS_IS_CORRUPT(mp, i != 0))
 546                         return -EFSCORRUPTED;
 547                 if ((error = xfs_btree_insert(cnt_cur, &i)))
 548                         return error;
 549                 if (XFS_IS_CORRUPT(mp, i != 1))
 550                         return -EFSCORRUPTED;
 551         }
 552         /*
 553          * Fix up the by-block btree entry(s).
 554          */
 555         if (nfbno1 == NULLAGBLOCK) {
 556                 /*
 557                  * No remaining freespace, just delete the by-block tree entry.
 558                  */
 559                 if ((error = xfs_btree_delete(bno_cur, &i)))
 560                         return error;
 561                 if (XFS_IS_CORRUPT(mp, i != 1))
 562                         return -EFSCORRUPTED;
 563         } else {
 564                 /*
 565                  * Update the by-block entry to start later|be shorter.
 566                  */
 567                 if ((error = xfs_alloc_update(bno_cur, nfbno1, nflen1)))
 568                         return error;
 569         }
 570         if (nfbno2 != NULLAGBLOCK) {
 571                 /*
 572                  * 2 resulting free entries, need to add one.
 573                  */
 574                 if ((error = xfs_alloc_lookup_eq(bno_cur, nfbno2, nflen2, &i)))
 575                         return error;
 576                 if (XFS_IS_CORRUPT(mp, i != 0))
 577                         return -EFSCORRUPTED;
 578                 if ((error = xfs_btree_insert(bno_cur, &i)))
 579                         return error;
 580                 if (XFS_IS_CORRUPT(mp, i != 1))
 581                         return -EFSCORRUPTED;
 582         }
 583         return 0;
 584 }
 585
 586 static xfs_failaddr_t
 587 xfs_agfl_verify(
 588         struct xfs_buf  *bp)
 589 {
 590         struct xfs_mount *mp = bp->b_mount;
 591         struct xfs_agfl *agfl = XFS_BUF_TO_AGFL(bp);
 592         __be32          *agfl_bno = xfs_buf_to_agfl_bno(bp);
 593         int             i;
 594
 595         /*
 596          * There is no verification of non-crc AGFLs because mkfs does not
 597          * initialise the AGFL to zero or NULL. Hence the only valid part of the
 598          * AGFL is what the AGF says is active. We can't get to the AGF, so we
 599          * can't verify just those entries are valid.
 600          */
 601         if (!xfs_sb_version_hascrc(&mp->m_sb))
 602                 return NULL;
 603
 604         if (!xfs_verify_magic(bp, agfl->agfl_magicnum))
 605                 return __this_address;
 606         if (!uuid_equal(&agfl->agfl_uuid, &mp->m_sb.sb_meta_uuid))
 607                 return __this_address;
 608         /*
 609          * during growfs operations, the perag is not fully initialised,
 610          * so we can't use it for any useful checking. growfs ensures we can't
 611          * use it by using uncached buffers that don't have the perag attached
 612          * so we can detect and avoid this problem.
 613          */
 614         if (bp->b_pag && be32_to_cpu(agfl->agfl_seqno) != bp->b_pag->pag_agno)
 615                 return __this_address;
 616
 617         for (i = 0; i < xfs_agfl_size(mp); i++) {
 618                 if (be32_to_cpu(agfl_bno[i]) != NULLAGBLOCK &&
 619                     be32_to_cpu(agfl_bno[i]) >= mp->m_sb.sb_agblocks)
 620                         return __this_address;
 621         }
 622
 623         if (!xfs_log_check_lsn(mp, be64_to_cpu(XFS_BUF_TO_AGFL(bp)->agfl_lsn)))
 624                 return __this_address;
 625         return NULL;
 626 }
 627
 628 static void
 629 xfs_agfl_read_verify(
 630         struct xfs_buf  *bp)
 631 {
 632         struct xfs_mount *mp = bp->b_mount;
 633         xfs_failaddr_t  fa;
 634
 635         /*
 636          * There is no verification of non-crc AGFLs because mkfs does not
 637          * initialise the AGFL to zero or NULL. Hence the only valid part of the
 638          * AGFL is what the AGF says is active. We can't get to the AGF, so we
 639          * can't verify just those entries are valid.
 640          */
 641         if (!xfs_sb_version_hascrc(&mp->m_sb))
 642                 return;
 643
 644         if (!xfs_buf_verify_cksum(bp, XFS_AGFL_CRC_OFF))
 645                 xfs_verifier_error(bp, -EFSBADCRC, __this_address);
 646         else {
 647                 fa = xfs_agfl_verify(bp);
 648                 if (fa)
 649                         xfs_verifier_error(bp, -EFSCORRUPTED, fa);
 650         }
 651 }
 652
 653 static void
 654 xfs_agfl_write_verify(
 655         struct xfs_buf  *bp)
 656 {
 657         struct xfs_mount        *mp = bp->b_mount;
 658         struct xfs_buf_log_item *bip = bp->b_log_item;
 659         xfs_failaddr_t          fa;
 660
 661         /* no verification of non-crc AGFLs */
 662         if (!xfs_sb_version_hascrc(&mp->m_sb))
 663                 return;
 664
 665         fa = xfs_agfl_verify(bp);
 666         if (fa) {
 667                 xfs_verifier_error(bp, -EFSCORRUPTED, fa);
 668                 return;
 669         }
 670
 671         if (bip)
 672                 XFS_BUF_TO_AGFL(bp)->agfl_lsn = cpu_to_be64(bip->bli_item.li_lsn);
 673
 674         xfs_buf_update_cksum(bp, XFS_AGFL_CRC_OFF);
 675 }
 676
 677 const struct xfs_buf_ops xfs_agfl_buf_ops = {
 678         .name = "xfs_agfl",
 679         .magic = { cpu_to_be32(XFS_AGFL_MAGIC), cpu_to_be32(XFS_AGFL_MAGIC) },
 680         .verify_read = xfs_agfl_read_verify,
 681         .verify_write = xfs_agfl_write_verify,
 682         .verify_struct = xfs_agfl_verify,
 683 };
 684
 685 /*
 686  * Read in the allocation group free block array.
 687  */
 688 int                                     /* error */
 689 xfs_alloc_read_agfl(
 690         xfs_mount_t     *mp,            /* mount point structure */
 691         xfs_trans_t     *tp,            /* transaction pointer */
 692         xfs_agnumber_t  agno,           /* allocation group number */
 693         struct xfs_buf  **bpp)          /* buffer for the ag free block array */
 694 {
 695         struct xfs_buf  *bp;            /* return value */
 696         int             error;
 697
 698         ASSERT(agno != NULLAGNUMBER);
 699         error = xfs_trans_read_buf(
 700                         mp, tp, mp->m_ddev_targp,
 701                         XFS_AG_DADDR(mp, agno, XFS_AGFL_DADDR(mp)),
 702                         XFS_FSS_TO_BB(mp, 1), 0, &bp, &xfs_agfl_buf_ops);
 703         if (error)
 704                 return error;
 705         xfs_buf_set_ref(bp, XFS_AGFL_REF);
 706         *bpp = bp;
 707         return 0;
 708 }
 709
 710 STATIC int
 711 xfs_alloc_update_counters(
 712         struct xfs_trans        *tp,
 713         struct xfs_buf          *agbp,
 714         long                    len)
 715 {
 716         struct xfs_agf          *agf = agbp->b_addr;
 717
 718         agbp->b_pag->pagf_freeblks += len;
 719         be32_add_cpu(&agf->agf_freeblks, len);
 720
 721         if (unlikely(be32_to_cpu(agf->agf_freeblks) >
 722                      be32_to_cpu(agf->agf_length))) {
 723                 xfs_buf_mark_corrupt(agbp);
 724                 return -EFSCORRUPTED;
 725         }
 726
 727         xfs_alloc_log_agf(tp, agbp, XFS_AGF_FREEBLKS);
 728         return 0;
 729 }
 730
 731 /*
 732  * Block allocation algorithm and data structures.
 733  */
 734 struct xfs_alloc_cur {
 735         struct xfs_btree_cur            *cnt;   /* btree cursors */
 736         struct xfs_btree_cur            *bnolt;
 737         struct xfs_btree_cur            *bnogt;
 738         xfs_extlen_t                    cur_len;/* current search length */
 739         xfs_agblock_t                   rec_bno;/* extent startblock */
 740         xfs_extlen_t                    rec_len;/* extent length */
 741         xfs_agblock_t                   bno;    /* alloc bno */
 742         xfs_extlen_t                    len;    /* alloc len */
 743         xfs_extlen_t                    diff;   /* diff from search bno */
 744         unsigned int                    busy_gen;/* busy state */
 745         bool                            busy;
 746 };
 747
 748 /*
 749  * Set up cursors, etc. in the extent allocation cursor. This function can be
 750  * called multiple times to reset an initialized structure without having to
 751  * reallocate cursors.
 752  */
 753 static int
 754 xfs_alloc_cur_setup(
 755         struct xfs_alloc_arg    *args,
 756         struct xfs_alloc_cur    *acur)
 757 {
 758         int                     error;
 759         int                     i;
 760
 761         ASSERT(args->alignment == 1 || args->type != XFS_ALLOCTYPE_THIS_BNO);
 762
 763         acur->cur_len = args->maxlen;
 764         acur->rec_bno = 0;
 765         acur->rec_len = 0;
 766         acur->bno = 0;
 767         acur->len = 0;
 768         acur->diff = -1;
 769         acur->busy = false;
 770         acur->busy_gen = 0;
 771
 772         /*
 773          * Perform an initial cntbt lookup to check for availability of maxlen
 774          * extents. If this fails, we'll return -ENOSPC to signal the caller to
 775          * attempt a small allocation.
 776          */
 777         if (!acur->cnt)
 778                 acur->cnt = xfs_allocbt_init_cursor(args->mp, args->tp,
 779                                         args->agbp, args->pag, XFS_BTNUM_CNT);
 780         error = xfs_alloc_lookup_ge(acur->cnt, 0, args->maxlen, &i);
 781         if (error)
 782                 return error;
 783
 784         /*
 785          * Allocate the bnobt left and right search cursors.
 786          */
 787         if (!acur->bnolt)
 788                 acur->bnolt = xfs_allocbt_init_cursor(args->mp, args->tp,
 789                                         args->agbp, args->pag, XFS_BTNUM_BNO);
 790         if (!acur->bnogt)
 791                 acur->bnogt = xfs_allocbt_init_cursor(args->mp, args->tp,
 792                                         args->agbp, args->pag, XFS_BTNUM_BNO);
 793         return i == 1 ? 0 : -ENOSPC;
 794 }
 795
 796 static void
 797 xfs_alloc_cur_close(
 798         struct xfs_alloc_cur    *acur,
 799         bool                    error)
 800 {
 801         int                     cur_error = XFS_BTREE_NOERROR;
 802
 803         if (error)
 804                 cur_error = XFS_BTREE_ERROR;
 805
 806         if (acur->cnt)
 807                 xfs_btree_del_cursor(acur->cnt, cur_error);
 808         if (acur->bnolt)
 809                 xfs_btree_del_cursor(acur->bnolt, cur_error);
 810         if (acur->bnogt)
 811                 xfs_btree_del_cursor(acur->bnogt, cur_error);
 812         acur->cnt = acur->bnolt = acur->bnogt = NULL;
 813 }
 814
 815 /*
 816  * Check an extent for allocation and track the best available candidate in the
 817  * allocation structure. The cursor is deactivated if it has entered an out of
 818  * range state based on allocation arguments. Optionally return the extent
 819  * extent geometry and allocation status if requested by the caller.
 820  */
 821 static int
 822 xfs_alloc_cur_check(
 823         struct xfs_alloc_arg    *args,
 824         struct xfs_alloc_cur    *acur,
 825         struct xfs_btree_cur    *cur,
 826         int                     *new)
 827 {
 828         int                     error, i;
 829         xfs_agblock_t           bno, bnoa, bnew;
 830         xfs_extlen_t            len, lena, diff = -1;
 831         bool                    busy;
 832         unsigned                busy_gen = 0;
 833         bool                    deactivate = false;
 834         bool                    isbnobt = cur->bc_btnum == XFS_BTNUM_BNO;
 835
 836         *new = 0;
 837
 838         error = xfs_alloc_get_rec(cur, &bno, &len, &i);
 839         if (error)
 840                 return error;
 841         if (XFS_IS_CORRUPT(args->mp, i != 1))
 842                 return -EFSCORRUPTED;
 843
 844         /*
 845          * Check minlen and deactivate a cntbt cursor if out of acceptable size
 846          * range (i.e., walking backwards looking for a minlen extent).
 847          */
 848         if (len < args->minlen) {
 849                 deactivate = !isbnobt;
 850                 goto out;
 851         }
 852
 853         busy = xfs_alloc_compute_aligned(args, bno, len, &bnoa, &lena,
 854                                          &busy_gen);
 855         acur->busy |= busy;
 856         if (busy)
 857                 acur->busy_gen = busy_gen;
 858         /* deactivate a bnobt cursor outside of locality range */
 859         if (bnoa < args->min_agbno || bnoa > args->max_agbno) {
 860                 deactivate = isbnobt;
 861                 goto out;
 862         }
 863         if (lena < args->minlen)
 864                 goto out;
 865
 866         args->len = XFS_EXTLEN_MIN(lena, args->maxlen);
 867         xfs_alloc_fix_len(args);
 868         ASSERT(args->len >= args->minlen);
 869         if (args->len < acur->len)
 870                 goto out;
 871
 872         /*
 873          * We have an aligned record that satisfies minlen and beats or matches
 874          * the candidate extent size. Compare locality for near allocation mode.
 875          */
 876         ASSERT(args->type == XFS_ALLOCTYPE_NEAR_BNO);
 877         diff = xfs_alloc_compute_diff(args->agbno, args->len,
 878                                       args->alignment, args->datatype,
 879                                       bnoa, lena, &bnew);
 880         if (bnew == NULLAGBLOCK)
 881                 goto out;
 882
 883         /*
 884          * Deactivate a bnobt cursor with worse locality than the current best.
 885          */
 886         if (diff > acur->diff) {
 887                 deactivate = isbnobt;
 888                 goto out;
 889         }
 890
 891         ASSERT(args->len > acur->len ||
 892                (args->len == acur->len && diff <= acur->diff));
 893         acur->rec_bno = bno;
 894         acur->rec_len = len;
 895         acur->bno = bnew;
 896         acur->len = args->len;
 897         acur->diff = diff;
 898         *new = 1;
 899
 900         /*
 901          * We're done if we found a perfect allocation. This only deactivates
 902          * the current cursor, but this is just an optimization to terminate a
 903          * cntbt search that otherwise runs to the edge of the tree.
 904          */
 905         if (acur->diff == 0 && acur->len == args->maxlen)
 906                 deactivate = true;
 907 out:
 908         if (deactivate)
 909                 cur->bc_ag.abt.active = false;
 910         trace_xfs_alloc_cur_check(args->mp, cur->bc_btnum, bno, len, diff,
 911                                   *new);
 912         return 0;
 913 }
 914
 915 /*
 916  * Complete an allocation of a candidate extent. Remove the extent from both
 917  * trees and update the args structure.
 918  */
 919 STATIC int
 920 xfs_alloc_cur_finish(
 921         struct xfs_alloc_arg    *args,
 922         struct xfs_alloc_cur    *acur)
 923 {
 924         struct xfs_agf __maybe_unused *agf = args->agbp->b_addr;
 925         int                     error;
 926
 927         ASSERT(acur->cnt && acur->bnolt);
 928         ASSERT(acur->bno >= acur->rec_bno);
 929         ASSERT(acur->bno + acur->len <= acur->rec_bno + acur->rec_len);
 930         ASSERT(acur->rec_bno + acur->rec_len <= be32_to_cpu(agf->agf_length));
 931
 932         error = xfs_alloc_fixup_trees(acur->cnt, acur->bnolt, acur->rec_bno,
 933                                       acur->rec_len, acur->bno, acur->len, 0);
 934         if (error)
 935                 return error;
 936
 937         args->agbno = acur->bno;
 938         args->len = acur->len;
 939         args->wasfromfl = 0;
 940
 941         trace_xfs_alloc_cur(args);
 942         return 0;
 943 }
 944
 945 /*
 946  * Locality allocation lookup algorithm. This expects a cntbt cursor and uses
 947  * bno optimized lookup to search for extents with ideal size and locality.
 948  */
 949 STATIC int
 950 xfs_alloc_cntbt_iter(
 951         struct xfs_alloc_arg            *args,
 952         struct xfs_alloc_cur            *acur)
 953 {
 954         struct xfs_btree_cur    *cur = acur->cnt;
 955         xfs_agblock_t           bno;
 956         xfs_extlen_t            len, cur_len;
 957         int                     error;
 958         int                     i;
 959
 960         if (!xfs_alloc_cur_active(cur))
 961                 return 0;
 962
 963         /* locality optimized lookup */
 964         cur_len = acur->cur_len;
 965         error = xfs_alloc_lookup_ge(cur, args->agbno, cur_len, &i);
 966         if (error)
 967                 return error;
 968         if (i == 0)
 969                 return 0;
 970         error = xfs_alloc_get_rec(cur, &bno, &len, &i);
 971         if (error)
 972                 return error;
 973
 974         /* check the current record and update search length from it */
 975         error = xfs_alloc_cur_check(args, acur, cur, &i);
 976         if (error)
 977                 return error;
 978         ASSERT(len >= acur->cur_len);
 979         acur->cur_len = len;
 980
 981         /*
 982          * We looked up the first record >= [agbno, len] above. The agbno is a
 983          * secondary key and so the current record may lie just before or after
 984          * agbno. If it is past agbno, check the previous record too so long as
 985          * the length matches as it may be closer. Don't check a smaller record
 986          * because that could deactivate our cursor.
 987          */
 988         if (bno > args->agbno) {
 989                 error = xfs_btree_decrement(cur, 0, &i);
 990                 if (!error && i) {
 991                         error = xfs_alloc_get_rec(cur, &bno, &len, &i);
 992                         if (!error && i && len == acur->cur_len)
 993                                 error = xfs_alloc_cur_check(args, acur, cur,
 994                                                             &i);
 995                 }
 996                 if (error)
 997                         return error;
 998         }
 999
1000         /*
1001          * Increment the search key until we find at least one allocation
1002          * candidate or if the extent we found was larger. Otherwise, double the
1003          * search key to optimize the search. Efficiency is more important here
1004          * than absolute best locality.
1005          */
1006         cur_len <<= 1;
1007         if (!acur->len || acur->cur_len >= cur_len)
1008                 acur->cur_len++;
1009         else
1010                 acur->cur_len = cur_len;
1011
1012         return error;
1013 }
1014
1015 /*
1016  * Deal with the case where only small freespaces remain. Either return the
1017  * contents of the last freespace record, or allocate space from the freelist if
1018  * there is nothing in the tree.
1019  */
1020 STATIC int                      /* error */
1021 xfs_alloc_ag_vextent_small(
1022         struct xfs_alloc_arg    *args,  /* allocation argument structure */
1023         struct xfs_btree_cur    *ccur,  /* optional by-size cursor */
1024         xfs_agblock_t           *fbnop, /* result block number */
1025         xfs_extlen_t            *flenp, /* result length */
1026         int                     *stat)  /* status: 0-freelist, 1-normal/none */
1027 {
1028         struct xfs_agf          *agf = args->agbp->b_addr;
1029         int                     error = 0;
1030         xfs_agblock_t           fbno = NULLAGBLOCK;
1031         xfs_extlen_t            flen = 0;
1032         int                     i = 0;
1033
1034         /*
1035          * If a cntbt cursor is provided, try to allocate the largest record in
1036          * the tree. Try the AGFL if the cntbt is empty, otherwise fail the
1037          * allocation. Make sure to respect minleft even when pulling from the
1038          * freelist.
1039          */
1040         if (ccur)
1041                 error = xfs_btree_decrement(ccur, 0, &i);
1042         if (error)
1043                 goto error;
1044         if (i) {
1045                 error = xfs_alloc_get_rec(ccur, &fbno, &flen, &i);
1046                 if (error)
1047                         goto error;
1048                 if (XFS_IS_CORRUPT(args->mp, i != 1)) {
1049                         error = -EFSCORRUPTED;
1050                         goto error;
1051                 }
1052                 goto out;
1053         }
1054
1055         if (args->minlen != 1 || args->alignment != 1 ||
1056             args->resv == XFS_AG_RESV_AGFL ||
1057             be32_to_cpu(agf->agf_flcount) <= args->minleft)
1058                 goto out;
1059
1060         error = xfs_alloc_get_freelist(args->tp, args->agbp, &fbno, 0);
1061         if (error)
1062                 goto error;
1063         if (fbno == NULLAGBLOCK)
1064                 goto out;
1065
1066         xfs_extent_busy_reuse(args->mp, args->pag, fbno, 1,
1067                               (args->datatype & XFS_ALLOC_NOBUSY));
1068
1069         if (args->datatype & XFS_ALLOC_USERDATA) {
1070                 struct xfs_buf  *bp;
1071
1072                 error = xfs_trans_get_buf(args->tp, args->mp->m_ddev_targp,
1073                                 XFS_AGB_TO_DADDR(args->mp, args->agno, fbno),
1074                                 args->mp->m_bsize, 0, &bp);
1075                 if (error)
1076                         goto error;
1077                 xfs_trans_binval(args->tp, bp);
1078         }
1079         *fbnop = args->agbno = fbno;
1080         *flenp = args->len = 1;
1081         if (XFS_IS_CORRUPT(args->mp, fbno >= be32_to_cpu(agf->agf_length))) {
1082                 error = -EFSCORRUPTED;
1083                 goto error;
1084         }
1085         args->wasfromfl = 1;
1086         trace_xfs_alloc_small_freelist(args);
1087
1088         /*
1089          * If we're feeding an AGFL block to something that doesn't live in the
1090          * free space, we need to clear out the OWN_AG rmap.
1091          */
1092         error = xfs_rmap_free(args->tp, args->agbp, args->pag, fbno, 1,
1093                               &XFS_RMAP_OINFO_AG);
1094         if (error)
1095                 goto error;
1096
1097         *stat = 0;
1098         return 0;
1099
1100 out:
1101         /*
1102          * Can't do the allocation, give up.
1103          */
1104         if (flen < args->minlen) {
1105                 args->agbno = NULLAGBLOCK;
1106                 trace_xfs_alloc_small_notenough(args);
1107                 flen = 0;
1108         }
1109         *fbnop = fbno;
1110         *flenp = flen;
1111         *stat = 1;
1112         trace_xfs_alloc_small_done(args);
1113         return 0;
1114
1115 error:
1116         trace_xfs_alloc_small_error(args);
1117         return error;
1118 }
1119
1120 /*
1121  * Allocate a variable extent in the allocation group agno.
1122  * Type and bno are used to determine where in the allocation group the
1123  * extent will start.
1124  * Extent's length (returned in *len) will be between minlen and maxlen,
1125  * and of the form k * prod + mod unless there's nothing that large.
1126  * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
1127  */
1128 STATIC int                      /* error */
1129 xfs_alloc_ag_vextent(
1130         xfs_alloc_arg_t *args)  /* argument structure for allocation */
1131 {
1132         int             error=0;
1133
1134         ASSERT(args->minlen > 0);
1135         ASSERT(args->maxlen > 0);
1136         ASSERT(args->minlen <= args->maxlen);
1137         ASSERT(args->mod < args->prod);
1138         ASSERT(args->alignment > 0);
1139
1140         /*
1141          * Branch to correct routine based on the type.
1142          */
1143         args->wasfromfl = 0;
1144         switch (args->type) {
1145         case XFS_ALLOCTYPE_THIS_AG:
1146                 error = xfs_alloc_ag_vextent_size(args);
1147                 break;
1148         case XFS_ALLOCTYPE_NEAR_BNO:
1149                 error = xfs_alloc_ag_vextent_near(args);
1150                 break;
1151         case XFS_ALLOCTYPE_THIS_BNO:
1152                 error = xfs_alloc_ag_vextent_exact(args);
1153                 break;
1154         default:
1155                 ASSERT(0);
1156                 /* NOTREACHED */
1157         }
1158
1159         if (error || args->agbno == NULLAGBLOCK)
1160                 return error;
1161
1162         ASSERT(args->len >= args->minlen);
1163         ASSERT(args->len <= args->maxlen);
1164         ASSERT(!args->wasfromfl || args->resv != XFS_AG_RESV_AGFL);
1165         ASSERT(args->agbno % args->alignment == 0);
1166
1167         /* if not file data, insert new block into the reverse map btree */
1168         if (!xfs_rmap_should_skip_owner_update(&args->oinfo)) {
1169                 error = xfs_rmap_alloc(args->tp, args->agbp, args->pag,
1170                                        args->agbno, args->len, &args->oinfo);
1171                 if (error)
1172                         return error;
1173         }
1174
1175         if (!args->wasfromfl) {
1176                 error = xfs_alloc_update_counters(args->tp, args->agbp,
1177                                                   -((long)(args->len)));
1178                 if (error)
1179                         return error;
1180
1181                 ASSERT(!xfs_extent_busy_search(args->mp, args->pag,
1182                                               args->agbno, args->len));
1183         }
1184
1185         xfs_ag_resv_alloc_extent(args->pag, args->resv, args);
1186
1187         XFS_STATS_INC(args->mp, xs_allocx);
1188         XFS_STATS_ADD(args->mp, xs_allocb, args->len);
1189         return error;
1190 }
1191
1192 /*
1193  * Allocate a variable extent at exactly agno/bno.
1194  * Extent's length (returned in *len) will be between minlen and maxlen,
1195  * and of the form k * prod + mod unless there's nothing that large.
1196  * Return the starting a.g. block (bno), or NULLAGBLOCK if we can't do it.
1197  */
1198 STATIC int                      /* error */
1199 xfs_alloc_ag_vextent_exact(
1200         xfs_alloc_arg_t *args)  /* allocation argument structure */
1201 {
1202         struct xfs_agf __maybe_unused *agf = args->agbp->b_addr;
1203         xfs_btree_cur_t *bno_cur;/* by block-number btree cursor */
1204         xfs_btree_cur_t *cnt_cur;/* by count btree cursor */
1205         int             error;
1206         xfs_agblock_t   fbno;   /* start block of found extent */
1207         xfs_extlen_t    flen;   /* length of found extent */
1208         xfs_agblock_t   tbno;   /* start block of busy extent */
1209         xfs_extlen_t    tlen;   /* length of busy extent */
1210         xfs_agblock_t   tend;   /* end block of busy extent */
1211         int             i;      /* success/failure of operation */
1212         unsigned        busy_gen;
1213
1214         ASSERT(args->alignment == 1);
1215
1216         /*
1217          * Allocate/initialize a cursor for the by-number freespace btree.
1218          */
1219         bno_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
1220                                           args->pag, XFS_BTNUM_BNO);
1221
1222         /*
1223          * Lookup bno and minlen in the btree (minlen is irrelevant, really).
1224          * Look for the closest free block <= bno, it must contain bno
1225          * if any free block does.
1226          */
1227         error = xfs_alloc_lookup_le(bno_cur, args->agbno, args->minlen, &i);
1228         if (error)
1229                 goto error0;
1230         if (!i)
1231                 goto not_found;
1232
1233         /*
1234          * Grab the freespace record.
1235          */
1236         error = xfs_alloc_get_rec(bno_cur, &fbno, &flen, &i);
1237         if (error)
1238                 goto error0;
1239         if (XFS_IS_CORRUPT(args->mp, i != 1)) {
1240                 error = -EFSCORRUPTED;
1241                 goto error0;
1242         }
1243         ASSERT(fbno <= args->agbno);
1244
1245         /*
1246          * Check for overlapping busy extents.
1247          */
1248         tbno = fbno;
1249         tlen = flen;
1250         xfs_extent_busy_trim(args, &tbno, &tlen, &busy_gen);
1251
1252         /*
1253          * Give up if the start of the extent is busy, or the freespace isn't
1254          * long enough for the minimum request.
1255          */
1256         if (tbno > args->agbno)
1257                 goto not_found;
1258         if (tlen < args->minlen)
1259                 goto not_found;
1260         tend = tbno + tlen;
1261         if (tend < args->agbno + args->minlen)
1262                 goto not_found;
1263
1264         /*
1265          * End of extent will be smaller of the freespace end and the
1266          * maximal requested end.
1267          *
1268          * Fix the length according to mod and prod if given.
1269          */
1270         args->len = XFS_AGBLOCK_MIN(tend, args->agbno + args->maxlen)
1271                                                 - args->agbno;
1272         xfs_alloc_fix_len(args);
1273         ASSERT(args->agbno + args->len <= tend);
1274
1275         /*
1276          * We are allocating agbno for args->len
1277          * Allocate/initialize a cursor for the by-size btree.
1278          */
1279         cnt_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
1280                                         args->pag, XFS_BTNUM_CNT);
1281         ASSERT(args->agbno + args->len <= be32_to_cpu(agf->agf_length));
1282         error = xfs_alloc_fixup_trees(cnt_cur, bno_cur, fbno, flen, args->agbno,
1283                                       args->len, XFSA_FIXUP_BNO_OK);
1284         if (error) {
1285                 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
1286                 goto error0;
1287         }
1288
1289         xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
1290         xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1291
1292         args->wasfromfl = 0;
1293         trace_xfs_alloc_exact_done(args);
1294         return 0;
1295
1296 not_found:
1297         /* Didn't find it, return null. */
1298         xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
1299         args->agbno = NULLAGBLOCK;
1300         trace_xfs_alloc_exact_notfound(args);
1301         return 0;
1302
1303 error0:
1304         xfs_btree_del_cursor(bno_cur, XFS_BTREE_ERROR);
1305         trace_xfs_alloc_exact_error(args);
1306         return error;
1307 }
1308
1309 /*
1310  * Search a given number of btree records in a given direction. Check each
1311  * record against the good extent we've already found.
1312  */
1313 STATIC int
1314 xfs_alloc_walk_iter(
1315         struct xfs_alloc_arg    *args,
1316         struct xfs_alloc_cur    *acur,
1317         struct xfs_btree_cur    *cur,
1318         bool                    increment,
1319         bool                    find_one, /* quit on first candidate */
1320         int                     count,    /* rec count (-1 for infinite) */
1321         int                     *stat)
1322 {
1323         int                     error;
1324         int                     i;
1325
1326         *stat = 0;
1327
1328         /*
1329          * Search so long as the cursor is active or we find a better extent.
1330          * The cursor is deactivated if it extends beyond the range of the
1331          * current allocation candidate.
1332          */
1333         while (xfs_alloc_cur_active(cur) && count) {
1334                 error = xfs_alloc_cur_check(args, acur, cur, &i);
1335                 if (error)
1336                         return error;
1337                 if (i == 1) {
1338                         *stat = 1;
1339                         if (find_one)
1340                                 break;
1341                 }
1342                 if (!xfs_alloc_cur_active(cur))
1343                         break;
1344
1345                 if (increment)
1346                         error = xfs_btree_increment(cur, 0, &i);
1347                 else
1348                         error = xfs_btree_decrement(cur, 0, &i);
1349                 if (error)
1350                         return error;
1351                 if (i == 0)
1352                         cur->bc_ag.abt.active = false;
1353
1354                 if (count > 0)
1355                         count--;
1356         }
1357
1358         return 0;
1359 }
1360
1361 /*
1362  * Search the by-bno and by-size btrees in parallel in search of an extent with
1363  * ideal locality based on the NEAR mode ->agbno locality hint.
1364  */
1365 STATIC int
1366 xfs_alloc_ag_vextent_locality(
1367         struct xfs_alloc_arg    *args,
1368         struct xfs_alloc_cur    *acur,
1369         int                     *stat)
1370 {
1371         struct xfs_btree_cur    *fbcur = NULL;
1372         int                     error;
1373         int                     i;
1374         bool                    fbinc;
1375
1376         ASSERT(acur->len == 0);
1377         ASSERT(args->type == XFS_ALLOCTYPE_NEAR_BNO);
1378
1379         *stat = 0;
1380
1381         error = xfs_alloc_lookup_ge(acur->cnt, args->agbno, acur->cur_len, &i);
1382         if (error)
1383                 return error;
1384         error = xfs_alloc_lookup_le(acur->bnolt, args->agbno, 0, &i);
1385         if (error)
1386                 return error;
1387         error = xfs_alloc_lookup_ge(acur->bnogt, args->agbno, 0, &i);
1388         if (error)
1389                 return error;
1390
1391         /*
1392          * Search the bnobt and cntbt in parallel. Search the bnobt left and
1393          * right and lookup the closest extent to the locality hint for each
1394          * extent size key in the cntbt. The entire search terminates
1395          * immediately on a bnobt hit because that means we've found best case
1396          * locality. Otherwise the search continues until the cntbt cursor runs
1397          * off the end of the tree. If no allocation candidate is found at this
1398          * point, give up on locality, walk backwards from the end of the cntbt
1399          * and take the first available extent.
1400          *
1401          * The parallel tree searches balance each other out to provide fairly
1402          * consistent performance for various situations. The bnobt search can
1403          * have pathological behavior in the worst case scenario of larger
1404          * allocation requests and fragmented free space. On the other hand, the
1405          * bnobt is able to satisfy most smaller allocation requests much more
1406          * quickly than the cntbt. The cntbt search can sift through fragmented
1407          * free space and sets of free extents for larger allocation requests
1408          * more quickly than the bnobt. Since the locality hint is just a hint
1409          * and we don't want to scan the entire bnobt for perfect locality, the
1410          * cntbt search essentially bounds the bnobt search such that we can
1411          * find good enough locality at reasonable performance in most cases.
1412          */
1413         while (xfs_alloc_cur_active(acur->bnolt) ||
1414                xfs_alloc_cur_active(acur->bnogt) ||
1415                xfs_alloc_cur_active(acur->cnt)) {
1416
1417                 trace_xfs_alloc_cur_lookup(args);
1418
1419                 /*
1420                  * Search the bnobt left and right. In the case of a hit, finish
1421                  * the search in the opposite direction and we're done.
1422                  */
1423                 error = xfs_alloc_walk_iter(args, acur, acur->bnolt, false,
1424                                             true, 1, &i);
1425                 if (error)
1426                         return error;
1427                 if (i == 1) {
1428                         trace_xfs_alloc_cur_left(args);
1429                         fbcur = acur->bnogt;
1430                         fbinc = true;
1431                         break;
1432                 }
1433                 error = xfs_alloc_walk_iter(args, acur, acur->bnogt, true, true,
1434                                             1, &i);
1435                 if (error)
1436                         return error;
1437                 if (i == 1) {
1438                         trace_xfs_alloc_cur_right(args);
1439                         fbcur = acur->bnolt;
1440                         fbinc = false;
1441                         break;
1442                 }
1443
1444                 /*
1445                  * Check the extent with best locality based on the current
1446                  * extent size search key and keep track of the best candidate.
1447                  */
1448                 error = xfs_alloc_cntbt_iter(args, acur);
1449                 if (error)
1450                         return error;
1451                 if (!xfs_alloc_cur_active(acur->cnt)) {
1452                         trace_xfs_alloc_cur_lookup_done(args);
1453                         break;
1454                 }
1455         }
1456
1457         /*
1458          * If we failed to find anything due to busy extents, return empty
1459          * handed so the caller can flush and retry. If no busy extents were
1460          * found, walk backwards from the end of the cntbt as a last resort.
1461          */
1462         if (!xfs_alloc_cur_active(acur->cnt) && !acur->len && !acur->busy) {
1463                 error = xfs_btree_decrement(acur->cnt, 0, &i);
1464                 if (error)
1465                         return error;
1466                 if (i) {
1467                         acur->cnt->bc_ag.abt.active = true;
1468                         fbcur = acur->cnt;
1469                         fbinc = false;
1470                 }
1471         }
1472
1473         /*
1474          * Search in the opposite direction for a better entry in the case of
1475          * a bnobt hit or walk backwards from the end of the cntbt.
1476          */
1477         if (fbcur) {
1478                 error = xfs_alloc_walk_iter(args, acur, fbcur, fbinc, true, -1,
1479                                             &i);
1480                 if (error)
1481                         return error;
1482         }
1483
1484         if (acur->len)
1485                 *stat = 1;
1486
1487         return 0;
1488 }
1489
1490 /* Check the last block of the cnt btree for allocations. */
1491 static int
1492 xfs_alloc_ag_vextent_lastblock(
1493         struct xfs_alloc_arg    *args,
1494         struct xfs_alloc_cur    *acur,
1495         xfs_agblock_t           *bno,
1496         xfs_extlen_t            *len,
1497         bool                    *allocated)
1498 {
1499         int                     error;
1500         int                     i;
1501
1502 #ifdef DEBUG
1503         /* Randomly don't execute the first algorithm. */
1504         if (prandom_u32() & 1)
1505                 return 0;
1506 #endif
1507
1508         /*
1509          * Start from the entry that lookup found, sequence through all larger
1510          * free blocks.  If we're actually pointing at a record smaller than
1511          * maxlen, go to the start of this block, and skip all those smaller
1512          * than minlen.
1513          */
1514         if (*len || args->alignment > 1) {
1515                 acur->cnt->bc_ptrs[0] = 1;
1516                 do {
1517                         error = xfs_alloc_get_rec(acur->cnt, bno, len, &i);
1518                         if (error)
1519                                 return error;
1520                         if (XFS_IS_CORRUPT(args->mp, i != 1))
1521                                 return -EFSCORRUPTED;
1522                         if (*len >= args->minlen)
1523                                 break;
1524                         error = xfs_btree_increment(acur->cnt, 0, &i);
1525                         if (error)
1526                                 return error;
1527                 } while (i);
1528                 ASSERT(*len >= args->minlen);
1529                 if (!i)
1530                         return 0;
1531         }
1532
1533         error = xfs_alloc_walk_iter(args, acur, acur->cnt, true, false, -1, &i);
1534         if (error)
1535                 return error;
1536
1537         /*
1538          * It didn't work.  We COULD be in a case where there's a good record
1539          * somewhere, so try again.
1540          */
1541         if (acur->len == 0)
1542                 return 0;
1543
1544         trace_xfs_alloc_near_first(args);
1545         *allocated = true;
1546         return 0;
1547 }
1548
1549 /*
1550  * Allocate a variable extent near bno in the allocation group agno.
1551  * Extent's length (returned in len) will be between minlen and maxlen,
1552  * and of the form k * prod + mod unless there's nothing that large.
1553  * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
1554  */
1555 STATIC int
1556 xfs_alloc_ag_vextent_near(
1557         struct xfs_alloc_arg    *args)
1558 {
1559         struct xfs_alloc_cur    acur = {};
1560         int                     error;          /* error code */
1561         int                     i;              /* result code, temporary */
1562         xfs_agblock_t           bno;
1563         xfs_extlen_t            len;
1564
1565         /* handle uninitialized agbno range so caller doesn't have to */
1566         if (!args->min_agbno && !args->max_agbno)
1567                 args->max_agbno = args->mp->m_sb.sb_agblocks - 1;
1568         ASSERT(args->min_agbno <= args->max_agbno);
1569
1570         /* clamp agbno to the range if it's outside */
1571         if (args->agbno < args->min_agbno)
1572                 args->agbno = args->min_agbno;
1573         if (args->agbno > args->max_agbno)
1574                 args->agbno = args->max_agbno;
1575
1576 restart:
1577         len = 0;
1578
1579         /*
1580          * Set up cursors and see if there are any free extents as big as
1581          * maxlen. If not, pick the last entry in the tree unless the tree is
1582          * empty.
1583          */
1584         error = xfs_alloc_cur_setup(args, &acur);
1585         if (error == -ENOSPC) {
1586                 error = xfs_alloc_ag_vextent_small(args, acur.cnt, &bno,
1587                                 &len, &i);
1588                 if (error)
1589                         goto out;
1590                 if (i == 0 || len == 0) {
1591                         trace_xfs_alloc_near_noentry(args);
1592                         goto out;
1593                 }
1594                 ASSERT(i == 1);
1595         } else if (error) {
1596                 goto out;
1597         }
1598
1599         /*
1600          * First algorithm.
1601          * If the requested extent is large wrt the freespaces available
1602          * in this a.g., then the cursor will be pointing to a btree entry
1603          * near the right edge of the tree.  If it's in the last btree leaf
1604          * block, then we just examine all the entries in that block
1605          * that are big enough, and pick the best one.
1606          */
1607         if (xfs_btree_islastblock(acur.cnt, 0)) {
1608                 bool            allocated = false;
1609
1610                 error = xfs_alloc_ag_vextent_lastblock(args, &acur, &bno, &len,
1611                                 &allocated);
1612                 if (error)
1613                         goto out;
1614                 if (allocated)
1615                         goto alloc_finish;
1616         }
1617
1618         /*
1619          * Second algorithm. Combined cntbt and bnobt search to find ideal
1620          * locality.
1621          */
1622         error = xfs_alloc_ag_vextent_locality(args, &acur, &i);
1623         if (error)
1624                 goto out;
1625
1626         /*
1627          * If we couldn't get anything, give up.
1628          */
1629         if (!acur.len) {
1630                 if (acur.busy) {
1631                         trace_xfs_alloc_near_busy(args);
1632                         xfs_extent_busy_flush(args->mp, args->pag,
1633                                               acur.busy_gen);
1634                         goto restart;
1635                 }
1636                 trace_xfs_alloc_size_neither(args);
1637                 args->agbno = NULLAGBLOCK;
1638                 goto out;
1639         }
1640
1641 alloc_finish:
1642         /* fix up btrees on a successful allocation */
1643         error = xfs_alloc_cur_finish(args, &acur);
1644
1645 out:
1646         xfs_alloc_cur_close(&acur, error);
1647         return error;
1648 }
1649
1650 /*
1651  * Allocate a variable extent anywhere in the allocation group agno.
1652  * Extent's length (returned in len) will be between minlen and maxlen,
1653  * and of the form k * prod + mod unless there's nothing that large.
1654  * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
1655  */
1656 STATIC int                              /* error */
1657 xfs_alloc_ag_vextent_size(
1658         xfs_alloc_arg_t *args)          /* allocation argument structure */
1659 {
1660         struct xfs_agf  *agf = args->agbp->b_addr;
1661         xfs_btree_cur_t *bno_cur;       /* cursor for bno btree */
1662         xfs_btree_cur_t *cnt_cur;       /* cursor for cnt btree */
1663         int             error;          /* error result */
1664         xfs_agblock_t   fbno;           /* start of found freespace */
1665         xfs_extlen_t    flen;           /* length of found freespace */
1666         int             i;              /* temp status variable */
1667         xfs_agblock_t   rbno;           /* returned block number */
1668         xfs_extlen_t    rlen;           /* length of returned extent */
1669         bool            busy;
1670         unsigned        busy_gen;
1671
1672 restart:
1673         /*
1674          * Allocate and initialize a cursor for the by-size btree.
1675          */
1676         cnt_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
1677                                         args->pag, XFS_BTNUM_CNT);
1678         bno_cur = NULL;
1679
1680         /*
1681          * Look for an entry >= maxlen+alignment-1 blocks.
1682          */
1683         if ((error = xfs_alloc_lookup_ge(cnt_cur, 0,
1684                         args->maxlen + args->alignment - 1, &i)))
1685                 goto error0;
1686
1687         /*
1688          * If none then we have to settle for a smaller extent. In the case that
1689          * there are no large extents, this will return the last entry in the
1690          * tree unless the tree is empty. In the case that there are only busy
1691          * large extents, this will return the largest small extent unless there
1692          * are no smaller extents available.
1693          */
1694         if (!i) {
1695                 error = xfs_alloc_ag_vextent_small(args, cnt_cur,
1696                                                    &fbno, &flen, &i);
1697                 if (error)
1698                         goto error0;
1699                 if (i == 0 || flen == 0) {
1700                         xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1701                         trace_xfs_alloc_size_noentry(args);
1702                         return 0;
1703                 }
1704                 ASSERT(i == 1);
1705                 busy = xfs_alloc_compute_aligned(args, fbno, flen, &rbno,
1706                                 &rlen, &busy_gen);
1707         } else {
1708                 /*
1709                  * Search for a non-busy extent that is large enough.
1710                  */
1711                 for (;;) {
1712                         error = xfs_alloc_get_rec(cnt_cur, &fbno, &flen, &i);
1713                         if (error)
1714                                 goto error0;
1715                         if (XFS_IS_CORRUPT(args->mp, i != 1)) {
1716                                 error = -EFSCORRUPTED;
1717                                 goto error0;
1718                         }
1719
1720                         busy = xfs_alloc_compute_aligned(args, fbno, flen,
1721                                         &rbno, &rlen, &busy_gen);
1722
1723                         if (rlen >= args->maxlen)
1724                                 break;
1725
1726                         error = xfs_btree_increment(cnt_cur, 0, &i);
1727                         if (error)
1728                                 goto error0;
1729                         if (i == 0) {
1730                                 /*
1731                                  * Our only valid extents must have been busy.
1732                                  * Make it unbusy by forcing the log out and
1733                                  * retrying.
1734                                  */
1735                                 xfs_btree_del_cursor(cnt_cur,
1736                                                      XFS_BTREE_NOERROR);
1737                                 trace_xfs_alloc_size_busy(args);
1738                                 xfs_extent_busy_flush(args->mp,
1739                                                         args->pag, busy_gen);
1740                                 goto restart;
1741                         }
1742                 }
1743         }
1744
1745         /*
1746          * In the first case above, we got the last entry in the
1747          * by-size btree.  Now we check to see if the space hits maxlen
1748          * once aligned; if not, we search left for something better.
1749          * This can't happen in the second case above.
1750          */
1751         rlen = XFS_EXTLEN_MIN(args->maxlen, rlen);
1752         if (XFS_IS_CORRUPT(args->mp,
1753                            rlen != 0 &&
1754                            (rlen > flen ||
1755                             rbno + rlen > fbno + flen))) {
1756                 error = -EFSCORRUPTED;
1757                 goto error0;
1758         }
1759         if (rlen < args->maxlen) {
1760                 xfs_agblock_t   bestfbno;
1761                 xfs_extlen_t    bestflen;
1762                 xfs_agblock_t   bestrbno;
1763                 xfs_extlen_t    bestrlen;
1764
1765                 bestrlen = rlen;
1766                 bestrbno = rbno;
1767                 bestflen = flen;
1768                 bestfbno = fbno;
1769                 for (;;) {
1770                         if ((error = xfs_btree_decrement(cnt_cur, 0, &i)))
1771                                 goto error0;
1772                         if (i == 0)
1773                                 break;
1774                         if ((error = xfs_alloc_get_rec(cnt_cur, &fbno, &flen,
1775                                         &i)))
1776                                 goto error0;
1777                         if (XFS_IS_CORRUPT(args->mp, i != 1)) {
1778                                 error = -EFSCORRUPTED;
1779                                 goto error0;
1780                         }
1781                         if (flen < bestrlen)
1782                                 break;
1783                         busy = xfs_alloc_compute_aligned(args, fbno, flen,
1784                                         &rbno, &rlen, &busy_gen);
1785                         rlen = XFS_EXTLEN_MIN(args->maxlen, rlen);
1786                         if (XFS_IS_CORRUPT(args->mp,
1787                                            rlen != 0 &&
1788                                            (rlen > flen ||
1789                                             rbno + rlen > fbno + flen))) {
1790                                 error = -EFSCORRUPTED;
1791                                 goto error0;
1792                         }
1793                         if (rlen > bestrlen) {
1794                                 bestrlen = rlen;
1795                                 bestrbno = rbno;
1796                                 bestflen = flen;
1797                                 bestfbno = fbno;
1798                                 if (rlen == args->maxlen)
1799                                         break;
1800                         }
1801                 }
1802                 if ((error = xfs_alloc_lookup_eq(cnt_cur, bestfbno, bestflen,
1803                                 &i)))
1804                         goto error0;
1805                 if (XFS_IS_CORRUPT(args->mp, i != 1)) {
1806                         error = -EFSCORRUPTED;
1807                         goto error0;
1808                 }
1809                 rlen = bestrlen;
1810                 rbno = bestrbno;
1811                 flen = bestflen;
1812                 fbno = bestfbno;
1813         }
1814         args->wasfromfl = 0;
1815         /*
1816          * Fix up the length.
1817          */
1818         args->len = rlen;
1819         if (rlen < args->minlen) {
1820                 if (busy) {
1821                         xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1822                         trace_xfs_alloc_size_busy(args);
1823                         xfs_extent_busy_flush(args->mp, args->pag, busy_gen);
1824                         goto restart;
1825                 }
1826                 goto out_nominleft;
1827         }
1828         xfs_alloc_fix_len(args);
1829
1830         rlen = args->len;
1831         if (XFS_IS_CORRUPT(args->mp, rlen > flen)) {
1832                 error = -EFSCORRUPTED;
1833                 goto error0;
1834         }
1835         /*
1836          * Allocate and initialize a cursor for the by-block tree.
1837          */
1838         bno_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
1839                                         args->pag, XFS_BTNUM_BNO);
1840         if ((error = xfs_alloc_fixup_trees(cnt_cur, bno_cur, fbno, flen,
1841                         rbno, rlen, XFSA_FIXUP_CNT_OK)))
1842                 goto error0;
1843         xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1844         xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
1845         cnt_cur = bno_cur = NULL;
1846         args->len = rlen;
1847         args->agbno = rbno;
1848         if (XFS_IS_CORRUPT(args->mp,
1849                            args->agbno + args->len >
1850                            be32_to_cpu(agf->agf_length))) {
1851                 error = -EFSCORRUPTED;
1852                 goto error0;
1853         }
1854         trace_xfs_alloc_size_done(args);
1855         return 0;
1856
1857 error0:
1858         trace_xfs_alloc_size_error(args);
1859         if (cnt_cur)
1860                 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
1861         if (bno_cur)
1862                 xfs_btree_del_cursor(bno_cur, XFS_BTREE_ERROR);
1863         return error;
1864
1865 out_nominleft:
1866         xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1867         trace_xfs_alloc_size_nominleft(args);
1868         args->agbno = NULLAGBLOCK;
1869         return 0;
1870 }
1871
1872 /*
1873  * Free the extent starting at agno/bno for length.
1874  */
1875 STATIC int
1876 xfs_free_ag_extent(
1877         struct xfs_trans                *tp,
1878         struct xfs_buf                  *agbp,
1879         xfs_agnumber_t                  agno,
1880         xfs_agblock_t                   bno,
1881         xfs_extlen_t                    len,
1882         const struct xfs_owner_info     *oinfo,
1883         enum xfs_ag_resv_type           type)
1884 {
1885         struct xfs_mount                *mp;
1886         struct xfs_btree_cur            *bno_cur;
1887         struct xfs_btree_cur            *cnt_cur;
1888         xfs_agblock_t                   gtbno; /* start of right neighbor */
1889         xfs_extlen_t                    gtlen; /* length of right neighbor */
1890         xfs_agblock_t                   ltbno; /* start of left neighbor */
1891         xfs_extlen_t                    ltlen; /* length of left neighbor */
1892         xfs_agblock_t                   nbno; /* new starting block of freesp */
1893         xfs_extlen_t                    nlen; /* new length of freespace */
1894         int                             haveleft; /* have a left neighbor */
1895         int                             haveright; /* have a right neighbor */
1896         int                             i;
1897         int                             error;
1898         struct xfs_perag                *pag = agbp->b_pag;
1899
1900         bno_cur = cnt_cur = NULL;
1901         mp = tp->t_mountp;
1902
1903         if (!xfs_rmap_should_skip_owner_update(oinfo)) {
1904                 error = xfs_rmap_free(tp, agbp, pag, bno, len, oinfo);
1905                 if (error)
1906                         goto error0;
1907         }
1908
1909         /*
1910          * Allocate and initialize a cursor for the by-block btree.
1911          */
1912         bno_cur = xfs_allocbt_init_cursor(mp, tp, agbp, pag, XFS_BTNUM_BNO);
1913         /*
1914          * Look for a neighboring block on the left (lower block numbers)
1915          * that is contiguous with this space.
1916          */
1917         if ((error = xfs_alloc_lookup_le(bno_cur, bno, len, &haveleft)))
1918                 goto error0;
1919         if (haveleft) {
1920                 /*
1921                  * There is a block to our left.
1922                  */
1923                 if ((error = xfs_alloc_get_rec(bno_cur, &ltbno, &ltlen, &i)))
1924                         goto error0;
1925                 if (XFS_IS_CORRUPT(mp, i != 1)) {
1926                         error = -EFSCORRUPTED;
1927                         goto error0;
1928                 }
1929                 /*
1930                  * It's not contiguous, though.
1931                  */
1932                 if (ltbno + ltlen < bno)
1933                         haveleft = 0;
1934                 else {
1935                         /*
1936                          * If this failure happens the request to free this
1937                          * space was invalid, it's (partly) already free.
1938                          * Very bad.
1939                          */
1940                         if (XFS_IS_CORRUPT(mp, ltbno + ltlen > bno)) {
1941                                 error = -EFSCORRUPTED;
1942                                 goto error0;
1943                         }
1944                 }
1945         }
1946         /*
1947          * Look for a neighboring block on the right (higher block numbers)
1948          * that is contiguous with this space.
1949          */
1950         if ((error = xfs_btree_increment(bno_cur, 0, &haveright)))
1951                 goto error0;
1952         if (haveright) {
1953                 /*
1954                  * There is a block to our right.
1955                  */
1956                 if ((error = xfs_alloc_get_rec(bno_cur, &gtbno, &gtlen, &i)))
1957                         goto error0;
1958                 if (XFS_IS_CORRUPT(mp, i != 1)) {
1959                         error = -EFSCORRUPTED;
1960                         goto error0;
1961                 }
1962                 /*
1963                  * It's not contiguous, though.
1964                  */
1965                 if (bno + len < gtbno)
1966                         haveright = 0;
1967                 else {
1968                         /*
1969                          * If this failure happens the request to free this
1970                          * space was invalid, it's (partly) already free.
1971                          * Very bad.
1972                          */
1973                         if (XFS_IS_CORRUPT(mp, bno + len > gtbno)) {
1974                                 error = -EFSCORRUPTED;
1975                                 goto error0;
1976                         }
1977                 }
1978         }
1979         /*
1980          * Now allocate and initialize a cursor for the by-size tree.
1981          */
1982         cnt_cur = xfs_allocbt_init_cursor(mp, tp, agbp, pag, XFS_BTNUM_CNT);
1983         /*
1984          * Have both left and right contiguous neighbors.
1985          * Merge all three into a single free block.
1986          */
1987         if (haveleft && haveright) {
1988                 /*
1989                  * Delete the old by-size entry on the left.
1990                  */
1991                 if ((error = xfs_alloc_lookup_eq(cnt_cur, ltbno, ltlen, &i)))
1992                         goto error0;
1993                 if (XFS_IS_CORRUPT(mp, i != 1)) {
1994                         error = -EFSCORRUPTED;
1995                         goto error0;
1996                 }
1997                 if ((error = xfs_btree_delete(cnt_cur, &i)))
1998                         goto error0;
1999                 if (XFS_IS_CORRUPT(mp, i != 1)) {
2000                         error = -EFSCORRUPTED;
2001                         goto error0;
2002                 }
2003                 /*
2004                  * Delete the old by-size entry on the right.
2005                  */
2006                 if ((error = xfs_alloc_lookup_eq(cnt_cur, gtbno, gtlen, &i)))
2007                         goto error0;
2008                 if (XFS_IS_CORRUPT(mp, i != 1)) {
2009                         error = -EFSCORRUPTED;
2010                         goto error0;
2011                 }
2012                 if ((error = xfs_btree_delete(cnt_cur, &i)))
2013                         goto error0;
2014                 if (XFS_IS_CORRUPT(mp, i != 1)) {
2015                         error = -EFSCORRUPTED;
2016                         goto error0;
2017                 }
2018                 /*
2019                  * Delete the old by-block entry for the right block.
2020                  */
2021                 if ((error = xfs_btree_delete(bno_cur, &i)))
2022                         goto error0;
2023                 if (XFS_IS_CORRUPT(mp, i != 1)) {
2024                         error = -EFSCORRUPTED;
2025                         goto error0;
2026                 }
2027                 /*
2028                  * Move the by-block cursor back to the left neighbor.
2029                  */
2030                 if ((error = xfs_btree_decrement(bno_cur, 0, &i)))
2031                         goto error0;
2032                 if (XFS_IS_CORRUPT(mp, i != 1)) {
2033                         error = -EFSCORRUPTED;
2034                         goto error0;
2035                 }
2036 #ifdef DEBUG
2037                 /*
2038                  * Check that this is the right record: delete didn't
2039                  * mangle the cursor.
2040                  */
2041                 {
2042                         xfs_agblock_t   xxbno;
2043                         xfs_extlen_t    xxlen;
2044
2045                         if ((error = xfs_alloc_get_rec(bno_cur, &xxbno, &xxlen,
2046                                         &i)))
2047                                 goto error0;
2048                         if (XFS_IS_CORRUPT(mp,
2049                                            i != 1 ||
2050                                            xxbno != ltbno ||
2051                                            xxlen != ltlen)) {
2052                                 error = -EFSCORRUPTED;
2053                                 goto error0;
2054                         }
2055                 }
2056 #endif
2057                 /*
2058                  * Update remaining by-block entry to the new, joined block.
2059                  */
2060                 nbno = ltbno;
2061                 nlen = len + ltlen + gtlen;
2062                 if ((error = xfs_alloc_update(bno_cur, nbno, nlen)))
2063                         goto error0;
2064         }
2065         /*
2066          * Have only a left contiguous neighbor.
2067          * Merge it together with the new freespace.
2068          */
2069         else if (haveleft) {
2070                 /*
2071                  * Delete the old by-size entry on the left.
2072                  */
2073                 if ((error = xfs_alloc_lookup_eq(cnt_cur, ltbno, ltlen, &i)))
2074                         goto error0;
2075                 if (XFS_IS_CORRUPT(mp, i != 1)) {
2076                         error = -EFSCORRUPTED;
2077                         goto error0;
2078                 }
2079                 if ((error = xfs_btree_delete(cnt_cur, &i)))
2080                         goto error0;
2081                 if (XFS_IS_CORRUPT(mp, i != 1)) {
2082                         error = -EFSCORRUPTED;
2083                         goto error0;
2084                 }
2085                 /*
2086                  * Back up the by-block cursor to the left neighbor, and
2087                  * update its length.
2088                  */
2089                 if ((error = xfs_btree_decrement(bno_cur, 0, &i)))
2090                         goto error0;
2091                 if (XFS_IS_CORRUPT(mp, i != 1)) {
2092                         error = -EFSCORRUPTED;
2093                         goto error0;
2094                 }
2095                 nbno = ltbno;
2096                 nlen = len + ltlen;
2097                 if ((error = xfs_alloc_update(bno_cur, nbno, nlen)))
2098                         goto error0;
2099         }
2100         /*
2101          * Have only a right contiguous neighbor.
2102          * Merge it together with the new freespace.
2103          */
2104         else if (haveright) {
2105                 /*
2106                  * Delete the old by-size entry on the right.
2107                  */
2108                 if ((error = xfs_alloc_lookup_eq(cnt_cur, gtbno, gtlen, &i)))
2109                         goto error0;
2110                 if (XFS_IS_CORRUPT(mp, i != 1)) {
2111                         error = -EFSCORRUPTED;
2112                         goto error0;
2113                 }
2114                 if ((error = xfs_btree_delete(cnt_cur, &i)))
2115                         goto error0;
2116                 if (XFS_IS_CORRUPT(mp, i != 1)) {
2117                         error = -EFSCORRUPTED;
2118                         goto error0;
2119                 }
2120                 /*
2121                  * Update the starting block and length of the right
2122                  * neighbor in the by-block tree.
2123                  */
2124                 nbno = bno;
2125                 nlen = len + gtlen;
2126                 if ((error = xfs_alloc_update(bno_cur, nbno, nlen)))
2127                         goto error0;
2128         }
2129         /*
2130          * No contiguous neighbors.
2131          * Insert the new freespace into the by-block tree.
2132          */
2133         else {
2134                 nbno = bno;
2135                 nlen = len;
2136                 if ((error = xfs_btree_insert(bno_cur, &i)))
2137                         goto error0;
2138                 if (XFS_IS_CORRUPT(mp, i != 1)) {
2139                         error = -EFSCORRUPTED;
2140                         goto error0;
2141                 }
2142         }
2143         xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
2144         bno_cur = NULL;
2145         /*
2146          * In all cases we need to insert the new freespace in the by-size tree.
2147          */
2148         if ((error = xfs_alloc_lookup_eq(cnt_cur, nbno, nlen, &i)))
2149                 goto error0;
2150         if (XFS_IS_CORRUPT(mp, i != 0)) {
2151                 error = -EFSCORRUPTED;
2152                 goto error0;
2153         }
2154         if ((error = xfs_btree_insert(cnt_cur, &i)))
2155                 goto error0;
2156         if (XFS_IS_CORRUPT(mp, i != 1)) {
2157                 error = -EFSCORRUPTED;
2158                 goto error0;
2159         }
2160         xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
2161         cnt_cur = NULL;
2162
2163         /*
2164          * Update the freespace totals in the ag and superblock.
2165          */
2166         error = xfs_alloc_update_counters(tp, agbp, len);
2167         xfs_ag_resv_free_extent(agbp->b_pag, type, tp, len);
2168         if (error)
2169                 goto error0;
2170
2171         XFS_STATS_INC(mp, xs_freex);
2172         XFS_STATS_ADD(mp, xs_freeb, len);
2173
2174         trace_xfs_free_extent(mp, agno, bno, len, type, haveleft, haveright);
2175
2176         return 0;
2177
2178  error0:
2179         trace_xfs_free_extent(mp, agno, bno, len, type, -1, -1);
2180         if (bno_cur)
2181                 xfs_btree_del_cursor(bno_cur, XFS_BTREE_ERROR);
2182         if (cnt_cur)
2183                 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
2184         return error;
2185 }
2186
2187 /*
2188  * Visible (exported) allocation/free functions.
2189  * Some of these are used just by xfs_alloc_btree.c and this file.
2190  */
2191
2192 /*
2193  * Compute and fill in value of m_ag_maxlevels.
2194  */
2195 void
2196 xfs_alloc_compute_maxlevels(
2197         xfs_mount_t     *mp)    /* file system mount structure */
2198 {
2199         mp->m_ag_maxlevels = xfs_btree_compute_maxlevels(mp->m_alloc_mnr,
2200                         (mp->m_sb.sb_agblocks + 1) / 2);
2201 }
2202
2203 /*
2204  * Find the length of the longest extent in an AG.  The 'need' parameter
2205  * specifies how much space we're going to need for the AGFL and the
2206  * 'reserved' parameter tells us how many blocks in this AG are reserved for
2207  * other callers.
2208  */
2209 xfs_extlen_t
2210 xfs_alloc_longest_free_extent(
2211         struct xfs_perag        *pag,
2212         xfs_extlen_t            need,
2213         xfs_extlen_t            reserved)
2214 {
2215         xfs_extlen_t            delta = 0;
2216
2217         /*
2218          * If the AGFL needs a recharge, we'll have to subtract that from the
2219          * longest extent.
2220          */
2221         if (need > pag->pagf_flcount)
2222                 delta = need - pag->pagf_flcount;
2223
2224         /*
2225          * If we cannot maintain others' reservations with space from the
2226          * not-longest freesp extents, we'll have to subtract /that/ from
2227          * the longest extent too.
2228          */
2229         if (pag->pagf_freeblks - pag->pagf_longest < reserved)
2230                 delta += reserved - (pag->pagf_freeblks - pag->pagf_longest);
2231
2232         /*
2233          * If the longest extent is long enough to satisfy all the
2234          * reservations and AGFL rules in place, we can return this extent.
2235          */
2236         if (pag->pagf_longest > delta)
2237                 return min_t(xfs_extlen_t, pag->pag_mount->m_ag_max_usable,
2238                                 pag->pagf_longest - delta);
2239
2240         /* Otherwise, let the caller try for 1 block if there's space. */
2241         return pag->pagf_flcount > 0 || pag->pagf_longest > 0;
2242 }
2243
2244 /*
2245  * Compute the minimum length of the AGFL in the given AG.  If @pag is NULL,
2246  * return the largest possible minimum length.
2247  */
2248 unsigned int
2249 xfs_alloc_min_freelist(
2250         struct xfs_mount        *mp,
2251         struct xfs_perag        *pag)
2252 {
2253         /* AG btrees have at least 1 level. */
2254         static const uint8_t    fake_levels[XFS_BTNUM_AGF] = {1, 1, 1};
2255         const uint8_t           *levels = pag ? pag->pagf_levels : fake_levels;
2256         unsigned int            min_free;
2257
2258         ASSERT(mp->m_ag_maxlevels > 0);
2259
2260         /* space needed by-bno freespace btree */
2261         min_free = min_t(unsigned int, levels[XFS_BTNUM_BNOi] + 1,
2262                                        mp->m_ag_maxlevels);
2263         /* space needed by-size freespace btree */
2264         min_free += min_t(unsigned int, levels[XFS_BTNUM_CNTi] + 1,
2265                                        mp->m_ag_maxlevels);
2266         /* space needed reverse mapping used space btree */
2267         if (xfs_sb_version_hasrmapbt(&mp->m_sb))
2268                 min_free += min_t(unsigned int, levels[XFS_BTNUM_RMAPi] + 1,
2269                                                 mp->m_rmap_maxlevels);
2270
2271         return min_free;
2272 }
2273
2274 /*
2275  * Check if the operation we are fixing up the freelist for should go ahead or
2276  * not. If we are freeing blocks, we always allow it, otherwise the allocation
2277  * is dependent on whether the size and shape of free space available will
2278  * permit the requested allocation to take place.
2279  */
2280 static bool
2281 xfs_alloc_space_available(
2282         struct xfs_alloc_arg    *args,
2283         xfs_extlen_t            min_free,
2284         int                     flags)
2285 {
2286         struct xfs_perag        *pag = args->pag;
2287         xfs_extlen_t            alloc_len, longest;
2288         xfs_extlen_t            reservation; /* blocks that are still reserved */
2289         int                     available;
2290         xfs_extlen_t            agflcount;
2291
2292         if (flags & XFS_ALLOC_FLAG_FREEING)
2293                 return true;
2294
2295         reservation = xfs_ag_resv_needed(pag, args->resv);
2296
2297         /* do we have enough contiguous free space for the allocation? */
2298         alloc_len = args->minlen + (args->alignment - 1) + args->minalignslop;
2299         longest = xfs_alloc_longest_free_extent(pag, min_free, reservation);
2300         if (longest < alloc_len)
2301                 return false;
2302
2303         /*
2304          * Do we have enough free space remaining for the allocation? Don't
2305          * account extra agfl blocks because we are about to defer free them,
2306          * making them unavailable until the current transaction commits.
2307          */
2308         agflcount = min_t(xfs_extlen_t, pag->pagf_flcount, min_free);
2309         available = (int)(pag->pagf_freeblks + agflcount -
2310                           reservation - min_free - args->minleft);
2311         if (available < (int)max(args->total, alloc_len))
2312                 return false;
2313
2314         /*
2315          * Clamp maxlen to the amount of free space available for the actual
2316          * extent allocation.
2317          */
2318         if (available < (int)args->maxlen && !(flags & XFS_ALLOC_FLAG_CHECK)) {
2319                 args->maxlen = available;
2320                 ASSERT(args->maxlen > 0);
2321                 ASSERT(args->maxlen >= args->minlen);
2322         }
2323
2324         return true;
2325 }
2326
2327 int
2328 xfs_free_agfl_block(
2329         struct xfs_trans        *tp,
2330         xfs_agnumber_t          agno,
2331         xfs_agblock_t           agbno,
2332         struct xfs_buf          *agbp,
2333         struct xfs_owner_info   *oinfo)
2334 {
2335         int                     error;
2336         struct xfs_buf          *bp;
2337
2338         error = xfs_free_ag_extent(tp, agbp, agno, agbno, 1, oinfo,
2339                                    XFS_AG_RESV_AGFL);
2340         if (error)
2341                 return error;
2342
2343         error = xfs_trans_get_buf(tp, tp->t_mountp->m_ddev_targp,
2344                         XFS_AGB_TO_DADDR(tp->t_mountp, agno, agbno),
2345                         tp->t_mountp->m_bsize, 0, &bp);
2346         if (error)
2347                 return error;
2348         xfs_trans_binval(tp, bp);
2349
2350         return 0;
2351 }
2352
2353 /*
2354  * Check the agfl fields of the agf for inconsistency or corruption. The purpose
2355  * is to detect an agfl header padding mismatch between current and early v5
2356  * kernels. This problem manifests as a 1-slot size difference between the
2357  * on-disk flcount and the active [first, last] range of a wrapped agfl. This
2358  * may also catch variants of agfl count corruption unrelated to padding. Either
2359  * way, we'll reset the agfl and warn the user.
2360  *
2361  * Return true if a reset is required before the agfl can be used, false
2362  * otherwise.
2363  */
2364 static bool
2365 xfs_agfl_needs_reset(
2366         struct xfs_mount        *mp,
2367         struct xfs_agf          *agf)
2368 {
2369         uint32_t                f = be32_to_cpu(agf->agf_flfirst);
2370         uint32_t                l = be32_to_cpu(agf->agf_fllast);
2371         uint32_t                c = be32_to_cpu(agf->agf_flcount);
2372         int                     agfl_size = xfs_agfl_size(mp);
2373         int                     active;
2374
2375         /* no agfl header on v4 supers */
2376         if (!xfs_sb_version_hascrc(&mp->m_sb))
2377                 return false;
2378
2379         /*
2380          * The agf read verifier catches severe corruption of these fields.
2381          * Repeat some sanity checks to cover a packed -> unpacked mismatch if
2382          * the verifier allows it.
2383          */
2384         if (f >= agfl_size || l >= agfl_size)
2385                 return true;
2386         if (c > agfl_size)
2387                 return true;
2388
2389         /*
2390          * Check consistency between the on-disk count and the active range. An
2391          * agfl padding mismatch manifests as an inconsistent flcount.
2392          */
2393         if (c && l >= f)
2394                 active = l - f + 1;
2395         else if (c)
2396                 active = agfl_size - f + l + 1;
2397         else
2398                 active = 0;
2399
2400         return active != c;
2401 }
2402
2403 /*
2404  * Reset the agfl to an empty state. Ignore/drop any existing blocks since the
2405  * agfl content cannot be trusted. Warn the user that a repair is required to
2406  * recover leaked blocks.
2407  *
2408  * The purpose of this mechanism is to handle filesystems affected by the agfl
2409  * header padding mismatch problem. A reset keeps the filesystem online with a
2410  * relatively minor free space accounting inconsistency rather than suffer the
2411  * inevitable crash from use of an invalid agfl block.
2412  */
2413 static void
2414 xfs_agfl_reset(
2415         struct xfs_trans        *tp,
2416         struct xfs_buf          *agbp,
2417         struct xfs_perag        *pag)
2418 {
2419         struct xfs_mount        *mp = tp->t_mountp;
2420         struct xfs_agf          *agf = agbp->b_addr;
2421
2422         ASSERT(pag->pagf_agflreset);
2423         trace_xfs_agfl_reset(mp, agf, 0, _RET_IP_);
2424
2425         xfs_warn(mp,
2426                "WARNING: Reset corrupted AGFL on AG %u. %d blocks leaked. "
2427                "Please unmount and run xfs_repair.",
2428                  pag->pag_agno, pag->pagf_flcount);
2429
2430         agf->agf_flfirst = 0;
2431         agf->agf_fllast = cpu_to_be32(xfs_agfl_size(mp) - 1);
2432         agf->agf_flcount = 0;
2433         xfs_alloc_log_agf(tp, agbp, XFS_AGF_FLFIRST | XFS_AGF_FLLAST |
2434                                     XFS_AGF_FLCOUNT);
2435
2436         pag->pagf_flcount = 0;
2437         pag->pagf_agflreset = false;
2438 }
2439
2440 /*
2441  * Defer an AGFL block free. This is effectively equivalent to
2442  * xfs_bmap_add_free() with some special handling particular to AGFL blocks.
2443  *
2444  * Deferring AGFL frees helps prevent log reservation overruns due to too many
2445  * allocation operations in a transaction. AGFL frees are prone to this problem
2446  * because for one they are always freed one at a time. Further, an immediate
2447  * AGFL block free can cause a btree join and require another block free before
2448  * the real allocation can proceed. Deferring the free disconnects freeing up
2449  * the AGFL slot from freeing the block.
2450  */
2451 STATIC void
2452 xfs_defer_agfl_block(
2453         struct xfs_trans                *tp,
2454         xfs_agnumber_t                  agno,
2455         xfs_fsblock_t                   agbno,
2456         struct xfs_owner_info           *oinfo)
2457 {
2458         struct xfs_mount                *mp = tp->t_mountp;
2459         struct xfs_extent_free_item     *new;           /* new element */
2460
2461         ASSERT(xfs_bmap_free_item_zone != NULL);
2462         ASSERT(oinfo != NULL);
2463
2464         new = kmem_cache_alloc(xfs_bmap_free_item_zone,
2465                                GFP_KERNEL | __GFP_NOFAIL);
2466         new->xefi_startblock = XFS_AGB_TO_FSB(mp, agno, agbno);
2467         new->xefi_blockcount = 1;
2468         new->xefi_oinfo = *oinfo;
2469         new->xefi_skip_discard = false;
2470
2471         trace_xfs_agfl_free_defer(mp, agno, 0, agbno, 1);
2472
2473         xfs_defer_add(tp, XFS_DEFER_OPS_TYPE_AGFL_FREE, &new->xefi_list);
2474 }
2475
2476 #ifdef DEBUG
2477 /*
2478  * Check if an AGF has a free extent record whose length is equal to
2479  * args->minlen.
2480  */
2481 STATIC int
2482 xfs_exact_minlen_extent_available(
2483         struct xfs_alloc_arg    *args,
2484         struct xfs_buf          *agbp,
2485         int                     *stat)
2486 {
2487         struct xfs_btree_cur    *cnt_cur;
2488         xfs_agblock_t           fbno;
2489         xfs_extlen_t            flen;
2490         int                     error = 0;
2491
2492         cnt_cur = xfs_allocbt_init_cursor(args->mp, args->tp, agbp,
2493                                         args->pag, XFS_BTNUM_CNT);
2494         error = xfs_alloc_lookup_ge(cnt_cur, 0, args->minlen, stat);
2495         if (error)
2496                 goto out;
2497
2498         if (*stat == 0) {
2499                 error = -EFSCORRUPTED;
2500                 goto out;
2501         }
2502
2503         error = xfs_alloc_get_rec(cnt_cur, &fbno, &flen, stat);
2504         if (error)
2505                 goto out;
2506
2507         if (*stat == 1 && flen != args->minlen)
2508                 *stat = 0;
2509
2510 out:
2511         xfs_btree_del_cursor(cnt_cur, error);
2512
2513         return error;
2514 }
2515 #endif
2516
2517 /*
2518  * Decide whether to use this allocation group for this allocation.
2519  * If so, fix up the btree freelist's size.
2520  */
2521 int                     /* error */
2522 xfs_alloc_fix_freelist(
2523         struct xfs_alloc_arg    *args,  /* allocation argument structure */
2524         int                     flags)  /* XFS_ALLOC_FLAG_... */
2525 {
2526         struct xfs_mount        *mp = args->mp;
2527         struct xfs_perag        *pag = args->pag;
2528         struct xfs_trans        *tp = args->tp;
2529         struct xfs_buf          *agbp = NULL;
2530         struct xfs_buf          *agflbp = NULL;
2531         struct xfs_alloc_arg    targs;  /* local allocation arguments */
2532         xfs_agblock_t           bno;    /* freelist block */
2533         xfs_extlen_t            need;   /* total blocks needed in freelist */
2534         int                     error = 0;
2535
2536         /* deferred ops (AGFL block frees) require permanent transactions */
2537         ASSERT(tp->t_flags & XFS_TRANS_PERM_LOG_RES);
2538
2539         if (!pag->pagf_init) {
2540                 error = xfs_alloc_read_agf(mp, tp, args->agno, flags, &agbp);
2541                 if (error) {
2542                         /* Couldn't lock the AGF so skip this AG. */
2543                         if (error == -EAGAIN)
2544                                 error = 0;
2545                         goto out_no_agbp;
2546                 }
2547         }
2548
2549         /*
2550          * If this is a metadata preferred pag and we are user data then try
2551          * somewhere else if we are not being asked to try harder at this
2552          * point
2553          */
2554         if (pag->pagf_metadata && (args->datatype & XFS_ALLOC_USERDATA) &&
2555             (flags & XFS_ALLOC_FLAG_TRYLOCK)) {
2556                 ASSERT(!(flags & XFS_ALLOC_FLAG_FREEING));
2557                 goto out_agbp_relse;
2558         }
2559
2560         need = xfs_alloc_min_freelist(mp, pag);
2561         if (!xfs_alloc_space_available(args, need, flags |
2562                         XFS_ALLOC_FLAG_CHECK))
2563                 goto out_agbp_relse;
2564
2565         /*
2566          * Get the a.g. freespace buffer.
2567          * Can fail if we're not blocking on locks, and it's held.
2568          */
2569         if (!agbp) {
2570                 error = xfs_alloc_read_agf(mp, tp, args->agno, flags, &agbp);
2571                 if (error) {
2572                         /* Couldn't lock the AGF so skip this AG. */
2573                         if (error == -EAGAIN)
2574                                 error = 0;
2575                         goto out_no_agbp;
2576                 }
2577         }
2578
2579         /* reset a padding mismatched agfl before final free space check */
2580         if (pag->pagf_agflreset)
2581                 xfs_agfl_reset(tp, agbp, pag);
2582
2583         /* If there isn't enough total space or single-extent, reject it. */
2584         need = xfs_alloc_min_freelist(mp, pag);
2585         if (!xfs_alloc_space_available(args, need, flags))
2586                 goto out_agbp_relse;
2587
2588 #ifdef DEBUG
2589         if (args->alloc_minlen_only) {
2590                 int stat;
2591
2592                 error = xfs_exact_minlen_extent_available(args, agbp, &stat);
2593                 if (error || !stat)
2594                         goto out_agbp_relse;
2595         }
2596 #endif
2597         /*
2598          * Make the freelist shorter if it's too long.
2599          *
2600          * Note that from this point onwards, we will always release the agf and
2601          * agfl buffers on error. This handles the case where we error out and
2602          * the buffers are clean or may not have been joined to the transaction
2603          * and hence need to be released manually. If they have been joined to
2604          * the transaction, then xfs_trans_brelse() will handle them
2605          * appropriately based on the recursion count and dirty state of the
2606          * buffer.
2607          *
2608          * XXX (dgc): When we have lots of free space, does this buy us
2609          * anything other than extra overhead when we need to put more blocks
2610          * back on the free list? Maybe we should only do this when space is
2611          * getting low or the AGFL is more than half full?
2612          *
2613          * The NOSHRINK flag prevents the AGFL from being shrunk if it's too
2614          * big; the NORMAP flag prevents AGFL expand/shrink operations from
2615          * updating the rmapbt.  Both flags are used in xfs_repair while we're
2616          * rebuilding the rmapbt, and neither are used by the kernel.  They're
2617          * both required to ensure that rmaps are correctly recorded for the
2618          * regenerated AGFL, bnobt, and cntbt.  See repair/phase5.c and
2619          * repair/rmap.c in xfsprogs for details.
2620          */
2621         memset(&targs, 0, sizeof(targs));
2622         /* struct copy below */
2623         if (flags & XFS_ALLOC_FLAG_NORMAP)
2624                 targs.oinfo = XFS_RMAP_OINFO_SKIP_UPDATE;
2625         else
2626                 targs.oinfo = XFS_RMAP_OINFO_AG;
2627         while (!(flags & XFS_ALLOC_FLAG_NOSHRINK) && pag->pagf_flcount > need) {
2628                 error = xfs_alloc_get_freelist(tp, agbp, &bno, 0);
2629                 if (error)
2630                         goto out_agbp_relse;
2631
2632                 /* defer agfl frees */
2633                 xfs_defer_agfl_block(tp, args->agno, bno, &targs.oinfo);
2634         }
2635
2636         targs.tp = tp;
2637         targs.mp = mp;
2638         targs.agbp = agbp;
2639         targs.agno = args->agno;
2640         targs.alignment = targs.minlen = targs.prod = 1;
2641         targs.type = XFS_ALLOCTYPE_THIS_AG;
2642         targs.pag = pag;
2643         error = xfs_alloc_read_agfl(mp, tp, targs.agno, &agflbp);
2644         if (error)
2645                 goto out_agbp_relse;
2646
2647         /* Make the freelist longer if it's too short. */
2648         while (pag->pagf_flcount < need) {
2649                 targs.agbno = 0;
2650                 targs.maxlen = need - pag->pagf_flcount;
2651                 targs.resv = XFS_AG_RESV_AGFL;
2652
2653                 /* Allocate as many blocks as possible at once. */
2654                 error = xfs_alloc_ag_vextent(&targs);
2655                 if (error)
2656                         goto out_agflbp_relse;
2657
2658                 /*
2659                  * Stop if we run out.  Won't happen if callers are obeying
2660                  * the restrictions correctly.  Can happen for free calls
2661                  * on a completely full ag.
2662                  */
2663                 if (targs.agbno == NULLAGBLOCK) {
2664                         if (flags & XFS_ALLOC_FLAG_FREEING)
2665                                 break;
2666                         goto out_agflbp_relse;
2667                 }
2668                 /*
2669                  * Put each allocated block on the list.
2670                  */
2671                 for (bno = targs.agbno; bno < targs.agbno + targs.len; bno++) {
2672                         error = xfs_alloc_put_freelist(tp, agbp,
2673                                                         agflbp, bno, 0);
2674                         if (error)
2675                                 goto out_agflbp_relse;
2676                 }
2677         }
2678         xfs_trans_brelse(tp, agflbp);
2679         args->agbp = agbp;
2680         return 0;
2681
2682 out_agflbp_relse:
2683         xfs_trans_brelse(tp, agflbp);
2684 out_agbp_relse:
2685         if (agbp)
2686                 xfs_trans_brelse(tp, agbp);
2687 out_no_agbp:
2688         args->agbp = NULL;
2689         return error;
2690 }
2691
2692 /*
2693  * Get a block from the freelist.
2694  * Returns with the buffer for the block gotten.
2695  */
2696 int
2697 xfs_alloc_get_freelist(
2698         struct xfs_trans        *tp,
2699         struct xfs_buf          *agbp,
2700         xfs_agblock_t           *bnop,
2701         int                     btreeblk)
2702 {
2703         struct xfs_agf          *agf = agbp->b_addr;
2704         struct xfs_buf          *agflbp;
2705         xfs_agblock_t           bno;
2706         __be32                  *agfl_bno;
2707         int                     error;
2708         int                     logflags;
2709         struct xfs_mount        *mp = tp->t_mountp;
2710         struct xfs_perag        *pag;
2711
2712         /*
2713          * Freelist is empty, give up.
2714          */
2715         if (!agf->agf_flcount) {
2716                 *bnop = NULLAGBLOCK;
2717                 return 0;
2718         }
2719         /*
2720          * Read the array of free blocks.
2721          */
2722         error = xfs_alloc_read_agfl(mp, tp, be32_to_cpu(agf->agf_seqno),
2723                                     &agflbp);
2724         if (error)
2725                 return error;
2726
2727
2728         /*
2729          * Get the block number and update the data structures.
2730          */
2731         agfl_bno = xfs_buf_to_agfl_bno(agflbp);
2732         bno = be32_to_cpu(agfl_bno[be32_to_cpu(agf->agf_flfirst)]);
2733         be32_add_cpu(&agf->agf_flfirst, 1);
2734         xfs_trans_brelse(tp, agflbp);
2735         if (be32_to_cpu(agf->agf_flfirst) == xfs_agfl_size(mp))
2736                 agf->agf_flfirst = 0;
2737
2738         pag = agbp->b_pag;
2739         ASSERT(!pag->pagf_agflreset);
2740         be32_add_cpu(&agf->agf_flcount, -1);
2741         pag->pagf_flcount--;
2742
2743         logflags = XFS_AGF_FLFIRST | XFS_AGF_FLCOUNT;
2744         if (btreeblk) {
2745                 be32_add_cpu(&agf->agf_btreeblks, 1);
2746                 pag->pagf_btreeblks++;
2747                 logflags |= XFS_AGF_BTREEBLKS;
2748         }
2749
2750         xfs_alloc_log_agf(tp, agbp, logflags);
2751         *bnop = bno;
2752
2753         return 0;
2754 }
2755
2756 /*
2757  * Log the given fields from the agf structure.
2758  */
2759 void
2760 xfs_alloc_log_agf(
2761         xfs_trans_t     *tp,    /* transaction pointer */
2762         struct xfs_buf  *bp,    /* buffer for a.g. freelist header */
2763         int             fields) /* mask of fields to be logged (XFS_AGF_...) */
2764 {
2765         int     first;          /* first byte offset */
2766         int     last;           /* last byte offset */
2767         static const short      offsets[] = {
2768                 offsetof(xfs_agf_t, agf_magicnum),
2769                 offsetof(xfs_agf_t, agf_versionnum),
2770                 offsetof(xfs_agf_t, agf_seqno),
2771                 offsetof(xfs_agf_t, agf_length),
2772                 offsetof(xfs_agf_t, agf_roots[0]),
2773                 offsetof(xfs_agf_t, agf_levels[0]),
2774                 offsetof(xfs_agf_t, agf_flfirst),
2775                 offsetof(xfs_agf_t, agf_fllast),
2776                 offsetof(xfs_agf_t, agf_flcount),
2777                 offsetof(xfs_agf_t, agf_freeblks),
2778                 offsetof(xfs_agf_t, agf_longest),
2779                 offsetof(xfs_agf_t, agf_btreeblks),
2780                 offsetof(xfs_agf_t, agf_uuid),
2781                 offsetof(xfs_agf_t, agf_rmap_blocks),
2782                 offsetof(xfs_agf_t, agf_refcount_blocks),
2783                 offsetof(xfs_agf_t, agf_refcount_root),
2784                 offsetof(xfs_agf_t, agf_refcount_level),
2785                 /* needed so that we don't log the whole rest of the structure: */
2786                 offsetof(xfs_agf_t, agf_spare64),
2787                 sizeof(xfs_agf_t)
2788         };
2789
2790         trace_xfs_agf(tp->t_mountp, bp->b_addr, fields, _RET_IP_);
2791
2792         xfs_trans_buf_set_type(tp, bp, XFS_BLFT_AGF_BUF);
2793
2794         xfs_btree_offsets(fields, offsets, XFS_AGF_NUM_BITS, &first, &last);
2795         xfs_trans_log_buf(tp, bp, (uint)first, (uint)last);
2796 }
2797
2798 /*
2799  * Interface for inode allocation to force the pag data to be initialized.
2800  */
2801 int                                     /* error */
2802 xfs_alloc_pagf_init(
2803         xfs_mount_t             *mp,    /* file system mount structure */
2804         xfs_trans_t             *tp,    /* transaction pointer */
2805         xfs_agnumber_t          agno,   /* allocation group number */
2806         int                     flags)  /* XFS_ALLOC_FLAGS_... */
2807 {
2808         struct xfs_buf          *bp;
2809         int                     error;
2810
2811         error = xfs_alloc_read_agf(mp, tp, agno, flags, &bp);
2812         if (!error)
2813                 xfs_trans_brelse(tp, bp);
2814         return error;
2815 }
2816
2817 /*
2818  * Put the block on the freelist for the allocation group.
2819  */
2820 int
2821 xfs_alloc_put_freelist(
2822         struct xfs_trans        *tp,
2823         struct xfs_buf          *agbp,
2824         struct xfs_buf          *agflbp,
2825         xfs_agblock_t           bno,
2826         int                     btreeblk)
2827 {
2828         struct xfs_mount        *mp = tp->t_mountp;
2829         struct xfs_agf          *agf = agbp->b_addr;
2830         struct xfs_perag        *pag;
2831         __be32                  *blockp;
2832         int                     error;
2833         int                     logflags;
2834         __be32                  *agfl_bno;
2835         int                     startoff;
2836
2837         if (!agflbp && (error = xfs_alloc_read_agfl(mp, tp,
2838                         be32_to_cpu(agf->agf_seqno), &agflbp)))
2839                 return error;
2840         be32_add_cpu(&agf->agf_fllast, 1);
2841         if (be32_to_cpu(agf->agf_fllast) == xfs_agfl_size(mp))
2842                 agf->agf_fllast = 0;
2843
2844         pag = agbp->b_pag;
2845         ASSERT(!pag->pagf_agflreset);
2846         be32_add_cpu(&agf->agf_flcount, 1);
2847         pag->pagf_flcount++;
2848
2849         logflags = XFS_AGF_FLLAST | XFS_AGF_FLCOUNT;
2850         if (btreeblk) {
2851                 be32_add_cpu(&agf->agf_btreeblks, -1);
2852                 pag->pagf_btreeblks--;
2853                 logflags |= XFS_AGF_BTREEBLKS;
2854         }
2855
2856         xfs_alloc_log_agf(tp, agbp, logflags);
2857
2858         ASSERT(be32_to_cpu(agf->agf_flcount) <= xfs_agfl_size(mp));
2859
2860         agfl_bno = xfs_buf_to_agfl_bno(agflbp);
2861         blockp = &agfl_bno[be32_to_cpu(agf->agf_fllast)];
2862         *blockp = cpu_to_be32(bno);
2863         startoff = (char *)blockp - (char *)agflbp->b_addr;
2864
2865         xfs_alloc_log_agf(tp, agbp, logflags);
2866
2867         xfs_trans_buf_set_type(tp, agflbp, XFS_BLFT_AGFL_BUF);
2868         xfs_trans_log_buf(tp, agflbp, startoff,
2869                           startoff + sizeof(xfs_agblock_t) - 1);
2870         return 0;
2871 }
2872
2873 static xfs_failaddr_t
2874 xfs_agf_verify(
2875         struct xfs_buf          *bp)
2876 {
2877         struct xfs_mount        *mp = bp->b_mount;
2878         struct xfs_agf          *agf = bp->b_addr;
2879
2880         if (xfs_sb_version_hascrc(&mp->m_sb)) {
2881                 if (!uuid_equal(&agf->agf_uuid, &mp->m_sb.sb_meta_uuid))
2882                         return __this_address;
2883                 if (!xfs_log_check_lsn(mp, be64_to_cpu(agf->agf_lsn)))
2884                         return __this_address;
2885         }
2886
2887         if (!xfs_verify_magic(bp, agf->agf_magicnum))
2888                 return __this_address;
2889
2890         if (!(XFS_AGF_GOOD_VERSION(be32_to_cpu(agf->agf_versionnum)) &&
2891               be32_to_cpu(agf->agf_freeblks) <= be32_to_cpu(agf->agf_length) &&
2892               be32_to_cpu(agf->agf_flfirst) < xfs_agfl_size(mp) &&
2893               be32_to_cpu(agf->agf_fllast) < xfs_agfl_size(mp) &&
2894               be32_to_cpu(agf->agf_flcount) <= xfs_agfl_size(mp)))
2895                 return __this_address;
2896
2897         if (be32_to_cpu(agf->agf_length) > mp->m_sb.sb_dblocks)
2898                 return __this_address;
2899
2900         if (be32_to_cpu(agf->agf_freeblks) < be32_to_cpu(agf->agf_longest) ||
2901             be32_to_cpu(agf->agf_freeblks) > be32_to_cpu(agf->agf_length))
2902                 return __this_address;
2903
2904         if (be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNO]) < 1 ||
2905             be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNT]) < 1 ||
2906             be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNO]) > mp->m_ag_maxlevels ||
2907             be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNT]) > mp->m_ag_maxlevels)
2908                 return __this_address;
2909
2910         if (xfs_sb_version_hasrmapbt(&mp->m_sb) &&
2911             (be32_to_cpu(agf->agf_levels[XFS_BTNUM_RMAP]) < 1 ||
2912              be32_to_cpu(agf->agf_levels[XFS_BTNUM_RMAP]) > mp->m_rmap_maxlevels))
2913                 return __this_address;
2914
2915         if (xfs_sb_version_hasrmapbt(&mp->m_sb) &&
2916             be32_to_cpu(agf->agf_rmap_blocks) > be32_to_cpu(agf->agf_length))
2917                 return __this_address;
2918
2919         /*
2920          * during growfs operations, the perag is not fully initialised,
2921          * so we can't use it for any useful checking. growfs ensures we can't
2922          * use it by using uncached buffers that don't have the perag attached
2923          * so we can detect and avoid this problem.
2924          */
2925         if (bp->b_pag && be32_to_cpu(agf->agf_seqno) != bp->b_pag->pag_agno)
2926                 return __this_address;
2927
2928         if (xfs_sb_version_haslazysbcount(&mp->m_sb) &&
2929             be32_to_cpu(agf->agf_btreeblks) > be32_to_cpu(agf->agf_length))
2930                 return __this_address;
2931
2932         if (xfs_sb_version_hasreflink(&mp->m_sb) &&
2933             be32_to_cpu(agf->agf_refcount_blocks) >
2934             be32_to_cpu(agf->agf_length))
2935                 return __this_address;
2936
2937         if (xfs_sb_version_hasreflink(&mp->m_sb) &&
2938             (be32_to_cpu(agf->agf_refcount_level) < 1 ||
2939              be32_to_cpu(agf->agf_refcount_level) > mp->m_refc_maxlevels))
2940                 return __this_address;
2941
2942         return NULL;
2943
2944 }
2945
2946 static void
2947 xfs_agf_read_verify(
2948         struct xfs_buf  *bp)
2949 {
2950         struct xfs_mount *mp = bp->b_mount;
2951         xfs_failaddr_t  fa;
2952
2953         if (xfs_sb_version_hascrc(&mp->m_sb) &&
2954             !xfs_buf_verify_cksum(bp, XFS_AGF_CRC_OFF))
2955                 xfs_verifier_error(bp, -EFSBADCRC, __this_address);
2956         else {
2957                 fa = xfs_agf_verify(bp);
2958                 if (XFS_TEST_ERROR(fa, mp, XFS_ERRTAG_ALLOC_READ_AGF))
2959                         xfs_verifier_error(bp, -EFSCORRUPTED, fa);
2960         }
2961 }
2962
2963 static void
2964 xfs_agf_write_verify(
2965         struct xfs_buf  *bp)
2966 {
2967         struct xfs_mount        *mp = bp->b_mount;
2968         struct xfs_buf_log_item *bip = bp->b_log_item;
2969         struct xfs_agf          *agf = bp->b_addr;
2970         xfs_failaddr_t          fa;
2971
2972         fa = xfs_agf_verify(bp);
2973         if (fa) {
2974                 xfs_verifier_error(bp, -EFSCORRUPTED, fa);
2975                 return;
2976         }
2977
2978         if (!xfs_sb_version_hascrc(&mp->m_sb))
2979                 return;
2980
2981         if (bip)
2982                 agf->agf_lsn = cpu_to_be64(bip->bli_item.li_lsn);
2983
2984         xfs_buf_update_cksum(bp, XFS_AGF_CRC_OFF);
2985 }
2986
2987 const struct xfs_buf_ops xfs_agf_buf_ops = {
2988         .name = "xfs_agf",
2989         .magic = { cpu_to_be32(XFS_AGF_MAGIC), cpu_to_be32(XFS_AGF_MAGIC) },
2990         .verify_read = xfs_agf_read_verify,
2991         .verify_write = xfs_agf_write_verify,
2992         .verify_struct = xfs_agf_verify,
2993 };
2994
2995 /*
2996  * Read in the allocation group header (free/alloc section).
2997  */
2998 int                                     /* error */
2999 xfs_read_agf(
3000         struct xfs_mount        *mp,    /* mount point structure */
3001         struct xfs_trans        *tp,    /* transaction pointer */
3002         xfs_agnumber_t          agno,   /* allocation group number */
3003         int                     flags,  /* XFS_BUF_ */
3004         struct xfs_buf          **bpp)  /* buffer for the ag freelist header */
3005 {
3006         int             error;
3007
3008         trace_xfs_read_agf(mp, agno);
3009
3010         ASSERT(agno != NULLAGNUMBER);
3011         error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp,
3012                         XFS_AG_DADDR(mp, agno, XFS_AGF_DADDR(mp)),
3013                         XFS_FSS_TO_BB(mp, 1), flags, bpp, &xfs_agf_buf_ops);
3014         if (error)
3015                 return error;
3016
3017         ASSERT(!(*bpp)->b_error);
3018         xfs_buf_set_ref(*bpp, XFS_AGF_REF);
3019         return 0;
3020 }
3021
3022 /*
3023  * Read in the allocation group header (free/alloc section).
3024  */
3025 int                                     /* error */
3026 xfs_alloc_read_agf(
3027         struct xfs_mount        *mp,    /* mount point structure */
3028         struct xfs_trans        *tp,    /* transaction pointer */
3029         xfs_agnumber_t          agno,   /* allocation group number */
3030         int                     flags,  /* XFS_ALLOC_FLAG_... */
3031         struct xfs_buf          **bpp)  /* buffer for the ag freelist header */
3032 {
3033         struct xfs_agf          *agf;           /* ag freelist header */
3034         struct xfs_perag        *pag;           /* per allocation group data */
3035         int                     error;
3036         int                     allocbt_blks;
3037
3038         trace_xfs_alloc_read_agf(mp, agno);
3039
3040         /* We don't support trylock when freeing. */
3041         ASSERT((flags & (XFS_ALLOC_FLAG_FREEING | XFS_ALLOC_FLAG_TRYLOCK)) !=
3042                         (XFS_ALLOC_FLAG_FREEING | XFS_ALLOC_FLAG_TRYLOCK));
3043         ASSERT(agno != NULLAGNUMBER);
3044         error = xfs_read_agf(mp, tp, agno,
3045                         (flags & XFS_ALLOC_FLAG_TRYLOCK) ? XBF_TRYLOCK : 0,
3046                         bpp);
3047         if (error)
3048                 return error;
3049         ASSERT(!(*bpp)->b_error);
3050
3051         agf = (*bpp)->b_addr;
3052         pag = (*bpp)->b_pag;
3053         if (!pag->pagf_init) {
3054                 pag->pagf_freeblks = be32_to_cpu(agf->agf_freeblks);
3055                 pag->pagf_btreeblks = be32_to_cpu(agf->agf_btreeblks);
3056                 pag->pagf_flcount = be32_to_cpu(agf->agf_flcount);
3057                 pag->pagf_longest = be32_to_cpu(agf->agf_longest);
3058                 pag->pagf_levels[XFS_BTNUM_BNOi] =
3059                         be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNOi]);
3060                 pag->pagf_levels[XFS_BTNUM_CNTi] =
3061                         be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNTi]);
3062                 pag->pagf_levels[XFS_BTNUM_RMAPi] =
3063                         be32_to_cpu(agf->agf_levels[XFS_BTNUM_RMAPi]);
3064                 pag->pagf_refcount_level = be32_to_cpu(agf->agf_refcount_level);
3065                 pag->pagf_init = 1;
3066                 pag->pagf_agflreset = xfs_agfl_needs_reset(mp, agf);
3067
3068                 /*
3069                  * Update the in-core allocbt counter. Filter out the rmapbt
3070                  * subset of the btreeblks counter because the rmapbt is managed
3071                  * by perag reservation. Subtract one for the rmapbt root block
3072                  * because the rmap counter includes it while the btreeblks
3073                  * counter only tracks non-root blocks.
3074                  */
3075                 allocbt_blks = pag->pagf_btreeblks;
3076                 if (xfs_sb_version_hasrmapbt(&mp->m_sb))
3077                         allocbt_blks -= be32_to_cpu(agf->agf_rmap_blocks) - 1;
3078                 if (allocbt_blks > 0)
3079                         atomic64_add(allocbt_blks, &mp->m_allocbt_blks);
3080         }
3081 #ifdef DEBUG
3082         else if (!XFS_FORCED_SHUTDOWN(mp)) {
3083                 ASSERT(pag->pagf_freeblks == be32_to_cpu(agf->agf_freeblks));
3084                 ASSERT(pag->pagf_btreeblks == be32_to_cpu(agf->agf_btreeblks));
3085                 ASSERT(pag->pagf_flcount == be32_to_cpu(agf->agf_flcount));
3086                 ASSERT(pag->pagf_longest == be32_to_cpu(agf->agf_longest));
3087                 ASSERT(pag->pagf_levels[XFS_BTNUM_BNOi] ==
3088                        be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNOi]));
3089                 ASSERT(pag->pagf_levels[XFS_BTNUM_CNTi] ==
3090                        be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNTi]));
3091         }
3092 #endif
3093         return 0;
3094 }
3095
3096 /*
3097  * Allocate an extent (variable-size).
3098  * Depending on the allocation type, we either look in a single allocation
3099  * group or loop over the allocation groups to find the result.
3100  */
3101 int                             /* error */
3102 xfs_alloc_vextent(
3103         struct xfs_alloc_arg    *args)  /* allocation argument structure */
3104 {
3105         xfs_agblock_t           agsize; /* allocation group size */
3106         int                     error;
3107         int                     flags;  /* XFS_ALLOC_FLAG_... locking flags */
3108         struct xfs_mount        *mp;    /* mount structure pointer */
3109         xfs_agnumber_t          sagno;  /* starting allocation group number */
3110         xfs_alloctype_t         type;   /* input allocation type */
3111         int                     bump_rotor = 0;
3112         xfs_agnumber_t          rotorstep = xfs_rotorstep; /* inode32 agf stepper */
3113
3114         mp = args->mp;
3115         type = args->otype = args->type;
3116         args->agbno = NULLAGBLOCK;
3117         /*
3118          * Just fix this up, for the case where the last a.g. is shorter
3119          * (or there's only one a.g.) and the caller couldn't easily figure
3120          * that out (xfs_bmap_alloc).
3121          */
3122         agsize = mp->m_sb.sb_agblocks;
3123         if (args->maxlen > agsize)
3124                 args->maxlen = agsize;
3125         if (args->alignment == 0)
3126                 args->alignment = 1;
3127         ASSERT(XFS_FSB_TO_AGNO(mp, args->fsbno) < mp->m_sb.sb_agcount);
3128         ASSERT(XFS_FSB_TO_AGBNO(mp, args->fsbno) < agsize);
3129         ASSERT(args->minlen <= args->maxlen);
3130         ASSERT(args->minlen <= agsize);
3131         ASSERT(args->mod < args->prod);
3132         if (XFS_FSB_TO_AGNO(mp, args->fsbno) >= mp->m_sb.sb_agcount ||
3133             XFS_FSB_TO_AGBNO(mp, args->fsbno) >= agsize ||
3134             args->minlen > args->maxlen || args->minlen > agsize ||
3135             args->mod >= args->prod) {
3136                 args->fsbno = NULLFSBLOCK;
3137                 trace_xfs_alloc_vextent_badargs(args);
3138                 return 0;
3139         }
3140
3141         switch (type) {
3142         case XFS_ALLOCTYPE_THIS_AG:
3143         case XFS_ALLOCTYPE_NEAR_BNO:
3144         case XFS_ALLOCTYPE_THIS_BNO:
3145                 /*
3146                  * These three force us into a single a.g.
3147                  */
3148                 args->agno = XFS_FSB_TO_AGNO(mp, args->fsbno);
3149                 args->pag = xfs_perag_get(mp, args->agno);
3150                 error = xfs_alloc_fix_freelist(args, 0);
3151                 if (error) {
3152                         trace_xfs_alloc_vextent_nofix(args);
3153                         goto error0;
3154                 }
3155                 if (!args->agbp) {
3156                         trace_xfs_alloc_vextent_noagbp(args);
3157                         break;
3158                 }
3159                 args->agbno = XFS_FSB_TO_AGBNO(mp, args->fsbno);
3160                 if ((error = xfs_alloc_ag_vextent(args)))
3161                         goto error0;
3162                 break;
3163         case XFS_ALLOCTYPE_START_BNO:
3164                 /*
3165                  * Try near allocation first, then anywhere-in-ag after
3166                  * the first a.g. fails.
3167                  */
3168                 if ((args->datatype & XFS_ALLOC_INITIAL_USER_DATA) &&
3169                     (mp->m_flags & XFS_MOUNT_32BITINODES)) {
3170                         args->fsbno = XFS_AGB_TO_FSB(mp,
3171                                         ((mp->m_agfrotor / rotorstep) %
3172                                         mp->m_sb.sb_agcount), 0);
3173                         bump_rotor = 1;
3174                 }
3175                 args->agbno = XFS_FSB_TO_AGBNO(mp, args->fsbno);
3176                 args->type = XFS_ALLOCTYPE_NEAR_BNO;
3177                 fallthrough;
3178         case XFS_ALLOCTYPE_FIRST_AG:
3179                 /*
3180                  * Rotate through the allocation groups looking for a winner.
3181                  */
3182                 if (type == XFS_ALLOCTYPE_FIRST_AG) {
3183                         /*
3184                          * Start with allocation group given by bno.
3185                          */
3186                         args->agno = XFS_FSB_TO_AGNO(mp, args->fsbno);
3187                         args->type = XFS_ALLOCTYPE_THIS_AG;
3188                         sagno = 0;
3189                         flags = 0;
3190                 } else {
3191                         /*
3192                          * Start with the given allocation group.
3193                          */
3194                         args->agno = sagno = XFS_FSB_TO_AGNO(mp, args->fsbno);
3195                         flags = XFS_ALLOC_FLAG_TRYLOCK;
3196                 }
3197                 /*
3198                  * Loop over allocation groups twice; first time with
3199                  * trylock set, second time without.
3200                  */
3201                 for (;;) {
3202                         args->pag = xfs_perag_get(mp, args->agno);
3203                         error = xfs_alloc_fix_freelist(args, flags);
3204                         if (error) {
3205                                 trace_xfs_alloc_vextent_nofix(args);
3206                                 goto error0;
3207                         }
3208                         /*
3209                          * If we get a buffer back then the allocation will fly.
3210                          */
3211                         if (args->agbp) {
3212                                 if ((error = xfs_alloc_ag_vextent(args)))
3213                                         goto error0;
3214                                 break;
3215                         }
3216
3217                         trace_xfs_alloc_vextent_loopfailed(args);
3218
3219                         /*
3220                          * Didn't work, figure out the next iteration.
3221                          */
3222                         if (args->agno == sagno &&
3223                             type == XFS_ALLOCTYPE_START_BNO)
3224                                 args->type = XFS_ALLOCTYPE_THIS_AG;
3225                         /*
3226                         * For the first allocation, we can try any AG to get
3227                         * space.  However, if we already have allocated a
3228                         * block, we don't want to try AGs whose number is below
3229                         * sagno. Otherwise, we may end up with out-of-order
3230                         * locking of AGF, which might cause deadlock.
3231                         */
3232                         if (++(args->agno) == mp->m_sb.sb_agcount) {
3233                                 if (args->tp->t_firstblock != NULLFSBLOCK)
3234                                         args->agno = sagno;
3235                                 else
3236                                         args->agno = 0;
3237                         }
3238                         /*
3239                          * Reached the starting a.g., must either be done
3240                          * or switch to non-trylock mode.
3241                          */
3242                         if (args->agno == sagno) {
3243                                 if (flags == 0) {
3244                                         args->agbno = NULLAGBLOCK;
3245                                         trace_xfs_alloc_vextent_allfailed(args);
3246                                         break;
3247                                 }
3248
3249                                 flags = 0;
3250                                 if (type == XFS_ALLOCTYPE_START_BNO) {
3251                                         args->agbno = XFS_FSB_TO_AGBNO(mp,
3252                                                 args->fsbno);
3253                                         args->type = XFS_ALLOCTYPE_NEAR_BNO;
3254                                 }
3255                         }
3256                         xfs_perag_put(args->pag);
3257                 }
3258                 if (bump_rotor) {
3259                         if (args->agno == sagno)
3260                                 mp->m_agfrotor = (mp->m_agfrotor + 1) %
3261                                         (mp->m_sb.sb_agcount * rotorstep);
3262                         else
3263                                 mp->m_agfrotor = (args->agno * rotorstep + 1) %
3264                                         (mp->m_sb.sb_agcount * rotorstep);
3265                 }
3266                 break;
3267         default:
3268                 ASSERT(0);
3269                 /* NOTREACHED */
3270         }
3271         if (args->agbno == NULLAGBLOCK)
3272                 args->fsbno = NULLFSBLOCK;
3273         else {
3274                 args->fsbno = XFS_AGB_TO_FSB(mp, args->agno, args->agbno);
3275 #ifdef DEBUG
3276                 ASSERT(args->len >= args->minlen);
3277                 ASSERT(args->len <= args->maxlen);
3278                 ASSERT(args->agbno % args->alignment == 0);
3279                 XFS_AG_CHECK_DADDR(mp, XFS_FSB_TO_DADDR(mp, args->fsbno),
3280                         args->len);
3281 #endif
3282
3283         }
3284         xfs_perag_put(args->pag);
3285         return 0;
3286 error0:
3287         xfs_perag_put(args->pag);
3288         return error;
3289 }
3290
3291 /* Ensure that the freelist is at full capacity. */
3292 int
3293 xfs_free_extent_fix_freelist(
3294         struct xfs_trans        *tp,
3295         struct xfs_perag        *pag,
3296         struct xfs_buf          **agbp)
3297 {
3298         struct xfs_alloc_arg    args;
3299         int                     error;
3300
3301         memset(&args, 0, sizeof(struct xfs_alloc_arg));
3302         args.tp = tp;
3303         args.mp = tp->t_mountp;
3304         args.agno = pag->pag_agno;
3305         args.pag = pag;
3306
3307         /*
3308          * validate that the block number is legal - the enables us to detect
3309          * and handle a silent filesystem corruption rather than crashing.
3310          */
3311         if (args.agno >= args.mp->m_sb.sb_agcount)
3312                 return -EFSCORRUPTED;
3313
3314         error = xfs_alloc_fix_freelist(&args, XFS_ALLOC_FLAG_FREEING);
3315         if (error)
3316                 return error;
3317
3318         *agbp = args.agbp;
3319         return 0;
3320 }
3321
3322 /*
3323  * Free an extent.
3324  * Just break up the extent address and hand off to xfs_free_ag_extent
3325  * after fixing up the freelist.
3326  */
3327 int
3328 __xfs_free_extent(
3329         struct xfs_trans                *tp,
3330         xfs_fsblock_t                   bno,
3331         xfs_extlen_t                    len,
3332         const struct xfs_owner_info     *oinfo,
3333         enum xfs_ag_resv_type           type,
3334         bool                            skip_discard)
3335 {
3336         struct xfs_mount                *mp = tp->t_mountp;
3337         struct xfs_buf                  *agbp;
3338         xfs_agnumber_t                  agno = XFS_FSB_TO_AGNO(mp, bno);
3339         xfs_agblock_t                   agbno = XFS_FSB_TO_AGBNO(mp, bno);
3340         struct xfs_agf                  *agf;
3341         int                             error;
3342         unsigned int                    busy_flags = 0;
3343         struct xfs_perag                *pag;
3344
3345         ASSERT(len != 0);
3346         ASSERT(type != XFS_AG_RESV_AGFL);
3347
3348         if (XFS_TEST_ERROR(false, mp,
3349                         XFS_ERRTAG_FREE_EXTENT))
3350                 return -EIO;
3351
3352         pag = xfs_perag_get(mp, agno);
3353         error = xfs_free_extent_fix_freelist(tp, pag, &agbp);
3354         if (error)
3355                 goto err;
3356         agf = agbp->b_addr;
3357
3358         if (XFS_IS_CORRUPT(mp, agbno >= mp->m_sb.sb_agblocks)) {
3359                 error = -EFSCORRUPTED;
3360                 goto err_release;
3361         }
3362
3363         /* validate the extent size is legal now we have the agf locked */
3364         if (XFS_IS_CORRUPT(mp, agbno + len > be32_to_cpu(agf->agf_length))) {
3365                 error = -EFSCORRUPTED;
3366                 goto err_release;
3367         }
3368
3369         error = xfs_free_ag_extent(tp, agbp, agno, agbno, len, oinfo, type);
3370         if (error)
3371                 goto err_release;
3372
3373         if (skip_discard)
3374                 busy_flags |= XFS_EXTENT_BUSY_SKIP_DISCARD;
3375         xfs_extent_busy_insert(tp, pag, agbno, len, busy_flags);
3376         xfs_perag_put(pag);
3377         return 0;
3378
3379 err_release:
3380         xfs_trans_brelse(tp, agbp);
3381 err:
3382         xfs_perag_put(pag);
3383         return error;
3384 }
3385
3386 struct xfs_alloc_query_range_info {
3387         xfs_alloc_query_range_fn        fn;
3388         void                            *priv;
3389 };
3390
3391 /* Format btree record and pass to our callback. */
3392 STATIC int
3393 xfs_alloc_query_range_helper(
3394         struct xfs_btree_cur            *cur,
3395         union xfs_btree_rec             *rec,
3396         void                            *priv)
3397 {
3398         struct xfs_alloc_query_range_info       *query = priv;
3399         struct xfs_alloc_rec_incore             irec;
3400
3401         irec.ar_startblock = be32_to_cpu(rec->alloc.ar_startblock);
3402         irec.ar_blockcount = be32_to_cpu(rec->alloc.ar_blockcount);
3403         return query->fn(cur, &irec, query->priv);
3404 }
3405
3406 /* Find all free space within a given range of blocks. */
3407 int
3408 xfs_alloc_query_range(
3409         struct xfs_btree_cur                    *cur,
3410         struct xfs_alloc_rec_incore             *low_rec,
3411         struct xfs_alloc_rec_incore             *high_rec,
3412         xfs_alloc_query_range_fn                fn,
3413         void                                    *priv)
3414 {
3415         union xfs_btree_irec                    low_brec;
3416         union xfs_btree_irec                    high_brec;
3417         struct xfs_alloc_query_range_info       query;
3418
3419         ASSERT(cur->bc_btnum == XFS_BTNUM_BNO);
3420         low_brec.a = *low_rec;
3421         high_brec.a = *high_rec;
3422         query.priv = priv;
3423         query.fn = fn;
3424         return xfs_btree_query_range(cur, &low_brec, &high_brec,
3425                         xfs_alloc_query_range_helper, &query);
3426 }
3427
3428 /* Find all free space records. */
3429 int
3430 xfs_alloc_query_all(
3431         struct xfs_btree_cur                    *cur,
3432         xfs_alloc_query_range_fn                fn,
3433         void                                    *priv)
3434 {
3435         struct xfs_alloc_query_range_info       query;
3436
3437         ASSERT(cur->bc_btnum == XFS_BTNUM_BNO);
3438         query.priv = priv;
3439         query.fn = fn;
3440         return xfs_btree_query_all(cur, xfs_alloc_query_range_helper, &query);
3441 }
3442
3443 /* Is there a record covering a given extent? */
3444 int
3445 xfs_alloc_has_record(
3446         struct xfs_btree_cur    *cur,
3447         xfs_agblock_t           bno,
3448         xfs_extlen_t            len,
3449         bool                    *exists)
3450 {
3451         union xfs_btree_irec    low;
3452         union xfs_btree_irec    high;
3453
3454         memset(&low, 0, sizeof(low));
3455         low.a.ar_startblock = bno;
3456         memset(&high, 0xFF, sizeof(high));
3457         high.a.ar_startblock = bno + len - 1;
3458
3459         return xfs_btree_has_record(cur, &low, &high, exists);
3460 }
3461
3462 /*
3463  * Walk all the blocks in the AGFL.  The @walk_fn can return any negative
3464  * error code or XFS_ITER_*.
3465  */
3466 int
3467 xfs_agfl_walk(
3468         struct xfs_mount        *mp,
3469         struct xfs_agf          *agf,
3470         struct xfs_buf          *agflbp,
3471         xfs_agfl_walk_fn        walk_fn,
3472         void                    *priv)
3473 {
3474         __be32                  *agfl_bno;
3475         unsigned int            i;
3476         int                     error;
3477
3478         agfl_bno = xfs_buf_to_agfl_bno(agflbp);
3479         i = be32_to_cpu(agf->agf_flfirst);
3480
3481         /* Nothing to walk in an empty AGFL. */
3482         if (agf->agf_flcount == cpu_to_be32(0))
3483                 return 0;
3484
3485         /* Otherwise, walk from first to last, wrapping as needed. */
3486         for (;;) {
3487                 error = walk_fn(mp, be32_to_cpu(agfl_bno[i]), priv);
3488                 if (error)
3489                         return error;
3490                 if (i == be32_to_cpu(agf->agf_fllast))
3491                         break;
3492                 if (++i == xfs_agfl_size(mp))
3493                         i = 0;
3494         }
3495
3496         return 0;
3497 }