// SPDX-License-Identifier: GPL-2.0-or-later
/*
 * NTFS kernel directory operations.
 *
 * Copyright (c) 2001-2007 Anton Altaparmakov
 * Copyright (c) 2002 Richard Russon
 * Copyright (c) 2025 LG Electronics Co., Ltd.
 */

#include <linux/blkdev.h>

#include "dir.h"
#include "mft.h"
#include "ntfs.h"
#include "index.h"
#include "reparse.h"

#include <linux/filelock.h>

/*
 * The little endian Unicode string $I30 as a global constant.
 */
__le16 I30[5] = { cpu_to_le16('$'), cpu_to_le16('I'),
		cpu_to_le16('3'),	cpu_to_le16('0'), 0 };

static inline u64 ntfs_check_mref(u64 mref)
{
	if (IS_ERR_MREF(mref))
		return ERR_MREF(-EIO);
	return mref;
}

/*
 * ntfs_lookup_inode_by_name - find an inode in a directory given its name
 * @dir_ni:	ntfs inode of the directory in which to search for the name
 * @uname:	Unicode name for which to search in the directory
 * @uname_len:	length of the name @uname in Unicode characters
 * @res:	return the found file name if necessary (see below)
 *
 * Look for an inode with name @uname in the directory with inode @dir_ni.
 * ntfs_lookup_inode_by_name() walks the contents of the directory looking for
 * the Unicode name. If the name is found in the directory, the corresponding
 * inode number (>= 0) is returned as a mft reference in cpu format, i.e. it
 * is a 64-bit number containing the sequence number.
 *
 * On error, a negative value is returned corresponding to the error code. In
 * particular if the inode is not found -ENOENT is returned. Note that you
 * can't just check the return value for being negative, you have to check the
 * inode number for being negative which you can extract using MREC(return
 * value).
 *
 * Note, @uname_len does not include the (optional) terminating NULL character.
 *
 * Note, we look for a case sensitive match first but we also look for a case
 * insensitive match at the same time. If we find a case insensitive match, we
 * save that for the case that we don't find an exact match, where we return
 * the case insensitive match and setup @res (which we allocate!) with the mft
 * reference, the file name type, length and with a copy of the little endian
 * Unicode file name itself. If we match a file name which is in the DOS name
 * space, we only return the mft reference and file name type in @res.
 * ntfs_lookup() then uses this to find the long file name in the inode itself.
 * This is to avoid polluting the dcache with short file names. We want them to
 * work but we don't care for how quickly one can access them. This also fixes
 * the dcache aliasing issues.
 *
 * Locking:  - Caller must hold i_mutex on the directory.
 *	     - Each page cache page in the index allocation mapping must be
 *	       locked whilst being accessed otherwise we may find a corrupt
 *	       page due to it being under ->writepage at the moment which
 *	       applies the mst protection fixups before writing out and then
 *	       removes them again after the write is complete after which it
 *	       unlocks the page.
 */
