/**
 * index.c - NTFS index handling.  Originated from the Linux-NTFS project.
 *
 * Copyright (c) 2004-2005 Anton Altaparmakov
 * Copyright (c) 2004-2005 Richard Russon
 * Copyright (c) 2005-2006 Yura Pakhuchiy
 * Copyright (c) 2005-2008 Szabolcs Szakacsits
 * Copyright (c) 2007-2021 Jean-Pierre Andre
 *
 * This program/include file is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as published
 * by the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program/include file is distributed in the hope that it will be
 * useful, but WITHOUT ANY WARRANTY; without even the implied warranty
 * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program (in the main directory of the NTFS-3G
 * distribution in the file COPYING); if not, write to the Free Software
 * Foundation,Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#ifdef HAVE_STDLIB_H
#include <stdlib.h>
#endif
#ifdef HAVE_STRING_H
#include <string.h>
#endif
#ifdef HAVE_ERRNO_H
#include <errno.h>
#endif

#include "attrib.h"
#include "debug.h"
#include "index.h"
#include "collate.h"
#include "mst.h"
#include "dir.h"
#include "logging.h"
#include "bitmap.h"
#include "reparse.h"
#include "misc.h"

/**
 * ntfs_index_entry_mark_dirty - mark an index entry dirty
 * @ictx:       ntfs index context describing the index entry
 *
 * Mark the index entry described by the index entry context @ictx dirty.
 *
 * If the index entry is in the index root attribute, simply mark the inode
 * containing the index root attribute dirty.  This ensures the mftrecord, and
 * hence the index root attribute, will be written out to disk later.
 *
 * If the index entry is in an index block belonging to the index allocation
 * attribute, set ib_dirty to TRUE, thus index block will be updated during
 * ntfs_index_ctx_put.
 */
void ntfs_index_entry_mark_dirty(ntfs_index_context *ictx)
{
        if (ictx->is_in_root)
                ntfs_inode_mark_dirty(ictx->actx->ntfs_ino);
        else
                ictx->ib_dirty = TRUE;
}

static s64 ntfs_ib_vcn_to_pos(ntfs_index_context *icx, VCN vcn)
{
        return vcn << icx->vcn_size_bits;
}

static VCN ntfs_ib_pos_to_vcn(ntfs_index_context *icx, s64 pos)
{
        return pos >> icx->vcn_size_bits;
}

static int ntfs_ib_write(ntfs_index_context *icx, INDEX_BLOCK *ib)
{
        s64 ret, vcn = sle64_to_cpu(ib->index_block_vcn);
        
        ntfs_log_trace("vcn: %lld\n", (long long)vcn);
        
        ret = ntfs_attr_mst_pwrite(icx->ia_na, ntfs_ib_vcn_to_pos(icx, vcn),
                                   1, icx->block_size, ib);
        if (ret != 1) {
                ntfs_log_perror("Failed to write index block %lld, inode %llu",
                        (long long)vcn, (unsigned long long)icx->ni->mft_no);
                return STATUS_ERROR;
        }
        
        return STATUS_OK;
}

static int ntfs_icx_ib_write(ntfs_index_context *icx)
{
                if (ntfs_ib_write(icx, icx->ib))
                        return STATUS_ERROR;
                
                icx->ib_dirty = FALSE;
                
                return STATUS_OK;
}

/**
 * ntfs_index_ctx_get - allocate and initialize a new index context
 * @ni:         ntfs inode with which to initialize the context
 * @name:       name of the which context describes
 * @name_len:   length of the index name
 *
 * Allocate a new index context, initialize it with @ni and return it.
 * Return NULL if allocation failed.
 */
ntfs_index_context *ntfs_index_ctx_get(ntfs_inode *ni,
                                       ntfschar *name, u32 name_len)
{
        ntfs_index_context *icx;

        ntfs_log_trace("Entering\n");
        
        if (!ni) {
                errno = EINVAL;
                return NULL;
        }
        if (ni->nr_extents == -1)
                ni = ni->base_ni;
        icx = ntfs_calloc(sizeof(ntfs_index_context));
        if (icx)
                *icx = (ntfs_index_context) {
                        .ni = ni,
                        .name = name,
                        .name_len = name_len,
                };
        return icx;
}

static void ntfs_index_ctx_free(ntfs_index_context *icx)
{
        ntfs_log_trace("Entering\n");
        
        if (!icx->bad_index && !icx->entry)
                return;

        if (icx->actx)
                ntfs_attr_put_search_ctx(icx->actx);

        if (!icx->is_in_root) {
                if (icx->ib_dirty) {
                        /* FIXME: Error handling!!! */
                        ntfs_ib_write(icx, icx->ib);
                }
                free(icx->ib);
        }
        
        ntfs_attr_close(icx->ia_na);
}

/**
 * ntfs_index_ctx_put - release an index context
 * @icx:        index context to free
 *
 * Release the index context @icx, releasing all associated resources.
 */
void ntfs_index_ctx_put(ntfs_index_context *icx)
{
        ntfs_index_ctx_free(icx);
        free(icx);
}

/**
 * ntfs_index_ctx_reinit - reinitialize an index context
 * @icx:        index context to reinitialize
 *
 * Reinitialize the index context @icx so it can be used for ntfs_index_lookup.
 */
void ntfs_index_ctx_reinit(ntfs_index_context *icx)
{
        ntfs_log_trace("Entering\n");
        
        ntfs_index_ctx_free(icx);
        
        *icx = (ntfs_index_context) {
                .ni = icx->ni,
                .name = icx->name,
                .name_len = icx->name_len,
        };
}

static leVCN *ntfs_ie_get_vcn_addr(INDEX_ENTRY *ie)
{
        return (leVCN *)((u8 *)ie + le16_to_cpu(ie->length) - sizeof(leVCN));
}

/**
 *  Get the subnode vcn to which the index entry refers.
 */
VCN ntfs_ie_get_vcn(INDEX_ENTRY *ie)
{
        return sle64_to_cpup(ntfs_ie_get_vcn_addr(ie));
}

static INDEX_ENTRY *ntfs_ie_get_first(INDEX_HEADER *ih)
{
        return (INDEX_ENTRY *)((u8 *)ih + le32_to_cpu(ih->entries_offset));
}

static INDEX_ENTRY *ntfs_ie_get_next(INDEX_ENTRY *ie)
{
        return (INDEX_ENTRY *)((char *)ie + le16_to_cpu(ie->length));
}

static u8 *ntfs_ie_get_end(INDEX_HEADER *ih)
{
        /* FIXME: check if it isn't overflowing the index block size */
        return (u8 *)ih + le32_to_cpu(ih->index_length);
}

static int ntfs_ie_end(INDEX_ENTRY *ie)
{
        return ie->ie_flags & INDEX_ENTRY_END || !ie->length;
}

/** 
 *  Find the last entry in the index block
 */
static INDEX_ENTRY *ntfs_ie_get_last(INDEX_ENTRY *ie, char *ies_end)
{
        ntfs_log_trace("Entering\n");
        
        while ((char *)ie < ies_end && !ntfs_ie_end(ie))
                ie = ntfs_ie_get_next(ie);
        
        return ie;
}

static INDEX_ENTRY *ntfs_ie_get_by_pos(INDEX_HEADER *ih, int pos)
{
        INDEX_ENTRY *ie;
        
        ntfs_log_trace("pos: %d\n", pos);
        
        ie = ntfs_ie_get_first(ih);
        
        while (pos-- > 0)
                ie = ntfs_ie_get_next(ie);
        
        return ie;
}

static INDEX_ENTRY *ntfs_ie_prev(INDEX_HEADER *ih, INDEX_ENTRY *ie)
{
        INDEX_ENTRY *ie_prev = NULL;
        INDEX_ENTRY *tmp;
        
        ntfs_log_trace("Entering\n");
        
        tmp = ntfs_ie_get_first(ih);
        
        while (tmp != ie) {
                ie_prev = tmp;
                tmp = ntfs_ie_get_next(tmp);
        }
        
        return ie_prev;
}

char *ntfs_ie_filename_get(INDEX_ENTRY *ie)
{
        FILE_NAME_ATTR *fn;

        fn = (FILE_NAME_ATTR *)&ie->key;
        return ntfs_attr_name_get(fn->file_name, fn->file_name_length);
}

void ntfs_ie_filename_dump(INDEX_ENTRY *ie)
{
        char *s;

        s = ntfs_ie_filename_get(ie);
        ntfs_log_debug("'%s' ", s);
        ntfs_attr_name_free(&s);
}

void ntfs_ih_filename_dump(INDEX_HEADER *ih)
{
        INDEX_ENTRY *ie;
        
        ntfs_log_trace("Entering\n");
        
        ie = ntfs_ie_get_first(ih);
        while (!ntfs_ie_end(ie)) {
                ntfs_ie_filename_dump(ie);
                ie = ntfs_ie_get_next(ie);
        }
}

static int ntfs_ih_numof_entries(INDEX_HEADER *ih)
{
        int n;
        INDEX_ENTRY *ie;
        u8 *end;
        
        ntfs_log_trace("Entering\n");
        
        end = ntfs_ie_get_end(ih);
        ie = ntfs_ie_get_first(ih);
        for (n = 0; !ntfs_ie_end(ie) && (u8 *)ie < end; n++)
                ie = ntfs_ie_get_next(ie);
        return n;
}

