From 67e7d4da72dca6525fd2b9a2f2522994040897ba Mon Sep 17 00:00:00 2001 From: Tom Lane Date: Fri, 5 Oct 2018 16:01:29 -0400 Subject: [PATCH] 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 --- contrib/ltree/ltree_op.c | 11 +++- contrib/pgcrypto/imath.c | 15 ++--- doc/src/sgml/btree.sgml | 7 +-- src/backend/access/nbtree/nbtcompare.c | 77 ++++++++++++++++---------- src/backend/access/nbtree/nbtsearch.c | 2 +- src/backend/access/nbtree/nbtutils.c | 4 +- src/backend/executor/nodeGatherMerge.c | 5 +- src/backend/executor/nodeIndexscan.c | 7 ++- src/backend/executor/nodeMergeAppend.c | 5 +- src/bin/pg_rewind/filemap.c | 2 +- src/include/access/nbtree.h | 3 +- src/include/c.h | 8 +++ src/include/utils/sortsupport.h | 7 +-- 13 files changed, 92 insertions(+), 61 deletions(-) diff --git a/contrib/ltree/ltree_op.c b/contrib/ltree/ltree_op.c index 759f1f8d29..df61c63180 100644 --- 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 cd528bfd83..b94a51b81a 100644 --- 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/doc/src/sgml/btree.sgml b/doc/src/sgml/btree.sgml index 8bd0badb28..c16825e2ea 100644 --- a/doc/src/sgml/btree.sgml +++ b/doc/src/sgml/btree.sgml @@ -228,11 +228,8 @@ B, A = B, or A > - B, respectively. The function must not - return INT_MIN for the A - < B case, - since the value may be negated before being tested for sign. A null - result is disallowed, too. + B, respectively. + A null result is disallowed: all values of the data type must be comparable. See src/backend/access/nbtree/nbtcompare.c for examples. diff --git a/src/backend/access/nbtree/nbtcompare.c b/src/backend/access/nbtree/nbtcompare.c index b1855e8aa8..6f2ad23b5d 100644 --- 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 + #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 6831bc8c03..6971096329 100644 --- a/src/backend/access/nbtree/nbtsearch.c +++ b/src/backend/access/nbtree/nbtsearch.c @@ -500,7 +500,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/nbtutils.c b/src/backend/access/nbtree/nbtutils.c index 4528e87c83..205457ef99 100644 --- a/src/backend/access/nbtree/nbtutils.c +++ b/src/backend/access/nbtree/nbtutils.c @@ -518,7 +518,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; } @@ -1652,7 +1652,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/nodeGatherMerge.c b/src/backend/executor/nodeGatherMerge.c index a0b3334bed..36cd299706 100644 --- a/src/backend/executor/nodeGatherMerge.c +++ b/src/backend/executor/nodeGatherMerge.c @@ -756,7 +756,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/executor/nodeIndexscan.c b/src/backend/executor/nodeIndexscan.c index 10891bc3f4..0dc760011d 100644 --- a/src/backend/executor/nodeIndexscan.c +++ b/src/backend/executor/nodeIndexscan.c @@ -469,9 +469,10 @@ reorderqueue_cmp(const pairingheap_node *a, const pairingheap_node *b, ReorderTuple *rtb = (ReorderTuple *) b; IndexScanState *node = (IndexScanState *) arg; - return -cmp_orderbyvals(rta->orderbyvals, rta->orderbynulls, - rtb->orderbyvals, rtb->orderbynulls, - node); + /* exchange argument order to invert the sort order */ + return cmp_orderbyvals(rtb->orderbyvals, rtb->orderbynulls, + rta->orderbyvals, rta->orderbynulls, + node); } /* diff --git a/src/backend/executor/nodeMergeAppend.c b/src/backend/executor/nodeMergeAppend.c index 118f4ef07d..8dd05c1f85 100644 --- a/src/backend/executor/nodeMergeAppend.c +++ b/src/backend/executor/nodeMergeAppend.c @@ -257,7 +257,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/bin/pg_rewind/filemap.c b/src/bin/pg_rewind/filemap.c index 4ad7b2f207..222b56f58a 100644 --- a/src/bin/pg_rewind/filemap.c +++ b/src/bin/pg_rewind/filemap.c @@ -810,7 +810,7 @@ final_filemap_cmp(const void *a, const void *b) return -1; if (fa->action == FILE_ACTION_REMOVE) - return -strcmp(fa->path, fb->path); + return strcmp(fb->path, fa->path); else return strcmp(fa->path, fb->path); } diff --git a/src/include/access/nbtree.h b/src/include/access/nbtree.h index 04ecb4cbc0..ea495f1724 100644 --- a/src/include/access/nbtree.h +++ b/src/include/access/nbtree.h @@ -274,8 +274,7 @@ typedef struct BTMetaPageData * 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 901d791198..6b5e71782b 100644 --- a/src/include/c.h +++ b/src/include/c.h @@ -989,6 +989,14 @@ extern void ExceptionalCondition(const char *conditionName, * ---------------------------------------------------------------- */ +/* + * 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 53b692e9a2..818e0b1843 100644 --- a/src/include/utils/sortsupport.h +++ b/src/include/utils/sortsupport.h @@ -96,8 +96,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. * * This may be either the authoritative comparator, or the abbreviated * comparator. Core code may switch this over the initial preference of @@ -224,7 +223,7 @@ ApplySortComparator(Datum datum1, bool isNull1, { compare = ssup->comparator(datum1, datum2, ssup); if (ssup->ssup_reverse) - compare = -compare; + INVERT_COMPARE_RESULT(compare); } return compare; @@ -262,7 +261,7 @@ ApplySortAbbrevFullComparator(Datum datum1, bool isNull1, { compare = ssup->abbrev_full_comparator(datum1, datum2, ssup); if (ssup->ssup_reverse) - compare = -compare; + INVERT_COMPARE_RESULT(compare); } return compare; -- 2.40.0