* Re: [PATCH] ext4: verify extent header depth
2016-07-06 21:27 [PATCH] ext4: verify extent header depth Vegard Nossum
@ 2016-07-06 22:23 ` Vegard Nossum
2016-07-06 22:28 ` Darrick J. Wong
2016-07-07 0:54 ` Theodore Ts'o
2 siblings, 0 replies; 5+ messages in thread
From: Vegard Nossum @ 2016-07-06 22:23 UTC (permalink / raw)
To: tytso; +Cc: linux-ext4, Darrick J. Wong
On 07/06/2016 11:27 PM, Vegard Nossum wrote:
> According to the wiki [1], eh_depth cannot be larger than 5:
>
> Depth of this extent node in the extent tree. 0 = this extent node
> points to data blocks; otherwise, this extent node points to other
> extent nodes. The extent tree can be at most 5 levels deep: a logical
> block number can be at most 2^32, and the smallest n that satisfies
> 4*(((blocksize - 12)/12)^n) >= 2^32 is 5.
>
> [1]: https://ext4.wiki.kernel.org/index.php/Ext4_Disk_Layout#Extent_Tree
>
> Without this, we can end up trying to reserve too much space for the
> transaction in case of malicious corruption (here, eh_depth = 65280):
>
> JBD2: ext4.exe wants too many credits credits:195849 rsv_credits:0 max:256
> ------------[ cut here ]------------
> WARNING: CPU: 0 PID: 50 at fs/jbd2/transaction.c:293 start_this_handle+0x569/0x580
> CPU: 0 PID: 50 Comm: ext4.exe Not tainted 4.7.0-rc5+ #508
I'm guessing this would also fix another warning I saw earlier:
WARNING: CPU: 0 PID: 50 at mm/page_alloc.c:3584
__alloc_pages_nodemask+0x3c9/0xd20
CPU: 0 PID: 50 Comm: ext4.exe Not tainted 4.7.0-rc3 #1
Stack:
62629550 6005c7c2 03800000 600801f9
00000000 600760ce 62629560 601dbff1
626295c0 6002beb4 800000074786574 900000e00
Call Trace:
[<6001834b>] show_stack+0xdb/0x1a0
[<601dbff1>] dump_stack+0x2a/0x39
[<6002beb4>] __warn+0x114/0x140
[<6002c02f>] warn_slowpath_null+0x1f/0x30
[<600801f9>] __alloc_pages_nodemask+0x3c9/0xd20
[<60080e3c>] alloc_kmem_pages+0x1c/0x20
[<60096fea>] kmalloc_order+0x1a/0x60
[<600af518>] __kmalloc+0x1a8/0x1f0
[<6014dd09>] ext4_find_extent+0x3a9/0x420
[<60152df3>] ext4_ext_map_blocks+0x73/0x28d0
[<6011fc22>] ext4_map_blocks+0x612/0x980
[<6012002c>] _ext4_get_block+0x9c/0x150
[<60120120>] ext4_get_block+0x40/0x50
[<600edc2a>] generic_block_bmap+0x3a/0x40
[<6011bd4f>] ext4_bmap+0xcf/0x190
[<600d430a>] bmap+0x1a/0x30
[<6018bd41>] jbd2_journal_bmap+0x31/0xa0
[<6018c0c5>] jbd2_journal_init_inode+0x135/0x220
[<60143945>] ext4_fill_super+0x3085/0x4b60
[<600b794b>] mount_bdev+0x1fb/0x230
[<6013a865>] ext4_mount+0x45/0x50
[<600b7bd3>] mount_fs+0x33/0x210
[<600d9834>] vfs_kern_mount+0x74/0x170
[<600db34b>] do_mount+0x26b/0x10c0
[<600dc6a0>] SyS_mount+0xc0/0x130
...since this is ext4_find_extent() doing
depth = ext_depth(inode)
path = kzalloc(sizeof(struct ext4_ext_path) * (depth + 2), GFP_NOFS);
Vegard
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH] ext4: verify extent header depth
2016-07-06 21:27 [PATCH] ext4: verify extent header depth Vegard Nossum
2016-07-06 22:23 ` Vegard Nossum
@ 2016-07-06 22:28 ` Darrick J. Wong
2016-07-07 0:54 ` Theodore Ts'o
2 siblings, 0 replies; 5+ messages in thread
From: Darrick J. Wong @ 2016-07-06 22:28 UTC (permalink / raw)
To: Vegard Nossum; +Cc: tytso, linux-ext4
On Wed, Jul 06, 2016 at 11:27:11PM +0200, Vegard Nossum wrote:
> According to the wiki [1], eh_depth cannot be larger than 5:
>
> Depth of this extent node in the extent tree. 0 = this extent node
> points to data blocks; otherwise, this extent node points to other
> extent nodes. The extent tree can be at most 5 levels deep: a logical
> block number can be at most 2^32, and the smallest n that satisfies
> 4*(((blocksize - 12)/12)^n) >= 2^32 is 5.
>
> [1]: https://ext4.wiki.kernel.org/index.php/Ext4_Disk_Layout#Extent_Tree
>
> Without this, we can end up trying to reserve too much space for the
> transaction in case of malicious corruption (here, eh_depth = 65280):
>
> JBD2: ext4.exe wants too many credits credits:195849 rsv_credits:0 max:256
> ------------[ cut here ]------------
> WARNING: CPU: 0 PID: 50 at fs/jbd2/transaction.c:293 start_this_handle+0x569/0x580
> CPU: 0 PID: 50 Comm: ext4.exe Not tainted 4.7.0-rc5+ #508
> Stack:
> 604a8947 625badd8 0002fd09 00000000
> 60078643 00000000 62623910 601bf9bc
> 62623970 6002fc84 626239b0 900000125
> Call Trace:
> [<6001c2dc>] show_stack+0xdc/0x1a0
> [<601bf9bc>] dump_stack+0x2a/0x2e
> [<6002fc84>] __warn+0x114/0x140
> [<6002fdff>] warn_slowpath_null+0x1f/0x30
> [<60165829>] start_this_handle+0x569/0x580
> [<60165d4e>] jbd2__journal_start+0x11e/0x220
> [<60146690>] __ext4_journal_start_sb+0x60/0xa0
> [<60120a81>] ext4_truncate+0x131/0x3a0
> [<60123677>] ext4_setattr+0x757/0x840
> [<600d5d0f>] notify_change+0x16f/0x2a0
> [<600b2b16>] do_truncate+0x76/0xc0
> [<600c3e56>] path_openat+0x806/0x1300
> [<600c55c9>] do_filp_open+0x89/0xf0
> [<600b4074>] do_sys_open+0x134/0x1e0
> [<600b4140>] SyS_open+0x20/0x30
> [<6001ea68>] handle_syscall+0x88/0x90
> [<600295fd>] userspace+0x3fd/0x500
> [<6001ac55>] fork_handler+0x85/0x90
>
> ---[ end trace 08b0b88b6387a244 ]---
>
> Cc: Darrick J. Wong <darrick.wong@oracle.com>
> Signed-off-by: Vegard Nossum <vegard.nossum@oracle.com>
> ---
> fs/ext4/extents.c | 4 ++++
> 1 file changed, 4 insertions(+)
>
> diff --git a/fs/ext4/extents.c b/fs/ext4/extents.c
> index 30de10a..b584ddd 100644
> --- a/fs/ext4/extents.c
> +++ b/fs/ext4/extents.c
> @@ -476,6 +476,10 @@ static int __ext4_ext_check(const char *function, unsigned int line,
> error_msg = "invalid extent entries";
> goto corrupted;
> }
> + if (unlikely(depth > 5)) {
> + error_msg = "too large eh_depth";
> + goto corrupted;
> + }
Seems reasonable,
Reviewed-by: Darrick J. Wong <darrick.wong@oracle.com>
--D
> /* Verify checksum on non-root extent tree nodes */
> if (ext_depth(inode) != depth &&
> !ext4_extent_block_csum_verify(inode, eh)) {
> --
> 1.9.1
>
> --
> To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at http://vger.kernel.org/majordomo-info.html
^ permalink raw reply [flat|nested] 5+ messages in thread* Re: [PATCH] ext4: verify extent header depth
2016-07-06 21:27 [PATCH] ext4: verify extent header depth Vegard Nossum
2016-07-06 22:23 ` Vegard Nossum
2016-07-06 22:28 ` Darrick J. Wong
@ 2016-07-07 0:54 ` Theodore Ts'o
2016-07-15 4:22 ` Theodore Ts'o
2 siblings, 1 reply; 5+ messages in thread
From: Theodore Ts'o @ 2016-07-07 0:54 UTC (permalink / raw)
To: Vegard Nossum; +Cc: linux-ext4, Darrick J. Wong
On Wed, Jul 06, 2016 at 11:27:11PM +0200, Vegard Nossum wrote:
> According to the wiki [1], eh_depth cannot be larger than 5:
>
> Depth of this extent node in the extent tree. 0 = this extent node
> points to data blocks; otherwise, this extent node points to other
> extent nodes. The extent tree can be at most 5 levels deep: a logical
> block number can be at most 2^32, and the smallest n that satisfies
> 4*(((blocksize - 12)/12)^n) >= 2^32 is 5.
Hmm... well, so in practice it is *extremely* rare that the tree depth
would be even more than 3 deep. That's because (a) the above
calculation assumes a block size of 1k, where where the fanout factor
is 84, instead of the 340 with a 4k blocksize, and (b) the calculation
assumes that all of the extents have a length of 1; which is the worst
case, but in practice is quite rare.
On the other hand, in the absolute worst case the tree *can* get have
a depth greater than 5, because we currently don't enforce the B+ tree
constraint that all nodes (except for the last leaf node) must be at
least half full. Because of this, it's *possible* if all of the
extents are one block long (because the file system is highly
fragmented), and if there is an especially malicious punch hole and
fallocate sequence of operations, it might be possible to set up a
scenario with a 1k block file system which is extremely fragmented,
and then create a file whose extent tree has a huge number of empty
nodes, except in one block range where all of the interior nodes at
the 1st, 2nd, 3rd, 4th, and 5th level of the tree are completely full,
such that ext4_ext_create_new_leaf() might actually decide that it
needs to make the tree one level deeper.
I really can't quite see this happening except for someone who was
*really* trying to maliciously break the file system, though.
> Without this, we can end up trying to reserve too much space for the
> transaction in case of malicious corruption (here, eh_depth = 65280)
So we could arbitrarily limit eh_depth to say, 32 levels, or some
such. That will prevent the malicious corruption, while also making
it very difficult for the malicious fallocate/punch hole workload
scenario to be triggered. The best thing would be to actually
implement code to rebalance and shrink the extent tree when necessary...
- Ted
^ permalink raw reply [flat|nested] 5+ messages in thread