blob: 95862bbff56bf0cf8c82d4e88178dc43408866d7 [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*
Nathan Scott7b718762005-11-02 14:58:39 +11002 * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc.
3 * All Rights Reserved.
Linus Torvalds1da177e2005-04-16 15:20:36 -07004 *
Nathan Scott7b718762005-11-02 14:58:39 +11005 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License as
Linus Torvalds1da177e2005-04-16 15:20:36 -07007 * published by the Free Software Foundation.
8 *
Nathan Scott7b718762005-11-02 14:58:39 +11009 * 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.
Linus Torvalds1da177e2005-04-16 15:20:36 -070013 *
Nathan Scott7b718762005-11-02 14:58:39 +110014 * 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
Linus Torvalds1da177e2005-04-16 15:20:36 -070017 */
Linus Torvalds1da177e2005-04-16 15:20:36 -070018#include "xfs.h"
Nathan Scotta844f452005-11-02 14:38:42 +110019#include "xfs_fs.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070020#include "xfs_types.h"
Nathan Scotta844f452005-11-02 14:38:42 +110021#include "xfs_bit.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070022#include "xfs_log.h"
Nathan Scotta844f452005-11-02 14:38:42 +110023#include "xfs_inum.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070024#include "xfs_trans.h"
25#include "xfs_sb.h"
26#include "xfs_ag.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070027#include "xfs_mount.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070028#include "xfs_bmap_btree.h"
Nathan Scotta844f452005-11-02 14:38:42 +110029#include "xfs_alloc_btree.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070030#include "xfs_ialloc_btree.h"
Nathan Scotta844f452005-11-02 14:38:42 +110031#include "xfs_dinode.h"
32#include "xfs_inode.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070033#include "xfs_btree.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070034#include "xfs_alloc.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070035#include "xfs_error.h"
Christoph Hellwig0b1b2132009-12-14 23:14:59 +000036#include "xfs_trace.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070037
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
Linus Torvalds1da177e2005-04-16 15:20:36 -070044STATIC int xfs_alloc_ag_vextent_exact(xfs_alloc_arg_t *);
45STATIC int xfs_alloc_ag_vextent_near(xfs_alloc_arg_t *);
46STATIC int xfs_alloc_ag_vextent_size(xfs_alloc_arg_t *);
47STATIC int xfs_alloc_ag_vextent_small(xfs_alloc_arg_t *,
Christoph Hellwige26f0502011-04-24 19:06:15 +000048 xfs_btree_cur_t *, xfs_agblock_t *, xfs_extlen_t *, int *);
49STATIC void xfs_alloc_busy_trim(struct xfs_alloc_arg *,
50 xfs_agblock_t, xfs_extlen_t, xfs_agblock_t *, xfs_extlen_t *);
Linus Torvalds1da177e2005-04-16 15:20:36 -070051
52/*
Christoph Hellwigfe033cc2008-10-30 16:56:09 +110053 * Lookup the record equal to [bno, len] in the btree given by cur.
54 */
55STATIC int /* error */
56xfs_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 */
71STATIC int /* error */
72xfs_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 */
Christoph Hellwiga46db602011-01-07 13:02:04 +000087int /* error */
Christoph Hellwigfe033cc2008-10-30 16:56:09 +110088xfs_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
Christoph Hellwig278d0ca2008-10-30 16:56:32 +110099/*
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 */
104STATIC int /* error */
105xfs_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}
Christoph Hellwigfe033cc2008-10-30 16:56:09 +1100116
117/*
Christoph Hellwig8cc938f2008-10-30 16:58:11 +1100118 * Get the data from the pointed-to record.
119 */
Christoph Hellwiga46db602011-01-07 13:02:04 +0000120int /* error */
Christoph Hellwig8cc938f2008-10-30 16:58:11 +1100121xfs_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/*
Linus Torvalds1da177e2005-04-16 15:20:36 -0700139 * Compute aligned version of the found extent.
140 * Takes alignment and min length into account.
141 */
David Chinner12375c82008-04-10 12:21:32 +1000142STATIC void
Linus Torvalds1da177e2005-04-16 15:20:36 -0700143xfs_alloc_compute_aligned(
Christoph Hellwig86fa8af2011-03-04 12:59:54 +0000144 xfs_alloc_arg_t *args, /* allocation argument structure */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700145 xfs_agblock_t foundbno, /* starting block in found extent */
146 xfs_extlen_t foundlen, /* length in found extent */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700147 xfs_agblock_t *resbno, /* result block number */
148 xfs_extlen_t *reslen) /* result length */
149{
150 xfs_agblock_t bno;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700151 xfs_extlen_t len;
152
Christoph Hellwige26f0502011-04-24 19:06:15 +0000153 /* 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;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700162 } else {
Christoph Hellwige26f0502011-04-24 19:06:15 +0000163 *resbno = bno;
164 *reslen = len;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700165 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700166}
167
168/*
169 * Compute best start block and diff for "near" allocations.
170 * freelen >= wantlen already checked by caller.
171 */
172STATIC xfs_extlen_t /* difference value (absolute) */
173xfs_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 */
234STATIC void
235xfs_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 */
268STATIC int
269xfs_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);
Christoph Hellwig16259e72005-11-02 15:11:25 +1100278 diff = be32_to_cpu(agf->agf_freeblks)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700279 - 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 */
296STATIC int /* error code */
297xfs_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 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700343
Christoph Hellwig7cc95a82008-10-30 17:14:34 +1100344#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);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700354 }
355#endif
Christoph Hellwig7cc95a82008-10-30 17:14:34 +1100356
Linus Torvalds1da177e2005-04-16 15:20:36 -0700357 /*
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 */
Christoph Hellwig91cca5d2008-10-30 16:58:01 +1100381 if ((error = xfs_btree_delete(cnt_cur, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700382 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);
Christoph Hellwig4b22a572008-10-30 16:57:40 +1100391 if ((error = xfs_btree_insert(cnt_cur, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700392 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);
Christoph Hellwig4b22a572008-10-30 16:57:40 +1100399 if ((error = xfs_btree_insert(cnt_cur, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700400 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 */
Christoph Hellwig91cca5d2008-10-30 16:58:01 +1100410 if ((error = xfs_btree_delete(bno_cur, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700411 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);
Christoph Hellwig4b22a572008-10-30 16:57:40 +1100427 if ((error = xfs_btree_insert(bno_cur, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700428 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 */
437STATIC int /* error */
438xfs_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(bp);
455 ASSERT(!XFS_BUF_GETERROR(bp));
456 XFS_BUF_SET_VTYPE_REF(bp, B_FS_AGFL, XFS_AGFL_REF);
457 *bpp = bp;
458 return 0;
459}
460
Christoph Hellwigecb69282011-03-04 12:59:55 +0000461STATIC int
462xfs_alloc_update_counters(
463 struct xfs_trans *tp,
464 struct xfs_perag *pag,
465 struct xfs_buf *agbp,
466 long len)
467{
468 struct xfs_agf *agf = XFS_BUF_TO_AGF(agbp);
469
470 pag->pagf_freeblks += len;
471 be32_add_cpu(&agf->agf_freeblks, len);
472
473 xfs_trans_agblocks_delta(tp, len);
474 if (unlikely(be32_to_cpu(agf->agf_freeblks) >
475 be32_to_cpu(agf->agf_length)))
476 return EFSCORRUPTED;
477
478 xfs_alloc_log_agf(tp, agbp, XFS_AGF_FREEBLKS);
479 return 0;
480}
481
Linus Torvalds1da177e2005-04-16 15:20:36 -0700482/*
483 * Allocation group level functions.
484 */
485
486/*
487 * Allocate a variable extent in the allocation group agno.
488 * Type and bno are used to determine where in the allocation group the
489 * extent will start.
490 * Extent's length (returned in *len) will be between minlen and maxlen,
491 * and of the form k * prod + mod unless there's nothing that large.
492 * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
493 */
494STATIC int /* error */
495xfs_alloc_ag_vextent(
496 xfs_alloc_arg_t *args) /* argument structure for allocation */
497{
498 int error=0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700499
500 ASSERT(args->minlen > 0);
501 ASSERT(args->maxlen > 0);
502 ASSERT(args->minlen <= args->maxlen);
503 ASSERT(args->mod < args->prod);
504 ASSERT(args->alignment > 0);
505 /*
506 * Branch to correct routine based on the type.
507 */
508 args->wasfromfl = 0;
509 switch (args->type) {
510 case XFS_ALLOCTYPE_THIS_AG:
511 error = xfs_alloc_ag_vextent_size(args);
512 break;
513 case XFS_ALLOCTYPE_NEAR_BNO:
514 error = xfs_alloc_ag_vextent_near(args);
515 break;
516 case XFS_ALLOCTYPE_THIS_BNO:
517 error = xfs_alloc_ag_vextent_exact(args);
518 break;
519 default:
520 ASSERT(0);
521 /* NOTREACHED */
522 }
Christoph Hellwigecb69282011-03-04 12:59:55 +0000523
524 if (error || args->agbno == NULLAGBLOCK)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700525 return error;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700526
Christoph Hellwigecb69282011-03-04 12:59:55 +0000527 ASSERT(args->len >= args->minlen);
528 ASSERT(args->len <= args->maxlen);
529 ASSERT(!args->wasfromfl || !args->isfl);
530 ASSERT(args->agbno % args->alignment == 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700531
Christoph Hellwigecb69282011-03-04 12:59:55 +0000532 if (!args->wasfromfl) {
533 error = xfs_alloc_update_counters(args->tp, args->pag,
534 args->agbp,
535 -((long)(args->len)));
536 if (error)
537 return error;
538
Christoph Hellwige26f0502011-04-24 19:06:15 +0000539 ASSERT(!xfs_alloc_busy_search(args->mp, args->agno,
540 args->agbno, args->len));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700541 }
Christoph Hellwigecb69282011-03-04 12:59:55 +0000542
543 if (!args->isfl) {
544 xfs_trans_mod_sb(args->tp, args->wasdel ?
545 XFS_TRANS_SB_RES_FDBLOCKS :
546 XFS_TRANS_SB_FDBLOCKS,
547 -((long)(args->len)));
548 }
549
550 XFS_STATS_INC(xs_allocx);
551 XFS_STATS_ADD(xs_allocb, args->len);
552 return error;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700553}
554
555/*
556 * Allocate a variable extent at exactly agno/bno.
557 * Extent's length (returned in *len) will be between minlen and maxlen,
558 * and of the form k * prod + mod unless there's nothing that large.
559 * Return the starting a.g. block (bno), or NULLAGBLOCK if we can't do it.
560 */
561STATIC int /* error */
562xfs_alloc_ag_vextent_exact(
563 xfs_alloc_arg_t *args) /* allocation argument structure */
564{
565 xfs_btree_cur_t *bno_cur;/* by block-number btree cursor */
566 xfs_btree_cur_t *cnt_cur;/* by count btree cursor */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700567 int error;
568 xfs_agblock_t fbno; /* start block of found extent */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700569 xfs_extlen_t flen; /* length of found extent */
Christoph Hellwige26f0502011-04-24 19:06:15 +0000570 xfs_agblock_t tbno; /* start block of trimmed extent */
571 xfs_extlen_t tlen; /* length of trimmed extent */
572 xfs_agblock_t tend; /* end block of trimmed extent */
573 xfs_agblock_t end; /* end of allocated extent */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700574 int i; /* success/failure of operation */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700575 xfs_extlen_t rlen; /* length of returned extent */
576
577 ASSERT(args->alignment == 1);
Christoph Hellwig9f9baab2010-12-10 15:03:57 +0000578
Linus Torvalds1da177e2005-04-16 15:20:36 -0700579 /*
580 * Allocate/initialize a cursor for the by-number freespace btree.
581 */
Christoph Hellwig561f7d12008-10-30 16:53:59 +1100582 bno_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
Christoph Hellwig9f9baab2010-12-10 15:03:57 +0000583 args->agno, XFS_BTNUM_BNO);
584
Linus Torvalds1da177e2005-04-16 15:20:36 -0700585 /*
586 * Lookup bno and minlen in the btree (minlen is irrelevant, really).
587 * Look for the closest free block <= bno, it must contain bno
588 * if any free block does.
589 */
Christoph Hellwig9f9baab2010-12-10 15:03:57 +0000590 error = xfs_alloc_lookup_le(bno_cur, args->agbno, args->minlen, &i);
591 if (error)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700592 goto error0;
Christoph Hellwig9f9baab2010-12-10 15:03:57 +0000593 if (!i)
594 goto not_found;
595
Linus Torvalds1da177e2005-04-16 15:20:36 -0700596 /*
597 * Grab the freespace record.
598 */
Christoph Hellwig9f9baab2010-12-10 15:03:57 +0000599 error = xfs_alloc_get_rec(bno_cur, &fbno, &flen, &i);
600 if (error)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700601 goto error0;
602 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
603 ASSERT(fbno <= args->agbno);
Christoph Hellwig9f9baab2010-12-10 15:03:57 +0000604
Linus Torvalds1da177e2005-04-16 15:20:36 -0700605 /*
Christoph Hellwige26f0502011-04-24 19:06:15 +0000606 * Check for overlapping busy extents.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700607 */
Christoph Hellwige26f0502011-04-24 19:06:15 +0000608 xfs_alloc_busy_trim(args, fbno, flen, &tbno, &tlen);
609
610 /*
611 * Give up if the start of the extent is busy, or the freespace isn't
612 * long enough for the minimum request.
613 */
614 if (tbno > args->agbno)
615 goto not_found;
616 if (tlen < args->minlen)
617 goto not_found;
618 tend = tbno + tlen;
619 if (tend < args->agbno + args->minlen)
Christoph Hellwig9f9baab2010-12-10 15:03:57 +0000620 goto not_found;
621
Linus Torvalds1da177e2005-04-16 15:20:36 -0700622 /*
623 * End of extent will be smaller of the freespace end and the
624 * maximal requested end.
Christoph Hellwig9f9baab2010-12-10 15:03:57 +0000625 *
Linus Torvalds1da177e2005-04-16 15:20:36 -0700626 * Fix the length according to mod and prod if given.
627 */
Christoph Hellwige26f0502011-04-24 19:06:15 +0000628 end = XFS_AGBLOCK_MIN(tend, args->agbno + args->maxlen);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700629 args->len = end - args->agbno;
630 xfs_alloc_fix_len(args);
Christoph Hellwig9f9baab2010-12-10 15:03:57 +0000631 if (!xfs_alloc_fix_minleft(args))
632 goto not_found;
633
Linus Torvalds1da177e2005-04-16 15:20:36 -0700634 rlen = args->len;
Christoph Hellwige26f0502011-04-24 19:06:15 +0000635 ASSERT(args->agbno + rlen <= tend);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700636 end = args->agbno + rlen;
Christoph Hellwig9f9baab2010-12-10 15:03:57 +0000637
Linus Torvalds1da177e2005-04-16 15:20:36 -0700638 /*
639 * We are allocating agbno for rlen [agbno .. end]
640 * Allocate/initialize a cursor for the by-size btree.
641 */
Christoph Hellwig561f7d12008-10-30 16:53:59 +1100642 cnt_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
643 args->agno, XFS_BTNUM_CNT);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700644 ASSERT(args->agbno + args->len <=
Christoph Hellwig16259e72005-11-02 15:11:25 +1100645 be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length));
Christoph Hellwig9f9baab2010-12-10 15:03:57 +0000646 error = xfs_alloc_fixup_trees(cnt_cur, bno_cur, fbno, flen, args->agbno,
647 args->len, XFSA_FIXUP_BNO_OK);
648 if (error) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700649 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
650 goto error0;
651 }
Christoph Hellwig9f9baab2010-12-10 15:03:57 +0000652
Linus Torvalds1da177e2005-04-16 15:20:36 -0700653 xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
654 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
Christoph Hellwig0b1b2132009-12-14 23:14:59 +0000655
Linus Torvalds1da177e2005-04-16 15:20:36 -0700656 args->wasfromfl = 0;
Christoph Hellwig9f9baab2010-12-10 15:03:57 +0000657 trace_xfs_alloc_exact_done(args);
658 return 0;
659
660not_found:
661 /* Didn't find it, return null. */
662 xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
663 args->agbno = NULLAGBLOCK;
664 trace_xfs_alloc_exact_notfound(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700665 return 0;
666
667error0:
668 xfs_btree_del_cursor(bno_cur, XFS_BTREE_ERROR);
Christoph Hellwig0b1b2132009-12-14 23:14:59 +0000669 trace_xfs_alloc_exact_error(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700670 return error;
671}
672
673/*
Christoph Hellwig489a1502010-12-10 15:04:11 +0000674 * Search the btree in a given direction via the search cursor and compare
675 * the records found against the good extent we've already found.
676 */
677STATIC int
678xfs_alloc_find_best_extent(
679 struct xfs_alloc_arg *args, /* allocation argument structure */
680 struct xfs_btree_cur **gcur, /* good cursor */
681 struct xfs_btree_cur **scur, /* searching cursor */
682 xfs_agblock_t gdiff, /* difference for search comparison */
683 xfs_agblock_t *sbno, /* extent found by search */
Christoph Hellwige26f0502011-04-24 19:06:15 +0000684 xfs_extlen_t *slen, /* extent length */
685 xfs_agblock_t *sbnoa, /* aligned extent found by search */
686 xfs_extlen_t *slena, /* aligned extent length */
Christoph Hellwig489a1502010-12-10 15:04:11 +0000687 int dir) /* 0 = search right, 1 = search left */
688{
Christoph Hellwig489a1502010-12-10 15:04:11 +0000689 xfs_agblock_t new;
690 xfs_agblock_t sdiff;
691 int error;
692 int i;
693
694 /* The good extent is perfect, no need to search. */
695 if (!gdiff)
696 goto out_use_good;
697
698 /*
699 * Look until we find a better one, run out of space or run off the end.
700 */
701 do {
702 error = xfs_alloc_get_rec(*scur, sbno, slen, &i);
703 if (error)
704 goto error0;
705 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
Christoph Hellwige26f0502011-04-24 19:06:15 +0000706 xfs_alloc_compute_aligned(args, *sbno, *slen, sbnoa, slena);
Christoph Hellwig489a1502010-12-10 15:04:11 +0000707
708 /*
709 * The good extent is closer than this one.
710 */
711 if (!dir) {
Christoph Hellwige26f0502011-04-24 19:06:15 +0000712 if (*sbnoa >= args->agbno + gdiff)
Christoph Hellwig489a1502010-12-10 15:04:11 +0000713 goto out_use_good;
714 } else {
Christoph Hellwige26f0502011-04-24 19:06:15 +0000715 if (*sbnoa <= args->agbno - gdiff)
Christoph Hellwig489a1502010-12-10 15:04:11 +0000716 goto out_use_good;
717 }
718
719 /*
720 * Same distance, compare length and pick the best.
721 */
722 if (*slena >= args->minlen) {
723 args->len = XFS_EXTLEN_MIN(*slena, args->maxlen);
724 xfs_alloc_fix_len(args);
725
726 sdiff = xfs_alloc_compute_diff(args->agbno, args->len,
Christoph Hellwige26f0502011-04-24 19:06:15 +0000727 args->alignment, *sbnoa,
728 *slena, &new);
Christoph Hellwig489a1502010-12-10 15:04:11 +0000729
730 /*
731 * Choose closer size and invalidate other cursor.
732 */
733 if (sdiff < gdiff)
734 goto out_use_search;
735 goto out_use_good;
736 }
737
738 if (!dir)
739 error = xfs_btree_increment(*scur, 0, &i);
740 else
741 error = xfs_btree_decrement(*scur, 0, &i);
742 if (error)
743 goto error0;
744 } while (i);
745
746out_use_good:
747 xfs_btree_del_cursor(*scur, XFS_BTREE_NOERROR);
748 *scur = NULL;
749 return 0;
750
751out_use_search:
752 xfs_btree_del_cursor(*gcur, XFS_BTREE_NOERROR);
753 *gcur = NULL;
754 return 0;
755
756error0:
757 /* caller invalidates cursors */
758 return error;
759}
760
761/*
Linus Torvalds1da177e2005-04-16 15:20:36 -0700762 * Allocate a variable extent near bno in the allocation group agno.
763 * Extent's length (returned in len) will be between minlen and maxlen,
764 * and of the form k * prod + mod unless there's nothing that large.
765 * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
766 */
767STATIC int /* error */
768xfs_alloc_ag_vextent_near(
769 xfs_alloc_arg_t *args) /* allocation argument structure */
770{
771 xfs_btree_cur_t *bno_cur_gt; /* cursor for bno btree, right side */
772 xfs_btree_cur_t *bno_cur_lt; /* cursor for bno btree, left side */
773 xfs_btree_cur_t *cnt_cur; /* cursor for count btree */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700774 xfs_agblock_t gtbno; /* start bno of right side entry */
775 xfs_agblock_t gtbnoa; /* aligned ... */
776 xfs_extlen_t gtdiff; /* difference to right side entry */
777 xfs_extlen_t gtlen; /* length of right side entry */
Christoph Hellwige26f0502011-04-24 19:06:15 +0000778 xfs_extlen_t gtlena; /* aligned ... */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700779 xfs_agblock_t gtnew; /* useful start bno of right side */
780 int error; /* error code */
781 int i; /* result code, temporary */
782 int j; /* result code, temporary */
783 xfs_agblock_t ltbno; /* start bno of left side entry */
784 xfs_agblock_t ltbnoa; /* aligned ... */
785 xfs_extlen_t ltdiff; /* difference to left side entry */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700786 xfs_extlen_t ltlen; /* length of left side entry */
Christoph Hellwige26f0502011-04-24 19:06:15 +0000787 xfs_extlen_t ltlena; /* aligned ... */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700788 xfs_agblock_t ltnew; /* useful start bno of left side */
789 xfs_extlen_t rlen; /* length of returned extent */
Christoph Hellwige26f0502011-04-24 19:06:15 +0000790 int forced = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700791#if defined(DEBUG) && defined(__KERNEL__)
792 /*
793 * Randomly don't execute the first algorithm.
794 */
795 int dofirst; /* set to do first algorithm */
796
Joe Perchese7a23a92007-05-08 13:49:03 +1000797 dofirst = random32() & 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700798#endif
Christoph Hellwige26f0502011-04-24 19:06:15 +0000799
800restart:
801 bno_cur_lt = NULL;
802 bno_cur_gt = NULL;
803 ltlen = 0;
804 gtlena = 0;
805 ltlena = 0;
806
Linus Torvalds1da177e2005-04-16 15:20:36 -0700807 /*
808 * Get a cursor for the by-size btree.
809 */
Christoph Hellwig561f7d12008-10-30 16:53:59 +1100810 cnt_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
811 args->agno, XFS_BTNUM_CNT);
Christoph Hellwige26f0502011-04-24 19:06:15 +0000812
Linus Torvalds1da177e2005-04-16 15:20:36 -0700813 /*
814 * See if there are any free extents as big as maxlen.
815 */
816 if ((error = xfs_alloc_lookup_ge(cnt_cur, 0, args->maxlen, &i)))
817 goto error0;
818 /*
819 * If none, then pick up the last entry in the tree unless the
820 * tree is empty.
821 */
822 if (!i) {
823 if ((error = xfs_alloc_ag_vextent_small(args, cnt_cur, &ltbno,
824 &ltlen, &i)))
825 goto error0;
826 if (i == 0 || ltlen == 0) {
827 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
Christoph Hellwige26f0502011-04-24 19:06:15 +0000828 trace_xfs_alloc_near_noentry(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700829 return 0;
830 }
831 ASSERT(i == 1);
832 }
833 args->wasfromfl = 0;
Christoph Hellwige26f0502011-04-24 19:06:15 +0000834
Linus Torvalds1da177e2005-04-16 15:20:36 -0700835 /*
836 * First algorithm.
837 * If the requested extent is large wrt the freespaces available
838 * in this a.g., then the cursor will be pointing to a btree entry
839 * near the right edge of the tree. If it's in the last btree leaf
840 * block, then we just examine all the entries in that block
841 * that are big enough, and pick the best one.
842 * This is written as a while loop so we can break out of it,
843 * but we never loop back to the top.
844 */
845 while (xfs_btree_islastblock(cnt_cur, 0)) {
846 xfs_extlen_t bdiff;
847 int besti=0;
848 xfs_extlen_t blen=0;
849 xfs_agblock_t bnew=0;
850
851#if defined(DEBUG) && defined(__KERNEL__)
852 if (!dofirst)
853 break;
854#endif
855 /*
856 * Start from the entry that lookup found, sequence through
857 * all larger free blocks. If we're actually pointing at a
858 * record smaller than maxlen, go to the start of this block,
859 * and skip all those smaller than minlen.
860 */
861 if (ltlen || args->alignment > 1) {
862 cnt_cur->bc_ptrs[0] = 1;
863 do {
864 if ((error = xfs_alloc_get_rec(cnt_cur, &ltbno,
865 &ltlen, &i)))
866 goto error0;
867 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
868 if (ltlen >= args->minlen)
869 break;
Christoph Hellwig637aa502008-10-30 16:55:45 +1100870 if ((error = xfs_btree_increment(cnt_cur, 0, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700871 goto error0;
872 } while (i);
873 ASSERT(ltlen >= args->minlen);
874 if (!i)
875 break;
876 }
877 i = cnt_cur->bc_ptrs[0];
878 for (j = 1, blen = 0, bdiff = 0;
879 !error && j && (blen < args->maxlen || bdiff > 0);
Christoph Hellwig637aa502008-10-30 16:55:45 +1100880 error = xfs_btree_increment(cnt_cur, 0, &j)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700881 /*
882 * For each entry, decide if it's better than
883 * the previous best entry.
884 */
885 if ((error = xfs_alloc_get_rec(cnt_cur, &ltbno, &ltlen, &i)))
886 goto error0;
887 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
Christoph Hellwig86fa8af2011-03-04 12:59:54 +0000888 xfs_alloc_compute_aligned(args, ltbno, ltlen,
889 &ltbnoa, &ltlena);
David Chinnere6430032008-04-17 16:49:49 +1000890 if (ltlena < args->minlen)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700891 continue;
892 args->len = XFS_EXTLEN_MIN(ltlena, args->maxlen);
893 xfs_alloc_fix_len(args);
894 ASSERT(args->len >= args->minlen);
895 if (args->len < blen)
896 continue;
897 ltdiff = xfs_alloc_compute_diff(args->agbno, args->len,
Christoph Hellwige26f0502011-04-24 19:06:15 +0000898 args->alignment, ltbnoa, ltlena, &ltnew);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700899 if (ltnew != NULLAGBLOCK &&
900 (args->len > blen || ltdiff < bdiff)) {
901 bdiff = ltdiff;
902 bnew = ltnew;
903 blen = args->len;
904 besti = cnt_cur->bc_ptrs[0];
905 }
906 }
907 /*
908 * It didn't work. We COULD be in a case where
909 * there's a good record somewhere, so try again.
910 */
911 if (blen == 0)
912 break;
913 /*
914 * Point at the best entry, and retrieve it again.
915 */
916 cnt_cur->bc_ptrs[0] = besti;
917 if ((error = xfs_alloc_get_rec(cnt_cur, &ltbno, &ltlen, &i)))
918 goto error0;
919 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
Christoph Hellwig73523a22010-07-20 17:54:45 +1000920 ASSERT(ltbno + ltlen <= be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700921 args->len = blen;
922 if (!xfs_alloc_fix_minleft(args)) {
923 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
Christoph Hellwig0b1b2132009-12-14 23:14:59 +0000924 trace_xfs_alloc_near_nominleft(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700925 return 0;
926 }
927 blen = args->len;
928 /*
929 * We are allocating starting at bnew for blen blocks.
930 */
931 args->agbno = bnew;
932 ASSERT(bnew >= ltbno);
Christoph Hellwig73523a22010-07-20 17:54:45 +1000933 ASSERT(bnew + blen <= ltbno + ltlen);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700934 /*
935 * Set up a cursor for the by-bno tree.
936 */
Christoph Hellwig561f7d12008-10-30 16:53:59 +1100937 bno_cur_lt = xfs_allocbt_init_cursor(args->mp, args->tp,
938 args->agbp, args->agno, XFS_BTNUM_BNO);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700939 /*
940 * Fix up the btree entries.
941 */
942 if ((error = xfs_alloc_fixup_trees(cnt_cur, bno_cur_lt, ltbno,
943 ltlen, bnew, blen, XFSA_FIXUP_CNT_OK)))
944 goto error0;
945 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
946 xfs_btree_del_cursor(bno_cur_lt, XFS_BTREE_NOERROR);
Christoph Hellwig0b1b2132009-12-14 23:14:59 +0000947
948 trace_xfs_alloc_near_first(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700949 return 0;
950 }
951 /*
952 * Second algorithm.
953 * Search in the by-bno tree to the left and to the right
954 * simultaneously, until in each case we find a space big enough,
955 * or run into the edge of the tree. When we run into the edge,
956 * we deallocate that cursor.
957 * If both searches succeed, we compare the two spaces and pick
958 * the better one.
959 * With alignment, it's possible for both to fail; the upper
960 * level algorithm that picks allocation groups for allocations
961 * is not supposed to do this.
962 */
963 /*
964 * Allocate and initialize the cursor for the leftward search.
965 */
Christoph Hellwig561f7d12008-10-30 16:53:59 +1100966 bno_cur_lt = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
967 args->agno, XFS_BTNUM_BNO);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700968 /*
969 * Lookup <= bno to find the leftward search's starting point.
970 */
971 if ((error = xfs_alloc_lookup_le(bno_cur_lt, args->agbno, args->maxlen, &i)))
972 goto error0;
973 if (!i) {
974 /*
975 * Didn't find anything; use this cursor for the rightward
976 * search.
977 */
978 bno_cur_gt = bno_cur_lt;
979 bno_cur_lt = NULL;
980 }
981 /*
982 * Found something. Duplicate the cursor for the rightward search.
983 */
984 else if ((error = xfs_btree_dup_cursor(bno_cur_lt, &bno_cur_gt)))
985 goto error0;
986 /*
987 * Increment the cursor, so we will point at the entry just right
988 * of the leftward entry if any, or to the leftmost entry.
989 */
Christoph Hellwig637aa502008-10-30 16:55:45 +1100990 if ((error = xfs_btree_increment(bno_cur_gt, 0, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700991 goto error0;
992 if (!i) {
993 /*
994 * It failed, there are no rightward entries.
995 */
996 xfs_btree_del_cursor(bno_cur_gt, XFS_BTREE_NOERROR);
997 bno_cur_gt = NULL;
998 }
999 /*
1000 * Loop going left with the leftward cursor, right with the
1001 * rightward cursor, until either both directions give up or
1002 * we find an entry at least as big as minlen.
1003 */
1004 do {
1005 if (bno_cur_lt) {
1006 if ((error = xfs_alloc_get_rec(bno_cur_lt, &ltbno, &ltlen, &i)))
1007 goto error0;
1008 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
Christoph Hellwig86fa8af2011-03-04 12:59:54 +00001009 xfs_alloc_compute_aligned(args, ltbno, ltlen,
1010 &ltbnoa, &ltlena);
David Chinner12375c82008-04-10 12:21:32 +10001011 if (ltlena >= args->minlen)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001012 break;
Christoph Hellwig8df4da42008-10-30 16:55:58 +11001013 if ((error = xfs_btree_decrement(bno_cur_lt, 0, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001014 goto error0;
1015 if (!i) {
1016 xfs_btree_del_cursor(bno_cur_lt,
1017 XFS_BTREE_NOERROR);
1018 bno_cur_lt = NULL;
1019 }
1020 }
1021 if (bno_cur_gt) {
1022 if ((error = xfs_alloc_get_rec(bno_cur_gt, &gtbno, &gtlen, &i)))
1023 goto error0;
1024 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
Christoph Hellwig86fa8af2011-03-04 12:59:54 +00001025 xfs_alloc_compute_aligned(args, gtbno, gtlen,
1026 &gtbnoa, &gtlena);
David Chinner12375c82008-04-10 12:21:32 +10001027 if (gtlena >= args->minlen)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001028 break;
Christoph Hellwig637aa502008-10-30 16:55:45 +11001029 if ((error = xfs_btree_increment(bno_cur_gt, 0, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001030 goto error0;
1031 if (!i) {
1032 xfs_btree_del_cursor(bno_cur_gt,
1033 XFS_BTREE_NOERROR);
1034 bno_cur_gt = NULL;
1035 }
1036 }
1037 } while (bno_cur_lt || bno_cur_gt);
Christoph Hellwig489a1502010-12-10 15:04:11 +00001038
Linus Torvalds1da177e2005-04-16 15:20:36 -07001039 /*
1040 * Got both cursors still active, need to find better entry.
1041 */
1042 if (bno_cur_lt && bno_cur_gt) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001043 if (ltlena >= args->minlen) {
1044 /*
Christoph Hellwig489a1502010-12-10 15:04:11 +00001045 * Left side is good, look for a right side entry.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001046 */
1047 args->len = XFS_EXTLEN_MIN(ltlena, args->maxlen);
1048 xfs_alloc_fix_len(args);
Christoph Hellwig489a1502010-12-10 15:04:11 +00001049 ltdiff = xfs_alloc_compute_diff(args->agbno, args->len,
Christoph Hellwige26f0502011-04-24 19:06:15 +00001050 args->alignment, ltbnoa, ltlena, &ltnew);
Christoph Hellwig489a1502010-12-10 15:04:11 +00001051
1052 error = xfs_alloc_find_best_extent(args,
1053 &bno_cur_lt, &bno_cur_gt,
Christoph Hellwige26f0502011-04-24 19:06:15 +00001054 ltdiff, &gtbno, &gtlen,
1055 &gtbnoa, &gtlena,
Christoph Hellwig489a1502010-12-10 15:04:11 +00001056 0 /* search right */);
1057 } else {
1058 ASSERT(gtlena >= args->minlen);
1059
Linus Torvalds1da177e2005-04-16 15:20:36 -07001060 /*
Christoph Hellwig489a1502010-12-10 15:04:11 +00001061 * Right side is good, look for a left side entry.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001062 */
1063 args->len = XFS_EXTLEN_MIN(gtlena, args->maxlen);
1064 xfs_alloc_fix_len(args);
Christoph Hellwig489a1502010-12-10 15:04:11 +00001065 gtdiff = xfs_alloc_compute_diff(args->agbno, args->len,
Christoph Hellwige26f0502011-04-24 19:06:15 +00001066 args->alignment, gtbnoa, gtlena, &gtnew);
Christoph Hellwig489a1502010-12-10 15:04:11 +00001067
1068 error = xfs_alloc_find_best_extent(args,
1069 &bno_cur_gt, &bno_cur_lt,
Christoph Hellwige26f0502011-04-24 19:06:15 +00001070 gtdiff, &ltbno, &ltlen,
1071 &ltbnoa, &ltlena,
Christoph Hellwig489a1502010-12-10 15:04:11 +00001072 1 /* search left */);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001073 }
Christoph Hellwig489a1502010-12-10 15:04:11 +00001074
1075 if (error)
1076 goto error0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001077 }
Christoph Hellwig489a1502010-12-10 15:04:11 +00001078
Linus Torvalds1da177e2005-04-16 15:20:36 -07001079 /*
1080 * If we couldn't get anything, give up.
1081 */
1082 if (bno_cur_lt == NULL && bno_cur_gt == NULL) {
Christoph Hellwige26f0502011-04-24 19:06:15 +00001083 if (!forced++) {
1084 trace_xfs_alloc_near_busy(args);
1085 xfs_log_force(args->mp, XFS_LOG_SYNC);
1086 goto restart;
1087 }
1088
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00001089 trace_xfs_alloc_size_neither(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001090 args->agbno = NULLAGBLOCK;
1091 return 0;
1092 }
Christoph Hellwig489a1502010-12-10 15:04:11 +00001093
Linus Torvalds1da177e2005-04-16 15:20:36 -07001094 /*
1095 * At this point we have selected a freespace entry, either to the
1096 * left or to the right. If it's on the right, copy all the
1097 * useful variables to the "left" set so we only have one
1098 * copy of this code.
1099 */
1100 if (bno_cur_gt) {
1101 bno_cur_lt = bno_cur_gt;
1102 bno_cur_gt = NULL;
1103 ltbno = gtbno;
1104 ltbnoa = gtbnoa;
1105 ltlen = gtlen;
1106 ltlena = gtlena;
1107 j = 1;
1108 } else
1109 j = 0;
Christoph Hellwig489a1502010-12-10 15:04:11 +00001110
Linus Torvalds1da177e2005-04-16 15:20:36 -07001111 /*
1112 * Fix up the length and compute the useful address.
1113 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001114 args->len = XFS_EXTLEN_MIN(ltlena, args->maxlen);
1115 xfs_alloc_fix_len(args);
1116 if (!xfs_alloc_fix_minleft(args)) {
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00001117 trace_xfs_alloc_near_nominleft(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001118 xfs_btree_del_cursor(bno_cur_lt, XFS_BTREE_NOERROR);
1119 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1120 return 0;
1121 }
1122 rlen = args->len;
Christoph Hellwige26f0502011-04-24 19:06:15 +00001123 (void)xfs_alloc_compute_diff(args->agbno, rlen, args->alignment,
1124 ltbnoa, ltlena, &ltnew);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001125 ASSERT(ltnew >= ltbno);
Christoph Hellwige26f0502011-04-24 19:06:15 +00001126 ASSERT(ltnew + rlen <= ltbnoa + ltlena);
Christoph Hellwig16259e72005-11-02 15:11:25 +11001127 ASSERT(ltnew + rlen <= be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001128 args->agbno = ltnew;
Christoph Hellwige26f0502011-04-24 19:06:15 +00001129
Linus Torvalds1da177e2005-04-16 15:20:36 -07001130 if ((error = xfs_alloc_fixup_trees(cnt_cur, bno_cur_lt, ltbno, ltlen,
1131 ltnew, rlen, XFSA_FIXUP_BNO_OK)))
1132 goto error0;
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00001133
1134 if (j)
1135 trace_xfs_alloc_near_greater(args);
1136 else
1137 trace_xfs_alloc_near_lesser(args);
1138
Linus Torvalds1da177e2005-04-16 15:20:36 -07001139 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1140 xfs_btree_del_cursor(bno_cur_lt, XFS_BTREE_NOERROR);
1141 return 0;
1142
1143 error0:
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00001144 trace_xfs_alloc_near_error(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001145 if (cnt_cur != NULL)
1146 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
1147 if (bno_cur_lt != NULL)
1148 xfs_btree_del_cursor(bno_cur_lt, XFS_BTREE_ERROR);
1149 if (bno_cur_gt != NULL)
1150 xfs_btree_del_cursor(bno_cur_gt, XFS_BTREE_ERROR);
1151 return error;
1152}
1153
1154/*
1155 * Allocate a variable extent anywhere in the allocation group agno.
1156 * Extent's length (returned in len) will be between minlen and maxlen,
1157 * and of the form k * prod + mod unless there's nothing that large.
1158 * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
1159 */
1160STATIC int /* error */
1161xfs_alloc_ag_vextent_size(
1162 xfs_alloc_arg_t *args) /* allocation argument structure */
1163{
1164 xfs_btree_cur_t *bno_cur; /* cursor for bno btree */
1165 xfs_btree_cur_t *cnt_cur; /* cursor for cnt btree */
1166 int error; /* error result */
1167 xfs_agblock_t fbno; /* start of found freespace */
1168 xfs_extlen_t flen; /* length of found freespace */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001169 int i; /* temp status variable */
1170 xfs_agblock_t rbno; /* returned block number */
1171 xfs_extlen_t rlen; /* length of returned extent */
Christoph Hellwige26f0502011-04-24 19:06:15 +00001172 int forced = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001173
Christoph Hellwige26f0502011-04-24 19:06:15 +00001174restart:
Linus Torvalds1da177e2005-04-16 15:20:36 -07001175 /*
1176 * Allocate and initialize a cursor for the by-size btree.
1177 */
Christoph Hellwig561f7d12008-10-30 16:53:59 +11001178 cnt_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
1179 args->agno, XFS_BTNUM_CNT);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001180 bno_cur = NULL;
Christoph Hellwige26f0502011-04-24 19:06:15 +00001181
Linus Torvalds1da177e2005-04-16 15:20:36 -07001182 /*
1183 * Look for an entry >= maxlen+alignment-1 blocks.
1184 */
1185 if ((error = xfs_alloc_lookup_ge(cnt_cur, 0,
1186 args->maxlen + args->alignment - 1, &i)))
1187 goto error0;
Christoph Hellwige26f0502011-04-24 19:06:15 +00001188
Linus Torvalds1da177e2005-04-16 15:20:36 -07001189 /*
Christoph Hellwige26f0502011-04-24 19:06:15 +00001190 * If none or we have busy extents that we cannot allocate from, then
1191 * we have to settle for a smaller extent. In the case that there are
1192 * no large extents, this will return the last entry in the tree unless
1193 * the tree is empty. In the case that there are only busy large
1194 * extents, this will return the largest small extent unless there
1195 * are no smaller extents available.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001196 */
Christoph Hellwige26f0502011-04-24 19:06:15 +00001197 if (!i || forced > 1) {
1198 error = xfs_alloc_ag_vextent_small(args, cnt_cur,
1199 &fbno, &flen, &i);
1200 if (error)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001201 goto error0;
1202 if (i == 0 || flen == 0) {
1203 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00001204 trace_xfs_alloc_size_noentry(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001205 return 0;
1206 }
1207 ASSERT(i == 1);
Christoph Hellwige26f0502011-04-24 19:06:15 +00001208 xfs_alloc_compute_aligned(args, fbno, flen, &rbno, &rlen);
1209 } else {
1210 /*
1211 * Search for a non-busy extent that is large enough.
1212 * If we are at low space, don't check, or if we fall of
1213 * the end of the btree, turn off the busy check and
1214 * restart.
1215 */
1216 for (;;) {
1217 error = xfs_alloc_get_rec(cnt_cur, &fbno, &flen, &i);
1218 if (error)
1219 goto error0;
1220 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1221
1222 xfs_alloc_compute_aligned(args, fbno, flen,
1223 &rbno, &rlen);
1224
1225 if (rlen >= args->maxlen)
1226 break;
1227
1228 error = xfs_btree_increment(cnt_cur, 0, &i);
1229 if (error)
1230 goto error0;
1231 if (i == 0) {
1232 /*
1233 * Our only valid extents must have been busy.
1234 * Make it unbusy by forcing the log out and
1235 * retrying. If we've been here before, forcing
1236 * the log isn't making the extents available,
1237 * which means they have probably been freed in
1238 * this transaction. In that case, we have to
1239 * give up on them and we'll attempt a minlen
1240 * allocation the next time around.
1241 */
1242 xfs_btree_del_cursor(cnt_cur,
1243 XFS_BTREE_NOERROR);
1244 trace_xfs_alloc_size_busy(args);
1245 if (!forced++)
1246 xfs_log_force(args->mp, XFS_LOG_SYNC);
1247 goto restart;
1248 }
1249 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001250 }
Christoph Hellwige26f0502011-04-24 19:06:15 +00001251
Linus Torvalds1da177e2005-04-16 15:20:36 -07001252 /*
1253 * In the first case above, we got the last entry in the
1254 * by-size btree. Now we check to see if the space hits maxlen
1255 * once aligned; if not, we search left for something better.
1256 * This can't happen in the second case above.
1257 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001258 rlen = XFS_EXTLEN_MIN(args->maxlen, rlen);
1259 XFS_WANT_CORRUPTED_GOTO(rlen == 0 ||
1260 (rlen <= flen && rbno + rlen <= fbno + flen), error0);
1261 if (rlen < args->maxlen) {
1262 xfs_agblock_t bestfbno;
1263 xfs_extlen_t bestflen;
1264 xfs_agblock_t bestrbno;
1265 xfs_extlen_t bestrlen;
1266
1267 bestrlen = rlen;
1268 bestrbno = rbno;
1269 bestflen = flen;
1270 bestfbno = fbno;
1271 for (;;) {
Christoph Hellwig8df4da42008-10-30 16:55:58 +11001272 if ((error = xfs_btree_decrement(cnt_cur, 0, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001273 goto error0;
1274 if (i == 0)
1275 break;
1276 if ((error = xfs_alloc_get_rec(cnt_cur, &fbno, &flen,
1277 &i)))
1278 goto error0;
1279 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1280 if (flen < bestrlen)
1281 break;
Christoph Hellwig86fa8af2011-03-04 12:59:54 +00001282 xfs_alloc_compute_aligned(args, fbno, flen,
1283 &rbno, &rlen);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001284 rlen = XFS_EXTLEN_MIN(args->maxlen, rlen);
1285 XFS_WANT_CORRUPTED_GOTO(rlen == 0 ||
1286 (rlen <= flen && rbno + rlen <= fbno + flen),
1287 error0);
1288 if (rlen > bestrlen) {
1289 bestrlen = rlen;
1290 bestrbno = rbno;
1291 bestflen = flen;
1292 bestfbno = fbno;
1293 if (rlen == args->maxlen)
1294 break;
1295 }
1296 }
1297 if ((error = xfs_alloc_lookup_eq(cnt_cur, bestfbno, bestflen,
1298 &i)))
1299 goto error0;
1300 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1301 rlen = bestrlen;
1302 rbno = bestrbno;
1303 flen = bestflen;
1304 fbno = bestfbno;
1305 }
1306 args->wasfromfl = 0;
1307 /*
1308 * Fix up the length.
1309 */
1310 args->len = rlen;
Christoph Hellwige26f0502011-04-24 19:06:15 +00001311 if (rlen < args->minlen) {
1312 if (!forced++) {
1313 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1314 trace_xfs_alloc_size_busy(args);
1315 xfs_log_force(args->mp, XFS_LOG_SYNC);
1316 goto restart;
1317 }
1318 goto out_nominleft;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001319 }
Christoph Hellwige26f0502011-04-24 19:06:15 +00001320 xfs_alloc_fix_len(args);
1321
1322 if (!xfs_alloc_fix_minleft(args))
1323 goto out_nominleft;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001324 rlen = args->len;
1325 XFS_WANT_CORRUPTED_GOTO(rlen <= flen, error0);
1326 /*
1327 * Allocate and initialize a cursor for the by-block tree.
1328 */
Christoph Hellwig561f7d12008-10-30 16:53:59 +11001329 bno_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
1330 args->agno, XFS_BTNUM_BNO);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001331 if ((error = xfs_alloc_fixup_trees(cnt_cur, bno_cur, fbno, flen,
1332 rbno, rlen, XFSA_FIXUP_CNT_OK)))
1333 goto error0;
1334 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1335 xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
1336 cnt_cur = bno_cur = NULL;
1337 args->len = rlen;
1338 args->agbno = rbno;
1339 XFS_WANT_CORRUPTED_GOTO(
1340 args->agbno + args->len <=
Christoph Hellwig16259e72005-11-02 15:11:25 +11001341 be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length),
Linus Torvalds1da177e2005-04-16 15:20:36 -07001342 error0);
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00001343 trace_xfs_alloc_size_done(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001344 return 0;
1345
1346error0:
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00001347 trace_xfs_alloc_size_error(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001348 if (cnt_cur)
1349 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
1350 if (bno_cur)
1351 xfs_btree_del_cursor(bno_cur, XFS_BTREE_ERROR);
1352 return error;
Christoph Hellwige26f0502011-04-24 19:06:15 +00001353
1354out_nominleft:
1355 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1356 trace_xfs_alloc_size_nominleft(args);
1357 args->agbno = NULLAGBLOCK;
1358 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001359}
1360
1361/*
1362 * Deal with the case where only small freespaces remain.
1363 * Either return the contents of the last freespace record,
1364 * or allocate space from the freelist if there is nothing in the tree.
1365 */
1366STATIC int /* error */
1367xfs_alloc_ag_vextent_small(
1368 xfs_alloc_arg_t *args, /* allocation argument structure */
1369 xfs_btree_cur_t *ccur, /* by-size cursor */
1370 xfs_agblock_t *fbnop, /* result block number */
1371 xfs_extlen_t *flenp, /* result length */
1372 int *stat) /* status: 0-freelist, 1-normal/none */
1373{
1374 int error;
1375 xfs_agblock_t fbno;
1376 xfs_extlen_t flen;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001377 int i;
1378
Christoph Hellwig8df4da42008-10-30 16:55:58 +11001379 if ((error = xfs_btree_decrement(ccur, 0, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001380 goto error0;
1381 if (i) {
1382 if ((error = xfs_alloc_get_rec(ccur, &fbno, &flen, &i)))
1383 goto error0;
1384 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1385 }
1386 /*
1387 * Nothing in the btree, try the freelist. Make sure
1388 * to respect minleft even when pulling from the
1389 * freelist.
1390 */
1391 else if (args->minlen == 1 && args->alignment == 1 && !args->isfl &&
Christoph Hellwig16259e72005-11-02 15:11:25 +11001392 (be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_flcount)
1393 > args->minleft)) {
David Chinner92821e22007-05-24 15:26:31 +10001394 error = xfs_alloc_get_freelist(args->tp, args->agbp, &fbno, 0);
1395 if (error)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001396 goto error0;
1397 if (fbno != NULLAGBLOCK) {
Christoph Hellwig97d3ac72011-04-24 19:06:16 +00001398 xfs_alloc_busy_reuse(args->mp, args->agno, fbno, 1,
1399 args->userdata);
1400
Linus Torvalds1da177e2005-04-16 15:20:36 -07001401 if (args->userdata) {
1402 xfs_buf_t *bp;
1403
1404 bp = xfs_btree_get_bufs(args->mp, args->tp,
1405 args->agno, fbno, 0);
1406 xfs_trans_binval(args->tp, bp);
1407 }
1408 args->len = 1;
1409 args->agbno = fbno;
1410 XFS_WANT_CORRUPTED_GOTO(
1411 args->agbno + args->len <=
Christoph Hellwig16259e72005-11-02 15:11:25 +11001412 be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length),
Linus Torvalds1da177e2005-04-16 15:20:36 -07001413 error0);
1414 args->wasfromfl = 1;
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00001415 trace_xfs_alloc_small_freelist(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001416 *stat = 0;
1417 return 0;
1418 }
1419 /*
1420 * Nothing in the freelist.
1421 */
1422 else
1423 flen = 0;
1424 }
1425 /*
1426 * Can't allocate from the freelist for some reason.
1427 */
Nathan Scottd432c802006-09-28 11:03:44 +10001428 else {
1429 fbno = NULLAGBLOCK;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001430 flen = 0;
Nathan Scottd432c802006-09-28 11:03:44 +10001431 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001432 /*
1433 * Can't do the allocation, give up.
1434 */
1435 if (flen < args->minlen) {
1436 args->agbno = NULLAGBLOCK;
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00001437 trace_xfs_alloc_small_notenough(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001438 flen = 0;
1439 }
1440 *fbnop = fbno;
1441 *flenp = flen;
1442 *stat = 1;
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00001443 trace_xfs_alloc_small_done(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001444 return 0;
1445
1446error0:
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00001447 trace_xfs_alloc_small_error(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001448 return error;
1449}
1450
1451/*
1452 * Free the extent starting at agno/bno for length.
1453 */
1454STATIC int /* error */
1455xfs_free_ag_extent(
1456 xfs_trans_t *tp, /* transaction pointer */
1457 xfs_buf_t *agbp, /* buffer for a.g. freelist header */
1458 xfs_agnumber_t agno, /* allocation group number */
1459 xfs_agblock_t bno, /* starting block number */
1460 xfs_extlen_t len, /* length of extent */
1461 int isfl) /* set if is freelist blocks - no sb acctg */
1462{
1463 xfs_btree_cur_t *bno_cur; /* cursor for by-block btree */
1464 xfs_btree_cur_t *cnt_cur; /* cursor for by-size btree */
1465 int error; /* error return value */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001466 xfs_agblock_t gtbno; /* start of right neighbor block */
1467 xfs_extlen_t gtlen; /* length of right neighbor block */
1468 int haveleft; /* have a left neighbor block */
1469 int haveright; /* have a right neighbor block */
1470 int i; /* temp, result code */
1471 xfs_agblock_t ltbno; /* start of left neighbor block */
1472 xfs_extlen_t ltlen; /* length of left neighbor block */
1473 xfs_mount_t *mp; /* mount point struct for filesystem */
1474 xfs_agblock_t nbno; /* new starting block of freespace */
1475 xfs_extlen_t nlen; /* new length of freespace */
Christoph Hellwigecb69282011-03-04 12:59:55 +00001476 xfs_perag_t *pag; /* per allocation group data */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001477
1478 mp = tp->t_mountp;
1479 /*
1480 * Allocate and initialize a cursor for the by-block btree.
1481 */
Christoph Hellwig561f7d12008-10-30 16:53:59 +11001482 bno_cur = xfs_allocbt_init_cursor(mp, tp, agbp, agno, XFS_BTNUM_BNO);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001483 cnt_cur = NULL;
1484 /*
1485 * Look for a neighboring block on the left (lower block numbers)
1486 * that is contiguous with this space.
1487 */
1488 if ((error = xfs_alloc_lookup_le(bno_cur, bno, len, &haveleft)))
1489 goto error0;
1490 if (haveleft) {
1491 /*
1492 * There is a block to our left.
1493 */
1494 if ((error = xfs_alloc_get_rec(bno_cur, &ltbno, &ltlen, &i)))
1495 goto error0;
1496 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1497 /*
1498 * It's not contiguous, though.
1499 */
1500 if (ltbno + ltlen < bno)
1501 haveleft = 0;
1502 else {
1503 /*
1504 * If this failure happens the request to free this
1505 * space was invalid, it's (partly) already free.
1506 * Very bad.
1507 */
1508 XFS_WANT_CORRUPTED_GOTO(ltbno + ltlen <= bno, error0);
1509 }
1510 }
1511 /*
1512 * Look for a neighboring block on the right (higher block numbers)
1513 * that is contiguous with this space.
1514 */
Christoph Hellwig637aa502008-10-30 16:55:45 +11001515 if ((error = xfs_btree_increment(bno_cur, 0, &haveright)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001516 goto error0;
1517 if (haveright) {
1518 /*
1519 * There is a block to our right.
1520 */
1521 if ((error = xfs_alloc_get_rec(bno_cur, &gtbno, &gtlen, &i)))
1522 goto error0;
1523 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1524 /*
1525 * It's not contiguous, though.
1526 */
1527 if (bno + len < gtbno)
1528 haveright = 0;
1529 else {
1530 /*
1531 * If this failure happens the request to free this
1532 * space was invalid, it's (partly) already free.
1533 * Very bad.
1534 */
1535 XFS_WANT_CORRUPTED_GOTO(gtbno >= bno + len, error0);
1536 }
1537 }
1538 /*
1539 * Now allocate and initialize a cursor for the by-size tree.
1540 */
Christoph Hellwig561f7d12008-10-30 16:53:59 +11001541 cnt_cur = xfs_allocbt_init_cursor(mp, tp, agbp, agno, XFS_BTNUM_CNT);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001542 /*
1543 * Have both left and right contiguous neighbors.
1544 * Merge all three into a single free block.
1545 */
1546 if (haveleft && haveright) {
1547 /*
1548 * Delete the old by-size entry on the left.
1549 */
1550 if ((error = xfs_alloc_lookup_eq(cnt_cur, ltbno, ltlen, &i)))
1551 goto error0;
1552 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
Christoph Hellwig91cca5d2008-10-30 16:58:01 +11001553 if ((error = xfs_btree_delete(cnt_cur, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001554 goto error0;
1555 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1556 /*
1557 * Delete the old by-size entry on the right.
1558 */
1559 if ((error = xfs_alloc_lookup_eq(cnt_cur, gtbno, gtlen, &i)))
1560 goto error0;
1561 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
Christoph Hellwig91cca5d2008-10-30 16:58:01 +11001562 if ((error = xfs_btree_delete(cnt_cur, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001563 goto error0;
1564 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1565 /*
1566 * Delete the old by-block entry for the right block.
1567 */
Christoph Hellwig91cca5d2008-10-30 16:58:01 +11001568 if ((error = xfs_btree_delete(bno_cur, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001569 goto error0;
1570 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1571 /*
1572 * Move the by-block cursor back to the left neighbor.
1573 */
Christoph Hellwig8df4da42008-10-30 16:55:58 +11001574 if ((error = xfs_btree_decrement(bno_cur, 0, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001575 goto error0;
1576 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1577#ifdef DEBUG
1578 /*
1579 * Check that this is the right record: delete didn't
1580 * mangle the cursor.
1581 */
1582 {
1583 xfs_agblock_t xxbno;
1584 xfs_extlen_t xxlen;
1585
1586 if ((error = xfs_alloc_get_rec(bno_cur, &xxbno, &xxlen,
1587 &i)))
1588 goto error0;
1589 XFS_WANT_CORRUPTED_GOTO(
1590 i == 1 && xxbno == ltbno && xxlen == ltlen,
1591 error0);
1592 }
1593#endif
1594 /*
1595 * Update remaining by-block entry to the new, joined block.
1596 */
1597 nbno = ltbno;
1598 nlen = len + ltlen + gtlen;
1599 if ((error = xfs_alloc_update(bno_cur, nbno, nlen)))
1600 goto error0;
1601 }
1602 /*
1603 * Have only a left contiguous neighbor.
1604 * Merge it together with the new freespace.
1605 */
1606 else if (haveleft) {
1607 /*
1608 * Delete the old by-size entry on the left.
1609 */
1610 if ((error = xfs_alloc_lookup_eq(cnt_cur, ltbno, ltlen, &i)))
1611 goto error0;
1612 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
Christoph Hellwig91cca5d2008-10-30 16:58:01 +11001613 if ((error = xfs_btree_delete(cnt_cur, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001614 goto error0;
1615 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1616 /*
1617 * Back up the by-block cursor to the left neighbor, and
1618 * update its length.
1619 */
Christoph Hellwig8df4da42008-10-30 16:55:58 +11001620 if ((error = xfs_btree_decrement(bno_cur, 0, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001621 goto error0;
1622 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1623 nbno = ltbno;
1624 nlen = len + ltlen;
1625 if ((error = xfs_alloc_update(bno_cur, nbno, nlen)))
1626 goto error0;
1627 }
1628 /*
1629 * Have only a right contiguous neighbor.
1630 * Merge it together with the new freespace.
1631 */
1632 else if (haveright) {
1633 /*
1634 * Delete the old by-size entry on the right.
1635 */
1636 if ((error = xfs_alloc_lookup_eq(cnt_cur, gtbno, gtlen, &i)))
1637 goto error0;
1638 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
Christoph Hellwig91cca5d2008-10-30 16:58:01 +11001639 if ((error = xfs_btree_delete(cnt_cur, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001640 goto error0;
1641 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1642 /*
1643 * Update the starting block and length of the right
1644 * neighbor in the by-block tree.
1645 */
1646 nbno = bno;
1647 nlen = len + gtlen;
1648 if ((error = xfs_alloc_update(bno_cur, nbno, nlen)))
1649 goto error0;
1650 }
1651 /*
1652 * No contiguous neighbors.
1653 * Insert the new freespace into the by-block tree.
1654 */
1655 else {
1656 nbno = bno;
1657 nlen = len;
Christoph Hellwig4b22a572008-10-30 16:57:40 +11001658 if ((error = xfs_btree_insert(bno_cur, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001659 goto error0;
1660 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1661 }
1662 xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
1663 bno_cur = NULL;
1664 /*
1665 * In all cases we need to insert the new freespace in the by-size tree.
1666 */
1667 if ((error = xfs_alloc_lookup_eq(cnt_cur, nbno, nlen, &i)))
1668 goto error0;
1669 XFS_WANT_CORRUPTED_GOTO(i == 0, error0);
Christoph Hellwig4b22a572008-10-30 16:57:40 +11001670 if ((error = xfs_btree_insert(cnt_cur, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001671 goto error0;
1672 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1673 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1674 cnt_cur = NULL;
Christoph Hellwigecb69282011-03-04 12:59:55 +00001675
Linus Torvalds1da177e2005-04-16 15:20:36 -07001676 /*
1677 * Update the freespace totals in the ag and superblock.
1678 */
Christoph Hellwigecb69282011-03-04 12:59:55 +00001679 pag = xfs_perag_get(mp, agno);
1680 error = xfs_alloc_update_counters(tp, pag, agbp, len);
1681 xfs_perag_put(pag);
1682 if (error)
1683 goto error0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001684
Christoph Hellwigecb69282011-03-04 12:59:55 +00001685 if (!isfl)
1686 xfs_trans_mod_sb(tp, XFS_TRANS_SB_FDBLOCKS, (long)len);
1687 XFS_STATS_INC(xs_freex);
1688 XFS_STATS_ADD(xs_freeb, len);
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00001689
1690 trace_xfs_free_extent(mp, agno, bno, len, isfl, haveleft, haveright);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001691
Linus Torvalds1da177e2005-04-16 15:20:36 -07001692 return 0;
1693
1694 error0:
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00001695 trace_xfs_free_extent(mp, agno, bno, len, isfl, -1, -1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001696 if (bno_cur)
1697 xfs_btree_del_cursor(bno_cur, XFS_BTREE_ERROR);
1698 if (cnt_cur)
1699 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
1700 return error;
1701}
1702
1703/*
1704 * Visible (exported) allocation/free functions.
1705 * Some of these are used just by xfs_alloc_btree.c and this file.
1706 */
1707
1708/*
1709 * Compute and fill in value of m_ag_maxlevels.
1710 */
1711void
1712xfs_alloc_compute_maxlevels(
1713 xfs_mount_t *mp) /* file system mount structure */
1714{
1715 int level;
1716 uint maxblocks;
1717 uint maxleafents;
1718 int minleafrecs;
1719 int minnoderecs;
1720
1721 maxleafents = (mp->m_sb.sb_agblocks + 1) / 2;
1722 minleafrecs = mp->m_alloc_mnr[0];
1723 minnoderecs = mp->m_alloc_mnr[1];
1724 maxblocks = (maxleafents + minleafrecs - 1) / minleafrecs;
1725 for (level = 1; maxblocks > 1; level++)
1726 maxblocks = (maxblocks + minnoderecs - 1) / minnoderecs;
1727 mp->m_ag_maxlevels = level;
1728}
1729
1730/*
Dave Chinner6cc87642009-03-16 08:29:46 +01001731 * Find the length of the longest extent in an AG.
1732 */
1733xfs_extlen_t
1734xfs_alloc_longest_free_extent(
1735 struct xfs_mount *mp,
1736 struct xfs_perag *pag)
1737{
1738 xfs_extlen_t need, delta = 0;
1739
1740 need = XFS_MIN_FREELIST_PAG(pag, mp);
1741 if (need > pag->pagf_flcount)
1742 delta = need - pag->pagf_flcount;
1743
1744 if (pag->pagf_longest > delta)
1745 return pag->pagf_longest - delta;
1746 return pag->pagf_flcount > 0 || pag->pagf_longest > 0;
1747}
1748
1749/*
Linus Torvalds1da177e2005-04-16 15:20:36 -07001750 * Decide whether to use this allocation group for this allocation.
1751 * If so, fix up the btree freelist's size.
1752 */
1753STATIC int /* error */
1754xfs_alloc_fix_freelist(
1755 xfs_alloc_arg_t *args, /* allocation argument structure */
1756 int flags) /* XFS_ALLOC_FLAG_... */
1757{
1758 xfs_buf_t *agbp; /* agf buffer pointer */
1759 xfs_agf_t *agf; /* a.g. freespace structure pointer */
1760 xfs_buf_t *agflbp;/* agfl buffer pointer */
1761 xfs_agblock_t bno; /* freelist block */
1762 xfs_extlen_t delta; /* new blocks needed in freelist */
1763 int error; /* error result code */
1764 xfs_extlen_t longest;/* longest extent in allocation group */
1765 xfs_mount_t *mp; /* file system mount point structure */
1766 xfs_extlen_t need; /* total blocks needed in freelist */
1767 xfs_perag_t *pag; /* per-ag information structure */
1768 xfs_alloc_arg_t targs; /* local allocation arguments */
1769 xfs_trans_t *tp; /* transaction pointer */
1770
1771 mp = args->mp;
1772
1773 pag = args->pag;
1774 tp = args->tp;
1775 if (!pag->pagf_init) {
1776 if ((error = xfs_alloc_read_agf(mp, tp, args->agno, flags,
1777 &agbp)))
1778 return error;
1779 if (!pag->pagf_init) {
Nathan Scott0e1edbd2006-08-10 14:40:41 +10001780 ASSERT(flags & XFS_ALLOC_FLAG_TRYLOCK);
1781 ASSERT(!(flags & XFS_ALLOC_FLAG_FREEING));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001782 args->agbp = NULL;
1783 return 0;
1784 }
1785 } else
1786 agbp = NULL;
1787
Nathan Scott0e1edbd2006-08-10 14:40:41 +10001788 /*
1789 * If this is a metadata preferred pag and we are user data
Linus Torvalds1da177e2005-04-16 15:20:36 -07001790 * then try somewhere else if we are not being asked to
1791 * try harder at this point
1792 */
Nathan Scott0e1edbd2006-08-10 14:40:41 +10001793 if (pag->pagf_metadata && args->userdata &&
1794 (flags & XFS_ALLOC_FLAG_TRYLOCK)) {
1795 ASSERT(!(flags & XFS_ALLOC_FLAG_FREEING));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001796 args->agbp = NULL;
1797 return 0;
1798 }
1799
Nathan Scott0e1edbd2006-08-10 14:40:41 +10001800 if (!(flags & XFS_ALLOC_FLAG_FREEING)) {
Nathan Scott0e1edbd2006-08-10 14:40:41 +10001801 /*
1802 * If it looks like there isn't a long enough extent, or enough
1803 * total blocks, reject it.
1804 */
Dave Chinner6cc87642009-03-16 08:29:46 +01001805 need = XFS_MIN_FREELIST_PAG(pag, mp);
1806 longest = xfs_alloc_longest_free_extent(mp, pag);
Nathan Scott0e1edbd2006-08-10 14:40:41 +10001807 if ((args->minlen + args->alignment + args->minalignslop - 1) >
1808 longest ||
1809 ((int)(pag->pagf_freeblks + pag->pagf_flcount -
1810 need - args->total) < (int)args->minleft)) {
1811 if (agbp)
1812 xfs_trans_brelse(tp, agbp);
1813 args->agbp = NULL;
1814 return 0;
1815 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001816 }
Nathan Scott0e1edbd2006-08-10 14:40:41 +10001817
Linus Torvalds1da177e2005-04-16 15:20:36 -07001818 /*
1819 * Get the a.g. freespace buffer.
1820 * Can fail if we're not blocking on locks, and it's held.
1821 */
1822 if (agbp == NULL) {
1823 if ((error = xfs_alloc_read_agf(mp, tp, args->agno, flags,
1824 &agbp)))
1825 return error;
1826 if (agbp == NULL) {
Nathan Scott0e1edbd2006-08-10 14:40:41 +10001827 ASSERT(flags & XFS_ALLOC_FLAG_TRYLOCK);
1828 ASSERT(!(flags & XFS_ALLOC_FLAG_FREEING));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001829 args->agbp = NULL;
1830 return 0;
1831 }
1832 }
1833 /*
1834 * Figure out how many blocks we should have in the freelist.
1835 */
1836 agf = XFS_BUF_TO_AGF(agbp);
1837 need = XFS_MIN_FREELIST(agf, mp);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001838 /*
1839 * If there isn't enough total or single-extent, reject it.
1840 */
Nathan Scott0e1edbd2006-08-10 14:40:41 +10001841 if (!(flags & XFS_ALLOC_FLAG_FREEING)) {
1842 delta = need > be32_to_cpu(agf->agf_flcount) ?
1843 (need - be32_to_cpu(agf->agf_flcount)) : 0;
1844 longest = be32_to_cpu(agf->agf_longest);
1845 longest = (longest > delta) ? (longest - delta) :
1846 (be32_to_cpu(agf->agf_flcount) > 0 || longest > 0);
1847 if ((args->minlen + args->alignment + args->minalignslop - 1) >
1848 longest ||
1849 ((int)(be32_to_cpu(agf->agf_freeblks) +
1850 be32_to_cpu(agf->agf_flcount) - need - args->total) <
1851 (int)args->minleft)) {
1852 xfs_trans_brelse(tp, agbp);
1853 args->agbp = NULL;
1854 return 0;
1855 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001856 }
1857 /*
1858 * Make the freelist shorter if it's too long.
1859 */
Christoph Hellwig16259e72005-11-02 15:11:25 +11001860 while (be32_to_cpu(agf->agf_flcount) > need) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001861 xfs_buf_t *bp;
1862
David Chinner92821e22007-05-24 15:26:31 +10001863 error = xfs_alloc_get_freelist(tp, agbp, &bno, 0);
1864 if (error)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001865 return error;
1866 if ((error = xfs_free_ag_extent(tp, agbp, args->agno, bno, 1, 1)))
1867 return error;
1868 bp = xfs_btree_get_bufs(mp, tp, args->agno, bno, 0);
1869 xfs_trans_binval(tp, bp);
1870 }
1871 /*
1872 * Initialize the args structure.
1873 */
1874 targs.tp = tp;
1875 targs.mp = mp;
1876 targs.agbp = agbp;
1877 targs.agno = args->agno;
1878 targs.mod = targs.minleft = targs.wasdel = targs.userdata =
1879 targs.minalignslop = 0;
1880 targs.alignment = targs.minlen = targs.prod = targs.isfl = 1;
1881 targs.type = XFS_ALLOCTYPE_THIS_AG;
1882 targs.pag = pag;
1883 if ((error = xfs_alloc_read_agfl(mp, tp, targs.agno, &agflbp)))
1884 return error;
1885 /*
1886 * Make the freelist longer if it's too short.
1887 */
Christoph Hellwig16259e72005-11-02 15:11:25 +11001888 while (be32_to_cpu(agf->agf_flcount) < need) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001889 targs.agbno = 0;
Christoph Hellwig16259e72005-11-02 15:11:25 +11001890 targs.maxlen = need - be32_to_cpu(agf->agf_flcount);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001891 /*
1892 * Allocate as many blocks as possible at once.
1893 */
Nathan Scotte63a3692006-05-08 19:51:58 +10001894 if ((error = xfs_alloc_ag_vextent(&targs))) {
1895 xfs_trans_brelse(tp, agflbp);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001896 return error;
Nathan Scotte63a3692006-05-08 19:51:58 +10001897 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001898 /*
1899 * Stop if we run out. Won't happen if callers are obeying
1900 * the restrictions correctly. Can happen for free calls
1901 * on a completely full ag.
1902 */
Yingping Lud210a282006-06-09 14:55:18 +10001903 if (targs.agbno == NULLAGBLOCK) {
Nathan Scott0e1edbd2006-08-10 14:40:41 +10001904 if (flags & XFS_ALLOC_FLAG_FREEING)
1905 break;
1906 xfs_trans_brelse(tp, agflbp);
1907 args->agbp = NULL;
1908 return 0;
Yingping Lud210a282006-06-09 14:55:18 +10001909 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001910 /*
1911 * Put each allocated block on the list.
1912 */
1913 for (bno = targs.agbno; bno < targs.agbno + targs.len; bno++) {
David Chinner92821e22007-05-24 15:26:31 +10001914 error = xfs_alloc_put_freelist(tp, agbp,
1915 agflbp, bno, 0);
1916 if (error)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001917 return error;
1918 }
1919 }
Nathan Scotte63a3692006-05-08 19:51:58 +10001920 xfs_trans_brelse(tp, agflbp);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001921 args->agbp = agbp;
1922 return 0;
1923}
1924
1925/*
1926 * Get a block from the freelist.
1927 * Returns with the buffer for the block gotten.
1928 */
1929int /* error */
1930xfs_alloc_get_freelist(
1931 xfs_trans_t *tp, /* transaction pointer */
1932 xfs_buf_t *agbp, /* buffer containing the agf structure */
David Chinner92821e22007-05-24 15:26:31 +10001933 xfs_agblock_t *bnop, /* block address retrieved from freelist */
1934 int btreeblk) /* destination is a AGF btree */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001935{
1936 xfs_agf_t *agf; /* a.g. freespace structure */
1937 xfs_agfl_t *agfl; /* a.g. freelist structure */
1938 xfs_buf_t *agflbp;/* buffer for a.g. freelist structure */
1939 xfs_agblock_t bno; /* block number returned */
1940 int error;
David Chinner92821e22007-05-24 15:26:31 +10001941 int logflags;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001942 xfs_mount_t *mp; /* mount structure */
1943 xfs_perag_t *pag; /* per allocation group data */
1944
1945 agf = XFS_BUF_TO_AGF(agbp);
1946 /*
1947 * Freelist is empty, give up.
1948 */
1949 if (!agf->agf_flcount) {
1950 *bnop = NULLAGBLOCK;
1951 return 0;
1952 }
1953 /*
1954 * Read the array of free blocks.
1955 */
1956 mp = tp->t_mountp;
1957 if ((error = xfs_alloc_read_agfl(mp, tp,
Christoph Hellwig16259e72005-11-02 15:11:25 +11001958 be32_to_cpu(agf->agf_seqno), &agflbp)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001959 return error;
1960 agfl = XFS_BUF_TO_AGFL(agflbp);
1961 /*
1962 * Get the block number and update the data structures.
1963 */
Christoph Hellwige2101002006-09-28 10:56:51 +10001964 bno = be32_to_cpu(agfl->agfl_bno[be32_to_cpu(agf->agf_flfirst)]);
Marcin Slusarz413d57c2008-02-13 15:03:29 -08001965 be32_add_cpu(&agf->agf_flfirst, 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001966 xfs_trans_brelse(tp, agflbp);
Christoph Hellwig16259e72005-11-02 15:11:25 +11001967 if (be32_to_cpu(agf->agf_flfirst) == XFS_AGFL_SIZE(mp))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001968 agf->agf_flfirst = 0;
Dave Chinnera862e0f2010-01-11 11:47:41 +00001969
1970 pag = xfs_perag_get(mp, be32_to_cpu(agf->agf_seqno));
Marcin Slusarz413d57c2008-02-13 15:03:29 -08001971 be32_add_cpu(&agf->agf_flcount, -1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001972 xfs_trans_agflist_delta(tp, -1);
1973 pag->pagf_flcount--;
Dave Chinnera862e0f2010-01-11 11:47:41 +00001974 xfs_perag_put(pag);
David Chinner92821e22007-05-24 15:26:31 +10001975
1976 logflags = XFS_AGF_FLFIRST | XFS_AGF_FLCOUNT;
1977 if (btreeblk) {
Marcin Slusarz413d57c2008-02-13 15:03:29 -08001978 be32_add_cpu(&agf->agf_btreeblks, 1);
David Chinner92821e22007-05-24 15:26:31 +10001979 pag->pagf_btreeblks++;
1980 logflags |= XFS_AGF_BTREEBLKS;
1981 }
1982
David Chinner92821e22007-05-24 15:26:31 +10001983 xfs_alloc_log_agf(tp, agbp, logflags);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001984 *bnop = bno;
1985
Linus Torvalds1da177e2005-04-16 15:20:36 -07001986 return 0;
1987}
1988
1989/*
1990 * Log the given fields from the agf structure.
1991 */
1992void
1993xfs_alloc_log_agf(
1994 xfs_trans_t *tp, /* transaction pointer */
1995 xfs_buf_t *bp, /* buffer for a.g. freelist header */
1996 int fields) /* mask of fields to be logged (XFS_AGF_...) */
1997{
1998 int first; /* first byte offset */
1999 int last; /* last byte offset */
2000 static const short offsets[] = {
2001 offsetof(xfs_agf_t, agf_magicnum),
2002 offsetof(xfs_agf_t, agf_versionnum),
2003 offsetof(xfs_agf_t, agf_seqno),
2004 offsetof(xfs_agf_t, agf_length),
2005 offsetof(xfs_agf_t, agf_roots[0]),
2006 offsetof(xfs_agf_t, agf_levels[0]),
2007 offsetof(xfs_agf_t, agf_flfirst),
2008 offsetof(xfs_agf_t, agf_fllast),
2009 offsetof(xfs_agf_t, agf_flcount),
2010 offsetof(xfs_agf_t, agf_freeblks),
2011 offsetof(xfs_agf_t, agf_longest),
David Chinner92821e22007-05-24 15:26:31 +10002012 offsetof(xfs_agf_t, agf_btreeblks),
Linus Torvalds1da177e2005-04-16 15:20:36 -07002013 sizeof(xfs_agf_t)
2014 };
2015
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00002016 trace_xfs_agf(tp->t_mountp, XFS_BUF_TO_AGF(bp), fields, _RET_IP_);
2017
Linus Torvalds1da177e2005-04-16 15:20:36 -07002018 xfs_btree_offsets(fields, offsets, XFS_AGF_NUM_BITS, &first, &last);
2019 xfs_trans_log_buf(tp, bp, (uint)first, (uint)last);
2020}
2021
2022/*
2023 * Interface for inode allocation to force the pag data to be initialized.
2024 */
2025int /* error */
2026xfs_alloc_pagf_init(
2027 xfs_mount_t *mp, /* file system mount structure */
2028 xfs_trans_t *tp, /* transaction pointer */
2029 xfs_agnumber_t agno, /* allocation group number */
2030 int flags) /* XFS_ALLOC_FLAGS_... */
2031{
2032 xfs_buf_t *bp;
2033 int error;
2034
2035 if ((error = xfs_alloc_read_agf(mp, tp, agno, flags, &bp)))
2036 return error;
2037 if (bp)
2038 xfs_trans_brelse(tp, bp);
2039 return 0;
2040}
2041
2042/*
2043 * Put the block on the freelist for the allocation group.
2044 */
2045int /* error */
2046xfs_alloc_put_freelist(
2047 xfs_trans_t *tp, /* transaction pointer */
2048 xfs_buf_t *agbp, /* buffer for a.g. freelist header */
2049 xfs_buf_t *agflbp,/* buffer for a.g. free block array */
David Chinner92821e22007-05-24 15:26:31 +10002050 xfs_agblock_t bno, /* block being freed */
2051 int btreeblk) /* block came from a AGF btree */
Linus Torvalds1da177e2005-04-16 15:20:36 -07002052{
2053 xfs_agf_t *agf; /* a.g. freespace structure */
2054 xfs_agfl_t *agfl; /* a.g. free block array */
Christoph Hellwige2101002006-09-28 10:56:51 +10002055 __be32 *blockp;/* pointer to array entry */
Linus Torvalds1da177e2005-04-16 15:20:36 -07002056 int error;
David Chinner92821e22007-05-24 15:26:31 +10002057 int logflags;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002058 xfs_mount_t *mp; /* mount structure */
2059 xfs_perag_t *pag; /* per allocation group data */
2060
2061 agf = XFS_BUF_TO_AGF(agbp);
2062 mp = tp->t_mountp;
2063
2064 if (!agflbp && (error = xfs_alloc_read_agfl(mp, tp,
Christoph Hellwig16259e72005-11-02 15:11:25 +11002065 be32_to_cpu(agf->agf_seqno), &agflbp)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07002066 return error;
2067 agfl = XFS_BUF_TO_AGFL(agflbp);
Marcin Slusarz413d57c2008-02-13 15:03:29 -08002068 be32_add_cpu(&agf->agf_fllast, 1);
Christoph Hellwig16259e72005-11-02 15:11:25 +11002069 if (be32_to_cpu(agf->agf_fllast) == XFS_AGFL_SIZE(mp))
Linus Torvalds1da177e2005-04-16 15:20:36 -07002070 agf->agf_fllast = 0;
Dave Chinnera862e0f2010-01-11 11:47:41 +00002071
2072 pag = xfs_perag_get(mp, be32_to_cpu(agf->agf_seqno));
Marcin Slusarz413d57c2008-02-13 15:03:29 -08002073 be32_add_cpu(&agf->agf_flcount, 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002074 xfs_trans_agflist_delta(tp, 1);
2075 pag->pagf_flcount++;
David Chinner92821e22007-05-24 15:26:31 +10002076
2077 logflags = XFS_AGF_FLLAST | XFS_AGF_FLCOUNT;
2078 if (btreeblk) {
Marcin Slusarz413d57c2008-02-13 15:03:29 -08002079 be32_add_cpu(&agf->agf_btreeblks, -1);
David Chinner92821e22007-05-24 15:26:31 +10002080 pag->pagf_btreeblks--;
2081 logflags |= XFS_AGF_BTREEBLKS;
2082 }
Dave Chinnera862e0f2010-01-11 11:47:41 +00002083 xfs_perag_put(pag);
David Chinner92821e22007-05-24 15:26:31 +10002084
David Chinner92821e22007-05-24 15:26:31 +10002085 xfs_alloc_log_agf(tp, agbp, logflags);
2086
Christoph Hellwig16259e72005-11-02 15:11:25 +11002087 ASSERT(be32_to_cpu(agf->agf_flcount) <= XFS_AGFL_SIZE(mp));
2088 blockp = &agfl->agfl_bno[be32_to_cpu(agf->agf_fllast)];
Christoph Hellwige2101002006-09-28 10:56:51 +10002089 *blockp = cpu_to_be32(bno);
David Chinner92821e22007-05-24 15:26:31 +10002090 xfs_alloc_log_agf(tp, agbp, logflags);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002091 xfs_trans_log_buf(tp, agflbp,
2092 (int)((xfs_caddr_t)blockp - (xfs_caddr_t)agfl),
2093 (int)((xfs_caddr_t)blockp - (xfs_caddr_t)agfl +
2094 sizeof(xfs_agblock_t) - 1));
2095 return 0;
2096}
2097
2098/*
2099 * Read in the allocation group header (free/alloc section).
2100 */
2101int /* error */
From: Christoph Hellwig48056212008-11-28 14:23:38 +11002102xfs_read_agf(
2103 struct xfs_mount *mp, /* mount point structure */
2104 struct xfs_trans *tp, /* transaction pointer */
2105 xfs_agnumber_t agno, /* allocation group number */
2106 int flags, /* XFS_BUF_ */
2107 struct xfs_buf **bpp) /* buffer for the ag freelist header */
Linus Torvalds1da177e2005-04-16 15:20:36 -07002108{
From: Christoph Hellwig48056212008-11-28 14:23:38 +11002109 struct xfs_agf *agf; /* ag freelist header */
Linus Torvalds1da177e2005-04-16 15:20:36 -07002110 int agf_ok; /* set if agf is consistent */
Linus Torvalds1da177e2005-04-16 15:20:36 -07002111 int error;
2112
2113 ASSERT(agno != NULLAGNUMBER);
2114 error = xfs_trans_read_buf(
2115 mp, tp, mp->m_ddev_targp,
2116 XFS_AG_DADDR(mp, agno, XFS_AGF_DADDR(mp)),
From: Christoph Hellwig48056212008-11-28 14:23:38 +11002117 XFS_FSS_TO_BB(mp, 1), flags, bpp);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002118 if (error)
2119 return error;
From: Christoph Hellwig48056212008-11-28 14:23:38 +11002120 if (!*bpp)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002121 return 0;
From: Christoph Hellwig48056212008-11-28 14:23:38 +11002122
2123 ASSERT(!XFS_BUF_GETERROR(*bpp));
2124 agf = XFS_BUF_TO_AGF(*bpp);
2125
Linus Torvalds1da177e2005-04-16 15:20:36 -07002126 /*
2127 * Validate the magic number of the agf block.
2128 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07002129 agf_ok =
Christoph Hellwig16259e72005-11-02 15:11:25 +11002130 be32_to_cpu(agf->agf_magicnum) == XFS_AGF_MAGIC &&
2131 XFS_AGF_GOOD_VERSION(be32_to_cpu(agf->agf_versionnum)) &&
2132 be32_to_cpu(agf->agf_freeblks) <= be32_to_cpu(agf->agf_length) &&
2133 be32_to_cpu(agf->agf_flfirst) < XFS_AGFL_SIZE(mp) &&
2134 be32_to_cpu(agf->agf_fllast) < XFS_AGFL_SIZE(mp) &&
From: Christoph Hellwig48056212008-11-28 14:23:38 +11002135 be32_to_cpu(agf->agf_flcount) <= XFS_AGFL_SIZE(mp) &&
2136 be32_to_cpu(agf->agf_seqno) == agno;
Barry Naujok89b28392008-10-30 17:05:49 +11002137 if (xfs_sb_version_haslazysbcount(&mp->m_sb))
2138 agf_ok = agf_ok && be32_to_cpu(agf->agf_btreeblks) <=
2139 be32_to_cpu(agf->agf_length);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002140 if (unlikely(XFS_TEST_ERROR(!agf_ok, mp, XFS_ERRTAG_ALLOC_READ_AGF,
2141 XFS_RANDOM_ALLOC_READ_AGF))) {
2142 XFS_CORRUPTION_ERROR("xfs_alloc_read_agf",
2143 XFS_ERRLEVEL_LOW, mp, agf);
From: Christoph Hellwig48056212008-11-28 14:23:38 +11002144 xfs_trans_brelse(tp, *bpp);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002145 return XFS_ERROR(EFSCORRUPTED);
2146 }
From: Christoph Hellwig48056212008-11-28 14:23:38 +11002147 XFS_BUF_SET_VTYPE_REF(*bpp, B_FS_AGF, XFS_AGF_REF);
2148 return 0;
2149}
2150
2151/*
2152 * Read in the allocation group header (free/alloc section).
2153 */
2154int /* error */
2155xfs_alloc_read_agf(
2156 struct xfs_mount *mp, /* mount point structure */
2157 struct xfs_trans *tp, /* transaction pointer */
2158 xfs_agnumber_t agno, /* allocation group number */
2159 int flags, /* XFS_ALLOC_FLAG_... */
2160 struct xfs_buf **bpp) /* buffer for the ag freelist header */
2161{
2162 struct xfs_agf *agf; /* ag freelist header */
2163 struct xfs_perag *pag; /* per allocation group data */
2164 int error;
2165
2166 ASSERT(agno != NULLAGNUMBER);
2167
2168 error = xfs_read_agf(mp, tp, agno,
Christoph Hellwig0cadda12010-01-19 09:56:44 +00002169 (flags & XFS_ALLOC_FLAG_TRYLOCK) ? XBF_TRYLOCK : 0,
From: Christoph Hellwig48056212008-11-28 14:23:38 +11002170 bpp);
2171 if (error)
2172 return error;
2173 if (!*bpp)
2174 return 0;
2175 ASSERT(!XFS_BUF_GETERROR(*bpp));
2176
2177 agf = XFS_BUF_TO_AGF(*bpp);
Dave Chinnera862e0f2010-01-11 11:47:41 +00002178 pag = xfs_perag_get(mp, agno);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002179 if (!pag->pagf_init) {
Christoph Hellwig16259e72005-11-02 15:11:25 +11002180 pag->pagf_freeblks = be32_to_cpu(agf->agf_freeblks);
David Chinner92821e22007-05-24 15:26:31 +10002181 pag->pagf_btreeblks = be32_to_cpu(agf->agf_btreeblks);
Christoph Hellwig16259e72005-11-02 15:11:25 +11002182 pag->pagf_flcount = be32_to_cpu(agf->agf_flcount);
2183 pag->pagf_longest = be32_to_cpu(agf->agf_longest);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002184 pag->pagf_levels[XFS_BTNUM_BNOi] =
Christoph Hellwig16259e72005-11-02 15:11:25 +11002185 be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNOi]);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002186 pag->pagf_levels[XFS_BTNUM_CNTi] =
Christoph Hellwig16259e72005-11-02 15:11:25 +11002187 be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNTi]);
Eric Sandeen007c61c2007-10-11 17:43:56 +10002188 spin_lock_init(&pag->pagb_lock);
Dave Chinnere57336f2010-01-11 11:47:49 +00002189 pag->pagb_count = 0;
Dave Chinnered3b4d62010-05-21 12:07:08 +10002190 pag->pagb_tree = RB_ROOT;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002191 pag->pagf_init = 1;
2192 }
2193#ifdef DEBUG
2194 else if (!XFS_FORCED_SHUTDOWN(mp)) {
Christoph Hellwig16259e72005-11-02 15:11:25 +11002195 ASSERT(pag->pagf_freeblks == be32_to_cpu(agf->agf_freeblks));
Barry Naujok89b28392008-10-30 17:05:49 +11002196 ASSERT(pag->pagf_btreeblks == be32_to_cpu(agf->agf_btreeblks));
Christoph Hellwig16259e72005-11-02 15:11:25 +11002197 ASSERT(pag->pagf_flcount == be32_to_cpu(agf->agf_flcount));
2198 ASSERT(pag->pagf_longest == be32_to_cpu(agf->agf_longest));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002199 ASSERT(pag->pagf_levels[XFS_BTNUM_BNOi] ==
Christoph Hellwig16259e72005-11-02 15:11:25 +11002200 be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNOi]));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002201 ASSERT(pag->pagf_levels[XFS_BTNUM_CNTi] ==
Christoph Hellwig16259e72005-11-02 15:11:25 +11002202 be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNTi]));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002203 }
2204#endif
Dave Chinnera862e0f2010-01-11 11:47:41 +00002205 xfs_perag_put(pag);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002206 return 0;
2207}
2208
2209/*
2210 * Allocate an extent (variable-size).
2211 * Depending on the allocation type, we either look in a single allocation
2212 * group or loop over the allocation groups to find the result.
2213 */
2214int /* error */
2215xfs_alloc_vextent(
2216 xfs_alloc_arg_t *args) /* allocation argument structure */
2217{
2218 xfs_agblock_t agsize; /* allocation group size */
2219 int error;
2220 int flags; /* XFS_ALLOC_FLAG_... locking flags */
Linus Torvalds1da177e2005-04-16 15:20:36 -07002221 xfs_extlen_t minleft;/* minimum left value, temp copy */
2222 xfs_mount_t *mp; /* mount structure pointer */
2223 xfs_agnumber_t sagno; /* starting allocation group number */
2224 xfs_alloctype_t type; /* input allocation type */
2225 int bump_rotor = 0;
2226 int no_min = 0;
2227 xfs_agnumber_t rotorstep = xfs_rotorstep; /* inode32 agf stepper */
2228
2229 mp = args->mp;
2230 type = args->otype = args->type;
2231 args->agbno = NULLAGBLOCK;
2232 /*
2233 * Just fix this up, for the case where the last a.g. is shorter
2234 * (or there's only one a.g.) and the caller couldn't easily figure
2235 * that out (xfs_bmap_alloc).
2236 */
2237 agsize = mp->m_sb.sb_agblocks;
2238 if (args->maxlen > agsize)
2239 args->maxlen = agsize;
2240 if (args->alignment == 0)
2241 args->alignment = 1;
2242 ASSERT(XFS_FSB_TO_AGNO(mp, args->fsbno) < mp->m_sb.sb_agcount);
2243 ASSERT(XFS_FSB_TO_AGBNO(mp, args->fsbno) < agsize);
2244 ASSERT(args->minlen <= args->maxlen);
2245 ASSERT(args->minlen <= agsize);
2246 ASSERT(args->mod < args->prod);
2247 if (XFS_FSB_TO_AGNO(mp, args->fsbno) >= mp->m_sb.sb_agcount ||
2248 XFS_FSB_TO_AGBNO(mp, args->fsbno) >= agsize ||
2249 args->minlen > args->maxlen || args->minlen > agsize ||
2250 args->mod >= args->prod) {
2251 args->fsbno = NULLFSBLOCK;
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00002252 trace_xfs_alloc_vextent_badargs(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002253 return 0;
2254 }
2255 minleft = args->minleft;
2256
2257 switch (type) {
2258 case XFS_ALLOCTYPE_THIS_AG:
2259 case XFS_ALLOCTYPE_NEAR_BNO:
2260 case XFS_ALLOCTYPE_THIS_BNO:
2261 /*
2262 * These three force us into a single a.g.
2263 */
2264 args->agno = XFS_FSB_TO_AGNO(mp, args->fsbno);
Dave Chinnera862e0f2010-01-11 11:47:41 +00002265 args->pag = xfs_perag_get(mp, args->agno);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002266 args->minleft = 0;
2267 error = xfs_alloc_fix_freelist(args, 0);
2268 args->minleft = minleft;
2269 if (error) {
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00002270 trace_xfs_alloc_vextent_nofix(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002271 goto error0;
2272 }
2273 if (!args->agbp) {
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00002274 trace_xfs_alloc_vextent_noagbp(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002275 break;
2276 }
2277 args->agbno = XFS_FSB_TO_AGBNO(mp, args->fsbno);
2278 if ((error = xfs_alloc_ag_vextent(args)))
2279 goto error0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002280 break;
2281 case XFS_ALLOCTYPE_START_BNO:
2282 /*
2283 * Try near allocation first, then anywhere-in-ag after
2284 * the first a.g. fails.
2285 */
2286 if ((args->userdata == XFS_ALLOC_INITIAL_USER_DATA) &&
2287 (mp->m_flags & XFS_MOUNT_32BITINODES)) {
2288 args->fsbno = XFS_AGB_TO_FSB(mp,
2289 ((mp->m_agfrotor / rotorstep) %
2290 mp->m_sb.sb_agcount), 0);
2291 bump_rotor = 1;
2292 }
2293 args->agbno = XFS_FSB_TO_AGBNO(mp, args->fsbno);
2294 args->type = XFS_ALLOCTYPE_NEAR_BNO;
2295 /* FALLTHROUGH */
2296 case XFS_ALLOCTYPE_ANY_AG:
2297 case XFS_ALLOCTYPE_START_AG:
2298 case XFS_ALLOCTYPE_FIRST_AG:
2299 /*
2300 * Rotate through the allocation groups looking for a winner.
2301 */
2302 if (type == XFS_ALLOCTYPE_ANY_AG) {
2303 /*
2304 * Start with the last place we left off.
2305 */
2306 args->agno = sagno = (mp->m_agfrotor / rotorstep) %
2307 mp->m_sb.sb_agcount;
2308 args->type = XFS_ALLOCTYPE_THIS_AG;
2309 flags = XFS_ALLOC_FLAG_TRYLOCK;
2310 } else if (type == XFS_ALLOCTYPE_FIRST_AG) {
2311 /*
2312 * Start with allocation group given by bno.
2313 */
2314 args->agno = XFS_FSB_TO_AGNO(mp, args->fsbno);
2315 args->type = XFS_ALLOCTYPE_THIS_AG;
2316 sagno = 0;
2317 flags = 0;
2318 } else {
2319 if (type == XFS_ALLOCTYPE_START_AG)
2320 args->type = XFS_ALLOCTYPE_THIS_AG;
2321 /*
2322 * Start with the given allocation group.
2323 */
2324 args->agno = sagno = XFS_FSB_TO_AGNO(mp, args->fsbno);
2325 flags = XFS_ALLOC_FLAG_TRYLOCK;
2326 }
2327 /*
2328 * Loop over allocation groups twice; first time with
2329 * trylock set, second time without.
2330 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07002331 for (;;) {
Dave Chinnera862e0f2010-01-11 11:47:41 +00002332 args->pag = xfs_perag_get(mp, args->agno);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002333 if (no_min) args->minleft = 0;
2334 error = xfs_alloc_fix_freelist(args, flags);
2335 args->minleft = minleft;
2336 if (error) {
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00002337 trace_xfs_alloc_vextent_nofix(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002338 goto error0;
2339 }
2340 /*
2341 * If we get a buffer back then the allocation will fly.
2342 */
2343 if (args->agbp) {
2344 if ((error = xfs_alloc_ag_vextent(args)))
2345 goto error0;
2346 break;
2347 }
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00002348
2349 trace_xfs_alloc_vextent_loopfailed(args);
2350
Linus Torvalds1da177e2005-04-16 15:20:36 -07002351 /*
2352 * Didn't work, figure out the next iteration.
2353 */
2354 if (args->agno == sagno &&
2355 type == XFS_ALLOCTYPE_START_BNO)
2356 args->type = XFS_ALLOCTYPE_THIS_AG;
Yingping Lud210a282006-06-09 14:55:18 +10002357 /*
2358 * For the first allocation, we can try any AG to get
2359 * space. However, if we already have allocated a
2360 * block, we don't want to try AGs whose number is below
2361 * sagno. Otherwise, we may end up with out-of-order
2362 * locking of AGF, which might cause deadlock.
2363 */
2364 if (++(args->agno) == mp->m_sb.sb_agcount) {
2365 if (args->firstblock != NULLFSBLOCK)
2366 args->agno = sagno;
2367 else
2368 args->agno = 0;
2369 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002370 /*
2371 * Reached the starting a.g., must either be done
2372 * or switch to non-trylock mode.
2373 */
2374 if (args->agno == sagno) {
2375 if (no_min == 1) {
2376 args->agbno = NULLAGBLOCK;
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00002377 trace_xfs_alloc_vextent_allfailed(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002378 break;
2379 }
2380 if (flags == 0) {
2381 no_min = 1;
2382 } else {
2383 flags = 0;
2384 if (type == XFS_ALLOCTYPE_START_BNO) {
2385 args->agbno = XFS_FSB_TO_AGBNO(mp,
2386 args->fsbno);
2387 args->type = XFS_ALLOCTYPE_NEAR_BNO;
2388 }
2389 }
2390 }
Dave Chinnera862e0f2010-01-11 11:47:41 +00002391 xfs_perag_put(args->pag);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002392 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002393 if (bump_rotor || (type == XFS_ALLOCTYPE_ANY_AG)) {
2394 if (args->agno == sagno)
2395 mp->m_agfrotor = (mp->m_agfrotor + 1) %
2396 (mp->m_sb.sb_agcount * rotorstep);
2397 else
2398 mp->m_agfrotor = (args->agno * rotorstep + 1) %
2399 (mp->m_sb.sb_agcount * rotorstep);
2400 }
2401 break;
2402 default:
2403 ASSERT(0);
2404 /* NOTREACHED */
2405 }
2406 if (args->agbno == NULLAGBLOCK)
2407 args->fsbno = NULLFSBLOCK;
2408 else {
2409 args->fsbno = XFS_AGB_TO_FSB(mp, args->agno, args->agbno);
2410#ifdef DEBUG
2411 ASSERT(args->len >= args->minlen);
2412 ASSERT(args->len <= args->maxlen);
2413 ASSERT(args->agbno % args->alignment == 0);
2414 XFS_AG_CHECK_DADDR(mp, XFS_FSB_TO_DADDR(mp, args->fsbno),
2415 args->len);
2416#endif
2417 }
Dave Chinnera862e0f2010-01-11 11:47:41 +00002418 xfs_perag_put(args->pag);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002419 return 0;
2420error0:
Dave Chinnera862e0f2010-01-11 11:47:41 +00002421 xfs_perag_put(args->pag);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002422 return error;
2423}
2424
2425/*
2426 * Free an extent.
2427 * Just break up the extent address and hand off to xfs_free_ag_extent
2428 * after fixing up the freelist.
2429 */
2430int /* error */
2431xfs_free_extent(
2432 xfs_trans_t *tp, /* transaction pointer */
2433 xfs_fsblock_t bno, /* starting block number of extent */
2434 xfs_extlen_t len) /* length of extent */
2435{
Nathan Scott0e1edbd2006-08-10 14:40:41 +10002436 xfs_alloc_arg_t args;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002437 int error;
2438
2439 ASSERT(len != 0);
Nathan Scott0e1edbd2006-08-10 14:40:41 +10002440 memset(&args, 0, sizeof(xfs_alloc_arg_t));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002441 args.tp = tp;
2442 args.mp = tp->t_mountp;
Dave Chinnerbe65b182011-04-08 12:45:07 +10002443
2444 /*
2445 * validate that the block number is legal - the enables us to detect
2446 * and handle a silent filesystem corruption rather than crashing.
2447 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07002448 args.agno = XFS_FSB_TO_AGNO(args.mp, bno);
Dave Chinnerbe65b182011-04-08 12:45:07 +10002449 if (args.agno >= args.mp->m_sb.sb_agcount)
2450 return EFSCORRUPTED;
2451
Linus Torvalds1da177e2005-04-16 15:20:36 -07002452 args.agbno = XFS_FSB_TO_AGBNO(args.mp, bno);
Dave Chinnerbe65b182011-04-08 12:45:07 +10002453 if (args.agbno >= args.mp->m_sb.sb_agblocks)
2454 return EFSCORRUPTED;
2455
Dave Chinnera862e0f2010-01-11 11:47:41 +00002456 args.pag = xfs_perag_get(args.mp, args.agno);
Dave Chinnerbe65b182011-04-08 12:45:07 +10002457 ASSERT(args.pag);
2458
2459 error = xfs_alloc_fix_freelist(&args, XFS_ALLOC_FLAG_FREEING);
2460 if (error)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002461 goto error0;
Dave Chinnerbe65b182011-04-08 12:45:07 +10002462
2463 /* validate the extent size is legal now we have the agf locked */
2464 if (args.agbno + len >
2465 be32_to_cpu(XFS_BUF_TO_AGF(args.agbp)->agf_length)) {
2466 error = EFSCORRUPTED;
2467 goto error0;
2468 }
2469
Nathan Scott0e1edbd2006-08-10 14:40:41 +10002470 error = xfs_free_ag_extent(tp, args.agbp, args.agno, args.agbno, len, 0);
Christoph Hellwiga870acd2011-04-24 19:06:14 +00002471 if (!error)
Christoph Hellwig55a7bc52011-05-04 18:55:15 +00002472 xfs_alloc_busy_insert(tp, args.agno, args.agbno, len, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002473error0:
Dave Chinnera862e0f2010-01-11 11:47:41 +00002474 xfs_perag_put(args.pag);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002475 return error;
2476}
2477
Linus Torvalds1da177e2005-04-16 15:20:36 -07002478void
Dave Chinnered3b4d62010-05-21 12:07:08 +10002479xfs_alloc_busy_insert(
2480 struct xfs_trans *tp,
2481 xfs_agnumber_t agno,
2482 xfs_agblock_t bno,
Christoph Hellwig55a7bc52011-05-04 18:55:15 +00002483 xfs_extlen_t len,
2484 unsigned int flags)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002485{
Dave Chinnered3b4d62010-05-21 12:07:08 +10002486 struct xfs_busy_extent *new;
2487 struct xfs_busy_extent *busyp;
Dave Chinnera862e0f2010-01-11 11:47:41 +00002488 struct xfs_perag *pag;
Dave Chinnered3b4d62010-05-21 12:07:08 +10002489 struct rb_node **rbp;
Christoph Hellwig97d3ac72011-04-24 19:06:16 +00002490 struct rb_node *parent = NULL;
Dave Chinnered3b4d62010-05-21 12:07:08 +10002491
2492 new = kmem_zalloc(sizeof(struct xfs_busy_extent), KM_MAYFAIL);
2493 if (!new) {
2494 /*
2495 * No Memory! Since it is now not possible to track the free
2496 * block, make this a synchronous transaction to insure that
2497 * the block is not reused before this transaction commits.
2498 */
Christoph Hellwig97d3ac72011-04-24 19:06:16 +00002499 trace_xfs_alloc_busy_enomem(tp->t_mountp, agno, bno, len);
Dave Chinnered3b4d62010-05-21 12:07:08 +10002500 xfs_trans_set_sync(tp);
2501 return;
2502 }
2503
2504 new->agno = agno;
2505 new->bno = bno;
2506 new->length = len;
Dave Chinnered3b4d62010-05-21 12:07:08 +10002507 INIT_LIST_HEAD(&new->list);
Christoph Hellwig55a7bc52011-05-04 18:55:15 +00002508 new->flags = flags;
Dave Chinnered3b4d62010-05-21 12:07:08 +10002509
2510 /* trace before insert to be able to see failed inserts */
Christoph Hellwig97d3ac72011-04-24 19:06:16 +00002511 trace_xfs_alloc_busy(tp->t_mountp, agno, bno, len);
Dave Chinnered3b4d62010-05-21 12:07:08 +10002512
2513 pag = xfs_perag_get(tp->t_mountp, new->agno);
Dave Chinnera862e0f2010-01-11 11:47:41 +00002514 spin_lock(&pag->pagb_lock);
Dave Chinnered3b4d62010-05-21 12:07:08 +10002515 rbp = &pag->pagb_tree.rb_node;
Christoph Hellwig97d3ac72011-04-24 19:06:16 +00002516 while (*rbp) {
Dave Chinnered3b4d62010-05-21 12:07:08 +10002517 parent = *rbp;
2518 busyp = rb_entry(parent, struct xfs_busy_extent, rb_node);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002519
Dave Chinnered3b4d62010-05-21 12:07:08 +10002520 if (new->bno < busyp->bno) {
Dave Chinnered3b4d62010-05-21 12:07:08 +10002521 rbp = &(*rbp)->rb_left;
Christoph Hellwig97d3ac72011-04-24 19:06:16 +00002522 ASSERT(new->bno + new->length <= busyp->bno);
Dave Chinnered3b4d62010-05-21 12:07:08 +10002523 } else if (new->bno > busyp->bno) {
Dave Chinnered3b4d62010-05-21 12:07:08 +10002524 rbp = &(*rbp)->rb_right;
Christoph Hellwig97d3ac72011-04-24 19:06:16 +00002525 ASSERT(bno >= busyp->bno + busyp->length);
Dave Chinnered3b4d62010-05-21 12:07:08 +10002526 } else {
Christoph Hellwig97d3ac72011-04-24 19:06:16 +00002527 ASSERT(0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002528 }
2529 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002530
Dave Chinnered3b4d62010-05-21 12:07:08 +10002531 rb_link_node(&new->rb_node, parent, rbp);
2532 rb_insert_color(&new->rb_node, &pag->pagb_tree);
2533
2534 list_add(&new->list, &tp->t_busy);
Dave Chinnera862e0f2010-01-11 11:47:41 +00002535 spin_unlock(&pag->pagb_lock);
2536 xfs_perag_put(pag);
Dave Chinnered3b4d62010-05-21 12:07:08 +10002537}
2538
2539/*
2540 * Search for a busy extent within the range of the extent we are about to
2541 * allocate. You need to be holding the busy extent tree lock when calling
2542 * xfs_alloc_busy_search(). This function returns 0 for no overlapping busy
2543 * extent, -1 for an overlapping but not exact busy extent, and 1 for an exact
2544 * match. This is done so that a non-zero return indicates an overlap that
2545 * will require a synchronous transaction, but it can still be
2546 * used to distinguish between a partial or exact match.
2547 */
Christoph Hellwiga46db602011-01-07 13:02:04 +00002548int
Dave Chinnered3b4d62010-05-21 12:07:08 +10002549xfs_alloc_busy_search(
2550 struct xfs_mount *mp,
2551 xfs_agnumber_t agno,
2552 xfs_agblock_t bno,
2553 xfs_extlen_t len)
2554{
2555 struct xfs_perag *pag;
2556 struct rb_node *rbp;
2557 struct xfs_busy_extent *busyp;
2558 int match = 0;
2559
2560 pag = xfs_perag_get(mp, agno);
2561 spin_lock(&pag->pagb_lock);
2562
2563 rbp = pag->pagb_tree.rb_node;
2564
2565 /* find closest start bno overlap */
2566 while (rbp) {
2567 busyp = rb_entry(rbp, struct xfs_busy_extent, rb_node);
2568 if (bno < busyp->bno) {
2569 /* may overlap, but exact start block is lower */
2570 if (bno + len > busyp->bno)
2571 match = -1;
2572 rbp = rbp->rb_left;
2573 } else if (bno > busyp->bno) {
2574 /* may overlap, but exact start block is higher */
2575 if (bno < busyp->bno + busyp->length)
2576 match = -1;
2577 rbp = rbp->rb_right;
2578 } else {
2579 /* bno matches busyp, length determines exact match */
2580 match = (busyp->length == len) ? 1 : -1;
2581 break;
2582 }
2583 }
2584 spin_unlock(&pag->pagb_lock);
Dave Chinnered3b4d62010-05-21 12:07:08 +10002585 xfs_perag_put(pag);
2586 return match;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002587}
2588
Christoph Hellwige26f0502011-04-24 19:06:15 +00002589/*
Christoph Hellwig97d3ac72011-04-24 19:06:16 +00002590 * The found free extent [fbno, fend] overlaps part or all of the given busy
2591 * extent. If the overlap covers the beginning, the end, or all of the busy
2592 * extent, the overlapping portion can be made unbusy and used for the
2593 * allocation. We can't split a busy extent because we can't modify a
2594 * transaction/CIL context busy list, but we can update an entries block
2595 * number or length.
2596 *
2597 * Returns true if the extent can safely be reused, or false if the search
2598 * needs to be restarted.
2599 */
2600STATIC bool
2601xfs_alloc_busy_update_extent(
2602 struct xfs_mount *mp,
2603 struct xfs_perag *pag,
2604 struct xfs_busy_extent *busyp,
2605 xfs_agblock_t fbno,
2606 xfs_extlen_t flen,
2607 bool userdata)
2608{
2609 xfs_agblock_t fend = fbno + flen;
2610 xfs_agblock_t bbno = busyp->bno;
2611 xfs_agblock_t bend = bbno + busyp->length;
2612
2613 /*
Christoph Hellwige84661a2011-05-20 13:45:32 +00002614 * This extent is currently being discarded. Give the thread
2615 * performing the discard a chance to mark the extent unbusy
2616 * and retry.
2617 */
2618 if (busyp->flags & XFS_ALLOC_BUSY_DISCARDED) {
2619 spin_unlock(&pag->pagb_lock);
2620 delay(1);
2621 spin_lock(&pag->pagb_lock);
2622 return false;
2623 }
2624
2625 /*
Christoph Hellwig97d3ac72011-04-24 19:06:16 +00002626 * If there is a busy extent overlapping a user allocation, we have
2627 * no choice but to force the log and retry the search.
2628 *
2629 * Fortunately this does not happen during normal operation, but
2630 * only if the filesystem is very low on space and has to dip into
2631 * the AGFL for normal allocations.
2632 */
2633 if (userdata)
2634 goto out_force_log;
2635
2636 if (bbno < fbno && bend > fend) {
2637 /*
2638 * Case 1:
2639 * bbno bend
2640 * +BBBBBBBBBBBBBBBBB+
2641 * +---------+
2642 * fbno fend
2643 */
2644
2645 /*
2646 * We would have to split the busy extent to be able to track
2647 * it correct, which we cannot do because we would have to
2648 * modify the list of busy extents attached to the transaction
2649 * or CIL context, which is immutable.
2650 *
2651 * Force out the log to clear the busy extent and retry the
2652 * search.
2653 */
2654 goto out_force_log;
2655 } else if (bbno >= fbno && bend <= fend) {
2656 /*
2657 * Case 2:
2658 * bbno bend
2659 * +BBBBBBBBBBBBBBBBB+
2660 * +-----------------+
2661 * fbno fend
2662 *
2663 * Case 3:
2664 * bbno bend
2665 * +BBBBBBBBBBBBBBBBB+
2666 * +--------------------------+
2667 * fbno fend
2668 *
2669 * Case 4:
2670 * bbno bend
2671 * +BBBBBBBBBBBBBBBBB+
2672 * +--------------------------+
2673 * fbno fend
2674 *
2675 * Case 5:
2676 * bbno bend
2677 * +BBBBBBBBBBBBBBBBB+
2678 * +-----------------------------------+
2679 * fbno fend
2680 *
2681 */
2682
2683 /*
2684 * The busy extent is fully covered by the extent we are
2685 * allocating, and can simply be removed from the rbtree.
2686 * However we cannot remove it from the immutable list
2687 * tracking busy extents in the transaction or CIL context,
2688 * so set the length to zero to mark it invalid.
2689 *
2690 * We also need to restart the busy extent search from the
2691 * tree root, because erasing the node can rearrange the
2692 * tree topology.
2693 */
2694 rb_erase(&busyp->rb_node, &pag->pagb_tree);
2695 busyp->length = 0;
2696 return false;
2697 } else if (fend < bend) {
2698 /*
2699 * Case 6:
2700 * bbno bend
2701 * +BBBBBBBBBBBBBBBBB+
2702 * +---------+
2703 * fbno fend
2704 *
2705 * Case 7:
2706 * bbno bend
2707 * +BBBBBBBBBBBBBBBBB+
2708 * +------------------+
2709 * fbno fend
2710 *
2711 */
2712 busyp->bno = fend;
2713 } else if (bbno < fbno) {
2714 /*
2715 * Case 8:
2716 * bbno bend
2717 * +BBBBBBBBBBBBBBBBB+
2718 * +-------------+
2719 * fbno fend
2720 *
2721 * Case 9:
2722 * bbno bend
2723 * +BBBBBBBBBBBBBBBBB+
2724 * +----------------------+
2725 * fbno fend
2726 */
2727 busyp->length = fbno - busyp->bno;
2728 } else {
2729 ASSERT(0);
2730 }
2731
2732 trace_xfs_alloc_busy_reuse(mp, pag->pag_agno, fbno, flen);
2733 return true;
2734
2735out_force_log:
2736 spin_unlock(&pag->pagb_lock);
2737 xfs_log_force(mp, XFS_LOG_SYNC);
2738 trace_xfs_alloc_busy_force(mp, pag->pag_agno, fbno, flen);
2739 spin_lock(&pag->pagb_lock);
2740 return false;
2741}
2742
2743
2744/*
2745 * For a given extent [fbno, flen], make sure we can reuse it safely.
2746 */
2747void
2748xfs_alloc_busy_reuse(
2749 struct xfs_mount *mp,
2750 xfs_agnumber_t agno,
2751 xfs_agblock_t fbno,
2752 xfs_extlen_t flen,
2753 bool userdata)
2754{
2755 struct xfs_perag *pag;
2756 struct rb_node *rbp;
2757
2758 ASSERT(flen > 0);
2759
2760 pag = xfs_perag_get(mp, agno);
2761 spin_lock(&pag->pagb_lock);
2762restart:
2763 rbp = pag->pagb_tree.rb_node;
2764 while (rbp) {
2765 struct xfs_busy_extent *busyp =
2766 rb_entry(rbp, struct xfs_busy_extent, rb_node);
2767 xfs_agblock_t bbno = busyp->bno;
2768 xfs_agblock_t bend = bbno + busyp->length;
2769
2770 if (fbno + flen <= bbno) {
2771 rbp = rbp->rb_left;
2772 continue;
2773 } else if (fbno >= bend) {
2774 rbp = rbp->rb_right;
2775 continue;
2776 }
2777
2778 if (!xfs_alloc_busy_update_extent(mp, pag, busyp, fbno, flen,
2779 userdata))
2780 goto restart;
2781 }
2782 spin_unlock(&pag->pagb_lock);
2783 xfs_perag_put(pag);
2784}
2785
2786/*
Christoph Hellwige26f0502011-04-24 19:06:15 +00002787 * For a given extent [fbno, flen], search the busy extent list to find a
2788 * subset of the extent that is not busy. If *rlen is smaller than
2789 * args->minlen no suitable extent could be found, and the higher level
2790 * code needs to force out the log and retry the allocation.
2791 */
2792STATIC void
2793xfs_alloc_busy_trim(
2794 struct xfs_alloc_arg *args,
2795 xfs_agblock_t bno,
2796 xfs_extlen_t len,
2797 xfs_agblock_t *rbno,
2798 xfs_extlen_t *rlen)
2799{
Christoph Hellwig97d3ac72011-04-24 19:06:16 +00002800 xfs_agblock_t fbno;
2801 xfs_extlen_t flen;
Christoph Hellwige26f0502011-04-24 19:06:15 +00002802 struct rb_node *rbp;
2803
Christoph Hellwig97d3ac72011-04-24 19:06:16 +00002804 ASSERT(len > 0);
Christoph Hellwige26f0502011-04-24 19:06:15 +00002805
2806 spin_lock(&args->pag->pagb_lock);
Christoph Hellwig97d3ac72011-04-24 19:06:16 +00002807restart:
2808 fbno = bno;
2809 flen = len;
Christoph Hellwige26f0502011-04-24 19:06:15 +00002810 rbp = args->pag->pagb_tree.rb_node;
2811 while (rbp && flen >= args->minlen) {
2812 struct xfs_busy_extent *busyp =
2813 rb_entry(rbp, struct xfs_busy_extent, rb_node);
2814 xfs_agblock_t fend = fbno + flen;
2815 xfs_agblock_t bbno = busyp->bno;
2816 xfs_agblock_t bend = bbno + busyp->length;
2817
2818 if (fend <= bbno) {
2819 rbp = rbp->rb_left;
2820 continue;
2821 } else if (fbno >= bend) {
2822 rbp = rbp->rb_right;
2823 continue;
2824 }
2825
Christoph Hellwig97d3ac72011-04-24 19:06:16 +00002826 /*
2827 * If this is a metadata allocation, try to reuse the busy
2828 * extent instead of trimming the allocation.
2829 */
Christoph Hellwige84661a2011-05-20 13:45:32 +00002830 if (!args->userdata &&
2831 !(busyp->flags & XFS_ALLOC_BUSY_DISCARDED)) {
Christoph Hellwig97d3ac72011-04-24 19:06:16 +00002832 if (!xfs_alloc_busy_update_extent(args->mp, args->pag,
2833 busyp, fbno, flen,
2834 false))
2835 goto restart;
2836 continue;
2837 }
2838
Christoph Hellwige26f0502011-04-24 19:06:15 +00002839 if (bbno <= fbno) {
2840 /* start overlap */
2841
2842 /*
2843 * Case 1:
2844 * bbno bend
2845 * +BBBBBBBBBBBBBBBBB+
2846 * +---------+
2847 * fbno fend
2848 *
2849 * Case 2:
2850 * bbno bend
2851 * +BBBBBBBBBBBBBBBBB+
2852 * +-------------+
2853 * fbno fend
2854 *
2855 * Case 3:
2856 * bbno bend
2857 * +BBBBBBBBBBBBBBBBB+
2858 * +-------------+
2859 * fbno fend
2860 *
2861 * Case 4:
2862 * bbno bend
2863 * +BBBBBBBBBBBBBBBBB+
2864 * +-----------------+
2865 * fbno fend
2866 *
2867 * No unbusy region in extent, return failure.
2868 */
2869 if (fend <= bend)
2870 goto fail;
2871
2872 /*
2873 * Case 5:
2874 * bbno bend
2875 * +BBBBBBBBBBBBBBBBB+
2876 * +----------------------+
2877 * fbno fend
2878 *
2879 * Case 6:
2880 * bbno bend
2881 * +BBBBBBBBBBBBBBBBB+
2882 * +--------------------------+
2883 * fbno fend
2884 *
2885 * Needs to be trimmed to:
2886 * +-------+
2887 * fbno fend
2888 */
2889 fbno = bend;
2890 } else if (bend >= fend) {
2891 /* end overlap */
2892
2893 /*
2894 * Case 7:
2895 * bbno bend
2896 * +BBBBBBBBBBBBBBBBB+
2897 * +------------------+
2898 * fbno fend
2899 *
2900 * Case 8:
2901 * bbno bend
2902 * +BBBBBBBBBBBBBBBBB+
2903 * +--------------------------+
2904 * fbno fend
2905 *
2906 * Needs to be trimmed to:
2907 * +-------+
2908 * fbno fend
2909 */
2910 fend = bbno;
2911 } else {
2912 /* middle overlap */
2913
2914 /*
2915 * Case 9:
2916 * bbno bend
2917 * +BBBBBBBBBBBBBBBBB+
2918 * +-----------------------------------+
2919 * fbno fend
2920 *
2921 * Can be trimmed to:
2922 * +-------+ OR +-------+
2923 * fbno fend fbno fend
2924 *
2925 * Backward allocation leads to significant
2926 * fragmentation of directories, which degrades
2927 * directory performance, therefore we always want to
2928 * choose the option that produces forward allocation
2929 * patterns.
2930 * Preferring the lower bno extent will make the next
2931 * request use "fend" as the start of the next
2932 * allocation; if the segment is no longer busy at
2933 * that point, we'll get a contiguous allocation, but
2934 * even if it is still busy, we will get a forward
2935 * allocation.
2936 * We try to avoid choosing the segment at "bend",
2937 * because that can lead to the next allocation
2938 * taking the segment at "fbno", which would be a
2939 * backward allocation. We only use the segment at
2940 * "fbno" if it is much larger than the current
2941 * requested size, because in that case there's a
2942 * good chance subsequent allocations will be
2943 * contiguous.
2944 */
2945 if (bbno - fbno >= args->maxlen) {
2946 /* left candidate fits perfect */
2947 fend = bbno;
2948 } else if (fend - bend >= args->maxlen * 4) {
2949 /* right candidate has enough free space */
2950 fbno = bend;
2951 } else if (bbno - fbno >= args->minlen) {
2952 /* left candidate fits minimum requirement */
2953 fend = bbno;
2954 } else {
2955 goto fail;
2956 }
2957 }
2958
2959 flen = fend - fbno;
2960 }
2961 spin_unlock(&args->pag->pagb_lock);
2962
2963 if (fbno != bno || flen != len) {
2964 trace_xfs_alloc_busy_trim(args->mp, args->agno, bno, len,
2965 fbno, flen);
2966 }
2967 *rbno = fbno;
2968 *rlen = flen;
2969 return;
2970fail:
2971 /*
2972 * Return a zero extent length as failure indications. All callers
2973 * re-check if the trimmed extent satisfies the minlen requirement.
2974 */
2975 spin_unlock(&args->pag->pagb_lock);
2976 trace_xfs_alloc_busy_trim(args->mp, args->agno, bno, len, fbno, 0);
2977 *rbno = fbno;
2978 *rlen = 0;
2979}
2980
Christoph Hellwig8a072a42011-04-24 19:06:17 +00002981static void
2982xfs_alloc_busy_clear_one(
Dave Chinnered3b4d62010-05-21 12:07:08 +10002983 struct xfs_mount *mp,
Christoph Hellwig8a072a42011-04-24 19:06:17 +00002984 struct xfs_perag *pag,
Dave Chinnered3b4d62010-05-21 12:07:08 +10002985 struct xfs_busy_extent *busyp)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002986{
Christoph Hellwig97d3ac72011-04-24 19:06:16 +00002987 if (busyp->length) {
2988 trace_xfs_alloc_busy_clear(mp, busyp->agno, busyp->bno,
2989 busyp->length);
2990 rb_erase(&busyp->rb_node, &pag->pagb_tree);
2991 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002992
Christoph Hellwig8a072a42011-04-24 19:06:17 +00002993 list_del_init(&busyp->list);
Dave Chinnered3b4d62010-05-21 12:07:08 +10002994 kmem_free(busyp);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002995}
Christoph Hellwig8a072a42011-04-24 19:06:17 +00002996
Christoph Hellwige84661a2011-05-20 13:45:32 +00002997/*
2998 * Remove all extents on the passed in list from the busy extents tree.
2999 * If do_discard is set skip extents that need to be discarded, and mark
3000 * these as undergoing a discard operation instead.
3001 */
Christoph Hellwig8a072a42011-04-24 19:06:17 +00003002void
3003xfs_alloc_busy_clear(
3004 struct xfs_mount *mp,
Christoph Hellwige84661a2011-05-20 13:45:32 +00003005 struct list_head *list,
3006 bool do_discard)
Christoph Hellwig8a072a42011-04-24 19:06:17 +00003007{
3008 struct xfs_busy_extent *busyp, *n;
3009 struct xfs_perag *pag = NULL;
3010 xfs_agnumber_t agno = NULLAGNUMBER;
3011
3012 list_for_each_entry_safe(busyp, n, list, list) {
3013 if (busyp->agno != agno) {
3014 if (pag) {
3015 spin_unlock(&pag->pagb_lock);
3016 xfs_perag_put(pag);
3017 }
3018 pag = xfs_perag_get(mp, busyp->agno);
3019 spin_lock(&pag->pagb_lock);
3020 agno = busyp->agno;
3021 }
3022
Christoph Hellwig55a7bc52011-05-04 18:55:15 +00003023 if (do_discard && busyp->length &&
3024 !(busyp->flags & XFS_ALLOC_BUSY_SKIP_DISCARD))
Christoph Hellwige84661a2011-05-20 13:45:32 +00003025 busyp->flags = XFS_ALLOC_BUSY_DISCARDED;
3026 else
3027 xfs_alloc_busy_clear_one(mp, pag, busyp);
Christoph Hellwig8a072a42011-04-24 19:06:17 +00003028 }
3029
3030 if (pag) {
3031 spin_unlock(&pag->pagb_lock);
3032 xfs_perag_put(pag);
3033 }
3034}
3035
3036/*
3037 * Callback for list_sort to sort busy extents by the AG they reside in.
3038 */
3039int
3040xfs_busy_extent_ag_cmp(
3041 void *priv,
3042 struct list_head *a,
3043 struct list_head *b)
3044{
3045 return container_of(a, struct xfs_busy_extent, list)->agno -
3046 container_of(b, struct xfs_busy_extent, list)->agno;
3047}