// SPDX-License-Identifier: GPL-2.0-or-later
/*
 * Copyright (C) 2020 Oracle.  All Rights Reserved.
 * Author: Darrick J. Wong <darrick.wong@oracle.com>
 */
#include "xfs.h"
#include "xfs_fs.h"
#include "xfs_shared.h"
#include "xfs_format.h"
#include "xfs_log_format.h"
#include "xfs_trans_resv.h"
#include "xfs_bit.h"
#include "xfs_mount.h"
#include "xfs_inode.h"
#include "xfs_trans.h"
#include "xfs_btree.h"
#include "xfs_trace.h"
#include "xfs_btree_staging.h"

/*
 * Staging Cursors and Fake Roots for Btrees
 * =========================================
 *
 * A staging btree cursor is a special type of btree cursor that callers must
 * use to construct a new btree index using the btree bulk loader code.  The
 * bulk loading code uses the staging btree cursor to abstract the details of
 * initializing new btree blocks and filling them with records or key/ptr
 * pairs.  Regular btree operations (e.g. queries and modifications) are not
 * supported with staging cursors, and callers must not invoke them.
 *
 * Fake root structures contain all the information about a btree that is under
 * construction by the bulk loading code.  Staging btree cursors point to fake
 * root structures instead of the usual AG header or inode structure.
 *
 * Callers are expected to initialize a fake root structure and pass it into
 * the _stage_cursor function for a specific btree type.  When bulk loading is
 * complete, callers should call the _commit_staged_btree function for that
 * specific btree type to commit the new btree into the filesystem.
 */

/*
 * Don't allow staging cursors to be duplicated because they're supposed to be
 * kept private to a single thread.
 */
STATIC struct xfs_btree_cur *
xfs_btree_fakeroot_dup_cursor(
        struct xfs_btree_cur    *cur)
{
        ASSERT(0);
        return NULL;
}

/*
 * Don't allow block allocation for a staging cursor, because staging cursors
 * do not support regular btree modifications.
 *
 * Bulk loading uses a separate callback to obtain new blocks from a
 * preallocated list, which prevents ENOSPC failures during loading.
 */
STATIC int
xfs_btree_fakeroot_alloc_block(
        struct xfs_btree_cur            *cur,
        const union xfs_btree_ptr       *start_bno,
        union xfs_btree_ptr             *new_bno,
        int                             *stat)
{
        ASSERT(0);
        return -EFSCORRUPTED;
}

/*
 * Don't allow block freeing for a staging cursor, because staging cursors
 * do not support regular btree modifications.
 */
STATIC int
xfs_btree_fakeroot_free_block(
        struct xfs_btree_cur    *cur,
        struct xfs_buf          *bp)
{
        ASSERT(0);
        return -EFSCORRUPTED;
}

/* Initialize a pointer to the root block from the fakeroot. */
STATIC void
xfs_btree_fakeroot_init_ptr_from_cur(
        struct xfs_btree_cur    *cur,
        union xfs_btree_ptr     *ptr)
{
        struct xbtree_afakeroot *afake;

        ASSERT(cur->bc_flags & XFS_BTREE_STAGING);

        afake = cur->bc_ag.afake;
        ptr->s = cpu_to_be32(afake->af_root);
}

/*
 * Bulk Loading for AG Btrees
 * ==========================
 *
 * For a btree rooted in an AG header, pass a xbtree_afakeroot structure to the
 * staging cursor.  Callers should initialize this to zero.
 *
 * The _stage_cursor() function for a specific btree type should call
 * xfs_btree_stage_afakeroot to set up the in-memory cursor as a staging
 * cursor.  The corresponding _commit_staged_btree() function should log the
 * new root and call xfs_btree_commit_afakeroot() to transform the staging
 * cursor into a regular btree cursor.
 */

