Skip to content

Commit c87cb5f

Browse files
tglsfdctglsfdc
committed
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
1 parent 113a659 commit c87cb5f

File tree

13 files changed

+92
-61
lines changed

13 files changed

+92
-61
lines changed

‎contrib/ltree/ltree_op.c

Lines changed: 9 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -45,17 +45,24 @@ ltree_compare(const ltree *a, const ltree *b)
4545
ltree_level *bl = LTREE_FIRST(b);
4646
int an = a->numlevel;
4747
int bn = b->numlevel;
48-
int res = 0;
4948

5049
while (an > 0 && bn > 0)
5150
{
51+
int res;
52+
5253
if ((res = memcmp(al->name, bl->name, Min(al->len, bl->len))) == 0)
5354
{
5455
if (al->len != bl->len)
5556
return (al->len - bl->len) * 10 * (an + 1);
5657
}
5758
else
59+
{
60+
if (res < 0)
61+
res = -1;
62+
else
63+
res = 1;
5864
return res * 10 * (an + 1);
65+
}
5966

6067
an--;
6168
bn--;
@@ -146,7 +153,7 @@ inner_isparent(const ltree *c, const ltree *p)
146153
{
147154
if (cl->len != pl->len)
148155
return false;
149-
if (memcmp(cl->name, pl->name, cl->len))
156+
if (memcmp(cl->name, pl->name, cl->len) != 0)
150157
return false;
151158

152159
pn--;

‎contrib/pgcrypto/imath.c

Lines changed: 6 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1254,11 +1254,9 @@ mp_int_compare(mp_int a, mp_int b)
12541254
* If they're both zero or positive, the normal comparison applies; if
12551255
* both negative, the sense is reversed.
12561256
*/
1257-
if (sa == MP_ZPOS)
1258-
return cmp;
1259-
else
1260-
return -cmp;
1261-
1257+
if (sa != MP_ZPOS)
1258+
INVERT_COMPARE_RESULT(cmp);
1259+
return cmp;
12621260
}
12631261
else
12641262
{
@@ -1314,10 +1312,9 @@ mp_int_compare_value(mp_int z, int value)
13141312
{
13151313
cmp = s_vcmp(z, value);
13161314

1317-
if (vsign == MP_ZPOS)
1318-
return cmp;
1319-
else
1320-
return -cmp;
1315+
if (vsign != MP_ZPOS)
1316+
INVERT_COMPARE_RESULT(cmp);
1317+
return cmp;
13211318
}
13221319
else
13231320
{

‎doc/src/sgml/btree.sgml

Lines changed: 2 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -228,11 +228,8 @@
228228
<replaceable>B</replaceable>, <replaceable>A</replaceable>
229229
<literal>=</literal> <replaceable>B</replaceable>,
230230
or <replaceable>A</replaceable> <literal>&gt;</literal>
231-
<replaceable>B</replaceable>, respectively. The function must not
232-
return <literal>INT_MIN</literal> for the <replaceable>A</replaceable>
233-
<literal>&lt;</literal> <replaceable>B</replaceable> case,
234-
since the value may be negated before being tested for sign. A null
235-
result is disallowed, too.
231+
<replaceable>B</replaceable>, respectively.
232+
A null result is disallowed: all values of the data type must be comparable.
236233
See <filename>src/backend/access/nbtree/nbtcompare.c</filename> for
237234
examples.
238235
</para>

‎src/backend/access/nbtree/nbtcompare.c

Lines changed: 47 additions & 30 deletions
Original file line numberDiff line numberDiff line change
@@ -22,11 +22,10 @@
2222
*
2323
* The result is always an int32 regardless of the input datatype.
2424
*
25-
* Although any negative int32 (except INT_MIN) is acceptable for reporting
26-
* "<", and any positive int32 is acceptable for reporting ">", routines
25+
* Although any negative int32 is acceptable for reporting "<",
26+
* and any positive int32 is acceptable for reporting ">", routines
2727
* that work on 32-bit or wider datatypes can't just return "a - b".
28-
* That could overflow and give the wrong answer. Also, one must not
29-
* return INT_MIN to report "<", since some callers will negate the result.
28+
* That could overflow and give the wrong answer.
3029
*
3130
* NOTE: it is critical that the comparison function impose a total order
3231
* on all non-NULL values of the data type, and that the datatype's
@@ -44,13 +43,31 @@
4443
* during an index access won't be recovered till end of query. This
4544
* primarily affects comparison routines for toastable datatypes;
4645
* they have to be careful to free any detoasted copy of an input datum.
46+
*
47+
* NOTE: we used to forbid comparison functions from returning INT_MIN,
48+
* but that proves to be too error-prone because some platforms' versions
49+
* of memcmp() etc can return INT_MIN. As a means of stress-testing
50+
* callers, this file can be compiled with STRESS_SORT_INT_MIN defined
51+
* to cause many of these functions to return INT_MIN or INT_MAX instead of
52+
* their customary -1/+1. For production, though, that's not a good idea
53+
* since users or third-party code might expect the traditional results.
4754
*-------------------------------------------------------------------------
4855
*/
4956
#include "postgres.h"
5057

58+
#include <limits.h>
59+
5160
#include "utils/builtins.h"
5261
#include "utils/sortsupport.h"
5362

63+
#ifdef STRESS_SORT_INT_MIN
64+
#define A_LESS_THAN_B INT_MIN
65+
#define A_GREATER_THAN_B INT_MAX
66+
#else
67+
#define A_LESS_THAN_B (-1)
68+
#define A_GREATER_THAN_B 1
69+
#endif
70+
5471

5572
Datum
5673
btboolcmp(PG_FUNCTION_ARGS)
@@ -95,11 +112,11 @@ btint4cmp(PG_FUNCTION_ARGS)
95112
int32 b = PG_GETARG_INT32(1);
96113

97114
if (a > b)
98-
PG_RETURN_INT32(1);
115+
PG_RETURN_INT32(A_GREATER_THAN_B);
99116
else if (a == b)
100117
PG_RETURN_INT32(0);
101118
else
102-
PG_RETURN_INT32(-1);
119+
PG_RETURN_INT32(A_LESS_THAN_B);
103120
}
104121

105122
static int
@@ -109,11 +126,11 @@ btint4fastcmp(Datum x, Datum y, SortSupport ssup)
109126
int32 b = DatumGetInt32(y);
110127

111128
if (a > b)
112-
return 1;
129+
return A_GREATER_THAN_B;
113130
else if (a == b)
114131
return 0;
115132
else
116-
return -1;
133+
return A_LESS_THAN_B;
117134
}
118135

119136
Datum
@@ -132,11 +149,11 @@ btint8cmp(PG_FUNCTION_ARGS)
132149
int64 b = PG_GETARG_INT64(1);
133150

134151
if (a > b)
135-
PG_RETURN_INT32(1);
152+
PG_RETURN_INT32(A_GREATER_THAN_B);
136153
else if (a == b)
137154
PG_RETURN_INT32(0);
138155
else
139-
PG_RETURN_INT32(-1);
156+
PG_RETURN_INT32(A_LESS_THAN_B);
140157
}
141158

