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 8881938 : xfs_agfl_size(
46 : struct xfs_mount *mp)
47 : {
48 1725308392 : unsigned int size = mp->m_sb.sb_sectsize;
49 :
50 12531055 : if (xfs_has_crc(mp))
51 1723483978 : size -= sizeof(struct xfs_agfl);
52 :
53 1725308392 : return size / sizeof(xfs_agblock_t);
54 : }
55 :
56 : unsigned int
57 127813 : xfs_refc_block(
58 : struct xfs_mount *mp)
59 : {
60 127813 : if (xfs_has_rmapbt(mp))
61 125531 : return XFS_RMAP_BLOCK(mp) + 1;
62 2282 : if (xfs_has_finobt(mp))
63 0 : return XFS_FIBT_BLOCK(mp) + 1;
64 2282 : return XFS_IBT_BLOCK(mp) + 1;
65 : }
66 :
67 : xfs_extlen_t
68 32871 : xfs_prealloc_blocks(
69 : struct xfs_mount *mp)
70 : {
71 32871 : if (xfs_has_reflink(mp))
72 32642 : return xfs_refc_block(mp) + 1;
73 229 : if (xfs_has_rmapbt(mp))
74 0 : return XFS_RMAP_BLOCK(mp) + 1;
75 229 : if (xfs_has_finobt(mp))
76 183 : return XFS_FIBT_BLOCK(mp) + 1;
77 46 : 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 32916 : xfs_alloc_set_aside(
115 : struct xfs_mount *mp)
116 : {
117 32916 : 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 22501 : xfs_alloc_ag_max_usable(
136 : struct xfs_mount *mp)
137 : {
138 22501 : unsigned int blocks;
139 :
140 22501 : blocks = XFS_BB_TO_FSB(mp, XFS_FSS_TO_BB(mp, 4)); /* ag headers */
141 22501 : blocks += XFS_ALLOCBT_AGFL_RESERVE;
142 22501 : blocks += 3; /* AGF, AGI btree root blocks */
143 22501 : if (xfs_has_finobt(mp))
144 22453 : blocks++; /* finobt root block */
145 22501 : if (xfs_has_rmapbt(mp))
146 22274 : blocks++; /* rmap root block */
147 22501 : if (xfs_has_reflink(mp))
148 22274 : blocks++; /* refcount root block */
149 :
150 22501 : 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 189961744 : 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 189961744 : int error;
164 :
165 189961744 : cur->bc_rec.a.ar_startblock = bno;
166 189961744 : cur->bc_rec.a.ar_blockcount = len;
167 189961744 : error = xfs_btree_lookup(cur, XFS_LOOKUP_EQ, stat);
168 189970485 : cur->bc_ag.abt.active = (*stat == 1);
169 189970485 : 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 19835 : 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 192922751 : int error;
184 :
185 192922751 : cur->bc_rec.a.ar_startblock = bno;
186 192922751 : cur->bc_rec.a.ar_blockcount = len;
187 19835 : error = xfs_btree_lookup(cur, XFS_LOOKUP_GE, stat);
188 192918785 : cur->bc_ag.abt.active = (*stat == 1);
189 192918785 : 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 244728589 : 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 308735764 : int error;
204 308735764 : cur->bc_rec.a.ar_startblock = bno;
205 308735764 : cur->bc_rec.a.ar_blockcount = len;
206 244728589 : error = xfs_btree_lookup(cur, XFS_LOOKUP_LE, stat);
207 308734606 : cur->bc_ag.abt.active = (*stat == 1);
208 308734606 : return error;
209 : }
210 :
211 : static inline bool
212 6878623161 : xfs_alloc_cur_active(
213 : struct xfs_btree_cur *cur)
214 : {
215 6878623161 : 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 52391424 : 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 52391424 : union xfs_btree_rec rec;
230 :
231 52391424 : rec.alloc.ar_startblock = cpu_to_be32(bno);
232 52391424 : rec.alloc.ar_blockcount = cpu_to_be32(len);
233 52391424 : return xfs_btree_update(cur, &rec);
234 : }
235 :
236 : /* Convert the ondisk btree record to its incore representation. */
237 : void
238 5266793685 : xfs_alloc_btrec_to_irec(
239 : const union xfs_btree_rec *rec,
240 : struct xfs_alloc_rec_incore *irec)
241 : {
242 5266793685 : irec->ar_startblock = be32_to_cpu(rec->alloc.ar_startblock);
243 5266793685 : irec->ar_blockcount = be32_to_cpu(rec->alloc.ar_blockcount);
244 5266793685 : }
245 :
246 : /* Simple checks for free space records. */
247 : xfs_failaddr_t
248 5271965574 : xfs_alloc_check_irec(
249 : struct xfs_btree_cur *cur,
250 : const struct xfs_alloc_rec_incore *irec)
251 : {
252 5271965574 : struct xfs_perag *pag = cur->bc_ag.pag;
253 :
254 5271965574 : if (irec->ar_blockcount == 0)
255 0 : return __this_address;
256 :
257 : /* check for valid extent range, including overflow */
258 5271965574 : 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 4018289432 : 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 4018289432 : struct xfs_alloc_rec_incore irec;
293 4018289432 : union xfs_btree_rec *rec;
294 4018289432 : xfs_failaddr_t fa;
295 4018289432 : int error;
296 :
297 4018289432 : error = xfs_btree_get_rec(cur, &rec, stat);
298 4011905361 : if (error || !(*stat))
299 : return error;
300 :
301 4014685058 : xfs_alloc_btrec_to_irec(rec, &irec);
302 4016723406 : fa = xfs_alloc_check_irec(cur, &irec);
303 4017357603 : if (fa)
304 0 : return xfs_alloc_complain_bad_rec(cur, fa, &irec);
305 :
306 4017357603 : *bno = irec.ar_startblock;
307 4017357603 : *len = irec.ar_blockcount;
308 4017357603 : 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 3304424010 : 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 3304424010 : xfs_agblock_t bno = foundbno;
325 3304424010 : xfs_extlen_t len = foundlen;
326 3304424010 : xfs_extlen_t diff;
327 3304424010 : bool busy;
328 :
329 : /* Trim busy sections out of found extent */
330 3304424010 : 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 3307702687 : if (bno < args->min_agbno && bno + len > args->min_agbno) {
337 108 : diff = args->min_agbno - bno;
338 108 : if (len > diff) {
339 108 : bno += diff;
340 108 : len -= diff;
341 : }
342 : }
343 :
344 3307702687 : if (args->alignment > 1 && len >= args->minlen) {
345 6092277 : xfs_agblock_t aligned_bno = roundup(bno, args->alignment);
346 :
347 6092277 : diff = aligned_bno - bno;
348 :
349 6092277 : *resbno = aligned_bno;
350 6092277 : *reslen = diff >= len ? 0 : len - diff;
351 : } else {
352 3301610410 : *resbno = bno;
353 3301610410 : *reslen = len;
354 : }
355 :
356 3307702687 : 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 1797805349 : 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 1797805349 : xfs_agblock_t freeend; /* end of freespace extent */
374 1797805349 : xfs_agblock_t newbno1; /* return block number */
375 1797805349 : xfs_agblock_t newbno2; /* other new block number */
376 1797805349 : xfs_extlen_t newlen1=0; /* length with newbno1 */
377 1797805349 : xfs_extlen_t newlen2=0; /* length with newbno2 */
378 1797805349 : xfs_agblock_t wantend; /* end of target extent */
379 1797805349 : bool userdata = datatype & XFS_ALLOC_USERDATA;
380 :
381 1797805349 : ASSERT(freelen >= wantlen);
382 1797805349 : freeend = freebno + freelen;
383 1797805349 : 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 1797805349 : if (freebno >= wantbno || (userdata && freeend < wantend)) {
392 1247212608 : if ((newbno1 = roundup(freebno, alignment)) >= freeend)
393 0 : newbno1 = NULLAGBLOCK;
394 550592741 : } else if (freeend >= wantend && alignment > 1) {
395 0 : newbno1 = roundup(wantbno, alignment);
396 0 : newbno2 = newbno1 - alignment;
397 0 : if (newbno1 >= freeend)
398 : newbno1 = NULLAGBLOCK;
399 : else
400 0 : newlen1 = XFS_EXTLEN_MIN(wantlen, freeend - newbno1);
401 0 : if (newbno2 < freebno)
402 : newbno2 = NULLAGBLOCK;
403 : else
404 0 : newlen2 = XFS_EXTLEN_MIN(wantlen, freeend - newbno2);
405 0 : if (newbno1 != NULLAGBLOCK && newbno2 != NULLAGBLOCK) {
406 0 : if (newlen1 < newlen2 ||
407 0 : (newlen1 == newlen2 &&
408 0 : XFS_ABSDIFF(newbno1, wantbno) >
409 0 : XFS_ABSDIFF(newbno2, wantbno)))
410 0 : newbno1 = newbno2;
411 0 : } else if (newbno2 != NULLAGBLOCK)
412 0 : newbno1 = newbno2;
413 550592741 : } else if (freeend >= wantend) {
414 : newbno1 = wantbno;
415 550024801 : } else if (alignment > 1) {
416 28265 : newbno1 = roundup(freeend - wantlen, alignment);
417 28265 : if (newbno1 > freeend - wantlen &&
418 17829 : newbno1 - alignment >= freebno)
419 : newbno1 -= alignment;
420 10436 : else if (newbno1 >= freeend)
421 0 : newbno1 = NULLAGBLOCK;
422 : } else
423 549996536 : newbno1 = freeend - wantlen;
424 1797805349 : *newbnop = newbno1;
425 1797805349 : 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 1799573843 : xfs_alloc_fix_len(
436 : xfs_alloc_arg_t *args) /* allocation argument structure */
437 : {
438 1799573843 : xfs_extlen_t k;
439 1799573843 : xfs_extlen_t rlen;
440 :
441 1799573843 : ASSERT(args->mod < args->prod);
442 1799573843 : rlen = args->len;
443 1799573843 : ASSERT(rlen >= args->minlen);
444 1799573843 : ASSERT(rlen <= args->maxlen);
445 1799573843 : if (args->prod <= 1 || rlen < args->mod || rlen == args->maxlen ||
446 13079 : (args->mod == 0 && rlen < args->prod))
447 : return;
448 22249 : k = rlen % args->prod;
449 22249 : if (k == args->mod)
450 : return;
451 17920 : if (k > args->mod)
452 8298 : rlen = rlen - (k - args->mod);
453 : else
454 9622 : rlen = rlen - args->prod + (args->mod - k);
455 : /* casts to (int) catch length underflows */
456 17920 : if ((int)rlen < (int)args->minlen)
457 : return;
458 5124 : ASSERT(rlen >= args->minlen && rlen <= args->maxlen);
459 5124 : ASSERT(rlen % args->prod == args->mod);
460 5124 : ASSERT(args->pag->pagf_freeblks + args->pag->pagf_flcount >=
461 : rlen + args->minleft);
462 5124 : 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 44876514 : 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 44876514 : int error; /* error code */
483 44876514 : int i; /* operation results */
484 44876514 : xfs_agblock_t nfbno1; /* first new free startblock */
485 44876514 : xfs_agblock_t nfbno2; /* second new free startblock */
486 44876514 : xfs_extlen_t nflen1=0; /* first new free length */
487 44876514 : xfs_extlen_t nflen2=0; /* second new free length */
488 44876514 : struct xfs_mount *mp;
489 :
490 44876514 : mp = cnt_cur->bc_mp;
491 :
492 : /*
493 : * Look up the record in the by-size tree if necessary.
494 : */
495 44876514 : if (flags & XFSA_FIXUP_CNT_OK) {
496 : #ifdef DEBUG
497 2576105 : if ((error = xfs_alloc_get_rec(cnt_cur, &nfbno1, &nflen1, &i)))
498 : return error;
499 2576100 : if (XFS_IS_CORRUPT(mp,
500 : i != 1 ||
501 : nfbno1 != fbno ||
502 : nflen1 != flen))
503 0 : return -EFSCORRUPTED;
504 : #endif
505 : } else {
506 42300409 : if ((error = xfs_alloc_lookup_eq(cnt_cur, fbno, flen, &i)))
507 : return error;
508 42300958 : 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 44877058 : if (flags & XFSA_FIXUP_BNO_OK) {
515 : #ifdef DEBUG
516 60434 : if ((error = xfs_alloc_get_rec(bno_cur, &nfbno1, &nflen1, &i)))
517 : return error;
518 60436 : if (XFS_IS_CORRUPT(mp,
519 : i != 1 ||
520 : nfbno1 != fbno ||
521 : nflen1 != flen))
522 0 : return -EFSCORRUPTED;
523 : #endif
524 : } else {
525 44816624 : if ((error = xfs_alloc_lookup_eq(bno_cur, fbno, flen, &i)))
526 : return error;
527 44817160 : if (XFS_IS_CORRUPT(mp, i != 1))
528 0 : return -EFSCORRUPTED;
529 : }
530 :
531 : #ifdef DEBUG
532 44877596 : if (bno_cur->bc_nlevels == 1 && cnt_cur->bc_nlevels == 1) {
533 33461606 : struct xfs_btree_block *bnoblock;
534 33461606 : struct xfs_btree_block *cntblock;
535 :
536 33461606 : bnoblock = XFS_BUF_TO_BLOCK(bno_cur->bc_levels[0].bp);
537 33461606 : cntblock = XFS_BUF_TO_BLOCK(cnt_cur->bc_levels[0].bp);
538 :
539 33461606 : 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 44877596 : if (rbno == fbno && rlen == flen)
552 11697877 : nfbno1 = nfbno2 = NULLAGBLOCK;
553 33179719 : else if (rbno == fbno) {
554 28699562 : nfbno1 = rbno + rlen;
555 28699562 : nflen1 = flen - rlen;
556 28699562 : nfbno2 = NULLAGBLOCK;
557 4480157 : } else if (rbno + rlen == fbno + flen) {
558 2593452 : nfbno1 = fbno;
559 2593452 : nflen1 = flen - rlen;
560 2593452 : nfbno2 = NULLAGBLOCK;
561 : } else {
562 1886705 : nfbno1 = fbno;
563 1886705 : nflen1 = rbno - fbno;
564 1886705 : nfbno2 = rbno + rlen;
565 1886705 : nflen2 = (fbno + flen) - nfbno2;
566 : }
567 : /*
568 : * Delete the entry from the by-size btree.
569 : */
570 44877596 : if ((error = xfs_btree_delete(cnt_cur, &i)))
571 : return error;
572 44877720 : if (XFS_IS_CORRUPT(mp, i != 1))
573 0 : return -EFSCORRUPTED;
574 : /*
575 : * Add new by-size btree entry(s).
576 : */
577 44877720 : if (nfbno1 != NULLAGBLOCK) {
578 33179324 : if ((error = xfs_alloc_lookup_eq(cnt_cur, nfbno1, nflen1, &i)))
579 : return error;
580 33179732 : if (XFS_IS_CORRUPT(mp, i != 0))
581 0 : return -EFSCORRUPTED;
582 33179732 : if ((error = xfs_btree_insert(cnt_cur, &i)))
583 : return error;
584 33179031 : if (XFS_IS_CORRUPT(mp, i != 1))
585 0 : return -EFSCORRUPTED;
586 : }
587 44877427 : if (nfbno2 != NULLAGBLOCK) {
588 1886702 : if ((error = xfs_alloc_lookup_eq(cnt_cur, nfbno2, nflen2, &i)))
589 : return error;
590 1886695 : if (XFS_IS_CORRUPT(mp, i != 0))
591 0 : return -EFSCORRUPTED;
592 1886695 : if ((error = xfs_btree_insert(cnt_cur, &i)))
593 : return error;
594 1886704 : if (XFS_IS_CORRUPT(mp, i != 1))
595 0 : return -EFSCORRUPTED;
596 : }
597 : /*
598 : * Fix up the by-block btree entry(s).
599 : */
600 44877429 : if (nfbno1 == NULLAGBLOCK) {
601 : /*
602 : * No remaining freespace, just delete the by-block tree entry.
603 : */
604 11697777 : if ((error = xfs_btree_delete(bno_cur, &i)))
605 : return error;
606 11698005 : 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 33179652 : if ((error = xfs_alloc_update(bno_cur, nfbno1, nflen1)))
613 : return error;
614 : }
615 44876717 : if (nfbno2 != NULLAGBLOCK) {
616 : /*
617 : * 2 resulting free entries, need to add one.
618 : */
619 1886704 : if ((error = xfs_alloc_lookup_eq(bno_cur, nfbno2, nflen2, &i)))
620 : return error;
621 1886703 : if (XFS_IS_CORRUPT(mp, i != 0))
622 0 : return -EFSCORRUPTED;
623 1886703 : if ((error = xfs_btree_insert(bno_cur, &i)))
624 : return error;
625 1886703 : 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 1274543 : xfs_agfl_verify(
652 : struct xfs_buf *bp)
653 : {
654 1274543 : struct xfs_mount *mp = bp->b_mount;
655 1274543 : struct xfs_agfl *agfl = XFS_BUF_TO_AGFL(bp);
656 1274543 : __be32 *agfl_bno = xfs_buf_to_agfl_bno(bp);
657 1274543 : int i;
658 :
659 1274543 : if (!xfs_has_crc(mp))
660 : return NULL;
661 :
662 1274539 : if (!xfs_verify_magic(bp, agfl->agfl_magicnum))
663 0 : return __this_address;
664 1274540 : 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 2543663 : if (bp->b_pag && be32_to_cpu(agfl->agfl_seqno) != bp->b_pag->pag_agno)
673 0 : return __this_address;
674 :
675 2574842701 : for (i = 0; i < xfs_agfl_size(mp); i++) {
676 1285959006 : if (be32_to_cpu(agfl_bno[i]) != NULLAGBLOCK &&
677 174347196 : be32_to_cpu(agfl_bno[i]) >= mp->m_sb.sb_agblocks)
678 0 : return __this_address;
679 : }
680 :
681 1274547 : 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 60595 : xfs_agfl_read_verify(
688 : struct xfs_buf *bp)
689 : {
690 60595 : struct xfs_mount *mp = bp->b_mount;
691 60595 : 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 60595 : if (!xfs_has_crc(mp))
700 : return;
701 :
702 60577 : if (!xfs_buf_verify_cksum(bp, XFS_AGFL_CRC_OFF))
703 128 : xfs_verifier_error(bp, -EFSBADCRC, __this_address);
704 : else {
705 60449 : fa = xfs_agfl_verify(bp);
706 60449 : if (fa)
707 0 : xfs_verifier_error(bp, -EFSCORRUPTED, fa);
708 : }
709 : }
710 :
711 : static void
712 84112 : xfs_agfl_write_verify(
713 : struct xfs_buf *bp)
714 : {
715 84112 : struct xfs_mount *mp = bp->b_mount;
716 84112 : struct xfs_buf_log_item *bip = bp->b_log_item;
717 84112 : xfs_failaddr_t fa;
718 :
719 : /* no verification of non-crc AGFLs */
720 84112 : if (!xfs_has_crc(mp))
721 : return;
722 :
723 81830 : fa = xfs_agfl_verify(bp);
724 81830 : if (fa) {
725 0 : xfs_verifier_error(bp, -EFSCORRUPTED, fa);
726 0 : return;
727 : }
728 :
729 81830 : if (bip)
730 76422 : XFS_BUF_TO_AGFL(bp)->agfl_lsn = cpu_to_be64(bip->bli_item.li_lsn);
731 :
732 81830 : 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 277007122 : xfs_alloc_read_agfl(
748 : struct xfs_perag *pag,
749 : struct xfs_trans *tp,
750 : struct xfs_buf **bpp)
751 : {
752 277007122 : struct xfs_mount *mp = pag->pag_mount;
753 277007122 : struct xfs_buf *bp;
754 277007122 : int error;
755 :
756 831021366 : error = xfs_trans_read_buf(
757 277007122 : mp, tp, mp->m_ddev_targp,
758 277007122 : XFS_AG_DADDR(mp, pag->pag_agno, XFS_AGFL_DADDR(mp)),
759 277007122 : XFS_FSS_TO_BB(mp, 1), 0, &bp, &xfs_agfl_buf_ops);
760 277007078 : if (error)
761 : return error;
762 277010898 : xfs_buf_set_ref(bp, XFS_AGFL_REF);
763 277010627 : *bpp = bp;
764 277010627 : return 0;
765 : }
766 :
767 : STATIC int
768 85850820 : xfs_alloc_update_counters(
769 : struct xfs_trans *tp,
770 : struct xfs_buf *agbp,
771 : long len)
772 : {
773 85850820 : struct xfs_agf *agf = agbp->b_addr;
774 :
775 85850820 : agbp->b_pag->pagf_freeblks += len;
776 85850820 : be32_add_cpu(&agf->agf_freeblks, len);
777 :
778 257553015 : 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 85851005 : xfs_alloc_log_agf(tp, agbp, XFS_AGF_FREEBLKS);
785 85851005 : 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 42280095 : xfs_alloc_cur_setup(
812 : struct xfs_alloc_arg *args,
813 : struct xfs_alloc_cur *acur)
814 : {
815 42280095 : int error;
816 42280095 : int i;
817 :
818 42280095 : acur->cur_len = args->maxlen;
819 42280095 : acur->rec_bno = 0;
820 42280095 : acur->rec_len = 0;
821 42280095 : acur->bno = 0;
822 42280095 : acur->len = 0;
823 42280095 : acur->diff = -1;
824 42280095 : acur->busy = false;
825 42280095 : 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 42280095 : if (!acur->cnt)
833 42241318 : acur->cnt = xfs_allocbt_init_cursor(args->mp, args->tp,
834 : args->agbp, args->pag, XFS_BTNUM_CNT);
835 42279689 : error = xfs_alloc_lookup_ge(acur->cnt, 0, args->maxlen, &i);
836 42281134 : if (error)
837 : return error;
838 :
839 : /*
840 : * Allocate the bnobt left and right search cursors.
841 : */
842 42280738 : if (!acur->bnolt)
843 42241516 : acur->bnolt = xfs_allocbt_init_cursor(args->mp, args->tp,
844 : args->agbp, args->pag, XFS_BTNUM_BNO);
845 42280585 : if (!acur->bnogt)
846 42241453 : acur->bnogt = xfs_allocbt_init_cursor(args->mp, args->tp,
847 : args->agbp, args->pag, XFS_BTNUM_BNO);
848 42280485 : return i == 1 ? 0 : -ENOSPC;
849 : }
850 :
851 : static void
852 42241108 : xfs_alloc_cur_close(
853 : struct xfs_alloc_cur *acur,
854 : bool error)
855 : {
856 42241108 : int cur_error = XFS_BTREE_NOERROR;
857 :
858 42241108 : if (error)
859 836 : cur_error = XFS_BTREE_ERROR;
860 :
861 42241108 : if (acur->cnt)
862 42241108 : xfs_btree_del_cursor(acur->cnt, cur_error);
863 42241758 : if (acur->bnolt)
864 42241362 : xfs_btree_del_cursor(acur->bnolt, cur_error);
865 42240980 : if (acur->bnogt)
866 42240584 : xfs_btree_del_cursor(acur->bnogt, cur_error);
867 42241028 : acur->cnt = acur->bnolt = acur->bnogt = NULL;
868 42241028 : }
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 3303948313 : 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 3303948313 : int error, i;
884 3303948313 : xfs_agblock_t bno, bnoa, bnew;
885 3303948313 : xfs_extlen_t len, lena, diff = -1;
886 3303948313 : bool busy;
887 3303948313 : unsigned busy_gen = 0;
888 3303948313 : bool deactivate = false;
889 3303948313 : bool isbnobt = cur->bc_btnum == XFS_BTNUM_BNO;
890 :
891 3303948313 : *new = 0;
892 :
893 3303948313 : error = xfs_alloc_get_rec(cur, &bno, &len, &i);
894 3302748254 : if (error)
895 : return error;
896 3302748254 : 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 3302748254 : if (len < args->minlen) {
904 184546132 : deactivate = !isbnobt;
905 184546132 : goto out;
906 : }
907 :
908 3118202122 : busy = xfs_alloc_compute_aligned(args, bno, len, &bnoa, &lena,
909 : &busy_gen);
910 3123379466 : acur->busy |= busy;
911 3123379466 : if (busy)
912 1451234475 : acur->busy_gen = busy_gen;
913 : /* deactivate a bnobt cursor outside of locality range */
914 3123379466 : if (bnoa < args->min_agbno || bnoa > args->max_agbno) {
915 992 : deactivate = isbnobt;
916 992 : goto out;
917 : }
918 3123378474 : if (lena < args->minlen)
919 1327854330 : goto out;
920 :
921 1795524144 : args->len = XFS_EXTLEN_MIN(lena, args->maxlen);
922 1795524144 : xfs_alloc_fix_len(args);
923 1797419693 : ASSERT(args->len >= args->minlen);
924 1797419693 : if (args->len < acur->len)
925 21473 : 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 1797398220 : diff = xfs_alloc_compute_diff(args->agbno, args->len,
932 : args->alignment, args->datatype,
933 : bnoa, lena, &bnew);
934 1798155211 : if (bnew == NULLAGBLOCK)
935 0 : goto out;
936 :
937 : /*
938 : * Deactivate a bnobt cursor with worse locality than the current best.
939 : */
940 1798155211 : if (diff > acur->diff) {
941 1314112629 : deactivate = isbnobt;
942 1314112629 : goto out;
943 : }
944 :
945 484042582 : ASSERT(args->len > acur->len ||
946 : (args->len == acur->len && diff <= acur->diff));
947 484042582 : acur->rec_bno = bno;
948 484042582 : acur->rec_len = len;
949 484042582 : acur->bno = bnew;
950 484042582 : acur->len = args->len;
951 484042582 : acur->diff = diff;
952 484042582 : *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 484042582 : if (acur->diff == 0 && acur->len == args->maxlen)
960 : deactivate = true;
961 476767504 : out:
962 2826535556 : if (deactivate)
963 12651079 : cur->bc_ag.abt.active = false;
964 3310578138 : trace_xfs_alloc_cur_check(args->mp, cur->bc_btnum, bno, len, diff,
965 3310578138 : *new);
966 3310578138 : 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 42240061 : xfs_alloc_cur_finish(
975 : struct xfs_alloc_arg *args,
976 : struct xfs_alloc_cur *acur)
977 : {
978 42240061 : struct xfs_agf __maybe_unused *agf = args->agbp->b_addr;
979 42240061 : int error;
980 :
981 42240061 : ASSERT(acur->cnt && acur->bnolt);
982 42240061 : ASSERT(acur->bno >= acur->rec_bno);
983 42240061 : ASSERT(acur->bno + acur->len <= acur->rec_bno + acur->rec_len);
984 84480122 : ASSERT(acur->rec_bno + acur->rec_len <= be32_to_cpu(agf->agf_length));
985 :
986 42240061 : error = xfs_alloc_fixup_trees(acur->cnt, acur->bnolt, acur->rec_bno,
987 : acur->rec_len, acur->bno, acur->len, 0);
988 42240934 : if (error)
989 : return error;
990 :
991 42240893 : args->agbno = acur->bno;
992 42240893 : args->len = acur->len;
993 42240893 : args->wasfromfl = 0;
994 :
995 42240893 : trace_xfs_alloc_cur(args);
996 42240893 : 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 101990381 : xfs_alloc_cntbt_iter(
1005 : struct xfs_alloc_arg *args,
1006 : struct xfs_alloc_cur *acur)
1007 : {
1008 101990381 : struct xfs_btree_cur *cur = acur->cnt;
1009 101990381 : xfs_agblock_t bno;
1010 101990381 : xfs_extlen_t len, cur_len;
1011 101990381 : int error;
1012 101990381 : int i;
1013 :
1014 101990381 : if (!xfs_alloc_cur_active(cur))
1015 : return 0;
1016 :
1017 : /* locality optimized lookup */
1018 101983892 : cur_len = acur->cur_len;
1019 101983892 : error = xfs_alloc_lookup_ge(cur, args->agbno, cur_len, &i);
1020 101978321 : if (error)
1021 : return error;
1022 101978321 : if (i == 0)
1023 : return 0;
1024 93002793 : error = xfs_alloc_get_rec(cur, &bno, &len, &i);
1025 93003904 : if (error)
1026 : return error;
1027 :
1028 : /* check the current record and update search length from it */
1029 93004733 : error = xfs_alloc_cur_check(args, acur, cur, &i);
1030 92995098 : if (error)
1031 : return error;
1032 92995098 : ASSERT(len >= acur->cur_len);
1033 92995098 : 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 92995098 : if (bno > args->agbno) {
1043 90306874 : error = xfs_btree_decrement(cur, 0, &i);
1044 90306709 : if (!error && i) {
1045 89768479 : error = xfs_alloc_get_rec(cur, &bno, &len, &i);
1046 89767912 : if (!error && i && len == acur->cur_len)
1047 24872676 : error = xfs_alloc_cur_check(args, acur, cur,
1048 : &i);
1049 : }
1050 90305741 : 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 92993965 : cur_len <<= 1;
1061 92993965 : if (!acur->len || acur->cur_len >= cur_len)
1062 65555724 : acur->cur_len++;
1063 : else
1064 27438241 : 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 53728 : 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 53728 : struct xfs_agf *agf = args->agbp->b_addr;
1083 53728 : int error = 0;
1084 53728 : xfs_agblock_t fbno = NULLAGBLOCK;
1085 53728 : xfs_extlen_t flen = 0;
1086 53728 : 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 53728 : if (ccur)
1095 53728 : error = xfs_btree_decrement(ccur, 0, &i);
1096 53728 : if (error)
1097 0 : goto error;
1098 53728 : if (i) {
1099 53728 : error = xfs_alloc_get_rec(ccur, &fbno, &flen, &i);
1100 53728 : if (error)
1101 0 : goto error;
1102 53728 : if (XFS_IS_CORRUPT(args->mp, i != 1)) {
1103 0 : error = -EFSCORRUPTED;
1104 0 : goto error;
1105 : }
1106 53728 : 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 53728 : out:
1156 : /*
1157 : * Can't do the allocation, give up.
1158 : */
1159 53728 : if (flen < args->minlen) {
1160 0 : args->agbno = NULLAGBLOCK;
1161 0 : trace_xfs_alloc_small_notenough(args);
1162 0 : flen = 0;
1163 : }
1164 53728 : *fbnop = fbno;
1165 53728 : *flenp = flen;
1166 53728 : *stat = 1;
1167 53728 : trace_xfs_alloc_small_done(args);
1168 53728 : 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 174327 : xfs_alloc_ag_vextent_exact(
1183 : xfs_alloc_arg_t *args) /* allocation argument structure */
1184 : {
1185 174327 : struct xfs_agf __maybe_unused *agf = args->agbp->b_addr;
1186 174327 : struct xfs_btree_cur *bno_cur;/* by block-number btree cursor */
1187 174327 : struct xfs_btree_cur *cnt_cur;/* by count btree cursor */
1188 174327 : int error;
1189 174327 : xfs_agblock_t fbno; /* start block of found extent */
1190 174327 : xfs_extlen_t flen; /* length of found extent */
1191 174327 : xfs_agblock_t tbno; /* start block of busy extent */
1192 174327 : xfs_extlen_t tlen; /* length of busy extent */
1193 174327 : xfs_agblock_t tend; /* end block of busy extent */
1194 174327 : int i; /* success/failure of operation */
1195 174327 : unsigned busy_gen;
1196 :
1197 174327 : ASSERT(args->alignment == 1);
1198 :
1199 : /*
1200 : * Allocate/initialize a cursor for the by-number freespace btree.
1201 : */
1202 174327 : 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 174327 : error = xfs_alloc_lookup_le(bno_cur, args->agbno, args->minlen, &i);
1211 174327 : if (error)
1212 3 : goto error0;
1213 174324 : if (!i)
1214 14425 : goto not_found;
1215 :
1216 : /*
1217 : * Grab the freespace record.
1218 : */
1219 159899 : error = xfs_alloc_get_rec(bno_cur, &fbno, &flen, &i);
1220 159899 : if (error)
1221 0 : goto error0;
1222 159899 : if (XFS_IS_CORRUPT(args->mp, i != 1)) {
1223 0 : error = -EFSCORRUPTED;
1224 0 : goto error0;
1225 : }
1226 159899 : ASSERT(fbno <= args->agbno);
1227 :
1228 : /*
1229 : * Check for overlapping busy extents.
1230 : */
1231 159899 : tbno = fbno;
1232 159899 : tlen = flen;
1233 159899 : 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 159899 : if (tbno > args->agbno)
1240 67 : goto not_found;
1241 159832 : if (tlen < args->minlen)
1242 95309 : goto not_found;
1243 64523 : tend = tbno + tlen;
1244 64523 : if (tend < args->agbno + args->minlen)
1245 4087 : 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 60436 : args->len = XFS_AGBLOCK_MIN(tend, args->agbno + args->maxlen)
1254 60436 : - args->agbno;
1255 60436 : xfs_alloc_fix_len(args);
1256 60436 : 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 60436 : cnt_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
1263 : args->pag, XFS_BTNUM_CNT);
1264 120872 : ASSERT(args->agbno + args->len <= be32_to_cpu(agf->agf_length));
1265 60436 : error = xfs_alloc_fixup_trees(cnt_cur, bno_cur, fbno, flen, args->agbno,
1266 : args->len, XFSA_FIXUP_BNO_OK);
1267 60436 : if (error) {
1268 0 : xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
1269 0 : goto error0;
1270 : }
1271 :
1272 60436 : xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
1273 60436 : xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1274 :
1275 60436 : args->wasfromfl = 0;
1276 60436 : trace_xfs_alloc_exact_done(args);
1277 60436 : return 0;
1278 :
1279 113888 : not_found:
1280 : /* Didn't find it, return null. */
1281 113888 : xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
1282 113888 : args->agbno = NULLAGBLOCK;
1283 113888 : trace_xfs_alloc_exact_notfound(args);
1284 113888 : return 0;
1285 :
1286 3 : error0:
1287 3 : xfs_btree_del_cursor(bno_cur, XFS_BTREE_ERROR);
1288 3 : trace_xfs_alloc_exact_error(args);
1289 3 : 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 256128561 : 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 256128561 : int error;
1307 256128561 : int i;
1308 :
1309 256128561 : *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 3420471255 : while (xfs_alloc_cur_active(cur) && count) {
1317 3189560163 : error = xfs_alloc_cur_check(args, acur, cur, &i);
1318 3189587240 : if (error)
1319 0 : return error;
1320 3189587240 : if (i == 1) {
1321 467865108 : *stat = 1;
1322 467865108 : if (find_one)
1323 : break;
1324 : }
1325 3170092914 : if (!xfs_alloc_cur_active(cur))
1326 : break;
1327 :
1328 3161201054 : if (increment)
1329 2766838938 : error = xfs_btree_increment(cur, 0, &i);
1330 : else
1331 394362116 : error = xfs_btree_decrement(cur, 0, &i);
1332 3164342699 : if (error)
1333 5 : return error;
1334 3164342694 : if (i == 0)
1335 18749375 : cur->bc_ag.abt.active = false;
1336 :
1337 3164342694 : if (count > 0)
1338 194591730 : 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 22854641 : xfs_alloc_ag_vextent_locality(
1350 : struct xfs_alloc_arg *args,
1351 : struct xfs_alloc_cur *acur,
1352 : int *stat)
1353 : {
1354 22854641 : struct xfs_btree_cur *fbcur = NULL;
1355 22854641 : int error;
1356 22854641 : int i;
1357 22854641 : bool fbinc;
1358 :
1359 22854641 : ASSERT(acur->len == 0);
1360 :
1361 22854641 : *stat = 0;
1362 :
1363 22854641 : error = xfs_alloc_lookup_ge(acur->cnt, args->agbno, acur->cur_len, &i);
1364 22854782 : if (error)
1365 : return error;
1366 22854646 : error = xfs_alloc_lookup_le(acur->bnolt, args->agbno, 0, &i);
1367 22854846 : if (error)
1368 : return error;
1369 22854677 : error = xfs_alloc_lookup_ge(acur->bnogt, args->agbno, 0, &i);
1370 22854703 : 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 14055771 : while (xfs_alloc_cur_active(acur->bnolt) ||
1396 115855954 : xfs_alloc_cur_active(acur->bnogt) ||
1397 15121 : xfs_alloc_cur_active(acur->cnt)) {
1398 :
1399 115839018 : 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 115833321 : error = xfs_alloc_walk_iter(args, acur, acur->bnolt, false,
1406 : true, 1, &i);
1407 115854906 : if (error)
1408 1 : return error;
1409 115854905 : if (i == 1) {
1410 8840822 : trace_xfs_alloc_cur_left(args);
1411 8840839 : fbcur = acur->bnogt;
1412 8840839 : fbinc = true;
1413 8840839 : break;
1414 : }
1415 107014083 : error = xfs_alloc_walk_iter(args, acur, acur->bnogt, true, true,
1416 : 1, &i);
1417 107019473 : if (error)
1418 0 : return error;
1419 107019473 : if (i == 1) {
1420 5026329 : trace_xfs_alloc_cur_right(args);
1421 5026341 : fbcur = acur->bnolt;
1422 5026341 : fbinc = false;
1423 5026341 : 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 101993144 : error = xfs_alloc_cntbt_iter(args, acur);
1431 101975701 : if (error)
1432 0 : return error;
1433 101975701 : if (!xfs_alloc_cur_active(acur->cnt)) {
1434 8987444 : trace_xfs_alloc_cur_lookup_done(args);
1435 8987444 : 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 22854621 : if (!xfs_alloc_cur_active(acur->cnt) && !acur->len && !acur->busy) {
1445 9043 : error = xfs_btree_decrement(acur->cnt, 0, &i);
1446 9043 : if (error)
1447 : return error;
1448 9043 : if (i) {
1449 9043 : acur->cnt->bc_ag.abt.active = true;
1450 9043 : fbcur = acur->cnt;
1451 9043 : 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 22854442 : if (fbcur) {
1460 13876183 : error = xfs_alloc_walk_iter(args, acur, fbcur, fbinc, true, -1,
1461 : &i);
1462 13876290 : if (error)
1463 : return error;
1464 : }
1465 :
1466 22854545 : if (acur->len)
1467 22815215 : *stat = 1;
1468 :
1469 : return 0;
1470 : }
1471 :
1472 : /* Check the last block of the cnt btree for allocations. */
1473 : static int
1474 38923955 : 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 38923955 : int error;
1482 38923955 : int i;
1483 :
1484 : #ifdef DEBUG
1485 : /* Randomly don't execute the first algorithm. */
1486 38923955 : 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 19461301 : if (*len || args->alignment > 1) {
1497 136028 : acur->cnt->bc_levels[0].ptr = 1;
1498 13195974 : do {
1499 13195974 : error = xfs_alloc_get_rec(acur->cnt, bno, len, &i);
1500 13195970 : if (error)
1501 0 : return error;
1502 13195970 : if (XFS_IS_CORRUPT(args->mp, i != 1))
1503 0 : return -EFSCORRUPTED;
1504 13195970 : if (*len >= args->minlen)
1505 : break;
1506 13059942 : error = xfs_btree_increment(acur->cnt, 0, &i);
1507 13059946 : if (error)
1508 0 : return error;
1509 13059946 : } while (i);
1510 136028 : ASSERT(*len >= args->minlen);
1511 136028 : if (!i)
1512 : return 0;
1513 : }
1514 :
1515 19461301 : error = xfs_alloc_walk_iter(args, acur, acur->cnt, true, false, -1, &i);
1516 19461261 : 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 19461261 : if (acur->len == 0)
1524 : return 0;
1525 :
1526 19426213 : trace_xfs_alloc_near_first(args);
1527 19426217 : *allocated = true;
1528 19426217 : 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 42241208 : xfs_alloc_ag_vextent_near(
1539 : struct xfs_alloc_arg *args,
1540 : uint32_t alloc_flags)
1541 : {
1542 42241208 : struct xfs_alloc_cur acur = {};
1543 42241208 : int error; /* error code */
1544 42241208 : int i; /* result code, temporary */
1545 42241208 : xfs_agblock_t bno;
1546 42241208 : xfs_extlen_t len;
1547 :
1548 : /* handle uninitialized agbno range so caller doesn't have to */
1549 42241208 : if (!args->min_agbno && !args->max_agbno)
1550 42064481 : args->max_agbno = args->mp->m_sb.sb_agblocks - 1;
1551 42241208 : ASSERT(args->min_agbno <= args->max_agbno);
1552 :
1553 : /* clamp agbno to the range if it's outside */
1554 42241208 : if (args->agbno < args->min_agbno)
1555 59718 : args->agbno = args->min_agbno;
1556 42241208 : 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 42241208 : alloc_flags |= XFS_ALLOC_FLAG_TRYFLUSH;
1561 42280537 : restart:
1562 42280537 : 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 42280537 : error = xfs_alloc_cur_setup(args, &acur);
1570 42280870 : if (error == -ENOSPC) {
1571 36674 : error = xfs_alloc_ag_vextent_small(args, acur.cnt, &bno,
1572 : &len, &i);
1573 36674 : if (error)
1574 0 : goto out;
1575 36674 : if (i == 0 || len == 0) {
1576 0 : trace_xfs_alloc_near_noentry(args);
1577 0 : goto out;
1578 : }
1579 36674 : ASSERT(i == 1);
1580 42244196 : } else if (error) {
1581 396 : 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 42280474 : if (xfs_btree_islastblock(acur.cnt, 0)) {
1593 38923968 : bool allocated = false;
1594 :
1595 38923968 : error = xfs_alloc_ag_vextent_lastblock(args, &acur, &bno, &len,
1596 : &allocated);
1597 38923952 : if (error)
1598 0 : goto out;
1599 38923952 : if (allocated)
1600 19426129 : goto alloc_finish;
1601 : }
1602 :
1603 : /*
1604 : * Second algorithm. Combined cntbt and bnobt search to find ideal
1605 : * locality.
1606 : */
1607 22854024 : error = xfs_alloc_ag_vextent_locality(args, &acur, &i);
1608 22854626 : if (error)
1609 171 : goto out;
1610 :
1611 : /*
1612 : * If we couldn't get anything, give up.
1613 : */
1614 22854455 : if (!acur.len) {
1615 39330 : 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 39330 : trace_xfs_alloc_near_busy(args);
1624 39330 : error = xfs_extent_busy_flush(args->tp, args->pag,
1625 : acur.busy_gen, alloc_flags);
1626 39330 : if (error)
1627 1 : goto out;
1628 :
1629 39329 : alloc_flags &= ~XFS_ALLOC_FLAG_TRYFLUSH;
1630 39329 : goto restart;
1631 : }
1632 0 : trace_xfs_alloc_size_neither(args);
1633 0 : args->agbno = NULLAGBLOCK;
1634 0 : goto out;
1635 : }
1636 :
1637 22815125 : alloc_finish:
1638 : /* fix up btrees on a successful allocation */
1639 42241254 : error = xfs_alloc_cur_finish(args, &acur);
1640 :
1641 42241605 : out:
1642 42241605 : xfs_alloc_cur_close(&acur, error);
1643 42241873 : 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 2586264 : xfs_alloc_ag_vextent_size(
1654 : struct xfs_alloc_arg *args,
1655 : uint32_t alloc_flags)
1656 : {
1657 2586264 : struct xfs_agf *agf = args->agbp->b_addr;
1658 2586264 : struct xfs_btree_cur *bno_cur;
1659 2586264 : struct xfs_btree_cur *cnt_cur;
1660 2586264 : xfs_agblock_t fbno; /* start of found freespace */
1661 2586264 : xfs_extlen_t flen; /* length of found freespace */
1662 2586264 : xfs_agblock_t rbno; /* returned block number */
1663 2586264 : xfs_extlen_t rlen; /* length of returned extent */
1664 2586264 : bool busy;
1665 2586264 : unsigned busy_gen;
1666 2586264 : int error;
1667 2586264 : int i;
1668 :
1669 : /* Retry once quickly if we find busy extents before blocking. */
1670 2586264 : alloc_flags |= XFS_ALLOC_FLAG_TRYFLUSH;
1671 : restart:
1672 : /*
1673 : * Allocate and initialize a cursor for the by-size btree.
1674 : */
1675 2592928 : cnt_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
1676 : args->pag, XFS_BTNUM_CNT);
1677 2592924 : bno_cur = NULL;
1678 :
1679 : /*
1680 : * Look for an entry >= maxlen+alignment-1 blocks.
1681 : */
1682 2592924 : if ((error = xfs_alloc_lookup_ge(cnt_cur, 0,
1683 2592924 : args->maxlen + args->alignment - 1, &i)))
1684 66 : 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 2592858 : if (!i) {
1694 17054 : error = xfs_alloc_ag_vextent_small(args, cnt_cur,
1695 : &fbno, &flen, &i);
1696 17054 : if (error)
1697 0 : goto error0;
1698 17054 : 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 17054 : ASSERT(i == 1);
1704 17054 : 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 364648044 : for (;;) {
1711 183611924 : error = xfs_alloc_get_rec(cnt_cur, &fbno, &flen, &i);
1712 183606594 : if (error)
1713 0 : goto error0;
1714 183606594 : if (XFS_IS_CORRUPT(args->mp, i != 1)) {
1715 0 : error = -EFSCORRUPTED;
1716 0 : goto error0;
1717 : }
1718 :
1719 183606594 : busy = xfs_alloc_compute_aligned(args, fbno, flen,
1720 : &rbno, &rlen, &busy_gen);
1721 :
1722 183606012 : if (rlen >= args->maxlen)
1723 : break;
1724 :
1725 181036751 : error = xfs_btree_increment(cnt_cur, 0, &i);
1726 181042662 : if (error)
1727 0 : goto error0;
1728 181042662 : if (i)
1729 181036120 : 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 6542 : trace_xfs_alloc_size_busy(args);
1739 6542 : error = xfs_extent_busy_flush(args->tp, args->pag,
1740 : busy_gen, alloc_flags);
1741 6542 : if (error)
1742 1 : goto error0;
1743 :
1744 6541 : alloc_flags &= ~XFS_ALLOC_FLAG_TRYFLUSH;
1745 6541 : xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1746 6541 : 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 2586304 : rlen = XFS_EXTLEN_MIN(args->maxlen, rlen);
1757 2586304 : 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 2586304 : if (rlen < args->maxlen) {
1765 17054 : xfs_agblock_t bestfbno;
1766 17054 : xfs_extlen_t bestflen;
1767 17054 : xfs_agblock_t bestrbno;
1768 17054 : xfs_extlen_t bestrlen;
1769 :
1770 17054 : bestrlen = rlen;
1771 17054 : bestrbno = rbno;
1772 17054 : bestflen = flen;
1773 17054 : bestfbno = fbno;
1774 3312109 : for (;;) {
1775 3312109 : if ((error = xfs_btree_decrement(cnt_cur, 0, &i)))
1776 0 : goto error0;
1777 3312109 : if (i == 0)
1778 : break;
1779 3311962 : if ((error = xfs_alloc_get_rec(cnt_cur, &fbno, &flen,
1780 : &i)))
1781 0 : goto error0;
1782 3311962 : if (XFS_IS_CORRUPT(args->mp, i != 1)) {
1783 0 : error = -EFSCORRUPTED;
1784 0 : goto error0;
1785 : }
1786 3311962 : if (flen < bestrlen)
1787 : break;
1788 3295055 : busy = xfs_alloc_compute_aligned(args, fbno, flen,
1789 : &rbno, &rlen, &busy_gen);
1790 3295055 : rlen = XFS_EXTLEN_MIN(args->maxlen, rlen);
1791 3295055 : 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 3295055 : if (rlen > bestrlen) {
1799 10231 : bestrlen = rlen;
1800 10231 : bestrbno = rbno;
1801 10231 : bestflen = flen;
1802 10231 : bestfbno = fbno;
1803 10231 : if (rlen == args->maxlen)
1804 : break;
1805 : }
1806 : }
1807 17054 : if ((error = xfs_alloc_lookup_eq(cnt_cur, bestfbno, bestflen,
1808 : &i)))
1809 0 : goto error0;
1810 17054 : if (XFS_IS_CORRUPT(args->mp, i != 1)) {
1811 0 : error = -EFSCORRUPTED;
1812 0 : goto error0;
1813 : }
1814 17054 : rlen = bestrlen;
1815 17054 : rbno = bestrbno;
1816 17054 : flen = bestflen;
1817 17054 : fbno = bestfbno;
1818 : }
1819 2586304 : args->wasfromfl = 0;
1820 : /*
1821 : * Fix up the length.
1822 : */
1823 2586304 : args->len = rlen;
1824 2586304 : if (rlen < args->minlen) {
1825 10194 : 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 123 : trace_xfs_alloc_size_busy(args);
1834 123 : error = xfs_extent_busy_flush(args->tp, args->pag,
1835 : busy_gen, alloc_flags);
1836 123 : if (error)
1837 0 : goto error0;
1838 :
1839 123 : alloc_flags &= ~XFS_ALLOC_FLAG_TRYFLUSH;
1840 123 : xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1841 123 : goto restart;
1842 : }
1843 10071 : goto out_nominleft;
1844 : }
1845 2576110 : xfs_alloc_fix_len(args);
1846 :
1847 2576114 : rlen = args->len;
1848 2576114 : 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 2576114 : bno_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
1856 : args->pag, XFS_BTNUM_BNO);
1857 2576105 : if ((error = xfs_alloc_fixup_trees(cnt_cur, bno_cur, fbno, flen,
1858 : rbno, rlen, XFSA_FIXUP_CNT_OK)))
1859 44 : goto error0;
1860 2576047 : xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1861 2576075 : xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
1862 2576065 : cnt_cur = bno_cur = NULL;
1863 2576065 : args->len = rlen;
1864 2576065 : args->agbno = rbno;
1865 5152130 : 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 2576065 : trace_xfs_alloc_size_done(args);
1872 2576065 : return 0;
1873 :
1874 111 : error0:
1875 111 : trace_xfs_alloc_size_error(args);
1876 111 : if (cnt_cur)
1877 111 : xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
1878 111 : if (bno_cur)
1879 44 : xfs_btree_del_cursor(bno_cur, XFS_BTREE_ERROR);
1880 : return error;
1881 :
1882 : out_nominleft:
1883 10071 : xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
1884 10071 : trace_xfs_alloc_size_nominleft(args);
1885 10071 : args->agbno = NULLAGBLOCK;
1886 10071 : return 0;
1887 : }
1888 :
1889 : /*
1890 : * Free the extent starting at agno/bno for length.
1891 : */
1892 : STATIC int
1893 40978418 : 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 40978418 : struct xfs_mount *mp;
1903 40978418 : struct xfs_btree_cur *bno_cur;
1904 40978418 : struct xfs_btree_cur *cnt_cur;
1905 40978418 : xfs_agblock_t gtbno; /* start of right neighbor */
1906 40978418 : xfs_extlen_t gtlen; /* length of right neighbor */
1907 40978418 : xfs_agblock_t ltbno; /* start of left neighbor */
1908 40978418 : xfs_extlen_t ltlen; /* length of left neighbor */
1909 40978418 : xfs_agblock_t nbno; /* new starting block of freesp */
1910 40978418 : xfs_extlen_t nlen; /* new length of freespace */
1911 40978418 : int haveleft; /* have a left neighbor */
1912 40978418 : int haveright; /* have a right neighbor */
1913 40978418 : int i;
1914 40978418 : int error;
1915 40978418 : struct xfs_perag *pag = agbp->b_pag;
1916 :
1917 40978418 : bno_cur = cnt_cur = NULL;
1918 40978418 : mp = tp->t_mountp;
1919 :
1920 40978418 : if (!xfs_rmap_should_skip_owner_update(oinfo)) {
1921 548482 : error = xfs_rmap_free(tp, agbp, pag, bno, len, oinfo);
1922 548481 : if (error)
1923 17 : goto error0;
1924 : }
1925 :
1926 : /*
1927 : * Allocate and initialize a cursor for the by-block btree.
1928 : */
1929 40978400 : 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 40978202 : if ((error = xfs_alloc_lookup_le(bno_cur, bno, len, &haveleft)))
1935 180 : goto error0;
1936 40978130 : if (haveleft) {
1937 : /*
1938 : * There is a block to our left.
1939 : */
1940 40255689 : if ((error = xfs_alloc_get_rec(bno_cur, <bno, <len, &i)))
1941 0 : goto error0;
1942 40255676 : 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 40255676 : if (ltbno + ltlen < bno)
1950 29765965 : 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 10489711 : 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 40978117 : if ((error = xfs_btree_increment(bno_cur, 0, &haveright)))
1968 0 : goto error0;
1969 40978084 : if (haveright) {
1970 : /*
1971 : * There is a block to our right.
1972 : */
1973 40908671 : if ((error = xfs_alloc_get_rec(bno_cur, >bno, >len, &i)))
1974 0 : goto error0;
1975 40908754 : 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 40908754 : if (bno + len < gtbno)
1983 26482171 : 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 14426583 : 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 40978167 : 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 40978176 : if (haveleft && haveright) {
2005 : /*
2006 : * Delete the old by-size entry on the left.
2007 : */
2008 5704100 : if ((error = xfs_alloc_lookup_eq(cnt_cur, ltbno, ltlen, &i)))
2009 15 : goto error0;
2010 5704088 : if (XFS_IS_CORRUPT(mp, i != 1)) {
2011 0 : error = -EFSCORRUPTED;
2012 0 : goto error0;
2013 : }
2014 5704088 : if ((error = xfs_btree_delete(cnt_cur, &i)))
2015 0 : goto error0;
2016 5704085 : 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 5704085 : if ((error = xfs_alloc_lookup_eq(cnt_cur, gtbno, gtlen, &i)))
2024 6 : goto error0;
2025 5704081 : if (XFS_IS_CORRUPT(mp, i != 1)) {
2026 0 : error = -EFSCORRUPTED;
2027 0 : goto error0;
2028 : }
2029 5704081 : if ((error = xfs_btree_delete(cnt_cur, &i)))
2030 0 : goto error0;
2031 5704080 : 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 5704080 : if ((error = xfs_btree_delete(bno_cur, &i)))
2039 0 : goto error0;
2040 5704081 : 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 5704081 : if ((error = xfs_btree_decrement(bno_cur, 0, &i)))
2048 0 : goto error0;
2049 5704075 : 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 5704075 : xfs_agblock_t xxbno;
2060 5704075 : xfs_extlen_t xxlen;
2061 :
2062 5704075 : if ((error = xfs_alloc_get_rec(bno_cur, &xxbno, &xxlen,
2063 : &i)))
2064 0 : goto error0;
2065 5704078 : 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 5704078 : nbno = ltbno;
2078 5704078 : nlen = len + ltlen + gtlen;
2079 5704078 : 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 35274076 : else if (haveleft) {
2087 : /*
2088 : * Delete the old by-size entry on the left.
2089 : */
2090 4785615 : if ((error = xfs_alloc_lookup_eq(cnt_cur, ltbno, ltlen, &i)))
2091 4 : goto error0;
2092 4785610 : if (XFS_IS_CORRUPT(mp, i != 1)) {
2093 0 : error = -EFSCORRUPTED;
2094 0 : goto error0;
2095 : }
2096 4785610 : if ((error = xfs_btree_delete(cnt_cur, &i)))
2097 0 : goto error0;
2098 4785611 : 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 4785611 : if ((error = xfs_btree_decrement(bno_cur, 0, &i)))
2107 0 : goto error0;
2108 4785610 : if (XFS_IS_CORRUPT(mp, i != 1)) {
2109 0 : error = -EFSCORRUPTED;
2110 0 : goto error0;
2111 : }
2112 4785610 : nbno = ltbno;
2113 4785610 : nlen = len + ltlen;
2114 4785610 : 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 30488461 : else if (haveright) {
2122 : /*
2123 : * Delete the old by-size entry on the right.
2124 : */
2125 8722501 : if ((error = xfs_alloc_lookup_eq(cnt_cur, gtbno, gtlen, &i)))
2126 13 : goto error0;
2127 8722498 : if (XFS_IS_CORRUPT(mp, i != 1)) {
2128 0 : error = -EFSCORRUPTED;
2129 0 : goto error0;
2130 : }
2131 8722498 : if ((error = xfs_btree_delete(cnt_cur, &i)))
2132 0 : goto error0;
2133 8722487 : 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 8722487 : nbno = bno;
2142 8722487 : nlen = len + gtlen;
2143 8722487 : 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 21765960 : nbno = bno;
2152 21765960 : nlen = len;
2153 21765960 : if ((error = xfs_btree_insert(bno_cur, &i)))
2154 0 : goto error0;
2155 21765984 : if (XFS_IS_CORRUPT(mp, i != 1)) {
2156 0 : error = -EFSCORRUPTED;
2157 0 : goto error0;
2158 : }
2159 : }
2160 40978174 : xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
2161 40978050 : bno_cur = NULL;
2162 : /*
2163 : * In all cases we need to insert the new freespace in the by-size tree.
2164 : */
2165 40978050 : if ((error = xfs_alloc_lookup_eq(cnt_cur, nbno, nlen, &i)))
2166 36 : goto error0;
2167 40977980 : if (XFS_IS_CORRUPT(mp, i != 0)) {
2168 0 : error = -EFSCORRUPTED;
2169 0 : goto error0;
2170 : }
2171 40977980 : if ((error = xfs_btree_insert(cnt_cur, &i)))
2172 0 : goto error0;
2173 40978159 : if (XFS_IS_CORRUPT(mp, i != 1)) {
2174 0 : error = -EFSCORRUPTED;
2175 0 : goto error0;
2176 : }
2177 40978159 : xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
2178 40978162 : cnt_cur = NULL;
2179 :
2180 : /*
2181 : * Update the freespace totals in the ag and superblock.
2182 : */
2183 40978162 : error = xfs_alloc_update_counters(tp, agbp, len);
2184 40978141 : xfs_ag_resv_free_extent(agbp->b_pag, type, tp, len);
2185 40977846 : if (error)
2186 0 : goto error0;
2187 :
2188 40977846 : XFS_STATS_INC(mp, xs_freex);
2189 40978006 : XFS_STATS_ADD(mp, xs_freeb, len);
2190 :
2191 40977895 : trace_xfs_free_extent(mp, agno, bno, len, type, haveleft, haveright);
2192 :
2193 40977895 : return 0;
2194 :
2195 271 : error0:
2196 271 : trace_xfs_free_extent(mp, agno, bno, len, type, -1, -1);
2197 271 : if (bno_cur)
2198 218 : xfs_btree_del_cursor(bno_cur, XFS_BTREE_ERROR);
2199 271 : if (cnt_cur)
2200 74 : 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 22495 : xfs_alloc_compute_maxlevels(
2214 : xfs_mount_t *mp) /* file system mount structure */
2215 : {
2216 44990 : mp->m_alloc_maxlevels = xfs_btree_compute_maxlevels(mp->m_alloc_mnr,
2217 22495 : (mp->m_sb.sb_agblocks + 1) / 2);
2218 22495 : ASSERT(mp->m_alloc_maxlevels <= xfs_allocbt_maxlevels_ondisk());
2219 22495 : }
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 169736546 : xfs_alloc_longest_free_extent(
2229 : struct xfs_perag *pag,
2230 : xfs_extlen_t need,
2231 : xfs_extlen_t reserved)
2232 : {
2233 169736546 : 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 169736546 : if (need > pag->pagf_flcount)
2240 250666 : 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 169736546 : if (pag->pagf_freeblks - pag->pagf_longest < reserved)
2248 138950053 : 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 169736546 : if (pag->pagf_longest > delta)
2255 169703590 : 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 32956 : 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 629340778 : xfs_alloc_min_freelist(
2268 : struct xfs_mount *mp,
2269 : struct xfs_perag *pag)
2270 : {
2271 : /* AG btrees have at least 1 level. */
2272 629340778 : static const uint8_t fake_levels[XFS_BTNUM_AGF] = {1, 1, 1};
2273 629340778 : const uint8_t *levels = pag ? pag->pagf_levels : fake_levels;
2274 629340778 : unsigned int min_free;
2275 :
2276 629340778 : ASSERT(mp->m_alloc_maxlevels > 0);
2277 :
2278 : /* space needed by-bno freespace btree */
2279 629340778 : min_free = min_t(unsigned int, levels[XFS_BTNUM_BNOi] + 1,
2280 : mp->m_alloc_maxlevels);
2281 : /* space needed by-size freespace btree */
2282 629340778 : 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 629340778 : if (xfs_has_rmapbt(mp))
2286 582722959 : min_free += min_t(unsigned int, levels[XFS_BTNUM_RMAPi] + 1,
2287 : mp->m_rmap_maxlevels);
2288 :
2289 629340778 : 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 585793383 : xfs_alloc_space_available(
2300 : struct xfs_alloc_arg *args,
2301 : xfs_extlen_t min_free,
2302 : int flags)
2303 : {
2304 585793383 : struct xfs_perag *pag = args->pag;
2305 585793383 : xfs_extlen_t alloc_len, longest;
2306 585793383 : xfs_extlen_t reservation; /* blocks that are still reserved */
2307 585793383 : int available;
2308 585793383 : xfs_extlen_t agflcount;
2309 :
2310 585793383 : if (flags & XFS_ALLOC_FLAG_FREEING)
2311 : return true;
2312 :
2313 126139127 : reservation = xfs_ag_resv_needed(pag, args->resv);
2314 :
2315 : /* do we have enough contiguous free space for the allocation? */
2316 126138835 : alloc_len = args->minlen + (args->alignment - 1) + args->minalignslop;
2317 126138835 : longest = xfs_alloc_longest_free_extent(pag, min_free, reservation);
2318 126138835 : 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 111636455 : agflcount = min_t(xfs_extlen_t, pag->pagf_flcount, min_free);
2327 111636455 : available = (int)(pag->pagf_freeblks + agflcount -
2328 111636455 : reservation - min_free - args->minleft);
2329 111636455 : 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 91970356 : if (available < (int)args->maxlen && !(flags & XFS_ALLOC_FLAG_CHECK)) {
2337 16908 : args->maxlen = available;
2338 16908 : ASSERT(args->maxlen > 0);
2339 16908 : ASSERT(args->maxlen >= args->minlen);
2340 : }
2341 :
2342 : return true;
2343 : }
2344 :
2345 : int
2346 154920 : 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 154920 : int error;
2354 154920 : struct xfs_buf *bp;
2355 :
2356 154920 : error = xfs_free_ag_extent(tp, agbp, agno, agbno, 1, oinfo,
2357 : XFS_AG_RESV_AGFL);
2358 154920 : if (error)
2359 : return error;
2360 :
2361 309822 : error = xfs_trans_get_buf(tp, tp->t_mountp->m_ddev_targp,
2362 154911 : XFS_AGB_TO_DADDR(tp->t_mountp, agno, agbno),
2363 154911 : tp->t_mountp->m_bsize, 0, &bp);
2364 154911 : if (error)
2365 : return error;
2366 154911 : xfs_trans_binval(tp, bp);
2367 :
2368 154911 : 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 124400 : xfs_agfl_needs_reset(
2388 : struct xfs_mount *mp,
2389 : struct xfs_agf *agf)
2390 : {
2391 124400 : uint32_t f = be32_to_cpu(agf->agf_flfirst);
2392 124400 : uint32_t l = be32_to_cpu(agf->agf_fllast);
2393 124400 : uint32_t c = be32_to_cpu(agf->agf_flcount);
2394 124400 : int agfl_size = xfs_agfl_size(mp);
2395 124400 : 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 124400 : if (f >= agfl_size || l >= agfl_size)
2403 : return true;
2404 124400 : 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 124400 : if (c && l >= f)
2412 114129 : active = l - f + 1;
2413 10271 : else if (c)
2414 38 : active = agfl_size - f + l + 1;
2415 : else
2416 : active = 0;
2417 :
2418 124400 : 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 4 : xfs_agfl_reset(
2433 : struct xfs_trans *tp,
2434 : struct xfs_buf *agbp,
2435 : struct xfs_perag *pag)
2436 : {
2437 4 : struct xfs_mount *mp = tp->t_mountp;
2438 4 : struct xfs_agf *agf = agbp->b_addr;
2439 :
2440 8 : ASSERT(xfs_perag_agfl_needs_reset(pag));
2441 4 : trace_xfs_agfl_reset(mp, agf, 0, _RET_IP_);
2442 :
2443 4 : 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 4 : agf->agf_flfirst = 0;
2449 8 : agf->agf_fllast = cpu_to_be32(xfs_agfl_size(mp) - 1);
2450 4 : agf->agf_flcount = 0;
2451 4 : xfs_alloc_log_agf(tp, agbp, XFS_AGF_FLFIRST | XFS_AGF_FLLAST |
2452 : XFS_AGF_FLCOUNT);
2453 :
2454 4 : pag->pagf_flcount = 0;
2455 4 : clear_bit(XFS_AGSTATE_AGFL_NEEDS_RESET, &pag->pag_opstate);
2456 4 : }
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 154926 : 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 154926 : struct xfs_mount *mp = tp->t_mountp;
2477 154926 : struct xfs_extent_free_item *xefi;
2478 154926 : xfs_fsblock_t fsbno = XFS_AGB_TO_FSB(mp, agno, agbno);
2479 :
2480 154926 : ASSERT(xfs_extfree_item_cache != NULL);
2481 154926 : ASSERT(oinfo != NULL);
2482 :
2483 154926 : if (XFS_IS_CORRUPT(mp, !xfs_verify_fsbno(mp, fsbno)))
2484 0 : return -EFSCORRUPTED;
2485 :
2486 154926 : xefi = kmem_cache_zalloc(xfs_extfree_item_cache,
2487 : GFP_KERNEL | __GFP_NOFAIL);
2488 154926 : xefi->xefi_startblock = fsbno;
2489 154926 : xefi->xefi_blockcount = 1;
2490 154926 : xefi->xefi_owner = oinfo->oi_owner;
2491 154926 : xefi->xefi_agresv = XFS_AG_RESV_AGFL;
2492 :
2493 154926 : trace_xfs_agfl_free_defer(mp, agno, 0, agbno, 1);
2494 :
2495 154926 : xfs_extent_free_get_group(mp, xefi);
2496 154926 : xfs_defer_add(tp, XFS_DEFER_OPS_TYPE_AGFL_FREE, &xefi->xefi_list);
2497 154926 : 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 40822236 : __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 40822236 : struct xfs_extent_free_item *xefi;
2514 40822236 : struct xfs_mount *mp = tp->t_mountp;
2515 : #ifdef DEBUG
2516 40822236 : xfs_agnumber_t agno;
2517 40822236 : xfs_agblock_t agbno;
2518 :
2519 40822236 : ASSERT(bno != NULLFSBLOCK);
2520 40822236 : ASSERT(len > 0);
2521 40822236 : ASSERT(len <= XFS_MAX_BMBT_EXTLEN);
2522 40822236 : ASSERT(!isnullstartblock(bno));
2523 40822236 : agno = XFS_FSB_TO_AGNO(mp, bno);
2524 40822236 : agbno = XFS_FSB_TO_AGBNO(mp, bno);
2525 40821789 : ASSERT(agno < mp->m_sb.sb_agcount);
2526 40821789 : ASSERT(agbno < mp->m_sb.sb_agblocks);
2527 40821789 : ASSERT(len < mp->m_sb.sb_agblocks);
2528 40821789 : ASSERT(agbno + len <= mp->m_sb.sb_agblocks);
2529 : #endif
2530 40821789 : ASSERT(xfs_extfree_item_cache != NULL);
2531 40821789 : ASSERT(type != XFS_AG_RESV_AGFL);
2532 :
2533 40821789 : if (XFS_IS_CORRUPT(mp, !xfs_verify_fsbext(mp, bno, len)))
2534 0 : return -EFSCORRUPTED;
2535 :
2536 40822532 : xefi = kmem_cache_zalloc(xfs_extfree_item_cache,
2537 : GFP_KERNEL | __GFP_NOFAIL);
2538 40822259 : xefi->xefi_startblock = bno;
2539 40822259 : xefi->xefi_blockcount = (xfs_extlen_t)len;
2540 40822259 : xefi->xefi_agresv = type;
2541 40822259 : if (skip_discard)
2542 1356334 : xefi->xefi_flags |= XFS_EFI_SKIP_DISCARD;
2543 40822259 : if (oinfo) {
2544 393084 : ASSERT(oinfo->oi_offset == 0);
2545 :
2546 393084 : if (oinfo->oi_flags & XFS_OWNER_INFO_ATTR_FORK)
2547 0 : xefi->xefi_flags |= XFS_EFI_ATTR_FORK;
2548 393084 : if (oinfo->oi_flags & XFS_OWNER_INFO_BMBT_BLOCK)
2549 261739 : xefi->xefi_flags |= XFS_EFI_BMBT_BLOCK;
2550 393084 : xefi->xefi_owner = oinfo->oi_owner;
2551 : } else {
2552 40429175 : xefi->xefi_owner = XFS_RMAP_OWN_NULL;
2553 : }
2554 40821902 : trace_xfs_bmap_free_defer(mp,
2555 40822259 : XFS_FSB_TO_AGNO(tp->t_mountp, bno), 0,
2556 40822259 : XFS_FSB_TO_AGBNO(tp->t_mountp, bno), len);
2557 :
2558 40821973 : xfs_extent_free_get_group(mp, xefi);
2559 40820919 : xfs_defer_add(tp, XFS_DEFER_OPS_TYPE_FREE, &xefi->xefi_list);
2560 40820919 : 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 337089 : xfs_exact_minlen_extent_available(
2570 : struct xfs_alloc_arg *args,
2571 : struct xfs_buf *agbp,
2572 : int *stat)
2573 : {
2574 337089 : struct xfs_btree_cur *cnt_cur;
2575 337089 : xfs_agblock_t fbno;
2576 337089 : xfs_extlen_t flen;
2577 337089 : int error = 0;
2578 :
2579 337089 : cnt_cur = xfs_allocbt_init_cursor(args->mp, args->tp, agbp,
2580 : args->pag, XFS_BTNUM_CNT);
2581 337093 : error = xfs_alloc_lookup_ge(cnt_cur, 0, args->minlen, stat);
2582 337086 : if (error)
2583 0 : goto out;
2584 :
2585 337086 : if (*stat == 0) {
2586 0 : error = -EFSCORRUPTED;
2587 0 : goto out;
2588 : }
2589 :
2590 337086 : error = xfs_alloc_get_rec(cnt_cur, &fbno, &flen, stat);
2591 337084 : if (error)
2592 0 : goto out;
2593 :
2594 337084 : if (*stat == 1 && flen != args->minlen)
2595 2740 : *stat = 0;
2596 :
2597 334344 : out:
2598 337084 : xfs_btree_del_cursor(cnt_cur, error);
2599 :
2600 337091 : 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 311321334 : xfs_alloc_fix_freelist(
2610 : struct xfs_alloc_arg *args, /* allocation argument structure */
2611 : uint32_t alloc_flags)
2612 : {
2613 311321334 : struct xfs_mount *mp = args->mp;
2614 311321334 : struct xfs_perag *pag = args->pag;
2615 311321334 : struct xfs_trans *tp = args->tp;
2616 311321334 : struct xfs_buf *agbp = NULL;
2617 311321334 : struct xfs_buf *agflbp = NULL;
2618 311321334 : struct xfs_alloc_arg targs; /* local allocation arguments */
2619 311321334 : xfs_agblock_t bno; /* freelist block */
2620 311321334 : xfs_extlen_t need; /* total blocks needed in freelist */
2621 311321334 : int error = 0;
2622 :
2623 : /* deferred ops (AGFL block frees) require permanent transactions */
2624 311321334 : ASSERT(tp->t_flags & XFS_TRANS_PERM_LOG_RES);
2625 :
2626 622642668 : if (!xfs_perag_initialised_agf(pag)) {
2627 3313 : error = xfs_alloc_read_agf(pag, tp, alloc_flags, &agbp);
2628 3313 : if (error) {
2629 : /* Couldn't lock the AGF so skip this AG. */
2630 1785 : if (error == -EAGAIN)
2631 1785 : error = 0;
2632 1785 : 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 622639098 : 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 311319549 : need = xfs_alloc_min_freelist(mp, pag);
2649 311318784 : if (!xfs_alloc_space_available(args, need, alloc_flags |
2650 : XFS_ALLOC_FLAG_CHECK))
2651 34168338 : 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 277151917 : if (!agbp) {
2658 277150878 : error = xfs_alloc_read_agf(pag, tp, alloc_flags, &agbp);
2659 277159630 : if (error) {
2660 : /* Couldn't lock the AGF so skip this AG. */
2661 2582804 : if (error == -EAGAIN)
2662 2581957 : error = 0;
2663 2582804 : goto out_no_agbp;
2664 : }
2665 : }
2666 :
2667 : /* reset a padding mismatched agfl before final free space check */
2668 549155730 : if (xfs_perag_agfl_needs_reset(pag))
2669 4 : xfs_agfl_reset(tp, agbp, pag);
2670 :
2671 : /* If there isn't enough total space or single-extent, reject it. */
2672 274577865 : need = xfs_alloc_min_freelist(mp, pag);
2673 274579687 : if (!xfs_alloc_space_available(args, need, alloc_flags))
2674 139 : goto out_agbp_relse;
2675 :
2676 : #ifdef DEBUG
2677 274572203 : if (args->alloc_minlen_only) {
2678 337081 : int stat;
2679 :
2680 337081 : error = xfs_exact_minlen_extent_available(args, agbp, &stat);
2681 337091 : if (error || !stat)
2682 2740 : 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 274569473 : memset(&targs, 0, sizeof(targs));
2710 : /* struct copy below */
2711 274569473 : if (alloc_flags & XFS_ALLOC_FLAG_NORMAP)
2712 0 : targs.oinfo = XFS_RMAP_OINFO_SKIP_UPDATE;
2713 : else
2714 274569473 : targs.oinfo = XFS_RMAP_OINFO_AG;
2715 274724399 : while (!(alloc_flags & XFS_ALLOC_FLAG_NOSHRINK) &&
2716 274724399 : pag->pagf_flcount > need) {
2717 152079 : error = xfs_alloc_get_freelist(pag, tp, agbp, &bno, 0);
2718 154926 : if (error)
2719 0 : goto out_agbp_relse;
2720 :
2721 : /* defer agfl frees */
2722 154926 : error = xfs_defer_agfl_block(tp, args->agno, bno, &targs.oinfo);
2723 154926 : if (error)
2724 0 : goto out_agbp_relse;
2725 : }
2726 :
2727 274572871 : targs.tp = tp;
2728 274572871 : targs.mp = mp;
2729 274572871 : targs.agbp = agbp;
2730 274572871 : targs.agno = args->agno;
2731 274572871 : targs.alignment = targs.minlen = targs.prod = 1;
2732 274572871 : targs.pag = pag;
2733 274572871 : error = xfs_alloc_read_agfl(pag, tp, &agflbp);
2734 274576353 : if (error)
2735 758 : goto out_agbp_relse;
2736 :
2737 : /* Make the freelist longer if it's too short. */
2738 274885527 : while (pag->pagf_flcount < need) {
2739 312755 : targs.agbno = 0;
2740 312755 : targs.maxlen = need - pag->pagf_flcount;
2741 312755 : targs.resv = XFS_AG_RESV_AGFL;
2742 :
2743 : /* Allocate as many blocks as possible at once. */
2744 312755 : error = xfs_alloc_ag_vextent_size(&targs, alloc_flags);
2745 309942 : if (error)
2746 1 : 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 309941 : if (targs.agbno == NULLAGBLOCK) {
2754 0 : if (alloc_flags & XFS_ALLOC_FLAG_FREEING)
2755 : break;
2756 0 : goto out_agflbp_relse;
2757 : }
2758 :
2759 309941 : if (!xfs_rmap_should_skip_owner_update(&targs.oinfo)) {
2760 309941 : error = xfs_rmap_alloc(tp, agbp, pag,
2761 : targs.agbno, targs.len, &targs.oinfo);
2762 309941 : if (error)
2763 9 : goto out_agflbp_relse;
2764 : }
2765 309932 : error = xfs_alloc_update_counters(tp, agbp,
2766 309932 : -((long)(targs.len)));
2767 309932 : if (error)
2768 0 : goto out_agflbp_relse;
2769 :
2770 : /*
2771 : * Put each allocated block on the list.
2772 : */
2773 662704 : for (bno = targs.agbno; bno < targs.agbno + targs.len; bno++) {
2774 352772 : error = xfs_alloc_put_freelist(pag, tp, agbp,
2775 : agflbp, bno, 0);
2776 352772 : if (error)
2777 0 : goto out_agflbp_relse;
2778 : }
2779 : }
2780 274572772 : xfs_trans_brelse(tp, agflbp);
2781 274575939 : args->agbp = agbp;
2782 274575939 : return 0;
2783 :
2784 10 : out_agflbp_relse:
2785 10 : xfs_trans_brelse(tp, agflbp);
2786 34171985 : out_agbp_relse:
2787 34171985 : if (agbp)
2788 3647 : xfs_trans_brelse(tp, agbp);
2789 34168338 : out_no_agbp:
2790 36756574 : args->agbp = NULL;
2791 36756574 : 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 493123 : 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 493123 : struct xfs_agf *agf = agbp->b_addr;
2807 493123 : struct xfs_buf *agflbp;
2808 493123 : xfs_agblock_t bno;
2809 493123 : __be32 *agfl_bno;
2810 493123 : int error;
2811 493123 : uint32_t logflags;
2812 493123 : struct xfs_mount *mp = tp->t_mountp;
2813 :
2814 : /*
2815 : * Freelist is empty, give up.
2816 : */
2817 493123 : if (!agf->agf_flcount) {
2818 0 : *bnop = NULLAGBLOCK;
2819 0 : return 0;
2820 : }
2821 : /*
2822 : * Read the array of free blocks.
2823 : */
2824 493123 : error = xfs_alloc_read_agfl(pag, tp, &agflbp);
2825 493123 : if (error)
2826 : return error;
2827 :
2828 :
2829 : /*
2830 : * Get the block number and update the data structures.
2831 : */
2832 493123 : agfl_bno = xfs_buf_to_agfl_bno(agflbp);
2833 493123 : bno = be32_to_cpu(agfl_bno[be32_to_cpu(agf->agf_flfirst)]);
2834 986246 : if (XFS_IS_CORRUPT(tp->t_mountp, !xfs_verify_agbno(pag, bno)))
2835 0 : return -EFSCORRUPTED;
2836 :
2837 493123 : be32_add_cpu(&agf->agf_flfirst, 1);
2838 493123 : xfs_trans_brelse(tp, agflbp);
2839 986246 : if (be32_to_cpu(agf->agf_flfirst) == xfs_agfl_size(mp))
2840 342 : agf->agf_flfirst = 0;
2841 :
2842 986246 : ASSERT(!xfs_perag_agfl_needs_reset(pag));
2843 493123 : be32_add_cpu(&agf->agf_flcount, -1);
2844 493123 : pag->pagf_flcount--;
2845 :
2846 493123 : logflags = XFS_AGF_FLFIRST | XFS_AGF_FLCOUNT;
2847 493123 : if (btreeblk) {
2848 338197 : be32_add_cpu(&agf->agf_btreeblks, 1);
2849 338197 : pag->pagf_btreeblks++;
2850 338197 : logflags |= XFS_AGF_BTREEBLKS;
2851 : }
2852 :
2853 493123 : xfs_alloc_log_agf(tp, agbp, logflags);
2854 493123 : *bnop = bno;
2855 :
2856 493123 : return 0;
2857 : }
2858 :
2859 : /*
2860 : * Log the given fields from the agf structure.
2861 : */
2862 : void
2863 109294647 : xfs_alloc_log_agf(
2864 : struct xfs_trans *tp,
2865 : struct xfs_buf *bp,
2866 : uint32_t fields)
2867 : {
2868 109294647 : int first; /* first byte offset */
2869 109294647 : int last; /* last byte offset */
2870 109294647 : 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 109294647 : trace_xfs_agf(tp->t_mountp, bp->b_addr, fields, _RET_IP_);
2894 :
2895 109296661 : xfs_trans_buf_set_type(tp, bp, XFS_BLFT_AGF_BUF);
2896 :
2897 109297658 : xfs_btree_offsets(fields, offsets, XFS_AGF_NUM_BITS, &first, &last);
2898 109298136 : xfs_trans_log_buf(tp, bp, (uint)first, (uint)last);
2899 109297700 : }
2900 :
2901 : /*
2902 : * Put the block on the freelist for the allocation group.
2903 : */
2904 : int
2905 494943 : 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 494943 : struct xfs_mount *mp = tp->t_mountp;
2914 494943 : struct xfs_agf *agf = agbp->b_addr;
2915 494943 : __be32 *blockp;
2916 494943 : int error;
2917 494943 : uint32_t logflags;
2918 494943 : __be32 *agfl_bno;
2919 494943 : int startoff;
2920 :
2921 494943 : if (!agflbp) {
2922 142171 : error = xfs_alloc_read_agfl(pag, tp, &agflbp);
2923 142171 : if (error)
2924 : return error;
2925 : }
2926 :
2927 494943 : be32_add_cpu(&agf->agf_fllast, 1);
2928 989886 : if (be32_to_cpu(agf->agf_fllast) == xfs_agfl_size(mp))
2929 337 : agf->agf_fllast = 0;
2930 :
2931 989886 : ASSERT(!xfs_perag_agfl_needs_reset(pag));
2932 494943 : be32_add_cpu(&agf->agf_flcount, 1);
2933 494943 : pag->pagf_flcount++;
2934 :
2935 494943 : logflags = XFS_AGF_FLLAST | XFS_AGF_FLCOUNT;
2936 494943 : if (btreeblk) {
2937 142171 : be32_add_cpu(&agf->agf_btreeblks, -1);
2938 142171 : pag->pagf_btreeblks--;
2939 142171 : logflags |= XFS_AGF_BTREEBLKS;
2940 : }
2941 :
2942 494943 : xfs_alloc_log_agf(tp, agbp, logflags);
2943 :
2944 989886 : ASSERT(be32_to_cpu(agf->agf_flcount) <= xfs_agfl_size(mp));
2945 :
2946 494943 : agfl_bno = xfs_buf_to_agfl_bno(agflbp);
2947 494943 : blockp = &agfl_bno[be32_to_cpu(agf->agf_fllast)];
2948 494943 : *blockp = cpu_to_be32(bno);
2949 494943 : startoff = (char *)blockp - (char *)agflbp->b_addr;
2950 :
2951 494943 : xfs_alloc_log_agf(tp, agbp, logflags);
2952 :
2953 494943 : xfs_trans_buf_set_type(tp, agflbp, XFS_BLFT_AGFL_BUF);
2954 494943 : xfs_trans_log_buf(tp, agflbp, startoff,
2955 : startoff + sizeof(xfs_agblock_t) - 1);
2956 494943 : 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 4037363 : xfs_validate_ag_length(
2965 : struct xfs_buf *bp,
2966 : uint32_t seqno,
2967 : uint32_t length)
2968 : {
2969 4037363 : 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 4037363 : 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 4037363 : 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 994 : if (bp->b_pag && seqno != mp->m_sb.sb_agcount - 1)
2990 0 : return __this_address;
2991 994 : if (length < XFS_MIN_AG_BLOCKS)
2992 0 : return __this_address;
2993 994 : if (length > mp->m_sb.sb_agblocks)
2994 2 : 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 2166109 : xfs_agf_verify(
3015 : struct xfs_buf *bp)
3016 : {
3017 2166109 : struct xfs_mount *mp = bp->b_mount;
3018 2166109 : struct xfs_agf *agf = bp->b_addr;
3019 2166109 : xfs_failaddr_t fa;
3020 2166109 : uint32_t agf_seqno = be32_to_cpu(agf->agf_seqno);
3021 2166109 : uint32_t agf_length = be32_to_cpu(agf->agf_length);
3022 :
3023 2166109 : if (xfs_has_crc(mp)) {
3024 2163781 : if (!uuid_equal(&agf->agf_uuid, &mp->m_sb.sb_meta_uuid))
3025 0 : return __this_address;
3026 2163775 : if (!xfs_log_check_lsn(mp, be64_to_cpu(agf->agf_lsn)))
3027 0 : return __this_address;
3028 : }
3029 :
3030 2166126 : if (!xfs_verify_magic(bp, agf->agf_magicnum))
3031 0 : return __this_address;
3032 :
3033 2166123 : 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 2166125 : fa = xfs_validate_ag_length(bp, agf_seqno, agf_length);
3041 2166084 : if (fa)
3042 : return fa;
3043 :
3044 4332216 : if (be32_to_cpu(agf->agf_flfirst) >= xfs_agfl_size(mp))
3045 2 : return __this_address;
3046 4332212 : if (be32_to_cpu(agf->agf_fllast) >= xfs_agfl_size(mp))
3047 0 : return __this_address;
3048 4332212 : if (be32_to_cpu(agf->agf_flcount) > xfs_agfl_size(mp))
3049 0 : return __this_address;
3050 :
3051 6498318 : if (be32_to_cpu(agf->agf_freeblks) < be32_to_cpu(agf->agf_longest) ||
3052 : be32_to_cpu(agf->agf_freeblks) > agf_length)
3053 5 : return __this_address;
3054 :
3055 2166111 : if (be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNO]) < 1 ||
3056 2166111 : be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNT]) < 1 ||
3057 2166111 : be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNO]) >
3058 4332211 : mp->m_alloc_maxlevels ||
3059 2166100 : be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNT]) >
3060 : mp->m_alloc_maxlevels)
3061 6 : return __this_address;
3062 :
3063 4332193 : if (xfs_has_lazysbcount(mp) &&
3064 2166085 : be32_to_cpu(agf->agf_btreeblks) > agf_length)
3065 0 : return __this_address;
3066 :
3067 2166108 : if (xfs_has_rmapbt(mp)) {
3068 3606012 : if (be32_to_cpu(agf->agf_rmap_blocks) > agf_length)
3069 2 : return __this_address;
3070 :
3071 1803004 : if (be32_to_cpu(agf->agf_levels[XFS_BTNUM_RMAP]) < 1 ||
3072 1803010 : be32_to_cpu(agf->agf_levels[XFS_BTNUM_RMAP]) >
3073 1803010 : mp->m_rmap_maxlevels)
3074 1 : return __this_address;
3075 : }
3076 :
3077 2166112 : if (xfs_has_reflink(mp)) {
3078 3606036 : if (be32_to_cpu(agf->agf_refcount_blocks) > agf_length)
3079 2 : return __this_address;
3080 :
3081 1803016 : if (be32_to_cpu(agf->agf_refcount_level) < 1 ||
3082 3606004 : be32_to_cpu(agf->agf_refcount_level) > mp->m_refc_maxlevels)
3083 14 : return __this_address;
3084 : }
3085 :
3086 : return NULL;
3087 : }
3088 :
3089 : static void
3090 268776 : xfs_agf_read_verify(
3091 : struct xfs_buf *bp)
3092 : {
3093 268776 : struct xfs_mount *mp = bp->b_mount;
3094 268776 : xfs_failaddr_t fa;
3095 :
3096 537534 : if (xfs_has_crc(mp) &&
3097 : !xfs_buf_verify_cksum(bp, XFS_AGF_CRC_OFF))
3098 8 : xfs_verifier_error(bp, -EFSBADCRC, __this_address);
3099 : else {
3100 268768 : fa = xfs_agf_verify(bp);
3101 268768 : if (XFS_TEST_ERROR(fa, mp, XFS_ERRTAG_ALLOC_READ_AGF))
3102 12 : xfs_verifier_error(bp, -EFSCORRUPTED, fa);
3103 : }
3104 268776 : }
3105 :
3106 : static void
3107 775673 : xfs_agf_write_verify(
3108 : struct xfs_buf *bp)
3109 : {
3110 775673 : struct xfs_mount *mp = bp->b_mount;
3111 775673 : struct xfs_buf_log_item *bip = bp->b_log_item;
3112 775673 : struct xfs_agf *agf = bp->b_addr;
3113 775673 : xfs_failaddr_t fa;
3114 :
3115 775673 : fa = xfs_agf_verify(bp);
3116 775673 : if (fa) {
3117 0 : xfs_verifier_error(bp, -EFSCORRUPTED, fa);
3118 0 : return;
3119 : }
3120 :
3121 775673 : if (!xfs_has_crc(mp))
3122 : return;
3123 :
3124 773379 : if (bip)
3125 767971 : agf->agf_lsn = cpu_to_be64(bip->bli_item.li_lsn);
3126 :
3127 773379 : 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 1158429215 : xfs_read_agf(
3143 : struct xfs_perag *pag,
3144 : struct xfs_trans *tp,
3145 : int flags,
3146 : struct xfs_buf **agfbpp)
3147 : {
3148 1158429215 : struct xfs_mount *mp = pag->pag_mount;
3149 1158429215 : int error;
3150 :
3151 1158429215 : trace_xfs_read_agf(pag->pag_mount, pag->pag_agno);
3152 :
3153 4633794092 : error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp,
3154 1158448523 : XFS_AG_DADDR(mp, pag->pag_agno, XFS_AGF_DADDR(mp)),
3155 1158448523 : XFS_FSS_TO_BB(mp, 1), flags, agfbpp, &xfs_agf_buf_ops);
3156 1158524743 : if (error)
3157 : return error;
3158 :
3159 1155937852 : xfs_buf_set_ref(*agfbpp, XFS_AGF_REF);
3160 1155937852 : 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 1158413963 : xfs_alloc_read_agf(
3170 : struct xfs_perag *pag,
3171 : struct xfs_trans *tp,
3172 : int flags,
3173 : struct xfs_buf **agfbpp)
3174 : {
3175 1158413963 : struct xfs_buf *agfbp;
3176 1158413963 : struct xfs_agf *agf;
3177 1158413963 : int error;
3178 1158413963 : int allocbt_blks;
3179 :
3180 1158413963 : trace_xfs_alloc_read_agf(pag->pag_mount, pag->pag_agno);
3181 :
3182 : /* We don't support trylock when freeing. */
3183 1158448324 : ASSERT((flags & (XFS_ALLOC_FLAG_FREEING | XFS_ALLOC_FLAG_TRYLOCK)) !=
3184 : (XFS_ALLOC_FLAG_FREEING | XFS_ALLOC_FLAG_TRYLOCK));
3185 1158448324 : error = xfs_read_agf(pag, tp,
3186 1158448324 : (flags & XFS_ALLOC_FLAG_TRYLOCK) ? XBF_TRYLOCK : 0,
3187 : &agfbp);
3188 1158514425 : if (error)
3189 : return error;
3190 :
3191 1155927727 : agf = agfbp->b_addr;
3192 2311855454 : if (!xfs_perag_initialised_agf(pag)) {
3193 124400 : pag->pagf_freeblks = be32_to_cpu(agf->agf_freeblks);
3194 124400 : pag->pagf_btreeblks = be32_to_cpu(agf->agf_btreeblks);
3195 124400 : pag->pagf_flcount = be32_to_cpu(agf->agf_flcount);
3196 124400 : pag->pagf_longest = be32_to_cpu(agf->agf_longest);
3197 124400 : pag->pagf_levels[XFS_BTNUM_BNOi] =
3198 124400 : be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNOi]);
3199 124400 : pag->pagf_levels[XFS_BTNUM_CNTi] =
3200 124400 : be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNTi]);
3201 124400 : pag->pagf_levels[XFS_BTNUM_RMAPi] =
3202 124400 : be32_to_cpu(agf->agf_levels[XFS_BTNUM_RMAPi]);
3203 124400 : pag->pagf_refcount_level = be32_to_cpu(agf->agf_refcount_level);
3204 124400 : if (xfs_agfl_needs_reset(pag->pag_mount, agf))
3205 4 : set_bit(XFS_AGSTATE_AGFL_NEEDS_RESET, &pag->pag_opstate);
3206 : else
3207 124396 : 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 124400 : allocbt_blks = pag->pagf_btreeblks;
3217 124400 : if (xfs_has_rmapbt(pag->pag_mount))
3218 123630 : allocbt_blks -= be32_to_cpu(agf->agf_rmap_blocks) - 1;
3219 124400 : if (allocbt_blks > 0)
3220 19596 : atomic64_add(allocbt_blks,
3221 : &pag->pag_mount->m_allocbt_blks);
3222 :
3223 124400 : set_bit(XFS_AGSTATE_AGF_INIT, &pag->pag_opstate);
3224 : }
3225 : #ifdef DEBUG
3226 2311606654 : else if (!xfs_is_shutdown(pag->pag_mount)) {
3227 2311606128 : ASSERT(pag->pagf_freeblks == be32_to_cpu(agf->agf_freeblks));
3228 2311606128 : ASSERT(pag->pagf_btreeblks == be32_to_cpu(agf->agf_btreeblks));
3229 2311606128 : ASSERT(pag->pagf_flcount == be32_to_cpu(agf->agf_flcount));
3230 2311606128 : ASSERT(pag->pagf_longest == be32_to_cpu(agf->agf_longest));
3231 2311606128 : ASSERT(pag->pagf_levels[XFS_BTNUM_BNOi] ==
3232 : be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNOi]));
3233 2311606128 : ASSERT(pag->pagf_levels[XFS_BTNUM_CNTi] ==
3234 : be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNTi]));
3235 : }
3236 : #endif
3237 1155927727 : if (agfbpp)
3238 1155649554 : *agfbpp = agfbp;
3239 : else
3240 278173 : 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 45269499 : xfs_alloc_vextent_check_args(
3251 : struct xfs_alloc_arg *args,
3252 : xfs_fsblock_t target,
3253 : xfs_agnumber_t *minimum_agno)
3254 : {
3255 45269499 : struct xfs_mount *mp = args->mp;
3256 45269499 : xfs_agblock_t agsize;
3257 :
3258 45269499 : args->fsbno = NULLFSBLOCK;
3259 :
3260 45269499 : *minimum_agno = 0;
3261 45269499 : if (args->tp->t_highest_agno != NULLAGNUMBER)
3262 289660 : *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 45269499 : agsize = mp->m_sb.sb_agblocks;
3270 45269499 : if (args->maxlen > agsize)
3271 0 : args->maxlen = agsize;
3272 45269499 : if (args->alignment == 0)
3273 561016 : args->alignment = 1;
3274 :
3275 45269499 : ASSERT(args->minlen > 0);
3276 45269499 : ASSERT(args->maxlen > 0);
3277 45269499 : ASSERT(args->alignment > 0);
3278 45269499 : ASSERT(args->resv != XFS_AG_RESV_AGFL);
3279 :
3280 45269499 : ASSERT(XFS_FSB_TO_AGNO(mp, target) < mp->m_sb.sb_agcount);
3281 45269499 : ASSERT(XFS_FSB_TO_AGBNO(mp, target) < agsize);
3282 45269908 : ASSERT(args->minlen <= args->maxlen);
3283 45269908 : ASSERT(args->minlen <= agsize);
3284 45269908 : ASSERT(args->mod < args->prod);
3285 :
3286 45269908 : if (XFS_FSB_TO_AGNO(mp, target) >= mp->m_sb.sb_agcount ||
3287 45269908 : XFS_FSB_TO_AGBNO(mp, target) >= agsize ||
3288 45269790 : args->minlen > args->maxlen || args->minlen > agsize ||
3289 45269790 : args->mod >= args->prod) {
3290 0 : trace_xfs_alloc_vextent_badargs(args);
3291 0 : return -ENOSPC;
3292 : }
3293 :
3294 45269790 : if (args->agno != NULLAGNUMBER && *minimum_agno > args->agno) {
3295 0 : trace_xfs_alloc_vextent_skip_deadlock(args);
3296 0 : 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 81446793 : xfs_alloc_vextent_prepare_ag(
3311 : struct xfs_alloc_arg *args,
3312 : uint32_t alloc_flags)
3313 : {
3314 81446793 : bool need_pag = !args->pag;
3315 81446793 : int error;
3316 :
3317 81446793 : if (need_pag)
3318 0 : args->pag = xfs_perag_get(args->mp, args->agno);
3319 :
3320 81446793 : args->agbp = NULL;
3321 81446793 : error = xfs_alloc_fix_freelist(args, alloc_flags);
3322 81447492 : if (error) {
3323 738 : trace_xfs_alloc_vextent_nofix(args);
3324 738 : if (need_pag)
3325 0 : xfs_perag_put(args->pag);
3326 738 : args->agbno = NULLAGBLOCK;
3327 738 : return error;
3328 : }
3329 81446754 : if (!args->agbp) {
3330 : /* cannot allocate in this AG at all */
3331 36754948 : trace_xfs_alloc_vextent_noagbp(args);
3332 36754933 : args->agbno = NULLAGBLOCK;
3333 36754933 : return 0;
3334 : }
3335 44691806 : args->wasfromfl = 0;
3336 44691806 : 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 45270800 : 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 45270800 : struct xfs_mount *mp = args->mp;
3354 45270800 : 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 45270800 : if (args->agbp &&
3373 44691107 : (args->tp->t_highest_agno == NULLAGNUMBER ||
3374 289655 : args->agno > minimum_agno))
3375 44424439 : 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 45270800 : if (alloc_error || args->agbno == NULLAGBLOCK) {
3384 703378 : args->fsbno = NULLFSBLOCK;
3385 703378 : error = alloc_error;
3386 703378 : goto out_drop_perag;
3387 : }
3388 :
3389 44567422 : args->fsbno = XFS_AGB_TO_FSB(mp, args->agno, args->agbno);
3390 :
3391 44567422 : ASSERT(args->len >= args->minlen);
3392 44567422 : ASSERT(args->len <= args->maxlen);
3393 44567422 : ASSERT(args->agbno % args->alignment == 0);
3394 44567422 : 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 44567006 : if (!xfs_rmap_should_skip_owner_update(&args->oinfo)) {
3398 913394 : error = xfs_rmap_alloc(args->tp, args->agbp, args->pag,
3399 913394 : args->agbno, args->len, &args->oinfo);
3400 913396 : if (error)
3401 30 : goto out_drop_perag;
3402 : }
3403 :
3404 44566978 : if (!args->wasfromfl) {
3405 44566672 : error = xfs_alloc_update_counters(args->tp, args->agbp,
3406 44566672 : -((long)(args->len)));
3407 44566914 : if (error)
3408 0 : goto out_drop_perag;
3409 :
3410 44566914 : ASSERT(!xfs_extent_busy_search(mp, args->pag, args->agbno,
3411 : args->len));
3412 : }
3413 :
3414 44567531 : xfs_ag_resv_alloc_extent(args->pag, args->resv, args);
3415 :
3416 44566391 : XFS_STATS_INC(mp, xs_allocx);
3417 44567185 : XFS_STATS_ADD(mp, xs_allocb, args->len);
3418 :
3419 44567214 : trace_xfs_alloc_vextent_finish(args);
3420 :
3421 45270723 : out_drop_perag:
3422 45270723 : if (drop_perag && args->pag) {
3423 44135211 : xfs_perag_rele(args->pag);
3424 44135138 : args->pag = NULL;
3425 : }
3426 45270650 : 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 44151954 : 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 44151954 : struct xfs_mount *mp = args->mp;
3496 44151954 : xfs_agnumber_t restart_agno = minimum_agno;
3497 44151954 : xfs_agnumber_t agno;
3498 44151954 : int error = 0;
3499 :
3500 44151954 : if (alloc_flags & XFS_ALLOC_FLAG_TRYLOCK)
3501 44151954 : restart_agno = 0;
3502 0 : restart:
3503 80378299 : for_each_perag_wrap_range(mp, start_agno, restart_agno,
3504 : mp->m_sb.sb_agcount, agno, args->pag) {
3505 80329750 : args->agno = agno;
3506 80329750 : error = xfs_alloc_vextent_prepare_ag(args, alloc_flags);
3507 80330876 : if (error)
3508 : break;
3509 80330142 : if (!args->agbp) {
3510 36193603 : trace_xfs_alloc_vextent_loopfailed(args);
3511 36193617 : 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 44136539 : if (args->agno == start_agno && target_agbno) {
3519 41859919 : args->agbno = target_agbno;
3520 41859919 : error = xfs_alloc_ag_vextent_near(args, alloc_flags);
3521 : } else {
3522 2276620 : args->agbno = 0;
3523 2276620 : error = xfs_alloc_ag_vextent_size(args, alloc_flags);
3524 : }
3525 : break;
3526 : }
3527 44185994 : if (error) {
3528 1672 : xfs_perag_rele(args->pag);
3529 1672 : args->pag = NULL;
3530 1672 : return error;
3531 : }
3532 44184322 : 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 49114 : if (alloc_flags & XFS_ALLOC_FLAG_TRYLOCK) {
3541 32716 : alloc_flags &= ~XFS_ALLOC_FLAG_TRYLOCK;
3542 32716 : restart_agno = minimum_agno;
3543 32716 : goto restart;
3544 : }
3545 :
3546 16398 : ASSERT(args->pag == NULL);
3547 16398 : trace_xfs_alloc_vextent_allfailed(args);
3548 16398 : 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 43818165 : xfs_alloc_vextent_start_ag(
3561 : struct xfs_alloc_arg *args,
3562 : xfs_fsblock_t target)
3563 : {
3564 43818165 : struct xfs_mount *mp = args->mp;
3565 43818165 : xfs_agnumber_t minimum_agno;
3566 43818165 : xfs_agnumber_t start_agno;
3567 43818165 : xfs_agnumber_t rotorstep = xfs_rotorstep;
3568 43818165 : bool bump_rotor = false;
3569 43818165 : uint32_t alloc_flags = XFS_ALLOC_FLAG_TRYLOCK;
3570 43818165 : int error;
3571 :
3572 43818165 : ASSERT(args->pag == NULL);
3573 :
3574 43818165 : args->agno = NULLAGNUMBER;
3575 43818165 : args->agbno = NULLAGBLOCK;
3576 :
3577 43818165 : trace_xfs_alloc_vextent_start_ag(args);
3578 :
3579 43818015 : error = xfs_alloc_vextent_check_args(args, target, &minimum_agno);
3580 43817731 : if (error) {
3581 0 : if (error == -ENOSPC)
3582 : return 0;
3583 0 : return error;
3584 : }
3585 :
3586 46279971 : 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 43817731 : start_agno = max(minimum_agno, XFS_FSB_TO_AGNO(mp, target));
3595 43817203 : error = xfs_alloc_vextent_iterate_ags(args, minimum_agno, start_agno,
3596 43817731 : XFS_FSB_TO_AGBNO(mp, target), alloc_flags);
3597 :
3598 43818745 : 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 43818745 : 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 334378 : xfs_alloc_vextent_first_ag(
3617 : struct xfs_alloc_arg *args,
3618 : xfs_fsblock_t target)
3619 : {
3620 334378 : struct xfs_mount *mp = args->mp;
3621 334378 : xfs_agnumber_t minimum_agno;
3622 334378 : xfs_agnumber_t start_agno;
3623 334378 : uint32_t alloc_flags = XFS_ALLOC_FLAG_TRYLOCK;
3624 334378 : int error;
3625 :
3626 334378 : ASSERT(args->pag == NULL);
3627 :
3628 334378 : args->agno = NULLAGNUMBER;
3629 334378 : args->agbno = NULLAGBLOCK;
3630 :
3631 334378 : trace_xfs_alloc_vextent_first_ag(args);
3632 :
3633 334378 : error = xfs_alloc_vextent_check_args(args, target, &minimum_agno);
3634 334378 : if (error) {
3635 0 : if (error == -ENOSPC)
3636 : return 0;
3637 0 : return error;
3638 : }
3639 :
3640 334378 : start_agno = max(minimum_agno, XFS_FSB_TO_AGNO(mp, target));
3641 334376 : error = xfs_alloc_vextent_iterate_ags(args, minimum_agno, start_agno,
3642 334378 : XFS_FSB_TO_AGBNO(mp, target), alloc_flags);
3643 334355 : 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 305338 : xfs_alloc_vextent_exact_bno(
3652 : struct xfs_alloc_arg *args,
3653 : xfs_fsblock_t target)
3654 : {
3655 305338 : struct xfs_mount *mp = args->mp;
3656 305338 : xfs_agnumber_t minimum_agno;
3657 305338 : int error;
3658 :
3659 305338 : ASSERT(args->pag != NULL);
3660 305338 : ASSERT(args->pag->pag_agno == XFS_FSB_TO_AGNO(mp, target));
3661 :
3662 305338 : args->agno = XFS_FSB_TO_AGNO(mp, target);
3663 305338 : args->agbno = XFS_FSB_TO_AGBNO(mp, target);
3664 :
3665 305338 : trace_xfs_alloc_vextent_exact_bno(args);
3666 :
3667 305338 : error = xfs_alloc_vextent_check_args(args, target, &minimum_agno);
3668 305338 : if (error) {
3669 0 : if (error == -ENOSPC)
3670 : return 0;
3671 0 : return error;
3672 : }
3673 :
3674 305338 : error = xfs_alloc_vextent_prepare_ag(args, 0);
3675 305338 : if (!error && args->agbp)
3676 174327 : error = xfs_alloc_ag_vextent_exact(args);
3677 :
3678 305338 : 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 812152 : xfs_alloc_vextent_near_bno(
3689 : struct xfs_alloc_arg *args,
3690 : xfs_fsblock_t target)
3691 : {
3692 812152 : struct xfs_mount *mp = args->mp;
3693 812152 : xfs_agnumber_t minimum_agno;
3694 812152 : bool needs_perag = args->pag == NULL;
3695 812152 : uint32_t alloc_flags = 0;
3696 812152 : int error;
3697 :
3698 812152 : if (!needs_perag)
3699 812152 : ASSERT(args->pag->pag_agno == XFS_FSB_TO_AGNO(mp, target));
3700 :
3701 812152 : args->agno = XFS_FSB_TO_AGNO(mp, target);
3702 812152 : args->agbno = XFS_FSB_TO_AGBNO(mp, target);
3703 :
3704 812158 : trace_xfs_alloc_vextent_near_bno(args);
3705 :
3706 812157 : error = xfs_alloc_vextent_check_args(args, target, &minimum_agno);
3707 812157 : if (error) {
3708 0 : if (error == -ENOSPC)
3709 : return 0;
3710 0 : return error;
3711 : }
3712 :
3713 812157 : if (needs_perag)
3714 0 : args->pag = xfs_perag_grab(mp, args->agno);
3715 :
3716 812157 : error = xfs_alloc_vextent_prepare_ag(args, alloc_flags);
3717 812158 : if (!error && args->agbp)
3718 381831 : error = xfs_alloc_ag_vextent_near(args, alloc_flags);
3719 :
3720 812157 : 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 229881862 : xfs_free_extent_fix_freelist(
3726 : struct xfs_trans *tp,
3727 : struct xfs_perag *pag,
3728 : struct xfs_buf **agbp)
3729 : {
3730 229881862 : struct xfs_alloc_arg args;
3731 229881862 : int error;
3732 :
3733 229881862 : memset(&args, 0, sizeof(struct xfs_alloc_arg));
3734 229881862 : args.tp = tp;
3735 229881862 : args.mp = tp->t_mountp;
3736 229881862 : args.agno = pag->pag_agno;
3737 229881862 : 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 229881862 : if (args.agno >= args.mp->m_sb.sb_agcount)
3744 : return -EFSCORRUPTED;
3745 :
3746 229881862 : error = xfs_alloc_fix_freelist(&args, XFS_ALLOC_FLAG_FREEING);
3747 229883544 : if (error)
3748 : return error;
3749 :
3750 229882663 : *agbp = args.agbp;
3751 229882663 : 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 40823161 : __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 40823161 : struct xfs_mount *mp = tp->t_mountp;
3770 40823161 : struct xfs_buf *agbp;
3771 40823161 : struct xfs_agf *agf;
3772 40823161 : int error;
3773 40823161 : unsigned int busy_flags = 0;
3774 :
3775 40823161 : ASSERT(len != 0);
3776 40823161 : ASSERT(type != XFS_AG_RESV_AGFL);
3777 :
3778 40823161 : if (XFS_TEST_ERROR(false, mp,
3779 : XFS_ERRTAG_FREE_EXTENT))
3780 : return -EIO;
3781 :
3782 40823367 : error = xfs_free_extent_fix_freelist(tp, pag, &agbp);
3783 40823476 : if (error)
3784 : return error;
3785 40823461 : agf = agbp->b_addr;
3786 :
3787 40823461 : 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 81646922 : 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 40823461 : error = xfs_free_ag_extent(tp, agbp, pag->pag_agno, agbno, len, oinfo,
3799 : type);
3800 40823304 : if (error)
3801 262 : goto err_release;
3802 :
3803 40823042 : if (skip_discard)
3804 1356295 : busy_flags |= XFS_EXTENT_BUSY_SKIP_DISCARD;
3805 40823042 : xfs_extent_busy_insert(tp, pag, agbno, len, busy_flags);
3806 40823042 : return 0;
3807 :
3808 262 : err_release:
3809 262 : xfs_trans_brelse(tp, agbp);
3810 262 : 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 1005669050 : xfs_alloc_query_range_helper(
3821 : struct xfs_btree_cur *cur,
3822 : const union xfs_btree_rec *rec,
3823 : void *priv)
3824 : {
3825 1005669050 : struct xfs_alloc_query_range_info *query = priv;
3826 1005669050 : struct xfs_alloc_rec_incore irec;
3827 1005669050 : xfs_failaddr_t fa;
3828 :
3829 1005669050 : xfs_alloc_btrec_to_irec(rec, &irec);
3830 1005668796 : fa = xfs_alloc_check_irec(cur, &irec);
3831 1005670176 : if (fa)
3832 0 : return xfs_alloc_complain_bad_rec(cur, fa, &irec);
3833 :
3834 1005670176 : return query->fn(cur, &irec, query->priv);
3835 : }
3836 :
3837 : /* Find all free space within a given range of blocks. */
3838 : int
3839 199096 : 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 199096 : union xfs_btree_irec low_brec = { .a = *low_rec };
3847 199096 : union xfs_btree_irec high_brec = { .a = *high_rec };
3848 199096 : struct xfs_alloc_query_range_info query = { .priv = priv, .fn = fn };
3849 :
3850 199096 : ASSERT(cur->bc_btnum == XFS_BTNUM_BNO);
3851 199096 : 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 1302433 : xfs_alloc_query_all(
3858 : struct xfs_btree_cur *cur,
3859 : xfs_alloc_query_range_fn fn,
3860 : void *priv)
3861 : {
3862 1302433 : struct xfs_alloc_query_range_info query;
3863 :
3864 1302433 : ASSERT(cur->bc_btnum == XFS_BTNUM_BNO);
3865 1302433 : query.priv = priv;
3866 1302433 : query.fn = fn;
3867 1302433 : 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 1328732649 : 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 1328732649 : union xfs_btree_irec low;
3882 1328732649 : union xfs_btree_irec high;
3883 :
3884 1328732649 : memset(&low, 0, sizeof(low));
3885 1328732649 : low.a.ar_startblock = bno;
3886 1328732649 : memset(&high, 0xFF, sizeof(high));
3887 1328732649 : high.a.ar_startblock = bno + len - 1;
3888 :
3889 1328732649 : 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 51255407 : 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 51255407 : __be32 *agfl_bno;
3905 51255407 : unsigned int i;
3906 51255407 : int error;
3907 :
3908 51255407 : agfl_bno = xfs_buf_to_agfl_bno(agflbp);
3909 51255407 : i = be32_to_cpu(agf->agf_flfirst);
3910 :
3911 : /* Nothing to walk in an empty AGFL. */
3912 51255407 : if (agf->agf_flcount == cpu_to_be32(0))
3913 : return 0;
3914 :
3915 : /* Otherwise, walk from first to last, wrapping as needed. */
3916 476665169 : for (;;) {
3917 953330338 : error = walk_fn(mp, be32_to_cpu(agfl_bno[i]), priv);
3918 476665572 : if (error)
3919 3787165 : return error;
3920 945756814 : if (i == be32_to_cpu(agf->agf_fllast))
3921 : break;
3922 850840380 : if (++i == xfs_agfl_size(mp))
3923 0 : i = 0;
3924 : }
3925 :
3926 : return 0;
3927 : }
3928 :
3929 : int __init
3930 12 : xfs_extfree_intent_init_cache(void)
3931 : {
3932 12 : xfs_extfree_item_cache = kmem_cache_create("xfs_extfree_intent",
3933 : sizeof(struct xfs_extent_free_item),
3934 : 0, 0, NULL);
3935 :
3936 12 : return xfs_extfree_item_cache != NULL ? 0 : -ENOMEM;
3937 : }
3938 :
3939 : void
3940 12 : xfs_extfree_intent_destroy_cache(void)
3941 : {
3942 12 : kmem_cache_destroy(xfs_extfree_item_cache);
3943 12 : xfs_extfree_item_cache = NULL;
3944 12 : }
|
