xfs: do not immediately reuse busy extent ranges
[linux-2.6.git] / fs / xfs / xfs_alloc.c
1 /*
2  * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc.
3  * All Rights Reserved.
4  *
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.
8  *
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.
13  *
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
17  */
18 #include "xfs.h"
19 #include "xfs_fs.h"
20 #include "xfs_types.h"
21 #include "xfs_bit.h"
22 #include "xfs_log.h"
23 #include "xfs_inum.h"
24 #include "xfs_trans.h"
25 #include "xfs_sb.h"
26 #include "xfs_ag.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"
37
38
39 #define XFS_ABSDIFF(a,b)        (((a) <= (b)) ? ((b) - (a)) : ((a) - (b)))
40
41 #define XFSA_FIXUP_BNO_OK       1
42 #define XFSA_FIXUP_CNT_OK       2
43
44 STATIC int xfs_alloc_ag_vextent_exact(xfs_alloc_arg_t *);
45 STATIC int xfs_alloc_ag_vextent_near(xfs_alloc_arg_t *);
46 STATIC int xfs_alloc_ag_vextent_size(xfs_alloc_arg_t *);
47 STATIC int xfs_alloc_ag_vextent_small(xfs_alloc_arg_t *,
48                 xfs_btree_cur_t *, xfs_agblock_t *, xfs_extlen_t *, int *);
49 STATIC void xfs_alloc_busy_trim(struct xfs_alloc_arg *,
50                 xfs_agblock_t, xfs_extlen_t, xfs_agblock_t *, xfs_extlen_t *);
51
52 /*
53  * Lookup the record equal to [bno, len] in the btree given by cur.
54  */
55 STATIC int                              /* error */
56 xfs_alloc_lookup_eq(
57         struct xfs_btree_cur    *cur,   /* btree cursor */
58         xfs_agblock_t           bno,    /* starting block of extent */
59         xfs_extlen_t            len,    /* length of extent */
60         int                     *stat)  /* success/failure */
61 {
62         cur->bc_rec.a.ar_startblock = bno;
63         cur->bc_rec.a.ar_blockcount = len;
64         return xfs_btree_lookup(cur, XFS_LOOKUP_EQ, stat);
65 }
66
67 /*
68  * Lookup the first record greater than or equal to [bno, len]
69  * in the btree given by cur.
70  */
71 STATIC int                              /* error */
72 xfs_alloc_lookup_ge(
73         struct xfs_btree_cur    *cur,   /* btree cursor */
74         xfs_agblock_t           bno,    /* starting block of extent */
75         xfs_extlen_t            len,    /* length of extent */
76         int                     *stat)  /* success/failure */
77 {
78         cur->bc_rec.a.ar_startblock = bno;
79         cur->bc_rec.a.ar_blockcount = len;
80         return xfs_btree_lookup(cur, XFS_LOOKUP_GE, stat);
81 }
82
83 /*
84  * Lookup the first record less than or equal to [bno, len]
85  * in the btree given by cur.
86  */
87 int                                     /* error */
88 xfs_alloc_lookup_le(
89         struct xfs_btree_cur    *cur,   /* btree cursor */
90         xfs_agblock_t           bno,    /* starting block of extent */
91         xfs_extlen_t            len,    /* length of extent */
92         int                     *stat)  /* success/failure */
93 {
94         cur->bc_rec.a.ar_startblock = bno;
95         cur->bc_rec.a.ar_blockcount = len;
96         return xfs_btree_lookup(cur, XFS_LOOKUP_LE, stat);
97 }
98
99 /*
100  * Update the record referred to by cur to the value given
101  * by [bno, len].
102  * This either works (return 0) or gets an EFSCORRUPTED error.
103  */
104 STATIC int                              /* error */
105 xfs_alloc_update(
106         struct xfs_btree_cur    *cur,   /* btree cursor */
107         xfs_agblock_t           bno,    /* starting block of extent */
108         xfs_extlen_t            len)    /* length of extent */
109 {
110         union xfs_btree_rec     rec;
111
112         rec.alloc.ar_startblock = cpu_to_be32(bno);
113         rec.alloc.ar_blockcount = cpu_to_be32(len);
114         return xfs_btree_update(cur, &rec);
115 }
116
117 /*
118  * Get the data from the pointed-to record.
119  */
120 int                                     /* error */
121 xfs_alloc_get_rec(
122         struct xfs_btree_cur    *cur,   /* btree cursor */
123         xfs_agblock_t           *bno,   /* output: starting block of extent */
124         xfs_extlen_t            *len,   /* output: length of extent */
125         int                     *stat)  /* output: success/failure */
126 {
127         union xfs_btree_rec     *rec;
128         int                     error;
129
130         error = xfs_btree_get_rec(cur, &rec, stat);
131         if (!error && *stat == 1) {
132                 *bno = be32_to_cpu(rec->alloc.ar_startblock);
133                 *len = be32_to_cpu(rec->alloc.ar_blockcount);
134         }
135         return error;
136 }
137
138 /*
139  * Compute aligned version of the found extent.
140  * Takes alignment and min length into account.
141  */
142 STATIC void
143 xfs_alloc_compute_aligned(
144         xfs_alloc_arg_t *args,          /* allocation argument structure */
145         xfs_agblock_t   foundbno,       /* starting block in found extent */
146         xfs_extlen_t    foundlen,       /* length in found extent */
147         xfs_agblock_t   *resbno,        /* result block number */
148         xfs_extlen_t    *reslen)        /* result length */
149 {
150         xfs_agblock_t   bno;
151         xfs_extlen_t    len;
152
153         /* Trim busy sections out of found extent */
154         xfs_alloc_busy_trim(args, foundbno, foundlen, &bno, &len);
155
156         if (args->alignment > 1 && len >= args->minlen) {
157                 xfs_agblock_t   aligned_bno = roundup(bno, args->alignment);
158                 xfs_extlen_t    diff = aligned_bno - bno;
159
160                 *resbno = aligned_bno;
161                 *reslen = diff >= len ? 0 : len - diff;
162         } else {
163                 *resbno = bno;
164                 *reslen = len;
165         }
166 }
167
168 /*
169  * Compute best start block and diff for "near" allocations.
170  * freelen >= wantlen already checked by caller.
171  */
172 STATIC xfs_extlen_t                     /* difference value (absolute) */
173 xfs_alloc_compute_diff(
174         xfs_agblock_t   wantbno,        /* target starting block */
175         xfs_extlen_t    wantlen,        /* target length */
176         xfs_extlen_t    alignment,      /* target alignment */
177         xfs_agblock_t   freebno,        /* freespace's starting block */
178         xfs_extlen_t    freelen,        /* freespace's length */
179         xfs_agblock_t   *newbnop)       /* result: best start block from free */
180 {
181         xfs_agblock_t   freeend;        /* end of freespace extent */
182         xfs_agblock_t   newbno1;        /* return block number */
183         xfs_agblock_t   newbno2;        /* other new block number */
184         xfs_extlen_t    newlen1=0;      /* length with newbno1 */
185         xfs_extlen_t    newlen2=0;      /* length with newbno2 */
186         xfs_agblock_t   wantend;        /* end of target extent */
187
188         ASSERT(freelen >= wantlen);
189         freeend = freebno + freelen;
190         wantend = wantbno + wantlen;
191         if (freebno >= wantbno) {
192                 if ((newbno1 = roundup(freebno, alignment)) >= freeend)
193                         newbno1 = NULLAGBLOCK;
194         } else if (freeend >= wantend && alignment > 1) {
195                 newbno1 = roundup(wantbno, alignment);
196                 newbno2 = newbno1 - alignment;
197                 if (newbno1 >= freeend)
198                         newbno1 = NULLAGBLOCK;
199                 else
200                         newlen1 = XFS_EXTLEN_MIN(wantlen, freeend - newbno1);
201                 if (newbno2 < freebno)
202                         newbno2 = NULLAGBLOCK;
203                 else
204                         newlen2 = XFS_EXTLEN_MIN(wantlen, freeend - newbno2);
205                 if (newbno1 != NULLAGBLOCK && newbno2 != NULLAGBLOCK) {
206                         if (newlen1 < newlen2 ||
207                             (newlen1 == newlen2 &&
208                              XFS_ABSDIFF(newbno1, wantbno) >
209                              XFS_ABSDIFF(newbno2, wantbno)))
210                                 newbno1 = newbno2;
211                 } else if (newbno2 != NULLAGBLOCK)
212                         newbno1 = newbno2;
213         } else if (freeend >= wantend) {
214                 newbno1 = wantbno;
215         } else if (alignment > 1) {
216                 newbno1 = roundup(freeend - wantlen, alignment);
217                 if (newbno1 > freeend - wantlen &&
218                     newbno1 - alignment >= freebno)
219                         newbno1 -= alignment;
220                 else if (newbno1 >= freeend)
221                         newbno1 = NULLAGBLOCK;
222         } else
223                 newbno1 = freeend - wantlen;
224         *newbnop = newbno1;
225         return newbno1 == NULLAGBLOCK ? 0 : XFS_ABSDIFF(newbno1, wantbno);
226 }
227
228 /*
229  * Fix up the length, based on mod and prod.
230  * len should be k * prod + mod for some k.
231  * If len is too small it is returned unchanged.
232  * If len hits maxlen it is left alone.
233  */
234 STATIC void
235 xfs_alloc_fix_len(
236         xfs_alloc_arg_t *args)          /* allocation argument structure */
237 {
238         xfs_extlen_t    k;
239         xfs_extlen_t    rlen;
240
241         ASSERT(args->mod < args->prod);
242         rlen = args->len;
243         ASSERT(rlen >= args->minlen);
244         ASSERT(rlen <= args->maxlen);
245         if (args->prod <= 1 || rlen < args->mod || rlen == args->maxlen ||
246             (args->mod == 0 && rlen < args->prod))
247                 return;
248         k = rlen % args->prod;
249         if (k == args->mod)
250                 return;
251         if (k > args->mod) {
252                 if ((int)(rlen = rlen - k - args->mod) < (int)args->minlen)
253                         return;
254         } else {
255                 if ((int)(rlen = rlen - args->prod - (args->mod - k)) <
256                     (int)args->minlen)
257                         return;
258         }
259         ASSERT(rlen >= args->minlen);
260         ASSERT(rlen <= args->maxlen);
261         args->len = rlen;
262 }
263
264 /*
265  * Fix up length if there is too little space left in the a.g.
266  * Return 1 if ok, 0 if too little, should give up.
267  */
268 STATIC int
269 xfs_alloc_fix_minleft(
270         xfs_alloc_arg_t *args)          /* allocation argument structure */
271 {
272         xfs_agf_t       *agf;           /* a.g. freelist header */
273         int             diff;           /* free space difference */
274
275         if (args->minleft == 0)
276                 return 1;
277         agf = XFS_BUF_TO_AGF(args->agbp);
278         diff = be32_to_cpu(agf->agf_freeblks)
279                 + be32_to_cpu(agf->agf_flcount)
280                 - args->len - args->minleft;
281         if (diff >= 0)
282                 return 1;
283         args->len += diff;              /* shrink the allocated space */
284         if (args->len >= args->minlen)
285                 return 1;
286         args->agbno = NULLAGBLOCK;
287         return 0;
288 }
289
290 /*
291  * Update the two btrees, logically removing from freespace the extent
292  * starting at rbno, rlen blocks.  The extent is contained within the
293  * actual (current) free extent fbno for flen blocks.
294  * Flags are passed in indicating whether the cursors are set to the
295  * relevant records.
296  */
297 STATIC int                              /* error code */
298 xfs_alloc_fixup_trees(
299         xfs_btree_cur_t *cnt_cur,       /* cursor for by-size btree */
300         xfs_btree_cur_t *bno_cur,       /* cursor for by-block btree */
301         xfs_agblock_t   fbno,           /* starting block of free extent */
302         xfs_extlen_t    flen,           /* length of free extent */
303         xfs_agblock_t   rbno,           /* starting block of returned extent */
304         xfs_extlen_t    rlen,           /* length of returned extent */
305         int             flags)          /* flags, XFSA_FIXUP_... */
306 {
307         int             error;          /* error code */
308         int             i;              /* operation results */
309         xfs_agblock_t   nfbno1;         /* first new free startblock */
310         xfs_agblock_t   nfbno2;         /* second new free startblock */
311         xfs_extlen_t    nflen1=0;       /* first new free length */
312         xfs_extlen_t    nflen2=0;       /* second new free length */
313
314         /*
315          * Look up the record in the by-size tree if necessary.
316          */
317         if (flags & XFSA_FIXUP_CNT_OK) {
318 #ifdef DEBUG
319                 if ((error = xfs_alloc_get_rec(cnt_cur, &nfbno1, &nflen1, &i)))
320                         return error;
321                 XFS_WANT_CORRUPTED_RETURN(
322                         i == 1 && nfbno1 == fbno && nflen1 == flen);
323 #endif
324         } else {
325                 if ((error = xfs_alloc_lookup_eq(cnt_cur, fbno, flen, &i)))
326                         return error;
327                 XFS_WANT_CORRUPTED_RETURN(i == 1);
328         }
329         /*
330          * Look up the record in the by-block tree if necessary.
331          */
332         if (flags & XFSA_FIXUP_BNO_OK) {
333 #ifdef DEBUG
334                 if ((error = xfs_alloc_get_rec(bno_cur, &nfbno1, &nflen1, &i)))
335                         return error;
336                 XFS_WANT_CORRUPTED_RETURN(
337                         i == 1 && nfbno1 == fbno && nflen1 == flen);
338 #endif
339         } else {
340                 if ((error = xfs_alloc_lookup_eq(bno_cur, fbno, flen, &i)))
341                         return error;
342                 XFS_WANT_CORRUPTED_RETURN(i == 1);
343         }
344
345 #ifdef DEBUG
346         if (bno_cur->bc_nlevels == 1 && cnt_cur->bc_nlevels == 1) {
347                 struct xfs_btree_block  *bnoblock;
348                 struct xfs_btree_block  *cntblock;
349
350                 bnoblock = XFS_BUF_TO_BLOCK(bno_cur->bc_bufs[0]);
351                 cntblock = XFS_BUF_TO_BLOCK(cnt_cur->bc_bufs[0]);
352
353                 XFS_WANT_CORRUPTED_RETURN(
354                         bnoblock->bb_numrecs == cntblock->bb_numrecs);
355         }
356 #endif
357
358         /*
359          * Deal with all four cases: the allocated record is contained
360          * within the freespace record, so we can have new freespace
361          * at either (or both) end, or no freespace remaining.
362          */
363         if (rbno == fbno && rlen == flen)
364                 nfbno1 = nfbno2 = NULLAGBLOCK;
365         else if (rbno == fbno) {
366                 nfbno1 = rbno + rlen;
367                 nflen1 = flen - rlen;
368                 nfbno2 = NULLAGBLOCK;
369         } else if (rbno + rlen == fbno + flen) {
370                 nfbno1 = fbno;
371                 nflen1 = flen - rlen;
372                 nfbno2 = NULLAGBLOCK;
373         } else {
374                 nfbno1 = fbno;
375                 nflen1 = rbno - fbno;
376                 nfbno2 = rbno + rlen;
377                 nflen2 = (fbno + flen) - nfbno2;
378         }
379         /*
380          * Delete the entry from the by-size btree.
381          */
382         if ((error = xfs_btree_delete(cnt_cur, &i)))
383                 return error;
384         XFS_WANT_CORRUPTED_RETURN(i == 1);
385         /*
386          * Add new by-size btree entry(s).
387          */
388         if (nfbno1 != NULLAGBLOCK) {
389                 if ((error = xfs_alloc_lookup_eq(cnt_cur, nfbno1, nflen1, &i)))
390                         return error;
391                 XFS_WANT_CORRUPTED_RETURN(i == 0);
392                 if ((error = xfs_btree_insert(cnt_cur, &i)))
393                         return error;
394                 XFS_WANT_CORRUPTED_RETURN(i == 1);
395         }
396         if (nfbno2 != NULLAGBLOCK) {
397                 if ((error = xfs_alloc_lookup_eq(cnt_cur, nfbno2, nflen2, &i)))
398                         return error;
399                 XFS_WANT_CORRUPTED_RETURN(i == 0);
400                 if ((error = xfs_btree_insert(cnt_cur, &i)))
401                         return error;
402                 XFS_WANT_CORRUPTED_RETURN(i == 1);
403         }
404         /*
405          * Fix up the by-block btree entry(s).
406          */
407         if (nfbno1 == NULLAGBLOCK) {
408                 /*
409                  * No remaining freespace, just delete the by-block tree entry.
410                  */
411                 if ((error = xfs_btree_delete(bno_cur, &i)))
412                         return error;
413                 XFS_WANT_CORRUPTED_RETURN(i == 1);
414         } else {
415                 /*
416                  * Update the by-block entry to start later|be shorter.
417                  */
418                 if ((error = xfs_alloc_update(bno_cur, nfbno1, nflen1)))
419                         return error;
420         }
421         if (nfbno2 != NULLAGBLOCK) {
422                 /*
423                  * 2 resulting free entries, need to add one.
424                  */
425                 if ((error = xfs_alloc_lookup_eq(bno_cur, nfbno2, nflen2, &i)))
426                         return error;
427                 XFS_WANT_CORRUPTED_RETURN(i == 0);
428                 if ((error = xfs_btree_insert(bno_cur, &i)))
429                         return error;
430                 XFS_WANT_CORRUPTED_RETURN(i == 1);
431         }
432         return 0;
433 }
434
435 /*
436  * Read in the allocation group free block array.
437  */
438 STATIC int                              /* error */
439 xfs_alloc_read_agfl(
440         xfs_mount_t     *mp,            /* mount point structure */
441         xfs_trans_t     *tp,            /* transaction pointer */
442         xfs_agnumber_t  agno,           /* allocation group number */
443         xfs_buf_t       **bpp)          /* buffer for the ag free block array */
444 {
445         xfs_buf_t       *bp;            /* return value */
446         int             error;
447
448         ASSERT(agno != NULLAGNUMBER);
449         error = xfs_trans_read_buf(
450                         mp, tp, mp->m_ddev_targp,
451                         XFS_AG_DADDR(mp, agno, XFS_AGFL_DADDR(mp)),
452                         XFS_FSS_TO_BB(mp, 1), 0, &bp);
453         if (error)
454                 return error;
455         ASSERT(bp);
456         ASSERT(!XFS_BUF_GETERROR(bp));
457         XFS_BUF_SET_VTYPE_REF(bp, B_FS_AGFL, XFS_AGFL_REF);
458         *bpp = bp;
459         return 0;
460 }
461
462 STATIC int
463 xfs_alloc_update_counters(
464         struct xfs_trans        *tp,
465         struct xfs_perag        *pag,
466         struct xfs_buf          *agbp,
467         long                    len)
468 {
469         struct xfs_agf          *agf = XFS_BUF_TO_AGF(agbp);
470
471         pag->pagf_freeblks += len;
472         be32_add_cpu(&agf->agf_freeblks, len);
473
474         xfs_trans_agblocks_delta(tp, len);
475         if (unlikely(be32_to_cpu(agf->agf_freeblks) >
476                      be32_to_cpu(agf->agf_length)))
477                 return EFSCORRUPTED;
478
479         xfs_alloc_log_agf(tp, agbp, XFS_AGF_FREEBLKS);
480         return 0;
481 }
482
483 /*
484  * Allocation group level functions.
485  */
486
487 /*
488  * Allocate a variable extent in the allocation group agno.
489  * Type and bno are used to determine where in the allocation group the
490  * extent will start.
491  * Extent's length (returned in *len) will be between minlen and maxlen,
492  * and of the form k * prod + mod unless there's nothing that large.
493  * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
494  */
495 STATIC int                      /* error */
496 xfs_alloc_ag_vextent(
497         xfs_alloc_arg_t *args)  /* argument structure for allocation */
498 {
499         int             error=0;
500
501         ASSERT(args->minlen > 0);
502         ASSERT(args->maxlen > 0);
503         ASSERT(args->minlen <= args->maxlen);
504         ASSERT(args->mod < args->prod);
505         ASSERT(args->alignment > 0);
506         /*
507          * Branch to correct routine based on the type.
508          */
509         args->wasfromfl = 0;
510         switch (args->type) {
511         case XFS_ALLOCTYPE_THIS_AG:
512                 error = xfs_alloc_ag_vextent_size(args);
513                 break;
514         case XFS_ALLOCTYPE_NEAR_BNO:
515                 error = xfs_alloc_ag_vextent_near(args);
516                 break;
517         case XFS_ALLOCTYPE_THIS_BNO:
518                 error = xfs_alloc_ag_vextent_exact(args);
519                 break;
520         default:
521                 ASSERT(0);
522                 /* NOTREACHED */
523         }
524
525         if (error || args->agbno == NULLAGBLOCK)
526                 return error;
527
528         ASSERT(args->len >= args->minlen);
529         ASSERT(args->len <= args->maxlen);
530         ASSERT(!args->wasfromfl || !args->isfl);
531         ASSERT(args->agbno % args->alignment == 0);
532
533         if (!args->wasfromfl) {
534                 error = xfs_alloc_update_counters(args->tp, args->pag,
535                                                   args->agbp,
536                                                   -((long)(args->len)));
537                 if (error)
538                         return error;
539
540                 ASSERT(!xfs_alloc_busy_search(args->mp, args->agno,
541                                               args->agbno, args->len));
542         }
543
544         if (!args->isfl) {
545                 xfs_trans_mod_sb(args->tp, args->wasdel ?
546                                  XFS_TRANS_SB_RES_FDBLOCKS :
547                                  XFS_TRANS_SB_FDBLOCKS,
548                                  -((long)(args->len)));
549         }
550
551         XFS_STATS_INC(xs_allocx);
552         XFS_STATS_ADD(xs_allocb, args->len);
553         return error;
554 }
555
556 /*
557  * Allocate a variable extent at exactly agno/bno.
558  * Extent's length (returned in *len) will be between minlen and maxlen,
559  * and of the form k * prod + mod unless there's nothing that large.
560  * Return the starting a.g. block (bno), or NULLAGBLOCK if we can't do it.
561  */
562 STATIC int                      /* error */
563 xfs_alloc_ag_vextent_exact(
564         xfs_alloc_arg_t *args)  /* allocation argument structure */
565 {
566         xfs_btree_cur_t *bno_cur;/* by block-number btree cursor */
567         xfs_btree_cur_t *cnt_cur;/* by count btree cursor */
568         int             error;
569         xfs_agblock_t   fbno;   /* start block of found extent */
570         xfs_extlen_t    flen;   /* length of found extent */
571         xfs_agblock_t   tbno;   /* start block of trimmed extent */
572         xfs_extlen_t    tlen;   /* length of trimmed extent */
573         xfs_agblock_t   tend;   /* end block of trimmed extent */
574         xfs_agblock_t   end;    /* end of allocated extent */
575         int             i;      /* success/failure of operation */
576         xfs_extlen_t    rlen;   /* length of returned extent */
577
578         ASSERT(args->alignment == 1);
579
580         /*
581          * Allocate/initialize a cursor for the by-number freespace btree.
582          */
583         bno_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
584                                           args->agno, XFS_BTNUM_BNO);
585
586         /*
587          * Lookup bno and minlen in the btree (minlen is irrelevant, really).
588          * Look for the closest free block <= bno, it must contain bno
589          * if any free block does.
590          */
591         error = xfs_alloc_lookup_le(bno_cur, args->agbno, args->minlen, &i);
592         if (error)
593                 goto error0;
594         if (!i)
595                 goto not_found;
596
597         /*
598          * Grab the freespace record.
599          */
600         error = xfs_alloc_get_rec(bno_cur, &fbno, &flen, &i);
601         if (error)
602                 goto error0;
603         XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
604         ASSERT(fbno <= args->agbno);
605
606         /*
607          * Check for overlapping busy extents.
608          */
609         xfs_alloc_busy_trim(args, fbno, flen, &tbno, &tlen);
610
611         /*
612          * Give up if the start of the extent is busy, or the freespace isn't
613          * long enough for the minimum request.
614          */
615         if (tbno > args->agbno)
616                 goto not_found;
617         if (tlen < args->minlen)
618                 goto not_found;
619         tend = tbno + tlen;
620         if (tend < args->agbno + args->minlen)
621                 goto not_found;
622
623         /*
624          * End of extent will be smaller of the freespace end and the
625          * maximal requested end.
626          *
627          * Fix the length according to mod and prod if given.
628          */
629         end = XFS_AGBLOCK_MIN(tend, args->agbno + args->maxlen);
630         args->len = end - args->agbno;
631         xfs_alloc_fix_len(args);
632         if (!xfs_alloc_fix_minleft(args))
633                 goto not_found;
634
635         rlen = args->len;
636         ASSERT(args->agbno + rlen <= tend);
637         end = args->agbno + rlen;
638
639         /*
640          * We are allocating agbno for rlen [agbno .. end]
641          * Allocate/initialize a cursor for the by-size btree.
642          */
643         cnt_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
644                 args->agno, XFS_BTNUM_CNT);
645         ASSERT(args->agbno + args->len <=
646                 be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length));
647         error = xfs_alloc_fixup_trees(cnt_cur, bno_cur, fbno, flen, args->agbno,
648                                       args->len, XFSA_FIXUP_BNO_OK);
649         if (error) {
650                 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
651                 goto error0;
652         }
653
654         xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
655         xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
656
657         args->wasfromfl = 0;
658         trace_xfs_alloc_exact_done(args);
659         return 0;
660
661 not_found:
662         /* Didn't find it, return null. */
663         xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
664         args->agbno = NULLAGBLOCK;
665         trace_xfs_alloc_exact_notfound(args);
666         return 0;
667
668 error0:
669         xfs_btree_del_cursor(bno_cur, XFS_BTREE_ERROR);
670         trace_xfs_alloc_exact_error(args);
671         return error;
672 }
673
674 /*
675  * Search the btree in a given direction via the search cursor and compare
676  * the records found against the good extent we've already found.
677  */
678 STATIC int
679 xfs_alloc_find_best_extent(
680         struct xfs_alloc_arg    *args,  /* allocation argument structure */
681         struct xfs_btree_cur    **gcur, /* good cursor */
682         struct xfs_btree_cur    **scur, /* searching cursor */
683         xfs_agblock_t           gdiff,  /* difference for search comparison */
684         xfs_agblock_t           *sbno,  /* extent found by search */
685         xfs_extlen_t            *slen,  /* extent length */
686         xfs_agblock_t           *sbnoa, /* aligned extent found by search */
687         xfs_extlen_t            *slena, /* aligned extent length */
688         int                     dir)    /* 0 = search right, 1 = search left */
689 {
690         xfs_agblock_t           new;
691         xfs_agblock_t           sdiff;
692         int                     error;
693         int                     i;
694
695         /* The good extent is perfect, no need to  search. */
696         if (!gdiff)
697                 goto out_use_good;
698
699         /*
700          * Look until we find a better one, run out of space or run off the end.
701          */
702         do {
703                 error = xfs_alloc_get_rec(*scur, sbno, slen, &i);
704                 if (error)
705                         goto error0;
706                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
707                 xfs_alloc_compute_aligned(args, *sbno, *slen, sbnoa, slena);
708
709                 /*
710                  * The good extent is closer than this one.
711                  */
712                 if (!dir) {
713                         if (*sbnoa >= args->agbno + gdiff)
714                                 goto out_use_good;
715                 } else {
716                         if (*sbnoa <= args->agbno - gdiff)
717                                 goto out_use_good;
718                 }
719
720                 /*
721                  * Same distance, compare length and pick the best.
722                  */
723                 if (*slena >= args->minlen) {
724                         args->len = XFS_EXTLEN_MIN(*slena, args->maxlen);
725                         xfs_alloc_fix_len(args);
726
727                         sdiff = xfs_alloc_compute_diff(args->agbno, args->len,
728                                                        args->alignment, *sbnoa,
729                                                        *slena, &new);
730
731                         /*
732                          * Choose closer size and invalidate other cursor.
733                          */
734                         if (sdiff < gdiff)
735                                 goto out_use_search;
736                         goto out_use_good;
737                 }
738
739                 if (!dir)
740                         error = xfs_btree_increment(*scur, 0, &i);
741                 else
742                         error = xfs_btree_decrement(*scur, 0, &i);
743                 if (error)
744                         goto error0;
745         } while (i);
746
747 out_use_good:
748         xfs_btree_del_cursor(*scur, XFS_BTREE_NOERROR);
749         *scur = NULL;
750         return 0;
751
752 out_use_search:
753         xfs_btree_del_cursor(*gcur, XFS_BTREE_NOERROR);
754         *gcur = NULL;
755         return 0;
756
757 error0:
758         /* caller invalidates cursors */
759         return error;
760 }
761
762 /*
763  * Allocate a variable extent near bno in the allocation group agno.
764  * Extent's length (returned in len) will be between minlen and maxlen,
765  * and of the form k * prod + mod unless there's nothing that large.
766  * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
767  */
768 STATIC int                              /* error */
769 xfs_alloc_ag_vextent_near(
770         xfs_alloc_arg_t *args)          /* allocation argument structure */
771 {
772         xfs_btree_cur_t *bno_cur_gt;    /* cursor for bno btree, right side */
773         xfs_btree_cur_t *bno_cur_lt;    /* cursor for bno btree, left side */
774         xfs_btree_cur_t *cnt_cur;       /* cursor for count btree */
775         xfs_agblock_t   gtbno;          /* start bno of right side entry */
776         xfs_agblock_t   gtbnoa;         /* aligned ... */
777         xfs_extlen_t    gtdiff;         /* difference to right side entry */
778         xfs_extlen_t    gtlen;          /* length of right side entry */
779         xfs_extlen_t    gtlena;         /* aligned ... */
780         xfs_agblock_t   gtnew;          /* useful start bno of right side */
781         int             error;          /* error code */
782         int             i;              /* result code, temporary */
783         int             j;              /* result code, temporary */
784         xfs_agblock_t   ltbno;          /* start bno of left side entry */
785         xfs_agblock_t   ltbnoa;         /* aligned ... */
786         xfs_extlen_t    ltdiff;         /* difference to left side entry */
787         xfs_extlen_t    ltlen;          /* length of left side entry */
788         xfs_extlen_t    ltlena;         /* aligned ... */
789         xfs_agblock_t   ltnew;          /* useful start bno of left side */
790         xfs_extlen_t    rlen;           /* length of returned extent */
791         int             forced = 0;
792 #if defined(DEBUG) && defined(__KERNEL__)
793         /*
794          * Randomly don't execute the first algorithm.
795          */
796         int             dofirst;        /* set to do first algorithm */
797
798         dofirst = random32() & 1;
799 #endif
800
801 restart:
802         bno_cur_lt = NULL;
803         bno_cur_gt = NULL;
804         ltlen = 0;
805         gtlena = 0;
806         ltlena = 0;
807
808         /*
809          * Get a cursor for the by-size btree.
810          */
811         cnt_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
812                 args->agno, XFS_BTNUM_CNT);
813
814         /*
815          * See if there are any free extents as big as maxlen.
816          */
817         if ((error = xfs_alloc_lookup_ge(cnt_cur, 0, args->maxlen, &i)))
818                 goto error0;
819         /*
820          * If none, then pick up the last entry in the tree unless the
821          * tree is empty.
822          */
823         if (!i) {
824                 if ((error = xfs_alloc_ag_vextent_small(args, cnt_cur, &ltbno,
825                                 &ltlen, &i)))
826                         goto error0;
827                 if (i == 0 || ltlen == 0) {
828                         xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
829                         trace_xfs_alloc_near_noentry(args);
830                         return 0;
831                 }
832                 ASSERT(i == 1);
833         }
834         args->wasfromfl = 0;
835
836         /*
837          * First algorithm.
838          * If the requested extent is large wrt the freespaces available
839          * in this a.g., then the cursor will be pointing to a btree entry
840          * near the right edge of the tree.  If it's in the last btree leaf
841          * block, then we just examine all the entries in that block
842          * that are big enough, and pick the best one.
843          * This is written as a while loop so we can break out of it,
844          * but we never loop back to the top.
845          */
846         while (xfs_btree_islastblock(cnt_cur, 0)) {
847                 xfs_extlen_t    bdiff;
848                 int             besti=0;
849                 xfs_extlen_t    blen=0;
850                 xfs_agblock_t   bnew=0;
851
852 #if defined(DEBUG) && defined(__KERNEL__)
853                 if (!dofirst)
854                         break;
855 #endif
856                 /*
857                  * Start from the entry that lookup found, sequence through
858                  * all larger free blocks.  If we're actually pointing at a
859                  * record smaller than maxlen, go to the start of this block,
860                  * and skip all those smaller than minlen.
861                  */
862                 if (ltlen || args->alignment > 1) {
863                         cnt_cur->bc_ptrs[0] = 1;
864                         do {
865                                 if ((error = xfs_alloc_get_rec(cnt_cur, &ltbno,
866                                                 &ltlen, &i)))
867                                         goto error0;
868                                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
869                                 if (ltlen >= args->minlen)
870                                         break;
871                                 if ((error = xfs_btree_increment(cnt_cur, 0, &i)))
872                                         goto error0;
873                         } while (i);
874                         ASSERT(ltlen >= args->minlen);
875                         if (!i)
876                                 break;
877                 }
878                 i = cnt_cur->bc_ptrs[0];
879                 for (j = 1, blen = 0, bdiff = 0;
880                      !error && j && (blen < args->maxlen || bdiff > 0);
881                      error = xfs_btree_increment(cnt_cur, 0, &j)) {
882                         /*
883                          * For each entry, decide if it's better than
884                          * the previous best entry.
885                          */
886                         if ((error = xfs_alloc_get_rec(cnt_cur, &ltbno, &ltlen, &i)))
887                                 goto error0;
888                         XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
889                         xfs_alloc_compute_aligned(args, ltbno, ltlen,
890                                                   &ltbnoa, &ltlena);
891                         if (ltlena < args->minlen)
892                                 continue;
893                         args->len = XFS_EXTLEN_MIN(ltlena, args->maxlen);
894                         xfs_alloc_fix_len(args);
895                         ASSERT(args->len >= args->minlen);
896                         if (args->len < blen)
897                                 continue;
898                         ltdiff = xfs_alloc_compute_diff(args->agbno, args->len,
899                                 args->alignment, ltbnoa, ltlena, &ltnew);
900                         if (ltnew != NULLAGBLOCK &&
901                             (args->len > blen || ltdiff < bdiff)) {
902                                 bdiff = ltdiff;
903                                 bnew = ltnew;
904                                 blen = args->len;
905                                 besti = cnt_cur->bc_ptrs[0];
906                         }
907                 }
908                 /*
909                  * It didn't work.  We COULD be in a case where
910                  * there's a good record somewhere, so try again.
911                  */
912                 if (blen == 0)
913                         break;
914                 /*
915                  * Point at the best entry, and retrieve it again.
916                  */
917                 cnt_cur->bc_ptrs[0] = besti;
918                 if ((error = xfs_alloc_get_rec(cnt_cur, &ltbno, &ltlen, &i)))
919                         goto error0;
920                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
921                 ASSERT(ltbno + ltlen <= be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length));
922                 args->len = blen;
923                 if (!xfs_alloc_fix_minleft(args)) {
924                         xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
925                         trace_xfs_alloc_near_nominleft(args);
926                         return 0;
927                 }
928                 blen = args->len;
929                 /*
930                  * We are allocating starting at bnew for blen blocks.
931                  */
932                 args->agbno = bnew;
933                 ASSERT(bnew >= ltbno);
934                 ASSERT(bnew + blen <= ltbno + ltlen);
935                 /*
936                  * Set up a cursor for the by-bno tree.
937                  */
938                 bno_cur_lt = xfs_allocbt_init_cursor(args->mp, args->tp,
939                         args->agbp, args->agno, XFS_BTNUM_BNO);
940                 /*
941                  * Fix up the btree entries.
942                  */
943                 if ((error = xfs_alloc_fixup_trees(cnt_cur, bno_cur_lt, ltbno,
944                                 ltlen, bnew, blen, XFSA_FIXUP_CNT_OK)))
945                         goto error0;
946                 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
947                 xfs_btree_del_cursor(bno_cur_lt, XFS_BTREE_NOERROR);
948
949                 trace_xfs_alloc_near_first(args);
950                 return 0;
951         }
952         /*
953          * Second algorithm.
954          * Search in the by-bno tree to the left and to the right
955          * simultaneously, until in each case we find a space big enough,
956          * or run into the edge of the tree.  When we run into the edge,
957          * we deallocate that cursor.
958          * If both searches succeed, we compare the two spaces and pick
959          * the better one.
960          * With alignment, it's possible for both to fail; the upper
961          * level algorithm that picks allocation groups for allocations
962          * is not supposed to do this.
963          */
964         /*
965          * Allocate and initialize the cursor for the leftward search.
966          */
967         bno_cur_lt = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
968                 args->agno, XFS_BTNUM_BNO);
969         /*
970          * Lookup <= bno to find the leftward search's starting point.
971          */
972         if ((error = xfs_alloc_lookup_le(bno_cur_lt, args->agbno, args->maxlen, &i)))
973                 goto error0;
974         if (!i) {
975                 /*
976                  * Didn't find anything; use this cursor for the rightward
977                  * search.
978                  */
979                 bno_cur_gt = bno_cur_lt;
980                 bno_cur_lt = NULL;
981         }
982         /*
983          * Found something.  Duplicate the cursor for the rightward search.
984          */
985         else if ((error = xfs_btree_dup_cursor(bno_cur_lt, &bno_cur_gt)))
986                 goto error0;
987         /*
988          * Increment the cursor, so we will point at the entry just right
989          * of the leftward entry if any, or to the leftmost entry.
990          */
991         if ((error = xfs_btree_increment(bno_cur_gt, 0, &i)))
992                 goto error0;
993         if (!i) {
994                 /*
995                  * It failed, there are no rightward entries.
996                  */
997                 xfs_btree_del_cursor(bno_cur_gt, XFS_BTREE_NOERROR);
998                 bno_cur_gt = NULL;
999         }
1000         /*
1001          * Loop going left with the leftward cursor, right with the
1002          * rightward cursor, until either both directions give up or
1003          * we find an entry at least as big as minlen.
1004          */
1005         do {
1006                 if (bno_cur_lt) {
1007                         if ((error = xfs_alloc_get_rec(bno_cur_lt, &ltbno, &ltlen, &i)))
1008                                 goto error0;
1009                         XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1010                         xfs_alloc_compute_aligned(args, ltbno, ltlen,
1011                                                   &ltbnoa, &ltlena);
1012                         if (ltlena >= args->minlen)
1013                                 break;
1014                         if ((error = xfs_btree_decrement(bno_cur_lt, 0, &i)))
1015                                 goto error0;
1016                         if (!i) {
1017                                 xfs_btree_del_cursor(bno_cur_lt,
1018                                                      XFS_BTREE_NOERROR);
1019                                 bno_cur_lt = NULL;
1020                         }
1021                 }
1022                 if (bno_cur_gt) {
1023                         if ((error = xfs_alloc_get_rec(bno_cur_gt, &gtbno, &gtlen, &i)))
1024                                 goto error0;
1025                         XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1026                         xfs_alloc_compute_aligned(args, gtbno, gtlen,
1027                                                   &gtbnoa, &gtlena);
1028                         if (gtlena >= args->minlen)
1029                                 break;
1030                         if ((error = xfs_btree_increment(bno_cur_gt, 0, &i)))
1031                                 goto error0;
1032                         if (!i) {
1033                                 xfs_btree_del_cursor(bno_cur_gt,
1034                                                      XFS_BTREE_NOERROR);
1035                                 bno_cur_gt = NULL;
1036                         }
1037                 }
1038         } while (bno_cur_lt || bno_cur_gt);
1039
1040         /*
1041          * Got both cursors still active, need to find better entry.
1042          */
1043         if (bno_cur_lt && bno_cur_gt) {
1044                 if (ltlena >= args->minlen) {
1045                         /*
1046                          * Left side is good, look for a right side entry.
1047                          */
1048                         args->len = XFS_EXTLEN_MIN(ltlena, args->maxlen);
1049                         xfs_alloc_fix_len(args);
1050                         ltdiff = xfs_alloc_compute_diff(args->agbno, args->len,
1051                                 args->alignment, ltbnoa, ltlena, &ltnew);
1052
1053                         error = xfs_alloc_find_best_extent(args,
1054                                                 &bno_cur_lt, &bno_cur_gt,
1055                                                 ltdiff, &gtbno, &gtlen,
1056                                                 &gtbnoa, &gtlena,
1057                                                 0 /* search right */);
1058                 } else {
1059                         ASSERT(gtlena >= args->minlen);
1060
1061                         /*
1062                          * Right side is good, look for a left side entry.
1063                          */
1064                         args->len = XFS_EXTLEN_MIN(gtlena, args->maxlen);
1065                         xfs_alloc_fix_len(args);
1066                         gtdiff = xfs_alloc_compute_diff(args->agbno, args->len,
1067                                 args->alignment, gtbnoa, gtlena, &gtnew);
1068
1069                         error = xfs_alloc_find_best_extent(args,
1070                                                 &bno_cur_gt, &bno_cur_lt,
1071                                                 gtdiff, &ltbno, &ltlen,
1072                                                 &ltbnoa, &ltlena,
1073                                                 1 /* search left */);
1074                 }
1075
1076                 if (error)
1077                         goto error0;
1078         }
1079
1080         /*
1081          * If we couldn't get anything, give up.
1082          */
1083         if (bno_cur_lt == NULL && bno_cur_gt == NULL) {
1084                 if (!forced++) {
1085                         trace_xfs_alloc_near_busy(args);
1086                         xfs_log_force(args->mp, XFS_LOG_SYNC);
1087                         goto restart;
1088                 }
1089
1090                 trace_xfs_alloc_size_neither(args);
1091                 args->agbno = NULLAGBLOCK;
1092                 return 0;
1093         }
1094
1095         /*
1096          * At this point we have selected a freespace entry, either to the
1097          * left or to the right.  If it's on the right, copy all the
1098          * useful variables to the "left" set so we only have one
1099          * copy of this code.
1100          */
1101         if (bno_cur_gt) {
1102                 bno_cur_lt = bno_cur_gt;
1103                 bno_cur_gt = NULL;
1104                 ltbno = gtbno;
1105                 ltbnoa = gtbnoa;
1106                 ltlen = gtlen;
1107                 ltlena = gtlena;
1108                 j = 1;
1109         } else
1110                 j = 0;
1111
1112         /*
1113          * Fix up the length and compute the useful address.
1114          */
1115         args->len = XFS_EXTLEN_MIN(ltlena, args->maxlen);
1116         xfs_alloc_fix_len(args);
1117         if (!xfs_alloc_fix_minleft(args)) {
1118                 trace_xfs_alloc_near_nominleft(args);
1119                 xfs_btree_del_cursor(bno_cur_lt, XFS_BTREE_NOERROR);
1120                 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1121                 return 0;
1122         }
1123         rlen = args->len;
1124         (void)xfs_alloc_compute_diff(args->agbno, rlen, args->alignment,
1125                                      ltbnoa, ltlena, &ltnew);
1126         ASSERT(ltnew >= ltbno);
1127         ASSERT(ltnew + rlen <= ltbnoa + ltlena);
1128         ASSERT(ltnew + rlen <= be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length));
1129         args->agbno = ltnew;
1130
1131         if ((error = xfs_alloc_fixup_trees(cnt_cur, bno_cur_lt, ltbno, ltlen,
1132                         ltnew, rlen, XFSA_FIXUP_BNO_OK)))
1133                 goto error0;
1134
1135         if (j)
1136                 trace_xfs_alloc_near_greater(args);
1137         else
1138                 trace_xfs_alloc_near_lesser(args);
1139
1140         xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1141         xfs_btree_del_cursor(bno_cur_lt, XFS_BTREE_NOERROR);
1142         return 0;
1143
1144  error0:
1145         trace_xfs_alloc_near_error(args);
1146         if (cnt_cur != NULL)
1147                 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
1148         if (bno_cur_lt != NULL)
1149                 xfs_btree_del_cursor(bno_cur_lt, XFS_BTREE_ERROR);
1150         if (bno_cur_gt != NULL)
1151                 xfs_btree_del_cursor(bno_cur_gt, XFS_BTREE_ERROR);
1152         return error;
1153 }
1154
1155 /*
1156  * Allocate a variable extent anywhere in the allocation group agno.
1157  * Extent's length (returned in len) will be between minlen and maxlen,
1158  * and of the form k * prod + mod unless there's nothing that large.
1159  * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
1160  */
1161 STATIC int                              /* error */
1162 xfs_alloc_ag_vextent_size(
1163         xfs_alloc_arg_t *args)          /* allocation argument structure */
1164 {
1165         xfs_btree_cur_t *bno_cur;       /* cursor for bno btree */
1166         xfs_btree_cur_t *cnt_cur;       /* cursor for cnt btree */
1167         int             error;          /* error result */
1168         xfs_agblock_t   fbno;           /* start of found freespace */
1169         xfs_extlen_t    flen;           /* length of found freespace */
1170         int             i;              /* temp status variable */
1171         xfs_agblock_t   rbno;           /* returned block number */
1172         xfs_extlen_t    rlen;           /* length of returned extent */
1173         int             forced = 0;
1174
1175 restart:
1176         /*
1177          * Allocate and initialize a cursor for the by-size btree.
1178          */
1179         cnt_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
1180                 args->agno, XFS_BTNUM_CNT);
1181         bno_cur = NULL;
1182
1183         /*
1184          * Look for an entry >= maxlen+alignment-1 blocks.
1185          */
1186         if ((error = xfs_alloc_lookup_ge(cnt_cur, 0,
1187                         args->maxlen + args->alignment - 1, &i)))
1188                 goto error0;
1189
1190         /*
1191          * If none or we have busy extents that we cannot allocate from, then
1192          * we have to settle for a smaller extent. In the case that there are
1193          * no large extents, this will return the last entry in the tree unless
1194          * the tree is empty. In the case that there are only busy large
1195          * extents, this will return the largest small extent unless there
1196          * are no smaller extents available.
1197          */
1198         if (!i || forced > 1) {
1199                 error = xfs_alloc_ag_vextent_small(args, cnt_cur,
1200                                                    &fbno, &flen, &i);
1201                 if (error)
1202                         goto error0;
1203                 if (i == 0 || flen == 0) {
1204                         xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1205                         trace_xfs_alloc_size_noentry(args);
1206                         return 0;
1207                 }
1208                 ASSERT(i == 1);
1209                 xfs_alloc_compute_aligned(args, fbno, flen, &rbno, &rlen);
1210         } else {
1211                 /*
1212                  * Search for a non-busy extent that is large enough.
1213                  * If we are at low space, don't check, or if we fall of
1214                  * the end of the btree, turn off the busy check and
1215                  * restart.
1216                  */
1217                 for (;;) {
1218                         error = xfs_alloc_get_rec(cnt_cur, &fbno, &flen, &i);
1219                         if (error)
1220                                 goto error0;
1221                         XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1222
1223                         xfs_alloc_compute_aligned(args, fbno, flen,
1224                                                   &rbno, &rlen);
1225
1226                         if (rlen >= args->maxlen)
1227                                 break;
1228
1229                         error = xfs_btree_increment(cnt_cur, 0, &i);
1230                         if (error)
1231                                 goto error0;
1232                         if (i == 0) {
1233                                 /*
1234                                  * Our only valid extents must have been busy.
1235                                  * Make it unbusy by forcing the log out and
1236                                  * retrying. If we've been here before, forcing
1237                                  * the log isn't making the extents available,
1238                                  * which means they have probably been freed in
1239                                  * this transaction.  In that case, we have to
1240                                  * give up on them and we'll attempt a minlen
1241                                  * allocation the next time around.
1242                                  */
1243                                 xfs_btree_del_cursor(cnt_cur,
1244                                                      XFS_BTREE_NOERROR);
1245                                 trace_xfs_alloc_size_busy(args);
1246                                 if (!forced++)
1247                                         xfs_log_force(args->mp, XFS_LOG_SYNC);
1248                                 goto restart;
1249                         }
1250                 }
1251         }
1252
1253         /*
1254          * In the first case above, we got the last entry in the
1255          * by-size btree.  Now we check to see if the space hits maxlen
1256          * once aligned; if not, we search left for something better.
1257          * This can't happen in the second case above.
1258          */
1259         rlen = XFS_EXTLEN_MIN(args->maxlen, rlen);
1260         XFS_WANT_CORRUPTED_GOTO(rlen == 0 ||
1261                         (rlen <= flen && rbno + rlen <= fbno + flen), error0);
1262         if (rlen < args->maxlen) {
1263                 xfs_agblock_t   bestfbno;
1264                 xfs_extlen_t    bestflen;
1265                 xfs_agblock_t   bestrbno;
1266                 xfs_extlen_t    bestrlen;
1267
1268                 bestrlen = rlen;
1269                 bestrbno = rbno;
1270                 bestflen = flen;
1271                 bestfbno = fbno;
1272                 for (;;) {
1273                         if ((error = xfs_btree_decrement(cnt_cur, 0, &i)))
1274                                 goto error0;
1275                         if (i == 0)
1276                                 break;
1277                         if ((error = xfs_alloc_get_rec(cnt_cur, &fbno, &flen,
1278                                         &i)))
1279                                 goto error0;
1280                         XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1281                         if (flen < bestrlen)
1282                                 break;
1283                         xfs_alloc_compute_aligned(args, fbno, flen,
1284                                                   &rbno, &rlen);
1285                         rlen = XFS_EXTLEN_MIN(args->maxlen, rlen);
1286                         XFS_WANT_CORRUPTED_GOTO(rlen == 0 ||
1287                                 (rlen <= flen && rbno + rlen <= fbno + flen),
1288                                 error0);
1289                         if (rlen > bestrlen) {
1290                                 bestrlen = rlen;
1291                                 bestrbno = rbno;
1292                                 bestflen = flen;
1293                                 bestfbno = fbno;
1294                                 if (rlen == args->maxlen)
1295                                         break;
1296                         }
1297                 }
1298                 if ((error = xfs_alloc_lookup_eq(cnt_cur, bestfbno, bestflen,
1299                                 &i)))
1300                         goto error0;
1301                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1302                 rlen = bestrlen;
1303                 rbno = bestrbno;
1304                 flen = bestflen;
1305                 fbno = bestfbno;
1306         }
1307         args->wasfromfl = 0;
1308         /*
1309          * Fix up the length.
1310          */
1311         args->len = rlen;
1312         if (rlen < args->minlen) {
1313                 if (!forced++) {
1314                         xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1315                         trace_xfs_alloc_size_busy(args);
1316                         xfs_log_force(args->mp, XFS_LOG_SYNC);
1317                         goto restart;
1318                 }
1319                 goto out_nominleft;
1320         }
1321         xfs_alloc_fix_len(args);
1322
1323         if (!xfs_alloc_fix_minleft(args))
1324                 goto out_nominleft;
1325         rlen = args->len;
1326         XFS_WANT_CORRUPTED_GOTO(rlen <= flen, error0);
1327         /*
1328          * Allocate and initialize a cursor for the by-block tree.
1329          */
1330         bno_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
1331                 args->agno, XFS_BTNUM_BNO);
1332         if ((error = xfs_alloc_fixup_trees(cnt_cur, bno_cur, fbno, flen,
1333                         rbno, rlen, XFSA_FIXUP_CNT_OK)))
1334                 goto error0;
1335         xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1336         xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
1337         cnt_cur = bno_cur = NULL;
1338         args->len = rlen;
1339         args->agbno = rbno;
1340         XFS_WANT_CORRUPTED_GOTO(
1341                 args->agbno + args->len <=
1342                         be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length),
1343                 error0);
1344         trace_xfs_alloc_size_done(args);
1345         return 0;
1346
1347 error0:
1348         trace_xfs_alloc_size_error(args);
1349         if (cnt_cur)
1350                 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
1351         if (bno_cur)
1352                 xfs_btree_del_cursor(bno_cur, XFS_BTREE_ERROR);
1353         return error;
1354
1355 out_nominleft:
1356         xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1357         trace_xfs_alloc_size_nominleft(args);
1358         args->agbno = NULLAGBLOCK;
1359         return 0;
1360 }
1361
1362 /*
1363  * Deal with the case where only small freespaces remain.
1364  * Either return the contents of the last freespace record,
1365  * or allocate space from the freelist if there is nothing in the tree.
1366  */
1367 STATIC int                      /* error */
1368 xfs_alloc_ag_vextent_small(
1369         xfs_alloc_arg_t *args,  /* allocation argument structure */
1370         xfs_btree_cur_t *ccur,  /* by-size cursor */
1371         xfs_agblock_t   *fbnop, /* result block number */
1372         xfs_extlen_t    *flenp, /* result length */
1373         int             *stat)  /* status: 0-freelist, 1-normal/none */
1374 {
1375         int             error;
1376         xfs_agblock_t   fbno;
1377         xfs_extlen_t    flen;
1378         int             i;
1379
1380         if ((error = xfs_btree_decrement(ccur, 0, &i)))
1381                 goto error0;
1382         if (i) {
1383                 if ((error = xfs_alloc_get_rec(ccur, &fbno, &flen, &i)))
1384                         goto error0;
1385                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1386         }
1387         /*
1388          * Nothing in the btree, try the freelist.  Make sure
1389          * to respect minleft even when pulling from the
1390          * freelist.
1391          */
1392         else if (args->minlen == 1 && args->alignment == 1 && !args->isfl &&
1393                  (be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_flcount)
1394                   > args->minleft)) {
1395                 error = xfs_alloc_get_freelist(args->tp, args->agbp, &fbno, 0);
1396                 if (error)
1397                         goto error0;
1398                 if (fbno != NULLAGBLOCK) {
1399                         if (xfs_alloc_busy_search(args->mp, args->agno, fbno, 1))
1400                                 xfs_trans_set_sync(args->tp);
1401                         if (args->userdata) {
1402                                 xfs_buf_t       *bp;
1403
1404                                 bp = xfs_btree_get_bufs(args->mp, args->tp,
1405                                         args->agno, fbno, 0);
1406                                 xfs_trans_binval(args->tp, bp);
1407                         }
1408                         args->len = 1;
1409                         args->agbno = fbno;
1410                         XFS_WANT_CORRUPTED_GOTO(
1411                                 args->agbno + args->len <=
1412                                 be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length),
1413                                 error0);
1414                         args->wasfromfl = 1;
1415                         trace_xfs_alloc_small_freelist(args);
1416                         *stat = 0;
1417                         return 0;
1418                 }
1419                 /*
1420                  * Nothing in the freelist.
1421                  */
1422                 else
1423                         flen = 0;
1424         }
1425         /*
1426          * Can't allocate from the freelist for some reason.
1427          */
1428         else {
1429                 fbno = NULLAGBLOCK;
1430                 flen = 0;
1431         }
1432         /*
1433          * Can't do the allocation, give up.
1434          */
1435         if (flen < args->minlen) {
1436                 args->agbno = NULLAGBLOCK;
1437                 trace_xfs_alloc_small_notenough(args);
1438                 flen = 0;
1439         }
1440         *fbnop = fbno;
1441         *flenp = flen;
1442         *stat = 1;
1443         trace_xfs_alloc_small_done(args);
1444         return 0;
1445
1446 error0:
1447         trace_xfs_alloc_small_error(args);
1448         return error;
1449 }
1450
1451 /*
1452  * Free the extent starting at agno/bno for length.
1453  */
1454 STATIC int                      /* error */
1455 xfs_free_ag_extent(
1456         xfs_trans_t     *tp,    /* transaction pointer */
1457         xfs_buf_t       *agbp,  /* buffer for a.g. freelist header */
1458         xfs_agnumber_t  agno,   /* allocation group number */
1459         xfs_agblock_t   bno,    /* starting block number */
1460         xfs_extlen_t    len,    /* length of extent */
1461         int             isfl)   /* set if is freelist blocks - no sb acctg */
1462 {
1463         xfs_btree_cur_t *bno_cur;       /* cursor for by-block btree */
1464         xfs_btree_cur_t *cnt_cur;       /* cursor for by-size btree */
1465         int             error;          /* error return value */
1466         xfs_agblock_t   gtbno;          /* start of right neighbor block */
1467         xfs_extlen_t    gtlen;          /* length of right neighbor block */
1468         int             haveleft;       /* have a left neighbor block */
1469         int             haveright;      /* have a right neighbor block */
1470         int             i;              /* temp, result code */
1471         xfs_agblock_t   ltbno;          /* start of left neighbor block */
1472         xfs_extlen_t    ltlen;          /* length of left neighbor block */
1473         xfs_mount_t     *mp;            /* mount point struct for filesystem */
1474         xfs_agblock_t   nbno;           /* new starting block of freespace */
1475         xfs_extlen_t    nlen;           /* new length of freespace */
1476         xfs_perag_t     *pag;           /* per allocation group data */
1477
1478         mp = tp->t_mountp;
1479         /*
1480          * Allocate and initialize a cursor for the by-block btree.
1481          */
1482         bno_cur = xfs_allocbt_init_cursor(mp, tp, agbp, agno, XFS_BTNUM_BNO);
1483         cnt_cur = NULL;
1484         /*
1485          * Look for a neighboring block on the left (lower block numbers)
1486          * that is contiguous with this space.
1487          */
1488         if ((error = xfs_alloc_lookup_le(bno_cur, bno, len, &haveleft)))
1489                 goto error0;
1490         if (haveleft) {
1491                 /*
1492                  * There is a block to our left.
1493                  */
1494                 if ((error = xfs_alloc_get_rec(bno_cur, &ltbno, &ltlen, &i)))
1495                         goto error0;
1496                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1497                 /*
1498                  * It's not contiguous, though.
1499                  */
1500                 if (ltbno + ltlen < bno)
1501                         haveleft = 0;
1502                 else {
1503                         /*
1504                          * If this failure happens the request to free this
1505                          * space was invalid, it's (partly) already free.
1506                          * Very bad.
1507                          */
1508                         XFS_WANT_CORRUPTED_GOTO(ltbno + ltlen <= bno, error0);
1509                 }
1510         }
1511         /*
1512          * Look for a neighboring block on the right (higher block numbers)
1513          * that is contiguous with this space.
1514          */
1515         if ((error = xfs_btree_increment(bno_cur, 0, &haveright)))
1516                 goto error0;
1517         if (haveright) {
1518                 /*
1519                  * There is a block to our right.
1520                  */
1521                 if ((error = xfs_alloc_get_rec(bno_cur, &gtbno, &gtlen, &i)))
1522                         goto error0;
1523                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1524                 /*
1525                  * It's not contiguous, though.
1526                  */
1527                 if (bno + len < gtbno)
1528                         haveright = 0;
1529                 else {
1530                         /*
1531                          * If this failure happens the request to free this
1532                          * space was invalid, it's (partly) already free.
1533                          * Very bad.
1534                          */
1535                         XFS_WANT_CORRUPTED_GOTO(gtbno >= bno + len, error0);
1536                 }
1537         }
1538         /*
1539          * Now allocate and initialize a cursor for the by-size tree.
1540          */
1541         cnt_cur = xfs_allocbt_init_cursor(mp, tp, agbp, agno, XFS_BTNUM_CNT);
1542         /*
1543          * Have both left and right contiguous neighbors.
1544          * Merge all three into a single free block.
1545          */
1546         if (haveleft && haveright) {
1547                 /*
1548                  * Delete the old by-size entry on the left.
1549                  */
1550                 if ((error = xfs_alloc_lookup_eq(cnt_cur, ltbno, ltlen, &i)))
1551                         goto error0;
1552                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1553                 if ((error = xfs_btree_delete(cnt_cur, &i)))
1554                         goto error0;
1555                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1556                 /*
1557                  * Delete the old by-size entry on the right.
1558                  */
1559                 if ((error = xfs_alloc_lookup_eq(cnt_cur, gtbno, gtlen, &i)))
1560                         goto error0;
1561                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1562                 if ((error = xfs_btree_delete(cnt_cur, &i)))
1563                         goto error0;
1564                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1565                 /*
1566                  * Delete the old by-block entry for the right block.
1567                  */
1568                 if ((error = xfs_btree_delete(bno_cur, &i)))
1569                         goto error0;
1570                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1571                 /*
1572                  * Move the by-block cursor back to the left neighbor.
1573                  */
1574                 if ((error = xfs_btree_decrement(bno_cur, 0, &i)))
1575                         goto error0;
1576                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1577 #ifdef DEBUG
1578                 /*
1579                  * Check that this is the right record: delete didn't
1580                  * mangle the cursor.
1581                  */
1582                 {
1583                         xfs_agblock_t   xxbno;
1584                         xfs_extlen_t    xxlen;
1585
1586                         if ((error = xfs_alloc_get_rec(bno_cur, &xxbno, &xxlen,
1587                                         &i)))
1588                                 goto error0;
1589                         XFS_WANT_CORRUPTED_GOTO(
1590                                 i == 1 && xxbno == ltbno && xxlen == ltlen,
1591                                 error0);
1592                 }
1593 #endif
1594                 /*
1595                  * Update remaining by-block entry to the new, joined block.
1596                  */
1597                 nbno = ltbno;
1598                 nlen = len + ltlen + gtlen;
1599                 if ((error = xfs_alloc_update(bno_cur, nbno, nlen)))
1600                         goto error0;
1601         }
1602         /*
1603          * Have only a left contiguous neighbor.
1604          * Merge it together with the new freespace.
1605          */
1606         else if (haveleft) {
1607                 /*
1608                  * Delete the old by-size entry on the left.
1609                  */
1610                 if ((error = xfs_alloc_lookup_eq(cnt_cur, ltbno, ltlen, &i)))
1611                         goto error0;
1612                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1613                 if ((error = xfs_btree_delete(cnt_cur, &i)))
1614                         goto error0;
1615                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1616                 /*
1617                  * Back up the by-block cursor to the left neighbor, and
1618                  * update its length.
1619                  */
1620                 if ((error = xfs_btree_decrement(bno_cur, 0, &i)))
1621                         goto error0;
1622                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1623                 nbno = ltbno;
1624                 nlen = len + ltlen;
1625                 if ((error = xfs_alloc_update(bno_cur, nbno, nlen)))
1626                         goto error0;
1627         }
1628         /*
1629          * Have only a right contiguous neighbor.
1630          * Merge it together with the new freespace.
1631          */
1632         else if (haveright) {
1633                 /*
1634                  * Delete the old by-size entry on the right.
1635                  */
1636                 if ((error = xfs_alloc_lookup_eq(cnt_cur, gtbno, gtlen, &i)))
1637                         goto error0;
1638                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1639                 if ((error = xfs_btree_delete(cnt_cur, &i)))
1640                         goto error0;
1641                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1642                 /*
1643                  * Update the starting block and length of the right
1644                  * neighbor in the by-block tree.
1645                  */
1646                 nbno = bno;
1647                 nlen = len + gtlen;
1648                 if ((error = xfs_alloc_update(bno_cur, nbno, nlen)))
1649                         goto error0;
1650         }
1651         /*
1652          * No contiguous neighbors.
1653          * Insert the new freespace into the by-block tree.
1654          */
1655         else {
1656                 nbno = bno;
1657                 nlen = len;
1658                 if ((error = xfs_btree_insert(bno_cur, &i)))
1659                         goto error0;
1660                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1661         }
1662         xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
1663         bno_cur = NULL;
1664         /*
1665          * In all cases we need to insert the new freespace in the by-size tree.
1666          */
1667         if ((error = xfs_alloc_lookup_eq(cnt_cur, nbno, nlen, &i)))
1668                 goto error0;
1669         XFS_WANT_CORRUPTED_GOTO(i == 0, error0);
1670         if ((error = xfs_btree_insert(cnt_cur, &i)))
1671                 goto error0;
1672         XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1673         xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1674         cnt_cur = NULL;
1675
1676         /*
1677          * Update the freespace totals in the ag and superblock.
1678          */
1679         pag = xfs_perag_get(mp, agno);
1680         error = xfs_alloc_update_counters(tp, pag, agbp, len);
1681         xfs_perag_put(pag);
1682         if (error)
1683                 goto error0;
1684
1685         if (!isfl)
1686                 xfs_trans_mod_sb(tp, XFS_TRANS_SB_FDBLOCKS, (long)len);
1687         XFS_STATS_INC(xs_freex);
1688         XFS_STATS_ADD(xs_freeb, len);
1689
1690         trace_xfs_free_extent(mp, agno, bno, len, isfl, haveleft, haveright);
1691
1692         return 0;
1693
1694  error0:
1695         trace_xfs_free_extent(mp, agno, bno, len, isfl, -1, -1);
1696         if (bno_cur)
1697                 xfs_btree_del_cursor(bno_cur, XFS_BTREE_ERROR);
1698         if (cnt_cur)
1699                 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
1700         return error;
1701 }
1702
1703 /*
1704  * Visible (exported) allocation/free functions.
1705  * Some of these are used just by xfs_alloc_btree.c and this file.
1706  */
1707
1708 /*
1709  * Compute and fill in value of m_ag_maxlevels.
1710  */
1711 void
1712 xfs_alloc_compute_maxlevels(
1713         xfs_mount_t     *mp)    /* file system mount structure */
1714 {
1715         int             level;
1716         uint            maxblocks;
1717         uint            maxleafents;
1718         int             minleafrecs;
1719         int             minnoderecs;
1720
1721         maxleafents = (mp->m_sb.sb_agblocks + 1) / 2;
1722         minleafrecs = mp->m_alloc_mnr[0];
1723         minnoderecs = mp->m_alloc_mnr[1];
1724         maxblocks = (maxleafents + minleafrecs - 1) / minleafrecs;
1725         for (level = 1; maxblocks > 1; level++)
1726                 maxblocks = (maxblocks + minnoderecs - 1) / minnoderecs;
1727         mp->m_ag_maxlevels = level;
1728 }
1729
1730 /*
1731  * Find the length of the longest extent in an AG.
1732  */
1733 xfs_extlen_t
1734 xfs_alloc_longest_free_extent(
1735         struct xfs_mount        *mp,
1736         struct xfs_perag        *pag)
1737 {
1738         xfs_extlen_t            need, delta = 0;
1739
1740         need = XFS_MIN_FREELIST_PAG(pag, mp);
1741         if (need > pag->pagf_flcount)
1742                 delta = need - pag->pagf_flcount;
1743
1744         if (pag->pagf_longest > delta)
1745                 return pag->pagf_longest - delta;
1746         return pag->pagf_flcount > 0 || pag->pagf_longest > 0;
1747 }
1748
1749 /*
1750  * Decide whether to use this allocation group for this allocation.
1751  * If so, fix up the btree freelist's size.
1752  */
1753 STATIC int                      /* error */
1754 xfs_alloc_fix_freelist(
1755         xfs_alloc_arg_t *args,  /* allocation argument structure */
1756         int             flags)  /* XFS_ALLOC_FLAG_... */
1757 {
1758         xfs_buf_t       *agbp;  /* agf buffer pointer */
1759         xfs_agf_t       *agf;   /* a.g. freespace structure pointer */
1760         xfs_buf_t       *agflbp;/* agfl buffer pointer */
1761         xfs_agblock_t   bno;    /* freelist block */
1762         xfs_extlen_t    delta;  /* new blocks needed in freelist */
1763         int             error;  /* error result code */
1764         xfs_extlen_t    longest;/* longest extent in allocation group */
1765         xfs_mount_t     *mp;    /* file system mount point structure */
1766         xfs_extlen_t    need;   /* total blocks needed in freelist */
1767         xfs_perag_t     *pag;   /* per-ag information structure */
1768         xfs_alloc_arg_t targs;  /* local allocation arguments */
1769         xfs_trans_t     *tp;    /* transaction pointer */
1770
1771         mp = args->mp;
1772
1773         pag = args->pag;
1774         tp = args->tp;
1775         if (!pag->pagf_init) {
1776                 if ((error = xfs_alloc_read_agf(mp, tp, args->agno, flags,
1777                                 &agbp)))
1778                         return error;
1779                 if (!pag->pagf_init) {
1780                         ASSERT(flags & XFS_ALLOC_FLAG_TRYLOCK);
1781                         ASSERT(!(flags & XFS_ALLOC_FLAG_FREEING));
1782                         args->agbp = NULL;
1783                         return 0;
1784                 }
1785         } else
1786                 agbp = NULL;
1787
1788         /*
1789          * If this is a metadata preferred pag and we are user data
1790          * then try somewhere else if we are not being asked to
1791          * try harder at this point
1792          */
1793         if (pag->pagf_metadata && args->userdata &&
1794             (flags & XFS_ALLOC_FLAG_TRYLOCK)) {
1795                 ASSERT(!(flags & XFS_ALLOC_FLAG_FREEING));
1796                 args->agbp = NULL;
1797                 return 0;
1798         }
1799
1800         if (!(flags & XFS_ALLOC_FLAG_FREEING)) {
1801                 /*
1802                  * If it looks like there isn't a long enough extent, or enough
1803                  * total blocks, reject it.
1804                  */
1805                 need = XFS_MIN_FREELIST_PAG(pag, mp);
1806                 longest = xfs_alloc_longest_free_extent(mp, pag);
1807                 if ((args->minlen + args->alignment + args->minalignslop - 1) >
1808                                 longest ||
1809                     ((int)(pag->pagf_freeblks + pag->pagf_flcount -
1810                            need - args->total) < (int)args->minleft)) {
1811                         if (agbp)
1812                                 xfs_trans_brelse(tp, agbp);
1813                         args->agbp = NULL;
1814                         return 0;
1815                 }
1816         }
1817
1818         /*
1819          * Get the a.g. freespace buffer.
1820          * Can fail if we're not blocking on locks, and it's held.
1821          */
1822         if (agbp == NULL) {
1823                 if ((error = xfs_alloc_read_agf(mp, tp, args->agno, flags,
1824                                 &agbp)))
1825                         return error;
1826                 if (agbp == NULL) {
1827                         ASSERT(flags & XFS_ALLOC_FLAG_TRYLOCK);
1828                         ASSERT(!(flags & XFS_ALLOC_FLAG_FREEING));
1829                         args->agbp = NULL;
1830                         return 0;
1831                 }
1832         }
1833         /*
1834          * Figure out how many blocks we should have in the freelist.
1835          */
1836         agf = XFS_BUF_TO_AGF(agbp);
1837         need = XFS_MIN_FREELIST(agf, mp);
1838         /*
1839          * If there isn't enough total or single-extent, reject it.
1840          */
1841         if (!(flags & XFS_ALLOC_FLAG_FREEING)) {
1842                 delta = need > be32_to_cpu(agf->agf_flcount) ?
1843                         (need - be32_to_cpu(agf->agf_flcount)) : 0;
1844                 longest = be32_to_cpu(agf->agf_longest);
1845                 longest = (longest > delta) ? (longest - delta) :
1846                         (be32_to_cpu(agf->agf_flcount) > 0 || longest > 0);
1847                 if ((args->minlen + args->alignment + args->minalignslop - 1) >
1848                                 longest ||
1849                     ((int)(be32_to_cpu(agf->agf_freeblks) +
1850                      be32_to_cpu(agf->agf_flcount) - need - args->total) <
1851                                 (int)args->minleft)) {
1852                         xfs_trans_brelse(tp, agbp);
1853                         args->agbp = NULL;
1854                         return 0;
1855                 }
1856         }
1857         /*
1858          * Make the freelist shorter if it's too long.
1859          */
1860         while (be32_to_cpu(agf->agf_flcount) > need) {
1861                 xfs_buf_t       *bp;
1862
1863                 error = xfs_alloc_get_freelist(tp, agbp, &bno, 0);
1864                 if (error)
1865                         return error;
1866                 if ((error = xfs_free_ag_extent(tp, agbp, args->agno, bno, 1, 1)))
1867                         return error;
1868                 bp = xfs_btree_get_bufs(mp, tp, args->agno, bno, 0);
1869                 xfs_trans_binval(tp, bp);
1870         }
1871         /*
1872          * Initialize the args structure.
1873          */
1874         targs.tp = tp;
1875         targs.mp = mp;
1876         targs.agbp = agbp;
1877         targs.agno = args->agno;
1878         targs.mod = targs.minleft = targs.wasdel = targs.userdata =
1879                 targs.minalignslop = 0;
1880         targs.alignment = targs.minlen = targs.prod = targs.isfl = 1;
1881         targs.type = XFS_ALLOCTYPE_THIS_AG;
1882         targs.pag = pag;
1883         if ((error = xfs_alloc_read_agfl(mp, tp, targs.agno, &agflbp)))
1884                 return error;
1885         /*
1886          * Make the freelist longer if it's too short.
1887          */
1888         while (be32_to_cpu(agf->agf_flcount) < need) {
1889                 targs.agbno = 0;
1890                 targs.maxlen = need - be32_to_cpu(agf->agf_flcount);
1891                 /*
1892                  * Allocate as many blocks as possible at once.
1893                  */
1894                 if ((error = xfs_alloc_ag_vextent(&targs))) {
1895                         xfs_trans_brelse(tp, agflbp);
1896                         return error;
1897                 }
1898                 /*
1899                  * Stop if we run out.  Won't happen if callers are obeying
1900                  * the restrictions correctly.  Can happen for free calls
1901                  * on a completely full ag.
1902                  */
1903                 if (targs.agbno == NULLAGBLOCK) {
1904                         if (flags & XFS_ALLOC_FLAG_FREEING)
1905                                 break;
1906                         xfs_trans_brelse(tp, agflbp);
1907                         args->agbp = NULL;
1908                         return 0;
1909                 }
1910                 /*
1911                  * Put each allocated block on the list.
1912                  */
1913                 for (bno = targs.agbno; bno < targs.agbno + targs.len; bno++) {
1914                         error = xfs_alloc_put_freelist(tp, agbp,
1915                                                         agflbp, bno, 0);
1916                         if (error)
1917                                 return error;
1918                 }
1919         }
1920         xfs_trans_brelse(tp, agflbp);
1921         args->agbp = agbp;
1922         return 0;
1923 }
1924
1925 /*
1926  * Get a block from the freelist.
1927  * Returns with the buffer for the block gotten.
1928  */
1929 int                             /* error */
1930 xfs_alloc_get_freelist(
1931         xfs_trans_t     *tp,    /* transaction pointer */
1932         xfs_buf_t       *agbp,  /* buffer containing the agf structure */
1933         xfs_agblock_t   *bnop,  /* block address retrieved from freelist */
1934         int             btreeblk) /* destination is a AGF btree */
1935 {
1936         xfs_agf_t       *agf;   /* a.g. freespace structure */
1937         xfs_agfl_t      *agfl;  /* a.g. freelist structure */
1938         xfs_buf_t       *agflbp;/* buffer for a.g. freelist structure */
1939         xfs_agblock_t   bno;    /* block number returned */
1940         int             error;
1941         int             logflags;
1942         xfs_mount_t     *mp;    /* mount structure */
1943         xfs_perag_t     *pag;   /* per allocation group data */
1944
1945         agf = XFS_BUF_TO_AGF(agbp);
1946         /*
1947          * Freelist is empty, give up.
1948          */
1949         if (!agf->agf_flcount) {
1950                 *bnop = NULLAGBLOCK;
1951                 return 0;
1952         }
1953         /*
1954          * Read the array of free blocks.
1955          */
1956         mp = tp->t_mountp;
1957         if ((error = xfs_alloc_read_agfl(mp, tp,
1958                         be32_to_cpu(agf->agf_seqno), &agflbp)))
1959                 return error;
1960         agfl = XFS_BUF_TO_AGFL(agflbp);
1961         /*
1962          * Get the block number and update the data structures.
1963          */
1964         bno = be32_to_cpu(agfl->agfl_bno[be32_to_cpu(agf->agf_flfirst)]);
1965         be32_add_cpu(&agf->agf_flfirst, 1);
1966         xfs_trans_brelse(tp, agflbp);
1967         if (be32_to_cpu(agf->agf_flfirst) == XFS_AGFL_SIZE(mp))
1968                 agf->agf_flfirst = 0;
1969
1970         pag = xfs_perag_get(mp, be32_to_cpu(agf->agf_seqno));
1971         be32_add_cpu(&agf->agf_flcount, -1);
1972         xfs_trans_agflist_delta(tp, -1);
1973         pag->pagf_flcount--;
1974         xfs_perag_put(pag);
1975
1976         logflags = XFS_AGF_FLFIRST | XFS_AGF_FLCOUNT;
1977         if (btreeblk) {
1978                 be32_add_cpu(&agf->agf_btreeblks, 1);
1979                 pag->pagf_btreeblks++;
1980                 logflags |= XFS_AGF_BTREEBLKS;
1981         }
1982
1983         xfs_alloc_log_agf(tp, agbp, logflags);
1984         *bnop = bno;
1985
1986         return 0;
1987 }
1988
1989 /*
1990  * Log the given fields from the agf structure.
1991  */
1992 void
1993 xfs_alloc_log_agf(
1994         xfs_trans_t     *tp,    /* transaction pointer */
1995         xfs_buf_t       *bp,    /* buffer for a.g. freelist header */
1996         int             fields) /* mask of fields to be logged (XFS_AGF_...) */
1997 {
1998         int     first;          /* first byte offset */
1999         int     last;           /* last byte offset */
2000         static const short      offsets[] = {
2001                 offsetof(xfs_agf_t, agf_magicnum),
2002                 offsetof(xfs_agf_t, agf_versionnum),
2003                 offsetof(xfs_agf_t, agf_seqno),
2004                 offsetof(xfs_agf_t, agf_length),
2005                 offsetof(xfs_agf_t, agf_roots[0]),
2006                 offsetof(xfs_agf_t, agf_levels[0]),
2007                 offsetof(xfs_agf_t, agf_flfirst),
2008                 offsetof(xfs_agf_t, agf_fllast),
2009                 offsetof(xfs_agf_t, agf_flcount),
2010                 offsetof(xfs_agf_t, agf_freeblks),
2011                 offsetof(xfs_agf_t, agf_longest),
2012                 offsetof(xfs_agf_t, agf_btreeblks),
2013                 sizeof(xfs_agf_t)
2014         };
2015
2016         trace_xfs_agf(tp->t_mountp, XFS_BUF_TO_AGF(bp), fields, _RET_IP_);
2017
2018         xfs_btree_offsets(fields, offsets, XFS_AGF_NUM_BITS, &first, &last);
2019         xfs_trans_log_buf(tp, bp, (uint)first, (uint)last);
2020 }
2021
2022 /*
2023  * Interface for inode allocation to force the pag data to be initialized.
2024  */
2025 int                                     /* error */
2026 xfs_alloc_pagf_init(
2027         xfs_mount_t             *mp,    /* file system mount structure */
2028         xfs_trans_t             *tp,    /* transaction pointer */
2029         xfs_agnumber_t          agno,   /* allocation group number */
2030         int                     flags)  /* XFS_ALLOC_FLAGS_... */
2031 {
2032         xfs_buf_t               *bp;
2033         int                     error;
2034
2035         if ((error = xfs_alloc_read_agf(mp, tp, agno, flags, &bp)))
2036                 return error;
2037         if (bp)
2038                 xfs_trans_brelse(tp, bp);
2039         return 0;
2040 }
2041
2042 /*
2043  * Put the block on the freelist for the allocation group.
2044  */
2045 int                                     /* error */
2046 xfs_alloc_put_freelist(
2047         xfs_trans_t             *tp,    /* transaction pointer */
2048         xfs_buf_t               *agbp,  /* buffer for a.g. freelist header */
2049         xfs_buf_t               *agflbp,/* buffer for a.g. free block array */
2050         xfs_agblock_t           bno,    /* block being freed */
2051         int                     btreeblk) /* block came from a AGF btree */
2052 {
2053         xfs_agf_t               *agf;   /* a.g. freespace structure */
2054         xfs_agfl_t              *agfl;  /* a.g. free block array */
2055         __be32                  *blockp;/* pointer to array entry */
2056         int                     error;
2057         int                     logflags;
2058         xfs_mount_t             *mp;    /* mount structure */
2059         xfs_perag_t             *pag;   /* per allocation group data */
2060
2061         agf = XFS_BUF_TO_AGF(agbp);
2062         mp = tp->t_mountp;
2063
2064         if (!agflbp && (error = xfs_alloc_read_agfl(mp, tp,
2065                         be32_to_cpu(agf->agf_seqno), &agflbp)))
2066                 return error;
2067         agfl = XFS_BUF_TO_AGFL(agflbp);
2068         be32_add_cpu(&agf->agf_fllast, 1);
2069         if (be32_to_cpu(agf->agf_fllast) == XFS_AGFL_SIZE(mp))
2070                 agf->agf_fllast = 0;
2071
2072         pag = xfs_perag_get(mp, be32_to_cpu(agf->agf_seqno));
2073         be32_add_cpu(&agf->agf_flcount, 1);
2074         xfs_trans_agflist_delta(tp, 1);
2075         pag->pagf_flcount++;
2076
2077         logflags = XFS_AGF_FLLAST | XFS_AGF_FLCOUNT;
2078         if (btreeblk) {
2079                 be32_add_cpu(&agf->agf_btreeblks, -1);
2080                 pag->pagf_btreeblks--;
2081                 logflags |= XFS_AGF_BTREEBLKS;
2082         }
2083         xfs_perag_put(pag);
2084
2085         xfs_alloc_log_agf(tp, agbp, logflags);
2086
2087         ASSERT(be32_to_cpu(agf->agf_flcount) <= XFS_AGFL_SIZE(mp));
2088         blockp = &agfl->agfl_bno[be32_to_cpu(agf->agf_fllast)];
2089         *blockp = cpu_to_be32(bno);
2090         xfs_alloc_log_agf(tp, agbp, logflags);
2091         xfs_trans_log_buf(tp, agflbp,
2092                 (int)((xfs_caddr_t)blockp - (xfs_caddr_t)agfl),
2093                 (int)((xfs_caddr_t)blockp - (xfs_caddr_t)agfl +
2094                         sizeof(xfs_agblock_t) - 1));
2095         return 0;
2096 }
2097
2098 /*
2099  * Read in the allocation group header (free/alloc section).
2100  */
2101 int                                     /* error */
2102 xfs_read_agf(
2103         struct xfs_mount        *mp,    /* mount point structure */
2104         struct xfs_trans        *tp,    /* transaction pointer */
2105         xfs_agnumber_t          agno,   /* allocation group number */
2106         int                     flags,  /* XFS_BUF_ */
2107         struct xfs_buf          **bpp)  /* buffer for the ag freelist header */
2108 {
2109         struct xfs_agf  *agf;           /* ag freelist header */
2110         int             agf_ok;         /* set if agf is consistent */
2111         int             error;
2112
2113         ASSERT(agno != NULLAGNUMBER);
2114         error = xfs_trans_read_buf(
2115                         mp, tp, mp->m_ddev_targp,
2116                         XFS_AG_DADDR(mp, agno, XFS_AGF_DADDR(mp)),
2117                         XFS_FSS_TO_BB(mp, 1), flags, bpp);
2118         if (error)
2119                 return error;
2120         if (!*bpp)
2121                 return 0;
2122
2123         ASSERT(!XFS_BUF_GETERROR(*bpp));
2124         agf = XFS_BUF_TO_AGF(*bpp);
2125
2126         /*
2127          * Validate the magic number of the agf block.
2128          */
2129         agf_ok =
2130                 be32_to_cpu(agf->agf_magicnum) == XFS_AGF_MAGIC &&
2131                 XFS_AGF_GOOD_VERSION(be32_to_cpu(agf->agf_versionnum)) &&
2132                 be32_to_cpu(agf->agf_freeblks) <= be32_to_cpu(agf->agf_length) &&
2133                 be32_to_cpu(agf->agf_flfirst) < XFS_AGFL_SIZE(mp) &&
2134                 be32_to_cpu(agf->agf_fllast) < XFS_AGFL_SIZE(mp) &&
2135                 be32_to_cpu(agf->agf_flcount) <= XFS_AGFL_SIZE(mp) &&
2136                 be32_to_cpu(agf->agf_seqno) == agno;
2137         if (xfs_sb_version_haslazysbcount(&mp->m_sb))
2138                 agf_ok = agf_ok && be32_to_cpu(agf->agf_btreeblks) <=
2139                                                 be32_to_cpu(agf->agf_length);
2140         if (unlikely(XFS_TEST_ERROR(!agf_ok, mp, XFS_ERRTAG_ALLOC_READ_AGF,
2141                         XFS_RANDOM_ALLOC_READ_AGF))) {
2142                 XFS_CORRUPTION_ERROR("xfs_alloc_read_agf",
2143                                      XFS_ERRLEVEL_LOW, mp, agf);
2144                 xfs_trans_brelse(tp, *bpp);
2145                 return XFS_ERROR(EFSCORRUPTED);
2146         }
2147         XFS_BUF_SET_VTYPE_REF(*bpp, B_FS_AGF, XFS_AGF_REF);
2148         return 0;
2149 }
2150
2151 /*
2152  * Read in the allocation group header (free/alloc section).
2153  */
2154 int                                     /* error */
2155 xfs_alloc_read_agf(
2156         struct xfs_mount        *mp,    /* mount point structure */
2157         struct xfs_trans        *tp,    /* transaction pointer */
2158         xfs_agnumber_t          agno,   /* allocation group number */
2159         int                     flags,  /* XFS_ALLOC_FLAG_... */
2160         struct xfs_buf          **bpp)  /* buffer for the ag freelist header */
2161 {
2162         struct xfs_agf          *agf;           /* ag freelist header */
2163         struct xfs_perag        *pag;           /* per allocation group data */
2164         int                     error;
2165
2166         ASSERT(agno != NULLAGNUMBER);
2167
2168         error = xfs_read_agf(mp, tp, agno,
2169                         (flags & XFS_ALLOC_FLAG_TRYLOCK) ? XBF_TRYLOCK : 0,
2170                         bpp);
2171         if (error)
2172                 return error;
2173         if (!*bpp)
2174                 return 0;
2175         ASSERT(!XFS_BUF_GETERROR(*bpp));
2176
2177         agf = XFS_BUF_TO_AGF(*bpp);
2178         pag = xfs_perag_get(mp, agno);
2179         if (!pag->pagf_init) {
2180                 pag->pagf_freeblks = be32_to_cpu(agf->agf_freeblks);
2181                 pag->pagf_btreeblks = be32_to_cpu(agf->agf_btreeblks);
2182                 pag->pagf_flcount = be32_to_cpu(agf->agf_flcount);
2183                 pag->pagf_longest = be32_to_cpu(agf->agf_longest);
2184                 pag->pagf_levels[XFS_BTNUM_BNOi] =
2185                         be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNOi]);
2186                 pag->pagf_levels[XFS_BTNUM_CNTi] =
2187                         be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNTi]);
2188                 spin_lock_init(&pag->pagb_lock);
2189                 pag->pagb_count = 0;
2190                 pag->pagb_tree = RB_ROOT;
2191                 pag->pagf_init = 1;
2192         }
2193 #ifdef DEBUG
2194         else if (!XFS_FORCED_SHUTDOWN(mp)) {
2195                 ASSERT(pag->pagf_freeblks == be32_to_cpu(agf->agf_freeblks));
2196                 ASSERT(pag->pagf_btreeblks == be32_to_cpu(agf->agf_btreeblks));
2197                 ASSERT(pag->pagf_flcount == be32_to_cpu(agf->agf_flcount));
2198                 ASSERT(pag->pagf_longest == be32_to_cpu(agf->agf_longest));
2199                 ASSERT(pag->pagf_levels[XFS_BTNUM_BNOi] ==
2200                        be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNOi]));
2201                 ASSERT(pag->pagf_levels[XFS_BTNUM_CNTi] ==
2202                        be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNTi]));
2203         }
2204 #endif
2205         xfs_perag_put(pag);
2206         return 0;
2207 }
2208
2209 /*
2210  * Allocate an extent (variable-size).
2211  * Depending on the allocation type, we either look in a single allocation
2212  * group or loop over the allocation groups to find the result.
2213  */
2214 int                             /* error */
2215 xfs_alloc_vextent(
2216         xfs_alloc_arg_t *args)  /* allocation argument structure */
2217 {
2218         xfs_agblock_t   agsize; /* allocation group size */
2219         int             error;
2220         int             flags;  /* XFS_ALLOC_FLAG_... locking flags */
2221         xfs_extlen_t    minleft;/* minimum left value, temp copy */
2222         xfs_mount_t     *mp;    /* mount structure pointer */
2223         xfs_agnumber_t  sagno;  /* starting allocation group number */
2224         xfs_alloctype_t type;   /* input allocation type */
2225         int             bump_rotor = 0;
2226         int             no_min = 0;
2227         xfs_agnumber_t  rotorstep = xfs_rotorstep; /* inode32 agf stepper */
2228
2229         mp = args->mp;
2230         type = args->otype = args->type;
2231         args->agbno = NULLAGBLOCK;
2232         /*
2233          * Just fix this up, for the case where the last a.g. is shorter
2234          * (or there's only one a.g.) and the caller couldn't easily figure
2235          * that out (xfs_bmap_alloc).
2236          */
2237         agsize = mp->m_sb.sb_agblocks;
2238         if (args->maxlen > agsize)
2239                 args->maxlen = agsize;
2240         if (args->alignment == 0)
2241                 args->alignment = 1;
2242         ASSERT(XFS_FSB_TO_AGNO(mp, args->fsbno) < mp->m_sb.sb_agcount);
2243         ASSERT(XFS_FSB_TO_AGBNO(mp, args->fsbno) < agsize);
2244         ASSERT(args->minlen <= args->maxlen);
2245         ASSERT(args->minlen <= agsize);
2246         ASSERT(args->mod < args->prod);
2247         if (XFS_FSB_TO_AGNO(mp, args->fsbno) >= mp->m_sb.sb_agcount ||
2248             XFS_FSB_TO_AGBNO(mp, args->fsbno) >= agsize ||
2249             args->minlen > args->maxlen || args->minlen > agsize ||
2250             args->mod >= args->prod) {
2251                 args->fsbno = NULLFSBLOCK;
2252                 trace_xfs_alloc_vextent_badargs(args);
2253                 return 0;
2254         }
2255         minleft = args->minleft;
2256
2257         switch (type) {
2258         case XFS_ALLOCTYPE_THIS_AG:
2259         case XFS_ALLOCTYPE_NEAR_BNO:
2260         case XFS_ALLOCTYPE_THIS_BNO:
2261                 /*
2262                  * These three force us into a single a.g.
2263                  */
2264                 args->agno = XFS_FSB_TO_AGNO(mp, args->fsbno);
2265                 args->pag = xfs_perag_get(mp, args->agno);
2266                 args->minleft = 0;
2267                 error = xfs_alloc_fix_freelist(args, 0);
2268                 args->minleft = minleft;
2269                 if (error) {
2270                         trace_xfs_alloc_vextent_nofix(args);
2271                         goto error0;
2272                 }
2273                 if (!args->agbp) {
2274                         trace_xfs_alloc_vextent_noagbp(args);
2275                         break;
2276                 }
2277                 args->agbno = XFS_FSB_TO_AGBNO(mp, args->fsbno);
2278                 if ((error = xfs_alloc_ag_vextent(args)))
2279                         goto error0;
2280                 break;
2281         case XFS_ALLOCTYPE_START_BNO:
2282                 /*
2283                  * Try near allocation first, then anywhere-in-ag after
2284                  * the first a.g. fails.
2285                  */
2286                 if ((args->userdata  == XFS_ALLOC_INITIAL_USER_DATA) &&
2287                     (mp->m_flags & XFS_MOUNT_32BITINODES)) {
2288                         args->fsbno = XFS_AGB_TO_FSB(mp,
2289                                         ((mp->m_agfrotor / rotorstep) %
2290                                         mp->m_sb.sb_agcount), 0);
2291                         bump_rotor = 1;
2292                 }
2293                 args->agbno = XFS_FSB_TO_AGBNO(mp, args->fsbno);
2294                 args->type = XFS_ALLOCTYPE_NEAR_BNO;
2295                 /* FALLTHROUGH */
2296         case XFS_ALLOCTYPE_ANY_AG:
2297         case XFS_ALLOCTYPE_START_AG:
2298         case XFS_ALLOCTYPE_FIRST_AG:
2299                 /*
2300                  * Rotate through the allocation groups looking for a winner.
2301                  */
2302                 if (type == XFS_ALLOCTYPE_ANY_AG) {
2303                         /*
2304                          * Start with the last place we left off.
2305                          */
2306                         args->agno = sagno = (mp->m_agfrotor / rotorstep) %
2307                                         mp->m_sb.sb_agcount;
2308                         args->type = XFS_ALLOCTYPE_THIS_AG;
2309                         flags = XFS_ALLOC_FLAG_TRYLOCK;
2310                 } else if (type == XFS_ALLOCTYPE_FIRST_AG) {
2311                         /*
2312                          * Start with allocation group given by bno.
2313                          */
2314                         args->agno = XFS_FSB_TO_AGNO(mp, args->fsbno);
2315                         args->type = XFS_ALLOCTYPE_THIS_AG;
2316                         sagno = 0;
2317                         flags = 0;
2318                 } else {
2319                         if (type == XFS_ALLOCTYPE_START_AG)
2320                                 args->type = XFS_ALLOCTYPE_THIS_AG;
2321                         /*
2322                          * Start with the given allocation group.
2323                          */
2324                         args->agno = sagno = XFS_FSB_TO_AGNO(mp, args->fsbno);
2325                         flags = XFS_ALLOC_FLAG_TRYLOCK;
2326                 }
2327                 /*
2328                  * Loop over allocation groups twice; first time with
2329                  * trylock set, second time without.
2330                  */
2331                 for (;;) {
2332                         args->pag = xfs_perag_get(mp, args->agno);
2333                         if (no_min) args->minleft = 0;
2334                         error = xfs_alloc_fix_freelist(args, flags);
2335                         args->minleft = minleft;
2336                         if (error) {
2337                                 trace_xfs_alloc_vextent_nofix(args);
2338                                 goto error0;
2339                         }
2340                         /*
2341                          * If we get a buffer back then the allocation will fly.
2342                          */
2343                         if (args->agbp) {
2344                                 if ((error = xfs_alloc_ag_vextent(args)))
2345                                         goto error0;
2346                                 break;
2347                         }
2348
2349                         trace_xfs_alloc_vextent_loopfailed(args);
2350
2351                         /*
2352                          * Didn't work, figure out the next iteration.
2353                          */
2354                         if (args->agno == sagno &&
2355                             type == XFS_ALLOCTYPE_START_BNO)
2356                                 args->type = XFS_ALLOCTYPE_THIS_AG;
2357                         /*
2358                         * For the first allocation, we can try any AG to get
2359                         * space.  However, if we already have allocated a
2360                         * block, we don't want to try AGs whose number is below
2361                         * sagno. Otherwise, we may end up with out-of-order
2362                         * locking of AGF, which might cause deadlock.
2363                         */
2364                         if (++(args->agno) == mp->m_sb.sb_agcount) {
2365                                 if (args->firstblock != NULLFSBLOCK)
2366                                         args->agno = sagno;
2367                                 else
2368                                         args->agno = 0;
2369                         }
2370                         /*
2371                          * Reached the starting a.g., must either be done
2372                          * or switch to non-trylock mode.
2373                          */
2374                         if (args->agno == sagno) {
2375                                 if (no_min == 1) {
2376                                         args->agbno = NULLAGBLOCK;
2377                                         trace_xfs_alloc_vextent_allfailed(args);
2378                                         break;
2379                                 }
2380                                 if (flags == 0) {
2381                                         no_min = 1;
2382                                 } else {
2383                                         flags = 0;
2384                                         if (type == XFS_ALLOCTYPE_START_BNO) {
2385                                                 args->agbno = XFS_FSB_TO_AGBNO(mp,
2386                                                         args->fsbno);
2387                                                 args->type = XFS_ALLOCTYPE_NEAR_BNO;
2388                                         }
2389                                 }
2390                         }
2391                         xfs_perag_put(args->pag);
2392                 }
2393                 if (bump_rotor || (type == XFS_ALLOCTYPE_ANY_AG)) {
2394                         if (args->agno == sagno)
2395                                 mp->m_agfrotor = (mp->m_agfrotor + 1) %
2396                                         (mp->m_sb.sb_agcount * rotorstep);
2397                         else
2398                                 mp->m_agfrotor = (args->agno * rotorstep + 1) %
2399                                         (mp->m_sb.sb_agcount * rotorstep);
2400                 }
2401                 break;
2402         default:
2403                 ASSERT(0);
2404                 /* NOTREACHED */
2405         }
2406         if (args->agbno == NULLAGBLOCK)
2407                 args->fsbno = NULLFSBLOCK;
2408         else {
2409                 args->fsbno = XFS_AGB_TO_FSB(mp, args->agno, args->agbno);
2410 #ifdef DEBUG
2411                 ASSERT(args->len >= args->minlen);
2412                 ASSERT(args->len <= args->maxlen);
2413                 ASSERT(args->agbno % args->alignment == 0);
2414                 XFS_AG_CHECK_DADDR(mp, XFS_FSB_TO_DADDR(mp, args->fsbno),
2415                         args->len);
2416 #endif
2417         }
2418         xfs_perag_put(args->pag);
2419         return 0;
2420 error0:
2421         xfs_perag_put(args->pag);
2422         return error;
2423 }
2424
2425 /*
2426  * Free an extent.
2427  * Just break up the extent address and hand off to xfs_free_ag_extent
2428  * after fixing up the freelist.
2429  */
2430 int                             /* error */
2431 xfs_free_extent(
2432         xfs_trans_t     *tp,    /* transaction pointer */
2433         xfs_fsblock_t   bno,    /* starting block number of extent */
2434         xfs_extlen_t    len)    /* length of extent */
2435 {
2436         xfs_alloc_arg_t args;
2437         int             error;
2438
2439         ASSERT(len != 0);
2440         memset(&args, 0, sizeof(xfs_alloc_arg_t));
2441         args.tp = tp;
2442         args.mp = tp->t_mountp;
2443
2444         /*
2445          * validate that the block number is legal - the enables us to detect
2446          * and handle a silent filesystem corruption rather than crashing.
2447          */
2448         args.agno = XFS_FSB_TO_AGNO(args.mp, bno);
2449         if (args.agno >= args.mp->m_sb.sb_agcount)
2450                 return EFSCORRUPTED;
2451
2452         args.agbno = XFS_FSB_TO_AGBNO(args.mp, bno);
2453         if (args.agbno >= args.mp->m_sb.sb_agblocks)
2454                 return EFSCORRUPTED;
2455
2456         args.pag = xfs_perag_get(args.mp, args.agno);
2457         ASSERT(args.pag);
2458
2459         error = xfs_alloc_fix_freelist(&args, XFS_ALLOC_FLAG_FREEING);
2460         if (error)
2461                 goto error0;
2462
2463         /* validate the extent size is legal now we have the agf locked */
2464         if (args.agbno + len >
2465                         be32_to_cpu(XFS_BUF_TO_AGF(args.agbp)->agf_length)) {
2466                 error = EFSCORRUPTED;
2467                 goto error0;
2468         }
2469
2470         error = xfs_free_ag_extent(tp, args.agbp, args.agno, args.agbno, len, 0);
2471         if (!error)
2472                 xfs_alloc_busy_insert(tp, args.agno, args.agbno, len);
2473 error0:
2474         xfs_perag_put(args.pag);
2475         return error;
2476 }
2477
2478
2479 /*
2480  * AG Busy list management
2481  * The busy list contains block ranges that have been freed but whose
2482  * transactions have not yet hit disk.  If any block listed in a busy
2483  * list is reused, the transaction that freed it must be forced to disk
2484  * before continuing to use the block.
2485  *
2486  * xfs_alloc_busy_insert - add to the per-ag busy list
2487  * xfs_alloc_busy_clear - remove an item from the per-ag busy list
2488  * xfs_alloc_busy_search - search for a busy extent
2489  */
2490
2491 /*
2492  * Insert a new extent into the busy tree.
2493  *
2494  * The busy extent tree is indexed by the start block of the busy extent.
2495  * there can be multiple overlapping ranges in the busy extent tree but only
2496  * ever one entry at a given start block. The reason for this is that
2497  * multi-block extents can be freed, then smaller chunks of that extent
2498  * allocated and freed again before the first transaction commit is on disk.
2499  * If the exact same start block is freed a second time, we have to wait for
2500  * that busy extent to pass out of the tree before the new extent is inserted.
2501  * There are two main cases we have to handle here.
2502  *
2503  * The first case is a transaction that triggers a "free - allocate - free"
2504  * cycle. This can occur during btree manipulations as a btree block is freed
2505  * to the freelist, then allocated from the free list, then freed again. In
2506  * this case, the second extxpnet free is what triggers the duplicate and as
2507  * such the transaction IDs should match. Because the extent was allocated in
2508  * this transaction, the transaction must be marked as synchronous. This is
2509  * true for all cases where the free/alloc/free occurs in the one transaction,
2510  * hence the addition of the ASSERT(tp->t_flags & XFS_TRANS_SYNC) to this case.
2511  * This serves to catch violations of the second case quite effectively.
2512  *
2513  * The second case is where the free/alloc/free occur in different
2514  * transactions. In this case, the thread freeing the extent the second time
2515  * can't mark the extent busy immediately because it is already tracked in a
2516  * transaction that may be committing.  When the log commit for the existing
2517  * busy extent completes, the busy extent will be removed from the tree. If we
2518  * allow the second busy insert to continue using that busy extent structure,
2519  * it can be freed before this transaction is safely in the log.  Hence our
2520  * only option in this case is to force the log to remove the existing busy
2521  * extent from the list before we insert the new one with the current
2522  * transaction ID.
2523  *
2524  * The problem we are trying to avoid in the free-alloc-free in separate
2525  * transactions is most easily described with a timeline:
2526  *
2527  *      Thread 1        Thread 2        Thread 3        xfslogd
2528  *      xact alloc
2529  *      free X
2530  *      mark busy
2531  *      commit xact
2532  *      free xact
2533  *                      xact alloc
2534  *                      alloc X
2535  *                      busy search
2536  *                      mark xact sync
2537  *                      commit xact
2538  *                      free xact
2539  *                      force log
2540  *                      checkpoint starts
2541  *                      ....
2542  *                                      xact alloc
2543  *                                      free X
2544  *                                      mark busy
2545  *                                      finds match
2546  *                                      *** KABOOM! ***
2547  *                                      ....
2548  *                                                      log IO completes
2549  *                                                      unbusy X
2550  *                      checkpoint completes
2551  *
2552  * By issuing a log force in thread 3 @ "KABOOM", the thread will block until
2553  * the checkpoint completes, and the busy extent it matched will have been
2554  * removed from the tree when it is woken. Hence it can then continue safely.
2555  *
2556  * However, to ensure this matching process is robust, we need to use the
2557  * transaction ID for identifying transaction, as delayed logging results in
2558  * the busy extent and transaction lifecycles being different. i.e. the busy
2559  * extent is active for a lot longer than the transaction.  Hence the
2560  * transaction structure can be freed and reallocated, then mark the same
2561  * extent busy again in the new transaction. In this case the new transaction
2562  * will have a different tid but can have the same address, and hence we need
2563  * to check against the tid.
2564  *
2565  * Future: for delayed logging, we could avoid the log force if the extent was
2566  * first freed in the current checkpoint sequence. This, however, requires the
2567  * ability to pin the current checkpoint in memory until this transaction
2568  * commits to ensure that both the original free and the current one combine
2569  * logically into the one checkpoint. If the checkpoint sequences are
2570  * different, however, we still need to wait on a log force.
2571  */
2572 void
2573 xfs_alloc_busy_insert(
2574         struct xfs_trans        *tp,
2575         xfs_agnumber_t          agno,
2576         xfs_agblock_t           bno,
2577         xfs_extlen_t            len)
2578 {
2579         struct xfs_busy_extent  *new;
2580         struct xfs_busy_extent  *busyp;
2581         struct xfs_perag        *pag;
2582         struct rb_node          **rbp;
2583         struct rb_node          *parent;
2584         int                     match;
2585
2586
2587         new = kmem_zalloc(sizeof(struct xfs_busy_extent), KM_MAYFAIL);
2588         if (!new) {
2589                 /*
2590                  * No Memory!  Since it is now not possible to track the free
2591                  * block, make this a synchronous transaction to insure that
2592                  * the block is not reused before this transaction commits.
2593                  */
2594                 trace_xfs_alloc_busy(tp, agno, bno, len, 1);
2595                 xfs_trans_set_sync(tp);
2596                 return;
2597         }
2598
2599         new->agno = agno;
2600         new->bno = bno;
2601         new->length = len;
2602         new->tid = xfs_log_get_trans_ident(tp);
2603
2604         INIT_LIST_HEAD(&new->list);
2605
2606         /* trace before insert to be able to see failed inserts */
2607         trace_xfs_alloc_busy(tp, agno, bno, len, 0);
2608
2609         pag = xfs_perag_get(tp->t_mountp, new->agno);
2610 restart:
2611         spin_lock(&pag->pagb_lock);
2612         rbp = &pag->pagb_tree.rb_node;
2613         parent = NULL;
2614         busyp = NULL;
2615         match = 0;
2616         while (*rbp && match >= 0) {
2617                 parent = *rbp;
2618                 busyp = rb_entry(parent, struct xfs_busy_extent, rb_node);
2619
2620                 if (new->bno < busyp->bno) {
2621                         /* may overlap, but exact start block is lower */
2622                         rbp = &(*rbp)->rb_left;
2623                         if (new->bno + new->length > busyp->bno)
2624                                 match = busyp->tid == new->tid ? 1 : -1;
2625                 } else if (new->bno > busyp->bno) {
2626                         /* may overlap, but exact start block is higher */
2627                         rbp = &(*rbp)->rb_right;
2628                         if (bno < busyp->bno + busyp->length)
2629                                 match = busyp->tid == new->tid ? 1 : -1;
2630                 } else {
2631                         match = busyp->tid == new->tid ? 1 : -1;
2632                         break;
2633                 }
2634         }
2635         if (match < 0) {
2636                 /* overlap marked busy in different transaction */
2637                 spin_unlock(&pag->pagb_lock);
2638                 xfs_log_force(tp->t_mountp, XFS_LOG_SYNC);
2639                 goto restart;
2640         }
2641         if (match > 0) {
2642                 /*
2643                  * overlap marked busy in same transaction. Update if exact
2644                  * start block match, otherwise combine the busy extents into
2645                  * a single range.
2646                  */
2647                 if (busyp->bno == new->bno) {
2648                         busyp->length = max(busyp->length, new->length);
2649                         spin_unlock(&pag->pagb_lock);
2650                         ASSERT(tp->t_flags & XFS_TRANS_SYNC);
2651                         xfs_perag_put(pag);
2652                         kmem_free(new);
2653                         return;
2654                 }
2655                 rb_erase(&busyp->rb_node, &pag->pagb_tree);
2656                 new->length = max(busyp->bno + busyp->length,
2657                                         new->bno + new->length) -
2658                                 min(busyp->bno, new->bno);
2659                 new->bno = min(busyp->bno, new->bno);
2660         } else
2661                 busyp = NULL;
2662
2663         rb_link_node(&new->rb_node, parent, rbp);
2664         rb_insert_color(&new->rb_node, &pag->pagb_tree);
2665
2666         list_add(&new->list, &tp->t_busy);
2667         spin_unlock(&pag->pagb_lock);
2668         xfs_perag_put(pag);
2669         kmem_free(busyp);
2670 }
2671
2672 /*
2673  * Search for a busy extent within the range of the extent we are about to
2674  * allocate.  You need to be holding the busy extent tree lock when calling
2675  * xfs_alloc_busy_search(). This function returns 0 for no overlapping busy
2676  * extent, -1 for an overlapping but not exact busy extent, and 1 for an exact
2677  * match. This is done so that a non-zero return indicates an overlap that
2678  * will require a synchronous transaction, but it can still be
2679  * used to distinguish between a partial or exact match.
2680  */
2681 int
2682 xfs_alloc_busy_search(
2683         struct xfs_mount        *mp,
2684         xfs_agnumber_t          agno,
2685         xfs_agblock_t           bno,
2686         xfs_extlen_t            len)
2687 {
2688         struct xfs_perag        *pag;
2689         struct rb_node          *rbp;
2690         struct xfs_busy_extent  *busyp;
2691         int                     match = 0;
2692
2693         pag = xfs_perag_get(mp, agno);
2694         spin_lock(&pag->pagb_lock);
2695
2696         rbp = pag->pagb_tree.rb_node;
2697
2698         /* find closest start bno overlap */
2699         while (rbp) {
2700                 busyp = rb_entry(rbp, struct xfs_busy_extent, rb_node);
2701                 if (bno < busyp->bno) {
2702                         /* may overlap, but exact start block is lower */
2703                         if (bno + len > busyp->bno)
2704                                 match = -1;
2705                         rbp = rbp->rb_left;
2706                 } else if (bno > busyp->bno) {
2707                         /* may overlap, but exact start block is higher */
2708                         if (bno < busyp->bno + busyp->length)
2709                                 match = -1;
2710                         rbp = rbp->rb_right;
2711                 } else {
2712                         /* bno matches busyp, length determines exact match */
2713                         match = (busyp->length == len) ? 1 : -1;
2714                         break;
2715                 }
2716         }
2717         spin_unlock(&pag->pagb_lock);
2718         trace_xfs_alloc_busysearch(mp, agno, bno, len, !!match);
2719         xfs_perag_put(pag);
2720         return match;
2721 }
2722
2723 /*
2724  * For a given extent [fbno, flen], search the busy extent list to find a
2725  * subset of the extent that is not busy.  If *rlen is smaller than
2726  * args->minlen no suitable extent could be found, and the higher level
2727  * code needs to force out the log and retry the allocation.
2728  */
2729 STATIC void
2730 xfs_alloc_busy_trim(
2731         struct xfs_alloc_arg    *args,
2732         xfs_agblock_t           bno,
2733         xfs_extlen_t            len,
2734         xfs_agblock_t           *rbno,
2735         xfs_extlen_t            *rlen)
2736 {
2737         xfs_agblock_t           fbno = bno;
2738         xfs_extlen_t            flen = len;
2739         struct rb_node          *rbp;
2740
2741         ASSERT(flen > 0);
2742
2743         spin_lock(&args->pag->pagb_lock);
2744         rbp = args->pag->pagb_tree.rb_node;
2745         while (rbp && flen >= args->minlen) {
2746                 struct xfs_busy_extent *busyp =
2747                         rb_entry(rbp, struct xfs_busy_extent, rb_node);
2748                 xfs_agblock_t   fend = fbno + flen;
2749                 xfs_agblock_t   bbno = busyp->bno;
2750                 xfs_agblock_t   bend = bbno + busyp->length;
2751
2752                 if (fend <= bbno) {
2753                         rbp = rbp->rb_left;
2754                         continue;
2755                 } else if (fbno >= bend) {
2756                         rbp = rbp->rb_right;
2757                         continue;
2758                 }
2759
2760                 if (bbno <= fbno) {
2761                         /* start overlap */
2762
2763                         /*
2764                          * Case 1:
2765                          *    bbno           bend
2766                          *    +BBBBBBBBBBBBBBBBB+
2767                          *        +---------+
2768                          *        fbno   fend
2769                          *
2770                          * Case 2:
2771                          *    bbno           bend
2772                          *    +BBBBBBBBBBBBBBBBB+
2773                          *    +-------------+
2774                          *    fbno       fend
2775                          *
2776                          * Case 3:
2777                          *    bbno           bend
2778                          *    +BBBBBBBBBBBBBBBBB+
2779                          *        +-------------+
2780                          *        fbno       fend
2781                          *
2782                          * Case 4:
2783                          *    bbno           bend
2784                          *    +BBBBBBBBBBBBBBBBB+
2785                          *    +-----------------+
2786                          *    fbno           fend
2787                          *
2788                          * No unbusy region in extent, return failure.
2789                          */
2790                         if (fend <= bend)
2791                                 goto fail;
2792
2793                         /*
2794                          * Case 5:
2795                          *    bbno           bend
2796                          *    +BBBBBBBBBBBBBBBBB+
2797                          *        +----------------------+
2798                          *        fbno                fend
2799                          *
2800                          * Case 6:
2801                          *    bbno           bend
2802                          *    +BBBBBBBBBBBBBBBBB+
2803                          *    +--------------------------+
2804                          *    fbno                    fend
2805                          *
2806                          * Needs to be trimmed to:
2807                          *                       +-------+
2808                          *                       fbno fend
2809                          */
2810                         fbno = bend;
2811                 } else if (bend >= fend) {
2812                         /* end overlap */
2813
2814                         /*
2815                          * Case 7:
2816                          *             bbno           bend
2817                          *             +BBBBBBBBBBBBBBBBB+
2818                          *    +------------------+
2819                          *    fbno            fend
2820                          *
2821                          * Case 8:
2822                          *             bbno           bend
2823                          *             +BBBBBBBBBBBBBBBBB+
2824                          *    +--------------------------+
2825                          *    fbno                    fend
2826                          *
2827                          * Needs to be trimmed to:
2828                          *    +-------+
2829                          *    fbno fend
2830                          */
2831                         fend = bbno;
2832                 } else {
2833                         /* middle overlap */
2834
2835                         /*
2836                          * Case 9:
2837                          *             bbno           bend
2838                          *             +BBBBBBBBBBBBBBBBB+
2839                          *    +-----------------------------------+
2840                          *    fbno                             fend
2841                          *
2842                          * Can be trimmed to:
2843                          *    +-------+        OR         +-------+
2844                          *    fbno fend                   fbno fend
2845                          *
2846                          * Backward allocation leads to significant
2847                          * fragmentation of directories, which degrades
2848                          * directory performance, therefore we always want to
2849                          * choose the option that produces forward allocation
2850                          * patterns.
2851                          * Preferring the lower bno extent will make the next
2852                          * request use "fend" as the start of the next
2853                          * allocation;  if the segment is no longer busy at
2854                          * that point, we'll get a contiguous allocation, but
2855                          * even if it is still busy, we will get a forward
2856                          * allocation.
2857                          * We try to avoid choosing the segment at "bend",
2858                          * because that can lead to the next allocation
2859                          * taking the segment at "fbno", which would be a
2860                          * backward allocation.  We only use the segment at
2861                          * "fbno" if it is much larger than the current
2862                          * requested size, because in that case there's a
2863                          * good chance subsequent allocations will be
2864                          * contiguous.
2865                          */
2866                         if (bbno - fbno >= args->maxlen) {
2867                                 /* left candidate fits perfect */
2868                                 fend = bbno;
2869                         } else if (fend - bend >= args->maxlen * 4) {
2870                                 /* right candidate has enough free space */
2871                                 fbno = bend;
2872                         } else if (bbno - fbno >= args->minlen) {
2873                                 /* left candidate fits minimum requirement */
2874                                 fend = bbno;
2875                         } else {
2876                                 goto fail;
2877                         }
2878                 }
2879
2880                 flen = fend - fbno;
2881         }
2882         spin_unlock(&args->pag->pagb_lock);
2883
2884         if (fbno != bno || flen != len) {
2885                 trace_xfs_alloc_busy_trim(args->mp, args->agno, bno, len,
2886                                           fbno, flen);
2887         }
2888         *rbno = fbno;
2889         *rlen = flen;
2890         return;
2891 fail:
2892         /*
2893          * Return a zero extent length as failure indications.  All callers
2894          * re-check if the trimmed extent satisfies the minlen requirement.
2895          */
2896         spin_unlock(&args->pag->pagb_lock);
2897         trace_xfs_alloc_busy_trim(args->mp, args->agno, bno, len, fbno, 0);
2898         *rbno = fbno;
2899         *rlen = 0;
2900 }
2901
2902 void
2903 xfs_alloc_busy_clear(
2904         struct xfs_mount        *mp,
2905         struct xfs_busy_extent  *busyp)
2906 {
2907         struct xfs_perag        *pag;
2908
2909         trace_xfs_alloc_unbusy(mp, busyp->agno, busyp->bno,
2910                                                 busyp->length);
2911
2912         ASSERT(xfs_alloc_busy_search(mp, busyp->agno, busyp->bno,
2913                                                 busyp->length) == 1);
2914
2915         list_del_init(&busyp->list);
2916
2917         pag = xfs_perag_get(mp, busyp->agno);
2918         spin_lock(&pag->pagb_lock);
2919         rb_erase(&busyp->rb_node, &pag->pagb_tree);
2920         spin_unlock(&pag->pagb_lock);
2921         xfs_perag_put(pag);
2922
2923         kmem_free(busyp);
2924 }