Allow btree comparison functions to return INT_MIN.

Historically we forbade datatype-specific comparison functions from
returning INT_MIN, so that it would be safe to invert the sort order
just by negating the comparison result.  However, this was never
really safe for comparison functions that directly return the result
of memcmp(), strcmp(), etc, as POSIX doesn't place any such restriction
on those library functions.  Buildfarm results show that at least on
recent Linux on s390x, memcmp() actually does return INT_MIN sometimes,
causing sort failures.

The agreed-on answer is to remove this restriction and fix relevant
call sites to not make such an assumption; code such as "res = -res"
should be replaced by "INVERT_COMPARE_RESULT(res)".  The same is needed
in a few places that just directly negated the result of memcmp or
strcmp.

To help find places having this problem, I've also added a compile option
to nbtcompare.c that causes some of the commonly used comparators to
return INT_MIN/INT_MAX instead of their usual -1/+1.  It'd likely be
a good idea to have at least one buildfarm member running with
"-DSTRESS_SORT_INT_MIN".  That's far from a complete test of course,
but it should help to prevent fresh introductions of such bugs.

This is a longstanding portability hazard, so back-patch to all supported
branches.

Discussion: https://postgr.es/m/20180928185215.ffoq2xrq5d3pafna@alap3.anarazel.de

diff --git a/contrib/ltree/ltree_op.c b/contrib/ltree/ltree_op.c
index cb59d21ced4a7916f5c8fdcf16bf4635bcd22a85..d1067f8146567beee33990fa7f3b2ee85d3115de 100644 (file)
--- a/contrib/ltree/ltree_op.c
+++ b/contrib/ltree/ltree_op.c
@@ -45,17 +45,24 @@ ltree_compare(const ltree *a, const ltree *b)
    ltree_level *bl = LTREE_FIRST(b);
    int         an = a->numlevel;
    int         bn = b->numlevel;
