← Back to branch summary

~ubuntu-branches/ubuntu/precise/linux-lowlatency/precise

« back to all changes in this revision

Viewing changes to fs/xfs/xfs_alloc.c

  • Committer: Package Import Robot
  • Author(s): Alessio Igor Bogani
  • Date: 2011-10-26 11:13:05 UTC
  • Revision ID: package-import@ubuntu.com-20111026111305-tz023xykf0i6eosh
Tags: upstream-3.2.0
Import upstream version 3.2.0

Show diffs side-by-side

added added

removed removed

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