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

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

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

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 <ddi@dubex.dk>
Signed-off-by: Eric Sandeen <sandeen@redhat.com>
--

Index: linux-2.6/fs/ext4/extents.c
===================================================================
--- linux-2.6.orig/fs/ext4/extents.c
+++ 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;
 		}

Re: [PATCH] fix header check in ext4_ext_search_right() for deep extent trees.

[Aneesh Kumar K.V]

On Fri, Mar 06, 2009 at 02:50:51PM -0600, Eric Sandeen wrote:
> 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.

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


> 
> 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 <ddi@dubex.dk>
> Signed-off-by: Eric Sandeen <sandeen@redhat.com>


Reviewed-by: Aneesh Kumar K.V <aneesh.kumar@linux.vnet.ibm.com>


> --
> 
> Index: linux-2.6/fs/ext4/extents.c
> ===================================================================
> --- linux-2.6.orig/fs/ext4/extents.c
> +++ 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

Re: [PATCH] fix header check in ext4_ext_search_right() for deep extent trees.

[Theodore Tso]

On Fri, Mar 06, 2009 at 02:50:51PM -0600, Eric Sandeen wrote:
> 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

Re: [PATCH] fix header check in ext4_ext_search_right() for deep extent trees.

[Eric Sandeen]

Theodore Tso wrote:
> On Fri, Mar 06, 2009 at 02:50:51PM -0600, Eric Sandeen wrote:
>> 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

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

Re: [PATCH] fix header check in ext4_ext_search_right() for deep extent trees.

[Aneesh Kumar K.V]

On Mon, Mar 09, 2009 at 07:36:19AM -0400, Theodore Tso wrote:
> On Fri, Mar 06, 2009 at 02:50:51PM -0600, Eric Sandeen wrote:
> > 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

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)


> 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

Re: [PATCH] fix header check in ext4_ext_search_right() for deep extent trees.

[Eric Sandeen]

Aneesh Kumar K.V wrote:
> On Mon, Mar 09, 2009 at 07:36:19AM -0400, Theodore Tso wrote:
>> On Fri, Mar 06, 2009 at 02:50:51PM -0600, Eric Sandeen wrote:
>>> 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
> 
> 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)

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

> 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

> -aneesh

Re: [PATCH] fix header check in ext4_ext_search_right() for deep extent trees.

[Theodore Tso]

On Mon, Mar 09, 2009 at 11:13:08AM -0500, Eric Sandeen wrote:
> >> 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

Re: [PATCH] fix header check in ext4_ext_search_right() for deep extent trees.

[Eric Sandeen]

Theodore Tso wrote:
> On Mon, Mar 09, 2009 at 11:13:08AM -0500, Eric Sandeen wrote:
>>>> 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

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