Subject: Re: glibc qsort() vulnerability

From: Mats Kindahl <[email-masked]>
Date: Wed, 7 Feb 2024 10:09:58 +0100

On Tue, Feb 6, 2024 at 9:56 PM Tom Lane <[email-masked]> wrote:

> Nathan Bossart <[email-masked]> writes:
> > Even if the glibc issue doesn't apply to Postgres, I'm tempted to suggest
> > that we make it project policy that comparison functions must be
> > transitive.  There might be no real issues today, but if we write all
> > comparison functions the way Mats is suggesting, it should be easier to
> > reason about overflow risks.
>
> A comparison routine that is not is probably broken, agreed.
> I didn't look through the details of the patch --- I was more
> curious whether we had a version of the qsort bug, because
> if we do, we should fix that too.
>

The patch basically removes the risk of overflow in three routines and just
returns -1, 0, or 1, and adds a comment in one.

The routines modified do a subtraction of int:s and return that, which can
cause an overflow. This method is used for some int16 as well but since
standard conversions in C will perform the arithmetics in "int" precision,
this cannot overflow, so added a comment there. It might still be a good
idea to follow the same pattern for the int16 routines, but since there is
no bug there, I did not add them to the patch.

Best wishes,
Mats Kindahl

>                         regards, tom lane

---

From: Heikki Linnakangas <[email-masked]>
Date: Wed, 7 Feb 2024 20:46:56 +0200

On 07/02/2024 11:09, Mats Kindahl wrote:
> On Tue, Feb 6, 2024 at 9:56 PM Tom Lane <[email-masked] 
> <mailto:[email-masked]>> wrote:
> 
>   Nathan Bossart <[email-masked]
>     <mailto:[email-masked]>> writes:
> The patch basically removes the risk of overflow in three routines and 
> just returns -1, 0, or 1, and adds a comment in one.
> 
> The routines modified do a subtraction of int:s and return that, which 
> can cause an overflow. This method is used for some int16 as well but 
> since standard conversions in C will perform the arithmetics in "int" 
> precision, this cannot overflow, so added a comment there. It might 
> still be a good idea to follow the same pattern for the int16 routines, 
> but since there is no bug there, I did not add them to the patch.

Doesn't hurt to fix the comparison functions, and +1 on using the same 
pattern everywhere.

However, we use our qsort() with user-defined comparison functions, and 
we cannot make any guarantees about what they might do. So we must 
ensure that our qsort() doesn't overflow, no matter what the comparison 
function does.

Looking at our ST_SORT(), it seems safe to me.

