/*      $NetBSD: ext2fs_htree.c,v 1.11 2023/08/26 05:22:50 riastradh Exp $      */

/*-
 * 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.
 *
 * $FreeBSD: head/sys/fs/ext2fs/ext2fs_htree.c 294653 2016-01-24 02:41:49Z pfg $
 */
#include <sys/cdefs.h>
__KERNEL_RCSID(0, "$NetBSD: ext2fs_htree.c,v 1.11 2023/08/26 05:22:50 riastradh Exp $");

#include <sys/param.h>
#include <sys/systm.h>
#include <sys/resourcevar.h>
#include <sys/kernel.h>
#include <sys/file.h>
#include <sys/stat.h>
#include <sys/buf.h>
#include <sys/proc.h>
#include <sys/mount.h>
#include <sys/namei.h>
#include <sys/vnode.h>
#include <sys/lockf.h>
#include <sys/pool.h>
#include <sys/signalvar.h>
#include <sys/kauth.h>
#include <sys/malloc.h>
#include <ufs/ufs/dir.h>

#include <ufs/ufs/inode.h>
#include <ufs/ufs/ufsmount.h>
#include <ufs/ext2fs/ext2fs.h>

#include <ufs/ext2fs/ext2fs_extern.h>
#include <ufs/ext2fs/ext2fs_dinode.h>
#include <ufs/ext2fs/ext2fs_dir.h>
#include <ufs/ext2fs/ext2fs_htree.h>
#include <ufs/ext2fs/ext2fs_hash.h>

static int ext2fs_htree_find_leaf(struct inode *, const char *, int ,
    uint32_t *, uint8_t *, struct ext2fs_htree_lookup_info *);

int
ext2fs_htree_has_idx(struct inode *ip)
{
        return EXT2F_HAS_COMPAT_FEATURE(ip->i_e2fs, EXT2F_COMPAT_DIRHASHINDEX)
            && (ip->i_din.e2fs_din->e2di_flags & EXT2_INDEX);
}

static off_t
ext2fs_htree_get_block(struct ext2fs_htree_entry *ep)
{
        return ep->h_blk & 0x00FFFFFF;
}

static void
ext2fs_htree_release(struct ext2fs_htree_lookup_info *info)
{
        for (u_int i = 0; i < info->h_levels_num; i++) {
                struct buf *bp = info->h_levels[i].h_bp;
                if (bp != NULL)
                        brelse(bp, 0);
        }
}

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

static uint32_t
ext2fs_htree_root_limit(struct inode *ip, int len)
{
        uint32_t space = ip->i_e2fs->e2fs_bsize - EXT2_DIR_REC_LEN(1) -
            EXT2_DIR_REC_LEN(2) - len;
        return space / sizeof(struct ext2fs_htree_entry);
}

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

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


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

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

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

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

static uint32_t
ext2fs_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);

        return space / sizeof(struct ext2fs_htree_entry);
}

static int
ext2fs_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_vmspace = vmspace_kernel();
        error = VOP_WRITE(vp, &auio, IO_SYNC, cnp->cn_cred);
        if (!error)
                dp->i_size = newsize;

        return error;
}

static int
ext2fs_htree_writebuf(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;
                error = bwrite(bp);
                if (error)
                        return error;
        }

        return 0;
}

static void
ext2fs_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 = ext2fs_htree_get_count(level->h_entries);

        memmove(target + 1, target, (char *)(level->h_entries + entries_num) -
            (char *)target);
        ext2fs_htree_set_block(target, blk);
        ext2fs_htree_set_hash(target, hash);
        ext2fs_htree_set_count(level->h_entries, entries_num + 1);
}

/*
 * Insert an index entry to the index node.
 */
static void
ext2fs_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];
        ext2fs_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
ext2fs_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 (entry1->h_hash < entry2->h_hash)
                return -1;
        if (entry1->h_hash > entry2->h_hash)
                return 1;
        return 0;
}

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

        entry_len = EXT2_DIR_REC_LEN(last_entry->e2d_namlen);
        last_entry->e2d_reclen = entry_len;
        last_entry = (struct ext2fs_direct *)((char *)last_entry + entry_len);
        new_entry->e2d_reclen = block + blksize - (char *)last_entry;
        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