u64 ntfs_lookup_inode_by_name(struct ntfs_inode *dir_ni, const __le16 *uname,
		const int uname_len, struct ntfs_name **res)
{
	struct ntfs_volume *vol = dir_ni->vol;
	struct super_block *sb = vol->sb;
	struct inode *ia_vi = NULL;
	struct mft_record *m;
	struct index_root *ir;
	struct index_entry *ie;
	struct index_block *ia;
	u8 *index_end;
	u64 mref;
	struct ntfs_attr_search_ctx *ctx;
	int err, rc;
	s64 vcn, old_vcn;
	struct address_space *ia_mapping;
	struct folio *folio;
	u8 *kaddr = NULL;
	struct ntfs_name *name = NULL;

	/* Get hold of the mft record for the directory. */
	m = map_mft_record(dir_ni);
	if (IS_ERR(m)) {
		ntfs_error(sb, "map_mft_record() failed with error code %ld.",
				-PTR_ERR(m));
		return ERR_MREF(PTR_ERR(m));
	}
	ctx = ntfs_attr_get_search_ctx(dir_ni, m);
	if (unlikely(!ctx)) {
		err = -ENOMEM;
		goto err_out;
	}
	/* Find the index root attribute in the mft record. */
	err = ntfs_attr_lookup(AT_INDEX_ROOT, I30, 4, CASE_SENSITIVE, 0, NULL,
			0, ctx);
	if (unlikely(err)) {
		if (err == -ENOENT) {
			ntfs_error(sb,
				"Index root attribute missing in directory inode 0x%llx.",
				dir_ni->mft_no);
			err = -EIO;
		}
		goto err_out;
	}
	/* Get to the index root value (it's been verified in read_inode). */
	ir = (struct index_root *)((u8 *)ctx->attr +
			le16_to_cpu(ctx->attr->data.resident.value_offset));
	index_end = (u8 *)&ir->index + le32_to_cpu(ir->index.index_length);
	/* The first index entry. */
	ie = (struct index_entry *)((u8 *)&ir->index +
			le32_to_cpu(ir->index.entries_offset));
	/*
	 * Loop until we exceed valid memory (corruption case) or until we
	 * reach the last entry.
	 */
	for (;; ie = (struct index_entry *)((u8 *)ie + le16_to_cpu(ie->length))) {
		/* Bounds checks. */
		if ((u8 *)ie < (u8 *)ctx->mrec ||
		    (u8 *)ie + sizeof(struct index_entry_header) > index_end ||
		    (u8 *)ie + sizeof(struct index_entry_header) + le16_to_cpu(ie->key_length) >
				index_end || (u8 *)ie + le16_to_cpu(ie->length) > index_end)
			goto dir_err_out;
		/*
		 * The last entry cannot contain a name. It can however contain
		 * a pointer to a child node in the B+tree so we just break out.
		 */
		if (ie->flags & INDEX_ENTRY_END)
			break;
		/* Key length should not be zero if it is not last entry. */
		if (!ie->key_length)
			goto dir_err_out;
		/*
		 * We perform a case sensitive comparison and if that matches
		 * we are done and return the mft reference of the inode (i.e.
		 * the inode number together with the sequence number for
		 * consistency checking). We convert it to cpu format before
		 * returning.
		 */
		if (ntfs_are_names_equal(uname, uname_len,
				(__le16 *)&ie->key.file_name.file_name,
				ie->key.file_name.file_name_length,
				CASE_SENSITIVE, vol->upcase, vol->upcase_len)) {
found_it:
			/*
			 * We have a perfect match, so we don't need to care
			 * about having matched imperfectly before, so we can
			 * free name and set *res to NULL.
			 * However, if the perfect match is a short file name,
			 * we need to signal this through *res, so that
			 * ntfs_lookup() can fix dcache aliasing issues.
			 * As an optimization we just reuse an existing
			 * allocation of *res.
			 */
			if (ie->key.file_name.file_name_type == FILE_NAME_DOS) {
				if (!name) {
					name = kmalloc_obj(struct ntfs_name,
							   GFP_NOFS);
					if (!name) {
						err = -ENOMEM;
						goto err_out;
					}
				}
				name->mref = le64_to_cpu(
						ie->data.dir.indexed_file);
				name->type = FILE_NAME_DOS;
				name->len = 0;
				*res = name;
			} else {
				kfree(name);
				*res = NULL;
			}
			mref = le64_to_cpu(ie->data.dir.indexed_file);
			ntfs_attr_put_search_ctx(ctx);
			unmap_mft_record(dir_ni);
			return ntfs_check_mref(mref);
		}
		/*
		 * For a case insensitive mount, we also perform a case
		 * insensitive comparison (provided the file name is not in the
		 * POSIX namespace). If the comparison matches, and the name is
		 * in the WIN32 namespace, we cache the filename in *res so
		 * that the caller, ntfs_lookup(), can work on it. If the
		 * comparison matches, and the name is in the DOS namespace, we
		 * only cache the mft reference and the file name type (we set
		 * the name length to zero for simplicity).
		 */
		if ((!NVolCaseSensitive(vol) ||
		     ie->key.file_name.file_name_type == FILE_NAME_DOS) &&
		    ntfs_are_names_equal(uname, uname_len,
					 (__le16 *)&ie->key.file_name.file_name,
					 ie->key.file_name.file_name_length,
					 IGNORE_CASE, vol->upcase,
					 vol->upcase_len)) {
			int name_size = sizeof(struct ntfs_name);
			u8 type = ie->key.file_name.file_name_type;
			u8 len = ie->key.file_name.file_name_length;

			/* Only one case insensitive matching name allowed. */
			if (name) {
				ntfs_error(sb,
					"Found already allocated name in phase 1. Please run chkdsk");
				goto dir_err_out;
			}

			if (type != FILE_NAME_DOS)
				name_size += len * sizeof(__le16);
			name = kmalloc(name_size, GFP_NOFS);
			if (!name) {
				err = -ENOMEM;
				goto err_out;
			}
			name->mref = le64_to_cpu(ie->data.dir.indexed_file);
			name->type = type;
			if (type != FILE_NAME_DOS) {
				name->len = len;
				memcpy(name->name, ie->key.file_name.file_name,
						len * sizeof(__le16));
			} else
				name->len = 0;
			*res = name;
		}
		/*
		 * 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_names(uname, uname_len,
				(__le16 *)&ie->key.file_name.file_name,
				ie->key.file_name.file_name_length, 1,
				IGNORE_CASE, vol->upcase, vol->upcase_len);
		/*
		 * If uname collates before the name of the current entry, there
		 * is definitely no such name 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;
		/* The names are not equal, continue the search. */
		if (rc)
			continue;
		/*
		 * Names match with case insensitive comparison, now try the
		 * case sensitive comparison, which is required for proper
		 * collation.
		 */
		rc = ntfs_collate_names(uname, uname_len,
				(__le16 *)&ie->key.file_name.file_name,
				ie->key.file_name.file_name_length, 1,
				CASE_SENSITIVE, vol->upcase, vol->upcase_len);
		if (rc == -1)
			break;
		if (rc)
			continue;
		/*
		 * Perfect match, this will never happen as the
		 * ntfs_are_names_equal() call will have gotten a match but we
		 * still treat it correctly.
		 */
		goto found_it;
	}
	/*
	 * We have finished with this index without success. Check for the
	 * presence of a child node and if not present return -ENOENT, unless
	 * we have got a matching name cached in name in which case return the
	 * mft reference associated with it.
	 */
	if (!(ie->flags & INDEX_ENTRY_NODE)) {
		if (name) {
			ntfs_attr_put_search_ctx(ctx);
			unmap_mft_record(dir_ni);
			return ntfs_check_mref(name->mref);
		}
		ntfs_debug("Entry not found.");
		err = -ENOENT;
		goto err_out;
	} /* Child node present, descend into it. */

	/* Get the starting vcn of the index_block holding the child node. */
	vcn = le64_to_cpup((__le64 *)((u8 *)ie + le16_to_cpu(ie->length) - 8));

	/*
	 * We are done with the index root and the mft record. Release them,
	 * otherwise we deadlock with read_mapping_folio().
	 */
	ntfs_attr_put_search_ctx(ctx);
	unmap_mft_record(dir_ni);
	m = NULL;
	ctx = NULL;

	ia_vi = ntfs_index_iget(VFS_I(dir_ni), I30, 4);
	if (IS_ERR(ia_vi)) {
		err = PTR_ERR(ia_vi);
		goto err_out;
	}

	ia_mapping = ia_vi->i_mapping;
descend_into_child_node:
	/*
	 * Convert vcn to index into the index allocation attribute in units
	 * of PAGE_SIZE and map the page cache page, reading it from
	 * disk if necessary.
	 */
	folio = read_mapping_folio(ia_mapping, vcn <<
			dir_ni->itype.index.vcn_size_bits >> PAGE_SHIFT, NULL);
	if (IS_ERR(folio)) {
		ntfs_error(sb, "Failed to map directory index page, error %ld.",
				-PTR_ERR(folio));
		err = PTR_ERR(folio);
		goto err_out;
	}

	folio_lock(folio);
	kaddr = kmalloc(PAGE_SIZE, GFP_NOFS);
	if (!kaddr) {
		err = -ENOMEM;
		folio_unlock(folio);
		folio_put(folio);
		goto unm_err_out;
	}

	memcpy_from_folio(kaddr, folio, 0, PAGE_SIZE);
	post_read_mst_fixup((struct ntfs_record *)kaddr, PAGE_SIZE);
	folio_unlock(folio);
	folio_put(folio);
fast_descend_into_child_node:
	/* Get to the index allocation block. */
	ia = (struct index_block *)(kaddr + ((vcn <<
			dir_ni->itype.index.vcn_size_bits) & ~PAGE_MASK));
	/* Bounds checks. */
	if ((u8 *)ia < kaddr || (u8 *)ia > kaddr + PAGE_SIZE) {
		ntfs_error(sb,
			"Out of bounds check failed. Corrupt directory inode 0x%llx or driver bug.",
			dir_ni->mft_no);
		goto unm_err_out;
	}
	index_end = (u8 *)ia + dir_ni->itype.index.block_size;
	if (index_end > kaddr + PAGE_SIZE) {
		ntfs_error(sb,
			   "Index buffer (VCN 0x%llx) of directory inode 0x%llx crosses page boundary. Impossible! Cannot access! This is probably a bug in the driver.",
			   vcn, dir_ni->mft_no);
		goto unm_err_out;
	}
	err = ntfs_index_block_inconsistent(vol, ia,
					    dir_ni->itype.index.block_size,
					    vcn, COLLATION_FILE_NAME,
					    dir_ni->mft_no);
	if (err)
		goto unm_err_out;
	index_end = (u8 *)&ia->index + le32_to_cpu(ia->index.index_length);
	/* The first index entry. */
	ie = (struct index_entry *)((u8 *)&ia->index +
			le32_to_cpu(ia->index.entries_offset));
	/*
	 * Iterate similar to above big loop but applied to index buffer, thus
	 * loop until we exceed valid memory (corruption case) or until we
	 * reach the last entry.
	 */
	for (;; ie = (struct index_entry *)((u8 *)ie + le16_to_cpu(ie->length))) {
		/*
		 * The last entry cannot contain a name. It can however contain
		 * a pointer to a child node in the B+tree so we just break out.
		 */
		if (ie->flags & INDEX_ENTRY_END)
			break;
		/* Key length should not be zero if it is not last entry. */
		if (!ie->key_length)
			goto unm_err_out;
		/*
		 * We perform a case sensitive comparison and if that matches
		 * we are done and return the mft reference of the inode (i.e.
		 * the inode number together with the sequence number for
		 * consistency checking). We convert it to cpu format before
		 * returning.
		 */
		if (ntfs_are_names_equal(uname, uname_len,
				(__le16 *)&ie->key.file_name.file_name,
				ie->key.file_name.file_name_length,
				CASE_SENSITIVE, vol->upcase, vol->upcase_len)) {
found_it2:
			/*
			 * We have a perfect match, so we don't need to care
			 * about having matched imperfectly before, so we can
			 * free name and set *res to NULL.
			 * However, if the perfect match is a short file name,
			 * we need to signal this through *res, so that
			 * ntfs_lookup() can fix dcache aliasing issues.
			 * As an optimization we just reuse an existing
			 * allocation of *res.
			 */
			if (ie->key.file_name.file_name_type == FILE_NAME_DOS) {
				if (!name) {
					name = kmalloc_obj(struct ntfs_name,
							   GFP_NOFS);
					if (!name) {
						err = -ENOMEM;
						goto unm_err_out;
					}
				}
				name->mref = le64_to_cpu(
						ie->data.dir.indexed_file);
				name->type = FILE_NAME_DOS;
				name->len = 0;
				*res = name;
			} else {
				kfree(name);
				*res = NULL;
			}
			mref = le64_to_cpu(ie->data.dir.indexed_file);
			kfree(kaddr);
			iput(ia_vi);
			return ntfs_check_mref(mref);
		}
		/*
		 * For a case insensitive mount, we also perform a case
		 * insensitive comparison (provided the file name is not in the
		 * POSIX namespace). If the comparison matches, and the name is
		 * in the WIN32 namespace, we cache the filename in *res so
		 * that the caller, ntfs_lookup(), can work on it. If the
		 * comparison matches, and the name is in the DOS namespace, we
		 * only cache the mft reference and the file name type (we set
		 * the name length to zero for simplicity).
		 */
		if ((!NVolCaseSensitive(vol) ||
		     ie->key.file_name.file_name_type == FILE_NAME_DOS) &&
		    ntfs_are_names_equal(uname, uname_len,
					 (__le16 *)&ie->key.file_name.file_name,
					 ie->key.file_name.file_name_length,
					 IGNORE_CASE, vol->upcase,
					 vol->upcase_len)) {
			int name_size = sizeof(struct ntfs_name);
			u8 type = ie->key.file_name.file_name_type;
			u8 len = ie->key.file_name.file_name_length;

			/* Only one case insensitive matching name allowed. */
			if (name) {
				ntfs_error(sb,
					"Found already allocated name in phase 2. Please run chkdsk");
				kfree(kaddr);
				goto dir_err_out;
			}

			if (type != FILE_NAME_DOS)
				name_size += len * sizeof(__le16);
			name = kmalloc(name_size, GFP_NOFS);
			if (!name) {
				err = -ENOMEM;
				goto unm_err_out;
			}
			name->mref = le64_to_cpu(ie->data.dir.indexed_file);
			name->type = type;
			if (type != FILE_NAME_DOS) {
				name->len = len;
				memcpy(name->name, ie->key.file_name.file_name,
						len * sizeof(__le16));
			} else
				name->len = 0;
			*res = name;
		}
		/*
		 * 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_names(uname, uname_len,
				(__le16 *)&ie->key.file_name.file_name,
				ie->key.file_name.file_name_length, 1,
				IGNORE_CASE, vol->upcase, vol->upcase_len);
		/*
		 * If uname collates before the name of the current entry, there
		 * is definitely no such name 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;
		/* The names are not equal, continue the search. */
		if (rc)
			continue;
		/*
		 * Names match with case insensitive comparison, now try the
		 * case sensitive comparison, which is required for proper
		 * collation.
		 */
		rc = ntfs_collate_names(uname, uname_len,
				(__le16 *)&ie->key.file_name.file_name,
				ie->key.file_name.file_name_length, 1,
				CASE_SENSITIVE, vol->upcase, vol->upcase_len);
		if (rc == -1)
			break;
		if (rc)
			continue;
		/*
		 * Perfect match, this will never happen as the
		 * ntfs_are_names_equal() call will have gotten a match but we
		 * still treat it correctly.
		 */
		goto found_it2;
	}
	/*
	 * We have finished with this index buffer without success. Check for
	 * the presence of a child node.
	 */
	if (ie->flags & INDEX_ENTRY_NODE) {
		if ((ia->index.flags & NODE_MASK) == LEAF_NODE) {
			ntfs_error(sb,
				"Index entry with child node found in a leaf node in directory inode 0x%llx.",
				dir_ni->mft_no);
			goto unm_err_out;
		}
		/* Child node present, descend into it. */
		old_vcn = vcn;
		vcn = le64_to_cpup((__le64 *)((u8 *)ie +
				le16_to_cpu(ie->length) - 8));
		if (vcn >= 0) {
			/*
			 * If vcn is in the same page cache page as old_vcn we
			 * recycle the mapped page.
			 */
			if (ntfs_cluster_to_pidx(vol, old_vcn) ==
			    ntfs_cluster_to_pidx(vol, vcn))
				goto fast_descend_into_child_node;
			kfree(kaddr);
			kaddr = NULL;
			goto descend_into_child_node;
		}
		ntfs_error(sb, "Negative child node vcn in directory inode 0x%llx.",
				dir_ni->mft_no);
		goto unm_err_out;
	}
	/*
	 * No child node present, return -ENOENT, unless we have got a matching
	 * name cached in name in which case return the mft reference
	 * associated with it.
	 */
	if (name) {
		kfree(kaddr);
		iput(ia_vi);
		return ntfs_check_mref(name->mref);
	}
	ntfs_debug("Entry not found.");
	err = -ENOENT;
unm_err_out:
	kfree(kaddr);
err_out:
	if (!err)
		err = -EIO;
	if (ctx)
		ntfs_attr_put_search_ctx(ctx);
	if (m)
		unmap_mft_record(dir_ni);
	kfree(name);
	*res = NULL;
	if (!IS_ERR_OR_NULL(ia_vi))
		iput(ia_vi);
	return ERR_MREF(err);
dir_err_out:
	ntfs_error(sb, "Corrupt directory.  Aborting lookup.");
	goto err_out;
}

