static int
__split_parent(WT_SESSION_IMPL *session, WT_REF *ref, WT_REF **ref_new,
    uint32_t new_entries, size_t parent_incr, bool exclusive, bool discard)
{
        WT_DECL_ITEM(scr);
        WT_DECL_RET;
        WT_IKEY *ikey;
        WT_PAGE *parent;
        WT_PAGE_INDEX *alloc_index, *pindex;
        WT_REF **alloc_refp, *next_ref;
        WT_SPLIT_ERROR_PHASE complete;
        size_t parent_decr, size;
        uint64_t split_gen;
        uint32_t hint, i, j;
        uint32_t deleted_entries, parent_entries, result_entries;
        uint32_t *deleted_refs;
        bool empty_parent;

        parent = ref->home;

        alloc_index = pindex = NULL;
        parent_decr = 0;
        parent_entries = 0;
        empty_parent = false;

        complete = WT_ERR_RETURN;

        /* The parent page will be marked dirty, make sure that will succeed. */
        WT_RET(__wt_page_modify_init(session, parent));

        /*
         * We've locked the parent, which means it cannot split (which is the
         * only reason to worry about split generation values).
         */
        pindex = WT_INTL_INDEX_GET_SAFE(parent);
        parent_entries = pindex->entries;

        /*
         * Remove any refs to deleted pages while we are splitting, we have
         * the internal page locked down, and are copying the refs into a new
         * array anyway.  Switch them to the special split state, so that any
         * reading thread will restart.
         */
        WT_ERR(__wt_scr_alloc(session, 10 * sizeof(uint32_t), &scr));
        for (deleted_entries = 0, i = 0; i < parent_entries; ++i) {
                next_ref = pindex->index[i];
                WT_ASSERT(session, next_ref->state != WT_REF_SPLIT);
                if ((discard && next_ref == ref) ||
                    (next_ref->state == WT_REF_DELETED &&
                    __wt_delete_page_skip(session, next_ref, true) &&
                    __wt_atomic_casv32(
                    &next_ref->state, WT_REF_DELETED, WT_REF_SPLIT))) {
                        WT_ERR(__wt_buf_grow(session, scr,
                            (deleted_entries + 1) * sizeof(uint32_t)));
                        deleted_refs = scr->mem;
                        deleted_refs[deleted_entries++] = i;
                }
        }

        /*
         * The final entry count consists of the original count, plus any new
         * pages, less any WT_REFs we're removing (deleted entries plus the
         * entry we're replacing).
         */
        result_entries = (parent_entries + new_entries) - deleted_entries;
        if (!discard)
                --result_entries;

        /*
         * If there are no remaining entries on the parent, give up, we can't
         * leave an empty internal page. Mark it to be evicted soon and clean
         * up any references that have changed state.
         */
        if (result_entries == 0) {
                empty_parent = true;
                __wt_page_evict_soon(parent);
                goto err;
        }

        /*
         * Allocate and initialize a new page index array for the parent, then
         * copy references from the original index array, plus references from
         * the newly created split array, into place.
         *
         * Update the WT_REF's page-index hint as we go. This can race with a
         * thread setting the hint based on an older page-index, and the change
         * isn't backed out in the case of an error, so there ways for the hint
         * to be wrong; OK because it's just a hint.
         */
        size = sizeof(WT_PAGE_INDEX) + result_entries * sizeof(WT_REF *);
        WT_ERR(__wt_calloc(session, 1, size, &alloc_index));
        parent_incr += size;
        alloc_index->index = (WT_REF **)(alloc_index + 1);
        alloc_index->entries = result_entries;
        for (alloc_refp = alloc_index->index,
            hint = i = 0; i < parent_entries; ++i) {
                next_ref = pindex->index[i];
                if (next_ref == ref)
                        for (j = 0; j < new_entries; ++j) {
                                ref_new[j]->home = parent;
                                ref_new[j]->pindex_hint = hint++;
                                *alloc_refp++ = ref_new[j];
                        }
                else if (next_ref->state != WT_REF_SPLIT) {
                        /* Skip refs we have marked for deletion. */
                        next_ref->pindex_hint = hint++;
                        *alloc_refp++ = next_ref;
                }
        }

        /* Check that we filled in all the entries. */
        WT_ASSERT(session,
            alloc_refp - alloc_index->index == (ptrdiff_t)result_entries);

        /* Start making real changes to the tree, errors are fatal. */
        complete = WT_ERR_PANIC;

        /*
         * Confirm the parent page's index hasn't moved then update it, which
         * makes the split visible to threads descending the tree.
         */
        WT_ASSERT(session, WT_INTL_INDEX_GET_SAFE(parent) == pindex);
        WT_INTL_INDEX_SET(parent, alloc_index);
        alloc_index = NULL;

#ifdef HAVE_DIAGNOSTIC
        WT_WITH_PAGE_INDEX(session,
            __split_verify_intl_key_order(session, parent));
#endif

        /*
         * If discarding the page's original WT_REF field, reset it to split.
         * Threads cursoring through the tree were blocked because that WT_REF
         * state was set to locked. Changing the locked state to split unblocks
         * those threads and causes them to re-calculate their position based
         * on the just-updated parent page's index.
         */
        if (discard) {
                /*
                 * Page-delete information is only read when the WT_REF state is
                 * WT_REF_DELETED.  The page-delete memory wasn't added to the
                 * parent's footprint, ignore it here.
                 */
                if (ref->page_del != NULL) {
                        __wt_free(session, ref->page_del->update_list);
                        __wt_free(session, ref->page_del);
                }

                WT_PUBLISH(ref->state, WT_REF_SPLIT);
        }

        /*
         * Push out the changes: not required for correctness, but don't let
         * threads spin on incorrect page references longer than necessary.
         */
        WT_FULL_BARRIER();

        /* The split is complete and correct, ignore benign errors. */

        complete = WT_ERR_IGNORE;

        /*
         * !!!
         * Swapping in the new page index released the page for eviction, we can
         * no longer look inside the page.
         */

        if (ref->page == NULL)
                WT_ERR(__wt_verbose(session, WT_VERB_SPLIT,
                    "%p: reverse split into parent %p, %" PRIu32 " -> %" PRIu32
                    " (-%" PRIu32 ")",
                    ref->page, parent, parent_entries, result_entries,
                    parent_entries - result_entries));
        else
                WT_ERR(__wt_verbose(session, WT_VERB_SPLIT,
                    "%p: split into parent %p, %" PRIu32 " -> %" PRIu32
                    " (+%" PRIu32 ")",
                    ref->page, parent, parent_entries, result_entries,
                    result_entries - parent_entries));

        /*
         * The new page index is in place, free the WT_REF we were splitting and
         * any deleted WT_REFs we found, modulo the usual safe free semantics.
         *
         * Acquire a new split generation.
         */
        split_gen = __wt_atomic_addv64(&S2C(session)->split_gen, 1);
        for (i = 0, deleted_refs = scr->mem; i < deleted_entries; ++i) {
                next_ref = pindex->index[deleted_refs[i]];
                WT_ASSERT(session, next_ref->state == WT_REF_SPLIT);

                /*
                 * We set the WT_REF to split, discard it, freeing any resources
                 * it holds.
                 *
                 * Row-store trees where the old version of the page is being
                 * discarded: the previous parent page's key for this child page
                 * may have been an on-page overflow key.  In that case, if the
                 * key hasn't been deleted, delete it now, including its backing
                 * blocks.  We are exchanging the WT_REF that referenced it for
                 * the split page WT_REFs and their keys, and there's no longer
                 * any reference to it.  Done after completing the split (if we
                 * failed, we'd leak the underlying blocks, but the parent page
                 * would be unaffected).
                 */
                if (parent->type == WT_PAGE_ROW_INT) {
                        WT_TRET(__split_ovfl_key_cleanup(
                            session, parent, next_ref));
                        ikey = __wt_ref_key_instantiated(next_ref);
                        if (ikey != NULL) {
                                size = sizeof(WT_IKEY) + ikey->size;
                                WT_TRET(__split_safe_free(
                                    session, split_gen, exclusive, ikey, size));
                                parent_decr += size;
                        }
                }

                /*
                 * If this page was fast-truncated, any attached structure
                 * should have been freed before now.
                 */
                WT_ASSERT(session, next_ref->page_del == NULL);

                WT_TRET(__wt_ref_block_free(session, next_ref));
                WT_TRET(__split_safe_free(
                    session, split_gen, exclusive, next_ref, sizeof(WT_REF)));
                parent_decr += sizeof(WT_REF);
        }

        /*
         * !!!
         * The original WT_REF has now been freed, we can no longer look at it.
         */

        /*
         * We can't free the previous page index, there may be threads using it.
         * Add it to the session discard list, to be freed when it's safe.
         */
        size = sizeof(WT_PAGE_INDEX) + pindex->entries * sizeof(WT_REF *);
        WT_TRET(__split_safe_free(session, split_gen, exclusive, pindex, size));
        parent_decr += size;

        /* Adjust the parent's memory footprint and mark it dirty. */
        __wt_cache_page_inmem_incr(session, parent, parent_incr);
        __wt_cache_page_inmem_decr(session, parent, parent_decr);
        __wt_page_modify_set(session, parent);

err:        __wt_scr_free(session, &scr);
        /*
         * A note on error handling: if we completed the split, return success,
         * nothing really bad can have happened, and our caller has to proceed
         * with the split.
         */

        switch (complete) {
        case WT_ERR_RETURN:
                for (i = 0; i < parent_entries; ++i) {
                        next_ref = pindex->index[i];
                        if (next_ref->state == WT_REF_SPLIT)
                                next_ref->state = WT_REF_DELETED;
                }

                __wt_free_ref_index(session, NULL, alloc_index, false);
                /*
                 * The split couldn't proceed because the parent would be empty,
                 * return EBUSY so our caller knows to unlock the WT_REF that's
                 * being deleted, but don't be noisy, there's nothing wrong.
                 */
                if (empty_parent)
                        ret = EBUSY;
                break;

        case WT_ERR_PANIC:
                __wt_err(session, ret, "fatal error during parent page split");
                ret = WT_PANIC;
                break;
        case WT_ERR_IGNORE:
                if (ret != 0 && ret != WT_PANIC) {
                        __wt_err(session, ret,
                            "ignoring not-fatal error during parent page "
                            "split");
                        ret = 0;
                }
                break;
        }
        return (ret);
}

/*
 * __split_internal --
 *        Split an internal page into its parent.
 */
static int
__split_internal(WT_SESSION_IMPL *session, WT_PAGE *parent, WT_PAGE *page)
{
        WT_BTREE *btree;
        WT_DECL_RET;
        WT_PAGE *child;
        WT_PAGE_INDEX *alloc_index, *child_pindex, *pindex, *replace_index;