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
35 STATIC
int xfs_alloc_ag_vextent_exact(xfs_alloc_arg_t
*);
36 STATIC
int xfs_alloc_ag_vextent_near(xfs_alloc_arg_t
*);
37 STATIC
int xfs_alloc_ag_vextent_size(xfs_alloc_arg_t
*);
40 * Size of the AGFL. For CRC-enabled filesystes we steal a couple of slots in
41 * the beginning of the block for a proper header with the location information
48 unsigned int size
= mp
->m_sb
.sb_sectsize
;
51 size
-= sizeof(struct xfs_agfl
);
53 return size
/ sizeof(xfs_agblock_t
);
60 if (xfs_has_rmapbt(mp
))
61 return XFS_RMAP_BLOCK(mp
) + 1;
62 if (xfs_has_finobt(mp
))
63 return XFS_FIBT_BLOCK(mp
) + 1;
64 return XFS_IBT_BLOCK(mp
) + 1;
71 if (xfs_has_reflink(mp
))
72 return xfs_refc_block(mp
) + 1;
73 if (xfs_has_rmapbt(mp
))
74 return XFS_RMAP_BLOCK(mp
) + 1;
75 if (xfs_has_finobt(mp
))
76 return XFS_FIBT_BLOCK(mp
) + 1;
77 return XFS_IBT_BLOCK(mp
) + 1;
81 * The number of blocks per AG that we withhold from xfs_mod_fdblocks to
82 * guarantee that we can refill the AGFL prior to allocating space in a nearly
83 * full AG. Although the the space described by the free space btrees, the
84 * blocks used by the freesp btrees themselves, and the blocks owned by the
85 * AGFL are counted in the ondisk fdblocks, it's a mistake to let the ondisk
86 * free space in the AG drop so low that the free space btrees cannot refill an
87 * empty AGFL up to the minimum level. Rather than grind through empty AGs
88 * until the fs goes down, we subtract this many AG blocks from the incore
89 * fdblocks to ensure user allocation does not overcommit the space the
90 * filesystem needs for the AGFLs. The rmap btree uses a per-AG reservation to
91 * withhold space from xfs_mod_fdblocks, so we do not account for that here.
93 #define XFS_ALLOCBT_AGFL_RESERVE 4
96 * Compute the number of blocks that we set aside to guarantee the ability to
97 * refill the AGFL and handle a full bmap btree split.
99 * In order to avoid ENOSPC-related deadlock caused by out-of-order locking of
100 * AGF buffer (PV 947395), we place constraints on the relationship among
101 * actual allocations for data blocks, freelist blocks, and potential file data
102 * bmap btree blocks. However, these restrictions may result in no actual space
103 * allocated for a delayed extent, for example, a data block in a certain AG is
104 * allocated but there is no additional block for the additional bmap btree
105 * block due to a split of the bmap btree of the file. The result of this may
106 * lead to an infinite loop when the file gets flushed to disk and all delayed
107 * extents need to be actually allocated. To get around this, we explicitly set
108 * aside a few blocks which will not be reserved in delayed allocation.
110 * For each AG, we need to reserve enough blocks to replenish a totally empty
111 * AGFL and 4 more to handle a potential split of the file's bmap btree.
115 struct xfs_mount
*mp
)
117 return mp
->m_sb
.sb_agcount
* (XFS_ALLOCBT_AGFL_RESERVE
+ 4);
121 * When deciding how much space to allocate out of an AG, we limit the
122 * allocation maximum size to the size the AG. However, we cannot use all the
123 * blocks in the AG - some are permanently used by metadata. These
124 * blocks are generally:
125 * - the AG superblock, AGF, AGI and AGFL
126 * - the AGF (bno and cnt) and AGI btree root blocks, and optionally
127 * the AGI free inode and rmap btree root blocks.
128 * - blocks on the AGFL according to xfs_alloc_set_aside() limits
129 * - the rmapbt root block
131 * The AG headers are sector sized, so the amount of space they take up is
132 * dependent on filesystem geometry. The others are all single blocks.
135 xfs_alloc_ag_max_usable(
136 struct xfs_mount
*mp
)
140 blocks
= XFS_BB_TO_FSB(mp
, XFS_FSS_TO_BB(mp
, 4)); /* ag headers */
141 blocks
+= XFS_ALLOCBT_AGFL_RESERVE
;
142 blocks
+= 3; /* AGF, AGI btree root blocks */
143 if (xfs_has_finobt(mp
))
144 blocks
++; /* finobt root block */
145 if (xfs_has_rmapbt(mp
))
146 blocks
++; /* rmap root block */
147 if (xfs_has_reflink(mp
))
148 blocks
++; /* refcount root block */
150 return mp
->m_sb
.sb_agblocks
- blocks
;
154 * Lookup the record equal to [bno, len] in the btree given by cur.
156 STATIC
int /* error */
158 struct xfs_btree_cur
*cur
, /* btree cursor */
159 xfs_agblock_t bno
, /* starting block of extent */
160 xfs_extlen_t len
, /* length of extent */
161 int *stat
) /* success/failure */
165 cur
->bc_rec
.a
.ar_startblock
= bno
;
166 cur
->bc_rec
.a
.ar_blockcount
= len
;
167 error
= xfs_btree_lookup(cur
, XFS_LOOKUP_EQ
, stat
);
168 cur
->bc_ag
.abt
.active
= (*stat
== 1);
173 * Lookup the first record greater than or equal to [bno, len]
174 * in the btree given by cur.
178 struct xfs_btree_cur
*cur
, /* btree cursor */
179 xfs_agblock_t bno
, /* starting block of extent */
180 xfs_extlen_t len
, /* length of extent */
181 int *stat
) /* success/failure */
185 cur
->bc_rec
.a
.ar_startblock
= bno
;
186 cur
->bc_rec
.a
.ar_blockcount
= len
;
187 error
= xfs_btree_lookup(cur
, XFS_LOOKUP_GE
, stat
);
188 cur
->bc_ag
.abt
.active
= (*stat
== 1);
193 * Lookup the first record less than or equal to [bno, len]
194 * in the btree given by cur.
198 struct xfs_btree_cur
*cur
, /* btree cursor */
199 xfs_agblock_t bno
, /* starting block of extent */
200 xfs_extlen_t len
, /* length of extent */
201 int *stat
) /* success/failure */
204 cur
->bc_rec
.a
.ar_startblock
= bno
;
205 cur
->bc_rec
.a
.ar_blockcount
= len
;
206 error
= xfs_btree_lookup(cur
, XFS_LOOKUP_LE
, stat
);
207 cur
->bc_ag
.abt
.active
= (*stat
== 1);
212 xfs_alloc_cur_active(
213 struct xfs_btree_cur
*cur
)
215 return cur
&& cur
->bc_ag
.abt
.active
;
219 * Update the record referred to by cur to the value given
221 * This either works (return 0) or gets an EFSCORRUPTED error.
223 STATIC
int /* error */
225 struct xfs_btree_cur
*cur
, /* btree cursor */
226 xfs_agblock_t bno
, /* starting block of extent */
227 xfs_extlen_t len
) /* length of extent */
229 union xfs_btree_rec rec
;
231 rec
.alloc
.ar_startblock
= cpu_to_be32(bno
);
232 rec
.alloc
.ar_blockcount
= cpu_to_be32(len
);
233 return xfs_btree_update(cur
, &rec
);
237 * Get the data from the pointed-to record.
241 struct xfs_btree_cur
*cur
, /* btree cursor */
242 xfs_agblock_t
*bno
, /* output: starting block of extent */
243 xfs_extlen_t
*len
, /* output: length of extent */
244 int *stat
) /* output: success/failure */
246 struct xfs_mount
*mp
= cur
->bc_mp
;
247 xfs_agnumber_t agno
= cur
->bc_ag
.pag
->pag_agno
;
248 union xfs_btree_rec
*rec
;
251 error
= xfs_btree_get_rec(cur
, &rec
, stat
);
252 if (error
|| !(*stat
))
255 *bno
= be32_to_cpu(rec
->alloc
.ar_startblock
);
256 *len
= be32_to_cpu(rec
->alloc
.ar_blockcount
);
261 /* check for valid extent range, including overflow */
262 if (!xfs_verify_agbno(mp
, agno
, *bno
))
264 if (*bno
> *bno
+ *len
)
266 if (!xfs_verify_agbno(mp
, agno
, *bno
+ *len
- 1))
273 "%s Freespace BTree record corruption in AG %d detected!",
274 cur
->bc_btnum
== XFS_BTNUM_BNO
? "Block" : "Size", agno
);
276 "start block 0x%x block count 0x%x", *bno
, *len
);
277 return -EFSCORRUPTED
;
281 * Compute aligned version of the found extent.
282 * Takes alignment and min length into account.
285 xfs_alloc_compute_aligned(
286 xfs_alloc_arg_t
*args
, /* allocation argument structure */
287 xfs_agblock_t foundbno
, /* starting block in found extent */
288 xfs_extlen_t foundlen
, /* length in found extent */
289 xfs_agblock_t
*resbno
, /* result block number */
290 xfs_extlen_t
*reslen
, /* result length */
293 xfs_agblock_t bno
= foundbno
;
294 xfs_extlen_t len
= foundlen
;
298 /* Trim busy sections out of found extent */
299 busy
= xfs_extent_busy_trim(args
, &bno
, &len
, busy_gen
);
302 * If we have a largish extent that happens to start before min_agbno,
303 * see if we can shift it into range...
305 if (bno
< args
->min_agbno
&& bno
+ len
> args
->min_agbno
) {
306 diff
= args
->min_agbno
- bno
;
313 if (args
->alignment
> 1 && len
>= args
->minlen
) {
314 xfs_agblock_t aligned_bno
= roundup(bno
, args
->alignment
);
316 diff
= aligned_bno
- bno
;
318 *resbno
= aligned_bno
;
319 *reslen
= diff
>= len
? 0 : len
- diff
;
329 * Compute best start block and diff for "near" allocations.
330 * freelen >= wantlen already checked by caller.
332 STATIC xfs_extlen_t
/* difference value (absolute) */
333 xfs_alloc_compute_diff(
334 xfs_agblock_t wantbno
, /* target starting block */
335 xfs_extlen_t wantlen
, /* target length */
336 xfs_extlen_t alignment
, /* target alignment */
337 int datatype
, /* are we allocating data? */
338 xfs_agblock_t freebno
, /* freespace's starting block */
339 xfs_extlen_t freelen
, /* freespace's length */
340 xfs_agblock_t
*newbnop
) /* result: best start block from free */
342 xfs_agblock_t freeend
; /* end of freespace extent */
343 xfs_agblock_t newbno1
; /* return block number */
344 xfs_agblock_t newbno2
; /* other new block number */
345 xfs_extlen_t newlen1
=0; /* length with newbno1 */
346 xfs_extlen_t newlen2
=0; /* length with newbno2 */
347 xfs_agblock_t wantend
; /* end of target extent */
348 bool userdata
= datatype
& XFS_ALLOC_USERDATA
;
350 ASSERT(freelen
>= wantlen
);
351 freeend
= freebno
+ freelen
;
352 wantend
= wantbno
+ wantlen
;
354 * We want to allocate from the start of a free extent if it is past
355 * the desired block or if we are allocating user data and the free
356 * extent is before desired block. The second case is there to allow
357 * for contiguous allocation from the remaining free space if the file
358 * grows in the short term.
360 if (freebno
>= wantbno
|| (userdata
&& freeend
< wantend
)) {
361 if ((newbno1
= roundup(freebno
, alignment
)) >= freeend
)
362 newbno1
= NULLAGBLOCK
;
363 } else if (freeend
>= wantend
&& alignment
> 1) {
364 newbno1
= roundup(wantbno
, alignment
);
365 newbno2
= newbno1
- alignment
;
366 if (newbno1
>= freeend
)
367 newbno1
= NULLAGBLOCK
;
369 newlen1
= XFS_EXTLEN_MIN(wantlen
, freeend
- newbno1
);
370 if (newbno2
< freebno
)
371 newbno2
= NULLAGBLOCK
;
373 newlen2
= XFS_EXTLEN_MIN(wantlen
, freeend
- newbno2
);
374 if (newbno1
!= NULLAGBLOCK
&& newbno2
!= NULLAGBLOCK
) {
375 if (newlen1
< newlen2
||
376 (newlen1
== newlen2
&&
377 XFS_ABSDIFF(newbno1
, wantbno
) >
378 XFS_ABSDIFF(newbno2
, wantbno
)))
380 } else if (newbno2
!= NULLAGBLOCK
)
382 } else if (freeend
>= wantend
) {
384 } else if (alignment
> 1) {
385 newbno1
= roundup(freeend
- wantlen
, alignment
);
386 if (newbno1
> freeend
- wantlen
&&
387 newbno1
- alignment
>= freebno
)
388 newbno1
-= alignment
;
389 else if (newbno1
>= freeend
)
390 newbno1
= NULLAGBLOCK
;
392 newbno1
= freeend
- wantlen
;
394 return newbno1
== NULLAGBLOCK
? 0 : XFS_ABSDIFF(newbno1
, wantbno
);
398 * Fix up the length, based on mod and prod.
399 * len should be k * prod + mod for some k.
400 * If len is too small it is returned unchanged.
401 * If len hits maxlen it is left alone.
405 xfs_alloc_arg_t
*args
) /* allocation argument structure */
410 ASSERT(args
->mod
< args
->prod
);
412 ASSERT(rlen
>= args
->minlen
);
413 ASSERT(rlen
<= args
->maxlen
);
414 if (args
->prod
<= 1 || rlen
< args
->mod
|| rlen
== args
->maxlen
||
415 (args
->mod
== 0 && rlen
< args
->prod
))
417 k
= rlen
% args
->prod
;
421 rlen
= rlen
- (k
- args
->mod
);
423 rlen
= rlen
- args
->prod
+ (args
->mod
- k
);
424 /* casts to (int) catch length underflows */
425 if ((int)rlen
< (int)args
->minlen
)
427 ASSERT(rlen
>= args
->minlen
&& rlen
<= args
->maxlen
);
428 ASSERT(rlen
% args
->prod
== args
->mod
);
429 ASSERT(args
->pag
->pagf_freeblks
+ args
->pag
->pagf_flcount
>=
430 rlen
+ args
->minleft
);
435 * Update the two btrees, logically removing from freespace the extent
436 * starting at rbno, rlen blocks. The extent is contained within the
437 * actual (current) free extent fbno for flen blocks.
438 * Flags are passed in indicating whether the cursors are set to the
441 STATIC
int /* error code */
442 xfs_alloc_fixup_trees(
443 struct xfs_btree_cur
*cnt_cur
, /* cursor for by-size btree */
444 struct xfs_btree_cur
*bno_cur
, /* cursor for by-block btree */
445 xfs_agblock_t fbno
, /* starting block of free extent */
446 xfs_extlen_t flen
, /* length of free extent */
447 xfs_agblock_t rbno
, /* starting block of returned extent */
448 xfs_extlen_t rlen
, /* length of returned extent */
449 int flags
) /* flags, XFSA_FIXUP_... */
451 int error
; /* error code */
452 int i
; /* operation results */
453 xfs_agblock_t nfbno1
; /* first new free startblock */
454 xfs_agblock_t nfbno2
; /* second new free startblock */
455 xfs_extlen_t nflen1
=0; /* first new free length */
456 xfs_extlen_t nflen2
=0; /* second new free length */
457 struct xfs_mount
*mp
;
462 * Look up the record in the by-size tree if necessary.
464 if (flags
& XFSA_FIXUP_CNT_OK
) {
466 if ((error
= xfs_alloc_get_rec(cnt_cur
, &nfbno1
, &nflen1
, &i
)))
468 if (XFS_IS_CORRUPT(mp
,
472 return -EFSCORRUPTED
;
475 if ((error
= xfs_alloc_lookup_eq(cnt_cur
, fbno
, flen
, &i
)))
477 if (XFS_IS_CORRUPT(mp
, i
!= 1))
478 return -EFSCORRUPTED
;
481 * Look up the record in the by-block tree if necessary.
483 if (flags
& XFSA_FIXUP_BNO_OK
) {
485 if ((error
= xfs_alloc_get_rec(bno_cur
, &nfbno1
, &nflen1
, &i
)))
487 if (XFS_IS_CORRUPT(mp
,
491 return -EFSCORRUPTED
;
494 if ((error
= xfs_alloc_lookup_eq(bno_cur
, fbno
, flen
, &i
)))
496 if (XFS_IS_CORRUPT(mp
, i
!= 1))
497 return -EFSCORRUPTED
;
501 if (bno_cur
->bc_nlevels
== 1 && cnt_cur
->bc_nlevels
== 1) {
502 struct xfs_btree_block
*bnoblock
;
503 struct xfs_btree_block
*cntblock
;
505 bnoblock
= XFS_BUF_TO_BLOCK(bno_cur
->bc_levels
[0].bp
);
506 cntblock
= XFS_BUF_TO_BLOCK(cnt_cur
->bc_levels
[0].bp
);
508 if (XFS_IS_CORRUPT(mp
,
509 bnoblock
->bb_numrecs
!=
510 cntblock
->bb_numrecs
))
511 return -EFSCORRUPTED
;
516 * Deal with all four cases: the allocated record is contained
517 * within the freespace record, so we can have new freespace
518 * at either (or both) end, or no freespace remaining.
520 if (rbno
== fbno
&& rlen
== flen
)
521 nfbno1
= nfbno2
= NULLAGBLOCK
;
522 else if (rbno
== fbno
) {
523 nfbno1
= rbno
+ rlen
;
524 nflen1
= flen
- rlen
;
525 nfbno2
= NULLAGBLOCK
;
526 } else if (rbno
+ rlen
== fbno
+ flen
) {
528 nflen1
= flen
- rlen
;
529 nfbno2
= NULLAGBLOCK
;
532 nflen1
= rbno
- fbno
;
533 nfbno2
= rbno
+ rlen
;
534 nflen2
= (fbno
+ flen
) - nfbno2
;
537 * Delete the entry from the by-size btree.
539 if ((error
= xfs_btree_delete(cnt_cur
, &i
)))
541 if (XFS_IS_CORRUPT(mp
, i
!= 1))
542 return -EFSCORRUPTED
;
544 * Add new by-size btree entry(s).
546 if (nfbno1
!= NULLAGBLOCK
) {
547 if ((error
= xfs_alloc_lookup_eq(cnt_cur
, nfbno1
, nflen1
, &i
)))
549 if (XFS_IS_CORRUPT(mp
, i
!= 0))
550 return -EFSCORRUPTED
;
551 if ((error
= xfs_btree_insert(cnt_cur
, &i
)))
553 if (XFS_IS_CORRUPT(mp
, i
!= 1))
554 return -EFSCORRUPTED
;
556 if (nfbno2
!= NULLAGBLOCK
) {
557 if ((error
= xfs_alloc_lookup_eq(cnt_cur
, nfbno2
, nflen2
, &i
)))
559 if (XFS_IS_CORRUPT(mp
, i
!= 0))
560 return -EFSCORRUPTED
;
561 if ((error
= xfs_btree_insert(cnt_cur
, &i
)))
563 if (XFS_IS_CORRUPT(mp
, i
!= 1))
564 return -EFSCORRUPTED
;
567 * Fix up the by-block btree entry(s).
569 if (nfbno1
== NULLAGBLOCK
) {
571 * No remaining freespace, just delete the by-block tree entry.
573 if ((error
= xfs_btree_delete(bno_cur
, &i
)))
575 if (XFS_IS_CORRUPT(mp
, i
!= 1))
576 return -EFSCORRUPTED
;
579 * Update the by-block entry to start later|be shorter.
581 if ((error
= xfs_alloc_update(bno_cur
, nfbno1
, nflen1
)))
584 if (nfbno2
!= NULLAGBLOCK
) {
586 * 2 resulting free entries, need to add one.
588 if ((error
= xfs_alloc_lookup_eq(bno_cur
, nfbno2
, nflen2
, &i
)))
590 if (XFS_IS_CORRUPT(mp
, i
!= 0))
591 return -EFSCORRUPTED
;
592 if ((error
= xfs_btree_insert(bno_cur
, &i
)))
594 if (XFS_IS_CORRUPT(mp
, i
!= 1))
595 return -EFSCORRUPTED
;
600 static xfs_failaddr_t
604 struct xfs_mount
*mp
= bp
->b_mount
;
605 struct xfs_agfl
*agfl
= XFS_BUF_TO_AGFL(bp
);
606 __be32
*agfl_bno
= xfs_buf_to_agfl_bno(bp
);
610 * There is no verification of non-crc AGFLs because mkfs does not
611 * initialise the AGFL to zero or NULL. Hence the only valid part of the
612 * AGFL is what the AGF says is active. We can't get to the AGF, so we
613 * can't verify just those entries are valid.
615 if (!xfs_has_crc(mp
))
618 if (!xfs_verify_magic(bp
, agfl
->agfl_magicnum
))
619 return __this_address
;
620 if (!uuid_equal(&agfl
->agfl_uuid
, &mp
->m_sb
.sb_meta_uuid
))
621 return __this_address
;
623 * during growfs operations, the perag is not fully initialised,
624 * so we can't use it for any useful checking. growfs ensures we can't
625 * use it by using uncached buffers that don't have the perag attached
626 * so we can detect and avoid this problem.
628 if (bp
->b_pag
&& be32_to_cpu(agfl
->agfl_seqno
) != bp
->b_pag
->pag_agno
)
629 return __this_address
;
631 for (i
= 0; i
< xfs_agfl_size(mp
); i
++) {
632 if (be32_to_cpu(agfl_bno
[i
]) != NULLAGBLOCK
&&
633 be32_to_cpu(agfl_bno
[i
]) >= mp
->m_sb
.sb_agblocks
)
634 return __this_address
;
637 if (!xfs_log_check_lsn(mp
, be64_to_cpu(XFS_BUF_TO_AGFL(bp
)->agfl_lsn
)))
638 return __this_address
;
643 xfs_agfl_read_verify(
646 struct xfs_mount
*mp
= bp
->b_mount
;
650 * There is no verification of non-crc AGFLs because mkfs does not
651 * initialise the AGFL to zero or NULL. Hence the only valid part of the
652 * AGFL is what the AGF says is active. We can't get to the AGF, so we
653 * can't verify just those entries are valid.
655 if (!xfs_has_crc(mp
))
658 if (!xfs_buf_verify_cksum(bp
, XFS_AGFL_CRC_OFF
))
659 xfs_verifier_error(bp
, -EFSBADCRC
, __this_address
);
661 fa
= xfs_agfl_verify(bp
);
663 xfs_verifier_error(bp
, -EFSCORRUPTED
, fa
);
668 xfs_agfl_write_verify(
671 struct xfs_mount
*mp
= bp
->b_mount
;
672 struct xfs_buf_log_item
*bip
= bp
->b_log_item
;
675 /* no verification of non-crc AGFLs */
676 if (!xfs_has_crc(mp
))
679 fa
= xfs_agfl_verify(bp
);
681 xfs_verifier_error(bp
, -EFSCORRUPTED
, fa
);
686 XFS_BUF_TO_AGFL(bp
)->agfl_lsn
= cpu_to_be64(bip
->bli_item
.li_lsn
);
688 xfs_buf_update_cksum(bp
, XFS_AGFL_CRC_OFF
);
691 const struct xfs_buf_ops xfs_agfl_buf_ops
= {
693 .magic
= { cpu_to_be32(XFS_AGFL_MAGIC
), cpu_to_be32(XFS_AGFL_MAGIC
) },
694 .verify_read
= xfs_agfl_read_verify
,
695 .verify_write
= xfs_agfl_write_verify
,
696 .verify_struct
= xfs_agfl_verify
,
700 * Read in the allocation group free block array.
704 xfs_mount_t
*mp
, /* mount point structure */
705 xfs_trans_t
*tp
, /* transaction pointer */
706 xfs_agnumber_t agno
, /* allocation group number */
707 struct xfs_buf
**bpp
) /* buffer for the ag free block array */
709 struct xfs_buf
*bp
; /* return value */
712 ASSERT(agno
!= NULLAGNUMBER
);
713 error
= xfs_trans_read_buf(
714 mp
, tp
, mp
->m_ddev_targp
,
715 XFS_AG_DADDR(mp
, agno
, XFS_AGFL_DADDR(mp
)),
716 XFS_FSS_TO_BB(mp
, 1), 0, &bp
, &xfs_agfl_buf_ops
);
719 xfs_buf_set_ref(bp
, XFS_AGFL_REF
);
725 xfs_alloc_update_counters(
726 struct xfs_trans
*tp
,
727 struct xfs_buf
*agbp
,
730 struct xfs_agf
*agf
= agbp
->b_addr
;
732 agbp
->b_pag
->pagf_freeblks
+= len
;
733 be32_add_cpu(&agf
->agf_freeblks
, len
);
735 if (unlikely(be32_to_cpu(agf
->agf_freeblks
) >
736 be32_to_cpu(agf
->agf_length
))) {
737 xfs_buf_mark_corrupt(agbp
);
738 return -EFSCORRUPTED
;
741 xfs_alloc_log_agf(tp
, agbp
, XFS_AGF_FREEBLKS
);
746 * Block allocation algorithm and data structures.
748 struct xfs_alloc_cur
{
749 struct xfs_btree_cur
*cnt
; /* btree cursors */
750 struct xfs_btree_cur
*bnolt
;
751 struct xfs_btree_cur
*bnogt
;
752 xfs_extlen_t cur_len
;/* current search length */
753 xfs_agblock_t rec_bno
;/* extent startblock */
754 xfs_extlen_t rec_len
;/* extent length */
755 xfs_agblock_t bno
; /* alloc bno */
756 xfs_extlen_t len
; /* alloc len */
757 xfs_extlen_t diff
; /* diff from search bno */
758 unsigned int busy_gen
;/* busy state */
763 * Set up cursors, etc. in the extent allocation cursor. This function can be
764 * called multiple times to reset an initialized structure without having to
765 * reallocate cursors.
769 struct xfs_alloc_arg
*args
,
770 struct xfs_alloc_cur
*acur
)
775 ASSERT(args
->alignment
== 1 || args
->type
!= XFS_ALLOCTYPE_THIS_BNO
);
777 acur
->cur_len
= args
->maxlen
;
787 * Perform an initial cntbt lookup to check for availability of maxlen
788 * extents. If this fails, we'll return -ENOSPC to signal the caller to
789 * attempt a small allocation.
792 acur
->cnt
= xfs_allocbt_init_cursor(args
->mp
, args
->tp
,
793 args
->agbp
, args
->pag
, XFS_BTNUM_CNT
);
794 error
= xfs_alloc_lookup_ge(acur
->cnt
, 0, args
->maxlen
, &i
);
799 * Allocate the bnobt left and right search cursors.
802 acur
->bnolt
= xfs_allocbt_init_cursor(args
->mp
, args
->tp
,
803 args
->agbp
, args
->pag
, XFS_BTNUM_BNO
);
805 acur
->bnogt
= xfs_allocbt_init_cursor(args
->mp
, args
->tp
,
806 args
->agbp
, args
->pag
, XFS_BTNUM_BNO
);
807 return i
== 1 ? 0 : -ENOSPC
;
812 struct xfs_alloc_cur
*acur
,
815 int cur_error
= XFS_BTREE_NOERROR
;
818 cur_error
= XFS_BTREE_ERROR
;
821 xfs_btree_del_cursor(acur
->cnt
, cur_error
);
823 xfs_btree_del_cursor(acur
->bnolt
, cur_error
);
825 xfs_btree_del_cursor(acur
->bnogt
, cur_error
);
826 acur
->cnt
= acur
->bnolt
= acur
->bnogt
= NULL
;
830 * Check an extent for allocation and track the best available candidate in the
831 * allocation structure. The cursor is deactivated if it has entered an out of
832 * range state based on allocation arguments. Optionally return the extent
833 * extent geometry and allocation status if requested by the caller.
837 struct xfs_alloc_arg
*args
,
838 struct xfs_alloc_cur
*acur
,
839 struct xfs_btree_cur
*cur
,
843 xfs_agblock_t bno
, bnoa
, bnew
;
844 xfs_extlen_t len
, lena
, diff
= -1;
846 unsigned busy_gen
= 0;
847 bool deactivate
= false;
848 bool isbnobt
= cur
->bc_btnum
== XFS_BTNUM_BNO
;
852 error
= xfs_alloc_get_rec(cur
, &bno
, &len
, &i
);
855 if (XFS_IS_CORRUPT(args
->mp
, i
!= 1))
856 return -EFSCORRUPTED
;
859 * Check minlen and deactivate a cntbt cursor if out of acceptable size
860 * range (i.e., walking backwards looking for a minlen extent).
862 if (len
< args
->minlen
) {
863 deactivate
= !isbnobt
;
867 busy
= xfs_alloc_compute_aligned(args
, bno
, len
, &bnoa
, &lena
,
871 acur
->busy_gen
= busy_gen
;
872 /* deactivate a bnobt cursor outside of locality range */
873 if (bnoa
< args
->min_agbno
|| bnoa
> args
->max_agbno
) {
874 deactivate
= isbnobt
;
877 if (lena
< args
->minlen
)
880 args
->len
= XFS_EXTLEN_MIN(lena
, args
->maxlen
);
881 xfs_alloc_fix_len(args
);
882 ASSERT(args
->len
>= args
->minlen
);
883 if (args
->len
< acur
->len
)
887 * We have an aligned record that satisfies minlen and beats or matches
888 * the candidate extent size. Compare locality for near allocation mode.
890 ASSERT(args
->type
== XFS_ALLOCTYPE_NEAR_BNO
);
891 diff
= xfs_alloc_compute_diff(args
->agbno
, args
->len
,
892 args
->alignment
, args
->datatype
,
894 if (bnew
== NULLAGBLOCK
)
898 * Deactivate a bnobt cursor with worse locality than the current best.
900 if (diff
> acur
->diff
) {
901 deactivate
= isbnobt
;
905 ASSERT(args
->len
> acur
->len
||
906 (args
->len
== acur
->len
&& diff
<= acur
->diff
));
910 acur
->len
= args
->len
;
915 * We're done if we found a perfect allocation. This only deactivates
916 * the current cursor, but this is just an optimization to terminate a
917 * cntbt search that otherwise runs to the edge of the tree.
919 if (acur
->diff
== 0 && acur
->len
== args
->maxlen
)
923 cur
->bc_ag
.abt
.active
= false;
924 trace_xfs_alloc_cur_check(args
->mp
, cur
->bc_btnum
, bno
, len
, diff
,
930 * Complete an allocation of a candidate extent. Remove the extent from both
931 * trees and update the args structure.
934 xfs_alloc_cur_finish(
935 struct xfs_alloc_arg
*args
,
936 struct xfs_alloc_cur
*acur
)
938 struct xfs_agf __maybe_unused
*agf
= args
->agbp
->b_addr
;
941 ASSERT(acur
->cnt
&& acur
->bnolt
);
942 ASSERT(acur
->bno
>= acur
->rec_bno
);
943 ASSERT(acur
->bno
+ acur
->len
<= acur
->rec_bno
+ acur
->rec_len
);
944 ASSERT(acur
->rec_bno
+ acur
->rec_len
<= be32_to_cpu(agf
->agf_length
));
946 error
= xfs_alloc_fixup_trees(acur
->cnt
, acur
->bnolt
, acur
->rec_bno
,
947 acur
->rec_len
, acur
->bno
, acur
->len
, 0);
951 args
->agbno
= acur
->bno
;
952 args
->len
= acur
->len
;
955 trace_xfs_alloc_cur(args
);
960 * Locality allocation lookup algorithm. This expects a cntbt cursor and uses
961 * bno optimized lookup to search for extents with ideal size and locality.
964 xfs_alloc_cntbt_iter(
965 struct xfs_alloc_arg
*args
,
966 struct xfs_alloc_cur
*acur
)
968 struct xfs_btree_cur
*cur
= acur
->cnt
;
970 xfs_extlen_t len
, cur_len
;
974 if (!xfs_alloc_cur_active(cur
))
977 /* locality optimized lookup */
978 cur_len
= acur
->cur_len
;
979 error
= xfs_alloc_lookup_ge(cur
, args
->agbno
, cur_len
, &i
);
984 error
= xfs_alloc_get_rec(cur
, &bno
, &len
, &i
);
988 /* check the current record and update search length from it */
989 error
= xfs_alloc_cur_check(args
, acur
, cur
, &i
);
992 ASSERT(len
>= acur
->cur_len
);
996 * We looked up the first record >= [agbno, len] above. The agbno is a
997 * secondary key and so the current record may lie just before or after
998 * agbno. If it is past agbno, check the previous record too so long as
999 * the length matches as it may be closer. Don't check a smaller record
1000 * because that could deactivate our cursor.
1002 if (bno
> args
->agbno
) {
1003 error
= xfs_btree_decrement(cur
, 0, &i
);
1005 error
= xfs_alloc_get_rec(cur
, &bno
, &len
, &i
);
1006 if (!error
&& i
&& len
== acur
->cur_len
)
1007 error
= xfs_alloc_cur_check(args
, acur
, cur
,
1015 * Increment the search key until we find at least one allocation
1016 * candidate or if the extent we found was larger. Otherwise, double the
1017 * search key to optimize the search. Efficiency is more important here
1018 * than absolute best locality.
1021 if (!acur
->len
|| acur
->cur_len
>= cur_len
)
1024 acur
->cur_len
= cur_len
;
1030 * Deal with the case where only small freespaces remain. Either return the
1031 * contents of the last freespace record, or allocate space from the freelist if
1032 * there is nothing in the tree.
1034 STATIC
int /* error */
1035 xfs_alloc_ag_vextent_small(
1036 struct xfs_alloc_arg
*args
, /* allocation argument structure */
1037 struct xfs_btree_cur
*ccur
, /* optional by-size cursor */
1038 xfs_agblock_t
*fbnop
, /* result block number */
1039 xfs_extlen_t
*flenp
, /* result length */
1040 int *stat
) /* status: 0-freelist, 1-normal/none */
1042 struct xfs_agf
*agf
= args
->agbp
->b_addr
;
1044 xfs_agblock_t fbno
= NULLAGBLOCK
;
1045 xfs_extlen_t flen
= 0;
1049 * If a cntbt cursor is provided, try to allocate the largest record in
1050 * the tree. Try the AGFL if the cntbt is empty, otherwise fail the
1051 * allocation. Make sure to respect minleft even when pulling from the
1055 error
= xfs_btree_decrement(ccur
, 0, &i
);
1059 error
= xfs_alloc_get_rec(ccur
, &fbno
, &flen
, &i
);
1062 if (XFS_IS_CORRUPT(args
->mp
, i
!= 1)) {
1063 error
= -EFSCORRUPTED
;
1069 if (args
->minlen
!= 1 || args
->alignment
!= 1 ||
1070 args
->resv
== XFS_AG_RESV_AGFL
||
1071 be32_to_cpu(agf
->agf_flcount
) <= args
->minleft
)
1074 error
= xfs_alloc_get_freelist(args
->tp
, args
->agbp
, &fbno
, 0);
1077 if (fbno
== NULLAGBLOCK
)
1080 xfs_extent_busy_reuse(args
->mp
, args
->pag
, fbno
, 1,
1081 (args
->datatype
& XFS_ALLOC_NOBUSY
));
1083 if (args
->datatype
& XFS_ALLOC_USERDATA
) {
1086 error
= xfs_trans_get_buf(args
->tp
, args
->mp
->m_ddev_targp
,
1087 XFS_AGB_TO_DADDR(args
->mp
, args
->agno
, fbno
),
1088 args
->mp
->m_bsize
, 0, &bp
);
1091 xfs_trans_binval(args
->tp
, bp
);
1093 *fbnop
= args
->agbno
= fbno
;
1094 *flenp
= args
->len
= 1;
1095 if (XFS_IS_CORRUPT(args
->mp
, fbno
>= be32_to_cpu(agf
->agf_length
))) {
1096 error
= -EFSCORRUPTED
;
1099 args
->wasfromfl
= 1;
1100 trace_xfs_alloc_small_freelist(args
);
1103 * If we're feeding an AGFL block to something that doesn't live in the
1104 * free space, we need to clear out the OWN_AG rmap.
1106 error
= xfs_rmap_free(args
->tp
, args
->agbp
, args
->pag
, fbno
, 1,
1107 &XFS_RMAP_OINFO_AG
);
1116 * Can't do the allocation, give up.
1118 if (flen
< args
->minlen
) {
1119 args
->agbno
= NULLAGBLOCK
;
1120 trace_xfs_alloc_small_notenough(args
);
1126 trace_xfs_alloc_small_done(args
);
1130 trace_xfs_alloc_small_error(args
);
1135 * Allocate a variable extent in the allocation group agno.
1136 * Type and bno are used to determine where in the allocation group the
1137 * extent will start.
1138 * Extent's length (returned in *len) will be between minlen and maxlen,
1139 * and of the form k * prod + mod unless there's nothing that large.
1140 * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
1142 STATIC
int /* error */
1143 xfs_alloc_ag_vextent(
1144 xfs_alloc_arg_t
*args
) /* argument structure for allocation */
1148 ASSERT(args
->minlen
> 0);
1149 ASSERT(args
->maxlen
> 0);
1150 ASSERT(args
->minlen
<= args
->maxlen
);
1151 ASSERT(args
->mod
< args
->prod
);
1152 ASSERT(args
->alignment
> 0);
1155 * Branch to correct routine based on the type.
1157 args
->wasfromfl
= 0;
1158 switch (args
->type
) {
1159 case XFS_ALLOCTYPE_THIS_AG
:
1160 error
= xfs_alloc_ag_vextent_size(args
);
1162 case XFS_ALLOCTYPE_NEAR_BNO
:
1163 error
= xfs_alloc_ag_vextent_near(args
);
1165 case XFS_ALLOCTYPE_THIS_BNO
:
1166 error
= xfs_alloc_ag_vextent_exact(args
);
1173 if (error
|| args
->agbno
== NULLAGBLOCK
)
1176 ASSERT(args
->len
>= args
->minlen
);
1177 ASSERT(args
->len
<= args
->maxlen
);
1178 ASSERT(!args
->wasfromfl
|| args
->resv
!= XFS_AG_RESV_AGFL
);
1179 ASSERT(args
->agbno
% args
->alignment
== 0);
1181 /* if not file data, insert new block into the reverse map btree */
1182 if (!xfs_rmap_should_skip_owner_update(&args
->oinfo
)) {
1183 error
= xfs_rmap_alloc(args
->tp
, args
->agbp
, args
->pag
,
1184 args
->agbno
, args
->len
, &args
->oinfo
);
1189 if (!args
->wasfromfl
) {
1190 error
= xfs_alloc_update_counters(args
->tp
, args
->agbp
,
1191 -((long)(args
->len
)));
1195 ASSERT(!xfs_extent_busy_search(args
->mp
, args
->pag
,
1196 args
->agbno
, args
->len
));
1199 xfs_ag_resv_alloc_extent(args
->pag
, args
->resv
, args
);
1201 XFS_STATS_INC(args
->mp
, xs_allocx
);
1202 XFS_STATS_ADD(args
->mp
, xs_allocb
, args
->len
);
1207 * Allocate a variable extent at exactly agno/bno.
1208 * Extent's length (returned in *len) will be between minlen and maxlen,
1209 * and of the form k * prod + mod unless there's nothing that large.
1210 * Return the starting a.g. block (bno), or NULLAGBLOCK if we can't do it.
1212 STATIC
int /* error */
1213 xfs_alloc_ag_vextent_exact(
1214 xfs_alloc_arg_t
*args
) /* allocation argument structure */
1216 struct xfs_agf __maybe_unused
*agf
= args
->agbp
->b_addr
;
1217 struct xfs_btree_cur
*bno_cur
;/* by block-number btree cursor */
1218 struct xfs_btree_cur
*cnt_cur
;/* by count btree cursor */
1220 xfs_agblock_t fbno
; /* start block of found extent */
1221 xfs_extlen_t flen
; /* length of found extent */
1222 xfs_agblock_t tbno
; /* start block of busy extent */
1223 xfs_extlen_t tlen
; /* length of busy extent */
1224 xfs_agblock_t tend
; /* end block of busy extent */
1225 int i
; /* success/failure of operation */
1228 ASSERT(args
->alignment
== 1);
1231 * Allocate/initialize a cursor for the by-number freespace btree.
1233 bno_cur
= xfs_allocbt_init_cursor(args
->mp
, args
->tp
, args
->agbp
,
1234 args
->pag
, XFS_BTNUM_BNO
);
1237 * Lookup bno and minlen in the btree (minlen is irrelevant, really).
1238 * Look for the closest free block <= bno, it must contain bno
1239 * if any free block does.
1241 error
= xfs_alloc_lookup_le(bno_cur
, args
->agbno
, args
->minlen
, &i
);
1248 * Grab the freespace record.
1250 error
= xfs_alloc_get_rec(bno_cur
, &fbno
, &flen
, &i
);
1253 if (XFS_IS_CORRUPT(args
->mp
, i
!= 1)) {
1254 error
= -EFSCORRUPTED
;
1257 ASSERT(fbno
<= args
->agbno
);
1260 * Check for overlapping busy extents.
1264 xfs_extent_busy_trim(args
, &tbno
, &tlen
, &busy_gen
);
1267 * Give up if the start of the extent is busy, or the freespace isn't
1268 * long enough for the minimum request.
1270 if (tbno
> args
->agbno
)
1272 if (tlen
< args
->minlen
)
1275 if (tend
< args
->agbno
+ args
->minlen
)
1279 * End of extent will be smaller of the freespace end and the
1280 * maximal requested end.
1282 * Fix the length according to mod and prod if given.
1284 args
->len
= XFS_AGBLOCK_MIN(tend
, args
->agbno
+ args
->maxlen
)
1286 xfs_alloc_fix_len(args
);
1287 ASSERT(args
->agbno
+ args
->len
<= tend
);
1290 * We are allocating agbno for args->len
1291 * Allocate/initialize a cursor for the by-size btree.
1293 cnt_cur
= xfs_allocbt_init_cursor(args
->mp
, args
->tp
, args
->agbp
,
1294 args
->pag
, XFS_BTNUM_CNT
);
1295 ASSERT(args
->agbno
+ args
->len
<= be32_to_cpu(agf
->agf_length
));
1296 error
= xfs_alloc_fixup_trees(cnt_cur
, bno_cur
, fbno
, flen
, args
->agbno
,
1297 args
->len
, XFSA_FIXUP_BNO_OK
);
1299 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_ERROR
);
1303 xfs_btree_del_cursor(bno_cur
, XFS_BTREE_NOERROR
);
1304 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_NOERROR
);
1306 args
->wasfromfl
= 0;
1307 trace_xfs_alloc_exact_done(args
);
1311 /* Didn't find it, return null. */
1312 xfs_btree_del_cursor(bno_cur
, XFS_BTREE_NOERROR
);
1313 args
->agbno
= NULLAGBLOCK
;
1314 trace_xfs_alloc_exact_notfound(args
);
1318 xfs_btree_del_cursor(bno_cur
, XFS_BTREE_ERROR
);
1319 trace_xfs_alloc_exact_error(args
);
1324 * Search a given number of btree records in a given direction. Check each
1325 * record against the good extent we've already found.
1328 xfs_alloc_walk_iter(
1329 struct xfs_alloc_arg
*args
,
1330 struct xfs_alloc_cur
*acur
,
1331 struct xfs_btree_cur
*cur
,
1333 bool find_one
, /* quit on first candidate */
1334 int count
, /* rec count (-1 for infinite) */
1343 * Search so long as the cursor is active or we find a better extent.
1344 * The cursor is deactivated if it extends beyond the range of the
1345 * current allocation candidate.
1347 while (xfs_alloc_cur_active(cur
) && count
) {
1348 error
= xfs_alloc_cur_check(args
, acur
, cur
, &i
);
1356 if (!xfs_alloc_cur_active(cur
))
1360 error
= xfs_btree_increment(cur
, 0, &i
);
1362 error
= xfs_btree_decrement(cur
, 0, &i
);
1366 cur
->bc_ag
.abt
.active
= false;
1376 * Search the by-bno and by-size btrees in parallel in search of an extent with
1377 * ideal locality based on the NEAR mode ->agbno locality hint.
1380 xfs_alloc_ag_vextent_locality(
1381 struct xfs_alloc_arg
*args
,
1382 struct xfs_alloc_cur
*acur
,
1385 struct xfs_btree_cur
*fbcur
= NULL
;
1390 ASSERT(acur
->len
== 0);
1391 ASSERT(args
->type
== XFS_ALLOCTYPE_NEAR_BNO
);
1395 error
= xfs_alloc_lookup_ge(acur
->cnt
, args
->agbno
, acur
->cur_len
, &i
);
1398 error
= xfs_alloc_lookup_le(acur
->bnolt
, args
->agbno
, 0, &i
);
1401 error
= xfs_alloc_lookup_ge(acur
->bnogt
, args
->agbno
, 0, &i
);
1406 * Search the bnobt and cntbt in parallel. Search the bnobt left and
1407 * right and lookup the closest extent to the locality hint for each
1408 * extent size key in the cntbt. The entire search terminates
1409 * immediately on a bnobt hit because that means we've found best case
1410 * locality. Otherwise the search continues until the cntbt cursor runs
1411 * off the end of the tree. If no allocation candidate is found at this
1412 * point, give up on locality, walk backwards from the end of the cntbt
1413 * and take the first available extent.
1415 * The parallel tree searches balance each other out to provide fairly
1416 * consistent performance for various situations. The bnobt search can
1417 * have pathological behavior in the worst case scenario of larger
1418 * allocation requests and fragmented free space. On the other hand, the
1419 * bnobt is able to satisfy most smaller allocation requests much more
1420 * quickly than the cntbt. The cntbt search can sift through fragmented
1421 * free space and sets of free extents for larger allocation requests
1422 * more quickly than the bnobt. Since the locality hint is just a hint
1423 * and we don't want to scan the entire bnobt for perfect locality, the
1424 * cntbt search essentially bounds the bnobt search such that we can
1425 * find good enough locality at reasonable performance in most cases.
1427 while (xfs_alloc_cur_active(acur
->bnolt
) ||
1428 xfs_alloc_cur_active(acur
->bnogt
) ||
1429 xfs_alloc_cur_active(acur
->cnt
)) {
1431 trace_xfs_alloc_cur_lookup(args
);
1434 * Search the bnobt left and right. In the case of a hit, finish
1435 * the search in the opposite direction and we're done.
1437 error
= xfs_alloc_walk_iter(args
, acur
, acur
->bnolt
, false,
1442 trace_xfs_alloc_cur_left(args
);
1443 fbcur
= acur
->bnogt
;
1447 error
= xfs_alloc_walk_iter(args
, acur
, acur
->bnogt
, true, true,
1452 trace_xfs_alloc_cur_right(args
);
1453 fbcur
= acur
->bnolt
;
1459 * Check the extent with best locality based on the current
1460 * extent size search key and keep track of the best candidate.
1462 error
= xfs_alloc_cntbt_iter(args
, acur
);
1465 if (!xfs_alloc_cur_active(acur
->cnt
)) {
1466 trace_xfs_alloc_cur_lookup_done(args
);
1472 * If we failed to find anything due to busy extents, return empty
1473 * handed so the caller can flush and retry. If no busy extents were
1474 * found, walk backwards from the end of the cntbt as a last resort.
1476 if (!xfs_alloc_cur_active(acur
->cnt
) && !acur
->len
&& !acur
->busy
) {
1477 error
= xfs_btree_decrement(acur
->cnt
, 0, &i
);
1481 acur
->cnt
->bc_ag
.abt
.active
= true;
1488 * Search in the opposite direction for a better entry in the case of
1489 * a bnobt hit or walk backwards from the end of the cntbt.
1492 error
= xfs_alloc_walk_iter(args
, acur
, fbcur
, fbinc
, true, -1,
1504 /* Check the last block of the cnt btree for allocations. */
1506 xfs_alloc_ag_vextent_lastblock(
1507 struct xfs_alloc_arg
*args
,
1508 struct xfs_alloc_cur
*acur
,
1517 /* Randomly don't execute the first algorithm. */
1518 if (prandom_u32() & 1)
1523 * Start from the entry that lookup found, sequence through all larger
1524 * free blocks. If we're actually pointing at a record smaller than
1525 * maxlen, go to the start of this block, and skip all those smaller
1528 if (*len
|| args
->alignment
> 1) {
1529 acur
->cnt
->bc_levels
[0].ptr
= 1;
1531 error
= xfs_alloc_get_rec(acur
->cnt
, bno
, len
, &i
);
1534 if (XFS_IS_CORRUPT(args
->mp
, i
!= 1))
1535 return -EFSCORRUPTED
;
1536 if (*len
>= args
->minlen
)
1538 error
= xfs_btree_increment(acur
->cnt
, 0, &i
);
1542 ASSERT(*len
>= args
->minlen
);
1547 error
= xfs_alloc_walk_iter(args
, acur
, acur
->cnt
, true, false, -1, &i
);
1552 * It didn't work. We COULD be in a case where there's a good record
1553 * somewhere, so try again.
1558 trace_xfs_alloc_near_first(args
);
1564 * Allocate a variable extent near bno in the allocation group agno.
1565 * Extent's length (returned in len) will be between minlen and maxlen,
1566 * and of the form k * prod + mod unless there's nothing that large.
1567 * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
1570 xfs_alloc_ag_vextent_near(
1571 struct xfs_alloc_arg
*args
)
1573 struct xfs_alloc_cur acur
= {};
1574 int error
; /* error code */
1575 int i
; /* result code, temporary */
1579 /* handle uninitialized agbno range so caller doesn't have to */
1580 if (!args
->min_agbno
&& !args
->max_agbno
)
1581 args
->max_agbno
= args
->mp
->m_sb
.sb_agblocks
- 1;
1582 ASSERT(args
->min_agbno
<= args
->max_agbno
);
1584 /* clamp agbno to the range if it's outside */
1585 if (args
->agbno
< args
->min_agbno
)
1586 args
->agbno
= args
->min_agbno
;
1587 if (args
->agbno
> args
->max_agbno
)
1588 args
->agbno
= args
->max_agbno
;
1594 * Set up cursors and see if there are any free extents as big as
1595 * maxlen. If not, pick the last entry in the tree unless the tree is
1598 error
= xfs_alloc_cur_setup(args
, &acur
);
1599 if (error
== -ENOSPC
) {
1600 error
= xfs_alloc_ag_vextent_small(args
, acur
.cnt
, &bno
,
1604 if (i
== 0 || len
== 0) {
1605 trace_xfs_alloc_near_noentry(args
);
1615 * If the requested extent is large wrt the freespaces available
1616 * in this a.g., then the cursor will be pointing to a btree entry
1617 * near the right edge of the tree. If it's in the last btree leaf
1618 * block, then we just examine all the entries in that block
1619 * that are big enough, and pick the best one.
1621 if (xfs_btree_islastblock(acur
.cnt
, 0)) {
1622 bool allocated
= false;
1624 error
= xfs_alloc_ag_vextent_lastblock(args
, &acur
, &bno
, &len
,
1633 * Second algorithm. Combined cntbt and bnobt search to find ideal
1636 error
= xfs_alloc_ag_vextent_locality(args
, &acur
, &i
);
1641 * If we couldn't get anything, give up.
1645 trace_xfs_alloc_near_busy(args
);
1646 xfs_extent_busy_flush(args
->mp
, args
->pag
,
1650 trace_xfs_alloc_size_neither(args
);
1651 args
->agbno
= NULLAGBLOCK
;
1656 /* fix up btrees on a successful allocation */
1657 error
= xfs_alloc_cur_finish(args
, &acur
);
1660 xfs_alloc_cur_close(&acur
, error
);
1665 * Allocate a variable extent anywhere in the allocation group agno.
1666 * Extent's length (returned in len) will be between minlen and maxlen,
1667 * and of the form k * prod + mod unless there's nothing that large.
1668 * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
1670 STATIC
int /* error */
1671 xfs_alloc_ag_vextent_size(
1672 xfs_alloc_arg_t
*args
) /* allocation argument structure */
1674 struct xfs_agf
*agf
= args
->agbp
->b_addr
;
1675 struct xfs_btree_cur
*bno_cur
; /* cursor for bno btree */
1676 struct xfs_btree_cur
*cnt_cur
; /* cursor for cnt btree */
1677 int error
; /* error result */
1678 xfs_agblock_t fbno
; /* start of found freespace */
1679 xfs_extlen_t flen
; /* length of found freespace */
1680 int i
; /* temp status variable */
1681 xfs_agblock_t rbno
; /* returned block number */
1682 xfs_extlen_t rlen
; /* length of returned extent */
1688 * Allocate and initialize a cursor for the by-size btree.
1690 cnt_cur
= xfs_allocbt_init_cursor(args
->mp
, args
->tp
, args
->agbp
,
1691 args
->pag
, XFS_BTNUM_CNT
);
1695 * Look for an entry >= maxlen+alignment-1 blocks.
1697 if ((error
= xfs_alloc_lookup_ge(cnt_cur
, 0,
1698 args
->maxlen
+ args
->alignment
- 1, &i
)))
1702 * If none then we have to settle for a smaller extent. In the case that
1703 * there are no large extents, this will return the last entry in the
1704 * tree unless the tree is empty. In the case that there are only busy
1705 * large extents, this will return the largest small extent unless there
1706 * are no smaller extents available.
1709 error
= xfs_alloc_ag_vextent_small(args
, cnt_cur
,
1713 if (i
== 0 || flen
== 0) {
1714 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_NOERROR
);
1715 trace_xfs_alloc_size_noentry(args
);
1719 busy
= xfs_alloc_compute_aligned(args
, fbno
, flen
, &rbno
,
1723 * Search for a non-busy extent that is large enough.
1726 error
= xfs_alloc_get_rec(cnt_cur
, &fbno
, &flen
, &i
);
1729 if (XFS_IS_CORRUPT(args
->mp
, i
!= 1)) {
1730 error
= -EFSCORRUPTED
;
1734 busy
= xfs_alloc_compute_aligned(args
, fbno
, flen
,
1735 &rbno
, &rlen
, &busy_gen
);
1737 if (rlen
>= args
->maxlen
)
1740 error
= xfs_btree_increment(cnt_cur
, 0, &i
);
1745 * Our only valid extents must have been busy.
1746 * Make it unbusy by forcing the log out and
1749 xfs_btree_del_cursor(cnt_cur
,
1751 trace_xfs_alloc_size_busy(args
);
1752 xfs_extent_busy_flush(args
->mp
,
1753 args
->pag
, busy_gen
);
1760 * In the first case above, we got the last entry in the
1761 * by-size btree. Now we check to see if the space hits maxlen
1762 * once aligned; if not, we search left for something better.
1763 * This can't happen in the second case above.
1765 rlen
= XFS_EXTLEN_MIN(args
->maxlen
, rlen
);
1766 if (XFS_IS_CORRUPT(args
->mp
,
1769 rbno
+ rlen
> fbno
+ flen
))) {
1770 error
= -EFSCORRUPTED
;
1773 if (rlen
< args
->maxlen
) {
1774 xfs_agblock_t bestfbno
;
1775 xfs_extlen_t bestflen
;
1776 xfs_agblock_t bestrbno
;
1777 xfs_extlen_t bestrlen
;
1784 if ((error
= xfs_btree_decrement(cnt_cur
, 0, &i
)))
1788 if ((error
= xfs_alloc_get_rec(cnt_cur
, &fbno
, &flen
,
1791 if (XFS_IS_CORRUPT(args
->mp
, i
!= 1)) {
1792 error
= -EFSCORRUPTED
;
1795 if (flen
< bestrlen
)
1797 busy
= xfs_alloc_compute_aligned(args
, fbno
, flen
,
1798 &rbno
, &rlen
, &busy_gen
);
1799 rlen
= XFS_EXTLEN_MIN(args
->maxlen
, rlen
);
1800 if (XFS_IS_CORRUPT(args
->mp
,
1803 rbno
+ rlen
> fbno
+ flen
))) {
1804 error
= -EFSCORRUPTED
;
1807 if (rlen
> bestrlen
) {
1812 if (rlen
== args
->maxlen
)
1816 if ((error
= xfs_alloc_lookup_eq(cnt_cur
, bestfbno
, bestflen
,
1819 if (XFS_IS_CORRUPT(args
->mp
, i
!= 1)) {
1820 error
= -EFSCORRUPTED
;
1828 args
->wasfromfl
= 0;
1830 * Fix up the length.
1833 if (rlen
< args
->minlen
) {
1835 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_NOERROR
);
1836 trace_xfs_alloc_size_busy(args
);
1837 xfs_extent_busy_flush(args
->mp
, args
->pag
, busy_gen
);
1842 xfs_alloc_fix_len(args
);
1845 if (XFS_IS_CORRUPT(args
->mp
, rlen
> flen
)) {
1846 error
= -EFSCORRUPTED
;
1850 * Allocate and initialize a cursor for the by-block tree.
1852 bno_cur
= xfs_allocbt_init_cursor(args
->mp
, args
->tp
, args
->agbp
,
1853 args
->pag
, XFS_BTNUM_BNO
);
1854 if ((error
= xfs_alloc_fixup_trees(cnt_cur
, bno_cur
, fbno
, flen
,
1855 rbno
, rlen
, XFSA_FIXUP_CNT_OK
)))
1857 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_NOERROR
);
1858 xfs_btree_del_cursor(bno_cur
, XFS_BTREE_NOERROR
);
1859 cnt_cur
= bno_cur
= NULL
;
1862 if (XFS_IS_CORRUPT(args
->mp
,
1863 args
->agbno
+ args
->len
>
1864 be32_to_cpu(agf
->agf_length
))) {
1865 error
= -EFSCORRUPTED
;
1868 trace_xfs_alloc_size_done(args
);
1872 trace_xfs_alloc_size_error(args
);
1874 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_ERROR
);
1876 xfs_btree_del_cursor(bno_cur
, XFS_BTREE_ERROR
);
1880 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_NOERROR
);
1881 trace_xfs_alloc_size_nominleft(args
);
1882 args
->agbno
= NULLAGBLOCK
;
1887 * Free the extent starting at agno/bno for length.
1891 struct xfs_trans
*tp
,
1892 struct xfs_buf
*agbp
,
1893 xfs_agnumber_t agno
,
1896 const struct xfs_owner_info
*oinfo
,
1897 enum xfs_ag_resv_type type
)
1899 struct xfs_mount
*mp
;
1900 struct xfs_btree_cur
*bno_cur
;
1901 struct xfs_btree_cur
*cnt_cur
;
1902 xfs_agblock_t gtbno
; /* start of right neighbor */
1903 xfs_extlen_t gtlen
; /* length of right neighbor */
1904 xfs_agblock_t ltbno
; /* start of left neighbor */
1905 xfs_extlen_t ltlen
; /* length of left neighbor */
1906 xfs_agblock_t nbno
; /* new starting block of freesp */
1907 xfs_extlen_t nlen
; /* new length of freespace */
1908 int haveleft
; /* have a left neighbor */
1909 int haveright
; /* have a right neighbor */
1912 struct xfs_perag
*pag
= agbp
->b_pag
;
1914 bno_cur
= cnt_cur
= NULL
;
1917 if (!xfs_rmap_should_skip_owner_update(oinfo
)) {
1918 error
= xfs_rmap_free(tp
, agbp
, pag
, bno
, len
, oinfo
);
1924 * Allocate and initialize a cursor for the by-block btree.
1926 bno_cur
= xfs_allocbt_init_cursor(mp
, tp
, agbp
, pag
, XFS_BTNUM_BNO
);
1928 * Look for a neighboring block on the left (lower block numbers)
1929 * that is contiguous with this space.
1931 if ((error
= xfs_alloc_lookup_le(bno_cur
, bno
, len
, &haveleft
)))
1935 * There is a block to our left.
1937 if ((error
= xfs_alloc_get_rec(bno_cur
, <bno
, <len
, &i
)))
1939 if (XFS_IS_CORRUPT(mp
, i
!= 1)) {
1940 error
= -EFSCORRUPTED
;
1944 * It's not contiguous, though.
1946 if (ltbno
+ ltlen
< bno
)
1950 * If this failure happens the request to free this
1951 * space was invalid, it's (partly) already free.
1954 if (XFS_IS_CORRUPT(mp
, ltbno
+ ltlen
> bno
)) {
1955 error
= -EFSCORRUPTED
;
1961 * Look for a neighboring block on the right (higher block numbers)
1962 * that is contiguous with this space.
1964 if ((error
= xfs_btree_increment(bno_cur
, 0, &haveright
)))
1968 * There is a block to our right.
1970 if ((error
= xfs_alloc_get_rec(bno_cur
, >bno
, >len
, &i
)))
1972 if (XFS_IS_CORRUPT(mp
, i
!= 1)) {
1973 error
= -EFSCORRUPTED
;
1977 * It's not contiguous, though.
1979 if (bno
+ len
< gtbno
)
1983 * If this failure happens the request to free this
1984 * space was invalid, it's (partly) already free.
1987 if (XFS_IS_CORRUPT(mp
, bno
+ len
> gtbno
)) {
1988 error
= -EFSCORRUPTED
;
1994 * Now allocate and initialize a cursor for the by-size tree.
1996 cnt_cur
= xfs_allocbt_init_cursor(mp
, tp
, agbp
, pag
, XFS_BTNUM_CNT
);
1998 * Have both left and right contiguous neighbors.
1999 * Merge all three into a single free block.
2001 if (haveleft
&& haveright
) {
2003 * Delete the old by-size entry on the left.
2005 if ((error
= xfs_alloc_lookup_eq(cnt_cur
, ltbno
, ltlen
, &i
)))
2007 if (XFS_IS_CORRUPT(mp
, i
!= 1)) {
2008 error
= -EFSCORRUPTED
;
2011 if ((error
= xfs_btree_delete(cnt_cur
, &i
)))
2013 if (XFS_IS_CORRUPT(mp
, i
!= 1)) {
2014 error
= -EFSCORRUPTED
;
2018 * Delete the old by-size entry on the right.
2020 if ((error
= xfs_alloc_lookup_eq(cnt_cur
, gtbno
, gtlen
, &i
)))
2022 if (XFS_IS_CORRUPT(mp
, i
!= 1)) {
2023 error
= -EFSCORRUPTED
;
2026 if ((error
= xfs_btree_delete(cnt_cur
, &i
)))
2028 if (XFS_IS_CORRUPT(mp
, i
!= 1)) {
2029 error
= -EFSCORRUPTED
;
2033 * Delete the old by-block entry for the right block.
2035 if ((error
= xfs_btree_delete(bno_cur
, &i
)))
2037 if (XFS_IS_CORRUPT(mp
, i
!= 1)) {
2038 error
= -EFSCORRUPTED
;
2042 * Move the by-block cursor back to the left neighbor.
2044 if ((error
= xfs_btree_decrement(bno_cur
, 0, &i
)))
2046 if (XFS_IS_CORRUPT(mp
, i
!= 1)) {
2047 error
= -EFSCORRUPTED
;
2052 * Check that this is the right record: delete didn't
2053 * mangle the cursor.
2056 xfs_agblock_t xxbno
;
2059 if ((error
= xfs_alloc_get_rec(bno_cur
, &xxbno
, &xxlen
,
2062 if (XFS_IS_CORRUPT(mp
,
2066 error
= -EFSCORRUPTED
;
2072 * Update remaining by-block entry to the new, joined block.
2075 nlen
= len
+ ltlen
+ gtlen
;
2076 if ((error
= xfs_alloc_update(bno_cur
, nbno
, nlen
)))
2080 * Have only a left contiguous neighbor.
2081 * Merge it together with the new freespace.
2083 else if (haveleft
) {
2085 * Delete the old by-size entry on the left.
2087 if ((error
= xfs_alloc_lookup_eq(cnt_cur
, ltbno
, ltlen
, &i
)))
2089 if (XFS_IS_CORRUPT(mp
, i
!= 1)) {
2090 error
= -EFSCORRUPTED
;
2093 if ((error
= xfs_btree_delete(cnt_cur
, &i
)))
2095 if (XFS_IS_CORRUPT(mp
, i
!= 1)) {
2096 error
= -EFSCORRUPTED
;
2100 * Back up the by-block cursor to the left neighbor, and
2101 * update its length.
2103 if ((error
= xfs_btree_decrement(bno_cur
, 0, &i
)))
2105 if (XFS_IS_CORRUPT(mp
, i
!= 1)) {
2106 error
= -EFSCORRUPTED
;
2111 if ((error
= xfs_alloc_update(bno_cur
, nbno
, nlen
)))
2115 * Have only a right contiguous neighbor.
2116 * Merge it together with the new freespace.
2118 else if (haveright
) {
2120 * Delete the old by-size entry on the right.
2122 if ((error
= xfs_alloc_lookup_eq(cnt_cur
, gtbno
, gtlen
, &i
)))
2124 if (XFS_IS_CORRUPT(mp
, i
!= 1)) {
2125 error
= -EFSCORRUPTED
;
2128 if ((error
= xfs_btree_delete(cnt_cur
, &i
)))
2130 if (XFS_IS_CORRUPT(mp
, i
!= 1)) {
2131 error
= -EFSCORRUPTED
;
2135 * Update the starting block and length of the right
2136 * neighbor in the by-block tree.
2140 if ((error
= xfs_alloc_update(bno_cur
, nbno
, nlen
)))
2144 * No contiguous neighbors.
2145 * Insert the new freespace into the by-block tree.
2150 if ((error
= xfs_btree_insert(bno_cur
, &i
)))
2152 if (XFS_IS_CORRUPT(mp
, i
!= 1)) {
2153 error
= -EFSCORRUPTED
;
2157 xfs_btree_del_cursor(bno_cur
, XFS_BTREE_NOERROR
);
2160 * In all cases we need to insert the new freespace in the by-size tree.
2162 if ((error
= xfs_alloc_lookup_eq(cnt_cur
, nbno
, nlen
, &i
)))
2164 if (XFS_IS_CORRUPT(mp
, i
!= 0)) {
2165 error
= -EFSCORRUPTED
;
2168 if ((error
= xfs_btree_insert(cnt_cur
, &i
)))
2170 if (XFS_IS_CORRUPT(mp
, i
!= 1)) {
2171 error
= -EFSCORRUPTED
;
2174 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_NOERROR
);
2178 * Update the freespace totals in the ag and superblock.
2180 error
= xfs_alloc_update_counters(tp
, agbp
, len
);
2181 xfs_ag_resv_free_extent(agbp
->b_pag
, type
, tp
, len
);
2185 XFS_STATS_INC(mp
, xs_freex
);
2186 XFS_STATS_ADD(mp
, xs_freeb
, len
);
2188 trace_xfs_free_extent(mp
, agno
, bno
, len
, type
, haveleft
, haveright
);
2193 trace_xfs_free_extent(mp
, agno
, bno
, len
, type
, -1, -1);
2195 xfs_btree_del_cursor(bno_cur
, XFS_BTREE_ERROR
);
2197 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_ERROR
);
2202 * Visible (exported) allocation/free functions.
2203 * Some of these are used just by xfs_alloc_btree.c and this file.
2207 * Compute and fill in value of m_alloc_maxlevels.
2210 xfs_alloc_compute_maxlevels(
2211 xfs_mount_t
*mp
) /* file system mount structure */
2213 mp
->m_alloc_maxlevels
= xfs_btree_compute_maxlevels(mp
->m_alloc_mnr
,
2214 (mp
->m_sb
.sb_agblocks
+ 1) / 2);
2215 ASSERT(mp
->m_alloc_maxlevels
<= xfs_allocbt_maxlevels_ondisk());
2219 * Find the length of the longest extent in an AG. The 'need' parameter
2220 * specifies how much space we're going to need for the AGFL and the
2221 * 'reserved' parameter tells us how many blocks in this AG are reserved for
2225 xfs_alloc_longest_free_extent(
2226 struct xfs_perag
*pag
,
2228 xfs_extlen_t reserved
)
2230 xfs_extlen_t delta
= 0;
2233 * If the AGFL needs a recharge, we'll have to subtract that from the
2236 if (need
> pag
->pagf_flcount
)
2237 delta
= need
- pag
->pagf_flcount
;
2240 * If we cannot maintain others' reservations with space from the
2241 * not-longest freesp extents, we'll have to subtract /that/ from
2242 * the longest extent too.
2244 if (pag
->pagf_freeblks
- pag
->pagf_longest
< reserved
)
2245 delta
+= reserved
- (pag
->pagf_freeblks
- pag
->pagf_longest
);
2248 * If the longest extent is long enough to satisfy all the
2249 * reservations and AGFL rules in place, we can return this extent.
2251 if (pag
->pagf_longest
> delta
)
2252 return min_t(xfs_extlen_t
, pag
->pag_mount
->m_ag_max_usable
,
2253 pag
->pagf_longest
- delta
);
2255 /* Otherwise, let the caller try for 1 block if there's space. */
2256 return pag
->pagf_flcount
> 0 || pag
->pagf_longest
> 0;
2260 * Compute the minimum length of the AGFL in the given AG. If @pag is NULL,
2261 * return the largest possible minimum length.
2264 xfs_alloc_min_freelist(
2265 struct xfs_mount
*mp
,
2266 struct xfs_perag
*pag
)
2268 /* AG btrees have at least 1 level. */
2269 static const uint8_t fake_levels
[XFS_BTNUM_AGF
] = {1, 1, 1};
2270 const uint8_t *levels
= pag
? pag
->pagf_levels
: fake_levels
;
2271 unsigned int min_free
;
2273 ASSERT(mp
->m_alloc_maxlevels
> 0);
2275 /* space needed by-bno freespace btree */
2276 min_free
= min_t(unsigned int, levels
[XFS_BTNUM_BNOi
] + 1,
2277 mp
->m_alloc_maxlevels
);
2278 /* space needed by-size freespace btree */
2279 min_free
+= min_t(unsigned int, levels
[XFS_BTNUM_CNTi
] + 1,
2280 mp
->m_alloc_maxlevels
);
2281 /* space needed reverse mapping used space btree */
2282 if (xfs_has_rmapbt(mp
))
2283 min_free
+= min_t(unsigned int, levels
[XFS_BTNUM_RMAPi
] + 1,
2284 mp
->m_rmap_maxlevels
);
2290 * Check if the operation we are fixing up the freelist for should go ahead or
2291 * not. If we are freeing blocks, we always allow it, otherwise the allocation
2292 * is dependent on whether the size and shape of free space available will
2293 * permit the requested allocation to take place.
2296 xfs_alloc_space_available(
2297 struct xfs_alloc_arg
*args
,
2298 xfs_extlen_t min_free
,
2301 struct xfs_perag
*pag
= args
->pag
;
2302 xfs_extlen_t alloc_len
, longest
;
2303 xfs_extlen_t reservation
; /* blocks that are still reserved */
2305 xfs_extlen_t agflcount
;
2307 if (flags
& XFS_ALLOC_FLAG_FREEING
)
2310 reservation
= xfs_ag_resv_needed(pag
, args
->resv
);
2312 /* do we have enough contiguous free space for the allocation? */
2313 alloc_len
= args
->minlen
+ (args
->alignment
- 1) + args
->minalignslop
;
2314 longest
= xfs_alloc_longest_free_extent(pag
, min_free
, reservation
);
2315 if (longest
< alloc_len
)
2319 * Do we have enough free space remaining for the allocation? Don't
2320 * account extra agfl blocks because we are about to defer free them,
2321 * making them unavailable until the current transaction commits.
2323 agflcount
= min_t(xfs_extlen_t
, pag
->pagf_flcount
, min_free
);
2324 available
= (int)(pag
->pagf_freeblks
+ agflcount
-
2325 reservation
- min_free
- args
->minleft
);
2326 if (available
< (int)max(args
->total
, alloc_len
))
2330 * Clamp maxlen to the amount of free space available for the actual
2331 * extent allocation.
2333 if (available
< (int)args
->maxlen
&& !(flags
& XFS_ALLOC_FLAG_CHECK
)) {
2334 args
->maxlen
= available
;
2335 ASSERT(args
->maxlen
> 0);
2336 ASSERT(args
->maxlen
>= args
->minlen
);
2343 xfs_free_agfl_block(
2344 struct xfs_trans
*tp
,
2345 xfs_agnumber_t agno
,
2346 xfs_agblock_t agbno
,
2347 struct xfs_buf
*agbp
,
2348 struct xfs_owner_info
*oinfo
)
2353 error
= xfs_free_ag_extent(tp
, agbp
, agno
, agbno
, 1, oinfo
,
2358 error
= xfs_trans_get_buf(tp
, tp
->t_mountp
->m_ddev_targp
,
2359 XFS_AGB_TO_DADDR(tp
->t_mountp
, agno
, agbno
),
2360 tp
->t_mountp
->m_bsize
, 0, &bp
);
2363 xfs_trans_binval(tp
, bp
);
2369 * Check the agfl fields of the agf for inconsistency or corruption. The purpose
2370 * is to detect an agfl header padding mismatch between current and early v5
2371 * kernels. This problem manifests as a 1-slot size difference between the
2372 * on-disk flcount and the active [first, last] range of a wrapped agfl. This
2373 * may also catch variants of agfl count corruption unrelated to padding. Either
2374 * way, we'll reset the agfl and warn the user.
2376 * Return true if a reset is required before the agfl can be used, false
2380 xfs_agfl_needs_reset(
2381 struct xfs_mount
*mp
,
2382 struct xfs_agf
*agf
)
2384 uint32_t f
= be32_to_cpu(agf
->agf_flfirst
);
2385 uint32_t l
= be32_to_cpu(agf
->agf_fllast
);
2386 uint32_t c
= be32_to_cpu(agf
->agf_flcount
);
2387 int agfl_size
= xfs_agfl_size(mp
);
2390 /* no agfl header on v4 supers */
2391 if (!xfs_has_crc(mp
))
2395 * The agf read verifier catches severe corruption of these fields.
2396 * Repeat some sanity checks to cover a packed -> unpacked mismatch if
2397 * the verifier allows it.
2399 if (f
>= agfl_size
|| l
>= agfl_size
)
2405 * Check consistency between the on-disk count and the active range. An
2406 * agfl padding mismatch manifests as an inconsistent flcount.
2411 active
= agfl_size
- f
+ l
+ 1;
2419 * Reset the agfl to an empty state. Ignore/drop any existing blocks since the
2420 * agfl content cannot be trusted. Warn the user that a repair is required to
2421 * recover leaked blocks.
2423 * The purpose of this mechanism is to handle filesystems affected by the agfl
2424 * header padding mismatch problem. A reset keeps the filesystem online with a
2425 * relatively minor free space accounting inconsistency rather than suffer the
2426 * inevitable crash from use of an invalid agfl block.
2430 struct xfs_trans
*tp
,
2431 struct xfs_buf
*agbp
,
2432 struct xfs_perag
*pag
)
2434 struct xfs_mount
*mp
= tp
->t_mountp
;
2435 struct xfs_agf
*agf
= agbp
->b_addr
;
2437 ASSERT(pag
->pagf_agflreset
);
2438 trace_xfs_agfl_reset(mp
, agf
, 0, _RET_IP_
);
2441 "WARNING: Reset corrupted AGFL on AG %u. %d blocks leaked. "
2442 "Please unmount and run xfs_repair.",
2443 pag
->pag_agno
, pag
->pagf_flcount
);
2445 agf
->agf_flfirst
= 0;
2446 agf
->agf_fllast
= cpu_to_be32(xfs_agfl_size(mp
) - 1);
2447 agf
->agf_flcount
= 0;
2448 xfs_alloc_log_agf(tp
, agbp
, XFS_AGF_FLFIRST
| XFS_AGF_FLLAST
|
2451 pag
->pagf_flcount
= 0;
2452 pag
->pagf_agflreset
= false;
2456 * Defer an AGFL block free. This is effectively equivalent to
2457 * xfs_free_extent_later() with some special handling particular to AGFL blocks.
2459 * Deferring AGFL frees helps prevent log reservation overruns due to too many
2460 * allocation operations in a transaction. AGFL frees are prone to this problem
2461 * because for one they are always freed one at a time. Further, an immediate
2462 * AGFL block free can cause a btree join and require another block free before
2463 * the real allocation can proceed. Deferring the free disconnects freeing up
2464 * the AGFL slot from freeing the block.
2467 xfs_defer_agfl_block(
2468 struct xfs_trans
*tp
,
2469 xfs_agnumber_t agno
,
2470 xfs_fsblock_t agbno
,
2471 struct xfs_owner_info
*oinfo
)
2473 struct xfs_mount
*mp
= tp
->t_mountp
;
2474 struct xfs_extent_free_item
*new; /* new element */
2476 ASSERT(xfs_extfree_item_cache
!= NULL
);
2477 ASSERT(oinfo
!= NULL
);
2479 new = kmem_cache_zalloc(xfs_extfree_item_cache
,
2480 GFP_KERNEL
| __GFP_NOFAIL
);
2481 new->xefi_startblock
= XFS_AGB_TO_FSB(mp
, agno
, agbno
);
2482 new->xefi_blockcount
= 1;
2483 new->xefi_owner
= oinfo
->oi_owner
;
2485 trace_xfs_agfl_free_defer(mp
, agno
, 0, agbno
, 1);
2487 xfs_defer_add(tp
, XFS_DEFER_OPS_TYPE_AGFL_FREE
, &new->xefi_list
);
2491 * Add the extent to the list of extents to be free at transaction end.
2492 * The list is maintained sorted (by block number).
2495 __xfs_free_extent_later(
2496 struct xfs_trans
*tp
,
2499 const struct xfs_owner_info
*oinfo
,
2502 struct xfs_extent_free_item
*new; /* new element */
2504 struct xfs_mount
*mp
= tp
->t_mountp
;
2505 xfs_agnumber_t agno
;
2506 xfs_agblock_t agbno
;
2508 ASSERT(bno
!= NULLFSBLOCK
);
2510 ASSERT(len
<= XFS_MAX_BMBT_EXTLEN
);
2511 ASSERT(!isnullstartblock(bno
));
2512 agno
= XFS_FSB_TO_AGNO(mp
, bno
);
2513 agbno
= XFS_FSB_TO_AGBNO(mp
, bno
);
2514 ASSERT(agno
< mp
->m_sb
.sb_agcount
);
2515 ASSERT(agbno
< mp
->m_sb
.sb_agblocks
);
2516 ASSERT(len
< mp
->m_sb
.sb_agblocks
);
2517 ASSERT(agbno
+ len
<= mp
->m_sb
.sb_agblocks
);
2519 ASSERT(xfs_extfree_item_cache
!= NULL
);
2521 new = kmem_cache_zalloc(xfs_extfree_item_cache
,
2522 GFP_KERNEL
| __GFP_NOFAIL
);
2523 new->xefi_startblock
= bno
;
2524 new->xefi_blockcount
= (xfs_extlen_t
)len
;
2526 new->xefi_flags
|= XFS_EFI_SKIP_DISCARD
;
2528 ASSERT(oinfo
->oi_offset
== 0);
2530 if (oinfo
->oi_flags
& XFS_OWNER_INFO_ATTR_FORK
)
2531 new->xefi_flags
|= XFS_EFI_ATTR_FORK
;
2532 if (oinfo
->oi_flags
& XFS_OWNER_INFO_BMBT_BLOCK
)
2533 new->xefi_flags
|= XFS_EFI_BMBT_BLOCK
;
2534 new->xefi_owner
= oinfo
->oi_owner
;
2536 new->xefi_owner
= XFS_RMAP_OWN_NULL
;
2538 trace_xfs_bmap_free_defer(tp
->t_mountp
,
2539 XFS_FSB_TO_AGNO(tp
->t_mountp
, bno
), 0,
2540 XFS_FSB_TO_AGBNO(tp
->t_mountp
, bno
), len
);
2541 xfs_defer_add(tp
, XFS_DEFER_OPS_TYPE_FREE
, &new->xefi_list
);
2546 * Check if an AGF has a free extent record whose length is equal to
2550 xfs_exact_minlen_extent_available(
2551 struct xfs_alloc_arg
*args
,
2552 struct xfs_buf
*agbp
,
2555 struct xfs_btree_cur
*cnt_cur
;
2560 cnt_cur
= xfs_allocbt_init_cursor(args
->mp
, args
->tp
, agbp
,
2561 args
->pag
, XFS_BTNUM_CNT
);
2562 error
= xfs_alloc_lookup_ge(cnt_cur
, 0, args
->minlen
, stat
);
2567 error
= -EFSCORRUPTED
;
2571 error
= xfs_alloc_get_rec(cnt_cur
, &fbno
, &flen
, stat
);
2575 if (*stat
== 1 && flen
!= args
->minlen
)
2579 xfs_btree_del_cursor(cnt_cur
, error
);
2586 * Decide whether to use this allocation group for this allocation.
2587 * If so, fix up the btree freelist's size.
2590 xfs_alloc_fix_freelist(
2591 struct xfs_alloc_arg
*args
, /* allocation argument structure */
2592 int flags
) /* XFS_ALLOC_FLAG_... */
2594 struct xfs_mount
*mp
= args
->mp
;
2595 struct xfs_perag
*pag
= args
->pag
;
2596 struct xfs_trans
*tp
= args
->tp
;
2597 struct xfs_buf
*agbp
= NULL
;
2598 struct xfs_buf
*agflbp
= NULL
;
2599 struct xfs_alloc_arg targs
; /* local allocation arguments */
2600 xfs_agblock_t bno
; /* freelist block */
2601 xfs_extlen_t need
; /* total blocks needed in freelist */
2604 /* deferred ops (AGFL block frees) require permanent transactions */
2605 ASSERT(tp
->t_flags
& XFS_TRANS_PERM_LOG_RES
);
2607 if (!pag
->pagf_init
) {
2608 error
= xfs_alloc_read_agf(mp
, tp
, args
->agno
, flags
, &agbp
);
2610 /* Couldn't lock the AGF so skip this AG. */
2611 if (error
== -EAGAIN
)
2618 * If this is a metadata preferred pag and we are user data then try
2619 * somewhere else if we are not being asked to try harder at this
2622 if (pag
->pagf_metadata
&& (args
->datatype
& XFS_ALLOC_USERDATA
) &&
2623 (flags
& XFS_ALLOC_FLAG_TRYLOCK
)) {
2624 ASSERT(!(flags
& XFS_ALLOC_FLAG_FREEING
));
2625 goto out_agbp_relse
;
2628 need
= xfs_alloc_min_freelist(mp
, pag
);
2629 if (!xfs_alloc_space_available(args
, need
, flags
|
2630 XFS_ALLOC_FLAG_CHECK
))
2631 goto out_agbp_relse
;
2634 * Get the a.g. freespace buffer.
2635 * Can fail if we're not blocking on locks, and it's held.
2638 error
= xfs_alloc_read_agf(mp
, tp
, args
->agno
, flags
, &agbp
);
2640 /* Couldn't lock the AGF so skip this AG. */
2641 if (error
== -EAGAIN
)
2647 /* reset a padding mismatched agfl before final free space check */
2648 if (pag
->pagf_agflreset
)
2649 xfs_agfl_reset(tp
, agbp
, pag
);
2651 /* If there isn't enough total space or single-extent, reject it. */
2652 need
= xfs_alloc_min_freelist(mp
, pag
);
2653 if (!xfs_alloc_space_available(args
, need
, flags
))
2654 goto out_agbp_relse
;
2657 if (args
->alloc_minlen_only
) {
2660 error
= xfs_exact_minlen_extent_available(args
, agbp
, &stat
);
2662 goto out_agbp_relse
;
2666 * Make the freelist shorter if it's too long.
2668 * Note that from this point onwards, we will always release the agf and
2669 * agfl buffers on error. This handles the case where we error out and
2670 * the buffers are clean or may not have been joined to the transaction
2671 * and hence need to be released manually. If they have been joined to
2672 * the transaction, then xfs_trans_brelse() will handle them
2673 * appropriately based on the recursion count and dirty state of the
2676 * XXX (dgc): When we have lots of free space, does this buy us
2677 * anything other than extra overhead when we need to put more blocks
2678 * back on the free list? Maybe we should only do this when space is
2679 * getting low or the AGFL is more than half full?
2681 * The NOSHRINK flag prevents the AGFL from being shrunk if it's too
2682 * big; the NORMAP flag prevents AGFL expand/shrink operations from
2683 * updating the rmapbt. Both flags are used in xfs_repair while we're
2684 * rebuilding the rmapbt, and neither are used by the kernel. They're
2685 * both required to ensure that rmaps are correctly recorded for the
2686 * regenerated AGFL, bnobt, and cntbt. See repair/phase5.c and
2687 * repair/rmap.c in xfsprogs for details.
2689 memset(&targs
, 0, sizeof(targs
));
2690 /* struct copy below */
2691 if (flags
& XFS_ALLOC_FLAG_NORMAP
)
2692 targs
.oinfo
= XFS_RMAP_OINFO_SKIP_UPDATE
;
2694 targs
.oinfo
= XFS_RMAP_OINFO_AG
;
2695 while (!(flags
& XFS_ALLOC_FLAG_NOSHRINK
) && pag
->pagf_flcount
> need
) {
2696 error
= xfs_alloc_get_freelist(tp
, agbp
, &bno
, 0);
2698 goto out_agbp_relse
;
2700 /* defer agfl frees */
2701 xfs_defer_agfl_block(tp
, args
->agno
, bno
, &targs
.oinfo
);
2707 targs
.agno
= args
->agno
;
2708 targs
.alignment
= targs
.minlen
= targs
.prod
= 1;
2709 targs
.type
= XFS_ALLOCTYPE_THIS_AG
;
2711 error
= xfs_alloc_read_agfl(mp
, tp
, targs
.agno
, &agflbp
);
2713 goto out_agbp_relse
;
2715 /* Make the freelist longer if it's too short. */
2716 while (pag
->pagf_flcount
< need
) {
2718 targs
.maxlen
= need
- pag
->pagf_flcount
;
2719 targs
.resv
= XFS_AG_RESV_AGFL
;
2721 /* Allocate as many blocks as possible at once. */
2722 error
= xfs_alloc_ag_vextent(&targs
);
2724 goto out_agflbp_relse
;
2727 * Stop if we run out. Won't happen if callers are obeying
2728 * the restrictions correctly. Can happen for free calls
2729 * on a completely full ag.
2731 if (targs
.agbno
== NULLAGBLOCK
) {
2732 if (flags
& XFS_ALLOC_FLAG_FREEING
)
2734 goto out_agflbp_relse
;
2737 * Put each allocated block on the list.
2739 for (bno
= targs
.agbno
; bno
< targs
.agbno
+ targs
.len
; bno
++) {
2740 error
= xfs_alloc_put_freelist(tp
, agbp
,
2743 goto out_agflbp_relse
;
2746 xfs_trans_brelse(tp
, agflbp
);
2751 xfs_trans_brelse(tp
, agflbp
);
2754 xfs_trans_brelse(tp
, agbp
);
2761 * Get a block from the freelist.
2762 * Returns with the buffer for the block gotten.
2765 xfs_alloc_get_freelist(
2766 struct xfs_trans
*tp
,
2767 struct xfs_buf
*agbp
,
2768 xfs_agblock_t
*bnop
,
2771 struct xfs_agf
*agf
= agbp
->b_addr
;
2772 struct xfs_buf
*agflbp
;
2777 struct xfs_mount
*mp
= tp
->t_mountp
;
2778 struct xfs_perag
*pag
;
2781 * Freelist is empty, give up.
2783 if (!agf
->agf_flcount
) {
2784 *bnop
= NULLAGBLOCK
;
2788 * Read the array of free blocks.
2790 error
= xfs_alloc_read_agfl(mp
, tp
, be32_to_cpu(agf
->agf_seqno
),
2797 * Get the block number and update the data structures.
2799 agfl_bno
= xfs_buf_to_agfl_bno(agflbp
);
2800 bno
= be32_to_cpu(agfl_bno
[be32_to_cpu(agf
->agf_flfirst
)]);
2801 be32_add_cpu(&agf
->agf_flfirst
, 1);
2802 xfs_trans_brelse(tp
, agflbp
);
2803 if (be32_to_cpu(agf
->agf_flfirst
) == xfs_agfl_size(mp
))
2804 agf
->agf_flfirst
= 0;
2807 ASSERT(!pag
->pagf_agflreset
);
2808 be32_add_cpu(&agf
->agf_flcount
, -1);
2809 pag
->pagf_flcount
--;
2811 logflags
= XFS_AGF_FLFIRST
| XFS_AGF_FLCOUNT
;
2813 be32_add_cpu(&agf
->agf_btreeblks
, 1);
2814 pag
->pagf_btreeblks
++;
2815 logflags
|= XFS_AGF_BTREEBLKS
;
2818 xfs_alloc_log_agf(tp
, agbp
, logflags
);
2825 * Log the given fields from the agf structure.
2829 xfs_trans_t
*tp
, /* transaction pointer */
2830 struct xfs_buf
*bp
, /* buffer for a.g. freelist header */
2831 int fields
) /* mask of fields to be logged (XFS_AGF_...) */
2833 int first
; /* first byte offset */
2834 int last
; /* last byte offset */
2835 static const short offsets
[] = {
2836 offsetof(xfs_agf_t
, agf_magicnum
),
2837 offsetof(xfs_agf_t
, agf_versionnum
),
2838 offsetof(xfs_agf_t
, agf_seqno
),
2839 offsetof(xfs_agf_t
, agf_length
),
2840 offsetof(xfs_agf_t
, agf_roots
[0]),
2841 offsetof(xfs_agf_t
, agf_levels
[0]),
2842 offsetof(xfs_agf_t
, agf_flfirst
),
2843 offsetof(xfs_agf_t
, agf_fllast
),
2844 offsetof(xfs_agf_t
, agf_flcount
),
2845 offsetof(xfs_agf_t
, agf_freeblks
),
2846 offsetof(xfs_agf_t
, agf_longest
),
2847 offsetof(xfs_agf_t
, agf_btreeblks
),
2848 offsetof(xfs_agf_t
, agf_uuid
),
2849 offsetof(xfs_agf_t
, agf_rmap_blocks
),
2850 offsetof(xfs_agf_t
, agf_refcount_blocks
),
2851 offsetof(xfs_agf_t
, agf_refcount_root
),
2852 offsetof(xfs_agf_t
, agf_refcount_level
),
2853 /* needed so that we don't log the whole rest of the structure: */
2854 offsetof(xfs_agf_t
, agf_spare64
),
2858 trace_xfs_agf(tp
->t_mountp
, bp
->b_addr
, fields
, _RET_IP_
);
2860 xfs_trans_buf_set_type(tp
, bp
, XFS_BLFT_AGF_BUF
);
2862 xfs_btree_offsets(fields
, offsets
, XFS_AGF_NUM_BITS
, &first
, &last
);
2863 xfs_trans_log_buf(tp
, bp
, (uint
)first
, (uint
)last
);
2867 * Interface for inode allocation to force the pag data to be initialized.
2870 xfs_alloc_pagf_init(
2871 xfs_mount_t
*mp
, /* file system mount structure */
2872 xfs_trans_t
*tp
, /* transaction pointer */
2873 xfs_agnumber_t agno
, /* allocation group number */
2874 int flags
) /* XFS_ALLOC_FLAGS_... */
2879 error
= xfs_alloc_read_agf(mp
, tp
, agno
, flags
, &bp
);
2881 xfs_trans_brelse(tp
, bp
);
2886 * Put the block on the freelist for the allocation group.
2889 xfs_alloc_put_freelist(
2890 struct xfs_trans
*tp
,
2891 struct xfs_buf
*agbp
,
2892 struct xfs_buf
*agflbp
,
2896 struct xfs_mount
*mp
= tp
->t_mountp
;
2897 struct xfs_agf
*agf
= agbp
->b_addr
;
2898 struct xfs_perag
*pag
;
2905 if (!agflbp
&& (error
= xfs_alloc_read_agfl(mp
, tp
,
2906 be32_to_cpu(agf
->agf_seqno
), &agflbp
)))
2908 be32_add_cpu(&agf
->agf_fllast
, 1);
2909 if (be32_to_cpu(agf
->agf_fllast
) == xfs_agfl_size(mp
))
2910 agf
->agf_fllast
= 0;
2913 ASSERT(!pag
->pagf_agflreset
);
2914 be32_add_cpu(&agf
->agf_flcount
, 1);
2915 pag
->pagf_flcount
++;
2917 logflags
= XFS_AGF_FLLAST
| XFS_AGF_FLCOUNT
;
2919 be32_add_cpu(&agf
->agf_btreeblks
, -1);
2920 pag
->pagf_btreeblks
--;
2921 logflags
|= XFS_AGF_BTREEBLKS
;
2924 xfs_alloc_log_agf(tp
, agbp
, logflags
);
2926 ASSERT(be32_to_cpu(agf
->agf_flcount
) <= xfs_agfl_size(mp
));
2928 agfl_bno
= xfs_buf_to_agfl_bno(agflbp
);
2929 blockp
= &agfl_bno
[be32_to_cpu(agf
->agf_fllast
)];
2930 *blockp
= cpu_to_be32(bno
);
2931 startoff
= (char *)blockp
- (char *)agflbp
->b_addr
;
2933 xfs_alloc_log_agf(tp
, agbp
, logflags
);
2935 xfs_trans_buf_set_type(tp
, agflbp
, XFS_BLFT_AGFL_BUF
);
2936 xfs_trans_log_buf(tp
, agflbp
, startoff
,
2937 startoff
+ sizeof(xfs_agblock_t
) - 1);
2941 static xfs_failaddr_t
2945 struct xfs_mount
*mp
= bp
->b_mount
;
2946 struct xfs_agf
*agf
= bp
->b_addr
;
2948 if (xfs_has_crc(mp
)) {
2949 if (!uuid_equal(&agf
->agf_uuid
, &mp
->m_sb
.sb_meta_uuid
))
2950 return __this_address
;
2951 if (!xfs_log_check_lsn(mp
, be64_to_cpu(agf
->agf_lsn
)))
2952 return __this_address
;
2955 if (!xfs_verify_magic(bp
, agf
->agf_magicnum
))
2956 return __this_address
;
2958 if (!(XFS_AGF_GOOD_VERSION(be32_to_cpu(agf
->agf_versionnum
)) &&
2959 be32_to_cpu(agf
->agf_freeblks
) <= be32_to_cpu(agf
->agf_length
) &&
2960 be32_to_cpu(agf
->agf_flfirst
) < xfs_agfl_size(mp
) &&
2961 be32_to_cpu(agf
->agf_fllast
) < xfs_agfl_size(mp
) &&
2962 be32_to_cpu(agf
->agf_flcount
) <= xfs_agfl_size(mp
)))
2963 return __this_address
;
2965 if (be32_to_cpu(agf
->agf_length
) > mp
->m_sb
.sb_dblocks
)
2966 return __this_address
;
2968 if (be32_to_cpu(agf
->agf_freeblks
) < be32_to_cpu(agf
->agf_longest
) ||
2969 be32_to_cpu(agf
->agf_freeblks
) > be32_to_cpu(agf
->agf_length
))
2970 return __this_address
;
2972 if (be32_to_cpu(agf
->agf_levels
[XFS_BTNUM_BNO
]) < 1 ||
2973 be32_to_cpu(agf
->agf_levels
[XFS_BTNUM_CNT
]) < 1 ||
2974 be32_to_cpu(agf
->agf_levels
[XFS_BTNUM_BNO
]) >
2975 mp
->m_alloc_maxlevels
||
2976 be32_to_cpu(agf
->agf_levels
[XFS_BTNUM_CNT
]) >
2977 mp
->m_alloc_maxlevels
)
2978 return __this_address
;
2980 if (xfs_has_rmapbt(mp
) &&
2981 (be32_to_cpu(agf
->agf_levels
[XFS_BTNUM_RMAP
]) < 1 ||
2982 be32_to_cpu(agf
->agf_levels
[XFS_BTNUM_RMAP
]) >
2983 mp
->m_rmap_maxlevels
))
2984 return __this_address
;
2986 if (xfs_has_rmapbt(mp
) &&
2987 be32_to_cpu(agf
->agf_rmap_blocks
) > be32_to_cpu(agf
->agf_length
))
2988 return __this_address
;
2991 * during growfs operations, the perag is not fully initialised,
2992 * so we can't use it for any useful checking. growfs ensures we can't
2993 * use it by using uncached buffers that don't have the perag attached
2994 * so we can detect and avoid this problem.
2996 if (bp
->b_pag
&& be32_to_cpu(agf
->agf_seqno
) != bp
->b_pag
->pag_agno
)
2997 return __this_address
;
2999 if (xfs_has_lazysbcount(mp
) &&
3000 be32_to_cpu(agf
->agf_btreeblks
) > be32_to_cpu(agf
->agf_length
))
3001 return __this_address
;
3003 if (xfs_has_reflink(mp
) &&
3004 be32_to_cpu(agf
->agf_refcount_blocks
) >
3005 be32_to_cpu(agf
->agf_length
))
3006 return __this_address
;
3008 if (xfs_has_reflink(mp
) &&
3009 (be32_to_cpu(agf
->agf_refcount_level
) < 1 ||
3010 be32_to_cpu(agf
->agf_refcount_level
) > mp
->m_refc_maxlevels
))
3011 return __this_address
;
3018 xfs_agf_read_verify(
3021 struct xfs_mount
*mp
= bp
->b_mount
;
3024 if (xfs_has_crc(mp
) &&
3025 !xfs_buf_verify_cksum(bp
, XFS_AGF_CRC_OFF
))
3026 xfs_verifier_error(bp
, -EFSBADCRC
, __this_address
);
3028 fa
= xfs_agf_verify(bp
);
3029 if (XFS_TEST_ERROR(fa
, mp
, XFS_ERRTAG_ALLOC_READ_AGF
))
3030 xfs_verifier_error(bp
, -EFSCORRUPTED
, fa
);
3035 xfs_agf_write_verify(
3038 struct xfs_mount
*mp
= bp
->b_mount
;
3039 struct xfs_buf_log_item
*bip
= bp
->b_log_item
;
3040 struct xfs_agf
*agf
= bp
->b_addr
;
3043 fa
= xfs_agf_verify(bp
);
3045 xfs_verifier_error(bp
, -EFSCORRUPTED
, fa
);
3049 if (!xfs_has_crc(mp
))
3053 agf
->agf_lsn
= cpu_to_be64(bip
->bli_item
.li_lsn
);
3055 xfs_buf_update_cksum(bp
, XFS_AGF_CRC_OFF
);
3058 const struct xfs_buf_ops xfs_agf_buf_ops
= {
3060 .magic
= { cpu_to_be32(XFS_AGF_MAGIC
), cpu_to_be32(XFS_AGF_MAGIC
) },
3061 .verify_read
= xfs_agf_read_verify
,
3062 .verify_write
= xfs_agf_write_verify
,
3063 .verify_struct
= xfs_agf_verify
,
3067 * Read in the allocation group header (free/alloc section).
3071 struct xfs_mount
*mp
, /* mount point structure */
3072 struct xfs_trans
*tp
, /* transaction pointer */
3073 xfs_agnumber_t agno
, /* allocation group number */
3074 int flags
, /* XFS_BUF_ */
3075 struct xfs_buf
**bpp
) /* buffer for the ag freelist header */
3079 trace_xfs_read_agf(mp
, agno
);
3081 ASSERT(agno
!= NULLAGNUMBER
);
3082 error
= xfs_trans_read_buf(mp
, tp
, mp
->m_ddev_targp
,
3083 XFS_AG_DADDR(mp
, agno
, XFS_AGF_DADDR(mp
)),
3084 XFS_FSS_TO_BB(mp
, 1), flags
, bpp
, &xfs_agf_buf_ops
);
3088 ASSERT(!(*bpp
)->b_error
);
3089 xfs_buf_set_ref(*bpp
, XFS_AGF_REF
);
3094 * Read in the allocation group header (free/alloc section).
3098 struct xfs_mount
*mp
, /* mount point structure */
3099 struct xfs_trans
*tp
, /* transaction pointer */
3100 xfs_agnumber_t agno
, /* allocation group number */
3101 int flags
, /* XFS_ALLOC_FLAG_... */
3102 struct xfs_buf
**bpp
) /* buffer for the ag freelist header */
3104 struct xfs_agf
*agf
; /* ag freelist header */
3105 struct xfs_perag
*pag
; /* per allocation group data */
3109 trace_xfs_alloc_read_agf(mp
, agno
);
3111 /* We don't support trylock when freeing. */
3112 ASSERT((flags
& (XFS_ALLOC_FLAG_FREEING
| XFS_ALLOC_FLAG_TRYLOCK
)) !=
3113 (XFS_ALLOC_FLAG_FREEING
| XFS_ALLOC_FLAG_TRYLOCK
));
3114 ASSERT(agno
!= NULLAGNUMBER
);
3115 error
= xfs_read_agf(mp
, tp
, agno
,
3116 (flags
& XFS_ALLOC_FLAG_TRYLOCK
) ? XBF_TRYLOCK
: 0,
3120 ASSERT(!(*bpp
)->b_error
);
3122 agf
= (*bpp
)->b_addr
;
3123 pag
= (*bpp
)->b_pag
;
3124 if (!pag
->pagf_init
) {
3125 pag
->pagf_freeblks
= be32_to_cpu(agf
->agf_freeblks
);
3126 pag
->pagf_btreeblks
= be32_to_cpu(agf
->agf_btreeblks
);
3127 pag
->pagf_flcount
= be32_to_cpu(agf
->agf_flcount
);
3128 pag
->pagf_longest
= be32_to_cpu(agf
->agf_longest
);
3129 pag
->pagf_levels
[XFS_BTNUM_BNOi
] =
3130 be32_to_cpu(agf
->agf_levels
[XFS_BTNUM_BNOi
]);
3131 pag
->pagf_levels
[XFS_BTNUM_CNTi
] =
3132 be32_to_cpu(agf
->agf_levels
[XFS_BTNUM_CNTi
]);
3133 pag
->pagf_levels
[XFS_BTNUM_RMAPi
] =
3134 be32_to_cpu(agf
->agf_levels
[XFS_BTNUM_RMAPi
]);
3135 pag
->pagf_refcount_level
= be32_to_cpu(agf
->agf_refcount_level
);
3137 pag
->pagf_agflreset
= xfs_agfl_needs_reset(mp
, agf
);
3140 * Update the in-core allocbt counter. Filter out the rmapbt
3141 * subset of the btreeblks counter because the rmapbt is managed
3142 * by perag reservation. Subtract one for the rmapbt root block
3143 * because the rmap counter includes it while the btreeblks
3144 * counter only tracks non-root blocks.
3146 allocbt_blks
= pag
->pagf_btreeblks
;
3147 if (xfs_has_rmapbt(mp
))
3148 allocbt_blks
-= be32_to_cpu(agf
->agf_rmap_blocks
) - 1;
3149 if (allocbt_blks
> 0)
3150 atomic64_add(allocbt_blks
, &mp
->m_allocbt_blks
);
3153 else if (!xfs_is_shutdown(mp
)) {
3154 ASSERT(pag
->pagf_freeblks
== be32_to_cpu(agf
->agf_freeblks
));
3155 ASSERT(pag
->pagf_btreeblks
== be32_to_cpu(agf
->agf_btreeblks
));
3156 ASSERT(pag
->pagf_flcount
== be32_to_cpu(agf
->agf_flcount
));
3157 ASSERT(pag
->pagf_longest
== be32_to_cpu(agf
->agf_longest
));
3158 ASSERT(pag
->pagf_levels
[XFS_BTNUM_BNOi
] ==
3159 be32_to_cpu(agf
->agf_levels
[XFS_BTNUM_BNOi
]));
3160 ASSERT(pag
->pagf_levels
[XFS_BTNUM_CNTi
] ==
3161 be32_to_cpu(agf
->agf_levels
[XFS_BTNUM_CNTi
]));
3168 * Allocate an extent (variable-size).
3169 * Depending on the allocation type, we either look in a single allocation
3170 * group or loop over the allocation groups to find the result.
3174 struct xfs_alloc_arg
*args
) /* allocation argument structure */
3176 xfs_agblock_t agsize
; /* allocation group size */
3178 int flags
; /* XFS_ALLOC_FLAG_... locking flags */
3179 struct xfs_mount
*mp
; /* mount structure pointer */
3180 xfs_agnumber_t sagno
; /* starting allocation group number */
3181 xfs_alloctype_t type
; /* input allocation type */
3183 xfs_agnumber_t rotorstep
= xfs_rotorstep
; /* inode32 agf stepper */
3186 type
= args
->otype
= args
->type
;
3187 args
->agbno
= NULLAGBLOCK
;
3189 * Just fix this up, for the case where the last a.g. is shorter
3190 * (or there's only one a.g.) and the caller couldn't easily figure
3191 * that out (xfs_bmap_alloc).
3193 agsize
= mp
->m_sb
.sb_agblocks
;
3194 if (args
->maxlen
> agsize
)
3195 args
->maxlen
= agsize
;
3196 if (args
->alignment
== 0)
3197 args
->alignment
= 1;
3198 ASSERT(XFS_FSB_TO_AGNO(mp
, args
->fsbno
) < mp
->m_sb
.sb_agcount
);
3199 ASSERT(XFS_FSB_TO_AGBNO(mp
, args
->fsbno
) < agsize
);
3200 ASSERT(args
->minlen
<= args
->maxlen
);
3201 ASSERT(args
->minlen
<= agsize
);
3202 ASSERT(args
->mod
< args
->prod
);
3203 if (XFS_FSB_TO_AGNO(mp
, args
->fsbno
) >= mp
->m_sb
.sb_agcount
||
3204 XFS_FSB_TO_AGBNO(mp
, args
->fsbno
) >= agsize
||
3205 args
->minlen
> args
->maxlen
|| args
->minlen
> agsize
||
3206 args
->mod
>= args
->prod
) {
3207 args
->fsbno
= NULLFSBLOCK
;
3208 trace_xfs_alloc_vextent_badargs(args
);
3213 case XFS_ALLOCTYPE_THIS_AG
:
3214 case XFS_ALLOCTYPE_NEAR_BNO
:
3215 case XFS_ALLOCTYPE_THIS_BNO
:
3217 * These three force us into a single a.g.
3219 args
->agno
= XFS_FSB_TO_AGNO(mp
, args
->fsbno
);
3220 args
->pag
= xfs_perag_get(mp
, args
->agno
);
3221 error
= xfs_alloc_fix_freelist(args
, 0);
3223 trace_xfs_alloc_vextent_nofix(args
);
3227 trace_xfs_alloc_vextent_noagbp(args
);
3230 args
->agbno
= XFS_FSB_TO_AGBNO(mp
, args
->fsbno
);
3231 if ((error
= xfs_alloc_ag_vextent(args
)))
3234 case XFS_ALLOCTYPE_START_BNO
:
3236 * Try near allocation first, then anywhere-in-ag after
3237 * the first a.g. fails.
3239 if ((args
->datatype
& XFS_ALLOC_INITIAL_USER_DATA
) &&
3240 xfs_is_inode32(mp
)) {
3241 args
->fsbno
= XFS_AGB_TO_FSB(mp
,
3242 ((mp
->m_agfrotor
/ rotorstep
) %
3243 mp
->m_sb
.sb_agcount
), 0);
3246 args
->agbno
= XFS_FSB_TO_AGBNO(mp
, args
->fsbno
);
3247 args
->type
= XFS_ALLOCTYPE_NEAR_BNO
;
3249 case XFS_ALLOCTYPE_FIRST_AG
:
3251 * Rotate through the allocation groups looking for a winner.
3253 if (type
== XFS_ALLOCTYPE_FIRST_AG
) {
3255 * Start with allocation group given by bno.
3257 args
->agno
= XFS_FSB_TO_AGNO(mp
, args
->fsbno
);
3258 args
->type
= XFS_ALLOCTYPE_THIS_AG
;
3263 * Start with the given allocation group.
3265 args
->agno
= sagno
= XFS_FSB_TO_AGNO(mp
, args
->fsbno
);
3266 flags
= XFS_ALLOC_FLAG_TRYLOCK
;
3269 * Loop over allocation groups twice; first time with
3270 * trylock set, second time without.
3273 args
->pag
= xfs_perag_get(mp
, args
->agno
);
3274 error
= xfs_alloc_fix_freelist(args
, flags
);
3276 trace_xfs_alloc_vextent_nofix(args
);
3280 * If we get a buffer back then the allocation will fly.
3283 if ((error
= xfs_alloc_ag_vextent(args
)))
3288 trace_xfs_alloc_vextent_loopfailed(args
);
3291 * Didn't work, figure out the next iteration.
3293 if (args
->agno
== sagno
&&
3294 type
== XFS_ALLOCTYPE_START_BNO
)
3295 args
->type
= XFS_ALLOCTYPE_THIS_AG
;
3297 * For the first allocation, we can try any AG to get
3298 * space. However, if we already have allocated a
3299 * block, we don't want to try AGs whose number is below
3300 * sagno. Otherwise, we may end up with out-of-order
3301 * locking of AGF, which might cause deadlock.
3303 if (++(args
->agno
) == mp
->m_sb
.sb_agcount
) {
3304 if (args
->tp
->t_firstblock
!= NULLFSBLOCK
)
3310 * Reached the starting a.g., must either be done
3311 * or switch to non-trylock mode.
3313 if (args
->agno
== sagno
) {
3315 args
->agbno
= NULLAGBLOCK
;
3316 trace_xfs_alloc_vextent_allfailed(args
);
3321 if (type
== XFS_ALLOCTYPE_START_BNO
) {
3322 args
->agbno
= XFS_FSB_TO_AGBNO(mp
,
3324 args
->type
= XFS_ALLOCTYPE_NEAR_BNO
;
3327 xfs_perag_put(args
->pag
);
3330 if (args
->agno
== sagno
)
3331 mp
->m_agfrotor
= (mp
->m_agfrotor
+ 1) %
3332 (mp
->m_sb
.sb_agcount
* rotorstep
);
3334 mp
->m_agfrotor
= (args
->agno
* rotorstep
+ 1) %
3335 (mp
->m_sb
.sb_agcount
* rotorstep
);
3342 if (args
->agbno
== NULLAGBLOCK
)
3343 args
->fsbno
= NULLFSBLOCK
;
3345 args
->fsbno
= XFS_AGB_TO_FSB(mp
, args
->agno
, args
->agbno
);
3347 ASSERT(args
->len
>= args
->minlen
);
3348 ASSERT(args
->len
<= args
->maxlen
);
3349 ASSERT(args
->agbno
% args
->alignment
== 0);
3350 XFS_AG_CHECK_DADDR(mp
, XFS_FSB_TO_DADDR(mp
, args
->fsbno
),
3355 xfs_perag_put(args
->pag
);
3358 xfs_perag_put(args
->pag
);
3362 /* Ensure that the freelist is at full capacity. */
3364 xfs_free_extent_fix_freelist(
3365 struct xfs_trans
*tp
,
3366 struct xfs_perag
*pag
,
3367 struct xfs_buf
**agbp
)
3369 struct xfs_alloc_arg args
;
3372 memset(&args
, 0, sizeof(struct xfs_alloc_arg
));
3374 args
.mp
= tp
->t_mountp
;
3375 args
.agno
= pag
->pag_agno
;
3379 * validate that the block number is legal - the enables us to detect
3380 * and handle a silent filesystem corruption rather than crashing.
3382 if (args
.agno
>= args
.mp
->m_sb
.sb_agcount
)
3383 return -EFSCORRUPTED
;
3385 error
= xfs_alloc_fix_freelist(&args
, XFS_ALLOC_FLAG_FREEING
);
3395 * Just break up the extent address and hand off to xfs_free_ag_extent
3396 * after fixing up the freelist.
3400 struct xfs_trans
*tp
,
3403 const struct xfs_owner_info
*oinfo
,
3404 enum xfs_ag_resv_type type
,
3407 struct xfs_mount
*mp
= tp
->t_mountp
;
3408 struct xfs_buf
*agbp
;
3409 xfs_agnumber_t agno
= XFS_FSB_TO_AGNO(mp
, bno
);
3410 xfs_agblock_t agbno
= XFS_FSB_TO_AGBNO(mp
, bno
);
3411 struct xfs_agf
*agf
;
3413 unsigned int busy_flags
= 0;
3414 struct xfs_perag
*pag
;
3417 ASSERT(type
!= XFS_AG_RESV_AGFL
);
3419 if (XFS_TEST_ERROR(false, mp
,
3420 XFS_ERRTAG_FREE_EXTENT
))
3423 pag
= xfs_perag_get(mp
, agno
);
3424 error
= xfs_free_extent_fix_freelist(tp
, pag
, &agbp
);
3429 if (XFS_IS_CORRUPT(mp
, agbno
>= mp
->m_sb
.sb_agblocks
)) {
3430 error
= -EFSCORRUPTED
;
3434 /* validate the extent size is legal now we have the agf locked */
3435 if (XFS_IS_CORRUPT(mp
, agbno
+ len
> be32_to_cpu(agf
->agf_length
))) {
3436 error
= -EFSCORRUPTED
;
3440 error
= xfs_free_ag_extent(tp
, agbp
, agno
, agbno
, len
, oinfo
, type
);
3445 busy_flags
|= XFS_EXTENT_BUSY_SKIP_DISCARD
;
3446 xfs_extent_busy_insert(tp
, pag
, agbno
, len
, busy_flags
);
3451 xfs_trans_brelse(tp
, agbp
);
3457 struct xfs_alloc_query_range_info
{
3458 xfs_alloc_query_range_fn fn
;
3462 /* Format btree record and pass to our callback. */
3464 xfs_alloc_query_range_helper(
3465 struct xfs_btree_cur
*cur
,
3466 const union xfs_btree_rec
*rec
,
3469 struct xfs_alloc_query_range_info
*query
= priv
;
3470 struct xfs_alloc_rec_incore irec
;
3472 irec
.ar_startblock
= be32_to_cpu(rec
->alloc
.ar_startblock
);
3473 irec
.ar_blockcount
= be32_to_cpu(rec
->alloc
.ar_blockcount
);
3474 return query
->fn(cur
, &irec
, query
->priv
);
3477 /* Find all free space within a given range of blocks. */
3479 xfs_alloc_query_range(
3480 struct xfs_btree_cur
*cur
,
3481 const struct xfs_alloc_rec_incore
*low_rec
,
3482 const struct xfs_alloc_rec_incore
*high_rec
,
3483 xfs_alloc_query_range_fn fn
,
3486 union xfs_btree_irec low_brec
;
3487 union xfs_btree_irec high_brec
;
3488 struct xfs_alloc_query_range_info query
;
3490 ASSERT(cur
->bc_btnum
== XFS_BTNUM_BNO
);
3491 low_brec
.a
= *low_rec
;
3492 high_brec
.a
= *high_rec
;
3495 return xfs_btree_query_range(cur
, &low_brec
, &high_brec
,
3496 xfs_alloc_query_range_helper
, &query
);
3499 /* Find all free space records. */
3501 xfs_alloc_query_all(
3502 struct xfs_btree_cur
*cur
,
3503 xfs_alloc_query_range_fn fn
,
3506 struct xfs_alloc_query_range_info query
;
3508 ASSERT(cur
->bc_btnum
== XFS_BTNUM_BNO
);
3511 return xfs_btree_query_all(cur
, xfs_alloc_query_range_helper
, &query
);
3514 /* Is there a record covering a given extent? */
3516 xfs_alloc_has_record(
3517 struct xfs_btree_cur
*cur
,
3522 union xfs_btree_irec low
;
3523 union xfs_btree_irec high
;
3525 memset(&low
, 0, sizeof(low
));
3526 low
.a
.ar_startblock
= bno
;
3527 memset(&high
, 0xFF, sizeof(high
));
3528 high
.a
.ar_startblock
= bno
+ len
- 1;
3530 return xfs_btree_has_record(cur
, &low
, &high
, exists
);
3534 * Walk all the blocks in the AGFL. The @walk_fn can return any negative
3535 * error code or XFS_ITER_*.
3539 struct xfs_mount
*mp
,
3540 struct xfs_agf
*agf
,
3541 struct xfs_buf
*agflbp
,
3542 xfs_agfl_walk_fn walk_fn
,
3549 agfl_bno
= xfs_buf_to_agfl_bno(agflbp
);
3550 i
= be32_to_cpu(agf
->agf_flfirst
);
3552 /* Nothing to walk in an empty AGFL. */
3553 if (agf
->agf_flcount
== cpu_to_be32(0))
3556 /* Otherwise, walk from first to last, wrapping as needed. */
3558 error
= walk_fn(mp
, be32_to_cpu(agfl_bno
[i
]), priv
);
3561 if (i
== be32_to_cpu(agf
->agf_fllast
))
3563 if (++i
== xfs_agfl_size(mp
))
3571 xfs_extfree_intent_init_cache(void)
3573 xfs_extfree_item_cache
= kmem_cache_create("xfs_extfree_intent",
3574 sizeof(struct xfs_extent_free_item
),
3577 return xfs_extfree_item_cache
!= NULL
? 0 : -ENOMEM
;
3581 xfs_extfree_intent_destroy_cache(void)
3583 kmem_cache_destroy(xfs_extfree_item_cache
);
3584 xfs_extfree_item_cache
= NULL
;