/*
 * 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_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 */
        void            (*init_fn)(struct xfs_buf *bp,
                                   struct xfs_inode *ip,
                                   struct xfs_ifork *ifp));

/*
 * 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);
}

/*
 * Check if the inode needs to be converted to btree format.
 */
static inline bool xfs_bmap_needs_btree(struct xfs_inode *ip, int whichfork)
{
        return XFS_IFORK_FORMAT(ip, whichfork) == XFS_DINODE_FMT_EXTENTS &&
                XFS_IFORK_NEXTENTS(ip, whichfork) >
                        XFS_IFORK_MAXEXT(ip, whichfork);
}

/*
 * Check if the inode should be converted to extent format.
 */
static inline bool xfs_bmap_wants_extents(struct xfs_inode *ip, int whichfork)
{
        return XFS_IFORK_FORMAT(ip, whichfork) == XFS_DINODE_FMT_BTREE &&
                XFS_IFORK_NEXTENTS(ip, whichfork) <=
                        XFS_IFORK_MAXEXT(ip, whichfork);
}

/*
 * 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;
}

/*
 * Block initialisation functions for local to extent format conversion.
 * As these get more complex, they will be moved to the relevant files,
 * but for now they are too simple to worry about.
 */
STATIC void
xfs_bmap_local_to_extents_init_fn(
        struct xfs_buf          *bp,
        struct xfs_inode        *ip,
        struct xfs_ifork        *ifp)
{
        bp->b_ops = &xfs_bmbt_buf_ops;
        memcpy(bp->b_addr, ifp->if_u1.if_data, ifp->if_bytes);
}

STATIC void
xfs_symlink_local_to_remote(
        struct xfs_buf          *bp,
        struct xfs_inode        *ip,
        struct xfs_ifork        *ifp)
{
        /* remote symlink blocks are not verifiable until CRCs come along */
        bp->b_ops = NULL;
        memcpy(bp->b_addr, ifp->if_u1.if_data, ifp->if_bytes);
}

/*
 * Called from xfs_bmap_add_attrfork to handle local format files. Each
 * different data fork content type needs a different callout to do the
 * conversion. Some are basic and only require special block initialisation
 * callouts for the data formating, others (directories) are so specialised they
 * handle everything themselves.
 *
 * XXX (dgc): investigate whether directory conversion can use the generic
 * formatting callout. It should be possible - it's just a very complex
 * formatter. it would also require passing the transaction through to the init
 * function.
 */
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 */

        if (ip->i_df.if_bytes <= XFS_IFORK_DSIZE(ip))
                return 0;

        if (S_ISDIR(ip->i_d.di_mode)) {
                memset(&dargs, 0, sizeof(dargs));
                dargs.dp = ip;
                dargs.firstblock = firstblock;
                dargs.flist = flist;
                dargs.total = ip->i_mount->m_dirblkfsbs;
                dargs.whichfork = XFS_DATA_FORK;
                dargs.trans = tp;
                return xfs_dir2_sf_to_block(&dargs);
        }

        if (S_ISLNK(ip->i_d.di_mode))
                return xfs_bmap_local_to_extents(tp, ip, firstblock, 1,
                                                 flags, XFS_DATA_FORK,
                                                 xfs_symlink_local_to_remote);

        return xfs_bmap_local_to_extents(tp, ip, firstblock, 1, flags,
                                         XFS_DATA_FORK,
                                         xfs_bmap_local_to_extents_init_fn);
}

/*
 * 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 (xfs_bmap_needs_btree(bma->ip, XFS_DATA_FORK)) {
                        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 (xfs_bmap_needs_btree(bma->ip, XFS_DATA_FORK)) {
                        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 (xfs_bmap_needs_btree(bma->ip, XFS_DATA_FORK)) {
                        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_bmap_needs_btree(bma->ip, XFS_DATA_FORK)) {
                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_bmap_needs_btree(ip, XFS_DATA_FORK)) {
                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:
                /*
                 * New allocation is contiguous with real allocations on the
                 * left and on the right.
                 * Merge all three into a single extent record.
                 */
                --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 + new->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);

                XFS_IFORK_NEXT_SET(bma->ip, whichfork,
                        XFS_IFORK_NEXTENTS(bma->ip, whichfork) - 1);
                if (bma->cur == NULL) {
                        rval = XFS_ILOG_CORE | xfs_ilog_fext(whichfork);
                } 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 +
                                                new->br_blockcount +
                                                right.br_blockcount,
                                        left.br_state);
                        if (error)
                                goto done;
                }
                break;

        case BMAP_LEFT_CONTIG:
                /*
                 * New allocation is contiguous with a real allocation
                 * on the left.
                 * Merge the new allocation with the left neighbor.
                 */
                --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 + new->br_blockcount);
                trace_xfs_bmap_post_update(bma->ip, bma->idx, state, _THIS_IP_);

                if (bma->cur == NULL) {
                        rval = xfs_ilog_fext(whichfork);
                } 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;
                }
                break;

        case BMAP_RIGHT_CONTIG:
                /*
                 * New allocation is contiguous with a real allocation
                 * on the right.
                 * Merge the new allocation with the right neighbor.
                 */
                trace_xfs_bmap_pre_update(bma->ip, bma->idx, state, _THIS_IP_);
                xfs_bmbt_set_allf(xfs_iext_get_ext(ifp, bma->idx),
                        new->br_startoff, new->br_startblock,
                        new->br_blockcount + right.br_blockcount,
                        right.br_state);
                trace_xfs_bmap_post_update(bma->ip, bma->idx, state, _THIS_IP_);

                if (bma->cur == NULL) {
                        rval = xfs_ilog_fext(whichfork);
                } 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;
                }
                break;

        case 0:
                /*
                 * New allocation is not contiguous with another
                 * real allocation.
                 * Insert a new entry.
                 */
                xfs_iext_insert(bma->ip, bma->idx, 1, new, state);
                XFS_IFORK_NEXT_SET(bma->ip, whichfork,
                        XFS_IFORK_NEXTENTS(bma->ip, whichfork) + 1);
                if (bma->cur == NULL) {
                        rval = XFS_ILOG_CORE | xfs_ilog_fext(whichfork);
                } 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 = new->br_state;
                        error = xfs_btree_insert(bma->cur, &i);
                        if (error)
                                goto done;
                        XFS_WANT_CORRUPTED_GOTO(i == 1, done);
                }
                break;
        }

        /* convert to a btree if necessary */
        if (xfs_bmap_needs_btree(bma->ip, whichfork)) {
                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,
                                0, &tmp_logflags, whichfork);
                bma->logflags |= tmp_logflags;
                if (error)
                        goto done;
        }

        /* 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, whichfork);
done:
        bma->logflags |= rval;
        return error;
}

/*
 * Adjust the size of the new extent based on di_extsize and rt extsize.
 */
