[Bug c/27214] New: The C frontend introduces undefined pointer overflow

[Bug c/27214] New: The C frontend introduces undefined pointer overflow

[rguenth at gcc dot gnu dot org]

The C frontend creates pointer arithmetic that assumes that pointer
overflow is defined (and wraps).

char *foo(char *p)
{
  return p + -4;
}

results in

foo (p)
{
  char * D.1523;

  D.1523 = p + -4B;
  return D.1523;
}

this is via c-common.c:pointer_int_sum().

 <plus_expr 0xb7da4144
    type <pointer_type 0xb7db405c
        type <integer_type 0xb7dac170 char public string-flag QI
            size <integer_cst 0xb7d9d1f8 constant invariant 8>
            unit size <integer_cst 0xb7d9d210 constant invariant 1>
            align 8 symtab 0 alias set -1 precision 8 min <integer_cst
0xb7d9d258 -128> max <integer_cst 0xb7d9d2b8 127>
            pointer_to_this <pointer_type 0xb7db405c>>
        unsigned SI
        size <integer_cst 0xb7d9d3f0 constant invariant 32>
        unit size <integer_cst 0xb7d9d180 constant invariant 4>
        align 32 symtab 0 alias set -1>

    arg 0 <parm_decl 0xb7da5140 p type <pointer_type 0xb7db405c>
        used unsigned SI file t.c line 1 size <integer_cst 0xb7d9d3f0 32> unit
size <integer_cst 0xb7d9d180 4>
        align 32 context <function_decl 0xb7e2d980 foo> initial <pointer_type
0xb7db405c> arg-type <pointer_type 0xb7db405c>>
    arg 1 <integer_cst 0xb7e35eb8 type <pointer_type 0xb7db405c> constant
invariant 4294967292>>


-- 
           Summary: The C frontend introduces undefined pointer overflow
           Product: gcc
           Version: 4.2.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: rguenth at gcc dot gnu dot org
OtherBugsDependingO 27039
             nThis:


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=27214

[Bug c/27214] The C frontend introduces undefined pointer overflow

[pinskia at gcc dot gnu dot org]

------- Comment #1 from pinskia at gcc dot gnu dot org  2006-04-19 15:06 -------
There is no wrapping here or undefinedness here as far as I can see

You just have to learn that a + "-CST" is the same as a - CST.


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
         Resolution|                            |INVALID


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=27214

[Bug c/27214] The C frontend introduces undefined pointer overflow

[rguenth at gcc dot gnu dot org]

------- Comment #2 from rguenth at gcc dot gnu dot org  2006-04-19 15:13 -------
"-CST" in this case is unsigned 4294967292, it just happens to be printed as
-4B.
So the addition wraps, as it is done using unsigned arithmetic.  Writing

char *foo(char *p)
{
  return p + 4294967292;
}

results in the same

  D.1523 = p + -4B;

but the above source would be invalid due to the wrapping pointer.  Now the
middle-end in some places assumes/assumed that pointers do not wrap.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |UNCONFIRMED
         Resolution|INVALID                     |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=27214

[Bug c/27214] The C frontend introduces undefined pointer overflow

[pinskia at gcc dot gnu dot org]

------- Comment #3 from pinskia at gcc dot gnu dot org  2006-04-19 15:22 -------
Both are those are the same.  Maybe we should just get a POINTER_PLUS_EXPR but
that is really not an issue here.


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
         Resolution|                            |INVALID


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=27214

[Bug c/27214] The C frontend introduces undefined pointer overflow

[rguenth at gcc dot gnu dot org]

------- Comment #4 from rguenth at gcc dot gnu dot org  2006-04-19 15:31 -------
How's that "the same"?  Either you say that pointers follow unsigned integer
types in overflow behavior (quote me the standard for that) or explain why

     p + -4  is treated as  p + (char *)-4

but  p -  4  is treated as  p - (char *)4

which are different in overflow behavior as (char *) is "unsigned" as far as
the middle-end concerns.

I see 6.5.6/8 where it says

