Thread: [RFC] Fix div/mul crash and more undefined behavior

The INT_MIN / -1 crash problem was partially addressed in 2006 and
commit 9fc6f4e1ae107f44807c4906105e1f7eb052ecb1.

http://archives.postgresql.org/pgsql-patches/2006-06/msg00102.php

However, the fix is incomplete and incorrect for some cases.

64-bit crash
============

Below is an example that crashes PostgreSQL on Windows, using the
64-bit binary from http://www.postgresql.org/download/windows/.
SELECT ((-9223372036854775808)::int8) % (-1);

Note that the previous discussion concluded that int8 (64-bit)
division didn't crash, which is incorrect.

http://archives.postgresql.org/pgsql-patches/2006-06/msg00104.php

My guess is that the previous test was carried out on a 32-bit
Windows, where there's no 64-bit division instruction.  In that
case, the generated code calls a runtime function (e.g., lldiv),
which doesn't trap.  However, on a 64-bit system, the compiler
generates the idivq instruction, which leads to a crash.

Note that the problem is not limited to division.  The following
multiplication crashes as well:
SELECT ((-9223372036854775808)::int8) * ((-1)::int8);

The reason is that the multiplication overflow check uses a division.

32-bit crash
============

The previous fix doesn't fix all possible crashes, even on a 32-bit
Windows.  Below is an example to crash a 32-bit PostgreSQL:
       SELECT ((-2147483648)::int4) % ((-1)::int2);

Portability
===========

The previous fix uses #ifdef WIN32 ... #endif, which is not portable,
as noted below:

http://archives.postgresql.org/pgsql-patches/2006-06/msg00103.php

Using a SIGFPE handler is also dangerous (e.g., causing an infinite
loop sometimes):


https://www.securecoding.cert.org/confluence/display/seccode/SIG35-C.+Do+not+return+from+SIGSEGV,+SIGILL,+or+SIGFPE+signal+handlers

Strictly speaking, using postcondition checking to detect signed
division overflows (actually, all signed integer overflows) violates
the C language standard, because signed integer overflow is undefined
behavior in C and we cannot first compute the result and then check
for overflow.  Compilers can do a lot of funny and crazy things
(e.g., generating traps or even optimizing away overflow checks).

BTW, PostgreSQL currently uses gcc's workaround option -fwrapv to
disable offending optimizations based on integer overflows.  The
problems are: (1) it doesn't always work (e.g., for division), and
(2) many other C compilers do not even support this workaround
option and can perform offending optimizations.

Patching
========

Below is a patch that fixes division crashes.  It removes #ifdef WIN32
and tries to use portable checks.  I'll send more (e.g., for fixing
multiplication crashes) if this looks good.

I understand that the existing integer overflow checks tried to
avoid dependency on constants like INT64_MIN.  But I'm not sure how
to perform simpler and portable overflow checks without using such
constants.

Also, I could use the SHRT_MIN rather than introducing INT16_MIN; I just
feel like using INT16_MIN with int16 is clearer and less confusing.

diff --git a/src/backend/utils/adt/int.c b/src/backend/utils/adt/int.c
index 9f752ed..d7867cb 100644
--- a/src/backend/utils/adt/int.c
+++ b/src/backend/utils/adt/int.c
@@ -732,30 +732,18 @@ int4div(PG_FUNCTION_ARGS)        PG_RETURN_NULL();    }
-#ifdef WIN32
-    /*
-     * Win32 doesn't throw a catchable exception for SELECT -2147483648 /
-     * (-1); -- INT_MIN
+     * Overflow check.    The only possible overflow case is for arg1 =
+     * INT32_MIN, arg2 = -1, where the correct result is -INT32_MIN, which
+     * can't be represented on a two's-complement machine.     */
-    if (arg2 == -1 && arg1 == INT_MIN)
+    if (arg1 == INT32_MIN && arg2 == -1)        ereport(ERROR,
(errcode(ERRCODE_NUMERIC_VALUE_OUT_OF_RANGE),                errmsg("integer out of range")));
 