STATIC int
xfs_bmap_extsize_align(
        xfs_mount_t     *mp,
        xfs_bmbt_irec_t *gotp,          /* next extent pointer */
        xfs_bmbt_irec_t *prevp,         /* previous extent pointer */
        xfs_extlen_t    extsz,          /* align to this extent size */
        int             rt,             /* is this a realtime inode? */
        int             eof,            /* is extent at end-of-file? */
        int             delay,          /* creating delalloc extent? */
        int             convert,        /* overwriting unwritten extent? */
        xfs_fileoff_t   *offp,          /* in/out: aligned offset */
        xfs_extlen_t    *lenp)          /* in/out: aligned length */
{
        xfs_fileoff_t   orig_off;       /* original offset */
        xfs_extlen_t    orig_alen;      /* original length */
        xfs_fileoff_t   orig_end;       /* original off+len */
        xfs_fileoff_t   nexto;          /* next file offset */
        xfs_fileoff_t   prevo;          /* previous file offset */
        xfs_fileoff_t   align_off;      /* temp for offset */
        xfs_extlen_t    align_alen;     /* temp for length */
        xfs_extlen_t    temp;           /* temp for calculations */

        if (convert)
                return 0;

        orig_off = align_off = *offp;
        orig_alen = align_alen = *lenp;
        orig_end = orig_off + orig_alen;

        /*
         * If this request overlaps an existing extent, then don't
         * attempt to perform any additional alignment.
         */
        if (!delay && !eof &&
            (orig_off >= gotp->br_startoff) &&
            (orig_end <= gotp->br_startoff + gotp->br_blockcount)) {
                return 0;
        }

        /*
         * If the file offset is unaligned vs. the extent size
         * we need to align it.  This will be possible unless
         * the file was previously written with a kernel that didn't
         * perform this alignment, or if a truncate shot us in the
         * foot.
         */
        temp = do_mod(orig_off, extsz);
        if (temp) {
                align_alen += temp;
                align_off -= temp;
        }
        /*
         * Same adjustment for the end of the requested area.
         */
        if ((temp = (align_alen % extsz))) {
                align_alen += extsz - temp;
        }
        /*
         * If the previous block overlaps with this proposed allocation
         * then move the start forward without adjusting the length.
         */
        if (prevp->br_startoff != NULLFILEOFF) {
                if (prevp->br_startblock == HOLESTARTBLOCK)
                        prevo = prevp->br_startoff;
                else
                        prevo = prevp->br_startoff + prevp->br_blockcount;
        } else
                prevo = 0;
        if (align_off != orig_off && align_off < prevo)
                align_off = prevo;
        /*
         * If the next block overlaps with this proposed allocation
         * then move the start back without adjusting the length,
         * but not before offset 0.
         * This may of course make the start overlap previous block,
         * and if we hit the offset 0 limit then the next block
         * can still overlap too.
         */
        if (!eof && gotp->br_startoff != NULLFILEOFF) {
                if ((delay && gotp->br_startblock == HOLESTARTBLOCK) ||
                    (!delay && gotp->br_startblock == DELAYSTARTBLOCK))
                        nexto = gotp->br_startoff + gotp->br_blockcount;
                else
                        nexto = gotp->br_startoff;
        } else
                nexto = NULLFILEOFF;
        if (!eof &&
            align_off + align_alen != orig_end &&
            align_off + align_alen > nexto)
                align_off = nexto > align_alen ? nexto - align_alen : 0;
        /*
         * If we're now overlapping the next or previous extent that
         * means we can't fit an extsz piece in this hole.  Just move
         * the start forward to the first valid spot and set
         * the length so we hit the end.
         */
        if (align_off != orig_off && align_off < prevo)
                align_off = prevo;
        if (align_off + align_alen != orig_end &&
            align_off + align_alen > nexto &&
            nexto != NULLFILEOFF) {
                ASSERT(nexto > prevo);

                align_alen = nexto - align_off;
        }

        /*
         * If realtime, and the result isn't a multiple of the realtime
         * extent size we need to remove blocks until it is.
         */
        if (rt && (temp = (align_alen % mp->m_sb.sb_rextsize))) {
                /*
                 * We're not covering the original request, or
                 * we won't be able to once we fix the length.
                 */
                if (orig_off < align_off ||
                    orig_end > align_off + align_alen ||
                    align_alen - temp < orig_alen)
                        return XFS_ERROR(EINVAL);
                /*
                 * Try to fix it by moving the start up.
                 */
                if (align_off + temp <= orig_off) {
                        align_alen -= temp;
                        align_off += temp;
                }
                /*
                 * Try to fix it by moving the end in.
                 */
                else if (align_off + align_alen - temp >= orig_end)
                        align_alen -= temp;
                /*
                 * Set the start to the minimum then trim the length.
                 */
                else {
                        align_alen -= orig_off - align_off;
                        align_off = orig_off;
                        align_alen -= align_alen % mp->m_sb.sb_rextsize;
                }
                /*
                 * Result doesn't cover the request, fail it.
                 */
                if (orig_off < align_off || orig_end > align_off + align_alen)
                        return XFS_ERROR(EINVAL);
        } else {
                ASSERT(orig_off >= align_off);
                ASSERT(orig_end <= align_off + align_alen);
        }

#ifdef DEBUG
        if (!eof && gotp->br_startoff != NULLFILEOFF)
                ASSERT(align_off + align_alen <= gotp->br_startoff);
        if (prevp->br_startoff != NULLFILEOFF)
                ASSERT(align_off >= prevp->br_startoff + prevp->br_blockcount);
#endif

        *lenp = align_alen;
        *offp = align_off;
        return 0;
}

