A corrupted ext4 may have out of order leaf extents, i.e.
extent: lblk 0--1023, len 1024, pblk 9217, flags: LEAF UNINIT
extent: lblk 1000--2047, len 1024, pblk 10241, flags: LEAF UNINIT
^^^^ overlap with previous extent
Reading such extent could hit BUG_ON() in ext4_es_cache_extent().
BUG_ON(end < lblk);
The problem is that __read_extent_tree_block() tries to cache holes as
well but assumes 'lblk' is greater than 'prev' and passes underflowed
length to ext4_es_cache_extent().
I hit this when fuzz testing ext4, and am able to reproduce it by
modifying the on-disk extent by hand.
Ran xfstests on patched ext4 and no regression.
Cc: "Theodore Ts'o" <[email protected]>
Signed-off-by: Eryu Guan <[email protected]>
---
fs/ext4/extents.c | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/fs/ext4/extents.c b/fs/ext4/extents.c
index 54d52af..c9ebcb9 100644
--- a/fs/ext4/extents.c
+++ b/fs/ext4/extents.c
@@ -503,7 +503,7 @@ __read_extent_tree_block(const char *function, unsigned int line,
ext4_lblk_t lblk = le32_to_cpu(ex->ee_block);
int len = ext4_ext_get_actual_len(ex);
- if (prev && (prev != lblk))
+ if (prev && (prev < lblk))
ext4_es_cache_extent(inode, prev,
lblk - prev, ~0,
EXTENT_STATUS_HOLE);
--
1.8.3.1
On Thu, 17 Oct 2013, Eryu Guan wrote:
> Date: Thu, 17 Oct 2013 17:27:53 +0800
> From: Eryu Guan <[email protected]>
> To: [email protected]
> Cc: Eryu Guan <[email protected]>, Theodore Ts'o <[email protected]>
> Subject: [PATCH] ext4: don't cache out of order extents
>
> A corrupted ext4 may have out of order leaf extents, i.e.
>
> extent: lblk 0--1023, len 1024, pblk 9217, flags: LEAF UNINIT
> extent: lblk 1000--2047, len 1024, pblk 10241, flags: LEAF UNINIT
> ^^^^ overlap with previous extent
>
> Reading such extent could hit BUG_ON() in ext4_es_cache_extent().
>
> BUG_ON(end < lblk);
>
> The problem is that __read_extent_tree_block() tries to cache holes as
> well but assumes 'lblk' is greater than 'prev' and passes underflowed
> length to ext4_es_cache_extent().
>
> I hit this when fuzz testing ext4, and am able to reproduce it by
> modifying the on-disk extent by hand.
>
> Ran xfstests on patched ext4 and no regression.
So what will happen with the file system with this patch when
presented with such corruption ?
It seems to me that ext4_es_cache_extent() will happily skip this
extent because it will find that this particular offset is already
in the tree. Hence we'll have a gap in the status tree which really
should not be there and I suspect that something bad will happen.
I think that we should deal with this corruption immediately when we
spot it there, not just hide it.
Thanks!
-Lukas
>
> Cc: "Theodore Ts'o" <[email protected]>
> Signed-off-by: Eryu Guan <[email protected]>
> ---
> fs/ext4/extents.c | 2 +-
> 1 file changed, 1 insertion(+), 1 deletion(-)
>
> diff --git a/fs/ext4/extents.c b/fs/ext4/extents.c
> index 54d52af..c9ebcb9 100644
> --- a/fs/ext4/extents.c
> +++ b/fs/ext4/extents.c
> @@ -503,7 +503,7 @@ __read_extent_tree_block(const char *function, unsigned int line,
> ext4_lblk_t lblk = le32_to_cpu(ex->ee_block);
> int len = ext4_ext_get_actual_len(ex);
>
> - if (prev && (prev != lblk))
> + if (prev && (prev < lblk))
> ext4_es_cache_extent(inode, prev,
> lblk - prev, ~0,
> EXTENT_STATUS_HOLE);
>
On Thu, Oct 17, 2013 at 03:44:35PM +0200, Lukáš Czerner wrote:
>
> So what will happen with the file system with this patch when
> presented with such corruption ?
>
> It seems to me that ext4_es_cache_extent() will happily skip this
> extent because it will find that this particular offset is already
> in the tree. Hence we'll have a gap in the status tree which really
> should not be there and I suspect that something bad will happen.
Ah, I see what's going wrong. __read_extent_tree_block() calls
__ext4_ext_check() which is supposed to validate that extent tree
block is valid. The __ext4_ext_check() function calls
ext4_valid_extent_entries() which is supposed to validate the
individual entries in the extent. However, it is not checking to make
sure there are no overlapping extents. We should add that check to
ext4_valid_extent_entries(); that way, we will call ext4_error_inode()
to mark the file system as corrupted.
Eryu's patch, or something like it, will still be needed so that in
the case of errors=countinue, we don't end up calling BUG_ON().
Thanks for finding this!
- Ted
On Thu, Oct 17, 2013 at 03:44:35PM +0200, Lukáš Czerner wrote:
> On Thu, 17 Oct 2013, Eryu Guan wrote:
>
> > Date: Thu, 17 Oct 2013 17:27:53 +0800
> > From: Eryu Guan <[email protected]>
> > To: [email protected]
> > Cc: Eryu Guan <[email protected]>, Theodore Ts'o <[email protected]>
> > Subject: [PATCH] ext4: don't cache out of order extents
> >
> > A corrupted ext4 may have out of order leaf extents, i.e.
> >
> > extent: lblk 0--1023, len 1024, pblk 9217, flags: LEAF UNINIT
> > extent: lblk 1000--2047, len 1024, pblk 10241, flags: LEAF UNINIT
> > ^^^^ overlap with previous extent
> >
> > Reading such extent could hit BUG_ON() in ext4_es_cache_extent().
> >
> > BUG_ON(end < lblk);
> >
> > The problem is that __read_extent_tree_block() tries to cache holes as
> > well but assumes 'lblk' is greater than 'prev' and passes underflowed
> > length to ext4_es_cache_extent().
> >
> > I hit this when fuzz testing ext4, and am able to reproduce it by
> > modifying the on-disk extent by hand.
> >
> > Ran xfstests on patched ext4 and no regression.
>
> So what will happen with the file system with this patch when
> presented with such corruption ?
>
> It seems to me that ext4_es_cache_extent() will happily skip this
> extent because it will find that this particular offset is already
> in the tree. Hence we'll have a gap in the status tree which really
> should not be there and I suspect that something bad will happen.
>
> I think that we should deal with this corruption immediately when we
> spot it there, not just hide it.
Yes, agreed, we should validate the extent not cover the corruption as
Ted pointed out. Don't know why I didn't think about it more in the
first place..
Thanks!
Eryu Guan
On Thu, 17 Oct 2013, Theodore Ts'o wrote:
> Date: Thu, 17 Oct 2013 10:40:44 -0400
> From: Theodore Ts'o <[email protected]>
> To: Lukáš Czerner <[email protected]>
> Cc: Eryu Guan <[email protected]>, [email protected]
> Subject: Re: [PATCH] ext4: don't cache out of order extents
>
> On Thu, Oct 17, 2013 at 03:44:35PM +0200, Lukáš Czerner wrote:
> >
> > So what will happen with the file system with this patch when
> > presented with such corruption ?
> >
> > It seems to me that ext4_es_cache_extent() will happily skip this
> > extent because it will find that this particular offset is already
> > in the tree. Hence we'll have a gap in the status tree which really
> > should not be there and I suspect that something bad will happen.
>
> Ah, I see what's going wrong. __read_extent_tree_block() calls
> __ext4_ext_check() which is supposed to validate that extent tree
> block is valid. The __ext4_ext_check() function calls
> ext4_valid_extent_entries() which is supposed to validate the
> individual entries in the extent. However, it is not checking to make
> sure there are no overlapping extents. We should add that check to
> ext4_valid_extent_entries(); that way, we will call ext4_error_inode()
> to mark the file system as corrupted.
I agree, since ext4_ext_check() should be really only used when
reading data from disk. That said, we might actually remove the
check from ext4_ext_precache() and ext4_ext_remove_space() because
it seems to be that the check has already been done in ext4_iget()
and it should be enough to check it once when reading from disk,
right ?
>
> Eryu's patch, or something like it, will still be needed so that in
> the case of errors=countinue, we don't end up calling BUG_ON().
Hmm shouldn't we avoid that data in the case that it's corrupted
rather than using it ? It seems like this is what the code would do
anyway even with errors=continue when __ext4_ext_check() returns
error.
Thanks!
-Lukas
>
> Thanks for finding this!
>
> - Ted
>
On Thu, Oct 17, 2013 at 05:22:58PM +0200, Lukáš Czerner wrote:
>
> I agree, since ext4_ext_check() should be really only used when
> reading data from disk. That said, we might actually remove the
> check from ext4_ext_precache() and ext4_ext_remove_space() because
> it seems to be that the check has already been done in ext4_iget()
> and it should be enough to check it once when reading from disk,
> right ?
Yes, since we do call ext4_ext_check() in ext4_iget() to verify the
root node of the extent tree located in ei->i_blocks[], it's strictly
speaking not necessary. OTOH, there are at most four entries in
i_blocks[] that need to be verified, and it's a bit easier for the
contents of i_blocks[] to get corrupted by buggy code, so it's a
toss-up whether it's really worth it to remove it from those two
places, which aren't really hotspots. It could be argued that are
plenty of other places that where we're not validating the root extent
tree node, so we might as well remove it from those two functions,
though.
> > Eryu's patch, or something like it, will still be needed so that in
> > the case of errors=countinue, we don't end up calling BUG_ON().
>
> Hmm shouldn't we avoid that data in the case that it's corrupted
> rather than using it ? It seems like this is what the code would do
> anyway even with errors=continue when __ext4_ext_check() returns
> error.
Hmm, maybe we should set a flag indicating that the inode is bad, and
then cause attempts to read or write the contents of that inode should
return EIO.
- Ted
A corrupted ext4 may have out of order leaf extents, i.e.
extent: lblk 0--1023, len 1024, pblk 9217, flags: LEAF UNINIT
extent: lblk 1000--2047, len 1024, pblk 10241, flags: LEAF UNINIT
^^^^ overlap with previous extent
Reading such extent could hit BUG_ON() in ext4_es_cache_extent().
BUG_ON(end < lblk);
The problem is that __read_extent_tree_block() tries to cache holes as
well but assumes 'lblk' is greater than 'prev' and passes underflowed
length to ext4_es_cache_extent(). Fix it by checking for overlapping
extents in ext4_valid_extent_entries().
I hit this when fuzz testing ext4, and am able to reproduce it by
modifying the on-disk extent by hand.
Ran xfstests on patched ext4 and no regression.
Cc: "Theodore Ts'o" <[email protected]>
Cc: Lukáš Czerner <[email protected]>
Signed-off-by: Eryu Guan <[email protected]>
---
Hi,
My second try to find and report the corruption instead of hiding it,
how about this one?
Thanks!
Eryu
fs/ext4/extents.c | 10 ++++++++++
1 file changed, 10 insertions(+)
diff --git a/fs/ext4/extents.c b/fs/ext4/extents.c
index c9ebcb9..855b11d 100644
--- a/fs/ext4/extents.c
+++ b/fs/ext4/extents.c
@@ -387,11 +387,21 @@ static int ext4_valid_extent_entries(struct inode *inode,
if (depth == 0) {
/* leaf entries */
struct ext4_extent *ext = EXT_FIRST_EXTENT(eh);
+ ext4_lblk_t block = 0;
+ ext4_lblk_t prev = 0;
+ int len = 0;
while (entries) {
if (!ext4_valid_extent(inode, ext))
return 0;
+
+ /* Check for overlapping extents */
+ block = le32_to_cpu(ext->ee_block);
+ len = ext4_ext_get_actual_len(ext);
+ if ((block <= prev) && prev)
+ return 0;
ext++;
entries--;
+ prev = block + len - 1;
}
} else {
struct ext4_extent_idx *ext_idx = EXT_FIRST_INDEX(eh);
--
1.8.3.1
On Sun, Oct 20, 2013 at 09:27:27PM +0800, Eryu Guan wrote:
> A corrupted ext4 may have out of order leaf extents, i.e.
>
> extent: lblk 0--1023, len 1024, pblk 9217, flags: LEAF UNINIT
> extent: lblk 1000--2047, len 1024, pblk 10241, flags: LEAF UNINIT
> ^^^^ overlap with previous extent
>
> Reading such extent could hit BUG_ON() in ext4_es_cache_extent().
>
> BUG_ON(end < lblk);
>
> The problem is that __read_extent_tree_block() tries to cache holes as
> well but assumes 'lblk' is greater than 'prev' and passes underflowed
> length to ext4_es_cache_extent(). Fix it by checking for overlapping
> extents in ext4_valid_extent_entries().
>
> I hit this when fuzz testing ext4, and am able to reproduce it by
> modifying the on-disk extent by hand.
>
> Ran xfstests on patched ext4 and no regression.
>
> Cc: "Theodore Ts'o" <[email protected]>
> Cc: Lukáš Czerner <[email protected]>
> Signed-off-by: Eryu Guan <[email protected]>
Self NAK, I found problems in tests, will think about it more.
Thanks,
Eryu
On Mon, Oct 21, 2013 at 07:59:54PM +0800, Eryu Guan wrote:
> On Sun, Oct 20, 2013 at 09:27:27PM +0800, Eryu Guan wrote:
> > A corrupted ext4 may have out of order leaf extents, i.e.
> >
> > extent: lblk 0--1023, len 1024, pblk 9217, flags: LEAF UNINIT
> > extent: lblk 1000--2047, len 1024, pblk 10241, flags: LEAF UNINIT
> > ^^^^ overlap with previous extent
> >
> > Reading such extent could hit BUG_ON() in ext4_es_cache_extent().
> >
> > BUG_ON(end < lblk);
> >
> > The problem is that __read_extent_tree_block() tries to cache holes as
> > well but assumes 'lblk' is greater than 'prev' and passes underflowed
> > length to ext4_es_cache_extent(). Fix it by checking for overlapping
> > extents in ext4_valid_extent_entries().
> >
> > I hit this when fuzz testing ext4, and am able to reproduce it by
> > modifying the on-disk extent by hand.
> >
> > Ran xfstests on patched ext4 and no regression.
> >
> > Cc: "Theodore Ts'o" <[email protected]>
> > Cc: Lukáš Czerner <[email protected]>
> > Signed-off-by: Eryu Guan <[email protected]>
>
> Self NAK, I found problems in tests, will think about it more.
Ah, the error messages in dmesg I've seen are from previous tests, so
there're no problems. Withdraw the self NAK.
Sorry for the noise..
Thanks,
Eryu
On Sun, 20 Oct 2013, Eryu Guan wrote:
> Date: Sun, 20 Oct 2013 21:27:27 +0800
> From: Eryu Guan <[email protected]>
> To: [email protected]
> Cc: Eryu Guan <[email protected]>, Theodore Ts'o <[email protected]>,
> Lukáš Czerner <[email protected]>
> Subject: [PATCH v2] ext4: check for overlapping extents in
> ext4_valid_extent_entries()
>
> A corrupted ext4 may have out of order leaf extents, i.e.
>
> extent: lblk 0--1023, len 1024, pblk 9217, flags: LEAF UNINIT
> extent: lblk 1000--2047, len 1024, pblk 10241, flags: LEAF UNINIT
> ^^^^ overlap with previous extent
>
> Reading such extent could hit BUG_ON() in ext4_es_cache_extent().
>
> BUG_ON(end < lblk);
>
> The problem is that __read_extent_tree_block() tries to cache holes as
> well but assumes 'lblk' is greater than 'prev' and passes underflowed
> length to ext4_es_cache_extent(). Fix it by checking for overlapping
> extents in ext4_valid_extent_entries().
>
> I hit this when fuzz testing ext4, and am able to reproduce it by
> modifying the on-disk extent by hand.
>
> Ran xfstests on patched ext4 and no regression.
Looks ok, but I have some nitpicks bellow :)
>
> Cc: "Theodore Ts'o" <[email protected]>
> Cc: Lukáš Czerner <[email protected]>
> Signed-off-by: Eryu Guan <[email protected]>
> ---
> Hi,
>
> My second try to find and report the corruption instead of hiding it,
> how about this one?
>
> Thanks!
>
> Eryu
>
> fs/ext4/extents.c | 10 ++++++++++
> 1 file changed, 10 insertions(+)
>
> diff --git a/fs/ext4/extents.c b/fs/ext4/extents.c
> index c9ebcb9..855b11d 100644
> --- a/fs/ext4/extents.c
> +++ b/fs/ext4/extents.c
> @@ -387,11 +387,21 @@ static int ext4_valid_extent_entries(struct inode *inode,
> if (depth == 0) {
> /* leaf entries */
> struct ext4_extent *ext = EXT_FIRST_EXTENT(eh);
> + ext4_lblk_t block = 0;
> + ext4_lblk_t prev = 0;
> + int len = 0;
> while (entries) {
> if (!ext4_valid_extent(inode, ext))
> return 0;
> +
> + /* Check for overlapping extents */
> + block = le32_to_cpu(ext->ee_block);
> + len = ext4_ext_get_actual_len(ext);
> + if ((block <= prev) && prev)
Both ext4_valid_extent() and ext4_valid_extent_idx() are setting
s_last_error_block in the case of error. Maybe we should to the same
here ? Note that the block saved in that variable is physical, not
logical.
Also I am curious what happens when one of the extents is corrupted
in such a way that it crosses the 16TB boundary ? In this case the
check would not recognise that since prev will underflow, but maybe
something else catches that ?
Thanks!
-Lukas
> + return 0;
> ext++;
> entries--;
> + prev = block + len - 1;
> }
> } else {
> struct ext4_extent_idx *ext_idx = EXT_FIRST_INDEX(eh);
>
On Mon, Oct 21, 2013 at 06:06:23PM +0200, Lukáš Czerner wrote:
> On Sun, 20 Oct 2013, Eryu Guan wrote:
...
> >
> > diff --git a/fs/ext4/extents.c b/fs/ext4/extents.c
> > index c9ebcb9..855b11d 100644
> > --- a/fs/ext4/extents.c
> > +++ b/fs/ext4/extents.c
> > @@ -387,11 +387,21 @@ static int ext4_valid_extent_entries(struct inode *inode,
> > if (depth == 0) {
> > /* leaf entries */
> > struct ext4_extent *ext = EXT_FIRST_EXTENT(eh);
> > + ext4_lblk_t block = 0;
> > + ext4_lblk_t prev = 0;
> > + int len = 0;
> > while (entries) {
> > if (!ext4_valid_extent(inode, ext))
> > return 0;
> > +
> > + /* Check for overlapping extents */
> > + block = le32_to_cpu(ext->ee_block);
> > + len = ext4_ext_get_actual_len(ext);
> > + if ((block <= prev) && prev)
>
> Both ext4_valid_extent() and ext4_valid_extent_idx() are setting
> s_last_error_block in the case of error. Maybe we should to the same
> here ? Note that the block saved in that variable is physical, not
> logical.
I think that makes sense, it's better to keep the consistency.
But it seems that the s_last_error_block will eventually be
overwritten by ext4_error_inode() in __ext4_ext_check() ?
>
> Also I am curious what happens when one of the extents is corrupted
> in such a way that it crosses the 16TB boundary ? In this case the
> check would not recognise that since prev will underflow, but maybe
> something else catches that ?
Do you mean that a previous (ee_block + len - 1) could cross the 2**32
boundary? I think we can add another check in ext4_valid_extent() for
this situation.
I update the patch to a v3 version, could you please review again?
Thanks a lot!
Eryu Guan
---
From 467025c05bce3ee44e607887bc7cb74ff1bfefcb Mon Sep 17 00:00:00 2001
From: Eryu Guan <[email protected]>
Date: Thu, 17 Oct 2013 23:57:22 +0800
Subject: [PATCH v3] ext4: check for overlapping extents in
ext4_valid_extent_entries()
A corrupted ext4 may have out of order leaf extents, i.e.
extent: lblk 0--1023, len 1024, pblk 9217, flags: LEAF UNINIT
extent: lblk 1000--2047, len 1024, pblk 10241, flags: LEAF UNINIT
^^^^ overlap with previous extent
Reading such extent could hit BUG_ON() in ext4_es_cache_extent().
BUG_ON(end < lblk);
The problem is that __read_extent_tree_block() tries to cache holes as
well but assumes 'lblk' is greater than 'prev' and passes underflowed
length to ext4_es_cache_extent(). Fix it by checking for overlapping
extents in ext4_valid_extent_entries().
I hit this when fuzz testing ext4, and am able to reproduce it by
modifying the on-disk extent by hand.
Also add the check for (ee_block + len - 1) in ext4_valid_extent() to
make sure the value is not overflow.
Ran xfstests on patched ext4 and no regression.
Cc: "Theodore Ts'o" <[email protected]>
Cc: Lukáš Czerner <[email protected]>
Signed-off-by: Eryu Guan <[email protected]>
---
v3: Address comments from Lukas
- set s_last_error_block when there's overlapping extents found
- check for (ee_block + len - 1) in ext4_valid_extent(), value should
not overflow
v2:
- check for overlapping extents explicitly not hide the corruption
fs/ext4/extents.c | 19 ++++++++++++++++++-
1 file changed, 18 insertions(+), 1 deletion(-)
diff --git a/fs/ext4/extents.c b/fs/ext4/extents.c
index c9ebcb9..85d977f 100644
--- a/fs/ext4/extents.c
+++ b/fs/ext4/extents.c
@@ -360,8 +360,10 @@ static int ext4_valid_extent(struct inode *inode, struct ext4_extent *ext)
{
ext4_fsblk_t block = ext4_ext_pblock(ext);
int len = ext4_ext_get_actual_len(ext);
+ ext4_lblk_t lblock = le32_to_cpu(ext->ee_block);
+ ext4_lblk_t last = lblock + len - 1;
- if (len == 0)
+ if (lblock > last)
return 0;
return ext4_data_block_valid(EXT4_SB(inode->i_sb), block, len);
}
@@ -387,11 +389,26 @@ static int ext4_valid_extent_entries(struct inode *inode,
if (depth == 0) {
/* leaf entries */
struct ext4_extent *ext = EXT_FIRST_EXTENT(eh);
+ struct ext4_super_block *es = EXT4_SB(inode->i_sb)->s_es;
+ ext4_fsblk_t pblock = 0;
+ ext4_lblk_t lblock = 0;
+ ext4_lblk_t prev = 0;
+ int len = 0;
while (entries) {
if (!ext4_valid_extent(inode, ext))
return 0;
+
+ /* Check for overlapping extents */
+ lblock = le32_to_cpu(ext->ee_block);
+ len = ext4_ext_get_actual_len(ext);
+ if ((lblock <= prev) && prev) {
+ pblock = ext4_ext_pblock(ext);
+ es->s_last_error_block = cpu_to_le64(pblock);
+ return 0;
+ }
ext++;
entries--;
+ prev = lblock + len - 1;
}
} else {
struct ext4_extent_idx *ext_idx = EXT_FIRST_INDEX(eh);
--
1.8.3.1
On Wed, Oct 23, 2013 at 02:40:30AM +0800, Eryu Guan wrote:
> A corrupted ext4 may have out of order leaf extents, i.e.
>
> extent: lblk 0--1023, len 1024, pblk 9217, flags: LEAF UNINIT
> extent: lblk 1000--2047, len 1024, pblk 10241, flags: LEAF UNINIT
> ^^^^ overlap with previous extent
>
> Reading such extent could hit BUG_ON() in ext4_es_cache_extent().
>
> BUG_ON(end < lblk);
>
> The problem is that __read_extent_tree_block() tries to cache holes as
> well but assumes 'lblk' is greater than 'prev' and passes underflowed
> length to ext4_es_cache_extent(). Fix it by checking for overlapping
> extents in ext4_valid_extent_entries().
>
> I hit this when fuzz testing ext4, and am able to reproduce it by
> modifying the on-disk extent by hand.
>
> Also add the check for (ee_block + len - 1) in ext4_valid_extent() to
> make sure the value is not overflow.
>
> Ran xfstests on patched ext4 and no regression.
>
> Cc: "Theodore Ts'o" <[email protected]>
> Cc: Lukáš Czerner <[email protected]>
> Signed-off-by: Eryu Guan <[email protected]>
Thanks, applied.
- Ted