/*
 * ntfs_filldir - ntfs specific filldir method
 * @vol:	current ntfs volume
 * @ndir:	ntfs inode of current directory
 * @ia_page:	page in which the index allocation buffer @ie is in resides
 * @ie:		current index entry
 * @name:	buffer to use for the converted name
 * @actor:	what to feed the entries to
 *
 * Convert the Unicode @name to the loaded NLS and pass it to the @filldir
 * callback.
 *
 * If @ia_page is not NULL it is the locked page containing the index
 * allocation block containing the index entry @ie.
 *
 * Note, we drop (and then reacquire) the page lock on @ia_page across the
 * @filldir() call otherwise we would deadlock with NFSd when it calls ->lookup
 * since ntfs_lookup() will lock the same page.  As an optimization, we do not
 * retake the lock if we are returning a non-zero value as ntfs_readdir()
 * would need to drop the lock immediately anyway.
 */
static inline int ntfs_filldir(struct ntfs_volume *vol,
		struct ntfs_inode *ndir, struct page *ia_page, struct index_entry *ie,
		u8 *name, struct dir_context *actor)
{
	unsigned long mref;
	int name_len;
	unsigned int dt_type;
	u8 name_type;

	name_type = ie->key.file_name.file_name_type;
	if (name_type == FILE_NAME_DOS) {
		ntfs_debug("Skipping DOS name space entry.");
		return 0;
	}
	if (MREF_LE(ie->data.dir.indexed_file) == FILE_root) {
		ntfs_debug("Skipping root directory self reference entry.");
		return 0;
	}
	if (MREF_LE(ie->data.dir.indexed_file) < FILE_first_user &&
			!NVolShowSystemFiles(vol)) {
		ntfs_debug("Skipping system file.");
		return 0;
	}
	if (!NVolShowHiddenFiles(vol) &&
	    (ie->key.file_name.file_attributes & FILE_ATTR_HIDDEN)) {
		ntfs_debug("Skipping hidden file.");
		return 0;
	}

	name_len = ntfs_ucstonls(vol, (__le16 *)&ie->key.file_name.file_name,
			ie->key.file_name.file_name_length, &name,
			NTFS_MAX_NAME_LEN * NLS_MAX_CHARSET_SIZE + 1);
	if (name_len <= 0) {
		ntfs_warning(vol->sb, "Skipping unrepresentable inode 0x%llx.",
				(long long)MREF_LE(ie->data.dir.indexed_file));
		return 0;
	}

	mref = MREF_LE(ie->data.dir.indexed_file);
	if (ie->key.file_name.file_attributes &
			FILE_ATTR_DUP_FILE_NAME_INDEX_PRESENT)
		dt_type = DT_DIR;
	else if (ie->key.file_name.file_attributes & FILE_ATTR_REPARSE_POINT)
		dt_type = ntfs_reparse_tag_dt_types(vol, mref);
	else
		dt_type = DT_REG;

	/*
	 * Drop the page lock otherwise we deadlock with NFS when it calls
	 * ->lookup since ntfs_lookup() will lock the same page.
	 */
	if (ia_page)
		unlock_page(ia_page);
	ntfs_debug("Calling filldir for %s with len %i, fpos 0x%llx, inode 0x%lx, DT_%s.",
		name, name_len, actor->pos, mref, dt_type == DT_DIR ? "DIR" : "REG");
	if (!dir_emit(actor, name, name_len, mref, dt_type))
		return 1;
	/* Relock the page but not if we are aborting ->readdir. */
	if (ia_page)
		lock_page(ia_page);
	return 0;
}

