[PATCH 0/2] omfs: detect metadata chain cycles

[PATCH 0/2] omfs: detect metadata chain cycles

[이상호]

OMFS stores directory sibling chains and file extent continuation chains
on disk. Both chains are terminated by ~0, but the next block values are
image-controlled.

A crafted filesystem can create a cycle in either chain. Lookup of a
missing directory entry or read of a file with a cyclic extent
continuation then loops in the kernel.

This series detects cycles in both metadata chains. I verified the fixes
with crafted OMFS images:

- directory sibling self-cycle:
  unpatched kernel timed out after "statting /mnt/missing";
  patched kernel returned ELOOP.

- file extent continuation self-cycle:
  unpatched kernel timed out after "reading /mnt/loopfile";
  patched kernel returned from read with EIO.

Valid directory and file images continued to behave normally.

이상호 (2):
  omfs: detect directory sibling chain cycles
  omfs: detect file extent chain cycles

 fs/omfs/dir.c  | 64 +++++++++++++++++++++++++++++++++++++++-
 fs/omfs/file.c | 79 +++++++++++++++++++++++++++++++++++++++++++++++++-
 2 files changed, 141 insertions(+), 2 deletions(-)

-- 
2.43.0

[PATCH 1/2] omfs: detect directory sibling chain cycles

[이상호]

OMFS directory lookup follows an on-disk sibling chain until it
reaches the ~0 terminator.

The sibling block number is image-controlled, so a crafted image can
point an entry back to itself or create a small cycle. Lookup of a
missing name in that hash bucket then spins in the kernel.

Detect cycles in OMFS directory sibling chains and return -ELOOP from
lookup when a cycle is found. Readdir uses the same detection to stop
traversing malformed chains.

Fixes: a3ab7155ea21 ("omfs: add directory routines")
Signed-off-by: 이상호 <kudo3228@gmail.com>
---
 fs/omfs/dir.c | 64 ++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 63 insertions(+), 1 deletion(-)

diff --git a/fs/omfs/dir.c b/fs/omfs/dir.c
index 2ed541fccf33..11b680f1c383 100644
--- a/fs/omfs/dir.c
+++ b/fs/omfs/dir.c
@@ -31,6 +31,56 @@ static struct buffer_head *omfs_get_bucket(struct inode *dir,
 	return omfs_bread(dir->i_sb, dir->i_ino);
 }
 
+static int omfs_get_sibling(struct inode *dir, u64 block, u64 *sibling)
+{
+	struct buffer_head *bh;
+	struct omfs_inode *oi;
+
+	bh = omfs_bread(dir->i_sb, block);
+	if (!bh)
+		return -EIO;
+
+	oi = (struct omfs_inode *)bh->b_data;
+	if (omfs_is_bad(OMFS_SB(dir->i_sb), &oi->i_head, block)) {
+		brelse(bh);
+		return -EIO;
+	}
+
+	*sibling = be64_to_cpu(oi->i_sibling);
+	brelse(bh);
+	return 0;
+}
+
+static int omfs_check_chain_cycle(struct inode *dir, u64 *slow, u64 *fast)
+{
+	int err;
+
+	if (*fast == ~0)
+		return 0;
+
+	err = omfs_get_sibling(dir, *fast, fast);
+	if (err)
+		return err;
+
+	if (*fast == ~0)
+		return 0;
+
+	err = omfs_get_sibling(dir, *fast, fast);
+	if (err)
+		return err;
+
+	if (*slow != ~0) {
+		err = omfs_get_sibling(dir, *slow, slow);
+		if (err)
+			return err;
+	}
+
+	if (*slow != ~0 && *slow == *fast)
+		return -ELOOP;
+
+	return 0;
+}
+
 static struct buffer_head *omfs_scan_list(struct inode *dir, u64 block,
 				const char *name, int namelen,
 				u64 *prev_block)
