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