[XFS] Update license/copyright notices to match the prefered SGI
[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_dir.h"
28 #include "xfs_dir2.h"
29 #include "xfs_dmapi.h"
30 #include "xfs_mount.h"
31 #include "xfs_bmap_btree.h"
32 #include "xfs_alloc_btree.h"
33 #include "xfs_ialloc_btree.h"
34 #include "xfs_dir_sf.h"
35 #include "xfs_dir2_sf.h"
36 #include "xfs_attr_sf.h"
37 #include "xfs_dinode.h"
38 #include "xfs_inode.h"
39 #include "xfs_btree.h"
40 #include "xfs_ialloc.h"
41 #include "xfs_alloc.h"
42 #include "xfs_error.h"
43
44
45 #define XFS_ABSDIFF(a,b)        (((a) <= (b)) ? ((b) - (a)) : ((a) - (b)))
46
47 #define XFSA_FIXUP_BNO_OK       1
48 #define XFSA_FIXUP_CNT_OK       2
49
50 STATIC int
51 xfs_alloc_search_busy(xfs_trans_t *tp,
52                     xfs_agnumber_t agno,
53                     xfs_agblock_t bno,
54                     xfs_extlen_t len);
55
56 #if defined(XFS_ALLOC_TRACE)
57 ktrace_t *xfs_alloc_trace_buf;
58
59 #define TRACE_ALLOC(s,a)        \
60         xfs_alloc_trace_alloc(fname, s, a, __LINE__)
61 #define TRACE_FREE(s,a,b,x,f)   \
62         xfs_alloc_trace_free(fname, s, mp, a, b, x, f, __LINE__)
63 #define TRACE_MODAGF(s,a,f)     \
64         xfs_alloc_trace_modagf(fname, s, mp, a, f, __LINE__)
65 #define TRACE_BUSY(fname,s,ag,agb,l,sl,tp)      \
66         xfs_alloc_trace_busy(fname, s, mp, ag, agb, l, sl, tp, XFS_ALLOC_KTRACE_BUSY, __LINE__)
67 #define TRACE_UNBUSY(fname,s,ag,sl,tp)  \
68         xfs_alloc_trace_busy(fname, s, mp, ag, -1, -1, sl, tp, XFS_ALLOC_KTRACE_UNBUSY, __LINE__)
69 #define TRACE_BUSYSEARCH(fname,s,ag,agb,l,sl,tp)        \
70         xfs_alloc_trace_busy(fname, s, mp, ag, agb, l, sl, tp, XFS_ALLOC_KTRACE_BUSYSEARCH, __LINE__)
71 #else
72 #define TRACE_ALLOC(s,a)
73 #define TRACE_FREE(s,a,b,x,f)
74 #define TRACE_MODAGF(s,a,f)
75 #define TRACE_BUSY(s,a,ag,agb,l,sl,tp)
76 #define TRACE_UNBUSY(fname,s,ag,sl,tp)
77 #define TRACE_BUSYSEARCH(fname,s,ag,agb,l,sl,tp)
78 #endif  /* XFS_ALLOC_TRACE */
79
80 /*
81  * Prototypes for per-ag allocation routines
82  */
83
84 STATIC int xfs_alloc_ag_vextent_exact(xfs_alloc_arg_t *);
85 STATIC int xfs_alloc_ag_vextent_near(xfs_alloc_arg_t *);
86 STATIC int xfs_alloc_ag_vextent_size(xfs_alloc_arg_t *);
87 STATIC int xfs_alloc_ag_vextent_small(xfs_alloc_arg_t *,
88         xfs_btree_cur_t *, xfs_agblock_t *, xfs_extlen_t *, int *);
89
90 /*
91  * Internal functions.
92  */
93
94 /*
95  * Compute aligned version of the found extent.
96  * Takes alignment and min length into account.
97  */
98 STATIC int                              /* success (>= minlen) */
99 xfs_alloc_compute_aligned(
100         xfs_agblock_t   foundbno,       /* starting block in found extent */
101         xfs_extlen_t    foundlen,       /* length in found extent */
102         xfs_extlen_t    alignment,      /* alignment for allocation */
103         xfs_extlen_t    minlen,         /* minimum length for allocation */
104         xfs_agblock_t   *resbno,        /* result block number */
105         xfs_extlen_t    *reslen)        /* result length */
106 {
107         xfs_agblock_t   bno;
108         xfs_extlen_t    diff;
109         xfs_extlen_t    len;
110
111         if (alignment > 1 && foundlen >= minlen) {
112                 bno = roundup(foundbno, alignment);
113                 diff = bno - foundbno;
114                 len = diff >= foundlen ? 0 : foundlen - diff;
115         } else {
116                 bno = foundbno;
117                 len = foundlen;
118         }
119         *resbno = bno;
120         *reslen = len;
121         return len >= minlen;
122 }
123
124 /*
125  * Compute best start block and diff for "near" allocations.
126  * freelen >= wantlen already checked by caller.
127  */
128 STATIC xfs_extlen_t                     /* difference value (absolute) */
129 xfs_alloc_compute_diff(
130         xfs_agblock_t   wantbno,        /* target starting block */
131         xfs_extlen_t    wantlen,        /* target length */
132         xfs_extlen_t    alignment,      /* target alignment */
133         xfs_agblock_t   freebno,        /* freespace's starting block */
134         xfs_extlen_t    freelen,        /* freespace's length */
135         xfs_agblock_t   *newbnop)       /* result: best start block from free */
136 {
137         xfs_agblock_t   freeend;        /* end of freespace extent */
138         xfs_agblock_t   newbno1;        /* return block number */
139         xfs_agblock_t   newbno2;        /* other new block number */
140         xfs_extlen_t    newlen1=0;      /* length with newbno1 */
141         xfs_extlen_t    newlen2=0;      /* length with newbno2 */
142         xfs_agblock_t   wantend;        /* end of target extent */
143
144         ASSERT(freelen >= wantlen);
145         freeend = freebno + freelen;
146         wantend = wantbno + wantlen;
147         if (freebno >= wantbno) {
148                 if ((newbno1 = roundup(freebno, alignment)) >= freeend)
149                         newbno1 = NULLAGBLOCK;
150         } else if (freeend >= wantend && alignment > 1) {
151                 newbno1 = roundup(wantbno, alignment);
152                 newbno2 = newbno1 - alignment;
153                 if (newbno1 >= freeend)
154                         newbno1 = NULLAGBLOCK;
155                 else
156                         newlen1 = XFS_EXTLEN_MIN(wantlen, freeend - newbno1);
157                 if (newbno2 < freebno)
158                         newbno2 = NULLAGBLOCK;
159                 else
160                         newlen2 = XFS_EXTLEN_MIN(wantlen, freeend - newbno2);
161                 if (newbno1 != NULLAGBLOCK && newbno2 != NULLAGBLOCK) {
162                         if (newlen1 < newlen2 ||
163                             (newlen1 == newlen2 &&
164                              XFS_ABSDIFF(newbno1, wantbno) >
165                              XFS_ABSDIFF(newbno2, wantbno)))
166                                 newbno1 = newbno2;
167                 } else if (newbno2 != NULLAGBLOCK)
168                         newbno1 = newbno2;
169         } else if (freeend >= wantend) {
170                 newbno1 = wantbno;
171         } else if (alignment > 1) {
172                 newbno1 = roundup(freeend - wantlen, alignment);
173                 if (newbno1 > freeend - wantlen &&
174                     newbno1 - alignment >= freebno)
175                         newbno1 -= alignment;
176                 else if (newbno1 >= freeend)
177                         newbno1 = NULLAGBLOCK;
178         } else
179                 newbno1 = freeend - wantlen;
180         *newbnop = newbno1;
181         return newbno1 == NULLAGBLOCK ? 0 : XFS_ABSDIFF(newbno1, wantbno);
182 }
183
184 /*
185  * Fix up the length, based on mod and prod.
186  * len should be k * prod + mod for some k.
187  * If len is too small it is returned unchanged.
188  * If len hits maxlen it is left alone.
189  */
190 STATIC void
191 xfs_alloc_fix_len(
192         xfs_alloc_arg_t *args)          /* allocation argument structure */
193 {
194         xfs_extlen_t    k;
195         xfs_extlen_t    rlen;
196
197         ASSERT(args->mod < args->prod);
198         rlen = args->len;
199         ASSERT(rlen >= args->minlen);
200         ASSERT(rlen <= args->maxlen);
201         if (args->prod <= 1 || rlen < args->mod || rlen == args->maxlen ||
202             (args->mod == 0 && rlen < args->prod))
203                 return;
204         k = rlen % args->prod;
205         if (k == args->mod)
206                 return;
207         if (k > args->mod) {
208                 if ((int)(rlen = rlen - k - args->mod) < (int)args->minlen)
209                         return;
210         } else {
211                 if ((int)(rlen = rlen - args->prod - (args->mod - k)) <
212                     (int)args->minlen)
213                         return;
214         }
215         ASSERT(rlen >= args->minlen);
216         ASSERT(rlen <= args->maxlen);
217         args->len = rlen;
218 }
219
220 /*
221  * Fix up length if there is too little space left in the a.g.
222  * Return 1 if ok, 0 if too little, should give up.
223  */
224 STATIC int
225 xfs_alloc_fix_minleft(
226         xfs_alloc_arg_t *args)          /* allocation argument structure */
227 {
228         xfs_agf_t       *agf;           /* a.g. freelist header */
229         int             diff;           /* free space difference */
230
231         if (args->minleft == 0)
232                 return 1;
233         agf = XFS_BUF_TO_AGF(args->agbp);
234         diff = INT_GET(agf->agf_freeblks, ARCH_CONVERT)
235                 + INT_GET(agf->agf_flcount, ARCH_CONVERT)
236                 - args->len - args->minleft;
237         if (diff >= 0)
238                 return 1;
239         args->len += diff;              /* shrink the allocated space */
240         if (args->len >= args->minlen)
241                 return 1;
242         args->agbno = NULLAGBLOCK;
243         return 0;
244 }
245
246 /*
247  * Update the two btrees, logically removing from freespace the extent
248  * starting at rbno, rlen blocks.  The extent is contained within the
249  * actual (current) free extent fbno for flen blocks.
250  * Flags are passed in indicating whether the cursors are set to the
251  * relevant records.
252  */
253 STATIC int                              /* error code */
254 xfs_alloc_fixup_trees(
255         xfs_btree_cur_t *cnt_cur,       /* cursor for by-size btree */
256         xfs_btree_cur_t *bno_cur,       /* cursor for by-block btree */
257         xfs_agblock_t   fbno,           /* starting block of free extent */
258         xfs_extlen_t    flen,           /* length of free extent */
259         xfs_agblock_t   rbno,           /* starting block of returned extent */
260         xfs_extlen_t    rlen,           /* length of returned extent */
261         int             flags)          /* flags, XFSA_FIXUP_... */
262 {
263         int             error;          /* error code */
264         int             i;              /* operation results */
265         xfs_agblock_t   nfbno1;         /* first new free startblock */
266         xfs_agblock_t   nfbno2;         /* second new free startblock */
267         xfs_extlen_t    nflen1=0;       /* first new free length */
268         xfs_extlen_t    nflen2=0;       /* second new free length */
269
270         /*
271          * Look up the record in the by-size tree if necessary.
272          */
273         if (flags & XFSA_FIXUP_CNT_OK) {
274 #ifdef DEBUG
275                 if ((error = xfs_alloc_get_rec(cnt_cur, &nfbno1, &nflen1, &i)))
276                         return error;
277                 XFS_WANT_CORRUPTED_RETURN(
278                         i == 1 && nfbno1 == fbno && nflen1 == flen);
279 #endif
280         } else {
281                 if ((error = xfs_alloc_lookup_eq(cnt_cur, fbno, flen, &i)))
282                         return error;
283                 XFS_WANT_CORRUPTED_RETURN(i == 1);
284         }
285         /*
286          * Look up the record in the by-block tree if necessary.
287          */
288         if (flags & XFSA_FIXUP_BNO_OK) {
289 #ifdef DEBUG
290                 if ((error = xfs_alloc_get_rec(bno_cur, &nfbno1, &nflen1, &i)))
291                         return error;
292                 XFS_WANT_CORRUPTED_RETURN(
293                         i == 1 && nfbno1 == fbno && nflen1 == flen);
294 #endif
295         } else {
296                 if ((error = xfs_alloc_lookup_eq(bno_cur, fbno, flen, &i)))
297                         return error;
298                 XFS_WANT_CORRUPTED_RETURN(i == 1);
299         }
300 #ifdef DEBUG
301         {
302                 xfs_alloc_block_t       *bnoblock;
303                 xfs_alloc_block_t       *cntblock;
304
305                 if (bno_cur->bc_nlevels == 1 &&
306                     cnt_cur->bc_nlevels == 1) {
307                         bnoblock = XFS_BUF_TO_ALLOC_BLOCK(bno_cur->bc_bufs[0]);
308                         cntblock = XFS_BUF_TO_ALLOC_BLOCK(cnt_cur->bc_bufs[0]);
309                         XFS_WANT_CORRUPTED_RETURN(
310                                 INT_GET(bnoblock->bb_numrecs, ARCH_CONVERT) == INT_GET(cntblock->bb_numrecs, ARCH_CONVERT));
311                 }
312         }
313 #endif
314         /*
315          * Deal with all four cases: the allocated record is contained
316          * within the freespace record, so we can have new freespace
317          * at either (or both) end, or no freespace remaining.
318          */
319         if (rbno == fbno && rlen == flen)
320                 nfbno1 = nfbno2 = NULLAGBLOCK;
321         else if (rbno == fbno) {
322                 nfbno1 = rbno + rlen;
323                 nflen1 = flen - rlen;
324                 nfbno2 = NULLAGBLOCK;
325         } else if (rbno + rlen == fbno + flen) {
326                 nfbno1 = fbno;
327                 nflen1 = flen - rlen;
328                 nfbno2 = NULLAGBLOCK;
329         } else {
330                 nfbno1 = fbno;
331                 nflen1 = rbno - fbno;
332                 nfbno2 = rbno + rlen;
333                 nflen2 = (fbno + flen) - nfbno2;
334         }
335         /*
336          * Delete the entry from the by-size btree.
337          */
338         if ((error = xfs_alloc_delete(cnt_cur, &i)))
339                 return error;
340         XFS_WANT_CORRUPTED_RETURN(i == 1);
341         /*
342          * Add new by-size btree entry(s).
343          */
344         if (nfbno1 != NULLAGBLOCK) {
345                 if ((error = xfs_alloc_lookup_eq(cnt_cur, nfbno1, nflen1, &i)))
346                         return error;
347                 XFS_WANT_CORRUPTED_RETURN(i == 0);
348                 if ((error = xfs_alloc_insert(cnt_cur, &i)))
349                         return error;
350                 XFS_WANT_CORRUPTED_RETURN(i == 1);
351         }
352         if (nfbno2 != NULLAGBLOCK) {
353                 if ((error = xfs_alloc_lookup_eq(cnt_cur, nfbno2, nflen2, &i)))
354                         return error;
355                 XFS_WANT_CORRUPTED_RETURN(i == 0);
356                 if ((error = xfs_alloc_insert(cnt_cur, &i)))
357                         return error;
358                 XFS_WANT_CORRUPTED_RETURN(i == 1);
359         }
360         /*
361          * Fix up the by-block btree entry(s).
362          */
363         if (nfbno1 == NULLAGBLOCK) {
364                 /*
365                  * No remaining freespace, just delete the by-block tree entry.
366                  */
367                 if ((error = xfs_alloc_delete(bno_cur, &i)))
368                         return error;
369                 XFS_WANT_CORRUPTED_RETURN(i == 1);
370         } else {
371                 /*
372                  * Update the by-block entry to start later|be shorter.
373                  */
374                 if ((error = xfs_alloc_update(bno_cur, nfbno1, nflen1)))
375                         return error;
376         }
377         if (nfbno2 != NULLAGBLOCK) {
378                 /*
379                  * 2 resulting free entries, need to add one.
380                  */
381                 if ((error = xfs_alloc_lookup_eq(bno_cur, nfbno2, nflen2, &i)))
382                         return error;
383                 XFS_WANT_CORRUPTED_RETURN(i == 0);
384                 if ((error = xfs_alloc_insert(bno_cur, &i)))
385                         return error;
386                 XFS_WANT_CORRUPTED_RETURN(i == 1);
387         }
388         return 0;
389 }
390
391 /*
392  * Read in the allocation group free block array.
393  */
394 STATIC int                              /* error */
395 xfs_alloc_read_agfl(
396         xfs_mount_t     *mp,            /* mount point structure */
397         xfs_trans_t     *tp,            /* transaction pointer */
398         xfs_agnumber_t  agno,           /* allocation group number */
399         xfs_buf_t       **bpp)          /* buffer for the ag free block array */
400 {
401         xfs_buf_t       *bp;            /* return value */
402         int             error;
403
404         ASSERT(agno != NULLAGNUMBER);
405         error = xfs_trans_read_buf(
406                         mp, tp, mp->m_ddev_targp,
407                         XFS_AG_DADDR(mp, agno, XFS_AGFL_DADDR(mp)),
408                         XFS_FSS_TO_BB(mp, 1), 0, &bp);
409         if (error)
410                 return error;
411         ASSERT(bp);
412         ASSERT(!XFS_BUF_GETERROR(bp));
413         XFS_BUF_SET_VTYPE_REF(bp, B_FS_AGFL, XFS_AGFL_REF);
414         *bpp = bp;
415         return 0;
416 }
417
418 #if defined(XFS_ALLOC_TRACE)
419 /*
420  * Add an allocation trace entry for an alloc call.
421  */
422 STATIC void
423 xfs_alloc_trace_alloc(
424         char            *name,          /* function tag string */
425         char            *str,           /* additional string */
426         xfs_alloc_arg_t *args,          /* allocation argument structure */
427         int             line)           /* source line number */
428 {
429         ktrace_enter(xfs_alloc_trace_buf,
430                 (void *)(__psint_t)(XFS_ALLOC_KTRACE_ALLOC | (line << 16)),
431                 (void *)name,
432                 (void *)str,
433                 (void *)args->mp,
434                 (void *)(__psunsigned_t)args->agno,
435                 (void *)(__psunsigned_t)args->agbno,
436                 (void *)(__psunsigned_t)args->minlen,
437                 (void *)(__psunsigned_t)args->maxlen,
438                 (void *)(__psunsigned_t)args->mod,
439                 (void *)(__psunsigned_t)args->prod,
440                 (void *)(__psunsigned_t)args->minleft,
441                 (void *)(__psunsigned_t)args->total,
442                 (void *)(__psunsigned_t)args->alignment,
443                 (void *)(__psunsigned_t)args->len,
444                 (void *)((((__psint_t)args->type) << 16) |
445                          (__psint_t)args->otype),
446                 (void *)(__psint_t)((args->wasdel << 3) |
447                                     (args->wasfromfl << 2) |
448                                     (args->isfl << 1) |
449                                     (args->userdata << 0)));
450 }
451
452 /*
453  * Add an allocation trace entry for a free call.
454  */
455 STATIC void
456 xfs_alloc_trace_free(
457         char            *name,          /* function tag string */
458         char            *str,           /* additional string */
459         xfs_mount_t     *mp,            /* file system mount point */
460         xfs_agnumber_t  agno,           /* allocation group number */
461         xfs_agblock_t   agbno,          /* a.g. relative block number */
462         xfs_extlen_t    len,            /* length of extent */
463         int             isfl,           /* set if is freelist allocation/free */
464         int             line)           /* source line number */
465 {
466         ktrace_enter(xfs_alloc_trace_buf,
467                 (void *)(__psint_t)(XFS_ALLOC_KTRACE_FREE | (line << 16)),
468                 (void *)name,
469                 (void *)str,
470                 (void *)mp,
471                 (void *)(__psunsigned_t)agno,
472                 (void *)(__psunsigned_t)agbno,
473                 (void *)(__psunsigned_t)len,
474                 (void *)(__psint_t)isfl,
475                 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL);
476 }
477
478 /*
479  * Add an allocation trace entry for modifying an agf.
480  */
481 STATIC void
482 xfs_alloc_trace_modagf(
483         char            *name,          /* function tag string */
484         char            *str,           /* additional string */
485         xfs_mount_t     *mp,            /* file system mount point */
486         xfs_agf_t       *agf,           /* new agf value */
487         int             flags,          /* logging flags for agf */
488         int             line)           /* source line number */
489 {
490         ktrace_enter(xfs_alloc_trace_buf,
491                 (void *)(__psint_t)(XFS_ALLOC_KTRACE_MODAGF | (line << 16)),
492                 (void *)name,
493                 (void *)str,
494                 (void *)mp,
495                 (void *)(__psint_t)flags,
496                 (void *)(__psunsigned_t)INT_GET(agf->agf_seqno, ARCH_CONVERT),
497                 (void *)(__psunsigned_t)INT_GET(agf->agf_length, ARCH_CONVERT),
498                 (void *)(__psunsigned_t)INT_GET(agf->agf_roots[XFS_BTNUM_BNO],
499                                                 ARCH_CONVERT),
500                 (void *)(__psunsigned_t)INT_GET(agf->agf_roots[XFS_BTNUM_CNT],
501                                                 ARCH_CONVERT),
502                 (void *)(__psunsigned_t)INT_GET(agf->agf_levels[XFS_BTNUM_BNO],
503                                                 ARCH_CONVERT),
504                 (void *)(__psunsigned_t)INT_GET(agf->agf_levels[XFS_BTNUM_CNT],
505                                                 ARCH_CONVERT),
506                 (void *)(__psunsigned_t)INT_GET(agf->agf_flfirst, ARCH_CONVERT),
507                 (void *)(__psunsigned_t)INT_GET(agf->agf_fllast, ARCH_CONVERT),
508                 (void *)(__psunsigned_t)INT_GET(agf->agf_flcount, ARCH_CONVERT),
509                 (void *)(__psunsigned_t)INT_GET(agf->agf_freeblks, ARCH_CONVERT),
510                 (void *)(__psunsigned_t)INT_GET(agf->agf_longest, ARCH_CONVERT));
511 }
512
513 STATIC void
514 xfs_alloc_trace_busy(
515         char            *name,          /* function tag string */
516         char            *str,           /* additional string */
517         xfs_mount_t     *mp,            /* file system mount poing */
518         xfs_agnumber_t  agno,           /* allocation group number */
519         xfs_agblock_t   agbno,          /* a.g. relative block number */
520         xfs_extlen_t    len,            /* length of extent */
521         int             slot,           /* perag Busy slot */
522         xfs_trans_t     *tp,
523         int             trtype,         /* type: add, delete, search */
524         int             line)           /* source line number */
525 {
526         ktrace_enter(xfs_alloc_trace_buf,
527                 (void *)(__psint_t)(trtype | (line << 16)),
528                 (void *)name,
529                 (void *)str,
530                 (void *)mp,
531                 (void *)(__psunsigned_t)agno,
532                 (void *)(__psunsigned_t)agbno,
533                 (void *)(__psunsigned_t)len,
534                 (void *)(__psint_t)slot,
535                 (void *)tp,
536                 NULL, NULL, NULL, NULL, NULL, NULL, NULL);
537 }
538 #endif  /* XFS_ALLOC_TRACE */
539
540 /*
541  * Allocation group level functions.
542  */
543
544 /*
545  * Allocate a variable extent in the allocation group agno.
546  * Type and bno are used to determine where in the allocation group the
547  * extent will start.
548  * Extent's length (returned in *len) will be between minlen and maxlen,
549  * and of the form k * prod + mod unless there's nothing that large.
550  * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
551  */
552 STATIC int                      /* error */
553 xfs_alloc_ag_vextent(
554         xfs_alloc_arg_t *args)  /* argument structure for allocation */
555 {
556         int             error=0;
557 #ifdef XFS_ALLOC_TRACE
558         static char     fname[] = "xfs_alloc_ag_vextent";
559 #endif
560
561         ASSERT(args->minlen > 0);
562         ASSERT(args->maxlen > 0);
563         ASSERT(args->minlen <= args->maxlen);
564         ASSERT(args->mod < args->prod);
565         ASSERT(args->alignment > 0);
566         /*
567          * Branch to correct routine based on the type.
568          */
569         args->wasfromfl = 0;
570         switch (args->type) {
571         case XFS_ALLOCTYPE_THIS_AG:
572                 error = xfs_alloc_ag_vextent_size(args);
573                 break;
574         case XFS_ALLOCTYPE_NEAR_BNO:
575                 error = xfs_alloc_ag_vextent_near(args);
576                 break;
577         case XFS_ALLOCTYPE_THIS_BNO:
578                 error = xfs_alloc_ag_vextent_exact(args);
579                 break;
580         default:
581                 ASSERT(0);
582                 /* NOTREACHED */
583         }
584         if (error)
585                 return error;
586         /*
587          * If the allocation worked, need to change the agf structure
588          * (and log it), and the superblock.
589          */
590         if (args->agbno != NULLAGBLOCK) {
591                 xfs_agf_t       *agf;   /* allocation group freelist header */
592 #ifdef XFS_ALLOC_TRACE
593                 xfs_mount_t     *mp = args->mp;
594 #endif
595                 long            slen = (long)args->len;
596
597                 ASSERT(args->len >= args->minlen && args->len <= args->maxlen);
598                 ASSERT(!(args->wasfromfl) || !args->isfl);
599                 ASSERT(args->agbno % args->alignment == 0);
600                 if (!(args->wasfromfl)) {
601
602                         agf = XFS_BUF_TO_AGF(args->agbp);
603                         INT_MOD(agf->agf_freeblks, ARCH_CONVERT, -(args->len));
604                         xfs_trans_agblocks_delta(args->tp,
605                                                  -((long)(args->len)));
606                         args->pag->pagf_freeblks -= args->len;
607                         ASSERT(INT_GET(agf->agf_freeblks, ARCH_CONVERT)
608                                 <= INT_GET(agf->agf_length, ARCH_CONVERT));
609                         TRACE_MODAGF(NULL, agf, XFS_AGF_FREEBLKS);
610                         xfs_alloc_log_agf(args->tp, args->agbp,
611                                                 XFS_AGF_FREEBLKS);
612                         /* search the busylist for these blocks */
613                         xfs_alloc_search_busy(args->tp, args->agno,
614                                         args->agbno, args->len);
615                 }
616                 if (!args->isfl)
617                         xfs_trans_mod_sb(args->tp,
618                                 args->wasdel ? XFS_TRANS_SB_RES_FDBLOCKS :
619                                         XFS_TRANS_SB_FDBLOCKS, -slen);
620                 XFS_STATS_INC(xs_allocx);
621                 XFS_STATS_ADD(xs_allocb, args->len);
622         }
623         return 0;
624 }
625
626 /*
627  * Allocate a variable extent at exactly agno/bno.
628  * Extent's length (returned in *len) will be between minlen and maxlen,
629  * and of the form k * prod + mod unless there's nothing that large.
630  * Return the starting a.g. block (bno), or NULLAGBLOCK if we can't do it.
631  */
632 STATIC int                      /* error */
633 xfs_alloc_ag_vextent_exact(
634         xfs_alloc_arg_t *args)  /* allocation argument structure */
635 {
636         xfs_btree_cur_t *bno_cur;/* by block-number btree cursor */
637         xfs_btree_cur_t *cnt_cur;/* by count btree cursor */
638         xfs_agblock_t   end;    /* end of allocated extent */
639         int             error;
640         xfs_agblock_t   fbno;   /* start block of found extent */
641         xfs_agblock_t   fend;   /* end block of found extent */
642         xfs_extlen_t    flen;   /* length of found extent */
643 #ifdef XFS_ALLOC_TRACE
644         static char     fname[] = "xfs_alloc_ag_vextent_exact";
645 #endif
646         int             i;      /* success/failure of operation */
647         xfs_agblock_t   maxend; /* end of maximal extent */
648         xfs_agblock_t   minend; /* end of minimal extent */
649         xfs_extlen_t    rlen;   /* length of returned extent */
650
651         ASSERT(args->alignment == 1);
652         /*
653          * Allocate/initialize a cursor for the by-number freespace btree.
654          */
655         bno_cur = xfs_btree_init_cursor(args->mp, args->tp, args->agbp,
656                 args->agno, XFS_BTNUM_BNO, NULL, 0);
657         /*
658          * Lookup bno and minlen in the btree (minlen is irrelevant, really).
659          * Look for the closest free block <= bno, it must contain bno
660          * if any free block does.
661          */
662         if ((error = xfs_alloc_lookup_le(bno_cur, args->agbno, args->minlen, &i)))
663                 goto error0;
664         if (!i) {
665                 /*
666                  * Didn't find it, return null.
667                  */
668                 xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
669                 args->agbno = NULLAGBLOCK;
670                 return 0;
671         }
672         /*
673          * Grab the freespace record.
674          */
675         if ((error = xfs_alloc_get_rec(bno_cur, &fbno, &flen, &i)))
676                 goto error0;
677         XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
678         ASSERT(fbno <= args->agbno);
679         minend = args->agbno + args->minlen;
680         maxend = args->agbno + args->maxlen;
681         fend = fbno + flen;
682         /*
683          * Give up if the freespace isn't long enough for the minimum request.
684          */
685         if (fend < minend) {
686                 xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
687                 args->agbno = NULLAGBLOCK;
688                 return 0;
689         }
690         /*
691          * End of extent will be smaller of the freespace end and the
692          * maximal requested end.
693          */
694         end = XFS_AGBLOCK_MIN(fend, maxend);
695         /*
696          * Fix the length according to mod and prod if given.
697          */
698         args->len = end - args->agbno;
699         xfs_alloc_fix_len(args);
700         if (!xfs_alloc_fix_minleft(args)) {
701                 xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
702                 return 0;
703         }
704         rlen = args->len;
705         ASSERT(args->agbno + rlen <= fend);
706         end = args->agbno + rlen;
707         /*
708          * We are allocating agbno for rlen [agbno .. end]
709          * Allocate/initialize a cursor for the by-size btree.
710          */
711         cnt_cur = xfs_btree_init_cursor(args->mp, args->tp, args->agbp,
712                 args->agno, XFS_BTNUM_CNT, NULL, 0);
713         ASSERT(args->agbno + args->len <=
714                 INT_GET(XFS_BUF_TO_AGF(args->agbp)->agf_length,
715                         ARCH_CONVERT));
716         if ((error = xfs_alloc_fixup_trees(cnt_cur, bno_cur, fbno, flen,
717                         args->agbno, args->len, XFSA_FIXUP_BNO_OK))) {
718                 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
719                 goto error0;
720         }
721         xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
722         xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
723         TRACE_ALLOC("normal", args);
724         args->wasfromfl = 0;
725         return 0;
726
727 error0:
728         xfs_btree_del_cursor(bno_cur, XFS_BTREE_ERROR);
729         TRACE_ALLOC("error", args);
730         return error;
731 }
732
733 /*
734  * Allocate a variable extent near bno in the allocation group agno.
735  * Extent's length (returned in len) will be between minlen and maxlen,
736  * and of the form k * prod + mod unless there's nothing that large.
737  * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
738  */
739 STATIC int                              /* error */
740 xfs_alloc_ag_vextent_near(
741         xfs_alloc_arg_t *args)          /* allocation argument structure */
742 {
743         xfs_btree_cur_t *bno_cur_gt;    /* cursor for bno btree, right side */
744         xfs_btree_cur_t *bno_cur_lt;    /* cursor for bno btree, left side */
745         xfs_btree_cur_t *cnt_cur;       /* cursor for count btree */
746 #ifdef XFS_ALLOC_TRACE
747         static char     fname[] = "xfs_alloc_ag_vextent_near";
748 #endif
749         xfs_agblock_t   gtbno;          /* start bno of right side entry */
750         xfs_agblock_t   gtbnoa;         /* aligned ... */
751         xfs_extlen_t    gtdiff;         /* difference to right side entry */
752         xfs_extlen_t    gtlen;          /* length of right side entry */
753         xfs_extlen_t    gtlena;         /* aligned ... */
754         xfs_agblock_t   gtnew;          /* useful start bno of right side */
755         int             error;          /* error code */
756         int             i;              /* result code, temporary */
757         int             j;              /* result code, temporary */
758         xfs_agblock_t   ltbno;          /* start bno of left side entry */
759         xfs_agblock_t   ltbnoa;         /* aligned ... */
760         xfs_extlen_t    ltdiff;         /* difference to left side entry */
761         /*REFERENCED*/
762         xfs_agblock_t   ltend;          /* end bno of left side entry */
763         xfs_extlen_t    ltlen;          /* length of left side entry */
764         xfs_extlen_t    ltlena;         /* aligned ... */
765         xfs_agblock_t   ltnew;          /* useful start bno of left side */
766         xfs_extlen_t    rlen;           /* length of returned extent */
767 #if defined(DEBUG) && defined(__KERNEL__)
768         /*
769          * Randomly don't execute the first algorithm.
770          */
771         int             dofirst;        /* set to do first algorithm */
772
773         dofirst = random() & 1;
774 #endif
775         /*
776          * Get a cursor for the by-size btree.
777          */
778         cnt_cur = xfs_btree_init_cursor(args->mp, args->tp, args->agbp,
779                 args->agno, XFS_BTNUM_CNT, NULL, 0);
780         ltlen = 0;
781         bno_cur_lt = bno_cur_gt = NULL;
782         /*
783          * See if there are any free extents as big as maxlen.
784          */
785         if ((error = xfs_alloc_lookup_ge(cnt_cur, 0, args->maxlen, &i)))
786                 goto error0;
787         /*
788          * If none, then pick up the last entry in the tree unless the
789          * tree is empty.
790          */
791         if (!i) {
792                 if ((error = xfs_alloc_ag_vextent_small(args, cnt_cur, &ltbno,
793                                 &ltlen, &i)))
794                         goto error0;
795                 if (i == 0 || ltlen == 0) {
796                         xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
797                         return 0;
798                 }
799                 ASSERT(i == 1);
800         }
801         args->wasfromfl = 0;
802         /*
803          * First algorithm.
804          * If the requested extent is large wrt the freespaces available
805          * in this a.g., then the cursor will be pointing to a btree entry
806          * near the right edge of the tree.  If it's in the last btree leaf
807          * block, then we just examine all the entries in that block
808          * that are big enough, and pick the best one.
809          * This is written as a while loop so we can break out of it,
810          * but we never loop back to the top.
811          */
812         while (xfs_btree_islastblock(cnt_cur, 0)) {
813                 xfs_extlen_t    bdiff;
814                 int             besti=0;
815                 xfs_extlen_t    blen=0;
816                 xfs_agblock_t   bnew=0;
817
818 #if defined(DEBUG) && defined(__KERNEL__)
819                 if (!dofirst)
820                         break;
821 #endif
822                 /*
823                  * Start from the entry that lookup found, sequence through
824                  * all larger free blocks.  If we're actually pointing at a
825                  * record smaller than maxlen, go to the start of this block,
826                  * and skip all those smaller than minlen.
827                  */
828                 if (ltlen || args->alignment > 1) {
829                         cnt_cur->bc_ptrs[0] = 1;
830                         do {
831                                 if ((error = xfs_alloc_get_rec(cnt_cur, &ltbno,
832                                                 &ltlen, &i)))
833                                         goto error0;
834                                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
835                                 if (ltlen >= args->minlen)
836                                         break;
837                                 if ((error = xfs_alloc_increment(cnt_cur, 0, &i)))
838                                         goto error0;
839                         } while (i);
840                         ASSERT(ltlen >= args->minlen);
841                         if (!i)
842                                 break;
843                 }
844                 i = cnt_cur->bc_ptrs[0];
845                 for (j = 1, blen = 0, bdiff = 0;
846                      !error && j && (blen < args->maxlen || bdiff > 0);
847                      error = xfs_alloc_increment(cnt_cur, 0, &j)) {
848                         /*
849                          * For each entry, decide if it's better than
850                          * the previous best entry.
851                          */
852                         if ((error = xfs_alloc_get_rec(cnt_cur, &ltbno, &ltlen, &i)))
853                                 goto error0;
854                         XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
855                         if (!xfs_alloc_compute_aligned(ltbno, ltlen,
856                                         args->alignment, args->minlen,
857                                         &ltbnoa, &ltlena))
858                                 continue;
859                         args->len = XFS_EXTLEN_MIN(ltlena, args->maxlen);
860                         xfs_alloc_fix_len(args);
861                         ASSERT(args->len >= args->minlen);
862                         if (args->len < blen)
863                                 continue;
864                         ltdiff = xfs_alloc_compute_diff(args->agbno, args->len,
865                                 args->alignment, ltbno, ltlen, &ltnew);
866                         if (ltnew != NULLAGBLOCK &&
867                             (args->len > blen || ltdiff < bdiff)) {
868                                 bdiff = ltdiff;
869                                 bnew = ltnew;
870                                 blen = args->len;
871                                 besti = cnt_cur->bc_ptrs[0];
872                         }
873                 }
874                 /*
875                  * It didn't work.  We COULD be in a case where
876                  * there's a good record somewhere, so try again.
877                  */
878                 if (blen == 0)
879                         break;
880                 /*
881                  * Point at the best entry, and retrieve it again.
882                  */
883                 cnt_cur->bc_ptrs[0] = besti;
884                 if ((error = xfs_alloc_get_rec(cnt_cur, &ltbno, &ltlen, &i)))
885                         goto error0;
886                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
887                 ltend = ltbno + ltlen;
888                 ASSERT(ltend <= INT_GET(XFS_BUF_TO_AGF(args->agbp)->agf_length,
889                                 ARCH_CONVERT));
890                 args->len = blen;
891                 if (!xfs_alloc_fix_minleft(args)) {
892                         xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
893                         TRACE_ALLOC("nominleft", args);
894                         return 0;
895                 }
896                 blen = args->len;
897                 /*
898                  * We are allocating starting at bnew for blen blocks.
899                  */
900                 args->agbno = bnew;
901                 ASSERT(bnew >= ltbno);
902                 ASSERT(bnew + blen <= ltend);
903                 /*
904                  * Set up a cursor for the by-bno tree.
905                  */
906                 bno_cur_lt = xfs_btree_init_cursor(args->mp, args->tp,
907                         args->agbp, args->agno, XFS_BTNUM_BNO, NULL, 0);
908                 /*
909                  * Fix up the btree entries.
910                  */
911                 if ((error = xfs_alloc_fixup_trees(cnt_cur, bno_cur_lt, ltbno,
912                                 ltlen, bnew, blen, XFSA_FIXUP_CNT_OK)))
913                         goto error0;
914                 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
915                 xfs_btree_del_cursor(bno_cur_lt, XFS_BTREE_NOERROR);
916                 TRACE_ALLOC("first", args);
917                 return 0;
918         }
919         /*
920          * Second algorithm.
921          * Search in the by-bno tree to the left and to the right
922          * simultaneously, until in each case we find a space big enough,
923          * or run into the edge of the tree.  When we run into the edge,
924          * we deallocate that cursor.
925          * If both searches succeed, we compare the two spaces and pick
926          * the better one.
927          * With alignment, it's possible for both to fail; the upper
928          * level algorithm that picks allocation groups for allocations
929          * is not supposed to do this.
930          */
931         /*
932          * Allocate and initialize the cursor for the leftward search.
933          */
934         bno_cur_lt = xfs_btree_init_cursor(args->mp, args->tp, args->agbp,
935                 args->agno, XFS_BTNUM_BNO, NULL, 0);
936         /*
937          * Lookup <= bno to find the leftward search's starting point.
938          */
939         if ((error = xfs_alloc_lookup_le(bno_cur_lt, args->agbno, args->maxlen, &i)))
940                 goto error0;
941         if (!i) {
942                 /*
943                  * Didn't find anything; use this cursor for the rightward
944                  * search.
945                  */
946                 bno_cur_gt = bno_cur_lt;
947                 bno_cur_lt = NULL;
948         }
949         /*
950          * Found something.  Duplicate the cursor for the rightward search.
951          */
952         else if ((error = xfs_btree_dup_cursor(bno_cur_lt, &bno_cur_gt)))
953                 goto error0;
954         /*
955          * Increment the cursor, so we will point at the entry just right
956          * of the leftward entry if any, or to the leftmost entry.
957          */
958         if ((error = xfs_alloc_increment(bno_cur_gt, 0, &i)))
959                 goto error0;
960         if (!i) {
961                 /*
962                  * It failed, there are no rightward entries.
963                  */
964                 xfs_btree_del_cursor(bno_cur_gt, XFS_BTREE_NOERROR);
965                 bno_cur_gt = NULL;
966         }
967         /*
968          * Loop going left with the leftward cursor, right with the
969          * rightward cursor, until either both directions give up or
970          * we find an entry at least as big as minlen.
971          */
972         do {
973                 if (bno_cur_lt) {
974                         if ((error = xfs_alloc_get_rec(bno_cur_lt, &ltbno, &ltlen, &i)))
975                                 goto error0;
976                         XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
977                         if (xfs_alloc_compute_aligned(ltbno, ltlen,
978                                         args->alignment, args->minlen,
979                                         &ltbnoa, &ltlena))
980                                 break;
981                         if ((error = xfs_alloc_decrement(bno_cur_lt, 0, &i)))
982                                 goto error0;
983                         if (!i) {
984                                 xfs_btree_del_cursor(bno_cur_lt,
985                                                      XFS_BTREE_NOERROR);
986                                 bno_cur_lt = NULL;
987                         }
988                 }
989                 if (bno_cur_gt) {
990                         if ((error = xfs_alloc_get_rec(bno_cur_gt, &gtbno, &gtlen, &i)))
991                                 goto error0;
992                         XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
993                         if (xfs_alloc_compute_aligned(gtbno, gtlen,
994                                         args->alignment, args->minlen,
995                                         &gtbnoa, &gtlena))
996                                 break;
997                         if ((error = xfs_alloc_increment(bno_cur_gt, 0, &i)))
998                                 goto error0;
999                         if (!i) {
1000                                 xfs_btree_del_cursor(bno_cur_gt,
1001                                                      XFS_BTREE_NOERROR);
1002                                 bno_cur_gt = NULL;
1003                         }
1004                 }
1005         } while (bno_cur_lt || bno_cur_gt);
1006         /*
1007          * Got both cursors still active, need to find better entry.
1008          */
1009         if (bno_cur_lt && bno_cur_gt) {
1010                 /*
1011                  * Left side is long enough, look for a right side entry.
1012                  */
1013                 if (ltlena >= args->minlen) {
1014                         /*
1015                          * Fix up the length.
1016                          */
1017                         args->len = XFS_EXTLEN_MIN(ltlena, args->maxlen);
1018                         xfs_alloc_fix_len(args);
1019                         rlen = args->len;
1020                         ltdiff = xfs_alloc_compute_diff(args->agbno, rlen,
1021                                 args->alignment, ltbno, ltlen, &ltnew);
1022                         /*
1023                          * Not perfect.
1024                          */
1025                         if (ltdiff) {
1026                                 /*
1027                                  * Look until we find a better one, run out of
1028                                  * space, or run off the end.
1029                                  */
1030                                 while (bno_cur_lt && bno_cur_gt) {
1031                                         if ((error = xfs_alloc_get_rec(
1032                                                         bno_cur_gt, &gtbno,
1033                                                         &gtlen, &i)))
1034                                                 goto error0;
1035                                         XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1036                                         xfs_alloc_compute_aligned(gtbno, gtlen,
1037                                                 args->alignment, args->minlen,
1038                                                 &gtbnoa, &gtlena);
1039                                         /*
1040                                          * The left one is clearly better.
1041                                          */
1042                                         if (gtbnoa >= args->agbno + ltdiff) {
1043                                                 xfs_btree_del_cursor(
1044                                                         bno_cur_gt,
1045                                                         XFS_BTREE_NOERROR);
1046                                                 bno_cur_gt = NULL;
1047                                                 break;
1048                                         }
1049                                         /*
1050                                          * If we reach a big enough entry,
1051                                          * compare the two and pick the best.
1052                                          */
1053                                         if (gtlena >= args->minlen) {
1054                                                 args->len =
1055                                                         XFS_EXTLEN_MIN(gtlena,
1056                                                                 args->maxlen);
1057                                                 xfs_alloc_fix_len(args);
1058                                                 rlen = args->len;
1059                                                 gtdiff = xfs_alloc_compute_diff(
1060                                                         args->agbno, rlen,
1061                                                         args->alignment,
1062                                                         gtbno, gtlen, &gtnew);
1063                                                 /*
1064                                                  * Right side is better.
1065                                                  */
1066                                                 if (gtdiff < ltdiff) {
1067                                                         xfs_btree_del_cursor(
1068                                                                 bno_cur_lt,
1069                                                                 XFS_BTREE_NOERROR);
1070                                                         bno_cur_lt = NULL;
1071                                                 }
1072                                                 /*
1073                                                  * Left side is better.
1074                                                  */
1075                                                 else {
1076                                                         xfs_btree_del_cursor(
1077                                                                 bno_cur_gt,
1078                                                                 XFS_BTREE_NOERROR);
1079                                                         bno_cur_gt = NULL;
1080                                                 }
1081                                                 break;
1082                                         }
1083                                         /*
1084                                          * Fell off the right end.
1085                                          */
1086                                         if ((error = xfs_alloc_increment(
1087                                                         bno_cur_gt, 0, &i)))
1088                                                 goto error0;
1089                                         if (!i) {
1090                                                 xfs_btree_del_cursor(
1091                                                         bno_cur_gt,
1092                                                         XFS_BTREE_NOERROR);
1093                                                 bno_cur_gt = NULL;
1094                                                 break;
1095                                         }
1096                                 }
1097                         }
1098                         /*
1099                          * The left side is perfect, trash the right side.
1100                          */
1101                         else {
1102                                 xfs_btree_del_cursor(bno_cur_gt,
1103                                                      XFS_BTREE_NOERROR);
1104                                 bno_cur_gt = NULL;
1105                         }
1106                 }
1107                 /*
1108                  * It's the right side that was found first, look left.
1109                  */
1110                 else {
1111                         /*
1112                          * Fix up the length.
1113                          */
1114                         args->len = XFS_EXTLEN_MIN(gtlena, args->maxlen);
1115                         xfs_alloc_fix_len(args);
1116                         rlen = args->len;
1117                         gtdiff = xfs_alloc_compute_diff(args->agbno, rlen,
1118                                 args->alignment, gtbno, gtlen, &gtnew);
1119                         /*
1120                          * Right side entry isn't perfect.
1121                          */
1122                         if (gtdiff) {
1123                                 /*
1124                                  * Look until we find a better one, run out of
1125                                  * space, or run off the end.
1126                                  */
1127                                 while (bno_cur_lt && bno_cur_gt) {
1128                                         if ((error = xfs_alloc_get_rec(
1129                                                         bno_cur_lt, &ltbno,
1130                                                         &ltlen, &i)))
1131                                                 goto error0;
1132                                         XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1133                                         xfs_alloc_compute_aligned(ltbno, ltlen,
1134                                                 args->alignment, args->minlen,
1135                                                 &ltbnoa, &ltlena);
1136                                         /*
1137                                          * The right one is clearly better.
1138                                          */
1139                                         if (ltbnoa <= args->agbno - gtdiff) {
1140                                                 xfs_btree_del_cursor(
1141                                                         bno_cur_lt,
1142                                                         XFS_BTREE_NOERROR);
1143                                                 bno_cur_lt = NULL;
1144                                                 break;
1145                                         }
1146                                         /*
1147                                          * If we reach a big enough entry,
1148                                          * compare the two and pick the best.
1149                                          */
1150                                         if (ltlena >= args->minlen) {
1151                                                 args->len = XFS_EXTLEN_MIN(
1152                                                         ltlena, args->maxlen);
1153                                                 xfs_alloc_fix_len(args);
1154                                                 rlen = args->len;
1155                                                 ltdiff = xfs_alloc_compute_diff(
1156                                                         args->agbno, rlen,
1157                                                         args->alignment,
1158                                                         ltbno, ltlen, &ltnew);
1159                                                 /*
1160                                                  * Left side is better.
1161                                                  */
1162                                                 if (ltdiff < gtdiff) {
1163                                                         xfs_btree_del_cursor(
1164                                                                 bno_cur_gt,
1165                                                                 XFS_BTREE_NOERROR);
1166                                                         bno_cur_gt = NULL;
1167                                                 }
1168                                                 /*
1169                                                  * Right side is better.
1170                                                  */
1171                                                 else {
1172                                                         xfs_btree_del_cursor(
1173                                                                 bno_cur_lt,
1174                                                                 XFS_BTREE_NOERROR);
1175                                                         bno_cur_lt = NULL;
1176                                                 }
1177                                                 break;
1178                                         }
1179                                         /*
1180                                          * Fell off the left end.
1181                                          */
1182                                         if ((error = xfs_alloc_decrement(
1183                                                         bno_cur_lt, 0, &i)))
1184                                                 goto error0;
1185                                         if (!i) {
1186                                                 xfs_btree_del_cursor(bno_cur_lt,
1187                                                         XFS_BTREE_NOERROR);
1188                                                 bno_cur_lt = NULL;
1189                                                 break;
1190                                         }
1191                                 }
1192                         }
1193                         /*
1194                          * The right side is perfect, trash the left side.
1195                          */
1196                         else {
1197                                 xfs_btree_del_cursor(bno_cur_lt,
1198                                         XFS_BTREE_NOERROR);
1199                                 bno_cur_lt = NULL;
1200                         }
1201                 }
1202         }
1203         /*
1204          * If we couldn't get anything, give up.
1205          */
1206         if (bno_cur_lt == NULL && bno_cur_gt == NULL) {
1207                 TRACE_ALLOC("neither", args);
1208                 args->agbno = NULLAGBLOCK;
1209                 return 0;
1210         }
1211         /*
1212          * At this point we have selected a freespace entry, either to the
1213          * left or to the right.  If it's on the right, copy all the
1214          * useful variables to the "left" set so we only have one
1215          * copy of this code.
1216          */
1217         if (bno_cur_gt) {
1218                 bno_cur_lt = bno_cur_gt;
1219                 bno_cur_gt = NULL;
1220                 ltbno = gtbno;
1221                 ltbnoa = gtbnoa;
1222                 ltlen = gtlen;
1223                 ltlena = gtlena;
1224                 j = 1;
1225         } else
1226                 j = 0;
1227         /*
1228          * Fix up the length and compute the useful address.
1229          */
1230         ltend = ltbno + ltlen;
1231         args->len = XFS_EXTLEN_MIN(ltlena, args->maxlen);
1232         xfs_alloc_fix_len(args);
1233         if (!xfs_alloc_fix_minleft(args)) {
1234                 TRACE_ALLOC("nominleft", args);
1235                 xfs_btree_del_cursor(bno_cur_lt, XFS_BTREE_NOERROR);
1236                 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1237                 return 0;
1238         }
1239         rlen = args->len;
1240         (void)xfs_alloc_compute_diff(args->agbno, rlen, args->alignment, ltbno,
1241                 ltlen, &ltnew);
1242         ASSERT(ltnew >= ltbno);
1243         ASSERT(ltnew + rlen <= ltend);
1244         ASSERT(ltnew + rlen <= INT_GET(XFS_BUF_TO_AGF(args->agbp)->agf_length,
1245                 ARCH_CONVERT));
1246         args->agbno = ltnew;
1247         if ((error = xfs_alloc_fixup_trees(cnt_cur, bno_cur_lt, ltbno, ltlen,
1248                         ltnew, rlen, XFSA_FIXUP_BNO_OK)))
1249                 goto error0;
1250         TRACE_ALLOC(j ? "gt" : "lt", args);
1251         xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1252         xfs_btree_del_cursor(bno_cur_lt, XFS_BTREE_NOERROR);
1253         return 0;
1254
1255  error0:
1256         TRACE_ALLOC("error", args);
1257         if (cnt_cur != NULL)
1258                 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
1259         if (bno_cur_lt != NULL)
1260                 xfs_btree_del_cursor(bno_cur_lt, XFS_BTREE_ERROR);
1261         if (bno_cur_gt != NULL)
1262                 xfs_btree_del_cursor(bno_cur_gt, XFS_BTREE_ERROR);
1263         return error;
1264 }
1265
1266 /*
1267  * Allocate a variable extent anywhere in the allocation group agno.
1268  * Extent's length (returned in len) will be between minlen and maxlen,
1269  * and of the form k * prod + mod unless there's nothing that large.
1270  * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
1271  */
1272 STATIC int                              /* error */
1273 xfs_alloc_ag_vextent_size(
1274         xfs_alloc_arg_t *args)          /* allocation argument structure */
1275 {
1276         xfs_btree_cur_t *bno_cur;       /* cursor for bno btree */
1277         xfs_btree_cur_t *cnt_cur;       /* cursor for cnt btree */
1278         int             error;          /* error result */
1279         xfs_agblock_t   fbno;           /* start of found freespace */
1280         xfs_extlen_t    flen;           /* length of found freespace */
1281 #ifdef XFS_ALLOC_TRACE
1282         static char     fname[] = "xfs_alloc_ag_vextent_size";
1283 #endif
1284         int             i;              /* temp status variable */
1285         xfs_agblock_t   rbno;           /* returned block number */
1286         xfs_extlen_t    rlen;           /* length of returned extent */
1287
1288         /*
1289          * Allocate and initialize a cursor for the by-size btree.
1290          */
1291         cnt_cur = xfs_btree_init_cursor(args->mp, args->tp, args->agbp,
1292                 args->agno, XFS_BTNUM_CNT, NULL, 0);
1293         bno_cur = NULL;
1294         /*
1295          * Look for an entry >= maxlen+alignment-1 blocks.
1296          */
1297         if ((error = xfs_alloc_lookup_ge(cnt_cur, 0,
1298                         args->maxlen + args->alignment - 1, &i)))
1299                 goto error0;
1300         /*
1301          * If none, then pick up the last entry in the tree unless the
1302          * tree is empty.
1303          */
1304         if (!i) {
1305                 if ((error = xfs_alloc_ag_vextent_small(args, cnt_cur, &fbno,
1306                                 &flen, &i)))
1307                         goto error0;
1308                 if (i == 0 || flen == 0) {
1309                         xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1310                         TRACE_ALLOC("noentry", args);
1311                         return 0;
1312                 }
1313                 ASSERT(i == 1);
1314         }
1315         /*
1316          * There's a freespace as big as maxlen+alignment-1, get it.
1317          */
1318         else {
1319                 if ((error = xfs_alloc_get_rec(cnt_cur, &fbno, &flen, &i)))
1320                         goto error0;
1321                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1322         }
1323         /*
1324          * In the first case above, we got the last entry in the
1325          * by-size btree.  Now we check to see if the space hits maxlen
1326          * once aligned; if not, we search left for something better.
1327          * This can't happen in the second case above.
1328          */
1329         xfs_alloc_compute_aligned(fbno, flen, args->alignment, args->minlen,
1330                 &rbno, &rlen);
1331         rlen = XFS_EXTLEN_MIN(args->maxlen, rlen);
1332         XFS_WANT_CORRUPTED_GOTO(rlen == 0 ||
1333                         (rlen <= flen && rbno + rlen <= fbno + flen), error0);
1334         if (rlen < args->maxlen) {
1335                 xfs_agblock_t   bestfbno;
1336                 xfs_extlen_t    bestflen;
1337                 xfs_agblock_t   bestrbno;
1338                 xfs_extlen_t    bestrlen;
1339
1340                 bestrlen = rlen;
1341                 bestrbno = rbno;
1342                 bestflen = flen;
1343                 bestfbno = fbno;
1344                 for (;;) {
1345                         if ((error = xfs_alloc_decrement(cnt_cur, 0, &i)))
1346                                 goto error0;
1347                         if (i == 0)
1348                                 break;
1349                         if ((error = xfs_alloc_get_rec(cnt_cur, &fbno, &flen,
1350                                         &i)))
1351                                 goto error0;
1352                         XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1353                         if (flen < bestrlen)
1354                                 break;
1355                         xfs_alloc_compute_aligned(fbno, flen, args->alignment,
1356                                 args->minlen, &rbno, &rlen);
1357                         rlen = XFS_EXTLEN_MIN(args->maxlen, rlen);
1358                         XFS_WANT_CORRUPTED_GOTO(rlen == 0 ||
1359                                 (rlen <= flen && rbno + rlen <= fbno + flen),
1360                                 error0);
1361                         if (rlen > bestrlen) {
1362                                 bestrlen = rlen;
1363                                 bestrbno = rbno;
1364                                 bestflen = flen;
1365                                 bestfbno = fbno;
1366                                 if (rlen == args->maxlen)
1367                                         break;
1368                         }
1369                 }
1370                 if ((error = xfs_alloc_lookup_eq(cnt_cur, bestfbno, bestflen,
1371                                 &i)))
1372                         goto error0;
1373                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1374                 rlen = bestrlen;
1375                 rbno = bestrbno;
1376                 flen = bestflen;
1377                 fbno = bestfbno;
1378         }
1379         args->wasfromfl = 0;
1380         /*
1381          * Fix up the length.
1382          */
1383         args->len = rlen;
1384         xfs_alloc_fix_len(args);
1385         if (rlen < args->minlen || !xfs_alloc_fix_minleft(args)) {
1386                 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1387                 TRACE_ALLOC("nominleft", args);
1388                 args->agbno = NULLAGBLOCK;
1389                 return 0;
1390         }
1391         rlen = args->len;
1392         XFS_WANT_CORRUPTED_GOTO(rlen <= flen, error0);
1393         /*
1394          * Allocate and initialize a cursor for the by-block tree.
1395          */
1396         bno_cur = xfs_btree_init_cursor(args->mp, args->tp, args->agbp,
1397                 args->agno, XFS_BTNUM_BNO, NULL, 0);
1398         if ((error = xfs_alloc_fixup_trees(cnt_cur, bno_cur, fbno, flen,
1399                         rbno, rlen, XFSA_FIXUP_CNT_OK)))
1400                 goto error0;
1401         xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1402         xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
1403         cnt_cur = bno_cur = NULL;
1404         args->len = rlen;
1405         args->agbno = rbno;
1406         XFS_WANT_CORRUPTED_GOTO(
1407                 args->agbno + args->len <=
1408                         INT_GET(XFS_BUF_TO_AGF(args->agbp)->agf_length,
1409                         ARCH_CONVERT),
1410                 error0);
1411         TRACE_ALLOC("normal", args);
1412         return 0;
1413
1414 error0:
1415         TRACE_ALLOC("error", args);
1416         if (cnt_cur)
1417                 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
1418         if (bno_cur)
1419                 xfs_btree_del_cursor(bno_cur, XFS_BTREE_ERROR);
1420         return error;
1421 }
1422
1423 /*
1424  * Deal with the case where only small freespaces remain.
1425  * Either return the contents of the last freespace record,
1426  * or allocate space from the freelist if there is nothing in the tree.
1427  */
1428 STATIC int                      /* error */
1429 xfs_alloc_ag_vextent_small(
1430         xfs_alloc_arg_t *args,  /* allocation argument structure */
1431         xfs_btree_cur_t *ccur,  /* by-size cursor */
1432         xfs_agblock_t   *fbnop, /* result block number */
1433         xfs_extlen_t    *flenp, /* result length */
1434         int             *stat)  /* status: 0-freelist, 1-normal/none */
1435 {
1436         int             error;
1437         xfs_agblock_t   fbno;
1438         xfs_extlen_t    flen;
1439 #ifdef XFS_ALLOC_TRACE
1440         static char     fname[] = "xfs_alloc_ag_vextent_small";
1441 #endif
1442         int             i;
1443
1444         if ((error = xfs_alloc_decrement(ccur, 0, &i)))
1445                 goto error0;
1446         if (i) {
1447                 if ((error = xfs_alloc_get_rec(ccur, &fbno, &flen, &i)))
1448                         goto error0;
1449                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1450         }
1451         /*
1452          * Nothing in the btree, try the freelist.  Make sure
1453          * to respect minleft even when pulling from the
1454          * freelist.
1455          */
1456         else if (args->minlen == 1 && args->alignment == 1 && !args->isfl &&
1457                  (INT_GET(XFS_BUF_TO_AGF(args->agbp)->agf_flcount,
1458                         ARCH_CONVERT) > args->minleft)) {
1459                 if ((error = xfs_alloc_get_freelist(args->tp, args->agbp, &fbno)))
1460                         goto error0;
1461                 if (fbno != NULLAGBLOCK) {
1462                         if (args->userdata) {
1463                                 xfs_buf_t       *bp;
1464
1465                                 bp = xfs_btree_get_bufs(args->mp, args->tp,
1466                                         args->agno, fbno, 0);
1467                                 xfs_trans_binval(args->tp, bp);
1468                         }
1469                         args->len = 1;
1470                         args->agbno = fbno;
1471                         XFS_WANT_CORRUPTED_GOTO(
1472                                 args->agbno + args->len <=
1473                                 INT_GET(XFS_BUF_TO_AGF(args->agbp)->agf_length,
1474                                         ARCH_CONVERT),
1475                                 error0);
1476                         args->wasfromfl = 1;
1477                         TRACE_ALLOC("freelist", args);
1478                         *stat = 0;
1479                         return 0;
1480                 }
1481                 /*
1482                  * Nothing in the freelist.
1483                  */
1484                 else
1485                         flen = 0;
1486         }
1487         /*
1488          * Can't allocate from the freelist for some reason.
1489          */
1490         else
1491                 flen = 0;
1492         /*
1493          * Can't do the allocation, give up.
1494          */
1495         if (flen < args->minlen) {
1496                 args->agbno = NULLAGBLOCK;
1497                 TRACE_ALLOC("notenough", args);
1498                 flen = 0;
1499         }
1500         *fbnop = fbno;
1501         *flenp = flen;
1502         *stat = 1;
1503         TRACE_ALLOC("normal", args);
1504         return 0;
1505
1506 error0:
1507         TRACE_ALLOC("error", args);
1508         return error;
1509 }
1510
1511 /*
1512  * Free the extent starting at agno/bno for length.
1513  */
1514 STATIC int                      /* error */
1515 xfs_free_ag_extent(
1516         xfs_trans_t     *tp,    /* transaction pointer */
1517         xfs_buf_t       *agbp,  /* buffer for a.g. freelist header */
1518         xfs_agnumber_t  agno,   /* allocation group number */
1519         xfs_agblock_t   bno,    /* starting block number */
1520         xfs_extlen_t    len,    /* length of extent */
1521         int             isfl)   /* set if is freelist blocks - no sb acctg */
1522 {
1523         xfs_btree_cur_t *bno_cur;       /* cursor for by-block btree */
1524         xfs_btree_cur_t *cnt_cur;       /* cursor for by-size btree */
1525         int             error;          /* error return value */
1526 #ifdef XFS_ALLOC_TRACE
1527         static char     fname[] = "xfs_free_ag_extent";
1528 #endif
1529         xfs_agblock_t   gtbno;          /* start of right neighbor block */
1530         xfs_extlen_t    gtlen;          /* length of right neighbor block */
1531         int             haveleft;       /* have a left neighbor block */
1532         int             haveright;      /* have a right neighbor block */
1533         int             i;              /* temp, result code */
1534         xfs_agblock_t   ltbno;          /* start of left neighbor block */
1535         xfs_extlen_t    ltlen;          /* length of left neighbor block */
1536         xfs_mount_t     *mp;            /* mount point struct for filesystem */
1537         xfs_agblock_t   nbno;           /* new starting block of freespace */
1538         xfs_extlen_t    nlen;           /* new length of freespace */
1539
1540         mp = tp->t_mountp;
1541         /*
1542          * Allocate and initialize a cursor for the by-block btree.
1543          */
1544         bno_cur = xfs_btree_init_cursor(mp, tp, agbp, agno, XFS_BTNUM_BNO, NULL,
1545                 0);
1546         cnt_cur = NULL;
1547         /*
1548          * Look for a neighboring block on the left (lower block numbers)
1549          * that is contiguous with this space.
1550          */
1551         if ((error = xfs_alloc_lookup_le(bno_cur, bno, len, &haveleft)))
1552                 goto error0;
1553         if (haveleft) {
1554                 /*
1555                  * There is a block to our left.
1556                  */
1557                 if ((error = xfs_alloc_get_rec(bno_cur, &ltbno, &ltlen, &i)))
1558                         goto error0;
1559                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1560                 /*
1561                  * It's not contiguous, though.
1562                  */
1563                 if (ltbno + ltlen < bno)
1564                         haveleft = 0;
1565                 else {
1566                         /*
1567                          * If this failure happens the request to free this
1568                          * space was invalid, it's (partly) already free.
1569                          * Very bad.
1570                          */
1571                         XFS_WANT_CORRUPTED_GOTO(ltbno + ltlen <= bno, error0);
1572                 }
1573         }
1574         /*
1575          * Look for a neighboring block on the right (higher block numbers)
1576          * that is contiguous with this space.
1577          */
1578         if ((error = xfs_alloc_increment(bno_cur, 0, &haveright)))
1579                 goto error0;
1580         if (haveright) {
1581                 /*
1582                  * There is a block to our right.
1583                  */
1584                 if ((error = xfs_alloc_get_rec(bno_cur, &gtbno, &gtlen, &i)))
1585                         goto error0;
1586                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1587                 /*
1588                  * It's not contiguous, though.
1589                  */
1590                 if (bno + len < gtbno)
1591                         haveright = 0;
1592                 else {
1593                         /*
1594                          * If this failure happens the request to free this
1595                          * space was invalid, it's (partly) already free.
1596                          * Very bad.
1597                          */
1598                         XFS_WANT_CORRUPTED_GOTO(gtbno >= bno + len, error0);
1599                 }
1600         }
1601         /*
1602          * Now allocate and initialize a cursor for the by-size tree.
1603          */
1604         cnt_cur = xfs_btree_init_cursor(mp, tp, agbp, agno, XFS_BTNUM_CNT, NULL,
1605                 0);
1606         /*
1607          * Have both left and right contiguous neighbors.
1608          * Merge all three into a single free block.
1609          */
1610         if (haveleft && haveright) {
1611                 /*
1612                  * Delete the old by-size entry on the left.
1613                  */
1614                 if ((error = xfs_alloc_lookup_eq(cnt_cur, ltbno, ltlen, &i)))
1615                         goto error0;
1616                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1617                 if ((error = xfs_alloc_delete(cnt_cur, &i)))
1618                         goto error0;
1619                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1620                 /*
1621                  * Delete the old by-size entry on the right.
1622                  */
1623                 if ((error = xfs_alloc_lookup_eq(cnt_cur, gtbno, gtlen, &i)))
1624                         goto error0;
1625                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1626                 if ((error = xfs_alloc_delete(cnt_cur, &i)))
1627                         goto error0;
1628                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1629                 /*
1630                  * Delete the old by-block entry for the right block.
1631                  */
1632                 if ((error = xfs_alloc_delete(bno_cur, &i)))
1633                         goto error0;
1634                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1635                 /*
1636                  * Move the by-block cursor back to the left neighbor.
1637                  */
1638                 if ((error = xfs_alloc_decrement(bno_cur, 0, &i)))
1639                         goto error0;
1640                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1641 #ifdef DEBUG
1642                 /*
1643                  * Check that this is the right record: delete didn't
1644                  * mangle the cursor.
1645                  */
1646                 {
1647                         xfs_agblock_t   xxbno;
1648                         xfs_extlen_t    xxlen;
1649
1650                         if ((error = xfs_alloc_get_rec(bno_cur, &xxbno, &xxlen,
1651                                         &i)))
1652                                 goto error0;
1653                         XFS_WANT_CORRUPTED_GOTO(
1654                                 i == 1 && xxbno == ltbno && xxlen == ltlen,
1655                                 error0);
1656                 }
1657 #endif
1658                 /*
1659                  * Update remaining by-block entry to the new, joined block.
1660                  */
1661                 nbno = ltbno;
1662                 nlen = len + ltlen + gtlen;
1663                 if ((error = xfs_alloc_update(bno_cur, nbno, nlen)))
1664                         goto error0;
1665         }
1666         /*
1667          * Have only a left contiguous neighbor.
1668          * Merge it together with the new freespace.
1669          */
1670         else if (haveleft) {
1671                 /*
1672                  * Delete the old by-size entry on the left.
1673                  */
1674                 if ((error = xfs_alloc_lookup_eq(cnt_cur, ltbno, ltlen, &i)))
1675                         goto error0;
1676                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1677                 if ((error = xfs_alloc_delete(cnt_cur, &i)))
1678                         goto error0;
1679                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1680                 /*
1681                  * Back up the by-block cursor to the left neighbor, and
1682                  * update its length.
1683                  */
1684                 if ((error = xfs_alloc_decrement(bno_cur, 0, &i)))
1685                         goto error0;
1686                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1687                 nbno = ltbno;
1688                 nlen = len + ltlen;
1689                 if ((error = xfs_alloc_update(bno_cur, nbno, nlen)))
1690                         goto error0;
1691         }
1692         /*
1693          * Have only a right contiguous neighbor.
1694          * Merge it together with the new freespace.
1695          */
1696         else if (haveright) {
1697                 /*
1698                  * Delete the old by-size entry on the right.
1699                  */
1700                 if ((error = xfs_alloc_lookup_eq(cnt_cur, gtbno, gtlen, &i)))
1701                         goto error0;
1702                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1703                 if ((error = xfs_alloc_delete(cnt_cur, &i)))
1704                         goto error0;
1705                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1706                 /*
1707                  * Update the starting block and length of the right
1708                  * neighbor in the by-block tree.
1709                  */
1710                 nbno = bno;
1711                 nlen = len + gtlen;
1712                 if ((error = xfs_alloc_update(bno_cur, nbno, nlen)))
1713                         goto error0;
1714         }
1715         /*
1716          * No contiguous neighbors.
1717          * Insert the new freespace into the by-block tree.
1718          */
1719         else {
1720                 nbno = bno;
1721                 nlen = len;
1722                 if ((error = xfs_alloc_insert(bno_cur, &i)))
1723                         goto error0;
1724                 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1725         }
1726         xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
1727         bno_cur = NULL;
1728         /*
1729          * In all cases we need to insert the new freespace in the by-size tree.
1730          */
1731         if ((error = xfs_alloc_lookup_eq(cnt_cur, nbno, nlen, &i)))
1732                 goto error0;
1733         XFS_WANT_CORRUPTED_GOTO(i == 0, error0);
1734         if ((error = xfs_alloc_insert(cnt_cur, &i)))
1735                 goto error0;
1736         XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1737         xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1738         cnt_cur = NULL;
1739         /*
1740          * Update the freespace totals in the ag and superblock.
1741          */
1742         {
1743                 xfs_agf_t       *agf;
1744                 xfs_perag_t     *pag;           /* per allocation group data */
1745
1746                 agf = XFS_BUF_TO_AGF(agbp);
1747                 pag = &mp->m_perag[agno];
1748                 INT_MOD(agf->agf_freeblks, ARCH_CONVERT, len);
1749                 xfs_trans_agblocks_delta(tp, len);
1750                 pag->pagf_freeblks += len;
1751                 XFS_WANT_CORRUPTED_GOTO(
1752                         INT_GET(agf->agf_freeblks, ARCH_CONVERT)
1753                                 <= INT_GET(agf->agf_length, ARCH_CONVERT),
1754                         error0);
1755                 TRACE_MODAGF(NULL, agf, XFS_AGF_FREEBLKS);
1756                 xfs_alloc_log_agf(tp, agbp, XFS_AGF_FREEBLKS);
1757                 if (!isfl)
1758                         xfs_trans_mod_sb(tp, XFS_TRANS_SB_FDBLOCKS, (long)len);
1759                 XFS_STATS_INC(xs_freex);
1760                 XFS_STATS_ADD(xs_freeb, len);
1761         }
1762         TRACE_FREE(haveleft ?
1763                         (haveright ? "both" : "left") :
1764                         (haveright ? "right" : "none"),
1765                 agno, bno, len, isfl);
1766
1767         /*
1768          * Since blocks move to the free list without the coordination
1769          * used in xfs_bmap_finish, we can't allow block to be available
1770          * for reallocation and non-transaction writing (user data)
1771          * until we know that the transaction that moved it to the free
1772          * list is permanently on disk.  We track the blocks by declaring
1773          * these blocks as "busy"; the busy list is maintained on a per-ag
1774          * basis and each transaction records which entries should be removed
1775          * when the iclog commits to disk.  If a busy block is allocated,
1776          * the iclog is pushed up to the LSN that freed the block.
1777          */
1778         xfs_alloc_mark_busy(tp, agno, bno, len);
1779         return 0;
1780
1781  error0:
1782         TRACE_FREE("error", agno, bno, len, isfl);
1783         if (bno_cur)
1784                 xfs_btree_del_cursor(bno_cur, XFS_BTREE_ERROR);
1785         if (cnt_cur)
1786                 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
1787         return error;
1788 }
1789
1790 /*
1791  * Visible (exported) allocation/free functions.
1792  * Some of these are used just by xfs_alloc_btree.c and this file.
1793  */
1794
1795 /*
1796  * Compute and fill in value of m_ag_maxlevels.
1797  */
1798 void
1799 xfs_alloc_compute_maxlevels(
1800         xfs_mount_t     *mp)    /* file system mount structure */
1801 {
1802         int             level;
1803         uint            maxblocks;
1804         uint            maxleafents;
1805         int             minleafrecs;
1806         int             minnoderecs;
1807
1808         maxleafents = (mp->m_sb.sb_agblocks + 1) / 2;
1809         minleafrecs = mp->m_alloc_mnr[0];
1810         minnoderecs = mp->m_alloc_mnr[1];
1811         maxblocks = (maxleafents + minleafrecs - 1) / minleafrecs;
1812         for (level = 1; maxblocks > 1; level++)
1813                 maxblocks = (maxblocks + minnoderecs - 1) / minnoderecs;
1814         mp->m_ag_maxlevels = level;
1815 }
1816
1817 /*
1818  * Decide whether to use this allocation group for this allocation.
1819  * If so, fix up the btree freelist's size.
1820  */
1821 STATIC int                      /* error */
1822 xfs_alloc_fix_freelist(
1823         xfs_alloc_arg_t *args,  /* allocation argument structure */
1824         int             flags)  /* XFS_ALLOC_FLAG_... */
1825 {
1826         xfs_buf_t       *agbp;  /* agf buffer pointer */
1827         xfs_agf_t       *agf;   /* a.g. freespace structure pointer */
1828         xfs_buf_t       *agflbp;/* agfl buffer pointer */
1829         xfs_agblock_t   bno;    /* freelist block */
1830         xfs_extlen_t    delta;  /* new blocks needed in freelist */
1831         int             error;  /* error result code */
1832         xfs_extlen_t    longest;/* longest extent in allocation group */
1833         xfs_mount_t     *mp;    /* file system mount point structure */
1834         xfs_extlen_t    need;   /* total blocks needed in freelist */
1835         xfs_perag_t     *pag;   /* per-ag information structure */
1836         xfs_alloc_arg_t targs;  /* local allocation arguments */
1837         xfs_trans_t     *tp;    /* transaction pointer */
1838
1839         mp = args->mp;
1840
1841         pag = args->pag;
1842         tp = args->tp;
1843         if (!pag->pagf_init) {
1844                 if ((error = xfs_alloc_read_agf(mp, tp, args->agno, flags,
1845                                 &agbp)))
1846                         return error;
1847                 if (!pag->pagf_init) {
1848                         args->agbp = NULL;
1849                         return 0;
1850                 }
1851         } else
1852                 agbp = NULL;
1853
1854         /* If this is a metadata prefered pag and we are user data
1855          * then try somewhere else if we are not being asked to
1856          * try harder at this point
1857          */
1858         if (pag->pagf_metadata && args->userdata && flags) {
1859                 args->agbp = NULL;
1860                 return 0;
1861         }
1862
1863         need = XFS_MIN_FREELIST_PAG(pag, mp);
1864         delta = need > pag->pagf_flcount ? need - pag->pagf_flcount : 0;
1865         /*
1866          * If it looks like there isn't a long enough extent, or enough
1867          * total blocks, reject it.
1868          */
1869         longest = (pag->pagf_longest > delta) ?
1870                 (pag->pagf_longest - delta) :
1871                 (pag->pagf_flcount > 0 || pag->pagf_longest > 0);
1872         if (args->minlen + args->alignment + args->minalignslop - 1 > longest ||
1873             (args->minleft &&
1874              (int)(pag->pagf_freeblks + pag->pagf_flcount -
1875                    need - args->total) <
1876              (int)args->minleft)) {
1877                 if (agbp)
1878                         xfs_trans_brelse(tp, agbp);
1879                 args->agbp = NULL;
1880                 return 0;
1881         }
1882         /*
1883          * Get the a.g. freespace buffer.
1884          * Can fail if we're not blocking on locks, and it's held.
1885          */
1886         if (agbp == NULL) {
1887                 if ((error = xfs_alloc_read_agf(mp, tp, args->agno, flags,
1888                                 &agbp)))
1889                         return error;
1890                 if (agbp == NULL) {
1891                         args->agbp = NULL;
1892                         return 0;
1893                 }
1894         }
1895         /*
1896          * Figure out how many blocks we should have in the freelist.
1897          */
1898         agf = XFS_BUF_TO_AGF(agbp);
1899         need = XFS_MIN_FREELIST(agf, mp);
1900         delta = need > INT_GET(agf->agf_flcount, ARCH_CONVERT) ?
1901                 (need - INT_GET(agf->agf_flcount, ARCH_CONVERT)) : 0;
1902         /*
1903          * If there isn't enough total or single-extent, reject it.
1904          */
1905         longest = INT_GET(agf->agf_longest, ARCH_CONVERT);
1906         longest = (longest > delta) ? (longest - delta) :
1907                 (INT_GET(agf->agf_flcount, ARCH_CONVERT) > 0 || longest > 0);
1908         if (args->minlen + args->alignment + args->minalignslop - 1 > longest ||
1909              (args->minleft &&
1910                 (int)(INT_GET(agf->agf_freeblks, ARCH_CONVERT) +
1911                    INT_GET(agf->agf_flcount, ARCH_CONVERT) - need - args->total) <
1912              (int)args->minleft)) {
1913                 xfs_trans_brelse(tp, agbp);
1914                 args->agbp = NULL;
1915                 return 0;
1916         }
1917         /*
1918          * Make the freelist shorter if it's too long.
1919          */
1920         while (INT_GET(agf->agf_flcount, ARCH_CONVERT) > need) {
1921                 xfs_buf_t       *bp;
1922
1923                 if ((error = xfs_alloc_get_freelist(tp, agbp, &bno)))
1924                         return error;
1925                 if ((error = xfs_free_ag_extent(tp, agbp, args->agno, bno, 1, 1)))
1926                         return error;
1927                 bp = xfs_btree_get_bufs(mp, tp, args->agno, bno, 0);
1928                 xfs_trans_binval(tp, bp);
1929         }
1930         /*
1931          * Initialize the args structure.
1932          */
1933         targs.tp = tp;
1934         targs.mp = mp;
1935         targs.agbp = agbp;
1936         targs.agno = args->agno;
1937         targs.mod = targs.minleft = targs.wasdel = targs.userdata =
1938                 targs.minalignslop = 0;
1939         targs.alignment = targs.minlen = targs.prod = targs.isfl = 1;
1940         targs.type = XFS_ALLOCTYPE_THIS_AG;
1941         targs.pag = pag;
1942         if ((error = xfs_alloc_read_agfl(mp, tp, targs.agno, &agflbp)))
1943                 return error;
1944         /*
1945          * Make the freelist longer if it's too short.
1946          */
1947         while (INT_GET(agf->agf_flcount, ARCH_CONVERT) < need) {
1948                 targs.agbno = 0;
1949                 targs.maxlen = need - INT_GET(agf->agf_flcount, ARCH_CONVERT);
1950                 /*
1951                  * Allocate as many blocks as possible at once.
1952                  */
1953                 if ((error = xfs_alloc_ag_vextent(&targs)))
1954                         return error;
1955                 /*
1956                  * Stop if we run out.  Won't happen if callers are obeying
1957                  * the restrictions correctly.  Can happen for free calls
1958                  * on a completely full ag.
1959                  */
1960                 if (targs.agbno == NULLAGBLOCK)
1961                         break;
1962                 /*
1963                  * Put each allocated block on the list.
1964                  */
1965                 for (bno = targs.agbno; bno < targs.agbno + targs.len; bno++) {
1966                         if ((error = xfs_alloc_put_freelist(tp, agbp, agflbp,
1967                                         bno)))
1968                                 return error;
1969                 }
1970         }
1971         args->agbp = agbp;
1972         return 0;
1973 }
1974
1975 /*
1976  * Get a block from the freelist.
1977  * Returns with the buffer for the block gotten.
1978  */
1979 int                             /* error */
1980 xfs_alloc_get_freelist(
1981         xfs_trans_t     *tp,    /* transaction pointer */
1982         xfs_buf_t       *agbp,  /* buffer containing the agf structure */
1983         xfs_agblock_t   *bnop)  /* block address retrieved from freelist */
1984 {
1985         xfs_agf_t       *agf;   /* a.g. freespace structure */
1986         xfs_agfl_t      *agfl;  /* a.g. freelist structure */
1987         xfs_buf_t       *agflbp;/* buffer for a.g. freelist structure */
1988         xfs_agblock_t   bno;    /* block number returned */
1989         int             error;
1990 #ifdef XFS_ALLOC_TRACE
1991         static char     fname[] = "xfs_alloc_get_freelist";
1992 #endif
1993         xfs_mount_t     *mp;    /* mount structure */
1994         xfs_perag_t     *pag;   /* per allocation group data */
1995
1996         agf = XFS_BUF_TO_AGF(agbp);
1997         /*
1998          * Freelist is empty, give up.
1999          */
2000         if (!agf->agf_flcount) {
2001                 *bnop = NULLAGBLOCK;
2002                 return 0;
2003         }
2004         /*
2005          * Read the array of free blocks.
2006          */
2007         mp = tp->t_mountp;
2008         if ((error = xfs_alloc_read_agfl(mp, tp,
2009                         INT_GET(agf->agf_seqno, ARCH_CONVERT), &agflbp)))
2010                 return error;
2011         agfl = XFS_BUF_TO_AGFL(agflbp);
2012         /*
2013          * Get the block number and update the data structures.
2014          */
2015         bno = INT_GET(agfl->agfl_bno[INT_GET(agf->agf_flfirst, ARCH_CONVERT)], ARCH_CONVERT);
2016         INT_MOD(agf->agf_flfirst, ARCH_CONVERT, 1);
2017         xfs_trans_brelse(tp, agflbp);
2018         if (INT_GET(agf->agf_flfirst, ARCH_CONVERT) == XFS_AGFL_SIZE(mp))
2019                 agf->agf_flfirst = 0;
2020         pag = &mp->m_perag[INT_GET(agf->agf_seqno, ARCH_CONVERT)];
2021         INT_MOD(agf->agf_flcount, ARCH_CONVERT, -1);
2022         xfs_trans_agflist_delta(tp, -1);
2023         pag->pagf_flcount--;
2024         TRACE_MODAGF(NULL, agf, XFS_AGF_FLFIRST | XFS_AGF_FLCOUNT);
2025         xfs_alloc_log_agf(tp, agbp, XFS_AGF_FLFIRST | XFS_AGF_FLCOUNT);
2026         *bnop = bno;
2027
2028         /*
2029          * As blocks are freed, they are added to the per-ag busy list
2030          * and remain there until the freeing transaction is committed to
2031          * disk.  Now that we have allocated blocks, this list must be
2032          * searched to see if a block is being reused.  If one is, then
2033          * the freeing transaction must be pushed to disk NOW by forcing
2034          * to disk all iclogs up that transaction's LSN.
2035          */
2036         xfs_alloc_search_busy(tp, INT_GET(agf->agf_seqno, ARCH_CONVERT), bno, 1);
2037         return 0;
2038 }
2039
2040 /*
2041  * Log the given fields from the agf structure.
2042  */
2043 void
2044 xfs_alloc_log_agf(
2045         xfs_trans_t     *tp,    /* transaction pointer */
2046         xfs_buf_t       *bp,    /* buffer for a.g. freelist header */
2047         int             fields) /* mask of fields to be logged (XFS_AGF_...) */
2048 {
2049         int     first;          /* first byte offset */
2050         int     last;           /* last byte offset */
2051         static const short      offsets[] = {
2052                 offsetof(xfs_agf_t, agf_magicnum),
2053                 offsetof(xfs_agf_t, agf_versionnum),
2054                 offsetof(xfs_agf_t, agf_seqno),
2055                 offsetof(xfs_agf_t, agf_length),
2056                 offsetof(xfs_agf_t, agf_roots[0]),
2057                 offsetof(xfs_agf_t, agf_levels[0]),
2058                 offsetof(xfs_agf_t, agf_flfirst),
2059                 offsetof(xfs_agf_t, agf_fllast),
2060                 offsetof(xfs_agf_t, agf_flcount),
2061                 offsetof(xfs_agf_t, agf_freeblks),
2062                 offsetof(xfs_agf_t, agf_longest),
2063                 sizeof(xfs_agf_t)
2064         };
2065
2066         xfs_btree_offsets(fields, offsets, XFS_AGF_NUM_BITS, &first, &last);
2067         xfs_trans_log_buf(tp, bp, (uint)first, (uint)last);
2068 }
2069
2070 /*
2071  * Interface for inode allocation to force the pag data to be initialized.
2072  */
2073 int                                     /* error */
2074 xfs_alloc_pagf_init(
2075         xfs_mount_t             *mp,    /* file system mount structure */
2076         xfs_trans_t             *tp,    /* transaction pointer */
2077         xfs_agnumber_t          agno,   /* allocation group number */
2078         int                     flags)  /* XFS_ALLOC_FLAGS_... */
2079 {
2080         xfs_buf_t               *bp;
2081         int                     error;
2082
2083         if ((error = xfs_alloc_read_agf(mp, tp, agno, flags, &bp)))
2084                 return error;
2085         if (bp)
2086                 xfs_trans_brelse(tp, bp);
2087         return 0;
2088 }
2089
2090 /*
2091  * Put the block on the freelist for the allocation group.
2092  */
2093 int                                     /* error */
2094 xfs_alloc_put_freelist(
2095         xfs_trans_t             *tp,    /* transaction pointer */
2096         xfs_buf_t               *agbp,  /* buffer for a.g. freelist header */
2097         xfs_buf_t               *agflbp,/* buffer for a.g. free block array */
2098         xfs_agblock_t           bno)    /* block being freed */
2099 {
2100         xfs_agf_t               *agf;   /* a.g. freespace structure */
2101         xfs_agfl_t              *agfl;  /* a.g. free block array */
2102         xfs_agblock_t           *blockp;/* pointer to array entry */
2103         int                     error;
2104 #ifdef XFS_ALLOC_TRACE
2105         static char             fname[] = "xfs_alloc_put_freelist";
2106 #endif
2107         xfs_mount_t             *mp;    /* mount structure */
2108         xfs_perag_t             *pag;   /* per allocation group data */
2109
2110         agf = XFS_BUF_TO_AGF(agbp);
2111         mp = tp->t_mountp;
2112
2113         if (!agflbp && (error = xfs_alloc_read_agfl(mp, tp,
2114                         INT_GET(agf->agf_seqno, ARCH_CONVERT), &agflbp)))
2115                 return error;
2116         agfl = XFS_BUF_TO_AGFL(agflbp);
2117         INT_MOD(agf->agf_fllast, ARCH_CONVERT, 1);
2118         if (INT_GET(agf->agf_fllast, ARCH_CONVERT) == XFS_AGFL_SIZE(mp))
2119                 agf->agf_fllast = 0;
2120         pag = &mp->m_perag[INT_GET(agf->agf_seqno, ARCH_CONVERT)];
2121         INT_MOD(agf->agf_flcount, ARCH_CONVERT, 1);
2122         xfs_trans_agflist_delta(tp, 1);
2123         pag->pagf_flcount++;
2124         ASSERT(INT_GET(agf->agf_flcount, ARCH_CONVERT) <= XFS_AGFL_SIZE(mp));
2125         blockp = &agfl->agfl_bno[INT_GET(agf->agf_fllast, ARCH_CONVERT)];
2126         INT_SET(*blockp, ARCH_CONVERT, bno);
2127         TRACE_MODAGF(NULL, agf, XFS_AGF_FLLAST | XFS_AGF_FLCOUNT);
2128         xfs_alloc_log_agf(tp, agbp, XFS_AGF_FLLAST | XFS_AGF_FLCOUNT);
2129         xfs_trans_log_buf(tp, agflbp,
2130                 (int)((xfs_caddr_t)blockp - (xfs_caddr_t)agfl),
2131                 (int)((xfs_caddr_t)blockp - (xfs_caddr_t)agfl +
2132                         sizeof(xfs_agblock_t) - 1));
2133         return 0;
2134 }
2135
2136 /*
2137  * Read in the allocation group header (free/alloc section).
2138  */
2139 int                                     /* error */
2140 xfs_alloc_read_agf(
2141         xfs_mount_t     *mp,            /* mount point structure */
2142         xfs_trans_t     *tp,            /* transaction pointer */
2143         xfs_agnumber_t  agno,           /* allocation group number */
2144         int             flags,          /* XFS_ALLOC_FLAG_... */
2145         xfs_buf_t       **bpp)          /* buffer for the ag freelist header */
2146 {
2147         xfs_agf_t       *agf;           /* ag freelist header */
2148         int             agf_ok;         /* set if agf is consistent */
2149         xfs_buf_t       *bp;            /* return value */
2150         xfs_perag_t     *pag;           /* per allocation group data */
2151         int             error;
2152
2153         ASSERT(agno != NULLAGNUMBER);
2154         error = xfs_trans_read_buf(
2155                         mp, tp, mp->m_ddev_targp,
2156                         XFS_AG_DADDR(mp, agno, XFS_AGF_DADDR(mp)),
2157                         XFS_FSS_TO_BB(mp, 1),
2158                         (flags & XFS_ALLOC_FLAG_TRYLOCK) ? XFS_BUF_TRYLOCK : 0U,
2159                         &bp);
2160         if (error)
2161                 return error;
2162         ASSERT(!bp || !XFS_BUF_GETERROR(bp));
2163         if (!bp) {
2164                 *bpp = NULL;
2165                 return 0;
2166         }
2167         /*
2168          * Validate the magic number of the agf block.
2169          */
2170         agf = XFS_BUF_TO_AGF(bp);
2171         agf_ok =
2172                 INT_GET(agf->agf_magicnum, ARCH_CONVERT) == XFS_AGF_MAGIC &&
2173                 XFS_AGF_GOOD_VERSION(
2174                         INT_GET(agf->agf_versionnum, ARCH_CONVERT)) &&
2175                 INT_GET(agf->agf_freeblks, ARCH_CONVERT) <=
2176                                 INT_GET(agf->agf_length, ARCH_CONVERT) &&
2177                 INT_GET(agf->agf_flfirst, ARCH_CONVERT) < XFS_AGFL_SIZE(mp) &&
2178                 INT_GET(agf->agf_fllast,  ARCH_CONVERT) < XFS_AGFL_SIZE(mp) &&
2179                 INT_GET(agf->agf_flcount, ARCH_CONVERT) <= XFS_AGFL_SIZE(mp);
2180         if (unlikely(XFS_TEST_ERROR(!agf_ok, mp, XFS_ERRTAG_ALLOC_READ_AGF,
2181                         XFS_RANDOM_ALLOC_READ_AGF))) {
2182                 XFS_CORRUPTION_ERROR("xfs_alloc_read_agf",
2183                                      XFS_ERRLEVEL_LOW, mp, agf);
2184                 xfs_trans_brelse(tp, bp);
2185                 return XFS_ERROR(EFSCORRUPTED);
2186         }
2187         pag = &mp->m_perag[agno];
2188         if (!pag->pagf_init) {
2189                 pag->pagf_freeblks = INT_GET(agf->agf_freeblks, ARCH_CONVERT);
2190                 pag->pagf_flcount = INT_GET(agf->agf_flcount, ARCH_CONVERT);
2191                 pag->pagf_longest = INT_GET(agf->agf_longest, ARCH_CONVERT);
2192                 pag->pagf_levels[XFS_BTNUM_BNOi] =
2193                         INT_GET(agf->agf_levels[XFS_BTNUM_BNOi], ARCH_CONVERT);
2194                 pag->pagf_levels[XFS_BTNUM_CNTi] =
2195                         INT_GET(agf->agf_levels[XFS_BTNUM_CNTi], ARCH_CONVERT);
2196                 spinlock_init(&pag->pagb_lock, "xfspagb");
2197                 pag->pagb_list = kmem_zalloc(XFS_PAGB_NUM_SLOTS *
2198                                         sizeof(xfs_perag_busy_t), KM_SLEEP);
2199                 pag->pagf_init = 1;
2200         }
2201 #ifdef DEBUG
2202         else if (!XFS_FORCED_SHUTDOWN(mp)) {
2203                 ASSERT(pag->pagf_freeblks == INT_GET(agf->agf_freeblks, ARCH_CONVERT));
2204                 ASSERT(pag->pagf_flcount == INT_GET(agf->agf_flcount, ARCH_CONVERT));
2205                 ASSERT(pag->pagf_longest == INT_GET(agf->agf_longest, ARCH_CONVERT));
2206                 ASSERT(pag->pagf_levels[XFS_BTNUM_BNOi] ==
2207                        INT_GET(agf->agf_levels[XFS_BTNUM_BNOi], ARCH_CONVERT));
2208                 ASSERT(pag->pagf_levels[XFS_BTNUM_CNTi] ==
2209                        INT_GET(agf->agf_levels[XFS_BTNUM_CNTi], ARCH_CONVERT));
2210         }
2211 #endif
2212         XFS_BUF_SET_VTYPE_REF(bp, B_FS_AGF, XFS_AGF_REF);
2213         *bpp = bp;
2214         return 0;
2215 }
2216
2217 /*
2218  * Allocate an extent (variable-size).
2219  * Depending on the allocation type, we either look in a single allocation
2220  * group or loop over the allocation groups to find the result.
2221  */
2222 int                             /* error */
2223 xfs_alloc_vextent(
2224         xfs_alloc_arg_t *args)  /* allocation argument structure */
2225 {
2226         xfs_agblock_t   agsize; /* allocation group size */
2227         int             error;
2228         int             flags;  /* XFS_ALLOC_FLAG_... locking flags */
2229 #ifdef XFS_ALLOC_TRACE
2230         static char     fname[] = "xfs_alloc_vextent";
2231 #endif
2232         xfs_extlen_t    minleft;/* minimum left value, temp copy */
2233         xfs_mount_t     *mp;    /* mount structure pointer */
2234         xfs_agnumber_t  sagno;  /* starting allocation group number */
2235         xfs_alloctype_t type;   /* input allocation type */
2236         int             bump_rotor = 0;
2237         int             no_min = 0;
2238         xfs_agnumber_t  rotorstep = xfs_rotorstep; /* inode32 agf stepper */
2239
2240         mp = args->mp;
2241         type = args->otype = args->type;
2242         args->agbno = NULLAGBLOCK;
2243         /*
2244          * Just fix this up, for the case where the last a.g. is shorter
2245          * (or there's only one a.g.) and the caller couldn't easily figure
2246          * that out (xfs_bmap_alloc).
2247          */
2248         agsize = mp->m_sb.sb_agblocks;
2249         if (args->maxlen > agsize)
2250                 args->maxlen = agsize;
2251         if (args->alignment == 0)
2252                 args->alignment = 1;
2253         ASSERT(XFS_FSB_TO_AGNO(mp, args->fsbno) < mp->m_sb.sb_agcount);
2254         ASSERT(XFS_FSB_TO_AGBNO(mp, args->fsbno) < agsize);
2255         ASSERT(args->minlen <= args->maxlen);
2256         ASSERT(args->minlen <= agsize);
2257         ASSERT(args->mod < args->prod);
2258         if (XFS_FSB_TO_AGNO(mp, args->fsbno) >= mp->m_sb.sb_agcount ||
2259             XFS_FSB_TO_AGBNO(mp, args->fsbno) >= agsize ||
2260             args->minlen > args->maxlen || args->minlen > agsize ||
2261             args->mod >= args->prod) {
2262                 args->fsbno = NULLFSBLOCK;
2263                 TRACE_ALLOC("badargs", args);
2264                 return 0;
2265         }
2266         minleft = args->minleft;
2267
2268         switch (type) {
2269         case XFS_ALLOCTYPE_THIS_AG:
2270         case XFS_ALLOCTYPE_NEAR_BNO:
2271         case XFS_ALLOCTYPE_THIS_BNO:
2272                 /*
2273                  * These three force us into a single a.g.
2274                  */
2275                 args->agno = XFS_FSB_TO_AGNO(mp, args->fsbno);
2276                 down_read(&mp->m_peraglock);
2277                 args->pag = &mp->m_perag[args->agno];
2278                 args->minleft = 0;
2279                 error = xfs_alloc_fix_freelist(args, 0);
2280                 args->minleft = minleft;
2281                 if (error) {
2282                         TRACE_ALLOC("nofix", args);
2283                         goto error0;
2284                 }
2285                 if (!args->agbp) {
2286                         up_read(&mp->m_peraglock);
2287                         TRACE_ALLOC("noagbp", args);
2288                         break;
2289                 }
2290                 args->agbno = XFS_FSB_TO_AGBNO(mp, args->fsbno);
2291                 if ((error = xfs_alloc_ag_vextent(args)))
2292                         goto error0;
2293                 up_read(&mp->m_peraglock);
2294                 break;
2295         case XFS_ALLOCTYPE_START_BNO:
2296                 /*
2297                  * Try near allocation first, then anywhere-in-ag after
2298                  * the first a.g. fails.
2299                  */
2300                 if ((args->userdata  == XFS_ALLOC_INITIAL_USER_DATA) &&
2301                     (mp->m_flags & XFS_MOUNT_32BITINODES)) {
2302                         args->fsbno = XFS_AGB_TO_FSB(mp,
2303                                         ((mp->m_agfrotor / rotorstep) %
2304                                         mp->m_sb.sb_agcount), 0);
2305                         bump_rotor = 1;
2306                 }
2307                 args->agbno = XFS_FSB_TO_AGBNO(mp, args->fsbno);
2308                 args->type = XFS_ALLOCTYPE_NEAR_BNO;
2309                 /* FALLTHROUGH */
2310         case XFS_ALLOCTYPE_ANY_AG:
2311         case XFS_ALLOCTYPE_START_AG:
2312         case XFS_ALLOCTYPE_FIRST_AG:
2313                 /*
2314                  * Rotate through the allocation groups looking for a winner.
2315                  */
2316                 if (type == XFS_ALLOCTYPE_ANY_AG) {
2317                         /*
2318                          * Start with the last place we left off.
2319                          */
2320                         args->agno = sagno = (mp->m_agfrotor / rotorstep) %
2321                                         mp->m_sb.sb_agcount;
2322                         args->type = XFS_ALLOCTYPE_THIS_AG;
2323                         flags = XFS_ALLOC_FLAG_TRYLOCK;
2324                 } else if (type == XFS_ALLOCTYPE_FIRST_AG) {
2325                         /*
2326                          * Start with allocation group given by bno.
2327                          */
2328                         args->agno = XFS_FSB_TO_AGNO(mp, args->fsbno);
2329                         args->type = XFS_ALLOCTYPE_THIS_AG;
2330                         sagno = 0;
2331                         flags = 0;
2332                 } else {
2333                         if (type == XFS_ALLOCTYPE_START_AG)
2334                                 args->type = XFS_ALLOCTYPE_THIS_AG;
2335                         /*
2336                          * Start with the given allocation group.
2337                          */
2338                         args->agno = sagno = XFS_FSB_TO_AGNO(mp, args->fsbno);
2339                         flags = XFS_ALLOC_FLAG_TRYLOCK;
2340                 }
2341                 /*
2342                  * Loop over allocation groups twice; first time with
2343                  * trylock set, second time without.
2344                  */
2345                 down_read(&mp->m_peraglock);
2346                 for (;;) {
2347                         args->pag = &mp->m_perag[args->agno];
2348                         if (no_min) args->minleft = 0;
2349                         error = xfs_alloc_fix_freelist(args, flags);
2350                         args->minleft = minleft;
2351                         if (error) {
2352                                 TRACE_ALLOC("nofix", args);
2353                                 goto error0;
2354                         }
2355                         /*
2356                          * If we get a buffer back then the allocation will fly.
2357                          */
2358                         if (args->agbp) {
2359                                 if ((error = xfs_alloc_ag_vextent(args)))
2360                                         goto error0;
2361                                 break;
2362                         }
2363                         TRACE_ALLOC("loopfailed", args);
2364                         /*
2365                          * Didn't work, figure out the next iteration.
2366                          */
2367                         if (args->agno == sagno &&
2368                             type == XFS_ALLOCTYPE_START_BNO)
2369                                 args->type = XFS_ALLOCTYPE_THIS_AG;
2370                         if (++(args->agno) == mp->m_sb.sb_agcount)
2371                                 args->agno = 0;
2372                         /*
2373                          * Reached the starting a.g., must either be done
2374                          * or switch to non-trylock mode.
2375                          */
2376                         if (args->agno == sagno) {
2377                                 if (no_min == 1) {
2378                                         args->agbno = NULLAGBLOCK;
2379                                         TRACE_ALLOC("allfailed", args);
2380                                         break;
2381                                 }
2382                                 if (flags == 0) {
2383                                         no_min = 1;
2384                                 } else {
2385                                         flags = 0;
2386                                         if (type == XFS_ALLOCTYPE_START_BNO) {
2387                                                 args->agbno = XFS_FSB_TO_AGBNO(mp,
2388                                                         args->fsbno);
2389                                                 args->type = XFS_ALLOCTYPE_NEAR_BNO;
2390                                         }
2391                                 }
2392                         }
2393                 }
2394                 up_read(&mp->m_peraglock);
2395                 if (bump_rotor || (type == XFS_ALLOCTYPE_ANY_AG)) {
2396                         if (args->agno == sagno)
2397                                 mp->m_agfrotor = (mp->m_agfrotor + 1) %
2398                                         (mp->m_sb.sb_agcount * rotorstep);
2399                         else
2400                                 mp->m_agfrotor = (args->agno * rotorstep + 1) %
2401                                         (mp->m_sb.sb_agcount * rotorstep);
2402                 }
2403                 break;
2404         default:
2405                 ASSERT(0);
2406                 /* NOTREACHED */
2407         }
2408         if (args->agbno == NULLAGBLOCK)
2409                 args->fsbno = NULLFSBLOCK;
2410         else {
2411                 args->fsbno = XFS_AGB_TO_FSB(mp, args->agno, args->agbno);
2412 #ifdef DEBUG
2413                 ASSERT(args->len >= args->minlen);
2414                 ASSERT(args->len <= args->maxlen);
2415                 ASSERT(args->agbno % args->alignment == 0);
2416                 XFS_AG_CHECK_DADDR(mp, XFS_FSB_TO_DADDR(mp, args->fsbno),
2417                         args->len);
2418 #endif
2419         }
2420         return 0;
2421 error0:
2422         up_read(&mp->m_peraglock);
2423         return error;
2424 }
2425
2426 /*
2427  * Free an extent.
2428  * Just break up the extent address and hand off to xfs_free_ag_extent
2429  * after fixing up the freelist.
2430  */
2431 int                             /* error */
2432 xfs_free_extent(
2433         xfs_trans_t     *tp,    /* transaction pointer */
2434         xfs_fsblock_t   bno,    /* starting block number of extent */
2435         xfs_extlen_t    len)    /* length of extent */
2436 {
2437 #ifdef DEBUG
2438         xfs_agf_t       *agf;   /* a.g. freespace header */
2439 #endif
2440         xfs_alloc_arg_t args;   /* allocation argument structure */
2441         int             error;
2442
2443         ASSERT(len != 0);
2444         args.tp = tp;
2445         args.mp = tp->t_mountp;
2446         args.agno = XFS_FSB_TO_AGNO(args.mp, bno);
2447         ASSERT(args.agno < args.mp->m_sb.sb_agcount);
2448         args.agbno = XFS_FSB_TO_AGBNO(args.mp, bno);
2449         args.alignment = 1;
2450         args.minlen = args.minleft = args.minalignslop = 0;
2451         down_read(&args.mp->m_peraglock);
2452         args.pag = &args.mp->m_perag[args.agno];
2453         if ((error = xfs_alloc_fix_freelist(&args, 0)))
2454                 goto error0;
2455 #ifdef DEBUG
2456         ASSERT(args.agbp != NULL);
2457         agf = XFS_BUF_TO_AGF(args.agbp);
2458         ASSERT(args.agbno + len <= INT_GET(agf->agf_length, ARCH_CONVERT));
2459 #endif
2460         error = xfs_free_ag_extent(tp, args.agbp, args.agno, args.agbno,
2461                 len, 0);
2462 error0:
2463         up_read(&args.mp->m_peraglock);
2464         return error;
2465 }
2466
2467
2468 /*
2469  * AG Busy list management
2470  * The busy list contains block ranges that have been freed but whose
2471  * transacations have not yet hit disk.  If any block listed in a busy
2472  * list is reused, the transaction that freed it must be forced to disk
2473  * before continuing to use the block.
2474  *
2475  * xfs_alloc_mark_busy - add to the per-ag busy list
2476  * xfs_alloc_clear_busy - remove an item from the per-ag busy list
2477  */
2478 void
2479 xfs_alloc_mark_busy(xfs_trans_t *tp,
2480                     xfs_agnumber_t agno,
2481                     xfs_agblock_t bno,
2482                     xfs_extlen_t len)
2483 {
2484         xfs_mount_t             *mp;
2485         xfs_perag_busy_t        *bsy;
2486         int                     n;
2487         SPLDECL(s);
2488
2489         mp = tp->t_mountp;
2490         s = mutex_spinlock(&mp->m_perag[agno].pagb_lock);
2491
2492         /* search pagb_list for an open slot */
2493         for (bsy = mp->m_perag[agno].pagb_list, n = 0;
2494              n < XFS_PAGB_NUM_SLOTS;
2495              bsy++, n++) {
2496                 if (bsy->busy_tp == NULL) {
2497                         break;
2498                 }
2499         }
2500
2501         if (n < XFS_PAGB_NUM_SLOTS) {
2502                 bsy = &mp->m_perag[agno].pagb_list[n];
2503                 mp->m_perag[agno].pagb_count++;
2504                 TRACE_BUSY("xfs_alloc_mark_busy", "got", agno, bno, len, n, tp);
2505                 bsy->busy_start = bno;
2506                 bsy->busy_length = len;
2507                 bsy->busy_tp = tp;
2508                 xfs_trans_add_busy(tp, agno, n);
2509         } else {
2510                 TRACE_BUSY("xfs_alloc_mark_busy", "FULL", agno, bno, len, -1, tp);
2511                 /*
2512                  * The busy list is full!  Since it is now not possible to
2513                  * track the free block, make this a synchronous transaction
2514                  * to insure that the block is not reused before this
2515                  * transaction commits.
2516                  */
2517                 xfs_trans_set_sync(tp);
2518         }
2519
2520         mutex_spinunlock(&mp->m_perag[agno].pagb_lock, s);
2521 }
2522
2523 void
2524 xfs_alloc_clear_busy(xfs_trans_t *tp,
2525                      xfs_agnumber_t agno,
2526                      int idx)
2527 {
2528         xfs_mount_t             *mp;
2529         xfs_perag_busy_t        *list;
2530         SPLDECL(s);
2531
2532         mp = tp->t_mountp;
2533
2534         s = mutex_spinlock(&mp->m_perag[agno].pagb_lock);
2535         list = mp->m_perag[agno].pagb_list;
2536
2537         ASSERT(idx < XFS_PAGB_NUM_SLOTS);
2538         if (list[idx].busy_tp == tp) {
2539                 TRACE_UNBUSY("xfs_alloc_clear_busy", "found", agno, idx, tp);
2540                 list[idx].busy_tp = NULL;
2541                 mp->m_perag[agno].pagb_count--;
2542         } else {
2543                 TRACE_UNBUSY("xfs_alloc_clear_busy", "missing", agno, idx, tp);
2544         }
2545
2546         mutex_spinunlock(&mp->m_perag[agno].pagb_lock, s);
2547 }
2548
2549
2550 /*
2551  * returns non-zero if any of (agno,bno):len is in a busy list
2552  */
2553 STATIC int
2554 xfs_alloc_search_busy(xfs_trans_t *tp,
2555                     xfs_agnumber_t agno,
2556                     xfs_agblock_t bno,
2557                     xfs_extlen_t len)
2558 {
2559         xfs_mount_t             *mp;
2560         xfs_perag_busy_t        *bsy;
2561         int                     n;
2562         xfs_agblock_t           uend, bend;
2563         xfs_lsn_t               lsn;
2564         int                     cnt;
2565         SPLDECL(s);
2566
2567         mp = tp->t_mountp;
2568
2569         s = mutex_spinlock(&mp->m_perag[agno].pagb_lock);
2570         cnt = mp->m_perag[agno].pagb_count;
2571
2572         uend = bno + len - 1;
2573
2574         /* search pagb_list for this slot, skipping open slots */
2575         for (bsy = mp->m_perag[agno].pagb_list, n = 0;
2576              cnt; bsy++, n++) {
2577
2578                 /*
2579                  * (start1,length1) within (start2, length2)
2580                  */
2581                 if (bsy->busy_tp != NULL) {
2582                         bend = bsy->busy_start + bsy->busy_length - 1;
2583                         if ((bno > bend) ||
2584                             (uend < bsy->busy_start)) {
2585                                 cnt--;
2586                         } else {
2587                                 TRACE_BUSYSEARCH("xfs_alloc_search_busy",
2588                                                  "found1", agno, bno, len, n,
2589                                                  tp);
2590                                 break;
2591                         }
2592                 }
2593         }
2594
2595         /*
2596          * If a block was found, force the log through the LSN of the
2597          * transaction that freed the block
2598          */
2599         if (cnt) {
2600                 TRACE_BUSYSEARCH("xfs_alloc_search_busy", "found", agno, bno, len, n, tp);
2601                 lsn = bsy->busy_tp->t_commit_lsn;
2602                 mutex_spinunlock(&mp->m_perag[agno].pagb_lock, s);
2603                 xfs_log_force(mp, lsn, XFS_LOG_FORCE|XFS_LOG_SYNC);
2604         } else {
2605                 TRACE_BUSYSEARCH("xfs_alloc_search_busy", "not-found", agno, bno, len, n, tp);
2606                 n = -1;
2607                 mutex_spinunlock(&mp->m_perag[agno].pagb_lock, s);
2608         }
2609
2610         return n;
2611 }