/*-
 * SPDX-License-Identifier: BSD-2-Clause
 *
 * Copyright (c) 2010, 2012 Zheng Liu <lz@freebsd.org>
 * Copyright (c) 2012, Vyacheslav Matyushin
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#include <sys/param.h>
#include <sys/endian.h>
#include <sys/systm.h>
#include <sys/namei.h>
#include <sys/bio.h>
#include <sys/buf.h>
#include <sys/endian.h>
#include <sys/mount.h>
#include <sys/vnode.h>
#include <sys/malloc.h>
#include <sys/dirent.h>
#include <sys/sdt.h>
#include <sys/sysctl.h>

#include <ufs/ufs/dir.h>

#include <fs/ext2fs/fs.h>
#include <fs/ext2fs/inode.h>
#include <fs/ext2fs/ext2_mount.h>
#include <fs/ext2fs/ext2fs.h>
#include <fs/ext2fs/fs.h>
#include <fs/ext2fs/ext2_extern.h>
#include <fs/ext2fs/ext2_dinode.h>
#include <fs/ext2fs/ext2_dir.h>
#include <fs/ext2fs/htree.h>

SDT_PROVIDER_DECLARE(ext2fs);
/*
 * ext2fs trace probe:
 * arg0: verbosity. Higher numbers give more verbose messages
 * arg1: Textual message
 */
SDT_PROBE_DEFINE2(ext2fs, , trace, htree, "int", "char*");

static void     ext2_append_entry(char *block, uint32_t blksize,
                    struct ext2fs_direct_2 *last_entry,
                    struct ext2fs_direct_2 *new_entry, int csum_size);
static int      ext2_htree_append_block(struct vnode *vp, char *data,
                    struct componentname *cnp, uint32_t blksize);
static int      ext2_htree_check_next(struct inode *ip, uint32_t hash,
                    const char *name, struct ext2fs_htree_lookup_info *info);
static int      ext2_htree_cmp_sort_entry(const void *e1, const void *e2);
static int      ext2_htree_find_leaf(struct inode *ip, const char *name,
                    int namelen, uint32_t *hash, uint8_t *hash_version,
                    struct ext2fs_htree_lookup_info *info);
static uint32_t ext2_htree_get_block(struct ext2fs_htree_entry *ep);
static uint16_t ext2_htree_get_count(struct ext2fs_htree_entry *ep);
static uint32_t ext2_htree_get_hash(struct ext2fs_htree_entry *ep);
static uint16_t ext2_htree_get_limit(struct ext2fs_htree_entry *ep);
static void     ext2_htree_insert_entry_to_level(struct ext2fs_htree_lookup_level *level,
                    uint32_t hash, uint32_t blk);
static void     ext2_htree_insert_entry(struct ext2fs_htree_lookup_info *info,
                    uint32_t hash, uint32_t blk);
static uint32_t ext2_htree_node_limit(struct inode *ip);
static void     ext2_htree_set_block(struct ext2fs_htree_entry *ep,
                    uint32_t blk);
static void     ext2_htree_set_count(struct ext2fs_htree_entry *ep,
                    uint16_t cnt);
static void     ext2_htree_set_hash(struct ext2fs_htree_entry *ep,
                    uint32_t hash);
static void     ext2_htree_set_limit(struct ext2fs_htree_entry *ep,
                    uint16_t limit);
static int      ext2_htree_split_dirblock(struct inode *ip,
                    char *block1, char *block2, uint32_t blksize,
                    uint32_t *hash_seed, uint8_t hash_version,
                    uint32_t *split_hash, struct  ext2fs_direct_2 *entry);
static void     ext2_htree_release(struct ext2fs_htree_lookup_info *info);
static uint32_t ext2_htree_root_limit(struct inode *ip, int len);
static int      ext2_htree_writebuf(struct inode *ip,
                    struct ext2fs_htree_lookup_info *info);

int
ext2_htree_has_idx(struct inode *ip)
{
        if (EXT2_HAS_COMPAT_FEATURE(ip->i_e2fs, EXT2F_COMPAT_DIRHASHINDEX) &&
            ip->i_flag & IN_E3INDEX)
                return (1);
        else
                return (0);
}