/* Update the btree root information for a per-AG fake root. */
STATIC void
xfs_btree_afakeroot_set_root(
        struct xfs_btree_cur            *cur,
        const union xfs_btree_ptr       *ptr,
        int                             inc)
{
        struct xbtree_afakeroot *afake = cur->bc_ag.afake;

        ASSERT(cur->bc_flags & XFS_BTREE_STAGING);
        afake->af_root = be32_to_cpu(ptr->s);
        afake->af_levels += inc;
}

/*
 * Initialize a AG-rooted btree cursor with the given AG btree fake root.
 * The btree cursor's bc_ops will be overridden as needed to make the staging
 * functionality work.
 */
void
xfs_btree_stage_afakeroot(
        struct xfs_btree_cur            *cur,
        struct xbtree_afakeroot         *afake)
{
        struct xfs_btree_ops            *nops;

        ASSERT(!(cur->bc_flags & XFS_BTREE_STAGING));
        ASSERT(!(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE));
        ASSERT(cur->bc_tp == NULL);

        nops = kmem_alloc(sizeof(struct xfs_btree_ops), KM_NOFS);
        memcpy(nops, cur->bc_ops, sizeof(struct xfs_btree_ops));
        nops->alloc_block = xfs_btree_fakeroot_alloc_block;
        nops->free_block = xfs_btree_fakeroot_free_block;
        nops->init_ptr_from_cur = xfs_btree_fakeroot_init_ptr_from_cur;
        nops->set_root = xfs_btree_afakeroot_set_root;
        nops->dup_cursor = xfs_btree_fakeroot_dup_cursor;

        cur->bc_ag.afake = afake;
        cur->bc_nlevels = afake->af_levels;
        cur->bc_ops = nops;
        cur->bc_flags |= XFS_BTREE_STAGING;
}

/*
 * Transform an AG-rooted staging btree cursor back into a regular cursor by
 * substituting a real btree root for the fake one and restoring normal btree
 * cursor ops.  The caller must log the btree root change prior to calling
 * this.
 */
void
xfs_btree_commit_afakeroot(
        struct xfs_btree_cur            *cur,
        struct xfs_trans                *tp,
        struct xfs_buf                  *agbp,
        const struct xfs_btree_ops      *ops)
{
        ASSERT(cur->bc_flags & XFS_BTREE_STAGING);
        ASSERT(cur->bc_tp == NULL);

        trace_xfs_btree_commit_afakeroot(cur);

        kmem_free((void *)cur->bc_ops);
        cur->bc_ag.agbp = agbp;
        cur->bc_ops = ops;
        cur->bc_flags &= ~XFS_BTREE_STAGING;
        cur->bc_tp = tp;
}

/*
 * Bulk Loading for Inode-Rooted Btrees
 * ====================================
 *
 * For a btree rooted in an inode fork, pass a xbtree_ifakeroot structure to
 * the staging cursor.  This structure should be initialized as follows:
 *
 * - if_fork_size field should be set to the number of bytes available to the
 *   fork in the inode.
 *
 * - if_fork should point to a freshly allocated struct xfs_ifork.
 *
 * - if_format should be set to the appropriate fork type (e.g.
 *   XFS_DINODE_FMT_BTREE).
 *
 * All other fields must be zero.
 *
 * The _stage_cursor() function for a specific btree type should call
 * xfs_btree_stage_ifakeroot to set up the in-memory cursor as a staging
 * cursor.  The corresponding _commit_staged_btree() function should log the
 * new root and call xfs_btree_commit_ifakeroot() to transform the staging
 * cursor into a regular btree cursor.
 */

/*
 * Initialize an inode-rooted btree cursor with the given inode btree fake
 * root.  The btree cursor's bc_ops will be overridden as needed to make the
 * staging functionality work.  If new_ops is not NULL, these new ops will be
 * passed out to the caller for further overriding.
 */
void
xfs_btree_stage_ifakeroot(
        struct xfs_btree_cur            *cur,
        struct xbtree_ifakeroot         *ifake,
        struct xfs_btree_ops            **new_ops)
{
        struct xfs_btree_ops            *nops;

