[linux-block.git] / fs / xfs / xfs_extent_busy.c

// SPDX-License-Identifier: GPL-2.0
/*
 * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc.
 * Copyright (c) 2010 David Chinner.
 * Copyright (c) 2011 Christoph Hellwig.
 * All Rights Reserved.
 */
#include "xfs.h"
#include "xfs_fs.h"
#include "xfs_format.h"
#include "xfs_log_format.h"
#include "xfs_shared.h"
#include "xfs_trans_resv.h"
#include "xfs_mount.h"
#include "xfs_alloc.h"
#include "xfs_extent_busy.h"
#include "xfs_trace.h"
#include "xfs_trans.h"
#include "xfs_log.h"
#include "xfs_ag.h"

void
xfs_extent_busy_insert(
	struct xfs_trans	*tp,
	struct xfs_perag	*pag,
	xfs_agblock_t		bno,
	xfs_extlen_t		len,
	unsigned int		flags)
{
	struct xfs_extent_busy	*new;
	struct xfs_extent_busy	*busyp;
	struct rb_node		**rbp;
	struct rb_node		*parent = NULL;

	new = kmem_zalloc(sizeof(struct xfs_extent_busy), 0);
	new->agno = pag->pag_agno;
	new->bno = bno;
	new->length = len;
	INIT_LIST_HEAD(&new->list);
	new->flags = flags;

	/* trace before insert to be able to see failed inserts */
	trace_xfs_extent_busy(tp->t_mountp, pag->pag_agno, bno, len);

	spin_lock(&pag->pagb_lock);
	rbp = &pag->pagb_tree.rb_node;
	while (*rbp) {
		parent = *rbp;
		busyp = rb_entry(parent, struct xfs_extent_busy, rb_node);

		if (new->bno < busyp->bno) {
			rbp = &(*rbp)->rb_left;
			ASSERT(new->bno + new->length <= busyp->bno);
		} else if (new->bno > busyp->bno) {
			rbp = &(*rbp)->rb_right;
			ASSERT(bno >= busyp->bno + busyp->length);
		} else {
			ASSERT(0);
		}
	}

	rb_link_node(&new->rb_node, parent, rbp);
	rb_insert_color(&new->rb_node, &pag->pagb_tree);

	list_add(&new->list, &tp->t_busy);
	spin_unlock(&pag->pagb_lock);
}

/*
 * Search for a busy extent within the range of the extent we are about to
 * allocate.  You need to be holding the busy extent tree lock when calling
 * xfs_extent_busy_search(). This function returns 0 for no overlapping busy
 * extent, -1 for an overlapping but not exact busy extent, and 1 for an exact
 * match. This is done so that a non-zero return indicates an overlap that
 * will require a synchronous transaction, but it can still be
 * used to distinguish between a partial or exact match.
 */
int
xfs_extent_busy_search(
	struct xfs_mount	*mp,
	struct xfs_perag	*pag,
	xfs_agblock_t		bno,
	xfs_extlen_t		len)
{
	struct rb_node		*rbp;
	struct xfs_extent_busy	*busyp;
	int			match = 0;

	/* find closest start bno overlap */
	spin_lock(&pag->pagb_lock);
	rbp = pag->pagb_tree.rb_node;
	while (rbp) {
		busyp = rb_entry(rbp, struct xfs_extent_busy, rb_node);
		if (bno < busyp->bno) {
			/* may overlap, but exact start block is lower */
			if (bno + len > busyp->bno)
				match = -1;
			rbp = rbp->rb_left;
		} else if (bno > busyp->bno) {
			/* may overlap, but exact start block is higher */
			if (bno < busyp->bno + busyp->length)
				match = -1;
			rbp = rbp->rb_right;
		} else {
			/* bno matches busyp, length determines exact match */
			match = (busyp->length == len) ? 1 : -1;
			break;
		}
	}
	spin_unlock(&pag->pagb_lock);
	return match;
}

/*
 * The found free extent [fbno, fend] overlaps part or all of the given busy
 * extent.  If the overlap covers the beginning, the end, or all of the busy
 * extent, the overlapping portion can be made unbusy and used for the
 * allocation.  We can't split a busy extent because we can't modify a
 * transaction/CIL context busy list, but we can update an entry's block
 * number or length.
 *
 * Returns true if the extent can safely be reused, or false if the search
 * needs to be restarted.
 */
