[PATCH 4/4] fs/ntfs3: fix out-of-bounds access in alloc_rsttbl_from_idx()

[Giulia Aloia <giulia@bynar.io>]

alloc_rsttbl_from_idx() walks the restart table free list until it finds
the requested offset. If the requested entry is not already allocated,
the old code expects to find it in the free list and keeps walking until
it does.

A crafted on-disk restart table can use individually valid free-list
offsets but still omit the requested entry from the list.
When log replay asks alloc_rsttbl_from_idx() to allocate that entry,
the old code keeps following the list without bound checks.

This is reachable by mounting the crafted image on an x86-64 KASAN
kernel before this fix:

KASAN: use-after-free in log_replay+0x8986/0xe690
    Read of size 4 at addr ffff888102477828 by task mount/67
Call Trace:
 log_replay+0x8986/0xe690
 ntfs_loadlog_and_replay+0x3e0/0x500
 ntfs_fill_super+0x1fd3/0x4510
 ...

Validate the requested offset against the table entry size before using
it. Then bound the free-list search by rt->used and reject invalid,
allocated, out-of-range, or misaligned links while walking. If the
requested entry is not found in the bounded walk, return failure instead
of continuing indefinitely.

Fixes: b46acd6a6a62 ("fs/ntfs3: Add NTFS journal")
Cc: stable@vger.kernel.org
Assisted-by: Bynario AI
Signed-off-by: Giulia Aloia <giulia@bynar.io>
---
 fs/ntfs3/fslog.c | 66 ++++++++++++++++++++++++------------------------
 1 file changed, 33 insertions(+), 33 deletions(-)

diff --git a/fs/ntfs3/fslog.c b/fs/ntfs3/fslog.c
index e3b5a19f0e30..1793dd9ccfba 100644
--- a/fs/ntfs3/fslog.c
+++ b/fs/ntfs3/fslog.c
@@ -947,12 +947,20 @@ static inline void *alloc_rsttbl_idx(struct RESTART_TABLE **tbl)
  */
 static inline void *alloc_rsttbl_from_idx(struct RESTART_TABLE **tbl, u32 vbo)
 {
+	u32 i;
 	u32 off;
+	u32 prev_off = 0;
 	__le32 *e;
+	__le32 *prev_e = NULL;
 	struct RESTART_TABLE *rt = *tbl;
 	u32 bytes = bytes_per_rt(rt);
+	u16 used;
 	u16 esize = le16_to_cpu(rt->size);
 
+	if (esize < sizeof(__le32) || vbo < sizeof(struct RESTART_TABLE) ||
+	    (vbo - sizeof(struct RESTART_TABLE)) % esize)
+		return NULL;
+
 	/* If the entry is not the table, we will have to extend the table. */
 	if (vbo >= bytes) {
 		/*
@@ -968,57 +976,49 @@ static inline void *alloc_rsttbl_from_idx(struct RESTART_TABLE **tbl, u32 vbo)
 		*tbl = rt = extend_rsttbl(rt, bytes2idx / esize + 1, bytes);
 		if (!rt)
 			return NULL;
+		bytes = bytes_per_rt(rt);
 	}
 
+	used = le16_to_cpu(rt->used);
+
 	/* See if the entry is already allocated, and just return if it is. */
 	e = Add2Ptr(rt, vbo);
 
 	if (*e == RESTART_ENTRY_ALLOCATED_LE)
 		return e;
 
-	/*
-	 * Walk through the table, looking for the entry we're
-	 * interested and the previous entry.
-	 */
 	off = le32_to_cpu(rt->first_free);
-	e = Add2Ptr(rt, off);
-
-	if (off == vbo) {
-		/* this is a match */
-		rt->first_free = *e;
-		goto skip_looking;
-	}
-
-	/*
-	 * Need to walk through the list looking for the predecessor
-	 * of our entry.
-	 */
-	for (;;) {
-		/* Remember the entry just found */
-		u32 last_off = off;
-		__le32 *last_e = e;
 
-		/* Should never run of entries. */
+	for (i = 0; off; i++) {
+		if (i >= used || off == RESTART_ENTRY_ALLOCATED ||
+		    off < sizeof(struct RESTART_TABLE) ||
+		    off > bytes - sizeof(__le32) ||
+		    (off - sizeof(struct RESTART_TABLE)) % esize) {
+			return NULL;
+		}
 
-		/* Lookup up the next entry the list. */
-		off = le32_to_cpu(*last_e);
 		e = Add2Ptr(rt, off);
 
-		/* If this is our match we are done. */
 		if (off == vbo) {
-			*last_e = *e;
+			if (prev_e) {
+				*prev_e = *e;
 
-			/*
-			 * If this was the last entry, we update that
-			 * table as well.
-			 */
-			if (le32_to_cpu(rt->last_free) == off)
-				rt->last_free = cpu_to_le32(last_off);
-			break;
+				if (le32_to_cpu(rt->last_free) == off)
+					rt->last_free = cpu_to_le32(prev_off);
+			} else {
+				rt->first_free = *e;
+			}
+			goto found;
 		}
+
+		prev_e = e;
+		prev_off = off;
+		off = le32_to_cpu(*e);
 	}
 
-skip_looking:
+	return NULL;
+
+found:
 	/* If the list is now empty, we fix the last_free as well. */
 	if (!rt->first_free)
 		rt->last_free = 0;
-- 
2.55.0