a1d312de7780e (Thomas Gleixner 2019-05-22 09:51:42 +0200 1) // SPDX-License-Identifier: GPL-2.0-or-later
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 2) /*
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 3) * index.c - NTFS kernel index handling. Part of the Linux-NTFS project.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 4) *
442d207eb0b4e (Anton Altaparmakov 2005-05-27 16:42:56 +0100 5) * Copyright (c) 2004-2005 Anton Altaparmakov
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 6) */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 7)
5a0e3ad6af866 (Tejun Heo 2010-03-24 17:04:11 +0900 8) #include <linux/slab.h>
5a0e3ad6af866 (Tejun Heo 2010-03-24 17:04:11 +0900 9)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 10) #include "aops.h"
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 11) #include "collate.h"
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 12) #include "debug.h"
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 13) #include "index.h"
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 14) #include "ntfs.h"
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 15)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 16) /**
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 17) * ntfs_index_ctx_get - allocate and initialize a new index context
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 18) * @idx_ni: ntfs index inode with which to initialize the context
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 19) *
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 20) * Allocate a new index context, initialize it with @idx_ni and return it.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 21) * Return NULL if allocation failed.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 22) *
1b1dcc1b57a49 (Jes Sorensen 2006-01-09 15:59:24 -0800 23) * Locking: Caller must hold i_mutex on the index inode.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 24) */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 25) ntfs_index_context *ntfs_index_ctx_get(ntfs_inode *idx_ni)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 26) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 27) ntfs_index_context *ictx;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 28)
e6b4f8da3a884 (Christoph Lameter 2006-12-06 20:33:14 -0800 29) ictx = kmem_cache_alloc(ntfs_index_ctx_cache, GFP_NOFS);
442d207eb0b4e (Anton Altaparmakov 2005-05-27 16:42:56 +0100 30) if (ictx)
442d207eb0b4e (Anton Altaparmakov 2005-05-27 16:42:56 +0100 31) *ictx = (ntfs_index_context){ .idx_ni = idx_ni };
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 32) return ictx;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 33) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 34)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 35) /**
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 36) * ntfs_index_ctx_put - release an index context
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 37) * @ictx: index context to free
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 38) *
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 39) * Release the index context @ictx, releasing all associated resources.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 40) *
1b1dcc1b57a49 (Jes Sorensen 2006-01-09 15:59:24 -0800 41) * Locking: Caller must hold i_mutex on the index inode.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 42) */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 43) void ntfs_index_ctx_put(ntfs_index_context *ictx)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 44) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 45) if (ictx->entry) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 46) if (ictx->is_in_root) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 47) if (ictx->actx)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 48) ntfs_attr_put_search_ctx(ictx->actx);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 49) if (ictx->base_ni)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 50) unmap_mft_record(ictx->base_ni);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 51) } else {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 52) struct page *page = ictx->page;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 53) if (page) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 54) BUG_ON(!PageLocked(page));
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 55) unlock_page(page);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 56) ntfs_unmap_page(page);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 57) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 58) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 59) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 60) kmem_cache_free(ntfs_index_ctx_cache, ictx);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 61) return;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 62) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 63)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 64) /**
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 65) * ntfs_index_lookup - find a key in an index and return its index entry
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 66) * @key: [IN] key for which to search in the index
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 67) * @key_len: [IN] length of @key in bytes
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 68) * @ictx: [IN/OUT] context describing the index and the returned entry
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 69) *
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 70) * Before calling ntfs_index_lookup(), @ictx must have been obtained from a
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 71) * call to ntfs_index_ctx_get().
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 72) *
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 73) * Look for the @key in the index specified by the index lookup context @ictx.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 74) * ntfs_index_lookup() walks the contents of the index looking for the @key.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 75) *
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 76) * If the @key is found in the index, 0 is returned and @ictx is setup to
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 77) * describe the index entry containing the matching @key. @ictx->entry is the
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 78) * index entry and @ictx->data and @ictx->data_len are the index entry data and
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 79) * its length in bytes, respectively.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 80) *
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 81) * If the @key is not found in the index, -ENOENT is returned and @ictx is
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 82) * setup to describe the index entry whose key collates immediately after the
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 83) * search @key, i.e. this is the position in the index at which an index entry
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 84) * with a key of @key would need to be inserted.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 85) *
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 86) * If an error occurs return the negative error code and @ictx is left
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 87) * untouched.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 88) *
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 89) * When finished with the entry and its data, call ntfs_index_ctx_put() to free
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 90) * the context and other associated resources.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 91) *
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 92) * If the index entry was modified, call flush_dcache_index_entry_page()
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 93) * immediately after the modification and either ntfs_index_entry_mark_dirty()
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 94) * or ntfs_index_entry_write() before the call to ntfs_index_ctx_put() to
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 95) * ensure that the changes are written to disk.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 96) *
1b1dcc1b57a49 (Jes Sorensen 2006-01-09 15:59:24 -0800 97) * Locking: - Caller must hold i_mutex on the index inode.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 98) * - Each page cache page in the index allocation mapping must be
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 99) * locked whilst being accessed otherwise we may find a corrupt
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 100) * page due to it being under ->writepage at the moment which
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 101) * applies the mst protection fixups before writing out and then
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 102) * removes them again after the write is complete after which it
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 103) * unlocks the page.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 104) */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 105) int ntfs_index_lookup(const void *key, const int key_len,
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 106) ntfs_index_context *ictx)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 107) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 108) VCN vcn, old_vcn;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 109) ntfs_inode *idx_ni = ictx->idx_ni;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 110) ntfs_volume *vol = idx_ni->vol;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 111) struct super_block *sb = vol->sb;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 112) ntfs_inode *base_ni = idx_ni->ext.base_ntfs_ino;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 113) MFT_RECORD *m;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 114) INDEX_ROOT *ir;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 115) INDEX_ENTRY *ie;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 116) INDEX_ALLOCATION *ia;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 117) u8 *index_end, *kaddr;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 118) ntfs_attr_search_ctx *actx;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 119) struct address_space *ia_mapping;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 120) struct page *page;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 121) int rc, err = 0;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 122)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 123) ntfs_debug("Entering.");
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 124) BUG_ON(!NInoAttr(idx_ni));
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 125) BUG_ON(idx_ni->type != AT_INDEX_ALLOCATION);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 126) BUG_ON(idx_ni->nr_extents != -1);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 127) BUG_ON(!base_ni);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 128) BUG_ON(!key);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 129) BUG_ON(key_len <= 0);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 130) if (!ntfs_is_collation_rule_supported(
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 131) idx_ni->itype.index.collation_rule)) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 132) ntfs_error(sb, "Index uses unsupported collation rule 0x%x. "
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 133) "Aborting lookup.", le32_to_cpu(
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 134) idx_ni->itype.index.collation_rule));
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 135) return -EOPNOTSUPP;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 136) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 137) /* Get hold of the mft record for the index inode. */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 138) m = map_mft_record(base_ni);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 139) if (IS_ERR(m)) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 140) ntfs_error(sb, "map_mft_record() failed with error code %ld.",
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 141) -PTR_ERR(m));
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 142) return PTR_ERR(m);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 143) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 144) actx = ntfs_attr_get_search_ctx(base_ni, m);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 145) if (unlikely(!actx)) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 146) err = -ENOMEM;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 147) goto err_out;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 148) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 149) /* Find the index root attribute in the mft record. */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 150) err = ntfs_attr_lookup(AT_INDEX_ROOT, idx_ni->name, idx_ni->name_len,
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 151) CASE_SENSITIVE, 0, NULL, 0, actx);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 152) if (unlikely(err)) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 153) if (err == -ENOENT) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 154) ntfs_error(sb, "Index root attribute missing in inode "
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 155) "0x%lx.", idx_ni->mft_no);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 156) err = -EIO;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 157) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 158) goto err_out;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 159) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 160) /* Get to the index root value (it has been verified in read_inode). */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 161) ir = (INDEX_ROOT*)((u8*)actx->attr +
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 162) le16_to_cpu(actx->attr->data.resident.value_offset));
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 163) index_end = (u8*)&ir->index + le32_to_cpu(ir->index.index_length);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 164) /* The first index entry. */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 165) ie = (INDEX_ENTRY*)((u8*)&ir->index +
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 166) le32_to_cpu(ir->index.entries_offset));
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 167) /*
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 168) * Loop until we exceed valid memory (corruption case) or until we
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 169) * reach the last entry.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 170) */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 171) for (;; ie = (INDEX_ENTRY*)((u8*)ie + le16_to_cpu(ie->length))) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 172) /* Bounds checks. */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 173) if ((u8*)ie < (u8*)actx->mrec || (u8*)ie +
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 174) sizeof(INDEX_ENTRY_HEADER) > index_end ||
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 175) (u8*)ie + le16_to_cpu(ie->length) > index_end)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 176) goto idx_err_out;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 177) /*
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 178) * The last entry cannot contain a key. It can however contain
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 179) * a pointer to a child node in the B+tree so we just break out.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 180) */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 181) if (ie->flags & INDEX_ENTRY_END)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 182) break;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 183) /* Further bounds checks. */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 184) if ((u32)sizeof(INDEX_ENTRY_HEADER) +
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 185) le16_to_cpu(ie->key_length) >
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 186) le16_to_cpu(ie->data.vi.data_offset) ||
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 187) (u32)le16_to_cpu(ie->data.vi.data_offset) +
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 188) le16_to_cpu(ie->data.vi.data_length) >
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 189) le16_to_cpu(ie->length))
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 190) goto idx_err_out;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 191) /* If the keys match perfectly, we setup @ictx and return 0. */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 192) if ((key_len == le16_to_cpu(ie->key_length)) && !memcmp(key,
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 193) &ie->key, key_len)) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 194) ir_done:
c49c31115067b (Richard Knutsson 2006-09-30 23:27:12 -0700 195) ictx->is_in_root = true;
8e08ceaeacd5d (Anton Altaparmakov 2005-09-08 20:29:50 +0100 196) ictx->ir = ir;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 197) ictx->actx = actx;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 198) ictx->base_ni = base_ni;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 199) ictx->ia = NULL;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 200) ictx->page = NULL;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 201) done:
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 202) ictx->entry = ie;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 203) ictx->data = (u8*)ie +
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 204) le16_to_cpu(ie->data.vi.data_offset);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 205) ictx->data_len = le16_to_cpu(ie->data.vi.data_length);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 206) ntfs_debug("Done.");
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 207) return err;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 208) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 209) /*
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 210) * Not a perfect match, need to do full blown collation so we
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 211) * know which way in the B+tree we have to go.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 212) */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 213) rc = ntfs_collate(vol, idx_ni->itype.index.collation_rule, key,
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 214) key_len, &ie->key, le16_to_cpu(ie->key_length));
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 215) /*
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 216) * If @key collates before the key of the current entry, there
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 217) * is definitely no such key in this index but we might need to
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 218) * descend into the B+tree so we just break out of the loop.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 219) */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 220) if (rc == -1)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 221) break;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 222) /*
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 223) * A match should never happen as the memcmp() call should have
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 224) * cought it, but we still treat it correctly.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 225) */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 226) if (!rc)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 227) goto ir_done;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 228) /* The keys are not equal, continue the search. */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 229) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 230) /*
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 231) * We have finished with this index without success. Check for the
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 232) * presence of a child node and if not present setup @ictx and return
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 233) * -ENOENT.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 234) */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 235) if (!(ie->flags & INDEX_ENTRY_NODE)) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 236) ntfs_debug("Entry not found.");
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 237) err = -ENOENT;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 238) goto ir_done;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 239) } /* Child node present, descend into it. */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 240) /* Consistency check: Verify that an index allocation exists. */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 241) if (!NInoIndexAllocPresent(idx_ni)) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 242) ntfs_error(sb, "No index allocation attribute but index entry "
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 243) "requires one. Inode 0x%lx is corrupt or "
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 244) "driver bug.", idx_ni->mft_no);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 245) goto err_out;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 246) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 247) /* Get the starting vcn of the index_block holding the child node. */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 248) vcn = sle64_to_cpup((sle64*)((u8*)ie + le16_to_cpu(ie->length) - 8));
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 249) ia_mapping = VFS_I(idx_ni)->i_mapping;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 250) /*
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 251) * We are done with the index root and the mft record. Release them,
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 252) * otherwise we deadlock with ntfs_map_page().
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 253) */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 254) ntfs_attr_put_search_ctx(actx);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 255) unmap_mft_record(base_ni);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 256) m = NULL;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 257) actx = NULL;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 258) descend_into_child_node:
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 259) /*
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 260) * Convert vcn to index into the index allocation attribute in units
ea1754a084760 (Kirill A. Shutemov 2016-04-01 15:29:48 +0300 261) * of PAGE_SIZE and map the page cache page, reading it from
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 262) * disk if necessary.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 263) */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 264) page = ntfs_map_page(ia_mapping, vcn <<
09cbfeaf1a5a6 (Kirill A. Shutemov 2016-04-01 15:29:47 +0300 265) idx_ni->itype.index.vcn_size_bits >> PAGE_SHIFT);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 266) if (IS_ERR(page)) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 267) ntfs_error(sb, "Failed to map index page, error %ld.",
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 268) -PTR_ERR(page));
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 269) err = PTR_ERR(page);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 270) goto err_out;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 271) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 272) lock_page(page);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 273) kaddr = (u8*)page_address(page);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 274) fast_descend_into_child_node:
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 275) /* Get to the index allocation block. */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 276) ia = (INDEX_ALLOCATION*)(kaddr + ((vcn <<
09cbfeaf1a5a6 (Kirill A. Shutemov 2016-04-01 15:29:47 +0300 277) idx_ni->itype.index.vcn_size_bits) & ~PAGE_MASK));
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 278) /* Bounds checks. */
09cbfeaf1a5a6 (Kirill A. Shutemov 2016-04-01 15:29:47 +0300 279) if ((u8*)ia < kaddr || (u8*)ia > kaddr + PAGE_SIZE) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 280) ntfs_error(sb, "Out of bounds check failed. Corrupt inode "
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 281) "0x%lx or driver bug.", idx_ni->mft_no);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 282) goto unm_err_out;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 283) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 284) /* Catch multi sector transfer fixup errors. */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 285) if (unlikely(!ntfs_is_indx_record(ia->magic))) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 286) ntfs_error(sb, "Index record with vcn 0x%llx is corrupt. "
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 287) "Corrupt inode 0x%lx. Run chkdsk.",
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 288) (long long)vcn, idx_ni->mft_no);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 289) goto unm_err_out;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 290) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 291) if (sle64_to_cpu(ia->index_block_vcn) != vcn) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 292) ntfs_error(sb, "Actual VCN (0x%llx) of index buffer is "
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 293) "different from expected VCN (0x%llx). Inode "
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 294) "0x%lx is corrupt or driver bug.",
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 295) (unsigned long long)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 296) sle64_to_cpu(ia->index_block_vcn),
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 297) (unsigned long long)vcn, idx_ni->mft_no);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 298) goto unm_err_out;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 299) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 300) if (le32_to_cpu(ia->index.allocated_size) + 0x18 !=
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 301) idx_ni->itype.index.block_size) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 302) ntfs_error(sb, "Index buffer (VCN 0x%llx) of inode 0x%lx has "
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 303) "a size (%u) differing from the index "
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 304) "specified size (%u). Inode is corrupt or "
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 305) "driver bug.", (unsigned long long)vcn,
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 306) idx_ni->mft_no,
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 307) le32_to_cpu(ia->index.allocated_size) + 0x18,
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 308) idx_ni->itype.index.block_size);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 309) goto unm_err_out;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 310) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 311) index_end = (u8*)ia + idx_ni->itype.index.block_size;
09cbfeaf1a5a6 (Kirill A. Shutemov 2016-04-01 15:29:47 +0300 312) if (index_end > kaddr + PAGE_SIZE) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 313) ntfs_error(sb, "Index buffer (VCN 0x%llx) of inode 0x%lx "
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 314) "crosses page boundary. Impossible! Cannot "
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 315) "access! This is probably a bug in the "
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 316) "driver.", (unsigned long long)vcn,
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 317) idx_ni->mft_no);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 318) goto unm_err_out;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 319) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 320) index_end = (u8*)&ia->index + le32_to_cpu(ia->index.index_length);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 321) if (index_end > (u8*)ia + idx_ni->itype.index.block_size) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 322) ntfs_error(sb, "Size of index buffer (VCN 0x%llx) of inode "
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 323) "0x%lx exceeds maximum size.",
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 324) (unsigned long long)vcn, idx_ni->mft_no);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 325) goto unm_err_out;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 326) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 327) /* The first index entry. */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 328) ie = (INDEX_ENTRY*)((u8*)&ia->index +
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 329) le32_to_cpu(ia->index.entries_offset));
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 330) /*
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 331) * Iterate similar to above big loop but applied to index buffer, thus
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 332) * loop until we exceed valid memory (corruption case) or until we
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 333) * reach the last entry.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 334) */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 335) for (;; ie = (INDEX_ENTRY*)((u8*)ie + le16_to_cpu(ie->length))) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 336) /* Bounds checks. */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 337) if ((u8*)ie < (u8*)ia || (u8*)ie +
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 338) sizeof(INDEX_ENTRY_HEADER) > index_end ||
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 339) (u8*)ie + le16_to_cpu(ie->length) > index_end) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 340) ntfs_error(sb, "Index entry out of bounds in inode "
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 341) "0x%lx.", idx_ni->mft_no);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 342) goto unm_err_out;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 343) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 344) /*
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 345) * The last entry cannot contain a key. It can however contain
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 346) * a pointer to a child node in the B+tree so we just break out.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 347) */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 348) if (ie->flags & INDEX_ENTRY_END)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 349) break;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 350) /* Further bounds checks. */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 351) if ((u32)sizeof(INDEX_ENTRY_HEADER) +
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 352) le16_to_cpu(ie->key_length) >
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 353) le16_to_cpu(ie->data.vi.data_offset) ||
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 354) (u32)le16_to_cpu(ie->data.vi.data_offset) +
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 355) le16_to_cpu(ie->data.vi.data_length) >
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 356) le16_to_cpu(ie->length)) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 357) ntfs_error(sb, "Index entry out of bounds in inode "
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 358) "0x%lx.", idx_ni->mft_no);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 359) goto unm_err_out;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 360) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 361) /* If the keys match perfectly, we setup @ictx and return 0. */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 362) if ((key_len == le16_to_cpu(ie->key_length)) && !memcmp(key,
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 363) &ie->key, key_len)) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 364) ia_done:
c49c31115067b (Richard Knutsson 2006-09-30 23:27:12 -0700 365) ictx->is_in_root = false;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 366) ictx->actx = NULL;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 367) ictx->base_ni = NULL;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 368) ictx->ia = ia;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 369) ictx->page = page;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 370) goto done;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 371) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 372) /*
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 373) * Not a perfect match, need to do full blown collation so we
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 374) * know which way in the B+tree we have to go.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 375) */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 376) rc = ntfs_collate(vol, idx_ni->itype.index.collation_rule, key,
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 377) key_len, &ie->key, le16_to_cpu(ie->key_length));
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 378) /*
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 379) * If @key collates before the key of the current entry, there
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 380) * is definitely no such key in this index but we might need to
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 381) * descend into the B+tree so we just break out of the loop.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 382) */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 383) if (rc == -1)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 384) break;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 385) /*
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 386) * A match should never happen as the memcmp() call should have
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 387) * cought it, but we still treat it correctly.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 388) */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 389) if (!rc)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 390) goto ia_done;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 391) /* The keys are not equal, continue the search. */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 392) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 393) /*
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 394) * We have finished with this index buffer without success. Check for
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 395) * the presence of a child node and if not present return -ENOENT.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 396) */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 397) if (!(ie->flags & INDEX_ENTRY_NODE)) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 398) ntfs_debug("Entry not found.");
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 399) err = -ENOENT;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 400) goto ia_done;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 401) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 402) if ((ia->index.flags & NODE_MASK) == LEAF_NODE) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 403) ntfs_error(sb, "Index entry with child node found in a leaf "
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 404) "node in inode 0x%lx.", idx_ni->mft_no);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 405) goto unm_err_out;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 406) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 407) /* Child node present, descend into it. */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 408) old_vcn = vcn;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 409) vcn = sle64_to_cpup((sle64*)((u8*)ie + le16_to_cpu(ie->length) - 8));
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 410) if (vcn >= 0) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 411) /*
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 412) * If vcn is in the same page cache page as old_vcn we recycle
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 413) * the mapped page.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 414) */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 415) if (old_vcn << vol->cluster_size_bits >>
09cbfeaf1a5a6 (Kirill A. Shutemov 2016-04-01 15:29:47 +0300 416) PAGE_SHIFT == vcn <<
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 417) vol->cluster_size_bits >>
09cbfeaf1a5a6 (Kirill A. Shutemov 2016-04-01 15:29:47 +0300 418) PAGE_SHIFT)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 419) goto fast_descend_into_child_node;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 420) unlock_page(page);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 421) ntfs_unmap_page(page);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 422) goto descend_into_child_node;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 423) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 424) ntfs_error(sb, "Negative child node vcn in inode 0x%lx.",
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 425) idx_ni->mft_no);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 426) unm_err_out:
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 427) unlock_page(page);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 428) ntfs_unmap_page(page);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 429) err_out:
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 430) if (!err)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 431) err = -EIO;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 432) if (actx)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 433) ntfs_attr_put_search_ctx(actx);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 434) if (m)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 435) unmap_mft_record(base_ni);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 436) return err;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 437) idx_err_out:
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 438) ntfs_error(sb, "Corrupt index. Aborting lookup.");
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 439) goto err_out;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 440) }
VisionFive2 Linux kernel
StarFive Tech Linux Kernel for VisionFive (JH7110) boards (mirror)
More than 9999 Commits
32 Branches
54 Tags