static int
ext2_htree_check_next(struct inode *ip, uint32_t hash, const char *name,
    struct ext2fs_htree_lookup_info *info)
{
        struct vnode *vp = ITOV(ip);
        struct ext2fs_htree_lookup_level *level;
        struct buf *bp;
        uint32_t next_hash;
        int idx = info->h_levels_num - 1;
        int levels = 0;

        do {
                level = &info->h_levels[idx];
                level->h_entry++;
                if (level->h_entry < level->h_entries +
                    ext2_htree_get_count(level->h_entries))
                        break;
                if (idx == 0)
                        return (0);
                idx--;
                levels++;
        } while (1);

        next_hash = ext2_htree_get_hash(level->h_entry);
        if ((hash & 1) == 0) {
                if (hash != (next_hash & ~1))
                        return (0);
        }

        while (levels > 0) {
                levels--;
                if (ext2_blkatoff(vp, ext2_htree_get_block(level->h_entry) *
                    ip->i_e2fs->e2fs_bsize, NULL, &bp) != 0)
                        return (0);
                level = &info->h_levels[idx + 1];
                brelse(level->h_bp);
                level->h_bp = bp;
                level->h_entry = level->h_entries =
                    ((struct ext2fs_htree_node *)bp->b_data)->h_entries;
        }

        return (1);
}

static uint32_t
ext2_htree_get_block(struct ext2fs_htree_entry *ep)
{
        return (le32toh(ep->h_blk) & 0x00FFFFFF);
}

static void
ext2_htree_set_block(struct ext2fs_htree_entry *ep, uint32_t blk)
{
        ep->h_blk = htole32(blk);
}

static uint16_t
ext2_htree_get_count(struct ext2fs_htree_entry *ep)
{
        return (le16toh(((struct ext2fs_htree_count *)(ep))->h_entries_num));
}

static void
ext2_htree_set_count(struct ext2fs_htree_entry *ep, uint16_t cnt)
{
        ((struct ext2fs_htree_count *)(ep))->h_entries_num = htole16(cnt);
}

static uint32_t
ext2_htree_get_hash(struct ext2fs_htree_entry *ep)
{
        return (le32toh(ep->h_hash));
}

static uint16_t
ext2_htree_get_limit(struct ext2fs_htree_entry *ep)
{
        return (le16toh(((struct ext2fs_htree_count *)(ep))->h_entries_max));
}

static void
ext2_htree_set_hash(struct ext2fs_htree_entry *ep, uint32_t hash)
{
        ep->h_hash = htole32(hash);
}

static void
ext2_htree_set_limit(struct ext2fs_htree_entry *ep, uint16_t limit)
{
        ((struct ext2fs_htree_count *)(ep))->h_entries_max = htole16(limit);
}

static void
ext2_htree_release(struct ext2fs_htree_lookup_info *info)
{
        u_int i;

        for (i = 0; i < info->h_levels_num; i++) {
                struct buf *bp = info->h_levels[i].h_bp;

                if (bp != NULL)
                        brelse(bp);
        }
}

static uint32_t
ext2_htree_root_limit(struct inode *ip, int len)
{
        struct m_ext2fs *fs;
        uint32_t space;

        fs = ip->i_e2fs;
        space = ip->i_e2fs->e2fs_bsize - EXT2_DIR_REC_LEN(1) -
            EXT2_DIR_REC_LEN(2) - len;

        if (EXT2_HAS_RO_COMPAT_FEATURE(fs, EXT2F_ROCOMPAT_METADATA_CKSUM))
                space -= sizeof(struct ext2fs_htree_tail);

        return (space / sizeof(struct ext2fs_htree_entry));
}

static uint32_t
ext2_htree_node_limit(struct inode *ip)
{
        struct m_ext2fs *fs;
        uint32_t space;

        fs = ip->i_e2fs;
        space = fs->e2fs_bsize - EXT2_DIR_REC_LEN(0);

        if (EXT2_HAS_RO_COMPAT_FEATURE(fs, EXT2F_ROCOMPAT_METADATA_CKSUM))
                space -= sizeof(struct ext2fs_htree_tail);

        return (space / sizeof(struct ext2fs_htree_entry));
}

static void
ext2_get_hash_seed(struct ext2fs* es, uint32_t* seed)
{

        for (int i = 0; i < 4; i++)
                seed[i] = le32toh(es->e3fs_hash_seed[i]);
}

