ext3, ext4: do_split() fix loop, with obvious unsigned wrap
PATCH v2 1/1 ext3, ext4: do_split() fix loop, with obvious unsigned wrap
Fix loop, with obvious unsigned wrap
---
fs/ext3/namei.c +1 -1
@@ -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 ;
fs/ext4/namei.c +1 -1
@@ -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 ;
Theodore Tso
maintainerQuoted 3 lines · roel kluin
Fix loop, with obvious unsigned wrap
Signed-off-by Roel Kluin <[email protected]>
Um, no. Sorry, I didn't have a chance to reply earlier but this is obviously wrong.
Quoted 6 lines
---
fs/ext3/namei.c +0
-0
fs/ext3/namei.c static struct ext3_dir_entry_2 *do_split(handle_t *handle, struct inode *dir, · line 1194
Quoted 8 lines
fs/ext3/namei.c +1
-1@@ -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
Quoted 11 lines · Theodore Tso
Quoted 4 lines · roel kluin
Fix loop, with obvious unsigned wrap
Signed-off-by Roel Kluin <[email protected]>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).
Quoted 12 lines
Quoted 12 lines
---
fs/ext3/namei.c +1
-1@@ -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? */
Quoted 10 lines
fs/ext3/namei.c static struct ext3_dir_entry_2 *do_split(handle_t *handle, struct inode *dir, · line 1194
Quoted 3 lines
fs/ext3/namei.c +0
-0if (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.
Quoted 9 lines
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
Signature · 3 lines
Bill Davidsen <[email protected]> "Woe unto the statesman who makes war without a reason that will still be valid when the war is over..." Otto von Bismark
Quoted 2 lines · Bill Davidsen
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;
}Quoted 4 lines
Quoted 3 lines · Theodore Tso
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
---
fs/ext3/namei.c +2 -1
@@ -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 ;
fs/ext4/namei.c +2 -1
@@ -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 ;
Theodore Tso
maintainerQuoted 7 lines · Bill Davidsen
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:
Quoted 1 line
Quoted 1 line
Review
Quoted 1 line
(quoted diff) +1
-0+ 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
Quoted 8 lines · Theodore Tso
Quoted 2 lines · Bill Davidsen
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:
Quoted 7 lines
Quoted 2 lines
Quoted 2 lines
Review
Quoted 2 lines
(quoted diff) +1
-0+ 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...
Signature · 3 lines
Bill Davidsen <[email protected]> "Woe unto the statesman who makes war without a reason that will still be valid when the war is over..." Otto von Bismark
Quoted 3 lines · Bill Davidsen
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.
Signature · 3 lines
Bill Davidsen <[email protected]> "Woe unto the statesman who makes war without a reason that will still be valid when the war is over..." Otto von Bismark
Quoted 2 lines · On Mon, 01 Dec 2008 14:28:25 -0500 roel kluin <[email protected]> wrote:
Fix loop, with obvious unsigned wrap
Please raise separate patches for ext3 and ext4 - their paths into the tree are different.
fs/ext3/namei.c static struct ext3_dir_entry_2 *do_split(handle_t *handle, struct inode *dir, · line 1191
Quoted 8 lines
fs/ext3/namei.c +1
-1@@ -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.
Quoted 16 lines
fs/ext3/namei.c +0
-0/* is more than half of this entry in 2nd half of the block? */ if (size + map[i].size/2 > blocksize/2 )break ;fs/ext4/namei.c +1
-1@@ -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 ;
Quoted 11 lines · Andrew Morton
Quoted 3 lines · On Mon, 01 Dec 2008 14:28:25 -0500 roel kluin <[email protected]> wrote:
Fix loop, with obvious unsigned wrap
Please raise separate patches for ext3 and ext4 - their paths into the tree are different.
Quoted 15 lines
fs/ext3/namei.c static struct ext3_dir_entry_2 *do_split(handle_t *handle, struct inode *dir, · line 1192
Quoted 9 lines
fs/ext3/namei.c +1
-1@@ -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.
Signature · 3 lines
Bill Davidsen <[email protected]> "Woe unto the statesman who makes war without a reason that will still be valid when the war is over..." Otto von Bismark