STATIC bool
xfs_extent_busy_update_extent(
	struct xfs_mount	*mp,
	struct xfs_perag	*pag,
	struct xfs_extent_busy	*busyp,
	xfs_agblock_t		fbno,
	xfs_extlen_t		flen,
	bool			userdata) __releases(&pag->pagb_lock)
					  __acquires(&pag->pagb_lock)
{
	xfs_agblock_t		fend = fbno + flen;
	xfs_agblock_t		bbno = busyp->bno;
	xfs_agblock_t		bend = bbno + busyp->length;

	/*
	 * This extent is currently being discarded.  Give the thread
	 * performing the discard a chance to mark the extent unbusy
	 * and retry.
	 */
	if (busyp->flags & XFS_EXTENT_BUSY_DISCARDED) {
		spin_unlock(&pag->pagb_lock);
		delay(1);
		spin_lock(&pag->pagb_lock);
		return false;
	}

	/*
	 * If there is a busy extent overlapping a user allocation, we have
	 * no choice but to force the log and retry the search.
	 *
	 * Fortunately this does not happen during normal operation, but
	 * only if the filesystem is very low on space and has to dip into
	 * the AGFL for normal allocations.
	 */
	if (userdata)
		goto out_force_log;

	if (bbno < fbno && bend > fend) {
		/*
		 * Case 1:
		 *    bbno           bend
		 *    +BBBBBBBBBBBBBBBBB+
		 *        +---------+
		 *        fbno   fend
		 */

		/*
		 * We would have to split the busy extent to be able to track
		 * it correct, which we cannot do because we would have to
		 * modify the list of busy extents attached to the transaction
		 * or CIL context, which is immutable.
		 *
		 * Force out the log to clear the busy extent and retry the
		 * search.
		 */
		goto out_force_log;
	} else if (bbno >= fbno && bend <= fend) {
		/*
		 * Case 2:
		 *    bbno           bend
		 *    +BBBBBBBBBBBBBBBBB+
		 *    +-----------------+
		 *    fbno           fend
		 *
		 * Case 3:
		 *    bbno           bend
		 *    +BBBBBBBBBBBBBBBBB+
		 *    +--------------------------+
		 *    fbno                    fend
		 *
		 * Case 4:
		 *             bbno           bend
		 *             +BBBBBBBBBBBBBBBBB+
		 *    +--------------------------+
		 *    fbno                    fend
		 *
		 * Case 5:
		 *             bbno           bend
		 *             +BBBBBBBBBBBBBBBBB+
		 *    +-----------------------------------+
		 *    fbno                             fend
		 *
		 */

		/*
		 * The busy extent is fully covered by the extent we are
		 * allocating, and can simply be removed from the rbtree.
		 * However we cannot remove it from the immutable list
		 * tracking busy extents in the transaction or CIL context,
		 * so set the length to zero to mark it invalid.
		 *
		 * We also need to restart the busy extent search from the
		 * tree root, because erasing the node can rearrange the
		 * tree topology.
		 */
		rb_erase(&busyp->rb_node, &pag->pagb_tree);
		busyp->length = 0;
		return false;
	} else if (fend < bend) {
		/*
		 * Case 6:
		 *              bbno           bend
		 *             +BBBBBBBBBBBBBBBBB+
		 *             +---------+
		 *             fbno   fend
		 *
		 * Case 7:
		 *             bbno           bend
		 *             +BBBBBBBBBBBBBBBBB+
		 *    +------------------+
		 *    fbno            fend
		 *
		 */
		busyp->bno = fend;
		busyp->length = bend - fend;
	} else if (bbno < fbno) {
		/*
		 * Case 8:
		 *    bbno           bend
		 *    +BBBBBBBBBBBBBBBBB+
		 *        +-------------+
		 *        fbno       fend
		 *
		 * Case 9:
		 *    bbno           bend
		 *    +BBBBBBBBBBBBBBBBB+
		 *        +----------------------+
		 *        fbno                fend
		 */
		busyp->length = fbno - busyp->bno;
	} else {
		ASSERT(0);
	}

	trace_xfs_extent_busy_reuse(mp, pag->pag_agno, fbno, flen);
	return true;

out_force_log:
	spin_unlock(&pag->pagb_lock);
	xfs_log_force(mp, XFS_LOG_SYNC);
	trace_xfs_extent_busy_force(mp, pag->pag_agno, fbno, flen);
	spin_lock(&pag->pagb_lock);
	return false;
}


/*
 * For a given extent [fbno, flen], make sure we can reuse it safely.
 */
void
xfs_extent_busy_reuse(
	struct xfs_mount	*mp,
	struct xfs_perag	*pag,
	xfs_agblock_t		fbno,
	xfs_extlen_t		flen,
	bool			userdata)
{
	struct rb_node		*rbp;

	ASSERT(flen > 0);
	spin_lock(&pag->pagb_lock);
restart:
	rbp = pag->pagb_tree.rb_node;
	while (rbp) {
		struct xfs_extent_busy *busyp =
			rb_entry(rbp, struct xfs_extent_busy, rb_node);
		xfs_agblock_t	bbno = busyp->bno;
		xfs_agblock_t	bend = bbno + busyp->length;

		if (fbno + flen <= bbno) {
			rbp = rbp->rb_left;
			continue;
		} else if (fbno >= bend) {
			rbp = rbp->rb_right;
			continue;
		}

		if (!xfs_extent_busy_update_extent(mp, pag, busyp, fbno, flen,
						  userdata))
			goto restart;
	}
	spin_unlock(&pag->pagb_lock);
}

/*
 * For a given extent [fbno, flen], search the busy extent list to find a
 * subset of the extent that is not busy.  If *rlen is smaller than
 * args->minlen no suitable extent could be found, and the higher level
 * code needs to force out the log and retry the allocation.
 *
 * Return the current busy generation for the AG if the extent is busy. This
 * value can be used to wait for at least one of the currently busy extents
 * to be cleared. Note that the busy list is not guaranteed to be empty after
 * the gen is woken. The state of a specific extent must always be confirmed
 * with another call to xfs_extent_busy_trim() before it can be used.
 */