static int
ext2_htree_find_leaf(struct inode *ip, const char *name, int namelen,
    uint32_t *hash, uint8_t *hash_ver,
    struct ext2fs_htree_lookup_info *info)
{
        struct vnode *vp;
        struct ext2fs *fs;
        struct m_ext2fs *m_fs;
        struct buf *bp = NULL;
        struct ext2fs_htree_root *rootp;
        struct ext2fs_htree_entry *entp, *start, *end, *middle, *found;
        struct ext2fs_htree_lookup_level *level_info;
        uint32_t hash_major = 0, hash_minor = 0;
        uint32_t levels, cnt;
        uint32_t hash_seed[4];
        uint8_t hash_version;

        if (name == NULL || info == NULL)
                return (-1);

        vp = ITOV(ip);
        fs = ip->i_e2fs->e2fs;
        m_fs = ip->i_e2fs;

        if (ext2_blkatoff(vp, 0, NULL, &bp) != 0)
                return (-1);

        info->h_levels_num = 1;
        info->h_levels[0].h_bp = bp;
        rootp = (struct ext2fs_htree_root *)bp->b_data;
        if (rootp->h_info.h_hash_version != EXT2_HTREE_LEGACY &&
            rootp->h_info.h_hash_version != EXT2_HTREE_HALF_MD4 &&
            rootp->h_info.h_hash_version != EXT2_HTREE_TEA)
                goto error;

        hash_version = rootp->h_info.h_hash_version;
        if (hash_version <= EXT2_HTREE_TEA)
                hash_version += m_fs->e2fs_uhash;
        *hash_ver = hash_version;

        ext2_get_hash_seed(fs, hash_seed);
        ext2_htree_hash(name, namelen, hash_seed,
            hash_version, &hash_major, &hash_minor);
        *hash = hash_major;

        if ((levels = rootp->h_info.h_ind_levels) > 1)
                goto error;

        entp = (struct ext2fs_htree_entry *)(((char *)&rootp->h_info) +
            rootp->h_info.h_info_len);

        if (ext2_htree_get_limit(entp) !=
            ext2_htree_root_limit(ip, rootp->h_info.h_info_len))
                goto error;

        while (1) {
                cnt = ext2_htree_get_count(entp);
                if (cnt == 0 || cnt > ext2_htree_get_limit(entp))
                        goto error;

                start = entp + 1;
                end = entp + cnt - 1;
                while (start <= end) {
                        middle = start + (end - start) / 2;
                        if (ext2_htree_get_hash(middle) > hash_major)
                                end = middle - 1;
                        else
                                start = middle + 1;
                }
                found = start - 1;

                level_info = &(info->h_levels[info->h_levels_num - 1]);
                level_info->h_bp = bp;
                level_info->h_entries = entp;
                level_info->h_entry = found;
                if (levels == 0)
                        return (0);
                levels--;
                if (ext2_blkatoff(vp,
                    ext2_htree_get_block(found) * m_fs->e2fs_bsize,
                    NULL, &bp) != 0)
                        goto error;
                entp = ((struct ext2fs_htree_node *)bp->b_data)->h_entries;
                info->h_levels_num++;
                info->h_levels[info->h_levels_num - 1].h_bp = bp;
        }

error:
        ext2_htree_release(info);
        return (-1);
}

/*
 * Try to lookup a directory entry in HTree index
 */
int
ext2_htree_lookup(struct inode *ip, const char *name, int namelen,
    struct buf **bpp, int *entryoffp, doff_t *offp,
    doff_t *prevoffp, doff_t *endusefulp,
    struct ext2fs_searchslot *ss)
{
        struct vnode *vp;
        struct ext2fs_htree_lookup_info info;
        struct ext2fs_htree_entry *leaf_node;
        struct m_ext2fs *m_fs;
        struct buf *bp;
        uint32_t blk;
        uint32_t dirhash;
        uint32_t bsize;
        uint8_t hash_version;
        int search_next;
        int found = 0;

        m_fs = ip->i_e2fs;
        bsize = m_fs->e2fs_bsize;
        vp = ITOV(ip);

        /* TODO: print error msg because we don't lookup '.' and '..' */

        memset(&info, 0, sizeof(info));
        if (ext2_htree_find_leaf(ip, name, namelen, &dirhash,
            &hash_version, &info))
                return (-1);

