1 // SPDX-License-Identifier: GPL-2.0
3 * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc.
8 #include "xfs_format.h"
9 #include "xfs_log_format.h"
10 #include "xfs_shared.h"
11 #include "xfs_trans_resv.h"
13 #include "xfs_mount.h"
14 #include "xfs_defer.h"
15 #include "xfs_btree.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"
27 #include "xfs_ag_resv.h"
30 extern kmem_zone_t *xfs_bmap_free_item_zone;
32 struct workqueue_struct *xfs_alloc_wq;
34 #define XFS_ABSDIFF(a,b) (((a) <= (b)) ? ((b) - (a)) : ((a) - (b)))
36 #define XFSA_FIXUP_BNO_OK 1
37 #define XFSA_FIXUP_CNT_OK 2
39 STATIC int xfs_alloc_ag_vextent_exact(xfs_alloc_arg_t *);
40 STATIC int xfs_alloc_ag_vextent_near(xfs_alloc_arg_t *);
41 STATIC int xfs_alloc_ag_vextent_size(xfs_alloc_arg_t *);
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
52 unsigned int size = mp->m_sb.sb_sectsize;
54 if (xfs_sb_version_hascrc(&mp->m_sb))
55 size -= sizeof(struct xfs_agfl);
57 return size / sizeof(xfs_agblock_t);
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;
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;
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.
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.
101 struct xfs_mount *mp)
103 return mp->m_sb.sb_agcount * (XFS_ALLOC_AGFL_RESERVE + 4);
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
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.
121 xfs_alloc_ag_max_usable(
122 struct xfs_mount *mp)
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 */
136 return mp->m_sb.sb_agblocks - blocks;
140 * Lookup the record equal to [bno, len] in the btree given by cur.
142 STATIC int /* error */
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 */
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);
159 * Lookup the first record greater than or equal to [bno, len]
160 * in the btree given by cur.
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 */
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);
179 * Lookup the first record less than or equal to [bno, len]
180 * in the btree given by cur.
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 */
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);
198 xfs_alloc_cur_active(
199 struct xfs_btree_cur *cur)
201 return cur && cur->bc_ag.abt.active;
205 * Update the record referred to by cur to the value given
207 * This either works (return 0) or gets an EFSCORRUPTED error.
209 STATIC int /* error */
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 */
215 union xfs_btree_rec rec;
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);
223 * Get the data from the pointed-to record.
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 */
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;
237 error = xfs_btree_get_rec(cur, &rec, stat);
238 if (error || !(*stat))
241 *bno = be32_to_cpu(rec->alloc.ar_startblock);
242 *len = be32_to_cpu(rec->alloc.ar_blockcount);
247 /* check for valid extent range, including overflow */
248 if (!xfs_verify_agbno(mp, agno, *bno))
250 if (*bno > *bno + *len)
252 if (!xfs_verify_agbno(mp, agno, *bno + *len - 1))
259 "%s Freespace BTree record corruption in AG %d detected!",
260 cur->bc_btnum == XFS_BTNUM_BNO ? "Block" : "Size", agno);
262 "start block 0x%x block count 0x%x", *bno, *len);
263 return -EFSCORRUPTED;
267 * Compute aligned version of the found extent.
268 * Takes alignment and min length into account.
271 xfs_alloc_compute_aligned(
272 xfs_alloc_arg_t *args, /* allocation argument structure */
273 xfs_agblock_t foundbno, /* starting block in found extent */
274 xfs_extlen_t foundlen, /* length in found extent */
275 xfs_agblock_t *resbno, /* result block number */
276 xfs_extlen_t *reslen, /* result length */
279 xfs_agblock_t bno = foundbno;
280 xfs_extlen_t len = foundlen;
284 /* Trim busy sections out of found extent */
285 busy = xfs_extent_busy_trim(args, &bno, &len, busy_gen);
288 * If we have a largish extent that happens to start before min_agbno,
289 * see if we can shift it into range...
291 if (bno < args->min_agbno && bno + len > args->min_agbno) {
292 diff = args->min_agbno - bno;
299 if (args->alignment > 1 && len >= args->minlen) {
300 xfs_agblock_t aligned_bno = roundup(bno, args->alignment);
302 diff = aligned_bno - bno;
304 *resbno = aligned_bno;
305 *reslen = diff >= len ? 0 : len - diff;
315 * Compute best start block and diff for "near" allocations.
316 * freelen >= wantlen already checked by caller.
318 STATIC xfs_extlen_t /* difference value (absolute) */
319 xfs_alloc_compute_diff(
320 xfs_agblock_t wantbno, /* target starting block */
321 xfs_extlen_t wantlen, /* target length */
322 xfs_extlen_t alignment, /* target alignment */
323 int datatype, /* are we allocating data? */
324 xfs_agblock_t freebno, /* freespace's starting block */
325 xfs_extlen_t freelen, /* freespace's length */
326 xfs_agblock_t *newbnop) /* result: best start block from free */
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;
336 ASSERT(freelen >= wantlen);
337 freeend = freebno + freelen;
338 wantend = wantbno + wantlen;
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.
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;
355 newlen1 = XFS_EXTLEN_MIN(wantlen, freeend - newbno1);
356 if (newbno2 < freebno)
357 newbno2 = NULLAGBLOCK;
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)))
366 } else if (newbno2 != NULLAGBLOCK)
368 } else if (freeend >= wantend) {
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;
378 newbno1 = freeend - wantlen;
380 return newbno1 == NULLAGBLOCK ? 0 : XFS_ABSDIFF(newbno1, wantbno);
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.
391 xfs_alloc_arg_t *args) /* allocation argument structure */
396 ASSERT(args->mod < args->prod);
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))
403 k = rlen % args->prod;
407 rlen = rlen - (k - args->mod);
409 rlen = rlen - args->prod + (args->mod - k);
410 /* casts to (int) catch length underflows */
411 if ((int)rlen < (int)args->minlen)
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);
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
427 STATIC int /* error code */
428 xfs_alloc_fixup_trees(
429 xfs_btree_cur_t *cnt_cur, /* cursor for by-size btree */
430 xfs_btree_cur_t *bno_cur, /* cursor for by-block btree */
431 xfs_agblock_t fbno, /* starting block of free extent */
432 xfs_extlen_t flen, /* length of free extent */
433 xfs_agblock_t rbno, /* starting block of returned extent */
434 xfs_extlen_t rlen, /* length of returned extent */
435 int flags) /* flags, XFSA_FIXUP_... */
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;
448 * Look up the record in the by-size tree if necessary.
450 if (flags & XFSA_FIXUP_CNT_OK) {
452 if ((error = xfs_alloc_get_rec(cnt_cur, &nfbno1, &nflen1, &i)))
454 if (XFS_IS_CORRUPT(mp,
458 return -EFSCORRUPTED;
461 if ((error = xfs_alloc_lookup_eq(cnt_cur, fbno, flen, &i)))
463 if (XFS_IS_CORRUPT(mp, i != 1))
464 return -EFSCORRUPTED;
467 * Look up the record in the by-block tree if necessary.
469 if (flags & XFSA_FIXUP_BNO_OK) {
471 if ((error = xfs_alloc_get_rec(bno_cur, &nfbno1, &nflen1, &i)))
473 if (XFS_IS_CORRUPT(mp,
477 return -EFSCORRUPTED;
480 if ((error = xfs_alloc_lookup_eq(bno_cur, fbno, flen, &i)))
482 if (XFS_IS_CORRUPT(mp, i != 1))
483 return -EFSCORRUPTED;
487 if (bno_cur->bc_nlevels == 1 && cnt_cur->bc_nlevels == 1) {
488 struct xfs_btree_block *bnoblock;
489 struct xfs_btree_block *cntblock;
491 bnoblock = XFS_BUF_TO_BLOCK(bno_cur->bc_bufs[0]);
492 cntblock = XFS_BUF_TO_BLOCK(cnt_cur->bc_bufs[0]);
494 if (XFS_IS_CORRUPT(mp,
495 bnoblock->bb_numrecs !=
496 cntblock->bb_numrecs))
497 return -EFSCORRUPTED;
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.
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) {
514 nflen1 = flen - rlen;
515 nfbno2 = NULLAGBLOCK;
518 nflen1 = rbno - fbno;
519 nfbno2 = rbno + rlen;
520 nflen2 = (fbno + flen) - nfbno2;
523 * Delete the entry from the by-size btree.
525 if ((error = xfs_btree_delete(cnt_cur, &i)))
527 if (XFS_IS_CORRUPT(mp, i != 1))
528 return -EFSCORRUPTED;
530 * Add new by-size btree entry(s).
532 if (nfbno1 != NULLAGBLOCK) {
533 if ((error = xfs_alloc_lookup_eq(cnt_cur, nfbno1, nflen1, &i)))
535 if (XFS_IS_CORRUPT(mp, i != 0))
536 return -EFSCORRUPTED;
537 if ((error = xfs_btree_insert(cnt_cur, &i)))
539 if (XFS_IS_CORRUPT(mp, i != 1))
540 return -EFSCORRUPTED;
542 if (nfbno2 != NULLAGBLOCK) {
543 if ((error = xfs_alloc_lookup_eq(cnt_cur, nfbno2, nflen2, &i)))
545 if (XFS_IS_CORRUPT(mp, i != 0))
546 return -EFSCORRUPTED;
547 if ((error = xfs_btree_insert(cnt_cur, &i)))
549 if (XFS_IS_CORRUPT(mp, i != 1))
550 return -EFSCORRUPTED;
553 * Fix up the by-block btree entry(s).
555 if (nfbno1 == NULLAGBLOCK) {
557 * No remaining freespace, just delete the by-block tree entry.
559 if ((error = xfs_btree_delete(bno_cur, &i)))
561 if (XFS_IS_CORRUPT(mp, i != 1))
562 return -EFSCORRUPTED;
565 * Update the by-block entry to start later|be shorter.
567 if ((error = xfs_alloc_update(bno_cur, nfbno1, nflen1)))
570 if (nfbno2 != NULLAGBLOCK) {
572 * 2 resulting free entries, need to add one.
574 if ((error = xfs_alloc_lookup_eq(bno_cur, nfbno2, nflen2, &i)))
576 if (XFS_IS_CORRUPT(mp, i != 0))
577 return -EFSCORRUPTED;
578 if ((error = xfs_btree_insert(bno_cur, &i)))
580 if (XFS_IS_CORRUPT(mp, i != 1))
581 return -EFSCORRUPTED;
586 static xfs_failaddr_t
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);
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.
601 if (!xfs_sb_version_hascrc(&mp->m_sb))
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;
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.
614 if (bp->b_pag && be32_to_cpu(agfl->agfl_seqno) != bp->b_pag->pag_agno)
615 return __this_address;
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;
623 if (!xfs_log_check_lsn(mp, be64_to_cpu(XFS_BUF_TO_AGFL(bp)->agfl_lsn)))
624 return __this_address;
629 xfs_agfl_read_verify(
632 struct xfs_mount *mp = bp->b_mount;
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.
641 if (!xfs_sb_version_hascrc(&mp->m_sb))
644 if (!xfs_buf_verify_cksum(bp, XFS_AGFL_CRC_OFF))
645 xfs_verifier_error(bp, -EFSBADCRC, __this_address);
647 fa = xfs_agfl_verify(bp);
649 xfs_verifier_error(bp, -EFSCORRUPTED, fa);
654 xfs_agfl_write_verify(
657 struct xfs_mount *mp = bp->b_mount;
658 struct xfs_buf_log_item *bip = bp->b_log_item;
661 /* no verification of non-crc AGFLs */
662 if (!xfs_sb_version_hascrc(&mp->m_sb))
665 fa = xfs_agfl_verify(bp);
667 xfs_verifier_error(bp, -EFSCORRUPTED, fa);
672 XFS_BUF_TO_AGFL(bp)->agfl_lsn = cpu_to_be64(bip->bli_item.li_lsn);
674 xfs_buf_update_cksum(bp, XFS_AGFL_CRC_OFF);
677 const struct xfs_buf_ops xfs_agfl_buf_ops = {
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,
686 * Read in the allocation group free block array.
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 */
695 struct xfs_buf *bp; /* return value */
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);
705 xfs_buf_set_ref(bp, XFS_AGFL_REF);
711 xfs_alloc_update_counters(
712 struct xfs_trans *tp,
713 struct xfs_buf *agbp,
716 struct xfs_agf *agf = agbp->b_addr;
718 agbp->b_pag->pagf_freeblks += len;
719 be32_add_cpu(&agf->agf_freeblks, len);
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;
727 xfs_alloc_log_agf(tp, agbp, XFS_AGF_FREEBLKS);
732 * Block allocation algorithm and data structures.
734 struct xfs_alloc_cur {
735 struct xfs_btree_cur *cnt; /* btree cursors */
736 struct xfs_btree_cur *bnolt;
737 struct xfs_btree_cur *bnogt;
738 xfs_extlen_t cur_len;/* current search length */
739 xfs_agblock_t rec_bno;/* extent startblock */
740 xfs_extlen_t rec_len;/* extent length */
741 xfs_agblock_t bno; /* alloc bno */
742 xfs_extlen_t len; /* alloc len */
743 xfs_extlen_t diff; /* diff from search bno */
744 unsigned int busy_gen;/* busy state */
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.
755 struct xfs_alloc_arg *args,
756 struct xfs_alloc_cur *acur)
761 ASSERT(args->alignment == 1 || args->type != XFS_ALLOCTYPE_THIS_BNO);
763 acur->cur_len = args->maxlen;
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.
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);
785 * Allocate the bnobt left and right search cursors.
788 acur->bnolt = xfs_allocbt_init_cursor(args->mp, args->tp,
789 args->agbp, args->pag, XFS_BTNUM_BNO);
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;
798 struct xfs_alloc_cur *acur,
801 int cur_error = XFS_BTREE_NOERROR;
804 cur_error = XFS_BTREE_ERROR;
807 xfs_btree_del_cursor(acur->cnt, cur_error);
809 xfs_btree_del_cursor(acur->bnolt, cur_error);
811 xfs_btree_del_cursor(acur->bnogt, cur_error);
812 acur->cnt = acur->bnolt = acur->bnogt = NULL;
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.
823 struct xfs_alloc_arg *args,
824 struct xfs_alloc_cur *acur,
825 struct xfs_btree_cur *cur,
829 xfs_agblock_t bno, bnoa, bnew;
830 xfs_extlen_t len, lena, diff = -1;
832 unsigned busy_gen = 0;
833 bool deactivate = false;
834 bool isbnobt = cur->bc_btnum == XFS_BTNUM_BNO;
838 error = xfs_alloc_get_rec(cur, &bno, &len, &i);
841 if (XFS_IS_CORRUPT(args->mp, i != 1))
842 return -EFSCORRUPTED;
845 * Check minlen and deactivate a cntbt cursor if out of acceptable size
846 * range (i.e., walking backwards looking for a minlen extent).
848 if (len < args->minlen) {
849 deactivate = !isbnobt;
853 busy = xfs_alloc_compute_aligned(args, bno, len, &bnoa, &lena,
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;
863 if (lena < args->minlen)
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)
873 * We have an aligned record that satisfies minlen and beats or matches
874 * the candidate extent size. Compare locality for near allocation mode.
876 ASSERT(args->type == XFS_ALLOCTYPE_NEAR_BNO);
877 diff = xfs_alloc_compute_diff(args->agbno, args->len,
878 args->alignment, args->datatype,
880 if (bnew == NULLAGBLOCK)
884 * Deactivate a bnobt cursor with worse locality than the current best.
886 if (diff > acur->diff) {
887 deactivate = isbnobt;
891 ASSERT(args->len > acur->len ||
892 (args->len == acur->len && diff <= acur->diff));
896 acur->len = args->len;
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.
905 if (acur->diff == 0 && acur->len == args->maxlen)
909 cur->bc_ag.abt.active = false;
910 trace_xfs_alloc_cur_check(args->mp, cur->bc_btnum, bno, len, diff,
916 * Complete an allocation of a candidate extent. Remove the extent from both
917 * trees and update the args structure.
920 xfs_alloc_cur_finish(
921 struct xfs_alloc_arg *args,
922 struct xfs_alloc_cur *acur)
924 struct xfs_agf __maybe_unused *agf = args->agbp->b_addr;
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));
932 error = xfs_alloc_fixup_trees(acur->cnt, acur->bnolt, acur->rec_bno,
933 acur->rec_len, acur->bno, acur->len, 0);
937 args->agbno = acur->bno;
938 args->len = acur->len;
941 trace_xfs_alloc_cur(args);
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.
950 xfs_alloc_cntbt_iter(
951 struct xfs_alloc_arg *args,
952 struct xfs_alloc_cur *acur)
954 struct xfs_btree_cur *cur = acur->cnt;
956 xfs_extlen_t len, cur_len;
960 if (!xfs_alloc_cur_active(cur))
963 /* locality optimized lookup */
964 cur_len = acur->cur_len;
965 error = xfs_alloc_lookup_ge(cur, args->agbno, cur_len, &i);
970 error = xfs_alloc_get_rec(cur, &bno, &len, &i);
974 /* check the current record and update search length from it */
975 error = xfs_alloc_cur_check(args, acur, cur, &i);
978 ASSERT(len >= acur->cur_len);
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.
988 if (bno > args->agbno) {
989 error = xfs_btree_decrement(cur, 0, &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,
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.
1007 if (!acur->len || acur->cur_len >= cur_len)
1010 acur->cur_len = cur_len;
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.
1020 STATIC int /* error */
1021 xfs_alloc_ag_vextent_small(
1022 struct xfs_alloc_arg *args, /* allocation argument structure */
1023 struct xfs_btree_cur *ccur, /* optional by-size cursor */
1024 xfs_agblock_t *fbnop, /* result block number */
1025 xfs_extlen_t *flenp, /* result length */
1026 int *stat) /* status: 0-freelist, 1-normal/none */
1028 struct xfs_agf *agf = args->agbp->b_addr;
1030 xfs_agblock_t fbno = NULLAGBLOCK;
1031 xfs_extlen_t flen = 0;
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
1041 error = xfs_btree_decrement(ccur, 0, &i);
1045 error = xfs_alloc_get_rec(ccur, &fbno, &flen, &i);
1048 if (XFS_IS_CORRUPT(args->mp, i != 1)) {
1049 error = -EFSCORRUPTED;
1055 if (args->minlen != 1 || args->alignment != 1 ||
1056 args->resv == XFS_AG_RESV_AGFL ||
1057 be32_to_cpu(agf->agf_flcount) <= args->minleft)
1060 error = xfs_alloc_get_freelist(args->tp, args->agbp, &fbno, 0);
1063 if (fbno == NULLAGBLOCK)
1066 xfs_extent_busy_reuse(args->mp, args->pag, fbno, 1,
1067 (args->datatype & XFS_ALLOC_NOBUSY));
1069 if (args->datatype & XFS_ALLOC_USERDATA) {
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);
1077 xfs_trans_binval(args->tp, bp);
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;
1085 args->wasfromfl = 1;
1086 trace_xfs_alloc_small_freelist(args);
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.
1092 error = xfs_rmap_free(args->tp, args->agbp, args->pag, fbno, 1,
1093 &XFS_RMAP_OINFO_AG);
1102 * Can't do the allocation, give up.
1104 if (flen < args->minlen) {
1105 args->agbno = NULLAGBLOCK;
1106 trace_xfs_alloc_small_notenough(args);
1112 trace_xfs_alloc_small_done(args);
1116 trace_xfs_alloc_small_error(args);
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.
1128 STATIC int /* error */
1129 xfs_alloc_ag_vextent(
1130 xfs_alloc_arg_t *args) /* argument structure for allocation */
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);
1141 * Branch to correct routine based on the type.
1143 args->wasfromfl = 0;
1144 switch (args->type) {
1145 case XFS_ALLOCTYPE_THIS_AG:
1146 error = xfs_alloc_ag_vextent_size(args);
1148 case XFS_ALLOCTYPE_NEAR_BNO:
1149 error = xfs_alloc_ag_vextent_near(args);
1151 case XFS_ALLOCTYPE_THIS_BNO:
1152 error = xfs_alloc_ag_vextent_exact(args);
1159 if (error || args->agbno == NULLAGBLOCK)
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);
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);
1175 if (!args->wasfromfl) {
1176 error = xfs_alloc_update_counters(args->tp, args->agbp,
1177 -((long)(args->len)));
1181 ASSERT(!xfs_extent_busy_search(args->mp, args->pag,
1182 args->agbno, args->len));
1185 xfs_ag_resv_alloc_extent(args->pag, args->resv, args);
1187 XFS_STATS_INC(args->mp, xs_allocx);
1188 XFS_STATS_ADD(args->mp, xs_allocb, args->len);
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.
1198 STATIC int /* error */
1199 xfs_alloc_ag_vextent_exact(
1200 xfs_alloc_arg_t *args) /* allocation argument structure */
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 */
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 */
1214 ASSERT(args->alignment == 1);
1217 * Allocate/initialize a cursor for the by-number freespace btree.
1219 bno_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
1220 args->pag, XFS_BTNUM_BNO);
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.
1227 error = xfs_alloc_lookup_le(bno_cur, args->agbno, args->minlen, &i);
1234 * Grab the freespace record.
1236 error = xfs_alloc_get_rec(bno_cur, &fbno, &flen, &i);
1239 if (XFS_IS_CORRUPT(args->mp, i != 1)) {
1240 error = -EFSCORRUPTED;
1243 ASSERT(fbno <= args->agbno);
1246 * Check for overlapping busy extents.
1250 xfs_extent_busy_trim(args, &tbno, &tlen, &busy_gen);
1253 * Give up if the start of the extent is busy, or the freespace isn't
1254 * long enough for the minimum request.
1256 if (tbno > args->agbno)
1258 if (tlen < args->minlen)
1261 if (tend < args->agbno + args->minlen)
1265 * End of extent will be smaller of the freespace end and the
1266 * maximal requested end.
1268 * Fix the length according to mod and prod if given.
1270 args->len = XFS_AGBLOCK_MIN(tend, args->agbno + args->maxlen)
1272 xfs_alloc_fix_len(args);
1273 ASSERT(args->agbno + args->len <= tend);
1276 * We are allocating agbno for args->len
1277 * Allocate/initialize a cursor for the by-size btree.
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);
1285 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
1289 xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
1290 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1292 args->wasfromfl = 0;
1293 trace_xfs_alloc_exact_done(args);
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);
1304 xfs_btree_del_cursor(bno_cur, XFS_BTREE_ERROR);
1305 trace_xfs_alloc_exact_error(args);
1310 * Search a given number of btree records in a given direction. Check each
1311 * record against the good extent we've already found.
1314 xfs_alloc_walk_iter(
1315 struct xfs_alloc_arg *args,
1316 struct xfs_alloc_cur *acur,
1317 struct xfs_btree_cur *cur,
1319 bool find_one, /* quit on first candidate */
1320 int count, /* rec count (-1 for infinite) */
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.
1333 while (xfs_alloc_cur_active(cur) && count) {
1334 error = xfs_alloc_cur_check(args, acur, cur, &i);
1342 if (!xfs_alloc_cur_active(cur))
1346 error = xfs_btree_increment(cur, 0, &i);
1348 error = xfs_btree_decrement(cur, 0, &i);
1352 cur->bc_ag.abt.active = false;
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.
1366 xfs_alloc_ag_vextent_locality(
1367 struct xfs_alloc_arg *args,
1368 struct xfs_alloc_cur *acur,
1371 struct xfs_btree_cur *fbcur = NULL;
1376 ASSERT(acur->len == 0);
1377 ASSERT(args->type == XFS_ALLOCTYPE_NEAR_BNO);
1381 error = xfs_alloc_lookup_ge(acur->cnt, args->agbno, acur->cur_len, &i);
1384 error = xfs_alloc_lookup_le(acur->bnolt, args->agbno, 0, &i);
1387 error = xfs_alloc_lookup_ge(acur->bnogt, args->agbno, 0, &i);
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.
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.
1413 while (xfs_alloc_cur_active(acur->bnolt) ||
1414 xfs_alloc_cur_active(acur->bnogt) ||
1415 xfs_alloc_cur_active(acur->cnt)) {
1417 trace_xfs_alloc_cur_lookup(args);
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.
1423 error = xfs_alloc_walk_iter(args, acur, acur->bnolt, false,
1428 trace_xfs_alloc_cur_left(args);
1429 fbcur = acur->bnogt;
1433 error = xfs_alloc_walk_iter(args, acur, acur->bnogt, true, true,
1438 trace_xfs_alloc_cur_right(args);
1439 fbcur = acur->bnolt;
1445 * Check the extent with best locality based on the current
1446 * extent size search key and keep track of the best candidate.
1448 error = xfs_alloc_cntbt_iter(args, acur);
1451 if (!xfs_alloc_cur_active(acur->cnt)) {
1452 trace_xfs_alloc_cur_lookup_done(args);
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.
1462 if (!xfs_alloc_cur_active(acur->cnt) && !acur->len && !acur->busy) {
1463 error = xfs_btree_decrement(acur->cnt, 0, &i);
1467 acur->cnt->bc_ag.abt.active = true;
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.
1478 error = xfs_alloc_walk_iter(args, acur, fbcur, fbinc, true, -1,
1490 /* Check the last block of the cnt btree for allocations. */
1492 xfs_alloc_ag_vextent_lastblock(
1493 struct xfs_alloc_arg *args,
1494 struct xfs_alloc_cur *acur,
1503 /* Randomly don't execute the first algorithm. */
1504 if (prandom_u32() & 1)
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
1514 if (*len || args->alignment > 1) {
1515 acur->cnt->bc_ptrs[0] = 1;
1517 error = xfs_alloc_get_rec(acur->cnt, bno, len, &i);
1520 if (XFS_IS_CORRUPT(args->mp, i != 1))
1521 return -EFSCORRUPTED;
1522 if (*len >= args->minlen)
1524 error = xfs_btree_increment(acur->cnt, 0, &i);
1528 ASSERT(*len >= args->minlen);
1533 error = xfs_alloc_walk_iter(args, acur, acur->cnt, true, false, -1, &i);
1538 * It didn't work. We COULD be in a case where there's a good record
1539 * somewhere, so try again.
1544 trace_xfs_alloc_near_first(args);
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.
1556 xfs_alloc_ag_vextent_near(
1557 struct xfs_alloc_arg *args)
1559 struct xfs_alloc_cur acur = {};
1560 int error; /* error code */
1561 int i; /* result code, temporary */
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);
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;
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
1584 error = xfs_alloc_cur_setup(args, &acur);
1585 if (error == -ENOSPC) {
1586 error = xfs_alloc_ag_vextent_small(args, acur.cnt, &bno,
1590 if (i == 0 || len == 0) {
1591 trace_xfs_alloc_near_noentry(args);
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.
1607 if (xfs_btree_islastblock(acur.cnt, 0)) {
1608 bool allocated = false;
1610 error = xfs_alloc_ag_vextent_lastblock(args, &acur, &bno, &len,
1619 * Second algorithm. Combined cntbt and bnobt search to find ideal
1622 error = xfs_alloc_ag_vextent_locality(args, &acur, &i);
1627 * If we couldn't get anything, give up.
1631 trace_xfs_alloc_near_busy(args);
1632 xfs_extent_busy_flush(args->mp, args->pag,
1636 trace_xfs_alloc_size_neither(args);
1637 args->agbno = NULLAGBLOCK;
1642 /* fix up btrees on a successful allocation */
1643 error = xfs_alloc_cur_finish(args, &acur);
1646 xfs_alloc_cur_close(&acur, error);
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.
1656 STATIC int /* error */
1657 xfs_alloc_ag_vextent_size(
1658 xfs_alloc_arg_t *args) /* allocation argument structure */
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 */
1674 * Allocate and initialize a cursor for the by-size btree.
1676 cnt_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
1677 args->pag, XFS_BTNUM_CNT);
1681 * Look for an entry >= maxlen+alignment-1 blocks.
1683 if ((error = xfs_alloc_lookup_ge(cnt_cur, 0,
1684 args->maxlen + args->alignment - 1, &i)))
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.
1695 error = xfs_alloc_ag_vextent_small(args, cnt_cur,
1699 if (i == 0 || flen == 0) {
1700 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1701 trace_xfs_alloc_size_noentry(args);
1705 busy = xfs_alloc_compute_aligned(args, fbno, flen, &rbno,
1709 * Search for a non-busy extent that is large enough.
1712 error = xfs_alloc_get_rec(cnt_cur, &fbno, &flen, &i);
1715 if (XFS_IS_CORRUPT(args->mp, i != 1)) {
1716 error = -EFSCORRUPTED;
1720 busy = xfs_alloc_compute_aligned(args, fbno, flen,
1721 &rbno, &rlen, &busy_gen);
1723 if (rlen >= args->maxlen)
1726 error = xfs_btree_increment(cnt_cur, 0, &i);
1731 * Our only valid extents must have been busy.
1732 * Make it unbusy by forcing the log out and
1735 xfs_btree_del_cursor(cnt_cur,
1737 trace_xfs_alloc_size_busy(args);
1738 xfs_extent_busy_flush(args->mp,
1739 args->pag, busy_gen);
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.
1751 rlen = XFS_EXTLEN_MIN(args->maxlen, rlen);
1752 if (XFS_IS_CORRUPT(args->mp,
1755 rbno + rlen > fbno + flen))) {
1756 error = -EFSCORRUPTED;
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;
1770 if ((error = xfs_btree_decrement(cnt_cur, 0, &i)))
1774 if ((error = xfs_alloc_get_rec(cnt_cur, &fbno, &flen,
1777 if (XFS_IS_CORRUPT(args->mp, i != 1)) {
1778 error = -EFSCORRUPTED;
1781 if (flen < bestrlen)
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,
1789 rbno + rlen > fbno + flen))) {
1790 error = -EFSCORRUPTED;
1793 if (rlen > bestrlen) {
1798 if (rlen == args->maxlen)
1802 if ((error = xfs_alloc_lookup_eq(cnt_cur, bestfbno, bestflen,
1805 if (XFS_IS_CORRUPT(args->mp, i != 1)) {
1806 error = -EFSCORRUPTED;
1814 args->wasfromfl = 0;
1816 * Fix up the length.
1819 if (rlen < args->minlen) {
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);
1828 xfs_alloc_fix_len(args);
1831 if (XFS_IS_CORRUPT(args->mp, rlen > flen)) {
1832 error = -EFSCORRUPTED;
1836 * Allocate and initialize a cursor for the by-block tree.
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)))
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;
1848 if (XFS_IS_CORRUPT(args->mp,
1849 args->agbno + args->len >
1850 be32_to_cpu(agf->agf_length))) {
1851 error = -EFSCORRUPTED;
1854 trace_xfs_alloc_size_done(args);
1858 trace_xfs_alloc_size_error(args);
1860 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
1862 xfs_btree_del_cursor(bno_cur, XFS_BTREE_ERROR);
1866 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1867 trace_xfs_alloc_size_nominleft(args);
1868 args->agbno = NULLAGBLOCK;
1873 * Free the extent starting at agno/bno for length.
1877 struct xfs_trans *tp,
1878 struct xfs_buf *agbp,
1879 xfs_agnumber_t agno,
1882 const struct xfs_owner_info *oinfo,
1883 enum xfs_ag_resv_type type)
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 */
1898 struct xfs_perag *pag = agbp->b_pag;
1900 bno_cur = cnt_cur = NULL;
1903 if (!xfs_rmap_should_skip_owner_update(oinfo)) {
1904 error = xfs_rmap_free(tp, agbp, pag, bno, len, oinfo);
1910 * Allocate and initialize a cursor for the by-block btree.
1912 bno_cur = xfs_allocbt_init_cursor(mp, tp, agbp, pag, XFS_BTNUM_BNO);
1914 * Look for a neighboring block on the left (lower block numbers)
1915 * that is contiguous with this space.
1917 if ((error = xfs_alloc_lookup_le(bno_cur, bno, len, &haveleft)))
1921 * There is a block to our left.
1923 if ((error = xfs_alloc_get_rec(bno_cur, <bno, <len, &i)))
1925 if (XFS_IS_CORRUPT(mp, i != 1)) {
1926 error = -EFSCORRUPTED;
1930 * It's not contiguous, though.
1932 if (ltbno + ltlen < bno)
1936 * If this failure happens the request to free this
1937 * space was invalid, it's (partly) already free.
1940 if (XFS_IS_CORRUPT(mp, ltbno + ltlen > bno)) {
1941 error = -EFSCORRUPTED;
1947 * Look for a neighboring block on the right (higher block numbers)
1948 * that is contiguous with this space.
1950 if ((error = xfs_btree_increment(bno_cur, 0, &haveright)))
1954 * There is a block to our right.
1956 if ((error = xfs_alloc_get_rec(bno_cur, >bno, >len, &i)))
1958 if (XFS_IS_CORRUPT(mp, i != 1)) {
1959 error = -EFSCORRUPTED;
1963 * It's not contiguous, though.
1965 if (bno + len < gtbno)
1969 * If this failure happens the request to free this
1970 * space was invalid, it's (partly) already free.
1973 if (XFS_IS_CORRUPT(mp, bno + len > gtbno)) {
1974 error = -EFSCORRUPTED;
1980 * Now allocate and initialize a cursor for the by-size tree.
1982 cnt_cur = xfs_allocbt_init_cursor(mp, tp, agbp, pag, XFS_BTNUM_CNT);
1984 * Have both left and right contiguous neighbors.
1985 * Merge all three into a single free block.
1987 if (haveleft && haveright) {
1989 * Delete the old by-size entry on the left.
1991 if ((error = xfs_alloc_lookup_eq(cnt_cur, ltbno, ltlen, &i)))
1993 if (XFS_IS_CORRUPT(mp, i != 1)) {
1994 error = -EFSCORRUPTED;
1997 if ((error = xfs_btree_delete(cnt_cur, &i)))
1999 if (XFS_IS_CORRUPT(mp, i != 1)) {
2000 error = -EFSCORRUPTED;
2004 * Delete the old by-size entry on the right.
2006 if ((error = xfs_alloc_lookup_eq(cnt_cur, gtbno, gtlen, &i)))
2008 if (XFS_IS_CORRUPT(mp, i != 1)) {
2009 error = -EFSCORRUPTED;
2012 if ((error = xfs_btree_delete(cnt_cur, &i)))
2014 if (XFS_IS_CORRUPT(mp, i != 1)) {
2015 error = -EFSCORRUPTED;
2019 * Delete the old by-block entry for the right block.
2021 if ((error = xfs_btree_delete(bno_cur, &i)))
2023 if (XFS_IS_CORRUPT(mp, i != 1)) {
2024 error = -EFSCORRUPTED;
2028 * Move the by-block cursor back to the left neighbor.
2030 if ((error = xfs_btree_decrement(bno_cur, 0, &i)))
2032 if (XFS_IS_CORRUPT(mp, i != 1)) {
2033 error = -EFSCORRUPTED;
2038 * Check that this is the right record: delete didn't
2039 * mangle the cursor.
2042 xfs_agblock_t xxbno;
2045 if ((error = xfs_alloc_get_rec(bno_cur, &xxbno, &xxlen,
2048 if (XFS_IS_CORRUPT(mp,
2052 error = -EFSCORRUPTED;
2058 * Update remaining by-block entry to the new, joined block.
2061 nlen = len + ltlen + gtlen;
2062 if ((error = xfs_alloc_update(bno_cur, nbno, nlen)))
2066 * Have only a left contiguous neighbor.
2067 * Merge it together with the new freespace.
2069 else if (haveleft) {
2071 * Delete the old by-size entry on the left.
2073 if ((error = xfs_alloc_lookup_eq(cnt_cur, ltbno, ltlen, &i)))
2075 if (XFS_IS_CORRUPT(mp, i != 1)) {
2076 error = -EFSCORRUPTED;
2079 if ((error = xfs_btree_delete(cnt_cur, &i)))
2081 if (XFS_IS_CORRUPT(mp, i != 1)) {
2082 error = -EFSCORRUPTED;
2086 * Back up the by-block cursor to the left neighbor, and
2087 * update its length.
2089 if ((error = xfs_btree_decrement(bno_cur, 0, &i)))
2091 if (XFS_IS_CORRUPT(mp, i != 1)) {
2092 error = -EFSCORRUPTED;
2097 if ((error = xfs_alloc_update(bno_cur, nbno, nlen)))
2101 * Have only a right contiguous neighbor.
2102 * Merge it together with the new freespace.
2104 else if (haveright) {
2106 * Delete the old by-size entry on the right.
2108 if ((error = xfs_alloc_lookup_eq(cnt_cur, gtbno, gtlen, &i)))
2110 if (XFS_IS_CORRUPT(mp, i != 1)) {
2111 error = -EFSCORRUPTED;
2114 if ((error = xfs_btree_delete(cnt_cur, &i)))
2116 if (XFS_IS_CORRUPT(mp, i != 1)) {
2117 error = -EFSCORRUPTED;
2121 * Update the starting block and length of the right
2122 * neighbor in the by-block tree.
2126 if ((error = xfs_alloc_update(bno_cur, nbno, nlen)))
2130 * No contiguous neighbors.
2131 * Insert the new freespace into the by-block tree.
2136 if ((error = xfs_btree_insert(bno_cur, &i)))
2138 if (XFS_IS_CORRUPT(mp, i != 1)) {
2139 error = -EFSCORRUPTED;
2143 xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
2146 * In all cases we need to insert the new freespace in the by-size tree.
2148 if ((error = xfs_alloc_lookup_eq(cnt_cur, nbno, nlen, &i)))
2150 if (XFS_IS_CORRUPT(mp, i != 0)) {
2151 error = -EFSCORRUPTED;
2154 if ((error = xfs_btree_insert(cnt_cur, &i)))
2156 if (XFS_IS_CORRUPT(mp, i != 1)) {
2157 error = -EFSCORRUPTED;
2160 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
2164 * Update the freespace totals in the ag and superblock.
2166 error = xfs_alloc_update_counters(tp, agbp, len);
2167 xfs_ag_resv_free_extent(agbp->b_pag, type, tp, len);
2171 XFS_STATS_INC(mp, xs_freex);
2172 XFS_STATS_ADD(mp, xs_freeb, len);
2174 trace_xfs_free_extent(mp, agno, bno, len, type, haveleft, haveright);
2179 trace_xfs_free_extent(mp, agno, bno, len, type, -1, -1);
2181 xfs_btree_del_cursor(bno_cur, XFS_BTREE_ERROR);
2183 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
2188 * Visible (exported) allocation/free functions.
2189 * Some of these are used just by xfs_alloc_btree.c and this file.
2193 * Compute and fill in value of m_ag_maxlevels.
2196 xfs_alloc_compute_maxlevels(
2197 xfs_mount_t *mp) /* file system mount structure */
2199 mp->m_ag_maxlevels = xfs_btree_compute_maxlevels(mp->m_alloc_mnr,
2200 (mp->m_sb.sb_agblocks + 1) / 2);
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
2210 xfs_alloc_longest_free_extent(
2211 struct xfs_perag *pag,
2213 xfs_extlen_t reserved)
2215 xfs_extlen_t delta = 0;
2218 * If the AGFL needs a recharge, we'll have to subtract that from the
2221 if (need > pag->pagf_flcount)
2222 delta = need - pag->pagf_flcount;
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.
2229 if (pag->pagf_freeblks - pag->pagf_longest < reserved)
2230 delta += reserved - (pag->pagf_freeblks - pag->pagf_longest);
2233 * If the longest extent is long enough to satisfy all the
2234 * reservations and AGFL rules in place, we can return this extent.
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);
2240 /* Otherwise, let the caller try for 1 block if there's space. */
2241 return pag->pagf_flcount > 0 || pag->pagf_longest > 0;
2245 * Compute the minimum length of the AGFL in the given AG. If @pag is NULL,
2246 * return the largest possible minimum length.
2249 xfs_alloc_min_freelist(
2250 struct xfs_mount *mp,
2251 struct xfs_perag *pag)
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;
2258 ASSERT(mp->m_ag_maxlevels > 0);
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);
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.
2281 xfs_alloc_space_available(
2282 struct xfs_alloc_arg *args,
2283 xfs_extlen_t min_free,
2286 struct xfs_perag *pag = args->pag;
2287 xfs_extlen_t alloc_len, longest;
2288 xfs_extlen_t reservation; /* blocks that are still reserved */
2290 xfs_extlen_t agflcount;
2292 if (flags & XFS_ALLOC_FLAG_FREEING)
2295 reservation = xfs_ag_resv_needed(pag, args->resv);
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)
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.
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))
2315 * Clamp maxlen to the amount of free space available for the actual
2316 * extent allocation.
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);
2328 xfs_free_agfl_block(
2329 struct xfs_trans *tp,
2330 xfs_agnumber_t agno,
2331 xfs_agblock_t agbno,
2332 struct xfs_buf *agbp,
2333 struct xfs_owner_info *oinfo)
2338 error = xfs_free_ag_extent(tp, agbp, agno, agbno, 1, oinfo,
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);
2348 xfs_trans_binval(tp, bp);
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.
2361 * Return true if a reset is required before the agfl can be used, false
2365 xfs_agfl_needs_reset(
2366 struct xfs_mount *mp,
2367 struct xfs_agf *agf)
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);
2375 /* no agfl header on v4 supers */
2376 if (!xfs_sb_version_hascrc(&mp->m_sb))
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.
2384 if (f >= agfl_size || l >= agfl_size)
2390 * Check consistency between the on-disk count and the active range. An
2391 * agfl padding mismatch manifests as an inconsistent flcount.
2396 active = agfl_size - f + l + 1;
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.
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.
2415 struct xfs_trans *tp,
2416 struct xfs_buf *agbp,
2417 struct xfs_perag *pag)
2419 struct xfs_mount *mp = tp->t_mountp;
2420 struct xfs_agf *agf = agbp->b_addr;
2422 ASSERT(pag->pagf_agflreset);
2423 trace_xfs_agfl_reset(mp, agf, 0, _RET_IP_);
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);
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 |
2436 pag->pagf_flcount = 0;
2437 pag->pagf_agflreset = false;
2441 * Defer an AGFL block free. This is effectively equivalent to
2442 * xfs_bmap_add_free() with some special handling particular to AGFL blocks.
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.
2452 xfs_defer_agfl_block(
2453 struct xfs_trans *tp,
2454 xfs_agnumber_t agno,
2455 xfs_fsblock_t agbno,
2456 struct xfs_owner_info *oinfo)
2458 struct xfs_mount *mp = tp->t_mountp;
2459 struct xfs_extent_free_item *new; /* new element */
2461 ASSERT(xfs_bmap_free_item_zone != NULL);
2462 ASSERT(oinfo != NULL);
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;
2471 trace_xfs_agfl_free_defer(mp, agno, 0, agbno, 1);
2473 xfs_defer_add(tp, XFS_DEFER_OPS_TYPE_AGFL_FREE, &new->xefi_list);
2478 * Check if an AGF has a free extent record whose length is equal to
2482 xfs_exact_minlen_extent_available(
2483 struct xfs_alloc_arg *args,
2484 struct xfs_buf *agbp,
2487 struct xfs_btree_cur *cnt_cur;
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);
2499 error = -EFSCORRUPTED;
2503 error = xfs_alloc_get_rec(cnt_cur, &fbno, &flen, stat);
2507 if (*stat == 1 && flen != args->minlen)
2511 xfs_btree_del_cursor(cnt_cur, error);
2518 * Decide whether to use this allocation group for this allocation.
2519 * If so, fix up the btree freelist's size.
2522 xfs_alloc_fix_freelist(
2523 struct xfs_alloc_arg *args, /* allocation argument structure */
2524 int flags) /* XFS_ALLOC_FLAG_... */
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 */
2536 /* deferred ops (AGFL block frees) require permanent transactions */
2537 ASSERT(tp->t_flags & XFS_TRANS_PERM_LOG_RES);
2539 if (!pag->pagf_init) {
2540 error = xfs_alloc_read_agf(mp, tp, args->agno, flags, &agbp);
2542 /* Couldn't lock the AGF so skip this AG. */
2543 if (error == -EAGAIN)
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
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;
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;
2566 * Get the a.g. freespace buffer.
2567 * Can fail if we're not blocking on locks, and it's held.
2570 error = xfs_alloc_read_agf(mp, tp, args->agno, flags, &agbp);
2572 /* Couldn't lock the AGF so skip this AG. */
2573 if (error == -EAGAIN)
2579 /* reset a padding mismatched agfl before final free space check */
2580 if (pag->pagf_agflreset)
2581 xfs_agfl_reset(tp, agbp, pag);
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;
2589 if (args->alloc_minlen_only) {
2592 error = xfs_exact_minlen_extent_available(args, agbp, &stat);
2594 goto out_agbp_relse;
2598 * Make the freelist shorter if it's too long.
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
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?
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.
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;
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);
2630 goto out_agbp_relse;
2632 /* defer agfl frees */
2633 xfs_defer_agfl_block(tp, args->agno, bno, &targs.oinfo);
2639 targs.agno = args->agno;
2640 targs.alignment = targs.minlen = targs.prod = 1;
2641 targs.type = XFS_ALLOCTYPE_THIS_AG;
2643 error = xfs_alloc_read_agfl(mp, tp, targs.agno, &agflbp);
2645 goto out_agbp_relse;
2647 /* Make the freelist longer if it's too short. */
2648 while (pag->pagf_flcount < need) {
2650 targs.maxlen = need - pag->pagf_flcount;
2651 targs.resv = XFS_AG_RESV_AGFL;
2653 /* Allocate as many blocks as possible at once. */
2654 error = xfs_alloc_ag_vextent(&targs);
2656 goto out_agflbp_relse;
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.
2663 if (targs.agbno == NULLAGBLOCK) {
2664 if (flags & XFS_ALLOC_FLAG_FREEING)
2666 goto out_agflbp_relse;
2669 * Put each allocated block on the list.
2671 for (bno = targs.agbno; bno < targs.agbno + targs.len; bno++) {
2672 error = xfs_alloc_put_freelist(tp, agbp,
2675 goto out_agflbp_relse;
2678 xfs_trans_brelse(tp, agflbp);
2683 xfs_trans_brelse(tp, agflbp);
2686 xfs_trans_brelse(tp, agbp);
2693 * Get a block from the freelist.
2694 * Returns with the buffer for the block gotten.
2697 xfs_alloc_get_freelist(
2698 struct xfs_trans *tp,
2699 struct xfs_buf *agbp,
2700 xfs_agblock_t *bnop,
2703 struct xfs_agf *agf = agbp->b_addr;
2704 struct xfs_buf *agflbp;
2709 struct xfs_mount *mp = tp->t_mountp;
2710 struct xfs_perag *pag;
2713 * Freelist is empty, give up.
2715 if (!agf->agf_flcount) {
2716 *bnop = NULLAGBLOCK;
2720 * Read the array of free blocks.
2722 error = xfs_alloc_read_agfl(mp, tp, be32_to_cpu(agf->agf_seqno),
2729 * Get the block number and update the data structures.
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;
2739 ASSERT(!pag->pagf_agflreset);
2740 be32_add_cpu(&agf->agf_flcount, -1);
2741 pag->pagf_flcount--;
2743 logflags = XFS_AGF_FLFIRST | XFS_AGF_FLCOUNT;
2745 be32_add_cpu(&agf->agf_btreeblks, 1);
2746 pag->pagf_btreeblks++;
2747 logflags |= XFS_AGF_BTREEBLKS;
2750 xfs_alloc_log_agf(tp, agbp, logflags);
2757 * Log the given fields from the agf structure.
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_...) */
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),
2790 trace_xfs_agf(tp->t_mountp, bp->b_addr, fields, _RET_IP_);
2792 xfs_trans_buf_set_type(tp, bp, XFS_BLFT_AGF_BUF);
2794 xfs_btree_offsets(fields, offsets, XFS_AGF_NUM_BITS, &first, &last);
2795 xfs_trans_log_buf(tp, bp, (uint)first, (uint)last);
2799 * Interface for inode allocation to force the pag data to be initialized.
2802 xfs_alloc_pagf_init(
2803 xfs_mount_t *mp, /* file system mount structure */
2804 xfs_trans_t *tp, /* transaction pointer */
2805 xfs_agnumber_t agno, /* allocation group number */
2806 int flags) /* XFS_ALLOC_FLAGS_... */
2811 error = xfs_alloc_read_agf(mp, tp, agno, flags, &bp);
2813 xfs_trans_brelse(tp, bp);
2818 * Put the block on the freelist for the allocation group.
2821 xfs_alloc_put_freelist(
2822 struct xfs_trans *tp,
2823 struct xfs_buf *agbp,
2824 struct xfs_buf *agflbp,
2828 struct xfs_mount *mp = tp->t_mountp;
2829 struct xfs_agf *agf = agbp->b_addr;
2830 struct xfs_perag *pag;
2837 if (!agflbp && (error = xfs_alloc_read_agfl(mp, tp,
2838 be32_to_cpu(agf->agf_seqno), &agflbp)))
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;
2845 ASSERT(!pag->pagf_agflreset);
2846 be32_add_cpu(&agf->agf_flcount, 1);
2847 pag->pagf_flcount++;
2849 logflags = XFS_AGF_FLLAST | XFS_AGF_FLCOUNT;
2851 be32_add_cpu(&agf->agf_btreeblks, -1);
2852 pag->pagf_btreeblks--;
2853 logflags |= XFS_AGF_BTREEBLKS;
2856 xfs_alloc_log_agf(tp, agbp, logflags);
2858 ASSERT(be32_to_cpu(agf->agf_flcount) <= xfs_agfl_size(mp));
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;
2865 xfs_alloc_log_agf(tp, agbp, logflags);
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);
2873 static xfs_failaddr_t
2877 struct xfs_mount *mp = bp->b_mount;
2878 struct xfs_agf *agf = bp->b_addr;
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;
2887 if (!xfs_verify_magic(bp, agf->agf_magicnum))
2888 return __this_address;
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;
2897 if (be32_to_cpu(agf->agf_length) > mp->m_sb.sb_dblocks)
2898 return __this_address;
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;
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;
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;
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;
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.
2925 if (bp->b_pag && be32_to_cpu(agf->agf_seqno) != bp->b_pag->pag_agno)
2926 return __this_address;
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;
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;
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;
2947 xfs_agf_read_verify(
2950 struct xfs_mount *mp = bp->b_mount;
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);
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);
2964 xfs_agf_write_verify(
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;
2972 fa = xfs_agf_verify(bp);
2974 xfs_verifier_error(bp, -EFSCORRUPTED, fa);
2978 if (!xfs_sb_version_hascrc(&mp->m_sb))
2982 agf->agf_lsn = cpu_to_be64(bip->bli_item.li_lsn);
2984 xfs_buf_update_cksum(bp, XFS_AGF_CRC_OFF);
2987 const struct xfs_buf_ops xfs_agf_buf_ops = {
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,
2996 * Read in the allocation group header (free/alloc section).
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 */
3008 trace_xfs_read_agf(mp, agno);
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);
3017 ASSERT(!(*bpp)->b_error);
3018 xfs_buf_set_ref(*bpp, XFS_AGF_REF);
3023 * Read in the allocation group header (free/alloc section).
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 */
3033 struct xfs_agf *agf; /* ag freelist header */
3034 struct xfs_perag *pag; /* per allocation group data */
3038 trace_xfs_alloc_read_agf(mp, agno);
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,
3049 ASSERT(!(*bpp)->b_error);
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);
3066 pag->pagf_agflreset = xfs_agfl_needs_reset(mp, agf);
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.
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);
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]));
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.
3103 struct xfs_alloc_arg *args) /* allocation argument structure */
3105 xfs_agblock_t agsize; /* allocation group size */
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 */
3112 xfs_agnumber_t rotorstep = xfs_rotorstep; /* inode32 agf stepper */
3115 type = args->otype = args->type;
3116 args->agbno = NULLAGBLOCK;
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).
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);
3142 case XFS_ALLOCTYPE_THIS_AG:
3143 case XFS_ALLOCTYPE_NEAR_BNO:
3144 case XFS_ALLOCTYPE_THIS_BNO:
3146 * These three force us into a single a.g.
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);
3152 trace_xfs_alloc_vextent_nofix(args);
3156 trace_xfs_alloc_vextent_noagbp(args);
3159 args->agbno = XFS_FSB_TO_AGBNO(mp, args->fsbno);
3160 if ((error = xfs_alloc_ag_vextent(args)))
3163 case XFS_ALLOCTYPE_START_BNO:
3165 * Try near allocation first, then anywhere-in-ag after
3166 * the first a.g. fails.
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);
3175 args->agbno = XFS_FSB_TO_AGBNO(mp, args->fsbno);
3176 args->type = XFS_ALLOCTYPE_NEAR_BNO;
3178 case XFS_ALLOCTYPE_FIRST_AG:
3180 * Rotate through the allocation groups looking for a winner.
3182 if (type == XFS_ALLOCTYPE_FIRST_AG) {
3184 * Start with allocation group given by bno.
3186 args->agno = XFS_FSB_TO_AGNO(mp, args->fsbno);
3187 args->type = XFS_ALLOCTYPE_THIS_AG;
3192 * Start with the given allocation group.
3194 args->agno = sagno = XFS_FSB_TO_AGNO(mp, args->fsbno);
3195 flags = XFS_ALLOC_FLAG_TRYLOCK;
3198 * Loop over allocation groups twice; first time with
3199 * trylock set, second time without.
3202 args->pag = xfs_perag_get(mp, args->agno);
3203 error = xfs_alloc_fix_freelist(args, flags);
3205 trace_xfs_alloc_vextent_nofix(args);
3209 * If we get a buffer back then the allocation will fly.
3212 if ((error = xfs_alloc_ag_vextent(args)))
3217 trace_xfs_alloc_vextent_loopfailed(args);
3220 * Didn't work, figure out the next iteration.
3222 if (args->agno == sagno &&
3223 type == XFS_ALLOCTYPE_START_BNO)
3224 args->type = XFS_ALLOCTYPE_THIS_AG;
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.
3232 if (++(args->agno) == mp->m_sb.sb_agcount) {
3233 if (args->tp->t_firstblock != NULLFSBLOCK)
3239 * Reached the starting a.g., must either be done
3240 * or switch to non-trylock mode.
3242 if (args->agno == sagno) {
3244 args->agbno = NULLAGBLOCK;
3245 trace_xfs_alloc_vextent_allfailed(args);
3250 if (type == XFS_ALLOCTYPE_START_BNO) {
3251 args->agbno = XFS_FSB_TO_AGBNO(mp,
3253 args->type = XFS_ALLOCTYPE_NEAR_BNO;
3256 xfs_perag_put(args->pag);
3259 if (args->agno == sagno)
3260 mp->m_agfrotor = (mp->m_agfrotor + 1) %
3261 (mp->m_sb.sb_agcount * rotorstep);
3263 mp->m_agfrotor = (args->agno * rotorstep + 1) %
3264 (mp->m_sb.sb_agcount * rotorstep);
3271 if (args->agbno == NULLAGBLOCK)
3272 args->fsbno = NULLFSBLOCK;
3274 args->fsbno = XFS_AGB_TO_FSB(mp, args->agno, args->agbno);
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),
3284 xfs_perag_put(args->pag);
3287 xfs_perag_put(args->pag);
3291 /* Ensure that the freelist is at full capacity. */
3293 xfs_free_extent_fix_freelist(
3294 struct xfs_trans *tp,
3295 struct xfs_perag *pag,
3296 struct xfs_buf **agbp)
3298 struct xfs_alloc_arg args;
3301 memset(&args, 0, sizeof(struct xfs_alloc_arg));
3303 args.mp = tp->t_mountp;
3304 args.agno = pag->pag_agno;
3308 * validate that the block number is legal - the enables us to detect
3309 * and handle a silent filesystem corruption rather than crashing.
3311 if (args.agno >= args.mp->m_sb.sb_agcount)
3312 return -EFSCORRUPTED;
3314 error = xfs_alloc_fix_freelist(&args, XFS_ALLOC_FLAG_FREEING);
3324 * Just break up the extent address and hand off to xfs_free_ag_extent
3325 * after fixing up the freelist.
3329 struct xfs_trans *tp,
3332 const struct xfs_owner_info *oinfo,
3333 enum xfs_ag_resv_type type,
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;
3342 unsigned int busy_flags = 0;
3343 struct xfs_perag *pag;
3346 ASSERT(type != XFS_AG_RESV_AGFL);
3348 if (XFS_TEST_ERROR(false, mp,
3349 XFS_ERRTAG_FREE_EXTENT))
3352 pag = xfs_perag_get(mp, agno);
3353 error = xfs_free_extent_fix_freelist(tp, pag, &agbp);
3358 if (XFS_IS_CORRUPT(mp, agbno >= mp->m_sb.sb_agblocks)) {
3359 error = -EFSCORRUPTED;
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;
3369 error = xfs_free_ag_extent(tp, agbp, agno, agbno, len, oinfo, type);
3374 busy_flags |= XFS_EXTENT_BUSY_SKIP_DISCARD;
3375 xfs_extent_busy_insert(tp, pag, agbno, len, busy_flags);
3380 xfs_trans_brelse(tp, agbp);
3386 struct xfs_alloc_query_range_info {
3387 xfs_alloc_query_range_fn fn;
3391 /* Format btree record and pass to our callback. */
3393 xfs_alloc_query_range_helper(
3394 struct xfs_btree_cur *cur,
3395 union xfs_btree_rec *rec,
3398 struct xfs_alloc_query_range_info *query = priv;
3399 struct xfs_alloc_rec_incore irec;
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);
3406 /* Find all free space within a given range of blocks. */
3408 xfs_alloc_query_range(
3409 struct xfs_btree_cur *cur,
3410 struct xfs_alloc_rec_incore *low_rec,
3411 struct xfs_alloc_rec_incore *high_rec,
3412 xfs_alloc_query_range_fn fn,
3415 union xfs_btree_irec low_brec;
3416 union xfs_btree_irec high_brec;
3417 struct xfs_alloc_query_range_info query;
3419 ASSERT(cur->bc_btnum == XFS_BTNUM_BNO);
3420 low_brec.a = *low_rec;
3421 high_brec.a = *high_rec;
3424 return xfs_btree_query_range(cur, &low_brec, &high_brec,
3425 xfs_alloc_query_range_helper, &query);
3428 /* Find all free space records. */
3430 xfs_alloc_query_all(
3431 struct xfs_btree_cur *cur,
3432 xfs_alloc_query_range_fn fn,
3435 struct xfs_alloc_query_range_info query;
3437 ASSERT(cur->bc_btnum == XFS_BTNUM_BNO);
3440 return xfs_btree_query_all(cur, xfs_alloc_query_range_helper, &query);
3443 /* Is there a record covering a given extent? */
3445 xfs_alloc_has_record(
3446 struct xfs_btree_cur *cur,
3451 union xfs_btree_irec low;
3452 union xfs_btree_irec high;
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;
3459 return xfs_btree_has_record(cur, &low, &high, exists);
3463 * Walk all the blocks in the AGFL. The @walk_fn can return any negative
3464 * error code or XFS_ITER_*.
3468 struct xfs_mount *mp,
3469 struct xfs_agf *agf,
3470 struct xfs_buf *agflbp,
3471 xfs_agfl_walk_fn walk_fn,
3478 agfl_bno = xfs_buf_to_agfl_bno(agflbp);
3479 i = be32_to_cpu(agf->agf_flfirst);
3481 /* Nothing to walk in an empty AGFL. */
3482 if (agf->agf_flcount == cpu_to_be32(0))
3485 /* Otherwise, walk from first to last, wrapping as needed. */
3487 error = walk_fn(mp, be32_to_cpu(agfl_bno[i]), priv);
3490 if (i == be32_to_cpu(agf->agf_fllast))
3492 if (++i == xfs_agfl_size(mp))