-#endif    result = arg1 / arg2;
-    /*
-     * Overflow check.    The only possible overflow case is for arg1 = INT_MIN,
-     * arg2 = -1, where the correct result is -INT_MIN, which can't be
-     * represented on a two's-complement machine.  Most machines produce
-     * INT_MIN but it seems some produce zero.
-     */
-    if (arg2 == -1 && arg1 < 0 && result <= 0)
-        ereport(ERROR,
-                (errcode(ERRCODE_NUMERIC_VALUE_OUT_OF_RANGE),
-                 errmsg("integer out of range")));    PG_RETURN_INT32(result);}
@@ -877,18 +865,17 @@ int2div(PG_FUNCTION_ARGS)        PG_RETURN_NULL();    }
-    result = arg1 / arg2;
-
-    /*
-     * Overflow check.    The only possible overflow case is for arg1 =
-     * SHRT_MIN, arg2 = -1, where the correct result is -SHRT_MIN, which can't
-     * be represented on a two's-complement machine.  Most machines produce
-     * SHRT_MIN but it seems some produce zero.
+    /* Overflow check.    The only possible overflow case is for arg1 =
+     * INT16_MIN, arg2 = -1, where the correct result is -INT16_MIN, which
+     * can't be represented on a two's-complement machine.     */
-    if (arg2 == -1 && arg1 < 0 && result <= 0)
+    if (arg1 == INT16_MIN && arg2 == -1)        ereport(ERROR,
(errcode(ERRCODE_NUMERIC_VALUE_OUT_OF_RANGE),                errmsg("smallint out of range")));
 
+
+    result = arg1 / arg2;
+    PG_RETURN_INT16(result);}
@@ -1065,18 +1052,18 @@ int42div(PG_FUNCTION_ARGS)        PG_RETURN_NULL();    }
-    result = arg1 / arg2;
-    /*
-     * Overflow check.    The only possible overflow case is for arg1 = INT_MIN,
-     * arg2 = -1, where the correct result is -INT_MIN, which can't be
-     * represented on a two's-complement machine.  Most machines produce
-     * INT_MIN but it seems some produce zero.
+     * Overflow check.    The only possible overflow case is for arg1 =
+     * INT32_MIN, arg2 = -1, where the correct result is -INT32_MIN, which
+     * can't be represented on a two's-complement machine.     */
-    if (arg2 == -1 && arg1 < 0 && result <= 0)
+    if (arg1 == INT32_MIN && arg2 == -1)        ereport(ERROR,
(errcode(ERRCODE_NUMERIC_VALUE_OUT_OF_RANGE),                errmsg("integer out of range")));
 
+
+    result = arg1 / arg2;
+    PG_RETURN_INT32(result);}
diff --git a/src/backend/utils/adt/int8.c b/src/backend/utils/adt/int8.c
index 59c110b..83531ad 100644
--- a/src/backend/utils/adt/int8.c
+++ b/src/backend/utils/adt/int8.c
@@ -598,18 +598,18 @@ int8div(PG_FUNCTION_ARGS)        PG_RETURN_NULL();    }
-    result = arg1 / arg2;
-    /*     * Overflow check.    The only possible overflow case is for arg1 =     * INT64_MIN, arg2 = -1, where the
correctresult is -INT64_MIN, which
 
-     * can't be represented on a two's-complement machine.    Most machines
-     * produce INT64_MIN but it seems some produce zero.
+     * can't be represented on a two's-complement machine.     */
-    if (arg2 == -1 && arg1 < 0 && result <= 0)
+    if (arg1 == INT64_MIN && arg2 == -1)        ereport(ERROR,
(errcode(ERRCODE_NUMERIC_VALUE_OUT_OF_RANGE),                errmsg("bigint out of range")));
 
+
+    result = arg1 / arg2;
+    PG_RETURN_INT64(result);}
@@ -838,18 +838,18 @@ int84div(PG_FUNCTION_ARGS)        PG_RETURN_NULL();    }
-    result = arg1 / arg2;
-    /*     * Overflow check.    The only possible overflow case is for arg1 =     * INT64_MIN, arg2 = -1, where the
correctresult is -INT64_MIN, which
 
-     * can't be represented on a two's-complement machine.    Most machines
-     * produce INT64_MIN but it seems some produce zero.
+     * can't be represented on a two's-complement machine.     */
-    if (arg2 == -1 && arg1 < 0 && result <= 0)
+    if (arg1 == INT64_MIN && arg2 == -1)        ereport(ERROR,
(errcode(ERRCODE_NUMERIC_VALUE_OUT_OF_RANGE),                errmsg("bigint out of range")));
 
