xfs_alloc.c

linux 内核源代码

	/*
	 * Second algorithm.
	 * Search in the by-bno tree to the left and to the right
	 * simultaneously, until in each case we find a space big enough,
	 * or run into the edge of the tree.  When we run into the edge,
	 * we deallocate that cursor.
	 * If both searches succeed, we compare the two spaces and pick
	 * the better one.
	 * With alignment, it's possible for both to fail; the upper
	 * level algorithm that picks allocation groups for allocations
	 * is not supposed to do this.
	 */
	/*
	 * Allocate and initialize the cursor for the leftward search.
	 */
	bno_cur_lt = xfs_btree_init_cursor(args->mp, args->tp, args->agbp,
		args->agno, XFS_BTNUM_BNO, NULL, 0);
	/*
	 * Lookup <= bno to find the leftward search's starting point.
	 */
	if ((error = xfs_alloc_lookup_le(bno_cur_lt, args->agbno, args->maxlen, &i)))
		goto error0;
	if (!i) {
		/*
		 * Didn't find anything; use this cursor for the rightward
		 * search.
		 */
		bno_cur_gt = bno_cur_lt;
		bno_cur_lt = NULL;
	}
	/*
	 * Found something.  Duplicate the cursor for the rightward search.
	 */
	else if ((error = xfs_btree_dup_cursor(bno_cur_lt, &bno_cur_gt)))
		goto error0;
	/*
	 * Increment the cursor, so we will point at the entry just right
	 * of the leftward entry if any, or to the leftmost entry.
	 */
	if ((error = xfs_alloc_increment(bno_cur_gt, 0, &i)))
		goto error0;
	if (!i) {
		/*
		 * It failed, there are no rightward entries.
		 */
		xfs_btree_del_cursor(bno_cur_gt, XFS_BTREE_NOERROR);
		bno_cur_gt = NULL;
	}
	/*
	 * Loop going left with the leftward cursor, right with the
	 * rightward cursor, until either both directions give up or
	 * we find an entry at least as big as minlen.
	 */
	do {
		if (bno_cur_lt) {
			if ((error = xfs_alloc_get_rec(bno_cur_lt, &ltbno, &ltlen, &i)))
				goto error0;
			XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
			if (xfs_alloc_compute_aligned(ltbno, ltlen,
					args->alignment, args->minlen,
					&ltbnoa, &ltlena))
				break;
			if ((error = xfs_alloc_decrement(bno_cur_lt, 0, &i)))
				goto error0;
			if (!i) {
				xfs_btree_del_cursor(bno_cur_lt,
						     XFS_BTREE_NOERROR);
				bno_cur_lt = NULL;
			}
		}
		if (bno_cur_gt) {
			if ((error = xfs_alloc_get_rec(bno_cur_gt, &gtbno, &gtlen, &i)))
				goto error0;
			XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
			if (xfs_alloc_compute_aligned(gtbno, gtlen,
					args->alignment, args->minlen,
					&gtbnoa, &gtlena))
				break;
			if ((error = xfs_alloc_increment(bno_cur_gt, 0, &i)))
				goto error0;
			if (!i) {
				xfs_btree_del_cursor(bno_cur_gt,
						     XFS_BTREE_NOERROR);
				bno_cur_gt = NULL;
			}
		}
	} while (bno_cur_lt || bno_cur_gt);
	/*
	 * Got both cursors still active, need to find better entry.
	 */
	if (bno_cur_lt && bno_cur_gt) {
		/*
		 * Left side is long enough, look for a right side entry.
		 */
		if (ltlena >= args->minlen) {
			/*
			 * Fix up the length.
			 */
			args->len = XFS_EXTLEN_MIN(ltlena, args->maxlen);
			xfs_alloc_fix_len(args);
			rlen = args->len;
			ltdiff = xfs_alloc_compute_diff(args->agbno, rlen,
				args->alignment, ltbno, ltlen, &ltnew);
			/*
			 * Not perfect.
			 */
			if (ltdiff) {
				/*
				 * Look until we find a better one, run out of
				 * space, or run off the end.
				 */
				while (bno_cur_lt && bno_cur_gt) {
					if ((error = xfs_alloc_get_rec(
							bno_cur_gt, &gtbno,
							&gtlen, &i)))
						goto error0;
					XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
					xfs_alloc_compute_aligned(gtbno, gtlen,
						args->alignment, args->minlen,
						&gtbnoa, &gtlena);
					/*
					 * The left one is clearly better.
					 */
					if (gtbnoa >= args->agbno + ltdiff) {
						xfs_btree_del_cursor(
							bno_cur_gt,
							XFS_BTREE_NOERROR);
						bno_cur_gt = NULL;
						break;
					}
					/*
					 * If we reach a big enough entry,
					 * compare the two and pick the best.
					 */
					if (gtlena >= args->minlen) {
						args->len =
							XFS_EXTLEN_MIN(gtlena,
								args->maxlen);
						xfs_alloc_fix_len(args);
						rlen = args->len;
						gtdiff = xfs_alloc_compute_diff(
							args->agbno, rlen,
							args->alignment,
							gtbno, gtlen, &gtnew);
						/*
						 * Right side is better.
						 */
						if (gtdiff < ltdiff) {
							xfs_btree_del_cursor(
								bno_cur_lt,
								XFS_BTREE_NOERROR);
							bno_cur_lt = NULL;
						}
						/*
						 * Left side is better.
						 */
						else {
							xfs_btree_del_cursor(
								bno_cur_gt,
								XFS_BTREE_NOERROR);
							bno_cur_gt = NULL;
						}
						break;
					}
					/*
					 * Fell off the right end.
					 */
					if ((error = xfs_alloc_increment(
							bno_cur_gt, 0, &i)))
						goto error0;
					if (!i) {
						xfs_btree_del_cursor(
							bno_cur_gt,
							XFS_BTREE_NOERROR);
						bno_cur_gt = NULL;
						break;
					}
				}
			}
			/*
			 * The left side is perfect, trash the right side.
			 */
			else {
				xfs_btree_del_cursor(bno_cur_gt,
						     XFS_BTREE_NOERROR);
				bno_cur_gt = NULL;
			}
		}
		/*
		 * It's the right side that was found first, look left.
		 */
		else {
			/*
			 * Fix up the length.
			 */
			args->len = XFS_EXTLEN_MIN(gtlena, args->maxlen);
			xfs_alloc_fix_len(args);
			rlen = args->len;
			gtdiff = xfs_alloc_compute_diff(args->agbno, rlen,
				args->alignment, gtbno, gtlen, &gtnew);
			/*
			 * Right side entry isn't perfect.
			 */
			if (gtdiff) {
				/*
				 * Look until we find a better one, run out of
				 * space, or run off the end.
				 */
				while (bno_cur_lt && bno_cur_gt) {
					if ((error = xfs_alloc_get_rec(
							bno_cur_lt, &ltbno,
							&ltlen, &i)))
						goto error0;
					XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
					xfs_alloc_compute_aligned(ltbno, ltlen,
						args->alignment, args->minlen,
						&ltbnoa, &ltlena);
					/*
					 * The right one is clearly better.
					 */
					if (ltbnoa <= args->agbno - gtdiff) {
						xfs_btree_del_cursor(
							bno_cur_lt,
							XFS_BTREE_NOERROR);
						bno_cur_lt = NULL;
						break;
					}
					/*
					 * If we reach a big enough entry,
					 * compare the two and pick the best.
					 */
					if (ltlena >= args->minlen) {
						args->len = XFS_EXTLEN_MIN(
							ltlena, args->maxlen);
						xfs_alloc_fix_len(args);
						rlen = args->len;
						ltdiff = xfs_alloc_compute_diff(
							args->agbno, rlen,
							args->alignment,
							ltbno, ltlen, &ltnew);
						/*
						 * Left side is better.
						 */
						if (ltdiff < gtdiff) {
							xfs_btree_del_cursor(
								bno_cur_gt,
								XFS_BTREE_NOERROR);
							bno_cur_gt = NULL;
						}
						/*
						 * Right side is better.
						 */
						else {
							xfs_btree_del_cursor(
								bno_cur_lt,
								XFS_BTREE_NOERROR);
							bno_cur_lt = NULL;
						}
						break;
					}
					/*
					 * Fell off the left end.
					 */
					if ((error = xfs_alloc_decrement(
							bno_cur_lt, 0, &i)))
						goto error0;
					if (!i) {
						xfs_btree_del_cursor(bno_cur_lt,
							XFS_BTREE_NOERROR);
						bno_cur_lt = NULL;
						break;
					}
				}
			}
			/*
			 * The right side is perfect, trash the left side.
			 */
			else {
				xfs_btree_del_cursor(bno_cur_lt,
					XFS_BTREE_NOERROR);
				bno_cur_lt = NULL;
			}
		}
	}
	/*
	 * If we couldn't get anything, give up.
	 */
	if (bno_cur_lt == NULL && bno_cur_gt == NULL) {
		TRACE_ALLOC("neither", args);
		args->agbno = NULLAGBLOCK;
		return 0;
	}
	/*
	 * At this point we have selected a freespace entry, either to the
	 * left or to the right.  If it's on the right, copy all the
	 * useful variables to the "left" set so we only have one
	 * copy of this code.
	 */
	if (bno_cur_gt) {
		bno_cur_lt = bno_cur_gt;
		bno_cur_gt = NULL;
		ltbno = gtbno;
		ltbnoa = gtbnoa;
		ltlen = gtlen;
		ltlena = gtlena;
		j = 1;
	} else
		j = 0;
	/*
	 * Fix up the length and compute the useful address.
	 */
	ltend = ltbno + ltlen;
	args->len = XFS_EXTLEN_MIN(ltlena, args->maxlen);
	xfs_alloc_fix_len(args);
	if (!xfs_alloc_fix_minleft(args)) {
		TRACE_ALLOC("nominleft", args);
		xfs_btree_del_cursor(bno_cur_lt, XFS_BTREE_NOERROR);
		xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
		return 0;
	}
	rlen = args->len;
	(void)xfs_alloc_compute_diff(args->agbno, rlen, args->alignment, ltbno,
		ltlen, &ltnew);
	ASSERT(ltnew >= ltbno);
	ASSERT(ltnew + rlen <= ltend);
	ASSERT(ltnew + rlen <= be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length));
	args->agbno = ltnew;
	if ((error = xfs_alloc_fixup_trees(cnt_cur, bno_cur_lt, ltbno, ltlen,
			ltnew, rlen, XFSA_FIXUP_BNO_OK)))
		goto error0;
	TRACE_ALLOC(j ? "gt" : "lt", args);
	xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
	xfs_btree_del_cursor(bno_cur_lt, XFS_BTREE_NOERROR);
	return 0;

 error0:
	TRACE_ALLOC("error", args);
	if (cnt_cur != NULL)
		xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
	if (bno_cur_lt != NULL)
		xfs_btree_del_cursor(bno_cur_lt, XFS_BTREE_ERROR);
	if (bno_cur_gt != NULL)
		xfs_btree_del_cursor(bno_cur_gt, XFS_BTREE_ERROR);
	return error;
}

