2 * Copyright (c) 2000-2002 Silicon Graphics, Inc. All Rights Reserved.
4 * This program is free software; you can redistribute it and/or modify it
5 * under the terms of version 2 of the GNU General Public License as
6 * published by the Free Software Foundation.
8 * This program is distributed in the hope that it would be useful, but
9 * WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
12 * Further, this software is distributed without any warranty that it is
13 * free of the rightful claim of any third person regarding infringement
14 * or the like. Any license provided herein, whether implied or
15 * otherwise, applies only to this software file. Patent licenses, if
16 * any, provided herein do not apply to combinations of this program with
17 * other software, or any other product whatsoever.
19 * You should have received a copy of the GNU General Public License along
20 * with this program; if not, write the Free Software Foundation, Inc., 59
21 * Temple Place - Suite 330, Boston MA 02111-1307, USA.
23 * Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy,
24 * Mountain View, CA 94043, or:
28 * For further information regarding this notice, see:
30 * http://oss.sgi.com/projects/GenInfo/SGIGPLNoticeExplan/
34 #include "xfs_types.h"
38 #include "xfs_trans.h"
43 #include "xfs_dmapi.h"
44 #include "xfs_mount.h"
45 #include "xfs_bmap_btree.h"
46 #include "xfs_alloc_btree.h"
47 #include "xfs_ialloc_btree.h"
48 #include "xfs_dir_sf.h"
49 #include "xfs_dir2_sf.h"
50 #include "xfs_attr_sf.h"
51 #include "xfs_dinode.h"
52 #include "xfs_inode.h"
53 #include "xfs_btree.h"
54 #include "xfs_ialloc.h"
55 #include "xfs_alloc.h"
56 #include "xfs_error.h"
59 #define XFS_ABSDIFF(a,b) (((a) <= (b)) ? ((b) - (a)) : ((a) - (b)))
61 #define XFSA_FIXUP_BNO_OK 1
62 #define XFSA_FIXUP_CNT_OK 2
65 xfs_alloc_search_busy(xfs_trans_t
*tp
,
70 #if defined(XFS_ALLOC_TRACE)
71 ktrace_t
*xfs_alloc_trace_buf
;
73 #define TRACE_ALLOC(s,a) \
74 xfs_alloc_trace_alloc(fname, s, a, __LINE__)
75 #define TRACE_FREE(s,a,b,x,f) \
76 xfs_alloc_trace_free(fname, s, mp, a, b, x, f, __LINE__)
77 #define TRACE_MODAGF(s,a,f) \
78 xfs_alloc_trace_modagf(fname, s, mp, a, f, __LINE__)
79 #define TRACE_BUSY(fname,s,ag,agb,l,sl,tp) \
80 xfs_alloc_trace_busy(fname, s, mp, ag, agb, l, sl, tp, XFS_ALLOC_KTRACE_BUSY, __LINE__)
81 #define TRACE_UNBUSY(fname,s,ag,sl,tp) \
82 xfs_alloc_trace_busy(fname, s, mp, ag, -1, -1, sl, tp, XFS_ALLOC_KTRACE_UNBUSY, __LINE__)
83 #define TRACE_BUSYSEARCH(fname,s,ag,agb,l,sl,tp) \
84 xfs_alloc_trace_busy(fname, s, mp, ag, agb, l, sl, tp, XFS_ALLOC_KTRACE_BUSYSEARCH, __LINE__)
86 #define TRACE_ALLOC(s,a)
87 #define TRACE_FREE(s,a,b,x,f)
88 #define TRACE_MODAGF(s,a,f)
89 #define TRACE_BUSY(s,a,ag,agb,l,sl,tp)
90 #define TRACE_UNBUSY(fname,s,ag,sl,tp)
91 #define TRACE_BUSYSEARCH(fname,s,ag,agb,l,sl,tp)
92 #endif /* XFS_ALLOC_TRACE */
95 * Prototypes for per-ag allocation routines
98 STATIC
int xfs_alloc_ag_vextent_exact(xfs_alloc_arg_t
*);
99 STATIC
int xfs_alloc_ag_vextent_near(xfs_alloc_arg_t
*);
100 STATIC
int xfs_alloc_ag_vextent_size(xfs_alloc_arg_t
*);
101 STATIC
int xfs_alloc_ag_vextent_small(xfs_alloc_arg_t
*,
102 xfs_btree_cur_t
*, xfs_agblock_t
*, xfs_extlen_t
*, int *);
105 * Internal functions.
109 * Compute aligned version of the found extent.
110 * Takes alignment and min length into account.
112 STATIC
int /* success (>= minlen) */
113 xfs_alloc_compute_aligned(
114 xfs_agblock_t foundbno
, /* starting block in found extent */
115 xfs_extlen_t foundlen
, /* length in found extent */
116 xfs_extlen_t alignment
, /* alignment for allocation */
117 xfs_extlen_t minlen
, /* minimum length for allocation */
118 xfs_agblock_t
*resbno
, /* result block number */
119 xfs_extlen_t
*reslen
) /* result length */
125 if (alignment
> 1 && foundlen
>= minlen
) {
126 bno
= roundup(foundbno
, alignment
);
127 diff
= bno
- foundbno
;
128 len
= diff
>= foundlen
? 0 : foundlen
- diff
;
135 return len
>= minlen
;
139 * Compute best start block and diff for "near" allocations.
140 * freelen >= wantlen already checked by caller.
142 STATIC xfs_extlen_t
/* difference value (absolute) */
143 xfs_alloc_compute_diff(
144 xfs_agblock_t wantbno
, /* target starting block */
145 xfs_extlen_t wantlen
, /* target length */
146 xfs_extlen_t alignment
, /* target alignment */
147 xfs_agblock_t freebno
, /* freespace's starting block */
148 xfs_extlen_t freelen
, /* freespace's length */
149 xfs_agblock_t
*newbnop
) /* result: best start block from free */
151 xfs_agblock_t freeend
; /* end of freespace extent */
152 xfs_agblock_t newbno1
; /* return block number */
153 xfs_agblock_t newbno2
; /* other new block number */
154 xfs_extlen_t newlen1
=0; /* length with newbno1 */
155 xfs_extlen_t newlen2
=0; /* length with newbno2 */
156 xfs_agblock_t wantend
; /* end of target extent */
158 ASSERT(freelen
>= wantlen
);
159 freeend
= freebno
+ freelen
;
160 wantend
= wantbno
+ wantlen
;
161 if (freebno
>= wantbno
) {
162 if ((newbno1
= roundup(freebno
, alignment
)) >= freeend
)
163 newbno1
= NULLAGBLOCK
;
164 } else if (freeend
>= wantend
&& alignment
> 1) {
165 newbno1
= roundup(wantbno
, alignment
);
166 newbno2
= newbno1
- alignment
;
167 if (newbno1
>= freeend
)
168 newbno1
= NULLAGBLOCK
;
170 newlen1
= XFS_EXTLEN_MIN(wantlen
, freeend
- newbno1
);
171 if (newbno2
< freebno
)
172 newbno2
= NULLAGBLOCK
;
174 newlen2
= XFS_EXTLEN_MIN(wantlen
, freeend
- newbno2
);
175 if (newbno1
!= NULLAGBLOCK
&& newbno2
!= NULLAGBLOCK
) {
176 if (newlen1
< newlen2
||
177 (newlen1
== newlen2
&&
178 XFS_ABSDIFF(newbno1
, wantbno
) >
179 XFS_ABSDIFF(newbno2
, wantbno
)))
181 } else if (newbno2
!= NULLAGBLOCK
)
183 } else if (freeend
>= wantend
) {
185 } else if (alignment
> 1) {
186 newbno1
= roundup(freeend
- wantlen
, alignment
);
187 if (newbno1
> freeend
- wantlen
&&
188 newbno1
- alignment
>= freebno
)
189 newbno1
-= alignment
;
190 else if (newbno1
>= freeend
)
191 newbno1
= NULLAGBLOCK
;
193 newbno1
= freeend
- wantlen
;
195 return newbno1
== NULLAGBLOCK
? 0 : XFS_ABSDIFF(newbno1
, wantbno
);
199 * Fix up the length, based on mod and prod.
200 * len should be k * prod + mod for some k.
201 * If len is too small it is returned unchanged.
202 * If len hits maxlen it is left alone.
206 xfs_alloc_arg_t
*args
) /* allocation argument structure */
211 ASSERT(args
->mod
< args
->prod
);
213 ASSERT(rlen
>= args
->minlen
);
214 ASSERT(rlen
<= args
->maxlen
);
215 if (args
->prod
<= 1 || rlen
< args
->mod
|| rlen
== args
->maxlen
||
216 (args
->mod
== 0 && rlen
< args
->prod
))
218 k
= rlen
% args
->prod
;
222 if ((int)(rlen
= rlen
- k
- args
->mod
) < (int)args
->minlen
)
225 if ((int)(rlen
= rlen
- args
->prod
- (args
->mod
- k
)) <
229 ASSERT(rlen
>= args
->minlen
);
230 ASSERT(rlen
<= args
->maxlen
);
235 * Fix up length if there is too little space left in the a.g.
236 * Return 1 if ok, 0 if too little, should give up.
239 xfs_alloc_fix_minleft(
240 xfs_alloc_arg_t
*args
) /* allocation argument structure */
242 xfs_agf_t
*agf
; /* a.g. freelist header */
243 int diff
; /* free space difference */
245 if (args
->minleft
== 0)
247 agf
= XFS_BUF_TO_AGF(args
->agbp
);
248 diff
= INT_GET(agf
->agf_freeblks
, ARCH_CONVERT
)
249 + INT_GET(agf
->agf_flcount
, ARCH_CONVERT
)
250 - args
->len
- args
->minleft
;
253 args
->len
+= diff
; /* shrink the allocated space */
254 if (args
->len
>= args
->minlen
)
256 args
->agbno
= NULLAGBLOCK
;
261 * Update the two btrees, logically removing from freespace the extent
262 * starting at rbno, rlen blocks. The extent is contained within the
263 * actual (current) free extent fbno for flen blocks.
264 * Flags are passed in indicating whether the cursors are set to the
267 STATIC
int /* error code */
268 xfs_alloc_fixup_trees(
269 xfs_btree_cur_t
*cnt_cur
, /* cursor for by-size btree */
270 xfs_btree_cur_t
*bno_cur
, /* cursor for by-block btree */
271 xfs_agblock_t fbno
, /* starting block of free extent */
272 xfs_extlen_t flen
, /* length of free extent */
273 xfs_agblock_t rbno
, /* starting block of returned extent */
274 xfs_extlen_t rlen
, /* length of returned extent */
275 int flags
) /* flags, XFSA_FIXUP_... */
277 int error
; /* error code */
278 int i
; /* operation results */
279 xfs_agblock_t nfbno1
; /* first new free startblock */
280 xfs_agblock_t nfbno2
; /* second new free startblock */
281 xfs_extlen_t nflen1
=0; /* first new free length */
282 xfs_extlen_t nflen2
=0; /* second new free length */
285 * Look up the record in the by-size tree if necessary.
287 if (flags
& XFSA_FIXUP_CNT_OK
) {
289 if ((error
= xfs_alloc_get_rec(cnt_cur
, &nfbno1
, &nflen1
, &i
)))
291 XFS_WANT_CORRUPTED_RETURN(
292 i
== 1 && nfbno1
== fbno
&& nflen1
== flen
);
295 if ((error
= xfs_alloc_lookup_eq(cnt_cur
, fbno
, flen
, &i
)))
297 XFS_WANT_CORRUPTED_RETURN(i
== 1);
300 * Look up the record in the by-block tree if necessary.
302 if (flags
& XFSA_FIXUP_BNO_OK
) {
304 if ((error
= xfs_alloc_get_rec(bno_cur
, &nfbno1
, &nflen1
, &i
)))
306 XFS_WANT_CORRUPTED_RETURN(
307 i
== 1 && nfbno1
== fbno
&& nflen1
== flen
);
310 if ((error
= xfs_alloc_lookup_eq(bno_cur
, fbno
, flen
, &i
)))
312 XFS_WANT_CORRUPTED_RETURN(i
== 1);
316 xfs_alloc_block_t
*bnoblock
;
317 xfs_alloc_block_t
*cntblock
;
319 if (bno_cur
->bc_nlevels
== 1 &&
320 cnt_cur
->bc_nlevels
== 1) {
321 bnoblock
= XFS_BUF_TO_ALLOC_BLOCK(bno_cur
->bc_bufs
[0]);
322 cntblock
= XFS_BUF_TO_ALLOC_BLOCK(cnt_cur
->bc_bufs
[0]);
323 XFS_WANT_CORRUPTED_RETURN(
324 INT_GET(bnoblock
->bb_numrecs
, ARCH_CONVERT
) == INT_GET(cntblock
->bb_numrecs
, ARCH_CONVERT
));
329 * Deal with all four cases: the allocated record is contained
330 * within the freespace record, so we can have new freespace
331 * at either (or both) end, or no freespace remaining.
333 if (rbno
== fbno
&& rlen
== flen
)
334 nfbno1
= nfbno2
= NULLAGBLOCK
;
335 else if (rbno
== fbno
) {
336 nfbno1
= rbno
+ rlen
;
337 nflen1
= flen
- rlen
;
338 nfbno2
= NULLAGBLOCK
;
339 } else if (rbno
+ rlen
== fbno
+ flen
) {
341 nflen1
= flen
- rlen
;
342 nfbno2
= NULLAGBLOCK
;
345 nflen1
= rbno
- fbno
;
346 nfbno2
= rbno
+ rlen
;
347 nflen2
= (fbno
+ flen
) - nfbno2
;
350 * Delete the entry from the by-size btree.
352 if ((error
= xfs_alloc_delete(cnt_cur
, &i
)))
354 XFS_WANT_CORRUPTED_RETURN(i
== 1);
356 * Add new by-size btree entry(s).
358 if (nfbno1
!= NULLAGBLOCK
) {
359 if ((error
= xfs_alloc_lookup_eq(cnt_cur
, nfbno1
, nflen1
, &i
)))
361 XFS_WANT_CORRUPTED_RETURN(i
== 0);
362 if ((error
= xfs_alloc_insert(cnt_cur
, &i
)))
364 XFS_WANT_CORRUPTED_RETURN(i
== 1);
366 if (nfbno2
!= NULLAGBLOCK
) {
367 if ((error
= xfs_alloc_lookup_eq(cnt_cur
, nfbno2
, nflen2
, &i
)))
369 XFS_WANT_CORRUPTED_RETURN(i
== 0);
370 if ((error
= xfs_alloc_insert(cnt_cur
, &i
)))
372 XFS_WANT_CORRUPTED_RETURN(i
== 1);
375 * Fix up the by-block btree entry(s).
377 if (nfbno1
== NULLAGBLOCK
) {
379 * No remaining freespace, just delete the by-block tree entry.
381 if ((error
= xfs_alloc_delete(bno_cur
, &i
)))
383 XFS_WANT_CORRUPTED_RETURN(i
== 1);
386 * Update the by-block entry to start later|be shorter.
388 if ((error
= xfs_alloc_update(bno_cur
, nfbno1
, nflen1
)))
391 if (nfbno2
!= NULLAGBLOCK
) {
393 * 2 resulting free entries, need to add one.
395 if ((error
= xfs_alloc_lookup_eq(bno_cur
, nfbno2
, nflen2
, &i
)))
397 XFS_WANT_CORRUPTED_RETURN(i
== 0);
398 if ((error
= xfs_alloc_insert(bno_cur
, &i
)))
400 XFS_WANT_CORRUPTED_RETURN(i
== 1);
406 * Read in the allocation group free block array.
408 STATIC
int /* error */
410 xfs_mount_t
*mp
, /* mount point structure */
411 xfs_trans_t
*tp
, /* transaction pointer */
412 xfs_agnumber_t agno
, /* allocation group number */
413 xfs_buf_t
**bpp
) /* buffer for the ag free block array */
415 xfs_buf_t
*bp
; /* return value */
418 ASSERT(agno
!= NULLAGNUMBER
);
419 error
= xfs_trans_read_buf(
420 mp
, tp
, mp
->m_ddev_targp
,
421 XFS_AG_DADDR(mp
, agno
, XFS_AGFL_DADDR(mp
)),
422 XFS_FSS_TO_BB(mp
, 1), 0, &bp
);
426 ASSERT(!XFS_BUF_GETERROR(bp
));
427 XFS_BUF_SET_VTYPE_REF(bp
, B_FS_AGFL
, XFS_AGFL_REF
);
432 #if defined(XFS_ALLOC_TRACE)
434 * Add an allocation trace entry for an alloc call.
437 xfs_alloc_trace_alloc(
438 char *name
, /* function tag string */
439 char *str
, /* additional string */
440 xfs_alloc_arg_t
*args
, /* allocation argument structure */
441 int line
) /* source line number */
443 ktrace_enter(xfs_alloc_trace_buf
,
444 (void *)(__psint_t
)(XFS_ALLOC_KTRACE_ALLOC
| (line
<< 16)),
448 (void *)(__psunsigned_t
)args
->agno
,
449 (void *)(__psunsigned_t
)args
->agbno
,
450 (void *)(__psunsigned_t
)args
->minlen
,
451 (void *)(__psunsigned_t
)args
->maxlen
,
452 (void *)(__psunsigned_t
)args
->mod
,
453 (void *)(__psunsigned_t
)args
->prod
,
454 (void *)(__psunsigned_t
)args
->minleft
,
455 (void *)(__psunsigned_t
)args
->total
,
456 (void *)(__psunsigned_t
)args
->alignment
,
457 (void *)(__psunsigned_t
)args
->len
,
458 (void *)((((__psint_t
)args
->type
) << 16) |
459 (__psint_t
)args
->otype
),
460 (void *)(__psint_t
)((args
->wasdel
<< 3) |
461 (args
->wasfromfl
<< 2) |
463 (args
->userdata
<< 0)));
467 * Add an allocation trace entry for a free call.
470 xfs_alloc_trace_free(
471 char *name
, /* function tag string */
472 char *str
, /* additional string */
473 xfs_mount_t
*mp
, /* file system mount point */
474 xfs_agnumber_t agno
, /* allocation group number */
475 xfs_agblock_t agbno
, /* a.g. relative block number */
476 xfs_extlen_t len
, /* length of extent */
477 int isfl
, /* set if is freelist allocation/free */
478 int line
) /* source line number */
480 ktrace_enter(xfs_alloc_trace_buf
,
481 (void *)(__psint_t
)(XFS_ALLOC_KTRACE_FREE
| (line
<< 16)),
485 (void *)(__psunsigned_t
)agno
,
486 (void *)(__psunsigned_t
)agbno
,
487 (void *)(__psunsigned_t
)len
,
488 (void *)(__psint_t
)isfl
,
489 NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
);
493 * Add an allocation trace entry for modifying an agf.
496 xfs_alloc_trace_modagf(
497 char *name
, /* function tag string */
498 char *str
, /* additional string */
499 xfs_mount_t
*mp
, /* file system mount point */
500 xfs_agf_t
*agf
, /* new agf value */
501 int flags
, /* logging flags for agf */
502 int line
) /* source line number */
504 ktrace_enter(xfs_alloc_trace_buf
,
505 (void *)(__psint_t
)(XFS_ALLOC_KTRACE_MODAGF
| (line
<< 16)),
509 (void *)(__psint_t
)flags
,
510 (void *)(__psunsigned_t
)INT_GET(agf
->agf_seqno
, ARCH_CONVERT
),
511 (void *)(__psunsigned_t
)INT_GET(agf
->agf_length
, ARCH_CONVERT
),
512 (void *)(__psunsigned_t
)INT_GET(agf
->agf_roots
[XFS_BTNUM_BNO
],
514 (void *)(__psunsigned_t
)INT_GET(agf
->agf_roots
[XFS_BTNUM_CNT
],
516 (void *)(__psunsigned_t
)INT_GET(agf
->agf_levels
[XFS_BTNUM_BNO
],
518 (void *)(__psunsigned_t
)INT_GET(agf
->agf_levels
[XFS_BTNUM_CNT
],
520 (void *)(__psunsigned_t
)INT_GET(agf
->agf_flfirst
, ARCH_CONVERT
),
521 (void *)(__psunsigned_t
)INT_GET(agf
->agf_fllast
, ARCH_CONVERT
),
522 (void *)(__psunsigned_t
)INT_GET(agf
->agf_flcount
, ARCH_CONVERT
),
523 (void *)(__psunsigned_t
)INT_GET(agf
->agf_freeblks
, ARCH_CONVERT
),
524 (void *)(__psunsigned_t
)INT_GET(agf
->agf_longest
, ARCH_CONVERT
));
528 xfs_alloc_trace_busy(
529 char *name
, /* function tag string */
530 char *str
, /* additional string */
531 xfs_mount_t
*mp
, /* file system mount poing */
532 xfs_agnumber_t agno
, /* allocation group number */
533 xfs_agblock_t agbno
, /* a.g. relative block number */
534 xfs_extlen_t len
, /* length of extent */
535 int slot
, /* perag Busy slot */
537 int trtype
, /* type: add, delete, search */
538 int line
) /* source line number */
540 ktrace_enter(xfs_alloc_trace_buf
,
541 (void *)(__psint_t
)(trtype
| (line
<< 16)),
545 (void *)(__psunsigned_t
)agno
,
546 (void *)(__psunsigned_t
)agbno
,
547 (void *)(__psunsigned_t
)len
,
548 (void *)(__psint_t
)slot
,
550 NULL
, NULL
, NULL
, NULL
, NULL
, NULL
, NULL
);
552 #endif /* XFS_ALLOC_TRACE */
555 * Allocation group level functions.
559 * Allocate a variable extent in the allocation group agno.
560 * Type and bno are used to determine where in the allocation group the
562 * Extent's length (returned in *len) will be between minlen and maxlen,
563 * and of the form k * prod + mod unless there's nothing that large.
564 * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
566 STATIC
int /* error */
567 xfs_alloc_ag_vextent(
568 xfs_alloc_arg_t
*args
) /* argument structure for allocation */
571 #ifdef XFS_ALLOC_TRACE
572 static char fname
[] = "xfs_alloc_ag_vextent";
575 ASSERT(args
->minlen
> 0);
576 ASSERT(args
->maxlen
> 0);
577 ASSERT(args
->minlen
<= args
->maxlen
);
578 ASSERT(args
->mod
< args
->prod
);
579 ASSERT(args
->alignment
> 0);
581 * Branch to correct routine based on the type.
584 switch (args
->type
) {
585 case XFS_ALLOCTYPE_THIS_AG
:
586 error
= xfs_alloc_ag_vextent_size(args
);
588 case XFS_ALLOCTYPE_NEAR_BNO
:
589 error
= xfs_alloc_ag_vextent_near(args
);
591 case XFS_ALLOCTYPE_THIS_BNO
:
592 error
= xfs_alloc_ag_vextent_exact(args
);
601 * If the allocation worked, need to change the agf structure
602 * (and log it), and the superblock.
604 if (args
->agbno
!= NULLAGBLOCK
) {
605 xfs_agf_t
*agf
; /* allocation group freelist header */
606 #ifdef XFS_ALLOC_TRACE
607 xfs_mount_t
*mp
= args
->mp
;
609 long slen
= (long)args
->len
;
611 ASSERT(args
->len
>= args
->minlen
&& args
->len
<= args
->maxlen
);
612 ASSERT(!(args
->wasfromfl
) || !args
->isfl
);
613 ASSERT(args
->agbno
% args
->alignment
== 0);
614 if (!(args
->wasfromfl
)) {
616 agf
= XFS_BUF_TO_AGF(args
->agbp
);
617 INT_MOD(agf
->agf_freeblks
, ARCH_CONVERT
, -(args
->len
));
618 xfs_trans_agblocks_delta(args
->tp
,
619 -((long)(args
->len
)));
620 args
->pag
->pagf_freeblks
-= args
->len
;
621 ASSERT(INT_GET(agf
->agf_freeblks
, ARCH_CONVERT
)
622 <= INT_GET(agf
->agf_length
, ARCH_CONVERT
));
623 TRACE_MODAGF(NULL
, agf
, XFS_AGF_FREEBLKS
);
624 xfs_alloc_log_agf(args
->tp
, args
->agbp
,
626 /* search the busylist for these blocks */
627 xfs_alloc_search_busy(args
->tp
, args
->agno
,
628 args
->agbno
, args
->len
);
631 xfs_trans_mod_sb(args
->tp
,
632 args
->wasdel
? XFS_TRANS_SB_RES_FDBLOCKS
:
633 XFS_TRANS_SB_FDBLOCKS
, -slen
);
634 XFS_STATS_INC(xs_allocx
);
635 XFS_STATS_ADD(xs_allocb
, args
->len
);
641 * Allocate a variable extent at exactly agno/bno.
642 * Extent's length (returned in *len) will be between minlen and maxlen,
643 * and of the form k * prod + mod unless there's nothing that large.
644 * Return the starting a.g. block (bno), or NULLAGBLOCK if we can't do it.
646 STATIC
int /* error */
647 xfs_alloc_ag_vextent_exact(
648 xfs_alloc_arg_t
*args
) /* allocation argument structure */
650 xfs_btree_cur_t
*bno_cur
;/* by block-number btree cursor */
651 xfs_btree_cur_t
*cnt_cur
;/* by count btree cursor */
652 xfs_agblock_t end
; /* end of allocated extent */
654 xfs_agblock_t fbno
; /* start block of found extent */
655 xfs_agblock_t fend
; /* end block of found extent */
656 xfs_extlen_t flen
; /* length of found extent */
657 #ifdef XFS_ALLOC_TRACE
658 static char fname
[] = "xfs_alloc_ag_vextent_exact";
660 int i
; /* success/failure of operation */
661 xfs_agblock_t maxend
; /* end of maximal extent */
662 xfs_agblock_t minend
; /* end of minimal extent */
663 xfs_extlen_t rlen
; /* length of returned extent */
665 ASSERT(args
->alignment
== 1);
667 * Allocate/initialize a cursor for the by-number freespace btree.
669 bno_cur
= xfs_btree_init_cursor(args
->mp
, args
->tp
, args
->agbp
,
670 args
->agno
, XFS_BTNUM_BNO
, NULL
, 0);
672 * Lookup bno and minlen in the btree (minlen is irrelevant, really).
673 * Look for the closest free block <= bno, it must contain bno
674 * if any free block does.
676 if ((error
= xfs_alloc_lookup_le(bno_cur
, args
->agbno
, args
->minlen
, &i
)))
680 * Didn't find it, return null.
682 xfs_btree_del_cursor(bno_cur
, XFS_BTREE_NOERROR
);
683 args
->agbno
= NULLAGBLOCK
;
687 * Grab the freespace record.
689 if ((error
= xfs_alloc_get_rec(bno_cur
, &fbno
, &flen
, &i
)))
691 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
692 ASSERT(fbno
<= args
->agbno
);
693 minend
= args
->agbno
+ args
->minlen
;
694 maxend
= args
->agbno
+ args
->maxlen
;
697 * Give up if the freespace isn't long enough for the minimum request.
700 xfs_btree_del_cursor(bno_cur
, XFS_BTREE_NOERROR
);
701 args
->agbno
= NULLAGBLOCK
;
705 * End of extent will be smaller of the freespace end and the
706 * maximal requested end.
708 end
= XFS_AGBLOCK_MIN(fend
, maxend
);
710 * Fix the length according to mod and prod if given.
712 args
->len
= end
- args
->agbno
;
713 xfs_alloc_fix_len(args
);
714 if (!xfs_alloc_fix_minleft(args
)) {
715 xfs_btree_del_cursor(bno_cur
, XFS_BTREE_NOERROR
);
719 ASSERT(args
->agbno
+ rlen
<= fend
);
720 end
= args
->agbno
+ rlen
;
722 * We are allocating agbno for rlen [agbno .. end]
723 * Allocate/initialize a cursor for the by-size btree.
725 cnt_cur
= xfs_btree_init_cursor(args
->mp
, args
->tp
, args
->agbp
,
726 args
->agno
, XFS_BTNUM_CNT
, NULL
, 0);
727 ASSERT(args
->agbno
+ args
->len
<=
728 INT_GET(XFS_BUF_TO_AGF(args
->agbp
)->agf_length
,
730 if ((error
= xfs_alloc_fixup_trees(cnt_cur
, bno_cur
, fbno
, flen
,
731 args
->agbno
, args
->len
, XFSA_FIXUP_BNO_OK
))) {
732 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_ERROR
);
735 xfs_btree_del_cursor(bno_cur
, XFS_BTREE_NOERROR
);
736 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_NOERROR
);
737 TRACE_ALLOC("normal", args
);
742 xfs_btree_del_cursor(bno_cur
, XFS_BTREE_ERROR
);
743 TRACE_ALLOC("error", args
);
748 * Allocate a variable extent near bno in the allocation group agno.
749 * Extent's length (returned in len) will be between minlen and maxlen,
750 * and of the form k * prod + mod unless there's nothing that large.
751 * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
753 STATIC
int /* error */
754 xfs_alloc_ag_vextent_near(
755 xfs_alloc_arg_t
*args
) /* allocation argument structure */
757 xfs_btree_cur_t
*bno_cur_gt
; /* cursor for bno btree, right side */
758 xfs_btree_cur_t
*bno_cur_lt
; /* cursor for bno btree, left side */
759 xfs_btree_cur_t
*cnt_cur
; /* cursor for count btree */
760 #ifdef XFS_ALLOC_TRACE
761 static char fname
[] = "xfs_alloc_ag_vextent_near";
763 xfs_agblock_t gtbno
; /* start bno of right side entry */
764 xfs_agblock_t gtbnoa
; /* aligned ... */
765 xfs_extlen_t gtdiff
; /* difference to right side entry */
766 xfs_extlen_t gtlen
; /* length of right side entry */
767 xfs_extlen_t gtlena
; /* aligned ... */
768 xfs_agblock_t gtnew
; /* useful start bno of right side */
769 int error
; /* error code */
770 int i
; /* result code, temporary */
771 int j
; /* result code, temporary */
772 xfs_agblock_t ltbno
; /* start bno of left side entry */
773 xfs_agblock_t ltbnoa
; /* aligned ... */
774 xfs_extlen_t ltdiff
; /* difference to left side entry */
776 xfs_agblock_t ltend
; /* end bno of left side entry */
777 xfs_extlen_t ltlen
; /* length of left side entry */
778 xfs_extlen_t ltlena
; /* aligned ... */
779 xfs_agblock_t ltnew
; /* useful start bno of left side */
780 xfs_extlen_t rlen
; /* length of returned extent */
781 #if defined(DEBUG) && defined(__KERNEL__)
783 * Randomly don't execute the first algorithm.
785 int dofirst
; /* set to do first algorithm */
787 dofirst
= random() & 1;
790 * Get a cursor for the by-size btree.
792 cnt_cur
= xfs_btree_init_cursor(args
->mp
, args
->tp
, args
->agbp
,
793 args
->agno
, XFS_BTNUM_CNT
, NULL
, 0);
795 bno_cur_lt
= bno_cur_gt
= NULL
;
797 * See if there are any free extents as big as maxlen.
799 if ((error
= xfs_alloc_lookup_ge(cnt_cur
, 0, args
->maxlen
, &i
)))
802 * If none, then pick up the last entry in the tree unless the
806 if ((error
= xfs_alloc_ag_vextent_small(args
, cnt_cur
, <bno
,
809 if (i
== 0 || ltlen
== 0) {
810 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_NOERROR
);
818 * If the requested extent is large wrt the freespaces available
819 * in this a.g., then the cursor will be pointing to a btree entry
820 * near the right edge of the tree. If it's in the last btree leaf
821 * block, then we just examine all the entries in that block
822 * that are big enough, and pick the best one.
823 * This is written as a while loop so we can break out of it,
824 * but we never loop back to the top.
826 while (xfs_btree_islastblock(cnt_cur
, 0)) {
830 xfs_agblock_t bnew
=0;
832 #if defined(DEBUG) && defined(__KERNEL__)
837 * Start from the entry that lookup found, sequence through
838 * all larger free blocks. If we're actually pointing at a
839 * record smaller than maxlen, go to the start of this block,
840 * and skip all those smaller than minlen.
842 if (ltlen
|| args
->alignment
> 1) {
843 cnt_cur
->bc_ptrs
[0] = 1;
845 if ((error
= xfs_alloc_get_rec(cnt_cur
, <bno
,
848 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
849 if (ltlen
>= args
->minlen
)
851 if ((error
= xfs_alloc_increment(cnt_cur
, 0, &i
)))
854 ASSERT(ltlen
>= args
->minlen
);
858 i
= cnt_cur
->bc_ptrs
[0];
859 for (j
= 1, blen
= 0, bdiff
= 0;
860 !error
&& j
&& (blen
< args
->maxlen
|| bdiff
> 0);
861 error
= xfs_alloc_increment(cnt_cur
, 0, &j
)) {
863 * For each entry, decide if it's better than
864 * the previous best entry.
866 if ((error
= xfs_alloc_get_rec(cnt_cur
, <bno
, <len
, &i
)))
868 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
869 if (!xfs_alloc_compute_aligned(ltbno
, ltlen
,
870 args
->alignment
, args
->minlen
,
873 args
->len
= XFS_EXTLEN_MIN(ltlena
, args
->maxlen
);
874 xfs_alloc_fix_len(args
);
875 ASSERT(args
->len
>= args
->minlen
);
876 if (args
->len
< blen
)
878 ltdiff
= xfs_alloc_compute_diff(args
->agbno
, args
->len
,
879 args
->alignment
, ltbno
, ltlen
, <new
);
880 if (ltnew
!= NULLAGBLOCK
&&
881 (args
->len
> blen
|| ltdiff
< bdiff
)) {
885 besti
= cnt_cur
->bc_ptrs
[0];
889 * It didn't work. We COULD be in a case where
890 * there's a good record somewhere, so try again.
895 * Point at the best entry, and retrieve it again.
897 cnt_cur
->bc_ptrs
[0] = besti
;
898 if ((error
= xfs_alloc_get_rec(cnt_cur
, <bno
, <len
, &i
)))
900 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
901 ltend
= ltbno
+ ltlen
;
902 ASSERT(ltend
<= INT_GET(XFS_BUF_TO_AGF(args
->agbp
)->agf_length
,
905 if (!xfs_alloc_fix_minleft(args
)) {
906 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_NOERROR
);
907 TRACE_ALLOC("nominleft", args
);
912 * We are allocating starting at bnew for blen blocks.
915 ASSERT(bnew
>= ltbno
);
916 ASSERT(bnew
+ blen
<= ltend
);
918 * Set up a cursor for the by-bno tree.
920 bno_cur_lt
= xfs_btree_init_cursor(args
->mp
, args
->tp
,
921 args
->agbp
, args
->agno
, XFS_BTNUM_BNO
, NULL
, 0);
923 * Fix up the btree entries.
925 if ((error
= xfs_alloc_fixup_trees(cnt_cur
, bno_cur_lt
, ltbno
,
926 ltlen
, bnew
, blen
, XFSA_FIXUP_CNT_OK
)))
928 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_NOERROR
);
929 xfs_btree_del_cursor(bno_cur_lt
, XFS_BTREE_NOERROR
);
930 TRACE_ALLOC("first", args
);
935 * Search in the by-bno tree to the left and to the right
936 * simultaneously, until in each case we find a space big enough,
937 * or run into the edge of the tree. When we run into the edge,
938 * we deallocate that cursor.
939 * If both searches succeed, we compare the two spaces and pick
941 * With alignment, it's possible for both to fail; the upper
942 * level algorithm that picks allocation groups for allocations
943 * is not supposed to do this.
946 * Allocate and initialize the cursor for the leftward search.
948 bno_cur_lt
= xfs_btree_init_cursor(args
->mp
, args
->tp
, args
->agbp
,
949 args
->agno
, XFS_BTNUM_BNO
, NULL
, 0);
951 * Lookup <= bno to find the leftward search's starting point.
953 if ((error
= xfs_alloc_lookup_le(bno_cur_lt
, args
->agbno
, args
->maxlen
, &i
)))
957 * Didn't find anything; use this cursor for the rightward
960 bno_cur_gt
= bno_cur_lt
;
964 * Found something. Duplicate the cursor for the rightward search.
966 else if ((error
= xfs_btree_dup_cursor(bno_cur_lt
, &bno_cur_gt
)))
969 * Increment the cursor, so we will point at the entry just right
970 * of the leftward entry if any, or to the leftmost entry.
972 if ((error
= xfs_alloc_increment(bno_cur_gt
, 0, &i
)))
976 * It failed, there are no rightward entries.
978 xfs_btree_del_cursor(bno_cur_gt
, XFS_BTREE_NOERROR
);
982 * Loop going left with the leftward cursor, right with the
983 * rightward cursor, until either both directions give up or
984 * we find an entry at least as big as minlen.
988 if ((error
= xfs_alloc_get_rec(bno_cur_lt
, <bno
, <len
, &i
)))
990 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
991 if (xfs_alloc_compute_aligned(ltbno
, ltlen
,
992 args
->alignment
, args
->minlen
,
995 if ((error
= xfs_alloc_decrement(bno_cur_lt
, 0, &i
)))
998 xfs_btree_del_cursor(bno_cur_lt
,
1004 if ((error
= xfs_alloc_get_rec(bno_cur_gt
, >bno
, >len
, &i
)))
1006 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
1007 if (xfs_alloc_compute_aligned(gtbno
, gtlen
,
1008 args
->alignment
, args
->minlen
,
1011 if ((error
= xfs_alloc_increment(bno_cur_gt
, 0, &i
)))
1014 xfs_btree_del_cursor(bno_cur_gt
,
1019 } while (bno_cur_lt
|| bno_cur_gt
);
1021 * Got both cursors still active, need to find better entry.
1023 if (bno_cur_lt
&& bno_cur_gt
) {
1025 * Left side is long enough, look for a right side entry.
1027 if (ltlena
>= args
->minlen
) {
1029 * Fix up the length.
1031 args
->len
= XFS_EXTLEN_MIN(ltlena
, args
->maxlen
);
1032 xfs_alloc_fix_len(args
);
1034 ltdiff
= xfs_alloc_compute_diff(args
->agbno
, rlen
,
1035 args
->alignment
, ltbno
, ltlen
, <new
);
1041 * Look until we find a better one, run out of
1042 * space, or run off the end.
1044 while (bno_cur_lt
&& bno_cur_gt
) {
1045 if ((error
= xfs_alloc_get_rec(
1049 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
1050 xfs_alloc_compute_aligned(gtbno
, gtlen
,
1051 args
->alignment
, args
->minlen
,
1054 * The left one is clearly better.
1056 if (gtbnoa
>= args
->agbno
+ ltdiff
) {
1057 xfs_btree_del_cursor(
1064 * If we reach a big enough entry,
1065 * compare the two and pick the best.
1067 if (gtlena
>= args
->minlen
) {
1069 XFS_EXTLEN_MIN(gtlena
,
1071 xfs_alloc_fix_len(args
);
1073 gtdiff
= xfs_alloc_compute_diff(
1076 gtbno
, gtlen
, >new
);
1078 * Right side is better.
1080 if (gtdiff
< ltdiff
) {
1081 xfs_btree_del_cursor(
1087 * Left side is better.
1090 xfs_btree_del_cursor(
1098 * Fell off the right end.
1100 if ((error
= xfs_alloc_increment(
1101 bno_cur_gt
, 0, &i
)))
1104 xfs_btree_del_cursor(
1113 * The left side is perfect, trash the right side.
1116 xfs_btree_del_cursor(bno_cur_gt
,
1122 * It's the right side that was found first, look left.
1126 * Fix up the length.
1128 args
->len
= XFS_EXTLEN_MIN(gtlena
, args
->maxlen
);
1129 xfs_alloc_fix_len(args
);
1131 gtdiff
= xfs_alloc_compute_diff(args
->agbno
, rlen
,
1132 args
->alignment
, gtbno
, gtlen
, >new
);
1134 * Right side entry isn't perfect.
1138 * Look until we find a better one, run out of
1139 * space, or run off the end.
1141 while (bno_cur_lt
&& bno_cur_gt
) {
1142 if ((error
= xfs_alloc_get_rec(
1146 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
1147 xfs_alloc_compute_aligned(ltbno
, ltlen
,
1148 args
->alignment
, args
->minlen
,
1151 * The right one is clearly better.
1153 if (ltbnoa
<= args
->agbno
- gtdiff
) {
1154 xfs_btree_del_cursor(
1161 * If we reach a big enough entry,
1162 * compare the two and pick the best.
1164 if (ltlena
>= args
->minlen
) {
1165 args
->len
= XFS_EXTLEN_MIN(
1166 ltlena
, args
->maxlen
);
1167 xfs_alloc_fix_len(args
);
1169 ltdiff
= xfs_alloc_compute_diff(
1172 ltbno
, ltlen
, <new
);
1174 * Left side is better.
1176 if (ltdiff
< gtdiff
) {
1177 xfs_btree_del_cursor(
1183 * Right side is better.
1186 xfs_btree_del_cursor(
1194 * Fell off the left end.
1196 if ((error
= xfs_alloc_decrement(
1197 bno_cur_lt
, 0, &i
)))
1200 xfs_btree_del_cursor(bno_cur_lt
,
1208 * The right side is perfect, trash the left side.
1211 xfs_btree_del_cursor(bno_cur_lt
,
1218 * If we couldn't get anything, give up.
1220 if (bno_cur_lt
== NULL
&& bno_cur_gt
== NULL
) {
1221 TRACE_ALLOC("neither", args
);
1222 args
->agbno
= NULLAGBLOCK
;
1226 * At this point we have selected a freespace entry, either to the
1227 * left or to the right. If it's on the right, copy all the
1228 * useful variables to the "left" set so we only have one
1229 * copy of this code.
1232 bno_cur_lt
= bno_cur_gt
;
1242 * Fix up the length and compute the useful address.
1244 ltend
= ltbno
+ ltlen
;
1245 args
->len
= XFS_EXTLEN_MIN(ltlena
, args
->maxlen
);
1246 xfs_alloc_fix_len(args
);
1247 if (!xfs_alloc_fix_minleft(args
)) {
1248 TRACE_ALLOC("nominleft", args
);
1249 xfs_btree_del_cursor(bno_cur_lt
, XFS_BTREE_NOERROR
);
1250 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_NOERROR
);
1254 (void)xfs_alloc_compute_diff(args
->agbno
, rlen
, args
->alignment
, ltbno
,
1256 ASSERT(ltnew
>= ltbno
);
1257 ASSERT(ltnew
+ rlen
<= ltend
);
1258 ASSERT(ltnew
+ rlen
<= INT_GET(XFS_BUF_TO_AGF(args
->agbp
)->agf_length
,
1260 args
->agbno
= ltnew
;
1261 if ((error
= xfs_alloc_fixup_trees(cnt_cur
, bno_cur_lt
, ltbno
, ltlen
,
1262 ltnew
, rlen
, XFSA_FIXUP_BNO_OK
)))
1264 TRACE_ALLOC(j
? "gt" : "lt", args
);
1265 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_NOERROR
);
1266 xfs_btree_del_cursor(bno_cur_lt
, XFS_BTREE_NOERROR
);
1270 TRACE_ALLOC("error", args
);
1271 if (cnt_cur
!= NULL
)
1272 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_ERROR
);
1273 if (bno_cur_lt
!= NULL
)
1274 xfs_btree_del_cursor(bno_cur_lt
, XFS_BTREE_ERROR
);
1275 if (bno_cur_gt
!= NULL
)
1276 xfs_btree_del_cursor(bno_cur_gt
, XFS_BTREE_ERROR
);
1281 * Allocate a variable extent anywhere in the allocation group agno.
1282 * Extent's length (returned in len) will be between minlen and maxlen,
1283 * and of the form k * prod + mod unless there's nothing that large.
1284 * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
1286 STATIC
int /* error */
1287 xfs_alloc_ag_vextent_size(
1288 xfs_alloc_arg_t
*args
) /* allocation argument structure */
1290 xfs_btree_cur_t
*bno_cur
; /* cursor for bno btree */
1291 xfs_btree_cur_t
*cnt_cur
; /* cursor for cnt btree */
1292 int error
; /* error result */
1293 xfs_agblock_t fbno
; /* start of found freespace */
1294 xfs_extlen_t flen
; /* length of found freespace */
1295 #ifdef XFS_ALLOC_TRACE
1296 static char fname
[] = "xfs_alloc_ag_vextent_size";
1298 int i
; /* temp status variable */
1299 xfs_agblock_t rbno
; /* returned block number */
1300 xfs_extlen_t rlen
; /* length of returned extent */
1303 * Allocate and initialize a cursor for the by-size btree.
1305 cnt_cur
= xfs_btree_init_cursor(args
->mp
, args
->tp
, args
->agbp
,
1306 args
->agno
, XFS_BTNUM_CNT
, NULL
, 0);
1309 * Look for an entry >= maxlen+alignment-1 blocks.
1311 if ((error
= xfs_alloc_lookup_ge(cnt_cur
, 0,
1312 args
->maxlen
+ args
->alignment
- 1, &i
)))
1315 * If none, then pick up the last entry in the tree unless the
1319 if ((error
= xfs_alloc_ag_vextent_small(args
, cnt_cur
, &fbno
,
1322 if (i
== 0 || flen
== 0) {
1323 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_NOERROR
);
1324 TRACE_ALLOC("noentry", args
);
1330 * There's a freespace as big as maxlen+alignment-1, get it.
1333 if ((error
= xfs_alloc_get_rec(cnt_cur
, &fbno
, &flen
, &i
)))
1335 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
1338 * In the first case above, we got the last entry in the
1339 * by-size btree. Now we check to see if the space hits maxlen
1340 * once aligned; if not, we search left for something better.
1341 * This can't happen in the second case above.
1343 xfs_alloc_compute_aligned(fbno
, flen
, args
->alignment
, args
->minlen
,
1345 rlen
= XFS_EXTLEN_MIN(args
->maxlen
, rlen
);
1346 XFS_WANT_CORRUPTED_GOTO(rlen
== 0 ||
1347 (rlen
<= flen
&& rbno
+ rlen
<= fbno
+ flen
), error0
);
1348 if (rlen
< args
->maxlen
) {
1349 xfs_agblock_t bestfbno
;
1350 xfs_extlen_t bestflen
;
1351 xfs_agblock_t bestrbno
;
1352 xfs_extlen_t bestrlen
;
1359 if ((error
= xfs_alloc_decrement(cnt_cur
, 0, &i
)))
1363 if ((error
= xfs_alloc_get_rec(cnt_cur
, &fbno
, &flen
,
1366 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
1367 if (flen
< bestrlen
)
1369 xfs_alloc_compute_aligned(fbno
, flen
, args
->alignment
,
1370 args
->minlen
, &rbno
, &rlen
);
1371 rlen
= XFS_EXTLEN_MIN(args
->maxlen
, rlen
);
1372 XFS_WANT_CORRUPTED_GOTO(rlen
== 0 ||
1373 (rlen
<= flen
&& rbno
+ rlen
<= fbno
+ flen
),
1375 if (rlen
> bestrlen
) {
1380 if (rlen
== args
->maxlen
)
1384 if ((error
= xfs_alloc_lookup_eq(cnt_cur
, bestfbno
, bestflen
,
1387 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
1393 args
->wasfromfl
= 0;
1395 * Fix up the length.
1398 xfs_alloc_fix_len(args
);
1399 if (rlen
< args
->minlen
|| !xfs_alloc_fix_minleft(args
)) {
1400 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_NOERROR
);
1401 TRACE_ALLOC("nominleft", args
);
1402 args
->agbno
= NULLAGBLOCK
;
1406 XFS_WANT_CORRUPTED_GOTO(rlen
<= flen
, error0
);
1408 * Allocate and initialize a cursor for the by-block tree.
1410 bno_cur
= xfs_btree_init_cursor(args
->mp
, args
->tp
, args
->agbp
,
1411 args
->agno
, XFS_BTNUM_BNO
, NULL
, 0);
1412 if ((error
= xfs_alloc_fixup_trees(cnt_cur
, bno_cur
, fbno
, flen
,
1413 rbno
, rlen
, XFSA_FIXUP_CNT_OK
)))
1415 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_NOERROR
);
1416 xfs_btree_del_cursor(bno_cur
, XFS_BTREE_NOERROR
);
1417 cnt_cur
= bno_cur
= NULL
;
1420 XFS_WANT_CORRUPTED_GOTO(
1421 args
->agbno
+ args
->len
<=
1422 INT_GET(XFS_BUF_TO_AGF(args
->agbp
)->agf_length
,
1425 TRACE_ALLOC("normal", args
);
1429 TRACE_ALLOC("error", args
);
1431 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_ERROR
);
1433 xfs_btree_del_cursor(bno_cur
, XFS_BTREE_ERROR
);
1438 * Deal with the case where only small freespaces remain.
1439 * Either return the contents of the last freespace record,
1440 * or allocate space from the freelist if there is nothing in the tree.
1442 STATIC
int /* error */
1443 xfs_alloc_ag_vextent_small(
1444 xfs_alloc_arg_t
*args
, /* allocation argument structure */
1445 xfs_btree_cur_t
*ccur
, /* by-size cursor */
1446 xfs_agblock_t
*fbnop
, /* result block number */
1447 xfs_extlen_t
*flenp
, /* result length */
1448 int *stat
) /* status: 0-freelist, 1-normal/none */
1453 #ifdef XFS_ALLOC_TRACE
1454 static char fname
[] = "xfs_alloc_ag_vextent_small";
1458 if ((error
= xfs_alloc_decrement(ccur
, 0, &i
)))
1461 if ((error
= xfs_alloc_get_rec(ccur
, &fbno
, &flen
, &i
)))
1463 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
1466 * Nothing in the btree, try the freelist. Make sure
1467 * to respect minleft even when pulling from the
1470 else if (args
->minlen
== 1 && args
->alignment
== 1 && !args
->isfl
&&
1471 (INT_GET(XFS_BUF_TO_AGF(args
->agbp
)->agf_flcount
,
1472 ARCH_CONVERT
) > args
->minleft
)) {
1473 if ((error
= xfs_alloc_get_freelist(args
->tp
, args
->agbp
, &fbno
)))
1475 if (fbno
!= NULLAGBLOCK
) {
1476 if (args
->userdata
) {
1479 bp
= xfs_btree_get_bufs(args
->mp
, args
->tp
,
1480 args
->agno
, fbno
, 0);
1481 xfs_trans_binval(args
->tp
, bp
);
1485 XFS_WANT_CORRUPTED_GOTO(
1486 args
->agbno
+ args
->len
<=
1487 INT_GET(XFS_BUF_TO_AGF(args
->agbp
)->agf_length
,
1490 args
->wasfromfl
= 1;
1491 TRACE_ALLOC("freelist", args
);
1496 * Nothing in the freelist.
1502 * Can't allocate from the freelist for some reason.
1507 * Can't do the allocation, give up.
1509 if (flen
< args
->minlen
) {
1510 args
->agbno
= NULLAGBLOCK
;
1511 TRACE_ALLOC("notenough", args
);
1517 TRACE_ALLOC("normal", args
);
1521 TRACE_ALLOC("error", args
);
1526 * Free the extent starting at agno/bno for length.
1528 STATIC
int /* error */
1530 xfs_trans_t
*tp
, /* transaction pointer */
1531 xfs_buf_t
*agbp
, /* buffer for a.g. freelist header */
1532 xfs_agnumber_t agno
, /* allocation group number */
1533 xfs_agblock_t bno
, /* starting block number */
1534 xfs_extlen_t len
, /* length of extent */
1535 int isfl
) /* set if is freelist blocks - no sb acctg */
1537 xfs_btree_cur_t
*bno_cur
; /* cursor for by-block btree */
1538 xfs_btree_cur_t
*cnt_cur
; /* cursor for by-size btree */
1539 int error
; /* error return value */
1540 #ifdef XFS_ALLOC_TRACE
1541 static char fname
[] = "xfs_free_ag_extent";
1543 xfs_agblock_t gtbno
; /* start of right neighbor block */
1544 xfs_extlen_t gtlen
; /* length of right neighbor block */
1545 int haveleft
; /* have a left neighbor block */
1546 int haveright
; /* have a right neighbor block */
1547 int i
; /* temp, result code */
1548 xfs_agblock_t ltbno
; /* start of left neighbor block */
1549 xfs_extlen_t ltlen
; /* length of left neighbor block */
1550 xfs_mount_t
*mp
; /* mount point struct for filesystem */
1551 xfs_agblock_t nbno
; /* new starting block of freespace */
1552 xfs_extlen_t nlen
; /* new length of freespace */
1556 * Allocate and initialize a cursor for the by-block btree.
1558 bno_cur
= xfs_btree_init_cursor(mp
, tp
, agbp
, agno
, XFS_BTNUM_BNO
, NULL
,
1562 * Look for a neighboring block on the left (lower block numbers)
1563 * that is contiguous with this space.
1565 if ((error
= xfs_alloc_lookup_le(bno_cur
, bno
, len
, &haveleft
)))
1569 * There is a block to our left.
1571 if ((error
= xfs_alloc_get_rec(bno_cur
, <bno
, <len
, &i
)))
1573 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
1575 * It's not contiguous, though.
1577 if (ltbno
+ ltlen
< bno
)
1581 * If this failure happens the request to free this
1582 * space was invalid, it's (partly) already free.
1585 XFS_WANT_CORRUPTED_GOTO(ltbno
+ ltlen
<= bno
, error0
);
1589 * Look for a neighboring block on the right (higher block numbers)
1590 * that is contiguous with this space.
1592 if ((error
= xfs_alloc_increment(bno_cur
, 0, &haveright
)))
1596 * There is a block to our right.
1598 if ((error
= xfs_alloc_get_rec(bno_cur
, >bno
, >len
, &i
)))
1600 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
1602 * It's not contiguous, though.
1604 if (bno
+ len
< gtbno
)
1608 * If this failure happens the request to free this
1609 * space was invalid, it's (partly) already free.
1612 XFS_WANT_CORRUPTED_GOTO(gtbno
>= bno
+ len
, error0
);
1616 * Now allocate and initialize a cursor for the by-size tree.
1618 cnt_cur
= xfs_btree_init_cursor(mp
, tp
, agbp
, agno
, XFS_BTNUM_CNT
, NULL
,
1621 * Have both left and right contiguous neighbors.
1622 * Merge all three into a single free block.
1624 if (haveleft
&& haveright
) {
1626 * Delete the old by-size entry on the left.
1628 if ((error
= xfs_alloc_lookup_eq(cnt_cur
, ltbno
, ltlen
, &i
)))
1630 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
1631 if ((error
= xfs_alloc_delete(cnt_cur
, &i
)))
1633 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
1635 * Delete the old by-size entry on the right.
1637 if ((error
= xfs_alloc_lookup_eq(cnt_cur
, gtbno
, gtlen
, &i
)))
1639 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
1640 if ((error
= xfs_alloc_delete(cnt_cur
, &i
)))
1642 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
1644 * Delete the old by-block entry for the right block.
1646 if ((error
= xfs_alloc_delete(bno_cur
, &i
)))
1648 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
1650 * Move the by-block cursor back to the left neighbor.
1652 if ((error
= xfs_alloc_decrement(bno_cur
, 0, &i
)))
1654 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
1657 * Check that this is the right record: delete didn't
1658 * mangle the cursor.
1661 xfs_agblock_t xxbno
;
1664 if ((error
= xfs_alloc_get_rec(bno_cur
, &xxbno
, &xxlen
,
1667 XFS_WANT_CORRUPTED_GOTO(
1668 i
== 1 && xxbno
== ltbno
&& xxlen
== ltlen
,
1673 * Update remaining by-block entry to the new, joined block.
1676 nlen
= len
+ ltlen
+ gtlen
;
1677 if ((error
= xfs_alloc_update(bno_cur
, nbno
, nlen
)))
1681 * Have only a left contiguous neighbor.
1682 * Merge it together with the new freespace.
1684 else if (haveleft
) {
1686 * Delete the old by-size entry on the left.
1688 if ((error
= xfs_alloc_lookup_eq(cnt_cur
, ltbno
, ltlen
, &i
)))
1690 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
1691 if ((error
= xfs_alloc_delete(cnt_cur
, &i
)))
1693 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
1695 * Back up the by-block cursor to the left neighbor, and
1696 * update its length.
1698 if ((error
= xfs_alloc_decrement(bno_cur
, 0, &i
)))
1700 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
1703 if ((error
= xfs_alloc_update(bno_cur
, nbno
, nlen
)))
1707 * Have only a right contiguous neighbor.
1708 * Merge it together with the new freespace.
1710 else if (haveright
) {
1712 * Delete the old by-size entry on the right.
1714 if ((error
= xfs_alloc_lookup_eq(cnt_cur
, gtbno
, gtlen
, &i
)))
1716 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
1717 if ((error
= xfs_alloc_delete(cnt_cur
, &i
)))
1719 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
1721 * Update the starting block and length of the right
1722 * neighbor in the by-block tree.
1726 if ((error
= xfs_alloc_update(bno_cur
, nbno
, nlen
)))
1730 * No contiguous neighbors.
1731 * Insert the new freespace into the by-block tree.
1736 if ((error
= xfs_alloc_insert(bno_cur
, &i
)))
1738 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
1740 xfs_btree_del_cursor(bno_cur
, XFS_BTREE_NOERROR
);
1743 * In all cases we need to insert the new freespace in the by-size tree.
1745 if ((error
= xfs_alloc_lookup_eq(cnt_cur
, nbno
, nlen
, &i
)))
1747 XFS_WANT_CORRUPTED_GOTO(i
== 0, error0
);
1748 if ((error
= xfs_alloc_insert(cnt_cur
, &i
)))
1750 XFS_WANT_CORRUPTED_GOTO(i
== 1, error0
);
1751 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_NOERROR
);
1754 * Update the freespace totals in the ag and superblock.
1758 xfs_perag_t
*pag
; /* per allocation group data */
1760 agf
= XFS_BUF_TO_AGF(agbp
);
1761 pag
= &mp
->m_perag
[agno
];
1762 INT_MOD(agf
->agf_freeblks
, ARCH_CONVERT
, len
);
1763 xfs_trans_agblocks_delta(tp
, len
);
1764 pag
->pagf_freeblks
+= len
;
1765 XFS_WANT_CORRUPTED_GOTO(
1766 INT_GET(agf
->agf_freeblks
, ARCH_CONVERT
)
1767 <= INT_GET(agf
->agf_length
, ARCH_CONVERT
),
1769 TRACE_MODAGF(NULL
, agf
, XFS_AGF_FREEBLKS
);
1770 xfs_alloc_log_agf(tp
, agbp
, XFS_AGF_FREEBLKS
);
1772 xfs_trans_mod_sb(tp
, XFS_TRANS_SB_FDBLOCKS
, (long)len
);
1773 XFS_STATS_INC(xs_freex
);
1774 XFS_STATS_ADD(xs_freeb
, len
);
1776 TRACE_FREE(haveleft
?
1777 (haveright
? "both" : "left") :
1778 (haveright
? "right" : "none"),
1779 agno
, bno
, len
, isfl
);
1782 * Since blocks move to the free list without the coordination
1783 * used in xfs_bmap_finish, we can't allow block to be available
1784 * for reallocation and non-transaction writing (user data)
1785 * until we know that the transaction that moved it to the free
1786 * list is permanently on disk. We track the blocks by declaring
1787 * these blocks as "busy"; the busy list is maintained on a per-ag
1788 * basis and each transaction records which entries should be removed
1789 * when the iclog commits to disk. If a busy block is allocated,
1790 * the iclog is pushed up to the LSN that freed the block.
1792 xfs_alloc_mark_busy(tp
, agno
, bno
, len
);
1796 TRACE_FREE("error", agno
, bno
, len
, isfl
);
1798 xfs_btree_del_cursor(bno_cur
, XFS_BTREE_ERROR
);
1800 xfs_btree_del_cursor(cnt_cur
, XFS_BTREE_ERROR
);
1805 * Visible (exported) allocation/free functions.
1806 * Some of these are used just by xfs_alloc_btree.c and this file.
1810 * Compute and fill in value of m_ag_maxlevels.
1813 xfs_alloc_compute_maxlevels(
1814 xfs_mount_t
*mp
) /* file system mount structure */
1822 maxleafents
= (mp
->m_sb
.sb_agblocks
+ 1) / 2;
1823 minleafrecs
= mp
->m_alloc_mnr
[0];
1824 minnoderecs
= mp
->m_alloc_mnr
[1];
1825 maxblocks
= (maxleafents
+ minleafrecs
- 1) / minleafrecs
;
1826 for (level
= 1; maxblocks
> 1; level
++)
1827 maxblocks
= (maxblocks
+ minnoderecs
- 1) / minnoderecs
;
1828 mp
->m_ag_maxlevels
= level
;
1832 * Decide whether to use this allocation group for this allocation.
1833 * If so, fix up the btree freelist's size.
1835 STATIC
int /* error */
1836 xfs_alloc_fix_freelist(
1837 xfs_alloc_arg_t
*args
, /* allocation argument structure */
1838 int flags
) /* XFS_ALLOC_FLAG_... */
1840 xfs_buf_t
*agbp
; /* agf buffer pointer */
1841 xfs_agf_t
*agf
; /* a.g. freespace structure pointer */
1842 xfs_buf_t
*agflbp
;/* agfl buffer pointer */
1843 xfs_agblock_t bno
; /* freelist block */
1844 xfs_extlen_t delta
; /* new blocks needed in freelist */
1845 int error
; /* error result code */
1846 xfs_extlen_t longest
;/* longest extent in allocation group */
1847 xfs_mount_t
*mp
; /* file system mount point structure */
1848 xfs_extlen_t need
; /* total blocks needed in freelist */
1849 xfs_perag_t
*pag
; /* per-ag information structure */
1850 xfs_alloc_arg_t targs
; /* local allocation arguments */
1851 xfs_trans_t
*tp
; /* transaction pointer */
1857 if (!pag
->pagf_init
) {
1858 if ((error
= xfs_alloc_read_agf(mp
, tp
, args
->agno
, flags
,
1861 if (!pag
->pagf_init
) {
1868 /* If this is a metadata prefered pag and we are user data
1869 * then try somewhere else if we are not being asked to
1870 * try harder at this point
1872 if (pag
->pagf_metadata
&& args
->userdata
&& flags
) {
1877 need
= XFS_MIN_FREELIST_PAG(pag
, mp
);
1878 delta
= need
> pag
->pagf_flcount
? need
- pag
->pagf_flcount
: 0;
1880 * If it looks like there isn't a long enough extent, or enough
1881 * total blocks, reject it.
1883 longest
= (pag
->pagf_longest
> delta
) ?
1884 (pag
->pagf_longest
- delta
) :
1885 (pag
->pagf_flcount
> 0 || pag
->pagf_longest
> 0);
1886 if (args
->minlen
+ args
->alignment
+ args
->minalignslop
- 1 > longest
||
1888 (int)(pag
->pagf_freeblks
+ pag
->pagf_flcount
-
1889 need
- args
->total
) <
1890 (int)args
->minleft
)) {
1892 xfs_trans_brelse(tp
, agbp
);
1897 * Get the a.g. freespace buffer.
1898 * Can fail if we're not blocking on locks, and it's held.
1901 if ((error
= xfs_alloc_read_agf(mp
, tp
, args
->agno
, flags
,
1910 * Figure out how many blocks we should have in the freelist.
1912 agf
= XFS_BUF_TO_AGF(agbp
);
1913 need
= XFS_MIN_FREELIST(agf
, mp
);
1914 delta
= need
> INT_GET(agf
->agf_flcount
, ARCH_CONVERT
) ?
1915 (need
- INT_GET(agf
->agf_flcount
, ARCH_CONVERT
)) : 0;
1917 * If there isn't enough total or single-extent, reject it.
1919 longest
= INT_GET(agf
->agf_longest
, ARCH_CONVERT
);
1920 longest
= (longest
> delta
) ? (longest
- delta
) :
1921 (INT_GET(agf
->agf_flcount
, ARCH_CONVERT
) > 0 || longest
> 0);
1922 if (args
->minlen
+ args
->alignment
+ args
->minalignslop
- 1 > longest
||
1924 (int)(INT_GET(agf
->agf_freeblks
, ARCH_CONVERT
) +
1925 INT_GET(agf
->agf_flcount
, ARCH_CONVERT
) - need
- args
->total
) <
1926 (int)args
->minleft
)) {
1927 xfs_trans_brelse(tp
, agbp
);
1932 * Make the freelist shorter if it's too long.
1934 while (INT_GET(agf
->agf_flcount
, ARCH_CONVERT
) > need
) {
1937 if ((error
= xfs_alloc_get_freelist(tp
, agbp
, &bno
)))
1939 if ((error
= xfs_free_ag_extent(tp
, agbp
, args
->agno
, bno
, 1, 1)))
1941 bp
= xfs_btree_get_bufs(mp
, tp
, args
->agno
, bno
, 0);
1942 xfs_trans_binval(tp
, bp
);
1945 * Initialize the args structure.
1950 targs
.agno
= args
->agno
;
1951 targs
.mod
= targs
.minleft
= targs
.wasdel
= targs
.userdata
=
1952 targs
.minalignslop
= 0;
1953 targs
.alignment
= targs
.minlen
= targs
.prod
= targs
.isfl
= 1;
1954 targs
.type
= XFS_ALLOCTYPE_THIS_AG
;
1956 if ((error
= xfs_alloc_read_agfl(mp
, tp
, targs
.agno
, &agflbp
)))
1959 * Make the freelist longer if it's too short.
1961 while (INT_GET(agf
->agf_flcount
, ARCH_CONVERT
) < need
) {
1963 targs
.maxlen
= need
- INT_GET(agf
->agf_flcount
, ARCH_CONVERT
);
1965 * Allocate as many blocks as possible at once.
1967 if ((error
= xfs_alloc_ag_vextent(&targs
)))
1970 * Stop if we run out. Won't happen if callers are obeying
1971 * the restrictions correctly. Can happen for free calls
1972 * on a completely full ag.
1974 if (targs
.agbno
== NULLAGBLOCK
)
1977 * Put each allocated block on the list.
1979 for (bno
= targs
.agbno
; bno
< targs
.agbno
+ targs
.len
; bno
++) {
1980 if ((error
= xfs_alloc_put_freelist(tp
, agbp
, agflbp
,
1990 * Get a block from the freelist.
1991 * Returns with the buffer for the block gotten.
1994 xfs_alloc_get_freelist(
1995 xfs_trans_t
*tp
, /* transaction pointer */
1996 xfs_buf_t
*agbp
, /* buffer containing the agf structure */
1997 xfs_agblock_t
*bnop
) /* block address retrieved from freelist */
1999 xfs_agf_t
*agf
; /* a.g. freespace structure */
2000 xfs_agfl_t
*agfl
; /* a.g. freelist structure */
2001 xfs_buf_t
*agflbp
;/* buffer for a.g. freelist structure */
2002 xfs_agblock_t bno
; /* block number returned */
2004 #ifdef XFS_ALLOC_TRACE
2005 static char fname
[] = "xfs_alloc_get_freelist";
2007 xfs_mount_t
*mp
; /* mount structure */
2008 xfs_perag_t
*pag
; /* per allocation group data */
2010 agf
= XFS_BUF_TO_AGF(agbp
);
2012 * Freelist is empty, give up.
2014 if (!agf
->agf_flcount
) {
2015 *bnop
= NULLAGBLOCK
;
2019 * Read the array of free blocks.
2022 if ((error
= xfs_alloc_read_agfl(mp
, tp
,
2023 INT_GET(agf
->agf_seqno
, ARCH_CONVERT
), &agflbp
)))
2025 agfl
= XFS_BUF_TO_AGFL(agflbp
);
2027 * Get the block number and update the data structures.
2029 bno
= INT_GET(agfl
->agfl_bno
[INT_GET(agf
->agf_flfirst
, ARCH_CONVERT
)], ARCH_CONVERT
);
2030 INT_MOD(agf
->agf_flfirst
, ARCH_CONVERT
, 1);
2031 xfs_trans_brelse(tp
, agflbp
);
2032 if (INT_GET(agf
->agf_flfirst
, ARCH_CONVERT
) == XFS_AGFL_SIZE(mp
))
2033 agf
->agf_flfirst
= 0;
2034 pag
= &mp
->m_perag
[INT_GET(agf
->agf_seqno
, ARCH_CONVERT
)];
2035 INT_MOD(agf
->agf_flcount
, ARCH_CONVERT
, -1);
2036 xfs_trans_agflist_delta(tp
, -1);
2037 pag
->pagf_flcount
--;
2038 TRACE_MODAGF(NULL
, agf
, XFS_AGF_FLFIRST
| XFS_AGF_FLCOUNT
);
2039 xfs_alloc_log_agf(tp
, agbp
, XFS_AGF_FLFIRST
| XFS_AGF_FLCOUNT
);
2043 * As blocks are freed, they are added to the per-ag busy list
2044 * and remain there until the freeing transaction is committed to
2045 * disk. Now that we have allocated blocks, this list must be
2046 * searched to see if a block is being reused. If one is, then
2047 * the freeing transaction must be pushed to disk NOW by forcing
2048 * to disk all iclogs up that transaction's LSN.
2050 xfs_alloc_search_busy(tp
, INT_GET(agf
->agf_seqno
, ARCH_CONVERT
), bno
, 1);
2055 * Log the given fields from the agf structure.
2059 xfs_trans_t
*tp
, /* transaction pointer */
2060 xfs_buf_t
*bp
, /* buffer for a.g. freelist header */
2061 int fields
) /* mask of fields to be logged (XFS_AGF_...) */
2063 int first
; /* first byte offset */
2064 int last
; /* last byte offset */
2065 static const short offsets
[] = {
2066 offsetof(xfs_agf_t
, agf_magicnum
),
2067 offsetof(xfs_agf_t
, agf_versionnum
),
2068 offsetof(xfs_agf_t
, agf_seqno
),
2069 offsetof(xfs_agf_t
, agf_length
),
2070 offsetof(xfs_agf_t
, agf_roots
[0]),
2071 offsetof(xfs_agf_t
, agf_levels
[0]),
2072 offsetof(xfs_agf_t
, agf_flfirst
),
2073 offsetof(xfs_agf_t
, agf_fllast
),
2074 offsetof(xfs_agf_t
, agf_flcount
),
2075 offsetof(xfs_agf_t
, agf_freeblks
),
2076 offsetof(xfs_agf_t
, agf_longest
),
2080 xfs_btree_offsets(fields
, offsets
, XFS_AGF_NUM_BITS
, &first
, &last
);
2081 xfs_trans_log_buf(tp
, bp
, (uint
)first
, (uint
)last
);
2085 * Interface for inode allocation to force the pag data to be initialized.
2088 xfs_alloc_pagf_init(
2089 xfs_mount_t
*mp
, /* file system mount structure */
2090 xfs_trans_t
*tp
, /* transaction pointer */
2091 xfs_agnumber_t agno
, /* allocation group number */
2092 int flags
) /* XFS_ALLOC_FLAGS_... */
2097 if ((error
= xfs_alloc_read_agf(mp
, tp
, agno
, flags
, &bp
)))
2100 xfs_trans_brelse(tp
, bp
);
2105 * Put the block on the freelist for the allocation group.
2108 xfs_alloc_put_freelist(
2109 xfs_trans_t
*tp
, /* transaction pointer */
2110 xfs_buf_t
*agbp
, /* buffer for a.g. freelist header */
2111 xfs_buf_t
*agflbp
,/* buffer for a.g. free block array */
2112 xfs_agblock_t bno
) /* block being freed */
2114 xfs_agf_t
*agf
; /* a.g. freespace structure */
2115 xfs_agfl_t
*agfl
; /* a.g. free block array */
2116 xfs_agblock_t
*blockp
;/* pointer to array entry */
2118 #ifdef XFS_ALLOC_TRACE
2119 static char fname
[] = "xfs_alloc_put_freelist";
2121 xfs_mount_t
*mp
; /* mount structure */
2122 xfs_perag_t
*pag
; /* per allocation group data */
2124 agf
= XFS_BUF_TO_AGF(agbp
);
2127 if (!agflbp
&& (error
= xfs_alloc_read_agfl(mp
, tp
,
2128 INT_GET(agf
->agf_seqno
, ARCH_CONVERT
), &agflbp
)))
2130 agfl
= XFS_BUF_TO_AGFL(agflbp
);
2131 INT_MOD(agf
->agf_fllast
, ARCH_CONVERT
, 1);
2132 if (INT_GET(agf
->agf_fllast
, ARCH_CONVERT
) == XFS_AGFL_SIZE(mp
))
2133 agf
->agf_fllast
= 0;
2134 pag
= &mp
->m_perag
[INT_GET(agf
->agf_seqno
, ARCH_CONVERT
)];
2135 INT_MOD(agf
->agf_flcount
, ARCH_CONVERT
, 1);
2136 xfs_trans_agflist_delta(tp
, 1);
2137 pag
->pagf_flcount
++;
2138 ASSERT(INT_GET(agf
->agf_flcount
, ARCH_CONVERT
) <= XFS_AGFL_SIZE(mp
));
2139 blockp
= &agfl
->agfl_bno
[INT_GET(agf
->agf_fllast
, ARCH_CONVERT
)];
2140 INT_SET(*blockp
, ARCH_CONVERT
, bno
);
2141 TRACE_MODAGF(NULL
, agf
, XFS_AGF_FLLAST
| XFS_AGF_FLCOUNT
);
2142 xfs_alloc_log_agf(tp
, agbp
, XFS_AGF_FLLAST
| XFS_AGF_FLCOUNT
);
2143 xfs_trans_log_buf(tp
, agflbp
,
2144 (int)((xfs_caddr_t
)blockp
- (xfs_caddr_t
)agfl
),
2145 (int)((xfs_caddr_t
)blockp
- (xfs_caddr_t
)agfl
+
2146 sizeof(xfs_agblock_t
) - 1));
2151 * Read in the allocation group header (free/alloc section).
2155 xfs_mount_t
*mp
, /* mount point structure */
2156 xfs_trans_t
*tp
, /* transaction pointer */
2157 xfs_agnumber_t agno
, /* allocation group number */
2158 int flags
, /* XFS_ALLOC_FLAG_... */
2159 xfs_buf_t
**bpp
) /* buffer for the ag freelist header */
2161 xfs_agf_t
*agf
; /* ag freelist header */
2162 int agf_ok
; /* set if agf is consistent */
2163 xfs_buf_t
*bp
; /* return value */
2164 xfs_perag_t
*pag
; /* per allocation group data */
2167 ASSERT(agno
!= NULLAGNUMBER
);
2168 error
= xfs_trans_read_buf(
2169 mp
, tp
, mp
->m_ddev_targp
,
2170 XFS_AG_DADDR(mp
, agno
, XFS_AGF_DADDR(mp
)),
2171 XFS_FSS_TO_BB(mp
, 1),
2172 (flags
& XFS_ALLOC_FLAG_TRYLOCK
) ? XFS_BUF_TRYLOCK
: 0U,
2176 ASSERT(!bp
|| !XFS_BUF_GETERROR(bp
));
2182 * Validate the magic number of the agf block.
2184 agf
= XFS_BUF_TO_AGF(bp
);
2186 INT_GET(agf
->agf_magicnum
, ARCH_CONVERT
) == XFS_AGF_MAGIC
&&
2187 XFS_AGF_GOOD_VERSION(
2188 INT_GET(agf
->agf_versionnum
, ARCH_CONVERT
)) &&
2189 INT_GET(agf
->agf_freeblks
, ARCH_CONVERT
) <=
2190 INT_GET(agf
->agf_length
, ARCH_CONVERT
) &&
2191 INT_GET(agf
->agf_flfirst
, ARCH_CONVERT
) < XFS_AGFL_SIZE(mp
) &&
2192 INT_GET(agf
->agf_fllast
, ARCH_CONVERT
) < XFS_AGFL_SIZE(mp
) &&
2193 INT_GET(agf
->agf_flcount
, ARCH_CONVERT
) <= XFS_AGFL_SIZE(mp
);
2194 if (unlikely(XFS_TEST_ERROR(!agf_ok
, mp
, XFS_ERRTAG_ALLOC_READ_AGF
,
2195 XFS_RANDOM_ALLOC_READ_AGF
))) {
2196 XFS_CORRUPTION_ERROR("xfs_alloc_read_agf",
2197 XFS_ERRLEVEL_LOW
, mp
, agf
);
2198 xfs_trans_brelse(tp
, bp
);
2199 return XFS_ERROR(EFSCORRUPTED
);
2201 pag
= &mp
->m_perag
[agno
];
2202 if (!pag
->pagf_init
) {
2203 pag
->pagf_freeblks
= INT_GET(agf
->agf_freeblks
, ARCH_CONVERT
);
2204 pag
->pagf_flcount
= INT_GET(agf
->agf_flcount
, ARCH_CONVERT
);
2205 pag
->pagf_longest
= INT_GET(agf
->agf_longest
, ARCH_CONVERT
);
2206 pag
->pagf_levels
[XFS_BTNUM_BNOi
] =
2207 INT_GET(agf
->agf_levels
[XFS_BTNUM_BNOi
], ARCH_CONVERT
);
2208 pag
->pagf_levels
[XFS_BTNUM_CNTi
] =
2209 INT_GET(agf
->agf_levels
[XFS_BTNUM_CNTi
], ARCH_CONVERT
);
2210 spinlock_init(&pag
->pagb_lock
, "xfspagb");
2211 pag
->pagb_list
= kmem_zalloc(XFS_PAGB_NUM_SLOTS
*
2212 sizeof(xfs_perag_busy_t
), KM_SLEEP
);
2216 else if (!XFS_FORCED_SHUTDOWN(mp
)) {
2217 ASSERT(pag
->pagf_freeblks
== INT_GET(agf
->agf_freeblks
, ARCH_CONVERT
));
2218 ASSERT(pag
->pagf_flcount
== INT_GET(agf
->agf_flcount
, ARCH_CONVERT
));
2219 ASSERT(pag
->pagf_longest
== INT_GET(agf
->agf_longest
, ARCH_CONVERT
));
2220 ASSERT(pag
->pagf_levels
[XFS_BTNUM_BNOi
] ==
2221 INT_GET(agf
->agf_levels
[XFS_BTNUM_BNOi
], ARCH_CONVERT
));
2222 ASSERT(pag
->pagf_levels
[XFS_BTNUM_CNTi
] ==
2223 INT_GET(agf
->agf_levels
[XFS_BTNUM_CNTi
], ARCH_CONVERT
));
2226 XFS_BUF_SET_VTYPE_REF(bp
, B_FS_AGF
, XFS_AGF_REF
);
2232 * Allocate an extent (variable-size).
2233 * Depending on the allocation type, we either look in a single allocation
2234 * group or loop over the allocation groups to find the result.
2238 xfs_alloc_arg_t
*args
) /* allocation argument structure */
2240 xfs_agblock_t agsize
; /* allocation group size */
2242 int flags
; /* XFS_ALLOC_FLAG_... locking flags */
2243 #ifdef XFS_ALLOC_TRACE
2244 static char fname
[] = "xfs_alloc_vextent";
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_ALLOC("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 down_read(&mp
->m_peraglock
);
2291 args
->pag
= &mp
->m_perag
[args
->agno
];
2293 error
= xfs_alloc_fix_freelist(args
, 0);
2294 args
->minleft
= minleft
;
2296 TRACE_ALLOC("nofix", args
);
2300 up_read(&mp
->m_peraglock
);
2301 TRACE_ALLOC("noagbp", args
);
2304 args
->agbno
= XFS_FSB_TO_AGBNO(mp
, args
->fsbno
);
2305 if ((error
= xfs_alloc_ag_vextent(args
)))
2307 up_read(&mp
->m_peraglock
);
2309 case XFS_ALLOCTYPE_START_BNO
:
2311 * Try near allocation first, then anywhere-in-ag after
2312 * the first a.g. fails.
2314 if ((args
->userdata
== XFS_ALLOC_INITIAL_USER_DATA
) &&
2315 (mp
->m_flags
& XFS_MOUNT_32BITINODES
)) {
2316 args
->fsbno
= XFS_AGB_TO_FSB(mp
,
2317 ((mp
->m_agfrotor
/ rotorstep
) %
2318 mp
->m_sb
.sb_agcount
), 0);
2321 args
->agbno
= XFS_FSB_TO_AGBNO(mp
, args
->fsbno
);
2322 args
->type
= XFS_ALLOCTYPE_NEAR_BNO
;
2324 case XFS_ALLOCTYPE_ANY_AG
:
2325 case XFS_ALLOCTYPE_START_AG
:
2326 case XFS_ALLOCTYPE_FIRST_AG
:
2328 * Rotate through the allocation groups looking for a winner.
2330 if (type
== XFS_ALLOCTYPE_ANY_AG
) {
2332 * Start with the last place we left off.
2334 args
->agno
= sagno
= (mp
->m_agfrotor
/ rotorstep
) %
2335 mp
->m_sb
.sb_agcount
;
2336 args
->type
= XFS_ALLOCTYPE_THIS_AG
;
2337 flags
= XFS_ALLOC_FLAG_TRYLOCK
;
2338 } else if (type
== XFS_ALLOCTYPE_FIRST_AG
) {
2340 * Start with allocation group given by bno.
2342 args
->agno
= XFS_FSB_TO_AGNO(mp
, args
->fsbno
);
2343 args
->type
= XFS_ALLOCTYPE_THIS_AG
;
2347 if (type
== XFS_ALLOCTYPE_START_AG
)
2348 args
->type
= XFS_ALLOCTYPE_THIS_AG
;
2350 * Start with the given allocation group.
2352 args
->agno
= sagno
= XFS_FSB_TO_AGNO(mp
, args
->fsbno
);
2353 flags
= XFS_ALLOC_FLAG_TRYLOCK
;
2356 * Loop over allocation groups twice; first time with
2357 * trylock set, second time without.
2359 down_read(&mp
->m_peraglock
);
2361 args
->pag
= &mp
->m_perag
[args
->agno
];
2362 if (no_min
) args
->minleft
= 0;
2363 error
= xfs_alloc_fix_freelist(args
, flags
);
2364 args
->minleft
= minleft
;
2366 TRACE_ALLOC("nofix", args
);
2370 * If we get a buffer back then the allocation will fly.
2373 if ((error
= xfs_alloc_ag_vextent(args
)))
2377 TRACE_ALLOC("loopfailed", args
);
2379 * Didn't work, figure out the next iteration.
2381 if (args
->agno
== sagno
&&
2382 type
== XFS_ALLOCTYPE_START_BNO
)
2383 args
->type
= XFS_ALLOCTYPE_THIS_AG
;
2384 if (++(args
->agno
) == mp
->m_sb
.sb_agcount
)
2387 * Reached the starting a.g., must either be done
2388 * or switch to non-trylock mode.
2390 if (args
->agno
== sagno
) {
2392 args
->agbno
= NULLAGBLOCK
;
2393 TRACE_ALLOC("allfailed", args
);
2400 if (type
== XFS_ALLOCTYPE_START_BNO
) {
2401 args
->agbno
= XFS_FSB_TO_AGBNO(mp
,
2403 args
->type
= XFS_ALLOCTYPE_NEAR_BNO
;
2408 up_read(&mp
->m_peraglock
);
2409 if (bump_rotor
|| (type
== XFS_ALLOCTYPE_ANY_AG
)) {
2410 if (args
->agno
== sagno
)
2411 mp
->m_agfrotor
= (mp
->m_agfrotor
+ 1) %
2412 (mp
->m_sb
.sb_agcount
* rotorstep
);
2414 mp
->m_agfrotor
= (args
->agno
* rotorstep
+ 1) %
2415 (mp
->m_sb
.sb_agcount
* rotorstep
);
2422 if (args
->agbno
== NULLAGBLOCK
)
2423 args
->fsbno
= NULLFSBLOCK
;
2425 args
->fsbno
= XFS_AGB_TO_FSB(mp
, args
->agno
, args
->agbno
);
2427 ASSERT(args
->len
>= args
->minlen
);
2428 ASSERT(args
->len
<= args
->maxlen
);
2429 ASSERT(args
->agbno
% args
->alignment
== 0);
2430 XFS_AG_CHECK_DADDR(mp
, XFS_FSB_TO_DADDR(mp
, args
->fsbno
),
2436 up_read(&mp
->m_peraglock
);
2442 * Just break up the extent address and hand off to xfs_free_ag_extent
2443 * after fixing up the freelist.
2447 xfs_trans_t
*tp
, /* transaction pointer */
2448 xfs_fsblock_t bno
, /* starting block number of extent */
2449 xfs_extlen_t len
) /* length of extent */
2452 xfs_agf_t
*agf
; /* a.g. freespace header */
2454 xfs_alloc_arg_t args
; /* allocation argument structure */
2459 args
.mp
= tp
->t_mountp
;
2460 args
.agno
= XFS_FSB_TO_AGNO(args
.mp
, bno
);
2461 ASSERT(args
.agno
< args
.mp
->m_sb
.sb_agcount
);
2462 args
.agbno
= XFS_FSB_TO_AGBNO(args
.mp
, bno
);
2464 args
.minlen
= args
.minleft
= args
.minalignslop
= 0;
2465 down_read(&args
.mp
->m_peraglock
);
2466 args
.pag
= &args
.mp
->m_perag
[args
.agno
];
2467 if ((error
= xfs_alloc_fix_freelist(&args
, 0)))
2470 ASSERT(args
.agbp
!= NULL
);
2471 agf
= XFS_BUF_TO_AGF(args
.agbp
);
2472 ASSERT(args
.agbno
+ len
<= INT_GET(agf
->agf_length
, ARCH_CONVERT
));
2474 error
= xfs_free_ag_extent(tp
, args
.agbp
, args
.agno
, args
.agbno
,
2477 up_read(&args
.mp
->m_peraglock
);
2483 * AG Busy list management
2484 * The busy list contains block ranges that have been freed but whose
2485 * transacations have not yet hit disk. If any block listed in a busy
2486 * list is reused, the transaction that freed it must be forced to disk
2487 * before continuing to use the block.
2489 * xfs_alloc_mark_busy - add to the per-ag busy list
2490 * xfs_alloc_clear_busy - remove an item from the per-ag busy list
2493 xfs_alloc_mark_busy(xfs_trans_t
*tp
,
2494 xfs_agnumber_t agno
,
2499 xfs_perag_busy_t
*bsy
;
2504 s
= mutex_spinlock(&mp
->m_perag
[agno
].pagb_lock
);
2506 /* search pagb_list for an open slot */
2507 for (bsy
= mp
->m_perag
[agno
].pagb_list
, n
= 0;
2508 n
< XFS_PAGB_NUM_SLOTS
;
2510 if (bsy
->busy_tp
== NULL
) {
2515 if (n
< XFS_PAGB_NUM_SLOTS
) {
2516 bsy
= &mp
->m_perag
[agno
].pagb_list
[n
];
2517 mp
->m_perag
[agno
].pagb_count
++;
2518 TRACE_BUSY("xfs_alloc_mark_busy", "got", agno
, bno
, len
, n
, tp
);
2519 bsy
->busy_start
= bno
;
2520 bsy
->busy_length
= len
;
2522 xfs_trans_add_busy(tp
, agno
, n
);
2524 TRACE_BUSY("xfs_alloc_mark_busy", "FULL", agno
, bno
, len
, -1, tp
);
2526 * The busy list is full! Since it is now not possible to
2527 * track the free block, make this a synchronous transaction
2528 * to insure that the block is not reused before this
2529 * transaction commits.
2531 xfs_trans_set_sync(tp
);
2534 mutex_spinunlock(&mp
->m_perag
[agno
].pagb_lock
, s
);
2538 xfs_alloc_clear_busy(xfs_trans_t
*tp
,
2539 xfs_agnumber_t agno
,
2543 xfs_perag_busy_t
*list
;
2548 s
= mutex_spinlock(&mp
->m_perag
[agno
].pagb_lock
);
2549 list
= mp
->m_perag
[agno
].pagb_list
;
2551 ASSERT(idx
< XFS_PAGB_NUM_SLOTS
);
2552 if (list
[idx
].busy_tp
== tp
) {
2553 TRACE_UNBUSY("xfs_alloc_clear_busy", "found", agno
, idx
, tp
);
2554 list
[idx
].busy_tp
= NULL
;
2555 mp
->m_perag
[agno
].pagb_count
--;
2557 TRACE_UNBUSY("xfs_alloc_clear_busy", "missing", agno
, idx
, tp
);
2560 mutex_spinunlock(&mp
->m_perag
[agno
].pagb_lock
, s
);
2565 * returns non-zero if any of (agno,bno):len is in a busy list
2568 xfs_alloc_search_busy(xfs_trans_t
*tp
,
2569 xfs_agnumber_t agno
,
2574 xfs_perag_busy_t
*bsy
;
2576 xfs_agblock_t uend
, bend
;
2583 s
= mutex_spinlock(&mp
->m_perag
[agno
].pagb_lock
);
2584 cnt
= mp
->m_perag
[agno
].pagb_count
;
2586 uend
= bno
+ len
- 1;
2588 /* search pagb_list for this slot, skipping open slots */
2589 for (bsy
= mp
->m_perag
[agno
].pagb_list
, n
= 0;
2593 * (start1,length1) within (start2, length2)
2595 if (bsy
->busy_tp
!= NULL
) {
2596 bend
= bsy
->busy_start
+ bsy
->busy_length
- 1;
2598 (uend
< bsy
->busy_start
)) {
2601 TRACE_BUSYSEARCH("xfs_alloc_search_busy",
2602 "found1", agno
, bno
, len
, n
,
2610 * If a block was found, force the log through the LSN of the
2611 * transaction that freed the block
2614 TRACE_BUSYSEARCH("xfs_alloc_search_busy", "found", agno
, bno
, len
, n
, tp
);
2615 lsn
= bsy
->busy_tp
->t_commit_lsn
;
2616 mutex_spinunlock(&mp
->m_perag
[agno
].pagb_lock
, s
);
2617 xfs_log_force(mp
, lsn
, XFS_LOG_FORCE
|XFS_LOG_SYNC
);
2619 TRACE_BUSYSEARCH("xfs_alloc_search_busy", "not-found", agno
, bno
, len
, n
, tp
);
2621 mutex_spinunlock(&mp
->m_perag
[agno
].pagb_lock
, s
);