[PATCH 2/2] ext4: Avoid cycles in directory h-tree

[PATCH 2/2] ext4: Avoid cycles in directory h-tree

[Jan Kara]

A maliciously corrupted filesystem can contain cycles in the h-tree
stored inside a directory. That can easily lead to the kernel corrupting
tree nodes that were already verified under its hands while doing a node
split and consequently accessing unallocated memory. Fix the problem by
verifying traversed block numbers are unique.

CC: stable@vger.kernel.org
Signed-off-by: Jan Kara <jack@suse.cz>
---
 fs/ext4/namei.c | 24 ++++++++++++++++++++----
 1 file changed, 20 insertions(+), 4 deletions(-)

diff --git a/fs/ext4/namei.c b/fs/ext4/namei.c
index ca6ee9940599..06441ad6104d 100644
--- a/fs/ext4/namei.c
+++ b/fs/ext4/namei.c
@@ -777,12 +777,14 @@ static struct dx_frame *
 dx_probe(struct ext4_filename *fname, struct inode *dir,
 	 struct dx_hash_info *hinfo, struct dx_frame *frame_in)
 {
-	unsigned count, indirect;
+	unsigned count, indirect, level, i;
 	struct dx_entry *at, *entries, *p, *q, *m;
 	struct dx_root *root;
 	struct dx_frame *frame = frame_in;
 	struct dx_frame *ret_err = ERR_PTR(ERR_BAD_DX_DIR);
 	u32 hash;
+	ext4_lblk_t block;
+	ext4_lblk_t blocks[EXT4_HTREE_LEVEL];
 
 	memset(frame_in, 0, EXT4_HTREE_LEVEL * sizeof(frame_in[0]));
 	frame->bh = ext4_read_dirblock(dir, 0, INDEX);
@@ -854,6 +856,8 @@ dx_probe(struct ext4_filename *fname, struct inode *dir,
 	}
 
 	dxtrace(printk("Look up %x", hash));
+	level = 0;
+	blocks[0] = 0;
 	while (1) {
 		count = dx_get_count(entries);
 		if (!count || count > dx_get_limit(entries)) {
@@ -882,15 +886,27 @@ dx_probe(struct ext4_filename *fname, struct inode *dir,
 			       dx_get_block(at)));
 		frame->entries = entries;
 		frame->at = at;
-		if (!indirect--)
+
+		block = dx_get_block(at);
+		for (i = 0; i <= level; i++) {
+			if (blocks[i] == block) {
+				ext4_warning_inode(dir,
+					"dx entry: tree cycle block %u points back to block %u",
+					blocks[level], block);
+				goto fail;
+			}
+		}
+		blocks[++level] = block;
+		if (level > indirect)
 			return frame;
 		frame++;
-		frame->bh = ext4_read_dirblock(dir, dx_get_block(at), INDEX);
+		frame->bh = ext4_read_dirblock(dir, block, INDEX);
 		if (IS_ERR(frame->bh)) {
 			ret_err = (struct dx_frame *) frame->bh;
 			frame->bh = NULL;
 			goto fail;
 		}
+
 		entries = ((struct dx_node *) frame->bh->b_data)->entries;
 
 		if (dx_get_limit(entries) != dx_node_limit(dir)) {
@@ -1278,7 +1294,7 @@ static int dx_make_map(struct inode *dir, struct buffer_head *bh,
 			count++;
 			cond_resched();
 		}
-		de = ext4_next_entry(de, blocksize);
+		de = ext4_next_entry(de, dir->i_sb->s_blocksize);
 	}
 	return count;
 }
-- 
2.34.1

Re: [PATCH 2/2] ext4: Avoid cycles in directory h-tree

[Theodore Ts'o]

On Thu, Apr 28, 2022 at 08:31:38PM +0200, Jan Kara wrote:
> A maliciously corrupted filesystem can contain cycles in the h-tree
> stored inside a directory. That can easily lead to the kernel corrupting
> tree nodes that were already verified under its hands while doing a node
> split and consequently accessing unallocated memory. Fix the problem by
> verifying traversed block numbers are unique.
> 
> CC: stable@vger.kernel.org
> Signed-off-by: Jan Kara <jack@suse.cz>

When I tried applying this patch, I got this crash:

ext4/052 23s ... 	[19:28:41][    2.683407] run fstests ext4/052 at 2022-05-17 19:28:41
[    5.433672] Kernel panic - not syncing: stack-protector: Kernel stack is corrupted in: dx_probe+0x629/0x630
[    5.434449] CPU: 0 PID: 2468 Comm: dirstress Not tainted 5.18.0-rc5-xfstests-00019-g204e6b4d4cc1 #610
[    5.435012] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.15.0-1 04/01/2014
[    5.435501] Call Trace:
[    5.435659]  <TASK>
[    5.435791]  dump_stack_lvl+0x34/0x44
[    5.436027]  panic+0x107/0x28f
[    5.436221]  ? dx_probe+0x629/0x630
[    5.436430]  __stack_chk_fail+0x10/0x10
[    5.436663]  dx_probe+0x629/0x630
[    5.436869]  ext4_dx_add_entry+0x54/0x700
[    5.437176]  ext4_add_entry+0x38d/0x4e0
[    5.437421]  ext4_add_nondir+0x2b/0xc0
[    5.437647]  ext4_symlink+0x1c5/0x390
[    5.437869]  vfs_symlink+0x184/0x220
[    5.438095]  do_symlinkat+0x7a/0x110
[    5.438313]  __x64_sys_symlink+0x38/0x40
[    5.438548]  do_syscall_64+0x38/0x90
[    5.438762]  entry_SYSCALL_64_after_hwframe+0x44/0xae
[    5.439070] RIP: 0033:0x7f8137109a97
[    5.439285] Code: f0 ff ff 73 01 c3 48 8b 0d f6 d3 0c 00 f7 d8 64 89 01 48 83 c8 ff c3 66 2e 0f 1f 84 00 00 00 00 00 66 90 b8 58 00 00 00 0f 05 <48> 3d 01 f0 ff ff 73 01 c3 48 8b 0d c9 d3 0c 00 f7 d8 64 89 01 48
[    5.440374] RSP: 002b:00007ffc514a2428 EFLAGS: 00000246 ORIG_RAX: 0000000000000058
[    5.440820] RAX: ffffffffffffffda RBX: 0000000000035d4a RCX: 00007f8137109a97
[    5.441278] RDX: 0000000000000000 RSI: 00007ffc514a2450 RDI: 00007ffc514a2450
[    5.441734] RBP: 0000000000000003 R08: 0000000000000000 R09: 0000000000000013
[    5.442153] R10: 00007ffc514a21c2 R11: 0000000000000246 R12: 0000000000061a80
[    5.442571] R13: 0000000000000000 R14: 00007ffc514a2450 R15: 00007ffc514a2c50
[    5.442989]  </TASK>
[    5.443289] Kernel Offset: disabled
[    5.443517] Rebooting in 5 seconds..

Applying just the first patch series (plus the patch hunk from this
commit needed so that the first patch compiles) does not result in a
crash, so the problem is clearly with this change.

Looking more closely at ext4/052 which tests the large_dir feature,
and then looking at the patch, I suspect the fix which is needed
is:

> +	ext4_lblk_t blocks[EXT4_HTREE_LEVEL];

needs to be

	ext4_lblk_t blocks[EXT4_HTREE_LEVEL + 1];

Otherwise on large htree which is 3 levels deep, this

> +		blocks[++level] = block;

is going to end up smashing the stack.

Jan, do you agree?

							- Ted

Re: [PATCH 2/2] ext4: Avoid cycles in directory h-tree

[Jan Kara]

On Tue 17-05-22 19:55:47, Theodore Ts'o wrote:
> On Thu, Apr 28, 2022 at 08:31:38PM +0200, Jan Kara wrote:
> > A maliciously corrupted filesystem can contain cycles in the h-tree
> > stored inside a directory. That can easily lead to the kernel corrupting
> > tree nodes that were already verified under its hands while doing a node
> > split and consequently accessing unallocated memory. Fix the problem by
> > verifying traversed block numbers are unique.
> > 
> > CC: stable@vger.kernel.org
> > Signed-off-by: Jan Kara <jack@suse.cz>
> 
> When I tried applying this patch, I got this crash:
> 
> ext4/052 23s ... 	[19:28:41][    2.683407] run fstests ext4/052 at 2022-05-17 19:28:41
> [    5.433672] Kernel panic - not syncing: stack-protector: Kernel stack is corrupted in: dx_probe+0x629/0x630
> [    5.434449] CPU: 0 PID: 2468 Comm: dirstress Not tainted 5.18.0-rc5-xfstests-00019-g204e6b4d4cc1 #610
> [    5.435012] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.15.0-1 04/01/2014
> [    5.435501] Call Trace:
> [    5.435659]  <TASK>
> [    5.435791]  dump_stack_lvl+0x34/0x44
> [    5.436027]  panic+0x107/0x28f
> [    5.436221]  ? dx_probe+0x629/0x630
> [    5.436430]  __stack_chk_fail+0x10/0x10
> [    5.436663]  dx_probe+0x629/0x630
> [    5.436869]  ext4_dx_add_entry+0x54/0x700
> [    5.437176]  ext4_add_entry+0x38d/0x4e0
> [    5.437421]  ext4_add_nondir+0x2b/0xc0
> [    5.437647]  ext4_symlink+0x1c5/0x390
> [    5.437869]  vfs_symlink+0x184/0x220
> [    5.438095]  do_symlinkat+0x7a/0x110
> [    5.438313]  __x64_sys_symlink+0x38/0x40
> [    5.438548]  do_syscall_64+0x38/0x90
> [    5.438762]  entry_SYSCALL_64_after_hwframe+0x44/0xae
> [    5.439070] RIP: 0033:0x7f8137109a97
> [    5.439285] Code: f0 ff ff 73 01 c3 48 8b 0d f6 d3 0c 00 f7 d8 64 89 01 48 83 c8 ff c3 66 2e 0f 1f 84 00 00 00 00 00 66 90 b8 58 00 00 00 0f 05 <48> 3d 01 f0 ff ff 73 01 c3 48 8b 0d c9 d3 0c 00 f7 d8 64 89 01 48
> [    5.440374] RSP: 002b:00007ffc514a2428 EFLAGS: 00000246 ORIG_RAX: 0000000000000058
> [    5.440820] RAX: ffffffffffffffda RBX: 0000000000035d4a RCX: 00007f8137109a97
> [    5.441278] RDX: 0000000000000000 RSI: 00007ffc514a2450 RDI: 00007ffc514a2450
> [    5.441734] RBP: 0000000000000003 R08: 0000000000000000 R09: 0000000000000013
> [    5.442153] R10: 00007ffc514a21c2 R11: 0000000000000246 R12: 0000000000061a80
> [    5.442571] R13: 0000000000000000 R14: 00007ffc514a2450 R15: 00007ffc514a2c50
> [    5.442989]  </TASK>
> [    5.443289] Kernel Offset: disabled
> [    5.443517] Rebooting in 5 seconds..
> 
> Applying just the first patch series (plus the patch hunk from this
> commit needed so that the first patch compiles) does not result in a
> crash, so the problem is clearly with this change.

I was wondering why my testing didn't catch this and the reason was that my
test VM had a version of xfstests which had ext4/052 test but somehow the
'tests/ext4/group' file didn't contain that test (and a few other newer
ones) so it didn't get executed. Not sure how that broken group file got
there but anyway it's fixed now and indeed ext4/052 test crashes for me as
well.

> Looking more closely at ext4/052 which tests the large_dir feature,
> and then looking at the patch, I suspect the fix which is needed
> is:
> 
> > +	ext4_lblk_t blocks[EXT4_HTREE_LEVEL];
> 
> needs to be
> 
> 	ext4_lblk_t blocks[EXT4_HTREE_LEVEL + 1];
> 
> Otherwise on large htree which is 3 levels deep, this
> 
> > +		blocks[++level] = block;
> 
> is going to end up smashing the stack.
> 
> Jan, do you agree?

Yes, thanks for debugging this! But I'd prefer a fix like:

		if (++level > indirect)
			return frame;
		blocks[level] = block;

because the store of the leaf block into 'blocks' array is just bogus. I'll
send V2 with both the issues fixed.

								Honza
-- 
Jan Kara <jack@suse.com>
SUSE Labs, CR

[PATCH 0/2 v2] ext4: Fix crash when adding entry to corrupted directory

[Jan Kara]

Hello,

two patches in this series try to fix a crash when adding directory entry to a
directory with corrupted h-tree. Since I don't have the filesystem image
causing the crash, I'm not sure what was the cause but the stacktrace suggests
we have corrupted one h-tree node while modifying another one so likely
there was a cycle created in the h-tree. This series checks for it and bails
out early.

Changes since v1:
* Fixed compilation error in the first patch (which got fixed in the second
  patch)
* Fixed stack corruption issue with largedir feature

								Honza

Previous versions:
Link: http://lore.kernel.org/r/20220428180355.15209-1-jack@suse.cz # v1

[PATCH 1/2] ext4: Verify dir block before splitting it

[Jan Kara]

Before splitting a directory block verify its directory entries are sane
so that the splitting code does not access memory it should not.

CC: stable@vger.kernel.org
Signed-off-by: Jan Kara <jack@suse.cz>
---
 fs/ext4/namei.c | 32 +++++++++++++++++++++-----------
 1 file changed, 21 insertions(+), 11 deletions(-)

diff --git a/fs/ext4/namei.c b/fs/ext4/namei.c
index 767b4bfe39c3..2a55f23e4524 100644
--- a/fs/ext4/namei.c
+++ b/fs/ext4/namei.c
@@ -277,9 +277,9 @@ static struct dx_frame *dx_probe(struct ext4_filename *fname,
 				 struct dx_hash_info *hinfo,
 				 struct dx_frame *frame);
 static void dx_release(struct dx_frame *frames);
-static int dx_make_map(struct inode *dir, struct ext4_dir_entry_2 *de,
-		       unsigned blocksize, struct dx_hash_info *hinfo,
-		       struct dx_map_entry map[]);
+static int dx_make_map(struct inode *dir, struct buffer_head *bh,
+		       struct dx_hash_info *hinfo,
+		       struct dx_map_entry *map_tail);
 static void dx_sort_map(struct dx_map_entry *map, unsigned count);
 static struct ext4_dir_entry_2 *dx_move_dirents(struct inode *dir, char *from,
 					char *to, struct dx_map_entry *offsets,
@@ -1249,15 +1249,23 @@ static inline int search_dirblock(struct buffer_head *bh,
  * Create map of hash values, offsets, and sizes, stored at end of block.
  * Returns number of entries mapped.
  */
-static int dx_make_map(struct inode *dir, struct ext4_dir_entry_2 *de,
-		       unsigned blocksize, struct dx_hash_info *hinfo,
+static int dx_make_map(struct inode *dir, struct buffer_head *bh,
+		       struct dx_hash_info *hinfo,
 		       struct dx_map_entry *map_tail)
 {
 	int count = 0;
-	char *base = (char *) de;
+	struct ext4_dir_entry_2 *de = (struct ext4_dir_entry_2 *)bh->b_data;
+	unsigned int buflen = bh->b_size;
+	char *base = bh->b_data;
 	struct dx_hash_info h = *hinfo;
 
-	while ((char *) de < base + blocksize) {
+	if (ext4_has_metadata_csum(dir->i_sb))
+		buflen -= sizeof(struct ext4_dir_entry_tail);
+
+	while ((char *) de < base + buflen) {
+		if (ext4_check_dir_entry(dir, NULL, de, bh, base, buflen,
+					 ((char *)de) - base))
+			return -EFSCORRUPTED;
 		if (de->name_len && de->inode) {
 			if (ext4_hash_in_dirent(dir))
 				h.hash = EXT4_DIRENT_HASH(de);
@@ -1270,8 +1278,7 @@ static int dx_make_map(struct inode *dir, struct ext4_dir_entry_2 *de,
 			count++;
 			cond_resched();
 		}
-		/* XXX: do we need to check rec_len == 0 case? -Chris */
-		de = ext4_next_entry(de, blocksize);
+		de = ext4_next_entry(de, dir->i_sb->s_blocksize);
 	}
 	return count;
 }
@@ -1943,8 +1950,11 @@ static struct ext4_dir_entry_2 *do_split(handle_t *handle, struct inode *dir,
 
 	/* create map in the end of data2 block */
 	map = (struct dx_map_entry *) (data2 + blocksize);
-	count = dx_make_map(dir, (struct ext4_dir_entry_2 *) data1,
-			     blocksize, hinfo, map);
+	count = dx_make_map(dir, *bh, hinfo, map);
+	if (count < 0) {
+		err = count;
+		goto journal_error;
+	}
 	map -= count;
 	dx_sort_map(map, count);
 	/* Ensure that neither split block is over half full */
-- 
2.35.3

[PATCH 2/2] ext4: Avoid cycles in directory h-tree

[Jan Kara]

A maliciously corrupted filesystem can contain cycles in the h-tree
stored inside a directory. That can easily lead to the kernel corrupting
tree nodes that were already verified under its hands while doing a node
split and consequently accessing unallocated memory. Fix the problem by
verifying traversed block numbers are unique.

CC: stable@vger.kernel.org
Signed-off-by: Jan Kara <jack@suse.cz>
---
 fs/ext4/namei.c | 22 +++++++++++++++++++---
 1 file changed, 19 insertions(+), 3 deletions(-)

diff --git a/fs/ext4/namei.c b/fs/ext4/namei.c
index 2a55f23e4524..2ca99f1569c0 100644
--- a/fs/ext4/namei.c
+++ b/fs/ext4/namei.c
@@ -777,12 +777,14 @@ static struct dx_frame *
 dx_probe(struct ext4_filename *fname, struct inode *dir,
 	 struct dx_hash_info *hinfo, struct dx_frame *frame_in)
 {
-	unsigned count, indirect;
+	unsigned count, indirect, level, i;
 	struct dx_entry *at, *entries, *p, *q, *m;
 	struct dx_root *root;
 	struct dx_frame *frame = frame_in;
 	struct dx_frame *ret_err = ERR_PTR(ERR_BAD_DX_DIR);
 	u32 hash;
+	ext4_lblk_t block;
+	ext4_lblk_t blocks[EXT4_HTREE_LEVEL];
 
 	memset(frame_in, 0, EXT4_HTREE_LEVEL * sizeof(frame_in[0]));
 	frame->bh = ext4_read_dirblock(dir, 0, INDEX);
@@ -854,6 +856,8 @@ dx_probe(struct ext4_filename *fname, struct inode *dir,
 	}
 
 	dxtrace(printk("Look up %x", hash));
+	level = 0;
+	blocks[0] = 0;
 	while (1) {
 		count = dx_get_count(entries);
 		if (!count || count > dx_get_limit(entries)) {
@@ -882,15 +886,27 @@ dx_probe(struct ext4_filename *fname, struct inode *dir,
 			       dx_get_block(at)));
 		frame->entries = entries;
 		frame->at = at;
-		if (!indirect--)
+
+		block = dx_get_block(at);
+		for (i = 0; i <= level; i++) {
+			if (blocks[i] == block) {
+				ext4_warning_inode(dir,
+					"dx entry: tree cycle block %u points back to block %u",
+					blocks[level], block);
+				goto fail;
+			}
+		}
+		if (++level > indirect)
 			return frame;
+		blocks[level] = block;
 		frame++;
-		frame->bh = ext4_read_dirblock(dir, dx_get_block(at), INDEX);
+		frame->bh = ext4_read_dirblock(dir, block, INDEX);
 		if (IS_ERR(frame->bh)) {
 			ret_err = (struct dx_frame *) frame->bh;
 			frame->bh = NULL;
 			goto fail;
 		}
+
 		entries = ((struct dx_node *) frame->bh->b_data)->entries;
 
 		if (dx_get_limit(entries) != dx_node_limit(dir)) {
-- 
2.35.3

Re: [PATCH 1/2] ext4: Verify dir block before splitting it

[Theodore Ts'o]

On Wed, 18 May 2022 11:33:28 +0200, Jan Kara wrote:
> Before splitting a directory block verify its directory entries are sane
> so that the splitting code does not access memory it should not.
> 
> 

Applied, thanks!

[1/2] ext4: Verify dir block before splitting it
      commit: dfd094204c1f5bb4b1772bade3769cc92b645f1b
[2/2] ext4: Avoid cycles in directory h-tree
      commit: 01db66b58446cd7372c4f29324d270b4cd15157d

Best regards,
-- 
Theodore Ts'o <tytso@mit.edu>