#define XFS_ALLOC_GAP_UNITS     4

STATIC void
xfs_bmap_adjacent(
        xfs_bmalloca_t  *ap)            /* bmap alloc argument struct */
{
        xfs_fsblock_t   adjust;         /* adjustment to block numbers */
        xfs_agnumber_t  fb_agno;        /* ag number of ap->firstblock */
        xfs_mount_t     *mp;            /* mount point structure */
        int             nullfb;         /* true if ap->firstblock isn't set */
        int             rt;             /* true if inode is realtime */

#define ISVALID(x,y)    \
        (rt ? \
                (x) < mp->m_sb.sb_rblocks : \
                XFS_FSB_TO_AGNO(mp, x) == XFS_FSB_TO_AGNO(mp, y) && \
                XFS_FSB_TO_AGNO(mp, x) < mp->m_sb.sb_agcount && \
                XFS_FSB_TO_AGBNO(mp, x) < mp->m_sb.sb_agblocks)

        mp = ap->ip->i_mount;
        nullfb = *ap->firstblock == NULLFSBLOCK;
        rt = XFS_IS_REALTIME_INODE(ap->ip) && ap->userdata;
        fb_agno = nullfb ? NULLAGNUMBER : XFS_FSB_TO_AGNO(mp, *ap->firstblock);
        /*
         * If allocating at eof, and there's a previous real block,
         * try to use its last block as our starting point.
         */
        if (ap->eof && ap->prev.br_startoff != NULLFILEOFF &&
            !isnullstartblock(ap->prev.br_startblock) &&
            ISVALID(ap->prev.br_startblock + ap->prev.br_blockcount,
                    ap->prev.br_startblock)) {
                ap->blkno = ap->prev.br_startblock + ap->prev.br_blockcount;
                /*
                 * Adjust for the gap between prevp and us.
                 */
                adjust = ap->offset -
                        (ap->prev.br_startoff + ap->prev.br_blockcount);
                if (adjust &&
                    ISVALID(ap->blkno + adjust, ap->prev.br_startblock))
                        ap->blkno += adjust;
        }
        /*
         * If not at eof, then compare the two neighbor blocks.
         * Figure out whether either one gives us a good starting point,
         * and pick the better one.
         */
        else if (!ap->eof) {
                xfs_fsblock_t   gotbno;         /* right side block number */
                xfs_fsblock_t   gotdiff=0;      /* right side difference */
                xfs_fsblock_t   prevbno;        /* left side block number */
                xfs_fsblock_t   prevdiff=0;     /* left side difference */

                /*
                 * If there's a previous (left) block, select a requested
                 * start block based on it.
                 */
                if (ap->prev.br_startoff != NULLFILEOFF &&
                    !isnullstartblock(ap->prev.br_startblock) &&
                    (prevbno = ap->prev.br_startblock +
                               ap->prev.br_blockcount) &&
                    ISVALID(prevbno, ap->prev.br_startblock)) {
                        /*
                         * Calculate gap to end of previous block.
                         */
                        adjust = prevdiff = ap->offset -
                                (ap->prev.br_startoff +
                                 ap->prev.br_blockcount);
                        /*
                         * Figure the startblock based on the previous block's
                         * end and the gap size.
                         * Heuristic!
                         * If the gap is large relative to the piece we're
                         * allocating, or using it gives us an invalid block
                         * number, then just use the end of the previous block.
                         */
                        if (prevdiff <= XFS_ALLOC_GAP_UNITS * ap->length &&
                            ISVALID(prevbno + prevdiff,
                                    ap->prev.br_startblock))
                                prevbno += adjust;
                        else
                                prevdiff += adjust;
                        /*
                         * If the firstblock forbids it, can't use it,
                         * must use default.
                         */
                        if (!rt && !nullfb &&
                            XFS_FSB_TO_AGNO(mp, prevbno) != fb_agno)
                                prevbno = NULLFSBLOCK;
                }
                /*
                 * No previous block or can't follow it, just default.
                 */
                else
                        prevbno = NULLFSBLOCK;
                /*
                 * If there's a following (right) block, select a requested
                 * start block based on it.
                 */
                if (!isnullstartblock(ap->got.br_startblock)) {
                        /*
                         * Calculate gap to start of next block.
                         */
                        adjust = gotdiff = ap->got.br_startoff - ap->offset;
                        /*
                         * Figure the startblock based on the next block's
                         * start and the gap size.
                         */
                        gotbno = ap->got.br_startblock;
                        /*
                         * Heuristic!
                         * If the gap is large relative to the piece we're
                         * allocating, or using it gives us an invalid block
                         * number, then just use the start of the next block
                         * offset by our length.
                         */
                        if (gotdiff <= XFS_ALLOC_GAP_UNITS * ap->length &&
                            ISVALID(gotbno - gotdiff, gotbno))
                                gotbno -= adjust;
                        else if (ISVALID(gotbno - ap->length, gotbno)) {
                                gotbno -= ap->length;
                                gotdiff += adjust - ap->length;
                        } else
                                gotdiff += adjust;
                        /*
                         * If the firstblock forbids it, can't use it,
                         * must use default.
                         */
                        if (!rt && !nullfb &&
                            XFS_FSB_TO_AGNO(mp, gotbno) != fb_agno)
                                gotbno = NULLFSBLOCK;
                }
                /*
                 * No next block, just default.
                 */
                else
                        gotbno = NULLFSBLOCK;
                /*
                 * If both valid, pick the better one, else the only good
                 * one, else ap->blkno is already set (to 0 or the inode block).
                 */
                if (prevbno != NULLFSBLOCK && gotbno != NULLFSBLOCK)
                        ap->blkno = prevdiff <= gotdiff ? prevbno : gotbno;
                else if (prevbno != NULLFSBLOCK)
                        ap->blkno = prevbno;
                else if (gotbno != NULLFSBLOCK)
                        ap->blkno = gotbno;
        }
#undef ISVALID
}

