Bug 12597

Summary: Kernel should be built with -fwrapv
Product: Other Reporter: Török Edwin (edwin+bugs)
Component: ConfigurationAssignee: other_configuration (other_configuration)
Status: CLOSED CODE_FIX    
Severity: normal    
Priority: P1    
Hardware: All   
OS: Linux   
Kernel Version: 2.6.28.2 Subsystem:
Regression: --- Bisected commit-id:

Description Török Edwin 2009-02-01 11:10:32 UTC
Pointer arithmetic overflow is undefined (and gcc may assume that it never happens), same for signed arithmetic overflow.
Building the kernel with -Wstrict-overflow=3 shows new 287 warnings, a quick look at one of the warnings shows that this is a real concern as gcc does compile code as if the wrap would never happen.

Here is one that looks real:
fs/open.c: In function ‘sys_fallocate’:
fs/open.c:419: warning: assuming signed overflow does not occur when simplifying conditional to constant

fs/open.c:
 418 /* Check for wrap through zero too */
 419        if (((offset + len) > inode->i_sb->s_maxbytes) || ((offset + len) < 0))
 420                goto out_fput;

offset and len are both signed types, so gcc assumes that signed arithmetic overflow doesn't occur.

To fix this the kernel should be built with -fwrapv, which means that signed (and pointer) arithmetic overflow is defined: it wraps. (see the gcc manpage on -fwrapv and -fno-strict-overflow for more details).

Here is what gcc produces by default:
/* Check for wrap through zero too */
        if (((offset + len) > inode->i_sb->s_maxbytes) || ((offset + len) < 0))
    1053:       4b 8d 04 26             lea    (%r14,%r12,1),%rax
    1057:       48 8b 97 f8 00 00 00    mov    0xf8(%rdi),%rdx
    105e:       48 3b 42 28             cmp    0x28(%rdx),%rax
    1062:       77 2f                   ja     1093 <sys_fallocate+0x107>
    1064:       48 85 c0                test   %rax,%rax
    1067:       78 2a                   js     1093 <sys_fallocate+0x107>


Here is what gcc produces with -fwrapv:
/* Check for wrap through zero too */
        if (((offset + len) > inode->i_sb->s_maxbytes) || ((offset + len) < 0))
    1325:       48 8d 04 11             lea    (%rcx,%rdx,1),%rax
    1329:       48 8b b7 f8 00 00 00    mov    0xf8(%rdi),%rsi
    1330:       48 3b 46 28             cmp    0x28(%rsi),%rax
    1334:       77 2d                   ja     1363 <sys_fallocate+0x133>
    1336:       48 85 c0                test   %rax,%rax

Obviosuly the (offset+len) < 0 check was deleted, on the assumption that if it happens it is undefined behaviour -> it never happens.
Comment 1 Török Edwin 2009-02-01 11:25:28 UTC
This is with both gcc version 4.3.3 (Debian 4.3.3-3), and gcc version 4.4.0 20090131 (experimental) [trunk revision 143833] (GCC)

Perhaps -fno-strict-overflow should be used too:
-fstrict-overflow's manpage:
This permits the compiler to conclude that "p + u > p"is always true for a pointer "p" and unsigned integer "u".  This assumption is only validbecause pointer wraparound is undefined, as the expression is false if "p + u" overflows
using twos complement arithmetic

The -fstrict-overflow option is enabled at levels -O2, -O3, -Os
Comment 2 Anonymous Emailer 2009-02-01 12:46:38 UTC
Reply-To: akpm@linux-foundation.org


(switched to email.  Please respond via emailed reply-to-all, not via the
bugzilla web interface).

On Sun,  1 Feb 2009 11:10:32 -0800 (PST) bugme-daemon@bugzilla.kernel.org wrote:

> http://bugzilla.kernel.org/show_bug.cgi?id=12597
> 
>            Summary: Kernel should be built with -fwrapv

Your thoughts?

