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