STATIC int
xfs_bmap_rtalloc(
        xfs_bmalloca_t  *ap)            /* bmap alloc argument struct */
{
        xfs_alloctype_t atype = 0;      /* type for allocation routines */
        int             error;          /* error return value */
        xfs_mount_t     *mp;            /* mount point structure */
        xfs_extlen_t    prod = 0;       /* product factor for allocators */
        xfs_extlen_t    ralen = 0;      /* realtime allocation length */
        xfs_extlen_t    align;          /* minimum allocation alignment */
        xfs_rtblock_t   rtb;

        mp = ap->ip->i_mount;
        align = xfs_get_extsz_hint(ap->ip);
        prod = align / mp->m_sb.sb_rextsize;
        error = xfs_bmap_extsize_align(mp, &ap->got, &ap->prev,
                                        align, 1, ap->eof, 0,
                                        ap->conv, &ap->offset, &ap->length);
        if (error)
                return error;
        ASSERT(ap->length);
        ASSERT(ap->length % mp->m_sb.sb_rextsize == 0);

        /*
         * If the offset & length are not perfectly aligned
         * then kill prod, it will just get us in trouble.
         */
        if (do_mod(ap->offset, align) || ap->length % align)
                prod = 1;
        /*
         * Set ralen to be the actual requested length in rtextents.
         */
        ralen = ap->length / mp->m_sb.sb_rextsize;
        /*
         * If the old value was close enough to MAXEXTLEN that
         * we rounded up to it, cut it back so it's valid again.
         * Note that if it's a really large request (bigger than
         * MAXEXTLEN), we don't hear about that number, and can't
         * adjust the starting point to match it.
         */
        if (ralen * mp->m_sb.sb_rextsize >= MAXEXTLEN)
                ralen = MAXEXTLEN / mp->m_sb.sb_rextsize;

        /*
         * Lock out other modifications to the RT bitmap inode.
         */
        xfs_ilock(mp->m_rbmip, XFS_ILOCK_EXCL);
        xfs_trans_ijoin(ap->tp, mp->m_rbmip, XFS_ILOCK_EXCL);

        /*
         * If it's an allocation to an empty file at offset 0,
         * pick an extent that will space things out in the rt area.
         */
        if (ap->eof && ap->offset == 0) {
                xfs_rtblock_t uninitialized_var(rtx); /* realtime extent no */

                error = xfs_rtpick_extent(mp, ap->tp, ralen, &rtx);
                if (error)
                        return error;
                ap->blkno = rtx * mp->m_sb.sb_rextsize;
        } else {
                ap->blkno = 0;
        }

        xfs_bmap_adjacent(ap);

        /*
         * Realtime allocation, done through xfs_rtallocate_extent.
         */
        atype = ap->blkno == 0 ?  XFS_ALLOCTYPE_ANY_AG : XFS_ALLOCTYPE_NEAR_BNO;
        do_div(ap->blkno, mp->m_sb.sb_rextsize);
        rtb = ap->blkno;
        ap->length = ralen;
        if ((error = xfs_rtallocate_extent(ap->tp, ap->blkno, 1, ap->length,
                                &ralen, atype, ap->wasdel, prod, &rtb)))
                return error;
        if (rtb == NULLFSBLOCK && prod > 1 &&
            (error = xfs_rtallocate_extent(ap->tp, ap->blkno, 1,
                                           ap->length, &ralen, atype,
                                           ap->wasdel, 1, &rtb)))
                return error;
        ap->blkno = rtb;
        if (ap->blkno != NULLFSBLOCK) {
                ap->blkno *= mp->m_sb.sb_rextsize;
                ralen *= mp->m_sb.sb_rextsize;
                ap->length = ralen;
                ap->ip->i_d.di_nblocks += ralen;
                xfs_trans_log_inode(ap->tp, ap->ip, XFS_ILOG_CORE);
                if (ap->wasdel)
                        ap->ip->i_delayed_blks -= ralen;
                /*
                 * Adjust the disk quota also. This was reserved
                 * earlier.
                 */
                xfs_trans_mod_dquot_byino(ap->tp, ap->ip,
                        ap->wasdel ? XFS_TRANS_DQ_DELRTBCOUNT :
                                        XFS_TRANS_DQ_RTBCOUNT, (long) ralen);
        } else {
                ap->length = 0;
        }
        return 0;
}

STATIC int
xfs_bmap_btalloc_nullfb(
        struct xfs_bmalloca     *ap,
        struct xfs_alloc_arg    *args,
        xfs_extlen_t            *blen)
{
        struct xfs_mount        *mp = ap->ip->i_mount;
        struct xfs_perag        *pag;
        xfs_agnumber_t          ag, startag;
        int                     notinit = 0;
        int                     error;

        if (ap->userdata && xfs_inode_is_filestream(ap->ip))
                args->type = XFS_ALLOCTYPE_NEAR_BNO;
        else
                args->type = XFS_ALLOCTYPE_START_BNO;
        args->total = ap->total;

        /*
         * Search for an allocation group with a single extent large enough
         * for the request.  If one isn't found, then adjust the minimum
         * allocation size to the largest space found.
         */
        startag = ag = XFS_FSB_TO_AGNO(mp, args->fsbno);
        if (startag == NULLAGNUMBER)
                startag = ag = 0;

        pag = xfs_perag_get(mp, ag);
        while (*blen < args->maxlen) {
                if (!pag->pagf_init) {
                        error = xfs_alloc_pagf_init(mp, args->tp, ag,
                                                    XFS_ALLOC_FLAG_TRYLOCK);
                        if (error) {
                                xfs_perag_put(pag);
                                return error;
                        }
                }

                /*
                 * See xfs_alloc_fix_freelist...
                 */
                if (pag->pagf_init) {
                        xfs_extlen_t    longest;
                        longest = xfs_alloc_longest_free_extent(mp, pag);
                        if (*blen < longest)
                                *blen = longest;
                } else
                        notinit = 1;

                if (xfs_inode_is_filestream(ap->ip)) {
                        if (*blen >= args->maxlen)
                                break;

                        if (ap->userdata) {
                                /*
                                 * If startag is an invalid AG, we've
                                 * come here once before and
                                 * xfs_filestream_new_ag picked the
                                 * best currently available.
                                 *
                                 * Don't continue looping, since we
                                 * could loop forever.
                                 */
                                if (startag == NULLAGNUMBER)
                                        break;

                                error = xfs_filestream_new_ag(ap, &ag);
                                xfs_perag_put(pag);
                                if (error)
                                        return error;

                                /* loop again to set 'blen'*/
                                startag = NULLAGNUMBER;
                                pag = xfs_perag_get(mp, ag);
                                continue;
                        }
                }
                if (++ag == mp->m_sb.sb_agcount)
                        ag = 0;
                if (ag == startag)
                        break;
                xfs_perag_put(pag);
                pag = xfs_perag_get(mp, ag);
        }
        xfs_perag_put(pag);

        /*
         * Since the above loop did a BUF_TRYLOCK, it is
         * possible that there is space for this request.
         */
        if (notinit || *blen < ap->minlen)
                args->minlen = ap->minlen;
        /*
         * If the best seen length is less than the request
         * length, use the best as the minimum.
         */
        else if (*blen < args->maxlen)
                args->minlen = *blen;
        /*
         * Otherwise we've seen an extent as big as maxlen,
         * use that as the minimum.
         */
        else
                args->minlen = args->maxlen;

        /*
         * set the failure fallback case to look in the selected
         * AG as the stream may have moved.
         */
        if (xfs_inode_is_filestream(ap->ip))
                ap->blkno = args->fsbno = XFS_AGB_TO_FSB(mp, ag, 0);

        return 0;
}