-- 
Heikki Linnakangas
Neon (https://neon.tech)

---

From: Nathan Bossart <[email-masked]>
Date: Wed, 7 Feb 2024 14:56:00 -0600

> Doesn't hurt to fix the comparison functions, and +1 on using the same

I attached a new version of the patch with some small adjustments.  I
haven't looked through all in-tree qsort() comparators to see if any others
need to be adjusted, but we should definitely do so as part of this thread.
Mats, are you able to do this?

> However, we use our qsort() with user-defined comparison functions, and we
> cannot make any guarantees about what they might do. So we must ensure that
> our qsort() doesn't overflow, no matter what the comparison function does.
> 

Cool.

-- 
Nathan Bossart
Amazon Web Services: https://aws.amazon.com
>From f5850579e92f201218c3025327b91d820eabd18e Mon Sep 17 00:00:00 2001
From: Nathan Bossart <[email-masked]>
Date: Wed, 7 Feb 2024 14:29:04 -0600
Subject: [PATCH v2 1/2] remove direct calls to pg_qsort()

---
 contrib/pg_prewarm/autoprewarm.c            |  4 ++--
 src/backend/access/brin/brin_minmax_multi.c |  2 +-
 src/backend/storage/buffer/bufmgr.c         |  4 ++--
 src/backend/utils/cache/syscache.c          | 10 +++++-----
 4 files changed, 10 insertions(+), 10 deletions(-)

diff --git a/contrib/pg_prewarm/autoprewarm.c b/contrib/pg_prewarm/autoprewarm.c
index 06ee21d496..248b9914a3 100644
--- a/contrib/pg_prewarm/autoprewarm.c
+++ b/contrib/pg_prewarm/autoprewarm.c
@@ -346,8 +346,8 @@ apw_load_buffers(void)
 	FreeFile(file);
 
 	/* Sort the blocks to be loaded. */
-	pg_qsort(blkinfo, num_elements, sizeof(BlockInfoRecord),
-			 apw_compare_blockinfo);
+	qsort(blkinfo, num_elements, sizeof(BlockInfoRecord),
+		  apw_compare_blockinfo);
 
 	/* Populate shared memory state. */
 	apw_state->block_info_handle = dsm_segment_handle(seg);
diff --git a/src/backend/access/brin/brin_minmax_multi.c b/src/backend/access/brin/brin_minmax_multi.c
index 3ffaad3e42..2c29aa3d4e 100644
--- a/src/backend/access/brin/brin_minmax_multi.c
+++ b/src/backend/access/brin/brin_minmax_multi.c
@@ -1369,7 +1369,7 @@ build_distances(FmgrInfo *distanceFn, Oid colloid,
 	 * Sort the distances in descending order, so that the longest gaps are at
 	 * the front.
 	 */
-	pg_qsort(distances, ndistances, sizeof(DistanceValue), compare_distances);
+	qsort(distances, ndistances, sizeof(DistanceValue), compare_distances);
 
 	return distances;
 }
diff --git a/src/backend/storage/buffer/bufmgr.c b/src/backend/storage/buffer/bufmgr.c
index eb1ec3b86d..07575ef312 100644
--- a/src/backend/storage/buffer/bufmgr.c
+++ b/src/backend/storage/buffer/bufmgr.c
@@ -3915,7 +3915,7 @@ DropRelationsAllBuffers(SMgrRelation *smgr_reln, int nlocators)
 
 	/* sort the list of rlocators if necessary */
 	if (use_bsearch)
-		pg_qsort(locators, n, sizeof(RelFileLocator), rlocator_comparator);
+		qsort(locators, n, sizeof(RelFileLocator), rlocator_comparator);
 
 	for (i = 0; i < NBuffers; i++)
 	{
@@ -4269,7 +4269,7 @@ FlushRelationsAllBuffers(SMgrRelation *smgrs, int nrels)
 
 	/* sort the list of SMgrRelations if necessary */
 	if (use_bsearch)
-		pg_qsort(srels, nrels, sizeof(SMgrSortArray), rlocator_comparator);
+		qsort(srels, nrels, sizeof(SMgrSortArray), rlocator_comparator);
 
 	for (i = 0; i < NBuffers; i++)
 	{
diff --git a/src/backend/utils/cache/syscache.c b/src/backend/utils/cache/syscache.c
index 162855b158..662f930864 100644
--- a/src/backend/utils/cache/syscache.c
+++ b/src/backend/utils/cache/syscache.c
@@ -146,14 +146,14 @@ InitCatalogCache(void)
 	Assert(SysCacheSupportingRelOidSize <= lengthof(SysCacheSupportingRelOid));
 
 	/* Sort and de-dup OID arrays, so we can use binary search. */
-	pg_qsort(SysCacheRelationOid, SysCacheRelationOidSize,
-			 sizeof(Oid), oid_compare);
+	qsort(SysCacheRelationOid, SysCacheRelationOidSize,
+		  sizeof(Oid), oid_compare);
 	SysCacheRelationOidSize =
 		qunique(SysCacheRelationOid, SysCacheRelationOidSize, sizeof(Oid),
 				oid_compare);
 
-	pg_qsort(SysCacheSupportingRelOid, SysCacheSupportingRelOidSize,
-			 sizeof(Oid), oid_compare);
+	qsort(SysCacheSupportingRelOid, SysCacheSupportingRelOidSize,
+		  sizeof(Oid), oid_compare);
 	SysCacheSupportingRelOidSize =
 		qunique(SysCacheSupportingRelOid, SysCacheSupportingRelOidSize,
 				sizeof(Oid), oid_compare);
@@ -668,7 +668,7 @@ RelationSupportsSysCache(Oid relid)

 /*
- * OID comparator for pg_qsort
+ * OID comparator for qsort
  */
 static int
 oid_compare(const void *a, const void *b)
-- 
2.25.1

>From f1a046c3c67266187f5861b27c2fad1daa25101c Mon Sep 17 00:00:00 2001
From: Mats Kindahl <[email-masked]>
Date: Tue, 6 Feb 2024 14:53:53 +0100
Subject: [PATCH v2 2/2] Ensure comparison functions are transitive

There are a few comparison functions to qsort() that are non-transitive
because they can cause an overflow. Fix these functions to instead use
normal comparisons and return -1, 0, or 1 explicitly.
---
 src/backend/access/spgist/spgtextproc.c |  6 +++++-
 src/backend/utils/cache/relcache.c      | 12 ++++++++----
 src/bin/pg_upgrade/function.c           | 20 ++++++++++++++++----
 src/bin/psql/crosstabview.c             |  9 ++++++++-
 4 files changed, 37 insertions(+), 10 deletions(-)

diff --git a/src/backend/access/spgist/spgtextproc.c b/src/backend/access/spgist/spgtextproc.c
index b8fd0c2ad8..d0a2b4e6e1 100644
--- a/src/backend/access/spgist/spgtextproc.c
+++ b/src/backend/access/spgist/spgtextproc.c
@@ -325,7 +325,11 @@ cmpNodePtr(const void *a, const void *b)
 	const spgNodePtr *aa = (const spgNodePtr *) a;
 	const spgNodePtr *bb = (const spgNodePtr *) b;
 
-	return aa->c - bb->c;
+	if (aa->c > bb->c)
+		return 1;
+	if (aa->c < bb->c)
+		return -1;
+	return 0;
 }
 
 Datum
diff --git a/src/backend/utils/cache/relcache.c b/src/backend/utils/cache/relcache.c
index ac106b40e3..dc5a100d82 100644
--- a/src/backend/utils/cache/relcache.c
+++ b/src/backend/utils/cache/relcache.c
@@ -4517,10 +4517,14 @@ AttrDefaultFetch(Relation relation, int ndef)
 static int
 AttrDefaultCmp(const void *a, const void *b)
 {
-	const AttrDefault *ada = (const AttrDefault *) a;
-	const AttrDefault *adb = (const AttrDefault *) b;
-
-	return ada->adnum - adb->adnum;
+	AttrNumber	ana = ((const AttrDefault *) a)->adnum;
+	AttrNumber	anb = ((const AttrDefault *) b)->adnum;
+
+	if (ana > anb)
+		return 1;
+	if (ana < anb)
+		return -1;
+	return 0;
 }
 
 /*
diff --git a/src/bin/pg_upgrade/function.c b/src/bin/pg_upgrade/function.c
index af998f74d3..483ede2ce4 100644
--- a/src/bin/pg_upgrade/function.c
+++ b/src/bin/pg_upgrade/function.c
@@ -32,14 +32,26 @@ library_name_compare(const void *p1, const void *p2)
 	int			slen1 = strlen(str1);
 	int			slen2 = strlen(str2);
 	int			cmp = strcmp(str1, str2);
+	int			p1db = ((const LibraryInfo *) p1)->dbnum;
+	int			p2db = ((const LibraryInfo *) p2)->dbnum;
 
 	if (slen1 != slen2)
-		return slen1 - slen2;
+	{
+		if (slen1 > slen2)
+			return 1;
+		if (slen1 < slen2)
+			return -1;
+		return 0;
+	}
+
 	if (cmp != 0)
 		return cmp;
-	else
-		return ((const LibraryInfo *) p1)->dbnum -
-			((const LibraryInfo *) p2)->dbnum;
+
+	if (p1db > p2db)
+		return 1;
+	if (p1db < p2db)
+		return -1;
+	return 0;
 }

diff --git a/src/bin/psql/crosstabview.c b/src/bin/psql/crosstabview.c
index c6116b7238..de6168bd67 100644
--- a/src/bin/psql/crosstabview.c
+++ b/src/bin/psql/crosstabview.c
@@ -709,5 +709,12 @@ pivotFieldCompare(const void *a, const void *b)
 static int
 rankCompare(const void *a, const void *b)
 {
-	return *((const int *) a) - *((const int *) b);
+	const int	an = *(const int *) a;
+	const int	bn = *(const int *) b;
+
+	if (an > bn)
+		return 1;
+	if (an < bn)
+		return -1;
+	return 0;
 }
-- 
2.25.1

---

From: Andres Freund <[email-masked]>
Date: Wed, 7 Feb 2024 13:48:57 -0800

Hi,

> Doesn't hurt to fix the comparison functions, and +1 on using the same

It actually can hurt - the generated code will often be slower.

E.g.
#include <stdint.h>

int cmp_sub(int16_t a, int16_t b) {
    return (int32_t) a - (int32_t) b;
}

int cmp_if(int16_t a, int16_t b) {
    if (a < b)
        return -1;
    if (a > b)
        return 1;
    return 0;
}

yields

cmp_sub:
        movsx   eax, di
        movsx   esi, si
        sub     eax, esi
        ret
cmp_if:
        xor     eax, eax
        cmp     di, si
        mov     edx, -1
        setg    al
        cmovl   eax, edx
        ret

with gcc -O3.  With other compilers, e.g. msvc, the difference is considerably
bigger, due to msvc for some reason not using cmov.

See https://godbolt.org/z/34qerPaPE for a few more details.

Now, in most cases this won't matter, the sorting isn't performance
critical. But I don't think it's a good idea to standardize on a generally
slower pattern.

Not that that's a good test, but I did quickly benchmark [1] this with
intarray. There's about a 10% difference in performance between using the
existing compASC() and one using
	return (int64) *(const int32 *) a - (int64) *(const int32 *) b;

Perhaps we could have a central helper for this somewhere?

Greetings,

Andres Freund

[1]
-- prep
CREATE EXTENSION IF NOT EXISTS intarray;
DROP TABLE IF EXISTS arrays_to_sort;
CREATE TABLE arrays_to_sort AS SELECT array_shuffle(a) arr FROM (SELECT ARRAY(SELECT generate_series(1, 1000000)) a), generate_series(1, 10);
-- bench
SELECT (sort(arr))[1] FROM arrays_to_sort;

---

From: Nathan Bossart <[email-masked]>
Date: Wed, 7 Feb 2024 16:21:24 -0600

> Perhaps we could have a central helper for this somewhere?

Maybe said helper could use __builtin_sub_overflow() and fall back to the
slow "if" version only if absolutely necessary.  The assembly for that
looks encouraging, but I still need to actually test it...

---

From: Andres Freund <[email-masked]>
Date: Wed, 7 Feb 2024 16:42:07 -0800

Hi,

On 2024-02-07 16:21:24 -0600, Nathan Bossart wrote:
> slow "if" version only if absolutely necessary.

I suspect that'll be worse code in the common case, given the cmov generated
by gcc & clang for the typical branch-y formulation. But it's worth testing.

> The assembly for that looks encouraging, but I still need to actually test
> it...

Possible. For 16bit upcasting to 32bit is clearly the best way. For 32 bit
that doesn't work, given the 32bit return, so we need something more.

Greetings,

Andres Freund

---

From: Nathan Bossart <[email-masked]>
Date: Wed, 7 Feb 2024 19:52:11 -0600

> that doesn't work, given the 32bit return, so we need something more.

For the same compASC() test, I see an ~8.4% improvement with your int64
code and a ~3.4% improvement with this:

    int
    compASC(const void *a, const void *b)
    {
        int         result;

        if (unlikely(pg_sub_s32_overflow(*(const int32 *) a,
                                         *(const int32 *) b,
                                         &result)))
        {
            if (*(const int32 *) a > *(const int32 *) b)
                return 1;
            if (*(const int32 *) a < *(const int32 *) b)
                return -1;
            return 0;
        }

        return result;
    }

---

From: Andres Freund <[email-masked]>
Date: Wed, 7 Feb 2024 18:06:37 -0800

Hi,

On 2024-02-07 19:52:11 -0600, Nathan Bossart wrote:
> code

Just to be clear, that code unfortuntely isn't correct, the return value is a
32 bit integer, so the 64bit difference doesn't help. In contrast to the 16bit
case.

> and a ~3.4% improvement with this:

I guess that's still something.

Another branchless variant is (a > b) - (a < b). It seems to get a similar
improvement as the overflow-checking version.

Greetings,

Andres Freund

---

From: Thomas Munro <[email-masked]>
Date: Thu, 8 Feb 2024 15:38:10 +1300

> 32 bit integer, so the 64bit difference doesn't help. In contrast to the 16bit

Perhaps you could wrap it in a branch-free sign() function so you get
a narrow answer?

https://stackoverflow.com/questions/14579920/fast-sign-of-integer-in-c

---

From: Nathan Bossart <[email-masked]>
Date: Wed, 7 Feb 2024 20:45:58 -0600

> improvement as the overflow-checking version.

Well, that's certainly more elegant.  I updated the patch to that approach
for now.

>From 8668a0dd83ecbdd356c76416b8398138407ef829 Mon Sep 17 00:00:00 2001
From: Nathan Bossart <[email-masked]>
Date: Wed, 7 Feb 2024 14:29:04 -0600
Subject: [PATCH v3 1/2] remove direct calls to pg_qsort()

---

 
 
 	return distances;
 }

 

 

 /*

>From a74708f14d6e862b836b2d5106491a8db3114433 Mon Sep 17 00:00:00 2001
From: Mats Kindahl <[email-masked]>
Date: Tue, 6 Feb 2024 14:53:53 +0100
Subject: [PATCH v3 2/2] Ensure comparison functions are transitive

There are a few comparison functions to qsort() that are non-transitive
because they can cause an overflow. Fix these functions to instead use
normal comparisons and return -1, 0, or 1 explicitly.
---
 src/backend/access/spgist/spgtextproc.c |  2 +-
 src/backend/utils/cache/relcache.c      |  9 ++++++---
 src/bin/pg_upgrade/function.c           | 10 ++++++----
 src/bin/psql/crosstabview.c             |  5 ++++-
 4 files changed, 17 insertions(+), 9 deletions(-)

diff --git a/src/backend/access/spgist/spgtextproc.c b/src/backend/access/spgist/spgtextproc.c
index b8fd0c2ad8..e561bde63e 100644
--- a/src/backend/access/spgist/spgtextproc.c
+++ b/src/backend/access/spgist/spgtextproc.c
@@ -325,7 +325,7 @@ cmpNodePtr(const void *a, const void *b)
 	const spgNodePtr *aa = (const spgNodePtr *) a;
 	const spgNodePtr *bb = (const spgNodePtr *) b;
 
-	return aa->c - bb->c;
+	return (aa->c > bb->c) - (aa->c < bb->c);
 }
 
 Datum
index ac106b40e3..54682a0e60 100644
@@ -4517,10 +4517,13 @@ AttrDefaultFetch(Relation relation, int ndef)
 
-	return ada->adnum - adb->adnum;
+	/* ensure upcasting approach is transitive */
+	Assert(sizeof(AttrNumber) == 2);
+
+	return (int) ana - (int) anb;
 }
 
 /*
index af998f74d3..b421500bbb 100644
@@ -32,14 +32,16 @@ library_name_compare(const void *p1, const void *p2)
 
 	if (slen1 != slen2)
-		return slen1 - slen2;
+		return (slen1 > slen2) - (slen1 < slen2);
+
 	if (cmp != 0)
 		return cmp;
-	else
-		return ((const LibraryInfo *) p1)->dbnum -
-			((const LibraryInfo *) p2)->dbnum;
+
+	return (p1db > p2db) - (p1db < p2db);
 }

diff --git a/src/bin/psql/crosstabview.c b/src/bin/psql/crosstabview.c
index c6116b7238..7660f0ed4b 100644
--- a/src/bin/psql/crosstabview.c
+++ b/src/bin/psql/crosstabview.c
@@ -709,5 +709,8 @@ pivotFieldCompare(const void *a, const void *b)
 static int
 rankCompare(const void *a, const void *b)
 {
-	return *((const int *) a) - *((const int *) b);
+	const int	an = *(const int *) a;
+	const int	bn = *(const int *) b;
+
+	return (an > bn) - (an < bn);
 }
-- 
2.25.1

---

From: Thomas Munro <[email-masked]>
Date: Thu, 8 Feb 2024 15:49:03 +1300

> https://stackoverflow.com/questions/14579920/fast-sign-of-integer-in-c

Ah, strike that, it is much like the suggested (a > b) - (a < b) but
with extra steps...

---

From: Mats Kindahl <[email-masked]>
Date: Thu, 8 Feb 2024 12:01:22 +0100

> Mats, are you able to do this?

Sure, I checked them and the only ones remaining are those using int16.
Shall I modify those as well?

> we

---

From: "Andrey M. Borodin" <[email-masked]>
Date: Fri, 9 Feb 2024 13:19:49 +0500

> On 8 Feb 2024, at 06:52, Nathan Bossart <[email-masked]> wrote:
> 

If we care about branch prediction in comparison function, maybe we could produce sorting that inlines comparator, thus eliminating function call to comparator? We convert comparison logic to int, to extract comparison back then.

I bet “call" is more expensive than “if".

Best regards, Andrey Borodin.

---

From: Nathan Bossart <[email-masked]>
Date: Fri, 9 Feb 2024 10:32:45 -0600

On Fri, Feb 09, 2024 at 01:19:49PM +0500, Andrey M. Borodin wrote:
> If we care about branch prediction in comparison function, maybe we could
> produce sorting that inlines comparator, thus eliminating function call
> to comparator? We convert comparison logic to int, to extract comparison
> back then.
> 

It might make sense to have a couple of built-in qsort implementations for
pointers to integers, pointers to unsigned integers, etc.  However, a lot
of current use-cases require inspecting specific fields of structs, so
(assuming I understand your proposal correctly), we'd end up with many
qsort implementations.  If that can be made simple and elegant and
demonstrates substantial improvements, then it might be worth considering,
but I'm somewhat skeptical that the current uses are performance-sensitive
enough to be worth the effort.

---

From: Andrey Borodin <[email-masked]>
Date: Sat, 10 Feb 2024 00:02:08 +0500

> On 9 Feb 2024, at 21:32, Nathan Bossart <[email-masked]> wrote:
>  a lot
> of current use-cases require inspecting specific fields of structs
Yes, I'm proposing to pass to sorting routine not a comparator, but value extractor. And then rely on operators <,>,==.
In a pseudocode: instead of sort(array, (a,b)->a.field-b.field) use sort(array, x->x.field). And rely on "field" being comparable.

> If that can be made simple and elegant and
> demonstrates substantial improvements
I'll try to produce a PoC and measure it with Andres' intarray test.

> On 9 Feb 2024, at 23:40, Andres Freund <[email-masked]> wrote:
> 
> We have some infrastructure for that actually, see sort_template.h.  But
> perhaps we should define a static inline of the generic pg_qsort() even. OTOH,
> plenty places that'll just end up to a pointless amount of code emitted to
> sort ~5 elements on average.
I think there might be another benefit. It's easier to think about values order than function comparator that returns -1,0,+1...

> Not really in this case. The call is perfectly predictable - a single qsort()
> will use the same callback for every comparison, whereas the if is perfectly
> *unpredictable*.  A branch mispredict is far more expensive than a correctly
> predicted function call.

Oh, make sense... I did not understand that. But does cpu predicts what instruction to fetch even after a call instruction? These cpus are really neat things... so, probably, yes, it does.