ext2fs_htree_split_dirblock(char *block1, char *block2, uint32_t blksize,
    uint32_t *hash_seed, uint8_t hash_version,
    uint32_t *split_hash, struct ext2fs_direct *entry)
{
        int entry_cnt = 0;
        int size = 0;
        int i, k;
        uint32_t offset;
        uint16_t entry_len = 0;
        uint32_t entry_hash;
        struct ext2fs_direct *ep, *last;
        char *dest;
        struct ext2fs_htree_sort_entry *sort_info, dummy;

        ep = (struct ext2fs_direct *)block1;
        dest = block2;
        sort_info = (struct ext2fs_htree_sort_entry *)
            ((char *)block2 + blksize);

        /*
         * Calculate name hash value for the entry which is to be added.
         */
        ext2fs_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) {
                if (ep->e2d_ino && ep->e2d_namlen) {
                        entry_cnt++;
                        sort_info--;
                        sort_info->h_size = ep->e2d_reclen;
                        sort_info->h_offset = (char *)ep - block1;
                        ext2fs_htree_hash(ep->e2d_name, ep->e2d_namlen,
                            hash_seed, hash_version,
                            &sort_info->h_hash, NULL);
                }
                ep = (struct ext2fs_direct *)
                    ((char *)ep + ep->e2d_reclen);
        }

        /*
         * Sort directory entry descriptors by name hash value.
         */
        kheapsort(sort_info, entry_cnt, sizeof(struct ext2fs_htree_sort_entry),
            ext2fs_htree_cmp_sort_entry, &dummy);

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

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

        /*
         * Set collision bit.
         */
        if (*split_hash == 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 *)((char *)block1 +
                    sort_info[k].h_offset);
                entry_len = EXT2_DIR_REC_LEN(ep->e2d_namlen);
                memcpy(dest, ep, entry_len);
                ((struct ext2fs_direct *)dest)->e2d_reclen = 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 *)block1;
        entry_len = 0;
        for (offset = 0; offset < blksize;) {
                ep = (struct ext2fs_direct *)(block1 + offset);
                offset += ep->e2d_reclen;
                if (ep->e2d_ino) {
                        last = (struct ext2fs_direct *)
                           ((char *)last + entry_len);
                        entry_len = EXT2_DIR_REC_LEN(ep->e2d_namlen);
                        memcpy((void *)last, (void *)ep, entry_len);
                        last->e2d_reclen = entry_len;
                }
        }

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

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

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

        return 0;
}

/*
 * Create an HTree index for a directory having entries which are no more
 * accommodable in a single dir-block.
 */
int
ext2fs_htree_create_index(struct vnode *vp, struct componentname *cnp,
    struct ext2fs_direct *new_entry)
{
        struct buf *bp = NULL;
        struct inode *dp;
        struct ext2fs *fs;
        struct m_ext2fs *m_fs;
        struct ext2fs_direct *ep, *dotdot;
        struct ext2fs_htree_root *root;
        struct ext2fs_htree_lookup_info info;
        uint32_t blksize, dirlen, split_hash;
        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 = ext2fs_blkatoff(vp, 0, NULL, &bp)) != 0)
                goto out;

        root = (struct ext2fs_htree_root *)bp->b_data;
        dotdot = (struct ext2fs_direct *)((char *)&(root->h_dotdot));
        ep = (struct ext2fs_direct *)((char *)dotdot + dotdot->e2d_reclen);
        dirlen = (char *)root + blksize - (char *)ep;
        memcpy(buf1, ep, dirlen);
        ep = (struct ext2fs_direct *)buf1;
        while ((char *)ep < buf1 + dirlen)
                ep = (struct ext2fs_direct *)((char *)ep + ep->e2d_reclen);
        ep->e2d_reclen = buf1 + blksize - (char *)ep;
        /* XXX It should be made dp->i_flag |= IN_E3INDEX; */
        dp->i_din.e2fs_din->e2di_flags |= EXT2_INDEX;

        /*
         * Initialize index root.
         */
        dotdot->e2d_reclen = 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);
        ext2fs_htree_set_block(root->h_entries, 1);
        ext2fs_htree_set_count(root->h_entries, 1);
        ext2fs_htree_set_limit(root->h_entries,
            ext2fs_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;
        ext2fs_htree_split_dirblock(buf1, buf2, blksize, fs->e3fs_hash_seed,
            hash_version, &split_hash, new_entry);
        ext2fs_htree_insert_entry(&info, split_hash, 2);

        /*
         * Write directory block 0.
         */
        if ( (vp)->v_mount->mnt_iflag & IO_SYNC)
                (void)bwrite(bp);
        else
                bdwrite(bp);

        dp->i_flag |= IN_CHANGE | IN_UPDATE;

        /*
         * Write directory block 1.
         */
        error = ext2fs_htree_append_block(vp, buf1, cnp, blksize);
        if (error)
                goto out1;

        /*
         * Write directory block 2.
         */
        error = ext2fs_htree_append_block(vp, buf2, cnp, blksize);
        goto out1;
out:
        if (bp != NULL)
                brelse(bp, 0);
out1:
        free(buf1, M_TEMP);
        free(buf2, M_TEMP);
        return error;
}

