Bug 63303 - Pointer subtraction is broken when using -fsanitize=undefined
Summary: Pointer subtraction is broken when using -fsanitize=undefined
Status: NEW
Alias: None
Product: gcc
Classification: Unclassified
Component: c (show other bugs)
Version: 4.9.1
: P3 normal
Target Milestone: ---
Assignee: Not yet assigned to anyone
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2014-09-19 01:42 UTC by mikulas
Modified: 2018-08-26 23:23 UTC (History)
11 users (show)

See Also:
Host: x86_64-linux-gnux32
Target: x86_64-linux-gnux32
Build: x86_64-linux-gnux32
Known to work:
Known to fail:
Last reconfirmed: 2015-11-23 00:00:00


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description mikulas 2014-09-19 01:42:05 UTC
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;
}
Comment 1 Jakub Jelinek 2014-09-19 07:26:04 UTC
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.
Comment 2 mikulas 2014-09-19 13:38:08 UTC
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.
Comment 3 Jakub Jelinek 2014-09-19 13:47:36 UTC
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.
Comment 4 mikulas 2014-09-19 15:50:19 UTC
... 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.
Comment 5 Jakub Jelinek 2014-09-19 15:57:46 UTC
(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.
Comment 6 mikulas 2014-09-19 16:15:00 UTC
"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.
Comment 7 joseph@codesourcery.com 2014-09-19 16:21:06 UTC
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.
Comment 8 Jakub Jelinek 2014-09-19 16:22:31 UTC
(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.
Comment 9 mikulas 2014-09-19 16:28:53 UTC
> 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.
Comment 10 Richard Biener 2014-09-22 07:42:30 UTC
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.
Comment 11 mikulas 2014-09-22 14:31:19 UTC
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.
Comment 12 Richard Biener 2015-10-19 11:03:27 UTC
(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.
Comment 13 Szabolcs Nagy 2015-11-22 17:31:23 UTC
if gcc treats p-q as (ssize_t)p-(ssize_t)q and makes
optimization decisions based on signed int range then
that's broken and leads to wrong code gen.

e.g. gcc optimizes if(n - 0x7fffffff > 0).. away
(but not if(-0x7fffffff-1 - n > 0), but that's another
bug), so

$ cat bug.c
#include <sys/mman.h>
int main()
{
char *p = mmap((void*)(0x80000000-4096), 2*4096, PROT_READ|PROT_WRITE,
               MAP_FIXED|MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
char *q = (void*)(0x7fffffff); // p+4095
if ((p+4096) - q > 0) return 0; // wrongly optimized away
return 1;
}

$ gcc-5.2-i386 -fomit-frame-pointer -fno-asynchronous-unwind-tables -O3 -S bug.c
$ cat bug.s
	.file	"bug.c"
	.section	.text.unlikely,"ax",@progbits
.LCOLDB0:
	.section	.text.startup,"ax",@progbits
.LHOTB0:
	.p2align 2,,3
	.globl	main
	.type	main, @function
main:
	leal	4(%esp), %ecx
	andl	$-16, %esp
	pushl	-4(%ecx)
	pushl	%ebp
	movl	%esp, %ebp
	pushl	%ecx
	subl	$8, %esp
	pushl	$0
	pushl	$0
	pushl	$-1
	pushl	$50
	pushl	$3
	pushl	$8192
	pushl	$2147479552
	call	mmap
	addl	$32, %esp
	movl	$1, %eax
	movl	-4(%ebp), %ecx
	leave
	leal	-4(%ecx), %esp
	ret
	.size	main, .-main
	.section	.text.unlikely
.LCOLDE0:
	.section	.text.startup
.LHOTE0:
	.ident	"GCC: (GNU) 5.2.0"
	.section	.note.GNU-stack,"",@progbits

after the mmap call %eax is unconditionally set to 1.

at runtime the mmap succeeds and the returned object
crosses the 0x80000000 boundary, so the return value is
incorrect.

(i found this bug report after incorrectly getting SIGILL
at ptrdiffs with
-fsanitize=undefined -fsanitize-undefined-trap-on-error )
Comment 14 Florian Weimer 2015-11-23 10:34:30 UTC
(In reply to Szabolcs Nagy from comment #13)
> if gcc treats p-q as (ssize_t)p-(ssize_t)q and makes
> optimization decisions based on signed int range then
> that's broken and leads to wrong code gen.

Thanks for the test case.  I think the remedy proposed so far (glibc should block allocations sized half of the address space and larger) is insufficient.
Comment 15 Richard Biener 2015-11-23 11:58:57 UTC
Note that in practice it needs exposal of the address constant to trigger the
bogus optimization.

Note that the IL from the frontend is indeed the one to blame here:

    char * p = (char *) mmap (2147479552B, 8192, 3, 50, -1, 0);
    char * q = 2147483647B;
  if ((int) (p + 4096) - (int) q > 0)
    {

for correctness WRT undefined overflow we need to do the subtraction
in unsigned arithmetic and then interpret the result as signed
(for an eventual division by element size).

Same issue in the C++ frontend btw.
Comment 16 Alexander Cherepanov 2015-11-23 12:20:00 UTC
On 2015-11-23 14:58, rguenth at gcc dot gnu.org wrote:
> Note that in practice it needs exposal of the address constant to trigger the
> bogus optimization.

No. The program:

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

int main()
{
   // make sure our allocation will cross 0x80000000 boundary
   // but still will not violate limits of gcc
   size_t len = 0x7fffffff;
   char *p1 = malloc(len);
   char *volatile v = p1 + len;
   char *p2 = v;
   long l1 = (long)(uintptr_t)p1;
   long l2 = (long)(uintptr_t)p2;
   if (l2 < l1) {
     long z = p2 - p1;
     if (z < 0)
       printf("%ld\n", z);
   }
}

prints a positive number for me even though it guards against it. gcc 
5.2 with -m32 -O2.
Comment 17 Joshua Green 2018-08-21 12:01:33 UTC
"But if we don't know which pointer is greater, it gets more complicated: ..."

I'm not sure that this is true.  For types that are larger than 1 byte, it seems that one can do the subtraction after any division(s), hence only costing an additional division (or shift):

    T * p;
    T * q;

    .
    .
    .

    intptr_t pVal = ((uintptr_t) p)/(sizeof *p);
    intptr_t qVal = ((uintptr_t) q)/(sizeof *q);

    ptrdiff_t p_q = pVal - qVal;

This should work in well-defined cases, for if p and q are pointers into the same array then (presumably) ((uintptr_t) p) and ((uintptr_t) q) must have the same remainder modulo sizeof(T).

Of course, even an additional shift may be too expensive in some cases, so it's not entirely clear that this change should be made.
Comment 18 joseph@codesourcery.com 2018-08-21 12:07:03 UTC
On Tue, 21 Aug 2018, jvg1981 at aim dot com wrote:

>     intptr_t pVal = ((uintptr_t) p)/(sizeof *p);
>     intptr_t qVal = ((uintptr_t) q)/(sizeof *q);

Note that this can be expanded like an exact division (right shift and 
multiply by reciprocal).  See bug 67999 comment 24 and bug 81801 comment 4.
Comment 19 Marc Glisse 2018-08-21 12:17:49 UTC
This seems fixed in gcc-8, no?
Comment 20 Joshua Green 2018-08-26 23:23:23 UTC
> "But if we don't know which pointer is greater, it gets more complicated:
> ..."
> 
> I'm not sure that this is true.  For types that are larger than 1 byte, it
> seems that one can do the subtraction after any division(s), hence only
> costing an additional division (or shift):
> 
>     T * p;
>     T * q;
> 
>     .
>     .
>     .
> 
>     intptr_t pVal = ((uintptr_t) p)/(sizeof *p);
>     intptr_t qVal = ((uintptr_t) q)/(sizeof *q);
> 
>     ptrdiff_t p_q = pVal - qVal;
> 
> This should work in well-defined cases, for if p and q are pointers into the
> same array then (presumably) ((uintptr_t) p) and ((uintptr_t) q) must have
> the same remainder modulo sizeof(T).
> 
> Of course, even an additional shift may be too expensive in some cases, so
> it's not entirely clear that this change should be made.

It occurred to me that such contortions can be avoided in the (possibly) common case when (say) q is actually an array.