fix header check in ext4_ext_search_right() for deep extent trees.

PATCH In review Eric Sandeen 3 participants 8 messages Mar 6, 2009 – Mar 9, 2009 ext4 file system

lore

Share & tools

lore

Eric Sandeen

author

2009-03-06 20:50 UTC #0 lore raw

PATCH 1/1 fix header check in ext4_ext_search_right() for deep extent trees.

This should resolve kernel.org bugzilla 12821

I've not actually crafted a workload to exercise this code; this is from inspection...

The ext4_ext_search_right() function is confusing; it uses a "depth" variable which is 0 at the root and maximum at the leaves, but the on-disk metadata uses a "depth" (actually eh_depth) which is opposite: maximum at the root, and 0 at the leaves.

The ext4_ext_check_header() function is given a depth and checks the header agaisnt that depth; it expects the on-disk semantics, but we are giving it the opposite in the while loop in this function. We should be giving it the on-disk notion of "depth" which we can get from (p_depth - depth) - and if you look, the last (more commonly hit) call to ext4_ext_check_header() does just this.

Sending in the wrong depth results in (incorrect) messages about corruption:

EXT4-fs error (device sdb1): ext4_ext_search_right: bad header in inode #2621457: unexpected eh_depth - magic f30a, entries 340, max 340(0), depth 1(2)

Reported-by David Dindorp <[email protected]>

Signed-off-by Eric Sandeen <[email protected]>

fs/ext4/extents.c +4 -2

