Linux Audio

Check our new training course

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