blob: d12bbedf6fe522dd51423b12b691a639e531c641 [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"
23#include "xfs_trans.h"
24#include "xfs_sb.h"
25#include "xfs_ag.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070026#include "xfs_mount.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070027#include "xfs_bmap_btree.h"
Nathan Scotta844f452005-11-02 14:38:42 +110028#include "xfs_alloc_btree.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070029#include "xfs_ialloc_btree.h"
Nathan Scotta844f452005-11-02 14:38:42 +110030#include "xfs_dinode.h"
31#include "xfs_inode.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070032#include "xfs_btree.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070033#include "xfs_alloc.h"
Dave Chinnerefc27b52012-04-29 10:39:43 +000034#include "xfs_extent_busy.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
Dave Chinnerc999a222012-03-22 05:15:07 +000038struct workqueue_struct *xfs_alloc_wq;
Linus Torvalds1da177e2005-04-16 15:20:36 -070039
40#define XFS_ABSDIFF(a,b) (((a) <= (b)) ? ((b) - (a)) : ((a) - (b)))
41
42#define XFSA_FIXUP_BNO_OK 1
43#define XFSA_FIXUP_CNT_OK 2
44
Linus Torvalds1da177e2005-04-16 15:20:36 -070045STATIC int xfs_alloc_ag_vextent_exact(xfs_alloc_arg_t *);
46STATIC int xfs_alloc_ag_vextent_near(xfs_alloc_arg_t *);
47STATIC int xfs_alloc_ag_vextent_size(xfs_alloc_arg_t *);
48STATIC int xfs_alloc_ag_vextent_small(xfs_alloc_arg_t *,
Christoph Hellwige26f0502011-04-24 19:06:15 +000049 xfs_btree_cur_t *, xfs_agblock_t *, xfs_extlen_t *, int *);
Linus Torvalds1da177e2005-04-16 15:20:36 -070050
51/*
Christoph Hellwigfe033cc2008-10-30 16:56:09 +110052 * Lookup the record equal to [bno, len] in the btree given by cur.
53 */
54STATIC int /* error */
55xfs_alloc_lookup_eq(
56 struct xfs_btree_cur *cur, /* btree cursor */
57 xfs_agblock_t bno, /* starting block of extent */
58 xfs_extlen_t len, /* length of extent */
59 int *stat) /* success/failure */
60{
61 cur->bc_rec.a.ar_startblock = bno;
62 cur->bc_rec.a.ar_blockcount = len;
63 return xfs_btree_lookup(cur, XFS_LOOKUP_EQ, stat);
64}
65
66/*
67 * Lookup the first record greater than or equal to [bno, len]
68 * in the btree given by cur.
69 */
Dave Chinnera66d6362012-03-22 05:15:12 +000070int /* error */
Christoph Hellwigfe033cc2008-10-30 16:56:09 +110071xfs_alloc_lookup_ge(
72 struct xfs_btree_cur *cur, /* btree cursor */
73 xfs_agblock_t bno, /* starting block of extent */
74 xfs_extlen_t len, /* length of extent */
75 int *stat) /* success/failure */
76{
77 cur->bc_rec.a.ar_startblock = bno;
78 cur->bc_rec.a.ar_blockcount = len;
79 return xfs_btree_lookup(cur, XFS_LOOKUP_GE, stat);
80}
81
82/*
83 * Lookup the first record less than or equal to [bno, len]
84 * in the btree given by cur.
85 */
Christoph Hellwiga46db602011-01-07 13:02:04 +000086int /* error */
Christoph Hellwigfe033cc2008-10-30 16:56:09 +110087xfs_alloc_lookup_le(
88 struct xfs_btree_cur *cur, /* btree cursor */
89 xfs_agblock_t bno, /* starting block of extent */
90 xfs_extlen_t len, /* length of extent */
91 int *stat) /* success/failure */
92{
93 cur->bc_rec.a.ar_startblock = bno;
94 cur->bc_rec.a.ar_blockcount = len;
95 return xfs_btree_lookup(cur, XFS_LOOKUP_LE, stat);
96}
97
Christoph Hellwig278d0ca2008-10-30 16:56:32 +110098/*
99 * Update the record referred to by cur to the value given
100 * by [bno, len].
101 * This either works (return 0) or gets an EFSCORRUPTED error.
102 */
103STATIC int /* error */
104xfs_alloc_update(
105 struct xfs_btree_cur *cur, /* btree cursor */
106 xfs_agblock_t bno, /* starting block of extent */
107 xfs_extlen_t len) /* length of extent */
108{
109 union xfs_btree_rec rec;
110
111 rec.alloc.ar_startblock = cpu_to_be32(bno);
112 rec.alloc.ar_blockcount = cpu_to_be32(len);
113 return xfs_btree_update(cur, &rec);
114}
Christoph Hellwigfe033cc2008-10-30 16:56:09 +1100115
116/*
Christoph Hellwig8cc938f2008-10-30 16:58:11 +1100117 * Get the data from the pointed-to record.
118 */
Christoph Hellwiga46db602011-01-07 13:02:04 +0000119int /* error */
Christoph Hellwig8cc938f2008-10-30 16:58:11 +1100120xfs_alloc_get_rec(
121 struct xfs_btree_cur *cur, /* btree cursor */
122 xfs_agblock_t *bno, /* output: starting block of extent */
123 xfs_extlen_t *len, /* output: length of extent */
124 int *stat) /* output: success/failure */
125{
126 union xfs_btree_rec *rec;
127 int error;
128
129 error = xfs_btree_get_rec(cur, &rec, stat);
130 if (!error && *stat == 1) {
131 *bno = be32_to_cpu(rec->alloc.ar_startblock);
132 *len = be32_to_cpu(rec->alloc.ar_blockcount);
133 }
134 return error;
135}
136
137/*
Linus Torvalds1da177e2005-04-16 15:20:36 -0700138 * Compute aligned version of the found extent.
139 * Takes alignment and min length into account.
140 */
David Chinner12375c82008-04-10 12:21:32 +1000141STATIC void
Linus Torvalds1da177e2005-04-16 15:20:36 -0700142xfs_alloc_compute_aligned(
Christoph Hellwig86fa8af2011-03-04 12:59:54 +0000143 xfs_alloc_arg_t *args, /* allocation argument structure */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700144 xfs_agblock_t foundbno, /* starting block in found extent */
145 xfs_extlen_t foundlen, /* length in found extent */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700146 xfs_agblock_t *resbno, /* result block number */
147 xfs_extlen_t *reslen) /* result length */
148{
149 xfs_agblock_t bno;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700150 xfs_extlen_t len;
151
Christoph Hellwige26f0502011-04-24 19:06:15 +0000152 /* Trim busy sections out of found extent */
Dave Chinner4ecbfe62012-04-29 10:41:10 +0000153 xfs_extent_busy_trim(args, foundbno, foundlen, &bno, &len);
Christoph Hellwige26f0502011-04-24 19:06:15 +0000154
155 if (args->alignment > 1 && len >= args->minlen) {
156 xfs_agblock_t aligned_bno = roundup(bno, args->alignment);
157 xfs_extlen_t diff = aligned_bno - bno;
158
159 *resbno = aligned_bno;
160 *reslen = diff >= len ? 0 : len - diff;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700161 } else {
Christoph Hellwige26f0502011-04-24 19:06:15 +0000162 *resbno = bno;
163 *reslen = len;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700164 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700165}
166
167/*
168 * Compute best start block and diff for "near" allocations.
169 * freelen >= wantlen already checked by caller.
170 */
171STATIC xfs_extlen_t /* difference value (absolute) */
172xfs_alloc_compute_diff(
173 xfs_agblock_t wantbno, /* target starting block */
174 xfs_extlen_t wantlen, /* target length */
175 xfs_extlen_t alignment, /* target alignment */
176 xfs_agblock_t freebno, /* freespace's starting block */
177 xfs_extlen_t freelen, /* freespace's length */
178 xfs_agblock_t *newbnop) /* result: best start block from free */
179{
180 xfs_agblock_t freeend; /* end of freespace extent */
181 xfs_agblock_t newbno1; /* return block number */
182 xfs_agblock_t newbno2; /* other new block number */
183 xfs_extlen_t newlen1=0; /* length with newbno1 */
184 xfs_extlen_t newlen2=0; /* length with newbno2 */
185 xfs_agblock_t wantend; /* end of target extent */
186
187 ASSERT(freelen >= wantlen);
188 freeend = freebno + freelen;
189 wantend = wantbno + wantlen;
190 if (freebno >= wantbno) {
191 if ((newbno1 = roundup(freebno, alignment)) >= freeend)
192 newbno1 = NULLAGBLOCK;
193 } else if (freeend >= wantend && alignment > 1) {
194 newbno1 = roundup(wantbno, alignment);
195 newbno2 = newbno1 - alignment;
196 if (newbno1 >= freeend)
197 newbno1 = NULLAGBLOCK;
198 else
199 newlen1 = XFS_EXTLEN_MIN(wantlen, freeend - newbno1);
200 if (newbno2 < freebno)
201 newbno2 = NULLAGBLOCK;
202 else
203 newlen2 = XFS_EXTLEN_MIN(wantlen, freeend - newbno2);
204 if (newbno1 != NULLAGBLOCK && newbno2 != NULLAGBLOCK) {
205 if (newlen1 < newlen2 ||
206 (newlen1 == newlen2 &&
207 XFS_ABSDIFF(newbno1, wantbno) >
208 XFS_ABSDIFF(newbno2, wantbno)))
209 newbno1 = newbno2;
210 } else if (newbno2 != NULLAGBLOCK)
211 newbno1 = newbno2;
212 } else if (freeend >= wantend) {
213 newbno1 = wantbno;
214 } else if (alignment > 1) {
215 newbno1 = roundup(freeend - wantlen, alignment);
216 if (newbno1 > freeend - wantlen &&
217 newbno1 - alignment >= freebno)
218 newbno1 -= alignment;
219 else if (newbno1 >= freeend)
220 newbno1 = NULLAGBLOCK;
221 } else
222 newbno1 = freeend - wantlen;
223 *newbnop = newbno1;
224 return newbno1 == NULLAGBLOCK ? 0 : XFS_ABSDIFF(newbno1, wantbno);
225}
226
227/*
228 * Fix up the length, based on mod and prod.
229 * len should be k * prod + mod for some k.
230 * If len is too small it is returned unchanged.
231 * If len hits maxlen it is left alone.
232 */
233STATIC void
234xfs_alloc_fix_len(
235 xfs_alloc_arg_t *args) /* allocation argument structure */
236{
237 xfs_extlen_t k;
238 xfs_extlen_t rlen;
239
240 ASSERT(args->mod < args->prod);
241 rlen = args->len;
242 ASSERT(rlen >= args->minlen);
243 ASSERT(rlen <= args->maxlen);
244 if (args->prod <= 1 || rlen < args->mod || rlen == args->maxlen ||
245 (args->mod == 0 && rlen < args->prod))
246 return;
247 k = rlen % args->prod;
248 if (k == args->mod)
249 return;
250 if (k > args->mod) {
251 if ((int)(rlen = rlen - k - args->mod) < (int)args->minlen)
252 return;
253 } else {
254 if ((int)(rlen = rlen - args->prod - (args->mod - k)) <
255 (int)args->minlen)
256 return;
257 }
258 ASSERT(rlen >= args->minlen);
259 ASSERT(rlen <= args->maxlen);
260 args->len = rlen;
261}
262
263/*
264 * Fix up length if there is too little space left in the a.g.
265 * Return 1 if ok, 0 if too little, should give up.
266 */
267STATIC int
268xfs_alloc_fix_minleft(
269 xfs_alloc_arg_t *args) /* allocation argument structure */
270{
271 xfs_agf_t *agf; /* a.g. freelist header */
272 int diff; /* free space difference */
273
274 if (args->minleft == 0)
275 return 1;
276 agf = XFS_BUF_TO_AGF(args->agbp);
Christoph Hellwig16259e72005-11-02 15:11:25 +1100277 diff = be32_to_cpu(agf->agf_freeblks)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700278 - args->len - args->minleft;
279 if (diff >= 0)
280 return 1;
281 args->len += diff; /* shrink the allocated space */
282 if (args->len >= args->minlen)
283 return 1;
284 args->agbno = NULLAGBLOCK;
285 return 0;
286}
287
288/*
289 * Update the two btrees, logically removing from freespace the extent
290 * starting at rbno, rlen blocks. The extent is contained within the
291 * actual (current) free extent fbno for flen blocks.
292 * Flags are passed in indicating whether the cursors are set to the
293 * relevant records.
294 */
295STATIC int /* error code */
296xfs_alloc_fixup_trees(
297 xfs_btree_cur_t *cnt_cur, /* cursor for by-size btree */
298 xfs_btree_cur_t *bno_cur, /* cursor for by-block btree */
299 xfs_agblock_t fbno, /* starting block of free extent */
300 xfs_extlen_t flen, /* length of free extent */
301 xfs_agblock_t rbno, /* starting block of returned extent */
302 xfs_extlen_t rlen, /* length of returned extent */
303 int flags) /* flags, XFSA_FIXUP_... */
304{
305 int error; /* error code */
306 int i; /* operation results */
307 xfs_agblock_t nfbno1; /* first new free startblock */
308 xfs_agblock_t nfbno2; /* second new free startblock */
309 xfs_extlen_t nflen1=0; /* first new free length */
310 xfs_extlen_t nflen2=0; /* second new free length */
311
312 /*
313 * Look up the record in the by-size tree if necessary.
314 */
315 if (flags & XFSA_FIXUP_CNT_OK) {
316#ifdef DEBUG
317 if ((error = xfs_alloc_get_rec(cnt_cur, &nfbno1, &nflen1, &i)))
318 return error;
319 XFS_WANT_CORRUPTED_RETURN(
320 i == 1 && nfbno1 == fbno && nflen1 == flen);
321#endif
322 } else {
323 if ((error = xfs_alloc_lookup_eq(cnt_cur, fbno, flen, &i)))
324 return error;
325 XFS_WANT_CORRUPTED_RETURN(i == 1);
326 }
327 /*
328 * Look up the record in the by-block tree if necessary.
329 */
330 if (flags & XFSA_FIXUP_BNO_OK) {
331#ifdef DEBUG
332 if ((error = xfs_alloc_get_rec(bno_cur, &nfbno1, &nflen1, &i)))
333 return error;
334 XFS_WANT_CORRUPTED_RETURN(
335 i == 1 && nfbno1 == fbno && nflen1 == flen);
336#endif
337 } else {
338 if ((error = xfs_alloc_lookup_eq(bno_cur, fbno, flen, &i)))
339 return error;
340 XFS_WANT_CORRUPTED_RETURN(i == 1);
341 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700342
Christoph Hellwig7cc95a82008-10-30 17:14:34 +1100343#ifdef DEBUG
344 if (bno_cur->bc_nlevels == 1 && cnt_cur->bc_nlevels == 1) {
345 struct xfs_btree_block *bnoblock;
346 struct xfs_btree_block *cntblock;
347
348 bnoblock = XFS_BUF_TO_BLOCK(bno_cur->bc_bufs[0]);
349 cntblock = XFS_BUF_TO_BLOCK(cnt_cur->bc_bufs[0]);
350
351 XFS_WANT_CORRUPTED_RETURN(
352 bnoblock->bb_numrecs == cntblock->bb_numrecs);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700353 }
354#endif
Christoph Hellwig7cc95a82008-10-30 17:14:34 +1100355
Linus Torvalds1da177e2005-04-16 15:20:36 -0700356 /*
357 * Deal with all four cases: the allocated record is contained
358 * within the freespace record, so we can have new freespace
359 * at either (or both) end, or no freespace remaining.
360 */
361 if (rbno == fbno && rlen == flen)
362 nfbno1 = nfbno2 = NULLAGBLOCK;
363 else if (rbno == fbno) {
364 nfbno1 = rbno + rlen;
365 nflen1 = flen - rlen;
366 nfbno2 = NULLAGBLOCK;
367 } else if (rbno + rlen == fbno + flen) {
368 nfbno1 = fbno;
369 nflen1 = flen - rlen;
370 nfbno2 = NULLAGBLOCK;
371 } else {
372 nfbno1 = fbno;
373 nflen1 = rbno - fbno;
374 nfbno2 = rbno + rlen;
375 nflen2 = (fbno + flen) - nfbno2;
376 }
377 /*
378 * Delete the entry from the by-size btree.
379 */
Christoph Hellwig91cca5df2008-10-30 16:58:01 +1100380 if ((error = xfs_btree_delete(cnt_cur, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700381 return error;
382 XFS_WANT_CORRUPTED_RETURN(i == 1);
383 /*
384 * Add new by-size btree entry(s).
385 */
386 if (nfbno1 != NULLAGBLOCK) {
387 if ((error = xfs_alloc_lookup_eq(cnt_cur, nfbno1, nflen1, &i)))
388 return error;
389 XFS_WANT_CORRUPTED_RETURN(i == 0);
Christoph Hellwig4b22a572008-10-30 16:57:40 +1100390 if ((error = xfs_btree_insert(cnt_cur, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700391 return error;
392 XFS_WANT_CORRUPTED_RETURN(i == 1);
393 }
394 if (nfbno2 != NULLAGBLOCK) {
395 if ((error = xfs_alloc_lookup_eq(cnt_cur, nfbno2, nflen2, &i)))
396 return error;
397 XFS_WANT_CORRUPTED_RETURN(i == 0);
Christoph Hellwig4b22a572008-10-30 16:57:40 +1100398 if ((error = xfs_btree_insert(cnt_cur, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700399 return error;
400 XFS_WANT_CORRUPTED_RETURN(i == 1);
401 }
402 /*
403 * Fix up the by-block btree entry(s).
404 */
405 if (nfbno1 == NULLAGBLOCK) {
406 /*
407 * No remaining freespace, just delete the by-block tree entry.
408 */
Christoph Hellwig91cca5df2008-10-30 16:58:01 +1100409 if ((error = xfs_btree_delete(bno_cur, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700410 return error;
411 XFS_WANT_CORRUPTED_RETURN(i == 1);
412 } else {
413 /*
414 * Update the by-block entry to start later|be shorter.
415 */
416 if ((error = xfs_alloc_update(bno_cur, nfbno1, nflen1)))
417 return error;
418 }
419 if (nfbno2 != NULLAGBLOCK) {
420 /*
421 * 2 resulting free entries, need to add one.
422 */
423 if ((error = xfs_alloc_lookup_eq(bno_cur, nfbno2, nflen2, &i)))
424 return error;
425 XFS_WANT_CORRUPTED_RETURN(i == 0);
Christoph Hellwig4b22a572008-10-30 16:57:40 +1100426 if ((error = xfs_btree_insert(bno_cur, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700427 return error;
428 XFS_WANT_CORRUPTED_RETURN(i == 1);
429 }
430 return 0;
431}
432
Dave Chinner612cfbf2012-11-14 17:52:32 +1100433static void
434xfs_agfl_verify(
Dave Chinnerbb80c6d2012-11-12 22:54:06 +1100435 struct xfs_buf *bp)
436{
437#ifdef WHEN_CRCS_COME_ALONG
438 /*
439 * we cannot actually do any verification of the AGFL because mkfs does
440 * not initialise the AGFL to zero or NULL. Hence the only valid part of
441 * the AGFL is what the AGF says is active. We can't get to the AGF, so
442 * we can't verify just those entries are valid.
443 *
444 * This problem goes away when the CRC format change comes along as that
445 * requires the AGFL to be initialised by mkfs. At that point, we can
446 * verify the blocks in the agfl -active or not- lie within the bounds
447 * of the AG. Until then, just leave this check ifdef'd out.
448 */
449 struct xfs_mount *mp = bp->b_target->bt_mount;
450 struct xfs_agfl *agfl = XFS_BUF_TO_AGFL(bp);
451 int agfl_ok = 1;
452
453 int i;
454
455 for (i = 0; i < XFS_AGFL_SIZE(mp); i++) {
456 if (be32_to_cpu(agfl->agfl_bno[i]) == NULLAGBLOCK ||
457 be32_to_cpu(agfl->agfl_bno[i]) >= mp->m_sb.sb_agblocks)
458 agfl_ok = 0;
459 }
460
461 if (!agfl_ok) {
462 XFS_CORRUPTION_ERROR(__func__, XFS_ERRLEVEL_LOW, mp, agfl);
463 xfs_buf_ioerror(bp, EFSCORRUPTED);
464 }
465#endif
Dave Chinner612cfbf2012-11-14 17:52:32 +1100466}
467
468static void
469xfs_agfl_write_verify(
470 struct xfs_buf *bp)
471{
472 xfs_agfl_verify(bp);
473}
474
475void
476xfs_agfl_read_verify(
477 struct xfs_buf *bp)
478{
479 xfs_agfl_verify(bp);
480 bp->b_pre_io = xfs_agfl_write_verify;
Dave Chinnerbb80c6d2012-11-12 22:54:06 +1100481 bp->b_iodone = NULL;
482 xfs_buf_ioend(bp, 0);
483}
484
Linus Torvalds1da177e2005-04-16 15:20:36 -0700485/*
486 * Read in the allocation group free block array.
487 */
488STATIC int /* error */
489xfs_alloc_read_agfl(
490 xfs_mount_t *mp, /* mount point structure */
491 xfs_trans_t *tp, /* transaction pointer */
492 xfs_agnumber_t agno, /* allocation group number */
493 xfs_buf_t **bpp) /* buffer for the ag free block array */
494{
495 xfs_buf_t *bp; /* return value */
496 int error;
497
498 ASSERT(agno != NULLAGNUMBER);
499 error = xfs_trans_read_buf(
500 mp, tp, mp->m_ddev_targp,
501 XFS_AG_DADDR(mp, agno, XFS_AGFL_DADDR(mp)),
Dave Chinnerbb80c6d2012-11-12 22:54:06 +1100502 XFS_FSS_TO_BB(mp, 1), 0, &bp, xfs_agfl_read_verify);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700503 if (error)
504 return error;
Chandra Seetharaman5a52c2a582011-07-22 23:39:51 +0000505 ASSERT(!xfs_buf_geterror(bp));
Christoph Hellwig38f23232011-10-10 16:52:45 +0000506 xfs_buf_set_ref(bp, XFS_AGFL_REF);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700507 *bpp = bp;
508 return 0;
509}
510
Christoph Hellwigecb69282011-03-04 12:59:55 +0000511STATIC int
512xfs_alloc_update_counters(
513 struct xfs_trans *tp,
514 struct xfs_perag *pag,
515 struct xfs_buf *agbp,
516 long len)
517{
518 struct xfs_agf *agf = XFS_BUF_TO_AGF(agbp);
519
520 pag->pagf_freeblks += len;
521 be32_add_cpu(&agf->agf_freeblks, len);
522
523 xfs_trans_agblocks_delta(tp, len);
524 if (unlikely(be32_to_cpu(agf->agf_freeblks) >
525 be32_to_cpu(agf->agf_length)))
526 return EFSCORRUPTED;
527
528 xfs_alloc_log_agf(tp, agbp, XFS_AGF_FREEBLKS);
529 return 0;
530}
531
Linus Torvalds1da177e2005-04-16 15:20:36 -0700532/*
533 * Allocation group level functions.
534 */
535
536/*
537 * Allocate a variable extent in the allocation group agno.
538 * Type and bno are used to determine where in the allocation group the
539 * extent will start.
540 * Extent's length (returned in *len) will be between minlen and maxlen,
541 * and of the form k * prod + mod unless there's nothing that large.
542 * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
543 */
544STATIC int /* error */
545xfs_alloc_ag_vextent(
546 xfs_alloc_arg_t *args) /* argument structure for allocation */
547{
548 int error=0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700549
550 ASSERT(args->minlen > 0);
551 ASSERT(args->maxlen > 0);
552 ASSERT(args->minlen <= args->maxlen);
553 ASSERT(args->mod < args->prod);
554 ASSERT(args->alignment > 0);
555 /*
556 * Branch to correct routine based on the type.
557 */
558 args->wasfromfl = 0;
559 switch (args->type) {
560 case XFS_ALLOCTYPE_THIS_AG:
561 error = xfs_alloc_ag_vextent_size(args);
562 break;
563 case XFS_ALLOCTYPE_NEAR_BNO:
564 error = xfs_alloc_ag_vextent_near(args);
565 break;
566 case XFS_ALLOCTYPE_THIS_BNO:
567 error = xfs_alloc_ag_vextent_exact(args);
568 break;
569 default:
570 ASSERT(0);
571 /* NOTREACHED */
572 }
Christoph Hellwigecb69282011-03-04 12:59:55 +0000573
574 if (error || args->agbno == NULLAGBLOCK)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700575 return error;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700576
Christoph Hellwigecb69282011-03-04 12:59:55 +0000577 ASSERT(args->len >= args->minlen);
578 ASSERT(args->len <= args->maxlen);
579 ASSERT(!args->wasfromfl || !args->isfl);
580 ASSERT(args->agbno % args->alignment == 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700581
Christoph Hellwigecb69282011-03-04 12:59:55 +0000582 if (!args->wasfromfl) {
583 error = xfs_alloc_update_counters(args->tp, args->pag,
584 args->agbp,
585 -((long)(args->len)));
586 if (error)
587 return error;
588
Dave Chinner4ecbfe62012-04-29 10:41:10 +0000589 ASSERT(!xfs_extent_busy_search(args->mp, args->agno,
Christoph Hellwige26f0502011-04-24 19:06:15 +0000590 args->agbno, args->len));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700591 }
Christoph Hellwigecb69282011-03-04 12:59:55 +0000592
593 if (!args->isfl) {
594 xfs_trans_mod_sb(args->tp, args->wasdel ?
595 XFS_TRANS_SB_RES_FDBLOCKS :
596 XFS_TRANS_SB_FDBLOCKS,
597 -((long)(args->len)));
598 }
599
600 XFS_STATS_INC(xs_allocx);
601 XFS_STATS_ADD(xs_allocb, args->len);
602 return error;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700603}
604
605/*
606 * Allocate a variable extent at exactly agno/bno.
607 * Extent's length (returned in *len) will be between minlen and maxlen,
608 * and of the form k * prod + mod unless there's nothing that large.
609 * Return the starting a.g. block (bno), or NULLAGBLOCK if we can't do it.
610 */
611STATIC int /* error */
612xfs_alloc_ag_vextent_exact(
613 xfs_alloc_arg_t *args) /* allocation argument structure */
614{
615 xfs_btree_cur_t *bno_cur;/* by block-number btree cursor */
616 xfs_btree_cur_t *cnt_cur;/* by count btree cursor */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700617 int error;
618 xfs_agblock_t fbno; /* start block of found extent */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700619 xfs_extlen_t flen; /* length of found extent */
Christoph Hellwige26f0502011-04-24 19:06:15 +0000620 xfs_agblock_t tbno; /* start block of trimmed extent */
621 xfs_extlen_t tlen; /* length of trimmed extent */
622 xfs_agblock_t tend; /* end block of trimmed extent */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700623 int i; /* success/failure of operation */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700624
625 ASSERT(args->alignment == 1);
Christoph Hellwig9f9baab2010-12-10 15:03:57 +0000626
Linus Torvalds1da177e2005-04-16 15:20:36 -0700627 /*
628 * Allocate/initialize a cursor for the by-number freespace btree.
629 */
Christoph Hellwig561f7d12008-10-30 16:53:59 +1100630 bno_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
Christoph Hellwig9f9baab2010-12-10 15:03:57 +0000631 args->agno, XFS_BTNUM_BNO);
632
Linus Torvalds1da177e2005-04-16 15:20:36 -0700633 /*
634 * Lookup bno and minlen in the btree (minlen is irrelevant, really).
635 * Look for the closest free block <= bno, it must contain bno
636 * if any free block does.
637 */
Christoph Hellwig9f9baab2010-12-10 15:03:57 +0000638 error = xfs_alloc_lookup_le(bno_cur, args->agbno, args->minlen, &i);
639 if (error)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700640 goto error0;
Christoph Hellwig9f9baab2010-12-10 15:03:57 +0000641 if (!i)
642 goto not_found;
643
Linus Torvalds1da177e2005-04-16 15:20:36 -0700644 /*
645 * Grab the freespace record.
646 */
Christoph Hellwig9f9baab2010-12-10 15:03:57 +0000647 error = xfs_alloc_get_rec(bno_cur, &fbno, &flen, &i);
648 if (error)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700649 goto error0;
650 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
651 ASSERT(fbno <= args->agbno);
Christoph Hellwig9f9baab2010-12-10 15:03:57 +0000652
Linus Torvalds1da177e2005-04-16 15:20:36 -0700653 /*
Christoph Hellwige26f0502011-04-24 19:06:15 +0000654 * Check for overlapping busy extents.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700655 */
Dave Chinner4ecbfe62012-04-29 10:41:10 +0000656 xfs_extent_busy_trim(args, fbno, flen, &tbno, &tlen);
Christoph Hellwige26f0502011-04-24 19:06:15 +0000657
658 /*
659 * Give up if the start of the extent is busy, or the freespace isn't
660 * long enough for the minimum request.
661 */
662 if (tbno > args->agbno)
663 goto not_found;
664 if (tlen < args->minlen)
665 goto not_found;
666 tend = tbno + tlen;
667 if (tend < args->agbno + args->minlen)
Christoph Hellwig9f9baab2010-12-10 15:03:57 +0000668 goto not_found;
669
Linus Torvalds1da177e2005-04-16 15:20:36 -0700670 /*
671 * End of extent will be smaller of the freespace end and the
672 * maximal requested end.
Christoph Hellwig9f9baab2010-12-10 15:03:57 +0000673 *
Linus Torvalds1da177e2005-04-16 15:20:36 -0700674 * Fix the length according to mod and prod if given.
675 */
Chandra Seetharaman81463b12011-06-09 16:47:49 +0000676 args->len = XFS_AGBLOCK_MIN(tend, args->agbno + args->maxlen)
677 - args->agbno;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700678 xfs_alloc_fix_len(args);
Christoph Hellwig9f9baab2010-12-10 15:03:57 +0000679 if (!xfs_alloc_fix_minleft(args))
680 goto not_found;
681
Chandra Seetharaman81463b12011-06-09 16:47:49 +0000682 ASSERT(args->agbno + args->len <= tend);
Christoph Hellwig9f9baab2010-12-10 15:03:57 +0000683
Linus Torvalds1da177e2005-04-16 15:20:36 -0700684 /*
Chandra Seetharaman81463b12011-06-09 16:47:49 +0000685 * We are allocating agbno for args->len
Linus Torvalds1da177e2005-04-16 15:20:36 -0700686 * Allocate/initialize a cursor for the by-size btree.
687 */
Christoph Hellwig561f7d12008-10-30 16:53:59 +1100688 cnt_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
689 args->agno, XFS_BTNUM_CNT);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700690 ASSERT(args->agbno + args->len <=
Christoph Hellwig16259e72005-11-02 15:11:25 +1100691 be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length));
Christoph Hellwig9f9baab2010-12-10 15:03:57 +0000692 error = xfs_alloc_fixup_trees(cnt_cur, bno_cur, fbno, flen, args->agbno,
693 args->len, XFSA_FIXUP_BNO_OK);
694 if (error) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700695 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
696 goto error0;
697 }
Christoph Hellwig9f9baab2010-12-10 15:03:57 +0000698
Linus Torvalds1da177e2005-04-16 15:20:36 -0700699 xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
700 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
Christoph Hellwig0b1b2132009-12-14 23:14:59 +0000701
Linus Torvalds1da177e2005-04-16 15:20:36 -0700702 args->wasfromfl = 0;
Christoph Hellwig9f9baab2010-12-10 15:03:57 +0000703 trace_xfs_alloc_exact_done(args);
704 return 0;
705
706not_found:
707 /* Didn't find it, return null. */
708 xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
709 args->agbno = NULLAGBLOCK;
710 trace_xfs_alloc_exact_notfound(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700711 return 0;
712
713error0:
714 xfs_btree_del_cursor(bno_cur, XFS_BTREE_ERROR);
Christoph Hellwig0b1b2132009-12-14 23:14:59 +0000715 trace_xfs_alloc_exact_error(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700716 return error;
717}
718
719/*
Christoph Hellwig489a1502010-12-10 15:04:11 +0000720 * Search the btree in a given direction via the search cursor and compare
721 * the records found against the good extent we've already found.
722 */
723STATIC int
724xfs_alloc_find_best_extent(
725 struct xfs_alloc_arg *args, /* allocation argument structure */
726 struct xfs_btree_cur **gcur, /* good cursor */
727 struct xfs_btree_cur **scur, /* searching cursor */
728 xfs_agblock_t gdiff, /* difference for search comparison */
729 xfs_agblock_t *sbno, /* extent found by search */
Christoph Hellwige26f0502011-04-24 19:06:15 +0000730 xfs_extlen_t *slen, /* extent length */
731 xfs_agblock_t *sbnoa, /* aligned extent found by search */
732 xfs_extlen_t *slena, /* aligned extent length */
Christoph Hellwig489a1502010-12-10 15:04:11 +0000733 int dir) /* 0 = search right, 1 = search left */
734{
Christoph Hellwig489a1502010-12-10 15:04:11 +0000735 xfs_agblock_t new;
736 xfs_agblock_t sdiff;
737 int error;
738 int i;
739
740 /* The good extent is perfect, no need to search. */
741 if (!gdiff)
742 goto out_use_good;
743
744 /*
745 * Look until we find a better one, run out of space or run off the end.
746 */
747 do {
748 error = xfs_alloc_get_rec(*scur, sbno, slen, &i);
749 if (error)
750 goto error0;
751 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
Christoph Hellwige26f0502011-04-24 19:06:15 +0000752 xfs_alloc_compute_aligned(args, *sbno, *slen, sbnoa, slena);
Christoph Hellwig489a1502010-12-10 15:04:11 +0000753
754 /*
755 * The good extent is closer than this one.
756 */
757 if (!dir) {
Christoph Hellwige26f0502011-04-24 19:06:15 +0000758 if (*sbnoa >= args->agbno + gdiff)
Christoph Hellwig489a1502010-12-10 15:04:11 +0000759 goto out_use_good;
760 } else {
Christoph Hellwige26f0502011-04-24 19:06:15 +0000761 if (*sbnoa <= args->agbno - gdiff)
Christoph Hellwig489a1502010-12-10 15:04:11 +0000762 goto out_use_good;
763 }
764
765 /*
766 * Same distance, compare length and pick the best.
767 */
768 if (*slena >= args->minlen) {
769 args->len = XFS_EXTLEN_MIN(*slena, args->maxlen);
770 xfs_alloc_fix_len(args);
771
772 sdiff = xfs_alloc_compute_diff(args->agbno, args->len,
Christoph Hellwige26f0502011-04-24 19:06:15 +0000773 args->alignment, *sbnoa,
774 *slena, &new);
Christoph Hellwig489a1502010-12-10 15:04:11 +0000775
776 /*
777 * Choose closer size and invalidate other cursor.
778 */
779 if (sdiff < gdiff)
780 goto out_use_search;
781 goto out_use_good;
782 }
783
784 if (!dir)
785 error = xfs_btree_increment(*scur, 0, &i);
786 else
787 error = xfs_btree_decrement(*scur, 0, &i);
788 if (error)
789 goto error0;
790 } while (i);
791
792out_use_good:
793 xfs_btree_del_cursor(*scur, XFS_BTREE_NOERROR);
794 *scur = NULL;
795 return 0;
796
797out_use_search:
798 xfs_btree_del_cursor(*gcur, XFS_BTREE_NOERROR);
799 *gcur = NULL;
800 return 0;
801
802error0:
803 /* caller invalidates cursors */
804 return error;
805}
806
807/*
Linus Torvalds1da177e2005-04-16 15:20:36 -0700808 * Allocate a variable extent near bno in the allocation group agno.
809 * Extent's length (returned in len) will be between minlen and maxlen,
810 * and of the form k * prod + mod unless there's nothing that large.
811 * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
812 */
813STATIC int /* error */
814xfs_alloc_ag_vextent_near(
815 xfs_alloc_arg_t *args) /* allocation argument structure */
816{
817 xfs_btree_cur_t *bno_cur_gt; /* cursor for bno btree, right side */
818 xfs_btree_cur_t *bno_cur_lt; /* cursor for bno btree, left side */
819 xfs_btree_cur_t *cnt_cur; /* cursor for count btree */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700820 xfs_agblock_t gtbno; /* start bno of right side entry */
821 xfs_agblock_t gtbnoa; /* aligned ... */
822 xfs_extlen_t gtdiff; /* difference to right side entry */
823 xfs_extlen_t gtlen; /* length of right side entry */
Christoph Hellwige26f0502011-04-24 19:06:15 +0000824 xfs_extlen_t gtlena; /* aligned ... */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700825 xfs_agblock_t gtnew; /* useful start bno of right side */
826 int error; /* error code */
827 int i; /* result code, temporary */
828 int j; /* result code, temporary */
829 xfs_agblock_t ltbno; /* start bno of left side entry */
830 xfs_agblock_t ltbnoa; /* aligned ... */
831 xfs_extlen_t ltdiff; /* difference to left side entry */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700832 xfs_extlen_t ltlen; /* length of left side entry */
Christoph Hellwige26f0502011-04-24 19:06:15 +0000833 xfs_extlen_t ltlena; /* aligned ... */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700834 xfs_agblock_t ltnew; /* useful start bno of left side */
835 xfs_extlen_t rlen; /* length of returned extent */
Christoph Hellwige26f0502011-04-24 19:06:15 +0000836 int forced = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700837#if defined(DEBUG) && defined(__KERNEL__)
838 /*
839 * Randomly don't execute the first algorithm.
840 */
841 int dofirst; /* set to do first algorithm */
842
Joe Perchese7a23a92007-05-08 13:49:03 +1000843 dofirst = random32() & 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700844#endif
Christoph Hellwige26f0502011-04-24 19:06:15 +0000845
846restart:
847 bno_cur_lt = NULL;
848 bno_cur_gt = NULL;
849 ltlen = 0;
850 gtlena = 0;
851 ltlena = 0;
852
Linus Torvalds1da177e2005-04-16 15:20:36 -0700853 /*
854 * Get a cursor for the by-size btree.
855 */
Christoph Hellwig561f7d12008-10-30 16:53:59 +1100856 cnt_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
857 args->agno, XFS_BTNUM_CNT);
Christoph Hellwige26f0502011-04-24 19:06:15 +0000858
Linus Torvalds1da177e2005-04-16 15:20:36 -0700859 /*
860 * See if there are any free extents as big as maxlen.
861 */
862 if ((error = xfs_alloc_lookup_ge(cnt_cur, 0, args->maxlen, &i)))
863 goto error0;
864 /*
865 * If none, then pick up the last entry in the tree unless the
866 * tree is empty.
867 */
868 if (!i) {
869 if ((error = xfs_alloc_ag_vextent_small(args, cnt_cur, &ltbno,
870 &ltlen, &i)))
871 goto error0;
872 if (i == 0 || ltlen == 0) {
873 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
Christoph Hellwige26f0502011-04-24 19:06:15 +0000874 trace_xfs_alloc_near_noentry(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700875 return 0;
876 }
877 ASSERT(i == 1);
878 }
879 args->wasfromfl = 0;
Christoph Hellwige26f0502011-04-24 19:06:15 +0000880
Linus Torvalds1da177e2005-04-16 15:20:36 -0700881 /*
882 * First algorithm.
883 * If the requested extent is large wrt the freespaces available
884 * in this a.g., then the cursor will be pointing to a btree entry
885 * near the right edge of the tree. If it's in the last btree leaf
886 * block, then we just examine all the entries in that block
887 * that are big enough, and pick the best one.
888 * This is written as a while loop so we can break out of it,
889 * but we never loop back to the top.
890 */
891 while (xfs_btree_islastblock(cnt_cur, 0)) {
892 xfs_extlen_t bdiff;
893 int besti=0;
894 xfs_extlen_t blen=0;
895 xfs_agblock_t bnew=0;
896
897#if defined(DEBUG) && defined(__KERNEL__)
898 if (!dofirst)
899 break;
900#endif
901 /*
902 * Start from the entry that lookup found, sequence through
903 * all larger free blocks. If we're actually pointing at a
904 * record smaller than maxlen, go to the start of this block,
905 * and skip all those smaller than minlen.
906 */
907 if (ltlen || args->alignment > 1) {
908 cnt_cur->bc_ptrs[0] = 1;
909 do {
910 if ((error = xfs_alloc_get_rec(cnt_cur, &ltbno,
911 &ltlen, &i)))
912 goto error0;
913 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
914 if (ltlen >= args->minlen)
915 break;
Christoph Hellwig637aa502008-10-30 16:55:45 +1100916 if ((error = xfs_btree_increment(cnt_cur, 0, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700917 goto error0;
918 } while (i);
919 ASSERT(ltlen >= args->minlen);
920 if (!i)
921 break;
922 }
923 i = cnt_cur->bc_ptrs[0];
924 for (j = 1, blen = 0, bdiff = 0;
925 !error && j && (blen < args->maxlen || bdiff > 0);
Christoph Hellwig637aa502008-10-30 16:55:45 +1100926 error = xfs_btree_increment(cnt_cur, 0, &j)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700927 /*
928 * For each entry, decide if it's better than
929 * the previous best entry.
930 */
931 if ((error = xfs_alloc_get_rec(cnt_cur, &ltbno, &ltlen, &i)))
932 goto error0;
933 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
Christoph Hellwig86fa8af2011-03-04 12:59:54 +0000934 xfs_alloc_compute_aligned(args, ltbno, ltlen,
935 &ltbnoa, &ltlena);
David Chinnere6430032008-04-17 16:49:49 +1000936 if (ltlena < args->minlen)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700937 continue;
938 args->len = XFS_EXTLEN_MIN(ltlena, args->maxlen);
939 xfs_alloc_fix_len(args);
940 ASSERT(args->len >= args->minlen);
941 if (args->len < blen)
942 continue;
943 ltdiff = xfs_alloc_compute_diff(args->agbno, args->len,
Christoph Hellwige26f0502011-04-24 19:06:15 +0000944 args->alignment, ltbnoa, ltlena, &ltnew);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700945 if (ltnew != NULLAGBLOCK &&
946 (args->len > blen || ltdiff < bdiff)) {
947 bdiff = ltdiff;
948 bnew = ltnew;
949 blen = args->len;
950 besti = cnt_cur->bc_ptrs[0];
951 }
952 }
953 /*
954 * It didn't work. We COULD be in a case where
955 * there's a good record somewhere, so try again.
956 */
957 if (blen == 0)
958 break;
959 /*
960 * Point at the best entry, and retrieve it again.
961 */
962 cnt_cur->bc_ptrs[0] = besti;
963 if ((error = xfs_alloc_get_rec(cnt_cur, &ltbno, &ltlen, &i)))
964 goto error0;
965 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
Christoph Hellwig73523a22010-07-20 17:54:45 +1000966 ASSERT(ltbno + ltlen <= be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700967 args->len = blen;
968 if (!xfs_alloc_fix_minleft(args)) {
969 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
Christoph Hellwig0b1b2132009-12-14 23:14:59 +0000970 trace_xfs_alloc_near_nominleft(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700971 return 0;
972 }
973 blen = args->len;
974 /*
975 * We are allocating starting at bnew for blen blocks.
976 */
977 args->agbno = bnew;
978 ASSERT(bnew >= ltbno);
Christoph Hellwig73523a22010-07-20 17:54:45 +1000979 ASSERT(bnew + blen <= ltbno + ltlen);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700980 /*
981 * Set up a cursor for the by-bno tree.
982 */
Christoph Hellwig561f7d12008-10-30 16:53:59 +1100983 bno_cur_lt = xfs_allocbt_init_cursor(args->mp, args->tp,
984 args->agbp, args->agno, XFS_BTNUM_BNO);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700985 /*
986 * Fix up the btree entries.
987 */
988 if ((error = xfs_alloc_fixup_trees(cnt_cur, bno_cur_lt, ltbno,
989 ltlen, bnew, blen, XFSA_FIXUP_CNT_OK)))
990 goto error0;
991 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
992 xfs_btree_del_cursor(bno_cur_lt, XFS_BTREE_NOERROR);
Christoph Hellwig0b1b2132009-12-14 23:14:59 +0000993
994 trace_xfs_alloc_near_first(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700995 return 0;
996 }
997 /*
998 * Second algorithm.
999 * Search in the by-bno tree to the left and to the right
1000 * simultaneously, until in each case we find a space big enough,
1001 * or run into the edge of the tree. When we run into the edge,
1002 * we deallocate that cursor.
1003 * If both searches succeed, we compare the two spaces and pick
1004 * the better one.
1005 * With alignment, it's possible for both to fail; the upper
1006 * level algorithm that picks allocation groups for allocations
1007 * is not supposed to do this.
1008 */
1009 /*
1010 * Allocate and initialize the cursor for the leftward search.
1011 */
Christoph Hellwig561f7d12008-10-30 16:53:59 +11001012 bno_cur_lt = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
1013 args->agno, XFS_BTNUM_BNO);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001014 /*
1015 * Lookup <= bno to find the leftward search's starting point.
1016 */
1017 if ((error = xfs_alloc_lookup_le(bno_cur_lt, args->agbno, args->maxlen, &i)))
1018 goto error0;
1019 if (!i) {
1020 /*
1021 * Didn't find anything; use this cursor for the rightward
1022 * search.
1023 */
1024 bno_cur_gt = bno_cur_lt;
1025 bno_cur_lt = NULL;
1026 }
1027 /*
1028 * Found something. Duplicate the cursor for the rightward search.
1029 */
1030 else if ((error = xfs_btree_dup_cursor(bno_cur_lt, &bno_cur_gt)))
1031 goto error0;
1032 /*
1033 * Increment the cursor, so we will point at the entry just right
1034 * of the leftward entry if any, or to the leftmost entry.
1035 */
Christoph Hellwig637aa502008-10-30 16:55:45 +11001036 if ((error = xfs_btree_increment(bno_cur_gt, 0, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001037 goto error0;
1038 if (!i) {
1039 /*
1040 * It failed, there are no rightward entries.
1041 */
1042 xfs_btree_del_cursor(bno_cur_gt, XFS_BTREE_NOERROR);
1043 bno_cur_gt = NULL;
1044 }
1045 /*
1046 * Loop going left with the leftward cursor, right with the
1047 * rightward cursor, until either both directions give up or
1048 * we find an entry at least as big as minlen.
1049 */
1050 do {
1051 if (bno_cur_lt) {
1052 if ((error = xfs_alloc_get_rec(bno_cur_lt, &ltbno, &ltlen, &i)))
1053 goto error0;
1054 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
Christoph Hellwig86fa8af2011-03-04 12:59:54 +00001055 xfs_alloc_compute_aligned(args, ltbno, ltlen,
1056 &ltbnoa, &ltlena);
David Chinner12375c82008-04-10 12:21:32 +10001057 if (ltlena >= args->minlen)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001058 break;
Christoph Hellwig8df4da42008-10-30 16:55:58 +11001059 if ((error = xfs_btree_decrement(bno_cur_lt, 0, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001060 goto error0;
1061 if (!i) {
1062 xfs_btree_del_cursor(bno_cur_lt,
1063 XFS_BTREE_NOERROR);
1064 bno_cur_lt = NULL;
1065 }
1066 }
1067 if (bno_cur_gt) {
1068 if ((error = xfs_alloc_get_rec(bno_cur_gt, &gtbno, &gtlen, &i)))
1069 goto error0;
1070 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
Christoph Hellwig86fa8af2011-03-04 12:59:54 +00001071 xfs_alloc_compute_aligned(args, gtbno, gtlen,
1072 &gtbnoa, &gtlena);
David Chinner12375c82008-04-10 12:21:32 +10001073 if (gtlena >= args->minlen)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001074 break;
Christoph Hellwig637aa502008-10-30 16:55:45 +11001075 if ((error = xfs_btree_increment(bno_cur_gt, 0, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001076 goto error0;
1077 if (!i) {
1078 xfs_btree_del_cursor(bno_cur_gt,
1079 XFS_BTREE_NOERROR);
1080 bno_cur_gt = NULL;
1081 }
1082 }
1083 } while (bno_cur_lt || bno_cur_gt);
Christoph Hellwig489a1502010-12-10 15:04:11 +00001084
Linus Torvalds1da177e2005-04-16 15:20:36 -07001085 /*
1086 * Got both cursors still active, need to find better entry.
1087 */
1088 if (bno_cur_lt && bno_cur_gt) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001089 if (ltlena >= args->minlen) {
1090 /*
Christoph Hellwig489a1502010-12-10 15:04:11 +00001091 * Left side is good, look for a right side entry.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001092 */
1093 args->len = XFS_EXTLEN_MIN(ltlena, args->maxlen);
1094 xfs_alloc_fix_len(args);
Christoph Hellwig489a1502010-12-10 15:04:11 +00001095 ltdiff = xfs_alloc_compute_diff(args->agbno, args->len,
Christoph Hellwige26f0502011-04-24 19:06:15 +00001096 args->alignment, ltbnoa, ltlena, &ltnew);
Christoph Hellwig489a1502010-12-10 15:04:11 +00001097
1098 error = xfs_alloc_find_best_extent(args,
1099 &bno_cur_lt, &bno_cur_gt,
Christoph Hellwige26f0502011-04-24 19:06:15 +00001100 ltdiff, &gtbno, &gtlen,
1101 &gtbnoa, &gtlena,
Christoph Hellwig489a1502010-12-10 15:04:11 +00001102 0 /* search right */);
1103 } else {
1104 ASSERT(gtlena >= args->minlen);
1105
Linus Torvalds1da177e2005-04-16 15:20:36 -07001106 /*
Christoph Hellwig489a1502010-12-10 15:04:11 +00001107 * Right side is good, look for a left side entry.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001108 */
1109 args->len = XFS_EXTLEN_MIN(gtlena, args->maxlen);
1110 xfs_alloc_fix_len(args);
Christoph Hellwig489a1502010-12-10 15:04:11 +00001111 gtdiff = xfs_alloc_compute_diff(args->agbno, args->len,
Christoph Hellwige26f0502011-04-24 19:06:15 +00001112 args->alignment, gtbnoa, gtlena, &gtnew);
Christoph Hellwig489a1502010-12-10 15:04:11 +00001113
1114 error = xfs_alloc_find_best_extent(args,
1115 &bno_cur_gt, &bno_cur_lt,
Christoph Hellwige26f0502011-04-24 19:06:15 +00001116 gtdiff, &ltbno, &ltlen,
1117 &ltbnoa, &ltlena,
Christoph Hellwig489a1502010-12-10 15:04:11 +00001118 1 /* search left */);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001119 }
Christoph Hellwig489a1502010-12-10 15:04:11 +00001120
1121 if (error)
1122 goto error0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001123 }
Christoph Hellwig489a1502010-12-10 15:04:11 +00001124
Linus Torvalds1da177e2005-04-16 15:20:36 -07001125 /*
1126 * If we couldn't get anything, give up.
1127 */
1128 if (bno_cur_lt == NULL && bno_cur_gt == NULL) {
Dave Chinnere3a746f52012-07-12 07:40:42 +10001129 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1130
Christoph Hellwige26f0502011-04-24 19:06:15 +00001131 if (!forced++) {
1132 trace_xfs_alloc_near_busy(args);
1133 xfs_log_force(args->mp, XFS_LOG_SYNC);
1134 goto restart;
1135 }
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00001136 trace_xfs_alloc_size_neither(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001137 args->agbno = NULLAGBLOCK;
1138 return 0;
1139 }
Christoph Hellwig489a1502010-12-10 15:04:11 +00001140
Linus Torvalds1da177e2005-04-16 15:20:36 -07001141 /*
1142 * At this point we have selected a freespace entry, either to the
1143 * left or to the right. If it's on the right, copy all the
1144 * useful variables to the "left" set so we only have one
1145 * copy of this code.
1146 */
1147 if (bno_cur_gt) {
1148 bno_cur_lt = bno_cur_gt;
1149 bno_cur_gt = NULL;
1150 ltbno = gtbno;
1151 ltbnoa = gtbnoa;
1152 ltlen = gtlen;
1153 ltlena = gtlena;
1154 j = 1;
1155 } else
1156 j = 0;
Christoph Hellwig489a1502010-12-10 15:04:11 +00001157
Linus Torvalds1da177e2005-04-16 15:20:36 -07001158 /*
1159 * Fix up the length and compute the useful address.
1160 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001161 args->len = XFS_EXTLEN_MIN(ltlena, args->maxlen);
1162 xfs_alloc_fix_len(args);
1163 if (!xfs_alloc_fix_minleft(args)) {
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00001164 trace_xfs_alloc_near_nominleft(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001165 xfs_btree_del_cursor(bno_cur_lt, XFS_BTREE_NOERROR);
1166 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1167 return 0;
1168 }
1169 rlen = args->len;
Christoph Hellwige26f0502011-04-24 19:06:15 +00001170 (void)xfs_alloc_compute_diff(args->agbno, rlen, args->alignment,
1171 ltbnoa, ltlena, &ltnew);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001172 ASSERT(ltnew >= ltbno);
Christoph Hellwige26f0502011-04-24 19:06:15 +00001173 ASSERT(ltnew + rlen <= ltbnoa + ltlena);
Christoph Hellwig16259e72005-11-02 15:11:25 +11001174 ASSERT(ltnew + rlen <= be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001175 args->agbno = ltnew;
Christoph Hellwige26f0502011-04-24 19:06:15 +00001176
Linus Torvalds1da177e2005-04-16 15:20:36 -07001177 if ((error = xfs_alloc_fixup_trees(cnt_cur, bno_cur_lt, ltbno, ltlen,
1178 ltnew, rlen, XFSA_FIXUP_BNO_OK)))
1179 goto error0;
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00001180
1181 if (j)
1182 trace_xfs_alloc_near_greater(args);
1183 else
1184 trace_xfs_alloc_near_lesser(args);
1185
Linus Torvalds1da177e2005-04-16 15:20:36 -07001186 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1187 xfs_btree_del_cursor(bno_cur_lt, XFS_BTREE_NOERROR);
1188 return 0;
1189
1190 error0:
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00001191 trace_xfs_alloc_near_error(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001192 if (cnt_cur != NULL)
1193 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
1194 if (bno_cur_lt != NULL)
1195 xfs_btree_del_cursor(bno_cur_lt, XFS_BTREE_ERROR);
1196 if (bno_cur_gt != NULL)
1197 xfs_btree_del_cursor(bno_cur_gt, XFS_BTREE_ERROR);
1198 return error;
1199}
1200
1201/*
1202 * Allocate a variable extent anywhere in the allocation group agno.
1203 * Extent's length (returned in len) will be between minlen and maxlen,
1204 * and of the form k * prod + mod unless there's nothing that large.
1205 * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
1206 */
1207STATIC int /* error */
1208xfs_alloc_ag_vextent_size(
1209 xfs_alloc_arg_t *args) /* allocation argument structure */
1210{
1211 xfs_btree_cur_t *bno_cur; /* cursor for bno btree */
1212 xfs_btree_cur_t *cnt_cur; /* cursor for cnt btree */
1213 int error; /* error result */
1214 xfs_agblock_t fbno; /* start of found freespace */
1215 xfs_extlen_t flen; /* length of found freespace */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001216 int i; /* temp status variable */
1217 xfs_agblock_t rbno; /* returned block number */
1218 xfs_extlen_t rlen; /* length of returned extent */
Christoph Hellwige26f0502011-04-24 19:06:15 +00001219 int forced = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001220
Christoph Hellwige26f0502011-04-24 19:06:15 +00001221restart:
Linus Torvalds1da177e2005-04-16 15:20:36 -07001222 /*
1223 * Allocate and initialize a cursor for the by-size btree.
1224 */
Christoph Hellwig561f7d12008-10-30 16:53:59 +11001225 cnt_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
1226 args->agno, XFS_BTNUM_CNT);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001227 bno_cur = NULL;
Christoph Hellwige26f0502011-04-24 19:06:15 +00001228
Linus Torvalds1da177e2005-04-16 15:20:36 -07001229 /*
1230 * Look for an entry >= maxlen+alignment-1 blocks.
1231 */
1232 if ((error = xfs_alloc_lookup_ge(cnt_cur, 0,
1233 args->maxlen + args->alignment - 1, &i)))
1234 goto error0;
Christoph Hellwige26f0502011-04-24 19:06:15 +00001235
Linus Torvalds1da177e2005-04-16 15:20:36 -07001236 /*
Christoph Hellwige26f0502011-04-24 19:06:15 +00001237 * If none or we have busy extents that we cannot allocate from, then
1238 * we have to settle for a smaller extent. In the case that there are
1239 * no large extents, this will return the last entry in the tree unless
1240 * the tree is empty. In the case that there are only busy large
1241 * extents, this will return the largest small extent unless there
1242 * are no smaller extents available.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001243 */
Christoph Hellwige26f0502011-04-24 19:06:15 +00001244 if (!i || forced > 1) {
1245 error = xfs_alloc_ag_vextent_small(args, cnt_cur,
1246 &fbno, &flen, &i);
1247 if (error)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001248 goto error0;
1249 if (i == 0 || flen == 0) {
1250 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00001251 trace_xfs_alloc_size_noentry(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001252 return 0;
1253 }
1254 ASSERT(i == 1);
Christoph Hellwige26f0502011-04-24 19:06:15 +00001255 xfs_alloc_compute_aligned(args, fbno, flen, &rbno, &rlen);
1256 } else {
1257 /*
1258 * Search for a non-busy extent that is large enough.
1259 * If we are at low space, don't check, or if we fall of
1260 * the end of the btree, turn off the busy check and
1261 * restart.
1262 */
1263 for (;;) {
1264 error = xfs_alloc_get_rec(cnt_cur, &fbno, &flen, &i);
1265 if (error)
1266 goto error0;
1267 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1268
1269 xfs_alloc_compute_aligned(args, fbno, flen,
1270 &rbno, &rlen);
1271
1272 if (rlen >= args->maxlen)
1273 break;
1274
1275 error = xfs_btree_increment(cnt_cur, 0, &i);
1276 if (error)
1277 goto error0;
1278 if (i == 0) {
1279 /*
1280 * Our only valid extents must have been busy.
1281 * Make it unbusy by forcing the log out and
1282 * retrying. If we've been here before, forcing
1283 * the log isn't making the extents available,
1284 * which means they have probably been freed in
1285 * this transaction. In that case, we have to
1286 * give up on them and we'll attempt a minlen
1287 * allocation the next time around.
1288 */
1289 xfs_btree_del_cursor(cnt_cur,
1290 XFS_BTREE_NOERROR);
1291 trace_xfs_alloc_size_busy(args);
1292 if (!forced++)
1293 xfs_log_force(args->mp, XFS_LOG_SYNC);
1294 goto restart;
1295 }
1296 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001297 }
Christoph Hellwige26f0502011-04-24 19:06:15 +00001298
Linus Torvalds1da177e2005-04-16 15:20:36 -07001299 /*
1300 * In the first case above, we got the last entry in the
1301 * by-size btree. Now we check to see if the space hits maxlen
1302 * once aligned; if not, we search left for something better.
1303 * This can't happen in the second case above.
1304 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001305 rlen = XFS_EXTLEN_MIN(args->maxlen, rlen);
1306 XFS_WANT_CORRUPTED_GOTO(rlen == 0 ||
1307 (rlen <= flen && rbno + rlen <= fbno + flen), error0);
1308 if (rlen < args->maxlen) {
1309 xfs_agblock_t bestfbno;
1310 xfs_extlen_t bestflen;
1311 xfs_agblock_t bestrbno;
1312 xfs_extlen_t bestrlen;
1313
1314 bestrlen = rlen;
1315 bestrbno = rbno;
1316 bestflen = flen;
1317 bestfbno = fbno;
1318 for (;;) {
Christoph Hellwig8df4da42008-10-30 16:55:58 +11001319 if ((error = xfs_btree_decrement(cnt_cur, 0, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001320 goto error0;
1321 if (i == 0)
1322 break;
1323 if ((error = xfs_alloc_get_rec(cnt_cur, &fbno, &flen,
1324 &i)))
1325 goto error0;
1326 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1327 if (flen < bestrlen)
1328 break;
Christoph Hellwig86fa8af2011-03-04 12:59:54 +00001329 xfs_alloc_compute_aligned(args, fbno, flen,
1330 &rbno, &rlen);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001331 rlen = XFS_EXTLEN_MIN(args->maxlen, rlen);
1332 XFS_WANT_CORRUPTED_GOTO(rlen == 0 ||
1333 (rlen <= flen && rbno + rlen <= fbno + flen),
1334 error0);
1335 if (rlen > bestrlen) {
1336 bestrlen = rlen;
1337 bestrbno = rbno;
1338 bestflen = flen;
1339 bestfbno = fbno;
1340 if (rlen == args->maxlen)
1341 break;
1342 }
1343 }
1344 if ((error = xfs_alloc_lookup_eq(cnt_cur, bestfbno, bestflen,
1345 &i)))
1346 goto error0;
1347 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1348 rlen = bestrlen;
1349 rbno = bestrbno;
1350 flen = bestflen;
1351 fbno = bestfbno;
1352 }
1353 args->wasfromfl = 0;
1354 /*
1355 * Fix up the length.
1356 */
1357 args->len = rlen;
Christoph Hellwige26f0502011-04-24 19:06:15 +00001358 if (rlen < args->minlen) {
1359 if (!forced++) {
1360 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1361 trace_xfs_alloc_size_busy(args);
1362 xfs_log_force(args->mp, XFS_LOG_SYNC);
1363 goto restart;
1364 }
1365 goto out_nominleft;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001366 }
Christoph Hellwige26f0502011-04-24 19:06:15 +00001367 xfs_alloc_fix_len(args);
1368
1369 if (!xfs_alloc_fix_minleft(args))
1370 goto out_nominleft;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001371 rlen = args->len;
1372 XFS_WANT_CORRUPTED_GOTO(rlen <= flen, error0);
1373 /*
1374 * Allocate and initialize a cursor for the by-block tree.
1375 */
Christoph Hellwig561f7d12008-10-30 16:53:59 +11001376 bno_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
1377 args->agno, XFS_BTNUM_BNO);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001378 if ((error = xfs_alloc_fixup_trees(cnt_cur, bno_cur, fbno, flen,
1379 rbno, rlen, XFSA_FIXUP_CNT_OK)))
1380 goto error0;
1381 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1382 xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
1383 cnt_cur = bno_cur = NULL;
1384 args->len = rlen;
1385 args->agbno = rbno;
1386 XFS_WANT_CORRUPTED_GOTO(
1387 args->agbno + args->len <=
Christoph Hellwig16259e72005-11-02 15:11:25 +11001388 be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length),
Linus Torvalds1da177e2005-04-16 15:20:36 -07001389 error0);
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00001390 trace_xfs_alloc_size_done(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001391 return 0;
1392
1393error0:
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00001394 trace_xfs_alloc_size_error(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001395 if (cnt_cur)
1396 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
1397 if (bno_cur)
1398 xfs_btree_del_cursor(bno_cur, XFS_BTREE_ERROR);
1399 return error;
Christoph Hellwige26f0502011-04-24 19:06:15 +00001400
1401out_nominleft:
1402 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1403 trace_xfs_alloc_size_nominleft(args);
1404 args->agbno = NULLAGBLOCK;
1405 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001406}
1407
1408/*
1409 * Deal with the case where only small freespaces remain.
1410 * Either return the contents of the last freespace record,
1411 * or allocate space from the freelist if there is nothing in the tree.
1412 */
1413STATIC int /* error */
1414xfs_alloc_ag_vextent_small(
1415 xfs_alloc_arg_t *args, /* allocation argument structure */
1416 xfs_btree_cur_t *ccur, /* by-size cursor */
1417 xfs_agblock_t *fbnop, /* result block number */
1418 xfs_extlen_t *flenp, /* result length */
1419 int *stat) /* status: 0-freelist, 1-normal/none */
1420{
1421 int error;
1422 xfs_agblock_t fbno;
1423 xfs_extlen_t flen;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001424 int i;
1425
Christoph Hellwig8df4da42008-10-30 16:55:58 +11001426 if ((error = xfs_btree_decrement(ccur, 0, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001427 goto error0;
1428 if (i) {
1429 if ((error = xfs_alloc_get_rec(ccur, &fbno, &flen, &i)))
1430 goto error0;
1431 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1432 }
1433 /*
1434 * Nothing in the btree, try the freelist. Make sure
1435 * to respect minleft even when pulling from the
1436 * freelist.
1437 */
1438 else if (args->minlen == 1 && args->alignment == 1 && !args->isfl &&
Christoph Hellwig16259e72005-11-02 15:11:25 +11001439 (be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_flcount)
1440 > args->minleft)) {
David Chinner92821e22007-05-24 15:26:31 +10001441 error = xfs_alloc_get_freelist(args->tp, args->agbp, &fbno, 0);
1442 if (error)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001443 goto error0;
1444 if (fbno != NULLAGBLOCK) {
Dave Chinner4ecbfe62012-04-29 10:41:10 +00001445 xfs_extent_busy_reuse(args->mp, args->agno, fbno, 1,
Christoph Hellwig97d3ac72011-04-24 19:06:16 +00001446 args->userdata);
1447
Linus Torvalds1da177e2005-04-16 15:20:36 -07001448 if (args->userdata) {
1449 xfs_buf_t *bp;
1450
1451 bp = xfs_btree_get_bufs(args->mp, args->tp,
1452 args->agno, fbno, 0);
1453 xfs_trans_binval(args->tp, bp);
1454 }
1455 args->len = 1;
1456 args->agbno = fbno;
1457 XFS_WANT_CORRUPTED_GOTO(
1458 args->agbno + args->len <=
Christoph Hellwig16259e72005-11-02 15:11:25 +11001459 be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length),
Linus Torvalds1da177e2005-04-16 15:20:36 -07001460 error0);
1461 args->wasfromfl = 1;
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00001462 trace_xfs_alloc_small_freelist(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001463 *stat = 0;
1464 return 0;
1465 }
1466 /*
1467 * Nothing in the freelist.
1468 */
1469 else
1470 flen = 0;
1471 }
1472 /*
1473 * Can't allocate from the freelist for some reason.
1474 */
Nathan Scottd432c802006-09-28 11:03:44 +10001475 else {
1476 fbno = NULLAGBLOCK;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001477 flen = 0;
Nathan Scottd432c802006-09-28 11:03:44 +10001478 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001479 /*
1480 * Can't do the allocation, give up.
1481 */
1482 if (flen < args->minlen) {
1483 args->agbno = NULLAGBLOCK;
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00001484 trace_xfs_alloc_small_notenough(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001485 flen = 0;
1486 }
1487 *fbnop = fbno;
1488 *flenp = flen;
1489 *stat = 1;
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00001490 trace_xfs_alloc_small_done(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001491 return 0;
1492
1493error0:
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00001494 trace_xfs_alloc_small_error(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001495 return error;
1496}
1497
1498/*
1499 * Free the extent starting at agno/bno for length.
1500 */
1501STATIC int /* error */
1502xfs_free_ag_extent(
1503 xfs_trans_t *tp, /* transaction pointer */
1504 xfs_buf_t *agbp, /* buffer for a.g. freelist header */
1505 xfs_agnumber_t agno, /* allocation group number */
1506 xfs_agblock_t bno, /* starting block number */
1507 xfs_extlen_t len, /* length of extent */
1508 int isfl) /* set if is freelist blocks - no sb acctg */
1509{
1510 xfs_btree_cur_t *bno_cur; /* cursor for by-block btree */
1511 xfs_btree_cur_t *cnt_cur; /* cursor for by-size btree */
1512 int error; /* error return value */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001513 xfs_agblock_t gtbno; /* start of right neighbor block */
1514 xfs_extlen_t gtlen; /* length of right neighbor block */
1515 int haveleft; /* have a left neighbor block */
1516 int haveright; /* have a right neighbor block */
1517 int i; /* temp, result code */
1518 xfs_agblock_t ltbno; /* start of left neighbor block */
1519 xfs_extlen_t ltlen; /* length of left neighbor block */
1520 xfs_mount_t *mp; /* mount point struct for filesystem */
1521 xfs_agblock_t nbno; /* new starting block of freespace */
1522 xfs_extlen_t nlen; /* new length of freespace */
Christoph Hellwigecb69282011-03-04 12:59:55 +00001523 xfs_perag_t *pag; /* per allocation group data */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001524
1525 mp = tp->t_mountp;
1526 /*
1527 * Allocate and initialize a cursor for the by-block btree.
1528 */
Christoph Hellwig561f7d12008-10-30 16:53:59 +11001529 bno_cur = xfs_allocbt_init_cursor(mp, tp, agbp, agno, XFS_BTNUM_BNO);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001530 cnt_cur = NULL;
1531 /*
1532 * Look for a neighboring block on the left (lower block numbers)
1533 * that is contiguous with this space.
1534 */
1535 if ((error = xfs_alloc_lookup_le(bno_cur, bno, len, &haveleft)))
1536 goto error0;
1537 if (haveleft) {
1538 /*
1539 * There is a block to our left.
1540 */
1541 if ((error = xfs_alloc_get_rec(bno_cur, &ltbno, &ltlen, &i)))
1542 goto error0;
1543 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1544 /*
1545 * It's not contiguous, though.
1546 */
1547 if (ltbno + ltlen < bno)
1548 haveleft = 0;
1549 else {
1550 /*
1551 * If this failure happens the request to free this
1552 * space was invalid, it's (partly) already free.
1553 * Very bad.
1554 */
1555 XFS_WANT_CORRUPTED_GOTO(ltbno + ltlen <= bno, error0);
1556 }
1557 }
1558 /*
1559 * Look for a neighboring block on the right (higher block numbers)
1560 * that is contiguous with this space.
1561 */
Christoph Hellwig637aa502008-10-30 16:55:45 +11001562 if ((error = xfs_btree_increment(bno_cur, 0, &haveright)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001563 goto error0;
1564 if (haveright) {
1565 /*
1566 * There is a block to our right.
1567 */
1568 if ((error = xfs_alloc_get_rec(bno_cur, &gtbno, &gtlen, &i)))
1569 goto error0;
1570 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1571 /*
1572 * It's not contiguous, though.
1573 */
1574 if (bno + len < gtbno)
1575 haveright = 0;
1576 else {
1577 /*
1578 * If this failure happens the request to free this
1579 * space was invalid, it's (partly) already free.
1580 * Very bad.
1581 */
1582 XFS_WANT_CORRUPTED_GOTO(gtbno >= bno + len, error0);
1583 }
1584 }
1585 /*
1586 * Now allocate and initialize a cursor for the by-size tree.
1587 */
Christoph Hellwig561f7d12008-10-30 16:53:59 +11001588 cnt_cur = xfs_allocbt_init_cursor(mp, tp, agbp, agno, XFS_BTNUM_CNT);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001589 /*
1590 * Have both left and right contiguous neighbors.
1591 * Merge all three into a single free block.
1592 */
1593 if (haveleft && haveright) {
1594 /*
1595 * Delete the old by-size entry on the left.
1596 */
1597 if ((error = xfs_alloc_lookup_eq(cnt_cur, ltbno, ltlen, &i)))
1598 goto error0;
1599 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
Christoph Hellwig91cca5df2008-10-30 16:58:01 +11001600 if ((error = xfs_btree_delete(cnt_cur, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001601 goto error0;
1602 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1603 /*
1604 * Delete the old by-size entry on the right.
1605 */
1606 if ((error = xfs_alloc_lookup_eq(cnt_cur, gtbno, gtlen, &i)))
1607 goto error0;
1608 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
Christoph Hellwig91cca5df2008-10-30 16:58:01 +11001609 if ((error = xfs_btree_delete(cnt_cur, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001610 goto error0;
1611 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1612 /*
1613 * Delete the old by-block entry for the right block.
1614 */
Christoph Hellwig91cca5df2008-10-30 16:58:01 +11001615 if ((error = xfs_btree_delete(bno_cur, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001616 goto error0;
1617 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1618 /*
1619 * Move the by-block cursor back to the left neighbor.
1620 */
Christoph Hellwig8df4da42008-10-30 16:55:58 +11001621 if ((error = xfs_btree_decrement(bno_cur, 0, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001622 goto error0;
1623 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1624#ifdef DEBUG
1625 /*
1626 * Check that this is the right record: delete didn't
1627 * mangle the cursor.
1628 */
1629 {
1630 xfs_agblock_t xxbno;
1631 xfs_extlen_t xxlen;
1632
1633 if ((error = xfs_alloc_get_rec(bno_cur, &xxbno, &xxlen,
1634 &i)))
1635 goto error0;
1636 XFS_WANT_CORRUPTED_GOTO(
1637 i == 1 && xxbno == ltbno && xxlen == ltlen,
1638 error0);
1639 }
1640#endif
1641 /*
1642 * Update remaining by-block entry to the new, joined block.
1643 */
1644 nbno = ltbno;
1645 nlen = len + ltlen + gtlen;
1646 if ((error = xfs_alloc_update(bno_cur, nbno, nlen)))
1647 goto error0;
1648 }
1649 /*
1650 * Have only a left contiguous neighbor.
1651 * Merge it together with the new freespace.
1652 */
1653 else if (haveleft) {
1654 /*
1655 * Delete the old by-size entry on the left.
1656 */
1657 if ((error = xfs_alloc_lookup_eq(cnt_cur, ltbno, ltlen, &i)))
1658 goto error0;
1659 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
Christoph Hellwig91cca5df2008-10-30 16:58:01 +11001660 if ((error = xfs_btree_delete(cnt_cur, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001661 goto error0;
1662 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1663 /*
1664 * Back up the by-block cursor to the left neighbor, and
1665 * update its length.
1666 */
Christoph Hellwig8df4da42008-10-30 16:55:58 +11001667 if ((error = xfs_btree_decrement(bno_cur, 0, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001668 goto error0;
1669 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1670 nbno = ltbno;
1671 nlen = len + ltlen;
1672 if ((error = xfs_alloc_update(bno_cur, nbno, nlen)))
1673 goto error0;
1674 }
1675 /*
1676 * Have only a right contiguous neighbor.
1677 * Merge it together with the new freespace.
1678 */
1679 else if (haveright) {
1680 /*
1681 * Delete the old by-size entry on the right.
1682 */
1683 if ((error = xfs_alloc_lookup_eq(cnt_cur, gtbno, gtlen, &i)))
1684 goto error0;
1685 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
Christoph Hellwig91cca5df2008-10-30 16:58:01 +11001686 if ((error = xfs_btree_delete(cnt_cur, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001687 goto error0;
1688 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1689 /*
1690 * Update the starting block and length of the right
1691 * neighbor in the by-block tree.
1692 */
1693 nbno = bno;
1694 nlen = len + gtlen;
1695 if ((error = xfs_alloc_update(bno_cur, nbno, nlen)))
1696 goto error0;
1697 }
1698 /*
1699 * No contiguous neighbors.
1700 * Insert the new freespace into the by-block tree.
1701 */
1702 else {
1703 nbno = bno;
1704 nlen = len;
Christoph Hellwig4b22a572008-10-30 16:57:40 +11001705 if ((error = xfs_btree_insert(bno_cur, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001706 goto error0;
1707 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1708 }
1709 xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
1710 bno_cur = NULL;
1711 /*
1712 * In all cases we need to insert the new freespace in the by-size tree.
1713 */
1714 if ((error = xfs_alloc_lookup_eq(cnt_cur, nbno, nlen, &i)))
1715 goto error0;
1716 XFS_WANT_CORRUPTED_GOTO(i == 0, error0);
Christoph Hellwig4b22a572008-10-30 16:57:40 +11001717 if ((error = xfs_btree_insert(cnt_cur, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001718 goto error0;
1719 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1720 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1721 cnt_cur = NULL;
Christoph Hellwigecb69282011-03-04 12:59:55 +00001722
Linus Torvalds1da177e2005-04-16 15:20:36 -07001723 /*
1724 * Update the freespace totals in the ag and superblock.
1725 */
Christoph Hellwigecb69282011-03-04 12:59:55 +00001726 pag = xfs_perag_get(mp, agno);
1727 error = xfs_alloc_update_counters(tp, pag, agbp, len);
1728 xfs_perag_put(pag);
1729 if (error)
1730 goto error0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001731
Christoph Hellwigecb69282011-03-04 12:59:55 +00001732 if (!isfl)
1733 xfs_trans_mod_sb(tp, XFS_TRANS_SB_FDBLOCKS, (long)len);
1734 XFS_STATS_INC(xs_freex);
1735 XFS_STATS_ADD(xs_freeb, len);
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00001736
1737 trace_xfs_free_extent(mp, agno, bno, len, isfl, haveleft, haveright);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001738
Linus Torvalds1da177e2005-04-16 15:20:36 -07001739 return 0;
1740
1741 error0:
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00001742 trace_xfs_free_extent(mp, agno, bno, len, isfl, -1, -1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001743 if (bno_cur)
1744 xfs_btree_del_cursor(bno_cur, XFS_BTREE_ERROR);
1745 if (cnt_cur)
1746 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
1747 return error;
1748}
1749
1750/*
1751 * Visible (exported) allocation/free functions.
1752 * Some of these are used just by xfs_alloc_btree.c and this file.
1753 */
1754
1755/*
1756 * Compute and fill in value of m_ag_maxlevels.
1757 */
1758void
1759xfs_alloc_compute_maxlevels(
1760 xfs_mount_t *mp) /* file system mount structure */
1761{
1762 int level;
1763 uint maxblocks;
1764 uint maxleafents;
1765 int minleafrecs;
1766 int minnoderecs;
1767
1768 maxleafents = (mp->m_sb.sb_agblocks + 1) / 2;
1769 minleafrecs = mp->m_alloc_mnr[0];
1770 minnoderecs = mp->m_alloc_mnr[1];
1771 maxblocks = (maxleafents + minleafrecs - 1) / minleafrecs;
1772 for (level = 1; maxblocks > 1; level++)
1773 maxblocks = (maxblocks + minnoderecs - 1) / minnoderecs;
1774 mp->m_ag_maxlevels = level;
1775}
1776
1777/*
Dave Chinner6cc87642009-03-16 08:29:46 +01001778 * Find the length of the longest extent in an AG.
1779 */
1780xfs_extlen_t
1781xfs_alloc_longest_free_extent(
1782 struct xfs_mount *mp,
1783 struct xfs_perag *pag)
1784{
1785 xfs_extlen_t need, delta = 0;
1786
1787 need = XFS_MIN_FREELIST_PAG(pag, mp);
1788 if (need > pag->pagf_flcount)
1789 delta = need - pag->pagf_flcount;
1790
1791 if (pag->pagf_longest > delta)
1792 return pag->pagf_longest - delta;
1793 return pag->pagf_flcount > 0 || pag->pagf_longest > 0;
1794}
1795
1796/*
Linus Torvalds1da177e2005-04-16 15:20:36 -07001797 * Decide whether to use this allocation group for this allocation.
1798 * If so, fix up the btree freelist's size.
1799 */
1800STATIC int /* error */
1801xfs_alloc_fix_freelist(
1802 xfs_alloc_arg_t *args, /* allocation argument structure */
1803 int flags) /* XFS_ALLOC_FLAG_... */
1804{
1805 xfs_buf_t *agbp; /* agf buffer pointer */
1806 xfs_agf_t *agf; /* a.g. freespace structure pointer */
1807 xfs_buf_t *agflbp;/* agfl buffer pointer */
1808 xfs_agblock_t bno; /* freelist block */
1809 xfs_extlen_t delta; /* new blocks needed in freelist */
1810 int error; /* error result code */
1811 xfs_extlen_t longest;/* longest extent in allocation group */
1812 xfs_mount_t *mp; /* file system mount point structure */
1813 xfs_extlen_t need; /* total blocks needed in freelist */
1814 xfs_perag_t *pag; /* per-ag information structure */
1815 xfs_alloc_arg_t targs; /* local allocation arguments */
1816 xfs_trans_t *tp; /* transaction pointer */
1817
1818 mp = args->mp;
1819
1820 pag = args->pag;
1821 tp = args->tp;
1822 if (!pag->pagf_init) {
1823 if ((error = xfs_alloc_read_agf(mp, tp, args->agno, flags,
1824 &agbp)))
1825 return error;
1826 if (!pag->pagf_init) {
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 } else
1833 agbp = NULL;
1834
Nathan Scott0e1edbd2006-08-10 14:40:41 +10001835 /*
1836 * If this is a metadata preferred pag and we are user data
Linus Torvalds1da177e2005-04-16 15:20:36 -07001837 * then try somewhere else if we are not being asked to
1838 * try harder at this point
1839 */
Nathan Scott0e1edbd2006-08-10 14:40:41 +10001840 if (pag->pagf_metadata && args->userdata &&
1841 (flags & XFS_ALLOC_FLAG_TRYLOCK)) {
1842 ASSERT(!(flags & XFS_ALLOC_FLAG_FREEING));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001843 args->agbp = NULL;
1844 return 0;
1845 }
1846
Nathan Scott0e1edbd2006-08-10 14:40:41 +10001847 if (!(flags & XFS_ALLOC_FLAG_FREEING)) {
Nathan Scott0e1edbd2006-08-10 14:40:41 +10001848 /*
1849 * If it looks like there isn't a long enough extent, or enough
1850 * total blocks, reject it.
1851 */
Dave Chinner6cc87642009-03-16 08:29:46 +01001852 need = XFS_MIN_FREELIST_PAG(pag, mp);
1853 longest = xfs_alloc_longest_free_extent(mp, pag);
Nathan Scott0e1edbd2006-08-10 14:40:41 +10001854 if ((args->minlen + args->alignment + args->minalignslop - 1) >
1855 longest ||
1856 ((int)(pag->pagf_freeblks + pag->pagf_flcount -
1857 need - args->total) < (int)args->minleft)) {
1858 if (agbp)
1859 xfs_trans_brelse(tp, agbp);
1860 args->agbp = NULL;
1861 return 0;
1862 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001863 }
Nathan Scott0e1edbd2006-08-10 14:40:41 +10001864
Linus Torvalds1da177e2005-04-16 15:20:36 -07001865 /*
1866 * Get the a.g. freespace buffer.
1867 * Can fail if we're not blocking on locks, and it's held.
1868 */
1869 if (agbp == NULL) {
1870 if ((error = xfs_alloc_read_agf(mp, tp, args->agno, flags,
1871 &agbp)))
1872 return error;
1873 if (agbp == NULL) {
Nathan Scott0e1edbd2006-08-10 14:40:41 +10001874 ASSERT(flags & XFS_ALLOC_FLAG_TRYLOCK);
1875 ASSERT(!(flags & XFS_ALLOC_FLAG_FREEING));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001876 args->agbp = NULL;
1877 return 0;
1878 }
1879 }
1880 /*
1881 * Figure out how many blocks we should have in the freelist.
1882 */
1883 agf = XFS_BUF_TO_AGF(agbp);
1884 need = XFS_MIN_FREELIST(agf, mp);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001885 /*
1886 * If there isn't enough total or single-extent, reject it.
1887 */
Nathan Scott0e1edbd2006-08-10 14:40:41 +10001888 if (!(flags & XFS_ALLOC_FLAG_FREEING)) {
1889 delta = need > be32_to_cpu(agf->agf_flcount) ?
1890 (need - be32_to_cpu(agf->agf_flcount)) : 0;
1891 longest = be32_to_cpu(agf->agf_longest);
1892 longest = (longest > delta) ? (longest - delta) :
1893 (be32_to_cpu(agf->agf_flcount) > 0 || longest > 0);
1894 if ((args->minlen + args->alignment + args->minalignslop - 1) >
1895 longest ||
1896 ((int)(be32_to_cpu(agf->agf_freeblks) +
1897 be32_to_cpu(agf->agf_flcount) - need - args->total) <
1898 (int)args->minleft)) {
1899 xfs_trans_brelse(tp, agbp);
1900 args->agbp = NULL;
1901 return 0;
1902 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001903 }
1904 /*
1905 * Make the freelist shorter if it's too long.
1906 */
Christoph Hellwig16259e72005-11-02 15:11:25 +11001907 while (be32_to_cpu(agf->agf_flcount) > need) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001908 xfs_buf_t *bp;
1909
David Chinner92821e22007-05-24 15:26:31 +10001910 error = xfs_alloc_get_freelist(tp, agbp, &bno, 0);
1911 if (error)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001912 return error;
1913 if ((error = xfs_free_ag_extent(tp, agbp, args->agno, bno, 1, 1)))
1914 return error;
1915 bp = xfs_btree_get_bufs(mp, tp, args->agno, bno, 0);
1916 xfs_trans_binval(tp, bp);
1917 }
1918 /*
1919 * Initialize the args structure.
1920 */
Mark Tinguelya0041682012-09-20 13:16:45 -05001921 memset(&targs, 0, sizeof(targs));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001922 targs.tp = tp;
1923 targs.mp = mp;
1924 targs.agbp = agbp;
1925 targs.agno = args->agno;
1926 targs.mod = targs.minleft = targs.wasdel = targs.userdata =
1927 targs.minalignslop = 0;
1928 targs.alignment = targs.minlen = targs.prod = targs.isfl = 1;
1929 targs.type = XFS_ALLOCTYPE_THIS_AG;
1930 targs.pag = pag;
1931 if ((error = xfs_alloc_read_agfl(mp, tp, targs.agno, &agflbp)))
1932 return error;
1933 /*
1934 * Make the freelist longer if it's too short.
1935 */
Christoph Hellwig16259e72005-11-02 15:11:25 +11001936 while (be32_to_cpu(agf->agf_flcount) < need) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001937 targs.agbno = 0;
Christoph Hellwig16259e72005-11-02 15:11:25 +11001938 targs.maxlen = need - be32_to_cpu(agf->agf_flcount);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001939 /*
1940 * Allocate as many blocks as possible at once.
1941 */
Nathan Scotte63a3692006-05-08 19:51:58 +10001942 if ((error = xfs_alloc_ag_vextent(&targs))) {
1943 xfs_trans_brelse(tp, agflbp);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001944 return error;
Nathan Scotte63a3692006-05-08 19:51:58 +10001945 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001946 /*
1947 * Stop if we run out. Won't happen if callers are obeying
1948 * the restrictions correctly. Can happen for free calls
1949 * on a completely full ag.
1950 */
Yingping Lud210a282006-06-09 14:55:18 +10001951 if (targs.agbno == NULLAGBLOCK) {
Nathan Scott0e1edbd2006-08-10 14:40:41 +10001952 if (flags & XFS_ALLOC_FLAG_FREEING)
1953 break;
1954 xfs_trans_brelse(tp, agflbp);
1955 args->agbp = NULL;
1956 return 0;
Yingping Lud210a282006-06-09 14:55:18 +10001957 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001958 /*
1959 * Put each allocated block on the list.
1960 */
1961 for (bno = targs.agbno; bno < targs.agbno + targs.len; bno++) {
David Chinner92821e22007-05-24 15:26:31 +10001962 error = xfs_alloc_put_freelist(tp, agbp,
1963 agflbp, bno, 0);
1964 if (error)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001965 return error;
1966 }
1967 }
Nathan Scotte63a3692006-05-08 19:51:58 +10001968 xfs_trans_brelse(tp, agflbp);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001969 args->agbp = agbp;
1970 return 0;
1971}
1972
1973/*
1974 * Get a block from the freelist.
1975 * Returns with the buffer for the block gotten.
1976 */
1977int /* error */
1978xfs_alloc_get_freelist(
1979 xfs_trans_t *tp, /* transaction pointer */
1980 xfs_buf_t *agbp, /* buffer containing the agf structure */
David Chinner92821e22007-05-24 15:26:31 +10001981 xfs_agblock_t *bnop, /* block address retrieved from freelist */
1982 int btreeblk) /* destination is a AGF btree */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001983{
1984 xfs_agf_t *agf; /* a.g. freespace structure */
1985 xfs_agfl_t *agfl; /* a.g. freelist structure */
1986 xfs_buf_t *agflbp;/* buffer for a.g. freelist structure */
1987 xfs_agblock_t bno; /* block number returned */
1988 int error;
David Chinner92821e22007-05-24 15:26:31 +10001989 int logflags;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001990 xfs_mount_t *mp; /* mount structure */
1991 xfs_perag_t *pag; /* per allocation group data */
1992
1993 agf = XFS_BUF_TO_AGF(agbp);
1994 /*
1995 * Freelist is empty, give up.
1996 */
1997 if (!agf->agf_flcount) {
1998 *bnop = NULLAGBLOCK;
1999 return 0;
2000 }
2001 /*
2002 * Read the array of free blocks.
2003 */
2004 mp = tp->t_mountp;
2005 if ((error = xfs_alloc_read_agfl(mp, tp,
Christoph Hellwig16259e72005-11-02 15:11:25 +11002006 be32_to_cpu(agf->agf_seqno), &agflbp)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07002007 return error;
2008 agfl = XFS_BUF_TO_AGFL(agflbp);
2009 /*
2010 * Get the block number and update the data structures.
2011 */
Christoph Hellwige2101002006-09-28 10:56:51 +10002012 bno = be32_to_cpu(agfl->agfl_bno[be32_to_cpu(agf->agf_flfirst)]);
Marcin Slusarz413d57c2008-02-13 15:03:29 -08002013 be32_add_cpu(&agf->agf_flfirst, 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002014 xfs_trans_brelse(tp, agflbp);
Christoph Hellwig16259e72005-11-02 15:11:25 +11002015 if (be32_to_cpu(agf->agf_flfirst) == XFS_AGFL_SIZE(mp))
Linus Torvalds1da177e2005-04-16 15:20:36 -07002016 agf->agf_flfirst = 0;
Dave Chinnera862e0f2010-01-11 11:47:41 +00002017
2018 pag = xfs_perag_get(mp, be32_to_cpu(agf->agf_seqno));
Marcin Slusarz413d57c2008-02-13 15:03:29 -08002019 be32_add_cpu(&agf->agf_flcount, -1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002020 xfs_trans_agflist_delta(tp, -1);
2021 pag->pagf_flcount--;
Dave Chinnera862e0f2010-01-11 11:47:41 +00002022 xfs_perag_put(pag);
David Chinner92821e22007-05-24 15:26:31 +10002023
2024 logflags = XFS_AGF_FLFIRST | XFS_AGF_FLCOUNT;
2025 if (btreeblk) {
Marcin Slusarz413d57c2008-02-13 15:03:29 -08002026 be32_add_cpu(&agf->agf_btreeblks, 1);
David Chinner92821e22007-05-24 15:26:31 +10002027 pag->pagf_btreeblks++;
2028 logflags |= XFS_AGF_BTREEBLKS;
2029 }
2030
David Chinner92821e22007-05-24 15:26:31 +10002031 xfs_alloc_log_agf(tp, agbp, logflags);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002032 *bnop = bno;
2033
Linus Torvalds1da177e2005-04-16 15:20:36 -07002034 return 0;
2035}
2036
2037/*
2038 * Log the given fields from the agf structure.
2039 */
2040void
2041xfs_alloc_log_agf(
2042 xfs_trans_t *tp, /* transaction pointer */
2043 xfs_buf_t *bp, /* buffer for a.g. freelist header */
2044 int fields) /* mask of fields to be logged (XFS_AGF_...) */
2045{
2046 int first; /* first byte offset */
2047 int last; /* last byte offset */
2048 static const short offsets[] = {
2049 offsetof(xfs_agf_t, agf_magicnum),
2050 offsetof(xfs_agf_t, agf_versionnum),
2051 offsetof(xfs_agf_t, agf_seqno),
2052 offsetof(xfs_agf_t, agf_length),
2053 offsetof(xfs_agf_t, agf_roots[0]),
2054 offsetof(xfs_agf_t, agf_levels[0]),
2055 offsetof(xfs_agf_t, agf_flfirst),
2056 offsetof(xfs_agf_t, agf_fllast),
2057 offsetof(xfs_agf_t, agf_flcount),
2058 offsetof(xfs_agf_t, agf_freeblks),
2059 offsetof(xfs_agf_t, agf_longest),
David Chinner92821e22007-05-24 15:26:31 +10002060 offsetof(xfs_agf_t, agf_btreeblks),
Linus Torvalds1da177e2005-04-16 15:20:36 -07002061 sizeof(xfs_agf_t)
2062 };
2063
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00002064 trace_xfs_agf(tp->t_mountp, XFS_BUF_TO_AGF(bp), fields, _RET_IP_);
2065
Linus Torvalds1da177e2005-04-16 15:20:36 -07002066 xfs_btree_offsets(fields, offsets, XFS_AGF_NUM_BITS, &first, &last);
2067 xfs_trans_log_buf(tp, bp, (uint)first, (uint)last);
2068}
2069
2070/*
2071 * Interface for inode allocation to force the pag data to be initialized.
2072 */
2073int /* error */
2074xfs_alloc_pagf_init(
2075 xfs_mount_t *mp, /* file system mount structure */
2076 xfs_trans_t *tp, /* transaction pointer */
2077 xfs_agnumber_t agno, /* allocation group number */
2078 int flags) /* XFS_ALLOC_FLAGS_... */
2079{
2080 xfs_buf_t *bp;
2081 int error;
2082
2083 if ((error = xfs_alloc_read_agf(mp, tp, agno, flags, &bp)))
2084 return error;
2085 if (bp)
2086 xfs_trans_brelse(tp, bp);
2087 return 0;
2088}
2089
2090/*
2091 * Put the block on the freelist for the allocation group.
2092 */
2093int /* error */
2094xfs_alloc_put_freelist(
2095 xfs_trans_t *tp, /* transaction pointer */
2096 xfs_buf_t *agbp, /* buffer for a.g. freelist header */
2097 xfs_buf_t *agflbp,/* buffer for a.g. free block array */
David Chinner92821e22007-05-24 15:26:31 +10002098 xfs_agblock_t bno, /* block being freed */
2099 int btreeblk) /* block came from a AGF btree */
Linus Torvalds1da177e2005-04-16 15:20:36 -07002100{
2101 xfs_agf_t *agf; /* a.g. freespace structure */
2102 xfs_agfl_t *agfl; /* a.g. free block array */
Christoph Hellwige2101002006-09-28 10:56:51 +10002103 __be32 *blockp;/* pointer to array entry */
Linus Torvalds1da177e2005-04-16 15:20:36 -07002104 int error;
David Chinner92821e22007-05-24 15:26:31 +10002105 int logflags;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002106 xfs_mount_t *mp; /* mount structure */
2107 xfs_perag_t *pag; /* per allocation group data */
2108
2109 agf = XFS_BUF_TO_AGF(agbp);
2110 mp = tp->t_mountp;
2111
2112 if (!agflbp && (error = xfs_alloc_read_agfl(mp, tp,
Christoph Hellwig16259e72005-11-02 15:11:25 +11002113 be32_to_cpu(agf->agf_seqno), &agflbp)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07002114 return error;
2115 agfl = XFS_BUF_TO_AGFL(agflbp);
Marcin Slusarz413d57c2008-02-13 15:03:29 -08002116 be32_add_cpu(&agf->agf_fllast, 1);
Christoph Hellwig16259e72005-11-02 15:11:25 +11002117 if (be32_to_cpu(agf->agf_fllast) == XFS_AGFL_SIZE(mp))
Linus Torvalds1da177e2005-04-16 15:20:36 -07002118 agf->agf_fllast = 0;
Dave Chinnera862e0f2010-01-11 11:47:41 +00002119
2120 pag = xfs_perag_get(mp, be32_to_cpu(agf->agf_seqno));
Marcin Slusarz413d57c2008-02-13 15:03:29 -08002121 be32_add_cpu(&agf->agf_flcount, 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002122 xfs_trans_agflist_delta(tp, 1);
2123 pag->pagf_flcount++;
David Chinner92821e22007-05-24 15:26:31 +10002124
2125 logflags = XFS_AGF_FLLAST | XFS_AGF_FLCOUNT;
2126 if (btreeblk) {
Marcin Slusarz413d57c2008-02-13 15:03:29 -08002127 be32_add_cpu(&agf->agf_btreeblks, -1);
David Chinner92821e22007-05-24 15:26:31 +10002128 pag->pagf_btreeblks--;
2129 logflags |= XFS_AGF_BTREEBLKS;
2130 }
Dave Chinnera862e0f2010-01-11 11:47:41 +00002131 xfs_perag_put(pag);
David Chinner92821e22007-05-24 15:26:31 +10002132
David Chinner92821e22007-05-24 15:26:31 +10002133 xfs_alloc_log_agf(tp, agbp, logflags);
2134
Christoph Hellwig16259e72005-11-02 15:11:25 +11002135 ASSERT(be32_to_cpu(agf->agf_flcount) <= XFS_AGFL_SIZE(mp));
2136 blockp = &agfl->agfl_bno[be32_to_cpu(agf->agf_fllast)];
Christoph Hellwige2101002006-09-28 10:56:51 +10002137 *blockp = cpu_to_be32(bno);
David Chinner92821e22007-05-24 15:26:31 +10002138 xfs_alloc_log_agf(tp, agbp, logflags);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002139 xfs_trans_log_buf(tp, agflbp,
2140 (int)((xfs_caddr_t)blockp - (xfs_caddr_t)agfl),
2141 (int)((xfs_caddr_t)blockp - (xfs_caddr_t)agfl +
2142 sizeof(xfs_agblock_t) - 1));
2143 return 0;
2144}
2145
Dave Chinner5d5f5272012-11-14 17:44:56 +11002146static void
Dave Chinner612cfbf2012-11-14 17:52:32 +11002147xfs_agf_verify(
Dave Chinner5d5f5272012-11-14 17:44:56 +11002148 struct xfs_buf *bp)
2149 {
2150 struct xfs_mount *mp = bp->b_target->bt_mount;
2151 struct xfs_agf *agf;
2152 int agf_ok;
2153
2154 agf = XFS_BUF_TO_AGF(bp);
2155
2156 agf_ok = agf->agf_magicnum == cpu_to_be32(XFS_AGF_MAGIC) &&
2157 XFS_AGF_GOOD_VERSION(be32_to_cpu(agf->agf_versionnum)) &&
2158 be32_to_cpu(agf->agf_freeblks) <= be32_to_cpu(agf->agf_length) &&
2159 be32_to_cpu(agf->agf_flfirst) < XFS_AGFL_SIZE(mp) &&
2160 be32_to_cpu(agf->agf_fllast) < XFS_AGFL_SIZE(mp) &&
2161 be32_to_cpu(agf->agf_flcount) <= XFS_AGFL_SIZE(mp);
2162
2163 /*
2164 * during growfs operations, the perag is not fully initialised,
2165 * so we can't use it for any useful checking. growfs ensures we can't
2166 * use it by using uncached buffers that don't have the perag attached
2167 * so we can detect and avoid this problem.
2168 */
2169 if (bp->b_pag)
2170 agf_ok = agf_ok && be32_to_cpu(agf->agf_seqno) ==
2171 bp->b_pag->pag_agno;
2172
2173 if (xfs_sb_version_haslazysbcount(&mp->m_sb))
2174 agf_ok = agf_ok && be32_to_cpu(agf->agf_btreeblks) <=
2175 be32_to_cpu(agf->agf_length);
2176
2177 if (unlikely(XFS_TEST_ERROR(!agf_ok, mp, XFS_ERRTAG_ALLOC_READ_AGF,
2178 XFS_RANDOM_ALLOC_READ_AGF))) {
2179 XFS_CORRUPTION_ERROR(__func__, XFS_ERRLEVEL_LOW, mp, agf);
2180 xfs_buf_ioerror(bp, EFSCORRUPTED);
2181 }
Dave Chinner612cfbf2012-11-14 17:52:32 +11002182}
Dave Chinner5d5f5272012-11-14 17:44:56 +11002183
Dave Chinner612cfbf2012-11-14 17:52:32 +11002184static void
2185xfs_agf_write_verify(
2186 struct xfs_buf *bp)
2187{
2188 xfs_agf_verify(bp);
2189}
2190
2191void
2192xfs_agf_read_verify(
2193 struct xfs_buf *bp)
2194{
2195 xfs_agf_verify(bp);
2196 bp->b_pre_io = xfs_agf_write_verify;
Dave Chinner5d5f5272012-11-14 17:44:56 +11002197 bp->b_iodone = NULL;
2198 xfs_buf_ioend(bp, 0);
2199}
2200
Linus Torvalds1da177e2005-04-16 15:20:36 -07002201/*
2202 * Read in the allocation group header (free/alloc section).
2203 */
2204int /* error */
From: Christoph Hellwig48056212008-11-28 14:23:38 +11002205xfs_read_agf(
2206 struct xfs_mount *mp, /* mount point structure */
2207 struct xfs_trans *tp, /* transaction pointer */
2208 xfs_agnumber_t agno, /* allocation group number */
2209 int flags, /* XFS_BUF_ */
2210 struct xfs_buf **bpp) /* buffer for the ag freelist header */
Linus Torvalds1da177e2005-04-16 15:20:36 -07002211{
Linus Torvalds1da177e2005-04-16 15:20:36 -07002212 int error;
2213
2214 ASSERT(agno != NULLAGNUMBER);
2215 error = xfs_trans_read_buf(
2216 mp, tp, mp->m_ddev_targp,
2217 XFS_AG_DADDR(mp, agno, XFS_AGF_DADDR(mp)),
Dave Chinner5d5f5272012-11-14 17:44:56 +11002218 XFS_FSS_TO_BB(mp, 1), flags, bpp, xfs_agf_read_verify);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002219 if (error)
2220 return error;
From: Christoph Hellwig48056212008-11-28 14:23:38 +11002221 if (!*bpp)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002222 return 0;
From: Christoph Hellwig48056212008-11-28 14:23:38 +11002223
Chandra Seetharaman5a52c2a582011-07-22 23:39:51 +00002224 ASSERT(!(*bpp)->b_error);
Christoph Hellwig38f23232011-10-10 16:52:45 +00002225 xfs_buf_set_ref(*bpp, XFS_AGF_REF);
From: Christoph Hellwig48056212008-11-28 14:23:38 +11002226 return 0;
2227}
2228
2229/*
2230 * Read in the allocation group header (free/alloc section).
2231 */
2232int /* error */
2233xfs_alloc_read_agf(
2234 struct xfs_mount *mp, /* mount point structure */
2235 struct xfs_trans *tp, /* transaction pointer */
2236 xfs_agnumber_t agno, /* allocation group number */
2237 int flags, /* XFS_ALLOC_FLAG_... */
2238 struct xfs_buf **bpp) /* buffer for the ag freelist header */
2239{
2240 struct xfs_agf *agf; /* ag freelist header */
2241 struct xfs_perag *pag; /* per allocation group data */
2242 int error;
2243
2244 ASSERT(agno != NULLAGNUMBER);
2245
2246 error = xfs_read_agf(mp, tp, agno,
Christoph Hellwig0cadda12010-01-19 09:56:44 +00002247 (flags & XFS_ALLOC_FLAG_TRYLOCK) ? XBF_TRYLOCK : 0,
From: Christoph Hellwig48056212008-11-28 14:23:38 +11002248 bpp);
2249 if (error)
2250 return error;
2251 if (!*bpp)
2252 return 0;
Chandra Seetharaman5a52c2a582011-07-22 23:39:51 +00002253 ASSERT(!(*bpp)->b_error);
From: Christoph Hellwig48056212008-11-28 14:23:38 +11002254
2255 agf = XFS_BUF_TO_AGF(*bpp);
Dave Chinnera862e0f2010-01-11 11:47:41 +00002256 pag = xfs_perag_get(mp, agno);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002257 if (!pag->pagf_init) {
Christoph Hellwig16259e72005-11-02 15:11:25 +11002258 pag->pagf_freeblks = be32_to_cpu(agf->agf_freeblks);
David Chinner92821e22007-05-24 15:26:31 +10002259 pag->pagf_btreeblks = be32_to_cpu(agf->agf_btreeblks);
Christoph Hellwig16259e72005-11-02 15:11:25 +11002260 pag->pagf_flcount = be32_to_cpu(agf->agf_flcount);
2261 pag->pagf_longest = be32_to_cpu(agf->agf_longest);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002262 pag->pagf_levels[XFS_BTNUM_BNOi] =
Christoph Hellwig16259e72005-11-02 15:11:25 +11002263 be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNOi]);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002264 pag->pagf_levels[XFS_BTNUM_CNTi] =
Christoph Hellwig16259e72005-11-02 15:11:25 +11002265 be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNTi]);
Eric Sandeen007c61c2007-10-11 17:43:56 +10002266 spin_lock_init(&pag->pagb_lock);
Dave Chinnere57336f2010-01-11 11:47:49 +00002267 pag->pagb_count = 0;
Dave Chinnered3b4d62010-05-21 12:07:08 +10002268 pag->pagb_tree = RB_ROOT;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002269 pag->pagf_init = 1;
2270 }
2271#ifdef DEBUG
2272 else if (!XFS_FORCED_SHUTDOWN(mp)) {
Christoph Hellwig16259e72005-11-02 15:11:25 +11002273 ASSERT(pag->pagf_freeblks == be32_to_cpu(agf->agf_freeblks));
Barry Naujok89b28392008-10-30 17:05:49 +11002274 ASSERT(pag->pagf_btreeblks == be32_to_cpu(agf->agf_btreeblks));
Christoph Hellwig16259e72005-11-02 15:11:25 +11002275 ASSERT(pag->pagf_flcount == be32_to_cpu(agf->agf_flcount));
2276 ASSERT(pag->pagf_longest == be32_to_cpu(agf->agf_longest));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002277 ASSERT(pag->pagf_levels[XFS_BTNUM_BNOi] ==
Christoph Hellwig16259e72005-11-02 15:11:25 +11002278 be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNOi]));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002279 ASSERT(pag->pagf_levels[XFS_BTNUM_CNTi] ==
Christoph Hellwig16259e72005-11-02 15:11:25 +11002280 be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNTi]));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002281 }
2282#endif
Dave Chinnera862e0f2010-01-11 11:47:41 +00002283 xfs_perag_put(pag);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002284 return 0;
2285}
2286
2287/*
2288 * Allocate an extent (variable-size).
2289 * Depending on the allocation type, we either look in a single allocation
2290 * group or loop over the allocation groups to find the result.
2291 */
2292int /* error */
Dave Chinnere04426b2012-10-05 11:06:59 +10002293xfs_alloc_vextent(
Linus Torvalds1da177e2005-04-16 15:20:36 -07002294 xfs_alloc_arg_t *args) /* allocation argument structure */
2295{
2296 xfs_agblock_t agsize; /* allocation group size */
2297 int error;
2298 int flags; /* XFS_ALLOC_FLAG_... locking flags */
Linus Torvalds1da177e2005-04-16 15:20:36 -07002299 xfs_extlen_t minleft;/* minimum left value, temp copy */
2300 xfs_mount_t *mp; /* mount structure pointer */
2301 xfs_agnumber_t sagno; /* starting allocation group number */
2302 xfs_alloctype_t type; /* input allocation type */
2303 int bump_rotor = 0;
2304 int no_min = 0;
2305 xfs_agnumber_t rotorstep = xfs_rotorstep; /* inode32 agf stepper */
2306
2307 mp = args->mp;
2308 type = args->otype = args->type;
2309 args->agbno = NULLAGBLOCK;
2310 /*
2311 * Just fix this up, for the case where the last a.g. is shorter
2312 * (or there's only one a.g.) and the caller couldn't easily figure
2313 * that out (xfs_bmap_alloc).
2314 */
2315 agsize = mp->m_sb.sb_agblocks;
2316 if (args->maxlen > agsize)
2317 args->maxlen = agsize;
2318 if (args->alignment == 0)
2319 args->alignment = 1;
2320 ASSERT(XFS_FSB_TO_AGNO(mp, args->fsbno) < mp->m_sb.sb_agcount);
2321 ASSERT(XFS_FSB_TO_AGBNO(mp, args->fsbno) < agsize);
2322 ASSERT(args->minlen <= args->maxlen);
2323 ASSERT(args->minlen <= agsize);
2324 ASSERT(args->mod < args->prod);
2325 if (XFS_FSB_TO_AGNO(mp, args->fsbno) >= mp->m_sb.sb_agcount ||
2326 XFS_FSB_TO_AGBNO(mp, args->fsbno) >= agsize ||
2327 args->minlen > args->maxlen || args->minlen > agsize ||
2328 args->mod >= args->prod) {
2329 args->fsbno = NULLFSBLOCK;
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00002330 trace_xfs_alloc_vextent_badargs(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002331 return 0;
2332 }
2333 minleft = args->minleft;
2334
2335 switch (type) {
2336 case XFS_ALLOCTYPE_THIS_AG:
2337 case XFS_ALLOCTYPE_NEAR_BNO:
2338 case XFS_ALLOCTYPE_THIS_BNO:
2339 /*
2340 * These three force us into a single a.g.
2341 */
2342 args->agno = XFS_FSB_TO_AGNO(mp, args->fsbno);
Dave Chinnera862e0f2010-01-11 11:47:41 +00002343 args->pag = xfs_perag_get(mp, args->agno);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002344 args->minleft = 0;
2345 error = xfs_alloc_fix_freelist(args, 0);
2346 args->minleft = minleft;
2347 if (error) {
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00002348 trace_xfs_alloc_vextent_nofix(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002349 goto error0;
2350 }
2351 if (!args->agbp) {
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00002352 trace_xfs_alloc_vextent_noagbp(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002353 break;
2354 }
2355 args->agbno = XFS_FSB_TO_AGBNO(mp, args->fsbno);
2356 if ((error = xfs_alloc_ag_vextent(args)))
2357 goto error0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002358 break;
2359 case XFS_ALLOCTYPE_START_BNO:
2360 /*
2361 * Try near allocation first, then anywhere-in-ag after
2362 * the first a.g. fails.
2363 */
2364 if ((args->userdata == XFS_ALLOC_INITIAL_USER_DATA) &&
2365 (mp->m_flags & XFS_MOUNT_32BITINODES)) {
2366 args->fsbno = XFS_AGB_TO_FSB(mp,
2367 ((mp->m_agfrotor / rotorstep) %
2368 mp->m_sb.sb_agcount), 0);
2369 bump_rotor = 1;
2370 }
2371 args->agbno = XFS_FSB_TO_AGBNO(mp, args->fsbno);
2372 args->type = XFS_ALLOCTYPE_NEAR_BNO;
2373 /* FALLTHROUGH */
2374 case XFS_ALLOCTYPE_ANY_AG:
2375 case XFS_ALLOCTYPE_START_AG:
2376 case XFS_ALLOCTYPE_FIRST_AG:
2377 /*
2378 * Rotate through the allocation groups looking for a winner.
2379 */
2380 if (type == XFS_ALLOCTYPE_ANY_AG) {
2381 /*
2382 * Start with the last place we left off.
2383 */
2384 args->agno = sagno = (mp->m_agfrotor / rotorstep) %
2385 mp->m_sb.sb_agcount;
2386 args->type = XFS_ALLOCTYPE_THIS_AG;
2387 flags = XFS_ALLOC_FLAG_TRYLOCK;
2388 } else if (type == XFS_ALLOCTYPE_FIRST_AG) {
2389 /*
2390 * Start with allocation group given by bno.
2391 */
2392 args->agno = XFS_FSB_TO_AGNO(mp, args->fsbno);
2393 args->type = XFS_ALLOCTYPE_THIS_AG;
2394 sagno = 0;
2395 flags = 0;
2396 } else {
2397 if (type == XFS_ALLOCTYPE_START_AG)
2398 args->type = XFS_ALLOCTYPE_THIS_AG;
2399 /*
2400 * Start with the given allocation group.
2401 */
2402 args->agno = sagno = XFS_FSB_TO_AGNO(mp, args->fsbno);
2403 flags = XFS_ALLOC_FLAG_TRYLOCK;
2404 }
2405 /*
2406 * Loop over allocation groups twice; first time with
2407 * trylock set, second time without.
2408 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07002409 for (;;) {
Dave Chinnera862e0f2010-01-11 11:47:41 +00002410 args->pag = xfs_perag_get(mp, args->agno);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002411 if (no_min) args->minleft = 0;
2412 error = xfs_alloc_fix_freelist(args, flags);
2413 args->minleft = minleft;
2414 if (error) {
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00002415 trace_xfs_alloc_vextent_nofix(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002416 goto error0;
2417 }
2418 /*
2419 * If we get a buffer back then the allocation will fly.
2420 */
2421 if (args->agbp) {
2422 if ((error = xfs_alloc_ag_vextent(args)))
2423 goto error0;
2424 break;
2425 }
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00002426
2427 trace_xfs_alloc_vextent_loopfailed(args);
2428
Linus Torvalds1da177e2005-04-16 15:20:36 -07002429 /*
2430 * Didn't work, figure out the next iteration.
2431 */
2432 if (args->agno == sagno &&
2433 type == XFS_ALLOCTYPE_START_BNO)
2434 args->type = XFS_ALLOCTYPE_THIS_AG;
Yingping Lud210a282006-06-09 14:55:18 +10002435 /*
2436 * For the first allocation, we can try any AG to get
2437 * space. However, if we already have allocated a
2438 * block, we don't want to try AGs whose number is below
2439 * sagno. Otherwise, we may end up with out-of-order
2440 * locking of AGF, which might cause deadlock.
2441 */
2442 if (++(args->agno) == mp->m_sb.sb_agcount) {
2443 if (args->firstblock != NULLFSBLOCK)
2444 args->agno = sagno;
2445 else
2446 args->agno = 0;
2447 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002448 /*
2449 * Reached the starting a.g., must either be done
2450 * or switch to non-trylock mode.
2451 */
2452 if (args->agno == sagno) {
2453 if (no_min == 1) {
2454 args->agbno = NULLAGBLOCK;
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00002455 trace_xfs_alloc_vextent_allfailed(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002456 break;
2457 }
2458 if (flags == 0) {
2459 no_min = 1;
2460 } else {
2461 flags = 0;
2462 if (type == XFS_ALLOCTYPE_START_BNO) {
2463 args->agbno = XFS_FSB_TO_AGBNO(mp,
2464 args->fsbno);
2465 args->type = XFS_ALLOCTYPE_NEAR_BNO;
2466 }
2467 }
2468 }
Dave Chinnera862e0f2010-01-11 11:47:41 +00002469 xfs_perag_put(args->pag);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002470 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002471 if (bump_rotor || (type == XFS_ALLOCTYPE_ANY_AG)) {
2472 if (args->agno == sagno)
2473 mp->m_agfrotor = (mp->m_agfrotor + 1) %
2474 (mp->m_sb.sb_agcount * rotorstep);
2475 else
2476 mp->m_agfrotor = (args->agno * rotorstep + 1) %
2477 (mp->m_sb.sb_agcount * rotorstep);
2478 }
2479 break;
2480 default:
2481 ASSERT(0);
2482 /* NOTREACHED */
2483 }
2484 if (args->agbno == NULLAGBLOCK)
2485 args->fsbno = NULLFSBLOCK;
2486 else {
2487 args->fsbno = XFS_AGB_TO_FSB(mp, args->agno, args->agbno);
2488#ifdef DEBUG
2489 ASSERT(args->len >= args->minlen);
2490 ASSERT(args->len <= args->maxlen);
2491 ASSERT(args->agbno % args->alignment == 0);
2492 XFS_AG_CHECK_DADDR(mp, XFS_FSB_TO_DADDR(mp, args->fsbno),
2493 args->len);
2494#endif
2495 }
Dave Chinnera862e0f2010-01-11 11:47:41 +00002496 xfs_perag_put(args->pag);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002497 return 0;
2498error0:
Dave Chinnera862e0f2010-01-11 11:47:41 +00002499 xfs_perag_put(args->pag);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002500 return error;
2501}
2502
2503/*
2504 * Free an extent.
2505 * Just break up the extent address and hand off to xfs_free_ag_extent
2506 * after fixing up the freelist.
2507 */
2508int /* error */
2509xfs_free_extent(
2510 xfs_trans_t *tp, /* transaction pointer */
2511 xfs_fsblock_t bno, /* starting block number of extent */
2512 xfs_extlen_t len) /* length of extent */
2513{
Nathan Scott0e1edbd2006-08-10 14:40:41 +10002514 xfs_alloc_arg_t args;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002515 int error;
2516
2517 ASSERT(len != 0);
Nathan Scott0e1edbd2006-08-10 14:40:41 +10002518 memset(&args, 0, sizeof(xfs_alloc_arg_t));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002519 args.tp = tp;
2520 args.mp = tp->t_mountp;
Dave Chinnerbe65b182011-04-08 12:45:07 +10002521
2522 /*
2523 * validate that the block number is legal - the enables us to detect
2524 * and handle a silent filesystem corruption rather than crashing.
2525 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07002526 args.agno = XFS_FSB_TO_AGNO(args.mp, bno);
Dave Chinnerbe65b182011-04-08 12:45:07 +10002527 if (args.agno >= args.mp->m_sb.sb_agcount)
2528 return EFSCORRUPTED;
2529
Linus Torvalds1da177e2005-04-16 15:20:36 -07002530 args.agbno = XFS_FSB_TO_AGBNO(args.mp, bno);
Dave Chinnerbe65b182011-04-08 12:45:07 +10002531 if (args.agbno >= args.mp->m_sb.sb_agblocks)
2532 return EFSCORRUPTED;
2533
Dave Chinnera862e0f2010-01-11 11:47:41 +00002534 args.pag = xfs_perag_get(args.mp, args.agno);
Dave Chinnerbe65b182011-04-08 12:45:07 +10002535 ASSERT(args.pag);
2536
2537 error = xfs_alloc_fix_freelist(&args, XFS_ALLOC_FLAG_FREEING);
2538 if (error)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002539 goto error0;
Dave Chinnerbe65b182011-04-08 12:45:07 +10002540
2541 /* validate the extent size is legal now we have the agf locked */
2542 if (args.agbno + len >
2543 be32_to_cpu(XFS_BUF_TO_AGF(args.agbp)->agf_length)) {
2544 error = EFSCORRUPTED;
2545 goto error0;
2546 }
2547
Nathan Scott0e1edbd2006-08-10 14:40:41 +10002548 error = xfs_free_ag_extent(tp, args.agbp, args.agno, args.agbno, len, 0);
Christoph Hellwiga870acd2011-04-24 19:06:14 +00002549 if (!error)
Dave Chinner4ecbfe62012-04-29 10:41:10 +00002550 xfs_extent_busy_insert(tp, args.agno, args.agbno, len, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002551error0:
Dave Chinnera862e0f2010-01-11 11:47:41 +00002552 xfs_perag_put(args.pag);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002553 return error;
2554}