static int ntfs_ih_one_entry(INDEX_HEADER *ih)
{
        return (ntfs_ih_numof_entries(ih) == 1);
}

static int ntfs_ih_zero_entry(INDEX_HEADER *ih)
{
        return (ntfs_ih_numof_entries(ih) == 0);
}

static void ntfs_ie_delete(INDEX_HEADER *ih, INDEX_ENTRY *ie)
{
        u32 new_size;
        
        ntfs_log_trace("Entering\n");
        
        new_size = le32_to_cpu(ih->index_length) - le16_to_cpu(ie->length);
        ih->index_length = cpu_to_le32(new_size);
        memmove(ie, (u8 *)ie + le16_to_cpu(ie->length),
                new_size - ((u8 *)ie - (u8 *)ih));
}

static void ntfs_ie_set_vcn(INDEX_ENTRY *ie, VCN vcn)
{
        *ntfs_ie_get_vcn_addr(ie) = cpu_to_sle64(vcn);
}

/**
 *  Insert @ie index entry at @pos entry. Used @ih values should be ok already.
 */
static void ntfs_ie_insert(INDEX_HEADER *ih, INDEX_ENTRY *ie, INDEX_ENTRY *pos)
{
        int ie_size = le16_to_cpu(ie->length);
        
        ntfs_log_trace("Entering\n");
        
        ih->index_length = cpu_to_le32(le32_to_cpu(ih->index_length) + ie_size);
        memmove((u8 *)pos + ie_size, pos,
                le32_to_cpu(ih->index_length) - ((u8 *)pos - (u8 *)ih) - ie_size);
        memcpy(pos, ie, ie_size);
}

static INDEX_ENTRY *ntfs_ie_dup(INDEX_ENTRY *ie)
{
        INDEX_ENTRY *dup;
        
        ntfs_log_trace("Entering\n");
        
        dup = ntfs_malloc(le16_to_cpu(ie->length));
        if (dup)
                memcpy(dup, ie, le16_to_cpu(ie->length));
        
        return dup;
}

static INDEX_ENTRY *ntfs_ie_dup_novcn(INDEX_ENTRY *ie)
{
        INDEX_ENTRY *dup;
        int size = le16_to_cpu(ie->length);
        
        ntfs_log_trace("Entering\n");
        
        if (ie->ie_flags & INDEX_ENTRY_NODE)
                size -= sizeof(VCN);
        
        dup = ntfs_malloc(size);
        if (dup) {
                memcpy(dup, ie, size);
                dup->ie_flags &= ~INDEX_ENTRY_NODE;
                dup->length = cpu_to_le16(size);
        }
        return dup;
}

static INDEX_ROOT *ntfs_ir_lookup(ntfs_inode *ni, ntfschar *name,
                                  u32 name_len, ntfs_attr_search_ctx **ctx)
{
        ATTR_RECORD *a;
        INDEX_ROOT *ir = NULL;

        ntfs_log_trace("Entering\n");
        
        *ctx = ntfs_attr_get_search_ctx(ni, NULL);
        if (!*ctx)
                return NULL;
        
        if (ntfs_attr_lookup(AT_INDEX_ROOT, name, name_len, CASE_SENSITIVE, 
                             0, NULL, 0, *ctx)) {
                ntfs_log_perror("Failed to lookup $INDEX_ROOT");
                goto err_out;
        }
        
        a = (*ctx)->attr;
        if (a->non_resident) {
                errno = EINVAL;
                ntfs_log_perror("Non-resident $INDEX_ROOT detected");
                goto err_out;
        }
        
        ir = (INDEX_ROOT *)((char *)a + le16_to_cpu(a->value_offset));
err_out:
        if (!ir) {
                ntfs_attr_put_search_ctx(*ctx);
                *ctx = NULL;
        }
        return ir;
}

static INDEX_ROOT *ntfs_ir_lookup2(ntfs_inode *ni, ntfschar *name, u32 len)
{
        ntfs_attr_search_ctx *ctx;
        INDEX_ROOT *ir;

        ir = ntfs_ir_lookup(ni, name, len, &ctx);
        if (ir)
                ntfs_attr_put_search_ctx(ctx);
        return ir;
}

/*
 *              Check the consistency of an index block
 *
 *      Make sure the index block does not overflow from the index record.
 *      The size of block is assumed to have been checked to be what is
 *      defined in the index root.
 *
 *      Returns 0 if no error was found
 *              -1 otherwise (with errno unchanged)
 *
 *      |<--->|  offsetof(INDEX_BLOCK, index)
 *      |     |<--->|  sizeof(INDEX_HEADER)
 *      |     |     |
 *      |     |     | seq          index entries         unused
 *      |=====|=====|=====|===========================|==============|
 *      |     |           |                           |              |
 *      |     |<--------->| entries_offset            |              |
 *      |     |<---------------- index_length ------->|              |
 *      |     |<--------------------- allocated_size --------------->|
 *      |<--------------------------- block_size ------------------->|
 *
 *      size(INDEX_HEADER) <= ent_offset < ind_length <= alloc_size < bk_size
 */

int ntfs_index_block_inconsistent(const INDEX_BLOCK *ib, u32 block_size,
                        u64 inum, VCN vcn)
{
        u32 ib_size = (unsigned)le32_to_cpu(ib->index.allocated_size)
                        + offsetof(INDEX_BLOCK, index);

        if (!ntfs_is_indx_record(ib->magic)) {
                ntfs_log_error("Corrupt index block signature: vcn %lld inode "
                               "%llu\n", (long long)vcn,
                               (unsigned long long)inum);
                return -1;
        }
        
        if (sle64_to_cpu(ib->index_block_vcn) != vcn) {
                ntfs_log_error("Corrupt index block: VCN (%lld) is different "
                               "from expected VCN (%lld) in inode %llu\n",
                               (long long)sle64_to_cpu(ib->index_block_vcn),
                               (long long)vcn,
                               (unsigned long long)inum);
                return -1;
        }
        
        if (ib_size != block_size) {
                ntfs_log_error("Corrupt index block : VCN (%lld) of inode %llu "
                               "has a size (%u) differing from the index "
                               "specified size (%u)\n", (long long)vcn, 
                               (unsigned long long)inum, ib_size,
                               (unsigned int)block_size);
                return -1;
        }
        if (le32_to_cpu(ib->index.entries_offset) < sizeof(INDEX_HEADER)) {
                ntfs_log_error("Invalid index entry offset in inode %lld\n",
                                (unsigned long long)inum);
                return -1;
        }
        if (le32_to_cpu(ib->index.index_length)
                        <= le32_to_cpu(ib->index.entries_offset)) {
                ntfs_log_error("No space for index entries in inode %lld\n",
                                (unsigned long long)inum);
                return -1;
        }
        if (le32_to_cpu(ib->index.allocated_size)
                        < le32_to_cpu(ib->index.index_length)) {
                ntfs_log_error("Index entries overflow in inode %lld\n",
                                (unsigned long long)inum);
                return -1;
        }

        return (0);
}


/*
 *              Check the consistency of an index entry
 *
 *      Make sure data and key do not overflow from entry.
 *      As a side effect, an entry with zero length is rejected.
 *      This entry must be a full one (no INDEX_ENTRY_END flag), and its
 *      length must have been checked beforehand to not overflow from the
 *      index record.
 *
 *      Returns 0 if no error was found
 *              -1 otherwise (with errno unchanged)
 */

int ntfs_index_entry_inconsistent(const INDEX_ENTRY *ie,
                        COLLATION_RULES collation_rule, u64 inum)
{
        int ret;

        ret = 0;
        if (ie->key_length
                && ((le16_to_cpu(ie->key_length) + offsetof(INDEX_ENTRY, key))
                            > le16_to_cpu(ie->length))) {
                ntfs_log_error("Overflow from index entry in inode %lld\n",
                                (long long)inum);
                ret = -1;

        } else
                if (collation_rule == COLLATION_FILE_NAME) {
                        if ((offsetof(INDEX_ENTRY, key.file_name.file_name)
                                    + ie->key.file_name.file_name_length
                                                * sizeof(ntfschar))
                                > le16_to_cpu(ie->length)) {
                                ntfs_log_error("File name overflow from index"
                                        " entry in inode %lld\n",
                                        (long long)inum);
                                ret = -1;
                        }
                } else {
                        if (ie->data_length
                                && ((le16_to_cpu(ie->data_offset)
                                    + le16_to_cpu(ie->data_length))
                                    > le16_to_cpu(ie->length))) {
                                ntfs_log_error("Data overflow from index"
                                        " entry in inode %lld\n",
                                        (long long)inum);
                                ret = -1;
                        }
                }
        return (ret);
}

/** 
 * Find a key in the index block.
 * 
 * Return values:
 *   STATUS_OK with errno set to ESUCCESS if we know for sure that the 
 *             entry exists and @ie_out points to this entry.
 *   STATUS_NOT_FOUND with errno set to ENOENT if we know for sure the
 *                    entry doesn't exist and @ie_out is the insertion point.
 *   STATUS_KEEP_SEARCHING if we can't answer the above question and
 *                         @vcn will contain the node index block.
 *   STATUS_ERROR with errno set if on unexpected error during lookup.
 */