+
+    result = arg1 / arg2;
+    PG_RETURN_INT64(result);}
@@ -1026,18 +1026,18 @@ int82div(PG_FUNCTION_ARGS)        PG_RETURN_NULL();    }
-    result = arg1 / arg2;
-    /*     * Overflow check.    The only possible overflow case is for arg1 =     * INT64_MIN, arg2 = -1, where the
correctresult is -INT64_MIN, which
 
-     * can't be represented on a two's-complement machine.    Most machines
-     * produce INT64_MIN but it seems some produce zero.
+     * can't be represented on a two's-complement machine.     */
-    if (arg2 == -1 && arg1 < 0 && result <= 0)
+    if (arg1 == INT64_MIN && arg2 == -1)        ereport(ERROR,
(errcode(ERRCODE_NUMERIC_VALUE_OUT_OF_RANGE),                errmsg("bigint out of range")));
 
+
+    result = arg1 / arg2;
+    PG_RETURN_INT64(result);}
diff --git a/src/include/c.h b/src/include/c.h
index a6c0e6e..547a188 100644
--- a/src/include/c.h
+++ b/src/include/c.h
@@ -294,6 +294,29 @@ typedef unsigned long long int uint64;#define UINT64CONST(x) ((uint64) x)#endif
+#ifndef INT16_MAX
+#define INT16_MAX 32767
+#endif
+
+#ifndef INT16_MIN
+#define INT16_MIN (-INT16_MAX-1)
+#endif
+
+#ifndef INT32_MAX
+#define INT32_MAX 2147483647
+#endif
+
+#ifndef INT32_MIN
+#define INT32_MIN (-INT32_MAX-1)
+#endif
+
+#ifndef INT64_MAX
+#define INT64_MAX INT64CONST(9223372036854775807)
+#endif
+
+#ifndef INT64_MIN
+#define INT64_MIN (-INT64_MAX-1)
+#endif/* Select timestamp representation (float8 or int64) */#ifdef USE_INTEGER_DATETIMES

Xi Wang <xi.wang@gmail.com> writes:
> [ patch adding a bunch of explicit INT_MIN/MAX constants ]

I was against this style of coding before, and I still am.
For one thing, it's just about certain to introduce conflicts
against system headers.
        regards, tom lane

On 11/18/12 6:47 PM, Tom Lane wrote:
> Xi Wang <xi.wang@gmail.com> writes:
>> [ patch adding a bunch of explicit INT_MIN/MAX constants ]
> 
> I was against this style of coding before, and I still am.
> For one thing, it's just about certain to introduce conflicts
> against system headers.

I totally agree.

I would be happy to rewrite the integer overflow checks without
using these explicit constants, but it seems extremely tricky to
do so.  One possible check without using INTn_MIN is:
if (arg1 < 0 && -arg1 < 0 && arg2 == -1) { ... }

Compared to (arg1 == INTn_MIN && arg2 == -1), the above check is
not only more confusing and difficult to understand, but it also
invokes undefined behavior (-INT_MIN overflow), which is dangerous:
many C compilers will optimize away the check.  I've tried gcc,
clang, PathScale, and AMD's Open64, all of which perform such
optimizations.