-   int         res = 0;
 
    while (an > 0 && bn > 0)
    {
+       int         res;
+
        if ((res = memcmp(al->name, bl->name, Min(al->len, bl->len))) == 0)
        {
            if (al->len != bl->len)
                return (al->len - bl->len) * 10 * (an + 1);
        }
        else
+       {
+           if (res < 0)
+               res = -1;
+           else
+               res = 1;
            return res * 10 * (an + 1);
+       }
 
        an--;
        bn--;
@@ -146,7 +153,7 @@ inner_isparent(const ltree *c, const ltree *p)
    {
        if (cl->len != pl->len)
            return false;
-       if (memcmp(cl->name, pl->name, cl->len))
+       if (memcmp(cl->name, pl->name, cl->len) != 0)
            return false;
 
        pn--;

diff --git a/contrib/pgcrypto/imath.c b/contrib/pgcrypto/imath.c
index 61a01e2b71002e16fb0a27bc6201dd041f6a55cd..6449dd34b0b524b89887ca7b13be1aefc075894e 100644 (file)
--- a/contrib/pgcrypto/imath.c
+++ b/contrib/pgcrypto/imath.c
@@ -1254,11 +1254,9 @@ mp_int_compare(mp_int a, mp_int b)
         * If they're both zero or positive, the normal comparison applies; if
         * both negative, the sense is reversed.
         */
-       if (sa == MP_ZPOS)
-           return cmp;
-       else
-           return -cmp;
-
+       if (sa != MP_ZPOS)
+           INVERT_COMPARE_RESULT(cmp);
+       return cmp;
    }
    else
    {
@@ -1314,10 +1312,9 @@ mp_int_compare_value(mp_int z, int value)
    {
        cmp = s_vcmp(z, value);
 
-       if (vsign == MP_ZPOS)
-           return cmp;
-       else
-           return -cmp;
+       if (vsign != MP_ZPOS)
+           INVERT_COMPARE_RESULT(cmp);
+       return cmp;
    }
    else
    {

diff --git a/src/backend/access/nbtree/nbtcompare.c b/src/backend/access/nbtree/nbtcompare.c
index b1f9ae36850f73aff1237cdb639cb11f1e9cf45c..88e07e1bf87324366fa4ab00e8872b8f70df5983 100644 (file)
--- a/src/backend/access/nbtree/nbtcompare.c
+++ b/src/backend/access/nbtree/nbtcompare.c
@@ -22,11 +22,10 @@
  *
  * The result is always an int32 regardless of the input datatype.
  *
- * Although any negative int32 (except INT_MIN) is acceptable for reporting
- * "<", and any positive int32 is acceptable for reporting ">", routines
+ * Although any negative int32 is acceptable for reporting "<",
+ * and any positive int32 is acceptable for reporting ">", routines
  * that work on 32-bit or wider datatypes can't just return "a - b".
- * That could overflow and give the wrong answer.  Also, one must not
- * return INT_MIN to report "<", since some callers will negate the result.
+ * That could overflow and give the wrong answer.
  *
  * NOTE: it is critical that the comparison function impose a total order
  * on all non-NULL values of the data type, and that the datatype's
@@ -44,13 +43,31 @@
  * during an index access won't be recovered till end of query.  This
  * primarily affects comparison routines for toastable datatypes;
  * they have to be careful to free any detoasted copy of an input datum.
+ *
+ * NOTE: we used to forbid comparison functions from returning INT_MIN,
+ * but that proves to be too error-prone because some platforms' versions
+ * of memcmp() etc can return INT_MIN.  As a means of stress-testing
+ * callers, this file can be compiled with STRESS_SORT_INT_MIN defined
+ * to cause many of these functions to return INT_MIN or INT_MAX instead of
+ * their customary -1/+1.  For production, though, that's not a good idea
+ * since users or third-party code might expect the traditional results.
  *-------------------------------------------------------------------------
  */
 #include "postgres.h"
 
+#include <limits.h>
+
 #include "utils/builtins.h"
 #include "utils/sortsupport.h"
 
+#ifdef STRESS_SORT_INT_MIN
+#define A_LESS_THAN_B      INT_MIN
+#define A_GREATER_THAN_B   INT_MAX
+#else
+#define A_LESS_THAN_B      (-1)
+#define A_GREATER_THAN_B   1
+#endif
+
 
 Datum
 btboolcmp(PG_FUNCTION_ARGS)
@@ -95,11 +112,11 @@ btint4cmp(PG_FUNCTION_ARGS)
    int32       b = PG_GETARG_INT32(1);
 
    if (a > b)
-       PG_RETURN_INT32(1);
+       PG_RETURN_INT32(A_GREATER_THAN_B);
    else if (a == b)
        PG_RETURN_INT32(0);
    else
-       PG_RETURN_INT32(-1);
+       PG_RETURN_INT32(A_LESS_THAN_B);
 }
 
 static int
@@ -109,11 +126,11 @@ btint4fastcmp(Datum x, Datum y, SortSupport ssup)
    int32       b = DatumGetInt32(y);
 
    if (a > b)
-       return 1;
+       return A_GREATER_THAN_B;
    else if (a == b)
        return 0;
    else
-       return -1;
+       return A_LESS_THAN_B;
 }
 
 Datum
@@ -132,11 +149,11 @@ btint8cmp(PG_FUNCTION_ARGS)
    int64       b = PG_GETARG_INT64(1);
 
    if (a > b)
-       PG_RETURN_INT32(1);
+       PG_RETURN_INT32(A_GREATER_THAN_B);
    else if (a == b)
        PG_RETURN_INT32(0);
    else
-       PG_RETURN_INT32(-1);
+       PG_RETURN_INT32(A_LESS_THAN_B);
 }
 
 static int
@@ -146,11 +163,11 @@ btint8fastcmp(Datum x, Datum y, SortSupport ssup)
    int64       b = DatumGetInt64(y);
 
    if (a > b)