struct ntfs_file_private {
	void *key;
	__le16 key_length;
	bool end_in_iterate;
	loff_t curr_pos;
};

struct ntfs_index_ra {
	unsigned long start_index;
	unsigned int count;
	struct rb_node rb_node;
};

static void ntfs_insert_rb(struct ntfs_index_ra *nir, struct rb_root *root)
{
	struct rb_node **new = &root->rb_node, *parent = NULL;
	struct ntfs_index_ra *cnir;

	while (*new) {
		parent = *new;
		cnir = rb_entry(parent, struct ntfs_index_ra, rb_node);
		if (nir->start_index < cnir->start_index)
			new = &parent->rb_left;
		else if (nir->start_index >= cnir->start_index + cnir->count)
			new = &parent->rb_right;
		else {
			pr_err("nir start index : %ld, count : %d, cnir start_index : %ld, count : %d\n",
				nir->start_index, nir->count, cnir->start_index, cnir->count);
			return;
		}
	}

	rb_link_node(&nir->rb_node, parent, new);
	rb_insert_color(&nir->rb_node, root);
}

static int ntfs_ia_blocks_readahead(struct ntfs_inode *ia_ni, loff_t pos)
{
	unsigned long dir_start_index, dir_end_index;
	struct inode *ia_vi = VFS_I(ia_ni);
	struct file_ra_state *dir_ra;

	dir_end_index = (i_size_read(ia_vi) + PAGE_SIZE - 1) >> PAGE_SHIFT;
	dir_start_index = (pos + PAGE_SIZE - 1) >> PAGE_SHIFT;

	if (dir_start_index >= dir_end_index)
		return 0;

	dir_ra = kzalloc_obj(*dir_ra, GFP_NOFS);
	if (!dir_ra)
		return -ENOMEM;

	file_ra_state_init(dir_ra, ia_vi->i_mapping);
	dir_end_index = (i_size_read(ia_vi) + PAGE_SIZE - 1) >> PAGE_SHIFT;
	dir_start_index = (pos + PAGE_SIZE - 1) >> PAGE_SHIFT;
	dir_ra->ra_pages = dir_end_index - dir_start_index;
	page_cache_sync_readahead(ia_vi->i_mapping, dir_ra, NULL,
			dir_start_index, dir_end_index - dir_start_index);
	kfree(dir_ra);

	return 0;
}