bool
xfs_extent_busy_trim(
	struct xfs_alloc_arg	*args,
	xfs_agblock_t		*bno,
	xfs_extlen_t		*len,
	unsigned		*busy_gen)
{
	xfs_agblock_t		fbno;
	xfs_extlen_t		flen;
	struct rb_node		*rbp;
	bool			ret = false;

	ASSERT(*len > 0);

	spin_lock(&args->pag->pagb_lock);
	fbno = *bno;
	flen = *len;
	rbp = args->pag->pagb_tree.rb_node;
	while (rbp && flen >= args->minlen) {
		struct xfs_extent_busy *busyp =
			rb_entry(rbp, struct xfs_extent_busy, rb_node);
		xfs_agblock_t	fend = fbno + flen;
		xfs_agblock_t	bbno = busyp->bno;
		xfs_agblock_t	bend = bbno + busyp->length;

		if (fend <= bbno) {
			rbp = rbp->rb_left;
			continue;
		} else if (fbno >= bend) {
			rbp = rbp->rb_right;
			continue;
		}

		if (bbno <= fbno) {
			/* start overlap */

			/*
			 * Case 1:
			 *    bbno           bend
			 *    +BBBBBBBBBBBBBBBBB+
			 *        +---------+
			 *        fbno   fend
			 *
			 * Case 2:
			 *    bbno           bend
			 *    +BBBBBBBBBBBBBBBBB+
			 *    +-------------+
			 *    fbno       fend
			 *
			 * Case 3:
			 *    bbno           bend
			 *    +BBBBBBBBBBBBBBBBB+
			 *        +-------------+
			 *        fbno       fend
			 *
			 * Case 4:
			 *    bbno           bend
			 *    +BBBBBBBBBBBBBBBBB+
			 *    +-----------------+
			 *    fbno           fend
			 *
			 * No unbusy region in extent, return failure.
			 */
			if (fend <= bend)
				goto fail;

			/*
			 * Case 5:
			 *    bbno           bend
			 *    +BBBBBBBBBBBBBBBBB+
			 *        +----------------------+
			 *        fbno                fend
			 *
			 * Case 6:
			 *    bbno           bend
			 *    +BBBBBBBBBBBBBBBBB+
			 *    +--------------------------+
			 *    fbno                    fend
			 *
			 * Needs to be trimmed to:
			 *                       +-------+
			 *                       fbno fend
			 */
			fbno = bend;
		} else if (bend >= fend) {
			/* end overlap */

			/*
			 * Case 7:
			 *             bbno           bend
			 *             +BBBBBBBBBBBBBBBBB+
			 *    +------------------+
			 *    fbno            fend
			 *
			 * Case 8:
			 *             bbno           bend
			 *             +BBBBBBBBBBBBBBBBB+
			 *    +--------------------------+
			 *    fbno                    fend
			 *
			 * Needs to be trimmed to:
			 *    +-------+
			 *    fbno fend
			 */
			fend = bbno;
		} else {
			/* middle overlap */

			/*
			 * Case 9:
			 *             bbno           bend
			 *             +BBBBBBBBBBBBBBBBB+
			 *    +-----------------------------------+
			 *    fbno                             fend
			 *
			 * Can be trimmed to:
			 *    +-------+        OR         +-------+
			 *    fbno fend                   fbno fend
			 *
			 * Backward allocation leads to significant
			 * fragmentation of directories, which degrades
			 * directory performance, therefore we always want to
			 * choose the option that produces forward allocation
			 * patterns.
			 * Preferring the lower bno extent will make the next
			 * request use "fend" as the start of the next
			 * allocation;  if the segment is no longer busy at
			 * that point, we'll get a contiguous allocation, but
			 * even if it is still busy, we will get a forward
			 * allocation.
			 * We try to avoid choosing the segment at "bend",
			 * because that can lead to the next allocation
			 * taking the segment at "fbno", which would be a
			 * backward allocation.  We only use the segment at
			 * "fbno" if it is much larger than the current
			 * requested size, because in that case there's a
			 * good chance subsequent allocations will be
			 * contiguous.
			 */
			if (bbno - fbno >= args->maxlen) {
				/* left candidate fits perfect */
				fend = bbno;
			} else if (fend - bend >= args->maxlen * 4) {
				/* right candidate has enough free space */
				fbno = bend;
			} else if (bbno - fbno >= args->minlen) {
				/* left candidate fits minimum requirement */
				fend = bbno;
			} else {
				goto fail;
			}
		}

		flen = fend - fbno;
	}
out:

	if (fbno != *bno || flen != *len) {
		trace_xfs_extent_busy_trim(args->mp, args->agno, *bno, *len,
					  fbno, flen);
		*bno = fbno;
		*len = flen;
		*busy_gen = args->pag->pagb_gen;
		ret = true;
	}
	spin_unlock(&args->pag->pagb_lock);
	return ret;
fail:
	/*
	 * Return a zero extent length as failure indications.  All callers
	 * re-check if the trimmed extent satisfies the minlen requirement.
	 */
	flen = 0;
	goto out;
}

STATIC void
xfs_extent_busy_clear_one(
	struct xfs_mount	*mp,
	struct xfs_perag	*pag,
	struct xfs_extent_busy	*busyp)
{
	if (busyp->length) {
		trace_xfs_extent_busy_clear(mp, busyp->agno, busyp->bno,
						busyp->length);
		rb_erase(&busyp->rb_node, &pag->pagb_tree);
	}

	list_del_init(&busyp->list);
	kmem_free(busyp);
}

static void
xfs_extent_busy_put_pag(
	struct xfs_perag	*pag,
	bool			wakeup)
		__releases(pag->pagb_lock)
{
	if (wakeup) {
		pag->pagb_gen++;
		wake_up_all(&pag->pagb_wait);
	}

	spin_unlock(&pag->pagb_lock);
	xfs_perag_put(pag);
}

/*
 * Remove all extents on the passed in list from the busy extents tree.
 * If do_discard is set skip extents that need to be discarded, and mark
 * these as undergoing a discard operation instead.
 */
