summaryrefslogtreecommitdiffstats
path: root/fs/ntfs/index.c
diff options
context:
space:
mode:
Diffstat (limited to 'fs/ntfs/index.c')
-rw-r--r--fs/ntfs/index.c2297
1 files changed, 2297 insertions, 0 deletions
diff --git a/fs/ntfs/index.c b/fs/ntfs/index.c
new file mode 100644
index 000000000..580998990
--- /dev/null
+++ b/fs/ntfs/index.c
@@ -0,0 +1,2297 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ * NTFS kernel index handling.
+ *
+ * Copyright (c) 2004-2005 Anton Altaparmakov
+ * Copyright (c) 2025 LG Electronics Co., Ltd.
+ *
+ * Part of this file is based on code from the NTFS-3G.
+ * and is copyrighted by the respective authors below:
+ * 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
+ */
+
+#include "collate.h"
+#include "index.h"
+#include "ntfs.h"
+#include "attrlist.h"
+
+/*
+ * ntfs_index_entry_inconsistent - 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.
+ */
+static int ntfs_index_entry_inconsistent(const struct ntfs_volume *vol,
+ const struct index_entry *ie,
+ __le32 collation_rule, u64 inum)
+{
+ if (ie->key_length &&
+ ((le16_to_cpu(ie->key_length) + offsetof(struct index_entry, key)) >
+ le16_to_cpu(ie->length))) {
+ ntfs_error(vol->sb, "Overflow from index entry in inode %lld\n",
+ (long long)inum);
+ return -EIO;
+
+ } else {
+ if (collation_rule == COLLATION_FILE_NAME) {
+ if ((offsetof(struct index_entry, key.file_name.file_name) +
+ ie->key.file_name.file_name_length * sizeof(__le16)) >
+ le16_to_cpu(ie->length)) {
+ ntfs_error(vol->sb,
+ "File name overflow from index entry in inode %lld\n",
+ (long long)inum);
+ return -EIO;
+ }
+ } else {
+ if (ie->data.vi.data_length &&
+ ((le16_to_cpu(ie->data.vi.data_offset) +
+ le16_to_cpu(ie->data.vi.data_length)) >
+ le16_to_cpu(ie->length))) {
+ ntfs_error(vol->sb,
+ "Data overflow from index entry in inode %lld\n",
+ (long long)inum);
+ return -EIO;
+ }
+ }
+ }
+
+ return 0;
+}
+
+/*
+ * 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(struct ntfs_index_context *ictx)
+{
+ if (ictx->is_in_root)
+ mark_mft_record_dirty(ictx->actx->ntfs_ino);
+ else if (ictx->ib)
+ ictx->ib_dirty = true;
+}
+
+static s64 ntfs_ib_vcn_to_pos(struct ntfs_index_context *icx, s64 vcn)
+{
+ return vcn << icx->vcn_size_bits;
+}
+
+static s64 ntfs_ib_pos_to_vcn(struct ntfs_index_context *icx, s64 pos)
+{
+ return pos >> icx->vcn_size_bits;
+}
+
+static int ntfs_ib_write(struct ntfs_index_context *icx, struct index_block *ib)
+{
+ s64 ret, vcn = le64_to_cpu(ib->index_block_vcn);
+
+ ntfs_debug("vcn: %lld\n", vcn);
+
+ ret = pre_write_mst_fixup((struct ntfs_record *)ib, icx->block_size);
+ if (ret)
+ return -EIO;
+
+ ret = ntfs_inode_attr_pwrite(VFS_I(icx->ia_ni),
+ ntfs_ib_vcn_to_pos(icx, vcn), icx->block_size,
+ (u8 *)ib, icx->sync_write);
+
+ /* Perform data restoration before returning */
+ post_write_mst_fixup((struct ntfs_record *)ib);
+
+ if (ret != icx->block_size) {
+ ntfs_debug("Failed to write index block %lld, inode %llu",
+ vcn, (unsigned long long)icx->idx_ni->mft_no);
+ return ret;
+ }
+
+ return 0;
+}
+
+static int ntfs_icx_ib_write(struct ntfs_index_context *icx)
+{
+ int err;
+
+ err = ntfs_ib_write(icx, icx->ib);
+ if (err)
+ return err;
+
+ icx->ib_dirty = false;
+
+ return 0;
+}
+
+int ntfs_icx_ib_sync_write(struct ntfs_index_context *icx)
+{
+ int ret;
+
+ if (icx->ib_dirty == false)
+ return 0;
+
+ icx->sync_write = true;
+
+ ret = ntfs_ib_write(icx, icx->ib);
+ if (!ret) {
+ kvfree(icx->ib);
+ icx->ib = NULL;
+ icx->ib_dirty = false;
+ } else {
+ icx->sync_write = false;
+ }
+
+ return ret;
+}
+
+/*
+ * 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.
+ */
+struct ntfs_index_context *ntfs_index_ctx_get(struct ntfs_inode *ni,
+ __le16 *name, u32 name_len)
+{
+ struct ntfs_index_context *icx;
+
+ ntfs_debug("Entering\n");
+
+ if (!ni)
+ return NULL;
+
+ if (ni->nr_extents == -1)
+ ni = ni->ext.base_ntfs_ino;
+
+ icx = kmem_cache_alloc(ntfs_index_ctx_cache, GFP_NOFS);
+ if (icx)
+ *icx = (struct ntfs_index_context) {
+ .idx_ni = ni,
+ .name = name,
+ .name_len = name_len,
+ };
+ return icx;
+}
+
+static void ntfs_index_ctx_free(struct ntfs_index_context *icx)
+{
+ ntfs_debug("Entering\n");
+
+ if (icx->actx) {
+ ntfs_attr_put_search_ctx(icx->actx);
+ icx->actx = NULL;
+ }
+
+ if (!icx->is_in_root) {
+ if (icx->ib_dirty)
+ ntfs_ib_write(icx, icx->ib);
+ kvfree(icx->ib);
+ icx->ib = NULL;
+ }
+
+ if (icx->ia_ni) {
+ iput(VFS_I(icx->ia_ni));
+ icx->ia_ni = NULL;
+ }
+}
+
+/*
+ * 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(struct ntfs_index_context *icx)
+{
+ ntfs_index_ctx_free(icx);
+ kmem_cache_free(ntfs_index_ctx_cache, 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(struct ntfs_index_context *icx)
+{
+ ntfs_debug("Entering\n");
+
+ ntfs_index_ctx_free(icx);
+
+ *icx = (struct ntfs_index_context) {
+ .idx_ni = icx->idx_ni,
+ .name = icx->name,
+ .name_len = icx->name_len,
+ };
+}
+
+static __le64 *ntfs_ie_get_vcn_addr(struct index_entry *ie)
+{
+ return (__le64 *)((u8 *)ie + le16_to_cpu(ie->length) - sizeof(s64));
+}
+
+/*
+ * Get the subnode vcn to which the index entry refers.
+ */
+static s64 ntfs_ie_get_vcn(struct index_entry *ie)
+{
+ return le64_to_cpup(ntfs_ie_get_vcn_addr(ie));
+}
+
+static struct index_entry *ntfs_ie_get_first(struct index_header *ih)
+{
+ return (struct index_entry *)((u8 *)ih + le32_to_cpu(ih->entries_offset));
+}
+
+static struct index_entry *ntfs_ie_get_next(struct index_entry *ie)
+{
+ return (struct index_entry *)((char *)ie + le16_to_cpu(ie->length));
+}
+
+static u8 *ntfs_ie_get_end(struct index_header *ih)
+{
+ return (u8 *)ih + le32_to_cpu(ih->index_length);
+}
+
+static int ntfs_ie_end(struct index_entry *ie)
+{
+ return ie->flags & INDEX_ENTRY_END || !ie->length;
+}
+
+static int ntfs_index_header_inconsistent(struct ntfs_volume *vol,
+ const struct index_header *ih,
+ u32 bytes_available, u64 inum)
+{
+ u32 entries_offset, index_length, allocated_size;
+
+ if (bytes_available < sizeof(struct index_header)) {
+ ntfs_error(vol->sb,
+ "index block in inode %llu is smaller than an index header.",
+ (unsigned long long)inum);
+ return -EIO;
+ }
+
+ entries_offset = le32_to_cpu(ih->entries_offset);
+ index_length = le32_to_cpu(ih->index_length);
+ allocated_size = le32_to_cpu(ih->allocated_size);
+
+ if (entries_offset < sizeof(struct index_header) ||
+ entries_offset > bytes_available) {
+ ntfs_error(vol->sb,
+ "Invalid index entry offset in inode %llu.",
+ (unsigned long long)inum);
+ return -EIO;
+ }
+
+ if (index_length <= entries_offset) {
+ ntfs_error(vol->sb,
+ "No space for index entries in inode %llu.",
+ (unsigned long long)inum);
+ return -EIO;
+ }
+
+ if (allocated_size < index_length) {
+ ntfs_error(vol->sb,
+ "Index entries overflow in inode %llu.",
+ (unsigned long long)inum);
+ return -EIO;
+ }
+
+ if (allocated_size > bytes_available || index_length > bytes_available) {
+ ntfs_error(vol->sb,
+ "Index entries in inode %llu exceed the available buffer.",
+ (unsigned long long)inum);
+ return -EIO;
+ }
+
+ return 0;
+}
+
+int ntfs_index_entries_inconsistent(const struct ntfs_volume *vol,
+ const struct index_header *ih,
+ __le32 collation_rule, u64 inum)
+{
+ struct index_entry *ie;
+ u8 *index_end = (u8 *)ih + le32_to_cpu(ih->index_length);
+
+ for (ie = ntfs_ie_get_first((struct index_header *)ih);
+ ; ie = ntfs_ie_get_next(ie)) {
+ if ((u8 *)ie + sizeof(struct index_entry_header) > index_end ||
+ (u8 *)ie + le16_to_cpu(ie->length) > index_end) {
+ ntfs_error(vol->sb,
+ "Index entry out of bounds in inode %llu.",
+ (unsigned long long)inum);
+ return -EIO;
+ }
+
+ if (le16_to_cpu(ie->length) < sizeof(struct index_entry_header)) {
+ ntfs_error(vol->sb,
+ "Index entry too small in inode %llu.",
+ inum);
+ return -EIO;
+ }
+
+ if (ntfs_ie_end(ie))
+ break;
+
+ if (!ie->key_length)
+ return -EIO;
+
+ if (ntfs_index_entry_inconsistent(vol, ie,
+ collation_rule, inum))
+ return -EIO;
+ }
+
+ return 0;
+}
+
+/*
+ * Find the last entry in the index block
+ */
+static struct index_entry *ntfs_ie_get_last(struct index_entry *ie, char *ies_end)
+{
+ ntfs_debug("Entering\n");
+
+ while ((char *)ie < ies_end && !ntfs_ie_end(ie))
+ ie = ntfs_ie_get_next(ie);
+
+ return ie;
+}
+
+static struct index_entry *ntfs_ie_get_by_pos(struct index_header *ih, int pos)
+{
+ struct index_entry *ie;
+
+ ntfs_debug("pos: %d\n", pos);
+
+ ie = ntfs_ie_get_first(ih);
+
+ while (pos-- > 0)
+ ie = ntfs_ie_get_next(ie);
+
+ return ie;
+}
+
+static struct index_entry *ntfs_ie_prev(struct index_header *ih, struct index_entry *ie)
+{
+ struct index_entry *ie_prev = NULL;
+ struct index_entry *tmp;
+
+ ntfs_debug("Entering\n");
+
+ tmp = ntfs_ie_get_first(ih);
+
+ while (tmp != ie) {
+ ie_prev = tmp;
+ tmp = ntfs_ie_get_next(tmp);
+ }
+
+ return ie_prev;
+}
+
+static int ntfs_ih_numof_entries(struct index_header *ih)
+{
+ int n;
+ struct index_entry *ie;
+ u8 *end;
+
+ ntfs_debug("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(struct index_header *ih)
+{
+ return (ntfs_ih_numof_entries(ih) == 1);
+}
+
+static int ntfs_ih_zero_entry(struct index_header *ih)
+{
+ return (ntfs_ih_numof_entries(ih) == 0);
+}
+
+static void ntfs_ie_delete(struct index_header *ih, struct index_entry *ie)
+{
+ u32 new_size;
+
+ ntfs_debug("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(struct index_entry *ie, s64 vcn)
+{
+ *ntfs_ie_get_vcn_addr(ie) = cpu_to_le64(vcn);
+}
+
+/*
+ * Insert @ie index entry at @pos entry. Used @ih values should be ok already.
+ */
+static void ntfs_ie_insert(struct index_header *ih, struct index_entry *ie,
+ struct index_entry *pos)
+{
+ int ie_size = le16_to_cpu(ie->length);
+
+ ntfs_debug("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 struct index_entry *ntfs_ie_dup(struct index_entry *ie)
+{
+ ntfs_debug("Entering\n");
+
+ return kmemdup(ie, le16_to_cpu(ie->length), GFP_NOFS);
+}
+
+static struct index_entry *ntfs_ie_dup_novcn(struct index_entry *ie)
+{
+ struct index_entry *dup;
+ int size = le16_to_cpu(ie->length);
+
+ ntfs_debug("Entering\n");
+
+ if (ie->flags & INDEX_ENTRY_NODE)
+ size -= sizeof(s64);
+
+ dup = kmemdup(ie, size, GFP_NOFS);
+ if (dup) {
+ dup->flags &= ~INDEX_ENTRY_NODE;
+ dup->length = cpu_to_le16(size);
+ }
+ return dup;
+}
+
+/*
+ * 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, -EIO otherwise
+ *
+ * |<--->| offsetof(struct index_block, index)
+ * | |<--->| sizeof(struct index_header)
+ * | | |
+ * | | | seq index entries unused
+ * |=====|=====|=====|===========================|==============|
+ * | | | | |
+ * | |<--------->| entries_offset | |
+ * | |<---------------- index_length ------->| |
+ * | |<--------------------- allocated_size --------------->|
+ * |<--------------------------- block_size ------------------->|
+ *
+ * size(struct index_header) <= ent_offset < ind_length <= alloc_size < bk_size
+ */
+int ntfs_index_block_inconsistent(struct ntfs_volume *vol,
+ const struct index_block *ib,
+ u32 block_size, s64 vcn, __le32 cr,
+ u64 inum)
+{
+ u32 ib_size = (unsigned int)le32_to_cpu(ib->index.allocated_size) +
+ offsetof(struct index_block, index);
+ struct super_block *sb = vol->sb;
+
+ ntfs_debug("Entering\n");
+
+ if (!ntfs_is_indx_record(ib->magic)) {
+ ntfs_error(sb, "Corrupt index block signature: vcn %lld inode %llu\n",
+ vcn, (unsigned long long)inum);
+ return -EIO;
+ }
+
+ if (le64_to_cpu(ib->index_block_vcn) != vcn) {
+ ntfs_error(sb,
+ "Corrupt index block: s64 (%lld) is different from expected s64 (%lld) in inode %llu\n",
+ (long long)le64_to_cpu(ib->index_block_vcn),
+ vcn, inum);
+ return -EIO;
+ }
+
+ if (ib_size != block_size) {
+ ntfs_error(sb,
+ "Corrupt index block : s64 (%lld) of inode %llu has a size (%u) differing from the index specified size (%u)\n",
+ vcn, inum, ib_size, block_size);
+ return -EIO;
+ }
+
+ if (ntfs_index_header_inconsistent(vol, &ib->index,
+ block_size -
+ offsetof(struct index_block, index),
+ inum))
+ return -EIO;
+ if (ntfs_index_entries_inconsistent(vol, &ib->index, cr, inum))
+ return -EIO;
+ return 0;
+}
+
+int ntfs_index_root_inconsistent(struct ntfs_volume *vol,
+ const struct attr_record *a,
+ const struct index_root *ir, u64 inum)
+{
+ u32 value_length = le32_to_cpu(a->data.resident.value_length);
+
+ if (value_length < offsetof(struct index_root, index)) {
+ ntfs_error(vol->sb, "$INDEX_ROOT in inode %llu is too small.",
+ (unsigned long long)inum);
+ return -EIO;
+ }
+
+ return ntfs_index_header_inconsistent(vol, &ir->index,
+ value_length -
+ offsetof(struct index_root, index),
+ inum);
+}
+
+static struct index_root *ntfs_ir_lookup(struct ntfs_inode *ni, __le16 *name,
+ u32 name_len, struct ntfs_attr_search_ctx **ctx)
+{
+ struct attr_record *a;
+ struct index_root *ir = NULL;
+
+ ntfs_debug("Entering\n");
+ *ctx = ntfs_attr_get_search_ctx(ni, NULL);
+ if (!*ctx) {
+ ntfs_error(ni->vol->sb, "%s, Failed to get search context", __func__);
+ return NULL;
+ }
+
+ if (ntfs_attr_lookup(AT_INDEX_ROOT, name, name_len, CASE_SENSITIVE,
+ 0, NULL, 0, *ctx)) {
+ ntfs_error(ni->vol->sb, "Failed to lookup $INDEX_ROOT");
+ goto err_out;
+ }
+
+ a = (*ctx)->attr;
+ if (a->non_resident) {
+ ntfs_error(ni->vol->sb, "Non-resident $INDEX_ROOT detected");
+ goto err_out;
+ }
+
+ ir = (struct index_root *)((char *)a + le16_to_cpu(a->data.resident.value_offset));
+err_out:
+ if (!ir) {
+ ntfs_attr_put_search_ctx(*ctx);
+ *ctx = NULL;
+ }
+ return ir;
+}
+
+static struct index_root *ntfs_ir_lookup2(struct ntfs_inode *ni, __le16 *name, u32 len)
+{
+ struct ntfs_attr_search_ctx *ctx;
+ struct index_root *ir;
+
+ ir = ntfs_ir_lookup(ni, name, len, &ctx);
+ if (ir)
+ ntfs_attr_put_search_ctx(ctx);
+ return ir;
+}
+
+static int ntfs_ir_move_to_base(struct ntfs_index_context *icx)
+{
+ struct ntfs_attr_search_ctx *ctx = NULL;
+ struct index_root *ir;
+ bool moved = false;
+ int ret = 0;
+
+ ir = ntfs_ir_lookup(icx->idx_ni, icx->name, icx->name_len, &ctx);
+ if (!ir)
+ return -ENOENT;
+
+ if (ctx->ntfs_ino->mft_no != icx->idx_ni->mft_no) {
+ ret = ntfs_attr_record_move_to(ctx, icx->idx_ni);
+ if (!ret) {
+ moved = true;
+ ret = ntfs_attrlist_update(icx->idx_ni);
+ }
+ }
+
+ ntfs_attr_put_search_ctx(ctx);
+ if (!ret && moved)
+ ret = ntfs_inode_free_empty_extents(icx->idx_ni);
+ return ret;
+}
+
+/*
+ * Find a key in the index block.
+ */
+static int ntfs_ie_lookup(const void *key, const u32 key_len,
+ struct ntfs_index_context *icx, struct index_header *ih,
+ s64 *vcn, struct index_entry **ie_out)
+{
+ struct index_entry *ie;
+ u8 *index_end;
+ int rc, item = 0;
+
+ ntfs_debug("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(struct index_entry_header) > index_end ||
+ (u8 *)ie + le16_to_cpu(ie->length) > index_end) {
+ ntfs_error(icx->idx_ni->vol->sb,
+ "Index entry out of bounds in inode %llu.\n",
+ (unsigned long long)icx->idx_ni->mft_no);
+ return -ERANGE;
+ }
+
+ /*
+ * 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.
+ */
+ rc = ntfs_collate(icx->idx_ni->vol, icx->cr, key, key_len, &ie->key,
+ le16_to_cpu(ie->key_length));
+ if (rc == -EINVAL) {
+ ntfs_error(icx->idx_ni->vol->sb,
+ "Collation error. Perhaps a filename contains invalid characters?\n");
+ return -ERANGE;
+ }
+ /*
+ * 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;
+ icx->parent_pos[icx->pindex] = item;
+ return 0;
+ }
+
+ 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->flags & INDEX_ENTRY_NODE)) {
+ ntfs_debug("Index entry wasn't found.\n");
+ *ie_out = ie;
+ return -ENOENT;
+ }
+
+ /* Get the starting vcn of the index_block holding the child node. */
+ *vcn = ntfs_ie_get_vcn(ie);
+ if (*vcn < 0) {
+ ntfs_error(icx->idx_ni->vol->sb, "Negative vcn in inode %llu\n",
+ (unsigned long long)icx->idx_ni->mft_no);
+ return -EINVAL;
+ }
+
+ ntfs_debug("Parent entry number %d\n", item);
+ icx->parent_pos[icx->pindex] = item;
+
+ return -EAGAIN;
+}
+
+struct ntfs_inode *ntfs_ia_open(struct ntfs_index_context *icx, struct ntfs_inode *ni)
+{
+ struct inode *ia_vi;
+
+ ia_vi = ntfs_index_iget(VFS_I(ni), icx->name, icx->name_len);
+ if (IS_ERR(ia_vi)) {
+ ntfs_error(icx->idx_ni->vol->sb,
+ "Failed to open index allocation of inode %llu",
+ (unsigned long long)ni->mft_no);
+ return NULL;
+ }
+
+ return NTFS_I(ia_vi);
+}
+
+static int ntfs_ib_read(struct ntfs_index_context *icx, s64 vcn, struct index_block *dst)
+{
+ s64 pos, ret;
+
+ ntfs_debug("vcn: %lld\n", vcn);
+
+ pos = ntfs_ib_vcn_to_pos(icx, vcn);
+
+ ret = ntfs_inode_attr_pread(VFS_I(icx->ia_ni), pos, icx->block_size, (u8 *)dst);
+ if (ret != icx->block_size) {
+ if (ret == -1)
+ ntfs_error(icx->idx_ni->vol->sb, "Failed to read index block");
+ else
+ ntfs_error(icx->idx_ni->vol->sb,
+ "Failed to read full index block at %lld\n", pos);
+ return -EIO;
+ }
+
+ post_read_mst_fixup((struct ntfs_record *)((u8 *)dst), icx->block_size);
+ if (ntfs_index_block_inconsistent(icx->idx_ni->vol, dst,
+ icx->block_size, vcn, icx->cr,
+ icx->idx_ni->mft_no))
+ return -EIO;
+ return 0;
+}
+
+static int ntfs_icx_parent_inc(struct ntfs_index_context *icx)
+{
+ if (icx->pindex >= MAX_PARENT_VCN - 1) {
+ ntfs_error(icx->idx_ni->vol->sb, "Index is over %d level deep", MAX_PARENT_VCN);
+ return -EOPNOTSUPP;
+ }
+ icx->pindex++;
+ return 0;
+}
+
+static int ntfs_icx_parent_dec(struct ntfs_index_context *icx)
+{
+ icx->pindex--;
+ if (icx->pindex < 0) {
+ ntfs_error(icx->idx_ni->vol->sb, "Corrupt index pointer (%d)", icx->pindex);
+ return -EINVAL;
+ }
+ return 0;
+}
+
+/*
+ * ntfs_index_lookup - find a key in an index and return its index entry
+ * @key: key for which to search in the index
+ * @key_len: length of @key in bytes
+ * @icx: 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, -ENOENT is returned 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.
+ *
+ * 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 u32 key_len, struct ntfs_index_context *icx)
+{
+ s64 old_vcn, vcn;
+ struct ntfs_inode *ni = icx->idx_ni;
+ struct super_block *sb = ni->vol->sb;
+ struct index_root *ir;
+ struct index_entry *ie;
+ struct index_block *ib = NULL;
+ int err = 0;
+
+ ntfs_debug("Entering\n");
+
+ if (!key) {
+ ntfs_error(sb, "key: %p key_len: %d", key, key_len);
+ return -EINVAL;
+ }
+
+ ir = ntfs_ir_lookup(ni, icx->name, icx->name_len, &icx->actx);
+ if (!ir)
+ return -EIO;
+
+ icx->block_size = le32_to_cpu(ir->index_block_size);
+ if (icx->block_size < NTFS_BLOCK_SIZE) {
+ err = -EINVAL;
+ ntfs_error(sb,
+ "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 = ni->vol->sector_size_bits;
+
+ icx->cr = ir->collation_rule;
+ if (!ntfs_is_collation_rule_supported(icx->cr)) {
+ err = -EOPNOTSUPP;
+ ntfs_error(sb, "Unknown collation rule 0x%x",
+ (unsigned int)le32_to_cpu(icx->cr));
+ goto err_out;
+ }
+
+ old_vcn = VCN_INDEX_ROOT_PARENT;
+ err = ntfs_ie_lookup(key, key_len, icx, &ir->index, &vcn, &ie);
+ if (err == -ERANGE || err == -EINVAL)
+ goto err_out;
+
+ icx->ir = ir;
+ if (err != -EAGAIN) {
+ icx->is_in_root = true;
+ icx->parent_vcn[icx->pindex] = old_vcn;
+ goto done;
+ }
+
+ /* Child node present, descend into it. */
+ icx->ia_ni = ntfs_ia_open(icx, ni);
+ if (!icx->ia_ni) {
+ err = -ENOENT;
+ goto err_out;
+ }
+
+ ib = kvzalloc(icx->block_size, GFP_NOFS);
+ if (!ib) {
+ err = -ENOMEM;
+ goto err_out;
+ }
+
+descend_into_child_node:
+ icx->parent_vcn[icx->pindex] = old_vcn;
+ if (ntfs_icx_parent_inc(icx)) {
+ err = -EIO;
+ goto err_out;
+ }
+ old_vcn = vcn;
+
+ ntfs_debug("Descend into node with s64 %lld.\n", vcn);
+
+ if (ntfs_ib_read(icx, vcn, ib)) {
+ err = -EIO;
+ goto err_out;
+ }
+ err = ntfs_ie_lookup(key, key_len, icx, &ib->index, &vcn, &ie);
+ if (err != -EAGAIN) {
+ if (err == -EINVAL || err == -ERANGE)
+ goto err_out;
+
+ icx->is_in_root = false;
+ icx->ib = ib;
+ icx->parent_vcn[icx->pindex] = vcn;
+ goto done;
+ }
+
+ if ((ib->index.flags & NODE_MASK) == LEAF_NODE) {
+ ntfs_error(icx->idx_ni->vol->sb,
+ "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:
+ if (icx->actx) {
+ ntfs_attr_put_search_ctx(icx->actx);
+ icx->actx = NULL;
+ }
+ kvfree(ib);
+ if (!err)
+ err = -EIO;
+ return err;
+done:
+ icx->entry = ie;
+ icx->data = (u8 *)ie + offsetof(struct index_entry, key);
+ icx->data_len = le16_to_cpu(ie->key_length);
+ ntfs_debug("Done.\n");
+ return err;
+
+}
+
+static struct index_block *ntfs_ib_alloc(s64 ib_vcn, u32 ib_size,
+ u8 node_type)
+{
+ struct index_block *ib;
+ int ih_size = sizeof(struct index_header);
+
+ ntfs_debug("Entering ib_vcn = %lld ib_size = %u\n", ib_vcn, ib_size);
+
+ ib = kvzalloc(ib_size, GFP_NOFS);
+ if (!ib)
+ return NULL;
+
+ ib->magic = magic_INDX;
+ ib->usa_ofs = cpu_to_le16(sizeof(struct 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)) = cpu_to_le16(1);
+ ib->lsn = 0;
+ ib->index_block_vcn = cpu_to_le64(ib_vcn);
+ ib->index.entries_offset = cpu_to_le32((ih_size +
+ le16_to_cpu(ib->usa_count) * 2 + 7) & ~7);
+ ib->index.index_length = 0;
+ ib->index.allocated_size = cpu_to_le32(ib_size -
+ (sizeof(struct index_block) - ih_size));
+ ib->index.flags = node_type;
+
+ return ib;
+}
+
+/*
+ * Find the median by going through all the entries
+ */
+static struct index_entry *ntfs_ie_get_median(struct index_header *ih)
+{
+ struct index_entry *ie, *ie_start;
+ u8 *ie_end;
+ int i = 0, median;
+
+ ntfs_debug("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_debug("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 u64 ntfs_ibm_vcn_to_pos(struct ntfs_index_context *icx, s64 vcn)
+{
+ u64 pos = ntfs_ib_vcn_to_pos(icx, vcn);
+
+ do_div(pos, icx->block_size);
+ return pos;
+}
+
+static s64 ntfs_ibm_pos_to_vcn(struct ntfs_index_context *icx, s64 pos)
+{
+ return ntfs_ib_pos_to_vcn(icx, pos * icx->block_size);
+}
+
+static int ntfs_ibm_add(struct ntfs_index_context *icx)
+{
+ u8 bmp[8];
+ int ret;
+
+ ntfs_debug("Entering\n");
+
+ if (ntfs_attr_exist(icx->idx_ni, AT_BITMAP, icx->name, icx->name_len))
+ return 0;
+ /*
+ * AT_BITMAP must be at least 8 bytes.
+ */
+ memset(bmp, 0, sizeof(bmp));
+ ret = ntfs_attr_add(icx->idx_ni, AT_BITMAP, icx->name, icx->name_len,
+ bmp, sizeof(bmp));
+ if (ret) {
+ ntfs_error(icx->idx_ni->vol->sb, "Failed to add AT_BITMAP");
+ return ret;
+ }
+
+ return 0;
+}
+
+static int ntfs_ibm_modify(struct ntfs_index_context *icx, s64 vcn, int set)
+{
+ u8 byte;
+ u64 pos = ntfs_ibm_vcn_to_pos(icx, vcn);
+ u32 bpos = pos / 8;
+ u32 bit = 1 << (pos % 8);
+ struct ntfs_inode *bmp_ni;
+ struct inode *bmp_vi;
+ int ret = 0;
+
+ ntfs_debug("%s vcn: %lld\n", set ? "set" : "clear", vcn);
+
+ bmp_vi = ntfs_attr_iget(VFS_I(icx->idx_ni), AT_BITMAP, icx->name, icx->name_len);
+ if (IS_ERR(bmp_vi)) {
+ ntfs_error(icx->idx_ni->vol->sb, "Failed to open $BITMAP attribute");
+ return PTR_ERR(bmp_vi);
+ }
+
+ bmp_ni = NTFS_I(bmp_vi);
+
+ if (set) {
+ if (bmp_ni->data_size < bpos + 1) {
+ ret = ntfs_attr_truncate(bmp_ni, (bmp_ni->data_size + 8) & ~7);
+ if (ret) {
+ ntfs_error(icx->idx_ni->vol->sb, "Failed to truncate AT_BITMAP");
+ goto err;
+ }
+ i_size_write(bmp_vi, (loff_t)bmp_ni->data_size);
+ }
+ }
+
+ if (ntfs_inode_attr_pread(bmp_vi, bpos, 1, &byte) != 1) {
+ ret = -EIO;
+ ntfs_error(icx->idx_ni->vol->sb, "Failed to read $BITMAP");
+ goto err;
+ }
+
+ if (set)
+ byte |= bit;
+ else
+ byte &= ~bit;
+
+ if (ntfs_inode_attr_pwrite(bmp_vi, bpos, 1, &byte, false) != 1) {
+ ret = -EIO;
+ ntfs_error(icx->idx_ni->vol->sb, "Failed to write $Bitmap");
+ goto err;
+ }
+
+err:
+ iput(bmp_vi);
+ return ret;
+}
+
+static int ntfs_ibm_set(struct ntfs_index_context *icx, s64 vcn)
+{
+ return ntfs_ibm_modify(icx, vcn, 1);
+}
+
+static int ntfs_ibm_clear(struct ntfs_index_context *icx, s64 vcn)
+{
+ return ntfs_ibm_modify(icx, vcn, 0);
+}
+
+static s64 ntfs_ibm_get_free(struct ntfs_index_context *icx)
+{
+ u8 *bm;
+ int bit;
+ int ret;
+ s64 vcn, byte, size;
+
+ ntfs_debug("Entering\n");
+
+ bm = ntfs_attr_readall(icx->idx_ni, AT_BITMAP, icx->name, icx->name_len,
+ &size);
+ if (IS_ERR(bm))
+ return PTR_ERR(bm);
+
+ 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_debug("allocated vcn: %lld\n", vcn);
+
+ ret = ntfs_ibm_set(icx, vcn);
+
+ kvfree(bm);
+ if (ret)
+ return ret;
+
+ return vcn;
+}
+
+static struct index_block *ntfs_ir_to_ib(struct index_root *ir, s64 ib_vcn)
+{
+ struct index_block *ib;
+ struct index_entry *ie_last;
+ char *ies_start, *ies_end;
+ int i;
+ u32 ib_cap;
+
+ ntfs_debug("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((struct 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);
+
+ /* Entries must fit in the allocated index block */
+ ib_cap = le32_to_cpu(ib->index.allocated_size) -
+ le32_to_cpu(ib->index.entries_offset);
+ if ((u32)i > ib_cap) {
+ ntfs_error(NULL, "Entries (%d B) exceed IB capacity", i);
+ kvfree(ib);
+ return NULL;
+ }
+
+ memcpy(ntfs_ie_get_first(&ib->index), ies_start, i);
+
+ ib->index.flags = ir->index.flags;
+ ib->index.index_length = cpu_to_le32(i +
+ le32_to_cpu(ib->index.entries_offset));
+ return ib;
+}
+
+static void ntfs_ir_nill(struct index_root *ir)
+{
+ struct index_entry *ie_last;
+ char *ies_start, *ies_end;
+
+ ntfs_debug("Entering\n");
+
+ ies_start = (char *)ntfs_ie_get_first(&ir->index);
+ ies_end = (char *)ntfs_ie_get_end(&ir->index);
+ ie_last = ntfs_ie_get_last((struct index_entry *)ies_start, ies_end);
+ /*
+ * Move the index root termination entry forward
+ */
+ if ((char *)ie_last > ies_start) {
+ memmove((char *)ntfs_ie_get_first(&ir->index),
+ (char *)ie_last, le16_to_cpu(ie_last->length));
+ ie_last = (struct index_entry *)ies_start;
+ }
+}
+
+static int ntfs_ib_copy_tail(struct ntfs_index_context *icx, struct index_block *src,
+ struct index_entry *median, s64 new_vcn)
+{
+ u8 *ies_end;
+ struct index_entry *ie_head; /* first entry after the median */
+ int tail_size, ret;
+ struct index_block *dst;
+
+ ntfs_debug("Entering\n");
+
+ dst = ntfs_ib_alloc(new_vcn, icx->block_size,
+ src->index.flags & NODE_MASK);
+ if (!dst)
+ return -ENOMEM;
+
+ 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);
+
+ kvfree(dst);
+ return ret;
+}
+
+static int ntfs_ib_cut_tail(struct ntfs_index_context *icx, struct index_block *ib,
+ struct index_entry *ie)
+{
+ char *ies_start, *ies_end;
+ struct index_entry *ie_last;
+ int ret;
+
+ ntfs_debug("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((struct index_entry *)ies_start, ies_end);
+ if (ie_last->flags & INDEX_ENTRY_NODE)
+ ntfs_ie_set_vcn(ie_last, ntfs_ie_get_vcn(ie));
+
+ unsafe_memcpy(ie, ie_last, le16_to_cpu(ie_last->length),
+ /* alloc is larger than ie_last->length, see ntfs_ie_get_last() */);
+
+ ib->index.index_length = cpu_to_le32(((char *)ie - ies_start) +
+ le16_to_cpu(ie->length) + le32_to_cpu(ib->index.entries_offset));
+
+ ret = ntfs_ib_write(icx, ib);
+ return ret;
+}
+
+static int ntfs_ia_add(struct ntfs_index_context *icx)
+{
+ int ret;
+
+ ntfs_debug("Entering\n");
+
+ ret = ntfs_ibm_add(icx);
+ if (ret)
+ return ret;
+
+ if (!ntfs_attr_exist(icx->idx_ni, AT_INDEX_ALLOCATION, icx->name, icx->name_len)) {
+ ret = ntfs_attr_add(icx->idx_ni, AT_INDEX_ALLOCATION, icx->name,
+ icx->name_len, NULL, 0);
+ if (ret) {
+ ntfs_error(icx->idx_ni->vol->sb, "Failed to add AT_INDEX_ALLOCATION");
+ return ret;
+ }
+ }
+
+ icx->ia_ni = ntfs_ia_open(icx, icx->idx_ni);
+ if (!icx->ia_ni)
+ return -ENOENT;
+
+ return 0;
+}
+
+static int ntfs_ir_reparent(struct ntfs_index_context *icx)
+{
+ struct ntfs_attr_search_ctx *ctx = NULL;
+ struct index_root *ir;
+ struct index_entry *ie;
+ struct index_block *ib = NULL;
+ s64 new_ib_vcn;
+ u32 index_length;
+ u32 old_value_length;
+ int ix_root_size;
+ int ret = 0;
+
+ ntfs_debug("Entering\n");
+
+ ir = ntfs_ir_lookup2(icx->idx_ni, icx->name, icx->name_len);
+ if (!ir) {
+ ret = -ENOENT;
+ goto out;
+ }
+
+ if ((ir->index.flags & NODE_MASK) == SMALL_INDEX) {
+ ret = ntfs_ia_add(icx);
+ if (ret)
+ goto out;
+ }
+
+ new_ib_vcn = ntfs_ibm_get_free(icx);
+ if (new_ib_vcn < 0) {
+ ret = (int)new_ib_vcn;
+ goto out;
+ }
+
+ ir = ntfs_ir_lookup2(icx->idx_ni, icx->name, icx->name_len);
+ if (!ir) {
+ ret = -ENOENT;
+ goto clear_bmp;
+ }
+
+ ib = ntfs_ir_to_ib(ir, new_ib_vcn);
+ if (ib == NULL) {
+ ret = -EIO;
+ ntfs_error(icx->idx_ni->vol->sb, "Failed to move index root to index block");
+ goto clear_bmp;
+ }
+
+ ret = ntfs_ib_write(icx, ib);
+ if (ret)
+ goto clear_bmp;
+
+retry:
+ ir = ntfs_ir_lookup(icx->idx_ni, icx->name, icx->name_len, &ctx);
+ if (!ir) {
+ ret = -ENOENT;
+ goto clear_bmp;
+ }
+
+ old_value_length = le32_to_cpu(ctx->attr->data.resident.value_length);
+ index_length = le32_to_cpu(ir->index.entries_offset) +
+ sizeof(struct index_entry_header) + sizeof(s64);
+ ix_root_size = offsetof(struct index_root, index) + index_length;
+ /* Grow the resident value before publishing the larger root header. */
+ if (ix_root_size > old_value_length) {
+ ret = ntfs_resident_attr_value_resize(ctx->mrec, ctx->attr, ix_root_size);
+ if (ret)
+ goto resize_failed;
+
+ icx->idx_ni->data_size = ix_root_size;
+ icx->idx_ni->initialized_size = ix_root_size;
+ icx->idx_ni->allocated_size = (ix_root_size + 7) & ~7;
+ }
+
+ ntfs_ir_nill(ir);
+
+ ie = ntfs_ie_get_first(&ir->index);
+ ie->flags |= INDEX_ENTRY_NODE;
+ ie->length = cpu_to_le16(sizeof(struct index_entry_header) + sizeof(s64));
+
+ ir->index.flags = LARGE_INDEX;
+ NInoSetIndexAllocPresent(icx->idx_ni);
+ ir->index.index_length = cpu_to_le32(index_length);
+ ir->index.allocated_size = ir->index.index_length;
+
+ if (ix_root_size <= old_value_length) {
+ ret = ntfs_resident_attr_value_resize(ctx->mrec, ctx->attr, ix_root_size);
+ if (ret)
+ goto resize_failed;
+
+ icx->idx_ni->data_size = ix_root_size;
+ icx->idx_ni->initialized_size = ix_root_size;
+ icx->idx_ni->allocated_size = (ix_root_size + 7) & ~7;
+ }
+ ntfs_ie_set_vcn(ie, new_ib_vcn);
+ goto err_out;
+
+resize_failed:
+ /*
+ * When there is no space to build a non-resident
+ * index, we may have to move the root to an extent
+ */
+ if (ret == -ENOSPC) {
+ if (!ctx->al_entry) {
+ ret = ntfs_inode_add_attrlist(icx->idx_ni);
+ if (ret)
+ goto clear_bmp;
+
+ ntfs_attr_put_search_ctx(ctx);
+ ctx = NULL;
+ goto retry;
+ }
+
+ if (ctx->ntfs_ino->mft_no != icx->idx_ni->mft_no)
+ goto clear_bmp;
+
+ ret = ntfs_attr_record_move_away(ctx, ix_root_size -
+ le32_to_cpu(ctx->attr->data.resident.value_length));
+ if (ret)
+ goto clear_bmp;
+
+ ret = ntfs_attrlist_update(icx->idx_ni);
+ if (ret) {
+ int rollback_ret;
+
+ ntfs_attr_put_search_ctx(ctx);
+ ctx = NULL;
+ rollback_ret = ntfs_ir_move_to_base(icx);
+ if (rollback_ret)
+ ntfs_error(icx->idx_ni->vol->sb,
+ "Failed to roll back INDEX_ROOT relocation: %d",
+ rollback_ret);
+ goto clear_bmp;
+ }
+
+ ntfs_attr_put_search_ctx(ctx);
+ ctx = NULL;
+ goto retry;
+ }
+clear_bmp:
+ ntfs_ibm_clear(icx, new_ib_vcn);
+ goto err_out;
+err_out:
+ kvfree(ib);
+ if (ctx)
+ ntfs_attr_put_search_ctx(ctx);
+out:
+ return ret;
+}
+
+/*
+ * ntfs_ir_truncate - Truncate index root attribute
+ * @icx: index context
+ * @data_size: new data size for the index root
+ */
+static int ntfs_ir_truncate(struct ntfs_index_context *icx, int data_size)
+{
+ int ret;
+ u32 old_allocated_size;
+ bool shrink;
+
+ ntfs_debug("Entering\n");
+
+ old_allocated_size = le32_to_cpu(icx->ir->index.allocated_size);
+ shrink = data_size < old_allocated_size;
+ if (shrink)
+ icx->ir->index.allocated_size = cpu_to_le32(data_size);
+
+ /*
+ * INDEX_ROOT must be resident and its entries can be moved to
+ * struct index_block, so ENOSPC isn't a real error.
+ */
+ ret = ntfs_attr_truncate(icx->idx_ni, data_size + offsetof(struct index_root, index));
+ if (!ret) {
+ i_size_write(VFS_I(icx->idx_ni), icx->idx_ni->initialized_size);
+ icx->ir = ntfs_ir_lookup2(icx->idx_ni, icx->name, icx->name_len);
+ if (!icx->ir)
+ return -ENOENT;
+
+ if (!shrink)
+ icx->ir->index.allocated_size = cpu_to_le32(data_size);
+ } else {
+ if (shrink)
+ icx->ir->index.allocated_size = cpu_to_le32(old_allocated_size);
+ if (ret != -ENOSPC)
+ ntfs_error(icx->idx_ni->vol->sb, "Failed to truncate INDEX_ROOT");
+ }
+
+ return ret;
+}
+
+/*
+ * ntfs_ir_make_space - Make more space for the index root attribute
+ * @icx: index context
+ * @data_size: required data size for the index root
+ */
+static int ntfs_ir_make_space(struct ntfs_index_context *icx, int data_size)
+{
+ int ret;
+
+ ntfs_debug("Entering\n");
+
+ ret = ntfs_ir_truncate(icx, data_size);
+ if (ret == -ENOSPC) {
+ ret = ntfs_ir_reparent(icx);
+ if (!ret)
+ ret = -EAGAIN;
+ else
+ ntfs_error(icx->idx_ni->vol->sb, "Failed to modify INDEX_ROOT");
+ }
+
+ return ret;
+}
+
+/*
+ * NOTE: 'ie' must be a copy of a real index entry.
+ */
+static int ntfs_ie_add_vcn(struct index_entry **ie)
+{
+ struct index_entry *p, *old = *ie;
+
+ old->length = cpu_to_le16(le16_to_cpu(old->length) + sizeof(s64));
+ p = krealloc(old, le16_to_cpu(old->length), GFP_NOFS);
+ if (!p)
+ return -ENOMEM;
+
+ p->flags |= INDEX_ENTRY_NODE;
+ *ie = p;
+ return 0;
+}
+
+static int ntfs_ih_insert(struct index_header *ih, struct index_entry *orig_ie, s64 new_vcn,
+ int pos)
+{
+ struct index_entry *ie_node, *ie;
+ int ret = 0;
+ s64 old_vcn;
+
+ ntfs_debug("Entering\n");
+ ie = ntfs_ie_dup(orig_ie);
+ if (!ie)
+ return -ENOMEM;
+
+ if (!(ie->flags & INDEX_ENTRY_NODE)) {
+ ret = ntfs_ie_add_vcn(&ie);
+ if (ret)
+ 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);
+out:
+ kfree(ie);
+ return ret;
+}
+
+static s64 ntfs_icx_parent_vcn(struct ntfs_index_context *icx)
+{
+ return icx->parent_vcn[icx->pindex];
+}
+
+static s64 ntfs_icx_parent_pos(struct ntfs_index_context *icx)
+{
+ return icx->parent_pos[icx->pindex];
+}
+
+static int ntfs_ir_insert_median(struct ntfs_index_context *icx, struct index_entry *median,
+ s64 new_vcn)
+{
+ u32 new_size;
+ int ret;
+
+ ntfs_debug("Entering\n");
+
+ icx->ir = ntfs_ir_lookup2(icx->idx_ni, icx->name, icx->name_len);
+ if (!icx->ir)
+ return -ENOENT;
+
+ new_size = le32_to_cpu(icx->ir->index.index_length) +
+ le16_to_cpu(median->length);
+ if (!(median->flags & INDEX_ENTRY_NODE))
+ new_size += sizeof(s64);
+
+ ret = ntfs_ir_make_space(icx, new_size);
+ if (ret)
+ return ret;
+
+ icx->ir = ntfs_ir_lookup2(icx->idx_ni, icx->name, icx->name_len);
+ if (!icx->ir)
+ return -ENOENT;
+
+ return ntfs_ih_insert(&icx->ir->index, median, new_vcn,
+ ntfs_icx_parent_pos(icx));
+}
+
+static int ntfs_ib_split(struct ntfs_index_context *icx, struct index_block *ib);
+
+struct split_info {
+ struct list_head entry;
+ s64 new_vcn;
+ struct index_block *ib;
+};
+
+static int ntfs_ib_insert(struct ntfs_index_context *icx, struct index_entry *ie, s64 new_vcn,
+ struct split_info *si)
+{
+ struct index_block *ib;
+ u32 idx_size, allocated_size;
+ int err;
+ s64 old_vcn;
+
+ ntfs_debug("Entering\n");
+
+ ib = kvzalloc(icx->block_size, GFP_NOFS);
+ if (!ib)
+ return -ENOMEM;
+
+ old_vcn = ntfs_icx_parent_vcn(icx);
+
+ err = ntfs_ib_read(icx, old_vcn, ib);
+ if (err)
+ goto err_out;
+
+ idx_size = le32_to_cpu(ib->index.index_length);
+ allocated_size = le32_to_cpu(ib->index.allocated_size);
+ if (idx_size + le16_to_cpu(ie->length) + sizeof(s64) > allocated_size) {
+ si->ib = ib;
+ si->new_vcn = new_vcn;
+ return -EAGAIN;
+ }
+
+ err = ntfs_ih_insert(&ib->index, ie, new_vcn, ntfs_icx_parent_pos(icx));
+ if (err)
+ goto err_out;
+
+ err = ntfs_ib_write(icx, ib);
+
+err_out:
+ kvfree(ib);
+ return err;
+}
+
+/*
+ * ntfs_ib_split - Split an index block
+ * @icx: index context
+ * @ib: index block to split
+ */
+static int ntfs_ib_split(struct ntfs_index_context *icx, struct index_block *ib)
+{
+ struct index_entry *median;
+ s64 new_vcn;
+ int ret;
+ struct split_info *si;
+ LIST_HEAD(ntfs_cut_tail_list);
+
+ ntfs_debug("Entering\n");
+
+resplit:
+ ret = ntfs_icx_parent_dec(icx);
+ if (ret)
+ goto out;
+
+ median = ntfs_ie_get_median(&ib->index);
+ new_vcn = ntfs_ibm_get_free(icx);
+ if (new_vcn < 0) {
+ ret = (int)new_vcn;
+ goto out;
+ }
+
+ ret = ntfs_ib_copy_tail(icx, ib, median, new_vcn);
+ if (ret) {
+ ntfs_ibm_clear(icx, new_vcn);
+ goto out;
+ }
+
+ if (ntfs_icx_parent_vcn(icx) == VCN_INDEX_ROOT_PARENT) {
+ ret = ntfs_ir_insert_median(icx, median, new_vcn);
+ if (ret) {
+ ntfs_ibm_clear(icx, new_vcn);
+ goto out;
+ }
+ } else {
+ si = kzalloc_obj(struct split_info, GFP_NOFS);
+ if (!si) {
+ ntfs_ibm_clear(icx, new_vcn);
+ ret = -ENOMEM;
+ goto out;
+ }
+
+ ret = ntfs_ib_insert(icx, median, new_vcn, si);
+ if (ret == -EAGAIN) {
+ list_add_tail(&si->entry, &ntfs_cut_tail_list);
+ ib = si->ib;
+ goto resplit;
+ } else if (ret) {
+ kvfree(si->ib);
+ kfree(si);
+ ntfs_ibm_clear(icx, new_vcn);
+ goto out;
+ }
+ kfree(si);
+ }
+
+ ret = ntfs_ib_cut_tail(icx, ib, median);
+
+out:
+ while (!list_empty(&ntfs_cut_tail_list)) {
+ si = list_last_entry(&ntfs_cut_tail_list, struct split_info, entry);
+ ntfs_ibm_clear(icx, si->new_vcn);
+ kvfree(si->ib);
+ list_del(&si->entry);
+ kfree(si);
+ if (!ret)
+ ret = -EAGAIN;
+ }
+
+ return ret;
+}
+
+int ntfs_ie_add(struct ntfs_index_context *icx, struct index_entry *ie)
+{
+ struct index_header *ih;
+ int allocated_size, new_size;
+ int ret;
+
+ while (1) {
+ ret = ntfs_index_lookup(&ie->key, le16_to_cpu(ie->key_length), icx);
+ if (!ret) {
+ ret = -EEXIST;
+ ntfs_error(icx->idx_ni->vol->sb, "Index already have such entry");
+ goto err_out;
+ }
+ if (ret != -ENOENT) {
+ ntfs_error(icx->idx_ni->vol->sb, "Failed to find place for new entry");
+ goto err_out;
+ }
+ ret = 0;
+
+ 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_debug("index block sizes: allocated: %d needed: %d\n",
+ allocated_size, new_size);
+
+ if (icx->is_in_root)
+ ret = ntfs_ir_make_space(icx, new_size);
+ else
+ ret = ntfs_ib_split(icx, icx->ib);
+ if (ret && ret != -EAGAIN)
+ goto err_out;
+
+ mark_mft_record_dirty(icx->actx->ntfs_ino);
+ ntfs_index_ctx_reinit(icx);
+ }
+
+ ntfs_ie_insert(ih, ie, icx->entry);
+ ntfs_index_entry_mark_dirty(icx);
+
+err_out:
+ ntfs_debug("%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
+ */
+int ntfs_index_add_filename(struct ntfs_inode *ni, struct file_name_attr *fn, u64 mref)
+{
+ struct index_entry *ie;
+ struct ntfs_index_context *icx;
+ int fn_size, ie_size, err;
+
+ ntfs_debug("Entering\n");
+
+ if (!ni || !fn)
+ return -EINVAL;
+
+ fn_size = (fn->file_name_length * sizeof(__le16)) +
+ sizeof(struct file_name_attr);
+ ie_size = (sizeof(struct index_entry_header) + fn_size + 7) & ~7;
+
+ ie = kzalloc(ie_size, GFP_NOFS);
+ if (!ie)
+ return -ENOMEM;
+
+ ie->data.dir.indexed_file = cpu_to_le64(mref);
+ ie->length = cpu_to_le16(ie_size);
+ ie->key_length = cpu_to_le16(fn_size);
+
+ unsafe_memcpy(&ie->key, fn, fn_size,
+ /* "fn_size" was correctly calculated above */);
+
+ icx = ntfs_index_ctx_get(ni, I30, 4);
+ if (!icx) {
+ err = -ENOMEM;
+ goto out;
+ }
+
+ err = ntfs_ie_add(icx, ie);
+ ntfs_index_ctx_put(icx);
+out:
+ kfree(ie);
+ return err;
+}
+
+static int ntfs_ih_takeout(struct ntfs_index_context *icx, struct index_header *ih,
+ struct index_entry *ie, struct index_block *ib)
+{
+ struct index_entry *ie_roam;
+ int freed_space;
+ bool full;
+ int ret = 0;
+
+ ntfs_debug("Entering\n");
+
+ full = ih->index_length == ih->allocated_size;
+ ie_roam = ntfs_ie_dup_novcn(ie);
+ if (!ie_roam)
+ return -ENOMEM;
+
+ 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 */
+ }
+
+ mark_mft_record_dirty(icx->actx->ntfs_ino);
+ } else {
+ ret = ntfs_ib_write(icx, ib);
+ if (ret)
+ goto out;
+ }
+
+ ntfs_index_ctx_reinit(icx);
+
+ ret = ntfs_ie_add(icx, ie_roam);
+out:
+ kfree(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(struct ntfs_index_context *icx, struct index_header *ih)
+{
+ struct index_entry *ie;
+
+ ntfs_debug("Entering\n");
+
+ ie = ntfs_ie_get_first(ih);
+ ie->flags &= ~INDEX_ENTRY_NODE;
+ ie->length = cpu_to_le16(le16_to_cpu(ie->length) - sizeof(s64));
+
+ ih->index_length = cpu_to_le32(le32_to_cpu(ih->index_length) - sizeof(s64));
+ ih->flags &= ~LARGE_INDEX;
+ NInoClearIndexAllocPresent(icx->idx_ni);
+
+ /* 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(struct ntfs_index_context *icx, struct index_header *ih,
+ struct index_block *ib)
+{
+ struct index_entry *ie, *ie_prev;
+
+ ntfs_debug("Entering\n");
+
+ ie = ntfs_ie_get_by_pos(ih, ntfs_icx_parent_pos(icx));
+ ie_prev = ntfs_ie_prev(ih, ie);
+ if (!ie_prev)
+ return -EIO;
+ 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(struct ntfs_index_context *icx)
+{
+ struct index_block *ib = NULL;
+ struct index_header *parent_ih;
+ struct index_entry *ie;
+ int ret;
+
+ ntfs_debug("pindex: %d\n", icx->pindex);
+
+ ret = ntfs_icx_parent_dec(icx);
+ if (ret)
+ return ret;
+
+ ret = ntfs_ibm_clear(icx, icx->parent_vcn[icx->pindex + 1]);
+ if (ret)
+ return ret;
+
+ if (ntfs_icx_parent_vcn(icx) == VCN_INDEX_ROOT_PARENT)
+ parent_ih = &icx->ir->index;
+ else {
+ ib = kvzalloc(icx->block_size, GFP_NOFS);
+ if (!ib)
+ return -ENOMEM;
+
+ ret = ntfs_ib_read(icx, ntfs_icx_parent_vcn(icx), ib);
+ if (ret)
+ 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 out;
+ }
+
+ ret = ntfs_index_rm_leaf(icx);
+ goto out;
+ }
+
+ ret = ntfs_ih_reparent_end(icx, parent_ih, ib);
+out:
+ kvfree(ib);
+ return ret;
+}
+
+static int ntfs_index_rm_node(struct ntfs_index_context *icx)
+{
+ int entry_pos, pindex;
+ s64 vcn;
+ struct index_block *ib = NULL;
+ struct index_entry *ie_succ, *ie, *entry = icx->entry;
+ struct index_header *ih;
+ u32 new_size;
+ int delta, ret;
+
+ ntfs_debug("Entering\n");
+
+ if (!icx->ia_ni) {
+ icx->ia_ni = ntfs_ia_open(icx, icx->idx_ni);
+ if (!icx->ia_ni)
+ return -EINVAL;
+ }
+
+ ib = kvzalloc(icx->block_size, GFP_NOFS);
+ if (!ib)
+ return -ENOMEM;
+
+ 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);
+ ret = ntfs_ib_read(icx, vcn, ib);
+ if (ret)
+ goto out;
+
+ ie_succ = ntfs_ie_get_first(&ib->index);
+
+ ret = ntfs_icx_parent_inc(icx);
+ if (ret)
+ goto out;
+
+ icx->parent_vcn[icx->pindex] = vcn;
+ icx->parent_pos[icx->pindex] = 0;
+
+ if ((ib->index.flags & NODE_MASK) == INDEX_NODE)
+ goto descend;
+
+ if (ntfs_ih_zero_entry(&ib->index)) {
+ ret = -EIO;
+ ntfs_error(icx->idx_ni->vol->sb, "Empty index block");
+ goto out;
+ }
+
+ ie = ntfs_ie_dup(ie_succ);
+ if (!ie) {
+ ret = -ENOMEM;
+ goto out;
+ }
+
+ ret = ntfs_ie_add_vcn(&ie);
+ if (ret)
+ 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 != 0)
+ 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)
+ ret = -EAGAIN;
+ goto out2;
+ }
+ }
+
+ ntfs_ie_delete(ih, entry);
+ ntfs_ie_insert(ih, ie, entry);
+
+ if (icx->is_in_root)
+ ret = ntfs_ir_truncate(icx, new_size);
+ else
+ ret = ntfs_icx_ib_write(icx);
+ if (ret)
+ goto out2;
+
+ ntfs_ie_delete(&ib->index, ie_succ);
+
+ if (ntfs_ih_zero_entry(&ib->index))
+ ret = ntfs_index_rm_leaf(icx);
+ else
+ ret = ntfs_ib_write(icx, ib);
+
+out2:
+ kfree(ie);
+out:
+ kvfree(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.
+ */
+int ntfs_index_rm(struct ntfs_index_context *icx)
+{
+ struct index_header *ih;
+ int ret = 0;
+
+ ntfs_debug("Entering\n");
+
+ if (!icx || (!icx->ib && !icx->ir) || ntfs_ie_end(icx->entry)) {
+ ret = -EINVAL;
+ goto err_out;
+ }
+ if (icx->is_in_root)
+ ih = &icx->ir->index;
+ else
+ ih = &icx->ib->index;
+
+ if (icx->entry->flags & INDEX_ENTRY_NODE) {
+ ret = ntfs_index_rm_node(icx);
+ if (ret)
+ goto err_out;
+ } else if (icx->is_in_root || !ntfs_ih_one_entry(ih)) {
+ ntfs_ie_delete(ih, icx->entry);
+
+ if (icx->is_in_root)
+ ret = ntfs_ir_truncate(icx, le32_to_cpu(ih->index_length));
+ else
+ ret = ntfs_icx_ib_write(icx);
+ if (ret)
+ goto err_out;
+ } else {
+ ret = ntfs_index_rm_leaf(icx);
+ if (ret)
+ goto err_out;
+ }
+
+ return 0;
+err_out:
+ return ret;
+}
+
+int ntfs_index_remove(struct ntfs_inode *dir_ni, const void *key, const u32 keylen)
+{
+ int ret = 0;
+ struct ntfs_index_context *icx;
+
+ icx = ntfs_index_ctx_get(dir_ni, I30, 4);
+ if (!icx)
+ return -EINVAL;
+
+ while (1) {
+ ret = ntfs_index_lookup(key, keylen, icx);
+ if (ret)
+ goto err_out;
+
+ ret = ntfs_index_rm(icx);
+ if (ret && ret != -EAGAIN)
+ goto err_out;
+ else if (!ret)
+ break;
+
+ mark_mft_record_dirty(icx->actx->ntfs_ino);
+ ntfs_index_ctx_reinit(icx);
+ }
+
+ mark_mft_record_dirty(icx->actx->ntfs_ino);
+
+ ntfs_index_ctx_put(icx);
+ return 0;
+err_out:
+ ntfs_index_ctx_put(icx);
+ ntfs_error(dir_ni->vol->sb, "Delete failed");
+ return ret;
+}
+
+/*
+ * ntfs_index_walk_down - 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
+ */
+struct index_entry *ntfs_index_walk_down(struct index_entry *ie, struct ntfs_index_context *ictx)
+{
+ struct index_entry *entry;
+ struct index_block *ib;
+ int err;
+ s64 vcn;
+
+ entry = ie;
+ do {
+ vcn = ntfs_ie_get_vcn(entry);
+ if (ictx->is_in_root) {
+ ib = kvzalloc(ictx->block_size, GFP_NOFS);
+ if (!ib)
+ return ERR_PTR(-ENOMEM);
+ /*
+ * Descending from root index (level 0) to the first
+ * child level. is_in_root == true implies pindex == 0,
+ * so advance to level 1.
+ */
+ ictx->pindex = 1;
+ ictx->ir = NULL;
+ ictx->ib = ib;
+ ictx->is_in_root = false;
+ } else {
+ /* down from non-zero level */
+ err = ntfs_icx_parent_inc(ictx);
+ if (err)
+ return ERR_PTR(err);
+ }
+
+ 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 = ERR_PTR(-EIO);
+ } while (!IS_ERR(entry) && (entry->flags & INDEX_ENTRY_NODE));
+
+ return entry;
+}
+
+/*
+ * ntfs_index_walk_up - 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.
+ * @ie: current index entry
+ * @ictx: index context
+ */
+static struct index_entry *ntfs_index_walk_up(struct index_entry *ie,
+ struct ntfs_index_context *ictx)
+{
+ struct index_entry *entry = ie;
+ s64 vcn;
+
+ if (ictx->pindex <= 0)
+ return NULL;
+
+ do {
+ ictx->pindex--;
+ if (!ictx->pindex) {
+ /* we have reached the root */
+ kfree(ictx->ib);
+ ictx->ib = NULL;
+ ictx->is_in_root = true;
+ /* a new search context is to be allocated */
+ if (ictx->actx)
+ ntfs_attr_put_search_ctx(ictx->actx);
+ ictx->ir = ntfs_ir_lookup(ictx->idx_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 = 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 = NULL;
+ }
+ ictx->entry = entry;
+ } while (entry && (ictx->pindex > 0) &&
+ (entry->flags & INDEX_ENTRY_END));
+ return entry;
+}
+
+/*
+ * ntfs_index_next - get next entry in an index according to collating sequence.
+ * 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| |
+ * +---+---+---+---+---+---+---+---+
+ *
+ * @ie: current index entry
+ * @ictx: index context
+ */
+struct index_entry *ntfs_index_next(struct index_entry *ie, struct ntfs_index_context *ictx)
+{
+ struct 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->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 = (struct index_entry *)((char *)ie + le16_to_cpu(ie->length));
+ ++ictx->parent_pos[ictx->pindex];
+ flags = next->flags;
+
+ /* walk down if it has a subnode */
+ if (flags & INDEX_ENTRY_NODE) {
+ if (!ictx->ia_ni) {
+ ictx->ia_ni = ntfs_ia_open(ictx, ictx->idx_ni);
+ if (!ictx->ia_ni)
+ return ERR_PTR(-EIO);
+ }
+
+ next = ntfs_index_walk_down(next, ictx);
+ if (IS_ERR(next))
+ return next;
+ } 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->flags & INDEX_ENTRY_END))
+ next = NULL;
+
+ return next;
+}
generated by cgit v1.3.1 (git 2.54.0) at 2026-10-12 11:14:45 +0000