1N/A * index.c - NTFS index handling. Part of the Linux-NTFS project. 1N/A * Copyright (c) 2004-2005 Anton Altaparmakov 1N/A * Copyright (c) 2004-2005 Richard Russon 1N/A * Copyright (c) 2005-2007 Yura Pakhuchiy 1N/A * Copyright (c) 2005-2006 Szabolcs Szakacsits 1N/A * modify it under the terms of the GNU General Public License as published 1N/A * by the Free Software Foundation; either version 2 of the License, or 1N/A * (at your option) any later version. 1N/A * useful, but WITHOUT ANY WARRANTY; without even the implied warranty 1N/A * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1N/A * GNU General Public License for more details. 1N/A * You should have received a copy of the GNU General Public License 1N/A * along with this program (in the main directory of the Linux-NTFS 1N/A * distribution in the file COPYING); if not, write to the Free Software 1N/A * Foundation,Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 1N/A * ntfs_index_entry_mark_dirty - mark an index entry dirty 1N/A * @ictx: ntfs index context describing the index entry 1N/A * Mark the index entry described by the index entry context @ictx dirty. 1N/A * If the index entry is in the index root attribute, simply mark the inode 1N/A * containing the index root attribute dirty. This ensures the mftrecord, and 1N/A * hence the index root attribute, will be written out to disk later. 1N/A * If the index entry is in an index block belonging to the index allocation 1N/A * attribute, set ib_dirty to TRUE, thus index block will be updated during 1N/A * ntfs_index_ctx_put. 1N/A * ntfs_index_ctx_get - allocate and initialize a new index context 1N/A * @ni: ntfs inode with which to initialize the context 1N/A * @name: name of the which context describes 1N/A * @name_len: length of the index name 1N/A * Allocate a new index context, initialize it with @ni and return it. 1N/A * Return NULL if allocation failed. 1N/A /* FIXME: Error handling!!! */ 1N/A * ntfs_index_ctx_put - release an index context 1N/A * @icx: index context to free 1N/A * Release the index context @icx, releasing all associated resources. 1N/A * ntfs_index_ctx_reinit - reinitialize an index context 1N/A * @icx: index context to reinitialize 1N/A * Reinitialize the index context @icx so it can be used for ntfs_index_lookup. 1N/A * Get the subnode vcn to which the index entry refers. 1N/A /* FIXME: check if it isn't overflowing the index block size */ 1N/A * Find the last entry in the index block 1N/A * Insert @ie index entry at @pos entry. Used @ih values should be ok already. 1N/A "from expected VCN (%lld) in inode %llu\n",
1N/A "has a size (%u) differing from the index " 1N/A "specified size (%u)\n", (
long long)
vcn,
1N/A * Find a key in the index block. 1N/A * STATUS_OK with errno set to ESUCCESS if we know for sure that the 1N/A * entry exists and @ie_out points to this entry. 1N/A * STATUS_NOT_FOUND with errno set to ENOENT if we know for sure the 1N/A * entry doesn't exist and @ie_out is the insertion point. 1N/A * STATUS_KEEP_SEARCHING if we can't answer the above question and 1N/A * @vcn will contain the node index block. 1N/A * STATUS_ERROR with errno set if on unexpected error during lookup. 1N/A * Loop until we exceed valid memory (corruption case) or until we 1N/A * reach the last entry. 1N/A /* Bounds checks. */ 1N/A * The last entry cannot contain a key. It can however contain 1N/A * a pointer to a child node in the B+tree so we just break out. 1N/A * Not a perfect match, need to do full blown collation so we 1N/A * know which way in the B+tree we have to go. 1N/A "contains invalid characters?\n");
1N/A * If @key collates before the key of the current entry, there 1N/A * is definitely no such key in this index but we might need to 1N/A * descend into the B+tree so we just break out of the loop. 1N/A * We have finished with this index block without success. Check for the 1N/A * presence of a child node and if not present return with errno ENOENT, 1N/A * otherwise we will keep searching in another index block. 1N/A /* Get the starting vcn of the index_block holding the child node. */ 1N/A * ntfs_index_lookup - find a key in an index and return its index entry 1N/A * @key: [IN] key for which to search in the index 1N/A * @key_len: [IN] length of @key in bytes 1N/A * @icx: [IN/OUT] context describing the index and the returned entry 1N/A * Before calling ntfs_index_lookup(), @icx must have been obtained from a 1N/A * call to ntfs_index_ctx_get(). 1N/A * Look for the @key in the index specified by the index lookup context @icx. 1N/A * ntfs_index_lookup() walks the contents of the index looking for the @key. 1N/A * If the @key is found in the index, 0 is returned and @icx is setup to 1N/A * describe the index entry containing the matching @key. @icx->entry is the 1N/A * index entry and @icx->data and @icx->data_len are the index entry data and 1N/A * its length in bytes, respectively. 1N/A * If the @key is not found in the index, -1 is returned, errno = ENOENT and 1N/A * @icx is setup to describe the index entry whose key collates immediately 1N/A * after the search @key, i.e. this is the position in the index at which 1N/A * an index entry with a key of @key would need to be inserted. 1N/A * If an error occurs return -1, set errno to error code and @icx is left 1N/A * When finished with the entry and its data, call ntfs_index_ctx_put() to free 1N/A * the context and other associated resources. 1N/A * If the index entry was modified, call ntfs_index_entry_mark_dirty() before 1N/A * the call to ntfs_index_ctx_put() to ensure that the changes are written 1N/A * FIXME: check for both ir and ib that the first index entry is 1N/A * within the index block. 1N/A /* STATUS_OK or STATUS_NOT_FOUND */ 1N/A /* Child node present, descend into it. */ 1N/A /* STATUS_OK or STATUS_NOT_FOUND */ 1N/A "node in inode 0x%llx.\n",
1N/A * Find the median by going through all the entries 1N/A * NOTE: this could be also the entry at the half of the index block. 1N/A * AT_BITMAP must be at least 8 bytes. 1N/A * Copy all entries, including the termination entry 1N/A * as well, which can never have any data. 1N/A /* TODO: This function could be much simpler. */ 1N/A /* Move the index root termination entry forward. */ 1N/A /* FIXME: revert bitmap, index root */ 1N/A * ntfs_ir_truncate - Truncate index root attribute 1N/A * Returns STATUS_OK, STATUS_RESIDENT_ATTRIBUTE_FILLED_MFT or STATUS_ERROR. 1N/A * INDEX_ROOT must be resident and its entries can be moved to 1N/A * INDEX_BLOCK, so ENOSPC isn't a real error. 1N/A * ntfs_ir_make_space - Make more space for the index root attribute 1N/A * On success return STATUS_OK or STATUS_KEEP_SEARCHING. 1N/A * On error return STATUS_ERROR. 1N/A * NOTE: 'ie' must be a copy of a real index entry. 1N/A * ntfs_ib_insert - insert an index block to an index context. 1N/A * On success return STATUS_OK or STATUS_KEEP_SEARCHING. 1N/A * On error return STATUS_ERROR. 1N/A /* FIXME: sizeof(VCN) should be included only if ie has no VCN */ 1N/A * ntfs_ib_split - Split index allocation attribute 1N/A * On success return STATUS_OK or STATUS_KEEP_SEARCHING. 1N/A * On error return is STATUS_ERROR. 1N/A * ntfs_index_add_filename - add filename to directory index 1N/A * @ni: ntfs inode describing directory to which index add filename 1N/A * @fn: FILE_NAME attribute to add 1N/A * @mref: reference of the inode which @fn describes 1N/A * Return 0 on success or -1 on error with errno set to the error code. 1N/A * Used if an empty index block to be deleted has END entry as the parent 1N/A * in the INDEX_ROOT which is the only one there. 1N/A /* Not fatal error */ 1N/A * ntfs_ih_reparent_end - 1N/A * Used if an empty index block to be deleted has END entry as the parent 1N/A * in the INDEX_ROOT which is not the only one there. 1N/A "Please run chkdsk.");
1N/A " during entry removal");
1N/A * ntfs_index_rm - remove entry from the index 1N/A * @icx: index context describing entry to delete 1N/A * Delete entry described by @icx from the index. Index context is always 1N/A * reinitialized after use of this function, so it can be used for index 1N/A * lookup once again. 1N/A * Return 0 on success or -1 on error with errno set to the error code. 1N/A * ntfs_index_root_get - read the index root of an attribute 1N/A * @ni: open ntfs inode in which the ntfs attribute resides 1N/A * @attr: attribute for which we want its index root 1N/A * This function will read the related index root an ntfs attribute. 1N/A * On success a buffer is allocated with the content of the index root 1N/A * and which needs to be freed when it's not needed anymore. 1N/A * On error NULL is returned with errno set to the error code.