/*
 * Allocate a variable extent anywhere in the allocation group agno.
 * Extent's length (returned in len) will be between minlen and maxlen,
 * and of the form k * prod + mod unless there's nothing that large.
 * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
 */
STATIC int				/* error */
xfs_alloc_ag_vextent_size(
	xfs_alloc_arg_t	*args)		/* allocation argument structure */
{
	xfs_btree_cur_t	*bno_cur;	/* cursor for bno btree */
	xfs_btree_cur_t	*cnt_cur;	/* cursor for cnt btree */
	int		error;		/* error result */
	xfs_agblock_t	fbno;		/* start of found freespace */
	xfs_extlen_t	flen;		/* length of found freespace */
	int		i;		/* temp status variable */
	xfs_agblock_t	rbno;		/* returned block number */
	xfs_extlen_t	rlen;		/* length of returned extent */

	/*
	 * Allocate and initialize a cursor for the by-size btree.
	 */
	cnt_cur = xfs_btree_init_cursor(args->mp, args->tp, args->agbp,
		args->agno, XFS_BTNUM_CNT, NULL, 0);
	bno_cur = NULL;
	/*
	 * Look for an entry >= maxlen+alignment-1 blocks.
	 */
	if ((error = xfs_alloc_lookup_ge(cnt_cur, 0,
			args->maxlen + args->alignment - 1, &i)))
		goto error0;
	/*
	 * If none, then pick up the last entry in the tree unless the
	 * tree is empty.
	 */
	if (!i) {
		if ((error = xfs_alloc_ag_vextent_small(args, cnt_cur, &fbno,
				&flen, &i)))
			goto error0;
		if (i == 0 || flen == 0) {
			xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
			TRACE_ALLOC("noentry", args);
			return 0;
		}
		ASSERT(i == 1);
	}
	/*
	 * There's a freespace as big as maxlen+alignment-1, get it.
	 */
	else {
		if ((error = xfs_alloc_get_rec(cnt_cur, &fbno, &flen, &i)))
			goto error0;
		XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
	}
	/*
	 * In the first case above, we got the last entry in the
	 * by-size btree.  Now we check to see if the space hits maxlen
	 * once aligned; if not, we search left for something better.
	 * This can't happen in the second case above.
	 */
	xfs_alloc_compute_aligned(fbno, flen, args->alignment, args->minlen,
		&rbno, &rlen);
	rlen = XFS_EXTLEN_MIN(args->maxlen, rlen);
	XFS_WANT_CORRUPTED_GOTO(rlen == 0 ||
			(rlen <= flen && rbno + rlen <= fbno + flen), error0);
	if (rlen < args->maxlen) {
		xfs_agblock_t	bestfbno;
		xfs_extlen_t	bestflen;
		xfs_agblock_t	bestrbno;
		xfs_extlen_t	bestrlen;

		bestrlen = rlen;
		bestrbno = rbno;
		bestflen = flen;
		bestfbno = fbno;
		for (;;) {
			if ((error = xfs_alloc_decrement(cnt_cur, 0, &i)))
				goto error0;
			if (i == 0)
				break;
			if ((error = xfs_alloc_get_rec(cnt_cur, &fbno, &flen,
					&i)))
				goto error0;
			XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
			if (flen < bestrlen)
				break;
			xfs_alloc_compute_aligned(fbno, flen, args->alignment,
				args->minlen, &rbno, &rlen);
			rlen = XFS_EXTLEN_MIN(args->maxlen, rlen);
			XFS_WANT_CORRUPTED_GOTO(rlen == 0 ||
				(rlen <= flen && rbno + rlen <= fbno + flen),
				error0);
			if (rlen > bestrlen) {
				bestrlen = rlen;
				bestrbno = rbno;
				bestflen = flen;
				bestfbno = fbno;
				if (rlen == args->maxlen)
					break;
			}
		}
		if ((error = xfs_alloc_lookup_eq(cnt_cur, bestfbno, bestflen,
				&i)))
			goto error0;
		XFS_WANT_CORRUPTED_GOTO(i == 1, error0);