STATIC int
xfs_bmap_btalloc(
        xfs_bmalloca_t  *ap)            /* bmap alloc argument struct */
{
        xfs_mount_t     *mp;            /* mount point structure */
        xfs_alloctype_t atype = 0;      /* type for allocation routines */
        xfs_extlen_t    align;          /* minimum allocation alignment */
        xfs_agnumber_t  fb_agno;        /* ag number of ap->firstblock */
        xfs_agnumber_t  ag;
        xfs_alloc_arg_t args;
        xfs_extlen_t    blen;
        xfs_extlen_t    nextminlen = 0;
        int             nullfb;         /* true if ap->firstblock isn't set */
        int             isaligned;
        int             tryagain;
        int             error;

        ASSERT(ap->length);

        mp = ap->ip->i_mount;
        align = ap->userdata ? xfs_get_extsz_hint(ap->ip) : 0;
        if (unlikely(align)) {
                error = xfs_bmap_extsize_align(mp, &ap->got, &ap->prev,
                                                align, 0, ap->eof, 0, ap->conv,
                                                &ap->offset, &ap->length);
                ASSERT(!error);
                ASSERT(ap->length);
        }
        nullfb = *ap->firstblock == NULLFSBLOCK;
        fb_agno = nullfb ? NULLAGNUMBER : XFS_FSB_TO_AGNO(mp, *ap->firstblock);
        if (nullfb) {
                if (ap->userdata && xfs_inode_is_filestream(ap->ip)) {
                        ag = xfs_filestream_lookup_ag(ap->ip);
                        ag = (ag != NULLAGNUMBER) ? ag : 0;
                        ap->blkno = XFS_AGB_TO_FSB(mp, ag, 0);
                } else {
                        ap->blkno = XFS_INO_TO_FSB(mp, ap->ip->i_ino);
                }
        } else
                ap->blkno = *ap->firstblock;

        xfs_bmap_adjacent(ap);

        /*
         * If allowed, use ap->blkno; otherwise must use firstblock since
         * it's in the right allocation group.
         */
        if (nullfb || XFS_FSB_TO_AGNO(mp, ap->blkno) == fb_agno)
                ;
        else
                ap->blkno = *ap->firstblock;
        /*
         * Normal allocation, done through xfs_alloc_vextent.
         */
        tryagain = isaligned = 0;
        memset(&args, 0, sizeof(args));
        args.tp = ap->tp;
        args.mp = mp;
        args.fsbno = ap->blkno;

        /* Trim the allocation back to the maximum an AG can fit. */
        args.maxlen = MIN(ap->length, XFS_ALLOC_AG_MAX_USABLE(mp));
        args.firstblock = *ap->firstblock;
        blen = 0;
        if (nullfb) {
                error = xfs_bmap_btalloc_nullfb(ap, &args, &blen);
                if (error)
                        return error;
        } else if (ap->flist->xbf_low) {
                if (xfs_inode_is_filestream(ap->ip))
                        args.type = XFS_ALLOCTYPE_FIRST_AG;
                else
                        args.type = XFS_ALLOCTYPE_START_BNO;
                args.total = args.minlen = ap->minlen;
        } else {
                args.type = XFS_ALLOCTYPE_NEAR_BNO;
                args.total = ap->total;
                args.minlen = ap->minlen;
        }
        /* apply extent size hints if obtained earlier */
        if (unlikely(align)) {
                args.prod = align;
                if ((args.mod = (xfs_extlen_t)do_mod(ap->offset, args.prod)))
                        args.mod = (xfs_extlen_t)(args.prod - args.mod);
        } else if (mp->m_sb.sb_blocksize >= PAGE_CACHE_SIZE) {
                args.prod = 1;
                args.mod = 0;
        } else {
                args.prod = PAGE_CACHE_SIZE >> mp->m_sb.sb_blocklog;
                if ((args.mod = (xfs_extlen_t)(do_mod(ap->offset, args.prod))))
                        args.mod = (xfs_extlen_t)(args.prod - args.mod);
        }
        /*
         * If we are not low on available data blocks, and the
         * underlying logical volume manager is a stripe, and
         * the file offset is zero then try to allocate data
         * blocks on stripe unit boundary.
         * NOTE: ap->aeof is only set if the allocation length
         * is >= the stripe unit and the allocation offset is
         * at the end of file.
         */
        if (!ap->flist->xbf_low && ap->aeof) {
                if (!ap->offset) {
                        args.alignment = mp->m_dalign;
                        atype = args.type;
                        isaligned = 1;
                        /*
                         * Adjust for alignment
                         */
                        if (blen > args.alignment && blen <= args.maxlen)
                                args.minlen = blen - args.alignment;
                        args.minalignslop = 0;
                } else {
                        /*
                         * First try an exact bno allocation.
                         * If it fails then do a near or start bno
                         * allocation with alignment turned on.
                         */
                        atype = args.type;
                        tryagain = 1;
                        args.type = XFS_ALLOCTYPE_THIS_BNO;
                        args.alignment = 1;
                        /*
                         * Compute the minlen+alignment for the
                         * next case.  Set slop so that the value
                         * of minlen+alignment+slop doesn't go up
                         * between the calls.
                         */
                        if (blen > mp->m_dalign && blen <= args.maxlen)
                                nextminlen = blen - mp->m_dalign;
                        else
                                nextminlen = args.minlen;
                        if (nextminlen + mp->m_dalign > args.minlen + 1)
                                args.minalignslop =
                                        nextminlen + mp->m_dalign -
                                        args.minlen - 1;
                        else
                                args.minalignslop = 0;
                }
        } else {
                args.alignment = 1;
                args.minalignslop = 0;
        }
        args.minleft = ap->minleft;
        args.wasdel = ap->wasdel;
        args.isfl = 0;
        args.userdata = ap->userdata;
        if ((error = xfs_alloc_vextent(&args)))
                return error;
        if (tryagain && args.fsbno == NULLFSBLOCK) {
                /*
                 * Exact allocation failed. Now try with alignment
                 * turned on.
                 */
                args.type = atype;
                args.fsbno = ap->blkno;
                args.alignment = mp->m_dalign;
                args.minlen = nextminlen;
                args.minalignslop = 0;
                isaligned = 1;
                if ((error = xfs_alloc_vextent(&args)))
                        return error;
        }
        if (isaligned && args.fsbno == NULLFSBLOCK) {
                /*
                 * allocation failed, so turn off alignment and
                 * try again.
                 */
                args.type = atype;
                args.fsbno = ap->blkno;
                args.alignment = 0;
                if ((error = xfs_alloc_vextent(&args)))
                        return error;
        }
        if (args.fsbno == NULLFSBLOCK && nullfb &&
            args.minlen > ap->minlen) {
                args.minlen = ap->minlen;
                args.type = XFS_ALLOCTYPE_START_BNO;
                args.fsbno = ap->blkno;
                if ((error = xfs_alloc_vextent(&args)))
                        return error;
        }
        if (args.fsbno == NULLFSBLOCK && nullfb) {
                args.fsbno = 0;
                args.type = XFS_ALLOCTYPE_FIRST_AG;
                args.total = ap->minlen;
                args.minleft = 0;
                if ((error = xfs_alloc_vextent(&args)))
                        return error;
                ap->flist->xbf_low = 1;
        }
        if (args.fsbno != NULLFSBLOCK) {
                /*
                 * check the allocation happened at the same or higher AG than
                 * the first block that was allocated.
                 */
                ASSERT(*ap->firstblock == NULLFSBLOCK ||
                       XFS_FSB_TO_AGNO(mp, *ap->firstblock) ==
                       XFS_FSB_TO_AGNO(mp, args.fsbno) ||
                       (ap->flist->xbf_low &&
                        XFS_FSB_TO_AGNO(mp, *ap->firstblock) <
                        XFS_FSB_TO_AGNO(mp, args.fsbno)));

                ap->blkno = args.fsbno;
                if (*ap->firstblock == NULLFSBLOCK)
                        *ap->firstblock = args.fsbno;
                ASSERT(nullfb || fb_agno == args.agno ||
                       (ap->flist->xbf_low && fb_agno < args.agno));
                ap->length = args.len;
                ap->ip->i_d.di_nblocks += args.len;
                xfs_trans_log_inode(ap->tp, ap->ip, XFS_ILOG_CORE);
                if (ap->wasdel)
                        ap->ip->i_delayed_blks -= args.len;
                /*
                 * Adjust the disk quota also. This was reserved
                 * earlier.
                 */
                xfs_trans_mod_dquot_byino(ap->tp, ap->ip,
                        ap->wasdel ? XFS_TRANS_DQ_DELBCOUNT :
                                        XFS_TRANS_DQ_BCOUNT,
                        (long) args.len);
        } else {
                ap->blkno = NULLFSBLOCK;
                ap->length = 0;
        }
        return 0;
}

