Re: BUG #5416: int4inc() is wrong

The following bug has been logged online:

Bug reference: 5416
Logged by: John Regehr
Email address: regehr(at)cs(dot)utah(dot)edu
PostgreSQL version: git head Apr 12
Operating system: n/a
Description: int4inc() is wrong
Details:

The overflow check in int4inc() from int.c is wrong. The problem is that in
C, signed overflow is undefined. Both LLVM and GCC eliminate the overflow
check in this function. This is easy to see by looking at the asm emitted
by either compiler.

There are several easy ways to fix this code. One would be to test arg
against INT_MAX before incrementing. Another would be to cast arg to
unsigned, increment it, then do the check.

"John Regehr" <regehr(at)cs(dot)utah(dot)edu> writes:
> The overflow check in int4inc() from int.c is wrong.

Hm, works for me:

regression=# \set VERBOSITY verbose
regression=# select int4inc(2147483647);
ERROR: 22003: integer out of range
LOCATION: int4inc, int.c:768

> The problem is that in
> C, signed overflow is undefined. Both LLVM and GCC eliminate the overflow
> check in this function. This is easy to see by looking at the asm emitted
> by either compiler.

Note that we recommend using -fwrapv with gcc, so that it doesn't break
code that depends on this type of test. (If int4inc isn't working then
there are probably a lot of other places that are broken too.) I imagine
LLVM has the same or similar switch.

> There are several easy ways to fix this code. One would be to test arg
> against INT_MAX before incrementing. Another would be to cast arg to
> unsigned, increment it, then do the check.

None of these proposals are improvements over what's there. The
fundamental problem is that if the compiler chooses to believe that
overflow doesn't exist, it can optimize away *any* test that could only
succeed in overflow cases. Finding a form of the test that fails to be
optimized away by today's version of gcc doesn't protect you against
tomorrow's version.

regards, tom lane

Hi Tom,

> Note that we recommend using -fwrapv with gcc, so that it doesn't break
> code that depends on this type of test. (If int4inc isn't working then
> there are probably a lot of other places that are broken too.) I imagine
> LLVM has the same or similar switch.

llvm-gcc has the -fwrapv flag, but Clang does not, nor does Intel CC.

>> There are several easy ways to fix this code. One would be to test arg
>> against INT_MAX before incrementing. Another would be to cast arg to
>> unsigned, increment it, then do the check.
>
> None of these proposals are improvements over what's there. The
> fundamental problem is that if the compiler chooses to believe that
> overflow doesn't exist, it can optimize away *any* test that could only
> succeed in overflow cases. Finding a form of the test that fails to be
> optimized away by today's version of gcc doesn't protect you against
> tomorrow's version.

Your assessment is not quite correct. The existing function -- when passed
INT_MAX as the argument -- executes an operation with undefined behavior,
and a correct C compiler can optimize away the check.

The alternate tests do not execute operations with undefined behavior for
any argument value. Therefore, any compiler which removes the test is
wrong. Both the GCC and LLVM groups will be happy to fix a bug of that
kind if it exists.

Thanks,

John Regehr

John Regehr <regehr(at)cs(dot)utah(dot)edu> writes:
> Hi Tom,
>> None of these proposals are improvements over what's there. The
>> fundamental problem is that if the compiler chooses to believe that
>> overflow doesn't exist, it can optimize away *any* test that could only
>> succeed in overflow cases. Finding a form of the test that fails to be
>> optimized away by today's version of gcc doesn't protect you against
>> tomorrow's version.

> Your assessment is not quite correct. The existing function -- when passed
> INT_MAX as the argument -- executes an operation with undefined behavior,
> and a correct C compiler can optimize away the check.

> The alternate tests do not execute operations with undefined behavior for
> any argument value.

No, you're missing the point. int4inc() could be rewritten with a test
for INT_MAX or similar, because its overflow behavior is so trivial:
there is exactly one, well-known, input value that is troublesome.
However, this is not so easy for any of the other arithmetic operations.
We need an approach that results in sane code and sane behavior for all
those places, and there's no point in making int4inc() follow a
different coding style than is used in the other functions.

It might be worth pointing out that we prefer to avoid explicit uses of
INT_MAX, or similar hard-wired assumptions about exactly how wide the
datatypes are. This is so that the code won't fail if someday "int"
is not the same as "int32", for instance. The issue is already quite
pressing for int64, which corresponds to different native C types on
different platforms.

If you can show me rewrites of all the basic arithmetic operations that
detect overflow in full compliance with the C standard, and are
readable, portable, and efficient, I'm all ears. At the moment, though,
I regard the notion that C compilers can assume no overflow as pure
brain damage on the part of the spec authors and the compiler authors.
The real world is not like that.

regards, tom lane

Hi Tom,

> If you can show me rewrites of all the basic arithmetic operations that
> detect overflow in full compliance with the C standard, and are
> readable, portable, and efficient, I'm all ears.

These are the best ones that I know of:

https://www.securecoding.cert.org/confluence/display/seccode/INT32-C.+Ensure+that+operations+on+signed+integers+do+not+result+in+overflow

Even if you dislike these, please take a look at the safety checks for
shifts. The current postgresql shift functions need to be strengthened,
and it is easy to do.

John Regehr

John Regehr wrote:
> Hi Tom,
>
> > If you can show me rewrites of all the basic arithmetic operations that
> > detect overflow in full compliance with the C standard, and are
> > readable, portable, and efficient, I'm all ears.
>
> These are the best ones that I know of:
>
> https://www.securecoding.cert.org/confluence/display/seccode/INT32-C.+Ensure+that+operations+on+signed+integers+do+not+result+in+overflow
>
> Even if you dislike these, please take a look at the safety checks for
> shifts. The current postgresql shift functions need to be strengthened,
> and it is easy to do.

Added to TODO:

Consider improving overflow detection

* http://archives.postgresql.org/message-id/4BC66A57.2030809@cs.utah.edu

--
Bruce Momjian <bruce(at)momjian(dot)us> http://momjian.us
EnterpriseDB http://enterprisedb.com

+ None of us is going to be here forever. +

Bruce Momjian <bruce(at)momjian(dot)us> writes:
> Consider improving overflow detection
> * http://archives.postgresql.org/message-id/4BC66A57.2030809@cs.utah.edu

I did look at those at the time, and saw absolutely no reason to prefer
them over what we do now.

regards, tom lane

Tom Lane wrote:
> Bruce Momjian <bruce(at)momjian(dot)us> writes:
> > Consider improving overflow detection
> > * http://archives.postgresql.org/message-id/4BC66A57.2030809@cs.utah.edu
>
> I did look at those at the time, and saw absolutely no reason to prefer
> them over what we do now.

OK, removed from TODO.

--
Bruce Momjian <bruce(at)momjian(dot)us> http://momjian.us
EnterpriseDB http://enterprisedb.com

+ None of us is going to be here forever. +