static int ntfs_readdir(struct file *file, struct dir_context *actor)
{
	struct inode *vdir = file_inode(file);
	struct super_block *sb = vdir->i_sb;
	struct ntfs_inode *ndir = NTFS_I(vdir);
	struct ntfs_volume *vol = NTFS_SB(sb);
	struct ntfs_attr_search_ctx *ctx = NULL;
	struct ntfs_index_context *ictx = NULL;
	u8 *name;
	struct index_root *ir;
	struct index_entry *next = NULL;
	struct ntfs_file_private *private = NULL;
	int err = 0;
	loff_t ie_pos = 2; /* initialize it with dot and dotdot size */
	struct ntfs_index_ra *nir = NULL;
	unsigned long index;
	struct rb_root ra_root = RB_ROOT;
	struct file_ra_state *ra;

	ntfs_debug("Entering for inode 0x%llx, fpos 0x%llx.",
			ndir->mft_no, actor->pos);

	if (file->private_data) {
		private = file->private_data;

		if (actor->pos != private->curr_pos) {
			/*
			 * If actor->pos is different from the previous passed
			 * one, Discard the private->key and fill dirent buffer
			 * with linear lookup.
			 */
			kfree(private->key);
			private->key = NULL;
			private->end_in_iterate = false;
		} else if (private->end_in_iterate) {
			kfree(private->key);
			kfree(file->private_data);
			file->private_data = NULL;
			return 0;
		}
	}

	/* Emulate . and .. for all directories. */
	if (!dir_emit_dots(file, actor))
		return 0;

	/*
	 * Allocate a buffer to store the current name being processed
	 * converted to format determined by current NLS.
	 */
	name = kmalloc(NTFS_MAX_NAME_LEN * NLS_MAX_CHARSET_SIZE + 1, GFP_NOFS);
	if (unlikely(!name))
		return -ENOMEM;

	mutex_lock_nested(&ndir->mrec_lock, NTFS_INODE_MUTEX_PARENT);
	ictx = ntfs_index_ctx_get(ndir, I30, 4);
	if (!ictx) {
		kfree(name);
		mutex_unlock(&ndir->mrec_lock);
		return -ENOMEM;
	}

	ra = kzalloc_obj(struct file_ra_state, GFP_NOFS);
	if (!ra) {
		kfree(name);
		ntfs_index_ctx_put(ictx);
		mutex_unlock(&ndir->mrec_lock);
		return -ENOMEM;
	}
	file_ra_state_init(ra, vol->mft_ino->i_mapping);

	if (private && private->key) {
		/*
		 * Find index witk private->key using ntfs_index_lookup()
		 * instead of linear index lookup.
		 */
		err = ntfs_index_lookup(private->key,
					le16_to_cpu(private->key_length),
					ictx);
		if (!err) {
			next = ictx->entry;
			/*
			 * Update ie_pos with private->curr_pos
			 * to make next d_off of dirent correct.
			 */
			ie_pos = private->curr_pos;

			if (actor->pos > vol->mft_record_size && ictx->ia_ni) {
				err = ntfs_ia_blocks_readahead(ictx->ia_ni, actor->pos);
				if (err)
					goto out;
			}

			goto nextdir;
		} else {
			goto out;
		}
	} else if (!private) {
		private = kzalloc_obj(struct ntfs_file_private);
		if (!private) {
			err = -ENOMEM;
			goto out;
		}
		file->private_data = private;
	}

	ctx = ntfs_attr_get_search_ctx(ndir, NULL);
	if (!ctx) {
		err = -ENOMEM;
		goto out;
	}

	/* Find the index root attribute in the mft record. */
	if (ntfs_attr_lookup(AT_INDEX_ROOT, I30, 4, CASE_SENSITIVE, 0, NULL, 0,
				ctx)) {
		ntfs_error(sb, "Index root attribute missing in directory inode %llu",
				ndir->mft_no);
		ntfs_attr_put_search_ctx(ctx);
		err = -ENOMEM;
		goto out;
	}

	/* Get to the index root value. */
	ir = (struct index_root *)((u8 *)ctx->attr +
			le16_to_cpu(ctx->attr->data.resident.value_offset));

	ictx->ir = ir;
	ictx->actx = ctx;
	ictx->parent_vcn[ictx->pindex] = VCN_INDEX_ROOT_PARENT;
	ictx->is_in_root = true;
	ictx->parent_pos[ictx->pindex] = 0;

	ictx->block_size = le32_to_cpu(ir->index_block_size);
	if (ictx->block_size < NTFS_BLOCK_SIZE) {
		ntfs_error(sb, "Index block size (%d) is smaller than the sector size (%d)",
				ictx->block_size, NTFS_BLOCK_SIZE);
		err = -EIO;
		goto out;
	}

	if (vol->cluster_size <= ictx->block_size)
		ictx->vcn_size_bits = vol->cluster_size_bits;
	else
		ictx->vcn_size_bits = NTFS_BLOCK_SIZE_BITS;
	ictx->cr = ir->collation_rule;

	/* The first index entry. */
	next = (struct index_entry *)((u8 *)&ir->index +
			le32_to_cpu(ir->index.entries_offset));

	if (next->flags & INDEX_ENTRY_NODE) {
		ictx->ia_ni = ntfs_ia_open(ictx, ictx->idx_ni);
		if (!ictx->ia_ni) {
			err = -EINVAL;
			goto out;
		}

		err = ntfs_ia_blocks_readahead(ictx->ia_ni, actor->pos);
		if (err)
			goto out;
	}

	if (next->flags & INDEX_ENTRY_NODE) {
		next = ntfs_index_walk_down(next, ictx);
		if (IS_ERR(next)) {
			err = PTR_ERR(next);
			goto out;
		}
	}

	if (next && !(next->flags & INDEX_ENTRY_END))
		goto nextdir;

	while (1) {
		next = ntfs_index_next(next, ictx);
		if (IS_ERR(next)) {
			err = PTR_ERR(next);
			goto out;
		}
		if (!next)
			break;
nextdir:
		if (ie_pos < actor->pos) {
			ie_pos += le16_to_cpu(next->length);
			continue;
		}

		actor->pos = ie_pos;

		index = ntfs_mft_no_to_pidx(vol,
				MREF_LE(next->data.dir.indexed_file));
		if (nir) {
			struct ntfs_index_ra *cnir;
			struct rb_node *node = ra_root.rb_node;

			if (nir->start_index <= index &&
			    index < nir->start_index + nir->count) {
				/* No behavior */
				goto filldir;
			}

			while (node) {
				cnir = rb_entry(node, struct ntfs_index_ra, rb_node);
				if (cnir->start_index <= index &&
				    index < cnir->start_index + cnir->count) {
					goto filldir;
				} else if (cnir->start_index + cnir->count == index) {
					cnir->count++;
					goto filldir;
				} else if (!cnir->start_index && cnir->start_index - 1 == index) {
					cnir->start_index = index;
					goto filldir;
				}

				if (index < cnir->start_index)
					node = node->rb_left;
				else if (index >= cnir->start_index + cnir->count)
					node = node->rb_right;
			}

			if (nir->start_index + nir->count == index) {
				nir->count++;
			} else if (!nir->start_index && nir->start_index - 1 == index) {
				nir->start_index = index;
			} else if (nir->count > 2) {
				ntfs_insert_rb(nir, &ra_root);
				nir = NULL;
			} else {
				nir->start_index = index;
				nir->count = 1;
			}
		}

		if (!nir) {
			nir = kzalloc_obj(struct ntfs_index_ra);
			if (nir) {
				nir->start_index = index;
				nir->count = 1;
			}
		}

filldir:
		/* Submit the name to the filldir callback. */
		err = ntfs_filldir(vol, ndir, NULL, next, name, actor);
		if (err) {
			/*
			 * Store index key value to file private_data to start
			 * from current index offset on next round.
			 */
			private = file->private_data;
			kfree(private->key);
			private->key = kmemdup(&next->key.file_name,
					le16_to_cpu(next->key_length),
					GFP_KERNEL);
			if (!private->key) {
				err = -ENOMEM;
				goto out;
			}

			private->key_length = next->key_length;
			break;
		}
		ie_pos += le16_to_cpu(next->length);
	}

	if (!err)
		private->end_in_iterate = true;
	else
		err = 0;

	private->curr_pos = actor->pos = ie_pos;
out:
	while (!RB_EMPTY_ROOT(&ra_root)) {
		struct ntfs_index_ra *cnir;
		struct rb_node *node;

		node = rb_first(&ra_root);
		cnir = rb_entry(node, struct ntfs_index_ra, rb_node);
		ra->ra_pages = cnir->count;
		page_cache_sync_readahead(vol->mft_ino->i_mapping, ra, NULL,
				cnir->start_index, cnir->count);
		rb_erase(node, &ra_root);
		kfree(cnir);
	}

	if (err) {
		if (private) {
			private->curr_pos = actor->pos;
			private->end_in_iterate = true;
		}
		err = 0;
	}
	ntfs_index_ctx_put(ictx);
	kfree(name);
	kfree(nir);
	kfree(ra);
	mutex_unlock(&ndir->mrec_lock);
	return err;
}