142159
static int
@@ -146,11 +163,11 @@ btint8fastcmp(Datum x, Datum y, SortSupport ssup)
146163
int64 b = DatumGetInt64(y);
147164

148165
if (a > b)
149-
return 1;
166+
return A_GREATER_THAN_B;
150167
else if (a == b)
151168
return 0;
152169
else
153-
return -1;
170+
return A_LESS_THAN_B;
154171
}
155172

156173
Datum
@@ -169,11 +186,11 @@ btint48cmp(PG_FUNCTION_ARGS)
169186
int64 b = PG_GETARG_INT64(1);
170187

171188
if (a > b)
172-
PG_RETURN_INT32(1);
189+
PG_RETURN_INT32(A_GREATER_THAN_B);
173190
else if (a == b)
174191
PG_RETURN_INT32(0);
175192
else
176-
PG_RETURN_INT32(-1);
193+
PG_RETURN_INT32(A_LESS_THAN_B);
177194
}
178195

179196
Datum
@@ -183,11 +200,11 @@ btint84cmp(PG_FUNCTION_ARGS)
183200
int32 b = PG_GETARG_INT32(1);
184201

185202
if (a > b)
186-
PG_RETURN_INT32(1);
203+
PG_RETURN_INT32(A_GREATER_THAN_B);
187204
else if (a == b)
188205
PG_RETURN_INT32(0);
189206
else
190-
PG_RETURN_INT32(-1);
207+
PG_RETURN_INT32(A_LESS_THAN_B);
191208
}
192209

