Loading...
1// SPDX-License-Identifier: GPL-2.0
2/*
3 * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc.
4 * All Rights Reserved.
5 */
6#include "xfs.h"
7#include "xfs_fs.h"
8#include "xfs_format.h"
9#include "xfs_log_format.h"
10#include "xfs_shared.h"
11#include "xfs_trans_resv.h"
12#include "xfs_bit.h"
13#include "xfs_mount.h"
14#include "xfs_defer.h"
15#include "xfs_btree.h"
16#include "xfs_rmap.h"
17#include "xfs_alloc_btree.h"
18#include "xfs_alloc.h"
19#include "xfs_extent_busy.h"
20#include "xfs_errortag.h"
21#include "xfs_error.h"
22#include "xfs_trace.h"
23#include "xfs_trans.h"
24#include "xfs_buf_item.h"
25#include "xfs_log.h"
26#include "xfs_ag.h"
27#include "xfs_ag_resv.h"
28#include "xfs_bmap.h"
29
30struct kmem_cache *xfs_extfree_item_cache;
31
32struct workqueue_struct *xfs_alloc_wq;
33
34#define XFS_ABSDIFF(a,b) (((a) <= (b)) ? ((b) - (a)) : ((a) - (b)))
35
36#define XFSA_FIXUP_BNO_OK 1
37#define XFSA_FIXUP_CNT_OK 2
38
39/*
40 * Size of the AGFL. For CRC-enabled filesystes we steal a couple of slots in
41 * the beginning of the block for a proper header with the location information
42 * and CRC.
43 */
44unsigned int
45xfs_agfl_size(
46 struct xfs_mount *mp)
47{
48 unsigned int size = mp->m_sb.sb_sectsize;
49
50 if (xfs_has_crc(mp))
51 size -= sizeof(struct xfs_agfl);
52
53 return size / sizeof(xfs_agblock_t);
54}
55
56unsigned int
57xfs_refc_block(
58 struct xfs_mount *mp)
59{
60 if (xfs_has_rmapbt(mp))
61 return XFS_RMAP_BLOCK(mp) + 1;
62 if (xfs_has_finobt(mp))
63 return XFS_FIBT_BLOCK(mp) + 1;
64 return XFS_IBT_BLOCK(mp) + 1;
65}
66
67xfs_extlen_t
68xfs_prealloc_blocks(
69 struct xfs_mount *mp)
70{
71 if (xfs_has_reflink(mp))
72 return xfs_refc_block(mp) + 1;
73 if (xfs_has_rmapbt(mp))
74 return XFS_RMAP_BLOCK(mp) + 1;
75 if (xfs_has_finobt(mp))
76 return XFS_FIBT_BLOCK(mp) + 1;
77 return XFS_IBT_BLOCK(mp) + 1;
78}
79
80/*
81 * The number of blocks per AG that we withhold from xfs_mod_fdblocks to
82 * guarantee that we can refill the AGFL prior to allocating space in a nearly
83 * full AG. Although the space described by the free space btrees, the
84 * blocks used by the freesp btrees themselves, and the blocks owned by the
85 * AGFL are counted in the ondisk fdblocks, it's a mistake to let the ondisk
86 * free space in the AG drop so low that the free space btrees cannot refill an
87 * empty AGFL up to the minimum level. Rather than grind through empty AGs
88 * until the fs goes down, we subtract this many AG blocks from the incore
89 * fdblocks to ensure user allocation does not overcommit the space the
90 * filesystem needs for the AGFLs. The rmap btree uses a per-AG reservation to
91 * withhold space from xfs_mod_fdblocks, so we do not account for that here.
92 */
93#define XFS_ALLOCBT_AGFL_RESERVE 4
94
95/*
96 * Compute the number of blocks that we set aside to guarantee the ability to
97 * refill the AGFL and handle a full bmap btree split.
98 *
99 * In order to avoid ENOSPC-related deadlock caused by out-of-order locking of
100 * AGF buffer (PV 947395), we place constraints on the relationship among
101 * actual allocations for data blocks, freelist blocks, and potential file data
102 * bmap btree blocks. However, these restrictions may result in no actual space
103 * allocated for a delayed extent, for example, a data block in a certain AG is
104 * allocated but there is no additional block for the additional bmap btree
105 * block due to a split of the bmap btree of the file. The result of this may
106 * lead to an infinite loop when the file gets flushed to disk and all delayed
107 * extents need to be actually allocated. To get around this, we explicitly set
108 * aside a few blocks which will not be reserved in delayed allocation.
109 *
110 * For each AG, we need to reserve enough blocks to replenish a totally empty
111 * AGFL and 4 more to handle a potential split of the file's bmap btree.
112 */
113unsigned int
114xfs_alloc_set_aside(
115 struct xfs_mount *mp)
116{
117 return mp->m_sb.sb_agcount * (XFS_ALLOCBT_AGFL_RESERVE + 4);
118}
119
120/*
121 * When deciding how much space to allocate out of an AG, we limit the
122 * allocation maximum size to the size the AG. However, we cannot use all the
123 * blocks in the AG - some are permanently used by metadata. These
124 * blocks are generally:
125 * - the AG superblock, AGF, AGI and AGFL
126 * - the AGF (bno and cnt) and AGI btree root blocks, and optionally
127 * the AGI free inode and rmap btree root blocks.
128 * - blocks on the AGFL according to xfs_alloc_set_aside() limits
129 * - the rmapbt root block
130 *
131 * The AG headers are sector sized, so the amount of space they take up is
132 * dependent on filesystem geometry. The others are all single blocks.
133 */
134unsigned int
135xfs_alloc_ag_max_usable(
136 struct xfs_mount *mp)
137{
138 unsigned int blocks;
139
140 blocks = XFS_BB_TO_FSB(mp, XFS_FSS_TO_BB(mp, 4)); /* ag headers */
141 blocks += XFS_ALLOCBT_AGFL_RESERVE;
142 blocks += 3; /* AGF, AGI btree root blocks */
143 if (xfs_has_finobt(mp))
144 blocks++; /* finobt root block */
145 if (xfs_has_rmapbt(mp))
146 blocks++; /* rmap root block */
147 if (xfs_has_reflink(mp))
148 blocks++; /* refcount root block */
149
150 return mp->m_sb.sb_agblocks - blocks;
151}
152
153/*
154 * Lookup the record equal to [bno, len] in the btree given by cur.
155 */
156STATIC int /* error */
157xfs_alloc_lookup_eq(
158 struct xfs_btree_cur *cur, /* btree cursor */
159 xfs_agblock_t bno, /* starting block of extent */
160 xfs_extlen_t len, /* length of extent */
161 int *stat) /* success/failure */
162{
163 int error;
164
165 cur->bc_rec.a.ar_startblock = bno;
166 cur->bc_rec.a.ar_blockcount = len;
167 error = xfs_btree_lookup(cur, XFS_LOOKUP_EQ, stat);
168 cur->bc_ag.abt.active = (*stat == 1);
169 return error;
170}
171
172/*
173 * Lookup the first record greater than or equal to [bno, len]
174 * in the btree given by cur.
175 */
176int /* error */
177xfs_alloc_lookup_ge(
178 struct xfs_btree_cur *cur, /* btree cursor */
179 xfs_agblock_t bno, /* starting block of extent */
180 xfs_extlen_t len, /* length of extent */
181 int *stat) /* success/failure */
182{
183 int error;
184
185 cur->bc_rec.a.ar_startblock = bno;
186 cur->bc_rec.a.ar_blockcount = len;
187 error = xfs_btree_lookup(cur, XFS_LOOKUP_GE, stat);
188 cur->bc_ag.abt.active = (*stat == 1);
189 return error;
190}
191
192/*
193 * Lookup the first record less than or equal to [bno, len]
194 * in the btree given by cur.
195 */
196int /* error */
197xfs_alloc_lookup_le(
198 struct xfs_btree_cur *cur, /* btree cursor */
199 xfs_agblock_t bno, /* starting block of extent */
200 xfs_extlen_t len, /* length of extent */
201 int *stat) /* success/failure */
202{
203 int error;
204 cur->bc_rec.a.ar_startblock = bno;
205 cur->bc_rec.a.ar_blockcount = len;
206 error = xfs_btree_lookup(cur, XFS_LOOKUP_LE, stat);
207 cur->bc_ag.abt.active = (*stat == 1);
208 return error;
209}
210
211static inline bool
212xfs_alloc_cur_active(
213 struct xfs_btree_cur *cur)
214{
215 return cur && cur->bc_ag.abt.active;
216}
217
218/*
219 * Update the record referred to by cur to the value given
220 * by [bno, len].
221 * This either works (return 0) or gets an EFSCORRUPTED error.
222 */
223STATIC int /* error */
224xfs_alloc_update(
225 struct xfs_btree_cur *cur, /* btree cursor */
226 xfs_agblock_t bno, /* starting block of extent */
227 xfs_extlen_t len) /* length of extent */
228{
229 union xfs_btree_rec rec;
230
231 rec.alloc.ar_startblock = cpu_to_be32(bno);
232 rec.alloc.ar_blockcount = cpu_to_be32(len);
233 return xfs_btree_update(cur, &rec);
234}
235
236/* Convert the ondisk btree record to its incore representation. */
237void
238xfs_alloc_btrec_to_irec(
239 const union xfs_btree_rec *rec,
240 struct xfs_alloc_rec_incore *irec)
241{
242 irec->ar_startblock = be32_to_cpu(rec->alloc.ar_startblock);
243 irec->ar_blockcount = be32_to_cpu(rec->alloc.ar_blockcount);
244}
245
246/* Simple checks for free space records. */
247xfs_failaddr_t
248xfs_alloc_check_irec(
249 struct xfs_perag *pag,
250 const struct xfs_alloc_rec_incore *irec)
251{
252 if (irec->ar_blockcount == 0)
253 return __this_address;
254
255 /* check for valid extent range, including overflow */
256 if (!xfs_verify_agbext(pag, irec->ar_startblock, irec->ar_blockcount))
257 return __this_address;
258
259 return NULL;
260}
261
262static inline int
263xfs_alloc_complain_bad_rec(
264 struct xfs_btree_cur *cur,
265 xfs_failaddr_t fa,
266 const struct xfs_alloc_rec_incore *irec)
267{
268 struct xfs_mount *mp = cur->bc_mp;
269
270 xfs_warn(mp,
271 "%s Freespace BTree record corruption in AG %d detected at %pS!",
272 cur->bc_btnum == XFS_BTNUM_BNO ? "Block" : "Size",
273 cur->bc_ag.pag->pag_agno, fa);
274 xfs_warn(mp,
275 "start block 0x%x block count 0x%x", irec->ar_startblock,
276 irec->ar_blockcount);
277 return -EFSCORRUPTED;
278}
279
280/*
281 * Get the data from the pointed-to record.
282 */
283int /* error */
284xfs_alloc_get_rec(
285 struct xfs_btree_cur *cur, /* btree cursor */
286 xfs_agblock_t *bno, /* output: starting block of extent */
287 xfs_extlen_t *len, /* output: length of extent */
288 int *stat) /* output: success/failure */
289{
290 struct xfs_alloc_rec_incore irec;
291 union xfs_btree_rec *rec;
292 xfs_failaddr_t fa;
293 int error;
294
295 error = xfs_btree_get_rec(cur, &rec, stat);
296 if (error || !(*stat))
297 return error;
298
299 xfs_alloc_btrec_to_irec(rec, &irec);
300 fa = xfs_alloc_check_irec(cur->bc_ag.pag, &irec);
301 if (fa)
302 return xfs_alloc_complain_bad_rec(cur, fa, &irec);
303
304 *bno = irec.ar_startblock;
305 *len = irec.ar_blockcount;
306 return 0;
307}
308
309/*
310 * Compute aligned version of the found extent.
311 * Takes alignment and min length into account.
312 */
313STATIC bool
314xfs_alloc_compute_aligned(
315 xfs_alloc_arg_t *args, /* allocation argument structure */
316 xfs_agblock_t foundbno, /* starting block in found extent */
317 xfs_extlen_t foundlen, /* length in found extent */
318 xfs_agblock_t *resbno, /* result block number */
319 xfs_extlen_t *reslen, /* result length */
320 unsigned *busy_gen)
321{
322 xfs_agblock_t bno = foundbno;
323 xfs_extlen_t len = foundlen;
324 xfs_extlen_t diff;
325 bool busy;
326
327 /* Trim busy sections out of found extent */
328 busy = xfs_extent_busy_trim(args, &bno, &len, busy_gen);
329
330 /*
331 * If we have a largish extent that happens to start before min_agbno,
332 * see if we can shift it into range...
333 */
334 if (bno < args->min_agbno && bno + len > args->min_agbno) {
335 diff = args->min_agbno - bno;
336 if (len > diff) {
337 bno += diff;
338 len -= diff;
339 }
340 }
341
342 if (args->alignment > 1 && len >= args->minlen) {
343 xfs_agblock_t aligned_bno = roundup(bno, args->alignment);
344
345 diff = aligned_bno - bno;
346
347 *resbno = aligned_bno;
348 *reslen = diff >= len ? 0 : len - diff;
349 } else {
350 *resbno = bno;
351 *reslen = len;
352 }
353
354 return busy;
355}
356
357/*
358 * Compute best start block and diff for "near" allocations.
359 * freelen >= wantlen already checked by caller.
360 */
361STATIC xfs_extlen_t /* difference value (absolute) */
362xfs_alloc_compute_diff(
363 xfs_agblock_t wantbno, /* target starting block */
364 xfs_extlen_t wantlen, /* target length */
365 xfs_extlen_t alignment, /* target alignment */
366 int datatype, /* are we allocating data? */
367 xfs_agblock_t freebno, /* freespace's starting block */
368 xfs_extlen_t freelen, /* freespace's length */
369 xfs_agblock_t *newbnop) /* result: best start block from free */
370{
371 xfs_agblock_t freeend; /* end of freespace extent */
372 xfs_agblock_t newbno1; /* return block number */
373 xfs_agblock_t newbno2; /* other new block number */
374 xfs_extlen_t newlen1=0; /* length with newbno1 */
375 xfs_extlen_t newlen2=0; /* length with newbno2 */
376 xfs_agblock_t wantend; /* end of target extent */
377 bool userdata = datatype & XFS_ALLOC_USERDATA;
378
379 ASSERT(freelen >= wantlen);
380 freeend = freebno + freelen;
381 wantend = wantbno + wantlen;
382 /*
383 * We want to allocate from the start of a free extent if it is past
384 * the desired block or if we are allocating user data and the free
385 * extent is before desired block. The second case is there to allow
386 * for contiguous allocation from the remaining free space if the file
387 * grows in the short term.
388 */
389 if (freebno >= wantbno || (userdata && freeend < wantend)) {
390 if ((newbno1 = roundup(freebno, alignment)) >= freeend)
391 newbno1 = NULLAGBLOCK;
392 } else if (freeend >= wantend && alignment > 1) {
393 newbno1 = roundup(wantbno, alignment);
394 newbno2 = newbno1 - alignment;
395 if (newbno1 >= freeend)
396 newbno1 = NULLAGBLOCK;
397 else
398 newlen1 = XFS_EXTLEN_MIN(wantlen, freeend - newbno1);
399 if (newbno2 < freebno)
400 newbno2 = NULLAGBLOCK;
401 else
402 newlen2 = XFS_EXTLEN_MIN(wantlen, freeend - newbno2);
403 if (newbno1 != NULLAGBLOCK && newbno2 != NULLAGBLOCK) {
404 if (newlen1 < newlen2 ||
405 (newlen1 == newlen2 &&
406 XFS_ABSDIFF(newbno1, wantbno) >
407 XFS_ABSDIFF(newbno2, wantbno)))
408 newbno1 = newbno2;
409 } else if (newbno2 != NULLAGBLOCK)
410 newbno1 = newbno2;
411 } else if (freeend >= wantend) {
412 newbno1 = wantbno;
413 } else if (alignment > 1) {
414 newbno1 = roundup(freeend - wantlen, alignment);
415 if (newbno1 > freeend - wantlen &&
416 newbno1 - alignment >= freebno)
417 newbno1 -= alignment;
418 else if (newbno1 >= freeend)
419 newbno1 = NULLAGBLOCK;
420 } else
421 newbno1 = freeend - wantlen;
422 *newbnop = newbno1;
423 return newbno1 == NULLAGBLOCK ? 0 : XFS_ABSDIFF(newbno1, wantbno);
424}
425
426/*
427 * Fix up the length, based on mod and prod.
428 * len should be k * prod + mod for some k.
429 * If len is too small it is returned unchanged.
430 * If len hits maxlen it is left alone.
431 */
432STATIC void
433xfs_alloc_fix_len(
434 xfs_alloc_arg_t *args) /* allocation argument structure */
435{
436 xfs_extlen_t k;
437 xfs_extlen_t rlen;
438
439 ASSERT(args->mod < args->prod);
440 rlen = args->len;
441 ASSERT(rlen >= args->minlen);
442 ASSERT(rlen <= args->maxlen);
443 if (args->prod <= 1 || rlen < args->mod || rlen == args->maxlen ||
444 (args->mod == 0 && rlen < args->prod))
445 return;
446 k = rlen % args->prod;
447 if (k == args->mod)
448 return;
449 if (k > args->mod)
450 rlen = rlen - (k - args->mod);
451 else
452 rlen = rlen - args->prod + (args->mod - k);
453 /* casts to (int) catch length underflows */
454 if ((int)rlen < (int)args->minlen)
455 return;
456 ASSERT(rlen >= args->minlen && rlen <= args->maxlen);
457 ASSERT(rlen % args->prod == args->mod);
458 ASSERT(args->pag->pagf_freeblks + args->pag->pagf_flcount >=
459 rlen + args->minleft);
460 args->len = rlen;
461}
462
463/*
464 * Update the two btrees, logically removing from freespace the extent
465 * starting at rbno, rlen blocks. The extent is contained within the
466 * actual (current) free extent fbno for flen blocks.
467 * Flags are passed in indicating whether the cursors are set to the
468 * relevant records.
469 */
470STATIC int /* error code */
471xfs_alloc_fixup_trees(
472 struct xfs_btree_cur *cnt_cur, /* cursor for by-size btree */
473 struct xfs_btree_cur *bno_cur, /* cursor for by-block btree */
474 xfs_agblock_t fbno, /* starting block of free extent */
475 xfs_extlen_t flen, /* length of free extent */
476 xfs_agblock_t rbno, /* starting block of returned extent */
477 xfs_extlen_t rlen, /* length of returned extent */
478 int flags) /* flags, XFSA_FIXUP_... */
479{
480 int error; /* error code */
481 int i; /* operation results */
482 xfs_agblock_t nfbno1; /* first new free startblock */
483 xfs_agblock_t nfbno2; /* second new free startblock */
484 xfs_extlen_t nflen1=0; /* first new free length */
485 xfs_extlen_t nflen2=0; /* second new free length */
486 struct xfs_mount *mp;
487
488 mp = cnt_cur->bc_mp;
489
490 /*
491 * Look up the record in the by-size tree if necessary.
492 */
493 if (flags & XFSA_FIXUP_CNT_OK) {
494#ifdef DEBUG
495 if ((error = xfs_alloc_get_rec(cnt_cur, &nfbno1, &nflen1, &i)))
496 return error;
497 if (XFS_IS_CORRUPT(mp,
498 i != 1 ||
499 nfbno1 != fbno ||
500 nflen1 != flen))
501 return -EFSCORRUPTED;
502#endif
503 } else {
504 if ((error = xfs_alloc_lookup_eq(cnt_cur, fbno, flen, &i)))
505 return error;
506 if (XFS_IS_CORRUPT(mp, i != 1))
507 return -EFSCORRUPTED;
508 }
509 /*
510 * Look up the record in the by-block tree if necessary.
511 */
512 if (flags & XFSA_FIXUP_BNO_OK) {
513#ifdef DEBUG
514 if ((error = xfs_alloc_get_rec(bno_cur, &nfbno1, &nflen1, &i)))
515 return error;
516 if (XFS_IS_CORRUPT(mp,
517 i != 1 ||
518 nfbno1 != fbno ||
519 nflen1 != flen))
520 return -EFSCORRUPTED;
521#endif
522 } else {
523 if ((error = xfs_alloc_lookup_eq(bno_cur, fbno, flen, &i)))
524 return error;
525 if (XFS_IS_CORRUPT(mp, i != 1))
526 return -EFSCORRUPTED;
527 }
528
529#ifdef DEBUG
530 if (bno_cur->bc_nlevels == 1 && cnt_cur->bc_nlevels == 1) {
531 struct xfs_btree_block *bnoblock;
532 struct xfs_btree_block *cntblock;
533
534 bnoblock = XFS_BUF_TO_BLOCK(bno_cur->bc_levels[0].bp);
535 cntblock = XFS_BUF_TO_BLOCK(cnt_cur->bc_levels[0].bp);
536
537 if (XFS_IS_CORRUPT(mp,
538 bnoblock->bb_numrecs !=
539 cntblock->bb_numrecs))
540 return -EFSCORRUPTED;
541 }
542#endif
543
544 /*
545 * Deal with all four cases: the allocated record is contained
546 * within the freespace record, so we can have new freespace
547 * at either (or both) end, or no freespace remaining.
548 */
549 if (rbno == fbno && rlen == flen)
550 nfbno1 = nfbno2 = NULLAGBLOCK;
551 else if (rbno == fbno) {
552 nfbno1 = rbno + rlen;
553 nflen1 = flen - rlen;
554 nfbno2 = NULLAGBLOCK;
555 } else if (rbno + rlen == fbno + flen) {
556 nfbno1 = fbno;
557 nflen1 = flen - rlen;
558 nfbno2 = NULLAGBLOCK;
559 } else {
560 nfbno1 = fbno;
561 nflen1 = rbno - fbno;
562 nfbno2 = rbno + rlen;
563 nflen2 = (fbno + flen) - nfbno2;
564 }
565 /*
566 * Delete the entry from the by-size btree.
567 */
568 if ((error = xfs_btree_delete(cnt_cur, &i)))
569 return error;
570 if (XFS_IS_CORRUPT(mp, i != 1))
571 return -EFSCORRUPTED;
572 /*
573 * Add new by-size btree entry(s).
574 */
575 if (nfbno1 != NULLAGBLOCK) {
576 if ((error = xfs_alloc_lookup_eq(cnt_cur, nfbno1, nflen1, &i)))
577 return error;
578 if (XFS_IS_CORRUPT(mp, i != 0))
579 return -EFSCORRUPTED;
580 if ((error = xfs_btree_insert(cnt_cur, &i)))
581 return error;
582 if (XFS_IS_CORRUPT(mp, i != 1))
583 return -EFSCORRUPTED;
584 }
585 if (nfbno2 != NULLAGBLOCK) {
586 if ((error = xfs_alloc_lookup_eq(cnt_cur, nfbno2, nflen2, &i)))
587 return error;
588 if (XFS_IS_CORRUPT(mp, i != 0))
589 return -EFSCORRUPTED;
590 if ((error = xfs_btree_insert(cnt_cur, &i)))
591 return error;
592 if (XFS_IS_CORRUPT(mp, i != 1))
593 return -EFSCORRUPTED;
594 }
595 /*
596 * Fix up the by-block btree entry(s).
597 */
598 if (nfbno1 == NULLAGBLOCK) {
599 /*
600 * No remaining freespace, just delete the by-block tree entry.
601 */
602 if ((error = xfs_btree_delete(bno_cur, &i)))
603 return error;
604 if (XFS_IS_CORRUPT(mp, i != 1))
605 return -EFSCORRUPTED;
606 } else {
607 /*
608 * Update the by-block entry to start later|be shorter.
609 */
610 if ((error = xfs_alloc_update(bno_cur, nfbno1, nflen1)))
611 return error;
612 }
613 if (nfbno2 != NULLAGBLOCK) {
614 /*
615 * 2 resulting free entries, need to add one.
616 */
617 if ((error = xfs_alloc_lookup_eq(bno_cur, nfbno2, nflen2, &i)))
618 return error;
619 if (XFS_IS_CORRUPT(mp, i != 0))
620 return -EFSCORRUPTED;
621 if ((error = xfs_btree_insert(bno_cur, &i)))
622 return error;
623 if (XFS_IS_CORRUPT(mp, i != 1))
624 return -EFSCORRUPTED;
625 }
626 return 0;
627}
628
629/*
630 * We do not verify the AGFL contents against AGF-based index counters here,
631 * even though we may have access to the perag that contains shadow copies. We
632 * don't know if the AGF based counters have been checked, and if they have they
633 * still may be inconsistent because they haven't yet been reset on the first
634 * allocation after the AGF has been read in.
635 *
636 * This means we can only check that all agfl entries contain valid or null
637 * values because we can't reliably determine the active range to exclude
638 * NULLAGBNO as a valid value.
639 *
640 * However, we can't even do that for v4 format filesystems because there are
641 * old versions of mkfs out there that does not initialise the AGFL to known,
642 * verifiable values. HEnce we can't tell the difference between a AGFL block
643 * allocated by mkfs and a corrupted AGFL block here on v4 filesystems.
644 *
645 * As a result, we can only fully validate AGFL block numbers when we pull them
646 * from the freelist in xfs_alloc_get_freelist().
647 */
648static xfs_failaddr_t
649xfs_agfl_verify(
650 struct xfs_buf *bp)
651{
652 struct xfs_mount *mp = bp->b_mount;
653 struct xfs_agfl *agfl = XFS_BUF_TO_AGFL(bp);
654 __be32 *agfl_bno = xfs_buf_to_agfl_bno(bp);
655 int i;
656
657 if (!xfs_has_crc(mp))
658 return NULL;
659
660 if (!xfs_verify_magic(bp, agfl->agfl_magicnum))
661 return __this_address;
662 if (!uuid_equal(&agfl->agfl_uuid, &mp->m_sb.sb_meta_uuid))
663 return __this_address;
664 /*
665 * during growfs operations, the perag is not fully initialised,
666 * so we can't use it for any useful checking. growfs ensures we can't
667 * use it by using uncached buffers that don't have the perag attached
668 * so we can detect and avoid this problem.
669 */
670 if (bp->b_pag && be32_to_cpu(agfl->agfl_seqno) != bp->b_pag->pag_agno)
671 return __this_address;
672
673 for (i = 0; i < xfs_agfl_size(mp); i++) {
674 if (be32_to_cpu(agfl_bno[i]) != NULLAGBLOCK &&
675 be32_to_cpu(agfl_bno[i]) >= mp->m_sb.sb_agblocks)
676 return __this_address;
677 }
678
679 if (!xfs_log_check_lsn(mp, be64_to_cpu(XFS_BUF_TO_AGFL(bp)->agfl_lsn)))
680 return __this_address;
681 return NULL;
682}
683
684static void
685xfs_agfl_read_verify(
686 struct xfs_buf *bp)
687{
688 struct xfs_mount *mp = bp->b_mount;
689 xfs_failaddr_t fa;
690
691 /*
692 * There is no verification of non-crc AGFLs because mkfs does not
693 * initialise the AGFL to zero or NULL. Hence the only valid part of the
694 * AGFL is what the AGF says is active. We can't get to the AGF, so we
695 * can't verify just those entries are valid.
696 */
697 if (!xfs_has_crc(mp))
698 return;
699
700 if (!xfs_buf_verify_cksum(bp, XFS_AGFL_CRC_OFF))
701 xfs_verifier_error(bp, -EFSBADCRC, __this_address);
702 else {
703 fa = xfs_agfl_verify(bp);
704 if (fa)
705 xfs_verifier_error(bp, -EFSCORRUPTED, fa);
706 }
707}
708
709static void
710xfs_agfl_write_verify(
711 struct xfs_buf *bp)
712{
713 struct xfs_mount *mp = bp->b_mount;
714 struct xfs_buf_log_item *bip = bp->b_log_item;
715 xfs_failaddr_t fa;
716
717 /* no verification of non-crc AGFLs */
718 if (!xfs_has_crc(mp))
719 return;
720
721 fa = xfs_agfl_verify(bp);
722 if (fa) {
723 xfs_verifier_error(bp, -EFSCORRUPTED, fa);
724 return;
725 }
726
727 if (bip)
728 XFS_BUF_TO_AGFL(bp)->agfl_lsn = cpu_to_be64(bip->bli_item.li_lsn);
729
730 xfs_buf_update_cksum(bp, XFS_AGFL_CRC_OFF);
731}
732
733const struct xfs_buf_ops xfs_agfl_buf_ops = {
734 .name = "xfs_agfl",
735 .magic = { cpu_to_be32(XFS_AGFL_MAGIC), cpu_to_be32(XFS_AGFL_MAGIC) },
736 .verify_read = xfs_agfl_read_verify,
737 .verify_write = xfs_agfl_write_verify,
738 .verify_struct = xfs_agfl_verify,
739};
740
741/*
742 * Read in the allocation group free block array.
743 */
744int
745xfs_alloc_read_agfl(
746 struct xfs_perag *pag,
747 struct xfs_trans *tp,
748 struct xfs_buf **bpp)
749{
750 struct xfs_mount *mp = pag->pag_mount;
751 struct xfs_buf *bp;
752 int error;
753
754 error = xfs_trans_read_buf(
755 mp, tp, mp->m_ddev_targp,
756 XFS_AG_DADDR(mp, pag->pag_agno, XFS_AGFL_DADDR(mp)),
757 XFS_FSS_TO_BB(mp, 1), 0, &bp, &xfs_agfl_buf_ops);
758 if (error)
759 return error;
760 xfs_buf_set_ref(bp, XFS_AGFL_REF);
761 *bpp = bp;
762 return 0;
763}
764
765STATIC int
766xfs_alloc_update_counters(
767 struct xfs_trans *tp,
768 struct xfs_buf *agbp,
769 long len)
770{
771 struct xfs_agf *agf = agbp->b_addr;
772
773 agbp->b_pag->pagf_freeblks += len;
774 be32_add_cpu(&agf->agf_freeblks, len);
775
776 if (unlikely(be32_to_cpu(agf->agf_freeblks) >
777 be32_to_cpu(agf->agf_length))) {
778 xfs_buf_mark_corrupt(agbp);
779 return -EFSCORRUPTED;
780 }
781
782 xfs_alloc_log_agf(tp, agbp, XFS_AGF_FREEBLKS);
783 return 0;
784}
785
786/*
787 * Block allocation algorithm and data structures.
788 */
789struct xfs_alloc_cur {
790 struct xfs_btree_cur *cnt; /* btree cursors */
791 struct xfs_btree_cur *bnolt;
792 struct xfs_btree_cur *bnogt;
793 xfs_extlen_t cur_len;/* current search length */
794 xfs_agblock_t rec_bno;/* extent startblock */
795 xfs_extlen_t rec_len;/* extent length */
796 xfs_agblock_t bno; /* alloc bno */
797 xfs_extlen_t len; /* alloc len */
798 xfs_extlen_t diff; /* diff from search bno */
799 unsigned int busy_gen;/* busy state */
800 bool busy;
801};
802
803/*
804 * Set up cursors, etc. in the extent allocation cursor. This function can be
805 * called multiple times to reset an initialized structure without having to
806 * reallocate cursors.
807 */
808static int
809xfs_alloc_cur_setup(
810 struct xfs_alloc_arg *args,
811 struct xfs_alloc_cur *acur)
812{
813 int error;
814 int i;
815
816 acur->cur_len = args->maxlen;
817 acur->rec_bno = 0;
818 acur->rec_len = 0;
819 acur->bno = 0;
820 acur->len = 0;
821 acur->diff = -1;
822 acur->busy = false;
823 acur->busy_gen = 0;
824
825 /*
826 * Perform an initial cntbt lookup to check for availability of maxlen
827 * extents. If this fails, we'll return -ENOSPC to signal the caller to
828 * attempt a small allocation.
829 */
830 if (!acur->cnt)
831 acur->cnt = xfs_allocbt_init_cursor(args->mp, args->tp,
832 args->agbp, args->pag, XFS_BTNUM_CNT);
833 error = xfs_alloc_lookup_ge(acur->cnt, 0, args->maxlen, &i);
834 if (error)
835 return error;
836
837 /*
838 * Allocate the bnobt left and right search cursors.
839 */
840 if (!acur->bnolt)
841 acur->bnolt = xfs_allocbt_init_cursor(args->mp, args->tp,
842 args->agbp, args->pag, XFS_BTNUM_BNO);
843 if (!acur->bnogt)
844 acur->bnogt = xfs_allocbt_init_cursor(args->mp, args->tp,
845 args->agbp, args->pag, XFS_BTNUM_BNO);
846 return i == 1 ? 0 : -ENOSPC;
847}
848
849static void
850xfs_alloc_cur_close(
851 struct xfs_alloc_cur *acur,
852 bool error)
853{
854 int cur_error = XFS_BTREE_NOERROR;
855
856 if (error)
857 cur_error = XFS_BTREE_ERROR;
858
859 if (acur->cnt)
860 xfs_btree_del_cursor(acur->cnt, cur_error);
861 if (acur->bnolt)
862 xfs_btree_del_cursor(acur->bnolt, cur_error);
863 if (acur->bnogt)
864 xfs_btree_del_cursor(acur->bnogt, cur_error);
865 acur->cnt = acur->bnolt = acur->bnogt = NULL;
866}
867
868/*
869 * Check an extent for allocation and track the best available candidate in the
870 * allocation structure. The cursor is deactivated if it has entered an out of
871 * range state based on allocation arguments. Optionally return the extent
872 * extent geometry and allocation status if requested by the caller.
873 */
874static int
875xfs_alloc_cur_check(
876 struct xfs_alloc_arg *args,
877 struct xfs_alloc_cur *acur,
878 struct xfs_btree_cur *cur,
879 int *new)
880{
881 int error, i;
882 xfs_agblock_t bno, bnoa, bnew;
883 xfs_extlen_t len, lena, diff = -1;
884 bool busy;
885 unsigned busy_gen = 0;
886 bool deactivate = false;
887 bool isbnobt = cur->bc_btnum == XFS_BTNUM_BNO;
888
889 *new = 0;
890
891 error = xfs_alloc_get_rec(cur, &bno, &len, &i);
892 if (error)
893 return error;
894 if (XFS_IS_CORRUPT(args->mp, i != 1))
895 return -EFSCORRUPTED;
896
897 /*
898 * Check minlen and deactivate a cntbt cursor if out of acceptable size
899 * range (i.e., walking backwards looking for a minlen extent).
900 */
901 if (len < args->minlen) {
902 deactivate = !isbnobt;
903 goto out;
904 }
905
906 busy = xfs_alloc_compute_aligned(args, bno, len, &bnoa, &lena,
907 &busy_gen);
908 acur->busy |= busy;
909 if (busy)
910 acur->busy_gen = busy_gen;
911 /* deactivate a bnobt cursor outside of locality range */
912 if (bnoa < args->min_agbno || bnoa > args->max_agbno) {
913 deactivate = isbnobt;
914 goto out;
915 }
916 if (lena < args->minlen)
917 goto out;
918
919 args->len = XFS_EXTLEN_MIN(lena, args->maxlen);
920 xfs_alloc_fix_len(args);
921 ASSERT(args->len >= args->minlen);
922 if (args->len < acur->len)
923 goto out;
924
925 /*
926 * We have an aligned record that satisfies minlen and beats or matches
927 * the candidate extent size. Compare locality for near allocation mode.
928 */
929 diff = xfs_alloc_compute_diff(args->agbno, args->len,
930 args->alignment, args->datatype,
931 bnoa, lena, &bnew);
932 if (bnew == NULLAGBLOCK)
933 goto out;
934
935 /*
936 * Deactivate a bnobt cursor with worse locality than the current best.
937 */
938 if (diff > acur->diff) {
939 deactivate = isbnobt;
940 goto out;
941 }
942
943 ASSERT(args->len > acur->len ||
944 (args->len == acur->len && diff <= acur->diff));
945 acur->rec_bno = bno;
946 acur->rec_len = len;
947 acur->bno = bnew;
948 acur->len = args->len;
949 acur->diff = diff;
950 *new = 1;
951
952 /*
953 * We're done if we found a perfect allocation. This only deactivates
954 * the current cursor, but this is just an optimization to terminate a
955 * cntbt search that otherwise runs to the edge of the tree.
956 */
957 if (acur->diff == 0 && acur->len == args->maxlen)
958 deactivate = true;
959out:
960 if (deactivate)
961 cur->bc_ag.abt.active = false;
962 trace_xfs_alloc_cur_check(args->mp, cur->bc_btnum, bno, len, diff,
963 *new);
964 return 0;
965}
966
967/*
968 * Complete an allocation of a candidate extent. Remove the extent from both
969 * trees and update the args structure.
970 */
971STATIC int
972xfs_alloc_cur_finish(
973 struct xfs_alloc_arg *args,
974 struct xfs_alloc_cur *acur)
975{
976 struct xfs_agf __maybe_unused *agf = args->agbp->b_addr;
977 int error;
978
979 ASSERT(acur->cnt && acur->bnolt);
980 ASSERT(acur->bno >= acur->rec_bno);
981 ASSERT(acur->bno + acur->len <= acur->rec_bno + acur->rec_len);
982 ASSERT(acur->rec_bno + acur->rec_len <= be32_to_cpu(agf->agf_length));
983
984 error = xfs_alloc_fixup_trees(acur->cnt, acur->bnolt, acur->rec_bno,
985 acur->rec_len, acur->bno, acur->len, 0);
986 if (error)
987 return error;
988
989 args->agbno = acur->bno;
990 args->len = acur->len;
991 args->wasfromfl = 0;
992
993 trace_xfs_alloc_cur(args);
994 return 0;
995}
996
997/*
998 * Locality allocation lookup algorithm. This expects a cntbt cursor and uses
999 * bno optimized lookup to search for extents with ideal size and locality.
1000 */
1001STATIC int
1002xfs_alloc_cntbt_iter(
1003 struct xfs_alloc_arg *args,
1004 struct xfs_alloc_cur *acur)
1005{
1006 struct xfs_btree_cur *cur = acur->cnt;
1007 xfs_agblock_t bno;
1008 xfs_extlen_t len, cur_len;
1009 int error;
1010 int i;
1011
1012 if (!xfs_alloc_cur_active(cur))
1013 return 0;
1014
1015 /* locality optimized lookup */
1016 cur_len = acur->cur_len;
1017 error = xfs_alloc_lookup_ge(cur, args->agbno, cur_len, &i);
1018 if (error)
1019 return error;
1020 if (i == 0)
1021 return 0;
1022 error = xfs_alloc_get_rec(cur, &bno, &len, &i);
1023 if (error)
1024 return error;
1025
1026 /* check the current record and update search length from it */
1027 error = xfs_alloc_cur_check(args, acur, cur, &i);
1028 if (error)
1029 return error;
1030 ASSERT(len >= acur->cur_len);
1031 acur->cur_len = len;
1032
1033 /*
1034 * We looked up the first record >= [agbno, len] above. The agbno is a
1035 * secondary key and so the current record may lie just before or after
1036 * agbno. If it is past agbno, check the previous record too so long as
1037 * the length matches as it may be closer. Don't check a smaller record
1038 * because that could deactivate our cursor.
1039 */
1040 if (bno > args->agbno) {
1041 error = xfs_btree_decrement(cur, 0, &i);
1042 if (!error && i) {
1043 error = xfs_alloc_get_rec(cur, &bno, &len, &i);
1044 if (!error && i && len == acur->cur_len)
1045 error = xfs_alloc_cur_check(args, acur, cur,
1046 &i);
1047 }
1048 if (error)
1049 return error;
1050 }
1051
1052 /*
1053 * Increment the search key until we find at least one allocation
1054 * candidate or if the extent we found was larger. Otherwise, double the
1055 * search key to optimize the search. Efficiency is more important here
1056 * than absolute best locality.
1057 */
1058 cur_len <<= 1;
1059 if (!acur->len || acur->cur_len >= cur_len)
1060 acur->cur_len++;
1061 else
1062 acur->cur_len = cur_len;
1063
1064 return error;
1065}
1066
1067/*
1068 * Deal with the case where only small freespaces remain. Either return the
1069 * contents of the last freespace record, or allocate space from the freelist if
1070 * there is nothing in the tree.
1071 */
1072STATIC int /* error */
1073xfs_alloc_ag_vextent_small(
1074 struct xfs_alloc_arg *args, /* allocation argument structure */
1075 struct xfs_btree_cur *ccur, /* optional by-size cursor */
1076 xfs_agblock_t *fbnop, /* result block number */
1077 xfs_extlen_t *flenp, /* result length */
1078 int *stat) /* status: 0-freelist, 1-normal/none */
1079{
1080 struct xfs_agf *agf = args->agbp->b_addr;
1081 int error = 0;
1082 xfs_agblock_t fbno = NULLAGBLOCK;
1083 xfs_extlen_t flen = 0;
1084 int i = 0;
1085
1086 /*
1087 * If a cntbt cursor is provided, try to allocate the largest record in
1088 * the tree. Try the AGFL if the cntbt is empty, otherwise fail the
1089 * allocation. Make sure to respect minleft even when pulling from the
1090 * freelist.
1091 */
1092 if (ccur)
1093 error = xfs_btree_decrement(ccur, 0, &i);
1094 if (error)
1095 goto error;
1096 if (i) {
1097 error = xfs_alloc_get_rec(ccur, &fbno, &flen, &i);
1098 if (error)
1099 goto error;
1100 if (XFS_IS_CORRUPT(args->mp, i != 1)) {
1101 error = -EFSCORRUPTED;
1102 goto error;
1103 }
1104 goto out;
1105 }
1106
1107 if (args->minlen != 1 || args->alignment != 1 ||
1108 args->resv == XFS_AG_RESV_AGFL ||
1109 be32_to_cpu(agf->agf_flcount) <= args->minleft)
1110 goto out;
1111
1112 error = xfs_alloc_get_freelist(args->pag, args->tp, args->agbp,
1113 &fbno, 0);
1114 if (error)
1115 goto error;
1116 if (fbno == NULLAGBLOCK)
1117 goto out;
1118
1119 xfs_extent_busy_reuse(args->mp, args->pag, fbno, 1,
1120 (args->datatype & XFS_ALLOC_NOBUSY));
1121
1122 if (args->datatype & XFS_ALLOC_USERDATA) {
1123 struct xfs_buf *bp;
1124
1125 error = xfs_trans_get_buf(args->tp, args->mp->m_ddev_targp,
1126 XFS_AGB_TO_DADDR(args->mp, args->agno, fbno),
1127 args->mp->m_bsize, 0, &bp);
1128 if (error)
1129 goto error;
1130 xfs_trans_binval(args->tp, bp);
1131 }
1132 *fbnop = args->agbno = fbno;
1133 *flenp = args->len = 1;
1134 if (XFS_IS_CORRUPT(args->mp, fbno >= be32_to_cpu(agf->agf_length))) {
1135 error = -EFSCORRUPTED;
1136 goto error;
1137 }
1138 args->wasfromfl = 1;
1139 trace_xfs_alloc_small_freelist(args);
1140
1141 /*
1142 * If we're feeding an AGFL block to something that doesn't live in the
1143 * free space, we need to clear out the OWN_AG rmap.
1144 */
1145 error = xfs_rmap_free(args->tp, args->agbp, args->pag, fbno, 1,
1146 &XFS_RMAP_OINFO_AG);
1147 if (error)
1148 goto error;
1149
1150 *stat = 0;
1151 return 0;
1152
1153out:
1154 /*
1155 * Can't do the allocation, give up.
1156 */
1157 if (flen < args->minlen) {
1158 args->agbno = NULLAGBLOCK;
1159 trace_xfs_alloc_small_notenough(args);
1160 flen = 0;
1161 }
1162 *fbnop = fbno;
1163 *flenp = flen;
1164 *stat = 1;
1165 trace_xfs_alloc_small_done(args);
1166 return 0;
1167
1168error:
1169 trace_xfs_alloc_small_error(args);
1170 return error;
1171}
1172
1173/*
1174 * Allocate a variable extent at exactly agno/bno.
1175 * Extent's length (returned in *len) will be between minlen and maxlen,
1176 * and of the form k * prod + mod unless there's nothing that large.
1177 * Return the starting a.g. block (bno), or NULLAGBLOCK if we can't do it.
1178 */
1179STATIC int /* error */
1180xfs_alloc_ag_vextent_exact(
1181 xfs_alloc_arg_t *args) /* allocation argument structure */
1182{
1183 struct xfs_agf __maybe_unused *agf = args->agbp->b_addr;
1184 struct xfs_btree_cur *bno_cur;/* by block-number btree cursor */
1185 struct xfs_btree_cur *cnt_cur;/* by count btree cursor */
1186 int error;
1187 xfs_agblock_t fbno; /* start block of found extent */
1188 xfs_extlen_t flen; /* length of found extent */
1189 xfs_agblock_t tbno; /* start block of busy extent */
1190 xfs_extlen_t tlen; /* length of busy extent */
1191 xfs_agblock_t tend; /* end block of busy extent */
1192 int i; /* success/failure of operation */
1193 unsigned busy_gen;
1194
1195 ASSERT(args->alignment == 1);
1196
1197 /*
1198 * Allocate/initialize a cursor for the by-number freespace btree.
1199 */
1200 bno_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
1201 args->pag, XFS_BTNUM_BNO);
1202
1203 /*
1204 * Lookup bno and minlen in the btree (minlen is irrelevant, really).
1205 * Look for the closest free block <= bno, it must contain bno
1206 * if any free block does.
1207 */
1208 error = xfs_alloc_lookup_le(bno_cur, args->agbno, args->minlen, &i);
1209 if (error)
1210 goto error0;
1211 if (!i)
1212 goto not_found;
1213
1214 /*
1215 * Grab the freespace record.
1216 */
1217 error = xfs_alloc_get_rec(bno_cur, &fbno, &flen, &i);
1218 if (error)
1219 goto error0;
1220 if (XFS_IS_CORRUPT(args->mp, i != 1)) {
1221 error = -EFSCORRUPTED;
1222 goto error0;
1223 }
1224 ASSERT(fbno <= args->agbno);
1225
1226 /*
1227 * Check for overlapping busy extents.
1228 */
1229 tbno = fbno;
1230 tlen = flen;
1231 xfs_extent_busy_trim(args, &tbno, &tlen, &busy_gen);
1232
1233 /*
1234 * Give up if the start of the extent is busy, or the freespace isn't
1235 * long enough for the minimum request.
1236 */
1237 if (tbno > args->agbno)
1238 goto not_found;
1239 if (tlen < args->minlen)
1240 goto not_found;
1241 tend = tbno + tlen;
1242 if (tend < args->agbno + args->minlen)
1243 goto not_found;
1244
1245 /*
1246 * End of extent will be smaller of the freespace end and the
1247 * maximal requested end.
1248 *
1249 * Fix the length according to mod and prod if given.
1250 */
1251 args->len = XFS_AGBLOCK_MIN(tend, args->agbno + args->maxlen)
1252 - args->agbno;
1253 xfs_alloc_fix_len(args);
1254 ASSERT(args->agbno + args->len <= tend);
1255
1256 /*
1257 * We are allocating agbno for args->len
1258 * Allocate/initialize a cursor for the by-size btree.
1259 */
1260 cnt_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
1261 args->pag, XFS_BTNUM_CNT);
1262 ASSERT(args->agbno + args->len <= be32_to_cpu(agf->agf_length));
1263 error = xfs_alloc_fixup_trees(cnt_cur, bno_cur, fbno, flen, args->agbno,
1264 args->len, XFSA_FIXUP_BNO_OK);
1265 if (error) {
1266 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
1267 goto error0;
1268 }
1269
1270 xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
1271 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1272
1273 args->wasfromfl = 0;
1274 trace_xfs_alloc_exact_done(args);
1275 return 0;
1276
1277not_found:
1278 /* Didn't find it, return null. */
1279 xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
1280 args->agbno = NULLAGBLOCK;
1281 trace_xfs_alloc_exact_notfound(args);
1282 return 0;
1283
1284error0:
1285 xfs_btree_del_cursor(bno_cur, XFS_BTREE_ERROR);
1286 trace_xfs_alloc_exact_error(args);
1287 return error;
1288}
1289
1290/*
1291 * Search a given number of btree records in a given direction. Check each
1292 * record against the good extent we've already found.
1293 */
1294STATIC int
1295xfs_alloc_walk_iter(
1296 struct xfs_alloc_arg *args,
1297 struct xfs_alloc_cur *acur,
1298 struct xfs_btree_cur *cur,
1299 bool increment,
1300 bool find_one, /* quit on first candidate */
1301 int count, /* rec count (-1 for infinite) */
1302 int *stat)
1303{
1304 int error;
1305 int i;
1306
1307 *stat = 0;
1308
1309 /*
1310 * Search so long as the cursor is active or we find a better extent.
1311 * The cursor is deactivated if it extends beyond the range of the
1312 * current allocation candidate.
1313 */
1314 while (xfs_alloc_cur_active(cur) && count) {
1315 error = xfs_alloc_cur_check(args, acur, cur, &i);
1316 if (error)
1317 return error;
1318 if (i == 1) {
1319 *stat = 1;
1320 if (find_one)
1321 break;
1322 }
1323 if (!xfs_alloc_cur_active(cur))
1324 break;
1325
1326 if (increment)
1327 error = xfs_btree_increment(cur, 0, &i);
1328 else
1329 error = xfs_btree_decrement(cur, 0, &i);
1330 if (error)
1331 return error;
1332 if (i == 0)
1333 cur->bc_ag.abt.active = false;
1334
1335 if (count > 0)
1336 count--;
1337 }
1338
1339 return 0;
1340}
1341
1342/*
1343 * Search the by-bno and by-size btrees in parallel in search of an extent with
1344 * ideal locality based on the NEAR mode ->agbno locality hint.
1345 */
1346STATIC int
1347xfs_alloc_ag_vextent_locality(
1348 struct xfs_alloc_arg *args,
1349 struct xfs_alloc_cur *acur,
1350 int *stat)
1351{
1352 struct xfs_btree_cur *fbcur = NULL;
1353 int error;
1354 int i;
1355 bool fbinc;
1356
1357 ASSERT(acur->len == 0);
1358
1359 *stat = 0;
1360
1361 error = xfs_alloc_lookup_ge(acur->cnt, args->agbno, acur->cur_len, &i);
1362 if (error)
1363 return error;
1364 error = xfs_alloc_lookup_le(acur->bnolt, args->agbno, 0, &i);
1365 if (error)
1366 return error;
1367 error = xfs_alloc_lookup_ge(acur->bnogt, args->agbno, 0, &i);
1368 if (error)
1369 return error;
1370
1371 /*
1372 * Search the bnobt and cntbt in parallel. Search the bnobt left and
1373 * right and lookup the closest extent to the locality hint for each
1374 * extent size key in the cntbt. The entire search terminates
1375 * immediately on a bnobt hit because that means we've found best case
1376 * locality. Otherwise the search continues until the cntbt cursor runs
1377 * off the end of the tree. If no allocation candidate is found at this
1378 * point, give up on locality, walk backwards from the end of the cntbt
1379 * and take the first available extent.
1380 *
1381 * The parallel tree searches balance each other out to provide fairly
1382 * consistent performance for various situations. The bnobt search can
1383 * have pathological behavior in the worst case scenario of larger
1384 * allocation requests and fragmented free space. On the other hand, the
1385 * bnobt is able to satisfy most smaller allocation requests much more
1386 * quickly than the cntbt. The cntbt search can sift through fragmented
1387 * free space and sets of free extents for larger allocation requests
1388 * more quickly than the bnobt. Since the locality hint is just a hint
1389 * and we don't want to scan the entire bnobt for perfect locality, the
1390 * cntbt search essentially bounds the bnobt search such that we can
1391 * find good enough locality at reasonable performance in most cases.
1392 */
1393 while (xfs_alloc_cur_active(acur->bnolt) ||
1394 xfs_alloc_cur_active(acur->bnogt) ||
1395 xfs_alloc_cur_active(acur->cnt)) {
1396
1397 trace_xfs_alloc_cur_lookup(args);
1398
1399 /*
1400 * Search the bnobt left and right. In the case of a hit, finish
1401 * the search in the opposite direction and we're done.
1402 */
1403 error = xfs_alloc_walk_iter(args, acur, acur->bnolt, false,
1404 true, 1, &i);
1405 if (error)
1406 return error;
1407 if (i == 1) {
1408 trace_xfs_alloc_cur_left(args);
1409 fbcur = acur->bnogt;
1410 fbinc = true;
1411 break;
1412 }
1413 error = xfs_alloc_walk_iter(args, acur, acur->bnogt, true, true,
1414 1, &i);
1415 if (error)
1416 return error;
1417 if (i == 1) {
1418 trace_xfs_alloc_cur_right(args);
1419 fbcur = acur->bnolt;
1420 fbinc = false;
1421 break;
1422 }
1423
1424 /*
1425 * Check the extent with best locality based on the current
1426 * extent size search key and keep track of the best candidate.
1427 */
1428 error = xfs_alloc_cntbt_iter(args, acur);
1429 if (error)
1430 return error;
1431 if (!xfs_alloc_cur_active(acur->cnt)) {
1432 trace_xfs_alloc_cur_lookup_done(args);
1433 break;
1434 }
1435 }
1436
1437 /*
1438 * If we failed to find anything due to busy extents, return empty
1439 * handed so the caller can flush and retry. If no busy extents were
1440 * found, walk backwards from the end of the cntbt as a last resort.
1441 */
1442 if (!xfs_alloc_cur_active(acur->cnt) && !acur->len && !acur->busy) {
1443 error = xfs_btree_decrement(acur->cnt, 0, &i);
1444 if (error)
1445 return error;
1446 if (i) {
1447 acur->cnt->bc_ag.abt.active = true;
1448 fbcur = acur->cnt;
1449 fbinc = false;
1450 }
1451 }
1452
1453 /*
1454 * Search in the opposite direction for a better entry in the case of
1455 * a bnobt hit or walk backwards from the end of the cntbt.
1456 */
1457 if (fbcur) {
1458 error = xfs_alloc_walk_iter(args, acur, fbcur, fbinc, true, -1,
1459 &i);
1460 if (error)
1461 return error;
1462 }
1463
1464 if (acur->len)
1465 *stat = 1;
1466
1467 return 0;
1468}
1469
1470/* Check the last block of the cnt btree for allocations. */
1471static int
1472xfs_alloc_ag_vextent_lastblock(
1473 struct xfs_alloc_arg *args,
1474 struct xfs_alloc_cur *acur,
1475 xfs_agblock_t *bno,
1476 xfs_extlen_t *len,
1477 bool *allocated)
1478{
1479 int error;
1480 int i;
1481
1482#ifdef DEBUG
1483 /* Randomly don't execute the first algorithm. */
1484 if (get_random_u32_below(2))
1485 return 0;
1486#endif
1487
1488 /*
1489 * Start from the entry that lookup found, sequence through all larger
1490 * free blocks. If we're actually pointing at a record smaller than
1491 * maxlen, go to the start of this block, and skip all those smaller
1492 * than minlen.
1493 */
1494 if (*len || args->alignment > 1) {
1495 acur->cnt->bc_levels[0].ptr = 1;
1496 do {
1497 error = xfs_alloc_get_rec(acur->cnt, bno, len, &i);
1498 if (error)
1499 return error;
1500 if (XFS_IS_CORRUPT(args->mp, i != 1))
1501 return -EFSCORRUPTED;
1502 if (*len >= args->minlen)
1503 break;
1504 error = xfs_btree_increment(acur->cnt, 0, &i);
1505 if (error)
1506 return error;
1507 } while (i);
1508 ASSERT(*len >= args->minlen);
1509 if (!i)
1510 return 0;
1511 }
1512
1513 error = xfs_alloc_walk_iter(args, acur, acur->cnt, true, false, -1, &i);
1514 if (error)
1515 return error;
1516
1517 /*
1518 * It didn't work. We COULD be in a case where there's a good record
1519 * somewhere, so try again.
1520 */
1521 if (acur->len == 0)
1522 return 0;
1523
1524 trace_xfs_alloc_near_first(args);
1525 *allocated = true;
1526 return 0;
1527}
1528
1529/*
1530 * Allocate a variable extent near bno in the allocation group agno.
1531 * Extent's length (returned in len) will be between minlen and maxlen,
1532 * and of the form k * prod + mod unless there's nothing that large.
1533 * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
1534 */
1535STATIC int
1536xfs_alloc_ag_vextent_near(
1537 struct xfs_alloc_arg *args,
1538 uint32_t alloc_flags)
1539{
1540 struct xfs_alloc_cur acur = {};
1541 int error; /* error code */
1542 int i; /* result code, temporary */
1543 xfs_agblock_t bno;
1544 xfs_extlen_t len;
1545
1546 /* handle uninitialized agbno range so caller doesn't have to */
1547 if (!args->min_agbno && !args->max_agbno)
1548 args->max_agbno = args->mp->m_sb.sb_agblocks - 1;
1549 ASSERT(args->min_agbno <= args->max_agbno);
1550
1551 /* clamp agbno to the range if it's outside */
1552 if (args->agbno < args->min_agbno)
1553 args->agbno = args->min_agbno;
1554 if (args->agbno > args->max_agbno)
1555 args->agbno = args->max_agbno;
1556
1557 /* Retry once quickly if we find busy extents before blocking. */
1558 alloc_flags |= XFS_ALLOC_FLAG_TRYFLUSH;
1559restart:
1560 len = 0;
1561
1562 /*
1563 * Set up cursors and see if there are any free extents as big as
1564 * maxlen. If not, pick the last entry in the tree unless the tree is
1565 * empty.
1566 */
1567 error = xfs_alloc_cur_setup(args, &acur);
1568 if (error == -ENOSPC) {
1569 error = xfs_alloc_ag_vextent_small(args, acur.cnt, &bno,
1570 &len, &i);
1571 if (error)
1572 goto out;
1573 if (i == 0 || len == 0) {
1574 trace_xfs_alloc_near_noentry(args);
1575 goto out;
1576 }
1577 ASSERT(i == 1);
1578 } else if (error) {
1579 goto out;
1580 }
1581
1582 /*
1583 * First algorithm.
1584 * If the requested extent is large wrt the freespaces available
1585 * in this a.g., then the cursor will be pointing to a btree entry
1586 * near the right edge of the tree. If it's in the last btree leaf
1587 * block, then we just examine all the entries in that block
1588 * that are big enough, and pick the best one.
1589 */
1590 if (xfs_btree_islastblock(acur.cnt, 0)) {
1591 bool allocated = false;
1592
1593 error = xfs_alloc_ag_vextent_lastblock(args, &acur, &bno, &len,
1594 &allocated);
1595 if (error)
1596 goto out;
1597 if (allocated)
1598 goto alloc_finish;
1599 }
1600
1601 /*
1602 * Second algorithm. Combined cntbt and bnobt search to find ideal
1603 * locality.
1604 */
1605 error = xfs_alloc_ag_vextent_locality(args, &acur, &i);
1606 if (error)
1607 goto out;
1608
1609 /*
1610 * If we couldn't get anything, give up.
1611 */
1612 if (!acur.len) {
1613 if (acur.busy) {
1614 /*
1615 * Our only valid extents must have been busy. Flush and
1616 * retry the allocation again. If we get an -EAGAIN
1617 * error, we're being told that a deadlock was avoided
1618 * and the current transaction needs committing before
1619 * the allocation can be retried.
1620 */
1621 trace_xfs_alloc_near_busy(args);
1622 error = xfs_extent_busy_flush(args->tp, args->pag,
1623 acur.busy_gen, alloc_flags);
1624 if (error)
1625 goto out;
1626
1627 alloc_flags &= ~XFS_ALLOC_FLAG_TRYFLUSH;
1628 goto restart;
1629 }
1630 trace_xfs_alloc_size_neither(args);
1631 args->agbno = NULLAGBLOCK;
1632 goto out;
1633 }
1634
1635alloc_finish:
1636 /* fix up btrees on a successful allocation */
1637 error = xfs_alloc_cur_finish(args, &acur);
1638
1639out:
1640 xfs_alloc_cur_close(&acur, error);
1641 return error;
1642}
1643
1644/*
1645 * Allocate a variable extent anywhere in the allocation group agno.
1646 * Extent's length (returned in len) will be between minlen and maxlen,
1647 * and of the form k * prod + mod unless there's nothing that large.
1648 * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
1649 */
1650static int
1651xfs_alloc_ag_vextent_size(
1652 struct xfs_alloc_arg *args,
1653 uint32_t alloc_flags)
1654{
1655 struct xfs_agf *agf = args->agbp->b_addr;
1656 struct xfs_btree_cur *bno_cur;
1657 struct xfs_btree_cur *cnt_cur;
1658 xfs_agblock_t fbno; /* start of found freespace */
1659 xfs_extlen_t flen; /* length of found freespace */
1660 xfs_agblock_t rbno; /* returned block number */
1661 xfs_extlen_t rlen; /* length of returned extent */
1662 bool busy;
1663 unsigned busy_gen;
1664 int error;
1665 int i;
1666
1667 /* Retry once quickly if we find busy extents before blocking. */
1668 alloc_flags |= XFS_ALLOC_FLAG_TRYFLUSH;
1669restart:
1670 /*
1671 * Allocate and initialize a cursor for the by-size btree.
1672 */
1673 cnt_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
1674 args->pag, XFS_BTNUM_CNT);
1675 bno_cur = NULL;
1676
1677 /*
1678 * Look for an entry >= maxlen+alignment-1 blocks.
1679 */
1680 if ((error = xfs_alloc_lookup_ge(cnt_cur, 0,
1681 args->maxlen + args->alignment - 1, &i)))
1682 goto error0;
1683
1684 /*
1685 * If none then we have to settle for a smaller extent. In the case that
1686 * there are no large extents, this will return the last entry in the
1687 * tree unless the tree is empty. In the case that there are only busy
1688 * large extents, this will return the largest small extent unless there
1689 * are no smaller extents available.
1690 */
1691 if (!i) {
1692 error = xfs_alloc_ag_vextent_small(args, cnt_cur,
1693 &fbno, &flen, &i);
1694 if (error)
1695 goto error0;
1696 if (i == 0 || flen == 0) {
1697 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1698 trace_xfs_alloc_size_noentry(args);
1699 return 0;
1700 }
1701 ASSERT(i == 1);
1702 busy = xfs_alloc_compute_aligned(args, fbno, flen, &rbno,
1703 &rlen, &busy_gen);
1704 } else {
1705 /*
1706 * Search for a non-busy extent that is large enough.
1707 */
1708 for (;;) {
1709 error = xfs_alloc_get_rec(cnt_cur, &fbno, &flen, &i);
1710 if (error)
1711 goto error0;
1712 if (XFS_IS_CORRUPT(args->mp, i != 1)) {
1713 error = -EFSCORRUPTED;
1714 goto error0;
1715 }
1716
1717 busy = xfs_alloc_compute_aligned(args, fbno, flen,
1718 &rbno, &rlen, &busy_gen);
1719
1720 if (rlen >= args->maxlen)
1721 break;
1722
1723 error = xfs_btree_increment(cnt_cur, 0, &i);
1724 if (error)
1725 goto error0;
1726 if (i)
1727 continue;
1728
1729 /*
1730 * Our only valid extents must have been busy. Flush and
1731 * retry the allocation again. If we get an -EAGAIN
1732 * error, we're being told that a deadlock was avoided
1733 * and the current transaction needs committing before
1734 * the allocation can be retried.
1735 */
1736 trace_xfs_alloc_size_busy(args);
1737 error = xfs_extent_busy_flush(args->tp, args->pag,
1738 busy_gen, alloc_flags);
1739 if (error)
1740 goto error0;
1741
1742 alloc_flags &= ~XFS_ALLOC_FLAG_TRYFLUSH;
1743 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1744 goto restart;
1745 }
1746 }
1747
1748 /*
1749 * In the first case above, we got the last entry in the
1750 * by-size btree. Now we check to see if the space hits maxlen
1751 * once aligned; if not, we search left for something better.
1752 * This can't happen in the second case above.
1753 */
1754 rlen = XFS_EXTLEN_MIN(args->maxlen, rlen);
1755 if (XFS_IS_CORRUPT(args->mp,
1756 rlen != 0 &&
1757 (rlen > flen ||
1758 rbno + rlen > fbno + flen))) {
1759 error = -EFSCORRUPTED;
1760 goto error0;
1761 }
1762 if (rlen < args->maxlen) {
1763 xfs_agblock_t bestfbno;
1764 xfs_extlen_t bestflen;
1765 xfs_agblock_t bestrbno;
1766 xfs_extlen_t bestrlen;
1767
1768 bestrlen = rlen;
1769 bestrbno = rbno;
1770 bestflen = flen;
1771 bestfbno = fbno;
1772 for (;;) {
1773 if ((error = xfs_btree_decrement(cnt_cur, 0, &i)))
1774 goto error0;
1775 if (i == 0)
1776 break;
1777 if ((error = xfs_alloc_get_rec(cnt_cur, &fbno, &flen,
1778 &i)))
1779 goto error0;
1780 if (XFS_IS_CORRUPT(args->mp, i != 1)) {
1781 error = -EFSCORRUPTED;
1782 goto error0;
1783 }
1784 if (flen < bestrlen)
1785 break;
1786 busy = xfs_alloc_compute_aligned(args, fbno, flen,
1787 &rbno, &rlen, &busy_gen);
1788 rlen = XFS_EXTLEN_MIN(args->maxlen, rlen);
1789 if (XFS_IS_CORRUPT(args->mp,
1790 rlen != 0 &&
1791 (rlen > flen ||
1792 rbno + rlen > fbno + flen))) {
1793 error = -EFSCORRUPTED;
1794 goto error0;
1795 }
1796 if (rlen > bestrlen) {
1797 bestrlen = rlen;
1798 bestrbno = rbno;
1799 bestflen = flen;
1800 bestfbno = fbno;
1801 if (rlen == args->maxlen)
1802 break;
1803 }
1804 }
1805 if ((error = xfs_alloc_lookup_eq(cnt_cur, bestfbno, bestflen,
1806 &i)))
1807 goto error0;
1808 if (XFS_IS_CORRUPT(args->mp, i != 1)) {
1809 error = -EFSCORRUPTED;
1810 goto error0;
1811 }
1812 rlen = bestrlen;
1813 rbno = bestrbno;
1814 flen = bestflen;
1815 fbno = bestfbno;
1816 }
1817 args->wasfromfl = 0;
1818 /*
1819 * Fix up the length.
1820 */
1821 args->len = rlen;
1822 if (rlen < args->minlen) {
1823 if (busy) {
1824 /*
1825 * Our only valid extents must have been busy. Flush and
1826 * retry the allocation again. If we get an -EAGAIN
1827 * error, we're being told that a deadlock was avoided
1828 * and the current transaction needs committing before
1829 * the allocation can be retried.
1830 */
1831 trace_xfs_alloc_size_busy(args);
1832 error = xfs_extent_busy_flush(args->tp, args->pag,
1833 busy_gen, alloc_flags);
1834 if (error)
1835 goto error0;
1836
1837 alloc_flags &= ~XFS_ALLOC_FLAG_TRYFLUSH;
1838 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1839 goto restart;
1840 }
1841 goto out_nominleft;
1842 }
1843 xfs_alloc_fix_len(args);
1844
1845 rlen = args->len;
1846 if (XFS_IS_CORRUPT(args->mp, rlen > flen)) {
1847 error = -EFSCORRUPTED;
1848 goto error0;
1849 }
1850 /*
1851 * Allocate and initialize a cursor for the by-block tree.
1852 */
1853 bno_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
1854 args->pag, XFS_BTNUM_BNO);
1855 if ((error = xfs_alloc_fixup_trees(cnt_cur, bno_cur, fbno, flen,
1856 rbno, rlen, XFSA_FIXUP_CNT_OK)))
1857 goto error0;
1858 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1859 xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
1860 cnt_cur = bno_cur = NULL;
1861 args->len = rlen;
1862 args->agbno = rbno;
1863 if (XFS_IS_CORRUPT(args->mp,
1864 args->agbno + args->len >
1865 be32_to_cpu(agf->agf_length))) {
1866 error = -EFSCORRUPTED;
1867 goto error0;
1868 }
1869 trace_xfs_alloc_size_done(args);
1870 return 0;
1871
1872error0:
1873 trace_xfs_alloc_size_error(args);
1874 if (cnt_cur)
1875 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
1876 if (bno_cur)
1877 xfs_btree_del_cursor(bno_cur, XFS_BTREE_ERROR);
1878 return error;
1879
1880out_nominleft:
1881 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1882 trace_xfs_alloc_size_nominleft(args);
1883 args->agbno = NULLAGBLOCK;
1884 return 0;
1885}
1886
1887/*
1888 * Free the extent starting at agno/bno for length.
1889 */
1890STATIC int
1891xfs_free_ag_extent(
1892 struct xfs_trans *tp,
1893 struct xfs_buf *agbp,
1894 xfs_agnumber_t agno,
1895 xfs_agblock_t bno,
1896 xfs_extlen_t len,
1897 const struct xfs_owner_info *oinfo,
1898 enum xfs_ag_resv_type type)
1899{
1900 struct xfs_mount *mp;
1901 struct xfs_btree_cur *bno_cur;
1902 struct xfs_btree_cur *cnt_cur;
1903 xfs_agblock_t gtbno; /* start of right neighbor */
1904 xfs_extlen_t gtlen; /* length of right neighbor */
1905 xfs_agblock_t ltbno; /* start of left neighbor */
1906 xfs_extlen_t ltlen; /* length of left neighbor */
1907 xfs_agblock_t nbno; /* new starting block of freesp */
1908 xfs_extlen_t nlen; /* new length of freespace */
1909 int haveleft; /* have a left neighbor */
1910 int haveright; /* have a right neighbor */
1911 int i;
1912 int error;
1913 struct xfs_perag *pag = agbp->b_pag;
1914
1915 bno_cur = cnt_cur = NULL;
1916 mp = tp->t_mountp;
1917
1918 if (!xfs_rmap_should_skip_owner_update(oinfo)) {
1919 error = xfs_rmap_free(tp, agbp, pag, bno, len, oinfo);
1920 if (error)
1921 goto error0;
1922 }
1923
1924 /*
1925 * Allocate and initialize a cursor for the by-block btree.
1926 */
1927 bno_cur = xfs_allocbt_init_cursor(mp, tp, agbp, pag, XFS_BTNUM_BNO);
1928 /*
1929 * Look for a neighboring block on the left (lower block numbers)
1930 * that is contiguous with this space.
1931 */
1932 if ((error = xfs_alloc_lookup_le(bno_cur, bno, len, &haveleft)))
1933 goto error0;
1934 if (haveleft) {
1935 /*
1936 * There is a block to our left.
1937 */
1938 if ((error = xfs_alloc_get_rec(bno_cur, <bno, <len, &i)))
1939 goto error0;
1940 if (XFS_IS_CORRUPT(mp, i != 1)) {
1941 error = -EFSCORRUPTED;
1942 goto error0;
1943 }
1944 /*
1945 * It's not contiguous, though.
1946 */
1947 if (ltbno + ltlen < bno)
1948 haveleft = 0;
1949 else {
1950 /*
1951 * If this failure happens the request to free this
1952 * space was invalid, it's (partly) already free.
1953 * Very bad.
1954 */
1955 if (XFS_IS_CORRUPT(mp, ltbno + ltlen > bno)) {
1956 error = -EFSCORRUPTED;
1957 goto error0;
1958 }
1959 }
1960 }
1961 /*
1962 * Look for a neighboring block on the right (higher block numbers)
1963 * that is contiguous with this space.
1964 */
1965 if ((error = xfs_btree_increment(bno_cur, 0, &haveright)))
1966 goto error0;
1967 if (haveright) {
1968 /*
1969 * There is a block to our right.
1970 */
1971 if ((error = xfs_alloc_get_rec(bno_cur, >bno, >len, &i)))
1972 goto error0;
1973 if (XFS_IS_CORRUPT(mp, i != 1)) {
1974 error = -EFSCORRUPTED;
1975 goto error0;
1976 }
1977 /*
1978 * It's not contiguous, though.
1979 */
1980 if (bno + len < gtbno)
1981 haveright = 0;
1982 else {
1983 /*
1984 * If this failure happens the request to free this
1985 * space was invalid, it's (partly) already free.
1986 * Very bad.
1987 */
1988 if (XFS_IS_CORRUPT(mp, bno + len > gtbno)) {
1989 error = -EFSCORRUPTED;
1990 goto error0;
1991 }
1992 }
1993 }
1994 /*
1995 * Now allocate and initialize a cursor for the by-size tree.
1996 */
1997 cnt_cur = xfs_allocbt_init_cursor(mp, tp, agbp, pag, XFS_BTNUM_CNT);
1998 /*
1999 * Have both left and right contiguous neighbors.
2000 * Merge all three into a single free block.
2001 */
2002 if (haveleft && haveright) {
2003 /*
2004 * Delete the old by-size entry on the left.
2005 */
2006 if ((error = xfs_alloc_lookup_eq(cnt_cur, ltbno, ltlen, &i)))
2007 goto error0;
2008 if (XFS_IS_CORRUPT(mp, i != 1)) {
2009 error = -EFSCORRUPTED;
2010 goto error0;
2011 }
2012 if ((error = xfs_btree_delete(cnt_cur, &i)))
2013 goto error0;
2014 if (XFS_IS_CORRUPT(mp, i != 1)) {
2015 error = -EFSCORRUPTED;
2016 goto error0;
2017 }
2018 /*
2019 * Delete the old by-size entry on the right.
2020 */
2021 if ((error = xfs_alloc_lookup_eq(cnt_cur, gtbno, gtlen, &i)))
2022 goto error0;
2023 if (XFS_IS_CORRUPT(mp, i != 1)) {
2024 error = -EFSCORRUPTED;
2025 goto error0;
2026 }
2027 if ((error = xfs_btree_delete(cnt_cur, &i)))
2028 goto error0;
2029 if (XFS_IS_CORRUPT(mp, i != 1)) {
2030 error = -EFSCORRUPTED;
2031 goto error0;
2032 }
2033 /*
2034 * Delete the old by-block entry for the right block.
2035 */
2036 if ((error = xfs_btree_delete(bno_cur, &i)))
2037 goto error0;
2038 if (XFS_IS_CORRUPT(mp, i != 1)) {
2039 error = -EFSCORRUPTED;
2040 goto error0;
2041 }
2042 /*
2043 * Move the by-block cursor back to the left neighbor.
2044 */
2045 if ((error = xfs_btree_decrement(bno_cur, 0, &i)))
2046 goto error0;
2047 if (XFS_IS_CORRUPT(mp, i != 1)) {
2048 error = -EFSCORRUPTED;
2049 goto error0;
2050 }
2051#ifdef DEBUG
2052 /*
2053 * Check that this is the right record: delete didn't
2054 * mangle the cursor.
2055 */
2056 {
2057 xfs_agblock_t xxbno;
2058 xfs_extlen_t xxlen;
2059
2060 if ((error = xfs_alloc_get_rec(bno_cur, &xxbno, &xxlen,
2061 &i)))
2062 goto error0;
2063 if (XFS_IS_CORRUPT(mp,
2064 i != 1 ||
2065 xxbno != ltbno ||
2066 xxlen != ltlen)) {
2067 error = -EFSCORRUPTED;
2068 goto error0;
2069 }
2070 }
2071#endif
2072 /*
2073 * Update remaining by-block entry to the new, joined block.
2074 */
2075 nbno = ltbno;
2076 nlen = len + ltlen + gtlen;
2077 if ((error = xfs_alloc_update(bno_cur, nbno, nlen)))
2078 goto error0;
2079 }
2080 /*
2081 * Have only a left contiguous neighbor.
2082 * Merge it together with the new freespace.
2083 */
2084 else if (haveleft) {
2085 /*
2086 * Delete the old by-size entry on the left.
2087 */
2088 if ((error = xfs_alloc_lookup_eq(cnt_cur, ltbno, ltlen, &i)))
2089 goto error0;
2090 if (XFS_IS_CORRUPT(mp, i != 1)) {
2091 error = -EFSCORRUPTED;
2092 goto error0;
2093 }
2094 if ((error = xfs_btree_delete(cnt_cur, &i)))
2095 goto error0;
2096 if (XFS_IS_CORRUPT(mp, i != 1)) {
2097 error = -EFSCORRUPTED;
2098 goto error0;
2099 }
2100 /*
2101 * Back up the by-block cursor to the left neighbor, and
2102 * update its length.
2103 */
2104 if ((error = xfs_btree_decrement(bno_cur, 0, &i)))
2105 goto error0;
2106 if (XFS_IS_CORRUPT(mp, i != 1)) {
2107 error = -EFSCORRUPTED;
2108 goto error0;
2109 }
2110 nbno = ltbno;
2111 nlen = len + ltlen;
2112 if ((error = xfs_alloc_update(bno_cur, nbno, nlen)))
2113 goto error0;
2114 }
2115 /*
2116 * Have only a right contiguous neighbor.
2117 * Merge it together with the new freespace.
2118 */
2119 else if (haveright) {
2120 /*
2121 * Delete the old by-size entry on the right.
2122 */
2123 if ((error = xfs_alloc_lookup_eq(cnt_cur, gtbno, gtlen, &i)))
2124 goto error0;
2125 if (XFS_IS_CORRUPT(mp, i != 1)) {
2126 error = -EFSCORRUPTED;
2127 goto error0;
2128 }
2129 if ((error = xfs_btree_delete(cnt_cur, &i)))
2130 goto error0;
2131 if (XFS_IS_CORRUPT(mp, i != 1)) {
2132 error = -EFSCORRUPTED;
2133 goto error0;
2134 }
2135 /*
2136 * Update the starting block and length of the right
2137 * neighbor in the by-block tree.
2138 */
2139 nbno = bno;
2140 nlen = len + gtlen;
2141 if ((error = xfs_alloc_update(bno_cur, nbno, nlen)))
2142 goto error0;
2143 }
2144 /*
2145 * No contiguous neighbors.
2146 * Insert the new freespace into the by-block tree.
2147 */
2148 else {
2149 nbno = bno;
2150 nlen = len;
2151 if ((error = xfs_btree_insert(bno_cur, &i)))
2152 goto error0;
2153 if (XFS_IS_CORRUPT(mp, i != 1)) {
2154 error = -EFSCORRUPTED;
2155 goto error0;
2156 }
2157 }
2158 xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
2159 bno_cur = NULL;
2160 /*
2161 * In all cases we need to insert the new freespace in the by-size tree.
2162 */
2163 if ((error = xfs_alloc_lookup_eq(cnt_cur, nbno, nlen, &i)))
2164 goto error0;
2165 if (XFS_IS_CORRUPT(mp, i != 0)) {
2166 error = -EFSCORRUPTED;
2167 goto error0;
2168 }
2169 if ((error = xfs_btree_insert(cnt_cur, &i)))
2170 goto error0;
2171 if (XFS_IS_CORRUPT(mp, i != 1)) {
2172 error = -EFSCORRUPTED;
2173 goto error0;
2174 }
2175 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
2176 cnt_cur = NULL;
2177
2178 /*
2179 * Update the freespace totals in the ag and superblock.
2180 */
2181 error = xfs_alloc_update_counters(tp, agbp, len);
2182 xfs_ag_resv_free_extent(agbp->b_pag, type, tp, len);
2183 if (error)
2184 goto error0;
2185
2186 XFS_STATS_INC(mp, xs_freex);
2187 XFS_STATS_ADD(mp, xs_freeb, len);
2188
2189 trace_xfs_free_extent(mp, agno, bno, len, type, haveleft, haveright);
2190
2191 return 0;
2192
2193 error0:
2194 trace_xfs_free_extent(mp, agno, bno, len, type, -1, -1);
2195 if (bno_cur)
2196 xfs_btree_del_cursor(bno_cur, XFS_BTREE_ERROR);
2197 if (cnt_cur)
2198 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
2199 return error;
2200}
2201
2202/*
2203 * Visible (exported) allocation/free functions.
2204 * Some of these are used just by xfs_alloc_btree.c and this file.
2205 */
2206
2207/*
2208 * Compute and fill in value of m_alloc_maxlevels.
2209 */
2210void
2211xfs_alloc_compute_maxlevels(
2212 xfs_mount_t *mp) /* file system mount structure */
2213{
2214 mp->m_alloc_maxlevels = xfs_btree_compute_maxlevels(mp->m_alloc_mnr,
2215 (mp->m_sb.sb_agblocks + 1) / 2);
2216 ASSERT(mp->m_alloc_maxlevels <= xfs_allocbt_maxlevels_ondisk());
2217}
2218
2219/*
2220 * Find the length of the longest extent in an AG. The 'need' parameter
2221 * specifies how much space we're going to need for the AGFL and the
2222 * 'reserved' parameter tells us how many blocks in this AG are reserved for
2223 * other callers.
2224 */
2225xfs_extlen_t
2226xfs_alloc_longest_free_extent(
2227 struct xfs_perag *pag,
2228 xfs_extlen_t need,
2229 xfs_extlen_t reserved)
2230{
2231 xfs_extlen_t delta = 0;
2232
2233 /*
2234 * If the AGFL needs a recharge, we'll have to subtract that from the
2235 * longest extent.
2236 */
2237 if (need > pag->pagf_flcount)
2238 delta = need - pag->pagf_flcount;
2239
2240 /*
2241 * If we cannot maintain others' reservations with space from the
2242 * not-longest freesp extents, we'll have to subtract /that/ from
2243 * the longest extent too.
2244 */
2245 if (pag->pagf_freeblks - pag->pagf_longest < reserved)
2246 delta += reserved - (pag->pagf_freeblks - pag->pagf_longest);
2247
2248 /*
2249 * If the longest extent is long enough to satisfy all the
2250 * reservations and AGFL rules in place, we can return this extent.
2251 */
2252 if (pag->pagf_longest > delta)
2253 return min_t(xfs_extlen_t, pag->pag_mount->m_ag_max_usable,
2254 pag->pagf_longest - delta);
2255
2256 /* Otherwise, let the caller try for 1 block if there's space. */
2257 return pag->pagf_flcount > 0 || pag->pagf_longest > 0;
2258}
2259
2260/*
2261 * Compute the minimum length of the AGFL in the given AG. If @pag is NULL,
2262 * return the largest possible minimum length.
2263 */
2264unsigned int
2265xfs_alloc_min_freelist(
2266 struct xfs_mount *mp,
2267 struct xfs_perag *pag)
2268{
2269 /* AG btrees have at least 1 level. */
2270 static const uint8_t fake_levels[XFS_BTNUM_AGF] = {1, 1, 1};
2271 const uint8_t *levels = pag ? pag->pagf_levels : fake_levels;
2272 unsigned int min_free;
2273
2274 ASSERT(mp->m_alloc_maxlevels > 0);
2275
2276 /*
2277 * For a btree shorter than the maximum height, the worst case is that
2278 * every level gets split and a new level is added, then while inserting
2279 * another entry to refill the AGFL, every level under the old root gets
2280 * split again. This is:
2281 *
2282 * (full height split reservation) + (AGFL refill split height)
2283 * = (current height + 1) + (current height - 1)
2284 * = (new height) + (new height - 2)
2285 * = 2 * new height - 2
2286 *
2287 * For a btree of maximum height, the worst case is that every level
2288 * under the root gets split, then while inserting another entry to
2289 * refill the AGFL, every level under the root gets split again. This is
2290 * also:
2291 *
2292 * 2 * (current height - 1)
2293 * = 2 * (new height - 1)
2294 * = 2 * new height - 2
2295 */
2296
2297 /* space needed by-bno freespace btree */
2298 min_free = min_t(unsigned int, levels[XFS_BTNUM_BNOi] + 1,
2299 mp->m_alloc_maxlevels) * 2 - 2;
2300 /* space needed by-size freespace btree */
2301 min_free += min_t(unsigned int, levels[XFS_BTNUM_CNTi] + 1,
2302 mp->m_alloc_maxlevels) * 2 - 2;
2303 /* space needed reverse mapping used space btree */
2304 if (xfs_has_rmapbt(mp))
2305 min_free += min_t(unsigned int, levels[XFS_BTNUM_RMAPi] + 1,
2306 mp->m_rmap_maxlevels) * 2 - 2;
2307
2308 return min_free;
2309}
2310
2311/*
2312 * Check if the operation we are fixing up the freelist for should go ahead or
2313 * not. If we are freeing blocks, we always allow it, otherwise the allocation
2314 * is dependent on whether the size and shape of free space available will
2315 * permit the requested allocation to take place.
2316 */
2317static bool
2318xfs_alloc_space_available(
2319 struct xfs_alloc_arg *args,
2320 xfs_extlen_t min_free,
2321 int flags)
2322{
2323 struct xfs_perag *pag = args->pag;
2324 xfs_extlen_t alloc_len, longest;
2325 xfs_extlen_t reservation; /* blocks that are still reserved */
2326 int available;
2327 xfs_extlen_t agflcount;
2328
2329 if (flags & XFS_ALLOC_FLAG_FREEING)
2330 return true;
2331
2332 reservation = xfs_ag_resv_needed(pag, args->resv);
2333
2334 /* do we have enough contiguous free space for the allocation? */
2335 alloc_len = args->minlen + (args->alignment - 1) + args->minalignslop;
2336 longest = xfs_alloc_longest_free_extent(pag, min_free, reservation);
2337 if (longest < alloc_len)
2338 return false;
2339
2340 /*
2341 * Do we have enough free space remaining for the allocation? Don't
2342 * account extra agfl blocks because we are about to defer free them,
2343 * making them unavailable until the current transaction commits.
2344 */
2345 agflcount = min_t(xfs_extlen_t, pag->pagf_flcount, min_free);
2346 available = (int)(pag->pagf_freeblks + agflcount -
2347 reservation - min_free - args->minleft);
2348 if (available < (int)max(args->total, alloc_len))
2349 return false;
2350
2351 /*
2352 * Clamp maxlen to the amount of free space available for the actual
2353 * extent allocation.
2354 */
2355 if (available < (int)args->maxlen && !(flags & XFS_ALLOC_FLAG_CHECK)) {
2356 args->maxlen = available;
2357 ASSERT(args->maxlen > 0);
2358 ASSERT(args->maxlen >= args->minlen);
2359 }
2360
2361 return true;
2362}
2363
2364int
2365xfs_free_agfl_block(
2366 struct xfs_trans *tp,
2367 xfs_agnumber_t agno,
2368 xfs_agblock_t agbno,
2369 struct xfs_buf *agbp,
2370 struct xfs_owner_info *oinfo)
2371{
2372 int error;
2373 struct xfs_buf *bp;
2374
2375 error = xfs_free_ag_extent(tp, agbp, agno, agbno, 1, oinfo,
2376 XFS_AG_RESV_AGFL);
2377 if (error)
2378 return error;
2379
2380 error = xfs_trans_get_buf(tp, tp->t_mountp->m_ddev_targp,
2381 XFS_AGB_TO_DADDR(tp->t_mountp, agno, agbno),
2382 tp->t_mountp->m_bsize, 0, &bp);
2383 if (error)
2384 return error;
2385 xfs_trans_binval(tp, bp);
2386
2387 return 0;
2388}
2389
2390/*
2391 * Check the agfl fields of the agf for inconsistency or corruption.
2392 *
2393 * The original purpose was to detect an agfl header padding mismatch between
2394 * current and early v5 kernels. This problem manifests as a 1-slot size
2395 * difference between the on-disk flcount and the active [first, last] range of
2396 * a wrapped agfl.
2397 *
2398 * However, we need to use these same checks to catch agfl count corruptions
2399 * unrelated to padding. This could occur on any v4 or v5 filesystem, so either
2400 * way, we need to reset the agfl and warn the user.
2401 *
2402 * Return true if a reset is required before the agfl can be used, false
2403 * otherwise.
2404 */
2405static bool
2406xfs_agfl_needs_reset(
2407 struct xfs_mount *mp,
2408 struct xfs_agf *agf)
2409{
2410 uint32_t f = be32_to_cpu(agf->agf_flfirst);
2411 uint32_t l = be32_to_cpu(agf->agf_fllast);
2412 uint32_t c = be32_to_cpu(agf->agf_flcount);
2413 int agfl_size = xfs_agfl_size(mp);
2414 int active;
2415
2416 /*
2417 * The agf read verifier catches severe corruption of these fields.
2418 * Repeat some sanity checks to cover a packed -> unpacked mismatch if
2419 * the verifier allows it.
2420 */
2421 if (f >= agfl_size || l >= agfl_size)
2422 return true;
2423 if (c > agfl_size)
2424 return true;
2425
2426 /*
2427 * Check consistency between the on-disk count and the active range. An
2428 * agfl padding mismatch manifests as an inconsistent flcount.
2429 */
2430 if (c && l >= f)
2431 active = l - f + 1;
2432 else if (c)
2433 active = agfl_size - f + l + 1;
2434 else
2435 active = 0;
2436
2437 return active != c;
2438}
2439
2440/*
2441 * Reset the agfl to an empty state. Ignore/drop any existing blocks since the
2442 * agfl content cannot be trusted. Warn the user that a repair is required to
2443 * recover leaked blocks.
2444 *
2445 * The purpose of this mechanism is to handle filesystems affected by the agfl
2446 * header padding mismatch problem. A reset keeps the filesystem online with a
2447 * relatively minor free space accounting inconsistency rather than suffer the
2448 * inevitable crash from use of an invalid agfl block.
2449 */
2450static void
2451xfs_agfl_reset(
2452 struct xfs_trans *tp,
2453 struct xfs_buf *agbp,
2454 struct xfs_perag *pag)
2455{
2456 struct xfs_mount *mp = tp->t_mountp;
2457 struct xfs_agf *agf = agbp->b_addr;
2458
2459 ASSERT(xfs_perag_agfl_needs_reset(pag));
2460 trace_xfs_agfl_reset(mp, agf, 0, _RET_IP_);
2461
2462 xfs_warn(mp,
2463 "WARNING: Reset corrupted AGFL on AG %u. %d blocks leaked. "
2464 "Please unmount and run xfs_repair.",
2465 pag->pag_agno, pag->pagf_flcount);
2466
2467 agf->agf_flfirst = 0;
2468 agf->agf_fllast = cpu_to_be32(xfs_agfl_size(mp) - 1);
2469 agf->agf_flcount = 0;
2470 xfs_alloc_log_agf(tp, agbp, XFS_AGF_FLFIRST | XFS_AGF_FLLAST |
2471 XFS_AGF_FLCOUNT);
2472
2473 pag->pagf_flcount = 0;
2474 clear_bit(XFS_AGSTATE_AGFL_NEEDS_RESET, &pag->pag_opstate);
2475}
2476
2477/*
2478 * Defer an AGFL block free. This is effectively equivalent to
2479 * xfs_free_extent_later() with some special handling particular to AGFL blocks.
2480 *
2481 * Deferring AGFL frees helps prevent log reservation overruns due to too many
2482 * allocation operations in a transaction. AGFL frees are prone to this problem
2483 * because for one they are always freed one at a time. Further, an immediate
2484 * AGFL block free can cause a btree join and require another block free before
2485 * the real allocation can proceed. Deferring the free disconnects freeing up
2486 * the AGFL slot from freeing the block.
2487 */
2488static int
2489xfs_defer_agfl_block(
2490 struct xfs_trans *tp,
2491 xfs_agnumber_t agno,
2492 xfs_agblock_t agbno,
2493 struct xfs_owner_info *oinfo)
2494{
2495 struct xfs_mount *mp = tp->t_mountp;
2496 struct xfs_extent_free_item *xefi;
2497 xfs_fsblock_t fsbno = XFS_AGB_TO_FSB(mp, agno, agbno);
2498
2499 ASSERT(xfs_extfree_item_cache != NULL);
2500 ASSERT(oinfo != NULL);
2501
2502 if (XFS_IS_CORRUPT(mp, !xfs_verify_fsbno(mp, fsbno)))
2503 return -EFSCORRUPTED;
2504
2505 xefi = kmem_cache_zalloc(xfs_extfree_item_cache,
2506 GFP_KERNEL | __GFP_NOFAIL);
2507 xefi->xefi_startblock = fsbno;
2508 xefi->xefi_blockcount = 1;
2509 xefi->xefi_owner = oinfo->oi_owner;
2510 xefi->xefi_agresv = XFS_AG_RESV_AGFL;
2511
2512 trace_xfs_agfl_free_defer(mp, agno, 0, agbno, 1);
2513
2514 xfs_extent_free_get_group(mp, xefi);
2515 xfs_defer_add(tp, &xefi->xefi_list, &xfs_agfl_free_defer_type);
2516 return 0;
2517}
2518
2519/*
2520 * Add the extent to the list of extents to be free at transaction end.
2521 * The list is maintained sorted (by block number).
2522 */
2523static int
2524xfs_defer_extent_free(
2525 struct xfs_trans *tp,
2526 xfs_fsblock_t bno,
2527 xfs_filblks_t len,
2528 const struct xfs_owner_info *oinfo,
2529 enum xfs_ag_resv_type type,
2530 bool skip_discard,
2531 struct xfs_defer_pending **dfpp)
2532{
2533 struct xfs_extent_free_item *xefi;
2534 struct xfs_mount *mp = tp->t_mountp;
2535#ifdef DEBUG
2536 xfs_agnumber_t agno;
2537 xfs_agblock_t agbno;
2538
2539 ASSERT(bno != NULLFSBLOCK);
2540 ASSERT(len > 0);
2541 ASSERT(len <= XFS_MAX_BMBT_EXTLEN);
2542 ASSERT(!isnullstartblock(bno));
2543 agno = XFS_FSB_TO_AGNO(mp, bno);
2544 agbno = XFS_FSB_TO_AGBNO(mp, bno);
2545 ASSERT(agno < mp->m_sb.sb_agcount);
2546 ASSERT(agbno < mp->m_sb.sb_agblocks);
2547 ASSERT(len < mp->m_sb.sb_agblocks);
2548 ASSERT(agbno + len <= mp->m_sb.sb_agblocks);
2549#endif
2550 ASSERT(xfs_extfree_item_cache != NULL);
2551 ASSERT(type != XFS_AG_RESV_AGFL);
2552
2553 if (XFS_IS_CORRUPT(mp, !xfs_verify_fsbext(mp, bno, len)))
2554 return -EFSCORRUPTED;
2555
2556 xefi = kmem_cache_zalloc(xfs_extfree_item_cache,
2557 GFP_KERNEL | __GFP_NOFAIL);
2558 xefi->xefi_startblock = bno;
2559 xefi->xefi_blockcount = (xfs_extlen_t)len;
2560 xefi->xefi_agresv = type;
2561 if (skip_discard)
2562 xefi->xefi_flags |= XFS_EFI_SKIP_DISCARD;
2563 if (oinfo) {
2564 ASSERT(oinfo->oi_offset == 0);
2565
2566 if (oinfo->oi_flags & XFS_OWNER_INFO_ATTR_FORK)
2567 xefi->xefi_flags |= XFS_EFI_ATTR_FORK;
2568 if (oinfo->oi_flags & XFS_OWNER_INFO_BMBT_BLOCK)
2569 xefi->xefi_flags |= XFS_EFI_BMBT_BLOCK;
2570 xefi->xefi_owner = oinfo->oi_owner;
2571 } else {
2572 xefi->xefi_owner = XFS_RMAP_OWN_NULL;
2573 }
2574 trace_xfs_bmap_free_defer(mp,
2575 XFS_FSB_TO_AGNO(tp->t_mountp, bno), 0,
2576 XFS_FSB_TO_AGBNO(tp->t_mountp, bno), len);
2577
2578 xfs_extent_free_get_group(mp, xefi);
2579 *dfpp = xfs_defer_add(tp, &xefi->xefi_list, &xfs_extent_free_defer_type);
2580 return 0;
2581}
2582
2583int
2584xfs_free_extent_later(
2585 struct xfs_trans *tp,
2586 xfs_fsblock_t bno,
2587 xfs_filblks_t len,
2588 const struct xfs_owner_info *oinfo,
2589 enum xfs_ag_resv_type type,
2590 bool skip_discard)
2591{
2592 struct xfs_defer_pending *dontcare = NULL;
2593
2594 return xfs_defer_extent_free(tp, bno, len, oinfo, type, skip_discard,
2595 &dontcare);
2596}
2597
2598/*
2599 * Set up automatic freeing of unwritten space in the filesystem.
2600 *
2601 * This function attached a paused deferred extent free item to the
2602 * transaction. Pausing means that the EFI will be logged in the next
2603 * transaction commit, but the pending EFI will not be finished until the
2604 * pending item is unpaused.
2605 *
2606 * If the system goes down after the EFI has been persisted to the log but
2607 * before the pending item is unpaused, log recovery will find the EFI, fail to
2608 * find the EFD, and free the space.
2609 *
2610 * If the pending item is unpaused, the next transaction commit will log an EFD
2611 * without freeing the space.
2612 *
2613 * Caller must ensure that the tp, fsbno, len, oinfo, and resv flags of the
2614 * @args structure are set to the relevant values.
2615 */
2616int
2617xfs_alloc_schedule_autoreap(
2618 const struct xfs_alloc_arg *args,
2619 bool skip_discard,
2620 struct xfs_alloc_autoreap *aarp)
2621{
2622 int error;
2623
2624 error = xfs_defer_extent_free(args->tp, args->fsbno, args->len,
2625 &args->oinfo, args->resv, skip_discard, &aarp->dfp);
2626 if (error)
2627 return error;
2628
2629 xfs_defer_item_pause(args->tp, aarp->dfp);
2630 return 0;
2631}
2632
2633/*
2634 * Cancel automatic freeing of unwritten space in the filesystem.
2635 *
2636 * Earlier, we created a paused deferred extent free item and attached it to
2637 * this transaction so that we could automatically roll back a new space
2638 * allocation if the system went down. Now we want to cancel the paused work
2639 * item by marking the EFI stale so we don't actually free the space, unpausing
2640 * the pending item and logging an EFD.
2641 *
2642 * The caller generally should have already mapped the space into the ondisk
2643 * filesystem. If the reserved space was partially used, the caller must call
2644 * xfs_free_extent_later to create a new EFI to free the unused space.
2645 */
2646void
2647xfs_alloc_cancel_autoreap(
2648 struct xfs_trans *tp,
2649 struct xfs_alloc_autoreap *aarp)
2650{
2651 struct xfs_defer_pending *dfp = aarp->dfp;
2652 struct xfs_extent_free_item *xefi;
2653
2654 if (!dfp)
2655 return;
2656
2657 list_for_each_entry(xefi, &dfp->dfp_work, xefi_list)
2658 xefi->xefi_flags |= XFS_EFI_CANCELLED;
2659
2660 xfs_defer_item_unpause(tp, dfp);
2661}
2662
2663/*
2664 * Commit automatic freeing of unwritten space in the filesystem.
2665 *
2666 * This unpauses an earlier _schedule_autoreap and commits to freeing the
2667 * allocated space. Call this if none of the reserved space was used.
2668 */
2669void
2670xfs_alloc_commit_autoreap(
2671 struct xfs_trans *tp,
2672 struct xfs_alloc_autoreap *aarp)
2673{
2674 if (aarp->dfp)
2675 xfs_defer_item_unpause(tp, aarp->dfp);
2676}
2677
2678#ifdef DEBUG
2679/*
2680 * Check if an AGF has a free extent record whose length is equal to
2681 * args->minlen.
2682 */
2683STATIC int
2684xfs_exact_minlen_extent_available(
2685 struct xfs_alloc_arg *args,
2686 struct xfs_buf *agbp,
2687 int *stat)
2688{
2689 struct xfs_btree_cur *cnt_cur;
2690 xfs_agblock_t fbno;
2691 xfs_extlen_t flen;
2692 int error = 0;
2693
2694 cnt_cur = xfs_allocbt_init_cursor(args->mp, args->tp, agbp,
2695 args->pag, XFS_BTNUM_CNT);
2696 error = xfs_alloc_lookup_ge(cnt_cur, 0, args->minlen, stat);
2697 if (error)
2698 goto out;
2699
2700 if (*stat == 0) {
2701 error = -EFSCORRUPTED;
2702 goto out;
2703 }
2704
2705 error = xfs_alloc_get_rec(cnt_cur, &fbno, &flen, stat);
2706 if (error)
2707 goto out;
2708
2709 if (*stat == 1 && flen != args->minlen)
2710 *stat = 0;
2711
2712out:
2713 xfs_btree_del_cursor(cnt_cur, error);
2714
2715 return error;
2716}
2717#endif
2718
2719/*
2720 * Decide whether to use this allocation group for this allocation.
2721 * If so, fix up the btree freelist's size.
2722 */
2723int /* error */
2724xfs_alloc_fix_freelist(
2725 struct xfs_alloc_arg *args, /* allocation argument structure */
2726 uint32_t alloc_flags)
2727{
2728 struct xfs_mount *mp = args->mp;
2729 struct xfs_perag *pag = args->pag;
2730 struct xfs_trans *tp = args->tp;
2731 struct xfs_buf *agbp = NULL;
2732 struct xfs_buf *agflbp = NULL;
2733 struct xfs_alloc_arg targs; /* local allocation arguments */
2734 xfs_agblock_t bno; /* freelist block */
2735 xfs_extlen_t need; /* total blocks needed in freelist */
2736 int error = 0;
2737
2738 /* deferred ops (AGFL block frees) require permanent transactions */
2739 ASSERT(tp->t_flags & XFS_TRANS_PERM_LOG_RES);
2740
2741 if (!xfs_perag_initialised_agf(pag)) {
2742 error = xfs_alloc_read_agf(pag, tp, alloc_flags, &agbp);
2743 if (error) {
2744 /* Couldn't lock the AGF so skip this AG. */
2745 if (error == -EAGAIN)
2746 error = 0;
2747 goto out_no_agbp;
2748 }
2749 }
2750
2751 /*
2752 * If this is a metadata preferred pag and we are user data then try
2753 * somewhere else if we are not being asked to try harder at this
2754 * point
2755 */
2756 if (xfs_perag_prefers_metadata(pag) &&
2757 (args->datatype & XFS_ALLOC_USERDATA) &&
2758 (alloc_flags & XFS_ALLOC_FLAG_TRYLOCK)) {
2759 ASSERT(!(alloc_flags & XFS_ALLOC_FLAG_FREEING));
2760 goto out_agbp_relse;
2761 }
2762
2763 need = xfs_alloc_min_freelist(mp, pag);
2764 if (!xfs_alloc_space_available(args, need, alloc_flags |
2765 XFS_ALLOC_FLAG_CHECK))
2766 goto out_agbp_relse;
2767
2768 /*
2769 * Get the a.g. freespace buffer.
2770 * Can fail if we're not blocking on locks, and it's held.
2771 */
2772 if (!agbp) {
2773 error = xfs_alloc_read_agf(pag, tp, alloc_flags, &agbp);
2774 if (error) {
2775 /* Couldn't lock the AGF so skip this AG. */
2776 if (error == -EAGAIN)
2777 error = 0;
2778 goto out_no_agbp;
2779 }
2780 }
2781
2782 /* reset a padding mismatched agfl before final free space check */
2783 if (xfs_perag_agfl_needs_reset(pag))
2784 xfs_agfl_reset(tp, agbp, pag);
2785
2786 /* If there isn't enough total space or single-extent, reject it. */
2787 need = xfs_alloc_min_freelist(mp, pag);
2788 if (!xfs_alloc_space_available(args, need, alloc_flags))
2789 goto out_agbp_relse;
2790
2791#ifdef DEBUG
2792 if (args->alloc_minlen_only) {
2793 int stat;
2794
2795 error = xfs_exact_minlen_extent_available(args, agbp, &stat);
2796 if (error || !stat)
2797 goto out_agbp_relse;
2798 }
2799#endif
2800 /*
2801 * Make the freelist shorter if it's too long.
2802 *
2803 * Note that from this point onwards, we will always release the agf and
2804 * agfl buffers on error. This handles the case where we error out and
2805 * the buffers are clean or may not have been joined to the transaction
2806 * and hence need to be released manually. If they have been joined to
2807 * the transaction, then xfs_trans_brelse() will handle them
2808 * appropriately based on the recursion count and dirty state of the
2809 * buffer.
2810 *
2811 * XXX (dgc): When we have lots of free space, does this buy us
2812 * anything other than extra overhead when we need to put more blocks
2813 * back on the free list? Maybe we should only do this when space is
2814 * getting low or the AGFL is more than half full?
2815 *
2816 * The NOSHRINK flag prevents the AGFL from being shrunk if it's too
2817 * big; the NORMAP flag prevents AGFL expand/shrink operations from
2818 * updating the rmapbt. Both flags are used in xfs_repair while we're
2819 * rebuilding the rmapbt, and neither are used by the kernel. They're
2820 * both required to ensure that rmaps are correctly recorded for the
2821 * regenerated AGFL, bnobt, and cntbt. See repair/phase5.c and
2822 * repair/rmap.c in xfsprogs for details.
2823 */
2824 memset(&targs, 0, sizeof(targs));
2825 /* struct copy below */
2826 if (alloc_flags & XFS_ALLOC_FLAG_NORMAP)
2827 targs.oinfo = XFS_RMAP_OINFO_SKIP_UPDATE;
2828 else
2829 targs.oinfo = XFS_RMAP_OINFO_AG;
2830 while (!(alloc_flags & XFS_ALLOC_FLAG_NOSHRINK) &&
2831 pag->pagf_flcount > need) {
2832 error = xfs_alloc_get_freelist(pag, tp, agbp, &bno, 0);
2833 if (error)
2834 goto out_agbp_relse;
2835
2836 /* defer agfl frees */
2837 error = xfs_defer_agfl_block(tp, args->agno, bno, &targs.oinfo);
2838 if (error)
2839 goto out_agbp_relse;
2840 }
2841
2842 targs.tp = tp;
2843 targs.mp = mp;
2844 targs.agbp = agbp;
2845 targs.agno = args->agno;
2846 targs.alignment = targs.minlen = targs.prod = 1;
2847 targs.pag = pag;
2848 error = xfs_alloc_read_agfl(pag, tp, &agflbp);
2849 if (error)
2850 goto out_agbp_relse;
2851
2852 /* Make the freelist longer if it's too short. */
2853 while (pag->pagf_flcount < need) {
2854 targs.agbno = 0;
2855 targs.maxlen = need - pag->pagf_flcount;
2856 targs.resv = XFS_AG_RESV_AGFL;
2857
2858 /* Allocate as many blocks as possible at once. */
2859 error = xfs_alloc_ag_vextent_size(&targs, alloc_flags);
2860 if (error)
2861 goto out_agflbp_relse;
2862
2863 /*
2864 * Stop if we run out. Won't happen if callers are obeying
2865 * the restrictions correctly. Can happen for free calls
2866 * on a completely full ag.
2867 */
2868 if (targs.agbno == NULLAGBLOCK) {
2869 if (alloc_flags & XFS_ALLOC_FLAG_FREEING)
2870 break;
2871 goto out_agflbp_relse;
2872 }
2873
2874 if (!xfs_rmap_should_skip_owner_update(&targs.oinfo)) {
2875 error = xfs_rmap_alloc(tp, agbp, pag,
2876 targs.agbno, targs.len, &targs.oinfo);
2877 if (error)
2878 goto out_agflbp_relse;
2879 }
2880 error = xfs_alloc_update_counters(tp, agbp,
2881 -((long)(targs.len)));
2882 if (error)
2883 goto out_agflbp_relse;
2884
2885 /*
2886 * Put each allocated block on the list.
2887 */
2888 for (bno = targs.agbno; bno < targs.agbno + targs.len; bno++) {
2889 error = xfs_alloc_put_freelist(pag, tp, agbp,
2890 agflbp, bno, 0);
2891 if (error)
2892 goto out_agflbp_relse;
2893 }
2894 }
2895 xfs_trans_brelse(tp, agflbp);
2896 args->agbp = agbp;
2897 return 0;
2898
2899out_agflbp_relse:
2900 xfs_trans_brelse(tp, agflbp);
2901out_agbp_relse:
2902 if (agbp)
2903 xfs_trans_brelse(tp, agbp);
2904out_no_agbp:
2905 args->agbp = NULL;
2906 return error;
2907}
2908
2909/*
2910 * Get a block from the freelist.
2911 * Returns with the buffer for the block gotten.
2912 */
2913int
2914xfs_alloc_get_freelist(
2915 struct xfs_perag *pag,
2916 struct xfs_trans *tp,
2917 struct xfs_buf *agbp,
2918 xfs_agblock_t *bnop,
2919 int btreeblk)
2920{
2921 struct xfs_agf *agf = agbp->b_addr;
2922 struct xfs_buf *agflbp;
2923 xfs_agblock_t bno;
2924 __be32 *agfl_bno;
2925 int error;
2926 uint32_t logflags;
2927 struct xfs_mount *mp = tp->t_mountp;
2928
2929 /*
2930 * Freelist is empty, give up.
2931 */
2932 if (!agf->agf_flcount) {
2933 *bnop = NULLAGBLOCK;
2934 return 0;
2935 }
2936 /*
2937 * Read the array of free blocks.
2938 */
2939 error = xfs_alloc_read_agfl(pag, tp, &agflbp);
2940 if (error)
2941 return error;
2942
2943
2944 /*
2945 * Get the block number and update the data structures.
2946 */
2947 agfl_bno = xfs_buf_to_agfl_bno(agflbp);
2948 bno = be32_to_cpu(agfl_bno[be32_to_cpu(agf->agf_flfirst)]);
2949 if (XFS_IS_CORRUPT(tp->t_mountp, !xfs_verify_agbno(pag, bno)))
2950 return -EFSCORRUPTED;
2951
2952 be32_add_cpu(&agf->agf_flfirst, 1);
2953 xfs_trans_brelse(tp, agflbp);
2954 if (be32_to_cpu(agf->agf_flfirst) == xfs_agfl_size(mp))
2955 agf->agf_flfirst = 0;
2956
2957 ASSERT(!xfs_perag_agfl_needs_reset(pag));
2958 be32_add_cpu(&agf->agf_flcount, -1);
2959 pag->pagf_flcount--;
2960
2961 logflags = XFS_AGF_FLFIRST | XFS_AGF_FLCOUNT;
2962 if (btreeblk) {
2963 be32_add_cpu(&agf->agf_btreeblks, 1);
2964 pag->pagf_btreeblks++;
2965 logflags |= XFS_AGF_BTREEBLKS;
2966 }
2967
2968 xfs_alloc_log_agf(tp, agbp, logflags);
2969 *bnop = bno;
2970
2971 return 0;
2972}
2973
2974/*
2975 * Log the given fields from the agf structure.
2976 */
2977void
2978xfs_alloc_log_agf(
2979 struct xfs_trans *tp,
2980 struct xfs_buf *bp,
2981 uint32_t fields)
2982{
2983 int first; /* first byte offset */
2984 int last; /* last byte offset */
2985 static const short offsets[] = {
2986 offsetof(xfs_agf_t, agf_magicnum),
2987 offsetof(xfs_agf_t, agf_versionnum),
2988 offsetof(xfs_agf_t, agf_seqno),
2989 offsetof(xfs_agf_t, agf_length),
2990 offsetof(xfs_agf_t, agf_roots[0]),
2991 offsetof(xfs_agf_t, agf_levels[0]),
2992 offsetof(xfs_agf_t, agf_flfirst),
2993 offsetof(xfs_agf_t, agf_fllast),
2994 offsetof(xfs_agf_t, agf_flcount),
2995 offsetof(xfs_agf_t, agf_freeblks),
2996 offsetof(xfs_agf_t, agf_longest),
2997 offsetof(xfs_agf_t, agf_btreeblks),
2998 offsetof(xfs_agf_t, agf_uuid),
2999 offsetof(xfs_agf_t, agf_rmap_blocks),
3000 offsetof(xfs_agf_t, agf_refcount_blocks),
3001 offsetof(xfs_agf_t, agf_refcount_root),
3002 offsetof(xfs_agf_t, agf_refcount_level),
3003 /* needed so that we don't log the whole rest of the structure: */
3004 offsetof(xfs_agf_t, agf_spare64),
3005 sizeof(xfs_agf_t)
3006 };
3007
3008 trace_xfs_agf(tp->t_mountp, bp->b_addr, fields, _RET_IP_);
3009
3010 xfs_trans_buf_set_type(tp, bp, XFS_BLFT_AGF_BUF);
3011
3012 xfs_btree_offsets(fields, offsets, XFS_AGF_NUM_BITS, &first, &last);
3013 xfs_trans_log_buf(tp, bp, (uint)first, (uint)last);
3014}
3015
3016/*
3017 * Put the block on the freelist for the allocation group.
3018 */
3019int
3020xfs_alloc_put_freelist(
3021 struct xfs_perag *pag,
3022 struct xfs_trans *tp,
3023 struct xfs_buf *agbp,
3024 struct xfs_buf *agflbp,
3025 xfs_agblock_t bno,
3026 int btreeblk)
3027{
3028 struct xfs_mount *mp = tp->t_mountp;
3029 struct xfs_agf *agf = agbp->b_addr;
3030 __be32 *blockp;
3031 int error;
3032 uint32_t logflags;
3033 __be32 *agfl_bno;
3034 int startoff;
3035
3036 if (!agflbp) {
3037 error = xfs_alloc_read_agfl(pag, tp, &agflbp);
3038 if (error)
3039 return error;
3040 }
3041
3042 be32_add_cpu(&agf->agf_fllast, 1);
3043 if (be32_to_cpu(agf->agf_fllast) == xfs_agfl_size(mp))
3044 agf->agf_fllast = 0;
3045
3046 ASSERT(!xfs_perag_agfl_needs_reset(pag));
3047 be32_add_cpu(&agf->agf_flcount, 1);
3048 pag->pagf_flcount++;
3049
3050 logflags = XFS_AGF_FLLAST | XFS_AGF_FLCOUNT;
3051 if (btreeblk) {
3052 be32_add_cpu(&agf->agf_btreeblks, -1);
3053 pag->pagf_btreeblks--;
3054 logflags |= XFS_AGF_BTREEBLKS;
3055 }
3056
3057 xfs_alloc_log_agf(tp, agbp, logflags);
3058
3059 ASSERT(be32_to_cpu(agf->agf_flcount) <= xfs_agfl_size(mp));
3060
3061 agfl_bno = xfs_buf_to_agfl_bno(agflbp);
3062 blockp = &agfl_bno[be32_to_cpu(agf->agf_fllast)];
3063 *blockp = cpu_to_be32(bno);
3064 startoff = (char *)blockp - (char *)agflbp->b_addr;
3065
3066 xfs_alloc_log_agf(tp, agbp, logflags);
3067
3068 xfs_trans_buf_set_type(tp, agflbp, XFS_BLFT_AGFL_BUF);
3069 xfs_trans_log_buf(tp, agflbp, startoff,
3070 startoff + sizeof(xfs_agblock_t) - 1);
3071 return 0;
3072}
3073
3074/*
3075 * Check that this AGF/AGI header's sequence number and length matches the AG
3076 * number and size in fsblocks.
3077 */
3078xfs_failaddr_t
3079xfs_validate_ag_length(
3080 struct xfs_buf *bp,
3081 uint32_t seqno,
3082 uint32_t length)
3083{
3084 struct xfs_mount *mp = bp->b_mount;
3085 /*
3086 * During growfs operations, the perag is not fully initialised,
3087 * so we can't use it for any useful checking. growfs ensures we can't
3088 * use it by using uncached buffers that don't have the perag attached
3089 * so we can detect and avoid this problem.
3090 */
3091 if (bp->b_pag && seqno != bp->b_pag->pag_agno)
3092 return __this_address;
3093
3094 /*
3095 * Only the last AG in the filesystem is allowed to be shorter
3096 * than the AG size recorded in the superblock.
3097 */
3098 if (length != mp->m_sb.sb_agblocks) {
3099 /*
3100 * During growfs, the new last AG can get here before we
3101 * have updated the superblock. Give it a pass on the seqno
3102 * check.
3103 */
3104 if (bp->b_pag && seqno != mp->m_sb.sb_agcount - 1)
3105 return __this_address;
3106 if (length < XFS_MIN_AG_BLOCKS)
3107 return __this_address;
3108 if (length > mp->m_sb.sb_agblocks)
3109 return __this_address;
3110 }
3111
3112 return NULL;
3113}
3114
3115/*
3116 * Verify the AGF is consistent.
3117 *
3118 * We do not verify the AGFL indexes in the AGF are fully consistent here
3119 * because of issues with variable on-disk structure sizes. Instead, we check
3120 * the agfl indexes for consistency when we initialise the perag from the AGF
3121 * information after a read completes.
3122 *
3123 * If the index is inconsistent, then we mark the perag as needing an AGFL
3124 * reset. The first AGFL update performed then resets the AGFL indexes and
3125 * refills the AGFL with known good free blocks, allowing the filesystem to
3126 * continue operating normally at the cost of a few leaked free space blocks.
3127 */
3128static xfs_failaddr_t
3129xfs_agf_verify(
3130 struct xfs_buf *bp)
3131{
3132 struct xfs_mount *mp = bp->b_mount;
3133 struct xfs_agf *agf = bp->b_addr;
3134 xfs_failaddr_t fa;
3135 uint32_t agf_seqno = be32_to_cpu(agf->agf_seqno);
3136 uint32_t agf_length = be32_to_cpu(agf->agf_length);
3137
3138 if (xfs_has_crc(mp)) {
3139 if (!uuid_equal(&agf->agf_uuid, &mp->m_sb.sb_meta_uuid))
3140 return __this_address;
3141 if (!xfs_log_check_lsn(mp, be64_to_cpu(agf->agf_lsn)))
3142 return __this_address;
3143 }
3144
3145 if (!xfs_verify_magic(bp, agf->agf_magicnum))
3146 return __this_address;
3147
3148 if (!XFS_AGF_GOOD_VERSION(be32_to_cpu(agf->agf_versionnum)))
3149 return __this_address;
3150
3151 /*
3152 * Both agf_seqno and agf_length need to validated before anything else
3153 * block number related in the AGF or AGFL can be checked.
3154 */
3155 fa = xfs_validate_ag_length(bp, agf_seqno, agf_length);
3156 if (fa)
3157 return fa;
3158
3159 if (be32_to_cpu(agf->agf_flfirst) >= xfs_agfl_size(mp))
3160 return __this_address;
3161 if (be32_to_cpu(agf->agf_fllast) >= xfs_agfl_size(mp))
3162 return __this_address;
3163 if (be32_to_cpu(agf->agf_flcount) > xfs_agfl_size(mp))
3164 return __this_address;
3165
3166 if (be32_to_cpu(agf->agf_freeblks) < be32_to_cpu(agf->agf_longest) ||
3167 be32_to_cpu(agf->agf_freeblks) > agf_length)
3168 return __this_address;
3169
3170 if (be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNO]) < 1 ||
3171 be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNT]) < 1 ||
3172 be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNO]) >
3173 mp->m_alloc_maxlevels ||
3174 be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNT]) >
3175 mp->m_alloc_maxlevels)
3176 return __this_address;
3177
3178 if (xfs_has_lazysbcount(mp) &&
3179 be32_to_cpu(agf->agf_btreeblks) > agf_length)
3180 return __this_address;
3181
3182 if (xfs_has_rmapbt(mp)) {
3183 if (be32_to_cpu(agf->agf_rmap_blocks) > agf_length)
3184 return __this_address;
3185
3186 if (be32_to_cpu(agf->agf_levels[XFS_BTNUM_RMAP]) < 1 ||
3187 be32_to_cpu(agf->agf_levels[XFS_BTNUM_RMAP]) >
3188 mp->m_rmap_maxlevels)
3189 return __this_address;
3190 }
3191
3192 if (xfs_has_reflink(mp)) {
3193 if (be32_to_cpu(agf->agf_refcount_blocks) > agf_length)
3194 return __this_address;
3195
3196 if (be32_to_cpu(agf->agf_refcount_level) < 1 ||
3197 be32_to_cpu(agf->agf_refcount_level) > mp->m_refc_maxlevels)
3198 return __this_address;
3199 }
3200
3201 return NULL;
3202}
3203
3204static void
3205xfs_agf_read_verify(
3206 struct xfs_buf *bp)
3207{
3208 struct xfs_mount *mp = bp->b_mount;
3209 xfs_failaddr_t fa;
3210
3211 if (xfs_has_crc(mp) &&
3212 !xfs_buf_verify_cksum(bp, XFS_AGF_CRC_OFF))
3213 xfs_verifier_error(bp, -EFSBADCRC, __this_address);
3214 else {
3215 fa = xfs_agf_verify(bp);
3216 if (XFS_TEST_ERROR(fa, mp, XFS_ERRTAG_ALLOC_READ_AGF))
3217 xfs_verifier_error(bp, -EFSCORRUPTED, fa);
3218 }
3219}
3220
3221static void
3222xfs_agf_write_verify(
3223 struct xfs_buf *bp)
3224{
3225 struct xfs_mount *mp = bp->b_mount;
3226 struct xfs_buf_log_item *bip = bp->b_log_item;
3227 struct xfs_agf *agf = bp->b_addr;
3228 xfs_failaddr_t fa;
3229
3230 fa = xfs_agf_verify(bp);
3231 if (fa) {
3232 xfs_verifier_error(bp, -EFSCORRUPTED, fa);
3233 return;
3234 }
3235
3236 if (!xfs_has_crc(mp))
3237 return;
3238
3239 if (bip)
3240 agf->agf_lsn = cpu_to_be64(bip->bli_item.li_lsn);
3241
3242 xfs_buf_update_cksum(bp, XFS_AGF_CRC_OFF);
3243}
3244
3245const struct xfs_buf_ops xfs_agf_buf_ops = {
3246 .name = "xfs_agf",
3247 .magic = { cpu_to_be32(XFS_AGF_MAGIC), cpu_to_be32(XFS_AGF_MAGIC) },
3248 .verify_read = xfs_agf_read_verify,
3249 .verify_write = xfs_agf_write_verify,
3250 .verify_struct = xfs_agf_verify,
3251};
3252
3253/*
3254 * Read in the allocation group header (free/alloc section).
3255 */
3256int
3257xfs_read_agf(
3258 struct xfs_perag *pag,
3259 struct xfs_trans *tp,
3260 int flags,
3261 struct xfs_buf **agfbpp)
3262{
3263 struct xfs_mount *mp = pag->pag_mount;
3264 int error;
3265
3266 trace_xfs_read_agf(pag->pag_mount, pag->pag_agno);
3267
3268 error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp,
3269 XFS_AG_DADDR(mp, pag->pag_agno, XFS_AGF_DADDR(mp)),
3270 XFS_FSS_TO_BB(mp, 1), flags, agfbpp, &xfs_agf_buf_ops);
3271 if (error)
3272 return error;
3273
3274 xfs_buf_set_ref(*agfbpp, XFS_AGF_REF);
3275 return 0;
3276}
3277
3278/*
3279 * Read in the allocation group header (free/alloc section) and initialise the
3280 * perag structure if necessary. If the caller provides @agfbpp, then return the
3281 * locked buffer to the caller, otherwise free it.
3282 */
3283int
3284xfs_alloc_read_agf(
3285 struct xfs_perag *pag,
3286 struct xfs_trans *tp,
3287 int flags,
3288 struct xfs_buf **agfbpp)
3289{
3290 struct xfs_buf *agfbp;
3291 struct xfs_agf *agf;
3292 int error;
3293 int allocbt_blks;
3294
3295 trace_xfs_alloc_read_agf(pag->pag_mount, pag->pag_agno);
3296
3297 /* We don't support trylock when freeing. */
3298 ASSERT((flags & (XFS_ALLOC_FLAG_FREEING | XFS_ALLOC_FLAG_TRYLOCK)) !=
3299 (XFS_ALLOC_FLAG_FREEING | XFS_ALLOC_FLAG_TRYLOCK));
3300 error = xfs_read_agf(pag, tp,
3301 (flags & XFS_ALLOC_FLAG_TRYLOCK) ? XBF_TRYLOCK : 0,
3302 &agfbp);
3303 if (error)
3304 return error;
3305
3306 agf = agfbp->b_addr;
3307 if (!xfs_perag_initialised_agf(pag)) {
3308 pag->pagf_freeblks = be32_to_cpu(agf->agf_freeblks);
3309 pag->pagf_btreeblks = be32_to_cpu(agf->agf_btreeblks);
3310 pag->pagf_flcount = be32_to_cpu(agf->agf_flcount);
3311 pag->pagf_longest = be32_to_cpu(agf->agf_longest);
3312 pag->pagf_levels[XFS_BTNUM_BNOi] =
3313 be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNOi]);
3314 pag->pagf_levels[XFS_BTNUM_CNTi] =
3315 be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNTi]);
3316 pag->pagf_levels[XFS_BTNUM_RMAPi] =
3317 be32_to_cpu(agf->agf_levels[XFS_BTNUM_RMAPi]);
3318 pag->pagf_refcount_level = be32_to_cpu(agf->agf_refcount_level);
3319 if (xfs_agfl_needs_reset(pag->pag_mount, agf))
3320 set_bit(XFS_AGSTATE_AGFL_NEEDS_RESET, &pag->pag_opstate);
3321 else
3322 clear_bit(XFS_AGSTATE_AGFL_NEEDS_RESET, &pag->pag_opstate);
3323
3324 /*
3325 * Update the in-core allocbt counter. Filter out the rmapbt
3326 * subset of the btreeblks counter because the rmapbt is managed
3327 * by perag reservation. Subtract one for the rmapbt root block
3328 * because the rmap counter includes it while the btreeblks
3329 * counter only tracks non-root blocks.
3330 */
3331 allocbt_blks = pag->pagf_btreeblks;
3332 if (xfs_has_rmapbt(pag->pag_mount))
3333 allocbt_blks -= be32_to_cpu(agf->agf_rmap_blocks) - 1;
3334 if (allocbt_blks > 0)
3335 atomic64_add(allocbt_blks,
3336 &pag->pag_mount->m_allocbt_blks);
3337
3338 set_bit(XFS_AGSTATE_AGF_INIT, &pag->pag_opstate);
3339 }
3340#ifdef DEBUG
3341 else if (!xfs_is_shutdown(pag->pag_mount)) {
3342 ASSERT(pag->pagf_freeblks == be32_to_cpu(agf->agf_freeblks));
3343 ASSERT(pag->pagf_btreeblks == be32_to_cpu(agf->agf_btreeblks));
3344 ASSERT(pag->pagf_flcount == be32_to_cpu(agf->agf_flcount));
3345 ASSERT(pag->pagf_longest == be32_to_cpu(agf->agf_longest));
3346 ASSERT(pag->pagf_levels[XFS_BTNUM_BNOi] ==
3347 be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNOi]));
3348 ASSERT(pag->pagf_levels[XFS_BTNUM_CNTi] ==
3349 be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNTi]));
3350 }
3351#endif
3352 if (agfbpp)
3353 *agfbpp = agfbp;
3354 else
3355 xfs_trans_brelse(tp, agfbp);
3356 return 0;
3357}
3358
3359/*
3360 * Pre-proces allocation arguments to set initial state that we don't require
3361 * callers to set up correctly, as well as bounds check the allocation args
3362 * that are set up.
3363 */
3364static int
3365xfs_alloc_vextent_check_args(
3366 struct xfs_alloc_arg *args,
3367 xfs_fsblock_t target,
3368 xfs_agnumber_t *minimum_agno)
3369{
3370 struct xfs_mount *mp = args->mp;
3371 xfs_agblock_t agsize;
3372
3373 args->fsbno = NULLFSBLOCK;
3374
3375 *minimum_agno = 0;
3376 if (args->tp->t_highest_agno != NULLAGNUMBER)
3377 *minimum_agno = args->tp->t_highest_agno;
3378
3379 /*
3380 * Just fix this up, for the case where the last a.g. is shorter
3381 * (or there's only one a.g.) and the caller couldn't easily figure
3382 * that out (xfs_bmap_alloc).
3383 */
3384 agsize = mp->m_sb.sb_agblocks;
3385 if (args->maxlen > agsize)
3386 args->maxlen = agsize;
3387 if (args->alignment == 0)
3388 args->alignment = 1;
3389
3390 ASSERT(args->minlen > 0);
3391 ASSERT(args->maxlen > 0);
3392 ASSERT(args->alignment > 0);
3393 ASSERT(args->resv != XFS_AG_RESV_AGFL);
3394
3395 ASSERT(XFS_FSB_TO_AGNO(mp, target) < mp->m_sb.sb_agcount);
3396 ASSERT(XFS_FSB_TO_AGBNO(mp, target) < agsize);
3397 ASSERT(args->minlen <= args->maxlen);
3398 ASSERT(args->minlen <= agsize);
3399 ASSERT(args->mod < args->prod);
3400
3401 if (XFS_FSB_TO_AGNO(mp, target) >= mp->m_sb.sb_agcount ||
3402 XFS_FSB_TO_AGBNO(mp, target) >= agsize ||
3403 args->minlen > args->maxlen || args->minlen > agsize ||
3404 args->mod >= args->prod) {
3405 trace_xfs_alloc_vextent_badargs(args);
3406 return -ENOSPC;
3407 }
3408
3409 if (args->agno != NULLAGNUMBER && *minimum_agno > args->agno) {
3410 trace_xfs_alloc_vextent_skip_deadlock(args);
3411 return -ENOSPC;
3412 }
3413 return 0;
3414
3415}
3416
3417/*
3418 * Prepare an AG for allocation. If the AG is not prepared to accept the
3419 * allocation, return failure.
3420 *
3421 * XXX(dgc): The complexity of "need_pag" will go away as all caller paths are
3422 * modified to hold their own perag references.
3423 */
3424static int
3425xfs_alloc_vextent_prepare_ag(
3426 struct xfs_alloc_arg *args,
3427 uint32_t alloc_flags)
3428{
3429 bool need_pag = !args->pag;
3430 int error;
3431
3432 if (need_pag)
3433 args->pag = xfs_perag_get(args->mp, args->agno);
3434
3435 args->agbp = NULL;
3436 error = xfs_alloc_fix_freelist(args, alloc_flags);
3437 if (error) {
3438 trace_xfs_alloc_vextent_nofix(args);
3439 if (need_pag)
3440 xfs_perag_put(args->pag);
3441 args->agbno = NULLAGBLOCK;
3442 return error;
3443 }
3444 if (!args->agbp) {
3445 /* cannot allocate in this AG at all */
3446 trace_xfs_alloc_vextent_noagbp(args);
3447 args->agbno = NULLAGBLOCK;
3448 return 0;
3449 }
3450 args->wasfromfl = 0;
3451 return 0;
3452}
3453
3454/*
3455 * Post-process allocation results to account for the allocation if it succeed
3456 * and set the allocated block number correctly for the caller.
3457 *
3458 * XXX: we should really be returning ENOSPC for ENOSPC, not
3459 * hiding it behind a "successful" NULLFSBLOCK allocation.
3460 */
3461static int
3462xfs_alloc_vextent_finish(
3463 struct xfs_alloc_arg *args,
3464 xfs_agnumber_t minimum_agno,
3465 int alloc_error,
3466 bool drop_perag)
3467{
3468 struct xfs_mount *mp = args->mp;
3469 int error = 0;
3470
3471 /*
3472 * We can end up here with a locked AGF. If we failed, the caller is
3473 * likely going to try to allocate again with different parameters, and
3474 * that can widen the AGs that are searched for free space. If we have
3475 * to do BMBT block allocation, we have to do a new allocation.
3476 *
3477 * Hence leaving this function with the AGF locked opens up potential
3478 * ABBA AGF deadlocks because a future allocation attempt in this
3479 * transaction may attempt to lock a lower number AGF.
3480 *
3481 * We can't release the AGF until the transaction is commited, so at
3482 * this point we must update the "first allocation" tracker to point at
3483 * this AG if the tracker is empty or points to a lower AG. This allows
3484 * the next allocation attempt to be modified appropriately to avoid
3485 * deadlocks.
3486 */
3487 if (args->agbp &&
3488 (args->tp->t_highest_agno == NULLAGNUMBER ||
3489 args->agno > minimum_agno))
3490 args->tp->t_highest_agno = args->agno;
3491
3492 /*
3493 * If the allocation failed with an error or we had an ENOSPC result,
3494 * preserve the returned error whilst also marking the allocation result
3495 * as "no extent allocated". This ensures that callers that fail to
3496 * capture the error will still treat it as a failed allocation.
3497 */
3498 if (alloc_error || args->agbno == NULLAGBLOCK) {
3499 args->fsbno = NULLFSBLOCK;
3500 error = alloc_error;
3501 goto out_drop_perag;
3502 }
3503
3504 args->fsbno = XFS_AGB_TO_FSB(mp, args->agno, args->agbno);
3505
3506 ASSERT(args->len >= args->minlen);
3507 ASSERT(args->len <= args->maxlen);
3508 ASSERT(args->agbno % args->alignment == 0);
3509 XFS_AG_CHECK_DADDR(mp, XFS_FSB_TO_DADDR(mp, args->fsbno), args->len);
3510
3511 /* if not file data, insert new block into the reverse map btree */
3512 if (!xfs_rmap_should_skip_owner_update(&args->oinfo)) {
3513 error = xfs_rmap_alloc(args->tp, args->agbp, args->pag,
3514 args->agbno, args->len, &args->oinfo);
3515 if (error)
3516 goto out_drop_perag;
3517 }
3518
3519 if (!args->wasfromfl) {
3520 error = xfs_alloc_update_counters(args->tp, args->agbp,
3521 -((long)(args->len)));
3522 if (error)
3523 goto out_drop_perag;
3524
3525 ASSERT(!xfs_extent_busy_search(mp, args->pag, args->agbno,
3526 args->len));
3527 }
3528
3529 xfs_ag_resv_alloc_extent(args->pag, args->resv, args);
3530
3531 XFS_STATS_INC(mp, xs_allocx);
3532 XFS_STATS_ADD(mp, xs_allocb, args->len);
3533
3534 trace_xfs_alloc_vextent_finish(args);
3535
3536out_drop_perag:
3537 if (drop_perag && args->pag) {
3538 xfs_perag_rele(args->pag);
3539 args->pag = NULL;
3540 }
3541 return error;
3542}
3543
3544/*
3545 * Allocate within a single AG only. This uses a best-fit length algorithm so if
3546 * you need an exact sized allocation without locality constraints, this is the
3547 * fastest way to do it.
3548 *
3549 * Caller is expected to hold a perag reference in args->pag.
3550 */
3551int
3552xfs_alloc_vextent_this_ag(
3553 struct xfs_alloc_arg *args,
3554 xfs_agnumber_t agno)
3555{
3556 struct xfs_mount *mp = args->mp;
3557 xfs_agnumber_t minimum_agno;
3558 uint32_t alloc_flags = 0;
3559 int error;
3560
3561 ASSERT(args->pag != NULL);
3562 ASSERT(args->pag->pag_agno == agno);
3563
3564 args->agno = agno;
3565 args->agbno = 0;
3566
3567 trace_xfs_alloc_vextent_this_ag(args);
3568
3569 error = xfs_alloc_vextent_check_args(args, XFS_AGB_TO_FSB(mp, agno, 0),
3570 &minimum_agno);
3571 if (error) {
3572 if (error == -ENOSPC)
3573 return 0;
3574 return error;
3575 }
3576
3577 error = xfs_alloc_vextent_prepare_ag(args, alloc_flags);
3578 if (!error && args->agbp)
3579 error = xfs_alloc_ag_vextent_size(args, alloc_flags);
3580
3581 return xfs_alloc_vextent_finish(args, minimum_agno, error, false);
3582}
3583
3584/*
3585 * Iterate all AGs trying to allocate an extent starting from @start_ag.
3586 *
3587 * If the incoming allocation type is XFS_ALLOCTYPE_NEAR_BNO, it means the
3588 * allocation attempts in @start_agno have locality information. If we fail to
3589 * allocate in that AG, then we revert to anywhere-in-AG for all the other AGs
3590 * we attempt to allocation in as there is no locality optimisation possible for
3591 * those allocations.
3592 *
3593 * On return, args->pag may be left referenced if we finish before the "all
3594 * failed" return point. The allocation finish still needs the perag, and
3595 * so the caller will release it once they've finished the allocation.
3596 *
3597 * When we wrap the AG iteration at the end of the filesystem, we have to be
3598 * careful not to wrap into AGs below ones we already have locked in the
3599 * transaction if we are doing a blocking iteration. This will result in an
3600 * out-of-order locking of AGFs and hence can cause deadlocks.
3601 */
3602static int
3603xfs_alloc_vextent_iterate_ags(
3604 struct xfs_alloc_arg *args,
3605 xfs_agnumber_t minimum_agno,
3606 xfs_agnumber_t start_agno,
3607 xfs_agblock_t target_agbno,
3608 uint32_t alloc_flags)
3609{
3610 struct xfs_mount *mp = args->mp;
3611 xfs_agnumber_t restart_agno = minimum_agno;
3612 xfs_agnumber_t agno;
3613 int error = 0;
3614
3615 if (alloc_flags & XFS_ALLOC_FLAG_TRYLOCK)
3616 restart_agno = 0;
3617restart:
3618 for_each_perag_wrap_range(mp, start_agno, restart_agno,
3619 mp->m_sb.sb_agcount, agno, args->pag) {
3620 args->agno = agno;
3621 error = xfs_alloc_vextent_prepare_ag(args, alloc_flags);
3622 if (error)
3623 break;
3624 if (!args->agbp) {
3625 trace_xfs_alloc_vextent_loopfailed(args);
3626 continue;
3627 }
3628
3629 /*
3630 * Allocation is supposed to succeed now, so break out of the
3631 * loop regardless of whether we succeed or not.
3632 */
3633 if (args->agno == start_agno && target_agbno) {
3634 args->agbno = target_agbno;
3635 error = xfs_alloc_ag_vextent_near(args, alloc_flags);
3636 } else {
3637 args->agbno = 0;
3638 error = xfs_alloc_ag_vextent_size(args, alloc_flags);
3639 }
3640 break;
3641 }
3642 if (error) {
3643 xfs_perag_rele(args->pag);
3644 args->pag = NULL;
3645 return error;
3646 }
3647 if (args->agbp)
3648 return 0;
3649
3650 /*
3651 * We didn't find an AG we can alloation from. If we were given
3652 * constraining flags by the caller, drop them and retry the allocation
3653 * without any constraints being set.
3654 */
3655 if (alloc_flags & XFS_ALLOC_FLAG_TRYLOCK) {
3656 alloc_flags &= ~XFS_ALLOC_FLAG_TRYLOCK;
3657 restart_agno = minimum_agno;
3658 goto restart;
3659 }
3660
3661 ASSERT(args->pag == NULL);
3662 trace_xfs_alloc_vextent_allfailed(args);
3663 return 0;
3664}
3665
3666/*
3667 * Iterate from the AGs from the start AG to the end of the filesystem, trying
3668 * to allocate blocks. It starts with a near allocation attempt in the initial
3669 * AG, then falls back to anywhere-in-ag after the first AG fails. It will wrap
3670 * back to zero if allowed by previous allocations in this transaction,
3671 * otherwise will wrap back to the start AG and run a second blocking pass to
3672 * the end of the filesystem.
3673 */
3674int
3675xfs_alloc_vextent_start_ag(
3676 struct xfs_alloc_arg *args,
3677 xfs_fsblock_t target)
3678{
3679 struct xfs_mount *mp = args->mp;
3680 xfs_agnumber_t minimum_agno;
3681 xfs_agnumber_t start_agno;
3682 xfs_agnumber_t rotorstep = xfs_rotorstep;
3683 bool bump_rotor = false;
3684 uint32_t alloc_flags = XFS_ALLOC_FLAG_TRYLOCK;
3685 int error;
3686
3687 ASSERT(args->pag == NULL);
3688
3689 args->agno = NULLAGNUMBER;
3690 args->agbno = NULLAGBLOCK;
3691
3692 trace_xfs_alloc_vextent_start_ag(args);
3693
3694 error = xfs_alloc_vextent_check_args(args, target, &minimum_agno);
3695 if (error) {
3696 if (error == -ENOSPC)
3697 return 0;
3698 return error;
3699 }
3700
3701 if ((args->datatype & XFS_ALLOC_INITIAL_USER_DATA) &&
3702 xfs_is_inode32(mp)) {
3703 target = XFS_AGB_TO_FSB(mp,
3704 ((mp->m_agfrotor / rotorstep) %
3705 mp->m_sb.sb_agcount), 0);
3706 bump_rotor = 1;
3707 }
3708
3709 start_agno = max(minimum_agno, XFS_FSB_TO_AGNO(mp, target));
3710 error = xfs_alloc_vextent_iterate_ags(args, minimum_agno, start_agno,
3711 XFS_FSB_TO_AGBNO(mp, target), alloc_flags);
3712
3713 if (bump_rotor) {
3714 if (args->agno == start_agno)
3715 mp->m_agfrotor = (mp->m_agfrotor + 1) %
3716 (mp->m_sb.sb_agcount * rotorstep);
3717 else
3718 mp->m_agfrotor = (args->agno * rotorstep + 1) %
3719 (mp->m_sb.sb_agcount * rotorstep);
3720 }
3721
3722 return xfs_alloc_vextent_finish(args, minimum_agno, error, true);
3723}
3724
3725/*
3726 * Iterate from the agno indicated via @target through to the end of the
3727 * filesystem attempting blocking allocation. This does not wrap or try a second
3728 * pass, so will not recurse into AGs lower than indicated by the target.
3729 */
3730int
3731xfs_alloc_vextent_first_ag(
3732 struct xfs_alloc_arg *args,
3733 xfs_fsblock_t target)
3734 {
3735 struct xfs_mount *mp = args->mp;
3736 xfs_agnumber_t minimum_agno;
3737 xfs_agnumber_t start_agno;
3738 uint32_t alloc_flags = XFS_ALLOC_FLAG_TRYLOCK;
3739 int error;
3740
3741 ASSERT(args->pag == NULL);
3742
3743 args->agno = NULLAGNUMBER;
3744 args->agbno = NULLAGBLOCK;
3745
3746 trace_xfs_alloc_vextent_first_ag(args);
3747
3748 error = xfs_alloc_vextent_check_args(args, target, &minimum_agno);
3749 if (error) {
3750 if (error == -ENOSPC)
3751 return 0;
3752 return error;
3753 }
3754
3755 start_agno = max(minimum_agno, XFS_FSB_TO_AGNO(mp, target));
3756 error = xfs_alloc_vextent_iterate_ags(args, minimum_agno, start_agno,
3757 XFS_FSB_TO_AGBNO(mp, target), alloc_flags);
3758 return xfs_alloc_vextent_finish(args, minimum_agno, error, true);
3759}
3760
3761/*
3762 * Allocate at the exact block target or fail. Caller is expected to hold a
3763 * perag reference in args->pag.
3764 */
3765int
3766xfs_alloc_vextent_exact_bno(
3767 struct xfs_alloc_arg *args,
3768 xfs_fsblock_t target)
3769{
3770 struct xfs_mount *mp = args->mp;
3771 xfs_agnumber_t minimum_agno;
3772 int error;
3773
3774 ASSERT(args->pag != NULL);
3775 ASSERT(args->pag->pag_agno == XFS_FSB_TO_AGNO(mp, target));
3776
3777 args->agno = XFS_FSB_TO_AGNO(mp, target);
3778 args->agbno = XFS_FSB_TO_AGBNO(mp, target);
3779
3780 trace_xfs_alloc_vextent_exact_bno(args);
3781
3782 error = xfs_alloc_vextent_check_args(args, target, &minimum_agno);
3783 if (error) {
3784 if (error == -ENOSPC)
3785 return 0;
3786 return error;
3787 }
3788
3789 error = xfs_alloc_vextent_prepare_ag(args, 0);
3790 if (!error && args->agbp)
3791 error = xfs_alloc_ag_vextent_exact(args);
3792
3793 return xfs_alloc_vextent_finish(args, minimum_agno, error, false);
3794}
3795
3796/*
3797 * Allocate an extent as close to the target as possible. If there are not
3798 * viable candidates in the AG, then fail the allocation.
3799 *
3800 * Caller may or may not have a per-ag reference in args->pag.
3801 */
3802int
3803xfs_alloc_vextent_near_bno(
3804 struct xfs_alloc_arg *args,
3805 xfs_fsblock_t target)
3806{
3807 struct xfs_mount *mp = args->mp;
3808 xfs_agnumber_t minimum_agno;
3809 bool needs_perag = args->pag == NULL;
3810 uint32_t alloc_flags = 0;
3811 int error;
3812
3813 if (!needs_perag)
3814 ASSERT(args->pag->pag_agno == XFS_FSB_TO_AGNO(mp, target));
3815
3816 args->agno = XFS_FSB_TO_AGNO(mp, target);
3817 args->agbno = XFS_FSB_TO_AGBNO(mp, target);
3818
3819 trace_xfs_alloc_vextent_near_bno(args);
3820
3821 error = xfs_alloc_vextent_check_args(args, target, &minimum_agno);
3822 if (error) {
3823 if (error == -ENOSPC)
3824 return 0;
3825 return error;
3826 }
3827
3828 if (needs_perag)
3829 args->pag = xfs_perag_grab(mp, args->agno);
3830
3831 error = xfs_alloc_vextent_prepare_ag(args, alloc_flags);
3832 if (!error && args->agbp)
3833 error = xfs_alloc_ag_vextent_near(args, alloc_flags);
3834
3835 return xfs_alloc_vextent_finish(args, minimum_agno, error, needs_perag);
3836}
3837
3838/* Ensure that the freelist is at full capacity. */
3839int
3840xfs_free_extent_fix_freelist(
3841 struct xfs_trans *tp,
3842 struct xfs_perag *pag,
3843 struct xfs_buf **agbp)
3844{
3845 struct xfs_alloc_arg args;
3846 int error;
3847
3848 memset(&args, 0, sizeof(struct xfs_alloc_arg));
3849 args.tp = tp;
3850 args.mp = tp->t_mountp;
3851 args.agno = pag->pag_agno;
3852 args.pag = pag;
3853
3854 /*
3855 * validate that the block number is legal - the enables us to detect
3856 * and handle a silent filesystem corruption rather than crashing.
3857 */
3858 if (args.agno >= args.mp->m_sb.sb_agcount)
3859 return -EFSCORRUPTED;
3860
3861 error = xfs_alloc_fix_freelist(&args, XFS_ALLOC_FLAG_FREEING);
3862 if (error)
3863 return error;
3864
3865 *agbp = args.agbp;
3866 return 0;
3867}
3868
3869/*
3870 * Free an extent.
3871 * Just break up the extent address and hand off to xfs_free_ag_extent
3872 * after fixing up the freelist.
3873 */
3874int
3875__xfs_free_extent(
3876 struct xfs_trans *tp,
3877 struct xfs_perag *pag,
3878 xfs_agblock_t agbno,
3879 xfs_extlen_t len,
3880 const struct xfs_owner_info *oinfo,
3881 enum xfs_ag_resv_type type,
3882 bool skip_discard)
3883{
3884 struct xfs_mount *mp = tp->t_mountp;
3885 struct xfs_buf *agbp;
3886 struct xfs_agf *agf;
3887 int error;
3888 unsigned int busy_flags = 0;
3889
3890 ASSERT(len != 0);
3891 ASSERT(type != XFS_AG_RESV_AGFL);
3892
3893 if (XFS_TEST_ERROR(false, mp,
3894 XFS_ERRTAG_FREE_EXTENT))
3895 return -EIO;
3896
3897 error = xfs_free_extent_fix_freelist(tp, pag, &agbp);
3898 if (error)
3899 return error;
3900 agf = agbp->b_addr;
3901
3902 if (XFS_IS_CORRUPT(mp, agbno >= mp->m_sb.sb_agblocks)) {
3903 error = -EFSCORRUPTED;
3904 goto err_release;
3905 }
3906
3907 /* validate the extent size is legal now we have the agf locked */
3908 if (XFS_IS_CORRUPT(mp, agbno + len > be32_to_cpu(agf->agf_length))) {
3909 error = -EFSCORRUPTED;
3910 goto err_release;
3911 }
3912
3913 error = xfs_free_ag_extent(tp, agbp, pag->pag_agno, agbno, len, oinfo,
3914 type);
3915 if (error)
3916 goto err_release;
3917
3918 if (skip_discard)
3919 busy_flags |= XFS_EXTENT_BUSY_SKIP_DISCARD;
3920 xfs_extent_busy_insert(tp, pag, agbno, len, busy_flags);
3921 return 0;
3922
3923err_release:
3924 xfs_trans_brelse(tp, agbp);
3925 return error;
3926}
3927
3928struct xfs_alloc_query_range_info {
3929 xfs_alloc_query_range_fn fn;
3930 void *priv;
3931};
3932
3933/* Format btree record and pass to our callback. */
3934STATIC int
3935xfs_alloc_query_range_helper(
3936 struct xfs_btree_cur *cur,
3937 const union xfs_btree_rec *rec,
3938 void *priv)
3939{
3940 struct xfs_alloc_query_range_info *query = priv;
3941 struct xfs_alloc_rec_incore irec;
3942 xfs_failaddr_t fa;
3943
3944 xfs_alloc_btrec_to_irec(rec, &irec);
3945 fa = xfs_alloc_check_irec(cur->bc_ag.pag, &irec);
3946 if (fa)
3947 return xfs_alloc_complain_bad_rec(cur, fa, &irec);
3948
3949 return query->fn(cur, &irec, query->priv);
3950}
3951
3952/* Find all free space within a given range of blocks. */
3953int
3954xfs_alloc_query_range(
3955 struct xfs_btree_cur *cur,
3956 const struct xfs_alloc_rec_incore *low_rec,
3957 const struct xfs_alloc_rec_incore *high_rec,
3958 xfs_alloc_query_range_fn fn,
3959 void *priv)
3960{
3961 union xfs_btree_irec low_brec = { .a = *low_rec };
3962 union xfs_btree_irec high_brec = { .a = *high_rec };
3963 struct xfs_alloc_query_range_info query = { .priv = priv, .fn = fn };
3964
3965 ASSERT(cur->bc_btnum == XFS_BTNUM_BNO);
3966 return xfs_btree_query_range(cur, &low_brec, &high_brec,
3967 xfs_alloc_query_range_helper, &query);
3968}
3969
3970/* Find all free space records. */
3971int
3972xfs_alloc_query_all(
3973 struct xfs_btree_cur *cur,
3974 xfs_alloc_query_range_fn fn,
3975 void *priv)
3976{
3977 struct xfs_alloc_query_range_info query;
3978
3979 ASSERT(cur->bc_btnum == XFS_BTNUM_BNO);
3980 query.priv = priv;
3981 query.fn = fn;
3982 return xfs_btree_query_all(cur, xfs_alloc_query_range_helper, &query);
3983}
3984
3985/*
3986 * Scan part of the keyspace of the free space and tell us if the area has no
3987 * records, is fully mapped by records, or is partially filled.
3988 */
3989int
3990xfs_alloc_has_records(
3991 struct xfs_btree_cur *cur,
3992 xfs_agblock_t bno,
3993 xfs_extlen_t len,
3994 enum xbtree_recpacking *outcome)
3995{
3996 union xfs_btree_irec low;
3997 union xfs_btree_irec high;
3998
3999 memset(&low, 0, sizeof(low));
4000 low.a.ar_startblock = bno;
4001 memset(&high, 0xFF, sizeof(high));
4002 high.a.ar_startblock = bno + len - 1;
4003
4004 return xfs_btree_has_records(cur, &low, &high, NULL, outcome);
4005}
4006
4007/*
4008 * Walk all the blocks in the AGFL. The @walk_fn can return any negative
4009 * error code or XFS_ITER_*.
4010 */
4011int
4012xfs_agfl_walk(
4013 struct xfs_mount *mp,
4014 struct xfs_agf *agf,
4015 struct xfs_buf *agflbp,
4016 xfs_agfl_walk_fn walk_fn,
4017 void *priv)
4018{
4019 __be32 *agfl_bno;
4020 unsigned int i;
4021 int error;
4022
4023 agfl_bno = xfs_buf_to_agfl_bno(agflbp);
4024 i = be32_to_cpu(agf->agf_flfirst);
4025
4026 /* Nothing to walk in an empty AGFL. */
4027 if (agf->agf_flcount == cpu_to_be32(0))
4028 return 0;
4029
4030 /* Otherwise, walk from first to last, wrapping as needed. */
4031 for (;;) {
4032 error = walk_fn(mp, be32_to_cpu(agfl_bno[i]), priv);
4033 if (error)
4034 return error;
4035 if (i == be32_to_cpu(agf->agf_fllast))
4036 break;
4037 if (++i == xfs_agfl_size(mp))
4038 i = 0;
4039 }
4040
4041 return 0;
4042}
4043
4044int __init
4045xfs_extfree_intent_init_cache(void)
4046{
4047 xfs_extfree_item_cache = kmem_cache_create("xfs_extfree_intent",
4048 sizeof(struct xfs_extent_free_item),
4049 0, 0, NULL);
4050
4051 return xfs_extfree_item_cache != NULL ? 0 : -ENOMEM;
4052}
4053
4054void
4055xfs_extfree_intent_destroy_cache(void)
4056{
4057 kmem_cache_destroy(xfs_extfree_item_cache);
4058 xfs_extfree_item_cache = NULL;
4059}
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
42struct 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
49STATIC int xfs_alloc_ag_vextent_exact(xfs_alloc_arg_t *);
50STATIC int xfs_alloc_ag_vextent_near(xfs_alloc_arg_t *);
51STATIC int xfs_alloc_ag_vextent_size(xfs_alloc_arg_t *);
52STATIC int xfs_alloc_ag_vextent_small(xfs_alloc_arg_t *,
53 xfs_btree_cur_t *, xfs_agblock_t *, xfs_extlen_t *, int *);
54
55unsigned int
56xfs_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
66xfs_extlen_t
67xfs_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 */
94unsigned int
95xfs_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 */
115unsigned int
116xfs_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 */
137STATIC int /* error */
138xfs_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 */
153int /* error */
154xfs_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 */
169static int /* error */
170xfs_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 */
186STATIC int /* error */
187xfs_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 */
202int /* error */
203xfs_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 */
224STATIC void
225xfs_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 */
268STATIC xfs_extlen_t /* difference value (absolute) */
269xfs_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 */
339STATIC void
340xfs_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 */
377STATIC int /* error code */
378xfs_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
518static bool
519xfs_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
549static void
550xfs_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
573static void
574xfs_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
596const 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 */
605STATIC int /* error */
606xfs_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
627STATIC int
628xfs_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 */
660STATIC int /* error */
661xfs_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 */
731STATIC int /* error */
732xfs_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
823not_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
830error0:
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 */
840STATIC int
841xfs_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
914out_use_good:
915 xfs_btree_del_cursor(*scur, XFS_BTREE_NOERROR);
916 *scur = NULL;
917 return 0;
918
919out_use_search:
920 xfs_btree_del_cursor(*gcur, XFS_BTREE_NOERROR);
921 *gcur = NULL;
922 return 0;
923
924error0:
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 */
935STATIC int /* error */
936xfs_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
979restart:
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, <bno,
1003 <len, &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, <bno,
1044 <len, &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, <bno, <len, &i)))
1065 goto error0;
1066 XFS_WANT_CORRUPTED_GOTO(args->mp, i == 1, error0);
1067 xfs_alloc_compute_aligned(args, ltbno, ltlen,
1068 <bnoa, <lena);
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, <new);
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, <bno, <len, &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, <bno, <len, &i)))
1184 goto error0;
1185 XFS_WANT_CORRUPTED_GOTO(args->mp, i == 1, error0);
1186 xfs_alloc_compute_aligned(args, ltbno, ltlen,
1187 <bnoa, <lena);
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, >bno, >len, &i)))
1200 goto error0;
1201 XFS_WANT_CORRUPTED_GOTO(args->mp, i == 1, error0);
1202 xfs_alloc_compute_aligned(args, gtbno, gtlen,
1203 >bnoa, >lena);
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, <new);
1229
1230 error = xfs_alloc_find_best_extent(args,
1231 &bno_cur_lt, &bno_cur_gt,
1232 ltdiff, >bno, >len,
1233 >bnoa, >lena,
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, >new);
1246
1247 error = xfs_alloc_find_best_extent(args,
1248 &bno_cur_gt, &bno_cur_lt,
1249 gtdiff, <bno, <len,
1250 <bnoa, <lena,
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, <new);
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 */
1335STATIC int /* error */
1336xfs_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
1349restart:
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
1519error0:
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
1527out_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 */
1539STATIC int /* error */
1540xfs_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 xfs_trans_binval(args->tp, bp);
1583 }
1584 args->len = 1;
1585 args->agbno = fbno;
1586 XFS_WANT_CORRUPTED_GOTO(args->mp,
1587 args->agbno + args->len <=
1588 be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length),
1589 error0);
1590 args->wasfromfl = 1;
1591 trace_xfs_alloc_small_freelist(args);
1592
1593 /*
1594 * If we're feeding an AGFL block to something that
1595 * doesn't live in the free space, we need to clear
1596 * out the OWN_AG rmap and add the block back to
1597 * the AGFL per-AG reservation.
1598 */
1599 xfs_rmap_ag_owner(&oinfo, XFS_RMAP_OWN_AG);
1600 error = xfs_rmap_free(args->tp, args->agbp, args->agno,
1601 fbno, 1, &oinfo);
1602 if (error)
1603 goto error0;
1604 pag = xfs_perag_get(args->mp, args->agno);
1605 xfs_ag_resv_free_extent(pag, XFS_AG_RESV_AGFL,
1606 args->tp, 1);
1607 xfs_perag_put(pag);
1608
1609 *stat = 0;
1610 return 0;
1611 }
1612 /*
1613 * Nothing in the freelist.
1614 */
1615 else
1616 flen = 0;
1617 }
1618 /*
1619 * Can't allocate from the freelist for some reason.
1620 */
1621 else {
1622 fbno = NULLAGBLOCK;
1623 flen = 0;
1624 }
1625 /*
1626 * Can't do the allocation, give up.
1627 */
1628 if (flen < args->minlen) {
1629 args->agbno = NULLAGBLOCK;
1630 trace_xfs_alloc_small_notenough(args);
1631 flen = 0;
1632 }
1633 *fbnop = fbno;
1634 *flenp = flen;
1635 *stat = 1;
1636 trace_xfs_alloc_small_done(args);
1637 return 0;
1638
1639error0:
1640 trace_xfs_alloc_small_error(args);
1641 return error;
1642}
1643
1644/*
1645 * Free the extent starting at agno/bno for length.
1646 */
1647STATIC int
1648xfs_free_ag_extent(
1649 xfs_trans_t *tp,
1650 xfs_buf_t *agbp,
1651 xfs_agnumber_t agno,
1652 xfs_agblock_t bno,
1653 xfs_extlen_t len,
1654 struct xfs_owner_info *oinfo,
1655 enum xfs_ag_resv_type type)
1656{
1657 xfs_btree_cur_t *bno_cur; /* cursor for by-block btree */
1658 xfs_btree_cur_t *cnt_cur; /* cursor for by-size btree */
1659 int error; /* error return value */
1660 xfs_agblock_t gtbno; /* start of right neighbor block */
1661 xfs_extlen_t gtlen; /* length of right neighbor block */
1662 int haveleft; /* have a left neighbor block */
1663 int haveright; /* have a right neighbor block */
1664 int i; /* temp, result code */
1665 xfs_agblock_t ltbno; /* start of left neighbor block */
1666 xfs_extlen_t ltlen; /* length of left neighbor block */
1667 xfs_mount_t *mp; /* mount point struct for filesystem */
1668 xfs_agblock_t nbno; /* new starting block of freespace */
1669 xfs_extlen_t nlen; /* new length of freespace */
1670 xfs_perag_t *pag; /* per allocation group data */
1671
1672 bno_cur = cnt_cur = NULL;
1673 mp = tp->t_mountp;
1674
1675 if (oinfo->oi_owner != XFS_RMAP_OWN_UNKNOWN) {
1676 error = xfs_rmap_free(tp, agbp, agno, bno, len, oinfo);
1677 if (error)
1678 goto error0;
1679 }
1680
1681 /*
1682 * Allocate and initialize a cursor for the by-block btree.
1683 */
1684 bno_cur = xfs_allocbt_init_cursor(mp, tp, agbp, agno, XFS_BTNUM_BNO);
1685 /*
1686 * Look for a neighboring block on the left (lower block numbers)
1687 * that is contiguous with this space.
1688 */
1689 if ((error = xfs_alloc_lookup_le(bno_cur, bno, len, &haveleft)))
1690 goto error0;
1691 if (haveleft) {
1692 /*
1693 * There is a block to our left.
1694 */
1695 if ((error = xfs_alloc_get_rec(bno_cur, <bno, <len, &i)))
1696 goto error0;
1697 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, error0);
1698 /*
1699 * It's not contiguous, though.
1700 */
1701 if (ltbno + ltlen < bno)
1702 haveleft = 0;
1703 else {
1704 /*
1705 * If this failure happens the request to free this
1706 * space was invalid, it's (partly) already free.
1707 * Very bad.
1708 */
1709 XFS_WANT_CORRUPTED_GOTO(mp,
1710 ltbno + ltlen <= bno, error0);
1711 }
1712 }
1713 /*
1714 * Look for a neighboring block on the right (higher block numbers)
1715 * that is contiguous with this space.
1716 */
1717 if ((error = xfs_btree_increment(bno_cur, 0, &haveright)))
1718 goto error0;
1719 if (haveright) {
1720 /*
1721 * There is a block to our right.
1722 */
1723 if ((error = xfs_alloc_get_rec(bno_cur, >bno, >len, &i)))
1724 goto error0;
1725 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, error0);
1726 /*
1727 * It's not contiguous, though.
1728 */
1729 if (bno + len < gtbno)
1730 haveright = 0;
1731 else {
1732 /*
1733 * If this failure happens the request to free this
1734 * space was invalid, it's (partly) already free.
1735 * Very bad.
1736 */
1737 XFS_WANT_CORRUPTED_GOTO(mp, gtbno >= bno + len, error0);
1738 }
1739 }
1740 /*
1741 * Now allocate and initialize a cursor for the by-size tree.
1742 */
1743 cnt_cur = xfs_allocbt_init_cursor(mp, tp, agbp, agno, XFS_BTNUM_CNT);
1744 /*
1745 * Have both left and right contiguous neighbors.
1746 * Merge all three into a single free block.
1747 */
1748 if (haveleft && haveright) {
1749 /*
1750 * Delete the old by-size entry on the left.
1751 */
1752 if ((error = xfs_alloc_lookup_eq(cnt_cur, ltbno, ltlen, &i)))
1753 goto error0;
1754 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, error0);
1755 if ((error = xfs_btree_delete(cnt_cur, &i)))
1756 goto error0;
1757 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, error0);
1758 /*
1759 * Delete the old by-size entry on the right.
1760 */
1761 if ((error = xfs_alloc_lookup_eq(cnt_cur, gtbno, gtlen, &i)))
1762 goto error0;
1763 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, error0);
1764 if ((error = xfs_btree_delete(cnt_cur, &i)))
1765 goto error0;
1766 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, error0);
1767 /*
1768 * Delete the old by-block entry for the right block.
1769 */
1770 if ((error = xfs_btree_delete(bno_cur, &i)))
1771 goto error0;
1772 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, error0);
1773 /*
1774 * Move the by-block cursor back to the left neighbor.
1775 */
1776 if ((error = xfs_btree_decrement(bno_cur, 0, &i)))
1777 goto error0;
1778 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, error0);
1779#ifdef DEBUG
1780 /*
1781 * Check that this is the right record: delete didn't
1782 * mangle the cursor.
1783 */
1784 {
1785 xfs_agblock_t xxbno;
1786 xfs_extlen_t xxlen;
1787
1788 if ((error = xfs_alloc_get_rec(bno_cur, &xxbno, &xxlen,
1789 &i)))
1790 goto error0;
1791 XFS_WANT_CORRUPTED_GOTO(mp,
1792 i == 1 && xxbno == ltbno && xxlen == ltlen,
1793 error0);
1794 }
1795#endif
1796 /*
1797 * Update remaining by-block entry to the new, joined block.
1798 */
1799 nbno = ltbno;
1800 nlen = len + ltlen + gtlen;
1801 if ((error = xfs_alloc_update(bno_cur, nbno, nlen)))
1802 goto error0;
1803 }
1804 /*
1805 * Have only a left contiguous neighbor.
1806 * Merge it together with the new freespace.
1807 */
1808 else if (haveleft) {
1809 /*
1810 * Delete the old by-size entry on the left.
1811 */
1812 if ((error = xfs_alloc_lookup_eq(cnt_cur, ltbno, ltlen, &i)))
1813 goto error0;
1814 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, error0);
1815 if ((error = xfs_btree_delete(cnt_cur, &i)))
1816 goto error0;
1817 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, error0);
1818 /*
1819 * Back up the by-block cursor to the left neighbor, and
1820 * update its length.
1821 */
1822 if ((error = xfs_btree_decrement(bno_cur, 0, &i)))
1823 goto error0;
1824 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, error0);
1825 nbno = ltbno;
1826 nlen = len + ltlen;
1827 if ((error = xfs_alloc_update(bno_cur, nbno, nlen)))
1828 goto error0;
1829 }
1830 /*
1831 * Have only a right contiguous neighbor.
1832 * Merge it together with the new freespace.
1833 */
1834 else if (haveright) {
1835 /*
1836 * Delete the old by-size entry on the right.
1837 */
1838 if ((error = xfs_alloc_lookup_eq(cnt_cur, gtbno, gtlen, &i)))
1839 goto error0;
1840 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, error0);
1841 if ((error = xfs_btree_delete(cnt_cur, &i)))
1842 goto error0;
1843 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, error0);
1844 /*
1845 * Update the starting block and length of the right
1846 * neighbor in the by-block tree.
1847 */
1848 nbno = bno;
1849 nlen = len + gtlen;
1850 if ((error = xfs_alloc_update(bno_cur, nbno, nlen)))
1851 goto error0;
1852 }
1853 /*
1854 * No contiguous neighbors.
1855 * Insert the new freespace into the by-block tree.
1856 */
1857 else {
1858 nbno = bno;
1859 nlen = len;
1860 if ((error = xfs_btree_insert(bno_cur, &i)))
1861 goto error0;
1862 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, error0);
1863 }
1864 xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
1865 bno_cur = NULL;
1866 /*
1867 * In all cases we need to insert the new freespace in the by-size tree.
1868 */
1869 if ((error = xfs_alloc_lookup_eq(cnt_cur, nbno, nlen, &i)))
1870 goto error0;
1871 XFS_WANT_CORRUPTED_GOTO(mp, i == 0, error0);
1872 if ((error = xfs_btree_insert(cnt_cur, &i)))
1873 goto error0;
1874 XFS_WANT_CORRUPTED_GOTO(mp, i == 1, error0);
1875 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1876 cnt_cur = NULL;
1877
1878 /*
1879 * Update the freespace totals in the ag and superblock.
1880 */
1881 pag = xfs_perag_get(mp, agno);
1882 error = xfs_alloc_update_counters(tp, pag, agbp, len);
1883 xfs_ag_resv_free_extent(pag, type, tp, len);
1884 xfs_perag_put(pag);
1885 if (error)
1886 goto error0;
1887
1888 XFS_STATS_INC(mp, xs_freex);
1889 XFS_STATS_ADD(mp, xs_freeb, len);
1890
1891 trace_xfs_free_extent(mp, agno, bno, len, type == XFS_AG_RESV_AGFL,
1892 haveleft, haveright);
1893
1894 return 0;
1895
1896 error0:
1897 trace_xfs_free_extent(mp, agno, bno, len, type == XFS_AG_RESV_AGFL,
1898 -1, -1);
1899 if (bno_cur)
1900 xfs_btree_del_cursor(bno_cur, XFS_BTREE_ERROR);
1901 if (cnt_cur)
1902 xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
1903 return error;
1904}
1905
1906/*
1907 * Visible (exported) allocation/free functions.
1908 * Some of these are used just by xfs_alloc_btree.c and this file.
1909 */
1910
1911/*
1912 * Compute and fill in value of m_ag_maxlevels.
1913 */
1914void
1915xfs_alloc_compute_maxlevels(
1916 xfs_mount_t *mp) /* file system mount structure */
1917{
1918 mp->m_ag_maxlevels = xfs_btree_compute_maxlevels(mp, mp->m_alloc_mnr,
1919 (mp->m_sb.sb_agblocks + 1) / 2);
1920}
1921
1922/*
1923 * Find the length of the longest extent in an AG. The 'need' parameter
1924 * specifies how much space we're going to need for the AGFL and the
1925 * 'reserved' parameter tells us how many blocks in this AG are reserved for
1926 * other callers.
1927 */
1928xfs_extlen_t
1929xfs_alloc_longest_free_extent(
1930 struct xfs_mount *mp,
1931 struct xfs_perag *pag,
1932 xfs_extlen_t need,
1933 xfs_extlen_t reserved)
1934{
1935 xfs_extlen_t delta = 0;
1936
1937 /*
1938 * If the AGFL needs a recharge, we'll have to subtract that from the
1939 * longest extent.
1940 */
1941 if (need > pag->pagf_flcount)
1942 delta = need - pag->pagf_flcount;
1943
1944 /*
1945 * If we cannot maintain others' reservations with space from the
1946 * not-longest freesp extents, we'll have to subtract /that/ from
1947 * the longest extent too.
1948 */
1949 if (pag->pagf_freeblks - pag->pagf_longest < reserved)
1950 delta += reserved - (pag->pagf_freeblks - pag->pagf_longest);
1951
1952 /*
1953 * If the longest extent is long enough to satisfy all the
1954 * reservations and AGFL rules in place, we can return this extent.
1955 */
1956 if (pag->pagf_longest > delta)
1957 return pag->pagf_longest - delta;
1958
1959 /* Otherwise, let the caller try for 1 block if there's space. */
1960 return pag->pagf_flcount > 0 || pag->pagf_longest > 0;
1961}
1962
1963unsigned int
1964xfs_alloc_min_freelist(
1965 struct xfs_mount *mp,
1966 struct xfs_perag *pag)
1967{
1968 unsigned int min_free;
1969
1970 /* space needed by-bno freespace btree */
1971 min_free = min_t(unsigned int, pag->pagf_levels[XFS_BTNUM_BNOi] + 1,
1972 mp->m_ag_maxlevels);
1973 /* space needed by-size freespace btree */
1974 min_free += min_t(unsigned int, pag->pagf_levels[XFS_BTNUM_CNTi] + 1,
1975 mp->m_ag_maxlevels);
1976 /* space needed reverse mapping used space btree */
1977 if (xfs_sb_version_hasrmapbt(&mp->m_sb))
1978 min_free += min_t(unsigned int,
1979 pag->pagf_levels[XFS_BTNUM_RMAPi] + 1,
1980 mp->m_rmap_maxlevels);
1981
1982 return min_free;
1983}
1984
1985/*
1986 * Check if the operation we are fixing up the freelist for should go ahead or
1987 * not. If we are freeing blocks, we always allow it, otherwise the allocation
1988 * is dependent on whether the size and shape of free space available will
1989 * permit the requested allocation to take place.
1990 */
1991static bool
1992xfs_alloc_space_available(
1993 struct xfs_alloc_arg *args,
1994 xfs_extlen_t min_free,
1995 int flags)
1996{
1997 struct xfs_perag *pag = args->pag;
1998 xfs_extlen_t alloc_len, longest;
1999 xfs_extlen_t reservation; /* blocks that are still reserved */
2000 int available;
2001
2002 if (flags & XFS_ALLOC_FLAG_FREEING)
2003 return true;
2004
2005 reservation = xfs_ag_resv_needed(pag, args->resv);
2006
2007 /* do we have enough contiguous free space for the allocation? */
2008 alloc_len = args->minlen + (args->alignment - 1) + args->minalignslop;
2009 longest = xfs_alloc_longest_free_extent(args->mp, pag, min_free,
2010 reservation);
2011 if (longest < alloc_len)
2012 return false;
2013
2014 /* do we have enough free space remaining for the allocation? */
2015 available = (int)(pag->pagf_freeblks + pag->pagf_flcount -
2016 reservation - min_free - args->minleft);
2017 if (available < (int)max(args->total, alloc_len))
2018 return false;
2019
2020 /*
2021 * Clamp maxlen to the amount of free space available for the actual
2022 * extent allocation.
2023 */
2024 if (available < (int)args->maxlen && !(flags & XFS_ALLOC_FLAG_CHECK)) {
2025 args->maxlen = available;
2026 ASSERT(args->maxlen > 0);
2027 ASSERT(args->maxlen >= args->minlen);
2028 }
2029
2030 return true;
2031}
2032
2033/*
2034 * Decide whether to use this allocation group for this allocation.
2035 * If so, fix up the btree freelist's size.
2036 */
2037int /* error */
2038xfs_alloc_fix_freelist(
2039 struct xfs_alloc_arg *args, /* allocation argument structure */
2040 int flags) /* XFS_ALLOC_FLAG_... */
2041{
2042 struct xfs_mount *mp = args->mp;
2043 struct xfs_perag *pag = args->pag;
2044 struct xfs_trans *tp = args->tp;
2045 struct xfs_buf *agbp = NULL;
2046 struct xfs_buf *agflbp = NULL;
2047 struct xfs_alloc_arg targs; /* local allocation arguments */
2048 xfs_agblock_t bno; /* freelist block */
2049 xfs_extlen_t need; /* total blocks needed in freelist */
2050 int error = 0;
2051
2052 if (!pag->pagf_init) {
2053 error = xfs_alloc_read_agf(mp, tp, args->agno, flags, &agbp);
2054 if (error)
2055 goto out_no_agbp;
2056 if (!pag->pagf_init) {
2057 ASSERT(flags & XFS_ALLOC_FLAG_TRYLOCK);
2058 ASSERT(!(flags & XFS_ALLOC_FLAG_FREEING));
2059 goto out_agbp_relse;
2060 }
2061 }
2062
2063 /*
2064 * If this is a metadata preferred pag and we are user data then try
2065 * somewhere else if we are not being asked to try harder at this
2066 * point
2067 */
2068 if (pag->pagf_metadata && xfs_alloc_is_userdata(args->datatype) &&
2069 (flags & XFS_ALLOC_FLAG_TRYLOCK)) {
2070 ASSERT(!(flags & XFS_ALLOC_FLAG_FREEING));
2071 goto out_agbp_relse;
2072 }
2073
2074 need = xfs_alloc_min_freelist(mp, pag);
2075 if (!xfs_alloc_space_available(args, need, flags |
2076 XFS_ALLOC_FLAG_CHECK))
2077 goto out_agbp_relse;
2078
2079 /*
2080 * Get the a.g. freespace buffer.
2081 * Can fail if we're not blocking on locks, and it's held.
2082 */
2083 if (!agbp) {
2084 error = xfs_alloc_read_agf(mp, tp, args->agno, flags, &agbp);
2085 if (error)
2086 goto out_no_agbp;
2087 if (!agbp) {
2088 ASSERT(flags & XFS_ALLOC_FLAG_TRYLOCK);
2089 ASSERT(!(flags & XFS_ALLOC_FLAG_FREEING));
2090 goto out_no_agbp;
2091 }
2092 }
2093
2094 /* If there isn't enough total space or single-extent, reject it. */
2095 need = xfs_alloc_min_freelist(mp, pag);
2096 if (!xfs_alloc_space_available(args, need, flags))
2097 goto out_agbp_relse;
2098
2099 /*
2100 * Make the freelist shorter if it's too long.
2101 *
2102 * Note that from this point onwards, we will always release the agf and
2103 * agfl buffers on error. This handles the case where we error out and
2104 * the buffers are clean or may not have been joined to the transaction
2105 * and hence need to be released manually. If they have been joined to
2106 * the transaction, then xfs_trans_brelse() will handle them
2107 * appropriately based on the recursion count and dirty state of the
2108 * buffer.
2109 *
2110 * XXX (dgc): When we have lots of free space, does this buy us
2111 * anything other than extra overhead when we need to put more blocks
2112 * back on the free list? Maybe we should only do this when space is
2113 * getting low or the AGFL is more than half full?
2114 *
2115 * The NOSHRINK flag prevents the AGFL from being shrunk if it's too
2116 * big; the NORMAP flag prevents AGFL expand/shrink operations from
2117 * updating the rmapbt. Both flags are used in xfs_repair while we're
2118 * rebuilding the rmapbt, and neither are used by the kernel. They're
2119 * both required to ensure that rmaps are correctly recorded for the
2120 * regenerated AGFL, bnobt, and cntbt. See repair/phase5.c and
2121 * repair/rmap.c in xfsprogs for details.
2122 */
2123 memset(&targs, 0, sizeof(targs));
2124 if (flags & XFS_ALLOC_FLAG_NORMAP)
2125 xfs_rmap_skip_owner_update(&targs.oinfo);
2126 else
2127 xfs_rmap_ag_owner(&targs.oinfo, XFS_RMAP_OWN_AG);
2128 while (!(flags & XFS_ALLOC_FLAG_NOSHRINK) && pag->pagf_flcount > need) {
2129 struct xfs_buf *bp;
2130
2131 error = xfs_alloc_get_freelist(tp, agbp, &bno, 0);
2132 if (error)
2133 goto out_agbp_relse;
2134 error = xfs_free_ag_extent(tp, agbp, args->agno, bno, 1,
2135 &targs.oinfo, XFS_AG_RESV_AGFL);
2136 if (error)
2137 goto out_agbp_relse;
2138 bp = xfs_btree_get_bufs(mp, tp, args->agno, bno, 0);
2139 xfs_trans_binval(tp, bp);
2140 }
2141
2142 targs.tp = tp;
2143 targs.mp = mp;
2144 targs.agbp = agbp;
2145 targs.agno = args->agno;
2146 targs.alignment = targs.minlen = targs.prod = 1;
2147 targs.type = XFS_ALLOCTYPE_THIS_AG;
2148 targs.pag = pag;
2149 error = xfs_alloc_read_agfl(mp, tp, targs.agno, &agflbp);
2150 if (error)
2151 goto out_agbp_relse;
2152
2153 /* Make the freelist longer if it's too short. */
2154 while (pag->pagf_flcount < need) {
2155 targs.agbno = 0;
2156 targs.maxlen = need - pag->pagf_flcount;
2157 targs.resv = XFS_AG_RESV_AGFL;
2158
2159 /* Allocate as many blocks as possible at once. */
2160 error = xfs_alloc_ag_vextent(&targs);
2161 if (error)
2162 goto out_agflbp_relse;
2163
2164 /*
2165 * Stop if we run out. Won't happen if callers are obeying
2166 * the restrictions correctly. Can happen for free calls
2167 * on a completely full ag.
2168 */
2169 if (targs.agbno == NULLAGBLOCK) {
2170 if (flags & XFS_ALLOC_FLAG_FREEING)
2171 break;
2172 goto out_agflbp_relse;
2173 }
2174 /*
2175 * Put each allocated block on the list.
2176 */
2177 for (bno = targs.agbno; bno < targs.agbno + targs.len; bno++) {
2178 error = xfs_alloc_put_freelist(tp, agbp,
2179 agflbp, bno, 0);
2180 if (error)
2181 goto out_agflbp_relse;
2182 }
2183 }
2184 xfs_trans_brelse(tp, agflbp);
2185 args->agbp = agbp;
2186 return 0;
2187
2188out_agflbp_relse:
2189 xfs_trans_brelse(tp, agflbp);
2190out_agbp_relse:
2191 if (agbp)
2192 xfs_trans_brelse(tp, agbp);
2193out_no_agbp:
2194 args->agbp = NULL;
2195 return error;
2196}
2197
2198/*
2199 * Get a block from the freelist.
2200 * Returns with the buffer for the block gotten.
2201 */
2202int /* error */
2203xfs_alloc_get_freelist(
2204 xfs_trans_t *tp, /* transaction pointer */
2205 xfs_buf_t *agbp, /* buffer containing the agf structure */
2206 xfs_agblock_t *bnop, /* block address retrieved from freelist */
2207 int btreeblk) /* destination is a AGF btree */
2208{
2209 xfs_agf_t *agf; /* a.g. freespace structure */
2210 xfs_buf_t *agflbp;/* buffer for a.g. freelist structure */
2211 xfs_agblock_t bno; /* block number returned */
2212 __be32 *agfl_bno;
2213 int error;
2214 int logflags;
2215 xfs_mount_t *mp = tp->t_mountp;
2216 xfs_perag_t *pag; /* per allocation group data */
2217
2218 /*
2219 * Freelist is empty, give up.
2220 */
2221 agf = XFS_BUF_TO_AGF(agbp);
2222 if (!agf->agf_flcount) {
2223 *bnop = NULLAGBLOCK;
2224 return 0;
2225 }
2226 /*
2227 * Read the array of free blocks.
2228 */
2229 error = xfs_alloc_read_agfl(mp, tp, be32_to_cpu(agf->agf_seqno),
2230 &agflbp);
2231 if (error)
2232 return error;
2233
2234
2235 /*
2236 * Get the block number and update the data structures.
2237 */
2238 agfl_bno = XFS_BUF_TO_AGFL_BNO(mp, agflbp);
2239 bno = be32_to_cpu(agfl_bno[be32_to_cpu(agf->agf_flfirst)]);
2240 be32_add_cpu(&agf->agf_flfirst, 1);
2241 xfs_trans_brelse(tp, agflbp);
2242 if (be32_to_cpu(agf->agf_flfirst) == XFS_AGFL_SIZE(mp))
2243 agf->agf_flfirst = 0;
2244
2245 pag = xfs_perag_get(mp, be32_to_cpu(agf->agf_seqno));
2246 be32_add_cpu(&agf->agf_flcount, -1);
2247 xfs_trans_agflist_delta(tp, -1);
2248 pag->pagf_flcount--;
2249 xfs_perag_put(pag);
2250
2251 logflags = XFS_AGF_FLFIRST | XFS_AGF_FLCOUNT;
2252 if (btreeblk) {
2253 be32_add_cpu(&agf->agf_btreeblks, 1);
2254 pag->pagf_btreeblks++;
2255 logflags |= XFS_AGF_BTREEBLKS;
2256 }
2257
2258 xfs_alloc_log_agf(tp, agbp, logflags);
2259 *bnop = bno;
2260
2261 return 0;
2262}
2263
2264/*
2265 * Log the given fields from the agf structure.
2266 */
2267void
2268xfs_alloc_log_agf(
2269 xfs_trans_t *tp, /* transaction pointer */
2270 xfs_buf_t *bp, /* buffer for a.g. freelist header */
2271 int fields) /* mask of fields to be logged (XFS_AGF_...) */
2272{
2273 int first; /* first byte offset */
2274 int last; /* last byte offset */
2275 static const short offsets[] = {
2276 offsetof(xfs_agf_t, agf_magicnum),
2277 offsetof(xfs_agf_t, agf_versionnum),
2278 offsetof(xfs_agf_t, agf_seqno),
2279 offsetof(xfs_agf_t, agf_length),
2280 offsetof(xfs_agf_t, agf_roots[0]),
2281 offsetof(xfs_agf_t, agf_levels[0]),
2282 offsetof(xfs_agf_t, agf_flfirst),
2283 offsetof(xfs_agf_t, agf_fllast),
2284 offsetof(xfs_agf_t, agf_flcount),
2285 offsetof(xfs_agf_t, agf_freeblks),
2286 offsetof(xfs_agf_t, agf_longest),
2287 offsetof(xfs_agf_t, agf_btreeblks),
2288 offsetof(xfs_agf_t, agf_uuid),
2289 offsetof(xfs_agf_t, agf_rmap_blocks),
2290 offsetof(xfs_agf_t, agf_refcount_blocks),
2291 offsetof(xfs_agf_t, agf_refcount_root),
2292 offsetof(xfs_agf_t, agf_refcount_level),
2293 /* needed so that we don't log the whole rest of the structure: */
2294 offsetof(xfs_agf_t, agf_spare64),
2295 sizeof(xfs_agf_t)
2296 };
2297
2298 trace_xfs_agf(tp->t_mountp, XFS_BUF_TO_AGF(bp), fields, _RET_IP_);
2299
2300 xfs_trans_buf_set_type(tp, bp, XFS_BLFT_AGF_BUF);
2301
2302 xfs_btree_offsets(fields, offsets, XFS_AGF_NUM_BITS, &first, &last);
2303 xfs_trans_log_buf(tp, bp, (uint)first, (uint)last);
2304}
2305
2306/*
2307 * Interface for inode allocation to force the pag data to be initialized.
2308 */
2309int /* error */
2310xfs_alloc_pagf_init(
2311 xfs_mount_t *mp, /* file system mount structure */
2312 xfs_trans_t *tp, /* transaction pointer */
2313 xfs_agnumber_t agno, /* allocation group number */
2314 int flags) /* XFS_ALLOC_FLAGS_... */
2315{
2316 xfs_buf_t *bp;
2317 int error;
2318
2319 if ((error = xfs_alloc_read_agf(mp, tp, agno, flags, &bp)))
2320 return error;
2321 if (bp)
2322 xfs_trans_brelse(tp, bp);
2323 return 0;
2324}
2325
2326/*
2327 * Put the block on the freelist for the allocation group.
2328 */
2329int /* error */
2330xfs_alloc_put_freelist(
2331 xfs_trans_t *tp, /* transaction pointer */
2332 xfs_buf_t *agbp, /* buffer for a.g. freelist header */
2333 xfs_buf_t *agflbp,/* buffer for a.g. free block array */
2334 xfs_agblock_t bno, /* block being freed */
2335 int btreeblk) /* block came from a AGF btree */
2336{
2337 xfs_agf_t *agf; /* a.g. freespace structure */
2338 __be32 *blockp;/* pointer to array entry */
2339 int error;
2340 int logflags;
2341 xfs_mount_t *mp; /* mount structure */
2342 xfs_perag_t *pag; /* per allocation group data */
2343 __be32 *agfl_bno;
2344 int startoff;
2345
2346 agf = XFS_BUF_TO_AGF(agbp);
2347 mp = tp->t_mountp;
2348
2349 if (!agflbp && (error = xfs_alloc_read_agfl(mp, tp,
2350 be32_to_cpu(agf->agf_seqno), &agflbp)))
2351 return error;
2352 be32_add_cpu(&agf->agf_fllast, 1);
2353 if (be32_to_cpu(agf->agf_fllast) == XFS_AGFL_SIZE(mp))
2354 agf->agf_fllast = 0;
2355
2356 pag = xfs_perag_get(mp, be32_to_cpu(agf->agf_seqno));
2357 be32_add_cpu(&agf->agf_flcount, 1);
2358 xfs_trans_agflist_delta(tp, 1);
2359 pag->pagf_flcount++;
2360
2361 logflags = XFS_AGF_FLLAST | XFS_AGF_FLCOUNT;
2362 if (btreeblk) {
2363 be32_add_cpu(&agf->agf_btreeblks, -1);
2364 pag->pagf_btreeblks--;
2365 logflags |= XFS_AGF_BTREEBLKS;
2366 }
2367 xfs_perag_put(pag);
2368
2369 xfs_alloc_log_agf(tp, agbp, logflags);
2370
2371 ASSERT(be32_to_cpu(agf->agf_flcount) <= XFS_AGFL_SIZE(mp));
2372
2373 agfl_bno = XFS_BUF_TO_AGFL_BNO(mp, agflbp);
2374 blockp = &agfl_bno[be32_to_cpu(agf->agf_fllast)];
2375 *blockp = cpu_to_be32(bno);
2376 startoff = (char *)blockp - (char *)agflbp->b_addr;
2377
2378 xfs_alloc_log_agf(tp, agbp, logflags);
2379
2380 xfs_trans_buf_set_type(tp, agflbp, XFS_BLFT_AGFL_BUF);
2381 xfs_trans_log_buf(tp, agflbp, startoff,
2382 startoff + sizeof(xfs_agblock_t) - 1);
2383 return 0;
2384}
2385
2386static bool
2387xfs_agf_verify(
2388 struct xfs_mount *mp,
2389 struct xfs_buf *bp)
2390 {
2391 struct xfs_agf *agf = XFS_BUF_TO_AGF(bp);
2392
2393 if (xfs_sb_version_hascrc(&mp->m_sb)) {
2394 if (!uuid_equal(&agf->agf_uuid, &mp->m_sb.sb_meta_uuid))
2395 return false;
2396 if (!xfs_log_check_lsn(mp,
2397 be64_to_cpu(XFS_BUF_TO_AGF(bp)->agf_lsn)))
2398 return false;
2399 }
2400
2401 if (!(agf->agf_magicnum == cpu_to_be32(XFS_AGF_MAGIC) &&
2402 XFS_AGF_GOOD_VERSION(be32_to_cpu(agf->agf_versionnum)) &&
2403 be32_to_cpu(agf->agf_freeblks) <= be32_to_cpu(agf->agf_length) &&
2404 be32_to_cpu(agf->agf_flfirst) < XFS_AGFL_SIZE(mp) &&
2405 be32_to_cpu(agf->agf_fllast) < XFS_AGFL_SIZE(mp) &&
2406 be32_to_cpu(agf->agf_flcount) <= XFS_AGFL_SIZE(mp)))
2407 return false;
2408
2409 if (be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNO]) < 1 ||
2410 be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNT]) < 1 ||
2411 be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNO]) > XFS_BTREE_MAXLEVELS ||
2412 be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNT]) > XFS_BTREE_MAXLEVELS)
2413 return false;
2414
2415 if (xfs_sb_version_hasrmapbt(&mp->m_sb) &&
2416 (be32_to_cpu(agf->agf_levels[XFS_BTNUM_RMAP]) < 1 ||
2417 be32_to_cpu(agf->agf_levels[XFS_BTNUM_RMAP]) > XFS_BTREE_MAXLEVELS))
2418 return false;
2419
2420 /*
2421 * during growfs operations, the perag is not fully initialised,
2422 * so we can't use it for any useful checking. growfs ensures we can't
2423 * use it by using uncached buffers that don't have the perag attached
2424 * so we can detect and avoid this problem.
2425 */
2426 if (bp->b_pag && be32_to_cpu(agf->agf_seqno) != bp->b_pag->pag_agno)
2427 return false;
2428
2429 if (xfs_sb_version_haslazysbcount(&mp->m_sb) &&
2430 be32_to_cpu(agf->agf_btreeblks) > be32_to_cpu(agf->agf_length))
2431 return false;
2432
2433 if (xfs_sb_version_hasreflink(&mp->m_sb) &&
2434 (be32_to_cpu(agf->agf_refcount_level) < 1 ||
2435 be32_to_cpu(agf->agf_refcount_level) > XFS_BTREE_MAXLEVELS))
2436 return false;
2437
2438 return true;;
2439
2440}
2441
2442static void
2443xfs_agf_read_verify(
2444 struct xfs_buf *bp)
2445{
2446 struct xfs_mount *mp = bp->b_target->bt_mount;
2447
2448 if (xfs_sb_version_hascrc(&mp->m_sb) &&
2449 !xfs_buf_verify_cksum(bp, XFS_AGF_CRC_OFF))
2450 xfs_buf_ioerror(bp, -EFSBADCRC);
2451 else if (XFS_TEST_ERROR(!xfs_agf_verify(mp, bp), mp,
2452 XFS_ERRTAG_ALLOC_READ_AGF,
2453 XFS_RANDOM_ALLOC_READ_AGF))
2454 xfs_buf_ioerror(bp, -EFSCORRUPTED);
2455
2456 if (bp->b_error)
2457 xfs_verifier_error(bp);
2458}
2459
2460static void
2461xfs_agf_write_verify(
2462 struct xfs_buf *bp)
2463{
2464 struct xfs_mount *mp = bp->b_target->bt_mount;
2465 struct xfs_buf_log_item *bip = bp->b_fspriv;
2466
2467 if (!xfs_agf_verify(mp, bp)) {
2468 xfs_buf_ioerror(bp, -EFSCORRUPTED);
2469 xfs_verifier_error(bp);
2470 return;
2471 }
2472
2473 if (!xfs_sb_version_hascrc(&mp->m_sb))
2474 return;
2475
2476 if (bip)
2477 XFS_BUF_TO_AGF(bp)->agf_lsn = cpu_to_be64(bip->bli_item.li_lsn);
2478
2479 xfs_buf_update_cksum(bp, XFS_AGF_CRC_OFF);
2480}
2481
2482const struct xfs_buf_ops xfs_agf_buf_ops = {
2483 .name = "xfs_agf",
2484 .verify_read = xfs_agf_read_verify,
2485 .verify_write = xfs_agf_write_verify,
2486};
2487
2488/*
2489 * Read in the allocation group header (free/alloc section).
2490 */
2491int /* error */
2492xfs_read_agf(
2493 struct xfs_mount *mp, /* mount point structure */
2494 struct xfs_trans *tp, /* transaction pointer */
2495 xfs_agnumber_t agno, /* allocation group number */
2496 int flags, /* XFS_BUF_ */
2497 struct xfs_buf **bpp) /* buffer for the ag freelist header */
2498{
2499 int error;
2500
2501 trace_xfs_read_agf(mp, agno);
2502
2503 ASSERT(agno != NULLAGNUMBER);
2504 error = xfs_trans_read_buf(
2505 mp, tp, mp->m_ddev_targp,
2506 XFS_AG_DADDR(mp, agno, XFS_AGF_DADDR(mp)),
2507 XFS_FSS_TO_BB(mp, 1), flags, bpp, &xfs_agf_buf_ops);
2508 if (error)
2509 return error;
2510 if (!*bpp)
2511 return 0;
2512
2513 ASSERT(!(*bpp)->b_error);
2514 xfs_buf_set_ref(*bpp, XFS_AGF_REF);
2515 return 0;
2516}
2517
2518/*
2519 * Read in the allocation group header (free/alloc section).
2520 */
2521int /* error */
2522xfs_alloc_read_agf(
2523 struct xfs_mount *mp, /* mount point structure */
2524 struct xfs_trans *tp, /* transaction pointer */
2525 xfs_agnumber_t agno, /* allocation group number */
2526 int flags, /* XFS_ALLOC_FLAG_... */
2527 struct xfs_buf **bpp) /* buffer for the ag freelist header */
2528{
2529 struct xfs_agf *agf; /* ag freelist header */
2530 struct xfs_perag *pag; /* per allocation group data */
2531 int error;
2532
2533 trace_xfs_alloc_read_agf(mp, agno);
2534
2535 ASSERT(agno != NULLAGNUMBER);
2536 error = xfs_read_agf(mp, tp, agno,
2537 (flags & XFS_ALLOC_FLAG_TRYLOCK) ? XBF_TRYLOCK : 0,
2538 bpp);
2539 if (error)
2540 return error;
2541 if (!*bpp)
2542 return 0;
2543 ASSERT(!(*bpp)->b_error);
2544
2545 agf = XFS_BUF_TO_AGF(*bpp);
2546 pag = xfs_perag_get(mp, agno);
2547 if (!pag->pagf_init) {
2548 pag->pagf_freeblks = be32_to_cpu(agf->agf_freeblks);
2549 pag->pagf_btreeblks = be32_to_cpu(agf->agf_btreeblks);
2550 pag->pagf_flcount = be32_to_cpu(agf->agf_flcount);
2551 pag->pagf_longest = be32_to_cpu(agf->agf_longest);
2552 pag->pagf_levels[XFS_BTNUM_BNOi] =
2553 be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNOi]);
2554 pag->pagf_levels[XFS_BTNUM_CNTi] =
2555 be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNTi]);
2556 pag->pagf_levels[XFS_BTNUM_RMAPi] =
2557 be32_to_cpu(agf->agf_levels[XFS_BTNUM_RMAPi]);
2558 pag->pagf_refcount_level = be32_to_cpu(agf->agf_refcount_level);
2559 spin_lock_init(&pag->pagb_lock);
2560 pag->pagb_count = 0;
2561 pag->pagb_tree = RB_ROOT;
2562 pag->pagf_init = 1;
2563 }
2564#ifdef DEBUG
2565 else if (!XFS_FORCED_SHUTDOWN(mp)) {
2566 ASSERT(pag->pagf_freeblks == be32_to_cpu(agf->agf_freeblks));
2567 ASSERT(pag->pagf_btreeblks == be32_to_cpu(agf->agf_btreeblks));
2568 ASSERT(pag->pagf_flcount == be32_to_cpu(agf->agf_flcount));
2569 ASSERT(pag->pagf_longest == be32_to_cpu(agf->agf_longest));
2570 ASSERT(pag->pagf_levels[XFS_BTNUM_BNOi] ==
2571 be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNOi]));
2572 ASSERT(pag->pagf_levels[XFS_BTNUM_CNTi] ==
2573 be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNTi]));
2574 }
2575#endif
2576 xfs_perag_put(pag);
2577 return 0;
2578}
2579
2580/*
2581 * Allocate an extent (variable-size).
2582 * Depending on the allocation type, we either look in a single allocation
2583 * group or loop over the allocation groups to find the result.
2584 */
2585int /* error */
2586xfs_alloc_vextent(
2587 xfs_alloc_arg_t *args) /* allocation argument structure */
2588{
2589 xfs_agblock_t agsize; /* allocation group size */
2590 int error;
2591 int flags; /* XFS_ALLOC_FLAG_... locking flags */
2592 xfs_mount_t *mp; /* mount structure pointer */
2593 xfs_agnumber_t sagno; /* starting allocation group number */
2594 xfs_alloctype_t type; /* input allocation type */
2595 int bump_rotor = 0;
2596 xfs_agnumber_t rotorstep = xfs_rotorstep; /* inode32 agf stepper */
2597
2598 mp = args->mp;
2599 type = args->otype = args->type;
2600 args->agbno = NULLAGBLOCK;
2601 /*
2602 * Just fix this up, for the case where the last a.g. is shorter
2603 * (or there's only one a.g.) and the caller couldn't easily figure
2604 * that out (xfs_bmap_alloc).
2605 */
2606 agsize = mp->m_sb.sb_agblocks;
2607 if (args->maxlen > agsize)
2608 args->maxlen = agsize;
2609 if (args->alignment == 0)
2610 args->alignment = 1;
2611 ASSERT(XFS_FSB_TO_AGNO(mp, args->fsbno) < mp->m_sb.sb_agcount);
2612 ASSERT(XFS_FSB_TO_AGBNO(mp, args->fsbno) < agsize);
2613 ASSERT(args->minlen <= args->maxlen);
2614 ASSERT(args->minlen <= agsize);
2615 ASSERT(args->mod < args->prod);
2616 if (XFS_FSB_TO_AGNO(mp, args->fsbno) >= mp->m_sb.sb_agcount ||
2617 XFS_FSB_TO_AGBNO(mp, args->fsbno) >= agsize ||
2618 args->minlen > args->maxlen || args->minlen > agsize ||
2619 args->mod >= args->prod) {
2620 args->fsbno = NULLFSBLOCK;
2621 trace_xfs_alloc_vextent_badargs(args);
2622 return 0;
2623 }
2624
2625 switch (type) {
2626 case XFS_ALLOCTYPE_THIS_AG:
2627 case XFS_ALLOCTYPE_NEAR_BNO:
2628 case XFS_ALLOCTYPE_THIS_BNO:
2629 /*
2630 * These three force us into a single a.g.
2631 */
2632 args->agno = XFS_FSB_TO_AGNO(mp, args->fsbno);
2633 args->pag = xfs_perag_get(mp, args->agno);
2634 error = xfs_alloc_fix_freelist(args, 0);
2635 if (error) {
2636 trace_xfs_alloc_vextent_nofix(args);
2637 goto error0;
2638 }
2639 if (!args->agbp) {
2640 trace_xfs_alloc_vextent_noagbp(args);
2641 break;
2642 }
2643 args->agbno = XFS_FSB_TO_AGBNO(mp, args->fsbno);
2644 if ((error = xfs_alloc_ag_vextent(args)))
2645 goto error0;
2646 break;
2647 case XFS_ALLOCTYPE_START_BNO:
2648 /*
2649 * Try near allocation first, then anywhere-in-ag after
2650 * the first a.g. fails.
2651 */
2652 if ((args->datatype & XFS_ALLOC_INITIAL_USER_DATA) &&
2653 (mp->m_flags & XFS_MOUNT_32BITINODES)) {
2654 args->fsbno = XFS_AGB_TO_FSB(mp,
2655 ((mp->m_agfrotor / rotorstep) %
2656 mp->m_sb.sb_agcount), 0);
2657 bump_rotor = 1;
2658 }
2659 args->agbno = XFS_FSB_TO_AGBNO(mp, args->fsbno);
2660 args->type = XFS_ALLOCTYPE_NEAR_BNO;
2661 /* FALLTHROUGH */
2662 case XFS_ALLOCTYPE_ANY_AG:
2663 case XFS_ALLOCTYPE_START_AG:
2664 case XFS_ALLOCTYPE_FIRST_AG:
2665 /*
2666 * Rotate through the allocation groups looking for a winner.
2667 */
2668 if (type == XFS_ALLOCTYPE_ANY_AG) {
2669 /*
2670 * Start with the last place we left off.
2671 */
2672 args->agno = sagno = (mp->m_agfrotor / rotorstep) %
2673 mp->m_sb.sb_agcount;
2674 args->type = XFS_ALLOCTYPE_THIS_AG;
2675 flags = XFS_ALLOC_FLAG_TRYLOCK;
2676 } else if (type == XFS_ALLOCTYPE_FIRST_AG) {
2677 /*
2678 * Start with allocation group given by bno.
2679 */
2680 args->agno = XFS_FSB_TO_AGNO(mp, args->fsbno);
2681 args->type = XFS_ALLOCTYPE_THIS_AG;
2682 sagno = 0;
2683 flags = 0;
2684 } else {
2685 if (type == XFS_ALLOCTYPE_START_AG)
2686 args->type = XFS_ALLOCTYPE_THIS_AG;
2687 /*
2688 * Start with the given allocation group.
2689 */
2690 args->agno = sagno = XFS_FSB_TO_AGNO(mp, args->fsbno);
2691 flags = XFS_ALLOC_FLAG_TRYLOCK;
2692 }
2693 /*
2694 * Loop over allocation groups twice; first time with
2695 * trylock set, second time without.
2696 */
2697 for (;;) {
2698 args->pag = xfs_perag_get(mp, args->agno);
2699 error = xfs_alloc_fix_freelist(args, flags);
2700 if (error) {
2701 trace_xfs_alloc_vextent_nofix(args);
2702 goto error0;
2703 }
2704 /*
2705 * If we get a buffer back then the allocation will fly.
2706 */
2707 if (args->agbp) {
2708 if ((error = xfs_alloc_ag_vextent(args)))
2709 goto error0;
2710 break;
2711 }
2712
2713 trace_xfs_alloc_vextent_loopfailed(args);
2714
2715 /*
2716 * Didn't work, figure out the next iteration.
2717 */
2718 if (args->agno == sagno &&
2719 type == XFS_ALLOCTYPE_START_BNO)
2720 args->type = XFS_ALLOCTYPE_THIS_AG;
2721 /*
2722 * For the first allocation, we can try any AG to get
2723 * space. However, if we already have allocated a
2724 * block, we don't want to try AGs whose number is below
2725 * sagno. Otherwise, we may end up with out-of-order
2726 * locking of AGF, which might cause deadlock.
2727 */
2728 if (++(args->agno) == mp->m_sb.sb_agcount) {
2729 if (args->firstblock != NULLFSBLOCK)
2730 args->agno = sagno;
2731 else
2732 args->agno = 0;
2733 }
2734 /*
2735 * Reached the starting a.g., must either be done
2736 * or switch to non-trylock mode.
2737 */
2738 if (args->agno == sagno) {
2739 if (flags == 0) {
2740 args->agbno = NULLAGBLOCK;
2741 trace_xfs_alloc_vextent_allfailed(args);
2742 break;
2743 }
2744
2745 flags = 0;
2746 if (type == XFS_ALLOCTYPE_START_BNO) {
2747 args->agbno = XFS_FSB_TO_AGBNO(mp,
2748 args->fsbno);
2749 args->type = XFS_ALLOCTYPE_NEAR_BNO;
2750 }
2751 }
2752 xfs_perag_put(args->pag);
2753 }
2754 if (bump_rotor || (type == XFS_ALLOCTYPE_ANY_AG)) {
2755 if (args->agno == sagno)
2756 mp->m_agfrotor = (mp->m_agfrotor + 1) %
2757 (mp->m_sb.sb_agcount * rotorstep);
2758 else
2759 mp->m_agfrotor = (args->agno * rotorstep + 1) %
2760 (mp->m_sb.sb_agcount * rotorstep);
2761 }
2762 break;
2763 default:
2764 ASSERT(0);
2765 /* NOTREACHED */
2766 }
2767 if (args->agbno == NULLAGBLOCK)
2768 args->fsbno = NULLFSBLOCK;
2769 else {
2770 args->fsbno = XFS_AGB_TO_FSB(mp, args->agno, args->agbno);
2771#ifdef DEBUG
2772 ASSERT(args->len >= args->minlen);
2773 ASSERT(args->len <= args->maxlen);
2774 ASSERT(args->agbno % args->alignment == 0);
2775 XFS_AG_CHECK_DADDR(mp, XFS_FSB_TO_DADDR(mp, args->fsbno),
2776 args->len);
2777#endif
2778
2779 /* Zero the extent if we were asked to do so */
2780 if (args->datatype & XFS_ALLOC_USERDATA_ZERO) {
2781 error = xfs_zero_extent(args->ip, args->fsbno, args->len);
2782 if (error)
2783 goto error0;
2784 }
2785
2786 }
2787 xfs_perag_put(args->pag);
2788 return 0;
2789error0:
2790 xfs_perag_put(args->pag);
2791 return error;
2792}
2793
2794/* Ensure that the freelist is at full capacity. */
2795int
2796xfs_free_extent_fix_freelist(
2797 struct xfs_trans *tp,
2798 xfs_agnumber_t agno,
2799 struct xfs_buf **agbp)
2800{
2801 struct xfs_alloc_arg args;
2802 int error;
2803
2804 memset(&args, 0, sizeof(struct xfs_alloc_arg));
2805 args.tp = tp;
2806 args.mp = tp->t_mountp;
2807 args.agno = agno;
2808
2809 /*
2810 * validate that the block number is legal - the enables us to detect
2811 * and handle a silent filesystem corruption rather than crashing.
2812 */
2813 if (args.agno >= args.mp->m_sb.sb_agcount)
2814 return -EFSCORRUPTED;
2815
2816 args.pag = xfs_perag_get(args.mp, args.agno);
2817 ASSERT(args.pag);
2818
2819 error = xfs_alloc_fix_freelist(&args, XFS_ALLOC_FLAG_FREEING);
2820 if (error)
2821 goto out;
2822
2823 *agbp = args.agbp;
2824out:
2825 xfs_perag_put(args.pag);
2826 return error;
2827}
2828
2829/*
2830 * Free an extent.
2831 * Just break up the extent address and hand off to xfs_free_ag_extent
2832 * after fixing up the freelist.
2833 */
2834int /* error */
2835xfs_free_extent(
2836 struct xfs_trans *tp, /* transaction pointer */
2837 xfs_fsblock_t bno, /* starting block number of extent */
2838 xfs_extlen_t len, /* length of extent */
2839 struct xfs_owner_info *oinfo, /* extent owner */
2840 enum xfs_ag_resv_type type) /* block reservation type */
2841{
2842 struct xfs_mount *mp = tp->t_mountp;
2843 struct xfs_buf *agbp;
2844 xfs_agnumber_t agno = XFS_FSB_TO_AGNO(mp, bno);
2845 xfs_agblock_t agbno = XFS_FSB_TO_AGBNO(mp, bno);
2846 int error;
2847
2848 ASSERT(len != 0);
2849 ASSERT(type != XFS_AG_RESV_AGFL);
2850
2851 if (XFS_TEST_ERROR(false, mp,
2852 XFS_ERRTAG_FREE_EXTENT,
2853 XFS_RANDOM_FREE_EXTENT))
2854 return -EIO;
2855
2856 error = xfs_free_extent_fix_freelist(tp, agno, &agbp);
2857 if (error)
2858 return error;
2859
2860 XFS_WANT_CORRUPTED_GOTO(mp, agbno < mp->m_sb.sb_agblocks, err);
2861
2862 /* validate the extent size is legal now we have the agf locked */
2863 XFS_WANT_CORRUPTED_GOTO(mp,
2864 agbno + len <= be32_to_cpu(XFS_BUF_TO_AGF(agbp)->agf_length),
2865 err);
2866
2867 error = xfs_free_ag_extent(tp, agbp, agno, agbno, len, oinfo, type);
2868 if (error)
2869 goto err;
2870
2871 xfs_extent_busy_insert(tp, agno, agbno, len, 0);
2872 return 0;
2873
2874err:
2875 xfs_trans_brelse(tp, agbp);
2876 return error;
2877}