        do {
                leaf_node = info.h_levels[info.h_levels_num - 1].h_entry;
                blk = ext2_htree_get_block(leaf_node);
                if (ext2_blkatoff(vp, blk * bsize, NULL, &bp) != 0) {
                        ext2_htree_release(&info);
                        return (-1);
                }

                *offp = blk * bsize;
                *entryoffp = 0;
                *prevoffp = blk * bsize;
                *endusefulp = blk * bsize;

                if (ss->slotstatus == NONE) {
                        ss->slotoffset = -1;
                        ss->slotfreespace = 0;
                }

                if (ext2_search_dirblock(ip, bp->b_data, &found,
                    name, namelen, entryoffp, offp, prevoffp,
                    endusefulp, ss) != 0) {
                        brelse(bp);
                        ext2_htree_release(&info);
                        return (-1);
                }

                if (found) {
                        *bpp = bp;
                        ext2_htree_release(&info);
                        return (0);
                }

                brelse(bp);
                search_next = ext2_htree_check_next(ip, dirhash, name, &info);
        } while (search_next);

        ext2_htree_release(&info);
        return (ENOENT);
}

static int
ext2_htree_append_block(struct vnode *vp, char *data,
    struct componentname *cnp, uint32_t blksize)
{
        struct iovec aiov;
        struct uio auio;
        struct inode *dp = VTOI(vp);
        uint64_t cursize, newsize;
        int error;

        cursize = roundup(dp->i_size, blksize);
        newsize = cursize + blksize;

        auio.uio_offset = cursize;
        auio.uio_resid = blksize;
        aiov.iov_len = blksize;
        aiov.iov_base = data;
        auio.uio_iov = &aiov;
        auio.uio_iovcnt = 1;
        auio.uio_rw = UIO_WRITE;
        auio.uio_segflg = UIO_SYSSPACE;
        auio.uio_td = NULL;
        error = VOP_WRITE(vp, &auio, IO_SYNC, cnp->cn_cred);
        if (!error)
                dp->i_size = newsize;

        return (error);
}

static int
ext2_htree_writebuf(struct inode* ip, struct ext2fs_htree_lookup_info *info)
{
        int i, error;

        for (i = 0; i < info->h_levels_num; i++) {
                struct buf *bp = info->h_levels[i].h_bp;
                ext2_dx_csum_set(ip, (struct ext2fs_direct_2 *)bp->b_data);
                error = bwrite(bp);
                if (error)
                        return (error);
        }

        return (0);
}

static void
ext2_htree_insert_entry_to_level(struct ext2fs_htree_lookup_level *level,
    uint32_t hash, uint32_t blk)
{
        struct ext2fs_htree_entry *target;
        int entries_num;

        target = level->h_entry + 1;
        entries_num = ext2_htree_get_count(level->h_entries);

        memmove(target + 1, target, (char *)(level->h_entries + entries_num) -
            (char *)target);
        ext2_htree_set_block(target, blk);
        ext2_htree_set_hash(target, hash);
        ext2_htree_set_count(level->h_entries, entries_num + 1);
}

/*
 * Insert an index entry to the index node.
 */
static void
ext2_htree_insert_entry(struct ext2fs_htree_lookup_info *info,
    uint32_t hash, uint32_t blk)
{
        struct ext2fs_htree_lookup_level *level;

        level = &info->h_levels[info->h_levels_num - 1];
        ext2_htree_insert_entry_to_level(level, hash, blk);
}

/*
 * Compare two entry sort descriptors by name hash value.
 * This is used together with qsort.
 */
static int
ext2_htree_cmp_sort_entry(const void *e1, const void *e2)
{
        const struct ext2fs_htree_sort_entry *entry1, *entry2;

        entry1 = (const struct ext2fs_htree_sort_entry *)e1;
        entry2 = (const struct ext2fs_htree_sort_entry *)e2;

        if (le32toh(entry1->h_hash) < le32toh(entry2->h_hash))
                return (-1);
        if (le32toh(entry1->h_hash) > le32toh(entry2->h_hash))
                return (1);
        return (0);
}

/*
 * Append an entry to the end of the directory block.
 */
static void
ext2_append_entry(char *block, uint32_t blksize,
    struct ext2fs_direct_2 *last_entry,
    struct ext2fs_direct_2 *new_entry, int csum_size)
{
        uint16_t entry_len;

