/**
* index.c - NTFS index handling. Part of the Linux-NTFS project.
*
* Copyright (c) 2004-2005 Anton Altaparmakov
* Copyright (c) 2004-2005 Richard Russon
* Copyright (c) 2005-2007 Yura Pakhuchiy
* Copyright (c) 2005-2006 Szabolcs Szakacsits
*
* 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.
*
* 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 Linux-NTFS
* 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 "compat.h"
#include "attrib.h"
#include "collate.h"
#include "debug.h"
#include "index.h"
#include "mst.h"
#include "dir.h"
#include "logging.h"
#include "bitmap.h"
#include "support.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.
*/
{
if (ictx->is_in_root)
else
}
{
}
{
}
{
if (ret != 1) {
ntfs_log_perror("Failed to write index block %lld of inode "
"%llu", (long long)vcn,
return STATUS_ERROR;
}
return STATUS_OK;
}
{
return STATUS_ERROR;
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_log_trace("Entering.\n");
if (!ni) {
return NULL;
}
if (icx)
*icx = (ntfs_index_context) {
};
return icx;
}
{
ntfs_log_trace("Entering.\n");
return;
if (icx->is_in_root) {
return;
}
/* FIXME: Error handling!!! */
}
}
/**
* ntfs_index_ctx_put - release an index context
* @icx: index context to free
*
* Release the index context @icx, releasing all associated resources.
*/
{
}
/**
* 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.
*/
{
ntfs_log_trace("Entering.\n");
*icx = (ntfs_index_context) {
};
}
{
}
/**
* Get the subnode vcn to which the index entry refers.
*/
{
}
{
}
{
}
{
/* FIXME: check if it isn't overflowing the index block size */
}
{
}
/**
* Find the last entry in the index block
*/
{
ntfs_log_trace("Entering.\n");
return ie;
}
{
while (pos-- > 0)
return ie;
}
{
ntfs_log_trace("Entering.\n");
}
return ie_prev;
}
{
int name_len;
if (name_len < 0) {
ntfs_log_perror("ntfs_ucstombs");
return NULL;
} else if (name_len > 0)
return name;
return NULL;
}
{
char *s;
s = ntfs_ie_filename_get(ie);
ntfs_log_debug("'%s' ", s);
free(s);
}
{
ntfs_log_trace("Entering.\n");
while (!ntfs_ie_end(ie)) {
}
}
{
int n;
ntfs_log_trace("Entering.\n");
for (n = 0; !ntfs_ie_end(ie); n++)
return n;
}
{
}
{
return (ntfs_ih_numof_entries(ih) == 0);
}
{
ntfs_log_trace("Entering.\n");
}
{
}
/**
* Insert @ie index entry at @pos entry. Used @ih values should be ok already.
*/
{
ntfs_log_trace("Entering.\n");
ie_size);
}
{
ntfs_log_trace("Entering.\n");
if (dup)
return dup;
}
{
ntfs_log_trace("Entering.\n");
if (dup) {
}
return dup;
}
{
ntfs_log_trace("Entering.\n");
ntfs_log_error("Corrupt index block signature: vcn %lld inode "
"%llu\n", (long long)vcn,
return -1;
}
ntfs_log_error("Corrupt index block: VCN (%lld) is different "
"from expected VCN (%lld) in inode %llu\n",
(long long)vcn,
return -1;
}
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)icx->block_size);
return -1;
}
return 0;
}
{
ATTR_RECORD *a;
ntfs_log_trace("Entering.\n");
if (!*ctx) {
ntfs_log_perror("Failed to get $INDEX_ROOT search context");
return NULL;
}
ntfs_log_perror("Failed to lookup $INDEX_ROOT");
goto err_out;
}
if (a->non_resident) {
ntfs_log_perror("Non-resident $INDEX_ROOT detected");
goto err_out;
}
if (!ir)
return ir;
}
/**
* 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.
*/
{
ntfs_log_trace("Entering.\n");
/*
* Loop until we exceed valid memory (corruption case) or until we
* reach the last entry.
*/
/* Bounds checks. */
ntfs_log_error("Index entry out of bounds in inode "
"%llu.\n",
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 (rc == NTFS_COLLATION_ERROR) {
ntfs_log_error("Collation error. Perhaps a filename "
"contains invalid characters?\n");
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) {
errno = 0;
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.
*/
ntfs_log_debug("Index entry wasn't found.\n");
return STATUS_NOT_FOUND;
}
/* Get the starting vcn of the index_block holding the child node. */
if (*vcn < 0) {
ntfs_log_perror("Negative vcn in inode %llu\n",
return STATUS_ERROR;
}
return STATUS_KEEP_SEARCHING;
}
{
if (!na) {
ntfs_log_perror("Failed to open index allocation of inode "
return NULL;
}
return na;
}
{
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;
}
return -1;
return 0;
}
{
errno = EOPNOTSUPP;
return STATUS_ERROR;
}
return STATUS_OK;
}
{
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
*
* 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.
*/
{
ntfs_log_trace("Entering.\n");
return -1;
}
if (!ir) {
return -1;
}
ntfs_log_perror("Index block size (%u) is smaller than the "
return -1;
}
else
ntfs_log_perror("Unknown collation rule 0x%x",
goto err_out;
}
/*
* FIXME: check for both ir and ib that the first index entry is
* within the index block.
*/
if (ret == STATUS_ERROR) {
goto err_out;
}
if (ret != STATUS_KEEP_SEARCHING) {
/* STATUS_OK or STATUS_NOT_FOUND */
goto done;
}
/* Child node present, descend into it. */
goto err_out;
if (!ib) {
goto err_out;
}
if (ntfs_icx_parent_inc(icx)) {
goto err_out;
}
goto err_out;
if (ret != STATUS_KEEP_SEARCHING) {
if (ret == STATUS_ERROR)
goto err_out;
/* STATUS_OK or STATUS_NOT_FOUND */
goto done;
}
ntfs_log_error("Index entry with child node found in a leaf "
"node in inode 0x%llx.\n",
goto err_out;
}
goto descend_into_child_node;
}
if (!err)
if (actx)
return -1;
done:
ntfs_log_trace("Done.\n");
if (err) {
return -1;
}
return 0;
}
{
ib_size);
if (!ib)
return NULL;
/* Set USN to 1 */
(sizeof(INDEX_BLOCK) - ih_size));
return ib;
}
/**
* Find the median by going through all the entries
*/
{
int i = 0, median;
ntfs_log_trace("Entering.\n");
i++;
}
/*
* NOTE: this could be also the entry at the half of the index block.
*/
return ie;
}
{
}
{
}
{
ntfs_log_trace("Entering.\n");
return STATUS_OK;
/*
* AT_BITMAP must be at least 8 bytes.
*/
ntfs_log_perror("Failed to add AT_BITMAP");
return STATUS_ERROR;
}
return STATUS_OK;
}
{
if (!na) {
ntfs_log_perror("Failed to open $BITMAP attribute");
return -1;
}
if (set) {
ntfs_log_perror("Failed to truncate AT_BITMAP");
goto err_na;
}
}
}
ntfs_log_perror("Failed to read $BITMAP");
goto err_na;
}
if (set)
else
ntfs_log_perror("Failed to write $Bitmap");
goto err_na;
}
return ret;
}
{
}
{
}
{
int bit;
ntfs_log_trace("Entering.\n");
&size);
if (!bm)
return (VCN)-1;
continue;
goto out;
}
}
}
out:
return vcn;
}
{
int i;
ntfs_log_trace("Entering.\n");
LEAF_NODE)))
return NULL;
/*
* Copy all entries, including the termination entry
* as well, which can never have any data.
*/
return ib;
}
{
ntfs_log_trace("Entering\n");
/* TODO: This function could be much simpler. */
/* Move the index root termination entry forward. */
}
}
{
ntfs_log_trace("Entering.\n");
if (!dst)
return STATUS_ERROR;
return ret;
}
{
ntfs_log_trace("Entering.\n");
return STATUS_ERROR;
return STATUS_OK;
}
{
ntfs_log_trace("Entering.\n");
if (ntfs_ibm_add(icx))
return -1;
ntfs_log_perror("Failed to add AT_INDEX_ALLOCATION");
return -1;
}
}
return -1;
return 0;
}
{
if (ir)
return ir;
}
{
ntfs_log_trace("Entering.\n");
if (ntfs_ia_add(icx))
return -1;
if (!ir)
return -1;
if (new_ib_vcn == -1)
goto err_out;
ntfs_log_perror("Failed to move index root to index block");
goto clear_bmp;
}
goto clear_bmp;
sizeof(INDEX_ROOT) - sizeof(INDEX_HEADER) +
/* FIXME: revert bitmap, index root */
goto err_out;
return ret;
goto err_out;
}
/**
* ntfs_ir_truncate - Truncate index root attribute
*
* Returns STATUS_OK, STATUS_RESIDENT_ATTRIBUTE_FILLED_MFT or STATUS_ERROR.
*/
{
int ret;
ntfs_log_trace("Entering.\n");
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.
*/
return STATUS_ERROR;
} else {
ntfs_log_trace("Failed to truncate INDEX_ROOT");
}
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.
*/
{
int ret;
ntfs_log_trace("Entering.\n");
if (ret == STATUS_RESIDENT_ATTRIBUTE_FILLED_MFT) {
else
ntfs_log_perror("Failed to nodify INDEX_ROOT");
}
return ret;
}
/*
* NOTE: 'ie' must be a copy of a real index entry.
*/
{
if (!p)
return STATUS_ERROR;
p->flags |= INDEX_ENTRY_NODE;
*ie = p;
return STATUS_OK;
}
int pos)
{
ntfs_log_trace("Entering.\n");
if (!ie)
return STATUS_ERROR;
if (ntfs_ie_add_vcn(&ie))
goto out;
out:
return ret;
}
{
}
{
}
{
int ret;
ntfs_log_trace("Entering.\n");
return STATUS_ERROR;
return ret;
return STATUS_ERROR;
}
/**
* ntfs_ib_insert - insert an index block to an index context.
*
* On success return STATUS_OK or STATUS_KEEP_SEARCHING.
* On error return STATUS_ERROR.
*/
{
ntfs_log_trace("Entering.\n");
if (!ib)
return -1;
goto err_out;
/* FIXME: sizeof(VCN) should be included only if ie has no VCN */
goto err_out;
}
goto err_out;
goto err_out;
return err;
}
/**
* ntfs_ib_split - Split index allocation attribute
*
* On success return STATUS_OK or STATUS_KEEP_SEARCHING.
* On error return is STATUS_ERROR.
*/
{
int ret;
ntfs_log_trace("Entering.\n");
if (ntfs_icx_parent_dec(icx))
return STATUS_ERROR;
if (new_vcn == -1)
return STATUS_ERROR;
return STATUS_ERROR;
}
else
return ret;
}
return ret;
}
{
#ifdef DEBUG
char *fn;
#endif
while (1) {
icx)) {
ntfs_log_error("Index already have such entry.\n");
goto err_out;
}
ntfs_log_perror("Failed to find place for new entry");
goto err_out;
}
if (icx->is_in_root)
else
if (new_size <= allocated_size)
break;
ntfs_log_trace("index block sizes: allocated: %d needed: %d\n",
if (icx->is_in_root) {
goto err_out;
} else {
goto err_out;
}
}
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.
*/
{
ntfs_log_trace("Entering.\n");
ntfs_log_error("Invalid arguments.\n");
return -1;
}
sizeof(FILE_NAME_ATTR);
if (!ie)
return -1;
if (!icx)
goto out;
out:
return ret;
}
{
ntfs_log_trace("Entering.\n");
if (!ie_roam)
return STATUS_ERROR;
else
goto out;
out:
return ret;
}
/**
* ntfs_ir_leafify -
*
* 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.
*/
{
ntfs_log_trace("Entering.\n");
sizeof(VCN));
/* Not fatal error */
}
/**
* ntfs_ih_reparent_end -
*
* 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.
*/
{
ntfs_log_trace("Entering.\n");
}
{
if (ntfs_icx_parent_dec(icx))
return STATUS_ERROR;
return STATUS_ERROR;
else {
if (!ib)
return STATUS_ERROR;
goto out;
}
if (!ntfs_ie_end(ie)) {
goto out;
}
if (ntfs_ih_zero_entry(parent_ih)) {
goto ok;
}
goto out;
}
goto out;
ok:
out:
return ret;
}
{
int entry_pos;
ntfs_log_trace("Entering.\n");
return STATUS_ERROR;
}
if (!ib)
return STATUS_ERROR;
goto out;
if (ntfs_icx_parent_inc(icx))
goto out;
goto descend;
errno = EOPNOTSUPP;
ntfs_log_perror("Failed to find any entry in an index block. "
"Please run chkdsk.");
goto out;
}
if (!ie)
goto out;
if (ntfs_ie_add_vcn(&ie))
goto out2;
if (icx->is_in_root)
else
if (delta > 0) {
if (icx->is_in_root) {
errno = EOPNOTSUPP;
ntfs_log_perror("Denied to truncate INDEX_ROOT"
" during entry removal");
goto out2;
}
errno = EOPNOTSUPP;
ntfs_log_perror("Denied to split INDEX_BLOCK during "
"entry removal");
goto out2;
}
}
if (icx->is_in_root) {
goto out2;
} else
if (ntfs_icx_ib_write(icx))
goto out2;
if (ntfs_index_rm_leaf(icx))
goto out2;
} else
goto out2;
out2:
out:
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.
*/
{
int err;
ntfs_log_trace("Entering.\n");
ntfs_log_error("Invalid arguments.\n");
goto err_out;
}
if (icx->is_in_root)
else
if (ntfs_index_rm_node(icx))
goto err_out;
if (icx->is_in_root) {
goto err_out;
} else
if (ntfs_icx_ib_write(icx))
goto err_out;
} else {
if (ntfs_index_rm_leaf(icx))
goto err_out;
}
ntfs_log_trace("Done.\n");
return 0;
ntfs_log_trace("Failed.\n");
return -1;
}
/**
* 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.
*/
{
return NULL;
if (!root)
goto out;
out:
return root;
}