        ASSERT(!(cur->bc_flags & XFS_BTREE_STAGING));
        ASSERT(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE);
        ASSERT(cur->bc_tp == NULL);

        nops = kmem_alloc(sizeof(struct xfs_btree_ops), KM_NOFS);
        memcpy(nops, cur->bc_ops, sizeof(struct xfs_btree_ops));
        nops->alloc_block = xfs_btree_fakeroot_alloc_block;
        nops->free_block = xfs_btree_fakeroot_free_block;
        nops->init_ptr_from_cur = xfs_btree_fakeroot_init_ptr_from_cur;
        nops->dup_cursor = xfs_btree_fakeroot_dup_cursor;

        cur->bc_ino.ifake = ifake;
        cur->bc_nlevels = ifake->if_levels;
        cur->bc_ops = nops;
        cur->bc_flags |= XFS_BTREE_STAGING;

        if (new_ops)
                *new_ops = nops;
}

/*
 * Transform an inode-rooted staging btree cursor back into a regular cursor by
 * substituting a real btree root for the fake one and restoring normal btree
 * cursor ops.  The caller must log the btree root change prior to calling
 * this.
 */
void
xfs_btree_commit_ifakeroot(
        struct xfs_btree_cur            *cur,
        struct xfs_trans                *tp,
        int                             whichfork,
        const struct xfs_btree_ops      *ops)
{
        ASSERT(cur->bc_flags & XFS_BTREE_STAGING);
        ASSERT(cur->bc_tp == NULL);

        trace_xfs_btree_commit_ifakeroot(cur);

        kmem_free((void *)cur->bc_ops);
        cur->bc_ino.ifake = NULL;
        cur->bc_ino.whichfork = whichfork;
        cur->bc_ops = ops;
        cur->bc_flags &= ~XFS_BTREE_STAGING;
        cur->bc_tp = tp;
}

/*
 * Bulk Loading of Staged Btrees
 * =============================
 *
 * This interface is used with a staged btree cursor to create a totally new
 * btree with a large number of records (i.e. more than what would fit in a
 * single root block).  When the creation is complete, the new root can be
 * linked atomically into the filesystem by committing the staged cursor.
 *
 * Creation of a new btree proceeds roughly as follows:
 *
 * The first step is to initialize an appropriate fake btree root structure and
 * then construct a staged btree cursor.  Refer to the block comments about
 * "Bulk Loading for AG Btrees" and "Bulk Loading for Inode-Rooted Btrees" for
 * more information about how to do this.
 *
 * The second step is to initialize a struct xfs_btree_bload context as
 * documented in the structure definition.
 *
 * The third step is to call xfs_btree_bload_compute_geometry to compute the
 * height of and the number of blocks needed to construct the btree.  See the
 * section "Computing the Geometry of the New Btree" for details about this
 * computation.
 *
 * In step four, the caller must allocate xfs_btree_bload.nr_blocks blocks and
 * save them for later use by ->claim_block().  Bulk loading requires all
 * blocks to be allocated beforehand to avoid ENOSPC failures midway through a
 * rebuild, and to minimize seek distances of the new btree.
 *
 * Step five is to call xfs_btree_bload() to start constructing the btree.
 *
 * The final step is to commit the staging btree cursor, which logs the new
 * btree root and turns the staging cursor into a regular cursor.  The caller
 * is responsible for cleaning up the previous btree blocks, if any.
 *
 * Computing the Geometry of the New Btree
 * =======================================
 *
 * The number of items placed in each btree block is computed via the following
 * algorithm: For leaf levels, the number of items for the level is nr_records
 * in the bload structure.  For node levels, the number of items for the level
 * is the number of blocks in the next lower level of the tree.  For each
 * level, the desired number of items per block is defined as:
 *
 * desired = max(minrecs, maxrecs - slack factor)
 *
 * The number of blocks for the level is defined to be:
 *
 * blocks = floor(nr_items / desired)
 *
 * Note this is rounded down so that the npb calculation below will never fall
 * below minrecs.  The number of items that will actually be loaded into each
 * btree block is defined as:
 *
 * npb =  nr_items / blocks
 *
 * Some of the leftmost blocks in the level will contain one extra record as
 * needed to handle uneven division.  If the number of records in any block
 * would exceed maxrecs for that level, blocks is incremented and npb is
 * recalculated.
 *
 * In other words, we compute the number of blocks needed to satisfy a given
 * loading level, then spread the items as evenly as possible.
 *
 * The height and number of fs blocks required to create the btree are computed
 * and returned via btree_height and nr_blocks.
 */

