Skip to contentSkip to conversation

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

PATCH In review David Jeffery 4 participants 8 messages Apr 3, 2013 – Jul 16, 2013

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 e2fsck: detect invalid extents at the end of an extent-block

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.

Quoted 1 line

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.

---
 e2fsck/pass1.c   |   13 +++++++++----
 e2fsck/problem.c |    6 ++++++
 e2fsck/problem.h |    1 +
 3 files changed, 16 insertions(+), 4 deletions(-)
e2fsck/pass1.c +9 -4
index a20b57b..198e9a0 100644
@@ -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;
e2fsck/problem.c +6 -0
index 76bc1d5..b0a6e19 100644
@@ -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 */
e2fsck/problem.h +1 -0
index d2b6df4..fcdc1a1 100644
@@ -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
  */
#1 lore raw
Quoted 13 lines · David Jeffery

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
Quoted 5 lines

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

Quoted 96 lines
---
 e2fsck/pass1.c   |   13 +++++++++----
 e2fsck/problem.c |    6 ++++++
 e2fsck/problem.h |    1 +
 3 files changed, 16 insertions(+), 4 deletions(-)
e2fsck/pass1.c +9 -4
index a20b57b..198e9a0 100644
@@ -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;
e2fsck/problem.c +6 -0
index 76bc1d5..b0a6e19 100644
@@ -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 */
e2fsck/problem.h +1 -1
index d2b6df4..fcdc1a1 100644
@@ -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 [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

#2 lore raw
Quoted 3 lines · Eric Sandeen

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

#3 lore raw
Quoted 8 lines · Theodore Ts'o
Quoted 3 lines · Eric Sandeen

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

Quoted 35 lines

- 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 [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

Reviewed-by on v1 1/1
#4 lore raw
In reply to David Jeffery
Quoted 40 lines · David Jeffery

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.

---
 e2fsck/pass1.c   |   13 +++++++++----
 e2fsck/problem.c |    6 ++++++
 e2fsck/problem.h |    1 +
 3 files changed, 16 insertions(+), 4 deletions(-)
e2fsck/pass1.c +1 -1
index a20b57b..198e9a0 100644
@@ -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;

e2fsck/pass1.c static void scan_extent_node(e2fsck_t ctx, struct problem_context *pctx, · line 1896

Quoted 6 lines
e2fsck/pass1.c +3 -0
@@ -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?

e2fsck/pass1.c fix_problem_now: · line 1947

Quoted 13 lines
e2fsck/pass1.c +2 -1
 		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 ?

Quoted 14 lines
e2fsck/pass1.c +2 -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,

e2fsck/pass1.c static void check_blocks_extents(e2fsck_t ctx, struct problem_context *pctx, · line 2092

Quoted 5 lines
e2fsck/pass1.c +1 -1
@@ -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:

Thanks,
-Eric

Quoted 37 lines
e2fsck/pass1.c +0 -0
 	if (pctx->errcode &&
 	    fix_problem(ctx, PR_1_EXTENT_ITERATE_FAILURE, pctx)) {
 		pb->num_blocks = 0;
e2fsck/problem.c +6 -0
index 76bc1d5..b0a6e19 100644
@@ -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 */
e2fsck/problem.h +1 -1
index d2b6df4..fcdc1a1 100644
@@ -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 [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

Reviewed-by Eric Sandeen
#5 lore raw

Thanks for the review. I took your changes, and added a bit more code cleanup.

Here's the version I ultimately checked into my tree.

- Ted

commit d3f32c2db8f11c87aa7939d78e7eb4c373f7034f

Author: David Jeffery <[email protected]>
Date:   Thu Jun 6 20:04:33 2013 -0400

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

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.

e2fsck/pass1.c +11 -8
index de00638..af9afe3 100644
@@ -1760,11 +1760,11 @@ 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;
-	blk64_t			blk;
+	blk64_t			blk, last_lblk;
 	e2_blkcnt_t		blockcnt;
 	unsigned int		i;
 	int			is_dir, is_leaf;
@@ -1780,6 +1780,7 @@ static void scan_extent_node(e2fsck_t ctx, struct problem_context *pctx,
 	while (!pctx->errcode && info.num_entries-- > 0) {
 		is_leaf = extent.e_flags & EXT2_EXTENT_FLAGS_LEAF;
 		is_dir = LINUX_S_ISDIR(pctx->inode->i_mode);
+		last_lblk = extent.e_lblk + extent.e_len - 1;
 
 		problem = 0;
 		if (extent.e_pblk == 0 ||
@@ -1788,6 +1789,8 @@ 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 && last_lblk > 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 &&
@@ -1822,10 +1825,9 @@ report_problem:
 		}
 
 		if (!is_leaf) {
-			blk64_t lblk;
+			blk64_t lblk = extent.e_lblk;
 
 			blk = extent.e_pblk;
-			lblk = extent.e_lblk;
 			pctx->errcode = ext2fs_extent_get(ehandle,
 						  EXT2_EXTENT_DOWN, &extent);
 			if (pctx->errcode) {
@@ -1847,7 +1849,8 @@ report_problem:
 				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,
+					 last_lblk, ehandle);
 			if (pctx->errcode)
 				return;
 			pctx->errcode = ext2fs_extent_get(ehandle,
@@ -1928,10 +1931,10 @@ report_problem:
 		if (is_dir && extent.e_len > 0)
 			pb->last_db_block = blockcnt - 1;
 		pb->previous_block = extent.e_pblk + extent.e_len - 1;
-		start_block = pb->last_block = extent.e_lblk + extent.e_len - 1;
+		start_block = pb->last_block = last_lblk;
 		if (is_leaf && !is_dir &&
 		    !(extent.e_flags & EXT2_EXTENT_FLAGS_UNINIT))
-			pb->last_init_lblock = extent.e_lblk + extent.e_len - 1;
+			pb->last_init_lblock = last_lblk;
 	next:
 		pctx->errcode = ext2fs_extent_get(ehandle,
 						  EXT2_EXTENT_NEXT_SIB,
@@ -1967,7 +1970,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;
e2fsck/problem.c +6 -0
index 05ef626..6d03765 100644
@@ -954,6 +954,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 */
e2fsck/problem.h +1 -0
index aed524d..b578678 100644
@@ -561,6 +561,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
  */
#6 lore raw
Quoted 4 lines · Theodore Ts'o

Thanks for the review. I took your changes, and added a bit more code cleanup.

Here's the version I ultimately checked into my tree.

This patch cause regression TESTCASE:
#!/bin/bash

IMG=./IMG
MNT=/mnt
dd if=/dev/zero of=$IMG bs=1M count=16 mkfs.ext4 -b4096 -F $IMG
mount $IMG $MNT -oloop || exit 1 fallocate -n -l $((1024*1024*2)) $MNT/f1

for ((i=0;i<4;i++))
do

    dd if=/dev/zero of=$MNT/f1 bs=4k count=1 seek=$((i*100)) conv=notrunc

done
sync
filefrag -v $MNT/f1
umount $MNT
e2fsck -f -n $IMG

Quoted 144 lines

- Ted

commit d3f32c2db8f11c87aa7939d78e7eb4c373f7034f

Author: David Jeffery <[email protected]>
Date:   Thu Jun 6 20:04:33 2013 -0400

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

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.

e2fsck/pass1.c +11 -8
index de00638..af9afe3 100644
@@ -1760,11 +1760,11 @@ 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;
-	blk64_t			blk;
+	blk64_t			blk, last_lblk;
 	e2_blkcnt_t		blockcnt;
 	unsigned int		i;
 	int			is_dir, is_leaf;
@@ -1780,6 +1780,7 @@ static void scan_extent_node(e2fsck_t ctx, struct problem_context *pctx,
 	while (!pctx->errcode && info.num_entries-- > 0) {
 		is_leaf = extent.e_flags & EXT2_EXTENT_FLAGS_LEAF;
 		is_dir = LINUX_S_ISDIR(pctx->inode->i_mode);
+		last_lblk = extent.e_lblk + extent.e_len - 1;
 
 		problem = 0;
 		if (extent.e_pblk == 0 ||
@@ -1788,6 +1789,8 @@ 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 && last_lblk > 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 &&
@@ -1822,10 +1825,9 @@ report_problem:
 		}
 
 		if (!is_leaf) {
-			blk64_t lblk;
+			blk64_t lblk = extent.e_lblk;
 
 			blk = extent.e_pblk;
-			lblk = extent.e_lblk;
 			pctx->errcode = ext2fs_extent_get(ehandle,
 						  EXT2_EXTENT_DOWN, &extent);
 			if (pctx->errcode) {
@@ -1847,7 +1849,8 @@ report_problem:
 				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,
+					 last_lblk, ehandle);
 			if (pctx->errcode)
 				return;
 			pctx->errcode = ext2fs_extent_get(ehandle,
@@ -1928,10 +1931,10 @@ report_problem:
 		if (is_dir && extent.e_len > 0)
 			pb->last_db_block = blockcnt - 1;
 		pb->previous_block = extent.e_pblk + extent.e_len - 1;
-		start_block = pb->last_block = extent.e_lblk + extent.e_len - 1;
+		start_block = pb->last_block = last_lblk;
 		if (is_leaf && !is_dir &&
 		    !(extent.e_flags & EXT2_EXTENT_FLAGS_UNINIT))
-			pb->last_init_lblock = extent.e_lblk + extent.e_len - 1;
+			pb->last_init_lblock = last_lblk;
 	next:
 		pctx->errcode = ext2fs_extent_get(ehandle,
 						  EXT2_EXTENT_NEXT_SIB,
@@ -1967,7 +1970,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;
e2fsck/problem.c +6 -0
index 05ef626..6d03765 100644
@@ -954,6 +954,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 */
e2fsck/problem.h +1 -1
index aed524d..b578678 100644
@@ -561,6 +561,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 [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

#7 lore raw
Quoted 16 lines · Dmitry Monakhov
Quoted 4 lines · Theodore Ts'o

Thanks for the review. I took your changes, and added a bit more code cleanup.

Here's the version I ultimately checked into my tree.

This patch cause regression
TESTCASE:
#!/bin/bash

IMG=./IMG
MNT=/mnt
dd if=/dev/zero of=$IMG bs=1M count=16
mkfs.ext4 -b4096 -F $IMG
mount $IMG $MNT -oloop || exit 1
fallocate -n -l $((1024*1024*2)) $MNT/f1

Quoted 8 lines

for ((i=0;i<4;i++))
do

    dd if=/dev/zero of=$MNT/f1 bs=4k count=1 seek=$((i*100)) conv=notrunc

done
sync
filefrag -v $MNT/f1
umount $MNT
e2fsck -f -n $IMG

Yes,this is the case where extents past EOF aren't updating the parent node in the extent tree:

e2fsck 1.43-WIP (20-Jun-2013)
Pass 1: Checking inodes, blocks, and sizes
Inode 12, end of extent exceeds allowed value

	(logical block 301, physical block 1464, len 211)

Clear? no

Inode 12, i_blocks is 4112, should be 2424. Fix? no

Pass 2: Checking directory structure
Pass 3: Checking directory connectivity
Pass 4: Checking reference counts
Pass 5: Checking group summary information
Block bitmap differences: -(1464--1674)
Fix? no

The file looks like this:

debugfs: ex f1
Level Entries Logical Physical Length Flags
0/ 1 1/ 1 0 - 300 1675 301
^^^ length 301
^^ last logical block at 300

 1/ 1   1/  8     0 -     0  1163 -  1163      1 
 1/ 1   2/  8     1 -    99  1164 -  1262     99 Uninit
 1/ 1   3/  8   100 -   100  1263 -  1263      1 
 1/ 1   4/  8   101 -   199  1264 -  1362     99 Uninit
 1/ 1   5/  8   200 -   200  1363 -  1363      1 
 1/ 1   6/  8   201 -   299  1364 -  1462     99 Uninit
 1/ 1   7/  8   300 -   300  1463 -  1463      1 
 1/ 1   8/  8   301 -   511  1464 -  1674    211 Uninit

^^ extent past EOF extends beyond parent

Ted thought that was OK, I guess, but that seems very strange to me. Why would we NOT update the length/range of the parent block?

Where EOF/i_size happens to land should be orthogonal to how the extent tree is described, I would expect.

I asked in:

Subject: fallocated blocks past EOF & past parent node range OK?

but there's been no discussion so far. I'd like to understand why it's felt that the tree above is not considered to be corrupt.

Thanks,
-Eric

Quoted 149 lines
Quoted 141 lines

- Ted

commit d3f32c2db8f11c87aa7939d78e7eb4c373f7034f

Author: David Jeffery <[email protected]>
Date:   Thu Jun 6 20:04:33 2013 -0400

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

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.

e2fsck/pass1.c +11 -8
index de00638..af9afe3 100644
@@ -1760,11 +1760,11 @@ 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;
-	blk64_t			blk;
+	blk64_t			blk, last_lblk;
 	e2_blkcnt_t		blockcnt;
 	unsigned int		i;
 	int			is_dir, is_leaf;
@@ -1780,6 +1780,7 @@ static void scan_extent_node(e2fsck_t ctx, struct problem_context *pctx,
 	while (!pctx->errcode && info.num_entries-- > 0) {
 		is_leaf = extent.e_flags & EXT2_EXTENT_FLAGS_LEAF;
 		is_dir = LINUX_S_ISDIR(pctx->inode->i_mode);
+		last_lblk = extent.e_lblk + extent.e_len - 1;
 
 		problem = 0;
 		if (extent.e_pblk == 0 ||
@@ -1788,6 +1789,8 @@ 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 && last_lblk > 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 &&
@@ -1822,10 +1825,9 @@ report_problem:
 		}
 
 		if (!is_leaf) {
-			blk64_t lblk;
+			blk64_t lblk = extent.e_lblk;
 
 			blk = extent.e_pblk;
-			lblk = extent.e_lblk;
 			pctx->errcode = ext2fs_extent_get(ehandle,
 						  EXT2_EXTENT_DOWN, &extent);
 			if (pctx->errcode) {
@@ -1847,7 +1849,8 @@ report_problem:
 				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,
+					 last_lblk, ehandle);
 			if (pctx->errcode)
 				return;
 			pctx->errcode = ext2fs_extent_get(ehandle,
@@ -1928,10 +1931,10 @@ report_problem:
 		if (is_dir && extent.e_len > 0)
 			pb->last_db_block = blockcnt - 1;
 		pb->previous_block = extent.e_pblk + extent.e_len - 1;
-		start_block = pb->last_block = extent.e_lblk + extent.e_len - 1;
+		start_block = pb->last_block = last_lblk;
 		if (is_leaf && !is_dir &&
 		    !(extent.e_flags & EXT2_EXTENT_FLAGS_UNINIT))
-			pb->last_init_lblock = extent.e_lblk + extent.e_len - 1;
+			pb->last_init_lblock = last_lblk;
 	next:
 		pctx->errcode = ext2fs_extent_get(ehandle,
 						  EXT2_EXTENT_NEXT_SIB,
@@ -1967,7 +1970,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;
e2fsck/problem.c +6 -0
index 05ef626..6d03765 100644
@@ -954,6 +954,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 */
e2fsck/problem.h +1 -1
index aed524d..b578678 100644
@@ -561,6 +561,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
  */
--
Quoted 3 lines

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

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