-       return 1;
+       return A_GREATER_THAN_B;
    else if (a == b)
        return 0;
    else
-       return -1;
+       return A_LESS_THAN_B;
 }
 
 Datum
@@ -169,11 +186,11 @@ btint48cmp(PG_FUNCTION_ARGS)
    int64       b = PG_GETARG_INT64(1);
 
    if (a > b)
-       PG_RETURN_INT32(1);
+       PG_RETURN_INT32(A_GREATER_THAN_B);
    else if (a == b)
        PG_RETURN_INT32(0);
    else
-       PG_RETURN_INT32(-1);
+       PG_RETURN_INT32(A_LESS_THAN_B);
 }
 
 Datum
@@ -183,11 +200,11 @@ btint84cmp(PG_FUNCTION_ARGS)
    int32       b = PG_GETARG_INT32(1);
 
    if (a > b)
-       PG_RETURN_INT32(1);
+       PG_RETURN_INT32(A_GREATER_THAN_B);
    else if (a == b)
        PG_RETURN_INT32(0);
    else
-       PG_RETURN_INT32(-1);
+       PG_RETURN_INT32(A_LESS_THAN_B);
 }
 
 Datum
@@ -197,11 +214,11 @@ btint24cmp(PG_FUNCTION_ARGS)
    int32       b = PG_GETARG_INT32(1);
 
    if (a > b)
-       PG_RETURN_INT32(1);
+       PG_RETURN_INT32(A_GREATER_THAN_B);
    else if (a == b)
        PG_RETURN_INT32(0);
    else
-       PG_RETURN_INT32(-1);
+       PG_RETURN_INT32(A_LESS_THAN_B);
 }
 
 Datum
@@ -211,11 +228,11 @@ btint42cmp(PG_FUNCTION_ARGS)
    int16       b = PG_GETARG_INT16(1);
 
    if (a > b)
-       PG_RETURN_INT32(1);
+       PG_RETURN_INT32(A_GREATER_THAN_B);
    else if (a == b)
        PG_RETURN_INT32(0);
    else
-       PG_RETURN_INT32(-1);
+       PG_RETURN_INT32(A_LESS_THAN_B);
 }
 
 Datum
@@ -225,11 +242,11 @@ btint28cmp(PG_FUNCTION_ARGS)
    int64       b = PG_GETARG_INT64(1);
 
    if (a > b)
-       PG_RETURN_INT32(1);
+       PG_RETURN_INT32(A_GREATER_THAN_B);
    else if (a == b)
        PG_RETURN_INT32(0);
    else
-       PG_RETURN_INT32(-1);
+       PG_RETURN_INT32(A_LESS_THAN_B);
 }
 
 Datum
@@ -239,11 +256,11 @@ btint82cmp(PG_FUNCTION_ARGS)
    int16       b = PG_GETARG_INT16(1);
 
    if (a > b)
-       PG_RETURN_INT32(1);
+       PG_RETURN_INT32(A_GREATER_THAN_B);
    else if (a == b)
        PG_RETURN_INT32(0);
    else
-       PG_RETURN_INT32(-1);
+       PG_RETURN_INT32(A_LESS_THAN_B);
 }
 
 Datum
@@ -253,11 +270,11 @@ btoidcmp(PG_FUNCTION_ARGS)
    Oid         b = PG_GETARG_OID(1);
 
    if (a > b)
-       PG_RETURN_INT32(1);
+       PG_RETURN_INT32(A_GREATER_THAN_B);
    else if (a == b)
        PG_RETURN_INT32(0);
    else
-       PG_RETURN_INT32(-1);
+       PG_RETURN_INT32(A_LESS_THAN_B);
 }
 
 static int
@@ -267,11 +284,11 @@ btoidfastcmp(Datum x, Datum y, SortSupport ssup)
    Oid         b = DatumGetObjectId(y);
 
    if (a > b)