        entry_len = EXT2_DIR_REC_LEN(last_entry->e2d_namlen);
        last_entry->e2d_reclen = htole16(entry_len);
        last_entry = (struct ext2fs_direct_2 *)((char *)last_entry + entry_len);
        new_entry->e2d_reclen = htole16(block + blksize - (char *)last_entry -
            csum_size);
        memcpy(last_entry, new_entry, EXT2_DIR_REC_LEN(new_entry->e2d_namlen));
}

/*
 * Move half of entries from the old directory block to the new one.
 */
static int
ext2_htree_split_dirblock(struct inode *ip, char *block1, char *block2,
    uint32_t blksize, uint32_t *hash_seed, uint8_t hash_version,
    uint32_t *split_hash, struct ext2fs_direct_2 *entry)
{
        struct m_ext2fs *fs;
        int entry_cnt = 0;
        int size = 0, csum_size = 0;
        int i, k;
        uint32_t offset;
        uint16_t entry_len = 0;
        uint32_t entry_hash;
        struct ext2fs_direct_2 *ep, *last;
        char *dest;
        struct ext2fs_htree_sort_entry *sort_info;

        fs = ip->i_e2fs;
        ep = (struct ext2fs_direct_2 *)block1;
        dest = block2;
        sort_info = (struct ext2fs_htree_sort_entry *)
            ((char *)block2 + blksize);

        if (EXT2_HAS_RO_COMPAT_FEATURE(fs, EXT2F_ROCOMPAT_METADATA_CKSUM))
                csum_size = sizeof(struct ext2fs_direct_tail);

        /*
         * Calculate name hash value for the entry which is to be added.
         */
        ext2_htree_hash(entry->e2d_name, entry->e2d_namlen, hash_seed,
            hash_version, &entry_hash, NULL);

        /*
         * Fill in directory entry sort descriptors.
         */
        while ((char *)ep < block1 + blksize - csum_size) {
                if (le32toh(ep->e2d_ino) && ep->e2d_namlen) {
                        entry_cnt++;
                        sort_info--;
                        sort_info->h_size = ep->e2d_reclen;
                        sort_info->h_offset = htole16((char *)ep - block1);
                        ext2_htree_hash(ep->e2d_name, ep->e2d_namlen,
                            hash_seed, hash_version,
                            &sort_info->h_hash, NULL);
                        sort_info->h_hash = htole32(sort_info->h_hash);
                }
                ep = (struct ext2fs_direct_2 *)
                    ((char *)ep + le16toh(ep->e2d_reclen));
        }

        /*
         * Sort directory entry descriptors by name hash value.
         */
        qsort(sort_info, entry_cnt, sizeof(struct ext2fs_htree_sort_entry),
            ext2_htree_cmp_sort_entry);

        /*
         * Count the number of entries to move to directory block 2.
         */
        for (i = entry_cnt - 1; i >= 0; i--) {
                if (le16toh(sort_info[i].h_size) + size > blksize / 2)
                        break;
                size += le16toh(sort_info[i].h_size);
        }

        *split_hash = le32toh(sort_info[i + 1].h_hash);

        /*
         * Set collision bit.
         */
        if (*split_hash == le32toh(sort_info[i].h_hash))
                *split_hash += 1;

        /*
         * Move half of directory entries from block 1 to block 2.
         */
        for (k = i + 1; k < entry_cnt; k++) {
                ep = (struct ext2fs_direct_2 *)((char *)block1 +
                    le16toh(sort_info[k].h_offset));
                entry_len = EXT2_DIR_REC_LEN(ep->e2d_namlen);
                memcpy(dest, ep, entry_len);
                ((struct ext2fs_direct_2 *)dest)->e2d_reclen =
                    htole16(entry_len);
                /* Mark directory entry as unused. */
                ep->e2d_ino = 0;
                dest += entry_len;
        }
        dest -= entry_len;

        /* Shrink directory entries in block 1. */
        last = (struct ext2fs_direct_2 *)block1;
        entry_len = 0;
        for (offset = 0; offset < blksize - csum_size; ) {
                ep = (struct ext2fs_direct_2 *)(block1 + offset);
                offset += le16toh(ep->e2d_reclen);
                if (le32toh(ep->e2d_ino)) {
                        last = (struct ext2fs_direct_2 *)
                            ((char *)last + entry_len);
                        entry_len = EXT2_DIR_REC_LEN(ep->e2d_namlen);
                        memcpy((void *)last, (void *)ep, entry_len);
                        last->e2d_reclen = htole16(entry_len);
                }
        }

        if (entry_hash >= *split_hash) {
                /* Add entry to block 2. */
                ext2_append_entry(block2, blksize,
                    (struct ext2fs_direct_2 *)dest, entry, csum_size);

                /* Adjust length field of last entry of block 1. */
                last->e2d_reclen = htole16(block1 + blksize - (char *)last -
                    csum_size);
        } else {
                /* Add entry to block 1. */
                ext2_append_entry(block1, blksize, last, entry, csum_size);

                /* Adjust length field of last entry of block 2. */
                ((struct ext2fs_direct_2 *)dest)->e2d_reclen =
                    htole16(block2 + blksize - dest - csum_size);
        }

        if (csum_size) {
                ext2_init_dirent_tail(EXT2_DIRENT_TAIL(block1, blksize));
                ext2_init_dirent_tail(EXT2_DIRENT_TAIL(block2, blksize));
        }

        return (0);
}

