blob: 0ad23253e8b1ed1da6c723b44d828fbb7e743350 [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
Dave Chinner1813dd62012-11-14 17:54:40 +1100468static void
Dave Chinner612cfbf2012-11-14 17:52:32 +1100469xfs_agfl_write_verify(
470 struct xfs_buf *bp)
471{
472 xfs_agfl_verify(bp);
473}
474
Dave Chinnerb0f539d2012-11-14 17:53:49 +1100475static void
Dave Chinner612cfbf2012-11-14 17:52:32 +1100476xfs_agfl_read_verify(
477 struct xfs_buf *bp)
478{
479 xfs_agfl_verify(bp);
Dave Chinnerbb80c6d2012-11-12 22:54:06 +1100480}
481
Dave Chinner1813dd62012-11-14 17:54:40 +1100482const struct xfs_buf_ops xfs_agfl_buf_ops = {
483 .verify_read = xfs_agfl_read_verify,
484 .verify_write = xfs_agfl_write_verify,
485};
486
Linus Torvalds1da177e2005-04-16 15:20:36 -0700487/*
488 * Read in the allocation group free block array.
489 */
490STATIC int /* error */
491xfs_alloc_read_agfl(
492 xfs_mount_t *mp, /* mount point structure */
493 xfs_trans_t *tp, /* transaction pointer */
494 xfs_agnumber_t agno, /* allocation group number */
495 xfs_buf_t **bpp) /* buffer for the ag free block array */
496{
497 xfs_buf_t *bp; /* return value */
498 int error;
499
500 ASSERT(agno != NULLAGNUMBER);
501 error = xfs_trans_read_buf(
502 mp, tp, mp->m_ddev_targp,
503 XFS_AG_DADDR(mp, agno, XFS_AGFL_DADDR(mp)),
Dave Chinner1813dd62012-11-14 17:54:40 +1100504 XFS_FSS_TO_BB(mp, 1), 0, &bp, &xfs_agfl_buf_ops);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700505 if (error)
506 return error;
Chandra Seetharaman5a52c2a582011-07-22 23:39:51 +0000507 ASSERT(!xfs_buf_geterror(bp));
Christoph Hellwig38f23232011-10-10 16:52:45 +0000508 xfs_buf_set_ref(bp, XFS_AGFL_REF);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700509 *bpp = bp;
510 return 0;
511}
512
Christoph Hellwigecb69282011-03-04 12:59:55 +0000513STATIC int
514xfs_alloc_update_counters(
515 struct xfs_trans *tp,
516 struct xfs_perag *pag,
517 struct xfs_buf *agbp,
518 long len)
519{
520 struct xfs_agf *agf = XFS_BUF_TO_AGF(agbp);
521
522 pag->pagf_freeblks += len;
523 be32_add_cpu(&agf->agf_freeblks, len);
524
525 xfs_trans_agblocks_delta(tp, len);
526 if (unlikely(be32_to_cpu(agf->agf_freeblks) >
527 be32_to_cpu(agf->agf_length)))
528 return EFSCORRUPTED;
529
530 xfs_alloc_log_agf(tp, agbp, XFS_AGF_FREEBLKS);
531 return 0;
532}
533
Linus Torvalds1da177e2005-04-16 15:20:36 -0700534/*
535 * Allocation group level functions.
536 */
537
538/*
539 * Allocate a variable extent in the allocation group agno.
540 * Type and bno are used to determine where in the allocation group the
541 * extent will start.
542 * Extent's length (returned in *len) will be between minlen and maxlen,
543 * and of the form k * prod + mod unless there's nothing that large.
544 * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
545 */
546STATIC int /* error */
547xfs_alloc_ag_vextent(
548 xfs_alloc_arg_t *args) /* argument structure for allocation */
549{
550 int error=0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700551
552 ASSERT(args->minlen > 0);
553 ASSERT(args->maxlen > 0);
554 ASSERT(args->minlen <= args->maxlen);
555 ASSERT(args->mod < args->prod);
556 ASSERT(args->alignment > 0);
557 /*
558 * Branch to correct routine based on the type.
559 */
560 args->wasfromfl = 0;
561 switch (args->type) {
562 case XFS_ALLOCTYPE_THIS_AG:
563 error = xfs_alloc_ag_vextent_size(args);
564 break;
565 case XFS_ALLOCTYPE_NEAR_BNO:
566 error = xfs_alloc_ag_vextent_near(args);
567 break;
568 case XFS_ALLOCTYPE_THIS_BNO:
569 error = xfs_alloc_ag_vextent_exact(args);
570 break;
571 default:
572 ASSERT(0);
573 /* NOTREACHED */
574 }
Christoph Hellwigecb69282011-03-04 12:59:55 +0000575
576 if (error || args->agbno == NULLAGBLOCK)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700577 return error;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700578
Christoph Hellwigecb69282011-03-04 12:59:55 +0000579 ASSERT(args->len >= args->minlen);
580 ASSERT(args->len <= args->maxlen);
581 ASSERT(!args->wasfromfl || !args->isfl);
582 ASSERT(args->agbno % args->alignment == 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700583
Christoph Hellwigecb69282011-03-04 12:59:55 +0000584 if (!args->wasfromfl) {
585 error = xfs_alloc_update_counters(args->tp, args->pag,
586 args->agbp,
587 -((long)(args->len)));
588 if (error)
589 return error;
590
Dave Chinner4ecbfe62012-04-29 10:41:10 +0000591 ASSERT(!xfs_extent_busy_search(args->mp, args->agno,
Christoph Hellwige26f0502011-04-24 19:06:15 +0000592 args->agbno, args->len));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700593 }
Christoph Hellwigecb69282011-03-04 12:59:55 +0000594
595 if (!args->isfl) {
596 xfs_trans_mod_sb(args->tp, args->wasdel ?
597 XFS_TRANS_SB_RES_FDBLOCKS :
598 XFS_TRANS_SB_FDBLOCKS,
599 -((long)(args->len)));
600 }
601
602 XFS_STATS_INC(xs_allocx);
603 XFS_STATS_ADD(xs_allocb, args->len);
604 return error;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700605}
606
607/*
608 * Allocate a variable extent at exactly agno/bno.
609 * Extent's length (returned in *len) will be between minlen and maxlen,
610 * and of the form k * prod + mod unless there's nothing that large.
611 * Return the starting a.g. block (bno), or NULLAGBLOCK if we can't do it.
612 */
613STATIC int /* error */
614xfs_alloc_ag_vextent_exact(
615 xfs_alloc_arg_t *args) /* allocation argument structure */
616{
617 xfs_btree_cur_t *bno_cur;/* by block-number btree cursor */
618 xfs_btree_cur_t *cnt_cur;/* by count btree cursor */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700619 int error;
620 xfs_agblock_t fbno; /* start block of found extent */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700621 xfs_extlen_t flen; /* length of found extent */
Christoph Hellwige26f0502011-04-24 19:06:15 +0000622 xfs_agblock_t tbno; /* start block of trimmed extent */
623 xfs_extlen_t tlen; /* length of trimmed extent */
624 xfs_agblock_t tend; /* end block of trimmed extent */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700625 int i; /* success/failure of operation */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700626
627 ASSERT(args->alignment == 1);
Christoph Hellwig9f9baab2010-12-10 15:03:57 +0000628
Linus Torvalds1da177e2005-04-16 15:20:36 -0700629 /*
630 * Allocate/initialize a cursor for the by-number freespace btree.
631 */
Christoph Hellwig561f7d12008-10-30 16:53:59 +1100632 bno_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
Christoph Hellwig9f9baab2010-12-10 15:03:57 +0000633 args->agno, XFS_BTNUM_BNO);
634
Linus Torvalds1da177e2005-04-16 15:20:36 -0700635 /*
636 * Lookup bno and minlen in the btree (minlen is irrelevant, really).
637 * Look for the closest free block <= bno, it must contain bno
638 * if any free block does.
639 */
Christoph Hellwig9f9baab2010-12-10 15:03:57 +0000640 error = xfs_alloc_lookup_le(bno_cur, args->agbno, args->minlen, &i);
641 if (error)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700642 goto error0;
Christoph Hellwig9f9baab2010-12-10 15:03:57 +0000643 if (!i)
644 goto not_found;
645
Linus Torvalds1da177e2005-04-16 15:20:36 -0700646 /*
647 * Grab the freespace record.
648 */
Christoph Hellwig9f9baab2010-12-10 15:03:57 +0000649 error = xfs_alloc_get_rec(bno_cur, &fbno, &flen, &i);
650 if (error)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700651 goto error0;
652 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
653 ASSERT(fbno <= args->agbno);
Christoph Hellwig9f9baab2010-12-10 15:03:57 +0000654
Linus Torvalds1da177e2005-04-16 15:20:36 -0700655 /*
Christoph Hellwige26f0502011-04-24 19:06:15 +0000656 * Check for overlapping busy extents.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700657 */
Dave Chinner4ecbfe62012-04-29 10:41:10 +0000658 xfs_extent_busy_trim(args, fbno, flen, &tbno, &tlen);
Christoph Hellwige26f0502011-04-24 19:06:15 +0000659
660 /*
661 * Give up if the start of the extent is busy, or the freespace isn't
662 * long enough for the minimum request.
663 */
664 if (tbno > args->agbno)
665 goto not_found;
666 if (tlen < args->minlen)
667 goto not_found;
668 tend = tbno + tlen;
669 if (tend < args->agbno + args->minlen)
Christoph Hellwig9f9baab2010-12-10 15:03:57 +0000670 goto not_found;
671
Linus Torvalds1da177e2005-04-16 15:20:36 -0700672 /*
673 * End of extent will be smaller of the freespace end and the
674 * maximal requested end.
Christoph Hellwig9f9baab2010-12-10 15:03:57 +0000675 *
Linus Torvalds1da177e2005-04-16 15:20:36 -0700676 * Fix the length according to mod and prod if given.
677 */
Chandra Seetharaman81463b12011-06-09 16:47:49 +0000678 args->len = XFS_AGBLOCK_MIN(tend, args->agbno + args->maxlen)
679 - args->agbno;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700680 xfs_alloc_fix_len(args);
Christoph Hellwig9f9baab2010-12-10 15:03:57 +0000681 if (!xfs_alloc_fix_minleft(args))
682 goto not_found;
683
Chandra Seetharaman81463b12011-06-09 16:47:49 +0000684 ASSERT(args->agbno + args->len <= tend);
Christoph Hellwig9f9baab2010-12-10 15:03:57 +0000685
Linus Torvalds1da177e2005-04-16 15:20:36 -0700686 /*
Chandra Seetharaman81463b12011-06-09 16:47:49 +0000687 * We are allocating agbno for args->len
Linus Torvalds1da177e2005-04-16 15:20:36 -0700688 * Allocate/initialize a cursor for the by-size btree.
689 */
Christoph Hellwig561f7d12008-10-30 16:53:59 +1100690 cnt_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
691 args->agno, XFS_BTNUM_CNT);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700692 ASSERT(args->agbno + args->len <=
Christoph Hellwig16259e72005-11-02 15:11:25 +1100693 be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length));
Christoph Hellwig9f9baab2010-12-10 15:03:57 +0000694 error = xfs_alloc_fixup_trees(cnt_cur, bno_cur, fbno, flen, args->agbno,
695 args->len, XFSA_FIXUP_BNO_OK);
696 if (error) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700697 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
698 goto error0;
699 }
Christoph Hellwig9f9baab2010-12-10 15:03:57 +0000700
Linus Torvalds1da177e2005-04-16 15:20:36 -0700701 xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
702 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
Christoph Hellwig0b1b2132009-12-14 23:14:59 +0000703
Linus Torvalds1da177e2005-04-16 15:20:36 -0700704 args->wasfromfl = 0;
Christoph Hellwig9f9baab2010-12-10 15:03:57 +0000705 trace_xfs_alloc_exact_done(args);
706 return 0;
707
708not_found:
709 /* Didn't find it, return null. */
710 xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
711 args->agbno = NULLAGBLOCK;
712 trace_xfs_alloc_exact_notfound(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700713 return 0;
714
715error0:
716 xfs_btree_del_cursor(bno_cur, XFS_BTREE_ERROR);
Christoph Hellwig0b1b2132009-12-14 23:14:59 +0000717 trace_xfs_alloc_exact_error(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700718 return error;
719}
720
721/*
Christoph Hellwig489a1502010-12-10 15:04:11 +0000722 * Search the btree in a given direction via the search cursor and compare
723 * the records found against the good extent we've already found.
724 */
725STATIC int
726xfs_alloc_find_best_extent(
727 struct xfs_alloc_arg *args, /* allocation argument structure */
728 struct xfs_btree_cur **gcur, /* good cursor */
729 struct xfs_btree_cur **scur, /* searching cursor */
730 xfs_agblock_t gdiff, /* difference for search comparison */
731 xfs_agblock_t *sbno, /* extent found by search */
Christoph Hellwige26f0502011-04-24 19:06:15 +0000732 xfs_extlen_t *slen, /* extent length */
733 xfs_agblock_t *sbnoa, /* aligned extent found by search */
734 xfs_extlen_t *slena, /* aligned extent length */
Christoph Hellwig489a1502010-12-10 15:04:11 +0000735 int dir) /* 0 = search right, 1 = search left */
736{
Christoph Hellwig489a1502010-12-10 15:04:11 +0000737 xfs_agblock_t new;
738 xfs_agblock_t sdiff;
739 int error;
740 int i;
741
742 /* The good extent is perfect, no need to search. */
743 if (!gdiff)
744 goto out_use_good;
745
746 /*
747 * Look until we find a better one, run out of space or run off the end.
748 */
749 do {
750 error = xfs_alloc_get_rec(*scur, sbno, slen, &i);
751 if (error)
752 goto error0;
753 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
Christoph Hellwige26f0502011-04-24 19:06:15 +0000754 xfs_alloc_compute_aligned(args, *sbno, *slen, sbnoa, slena);
Christoph Hellwig489a1502010-12-10 15:04:11 +0000755
756 /*
757 * The good extent is closer than this one.
758 */
759 if (!dir) {
Christoph Hellwige26f0502011-04-24 19:06:15 +0000760 if (*sbnoa >= args->agbno + gdiff)
Christoph Hellwig489a1502010-12-10 15:04:11 +0000761 goto out_use_good;
762 } else {
Christoph Hellwige26f0502011-04-24 19:06:15 +0000763 if (*sbnoa <= args->agbno - gdiff)
Christoph Hellwig489a1502010-12-10 15:04:11 +0000764 goto out_use_good;
765 }
766
767 /*
768 * Same distance, compare length and pick the best.
769 */
770 if (*slena >= args->minlen) {
771 args->len = XFS_EXTLEN_MIN(*slena, args->maxlen);
772 xfs_alloc_fix_len(args);
773
774 sdiff = xfs_alloc_compute_diff(args->agbno, args->len,
Christoph Hellwige26f0502011-04-24 19:06:15 +0000775 args->alignment, *sbnoa,
776 *slena, &new);
Christoph Hellwig489a1502010-12-10 15:04:11 +0000777
778 /*
779 * Choose closer size and invalidate other cursor.
780 */
781 if (sdiff < gdiff)
782 goto out_use_search;
783 goto out_use_good;
784 }
785
786 if (!dir)
787 error = xfs_btree_increment(*scur, 0, &i);
788 else
789 error = xfs_btree_decrement(*scur, 0, &i);
790 if (error)
791 goto error0;
792 } while (i);
793
794out_use_good:
795 xfs_btree_del_cursor(*scur, XFS_BTREE_NOERROR);
796 *scur = NULL;
797 return 0;
798
799out_use_search:
800 xfs_btree_del_cursor(*gcur, XFS_BTREE_NOERROR);
801 *gcur = NULL;
802 return 0;
803
804error0:
805 /* caller invalidates cursors */
806 return error;
807}
808
809/*
Linus Torvalds1da177e2005-04-16 15:20:36 -0700810 * Allocate a variable extent near bno in the allocation group agno.
811 * Extent's length (returned in len) will be between minlen and maxlen,
812 * and of the form k * prod + mod unless there's nothing that large.
813 * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
814 */
815STATIC int /* error */
816xfs_alloc_ag_vextent_near(
817 xfs_alloc_arg_t *args) /* allocation argument structure */
818{
819 xfs_btree_cur_t *bno_cur_gt; /* cursor for bno btree, right side */
820 xfs_btree_cur_t *bno_cur_lt; /* cursor for bno btree, left side */
821 xfs_btree_cur_t *cnt_cur; /* cursor for count btree */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700822 xfs_agblock_t gtbno; /* start bno of right side entry */
823 xfs_agblock_t gtbnoa; /* aligned ... */
824 xfs_extlen_t gtdiff; /* difference to right side entry */
825 xfs_extlen_t gtlen; /* length of right side entry */
Christoph Hellwige26f0502011-04-24 19:06:15 +0000826 xfs_extlen_t gtlena; /* aligned ... */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700827 xfs_agblock_t gtnew; /* useful start bno of right side */
828 int error; /* error code */
829 int i; /* result code, temporary */
830 int j; /* result code, temporary */
831 xfs_agblock_t ltbno; /* start bno of left side entry */
832 xfs_agblock_t ltbnoa; /* aligned ... */
833 xfs_extlen_t ltdiff; /* difference to left side entry */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700834 xfs_extlen_t ltlen; /* length of left side entry */
Christoph Hellwige26f0502011-04-24 19:06:15 +0000835 xfs_extlen_t ltlena; /* aligned ... */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700836 xfs_agblock_t ltnew; /* useful start bno of left side */
837 xfs_extlen_t rlen; /* length of returned extent */
Christoph Hellwige26f0502011-04-24 19:06:15 +0000838 int forced = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700839#if defined(DEBUG) && defined(__KERNEL__)
840 /*
841 * Randomly don't execute the first algorithm.
842 */
843 int dofirst; /* set to do first algorithm */
844
Joe Perchese7a23a92007-05-08 13:49:03 +1000845 dofirst = random32() & 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700846#endif
Christoph Hellwige26f0502011-04-24 19:06:15 +0000847
848restart:
849 bno_cur_lt = NULL;
850 bno_cur_gt = NULL;
851 ltlen = 0;
852 gtlena = 0;
853 ltlena = 0;
854
Linus Torvalds1da177e2005-04-16 15:20:36 -0700855 /*
856 * Get a cursor for the by-size btree.
857 */
Christoph Hellwig561f7d12008-10-30 16:53:59 +1100858 cnt_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
859 args->agno, XFS_BTNUM_CNT);
Christoph Hellwige26f0502011-04-24 19:06:15 +0000860
Linus Torvalds1da177e2005-04-16 15:20:36 -0700861 /*
862 * See if there are any free extents as big as maxlen.
863 */
864 if ((error = xfs_alloc_lookup_ge(cnt_cur, 0, args->maxlen, &i)))
865 goto error0;
866 /*
867 * If none, then pick up the last entry in the tree unless the
868 * tree is empty.
869 */
870 if (!i) {
871 if ((error = xfs_alloc_ag_vextent_small(args, cnt_cur, &ltbno,
872 &ltlen, &i)))
873 goto error0;
874 if (i == 0 || ltlen == 0) {
875 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
Christoph Hellwige26f0502011-04-24 19:06:15 +0000876 trace_xfs_alloc_near_noentry(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700877 return 0;
878 }
879 ASSERT(i == 1);
880 }
881 args->wasfromfl = 0;
Christoph Hellwige26f0502011-04-24 19:06:15 +0000882
Linus Torvalds1da177e2005-04-16 15:20:36 -0700883 /*
884 * First algorithm.
885 * If the requested extent is large wrt the freespaces available
886 * in this a.g., then the cursor will be pointing to a btree entry
887 * near the right edge of the tree. If it's in the last btree leaf
888 * block, then we just examine all the entries in that block
889 * that are big enough, and pick the best one.
890 * This is written as a while loop so we can break out of it,
891 * but we never loop back to the top.
892 */
893 while (xfs_btree_islastblock(cnt_cur, 0)) {
894 xfs_extlen_t bdiff;
895 int besti=0;
896 xfs_extlen_t blen=0;
897 xfs_agblock_t bnew=0;
898
899#if defined(DEBUG) && defined(__KERNEL__)
900 if (!dofirst)
901 break;
902#endif
903 /*
904 * Start from the entry that lookup found, sequence through
905 * all larger free blocks. If we're actually pointing at a
906 * record smaller than maxlen, go to the start of this block,
907 * and skip all those smaller than minlen.
908 */
909 if (ltlen || args->alignment > 1) {
910 cnt_cur->bc_ptrs[0] = 1;
911 do {
912 if ((error = xfs_alloc_get_rec(cnt_cur, &ltbno,
913 &ltlen, &i)))
914 goto error0;
915 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
916 if (ltlen >= args->minlen)
917 break;
Christoph Hellwig637aa502008-10-30 16:55:45 +1100918 if ((error = xfs_btree_increment(cnt_cur, 0, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700919 goto error0;
920 } while (i);
921 ASSERT(ltlen >= args->minlen);
922 if (!i)
923 break;
924 }
925 i = cnt_cur->bc_ptrs[0];
926 for (j = 1, blen = 0, bdiff = 0;
927 !error && j && (blen < args->maxlen || bdiff > 0);
Christoph Hellwig637aa502008-10-30 16:55:45 +1100928 error = xfs_btree_increment(cnt_cur, 0, &j)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700929 /*
930 * For each entry, decide if it's better than
931 * the previous best entry.
932 */
933 if ((error = xfs_alloc_get_rec(cnt_cur, &ltbno, &ltlen, &i)))
934 goto error0;
935 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
Christoph Hellwig86fa8af2011-03-04 12:59:54 +0000936 xfs_alloc_compute_aligned(args, ltbno, ltlen,
937 &ltbnoa, &ltlena);
David Chinnere6430032008-04-17 16:49:49 +1000938 if (ltlena < args->minlen)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700939 continue;
940 args->len = XFS_EXTLEN_MIN(ltlena, args->maxlen);
941 xfs_alloc_fix_len(args);
942 ASSERT(args->len >= args->minlen);
943 if (args->len < blen)
944 continue;
945 ltdiff = xfs_alloc_compute_diff(args->agbno, args->len,
Christoph Hellwige26f0502011-04-24 19:06:15 +0000946 args->alignment, ltbnoa, ltlena, &ltnew);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700947 if (ltnew != NULLAGBLOCK &&
948 (args->len > blen || ltdiff < bdiff)) {
949 bdiff = ltdiff;
950 bnew = ltnew;
951 blen = args->len;
952 besti = cnt_cur->bc_ptrs[0];
953 }
954 }
955 /*
956 * It didn't work. We COULD be in a case where
957 * there's a good record somewhere, so try again.
958 */
959 if (blen == 0)
960 break;
961 /*
962 * Point at the best entry, and retrieve it again.
963 */
964 cnt_cur->bc_ptrs[0] = besti;
965 if ((error = xfs_alloc_get_rec(cnt_cur, &ltbno, &ltlen, &i)))
966 goto error0;
967 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
Christoph Hellwig73523a22010-07-20 17:54:45 +1000968 ASSERT(ltbno + ltlen <= be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700969 args->len = blen;
970 if (!xfs_alloc_fix_minleft(args)) {
971 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
Christoph Hellwig0b1b2132009-12-14 23:14:59 +0000972 trace_xfs_alloc_near_nominleft(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700973 return 0;
974 }
975 blen = args->len;
976 /*
977 * We are allocating starting at bnew for blen blocks.
978 */
979 args->agbno = bnew;
980 ASSERT(bnew >= ltbno);
Christoph Hellwig73523a22010-07-20 17:54:45 +1000981 ASSERT(bnew + blen <= ltbno + ltlen);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700982 /*
983 * Set up a cursor for the by-bno tree.
984 */
Christoph Hellwig561f7d12008-10-30 16:53:59 +1100985 bno_cur_lt = xfs_allocbt_init_cursor(args->mp, args->tp,
986 args->agbp, args->agno, XFS_BTNUM_BNO);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700987 /*
988 * Fix up the btree entries.
989 */
990 if ((error = xfs_alloc_fixup_trees(cnt_cur, bno_cur_lt, ltbno,
991 ltlen, bnew, blen, XFSA_FIXUP_CNT_OK)))
992 goto error0;
993 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
994 xfs_btree_del_cursor(bno_cur_lt, XFS_BTREE_NOERROR);
Christoph Hellwig0b1b2132009-12-14 23:14:59 +0000995
996 trace_xfs_alloc_near_first(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700997 return 0;
998 }
999 /*
1000 * Second algorithm.
1001 * Search in the by-bno tree to the left and to the right
1002 * simultaneously, until in each case we find a space big enough,
1003 * or run into the edge of the tree. When we run into the edge,
1004 * we deallocate that cursor.
1005 * If both searches succeed, we compare the two spaces and pick
1006 * the better one.
1007 * With alignment, it's possible for both to fail; the upper
1008 * level algorithm that picks allocation groups for allocations
1009 * is not supposed to do this.
1010 */
1011 /*
1012 * Allocate and initialize the cursor for the leftward search.
1013 */
Christoph Hellwig561f7d12008-10-30 16:53:59 +11001014 bno_cur_lt = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
1015 args->agno, XFS_BTNUM_BNO);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001016 /*
1017 * Lookup <= bno to find the leftward search's starting point.
1018 */
1019 if ((error = xfs_alloc_lookup_le(bno_cur_lt, args->agbno, args->maxlen, &i)))
1020 goto error0;
1021 if (!i) {
1022 /*
1023 * Didn't find anything; use this cursor for the rightward
1024 * search.
1025 */
1026 bno_cur_gt = bno_cur_lt;
1027 bno_cur_lt = NULL;
1028 }
1029 /*
1030 * Found something. Duplicate the cursor for the rightward search.
1031 */
1032 else if ((error = xfs_btree_dup_cursor(bno_cur_lt, &bno_cur_gt)))
1033 goto error0;
1034 /*
1035 * Increment the cursor, so we will point at the entry just right
1036 * of the leftward entry if any, or to the leftmost entry.
1037 */
Christoph Hellwig637aa502008-10-30 16:55:45 +11001038 if ((error = xfs_btree_increment(bno_cur_gt, 0, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001039 goto error0;
1040 if (!i) {
1041 /*
1042 * It failed, there are no rightward entries.
1043 */
1044 xfs_btree_del_cursor(bno_cur_gt, XFS_BTREE_NOERROR);
1045 bno_cur_gt = NULL;
1046 }
1047 /*
1048 * Loop going left with the leftward cursor, right with the
1049 * rightward cursor, until either both directions give up or
1050 * we find an entry at least as big as minlen.
1051 */
1052 do {
1053 if (bno_cur_lt) {
1054 if ((error = xfs_alloc_get_rec(bno_cur_lt, &ltbno, &ltlen, &i)))
1055 goto error0;
1056 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
Christoph Hellwig86fa8af2011-03-04 12:59:54 +00001057 xfs_alloc_compute_aligned(args, ltbno, ltlen,
1058 &ltbnoa, &ltlena);
David Chinner12375c82008-04-10 12:21:32 +10001059 if (ltlena >= args->minlen)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001060 break;
Christoph Hellwig8df4da42008-10-30 16:55:58 +11001061 if ((error = xfs_btree_decrement(bno_cur_lt, 0, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001062 goto error0;
1063 if (!i) {
1064 xfs_btree_del_cursor(bno_cur_lt,
1065 XFS_BTREE_NOERROR);
1066 bno_cur_lt = NULL;
1067 }
1068 }
1069 if (bno_cur_gt) {
1070 if ((error = xfs_alloc_get_rec(bno_cur_gt, &gtbno, &gtlen, &i)))
1071 goto error0;
1072 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
Christoph Hellwig86fa8af2011-03-04 12:59:54 +00001073 xfs_alloc_compute_aligned(args, gtbno, gtlen,
1074 &gtbnoa, &gtlena);
David Chinner12375c82008-04-10 12:21:32 +10001075 if (gtlena >= args->minlen)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001076 break;
Christoph Hellwig637aa502008-10-30 16:55:45 +11001077 if ((error = xfs_btree_increment(bno_cur_gt, 0, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001078 goto error0;
1079 if (!i) {
1080 xfs_btree_del_cursor(bno_cur_gt,
1081 XFS_BTREE_NOERROR);
1082 bno_cur_gt = NULL;
1083 }
1084 }
1085 } while (bno_cur_lt || bno_cur_gt);
Christoph Hellwig489a1502010-12-10 15:04:11 +00001086
Linus Torvalds1da177e2005-04-16 15:20:36 -07001087 /*
1088 * Got both cursors still active, need to find better entry.
1089 */
1090 if (bno_cur_lt && bno_cur_gt) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001091 if (ltlena >= args->minlen) {
1092 /*
Christoph Hellwig489a1502010-12-10 15:04:11 +00001093 * Left side is good, look for a right side entry.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001094 */
1095 args->len = XFS_EXTLEN_MIN(ltlena, args->maxlen);
1096 xfs_alloc_fix_len(args);
Christoph Hellwig489a1502010-12-10 15:04:11 +00001097 ltdiff = xfs_alloc_compute_diff(args->agbno, args->len,
Christoph Hellwige26f0502011-04-24 19:06:15 +00001098 args->alignment, ltbnoa, ltlena, &ltnew);
Christoph Hellwig489a1502010-12-10 15:04:11 +00001099
1100 error = xfs_alloc_find_best_extent(args,
1101 &bno_cur_lt, &bno_cur_gt,
Christoph Hellwige26f0502011-04-24 19:06:15 +00001102 ltdiff, &gtbno, &gtlen,
1103 &gtbnoa, &gtlena,
Christoph Hellwig489a1502010-12-10 15:04:11 +00001104 0 /* search right */);
1105 } else {
1106 ASSERT(gtlena >= args->minlen);
1107
Linus Torvalds1da177e2005-04-16 15:20:36 -07001108 /*
Christoph Hellwig489a1502010-12-10 15:04:11 +00001109 * Right side is good, look for a left side entry.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001110 */
1111 args->len = XFS_EXTLEN_MIN(gtlena, args->maxlen);
1112 xfs_alloc_fix_len(args);
Christoph Hellwig489a1502010-12-10 15:04:11 +00001113 gtdiff = xfs_alloc_compute_diff(args->agbno, args->len,
Christoph Hellwige26f0502011-04-24 19:06:15 +00001114 args->alignment, gtbnoa, gtlena, &gtnew);
Christoph Hellwig489a1502010-12-10 15:04:11 +00001115
1116 error = xfs_alloc_find_best_extent(args,
1117 &bno_cur_gt, &bno_cur_lt,
Christoph Hellwige26f0502011-04-24 19:06:15 +00001118 gtdiff, &ltbno, &ltlen,
1119 &ltbnoa, &ltlena,
Christoph Hellwig489a1502010-12-10 15:04:11 +00001120 1 /* search left */);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001121 }
Christoph Hellwig489a1502010-12-10 15:04:11 +00001122
1123 if (error)
1124 goto error0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001125 }
Christoph Hellwig489a1502010-12-10 15:04:11 +00001126
Linus Torvalds1da177e2005-04-16 15:20:36 -07001127 /*
1128 * If we couldn't get anything, give up.
1129 */
1130 if (bno_cur_lt == NULL && bno_cur_gt == NULL) {
Dave Chinnere3a746f52012-07-12 07:40:42 +10001131 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1132
Christoph Hellwige26f0502011-04-24 19:06:15 +00001133 if (!forced++) {
1134 trace_xfs_alloc_near_busy(args);
1135 xfs_log_force(args->mp, XFS_LOG_SYNC);
1136 goto restart;
1137 }
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00001138 trace_xfs_alloc_size_neither(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001139 args->agbno = NULLAGBLOCK;
1140 return 0;
1141 }
Christoph Hellwig489a1502010-12-10 15:04:11 +00001142
Linus Torvalds1da177e2005-04-16 15:20:36 -07001143 /*
1144 * At this point we have selected a freespace entry, either to the
1145 * left or to the right. If it's on the right, copy all the
1146 * useful variables to the "left" set so we only have one
1147 * copy of this code.
1148 */
1149 if (bno_cur_gt) {
1150 bno_cur_lt = bno_cur_gt;
1151 bno_cur_gt = NULL;
1152 ltbno = gtbno;
1153 ltbnoa = gtbnoa;
1154 ltlen = gtlen;
1155 ltlena = gtlena;
1156 j = 1;
1157 } else
1158 j = 0;
Christoph Hellwig489a1502010-12-10 15:04:11 +00001159
Linus Torvalds1da177e2005-04-16 15:20:36 -07001160 /*
1161 * Fix up the length and compute the useful address.
1162 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001163 args->len = XFS_EXTLEN_MIN(ltlena, args->maxlen);
1164 xfs_alloc_fix_len(args);
1165 if (!xfs_alloc_fix_minleft(args)) {
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00001166 trace_xfs_alloc_near_nominleft(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001167 xfs_btree_del_cursor(bno_cur_lt, XFS_BTREE_NOERROR);
1168 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1169 return 0;
1170 }
1171 rlen = args->len;
Christoph Hellwige26f0502011-04-24 19:06:15 +00001172 (void)xfs_alloc_compute_diff(args->agbno, rlen, args->alignment,
1173 ltbnoa, ltlena, &ltnew);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001174 ASSERT(ltnew >= ltbno);
Christoph Hellwige26f0502011-04-24 19:06:15 +00001175 ASSERT(ltnew + rlen <= ltbnoa + ltlena);
Christoph Hellwig16259e72005-11-02 15:11:25 +11001176 ASSERT(ltnew + rlen <= be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001177 args->agbno = ltnew;
Christoph Hellwige26f0502011-04-24 19:06:15 +00001178
Linus Torvalds1da177e2005-04-16 15:20:36 -07001179 if ((error = xfs_alloc_fixup_trees(cnt_cur, bno_cur_lt, ltbno, ltlen,
1180 ltnew, rlen, XFSA_FIXUP_BNO_OK)))
1181 goto error0;
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00001182
1183 if (j)
1184 trace_xfs_alloc_near_greater(args);
1185 else
1186 trace_xfs_alloc_near_lesser(args);
1187
Linus Torvalds1da177e2005-04-16 15:20:36 -07001188 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1189 xfs_btree_del_cursor(bno_cur_lt, XFS_BTREE_NOERROR);
1190 return 0;
1191
1192 error0:
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00001193 trace_xfs_alloc_near_error(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001194 if (cnt_cur != NULL)
1195 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
1196 if (bno_cur_lt != NULL)
1197 xfs_btree_del_cursor(bno_cur_lt, XFS_BTREE_ERROR);
1198 if (bno_cur_gt != NULL)
1199 xfs_btree_del_cursor(bno_cur_gt, XFS_BTREE_ERROR);
1200 return error;
1201}
1202
1203/*
1204 * Allocate a variable extent anywhere in the allocation group agno.
1205 * Extent's length (returned in len) will be between minlen and maxlen,
1206 * and of the form k * prod + mod unless there's nothing that large.
1207 * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
1208 */
1209STATIC int /* error */
1210xfs_alloc_ag_vextent_size(
1211 xfs_alloc_arg_t *args) /* allocation argument structure */
1212{
1213 xfs_btree_cur_t *bno_cur; /* cursor for bno btree */
1214 xfs_btree_cur_t *cnt_cur; /* cursor for cnt btree */
1215 int error; /* error result */
1216 xfs_agblock_t fbno; /* start of found freespace */
1217 xfs_extlen_t flen; /* length of found freespace */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001218 int i; /* temp status variable */
1219 xfs_agblock_t rbno; /* returned block number */
1220 xfs_extlen_t rlen; /* length of returned extent */
Christoph Hellwige26f0502011-04-24 19:06:15 +00001221 int forced = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001222
Christoph Hellwige26f0502011-04-24 19:06:15 +00001223restart:
Linus Torvalds1da177e2005-04-16 15:20:36 -07001224 /*
1225 * Allocate and initialize a cursor for the by-size btree.
1226 */
Christoph Hellwig561f7d12008-10-30 16:53:59 +11001227 cnt_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
1228 args->agno, XFS_BTNUM_CNT);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001229 bno_cur = NULL;
Christoph Hellwige26f0502011-04-24 19:06:15 +00001230
Linus Torvalds1da177e2005-04-16 15:20:36 -07001231 /*
1232 * Look for an entry >= maxlen+alignment-1 blocks.
1233 */
1234 if ((error = xfs_alloc_lookup_ge(cnt_cur, 0,
1235 args->maxlen + args->alignment - 1, &i)))
1236 goto error0;
Christoph Hellwige26f0502011-04-24 19:06:15 +00001237
Linus Torvalds1da177e2005-04-16 15:20:36 -07001238 /*
Christoph Hellwige26f0502011-04-24 19:06:15 +00001239 * If none or we have busy extents that we cannot allocate from, then
1240 * we have to settle for a smaller extent. In the case that there are
1241 * no large extents, this will return the last entry in the tree unless
1242 * the tree is empty. In the case that there are only busy large
1243 * extents, this will return the largest small extent unless there
1244 * are no smaller extents available.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001245 */
Christoph Hellwige26f0502011-04-24 19:06:15 +00001246 if (!i || forced > 1) {
1247 error = xfs_alloc_ag_vextent_small(args, cnt_cur,
1248 &fbno, &flen, &i);
1249 if (error)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001250 goto error0;
1251 if (i == 0 || flen == 0) {
1252 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00001253 trace_xfs_alloc_size_noentry(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001254 return 0;
1255 }
1256 ASSERT(i == 1);
Christoph Hellwige26f0502011-04-24 19:06:15 +00001257 xfs_alloc_compute_aligned(args, fbno, flen, &rbno, &rlen);
1258 } else {
1259 /*
1260 * Search for a non-busy extent that is large enough.
1261 * If we are at low space, don't check, or if we fall of
1262 * the end of the btree, turn off the busy check and
1263 * restart.
1264 */
1265 for (;;) {
1266 error = xfs_alloc_get_rec(cnt_cur, &fbno, &flen, &i);
1267 if (error)
1268 goto error0;
1269 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1270
1271 xfs_alloc_compute_aligned(args, fbno, flen,
1272 &rbno, &rlen);
1273
1274 if (rlen >= args->maxlen)
1275 break;
1276
1277 error = xfs_btree_increment(cnt_cur, 0, &i);
1278 if (error)
1279 goto error0;
1280 if (i == 0) {
1281 /*
1282 * Our only valid extents must have been busy.
1283 * Make it unbusy by forcing the log out and
1284 * retrying. If we've been here before, forcing
1285 * the log isn't making the extents available,
1286 * which means they have probably been freed in
1287 * this transaction. In that case, we have to
1288 * give up on them and we'll attempt a minlen
1289 * allocation the next time around.
1290 */
1291 xfs_btree_del_cursor(cnt_cur,
1292 XFS_BTREE_NOERROR);
1293 trace_xfs_alloc_size_busy(args);
1294 if (!forced++)
1295 xfs_log_force(args->mp, XFS_LOG_SYNC);
1296 goto restart;
1297 }
1298 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001299 }
Christoph Hellwige26f0502011-04-24 19:06:15 +00001300
Linus Torvalds1da177e2005-04-16 15:20:36 -07001301 /*
1302 * In the first case above, we got the last entry in the
1303 * by-size btree. Now we check to see if the space hits maxlen
1304 * once aligned; if not, we search left for something better.
1305 * This can't happen in the second case above.
1306 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001307 rlen = XFS_EXTLEN_MIN(args->maxlen, rlen);
1308 XFS_WANT_CORRUPTED_GOTO(rlen == 0 ||
1309 (rlen <= flen && rbno + rlen <= fbno + flen), error0);
1310 if (rlen < args->maxlen) {
1311 xfs_agblock_t bestfbno;
1312 xfs_extlen_t bestflen;
1313 xfs_agblock_t bestrbno;
1314 xfs_extlen_t bestrlen;
1315
1316 bestrlen = rlen;
1317 bestrbno = rbno;
1318 bestflen = flen;
1319 bestfbno = fbno;
1320 for (;;) {
Christoph Hellwig8df4da42008-10-30 16:55:58 +11001321 if ((error = xfs_btree_decrement(cnt_cur, 0, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001322 goto error0;
1323 if (i == 0)
1324 break;
1325 if ((error = xfs_alloc_get_rec(cnt_cur, &fbno, &flen,
1326 &i)))
1327 goto error0;
1328 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1329 if (flen < bestrlen)
1330 break;
Christoph Hellwig86fa8af2011-03-04 12:59:54 +00001331 xfs_alloc_compute_aligned(args, fbno, flen,
1332 &rbno, &rlen);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001333 rlen = XFS_EXTLEN_MIN(args->maxlen, rlen);
1334 XFS_WANT_CORRUPTED_GOTO(rlen == 0 ||
1335 (rlen <= flen && rbno + rlen <= fbno + flen),
1336 error0);
1337 if (rlen > bestrlen) {
1338 bestrlen = rlen;
1339 bestrbno = rbno;
1340 bestflen = flen;
1341 bestfbno = fbno;
1342 if (rlen == args->maxlen)
1343 break;
1344 }
1345 }
1346 if ((error = xfs_alloc_lookup_eq(cnt_cur, bestfbno, bestflen,
1347 &i)))
1348 goto error0;
1349 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1350 rlen = bestrlen;
1351 rbno = bestrbno;
1352 flen = bestflen;
1353 fbno = bestfbno;
1354 }
1355 args->wasfromfl = 0;
1356 /*
1357 * Fix up the length.
1358 */
1359 args->len = rlen;
Christoph Hellwige26f0502011-04-24 19:06:15 +00001360 if (rlen < args->minlen) {
1361 if (!forced++) {
1362 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1363 trace_xfs_alloc_size_busy(args);
1364 xfs_log_force(args->mp, XFS_LOG_SYNC);
1365 goto restart;
1366 }
1367 goto out_nominleft;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001368 }
Christoph Hellwige26f0502011-04-24 19:06:15 +00001369 xfs_alloc_fix_len(args);
1370
1371 if (!xfs_alloc_fix_minleft(args))
1372 goto out_nominleft;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001373 rlen = args->len;
1374 XFS_WANT_CORRUPTED_GOTO(rlen <= flen, error0);
1375 /*
1376 * Allocate and initialize a cursor for the by-block tree.
1377 */
Christoph Hellwig561f7d12008-10-30 16:53:59 +11001378 bno_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
1379 args->agno, XFS_BTNUM_BNO);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001380 if ((error = xfs_alloc_fixup_trees(cnt_cur, bno_cur, fbno, flen,
1381 rbno, rlen, XFSA_FIXUP_CNT_OK)))
1382 goto error0;
1383 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1384 xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
1385 cnt_cur = bno_cur = NULL;
1386 args->len = rlen;
1387 args->agbno = rbno;
1388 XFS_WANT_CORRUPTED_GOTO(
1389 args->agbno + args->len <=
Christoph Hellwig16259e72005-11-02 15:11:25 +11001390 be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length),
Linus Torvalds1da177e2005-04-16 15:20:36 -07001391 error0);
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00001392 trace_xfs_alloc_size_done(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001393 return 0;
1394
1395error0:
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00001396 trace_xfs_alloc_size_error(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001397 if (cnt_cur)
1398 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
1399 if (bno_cur)
1400 xfs_btree_del_cursor(bno_cur, XFS_BTREE_ERROR);
1401 return error;
Christoph Hellwige26f0502011-04-24 19:06:15 +00001402
1403out_nominleft:
1404 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1405 trace_xfs_alloc_size_nominleft(args);
1406 args->agbno = NULLAGBLOCK;
1407 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001408}
1409
1410/*
1411 * Deal with the case where only small freespaces remain.
1412 * Either return the contents of the last freespace record,
1413 * or allocate space from the freelist if there is nothing in the tree.
1414 */
1415STATIC int /* error */
1416xfs_alloc_ag_vextent_small(
1417 xfs_alloc_arg_t *args, /* allocation argument structure */
1418 xfs_btree_cur_t *ccur, /* by-size cursor */
1419 xfs_agblock_t *fbnop, /* result block number */
1420 xfs_extlen_t *flenp, /* result length */
1421 int *stat) /* status: 0-freelist, 1-normal/none */
1422{
1423 int error;
1424 xfs_agblock_t fbno;
1425 xfs_extlen_t flen;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001426 int i;
1427
Christoph Hellwig8df4da42008-10-30 16:55:58 +11001428 if ((error = xfs_btree_decrement(ccur, 0, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001429 goto error0;
1430 if (i) {
1431 if ((error = xfs_alloc_get_rec(ccur, &fbno, &flen, &i)))
1432 goto error0;
1433 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1434 }
1435 /*
1436 * Nothing in the btree, try the freelist. Make sure
1437 * to respect minleft even when pulling from the
1438 * freelist.
1439 */
1440 else if (args->minlen == 1 && args->alignment == 1 && !args->isfl &&
Christoph Hellwig16259e72005-11-02 15:11:25 +11001441 (be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_flcount)
1442 > args->minleft)) {
David Chinner92821e22007-05-24 15:26:31 +10001443 error = xfs_alloc_get_freelist(args->tp, args->agbp, &fbno, 0);
1444 if (error)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001445 goto error0;
1446 if (fbno != NULLAGBLOCK) {
Dave Chinner4ecbfe62012-04-29 10:41:10 +00001447 xfs_extent_busy_reuse(args->mp, args->agno, fbno, 1,
Christoph Hellwig97d3ac72011-04-24 19:06:16 +00001448 args->userdata);
1449
Linus Torvalds1da177e2005-04-16 15:20:36 -07001450 if (args->userdata) {
1451 xfs_buf_t *bp;
1452
1453 bp = xfs_btree_get_bufs(args->mp, args->tp,
1454 args->agno, fbno, 0);
1455 xfs_trans_binval(args->tp, bp);
1456 }
1457 args->len = 1;
1458 args->agbno = fbno;
1459 XFS_WANT_CORRUPTED_GOTO(
1460 args->agbno + args->len <=
Christoph Hellwig16259e72005-11-02 15:11:25 +11001461 be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length),
Linus Torvalds1da177e2005-04-16 15:20:36 -07001462 error0);
1463 args->wasfromfl = 1;
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00001464 trace_xfs_alloc_small_freelist(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001465 *stat = 0;
1466 return 0;
1467 }
1468 /*
1469 * Nothing in the freelist.
1470 */
1471 else
1472 flen = 0;
1473 }
1474 /*
1475 * Can't allocate from the freelist for some reason.
1476 */
Nathan Scottd432c802006-09-28 11:03:44 +10001477 else {
1478 fbno = NULLAGBLOCK;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001479 flen = 0;
Nathan Scottd432c802006-09-28 11:03:44 +10001480 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001481 /*
1482 * Can't do the allocation, give up.
1483 */
1484 if (flen < args->minlen) {
1485 args->agbno = NULLAGBLOCK;
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00001486 trace_xfs_alloc_small_notenough(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001487 flen = 0;
1488 }
1489 *fbnop = fbno;
1490 *flenp = flen;
1491 *stat = 1;
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00001492 trace_xfs_alloc_small_done(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001493 return 0;
1494
1495error0:
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00001496 trace_xfs_alloc_small_error(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001497 return error;
1498}
1499
1500/*
1501 * Free the extent starting at agno/bno for length.
1502 */
1503STATIC int /* error */
1504xfs_free_ag_extent(
1505 xfs_trans_t *tp, /* transaction pointer */
1506 xfs_buf_t *agbp, /* buffer for a.g. freelist header */
1507 xfs_agnumber_t agno, /* allocation group number */
1508 xfs_agblock_t bno, /* starting block number */
1509 xfs_extlen_t len, /* length of extent */
1510 int isfl) /* set if is freelist blocks - no sb acctg */
1511{
1512 xfs_btree_cur_t *bno_cur; /* cursor for by-block btree */
1513 xfs_btree_cur_t *cnt_cur; /* cursor for by-size btree */
1514 int error; /* error return value */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001515 xfs_agblock_t gtbno; /* start of right neighbor block */
1516 xfs_extlen_t gtlen; /* length of right neighbor block */
1517 int haveleft; /* have a left neighbor block */
1518 int haveright; /* have a right neighbor block */
1519 int i; /* temp, result code */
1520 xfs_agblock_t ltbno; /* start of left neighbor block */
1521 xfs_extlen_t ltlen; /* length of left neighbor block */
1522 xfs_mount_t *mp; /* mount point struct for filesystem */
1523 xfs_agblock_t nbno; /* new starting block of freespace */
1524 xfs_extlen_t nlen; /* new length of freespace */
Christoph Hellwigecb69282011-03-04 12:59:55 +00001525 xfs_perag_t *pag; /* per allocation group data */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001526
1527 mp = tp->t_mountp;
1528 /*
1529 * Allocate and initialize a cursor for the by-block btree.
1530 */
Christoph Hellwig561f7d12008-10-30 16:53:59 +11001531 bno_cur = xfs_allocbt_init_cursor(mp, tp, agbp, agno, XFS_BTNUM_BNO);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001532 cnt_cur = NULL;
1533 /*
1534 * Look for a neighboring block on the left (lower block numbers)
1535 * that is contiguous with this space.
1536 */
1537 if ((error = xfs_alloc_lookup_le(bno_cur, bno, len, &haveleft)))
1538 goto error0;
1539 if (haveleft) {
1540 /*
1541 * There is a block to our left.
1542 */
1543 if ((error = xfs_alloc_get_rec(bno_cur, &ltbno, &ltlen, &i)))
1544 goto error0;
1545 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1546 /*
1547 * It's not contiguous, though.
1548 */
1549 if (ltbno + ltlen < bno)
1550 haveleft = 0;
1551 else {
1552 /*
1553 * If this failure happens the request to free this
1554 * space was invalid, it's (partly) already free.
1555 * Very bad.
1556 */
1557 XFS_WANT_CORRUPTED_GOTO(ltbno + ltlen <= bno, error0);
1558 }
1559 }
1560 /*
1561 * Look for a neighboring block on the right (higher block numbers)
1562 * that is contiguous with this space.
1563 */
Christoph Hellwig637aa502008-10-30 16:55:45 +11001564 if ((error = xfs_btree_increment(bno_cur, 0, &haveright)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001565 goto error0;
1566 if (haveright) {
1567 /*
1568 * There is a block to our right.
1569 */
1570 if ((error = xfs_alloc_get_rec(bno_cur, &gtbno, &gtlen, &i)))
1571 goto error0;
1572 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1573 /*
1574 * It's not contiguous, though.
1575 */
1576 if (bno + len < gtbno)
1577 haveright = 0;
1578 else {
1579 /*
1580 * If this failure happens the request to free this
1581 * space was invalid, it's (partly) already free.
1582 * Very bad.
1583 */
1584 XFS_WANT_CORRUPTED_GOTO(gtbno >= bno + len, error0);
1585 }
1586 }
1587 /*
1588 * Now allocate and initialize a cursor for the by-size tree.
1589 */
Christoph Hellwig561f7d12008-10-30 16:53:59 +11001590 cnt_cur = xfs_allocbt_init_cursor(mp, tp, agbp, agno, XFS_BTNUM_CNT);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001591 /*
1592 * Have both left and right contiguous neighbors.
1593 * Merge all three into a single free block.
1594 */
1595 if (haveleft && haveright) {
1596 /*
1597 * Delete the old by-size entry on the left.
1598 */
1599 if ((error = xfs_alloc_lookup_eq(cnt_cur, ltbno, ltlen, &i)))
1600 goto error0;
1601 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
Christoph Hellwig91cca5df2008-10-30 16:58:01 +11001602 if ((error = xfs_btree_delete(cnt_cur, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001603 goto error0;
1604 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1605 /*
1606 * Delete the old by-size entry on the right.
1607 */
1608 if ((error = xfs_alloc_lookup_eq(cnt_cur, gtbno, gtlen, &i)))
1609 goto error0;
1610 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
Christoph Hellwig91cca5df2008-10-30 16:58:01 +11001611 if ((error = xfs_btree_delete(cnt_cur, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001612 goto error0;
1613 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1614 /*
1615 * Delete the old by-block entry for the right block.
1616 */
Christoph Hellwig91cca5df2008-10-30 16:58:01 +11001617 if ((error = xfs_btree_delete(bno_cur, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001618 goto error0;
1619 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1620 /*
1621 * Move the by-block cursor back to the left neighbor.
1622 */
Christoph Hellwig8df4da42008-10-30 16:55:58 +11001623 if ((error = xfs_btree_decrement(bno_cur, 0, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001624 goto error0;
1625 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1626#ifdef DEBUG
1627 /*
1628 * Check that this is the right record: delete didn't
1629 * mangle the cursor.
1630 */
1631 {
1632 xfs_agblock_t xxbno;
1633 xfs_extlen_t xxlen;
1634
1635 if ((error = xfs_alloc_get_rec(bno_cur, &xxbno, &xxlen,
1636 &i)))
1637 goto error0;
1638 XFS_WANT_CORRUPTED_GOTO(
1639 i == 1 && xxbno == ltbno && xxlen == ltlen,
1640 error0);
1641 }
1642#endif
1643 /*
1644 * Update remaining by-block entry to the new, joined block.
1645 */
1646 nbno = ltbno;
1647 nlen = len + ltlen + gtlen;
1648 if ((error = xfs_alloc_update(bno_cur, nbno, nlen)))
1649 goto error0;
1650 }
1651 /*
1652 * Have only a left contiguous neighbor.
1653 * Merge it together with the new freespace.
1654 */
1655 else if (haveleft) {
1656 /*
1657 * Delete the old by-size entry on the left.
1658 */
1659 if ((error = xfs_alloc_lookup_eq(cnt_cur, ltbno, ltlen, &i)))
1660 goto error0;
1661 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
Christoph Hellwig91cca5df2008-10-30 16:58:01 +11001662 if ((error = xfs_btree_delete(cnt_cur, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001663 goto error0;
1664 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1665 /*
1666 * Back up the by-block cursor to the left neighbor, and
1667 * update its length.
1668 */
Christoph Hellwig8df4da42008-10-30 16:55:58 +11001669 if ((error = xfs_btree_decrement(bno_cur, 0, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001670 goto error0;
1671 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1672 nbno = ltbno;
1673 nlen = len + ltlen;
1674 if ((error = xfs_alloc_update(bno_cur, nbno, nlen)))
1675 goto error0;
1676 }
1677 /*
1678 * Have only a right contiguous neighbor.
1679 * Merge it together with the new freespace.
1680 */
1681 else if (haveright) {
1682 /*
1683 * Delete the old by-size entry on the right.
1684 */
1685 if ((error = xfs_alloc_lookup_eq(cnt_cur, gtbno, gtlen, &i)))
1686 goto error0;
1687 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
Christoph Hellwig91cca5df2008-10-30 16:58:01 +11001688 if ((error = xfs_btree_delete(cnt_cur, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001689 goto error0;
1690 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1691 /*
1692 * Update the starting block and length of the right
1693 * neighbor in the by-block tree.
1694 */
1695 nbno = bno;
1696 nlen = len + gtlen;
1697 if ((error = xfs_alloc_update(bno_cur, nbno, nlen)))
1698 goto error0;
1699 }
1700 /*
1701 * No contiguous neighbors.
1702 * Insert the new freespace into the by-block tree.
1703 */
1704 else {
1705 nbno = bno;
1706 nlen = len;
Christoph Hellwig4b22a572008-10-30 16:57:40 +11001707 if ((error = xfs_btree_insert(bno_cur, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001708 goto error0;
1709 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1710 }
1711 xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
1712 bno_cur = NULL;
1713 /*
1714 * In all cases we need to insert the new freespace in the by-size tree.
1715 */
1716 if ((error = xfs_alloc_lookup_eq(cnt_cur, nbno, nlen, &i)))
1717 goto error0;
1718 XFS_WANT_CORRUPTED_GOTO(i == 0, error0);
Christoph Hellwig4b22a572008-10-30 16:57:40 +11001719 if ((error = xfs_btree_insert(cnt_cur, &i)))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001720 goto error0;
1721 XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
1722 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1723 cnt_cur = NULL;
Christoph Hellwigecb69282011-03-04 12:59:55 +00001724
Linus Torvalds1da177e2005-04-16 15:20:36 -07001725 /*
1726 * Update the freespace totals in the ag and superblock.
1727 */
Christoph Hellwigecb69282011-03-04 12:59:55 +00001728 pag = xfs_perag_get(mp, agno);
1729 error = xfs_alloc_update_counters(tp, pag, agbp, len);
1730 xfs_perag_put(pag);
1731 if (error)
1732 goto error0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001733
Christoph Hellwigecb69282011-03-04 12:59:55 +00001734 if (!isfl)
1735 xfs_trans_mod_sb(tp, XFS_TRANS_SB_FDBLOCKS, (long)len);
1736 XFS_STATS_INC(xs_freex);
1737 XFS_STATS_ADD(xs_freeb, len);
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00001738
1739 trace_xfs_free_extent(mp, agno, bno, len, isfl, haveleft, haveright);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001740
Linus Torvalds1da177e2005-04-16 15:20:36 -07001741 return 0;
1742
1743 error0:
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00001744 trace_xfs_free_extent(mp, agno, bno, len, isfl, -1, -1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001745 if (bno_cur)
1746 xfs_btree_del_cursor(bno_cur, XFS_BTREE_ERROR);
1747 if (cnt_cur)
1748 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
1749 return error;
1750}
1751
1752/*
1753 * Visible (exported) allocation/free functions.
1754 * Some of these are used just by xfs_alloc_btree.c and this file.
1755 */
1756
1757/*
1758 * Compute and fill in value of m_ag_maxlevels.
1759 */
1760void
1761xfs_alloc_compute_maxlevels(
1762 xfs_mount_t *mp) /* file system mount structure */
1763{
1764 int level;
1765 uint maxblocks;
1766 uint maxleafents;
1767 int minleafrecs;
1768 int minnoderecs;
1769
1770 maxleafents = (mp->m_sb.sb_agblocks + 1) / 2;
1771 minleafrecs = mp->m_alloc_mnr[0];
1772 minnoderecs = mp->m_alloc_mnr[1];
1773 maxblocks = (maxleafents + minleafrecs - 1) / minleafrecs;
1774 for (level = 1; maxblocks > 1; level++)
1775 maxblocks = (maxblocks + minnoderecs - 1) / minnoderecs;
1776 mp->m_ag_maxlevels = level;
1777}
1778
1779/*
Dave Chinner6cc87642009-03-16 08:29:46 +01001780 * Find the length of the longest extent in an AG.
1781 */
1782xfs_extlen_t
1783xfs_alloc_longest_free_extent(
1784 struct xfs_mount *mp,
1785 struct xfs_perag *pag)
1786{
1787 xfs_extlen_t need, delta = 0;
1788
1789 need = XFS_MIN_FREELIST_PAG(pag, mp);
1790 if (need > pag->pagf_flcount)
1791 delta = need - pag->pagf_flcount;
1792
1793 if (pag->pagf_longest > delta)
1794 return pag->pagf_longest - delta;
1795 return pag->pagf_flcount > 0 || pag->pagf_longest > 0;
1796}
1797
1798/*
Linus Torvalds1da177e2005-04-16 15:20:36 -07001799 * Decide whether to use this allocation group for this allocation.
1800 * If so, fix up the btree freelist's size.
1801 */
1802STATIC int /* error */
1803xfs_alloc_fix_freelist(
1804 xfs_alloc_arg_t *args, /* allocation argument structure */
1805 int flags) /* XFS_ALLOC_FLAG_... */
1806{
1807 xfs_buf_t *agbp; /* agf buffer pointer */
1808 xfs_agf_t *agf; /* a.g. freespace structure pointer */
1809 xfs_buf_t *agflbp;/* agfl buffer pointer */
1810 xfs_agblock_t bno; /* freelist block */
1811 xfs_extlen_t delta; /* new blocks needed in freelist */
1812 int error; /* error result code */
1813 xfs_extlen_t longest;/* longest extent in allocation group */
1814 xfs_mount_t *mp; /* file system mount point structure */
1815 xfs_extlen_t need; /* total blocks needed in freelist */
1816 xfs_perag_t *pag; /* per-ag information structure */
1817 xfs_alloc_arg_t targs; /* local allocation arguments */
1818 xfs_trans_t *tp; /* transaction pointer */
1819
1820 mp = args->mp;
1821
1822 pag = args->pag;
1823 tp = args->tp;
1824 if (!pag->pagf_init) {
1825 if ((error = xfs_alloc_read_agf(mp, tp, args->agno, flags,
1826 &agbp)))
1827 return error;
1828 if (!pag->pagf_init) {
Nathan Scott0e1edbd2006-08-10 14:40:41 +10001829 ASSERT(flags & XFS_ALLOC_FLAG_TRYLOCK);
1830 ASSERT(!(flags & XFS_ALLOC_FLAG_FREEING));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001831 args->agbp = NULL;
1832 return 0;
1833 }
1834 } else
1835 agbp = NULL;
1836
Nathan Scott0e1edbd2006-08-10 14:40:41 +10001837 /*
1838 * If this is a metadata preferred pag and we are user data
Linus Torvalds1da177e2005-04-16 15:20:36 -07001839 * then try somewhere else if we are not being asked to
1840 * try harder at this point
1841 */
Nathan Scott0e1edbd2006-08-10 14:40:41 +10001842 if (pag->pagf_metadata && args->userdata &&
1843 (flags & XFS_ALLOC_FLAG_TRYLOCK)) {
1844 ASSERT(!(flags & XFS_ALLOC_FLAG_FREEING));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001845 args->agbp = NULL;
1846 return 0;
1847 }
1848
Nathan Scott0e1edbd2006-08-10 14:40:41 +10001849 if (!(flags & XFS_ALLOC_FLAG_FREEING)) {
Nathan Scott0e1edbd2006-08-10 14:40:41 +10001850 /*
1851 * If it looks like there isn't a long enough extent, or enough
1852 * total blocks, reject it.
1853 */
Dave Chinner6cc87642009-03-16 08:29:46 +01001854 need = XFS_MIN_FREELIST_PAG(pag, mp);
1855 longest = xfs_alloc_longest_free_extent(mp, pag);
Nathan Scott0e1edbd2006-08-10 14:40:41 +10001856 if ((args->minlen + args->alignment + args->minalignslop - 1) >
1857 longest ||
1858 ((int)(pag->pagf_freeblks + pag->pagf_flcount -
1859 need - args->total) < (int)args->minleft)) {
1860 if (agbp)
1861 xfs_trans_brelse(tp, agbp);
1862 args->agbp = NULL;
1863 return 0;
1864 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001865 }
Nathan Scott0e1edbd2006-08-10 14:40:41 +10001866
Linus Torvalds1da177e2005-04-16 15:20:36 -07001867 /*
1868 * Get the a.g. freespace buffer.
1869 * Can fail if we're not blocking on locks, and it's held.
1870 */
1871 if (agbp == NULL) {
1872 if ((error = xfs_alloc_read_agf(mp, tp, args->agno, flags,
1873 &agbp)))
1874 return error;
1875 if (agbp == NULL) {
Nathan Scott0e1edbd2006-08-10 14:40:41 +10001876 ASSERT(flags & XFS_ALLOC_FLAG_TRYLOCK);
1877 ASSERT(!(flags & XFS_ALLOC_FLAG_FREEING));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001878 args->agbp = NULL;
1879 return 0;
1880 }
1881 }
1882 /*
1883 * Figure out how many blocks we should have in the freelist.
1884 */
1885 agf = XFS_BUF_TO_AGF(agbp);
1886 need = XFS_MIN_FREELIST(agf, mp);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001887 /*
1888 * If there isn't enough total or single-extent, reject it.
1889 */
Nathan Scott0e1edbd2006-08-10 14:40:41 +10001890 if (!(flags & XFS_ALLOC_FLAG_FREEING)) {
1891 delta = need > be32_to_cpu(agf->agf_flcount) ?
1892 (need - be32_to_cpu(agf->agf_flcount)) : 0;
1893 longest = be32_to_cpu(agf->agf_longest);
1894 longest = (longest > delta) ? (longest - delta) :
1895 (be32_to_cpu(agf->agf_flcount) > 0 || longest > 0);
1896 if ((args->minlen + args->alignment + args->minalignslop - 1) >
1897 longest ||
1898 ((int)(be32_to_cpu(agf->agf_freeblks) +
1899 be32_to_cpu(agf->agf_flcount) - need - args->total) <
1900 (int)args->minleft)) {
1901 xfs_trans_brelse(tp, agbp);
1902 args->agbp = NULL;
1903 return 0;
1904 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001905 }
1906 /*
1907 * Make the freelist shorter if it's too long.
1908 */
Christoph Hellwig16259e72005-11-02 15:11:25 +11001909 while (be32_to_cpu(agf->agf_flcount) > need) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001910 xfs_buf_t *bp;
1911
David Chinner92821e22007-05-24 15:26:31 +10001912 error = xfs_alloc_get_freelist(tp, agbp, &bno, 0);
1913 if (error)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001914 return error;
1915 if ((error = xfs_free_ag_extent(tp, agbp, args->agno, bno, 1, 1)))
1916 return error;
1917 bp = xfs_btree_get_bufs(mp, tp, args->agno, bno, 0);
1918 xfs_trans_binval(tp, bp);
1919 }
1920 /*
1921 * Initialize the args structure.
1922 */
Mark Tinguelya0041682012-09-20 13:16:45 -05001923 memset(&targs, 0, sizeof(targs));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001924 targs.tp = tp;
1925 targs.mp = mp;
1926 targs.agbp = agbp;
1927 targs.agno = args->agno;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001928 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 Chinner1813dd62012-11-14 17:54:40 +11002184static void
2185xfs_agf_read_verify(
Dave Chinner612cfbf2012-11-14 17:52:32 +11002186 struct xfs_buf *bp)
2187{
2188 xfs_agf_verify(bp);
2189}
2190
Dave Chinnerb0f539d2012-11-14 17:53:49 +11002191static void
Dave Chinner1813dd62012-11-14 17:54:40 +11002192xfs_agf_write_verify(
Dave Chinner612cfbf2012-11-14 17:52:32 +11002193 struct xfs_buf *bp)
2194{
2195 xfs_agf_verify(bp);
Dave Chinner5d5f5272012-11-14 17:44:56 +11002196}
2197
Dave Chinner1813dd62012-11-14 17:54:40 +11002198const struct xfs_buf_ops xfs_agf_buf_ops = {
2199 .verify_read = xfs_agf_read_verify,
2200 .verify_write = xfs_agf_write_verify,
2201};
2202
Linus Torvalds1da177e2005-04-16 15:20:36 -07002203/*
2204 * Read in the allocation group header (free/alloc section).
2205 */
2206int /* error */
From: Christoph Hellwig48056212008-11-28 14:23:38 +11002207xfs_read_agf(
2208 struct xfs_mount *mp, /* mount point structure */
2209 struct xfs_trans *tp, /* transaction pointer */
2210 xfs_agnumber_t agno, /* allocation group number */
2211 int flags, /* XFS_BUF_ */
2212 struct xfs_buf **bpp) /* buffer for the ag freelist header */
Linus Torvalds1da177e2005-04-16 15:20:36 -07002213{
Linus Torvalds1da177e2005-04-16 15:20:36 -07002214 int error;
2215
2216 ASSERT(agno != NULLAGNUMBER);
2217 error = xfs_trans_read_buf(
2218 mp, tp, mp->m_ddev_targp,
2219 XFS_AG_DADDR(mp, agno, XFS_AGF_DADDR(mp)),
Dave Chinner1813dd62012-11-14 17:54:40 +11002220 XFS_FSS_TO_BB(mp, 1), flags, bpp, &xfs_agf_buf_ops);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002221 if (error)
2222 return error;
From: Christoph Hellwig48056212008-11-28 14:23:38 +11002223 if (!*bpp)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002224 return 0;
From: Christoph Hellwig48056212008-11-28 14:23:38 +11002225
Chandra Seetharaman5a52c2a582011-07-22 23:39:51 +00002226 ASSERT(!(*bpp)->b_error);
Christoph Hellwig38f23232011-10-10 16:52:45 +00002227 xfs_buf_set_ref(*bpp, XFS_AGF_REF);
From: Christoph Hellwig48056212008-11-28 14:23:38 +11002228 return 0;
2229}
2230
2231/*
2232 * Read in the allocation group header (free/alloc section).
2233 */
2234int /* error */
2235xfs_alloc_read_agf(
2236 struct xfs_mount *mp, /* mount point structure */
2237 struct xfs_trans *tp, /* transaction pointer */
2238 xfs_agnumber_t agno, /* allocation group number */
2239 int flags, /* XFS_ALLOC_FLAG_... */
2240 struct xfs_buf **bpp) /* buffer for the ag freelist header */
2241{
2242 struct xfs_agf *agf; /* ag freelist header */
2243 struct xfs_perag *pag; /* per allocation group data */
2244 int error;
2245
2246 ASSERT(agno != NULLAGNUMBER);
2247
2248 error = xfs_read_agf(mp, tp, agno,
Christoph Hellwig0cadda12010-01-19 09:56:44 +00002249 (flags & XFS_ALLOC_FLAG_TRYLOCK) ? XBF_TRYLOCK : 0,
From: Christoph Hellwig48056212008-11-28 14:23:38 +11002250 bpp);
2251 if (error)
2252 return error;
2253 if (!*bpp)
2254 return 0;
Chandra Seetharaman5a52c2a582011-07-22 23:39:51 +00002255 ASSERT(!(*bpp)->b_error);
From: Christoph Hellwig48056212008-11-28 14:23:38 +11002256
2257 agf = XFS_BUF_TO_AGF(*bpp);
Dave Chinnera862e0f2010-01-11 11:47:41 +00002258 pag = xfs_perag_get(mp, agno);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002259 if (!pag->pagf_init) {
Christoph Hellwig16259e72005-11-02 15:11:25 +11002260 pag->pagf_freeblks = be32_to_cpu(agf->agf_freeblks);
David Chinner92821e22007-05-24 15:26:31 +10002261 pag->pagf_btreeblks = be32_to_cpu(agf->agf_btreeblks);
Christoph Hellwig16259e72005-11-02 15:11:25 +11002262 pag->pagf_flcount = be32_to_cpu(agf->agf_flcount);
2263 pag->pagf_longest = be32_to_cpu(agf->agf_longest);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002264 pag->pagf_levels[XFS_BTNUM_BNOi] =
Christoph Hellwig16259e72005-11-02 15:11:25 +11002265 be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNOi]);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002266 pag->pagf_levels[XFS_BTNUM_CNTi] =
Christoph Hellwig16259e72005-11-02 15:11:25 +11002267 be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNTi]);
Eric Sandeen007c61c2007-10-11 17:43:56 +10002268 spin_lock_init(&pag->pagb_lock);
Dave Chinnere57336f2010-01-11 11:47:49 +00002269 pag->pagb_count = 0;
Dave Chinnered3b4d62010-05-21 12:07:08 +10002270 pag->pagb_tree = RB_ROOT;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002271 pag->pagf_init = 1;
2272 }
2273#ifdef DEBUG
2274 else if (!XFS_FORCED_SHUTDOWN(mp)) {
Christoph Hellwig16259e72005-11-02 15:11:25 +11002275 ASSERT(pag->pagf_freeblks == be32_to_cpu(agf->agf_freeblks));
Barry Naujok89b28392008-10-30 17:05:49 +11002276 ASSERT(pag->pagf_btreeblks == be32_to_cpu(agf->agf_btreeblks));
Christoph Hellwig16259e72005-11-02 15:11:25 +11002277 ASSERT(pag->pagf_flcount == be32_to_cpu(agf->agf_flcount));
2278 ASSERT(pag->pagf_longest == be32_to_cpu(agf->agf_longest));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002279 ASSERT(pag->pagf_levels[XFS_BTNUM_BNOi] ==
Christoph Hellwig16259e72005-11-02 15:11:25 +11002280 be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNOi]));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002281 ASSERT(pag->pagf_levels[XFS_BTNUM_CNTi] ==
Christoph Hellwig16259e72005-11-02 15:11:25 +11002282 be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNTi]));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002283 }
2284#endif
Dave Chinnera862e0f2010-01-11 11:47:41 +00002285 xfs_perag_put(pag);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002286 return 0;
2287}
2288
2289/*
2290 * Allocate an extent (variable-size).
2291 * Depending on the allocation type, we either look in a single allocation
2292 * group or loop over the allocation groups to find the result.
2293 */
2294int /* error */
Dave Chinnere04426b2012-10-05 11:06:59 +10002295xfs_alloc_vextent(
Linus Torvalds1da177e2005-04-16 15:20:36 -07002296 xfs_alloc_arg_t *args) /* allocation argument structure */
2297{
2298 xfs_agblock_t agsize; /* allocation group size */
2299 int error;
2300 int flags; /* XFS_ALLOC_FLAG_... locking flags */
Linus Torvalds1da177e2005-04-16 15:20:36 -07002301 xfs_extlen_t minleft;/* minimum left value, temp copy */
2302 xfs_mount_t *mp; /* mount structure pointer */
2303 xfs_agnumber_t sagno; /* starting allocation group number */
2304 xfs_alloctype_t type; /* input allocation type */
2305 int bump_rotor = 0;
2306 int no_min = 0;
2307 xfs_agnumber_t rotorstep = xfs_rotorstep; /* inode32 agf stepper */
2308
2309 mp = args->mp;
2310 type = args->otype = args->type;
2311 args->agbno = NULLAGBLOCK;
2312 /*
2313 * Just fix this up, for the case where the last a.g. is shorter
2314 * (or there's only one a.g.) and the caller couldn't easily figure
2315 * that out (xfs_bmap_alloc).
2316 */
2317 agsize = mp->m_sb.sb_agblocks;
2318 if (args->maxlen > agsize)
2319 args->maxlen = agsize;
2320 if (args->alignment == 0)
2321 args->alignment = 1;
2322 ASSERT(XFS_FSB_TO_AGNO(mp, args->fsbno) < mp->m_sb.sb_agcount);
2323 ASSERT(XFS_FSB_TO_AGBNO(mp, args->fsbno) < agsize);
2324 ASSERT(args->minlen <= args->maxlen);
2325 ASSERT(args->minlen <= agsize);
2326 ASSERT(args->mod < args->prod);
2327 if (XFS_FSB_TO_AGNO(mp, args->fsbno) >= mp->m_sb.sb_agcount ||
2328 XFS_FSB_TO_AGBNO(mp, args->fsbno) >= agsize ||
2329 args->minlen > args->maxlen || args->minlen > agsize ||
2330 args->mod >= args->prod) {
2331 args->fsbno = NULLFSBLOCK;
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00002332 trace_xfs_alloc_vextent_badargs(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002333 return 0;
2334 }
2335 minleft = args->minleft;
2336
2337 switch (type) {
2338 case XFS_ALLOCTYPE_THIS_AG:
2339 case XFS_ALLOCTYPE_NEAR_BNO:
2340 case XFS_ALLOCTYPE_THIS_BNO:
2341 /*
2342 * These three force us into a single a.g.
2343 */
2344 args->agno = XFS_FSB_TO_AGNO(mp, args->fsbno);
Dave Chinnera862e0f2010-01-11 11:47:41 +00002345 args->pag = xfs_perag_get(mp, args->agno);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002346 args->minleft = 0;
2347 error = xfs_alloc_fix_freelist(args, 0);
2348 args->minleft = minleft;
2349 if (error) {
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00002350 trace_xfs_alloc_vextent_nofix(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002351 goto error0;
2352 }
2353 if (!args->agbp) {
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00002354 trace_xfs_alloc_vextent_noagbp(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002355 break;
2356 }
2357 args->agbno = XFS_FSB_TO_AGBNO(mp, args->fsbno);
2358 if ((error = xfs_alloc_ag_vextent(args)))
2359 goto error0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002360 break;
2361 case XFS_ALLOCTYPE_START_BNO:
2362 /*
2363 * Try near allocation first, then anywhere-in-ag after
2364 * the first a.g. fails.
2365 */
2366 if ((args->userdata == XFS_ALLOC_INITIAL_USER_DATA) &&
2367 (mp->m_flags & XFS_MOUNT_32BITINODES)) {
2368 args->fsbno = XFS_AGB_TO_FSB(mp,
2369 ((mp->m_agfrotor / rotorstep) %
2370 mp->m_sb.sb_agcount), 0);
2371 bump_rotor = 1;
2372 }
2373 args->agbno = XFS_FSB_TO_AGBNO(mp, args->fsbno);
2374 args->type = XFS_ALLOCTYPE_NEAR_BNO;
2375 /* FALLTHROUGH */
2376 case XFS_ALLOCTYPE_ANY_AG:
2377 case XFS_ALLOCTYPE_START_AG:
2378 case XFS_ALLOCTYPE_FIRST_AG:
2379 /*
2380 * Rotate through the allocation groups looking for a winner.
2381 */
2382 if (type == XFS_ALLOCTYPE_ANY_AG) {
2383 /*
2384 * Start with the last place we left off.
2385 */
2386 args->agno = sagno = (mp->m_agfrotor / rotorstep) %
2387 mp->m_sb.sb_agcount;
2388 args->type = XFS_ALLOCTYPE_THIS_AG;
2389 flags = XFS_ALLOC_FLAG_TRYLOCK;
2390 } else if (type == XFS_ALLOCTYPE_FIRST_AG) {
2391 /*
2392 * Start with allocation group given by bno.
2393 */
2394 args->agno = XFS_FSB_TO_AGNO(mp, args->fsbno);
2395 args->type = XFS_ALLOCTYPE_THIS_AG;
2396 sagno = 0;
2397 flags = 0;
2398 } else {
2399 if (type == XFS_ALLOCTYPE_START_AG)
2400 args->type = XFS_ALLOCTYPE_THIS_AG;
2401 /*
2402 * Start with the given allocation group.
2403 */
2404 args->agno = sagno = XFS_FSB_TO_AGNO(mp, args->fsbno);
2405 flags = XFS_ALLOC_FLAG_TRYLOCK;
2406 }
2407 /*
2408 * Loop over allocation groups twice; first time with
2409 * trylock set, second time without.
2410 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07002411 for (;;) {
Dave Chinnera862e0f2010-01-11 11:47:41 +00002412 args->pag = xfs_perag_get(mp, args->agno);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002413 if (no_min) args->minleft = 0;
2414 error = xfs_alloc_fix_freelist(args, flags);
2415 args->minleft = minleft;
2416 if (error) {
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00002417 trace_xfs_alloc_vextent_nofix(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002418 goto error0;
2419 }
2420 /*
2421 * If we get a buffer back then the allocation will fly.
2422 */
2423 if (args->agbp) {
2424 if ((error = xfs_alloc_ag_vextent(args)))
2425 goto error0;
2426 break;
2427 }
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00002428
2429 trace_xfs_alloc_vextent_loopfailed(args);
2430
Linus Torvalds1da177e2005-04-16 15:20:36 -07002431 /*
2432 * Didn't work, figure out the next iteration.
2433 */
2434 if (args->agno == sagno &&
2435 type == XFS_ALLOCTYPE_START_BNO)
2436 args->type = XFS_ALLOCTYPE_THIS_AG;
Yingping Lud210a282006-06-09 14:55:18 +10002437 /*
2438 * For the first allocation, we can try any AG to get
2439 * space. However, if we already have allocated a
2440 * block, we don't want to try AGs whose number is below
2441 * sagno. Otherwise, we may end up with out-of-order
2442 * locking of AGF, which might cause deadlock.
2443 */
2444 if (++(args->agno) == mp->m_sb.sb_agcount) {
2445 if (args->firstblock != NULLFSBLOCK)
2446 args->agno = sagno;
2447 else
2448 args->agno = 0;
2449 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002450 /*
2451 * Reached the starting a.g., must either be done
2452 * or switch to non-trylock mode.
2453 */
2454 if (args->agno == sagno) {
2455 if (no_min == 1) {
2456 args->agbno = NULLAGBLOCK;
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00002457 trace_xfs_alloc_vextent_allfailed(args);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002458 break;
2459 }
2460 if (flags == 0) {
2461 no_min = 1;
2462 } else {
2463 flags = 0;
2464 if (type == XFS_ALLOCTYPE_START_BNO) {
2465 args->agbno = XFS_FSB_TO_AGBNO(mp,
2466 args->fsbno);
2467 args->type = XFS_ALLOCTYPE_NEAR_BNO;
2468 }
2469 }
2470 }
Dave Chinnera862e0f2010-01-11 11:47:41 +00002471 xfs_perag_put(args->pag);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002472 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002473 if (bump_rotor || (type == XFS_ALLOCTYPE_ANY_AG)) {
2474 if (args->agno == sagno)
2475 mp->m_agfrotor = (mp->m_agfrotor + 1) %
2476 (mp->m_sb.sb_agcount * rotorstep);
2477 else
2478 mp->m_agfrotor = (args->agno * rotorstep + 1) %
2479 (mp->m_sb.sb_agcount * rotorstep);
2480 }
2481 break;
2482 default:
2483 ASSERT(0);
2484 /* NOTREACHED */
2485 }
2486 if (args->agbno == NULLAGBLOCK)
2487 args->fsbno = NULLFSBLOCK;
2488 else {
2489 args->fsbno = XFS_AGB_TO_FSB(mp, args->agno, args->agbno);
2490#ifdef DEBUG
2491 ASSERT(args->len >= args->minlen);
2492 ASSERT(args->len <= args->maxlen);
2493 ASSERT(args->agbno % args->alignment == 0);
2494 XFS_AG_CHECK_DADDR(mp, XFS_FSB_TO_DADDR(mp, args->fsbno),
2495 args->len);
2496#endif
2497 }
Dave Chinnera862e0f2010-01-11 11:47:41 +00002498 xfs_perag_put(args->pag);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002499 return 0;
2500error0:
Dave Chinnera862e0f2010-01-11 11:47:41 +00002501 xfs_perag_put(args->pag);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002502 return error;
2503}
2504
2505/*
2506 * Free an extent.
2507 * Just break up the extent address and hand off to xfs_free_ag_extent
2508 * after fixing up the freelist.
2509 */
2510int /* error */
2511xfs_free_extent(
2512 xfs_trans_t *tp, /* transaction pointer */
2513 xfs_fsblock_t bno, /* starting block number of extent */
2514 xfs_extlen_t len) /* length of extent */
2515{
Nathan Scott0e1edbd2006-08-10 14:40:41 +10002516 xfs_alloc_arg_t args;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002517 int error;
2518
2519 ASSERT(len != 0);
Nathan Scott0e1edbd2006-08-10 14:40:41 +10002520 memset(&args, 0, sizeof(xfs_alloc_arg_t));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002521 args.tp = tp;
2522 args.mp = tp->t_mountp;
Dave Chinnerbe65b182011-04-08 12:45:07 +10002523
2524 /*
2525 * validate that the block number is legal - the enables us to detect
2526 * and handle a silent filesystem corruption rather than crashing.
2527 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07002528 args.agno = XFS_FSB_TO_AGNO(args.mp, bno);
Dave Chinnerbe65b182011-04-08 12:45:07 +10002529 if (args.agno >= args.mp->m_sb.sb_agcount)
2530 return EFSCORRUPTED;
2531
Linus Torvalds1da177e2005-04-16 15:20:36 -07002532 args.agbno = XFS_FSB_TO_AGBNO(args.mp, bno);
Dave Chinnerbe65b182011-04-08 12:45:07 +10002533 if (args.agbno >= args.mp->m_sb.sb_agblocks)
2534 return EFSCORRUPTED;
2535
Dave Chinnera862e0f2010-01-11 11:47:41 +00002536 args.pag = xfs_perag_get(args.mp, args.agno);
Dave Chinnerbe65b182011-04-08 12:45:07 +10002537 ASSERT(args.pag);
2538
2539 error = xfs_alloc_fix_freelist(&args, XFS_ALLOC_FLAG_FREEING);
2540 if (error)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002541 goto error0;
Dave Chinnerbe65b182011-04-08 12:45:07 +10002542
2543 /* validate the extent size is legal now we have the agf locked */
2544 if (args.agbno + len >
2545 be32_to_cpu(XFS_BUF_TO_AGF(args.agbp)->agf_length)) {
2546 error = EFSCORRUPTED;
2547 goto error0;
2548 }
2549
Nathan Scott0e1edbd2006-08-10 14:40:41 +10002550 error = xfs_free_ag_extent(tp, args.agbp, args.agno, args.agbno, len, 0);
Christoph Hellwiga870acd2011-04-24 19:06:14 +00002551 if (!error)
Dave Chinner4ecbfe62012-04-29 10:41:10 +00002552 xfs_extent_busy_insert(tp, args.agno, args.agbno, len, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002553error0:
Dave Chinnera862e0f2010-01-11 11:47:41 +00002554 xfs_perag_put(args.pag);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002555 return error;
2556}