/*
 * 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
xfs_bmap_alloc(
        xfs_bmalloca_t  *ap)            /* bmap alloc argument struct */
{
        if (XFS_IS_REALTIME_INODE(ap->ip) && ap->userdata)
                return xfs_bmap_rtalloc(ap);
        return xfs_bmap_btalloc(ap);
}

/*
 * 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 */
{
        /* REFERENCED */
        struct xfs_btree_block  *cblock;/* child btree block */
        xfs_fsblock_t           cbno;   /* child block number */
        xfs_buf_t               *cbp;   /* child block's buffer */
        int                     error;  /* error return value */
        xfs_ifork_t             *ifp;   /* inode fork data */
        xfs_mount_t             *mp;    /* mount point structure */
        __be64                  *pp;    /* ptr to block address */
        struct xfs_btree_block  *rblock;/* root btree block */

        mp = ip->i_mount;
        ifp = XFS_IFORK_PTR(ip, whichfork);
        ASSERT(ifp->if_flags & XFS_IFEXTENTS);
        ASSERT(XFS_IFORK_FORMAT(ip, whichfork) == XFS_DINODE_FMT_BTREE);
        rblock = ifp->if_broot;
        ASSERT(be16_to_cpu(rblock->bb_level) == 1);
        ASSERT(be16_to_cpu(rblock->bb_numrecs) == 1);
        ASSERT(xfs_bmbt_maxrecs(mp, ifp->if_broot_bytes, 0) == 1);
        pp = XFS_BMAP_BROOT_PTR_ADDR(mp, rblock, 1, ifp->if_broot_bytes);
        cbno = be64_to_cpu(*pp);
        *logflagsp = 0;
#ifdef DEBUG
        if ((error = xfs_btree_check_lptr(cur, cbno, 1)))
                return error;
#endif
        error = xfs_btree_read_bufl(mp, tp, cbno, 0, &cbp, XFS_BMAP_BTREE_REF,
                                &xfs_bmbt_buf_ops);
        if (error)
                return error;
        cblock = XFS_BUF_TO_BLOCK(cbp);
        if ((error = xfs_btree_check_block(cur, cblock, 0, cbp)))
                return error;
        xfs_bmap_add_free(cbno, 1, cur->bc_private.b.flist, mp);
        ip->i_d.di_nblocks--;
        xfs_trans_mod_dquot_byino(tp, ip, XFS_TRANS_DQ_BCOUNT, -1L);
        xfs_trans_binval(tp, cbp);
        if (cur->bc_bufs[0] == cbp)
                cur->bc_bufs[0] = NULL;
        xfs_iroot_realloc(ip, -1, whichfork);
        ASSERT(ifp->if_broot == NULL);
        ASSERT((ifp->if_flags & XFS_IFBROOT) == 0);
        XFS_IFORK_FMT_SET(ip, whichfork, XFS_DINODE_FMT_EXTENTS);
        *logflagsp = XFS_ILOG_CORE | xfs_ilog_fext(whichfork);
        return 0;
}