int ntfs_check_empty_dir(struct ntfs_inode *ni, struct mft_record *ni_mrec)
{
	struct ntfs_attr_search_ctx *ctx;
	int ret = 0;

	if (!(ni_mrec->flags & MFT_RECORD_IS_DIRECTORY))
		return 0;

	ctx = ntfs_attr_get_search_ctx(ni, NULL);
	if (!ctx) {
		ntfs_error(ni->vol->sb, "Failed to get search context");
		return -ENOMEM;
	}

	/* Find the index root attribute in the mft record. */
	ret = ntfs_attr_lookup(AT_INDEX_ROOT, I30, 4, CASE_SENSITIVE, 0, NULL,
				0, ctx);
	if (ret) {
		ntfs_error(ni->vol->sb, "Index root attribute missing in directory inode %llu",
				ni->mft_no);
		ntfs_attr_put_search_ctx(ctx);
		return ret;
	}

	/* Non-empty directory? */
	if (le32_to_cpu(ctx->attr->data.resident.value_length) !=
	    sizeof(struct index_root) + sizeof(struct index_entry_header)) {
		/* Both ENOTEMPTY and EEXIST are ok. We use the more common. */
		ret = -ENOTEMPTY;
		ntfs_debug("Directory is not empty\n");
	}

	ntfs_attr_put_search_ctx(ctx);

	return ret;
}