void
xfs_extent_busy_clear(
	struct xfs_mount	*mp,
	struct list_head	*list,
	bool			do_discard)
{
	struct xfs_extent_busy	*busyp, *n;
	struct xfs_perag	*pag = NULL;
	xfs_agnumber_t		agno = NULLAGNUMBER;
	bool			wakeup = false;

	list_for_each_entry_safe(busyp, n, list, list) {
		if (busyp->agno != agno) {
			if (pag)
				xfs_extent_busy_put_pag(pag, wakeup);
			agno = busyp->agno;
			pag = xfs_perag_get(mp, agno);
			spin_lock(&pag->pagb_lock);
			wakeup = false;
		}

		if (do_discard && busyp->length &&
		    !(busyp->flags & XFS_EXTENT_BUSY_SKIP_DISCARD)) {
			busyp->flags = XFS_EXTENT_BUSY_DISCARDED;
		} else {
			xfs_extent_busy_clear_one(mp, pag, busyp);
			wakeup = true;
		}
	}

	if (pag)
		xfs_extent_busy_put_pag(pag, wakeup);
}

/*
 * Flush out all busy extents for this AG.
 */
void
xfs_extent_busy_flush(
	struct xfs_mount	*mp,
	struct xfs_perag	*pag,
	unsigned		busy_gen)
{
	DEFINE_WAIT		(wait);
	int			error;

	error = xfs_log_force(mp, XFS_LOG_SYNC);
	if (error)
		return;

	do {
		prepare_to_wait(&pag->pagb_wait, &wait, TASK_KILLABLE);
		if  (busy_gen != READ_ONCE(pag->pagb_gen))
			break;
		schedule();
	} while (1);

	finish_wait(&pag->pagb_wait, &wait);
}

void
xfs_extent_busy_wait_all(
	struct xfs_mount	*mp)
{
	struct xfs_perag	*pag;
	DEFINE_WAIT		(wait);
	xfs_agnumber_t		agno;

	for_each_perag(mp, agno, pag) {
		do {
			prepare_to_wait(&pag->pagb_wait, &wait, TASK_KILLABLE);
			if  (RB_EMPTY_ROOT(&pag->pagb_tree))
				break;
			schedule();
		} while (1);
		finish_wait(&pag->pagb_wait, &wait);
	}
}

/*
 * Callback for list_sort to sort busy extents by the AG they reside in.
 */
int
xfs_extent_busy_ag_cmp(
	void			*priv,
	const struct list_head	*l1,
	const struct list_head	*l2)
{
	struct xfs_extent_busy	*b1 =
		container_of(l1, struct xfs_extent_busy, list);
	struct xfs_extent_busy	*b2 =
		container_of(l2, struct xfs_extent_busy, list);
	s32 diff;

	diff = b1->agno - b2->agno;
	if (!diff)
		diff = b1->bno - b2->bno;
	return diff;
}
Commit	Line	Data
0b61f8a4	1	// SPDX-License-Identifier: GPL-2.0
efc27b52 DC	2	/*
	3	* Copyright (c) 2000-2002,2005 Silicon Graphics, Inc.
	4	* Copyright (c) 2010 David Chinner.
	5	* Copyright (c) 2011 Christoph Hellwig.
	6	* All Rights Reserved.
efc27b52 DC	7	*/
	8	#include "xfs.h"
	9	#include "xfs_fs.h"
70a9883c	10	#include "xfs_format.h"
239880ef	11	#include "xfs_log_format.h"
70a9883c	12	#include "xfs_shared.h"
239880ef	13	#include "xfs_trans_resv.h"
efc27b52	14	#include "xfs_mount.h"
efc27b52	15	#include "xfs_alloc.h"
efc27b52 DC	16	#include "xfs_extent_busy.h"
efc27b52 DC	17	#include "xfs_trace.h"
239880ef DC	18	#include "xfs_trans.h"
239880ef DC	19	#include "xfs_log.h"
9bbafc71	20	#include "xfs_ag.h"
efc27b52 DC	21
efc27b52 DC	22	void
4ecbfe63	23	xfs_extent_busy_insert(
efc27b52	24	struct xfs_trans *tp,
45d06621	25	struct xfs_perag *pag,
efc27b52 DC	26	xfs_agblock_t bno,
	27	xfs_extlen_t len,
	28	unsigned int flags)
	29	{
4ecbfe63 DC	30	struct xfs_extent_busy *new;
4ecbfe63 DC	31	struct xfs_extent_busy *busyp;
efc27b52 DC	32	struct rb_node **rbp;
	33	struct rb_node *parent = NULL;
	34
707e0dda	35	new = kmem_zalloc(sizeof(struct xfs_extent_busy), 0);
45d06621	36	new->agno = pag->pag_agno;
efc27b52 DC	37	new->bno = bno;
	38	new->length = len;
	39	INIT_LIST_HEAD(&new->list);
	40	new->flags = flags;
	41
	42	/* trace before insert to be able to see failed inserts */
45d06621	43	trace_xfs_extent_busy(tp->t_mountp, pag->pag_agno, bno, len);
efc27b52	44
efc27b52 DC	45	spin_lock(&pag->pagb_lock);
	46	rbp = &pag->pagb_tree.rb_node;
	47	while (*rbp) {
	48	parent = *rbp;
4ecbfe63	49	busyp = rb_entry(parent, struct xfs_extent_busy, rb_node);
efc27b52 DC	50
	51	if (new->bno < busyp->bno) {
	52	rbp = &(*rbp)->rb_left;
	53	ASSERT(new->bno + new->length <= busyp->bno);
	54	} else if (new->bno > busyp->bno) {
	55	rbp = &(*rbp)->rb_right;
	56	ASSERT(bno >= busyp->bno + busyp->length);
	57	} else {
	58	ASSERT(0);
	59	}
	60	}
	61
	62	rb_link_node(&new->rb_node, parent, rbp);
	63	rb_insert_color(&new->rb_node, &pag->pagb_tree);
	64
	65	list_add(&new->list, &tp->t_busy);
	66	spin_unlock(&pag->pagb_lock);
efc27b52 DC	67	}
	68
	69	/*
	70	* Search for a busy extent within the range of the extent we are about to
	71	* allocate. You need to be holding the busy extent tree lock when calling
4ecbfe63	72	* xfs_extent_busy_search(). This function returns 0 for no overlapping busy
efc27b52 DC	73	* extent, -1 for an overlapping but not exact busy extent, and 1 for an exact
	74	* match. This is done so that a non-zero return indicates an overlap that
	75	* will require a synchronous transaction, but it can still be
	76	* used to distinguish between a partial or exact match.
	77	*/
	78	int