193210
Datum
@@ -197,11 +214,11 @@ btint24cmp(PG_FUNCTION_ARGS)
197214
int32 b = PG_GETARG_INT32(1);
198215

199216
if (a > b)
200-
PG_RETURN_INT32(1);
217+
PG_RETURN_INT32(A_GREATER_THAN_B);
201218
else if (a == b)
202219
PG_RETURN_INT32(0);
203220
else
204-
PG_RETURN_INT32(-1);
221+
PG_RETURN_INT32(A_LESS_THAN_B);
205222
}
206223

207224
Datum
@@ -211,11 +228,11 @@ btint42cmp(PG_FUNCTION_ARGS)
211228
int16 b = PG_GETARG_INT16(1);
212229

213230
if (a > b)
214-
PG_RETURN_INT32(1);
231+
PG_RETURN_INT32(A_GREATER_THAN_B);
215232
else if (a == b)
216233
PG_RETURN_INT32(0);
217234
else
218-
PG_RETURN_INT32(-1);
235+
PG_RETURN_INT32(A_LESS_THAN_B);
219236
}
220237

221238
Datum
@@ -225,11 +242,11 @@ btint28cmp(PG_FUNCTION_ARGS)
225242
int64 b = PG_GETARG_INT64(1);
226243

227244
if (a > b)
228-
PG_RETURN_INT32(1);
245+
PG_RETURN_INT32(A_GREATER_THAN_B);
229246
else if (a == b)
230247
PG_RETURN_INT32(0);
231248
else
232-
PG_RETURN_INT32(-1);
249+
PG_RETURN_INT32(A_LESS_THAN_B);
233250
}
234251

235252
Datum
@@ -239,11 +256,11 @@ btint82cmp(PG_FUNCTION_ARGS)
239256
int16 b = PG_GETARG_INT16(1);
240257

241258
if (a > b)
242-
PG_RETURN_INT32(1);
259+
PG_RETURN_INT32(A_GREATER_THAN_B);
243260
else if (a == b)
244261
PG_RETURN_INT32(0);
245262
else
246-
PG_RETURN_INT32(-1);
263+
PG_RETURN_INT32(A_LESS_THAN_B);
247264
}
248265

249266
Datum
@@ -253,11 +270,11 @@ btoidcmp(PG_FUNCTION_ARGS)
253270
Oid b = PG_GETARG_OID(1);
254271

255272
if (a > b)
256-
PG_RETURN_INT32(1);
273+
PG_RETURN_INT32(A_GREATER_THAN_B);
257274
else if (a == b)
258275
PG_RETURN_INT32(0);
259276
else
260-
PG_RETURN_INT32(-1);
277+
PG_RETURN_INT32(A_LESS_THAN_B);
261278
}
262279

263280
static int
@@ -267,11 +284,11 @@ btoidfastcmp(Datum x, Datum y, SortSupport ssup)
267284
Oid b = DatumGetObjectId(y);
268285

269286
if (a > b)
270-
return 1;
287+
return A_GREATER_THAN_B;
271288
else if (a == b)
272289
return 0;
273290
else
274-
return -1;
291+
return A_LESS_THAN_B;
275292
}
276293

277294
Datum
@@ -299,9 +316,9 @@ btoidvectorcmp(PG_FUNCTION_ARGS)
299316
if (a->values[i] != b->values[i])
300317
{
301318
if (a->values[i] > b->values[i])
302-
PG_RETURN_INT32(1);
319+
PG_RETURN_INT32(A_GREATER_THAN_B);
303320
else
304-
PG_RETURN_INT32(-1);
321+
PG_RETURN_INT32(A_LESS_THAN_B);
305322
}
306323
}
307324
PG_RETURN_INT32(0);