If both the pointer operand and the result point to elements of the same array
object, or one past the last element of the array object, the evaluation shall
not produce an overflow; otherwise, the behavior is undefined.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |UNCONFIRMED
         Resolution|INVALID                     |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=27214

[Bug c/27214] The C frontend introduces undefined pointer overflow

[pinskia at gcc dot gnu dot org]

------- Comment #5 from pinskia at gcc dot gnu dot org  2006-04-19 15:34 -------
Then p + -4 is overflowed already -4 is no different than the unsigned version.


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
         Resolution|                            |INVALID


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=27214

[Bug c/27214] The C frontend introduces undefined pointer overflow

[rakdver at gcc dot gnu dot org]

------- Comment #6 from rakdver at gcc dot gnu dot org  2006-04-19 16:32 -------
I do not think this PR is invalid:

int a[100];
int *p = &a[50];

p - 1 is well defined, and points to 50 - 1 th element of a, as standard
specifies
p + (-1) is also well defined, and points to 50 + (-1) th element, again
according to standard.
p + (unsigned) -1 is undefined, as there is no 50 + 4294967295 th element in a
(the standard specifies that there cannot be any overflow in the computation).

Andrew, please do not mark PRs as invalid until the people involved in the
discussion do not agree on the common interpretation of the standard.


-- 

rakdver at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |UNCONFIRMED
         Resolution|INVALID                     |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=27214

[Bug c/27214] The C frontend introduces undefined pointer overflow

[joseph at codesourcery dot com]

------- Comment #7 from joseph at codesourcery dot com  2006-04-19 17:15 -------
Subject: Re:  The C frontend introduces undefined pointer overflow

On Wed, 19 Apr 2006, rakdver at gcc dot gnu dot org wrote:

> Andrew, please do not mark PRs as invalid until the people involved in the
> discussion do not agree on the common interpretation of the standard.

This bug is about the interpretation of GCC's internal representation, not 
that of the standard.

Valid pointer offsets range from -SIZE_MAX to +SIZE_MAX - thus they 
require one bit more than pointers to store.  An internal representation 
not allowing for this range of offsets is problematic.

