Linux ext4 development ()

Forrest Liu | 13 Dec 2012 16:32

[PATCH] ext4: fix extent tree corruption that incurred by hole punch [V2]

When depth of extent tree is greater than 1, logical start value
of interior node didn't updated correctly in ext4_ext_rm_idx.

Signed-off-by: Forrest Liu <forrestl <at> synology.com>
---
 fs/ext4/extents.c |   22 ++++++++++++++++++----
 1 file changed, 18 insertions(+), 4 deletions(-)

diff --git a/fs/ext4/extents.c b/fs/ext4/extents.c
index d3dd618..496952e 100644
--- a/fs/ext4/extents.c
+++ b/fs/ext4/extents.c
 <at>  <at>  -2190,13 +2190,14  <at>  <at>  errout:
  * removes index from the index block.
  */
 static int ext4_ext_rm_idx(handle_t *handle, struct inode *inode,
-			struct ext4_ext_path *path)
+			struct ext4_ext_path *path, int depth)
 {
 	int err;
 	ext4_fsblk_t leaf;

 	/* free index block */
-	path--;
+	depth--;
+	path = path + depth;
 	leaf = ext4_idx_pblock(path->p_idx);
 	if (unlikely(path->p_hdr->eh_entries == 0)) {
 		EXT4_ERROR_INODE(inode, "path->p_hdr->eh_entries == 0");
 <at>  <at>  -2221,6 +2222,19  <at>  <at>  static int ext4_ext_rm_idx(handle_t *handle,

(Continue reading)

Forrest Liu | 13 Dec 2012 17:04

Re: [PATCH] ext4: fix extent tree corruption that incurred by hole punch [V2]

 <at> Ashish
   I have modified the patch with your suggestion, could you help to review.

 <at> Ted
   I wrote a script to verify this problem.
   This script needs tst_extents and fallocate executables from e2fsprogs, and
fallocate needs your patch with bug fix to do hole punch.

   Steps to run the script
1) assign variable blkdev to path of block device that filesystem mount on
2) cd to mount point
3) run script

Thanks,
Forrest

# verify hole punch bug
#
blkdev=/dev/sda1
file=punch_test
cmdfile=cmds
filesize=`expr 1024 \* 1024 \* 1024`
blksize=`tst_extents -R "stats" $blkdev | grep "Block size" | cut -d
':'  -f 2 | tr -d ' '`
maxlblks=`expr $filesize \/ $blksize`

rm $file
touch $file
fallocate -l $filesize $file
sync

(Continue reading)

Forrest Liu | 13 Dec 2012 17:17

Re: [PATCH] ext4: fix extent tree corruption that incurred by hole punch [V2]

Hi Ted,
   Your patch for fallocate is no problem, my mistake. Sorry~

-Forrest

2012/12/14 Forrest Liu <forrestl <at> synology.com>:
>  <at> Ashish
>    I have modified the patch with your suggestion, could you help to review.
>
>  <at> Ted
>    I wrote a script to verify this problem.
>    This script needs tst_extents and fallocate executables from e2fsprogs, and
> fallocate needs your patch with bug fix to do hole punch.
>
>    Steps to run the script
> 1) assign variable blkdev to path of block device that filesystem mount on
> 2) cd to mount point
> 3) run script
>
> Thanks,
> Forrest
>
> # verify hole punch bug
> #
> blkdev=/dev/sda1
> file=punch_test
> cmdfile=cmds
> filesize=`expr 1024 \* 1024 \* 1024`
> blksize=`tst_extents -R "stats" $blkdev | grep "Block size" | cut -d
> ':'  -f 2 | tr -d ' '`

(Continue reading)

Eric Sandeen | 14 Dec 2012 18:18

Picon

Re: [PATCH] ext4: fix extent tree corruption that incurred by hole punch [V2]

