[Bug c/63303] New: Pointer subtraction is broken when using -fsanitize=undefined

[Bug c/63303] New: Pointer subtraction is broken when using -fsanitize=undefined

[mikulas at artax dot karlin.mff.cuni.cz]

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

            Bug ID: 63303
           Summary: Pointer subtraction is broken when using
                    -fsanitize=undefined
           Product: gcc
           Version: 4.9.1
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
          Assignee: unassigned at gcc dot gnu.org
          Reporter: mikulas at artax dot karlin.mff.cuni.cz
              Host: x86_64-linux-gnux32
            Target: x86_64-linux-gnux32
             Build: x86_64-linux-gnux32

The undefined behavior sanitizer incorrectly warns about pointer subtraction.

The reason is that the undefined behavior sanitizer treats pointer subtraction
like subtraction of two signed integers and warns if it would result in integer
overflow. However, this logic is incorrect.

Subtracting of these two pointers is perfectly legal operation but it results
in incorrect warning: (char *)0x90000000 - (char *)0x70000000: this bug causes
spurious warnings in correct program if array spans the boundary 0x80000000 and
the program subtracts pointers in this array.

Subtracting these two pointers doesn't result in a warning, but it should
because the resulting integer overflows: (char *)0xc0000000 - (char
*)0x30000000

BTW. The sanitizer also lacks warnings when addition of a pointer and integer
results in overflow. For example (char *)0xd0000000 + 0x40000000U doesn't
result in a warning but it should.

This is the example code, compile it with -fsanitize=undefined

#include <stdio.h>
#include <stddef.h>

__attribute((noinline,noclone)) ptrdiff_t ptr_diff(char *p1, char *p2)
{
        return p1 - p2;
}

__attribute((noinline,noclone)) void *ptr_add(char *p1, unsigned long p2)
{
        return p1 + p2;
}

void *get_address(unsigned n)
{
        return (void *)((unsigned long)n << (sizeof(void *) * 8 - 4));
}

int main(void)
{
        printf("%ld\n", (long)ptr_diff(get_address(0x9), get_address(0x7))); /*
sanitizer should not warn here */
        printf("%ld\n", (long)ptr_diff(get_address(0xc), get_address(0x3))); /*
sanitizer should warn here */
        return 0;
}

[Bug c/63303] Pointer subtraction is broken when using -fsanitize=undefined

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org

--- Comment #1 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Your testcase is definitely not valid C, you can't perform pointer arithmetics
in between pointers that don't point into the same array or one past the last
element in the array.

[Bug c/63303] Pointer subtraction is broken when using -fsanitize=undefined

[mikulas at artax dot karlin.mff.cuni.cz]

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

--- Comment #2 from mikulas at artax dot karlin.mff.cuni.cz ---
Jakub Jelinek: I know, but the problem happened in perfectly valid program.

Suppose that you do:
char *p = malloc(0x20000000); - the allocator allocates the array at
0x70000000.

Then, you do:
char *q = p + 0x20000000; /* q is 0x90000000, pointing to the end of the array
*/
long n = q - p;   --- this triggers the warning, although it is perfectly valid
operation.

The above case is non-reproducible because it depends on the address returned
from the allocator. I wrote the example code to trigger the warning
deterministically.

[Bug c/63303] Pointer subtraction is broken when using -fsanitize=undefined

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jason at gcc dot gnu.org,
                   |                            |jsm28 at gcc dot gnu.org,
                   |                            |rguenth at gcc dot gnu.org

--- Comment #3 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
The problem is that we don't have a POINTER_DIFF_EXPR similar to
POINTER_PLUS_EXPR, which would take two pointers and return an integer, and the
FEs emit pointer difference as cast of both the pointers to signed integral
type
and subtracts the integers.
If
ssize_t foo (char *p, char *q) { return p - q; }
is changed into
ssize_t foo (char *p, char *q) { return (ssize_t) p - (ssize_t) q; }
by the FE, then indeed if you have array starting at 0x7fff0000 and ending at
0x80010000 and subtract those two pointers, you get undefined behavior.
That is undefined behavior not just for ubsan, but for anything else in the
middle-end.
So, if pointer difference is supposed to behave differently, then
we'd either need to represent pointer difference as
ssize_t foo (char *p, char *q) { return (ssize_t) ((size_t) p - (size_t) q); }
(but we risk missed optimizations that way I'd say), or we'd need a better
representation of it in the middle-end.

[Bug c/63303] Pointer subtraction is broken when using -fsanitize=undefined

[mikulas at artax dot karlin.mff.cuni.cz]

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

--- Comment #4 from mikulas at artax dot karlin.mff.cuni.cz ---
... and another related problem (try this on 32-bit system):

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
        short *a = malloc(0x50000000 * sizeof(short));
        short *b = a + 0x50000000;
        printf("%ld\n", (long)(b - a));
        return 0;
}