static int ntfs_ie_lookup(const void *key, const int key_len,
                          ntfs_index_context *icx, INDEX_HEADER *ih,
                          VCN *vcn, INDEX_ENTRY **ie_out)
{
        INDEX_ENTRY *ie;
        u8 *index_end;
        int rc, item = 0;
         
        ntfs_log_trace("Entering\n");
        
        index_end = ntfs_ie_get_end(ih);
        
        /*
         * Loop until we exceed valid memory (corruption case) or until we
         * reach the last entry.
         */
        for (ie = ntfs_ie_get_first(ih); ; ie = ntfs_ie_get_next(ie)) {
                /* Bounds checks. */
                if ((u8 *)ie + sizeof(INDEX_ENTRY_HEADER) > index_end ||
                    (u8 *)ie + le16_to_cpu(ie->length) > index_end) {
                        errno = ERANGE;
                        ntfs_log_error("Index entry out of bounds in inode "
                                       "%llu.\n",
                                       (unsigned long long)icx->ni->mft_no);
                        return STATUS_ERROR;
                }
                /*
                 * The last entry cannot contain a key.  It can however contain
                 * a pointer to a child node in the B+tree so we just break out.
                 */
                if (ntfs_ie_end(ie))
                        break;
                /*
                 * Not a perfect match, need to do full blown collation so we
                 * know which way in the B+tree we have to go.
                 */
                if (!icx->collate) {
                        ntfs_log_error("Collation function not defined\n");
                        errno = EOPNOTSUPP;
                        return STATUS_ERROR;
                }
                        /* Make sure key and data do not overflow from entry */
                if (ntfs_index_entry_inconsistent(ie, icx->ir->collation_rule,
                                icx->ni->mft_no)) {
                        errno = EIO;
                        return STATUS_ERROR;
                }
                rc = icx->collate(icx->ni->vol, key, key_len,
                                        &ie->key, le16_to_cpu(ie->key_length));
                if (rc == NTFS_COLLATION_ERROR) {
                        ntfs_log_error("Collation error. Perhaps a filename "
                                       "contains invalid characters?\n");
                        errno = ERANGE;
                        return STATUS_ERROR;
                }
                /*
                 * If @key collates before the key of the current entry, there
                 * is definitely no such key in this index but we might need to
                 * descend into the B+tree so we just break out of the loop.
                 */
                if (rc == -1)
                        break;
                
                if (!rc) {
                        *ie_out = ie;
                        errno = 0;
                        icx->parent_pos[icx->pindex] = item;
                        return STATUS_OK;
                }
                
                item++;
        }
        /*
         * We have finished with this index block without success. Check for the
         * presence of a child node and if not present return with errno ENOENT,
         * otherwise we will keep searching in another index block.
         */
        if (!(ie->ie_flags & INDEX_ENTRY_NODE)) {
                ntfs_log_debug("Index entry wasn't found.\n");
                *ie_out = ie;
                errno = ENOENT;
                return STATUS_NOT_FOUND;
        }
        
        /* Get the starting vcn of the index_block holding the child node. */
        *vcn = ntfs_ie_get_vcn(ie);
        if (*vcn < 0) {
                errno = EINVAL;
                ntfs_log_perror("Negative vcn in inode %llu",
                                (unsigned long long)icx->ni->mft_no);
                return STATUS_ERROR;
        }

        ntfs_log_trace("Parent entry number %d\n", item);
        icx->parent_pos[icx->pindex] = item;
        
        return STATUS_KEEP_SEARCHING;
}

static ntfs_attr *ntfs_ia_open(ntfs_index_context *icx, ntfs_inode *ni)
{
        ntfs_attr *na;
        
        na = ntfs_attr_open(ni, AT_INDEX_ALLOCATION, icx->name, icx->name_len);
        if (!na) {
                ntfs_log_perror("Failed to open index allocation of inode "
                                "%llu", (unsigned long long)ni->mft_no);
                return NULL;
        }
        
        return na;
}

static int ntfs_ib_read(ntfs_index_context *icx, VCN vcn, INDEX_BLOCK *dst)
{
        s64 pos, ret;

        ntfs_log_trace("vcn: %lld\n", (long long)vcn);
        
        pos = ntfs_ib_vcn_to_pos(icx, vcn);

        ret = ntfs_attr_mst_pread(icx->ia_na, pos, 1, icx->block_size, (u8 *)dst);
        if (ret != 1) {
                if (ret == -1)
                        ntfs_log_perror("Failed to read index block");
                else 
                        ntfs_log_error("Failed to read full index block at "
                                       "%lld\n", (long long)pos);
                return -1;
        }
        
        if (ntfs_index_block_inconsistent((INDEX_BLOCK*)dst, icx->block_size,
                                icx->ia_na->ni->mft_no, vcn)) {
                errno = EIO;
                return -1;
        }
        
        return 0;
}

static int ntfs_icx_parent_inc(ntfs_index_context *icx)
{
        icx->pindex++;
        if (icx->pindex >= MAX_PARENT_VCN) {
                errno = EOPNOTSUPP;
                ntfs_log_perror("Index is over %d level deep", MAX_PARENT_VCN);
                return STATUS_ERROR;
        }
        return STATUS_OK;
}

static int ntfs_icx_parent_dec(ntfs_index_context *icx)
{
        icx->pindex--;
        if (icx->pindex < 0) {
                errno = EINVAL;
                ntfs_log_perror("Corrupt index pointer (%d)", icx->pindex);
                return STATUS_ERROR;
        }
        return STATUS_OK;
}
        
/**
 * ntfs_index_lookup - find a key in an index and return its index entry
 * @key:        [IN] key for which to search in the index
 * @key_len:    [IN] length of @key in bytes
 * @icx:        [IN/OUT] context describing the index and the returned entry
 *
 * Before calling ntfs_index_lookup(), @icx must have been obtained from a
 * call to ntfs_index_ctx_get().
 *
 * Look for the @key in the index specified by the index lookup context @icx.
 * ntfs_index_lookup() walks the contents of the index looking for the @key.
 *
 * If the @key is found in the index, 0 is returned and @icx is setup to
 * describe the index entry containing the matching @key.  @icx->entry is the
 * index entry and @icx->data and @icx->data_len are the index entry data and
 * its length in bytes, respectively.
 *
 * If the @key is not found in the index, -1 is returned, errno = ENOENT and
 * @icx is setup to describe the index entry whose key collates immediately
 * after the search @key, i.e. this is the position in the index at which
 * an index entry with a key of @key would need to be inserted.
 *
 * If an error occurs return -1, set errno to error code and @icx is left
 * untouched.
 *
 * When finished with the entry and its data, call ntfs_index_ctx_put() to free
 * the context and other associated resources.
 *
 * If the index entry was modified, call ntfs_index_entry_mark_dirty() before
 * the call to ntfs_index_ctx_put() to ensure that the changes are written
 * to disk.
 */
