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"
27 #include "xfs_mount.h"
28 #include "xfs_bmap_btree.h"
29 #include "xfs_alloc_btree.h"
30 #include "xfs_ialloc_btree.h"
31 #include "xfs_dinode.h"
32 #include "xfs_inode.h"
33 #include "xfs_btree.h"
34 #include "xfs_alloc.h"
35 #include "xfs_error.h"
36 #include "xfs_trace.h"
39 #define XFS_ABSDIFF(a,b) (((a) <= (b)) ? ((b) - (a)) : ((a) - (b)))
41 #define XFSA_FIXUP_BNO_OK 1
42 #define XFSA_FIXUP_CNT_OK 2
45 xfs_alloc_busy_search(struct xfs_mount *mp, xfs_agnumber_t agno,
46 xfs_agblock_t bno, xfs_extlen_t len);
49 * Prototypes for per-ag allocation routines
52 STATIC int xfs_alloc_ag_vextent_exact(xfs_alloc_arg_t *);
53 STATIC int xfs_alloc_ag_vextent_near(xfs_alloc_arg_t *);
54 STATIC int xfs_alloc_ag_vextent_size(xfs_alloc_arg_t *);
55 STATIC int xfs_alloc_ag_vextent_small(xfs_alloc_arg_t *,
56 xfs_btree_cur_t *, xfs_agblock_t *, xfs_extlen_t *, int *);
63 * Lookup the record equal to [bno, len] in the btree given by cur.
65 STATIC int /* error */
67 struct xfs_btree_cur *cur, /* btree cursor */
68 xfs_agblock_t bno, /* starting block of extent */
69 xfs_extlen_t len, /* length of extent */
70 int *stat) /* success/failure */
72 cur->bc_rec.a.ar_startblock = bno;
73 cur->bc_rec.a.ar_blockcount = len;
74 return xfs_btree_lookup(cur, XFS_LOOKUP_EQ, stat);
78 * Lookup the first record greater than or equal to [bno, len]
79 * in the btree given by cur.
81 STATIC int /* error */
83 struct xfs_btree_cur *cur, /* btree cursor */
84 xfs_agblock_t bno, /* starting block of extent */
85 xfs_extlen_t len, /* length of extent */
86 int *stat) /* success/failure */
88 cur->bc_rec.a.ar_startblock = bno;
89 cur->bc_rec.a.ar_blockcount = len;
90 return xfs_btree_lookup(cur, XFS_LOOKUP_GE, stat);
94 * Lookup the first record less than or equal to [bno, len]
95 * in the btree given by cur.
97 STATIC int /* error */
99 struct xfs_btree_cur *cur, /* btree cursor */
100 xfs_agblock_t bno, /* starting block of extent */
101 xfs_extlen_t len, /* length of extent */
102 int *stat) /* success/failure */
104 cur->bc_rec.a.ar_startblock = bno;
105 cur->bc_rec.a.ar_blockcount = len;
106 return xfs_btree_lookup(cur, XFS_LOOKUP_LE, stat);
110 * Update the record referred to by cur to the value given
112 * This either works (return 0) or gets an EFSCORRUPTED error.
114 STATIC int /* error */
116 struct xfs_btree_cur *cur, /* btree cursor */
117 xfs_agblock_t bno, /* starting block of extent */
118 xfs_extlen_t len) /* length of extent */
120 union xfs_btree_rec rec;
122 rec.alloc.ar_startblock = cpu_to_be32(bno);
123 rec.alloc.ar_blockcount = cpu_to_be32(len);
124 return xfs_btree_update(cur, &rec);
128 * Get the data from the pointed-to record.
130 STATIC int /* error */
132 struct xfs_btree_cur *cur, /* btree cursor */
133 xfs_agblock_t *bno, /* output: starting block of extent */
134 xfs_extlen_t *len, /* output: length of extent */
135 int *stat) /* output: success/failure */
137 union xfs_btree_rec *rec;
140 error = xfs_btree_get_rec(cur, &rec, stat);
141 if (!error && *stat == 1) {
142 *bno = be32_to_cpu(rec->alloc.ar_startblock);
143 *len = be32_to_cpu(rec->alloc.ar_blockcount);
149 * Compute aligned version of the found extent.
150 * Takes alignment and min length into account.
153 xfs_alloc_compute_aligned(
154 xfs_agblock_t foundbno, /* starting block in found extent */
155 xfs_extlen_t foundlen, /* length in found extent */
156 xfs_extlen_t alignment, /* alignment for allocation */
157 xfs_extlen_t minlen, /* minimum length for allocation */
158 xfs_agblock_t *resbno, /* result block number */
159 xfs_extlen_t *reslen) /* result length */
165 if (alignment > 1 && foundlen >= minlen) {
166 bno = roundup(foundbno, alignment);
167 diff = bno - foundbno;
168 len = diff >= foundlen ? 0 : foundlen - diff;
178 * Compute best start block and diff for "near" allocations.
179 * freelen >= wantlen already checked by caller.
181 STATIC xfs_extlen_t /* difference value (absolute) */
182 xfs_alloc_compute_diff(
183 xfs_agblock_t wantbno, /* target starting block */
184 xfs_extlen_t wantlen, /* target length */
185 xfs_extlen_t alignment, /* target alignment */
186 xfs_agblock_t freebno, /* freespace's starting block */
187 xfs_extlen_t freelen, /* freespace's length */
188 xfs_agblock_t *newbnop) /* result: best start block from free */
190 xfs_agblock_t freeend; /* end of freespace extent */
191 xfs_agblock_t newbno1; /* return block number */
192 xfs_agblock_t newbno2; /* other new block number */
193 xfs_extlen_t newlen1=0; /* length with newbno1 */
194 xfs_extlen_t newlen2=0; /* length with newbno2 */
195 xfs_agblock_t wantend; /* end of target extent */
197 ASSERT(freelen >= wantlen);
198 freeend = freebno + freelen;
199 wantend = wantbno + wantlen;
200 if (freebno >= wantbno) {
201 if ((newbno1 = roundup(freebno, alignment)) >= freeend)
202 newbno1 = NULLAGBLOCK;
203 } else if (freeend >= wantend && alignment > 1) {
204 newbno1 = roundup(wantbno, alignment);
205 newbno2 = newbno1 - alignment;
206 if (newbno1 >= freeend)
207 newbno1 = NULLAGBLOCK;
209 newlen1 = XFS_EXTLEN_MIN(wantlen, freeend - newbno1);
210 if (newbno2 < freebno)
211 newbno2 = NULLAGBLOCK;
213 newlen2 = XFS_EXTLEN_MIN(wantlen, freeend - newbno2);
214 if (newbno1 != NULLAGBLOCK && newbno2 != NULLAGBLOCK) {
215 if (newlen1 < newlen2 ||
216 (newlen1 == newlen2 &&
217 XFS_ABSDIFF(newbno1, wantbno) >
218 XFS_ABSDIFF(newbno2, wantbno)))
220 } else if (newbno2 != NULLAGBLOCK)
222 } else if (freeend >= wantend) {
224 } else if (alignment > 1) {
225 newbno1 = roundup(freeend - wantlen, alignment);
226 if (newbno1 > freeend - wantlen &&
227 newbno1 - alignment >= freebno)
228 newbno1 -= alignment;
229 else if (newbno1 >= freeend)
230 newbno1 = NULLAGBLOCK;
232 newbno1 = freeend - wantlen;
234 return newbno1 == NULLAGBLOCK ? 0 : XFS_ABSDIFF(newbno1, wantbno);
238 * Fix up the length, based on mod and prod.
239 * len should be k * prod + mod for some k.
240 * If len is too small it is returned unchanged.
241 * If len hits maxlen it is left alone.
245 xfs_alloc_arg_t *args) /* allocation argument structure */
250 ASSERT(args->mod < args->prod);
252 ASSERT(rlen >= args->minlen);
253 ASSERT(rlen <= args->maxlen);
254 if (args->prod <= 1 || rlen < args->mod || rlen == args->maxlen ||
255 (args->mod == 0 && rlen < args->prod))
257 k = rlen % args->prod;
261 if ((int)(rlen = rlen - k - args->mod) < (int)args->minlen)
264 if ((int)(rlen = rlen - args->prod - (args->mod - k)) <
268 ASSERT(rlen >= args->minlen);
269 ASSERT(rlen <= args->maxlen);
274 * Fix up length if there is too little space left in the a.g.
275 * Return 1 if ok, 0 if too little, should give up.
278 xfs_alloc_fix_minleft(
279 xfs_alloc_arg_t *args) /* allocation argument structure */
281 xfs_agf_t *agf; /* a.g. freelist header */
282 int diff; /* free space difference */
284 if (args->minleft == 0)
286 agf = XFS_BUF_TO_AGF(args->agbp);
287 diff = be32_to_cpu(agf->agf_freeblks)
288 + be32_to_cpu(agf->agf_flcount)
289 - args->len - args->minleft;
292 args->len += diff; /* shrink the allocated space */
293 if (args->len >= args->minlen)
295 args->agbno = NULLAGBLOCK;
300 * Update the two btrees, logically removing from freespace the extent
301 * starting at rbno, rlen blocks. The extent is contained within the
302 * actual (current) free extent fbno for flen blocks.
303 * Flags are passed in indicating whether the cursors are set to the
306 STATIC int /* error code */
307 xfs_alloc_fixup_trees(
308 xfs_btree_cur_t *cnt_cur, /* cursor for by-size btree */
309 xfs_btree_cur_t *bno_cur, /* cursor for by-block btree */
310 xfs_agblock_t fbno, /* starting block of free extent */
311 xfs_extlen_t flen, /* length of free extent */
312 xfs_agblock_t rbno, /* starting block of returned extent */
313 xfs_extlen_t rlen, /* length of returned extent */
314 int flags) /* flags, XFSA_FIXUP_... */
316 int error; /* error code */
317 int i; /* operation results */
318 xfs_agblock_t nfbno1; /* first new free startblock */
319 xfs_agblock_t nfbno2; /* second new free startblock */
320 xfs_extlen_t nflen1=0; /* first new free length */
321 xfs_extlen_t nflen2=0; /* second new free length */
324 * Look up the record in the by-size tree if necessary.
326 if (flags & XFSA_FIXUP_CNT_OK) {
328 if ((error = xfs_alloc_get_rec(cnt_cur, &nfbno1, &nflen1, &i)))
330 XFS_WANT_CORRUPTED_RETURN(
331 i == 1 && nfbno1 == fbno && nflen1 == flen);
334 if ((error = xfs_alloc_lookup_eq(cnt_cur, fbno, flen, &i)))
336 XFS_WANT_CORRUPTED_RETURN(i == 1);
339 * Look up the record in the by-block tree if necessary.
341 if (flags & XFSA_FIXUP_BNO_OK) {
343 if ((error = xfs_alloc_get_rec(bno_cur, &nfbno1, &nflen1, &i)))
345 XFS_WANT_CORRUPTED_RETURN(
346 i == 1 && nfbno1 == fbno && nflen1 == flen);
349 if ((error = xfs_alloc_lookup_eq(bno_cur, fbno, flen, &i)))
351 XFS_WANT_CORRUPTED_RETURN(i == 1);
355 if (bno_cur->bc_nlevels == 1 && cnt_cur->bc_nlevels == 1) {
356 struct xfs_btree_block *bnoblock;
357 struct xfs_btree_block *cntblock;
359 bnoblock = XFS_BUF_TO_BLOCK(bno_cur->bc_bufs[0]);
360 cntblock = XFS_BUF_TO_BLOCK(cnt_cur->bc_bufs[0]);
362 XFS_WANT_CORRUPTED_RETURN(
363 bnoblock->bb_numrecs == cntblock->bb_numrecs);
368 * Deal with all four cases: the allocated record is contained
369 * within the freespace record, so we can have new freespace
370 * at either (or both) end, or no freespace remaining.
372 if (rbno == fbno && rlen == flen)
373 nfbno1 = nfbno2 = NULLAGBLOCK;
374 else if (rbno == fbno) {
375 nfbno1 = rbno + rlen;
376 nflen1 = flen - rlen;
377 nfbno2 = NULLAGBLOCK;
378 } else if (rbno + rlen == fbno + flen) {
380 nflen1 = flen - rlen;
381 nfbno2 = NULLAGBLOCK;
384 nflen1 = rbno - fbno;
385 nfbno2 = rbno + rlen;
386 nflen2 = (fbno + flen) - nfbno2;
389 * Delete the entry from the by-size btree.
391 if ((error = xfs_btree_delete(cnt_cur, &i)))
393 XFS_WANT_CORRUPTED_RETURN(i == 1);
395 * Add new by-size btree entry(s).
397 if (nfbno1 != NULLAGBLOCK) {
398 if ((error = xfs_alloc_lookup_eq(cnt_cur, nfbno1, nflen1, &i)))
400 XFS_WANT_CORRUPTED_RETURN(i == 0);
401 if ((error = xfs_btree_insert(cnt_cur, &i)))
403 XFS_WANT_CORRUPTED_RETURN(i == 1);
405 if (nfbno2 != NULLAGBLOCK) {
406 if ((error = xfs_alloc_lookup_eq(cnt_cur, nfbno2, nflen2, &i)))
408 XFS_WANT_CORRUPTED_RETURN(i == 0);
409 if ((error = xfs_btree_insert(cnt_cur, &i)))
411 XFS_WANT_CORRUPTED_RETURN(i == 1);
414 * Fix up the by-block btree entry(s).
416 if (nfbno1 == NULLAGBLOCK) {
418 * No remaining freespace, just delete the by-block tree entry.
420 if ((error = xfs_btree_delete(bno_cur, &i)))
422 XFS_WANT_CORRUPTED_RETURN(i == 1);
425 * Update the by-block entry to start later|be shorter.
427 if ((error = xfs_alloc_update(bno_cur, nfbno1, nflen1)))
430 if (nfbno2 != NULLAGBLOCK) {
432 * 2 resulting free entries, need to add one.
434 if ((error = xfs_alloc_lookup_eq(bno_cur, nfbno2, nflen2, &i)))
436 XFS_WANT_CORRUPTED_RETURN(i == 0);
437 if ((error = xfs_btree_insert(bno_cur, &i)))
439 XFS_WANT_CORRUPTED_RETURN(i == 1);
445 * Read in the allocation group free block array.
447 STATIC int /* error */
449 xfs_mount_t *mp, /* mount point structure */
450 xfs_trans_t *tp, /* transaction pointer */
451 xfs_agnumber_t agno, /* allocation group number */
452 xfs_buf_t **bpp) /* buffer for the ag free block array */
454 xfs_buf_t *bp; /* return value */
457 ASSERT(agno != NULLAGNUMBER);
458 error = xfs_trans_read_buf(
459 mp, tp, mp->m_ddev_targp,
460 XFS_AG_DADDR(mp, agno, XFS_AGFL_DADDR(mp)),
461 XFS_FSS_TO_BB(mp, 1), 0, &bp);
465 ASSERT(!XFS_BUF_GETERROR(bp));
466 XFS_BUF_SET_VTYPE_REF(bp, B_FS_AGFL, XFS_AGFL_REF);
472 * Allocation group level functions.
476 * Allocate a variable extent in the allocation group agno.
477 * Type and bno are used to determine where in the allocation group the
479 * Extent's length (returned in *len) will be between minlen and maxlen,
480 * and of the form k * prod + mod unless there's nothing that large.
481 * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
483 STATIC int /* error */
484 xfs_alloc_ag_vextent(
485 xfs_alloc_arg_t *args) /* argument structure for allocation */
489 ASSERT(args->minlen > 0);
490 ASSERT(args->maxlen > 0);
491 ASSERT(args->minlen <= args->maxlen);
492 ASSERT(args->mod < args->prod);
493 ASSERT(args->alignment > 0);
495 * Branch to correct routine based on the type.
498 switch (args->type) {
499 case XFS_ALLOCTYPE_THIS_AG:
500 error = xfs_alloc_ag_vextent_size(args);
502 case XFS_ALLOCTYPE_NEAR_BNO:
503 error = xfs_alloc_ag_vextent_near(args);
505 case XFS_ALLOCTYPE_THIS_BNO:
506 error = xfs_alloc_ag_vextent_exact(args);
515 * If the allocation worked, need to change the agf structure
516 * (and log it), and the superblock.
518 if (args->agbno != NULLAGBLOCK) {
519 xfs_agf_t *agf; /* allocation group freelist header */
520 long slen = (long)args->len;
522 ASSERT(args->len >= args->minlen && args->len <= args->maxlen);
523 ASSERT(!(args->wasfromfl) || !args->isfl);
524 ASSERT(args->agbno % args->alignment == 0);
525 if (!(args->wasfromfl)) {
527 agf = XFS_BUF_TO_AGF(args->agbp);
528 be32_add_cpu(&agf->agf_freeblks, -(args->len));
529 xfs_trans_agblocks_delta(args->tp,
530 -((long)(args->len)));
531 args->pag->pagf_freeblks -= args->len;
532 ASSERT(be32_to_cpu(agf->agf_freeblks) <=
533 be32_to_cpu(agf->agf_length));
534 xfs_alloc_log_agf(args->tp, args->agbp,
537 * Search the busylist for these blocks and mark the
538 * transaction as synchronous if blocks are found. This
539 * avoids the need to block due to a synchronous log
540 * force to ensure correct ordering as the synchronous
541 * transaction will guarantee that for us.
543 if (xfs_alloc_busy_search(args->mp, args->agno,
544 args->agbno, args->len))
545 xfs_trans_set_sync(args->tp);
548 xfs_trans_mod_sb(args->tp,
549 args->wasdel ? XFS_TRANS_SB_RES_FDBLOCKS :
550 XFS_TRANS_SB_FDBLOCKS, -slen);
551 XFS_STATS_INC(xs_allocx);
552 XFS_STATS_ADD(xs_allocb, args->len);
558 * Allocate a variable extent at exactly agno/bno.
559 * Extent's length (returned in *len) will be between minlen and maxlen,
560 * and of the form k * prod + mod unless there's nothing that large.
561 * Return the starting a.g. block (bno), or NULLAGBLOCK if we can't do it.
563 STATIC int /* error */
564 xfs_alloc_ag_vextent_exact(
565 xfs_alloc_arg_t *args) /* allocation argument structure */
567 xfs_btree_cur_t *bno_cur;/* by block-number btree cursor */
568 xfs_btree_cur_t *cnt_cur;/* by count btree cursor */
569 xfs_agblock_t end; /* end of allocated extent */
571 xfs_agblock_t fbno; /* start block of found extent */
572 xfs_agblock_t fend; /* end block of found extent */
573 xfs_extlen_t flen; /* length of found extent */
574 int i; /* success/failure of operation */
575 xfs_agblock_t maxend; /* end of maximal extent */
576 xfs_agblock_t minend; /* end of minimal extent */
577 xfs_extlen_t rlen; /* length of returned extent */
579 ASSERT(args->alignment == 1);
581 * Allocate/initialize a cursor for the by-number freespace btree.
583 bno_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
584 args->agno, XFS_BTNUM_BNO);
586 * Lookup bno and minlen in the btree (minlen is irrelevant, really).
587 * Look for the closest free block <= bno, it must contain bno
588 * if any free block does.
590 if ((error = xfs_alloc_lookup_le(bno_cur, args->agbno, args->minlen, &i)))
594 * Didn't find it, return null.
596 xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
597 args->agbno = NULLAGBLOCK;
601 * Grab the freespace record.
603 if ((error = xfs_alloc_get_rec(bno_cur, &fbno, &flen, &i)))
605 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
606 ASSERT(fbno <= args->agbno);
607 minend = args->agbno + args->minlen;
608 maxend = args->agbno + args->maxlen;
611 * Give up if the freespace isn't long enough for the minimum request.
614 xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
615 args->agbno = NULLAGBLOCK;
619 * End of extent will be smaller of the freespace end and the
620 * maximal requested end.
622 end = XFS_AGBLOCK_MIN(fend, maxend);
624 * Fix the length according to mod and prod if given.
626 args->len = end - args->agbno;
627 xfs_alloc_fix_len(args);
628 if (!xfs_alloc_fix_minleft(args)) {
629 xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
633 ASSERT(args->agbno + rlen <= fend);
634 end = args->agbno + rlen;
636 * We are allocating agbno for rlen [agbno .. end]
637 * Allocate/initialize a cursor for the by-size btree.
639 cnt_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
640 args->agno, XFS_BTNUM_CNT);
641 ASSERT(args->agbno + args->len <=
642 be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length));
643 if ((error = xfs_alloc_fixup_trees(cnt_cur, bno_cur, fbno, flen,
644 args->agbno, args->len, XFSA_FIXUP_BNO_OK))) {
645 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
648 xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
649 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
651 trace_xfs_alloc_exact_done(args);
656 xfs_btree_del_cursor(bno_cur, XFS_BTREE_ERROR);
657 trace_xfs_alloc_exact_error(args);
662 * Allocate a variable extent near bno in the allocation group agno.
663 * Extent's length (returned in len) will be between minlen and maxlen,
664 * and of the form k * prod + mod unless there's nothing that large.
665 * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
667 STATIC int /* error */
668 xfs_alloc_ag_vextent_near(
669 xfs_alloc_arg_t *args) /* allocation argument structure */
671 xfs_btree_cur_t *bno_cur_gt; /* cursor for bno btree, right side */
672 xfs_btree_cur_t *bno_cur_lt; /* cursor for bno btree, left side */
673 xfs_btree_cur_t *cnt_cur; /* cursor for count btree */
674 xfs_agblock_t gtbno; /* start bno of right side entry */
675 xfs_agblock_t gtbnoa; /* aligned ... */
676 xfs_extlen_t gtdiff; /* difference to right side entry */
677 xfs_extlen_t gtlen; /* length of right side entry */
678 xfs_extlen_t gtlena; /* aligned ... */
679 xfs_agblock_t gtnew; /* useful start bno of right side */
680 int error; /* error code */
681 int i; /* result code, temporary */
682 int j; /* result code, temporary */
683 xfs_agblock_t ltbno; /* start bno of left side entry */
684 xfs_agblock_t ltbnoa; /* aligned ... */
685 xfs_extlen_t ltdiff; /* difference to left side entry */
687 xfs_agblock_t ltend; /* end bno of left side entry */
688 xfs_extlen_t ltlen; /* length of left side entry */
689 xfs_extlen_t ltlena; /* aligned ... */
690 xfs_agblock_t ltnew; /* useful start bno of left side */
691 xfs_extlen_t rlen; /* length of returned extent */
692 #if defined(DEBUG) && defined(__KERNEL__)
694 * Randomly don't execute the first algorithm.
696 int dofirst; /* set to do first algorithm */
698 dofirst = random32() & 1;
701 * Get a cursor for the by-size btree.
703 cnt_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
704 args->agno, XFS_BTNUM_CNT);
706 bno_cur_lt = bno_cur_gt = NULL;
708 * See if there are any free extents as big as maxlen.
710 if ((error = xfs_alloc_lookup_ge(cnt_cur, 0, args->maxlen, &i)))
713 * If none, then pick up the last entry in the tree unless the
717 if ((error = xfs_alloc_ag_vextent_small(args, cnt_cur, <bno,
720 if (i == 0 || ltlen == 0) {
721 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
729 * If the requested extent is large wrt the freespaces available
730 * in this a.g., then the cursor will be pointing to a btree entry
731 * near the right edge of the tree. If it's in the last btree leaf
732 * block, then we just examine all the entries in that block
733 * that are big enough, and pick the best one.
734 * This is written as a while loop so we can break out of it,
735 * but we never loop back to the top.
737 while (xfs_btree_islastblock(cnt_cur, 0)) {
741 xfs_agblock_t bnew=0;
743 #if defined(DEBUG) && defined(__KERNEL__)
748 * Start from the entry that lookup found, sequence through
749 * all larger free blocks. If we're actually pointing at a
750 * record smaller than maxlen, go to the start of this block,
751 * and skip all those smaller than minlen.
753 if (ltlen || args->alignment > 1) {
754 cnt_cur->bc_ptrs[0] = 1;
756 if ((error = xfs_alloc_get_rec(cnt_cur, <bno,
759 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
760 if (ltlen >= args->minlen)
762 if ((error = xfs_btree_increment(cnt_cur, 0, &i)))
765 ASSERT(ltlen >= args->minlen);
769 i = cnt_cur->bc_ptrs[0];
770 for (j = 1, blen = 0, bdiff = 0;
771 !error && j && (blen < args->maxlen || bdiff > 0);
772 error = xfs_btree_increment(cnt_cur, 0, &j)) {
774 * For each entry, decide if it's better than
775 * the previous best entry.
777 if ((error = xfs_alloc_get_rec(cnt_cur, <bno, <len, &i)))
779 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
780 xfs_alloc_compute_aligned(ltbno, ltlen, args->alignment,
781 args->minlen, <bnoa, <lena);
782 if (ltlena < args->minlen)
784 args->len = XFS_EXTLEN_MIN(ltlena, args->maxlen);
785 xfs_alloc_fix_len(args);
786 ASSERT(args->len >= args->minlen);
787 if (args->len < blen)
789 ltdiff = xfs_alloc_compute_diff(args->agbno, args->len,
790 args->alignment, ltbno, ltlen, <new);
791 if (ltnew != NULLAGBLOCK &&
792 (args->len > blen || ltdiff < bdiff)) {
796 besti = cnt_cur->bc_ptrs[0];
800 * It didn't work. We COULD be in a case where
801 * there's a good record somewhere, so try again.
806 * Point at the best entry, and retrieve it again.
808 cnt_cur->bc_ptrs[0] = besti;
809 if ((error = xfs_alloc_get_rec(cnt_cur, <bno, <len, &i)))
811 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
812 ltend = ltbno + ltlen;
813 ASSERT(ltend <= be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length));
815 if (!xfs_alloc_fix_minleft(args)) {
816 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
817 trace_xfs_alloc_near_nominleft(args);
822 * We are allocating starting at bnew for blen blocks.
825 ASSERT(bnew >= ltbno);
826 ASSERT(bnew + blen <= ltend);
828 * Set up a cursor for the by-bno tree.
830 bno_cur_lt = xfs_allocbt_init_cursor(args->mp, args->tp,
831 args->agbp, args->agno, XFS_BTNUM_BNO);
833 * Fix up the btree entries.
835 if ((error = xfs_alloc_fixup_trees(cnt_cur, bno_cur_lt, ltbno,
836 ltlen, bnew, blen, XFSA_FIXUP_CNT_OK)))
838 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
839 xfs_btree_del_cursor(bno_cur_lt, XFS_BTREE_NOERROR);
841 trace_xfs_alloc_near_first(args);
846 * Search in the by-bno tree to the left and to the right
847 * simultaneously, until in each case we find a space big enough,
848 * or run into the edge of the tree. When we run into the edge,
849 * we deallocate that cursor.
850 * If both searches succeed, we compare the two spaces and pick
852 * With alignment, it's possible for both to fail; the upper
853 * level algorithm that picks allocation groups for allocations
854 * is not supposed to do this.
857 * Allocate and initialize the cursor for the leftward search.
859 bno_cur_lt = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
860 args->agno, XFS_BTNUM_BNO);
862 * Lookup <= bno to find the leftward search's starting point.
864 if ((error = xfs_alloc_lookup_le(bno_cur_lt, args->agbno, args->maxlen, &i)))
868 * Didn't find anything; use this cursor for the rightward
871 bno_cur_gt = bno_cur_lt;
875 * Found something. Duplicate the cursor for the rightward search.
877 else if ((error = xfs_btree_dup_cursor(bno_cur_lt, &bno_cur_gt)))
880 * Increment the cursor, so we will point at the entry just right
881 * of the leftward entry if any, or to the leftmost entry.
883 if ((error = xfs_btree_increment(bno_cur_gt, 0, &i)))
887 * It failed, there are no rightward entries.
889 xfs_btree_del_cursor(bno_cur_gt, XFS_BTREE_NOERROR);
893 * Loop going left with the leftward cursor, right with the
894 * rightward cursor, until either both directions give up or
895 * we find an entry at least as big as minlen.
899 if ((error = xfs_alloc_get_rec(bno_cur_lt, <bno, <len, &i)))
901 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
902 xfs_alloc_compute_aligned(ltbno, ltlen, args->alignment,
903 args->minlen, <bnoa, <lena);
904 if (ltlena >= args->minlen)
906 if ((error = xfs_btree_decrement(bno_cur_lt, 0, &i)))
909 xfs_btree_del_cursor(bno_cur_lt,
915 if ((error = xfs_alloc_get_rec(bno_cur_gt, >bno, >len, &i)))
917 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
918 xfs_alloc_compute_aligned(gtbno, gtlen, args->alignment,
919 args->minlen, >bnoa, >lena);
920 if (gtlena >= args->minlen)
922 if ((error = xfs_btree_increment(bno_cur_gt, 0, &i)))
925 xfs_btree_del_cursor(bno_cur_gt,
930 } while (bno_cur_lt || bno_cur_gt);
932 * Got both cursors still active, need to find better entry.
934 if (bno_cur_lt && bno_cur_gt) {
936 * Left side is long enough, look for a right side entry.
938 if (ltlena >= args->minlen) {
942 args->len = XFS_EXTLEN_MIN(ltlena, args->maxlen);
943 xfs_alloc_fix_len(args);
945 ltdiff = xfs_alloc_compute_diff(args->agbno, rlen,
946 args->alignment, ltbno, ltlen, <new);
952 * Look until we find a better one, run out of
953 * space, or run off the end.
955 while (bno_cur_lt && bno_cur_gt) {
956 if ((error = xfs_alloc_get_rec(
960 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
961 xfs_alloc_compute_aligned(gtbno, gtlen,
962 args->alignment, args->minlen,
965 * The left one is clearly better.
967 if (gtbnoa >= args->agbno + ltdiff) {
968 xfs_btree_del_cursor(
975 * If we reach a big enough entry,
976 * compare the two and pick the best.
978 if (gtlena >= args->minlen) {
980 XFS_EXTLEN_MIN(gtlena,
982 xfs_alloc_fix_len(args);
984 gtdiff = xfs_alloc_compute_diff(
987 gtbno, gtlen, >new);
989 * Right side is better.
991 if (gtdiff < ltdiff) {
992 xfs_btree_del_cursor(
998 * Left side is better.
1001 xfs_btree_del_cursor(
1009 * Fell off the right end.
1011 if ((error = xfs_btree_increment(
1012 bno_cur_gt, 0, &i)))
1015 xfs_btree_del_cursor(
1024 * The left side is perfect, trash the right side.
1027 xfs_btree_del_cursor(bno_cur_gt,
1033 * It's the right side that was found first, look left.
1037 * Fix up the length.
1039 args->len = XFS_EXTLEN_MIN(gtlena, args->maxlen);
1040 xfs_alloc_fix_len(args);
1042 gtdiff = xfs_alloc_compute_diff(args->agbno, rlen,
1043 args->alignment, gtbno, gtlen, >new);
1045 * Right side entry isn't perfect.
1049 * Look until we find a better one, run out of
1050 * space, or run off the end.
1052 while (bno_cur_lt && bno_cur_gt) {
1053 if ((error = xfs_alloc_get_rec(
1057 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1058 xfs_alloc_compute_aligned(ltbno, ltlen,
1059 args->alignment, args->minlen,
1062 * The right one is clearly better.
1064 if (ltbnoa <= args->agbno - gtdiff) {
1065 xfs_btree_del_cursor(
1072 * If we reach a big enough entry,
1073 * compare the two and pick the best.
1075 if (ltlena >= args->minlen) {
1076 args->len = XFS_EXTLEN_MIN(
1077 ltlena, args->maxlen);
1078 xfs_alloc_fix_len(args);
1080 ltdiff = xfs_alloc_compute_diff(
1083 ltbno, ltlen, <new);
1085 * Left side is better.
1087 if (ltdiff < gtdiff) {
1088 xfs_btree_del_cursor(
1094 * Right side is better.
1097 xfs_btree_del_cursor(
1105 * Fell off the left end.
1107 if ((error = xfs_btree_decrement(
1108 bno_cur_lt, 0, &i)))
1111 xfs_btree_del_cursor(bno_cur_lt,
1119 * The right side is perfect, trash the left side.
1122 xfs_btree_del_cursor(bno_cur_lt,
1129 * If we couldn't get anything, give up.
1131 if (bno_cur_lt == NULL && bno_cur_gt == NULL) {
1132 trace_xfs_alloc_size_neither(args);
1133 args->agbno = NULLAGBLOCK;
1137 * At this point we have selected a freespace entry, either to the
1138 * left or to the right. If it's on the right, copy all the
1139 * useful variables to the "left" set so we only have one
1140 * copy of this code.
1143 bno_cur_lt = bno_cur_gt;
1153 * Fix up the length and compute the useful address.
1155 ltend = ltbno + ltlen;
1156 args->len = XFS_EXTLEN_MIN(ltlena, args->maxlen);
1157 xfs_alloc_fix_len(args);
1158 if (!xfs_alloc_fix_minleft(args)) {
1159 trace_xfs_alloc_near_nominleft(args);
1160 xfs_btree_del_cursor(bno_cur_lt, XFS_BTREE_NOERROR);
1161 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1165 (void)xfs_alloc_compute_diff(args->agbno, rlen, args->alignment, ltbno,
1167 ASSERT(ltnew >= ltbno);
1168 ASSERT(ltnew + rlen <= ltend);
1169 ASSERT(ltnew + rlen <= be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length));
1170 args->agbno = ltnew;
1171 if ((error = xfs_alloc_fixup_trees(cnt_cur, bno_cur_lt, ltbno, ltlen,
1172 ltnew, rlen, XFSA_FIXUP_BNO_OK)))
1176 trace_xfs_alloc_near_greater(args);
1178 trace_xfs_alloc_near_lesser(args);
1180 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1181 xfs_btree_del_cursor(bno_cur_lt, XFS_BTREE_NOERROR);
1185 trace_xfs_alloc_near_error(args);
1186 if (cnt_cur != NULL)
1187 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
1188 if (bno_cur_lt != NULL)
1189 xfs_btree_del_cursor(bno_cur_lt, XFS_BTREE_ERROR);
1190 if (bno_cur_gt != NULL)
1191 xfs_btree_del_cursor(bno_cur_gt, XFS_BTREE_ERROR);
1196 * Allocate a variable extent anywhere in the allocation group agno.
1197 * Extent's length (returned in len) will be between minlen and maxlen,
1198 * and of the form k * prod + mod unless there's nothing that large.
1199 * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
1201 STATIC int /* error */
1202 xfs_alloc_ag_vextent_size(
1203 xfs_alloc_arg_t *args) /* allocation argument structure */
1205 xfs_btree_cur_t *bno_cur; /* cursor for bno btree */
1206 xfs_btree_cur_t *cnt_cur; /* cursor for cnt btree */
1207 int error; /* error result */
1208 xfs_agblock_t fbno; /* start of found freespace */
1209 xfs_extlen_t flen; /* length of found freespace */
1210 int i; /* temp status variable */
1211 xfs_agblock_t rbno; /* returned block number */
1212 xfs_extlen_t rlen; /* length of returned extent */
1215 * Allocate and initialize a cursor for the by-size btree.
1217 cnt_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
1218 args->agno, XFS_BTNUM_CNT);
1221 * Look for an entry >= maxlen+alignment-1 blocks.
1223 if ((error = xfs_alloc_lookup_ge(cnt_cur, 0,
1224 args->maxlen + args->alignment - 1, &i)))
1227 * If none, then pick up the last entry in the tree unless the
1231 if ((error = xfs_alloc_ag_vextent_small(args, cnt_cur, &fbno,
1234 if (i == 0 || flen == 0) {
1235 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1236 trace_xfs_alloc_size_noentry(args);
1242 * There's a freespace as big as maxlen+alignment-1, get it.
1245 if ((error = xfs_alloc_get_rec(cnt_cur, &fbno, &flen, &i)))
1247 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1250 * In the first case above, we got the last entry in the
1251 * by-size btree. Now we check to see if the space hits maxlen
1252 * once aligned; if not, we search left for something better.
1253 * This can't happen in the second case above.
1255 xfs_alloc_compute_aligned(fbno, flen, args->alignment, args->minlen,
1257 rlen = XFS_EXTLEN_MIN(args->maxlen, rlen);
1258 XFS_WANT_CORRUPTED_GOTO(rlen == 0 ||
1259 (rlen <= flen && rbno + rlen <= fbno + flen), error0);
1260 if (rlen < args->maxlen) {
1261 xfs_agblock_t bestfbno;
1262 xfs_extlen_t bestflen;
1263 xfs_agblock_t bestrbno;
1264 xfs_extlen_t bestrlen;
1271 if ((error = xfs_btree_decrement(cnt_cur, 0, &i)))
1275 if ((error = xfs_alloc_get_rec(cnt_cur, &fbno, &flen,
1278 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1279 if (flen < bestrlen)
1281 xfs_alloc_compute_aligned(fbno, flen, args->alignment,
1282 args->minlen, &rbno, &rlen);
1283 rlen = XFS_EXTLEN_MIN(args->maxlen, rlen);
1284 XFS_WANT_CORRUPTED_GOTO(rlen == 0 ||
1285 (rlen <= flen && rbno + rlen <= fbno + flen),
1287 if (rlen > bestrlen) {
1292 if (rlen == args->maxlen)
1296 if ((error = xfs_alloc_lookup_eq(cnt_cur, bestfbno, bestflen,
1299 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1305 args->wasfromfl = 0;
1307 * Fix up the length.
1310 xfs_alloc_fix_len(args);
1311 if (rlen < args->minlen || !xfs_alloc_fix_minleft(args)) {
1312 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1313 trace_xfs_alloc_size_nominleft(args);
1314 args->agbno = NULLAGBLOCK;
1318 XFS_WANT_CORRUPTED_GOTO(rlen <= flen, error0);
1320 * Allocate and initialize a cursor for the by-block tree.
1322 bno_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
1323 args->agno, XFS_BTNUM_BNO);
1324 if ((error = xfs_alloc_fixup_trees(cnt_cur, bno_cur, fbno, flen,
1325 rbno, rlen, XFSA_FIXUP_CNT_OK)))
1327 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1328 xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
1329 cnt_cur = bno_cur = NULL;
1332 XFS_WANT_CORRUPTED_GOTO(
1333 args->agbno + args->len <=
1334 be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length),
1336 trace_xfs_alloc_size_done(args);
1340 trace_xfs_alloc_size_error(args);
1342 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
1344 xfs_btree_del_cursor(bno_cur, XFS_BTREE_ERROR);
1349 * Deal with the case where only small freespaces remain.
1350 * Either return the contents of the last freespace record,
1351 * or allocate space from the freelist if there is nothing in the tree.
1353 STATIC int /* error */
1354 xfs_alloc_ag_vextent_small(
1355 xfs_alloc_arg_t *args, /* allocation argument structure */
1356 xfs_btree_cur_t *ccur, /* by-size cursor */
1357 xfs_agblock_t *fbnop, /* result block number */
1358 xfs_extlen_t *flenp, /* result length */
1359 int *stat) /* status: 0-freelist, 1-normal/none */
1366 if ((error = xfs_btree_decrement(ccur, 0, &i)))
1369 if ((error = xfs_alloc_get_rec(ccur, &fbno, &flen, &i)))
1371 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1374 * Nothing in the btree, try the freelist. Make sure
1375 * to respect minleft even when pulling from the
1378 else if (args->minlen == 1 && args->alignment == 1 && !args->isfl &&
1379 (be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_flcount)
1381 error = xfs_alloc_get_freelist(args->tp, args->agbp, &fbno, 0);
1384 if (fbno != NULLAGBLOCK) {
1385 if (args->userdata) {
1388 bp = xfs_btree_get_bufs(args->mp, args->tp,
1389 args->agno, fbno, 0);
1390 xfs_trans_binval(args->tp, bp);
1394 XFS_WANT_CORRUPTED_GOTO(
1395 args->agbno + args->len <=
1396 be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length),
1398 args->wasfromfl = 1;
1399 trace_xfs_alloc_small_freelist(args);
1404 * Nothing in the freelist.
1410 * Can't allocate from the freelist for some reason.
1417 * Can't do the allocation, give up.
1419 if (flen < args->minlen) {
1420 args->agbno = NULLAGBLOCK;
1421 trace_xfs_alloc_small_notenough(args);
1427 trace_xfs_alloc_small_done(args);
1431 trace_xfs_alloc_small_error(args);
1436 * Free the extent starting at agno/bno for length.
1438 STATIC int /* error */
1440 xfs_trans_t *tp, /* transaction pointer */
1441 xfs_buf_t *agbp, /* buffer for a.g. freelist header */
1442 xfs_agnumber_t agno, /* allocation group number */
1443 xfs_agblock_t bno, /* starting block number */
1444 xfs_extlen_t len, /* length of extent */
1445 int isfl) /* set if is freelist blocks - no sb acctg */
1447 xfs_btree_cur_t *bno_cur; /* cursor for by-block btree */
1448 xfs_btree_cur_t *cnt_cur; /* cursor for by-size btree */
1449 int error; /* error return value */
1450 xfs_agblock_t gtbno; /* start of right neighbor block */
1451 xfs_extlen_t gtlen; /* length of right neighbor block */
1452 int haveleft; /* have a left neighbor block */
1453 int haveright; /* have a right neighbor block */
1454 int i; /* temp, result code */
1455 xfs_agblock_t ltbno; /* start of left neighbor block */
1456 xfs_extlen_t ltlen; /* length of left neighbor block */
1457 xfs_mount_t *mp; /* mount point struct for filesystem */
1458 xfs_agblock_t nbno; /* new starting block of freespace */
1459 xfs_extlen_t nlen; /* new length of freespace */
1463 * Allocate and initialize a cursor for the by-block btree.
1465 bno_cur = xfs_allocbt_init_cursor(mp, tp, agbp, agno, XFS_BTNUM_BNO);
1468 * Look for a neighboring block on the left (lower block numbers)
1469 * that is contiguous with this space.
1471 if ((error = xfs_alloc_lookup_le(bno_cur, bno, len, &haveleft)))
1475 * There is a block to our left.
1477 if ((error = xfs_alloc_get_rec(bno_cur, <bno, <len, &i)))
1479 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1481 * It's not contiguous, though.
1483 if (ltbno + ltlen < bno)
1487 * If this failure happens the request to free this
1488 * space was invalid, it's (partly) already free.
1491 XFS_WANT_CORRUPTED_GOTO(ltbno + ltlen <= bno, error0);
1495 * Look for a neighboring block on the right (higher block numbers)
1496 * that is contiguous with this space.
1498 if ((error = xfs_btree_increment(bno_cur, 0, &haveright)))
1502 * There is a block to our right.
1504 if ((error = xfs_alloc_get_rec(bno_cur, >bno, >len, &i)))
1506 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1508 * It's not contiguous, though.
1510 if (bno + len < gtbno)
1514 * If this failure happens the request to free this
1515 * space was invalid, it's (partly) already free.
1518 XFS_WANT_CORRUPTED_GOTO(gtbno >= bno + len, error0);
1522 * Now allocate and initialize a cursor for the by-size tree.
1524 cnt_cur = xfs_allocbt_init_cursor(mp, tp, agbp, agno, XFS_BTNUM_CNT);
1526 * Have both left and right contiguous neighbors.
1527 * Merge all three into a single free block.
1529 if (haveleft && haveright) {
1531 * Delete the old by-size entry on the left.
1533 if ((error = xfs_alloc_lookup_eq(cnt_cur, ltbno, ltlen, &i)))
1535 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1536 if ((error = xfs_btree_delete(cnt_cur, &i)))
1538 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1540 * Delete the old by-size entry on the right.
1542 if ((error = xfs_alloc_lookup_eq(cnt_cur, gtbno, gtlen, &i)))
1544 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1545 if ((error = xfs_btree_delete(cnt_cur, &i)))
1547 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1549 * Delete the old by-block entry for the right block.
1551 if ((error = xfs_btree_delete(bno_cur, &i)))
1553 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1555 * Move the by-block cursor back to the left neighbor.
1557 if ((error = xfs_btree_decrement(bno_cur, 0, &i)))
1559 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1562 * Check that this is the right record: delete didn't
1563 * mangle the cursor.
1566 xfs_agblock_t xxbno;
1569 if ((error = xfs_alloc_get_rec(bno_cur, &xxbno, &xxlen,
1572 XFS_WANT_CORRUPTED_GOTO(
1573 i == 1 && xxbno == ltbno && xxlen == ltlen,
1578 * Update remaining by-block entry to the new, joined block.
1581 nlen = len + ltlen + gtlen;
1582 if ((error = xfs_alloc_update(bno_cur, nbno, nlen)))
1586 * Have only a left contiguous neighbor.
1587 * Merge it together with the new freespace.
1589 else if (haveleft) {
1591 * Delete the old by-size entry on the left.
1593 if ((error = xfs_alloc_lookup_eq(cnt_cur, ltbno, ltlen, &i)))
1595 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1596 if ((error = xfs_btree_delete(cnt_cur, &i)))
1598 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1600 * Back up the by-block cursor to the left neighbor, and
1601 * update its length.
1603 if ((error = xfs_btree_decrement(bno_cur, 0, &i)))
1605 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1608 if ((error = xfs_alloc_update(bno_cur, nbno, nlen)))
1612 * Have only a right contiguous neighbor.
1613 * Merge it together with the new freespace.
1615 else if (haveright) {
1617 * Delete the old by-size entry on the right.
1619 if ((error = xfs_alloc_lookup_eq(cnt_cur, gtbno, gtlen, &i)))
1621 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1622 if ((error = xfs_btree_delete(cnt_cur, &i)))
1624 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1626 * Update the starting block and length of the right
1627 * neighbor in the by-block tree.
1631 if ((error = xfs_alloc_update(bno_cur, nbno, nlen)))
1635 * No contiguous neighbors.
1636 * Insert the new freespace into the by-block tree.
1641 if ((error = xfs_btree_insert(bno_cur, &i)))
1643 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1645 xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
1648 * In all cases we need to insert the new freespace in the by-size tree.
1650 if ((error = xfs_alloc_lookup_eq(cnt_cur, nbno, nlen, &i)))
1652 XFS_WANT_CORRUPTED_GOTO(i == 0, error0);
1653 if ((error = xfs_btree_insert(cnt_cur, &i)))
1655 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1656 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1659 * Update the freespace totals in the ag and superblock.
1663 xfs_perag_t *pag; /* per allocation group data */
1665 pag = xfs_perag_get(mp, agno);
1666 pag->pagf_freeblks += len;
1669 agf = XFS_BUF_TO_AGF(agbp);
1670 be32_add_cpu(&agf->agf_freeblks, len);
1671 xfs_trans_agblocks_delta(tp, len);
1672 XFS_WANT_CORRUPTED_GOTO(
1673 be32_to_cpu(agf->agf_freeblks) <=
1674 be32_to_cpu(agf->agf_length),
1676 xfs_alloc_log_agf(tp, agbp, XFS_AGF_FREEBLKS);
1678 xfs_trans_mod_sb(tp, XFS_TRANS_SB_FDBLOCKS, (long)len);
1679 XFS_STATS_INC(xs_freex);
1680 XFS_STATS_ADD(xs_freeb, len);
1683 trace_xfs_free_extent(mp, agno, bno, len, isfl, haveleft, haveright);
1686 * Since blocks move to the free list without the coordination
1687 * used in xfs_bmap_finish, we can't allow block to be available
1688 * for reallocation and non-transaction writing (user data)
1689 * until we know that the transaction that moved it to the free
1690 * list is permanently on disk. We track the blocks by declaring
1691 * these blocks as "busy"; the busy list is maintained on a per-ag
1692 * basis and each transaction records which entries should be removed
1693 * when the iclog commits to disk. If a busy block is allocated,
1694 * the iclog is pushed up to the LSN that freed the block.
1696 xfs_alloc_busy_insert(tp, agno, bno, len);
1700 trace_xfs_free_extent(mp, agno, bno, len, isfl, -1, -1);
1702 xfs_btree_del_cursor(bno_cur, XFS_BTREE_ERROR);
1704 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
1709 * Visible (exported) allocation/free functions.
1710 * Some of these are used just by xfs_alloc_btree.c and this file.
1714 * Compute and fill in value of m_ag_maxlevels.
1717 xfs_alloc_compute_maxlevels(
1718 xfs_mount_t *mp) /* file system mount structure */
1726 maxleafents = (mp->m_sb.sb_agblocks + 1) / 2;
1727 minleafrecs = mp->m_alloc_mnr[0];
1728 minnoderecs = mp->m_alloc_mnr[1];
1729 maxblocks = (maxleafents + minleafrecs - 1) / minleafrecs;
1730 for (level = 1; maxblocks > 1; level++)
1731 maxblocks = (maxblocks + minnoderecs - 1) / minnoderecs;
1732 mp->m_ag_maxlevels = level;
1736 * Find the length of the longest extent in an AG.
1739 xfs_alloc_longest_free_extent(
1740 struct xfs_mount *mp,
1741 struct xfs_perag *pag)
1743 xfs_extlen_t need, delta = 0;
1745 need = XFS_MIN_FREELIST_PAG(pag, mp);
1746 if (need > pag->pagf_flcount)
1747 delta = need - pag->pagf_flcount;
1749 if (pag->pagf_longest > delta)
1750 return pag->pagf_longest - delta;
1751 return pag->pagf_flcount > 0 || pag->pagf_longest > 0;
1755 * Decide whether to use this allocation group for this allocation.
1756 * If so, fix up the btree freelist's size.
1758 STATIC int /* error */
1759 xfs_alloc_fix_freelist(
1760 xfs_alloc_arg_t *args, /* allocation argument structure */
1761 int flags) /* XFS_ALLOC_FLAG_... */
1763 xfs_buf_t *agbp; /* agf buffer pointer */
1764 xfs_agf_t *agf; /* a.g. freespace structure pointer */
1765 xfs_buf_t *agflbp;/* agfl buffer pointer */
1766 xfs_agblock_t bno; /* freelist block */
1767 xfs_extlen_t delta; /* new blocks needed in freelist */
1768 int error; /* error result code */
1769 xfs_extlen_t longest;/* longest extent in allocation group */
1770 xfs_mount_t *mp; /* file system mount point structure */
1771 xfs_extlen_t need; /* total blocks needed in freelist */
1772 xfs_perag_t *pag; /* per-ag information structure */
1773 xfs_alloc_arg_t targs; /* local allocation arguments */
1774 xfs_trans_t *tp; /* transaction pointer */
1780 if (!pag->pagf_init) {
1781 if ((error = xfs_alloc_read_agf(mp, tp, args->agno, flags,
1784 if (!pag->pagf_init) {
1785 ASSERT(flags & XFS_ALLOC_FLAG_TRYLOCK);
1786 ASSERT(!(flags & XFS_ALLOC_FLAG_FREEING));
1794 * If this is a metadata preferred pag and we are user data
1795 * then try somewhere else if we are not being asked to
1796 * try harder at this point
1798 if (pag->pagf_metadata && args->userdata &&
1799 (flags & XFS_ALLOC_FLAG_TRYLOCK)) {
1800 ASSERT(!(flags & XFS_ALLOC_FLAG_FREEING));
1805 if (!(flags & XFS_ALLOC_FLAG_FREEING)) {
1807 * If it looks like there isn't a long enough extent, or enough
1808 * total blocks, reject it.
1810 need = XFS_MIN_FREELIST_PAG(pag, mp);
1811 longest = xfs_alloc_longest_free_extent(mp, pag);
1812 if ((args->minlen + args->alignment + args->minalignslop - 1) >
1814 ((int)(pag->pagf_freeblks + pag->pagf_flcount -
1815 need - args->total) < (int)args->minleft)) {
1817 xfs_trans_brelse(tp, agbp);
1824 * Get the a.g. freespace buffer.
1825 * Can fail if we're not blocking on locks, and it's held.
1828 if ((error = xfs_alloc_read_agf(mp, tp, args->agno, flags,
1832 ASSERT(flags & XFS_ALLOC_FLAG_TRYLOCK);
1833 ASSERT(!(flags & XFS_ALLOC_FLAG_FREEING));
1839 * Figure out how many blocks we should have in the freelist.
1841 agf = XFS_BUF_TO_AGF(agbp);
1842 need = XFS_MIN_FREELIST(agf, mp);
1844 * If there isn't enough total or single-extent, reject it.
1846 if (!(flags & XFS_ALLOC_FLAG_FREEING)) {
1847 delta = need > be32_to_cpu(agf->agf_flcount) ?
1848 (need - be32_to_cpu(agf->agf_flcount)) : 0;
1849 longest = be32_to_cpu(agf->agf_longest);
1850 longest = (longest > delta) ? (longest - delta) :
1851 (be32_to_cpu(agf->agf_flcount) > 0 || longest > 0);
1852 if ((args->minlen + args->alignment + args->minalignslop - 1) >
1854 ((int)(be32_to_cpu(agf->agf_freeblks) +
1855 be32_to_cpu(agf->agf_flcount) - need - args->total) <
1856 (int)args->minleft)) {
1857 xfs_trans_brelse(tp, agbp);
1863 * Make the freelist shorter if it's too long.
1865 while (be32_to_cpu(agf->agf_flcount) > need) {
1868 error = xfs_alloc_get_freelist(tp, agbp, &bno, 0);
1871 if ((error = xfs_free_ag_extent(tp, agbp, args->agno, bno, 1, 1)))
1873 bp = xfs_btree_get_bufs(mp, tp, args->agno, bno, 0);
1874 xfs_trans_binval(tp, bp);
1877 * Initialize the args structure.
1882 targs.agno = args->agno;
1883 targs.mod = targs.minleft = targs.wasdel = targs.userdata =
1884 targs.minalignslop = 0;
1885 targs.alignment = targs.minlen = targs.prod = targs.isfl = 1;
1886 targs.type = XFS_ALLOCTYPE_THIS_AG;
1888 if ((error = xfs_alloc_read_agfl(mp, tp, targs.agno, &agflbp)))
1891 * Make the freelist longer if it's too short.
1893 while (be32_to_cpu(agf->agf_flcount) < need) {
1895 targs.maxlen = need - be32_to_cpu(agf->agf_flcount);
1897 * Allocate as many blocks as possible at once.
1899 if ((error = xfs_alloc_ag_vextent(&targs))) {
1900 xfs_trans_brelse(tp, agflbp);
1904 * Stop if we run out. Won't happen if callers are obeying
1905 * the restrictions correctly. Can happen for free calls
1906 * on a completely full ag.
1908 if (targs.agbno == NULLAGBLOCK) {
1909 if (flags & XFS_ALLOC_FLAG_FREEING)
1911 xfs_trans_brelse(tp, agflbp);
1916 * Put each allocated block on the list.
1918 for (bno = targs.agbno; bno < targs.agbno + targs.len; bno++) {
1919 error = xfs_alloc_put_freelist(tp, agbp,
1925 xfs_trans_brelse(tp, agflbp);
1931 * Get a block from the freelist.
1932 * Returns with the buffer for the block gotten.
1935 xfs_alloc_get_freelist(
1936 xfs_trans_t *tp, /* transaction pointer */
1937 xfs_buf_t *agbp, /* buffer containing the agf structure */
1938 xfs_agblock_t *bnop, /* block address retrieved from freelist */
1939 int btreeblk) /* destination is a AGF btree */
1941 xfs_agf_t *agf; /* a.g. freespace structure */
1942 xfs_agfl_t *agfl; /* a.g. freelist structure */
1943 xfs_buf_t *agflbp;/* buffer for a.g. freelist structure */
1944 xfs_agblock_t bno; /* block number returned */
1947 xfs_mount_t *mp; /* mount structure */
1948 xfs_perag_t *pag; /* per allocation group data */
1950 agf = XFS_BUF_TO_AGF(agbp);
1952 * Freelist is empty, give up.
1954 if (!agf->agf_flcount) {
1955 *bnop = NULLAGBLOCK;
1959 * Read the array of free blocks.
1962 if ((error = xfs_alloc_read_agfl(mp, tp,
1963 be32_to_cpu(agf->agf_seqno), &agflbp)))
1965 agfl = XFS_BUF_TO_AGFL(agflbp);
1967 * Get the block number and update the data structures.
1969 bno = be32_to_cpu(agfl->agfl_bno[be32_to_cpu(agf->agf_flfirst)]);
1970 be32_add_cpu(&agf->agf_flfirst, 1);
1971 xfs_trans_brelse(tp, agflbp);
1972 if (be32_to_cpu(agf->agf_flfirst) == XFS_AGFL_SIZE(mp))
1973 agf->agf_flfirst = 0;
1975 pag = xfs_perag_get(mp, be32_to_cpu(agf->agf_seqno));
1976 be32_add_cpu(&agf->agf_flcount, -1);
1977 xfs_trans_agflist_delta(tp, -1);
1978 pag->pagf_flcount--;
1981 logflags = XFS_AGF_FLFIRST | XFS_AGF_FLCOUNT;
1983 be32_add_cpu(&agf->agf_btreeblks, 1);
1984 pag->pagf_btreeblks++;
1985 logflags |= XFS_AGF_BTREEBLKS;
1988 xfs_alloc_log_agf(tp, agbp, logflags);
1992 * As blocks are freed, they are added to the per-ag busy list and
1993 * remain there until the freeing transaction is committed to disk.
1994 * Now that we have allocated blocks, this list must be searched to see
1995 * if a block is being reused. If one is, then the freeing transaction
1996 * must be pushed to disk before this transaction.
1998 * We do this by setting the current transaction to a sync transaction
1999 * which guarantees that the freeing transaction is on disk before this
2000 * transaction. This is done instead of a synchronous log force here so
2001 * that we don't sit and wait with the AGF locked in the transaction
2002 * during the log force.
2004 if (xfs_alloc_busy_search(mp, be32_to_cpu(agf->agf_seqno), bno, 1))
2005 xfs_trans_set_sync(tp);
2010 * Log the given fields from the agf structure.
2014 xfs_trans_t *tp, /* transaction pointer */
2015 xfs_buf_t *bp, /* buffer for a.g. freelist header */
2016 int fields) /* mask of fields to be logged (XFS_AGF_...) */
2018 int first; /* first byte offset */
2019 int last; /* last byte offset */
2020 static const short offsets[] = {
2021 offsetof(xfs_agf_t, agf_magicnum),
2022 offsetof(xfs_agf_t, agf_versionnum),
2023 offsetof(xfs_agf_t, agf_seqno),
2024 offsetof(xfs_agf_t, agf_length),
2025 offsetof(xfs_agf_t, agf_roots[0]),
2026 offsetof(xfs_agf_t, agf_levels[0]),
2027 offsetof(xfs_agf_t, agf_flfirst),
2028 offsetof(xfs_agf_t, agf_fllast),
2029 offsetof(xfs_agf_t, agf_flcount),
2030 offsetof(xfs_agf_t, agf_freeblks),
2031 offsetof(xfs_agf_t, agf_longest),
2032 offsetof(xfs_agf_t, agf_btreeblks),
2036 trace_xfs_agf(tp->t_mountp, XFS_BUF_TO_AGF(bp), fields, _RET_IP_);
2038 xfs_btree_offsets(fields, offsets, XFS_AGF_NUM_BITS, &first, &last);
2039 xfs_trans_log_buf(tp, bp, (uint)first, (uint)last);
2043 * Interface for inode allocation to force the pag data to be initialized.
2046 xfs_alloc_pagf_init(
2047 xfs_mount_t *mp, /* file system mount structure */
2048 xfs_trans_t *tp, /* transaction pointer */
2049 xfs_agnumber_t agno, /* allocation group number */
2050 int flags) /* XFS_ALLOC_FLAGS_... */
2055 if ((error = xfs_alloc_read_agf(mp, tp, agno, flags, &bp)))
2058 xfs_trans_brelse(tp, bp);
2063 * Put the block on the freelist for the allocation group.
2066 xfs_alloc_put_freelist(
2067 xfs_trans_t *tp, /* transaction pointer */
2068 xfs_buf_t *agbp, /* buffer for a.g. freelist header */
2069 xfs_buf_t *agflbp,/* buffer for a.g. free block array */
2070 xfs_agblock_t bno, /* block being freed */
2071 int btreeblk) /* block came from a AGF btree */
2073 xfs_agf_t *agf; /* a.g. freespace structure */
2074 xfs_agfl_t *agfl; /* a.g. free block array */
2075 __be32 *blockp;/* pointer to array entry */
2078 xfs_mount_t *mp; /* mount structure */
2079 xfs_perag_t *pag; /* per allocation group data */
2081 agf = XFS_BUF_TO_AGF(agbp);
2084 if (!agflbp && (error = xfs_alloc_read_agfl(mp, tp,
2085 be32_to_cpu(agf->agf_seqno), &agflbp)))
2087 agfl = XFS_BUF_TO_AGFL(agflbp);
2088 be32_add_cpu(&agf->agf_fllast, 1);
2089 if (be32_to_cpu(agf->agf_fllast) == XFS_AGFL_SIZE(mp))
2090 agf->agf_fllast = 0;
2092 pag = xfs_perag_get(mp, be32_to_cpu(agf->agf_seqno));
2093 be32_add_cpu(&agf->agf_flcount, 1);
2094 xfs_trans_agflist_delta(tp, 1);
2095 pag->pagf_flcount++;
2097 logflags = XFS_AGF_FLLAST | XFS_AGF_FLCOUNT;
2099 be32_add_cpu(&agf->agf_btreeblks, -1);
2100 pag->pagf_btreeblks--;
2101 logflags |= XFS_AGF_BTREEBLKS;
2105 xfs_alloc_log_agf(tp, agbp, logflags);
2107 ASSERT(be32_to_cpu(agf->agf_flcount) <= XFS_AGFL_SIZE(mp));
2108 blockp = &agfl->agfl_bno[be32_to_cpu(agf->agf_fllast)];
2109 *blockp = cpu_to_be32(bno);
2110 xfs_alloc_log_agf(tp, agbp, logflags);
2111 xfs_trans_log_buf(tp, agflbp,
2112 (int)((xfs_caddr_t)blockp - (xfs_caddr_t)agfl),
2113 (int)((xfs_caddr_t)blockp - (xfs_caddr_t)agfl +
2114 sizeof(xfs_agblock_t) - 1));
2119 * Read in the allocation group header (free/alloc section).
2123 struct xfs_mount *mp, /* mount point structure */
2124 struct xfs_trans *tp, /* transaction pointer */
2125 xfs_agnumber_t agno, /* allocation group number */
2126 int flags, /* XFS_BUF_ */
2127 struct xfs_buf **bpp) /* buffer for the ag freelist header */
2129 struct xfs_agf *agf; /* ag freelist header */
2130 int agf_ok; /* set if agf is consistent */
2133 ASSERT(agno != NULLAGNUMBER);
2134 error = xfs_trans_read_buf(
2135 mp, tp, mp->m_ddev_targp,
2136 XFS_AG_DADDR(mp, agno, XFS_AGF_DADDR(mp)),
2137 XFS_FSS_TO_BB(mp, 1), flags, bpp);
2143 ASSERT(!XFS_BUF_GETERROR(*bpp));
2144 agf = XFS_BUF_TO_AGF(*bpp);
2147 * Validate the magic number of the agf block.
2150 be32_to_cpu(agf->agf_magicnum) == XFS_AGF_MAGIC &&
2151 XFS_AGF_GOOD_VERSION(be32_to_cpu(agf->agf_versionnum)) &&
2152 be32_to_cpu(agf->agf_freeblks) <= be32_to_cpu(agf->agf_length) &&
2153 be32_to_cpu(agf->agf_flfirst) < XFS_AGFL_SIZE(mp) &&
2154 be32_to_cpu(agf->agf_fllast) < XFS_AGFL_SIZE(mp) &&
2155 be32_to_cpu(agf->agf_flcount) <= XFS_AGFL_SIZE(mp) &&
2156 be32_to_cpu(agf->agf_seqno) == agno;
2157 if (xfs_sb_version_haslazysbcount(&mp->m_sb))
2158 agf_ok = agf_ok && be32_to_cpu(agf->agf_btreeblks) <=
2159 be32_to_cpu(agf->agf_length);
2160 if (unlikely(XFS_TEST_ERROR(!agf_ok, mp, XFS_ERRTAG_ALLOC_READ_AGF,
2161 XFS_RANDOM_ALLOC_READ_AGF))) {
2162 XFS_CORRUPTION_ERROR("xfs_alloc_read_agf",
2163 XFS_ERRLEVEL_LOW, mp, agf);
2164 xfs_trans_brelse(tp, *bpp);
2165 return XFS_ERROR(EFSCORRUPTED);
2167 XFS_BUF_SET_VTYPE_REF(*bpp, B_FS_AGF, XFS_AGF_REF);
2172 * Read in the allocation group header (free/alloc section).
2176 struct xfs_mount *mp, /* mount point structure */
2177 struct xfs_trans *tp, /* transaction pointer */
2178 xfs_agnumber_t agno, /* allocation group number */
2179 int flags, /* XFS_ALLOC_FLAG_... */
2180 struct xfs_buf **bpp) /* buffer for the ag freelist header */
2182 struct xfs_agf *agf; /* ag freelist header */
2183 struct xfs_perag *pag; /* per allocation group data */
2186 ASSERT(agno != NULLAGNUMBER);
2188 error = xfs_read_agf(mp, tp, agno,
2189 (flags & XFS_ALLOC_FLAG_TRYLOCK) ? XBF_TRYLOCK : 0,
2195 ASSERT(!XFS_BUF_GETERROR(*bpp));
2197 agf = XFS_BUF_TO_AGF(*bpp);
2198 pag = xfs_perag_get(mp, agno);
2199 if (!pag->pagf_init) {
2200 pag->pagf_freeblks = be32_to_cpu(agf->agf_freeblks);
2201 pag->pagf_btreeblks = be32_to_cpu(agf->agf_btreeblks);
2202 pag->pagf_flcount = be32_to_cpu(agf->agf_flcount);
2203 pag->pagf_longest = be32_to_cpu(agf->agf_longest);
2204 pag->pagf_levels[XFS_BTNUM_BNOi] =
2205 be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNOi]);
2206 pag->pagf_levels[XFS_BTNUM_CNTi] =
2207 be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNTi]);
2208 spin_lock_init(&pag->pagb_lock);
2209 pag->pagb_count = 0;
2210 pag->pagb_tree = RB_ROOT;
2214 else if (!XFS_FORCED_SHUTDOWN(mp)) {
2215 ASSERT(pag->pagf_freeblks == be32_to_cpu(agf->agf_freeblks));
2216 ASSERT(pag->pagf_btreeblks == be32_to_cpu(agf->agf_btreeblks));
2217 ASSERT(pag->pagf_flcount == be32_to_cpu(agf->agf_flcount));
2218 ASSERT(pag->pagf_longest == be32_to_cpu(agf->agf_longest));
2219 ASSERT(pag->pagf_levels[XFS_BTNUM_BNOi] ==
2220 be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNOi]));
2221 ASSERT(pag->pagf_levels[XFS_BTNUM_CNTi] ==
2222 be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNTi]));
2230 * Allocate an extent (variable-size).
2231 * Depending on the allocation type, we either look in a single allocation
2232 * group or loop over the allocation groups to find the result.
2236 xfs_alloc_arg_t *args) /* allocation argument structure */
2238 xfs_agblock_t agsize; /* allocation group size */
2240 int flags; /* XFS_ALLOC_FLAG_... locking flags */
2241 xfs_extlen_t minleft;/* minimum left value, temp copy */
2242 xfs_mount_t *mp; /* mount structure pointer */
2243 xfs_agnumber_t sagno; /* starting allocation group number */
2244 xfs_alloctype_t type; /* input allocation type */
2247 xfs_agnumber_t rotorstep = xfs_rotorstep; /* inode32 agf stepper */
2250 type = args->otype = args->type;
2251 args->agbno = NULLAGBLOCK;
2253 * Just fix this up, for the case where the last a.g. is shorter
2254 * (or there's only one a.g.) and the caller couldn't easily figure
2255 * that out (xfs_bmap_alloc).
2257 agsize = mp->m_sb.sb_agblocks;
2258 if (args->maxlen > agsize)
2259 args->maxlen = agsize;
2260 if (args->alignment == 0)
2261 args->alignment = 1;
2262 ASSERT(XFS_FSB_TO_AGNO(mp, args->fsbno) < mp->m_sb.sb_agcount);
2263 ASSERT(XFS_FSB_TO_AGBNO(mp, args->fsbno) < agsize);
2264 ASSERT(args->minlen <= args->maxlen);
2265 ASSERT(args->minlen <= agsize);
2266 ASSERT(args->mod < args->prod);
2267 if (XFS_FSB_TO_AGNO(mp, args->fsbno) >= mp->m_sb.sb_agcount ||
2268 XFS_FSB_TO_AGBNO(mp, args->fsbno) >= agsize ||
2269 args->minlen > args->maxlen || args->minlen > agsize ||
2270 args->mod >= args->prod) {
2271 args->fsbno = NULLFSBLOCK;
2272 trace_xfs_alloc_vextent_badargs(args);
2275 minleft = args->minleft;
2278 case XFS_ALLOCTYPE_THIS_AG:
2279 case XFS_ALLOCTYPE_NEAR_BNO:
2280 case XFS_ALLOCTYPE_THIS_BNO:
2282 * These three force us into a single a.g.
2284 args->agno = XFS_FSB_TO_AGNO(mp, args->fsbno);
2285 args->pag = xfs_perag_get(mp, args->agno);
2287 error = xfs_alloc_fix_freelist(args, 0);
2288 args->minleft = minleft;
2290 trace_xfs_alloc_vextent_nofix(args);
2294 trace_xfs_alloc_vextent_noagbp(args);
2297 args->agbno = XFS_FSB_TO_AGBNO(mp, args->fsbno);
2298 if ((error = xfs_alloc_ag_vextent(args)))
2301 case XFS_ALLOCTYPE_START_BNO:
2303 * Try near allocation first, then anywhere-in-ag after
2304 * the first a.g. fails.
2306 if ((args->userdata == XFS_ALLOC_INITIAL_USER_DATA) &&
2307 (mp->m_flags & XFS_MOUNT_32BITINODES)) {
2308 args->fsbno = XFS_AGB_TO_FSB(mp,
2309 ((mp->m_agfrotor / rotorstep) %
2310 mp->m_sb.sb_agcount), 0);
2313 args->agbno = XFS_FSB_TO_AGBNO(mp, args->fsbno);
2314 args->type = XFS_ALLOCTYPE_NEAR_BNO;
2316 case XFS_ALLOCTYPE_ANY_AG:
2317 case XFS_ALLOCTYPE_START_AG:
2318 case XFS_ALLOCTYPE_FIRST_AG:
2320 * Rotate through the allocation groups looking for a winner.
2322 if (type == XFS_ALLOCTYPE_ANY_AG) {
2324 * Start with the last place we left off.
2326 args->agno = sagno = (mp->m_agfrotor / rotorstep) %
2327 mp->m_sb.sb_agcount;
2328 args->type = XFS_ALLOCTYPE_THIS_AG;
2329 flags = XFS_ALLOC_FLAG_TRYLOCK;
2330 } else if (type == XFS_ALLOCTYPE_FIRST_AG) {
2332 * Start with allocation group given by bno.
2334 args->agno = XFS_FSB_TO_AGNO(mp, args->fsbno);
2335 args->type = XFS_ALLOCTYPE_THIS_AG;
2339 if (type == XFS_ALLOCTYPE_START_AG)
2340 args->type = XFS_ALLOCTYPE_THIS_AG;
2342 * Start with the given allocation group.
2344 args->agno = sagno = XFS_FSB_TO_AGNO(mp, args->fsbno);
2345 flags = XFS_ALLOC_FLAG_TRYLOCK;
2348 * Loop over allocation groups twice; first time with
2349 * trylock set, second time without.
2352 args->pag = xfs_perag_get(mp, args->agno);
2353 if (no_min) args->minleft = 0;
2354 error = xfs_alloc_fix_freelist(args, flags);
2355 args->minleft = minleft;
2357 trace_xfs_alloc_vextent_nofix(args);
2361 * If we get a buffer back then the allocation will fly.
2364 if ((error = xfs_alloc_ag_vextent(args)))
2369 trace_xfs_alloc_vextent_loopfailed(args);
2372 * Didn't work, figure out the next iteration.
2374 if (args->agno == sagno &&
2375 type == XFS_ALLOCTYPE_START_BNO)
2376 args->type = XFS_ALLOCTYPE_THIS_AG;
2378 * For the first allocation, we can try any AG to get
2379 * space. However, if we already have allocated a
2380 * block, we don't want to try AGs whose number is below
2381 * sagno. Otherwise, we may end up with out-of-order
2382 * locking of AGF, which might cause deadlock.
2384 if (++(args->agno) == mp->m_sb.sb_agcount) {
2385 if (args->firstblock != NULLFSBLOCK)
2391 * Reached the starting a.g., must either be done
2392 * or switch to non-trylock mode.
2394 if (args->agno == sagno) {
2396 args->agbno = NULLAGBLOCK;
2397 trace_xfs_alloc_vextent_allfailed(args);
2404 if (type == XFS_ALLOCTYPE_START_BNO) {
2405 args->agbno = XFS_FSB_TO_AGBNO(mp,
2407 args->type = XFS_ALLOCTYPE_NEAR_BNO;
2411 xfs_perag_put(args->pag);
2413 if (bump_rotor || (type == XFS_ALLOCTYPE_ANY_AG)) {
2414 if (args->agno == sagno)
2415 mp->m_agfrotor = (mp->m_agfrotor + 1) %
2416 (mp->m_sb.sb_agcount * rotorstep);
2418 mp->m_agfrotor = (args->agno * rotorstep + 1) %
2419 (mp->m_sb.sb_agcount * rotorstep);
2426 if (args->agbno == NULLAGBLOCK)
2427 args->fsbno = NULLFSBLOCK;
2429 args->fsbno = XFS_AGB_TO_FSB(mp, args->agno, args->agbno);
2431 ASSERT(args->len >= args->minlen);
2432 ASSERT(args->len <= args->maxlen);
2433 ASSERT(args->agbno % args->alignment == 0);
2434 XFS_AG_CHECK_DADDR(mp, XFS_FSB_TO_DADDR(mp, args->fsbno),
2438 xfs_perag_put(args->pag);
2441 xfs_perag_put(args->pag);
2447 * Just break up the extent address and hand off to xfs_free_ag_extent
2448 * after fixing up the freelist.
2452 xfs_trans_t *tp, /* transaction pointer */
2453 xfs_fsblock_t bno, /* starting block number of extent */
2454 xfs_extlen_t len) /* length of extent */
2456 xfs_alloc_arg_t args;
2460 memset(&args, 0, sizeof(xfs_alloc_arg_t));
2462 args.mp = tp->t_mountp;
2463 args.agno = XFS_FSB_TO_AGNO(args.mp, bno);
2464 ASSERT(args.agno < args.mp->m_sb.sb_agcount);
2465 args.agbno = XFS_FSB_TO_AGBNO(args.mp, bno);
2466 args.pag = xfs_perag_get(args.mp, args.agno);
2467 if ((error = xfs_alloc_fix_freelist(&args, XFS_ALLOC_FLAG_FREEING)))
2470 ASSERT(args.agbp != NULL);
2471 ASSERT((args.agbno + len) <=
2472 be32_to_cpu(XFS_BUF_TO_AGF(args.agbp)->agf_length));
2474 error = xfs_free_ag_extent(tp, args.agbp, args.agno, args.agbno, len, 0);
2476 xfs_perag_put(args.pag);
2482 * AG Busy list management
2483 * The busy list contains block ranges that have been freed but whose
2484 * transactions have not yet hit disk. If any block listed in a busy
2485 * list is reused, the transaction that freed it must be forced to disk
2486 * before continuing to use the block.
2488 * xfs_alloc_busy_insert - add to the per-ag busy list
2489 * xfs_alloc_busy_clear - remove an item from the per-ag busy list
2490 * xfs_alloc_busy_search - search for a busy extent
2494 * Insert a new extent into the busy tree.
2496 * The busy extent tree is indexed by the start block of the busy extent.
2497 * there can be multiple overlapping ranges in the busy extent tree but only
2498 * ever one entry at a given start block. The reason for this is that
2499 * multi-block extents can be freed, then smaller chunks of that extent
2500 * allocated and freed again before the first transaction commit is on disk.
2501 * If the exact same start block is freed a second time, we have to wait for
2502 * that busy extent to pass out of the tree before the new extent is inserted.
2503 * There are two main cases we have to handle here.
2505 * The first case is a transaction that triggers a "free - allocate - free"
2506 * cycle. This can occur during btree manipulations as a btree block is freed
2507 * to the freelist, then allocated from the free list, then freed again. In
2508 * this case, the second extxpnet free is what triggers the duplicate and as
2509 * such the transaction IDs should match. Because the extent was allocated in
2510 * this transaction, the transaction must be marked as synchronous. This is
2511 * true for all cases where the free/alloc/free occurs in the one transaction,
2512 * hence the addition of the ASSERT(tp->t_flags & XFS_TRANS_SYNC) to this case.
2513 * This serves to catch violations of the second case quite effectively.
2515 * The second case is where the free/alloc/free occur in different
2516 * transactions. In this case, the thread freeing the extent the second time
2517 * can't mark the extent busy immediately because it is already tracked in a
2518 * transaction that may be committing. When the log commit for the existing
2519 * busy extent completes, the busy extent will be removed from the tree. If we
2520 * allow the second busy insert to continue using that busy extent structure,
2521 * it can be freed before this transaction is safely in the log. Hence our
2522 * only option in this case is to force the log to remove the existing busy
2523 * extent from the list before we insert the new one with the current
2526 * The problem we are trying to avoid in the free-alloc-free in separate
2527 * transactions is most easily described with a timeline:
2529 * Thread 1 Thread 2 Thread 3 xfslogd
2552 * checkpoint completes
2554 * By issuing a log force in thread 3 @ "KABOOM", the thread will block until
2555 * the checkpoint completes, and the busy extent it matched will have been
2556 * removed from the tree when it is woken. Hence it can then continue safely.
2558 * However, to ensure this matching process is robust, we need to use the
2559 * transaction ID for identifying transaction, as delayed logging results in
2560 * the busy extent and transaction lifecycles being different. i.e. the busy
2561 * extent is active for a lot longer than the transaction. Hence the
2562 * transaction structure can be freed and reallocated, then mark the same
2563 * extent busy again in the new transaction. In this case the new transaction
2564 * will have a different tid but can have the same address, and hence we need
2565 * to check against the tid.
2567 * Future: for delayed logging, we could avoid the log force if the extent was
2568 * first freed in the current checkpoint sequence. This, however, requires the
2569 * ability to pin the current checkpoint in memory until this transaction
2570 * commits to ensure that both the original free and the current one combine
2571 * logically into the one checkpoint. If the checkpoint sequences are
2572 * different, however, we still need to wait on a log force.
2575 xfs_alloc_busy_insert(
2576 struct xfs_trans *tp,
2577 xfs_agnumber_t agno,
2581 struct xfs_busy_extent *new;
2582 struct xfs_busy_extent *busyp;
2583 struct xfs_perag *pag;
2584 struct rb_node **rbp;
2585 struct rb_node *parent;
2589 new = kmem_zalloc(sizeof(struct xfs_busy_extent), KM_MAYFAIL);
2592 * No Memory! Since it is now not possible to track the free
2593 * block, make this a synchronous transaction to insure that
2594 * the block is not reused before this transaction commits.
2596 trace_xfs_alloc_busy(tp, agno, bno, len, 1);
2597 xfs_trans_set_sync(tp);
2604 new->tid = xfs_log_get_trans_ident(tp);
2606 INIT_LIST_HEAD(&new->list);
2608 /* trace before insert to be able to see failed inserts */
2609 trace_xfs_alloc_busy(tp, agno, bno, len, 0);
2611 pag = xfs_perag_get(tp->t_mountp, new->agno);
2613 spin_lock(&pag->pagb_lock);
2614 rbp = &pag->pagb_tree.rb_node;
2618 while (*rbp && match >= 0) {
2620 busyp = rb_entry(parent, struct xfs_busy_extent, rb_node);
2622 if (new->bno < busyp->bno) {
2623 /* may overlap, but exact start block is lower */
2624 rbp = &(*rbp)->rb_left;
2625 if (new->bno + new->length > busyp->bno)
2626 match = busyp->tid == new->tid ? 1 : -1;
2627 } else if (new->bno > busyp->bno) {
2628 /* may overlap, but exact start block is higher */
2629 rbp = &(*rbp)->rb_right;
2630 if (bno < busyp->bno + busyp->length)
2631 match = busyp->tid == new->tid ? 1 : -1;
2633 match = busyp->tid == new->tid ? 1 : -1;
2638 /* overlap marked busy in different transaction */
2639 spin_unlock(&pag->pagb_lock);
2640 xfs_log_force(tp->t_mountp, XFS_LOG_SYNC);
2645 * overlap marked busy in same transaction. Update if exact
2646 * start block match, otherwise combine the busy extents into
2649 if (busyp->bno == new->bno) {
2650 busyp->length = max(busyp->length, new->length);
2651 spin_unlock(&pag->pagb_lock);
2652 ASSERT(tp->t_flags & XFS_TRANS_SYNC);
2657 rb_erase(&busyp->rb_node, &pag->pagb_tree);
2658 new->length = max(busyp->bno + busyp->length,
2659 new->bno + new->length) -
2660 min(busyp->bno, new->bno);
2661 new->bno = min(busyp->bno, new->bno);
2665 rb_link_node(&new->rb_node, parent, rbp);
2666 rb_insert_color(&new->rb_node, &pag->pagb_tree);
2668 list_add(&new->list, &tp->t_busy);
2669 spin_unlock(&pag->pagb_lock);
2675 * Search for a busy extent within the range of the extent we are about to
2676 * allocate. You need to be holding the busy extent tree lock when calling
2677 * xfs_alloc_busy_search(). This function returns 0 for no overlapping busy
2678 * extent, -1 for an overlapping but not exact busy extent, and 1 for an exact
2679 * match. This is done so that a non-zero return indicates an overlap that
2680 * will require a synchronous transaction, but it can still be
2681 * used to distinguish between a partial or exact match.
2684 xfs_alloc_busy_search(
2685 struct xfs_mount *mp,
2686 xfs_agnumber_t agno,
2690 struct xfs_perag *pag;
2691 struct rb_node *rbp;
2692 struct xfs_busy_extent *busyp;
2695 pag = xfs_perag_get(mp, agno);
2696 spin_lock(&pag->pagb_lock);
2698 rbp = pag->pagb_tree.rb_node;
2700 /* find closest start bno overlap */
2702 busyp = rb_entry(rbp, struct xfs_busy_extent, rb_node);
2703 if (bno < busyp->bno) {
2704 /* may overlap, but exact start block is lower */
2705 if (bno + len > busyp->bno)
2708 } else if (bno > busyp->bno) {
2709 /* may overlap, but exact start block is higher */
2710 if (bno < busyp->bno + busyp->length)
2712 rbp = rbp->rb_right;
2714 /* bno matches busyp, length determines exact match */
2715 match = (busyp->length == len) ? 1 : -1;
2719 spin_unlock(&pag->pagb_lock);
2720 trace_xfs_alloc_busysearch(mp, agno, bno, len, !!match);
2726 xfs_alloc_busy_clear(
2727 struct xfs_mount *mp,
2728 struct xfs_busy_extent *busyp)
2730 struct xfs_perag *pag;
2732 trace_xfs_alloc_unbusy(mp, busyp->agno, busyp->bno,
2735 ASSERT(xfs_alloc_busy_search(mp, busyp->agno, busyp->bno,
2736 busyp->length) == 1);
2738 list_del_init(&busyp->list);
2740 pag = xfs_perag_get(mp, busyp->agno);
2741 spin_lock(&pag->pagb_lock);
2742 rb_erase(&busyp->rb_node, &pag->pagb_tree);
2743 spin_unlock(&pag->pagb_lock);