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_types.h"
24 #include "xfs_trans.h"
28 #include "xfs_dmapi.h"
29 #include "xfs_mount.h"
30 #include "xfs_bmap_btree.h"
31 #include "xfs_alloc_btree.h"
32 #include "xfs_ialloc_btree.h"
33 #include "xfs_dir2_sf.h"
34 #include "xfs_attr_sf.h"
35 #include "xfs_dinode.h"
36 #include "xfs_inode.h"
37 #include "xfs_btree.h"
38 #include "xfs_ialloc.h"
39 #include "xfs_alloc.h"
40 #include "xfs_error.h"
41 #include "xfs_trace.h"
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
50 xfs_alloc_busy_search(struct xfs_mount
*mp
, xfs_agnumber_t agno
,
51 xfs_agblock_t bno
, xfs_extlen_t len
);
54 * Prototypes for per-ag allocation routines
57 STATIC
int xfs_alloc_ag_vextent_exact(xfs_alloc_arg_t
*);
58 STATIC
int xfs_alloc_ag_vextent_near(xfs_alloc_arg_t
*);
59 STATIC
int xfs_alloc_ag_vextent_size(xfs_alloc_arg_t
*);
60 STATIC
int xfs_alloc_ag_vextent_small(xfs_alloc_arg_t
*,
61 xfs_btree_cur_t
*, xfs_agblock_t
*, xfs_extlen_t
*, int *);
68 * Lookup the record equal to [bno, len] in the btree given by cur.
70 STATIC
int /* error */
72 struct xfs_btree_cur
*cur
, /* btree cursor */
73 xfs_agblock_t bno
, /* starting block of extent */
74 xfs_extlen_t len
, /* length of extent */
75 int *stat
) /* success/failure */
77 cur
->bc_rec
.a
.ar_startblock
= bno
;
78 cur
->bc_rec
.a
.ar_blockcount
= len
;
79 return xfs_btree_lookup(cur
, XFS_LOOKUP_EQ
, stat
);
83 * Lookup the first record greater than or equal to [bno, len]
84 * in the btree given by cur.
86 STATIC
int /* error */
88 struct xfs_btree_cur
*cur
, /* btree cursor */
89 xfs_agblock_t bno
, /* starting block of extent */
90 xfs_extlen_t len
, /* length of extent */
91 int *stat
) /* success/failure */
93 cur
->bc_rec
.a
.ar_startblock
= bno
;
94 cur
->bc_rec
.a
.ar_blockcount
= len
;
95 return xfs_btree_lookup(cur
, XFS_LOOKUP_GE
, stat
);
99 * Lookup the first record less than or equal to [bno, len]
100 * in the btree given by cur.
102 STATIC
int /* error */
104 struct xfs_btree_cur
*cur
, /* btree cursor */
105 xfs_agblock_t bno
, /* starting block of extent */
106 xfs_extlen_t len
, /* length of extent */
107 int *stat
) /* success/failure */
109 cur
->bc_rec
.a
.ar_startblock
= bno
;
110 cur
->bc_rec
.a
.ar_blockcount
= len
;
111 return xfs_btree_lookup(cur
, XFS_LOOKUP_LE
, stat
);
115 * Update the record referred to by cur to the value given
117 * This either works (return 0) or gets an EFSCORRUPTED error.
119 STATIC
int /* error */
121 struct xfs_btree_cur
*cur
, /* btree cursor */
122 xfs_agblock_t bno
, /* starting block of extent */
123 xfs_extlen_t len
) /* length of extent */
125 union xfs_btree_rec rec
;
127 rec
.alloc
.ar_startblock
= cpu_to_be32(bno
);
128 rec
.alloc
.ar_blockcount
= cpu_to_be32(len
);
129 return xfs_btree_update(cur
, &rec
);
133 * Get the data from the pointed-to record.
135 STATIC
int /* error */
137 struct xfs_btree_cur
*cur
, /* btree cursor */
138 xfs_agblock_t
*bno
, /* output: starting block of extent */
139 xfs_extlen_t
*len
, /* output: length of extent */
140 int *stat
) /* output: success/failure */
142 union xfs_btree_rec
*rec
;
145 error
= xfs_btree_get_rec(cur
, &rec
, stat
);
146 if (!error
&& *stat
== 1) {
147 *bno
= be32_to_cpu(rec
->alloc
.ar_startblock
);
148 *len
= be32_to_cpu(rec
->alloc
.ar_blockcount
);
154 * Compute aligned version of the found extent.
155 * Takes alignment and min length into account.
158 xfs_alloc_compute_aligned(
159 xfs_agblock_t foundbno
, /* starting block in found extent */
160 xfs_extlen_t foundlen
, /* length in found extent */
161 xfs_extlen_t alignment
, /* alignment for allocation */
162 xfs_extlen_t minlen
, /* minimum length for allocation */
163 xfs_agblock_t
*resbno
, /* result block number */
164 xfs_extlen_t
*reslen
) /* result length */
170 if (alignment
> 1 && foundlen
>= minlen
) {
171 bno
= roundup(foundbno
, alignment
);
172 diff
= bno
- foundbno
;
173 len
= diff
>= foundlen
? 0 : foundlen
- diff
;
183 * Compute best start block and diff for "near" allocations.
184 * freelen >= wantlen already checked by caller.
186 STATIC xfs_extlen_t
/* difference value (absolute) */
187 xfs_alloc_compute_diff(
188 xfs_agblock_t wantbno
, /* target starting block */
189 xfs_extlen_t wantlen
, /* target length */
190 xfs_extlen_t alignment
, /* target alignment */
191 xfs_agblock_t freebno
, /* freespace's starting block */
192 xfs_extlen_t freelen
, /* freespace's length */
193 xfs_agblock_t
*newbnop
) /* result: best start block from free */
195 xfs_agblock_t freeend
; /* end of freespace extent */
196 xfs_agblock_t newbno1
; /* return block number */
197 xfs_agblock_t newbno2
; /* other new block number */
198 xfs_extlen_t newlen1
=0; /* length with newbno1 */
199 xfs_extlen_t newlen2
=0; /* length with newbno2 */
200 xfs_agblock_t wantend
; /* end of target extent */
202 ASSERT(freelen
>= wantlen
);
203 freeend
= freebno
+ freelen
;
204 wantend
= wantbno
+ wantlen
;
205 if (freebno
>= wantbno
) {
206 if ((newbno1
= roundup(freebno
, alignment
)) >= freeend
)
207 newbno1
= NULLAGBLOCK
;
208 } else if (freeend
>= wantend
&& alignment
> 1) {
209 newbno1
= roundup(wantbno
, alignment
);
210 newbno2
= newbno1
- alignment
;
211 if (newbno1
>= freeend
)
212 newbno1
= NULLAGBLOCK
;
214 newlen1
= XFS_EXTLEN_MIN(wantlen
, freeend
- newbno1
);
215 if (newbno2
< freebno
)
216 newbno2
= NULLAGBLOCK
;
218 newlen2
= XFS_EXTLEN_MIN(wantlen
, freeend
- newbno2
);
219 if (newbno1
!= NULLAGBLOCK
&& newbno2
!= NULLAGBLOCK
) {
220 if (newlen1
< newlen2
||
221 (newlen1
== newlen2
&&
222 XFS_ABSDIFF(newbno1
, wantbno
) >
223 XFS_ABSDIFF(newbno2
, wantbno
)))
225 } else if (newbno2
!= NULLAGBLOCK
)
227 } else if (freeend
>= wantend
) {
229 } else if (alignment
> 1) {
230 newbno1
= roundup(freeend
- wantlen
, alignment
);
231 if (newbno1
> freeend
- wantlen
&&
232 newbno1
- alignment
>= freebno
)
233 newbno1
-= alignment
;
234 else if (newbno1
>= freeend
)
235 newbno1
= NULLAGBLOCK
;
237 newbno1
= freeend
- wantlen
;
239 return newbno1
== NULLAGBLOCK
? 0 : XFS_ABSDIFF(newbno1
, wantbno
);
243 * Fix up the length, based on mod and prod.
244 * len should be k * prod + mod for some k.
245 * If len is too small it is returned unchanged.
246 * If len hits maxlen it is left alone.
250 xfs_alloc_arg_t
*args
) /* allocation argument structure */
255 ASSERT(args
->mod
< args
->prod
);
257 ASSERT(rlen
>= args
->minlen
);
258 ASSERT(rlen
<= args
->maxlen
);
259 if (args
->prod
<= 1 || rlen
< args
->mod
|| rlen
== args
->maxlen
||
260 (args
->mod
== 0 && rlen
< args
->prod
))
262 k
= rlen
% args
->prod
;
266 if ((int)(rlen
= rlen
- k
- args
->mod
) < (int)args
->minlen
)
269 if ((int)(rlen
= rlen
- args
->prod
- (args
->mod
- k
)) <
273 ASSERT(rlen
>= args
->minlen
);
274 ASSERT(rlen
<= args
->maxlen
);
279 * Fix up length if there is too little space left in the a.g.
280 * Return 1 if ok, 0 if too little, should give up.
283 xfs_alloc_fix_minleft(
284 xfs_alloc_arg_t
*args
) /* allocation argument structure */
286 xfs_agf_t
*agf
; /* a.g. freelist header */
287 int diff
; /* free space difference */
289 if (args
->minleft
== 0)
291 agf
= XFS_BUF_TO_AGF(args
->agbp
);
292 diff
= be32_to_cpu(agf
->agf_freeblks
)
293 + be32_to_cpu(agf
->agf_flcount
)
294 - args
->len
- args
->minleft
;
297 args
->len
+= diff
; /* shrink the allocated space */
298 if (args
->len
>= args
->minlen
)
300 args
->agbno
= NULLAGBLOCK
;
305 * Update the two btrees, logically removing from freespace the extent
306 * starting at rbno, rlen blocks. The extent is contained within the
307 * actual (current) free extent fbno for flen blocks.
308 * Flags are passed in indicating whether the cursors are set to the
311 STATIC
int /* error code */
312 xfs_alloc_fixup_trees(
313 xfs_btree_cur_t
*cnt_cur
, /* cursor for by-size btree */
314 xfs_btree_cur_t
*bno_cur
, /* cursor for by-block btree */
315 xfs_agblock_t fbno
, /* starting block of free extent */
316 xfs_extlen_t flen
, /* length of free extent */
317 xfs_agblock_t rbno
, /* starting block of returned extent */
318 xfs_extlen_t rlen
, /* length of returned extent */
319 int flags
) /* flags, XFSA_FIXUP_... */
321 int error
; /* error code */
322 int i
; /* operation results */
323 xfs_agblock_t nfbno1
; /* first new free startblock */
324 xfs_agblock_t nfbno2
; /* second new free startblock */
325 xfs_extlen_t nflen1
=0; /* first new free length */
326 xfs_extlen_t nflen2
=0; /* second new free length */
329 * Look up the record in the by-size tree if necessary.
331 if (flags
& XFSA_FIXUP_CNT_OK
) {
333 if ((error
= xfs_alloc_get_rec(cnt_cur
, &nfbno1
, &nflen1
, &i
)))
335 XFS_WANT_CORRUPTED_RETURN(
336 i
== 1 && nfbno1
== fbno
&& nflen1
== flen
);
339 if ((error
= xfs_alloc_lookup_eq(cnt_cur
, fbno
, flen
, &i
)))
341 XFS_WANT_CORRUPTED_RETURN(i
== 1);
344 * Look up the record in the by-block tree if necessary.
346 if (flags
& XFSA_FIXUP_BNO_OK
) {
348 if ((error
= xfs_alloc_get_rec(bno_cur
, &nfbno1
, &nflen1
, &i
)))
350 XFS_WANT_CORRUPTED_RETURN(
351 i
== 1 && nfbno1
== fbno
&& nflen1
== flen
);
354 if ((error
= xfs_alloc_lookup_eq(bno_cur
, fbno
, flen
, &i
)))
356 XFS_WANT_CORRUPTED_RETURN(i
== 1);
360 if (bno_cur
->bc_nlevels
== 1 && cnt_cur
->bc_nlevels
== 1) {
361 struct xfs_btree_block
*bnoblock
;
362 struct xfs_btree_block
*cntblock
;
364 bnoblock
= XFS_BUF_TO_BLOCK(bno_cur
->bc_bufs
[0]);
365 cntblock
= XFS_BUF_TO_BLOCK(cnt_cur
->bc_bufs
[0]);
367 XFS_WANT_CORRUPTED_RETURN(
368 bnoblock
->bb_numrecs
== cntblock
->bb_numrecs
);
373 * Deal with all four cases: the allocated record is contained
374 * within the freespace record, so we can have new freespace
375 * at either (or both) end, or no freespace remaining.
377 if (rbno
== fbno
&& rlen
== flen
)
378 nfbno1
= nfbno2
= NULLAGBLOCK
;
379 else if (rbno
== fbno
) {
380 nfbno1
= rbno
+ rlen
;
381 nflen1
= flen
- rlen
;
382 nfbno2
= NULLAGBLOCK
;
383 } else if (rbno
+ rlen
== fbno
+ flen
) {
385 nflen1
= flen
- rlen
;
386 nfbno2
= NULLAGBLOCK
;
389 nflen1
= rbno
- fbno
;
390 nfbno2
= rbno
+ rlen
;
391 nflen2
= (fbno
+ flen
) - nfbno2
;
394 * Delete the entry from the by-size btree.
396 if ((error
= xfs_btree_delete(cnt_cur
, &i
)))
398 XFS_WANT_CORRUPTED_RETURN(i
== 1);
400 * Add new by-size btree entry(s).
402 if (nfbno1
!= NULLAGBLOCK
) {
403 if ((error
= xfs_alloc_lookup_eq(cnt_cur
, nfbno1
, nflen1
, &i
)))
405 XFS_WANT_CORRUPTED_RETURN(i
== 0);
406 if ((error
= xfs_btree_insert(cnt_cur
, &i
)))
408 XFS_WANT_CORRUPTED_RETURN(i
== 1);
410 if (nfbno2
!= NULLAGBLOCK
) {
411 if ((error
= xfs_alloc_lookup_eq(cnt_cur
, nfbno2
, nflen2
, &i
)))
413 XFS_WANT_CORRUPTED_RETURN(i
== 0);
414 if ((error
= xfs_btree_insert(cnt_cur
, &i
)))
416 XFS_WANT_CORRUPTED_RETURN(i
== 1);
419 * Fix up the by-block btree entry(s).
421 if (nfbno1
== NULLAGBLOCK
) {
423 * No remaining freespace, just delete the by-block tree entry.
425 if ((error
= xfs_btree_delete(bno_cur
, &i
)))
427 XFS_WANT_CORRUPTED_RETURN(i
== 1);
430 * Update the by-block entry to start later|be shorter.
432 if ((error
= xfs_alloc_update(bno_cur
, nfbno1
, nflen1
)))
435 if (nfbno2
!= NULLAGBLOCK
) {
437 * 2 resulting free entries, need to add one.
439 if ((error
= xfs_alloc_lookup_eq(bno_cur
, nfbno2
, nflen2
, &i
)))
441 XFS_WANT_CORRUPTED_RETURN(i
== 0);
442 if ((error
= xfs_btree_insert(bno_cur
, &i
)))
444 XFS_WANT_CORRUPTED_RETURN(i
== 1);
450 * Read in the allocation group free block array.
452 STATIC
int /* error */
454 xfs_mount_t
*mp
, /* mount point structure */
455 xfs_trans_t
*tp
, /* transaction pointer */
456 xfs_agnumber_t agno
, /* allocation group number */
457 xfs_buf_t
**bpp
) /* buffer for the ag free block array */
459 xfs_buf_t
*bp
; /* return value */
462 ASSERT(agno
!= NULLAGNUMBER
);
463 error
= xfs_trans_read_buf(
464 mp
, tp
, mp
->m_ddev_targp
,
465 XFS_AG_DADDR(mp
, agno
, XFS_AGFL_DADDR(mp
)),
466 XFS_FSS_TO_BB(mp
, 1), 0, &bp
);
470 ASSERT(!XFS_BUF_GETERROR(bp
));
471 XFS_BUF_SET_VTYPE_REF(bp
, B_FS_AGFL
, XFS_AGFL_REF
);
477 * Allocation group level functions.
481 * Allocate a variable extent in the allocation group agno.
482 * Type and bno are used to determine where in the allocation group the
484 * Extent's length (returned in *len) will be between minlen and maxlen,
485 * and of the form k * prod + mod unless there's nothing that large.
486 * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
488 STATIC
int /* error */
489 xfs_alloc_ag_vextent(
490 xfs_alloc_arg_t
*args
) /* argument structure for allocation */
494 ASSERT(args
->minlen
> 0);
495 ASSERT(args
->maxlen
> 0);
496 ASSERT(args
->minlen
<= args
->maxlen
);
497 ASSERT(args
->mod
< args
->prod
);
498 ASSERT(args
->alignment
> 0);
500 * Branch to correct routine based on the type.
503 switch (args
->type
) {
504 case XFS_ALLOCTYPE_THIS_AG
:
505 error
= xfs_alloc_ag_vextent_size(args
);
507 case XFS_ALLOCTYPE_NEAR_BNO
:
508 error
= xfs_alloc_ag_vextent_near(args
);
510 case XFS_ALLOCTYPE_THIS_BNO
:
511 error
= xfs_alloc_ag_vextent_exact(args
);
520 * If the allocation worked, need to change the agf structure
521 * (and log it), and the superblock.
523 if (args
->agbno
!= NULLAGBLOCK
) {
524 xfs_agf_t
*agf
; /* allocation group freelist header */
525 long slen
= (long)args
->len
;
527 ASSERT(args
->len
>= args
->minlen
&& args
->len
<= args
->maxlen
);
528 ASSERT(!(args
->wasfromfl
) || !args
->isfl
);
529 ASSERT(args
->agbno
% args
->alignment
== 0);
530 if (!(args
->wasfromfl
)) {
532 agf
= XFS_BUF_TO_AGF(args
->agbp
);
533 be32_add_cpu(&agf
->agf_freeblks
, -(args
->len
));
534 xfs_trans_agblocks_delta(args
->tp
,
535 -((long)(args
->len
)));
536 args
->pag
->pagf_freeblks
-= args
->len
;
537 ASSERT(be32_to_cpu(agf
->agf_freeblks
) <=
538 be32_to_cpu(agf
->agf_length
));
539 xfs_alloc_log_agf(args
->tp
, args
->agbp
,
542 * Search the busylist for these blocks and mark the
543 * transaction as synchronous if blocks are found. This
544 * avoids the need to block due to a synchronous log
545 * force to ensure correct ordering as the synchronous
546 * transaction will guarantee that for us.
548 if (xfs_alloc_busy_search(args
->mp
, args
->agno
,
549 args
->agbno
, args
->len
))
550 xfs_trans_set_sync(args
->tp
);
553 xfs_trans_mod_sb(args
->tp
,
554 args
->wasdel
? XFS_TRANS_SB_RES_FDBLOCKS
:
555 XFS_TRANS_SB_FDBLOCKS
, -slen
);
556 XFS_STATS_INC(xs_allocx
);
557 XFS_STATS_ADD(xs_allocb
, args
->len
);
563 * Allocate a variable extent at exactly agno/bno.
564 * Extent's length (returned in *len) will be between minlen and maxlen,
565 * and of the form k * prod + mod unless there's nothing that large.
566 * Return the starting a.g. block (bno), or NULLAGBLOCK if we can't do it.
568 STATIC
int /* error */
569 xfs_alloc_ag_vextent_exact(
570 xfs_alloc_arg_t
*args
) /* allocation argument structure */
572 xfs_btree_cur_t
*bno_cur
;/* by block-number btree cursor */
573 xfs_btree_cur_t
*cnt_cur
;/* by count btree cursor */
574 xfs_agblock_t end
; /* end of allocated extent */
576 xfs_agblock_t fbno
; /* start block of found extent */
577 xfs_agblock_t fend
; /* end block of found extent */
578 xfs_extlen_t flen
; /* length of found extent */
579 int i
; /* success/failure of operation */
580 xfs_agblock_t maxend
; /* end of maximal extent */
581 xfs_agblock_t minend
; /* end of minimal extent */
582 xfs_extlen_t rlen
; /* length of returned extent */
584 ASSERT(args
->alignment
== 1);
586 * Allocate/initialize a cursor for the by-number freespace btree.
588 bno_cur
= xfs_allocbt_init_cursor(args
->mp
, args
->tp
, args
->agbp
,
589 args
->agno
, XFS_BTNUM_BNO
);
591 * Lookup bno and minlen in the btree (minlen is irrelevant, really).
592 * Look for the closest free block <= bno, it must contain bno
593 * if any free block does.
595 if ((error
= xfs_alloc_lookup_le(bno_cur
, args
->agbno
, args
->minlen
, &i
)))
599 * Didn't find it, return null.
601 xfs_btree_del_cursor(bno_cur
, XFS_BTREE_NOERROR
);
602 args
->agbno
= NULLAGBLOCK
;
606 * Grab the freespace record.
608 if ((error
= xfs_alloc_get_rec(bno_cur
, &fbno
, &flen
, &i
)))
610 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
611 ASSERT(fbno
<= args
->agbno
);
612 minend
= args
->agbno
+ args
->minlen
;
613 maxend
= args
->agbno
+ args
->maxlen
;
616 * Give up if the freespace isn't long enough for the minimum request.
619 xfs_btree_del_cursor(bno_cur
, XFS_BTREE_NOERROR
);
620 args
->agbno
= NULLAGBLOCK
;
624 * End of extent will be smaller of the freespace end and the
625 * maximal requested end.
627 end
= XFS_AGBLOCK_MIN(fend
, maxend
);
629 * Fix the length according to mod and prod if given.
631 args
->len
= end
- args
->agbno
;
632 xfs_alloc_fix_len(args
);
633 if (!xfs_alloc_fix_minleft(args
)) {
634 xfs_btree_del_cursor(bno_cur
, XFS_BTREE_NOERROR
);
638 ASSERT(args
->agbno
+ rlen
<= fend
);
639 end
= args
->agbno
+ rlen
;
641 * We are allocating agbno for rlen [agbno .. end]
642 * Allocate/initialize a cursor for the by-size btree.
644 cnt_cur
= xfs_allocbt_init_cursor(args
->mp
, args
->tp
, args
->agbp
,
645 args
->agno
, XFS_BTNUM_CNT
);
646 ASSERT(args
->agbno
+ args
->len
<=
647 be32_to_cpu(XFS_BUF_TO_AGF(args
->agbp
)->agf_length
));
648 if ((error
= xfs_alloc_fixup_trees(cnt_cur
, bno_cur
, fbno
, flen
,
649 args
->agbno
, args
->len
, XFSA_FIXUP_BNO_OK
))) {
650 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_ERROR
);
653 xfs_btree_del_cursor(bno_cur
, XFS_BTREE_NOERROR
);
654 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_NOERROR
);
656 trace_xfs_alloc_exact_done(args
);
661 xfs_btree_del_cursor(bno_cur
, XFS_BTREE_ERROR
);
662 trace_xfs_alloc_exact_error(args
);
667 * Allocate a variable extent near bno in the allocation group agno.
668 * Extent's length (returned in len) will be between minlen and maxlen,
669 * and of the form k * prod + mod unless there's nothing that large.
670 * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
672 STATIC
int /* error */
673 xfs_alloc_ag_vextent_near(
674 xfs_alloc_arg_t
*args
) /* allocation argument structure */
676 xfs_btree_cur_t
*bno_cur_gt
; /* cursor for bno btree, right side */
677 xfs_btree_cur_t
*bno_cur_lt
; /* cursor for bno btree, left side */
678 xfs_btree_cur_t
*cnt_cur
; /* cursor for count btree */
679 xfs_agblock_t gtbno
; /* start bno of right side entry */
680 xfs_agblock_t gtbnoa
; /* aligned ... */
681 xfs_extlen_t gtdiff
; /* difference to right side entry */
682 xfs_extlen_t gtlen
; /* length of right side entry */
683 xfs_extlen_t gtlena
; /* aligned ... */
684 xfs_agblock_t gtnew
; /* useful start bno of right side */
685 int error
; /* error code */
686 int i
; /* result code, temporary */
687 int j
; /* result code, temporary */
688 xfs_agblock_t ltbno
; /* start bno of left side entry */
689 xfs_agblock_t ltbnoa
; /* aligned ... */
690 xfs_extlen_t ltdiff
; /* difference to left side entry */
692 xfs_agblock_t ltend
; /* end bno of left side entry */
693 xfs_extlen_t ltlen
; /* length of left side entry */
694 xfs_extlen_t ltlena
; /* aligned ... */
695 xfs_agblock_t ltnew
; /* useful start bno of left side */
696 xfs_extlen_t rlen
; /* length of returned extent */
697 #if defined(DEBUG) && defined(__KERNEL__)
699 * Randomly don't execute the first algorithm.
701 int dofirst
; /* set to do first algorithm */
703 dofirst
= random32() & 1;
706 * Get a cursor for the by-size btree.
708 cnt_cur
= xfs_allocbt_init_cursor(args
->mp
, args
->tp
, args
->agbp
,
709 args
->agno
, XFS_BTNUM_CNT
);
711 bno_cur_lt
= bno_cur_gt
= NULL
;
713 * See if there are any free extents as big as maxlen.
715 if ((error
= xfs_alloc_lookup_ge(cnt_cur
, 0, args
->maxlen
, &i
)))
718 * If none, then pick up the last entry in the tree unless the
722 if ((error
= xfs_alloc_ag_vextent_small(args
, cnt_cur
, <bno
,
725 if (i
== 0 || ltlen
== 0) {
726 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_NOERROR
);
734 * If the requested extent is large wrt the freespaces available
735 * in this a.g., then the cursor will be pointing to a btree entry
736 * near the right edge of the tree. If it's in the last btree leaf
737 * block, then we just examine all the entries in that block
738 * that are big enough, and pick the best one.
739 * This is written as a while loop so we can break out of it,
740 * but we never loop back to the top.
742 while (xfs_btree_islastblock(cnt_cur
, 0)) {
746 xfs_agblock_t bnew
=0;
748 #if defined(DEBUG) && defined(__KERNEL__)
753 * Start from the entry that lookup found, sequence through
754 * all larger free blocks. If we're actually pointing at a
755 * record smaller than maxlen, go to the start of this block,
756 * and skip all those smaller than minlen.
758 if (ltlen
|| args
->alignment
> 1) {
759 cnt_cur
->bc_ptrs
[0] = 1;
761 if ((error
= xfs_alloc_get_rec(cnt_cur
, <bno
,
764 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
765 if (ltlen
>= args
->minlen
)
767 if ((error
= xfs_btree_increment(cnt_cur
, 0, &i
)))
770 ASSERT(ltlen
>= args
->minlen
);
774 i
= cnt_cur
->bc_ptrs
[0];
775 for (j
= 1, blen
= 0, bdiff
= 0;
776 !error
&& j
&& (blen
< args
->maxlen
|| bdiff
> 0);
777 error
= xfs_btree_increment(cnt_cur
, 0, &j
)) {
779 * For each entry, decide if it's better than
780 * the previous best entry.
782 if ((error
= xfs_alloc_get_rec(cnt_cur
, <bno
, <len
, &i
)))
784 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
785 xfs_alloc_compute_aligned(ltbno
, ltlen
, args
->alignment
,
786 args
->minlen
, <bnoa
, <lena
);
787 if (ltlena
< args
->minlen
)
789 args
->len
= XFS_EXTLEN_MIN(ltlena
, args
->maxlen
);
790 xfs_alloc_fix_len(args
);
791 ASSERT(args
->len
>= args
->minlen
);
792 if (args
->len
< blen
)
794 ltdiff
= xfs_alloc_compute_diff(args
->agbno
, args
->len
,
795 args
->alignment
, ltbno
, ltlen
, <new
);
796 if (ltnew
!= NULLAGBLOCK
&&
797 (args
->len
> blen
|| ltdiff
< bdiff
)) {
801 besti
= cnt_cur
->bc_ptrs
[0];
805 * It didn't work. We COULD be in a case where
806 * there's a good record somewhere, so try again.
811 * Point at the best entry, and retrieve it again.
813 cnt_cur
->bc_ptrs
[0] = besti
;
814 if ((error
= xfs_alloc_get_rec(cnt_cur
, <bno
, <len
, &i
)))
816 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
817 ltend
= ltbno
+ ltlen
;
818 ASSERT(ltend
<= be32_to_cpu(XFS_BUF_TO_AGF(args
->agbp
)->agf_length
));
820 if (!xfs_alloc_fix_minleft(args
)) {
821 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_NOERROR
);
822 trace_xfs_alloc_near_nominleft(args
);
827 * We are allocating starting at bnew for blen blocks.
830 ASSERT(bnew
>= ltbno
);
831 ASSERT(bnew
+ blen
<= ltend
);
833 * Set up a cursor for the by-bno tree.
835 bno_cur_lt
= xfs_allocbt_init_cursor(args
->mp
, args
->tp
,
836 args
->agbp
, args
->agno
, XFS_BTNUM_BNO
);
838 * Fix up the btree entries.
840 if ((error
= xfs_alloc_fixup_trees(cnt_cur
, bno_cur_lt
, ltbno
,
841 ltlen
, bnew
, blen
, XFSA_FIXUP_CNT_OK
)))
843 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_NOERROR
);
844 xfs_btree_del_cursor(bno_cur_lt
, XFS_BTREE_NOERROR
);
846 trace_xfs_alloc_near_first(args
);
851 * Search in the by-bno tree to the left and to the right
852 * simultaneously, until in each case we find a space big enough,
853 * or run into the edge of the tree. When we run into the edge,
854 * we deallocate that cursor.
855 * If both searches succeed, we compare the two spaces and pick
857 * With alignment, it's possible for both to fail; the upper
858 * level algorithm that picks allocation groups for allocations
859 * is not supposed to do this.
862 * Allocate and initialize the cursor for the leftward search.
864 bno_cur_lt
= xfs_allocbt_init_cursor(args
->mp
, args
->tp
, args
->agbp
,
865 args
->agno
, XFS_BTNUM_BNO
);
867 * Lookup <= bno to find the leftward search's starting point.
869 if ((error
= xfs_alloc_lookup_le(bno_cur_lt
, args
->agbno
, args
->maxlen
, &i
)))
873 * Didn't find anything; use this cursor for the rightward
876 bno_cur_gt
= bno_cur_lt
;
880 * Found something. Duplicate the cursor for the rightward search.
882 else if ((error
= xfs_btree_dup_cursor(bno_cur_lt
, &bno_cur_gt
)))
885 * Increment the cursor, so we will point at the entry just right
886 * of the leftward entry if any, or to the leftmost entry.
888 if ((error
= xfs_btree_increment(bno_cur_gt
, 0, &i
)))
892 * It failed, there are no rightward entries.
894 xfs_btree_del_cursor(bno_cur_gt
, XFS_BTREE_NOERROR
);
898 * Loop going left with the leftward cursor, right with the
899 * rightward cursor, until either both directions give up or
900 * we find an entry at least as big as minlen.
904 if ((error
= xfs_alloc_get_rec(bno_cur_lt
, <bno
, <len
, &i
)))
906 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
907 xfs_alloc_compute_aligned(ltbno
, ltlen
, args
->alignment
,
908 args
->minlen
, <bnoa
, <lena
);
909 if (ltlena
>= args
->minlen
)
911 if ((error
= xfs_btree_decrement(bno_cur_lt
, 0, &i
)))
914 xfs_btree_del_cursor(bno_cur_lt
,
920 if ((error
= xfs_alloc_get_rec(bno_cur_gt
, >bno
, >len
, &i
)))
922 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
923 xfs_alloc_compute_aligned(gtbno
, gtlen
, args
->alignment
,
924 args
->minlen
, >bnoa
, >lena
);
925 if (gtlena
>= args
->minlen
)
927 if ((error
= xfs_btree_increment(bno_cur_gt
, 0, &i
)))
930 xfs_btree_del_cursor(bno_cur_gt
,
935 } while (bno_cur_lt
|| bno_cur_gt
);
937 * Got both cursors still active, need to find better entry.
939 if (bno_cur_lt
&& bno_cur_gt
) {
941 * Left side is long enough, look for a right side entry.
943 if (ltlena
>= args
->minlen
) {
947 args
->len
= XFS_EXTLEN_MIN(ltlena
, args
->maxlen
);
948 xfs_alloc_fix_len(args
);
950 ltdiff
= xfs_alloc_compute_diff(args
->agbno
, rlen
,
951 args
->alignment
, ltbno
, ltlen
, <new
);
957 * Look until we find a better one, run out of
958 * space, or run off the end.
960 while (bno_cur_lt
&& bno_cur_gt
) {
961 if ((error
= xfs_alloc_get_rec(
965 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
966 xfs_alloc_compute_aligned(gtbno
, gtlen
,
967 args
->alignment
, args
->minlen
,
970 * The left one is clearly better.
972 if (gtbnoa
>= args
->agbno
+ ltdiff
) {
973 xfs_btree_del_cursor(
980 * If we reach a big enough entry,
981 * compare the two and pick the best.
983 if (gtlena
>= args
->minlen
) {
985 XFS_EXTLEN_MIN(gtlena
,
987 xfs_alloc_fix_len(args
);
989 gtdiff
= xfs_alloc_compute_diff(
992 gtbno
, gtlen
, >new
);
994 * Right side is better.
996 if (gtdiff
< ltdiff
) {
997 xfs_btree_del_cursor(
1003 * Left side is better.
1006 xfs_btree_del_cursor(
1014 * Fell off the right end.
1016 if ((error
= xfs_btree_increment(
1017 bno_cur_gt
, 0, &i
)))
1020 xfs_btree_del_cursor(
1029 * The left side is perfect, trash the right side.
1032 xfs_btree_del_cursor(bno_cur_gt
,
1038 * It's the right side that was found first, look left.
1042 * Fix up the length.
1044 args
->len
= XFS_EXTLEN_MIN(gtlena
, args
->maxlen
);
1045 xfs_alloc_fix_len(args
);
1047 gtdiff
= xfs_alloc_compute_diff(args
->agbno
, rlen
,
1048 args
->alignment
, gtbno
, gtlen
, >new
);
1050 * Right side entry isn't perfect.
1054 * Look until we find a better one, run out of
1055 * space, or run off the end.
1057 while (bno_cur_lt
&& bno_cur_gt
) {
1058 if ((error
= xfs_alloc_get_rec(
1062 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
1063 xfs_alloc_compute_aligned(ltbno
, ltlen
,
1064 args
->alignment
, args
->minlen
,
1067 * The right one is clearly better.
1069 if (ltbnoa
<= args
->agbno
- gtdiff
) {
1070 xfs_btree_del_cursor(
1077 * If we reach a big enough entry,
1078 * compare the two and pick the best.
1080 if (ltlena
>= args
->minlen
) {
1081 args
->len
= XFS_EXTLEN_MIN(
1082 ltlena
, args
->maxlen
);
1083 xfs_alloc_fix_len(args
);
1085 ltdiff
= xfs_alloc_compute_diff(
1088 ltbno
, ltlen
, <new
);
1090 * Left side is better.
1092 if (ltdiff
< gtdiff
) {
1093 xfs_btree_del_cursor(
1099 * Right side is better.
1102 xfs_btree_del_cursor(
1110 * Fell off the left end.
1112 if ((error
= xfs_btree_decrement(
1113 bno_cur_lt
, 0, &i
)))
1116 xfs_btree_del_cursor(bno_cur_lt
,
1124 * The right side is perfect, trash the left side.
1127 xfs_btree_del_cursor(bno_cur_lt
,
1134 * If we couldn't get anything, give up.
1136 if (bno_cur_lt
== NULL
&& bno_cur_gt
== NULL
) {
1137 trace_xfs_alloc_size_neither(args
);
1138 args
->agbno
= NULLAGBLOCK
;
1142 * At this point we have selected a freespace entry, either to the
1143 * left or to the right. If it's on the right, copy all the
1144 * useful variables to the "left" set so we only have one
1145 * copy of this code.
1148 bno_cur_lt
= bno_cur_gt
;
1158 * Fix up the length and compute the useful address.
1160 ltend
= ltbno
+ ltlen
;
1161 args
->len
= XFS_EXTLEN_MIN(ltlena
, args
->maxlen
);
1162 xfs_alloc_fix_len(args
);
1163 if (!xfs_alloc_fix_minleft(args
)) {
1164 trace_xfs_alloc_near_nominleft(args
);
1165 xfs_btree_del_cursor(bno_cur_lt
, XFS_BTREE_NOERROR
);
1166 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_NOERROR
);
1170 (void)xfs_alloc_compute_diff(args
->agbno
, rlen
, args
->alignment
, ltbno
,
1172 ASSERT(ltnew
>= ltbno
);
1173 ASSERT(ltnew
+ rlen
<= ltend
);
1174 ASSERT(ltnew
+ rlen
<= be32_to_cpu(XFS_BUF_TO_AGF(args
->agbp
)->agf_length
));
1175 args
->agbno
= ltnew
;
1176 if ((error
= xfs_alloc_fixup_trees(cnt_cur
, bno_cur_lt
, ltbno
, ltlen
,
1177 ltnew
, rlen
, XFSA_FIXUP_BNO_OK
)))
1181 trace_xfs_alloc_near_greater(args
);
1183 trace_xfs_alloc_near_lesser(args
);
1185 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_NOERROR
);
1186 xfs_btree_del_cursor(bno_cur_lt
, XFS_BTREE_NOERROR
);
1190 trace_xfs_alloc_near_error(args
);
1191 if (cnt_cur
!= NULL
)
1192 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_ERROR
);
1193 if (bno_cur_lt
!= NULL
)
1194 xfs_btree_del_cursor(bno_cur_lt
, XFS_BTREE_ERROR
);
1195 if (bno_cur_gt
!= NULL
)
1196 xfs_btree_del_cursor(bno_cur_gt
, XFS_BTREE_ERROR
);
1201 * Allocate a variable extent anywhere in the allocation group agno.
1202 * Extent's length (returned in len) will be between minlen and maxlen,
1203 * and of the form k * prod + mod unless there's nothing that large.
1204 * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
1206 STATIC
int /* error */
1207 xfs_alloc_ag_vextent_size(
1208 xfs_alloc_arg_t
*args
) /* allocation argument structure */
1210 xfs_btree_cur_t
*bno_cur
; /* cursor for bno btree */
1211 xfs_btree_cur_t
*cnt_cur
; /* cursor for cnt btree */
1212 int error
; /* error result */
1213 xfs_agblock_t fbno
; /* start of found freespace */
1214 xfs_extlen_t flen
; /* length of found freespace */
1215 int i
; /* temp status variable */
1216 xfs_agblock_t rbno
; /* returned block number */
1217 xfs_extlen_t rlen
; /* length of returned extent */
1220 * Allocate and initialize a cursor for the by-size btree.
1222 cnt_cur
= xfs_allocbt_init_cursor(args
->mp
, args
->tp
, args
->agbp
,
1223 args
->agno
, XFS_BTNUM_CNT
);
1226 * Look for an entry >= maxlen+alignment-1 blocks.
1228 if ((error
= xfs_alloc_lookup_ge(cnt_cur
, 0,
1229 args
->maxlen
+ args
->alignment
- 1, &i
)))
1232 * If none, then pick up the last entry in the tree unless the
1236 if ((error
= xfs_alloc_ag_vextent_small(args
, cnt_cur
, &fbno
,
1239 if (i
== 0 || flen
== 0) {
1240 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_NOERROR
);
1241 trace_xfs_alloc_size_noentry(args
);
1247 * There's a freespace as big as maxlen+alignment-1, get it.
1250 if ((error
= xfs_alloc_get_rec(cnt_cur
, &fbno
, &flen
, &i
)))
1252 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
1255 * In the first case above, we got the last entry in the
1256 * by-size btree. Now we check to see if the space hits maxlen
1257 * once aligned; if not, we search left for something better.
1258 * This can't happen in the second case above.
1260 xfs_alloc_compute_aligned(fbno
, flen
, args
->alignment
, args
->minlen
,
1262 rlen
= XFS_EXTLEN_MIN(args
->maxlen
, rlen
);
1263 XFS_WANT_CORRUPTED_GOTO(rlen
== 0 ||
1264 (rlen
<= flen
&& rbno
+ rlen
<= fbno
+ flen
), error0
);
1265 if (rlen
< args
->maxlen
) {
1266 xfs_agblock_t bestfbno
;
1267 xfs_extlen_t bestflen
;
1268 xfs_agblock_t bestrbno
;
1269 xfs_extlen_t bestrlen
;
1276 if ((error
= xfs_btree_decrement(cnt_cur
, 0, &i
)))
1280 if ((error
= xfs_alloc_get_rec(cnt_cur
, &fbno
, &flen
,
1283 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
1284 if (flen
< bestrlen
)
1286 xfs_alloc_compute_aligned(fbno
, flen
, args
->alignment
,
1287 args
->minlen
, &rbno
, &rlen
);
1288 rlen
= XFS_EXTLEN_MIN(args
->maxlen
, rlen
);
1289 XFS_WANT_CORRUPTED_GOTO(rlen
== 0 ||
1290 (rlen
<= flen
&& rbno
+ rlen
<= fbno
+ flen
),
1292 if (rlen
> bestrlen
) {
1297 if (rlen
== args
->maxlen
)
1301 if ((error
= xfs_alloc_lookup_eq(cnt_cur
, bestfbno
, bestflen
,
1304 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
1310 args
->wasfromfl
= 0;
1312 * Fix up the length.
1315 xfs_alloc_fix_len(args
);
1316 if (rlen
< args
->minlen
|| !xfs_alloc_fix_minleft(args
)) {
1317 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_NOERROR
);
1318 trace_xfs_alloc_size_nominleft(args
);
1319 args
->agbno
= NULLAGBLOCK
;
1323 XFS_WANT_CORRUPTED_GOTO(rlen
<= flen
, error0
);
1325 * Allocate and initialize a cursor for the by-block tree.
1327 bno_cur
= xfs_allocbt_init_cursor(args
->mp
, args
->tp
, args
->agbp
,
1328 args
->agno
, XFS_BTNUM_BNO
);
1329 if ((error
= xfs_alloc_fixup_trees(cnt_cur
, bno_cur
, fbno
, flen
,
1330 rbno
, rlen
, XFSA_FIXUP_CNT_OK
)))
1332 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_NOERROR
);
1333 xfs_btree_del_cursor(bno_cur
, XFS_BTREE_NOERROR
);
1334 cnt_cur
= bno_cur
= NULL
;
1337 XFS_WANT_CORRUPTED_GOTO(
1338 args
->agbno
+ args
->len
<=
1339 be32_to_cpu(XFS_BUF_TO_AGF(args
->agbp
)->agf_length
),
1341 trace_xfs_alloc_size_done(args
);
1345 trace_xfs_alloc_size_error(args
);
1347 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_ERROR
);
1349 xfs_btree_del_cursor(bno_cur
, XFS_BTREE_ERROR
);
1354 * Deal with the case where only small freespaces remain.
1355 * Either return the contents of the last freespace record,
1356 * or allocate space from the freelist if there is nothing in the tree.
1358 STATIC
int /* error */
1359 xfs_alloc_ag_vextent_small(
1360 xfs_alloc_arg_t
*args
, /* allocation argument structure */
1361 xfs_btree_cur_t
*ccur
, /* by-size cursor */
1362 xfs_agblock_t
*fbnop
, /* result block number */
1363 xfs_extlen_t
*flenp
, /* result length */
1364 int *stat
) /* status: 0-freelist, 1-normal/none */
1371 if ((error
= xfs_btree_decrement(ccur
, 0, &i
)))
1374 if ((error
= xfs_alloc_get_rec(ccur
, &fbno
, &flen
, &i
)))
1376 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
1379 * Nothing in the btree, try the freelist. Make sure
1380 * to respect minleft even when pulling from the
1383 else if (args
->minlen
== 1 && args
->alignment
== 1 && !args
->isfl
&&
1384 (be32_to_cpu(XFS_BUF_TO_AGF(args
->agbp
)->agf_flcount
)
1386 error
= xfs_alloc_get_freelist(args
->tp
, args
->agbp
, &fbno
, 0);
1389 if (fbno
!= NULLAGBLOCK
) {
1390 if (args
->userdata
) {
1393 bp
= xfs_btree_get_bufs(args
->mp
, args
->tp
,
1394 args
->agno
, fbno
, 0);
1395 xfs_trans_binval(args
->tp
, bp
);
1399 XFS_WANT_CORRUPTED_GOTO(
1400 args
->agbno
+ args
->len
<=
1401 be32_to_cpu(XFS_BUF_TO_AGF(args
->agbp
)->agf_length
),
1403 args
->wasfromfl
= 1;
1404 trace_xfs_alloc_small_freelist(args
);
1409 * Nothing in the freelist.
1415 * Can't allocate from the freelist for some reason.
1422 * Can't do the allocation, give up.
1424 if (flen
< args
->minlen
) {
1425 args
->agbno
= NULLAGBLOCK
;
1426 trace_xfs_alloc_small_notenough(args
);
1432 trace_xfs_alloc_small_done(args
);
1436 trace_xfs_alloc_small_error(args
);
1441 * Free the extent starting at agno/bno for length.
1443 STATIC
int /* error */
1445 xfs_trans_t
*tp
, /* transaction pointer */
1446 xfs_buf_t
*agbp
, /* buffer for a.g. freelist header */
1447 xfs_agnumber_t agno
, /* allocation group number */
1448 xfs_agblock_t bno
, /* starting block number */
1449 xfs_extlen_t len
, /* length of extent */
1450 int isfl
) /* set if is freelist blocks - no sb acctg */
1452 xfs_btree_cur_t
*bno_cur
; /* cursor for by-block btree */
1453 xfs_btree_cur_t
*cnt_cur
; /* cursor for by-size btree */
1454 int error
; /* error return value */
1455 xfs_agblock_t gtbno
; /* start of right neighbor block */
1456 xfs_extlen_t gtlen
; /* length of right neighbor block */
1457 int haveleft
; /* have a left neighbor block */
1458 int haveright
; /* have a right neighbor block */
1459 int i
; /* temp, result code */
1460 xfs_agblock_t ltbno
; /* start of left neighbor block */
1461 xfs_extlen_t ltlen
; /* length of left neighbor block */
1462 xfs_mount_t
*mp
; /* mount point struct for filesystem */
1463 xfs_agblock_t nbno
; /* new starting block of freespace */
1464 xfs_extlen_t nlen
; /* new length of freespace */
1468 * Allocate and initialize a cursor for the by-block btree.
1470 bno_cur
= xfs_allocbt_init_cursor(mp
, tp
, agbp
, agno
, XFS_BTNUM_BNO
);
1473 * Look for a neighboring block on the left (lower block numbers)
1474 * that is contiguous with this space.
1476 if ((error
= xfs_alloc_lookup_le(bno_cur
, bno
, len
, &haveleft
)))
1480 * There is a block to our left.
1482 if ((error
= xfs_alloc_get_rec(bno_cur
, <bno
, <len
, &i
)))
1484 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
1486 * It's not contiguous, though.
1488 if (ltbno
+ ltlen
< bno
)
1492 * If this failure happens the request to free this
1493 * space was invalid, it's (partly) already free.
1496 XFS_WANT_CORRUPTED_GOTO(ltbno
+ ltlen
<= bno
, error0
);
1500 * Look for a neighboring block on the right (higher block numbers)
1501 * that is contiguous with this space.
1503 if ((error
= xfs_btree_increment(bno_cur
, 0, &haveright
)))
1507 * There is a block to our right.
1509 if ((error
= xfs_alloc_get_rec(bno_cur
, >bno
, >len
, &i
)))
1511 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
1513 * It's not contiguous, though.
1515 if (bno
+ len
< gtbno
)
1519 * If this failure happens the request to free this
1520 * space was invalid, it's (partly) already free.
1523 XFS_WANT_CORRUPTED_GOTO(gtbno
>= bno
+ len
, error0
);
1527 * Now allocate and initialize a cursor for the by-size tree.
1529 cnt_cur
= xfs_allocbt_init_cursor(mp
, tp
, agbp
, agno
, XFS_BTNUM_CNT
);
1531 * Have both left and right contiguous neighbors.
1532 * Merge all three into a single free block.
1534 if (haveleft
&& haveright
) {
1536 * Delete the old by-size entry on the left.
1538 if ((error
= xfs_alloc_lookup_eq(cnt_cur
, ltbno
, ltlen
, &i
)))
1540 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
1541 if ((error
= xfs_btree_delete(cnt_cur
, &i
)))
1543 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
1545 * Delete the old by-size entry on the right.
1547 if ((error
= xfs_alloc_lookup_eq(cnt_cur
, gtbno
, gtlen
, &i
)))
1549 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
1550 if ((error
= xfs_btree_delete(cnt_cur
, &i
)))
1552 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
1554 * Delete the old by-block entry for the right block.
1556 if ((error
= xfs_btree_delete(bno_cur
, &i
)))
1558 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
1560 * Move the by-block cursor back to the left neighbor.
1562 if ((error
= xfs_btree_decrement(bno_cur
, 0, &i
)))
1564 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
1567 * Check that this is the right record: delete didn't
1568 * mangle the cursor.
1571 xfs_agblock_t xxbno
;
1574 if ((error
= xfs_alloc_get_rec(bno_cur
, &xxbno
, &xxlen
,
1577 XFS_WANT_CORRUPTED_GOTO(
1578 i
== 1 && xxbno
== ltbno
&& xxlen
== ltlen
,
1583 * Update remaining by-block entry to the new, joined block.
1586 nlen
= len
+ ltlen
+ gtlen
;
1587 if ((error
= xfs_alloc_update(bno_cur
, nbno
, nlen
)))
1591 * Have only a left contiguous neighbor.
1592 * Merge it together with the new freespace.
1594 else if (haveleft
) {
1596 * Delete the old by-size entry on the left.
1598 if ((error
= xfs_alloc_lookup_eq(cnt_cur
, ltbno
, ltlen
, &i
)))
1600 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
1601 if ((error
= xfs_btree_delete(cnt_cur
, &i
)))
1603 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
1605 * Back up the by-block cursor to the left neighbor, and
1606 * update its length.
1608 if ((error
= xfs_btree_decrement(bno_cur
, 0, &i
)))
1610 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
1613 if ((error
= xfs_alloc_update(bno_cur
, nbno
, nlen
)))
1617 * Have only a right contiguous neighbor.
1618 * Merge it together with the new freespace.
1620 else if (haveright
) {
1622 * Delete the old by-size entry on the right.
1624 if ((error
= xfs_alloc_lookup_eq(cnt_cur
, gtbno
, gtlen
, &i
)))
1626 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
1627 if ((error
= xfs_btree_delete(cnt_cur
, &i
)))
1629 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
1631 * Update the starting block and length of the right
1632 * neighbor in the by-block tree.
1636 if ((error
= xfs_alloc_update(bno_cur
, nbno
, nlen
)))
1640 * No contiguous neighbors.
1641 * Insert the new freespace into the by-block tree.
1646 if ((error
= xfs_btree_insert(bno_cur
, &i
)))
1648 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
1650 xfs_btree_del_cursor(bno_cur
, XFS_BTREE_NOERROR
);
1653 * In all cases we need to insert the new freespace in the by-size tree.
1655 if ((error
= xfs_alloc_lookup_eq(cnt_cur
, nbno
, nlen
, &i
)))
1657 XFS_WANT_CORRUPTED_GOTO(i
== 0, error0
);
1658 if ((error
= xfs_btree_insert(cnt_cur
, &i
)))
1660 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
1661 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_NOERROR
);
1664 * Update the freespace totals in the ag and superblock.
1668 xfs_perag_t
*pag
; /* per allocation group data */
1670 pag
= xfs_perag_get(mp
, agno
);
1671 pag
->pagf_freeblks
+= len
;
1674 agf
= XFS_BUF_TO_AGF(agbp
);
1675 be32_add_cpu(&agf
->agf_freeblks
, len
);
1676 xfs_trans_agblocks_delta(tp
, len
);
1677 XFS_WANT_CORRUPTED_GOTO(
1678 be32_to_cpu(agf
->agf_freeblks
) <=
1679 be32_to_cpu(agf
->agf_length
),
1681 xfs_alloc_log_agf(tp
, agbp
, XFS_AGF_FREEBLKS
);
1683 xfs_trans_mod_sb(tp
, XFS_TRANS_SB_FDBLOCKS
, (long)len
);
1684 XFS_STATS_INC(xs_freex
);
1685 XFS_STATS_ADD(xs_freeb
, len
);
1688 trace_xfs_free_extent(mp
, agno
, bno
, len
, isfl
, haveleft
, haveright
);
1691 * Since blocks move to the free list without the coordination
1692 * used in xfs_bmap_finish, we can't allow block to be available
1693 * for reallocation and non-transaction writing (user data)
1694 * until we know that the transaction that moved it to the free
1695 * list is permanently on disk. We track the blocks by declaring
1696 * these blocks as "busy"; the busy list is maintained on a per-ag
1697 * basis and each transaction records which entries should be removed
1698 * when the iclog commits to disk. If a busy block is allocated,
1699 * the iclog is pushed up to the LSN that freed the block.
1701 xfs_alloc_busy_insert(tp
, agno
, bno
, len
);
1705 trace_xfs_free_extent(mp
, agno
, bno
, len
, isfl
, -1, -1);
1707 xfs_btree_del_cursor(bno_cur
, XFS_BTREE_ERROR
);
1709 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_ERROR
);
1714 * Visible (exported) allocation/free functions.
1715 * Some of these are used just by xfs_alloc_btree.c and this file.
1719 * Compute and fill in value of m_ag_maxlevels.
1722 xfs_alloc_compute_maxlevels(
1723 xfs_mount_t
*mp
) /* file system mount structure */
1731 maxleafents
= (mp
->m_sb
.sb_agblocks
+ 1) / 2;
1732 minleafrecs
= mp
->m_alloc_mnr
[0];
1733 minnoderecs
= mp
->m_alloc_mnr
[1];
1734 maxblocks
= (maxleafents
+ minleafrecs
- 1) / minleafrecs
;
1735 for (level
= 1; maxblocks
> 1; level
++)
1736 maxblocks
= (maxblocks
+ minnoderecs
- 1) / minnoderecs
;
1737 mp
->m_ag_maxlevels
= level
;
1741 * Find the length of the longest extent in an AG.
1744 xfs_alloc_longest_free_extent(
1745 struct xfs_mount
*mp
,
1746 struct xfs_perag
*pag
)
1748 xfs_extlen_t need
, delta
= 0;
1750 need
= XFS_MIN_FREELIST_PAG(pag
, mp
);
1751 if (need
> pag
->pagf_flcount
)
1752 delta
= need
- pag
->pagf_flcount
;
1754 if (pag
->pagf_longest
> delta
)
1755 return pag
->pagf_longest
- delta
;
1756 return pag
->pagf_flcount
> 0 || pag
->pagf_longest
> 0;
1760 * Decide whether to use this allocation group for this allocation.
1761 * If so, fix up the btree freelist's size.
1763 STATIC
int /* error */
1764 xfs_alloc_fix_freelist(
1765 xfs_alloc_arg_t
*args
, /* allocation argument structure */
1766 int flags
) /* XFS_ALLOC_FLAG_... */
1768 xfs_buf_t
*agbp
; /* agf buffer pointer */
1769 xfs_agf_t
*agf
; /* a.g. freespace structure pointer */
1770 xfs_buf_t
*agflbp
;/* agfl buffer pointer */
1771 xfs_agblock_t bno
; /* freelist block */
1772 xfs_extlen_t delta
; /* new blocks needed in freelist */
1773 int error
; /* error result code */
1774 xfs_extlen_t longest
;/* longest extent in allocation group */
1775 xfs_mount_t
*mp
; /* file system mount point structure */
1776 xfs_extlen_t need
; /* total blocks needed in freelist */
1777 xfs_perag_t
*pag
; /* per-ag information structure */
1778 xfs_alloc_arg_t targs
; /* local allocation arguments */
1779 xfs_trans_t
*tp
; /* transaction pointer */
1785 if (!pag
->pagf_init
) {
1786 if ((error
= xfs_alloc_read_agf(mp
, tp
, args
->agno
, flags
,
1789 if (!pag
->pagf_init
) {
1790 ASSERT(flags
& XFS_ALLOC_FLAG_TRYLOCK
);
1791 ASSERT(!(flags
& XFS_ALLOC_FLAG_FREEING
));
1799 * If this is a metadata preferred pag and we are user data
1800 * then try somewhere else if we are not being asked to
1801 * try harder at this point
1803 if (pag
->pagf_metadata
&& args
->userdata
&&
1804 (flags
& XFS_ALLOC_FLAG_TRYLOCK
)) {
1805 ASSERT(!(flags
& XFS_ALLOC_FLAG_FREEING
));
1810 if (!(flags
& XFS_ALLOC_FLAG_FREEING
)) {
1812 * If it looks like there isn't a long enough extent, or enough
1813 * total blocks, reject it.
1815 need
= XFS_MIN_FREELIST_PAG(pag
, mp
);
1816 longest
= xfs_alloc_longest_free_extent(mp
, pag
);
1817 if ((args
->minlen
+ args
->alignment
+ args
->minalignslop
- 1) >
1819 ((int)(pag
->pagf_freeblks
+ pag
->pagf_flcount
-
1820 need
- args
->total
) < (int)args
->minleft
)) {
1822 xfs_trans_brelse(tp
, agbp
);
1829 * Get the a.g. freespace buffer.
1830 * Can fail if we're not blocking on locks, and it's held.
1833 if ((error
= xfs_alloc_read_agf(mp
, tp
, args
->agno
, flags
,
1837 ASSERT(flags
& XFS_ALLOC_FLAG_TRYLOCK
);
1838 ASSERT(!(flags
& XFS_ALLOC_FLAG_FREEING
));
1844 * Figure out how many blocks we should have in the freelist.
1846 agf
= XFS_BUF_TO_AGF(agbp
);
1847 need
= XFS_MIN_FREELIST(agf
, mp
);
1849 * If there isn't enough total or single-extent, reject it.
1851 if (!(flags
& XFS_ALLOC_FLAG_FREEING
)) {
1852 delta
= need
> be32_to_cpu(agf
->agf_flcount
) ?
1853 (need
- be32_to_cpu(agf
->agf_flcount
)) : 0;
1854 longest
= be32_to_cpu(agf
->agf_longest
);
1855 longest
= (longest
> delta
) ? (longest
- delta
) :
1856 (be32_to_cpu(agf
->agf_flcount
) > 0 || longest
> 0);
1857 if ((args
->minlen
+ args
->alignment
+ args
->minalignslop
- 1) >
1859 ((int)(be32_to_cpu(agf
->agf_freeblks
) +
1860 be32_to_cpu(agf
->agf_flcount
) - need
- args
->total
) <
1861 (int)args
->minleft
)) {
1862 xfs_trans_brelse(tp
, agbp
);
1868 * Make the freelist shorter if it's too long.
1870 while (be32_to_cpu(agf
->agf_flcount
) > need
) {
1873 error
= xfs_alloc_get_freelist(tp
, agbp
, &bno
, 0);
1876 if ((error
= xfs_free_ag_extent(tp
, agbp
, args
->agno
, bno
, 1, 1)))
1878 bp
= xfs_btree_get_bufs(mp
, tp
, args
->agno
, bno
, 0);
1879 xfs_trans_binval(tp
, bp
);
1882 * Initialize the args structure.
1887 targs
.agno
= args
->agno
;
1888 targs
.mod
= targs
.minleft
= targs
.wasdel
= targs
.userdata
=
1889 targs
.minalignslop
= 0;
1890 targs
.alignment
= targs
.minlen
= targs
.prod
= targs
.isfl
= 1;
1891 targs
.type
= XFS_ALLOCTYPE_THIS_AG
;
1893 if ((error
= xfs_alloc_read_agfl(mp
, tp
, targs
.agno
, &agflbp
)))
1896 * Make the freelist longer if it's too short.
1898 while (be32_to_cpu(agf
->agf_flcount
) < need
) {
1900 targs
.maxlen
= need
- be32_to_cpu(agf
->agf_flcount
);
1902 * Allocate as many blocks as possible at once.
1904 if ((error
= xfs_alloc_ag_vextent(&targs
))) {
1905 xfs_trans_brelse(tp
, agflbp
);
1909 * Stop if we run out. Won't happen if callers are obeying
1910 * the restrictions correctly. Can happen for free calls
1911 * on a completely full ag.
1913 if (targs
.agbno
== NULLAGBLOCK
) {
1914 if (flags
& XFS_ALLOC_FLAG_FREEING
)
1916 xfs_trans_brelse(tp
, agflbp
);
1921 * Put each allocated block on the list.
1923 for (bno
= targs
.agbno
; bno
< targs
.agbno
+ targs
.len
; bno
++) {
1924 error
= xfs_alloc_put_freelist(tp
, agbp
,
1930 xfs_trans_brelse(tp
, agflbp
);
1936 * Get a block from the freelist.
1937 * Returns with the buffer for the block gotten.
1940 xfs_alloc_get_freelist(
1941 xfs_trans_t
*tp
, /* transaction pointer */
1942 xfs_buf_t
*agbp
, /* buffer containing the agf structure */
1943 xfs_agblock_t
*bnop
, /* block address retrieved from freelist */
1944 int btreeblk
) /* destination is a AGF btree */
1946 xfs_agf_t
*agf
; /* a.g. freespace structure */
1947 xfs_agfl_t
*agfl
; /* a.g. freelist structure */
1948 xfs_buf_t
*agflbp
;/* buffer for a.g. freelist structure */
1949 xfs_agblock_t bno
; /* block number returned */
1952 xfs_mount_t
*mp
; /* mount structure */
1953 xfs_perag_t
*pag
; /* per allocation group data */
1955 agf
= XFS_BUF_TO_AGF(agbp
);
1957 * Freelist is empty, give up.
1959 if (!agf
->agf_flcount
) {
1960 *bnop
= NULLAGBLOCK
;
1964 * Read the array of free blocks.
1967 if ((error
= xfs_alloc_read_agfl(mp
, tp
,
1968 be32_to_cpu(agf
->agf_seqno
), &agflbp
)))
1970 agfl
= XFS_BUF_TO_AGFL(agflbp
);
1972 * Get the block number and update the data structures.
1974 bno
= be32_to_cpu(agfl
->agfl_bno
[be32_to_cpu(agf
->agf_flfirst
)]);
1975 be32_add_cpu(&agf
->agf_flfirst
, 1);
1976 xfs_trans_brelse(tp
, agflbp
);
1977 if (be32_to_cpu(agf
->agf_flfirst
) == XFS_AGFL_SIZE(mp
))
1978 agf
->agf_flfirst
= 0;
1980 pag
= xfs_perag_get(mp
, be32_to_cpu(agf
->agf_seqno
));
1981 be32_add_cpu(&agf
->agf_flcount
, -1);
1982 xfs_trans_agflist_delta(tp
, -1);
1983 pag
->pagf_flcount
--;
1986 logflags
= XFS_AGF_FLFIRST
| XFS_AGF_FLCOUNT
;
1988 be32_add_cpu(&agf
->agf_btreeblks
, 1);
1989 pag
->pagf_btreeblks
++;
1990 logflags
|= XFS_AGF_BTREEBLKS
;
1993 xfs_alloc_log_agf(tp
, agbp
, logflags
);
1997 * As blocks are freed, they are added to the per-ag busy list and
1998 * remain there until the freeing transaction is committed to disk.
1999 * Now that we have allocated blocks, this list must be searched to see
2000 * if a block is being reused. If one is, then the freeing transaction
2001 * must be pushed to disk before this transaction.
2003 * We do this by setting the current transaction to a sync transaction
2004 * which guarantees that the freeing transaction is on disk before this
2005 * transaction. This is done instead of a synchronous log force here so
2006 * that we don't sit and wait with the AGF locked in the transaction
2007 * during the log force.
2009 if (xfs_alloc_busy_search(mp
, be32_to_cpu(agf
->agf_seqno
), bno
, 1))
2010 xfs_trans_set_sync(tp
);
2015 * Log the given fields from the agf structure.
2019 xfs_trans_t
*tp
, /* transaction pointer */
2020 xfs_buf_t
*bp
, /* buffer for a.g. freelist header */
2021 int fields
) /* mask of fields to be logged (XFS_AGF_...) */
2023 int first
; /* first byte offset */
2024 int last
; /* last byte offset */
2025 static const short offsets
[] = {
2026 offsetof(xfs_agf_t
, agf_magicnum
),
2027 offsetof(xfs_agf_t
, agf_versionnum
),
2028 offsetof(xfs_agf_t
, agf_seqno
),
2029 offsetof(xfs_agf_t
, agf_length
),
2030 offsetof(xfs_agf_t
, agf_roots
[0]),
2031 offsetof(xfs_agf_t
, agf_levels
[0]),
2032 offsetof(xfs_agf_t
, agf_flfirst
),
2033 offsetof(xfs_agf_t
, agf_fllast
),
2034 offsetof(xfs_agf_t
, agf_flcount
),
2035 offsetof(xfs_agf_t
, agf_freeblks
),
2036 offsetof(xfs_agf_t
, agf_longest
),
2037 offsetof(xfs_agf_t
, agf_btreeblks
),
2041 trace_xfs_agf(tp
->t_mountp
, XFS_BUF_TO_AGF(bp
), fields
, _RET_IP_
);
2043 xfs_btree_offsets(fields
, offsets
, XFS_AGF_NUM_BITS
, &first
, &last
);
2044 xfs_trans_log_buf(tp
, bp
, (uint
)first
, (uint
)last
);
2048 * Interface for inode allocation to force the pag data to be initialized.
2051 xfs_alloc_pagf_init(
2052 xfs_mount_t
*mp
, /* file system mount structure */
2053 xfs_trans_t
*tp
, /* transaction pointer */
2054 xfs_agnumber_t agno
, /* allocation group number */
2055 int flags
) /* XFS_ALLOC_FLAGS_... */
2060 if ((error
= xfs_alloc_read_agf(mp
, tp
, agno
, flags
, &bp
)))
2063 xfs_trans_brelse(tp
, bp
);
2068 * Put the block on the freelist for the allocation group.
2071 xfs_alloc_put_freelist(
2072 xfs_trans_t
*tp
, /* transaction pointer */
2073 xfs_buf_t
*agbp
, /* buffer for a.g. freelist header */
2074 xfs_buf_t
*agflbp
,/* buffer for a.g. free block array */
2075 xfs_agblock_t bno
, /* block being freed */
2076 int btreeblk
) /* block came from a AGF btree */
2078 xfs_agf_t
*agf
; /* a.g. freespace structure */
2079 xfs_agfl_t
*agfl
; /* a.g. free block array */
2080 __be32
*blockp
;/* pointer to array entry */
2083 xfs_mount_t
*mp
; /* mount structure */
2084 xfs_perag_t
*pag
; /* per allocation group data */
2086 agf
= XFS_BUF_TO_AGF(agbp
);
2089 if (!agflbp
&& (error
= xfs_alloc_read_agfl(mp
, tp
,
2090 be32_to_cpu(agf
->agf_seqno
), &agflbp
)))
2092 agfl
= XFS_BUF_TO_AGFL(agflbp
);
2093 be32_add_cpu(&agf
->agf_fllast
, 1);
2094 if (be32_to_cpu(agf
->agf_fllast
) == XFS_AGFL_SIZE(mp
))
2095 agf
->agf_fllast
= 0;
2097 pag
= xfs_perag_get(mp
, be32_to_cpu(agf
->agf_seqno
));
2098 be32_add_cpu(&agf
->agf_flcount
, 1);
2099 xfs_trans_agflist_delta(tp
, 1);
2100 pag
->pagf_flcount
++;
2102 logflags
= XFS_AGF_FLLAST
| XFS_AGF_FLCOUNT
;
2104 be32_add_cpu(&agf
->agf_btreeblks
, -1);
2105 pag
->pagf_btreeblks
--;
2106 logflags
|= XFS_AGF_BTREEBLKS
;
2110 xfs_alloc_log_agf(tp
, agbp
, logflags
);
2112 ASSERT(be32_to_cpu(agf
->agf_flcount
) <= XFS_AGFL_SIZE(mp
));
2113 blockp
= &agfl
->agfl_bno
[be32_to_cpu(agf
->agf_fllast
)];
2114 *blockp
= cpu_to_be32(bno
);
2115 xfs_alloc_log_agf(tp
, agbp
, logflags
);
2116 xfs_trans_log_buf(tp
, agflbp
,
2117 (int)((xfs_caddr_t
)blockp
- (xfs_caddr_t
)agfl
),
2118 (int)((xfs_caddr_t
)blockp
- (xfs_caddr_t
)agfl
+
2119 sizeof(xfs_agblock_t
) - 1));
2124 * Read in the allocation group header (free/alloc section).
2128 struct xfs_mount
*mp
, /* mount point structure */
2129 struct xfs_trans
*tp
, /* transaction pointer */
2130 xfs_agnumber_t agno
, /* allocation group number */
2131 int flags
, /* XFS_BUF_ */
2132 struct xfs_buf
**bpp
) /* buffer for the ag freelist header */
2134 struct xfs_agf
*agf
; /* ag freelist header */
2135 int agf_ok
; /* set if agf is consistent */
2138 ASSERT(agno
!= NULLAGNUMBER
);
2139 error
= xfs_trans_read_buf(
2140 mp
, tp
, mp
->m_ddev_targp
,
2141 XFS_AG_DADDR(mp
, agno
, XFS_AGF_DADDR(mp
)),
2142 XFS_FSS_TO_BB(mp
, 1), flags
, bpp
);
2148 ASSERT(!XFS_BUF_GETERROR(*bpp
));
2149 agf
= XFS_BUF_TO_AGF(*bpp
);
2152 * Validate the magic number of the agf block.
2155 be32_to_cpu(agf
->agf_magicnum
) == XFS_AGF_MAGIC
&&
2156 XFS_AGF_GOOD_VERSION(be32_to_cpu(agf
->agf_versionnum
)) &&
2157 be32_to_cpu(agf
->agf_freeblks
) <= be32_to_cpu(agf
->agf_length
) &&
2158 be32_to_cpu(agf
->agf_flfirst
) < XFS_AGFL_SIZE(mp
) &&
2159 be32_to_cpu(agf
->agf_fllast
) < XFS_AGFL_SIZE(mp
) &&
2160 be32_to_cpu(agf
->agf_flcount
) <= XFS_AGFL_SIZE(mp
) &&
2161 be32_to_cpu(agf
->agf_seqno
) == agno
;
2162 if (xfs_sb_version_haslazysbcount(&mp
->m_sb
))
2163 agf_ok
= agf_ok
&& be32_to_cpu(agf
->agf_btreeblks
) <=
2164 be32_to_cpu(agf
->agf_length
);
2165 if (unlikely(XFS_TEST_ERROR(!agf_ok
, mp
, XFS_ERRTAG_ALLOC_READ_AGF
,
2166 XFS_RANDOM_ALLOC_READ_AGF
))) {
2167 XFS_CORRUPTION_ERROR("xfs_alloc_read_agf",
2168 XFS_ERRLEVEL_LOW
, mp
, agf
);
2169 xfs_trans_brelse(tp
, *bpp
);
2170 return XFS_ERROR(EFSCORRUPTED
);
2172 XFS_BUF_SET_VTYPE_REF(*bpp
, B_FS_AGF
, XFS_AGF_REF
);
2177 * Read in the allocation group header (free/alloc section).
2181 struct xfs_mount
*mp
, /* mount point structure */
2182 struct xfs_trans
*tp
, /* transaction pointer */
2183 xfs_agnumber_t agno
, /* allocation group number */
2184 int flags
, /* XFS_ALLOC_FLAG_... */
2185 struct xfs_buf
**bpp
) /* buffer for the ag freelist header */
2187 struct xfs_agf
*agf
; /* ag freelist header */
2188 struct xfs_perag
*pag
; /* per allocation group data */
2191 ASSERT(agno
!= NULLAGNUMBER
);
2193 error
= xfs_read_agf(mp
, tp
, agno
,
2194 (flags
& XFS_ALLOC_FLAG_TRYLOCK
) ? XBF_TRYLOCK
: 0,
2200 ASSERT(!XFS_BUF_GETERROR(*bpp
));
2202 agf
= XFS_BUF_TO_AGF(*bpp
);
2203 pag
= xfs_perag_get(mp
, agno
);
2204 if (!pag
->pagf_init
) {
2205 pag
->pagf_freeblks
= be32_to_cpu(agf
->agf_freeblks
);
2206 pag
->pagf_btreeblks
= be32_to_cpu(agf
->agf_btreeblks
);
2207 pag
->pagf_flcount
= be32_to_cpu(agf
->agf_flcount
);
2208 pag
->pagf_longest
= be32_to_cpu(agf
->agf_longest
);
2209 pag
->pagf_levels
[XFS_BTNUM_BNOi
] =
2210 be32_to_cpu(agf
->agf_levels
[XFS_BTNUM_BNOi
]);
2211 pag
->pagf_levels
[XFS_BTNUM_CNTi
] =
2212 be32_to_cpu(agf
->agf_levels
[XFS_BTNUM_CNTi
]);
2213 spin_lock_init(&pag
->pagb_lock
);
2214 pag
->pagb_count
= 0;
2215 pag
->pagb_tree
= RB_ROOT
;
2219 else if (!XFS_FORCED_SHUTDOWN(mp
)) {
2220 ASSERT(pag
->pagf_freeblks
== be32_to_cpu(agf
->agf_freeblks
));
2221 ASSERT(pag
->pagf_btreeblks
== be32_to_cpu(agf
->agf_btreeblks
));
2222 ASSERT(pag
->pagf_flcount
== be32_to_cpu(agf
->agf_flcount
));
2223 ASSERT(pag
->pagf_longest
== be32_to_cpu(agf
->agf_longest
));
2224 ASSERT(pag
->pagf_levels
[XFS_BTNUM_BNOi
] ==
2225 be32_to_cpu(agf
->agf_levels
[XFS_BTNUM_BNOi
]));
2226 ASSERT(pag
->pagf_levels
[XFS_BTNUM_CNTi
] ==
2227 be32_to_cpu(agf
->agf_levels
[XFS_BTNUM_CNTi
]));
2235 * Allocate an extent (variable-size).
2236 * Depending on the allocation type, we either look in a single allocation
2237 * group or loop over the allocation groups to find the result.
2241 xfs_alloc_arg_t
*args
) /* allocation argument structure */
2243 xfs_agblock_t agsize
; /* allocation group size */
2245 int flags
; /* XFS_ALLOC_FLAG_... locking flags */
2246 xfs_extlen_t minleft
;/* minimum left value, temp copy */
2247 xfs_mount_t
*mp
; /* mount structure pointer */
2248 xfs_agnumber_t sagno
; /* starting allocation group number */
2249 xfs_alloctype_t type
; /* input allocation type */
2252 xfs_agnumber_t rotorstep
= xfs_rotorstep
; /* inode32 agf stepper */
2255 type
= args
->otype
= args
->type
;
2256 args
->agbno
= NULLAGBLOCK
;
2258 * Just fix this up, for the case where the last a.g. is shorter
2259 * (or there's only one a.g.) and the caller couldn't easily figure
2260 * that out (xfs_bmap_alloc).
2262 agsize
= mp
->m_sb
.sb_agblocks
;
2263 if (args
->maxlen
> agsize
)
2264 args
->maxlen
= agsize
;
2265 if (args
->alignment
== 0)
2266 args
->alignment
= 1;
2267 ASSERT(XFS_FSB_TO_AGNO(mp
, args
->fsbno
) < mp
->m_sb
.sb_agcount
);
2268 ASSERT(XFS_FSB_TO_AGBNO(mp
, args
->fsbno
) < agsize
);
2269 ASSERT(args
->minlen
<= args
->maxlen
);
2270 ASSERT(args
->minlen
<= agsize
);
2271 ASSERT(args
->mod
< args
->prod
);
2272 if (XFS_FSB_TO_AGNO(mp
, args
->fsbno
) >= mp
->m_sb
.sb_agcount
||
2273 XFS_FSB_TO_AGBNO(mp
, args
->fsbno
) >= agsize
||
2274 args
->minlen
> args
->maxlen
|| args
->minlen
> agsize
||
2275 args
->mod
>= args
->prod
) {
2276 args
->fsbno
= NULLFSBLOCK
;
2277 trace_xfs_alloc_vextent_badargs(args
);
2280 minleft
= args
->minleft
;
2283 case XFS_ALLOCTYPE_THIS_AG
:
2284 case XFS_ALLOCTYPE_NEAR_BNO
:
2285 case XFS_ALLOCTYPE_THIS_BNO
:
2287 * These three force us into a single a.g.
2289 args
->agno
= XFS_FSB_TO_AGNO(mp
, args
->fsbno
);
2290 args
->pag
= xfs_perag_get(mp
, args
->agno
);
2292 error
= xfs_alloc_fix_freelist(args
, 0);
2293 args
->minleft
= minleft
;
2295 trace_xfs_alloc_vextent_nofix(args
);
2299 trace_xfs_alloc_vextent_noagbp(args
);
2302 args
->agbno
= XFS_FSB_TO_AGBNO(mp
, args
->fsbno
);
2303 if ((error
= xfs_alloc_ag_vextent(args
)))
2306 case XFS_ALLOCTYPE_START_BNO
:
2308 * Try near allocation first, then anywhere-in-ag after
2309 * the first a.g. fails.
2311 if ((args
->userdata
== XFS_ALLOC_INITIAL_USER_DATA
) &&
2312 (mp
->m_flags
& XFS_MOUNT_32BITINODES
)) {
2313 args
->fsbno
= XFS_AGB_TO_FSB(mp
,
2314 ((mp
->m_agfrotor
/ rotorstep
) %
2315 mp
->m_sb
.sb_agcount
), 0);
2318 args
->agbno
= XFS_FSB_TO_AGBNO(mp
, args
->fsbno
);
2319 args
->type
= XFS_ALLOCTYPE_NEAR_BNO
;
2321 case XFS_ALLOCTYPE_ANY_AG
:
2322 case XFS_ALLOCTYPE_START_AG
:
2323 case XFS_ALLOCTYPE_FIRST_AG
:
2325 * Rotate through the allocation groups looking for a winner.
2327 if (type
== XFS_ALLOCTYPE_ANY_AG
) {
2329 * Start with the last place we left off.
2331 args
->agno
= sagno
= (mp
->m_agfrotor
/ rotorstep
) %
2332 mp
->m_sb
.sb_agcount
;
2333 args
->type
= XFS_ALLOCTYPE_THIS_AG
;
2334 flags
= XFS_ALLOC_FLAG_TRYLOCK
;
2335 } else if (type
== XFS_ALLOCTYPE_FIRST_AG
) {
2337 * Start with allocation group given by bno.
2339 args
->agno
= XFS_FSB_TO_AGNO(mp
, args
->fsbno
);
2340 args
->type
= XFS_ALLOCTYPE_THIS_AG
;
2344 if (type
== XFS_ALLOCTYPE_START_AG
)
2345 args
->type
= XFS_ALLOCTYPE_THIS_AG
;
2347 * Start with the given allocation group.
2349 args
->agno
= sagno
= XFS_FSB_TO_AGNO(mp
, args
->fsbno
);
2350 flags
= XFS_ALLOC_FLAG_TRYLOCK
;
2353 * Loop over allocation groups twice; first time with
2354 * trylock set, second time without.
2357 args
->pag
= xfs_perag_get(mp
, args
->agno
);
2358 if (no_min
) args
->minleft
= 0;
2359 error
= xfs_alloc_fix_freelist(args
, flags
);
2360 args
->minleft
= minleft
;
2362 trace_xfs_alloc_vextent_nofix(args
);
2366 * If we get a buffer back then the allocation will fly.
2369 if ((error
= xfs_alloc_ag_vextent(args
)))
2374 trace_xfs_alloc_vextent_loopfailed(args
);
2377 * Didn't work, figure out the next iteration.
2379 if (args
->agno
== sagno
&&
2380 type
== XFS_ALLOCTYPE_START_BNO
)
2381 args
->type
= XFS_ALLOCTYPE_THIS_AG
;
2383 * For the first allocation, we can try any AG to get
2384 * space. However, if we already have allocated a
2385 * block, we don't want to try AGs whose number is below
2386 * sagno. Otherwise, we may end up with out-of-order
2387 * locking of AGF, which might cause deadlock.
2389 if (++(args
->agno
) == mp
->m_sb
.sb_agcount
) {
2390 if (args
->firstblock
!= NULLFSBLOCK
)
2396 * Reached the starting a.g., must either be done
2397 * or switch to non-trylock mode.
2399 if (args
->agno
== sagno
) {
2401 args
->agbno
= NULLAGBLOCK
;
2402 trace_xfs_alloc_vextent_allfailed(args
);
2409 if (type
== XFS_ALLOCTYPE_START_BNO
) {
2410 args
->agbno
= XFS_FSB_TO_AGBNO(mp
,
2412 args
->type
= XFS_ALLOCTYPE_NEAR_BNO
;
2416 xfs_perag_put(args
->pag
);
2418 if (bump_rotor
|| (type
== XFS_ALLOCTYPE_ANY_AG
)) {
2419 if (args
->agno
== sagno
)
2420 mp
->m_agfrotor
= (mp
->m_agfrotor
+ 1) %
2421 (mp
->m_sb
.sb_agcount
* rotorstep
);
2423 mp
->m_agfrotor
= (args
->agno
* rotorstep
+ 1) %
2424 (mp
->m_sb
.sb_agcount
* rotorstep
);
2431 if (args
->agbno
== NULLAGBLOCK
)
2432 args
->fsbno
= NULLFSBLOCK
;
2434 args
->fsbno
= XFS_AGB_TO_FSB(mp
, args
->agno
, args
->agbno
);
2436 ASSERT(args
->len
>= args
->minlen
);
2437 ASSERT(args
->len
<= args
->maxlen
);
2438 ASSERT(args
->agbno
% args
->alignment
== 0);
2439 XFS_AG_CHECK_DADDR(mp
, XFS_FSB_TO_DADDR(mp
, args
->fsbno
),
2443 xfs_perag_put(args
->pag
);
2446 xfs_perag_put(args
->pag
);
2452 * Just break up the extent address and hand off to xfs_free_ag_extent
2453 * after fixing up the freelist.
2457 xfs_trans_t
*tp
, /* transaction pointer */
2458 xfs_fsblock_t bno
, /* starting block number of extent */
2459 xfs_extlen_t len
) /* length of extent */
2461 xfs_alloc_arg_t args
;
2465 memset(&args
, 0, sizeof(xfs_alloc_arg_t
));
2467 args
.mp
= tp
->t_mountp
;
2468 args
.agno
= XFS_FSB_TO_AGNO(args
.mp
, bno
);
2469 ASSERT(args
.agno
< args
.mp
->m_sb
.sb_agcount
);
2470 args
.agbno
= XFS_FSB_TO_AGBNO(args
.mp
, bno
);
2471 args
.pag
= xfs_perag_get(args
.mp
, args
.agno
);
2472 if ((error
= xfs_alloc_fix_freelist(&args
, XFS_ALLOC_FLAG_FREEING
)))
2475 ASSERT(args
.agbp
!= NULL
);
2476 ASSERT((args
.agbno
+ len
) <=
2477 be32_to_cpu(XFS_BUF_TO_AGF(args
.agbp
)->agf_length
));
2479 error
= xfs_free_ag_extent(tp
, args
.agbp
, args
.agno
, args
.agbno
, len
, 0);
2481 xfs_perag_put(args
.pag
);
2487 * AG Busy list management
2488 * The busy list contains block ranges that have been freed but whose
2489 * transactions have not yet hit disk. If any block listed in a busy
2490 * list is reused, the transaction that freed it must be forced to disk
2491 * before continuing to use the block.
2493 * xfs_alloc_busy_insert - add to the per-ag busy list
2494 * xfs_alloc_busy_clear - remove an item from the per-ag busy list
2495 * xfs_alloc_busy_search - search for a busy extent
2499 * Insert a new extent into the busy tree.
2501 * The busy extent tree is indexed by the start block of the busy extent.
2502 * there can be multiple overlapping ranges in the busy extent tree but only
2503 * ever one entry at a given start block. The reason for this is that
2504 * multi-block extents can be freed, then smaller chunks of that extent
2505 * allocated and freed again before the first transaction commit is on disk.
2506 * If the exact same start block is freed a second time, we have to wait for
2507 * that busy extent to pass out of the tree before the new extent is inserted.
2508 * There are two main cases we have to handle here.
2510 * The first case is a transaction that triggers a "free - allocate - free"
2511 * cycle. This can occur during btree manipulations as a btree block is freed
2512 * to the freelist, then allocated from the free list, then freed again. In
2513 * this case, the second extxpnet free is what triggers the duplicate and as
2514 * such the transaction IDs should match. Because the extent was allocated in
2515 * this transaction, the transaction must be marked as synchronous. This is
2516 * true for all cases where the free/alloc/free occurs in the one transaction,
2517 * hence the addition of the ASSERT(tp->t_flags & XFS_TRANS_SYNC) to this case.
2518 * This serves to catch violations of the second case quite effectively.
2520 * The second case is where the free/alloc/free occur in different
2521 * transactions. In this case, the thread freeing the extent the second time
2522 * can't mark the extent busy immediately because it is already tracked in a
2523 * transaction that may be committing. When the log commit for the existing
2524 * busy extent completes, the busy extent will be removed from the tree. If we
2525 * allow the second busy insert to continue using that busy extent structure,
2526 * it can be freed before this transaction is safely in the log. Hence our
2527 * only option in this case is to force the log to remove the existing busy
2528 * extent from the list before we insert the new one with the current
2531 * The problem we are trying to avoid in the free-alloc-free in separate
2532 * transactions is most easily described with a timeline:
2534 * Thread 1 Thread 2 Thread 3 xfslogd
2557 * checkpoint completes
2559 * By issuing a log force in thread 3 @ "KABOOM", the thread will block until
2560 * the checkpoint completes, and the busy extent it matched will have been
2561 * removed from the tree when it is woken. Hence it can then continue safely.
2563 * However, to ensure this matching process is robust, we need to use the
2564 * transaction ID for identifying transaction, as delayed logging results in
2565 * the busy extent and transaction lifecycles being different. i.e. the busy
2566 * extent is active for a lot longer than the transaction. Hence the
2567 * transaction structure can be freed and reallocated, then mark the same
2568 * extent busy again in the new transaction. In this case the new transaction
2569 * will have a different tid but can have the same address, and hence we need
2570 * to check against the tid.
2572 * Future: for delayed logging, we could avoid the log force if the extent was
2573 * first freed in the current checkpoint sequence. This, however, requires the
2574 * ability to pin the current checkpoint in memory until this transaction
2575 * commits to ensure that both the original free and the current one combine
2576 * logically into the one checkpoint. If the checkpoint sequences are
2577 * different, however, we still need to wait on a log force.
2580 xfs_alloc_busy_insert(
2581 struct xfs_trans
*tp
,
2582 xfs_agnumber_t agno
,
2586 struct xfs_busy_extent
*new;
2587 struct xfs_busy_extent
*busyp
;
2588 struct xfs_perag
*pag
;
2589 struct rb_node
**rbp
;
2590 struct rb_node
*parent
;
2594 new = kmem_zalloc(sizeof(struct xfs_busy_extent
), KM_MAYFAIL
);
2597 * No Memory! Since it is now not possible to track the free
2598 * block, make this a synchronous transaction to insure that
2599 * the block is not reused before this transaction commits.
2601 trace_xfs_alloc_busy(tp
, agno
, bno
, len
, 1);
2602 xfs_trans_set_sync(tp
);
2609 new->tid
= xfs_log_get_trans_ident(tp
);
2611 INIT_LIST_HEAD(&new->list
);
2613 /* trace before insert to be able to see failed inserts */
2614 trace_xfs_alloc_busy(tp
, agno
, bno
, len
, 0);
2616 pag
= xfs_perag_get(tp
->t_mountp
, new->agno
);
2618 spin_lock(&pag
->pagb_lock
);
2619 rbp
= &pag
->pagb_tree
.rb_node
;
2623 while (*rbp
&& match
>= 0) {
2625 busyp
= rb_entry(parent
, struct xfs_busy_extent
, rb_node
);
2627 if (new->bno
< busyp
->bno
) {
2628 /* may overlap, but exact start block is lower */
2629 rbp
= &(*rbp
)->rb_left
;
2630 if (new->bno
+ new->length
> busyp
->bno
)
2631 match
= busyp
->tid
== new->tid
? 1 : -1;
2632 } else if (new->bno
> busyp
->bno
) {
2633 /* may overlap, but exact start block is higher */
2634 rbp
= &(*rbp
)->rb_right
;
2635 if (bno
< busyp
->bno
+ busyp
->length
)
2636 match
= busyp
->tid
== new->tid
? 1 : -1;
2638 match
= busyp
->tid
== new->tid
? 1 : -1;
2643 /* overlap marked busy in different transaction */
2644 spin_unlock(&pag
->pagb_lock
);
2645 xfs_log_force(tp
->t_mountp
, XFS_LOG_SYNC
);
2650 * overlap marked busy in same transaction. Update if exact
2651 * start block match, otherwise combine the busy extents into
2654 if (busyp
->bno
== new->bno
) {
2655 busyp
->length
= max(busyp
->length
, new->length
);
2656 spin_unlock(&pag
->pagb_lock
);
2657 ASSERT(tp
->t_flags
& XFS_TRANS_SYNC
);
2662 rb_erase(&busyp
->rb_node
, &pag
->pagb_tree
);
2663 new->length
= max(busyp
->bno
+ busyp
->length
,
2664 new->bno
+ new->length
) -
2665 min(busyp
->bno
, new->bno
);
2666 new->bno
= min(busyp
->bno
, new->bno
);
2670 rb_link_node(&new->rb_node
, parent
, rbp
);
2671 rb_insert_color(&new->rb_node
, &pag
->pagb_tree
);
2673 list_add(&new->list
, &tp
->t_busy
);
2674 spin_unlock(&pag
->pagb_lock
);
2680 * Search for a busy extent within the range of the extent we are about to
2681 * allocate. You need to be holding the busy extent tree lock when calling
2682 * xfs_alloc_busy_search(). This function returns 0 for no overlapping busy
2683 * extent, -1 for an overlapping but not exact busy extent, and 1 for an exact
2684 * match. This is done so that a non-zero return indicates an overlap that
2685 * will require a synchronous transaction, but it can still be
2686 * used to distinguish between a partial or exact match.
2689 xfs_alloc_busy_search(
2690 struct xfs_mount
*mp
,
2691 xfs_agnumber_t agno
,
2695 struct xfs_perag
*pag
;
2696 struct rb_node
*rbp
;
2697 struct xfs_busy_extent
*busyp
;
2700 pag
= xfs_perag_get(mp
, agno
);
2701 spin_lock(&pag
->pagb_lock
);
2703 rbp
= pag
->pagb_tree
.rb_node
;
2705 /* find closest start bno overlap */
2707 busyp
= rb_entry(rbp
, struct xfs_busy_extent
, rb_node
);
2708 if (bno
< busyp
->bno
) {
2709 /* may overlap, but exact start block is lower */
2710 if (bno
+ len
> busyp
->bno
)
2713 } else if (bno
> busyp
->bno
) {
2714 /* may overlap, but exact start block is higher */
2715 if (bno
< busyp
->bno
+ busyp
->length
)
2717 rbp
= rbp
->rb_right
;
2719 /* bno matches busyp, length determines exact match */
2720 match
= (busyp
->length
== len
) ? 1 : -1;
2724 spin_unlock(&pag
->pagb_lock
);
2725 trace_xfs_alloc_busysearch(mp
, agno
, bno
, len
, !!match
);
2731 xfs_alloc_busy_clear(
2732 struct xfs_mount
*mp
,
2733 struct xfs_busy_extent
*busyp
)
2735 struct xfs_perag
*pag
;
2737 trace_xfs_alloc_unbusy(mp
, busyp
->agno
, busyp
->bno
,
2740 ASSERT(xfs_alloc_busy_search(mp
, busyp
->agno
, busyp
->bno
,
2741 busyp
->length
) == 1);
2743 list_del_init(&busyp
->list
);
2745 pag
= xfs_perag_get(mp
, busyp
->agno
);
2746 spin_lock(&pag
->pagb_lock
);
2747 rb_erase(&busyp
->rb_node
, &pag
->pagb_tree
);
2748 spin_unlock(&pag
->pagb_lock
);