int ntfs_index_lookup(const void *key, const int key_len, ntfs_index_context *icx)
{
        VCN old_vcn, vcn;
        ntfs_inode *ni = icx->ni;
        INDEX_ROOT *ir;
        INDEX_ENTRY *ie;
        INDEX_BLOCK *ib = NULL;
        int ret, err = 0;

        ntfs_log_trace("Entering\n");
        
        if (!key || key_len <= 0) {
                errno = EINVAL;
                ntfs_log_perror("key: %p  key_len: %d", key, key_len);
                return -1;
        }

        ir = ntfs_ir_lookup(ni, icx->name, icx->name_len, &icx->actx);
        if (!ir) {
                if (errno == ENOENT)
                        errno = EIO;
                return -1;
        }
        
        icx->block_size = le32_to_cpu(ir->index_block_size);
        if (icx->block_size < NTFS_BLOCK_SIZE) {
                errno = EINVAL;
                ntfs_log_perror("Index block size (%d) is smaller than the "
                                "sector size (%d)", icx->block_size, NTFS_BLOCK_SIZE);
                goto err_out;
        }

        if (ni->vol->cluster_size <= icx->block_size)
                icx->vcn_size_bits = ni->vol->cluster_size_bits;
        else
                icx->vcn_size_bits = NTFS_BLOCK_SIZE_BITS;
                        /* get the appropriate collation function */
        icx->ir = ir;
        icx->collate = ntfs_get_collate_function(ir->collation_rule);
        if (!icx->collate) {
                err = errno = EOPNOTSUPP;
                ntfs_log_perror("Unknown collation rule 0x%x", 
                                (unsigned)le32_to_cpu(ir->collation_rule));
                goto err_out;
        }
        
        old_vcn = VCN_INDEX_ROOT_PARENT;
        ret = ntfs_ie_lookup(key, key_len, icx, &ir->index, &vcn, &ie);
        if (ret == STATUS_ERROR) {
                err = errno;
                goto err_lookup;
        }
        
        icx->ir = ir;
        
        if (ret != STATUS_KEEP_SEARCHING) {
                /* STATUS_OK or STATUS_NOT_FOUND */
                err = errno;
                icx->is_in_root = TRUE;
                icx->parent_vcn[icx->pindex] = old_vcn;
                goto done;
        }
        
        /* Child node present, descend into it. */
        
        icx->ia_na = ntfs_ia_open(icx, ni);
        if (!icx->ia_na)
                goto err_out;
        
        ib = ntfs_malloc(icx->block_size);
        if (!ib) {
                err = errno;
                goto err_out;
        }
        
descend_into_child_node:

        icx->parent_vcn[icx->pindex] = old_vcn;
        if (ntfs_icx_parent_inc(icx)) {
                err = errno;
                goto err_out;
        }
        old_vcn = vcn;

        ntfs_log_debug("Descend into node with VCN %lld\n", (long long)vcn);
        
        if (ntfs_ib_read(icx, vcn, ib))
                goto err_out;
        
        ret = ntfs_ie_lookup(key, key_len, icx, &ib->index, &vcn, &ie);
        if (ret != STATUS_KEEP_SEARCHING) {
                err = errno;
                if (ret == STATUS_ERROR)
                        goto err_out;
                
                /* STATUS_OK or STATUS_NOT_FOUND */
                icx->is_in_root = FALSE;
                icx->ib = ib;
                icx->parent_vcn[icx->pindex] = vcn;
                goto done;
        }

        if ((ib->index.ih_flags & NODE_MASK) == LEAF_NODE) {
                ntfs_log_error("Index entry with child node found in a leaf "
                               "node in inode 0x%llx.\n",
                               (unsigned long long)ni->mft_no);
                goto err_out;
        }
        
        goto descend_into_child_node;
err_out:
        icx->bad_index = TRUE;  /* Force icx->* to be freed */
err_lookup:
        if (icx->actx) {
                ntfs_attr_put_search_ctx(icx->actx);
                icx->actx = NULL;
        }
        free(ib);
        if (!err)
                err = EIO;
        errno = err;
        return -1;
done:
        icx->entry = ie;
        icx->data = (u8 *)ie + offsetof(INDEX_ENTRY, key);
        icx->data_len = le16_to_cpu(ie->key_length);
        ntfs_log_trace("Done.\n");
        if (err) {
                errno = err;
                return -1;
        }
        return 0;

}

static INDEX_BLOCK *ntfs_ib_alloc(VCN ib_vcn, u32 ib_size, 
                                  INDEX_HEADER_FLAGS node_type)
{
        INDEX_BLOCK *ib;
        int ih_size = sizeof(INDEX_HEADER);
        
        ntfs_log_trace("ib_vcn: %lld ib_size: %u\n", (long long)ib_vcn, ib_size);
        
        ib = ntfs_calloc(ib_size);
        if (!ib)
                return NULL;
        
        ib->magic = magic_INDX;
        ib->usa_ofs = const_cpu_to_le16(sizeof(INDEX_BLOCK));
        ib->usa_count = cpu_to_le16(ib_size / NTFS_BLOCK_SIZE + 1);
        /* Set USN to 1 */
        *(le16 *)((char *)ib + le16_to_cpu(ib->usa_ofs)) = const_cpu_to_le16(1);
        ib->lsn = const_cpu_to_sle64(0);
        
        ib->index_block_vcn = cpu_to_sle64(ib_vcn);
        
        ib->index.entries_offset = cpu_to_le32((ih_size +
                        le16_to_cpu(ib->usa_count) * 2 + 7) & ~7);
        ib->index.index_length = const_cpu_to_le32(0);
        ib->index.allocated_size = cpu_to_le32(ib_size - 
                                               (sizeof(INDEX_BLOCK) - ih_size));
        ib->index.ih_flags = node_type;
        
        return ib;
}       

/** 
 *  Find the median by going through all the entries
 */
static INDEX_ENTRY *ntfs_ie_get_median(INDEX_HEADER *ih)
{
        INDEX_ENTRY *ie, *ie_start;
        u8 *ie_end;
        int i = 0, median;
        
        ntfs_log_trace("Entering\n");
        
        ie = ie_start = ntfs_ie_get_first(ih);
        ie_end   = (u8 *)ntfs_ie_get_end(ih);
        
        while ((u8 *)ie < ie_end && !ntfs_ie_end(ie)) {
                ie = ntfs_ie_get_next(ie);
                i++;
        }
        /*
         * NOTE: this could be also the entry at the half of the index block.
         */
        median = i / 2 - 1;
        
        ntfs_log_trace("Entries: %d  median: %d\n", i, median);
        
        for (i = 0, ie = ie_start; i <= median; i++)
                ie = ntfs_ie_get_next(ie);
        
        return ie;
}

static s64 ntfs_ibm_vcn_to_pos(ntfs_index_context *icx, VCN vcn)
{
        return ntfs_ib_vcn_to_pos(icx, vcn) / icx->block_size;
}

static s64 ntfs_ibm_pos_to_vcn(ntfs_index_context *icx, s64 pos)
{
        return ntfs_ib_pos_to_vcn(icx, pos * icx->block_size);
}

static int ntfs_ibm_add(ntfs_index_context *icx)
{
        u8 bmp[8];

        ntfs_log_trace("Entering\n");
        
        if (ntfs_attr_exist(icx->ni, AT_BITMAP, icx->name, icx->name_len))
                return STATUS_OK;
        /*
         * AT_BITMAP must be at least 8 bytes.
         */
        memset(bmp, 0, sizeof(bmp));
        if (ntfs_attr_add(icx->ni, AT_BITMAP, icx->name, icx->name_len,
                          bmp, sizeof(bmp))) {
                ntfs_log_perror("Failed to add AT_BITMAP");
                return STATUS_ERROR;
        }
        
        return STATUS_OK;
}

static int ntfs_ibm_modify(ntfs_index_context *icx, VCN vcn, int set)
{
        u8 byte;
        s64 pos = ntfs_ibm_vcn_to_pos(icx, vcn);
        u32 bpos = pos / 8;
        u32 bit = 1 << (pos % 8);
        ntfs_attr *na;
        int ret = STATUS_ERROR;

        ntfs_log_trace("%s vcn: %lld\n", set ? "set" : "clear", (long long)vcn);
        
        na = ntfs_attr_open(icx->ni, AT_BITMAP,  icx->name, icx->name_len);
        if (!na) {
                ntfs_log_perror("Failed to open $BITMAP attribute");
                return -1;
        }

        if (set) {
                if (na->data_size < bpos + 1) {
                        if (ntfs_attr_truncate(na, (na->data_size + 8) & ~7)) {
                                ntfs_log_perror("Failed to truncate AT_BITMAP");
                                goto err_na;
                        }
                }
        }
        
        if (ntfs_attr_pread(na, bpos, 1, &byte) != 1) {
                ntfs_log_perror("Failed to read $BITMAP");
                goto err_na;
        }

        if (set) 
                byte |= bit;
        else
                byte &= ~bit;
                
        if (ntfs_attr_pwrite(na, bpos, 1, &byte) != 1) {
                ntfs_log_perror("Failed to write $Bitmap");
                goto err_na;
        }

        ret = STATUS_OK;
err_na:
        ntfs_attr_close(na);
        return ret;
}


static int ntfs_ibm_set(ntfs_index_context *icx, VCN vcn)
{
        return ntfs_ibm_modify(icx, vcn, 1);
}

static int ntfs_ibm_clear(ntfs_index_context *icx, VCN vcn)
{
        return ntfs_ibm_modify(icx, vcn, 0);
}

static VCN ntfs_ibm_get_free(ntfs_index_context *icx)
{
        u8 *bm;
        int bit;
        s64 vcn, byte, size;

        ntfs_log_trace("Entering\n");
        
        bm = ntfs_attr_readall(icx->ni, AT_BITMAP,  icx->name, icx->name_len,
                               &size);
        if (!bm)
                return (VCN)-1;
        
        for (byte = 0; byte < size; byte++) {
                
                if (bm[byte] == 255)
                        continue;
                
                for (bit = 0; bit < 8; bit++) {
                        if (!(bm[byte] & (1 << bit))) {
                                vcn = ntfs_ibm_pos_to_vcn(icx, byte * 8 + bit);
                                goto out;
                        }
                }
        }
        
        vcn = ntfs_ibm_pos_to_vcn(icx, size * 8);
out:    
        ntfs_log_trace("allocated vcn: %lld\n", (long long)vcn);

        if (ntfs_ibm_set(icx, vcn))
                vcn = (VCN)-1;
        
        free(bm);
        return vcn;
}

static INDEX_BLOCK *ntfs_ir_to_ib(INDEX_ROOT *ir, VCN ib_vcn)
{
        INDEX_BLOCK *ib;
        INDEX_ENTRY *ie_last;
        char *ies_start, *ies_end;
        int i;
        
        ntfs_log_trace("Entering\n");
        
        ib = ntfs_ib_alloc(ib_vcn, le32_to_cpu(ir->index_block_size), LEAF_NODE);
        if (!ib)
                return NULL;
        
        ies_start = (char *)ntfs_ie_get_first(&ir->index);
        ies_end   = (char *)ntfs_ie_get_end(&ir->index);
        ie_last   = ntfs_ie_get_last((INDEX_ENTRY *)ies_start, ies_end);
        /* 
         * Copy all entries, including the termination entry
         * as well, which can never have any data.
         */
        i = (char *)ie_last - ies_start + le16_to_cpu(ie_last->length);
        memcpy(ntfs_ie_get_first(&ib->index), ies_start, i);
        
        ib->index.ih_flags = ir->index.ih_flags;
        ib->index.index_length = cpu_to_le32(i +
                        le32_to_cpu(ib->index.entries_offset));
        return ib;
}

