2 * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc.
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License as
7 * published by the Free Software Foundation.
9 * This program is distributed in the hope that it would be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write the Free Software Foundation,
16 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
20 #include "xfs_format.h"
21 #include "xfs_log_format.h"
22 #include "xfs_shared.h"
23 #include "xfs_trans_resv.h"
26 #include "xfs_mount.h"
27 #include "xfs_defer.h"
28 #include "xfs_inode.h"
29 #include "xfs_btree.h"
31 #include "xfs_alloc_btree.h"
32 #include "xfs_alloc.h"
33 #include "xfs_extent_busy.h"
34 #include "xfs_error.h"
35 #include "xfs_cksum.h"
36 #include "xfs_trace.h"
37 #include "xfs_trans.h"
38 #include "xfs_buf_item.h"
40 #include "xfs_ag_resv.h"
42 struct workqueue_struct
*xfs_alloc_wq
;
44 #define XFS_ABSDIFF(a,b) (((a) <= (b)) ? ((b) - (a)) : ((a) - (b)))
46 #define XFSA_FIXUP_BNO_OK 1
47 #define XFSA_FIXUP_CNT_OK 2
49 STATIC
int xfs_alloc_ag_vextent_exact(xfs_alloc_arg_t
*);
50 STATIC
int xfs_alloc_ag_vextent_near(xfs_alloc_arg_t
*);
51 STATIC
int xfs_alloc_ag_vextent_size(xfs_alloc_arg_t
*);
52 STATIC
int xfs_alloc_ag_vextent_small(xfs_alloc_arg_t
*,
53 xfs_btree_cur_t
*, xfs_agblock_t
*, xfs_extlen_t
*, int *);
59 if (xfs_sb_version_hasrmapbt(&mp
->m_sb
))
60 return XFS_RMAP_BLOCK(mp
) + 1;
61 if (xfs_sb_version_hasfinobt(&mp
->m_sb
))
62 return XFS_FIBT_BLOCK(mp
) + 1;
63 return XFS_IBT_BLOCK(mp
) + 1;
70 if (xfs_sb_version_hasreflink(&mp
->m_sb
))
71 return xfs_refc_block(mp
) + 1;
72 if (xfs_sb_version_hasrmapbt(&mp
->m_sb
))
73 return XFS_RMAP_BLOCK(mp
) + 1;
74 if (xfs_sb_version_hasfinobt(&mp
->m_sb
))
75 return XFS_FIBT_BLOCK(mp
) + 1;
76 return XFS_IBT_BLOCK(mp
) + 1;
80 * In order to avoid ENOSPC-related deadlock caused by out-of-order locking of
81 * AGF buffer (PV 947395), we place constraints on the relationship among
82 * actual allocations for data blocks, freelist blocks, and potential file data
83 * bmap btree blocks. However, these restrictions may result in no actual space
84 * allocated for a delayed extent, for example, a data block in a certain AG is
85 * allocated but there is no additional block for the additional bmap btree
86 * block due to a split of the bmap btree of the file. The result of this may
87 * lead to an infinite loop when the file gets flushed to disk and all delayed
88 * extents need to be actually allocated. To get around this, we explicitly set
89 * aside a few blocks which will not be reserved in delayed allocation.
91 * We need to reserve 4 fsbs _per AG_ for the freelist and 4 more to handle a
92 * potential split of the file's bmap btree.
100 blocks
= 4 + (mp
->m_sb
.sb_agcount
* XFS_ALLOC_AGFL_RESERVE
);
105 * When deciding how much space to allocate out of an AG, we limit the
106 * allocation maximum size to the size the AG. However, we cannot use all the
107 * blocks in the AG - some are permanently used by metadata. These
108 * blocks are generally:
109 * - the AG superblock, AGF, AGI and AGFL
110 * - the AGF (bno and cnt) and AGI btree root blocks, and optionally
111 * the AGI free inode and rmap btree root blocks.
112 * - blocks on the AGFL according to xfs_alloc_set_aside() limits
113 * - the rmapbt root block
115 * The AG headers are sector sized, so the amount of space they take up is
116 * dependent on filesystem geometry. The others are all single blocks.
119 xfs_alloc_ag_max_usable(
120 struct xfs_mount
*mp
)
124 blocks
= XFS_BB_TO_FSB(mp
, XFS_FSS_TO_BB(mp
, 4)); /* ag headers */
125 blocks
+= XFS_ALLOC_AGFL_RESERVE
;
126 blocks
+= 3; /* AGF, AGI btree root blocks */
127 if (xfs_sb_version_hasfinobt(&mp
->m_sb
))
128 blocks
++; /* finobt root block */
129 if (xfs_sb_version_hasrmapbt(&mp
->m_sb
))
130 blocks
++; /* rmap root block */
131 if (xfs_sb_version_hasreflink(&mp
->m_sb
))
132 blocks
++; /* refcount root block */
134 return mp
->m_sb
.sb_agblocks
- blocks
;
138 * Lookup the record equal to [bno, len] in the btree given by cur.
140 STATIC
int /* error */
142 struct xfs_btree_cur
*cur
, /* btree cursor */
143 xfs_agblock_t bno
, /* starting block of extent */
144 xfs_extlen_t len
, /* length of extent */
145 int *stat
) /* success/failure */
147 cur
->bc_rec
.a
.ar_startblock
= bno
;
148 cur
->bc_rec
.a
.ar_blockcount
= len
;
149 return xfs_btree_lookup(cur
, XFS_LOOKUP_EQ
, stat
);
153 * Lookup the first record greater than or equal to [bno, len]
154 * in the btree given by cur.
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 */
163 cur
->bc_rec
.a
.ar_startblock
= bno
;
164 cur
->bc_rec
.a
.ar_blockcount
= len
;
165 return xfs_btree_lookup(cur
, XFS_LOOKUP_GE
, stat
);
169 * Lookup the first record less than or equal to [bno, len]
170 * in the btree given by cur.
172 static int /* error */
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 */
179 cur
->bc_rec
.a
.ar_startblock
= bno
;
180 cur
->bc_rec
.a
.ar_blockcount
= len
;
181 return xfs_btree_lookup(cur
, XFS_LOOKUP_LE
, stat
);
185 * Update the record referred to by cur to the value given
187 * This either works (return 0) or gets an EFSCORRUPTED error.
189 STATIC
int /* error */
191 struct xfs_btree_cur
*cur
, /* btree cursor */
192 xfs_agblock_t bno
, /* starting block of extent */
193 xfs_extlen_t len
) /* length of extent */
195 union xfs_btree_rec rec
;
197 rec
.alloc
.ar_startblock
= cpu_to_be32(bno
);
198 rec
.alloc
.ar_blockcount
= cpu_to_be32(len
);
199 return xfs_btree_update(cur
, &rec
);
203 * Get the data from the pointed-to record.
207 struct xfs_btree_cur
*cur
, /* btree cursor */
208 xfs_agblock_t
*bno
, /* output: starting block of extent */
209 xfs_extlen_t
*len
, /* output: length of extent */
210 int *stat
) /* output: success/failure */
212 union xfs_btree_rec
*rec
;
215 error
= xfs_btree_get_rec(cur
, &rec
, stat
);
216 if (!error
&& *stat
== 1) {
217 *bno
= be32_to_cpu(rec
->alloc
.ar_startblock
);
218 *len
= be32_to_cpu(rec
->alloc
.ar_blockcount
);
224 * Compute aligned version of the found extent.
225 * Takes alignment and min length into account.
228 xfs_alloc_compute_aligned(
229 xfs_alloc_arg_t
*args
, /* allocation argument structure */
230 xfs_agblock_t foundbno
, /* starting block in found extent */
231 xfs_extlen_t foundlen
, /* length in found extent */
232 xfs_agblock_t
*resbno
, /* result block number */
233 xfs_extlen_t
*reslen
) /* result length */
239 /* Trim busy sections out of found extent */
240 xfs_extent_busy_trim(args
, foundbno
, foundlen
, &bno
, &len
);
243 * If we have a largish extent that happens to start before min_agbno,
244 * see if we can shift it into range...
246 if (bno
< args
->min_agbno
&& bno
+ len
> args
->min_agbno
) {
247 diff
= args
->min_agbno
- bno
;
254 if (args
->alignment
> 1 && len
>= args
->minlen
) {
255 xfs_agblock_t aligned_bno
= roundup(bno
, args
->alignment
);
257 diff
= aligned_bno
- bno
;
259 *resbno
= aligned_bno
;
260 *reslen
= diff
>= len
? 0 : len
- diff
;
268 * Compute best start block and diff for "near" allocations.
269 * freelen >= wantlen already checked by caller.
271 STATIC xfs_extlen_t
/* difference value (absolute) */
272 xfs_alloc_compute_diff(
273 xfs_agblock_t wantbno
, /* target starting block */
274 xfs_extlen_t wantlen
, /* target length */
275 xfs_extlen_t alignment
, /* target alignment */
276 int datatype
, /* are we allocating data? */
277 xfs_agblock_t freebno
, /* freespace's starting block */
278 xfs_extlen_t freelen
, /* freespace's length */
279 xfs_agblock_t
*newbnop
) /* result: best start block from free */
281 xfs_agblock_t freeend
; /* end of freespace extent */
282 xfs_agblock_t newbno1
; /* return block number */
283 xfs_agblock_t newbno2
; /* other new block number */
284 xfs_extlen_t newlen1
=0; /* length with newbno1 */
285 xfs_extlen_t newlen2
=0; /* length with newbno2 */
286 xfs_agblock_t wantend
; /* end of target extent */
287 bool userdata
= xfs_alloc_is_userdata(datatype
);
289 ASSERT(freelen
>= wantlen
);
290 freeend
= freebno
+ freelen
;
291 wantend
= wantbno
+ wantlen
;
293 * We want to allocate from the start of a free extent if it is past
294 * the desired block or if we are allocating user data and the free
295 * extent is before desired block. The second case is there to allow
296 * for contiguous allocation from the remaining free space if the file
297 * grows in the short term.
299 if (freebno
>= wantbno
|| (userdata
&& freeend
< wantend
)) {
300 if ((newbno1
= roundup(freebno
, alignment
)) >= freeend
)
301 newbno1
= NULLAGBLOCK
;
302 } else if (freeend
>= wantend
&& alignment
> 1) {
303 newbno1
= roundup(wantbno
, alignment
);
304 newbno2
= newbno1
- alignment
;
305 if (newbno1
>= freeend
)
306 newbno1
= NULLAGBLOCK
;
308 newlen1
= XFS_EXTLEN_MIN(wantlen
, freeend
- newbno1
);
309 if (newbno2
< freebno
)
310 newbno2
= NULLAGBLOCK
;
312 newlen2
= XFS_EXTLEN_MIN(wantlen
, freeend
- newbno2
);
313 if (newbno1
!= NULLAGBLOCK
&& newbno2
!= NULLAGBLOCK
) {
314 if (newlen1
< newlen2
||
315 (newlen1
== newlen2
&&
316 XFS_ABSDIFF(newbno1
, wantbno
) >
317 XFS_ABSDIFF(newbno2
, wantbno
)))
319 } else if (newbno2
!= NULLAGBLOCK
)
321 } else if (freeend
>= wantend
) {
323 } else if (alignment
> 1) {
324 newbno1
= roundup(freeend
- wantlen
, alignment
);
325 if (newbno1
> freeend
- wantlen
&&
326 newbno1
- alignment
>= freebno
)
327 newbno1
-= alignment
;
328 else if (newbno1
>= freeend
)
329 newbno1
= NULLAGBLOCK
;
331 newbno1
= freeend
- wantlen
;
333 return newbno1
== NULLAGBLOCK
? 0 : XFS_ABSDIFF(newbno1
, wantbno
);
337 * Fix up the length, based on mod and prod.
338 * len should be k * prod + mod for some k.
339 * If len is too small it is returned unchanged.
340 * If len hits maxlen it is left alone.
344 xfs_alloc_arg_t
*args
) /* allocation argument structure */
349 ASSERT(args
->mod
< args
->prod
);
351 ASSERT(rlen
>= args
->minlen
);
352 ASSERT(rlen
<= args
->maxlen
);
353 if (args
->prod
<= 1 || rlen
< args
->mod
|| rlen
== args
->maxlen
||
354 (args
->mod
== 0 && rlen
< args
->prod
))
356 k
= rlen
% args
->prod
;
360 rlen
= rlen
- (k
- args
->mod
);
362 rlen
= rlen
- args
->prod
+ (args
->mod
- k
);
363 /* casts to (int) catch length underflows */
364 if ((int)rlen
< (int)args
->minlen
)
366 ASSERT(rlen
>= args
->minlen
&& rlen
<= args
->maxlen
);
367 ASSERT(rlen
% args
->prod
== args
->mod
);
372 * Fix up length if there is too little space left in the a.g.
373 * Return 1 if ok, 0 if too little, should give up.
376 xfs_alloc_fix_minleft(
377 xfs_alloc_arg_t
*args
) /* allocation argument structure */
379 xfs_agf_t
*agf
; /* a.g. freelist header */
380 int diff
; /* free space difference */
382 if (args
->minleft
== 0)
384 agf
= XFS_BUF_TO_AGF(args
->agbp
);
385 diff
= be32_to_cpu(agf
->agf_freeblks
)
386 - args
->len
- args
->minleft
;
389 args
->len
+= diff
; /* shrink the allocated space */
390 /* casts to (int) catch length underflows */
391 if ((int)args
->len
>= (int)args
->minlen
)
393 args
->agbno
= NULLAGBLOCK
;
398 * Update the two btrees, logically removing from freespace the extent
399 * starting at rbno, rlen blocks. The extent is contained within the
400 * actual (current) free extent fbno for flen blocks.
401 * Flags are passed in indicating whether the cursors are set to the
404 STATIC
int /* error code */
405 xfs_alloc_fixup_trees(
406 xfs_btree_cur_t
*cnt_cur
, /* cursor for by-size btree */
407 xfs_btree_cur_t
*bno_cur
, /* cursor for by-block btree */
408 xfs_agblock_t fbno
, /* starting block of free extent */
409 xfs_extlen_t flen
, /* length of free extent */
410 xfs_agblock_t rbno
, /* starting block of returned extent */
411 xfs_extlen_t rlen
, /* length of returned extent */
412 int flags
) /* flags, XFSA_FIXUP_... */
414 int error
; /* error code */
415 int i
; /* operation results */
416 xfs_agblock_t nfbno1
; /* first new free startblock */
417 xfs_agblock_t nfbno2
; /* second new free startblock */
418 xfs_extlen_t nflen1
=0; /* first new free length */
419 xfs_extlen_t nflen2
=0; /* second new free length */
420 struct xfs_mount
*mp
;
425 * Look up the record in the by-size tree if necessary.
427 if (flags
& XFSA_FIXUP_CNT_OK
) {
429 if ((error
= xfs_alloc_get_rec(cnt_cur
, &nfbno1
, &nflen1
, &i
)))
431 XFS_WANT_CORRUPTED_RETURN(mp
,
432 i
== 1 && nfbno1
== fbno
&& nflen1
== flen
);
435 if ((error
= xfs_alloc_lookup_eq(cnt_cur
, fbno
, flen
, &i
)))
437 XFS_WANT_CORRUPTED_RETURN(mp
, i
== 1);
440 * Look up the record in the by-block tree if necessary.
442 if (flags
& XFSA_FIXUP_BNO_OK
) {
444 if ((error
= xfs_alloc_get_rec(bno_cur
, &nfbno1
, &nflen1
, &i
)))
446 XFS_WANT_CORRUPTED_RETURN(mp
,
447 i
== 1 && nfbno1
== fbno
&& nflen1
== flen
);
450 if ((error
= xfs_alloc_lookup_eq(bno_cur
, fbno
, flen
, &i
)))
452 XFS_WANT_CORRUPTED_RETURN(mp
, i
== 1);
456 if (bno_cur
->bc_nlevels
== 1 && cnt_cur
->bc_nlevels
== 1) {
457 struct xfs_btree_block
*bnoblock
;
458 struct xfs_btree_block
*cntblock
;
460 bnoblock
= XFS_BUF_TO_BLOCK(bno_cur
->bc_bufs
[0]);
461 cntblock
= XFS_BUF_TO_BLOCK(cnt_cur
->bc_bufs
[0]);
463 XFS_WANT_CORRUPTED_RETURN(mp
,
464 bnoblock
->bb_numrecs
== cntblock
->bb_numrecs
);
469 * Deal with all four cases: the allocated record is contained
470 * within the freespace record, so we can have new freespace
471 * at either (or both) end, or no freespace remaining.
473 if (rbno
== fbno
&& rlen
== flen
)
474 nfbno1
= nfbno2
= NULLAGBLOCK
;
475 else if (rbno
== fbno
) {
476 nfbno1
= rbno
+ rlen
;
477 nflen1
= flen
- rlen
;
478 nfbno2
= NULLAGBLOCK
;
479 } else if (rbno
+ rlen
== fbno
+ flen
) {
481 nflen1
= flen
- rlen
;
482 nfbno2
= NULLAGBLOCK
;
485 nflen1
= rbno
- fbno
;
486 nfbno2
= rbno
+ rlen
;
487 nflen2
= (fbno
+ flen
) - nfbno2
;
490 * Delete the entry from the by-size btree.
492 if ((error
= xfs_btree_delete(cnt_cur
, &i
)))
494 XFS_WANT_CORRUPTED_RETURN(mp
, i
== 1);
496 * Add new by-size btree entry(s).
498 if (nfbno1
!= NULLAGBLOCK
) {
499 if ((error
= xfs_alloc_lookup_eq(cnt_cur
, nfbno1
, nflen1
, &i
)))
501 XFS_WANT_CORRUPTED_RETURN(mp
, i
== 0);
502 if ((error
= xfs_btree_insert(cnt_cur
, &i
)))
504 XFS_WANT_CORRUPTED_RETURN(mp
, i
== 1);
506 if (nfbno2
!= NULLAGBLOCK
) {
507 if ((error
= xfs_alloc_lookup_eq(cnt_cur
, nfbno2
, nflen2
, &i
)))
509 XFS_WANT_CORRUPTED_RETURN(mp
, i
== 0);
510 if ((error
= xfs_btree_insert(cnt_cur
, &i
)))
512 XFS_WANT_CORRUPTED_RETURN(mp
, i
== 1);
515 * Fix up the by-block btree entry(s).
517 if (nfbno1
== NULLAGBLOCK
) {
519 * No remaining freespace, just delete the by-block tree entry.
521 if ((error
= xfs_btree_delete(bno_cur
, &i
)))
523 XFS_WANT_CORRUPTED_RETURN(mp
, i
== 1);
526 * Update the by-block entry to start later|be shorter.
528 if ((error
= xfs_alloc_update(bno_cur
, nfbno1
, nflen1
)))
531 if (nfbno2
!= NULLAGBLOCK
) {
533 * 2 resulting free entries, need to add one.
535 if ((error
= xfs_alloc_lookup_eq(bno_cur
, nfbno2
, nflen2
, &i
)))
537 XFS_WANT_CORRUPTED_RETURN(mp
, i
== 0);
538 if ((error
= xfs_btree_insert(bno_cur
, &i
)))
540 XFS_WANT_CORRUPTED_RETURN(mp
, i
== 1);
549 struct xfs_mount
*mp
= bp
->b_target
->bt_mount
;
550 struct xfs_agfl
*agfl
= XFS_BUF_TO_AGFL(bp
);
553 if (!uuid_equal(&agfl
->agfl_uuid
, &mp
->m_sb
.sb_meta_uuid
))
555 if (be32_to_cpu(agfl
->agfl_magicnum
) != XFS_AGFL_MAGIC
)
558 * during growfs operations, the perag is not fully initialised,
559 * so we can't use it for any useful checking. growfs ensures we can't
560 * use it by using uncached buffers that don't have the perag attached
561 * so we can detect and avoid this problem.
563 if (bp
->b_pag
&& be32_to_cpu(agfl
->agfl_seqno
) != bp
->b_pag
->pag_agno
)
566 for (i
= 0; i
< XFS_AGFL_SIZE(mp
); i
++) {
567 if (be32_to_cpu(agfl
->agfl_bno
[i
]) != NULLAGBLOCK
&&
568 be32_to_cpu(agfl
->agfl_bno
[i
]) >= mp
->m_sb
.sb_agblocks
)
572 return xfs_log_check_lsn(mp
,
573 be64_to_cpu(XFS_BUF_TO_AGFL(bp
)->agfl_lsn
));
577 xfs_agfl_read_verify(
580 struct xfs_mount
*mp
= bp
->b_target
->bt_mount
;
583 * There is no verification of non-crc AGFLs because mkfs does not
584 * initialise the AGFL to zero or NULL. Hence the only valid part of the
585 * AGFL is what the AGF says is active. We can't get to the AGF, so we
586 * can't verify just those entries are valid.
588 if (!xfs_sb_version_hascrc(&mp
->m_sb
))
591 if (!xfs_buf_verify_cksum(bp
, XFS_AGFL_CRC_OFF
))
592 xfs_buf_ioerror(bp
, -EFSBADCRC
);
593 else if (!xfs_agfl_verify(bp
))
594 xfs_buf_ioerror(bp
, -EFSCORRUPTED
);
597 xfs_verifier_error(bp
);
601 xfs_agfl_write_verify(
604 struct xfs_mount
*mp
= bp
->b_target
->bt_mount
;
605 struct xfs_buf_log_item
*bip
= bp
->b_fspriv
;
607 /* no verification of non-crc AGFLs */
608 if (!xfs_sb_version_hascrc(&mp
->m_sb
))
611 if (!xfs_agfl_verify(bp
)) {
612 xfs_buf_ioerror(bp
, -EFSCORRUPTED
);
613 xfs_verifier_error(bp
);
618 XFS_BUF_TO_AGFL(bp
)->agfl_lsn
= cpu_to_be64(bip
->bli_item
.li_lsn
);
620 xfs_buf_update_cksum(bp
, XFS_AGFL_CRC_OFF
);
623 const struct xfs_buf_ops xfs_agfl_buf_ops
= {
625 .verify_read
= xfs_agfl_read_verify
,
626 .verify_write
= xfs_agfl_write_verify
,
630 * Read in the allocation group free block array.
632 STATIC
int /* error */
634 xfs_mount_t
*mp
, /* mount point structure */
635 xfs_trans_t
*tp
, /* transaction pointer */
636 xfs_agnumber_t agno
, /* allocation group number */
637 xfs_buf_t
**bpp
) /* buffer for the ag free block array */
639 xfs_buf_t
*bp
; /* return value */
642 ASSERT(agno
!= NULLAGNUMBER
);
643 error
= xfs_trans_read_buf(
644 mp
, tp
, mp
->m_ddev_targp
,
645 XFS_AG_DADDR(mp
, agno
, XFS_AGFL_DADDR(mp
)),
646 XFS_FSS_TO_BB(mp
, 1), 0, &bp
, &xfs_agfl_buf_ops
);
649 xfs_buf_set_ref(bp
, XFS_AGFL_REF
);
655 xfs_alloc_update_counters(
656 struct xfs_trans
*tp
,
657 struct xfs_perag
*pag
,
658 struct xfs_buf
*agbp
,
661 struct xfs_agf
*agf
= XFS_BUF_TO_AGF(agbp
);
663 pag
->pagf_freeblks
+= len
;
664 be32_add_cpu(&agf
->agf_freeblks
, len
);
666 xfs_trans_agblocks_delta(tp
, len
);
667 if (unlikely(be32_to_cpu(agf
->agf_freeblks
) >
668 be32_to_cpu(agf
->agf_length
)))
669 return -EFSCORRUPTED
;
671 xfs_alloc_log_agf(tp
, agbp
, XFS_AGF_FREEBLKS
);
676 * Allocation group level functions.
680 * Allocate a variable extent in the allocation group agno.
681 * Type and bno are used to determine where in the allocation group the
683 * Extent's length (returned in *len) will be between minlen and maxlen,
684 * and of the form k * prod + mod unless there's nothing that large.
685 * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
687 STATIC
int /* error */
688 xfs_alloc_ag_vextent(
689 xfs_alloc_arg_t
*args
) /* argument structure for allocation */
692 xfs_extlen_t reservation
;
695 ASSERT(args
->minlen
> 0);
696 ASSERT(args
->maxlen
> 0);
697 ASSERT(args
->minlen
<= args
->maxlen
);
698 ASSERT(args
->mod
< args
->prod
);
699 ASSERT(args
->alignment
> 0);
702 * Clamp maxlen to the amount of free space minus any reservations
703 * that have been made.
705 oldmax
= args
->maxlen
;
706 reservation
= xfs_ag_resv_needed(args
->pag
, args
->resv
);
707 if (args
->maxlen
> args
->pag
->pagf_freeblks
- reservation
)
708 args
->maxlen
= args
->pag
->pagf_freeblks
- reservation
;
709 if (args
->maxlen
== 0) {
710 args
->agbno
= NULLAGBLOCK
;
711 args
->maxlen
= oldmax
;
716 * Branch to correct routine based on the type.
719 switch (args
->type
) {
720 case XFS_ALLOCTYPE_THIS_AG
:
721 error
= xfs_alloc_ag_vextent_size(args
);
723 case XFS_ALLOCTYPE_NEAR_BNO
:
724 error
= xfs_alloc_ag_vextent_near(args
);
726 case XFS_ALLOCTYPE_THIS_BNO
:
727 error
= xfs_alloc_ag_vextent_exact(args
);
734 args
->maxlen
= oldmax
;
736 if (error
|| args
->agbno
== NULLAGBLOCK
)
739 ASSERT(args
->len
>= args
->minlen
);
740 ASSERT(args
->len
<= args
->maxlen
);
741 ASSERT(!args
->wasfromfl
|| args
->resv
!= XFS_AG_RESV_AGFL
);
742 ASSERT(args
->agbno
% args
->alignment
== 0);
744 /* if not file data, insert new block into the reverse map btree */
745 if (args
->oinfo
.oi_owner
!= XFS_RMAP_OWN_UNKNOWN
) {
746 error
= xfs_rmap_alloc(args
->tp
, args
->agbp
, args
->agno
,
747 args
->agbno
, args
->len
, &args
->oinfo
);
752 if (!args
->wasfromfl
) {
753 error
= xfs_alloc_update_counters(args
->tp
, args
->pag
,
755 -((long)(args
->len
)));
759 ASSERT(!xfs_extent_busy_search(args
->mp
, args
->agno
,
760 args
->agbno
, args
->len
));
763 xfs_ag_resv_alloc_extent(args
->pag
, args
->resv
, args
);
765 XFS_STATS_INC(args
->mp
, xs_allocx
);
766 XFS_STATS_ADD(args
->mp
, xs_allocb
, args
->len
);
771 * Allocate a variable extent at exactly agno/bno.
772 * Extent's length (returned in *len) will be between minlen and maxlen,
773 * and of the form k * prod + mod unless there's nothing that large.
774 * Return the starting a.g. block (bno), or NULLAGBLOCK if we can't do it.
776 STATIC
int /* error */
777 xfs_alloc_ag_vextent_exact(
778 xfs_alloc_arg_t
*args
) /* allocation argument structure */
780 xfs_btree_cur_t
*bno_cur
;/* by block-number btree cursor */
781 xfs_btree_cur_t
*cnt_cur
;/* by count btree cursor */
783 xfs_agblock_t fbno
; /* start block of found extent */
784 xfs_extlen_t flen
; /* length of found extent */
785 xfs_agblock_t tbno
; /* start block of trimmed extent */
786 xfs_extlen_t tlen
; /* length of trimmed extent */
787 xfs_agblock_t tend
; /* end block of trimmed extent */
788 int i
; /* success/failure of operation */
790 ASSERT(args
->alignment
== 1);
793 * Allocate/initialize a cursor for the by-number freespace btree.
795 bno_cur
= xfs_allocbt_init_cursor(args
->mp
, args
->tp
, args
->agbp
,
796 args
->agno
, XFS_BTNUM_BNO
);
799 * Lookup bno and minlen in the btree (minlen is irrelevant, really).
800 * Look for the closest free block <= bno, it must contain bno
801 * if any free block does.
803 error
= xfs_alloc_lookup_le(bno_cur
, args
->agbno
, args
->minlen
, &i
);
810 * Grab the freespace record.
812 error
= xfs_alloc_get_rec(bno_cur
, &fbno
, &flen
, &i
);
815 XFS_WANT_CORRUPTED_GOTO(args
->mp
, i
== 1, error0
);
816 ASSERT(fbno
<= args
->agbno
);
819 * Check for overlapping busy extents.
821 xfs_extent_busy_trim(args
, fbno
, flen
, &tbno
, &tlen
);
824 * Give up if the start of the extent is busy, or the freespace isn't
825 * long enough for the minimum request.
827 if (tbno
> args
->agbno
)
829 if (tlen
< args
->minlen
)
832 if (tend
< args
->agbno
+ args
->minlen
)
836 * End of extent will be smaller of the freespace end and the
837 * maximal requested end.
839 * Fix the length according to mod and prod if given.
841 args
->len
= XFS_AGBLOCK_MIN(tend
, args
->agbno
+ args
->maxlen
)
843 xfs_alloc_fix_len(args
);
844 if (!xfs_alloc_fix_minleft(args
))
847 ASSERT(args
->agbno
+ args
->len
<= tend
);
850 * We are allocating agbno for args->len
851 * Allocate/initialize a cursor for the by-size btree.
853 cnt_cur
= xfs_allocbt_init_cursor(args
->mp
, args
->tp
, args
->agbp
,
854 args
->agno
, XFS_BTNUM_CNT
);
855 ASSERT(args
->agbno
+ args
->len
<=
856 be32_to_cpu(XFS_BUF_TO_AGF(args
->agbp
)->agf_length
));
857 error
= xfs_alloc_fixup_trees(cnt_cur
, bno_cur
, fbno
, flen
, args
->agbno
,
858 args
->len
, XFSA_FIXUP_BNO_OK
);
860 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_ERROR
);
864 xfs_btree_del_cursor(bno_cur
, XFS_BTREE_NOERROR
);
865 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_NOERROR
);
868 trace_xfs_alloc_exact_done(args
);
872 /* Didn't find it, return null. */
873 xfs_btree_del_cursor(bno_cur
, XFS_BTREE_NOERROR
);
874 args
->agbno
= NULLAGBLOCK
;
875 trace_xfs_alloc_exact_notfound(args
);
879 xfs_btree_del_cursor(bno_cur
, XFS_BTREE_ERROR
);
880 trace_xfs_alloc_exact_error(args
);
885 * Search the btree in a given direction via the search cursor and compare
886 * the records found against the good extent we've already found.
889 xfs_alloc_find_best_extent(
890 struct xfs_alloc_arg
*args
, /* allocation argument structure */
891 struct xfs_btree_cur
**gcur
, /* good cursor */
892 struct xfs_btree_cur
**scur
, /* searching cursor */
893 xfs_agblock_t gdiff
, /* difference for search comparison */
894 xfs_agblock_t
*sbno
, /* extent found by search */
895 xfs_extlen_t
*slen
, /* extent length */
896 xfs_agblock_t
*sbnoa
, /* aligned extent found by search */
897 xfs_extlen_t
*slena
, /* aligned extent length */
898 int dir
) /* 0 = search right, 1 = search left */
905 /* The good extent is perfect, no need to search. */
910 * Look until we find a better one, run out of space or run off the end.
913 error
= xfs_alloc_get_rec(*scur
, sbno
, slen
, &i
);
916 XFS_WANT_CORRUPTED_GOTO(args
->mp
, i
== 1, error0
);
917 xfs_alloc_compute_aligned(args
, *sbno
, *slen
, sbnoa
, slena
);
920 * The good extent is closer than this one.
923 if (*sbnoa
> args
->max_agbno
)
925 if (*sbnoa
>= args
->agbno
+ gdiff
)
928 if (*sbnoa
< args
->min_agbno
)
930 if (*sbnoa
<= args
->agbno
- gdiff
)
935 * Same distance, compare length and pick the best.
937 if (*slena
>= args
->minlen
) {
938 args
->len
= XFS_EXTLEN_MIN(*slena
, args
->maxlen
);
939 xfs_alloc_fix_len(args
);
941 sdiff
= xfs_alloc_compute_diff(args
->agbno
, args
->len
,
943 args
->datatype
, *sbnoa
,
947 * Choose closer size and invalidate other cursor.
955 error
= xfs_btree_increment(*scur
, 0, &i
);
957 error
= xfs_btree_decrement(*scur
, 0, &i
);
963 xfs_btree_del_cursor(*scur
, XFS_BTREE_NOERROR
);
968 xfs_btree_del_cursor(*gcur
, XFS_BTREE_NOERROR
);
973 /* caller invalidates cursors */
978 * Allocate a variable extent near bno in the allocation group agno.
979 * Extent's length (returned in len) will be between minlen and maxlen,
980 * and of the form k * prod + mod unless there's nothing that large.
981 * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
983 STATIC
int /* error */
984 xfs_alloc_ag_vextent_near(
985 xfs_alloc_arg_t
*args
) /* allocation argument structure */
987 xfs_btree_cur_t
*bno_cur_gt
; /* cursor for bno btree, right side */
988 xfs_btree_cur_t
*bno_cur_lt
; /* cursor for bno btree, left side */
989 xfs_btree_cur_t
*cnt_cur
; /* cursor for count btree */
990 xfs_agblock_t gtbno
; /* start bno of right side entry */
991 xfs_agblock_t gtbnoa
; /* aligned ... */
992 xfs_extlen_t gtdiff
; /* difference to right side entry */
993 xfs_extlen_t gtlen
; /* length of right side entry */
994 xfs_extlen_t gtlena
; /* aligned ... */
995 xfs_agblock_t gtnew
; /* useful start bno of right side */
996 int error
; /* error code */
997 int i
; /* result code, temporary */
998 int j
; /* result code, temporary */
999 xfs_agblock_t ltbno
; /* start bno of left side entry */
1000 xfs_agblock_t ltbnoa
; /* aligned ... */
1001 xfs_extlen_t ltdiff
; /* difference to left side entry */
1002 xfs_extlen_t ltlen
; /* length of left side entry */
1003 xfs_extlen_t ltlena
; /* aligned ... */
1004 xfs_agblock_t ltnew
; /* useful start bno of left side */
1005 xfs_extlen_t rlen
; /* length of returned extent */
1009 * Randomly don't execute the first algorithm.
1011 int dofirst
; /* set to do first algorithm */
1013 dofirst
= prandom_u32() & 1;
1016 /* handle unitialized agbno range so caller doesn't have to */
1017 if (!args
->min_agbno
&& !args
->max_agbno
)
1018 args
->max_agbno
= args
->mp
->m_sb
.sb_agblocks
- 1;
1019 ASSERT(args
->min_agbno
<= args
->max_agbno
);
1021 /* clamp agbno to the range if it's outside */
1022 if (args
->agbno
< args
->min_agbno
)
1023 args
->agbno
= args
->min_agbno
;
1024 if (args
->agbno
> args
->max_agbno
)
1025 args
->agbno
= args
->max_agbno
;
1035 * Get a cursor for the by-size btree.
1037 cnt_cur
= xfs_allocbt_init_cursor(args
->mp
, args
->tp
, args
->agbp
,
1038 args
->agno
, XFS_BTNUM_CNT
);
1041 * See if there are any free extents as big as maxlen.
1043 if ((error
= xfs_alloc_lookup_ge(cnt_cur
, 0, args
->maxlen
, &i
)))
1046 * If none, then pick up the last entry in the tree unless the
1050 if ((error
= xfs_alloc_ag_vextent_small(args
, cnt_cur
, <bno
,
1053 if (i
== 0 || ltlen
== 0) {
1054 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_NOERROR
);
1055 trace_xfs_alloc_near_noentry(args
);
1060 args
->wasfromfl
= 0;
1064 * If the requested extent is large wrt the freespaces available
1065 * in this a.g., then the cursor will be pointing to a btree entry
1066 * near the right edge of the tree. If it's in the last btree leaf
1067 * block, then we just examine all the entries in that block
1068 * that are big enough, and pick the best one.
1069 * This is written as a while loop so we can break out of it,
1070 * but we never loop back to the top.
1072 while (xfs_btree_islastblock(cnt_cur
, 0)) {
1075 xfs_extlen_t blen
=0;
1076 xfs_agblock_t bnew
=0;
1083 * Start from the entry that lookup found, sequence through
1084 * all larger free blocks. If we're actually pointing at a
1085 * record smaller than maxlen, go to the start of this block,
1086 * and skip all those smaller than minlen.
1088 if (ltlen
|| args
->alignment
> 1) {
1089 cnt_cur
->bc_ptrs
[0] = 1;
1091 if ((error
= xfs_alloc_get_rec(cnt_cur
, <bno
,
1094 XFS_WANT_CORRUPTED_GOTO(args
->mp
, i
== 1, error0
);
1095 if (ltlen
>= args
->minlen
)
1097 if ((error
= xfs_btree_increment(cnt_cur
, 0, &i
)))
1100 ASSERT(ltlen
>= args
->minlen
);
1104 i
= cnt_cur
->bc_ptrs
[0];
1105 for (j
= 1, blen
= 0, bdiff
= 0;
1106 !error
&& j
&& (blen
< args
->maxlen
|| bdiff
> 0);
1107 error
= xfs_btree_increment(cnt_cur
, 0, &j
)) {
1109 * For each entry, decide if it's better than
1110 * the previous best entry.
1112 if ((error
= xfs_alloc_get_rec(cnt_cur
, <bno
, <len
, &i
)))
1114 XFS_WANT_CORRUPTED_GOTO(args
->mp
, i
== 1, error0
);
1115 xfs_alloc_compute_aligned(args
, ltbno
, ltlen
,
1117 if (ltlena
< args
->minlen
)
1119 if (ltbnoa
< args
->min_agbno
|| ltbnoa
> args
->max_agbno
)
1121 args
->len
= XFS_EXTLEN_MIN(ltlena
, args
->maxlen
);
1122 xfs_alloc_fix_len(args
);
1123 ASSERT(args
->len
>= args
->minlen
);
1124 if (args
->len
< blen
)
1126 ltdiff
= xfs_alloc_compute_diff(args
->agbno
, args
->len
,
1127 args
->alignment
, args
->datatype
, ltbnoa
,
1129 if (ltnew
!= NULLAGBLOCK
&&
1130 (args
->len
> blen
|| ltdiff
< bdiff
)) {
1134 besti
= cnt_cur
->bc_ptrs
[0];
1138 * It didn't work. We COULD be in a case where
1139 * there's a good record somewhere, so try again.
1144 * Point at the best entry, and retrieve it again.
1146 cnt_cur
->bc_ptrs
[0] = besti
;
1147 if ((error
= xfs_alloc_get_rec(cnt_cur
, <bno
, <len
, &i
)))
1149 XFS_WANT_CORRUPTED_GOTO(args
->mp
, i
== 1, error0
);
1150 ASSERT(ltbno
+ ltlen
<= be32_to_cpu(XFS_BUF_TO_AGF(args
->agbp
)->agf_length
));
1152 if (!xfs_alloc_fix_minleft(args
)) {
1153 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_NOERROR
);
1154 trace_xfs_alloc_near_nominleft(args
);
1159 * We are allocating starting at bnew for blen blocks.
1162 ASSERT(bnew
>= ltbno
);
1163 ASSERT(bnew
+ blen
<= ltbno
+ ltlen
);
1165 * Set up a cursor for the by-bno tree.
1167 bno_cur_lt
= xfs_allocbt_init_cursor(args
->mp
, args
->tp
,
1168 args
->agbp
, args
->agno
, XFS_BTNUM_BNO
);
1170 * Fix up the btree entries.
1172 if ((error
= xfs_alloc_fixup_trees(cnt_cur
, bno_cur_lt
, ltbno
,
1173 ltlen
, bnew
, blen
, XFSA_FIXUP_CNT_OK
)))
1175 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_NOERROR
);
1176 xfs_btree_del_cursor(bno_cur_lt
, XFS_BTREE_NOERROR
);
1178 trace_xfs_alloc_near_first(args
);
1183 * Search in the by-bno tree to the left and to the right
1184 * simultaneously, until in each case we find a space big enough,
1185 * or run into the edge of the tree. When we run into the edge,
1186 * we deallocate that cursor.
1187 * If both searches succeed, we compare the two spaces and pick
1189 * With alignment, it's possible for both to fail; the upper
1190 * level algorithm that picks allocation groups for allocations
1191 * is not supposed to do this.
1194 * Allocate and initialize the cursor for the leftward search.
1196 bno_cur_lt
= xfs_allocbt_init_cursor(args
->mp
, args
->tp
, args
->agbp
,
1197 args
->agno
, XFS_BTNUM_BNO
);
1199 * Lookup <= bno to find the leftward search's starting point.
1201 if ((error
= xfs_alloc_lookup_le(bno_cur_lt
, args
->agbno
, args
->maxlen
, &i
)))
1205 * Didn't find anything; use this cursor for the rightward
1208 bno_cur_gt
= bno_cur_lt
;
1212 * Found something. Duplicate the cursor for the rightward search.
1214 else if ((error
= xfs_btree_dup_cursor(bno_cur_lt
, &bno_cur_gt
)))
1217 * Increment the cursor, so we will point at the entry just right
1218 * of the leftward entry if any, or to the leftmost entry.
1220 if ((error
= xfs_btree_increment(bno_cur_gt
, 0, &i
)))
1224 * It failed, there are no rightward entries.
1226 xfs_btree_del_cursor(bno_cur_gt
, XFS_BTREE_NOERROR
);
1230 * Loop going left with the leftward cursor, right with the
1231 * rightward cursor, until either both directions give up or
1232 * we find an entry at least as big as minlen.
1236 if ((error
= xfs_alloc_get_rec(bno_cur_lt
, <bno
, <len
, &i
)))
1238 XFS_WANT_CORRUPTED_GOTO(args
->mp
, i
== 1, error0
);
1239 xfs_alloc_compute_aligned(args
, ltbno
, ltlen
,
1241 if (ltlena
>= args
->minlen
&& ltbnoa
>= args
->min_agbno
)
1243 if ((error
= xfs_btree_decrement(bno_cur_lt
, 0, &i
)))
1245 if (!i
|| ltbnoa
< args
->min_agbno
) {
1246 xfs_btree_del_cursor(bno_cur_lt
,
1252 if ((error
= xfs_alloc_get_rec(bno_cur_gt
, >bno
, >len
, &i
)))
1254 XFS_WANT_CORRUPTED_GOTO(args
->mp
, i
== 1, error0
);
1255 xfs_alloc_compute_aligned(args
, gtbno
, gtlen
,
1257 if (gtlena
>= args
->minlen
&& gtbnoa
<= args
->max_agbno
)
1259 if ((error
= xfs_btree_increment(bno_cur_gt
, 0, &i
)))
1261 if (!i
|| gtbnoa
> args
->max_agbno
) {
1262 xfs_btree_del_cursor(bno_cur_gt
,
1267 } while (bno_cur_lt
|| bno_cur_gt
);
1270 * Got both cursors still active, need to find better entry.
1272 if (bno_cur_lt
&& bno_cur_gt
) {
1273 if (ltlena
>= args
->minlen
) {
1275 * Left side is good, look for a right side entry.
1277 args
->len
= XFS_EXTLEN_MIN(ltlena
, args
->maxlen
);
1278 xfs_alloc_fix_len(args
);
1279 ltdiff
= xfs_alloc_compute_diff(args
->agbno
, args
->len
,
1280 args
->alignment
, args
->datatype
, ltbnoa
,
1283 error
= xfs_alloc_find_best_extent(args
,
1284 &bno_cur_lt
, &bno_cur_gt
,
1285 ltdiff
, >bno
, >len
,
1287 0 /* search right */);
1289 ASSERT(gtlena
>= args
->minlen
);
1292 * Right side is good, look for a left side entry.
1294 args
->len
= XFS_EXTLEN_MIN(gtlena
, args
->maxlen
);
1295 xfs_alloc_fix_len(args
);
1296 gtdiff
= xfs_alloc_compute_diff(args
->agbno
, args
->len
,
1297 args
->alignment
, args
->datatype
, gtbnoa
,
1300 error
= xfs_alloc_find_best_extent(args
,
1301 &bno_cur_gt
, &bno_cur_lt
,
1302 gtdiff
, <bno
, <len
,
1304 1 /* search left */);
1312 * If we couldn't get anything, give up.
1314 if (bno_cur_lt
== NULL
&& bno_cur_gt
== NULL
) {
1315 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_NOERROR
);
1318 trace_xfs_alloc_near_busy(args
);
1319 xfs_log_force(args
->mp
, XFS_LOG_SYNC
);
1322 trace_xfs_alloc_size_neither(args
);
1323 args
->agbno
= NULLAGBLOCK
;
1328 * At this point we have selected a freespace entry, either to the
1329 * left or to the right. If it's on the right, copy all the
1330 * useful variables to the "left" set so we only have one
1331 * copy of this code.
1334 bno_cur_lt
= bno_cur_gt
;
1345 * Fix up the length and compute the useful address.
1347 args
->len
= XFS_EXTLEN_MIN(ltlena
, args
->maxlen
);
1348 xfs_alloc_fix_len(args
);
1349 if (!xfs_alloc_fix_minleft(args
)) {
1350 trace_xfs_alloc_near_nominleft(args
);
1351 xfs_btree_del_cursor(bno_cur_lt
, XFS_BTREE_NOERROR
);
1352 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_NOERROR
);
1356 (void)xfs_alloc_compute_diff(args
->agbno
, rlen
, args
->alignment
,
1357 args
->datatype
, ltbnoa
, ltlena
, <new
);
1358 ASSERT(ltnew
>= ltbno
);
1359 ASSERT(ltnew
+ rlen
<= ltbnoa
+ ltlena
);
1360 ASSERT(ltnew
+ rlen
<= be32_to_cpu(XFS_BUF_TO_AGF(args
->agbp
)->agf_length
));
1361 ASSERT(ltnew
>= args
->min_agbno
&& ltnew
<= args
->max_agbno
);
1362 args
->agbno
= ltnew
;
1364 if ((error
= xfs_alloc_fixup_trees(cnt_cur
, bno_cur_lt
, ltbno
, ltlen
,
1365 ltnew
, rlen
, XFSA_FIXUP_BNO_OK
)))
1369 trace_xfs_alloc_near_greater(args
);
1371 trace_xfs_alloc_near_lesser(args
);
1373 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_NOERROR
);
1374 xfs_btree_del_cursor(bno_cur_lt
, XFS_BTREE_NOERROR
);
1378 trace_xfs_alloc_near_error(args
);
1379 if (cnt_cur
!= NULL
)
1380 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_ERROR
);
1381 if (bno_cur_lt
!= NULL
)
1382 xfs_btree_del_cursor(bno_cur_lt
, XFS_BTREE_ERROR
);
1383 if (bno_cur_gt
!= NULL
)
1384 xfs_btree_del_cursor(bno_cur_gt
, XFS_BTREE_ERROR
);
1389 * Allocate a variable extent anywhere in the allocation group agno.
1390 * Extent's length (returned in len) will be between minlen and maxlen,
1391 * and of the form k * prod + mod unless there's nothing that large.
1392 * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
1394 STATIC
int /* error */
1395 xfs_alloc_ag_vextent_size(
1396 xfs_alloc_arg_t
*args
) /* allocation argument structure */
1398 xfs_btree_cur_t
*bno_cur
; /* cursor for bno btree */
1399 xfs_btree_cur_t
*cnt_cur
; /* cursor for cnt btree */
1400 int error
; /* error result */
1401 xfs_agblock_t fbno
; /* start of found freespace */
1402 xfs_extlen_t flen
; /* length of found freespace */
1403 int i
; /* temp status variable */
1404 xfs_agblock_t rbno
; /* returned block number */
1405 xfs_extlen_t rlen
; /* length of returned extent */
1410 * Allocate and initialize a cursor for the by-size btree.
1412 cnt_cur
= xfs_allocbt_init_cursor(args
->mp
, args
->tp
, args
->agbp
,
1413 args
->agno
, XFS_BTNUM_CNT
);
1417 * Look for an entry >= maxlen+alignment-1 blocks.
1419 if ((error
= xfs_alloc_lookup_ge(cnt_cur
, 0,
1420 args
->maxlen
+ args
->alignment
- 1, &i
)))
1424 * If none or we have busy extents that we cannot allocate from, then
1425 * we have to settle for a smaller extent. In the case that there are
1426 * no large extents, this will return the last entry in the tree unless
1427 * the tree is empty. In the case that there are only busy large
1428 * extents, this will return the largest small extent unless there
1429 * are no smaller extents available.
1431 if (!i
|| forced
> 1) {
1432 error
= xfs_alloc_ag_vextent_small(args
, cnt_cur
,
1436 if (i
== 0 || flen
== 0) {
1437 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_NOERROR
);
1438 trace_xfs_alloc_size_noentry(args
);
1442 xfs_alloc_compute_aligned(args
, fbno
, flen
, &rbno
, &rlen
);
1445 * Search for a non-busy extent that is large enough.
1446 * If we are at low space, don't check, or if we fall of
1447 * the end of the btree, turn off the busy check and
1451 error
= xfs_alloc_get_rec(cnt_cur
, &fbno
, &flen
, &i
);
1454 XFS_WANT_CORRUPTED_GOTO(args
->mp
, i
== 1, error0
);
1456 xfs_alloc_compute_aligned(args
, fbno
, flen
,
1459 if (rlen
>= args
->maxlen
)
1462 error
= xfs_btree_increment(cnt_cur
, 0, &i
);
1467 * Our only valid extents must have been busy.
1468 * Make it unbusy by forcing the log out and
1469 * retrying. If we've been here before, forcing
1470 * the log isn't making the extents available,
1471 * which means they have probably been freed in
1472 * this transaction. In that case, we have to
1473 * give up on them and we'll attempt a minlen
1474 * allocation the next time around.
1476 xfs_btree_del_cursor(cnt_cur
,
1478 trace_xfs_alloc_size_busy(args
);
1480 xfs_log_force(args
->mp
, XFS_LOG_SYNC
);
1487 * In the first case above, we got the last entry in the
1488 * by-size btree. Now we check to see if the space hits maxlen
1489 * once aligned; if not, we search left for something better.
1490 * This can't happen in the second case above.
1492 rlen
= XFS_EXTLEN_MIN(args
->maxlen
, rlen
);
1493 XFS_WANT_CORRUPTED_GOTO(args
->mp
, rlen
== 0 ||
1494 (rlen
<= flen
&& rbno
+ rlen
<= fbno
+ flen
), error0
);
1495 if (rlen
< args
->maxlen
) {
1496 xfs_agblock_t bestfbno
;
1497 xfs_extlen_t bestflen
;
1498 xfs_agblock_t bestrbno
;
1499 xfs_extlen_t bestrlen
;
1506 if ((error
= xfs_btree_decrement(cnt_cur
, 0, &i
)))
1510 if ((error
= xfs_alloc_get_rec(cnt_cur
, &fbno
, &flen
,
1513 XFS_WANT_CORRUPTED_GOTO(args
->mp
, i
== 1, error0
);
1514 if (flen
< bestrlen
)
1516 xfs_alloc_compute_aligned(args
, fbno
, flen
,
1518 rlen
= XFS_EXTLEN_MIN(args
->maxlen
, rlen
);
1519 XFS_WANT_CORRUPTED_GOTO(args
->mp
, rlen
== 0 ||
1520 (rlen
<= flen
&& rbno
+ rlen
<= fbno
+ flen
),
1522 if (rlen
> bestrlen
) {
1527 if (rlen
== args
->maxlen
)
1531 if ((error
= xfs_alloc_lookup_eq(cnt_cur
, bestfbno
, bestflen
,
1534 XFS_WANT_CORRUPTED_GOTO(args
->mp
, i
== 1, error0
);
1540 args
->wasfromfl
= 0;
1542 * Fix up the length.
1545 if (rlen
< args
->minlen
) {
1547 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_NOERROR
);
1548 trace_xfs_alloc_size_busy(args
);
1549 xfs_log_force(args
->mp
, XFS_LOG_SYNC
);
1554 xfs_alloc_fix_len(args
);
1556 if (!xfs_alloc_fix_minleft(args
))
1559 XFS_WANT_CORRUPTED_GOTO(args
->mp
, rlen
<= flen
, error0
);
1561 * Allocate and initialize a cursor for the by-block tree.
1563 bno_cur
= xfs_allocbt_init_cursor(args
->mp
, args
->tp
, args
->agbp
,
1564 args
->agno
, XFS_BTNUM_BNO
);
1565 if ((error
= xfs_alloc_fixup_trees(cnt_cur
, bno_cur
, fbno
, flen
,
1566 rbno
, rlen
, XFSA_FIXUP_CNT_OK
)))
1568 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_NOERROR
);
1569 xfs_btree_del_cursor(bno_cur
, XFS_BTREE_NOERROR
);
1570 cnt_cur
= bno_cur
= NULL
;
1573 XFS_WANT_CORRUPTED_GOTO(args
->mp
,
1574 args
->agbno
+ args
->len
<=
1575 be32_to_cpu(XFS_BUF_TO_AGF(args
->agbp
)->agf_length
),
1577 trace_xfs_alloc_size_done(args
);
1581 trace_xfs_alloc_size_error(args
);
1583 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_ERROR
);
1585 xfs_btree_del_cursor(bno_cur
, XFS_BTREE_ERROR
);
1589 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_NOERROR
);
1590 trace_xfs_alloc_size_nominleft(args
);
1591 args
->agbno
= NULLAGBLOCK
;
1596 * Deal with the case where only small freespaces remain.
1597 * Either return the contents of the last freespace record,
1598 * or allocate space from the freelist if there is nothing in the tree.
1600 STATIC
int /* error */
1601 xfs_alloc_ag_vextent_small(
1602 xfs_alloc_arg_t
*args
, /* allocation argument structure */
1603 xfs_btree_cur_t
*ccur
, /* by-size cursor */
1604 xfs_agblock_t
*fbnop
, /* result block number */
1605 xfs_extlen_t
*flenp
, /* result length */
1606 int *stat
) /* status: 0-freelist, 1-normal/none */
1608 struct xfs_owner_info oinfo
;
1609 struct xfs_perag
*pag
;
1615 if ((error
= xfs_btree_decrement(ccur
, 0, &i
)))
1618 if ((error
= xfs_alloc_get_rec(ccur
, &fbno
, &flen
, &i
)))
1620 XFS_WANT_CORRUPTED_GOTO(args
->mp
, i
== 1, error0
);
1623 * Nothing in the btree, try the freelist. Make sure
1624 * to respect minleft even when pulling from the
1627 else if (args
->minlen
== 1 && args
->alignment
== 1 &&
1628 args
->resv
!= XFS_AG_RESV_AGFL
&&
1629 (be32_to_cpu(XFS_BUF_TO_AGF(args
->agbp
)->agf_flcount
)
1631 error
= xfs_alloc_get_freelist(args
->tp
, args
->agbp
, &fbno
, 0);
1634 if (fbno
!= NULLAGBLOCK
) {
1635 xfs_extent_busy_reuse(args
->mp
, args
->agno
, fbno
, 1,
1636 xfs_alloc_allow_busy_reuse(args
->datatype
));
1638 if (xfs_alloc_is_userdata(args
->datatype
)) {
1641 bp
= xfs_btree_get_bufs(args
->mp
, args
->tp
,
1642 args
->agno
, fbno
, 0);
1643 xfs_trans_binval(args
->tp
, bp
);
1647 XFS_WANT_CORRUPTED_GOTO(args
->mp
,
1648 args
->agbno
+ args
->len
<=
1649 be32_to_cpu(XFS_BUF_TO_AGF(args
->agbp
)->agf_length
),
1651 args
->wasfromfl
= 1;
1652 trace_xfs_alloc_small_freelist(args
);
1655 * If we're feeding an AGFL block to something that
1656 * doesn't live in the free space, we need to clear
1657 * out the OWN_AG rmap and add the block back to
1658 * the AGFL per-AG reservation.
1660 xfs_rmap_ag_owner(&oinfo
, XFS_RMAP_OWN_AG
);
1661 error
= xfs_rmap_free(args
->tp
, args
->agbp
, args
->agno
,
1665 pag
= xfs_perag_get(args
->mp
, args
->agno
);
1666 xfs_ag_resv_free_extent(pag
, XFS_AG_RESV_AGFL
,
1674 * Nothing in the freelist.
1680 * Can't allocate from the freelist for some reason.
1687 * Can't do the allocation, give up.
1689 if (flen
< args
->minlen
) {
1690 args
->agbno
= NULLAGBLOCK
;
1691 trace_xfs_alloc_small_notenough(args
);
1697 trace_xfs_alloc_small_done(args
);
1701 trace_xfs_alloc_small_error(args
);
1706 * Free the extent starting at agno/bno for length.
1712 xfs_agnumber_t agno
,
1715 struct xfs_owner_info
*oinfo
,
1716 enum xfs_ag_resv_type type
)
1718 xfs_btree_cur_t
*bno_cur
; /* cursor for by-block btree */
1719 xfs_btree_cur_t
*cnt_cur
; /* cursor for by-size btree */
1720 int error
; /* error return value */
1721 xfs_agblock_t gtbno
; /* start of right neighbor block */
1722 xfs_extlen_t gtlen
; /* length of right neighbor block */
1723 int haveleft
; /* have a left neighbor block */
1724 int haveright
; /* have a right neighbor block */
1725 int i
; /* temp, result code */
1726 xfs_agblock_t ltbno
; /* start of left neighbor block */
1727 xfs_extlen_t ltlen
; /* length of left neighbor block */
1728 xfs_mount_t
*mp
; /* mount point struct for filesystem */
1729 xfs_agblock_t nbno
; /* new starting block of freespace */
1730 xfs_extlen_t nlen
; /* new length of freespace */
1731 xfs_perag_t
*pag
; /* per allocation group data */
1733 bno_cur
= cnt_cur
= NULL
;
1736 if (oinfo
->oi_owner
!= XFS_RMAP_OWN_UNKNOWN
) {
1737 error
= xfs_rmap_free(tp
, agbp
, agno
, bno
, len
, oinfo
);
1743 * Allocate and initialize a cursor for the by-block btree.
1745 bno_cur
= xfs_allocbt_init_cursor(mp
, tp
, agbp
, agno
, XFS_BTNUM_BNO
);
1747 * Look for a neighboring block on the left (lower block numbers)
1748 * that is contiguous with this space.
1750 if ((error
= xfs_alloc_lookup_le(bno_cur
, bno
, len
, &haveleft
)))
1754 * There is a block to our left.
1756 if ((error
= xfs_alloc_get_rec(bno_cur
, <bno
, <len
, &i
)))
1758 XFS_WANT_CORRUPTED_GOTO(mp
, i
== 1, error0
);
1760 * It's not contiguous, though.
1762 if (ltbno
+ ltlen
< bno
)
1766 * If this failure happens the request to free this
1767 * space was invalid, it's (partly) already free.
1770 XFS_WANT_CORRUPTED_GOTO(mp
,
1771 ltbno
+ ltlen
<= bno
, error0
);
1775 * Look for a neighboring block on the right (higher block numbers)
1776 * that is contiguous with this space.
1778 if ((error
= xfs_btree_increment(bno_cur
, 0, &haveright
)))
1782 * There is a block to our right.
1784 if ((error
= xfs_alloc_get_rec(bno_cur
, >bno
, >len
, &i
)))
1786 XFS_WANT_CORRUPTED_GOTO(mp
, i
== 1, error0
);
1788 * It's not contiguous, though.
1790 if (bno
+ len
< gtbno
)
1794 * If this failure happens the request to free this
1795 * space was invalid, it's (partly) already free.
1798 XFS_WANT_CORRUPTED_GOTO(mp
, gtbno
>= bno
+ len
, error0
);
1802 * Now allocate and initialize a cursor for the by-size tree.
1804 cnt_cur
= xfs_allocbt_init_cursor(mp
, tp
, agbp
, agno
, XFS_BTNUM_CNT
);
1806 * Have both left and right contiguous neighbors.
1807 * Merge all three into a single free block.
1809 if (haveleft
&& haveright
) {
1811 * Delete the old by-size entry on the left.
1813 if ((error
= xfs_alloc_lookup_eq(cnt_cur
, ltbno
, ltlen
, &i
)))
1815 XFS_WANT_CORRUPTED_GOTO(mp
, i
== 1, error0
);
1816 if ((error
= xfs_btree_delete(cnt_cur
, &i
)))
1818 XFS_WANT_CORRUPTED_GOTO(mp
, i
== 1, error0
);
1820 * Delete the old by-size entry on the right.
1822 if ((error
= xfs_alloc_lookup_eq(cnt_cur
, gtbno
, gtlen
, &i
)))
1824 XFS_WANT_CORRUPTED_GOTO(mp
, i
== 1, error0
);
1825 if ((error
= xfs_btree_delete(cnt_cur
, &i
)))
1827 XFS_WANT_CORRUPTED_GOTO(mp
, i
== 1, error0
);
1829 * Delete the old by-block entry for the right block.
1831 if ((error
= xfs_btree_delete(bno_cur
, &i
)))
1833 XFS_WANT_CORRUPTED_GOTO(mp
, i
== 1, error0
);
1835 * Move the by-block cursor back to the left neighbor.
1837 if ((error
= xfs_btree_decrement(bno_cur
, 0, &i
)))
1839 XFS_WANT_CORRUPTED_GOTO(mp
, i
== 1, error0
);
1842 * Check that this is the right record: delete didn't
1843 * mangle the cursor.
1846 xfs_agblock_t xxbno
;
1849 if ((error
= xfs_alloc_get_rec(bno_cur
, &xxbno
, &xxlen
,
1852 XFS_WANT_CORRUPTED_GOTO(mp
,
1853 i
== 1 && xxbno
== ltbno
&& xxlen
== ltlen
,
1858 * Update remaining by-block entry to the new, joined block.
1861 nlen
= len
+ ltlen
+ gtlen
;
1862 if ((error
= xfs_alloc_update(bno_cur
, nbno
, nlen
)))
1866 * Have only a left contiguous neighbor.
1867 * Merge it together with the new freespace.
1869 else if (haveleft
) {
1871 * Delete the old by-size entry on the left.
1873 if ((error
= xfs_alloc_lookup_eq(cnt_cur
, ltbno
, ltlen
, &i
)))
1875 XFS_WANT_CORRUPTED_GOTO(mp
, i
== 1, error0
);
1876 if ((error
= xfs_btree_delete(cnt_cur
, &i
)))
1878 XFS_WANT_CORRUPTED_GOTO(mp
, i
== 1, error0
);
1880 * Back up the by-block cursor to the left neighbor, and
1881 * update its length.
1883 if ((error
= xfs_btree_decrement(bno_cur
, 0, &i
)))
1885 XFS_WANT_CORRUPTED_GOTO(mp
, i
== 1, error0
);
1888 if ((error
= xfs_alloc_update(bno_cur
, nbno
, nlen
)))
1892 * Have only a right contiguous neighbor.
1893 * Merge it together with the new freespace.
1895 else if (haveright
) {
1897 * Delete the old by-size entry on the right.
1899 if ((error
= xfs_alloc_lookup_eq(cnt_cur
, gtbno
, gtlen
, &i
)))
1901 XFS_WANT_CORRUPTED_GOTO(mp
, i
== 1, error0
);
1902 if ((error
= xfs_btree_delete(cnt_cur
, &i
)))
1904 XFS_WANT_CORRUPTED_GOTO(mp
, i
== 1, error0
);
1906 * Update the starting block and length of the right
1907 * neighbor in the by-block tree.
1911 if ((error
= xfs_alloc_update(bno_cur
, nbno
, nlen
)))
1915 * No contiguous neighbors.
1916 * Insert the new freespace into the by-block tree.
1921 if ((error
= xfs_btree_insert(bno_cur
, &i
)))
1923 XFS_WANT_CORRUPTED_GOTO(mp
, i
== 1, error0
);
1925 xfs_btree_del_cursor(bno_cur
, XFS_BTREE_NOERROR
);
1928 * In all cases we need to insert the new freespace in the by-size tree.
1930 if ((error
= xfs_alloc_lookup_eq(cnt_cur
, nbno
, nlen
, &i
)))
1932 XFS_WANT_CORRUPTED_GOTO(mp
, i
== 0, error0
);
1933 if ((error
= xfs_btree_insert(cnt_cur
, &i
)))
1935 XFS_WANT_CORRUPTED_GOTO(mp
, i
== 1, error0
);
1936 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_NOERROR
);
1940 * Update the freespace totals in the ag and superblock.
1942 pag
= xfs_perag_get(mp
, agno
);
1943 error
= xfs_alloc_update_counters(tp
, pag
, agbp
, len
);
1944 xfs_ag_resv_free_extent(pag
, type
, tp
, len
);
1949 XFS_STATS_INC(mp
, xs_freex
);
1950 XFS_STATS_ADD(mp
, xs_freeb
, len
);
1952 trace_xfs_free_extent(mp
, agno
, bno
, len
, type
== XFS_AG_RESV_AGFL
,
1953 haveleft
, haveright
);
1958 trace_xfs_free_extent(mp
, agno
, bno
, len
, type
== XFS_AG_RESV_AGFL
,
1961 xfs_btree_del_cursor(bno_cur
, XFS_BTREE_ERROR
);
1963 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_ERROR
);
1968 * Visible (exported) allocation/free functions.
1969 * Some of these are used just by xfs_alloc_btree.c and this file.
1973 * Compute and fill in value of m_ag_maxlevels.
1976 xfs_alloc_compute_maxlevels(
1977 xfs_mount_t
*mp
) /* file system mount structure */
1979 mp
->m_ag_maxlevels
= xfs_btree_compute_maxlevels(mp
, mp
->m_alloc_mnr
,
1980 (mp
->m_sb
.sb_agblocks
+ 1) / 2);
1984 * Find the length of the longest extent in an AG. The 'need' parameter
1985 * specifies how much space we're going to need for the AGFL and the
1986 * 'reserved' parameter tells us how many blocks in this AG are reserved for
1990 xfs_alloc_longest_free_extent(
1991 struct xfs_mount
*mp
,
1992 struct xfs_perag
*pag
,
1994 xfs_extlen_t reserved
)
1996 xfs_extlen_t delta
= 0;
1999 * If the AGFL needs a recharge, we'll have to subtract that from the
2002 if (need
> pag
->pagf_flcount
)
2003 delta
= need
- pag
->pagf_flcount
;
2006 * If we cannot maintain others' reservations with space from the
2007 * not-longest freesp extents, we'll have to subtract /that/ from
2008 * the longest extent too.
2010 if (pag
->pagf_freeblks
- pag
->pagf_longest
< reserved
)
2011 delta
+= reserved
- (pag
->pagf_freeblks
- pag
->pagf_longest
);
2014 * If the longest extent is long enough to satisfy all the
2015 * reservations and AGFL rules in place, we can return this extent.
2017 if (pag
->pagf_longest
> delta
)
2018 return pag
->pagf_longest
- delta
;
2020 /* Otherwise, let the caller try for 1 block if there's space. */
2021 return pag
->pagf_flcount
> 0 || pag
->pagf_longest
> 0;
2025 xfs_alloc_min_freelist(
2026 struct xfs_mount
*mp
,
2027 struct xfs_perag
*pag
)
2029 unsigned int min_free
;
2031 /* space needed by-bno freespace btree */
2032 min_free
= min_t(unsigned int, pag
->pagf_levels
[XFS_BTNUM_BNOi
] + 1,
2033 mp
->m_ag_maxlevels
);
2034 /* space needed by-size freespace btree */
2035 min_free
+= min_t(unsigned int, pag
->pagf_levels
[XFS_BTNUM_CNTi
] + 1,
2036 mp
->m_ag_maxlevels
);
2037 /* space needed reverse mapping used space btree */
2038 if (xfs_sb_version_hasrmapbt(&mp
->m_sb
))
2039 min_free
+= min_t(unsigned int,
2040 pag
->pagf_levels
[XFS_BTNUM_RMAPi
] + 1,
2041 mp
->m_rmap_maxlevels
);
2047 * Check if the operation we are fixing up the freelist for should go ahead or
2048 * not. If we are freeing blocks, we always allow it, otherwise the allocation
2049 * is dependent on whether the size and shape of free space available will
2050 * permit the requested allocation to take place.
2053 xfs_alloc_space_available(
2054 struct xfs_alloc_arg
*args
,
2055 xfs_extlen_t min_free
,
2058 struct xfs_perag
*pag
= args
->pag
;
2059 xfs_extlen_t longest
;
2060 xfs_extlen_t reservation
; /* blocks that are still reserved */
2063 if (flags
& XFS_ALLOC_FLAG_FREEING
)
2066 reservation
= xfs_ag_resv_needed(pag
, args
->resv
);
2068 /* do we have enough contiguous free space for the allocation? */
2069 longest
= xfs_alloc_longest_free_extent(args
->mp
, pag
, min_free
,
2071 if ((args
->minlen
+ args
->alignment
+ args
->minalignslop
- 1) > longest
)
2074 /* do we have enough free space remaining for the allocation? */
2075 available
= (int)(pag
->pagf_freeblks
+ pag
->pagf_flcount
-
2076 reservation
- min_free
- args
->total
);
2077 if (available
< (int)args
->minleft
|| available
<= 0)
2084 * Decide whether to use this allocation group for this allocation.
2085 * If so, fix up the btree freelist's size.
2088 xfs_alloc_fix_freelist(
2089 struct xfs_alloc_arg
*args
, /* allocation argument structure */
2090 int flags
) /* XFS_ALLOC_FLAG_... */
2092 struct xfs_mount
*mp
= args
->mp
;
2093 struct xfs_perag
*pag
= args
->pag
;
2094 struct xfs_trans
*tp
= args
->tp
;
2095 struct xfs_buf
*agbp
= NULL
;
2096 struct xfs_buf
*agflbp
= NULL
;
2097 struct xfs_alloc_arg targs
; /* local allocation arguments */
2098 xfs_agblock_t bno
; /* freelist block */
2099 xfs_extlen_t need
; /* total blocks needed in freelist */
2102 if (!pag
->pagf_init
) {
2103 error
= xfs_alloc_read_agf(mp
, tp
, args
->agno
, flags
, &agbp
);
2106 if (!pag
->pagf_init
) {
2107 ASSERT(flags
& XFS_ALLOC_FLAG_TRYLOCK
);
2108 ASSERT(!(flags
& XFS_ALLOC_FLAG_FREEING
));
2109 goto out_agbp_relse
;
2114 * If this is a metadata preferred pag and we are user data then try
2115 * somewhere else if we are not being asked to try harder at this
2118 if (pag
->pagf_metadata
&& xfs_alloc_is_userdata(args
->datatype
) &&
2119 (flags
& XFS_ALLOC_FLAG_TRYLOCK
)) {
2120 ASSERT(!(flags
& XFS_ALLOC_FLAG_FREEING
));
2121 goto out_agbp_relse
;
2124 need
= xfs_alloc_min_freelist(mp
, pag
);
2125 if (!xfs_alloc_space_available(args
, need
, flags
))
2126 goto out_agbp_relse
;
2129 * Get the a.g. freespace buffer.
2130 * Can fail if we're not blocking on locks, and it's held.
2133 error
= xfs_alloc_read_agf(mp
, tp
, args
->agno
, flags
, &agbp
);
2137 ASSERT(flags
& XFS_ALLOC_FLAG_TRYLOCK
);
2138 ASSERT(!(flags
& XFS_ALLOC_FLAG_FREEING
));
2143 /* If there isn't enough total space or single-extent, reject it. */
2144 need
= xfs_alloc_min_freelist(mp
, pag
);
2145 if (!xfs_alloc_space_available(args
, need
, flags
))
2146 goto out_agbp_relse
;
2149 * Make the freelist shorter if it's too long.
2151 * Note that from this point onwards, we will always release the agf and
2152 * agfl buffers on error. This handles the case where we error out and
2153 * the buffers are clean or may not have been joined to the transaction
2154 * and hence need to be released manually. If they have been joined to
2155 * the transaction, then xfs_trans_brelse() will handle them
2156 * appropriately based on the recursion count and dirty state of the
2159 * XXX (dgc): When we have lots of free space, does this buy us
2160 * anything other than extra overhead when we need to put more blocks
2161 * back on the free list? Maybe we should only do this when space is
2162 * getting low or the AGFL is more than half full?
2164 * The NOSHRINK flag prevents the AGFL from being shrunk if it's too
2165 * big; the NORMAP flag prevents AGFL expand/shrink operations from
2166 * updating the rmapbt. Both flags are used in xfs_repair while we're
2167 * rebuilding the rmapbt, and neither are used by the kernel. They're
2168 * both required to ensure that rmaps are correctly recorded for the
2169 * regenerated AGFL, bnobt, and cntbt. See repair/phase5.c and
2170 * repair/rmap.c in xfsprogs for details.
2172 memset(&targs
, 0, sizeof(targs
));
2173 if (flags
& XFS_ALLOC_FLAG_NORMAP
)
2174 xfs_rmap_skip_owner_update(&targs
.oinfo
);
2176 xfs_rmap_ag_owner(&targs
.oinfo
, XFS_RMAP_OWN_AG
);
2177 while (!(flags
& XFS_ALLOC_FLAG_NOSHRINK
) && pag
->pagf_flcount
> need
) {
2180 error
= xfs_alloc_get_freelist(tp
, agbp
, &bno
, 0);
2182 goto out_agbp_relse
;
2183 error
= xfs_free_ag_extent(tp
, agbp
, args
->agno
, bno
, 1,
2184 &targs
.oinfo
, XFS_AG_RESV_AGFL
);
2186 goto out_agbp_relse
;
2187 bp
= xfs_btree_get_bufs(mp
, tp
, args
->agno
, bno
, 0);
2188 xfs_trans_binval(tp
, bp
);
2194 targs
.agno
= args
->agno
;
2195 targs
.alignment
= targs
.minlen
= targs
.prod
= 1;
2196 targs
.type
= XFS_ALLOCTYPE_THIS_AG
;
2198 error
= xfs_alloc_read_agfl(mp
, tp
, targs
.agno
, &agflbp
);
2200 goto out_agbp_relse
;
2202 /* Make the freelist longer if it's too short. */
2203 while (pag
->pagf_flcount
< need
) {
2205 targs
.maxlen
= need
- pag
->pagf_flcount
;
2206 targs
.resv
= XFS_AG_RESV_AGFL
;
2208 /* Allocate as many blocks as possible at once. */
2209 error
= xfs_alloc_ag_vextent(&targs
);
2211 goto out_agflbp_relse
;
2214 * Stop if we run out. Won't happen if callers are obeying
2215 * the restrictions correctly. Can happen for free calls
2216 * on a completely full ag.
2218 if (targs
.agbno
== NULLAGBLOCK
) {
2219 if (flags
& XFS_ALLOC_FLAG_FREEING
)
2221 goto out_agflbp_relse
;
2224 * Put each allocated block on the list.
2226 for (bno
= targs
.agbno
; bno
< targs
.agbno
+ targs
.len
; bno
++) {
2227 error
= xfs_alloc_put_freelist(tp
, agbp
,
2230 goto out_agflbp_relse
;
2233 xfs_trans_brelse(tp
, agflbp
);
2238 xfs_trans_brelse(tp
, agflbp
);
2241 xfs_trans_brelse(tp
, agbp
);
2248 * Get a block from the freelist.
2249 * Returns with the buffer for the block gotten.
2252 xfs_alloc_get_freelist(
2253 xfs_trans_t
*tp
, /* transaction pointer */
2254 xfs_buf_t
*agbp
, /* buffer containing the agf structure */
2255 xfs_agblock_t
*bnop
, /* block address retrieved from freelist */
2256 int btreeblk
) /* destination is a AGF btree */
2258 xfs_agf_t
*agf
; /* a.g. freespace structure */
2259 xfs_buf_t
*agflbp
;/* buffer for a.g. freelist structure */
2260 xfs_agblock_t bno
; /* block number returned */
2264 xfs_mount_t
*mp
= tp
->t_mountp
;
2265 xfs_perag_t
*pag
; /* per allocation group data */
2268 * Freelist is empty, give up.
2270 agf
= XFS_BUF_TO_AGF(agbp
);
2271 if (!agf
->agf_flcount
) {
2272 *bnop
= NULLAGBLOCK
;
2276 * Read the array of free blocks.
2278 error
= xfs_alloc_read_agfl(mp
, tp
, be32_to_cpu(agf
->agf_seqno
),
2285 * Get the block number and update the data structures.
2287 agfl_bno
= XFS_BUF_TO_AGFL_BNO(mp
, agflbp
);
2288 bno
= be32_to_cpu(agfl_bno
[be32_to_cpu(agf
->agf_flfirst
)]);
2289 be32_add_cpu(&agf
->agf_flfirst
, 1);
2290 xfs_trans_brelse(tp
, agflbp
);
2291 if (be32_to_cpu(agf
->agf_flfirst
) == XFS_AGFL_SIZE(mp
))
2292 agf
->agf_flfirst
= 0;
2294 pag
= xfs_perag_get(mp
, be32_to_cpu(agf
->agf_seqno
));
2295 be32_add_cpu(&agf
->agf_flcount
, -1);
2296 xfs_trans_agflist_delta(tp
, -1);
2297 pag
->pagf_flcount
--;
2300 logflags
= XFS_AGF_FLFIRST
| XFS_AGF_FLCOUNT
;
2302 be32_add_cpu(&agf
->agf_btreeblks
, 1);
2303 pag
->pagf_btreeblks
++;
2304 logflags
|= XFS_AGF_BTREEBLKS
;
2307 xfs_alloc_log_agf(tp
, agbp
, logflags
);
2314 * Log the given fields from the agf structure.
2318 xfs_trans_t
*tp
, /* transaction pointer */
2319 xfs_buf_t
*bp
, /* buffer for a.g. freelist header */
2320 int fields
) /* mask of fields to be logged (XFS_AGF_...) */
2322 int first
; /* first byte offset */
2323 int last
; /* last byte offset */
2324 static const short offsets
[] = {
2325 offsetof(xfs_agf_t
, agf_magicnum
),
2326 offsetof(xfs_agf_t
, agf_versionnum
),
2327 offsetof(xfs_agf_t
, agf_seqno
),
2328 offsetof(xfs_agf_t
, agf_length
),
2329 offsetof(xfs_agf_t
, agf_roots
[0]),
2330 offsetof(xfs_agf_t
, agf_levels
[0]),
2331 offsetof(xfs_agf_t
, agf_flfirst
),
2332 offsetof(xfs_agf_t
, agf_fllast
),
2333 offsetof(xfs_agf_t
, agf_flcount
),
2334 offsetof(xfs_agf_t
, agf_freeblks
),
2335 offsetof(xfs_agf_t
, agf_longest
),
2336 offsetof(xfs_agf_t
, agf_btreeblks
),
2337 offsetof(xfs_agf_t
, agf_uuid
),
2338 offsetof(xfs_agf_t
, agf_rmap_blocks
),
2339 offsetof(xfs_agf_t
, agf_refcount_blocks
),
2340 offsetof(xfs_agf_t
, agf_refcount_root
),
2341 offsetof(xfs_agf_t
, agf_refcount_level
),
2342 /* needed so that we don't log the whole rest of the structure: */
2343 offsetof(xfs_agf_t
, agf_spare64
),
2347 trace_xfs_agf(tp
->t_mountp
, XFS_BUF_TO_AGF(bp
), fields
, _RET_IP_
);
2349 xfs_trans_buf_set_type(tp
, bp
, XFS_BLFT_AGF_BUF
);
2351 xfs_btree_offsets(fields
, offsets
, XFS_AGF_NUM_BITS
, &first
, &last
);
2352 xfs_trans_log_buf(tp
, bp
, (uint
)first
, (uint
)last
);
2356 * Interface for inode allocation to force the pag data to be initialized.
2359 xfs_alloc_pagf_init(
2360 xfs_mount_t
*mp
, /* file system mount structure */
2361 xfs_trans_t
*tp
, /* transaction pointer */
2362 xfs_agnumber_t agno
, /* allocation group number */
2363 int flags
) /* XFS_ALLOC_FLAGS_... */
2368 if ((error
= xfs_alloc_read_agf(mp
, tp
, agno
, flags
, &bp
)))
2371 xfs_trans_brelse(tp
, bp
);
2376 * Put the block on the freelist for the allocation group.
2379 xfs_alloc_put_freelist(
2380 xfs_trans_t
*tp
, /* transaction pointer */
2381 xfs_buf_t
*agbp
, /* buffer for a.g. freelist header */
2382 xfs_buf_t
*agflbp
,/* buffer for a.g. free block array */
2383 xfs_agblock_t bno
, /* block being freed */
2384 int btreeblk
) /* block came from a AGF btree */
2386 xfs_agf_t
*agf
; /* a.g. freespace structure */
2387 __be32
*blockp
;/* pointer to array entry */
2390 xfs_mount_t
*mp
; /* mount structure */
2391 xfs_perag_t
*pag
; /* per allocation group data */
2395 agf
= XFS_BUF_TO_AGF(agbp
);
2398 if (!agflbp
&& (error
= xfs_alloc_read_agfl(mp
, tp
,
2399 be32_to_cpu(agf
->agf_seqno
), &agflbp
)))
2401 be32_add_cpu(&agf
->agf_fllast
, 1);
2402 if (be32_to_cpu(agf
->agf_fllast
) == XFS_AGFL_SIZE(mp
))
2403 agf
->agf_fllast
= 0;
2405 pag
= xfs_perag_get(mp
, be32_to_cpu(agf
->agf_seqno
));
2406 be32_add_cpu(&agf
->agf_flcount
, 1);
2407 xfs_trans_agflist_delta(tp
, 1);
2408 pag
->pagf_flcount
++;
2410 logflags
= XFS_AGF_FLLAST
| XFS_AGF_FLCOUNT
;
2412 be32_add_cpu(&agf
->agf_btreeblks
, -1);
2413 pag
->pagf_btreeblks
--;
2414 logflags
|= XFS_AGF_BTREEBLKS
;
2418 xfs_alloc_log_agf(tp
, agbp
, logflags
);
2420 ASSERT(be32_to_cpu(agf
->agf_flcount
) <= XFS_AGFL_SIZE(mp
));
2422 agfl_bno
= XFS_BUF_TO_AGFL_BNO(mp
, agflbp
);
2423 blockp
= &agfl_bno
[be32_to_cpu(agf
->agf_fllast
)];
2424 *blockp
= cpu_to_be32(bno
);
2425 startoff
= (char *)blockp
- (char *)agflbp
->b_addr
;
2427 xfs_alloc_log_agf(tp
, agbp
, logflags
);
2429 xfs_trans_buf_set_type(tp
, agflbp
, XFS_BLFT_AGFL_BUF
);
2430 xfs_trans_log_buf(tp
, agflbp
, startoff
,
2431 startoff
+ sizeof(xfs_agblock_t
) - 1);
2437 struct xfs_mount
*mp
,
2440 struct xfs_agf
*agf
= XFS_BUF_TO_AGF(bp
);
2442 if (xfs_sb_version_hascrc(&mp
->m_sb
)) {
2443 if (!uuid_equal(&agf
->agf_uuid
, &mp
->m_sb
.sb_meta_uuid
))
2445 if (!xfs_log_check_lsn(mp
,
2446 be64_to_cpu(XFS_BUF_TO_AGF(bp
)->agf_lsn
)))
2450 if (!(agf
->agf_magicnum
== cpu_to_be32(XFS_AGF_MAGIC
) &&
2451 XFS_AGF_GOOD_VERSION(be32_to_cpu(agf
->agf_versionnum
)) &&
2452 be32_to_cpu(agf
->agf_freeblks
) <= be32_to_cpu(agf
->agf_length
) &&
2453 be32_to_cpu(agf
->agf_flfirst
) < XFS_AGFL_SIZE(mp
) &&
2454 be32_to_cpu(agf
->agf_fllast
) < XFS_AGFL_SIZE(mp
) &&
2455 be32_to_cpu(agf
->agf_flcount
) <= XFS_AGFL_SIZE(mp
)))
2458 if (be32_to_cpu(agf
->agf_levels
[XFS_BTNUM_BNO
]) < 1 ||
2459 be32_to_cpu(agf
->agf_levels
[XFS_BTNUM_CNT
]) < 1 ||
2460 be32_to_cpu(agf
->agf_levels
[XFS_BTNUM_BNO
]) > XFS_BTREE_MAXLEVELS
||
2461 be32_to_cpu(agf
->agf_levels
[XFS_BTNUM_CNT
]) > XFS_BTREE_MAXLEVELS
)
2464 if (xfs_sb_version_hasrmapbt(&mp
->m_sb
) &&
2465 (be32_to_cpu(agf
->agf_levels
[XFS_BTNUM_RMAP
]) < 1 ||
2466 be32_to_cpu(agf
->agf_levels
[XFS_BTNUM_RMAP
]) > XFS_BTREE_MAXLEVELS
))
2470 * during growfs operations, the perag is not fully initialised,
2471 * so we can't use it for any useful checking. growfs ensures we can't
2472 * use it by using uncached buffers that don't have the perag attached
2473 * so we can detect and avoid this problem.
2475 if (bp
->b_pag
&& be32_to_cpu(agf
->agf_seqno
) != bp
->b_pag
->pag_agno
)
2478 if (xfs_sb_version_haslazysbcount(&mp
->m_sb
) &&
2479 be32_to_cpu(agf
->agf_btreeblks
) > be32_to_cpu(agf
->agf_length
))
2482 if (xfs_sb_version_hasreflink(&mp
->m_sb
) &&
2483 (be32_to_cpu(agf
->agf_refcount_level
) < 1 ||
2484 be32_to_cpu(agf
->agf_refcount_level
) > XFS_BTREE_MAXLEVELS
))
2492 xfs_agf_read_verify(
2495 struct xfs_mount
*mp
= bp
->b_target
->bt_mount
;
2497 if (xfs_sb_version_hascrc(&mp
->m_sb
) &&
2498 !xfs_buf_verify_cksum(bp
, XFS_AGF_CRC_OFF
))
2499 xfs_buf_ioerror(bp
, -EFSBADCRC
);
2500 else if (XFS_TEST_ERROR(!xfs_agf_verify(mp
, bp
), mp
,
2501 XFS_ERRTAG_ALLOC_READ_AGF
,
2502 XFS_RANDOM_ALLOC_READ_AGF
))
2503 xfs_buf_ioerror(bp
, -EFSCORRUPTED
);
2506 xfs_verifier_error(bp
);
2510 xfs_agf_write_verify(
2513 struct xfs_mount
*mp
= bp
->b_target
->bt_mount
;
2514 struct xfs_buf_log_item
*bip
= bp
->b_fspriv
;
2516 if (!xfs_agf_verify(mp
, bp
)) {
2517 xfs_buf_ioerror(bp
, -EFSCORRUPTED
);
2518 xfs_verifier_error(bp
);
2522 if (!xfs_sb_version_hascrc(&mp
->m_sb
))
2526 XFS_BUF_TO_AGF(bp
)->agf_lsn
= cpu_to_be64(bip
->bli_item
.li_lsn
);
2528 xfs_buf_update_cksum(bp
, XFS_AGF_CRC_OFF
);
2531 const struct xfs_buf_ops xfs_agf_buf_ops
= {
2533 .verify_read
= xfs_agf_read_verify
,
2534 .verify_write
= xfs_agf_write_verify
,
2538 * Read in the allocation group header (free/alloc section).
2542 struct xfs_mount
*mp
, /* mount point structure */
2543 struct xfs_trans
*tp
, /* transaction pointer */
2544 xfs_agnumber_t agno
, /* allocation group number */
2545 int flags
, /* XFS_BUF_ */
2546 struct xfs_buf
**bpp
) /* buffer for the ag freelist header */
2550 trace_xfs_read_agf(mp
, agno
);
2552 ASSERT(agno
!= NULLAGNUMBER
);
2553 error
= xfs_trans_read_buf(
2554 mp
, tp
, mp
->m_ddev_targp
,
2555 XFS_AG_DADDR(mp
, agno
, XFS_AGF_DADDR(mp
)),
2556 XFS_FSS_TO_BB(mp
, 1), flags
, bpp
, &xfs_agf_buf_ops
);
2562 ASSERT(!(*bpp
)->b_error
);
2563 xfs_buf_set_ref(*bpp
, XFS_AGF_REF
);
2568 * Read in the allocation group header (free/alloc section).
2572 struct xfs_mount
*mp
, /* mount point structure */
2573 struct xfs_trans
*tp
, /* transaction pointer */
2574 xfs_agnumber_t agno
, /* allocation group number */
2575 int flags
, /* XFS_ALLOC_FLAG_... */
2576 struct xfs_buf
**bpp
) /* buffer for the ag freelist header */
2578 struct xfs_agf
*agf
; /* ag freelist header */
2579 struct xfs_perag
*pag
; /* per allocation group data */
2582 trace_xfs_alloc_read_agf(mp
, agno
);
2584 ASSERT(agno
!= NULLAGNUMBER
);
2585 error
= xfs_read_agf(mp
, tp
, agno
,
2586 (flags
& XFS_ALLOC_FLAG_TRYLOCK
) ? XBF_TRYLOCK
: 0,
2592 ASSERT(!(*bpp
)->b_error
);
2594 agf
= XFS_BUF_TO_AGF(*bpp
);
2595 pag
= xfs_perag_get(mp
, agno
);
2596 if (!pag
->pagf_init
) {
2597 pag
->pagf_freeblks
= be32_to_cpu(agf
->agf_freeblks
);
2598 pag
->pagf_btreeblks
= be32_to_cpu(agf
->agf_btreeblks
);
2599 pag
->pagf_flcount
= be32_to_cpu(agf
->agf_flcount
);
2600 pag
->pagf_longest
= be32_to_cpu(agf
->agf_longest
);
2601 pag
->pagf_levels
[XFS_BTNUM_BNOi
] =
2602 be32_to_cpu(agf
->agf_levels
[XFS_BTNUM_BNOi
]);
2603 pag
->pagf_levels
[XFS_BTNUM_CNTi
] =
2604 be32_to_cpu(agf
->agf_levels
[XFS_BTNUM_CNTi
]);
2605 pag
->pagf_levels
[XFS_BTNUM_RMAPi
] =
2606 be32_to_cpu(agf
->agf_levels
[XFS_BTNUM_RMAPi
]);
2607 pag
->pagf_refcount_level
= be32_to_cpu(agf
->agf_refcount_level
);
2608 spin_lock_init(&pag
->pagb_lock
);
2609 pag
->pagb_count
= 0;
2610 pag
->pagb_tree
= RB_ROOT
;
2614 else if (!XFS_FORCED_SHUTDOWN(mp
)) {
2615 ASSERT(pag
->pagf_freeblks
== be32_to_cpu(agf
->agf_freeblks
));
2616 ASSERT(pag
->pagf_btreeblks
== be32_to_cpu(agf
->agf_btreeblks
));
2617 ASSERT(pag
->pagf_flcount
== be32_to_cpu(agf
->agf_flcount
));
2618 ASSERT(pag
->pagf_longest
== be32_to_cpu(agf
->agf_longest
));
2619 ASSERT(pag
->pagf_levels
[XFS_BTNUM_BNOi
] ==
2620 be32_to_cpu(agf
->agf_levels
[XFS_BTNUM_BNOi
]));
2621 ASSERT(pag
->pagf_levels
[XFS_BTNUM_CNTi
] ==
2622 be32_to_cpu(agf
->agf_levels
[XFS_BTNUM_CNTi
]));
2630 * Allocate an extent (variable-size).
2631 * Depending on the allocation type, we either look in a single allocation
2632 * group or loop over the allocation groups to find the result.
2636 xfs_alloc_arg_t
*args
) /* allocation argument structure */
2638 xfs_agblock_t agsize
; /* allocation group size */
2640 int flags
; /* XFS_ALLOC_FLAG_... locking flags */
2641 xfs_extlen_t minleft
;/* minimum left value, temp copy */
2642 xfs_mount_t
*mp
; /* mount structure pointer */
2643 xfs_agnumber_t sagno
; /* starting allocation group number */
2644 xfs_alloctype_t type
; /* input allocation type */
2647 xfs_agnumber_t rotorstep
= xfs_rotorstep
; /* inode32 agf stepper */
2650 type
= args
->otype
= args
->type
;
2651 args
->agbno
= NULLAGBLOCK
;
2653 * Just fix this up, for the case where the last a.g. is shorter
2654 * (or there's only one a.g.) and the caller couldn't easily figure
2655 * that out (xfs_bmap_alloc).
2657 agsize
= mp
->m_sb
.sb_agblocks
;
2658 if (args
->maxlen
> agsize
)
2659 args
->maxlen
= agsize
;
2660 if (args
->alignment
== 0)
2661 args
->alignment
= 1;
2662 ASSERT(XFS_FSB_TO_AGNO(mp
, args
->fsbno
) < mp
->m_sb
.sb_agcount
);
2663 ASSERT(XFS_FSB_TO_AGBNO(mp
, args
->fsbno
) < agsize
);
2664 ASSERT(args
->minlen
<= args
->maxlen
);
2665 ASSERT(args
->minlen
<= agsize
);
2666 ASSERT(args
->mod
< args
->prod
);
2667 if (XFS_FSB_TO_AGNO(mp
, args
->fsbno
) >= mp
->m_sb
.sb_agcount
||
2668 XFS_FSB_TO_AGBNO(mp
, args
->fsbno
) >= agsize
||
2669 args
->minlen
> args
->maxlen
|| args
->minlen
> agsize
||
2670 args
->mod
>= args
->prod
) {
2671 args
->fsbno
= NULLFSBLOCK
;
2672 trace_xfs_alloc_vextent_badargs(args
);
2675 minleft
= args
->minleft
;
2678 case XFS_ALLOCTYPE_THIS_AG
:
2679 case XFS_ALLOCTYPE_NEAR_BNO
:
2680 case XFS_ALLOCTYPE_THIS_BNO
:
2682 * These three force us into a single a.g.
2684 args
->agno
= XFS_FSB_TO_AGNO(mp
, args
->fsbno
);
2685 args
->pag
= xfs_perag_get(mp
, args
->agno
);
2687 error
= xfs_alloc_fix_freelist(args
, 0);
2688 args
->minleft
= minleft
;
2690 trace_xfs_alloc_vextent_nofix(args
);
2694 trace_xfs_alloc_vextent_noagbp(args
);
2697 args
->agbno
= XFS_FSB_TO_AGBNO(mp
, args
->fsbno
);
2698 if ((error
= xfs_alloc_ag_vextent(args
)))
2701 case XFS_ALLOCTYPE_START_BNO
:
2703 * Try near allocation first, then anywhere-in-ag after
2704 * the first a.g. fails.
2706 if ((args
->datatype
& XFS_ALLOC_INITIAL_USER_DATA
) &&
2707 (mp
->m_flags
& XFS_MOUNT_32BITINODES
)) {
2708 args
->fsbno
= XFS_AGB_TO_FSB(mp
,
2709 ((mp
->m_agfrotor
/ rotorstep
) %
2710 mp
->m_sb
.sb_agcount
), 0);
2713 args
->agbno
= XFS_FSB_TO_AGBNO(mp
, args
->fsbno
);
2714 args
->type
= XFS_ALLOCTYPE_NEAR_BNO
;
2716 case XFS_ALLOCTYPE_ANY_AG
:
2717 case XFS_ALLOCTYPE_START_AG
:
2718 case XFS_ALLOCTYPE_FIRST_AG
:
2720 * Rotate through the allocation groups looking for a winner.
2722 if (type
== XFS_ALLOCTYPE_ANY_AG
) {
2724 * Start with the last place we left off.
2726 args
->agno
= sagno
= (mp
->m_agfrotor
/ rotorstep
) %
2727 mp
->m_sb
.sb_agcount
;
2728 args
->type
= XFS_ALLOCTYPE_THIS_AG
;
2729 flags
= XFS_ALLOC_FLAG_TRYLOCK
;
2730 } else if (type
== XFS_ALLOCTYPE_FIRST_AG
) {
2732 * Start with allocation group given by bno.
2734 args
->agno
= XFS_FSB_TO_AGNO(mp
, args
->fsbno
);
2735 args
->type
= XFS_ALLOCTYPE_THIS_AG
;
2739 if (type
== XFS_ALLOCTYPE_START_AG
)
2740 args
->type
= XFS_ALLOCTYPE_THIS_AG
;
2742 * Start with the given allocation group.
2744 args
->agno
= sagno
= XFS_FSB_TO_AGNO(mp
, args
->fsbno
);
2745 flags
= XFS_ALLOC_FLAG_TRYLOCK
;
2748 * Loop over allocation groups twice; first time with
2749 * trylock set, second time without.
2752 args
->pag
= xfs_perag_get(mp
, args
->agno
);
2753 if (no_min
) args
->minleft
= 0;
2754 error
= xfs_alloc_fix_freelist(args
, flags
);
2755 args
->minleft
= minleft
;
2757 trace_xfs_alloc_vextent_nofix(args
);
2761 * If we get a buffer back then the allocation will fly.
2764 if ((error
= xfs_alloc_ag_vextent(args
)))
2769 trace_xfs_alloc_vextent_loopfailed(args
);
2772 * Didn't work, figure out the next iteration.
2774 if (args
->agno
== sagno
&&
2775 type
== XFS_ALLOCTYPE_START_BNO
)
2776 args
->type
= XFS_ALLOCTYPE_THIS_AG
;
2778 * For the first allocation, we can try any AG to get
2779 * space. However, if we already have allocated a
2780 * block, we don't want to try AGs whose number is below
2781 * sagno. Otherwise, we may end up with out-of-order
2782 * locking of AGF, which might cause deadlock.
2784 if (++(args
->agno
) == mp
->m_sb
.sb_agcount
) {
2785 if (args
->firstblock
!= NULLFSBLOCK
)
2791 * Reached the starting a.g., must either be done
2792 * or switch to non-trylock mode.
2794 if (args
->agno
== sagno
) {
2796 args
->agbno
= NULLAGBLOCK
;
2797 trace_xfs_alloc_vextent_allfailed(args
);
2804 if (type
== XFS_ALLOCTYPE_START_BNO
) {
2805 args
->agbno
= XFS_FSB_TO_AGBNO(mp
,
2807 args
->type
= XFS_ALLOCTYPE_NEAR_BNO
;
2811 xfs_perag_put(args
->pag
);
2813 if (bump_rotor
|| (type
== XFS_ALLOCTYPE_ANY_AG
)) {
2814 if (args
->agno
== sagno
)
2815 mp
->m_agfrotor
= (mp
->m_agfrotor
+ 1) %
2816 (mp
->m_sb
.sb_agcount
* rotorstep
);
2818 mp
->m_agfrotor
= (args
->agno
* rotorstep
+ 1) %
2819 (mp
->m_sb
.sb_agcount
* rotorstep
);
2826 if (args
->agbno
== NULLAGBLOCK
)
2827 args
->fsbno
= NULLFSBLOCK
;
2829 args
->fsbno
= XFS_AGB_TO_FSB(mp
, args
->agno
, args
->agbno
);
2831 ASSERT(args
->len
>= args
->minlen
);
2832 ASSERT(args
->len
<= args
->maxlen
);
2833 ASSERT(args
->agbno
% args
->alignment
== 0);
2834 XFS_AG_CHECK_DADDR(mp
, XFS_FSB_TO_DADDR(mp
, args
->fsbno
),
2838 /* Zero the extent if we were asked to do so */
2839 if (args
->datatype
& XFS_ALLOC_USERDATA_ZERO
) {
2840 error
= xfs_zero_extent(args
->ip
, args
->fsbno
, args
->len
);
2846 xfs_perag_put(args
->pag
);
2849 xfs_perag_put(args
->pag
);
2853 /* Ensure that the freelist is at full capacity. */
2855 xfs_free_extent_fix_freelist(
2856 struct xfs_trans
*tp
,
2857 xfs_agnumber_t agno
,
2858 struct xfs_buf
**agbp
)
2860 struct xfs_alloc_arg args
;
2863 memset(&args
, 0, sizeof(struct xfs_alloc_arg
));
2865 args
.mp
= tp
->t_mountp
;
2869 * validate that the block number is legal - the enables us to detect
2870 * and handle a silent filesystem corruption rather than crashing.
2872 if (args
.agno
>= args
.mp
->m_sb
.sb_agcount
)
2873 return -EFSCORRUPTED
;
2875 args
.pag
= xfs_perag_get(args
.mp
, args
.agno
);
2878 error
= xfs_alloc_fix_freelist(&args
, XFS_ALLOC_FLAG_FREEING
);
2884 xfs_perag_put(args
.pag
);
2890 * Just break up the extent address and hand off to xfs_free_ag_extent
2891 * after fixing up the freelist.
2895 struct xfs_trans
*tp
, /* transaction pointer */
2896 xfs_fsblock_t bno
, /* starting block number of extent */
2897 xfs_extlen_t len
, /* length of extent */
2898 struct xfs_owner_info
*oinfo
, /* extent owner */
2899 enum xfs_ag_resv_type type
) /* block reservation type */
2901 struct xfs_mount
*mp
= tp
->t_mountp
;
2902 struct xfs_buf
*agbp
;
2903 xfs_agnumber_t agno
= XFS_FSB_TO_AGNO(mp
, bno
);
2904 xfs_agblock_t agbno
= XFS_FSB_TO_AGBNO(mp
, bno
);
2908 ASSERT(type
!= XFS_AG_RESV_AGFL
);
2910 if (XFS_TEST_ERROR(false, mp
,
2911 XFS_ERRTAG_FREE_EXTENT
,
2912 XFS_RANDOM_FREE_EXTENT
))
2915 error
= xfs_free_extent_fix_freelist(tp
, agno
, &agbp
);
2919 XFS_WANT_CORRUPTED_GOTO(mp
, agbno
< mp
->m_sb
.sb_agblocks
, err
);
2921 /* validate the extent size is legal now we have the agf locked */
2922 XFS_WANT_CORRUPTED_GOTO(mp
,
2923 agbno
+ len
<= be32_to_cpu(XFS_BUF_TO_AGF(agbp
)->agf_length
),
2926 error
= xfs_free_ag_extent(tp
, agbp
, agno
, agbno
, len
, oinfo
, type
);
2930 xfs_extent_busy_insert(tp
, agno
, agbno
, len
, 0);
2934 xfs_trans_brelse(tp
, agbp
);