Date: Wed, 7 Feb 2024 14:56:00 -0600
From: Nathan Bossart <nathandbossart@gmail.com>
To: Heikki Linnakangas <hlinnaka@iki.fi>
Cc: Mats Kindahl <mats@timescale.com>, Tom Lane <tgl@sss.pgh.pa.us>,
	pgsql-hackers@lists.postgresql.org
Subject: Re: glibc qsort() vulnerability
Message-ID: <20240207205600.GA378707@nathanxps13>
References: <CA+14426g2Wa9QuUpmakwPxXFWG_1FaY0AsApkvcTBy-YfS6uaw@mail.gmail.com>
 <508821.1707232276@sss.pgh.pa.us>
 <20240206205305.GB3891538@nathanxps13>
 <642084.1707252958@sss.pgh.pa.us>
 <CA+14425TqyUZ3-O7zYsW6u85yY5diCz-p_TPQ2bZovn-N-fQ9A@mail.gmail.com>
 <cc9b0272-849a-4a88-8200-59786d18b7a1@iki.fi>
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary="x+6KMIRAuhnl3hBn"
Content-Disposition: inline
In-Reply-To: <cc9b0272-849a-4a88-8200-59786d18b7a1@iki.fi>
Archived-At: <https://www.postgresql.org/message-id/20240207205600.GA378707%40nathanxps13>
Precedence: bulk


--x+6KMIRAuhnl3hBn
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline

On Wed, Feb 07, 2024 at 08:46:56PM +0200, Heikki Linnakangas wrote:
> Doesn't hurt to fix the comparison functions, and +1 on using the same
> pattern everywhere.

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.
> 
> Looking at our ST_SORT(), it seems safe to me.

Cool.

-- 
Nathan Bossart
Amazon Web Services: https://aws.amazon.com

--x+6KMIRAuhnl3hBn
Content-Type: text/x-diff; charset=us-ascii
Content-Disposition: attachment;
	filename="v2-0001-remove-direct-calls-to-pg_qsort.patch"

From f5850579e92f201218c3025327b91d820eabd18e Mon Sep 17 00:00:00 2001
From: Nathan Bossart <nathan@postgresql.org>
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


--x+6KMIRAuhnl3hBn
Content-Type: text/x-diff; charset=us-ascii
Content-Disposition: attachment;
	filename="v2-0002-Ensure-comparison-functions-are-transitive.patch"

From f1a046c3c67266187f5861b27c2fad1daa25101c Mon Sep 17 00:00:00 2001
From: Mats Kindahl <mats@timescale.com>
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


--x+6KMIRAuhnl3hBn--