static void ntfs_ir_nill(INDEX_ROOT *ir)
{
        INDEX_ENTRY *ie_last;
        char *ies_start, *ies_end;
        
        ntfs_log_trace("Entering\n");
        /*
         * TODO: This function could be much simpler.
         */
        ies_start = (char *)ntfs_ie_get_first(&ir->index);
        ies_end   = (char *)ntfs_ie_get_end(&ir->index);
        ie_last   = ntfs_ie_get_last((INDEX_ENTRY *)ies_start, ies_end);
        /* 
         * Move the index root termination entry forward
         */
        if ((char *)ie_last > ies_start) {
                memmove(ies_start, (char *)ie_last, le16_to_cpu(ie_last->length));
                ie_last = (INDEX_ENTRY *)ies_start;
        }
}

static int ntfs_ib_copy_tail(ntfs_index_context *icx, INDEX_BLOCK *src,
                             INDEX_ENTRY *median, VCN new_vcn)
{
        u8 *ies_end;
        INDEX_ENTRY *ie_head;           /* first entry after the median */
        int tail_size, ret;
        INDEX_BLOCK *dst;
        
        ntfs_log_trace("Entering\n");
        
        dst = ntfs_ib_alloc(new_vcn, icx->block_size, 
                            src->index.ih_flags & NODE_MASK);
        if (!dst)
                return STATUS_ERROR;
        
        ie_head = ntfs_ie_get_next(median);
        
        ies_end = (u8 *)ntfs_ie_get_end(&src->index);
        tail_size = ies_end - (u8 *)ie_head;
        memcpy(ntfs_ie_get_first(&dst->index), ie_head, tail_size);
        
        dst->index.index_length = cpu_to_le32(tail_size + 
                                              le32_to_cpu(dst->index.entries_offset));
        ret = ntfs_ib_write(icx, dst);

        free(dst);
        return ret;
}

static int ntfs_ib_cut_tail(ntfs_index_context *icx, INDEX_BLOCK *ib,
                            INDEX_ENTRY *ie)
{
        char *ies_start, *ies_end;
        INDEX_ENTRY *ie_last;
        
        ntfs_log_trace("Entering\n");
        
        ies_start = (char *)ntfs_ie_get_first(&ib->index);
        ies_end   = (char *)ntfs_ie_get_end(&ib->index);
        
        ie_last   = ntfs_ie_get_last((INDEX_ENTRY *)ies_start, ies_end);
        if (ie_last->ie_flags & INDEX_ENTRY_NODE)
                ntfs_ie_set_vcn(ie_last, ntfs_ie_get_vcn(ie));
        
        memcpy(ie, ie_last, le16_to_cpu(ie_last->length));
        
        ib->index.index_length = cpu_to_le32(((char *)ie - ies_start) + 
                le16_to_cpu(ie->length) + le32_to_cpu(ib->index.entries_offset));
        
        if (ntfs_ib_write(icx, ib))
                return STATUS_ERROR;
        
        return STATUS_OK;
}
        
static int ntfs_ia_add(ntfs_index_context *icx)
{
        ntfs_log_trace("Entering\n");

        if (ntfs_ibm_add(icx))
                return -1;
        
        if (!ntfs_attr_exist(icx->ni, AT_INDEX_ALLOCATION, icx->name, icx->name_len)) {
        
                if (ntfs_attr_add(icx->ni, AT_INDEX_ALLOCATION, icx->name,
                                  icx->name_len, NULL, 0)) {
                        ntfs_log_perror("Failed to add AT_INDEX_ALLOCATION");
                        return -1;
                }
        }
        
        icx->ia_na = ntfs_ia_open(icx, icx->ni);
        if (!icx->ia_na)
                return -1;

        return 0;
}

static int ntfs_ir_reparent(ntfs_index_context *icx)
{
        ntfs_attr_search_ctx *ctx = NULL;
        INDEX_ROOT *ir;
        INDEX_ENTRY *ie;
        INDEX_BLOCK *ib = NULL;
        VCN new_ib_vcn;
        int ix_root_size;
        int ret = STATUS_ERROR;

        ntfs_log_trace("Entering\n");
        
        ir = ntfs_ir_lookup2(icx->ni, icx->name, icx->name_len);
        if (!ir)
                goto out;
        
        if ((ir->index.ih_flags & NODE_MASK) == SMALL_INDEX)
                if (ntfs_ia_add(icx))
                        goto out;
        
        new_ib_vcn = ntfs_ibm_get_free(icx);
        if (new_ib_vcn == -1)
                goto out;
                
        ir = ntfs_ir_lookup2(icx->ni, icx->name, icx->name_len);
        if (!ir)
                goto clear_bmp;
        
        ib = ntfs_ir_to_ib(ir, new_ib_vcn);
        if (ib == NULL) {
                ntfs_log_perror("Failed to move index root to index block");
                goto clear_bmp;
        }
                
        if (ntfs_ib_write(icx, ib))
                goto clear_bmp;
        
retry :
        ir = ntfs_ir_lookup(icx->ni, icx->name, icx->name_len, &ctx);
        if (!ir)
                goto clear_bmp;
        
        ntfs_ir_nill(ir);
        
        ie = ntfs_ie_get_first(&ir->index);
        ie->ie_flags |= INDEX_ENTRY_NODE;
        ie->length = const_cpu_to_le16(sizeof(INDEX_ENTRY_HEADER) + sizeof(VCN));
        
        ir->index.ih_flags = LARGE_INDEX;
        ir->index.index_length = cpu_to_le32(le32_to_cpu(ir->index.entries_offset)
                                             + le16_to_cpu(ie->length));
        ir->index.allocated_size = ir->index.index_length;
        ix_root_size = sizeof(INDEX_ROOT) - sizeof(INDEX_HEADER)
                        + le32_to_cpu(ir->index.allocated_size);
        if (ntfs_resident_attr_value_resize(ctx->mrec, ctx->attr,
                                        ix_root_size)) {
                        /*
                         * When there is no space to build a non-resident
                         * index, we may have to move the root to an extent
                         */
                if ((errno == ENOSPC)
                    && (ctx->al_entry || !ntfs_inode_add_attrlist(icx->ni))) {
                        ntfs_attr_put_search_ctx(ctx);
                        ctx = (ntfs_attr_search_ctx*)NULL;
                        ir = ntfs_ir_lookup(icx->ni, icx->name, icx->name_len,
                                                        &ctx);
                        if (ir
                            && !ntfs_attr_record_move_away(ctx, ix_root_size
                                    - le32_to_cpu(ctx->attr->value_length))) {
                                ntfs_attr_put_search_ctx(ctx);
                                ctx = (ntfs_attr_search_ctx*)NULL;
                                goto retry;
                        }
                }
                /* FIXME: revert index root */
                goto clear_bmp;
        }
        /*
         *  FIXME: do it earlier if we have enough space in IR (should always),
         *  so in error case we wouldn't lose the IB.
         */
        ntfs_ie_set_vcn(ie, new_ib_vcn);
        
        ret = STATUS_OK;
err_out:
        free(ib);
        ntfs_attr_put_search_ctx(ctx);
out:
        return ret;
clear_bmp:
        ntfs_ibm_clear(icx, new_ib_vcn);
        goto err_out;
}

/**
 * ntfs_ir_truncate - Truncate index root attribute
 * 
 * Returns STATUS_OK, STATUS_RESIDENT_ATTRIBUTE_FILLED_MFT or STATUS_ERROR.
 */
static int ntfs_ir_truncate(ntfs_index_context *icx, int data_size)
{                         
        ntfs_attr *na;
        int ret;

        ntfs_log_trace("Entering\n");
        
        na = ntfs_attr_open(icx->ni, AT_INDEX_ROOT, icx->name, icx->name_len);
        if (!na) {
                ntfs_log_perror("Failed to open INDEX_ROOT");
                return STATUS_ERROR;
        }
        /*
         *  INDEX_ROOT must be resident and its entries can be moved to 
         *  INDEX_BLOCK, so ENOSPC isn't a real error.
         */
        ret = ntfs_attr_truncate(na, data_size + offsetof(INDEX_ROOT, index));
        if (ret == STATUS_OK) {
                
                icx->ir = ntfs_ir_lookup2(icx->ni, icx->name, icx->name_len);
                if (!icx->ir)
                        return STATUS_ERROR;
        
                icx->ir->index.allocated_size = cpu_to_le32(data_size);
                
        } else if (ret == STATUS_ERROR)
                ntfs_log_perror("Failed to truncate INDEX_ROOT");
        
        ntfs_attr_close(na);
        return ret;
}
                
