Patchwork e2fsck: detect invalid extents at the end of an extent-block

login
register
mail settings
Submitter David Jeffery
Date April 3, 2013, 7:08 p.m.
Message ID <20130403190841.GA16276@fury.redhat.com>
Download mbox | patch
Permalink /patch/233572/
State Accepted
Headers show

Comments

David Jeffery - April 3, 2013, 7:08 p.m.
e2fsck does not detect extents which are outside their location in the
extent tree.  This can result in a bad extent at the end of an extent-block
not being detected.
    
From a part of a dump_extents output:
    
 1/ 2  37/ 68 143960 - 146679 123826181               2720
 2/ 2   1/  2 143960 - 146679 123785816 - 123788535   2720
 2/ 2   2/  2 146680 - 147583 123788536 - 123789439    904 Uninit <-bad extent
 1/ 2  38/ 68 146680 - 149391 123826182               2712
 2/ 2   1/  2 146680 - 147583     18486 -     19389    904
 2/ 2   2/  2 147584 - 149391 123789440 - 123791247   1808
    
e2fsck does not detect this bad extent which both overlaps another, valid
extent, and is invalid by being beyond the end of the extent above it in
the tree.
    
This patch modifies e2fsck to detect this invalid extent and remove it.

Signed-off-by: David Jeffery <djeffery@redhat.com>
---
 e2fsck/pass1.c   |   13 +++++++++----
 e2fsck/problem.c |    6 ++++++
 e2fsck/problem.h |    1 +
 3 files changed, 16 insertions(+), 4 deletions(-)

--
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
Eric Sandeen - June 4, 2013, 7:53 p.m.
On 4/3/13 2:08 PM, David Jeffery wrote:
> e2fsck does not detect extents which are outside their location in the
> extent tree.  This can result in a bad extent at the end of an extent-block
> not being detected.
>     
> From a part of a dump_extents output:
>     
>  1/ 2  37/ 68 143960 - 146679 123826181               2720
>  2/ 2   1/  2 143960 - 146679 123785816 - 123788535   2720
>  2/ 2   2/  2 146680 - 147583 123788536 - 123789439    904 Uninit <-bad extent
>  1/ 2  38/ 68 146680 - 149391 123826182               2712
>  2/ 2   1/  2 146680 - 147583     18486 -     19389    904
>  2/ 2   2/  2 147584 - 149391 123789440 - 123791247   1808
>     
> e2fsck does not detect this bad extent which both overlaps another, valid
> extent, and is invalid by being beyond the end of the extent above it in
> the tree.
>     
> This patch modifies e2fsck to detect this invalid extent and remove it.

Here's an image which demonstrates this, current e2fsck does not detect
the error.

-Eric

