Re: checked integer arithmetic

[Paul Eggert]

On 12/14/2016 02:56 PM, Bruno Haible wrote:
> Are you saying that -fsanitize=undefined or -fsanitize=signed-integer-overflow
> (or -ftrapv, when using an older GCC) can detect integer overflow for signed
> integers, whereas no such option exists and won't exist for unsigned integers
> (because there are so many pieces of code that intentionally do a mod-2^32
> or mod-2^64  computation on unsigned integers?

Yes, and as Eric says, arithmetic is well defined for unsigned integers, 
so long as they don't fit in 'int'.

> what about the gnulib 'xsize' module for checked size_t computations?

That module should work if INT_MAX < SIZE_MAX, which is a safe 
assumption as lots of code would break on a platform where SIZE_MAX <= 
INT_MAX. I suppose it wouldn't hurt to add 'verify (INT_MAX < 
SIZE_MAX);' to document the assumption.

Oh -- perhaps you're asking whether it's a good idea to use xsum with 
size_t rather than native addition with ptrdiff_t. Although xsize.h is 
portable and nicely maps size overflows to memory-allocation errors, it 
has some downsides. With xsize, it's a bit harder to read xsum calls 
than simple uses of +. WIth xsize, programming errors are more likely to 
not get caught by -fsanitize=undefined. But perhaps the biggest issue is 
that xsize does not prevent errors due to sizes greater than 
PTRDIFF_MAX. Although this problem is not unique to xsize (lots of 
gnulib and GNU core utilities have it) it's a shame that xsize doesn't 
prevent it, since the problem is in xsize's wheelhouse.

Come to think of it, I suppose we should change xalloc_oversized to 
report an overflow if the resulting size would be greater than 
PTRDIFF_MAX. That should catch more potential problems in Gnulib and in 
Gnulib-using code.

Here is an example of why arrays larger than PTRDIFF_MAX bytes can cause 
real problems. On a 32-bit host, the program below calls malloc (2**31), 
because n == 2**30 and sizeof (short) is 2. Assuming malloc succeeds, 
one might naively think that diff returns 2**30 (which does fit in 
ptrdiff_t) and that 'main' therefore returns 1. But this does not 
happen, at least not on my platform (Fedora 24, gcc 6.2.1). When 
compiled with gcc -O2, 'main' returns zero without allocating anything! 
'main' can do so because subtracting two pointers that differ by more 
than PTRDIFF_MAX bytes results in undefined behavior, so GCC can 
generate whatever code it wants.

#include <stdint.h>
#include <stddef.h>
#include <stdlib.h>

ptrdiff_t
diff (short *a, short *b)
{
  return a - b;
}

int
main (void)
{
  size_t n = PTRDIFF_MAX / sizeof (short) + 1;
  short *x = malloc (n * sizeof (short));
  return 0 < diff (x + n, x);
}