(As for the C language issues, subtraction of two pointers involves 
undefined behavior if the result is outside the range PTRDIFF_MIN to 
PTRDIFF_MAX, but you can still have an array using more than half of 
memory as long as you don't subtract pointers to elements too far apart.  
You could also have an array using almost all of memory, and subtract 
elements at opposite ends, as long as the element size is not 1; only the 
final result needs to be in range.  Such subtraction of pointers more 
than half of memory apart is not however an important case, and probably 
not one it's feasible to get right efficiently.)


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=27214

[Bug c/27214] The C frontend introduces undefined pointer overflow

[pinskia at gcc dot gnu dot org]

------- Comment #8 from pinskia at gcc dot gnu dot org  2006-05-05 09:22 -------
Maybe it is time to add POINTER_PLUS_EXPR which should solve the problem (well
95% of the way as what is the type of the 2nd operand, a signed or unsigned
type).


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=27214

[Bug c/27214] The C frontend introduces undefined pointer overflow

[pinskia at gcc dot gnu dot org]

------- Comment #9 from pinskia at gcc dot gnu dot org  2007-12-11 00:45 -------
I think this has been fixed by the pointer plus branch merge for 4.3.0.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=27214

[Bug c/27214] The C frontend introduces undefined pointer overflow

[rguenth at gcc dot gnu dot org]

------- Comment #10 from rguenth at gcc dot gnu dot org  2008-01-03 15:54 -------
"Fixed" only in the sense that we now create

 <pointer_plus_expr 0x2b6e7ed3b1c0
    type <pointer_type 0x2b6e7eda3000
        type <integer_type 0x2b6e7ed8c300 char public string-flag QI
            size <integer_cst 0x2b6e7ed7c7e0 constant invariant 8>
            unit size <integer_cst 0x2b6e7ed7c810 constant invariant 1>
            align 8 symtab 0 alias set -1 canonical type 0x2b6e7ed8c300
precision 8 min <integer_cst 0x2b6e7ed7c780 -128> max <integer_cst
0x2b6e7ed7c8d0 127>
            pointer_to_this <pointer_type 0x2b6e7eda3000>>
        unsigned DI
        size <integer_cst 0x2b6e7ed7cb70 constant invariant 64>
        unit size <integer_cst 0x2b6e7ed7cba0 constant invariant 8>
        align 64 symtab 0 alias set -1 canonical type 0x2b6e7eda3000>

    arg 0 <parm_decl 0x2b6e7ed82240 p type <pointer_type 0x2b6e7eda3000>
        used unsigned DI file t.i line 1 col 17 size <integer_cst
0x2b6e7ed7cb70 64> unit size <integer_cst 0x2b6e7ed7cba0 8>
        align 64 context <function_decl 0x2b6e7ee72b60 foo> initial
<pointer_type 0x2b6e7eda3000> arg-type <pointer_type 0x2b6e7eda3000>>
    arg 1 <integer_cst 0x2b6e7f709600 type <integer_type 0x2b6e7ed8c000 long
unsigned int> constant invariant public overflow -4>>

but I consider the 'overflow' bit set on the -4 a bug.  Also POINTER_PLUS_EXPR
does not in any way change the issues we raised with undefinedness of
overflow in pointer + offset expressions.

Now, Joseph says

> This bug is about the interpretation of GCC's internal representation, not 
> that of the standard.

where yes, we seem to agreed to having an unsigned offset argument to
POINTER_PLUS_EXPR which we need to interpret as a signed quantity.  And
in a different place we sort-of agreed to limit the maximum object size
gcc handles to half of SIZE_T_MAX.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=27214

[Bug c/27214] The C frontend introduces undefined pointer overflow

[bugdal at aerifal dot cx]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=27214

Rich Felker <bugdal at aerifal dot cx> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bugdal at aerifal dot cx

--- Comment #11 from Rich Felker <bugdal at aerifal dot cx> 2012-05-06 04:11:03 UTC ---
I would lean towards marking this one invalid. Under normal circumstances (and
I would argue, under ALL conditions, on a high-quality implementation), objects
cannot be larger than SIZE_MAX/2. This is because ptrdiff_t has been chosen to
be the signed type corresponding to size_t, and if objects larger than
SIZE_MAX/2 were allowed, valid pointer subtractions would overflow the signed
ptrdiff_t and result in undefined behavior.

There are three ways of addressing this issue; either:
(1) you say "subtracting pointers is unsafe unless the application makes an
effort to ensure that no huge objects exist" even though that's hard to do in
any portable way; OR
(2) you disallow objects sufficiently large that ptrdiff_t would overflow; OR
(3) you make ptrdiff_t a larger type (e.g. 64-bit on 32-bit systems). But this
is not an option since you're always dealing with an already-defined ABI.

If you take option (1), large objects (>SIZE_MAX/2) are already extremely
dangerous and so the additional wrapping issue in GCC's internal representation
is a really small matter in comparison. If you take option (2), offsets can
always be interpreted as the signed type.

[Bug c/27214] The C frontend introduces undefined pointer overflow

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=27214

Richard Guenther <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |ASSIGNED
   Last reconfirmed|                            |2012-05-07
         AssignedTo|unassigned at gcc dot       |rguenth at gcc dot gnu.org
                   |gnu.org                     |
     Ever Confirmed|0                           |1

--- Comment #12 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-05-07 09:00:26 UTC ---
There is no disagreement about the C side of things.  Still the middle-end
side needs some cleanups.  Incidentially I have been working on those.

[Bug c/27214] The C frontend introduces undefined pointer overflow

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=27214

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |FIXED
             Status|ASSIGNED                    |RESOLVED

--- Comment #15 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed.  That the POINTER_PLUS_EXPR is unsigned sizetype is a design decision,
it is interpreted signed and thus there is no bad overflow.  Yes, we should
have used signed sizetype.