/*
 * Called by xfs_bmapi to update file extent records and the btree
 * after removing space (or undoing a delayed allocation).
 */
STATIC int                              /* error */
xfs_bmap_del_extent(
        xfs_inode_t             *ip,    /* incore inode pointer */
        xfs_trans_t             *tp,    /* current transaction pointer */
        xfs_extnum_t            *idx,   /* extent number to update/delete */
        xfs_bmap_free_t         *flist, /* list of extents to be freed */
        xfs_btree_cur_t         *cur,   /* if null, not a btree */
        xfs_bmbt_irec_t         *del,   /* data to remove from extents */
        int                     *logflagsp, /* inode logging flags */
        int                     whichfork) /* data or attr fork */
{
        xfs_filblks_t           da_new; /* new delay-alloc indirect blocks */
        xfs_filblks_t           da_old; /* old delay-alloc indirect blocks */
        xfs_fsblock_t           del_endblock=0; /* first block past del */
        xfs_fileoff_t           del_endoff;     /* first offset past del */
        int                     delay;  /* current block is delayed allocated */
        int                     do_fx;  /* free extent at end of routine */
        xfs_bmbt_rec_host_t     *ep;    /* current extent entry pointer */
        int                     error;  /* error return value */
        int                     flags;  /* inode logging flags */
        xfs_bmbt_irec_t         got;    /* current extent entry */
        xfs_fileoff_t           got_endoff;     /* first offset past got */
        int                     i;      /* temp state */
        xfs_ifork_t             *ifp;   /* inode fork pointer */
        xfs_mount_t             *mp;    /* mount structure */
        xfs_filblks_t           nblks;  /* quota/sb block count */
        xfs_bmbt_irec_t         new;    /* new record to be inserted */
        /* REFERENCED */
        uint                    qfield; /* quota field to update */
        xfs_filblks_t           temp;   /* for indirect length calculations */
        xfs_filblks_t           temp2;  /* for indirect length calculations */
        int                     state = 0;

        XFS_STATS_INC(xs_del_exlist);

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

        mp = ip->i_mount;
        ifp = XFS_IFORK_PTR(ip, whichfork);
        ASSERT((*idx >= 0) && (*idx < ifp->if_bytes /
                (uint)sizeof(xfs_bmbt_rec_t)));
        ASSERT(del->br_blockcount > 0);
        ep = xfs_iext_get_ext(ifp, *idx);
        xfs_bmbt_get_all(ep, &got);
        ASSERT(got.br_startoff <= del->br_startoff);
        del_endoff = del->br_startoff + del->br_blockcount;
        got_endoff = got.br_startoff + got.br_blockcount;
        ASSERT(got_endoff >= del_endoff);
        delay = isnullstartblock(got.br_startblock);
        ASSERT(isnullstartblock(del->br_startblock) == delay);
        flags = 0;
        qfield = 0;
        error = 0;
        /*
         * If deleting a real allocation, must free up the disk space.
         */
        if (!delay) {
                flags = XFS_ILOG_CORE;
                /*
                 * Realtime allocation.  Free it and record di_nblocks update.
                 */
                if (whichfork == XFS_DATA_FORK && XFS_IS_REALTIME_INODE(ip)) {
                        xfs_fsblock_t   bno;
                        xfs_filblks_t   len;

                        ASSERT(do_mod(del->br_blockcount,
                                      mp->m_sb.sb_rextsize) == 0);
                        ASSERT(do_mod(del->br_startblock,
                                      mp->m_sb.sb_rextsize) == 0);
                        bno = del->br_startblock;
                        len = del->br_blockcount;
                        do_div(bno, mp->m_sb.sb_rextsize);
                        do_div(len, mp->m_sb.sb_rextsize);
                        error = xfs_rtfree_extent(tp, bno, (xfs_extlen_t)len);
                        if (error)
                                goto done;
                        do_fx = 0;
                        nblks = len * mp->m_sb.sb_rextsize;
                        qfield = XFS_TRANS_DQ_RTBCOUNT;
                }
                /*
                 * Ordinary allocation.
                 */
                else {
                        do_fx = 1;
                        nblks = del->br_blockcount;
                        qfield = XFS_TRANS_DQ_BCOUNT;
                }
                /*
                 * Set up del_endblock and cur for later.
                 */
                del_endblock = del->br_startblock + del->br_blockcount;
                if (cur) {
                        if ((error = xfs_bmbt_lookup_eq(cur, got.br_startoff,
                                        got.br_startblock, got.br_blockcount,
                                        &i)))
                                goto done;
                        XFS_WANT_CORRUPTED_GOTO(i == 1, done);
                }
                da_old = da_new = 0;
        } else {
                da_old = startblockval(got.br_startblock);
                da_new = 0;
                nblks = 0;
                do_fx = 0;
        }
        /*
         * Set flag value to use in switch statement.
         * Left-contig is 2, right-contig is 1.
         */
        switch (((got.br_startoff == del->br_startoff) << 1) |
                (got_endoff == del_endoff)) {
        case 3:
                /*
                 * Matches the whole extent.  Delete the entry.
                 */
                xfs_iext_remove(ip, *idx, 1,
                                whichfork == XFS_ATTR_FORK ? BMAP_ATTRFORK : 0);
                --*idx;
                if (delay)
                        break;

                XFS_IFORK_NEXT_SET(ip, whichfork,
                        XFS_IFORK_NEXTENTS(ip, whichfork) - 1);
                flags |= XFS_ILOG_CORE;
                if (!cur) {
                        flags |= xfs_ilog_fext(whichfork);
                        break;
                }
                if ((error = xfs_btree_delete(cur, &i)))
                        goto done;
                XFS_WANT_CORRUPTED_GOTO(i == 1, done);
                break;

        case 2:
                /*
                 * Deleting the first part of the extent.
                 */
                trace_xfs_bmap_pre_update(ip, *idx, state, _THIS_IP_);
                xfs_bmbt_set_startoff(ep, del_endoff);
                temp = got.br_blockcount - del->br_blockcount;
                xfs_bmbt_set_blockcount(ep, temp);
                if (delay) {
                        temp = XFS_FILBLKS_MIN(xfs_bmap_worst_indlen(ip, temp),
                                da_old);
                        xfs_bmbt_set_startblock(ep, nullstartblock((int)temp));
                        trace_xfs_bmap_post_update(ip, *idx, state, _THIS_IP_);
                        da_new = temp;
                        break;
                }
                xfs_bmbt_set_startblock(ep, del_endblock);
                trace_xfs_bmap_post_update(ip, *idx, state, _THIS_IP_);
                if (!cur) {
                        flags |= xfs_ilog_fext(whichfork);
                        break;
                }
                if ((error = xfs_bmbt_update(cur, del_endoff, del_endblock,
                                got.br_blockcount - del->br_blockcount,
                                got.br_state)))
                        goto done;
                break;

        case 1:
                /*
                 * Deleting the last part of the extent.
                 */
                temp = got.br_blockcount - del->br_blockcount;
                trace_xfs_bmap_pre_update(ip, *idx, state, _THIS_IP_);
                xfs_bmbt_set_blockcount(ep, temp);
                if (delay) {
                        temp = XFS_FILBLKS_MIN(xfs_bmap_worst_indlen(ip, temp),
                                da_old);
                        xfs_bmbt_set_startblock(ep, nullstartblock((int)temp));
                        trace_xfs_bmap_post_update(ip, *idx, state, _THIS_IP_);
                        da_new = temp;
                        break;
                }
                trace_xfs_bmap_post_update(ip, *idx, state, _THIS_IP_);
                if (!cur) {
                        flags |= xfs_ilog_fext(whichfork);
                        break;
                }
                if ((error = xfs_bmbt_update(cur, got.br_startoff,
                                got.br_startblock,
                                got.br_blockcount - del->br_blockcount,
                                got.br_state)))
                        goto done;
                break;

        case 0:
                /*
                 * Deleting the middle of the extent.
                 */
                temp = del->br_startoff - got.br_startoff;
                trace_xfs_bmap_pre_update(ip, *idx, state, _THIS_IP_);
                xfs_bmbt_set_blockcount(ep, temp);
                new.br_startoff = del_endoff;
                temp2 = got_endoff - del_endoff;
                new.br_blockcount = temp2;
                new.br_state = got.br_state;
                if (!delay) {
                        new.br_startblock = del_endblock;
                        flags |= XFS_ILOG_CORE;
                        if (cur) {
                                if ((error = xfs_bmbt_update(cur,
                                                got.br_startoff,
                                                got.br_startblock, temp,
                                                got.br_state)))
                                        goto done;
                                if ((error = xfs_btree_increment(cur, 0, &i)))
                                        goto done;
                                cur->bc_rec.b = new;
                                error = xfs_btree_insert(cur, &i);
                                if (error && error != ENOSPC)
                                        goto done;
                                /*
                                 * If get no-space back from btree insert,
                                 * it tried a split, and we have a zero
                                 * block reservation.
                                 * Fix up our state and return the error.
                                 */
                                if (error == ENOSPC) {
                                        /*
                                         * Reset the cursor, don't trust
                                         * it after any insert operation.
                                         */
                                        if ((error = xfs_bmbt_lookup_eq(cur,
                                                        got.br_startoff,
                                                        got.br_startblock,
                                                        temp, &i)))
                                                goto done;
                                        XFS_WANT_CORRUPTED_GOTO(i == 1, done);
                                        /*
                                         * Update the btree record back
                                         * to the original value.
                                         */
                                        if ((error = xfs_bmbt_update(cur,
                                                        got.br_startoff,
                                                        got.br_startblock,
                                                        got.br_blockcount,
                                                        got.br_state)))
                                                goto done;
                                        /*
                                         * Reset the extent record back
                                         * to the original value.
                                         */
                                        xfs_bmbt_set_blockcount(ep,
                                                got.br_blockcount);
                                        flags = 0;
                                        error = XFS_ERROR(ENOSPC);
                                        goto done;
                                }
                                XFS_WANT_CORRUPTED_GOTO(i == 1, done);
                        } else
                                flags |= xfs_ilog_fext(whichfork);
                        XFS_IFORK_NEXT_SET(ip, whichfork,
                                XFS_IFORK_NEXTENTS(ip, whichfork) + 1);
                } else {
                        ASSERT(whichfork == XFS_DATA_FORK);
                        temp = xfs_bmap_worst_indlen(ip, temp);
                        xfs_bmbt_set_startblock(ep, nullstartblock((int)temp));
                        temp2 = xfs_bmap_worst_indlen(ip, temp2);
                        new.br_startblock = nullstartblock((int)temp2);
                        da_new = temp + temp2;
                        while (da_new > da_old) {
                                if (temp) {
                                        temp--;
                                        da_new--;