‎src/backend/access/nbtree/nbtsearch.c

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -530,7 +530,7 @@ _bt_compare(Relation rel,
530530
scankey->sk_argument));
531531

532532
if (!(scankey->sk_flags & SK_BT_DESC))
533-
result = -result;
533+
INVERT_COMPARE_RESULT(result);
534534
}
535535

536536
/* if the keys are unequal, return the difference */

‎src/backend/access/nbtree/nbtutils.c

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -518,7 +518,7 @@ _bt_compare_array_elements(const void *a, const void *b, void *arg)
518518
cxt->collation,
519519
da, db));
520520
if (cxt->reverse)
521-
compare = -compare;
521+
INVERT_COMPARE_RESULT(compare);
522522
return compare;
523523
}
524524

@@ -1652,7 +1652,7 @@ _bt_check_rowcompare(ScanKey skey, IndexTuple tuple, TupleDesc tupdesc,
16521652
subkey->sk_argument));
16531653

16541654
if (subkey->sk_flags & SK_BT_DESC)
1655-
cmpresult = -cmpresult;
1655+
INVERT_COMPARE_RESULT(cmpresult);
16561656

16571657
/* Done comparing if unequal, else advance to next column */
16581658
if (cmpresult != 0)

‎src/backend/executor/nodeGatherMerge.c

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -755,7 +755,10 @@ heap_compare_slots(Datum a, Datum b, void *arg)
755755
datum2, isNull2,
756756
sortKey);
757757
if (compare != 0)
758-
return -compare;
758+
{
759+
INVERT_COMPARE_RESULT(compare);
760+
return compare;
761+
}
759762
}
760763
return 0;
761764
}

‎src/backend/executor/nodeIndexscan.c

Lines changed: 4 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -467,9 +467,10 @@ reorderqueue_cmp(const pairingheap_node *a, const pairingheap_node *b,
467467
ReorderTuple *rtb = (ReorderTuple *) b;
468468
IndexScanState *node = (IndexScanState *) arg;
469469

470-
return -cmp_orderbyvals(rta->orderbyvals, rta->orderbynulls,
471-
rtb->orderbyvals, rtb->orderbynulls,
472-
node);
470+
/* exchange argument order to invert the sort order */
471+
return cmp_orderbyvals(rtb->orderbyvals, rtb->orderbynulls,
472+
rta->orderbyvals, rta->orderbynulls,
473+
node);
473474
}
474475

475476
/*

‎src/backend/executor/nodeMergeAppend.c

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -338,7 +338,10 @@ heap_compare_slots(Datum a, Datum b, void *arg)
338338
datum2, isNull2,
339339
sortKey);
340340
if (compare != 0)
341-
return -compare;
341+
{
342+
INVERT_COMPARE_RESULT(compare);
343+
return compare;
344+
}
342345
}
343346
return 0;
344347
}

‎src/bin/pg_rewind/filemap.c

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -810,7 +810,7 @@ final_filemap_cmp(const void *a, const void *b)
810810
return -1;
811811

812812
if (fa->action == FILE_ACTION_REMOVE)
813-
return -strcmp(fa->path, fb->path);
813+
return strcmp(fb->path, fa->path);
814814
else
815815
return strcmp(fa->path, fb->path);
816816
}

‎src/include/access/nbtree.h

Lines changed: 1 addition & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -274,8 +274,7 @@ typedef struct BTMetaPageData
274274
* When a new operator class is declared, we require that the user
275275
* supply us with an amproc procedure (BTORDER_PROC) for determining
276276
* whether, for two keys a and b, a < b, a = b, or a > b. This routine
277-
* must return < 0, 0, > 0, respectively, in these three cases. (It must
278-
* not return INT_MIN, since we may negate the result before using it.)
277+
* must return < 0, 0, > 0, respectively, in these three cases.
279278
*
280279
* To facilitate accelerated sorting, an operator class may choose to
281280
* offer a second procedure (BTSORTSUPPORT_PROC). For full details, see

0 commit comments

Comments
 (0)