[PATCH] fs/ntfs3: fix loss of index entries in indx_insert_into_root()

[PATCH] fs/ntfs3: fix loss of index entries in indx_insert_into_root()

[Maciej Sadowniczyk]

When a new entry does not fit into the index root,
indx_insert_into_root() shrinks the root to a single END entry, moves
the root entries into a new index block and inserts the new entry
there. If the new entry does not fit into that block either, a separate
branch is meant to handle it ("MFT record is the same or bigger than
index buffer").

That branch is never taken: its check uses hdr_used, which was read
before hdr_insert_head() copied the root entries into the block, so it
only covers the END entry. hdr_insert_de() then fails and the function
returns -EINVAL with the root already pointing at the new index block,
which is never written. The entries that were in the root are lost.

This needs MFT records as big as the index block (4096 bytes, as
Windows and mkntfs create for 4096-byte sectors) and entries big
enough that the root entries and the new one do not fit into one
block together. With 247- or 255-character names in a new directory
with a short name, creating the 7th file fails with EINVAL and the 6
existing files are gone, also after a remount; the directory then
lists as empty, and lookups and creates in it fail:

  ntfs3(loop0): ino=1b, "d" indx_read_ra
  ntfs3(loop0): ino=1b, "d" ntfs_readdir

When the root that is moved already has subnodes (a later push-down in
a bigger directory), its entries carry the whole tree, so no file in
the directory can be looked up any more. With 243-character names the
32nd create fails, and afterwards none of the 31 files can be
unlinked, although readdir still lists those in the child blocks.

Only re-reading hdr_used is not enough. The branch inserts the new
entry again from the root with indx_insert_entry(), but the new entry
can be a node entry (a key promoted by indx_insert_into_buffer() or
the replacement key in indx_delete_entry()), and indx_find() always
ends at a leaf for a key that is no longer in the tree, so the node
entry would be put into a leaf. The branch also calls fnd_clear() on
the caller's fnd, which releases a buffer that
indx_insert_into_buffer() still uses if the insert fails.

Re-read hdr_used after hdr_insert_head(), and in that branch split the
new block with indx_insert_into_buffer() through a private fnd (the
caller's fnd describes the path to another block, or none): the new
entry goes into the half it belongs to, at its own level, and the
split key is promoted into the root, which at that point holds only its
END entry.

Fixes: 82cae269cfa9 ("fs/ntfs3: Add initialization of super block")
Cc: stable@vger.kernel.org
Signed-off-by: Maciej Sadowniczyk <m.sadowniczyk@gmail.com>
---

Notes:
    Reproducer (as root, ntfs-3g's mkntfs):
    
      truncate -s 256M img
      mkntfs -F -Q -s 4096 img
      mount -t ntfs3 -o loop img /mnt
      mkdir /mnt/d
      x=$(printf '%0254d' 0)
      for c in a b c d e f g; do touch /mnt/d/$c$x; done  # g: EINVAL
      ls /mnt/d | wc -l                                    # 0
    
    Tested on the ntfs3 devel tree (ee1cb3443cff) in a virtme-ng VM with
    KASAN and lockdep. Without this patch the reproducer above lists 0
    files, and after a remount ls fails; with 247-character names 6 files
    are lost as well, and with 243-character names the 32nd create fails
    and none of the 31 files can be unlinked. With it:
    
    - the reproducer lists 7 files, also after a remount;
    - 80 files with 120-, 200-, 230-, 243-, 247- or 255-character names
      created in ascending order, with the listing and an lstat() of every
      name checked after every create; after a remount the listing is
      checked and every file is unlinked;
    - 120 files with 243-, 247- and 255-character names created by ntfs3,
      then the image mounted read-only with ntfs-3g, whose lookup walks the
      B-tree itself: every name is found and listed, an absent one is not;
    - a randomised test of creates, unlinks and renames in one directory,
      3000 operations (names of 1..255 characters, two thirds of them 254
      or 255) and 2000 operations (names of 230..255 characters), with the
      listing and an lstat() of every name and of one absent name checked
      after every operation, then a remount and unlink of everything in a
      seeded order; 4096- and 1024-byte MFT records, three seeds each;
    - failslab with a stack filter and /proc/thread-self/fail-nth, failing
      each allocation in turn in the create that takes the new branch, for
      a leaf entry (255-character names, 7th create) and a node entry
      (247 and 243 characters, 25th and 32nd create): failures of the new
      fnd_get() (node cases), of the nested split's allocations (including
      its indx_new()) and of the caller's split are handled without losing
      entries, and every existing name is still listed and found, also
      after a remount. The only losses come from the outer indx_new()
      failing after the root was shrunk, the separate problem mentioned
      below.
    
    All pass. The randomised, 80-file and failslab runs also checked dmesg:
    no KASAN or lockdep reports (in the randomised runs lockdep was still
    active at the end). The
    patched test kernel carried a local stand-in for "[PATCH v2] fs/ntfs3:
    fix double ni_unlock() in ntfs_readdir()", because that bug otherwise
    turns lockdep off at the first readdir of a directory that does not
    fit into one getdents() buffer.
    
    A temporary printk in the new branch (not part of this patch) showed
    it taken with leaf entries and with node entries in these runs. A
    review of the first version of this patch, which only re-read
    hdr_used, found that it puts such a promoted node entry into a leaf;
    the 247-character test reaches that case at the 25th create.
    
    Not tested: a replacement entry from indx_delete_entry() reaching the
    branch, indexes other than $I30 (no other index has entries big enough
    to reach it), and Windows chkdsk on the resulting images. The 1024-byte
    runs only check for regressions; the branch cannot be reached with
    1 KiB MFT records and 4 KiB index blocks. In one earlier run of an
    older version of the randomised test (1024-byte records, unlink order
    from Python's hash-ordered set) on a kernel with only the hdr_used
    re-read and the ntfs_readdir() stand-in, an unlink of a name that had
    just been listed returned ENOENT after a remount. The branch cannot
    be reached with 1024-byte records, so that kernel behaved like devel
    there; later seeded runs, with renames added, did not show it, and I
    have not analysed it.
    
    A separate problem in the same function, which this patch does not
    address: if indx_new() fails after the root was shrunk (an allocation
    failure), the root is not restored either, and a plain restore does not
    fit back into the MFT record once $INDEX_ALLOCATION has been created.
    I will report that separately.
    
    An AI assistant (Claude Code with Claude Opus 5.5) found this bug while
    reviewing indx_insert_into_root() during my investigation of another
    ntfs3 issue, wrote the tests and drafted the patch and this changelog;
    an AI review of the first version found the node-entry problem. I
    reviewed the patch and the test results.

 fs/ntfs3/index.c | 37 +++++++++++++++++++++++++++++--------
 1 file changed, 29 insertions(+), 8 deletions(-)

diff --git a/fs/ntfs3/index.c b/fs/ntfs3/index.c
index c06b36760..55522da73 100644
--- a/fs/ntfs3/index.c
+++ b/fs/ntfs3/index.c
@@ -1624,6 +1624,13 @@ static int indx_add_allocate(struct ntfs_index *indx, struct ntfs_inode *ni,
 	return err;
 }
 
+static int indx_insert_into_buffer(struct ntfs_index *indx,
+				   struct ntfs_inode *ni,
+				   struct INDEX_ROOT *root,
+				   const struct NTFS_DE *new_de,
+				   const void *ctx, int level,
+				   struct ntfs_fnd *fnd, NTFS_CMP_FUNC cmp);
+
 /*
  * indx_insert_into_root - Attempt to insert an entry into the index root.
  *
@@ -1810,6 +1817,8 @@ static int indx_insert_into_root(struct ntfs_index *indx, struct ntfs_inode *ni,
 		err = -EINVAL;
 		goto out_put_n;
 	}
+	/* hdr_insert_head() has added the root entries. */
+	hdr_used = le32_to_cpu(hdr->used);
 
 	/* Update bitmap attribute. */
 	indx_mark_used(indx, ni, new_vbn >> indx->idx2vbn_bits);
@@ -1818,17 +1827,29 @@ static int indx_insert_into_root(struct ntfs_index *indx, struct ntfs_inode *ni,
 	if (hdr_used + new_de_size > hdr_total) {
 		/*
 		 * This occurs if MFT record is the same or bigger than index
-		 * buffer. Move all root new index and have no space to add
-		 * new entry classic case when MFT record is 1K and index
-		 * buffer 4K the problem should not occurs.
+		 * buffer: the root entries left no room for new_de. The root
+		 * already points at the new buffer, so write it first and then
+		 * split it like any full buffer below the root. new_de may be
+		 * a node entry, so it must go into this buffer, not be inserted
+		 * again from the root. The split key goes into the root, which
+		 * now holds only its END entry, so this branch is not reached
+		 * again.
 		 */
-		kfree(re);
+		struct ntfs_fnd *fnd2;
+
 		indx_write(indx, ni, n, 0);
 
-		put_indx_node(n);
-		fnd_clear(fnd);
-		err = indx_insert_entry(indx, ni, new_de, ctx, fnd, undo);
-		goto out_free_root;
+		fnd2 = fnd_get();
+		if (!fnd2) {
+			err = -ENOMEM;
+			goto out_put_n;
+		}
+		fnd_push(fnd2, n, NULL);
+		n = NULL;
+		err = indx_insert_into_buffer(indx, ni, root, new_de, ctx, 0,
+					      fnd2, cmp);
+		fnd_put(fnd2);
+		goto out_free_re;
 	}
 
 	/*

base-commit: ee1cb3443cff5a800948b662756f75b17ca63fe2
-- 
2.56.0