/*
 * Put a btree block that we're loading onto the ordered list and release it.
 * The btree blocks will be written to disk when bulk loading is finished.
 */
static void
xfs_btree_bload_drop_buf(
        struct list_head        *buffers_list,
        struct xfs_buf          **bpp)
{
        if (*bpp == NULL)
                return;

        if (!xfs_buf_delwri_queue(*bpp, buffers_list))
                ASSERT(0);

        xfs_buf_relse(*bpp);
        *bpp = NULL;
}

/*
 * Allocate and initialize one btree block for bulk loading.
 *
 * The new btree block will have its level and numrecs fields set to the values
 * of the level and nr_this_block parameters, respectively.
 *
 * The caller should ensure that ptrp, bpp, and blockp refer to the left
 * sibling of the new block, if there is any.  On exit, ptrp, bpp, and blockp
 * will all point to the new block.
 */
STATIC int
xfs_btree_bload_prep_block(
        struct xfs_btree_cur            *cur,
        struct xfs_btree_bload          *bbl,
        struct list_head                *buffers_list,
        unsigned int                    level,
        unsigned int                    nr_this_block,
        union xfs_btree_ptr             *ptrp, /* in/out */
        struct xfs_buf                  **bpp, /* in/out */
        struct xfs_btree_block          **blockp, /* in/out */
        void                            *priv)
{
        union xfs_btree_ptr             new_ptr;
        struct xfs_buf                  *new_bp;
        struct xfs_btree_block          *new_block;
        int                             ret;

        if ((cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) &&
            level == cur->bc_nlevels - 1) {
                struct xfs_ifork        *ifp = xfs_btree_ifork_ptr(cur);
                size_t                  new_size;

                ASSERT(*bpp == NULL);

                /* Allocate a new incore btree root block. */
                new_size = bbl->iroot_size(cur, nr_this_block, priv);
                ifp->if_broot = kmem_zalloc(new_size, 0);
                ifp->if_broot_bytes = (int)new_size;

                /* Initialize it and send it out. */
                xfs_btree_init_block_int(cur->bc_mp, ifp->if_broot,
                                XFS_BUF_DADDR_NULL, cur->bc_btnum, level,
                                nr_this_block, cur->bc_ino.ip->i_ino,
                                cur->bc_flags);

                *bpp = NULL;
                *blockp = ifp->if_broot;
                xfs_btree_set_ptr_null(cur, ptrp);
                return 0;
        }

        /* Claim one of the caller's preallocated blocks. */
        xfs_btree_set_ptr_null(cur, &new_ptr);
        ret = bbl->claim_block(cur, &new_ptr, priv);
        if (ret)
                return ret;

        ASSERT(!xfs_btree_ptr_is_null(cur, &new_ptr));

        ret = xfs_btree_get_buf_block(cur, &new_ptr, &new_block, &new_bp);
        if (ret)
                return ret;

        /*
         * The previous block (if any) is the left sibling of the new block,
         * so set its right sibling pointer to the new block and drop it.
         */
        if (*blockp)
                xfs_btree_set_sibling(cur, *blockp, &new_ptr, XFS_BB_RIGHTSIB);
        xfs_btree_bload_drop_buf(buffers_list, bpp);

        /* Initialize the new btree block. */
        xfs_btree_init_block_cur(cur, new_bp, level, nr_this_block);
        xfs_btree_set_sibling(cur, new_block, ptrp, XFS_BB_LEFTSIB);

        /* Set the out parameters. */
        *bpp = new_bp;
        *blockp = new_block;
        xfs_btree_copy_ptrs(cur, ptrp, &new_ptr, 1);
        return 0;
}