/*
 * Create an HTree index for a directory
 */
int
ext2_htree_create_index(struct vnode *vp, struct componentname *cnp,
    struct ext2fs_direct_2 *new_entry)
{
        struct buf *bp = NULL;
        struct inode *dp;
        struct ext2fs *fs;
        struct m_ext2fs *m_fs;
        struct ext2fs_direct_2 *ep, *dotdot;
        struct ext2fs_htree_root *root;
        struct ext2fs_htree_lookup_info info;
        uint32_t blksize, dirlen, split_hash;
        uint32_t hash_seed[4];
        uint8_t hash_version;
        char *buf1 = NULL;
        char *buf2 = NULL;
        int error = 0;

        dp = VTOI(vp);
        fs = dp->i_e2fs->e2fs;
        m_fs = dp->i_e2fs;
        blksize = m_fs->e2fs_bsize;

        buf1 = malloc(blksize, M_TEMP, M_WAITOK | M_ZERO);
        buf2 = malloc(blksize, M_TEMP, M_WAITOK | M_ZERO);

        if ((error = ext2_blkatoff(vp, 0, NULL, &bp)) != 0)
                goto out;

        root = (struct ext2fs_htree_root *)bp->b_data;
        dotdot = (struct ext2fs_direct_2 *)((char *)&(root->h_dotdot));
        ep = (struct ext2fs_direct_2 *)((char *)dotdot +
            le16toh(dotdot->e2d_reclen));
        dirlen = (char *)root + blksize - (char *)ep;
        memcpy(buf1, ep, dirlen);
        ep = (struct ext2fs_direct_2 *)buf1;
        while ((char *)ep < buf1 + dirlen)
                ep = (struct ext2fs_direct_2 *)
                    ((char *)ep + le16toh(ep->e2d_reclen));
        ep->e2d_reclen = htole16(buf1 + blksize - (char *)ep);

        dp->i_flag |= IN_E3INDEX;

        /*
         * Initialize index root.
         */
        dotdot->e2d_reclen = htole16(blksize - EXT2_DIR_REC_LEN(1));
        memset(&root->h_info, 0, sizeof(root->h_info));
        root->h_info.h_hash_version = fs->e3fs_def_hash_version;
        root->h_info.h_info_len = sizeof(root->h_info);
        ext2_htree_set_block(root->h_entries, 1);
        ext2_htree_set_count(root->h_entries, 1);
        ext2_htree_set_limit(root->h_entries,
            ext2_htree_root_limit(dp, sizeof(root->h_info)));

        memset(&info, 0, sizeof(info));
        info.h_levels_num = 1;
        info.h_levels[0].h_entries = root->h_entries;
        info.h_levels[0].h_entry = root->h_entries;

        hash_version = root->h_info.h_hash_version;
        if (hash_version <= EXT2_HTREE_TEA)
                hash_version += m_fs->e2fs_uhash;
        ext2_get_hash_seed(fs, hash_seed);
        ext2_htree_split_dirblock(dp, buf1, buf2, blksize, hash_seed,
            hash_version, &split_hash, new_entry);
        ext2_htree_insert_entry(&info, split_hash, 2);

