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