/* Load one leaf block. */
STATIC int
xfs_btree_bload_leaf(
        struct xfs_btree_cur            *cur,
        unsigned int                    recs_this_block,
        xfs_btree_bload_get_record_fn   get_record,
        struct xfs_btree_block          *block,
        void                            *priv)
{
        unsigned int                    j;
        int                             ret;

        /* Fill the leaf block with records. */
        for (j = 1; j <= recs_this_block; j++) {
                union xfs_btree_rec     *block_rec;

                ret = get_record(cur, priv);
                if (ret)
                        return ret;
                block_rec = xfs_btree_rec_addr(cur, j, block);
                cur->bc_ops->init_rec_from_cur(cur, block_rec);
        }

        return 0;
}

/*
 * Load one node block with key/ptr pairs.
 *
 * child_ptr must point to a block within the next level down in the tree.  A
 * key/ptr entry will be created in the new node block to the block pointed to
 * by child_ptr.  On exit, child_ptr points to the next block on the child
 * level that needs processing.
 */
STATIC int
xfs_btree_bload_node(
        struct xfs_btree_cur    *cur,
        unsigned int            recs_this_block,
        union xfs_btree_ptr     *child_ptr,
        struct xfs_btree_block  *block)
{
        unsigned int            j;
        int                     ret;

        /* Fill the node block with keys and pointers. */
        for (j = 1; j <= recs_this_block; j++) {
                union xfs_btree_key     child_key;
                union xfs_btree_ptr     *block_ptr;
                union xfs_btree_key     *block_key;
                struct xfs_btree_block  *child_block;
                struct xfs_buf          *child_bp;

                ASSERT(!xfs_btree_ptr_is_null(cur, child_ptr));

                ret = xfs_btree_get_buf_block(cur, child_ptr, &child_block,
                                &child_bp);
                if (ret)
                        return ret;

                block_ptr = xfs_btree_ptr_addr(cur, j, block);
                xfs_btree_copy_ptrs(cur, block_ptr, child_ptr, 1);

                block_key = xfs_btree_key_addr(cur, j, block);
                xfs_btree_get_keys(cur, child_block, &child_key);
                xfs_btree_copy_keys(cur, block_key, &child_key, 1);

                xfs_btree_get_sibling(cur, child_block, child_ptr,
                                XFS_BB_RIGHTSIB);
                xfs_buf_relse(child_bp);
        }

        return 0;
}

/*
 * Compute the maximum number of records (or keyptrs) per block that we want to
 * install at this level in the btree.  Caller is responsible for having set
 * @cur->bc_ino.forksize to the desired fork size, if appropriate.
 */
STATIC unsigned int
xfs_btree_bload_max_npb(
        struct xfs_btree_cur    *cur,
        struct xfs_btree_bload  *bbl,
        unsigned int            level)
{
        unsigned int            ret;

        if (level == cur->bc_nlevels - 1 && cur->bc_ops->get_dmaxrecs)
                return cur->bc_ops->get_dmaxrecs(cur, level);

        ret = cur->bc_ops->get_maxrecs(cur, level);
        if (level == 0)
                ret -= bbl->leaf_slack;
        else
                ret -= bbl->node_slack;
        return ret;
}

/*
 * Compute the desired number of records (or keyptrs) per block that we want to
 * install at this level in the btree, which must be somewhere between minrecs
 * and max_npb.  The caller is free to install fewer records per block.
 */
STATIC unsigned int
xfs_btree_bload_desired_npb(
        struct xfs_btree_cur    *cur,
        struct xfs_btree_bload  *bbl,
        unsigned int            level)
{
        unsigned int            npb = xfs_btree_bload_max_npb(cur, bbl, level);

        /* Root blocks are not subject to minrecs rules. */
        if (level == cur->bc_nlevels - 1)
                return max(1U, npb);

        return max_t(unsigned int, cur->bc_ops->get_minrecs(cur, level), npb);
}