/**
 * ntfs_ir_make_space - Make more space for the index root attribute
 * 
 * On success return STATUS_OK or STATUS_KEEP_SEARCHING.
 * On error return STATUS_ERROR.
 */
static int ntfs_ir_make_space(ntfs_index_context *icx, int data_size)
{                         
        int ret;

        ntfs_log_trace("Entering\n");

        ret = ntfs_ir_truncate(icx, data_size);
        if (ret == STATUS_RESIDENT_ATTRIBUTE_FILLED_MFT) {
        
                ret = ntfs_ir_reparent(icx);
                if (ret == STATUS_OK)
                        ret = STATUS_KEEP_SEARCHING;
                else
                        ntfs_log_perror("Failed to nodify INDEX_ROOT");
        }

        return ret;
}

/*
 * NOTE: 'ie' must be a copy of a real index entry.
 */
static int ntfs_ie_add_vcn(INDEX_ENTRY **ie)
{
        INDEX_ENTRY *p, *old = *ie;
         
        old->length = cpu_to_le16(le16_to_cpu(old->length) + sizeof(VCN));
        p = realloc(old, le16_to_cpu(old->length));
        if (!p)
                return STATUS_ERROR;
        
        p->ie_flags |= INDEX_ENTRY_NODE;
        *ie = p;

        return STATUS_OK;
}

static int ntfs_ih_insert(INDEX_HEADER *ih, INDEX_ENTRY *orig_ie, VCN new_vcn, 
                          int pos)
{
        INDEX_ENTRY *ie_node, *ie;
        int ret = STATUS_ERROR;
        VCN old_vcn;
        
        ntfs_log_trace("Entering\n");
        
        ie = ntfs_ie_dup(orig_ie);
        if (!ie)
                return STATUS_ERROR;
        
        if (!(ie->ie_flags & INDEX_ENTRY_NODE))
                if (ntfs_ie_add_vcn(&ie))
                        goto out;

        ie_node = ntfs_ie_get_by_pos(ih, pos);
        old_vcn = ntfs_ie_get_vcn(ie_node);
        ntfs_ie_set_vcn(ie_node, new_vcn);
        
        ntfs_ie_insert(ih, ie, ie_node);
        ntfs_ie_set_vcn(ie_node, old_vcn);
        ret = STATUS_OK;
out:    
        free(ie);
        
        return ret;
}

static VCN ntfs_icx_parent_vcn(ntfs_index_context *icx)
{
        return icx->parent_vcn[icx->pindex];
}

static VCN ntfs_icx_parent_pos(ntfs_index_context *icx)
{
        return icx->parent_pos[icx->pindex];
}


static int ntfs_ir_insert_median(ntfs_index_context *icx, INDEX_ENTRY *median,
                                 VCN new_vcn)
{
        u32 new_size;
        int ret;
        
        ntfs_log_trace("Entering\n");
        
        icx->ir = ntfs_ir_lookup2(icx->ni, icx->name, icx->name_len);
        if (!icx->ir)
                return STATUS_ERROR;

        new_size = le32_to_cpu(icx->ir->index.index_length) + 
                        le16_to_cpu(median->length);
        if (!(median->ie_flags & INDEX_ENTRY_NODE))
                new_size += sizeof(VCN);

        ret = ntfs_ir_make_space(icx, new_size);
        if (ret != STATUS_OK)
                return ret;
        
        icx->ir = ntfs_ir_lookup2(icx->ni, icx->name, icx->name_len);
        if (!icx->ir)
                return STATUS_ERROR;

        return ntfs_ih_insert(&icx->ir->index, median, new_vcn, 
                              ntfs_icx_parent_pos(icx));
}

static int ntfs_ib_split(ntfs_index_context *icx, INDEX_BLOCK *ib);

/**
 * On success return STATUS_OK or STATUS_KEEP_SEARCHING.
 * On error return STATUS_ERROR.
 */
static int ntfs_ib_insert(ntfs_index_context *icx, INDEX_ENTRY *ie, VCN new_vcn)
{                         
        INDEX_BLOCK *ib;
        u32 idx_size, allocated_size;
        int err = STATUS_ERROR;
        VCN old_vcn;

        ntfs_log_trace("Entering\n");
        
        ib = ntfs_malloc(icx->block_size);
        if (!ib)
                return -1;
        
        old_vcn = ntfs_icx_parent_vcn(icx);
        
        if (ntfs_ib_read(icx, old_vcn, ib))
                goto err_out;

        idx_size       = le32_to_cpu(ib->index.index_length);
        allocated_size = le32_to_cpu(ib->index.allocated_size);
        /* FIXME: sizeof(VCN) should be included only if ie has no VCN */
        if (idx_size + le16_to_cpu(ie->length) + sizeof(VCN) > allocated_size) {
                err = ntfs_ib_split(icx, ib);
                if (err == STATUS_OK)
                        err = STATUS_KEEP_SEARCHING;
                goto err_out;
        }
        
        if (ntfs_ih_insert(&ib->index, ie, new_vcn, ntfs_icx_parent_pos(icx)))
                goto err_out;
        
        if (ntfs_ib_write(icx, ib))
                goto err_out;
        
        err = STATUS_OK;
err_out:        
        free(ib);
        return err;
}

/**
 * ntfs_ib_split - Split an index block
 * 
 * On success return STATUS_OK or STATUS_KEEP_SEARCHING.
 * On error return is STATUS_ERROR.
 */
static int ntfs_ib_split(ntfs_index_context *icx, INDEX_BLOCK *ib)
{                         
        INDEX_ENTRY *median;
        VCN new_vcn;
        int ret;

        ntfs_log_trace("Entering\n");
        
        if (ntfs_icx_parent_dec(icx))
                return STATUS_ERROR;
        
        median  = ntfs_ie_get_median(&ib->index);
        new_vcn = ntfs_ibm_get_free(icx);
        if (new_vcn == -1)
                return STATUS_ERROR;
        
        if (ntfs_ib_copy_tail(icx, ib, median, new_vcn)) {
                ntfs_ibm_clear(icx, new_vcn);
                return STATUS_ERROR;
        }
        
        if (ntfs_icx_parent_vcn(icx) == VCN_INDEX_ROOT_PARENT)
                ret = ntfs_ir_insert_median(icx, median, new_vcn);
        else
                ret = ntfs_ib_insert(icx, median, new_vcn);
        
        if (ret != STATUS_OK) {
                ntfs_ibm_clear(icx, new_vcn);
                return ret;
        }
        
        ret = ntfs_ib_cut_tail(icx, ib, median);
        
        return ret;
}

/* JPA static */
int ntfs_ie_add(ntfs_index_context *icx, INDEX_ENTRY *ie)
{
        INDEX_HEADER *ih;
        int allocated_size, new_size;
        int ret = STATUS_ERROR;
        
#ifdef DEBUG
/* removed by JPA to make function usable for security indexes
        char *fn;
        fn = ntfs_ie_filename_get(ie);
        ntfs_log_trace("file: '%s'\n", fn);
        ntfs_attr_name_free(&fn);
*/
#endif
        
        while (1) {
                                
                if (!ntfs_index_lookup(&ie->key, le16_to_cpu(ie->key_length), icx)) {
                        errno = EEXIST;
                        ntfs_log_perror("Index already have such entry");
                        goto err_out;
                }
                if (errno != ENOENT) {
                        ntfs_log_perror("Failed to find place for new entry");
                        goto err_out;
                }
                
                if (icx->is_in_root)
                        ih = &icx->ir->index;
                else
                        ih = &icx->ib->index;
                
                allocated_size = le32_to_cpu(ih->allocated_size);
                new_size = le32_to_cpu(ih->index_length) + le16_to_cpu(ie->length);
        
                if (new_size <= allocated_size)
                        break;
                
                ntfs_log_trace("index block sizes: allocated: %d  needed: %d\n",
                               allocated_size, new_size);
                
                if (icx->is_in_root) {
                        if (ntfs_ir_make_space(icx, new_size) == STATUS_ERROR)
                                goto err_out;
                } else {
                        if (ntfs_ib_split(icx, icx->ib) == STATUS_ERROR)
                                goto err_out;
                }
                
                ntfs_inode_mark_dirty(icx->actx->ntfs_ino);
                ntfs_index_ctx_reinit(icx);
        }
        
        ntfs_ie_insert(ih, ie, icx->entry);
        ntfs_index_entry_mark_dirty(icx);
        
        ret = STATUS_OK;
err_out:
        ntfs_log_trace("%s\n", ret ? "Failed" : "Done");
        return ret;
}

/**
 * ntfs_index_add_filename - add filename to directory index
 * @ni:         ntfs inode describing directory to which index add filename
 * @fn:         FILE_NAME attribute to add
 * @mref:       reference of the inode which @fn describes
 *
 * Return 0 on success or -1 on error with errno set to the error code.
 */
