Patchwork [v2] ext3, ext4: do_split() fix loop, with obvious unsigned wrap

login
register
mail settings
Submitter roel kluin
Date Dec. 1, 2008, 7:28 p.m.
Message ID <49343AD9.4020606@gmail.com>
Download mbox | patch
Permalink /patch/11643/
State New
Headers show

Comments

roel kluin - Dec. 1, 2008, 7:28 p.m.
Fix loop, with obvious unsigned wrap

Signed-off-by: Roel Kluin <roel.kluin@gmail.com>
---
--
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 - Dec. 2, 2008, 1:24 p.m.
On Mon, Dec 01, 2008 at 02:28:25PM -0500, roel kluin wrote:
> Fix loop, with obvious unsigned wrap
> 
> Signed-off-by: Roel Kluin <roel.kluin@gmail.com>

Um, no.  Sorry, I didn't have a chance to reply earlier but this is
obviously wrong.

> ---
> diff --git a/fs/ext3/namei.c b/fs/ext3/namei.c
> index 3e5edc9..b0dcfb3 100644
> --- a/fs/ext3/namei.c
> +++ b/fs/ext3/namei.c
> @@ -1188,7 +1188,7 @@ static struct ext3_dir_entry_2 *do_split(handle_t *handle, struct inode *dir,
>  	/* Split the existing block in the middle, size-wise */
>  	size = 0;
>  	move = 0;
> -	for (i = count-1; i >= 0; i--) {
> +	for (i = count; i--; ) {
>  		/* is more than half of this entry in 2nd half of the block? */
>  		if (size + map[i].size/2 > blocksize/2)
>  			break;

Note that i is actually **used** in the loop?  So changing the
starting value of the counter without also adjusting all of the places
where i is used will cause the code to break, and in hard to find
ways...

Given that there are two loop termination conditions, and in fact the
one in the loop is the one that actually gets used 99% of the time
(which is why we've never noticed the problem in real life), probably
the best way of handling this is to recast it not as a for loop, but
as a while loop.

						- Ted
--
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
Bill Davidsen - Dec. 2, 2008, 5:08 p.m.
Theodore Tso wrote:
> On Mon, Dec 01, 2008 at 02:28:25PM -0500, roel kluin wrote:
>   
>> Fix loop, with obvious unsigned wrap
>>
>> Signed-off-by: Roel Kluin <roel.kluin@gmail.com>
>>     
>
> Um, no.  Sorry, I didn't have a chance to reply earlier but this is
> obviously wrong.
>
>   
Sorry, you are reading it wrong, the i values inside the loop are 
identical to those in the original. The value of i starts at count, and 
the test comes *before* the value is used inside the loop. The values of 
i inside the loop start at count-1 and go to zero, just as it did in the 
original. That's why the "i--" is there, the test is on the 
unincremented value range count to one, but the value inside the loop is 
correct (or at least is the same as the original patch).
>> ---
>> diff --git a/fs/ext3/namei.c b/fs/ext3/namei.c
>> index 3e5edc9..b0dcfb3 100644
>> --- a/fs/ext3/namei.c
>> +++ b/fs/ext3/namei.c
>> @@ -1188,7 +1188,7 @@ static struct ext3_dir_entry_2 *do_split(handle_t *handle, struct inode *dir,
>>  	/* Split the existing block in the middle, size-wise */
>>  	size = 0;
>>  	move = 0;
>> -	for (i = count-1; i >= 0; i--) {
>> +	for (i = count; i--; ) {
>>  		/* is more than half of this entry in 2nd half of the block? */
>>  		if (size + map[i].size/2 > blocksize/2)
>>  			break;
>>     
>
> Note that i is actually **used** in the loop?  So changing the
> starting value of the counter without also adjusting all of the places
> where i is used will cause the code to break, and in hard to find
> ways...
>
>   
As I said, the values used are identical, and the code works correctly.
> Given that there are two loop termination conditions, and in fact the
> one in the loop is the one that actually gets used 99% of the time
> (which is why we've never noticed the problem in real life), probably
> the best way of handling this is to recast it not as a for loop, but
> as a while loop.
>
> 						- Ted
>
>
Theodore Ts'o - Dec. 2, 2008, 9:57 p.m.
On Tue, Dec 02, 2008 at 12:08:38PM -0500, Bill Davidsen wrote:
> Sorry, you are reading it wrong, the i values inside the loop are  
> identical to those in the original. The value of i starts at count, and  
> the test comes *before* the value is used inside the loop. The values of  
> i inside the loop start at count-1 and go to zero, just as it did in the  
> original. That's why the "i--" is there, the test is on the  
> unincremented value range count to one, but the value inside the loop is  
> correct (or at least is the same as the original patch).

You're right; my bad.  But with something like this:

>>> +	for (i = count; i--; ) {

...where there is no third part of the for loop, and a decrement in
the second part of the loop, just for clarity's sake, it's much better
to write it as a while loop.

						- Ted
--
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
Bill Davidsen - Dec. 2, 2008, 11:17 p.m.
Theodore Tso wrote:
> On Tue, Dec 02, 2008 at 12:08:38PM -0500, Bill Davidsen wrote:
>   
>> Sorry, you are reading it wrong, the i values inside the loop are  
>> identical to those in the original. The value of i starts at count, and  
>> the test comes *before* the value is used inside the loop. The values of  
>> i inside the loop start at count-1 and go to zero, just as it did in the  
>> original. That's why the "i--" is there, the test is on the  
>> unincremented value range count to one, but the value inside the loop is  
>> correct (or at least is the same as the original patch).
>>     
>
> You're right; my bad.  But with something like this:
>
>   
>>>> +	for (i = count; i--; ) {
>>>>         
>
> ...where there is no third part of the for loop, and a decrement in
> the second part of the loop, just for clarity's sake, it's much better
> to write it as a while loop.
>   

I seriously disagree on that, writing it as a for makes it totally clear 
that the index initialization is part of the loop.
I know, looks funny, not the way we have always done it, not invented 
here...
Andrew Morton - Dec. 3, 2008, 6:05 a.m.
On Mon, 01 Dec 2008 14:28:25 -0500 roel kluin <roel.kluin@gmail.com> wrote:

> Fix loop, with obvious unsigned wrap
> 

Please raise separate patches for ext3 and ext4 - their paths into the
tree are different.

> --- a/fs/ext3/namei.c
> +++ b/fs/ext3/namei.c
> @@ -1188,7 +1188,7 @@ static struct ext3_dir_entry_2 *do_split(handle_t *handle, struct inode *dir,
>  	/* Split the existing block in the middle, size-wise */
>  	size = 0;
>  	move = 0;
> -	for (i = count-1; i >= 0; i--) {
> +	for (i = count; i--; ) {

So we're replacing an accidental for(;;) with something which can
really terminate.  This is potentially a functional change, and it's
perhaps telling us that we should replace it with a real for (;;) loop
anyway.

Plus we still have a local unsigned variable called "i".

Ted, could you please take a look at this sometime, work out the best
course of action?

Thanks.

>  		/* is more than half of this entry in 2nd half of the block? */
>  		if (size + map[i].size/2 > blocksize/2)
>  			break;
> diff --git a/fs/ext4/namei.c b/fs/ext4/namei.c
> index 63adcb7..34232c6 100644
> --- a/fs/ext4/namei.c
> +++ b/fs/ext4/namei.c
> @@ -1198,7 +1198,7 @@ static struct ext4_dir_entry_2 *do_split(handle_t *handle, struct inode *dir,
>  	/* Split the existing block in the middle, size-wise */
>  	size = 0;
>  	move = 0;
> -	for (i = count-1; i >= 0; i--) {
> +	for (i = count; i--; ) {
>  		/* is more than half of this entry in 2nd half of the block? */
>  		if (size + map[i].size/2 > blocksize/2)
>  			break;

--
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
Bill Davidsen - Dec. 3, 2008, 2:25 p.m.
Bill Davidsen wrote:
> I seriously disagree on that, writing it as a for makes it totally 
> clear that the index initialization is part of the loop.
> I know, looks funny, not the way we have always done it, not invented 
> here...
>
Just to be clear, I didn't mean that in any bad way, just that sometimes 
a new format, even if correct and unambiguous, looks strange to the eye 
and is not used just because it jars. I still think putting 
initialization for a loop in the start of the for is defensive 
programming, perhaps I've had too many bumblers inherit my code.
Bill Davidsen - Dec. 3, 2008, 2:32 p.m.
Andrew Morton wrote:
> On Mon, 01 Dec 2008 14:28:25 -0500 roel kluin <roel.kluin@gmail.com> wrote:
>
>   
>> Fix loop, with obvious unsigned wrap
>>
>>     
>
> Please raise separate patches for ext3 and ext4 - their paths into the
> tree are different.
>
>   
>> --- a/fs/ext3/namei.c
>> +++ b/fs/ext3/namei.c
>> @@ -1188,7 +1188,7 @@ static struct ext3_dir_entry_2 *do_split(handle_t *handle, struct inode *dir,
>>  	/* Split the existing block in the middle, size-wise */
>>  	size = 0;
>>  	move = 0;
>> -	for (i = count-1; i >= 0; i--) {
>> +	for (i = count; i--; ) {
>>     
>
> So we're replacing an accidental for(;;) with something which can
> really terminate.  This is potentially a functional change, and it's
> perhaps telling us that we should replace it with a real for (;;) loop
> anyway.
>   
It's not a "for (;;)" loop, because the index value does change, but 
clearly in the current implementation the termination condition won't be 
met by any index value. You still need to bail on index value, and the 
index is used in the loop.

Patch

diff --git a/fs/ext3/namei.c b/fs/ext3/namei.c
index 3e5edc9..b0dcfb3 100644
--- a/fs/ext3/namei.c
+++ b/fs/ext3/namei.c
@@ -1188,7 +1188,7 @@  static struct ext3_dir_entry_2 *do_split(handle_t *handle, struct inode *dir,
 	/* Split the existing block in the middle, size-wise */
 	size = 0;
 	move = 0;
-	for (i = count-1; i >= 0; i--) {
+	for (i = count; i--; ) {
 		/* is more than half of this entry in 2nd half of the block? */
 		if (size + map[i].size/2 > blocksize/2)
 			break;
diff --git a/fs/ext4/namei.c b/fs/ext4/namei.c
index 63adcb7..34232c6 100644
--- a/fs/ext4/namei.c
+++ b/fs/ext4/namei.c
@@ -1198,7 +1198,7 @@  static struct ext4_dir_entry_2 *do_split(handle_t *handle, struct inode *dir,
 	/* Split the existing block in the middle, size-wise */
 	size = 0;
 	move = 0;
-	for (i = count-1; i >= 0; i--) {
+	for (i = count; i--; ) {
 		/* is more than half of this entry in 2nd half of the block? */
 		if (size + map[i].size/2 > blocksize/2)
 			break;