/*
 * Compute the number of records to be stored in each block at this level and
 * the number of blocks for this level.  For leaf levels, we must populate an
 * empty root block even if there are no records, so we have to have at least
 * one block.
 */
STATIC void
xfs_btree_bload_level_geometry(
        struct xfs_btree_cur    *cur,
        struct xfs_btree_bload  *bbl,
        unsigned int            level,
        uint64_t                nr_this_level,
        unsigned int            *avg_per_block,
        uint64_t                *blocks,
        uint64_t                *blocks_with_extra)
{
        uint64_t                npb;
        uint64_t                dontcare;
        unsigned int            desired_npb;
        unsigned int            maxnr;

        maxnr = cur->bc_ops->get_maxrecs(cur, level);

        /*
         * Compute the number of blocks we need to fill each block with the
         * desired number of records/keyptrs per block.  Because desired_npb
         * could be minrecs, we use regular integer division (which rounds
         * the block count down) so that in the next step the effective # of
         * items per block will never be less than desired_npb.
         */
        desired_npb = xfs_btree_bload_desired_npb(cur, bbl, level);
        *blocks = div64_u64_rem(nr_this_level, desired_npb, &dontcare);
        *blocks = max(1ULL, *blocks);

        /*
         * Compute the number of records that we will actually put in each
         * block, assuming that we want to spread the records evenly between
         * the blocks.  Take care that the effective # of items per block (npb)
         * won't exceed maxrecs even for the blocks that get an extra record,
         * since desired_npb could be maxrecs, and in the previous step we
         * rounded the block count down.
         */
        npb = div64_u64_rem(nr_this_level, *blocks, blocks_with_extra);
        if (npb > maxnr || (npb == maxnr && *blocks_with_extra > 0)) {
                (*blocks)++;
                npb = div64_u64_rem(nr_this_level, *blocks, blocks_with_extra);
        }

        *avg_per_block = min_t(uint64_t, npb, nr_this_level);

        trace_xfs_btree_bload_level_geometry(cur, level, nr_this_level,
                        *avg_per_block, desired_npb, *blocks,
                        *blocks_with_extra);
}

/*
 * Ensure a slack value is appropriate for the btree.
 *
 * If the slack value is negative, set slack so that we fill the block to
 * halfway between minrecs and maxrecs.  Make sure the slack is never so large
 * that we can underflow minrecs.
 */
static void
xfs_btree_bload_ensure_slack(
        struct xfs_btree_cur    *cur,
        int                     *slack,
        int                     level)
{
        int                     maxr;
        int                     minr;

        maxr = cur->bc_ops->get_maxrecs(cur, level);
        minr = cur->bc_ops->get_minrecs(cur, level);

        /*
         * If slack is negative, automatically set slack so that we load the
         * btree block approximately halfway between minrecs and maxrecs.
         * Generally, this will net us 75% loading.
         */
        if (*slack < 0)
                *slack = maxr - ((maxr + minr) >> 1);

        *slack = min(*slack, maxr - minr);
}

/*
 * Prepare a btree cursor for a bulk load operation by computing the geometry
 * fields in bbl.  Caller must ensure that the btree cursor is a staging
 * cursor.  This function can be called multiple times.
 */
