/*

   * Copyright (c) 2000-2006 Silicon Graphics, Inc.

   * 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_types.h"

  #include "xfs_bit.h"

  #include "xfs_log.h"

  #include "xfs_inum.h"

  #include "xfs_trans.h"
  #include "xfs_sb.h"
  #include "xfs_ag.h"

  #include "xfs_dir2.h"

  #include "xfs_da_btree.h"

  #include "xfs_bmap_btree.h"

  #include "xfs_alloc_btree.h"

  #include "xfs_ialloc_btree.h"

  #include "xfs_dinode.h"

  #include "xfs_inode.h"

  #include "xfs_btree.h"

  #include "xfs_mount.h"

  #include "xfs_itable.h"

  #include "xfs_inode_item.h"

  #include "xfs_extfree_item.h"
  #include "xfs_alloc.h"
  #include "xfs_bmap.h"
  #include "xfs_rtalloc.h"
  #include "xfs_error.h"

  #include "xfs_attr_leaf.h"

  #include "xfs_rw.h"
  #include "xfs_quota.h"
  #include "xfs_trans_space.h"
  #include "xfs_buf_item.h"

  #include "xfs_filestream.h"

  #include "xfs_vnodeops.h"

  #include "xfs_trace.h"

  kmem_zone_t		*xfs_bmap_free_item_zone;
  
  /*
   * Prototypes for internal bmap routines.
   */

  #ifdef DEBUG
  STATIC void
  xfs_bmap_check_leaf_extents(
  	struct xfs_btree_cur	*cur,
  	struct xfs_inode	*ip,
  	int			whichfork);
  #else
  #define xfs_bmap_check_leaf_extents(cur, ip, whichfork)		do { } while (0)
  #endif

  
  /*
   * Called from xfs_bmap_add_attrfork to handle extents format files.
   */
  STATIC int					/* error */
  xfs_bmap_add_attrfork_extents(
  	xfs_trans_t		*tp,		/* transaction pointer */
  	xfs_inode_t		*ip,		/* incore inode pointer */
  	xfs_fsblock_t		*firstblock,	/* first block allocated */
  	xfs_bmap_free_t		*flist,		/* blocks to free at commit */
  	int			*flags);	/* inode logging flags */
  
  /*
   * Called from xfs_bmap_add_attrfork to handle local format files.
   */
  STATIC int					/* error */
  xfs_bmap_add_attrfork_local(
  	xfs_trans_t		*tp,		/* transaction pointer */
  	xfs_inode_t		*ip,		/* incore inode pointer */
  	xfs_fsblock_t		*firstblock,	/* first block allocated */
  	xfs_bmap_free_t		*flist,		/* blocks to free at commit */
  	int			*flags);	/* inode logging flags */
  
  /*

   * xfs_bmap_alloc is called by xfs_bmapi to allocate an extent for a file.
   * It figures out where to ask the underlying allocator to put the new extent.
   */
  STATIC int				/* error */
  xfs_bmap_alloc(
  	xfs_bmalloca_t		*ap);	/* bmap alloc argument struct */
  
  /*
   * Transform a btree format file with only one leaf node, where the
   * extents list will fit in the inode, into an extents format file.

   * Since the file extents are already in-core, all we have to do is

   * give up the space for the btree root and pitch the leaf block.
   */
  STATIC int				/* error */
  xfs_bmap_btree_to_extents(
  	xfs_trans_t		*tp,	/* transaction pointer */
  	xfs_inode_t		*ip,	/* incore inode pointer */
  	xfs_btree_cur_t		*cur,	/* btree cursor */
  	int			*logflagsp, /* inode logging flags */
  	int			whichfork); /* data or attr fork */

  /*

   * Remove the entry "free" from the free item list.  Prev points to the
   * previous entry, unless "free" is the head of the list.
   */
  STATIC void
  xfs_bmap_del_free(
  	xfs_bmap_free_t		*flist,	/* free item list header */
  	xfs_bmap_free_item_t	*prev,	/* previous item on list, if any */
  	xfs_bmap_free_item_t	*free);	/* list item to be freed */
  
  /*

   * Convert an extents-format file into a btree-format file.
   * The new file will have a root block (in the inode) and a single child block.
   */
  STATIC int					/* error */
  xfs_bmap_extents_to_btree(
  	xfs_trans_t		*tp,		/* transaction pointer */
  	xfs_inode_t		*ip,		/* incore inode pointer */
  	xfs_fsblock_t		*firstblock,	/* first-block-allocated */
  	xfs_bmap_free_t		*flist,		/* blocks freed in xaction */
  	xfs_btree_cur_t		**curp,		/* cursor returned to caller */
  	int			wasdel,		/* converting a delayed alloc */
  	int			*logflagsp,	/* inode logging flags */
  	int			whichfork);	/* data or attr fork */
  
  /*

   * Convert a local file to an extents file.
   * This code is sort of bogus, since the file data needs to get
   * logged so it won't be lost.  The bmap-level manipulations are ok, though.
   */
  STATIC int				/* error */
  xfs_bmap_local_to_extents(
  	xfs_trans_t	*tp,		/* transaction pointer */
  	xfs_inode_t	*ip,		/* incore inode pointer */
  	xfs_fsblock_t	*firstblock,	/* first block allocated in xaction */
  	xfs_extlen_t	total,		/* total blocks needed by transaction */
  	int		*logflagsp,	/* inode logging flags */
  	int		whichfork);	/* data or attr fork */
  
  /*
   * Search the extents list for the inode, for the extent containing bno.
   * If bno lies in a hole, point to the next entry.  If bno lies past eof,
   * *eofp will be set, and *prevp will contain the last entry (null if none).
   * Else, *lastxp will be set to the index of the found
   * entry; *gotp will contain the entry.
   */

  STATIC xfs_bmbt_rec_host_t *		/* pointer to found extent entry */

  xfs_bmap_search_extents(
  	xfs_inode_t	*ip,		/* incore inode pointer */
  	xfs_fileoff_t	bno,		/* block number searched for */
  	int		whichfork,	/* data or attr fork */
  	int		*eofp,		/* out: end of file found */
  	xfs_extnum_t	*lastxp,	/* out: last extent index */
  	xfs_bmbt_irec_t	*gotp,		/* out: extent entry found */
  	xfs_bmbt_irec_t	*prevp);	/* out: previous extent entry found */

  /*

   * Compute the worst-case number of indirect blocks that will be used
   * for ip's delayed extent of length "len".
   */
  STATIC xfs_filblks_t
  xfs_bmap_worst_indlen(
  	xfs_inode_t		*ip,	/* incore inode pointer */
  	xfs_filblks_t		len);	/* delayed extent length */
  
  #ifdef DEBUG
  /*
   * Perform various validation checks on the values being returned
   * from xfs_bmapi().
   */
  STATIC void
  xfs_bmap_validate_ret(
  	xfs_fileoff_t		bno,
  	xfs_filblks_t		len,
  	int			flags,
  	xfs_bmbt_irec_t		*mval,
  	int			nmap,
  	int			ret_nmap);
  #else
  #define	xfs_bmap_validate_ret(bno,len,flags,mval,onmap,nmap)
  #endif /* DEBUG */

  STATIC int
  xfs_bmap_count_tree(
  	xfs_mount_t     *mp,
  	xfs_trans_t     *tp,

  	xfs_ifork_t	*ifp,

  	xfs_fsblock_t   blockno,
  	int             levelin,
  	int		*count);

  STATIC void

  xfs_bmap_count_leaves(

  	xfs_ifork_t		*ifp,
  	xfs_extnum_t		idx,

  	int			numrecs,
  	int			*count);

  STATIC void

  xfs_bmap_disk_count_leaves(

  	struct xfs_mount	*mp,

  	struct xfs_btree_block	*block,

  	int			numrecs,
  	int			*count);

  /*
   * Bmap internal routines.
   */

  STATIC int				/* error */
  xfs_bmbt_lookup_eq(
  	struct xfs_btree_cur	*cur,
  	xfs_fileoff_t		off,
  	xfs_fsblock_t		bno,
  	xfs_filblks_t		len,
  	int			*stat)	/* success/failure */
  {
  	cur->bc_rec.b.br_startoff = off;
  	cur->bc_rec.b.br_startblock = bno;
  	cur->bc_rec.b.br_blockcount = len;
  	return xfs_btree_lookup(cur, XFS_LOOKUP_EQ, stat);
  }
  
  STATIC int				/* error */
  xfs_bmbt_lookup_ge(
  	struct xfs_btree_cur	*cur,
  	xfs_fileoff_t		off,
  	xfs_fsblock_t		bno,
  	xfs_filblks_t		len,
  	int			*stat)	/* success/failure */
  {
  	cur->bc_rec.b.br_startoff = off;
  	cur->bc_rec.b.br_startblock = bno;
  	cur->bc_rec.b.br_blockcount = len;
  	return xfs_btree_lookup(cur, XFS_LOOKUP_GE, stat);
  }

  /*
  * Update the record referred to by cur to the value given
   * by [off, bno, len, state].
   * This either works (return 0) or gets an EFSCORRUPTED error.
   */
  STATIC int
  xfs_bmbt_update(
  	struct xfs_btree_cur	*cur,
  	xfs_fileoff_t		off,
  	xfs_fsblock_t		bno,
  	xfs_filblks_t		len,
  	xfs_exntst_t		state)
  {
  	union xfs_btree_rec	rec;
  
  	xfs_bmbt_disk_set_allf(&rec.bmbt, off, bno, len, state);
  	return xfs_btree_update(cur, &rec);
  }

  /*
   * Called from xfs_bmap_add_attrfork to handle btree format files.
   */
  STATIC int					/* error */
  xfs_bmap_add_attrfork_btree(
  	xfs_trans_t		*tp,		/* transaction pointer */
  	xfs_inode_t		*ip,		/* incore inode pointer */
  	xfs_fsblock_t		*firstblock,	/* first block allocated */
  	xfs_bmap_free_t		*flist,		/* blocks to free at commit */
  	int			*flags)		/* inode logging flags */
  {
  	xfs_btree_cur_t		*cur;		/* btree cursor */
  	int			error;		/* error return value */
  	xfs_mount_t		*mp;		/* file system mount struct */
  	int			stat;		/* newroot status */
  
  	mp = ip->i_mount;
  	if (ip->i_df.if_broot_bytes <= XFS_IFORK_DSIZE(ip))
  		*flags |= XFS_ILOG_DBROOT;
  	else {

  		cur = xfs_bmbt_init_cursor(mp, tp, ip, XFS_DATA_FORK);

  		cur->bc_private.b.flist = flist;
  		cur->bc_private.b.firstblock = *firstblock;
  		if ((error = xfs_bmbt_lookup_ge(cur, 0, 0, 0, &stat)))
  			goto error0;

  		/* must be at least one entry */
  		XFS_WANT_CORRUPTED_GOTO(stat == 1, error0);

  		if ((error = xfs_btree_new_iroot(cur, flags, &stat)))

  			goto error0;
  		if (stat == 0) {
  			xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR);
  			return XFS_ERROR(ENOSPC);
  		}
  		*firstblock = cur->bc_private.b.firstblock;
  		cur->bc_private.b.allocated = 0;
  		xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR);
  	}
  	return 0;
  error0:
  	xfs_btree_del_cursor(cur, XFS_BTREE_ERROR);
  	return error;
  }
  
  /*
   * Called from xfs_bmap_add_attrfork to handle extents format files.
   */
  STATIC int					/* error */
  xfs_bmap_add_attrfork_extents(
  	xfs_trans_t		*tp,		/* transaction pointer */
  	xfs_inode_t		*ip,		/* incore inode pointer */
  	xfs_fsblock_t		*firstblock,	/* first block allocated */
  	xfs_bmap_free_t		*flist,		/* blocks to free at commit */
  	int			*flags)		/* inode logging flags */
  {
  	xfs_btree_cur_t		*cur;		/* bmap btree cursor */
  	int			error;		/* error return value */
  
  	if (ip->i_d.di_nextents * sizeof(xfs_bmbt_rec_t) <= XFS_IFORK_DSIZE(ip))
  		return 0;
  	cur = NULL;
  	error = xfs_bmap_extents_to_btree(tp, ip, firstblock, flist, &cur, 0,
  		flags, XFS_DATA_FORK);
  	if (cur) {
  		cur->bc_private.b.allocated = 0;
  		xfs_btree_del_cursor(cur,
  			error ? XFS_BTREE_ERROR : XFS_BTREE_NOERROR);
  	}
  	return error;
  }
  
  /*
   * Called from xfs_bmap_add_attrfork to handle local format files.
   */
  STATIC int					/* error */
  xfs_bmap_add_attrfork_local(
  	xfs_trans_t		*tp,		/* transaction pointer */
  	xfs_inode_t		*ip,		/* incore inode pointer */
  	xfs_fsblock_t		*firstblock,	/* first block allocated */
  	xfs_bmap_free_t		*flist,		/* blocks to free at commit */
  	int			*flags)		/* inode logging flags */
  {
  	xfs_da_args_t		dargs;		/* args for dir/attr code */
  	int			error;		/* error return value */
  	xfs_mount_t		*mp;		/* mount structure pointer */
  
  	if (ip->i_df.if_bytes <= XFS_IFORK_DSIZE(ip))
  		return 0;

  	if (S_ISDIR(ip->i_d.di_mode)) {

  		mp = ip->i_mount;
  		memset(&dargs, 0, sizeof(dargs));
  		dargs.dp = ip;
  		dargs.firstblock = firstblock;
  		dargs.flist = flist;
  		dargs.total = mp->m_dirblkfsbs;
  		dargs.whichfork = XFS_DATA_FORK;
  		dargs.trans = tp;

  		error = xfs_dir2_sf_to_block(&dargs);

  	} else
  		error = xfs_bmap_local_to_extents(tp, ip, firstblock, 1, flags,
  			XFS_DATA_FORK);
  	return error;
  }
  
  /*

   * Convert a delayed allocation to a real allocation.

   */
  STATIC int				/* error */
  xfs_bmap_add_extent_delay_real(

  	struct xfs_bmalloca	*bma)

  {

  	struct xfs_bmbt_irec	*new = &bma->got;

  	int			diff;	/* temp value */

  	xfs_bmbt_rec_host_t	*ep;	/* extent entry for idx */

  	int			error;	/* error return value */

  	int			i;	/* temp state */

  	xfs_ifork_t		*ifp;	/* inode fork pointer */

  	xfs_fileoff_t		new_endoff;	/* end offset of new entry */
  	xfs_bmbt_irec_t		r[3];	/* neighbor extent entries */
  					/* left is 0, right is 1, prev is 2 */
  	int			rval=0;	/* return value (logging flags) */
  	int			state = 0;/* state bits, accessed thru macros */

  	xfs_filblks_t		da_new; /* new count del alloc blocks used */
  	xfs_filblks_t		da_old; /* old count del alloc blocks used */
  	xfs_filblks_t		temp=0;	/* value for da_new calculations */
  	xfs_filblks_t		temp2=0;/* value for da_new calculations */

  	int			tmp_rval;	/* partial logging flags */

  	ifp = XFS_IFORK_PTR(bma->ip, XFS_DATA_FORK);

  	ASSERT(bma->idx >= 0);
  	ASSERT(bma->idx <= ifp->if_bytes / sizeof(struct xfs_bmbt_rec));

  	ASSERT(!isnullstartblock(new->br_startblock));

  	ASSERT(!bma->cur ||
  	       (bma->cur->bc_private.b.flags & XFS_BTCUR_BPRV_WASDEL));

  
  	XFS_STATS_INC(xs_add_exlist);

  #define	LEFT		r[0]
  #define	RIGHT		r[1]
  #define	PREV		r[2]

  
  	/*
  	 * Set up a bunch of variables to make the tests simpler.
  	 */

  	ep = xfs_iext_get_ext(ifp, bma->idx);

  	xfs_bmbt_get_all(ep, &PREV);
  	new_endoff = new->br_startoff + new->br_blockcount;
  	ASSERT(PREV.br_startoff <= new->br_startoff);
  	ASSERT(PREV.br_startoff + PREV.br_blockcount >= new_endoff);

  	da_old = startblockval(PREV.br_startblock);
  	da_new = 0;

  	/*
  	 * Set flags determining what part of the previous delayed allocation
  	 * extent is being replaced by a real allocation.
  	 */

  	if (PREV.br_startoff == new->br_startoff)
  		state |= BMAP_LEFT_FILLING;
  	if (PREV.br_startoff + PREV.br_blockcount == new_endoff)
  		state |= BMAP_RIGHT_FILLING;

  	/*
  	 * Check and set flags if this segment has a left neighbor.
  	 * Don't set contiguous if the combined extent would be too large.
  	 */

  	if (bma->idx > 0) {

  		state |= BMAP_LEFT_VALID;

  		xfs_bmbt_get_all(xfs_iext_get_ext(ifp, bma->idx - 1), &LEFT);

  
  		if (isnullstartblock(LEFT.br_startblock))
  			state |= BMAP_LEFT_DELAY;

  	}

  
  	if ((state & BMAP_LEFT_VALID) && !(state & BMAP_LEFT_DELAY) &&
  	    LEFT.br_startoff + LEFT.br_blockcount == new->br_startoff &&
  	    LEFT.br_startblock + LEFT.br_blockcount == new->br_startblock &&
  	    LEFT.br_state == new->br_state &&
  	    LEFT.br_blockcount + new->br_blockcount <= MAXEXTLEN)
  		state |= BMAP_LEFT_CONTIG;

  	/*
  	 * Check and set flags if this segment has a right neighbor.
  	 * Don't set contiguous if the combined extent would be too large.
  	 * Also check for all-three-contiguous being too large.
  	 */

  	if (bma->idx < bma->ip->i_df.if_bytes / (uint)sizeof(xfs_bmbt_rec_t) - 1) {

  		state |= BMAP_RIGHT_VALID;

  		xfs_bmbt_get_all(xfs_iext_get_ext(ifp, bma->idx + 1), &RIGHT);

  
  		if (isnullstartblock(RIGHT.br_startblock))
  			state |= BMAP_RIGHT_DELAY;

  	}

  
  	if ((state & BMAP_RIGHT_VALID) && !(state & BMAP_RIGHT_DELAY) &&
  	    new_endoff == RIGHT.br_startoff &&
  	    new->br_startblock + new->br_blockcount == RIGHT.br_startblock &&
  	    new->br_state == RIGHT.br_state &&
  	    new->br_blockcount + RIGHT.br_blockcount <= MAXEXTLEN &&
  	    ((state & (BMAP_LEFT_CONTIG | BMAP_LEFT_FILLING |
  		       BMAP_RIGHT_FILLING)) !=
  		      (BMAP_LEFT_CONTIG | BMAP_LEFT_FILLING |
  		       BMAP_RIGHT_FILLING) ||
  	     LEFT.br_blockcount + new->br_blockcount + RIGHT.br_blockcount
  			<= MAXEXTLEN))
  		state |= BMAP_RIGHT_CONTIG;

  	error = 0;
  	/*
  	 * Switch out based on the FILLING and CONTIG state bits.
  	 */

  	switch (state & (BMAP_LEFT_FILLING | BMAP_LEFT_CONTIG |
  			 BMAP_RIGHT_FILLING | BMAP_RIGHT_CONTIG)) {
  	case BMAP_LEFT_FILLING | BMAP_LEFT_CONTIG |
  	     BMAP_RIGHT_FILLING | BMAP_RIGHT_CONTIG:

  		/*
  		 * Filling in all of a previously delayed allocation extent.
  		 * The left and right neighbors are both contiguous with new.
  		 */

  		bma->idx--;
  		trace_xfs_bmap_pre_update(bma->ip, bma->idx, state, _THIS_IP_);
  		xfs_bmbt_set_blockcount(xfs_iext_get_ext(ifp, bma->idx),

  			LEFT.br_blockcount + PREV.br_blockcount +
  			RIGHT.br_blockcount);

  		trace_xfs_bmap_post_update(bma->ip, bma->idx, state, _THIS_IP_);

  		xfs_iext_remove(bma->ip, bma->idx + 1, 2, state);
  		bma->ip->i_d.di_nextents--;
  		if (bma->cur == NULL)

  			rval = XFS_ILOG_CORE | XFS_ILOG_DEXT;
  		else {
  			rval = XFS_ILOG_CORE;

  			error = xfs_bmbt_lookup_eq(bma->cur, RIGHT.br_startoff,

  					RIGHT.br_startblock,

  					RIGHT.br_blockcount, &i);
  			if (error)

  				goto done;

  			XFS_WANT_CORRUPTED_GOTO(i == 1, done);

  			error = xfs_btree_delete(bma->cur, &i);
  			if (error)

  				goto done;

  			XFS_WANT_CORRUPTED_GOTO(i == 1, done);

  			error = xfs_btree_decrement(bma->cur, 0, &i);
  			if (error)

  				goto done;

  			XFS_WANT_CORRUPTED_GOTO(i == 1, done);

  			error = xfs_bmbt_update(bma->cur, LEFT.br_startoff,

  					LEFT.br_startblock,
  					LEFT.br_blockcount +
  					PREV.br_blockcount +

  					RIGHT.br_blockcount, LEFT.br_state);
  			if (error)

  				goto done;
  		}

  		break;

  	case BMAP_LEFT_FILLING | BMAP_RIGHT_FILLING | BMAP_LEFT_CONTIG:

  		/*
  		 * Filling in all of a previously delayed allocation extent.
  		 * The left neighbor is contiguous, the right is not.
  		 */

  		bma->idx--;

  		trace_xfs_bmap_pre_update(bma->ip, bma->idx, state, _THIS_IP_);
  		xfs_bmbt_set_blockcount(xfs_iext_get_ext(ifp, bma->idx),

  			LEFT.br_blockcount + PREV.br_blockcount);

  		trace_xfs_bmap_post_update(bma->ip, bma->idx, state, _THIS_IP_);

  		xfs_iext_remove(bma->ip, bma->idx + 1, 1, state);
  		if (bma->cur == NULL)

  			rval = XFS_ILOG_DEXT;
  		else {
  			rval = 0;

  			error = xfs_bmbt_lookup_eq(bma->cur, LEFT.br_startoff,

  					LEFT.br_startblock, LEFT.br_blockcount,

  					&i);
  			if (error)

  				goto done;

  			XFS_WANT_CORRUPTED_GOTO(i == 1, done);

  			error = xfs_bmbt_update(bma->cur, LEFT.br_startoff,

  					LEFT.br_startblock,
  					LEFT.br_blockcount +

  					PREV.br_blockcount, LEFT.br_state);
  			if (error)

  				goto done;
  		}

  		break;

  	case BMAP_LEFT_FILLING | BMAP_RIGHT_FILLING | BMAP_RIGHT_CONTIG:

  		/*
  		 * Filling in all of a previously delayed allocation extent.
  		 * The right neighbor is contiguous, the left is not.
  		 */

  		trace_xfs_bmap_pre_update(bma->ip, bma->idx, state, _THIS_IP_);

  		xfs_bmbt_set_startblock(ep, new->br_startblock);
  		xfs_bmbt_set_blockcount(ep,
  			PREV.br_blockcount + RIGHT.br_blockcount);

  		trace_xfs_bmap_post_update(bma->ip, bma->idx, state, _THIS_IP_);

  		xfs_iext_remove(bma->ip, bma->idx + 1, 1, state);
  		if (bma->cur == NULL)

  			rval = XFS_ILOG_DEXT;
  		else {
  			rval = 0;

  			error = xfs_bmbt_lookup_eq(bma->cur, RIGHT.br_startoff,

  					RIGHT.br_startblock,

  					RIGHT.br_blockcount, &i);
  			if (error)

  				goto done;

  			XFS_WANT_CORRUPTED_GOTO(i == 1, done);

  			error = xfs_bmbt_update(bma->cur, PREV.br_startoff,

  					new->br_startblock,
  					PREV.br_blockcount +

  					RIGHT.br_blockcount, PREV.br_state);
  			if (error)

  				goto done;
  		}

  		break;

  	case BMAP_LEFT_FILLING | BMAP_RIGHT_FILLING:

  		/*
  		 * Filling in all of a previously delayed allocation extent.
  		 * Neither the left nor right neighbors are contiguous with
  		 * the new one.
  		 */

  		trace_xfs_bmap_pre_update(bma->ip, bma->idx, state, _THIS_IP_);

  		xfs_bmbt_set_startblock(ep, new->br_startblock);

  		trace_xfs_bmap_post_update(bma->ip, bma->idx, state, _THIS_IP_);

  		bma->ip->i_d.di_nextents++;
  		if (bma->cur == NULL)

  			rval = XFS_ILOG_CORE | XFS_ILOG_DEXT;
  		else {
  			rval = XFS_ILOG_CORE;

  			error = xfs_bmbt_lookup_eq(bma->cur, new->br_startoff,

  					new->br_startblock, new->br_blockcount,

  					&i);
  			if (error)

  				goto done;

  			XFS_WANT_CORRUPTED_GOTO(i == 0, done);

  			bma->cur->bc_rec.b.br_state = XFS_EXT_NORM;
  			error = xfs_btree_insert(bma->cur, &i);
  			if (error)

  				goto done;

  			XFS_WANT_CORRUPTED_GOTO(i == 1, done);

  		}

  		break;

  	case BMAP_LEFT_FILLING | BMAP_LEFT_CONTIG:

  		/*
  		 * Filling in the first part of a previous delayed allocation.
  		 * The left neighbor is contiguous.
  		 */

  		trace_xfs_bmap_pre_update(bma->ip, bma->idx - 1, state, _THIS_IP_);
  		xfs_bmbt_set_blockcount(xfs_iext_get_ext(ifp, bma->idx - 1),

  			LEFT.br_blockcount + new->br_blockcount);
  		xfs_bmbt_set_startoff(ep,
  			PREV.br_startoff + new->br_blockcount);

  		trace_xfs_bmap_post_update(bma->ip, bma->idx - 1, state, _THIS_IP_);

  		temp = PREV.br_blockcount - new->br_blockcount;

  		trace_xfs_bmap_pre_update(bma->ip, bma->idx, state, _THIS_IP_);

  		xfs_bmbt_set_blockcount(ep, temp);

  		if (bma->cur == NULL)

  			rval = XFS_ILOG_DEXT;
  		else {
  			rval = 0;

  			error = xfs_bmbt_lookup_eq(bma->cur, LEFT.br_startoff,

  					LEFT.br_startblock, LEFT.br_blockcount,

  					&i);
  			if (error)

  				goto done;

  			XFS_WANT_CORRUPTED_GOTO(i == 1, done);

  			error = xfs_bmbt_update(bma->cur, LEFT.br_startoff,

  					LEFT.br_startblock,
  					LEFT.br_blockcount +
  					new->br_blockcount,

  					LEFT.br_state);
  			if (error)

  				goto done;
  		}

  		da_new = XFS_FILBLKS_MIN(xfs_bmap_worst_indlen(bma->ip, temp),

  			startblockval(PREV.br_startblock));

  		xfs_bmbt_set_startblock(ep, nullstartblock(da_new));

  		trace_xfs_bmap_post_update(bma->ip, bma->idx, state, _THIS_IP_);

  		bma->idx--;

  		break;

  	case BMAP_LEFT_FILLING:

  		/*
  		 * Filling in the first part of a previous delayed allocation.
  		 * The left neighbor is not contiguous.
  		 */

  		trace_xfs_bmap_pre_update(bma->ip, bma->idx, state, _THIS_IP_);

  		xfs_bmbt_set_startoff(ep, new_endoff);
  		temp = PREV.br_blockcount - new->br_blockcount;
  		xfs_bmbt_set_blockcount(ep, temp);

  		xfs_iext_insert(bma->ip, bma->idx, 1, new, state);
  		bma->ip->i_d.di_nextents++;
  		if (bma->cur == NULL)

  			rval = XFS_ILOG_CORE | XFS_ILOG_DEXT;
  		else {
  			rval = XFS_ILOG_CORE;

  			error = xfs_bmbt_lookup_eq(bma->cur, new->br_startoff,

  					new->br_startblock, new->br_blockcount,

  					&i);
  			if (error)

  				goto done;

  			XFS_WANT_CORRUPTED_GOTO(i == 0, done);

  			bma->cur->bc_rec.b.br_state = XFS_EXT_NORM;
  			error = xfs_btree_insert(bma->cur, &i);
  			if (error)

  				goto done;

  			XFS_WANT_CORRUPTED_GOTO(i == 1, done);

  		}

  		if (bma->ip->i_d.di_format == XFS_DINODE_FMT_EXTENTS &&
  		    bma->ip->i_d.di_nextents > bma->ip->i_df.if_ext_max) {
  			error = xfs_bmap_extents_to_btree(bma->tp, bma->ip,
  					bma->firstblock, bma->flist,
  					&bma->cur, 1, &tmp_rval, XFS_DATA_FORK);

  			rval |= tmp_rval;
  			if (error)
  				goto done;
  		}

  		da_new = XFS_FILBLKS_MIN(xfs_bmap_worst_indlen(bma->ip, temp),

  			startblockval(PREV.br_startblock) -

  			(bma->cur ? bma->cur->bc_private.b.allocated : 0));
  		ep = xfs_iext_get_ext(ifp, bma->idx + 1);

  		xfs_bmbt_set_startblock(ep, nullstartblock(da_new));

  		trace_xfs_bmap_post_update(bma->ip, bma->idx + 1, state, _THIS_IP_);

  		break;

  	case BMAP_RIGHT_FILLING | BMAP_RIGHT_CONTIG:

  		/*
  		 * Filling in the last part of a previous delayed allocation.
  		 * The right neighbor is contiguous with the new allocation.
  		 */
  		temp = PREV.br_blockcount - new->br_blockcount;

  		trace_xfs_bmap_pre_update(bma->ip, bma->idx + 1, state, _THIS_IP_);

  		xfs_bmbt_set_blockcount(ep, temp);

  		xfs_bmbt_set_allf(xfs_iext_get_ext(ifp, bma->idx + 1),

  			new->br_startoff, new->br_startblock,

  			new->br_blockcount + RIGHT.br_blockcount,
  			RIGHT.br_state);

  		trace_xfs_bmap_post_update(bma->ip, bma->idx + 1, state, _THIS_IP_);
  		if (bma->cur == NULL)

  			rval = XFS_ILOG_DEXT;
  		else {
  			rval = 0;

  			error = xfs_bmbt_lookup_eq(bma->cur, RIGHT.br_startoff,

  					RIGHT.br_startblock,

  					RIGHT.br_blockcount, &i);
  			if (error)

  				goto done;

  			XFS_WANT_CORRUPTED_GOTO(i == 1, done);

  			error = xfs_bmbt_update(bma->cur, new->br_startoff,

  					new->br_startblock,
  					new->br_blockcount +
  					RIGHT.br_blockcount,

  					RIGHT.br_state);
  			if (error)

  				goto done;
  		}

  		da_new = XFS_FILBLKS_MIN(xfs_bmap_worst_indlen(bma->ip, temp),

  			startblockval(PREV.br_startblock));

  		trace_xfs_bmap_pre_update(bma->ip, bma->idx, state, _THIS_IP_);

  		xfs_bmbt_set_startblock(ep, nullstartblock(da_new));

  		trace_xfs_bmap_post_update(bma->ip, bma->idx, state, _THIS_IP_);

  		bma->idx++;

  		break;

  	case BMAP_RIGHT_FILLING:

  		/*
  		 * Filling in the last part of a previous delayed allocation.
  		 * The right neighbor is not contiguous.
  		 */
  		temp = PREV.br_blockcount - new->br_blockcount;

  		trace_xfs_bmap_pre_update(bma->ip, bma->idx, state, _THIS_IP_);

  		xfs_bmbt_set_blockcount(ep, temp);

  		xfs_iext_insert(bma->ip, bma->idx + 1, 1, new, state);
  		bma->ip->i_d.di_nextents++;
  		if (bma->cur == NULL)

  			rval = XFS_ILOG_CORE | XFS_ILOG_DEXT;
  		else {
  			rval = XFS_ILOG_CORE;

  			error = xfs_bmbt_lookup_eq(bma->cur, new->br_startoff,

  					new->br_startblock, new->br_blockcount,

  					&i);
  			if (error)

  				goto done;

  			XFS_WANT_CORRUPTED_GOTO(i == 0, done);

  			bma->cur->bc_rec.b.br_state = XFS_EXT_NORM;
  			error = xfs_btree_insert(bma->cur, &i);
  			if (error)

  				goto done;

  			XFS_WANT_CORRUPTED_GOTO(i == 1, done);

  		}

  		if (bma->ip->i_d.di_format == XFS_DINODE_FMT_EXTENTS &&
  		    bma->ip->i_d.di_nextents > bma->ip->i_df.if_ext_max) {
  			error = xfs_bmap_extents_to_btree(bma->tp, bma->ip,
  				bma->firstblock, bma->flist, &bma->cur, 1,
  				&tmp_rval, XFS_DATA_FORK);

  			rval |= tmp_rval;
  			if (error)
  				goto done;
  		}

  		da_new = XFS_FILBLKS_MIN(xfs_bmap_worst_indlen(bma->ip, temp),

  			startblockval(PREV.br_startblock) -

  			(bma->cur ? bma->cur->bc_private.b.allocated : 0));
  		ep = xfs_iext_get_ext(ifp, bma->idx);

  		xfs_bmbt_set_startblock(ep, nullstartblock(da_new));

  		trace_xfs_bmap_post_update(bma->ip, bma->idx, state, _THIS_IP_);

  		bma->idx++;

  		break;
  
  	case 0:
  		/*
  		 * Filling in the middle part of a previous delayed allocation.
  		 * Contiguity is impossible here.
  		 * This case is avoided almost all the time.

  		 *
  		 * We start with a delayed allocation:
  		 *
  		 * +ddddddddddddddddddddddddddddddddddddddddddddddddddddddd+
  		 *  PREV @ idx
  		 *
  	         * and we are allocating:
  		 *                     +rrrrrrrrrrrrrrrrr+
  		 *			      new
  		 *
  		 * and we set it up for insertion as:
  		 * +ddddddddddddddddddd+rrrrrrrrrrrrrrrrr+ddddddddddddddddd+
  		 *                            new
  		 *  PREV @ idx          LEFT              RIGHT
  		 *                      inserted at idx + 1

  		 */
  		temp = new->br_startoff - PREV.br_startoff;

  		temp2 = PREV.br_startoff + PREV.br_blockcount - new_endoff;

  		trace_xfs_bmap_pre_update(bma->ip, bma->idx, 0, _THIS_IP_);

  		xfs_bmbt_set_blockcount(ep, temp);	/* truncate PREV */
  		LEFT = *new;
  		RIGHT.br_state = PREV.br_state;
  		RIGHT.br_startblock = nullstartblock(

  				(int)xfs_bmap_worst_indlen(bma->ip, temp2));

  		RIGHT.br_startoff = new_endoff;
  		RIGHT.br_blockcount = temp2;
  		/* insert LEFT (r[0]) and RIGHT (r[1]) at the same time */

  		xfs_iext_insert(bma->ip, bma->idx + 1, 2, &LEFT, state);
  		bma->ip->i_d.di_nextents++;
  		if (bma->cur == NULL)

  			rval = XFS_ILOG_CORE | XFS_ILOG_DEXT;
  		else {
  			rval = XFS_ILOG_CORE;

  			error = xfs_bmbt_lookup_eq(bma->cur, new->br_startoff,

  					new->br_startblock, new->br_blockcount,

  					&i);
  			if (error)

  				goto done;

  			XFS_WANT_CORRUPTED_GOTO(i == 0, done);

  			bma->cur->bc_rec.b.br_state = XFS_EXT_NORM;
  			error = xfs_btree_insert(bma->cur, &i);
  			if (error)

  				goto done;

  			XFS_WANT_CORRUPTED_GOTO(i == 1, done);

  		}

  		if (bma->ip->i_d.di_format == XFS_DINODE_FMT_EXTENTS &&
  		    bma->ip->i_d.di_nextents > bma->ip->i_df.if_ext_max) {
  			error = xfs_bmap_extents_to_btree(bma->tp, bma->ip,
  					bma->firstblock, bma->flist, &bma->cur,
  					1, &tmp_rval, XFS_DATA_FORK);

  			rval |= tmp_rval;
  			if (error)
  				goto done;
  		}

  		temp = xfs_bmap_worst_indlen(bma->ip, temp);
  		temp2 = xfs_bmap_worst_indlen(bma->ip, temp2);

  		diff = (int)(temp + temp2 - startblockval(PREV.br_startblock) -

  			(bma->cur ? bma->cur->bc_private.b.allocated : 0));

  		if (diff > 0) {

  			error = xfs_icsb_modify_counters(bma->ip->i_mount,

  					XFS_SBS_FDBLOCKS,
  					-((int64_t)diff), 0);
  			ASSERT(!error);
  			if (error)
  				goto done;

  		}

  		ep = xfs_iext_get_ext(ifp, bma->idx);

  		xfs_bmbt_set_startblock(ep, nullstartblock((int)temp));

  		trace_xfs_bmap_post_update(bma->ip, bma->idx, state, _THIS_IP_);
  		trace_xfs_bmap_pre_update(bma->ip, bma->idx + 2, state, _THIS_IP_);
  		xfs_bmbt_set_startblock(xfs_iext_get_ext(ifp, bma->idx + 2),

  			nullstartblock((int)temp2));

  		trace_xfs_bmap_post_update(bma->ip, bma->idx + 2, state, _THIS_IP_);

  		bma->idx++;

  		da_new = temp + temp2;

  		break;

  	case BMAP_LEFT_FILLING | BMAP_LEFT_CONTIG | BMAP_RIGHT_CONTIG:
  	case BMAP_RIGHT_FILLING | BMAP_LEFT_CONTIG | BMAP_RIGHT_CONTIG:
  	case BMAP_LEFT_FILLING | BMAP_RIGHT_CONTIG:
  	case BMAP_RIGHT_FILLING | BMAP_LEFT_CONTIG:
  	case BMAP_LEFT_CONTIG | BMAP_RIGHT_CONTIG:
  	case BMAP_LEFT_CONTIG:
  	case BMAP_RIGHT_CONTIG:

  		/*
  		 * These cases are all impossible.
  		 */
  		ASSERT(0);
  	}

  
  	/* convert to a btree if necessary */

  	if (XFS_IFORK_FORMAT(bma->ip, XFS_DATA_FORK) == XFS_DINODE_FMT_EXTENTS &&
  	    XFS_IFORK_NEXTENTS(bma->ip, XFS_DATA_FORK) > ifp->if_ext_max) {

  		int	tmp_logflags;	/* partial log flag return val */

  		ASSERT(bma->cur == NULL);
  		error = xfs_bmap_extents_to_btree(bma->tp, bma->ip,
  				bma->firstblock, bma->flist, &bma->cur,

  				da_old > 0, &tmp_logflags, XFS_DATA_FORK);

  		bma->logflags |= tmp_logflags;

  		if (error)
  			goto done;
  	}
  
  	/* adjust for changes in reserved delayed indirect blocks */
  	if (da_old || da_new) {
  		temp = da_new;

  		if (bma->cur)
  			temp += bma->cur->bc_private.b.allocated;

  		ASSERT(temp <= da_old);
  		if (temp < da_old)

  			xfs_icsb_modify_counters(bma->ip->i_mount,
  					XFS_SBS_FDBLOCKS,
  					(int64_t)(da_old - temp), 0);

  	}
  
  	/* clear out the allocated field, done with it now in any case. */

  	if (bma->cur)
  		bma->cur->bc_private.b.allocated = 0;
  
  	xfs_bmap_check_leaf_extents(bma->cur, bma->ip, XFS_DATA_FORK);

  done:

  	bma->logflags |= rval;

  	return error;
  #undef	LEFT
  #undef	RIGHT
  #undef	PREV

  }
  
  /*

   * Convert an unwritten allocation to a real allocation or vice versa.

   */
  STATIC int				/* error */
  xfs_bmap_add_extent_unwritten_real(

  	struct xfs_trans	*tp,

  	xfs_inode_t		*ip,	/* incore inode pointer */

  	xfs_extnum_t		*idx,	/* extent number to update/insert */

  	xfs_btree_cur_t		**curp,	/* if *curp is null, not a btree */

  	xfs_bmbt_irec_t		*new,	/* new data to add to file extents */

  	xfs_fsblock_t		*first,	/* pointer to firstblock variable */
  	xfs_bmap_free_t		*flist,	/* list of extents to be freed */

  	int			*logflagsp) /* inode logging flags */

  {

  	xfs_btree_cur_t		*cur;	/* btree cursor */

  	xfs_bmbt_rec_host_t	*ep;	/* extent entry for idx */

  	int			error;	/* error return value */

  	int			i;	/* temp state */

  	xfs_ifork_t		*ifp;	/* inode fork pointer */

  	xfs_fileoff_t		new_endoff;	/* end offset of new entry */
  	xfs_exntst_t		newext;	/* new extent state */
  	xfs_exntst_t		oldext;	/* old extent state */
  	xfs_bmbt_irec_t		r[3];	/* neighbor extent entries */
  					/* left is 0, right is 1, prev is 2 */
  	int			rval=0;	/* return value (logging flags) */
  	int			state = 0;/* state bits, accessed thru macros */

  	*logflagsp = 0;
  
  	cur = *curp;
  	ifp = XFS_IFORK_PTR(ip, XFS_DATA_FORK);
  
  	ASSERT(*idx >= 0);
  	ASSERT(*idx <= ifp->if_bytes / sizeof(struct xfs_bmbt_rec));
  	ASSERT(!isnullstartblock(new->br_startblock));
  
  	XFS_STATS_INC(xs_add_exlist);

  #define	LEFT		r[0]
  #define	RIGHT		r[1]
  #define	PREV		r[2]

  	/*
  	 * Set up a bunch of variables to make the tests simpler.
  	 */
  	error = 0;

  	ep = xfs_iext_get_ext(ifp, *idx);

  	xfs_bmbt_get_all(ep, &PREV);
  	newext = new->br_state;
  	oldext = (newext == XFS_EXT_UNWRITTEN) ?
  		XFS_EXT_NORM : XFS_EXT_UNWRITTEN;
  	ASSERT(PREV.br_state == oldext);
  	new_endoff = new->br_startoff + new->br_blockcount;
  	ASSERT(PREV.br_startoff <= new->br_startoff);
  	ASSERT(PREV.br_startoff + PREV.br_blockcount >= new_endoff);

  	/*
  	 * Set flags determining what part of the previous oldext allocation
  	 * extent is being replaced by a newext allocation.
  	 */

  	if (PREV.br_startoff == new->br_startoff)
  		state |= BMAP_LEFT_FILLING;
  	if (PREV.br_startoff + PREV.br_blockcount == new_endoff)
  		state |= BMAP_RIGHT_FILLING;

  	/*
  	 * Check and set flags if this segment has a left neighbor.
  	 * Don't set contiguous if the combined extent would be too large.
  	 */

  	if (*idx > 0) {

  		state |= BMAP_LEFT_VALID;

  		xfs_bmbt_get_all(xfs_iext_get_ext(ifp, *idx - 1), &LEFT);

  
  		if (isnullstartblock(LEFT.br_startblock))
  			state |= BMAP_LEFT_DELAY;

  	}

  
  	if ((state & BMAP_LEFT_VALID) && !(state & BMAP_LEFT_DELAY) &&
  	    LEFT.br_startoff + LEFT.br_blockcount == new->br_startoff &&
  	    LEFT.br_startblock + LEFT.br_blockcount == new->br_startblock &&
  	    LEFT.br_state == newext &&
  	    LEFT.br_blockcount + new->br_blockcount <= MAXEXTLEN)
  		state |= BMAP_LEFT_CONTIG;

  	/*
  	 * Check and set flags if this segment has a right neighbor.
  	 * Don't set contiguous if the combined extent would be too large.
  	 * Also check for all-three-contiguous being too large.
  	 */

  	if (*idx < ip->i_df.if_bytes / (uint)sizeof(xfs_bmbt_rec_t) - 1) {

  		state |= BMAP_RIGHT_VALID;

  		xfs_bmbt_get_all(xfs_iext_get_ext(ifp, *idx + 1), &RIGHT);

  		if (isnullstartblock(RIGHT.br_startblock))
  			state |= BMAP_RIGHT_DELAY;

  	}

  
  	if ((state & BMAP_RIGHT_VALID) && !(state & BMAP_RIGHT_DELAY) &&
  	    new_endoff == RIGHT.br_startoff &&
  	    new->br_startblock + new->br_blockcount == RIGHT.br_startblock &&
  	    newext == RIGHT.br_state &&
  	    new->br_blockcount + RIGHT.br_blockcount <= MAXEXTLEN &&
  	    ((state & (BMAP_LEFT_CONTIG | BMAP_LEFT_FILLING |
  		       BMAP_RIGHT_FILLING)) !=
  		      (BMAP_LEFT_CONTIG | BMAP_LEFT_FILLING |
  		       BMAP_RIGHT_FILLING) ||
  	     LEFT.br_blockcount + new->br_blockcount + RIGHT.br_blockcount
  			<= MAXEXTLEN))
  		state |= BMAP_RIGHT_CONTIG;

  	/*
  	 * Switch out based on the FILLING and CONTIG state bits.
  	 */

  	switch (state & (BMAP_LEFT_FILLING | BMAP_LEFT_CONTIG |
  			 BMAP_RIGHT_FILLING | BMAP_RIGHT_CONTIG)) {
  	case BMAP_LEFT_FILLING | BMAP_LEFT_CONTIG |
  	     BMAP_RIGHT_FILLING | BMAP_RIGHT_CONTIG:

  		/*
  		 * Setting all of a previous oldext extent to newext.
  		 * The left and right neighbors are both contiguous with new.
  		 */

  		--*idx;
  
  		trace_xfs_bmap_pre_update(ip, *idx, state, _THIS_IP_);
  		xfs_bmbt_set_blockcount(xfs_iext_get_ext(ifp, *idx),

  			LEFT.br_blockcount + PREV.br_blockcount +
  			RIGHT.br_blockcount);

  		trace_xfs_bmap_post_update(ip, *idx, state, _THIS_IP_);

  		xfs_iext_remove(ip, *idx + 1, 2, state);

  		ip->i_d.di_nextents -= 2;
  		if (cur == NULL)
  			rval = XFS_ILOG_CORE | XFS_ILOG_DEXT;
  		else {
  			rval = XFS_ILOG_CORE;
  			if ((error = xfs_bmbt_lookup_eq(cur, RIGHT.br_startoff,
  					RIGHT.br_startblock,
  					RIGHT.br_blockcount, &i)))
  				goto done;

  			XFS_WANT_CORRUPTED_GOTO(i == 1, done);

  			if ((error = xfs_btree_delete(cur, &i)))

  				goto done;

  			XFS_WANT_CORRUPTED_GOTO(i == 1, done);

  			if ((error = xfs_btree_decrement(cur, 0, &i)))

  				goto done;

  			XFS_WANT_CORRUPTED_GOTO(i == 1, done);

  			if ((error = xfs_btree_delete(cur, &i)))

  				goto done;

  			XFS_WANT_CORRUPTED_GOTO(i == 1, done);

  			if ((error = xfs_btree_decrement(cur, 0, &i)))

  				goto done;

  			XFS_WANT_CORRUPTED_GOTO(i == 1, done);

  			if ((error = xfs_bmbt_update(cur, LEFT.br_startoff,
  				LEFT.br_startblock,
  				LEFT.br_blockcount + PREV.br_blockcount +
  				RIGHT.br_blockcount, LEFT.br_state)))
  				goto done;
  		}
  		break;

  	case BMAP_LEFT_FILLING | BMAP_RIGHT_FILLING | BMAP_LEFT_CONTIG:

  		/*
  		 * Setting all of a previous oldext extent to newext.
  		 * The left neighbor is contiguous, the right is not.
  		 */

  		--*idx;
  
  		trace_xfs_bmap_pre_update(ip, *idx, state, _THIS_IP_);
  		xfs_bmbt_set_blockcount(xfs_iext_get_ext(ifp, *idx),

  			LEFT.br_blockcount + PREV.br_blockcount);

  		trace_xfs_bmap_post_update(ip, *idx, state, _THIS_IP_);

  		xfs_iext_remove(ip, *idx + 1, 1, state);

  		ip->i_d.di_nextents--;
  		if (cur == NULL)
  			rval = XFS_ILOG_CORE | XFS_ILOG_DEXT;
  		else {
  			rval = XFS_ILOG_CORE;
  			if ((error = xfs_bmbt_lookup_eq(cur, PREV.br_startoff,
  					PREV.br_startblock, PREV.br_blockcount,
  					&i)))
  				goto done;

  			XFS_WANT_CORRUPTED_GOTO(i == 1, done);

  			if ((error = xfs_btree_delete(cur, &i)))

  				goto done;

  			XFS_WANT_CORRUPTED_GOTO(i == 1, done);

  			if ((error = xfs_btree_decrement(cur, 0, &i)))

  				goto done;

  			XFS_WANT_CORRUPTED_GOTO(i == 1, done);

  			if ((error = xfs_bmbt_update(cur, LEFT.br_startoff,
  				LEFT.br_startblock,
  				LEFT.br_blockcount + PREV.br_blockcount,
  				LEFT.br_state)))
  				goto done;
  		}
  		break;

  	case BMAP_LEFT_FILLING | BMAP_RIGHT_FILLING | BMAP_RIGHT_CONTIG:

  		/*
  		 * Setting all of a previous oldext extent to newext.
  		 * The right neighbor is contiguous, the left is not.
  		 */

  		trace_xfs_bmap_pre_update(ip, *idx, state, _THIS_IP_);

  		xfs_bmbt_set_blockcount(ep,
  			PREV.br_blockcount + RIGHT.br_blockcount);
  		xfs_bmbt_set_state(ep, newext);

  		trace_xfs_bmap_post_update(ip, *idx, state, _THIS_IP_);
  		xfs_iext_remove(ip, *idx + 1, 1, state);

  		ip->i_d.di_nextents--;
  		if (cur == NULL)
  			rval = XFS_ILOG_CORE | XFS_ILOG_DEXT;
  		else {
  			rval = XFS_ILOG_CORE;
  			if ((error = xfs_bmbt_lookup_eq(cur, RIGHT.br_startoff,
  					RIGHT.br_startblock,
  					RIGHT.br_blockcount, &i)))
  				goto done;

  			XFS_WANT_CORRUPTED_GOTO(i == 1, done);

  			if ((error = xfs_btree_delete(cur, &i)))

  				goto done;

  			XFS_WANT_CORRUPTED_GOTO(i == 1, done);

  			if ((error = xfs_btree_decrement(cur, 0, &i)))

  				goto done;

  			XFS_WANT_CORRUPTED_GOTO(i == 1, done);

  			if ((error = xfs_bmbt_update(cur, new->br_startoff,
  				new->br_startblock,
  				new->br_blockcount + RIGHT.br_blockcount,
  				newext)))
  				goto done;
  		}
  		break;

  	case BMAP_LEFT_FILLING | BMAP_RIGHT_FILLING:

  		/*
  		 * Setting all of a previous oldext extent to newext.
  		 * Neither the left nor right neighbors are contiguous with
  		 * the new one.
  		 */

  		trace_xfs_bmap_pre_update(ip, *idx, state, _THIS_IP_);

  		xfs_bmbt_set_state(ep, newext);

  		trace_xfs_bmap_post_update(ip, *idx, state, _THIS_IP_);

  		if (cur == NULL)
  			rval = XFS_ILOG_DEXT;
  		else {
  			rval = 0;
  			if ((error = xfs_bmbt_lookup_eq(cur, new->br_startoff,
  					new->br_startblock, new->br_blockcount,
  					&i)))
  				goto done;

  			XFS_WANT_CORRUPTED_GOTO(i == 1, done);

  			if ((error = xfs_bmbt_update(cur, new->br_startoff,
  				new->br_startblock, new->br_blockcount,
  				newext)))
  				goto done;
  		}
  		break;

  	case BMAP_LEFT_FILLING | BMAP_LEFT_CONTIG:

  		/*
  		 * Setting the first part of a previous oldext extent to newext.
  		 * The left neighbor is contiguous.
  		 */

  		trace_xfs_bmap_pre_update(ip, *idx - 1, state, _THIS_IP_);
  		xfs_bmbt_set_blockcount(xfs_iext_get_ext(ifp, *idx - 1),

  			LEFT.br_blockcount + new->br_blockcount);
  		xfs_bmbt_set_startoff(ep,
  			PREV.br_startoff + new->br_blockcount);

  		trace_xfs_bmap_post_update(ip, *idx - 1, state, _THIS_IP_);

  		trace_xfs_bmap_pre_update(ip, *idx, state, _THIS_IP_);

  		xfs_bmbt_set_startblock(ep,
  			new->br_startblock + new->br_blockcount);
  		xfs_bmbt_set_blockcount(ep,
  			PREV.br_blockcount - new->br_blockcount);

  		trace_xfs_bmap_post_update(ip, *idx, state, _THIS_IP_);
  
  		--*idx;

  		if (cur == NULL)
  			rval = XFS_ILOG_DEXT;
  		else {
  			rval = 0;
  			if ((error = xfs_bmbt_lookup_eq(cur, PREV.br_startoff,
  					PREV.br_startblock, PREV.br_blockcount,
  					&i)))
  				goto done;

  			XFS_WANT_CORRUPTED_GOTO(i == 1, done);

  			if ((error = xfs_bmbt_update(cur,
  				PREV.br_startoff + new->br_blockcount,
  				PREV.br_startblock + new->br_blockcount,
  				PREV.br_blockcount - new->br_blockcount,
  				oldext)))
  				goto done;

  			if ((error = xfs_btree_decrement(cur, 0, &i)))

  				goto done;

  			error = xfs_bmbt_update(cur, LEFT.br_startoff,

  				LEFT.br_startblock,
  				LEFT.br_blockcount + new->br_blockcount,

  				LEFT.br_state);
  			if (error)

  				goto done;
  		}
  		break;

  	case BMAP_LEFT_FILLING:

  		/*
  		 * Setting the first part of a previous oldext extent to newext.
  		 * The left neighbor is not contiguous.
  		 */

  		trace_xfs_bmap_pre_update(ip, *idx, state, _THIS_IP_);

  		ASSERT(ep && xfs_bmbt_get_state(ep) == oldext);
  		xfs_bmbt_set_startoff(ep, new_endoff);
  		xfs_bmbt_set_blockcount(ep,
  			PREV.br_blockcount - new->br_blockcount);
  		xfs_bmbt_set_startblock(ep,
  			new->br_startblock + new->br_blockcount);

  		trace_xfs_bmap_post_update(ip, *idx, state, _THIS_IP_);

  		xfs_iext_insert(ip, *idx, 1, new, state);

  		ip->i_d.di_nextents++;
  		if (cur == NULL)
  			rval = XFS_ILOG_CORE | XFS_ILOG_DEXT;
  		else {
  			rval = XFS_ILOG_CORE;
  			if ((error = xfs_bmbt_lookup_eq(cur, PREV.br_startoff,
  					PREV.br_startblock, PREV.br_blockcount,
  					&i)))
  				goto done;

  			XFS_WANT_CORRUPTED_GOTO(i == 1, done);

  			if ((error = xfs_bmbt_update(cur,
  				PREV.br_startoff + new->br_blockcount,
  				PREV.br_startblock + new->br_blockcount,
  				PREV.br_blockcount - new->br_blockcount,
  				oldext)))
  				goto done;
  			cur->bc_rec.b = *new;

  			if ((error = xfs_btree_insert(cur, &i)))

  				goto done;

  			XFS_WANT_CORRUPTED_GOTO(i == 1, done);

  		}
  		break;

  	case BMAP_RIGHT_FILLING | BMAP_RIGHT_CONTIG:

  		/*
  		 * Setting the last part of a previous oldext extent to newext.
  		 * The right neighbor is contiguous with the new allocation.
  		 */

  		trace_xfs_bmap_pre_update(ip, *idx, state, _THIS_IP_);

  		xfs_bmbt_set_blockcount(ep,
  			PREV.br_blockcount - new->br_blockcount);

  		trace_xfs_bmap_post_update(ip, *idx, state, _THIS_IP_);
  
  		++*idx;
  
  		trace_xfs_bmap_pre_update(ip, *idx, state, _THIS_IP_);
  		xfs_bmbt_set_allf(xfs_iext_get_ext(ifp, *idx),

  			new->br_startoff, new->br_startblock,

  			new->br_blockcount + RIGHT.br_blockcount, newext);

  		trace_xfs_bmap_post_update(ip, *idx, state, _THIS_IP_);

  		if (cur == NULL)
  			rval = XFS_ILOG_DEXT;
  		else {
  			rval = 0;
  			if ((error = xfs_bmbt_lookup_eq(cur, PREV.br_startoff,
  					PREV.br_startblock,
  					PREV.br_blockcount, &i)))
  				goto done;

  			XFS_WANT_CORRUPTED_GOTO(i == 1, done);

  			if ((error = xfs_bmbt_update(cur, PREV.br_startoff,
  				PREV.br_startblock,
  				PREV.br_blockcount - new->br_blockcount,
  				oldext)))
  				goto done;

  			if ((error = xfs_btree_increment(cur, 0, &i)))

  				goto done;
  			if ((error = xfs_bmbt_update(cur, new->br_startoff,
  				new->br_startblock,
  				new->br_blockcount + RIGHT.br_blockcount,
  				newext)))
  				goto done;
  		}
  		break;

  	case BMAP_RIGHT_FILLING:

  		/*
  		 * Setting the last part of a previous oldext extent to newext.
  		 * The right neighbor is not contiguous.
  		 */

  		trace_xfs_bmap_pre_update(ip, *idx, state, _THIS_IP_);

  		xfs_bmbt_set_blockcount(ep,
  			PREV.br_blockcount - new->br_blockcount);

  		trace_xfs_bmap_post_update(ip, *idx, state, _THIS_IP_);
  
  		++*idx;
  		xfs_iext_insert(ip, *idx, 1, new, state);

  		ip->i_d.di_nextents++;
  		if (cur == NULL)
  			rval = XFS_ILOG_CORE | XFS_ILOG_DEXT;
  		else {
  			rval = XFS_ILOG_CORE;
  			if ((error = xfs_bmbt_lookup_eq(cur, PREV.br_startoff,
  					PREV.br_startblock, PREV.br_blockcount,
  					&i)))
  				goto done;

  			XFS_WANT_CORRUPTED_GOTO(i == 1, done);

  			if ((error = xfs_bmbt_update(cur, PREV.br_startoff,
  				PREV.br_startblock,
  				PREV.br_blockcount - new->br_blockcount,
  				oldext)))
  				goto done;
  			if ((error = xfs_bmbt_lookup_eq(cur, new->br_startoff,
  					new->br_startblock, new->br_blockcount,
  					&i)))
  				goto done;

  			XFS_WANT_CORRUPTED_GOTO(i == 0, done);

  			cur->bc_rec.b.br_state = XFS_EXT_NORM;

  			if ((error = xfs_btree_insert(cur, &i)))

  				goto done;

  			XFS_WANT_CORRUPTED_GOTO(i == 1, done);

  		}
  		break;
  
  	case 0:
  		/*
  		 * Setting the middle part of a previous oldext extent to
  		 * newext.  Contiguity is impossible here.
  		 * One extent becomes three extents.
  		 */

  		trace_xfs_bmap_pre_update(ip, *idx, state, _THIS_IP_);

  		xfs_bmbt_set_blockcount(ep,
  			new->br_startoff - PREV.br_startoff);

  		trace_xfs_bmap_post_update(ip, *idx, state, _THIS_IP_);

  		r[0] = *new;
  		r[1].br_startoff = new_endoff;
  		r[1].br_blockcount =
  			PREV.br_startoff + PREV.br_blockcount - new_endoff;
  		r[1].br_startblock = new->br_startblock + new->br_blockcount;
  		r[1].br_state = oldext;

  
  		++*idx;
  		xfs_iext_insert(ip, *idx, 2, &r[0], state);

  		ip->i_d.di_nextents += 2;
  		if (cur == NULL)
  			rval = XFS_ILOG_CORE | XFS_ILOG_DEXT;
  		else {
  			rval = XFS_ILOG_CORE;
  			if ((error = xfs_bmbt_lookup_eq(cur, PREV.br_startoff,
  					PREV.br_startblock, PREV.br_blockcount,
  					&i)))
  				goto done;

  			XFS_WANT_CORRUPTED_GOTO(i == 1, done);

  			/* new right extent - oldext */
  			if ((error = xfs_bmbt_update(cur, r[1].br_startoff,
  				r[1].br_startblock, r[1].br_blockcount,
  				r[1].br_state)))
  				goto done;
  			/* new left extent - oldext */

  			cur->bc_rec.b = PREV;

  			cur->bc_rec.b.br_blockcount =
  				new->br_startoff - PREV.br_startoff;

  			if ((error = xfs_btree_insert(cur, &i)))

  				goto done;

  			XFS_WANT_CORRUPTED_GOTO(i == 1, done);

  			/*
  			 * Reset the cursor to the position of the new extent
  			 * we are about to insert as we can't trust it after
  			 * the previous insert.
  			 */
  			if ((error = xfs_bmbt_lookup_eq(cur, new->br_startoff,
  					new->br_startblock, new->br_blockcount,
  					&i)))

  				goto done;

  			XFS_WANT_CORRUPTED_GOTO(i == 0, done);

  			/* new middle extent - newext */

  			cur->bc_rec.b.br_state = new->br_state;

  			if ((error = xfs_btree_insert(cur, &i)))

  				goto done;

  			XFS_WANT_CORRUPTED_GOTO(i == 1, done);

  		}
  		break;

  	case BMAP_LEFT_FILLING | BMAP_LEFT_CONTIG | BMAP_RIGHT_CONTIG:
  	case BMAP_RIGHT_FILLING | BMAP_LEFT_CONTIG | BMAP_RIGHT_CONTIG:
  	case BMAP_LEFT_FILLING | BMAP_RIGHT_CONTIG:
  	case BMAP_RIGHT_FILLING | BMAP_LEFT_CONTIG:
  	case BMAP_LEFT_CONTIG | BMAP_RIGHT_CONTIG:
  	case BMAP_LEFT_CONTIG:
  	case BMAP_RIGHT_CONTIG:

  		/*
  		 * These cases are all impossible.
  		 */
  		ASSERT(0);
  	}

  
  	/* convert to a btree if necessary */
  	if (XFS_IFORK_FORMAT(ip, XFS_DATA_FORK) == XFS_DINODE_FMT_EXTENTS &&
  	    XFS_IFORK_NEXTENTS(ip, XFS_DATA_FORK) > ifp->if_ext_max) {
  		int	tmp_logflags;	/* partial log flag return val */
  
  		ASSERT(cur == NULL);
  		error = xfs_bmap_extents_to_btree(tp, ip, first, flist, &cur,
  				0, &tmp_logflags, XFS_DATA_FORK);
  		*logflagsp |= tmp_logflags;
  		if (error)
  			goto done;
  	}
  
  	/* clear out the allocated field, done with it now in any case. */
  	if (cur) {
  		cur->bc_private.b.allocated = 0;
  		*curp = cur;
  	}
  
  	xfs_bmap_check_leaf_extents(*curp, ip, XFS_DATA_FORK);

  done:

  	*logflagsp |= rval;

  	return error;
  #undef	LEFT
  #undef	RIGHT
  #undef	PREV

  }
  
  /*

   * Convert a hole to a delayed allocation.

   */

  STATIC void

  xfs_bmap_add_extent_hole_delay(
  	xfs_inode_t		*ip,	/* incore inode pointer */

  	xfs_extnum_t		*idx,	/* extent number to update/insert */

  	xfs_bmbt_irec_t		*new)	/* new data to add to file extents */

  {

  	xfs_ifork_t		*ifp;	/* inode fork pointer */

  	xfs_bmbt_irec_t		left;	/* left neighbor extent entry */
  	xfs_filblks_t		newlen=0;	/* new indirect size */
  	xfs_filblks_t		oldlen=0;	/* old indirect size */
  	xfs_bmbt_irec_t		right;	/* right neighbor extent entry */
  	int			state;  /* state bits, accessed thru macros */

  	xfs_filblks_t		temp=0;	/* temp for indirect calculations */

  	ifp = XFS_IFORK_PTR(ip, XFS_DATA_FORK);

  	state = 0;

  	ASSERT(isnullstartblock(new->br_startblock));

  	/*
  	 * Check and set flags if this segment has a left neighbor
  	 */

  	if (*idx > 0) {

  		state |= BMAP_LEFT_VALID;

  		xfs_bmbt_get_all(xfs_iext_get_ext(ifp, *idx - 1), &left);

  
  		if (isnullstartblock(left.br_startblock))
  			state |= BMAP_LEFT_DELAY;

  	}

  	/*
  	 * Check and set flags if the current (right) segment exists.
  	 * If it doesn't exist, we're converting the hole at end-of-file.
  	 */

  	if (*idx < ip->i_df.if_bytes / (uint)sizeof(xfs_bmbt_rec_t)) {

  		state |= BMAP_RIGHT_VALID;

  		xfs_bmbt_get_all(xfs_iext_get_ext(ifp, *idx), &right);

  
  		if (isnullstartblock(right.br_startblock))
  			state |= BMAP_RIGHT_DELAY;

  	}

  	/*
  	 * Set contiguity flags on the left and right neighbors.
  	 * Don't let extents get too large, even if the pieces are contiguous.
  	 */

  	if ((state & BMAP_LEFT_VALID) && (state & BMAP_LEFT_DELAY) &&
  	    left.br_startoff + left.br_blockcount == new->br_startoff &&
  	    left.br_blockcount + new->br_blockcount <= MAXEXTLEN)
  		state |= BMAP_LEFT_CONTIG;
  
  	if ((state & BMAP_RIGHT_VALID) && (state & BMAP_RIGHT_DELAY) &&
  	    new->br_startoff + new->br_blockcount == right.br_startoff &&
  	    new->br_blockcount + right.br_blockcount <= MAXEXTLEN &&
  	    (!(state & BMAP_LEFT_CONTIG) ||
  	     (left.br_blockcount + new->br_blockcount +
  	      right.br_blockcount <= MAXEXTLEN)))
  		state |= BMAP_RIGHT_CONTIG;

  	/*
  	 * Switch out based on the contiguity flags.
  	 */

  	switch (state & (BMAP_LEFT_CONTIG | BMAP_RIGHT_CONTIG)) {
  	case BMAP_LEFT_CONTIG | BMAP_RIGHT_CONTIG:

  		/*
  		 * New allocation is contiguous with delayed allocations
  		 * on the left and on the right.

  		 * Merge all three into a single extent record.

  		 */

  		--*idx;

  		temp = left.br_blockcount + new->br_blockcount +
  			right.br_blockcount;

  		trace_xfs_bmap_pre_update(ip, *idx, state, _THIS_IP_);
  		xfs_bmbt_set_blockcount(xfs_iext_get_ext(ifp, *idx), temp);

  		oldlen = startblockval(left.br_startblock) +
  			startblockval(new->br_startblock) +
  			startblockval(right.br_startblock);

  		newlen = xfs_bmap_worst_indlen(ip, temp);

  		xfs_bmbt_set_startblock(xfs_iext_get_ext(ifp, *idx),

  			nullstartblock((int)newlen));

  		trace_xfs_bmap_post_update(ip, *idx, state, _THIS_IP_);

  		xfs_iext_remove(ip, *idx + 1, 1, state);

  		break;

  	case BMAP_LEFT_CONTIG:

  		/*
  		 * New allocation is contiguous with a delayed allocation
  		 * on the left.
  		 * Merge the new allocation with the left neighbor.
  		 */

  		--*idx;

  		temp = left.br_blockcount + new->br_blockcount;

  
  		trace_xfs_bmap_pre_update(ip, *idx, state, _THIS_IP_);
  		xfs_bmbt_set_blockcount(xfs_iext_get_ext(ifp, *idx), temp);

  		oldlen = startblockval(left.br_startblock) +
  			startblockval(new->br_startblock);

  		newlen = xfs_bmap_worst_indlen(ip, temp);

  		xfs_bmbt_set_startblock(xfs_iext_get_ext(ifp, *idx),

  			nullstartblock((int)newlen));

  		trace_xfs_bmap_post_update(ip, *idx, state, _THIS_IP_);

  		break;

  	case BMAP_RIGHT_CONTIG:

  		/*
  		 * New allocation is contiguous with a delayed allocation
  		 * on the right.
  		 * Merge the new allocation with the right neighbor.
  		 */

  		trace_xfs_bmap_pre_update(ip, *idx, state, _THIS_IP_);

  		temp = new->br_blockcount + right.br_blockcount;

  		oldlen = startblockval(new->br_startblock) +
  			startblockval(right.br_startblock);

  		newlen = xfs_bmap_worst_indlen(ip, temp);

  		xfs_bmbt_set_allf(xfs_iext_get_ext(ifp, *idx),
  			new->br_startoff,

  			nullstartblock((int)newlen), temp, right.br_state);

  		trace_xfs_bmap_post_update(ip, *idx, state, _THIS_IP_);

  		break;
  
  	case 0:
  		/*
  		 * New allocation is not contiguous with another
  		 * delayed allocation.
  		 * Insert a new entry.
  		 */
  		oldlen = newlen = 0;

  		xfs_iext_insert(ip, *idx, 1, new, state);

  		break;
  	}
  	if (oldlen != newlen) {
  		ASSERT(oldlen > newlen);

  		xfs_icsb_modify_counters(ip->i_mount, XFS_SBS_FDBLOCKS,

  			(int64_t)(oldlen - newlen), 0);

  		/*
  		 * Nothing to do for disk quota accounting here.
  		 */
  	}

  }
  
  /*

   * Convert a hole to a real allocation.

   */
  STATIC int				/* error */
  xfs_bmap_add_extent_hole_real(

  	struct xfs_bmalloca	*bma,
  	int			whichfork)

  {

  	struct xfs_bmbt_irec	*new = &bma->got;

  	int			error;	/* error return value */

  	int			i;	/* temp state */
  	xfs_ifork_t		*ifp;	/* inode fork pointer */
  	xfs_bmbt_irec_t		left;	/* left neighbor extent entry */
  	xfs_bmbt_irec_t		right;	/* right neighbor extent entry */

  	int			rval=0;	/* return value (logging flags) */

  	int			state;	/* state bits, accessed thru macros */

  	ifp = XFS_IFORK_PTR(bma->ip, whichfork);

  	ASSERT(bma->idx >= 0);
  	ASSERT(bma->idx <= ifp->if_bytes / sizeof(struct xfs_bmbt_rec));

  	ASSERT(!isnullstartblock(new->br_startblock));

  	ASSERT(!bma->cur ||
  	       !(bma->cur->bc_private.b.flags & XFS_BTCUR_BPRV_WASDEL));

  
  	XFS_STATS_INC(xs_add_exlist);

  	state = 0;

  	if (whichfork == XFS_ATTR_FORK)
  		state |= BMAP_ATTRFORK;

  	/*
  	 * Check and set flags if this segment has a left neighbor.
  	 */

  	if (bma->idx > 0) {

  		state |= BMAP_LEFT_VALID;

  		xfs_bmbt_get_all(xfs_iext_get_ext(ifp, bma->idx - 1), &left);

  		if (isnullstartblock(left.br_startblock))
  			state |= BMAP_LEFT_DELAY;

  	}

  	/*
  	 * Check and set flags if this segment has a current value.
  	 * Not true if we're inserting into the "hole" at eof.
  	 */

  	if (bma->idx < ifp->if_bytes / (uint)sizeof(xfs_bmbt_rec_t)) {

  		state |= BMAP_RIGHT_VALID;

  		xfs_bmbt_get_all(xfs_iext_get_ext(ifp, bma->idx), &right);

  		if (isnullstartblock(right.br_startblock))
  			state |= BMAP_RIGHT_DELAY;

  	}

  	/*
  	 * We're inserting a real allocation between "left" and "right".
  	 * Set the contiguity flags.  Don't let extents get too large.
  	 */

  	if ((state & BMAP_LEFT_VALID) && !(state & BMAP_LEFT_DELAY) &&
  	    left.br_startoff + left.br_blockcount == new->br_startoff &&
  	    left.br_startblock + left.br_blockcount == new->br_startblock &&
  	    left.br_state == new->br_state &&
  	    left.br_blockcount + new->br_blockcount <= MAXEXTLEN)
  		state |= BMAP_LEFT_CONTIG;
  
  	if ((state & BMAP_RIGHT_VALID) && !(state & BMAP_RIGHT_DELAY) &&
  	    new->br_startoff + new->br_blockcount == right.br_startoff &&
  	    new->br_startblock + new->br_blockcount == right.br_startblock &&
  	    new->br_state == right.br_state &&
  	    new->br_blockcount + right.br_blockcount <= MAXEXTLEN &&
  	    (!(state & BMAP_LEFT_CONTIG) ||
  	     left.br_blockcount + new->br_blockcount +
  	     right.br_blockcount <= MAXEXTLEN))
  		state |= BMAP_RIGHT_CONTIG;

  	error = 0;

  	/*
  	 * Select which case we're in here, and implement it.
  	 */

  	switch (state & (BMAP_LEFT_CONTIG | BMAP_RIGHT_CONTIG)) {
  	case BMAP_LEFT_CONTIG | BMAP_RIGHT_CONTIG: