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