On 12/13/12 10:04 AM, Forrest Liu wrote:
>  <at> Ashish
>    I have modified the patch with your suggestion, could you help to review.
> 
>  <at> Ted
>    I wrote a script to verify this problem.
>    This script needs tst_extents and fallocate executables from e2fsprogs, and
> fallocate needs your patch with bug fix to do hole punch.

Just FWIW, upstream fallocate in util-linux can punch holes already.

Usage:
 fallocate [options] <filename>

Options:
 -n, --keep-size     don't modify the length of the file
 -p, --punch-hole    punch holes in the file
...

-Eric

>    Steps to run the script
> 1) assign variable blkdev to path of block device that filesystem mount on
> 2) cd to mount point
> 3) run script
> 
> Thanks,
> Forrest
> 
> # verify hole punch bug

(Continue reading)

Ashish Sangwan | 17 Dec 2012 05:25

Picon

Re: [PATCH] ext4: fix extent tree corruption that incurred by hole punch [V2]

On Thu, Dec 13, 2012 at 9:02 PM, Forrest Liu <forrestl <at> synology.com> wrote:
> When depth of extent tree is greater than 1, logical start value
> of interior node didn't updated correctly in ext4_ext_rm_idx.
>
> Signed-off-by: Forrest Liu <forrestl <at> synology.com>
> ---

Patch seems ok to me.
Reviewed-by: Ashish Sangwan <ashishsangwan2 <at> gmail.com>
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo <at> vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Theodore Ts'o | 20 Dec 2012 06:39

Picon

Picon

Re: [PATCH] ext4: fix extent tree corruption that incurred by hole punch [V2]

On Thu, Dec 13, 2012 at 11:32:22PM +0800, Forrest Liu wrote:
> When depth of extent tree is greater than 1, logical start value
> of interior node didn't updated correctly in ext4_ext_rm_idx.
> 
> Signed-off-by: Forrest Liu <forrestl <at> synology.com>

Applied.  

BTW, your reproduction case also results in a file system which isn't
noticed as being broken by e2fsck.  Eric's patch "e2fsck: Fix
incorrect interior node logical start values" fixes e2fsck so it
handles this.  Unfortunately applying his patch seems to uncover a bug
in e2fsck when clearing a bad extent node (f_extent_bad_node) which we
need to fix so the regression test suite is passing.

     	       	   	      	   	    - Ted
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo <at> vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Forrest Liu | 20 Dec 2012 16:11

Re: [PATCH] ext4: fix extent tree corruption that incurred by hole punch [V2]

2012/12/20 Theodore Ts'o <tytso <at> mit.edu>:
> On Thu, Dec 13, 2012 at 11:32:22PM +0800, Forrest Liu wrote:
>> When depth of extent tree is greater than 1, logical start value
>> of interior node didn't updated correctly in ext4_ext_rm_idx.
>>
>> Signed-off-by: Forrest Liu <forrestl <at> synology.com>
>
> Applied.
>
> BTW, your reproduction case also results in a file system which isn't
> noticed as being broken by e2fsck.  Eric's patch "e2fsck: Fix
> incorrect interior node logical start values" fixes e2fsck so it
> handles this.  Unfortunately applying his patch seems to uncover a bug
> in e2fsck when clearing a bad extent node (f_extent_bad_node) which we
> need to fix so the regression test suite is passing.
>
>                                             - Ted

Hi Ted,
   I will help to find out the problem in e2fsck.

Thanks,
Forrest
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo <at> vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Theodore Ts'o | 21 Dec 2012 00:42

Picon

Picon

Re: [PATCH] ext4: fix extent tree corruption that incurred by hole punch [V2]

On Thu, Dec 20, 2012 at 11:11:28PM +0800, Forrest Liu wrote:
> Hi Ted,
>    I will help to find out the problem in e2fsck.

Thanks for the offer, but I think I've found the problem and have the
following set of patches (versus the maint branch) to fix the problem.

						- Ted

--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo <at> vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Theodore Ts'o | 21 Dec 2012 00:43

Picon

Picon

[PATCH 1/3] e2fsck: fix incorrect interior node logical start values

