/*
   * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc.
   * Copyright (c) 2010 David Chinner.
   * Copyright (c) 2011 Christoph Hellwig.
   * All Rights Reserved.
   *
   * This program is free software; you can redistribute it and/or
   * modify it under the terms of the GNU General Public License as
   * published by the Free Software Foundation.
   *
   * This program is distributed in the hope that it would be useful,
   * but WITHOUT ANY WARRANTY; without even the implied warranty of
   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   * GNU General Public License for more details.
   *
   * You should have received a copy of the GNU General Public License
   * along with this program; if not, write the Free Software Foundation,
   * Inc.,  51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
   */
  #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_sb.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"
  
  void
  xfs_extent_busy_insert(
  	struct xfs_trans	*tp,
  	xfs_agnumber_t		agno,
  	xfs_agblock_t		bno,
  	xfs_extlen_t		len,
  	unsigned int		flags)
  {
  	struct xfs_extent_busy	*new;
  	struct xfs_extent_busy	*busyp;
  	struct xfs_perag	*pag;
  	struct rb_node		**rbp;
  	struct rb_node		*parent = NULL;
  
  	new = kmem_zalloc(sizeof(struct xfs_extent_busy), KM_MAYFAIL);
  	if (!new) {
  		/*
  		 * No Memory!  Since it is now not possible to track the free
  		 * block, make this a synchronous transaction to insure that
  		 * the block is not reused before this transaction commits.
  		 */
  		trace_xfs_extent_busy_enomem(tp->t_mountp, agno, bno, len);
  		xfs_trans_set_sync(tp);
  		return;
  	}
  
  	new->agno = 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, agno, bno, len);
  
  	pag = xfs_perag_get(tp->t_mountp, new->agno);
  	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);
  	xfs_perag_put(pag);
  }
  
  /*
   * 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,
  	xfs_agnumber_t		agno,
  	xfs_agblock_t		bno,
  	xfs_extlen_t		len)
  {
  	struct xfs_perag	*pag;
  	struct rb_node		*rbp;
  	struct xfs_extent_busy	*busyp;
  	int			match = 0;
  
  	pag = xfs_perag_get(mp, agno);
  	spin_lock(&pag->pagb_lock);
  
  	rbp = pag->pagb_tree.rb_node;
  
  	/* find closest start bno overlap */
  	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);
  	xfs_perag_put(pag);
  	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;
  	} 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,
  	xfs_agnumber_t		agno,
  	xfs_agblock_t		fbno,
  	xfs_extlen_t		flen,
  	bool			userdata)
  {
  	struct xfs_perag	*pag;
  	struct rb_node		*rbp;
  
  	ASSERT(flen > 0);
  
  	pag = xfs_perag_get(mp, agno);
  	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);
  	xfs_perag_put(pag);
  }
  
  /*
   * 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.
   */
  void
  xfs_extent_busy_trim(
  	struct xfs_alloc_arg	*args,
  	xfs_agblock_t		bno,
  	xfs_extlen_t		len,
  	xfs_agblock_t		*rbno,
  	xfs_extlen_t		*rlen)
  {
  	xfs_agblock_t		fbno;
  	xfs_extlen_t		flen;
  	struct rb_node		*rbp;
  
  	ASSERT(len > 0);
  
  	spin_lock(&args->pag->pagb_lock);
  restart:
  	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 this is a metadata allocation, try to reuse the busy
  		 * extent instead of trimming the allocation.
  		 */
  		if (!args->userdata &&
  		    !(busyp->flags & XFS_EXTENT_BUSY_DISCARDED)) {
  			if (!xfs_extent_busy_update_extent(args->mp, args->pag,
  							  busyp, fbno, flen,
  							  false))
  				goto restart;
  			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;
  	}
  	spin_unlock(&args->pag->pagb_lock);
  
  	if (fbno != bno || flen != len) {
  		trace_xfs_extent_busy_trim(args->mp, args->agno, bno, len,
  					  fbno, flen);
  	}
  	*rbno = fbno;
  	*rlen = flen;
  	return;
  fail:
  	/*
  	 * Return a zero extent length as failure indications.  All callers
  	 * re-check if the trimmed extent satisfies the minlen requirement.
  	 */
  	spin_unlock(&args->pag->pagb_lock);
  	trace_xfs_extent_busy_trim(args->mp, args->agno, bno, len, fbno, 0);
  	*rbno = fbno;
  	*rlen = 0;
  }
  
  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);
  }
  
  /*
   * 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;
  
  	list_for_each_entry_safe(busyp, n, list, list) {
  		if (busyp->agno != agno) {
  			if (pag) {
  				spin_unlock(&pag->pagb_lock);
  				xfs_perag_put(pag);
  			}
  			pag = xfs_perag_get(mp, busyp->agno);
  			spin_lock(&pag->pagb_lock);
  			agno = busyp->agno;
  		}
  
  		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);
  	}
  
  	if (pag) {
  		spin_unlock(&pag->pagb_lock);
  		xfs_perag_put(pag);
  	}
  }
  
  /*
   * Callback for list_sort to sort busy extents by the AG they reside in.
   */
  int
  xfs_extent_busy_ag_cmp(
  	void			*priv,
  	struct list_head	*a,
  	struct list_head	*b)
  {
  	return container_of(a, struct xfs_extent_busy, list)->agno -
  		container_of(b, struct xfs_extent_busy, list)->agno;
  }