1 // SPDX-License-Identifier: GPL-2.0
3 * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc.
6 #include "libxfs_priv.h"
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_errortag.h"
20 #include "xfs_trace.h"
21 #include "xfs_trans.h"
23 #include "xfs_ag_resv.h"
26 struct kmem_cache
*xfs_extfree_item_cache
;
28 struct workqueue_struct
*xfs_alloc_wq
;
30 #define XFS_ABSDIFF(a,b) (((a) <= (b)) ? ((b) - (a)) : ((a) - (b)))
32 #define XFSA_FIXUP_BNO_OK 1
33 #define XFSA_FIXUP_CNT_OK 2
36 * Size of the AGFL. For CRC-enabled filesystes we steal a couple of slots in
37 * the beginning of the block for a proper header with the location information
44 unsigned int size
= mp
->m_sb
.sb_sectsize
;
47 size
-= sizeof(struct xfs_agfl
);
49 return size
/ sizeof(xfs_agblock_t
);
56 if (xfs_has_rmapbt(mp
))
57 return XFS_RMAP_BLOCK(mp
) + 1;
58 if (xfs_has_finobt(mp
))
59 return XFS_FIBT_BLOCK(mp
) + 1;
60 return XFS_IBT_BLOCK(mp
) + 1;
67 if (xfs_has_reflink(mp
))
68 return xfs_refc_block(mp
) + 1;
69 if (xfs_has_rmapbt(mp
))
70 return XFS_RMAP_BLOCK(mp
) + 1;
71 if (xfs_has_finobt(mp
))
72 return XFS_FIBT_BLOCK(mp
) + 1;
73 return XFS_IBT_BLOCK(mp
) + 1;
77 * The number of blocks per AG that we withhold from xfs_mod_fdblocks to
78 * guarantee that we can refill the AGFL prior to allocating space in a nearly
79 * full AG. Although the space described by the free space btrees, the
80 * blocks used by the freesp btrees themselves, and the blocks owned by the
81 * AGFL are counted in the ondisk fdblocks, it's a mistake to let the ondisk
82 * free space in the AG drop so low that the free space btrees cannot refill an
83 * empty AGFL up to the minimum level. Rather than grind through empty AGs
84 * until the fs goes down, we subtract this many AG blocks from the incore
85 * fdblocks to ensure user allocation does not overcommit the space the
86 * filesystem needs for the AGFLs. The rmap btree uses a per-AG reservation to
87 * withhold space from xfs_mod_fdblocks, so we do not account for that here.
89 #define XFS_ALLOCBT_AGFL_RESERVE 4
92 * Compute the number of blocks that we set aside to guarantee the ability to
93 * refill the AGFL and handle a full bmap btree split.
95 * In order to avoid ENOSPC-related deadlock caused by out-of-order locking of
96 * AGF buffer (PV 947395), we place constraints on the relationship among
97 * actual allocations for data blocks, freelist blocks, and potential file data
98 * bmap btree blocks. However, these restrictions may result in no actual space
99 * allocated for a delayed extent, for example, a data block in a certain AG is
100 * allocated but there is no additional block for the additional bmap btree
101 * block due to a split of the bmap btree of the file. The result of this may
102 * lead to an infinite loop when the file gets flushed to disk and all delayed
103 * extents need to be actually allocated. To get around this, we explicitly set
104 * aside a few blocks which will not be reserved in delayed allocation.
106 * For each AG, we need to reserve enough blocks to replenish a totally empty
107 * AGFL and 4 more to handle a potential split of the file's bmap btree.
111 struct xfs_mount
*mp
)
113 return mp
->m_sb
.sb_agcount
* (XFS_ALLOCBT_AGFL_RESERVE
+ 4);
117 * When deciding how much space to allocate out of an AG, we limit the
118 * allocation maximum size to the size the AG. However, we cannot use all the
119 * blocks in the AG - some are permanently used by metadata. These
120 * blocks are generally:
121 * - the AG superblock, AGF, AGI and AGFL
122 * - the AGF (bno and cnt) and AGI btree root blocks, and optionally
123 * the AGI free inode and rmap btree root blocks.
124 * - blocks on the AGFL according to xfs_alloc_set_aside() limits
125 * - the rmapbt root block
127 * The AG headers are sector sized, so the amount of space they take up is
128 * dependent on filesystem geometry. The others are all single blocks.
131 xfs_alloc_ag_max_usable(
132 struct xfs_mount
*mp
)
136 blocks
= XFS_BB_TO_FSB(mp
, XFS_FSS_TO_BB(mp
, 4)); /* ag headers */
137 blocks
+= XFS_ALLOCBT_AGFL_RESERVE
;
138 blocks
+= 3; /* AGF, AGI btree root blocks */
139 if (xfs_has_finobt(mp
))
140 blocks
++; /* finobt root block */
141 if (xfs_has_rmapbt(mp
))
142 blocks
++; /* rmap root block */
143 if (xfs_has_reflink(mp
))
144 blocks
++; /* refcount root block */
146 return mp
->m_sb
.sb_agblocks
- blocks
;
150 * Lookup the record equal to [bno, len] in the btree given by cur.
152 STATIC
int /* error */
154 struct xfs_btree_cur
*cur
, /* btree cursor */
155 xfs_agblock_t bno
, /* starting block of extent */
156 xfs_extlen_t len
, /* length of extent */
157 int *stat
) /* success/failure */
161 cur
->bc_rec
.a
.ar_startblock
= bno
;
162 cur
->bc_rec
.a
.ar_blockcount
= len
;
163 error
= xfs_btree_lookup(cur
, XFS_LOOKUP_EQ
, stat
);
164 cur
->bc_ag
.abt
.active
= (*stat
== 1);
169 * Lookup the first record greater than or equal to [bno, len]
170 * in the btree given by cur.
174 struct xfs_btree_cur
*cur
, /* btree cursor */
175 xfs_agblock_t bno
, /* starting block of extent */
176 xfs_extlen_t len
, /* length of extent */
177 int *stat
) /* success/failure */
181 cur
->bc_rec
.a
.ar_startblock
= bno
;
182 cur
->bc_rec
.a
.ar_blockcount
= len
;
183 error
= xfs_btree_lookup(cur
, XFS_LOOKUP_GE
, stat
);
184 cur
->bc_ag
.abt
.active
= (*stat
== 1);
189 * Lookup the first record less than or equal to [bno, len]
190 * in the btree given by cur.
194 struct xfs_btree_cur
*cur
, /* btree cursor */
195 xfs_agblock_t bno
, /* starting block of extent */
196 xfs_extlen_t len
, /* length of extent */
197 int *stat
) /* success/failure */
200 cur
->bc_rec
.a
.ar_startblock
= bno
;
201 cur
->bc_rec
.a
.ar_blockcount
= len
;
202 error
= xfs_btree_lookup(cur
, XFS_LOOKUP_LE
, stat
);
203 cur
->bc_ag
.abt
.active
= (*stat
== 1);
208 xfs_alloc_cur_active(
209 struct xfs_btree_cur
*cur
)
211 return cur
&& cur
->bc_ag
.abt
.active
;
215 * Update the record referred to by cur to the value given
217 * This either works (return 0) or gets an EFSCORRUPTED error.
219 STATIC
int /* error */
221 struct xfs_btree_cur
*cur
, /* btree cursor */
222 xfs_agblock_t bno
, /* starting block of extent */
223 xfs_extlen_t len
) /* length of extent */
225 union xfs_btree_rec rec
;
227 rec
.alloc
.ar_startblock
= cpu_to_be32(bno
);
228 rec
.alloc
.ar_blockcount
= cpu_to_be32(len
);
229 return xfs_btree_update(cur
, &rec
);
232 /* Convert the ondisk btree record to its incore representation. */
234 xfs_alloc_btrec_to_irec(
235 const union xfs_btree_rec
*rec
,
236 struct xfs_alloc_rec_incore
*irec
)
238 irec
->ar_startblock
= be32_to_cpu(rec
->alloc
.ar_startblock
);
239 irec
->ar_blockcount
= be32_to_cpu(rec
->alloc
.ar_blockcount
);
242 /* Simple checks for free space records. */
244 xfs_alloc_check_irec(
245 struct xfs_btree_cur
*cur
,
246 const struct xfs_alloc_rec_incore
*irec
)
248 struct xfs_perag
*pag
= cur
->bc_ag
.pag
;
250 if (irec
->ar_blockcount
== 0)
251 return __this_address
;
253 /* check for valid extent range, including overflow */
254 if (!xfs_verify_agbext(pag
, irec
->ar_startblock
, irec
->ar_blockcount
))
255 return __this_address
;
261 xfs_alloc_complain_bad_rec(
262 struct xfs_btree_cur
*cur
,
264 const struct xfs_alloc_rec_incore
*irec
)
266 struct xfs_mount
*mp
= cur
->bc_mp
;
269 "%s Freespace BTree record corruption in AG %d detected at %pS!",
270 cur
->bc_btnum
== XFS_BTNUM_BNO
? "Block" : "Size",
271 cur
->bc_ag
.pag
->pag_agno
, fa
);
273 "start block 0x%x block count 0x%x", irec
->ar_startblock
,
274 irec
->ar_blockcount
);
275 return -EFSCORRUPTED
;
279 * Get the data from the pointed-to record.
283 struct xfs_btree_cur
*cur
, /* btree cursor */
284 xfs_agblock_t
*bno
, /* output: starting block of extent */
285 xfs_extlen_t
*len
, /* output: length of extent */
286 int *stat
) /* output: success/failure */
288 struct xfs_alloc_rec_incore irec
;
289 union xfs_btree_rec
*rec
;
293 error
= xfs_btree_get_rec(cur
, &rec
, stat
);
294 if (error
|| !(*stat
))
297 xfs_alloc_btrec_to_irec(rec
, &irec
);
298 fa
= xfs_alloc_check_irec(cur
, &irec
);
300 return xfs_alloc_complain_bad_rec(cur
, fa
, &irec
);
302 *bno
= irec
.ar_startblock
;
303 *len
= irec
.ar_blockcount
;
308 * Compute aligned version of the found extent.
309 * Takes alignment and min length into account.
312 xfs_alloc_compute_aligned(
313 xfs_alloc_arg_t
*args
, /* allocation argument structure */
314 xfs_agblock_t foundbno
, /* starting block in found extent */
315 xfs_extlen_t foundlen
, /* length in found extent */
316 xfs_agblock_t
*resbno
, /* result block number */
317 xfs_extlen_t
*reslen
, /* result length */
320 xfs_agblock_t bno
= foundbno
;
321 xfs_extlen_t len
= foundlen
;
325 /* Trim busy sections out of found extent */
326 busy
= xfs_extent_busy_trim(args
, &bno
, &len
, busy_gen
);
329 * If we have a largish extent that happens to start before min_agbno,
330 * see if we can shift it into range...
332 if (bno
< args
->min_agbno
&& bno
+ len
> args
->min_agbno
) {
333 diff
= args
->min_agbno
- bno
;
340 if (args
->alignment
> 1 && len
>= args
->minlen
) {
341 xfs_agblock_t aligned_bno
= roundup(bno
, args
->alignment
);
343 diff
= aligned_bno
- bno
;
345 *resbno
= aligned_bno
;
346 *reslen
= diff
>= len
? 0 : len
- diff
;
356 * Compute best start block and diff for "near" allocations.
357 * freelen >= wantlen already checked by caller.
359 STATIC xfs_extlen_t
/* difference value (absolute) */
360 xfs_alloc_compute_diff(
361 xfs_agblock_t wantbno
, /* target starting block */
362 xfs_extlen_t wantlen
, /* target length */
363 xfs_extlen_t alignment
, /* target alignment */
364 int datatype
, /* are we allocating data? */
365 xfs_agblock_t freebno
, /* freespace's starting block */
366 xfs_extlen_t freelen
, /* freespace's length */
367 xfs_agblock_t
*newbnop
) /* result: best start block from free */
369 xfs_agblock_t freeend
; /* end of freespace extent */
370 xfs_agblock_t newbno1
; /* return block number */
371 xfs_agblock_t newbno2
; /* other new block number */
372 xfs_extlen_t newlen1
=0; /* length with newbno1 */
373 xfs_extlen_t newlen2
=0; /* length with newbno2 */
374 xfs_agblock_t wantend
; /* end of target extent */
375 bool userdata
= datatype
& XFS_ALLOC_USERDATA
;
377 ASSERT(freelen
>= wantlen
);
378 freeend
= freebno
+ freelen
;
379 wantend
= wantbno
+ wantlen
;
381 * We want to allocate from the start of a free extent if it is past
382 * the desired block or if we are allocating user data and the free
383 * extent is before desired block. The second case is there to allow
384 * for contiguous allocation from the remaining free space if the file
385 * grows in the short term.
387 if (freebno
>= wantbno
|| (userdata
&& freeend
< wantend
)) {
388 if ((newbno1
= roundup(freebno
, alignment
)) >= freeend
)
389 newbno1
= NULLAGBLOCK
;
390 } else if (freeend
>= wantend
&& alignment
> 1) {
391 newbno1
= roundup(wantbno
, alignment
);
392 newbno2
= newbno1
- alignment
;
393 if (newbno1
>= freeend
)
394 newbno1
= NULLAGBLOCK
;
396 newlen1
= XFS_EXTLEN_MIN(wantlen
, freeend
- newbno1
);
397 if (newbno2
< freebno
)
398 newbno2
= NULLAGBLOCK
;
400 newlen2
= XFS_EXTLEN_MIN(wantlen
, freeend
- newbno2
);
401 if (newbno1
!= NULLAGBLOCK
&& newbno2
!= NULLAGBLOCK
) {
402 if (newlen1
< newlen2
||
403 (newlen1
== newlen2
&&
404 XFS_ABSDIFF(newbno1
, wantbno
) >
405 XFS_ABSDIFF(newbno2
, wantbno
)))
407 } else if (newbno2
!= NULLAGBLOCK
)
409 } else if (freeend
>= wantend
) {
411 } else if (alignment
> 1) {
412 newbno1
= roundup(freeend
- wantlen
, alignment
);
413 if (newbno1
> freeend
- wantlen
&&
414 newbno1
- alignment
>= freebno
)
415 newbno1
-= alignment
;
416 else if (newbno1
>= freeend
)
417 newbno1
= NULLAGBLOCK
;
419 newbno1
= freeend
- wantlen
;
421 return newbno1
== NULLAGBLOCK
? 0 : XFS_ABSDIFF(newbno1
, wantbno
);
425 * Fix up the length, based on mod and prod.
426 * len should be k * prod + mod for some k.
427 * If len is too small it is returned unchanged.
428 * If len hits maxlen it is left alone.
432 xfs_alloc_arg_t
*args
) /* allocation argument structure */
437 ASSERT(args
->mod
< args
->prod
);
439 ASSERT(rlen
>= args
->minlen
);
440 ASSERT(rlen
<= args
->maxlen
);
441 if (args
->prod
<= 1 || rlen
< args
->mod
|| rlen
== args
->maxlen
||
442 (args
->mod
== 0 && rlen
< args
->prod
))
444 k
= rlen
% args
->prod
;
448 rlen
= rlen
- (k
- args
->mod
);
450 rlen
= rlen
- args
->prod
+ (args
->mod
- k
);
451 /* casts to (int) catch length underflows */
452 if ((int)rlen
< (int)args
->minlen
)
454 ASSERT(rlen
>= args
->minlen
&& rlen
<= args
->maxlen
);
455 ASSERT(rlen
% args
->prod
== args
->mod
);
456 ASSERT(args
->pag
->pagf_freeblks
+ args
->pag
->pagf_flcount
>=
457 rlen
+ args
->minleft
);
462 * Update the two btrees, logically removing from freespace the extent
463 * starting at rbno, rlen blocks. The extent is contained within the
464 * actual (current) free extent fbno for flen blocks.
465 * Flags are passed in indicating whether the cursors are set to the
468 STATIC
int /* error code */
469 xfs_alloc_fixup_trees(
470 struct xfs_btree_cur
*cnt_cur
, /* cursor for by-size btree */
471 struct xfs_btree_cur
*bno_cur
, /* cursor for by-block btree */
472 xfs_agblock_t fbno
, /* starting block of free extent */
473 xfs_extlen_t flen
, /* length of free extent */
474 xfs_agblock_t rbno
, /* starting block of returned extent */
475 xfs_extlen_t rlen
, /* length of returned extent */
476 int flags
) /* flags, XFSA_FIXUP_... */
478 int error
; /* error code */
479 int i
; /* operation results */
480 xfs_agblock_t nfbno1
; /* first new free startblock */
481 xfs_agblock_t nfbno2
; /* second new free startblock */
482 xfs_extlen_t nflen1
=0; /* first new free length */
483 xfs_extlen_t nflen2
=0; /* second new free length */
484 struct xfs_mount
*mp
;
489 * Look up the record in the by-size tree if necessary.
491 if (flags
& XFSA_FIXUP_CNT_OK
) {
493 if ((error
= xfs_alloc_get_rec(cnt_cur
, &nfbno1
, &nflen1
, &i
)))
495 if (XFS_IS_CORRUPT(mp
,
499 return -EFSCORRUPTED
;
502 if ((error
= xfs_alloc_lookup_eq(cnt_cur
, fbno
, flen
, &i
)))
504 if (XFS_IS_CORRUPT(mp
, i
!= 1))
505 return -EFSCORRUPTED
;
508 * Look up the record in the by-block tree if necessary.
510 if (flags
& XFSA_FIXUP_BNO_OK
) {
512 if ((error
= xfs_alloc_get_rec(bno_cur
, &nfbno1
, &nflen1
, &i
)))
514 if (XFS_IS_CORRUPT(mp
,
518 return -EFSCORRUPTED
;
521 if ((error
= xfs_alloc_lookup_eq(bno_cur
, fbno
, flen
, &i
)))
523 if (XFS_IS_CORRUPT(mp
, i
!= 1))
524 return -EFSCORRUPTED
;
528 if (bno_cur
->bc_nlevels
== 1 && cnt_cur
->bc_nlevels
== 1) {
529 struct xfs_btree_block
*bnoblock
;
530 struct xfs_btree_block
*cntblock
;
532 bnoblock
= XFS_BUF_TO_BLOCK(bno_cur
->bc_levels
[0].bp
);
533 cntblock
= XFS_BUF_TO_BLOCK(cnt_cur
->bc_levels
[0].bp
);
535 if (XFS_IS_CORRUPT(mp
,
536 bnoblock
->bb_numrecs
!=
537 cntblock
->bb_numrecs
))
538 return -EFSCORRUPTED
;
543 * Deal with all four cases: the allocated record is contained
544 * within the freespace record, so we can have new freespace
545 * at either (or both) end, or no freespace remaining.
547 if (rbno
== fbno
&& rlen
== flen
)
548 nfbno1
= nfbno2
= NULLAGBLOCK
;
549 else if (rbno
== fbno
) {
550 nfbno1
= rbno
+ rlen
;
551 nflen1
= flen
- rlen
;
552 nfbno2
= NULLAGBLOCK
;
553 } else if (rbno
+ rlen
== fbno
+ flen
) {
555 nflen1
= flen
- rlen
;
556 nfbno2
= NULLAGBLOCK
;
559 nflen1
= rbno
- fbno
;
560 nfbno2
= rbno
+ rlen
;
561 nflen2
= (fbno
+ flen
) - nfbno2
;
564 * Delete the entry from the by-size btree.
566 if ((error
= xfs_btree_delete(cnt_cur
, &i
)))
568 if (XFS_IS_CORRUPT(mp
, i
!= 1))
569 return -EFSCORRUPTED
;
571 * Add new by-size btree entry(s).
573 if (nfbno1
!= NULLAGBLOCK
) {
574 if ((error
= xfs_alloc_lookup_eq(cnt_cur
, nfbno1
, nflen1
, &i
)))
576 if (XFS_IS_CORRUPT(mp
, i
!= 0))
577 return -EFSCORRUPTED
;
578 if ((error
= xfs_btree_insert(cnt_cur
, &i
)))
580 if (XFS_IS_CORRUPT(mp
, i
!= 1))
581 return -EFSCORRUPTED
;
583 if (nfbno2
!= NULLAGBLOCK
) {
584 if ((error
= xfs_alloc_lookup_eq(cnt_cur
, nfbno2
, nflen2
, &i
)))
586 if (XFS_IS_CORRUPT(mp
, i
!= 0))
587 return -EFSCORRUPTED
;
588 if ((error
= xfs_btree_insert(cnt_cur
, &i
)))
590 if (XFS_IS_CORRUPT(mp
, i
!= 1))
591 return -EFSCORRUPTED
;
594 * Fix up the by-block btree entry(s).
596 if (nfbno1
== NULLAGBLOCK
) {
598 * No remaining freespace, just delete the by-block tree entry.
600 if ((error
= xfs_btree_delete(bno_cur
, &i
)))
602 if (XFS_IS_CORRUPT(mp
, i
!= 1))
603 return -EFSCORRUPTED
;
606 * Update the by-block entry to start later|be shorter.
608 if ((error
= xfs_alloc_update(bno_cur
, nfbno1
, nflen1
)))
611 if (nfbno2
!= NULLAGBLOCK
) {
613 * 2 resulting free entries, need to add one.
615 if ((error
= xfs_alloc_lookup_eq(bno_cur
, nfbno2
, nflen2
, &i
)))
617 if (XFS_IS_CORRUPT(mp
, i
!= 0))
618 return -EFSCORRUPTED
;
619 if ((error
= xfs_btree_insert(bno_cur
, &i
)))
621 if (XFS_IS_CORRUPT(mp
, i
!= 1))
622 return -EFSCORRUPTED
;
627 static xfs_failaddr_t
631 struct xfs_mount
*mp
= bp
->b_mount
;
632 struct xfs_agfl
*agfl
= XFS_BUF_TO_AGFL(bp
);
633 __be32
*agfl_bno
= xfs_buf_to_agfl_bno(bp
);
637 * There is no verification of non-crc AGFLs because mkfs does not
638 * initialise the AGFL to zero or NULL. Hence the only valid part of the
639 * AGFL is what the AGF says is active. We can't get to the AGF, so we
640 * can't verify just those entries are valid.
642 if (!xfs_has_crc(mp
))
645 if (!xfs_verify_magic(bp
, agfl
->agfl_magicnum
))
646 return __this_address
;
647 if (!uuid_equal(&agfl
->agfl_uuid
, &mp
->m_sb
.sb_meta_uuid
))
648 return __this_address
;
650 * during growfs operations, the perag is not fully initialised,
651 * so we can't use it for any useful checking. growfs ensures we can't
652 * use it by using uncached buffers that don't have the perag attached
653 * so we can detect and avoid this problem.
655 if (bp
->b_pag
&& be32_to_cpu(agfl
->agfl_seqno
) != bp
->b_pag
->pag_agno
)
656 return __this_address
;
658 for (i
= 0; i
< xfs_agfl_size(mp
); i
++) {
659 if (be32_to_cpu(agfl_bno
[i
]) != NULLAGBLOCK
&&
660 be32_to_cpu(agfl_bno
[i
]) >= mp
->m_sb
.sb_agblocks
)
661 return __this_address
;
664 if (!xfs_log_check_lsn(mp
, be64_to_cpu(XFS_BUF_TO_AGFL(bp
)->agfl_lsn
)))
665 return __this_address
;
670 xfs_agfl_read_verify(
673 struct xfs_mount
*mp
= bp
->b_mount
;
677 * There is no verification of non-crc AGFLs because mkfs does not
678 * initialise the AGFL to zero or NULL. Hence the only valid part of the
679 * AGFL is what the AGF says is active. We can't get to the AGF, so we
680 * can't verify just those entries are valid.
682 if (!xfs_has_crc(mp
))
685 if (!xfs_buf_verify_cksum(bp
, XFS_AGFL_CRC_OFF
))
686 xfs_verifier_error(bp
, -EFSBADCRC
, __this_address
);
688 fa
= xfs_agfl_verify(bp
);
690 xfs_verifier_error(bp
, -EFSCORRUPTED
, fa
);
695 xfs_agfl_write_verify(
698 struct xfs_mount
*mp
= bp
->b_mount
;
699 struct xfs_buf_log_item
*bip
= bp
->b_log_item
;
702 /* no verification of non-crc AGFLs */
703 if (!xfs_has_crc(mp
))
706 fa
= xfs_agfl_verify(bp
);
708 xfs_verifier_error(bp
, -EFSCORRUPTED
, fa
);
713 XFS_BUF_TO_AGFL(bp
)->agfl_lsn
= cpu_to_be64(bip
->bli_item
.li_lsn
);
715 xfs_buf_update_cksum(bp
, XFS_AGFL_CRC_OFF
);
718 const struct xfs_buf_ops xfs_agfl_buf_ops
= {
720 .magic
= { cpu_to_be32(XFS_AGFL_MAGIC
), cpu_to_be32(XFS_AGFL_MAGIC
) },
721 .verify_read
= xfs_agfl_read_verify
,
722 .verify_write
= xfs_agfl_write_verify
,
723 .verify_struct
= xfs_agfl_verify
,
727 * Read in the allocation group free block array.
731 struct xfs_perag
*pag
,
732 struct xfs_trans
*tp
,
733 struct xfs_buf
**bpp
)
735 struct xfs_mount
*mp
= pag
->pag_mount
;
739 error
= xfs_trans_read_buf(
740 mp
, tp
, mp
->m_ddev_targp
,
741 XFS_AG_DADDR(mp
, pag
->pag_agno
, XFS_AGFL_DADDR(mp
)),
742 XFS_FSS_TO_BB(mp
, 1), 0, &bp
, &xfs_agfl_buf_ops
);
745 xfs_buf_set_ref(bp
, XFS_AGFL_REF
);
751 xfs_alloc_update_counters(
752 struct xfs_trans
*tp
,
753 struct xfs_buf
*agbp
,
756 struct xfs_agf
*agf
= agbp
->b_addr
;
758 agbp
->b_pag
->pagf_freeblks
+= len
;
759 be32_add_cpu(&agf
->agf_freeblks
, len
);
761 if (unlikely(be32_to_cpu(agf
->agf_freeblks
) >
762 be32_to_cpu(agf
->agf_length
))) {
763 xfs_buf_mark_corrupt(agbp
);
764 return -EFSCORRUPTED
;
767 xfs_alloc_log_agf(tp
, agbp
, XFS_AGF_FREEBLKS
);
772 * Block allocation algorithm and data structures.
774 struct xfs_alloc_cur
{
775 struct xfs_btree_cur
*cnt
; /* btree cursors */
776 struct xfs_btree_cur
*bnolt
;
777 struct xfs_btree_cur
*bnogt
;
778 xfs_extlen_t cur_len
;/* current search length */
779 xfs_agblock_t rec_bno
;/* extent startblock */
780 xfs_extlen_t rec_len
;/* extent length */
781 xfs_agblock_t bno
; /* alloc bno */
782 xfs_extlen_t len
; /* alloc len */
783 xfs_extlen_t diff
; /* diff from search bno */
784 unsigned int busy_gen
;/* busy state */
789 * Set up cursors, etc. in the extent allocation cursor. This function can be
790 * called multiple times to reset an initialized structure without having to
791 * reallocate cursors.
795 struct xfs_alloc_arg
*args
,
796 struct xfs_alloc_cur
*acur
)
801 acur
->cur_len
= args
->maxlen
;
811 * Perform an initial cntbt lookup to check for availability of maxlen
812 * extents. If this fails, we'll return -ENOSPC to signal the caller to
813 * attempt a small allocation.
816 acur
->cnt
= xfs_allocbt_init_cursor(args
->mp
, args
->tp
,
817 args
->agbp
, args
->pag
, XFS_BTNUM_CNT
);
818 error
= xfs_alloc_lookup_ge(acur
->cnt
, 0, args
->maxlen
, &i
);
823 * Allocate the bnobt left and right search cursors.
826 acur
->bnolt
= xfs_allocbt_init_cursor(args
->mp
, args
->tp
,
827 args
->agbp
, args
->pag
, XFS_BTNUM_BNO
);
829 acur
->bnogt
= xfs_allocbt_init_cursor(args
->mp
, args
->tp
,
830 args
->agbp
, args
->pag
, XFS_BTNUM_BNO
);
831 return i
== 1 ? 0 : -ENOSPC
;
836 struct xfs_alloc_cur
*acur
,
839 int cur_error
= XFS_BTREE_NOERROR
;
842 cur_error
= XFS_BTREE_ERROR
;
845 xfs_btree_del_cursor(acur
->cnt
, cur_error
);
847 xfs_btree_del_cursor(acur
->bnolt
, cur_error
);
849 xfs_btree_del_cursor(acur
->bnogt
, cur_error
);
850 acur
->cnt
= acur
->bnolt
= acur
->bnogt
= NULL
;
854 * Check an extent for allocation and track the best available candidate in the
855 * allocation structure. The cursor is deactivated if it has entered an out of
856 * range state based on allocation arguments. Optionally return the extent
857 * extent geometry and allocation status if requested by the caller.
861 struct xfs_alloc_arg
*args
,
862 struct xfs_alloc_cur
*acur
,
863 struct xfs_btree_cur
*cur
,
867 xfs_agblock_t bno
, bnoa
, bnew
;
868 xfs_extlen_t len
, lena
, diff
= -1;
870 unsigned busy_gen
= 0;
871 bool deactivate
= false;
872 bool isbnobt
= cur
->bc_btnum
== XFS_BTNUM_BNO
;
876 error
= xfs_alloc_get_rec(cur
, &bno
, &len
, &i
);
879 if (XFS_IS_CORRUPT(args
->mp
, i
!= 1))
880 return -EFSCORRUPTED
;
883 * Check minlen and deactivate a cntbt cursor if out of acceptable size
884 * range (i.e., walking backwards looking for a minlen extent).
886 if (len
< args
->minlen
) {
887 deactivate
= !isbnobt
;
891 busy
= xfs_alloc_compute_aligned(args
, bno
, len
, &bnoa
, &lena
,
895 acur
->busy_gen
= busy_gen
;
896 /* deactivate a bnobt cursor outside of locality range */
897 if (bnoa
< args
->min_agbno
|| bnoa
> args
->max_agbno
) {
898 deactivate
= isbnobt
;
901 if (lena
< args
->minlen
)
904 args
->len
= XFS_EXTLEN_MIN(lena
, args
->maxlen
);
905 xfs_alloc_fix_len(args
);
906 ASSERT(args
->len
>= args
->minlen
);
907 if (args
->len
< acur
->len
)
911 * We have an aligned record that satisfies minlen and beats or matches
912 * the candidate extent size. Compare locality for near allocation mode.
914 diff
= xfs_alloc_compute_diff(args
->agbno
, args
->len
,
915 args
->alignment
, args
->datatype
,
917 if (bnew
== NULLAGBLOCK
)
921 * Deactivate a bnobt cursor with worse locality than the current best.
923 if (diff
> acur
->diff
) {
924 deactivate
= isbnobt
;
928 ASSERT(args
->len
> acur
->len
||
929 (args
->len
== acur
->len
&& diff
<= acur
->diff
));
933 acur
->len
= args
->len
;
938 * We're done if we found a perfect allocation. This only deactivates
939 * the current cursor, but this is just an optimization to terminate a
940 * cntbt search that otherwise runs to the edge of the tree.
942 if (acur
->diff
== 0 && acur
->len
== args
->maxlen
)
946 cur
->bc_ag
.abt
.active
= false;
947 trace_xfs_alloc_cur_check(args
->mp
, cur
->bc_btnum
, bno
, len
, diff
,
953 * Complete an allocation of a candidate extent. Remove the extent from both
954 * trees and update the args structure.
957 xfs_alloc_cur_finish(
958 struct xfs_alloc_arg
*args
,
959 struct xfs_alloc_cur
*acur
)
961 struct xfs_agf __maybe_unused
*agf
= args
->agbp
->b_addr
;
964 ASSERT(acur
->cnt
&& acur
->bnolt
);
965 ASSERT(acur
->bno
>= acur
->rec_bno
);
966 ASSERT(acur
->bno
+ acur
->len
<= acur
->rec_bno
+ acur
->rec_len
);
967 ASSERT(acur
->rec_bno
+ acur
->rec_len
<= be32_to_cpu(agf
->agf_length
));
969 error
= xfs_alloc_fixup_trees(acur
->cnt
, acur
->bnolt
, acur
->rec_bno
,
970 acur
->rec_len
, acur
->bno
, acur
->len
, 0);
974 args
->agbno
= acur
->bno
;
975 args
->len
= acur
->len
;
978 trace_xfs_alloc_cur(args
);
983 * Locality allocation lookup algorithm. This expects a cntbt cursor and uses
984 * bno optimized lookup to search for extents with ideal size and locality.
987 xfs_alloc_cntbt_iter(
988 struct xfs_alloc_arg
*args
,
989 struct xfs_alloc_cur
*acur
)
991 struct xfs_btree_cur
*cur
= acur
->cnt
;
993 xfs_extlen_t len
, cur_len
;
997 if (!xfs_alloc_cur_active(cur
))
1000 /* locality optimized lookup */
1001 cur_len
= acur
->cur_len
;
1002 error
= xfs_alloc_lookup_ge(cur
, args
->agbno
, cur_len
, &i
);
1007 error
= xfs_alloc_get_rec(cur
, &bno
, &len
, &i
);
1011 /* check the current record and update search length from it */
1012 error
= xfs_alloc_cur_check(args
, acur
, cur
, &i
);
1015 ASSERT(len
>= acur
->cur_len
);
1016 acur
->cur_len
= len
;
1019 * We looked up the first record >= [agbno, len] above. The agbno is a
1020 * secondary key and so the current record may lie just before or after
1021 * agbno. If it is past agbno, check the previous record too so long as
1022 * the length matches as it may be closer. Don't check a smaller record
1023 * because that could deactivate our cursor.
1025 if (bno
> args
->agbno
) {
1026 error
= xfs_btree_decrement(cur
, 0, &i
);
1028 error
= xfs_alloc_get_rec(cur
, &bno
, &len
, &i
);
1029 if (!error
&& i
&& len
== acur
->cur_len
)
1030 error
= xfs_alloc_cur_check(args
, acur
, cur
,
1038 * Increment the search key until we find at least one allocation
1039 * candidate or if the extent we found was larger. Otherwise, double the
1040 * search key to optimize the search. Efficiency is more important here
1041 * than absolute best locality.
1044 if (!acur
->len
|| acur
->cur_len
>= cur_len
)
1047 acur
->cur_len
= cur_len
;
1053 * Deal with the case where only small freespaces remain. Either return the
1054 * contents of the last freespace record, or allocate space from the freelist if
1055 * there is nothing in the tree.
1057 STATIC
int /* error */
1058 xfs_alloc_ag_vextent_small(
1059 struct xfs_alloc_arg
*args
, /* allocation argument structure */
1060 struct xfs_btree_cur
*ccur
, /* optional by-size cursor */
1061 xfs_agblock_t
*fbnop
, /* result block number */
1062 xfs_extlen_t
*flenp
, /* result length */
1063 int *stat
) /* status: 0-freelist, 1-normal/none */
1065 struct xfs_agf
*agf
= args
->agbp
->b_addr
;
1067 xfs_agblock_t fbno
= NULLAGBLOCK
;
1068 xfs_extlen_t flen
= 0;
1072 * If a cntbt cursor is provided, try to allocate the largest record in
1073 * the tree. Try the AGFL if the cntbt is empty, otherwise fail the
1074 * allocation. Make sure to respect minleft even when pulling from the
1078 error
= xfs_btree_decrement(ccur
, 0, &i
);
1082 error
= xfs_alloc_get_rec(ccur
, &fbno
, &flen
, &i
);
1085 if (XFS_IS_CORRUPT(args
->mp
, i
!= 1)) {
1086 error
= -EFSCORRUPTED
;
1092 if (args
->minlen
!= 1 || args
->alignment
!= 1 ||
1093 args
->resv
== XFS_AG_RESV_AGFL
||
1094 be32_to_cpu(agf
->agf_flcount
) <= args
->minleft
)
1097 error
= xfs_alloc_get_freelist(args
->pag
, args
->tp
, args
->agbp
,
1101 if (fbno
== NULLAGBLOCK
)
1104 xfs_extent_busy_reuse(args
->mp
, args
->pag
, fbno
, 1,
1105 (args
->datatype
& XFS_ALLOC_NOBUSY
));
1107 if (args
->datatype
& XFS_ALLOC_USERDATA
) {
1110 error
= xfs_trans_get_buf(args
->tp
, args
->mp
->m_ddev_targp
,
1111 XFS_AGB_TO_DADDR(args
->mp
, args
->agno
, fbno
),
1112 args
->mp
->m_bsize
, 0, &bp
);
1115 xfs_trans_binval(args
->tp
, bp
);
1117 *fbnop
= args
->agbno
= fbno
;
1118 *flenp
= args
->len
= 1;
1119 if (XFS_IS_CORRUPT(args
->mp
, fbno
>= be32_to_cpu(agf
->agf_length
))) {
1120 error
= -EFSCORRUPTED
;
1123 args
->wasfromfl
= 1;
1124 trace_xfs_alloc_small_freelist(args
);
1127 * If we're feeding an AGFL block to something that doesn't live in the
1128 * free space, we need to clear out the OWN_AG rmap.
1130 error
= xfs_rmap_free(args
->tp
, args
->agbp
, args
->pag
, fbno
, 1,
1131 &XFS_RMAP_OINFO_AG
);
1140 * Can't do the allocation, give up.
1142 if (flen
< args
->minlen
) {
1143 args
->agbno
= NULLAGBLOCK
;
1144 trace_xfs_alloc_small_notenough(args
);
1150 trace_xfs_alloc_small_done(args
);
1154 trace_xfs_alloc_small_error(args
);
1159 * Allocate a variable extent at exactly agno/bno.
1160 * Extent's length (returned in *len) will be between minlen and maxlen,
1161 * and of the form k * prod + mod unless there's nothing that large.
1162 * Return the starting a.g. block (bno), or NULLAGBLOCK if we can't do it.
1164 STATIC
int /* error */
1165 xfs_alloc_ag_vextent_exact(
1166 xfs_alloc_arg_t
*args
) /* allocation argument structure */
1168 struct xfs_agf __maybe_unused
*agf
= args
->agbp
->b_addr
;
1169 struct xfs_btree_cur
*bno_cur
;/* by block-number btree cursor */
1170 struct xfs_btree_cur
*cnt_cur
;/* by count btree cursor */
1172 xfs_agblock_t fbno
; /* start block of found extent */
1173 xfs_extlen_t flen
; /* length of found extent */
1174 xfs_agblock_t tbno
; /* start block of busy extent */
1175 xfs_extlen_t tlen
; /* length of busy extent */
1176 xfs_agblock_t tend
; /* end block of busy extent */
1177 int i
; /* success/failure of operation */
1180 ASSERT(args
->alignment
== 1);
1183 * Allocate/initialize a cursor for the by-number freespace btree.
1185 bno_cur
= xfs_allocbt_init_cursor(args
->mp
, args
->tp
, args
->agbp
,
1186 args
->pag
, XFS_BTNUM_BNO
);
1189 * Lookup bno and minlen in the btree (minlen is irrelevant, really).
1190 * Look for the closest free block <= bno, it must contain bno
1191 * if any free block does.
1193 error
= xfs_alloc_lookup_le(bno_cur
, args
->agbno
, args
->minlen
, &i
);
1200 * Grab the freespace record.
1202 error
= xfs_alloc_get_rec(bno_cur
, &fbno
, &flen
, &i
);
1205 if (XFS_IS_CORRUPT(args
->mp
, i
!= 1)) {
1206 error
= -EFSCORRUPTED
;
1209 ASSERT(fbno
<= args
->agbno
);
1212 * Check for overlapping busy extents.
1216 xfs_extent_busy_trim(args
, &tbno
, &tlen
, &busy_gen
);
1219 * Give up if the start of the extent is busy, or the freespace isn't
1220 * long enough for the minimum request.
1222 if (tbno
> args
->agbno
)
1224 if (tlen
< args
->minlen
)
1227 if (tend
< args
->agbno
+ args
->minlen
)
1231 * End of extent will be smaller of the freespace end and the
1232 * maximal requested end.
1234 * Fix the length according to mod and prod if given.
1236 args
->len
= XFS_AGBLOCK_MIN(tend
, args
->agbno
+ args
->maxlen
)
1238 xfs_alloc_fix_len(args
);
1239 ASSERT(args
->agbno
+ args
->len
<= tend
);
1242 * We are allocating agbno for args->len
1243 * Allocate/initialize a cursor for the by-size btree.
1245 cnt_cur
= xfs_allocbt_init_cursor(args
->mp
, args
->tp
, args
->agbp
,
1246 args
->pag
, XFS_BTNUM_CNT
);
1247 ASSERT(args
->agbno
+ args
->len
<= be32_to_cpu(agf
->agf_length
));
1248 error
= xfs_alloc_fixup_trees(cnt_cur
, bno_cur
, fbno
, flen
, args
->agbno
,
1249 args
->len
, XFSA_FIXUP_BNO_OK
);
1251 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_ERROR
);
1255 xfs_btree_del_cursor(bno_cur
, XFS_BTREE_NOERROR
);
1256 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_NOERROR
);
1258 args
->wasfromfl
= 0;
1259 trace_xfs_alloc_exact_done(args
);
1263 /* Didn't find it, return null. */
1264 xfs_btree_del_cursor(bno_cur
, XFS_BTREE_NOERROR
);
1265 args
->agbno
= NULLAGBLOCK
;
1266 trace_xfs_alloc_exact_notfound(args
);
1270 xfs_btree_del_cursor(bno_cur
, XFS_BTREE_ERROR
);
1271 trace_xfs_alloc_exact_error(args
);
1276 * Search a given number of btree records in a given direction. Check each
1277 * record against the good extent we've already found.
1280 xfs_alloc_walk_iter(
1281 struct xfs_alloc_arg
*args
,
1282 struct xfs_alloc_cur
*acur
,
1283 struct xfs_btree_cur
*cur
,
1285 bool find_one
, /* quit on first candidate */
1286 int count
, /* rec count (-1 for infinite) */
1295 * Search so long as the cursor is active or we find a better extent.
1296 * The cursor is deactivated if it extends beyond the range of the
1297 * current allocation candidate.
1299 while (xfs_alloc_cur_active(cur
) && count
) {
1300 error
= xfs_alloc_cur_check(args
, acur
, cur
, &i
);
1308 if (!xfs_alloc_cur_active(cur
))
1312 error
= xfs_btree_increment(cur
, 0, &i
);
1314 error
= xfs_btree_decrement(cur
, 0, &i
);
1318 cur
->bc_ag
.abt
.active
= false;
1328 * Search the by-bno and by-size btrees in parallel in search of an extent with
1329 * ideal locality based on the NEAR mode ->agbno locality hint.
1332 xfs_alloc_ag_vextent_locality(
1333 struct xfs_alloc_arg
*args
,
1334 struct xfs_alloc_cur
*acur
,
1337 struct xfs_btree_cur
*fbcur
= NULL
;
1342 ASSERT(acur
->len
== 0);
1346 error
= xfs_alloc_lookup_ge(acur
->cnt
, args
->agbno
, acur
->cur_len
, &i
);
1349 error
= xfs_alloc_lookup_le(acur
->bnolt
, args
->agbno
, 0, &i
);
1352 error
= xfs_alloc_lookup_ge(acur
->bnogt
, args
->agbno
, 0, &i
);
1357 * Search the bnobt and cntbt in parallel. Search the bnobt left and
1358 * right and lookup the closest extent to the locality hint for each
1359 * extent size key in the cntbt. The entire search terminates
1360 * immediately on a bnobt hit because that means we've found best case
1361 * locality. Otherwise the search continues until the cntbt cursor runs
1362 * off the end of the tree. If no allocation candidate is found at this
1363 * point, give up on locality, walk backwards from the end of the cntbt
1364 * and take the first available extent.
1366 * The parallel tree searches balance each other out to provide fairly
1367 * consistent performance for various situations. The bnobt search can
1368 * have pathological behavior in the worst case scenario of larger
1369 * allocation requests and fragmented free space. On the other hand, the
1370 * bnobt is able to satisfy most smaller allocation requests much more
1371 * quickly than the cntbt. The cntbt search can sift through fragmented
1372 * free space and sets of free extents for larger allocation requests
1373 * more quickly than the bnobt. Since the locality hint is just a hint
1374 * and we don't want to scan the entire bnobt for perfect locality, the
1375 * cntbt search essentially bounds the bnobt search such that we can
1376 * find good enough locality at reasonable performance in most cases.
1378 while (xfs_alloc_cur_active(acur
->bnolt
) ||
1379 xfs_alloc_cur_active(acur
->bnogt
) ||
1380 xfs_alloc_cur_active(acur
->cnt
)) {
1382 trace_xfs_alloc_cur_lookup(args
);
1385 * Search the bnobt left and right. In the case of a hit, finish
1386 * the search in the opposite direction and we're done.
1388 error
= xfs_alloc_walk_iter(args
, acur
, acur
->bnolt
, false,
1393 trace_xfs_alloc_cur_left(args
);
1394 fbcur
= acur
->bnogt
;
1398 error
= xfs_alloc_walk_iter(args
, acur
, acur
->bnogt
, true, true,
1403 trace_xfs_alloc_cur_right(args
);
1404 fbcur
= acur
->bnolt
;
1410 * Check the extent with best locality based on the current
1411 * extent size search key and keep track of the best candidate.
1413 error
= xfs_alloc_cntbt_iter(args
, acur
);
1416 if (!xfs_alloc_cur_active(acur
->cnt
)) {
1417 trace_xfs_alloc_cur_lookup_done(args
);
1423 * If we failed to find anything due to busy extents, return empty
1424 * handed so the caller can flush and retry. If no busy extents were
1425 * found, walk backwards from the end of the cntbt as a last resort.
1427 if (!xfs_alloc_cur_active(acur
->cnt
) && !acur
->len
&& !acur
->busy
) {
1428 error
= xfs_btree_decrement(acur
->cnt
, 0, &i
);
1432 acur
->cnt
->bc_ag
.abt
.active
= true;
1439 * Search in the opposite direction for a better entry in the case of
1440 * a bnobt hit or walk backwards from the end of the cntbt.
1443 error
= xfs_alloc_walk_iter(args
, acur
, fbcur
, fbinc
, true, -1,
1455 /* Check the last block of the cnt btree for allocations. */
1457 xfs_alloc_ag_vextent_lastblock(
1458 struct xfs_alloc_arg
*args
,
1459 struct xfs_alloc_cur
*acur
,
1468 /* Randomly don't execute the first algorithm. */
1469 if (get_random_u32_below(2))
1474 * Start from the entry that lookup found, sequence through all larger
1475 * free blocks. If we're actually pointing at a record smaller than
1476 * maxlen, go to the start of this block, and skip all those smaller
1479 if (*len
|| args
->alignment
> 1) {
1480 acur
->cnt
->bc_levels
[0].ptr
= 1;
1482 error
= xfs_alloc_get_rec(acur
->cnt
, bno
, len
, &i
);
1485 if (XFS_IS_CORRUPT(args
->mp
, i
!= 1))
1486 return -EFSCORRUPTED
;
1487 if (*len
>= args
->minlen
)
1489 error
= xfs_btree_increment(acur
->cnt
, 0, &i
);
1493 ASSERT(*len
>= args
->minlen
);
1498 error
= xfs_alloc_walk_iter(args
, acur
, acur
->cnt
, true, false, -1, &i
);
1503 * It didn't work. We COULD be in a case where there's a good record
1504 * somewhere, so try again.
1509 trace_xfs_alloc_near_first(args
);
1515 * Allocate a variable extent near bno in the allocation group agno.
1516 * Extent's length (returned in len) will be between minlen and maxlen,
1517 * and of the form k * prod + mod unless there's nothing that large.
1518 * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
1521 xfs_alloc_ag_vextent_near(
1522 struct xfs_alloc_arg
*args
)
1524 struct xfs_alloc_cur acur
= {};
1525 int error
; /* error code */
1526 int i
; /* result code, temporary */
1530 /* handle uninitialized agbno range so caller doesn't have to */
1531 if (!args
->min_agbno
&& !args
->max_agbno
)
1532 args
->max_agbno
= args
->mp
->m_sb
.sb_agblocks
- 1;
1533 ASSERT(args
->min_agbno
<= args
->max_agbno
);
1535 /* clamp agbno to the range if it's outside */
1536 if (args
->agbno
< args
->min_agbno
)
1537 args
->agbno
= args
->min_agbno
;
1538 if (args
->agbno
> args
->max_agbno
)
1539 args
->agbno
= args
->max_agbno
;
1545 * Set up cursors and see if there are any free extents as big as
1546 * maxlen. If not, pick the last entry in the tree unless the tree is
1549 error
= xfs_alloc_cur_setup(args
, &acur
);
1550 if (error
== -ENOSPC
) {
1551 error
= xfs_alloc_ag_vextent_small(args
, acur
.cnt
, &bno
,
1555 if (i
== 0 || len
== 0) {
1556 trace_xfs_alloc_near_noentry(args
);
1566 * If the requested extent is large wrt the freespaces available
1567 * in this a.g., then the cursor will be pointing to a btree entry
1568 * near the right edge of the tree. If it's in the last btree leaf
1569 * block, then we just examine all the entries in that block
1570 * that are big enough, and pick the best one.
1572 if (xfs_btree_islastblock(acur
.cnt
, 0)) {
1573 bool allocated
= false;
1575 error
= xfs_alloc_ag_vextent_lastblock(args
, &acur
, &bno
, &len
,
1584 * Second algorithm. Combined cntbt and bnobt search to find ideal
1587 error
= xfs_alloc_ag_vextent_locality(args
, &acur
, &i
);
1592 * If we couldn't get anything, give up.
1596 trace_xfs_alloc_near_busy(args
);
1597 xfs_extent_busy_flush(args
->mp
, args
->pag
,
1601 trace_xfs_alloc_size_neither(args
);
1602 args
->agbno
= NULLAGBLOCK
;
1607 /* fix up btrees on a successful allocation */
1608 error
= xfs_alloc_cur_finish(args
, &acur
);
1611 xfs_alloc_cur_close(&acur
, error
);
1616 * Allocate a variable extent anywhere in the allocation group agno.
1617 * Extent's length (returned in len) will be between minlen and maxlen,
1618 * and of the form k * prod + mod unless there's nothing that large.
1619 * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
1621 STATIC
int /* error */
1622 xfs_alloc_ag_vextent_size(
1623 xfs_alloc_arg_t
*args
) /* allocation argument structure */
1625 struct xfs_agf
*agf
= args
->agbp
->b_addr
;
1626 struct xfs_btree_cur
*bno_cur
; /* cursor for bno btree */
1627 struct xfs_btree_cur
*cnt_cur
; /* cursor for cnt btree */
1628 int error
; /* error result */
1629 xfs_agblock_t fbno
; /* start of found freespace */
1630 xfs_extlen_t flen
; /* length of found freespace */
1631 int i
; /* temp status variable */
1632 xfs_agblock_t rbno
; /* returned block number */
1633 xfs_extlen_t rlen
; /* length of returned extent */
1639 * Allocate and initialize a cursor for the by-size btree.
1641 cnt_cur
= xfs_allocbt_init_cursor(args
->mp
, args
->tp
, args
->agbp
,
1642 args
->pag
, XFS_BTNUM_CNT
);
1646 * Look for an entry >= maxlen+alignment-1 blocks.
1648 if ((error
= xfs_alloc_lookup_ge(cnt_cur
, 0,
1649 args
->maxlen
+ args
->alignment
- 1, &i
)))
1653 * If none then we have to settle for a smaller extent. In the case that
1654 * there are no large extents, this will return the last entry in the
1655 * tree unless the tree is empty. In the case that there are only busy
1656 * large extents, this will return the largest small extent unless there
1657 * are no smaller extents available.
1660 error
= xfs_alloc_ag_vextent_small(args
, cnt_cur
,
1664 if (i
== 0 || flen
== 0) {
1665 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_NOERROR
);
1666 trace_xfs_alloc_size_noentry(args
);
1670 busy
= xfs_alloc_compute_aligned(args
, fbno
, flen
, &rbno
,
1674 * Search for a non-busy extent that is large enough.
1677 error
= xfs_alloc_get_rec(cnt_cur
, &fbno
, &flen
, &i
);
1680 if (XFS_IS_CORRUPT(args
->mp
, i
!= 1)) {
1681 error
= -EFSCORRUPTED
;
1685 busy
= xfs_alloc_compute_aligned(args
, fbno
, flen
,
1686 &rbno
, &rlen
, &busy_gen
);
1688 if (rlen
>= args
->maxlen
)
1691 error
= xfs_btree_increment(cnt_cur
, 0, &i
);
1696 * Our only valid extents must have been busy.
1697 * Make it unbusy by forcing the log out and
1700 xfs_btree_del_cursor(cnt_cur
,
1702 trace_xfs_alloc_size_busy(args
);
1703 xfs_extent_busy_flush(args
->mp
,
1704 args
->pag
, busy_gen
);
1711 * In the first case above, we got the last entry in the
1712 * by-size btree. Now we check to see if the space hits maxlen
1713 * once aligned; if not, we search left for something better.
1714 * This can't happen in the second case above.
1716 rlen
= XFS_EXTLEN_MIN(args
->maxlen
, rlen
);
1717 if (XFS_IS_CORRUPT(args
->mp
,
1720 rbno
+ rlen
> fbno
+ flen
))) {
1721 error
= -EFSCORRUPTED
;
1724 if (rlen
< args
->maxlen
) {
1725 xfs_agblock_t bestfbno
;
1726 xfs_extlen_t bestflen
;
1727 xfs_agblock_t bestrbno
;
1728 xfs_extlen_t bestrlen
;
1735 if ((error
= xfs_btree_decrement(cnt_cur
, 0, &i
)))
1739 if ((error
= xfs_alloc_get_rec(cnt_cur
, &fbno
, &flen
,
1742 if (XFS_IS_CORRUPT(args
->mp
, i
!= 1)) {
1743 error
= -EFSCORRUPTED
;
1746 if (flen
< bestrlen
)
1748 busy
= xfs_alloc_compute_aligned(args
, fbno
, flen
,
1749 &rbno
, &rlen
, &busy_gen
);
1750 rlen
= XFS_EXTLEN_MIN(args
->maxlen
, rlen
);
1751 if (XFS_IS_CORRUPT(args
->mp
,
1754 rbno
+ rlen
> fbno
+ flen
))) {
1755 error
= -EFSCORRUPTED
;
1758 if (rlen
> bestrlen
) {
1763 if (rlen
== args
->maxlen
)
1767 if ((error
= xfs_alloc_lookup_eq(cnt_cur
, bestfbno
, bestflen
,
1770 if (XFS_IS_CORRUPT(args
->mp
, i
!= 1)) {
1771 error
= -EFSCORRUPTED
;
1779 args
->wasfromfl
= 0;
1781 * Fix up the length.
1784 if (rlen
< args
->minlen
) {
1786 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_NOERROR
);
1787 trace_xfs_alloc_size_busy(args
);
1788 xfs_extent_busy_flush(args
->mp
, args
->pag
, busy_gen
);
1793 xfs_alloc_fix_len(args
);
1796 if (XFS_IS_CORRUPT(args
->mp
, rlen
> flen
)) {
1797 error
= -EFSCORRUPTED
;
1801 * Allocate and initialize a cursor for the by-block tree.
1803 bno_cur
= xfs_allocbt_init_cursor(args
->mp
, args
->tp
, args
->agbp
,
1804 args
->pag
, XFS_BTNUM_BNO
);
1805 if ((error
= xfs_alloc_fixup_trees(cnt_cur
, bno_cur
, fbno
, flen
,
1806 rbno
, rlen
, XFSA_FIXUP_CNT_OK
)))
1808 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_NOERROR
);
1809 xfs_btree_del_cursor(bno_cur
, XFS_BTREE_NOERROR
);
1810 cnt_cur
= bno_cur
= NULL
;
1813 if (XFS_IS_CORRUPT(args
->mp
,
1814 args
->agbno
+ args
->len
>
1815 be32_to_cpu(agf
->agf_length
))) {
1816 error
= -EFSCORRUPTED
;
1819 trace_xfs_alloc_size_done(args
);
1823 trace_xfs_alloc_size_error(args
);
1825 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_ERROR
);
1827 xfs_btree_del_cursor(bno_cur
, XFS_BTREE_ERROR
);
1831 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_NOERROR
);
1832 trace_xfs_alloc_size_nominleft(args
);
1833 args
->agbno
= NULLAGBLOCK
;
1838 * Free the extent starting at agno/bno for length.
1842 struct xfs_trans
*tp
,
1843 struct xfs_buf
*agbp
,
1844 xfs_agnumber_t agno
,
1847 const struct xfs_owner_info
*oinfo
,
1848 enum xfs_ag_resv_type type
)
1850 struct xfs_mount
*mp
;
1851 struct xfs_btree_cur
*bno_cur
;
1852 struct xfs_btree_cur
*cnt_cur
;
1853 xfs_agblock_t gtbno
; /* start of right neighbor */
1854 xfs_extlen_t gtlen
; /* length of right neighbor */
1855 xfs_agblock_t ltbno
; /* start of left neighbor */
1856 xfs_extlen_t ltlen
; /* length of left neighbor */
1857 xfs_agblock_t nbno
; /* new starting block of freesp */
1858 xfs_extlen_t nlen
; /* new length of freespace */
1859 int haveleft
; /* have a left neighbor */
1860 int haveright
; /* have a right neighbor */
1863 struct xfs_perag
*pag
= agbp
->b_pag
;
1865 bno_cur
= cnt_cur
= NULL
;
1868 if (!xfs_rmap_should_skip_owner_update(oinfo
)) {
1869 error
= xfs_rmap_free(tp
, agbp
, pag
, bno
, len
, oinfo
);
1875 * Allocate and initialize a cursor for the by-block btree.
1877 bno_cur
= xfs_allocbt_init_cursor(mp
, tp
, agbp
, pag
, XFS_BTNUM_BNO
);
1879 * Look for a neighboring block on the left (lower block numbers)
1880 * that is contiguous with this space.
1882 if ((error
= xfs_alloc_lookup_le(bno_cur
, bno
, len
, &haveleft
)))
1886 * There is a block to our left.
1888 if ((error
= xfs_alloc_get_rec(bno_cur
, <bno
, <len
, &i
)))
1890 if (XFS_IS_CORRUPT(mp
, i
!= 1)) {
1891 error
= -EFSCORRUPTED
;
1895 * It's not contiguous, though.
1897 if (ltbno
+ ltlen
< bno
)
1901 * If this failure happens the request to free this
1902 * space was invalid, it's (partly) already free.
1905 if (XFS_IS_CORRUPT(mp
, ltbno
+ ltlen
> bno
)) {
1906 error
= -EFSCORRUPTED
;
1912 * Look for a neighboring block on the right (higher block numbers)
1913 * that is contiguous with this space.
1915 if ((error
= xfs_btree_increment(bno_cur
, 0, &haveright
)))
1919 * There is a block to our right.
1921 if ((error
= xfs_alloc_get_rec(bno_cur
, >bno
, >len
, &i
)))
1923 if (XFS_IS_CORRUPT(mp
, i
!= 1)) {
1924 error
= -EFSCORRUPTED
;
1928 * It's not contiguous, though.
1930 if (bno
+ len
< gtbno
)
1934 * If this failure happens the request to free this
1935 * space was invalid, it's (partly) already free.
1938 if (XFS_IS_CORRUPT(mp
, bno
+ len
> gtbno
)) {
1939 error
= -EFSCORRUPTED
;
1945 * Now allocate and initialize a cursor for the by-size tree.
1947 cnt_cur
= xfs_allocbt_init_cursor(mp
, tp
, agbp
, pag
, XFS_BTNUM_CNT
);
1949 * Have both left and right contiguous neighbors.
1950 * Merge all three into a single free block.
1952 if (haveleft
&& haveright
) {
1954 * Delete the old by-size entry on the left.
1956 if ((error
= xfs_alloc_lookup_eq(cnt_cur
, ltbno
, ltlen
, &i
)))
1958 if (XFS_IS_CORRUPT(mp
, i
!= 1)) {
1959 error
= -EFSCORRUPTED
;
1962 if ((error
= xfs_btree_delete(cnt_cur
, &i
)))
1964 if (XFS_IS_CORRUPT(mp
, i
!= 1)) {
1965 error
= -EFSCORRUPTED
;
1969 * Delete the old by-size entry on the right.
1971 if ((error
= xfs_alloc_lookup_eq(cnt_cur
, gtbno
, gtlen
, &i
)))
1973 if (XFS_IS_CORRUPT(mp
, i
!= 1)) {
1974 error
= -EFSCORRUPTED
;
1977 if ((error
= xfs_btree_delete(cnt_cur
, &i
)))
1979 if (XFS_IS_CORRUPT(mp
, i
!= 1)) {
1980 error
= -EFSCORRUPTED
;
1984 * Delete the old by-block entry for the right block.
1986 if ((error
= xfs_btree_delete(bno_cur
, &i
)))
1988 if (XFS_IS_CORRUPT(mp
, i
!= 1)) {
1989 error
= -EFSCORRUPTED
;
1993 * Move the by-block cursor back to the left neighbor.
1995 if ((error
= xfs_btree_decrement(bno_cur
, 0, &i
)))
1997 if (XFS_IS_CORRUPT(mp
, i
!= 1)) {
1998 error
= -EFSCORRUPTED
;
2003 * Check that this is the right record: delete didn't
2004 * mangle the cursor.
2007 xfs_agblock_t xxbno
;
2010 if ((error
= xfs_alloc_get_rec(bno_cur
, &xxbno
, &xxlen
,
2013 if (XFS_IS_CORRUPT(mp
,
2017 error
= -EFSCORRUPTED
;
2023 * Update remaining by-block entry to the new, joined block.
2026 nlen
= len
+ ltlen
+ gtlen
;
2027 if ((error
= xfs_alloc_update(bno_cur
, nbno
, nlen
)))
2031 * Have only a left contiguous neighbor.
2032 * Merge it together with the new freespace.
2034 else if (haveleft
) {
2036 * Delete the old by-size entry on the left.
2038 if ((error
= xfs_alloc_lookup_eq(cnt_cur
, ltbno
, ltlen
, &i
)))
2040 if (XFS_IS_CORRUPT(mp
, i
!= 1)) {
2041 error
= -EFSCORRUPTED
;
2044 if ((error
= xfs_btree_delete(cnt_cur
, &i
)))
2046 if (XFS_IS_CORRUPT(mp
, i
!= 1)) {
2047 error
= -EFSCORRUPTED
;
2051 * Back up the by-block cursor to the left neighbor, and
2052 * update its length.
2054 if ((error
= xfs_btree_decrement(bno_cur
, 0, &i
)))
2056 if (XFS_IS_CORRUPT(mp
, i
!= 1)) {
2057 error
= -EFSCORRUPTED
;
2062 if ((error
= xfs_alloc_update(bno_cur
, nbno
, nlen
)))
2066 * Have only a right contiguous neighbor.
2067 * Merge it together with the new freespace.
2069 else if (haveright
) {
2071 * Delete the old by-size entry on the right.
2073 if ((error
= xfs_alloc_lookup_eq(cnt_cur
, gtbno
, gtlen
, &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 * Update the starting block and length of the right
2087 * neighbor in the by-block tree.
2091 if ((error
= xfs_alloc_update(bno_cur
, nbno
, nlen
)))
2095 * No contiguous neighbors.
2096 * Insert the new freespace into the by-block tree.
2101 if ((error
= xfs_btree_insert(bno_cur
, &i
)))
2103 if (XFS_IS_CORRUPT(mp
, i
!= 1)) {
2104 error
= -EFSCORRUPTED
;
2108 xfs_btree_del_cursor(bno_cur
, XFS_BTREE_NOERROR
);
2111 * In all cases we need to insert the new freespace in the by-size tree.
2113 if ((error
= xfs_alloc_lookup_eq(cnt_cur
, nbno
, nlen
, &i
)))
2115 if (XFS_IS_CORRUPT(mp
, i
!= 0)) {
2116 error
= -EFSCORRUPTED
;
2119 if ((error
= xfs_btree_insert(cnt_cur
, &i
)))
2121 if (XFS_IS_CORRUPT(mp
, i
!= 1)) {
2122 error
= -EFSCORRUPTED
;
2125 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_NOERROR
);
2129 * Update the freespace totals in the ag and superblock.
2131 error
= xfs_alloc_update_counters(tp
, agbp
, len
);
2132 xfs_ag_resv_free_extent(agbp
->b_pag
, type
, tp
, len
);
2136 XFS_STATS_INC(mp
, xs_freex
);
2137 XFS_STATS_ADD(mp
, xs_freeb
, len
);
2139 trace_xfs_free_extent(mp
, agno
, bno
, len
, type
, haveleft
, haveright
);
2144 trace_xfs_free_extent(mp
, agno
, bno
, len
, type
, -1, -1);
2146 xfs_btree_del_cursor(bno_cur
, XFS_BTREE_ERROR
);
2148 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_ERROR
);
2153 * Visible (exported) allocation/free functions.
2154 * Some of these are used just by xfs_alloc_btree.c and this file.
2158 * Compute and fill in value of m_alloc_maxlevels.
2161 xfs_alloc_compute_maxlevels(
2162 xfs_mount_t
*mp
) /* file system mount structure */
2164 mp
->m_alloc_maxlevels
= xfs_btree_compute_maxlevels(mp
->m_alloc_mnr
,
2165 (mp
->m_sb
.sb_agblocks
+ 1) / 2);
2166 ASSERT(mp
->m_alloc_maxlevels
<= xfs_allocbt_maxlevels_ondisk());
2170 * Find the length of the longest extent in an AG. The 'need' parameter
2171 * specifies how much space we're going to need for the AGFL and the
2172 * 'reserved' parameter tells us how many blocks in this AG are reserved for
2176 xfs_alloc_longest_free_extent(
2177 struct xfs_perag
*pag
,
2179 xfs_extlen_t reserved
)
2181 xfs_extlen_t delta
= 0;
2184 * If the AGFL needs a recharge, we'll have to subtract that from the
2187 if (need
> pag
->pagf_flcount
)
2188 delta
= need
- pag
->pagf_flcount
;
2191 * If we cannot maintain others' reservations with space from the
2192 * not-longest freesp extents, we'll have to subtract /that/ from
2193 * the longest extent too.
2195 if (pag
->pagf_freeblks
- pag
->pagf_longest
< reserved
)
2196 delta
+= reserved
- (pag
->pagf_freeblks
- pag
->pagf_longest
);
2199 * If the longest extent is long enough to satisfy all the
2200 * reservations and AGFL rules in place, we can return this extent.
2202 if (pag
->pagf_longest
> delta
)
2203 return min_t(xfs_extlen_t
, pag
->pag_mount
->m_ag_max_usable
,
2204 pag
->pagf_longest
- delta
);
2206 /* Otherwise, let the caller try for 1 block if there's space. */
2207 return pag
->pagf_flcount
> 0 || pag
->pagf_longest
> 0;
2211 * Compute the minimum length of the AGFL in the given AG. If @pag is NULL,
2212 * return the largest possible minimum length.
2215 xfs_alloc_min_freelist(
2216 struct xfs_mount
*mp
,
2217 struct xfs_perag
*pag
)
2219 /* AG btrees have at least 1 level. */
2220 static const uint8_t fake_levels
[XFS_BTNUM_AGF
] = {1, 1, 1};
2221 const uint8_t *levels
= pag
? pag
->pagf_levels
: fake_levels
;
2222 unsigned int min_free
;
2224 ASSERT(mp
->m_alloc_maxlevels
> 0);
2226 /* space needed by-bno freespace btree */
2227 min_free
= min_t(unsigned int, levels
[XFS_BTNUM_BNOi
] + 1,
2228 mp
->m_alloc_maxlevels
);
2229 /* space needed by-size freespace btree */
2230 min_free
+= min_t(unsigned int, levels
[XFS_BTNUM_CNTi
] + 1,
2231 mp
->m_alloc_maxlevels
);
2232 /* space needed reverse mapping used space btree */
2233 if (xfs_has_rmapbt(mp
))
2234 min_free
+= min_t(unsigned int, levels
[XFS_BTNUM_RMAPi
] + 1,
2235 mp
->m_rmap_maxlevels
);
2241 * Check if the operation we are fixing up the freelist for should go ahead or
2242 * not. If we are freeing blocks, we always allow it, otherwise the allocation
2243 * is dependent on whether the size and shape of free space available will
2244 * permit the requested allocation to take place.
2247 xfs_alloc_space_available(
2248 struct xfs_alloc_arg
*args
,
2249 xfs_extlen_t min_free
,
2252 struct xfs_perag
*pag
= args
->pag
;
2253 xfs_extlen_t alloc_len
, longest
;
2254 xfs_extlen_t reservation
; /* blocks that are still reserved */
2256 xfs_extlen_t agflcount
;
2258 if (flags
& XFS_ALLOC_FLAG_FREEING
)
2261 reservation
= xfs_ag_resv_needed(pag
, args
->resv
);
2263 /* do we have enough contiguous free space for the allocation? */
2264 alloc_len
= args
->minlen
+ (args
->alignment
- 1) + args
->minalignslop
;
2265 longest
= xfs_alloc_longest_free_extent(pag
, min_free
, reservation
);
2266 if (longest
< alloc_len
)
2270 * Do we have enough free space remaining for the allocation? Don't
2271 * account extra agfl blocks because we are about to defer free them,
2272 * making them unavailable until the current transaction commits.
2274 agflcount
= min_t(xfs_extlen_t
, pag
->pagf_flcount
, min_free
);
2275 available
= (int)(pag
->pagf_freeblks
+ agflcount
-
2276 reservation
- min_free
- args
->minleft
);
2277 if (available
< (int)max(args
->total
, alloc_len
))
2281 * Clamp maxlen to the amount of free space available for the actual
2282 * extent allocation.
2284 if (available
< (int)args
->maxlen
&& !(flags
& XFS_ALLOC_FLAG_CHECK
)) {
2285 args
->maxlen
= available
;
2286 ASSERT(args
->maxlen
> 0);
2287 ASSERT(args
->maxlen
>= args
->minlen
);
2294 xfs_free_agfl_block(
2295 struct xfs_trans
*tp
,
2296 xfs_agnumber_t agno
,
2297 xfs_agblock_t agbno
,
2298 struct xfs_buf
*agbp
,
2299 struct xfs_owner_info
*oinfo
)
2304 error
= xfs_free_ag_extent(tp
, agbp
, agno
, agbno
, 1, oinfo
,
2309 error
= xfs_trans_get_buf(tp
, tp
->t_mountp
->m_ddev_targp
,
2310 XFS_AGB_TO_DADDR(tp
->t_mountp
, agno
, agbno
),
2311 tp
->t_mountp
->m_bsize
, 0, &bp
);
2314 xfs_trans_binval(tp
, bp
);
2320 * Check the agfl fields of the agf for inconsistency or corruption. The purpose
2321 * is to detect an agfl header padding mismatch between current and early v5
2322 * kernels. This problem manifests as a 1-slot size difference between the
2323 * on-disk flcount and the active [first, last] range of a wrapped agfl. This
2324 * may also catch variants of agfl count corruption unrelated to padding. Either
2325 * way, we'll reset the agfl and warn the user.
2327 * Return true if a reset is required before the agfl can be used, false
2331 xfs_agfl_needs_reset(
2332 struct xfs_mount
*mp
,
2333 struct xfs_agf
*agf
)
2335 uint32_t f
= be32_to_cpu(agf
->agf_flfirst
);
2336 uint32_t l
= be32_to_cpu(agf
->agf_fllast
);
2337 uint32_t c
= be32_to_cpu(agf
->agf_flcount
);
2338 int agfl_size
= xfs_agfl_size(mp
);
2341 /* no agfl header on v4 supers */
2342 if (!xfs_has_crc(mp
))
2346 * The agf read verifier catches severe corruption of these fields.
2347 * Repeat some sanity checks to cover a packed -> unpacked mismatch if
2348 * the verifier allows it.
2350 if (f
>= agfl_size
|| l
>= agfl_size
)
2356 * Check consistency between the on-disk count and the active range. An
2357 * agfl padding mismatch manifests as an inconsistent flcount.
2362 active
= agfl_size
- f
+ l
+ 1;
2370 * Reset the agfl to an empty state. Ignore/drop any existing blocks since the
2371 * agfl content cannot be trusted. Warn the user that a repair is required to
2372 * recover leaked blocks.
2374 * The purpose of this mechanism is to handle filesystems affected by the agfl
2375 * header padding mismatch problem. A reset keeps the filesystem online with a
2376 * relatively minor free space accounting inconsistency rather than suffer the
2377 * inevitable crash from use of an invalid agfl block.
2381 struct xfs_trans
*tp
,
2382 struct xfs_buf
*agbp
,
2383 struct xfs_perag
*pag
)
2385 struct xfs_mount
*mp
= tp
->t_mountp
;
2386 struct xfs_agf
*agf
= agbp
->b_addr
;
2388 ASSERT(xfs_perag_agfl_needs_reset(pag
));
2389 trace_xfs_agfl_reset(mp
, agf
, 0, _RET_IP_
);
2392 "WARNING: Reset corrupted AGFL on AG %u. %d blocks leaked. "
2393 "Please unmount and run xfs_repair.",
2394 pag
->pag_agno
, pag
->pagf_flcount
);
2396 agf
->agf_flfirst
= 0;
2397 agf
->agf_fllast
= cpu_to_be32(xfs_agfl_size(mp
) - 1);
2398 agf
->agf_flcount
= 0;
2399 xfs_alloc_log_agf(tp
, agbp
, XFS_AGF_FLFIRST
| XFS_AGF_FLLAST
|
2402 pag
->pagf_flcount
= 0;
2403 clear_bit(XFS_AGSTATE_AGFL_NEEDS_RESET
, &pag
->pag_opstate
);
2407 * Defer an AGFL block free. This is effectively equivalent to
2408 * xfs_free_extent_later() with some special handling particular to AGFL blocks.
2410 * Deferring AGFL frees helps prevent log reservation overruns due to too many
2411 * allocation operations in a transaction. AGFL frees are prone to this problem
2412 * because for one they are always freed one at a time. Further, an immediate
2413 * AGFL block free can cause a btree join and require another block free before
2414 * the real allocation can proceed. Deferring the free disconnects freeing up
2415 * the AGFL slot from freeing the block.
2418 xfs_defer_agfl_block(
2419 struct xfs_trans
*tp
,
2420 xfs_agnumber_t agno
,
2421 xfs_fsblock_t agbno
,
2422 struct xfs_owner_info
*oinfo
)
2424 struct xfs_mount
*mp
= tp
->t_mountp
;
2425 struct xfs_extent_free_item
*xefi
;
2427 ASSERT(xfs_extfree_item_cache
!= NULL
);
2428 ASSERT(oinfo
!= NULL
);
2430 xefi
= kmem_cache_zalloc(xfs_extfree_item_cache
,
2431 GFP_KERNEL
| __GFP_NOFAIL
);
2432 xefi
->xefi_startblock
= XFS_AGB_TO_FSB(mp
, agno
, agbno
);
2433 xefi
->xefi_blockcount
= 1;
2434 xefi
->xefi_owner
= oinfo
->oi_owner
;
2436 trace_xfs_agfl_free_defer(mp
, agno
, 0, agbno
, 1);
2438 xfs_extent_free_get_group(mp
, xefi
);
2439 xfs_defer_add(tp
, XFS_DEFER_OPS_TYPE_AGFL_FREE
, &xefi
->xefi_list
);
2443 * Add the extent to the list of extents to be free at transaction end.
2444 * The list is maintained sorted (by block number).
2447 __xfs_free_extent_later(
2448 struct xfs_trans
*tp
,
2451 const struct xfs_owner_info
*oinfo
,
2454 struct xfs_extent_free_item
*xefi
;
2455 struct xfs_mount
*mp
= tp
->t_mountp
;
2457 xfs_agnumber_t agno
;
2458 xfs_agblock_t agbno
;
2460 ASSERT(bno
!= NULLFSBLOCK
);
2462 ASSERT(len
<= XFS_MAX_BMBT_EXTLEN
);
2463 ASSERT(!isnullstartblock(bno
));
2464 agno
= XFS_FSB_TO_AGNO(mp
, bno
);
2465 agbno
= XFS_FSB_TO_AGBNO(mp
, bno
);
2466 ASSERT(agno
< mp
->m_sb
.sb_agcount
);
2467 ASSERT(agbno
< mp
->m_sb
.sb_agblocks
);
2468 ASSERT(len
< mp
->m_sb
.sb_agblocks
);
2469 ASSERT(agbno
+ len
<= mp
->m_sb
.sb_agblocks
);
2471 ASSERT(xfs_extfree_item_cache
!= NULL
);
2473 xefi
= kmem_cache_zalloc(xfs_extfree_item_cache
,
2474 GFP_KERNEL
| __GFP_NOFAIL
);
2475 xefi
->xefi_startblock
= bno
;
2476 xefi
->xefi_blockcount
= (xfs_extlen_t
)len
;
2478 xefi
->xefi_flags
|= XFS_EFI_SKIP_DISCARD
;
2480 ASSERT(oinfo
->oi_offset
== 0);
2482 if (oinfo
->oi_flags
& XFS_OWNER_INFO_ATTR_FORK
)
2483 xefi
->xefi_flags
|= XFS_EFI_ATTR_FORK
;
2484 if (oinfo
->oi_flags
& XFS_OWNER_INFO_BMBT_BLOCK
)
2485 xefi
->xefi_flags
|= XFS_EFI_BMBT_BLOCK
;
2486 xefi
->xefi_owner
= oinfo
->oi_owner
;
2488 xefi
->xefi_owner
= XFS_RMAP_OWN_NULL
;
2490 trace_xfs_bmap_free_defer(mp
,
2491 XFS_FSB_TO_AGNO(tp
->t_mountp
, bno
), 0,
2492 XFS_FSB_TO_AGBNO(tp
->t_mountp
, bno
), len
);
2494 xfs_extent_free_get_group(mp
, xefi
);
2495 xfs_defer_add(tp
, XFS_DEFER_OPS_TYPE_FREE
, &xefi
->xefi_list
);
2500 * Check if an AGF has a free extent record whose length is equal to
2504 xfs_exact_minlen_extent_available(
2505 struct xfs_alloc_arg
*args
,
2506 struct xfs_buf
*agbp
,
2509 struct xfs_btree_cur
*cnt_cur
;
2514 cnt_cur
= xfs_allocbt_init_cursor(args
->mp
, args
->tp
, agbp
,
2515 args
->pag
, XFS_BTNUM_CNT
);
2516 error
= xfs_alloc_lookup_ge(cnt_cur
, 0, args
->minlen
, stat
);
2521 error
= -EFSCORRUPTED
;
2525 error
= xfs_alloc_get_rec(cnt_cur
, &fbno
, &flen
, stat
);
2529 if (*stat
== 1 && flen
!= args
->minlen
)
2533 xfs_btree_del_cursor(cnt_cur
, error
);
2540 * Decide whether to use this allocation group for this allocation.
2541 * If so, fix up the btree freelist's size.
2544 xfs_alloc_fix_freelist(
2545 struct xfs_alloc_arg
*args
, /* allocation argument structure */
2546 int flags
) /* XFS_ALLOC_FLAG_... */
2548 struct xfs_mount
*mp
= args
->mp
;
2549 struct xfs_perag
*pag
= args
->pag
;
2550 struct xfs_trans
*tp
= args
->tp
;
2551 struct xfs_buf
*agbp
= NULL
;
2552 struct xfs_buf
*agflbp
= NULL
;
2553 struct xfs_alloc_arg targs
; /* local allocation arguments */
2554 xfs_agblock_t bno
; /* freelist block */
2555 xfs_extlen_t need
; /* total blocks needed in freelist */
2558 /* deferred ops (AGFL block frees) require permanent transactions */
2559 ASSERT(tp
->t_flags
& XFS_TRANS_PERM_LOG_RES
);
2561 if (!xfs_perag_initialised_agf(pag
)) {
2562 error
= xfs_alloc_read_agf(pag
, tp
, flags
, &agbp
);
2564 /* Couldn't lock the AGF so skip this AG. */
2565 if (error
== -EAGAIN
)
2572 * If this is a metadata preferred pag and we are user data then try
2573 * somewhere else if we are not being asked to try harder at this
2576 if (xfs_perag_prefers_metadata(pag
) &&
2577 (args
->datatype
& XFS_ALLOC_USERDATA
) &&
2578 (flags
& XFS_ALLOC_FLAG_TRYLOCK
)) {
2579 ASSERT(!(flags
& XFS_ALLOC_FLAG_FREEING
));
2580 goto out_agbp_relse
;
2583 need
= xfs_alloc_min_freelist(mp
, pag
);
2584 if (!xfs_alloc_space_available(args
, need
, flags
|
2585 XFS_ALLOC_FLAG_CHECK
))
2586 goto out_agbp_relse
;
2589 * Get the a.g. freespace buffer.
2590 * Can fail if we're not blocking on locks, and it's held.
2593 error
= xfs_alloc_read_agf(pag
, tp
, flags
, &agbp
);
2595 /* Couldn't lock the AGF so skip this AG. */
2596 if (error
== -EAGAIN
)
2602 /* reset a padding mismatched agfl before final free space check */
2603 if (xfs_perag_agfl_needs_reset(pag
))
2604 xfs_agfl_reset(tp
, agbp
, pag
);
2606 /* If there isn't enough total space or single-extent, reject it. */
2607 need
= xfs_alloc_min_freelist(mp
, pag
);
2608 if (!xfs_alloc_space_available(args
, need
, flags
))
2609 goto out_agbp_relse
;
2612 if (args
->alloc_minlen_only
) {
2615 error
= xfs_exact_minlen_extent_available(args
, agbp
, &stat
);
2617 goto out_agbp_relse
;
2621 * Make the freelist shorter if it's too long.
2623 * Note that from this point onwards, we will always release the agf and
2624 * agfl buffers on error. This handles the case where we error out and
2625 * the buffers are clean or may not have been joined to the transaction
2626 * and hence need to be released manually. If they have been joined to
2627 * the transaction, then xfs_trans_brelse() will handle them
2628 * appropriately based on the recursion count and dirty state of the
2631 * XXX (dgc): When we have lots of free space, does this buy us
2632 * anything other than extra overhead when we need to put more blocks
2633 * back on the free list? Maybe we should only do this when space is
2634 * getting low or the AGFL is more than half full?
2636 * The NOSHRINK flag prevents the AGFL from being shrunk if it's too
2637 * big; the NORMAP flag prevents AGFL expand/shrink operations from
2638 * updating the rmapbt. Both flags are used in xfs_repair while we're
2639 * rebuilding the rmapbt, and neither are used by the kernel. They're
2640 * both required to ensure that rmaps are correctly recorded for the
2641 * regenerated AGFL, bnobt, and cntbt. See repair/phase5.c and
2642 * repair/rmap.c in xfsprogs for details.
2644 memset(&targs
, 0, sizeof(targs
));
2645 /* struct copy below */
2646 if (flags
& XFS_ALLOC_FLAG_NORMAP
)
2647 targs
.oinfo
= XFS_RMAP_OINFO_SKIP_UPDATE
;
2649 targs
.oinfo
= XFS_RMAP_OINFO_AG
;
2650 while (!(flags
& XFS_ALLOC_FLAG_NOSHRINK
) && pag
->pagf_flcount
> need
) {
2651 error
= xfs_alloc_get_freelist(pag
, tp
, agbp
, &bno
, 0);
2653 goto out_agbp_relse
;
2655 /* defer agfl frees */
2656 xfs_defer_agfl_block(tp
, args
->agno
, bno
, &targs
.oinfo
);
2662 targs
.agno
= args
->agno
;
2663 targs
.alignment
= targs
.minlen
= targs
.prod
= 1;
2665 error
= xfs_alloc_read_agfl(pag
, tp
, &agflbp
);
2667 goto out_agbp_relse
;
2669 /* Make the freelist longer if it's too short. */
2670 while (pag
->pagf_flcount
< need
) {
2672 targs
.maxlen
= need
- pag
->pagf_flcount
;
2673 targs
.resv
= XFS_AG_RESV_AGFL
;
2675 /* Allocate as many blocks as possible at once. */
2676 error
= xfs_alloc_ag_vextent_size(&targs
);
2678 goto out_agflbp_relse
;
2681 * Stop if we run out. Won't happen if callers are obeying
2682 * the restrictions correctly. Can happen for free calls
2683 * on a completely full ag.
2685 if (targs
.agbno
== NULLAGBLOCK
) {
2686 if (flags
& XFS_ALLOC_FLAG_FREEING
)
2688 goto out_agflbp_relse
;
2691 if (!xfs_rmap_should_skip_owner_update(&targs
.oinfo
)) {
2692 error
= xfs_rmap_alloc(tp
, agbp
, pag
,
2693 targs
.agbno
, targs
.len
, &targs
.oinfo
);
2695 goto out_agflbp_relse
;
2697 error
= xfs_alloc_update_counters(tp
, agbp
,
2698 -((long)(targs
.len
)));
2700 goto out_agflbp_relse
;
2703 * Put each allocated block on the list.
2705 for (bno
= targs
.agbno
; bno
< targs
.agbno
+ targs
.len
; bno
++) {
2706 error
= xfs_alloc_put_freelist(pag
, tp
, agbp
,
2709 goto out_agflbp_relse
;
2712 xfs_trans_brelse(tp
, agflbp
);
2717 xfs_trans_brelse(tp
, agflbp
);
2720 xfs_trans_brelse(tp
, agbp
);
2727 * Get a block from the freelist.
2728 * Returns with the buffer for the block gotten.
2731 xfs_alloc_get_freelist(
2732 struct xfs_perag
*pag
,
2733 struct xfs_trans
*tp
,
2734 struct xfs_buf
*agbp
,
2735 xfs_agblock_t
*bnop
,
2738 struct xfs_agf
*agf
= agbp
->b_addr
;
2739 struct xfs_buf
*agflbp
;
2744 struct xfs_mount
*mp
= tp
->t_mountp
;
2747 * Freelist is empty, give up.
2749 if (!agf
->agf_flcount
) {
2750 *bnop
= NULLAGBLOCK
;
2754 * Read the array of free blocks.
2756 error
= xfs_alloc_read_agfl(pag
, tp
, &agflbp
);
2762 * Get the block number and update the data structures.
2764 agfl_bno
= xfs_buf_to_agfl_bno(agflbp
);
2765 bno
= be32_to_cpu(agfl_bno
[be32_to_cpu(agf
->agf_flfirst
)]);
2766 be32_add_cpu(&agf
->agf_flfirst
, 1);
2767 xfs_trans_brelse(tp
, agflbp
);
2768 if (be32_to_cpu(agf
->agf_flfirst
) == xfs_agfl_size(mp
))
2769 agf
->agf_flfirst
= 0;
2771 ASSERT(!xfs_perag_agfl_needs_reset(pag
));
2772 be32_add_cpu(&agf
->agf_flcount
, -1);
2773 pag
->pagf_flcount
--;
2775 logflags
= XFS_AGF_FLFIRST
| XFS_AGF_FLCOUNT
;
2777 be32_add_cpu(&agf
->agf_btreeblks
, 1);
2778 pag
->pagf_btreeblks
++;
2779 logflags
|= XFS_AGF_BTREEBLKS
;
2782 xfs_alloc_log_agf(tp
, agbp
, logflags
);
2789 * Log the given fields from the agf structure.
2793 struct xfs_trans
*tp
,
2797 int first
; /* first byte offset */
2798 int last
; /* last byte offset */
2799 static const short offsets
[] = {
2800 offsetof(xfs_agf_t
, agf_magicnum
),
2801 offsetof(xfs_agf_t
, agf_versionnum
),
2802 offsetof(xfs_agf_t
, agf_seqno
),
2803 offsetof(xfs_agf_t
, agf_length
),
2804 offsetof(xfs_agf_t
, agf_roots
[0]),
2805 offsetof(xfs_agf_t
, agf_levels
[0]),
2806 offsetof(xfs_agf_t
, agf_flfirst
),
2807 offsetof(xfs_agf_t
, agf_fllast
),
2808 offsetof(xfs_agf_t
, agf_flcount
),
2809 offsetof(xfs_agf_t
, agf_freeblks
),
2810 offsetof(xfs_agf_t
, agf_longest
),
2811 offsetof(xfs_agf_t
, agf_btreeblks
),
2812 offsetof(xfs_agf_t
, agf_uuid
),
2813 offsetof(xfs_agf_t
, agf_rmap_blocks
),
2814 offsetof(xfs_agf_t
, agf_refcount_blocks
),
2815 offsetof(xfs_agf_t
, agf_refcount_root
),
2816 offsetof(xfs_agf_t
, agf_refcount_level
),
2817 /* needed so that we don't log the whole rest of the structure: */
2818 offsetof(xfs_agf_t
, agf_spare64
),
2822 trace_xfs_agf(tp
->t_mountp
, bp
->b_addr
, fields
, _RET_IP_
);
2824 xfs_trans_buf_set_type(tp
, bp
, XFS_BLFT_AGF_BUF
);
2826 xfs_btree_offsets(fields
, offsets
, XFS_AGF_NUM_BITS
, &first
, &last
);
2827 xfs_trans_log_buf(tp
, bp
, (uint
)first
, (uint
)last
);
2831 * Put the block on the freelist for the allocation group.
2834 xfs_alloc_put_freelist(
2835 struct xfs_perag
*pag
,
2836 struct xfs_trans
*tp
,
2837 struct xfs_buf
*agbp
,
2838 struct xfs_buf
*agflbp
,
2842 struct xfs_mount
*mp
= tp
->t_mountp
;
2843 struct xfs_agf
*agf
= agbp
->b_addr
;
2851 error
= xfs_alloc_read_agfl(pag
, tp
, &agflbp
);
2856 be32_add_cpu(&agf
->agf_fllast
, 1);
2857 if (be32_to_cpu(agf
->agf_fllast
) == xfs_agfl_size(mp
))
2858 agf
->agf_fllast
= 0;
2860 ASSERT(!xfs_perag_agfl_needs_reset(pag
));
2861 be32_add_cpu(&agf
->agf_flcount
, 1);
2862 pag
->pagf_flcount
++;
2864 logflags
= XFS_AGF_FLLAST
| XFS_AGF_FLCOUNT
;
2866 be32_add_cpu(&agf
->agf_btreeblks
, -1);
2867 pag
->pagf_btreeblks
--;
2868 logflags
|= XFS_AGF_BTREEBLKS
;
2871 xfs_alloc_log_agf(tp
, agbp
, logflags
);
2873 ASSERT(be32_to_cpu(agf
->agf_flcount
) <= xfs_agfl_size(mp
));
2875 agfl_bno
= xfs_buf_to_agfl_bno(agflbp
);
2876 blockp
= &agfl_bno
[be32_to_cpu(agf
->agf_fllast
)];
2877 *blockp
= cpu_to_be32(bno
);
2878 startoff
= (char *)blockp
- (char *)agflbp
->b_addr
;
2880 xfs_alloc_log_agf(tp
, agbp
, logflags
);
2882 xfs_trans_buf_set_type(tp
, agflbp
, XFS_BLFT_AGFL_BUF
);
2883 xfs_trans_log_buf(tp
, agflbp
, startoff
,
2884 startoff
+ sizeof(xfs_agblock_t
) - 1);
2888 static xfs_failaddr_t
2892 struct xfs_mount
*mp
= bp
->b_mount
;
2893 struct xfs_agf
*agf
= bp
->b_addr
;
2895 if (xfs_has_crc(mp
)) {
2896 if (!uuid_equal(&agf
->agf_uuid
, &mp
->m_sb
.sb_meta_uuid
))
2897 return __this_address
;
2898 if (!xfs_log_check_lsn(mp
, be64_to_cpu(agf
->agf_lsn
)))
2899 return __this_address
;
2902 if (!xfs_verify_magic(bp
, agf
->agf_magicnum
))
2903 return __this_address
;
2905 if (!(XFS_AGF_GOOD_VERSION(be32_to_cpu(agf
->agf_versionnum
)) &&
2906 be32_to_cpu(agf
->agf_freeblks
) <= be32_to_cpu(agf
->agf_length
) &&
2907 be32_to_cpu(agf
->agf_flfirst
) < xfs_agfl_size(mp
) &&
2908 be32_to_cpu(agf
->agf_fllast
) < xfs_agfl_size(mp
) &&
2909 be32_to_cpu(agf
->agf_flcount
) <= xfs_agfl_size(mp
)))
2910 return __this_address
;
2912 if (be32_to_cpu(agf
->agf_length
) > mp
->m_sb
.sb_dblocks
)
2913 return __this_address
;
2915 if (be32_to_cpu(agf
->agf_freeblks
) < be32_to_cpu(agf
->agf_longest
) ||
2916 be32_to_cpu(agf
->agf_freeblks
) > be32_to_cpu(agf
->agf_length
))
2917 return __this_address
;
2919 if (be32_to_cpu(agf
->agf_levels
[XFS_BTNUM_BNO
]) < 1 ||
2920 be32_to_cpu(agf
->agf_levels
[XFS_BTNUM_CNT
]) < 1 ||
2921 be32_to_cpu(agf
->agf_levels
[XFS_BTNUM_BNO
]) >
2922 mp
->m_alloc_maxlevels
||
2923 be32_to_cpu(agf
->agf_levels
[XFS_BTNUM_CNT
]) >
2924 mp
->m_alloc_maxlevels
)
2925 return __this_address
;
2927 if (xfs_has_rmapbt(mp
) &&
2928 (be32_to_cpu(agf
->agf_levels
[XFS_BTNUM_RMAP
]) < 1 ||
2929 be32_to_cpu(agf
->agf_levels
[XFS_BTNUM_RMAP
]) >
2930 mp
->m_rmap_maxlevels
))
2931 return __this_address
;
2933 if (xfs_has_rmapbt(mp
) &&
2934 be32_to_cpu(agf
->agf_rmap_blocks
) > be32_to_cpu(agf
->agf_length
))
2935 return __this_address
;
2938 * during growfs operations, the perag is not fully initialised,
2939 * so we can't use it for any useful checking. growfs ensures we can't
2940 * use it by using uncached buffers that don't have the perag attached
2941 * so we can detect and avoid this problem.
2943 if (bp
->b_pag
&& be32_to_cpu(agf
->agf_seqno
) != bp
->b_pag
->pag_agno
)
2944 return __this_address
;
2946 if (xfs_has_lazysbcount(mp
) &&
2947 be32_to_cpu(agf
->agf_btreeblks
) > be32_to_cpu(agf
->agf_length
))
2948 return __this_address
;
2950 if (xfs_has_reflink(mp
) &&
2951 be32_to_cpu(agf
->agf_refcount_blocks
) >
2952 be32_to_cpu(agf
->agf_length
))
2953 return __this_address
;
2955 if (xfs_has_reflink(mp
) &&
2956 (be32_to_cpu(agf
->agf_refcount_level
) < 1 ||
2957 be32_to_cpu(agf
->agf_refcount_level
) > mp
->m_refc_maxlevels
))
2958 return __this_address
;
2965 xfs_agf_read_verify(
2968 struct xfs_mount
*mp
= bp
->b_mount
;
2971 if (xfs_has_crc(mp
) &&
2972 !xfs_buf_verify_cksum(bp
, XFS_AGF_CRC_OFF
))
2973 xfs_verifier_error(bp
, -EFSBADCRC
, __this_address
);
2975 fa
= xfs_agf_verify(bp
);
2976 if (XFS_TEST_ERROR(fa
, mp
, XFS_ERRTAG_ALLOC_READ_AGF
))
2977 xfs_verifier_error(bp
, -EFSCORRUPTED
, fa
);
2982 xfs_agf_write_verify(
2985 struct xfs_mount
*mp
= bp
->b_mount
;
2986 struct xfs_buf_log_item
*bip
= bp
->b_log_item
;
2987 struct xfs_agf
*agf
= bp
->b_addr
;
2990 fa
= xfs_agf_verify(bp
);
2992 xfs_verifier_error(bp
, -EFSCORRUPTED
, fa
);
2996 if (!xfs_has_crc(mp
))
3000 agf
->agf_lsn
= cpu_to_be64(bip
->bli_item
.li_lsn
);
3002 xfs_buf_update_cksum(bp
, XFS_AGF_CRC_OFF
);
3005 const struct xfs_buf_ops xfs_agf_buf_ops
= {
3007 .magic
= { cpu_to_be32(XFS_AGF_MAGIC
), cpu_to_be32(XFS_AGF_MAGIC
) },
3008 .verify_read
= xfs_agf_read_verify
,
3009 .verify_write
= xfs_agf_write_verify
,
3010 .verify_struct
= xfs_agf_verify
,
3014 * Read in the allocation group header (free/alloc section).
3018 struct xfs_perag
*pag
,
3019 struct xfs_trans
*tp
,
3021 struct xfs_buf
**agfbpp
)
3023 struct xfs_mount
*mp
= pag
->pag_mount
;
3026 trace_xfs_read_agf(pag
->pag_mount
, pag
->pag_agno
);
3028 error
= xfs_trans_read_buf(mp
, tp
, mp
->m_ddev_targp
,
3029 XFS_AG_DADDR(mp
, pag
->pag_agno
, XFS_AGF_DADDR(mp
)),
3030 XFS_FSS_TO_BB(mp
, 1), flags
, agfbpp
, &xfs_agf_buf_ops
);
3034 xfs_buf_set_ref(*agfbpp
, XFS_AGF_REF
);
3039 * Read in the allocation group header (free/alloc section) and initialise the
3040 * perag structure if necessary. If the caller provides @agfbpp, then return the
3041 * locked buffer to the caller, otherwise free it.
3045 struct xfs_perag
*pag
,
3046 struct xfs_trans
*tp
,
3048 struct xfs_buf
**agfbpp
)
3050 struct xfs_buf
*agfbp
;
3051 struct xfs_agf
*agf
;
3055 trace_xfs_alloc_read_agf(pag
->pag_mount
, pag
->pag_agno
);
3057 /* We don't support trylock when freeing. */
3058 ASSERT((flags
& (XFS_ALLOC_FLAG_FREEING
| XFS_ALLOC_FLAG_TRYLOCK
)) !=
3059 (XFS_ALLOC_FLAG_FREEING
| XFS_ALLOC_FLAG_TRYLOCK
));
3060 error
= xfs_read_agf(pag
, tp
,
3061 (flags
& XFS_ALLOC_FLAG_TRYLOCK
) ? XBF_TRYLOCK
: 0,
3066 agf
= agfbp
->b_addr
;
3067 if (!xfs_perag_initialised_agf(pag
)) {
3068 pag
->pagf_freeblks
= be32_to_cpu(agf
->agf_freeblks
);
3069 pag
->pagf_btreeblks
= be32_to_cpu(agf
->agf_btreeblks
);
3070 pag
->pagf_flcount
= be32_to_cpu(agf
->agf_flcount
);
3071 pag
->pagf_longest
= be32_to_cpu(agf
->agf_longest
);
3072 pag
->pagf_levels
[XFS_BTNUM_BNOi
] =
3073 be32_to_cpu(agf
->agf_levels
[XFS_BTNUM_BNOi
]);
3074 pag
->pagf_levels
[XFS_BTNUM_CNTi
] =
3075 be32_to_cpu(agf
->agf_levels
[XFS_BTNUM_CNTi
]);
3076 pag
->pagf_levels
[XFS_BTNUM_RMAPi
] =
3077 be32_to_cpu(agf
->agf_levels
[XFS_BTNUM_RMAPi
]);
3078 pag
->pagf_refcount_level
= be32_to_cpu(agf
->agf_refcount_level
);
3079 if (xfs_agfl_needs_reset(pag
->pag_mount
, agf
))
3080 set_bit(XFS_AGSTATE_AGFL_NEEDS_RESET
, &pag
->pag_opstate
);
3082 clear_bit(XFS_AGSTATE_AGFL_NEEDS_RESET
, &pag
->pag_opstate
);
3085 * Update the in-core allocbt counter. Filter out the rmapbt
3086 * subset of the btreeblks counter because the rmapbt is managed
3087 * by perag reservation. Subtract one for the rmapbt root block
3088 * because the rmap counter includes it while the btreeblks
3089 * counter only tracks non-root blocks.
3091 allocbt_blks
= pag
->pagf_btreeblks
;
3092 if (xfs_has_rmapbt(pag
->pag_mount
))
3093 allocbt_blks
-= be32_to_cpu(agf
->agf_rmap_blocks
) - 1;
3094 if (allocbt_blks
> 0)
3095 atomic64_add(allocbt_blks
,
3096 &pag
->pag_mount
->m_allocbt_blks
);
3098 set_bit(XFS_AGSTATE_AGF_INIT
, &pag
->pag_opstate
);
3101 else if (!xfs_is_shutdown(pag
->pag_mount
)) {
3102 ASSERT(pag
->pagf_freeblks
== be32_to_cpu(agf
->agf_freeblks
));
3103 ASSERT(pag
->pagf_btreeblks
== be32_to_cpu(agf
->agf_btreeblks
));
3104 ASSERT(pag
->pagf_flcount
== be32_to_cpu(agf
->agf_flcount
));
3105 ASSERT(pag
->pagf_longest
== be32_to_cpu(agf
->agf_longest
));
3106 ASSERT(pag
->pagf_levels
[XFS_BTNUM_BNOi
] ==
3107 be32_to_cpu(agf
->agf_levels
[XFS_BTNUM_BNOi
]));
3108 ASSERT(pag
->pagf_levels
[XFS_BTNUM_CNTi
] ==
3109 be32_to_cpu(agf
->agf_levels
[XFS_BTNUM_CNTi
]));
3115 xfs_trans_brelse(tp
, agfbp
);
3120 * Pre-proces allocation arguments to set initial state that we don't require
3121 * callers to set up correctly, as well as bounds check the allocation args
3125 xfs_alloc_vextent_check_args(
3126 struct xfs_alloc_arg
*args
,
3127 xfs_fsblock_t target
,
3128 xfs_agnumber_t
*minimum_agno
)
3130 struct xfs_mount
*mp
= args
->mp
;
3131 xfs_agblock_t agsize
;
3133 args
->fsbno
= NULLFSBLOCK
;
3136 if (args
->tp
->t_highest_agno
!= NULLAGNUMBER
)
3137 *minimum_agno
= args
->tp
->t_highest_agno
;
3140 * Just fix this up, for the case where the last a.g. is shorter
3141 * (or there's only one a.g.) and the caller couldn't easily figure
3142 * that out (xfs_bmap_alloc).
3144 agsize
= mp
->m_sb
.sb_agblocks
;
3145 if (args
->maxlen
> agsize
)
3146 args
->maxlen
= agsize
;
3147 if (args
->alignment
== 0)
3148 args
->alignment
= 1;
3150 ASSERT(args
->minlen
> 0);
3151 ASSERT(args
->maxlen
> 0);
3152 ASSERT(args
->alignment
> 0);
3153 ASSERT(args
->resv
!= XFS_AG_RESV_AGFL
);
3155 ASSERT(XFS_FSB_TO_AGNO(mp
, target
) < mp
->m_sb
.sb_agcount
);
3156 ASSERT(XFS_FSB_TO_AGBNO(mp
, target
) < agsize
);
3157 ASSERT(args
->minlen
<= args
->maxlen
);
3158 ASSERT(args
->minlen
<= agsize
);
3159 ASSERT(args
->mod
< args
->prod
);
3161 if (XFS_FSB_TO_AGNO(mp
, target
) >= mp
->m_sb
.sb_agcount
||
3162 XFS_FSB_TO_AGBNO(mp
, target
) >= agsize
||
3163 args
->minlen
> args
->maxlen
|| args
->minlen
> agsize
||
3164 args
->mod
>= args
->prod
) {
3165 trace_xfs_alloc_vextent_badargs(args
);
3169 if (args
->agno
!= NULLAGNUMBER
&& *minimum_agno
> args
->agno
) {
3170 trace_xfs_alloc_vextent_skip_deadlock(args
);
3178 * Prepare an AG for allocation. If the AG is not prepared to accept the
3179 * allocation, return failure.
3181 * XXX(dgc): The complexity of "need_pag" will go away as all caller paths are
3182 * modified to hold their own perag references.
3185 xfs_alloc_vextent_prepare_ag(
3186 struct xfs_alloc_arg
*args
)
3188 bool need_pag
= !args
->pag
;
3192 args
->pag
= xfs_perag_get(args
->mp
, args
->agno
);
3195 error
= xfs_alloc_fix_freelist(args
, 0);
3197 trace_xfs_alloc_vextent_nofix(args
);
3199 xfs_perag_put(args
->pag
);
3200 args
->agbno
= NULLAGBLOCK
;
3204 /* cannot allocate in this AG at all */
3205 trace_xfs_alloc_vextent_noagbp(args
);
3206 args
->agbno
= NULLAGBLOCK
;
3209 args
->wasfromfl
= 0;
3214 * Post-process allocation results to account for the allocation if it succeed
3215 * and set the allocated block number correctly for the caller.
3217 * XXX: we should really be returning ENOSPC for ENOSPC, not
3218 * hiding it behind a "successful" NULLFSBLOCK allocation.
3221 xfs_alloc_vextent_finish(
3222 struct xfs_alloc_arg
*args
,
3223 xfs_agnumber_t minimum_agno
,
3227 struct xfs_mount
*mp
= args
->mp
;
3231 * We can end up here with a locked AGF. If we failed, the caller is
3232 * likely going to try to allocate again with different parameters, and
3233 * that can widen the AGs that are searched for free space. If we have
3234 * to do BMBT block allocation, we have to do a new allocation.
3236 * Hence leaving this function with the AGF locked opens up potential
3237 * ABBA AGF deadlocks because a future allocation attempt in this
3238 * transaction may attempt to lock a lower number AGF.
3240 * We can't release the AGF until the transaction is commited, so at
3241 * this point we must update the "first allocation" tracker to point at
3242 * this AG if the tracker is empty or points to a lower AG. This allows
3243 * the next allocation attempt to be modified appropriately to avoid
3247 (args
->tp
->t_highest_agno
== NULLAGNUMBER
||
3248 args
->agno
> minimum_agno
))
3249 args
->tp
->t_highest_agno
= args
->agno
;
3252 * If the allocation failed with an error or we had an ENOSPC result,
3253 * preserve the returned error whilst also marking the allocation result
3254 * as "no extent allocated". This ensures that callers that fail to
3255 * capture the error will still treat it as a failed allocation.
3257 if (alloc_error
|| args
->agbno
== NULLAGBLOCK
) {
3258 args
->fsbno
= NULLFSBLOCK
;
3259 error
= alloc_error
;
3260 goto out_drop_perag
;
3263 args
->fsbno
= XFS_AGB_TO_FSB(mp
, args
->agno
, args
->agbno
);
3265 ASSERT(args
->len
>= args
->minlen
);
3266 ASSERT(args
->len
<= args
->maxlen
);
3267 ASSERT(args
->agbno
% args
->alignment
== 0);
3268 XFS_AG_CHECK_DADDR(mp
, XFS_FSB_TO_DADDR(mp
, args
->fsbno
), args
->len
);
3270 /* if not file data, insert new block into the reverse map btree */
3271 if (!xfs_rmap_should_skip_owner_update(&args
->oinfo
)) {
3272 error
= xfs_rmap_alloc(args
->tp
, args
->agbp
, args
->pag
,
3273 args
->agbno
, args
->len
, &args
->oinfo
);
3275 goto out_drop_perag
;
3278 if (!args
->wasfromfl
) {
3279 error
= xfs_alloc_update_counters(args
->tp
, args
->agbp
,
3280 -((long)(args
->len
)));
3282 goto out_drop_perag
;
3284 ASSERT(!xfs_extent_busy_search(mp
, args
->pag
, args
->agbno
,
3288 xfs_ag_resv_alloc_extent(args
->pag
, args
->resv
, args
);
3290 XFS_STATS_INC(mp
, xs_allocx
);
3291 XFS_STATS_ADD(mp
, xs_allocb
, args
->len
);
3293 trace_xfs_alloc_vextent_finish(args
);
3296 if (drop_perag
&& args
->pag
) {
3297 xfs_perag_rele(args
->pag
);
3304 * Allocate within a single AG only. This uses a best-fit length algorithm so if
3305 * you need an exact sized allocation without locality constraints, this is the
3306 * fastest way to do it.
3308 * Caller is expected to hold a perag reference in args->pag.
3311 xfs_alloc_vextent_this_ag(
3312 struct xfs_alloc_arg
*args
,
3313 xfs_agnumber_t agno
)
3315 struct xfs_mount
*mp
= args
->mp
;
3316 xfs_agnumber_t minimum_agno
;
3319 ASSERT(args
->pag
!= NULL
);
3320 ASSERT(args
->pag
->pag_agno
== agno
);
3325 trace_xfs_alloc_vextent_this_ag(args
);
3327 error
= xfs_alloc_vextent_check_args(args
, XFS_AGB_TO_FSB(mp
, agno
, 0),
3330 if (error
== -ENOSPC
)
3335 error
= xfs_alloc_vextent_prepare_ag(args
);
3336 if (!error
&& args
->agbp
)
3337 error
= xfs_alloc_ag_vextent_size(args
);
3339 return xfs_alloc_vextent_finish(args
, minimum_agno
, error
, false);
3343 * Iterate all AGs trying to allocate an extent starting from @start_ag.
3345 * If the incoming allocation type is XFS_ALLOCTYPE_NEAR_BNO, it means the
3346 * allocation attempts in @start_agno have locality information. If we fail to
3347 * allocate in that AG, then we revert to anywhere-in-AG for all the other AGs
3348 * we attempt to allocation in as there is no locality optimisation possible for
3349 * those allocations.
3351 * On return, args->pag may be left referenced if we finish before the "all
3352 * failed" return point. The allocation finish still needs the perag, and
3353 * so the caller will release it once they've finished the allocation.
3355 * When we wrap the AG iteration at the end of the filesystem, we have to be
3356 * careful not to wrap into AGs below ones we already have locked in the
3357 * transaction if we are doing a blocking iteration. This will result in an
3358 * out-of-order locking of AGFs and hence can cause deadlocks.
3361 xfs_alloc_vextent_iterate_ags(
3362 struct xfs_alloc_arg
*args
,
3363 xfs_agnumber_t minimum_agno
,
3364 xfs_agnumber_t start_agno
,
3365 xfs_agblock_t target_agbno
,
3368 struct xfs_mount
*mp
= args
->mp
;
3369 xfs_agnumber_t restart_agno
= minimum_agno
;
3370 xfs_agnumber_t agno
;
3373 if (flags
& XFS_ALLOC_FLAG_TRYLOCK
)
3376 for_each_perag_wrap_range(mp
, start_agno
, restart_agno
,
3377 mp
->m_sb
.sb_agcount
, agno
, args
->pag
) {
3379 error
= xfs_alloc_vextent_prepare_ag(args
);
3383 trace_xfs_alloc_vextent_loopfailed(args
);
3388 * Allocation is supposed to succeed now, so break out of the
3389 * loop regardless of whether we succeed or not.
3391 if (args
->agno
== start_agno
&& target_agbno
) {
3392 args
->agbno
= target_agbno
;
3393 error
= xfs_alloc_ag_vextent_near(args
);
3396 error
= xfs_alloc_ag_vextent_size(args
);
3401 xfs_perag_rele(args
->pag
);
3409 * We didn't find an AG we can alloation from. If we were given
3410 * constraining flags by the caller, drop them and retry the allocation
3411 * without any constraints being set.
3415 restart_agno
= minimum_agno
;
3419 ASSERT(args
->pag
== NULL
);
3420 trace_xfs_alloc_vextent_allfailed(args
);
3425 * Iterate from the AGs from the start AG to the end of the filesystem, trying
3426 * to allocate blocks. It starts with a near allocation attempt in the initial
3427 * AG, then falls back to anywhere-in-ag after the first AG fails. It will wrap
3428 * back to zero if allowed by previous allocations in this transaction,
3429 * otherwise will wrap back to the start AG and run a second blocking pass to
3430 * the end of the filesystem.
3433 xfs_alloc_vextent_start_ag(
3434 struct xfs_alloc_arg
*args
,
3435 xfs_fsblock_t target
)
3437 struct xfs_mount
*mp
= args
->mp
;
3438 xfs_agnumber_t minimum_agno
;
3439 xfs_agnumber_t start_agno
;
3440 xfs_agnumber_t rotorstep
= xfs_rotorstep
;
3441 bool bump_rotor
= false;
3444 ASSERT(args
->pag
== NULL
);
3446 args
->agno
= NULLAGNUMBER
;
3447 args
->agbno
= NULLAGBLOCK
;
3449 trace_xfs_alloc_vextent_start_ag(args
);
3451 error
= xfs_alloc_vextent_check_args(args
, target
, &minimum_agno
);
3453 if (error
== -ENOSPC
)
3458 if ((args
->datatype
& XFS_ALLOC_INITIAL_USER_DATA
) &&
3459 xfs_is_inode32(mp
)) {
3460 target
= XFS_AGB_TO_FSB(mp
,
3461 ((mp
->m_agfrotor
/ rotorstep
) %
3462 mp
->m_sb
.sb_agcount
), 0);
3466 start_agno
= max(minimum_agno
, XFS_FSB_TO_AGNO(mp
, target
));
3467 error
= xfs_alloc_vextent_iterate_ags(args
, minimum_agno
, start_agno
,
3468 XFS_FSB_TO_AGBNO(mp
, target
), XFS_ALLOC_FLAG_TRYLOCK
);
3471 if (args
->agno
== start_agno
)
3472 mp
->m_agfrotor
= (mp
->m_agfrotor
+ 1) %
3473 (mp
->m_sb
.sb_agcount
* rotorstep
);
3475 mp
->m_agfrotor
= (args
->agno
* rotorstep
+ 1) %
3476 (mp
->m_sb
.sb_agcount
* rotorstep
);
3479 return xfs_alloc_vextent_finish(args
, minimum_agno
, error
, true);
3483 * Iterate from the agno indicated via @target through to the end of the
3484 * filesystem attempting blocking allocation. This does not wrap or try a second
3485 * pass, so will not recurse into AGs lower than indicated by the target.
3488 xfs_alloc_vextent_first_ag(
3489 struct xfs_alloc_arg
*args
,
3490 xfs_fsblock_t target
)
3492 struct xfs_mount
*mp
= args
->mp
;
3493 xfs_agnumber_t minimum_agno
;
3494 xfs_agnumber_t start_agno
;
3497 ASSERT(args
->pag
== NULL
);
3499 args
->agno
= NULLAGNUMBER
;
3500 args
->agbno
= NULLAGBLOCK
;
3502 trace_xfs_alloc_vextent_first_ag(args
);
3504 error
= xfs_alloc_vextent_check_args(args
, target
, &minimum_agno
);
3506 if (error
== -ENOSPC
)
3511 start_agno
= max(minimum_agno
, XFS_FSB_TO_AGNO(mp
, target
));
3512 error
= xfs_alloc_vextent_iterate_ags(args
, minimum_agno
, start_agno
,
3513 XFS_FSB_TO_AGBNO(mp
, target
), 0);
3514 return xfs_alloc_vextent_finish(args
, minimum_agno
, error
, true);
3518 * Allocate at the exact block target or fail. Caller is expected to hold a
3519 * perag reference in args->pag.
3522 xfs_alloc_vextent_exact_bno(
3523 struct xfs_alloc_arg
*args
,
3524 xfs_fsblock_t target
)
3526 struct xfs_mount
*mp
= args
->mp
;
3527 xfs_agnumber_t minimum_agno
;
3530 ASSERT(args
->pag
!= NULL
);
3531 ASSERT(args
->pag
->pag_agno
== XFS_FSB_TO_AGNO(mp
, target
));
3533 args
->agno
= XFS_FSB_TO_AGNO(mp
, target
);
3534 args
->agbno
= XFS_FSB_TO_AGBNO(mp
, target
);
3536 trace_xfs_alloc_vextent_exact_bno(args
);
3538 error
= xfs_alloc_vextent_check_args(args
, target
, &minimum_agno
);
3540 if (error
== -ENOSPC
)
3545 error
= xfs_alloc_vextent_prepare_ag(args
);
3546 if (!error
&& args
->agbp
)
3547 error
= xfs_alloc_ag_vextent_exact(args
);
3549 return xfs_alloc_vextent_finish(args
, minimum_agno
, error
, false);
3553 * Allocate an extent as close to the target as possible. If there are not
3554 * viable candidates in the AG, then fail the allocation.
3556 * Caller may or may not have a per-ag reference in args->pag.
3559 xfs_alloc_vextent_near_bno(
3560 struct xfs_alloc_arg
*args
,
3561 xfs_fsblock_t target
)
3563 struct xfs_mount
*mp
= args
->mp
;
3564 xfs_agnumber_t minimum_agno
;
3565 bool needs_perag
= args
->pag
== NULL
;
3569 ASSERT(args
->pag
->pag_agno
== XFS_FSB_TO_AGNO(mp
, target
));
3571 args
->agno
= XFS_FSB_TO_AGNO(mp
, target
);
3572 args
->agbno
= XFS_FSB_TO_AGBNO(mp
, target
);
3574 trace_xfs_alloc_vextent_near_bno(args
);
3576 error
= xfs_alloc_vextent_check_args(args
, target
, &minimum_agno
);
3578 if (error
== -ENOSPC
)
3584 args
->pag
= xfs_perag_grab(mp
, args
->agno
);
3586 error
= xfs_alloc_vextent_prepare_ag(args
);
3587 if (!error
&& args
->agbp
)
3588 error
= xfs_alloc_ag_vextent_near(args
);
3590 return xfs_alloc_vextent_finish(args
, minimum_agno
, error
, needs_perag
);
3593 /* Ensure that the freelist is at full capacity. */
3595 xfs_free_extent_fix_freelist(
3596 struct xfs_trans
*tp
,
3597 struct xfs_perag
*pag
,
3598 struct xfs_buf
**agbp
)
3600 struct xfs_alloc_arg args
;
3603 memset(&args
, 0, sizeof(struct xfs_alloc_arg
));
3605 args
.mp
= tp
->t_mountp
;
3606 args
.agno
= pag
->pag_agno
;
3610 * validate that the block number is legal - the enables us to detect
3611 * and handle a silent filesystem corruption rather than crashing.
3613 if (args
.agno
>= args
.mp
->m_sb
.sb_agcount
)
3614 return -EFSCORRUPTED
;
3616 error
= xfs_alloc_fix_freelist(&args
, XFS_ALLOC_FLAG_FREEING
);
3626 * Just break up the extent address and hand off to xfs_free_ag_extent
3627 * after fixing up the freelist.
3631 struct xfs_trans
*tp
,
3632 struct xfs_perag
*pag
,
3633 xfs_agblock_t agbno
,
3635 const struct xfs_owner_info
*oinfo
,
3636 enum xfs_ag_resv_type type
,
3639 struct xfs_mount
*mp
= tp
->t_mountp
;
3640 struct xfs_buf
*agbp
;
3641 struct xfs_agf
*agf
;
3643 unsigned int busy_flags
= 0;
3646 ASSERT(type
!= XFS_AG_RESV_AGFL
);
3648 if (XFS_TEST_ERROR(false, mp
,
3649 XFS_ERRTAG_FREE_EXTENT
))
3652 error
= xfs_free_extent_fix_freelist(tp
, pag
, &agbp
);
3657 if (XFS_IS_CORRUPT(mp
, agbno
>= mp
->m_sb
.sb_agblocks
)) {
3658 error
= -EFSCORRUPTED
;
3662 /* validate the extent size is legal now we have the agf locked */
3663 if (XFS_IS_CORRUPT(mp
, agbno
+ len
> be32_to_cpu(agf
->agf_length
))) {
3664 error
= -EFSCORRUPTED
;
3668 error
= xfs_free_ag_extent(tp
, agbp
, pag
->pag_agno
, agbno
, len
, oinfo
,
3674 busy_flags
|= XFS_EXTENT_BUSY_SKIP_DISCARD
;
3675 xfs_extent_busy_insert(tp
, pag
, agbno
, len
, busy_flags
);
3679 xfs_trans_brelse(tp
, agbp
);
3683 struct xfs_alloc_query_range_info
{
3684 xfs_alloc_query_range_fn fn
;
3688 /* Format btree record and pass to our callback. */
3690 xfs_alloc_query_range_helper(
3691 struct xfs_btree_cur
*cur
,
3692 const union xfs_btree_rec
*rec
,
3695 struct xfs_alloc_query_range_info
*query
= priv
;
3696 struct xfs_alloc_rec_incore irec
;
3699 xfs_alloc_btrec_to_irec(rec
, &irec
);
3700 fa
= xfs_alloc_check_irec(cur
, &irec
);
3702 return xfs_alloc_complain_bad_rec(cur
, fa
, &irec
);
3704 return query
->fn(cur
, &irec
, query
->priv
);
3707 /* Find all free space within a given range of blocks. */
3709 xfs_alloc_query_range(
3710 struct xfs_btree_cur
*cur
,
3711 const struct xfs_alloc_rec_incore
*low_rec
,
3712 const struct xfs_alloc_rec_incore
*high_rec
,
3713 xfs_alloc_query_range_fn fn
,
3716 union xfs_btree_irec low_brec
;
3717 union xfs_btree_irec high_brec
;
3718 struct xfs_alloc_query_range_info query
;
3720 ASSERT(cur
->bc_btnum
== XFS_BTNUM_BNO
);
3721 low_brec
.a
= *low_rec
;
3722 high_brec
.a
= *high_rec
;
3725 return xfs_btree_query_range(cur
, &low_brec
, &high_brec
,
3726 xfs_alloc_query_range_helper
, &query
);
3729 /* Find all free space records. */
3731 xfs_alloc_query_all(
3732 struct xfs_btree_cur
*cur
,
3733 xfs_alloc_query_range_fn fn
,
3736 struct xfs_alloc_query_range_info query
;
3738 ASSERT(cur
->bc_btnum
== XFS_BTNUM_BNO
);
3741 return xfs_btree_query_all(cur
, xfs_alloc_query_range_helper
, &query
);
3745 * Scan part of the keyspace of the free space and tell us if the area has no
3746 * records, is fully mapped by records, or is partially filled.
3749 xfs_alloc_has_records(
3750 struct xfs_btree_cur
*cur
,
3753 enum xbtree_recpacking
*outcome
)
3755 union xfs_btree_irec low
;
3756 union xfs_btree_irec high
;
3758 memset(&low
, 0, sizeof(low
));
3759 low
.a
.ar_startblock
= bno
;
3760 memset(&high
, 0xFF, sizeof(high
));
3761 high
.a
.ar_startblock
= bno
+ len
- 1;
3763 return xfs_btree_has_records(cur
, &low
, &high
, outcome
);
3767 * Walk all the blocks in the AGFL. The @walk_fn can return any negative
3768 * error code or XFS_ITER_*.
3772 struct xfs_mount
*mp
,
3773 struct xfs_agf
*agf
,
3774 struct xfs_buf
*agflbp
,
3775 xfs_agfl_walk_fn walk_fn
,
3782 agfl_bno
= xfs_buf_to_agfl_bno(agflbp
);
3783 i
= be32_to_cpu(agf
->agf_flfirst
);
3785 /* Nothing to walk in an empty AGFL. */
3786 if (agf
->agf_flcount
== cpu_to_be32(0))
3789 /* Otherwise, walk from first to last, wrapping as needed. */
3791 error
= walk_fn(mp
, be32_to_cpu(agfl_bno
[i
]), priv
);
3794 if (i
== be32_to_cpu(agf
->agf_fllast
))
3796 if (++i
== xfs_agfl_size(mp
))
3804 xfs_extfree_intent_init_cache(void)
3806 xfs_extfree_item_cache
= kmem_cache_create("xfs_extfree_intent",
3807 sizeof(struct xfs_extent_free_item
),
3810 return xfs_extfree_item_cache
!= NULL
? 0 : -ENOMEM
;
3814 xfs_extfree_intent_destroy_cache(void)
3816 kmem_cache_destroy(xfs_extfree_item_cache
);
3817 xfs_extfree_item_cache
= NULL
;