/*
 * ntfs_dir_open - called when an inode is about to be opened
 * @vi:		inode to be opened
 * @filp:	file structure describing the inode
 *
 * Limit directory size to the page cache limit on architectures where unsigned
 * long is 32-bits. This is the most we can do for now without overflowing the
 * page cache page index. Doing it this way means we don't run into problems
 * because of existing too large directories. It would be better to allow the
 * user to read the accessible part of the directory but I doubt very much
 * anyone is going to hit this check on a 32-bit architecture, so there is no
 * point in adding the extra complexity required to support this.
 *
 * On 64-bit architectures, the check is hopefully optimized away by the
 * compiler.
 */
static int ntfs_dir_open(struct inode *vi, struct file *filp)
{
	if (sizeof(unsigned long) < 8) {
		if (i_size_read(vi) > MAX_LFS_FILESIZE)
			return -EFBIG;
	}
	return 0;
}

static int ntfs_dir_release(struct inode *vi, struct file *filp)
{
	if (filp->private_data) {
		kfree(((struct ntfs_file_private *)filp->private_data)->key);
		kfree(filp->private_data);
		filp->private_data = NULL;
	}
	return 0;
}

/*
 * ntfs_dir_fsync - sync a directory to disk
 * @filp:	file describing the directory to be synced
 * @start:	start offset to be synced
 * @end:	end offset to be synced
 * @datasync:	if non-zero only flush user data and not metadata
 *
 * Data integrity sync of a directory to disk.  Used for fsync, fdatasync, and
 * msync system calls.  This function is based on file.c::ntfs_file_fsync().
 *
 * Write the mft record and all associated extent mft records as well as the
 * $INDEX_ALLOCATION and $BITMAP attributes and then sync the block device.
 *
 * If @datasync is true, we do not wait on the inode(s) to be written out
 * but we always wait on the page cache pages to be written out.
 *
 * Note: In the past @filp could be NULL so we ignore it as we don't need it
 * anyway.
 *
 * Locking: Caller must hold i_mutex on the inode.
 */
