Date: Wed, 7 Feb 2024 20:45:58 -0600
From: Nathan Bossart <nathandbossart@gmail.com>
To: Andres Freund <andres@anarazel.de>
Cc: Heikki Linnakangas <hlinnaka@iki.fi>, Mats Kindahl <mats@timescale.com>,
	Tom Lane <tgl@sss.pgh.pa.us>, pgsql-hackers@lists.postgresql.org
Subject: Re: glibc qsort() vulnerability
Message-ID: <20240208024558.GB445153@nathanxps13>
References: <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>
 <20240207214857.rjqkutiaapka2xyp@awork3.anarazel.de>
 <20240207222124.GA382832@nathanxps13>
 <20240208004207.aoyrtv577nmhrivy@awork3.anarazel.de>
 <20240208015211.GA445153@nathanxps13>
 <20240208020637.3irwi5vph4fbxw2f@awork3.anarazel.de>
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary="T4sUOijqQbZv57TR"
Content-Disposition: inline
In-Reply-To: <20240208020637.3irwi5vph4fbxw2f@awork3.anarazel.de>
Archived-At: <https://www.postgresql.org/message-id/20240208024558.GB445153%40nathanxps13>
Precedence: bulk


--T4sUOijqQbZv57TR
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline

On Wed, Feb 07, 2024 at 06:06:37PM -0800, Andres Freund wrote:
> Another branchless variant is (a > b) - (a < b). It seems to get a similar
> improvement as the overflow-checking version.

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

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

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

From 8668a0dd83ecbdd356c76416b8398138407ef829 Mon Sep 17 00:00:00 2001
From: Nathan Bossart <nathan@postgresql.org>
Date: Wed, 7 Feb 2024 14:29:04 -0600
Subject: [PATCH v3 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


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

From a74708f14d6e862b836b2d5106491a8db3114433 Mon Sep 17 00:00:00 2001
From: Mats Kindahl <mats@timescale.com>
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
diff --git a/src/backend/utils/cache/relcache.c b/src/backend/utils/cache/relcache.c
index ac106b40e3..54682a0e60 100644
--- a/src/backend/utils/cache/relcache.c
+++ b/src/backend/utils/cache/relcache.c
@@ -4517,10 +4517,13 @@ 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;
+	AttrNumber	ana = ((const AttrDefault *) a)->adnum;
+	AttrNumber	anb = ((const AttrDefault *) b)->adnum;
 
-	return ada->adnum - adb->adnum;
+	/* ensure upcasting approach is transitive */
+	Assert(sizeof(AttrNumber) == 2);
+
+	return (int) ana - (int) anb;
 }
 
 /*
diff --git a/src/bin/pg_upgrade/function.c b/src/bin/pg_upgrade/function.c
index af998f74d3..b421500bbb 100644
--- a/src/bin/pg_upgrade/function.c
+++ b/src/bin/pg_upgrade/function.c
@@ -32,14 +32,16 @@ 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;
+		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


--T4sUOijqQbZv57TR--