> Signed-off-by: David Jeffery <djeffery@redhat.com>
> ---
>  e2fsck/pass1.c   |   13 +++++++++----
>  e2fsck/problem.c |    6 ++++++
>  e2fsck/problem.h |    1 +
>  3 files changed, 16 insertions(+), 4 deletions(-)
> 
> diff --git a/e2fsck/pass1.c b/e2fsck/pass1.c
> index a20b57b..198e9a0 100644
> --- a/e2fsck/pass1.c
> +++ b/e2fsck/pass1.c
> @@ -1848,7 +1848,7 @@ void e2fsck_clear_inode(e2fsck_t ctx, ext2_ino_t ino,
>  
>  static void scan_extent_node(e2fsck_t ctx, struct problem_context *pctx,
>  			     struct process_block_struct *pb,
> -			     blk64_t start_block,
> +			     blk64_t start_block, blk64_t end_block,
>  			     ext2_extent_handle_t ehandle)
>  {
>  	struct ext2fs_extent	extent;
> @@ -1891,6 +1891,9 @@ static void scan_extent_node(e2fsck_t ctx, struct problem_context *pctx,
>  			problem = PR_1_EXTENT_BAD_START_BLK;
>  		else if (extent.e_lblk < start_block)
>  			problem = PR_1_OUT_OF_ORDER_EXTENTS;
> +		else if (end_block &&
> +			 (extent.e_lblk + extent.e_len) > end_block)
> +			problem = PR_1_EXTENT_END_OUT_OF_BOUNDS;
>  		else if (is_leaf && extent.e_len == 0)
>  			problem = PR_1_EXTENT_LENGTH_ZERO;
>  		else if (is_leaf &&
> @@ -1937,10 +1940,11 @@ fix_problem_now:
>  		}
>  
>  		if (!is_leaf) {
> -			blk64_t lblk;
> +			blk64_t lblk, lblk_end;
>  
>  			blk = extent.e_pblk;
>  			lblk = extent.e_lblk;
> +			lblk_end = extent.e_lblk + extent.e_len;
>  			pctx->errcode = ext2fs_extent_get(ehandle,
>  						  EXT2_EXTENT_DOWN, &extent);
>  			if (pctx->errcode) {
> @@ -1965,7 +1969,8 @@ fix_problem_now:
>  				if (fix_problem(ctx, problem, pctx))
>  					ext2fs_extent_fix_parents(ehandle);
>  			}
> -			scan_extent_node(ctx, pctx, pb, extent.e_lblk, ehandle);
> +			scan_extent_node(ctx, pctx, pb, extent.e_lblk,
> +					 lblk_end, ehandle);
>  			if (pctx->errcode)
>  				return;
>  			pctx->errcode = ext2fs_extent_get(ehandle,
> @@ -2084,7 +2089,7 @@ static void check_blocks_extents(e2fsck_t ctx, struct problem_context *pctx,
>  		ctx->extent_depth_count[info.max_depth]++;
>  	}
>  
> -	scan_extent_node(ctx, pctx, pb, 0, ehandle);
> +	scan_extent_node(ctx, pctx, pb, 0, 0, ehandle);
>  	if (pctx->errcode &&
>  	    fix_problem(ctx, PR_1_EXTENT_ITERATE_FAILURE, pctx)) {
>  		pb->num_blocks = 0;
> diff --git a/e2fsck/problem.c b/e2fsck/problem.c
> index 76bc1d5..b0a6e19 100644
> --- a/e2fsck/problem.c
> +++ b/e2fsck/problem.c
> @@ -1008,6 +1008,12 @@ static struct e2fsck_problem problem_table[] = {
>  	     "Logical start %b does not match logical start %c at next level.  "),
>  	  PROMPT_FIX, 0 },
>  
> +	/* Extent end is out of bounds for the tree */
> +	{ PR_1_EXTENT_END_OUT_OF_BOUNDS,
> +	  N_("@i %i, end of extent exceeds allowed value\n\t(logical @b %c, physical @b %b, len %N)\n"),
> +	  PROMPT_CLEAR, 0 },
> +
> +
>  	/* Pass 1b errors */
>  
>  	/* Pass 1B: Rescan for duplicate/bad blocks */
> diff --git a/e2fsck/problem.h b/e2fsck/problem.h
> index d2b6df4..fcdc1a1 100644
> --- a/e2fsck/problem.h
> +++ b/e2fsck/problem.h
> @@ -589,6 +589,7 @@ struct problem_context {
>  /* Index start doesn't match start of next extent down */
>  #define PR_1_EXTENT_INDEX_START_INVALID	0x01006D
>  
> +#define PR_1_EXTENT_END_OUT_OF_BOUNDS	0x01006E
>  /*
>   * Pass 1b errors
>   */
> --
> 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
>
Eric Sandeen - June 4, 2013, 9:54 p.m.
On 4/3/13 2:08 PM, David Jeffery wrote:
> e2fsck does not detect extents which are outside their location in the
> extent tree.  This can result in a bad extent at the end of an extent-block
> not being detected.
>     
> From a part of a dump_extents output:
>     
>  1/ 2  37/ 68 143960 - 146679 123826181               2720
>  2/ 2   1/  2 143960 - 146679 123785816 - 123788535   2720
>  2/ 2   2/  2 146680 - 147583 123788536 - 123789439    904 Uninit <-bad extent
>  1/ 2  38/ 68 146680 - 149391 123826182               2712
>  2/ 2   1/  2 146680 - 147583     18486 -     19389    904
>  2/ 2   2/  2 147584 - 149391 123789440 - 123791247   1808
>     
> e2fsck does not detect this bad extent which both overlaps another, valid
> extent, and is invalid by being beyond the end of the extent above it in
> the tree.
>     
> This patch modifies e2fsck to detect this invalid extent and remove it.
> 
> Signed-off-by: David Jeffery <djeffery@redhat.com>
> ---
>  e2fsck/pass1.c   |   13 +++++++++----
>  e2fsck/problem.c |    6 ++++++
>  e2fsck/problem.h |    1 +
>  3 files changed, 16 insertions(+), 4 deletions(-)
> 
> diff --git a/e2fsck/pass1.c b/e2fsck/pass1.c
> index a20b57b..198e9a0 100644
> --- a/e2fsck/pass1.c
> +++ b/e2fsck/pass1.c
> @@ -1848,7 +1848,7 @@ void e2fsck_clear_inode(e2fsck_t ctx, ext2_ino_t ino,
>  
>  static void scan_extent_node(e2fsck_t ctx, struct problem_context *pctx,
>  			     struct process_block_struct *pb,
> -			     blk64_t start_block,
> +			     blk64_t start_block, blk64_t end_block,
>  			     ext2_extent_handle_t ehandle)
>  {
>  	struct ext2fs_extent	extent;
> @@ -1891,6 +1891,9 @@ static void scan_extent_node(e2fsck_t ctx, struct problem_context *pctx,
>  			problem = PR_1_EXTENT_BAD_START_BLK;
>  		else if (extent.e_lblk < start_block)
>  			problem = PR_1_OUT_OF_ORDER_EXTENTS;
> +		else if (end_block &&
> +			 (extent.e_lblk + extent.e_len) > end_block)
> +			problem = PR_1_EXTENT_END_OUT_OF_BOUNDS;

thinking out loud; let's say e_lblk is 10 and len is 10.  So the
extent covers blocks 10->19, and e_lbk + e_len is 20, though
the last block in the range is 19.

But you pass in the same value (lblk + len) as "last block" so I guess
it matches up, it just requires some thought.

It might be better to do this in the caller:

lblk_end = extent.e_lblk + extent.e_len - 1;

and this in the test:

		else if (end_block &&
			 (extent.e_lblk + extent.e_len - 1) > end_block)

just so that "end_block" really is the end block?

>  		else if (is_leaf && extent.e_len == 0)
>  			problem = PR_1_EXTENT_LENGTH_ZERO;
>  		else if (is_leaf &&
> @@ -1937,10 +1940,11 @@ fix_problem_now:
>  		}
>  
>  		if (!is_leaf) {
> -			blk64_t lblk;
> +			blk64_t lblk, lblk_end;
>  
>  			blk = extent.e_pblk;
>  			lblk = extent.e_lblk;
> +			lblk_end = extent.e_lblk + extent.e_len;

maybe extent.e_lblk + extent.e_len - 1 ?

>  			pctx->errcode = ext2fs_extent_get(ehandle,
>  						  EXT2_EXTENT_DOWN, &extent);
>  			if (pctx->errcode) {
> @@ -1965,7 +1969,8 @@ fix_problem_now:
>  				if (fix_problem(ctx, problem, pctx))
>  					ext2fs_extent_fix_parents(ehandle);
>  			}
> -			scan_extent_node(ctx, pctx, pb, extent.e_lblk, ehandle);
> +			scan_extent_node(ctx, pctx, pb, extent.e_lblk,
> +					 lblk_end, ehandle);
>  			if (pctx->errcode)
>  				return;
>  			pctx->errcode = ext2fs_extent_get(ehandle,
> @@ -2084,7 +2089,7 @@ static void check_blocks_extents(e2fsck_t ctx, struct problem_context *pctx,
>  		ctx->extent_depth_count[info.max_depth]++;
>  	}
>  
> -	scan_extent_node(ctx, pctx, pb, 0, ehandle);
> +	scan_extent_node(ctx, pctx, pb, 0, 0, ehandle);

Other than the above nitpick, I think this does what it advertises, so:

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

Thanks,
-Eric

>  	if (pctx->errcode &&
>  	    fix_problem(ctx, PR_1_EXTENT_ITERATE_FAILURE, pctx)) {
>  		pb->num_blocks = 0;
> diff --git a/e2fsck/problem.c b/e2fsck/problem.c
> index 76bc1d5..b0a6e19 100644
> --- a/e2fsck/problem.c
> +++ b/e2fsck/problem.c
> @@ -1008,6 +1008,12 @@ static struct e2fsck_problem problem_table[] = {
>  	     "Logical start %b does not match logical start %c at next level.  "),
>  	  PROMPT_FIX, 0 },
>  
> +	/* Extent end is out of bounds for the tree */
> +	{ PR_1_EXTENT_END_OUT_OF_BOUNDS,
> +	  N_("@i %i, end of extent exceeds allowed value\n\t(logical @b %c, physical @b %b, len %N)\n"),
> +	  PROMPT_CLEAR, 0 },
> +
> +
>  	/* Pass 1b errors */
>  
>  	/* Pass 1B: Rescan for duplicate/bad blocks */
> diff --git a/e2fsck/problem.h b/e2fsck/problem.h
> index d2b6df4..fcdc1a1 100644
> --- a/e2fsck/problem.h
> +++ b/e2fsck/problem.h
> @@ -589,6 +589,7 @@ struct problem_context {
>  /* Index start doesn't match start of next extent down */
>  #define PR_1_EXTENT_INDEX_START_INVALID	0x01006D
>  
> +#define PR_1_EXTENT_END_OUT_OF_BOUNDS	0x01006E
>  /*
>   * Pass 1b errors
>   */
> --
> 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
> 

--
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
Theodore Ts'o - June 7, 2013, 3:35 a.m.
On Tue, Jun 04, 2013 at 02:53:51PM -0500, Eric Sandeen wrote:
> 
> Here's an image which demonstrates this, current e2fsck does not detect
> the error.

Thanks.  For future reference, here's how you can use debugfs to
generate a much smaller image which demonstrates the problem, suitable
for use in a regression test.

					- Ted

#!/bin/sh
dd if=/dev/zero of=image bs=1k count=256
mke2fs -Ft ext4 image
debugfs -w image << EOF
write /dev/null testfile
extent_open testfile
  insert_node 0 15 100
  insert_node --after 15 15 115
  insert_node --after 30 15 130
  insert_node --after 45 15 145
  split
  down
  split
  root
  down
  next
  replace_node 15 30 200
  extent_close
set_inode_field testfile i_size 61400
set_inode_field testfile i_blocks 154
setb 100 15
setb 130 30
setb 200 30
set_bg 0 free_blocks_count 156
set_bg 0 bg_checksum calc
set_super_value free_blocks_count 156
EOF

--
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
Eric Sandeen - June 7, 2013, 3:40 a.m.
On 6/6/13 10:35 PM, Theodore Ts'o wrote:
> On Tue, Jun 04, 2013 at 02:53:51PM -0500, Eric Sandeen wrote:
>>
>> Here's an image which demonstrates this, current e2fsck does not detect
>> the error.
> 
> Thanks.  For future reference, here's how you can use debugfs to
> generate a much smaller image which demonstrates the problem, suitable
> for use in a regression test.

Ah.  Well, I did use debugfs to make it, but not quite so compactly.  :)

Thanks,
-Eric

> 					- Ted
> 
> #!/bin/sh
> dd if=/dev/zero of=image bs=1k count=256
> mke2fs -Ft ext4 image
> debugfs -w image << EOF
> write /dev/null testfile
> extent_open testfile
>   insert_node 0 15 100
>   insert_node --after 15 15 115
>   insert_node --after 30 15 130
>   insert_node --after 45 15 145
>   split
>   down
>   split
>   root
>   down
>   next
>   replace_node 15 30 200
>   extent_close
> set_inode_field testfile i_size 61400
> set_inode_field testfile i_blocks 154
> setb 100 15
> setb 130 30
> setb 200 30
> set_bg 0 free_blocks_count 156
> set_bg 0 bg_checksum calc
> set_super_value free_blocks_count 156
> EOF
> 
> --
> 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
> 

--
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

Patch

diff --git a/e2fsck/pass1.c b/e2fsck/pass1.c
index a20b57b..198e9a0 100644
--- a/e2fsck/pass1.c
+++ b/e2fsck/pass1.c
@@ -1848,7 +1848,7 @@  void e2fsck_clear_inode(e2fsck_t ctx, ext2_ino_t ino,
 
 static void scan_extent_node(e2fsck_t ctx, struct problem_context *pctx,
 			     struct process_block_struct *pb,
-			     blk64_t start_block,
+			     blk64_t start_block, blk64_t end_block,
 			     ext2_extent_handle_t ehandle)
 {
 	struct ext2fs_extent	extent;
@@ -1891,6 +1891,9 @@  static void scan_extent_node(e2fsck_t ctx, struct problem_context *pctx,
 			problem = PR_1_EXTENT_BAD_START_BLK;
 		else if (extent.e_lblk < start_block)
 			problem = PR_1_OUT_OF_ORDER_EXTENTS;
+		else if (end_block &&
+			 (extent.e_lblk + extent.e_len) > end_block)
+			problem = PR_1_EXTENT_END_OUT_OF_BOUNDS;
 		else if (is_leaf && extent.e_len == 0)
 			problem = PR_1_EXTENT_LENGTH_ZERO;
 		else if (is_leaf &&
@@ -1937,10 +1940,11 @@  fix_problem_now:
 		}
 
 		if (!is_leaf) {
-			blk64_t lblk;
+			blk64_t lblk, lblk_end;
 
 			blk = extent.e_pblk;
 			lblk = extent.e_lblk;
+			lblk_end = extent.e_lblk + extent.e_len;
 			pctx->errcode = ext2fs_extent_get(ehandle,
 						  EXT2_EXTENT_DOWN, &extent);
 			if (pctx->errcode) {
@@ -1965,7 +1969,8 @@  fix_problem_now:
 				if (fix_problem(ctx, problem, pctx))
 					ext2fs_extent_fix_parents(ehandle);
 			}
-			scan_extent_node(ctx, pctx, pb, extent.e_lblk, ehandle);
+			scan_extent_node(ctx, pctx, pb, extent.e_lblk,
+					 lblk_end, ehandle);
 			if (pctx->errcode)
 				return;
 			pctx->errcode = ext2fs_extent_get(ehandle,
@@ -2084,7 +2089,7 @@  static void check_blocks_extents(e2fsck_t ctx, struct problem_context *pctx,
 		ctx->extent_depth_count[info.max_depth]++;
 	}
 
-	scan_extent_node(ctx, pctx, pb, 0, ehandle);
+	scan_extent_node(ctx, pctx, pb, 0, 0, ehandle);
 	if (pctx->errcode &&
 	    fix_problem(ctx, PR_1_EXTENT_ITERATE_FAILURE, pctx)) {
 		pb->num_blocks = 0;
diff --git a/e2fsck/problem.c b/e2fsck/problem.c
index 76bc1d5..b0a6e19 100644
--- a/e2fsck/problem.c
+++ b/e2fsck/problem.c
@@ -1008,6 +1008,12 @@  static struct e2fsck_problem problem_table[] = {
 	     "Logical start %b does not match logical start %c at next level.  "),
 	  PROMPT_FIX, 0 },
 
+	/* Extent end is out of bounds for the tree */
+	{ PR_1_EXTENT_END_OUT_OF_BOUNDS,
+	  N_("@i %i, end of extent exceeds allowed value\n\t(logical @b %c, physical @b %b, len %N)\n"),
+	  PROMPT_CLEAR, 0 },
+
+
 	/* Pass 1b errors */
 
 	/* Pass 1B: Rescan for duplicate/bad blocks */
diff --git a/e2fsck/problem.h b/e2fsck/problem.h
index d2b6df4..fcdc1a1 100644
--- a/e2fsck/problem.h
+++ b/e2fsck/problem.h
@@ -589,6 +589,7 @@  struct problem_context {
 /* Index start doesn't match start of next extent down */
 #define PR_1_EXTENT_INDEX_START_INVALID	0x01006D
 
+#define PR_1_EXTENT_END_OUT_OF_BOUNDS	0x01006E
 /*
  * Pass 1b errors
  */