static int ntfs_dir_fsync(struct file *filp, loff_t start, loff_t end,
			  int datasync)
{
	struct inode *bmp_vi, *vi = filp->f_mapping->host;
	struct ntfs_volume *vol = NTFS_I(vi)->vol;
	struct ntfs_inode *ni = NTFS_I(vi);
	struct ntfs_attr_search_ctx *ctx;
	struct inode *parent_vi, *ia_vi;
	int err, ret;
	struct ntfs_attr na;

	ntfs_debug("Entering for inode 0x%llx.", ni->mft_no);

	if (NVolShutdown(vol))
		return -EIO;

	ctx = ntfs_attr_get_search_ctx(ni, NULL);
	if (!ctx)
		return -ENOMEM;

	mutex_lock_nested(&ni->mrec_lock, NTFS_INODE_MUTEX_NORMAL_CHILD);
	while (!(err = ntfs_attr_lookup(AT_FILE_NAME, NULL, 0, 0, 0, NULL, 0, ctx))) {
		struct file_name_attr *fn = (struct file_name_attr *)((u8 *)ctx->attr +
				le16_to_cpu(ctx->attr->data.resident.value_offset));

		if (MREF_LE(fn->parent_directory) == ni->mft_no)
			continue;

		parent_vi = ntfs_iget(vi->i_sb, MREF_LE(fn->parent_directory));
		if (IS_ERR(parent_vi))
			continue;
		mutex_lock_nested(&NTFS_I(parent_vi)->mrec_lock, NTFS_INODE_MUTEX_NORMAL);
		ia_vi = ntfs_index_iget(parent_vi, I30, 4);
		mutex_unlock(&NTFS_I(parent_vi)->mrec_lock);
		if (IS_ERR(ia_vi)) {
			iput(parent_vi);
			continue;
		}
		write_inode_now(ia_vi, 1);
		iput(ia_vi);
		write_inode_now(parent_vi, 1);
		iput(parent_vi);
	}
	mutex_unlock(&ni->mrec_lock);
	ntfs_attr_put_search_ctx(ctx);

	err = file_write_and_wait_range(filp, start, end);
	if (err)
		return err;
	inode_lock(vi);

	/* If the bitmap attribute inode is in memory sync it, too. */
	na.mft_no = vi->i_ino;
	na.type = AT_BITMAP;
	na.name = I30;
	na.name_len = 4;
	bmp_vi = ilookup5(vi->i_sb, vi->i_ino, ntfs_test_inode, &na);
	if (bmp_vi) {
		write_inode_now(bmp_vi, !datasync);
		iput(bmp_vi);
	}
	ret = __ntfs_write_inode(vi, 1);

	write_inode_now(vi, !datasync);

	write_inode_now(vol->mftbmp_ino, 1);
	down_write(&vol->lcnbmp_lock);
	write_inode_now(vol->lcnbmp_ino, 1);
	up_write(&vol->lcnbmp_lock);
	write_inode_now(vol->mft_ino, 1);

	err = sync_blockdev(vi->i_sb->s_bdev);
	if (unlikely(err && !ret))
		ret = err;
	if (likely(!ret))
		ntfs_debug("Done.");
	else
		ntfs_warning(vi->i_sb,
			"Failed to f%ssync inode 0x%llx.  Error %u.",
			datasync ? "data" : "", ni->mft_no, -ret);
	inode_unlock(vi);
	return ret;
}

const struct file_operations ntfs_dir_ops = {
	.llseek		= generic_file_llseek,	/* Seek inside directory. */
	.read		= generic_read_dir,	/* Return -EISDIR. */
	.iterate_shared	= ntfs_readdir,		/* Read directory contents. */
	.fsync		= ntfs_dir_fsync,	/* Sync a directory to disk. */
	.open		= ntfs_dir_open,	/* Open directory. */
	.release	= ntfs_dir_release,
	.unlocked_ioctl	= ntfs_ioctl,
#ifdef CONFIG_COMPAT
	.compat_ioctl	= ntfs_compat_ioctl,
#endif
	.setlease	= generic_setlease,
};