int
xfs_btree_bload_compute_geometry(
        struct xfs_btree_cur    *cur,
        struct xfs_btree_bload  *bbl,
        uint64_t                nr_records)
{
        uint64_t                nr_blocks = 0;
        uint64_t                nr_this_level;

        ASSERT(cur->bc_flags & XFS_BTREE_STAGING);

        /*
         * Make sure that the slack values make sense for traditional leaf and
         * node blocks.  Inode-rooted btrees will return different minrecs and
         * maxrecs values for the root block (bc_nlevels == level - 1).  We're
         * checking levels 0 and 1 here, so set bc_nlevels such that the btree
         * code doesn't interpret either as the root level.
         */
        cur->bc_nlevels = cur->bc_maxlevels - 1;
        xfs_btree_bload_ensure_slack(cur, &bbl->leaf_slack, 0);
        xfs_btree_bload_ensure_slack(cur, &bbl->node_slack, 1);

        bbl->nr_records = nr_this_level = nr_records;
        for (cur->bc_nlevels = 1; cur->bc_nlevels <= cur->bc_maxlevels;) {
                uint64_t        level_blocks;
                uint64_t        dontcare64;
                unsigned int    level = cur->bc_nlevels - 1;
                unsigned int    avg_per_block;

                xfs_btree_bload_level_geometry(cur, bbl, level, nr_this_level,
                                &avg_per_block, &level_blocks, &dontcare64);

                if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) {
                        /*
                         * If all the items we want to store at this level
                         * would fit in the inode root block, then we have our
                         * btree root and are done.
                         *
                         * Note that bmap btrees forbid records in the root.
                         */
                        if (level != 0 && nr_this_level <= avg_per_block) {
                                nr_blocks++;
                                break;
                        }

                        /*
                         * Otherwise, we have to store all the items for this
                         * level in traditional btree blocks and therefore need
                         * another level of btree to point to those blocks.
                         *
                         * We have to re-compute the geometry for each level of
                         * an inode-rooted btree because the geometry differs
                         * between a btree root in an inode fork and a
                         * traditional btree block.
                         *
                         * This distinction is made in the btree code based on
                         * whether level == bc_nlevels - 1.  Based on the
                         * previous root block size check against the root
                         * block geometry, we know that we aren't yet ready to
                         * populate the root.  Increment bc_nevels and
                         * recalculate the geometry for a traditional
                         * block-based btree level.
                         */
                        cur->bc_nlevels++;
                        ASSERT(cur->bc_nlevels <= cur->bc_maxlevels);
                        xfs_btree_bload_level_geometry(cur, bbl, level,
                                        nr_this_level, &avg_per_block,
                                        &level_blocks, &dontcare64);
                } else {
                        /*
                         * If all the items we want to store at this level
                         * would fit in a single root block, we're done.
                         */
                        if (nr_this_level <= avg_per_block) {
                                nr_blocks++;
                                break;
                        }

                        /* Otherwise, we need another level of btree. */
                        cur->bc_nlevels++;
                        ASSERT(cur->bc_nlevels <= cur->bc_maxlevels);
                }

                nr_blocks += level_blocks;
                nr_this_level = level_blocks;
        }

        if (cur->bc_nlevels > cur->bc_maxlevels)
                return -EOVERFLOW;

        bbl->btree_height = cur->bc_nlevels;
        if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE)
                bbl->nr_blocks = nr_blocks - 1;
        else
                bbl->nr_blocks = nr_blocks;
        return 0;
}

