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; }
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.
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.
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.
... 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.
(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.
"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.
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.
(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.
> 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.
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.
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.
(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.
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 )
(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.
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.
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.
"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.
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.
This seems fixed in gcc-8, no?
> "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.