Here, the return value should be positive (0x50000000), but it is negative.
IMHO, according to the C standard, this is program correct and positive result
should be returned.

The problem is that it is not easy to fix it without performance penalty and
all compilers that I tried (gcc, clang, icc, suncc, opencc, nwcc) print
negative result.

[Bug c/63303] Pointer subtraction is broken when using -fsanitize=undefined

[jakub at gcc dot gnu.org]

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

--- Comment #5 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
(In reply to mikulas from comment #4)
> ... and another related problem (try this on 32-bit system):
> 
> #include <stdio.h>
> #include <stdlib.h>
> 
> int main(void)
> {
>         short *a = malloc(0x50000000 * sizeof(short));
>         short *b = a + 0x50000000;
>         printf("%ld\n", (long)(b - a));
>         return 0;
> }
> 
> Here, the return value should be positive (0x50000000), but it is negative.
> IMHO, according to the C standard, this is program correct and positive
> result should be returned.

This testcase is invalid, you really can't have an object bigger than half of
the address space in C/C++, pointer difference is signed ptrdiff_t and if you
have larger object, you can't subtract arbitrary char pointers in it anymore.
If you need more than 2GB in a single array, just use 64-bit system.

[Bug c/63303] Pointer subtraction is broken when using -fsanitize=undefined

[mikulas at artax dot karlin.mff.cuni.cz]

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

--- Comment #6 from mikulas at artax dot karlin.mff.cuni.cz ---
"you really can't have an object bigger than half of the address space in
C/C++" - where does the standard claim this? If this is true, we should change
malloc so that it doesn't allocate 2GiB or larger objects.


Regarding pointer difference, the C standard says this:

When two pointers are subtracted, both shall point to elements of the same
array object, or one past the last element of the array object; the result is
the difference of the subscripts of the two array elements. The size of the
result is implementation-defined, and its type (a signed integer type) is
ptrdiff_t defined in the <stddef.h> header. If the result is not representable
in an object of that type, the behavior is undefined. In other words, if the
expressions P and Q point to, respectively, the i-th and j-th elements of an
array object, the expression (P)-(Q) has the value i−j provided the value fits
in an object of type ptrdiff_t.

So: p points to the beginning, q points one past the last element, so the first
condition is valid.

The result is the difference of the subscripts of those two array elements:
0x50000000 - 0 = 0x50000000 - this is clearly representable in the type
ptrdiff_t, so 0x50000000 result should be returned.
>From gcc-bugs-return-462131-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Fri Sep 19 16:20:57 2014
Return-Path: <gcc-bugs-return-462131-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 3399 invoked by alias); 19 Sep 2014 16:20:57 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 3333 invoked by uid 48); 19 Sep 2014 16:20:50 -0000
From: "krebbel at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug debug/63300] 'const volatile' sometimes stripped in debug info
Date: Fri, 19 Sep 2014 16:20:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: debug
X-Bugzilla-Version: 5.0
X-Bugzilla-Keywords:
X-Bugzilla-Severity: normal
X-Bugzilla-Who: krebbel at gcc dot gnu.org
X-Bugzilla-Status: NEW
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields: bug_status cf_reconfirmed_on cc everconfirmed
Message-ID: <bug-63300-4-xNCZFiYOEJ@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-63300-4@http.gcc.gnu.org/bugzilla/>
References: <bug-63300-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2014-09/txt/msg01965.txt.bz2
Content-length: 1932

https://gcc.gnu.org/bugzilla/show_bug.cgi?idc300

Andreas Krebbel <krebbel at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2014-09-19
                 CC|                            |mark at gcc dot gnu.org
     Ever confirmed|0                           |1

--- Comment #1 from Andreas Krebbel <krebbel at gcc dot gnu.org> ---
Reghunt indicates that this is caused by r214143.