-       return 1;
+       return A_GREATER_THAN_B;
    else if (a == b)
        return 0;
    else
-       return -1;
+       return A_LESS_THAN_B;
 }
 
 Datum
@@ -299,9 +316,9 @@ btoidvectorcmp(PG_FUNCTION_ARGS)
        if (a->values[i] != b->values[i])
        {
            if (a->values[i] > b->values[i])
-               PG_RETURN_INT32(1);
+               PG_RETURN_INT32(A_GREATER_THAN_B);
            else
-               PG_RETURN_INT32(-1);
+               PG_RETURN_INT32(A_LESS_THAN_B);
        }
    }
    PG_RETURN_INT32(0);

diff --git a/src/backend/access/nbtree/nbtsearch.c b/src/backend/access/nbtree/nbtsearch.c
index 203b9691baa2d834d108428482d2e9152d343679..dfdc8945594e1f81b29e389250b04f16d081faa2 100644 (file)
--- a/src/backend/access/nbtree/nbtsearch.c
+++ b/src/backend/access/nbtree/nbtsearch.c
@@ -453,7 +453,7 @@ _bt_compare(Relation rel,
                                                     scankey->sk_argument));
 
            if (!(scankey->sk_flags & SK_BT_DESC))
-               result = -result;
+               INVERT_COMPARE_RESULT(result);
        }
 
        /* if the keys are unequal, return the difference */

diff --git a/src/backend/access/nbtree/nbtsort.c b/src/backend/access/nbtree/nbtsort.c
index 1281a120c560b01e1b61ee7dcc011b580a7b18d3..5a74f9b1b8462739a611435cd2b8a575d976db1a 100644 (file)
--- a/src/backend/access/nbtree/nbtsort.c
+++ b/src/backend/access/nbtree/nbtsort.c
@@ -746,7 +746,7 @@ _bt_load(BTWriteState *wstate, BTSpool *btspool, BTSpool *btspool2)
                                                            attrDatum2));
 
                        if (entry->sk_flags & SK_BT_DESC)
-                           compare = -compare;
+                           INVERT_COMPARE_RESULT(compare);
                    }
                    if (compare > 0)
                    {

diff --git a/src/backend/access/nbtree/nbtutils.c b/src/backend/access/nbtree/nbtutils.c
index 5ed732e2fe9e2356727c367bdbfa419b7967c956..05a4d3c374ea9fecbb3946dcdb0bf98d5e0ea778 100644 (file)
--- a/src/backend/access/nbtree/nbtutils.c
+++ b/src/backend/access/nbtree/nbtutils.c
@@ -509,7 +509,7 @@ _bt_compare_array_elements(const void *a, const void *b, void *arg)
                                              cxt->collation,
                                              da, db));
    if (cxt->reverse)
-       compare = -compare;
+       INVERT_COMPARE_RESULT(compare);
    return compare;
 }
 
@@ -1638,7 +1638,7 @@ _bt_check_rowcompare(ScanKey skey, IndexTuple tuple, TupleDesc tupdesc,
                                                    subkey->sk_argument));
 
        if (subkey->sk_flags & SK_BT_DESC)
-           cmpresult = -cmpresult;
+           INVERT_COMPARE_RESULT(cmpresult);
 
        /* Done comparing if unequal, else advance to next column */
        if (cmpresult != 0)

diff --git a/src/backend/executor/nodeMergeAppend.c b/src/backend/executor/nodeMergeAppend.c
index 47ed068c7b71fe235d36c52a5c19e44b238b12f7..a32d66ca766d33545a4bb003ee737e4d50a9eb14 100644 (file)
--- a/src/backend/executor/nodeMergeAppend.c
+++ b/src/backend/executor/nodeMergeAppend.c
@@ -241,7 +241,10 @@ heap_compare_slots(Datum a, Datum b, void *arg)
                                      datum2, isNull2,
                                      sortKey);
        if (compare != 0)
