ext4: don't cache out of order extents
PATCH 1/1 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.
--- fs/ext4/extents.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
fs/ext4/extents.c +1 -1
@@ -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 );
Signature · 1 line
1.8.3.1
Quoted 16 lines · Eryu Guan
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 extentsA 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 extentReading such extent could hit
BUG_ON()inext4_es_cache_extent().BUG_ON(end < lblk);
Quoted 8 lines
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 toext4_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
Quoted 21 lines
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(-)fs/ext4/extents.c +1
-1@@ -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 );
Theodore Ts'o
maintainerQuoted 8 lines · Lukáš Czerner
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
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Quoted 16 lines · Theodore Ts'o
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 extentsQuoted 8 lines · Lukáš Czerner
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.
Quoted 8 lines
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 callsext4_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 toext4_valid_extent_entries(); that way, we will callext4_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 ?
Quoted 3 lines
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
Quoted 5 lines
Thanks for finding this!
- Ted
Theodore Ts'o
maintainerQuoted 7 lines · Lukáš Czerner
I agree, since
ext4_ext_check()should be really only used when reading data from disk. That said, we might actually remove the check fromext4_ext_precache()andext4_ext_remove_space()because it seems to be that the check has already been done inext4_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.
Quoted 7 lines
Quoted 2 lines
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
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Quoted 30 lines · Lukáš Czerner
Quoted 16 lines · Eryu Guan
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 extentsA 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 extentReading such extent could hit
BUG_ON()inext4_es_cache_extent().BUG_ON(end < lblk);Quoted 8 lines
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 toext4_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 ?
Quoted 7 lines
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
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
PATCH v2 1/1 ext4: check for overlapping extents in ext4_valid_extent_entries()
In reply to Eryu GuanA 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.
---
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(+)
fs/ext4/extents.c +10 -0
@@ -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);
Signature · 6 lines
1.8.3.1 -- To unsubscribe from this list: send the line "unsubscribe linux-ext4" in the body of a message to [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH v2] ext4: check for overlapping extents in ext4_valid_extent_entries()
Quoted 15 lines · Eryu Guan
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 extentReading such extent could hit
BUG_ON()inext4_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 toext4_es_cache_extent(). Fix it by checking for overlapping extents inext4_valid_extent_entries().
Quoted 8 lines
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
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH v2] ext4: check for overlapping extents in ext4_valid_extent_entries()
Quoted 19 lines · Eryu Guan
Quoted 18 lines · Eryu Guan
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 extentReading such extent could hit
BUG_ON()inext4_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 toext4_es_cache_extent(). Fix it by checking for overlapping extents inext4_valid_extent_entries().I hit this when fuzz testing ext4, and am able to reproduce it by modifying the on-disk extent by hand.
Quoted 7 lines
Quoted 5 lines
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
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH v2] ext4: check for overlapping extents in ext4_valid_extent_entries()
In reply to Eryu GuanQuoted 23 lines · Eryu Guan
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 extentReading such extent could hit
BUG_ON()inext4_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 toext4_es_cache_extent(). Fix it by checking for overlapping extents inext4_valid_extent_entries().
Quoted 4 lines
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 :)
Quoted 26 lines
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(+)fs/ext4/extents.c +1
-0@@ -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 ;
fs/ext4/extents.c static int ext4_valid_extent_entries(struct inode *inode, · line 400
Quoted 10 lines
fs/ext4/extents.c +7
-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
Quoted 8 lines
fs/ext4/extents.c +2
-0+return 0 ; ext++; entries--; + prev = block + len -1 ; } }else {struct ext4_extent_idx *ext_idx =EXT_FIRST_INDEX (eh);
Re: [PATCH v2] ext4: check for overlapping extents in ext4_valid_extent_entries()
Quoted 1 line · Lukáš Czerner
On Sun, 20 Oct 2013, Eryu Guan wrote:
...
Quoted 17 lines
Quoted 17 lines
fs/ext4/extents.c +5
-0@@ -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 */
Quoted 8 lines
fs/ext4/extents.c static int ext4_valid_extent_entries(struct inode *inode, · line 400
Quoted 3 lines
fs/ext4/extents.c +3
-0+ block =le32_to_cpu (ext->ee_block); + len =ext4_ext_get_actual_len (ext); +if ((block <= prev) && prev)Both
ext4_valid_extent()andext4_valid_extent_idx()are settings_last_error_blockin 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() ?
Quoted 5 lines
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.
---
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(-)
fs/ext4/extents.c +18 -1
@@ -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);
Signature · 8 lines
1.8.3.1 -- To unsubscribe from this list: send the line "unsubscribe linux-ext4" in the body of a message to [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html
PATCH v3 1/1 ext4: check for overlapping extents in ext4_valid_extent_entries()
Quoted 18 lines · Eryu Guan
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 extentReading such extent could hit
BUG_ON()inext4_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 toext4_es_cache_extent(). Fix it by checking for overlapping extents inext4_valid_extent_entries().I hit this when fuzz testing ext4, and am able to reproduce it by modifying the on-disk extent by hand.
Quoted 8 lines
Also add the check for (
ee_block+ len - 1) inext4_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
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html