        /*
         * Write directory block 0.
         */
        ext2_dx_csum_set(dp, (struct ext2fs_direct_2 *)bp->b_data);
        if (DOINGASYNC(vp)) {
                bdwrite(bp);
                error = 0;
        } else {
                error = bwrite(bp);
        }
        dp->i_flag |= IN_CHANGE | IN_UPDATE;
        if (error)
                goto out;

        /*
         * Write directory block 1.
         */
        ext2_dirent_csum_set(dp, (struct ext2fs_direct_2 *)buf1);
        error = ext2_htree_append_block(vp, buf1, cnp, blksize);
        if (error)
                goto out1;

        /*
         * Write directory block 2.
         */
        ext2_dirent_csum_set(dp, (struct ext2fs_direct_2 *)buf2);
        error = ext2_htree_append_block(vp, buf2, cnp, blksize);

        free(buf1, M_TEMP);
        free(buf2, M_TEMP);
        return (error);
out:
        if (bp != NULL)
                brelse(bp);
out1:
        free(buf1, M_TEMP);
        free(buf2, M_TEMP);
        return (error);
}

/*
 * Add an entry to the directory using htree index.
 */
int
ext2_htree_add_entry(struct vnode *dvp, struct ext2fs_direct_2 *entry,
    struct componentname *cnp)
{
        struct ext2fs_htree_entry *entries, *leaf_node;
        struct ext2fs_htree_lookup_info info;
        struct buf *bp = NULL;
        struct ext2fs *fs;
        struct m_ext2fs *m_fs;
        struct inode *ip;
        uint16_t ent_num;
        uint32_t dirhash, split_hash;
        uint32_t blksize, blknum;
        uint64_t cursize, dirsize;
        uint32_t hash_seed[4];
        uint8_t hash_version;
        char *newdirblock = NULL;
        char *newidxblock = NULL;
        struct ext2fs_htree_node *dst_node;
        struct ext2fs_htree_entry *dst_entries;
        struct ext2fs_htree_entry *root_entires;
        struct buf *dst_bp = NULL;
        int error, write_bp = 0, write_dst_bp = 0, write_info = 0;

        ip = VTOI(dvp);
        m_fs = ip->i_e2fs;
        fs = m_fs->e2fs;
        blksize = m_fs->e2fs_bsize;

        if (ip->i_count != 0)
                return ext2_add_entry(dvp, entry);

        /* Target directory block is full, split it */
        memset(&info, 0, sizeof(info));
        error = ext2_htree_find_leaf(ip, entry->e2d_name, entry->e2d_namlen,
            &dirhash, &hash_version, &info);
        if (error)
                return (error);