-           return -compare;
+       {
+           INVERT_COMPARE_RESULT(compare);
+           return compare;
+       }
    }
    return 0;
 }

diff --git a/src/backend/utils/sort/tuplesort.c b/src/backend/utils/sort/tuplesort.c
index 9b61a893ca1396447d3a4616604870f2441be726..2cf713eb63eb5737c36e35df92b75032563c4044 100644 (file)
--- a/src/backend/utils/sort/tuplesort.c
+++ b/src/backend/utils/sort/tuplesort.c
@@ -2849,7 +2849,7 @@ inlineApplySortFunction(FmgrInfo *sortFunction, int sk_flags, Oid collation,
                                                    datum1, datum2));
 
        if (sk_flags & SK_BT_DESC)
-           compare = -compare;
+           INVERT_COMPARE_RESULT(compare);
    }
 
    return compare;

diff --git a/src/include/access/nbtree.h b/src/include/access/nbtree.h
index 09708c01c810ac63d704565c61ad955ab939612f..61f4574948d388a8f7f8d09a00ac55f11c96561e 100644 (file)
--- a/src/include/access/nbtree.h
+++ b/src/include/access/nbtree.h
@@ -449,8 +449,7 @@ typedef struct xl_btree_newroot
  * When a new operator class is declared, we require that the user
  * supply us with an amproc procedure (BTORDER_PROC) for determining
  * whether, for two keys a and b, a < b, a = b, or a > b.  This routine
- * must return < 0, 0, > 0, respectively, in these three cases.  (It must
- * not return INT_MIN, since we may negate the result before using it.)
+ * must return < 0, 0, > 0, respectively, in these three cases.
  *
  * To facilitate accelerated sorting, an operator class may choose to
  * offer a second procedure (BTSORTSUPPORT_PROC).  For full details, see

diff --git a/src/include/c.h b/src/include/c.h
index 6836b0a0f56828c2d867b97f259ddf6780f5e6f1..aad18a7c65149678b851c2913361859f0faa5a66 100644 (file)
--- a/src/include/c.h
+++ b/src/include/c.h
@@ -867,6 +867,14 @@ typedef NameData *Name;
  * ----------------------------------------------------------------
  */
 
+/*
+ * Invert the sign of a qsort-style comparison result, ie, exchange negative
+ * and positive integer values, being careful not to get the wrong answer
+ * for INT_MIN.  The argument should be an integral variable.
+ */
+#define INVERT_COMPARE_RESULT(var) \
+   ((var) = ((var) < 0) ? 1 : -(var))
+
 /*
  * Use this, not "char buf[BLCKSZ]", to declare a field or local variable
  * holding a page buffer, if that page might be accessed as a page and not

diff --git a/src/include/utils/sortsupport.h b/src/include/utils/sortsupport.h
index 8b6b0de2e8b606754ef7bbf3cbe1c562f80c2c29..2e4dba334d2a9a57e859cb832a6eac7cebc74c97 100644 (file)
--- a/src/include/utils/sortsupport.h
+++ b/src/include/utils/sortsupport.h
@@ -90,8 +90,7 @@ typedef struct SortSupportData
     * Comparator function has the same API as the traditional btree
     * comparison function, ie, return <0, 0, or >0 according as x is less
     * than, equal to, or greater than y.  Note that x and y are guaranteed
-    * not null, and there is no way to return null either.  Do not return
-    * INT_MIN, as callers are allowed to negate the result before using it.
+    * not null, and there is no way to return null either.
     */
    int         (*comparator) (Datum x, Datum y, SortSupport ssup);
 
@@ -142,7 +141,7 @@ ApplySortComparator(Datum datum1, bool isNull1,
    {
        compare = (*ssup->comparator) (datum1, datum2, ssup);
        if (ssup->ssup_reverse)
-           compare = -compare;
+           INVERT_COMPARE_RESULT(compare);
    }
 
    return compare;