[PATCH] use-before-uninitialized value in ext3(2)_find_ goal

[PATCH] use-before-uninitialized value in ext3(2)_find_ goal

[Mingming Cao]

[-- Attachment #1: Type: text/plain, Size: 2506 bytes --]

I am looking at the how the goal for block allocation is determined in
in ext3_find_goal(), so I wrote a very simple test to do random write by
one process on one file (write() ,then lseek then write then lseek). 
The test shows a bug there.

There is a uninitialized goal value being referenced in both ext3 and
ext2 find goal block functions (ext3_find_goal() and ext2_find_goal()).
In the non-sequential write case, these functions check the goal
value(non zero) before calling ext3(2)_find_near() to find the goal
block to allocate. Since the goal value is uninitialized(non zero), the
ext3(2)_find_near() is never being called in the non-sequential write,
thus ext3(2)_find_goal() failed to guide a goal block in the random
write case. 

ext3(2)_new_block() takes the junk goal value and will turn it to goal 0
since it's normally beyond the filesystem block number limit.

The fix is trivial. 

There is a uninitialized goal value being referenced in both ext3 and ext2 find goal block functions (ext3_find_goal() and ext2_find_goal()). In the non-sequential write case, these functions check the goal value(non zero) before calling ext3(2)_find_near() to find the goal block to allocate. Since the goal value is uninitialized(non zero), the ext3(2)_find_near() is never being called in the non-sequential write, thus ext3(2)_find_goal() failed to guide a goal block in the random write case. ext3(2)_new_block() takes the junk goal value and will turn it to goal 0 since it's normally beyond the filesystem block number limit. The fix is trivial. 


---

 src-ming/fs/ext2/inode.c |    1 +
 src-ming/fs/ext3/inode.c |    1 +
 2 files changed, 2 insertions(+)

diff -puN fs/ext3/inode.c~ext3_find_goal_uninitialization_fix fs/ext3/inode.c
--- src/fs/ext3/inode.c~ext3_find_goal_uninitialization_fix	2004-05-19 18:30:13.857197080 -0700
+++ src-ming/fs/ext3/inode.c	2004-05-19 18:45:31.689665336 -0700
@@ -748,6 +748,7 @@ out:
 	if (err == -EAGAIN)
 		goto changed;
 
+	goal = 0;
 	down(&ei->truncate_sem);
 	if (ext3_find_goal(inode, iblock, chain, partial, &goal) < 0) {
 		up(&ei->truncate_sem);
diff -puN fs/ext2/inode.c~ext3_find_goal_uninitialization_fix fs/ext2/inode.c
--- src/fs/ext2/inode.c~ext3_find_goal_uninitialization_fix	2004-05-19 18:30:13.861196472 -0700
+++ src-ming/fs/ext2/inode.c	2004-05-19 18:45:40.586312840 -0700
@@ -584,6 +584,7 @@ out:
 	if (err == -EAGAIN)
 		goto changed;
 
+	goal = 0;
 	if (ext2_find_goal(inode, iblock, chain, partial, &goal) < 0)
 		goto changed;
 

_

[-- Attachment #2: ext3_find_goal_uninitialization_fix.patch --]
[-- Type: text/plain, Size: 1636 bytes --]


There is a uninitialized goal value being referenced in both ext3 and ext2 find goal block functions (ext3_find_goal() and ext2_find_goal()). In the non-sequential write case, these functions check the goal value(non zero) before calling ext3(2)_find_near() to find the goal block to allocate. Since the goal value is uninitialized(non zero), the ext3(2)_find_near() is never being called in the non-sequential write, thus ext3(2)_find_goal() failed to guide a goal block in the random write case. ext3(2)_new_block() takes the junk goal value and will turn it to goal 0 since it's normally beyond the filesystem block number limit. The fix is trivial. 


---

 src-ming/fs/ext2/inode.c |    1 +
 src-ming/fs/ext3/inode.c |    1 +
 2 files changed, 2 insertions(+)

diff -puN fs/ext3/inode.c~ext3_find_goal_unintialization_fix fs/ext3/inode.c
--- src/fs/ext3/inode.c~ext3_find_goal_unintialization_fix	2004-05-19 18:30:13.857197080 -0700
+++ src-ming/fs/ext3/inode.c	2004-05-19 18:45:31.689665336 -0700
@@ -748,6 +748,7 @@ out:
 	if (err == -EAGAIN)
 		goto changed;
 
+	goal = 0;
 	down(&ei->truncate_sem);
 	if (ext3_find_goal(inode, iblock, chain, partial, &goal) < 0) {
 		up(&ei->truncate_sem);
diff -puN fs/ext2/inode.c~ext3_find_goal_unintialization_fix fs/ext2/inode.c
--- src/fs/ext2/inode.c~ext3_find_goal_unintialization_fix	2004-05-19 18:30:13.861196472 -0700
+++ src-ming/fs/ext2/inode.c	2004-05-19 18:45:40.586312840 -0700
@@ -584,6 +584,7 @@ out:
 	if (err == -EAGAIN)
 		goto changed;
 
+	goal = 0;
 	if (ext2_find_goal(inode, iblock, chain, partial, &goal) < 0)
 		goto changed;
 

_

Re: [PATCH] use-before-uninitialized value in ext3(2)_find_ goal

[Chris Wright]

* Mingming Cao (cmm@us.ibm.com) wrote:
> +	goal = 0;
>  	down(&ei->truncate_sem);
>  	if (ext3_find_goal(inode, iblock, chain, partial, &goal) < 0) {
...
> +	goal = 0;
>  	if (ext2_find_goal(inode, iblock, chain, partial, &goal) < 0)
>  		goto changed;

I know it's a slightly bigger patch, but would it make sense to just enforce
this as part of api?  Just a thought...(patch untested)

thanks,
-chris

--- linux-2.6.6-mm3/fs/ext2/inode.c~goal	2004-05-09 19:32:00.000000000 -0700
+++ linux-2.6.6-mm3/fs/ext2/inode.c	2004-05-19 12:27:11.968054560 -0700
@@ -366,6 +366,7 @@ static inline int ext2_find_goal(struct 
 				 unsigned long *goal)
 {
 	struct ext2_inode_info *ei = EXT2_I(inode);
+	unsigned long _goal = 0;
 	write_lock(&ei->i_meta_lock);
 	if (block == ei->i_next_alloc_block + 1) {
 		ei->i_next_alloc_block++;
@@ -377,10 +378,11 @@ static inline int ext2_find_goal(struct 
 		 * failing that at least try to get decent locality.
 		 */
 		if (block == ei->i_next_alloc_block)
-			*goal = ei->i_next_alloc_goal;
-		if (!*goal)
-			*goal = ext2_find_near(inode, partial);
+			_goal = ei->i_next_alloc_goal;
+		if (!_goal)
+			_goal = ext2_find_near(inode, partial);
 		write_unlock(&ei->i_meta_lock);
+		*goal = _goal;
 		return 0;
 	}
 	write_unlock(&ei->i_meta_lock);
--- linux-2.6.6-mm3/fs/ext3/inode.c~goal	2004-05-13 11:19:42.000000000 -0700
+++ linux-2.6.6-mm3/fs/ext3/inode.c	2004-05-19 12:25:48.441752488 -0700
@@ -461,6 +461,7 @@ static int ext3_find_goal(struct inode *
 			  Indirect *partial, unsigned long *goal)
 {
 	struct ext3_inode_info *ei = EXT3_I(inode);
+	unsigned long _goal = 0;
 	/* Writer: ->i_next_alloc* */
 	if (block == ei->i_next_alloc_block + 1) {
 		ei->i_next_alloc_block++;
@@ -474,9 +475,10 @@ static int ext3_find_goal(struct inode *
 		 * failing that at least try to get decent locality.
 		 */
 		if (block == ei->i_next_alloc_block)
-			*goal = ei->i_next_alloc_goal;
-		if (!*goal)
-			*goal = ext3_find_near(inode, partial);
+			_goal = ei->i_next_alloc_goal;
+		if (!_goal)
+			_goal = ext3_find_near(inode, partial);
+		*goal = _goal;
 		return 0;
 	}
 	/* Reader: end */

Re: [Ext2-devel] Re: [PATCH] use-before-uninitialized value in ext3(2)_find_ goal

[Mingming Cao]

On Wed, 2004-05-19 at 12:53, Chris Wright wrote:
> 
> I know it's a slightly bigger patch, but would it make sense to just enforce
> this as part of api?  Just a thought...(patch untested)

The patch itself (in both your way and my way) is trivial, so either way
is okey. 

But the changes it bring up is not trivial, the ext2/3 disk layout for
random writes could be changed heavily, though that's the expected way
(and hopefully result in the good direction). We need to benchmark the
random write on ext2/3 to see what the changes bring about.

I will try random writes on some benchmark later today.

Mingming

Re: [Ext2-devel] Re: [PATCH] use-before-uninitialized value in ext3(2)_find_ goal

[Matthew Wilcox]

On Wed, May 19, 2004 at 12:53:28PM -0700, Chris Wright wrote:
> I know it's a slightly bigger patch, but would it make sense to just enforce
> this as part of api?  Just a thought...(patch untested)

No, that doesn't work.  Look:

reread:
	...

        if (ext2_find_goal(inode, iblock, chain, partial, &goal) < 0)
                goto changed;

changed:
        while (partial > chain) {
                brelse(partial->bh);
                partial--;
        }
        goto reread;

So it's spaghetti code that can modify goal.  Yuck.

5 labels in one function?  3 backwards jumps?  Disgusting.

> --- linux-2.6.6-mm3/fs/ext2/inode.c~goal	2004-05-09 19:32:00.000000000 -0700
> +++ linux-2.6.6-mm3/fs/ext2/inode.c	2004-05-19 12:27:11.968054560 -0700
> @@ -366,6 +366,7 @@ static inline int ext2_find_goal(struct 
>  				 unsigned long *goal)
>  {
>  	struct ext2_inode_info *ei = EXT2_I(inode);
> +	unsigned long _goal = 0;
>  	write_lock(&ei->i_meta_lock);
>  	if (block == ei->i_next_alloc_block + 1) {
>  		ei->i_next_alloc_block++;
> @@ -377,10 +378,11 @@ static inline int ext2_find_goal(struct 
>  		 * failing that at least try to get decent locality.
>  		 */
>  		if (block == ei->i_next_alloc_block)
> -			*goal = ei->i_next_alloc_goal;
> -		if (!*goal)
> -			*goal = ext2_find_near(inode, partial);
> +			_goal = ei->i_next_alloc_goal;
> +		if (!_goal)
> +			_goal = ext2_find_near(inode, partial);
>  		write_unlock(&ei->i_meta_lock);
> +		*goal = _goal;
>  		return 0;
>  	}
>  	write_unlock(&ei->i_meta_lock);
> --- linux-2.6.6-mm3/fs/ext3/inode.c~goal	2004-05-13 11:19:42.000000000 -0700
> +++ linux-2.6.6-mm3/fs/ext3/inode.c	2004-05-19 12:25:48.441752488 -0700
> @@ -461,6 +461,7 @@ static int ext3_find_goal(struct inode *
>  			  Indirect *partial, unsigned long *goal)
>  {
>  	struct ext3_inode_info *ei = EXT3_I(inode);
> +	unsigned long _goal = 0;
>  	/* Writer: ->i_next_alloc* */
>  	if (block == ei->i_next_alloc_block + 1) {
>  		ei->i_next_alloc_block++;
> @@ -474,9 +475,10 @@ static int ext3_find_goal(struct inode *
>  		 * failing that at least try to get decent locality.
>  		 */
>  		if (block == ei->i_next_alloc_block)
> -			*goal = ei->i_next_alloc_goal;
> -		if (!*goal)
> -			*goal = ext3_find_near(inode, partial);
> +			_goal = ei->i_next_alloc_goal;
> +		if (!_goal)
> +			_goal = ext3_find_near(inode, partial);
> +		*goal = _goal;
>  		return 0;
>  	}
>  	/* Reader: end */
> 
> 
> -------------------------------------------------------
> This SF.Net email is sponsored by: SourceForge.net Broadband
> Sign-up now for SourceForge Broadband and get the fastest
> 6.0/768 connection for only $19.95/mo for the first 3 months!
> http://ads.osdn.com/?ad_id=2562&alloc_id=6184&op=click
> _______________________________________________
> Ext2-devel mailing list
> Ext2-devel@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/ext2-devel

-- 
"Next the statesmen will invent cheap lies, putting the blame upon 
the nation that is attacked, and every man will be glad of those
conscience-soothing falsities, and will diligently study them, and refuse
to examine any refutations of them; and thus he will by and by convince 
himself that the war is just, and will thank God for the better sleep 
he enjoys after this process of grotesque self-deception." -- Mark Twain

Re: [Ext2-devel] Re: [PATCH] use-before-uninitialized value in ext3(2)_find_ goal

[Chris Wright]

* Matthew Wilcox (willy@debian.org) wrote:
> On Wed, May 19, 2004 at 12:53:28PM -0700, Chris Wright wrote:
> > I know it's a slightly bigger patch, but would it make sense to just enforce
> > this as part of api?  Just a thought...(patch untested)
> 
> No, that doesn't work.  Look:
> 
> reread:
> 	...
> 
>         if (ext2_find_goal(inode, iblock, chain, partial, &goal) < 0)
>                 goto changed;
> 
> changed:
>         while (partial > chain) {
>                 brelse(partial->bh);
>                 partial--;
>         }
>         goto reread;
> 
> So it's spaghetti code that can modify goal.  Yuck.
> 
> 5 labels in one function?  3 backwards jumps?  Disgusting.

Heh, yeah.  I actually did look, and had the same concern about goal.
I think it's ok though.  For one thing, in that changed->reread loop
goal is never used.  Secondly, I think that the intention was to have
*_find_goal start from 0, not from last goal, since goal is marked as
output, and Mingming's patch reset goal to 0 every pass through.  This
is exactly why I thought it useful to clarify the api.

thanks,
-chris
-- 
Linux Security Modules     http://lsm.immunix.org     http://lsm.bkbits.net