Since INTn_MIN and INTn_MAX are standard macros from the C library,
can we assume that every C compiler should provide them in stdint.h?
At least this is true for gcc, clang, and Visual C++.  Then we don't
have to define them and worry about possible conflicts (though I
think using #ifndef...#endif should be able to avoid conflicts).

- xi

Xi Wang <xi.wang@gmail.com> writes:
> On 11/18/12 6:47 PM, Tom Lane wrote:
>> I was against this style of coding before, and I still am.
>> For one thing, it's just about certain to introduce conflicts
>> against system headers.

> I totally agree.

> I would be happy to rewrite the integer overflow checks without
> using these explicit constants, but it seems extremely tricky to
> do so.

I thought about this some more and realized that we can handle it
by realizing that division by -1 is the same as negation, and so
we can copy the method used in int4um.  So the code would look like
if (arg2 == -1){    result = -arg1;    if (arg1 != 0 && SAMESIGN(result, arg1))        ereport(ERROR, ...);
PG_RETURN_INT32(result);}

(with rather more comments than this, of course).  This looks faster
than what's there now, as well as removing the need for use of
explicit INT_MIN constants.

> Compared to (arg1 == INTn_MIN && arg2 == -1), the above check is
> not only more confusing and difficult to understand, but it also
> invokes undefined behavior (-INT_MIN overflow), which is dangerous:
> many C compilers will optimize away the check.

They'd better not, else they'll break many of our overflow checks.
This is why we use -fwrapv with gcc, for example.  Any other compiler
with similar optimizations needs to be invoked with a similar switch.

> Since INTn_MIN and INTn_MAX are standard macros from the C library,
> can we assume that every C compiler should provide them in stdint.h?

Not every C compiler provides stdint.h, unfortunately --- otherwise
I'd not be so resistant to depending on this.
        regards, tom lane

On 11/19/12 11:04 AM, Tom Lane wrote:
> I thought about this some more and realized that we can handle it
> by realizing that division by -1 is the same as negation, and so
> we can copy the method used in int4um.  So the code would look like
> 
>     if (arg2 == -1)
>     {
>         result = -arg1;
>         if (arg1 != 0 && SAMESIGN(result, arg1))
>             ereport(ERROR, ...);
>         PG_RETURN_INT32(result);
>     }
> 
> (with rather more comments than this, of course).  This looks faster
> than what's there now, as well as removing the need for use of
> explicit INT_MIN constants.

Hah, I used exactly the same code in my initial patch. :)

See below.

> They'd better not, else they'll break many of our overflow checks.
> This is why we use -fwrapv with gcc, for example.  Any other compiler
> with similar optimizations needs to be invoked with a similar switch.

Yes, that's the scary part.

Even with -fwrapv in gcc (I tried 4.6/4.7/4.8), it still optimizes away
my overflow check!
if (arg1 < 0 && -arg1 < 0) { ... }

Fortunately, it doesn't optimize way checks using SAMESIGN() for now.
Who knows what could happen in the next version..

Clang's -fwrapv works as expected.

PathScale and Open64 (and probably icc) don't support -fwrapv at all.
Not sure if they have similar options.  They do such optimizations, too.

The reality is that C compilers are not friendly to postcondition
checking; they consider signed integer overflow as undefined behavior,
so they do whatever they want to do.  Even workaround options like
-fwrapv are often broken, not to mention that they may not even have
those options.

That's why I am suggesting to avoid postcondition checking for signed
integer overflow.

> Not every C compiler provides stdint.h, unfortunately --- otherwise
> I'd not be so resistant to depending on this.

Sigh..  You are right.

- xi

Xi Wang <xi.wang@gmail.com> writes:
> The reality is that C compilers are not friendly to postcondition
> checking; they consider signed integer overflow as undefined behavior,
> so they do whatever they want to do.  Even workaround options like
> -fwrapv are often broken, not to mention that they may not even have
> those options.

I think it's probably past time that we stopped guessing about this
sort of thing and added some regression test cases for it.  I'm
planning to add cases like this:

-- check sane handling of INT_MIN overflow cases
SELECT (-2147483648)::int4 * (-1)::int4;
SELECT (-2147483648)::int4 / (-1)::int4;
SELECT (-2147483648)::int4 % (-1)::int4;
        regards, tom lane

On 2012-11-19 11:04:31 -0500, Tom Lane wrote:
> Xi Wang <xi.wang@gmail.com> writes:
> > Since INTn_MIN and INTn_MAX are standard macros from the C library,
> > can we assume that every C compiler should provide them in stdint.h?
>
> Not every C compiler provides stdint.h, unfortunately --- otherwise
> I'd not be so resistant to depending on this.

We already have hardcoded values for INT64_MIN in numutils.c's
pg_lltoa(). Given that I think we could just bite the apple and provide
our own values if the platform doesn't provide them.

Greetings,

Andres Freund