Index: linux-2.6/fs/ext4/extents.c
===================================================================
@@ -1122,7 +1122,8 @@ ext4_ext_search_right(struct inode *inod
 	struct ext4_extent_idx *ix;
 	struct ext4_extent *ex;
 	ext4_fsblk_t block;
-	int depth, ee_len;
+	int depth;	/* Note, NOT eh_depth; depth from top of tree */
+	int ee_len;
 
 	BUG_ON(path == NULL);
 	depth = path->p_depth;

@@ -1179,7 +1180,8 @@ got_index:
 		if (bh == NULL)
 			return -EIO;
 		eh = ext_block_hdr(bh);
-		if (ext4_ext_check_header(inode, eh, depth)) {
+		/* subtract from p_depth to get proper eh_depth */
+		if (ext4_ext_check_header(inode, eh, path->p_depth - depth)) {
 			put_bh(bh);
 			return -EIO;
 		}

Aneesh Kumar K.V

Reviewed-by on v1 1/1

2009-03-09 05:00 UTC #1 lore raw

Quoted 10 lines · Eric Sandeen

This should resolve kernel.org bugzilla 12821
I've not actually crafted a workload to exercise this code; this is from inspection...
The ext4_ext_search_right() function is confusing; it uses a "depth" variable which is 0 at the root and maximum at the leaves, but the on-disk metadata uses a "depth" (actually eh_depth) which is opposite: maximum at the root, and 0 at the leaves.

Quoted 6 lines

The ext4_ext_check_header() function is given a depth and checks the header agaisnt that depth; it expects the on-disk semantics, but we are giving it the opposite in the while loop in this function. We should be giving it the on-disk notion of "depth" which we can get from (p_depth - depth) - and if you look, the last (more commonly hit) call to ext4_ext_check_header() does just this.

Correct. Few lines below we are passing the right depth when verifying the leaf blocks. So I guess it was a coding error.

Quoted 10 lines

Sending in the wrong depth results in (incorrect) messages about corruption:
EXT4-fs error (device sdb1): ext4_ext_search_right: bad header in inode #2621457: unexpected eh_depth - magic f30a, entries 340, max 340(0), depth 1(2)
Reported-by David Dindorp <[email protected]>
Signed-off-by Eric Sandeen <[email protected]>

Reviewed-by Aneesh Kumar K.V <[email protected]>

Quoted 18 lines

Index: linux-2.6/fs/ext4/extents.c
===================================================================

fs/ext4/extents.c +2 -1

@@ -1122,7 +1122,8 @@ ext4_ext_search_right(struct inode *inod
 	struct ext4_extent_idx *ix;
 	struct ext4_extent *ex;
 	ext4_fsblk_t block;
-	int depth, ee_len;
+	int depth;	/* Note, NOT eh_depth; depth from top of tree */
+	int ee_len;
 
 	BUG_ON(path == NULL);
 	depth = path->p_depth;

fs/ext4/extents.c got_index: · line 1187

Quoted 9 lines

fs/ext4/extents.c +2 -1

@@ -1179,7 +1180,8 @@ got_index:
 		if (bh == NULL)
 			return -EIO;
 		eh = ext_block_hdr(bh);
-		if (ext4_ext_check_header(inode, eh, depth)) {
+		/* subtract from p_depth to get proper eh_depth */
+		if (ext4_ext_check_header(inode, eh, path->p_depth - depth)) {
 			put_bh(bh);
 			return -EIO;
 		}

-aneesh

Theodore Tso

maintainer

2009-03-09 11:36 UTC #2 lore raw

In reply to Eric Sandeen

Quoted 4 lines · Eric Sandeen

This should resolve kernel.org bugzilla 12821
I've not actually crafted a workload to exercise this code; this is from inspection...

Hmm, so I've been trying to create a test case, but the test cases I've created (which e2fsck say are fine) aren't causing complaints by the kernel.

Please see:

http://master.kernel.org/~tytso/deep-tree/

deep-tree.img.gz contains an extent tree of depth 3, and deep-tree-2.img.gz contains an extent tree of depth 4....

- Ted

Eric Sandeen

author

2009-03-09 15:53 UTC #3 lore raw

Quoted 10 lines · Theodore Tso

Quoted 4 lines · Eric Sandeen
This should resolve kernel.org bugzilla 12821
I've not actually crafted a workload to exercise this code; this is from inspection...
Hmm, so I've been trying to create a test case, but the test cases I've created (which e2fsck say are fine) aren't causing complaints by the kernel.

Quoted 8 lines

Please see:
http://master.kernel.org/~tytso/deep-tree/
deep-tree.img.gz contains an extent tree of depth 3, and deep-tree-2.img.gz contains an extent tree of depth 4....
- Ted

I've had no trouble creating a deep tree, but I have had trouble making it actually exercise the code in that loop.

I think the initial ext4_ext_find_extent() needs to land us in just the right place such that the search_right must traverse back up & back down the tree to get the nearest right allocation... I haven't sorted that out yet.

I'd feel better w/ a testcase to demonstrate correctness too, but I'm 99.9% sure that the fix is correct by inspection, and would rather see it get into .29 sooner than later unless you have strong misgivings.

-Eric

Aneesh Kumar K.V

2009-03-09 16:01 UTC #4 lore raw

In reply to Theodore Tso

Quoted 10 lines · Theodore Tso

Quoted 4 lines · Eric Sandeen
This should resolve kernel.org bugzilla 12821
I've not actually crafted a workload to exercise this code; this is from inspection...
Hmm, so I've been trying to create a test case, but the test cases I've created (which e2fsck say are fine) aren't causing complaints by the kernel.

Quoted 5 lines

Please see:
http://master.kernel.org/~tytso/deep-tree/
deep-tree.img.gz contains an extent tree of depth 3, and

With depth 3 we would have path->p_depth = 2 and with middle index block would have eh->eh_depth = 1 and depth variable also will be having value 1. (also path->p_depth - depth)

Quoted 2 lines

deep-tree-2.img.gz contains an extent tree of depth 4....

So what is the logical block number with which you trying to allocate blocks in deep-tree-2.img.gz

-aneesh

Eric Sandeen

author

2009-03-09 16:13 UTC #5 lore raw

Quoted 12 lines · Aneesh Kumar K.V

Quoted 11 lines · Theodore Tso
Quoted 4 lines · Eric Sandeen
This should resolve kernel.org bugzilla 12821
I've not actually crafted a workload to exercise this code; this is from inspection...
Hmm, so I've been trying to create a test case, but the test cases I've created (which e2fsck say are fine) aren't causing complaints by the kernel.
Please see:

Quoted 10 lines

Quoted 3 lines
http://master.kernel.org/~tytso/deep-tree/
deep-tree.img.gz contains an extent tree of depth 3, and
With depth 3 we would have path->p_depth = 2 and with middle index block would have eh->eh_depth = 1 and depth variable also will be having value 1. (also path->p_depth - depth)
Quoted 2 lines
deep-tree-2.img.gz contains an extent tree of depth 4....

I think this jives w/ what the reporter had, although in the e2image the problematic inode only had depth 3 (at the time)

for 4 levels, p_depth would be 3, so for

depth eh_depth p_depth-depth
0 3 3
1 2 2
2 1 1 <----check got 2, expected 1
3 0 0

he got:

ext4_ext_search_right: bad header in inode #2621457: unexpected eh_depth
- magic f30a, entries 340, max 340(0), depth 1(2)

Quoted 2 lines

So what is the logical block number with which you trying to allocate blocks in deep-tree-2.img.gz

yep that's the key :)

-Eric

Quoted 1 line

-aneesh

Theodore Tso

maintainer

2009-03-09 17:35 UTC #6 lore raw

Quoted 5 lines · Eric Sandeen

Quoted 2 lines
Quoted 2 lines
deep-tree-2.img.gz contains an extent tree of depth 4....
I think this jives w/ what the reporter had, although in the e2image the problematic inode only had depth 3 (at the time)

I'm downloading and decompressing the e2image from the reporter right now. Have you tried mounting the e2image over the loop device with and without the patch? That should be able to demonstrate the problem, and then prove that the patch fixes it. I'll also dump out the extent tree from the reporter and try to create a small test case based on the inode in question. (Inode #2621457, right?)

- Ted

Eric Sandeen

author

2009-03-09 17:52 UTC #7 lore raw

Quoted 6 lines · Theodore Tso

Quoted 4 lines · Eric Sandeen
Quoted 2 lines
Quoted 2 lines
deep-tree-2.img.gz contains an extent tree of depth 4....
I think this jives w/ what the reporter had, although in the e2image the problematic inode only had depth 3 (at the time)

Quoted 8 lines

I'm downloading and decompressing the e2image from the reporter right now. Have you tried mounting the e2image over the loop device with and without the patch? That should be able to demonstrate the problem, and then prove that the patch fixes it. I'll also dump out the extent tree from the reporter and try to create a small test case based on the inode in question. (Inode #2621457, right?)
- Ted

I have mounted it but I'm not sure that's sufficient to trip the case.

A dump of the inode in question from the e2image is at:

http://bugzilla.kernel.org/attachment.cgi?id=20449&action=view

(slightly massaged from default output)

-Eric