        entries = info.h_levels[info.h_levels_num - 1].h_entries;
        ent_num = ext2_htree_get_count(entries);
        if (ent_num == ext2_htree_get_limit(entries)) {
                /* Split the index node. */
                root_entires = info.h_levels[0].h_entries;
                newidxblock = malloc(blksize, M_TEMP, M_WAITOK | M_ZERO);
                dst_node = (struct ext2fs_htree_node *)newidxblock;
                memset(&dst_node->h_fake_dirent, 0,
                    sizeof(dst_node->h_fake_dirent));
                dst_node->h_fake_dirent.e2d_reclen = htole16(blksize);

                cursize = roundup(ip->i_size, blksize);
                dirsize = cursize + blksize;
                blknum = dirsize / blksize - 1;
                ext2_dx_csum_set(ip, (struct ext2fs_direct_2 *)newidxblock);
                error = ext2_htree_append_block(dvp, newidxblock,
                    cnp, blksize);
                if (error)
                        goto finish;
                error = ext2_blkatoff(dvp, cursize, NULL, &dst_bp);
                if (error)
                        goto finish;
                dst_node = (struct ext2fs_htree_node *)dst_bp->b_data;
                dst_entries = dst_node->h_entries;

                if (info.h_levels_num == 2) {
                        uint16_t src_ent_num, dst_ent_num;

                        if (ext2_htree_get_count(root_entires) ==
                            ext2_htree_get_limit(root_entires)) {
                                SDT_PROBE2(ext2fs, , trace, htree, 1,
                                    "directory index is full");
                                error = EIO;
                                goto finish;
                        }

                        src_ent_num = ent_num / 2;
                        dst_ent_num = ent_num - src_ent_num;
                        split_hash = ext2_htree_get_hash(entries + src_ent_num);

                        /* Move half of index entries to the new index node */
                        memcpy(dst_entries, entries + src_ent_num,
                            dst_ent_num * sizeof(struct ext2fs_htree_entry));
                        ext2_htree_set_count(entries, src_ent_num);
                        ext2_htree_set_count(dst_entries, dst_ent_num);
                        ext2_htree_set_limit(dst_entries,
                            ext2_htree_node_limit(ip));

                        if (info.h_levels[1].h_entry >= entries + src_ent_num) {
                                struct buf *tmp = info.h_levels[1].h_bp;

                                info.h_levels[1].h_bp = dst_bp;
                                dst_bp = tmp;

                                info.h_levels[1].h_entry =
                                    info.h_levels[1].h_entry -
                                    (entries + src_ent_num) +
                                    dst_entries;
                                info.h_levels[1].h_entries = dst_entries;
                        }
                        ext2_htree_insert_entry_to_level(&info.h_levels[0],
                            split_hash, blknum);

                        /* Write new index node to disk */
                        ext2_dx_csum_set(ip,
                            (struct ext2fs_direct_2 *)dst_bp->b_data);
                        error = bwrite(dst_bp);
                        ip->i_flag |= IN_CHANGE | IN_UPDATE;
                        if (error)
                                goto finish;
                        write_dst_bp = 1;
                } else {
                        /* Create second level for htree index */
                        struct ext2fs_htree_root *idx_root;

                        memcpy(dst_entries, entries,
                            ent_num * sizeof(struct ext2fs_htree_entry));
                        ext2_htree_set_limit(dst_entries,
                            ext2_htree_node_limit(ip));

                        idx_root = (struct ext2fs_htree_root *)
                            info.h_levels[0].h_bp->b_data;
                        idx_root->h_info.h_ind_levels = 1;

                        ext2_htree_set_count(entries, 1);
                        ext2_htree_set_block(entries, blknum);

                        info.h_levels_num = 2;
                        info.h_levels[1].h_entries = dst_entries;
                        info.h_levels[1].h_entry = info.h_levels[0].h_entry -
                            info.h_levels[0].h_entries + dst_entries;
                        info.h_levels[1].h_bp = dst_bp;
                        dst_bp = NULL;
                }
        }

        leaf_node = info.h_levels[info.h_levels_num - 1].h_entry;
        blknum = ext2_htree_get_block(leaf_node);
        error = ext2_blkatoff(dvp, blknum * blksize, NULL, &bp);
        if (error)
                goto finish;

        /* Split target directory block */
        newdirblock = malloc(blksize, M_TEMP, M_WAITOK | M_ZERO);
        ext2_get_hash_seed(fs, hash_seed);
        ext2_htree_split_dirblock(ip, (char *)bp->b_data, newdirblock, blksize,
            hash_seed, hash_version, &split_hash, entry);
        cursize = roundup(ip->i_size, blksize);
        dirsize = cursize + blksize;
        blknum = dirsize / blksize - 1;

        /* Add index entry for the new directory block */
        ext2_htree_insert_entry(&info, split_hash, blknum);

        /* Write the new directory block to the end of the directory */
        ext2_dirent_csum_set(ip, (struct ext2fs_direct_2 *)newdirblock);
        error = ext2_htree_append_block(dvp, newdirblock, cnp, blksize);
        if (error)
                goto finish;

        /* Write the target directory block */
        ext2_dirent_csum_set(ip, (struct ext2fs_direct_2 *)bp->b_data);
        error = bwrite(bp);
        ip->i_flag |= IN_CHANGE | IN_UPDATE;
        if (error)
                goto finish;
        write_bp = 1;

        /* Write the index block */
        error = ext2_htree_writebuf(ip, &info);
        if (!error)
                write_info = 1;

finish:
        if (dst_bp != NULL && !write_dst_bp)
                brelse(dst_bp);
        if (bp != NULL && !write_bp)
                brelse(bp);
        if (newdirblock != NULL)
                free(newdirblock, M_TEMP);
        if (newidxblock != NULL)
                free(newidxblock, M_TEMP);
        if (!write_info)
                ext2_htree_release(&info);
        return (error);
}