4ecbfe63	79	xfs_extent_busy_search(
efc27b52	80	struct xfs_mount *mp,
45d06621	81	struct xfs_perag *pag,
efc27b52 DC	82	xfs_agblock_t bno,
	83	xfs_extlen_t len)
	84	{
efc27b52	85	struct rb_node *rbp;
4ecbfe63	86	struct xfs_extent_busy *busyp;
efc27b52 DC	87	int match = 0;
efc27b52 DC	88
45d06621	89	/* find closest start bno overlap */
efc27b52	90	spin_lock(&pag->pagb_lock);
efc27b52	91	rbp = pag->pagb_tree.rb_node;
efc27b52	92	while (rbp) {
4ecbfe63	93	busyp = rb_entry(rbp, struct xfs_extent_busy, rb_node);
efc27b52 DC	94	if (bno < busyp->bno) {
	95	/* may overlap, but exact start block is lower */
	96	if (bno + len > busyp->bno)
	97	match = -1;
	98	rbp = rbp->rb_left;
	99	} else if (bno > busyp->bno) {
	100	/* may overlap, but exact start block is higher */
	101	if (bno < busyp->bno + busyp->length)
	102	match = -1;
	103	rbp = rbp->rb_right;
	104	} else {
	105	/* bno matches busyp, length determines exact match */
	106	match = (busyp->length == len) ? 1 : -1;
	107	break;
	108	}
	109	}
	110	spin_unlock(&pag->pagb_lock);
efc27b52 DC	111	return match;
	112	}
	113
	114	/*
	115	* The found free extent [fbno, fend] overlaps part or all of the given busy
	116	* extent. If the overlap covers the beginning, the end, or all of the busy
	117	* extent, the overlapping portion can be made unbusy and used for the
	118	* allocation. We can't split a busy extent because we can't modify a
b3c49634	119	* transaction/CIL context busy list, but we can update an entry's block
efc27b52 DC	120	* number or length.
	121	*
	122	* Returns true if the extent can safely be reused, or false if the search
	123	* needs to be restarted.
	124	*/
	125	STATIC bool