>            Product: Other
>            Version: 2.5
>      KernelVersion: 2.6.28.2
>           Platform: All
>         OS/Version: Linux
>               Tree: Mainline
>             Status: NEW
>           Severity: normal
>           Priority: P1
>          Component: Configuration
>         AssignedTo: other_configuration@kernel-bugs.osdl.org
>         ReportedBy: edwintorok@gmail.com
> 
> 
> Pointer arithmetic overflow is undefined (and gcc may assume that it never
> happens), same for signed arithmetic overflow.
> Building the kernel with -Wstrict-overflow=3 shows new 287 warnings, a quick
> look at one of the warnings shows that this is a real concern as gcc does
> compile code as if the wrap would never happen.
> 
> Here is one that looks real:
> fs/open.c: In function ___sys_fallocate___:
> fs/open.c:419: warning: assuming signed overflow does not occur when
> simplifying conditional to constant
> 
> fs/open.c:
>  418 /* Check for wrap through zero too */
>  419        if (((offset + len) > inode->i_sb->s_maxbytes) || ((offset + len)
>  <
> 0))
>  420                goto out_fput;
> 
> offset and len are both signed types, so gcc assumes that signed arithmetic
> overflow doesn't occur.
> 
> To fix this the kernel should be built with -fwrapv, which means that signed
> (and pointer) arithmetic overflow is defined: it wraps. (see the gcc manpage
> on
> -fwrapv and -fno-strict-overflow for more details).
> 
> Here is what gcc produces by default:
> /* Check for wrap through zero too */
>         if (((offset + len) > inode->i_sb->s_maxbytes) || ((offset + len) <
>         0))
>     1053:       4b 8d 04 26             lea    (%r14,%r12,1),%rax
>     1057:       48 8b 97 f8 00 00 00    mov    0xf8(%rdi),%rdx
>     105e:       48 3b 42 28             cmp    0x28(%rdx),%rax
>     1062:       77 2f                   ja     1093 <sys_fallocate+0x107>
>     1064:       48 85 c0                test   %rax,%rax
>     1067:       78 2a                   js     1093 <sys_fallocate+0x107>
> 
> 
> Here is what gcc produces with -fwrapv:
> /* Check for wrap through zero too */
>         if (((offset + len) > inode->i_sb->s_maxbytes) || ((offset + len) <
>         0))
>     1325:       48 8d 04 11             lea    (%rcx,%rdx,1),%rax
>     1329:       48 8b b7 f8 00 00 00    mov    0xf8(%rdi),%rsi
>     1330:       48 3b 46 28             cmp    0x28(%rsi),%rax
>     1334:       77 2d                   ja     1363 <sys_fallocate+0x133>
>     1336:       48 85 c0                test   %rax,%rax
> 
> Obviosuly the (offset+len) < 0 check was deleted, on the assumption that if
> it
> happens it is undefined behaviour -> it never happens.
Comment 3 Török Edwin 2009-02-01 12:52:53 UTC
On 2009-02-01 22:46, Andrew Morton wrote:
> (switched to email.  Please respond via emailed reply-to-all, not via the
> bugzilla web interface).
>
> On Sun,  1 Feb 2009 11:10:32 -0800 (PST) bugme-daemon@bugzilla.kernel.org
> wrote:
>
>   
>> http://bugzilla.kernel.org/show_bug.cgi?id=12597
>>
>>            Summary: Kernel should be built with -fwrapv
>>     
>
> Your thoughts?
>
>   
>>            Product: Other
>>            Version: 2.5
>>      KernelVersion: 2.6.28.2
>>           Platform: All
>>         OS/Version: Linux
>>               Tree: Mainline
>>             Status: NEW
>>           Severity: normal
>>           Priority: P1
>>          Component: Configuration
>>         AssignedTo: other_configuration@kernel-bugs.osdl.org
>>         ReportedBy: edwintorok@gmail.com
>>
>>
>> Pointer arithmetic overflow is undefined (and gcc may assume that it never
>> happens), same for signed arithmetic overflow.
>> Building the kernel with -Wstrict-overflow=3 shows new 287 warnings, a quick
>> look at one of the warnings shows that this is a real concern as gcc does
>> compile code as if the wrap would never happen.
>>
>> Here is one that looks real:
>> fs/open.c: In function ___sys_fallocate___:
>> fs/open.c:419: warning: assuming signed overflow does not occur when
>> simplifying conditional to constant
>>
>> fs/open.c:
>>  418 /* Check for wrap through zero too */
>>  419        if (((offset + len) > inode->i_sb->s_maxbytes) || ((offset +
>>  len) <
>> 0))
>>  420                goto out_fput;
>>
>> offset and len are both signed types, so gcc assumes that signed arithmetic
>> overflow doesn't occur.
>>
>> To fix this the kernel should be built with -fwrapv, which means that signed
>> (and pointer) arithmetic overflow is defined: it wraps. (see the gcc manpage
>> on
>> -fwrapv and -fno-strict-overflow for more details).
>>
>> Here is what gcc produces by default:
>>     