From: Eric Sandeen <sandeen <at> redhat.com>

An index node's logical start (ei_block) should
match the logical start of the first node (index
or leaf) below it.  If we find a node whose start
does not match its parent, fix all of its parents
accordingly.

If it finds such a problem, we'll see:

Pass 1: Checking inodes, blocks, and sizes
Interior extent node level 0 of inode 274258:
Logical start 3666 does not match logical start 4093 at next level.  Fix<y>?

Signed-off-by: Eric Sandeen <sandeen <at> redhat.com>
Signed-off-by: "Theodore Ts'o" <tytso <at> mit.edu>
---
 e2fsck/pass1.c      | 17 ++++++++++++++++-
 e2fsck/problem.c    |  8 ++++++++
 e2fsck/problem.h    |  4 +++-
 lib/ext2fs/ext2fs.h |  1 +
 lib/ext2fs/extent.c |  2 +-
 5 files changed, 29 insertions(+), 3 deletions(-)

diff --git a/e2fsck/pass1.c b/e2fsck/pass1.c
index cc00e0f..2acbb53 100644
--- a/e2fsck/pass1.c
+++ b/e2fsck/pass1.c
 <at>  <at>  -1797,7 +1797,7  <at>  <at>  static void scan_extent_node(e2fsck_t ctx, struct problem_context *pctx,
 			problem = PR_1_EXTENT_ENDS_BEYOND;

(Continue reading)

Theodore Ts'o | 21 Dec 2012 00:43

Picon

Picon

[PATCH 3/3] e2fsck: make sure the extent tree is consistent after bogus node in the tree

Commit 789bd401c3 ("e2fsck: fix incorrect interior node logical start
values") surfaced a bug where if e2fsck finds and removed an invalid
node in the extent tree, i.e.:

Inode 12 has an invalid extent node (blk 22, lblk 0)
Clear? yes

It was possible for starting logical blocks found in the interior
nodes of the extent tree.  Commit 789bd401c3 added the ability for
e2fsck to discover this problem, which resulted in the test
f_extent_bad_node to fail when the second pass of e2fsck reported the
following complaint:

Interior extent node level 0 of inode 12:
Logical start 0 does not match logical start 3 at next level.  Fix? yes

This patch fixes this by adding a call to ext2fs_extent_fix_parents()
after deleting the bogus node in the extent tree.

Signed-off-by: "Theodore Ts'o" <tytso <at> mit.edu>
---
 e2fsck/pass1.c | 1 +
 1 file changed, 1 insertion(+)

diff --git a/e2fsck/pass1.c b/e2fsck/pass1.c
index 2acbb53..a8231f4 100644
--- a/e2fsck/pass1.c
+++ b/e2fsck/pass1.c
 <at>  <at>  -1809,6 +1809,7  <at>  <at>  report_problem:
 					pctx->str = "ext2fs_extent_delete";

(Continue reading)

Theodore Ts'o | 21 Dec 2012 04:19

Picon

Picon

Re: [PATCH 3/3] e2fsck: make sure the extent tree is consistent after bogus node in the tree

And here is the test case....

BTW, #protip: You can use the split_node command in tst_extents
debugging program not only to perform node splits (which will make the
tree wider), but if you try splitting at the root node, it will
allocate a new extent tree block, and then move all of the extent tree
nodes at the top-level, in the inode, into the new exterior extent
tree block.  In effect, this will make the tree deeper.

This should allow you to make fairly arbitrarily deep and complex
extent trees by hand, without having to resort to using fallocate and
punch hole commands, which tend to take a lot longer than using the
"insert_extent", "replace_extent", and "split_node" commands in
tst_extent when creating test cases.

This also makes it easier to create small test file system images so
we don't have to bloat the e2fsprogs source tree with huge test file
systems in our regression test suite (which also tend to very much
slow down running said regression test suite).

Regards,

					- Ted

Attachment (0001-tests-add-test-of-an-incorrect-interior-node-in-an-e.patch): text/x-diff, 3288 bytes

Forrest Liu | 21 Dec 2012 12:02

Re: [PATCH 3/3] e2fsck: make sure the extent tree is consistent after bogus node in the tree

I have test these patches, and they work fine.
Thanks for the tip
                                             - Forrest

2012/12/21 Theodore Ts'o <tytso <at> mit.edu>:
> And here is the test case....
>
> BTW, #protip: You can use the split_node command in tst_extents
> debugging program not only to perform node splits (which will make the
> tree wider), but if you try splitting at the root node, it will
> allocate a new extent tree block, and then move all of the extent tree
> nodes at the top-level, in the inode, into the new exterior extent
> tree block.  In effect, this will make the tree deeper.
>
> This should allow you to make fairly arbitrarily deep and complex
> extent trees by hand, without having to resort to using fallocate and
> punch hole commands, which tend to take a lot longer than using the
> "insert_extent", "replace_extent", and "split_node" commands in
> tst_extent when creating test cases.
>
> This also makes it easier to create small test file system images so
> we don't have to bloat the e2fsprogs source tree with huge test file
> systems in our regression test suite (which also tend to very much
> slow down running said regression test suite).
>
> Regards,
>
>                                                - Ted
>
--

(Continue reading)

Eric Sandeen | 21 Dec 2012 16:34

Picon

Re: [PATCH 3/3] e2fsck: make sure the extent tree is consistent after bogus node in the tree

On 12/20/12 5:43 PM, Theodore Ts'o wrote:
> Commit 789bd401c3 ("e2fsck: fix incorrect interior node logical start
> values") surfaced a bug where if e2fsck finds and removed an invalid
> node in the extent tree, i.e.:
> 
> Inode 12 has an invalid extent node (blk 22, lblk 0)
> Clear? yes
> 
> It was possible for starting logical blocks found in the interior
> nodes of the extent tree.  Commit 789bd401c3 added the ability for
> e2fsck to discover this problem, which resulted in the test
> f_extent_bad_node to fail when the second pass of e2fsck reported the
> following complaint:
> 
> Interior extent node level 0 of inode 12:
> Logical start 0 does not match logical start 3 at next level.  Fix? yes
> 
> This patch fixes this by adding a call to ext2fs_extent_fix_parents()
> after deleting the bogus node in the extent tree.
> 
> Signed-off-by: "Theodore Ts'o" <tytso <at> mit.edu>

Reviewed-by: Eric Sandeen <sandeen <at> redhat.com>

Thanks Ted, sorry I didn't catch this.  And this gives me hope
that maybe the extent tree corruption report I had received
might be due to an e2fsck, not kernel runtime...

-Eric

(Continue reading)

Theodore Ts'o | 21 Dec 2012 00:43

Picon

Picon

[PATCH 2/3] libext2fs: ext2fs_extents_fix_parents() should not modify the handle location

Previously, ext2fs_extent_fix_parents() would only avoid modifying the
cursor location associated with the extent handle the cursor was
pointed at a leaf node in the extent tree.  This is because it saved
the starting logical block number of the current extent, but not the
"level" of the extent (where level 0 is the leaf node, level 1 is the
interior node which points at blocks containing leaf nodes, etc.)

Fix ext2fs_extent_fix_parents() so it is guaranteed to not change the
current extent in the handle even if the current extent is not at the
bottom of the tree.

Also add a fix_extent command to the tst_extents program to make it
easier to test this function.

Signed-off-by: "Theodore Ts'o" <tytso <at> mit.edu>
---
 lib/ext2fs/extent.c      | 25 ++++++++++++++++++++++++-
 lib/ext2fs/extent_dbg.ct |  3 +++
 2 files changed, 27 insertions(+), 1 deletion(-)

diff --git a/lib/ext2fs/extent.c b/lib/ext2fs/extent.c
index 95a0a86..c6716bc 100644
--- a/lib/ext2fs/extent.c
+++ b/lib/ext2fs/extent.c
 <at>  <at>  -709,9 +709,11  <at>  <at>  errcode_t ext2fs_extent_goto(ext2_extent_handle_t handle,
 errcode_t ext2fs_extent_fix_parents(ext2_extent_handle_t handle)
 {
 	int				retval = 0;
+	int				orig_height;
 	blk64_t				start;

(Continue reading)

Eric Sandeen | 21 Dec 2012 21:47

Picon

Re: [PATCH 1/3] e2fsck: fix incorrect interior node logical start values

On 12/20/12 5:43 PM, Theodore Ts'o wrote:
> From: Eric Sandeen <sandeen <at> redhat.com>
> 
> An index node's logical start (ei_block) should
> match the logical start of the first node (index
> or leaf) below it.  If we find a node whose start
> does not match its parent, fix all of its parents
> accordingly.
> 
> If it finds such a problem, we'll see:
> 
> Pass 1: Checking inodes, blocks, and sizes
> Interior extent node level 0 of inode 274258:
> Logical start 3666 does not match logical start 4093 at next level.  Fix<y>?

Hm, this situation might still need more work in some cases.

Looking at a "bad" extent tree reported to me:

 1/ 2  25/ 29 57524 - 59011 15538183              1488
 2/ 2   1/  2 57524 - 59011 15556788 - 15558275   1488
 2/ 2   2/  2 59012 - 65535 15558276 - 15564799   6524 Uninit <- what's this extent?

 1/ 2  26/ 29 59012 - 60671 15538184              1660
 2/ 2   1/  2 59012 - 60671    25638 -    27297   1660
 2/ 2   2/  2 60672 - 60689    27298 -    27315     18 Uninit

 1/ 2  27/ 29 60672 - 61023 15538185               352 <- bad logical start
 2/ 2   1/ 19 60690 - 60690    27316 -    27316      1 Uninit

(Continue reading)

Theodore Ts'o | 24 Dec 2012 15:57

Picon

Picon

Re: [PATCH 1/3] e2fsck: fix incorrect interior node logical start values

On Fri, Dec 21, 2012 at 02:47:58PM -0600, Eric Sandeen wrote:
> 
> Hm, this situation might still need more work in some cases.
> 
> but in this case, it seems that the length of the range covered by
> the previous interior nodes is still incorrect.  :(

Yep, we've got a problem which e2fsck is not detecting.  Here's a
simple test case which shows the problem:

debugfs:  extents <12>
Level Entries       Logical      Physical Length Flags
 0/ 2   1/  2     0 -     6    23              7
 1/ 2   1/  2     0 -     3    18              4
 2/ 2   1/  2     0 -     0    37 -    37      1 Uninit
 2/ 2   2/  2     2 -    21    50 -    69     20 Uninit <----- this conflicts
 1/ 2   2/  2     4 -     6    21              3        <----- with this
 2/ 2   1/  2     4 -     4    39 -    39      1 Uninit
 2/ 2   2/  2     6 -     6    40 -    40      1 Uninit
 0/ 2   2/  2     7 -    10    24              4
 1/ 2   1/  2     7 -     8    20              2
 2/ 2   1/  2     7 -     7    41 -    41      1 Uninit
 2/ 2   2/  2     8 -     8    42 -    42      1 Uninit
 1/ 2   2/  2     9 -    10    22              2
 2/ 2   1/  2     9 -     9    43 -    43      1 Uninit
 2/ 2   2/  2    10 -    10    44 -    44      1 Uninit

In this case it's not obvious what is the right fix, since we have two
physical blocks which claim to map to the same logical block.  There
are some places already in e2fsck where we today just throw up our

(Continue reading)

Return

Return to gmane.comp.file-systems.ext4.

Search Archive

Language

Change language

Options

Current view: Threads only / Showing only 20 lines / Not hiding cited text.
Change to All messages, whole messages, or hide cited text.

Post a message
NNTP Newsgroup
Classic Gmane web interface
XML

XML

RSS Feed
List Information

About Gmane