4ecbfe63	126	xfs_extent_busy_update_extent(
efc27b52 DC	127	struct xfs_mount *mp,
efc27b52 DC	128	struct xfs_perag *pag,
4ecbfe63	129	struct xfs_extent_busy *busyp,
efc27b52 DC	130	xfs_agblock_t fbno,
efc27b52 DC	131	xfs_extlen_t flen,
a30b0367 DC	132	bool userdata) __releases(&pag->pagb_lock)
a30b0367 DC	133	__acquires(&pag->pagb_lock)
efc27b52 DC	134	{
	135	xfs_agblock_t fend = fbno + flen;
	136	xfs_agblock_t bbno = busyp->bno;
	137	xfs_agblock_t bend = bbno + busyp->length;
	138
	139	/*
	140	* This extent is currently being discarded. Give the thread
	141	* performing the discard a chance to mark the extent unbusy
	142	* and retry.
	143	*/
4ecbfe63	144	if (busyp->flags & XFS_EXTENT_BUSY_DISCARDED) {
efc27b52 DC	145	spin_unlock(&pag->pagb_lock);
	146	delay(1);
	147	spin_lock(&pag->pagb_lock);
	148	return false;
	149	}
	150
	151	/*
	152	* If there is a busy extent overlapping a user allocation, we have
	153	* no choice but to force the log and retry the search.
	154	*
	155	* Fortunately this does not happen during normal operation, but
	156	* only if the filesystem is very low on space and has to dip into
	157	* the AGFL for normal allocations.
	158	*/
	159	if (userdata)
	160	goto out_force_log;
	161
	162	if (bbno < fbno && bend > fend) {
	163	/*
	164	* Case 1:
	165	* bbno bend
	166	* +BBBBBBBBBBBBBBBBB+
	167	* +---------+
	168	* fbno fend
	169	*/
	170
	171	/*
	172	* We would have to split the busy extent to be able to track
	173	* it correct, which we cannot do because we would have to
	174	* modify the list of busy extents attached to the transaction
	175	* or CIL context, which is immutable.
	176	*
	177	* Force out the log to clear the busy extent and retry the
	178	* search.
	179	*/
	180	goto out_force_log;
	181	} else if (bbno >= fbno && bend <= fend) {
	182	/*
	183	* Case 2:
	184	* bbno bend
	185	* +BBBBBBBBBBBBBBBBB+
	186	* +-----------------+
	187	* fbno fend
	188	*
	189	* Case 3:
	190	* bbno bend
	191	* +BBBBBBBBBBBBBBBBB+
	192	* +--------------------------+
	193	* fbno fend
	194	*
	195	* Case 4:
	196	* bbno bend
	197	* +BBBBBBBBBBBBBBBBB+
	198	* +--------------------------+
	199	* fbno fend
	200	*
	201	* Case 5:
	202	* bbno bend
	203	* +BBBBBBBBBBBBBBBBB+
	204	* +-----------------------------------+
	205	* fbno fend
	206	*
	207	*/
	208
209	/*
210	* The busy extent is fully covered by the extent we are
211	* allocating, and can simply be removed from the rbtree.
212	* However we cannot remove it from the immutable list
213	* tracking busy extents in the transaction or CIL context,
214	* so set the length to zero to mark it invalid.
215	*
216	* We also need to restart the busy extent search from the
217	* tree root, because erasing the node can rearrange the
218	* tree topology.
219	*/
220	rb_erase(&busyp->rb_node, &pag->pagb_tree);
221	busyp->length = 0;
222	return false;
223	} else if (fend < bend) {
224	/*
225	* Case 6:
226	* bbno bend
227	* +BBBBBBBBBBBBBBBBB+
228	* +---------+
229	* fbno fend
230	*
231	* Case 7:
232	* bbno bend
233	* +BBBBBBBBBBBBBBBBB+
234	* +------------------+
235	* fbno fend
236	*
237	*/
238	busyp->bno = fend;
601a27ea	239	busyp->length = bend - fend;
efc27b52 DC	240	} else if (bbno < fbno) {
	241	/*
	242	* Case 8:
	243	* bbno bend
	244	* +BBBBBBBBBBBBBBBBB+
	245	* +-------------+
	246	* fbno fend
	247	*
	248	* Case 9:
	249	* bbno bend
	250	* +BBBBBBBBBBBBBBBBB+
	251	* +----------------------+
	252	* fbno fend
	253	*/
	254	busyp->length = fbno - busyp->bno;
	255	} else {
	256	ASSERT(0);
	257	}
	258
4ecbfe63	259	trace_xfs_extent_busy_reuse(mp, pag->pag_agno, fbno, flen);
efc27b52 DC	260	return true;
	261
	262	out_force_log:
	263	spin_unlock(&pag->pagb_lock);
	264	xfs_log_force(mp, XFS_LOG_SYNC);
4ecbfe63	265	trace_xfs_extent_busy_force(mp, pag->pag_agno, fbno, flen);
efc27b52 DC	266	spin_lock(&pag->pagb_lock);
	267	return false;
	268	}
	269
	270
	271	/*
	272	* For a given extent [fbno, flen], make sure we can reuse it safely.
	273	*/
	274	void
4ecbfe63	275	xfs_extent_busy_reuse(
efc27b52	276	struct xfs_mount *mp,
45d06621	277	struct xfs_perag *pag,
efc27b52 DC	278	xfs_agblock_t fbno,
	279	xfs_extlen_t flen,
	280	bool userdata)
	281	{
efc27b52 DC	282	struct rb_node *rbp;
	283
	284	ASSERT(flen > 0);
efc27b52 DC	285	spin_lock(&pag->pagb_lock);
	286	restart:
	287	rbp = pag->pagb_tree.rb_node;
	288	while (rbp) {
4ecbfe63 DC	289	struct xfs_extent_busy *busyp =
4ecbfe63 DC	290	rb_entry(rbp, struct xfs_extent_busy, rb_node);
efc27b52 DC	291	xfs_agblock_t bbno = busyp->bno;
	292	xfs_agblock_t bend = bbno + busyp->length;
	293
	294	if (fbno + flen <= bbno) {
	295	rbp = rbp->rb_left;
	296	continue;
	297	} else if (fbno >= bend) {
	298	rbp = rbp->rb_right;
	299	continue;
	300	}
	301
4ecbfe63	302	if (!xfs_extent_busy_update_extent(mp, pag, busyp, fbno, flen,
efc27b52 DC	303	userdata))
	304	goto restart;
	305	}
	306	spin_unlock(&pag->pagb_lock);
efc27b52 DC	307	}
	308
	309	/*
	310	* For a given extent [fbno, flen], search the busy extent list to find a
	311	* subset of the extent that is not busy. If *rlen is smaller than
	312	* args->minlen no suitable extent could be found, and the higher level
	313	* code needs to force out the log and retry the allocation.
ebf55872 CH	314	*
	315	* Return the current busy generation for the AG if the extent is busy. This
	316	* value can be used to wait for at least one of the currently busy extents
	317	* to be cleared. Note that the busy list is not guaranteed to be empty after
	318	* the gen is woken. The state of a specific extent must always be confirmed
	319	* with another call to xfs_extent_busy_trim() before it can be used.
efc27b52	320	*/
ebf55872	321	bool
4ecbfe63	322	xfs_extent_busy_trim(
efc27b52	323	struct xfs_alloc_arg *args,
ebf55872 CH	324	xfs_agblock_t *bno,
	325	xfs_extlen_t *len,
	326	unsigned *busy_gen)