For a const volatile type none of the following IFs is triggered:

  if ((cv_quals & TYPE_QUAL_CONST)
      /* If there are multiple type modifiers, prefer a path which
     leads to a qualified type.  */
      && (((cv_quals & ~TYPE_QUAL_CONST) == TYPE_UNQUALIFIED)
      || get_qualified_type (type, cv_quals) == NULL_TREE
      || (get_qualified_type (type, cv_quals & ~TYPE_QUAL_CONST)
          != NULL_TREE)))
    {
      mod_type_die = new_die (DW_TAG_const_type, mod_scope, type);
      sub_die = modified_type_die (type, cv_quals & ~TYPE_QUAL_CONST,
                   context_die);
    }
  else if ((cv_quals & TYPE_QUAL_VOLATILE)
       && (((cv_quals & ~TYPE_QUAL_VOLATILE) == TYPE_UNQUALIFIED)
           || get_qualified_type (type, cv_quals) == NULL_TREE
           || (get_qualified_type (type, cv_quals & ~TYPE_QUAL_VOLATILE)
           != NULL_TREE)))
    {
      mod_type_die = new_die (DW_TAG_volatile_type, mod_scope, type);
      sub_die = modified_type_die (type, cv_quals & ~TYPE_QUAL_VOLATILE,
                   context_die);
    }
  else if (cv_quals & TYPE_QUAL_RESTRICT)
    {
      mod_type_die = new_die (DW_TAG_restrict_type, mod_scope, type);
      sub_die = modified_type_die (type, cv_quals & ~TYPE_QUAL_RESTRICT,
                   context_die);
    }

So the DIE ends up with an unqualified type.

[Bug c/63303] Pointer subtraction is broken when using -fsanitize=undefined

[joseph at codesourcery dot com]

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

--- Comment #7 from joseph at codesourcery dot com <joseph at codesourcery dot com> ---
Yes, I consider it a bug in malloc that it produces objects 2GB or more in 
size on 32-bit systems (because of the one-past-end address, the largest 
size that can't produce undefined behavior in the user program is 2GB 
minus one byte).

Unfortunately I expect some 32-bit applications rely on such large 
allocations, so if we changed malloc (please report a bug to glibc 
Bugzilla) we'd need a way (feature test macro?) for people to continue to 
build programs to use the old malloc, as well as to avoid breaking 
existing binaries.

[Bug c/63303] Pointer subtraction is broken when using -fsanitize=undefined

[jakub at gcc dot gnu.org]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain; charset="UTF-8", Size: 3730 bytes --]

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

--- Comment #8 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
(In reply to mikulas from comment #6)
> Regarding pointer difference, the C standard says this:
> 
> When two pointers are subtracted, both shall point to elements of the same
> array object, or one past the last element of the array object; the result
> is the difference of the subscripts of the two array elements. The size of
> the result is implementation-defined, and its type (a signed integer type)
> is ptrdiff_t defined in the <stddef.h> header. If the result is not
> representable in an object of that type, the behavior is undefined. In other
> words, if the expressions P and Q point to, respectively, the i-th and j-th
> elements of an array object, the expression (P)-(Q) has the value i−j
> provided the value fits in an object of type ptrdiff_t.
> 
> So: p points to the beginning, q points one past the last element, so the
> first condition is valid.
> 
> The result is the difference of the subscripts of those two array elements:
> 0x50000000 - 0 = 0x50000000 - this is clearly representable in the type
> ptrdiff_t, so 0x50000000 result should be returned.

See what I wrote, any object size bigger than half of address space really
isn't supportable, because then (char *) (P) - (char *) (Q) might not fit into
ptrdiff_t.  There is no point slowing down all pointer subtractions (other than
char/signed char/unsigned char pointers) for something that really wouldn't
work reliably anyway.
>From gcc-bugs-return-462134-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Fri Sep 19 16:26:53 2014
Return-Path: <gcc-bugs-return-462134-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 10356 invoked by alias); 19 Sep 2014 16:26:53 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 10321 invoked by uid 48); 19 Sep 2014 16:26:49 -0000
From: "jsm28 at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug target/63312] FAIL: gcc.dg/torture/float128-exact-underflow.c   -O0  execution test
Date: Fri, 19 Sep 2014 16:26:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: target
X-Bugzilla-Version: 5.0
X-Bugzilla-Keywords:
X-Bugzilla-Severity: normal
X-Bugzilla-Who: jsm28 at gcc dot gnu.org
X-Bugzilla-Status: UNCONFIRMED
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields: attachments.created
Message-ID: <bug-63312-4-gjd1sS2BDr@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-63312-4@http.gcc.gnu.org/bugzilla/>
References: <bug-63312-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2014-09/txt/msg01968.txt.bz2
Content-length: 361