int ntfs_index_add_filename(ntfs_inode *ni, FILE_NAME_ATTR *fn, MFT_REF mref)
{
        INDEX_ENTRY *ie;
        ntfs_index_context *icx;
        int fn_size, ie_size, err, ret = -1;

        ntfs_log_trace("Entering\n");
        
        if (!ni || !fn) {
                ntfs_log_error("Invalid arguments.\n");
                errno = EINVAL;
                return -1;
        }
        
        fn_size = (fn->file_name_length * sizeof(ntfschar)) +
                        sizeof(FILE_NAME_ATTR);
        ie_size = (sizeof(INDEX_ENTRY_HEADER) + fn_size + 7) & ~7;
        
        ie = ntfs_calloc(ie_size);
        if (!ie)
                return -1;

        ie->indexed_file = cpu_to_le64(mref);
        ie->length       = cpu_to_le16(ie_size);
        ie->key_length   = cpu_to_le16(fn_size);
        memcpy(&ie->key, fn, fn_size);
        
        icx = ntfs_index_ctx_get(ni, NTFS_INDEX_I30, 4);
        if (!icx)
                goto out;
        
        ret = ntfs_ie_add(icx, ie);
        err = errno;
        ntfs_index_ctx_put(icx);
        errno = err;
out:
        free(ie);
        return ret;
}

static int ntfs_ih_takeout(ntfs_index_context *icx, INDEX_HEADER *ih,
                           INDEX_ENTRY *ie, INDEX_BLOCK *ib)
{
        INDEX_ENTRY *ie_roam;
        int freed_space;
        BOOL full;
        int ret = STATUS_ERROR;
        
        ntfs_log_trace("Entering\n");
        
        full = ih->index_length == ih->allocated_size;
        ie_roam = ntfs_ie_dup_novcn(ie);
        if (!ie_roam)
                return STATUS_ERROR;

        ntfs_ie_delete(ih, ie);

        if (ntfs_icx_parent_vcn(icx) == VCN_INDEX_ROOT_PARENT) {
                /*
                 * Recover the space which may have been freed
                 * while deleting an entry from root index
                 */
                freed_space = le32_to_cpu(ih->allocated_size)
                                - le32_to_cpu(ih->index_length);
                if (full && (freed_space > 0) && !(freed_space & 7)) {
                        ntfs_ir_truncate(icx, le32_to_cpu(ih->index_length));
                        /* do nothing if truncation fails */
                }
                ntfs_inode_mark_dirty(icx->actx->ntfs_ino);
        } else
                if (ntfs_ib_write(icx, ib))
                        goto out;
        
        ntfs_index_ctx_reinit(icx);

        ret = ntfs_ie_add(icx, ie_roam);
out:
        free(ie_roam);
        return ret;
}

/**
 *  Used if an empty index block to be deleted has END entry as the parent
 *  in the INDEX_ROOT which is the only one there.
 */
static void ntfs_ir_leafify(ntfs_index_context *icx, INDEX_HEADER *ih)
{
        INDEX_ENTRY *ie;
        
        ntfs_log_trace("Entering\n");
        
        ie = ntfs_ie_get_first(ih);
        ie->ie_flags &= ~INDEX_ENTRY_NODE;
        ie->length = cpu_to_le16(le16_to_cpu(ie->length) - sizeof(VCN));
        
        ih->index_length = cpu_to_le32(le32_to_cpu(ih->index_length) - sizeof(VCN));
        ih->ih_flags &= ~LARGE_INDEX;
        
        /* Not fatal error */
        ntfs_ir_truncate(icx, le32_to_cpu(ih->index_length));
}

/**
 *  Used if an empty index block to be deleted has END entry as the parent 
 *  in the INDEX_ROOT which is not the only one there.
 */
static int ntfs_ih_reparent_end(ntfs_index_context *icx, INDEX_HEADER *ih,
                                INDEX_BLOCK *ib)
{
        INDEX_ENTRY *ie, *ie_prev;
        
        ntfs_log_trace("Entering\n");
        
        ie = ntfs_ie_get_by_pos(ih, ntfs_icx_parent_pos(icx));
        ie_prev = ntfs_ie_prev(ih, ie);
        
        ntfs_ie_set_vcn(ie, ntfs_ie_get_vcn(ie_prev));
        
        return ntfs_ih_takeout(icx, ih, ie_prev, ib);
}

static int ntfs_index_rm_leaf(ntfs_index_context *icx)
{
        INDEX_BLOCK *ib = NULL;
        INDEX_HEADER *parent_ih;
        INDEX_ENTRY *ie;
        int ret = STATUS_ERROR;
        
        ntfs_log_trace("pindex: %d\n", icx->pindex);
        
        if (ntfs_icx_parent_dec(icx))
                return STATUS_ERROR;

        if (ntfs_ibm_clear(icx, icx->parent_vcn[icx->pindex + 1]))
                return STATUS_ERROR;
        
        if (ntfs_icx_parent_vcn(icx) == VCN_INDEX_ROOT_PARENT)
                parent_ih = &icx->ir->index;
        else {
                ib = ntfs_malloc(icx->block_size);
                if (!ib)
                        return STATUS_ERROR;
                
                if (ntfs_ib_read(icx, ntfs_icx_parent_vcn(icx), ib))
                        goto out;
        
                parent_ih = &ib->index;
        }
        
        ie = ntfs_ie_get_by_pos(parent_ih, ntfs_icx_parent_pos(icx));
        if (!ntfs_ie_end(ie)) {
                ret = ntfs_ih_takeout(icx, parent_ih, ie, ib);
                goto out;
        }
                
        if (ntfs_ih_zero_entry(parent_ih)) {
                
                if (ntfs_icx_parent_vcn(icx) == VCN_INDEX_ROOT_PARENT) {
                        ntfs_ir_leafify(icx, parent_ih);
                        goto ok;
                }
                
                ret = ntfs_index_rm_leaf(icx);
                goto out;
        }
                
        if (ntfs_ih_reparent_end(icx, parent_ih, ib))
                goto out;
ok:     
        ret = STATUS_OK;
out:
        free(ib);
        return ret;
}

static int ntfs_index_rm_node(ntfs_index_context *icx)
{
        int entry_pos, pindex;
        VCN vcn;
        INDEX_BLOCK *ib = NULL;
        INDEX_ENTRY *ie_succ, *ie, *entry = icx->entry;
        INDEX_HEADER *ih;
        u32 new_size;
        int delta, ret = STATUS_ERROR;

        ntfs_log_trace("Entering\n");
        
        if (!icx->ia_na) {
                icx->ia_na = ntfs_ia_open(icx, icx->ni);
                if (!icx->ia_na)
                        return STATUS_ERROR;
        }

        ib = ntfs_malloc(icx->block_size);
        if (!ib)
                return STATUS_ERROR;
        
        ie_succ = ntfs_ie_get_next(icx->entry);
        entry_pos = icx->parent_pos[icx->pindex]++;
        pindex = icx->pindex;
descend:
        vcn = ntfs_ie_get_vcn(ie_succ);
        if (ntfs_ib_read(icx, vcn, ib))
                goto out;
        
        ie_succ = ntfs_ie_get_first(&ib->index);

        if (ntfs_icx_parent_inc(icx))
                goto out;
        
        icx->parent_vcn[icx->pindex] = vcn;
        icx->parent_pos[icx->pindex] = 0;

        if ((ib->index.ih_flags & NODE_MASK) == INDEX_NODE)
                goto descend;

        if (ntfs_ih_zero_entry(&ib->index)) {
                errno = EIO;
                ntfs_log_perror("Empty index block");
                goto out;
        }

        ie = ntfs_ie_dup(ie_succ);
        if (!ie)
                goto out;
        
        if (ntfs_ie_add_vcn(&ie))
                goto out2;

        ntfs_ie_set_vcn(ie, ntfs_ie_get_vcn(icx->entry));

        if (icx->is_in_root)
                ih = &icx->ir->index;
        else
                ih = &icx->ib->index;

        delta = le16_to_cpu(ie->length) - le16_to_cpu(icx->entry->length);
        new_size = le32_to_cpu(ih->index_length) + delta;
        if (delta > 0) {
                if (icx->is_in_root) {
                        ret = ntfs_ir_make_space(icx, new_size);
                        if (ret != STATUS_OK)
                                goto out2;
                        
                        ih = &icx->ir->index;
                        entry = ntfs_ie_get_by_pos(ih, entry_pos);
                        
                } else if (new_size > le32_to_cpu(ih->allocated_size)) {
                        icx->pindex = pindex;
                        ret = ntfs_ib_split(icx, icx->ib);
                        if (ret == STATUS_OK)
                                ret = STATUS_KEEP_SEARCHING;
                        goto out2;
                }
        }

        ntfs_ie_delete(ih, entry);
        ntfs_ie_insert(ih, ie, entry);
        
        if (icx->is_in_root) {
                if (ntfs_ir_truncate(icx, new_size))
                        goto out2;
        } else
                if (ntfs_icx_ib_write(icx))
                        goto out2;
        
        ntfs_ie_delete(&ib->index, ie_succ);
        
        if (ntfs_ih_zero_entry(&ib->index)) {
                if (ntfs_index_rm_leaf(icx))
                        goto out2;
        } else 
                if (ntfs_ib_write(icx, ib))
                        goto out2;

        ret = STATUS_OK;
out2:
        free(ie);
out:
        free(ib);
        return ret;
}

/**
 * ntfs_index_rm - remove entry from the index
 * @icx:        index context describing entry to delete
 *
 * Delete entry described by @icx from the index. Index context is always 
 * reinitialized after use of this function, so it can be used for index 
 * lookup once again.
 *
 * Return 0 on success or -1 on error with errno set to the error code.
 */