efc27b52 DC	327	{
	328	xfs_agblock_t fbno;
	329	xfs_extlen_t flen;
	330	struct rb_node *rbp;
ebf55872	331	bool ret = false;
efc27b52	332
353fe445	333	ASSERT(*len > 0);
efc27b52 DC	334
efc27b52 DC	335	spin_lock(&args->pag->pagb_lock);
ebf55872 CH	336	fbno = *bno;
ebf55872 CH	337	flen = *len;
efc27b52 DC	338	rbp = args->pag->pagb_tree.rb_node;
efc27b52 DC	339	while (rbp && flen >= args->minlen) {
4ecbfe63 DC	340	struct xfs_extent_busy *busyp =
4ecbfe63 DC	341	rb_entry(rbp, struct xfs_extent_busy, rb_node);
efc27b52 DC	342	xfs_agblock_t fend = fbno + flen;
	343	xfs_agblock_t bbno = busyp->bno;
	344	xfs_agblock_t bend = bbno + busyp->length;
	345
	346	if (fend <= bbno) {
	347	rbp = rbp->rb_left;
	348	continue;
	349	} else if (fbno >= bend) {
	350	rbp = rbp->rb_right;
	351	continue;
	352	}
	353
efc27b52 DC	354	if (bbno <= fbno) {
	355	/* start overlap */
	356
	357	/*
	358	* Case 1:
	359	* bbno bend
	360	* +BBBBBBBBBBBBBBBBB+
	361	* +---------+
	362	* fbno fend
	363	*
	364	* Case 2:
	365	* bbno bend
	366	* +BBBBBBBBBBBBBBBBB+
	367	* +-------------+
	368	* fbno fend
	369	*
	370	* Case 3:
	371	* bbno bend
	372	* +BBBBBBBBBBBBBBBBB+
	373	* +-------------+
	374	* fbno fend
	375	*
	376	* Case 4:
	377	* bbno bend
	378	* +BBBBBBBBBBBBBBBBB+
	379	* +-----------------+
	380	* fbno fend
	381	*
	382	* No unbusy region in extent, return failure.
	383	*/
	384	if (fend <= bend)
	385	goto fail;
	386
	387	/*
	388	* Case 5:
	389	* bbno bend
	390	* +BBBBBBBBBBBBBBBBB+
	391	* +----------------------+
	392	* fbno fend
	393	*
	394	* Case 6:
	395	* bbno bend
	396	* +BBBBBBBBBBBBBBBBB+
	397	* +--------------------------+
	398	* fbno fend
	399	*
	400	* Needs to be trimmed to:
	401	* +-------+
	402	* fbno fend
	403	*/
	404	fbno = bend;
	405	} else if (bend >= fend) {
	406	/* end overlap */
	407
	408	/*
	409	* Case 7:
	410	* bbno bend
	411	* +BBBBBBBBBBBBBBBBB+
	412	* +------------------+
	413	* fbno fend
	414	*
	415	* Case 8:
	416	* bbno bend
	417	* +BBBBBBBBBBBBBBBBB+
418	* +--------------------------+
419	* fbno fend
420	*
421	* Needs to be trimmed to:
422	* +-------+
423	* fbno fend
424	*/
425	fend = bbno;
426	} else {
427	/* middle overlap */
428
429	/*
430	* Case 9:
431	* bbno bend
432	* +BBBBBBBBBBBBBBBBB+
433	* +-----------------------------------+
434	* fbno fend
435	*
436	* Can be trimmed to:
437	* +-------+ OR +-------+
438	* fbno fend fbno fend
439	*
440	* Backward allocation leads to significant
441	* fragmentation of directories, which degrades
442	* directory performance, therefore we always want to
443	* choose the option that produces forward allocation
444	* patterns.
445	* Preferring the lower bno extent will make the next
446	* request use "fend" as the start of the next
447	* allocation; if the segment is no longer busy at
448	* that point, we'll get a contiguous allocation, but
449	* even if it is still busy, we will get a forward
450	* allocation.
451	* We try to avoid choosing the segment at "bend",
452	* because that can lead to the next allocation
453	* taking the segment at "fbno", which would be a
454	* backward allocation. We only use the segment at
455	* "fbno" if it is much larger than the current
456	* requested size, because in that case there's a
457	* good chance subsequent allocations will be
458	* contiguous.
459	*/
460	if (bbno - fbno >= args->maxlen) {
461	/* left candidate fits perfect */
462	fend = bbno;
463	} else if (fend - bend >= args->maxlen * 4) {
464	/* right candidate has enough free space */
465	fbno = bend;
466	} else if (bbno - fbno >= args->minlen) {
467	/* left candidate fits minimum requirement */
468	fend = bbno;
469	} else {
470	goto fail;
471	}
472	}
473
474	flen = fend - fbno;
475	}
ebf55872	476	out:
efc27b52	477
ebf55872 CH	478	if (fbno != bno \|\| flen != len) {
ebf55872 CH	479	trace_xfs_extent_busy_trim(args->mp, args->agno, bno, len,
efc27b52	480	fbno, flen);
ebf55872 CH	481	*bno = fbno;
	482	*len = flen;
	483	*busy_gen = args->pag->pagb_gen;
	484	ret = true;
efc27b52	485	}
ebf55872 CH	486	spin_unlock(&args->pag->pagb_lock);
ebf55872 CH	487	return ret;
efc27b52 DC	488	fail:
	489	/*
	490	* Return a zero extent length as failure indications. All callers
	491	* re-check if the trimmed extent satisfies the minlen requirement.
	492	*/
ebf55872 CH	493	flen = 0;
ebf55872 CH	494	goto out;
efc27b52 DC	495	}
efc27b52 DC	496
4ecbfe63 DC	497	STATIC void
4ecbfe63 DC	498	xfs_extent_busy_clear_one(
efc27b52 DC	499	struct xfs_mount *mp,
efc27b52 DC	500	struct xfs_perag *pag,
4ecbfe63	501	struct xfs_extent_busy *busyp)
efc27b52 DC	502	{
efc27b52 DC	503	if (busyp->length) {
4ecbfe63	504	trace_xfs_extent_busy_clear(mp, busyp->agno, busyp->bno,
efc27b52 DC	505	busyp->length);
	506	rb_erase(&busyp->rb_node, &pag->pagb_tree);
	507	}
	508
	509	list_del_init(&busyp->list);
	510	kmem_free(busyp);
	511	}
	512