https://gcc.gnu.org/bugzilla/show_bug.cgi?idc312

--- Comment #1 from Joseph S. Myers <jsm28 at gcc dot gnu.org> ---
Created attachment 33519
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id3519&actioníit
Untested patch

Please try this patch.  As I noted in my patch posting, the issue is that there
is no ia64 definition of FP_TRAPPING_EXCEPTIONS.

[Bug c/63303] Pointer subtraction is broken when using -fsanitize=undefined

[mikulas at artax dot karlin.mff.cuni.cz]

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

--- Comment #9 from mikulas at artax dot karlin.mff.cuni.cz ---
> See what I wrote, any object size bigger than half of address space really
> isn't supportable, because then (char *) (P) - (char *) (Q) might not fit into
> ptrdiff_t.  There is no point slowing down all pointer subtractions (other than
> char/signed char/unsigned char pointers) for something that really wouldn't
> work reliably anyway.

But the code in comment 4 doesn't perform (char *)P - (char *)Q. It performs
(short *)P - (short *)Q. And that result clearly fits into the signed ptrdiff_t
type.

If the code in comment 4 performed (char *)b - (char *)a, that operation would
be invalid because of overflow. But it doesn't.

[Bug c/63303] Pointer subtraction is broken when using -fsanitize=undefined

[rguenth at gcc dot gnu.org]

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

--- Comment #10 from Richard Biener <rguenth at gcc dot gnu.org> ---
To support the standards definition of p1 - p2 we'd need a POINTER_DIFF_EXPR
that also embeds the exact division by the array element size.

Btw, while C and C++ share pointer_int_sum they have differing implementations
for computing pointer differences.

The safe variant would be indeed to compute the pointer difference using an
unsigned type and I can't see what optimizations we lose when doing that.
Note that you'd still need to convert the result to a signed type before
doing the exact division by the element size.

[Bug c/63303] Pointer subtraction is broken when using -fsanitize=undefined

[mikulas at artax dot karlin.mff.cuni.cz]

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

--- Comment #11 from mikulas at artax dot karlin.mff.cuni.cz ---
Richard Biener: if the middle end tells us that one pointer is greater or equal
than the other pointer, we could do unsigned subtraction and shift.

But if we don't know which pointer is greater, it gets more complicated: To do
correct short* pointer subtraction, we need to subtract pointers using
sub %edx, %eax; rcr $1, %eax --- i.e. shift the carry bit back to the topmost
bit of the result. According to Agner's tables, rcr with 1-bit count takes 1
tick on AMD and 2 ticks on Intel, so the performance penalty isn't that big. On
other architectures that lack rcr, it would be more complicated.

Another possibility is to file a defect report on the C standard and request
that program in comment 4 be considered invalid. - for example, change the
wording to this: "If the result multiplied by the size of the array element is
not representable in an object of that type, the behavior is undefined." - that
would specify that that subtraction is invalid.

[Bug c/63303] Pointer subtraction is broken when using -fsanitize=undefined

[rguenth at gcc dot gnu.org]

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

--- Comment #12 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Jakub Jelinek from comment #3)
> The problem is that we don't have a POINTER_DIFF_EXPR similar to
> POINTER_PLUS_EXPR, which would take two pointers and return an integer, and
> the FEs emit pointer difference as cast of both the pointers to signed
> integral type
> and subtracts the integers.
> If
> ssize_t foo (char *p, char *q) { return p - q; }
> is changed into
> ssize_t foo (char *p, char *q) { return (ssize_t) p - (ssize_t) q; }
> by the FE, then indeed if you have array starting at 0x7fff0000 and ending
> at 0x80010000 and subtract those two pointers, you get undefined behavior.
> That is undefined behavior not just for ubsan, but for anything else in the
> middle-end.
> So, if pointer difference is supposed to behave differently, then
> we'd either need to represent pointer difference as
> ssize_t foo (char *p, char *q) { return (ssize_t) ((size_t) p - (size_t) q);
> }
> (but we risk missed optimizations that way I'd say), or we'd need a better
> representation of it in the middle-end.

Note that apart from missing POINTER_DIFF this isn't a middle-end but a
frontend
issue.