Sorry, it looks like I made a copy+paste error (stale clipboard), and
pasted only the -fwrapv case.
Here is what gcc-4.3 generates by default:

      ret = -EFBIG;
        /* Check for wrap through zero too */
        if (((offset + len) > inode->i_sb->s_maxbytes) || ((offset +
len) < 0))
    1320:       4b 8d 54 25 00          lea    0x0(%r13,%r12,1),%rdx
    1325:       48 8b 87 f8 00 00 00    mov    0xf8(%rdi),%rax
    132c:       48 c7 c3 e5 ff ff ff    mov    $0xffffffffffffffe5,%rbx
    1333:       48 3b 50 28             cmp    0x28(%rax),%rdx
    1337:       0f 87 5c ff ff ff       ja     1299 <sys_fallocate+0x69>
                goto out_fput;

>> /* Check for wrap through zero too */
>>         if (((offset + len) > inode->i_sb->s_maxbytes) || ((offset + len) <
>>         0))
>>     1053:       4b 8d 04 26             lea    (%r14,%r12,1),%rax
>>     1057:       48 8b 97 f8 00 00 00    mov    0xf8(%rdi),%rdx
>>     105e:       48 3b 42 28             cmp    0x28(%rdx),%rax
>>     1062:       77 2f                   ja     1093 <sys_fallocate+0x107>
>>     1064:       48 85 c0                test   %rax,%rax
>>     1067:       78 2a                   js     1093 <sys_fallocate+0x107>
>>     

^And this is what it generates with -fwrapv

>>
>> Here is what gcc produces with -fwrapv:
>> /* Check for wrap through zero too */
>>         if (((offset + len) > inode->i_sb->s_maxbytes) || ((offset + len) <
>>         0))
>>     1325:       48 8d 04 11             lea    (%rcx,%rdx,1),%rax
>>     1329:       48 8b b7 f8 00 00 00    mov    0xf8(%rdi),%rsi
>>     1330:       48 3b 46 28             cmp    0x28(%rsi),%rax
>>     1334:       77 2d                   ja     1363 <sys_fallocate+0x133>
>>     1336:       48 85 c0                test   %rax,%rax
>>     

And this is ^gcc-4.4.0 default.

>> Obviosuly the (offset+len) < 0 check was deleted, on the assumption that if
>> it
>> happens it is undefined behaviour -> it never happens.
>>     
>
>   


Best regards,
--Edwin
Comment 4 Linus Torvalds 2009-02-01 14:10:23 UTC

On Sun, 1 Feb 2009, Andrew Morton wrote:

> 
> (switched to email.  Please respond via emailed reply-to-all, not via the
> bugzilla web interface).
> 
> On Sun,  1 Feb 2009 11:10:32 -0800 (PST) bugme-daemon@bugzilla.kernel.org
> wrote:
> 
> > http://bugzilla.kernel.org/show_bug.cgi?id=12597
> > 
> >            Summary: Kernel should be built with -fwrapv
> 
> Your thoughts?

Yeah, we probably should. 

Many parts of the kernel do the whole "unsigned wrap" thing, which is 
well-defined, but I'd expect us to do pointers quite often, and sometimes 
even perhaps depend on signed wrap.

		Linus
Comment 5 Anonymous Emailer 2009-02-01 14:45:43 UTC
Reply-To: viro@ZenIV.linux.org.uk

On Sun, Feb 01, 2009 at 02:10:14PM -0800, Linus Torvalds wrote:
> 
> 
> On Sun, 1 Feb 2009, Andrew Morton wrote:
> 
> > 
> > (switched to email.  Please respond via emailed reply-to-all, not via the
> > bugzilla web interface).
> > 
> > On Sun,  1 Feb 2009 11:10:32 -0800 (PST) bugme-daemon@bugzilla.kernel.org
> wrote:
> > 
> > > http://bugzilla.kernel.org/show_bug.cgi?id=12597
> > > 
> > >            Summary: Kernel should be built with -fwrapv
> > 
> > Your thoughts?
> 
> Yeah, we probably should. 
> 
> Many parts of the kernel do the whole "unsigned wrap" thing, which is 
> well-defined, but I'd expect us to do pointers quite often, and sometimes 
> even perhaps depend on signed wrap.

	For now - yes, but in the long run we really ought to get rid of
that...  FWIW, I'd expect the frequencies to be the other way round - signed
wrap *more* often that pointers.
Comment 6 Anonymous Emailer 2009-02-02 03:27:06 UTC
Reply-To: andi@firstfloor.org

> > 
> > > http://bugzilla.kernel.org/show_bug.cgi?id=12597
> > > 
> > >            Summary: Kernel should be built with -fwrapv
> > 
> > Your thoughts?
> 
> Yeah, we probably should. 

Agreed. Specifying that would be safer right now.

-Andi