/* Bulk load a btree given the parameters and geometry established in bbl. */
int
xfs_btree_bload(
        struct xfs_btree_cur            *cur,
        struct xfs_btree_bload          *bbl,
        void                            *priv)
{
        struct list_head                buffers_list;
        union xfs_btree_ptr             child_ptr;
        union xfs_btree_ptr             ptr;
        struct xfs_buf                  *bp = NULL;
        struct xfs_btree_block          *block = NULL;
        uint64_t                        nr_this_level = bbl->nr_records;
        uint64_t                        blocks;
        uint64_t                        i;
        uint64_t                        blocks_with_extra;
        uint64_t                        total_blocks = 0;
        unsigned int                    avg_per_block;
        unsigned int                    level = 0;
        int                             ret;

        ASSERT(cur->bc_flags & XFS_BTREE_STAGING);

        INIT_LIST_HEAD(&buffers_list);
        cur->bc_nlevels = bbl->btree_height;
        xfs_btree_set_ptr_null(cur, &child_ptr);
        xfs_btree_set_ptr_null(cur, &ptr);

        xfs_btree_bload_level_geometry(cur, bbl, level, nr_this_level,
                        &avg_per_block, &blocks, &blocks_with_extra);

        /* Load each leaf block. */
        for (i = 0; i < blocks; i++) {
                unsigned int            nr_this_block = avg_per_block;

                /*
                 * Due to rounding, btree blocks will not be evenly populated
                 * in most cases.  blocks_with_extra tells us how many blocks
                 * will receive an extra record to distribute the excess across
                 * the current level as evenly as possible.
                 */
                if (i < blocks_with_extra)
                        nr_this_block++;

                ret = xfs_btree_bload_prep_block(cur, bbl, &buffers_list, level,
                                nr_this_block, &ptr, &bp, &block, priv);
                if (ret)
                        goto out;

                trace_xfs_btree_bload_block(cur, level, i, blocks, &ptr,
                                nr_this_block);

                ret = xfs_btree_bload_leaf(cur, nr_this_block, bbl->get_record,
                                block, priv);
                if (ret)
                        goto out;

                /*
                 * Record the leftmost leaf pointer so we know where to start
                 * with the first node level.
                 */
                if (i == 0)
                        xfs_btree_copy_ptrs(cur, &child_ptr, &ptr, 1);
        }
        total_blocks += blocks;
        xfs_btree_bload_drop_buf(&buffers_list, &bp);

        /* Populate the internal btree nodes. */
        for (level = 1; level < cur->bc_nlevels; level++) {
                union xfs_btree_ptr     first_ptr;

                nr_this_level = blocks;
                block = NULL;
                xfs_btree_set_ptr_null(cur, &ptr);

                xfs_btree_bload_level_geometry(cur, bbl, level, nr_this_level,
                                &avg_per_block, &blocks, &blocks_with_extra);

                /* Load each node block. */
                for (i = 0; i < blocks; i++) {
                        unsigned int    nr_this_block = avg_per_block;

                        if (i < blocks_with_extra)
                                nr_this_block++;

                        ret = xfs_btree_bload_prep_block(cur, bbl,
                                        &buffers_list, level, nr_this_block,
                                        &ptr, &bp, &block, priv);
                        if (ret)
                                goto out;

                        trace_xfs_btree_bload_block(cur, level, i, blocks,
                                        &ptr, nr_this_block);

                        ret = xfs_btree_bload_node(cur, nr_this_block,
                                        &child_ptr, block);
                        if (ret)
                                goto out;

                        /*
                         * Record the leftmost node pointer so that we know
                         * where to start the next node level above this one.
                         */
                        if (i == 0)
                                xfs_btree_copy_ptrs(cur, &first_ptr, &ptr, 1);
                }
                total_blocks += blocks;
                xfs_btree_bload_drop_buf(&buffers_list, &bp);
                xfs_btree_copy_ptrs(cur, &child_ptr, &first_ptr, 1);
        }

        /* Initialize the new root. */
        if (cur->bc_flags & XFS_BTREE_ROOT_IN_INODE) {
                ASSERT(xfs_btree_ptr_is_null(cur, &ptr));
                cur->bc_ino.ifake->if_levels = cur->bc_nlevels;
                cur->bc_ino.ifake->if_blocks = total_blocks - 1;
        } else {
                cur->bc_ag.afake->af_root = be32_to_cpu(ptr.s);
                cur->bc_ag.afake->af_levels = cur->bc_nlevels;
                cur->bc_ag.afake->af_blocks = total_blocks;
        }

        /*
         * Write the new blocks to disk.  If the ordered list isn't empty after
         * that, then something went wrong and we have to fail.  This should
         * never happen, but we'll check anyway.
         */
        ret = xfs_buf_delwri_submit(&buffers_list);
        if (ret)
                goto out;
        if (!list_empty(&buffers_list)) {
                ASSERT(list_empty(&buffers_list));
                ret = -EIO;
        }

out:
        xfs_buf_delwri_cancel(&buffers_list);
        if (bp)
                xfs_buf_relse(bp);
        return ret;
}