@@ -38,6 +88,8 @@ static struct buffer_head *omfs_scan_list(struct inode *dir, u64 block,
 	struct buffer_head *bh;
 	struct omfs_inode *oi;
 	int err = -ENOENT;
+	u64 slow = block;
+	u64 fast = block;
 	*prev_block = ~0;
 
 	while (block != ~0) {
@@ -59,6 +111,10 @@ static struct buffer_head *omfs_scan_list(struct inode *dir, u64 block,
 		*prev_block = block;
 		block = be64_to_cpu(oi->i_sibling);
 		brelse(bh);
+
+		err = omfs_check_chain_cycle(dir, &slow, &fast);
+		if (err)
+			goto err;
 	}
 err:
 	return ERR_PTR(err);
@@ -331,12 +387,15 @@ static bool omfs_fill_chain(struct inode *dir, struct dir_context *ctx,
 		u64 fsblock, int hindex)
 {
 	/* follow chain in this bucket */
+	u64 slow = fsblock;
+	u64 fast = fsblock;
 	while (fsblock != ~0) {
-		struct buffer_head *bh = omfs_bread(dir->i_sb, fsblock);
+		struct buffer_head *bh;
 		struct omfs_inode *oi;
 		u64 self;
 		unsigned char d_type;
 
+		bh = omfs_bread(dir->i_sb, fsblock);
 		if (!bh)
 			return true;
 
@@ -366,6 +425,9 @@ static bool omfs_fill_chain(struct inode *dir, struct dir_context *ctx,
 		}
 		brelse(bh);
 		ctx->pos++;
+
+		if (omfs_check_chain_cycle(dir, &slow, &fast))
+			return true;
 	}
 	return true;
 }
-- 
2.43.0

[PATCH 2/2] omfs: detect file extent chain cycles

[이상호]

OMFS file block lookup follows an on-disk extent continuation chain
until e_next reaches ~0.

The continuation block number is image-controlled. A crafted filesystem
can point a continuation table back to itself, making read paths loop in
the kernel while resolving a file block.

Detect cycles in OMFS extent continuation chains and return -ELOOP when
a cycle is found. Apply the same detection to truncate-to-zero cleanup.

Fixes: a3ab7155ea21 ("omfs: add directory routines")
Signed-off-by: 이상호 <kudo3228@gmail.com>
---
 fs/omfs/file.c | 79 +++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 78 insertions(+), 1 deletion(-)

diff --git a/fs/omfs/file.c b/fs/omfs/file.c
index 28f3b113340e..8e4e9660789a 100644
--- a/fs/omfs/file.c
+++ b/fs/omfs/file.c
@@ -17,6 +17,70 @@ static u32 omfs_max_extents(struct omfs_sb_info *sbi, int offset)
 		sizeof(struct omfs_extent_entry);
 }
 
+static int omfs_extent_table_offset(struct inode *inode, u64 block)
+{
+	return block == inode->i_ino ? OMFS_EXTENT_START : OMFS_EXTENT_CONT;
+}
+
+static int omfs_extent_next(struct inode *inode, u64 block, u64 *next)
+{
+	struct omfs_sb_info *sbi = OMFS_SB(inode->i_sb);
+	struct buffer_head *bh;
+	struct omfs_extent *oe;
+	u32 extent_count;
+	int offset = omfs_extent_table_offset(inode, block);
+
+	bh = omfs_bread(inode->i_sb, block);
+	if (!bh)
+		return -EIO;
+
+	if (omfs_is_bad(sbi, (struct omfs_header *)bh->b_data, block)) {
+		brelse(bh);
+		return -EIO;
+	}
+
+	oe = (struct omfs_extent *)&bh->b_data[offset];
+	extent_count = be32_to_cpu(oe->e_extent_count);
+	if (extent_count > omfs_max_extents(sbi, offset)) {
+		brelse(bh);
+		return -EIO;
+	}
+
+	*next = be64_to_cpu(oe->e_next);
+	brelse(bh);
+	return 0;
+}
+
+static int omfs_check_extent_cycle(struct inode *inode, u64 *slow, u64 *fast)
+{
+	int err;
+
+	if (*fast == ~0)
+		return 0;
+
+	err = omfs_extent_next(inode, *fast, fast);
+	if (err)
+		return err;
+
+	if (*fast == ~0)
+		return 0;
+
+	err = omfs_extent_next(inode, *fast, fast);
+	if (err)
+		return err;
+
+	if (*slow != ~0) {
+		err = omfs_extent_next(inode, *slow, slow);
+		if (err)
+			return err;
+	}
+
+	if (*slow != ~0 && *slow == *fast)
+		return -ELOOP;
+
+	return 0;
+}
+
 void omfs_make_empty_table(struct buffer_head *bh, int offset)
 {
 	struct omfs_extent *oe = (struct omfs_extent *) &bh->b_data[offset];
@@ -35,6 +99,7 @@ int omfs_shrink_inode(struct inode *inode)
 	struct omfs_extent_entry *entry;
 	struct buffer_head *bh;
 	u64 next, last;
+	u64 slow, fast;
 	u32 extent_count;
 	u32 max_extents;
 	int ret;
@@ -43,6 +108,8 @@ int omfs_shrink_inode(struct inode *inode)
 	 * than inode->i_size;
 	 */
 	next = inode->i_ino;
+	slow = next;
+	fast = next;
 
 	/* only support truncate -> 0 for now */
 	ret = -EIO;
@@ -70,6 +137,10 @@ int omfs_shrink_inode(struct inode *inode)
 		next = be64_to_cpu(oe->e_next);
 		entry = oe->e_entry;
 
+		ret = omfs_check_extent_cycle(inode, &slow, &fast);
+		if (ret)
+			goto out_brelse;
+
 		/* ignore last entry as it is the terminator */
 		for (; extent_count > 1; extent_count--) {
 			u64 start, count;
@@ -228,6 +299,7 @@ static int omfs_get_block(struct inode *inode, sector_t block,
 	struct omfs_sb_info *sbi = OMFS_SB(inode->i_sb);
 	int max_blocks = bh_result->b_size >> inode->i_blkbits;
 	int remain;
+	u64 slow, fast;
 
 	ret = -EIO;
 	bh = omfs_bread(inode->i_sb, inode->i_ino);
@@ -237,6 +309,8 @@ static int omfs_get_block(struct inode *inode, sector_t block,
 	oe = (struct omfs_extent *)(&bh->b_data[OMFS_EXTENT_START]);
 	max_extents = omfs_max_extents(sbi, OMFS_EXTENT_START);
 	next = inode->i_ino;
+	slow = next;
+	fast = next;
 
 	for (;;) {
 
@@ -262,6 +336,10 @@ static int omfs_get_block(struct inode *inode, sector_t block,
 		if (next == ~0)
 			break;
 
+		ret = omfs_check_extent_cycle(inode, &slow, &fast);
+		if (ret)
+			goto out_brelse;
+
 		brelse(bh);
 		bh = omfs_bread(inode->i_sb, next);
 		if (!bh)
@@ -377,4 +455,3 @@ const struct address_space_operations omfs_aops = {
 	.bmap = omfs_bmap,
 	.migrate_folio = buffer_migrate_folio,
 };
-
-- 
2.43.0