ebf55872 CH	513	static void
	514	xfs_extent_busy_put_pag(
	515	struct xfs_perag *pag,
	516	bool wakeup)
	517	__releases(pag->pagb_lock)
	518	{
	519	if (wakeup) {
	520	pag->pagb_gen++;
	521	wake_up_all(&pag->pagb_wait);
	522	}
	523
	524	spin_unlock(&pag->pagb_lock);
	525	xfs_perag_put(pag);
	526	}
	527
efc27b52 DC	528	/*
	529	* Remove all extents on the passed in list from the busy extents tree.
	530	* If do_discard is set skip extents that need to be discarded, and mark
	531	* these as undergoing a discard operation instead.
	532	*/
	533	void
4ecbfe63	534	xfs_extent_busy_clear(
efc27b52 DC	535	struct xfs_mount *mp,
	536	struct list_head *list,
	537	bool do_discard)
	538	{
4ecbfe63	539	struct xfs_extent_busy busyp, n;
efc27b52 DC	540	struct xfs_perag *pag = NULL;
efc27b52 DC	541	xfs_agnumber_t agno = NULLAGNUMBER;
ebf55872	542	bool wakeup = false;
efc27b52 DC	543
	544	list_for_each_entry_safe(busyp, n, list, list) {
	545	if (busyp->agno != agno) {
ebf55872 CH	546	if (pag)
ebf55872 CH	547	xfs_extent_busy_put_pag(pag, wakeup);
efc27b52	548	agno = busyp->agno;
ebf55872 CH	549	pag = xfs_perag_get(mp, agno);
	550	spin_lock(&pag->pagb_lock);
	551	wakeup = false;
efc27b52 DC	552	}
	553
	554	if (do_discard && busyp->length &&
ebf55872	555	!(busyp->flags & XFS_EXTENT_BUSY_SKIP_DISCARD)) {
4ecbfe63	556	busyp->flags = XFS_EXTENT_BUSY_DISCARDED;
ebf55872	557	} else {
4ecbfe63	558	xfs_extent_busy_clear_one(mp, pag, busyp);
ebf55872 CH	559	wakeup = true;
ebf55872 CH	560	}
efc27b52 DC	561	}
efc27b52 DC	562
ebf55872 CH	563	if (pag)
	564	xfs_extent_busy_put_pag(pag, wakeup);
	565	}
	566
	567	/*
	568	* Flush out all busy extents for this AG.
	569	*/
	570	void
	571	xfs_extent_busy_flush(
	572	struct xfs_mount *mp,
	573	struct xfs_perag *pag,
	574	unsigned busy_gen)
	575	{
	576	DEFINE_WAIT (wait);
2b56c285	577	int error;
ebf55872	578
60e5bb78	579	error = xfs_log_force(mp, XFS_LOG_SYNC);
ebf55872 CH	580	if (error)
	581	return;
	582
	583	do {
	584	prepare_to_wait(&pag->pagb_wait, &wait, TASK_KILLABLE);
	585	if (busy_gen != READ_ONCE(pag->pagb_gen))
	586	break;
	587	schedule();
	588	} while (1);
	589
	590	finish_wait(&pag->pagb_wait, &wait);
	591	}
	592
	593	void
	594	xfs_extent_busy_wait_all(
	595	struct xfs_mount *mp)
	596	{
f250eedc	597	struct xfs_perag *pag;
ebf55872 CH	598	DEFINE_WAIT (wait);
	599	xfs_agnumber_t agno;
	600
f250eedc	601	for_each_perag(mp, agno, pag) {
ebf55872 CH	602	do {
	603	prepare_to_wait(&pag->pagb_wait, &wait, TASK_KILLABLE);
	604	if (RB_EMPTY_ROOT(&pag->pagb_tree))
	605	break;
	606	schedule();
	607	} while (1);
	608	finish_wait(&pag->pagb_wait, &wait);
efc27b52 DC	609	}
	610	}
	611
	612	/*
	613	* Callback for list_sort to sort busy extents by the AG they reside in.
	614	*/
	615	int
4ecbfe63	616	xfs_extent_busy_ag_cmp(
efc27b52	617	void *priv,
4f0f586b ST	618	const struct list_head *l1,
4f0f586b ST	619	const struct list_head *l2)
efc27b52	620	{
46694129 CH	621	struct xfs_extent_busy *b1 =
	622	container_of(l1, struct xfs_extent_busy, list);
	623	struct xfs_extent_busy *b2 =
	624	container_of(l2, struct xfs_extent_busy, list);
	625	s32 diff;
	626
	627	diff = b1->agno - b2->agno;
	628	if (!diff)
	629	diff = b1->bno - b2->bno;
	630	return diff;
efc27b52	631	}