/*static JPA*/
int ntfs_index_rm(ntfs_index_context *icx)
{
        INDEX_HEADER *ih;
        int err, ret = STATUS_OK;

        ntfs_log_trace("Entering\n");
        
        if (!icx || (!icx->ib && !icx->ir) || ntfs_ie_end(icx->entry)) {
                ntfs_log_error("Invalid arguments.\n");
                errno = EINVAL;
                goto err_out;
        }
        if (icx->is_in_root)
                ih = &icx->ir->index;
        else
                ih = &icx->ib->index;
        
        if (icx->entry->ie_flags & INDEX_ENTRY_NODE) {
                
                ret = ntfs_index_rm_node(icx);

        } else if (icx->is_in_root || !ntfs_ih_one_entry(ih)) {
                
                ntfs_ie_delete(ih, icx->entry);
                
                if (icx->is_in_root) {
                        err = ntfs_ir_truncate(icx, le32_to_cpu(ih->index_length));
                        if (err != STATUS_OK)
                                goto err_out;
                } else
                        if (ntfs_icx_ib_write(icx))
                                goto err_out;
        } else {
                if (ntfs_index_rm_leaf(icx))
                        goto err_out;
        }
out:
        return ret;
err_out:
        ret = STATUS_ERROR;
        goto out;
}

int ntfs_index_remove(ntfs_inode *dir_ni,
                ntfs_inode *ni __attribute__((unused)),
                const void *key, const int keylen)
{
        int ret = STATUS_ERROR;
        ntfs_index_context *icx;

        icx = ntfs_index_ctx_get(dir_ni, NTFS_INDEX_I30, 4);
        if (!icx)
                return -1;

        while (1) {
                                
                if (ntfs_index_lookup(key, keylen, icx))
                        goto err_out;

                ret = ntfs_index_rm(icx);
                if (ret == STATUS_ERROR)
                        goto err_out;
                else if (ret == STATUS_OK)
                        break;
                
                ntfs_inode_mark_dirty(icx->actx->ntfs_ino);
                ntfs_index_ctx_reinit(icx);
        }

        ntfs_inode_mark_dirty(icx->actx->ntfs_ino);
out:    
        ntfs_index_ctx_put(icx);
        return ret;
err_out:
        ret = STATUS_ERROR;
        ntfs_log_perror("Delete failed");
        goto out;
}

/**
 * ntfs_index_root_get - read the index root of an attribute
 * @ni:         open ntfs inode in which the ntfs attribute resides
 * @attr:       attribute for which we want its index root 
 *
 * This function will read the related index root an ntfs attribute.
 *
 * On success a buffer is allocated with the content of the index root
 * and which needs to be freed when it's not needed anymore.
 *
 * On error NULL is returned with errno set to the error code.
 */
INDEX_ROOT *ntfs_index_root_get(ntfs_inode *ni, ATTR_RECORD *attr)
{
        ntfs_attr_search_ctx *ctx;
        ntfschar *name;
        INDEX_ROOT *root = NULL;

        name = (ntfschar *)((u8 *)attr + le16_to_cpu(attr->name_offset));

        if (!ntfs_ir_lookup(ni, name, attr->name_length, &ctx))
                return NULL;
        
        root = ntfs_malloc(sizeof(INDEX_ROOT));
        if (!root)
                goto out;
        
        *root = *((INDEX_ROOT *)((u8 *)ctx->attr +
                                le16_to_cpu(ctx->attr->value_offset)));
out:    
        ntfs_attr_put_search_ctx(ctx);
        return root;
}


/*
 *              Walk down the index tree (leaf bound)
 *      until there are no subnode in the first index entry
 *      returns the entry at the bottom left in subnode
 */

static INDEX_ENTRY *ntfs_index_walk_down(INDEX_ENTRY *ie,
                        ntfs_index_context *ictx)
{
        INDEX_ENTRY *entry;
        s64 vcn;

        entry = ie;
        do {
                vcn = ntfs_ie_get_vcn(entry);
                if (ictx->is_in_root) {

                        /* down from level zero */

                        ictx->ir = (INDEX_ROOT*)NULL;
                        ictx->ib = (INDEX_BLOCK*)ntfs_malloc(ictx->block_size);
                        ictx->pindex = 1;
                        ictx->is_in_root = FALSE;
                } else {

                        /* down from non-zero level */
                        
                        ictx->pindex++;
                }
                ictx->parent_pos[ictx->pindex] = 0;
                ictx->parent_vcn[ictx->pindex] = vcn;
                if (!ntfs_ib_read(ictx,vcn,ictx->ib)) {
                        ictx->entry = ntfs_ie_get_first(&ictx->ib->index);
                        entry = ictx->entry;
                } else
                        entry = (INDEX_ENTRY*)NULL;
        } while (entry && (entry->ie_flags & INDEX_ENTRY_NODE));
        return (entry);
}

/*
 *              Walk up the index tree (root bound)
 *      until there is a valid data entry in parent
 *      returns the parent entry or NULL if no more parent
 */

static INDEX_ENTRY *ntfs_index_walk_up(INDEX_ENTRY *ie,
                        ntfs_index_context *ictx)
{
        INDEX_ENTRY *entry;
        s64 vcn;

        entry = ie;
        if (ictx->pindex > 0) {
                do {
                        ictx->pindex--;
                        if (!ictx->pindex) {

                                        /* we have reached the root */

                                free(ictx->ib);
                                ictx->ib = (INDEX_BLOCK*)NULL;
                                ictx->is_in_root = TRUE;
                                /* a new search context is to be allocated */
                                if (ictx->actx)
                                        free(ictx->actx);
                                ictx->ir = ntfs_ir_lookup(ictx->ni,
                                        ictx->name, ictx->name_len,
                                        &ictx->actx);
                                if (ictx->ir)
                                        entry = ntfs_ie_get_by_pos(
                                                &ictx->ir->index,
                                                ictx->parent_pos[ictx->pindex]);
                                else
                                        entry = (INDEX_ENTRY*)NULL;
                        } else {
                                        /* up into non-root node */
                                vcn = ictx->parent_vcn[ictx->pindex];
                                if (!ntfs_ib_read(ictx,vcn,ictx->ib)) {
                                        entry = ntfs_ie_get_by_pos(
                                                &ictx->ib->index,
                                                ictx->parent_pos[ictx->pindex]);
                                } else
                                        entry = (INDEX_ENTRY*)NULL;
                        }
                ictx->entry = entry;
                } while (entry && (ictx->pindex > 0)
                         && (entry->ie_flags & INDEX_ENTRY_END));
        } else
                entry = (INDEX_ENTRY*)NULL;
        return (entry);
}

/*
 *              Get next entry in an index according to collating sequence.
 *      Must be initialized through a ntfs_index_lookup()
 *
 *      Returns next entry or NULL if none
 *
 *      Sample layout :
 *
 *                 +---+---+---+---+---+---+---+---+    n ptrs to subnodes
 *                 |   |   | 10| 25| 33|   |   |   |    n-1 keys in between
 *                 +---+---+---+---+---+---+---+---+    no key in last entry
 *                              | A | A
 *                              | | | +-------------------------------+
 *   +--------------------------+ | +-----+                           |
 *   |                            +--+    |                           |
 *   V                               |    V                           |
 * +---+---+---+---+---+---+---+---+ |  +---+---+---+---+---+---+---+---+
 * | 11| 12| 13| 14| 15| 16| 17|   | |  | 26| 27| 28| 29| 30| 31| 32|   |
 * +---+---+---+---+---+---+---+---+ |  +---+---+---+---+---+---+---+---+
 *                               |   |
 *       +-----------------------+   |
 *       |                           |
 *     +---+---+---+---+---+---+---+---+
 *     | 18| 19| 20| 21| 22| 23| 24|   |
 *     +---+---+---+---+---+---+---+---+
 */

INDEX_ENTRY *ntfs_index_next(INDEX_ENTRY *ie, ntfs_index_context *ictx)
{
        INDEX_ENTRY *next;
        le16 flags;

                        /*
                         * lookup() may have returned an invalid node
                         * when searching for a partial key
                         * if this happens, walk up
                         */

        if (ie->ie_flags & INDEX_ENTRY_END)
                next = ntfs_index_walk_up(ie, ictx);
        else {
                        /*
                         * get next entry in same node
                         * there is always one after any entry with data
                         */

                next = (INDEX_ENTRY*)((char*)ie + le16_to_cpu(ie->length));
                ++ictx->parent_pos[ictx->pindex];
                flags = next->ie_flags;

                        /* walk down if it has a subnode */

                if (flags & INDEX_ENTRY_NODE) {
                        next = ntfs_index_walk_down(next,ictx);
                } else {

                                /* walk up it has no subnode, nor data */

                        if (flags & INDEX_ENTRY_END) {
                                next = ntfs_index_walk_up(next, ictx);
                        }
                }
        }
                /* return NULL if stuck at end of a block */

        if (next && (next->ie_flags & INDEX_ENTRY_END))
                next = (INDEX_ENTRY*)NULL;
        return (next);
}