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

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

[roel kluin]

Fix loop, with obvious unsigned wrap

Signed-off-by: Roel Kluin <roel.kluin@gmail.com>
---
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;

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

[Theodore Tso]

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

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

[Bill Davidsen]

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


-- 
Bill Davidsen <davidsen@tmr.com>
  "Woe unto the statesman who makes war without a reason that will still
  be valid when the war is over..." Otto von Bismark 

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

[Roel Kluin]

Bill Davidsen wrote:

> the value inside the loop is
> correct (or at least is the same as the original patch).

I agree, this can be shown with:

#include <stdio.h>

int main()
{
	unsigned int i, count = 10;

	printf ("The original loop:\n");
        for (i = count-1; i >= 0; i--) {
		printf ("%u, ", i);
		if (i == -1) {
			printf ("which is wrong.\n");
			break;
		}
	}

        printf ("As suggested by Bill:\n");
	for (i = count; i--; )
		printf ("%u, ", i);
	printf ("...After the loop i=%u\n");

	printf ("Your suggestion:\n");
	i = count;
	while (i--)
		printf ("%u, ", i);
	printf ("...After the loop i=%u\n");

	return 0;
}
> Theodore Tso wrote:
>> probably
>> the best way of handling this is to recast it not as a for loop, but
>> as a while loop.

Ok, with me. As also shown this will give the same results:
-----------8<--------------->8-------------
Fix loop, with obvious unsigned wrap

Signed-off-by: Roel Kluin <roel.kluin@gmail.com> 
---
diff --git a/fs/ext3/namei.c b/fs/ext3/namei.c
index 3e5edc9..0e574d4 100644
--- a/fs/ext3/namei.c
+++ b/fs/ext3/namei.c
@@ -1188,7 +1188,8 @@ 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--) {
+	i = count;
+	while (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..b8903d4 100644
--- a/fs/ext4/namei.c
+++ b/fs/ext4/namei.c
@@ -1198,7 +1198,8 @@ 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--) {
+	i = count;
+	while (i--) {
 		/* is more than half of this entry in 2nd half of the block? */
 		if (size + map[i].size/2 > blocksize/2)
 			break;

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

[Theodore Tso]

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

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

[Bill Davidsen]

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

-- 
Bill Davidsen <davidsen@tmr.com>
  "Woe unto the statesman who makes war without a reason that will still
  be valid when the war is over..." Otto von Bismark 

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

[Bill Davidsen]

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 <davidsen@tmr.com>
  "Woe unto the statesman who makes war without a reason that will still
  be valid when the war is over..." Otto von Bismark 

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

[Andrew Morton]

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;

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

[Bill Davidsen]

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.

-- 
Bill Davidsen <davidsen@tmr.com>
  "Woe unto the statesman who makes war without a reason that will still
  be valid when the war is over..." Otto von Bismark