/*
 * Add an entry to the directory using htree index.
 */
int
ext2fs_htree_add_entry(struct vnode *dvp, struct ext2fs_direct *entry,
    struct componentname *cnp, size_t newentrysize)
{
        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;
        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_entries;
        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_crap.ulr_count != 0)
                return ext2fs_add_entry(dvp, entry, &(ip->i_crap), newentrysize);

        /* Target directory block is full, split it */
        memset(&info, 0, sizeof(info));
        error = ext2fs_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 = ext2fs_htree_get_count(entries);
        if (ent_num == ext2fs_htree_get_limit(entries)) {
                /* Split the index node. */
                root_entries = info.h_levels[0].h_entries;
                newidxblock = malloc(blksize, M_TEMP, M_WAITOK | M_ZERO);
                dst_node = (struct ext2fs_htree_node *)newidxblock;
                dst_entries = dst_node->h_entries;
                memset(&dst_node->h_fake_dirent, 0,
                    sizeof(dst_node->h_fake_dirent));
                dst_node->h_fake_dirent.e2d_reclen = blksize;

                cursize = roundup(ip->i_size, blksize);
                dirsize = cursize + blksize;
                blknum = dirsize / blksize - 1;

                error = ext2fs_htree_append_block(dvp, newidxblock,
                    cnp, blksize);
                if (error)
                        goto finish;
                error = ext2fs_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 (ext2fs_htree_get_count(root_entries) ==
                            ext2fs_htree_get_limit(root_entries)) {
                                /* Directory index is full */
                                error = EIO;
                                goto finish;
                        }

                        src_ent_num = ent_num / 2;
                        dst_ent_num = ent_num - src_ent_num;
                        split_hash = ext2fs_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));
                        ext2fs_htree_set_count(entries, src_ent_num);
                        ext2fs_htree_set_count(dst_entries, dst_ent_num);
                        ext2fs_htree_set_limit(dst_entries,
                            ext2fs_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;
                        }
                        ext2fs_htree_insert_entry_to_level(&info.h_levels[0],
                            split_hash, blknum);

                        /* Write new index node to disk */
                        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));
                        ext2fs_htree_set_limit(dst_entries,
                            ext2fs_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;

                        ext2fs_htree_set_count(entries, 1);
                        ext2fs_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 = ext2fs_htree_get_block(leaf_node);
        error = ext2fs_blkatoff(dvp, blknum * blksize, NULL, &bp);
        if (error)
                goto finish;

        /* Split target directory block */
        newdirblock = malloc(blksize, M_TEMP, M_WAITOK | M_ZERO);
        ext2fs_htree_split_dirblock((char *)bp->b_data, newdirblock, blksize,
            fs->e3fs_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 */
        ext2fs_htree_insert_entry(&info, split_hash, blknum);

        /* Write the new directory block to the end of the directory */
        error = ext2fs_htree_append_block(dvp, newdirblock, cnp, blksize);

        if (error)
                goto finish;

        /* Write the target directory block */
        error = bwrite(bp);
        ip->i_flag |= IN_CHANGE | IN_UPDATE;

        if (error)
                goto finish;
        write_bp = 1;

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

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

static int
ext2fs_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;

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

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

        while (levels > 0) {
                levels--;
                if (ext2fs_blkatoff(vp, ext2fs_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, 0);
                level->h_bp = bp;
                level->h_entry = level->h_entries =
                    ((struct ext2fs_htree_node *)bp->b_data)->h_entries;
        }

        return 1;
}

static int
ext2fs_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;/* F, G, and H are MD4 functions */
        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;
        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 (ext2fs_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;

        ext2fs_htree_hash(name, namelen, fs->e3fs_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 (ext2fs_htree_get_limit(entp) !=
            ext2fs_htree_root_limit(ip, rootp->h_info.h_info_len))
                goto error;

        for (;;) {
                cnt = ext2fs_htree_get_count(entp);
                if (cnt == 0 || cnt > ext2fs_htree_get_limit(entp))
                        goto error;

                start = entp + 1;
                end = entp + cnt - 1;
                while (start <= end) {
                        middle = start + (end - start) / 2;
                        if (ext2fs_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 (ext2fs_blkatoff(vp,
                    ext2fs_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:
        ext2fs_htree_release(info);
        return -1;
}

/*
 * Try to lookup a directory entry in HTree index
 */
int
ext2fs_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;

        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 (ext2fs_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 = ext2fs_htree_get_block(leaf_node);
                if (ext2fs_blkatoff(vp, blk * bsize, NULL, &bp) != 0) {
                        ext2fs_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;
                }

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

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

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

        ext2fs_htree_release(&info);
        return ENOENT;
}