linux/fs/xfs/libxfs/xfs_alloc.c
<<
>>
Prefs
   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
  30extern kmem_zone_t      *xfs_bmap_free_item_zone;
  31
  32struct 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
  39STATIC int xfs_alloc_ag_vextent_exact(xfs_alloc_arg_t *);
  40STATIC int xfs_alloc_ag_vextent_near(xfs_alloc_arg_t *);
  41STATIC 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 */
  48unsigned int
  49xfs_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
  60unsigned int
  61xfs_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
  71xfs_extlen_t
  72xfs_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 */
  99unsigned int
 100xfs_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 */
 120unsigned int
 121xfs_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 */
 142STATIC int                              /* error */
 143xfs_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 */
 162int                             /* error */
 163xfs_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 */
 182int                                     /* error */
 183xfs_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
 197static inline bool
 198xfs_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 */
 209STATIC int                              /* error */
 210xfs_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 */
 225int                                     /* error */
 226xfs_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
 257out_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 */
 270STATIC bool
 271xfs_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 */
 318STATIC xfs_extlen_t                     /* difference value (absolute) */
 319xfs_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 */
 389STATIC void
 390xfs_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 */
 427STATIC int                              /* error code */
 428xfs_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
 586static xfs_failaddr_t
 587xfs_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
 628static void
 629xfs_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
 653static void
 654xfs_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
 677const 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 */
 688int                                     /* error */
 689xfs_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
 710STATIC int
 711xfs_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 */
 734struct 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 */
 753static int
 754xfs_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
 796static void
 797xfs_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 */
 821static int
 822xfs_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;
 907out:
 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 */
 919STATIC int
 920xfs_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 */
 949STATIC int
 950xfs_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 */
1020STATIC int                      /* error */
1021xfs_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
1100out:
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
1115error:
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 */
1128STATIC int                      /* error */
1129xfs_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 */
1198STATIC int                      /* error */
1199xfs_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
1296not_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
1303error0:
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 */
1313STATIC int
1314xfs_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 */
1365STATIC int
1366xfs_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. */
1491static int
1492xfs_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 */
1555STATIC int
1556xfs_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
1576restart:
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
1641alloc_finish:
1642        /* fix up btrees on a successful allocation */
1643        error = xfs_alloc_cur_finish(args, &acur);
1644
1645out:
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 */
1656STATIC int                              /* error */
1657xfs_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
1672restart:
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
1857error0:
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
1865out_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 */
1875STATIC int
1876xfs_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 */
2195void
2196xfs_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 */
2209xfs_extlen_t
2210xfs_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 */
2248unsigned int
2249xfs_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 */
2280static bool
2281xfs_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
2327int
2328xfs_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 */
2364static bool
2365xfs_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 */
2413static void
2414xfs_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 */
2451STATIC void
2452xfs_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 */
2481STATIC int
2482xfs_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
2510out:
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 */
2521int                     /* error */
2522xfs_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
2682out_agflbp_relse:
2683        xfs_trans_brelse(tp, agflbp);
2684out_agbp_relse:
2685        if (agbp)
2686                xfs_trans_brelse(tp, agbp);
2687out_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 */
2696int
2697xfs_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 */
2759void
2760xfs_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 */
2801int                                     /* error */
2802xfs_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 */
2820int
2821xfs_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
2873static xfs_failaddr_t
2874xfs_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
2946static void
2947xfs_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
2963static void
2964xfs_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
2987const 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 */
2998int                                     /* error */
2999xfs_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 */
3025int                                     /* error */
3026xfs_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 */
3101int                             /* error */
3102xfs_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;
3286error0:
3287        xfs_perag_put(args->pag);
3288        return error;
3289}
3290
3291/* Ensure that the freelist is at full capacity. */
3292int
3293xfs_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 */
3327int
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
3379err_release:
3380        xfs_trans_brelse(tp, agbp);
3381err:
3382        xfs_perag_put(pag);
3383        return error;
3384}
3385
3386struct 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. */
3392STATIC int
3393xfs_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. */
3407int
3408xfs_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. */
3429int
3430xfs_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? */
3444int
3445xfs_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 */
3466int
3467xfs_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}
3498
lxr.linux.no kindly hosted by Redpill Linpro AS, provider of Linux consulting and operations services since 1995.