Subject: Fw:Re: Fw: ltree_compare in contrib/ltree/ltree_op.c overflows int32 on deep ltree comparisons, returning the wrong sign

From: 王跃林 <[email-masked]>
Date: Sat, 13 Jun 2026 11:50:25 +0800 (GMT+08:00)

-------- 转发邮件信息 --------
发件人：Noah Misch <[email-masked]>
发送日期：2026-06-13 08:31:47
收件人："[email-masked]" <[email-masked]>
抄送人：[email-masked]
主题：Re: Fw: ltree_compare in contrib/ltree/ltree_op.c overflows int32 on deep ltree comparisons, returning the wrong sign
On Mon, May 25, 2026 at 10:58:05PM +0800, [email-masked] wrote:
> PoC
> 
> File vuln_001.sql
> 
>  CREATE EXTENSION IF NOT EXISTS ltree;
>  â
>  WITH s AS (SELECT 'a'::ltree AS v),
>       l AS (SELECT (repeat('a.', 19999) || 'a')::ltree AS v)
>  SELECT (l.v > s.v) AS long_gt_short_expected_true,
>         (l.v < s.v) AS long_lt_short_expected_false
>  FROM s, l;
> 
> Process
> 
>  psql -h /tmp -p 36265 -U postgres -f vuln_001.sql
> 
> Results
> 
>   long_gt_short_expected_true | long_lt_short_expected_false
>  -----------------------------+------------------------------
>   f                           | t
> 
>    Both columns are inverted. long > short returned false, long < short
>    returned true.

This is certainly a bug, but it's not a vuln.  Please report the bug to
[email-masked].

---

From: Ayush Tiwari <[email-masked]>
Date: Sat, 13 Jun 2026 11:42:44 +0530

Hi,

> >   long_gt_short_expected_true | long_lt_short_expected_false
This looks like a classic case of integer overflow that's
happening in ltree_compare function in ltree_op.c.

return (al->len - bl->len) * 10 * (an + 1);
return res * 10 * (an + 1);
return (a->numlevel - b->numlevel) * 10 * (an + 1);

I think the calculation should be done as int64, something of this sort:

    int64 v = (int64) (al->len - bl->len) * 10 * (an + 1);
    if (v > PG_INT32_MAX) return PG_INT32_MAX;
    if (v < PG_INT32_MIN) return PG_INT32_MIN;
    return (int) v;

And needed to adjust the ltree_penalty function too.

Attached is a draft patch for this, I guess we can add a helper
function too for the above conversion.

Thoughts?

Regards,
Ayush

---

From: Heikki Linnakangas <[email-masked]>
Date: Mon, 15 Jun 2026 18:08:05 +0300

> function too for the above conversion.

Yeah, that works. However, I note that the multiplication is only really 
needed by the ltree_penalty() caller. All the other callers just check 
if the return value is less than, equal, or greater than zero. It feels 
a little silly to do all that work of multiplication and clamping for 
those callers. And for ltree_penalty(), the caller actually converts the 
return value to a float, so clamping it to int32 range feels a little 
silly for that too. So I propose the attached, which splits the 
ltree_compare() function into two variants: one for ltree_penalty() that 
returns a float, and one for others that don't care about the 
"magnitude". It duplicates a little code, but I think it's easier to 
reason about. What do you think?

- Heikki
From 1804f4f2a43e06748ffaccca1f9e027d03b7e3fa Mon Sep 17 00:00:00 2001
From: Heikki Linnakangas <[email-masked]>
Date: Mon, 15 Jun 2026 17:53:51 +0300
Subject: [PATCH v2 1/1] Fix int32 overflow in ltree_compare()
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

The expression (len_diff * 10 * (an + 1)) used as the return value of
ltree_compare() is computed at int32 width.  With LTREE_MAX_LEVELS =
65535, the product can exceed INT32_MAX once an ltree has more than
~14,653 levels, which causes the result to wrap and invert its sign.
That corrupts btree ordering as well as the magnitude consumed by
ltree_penalty() for GiST page splits.

Widen the multiplication to int64 and saturate the result to
PG_INT32_MIN / PG_INT32_MAX before returning.  Saturation preserves both
the sign needed by btree comparators and the "deeper mismatch yields
larger magnitude" property used by ltree_penalty().  Returning INT_MIN
from a comparator has been explicitly allowed since commit 6e63e069751.

ltree_penalty() sums the two comparator results, so a pair of saturated
INT32_MAX values would re-overflow int32 and yield a negative penalty
once assigned to its float output.  Widen that sum to int64 before
converting to float.

Existing btree or GiST indexes on ltree columns containing values with
more than ~14,653 levels may be corrupt and should be REINDEXed.

Add a regression test based on the reporter's PoC.

Author: Ayush Tiwari <[email-masked]>
Reported-by: 王跃林 <[email-masked]>
Discussion: https://www.postgresql.org/message-id/AI6AnABgKW93Qbx1jVzi84r9.8.1781322625756.Hmail.3020001251%40tju.edu.cn
---
 contrib/ltree/expected/ltree.out | 10 +++++++
 contrib/ltree/ltree.h            |  1 +
 contrib/ltree/ltree_gist.c       |  6 ++--
 contrib/ltree/ltree_op.c         | 49 ++++++++++++++++++++++++++++----
 contrib/ltree/sql/ltree.sql      |  6 ++++
 5 files changed, 63 insertions(+), 9 deletions(-)

diff --git a/contrib/ltree/expected/ltree.out b/contrib/ltree/expected/ltree.out
index 15b9131a750..f1d0eb37b81 100644
--- a/contrib/ltree/expected/ltree.out
+++ b/contrib/ltree/expected/ltree.out
@@ -8226,3 +8226,13 @@ DETAIL:  Total size of level exceeds the maximum allowed (65535 bytes).
 SELECT (repeat('a|', 65535) || 'a')::lquery;
 ERROR:  lquery level has too many variants
 DETAIL:  Number of variants exceeds the maximum allowed (65535).
+-- Test that ltree_compare() does not overflow with very deep paths.
+WITH s AS (SELECT 'a'::ltree AS v),
+     l AS (SELECT (repeat('a.', 14999) || 'a')::ltree AS v)
+SELECT (l.v > s.v) AS gt_ok, (l.v < s.v) AS lt_ok, (l.v = s.v) AS eq_ok
+  FROM s, l;
+ gt_ok | lt_ok | eq_ok 
+-------+-------+-------
+ t     | f     | f
+(1 row)
+
diff --git a/contrib/ltree/ltree.h b/contrib/ltree/ltree.h
index 226c1cb2115..89c5b932292 100644
--- a/contrib/ltree/ltree.h
+++ b/contrib/ltree/ltree.h
@@ -206,6 +206,7 @@ bool		ltree_execute(ITEM *curitem, void *checkval,
 						  bool calcnot, bool (*chkcond) (void *checkval, ITEM *val));
 
 int			ltree_compare(const ltree *a, const ltree *b);
+float		ltree_compare_distance(const ltree *a, const ltree *b);
 bool		inner_isparent(const ltree *c, const ltree *p);
 bool		compare_subnode(ltree_level *t, char *qn, int len, bool prefix, bool ci);
 ltree	   *lca_inner(ltree **a, int len);
diff --git a/contrib/ltree/ltree_gist.c b/contrib/ltree/ltree_gist.c
index 78c95052990..e8451171c72 100644
--- a/contrib/ltree/ltree_gist.c
+++ b/contrib/ltree/ltree_gist.c
@@ -264,11 +264,11 @@ ltree_penalty(PG_FUNCTION_ARGS)
 	ltree_gist *newval = (ltree_gist *) DatumGetPointer(((GISTENTRY *) PG_GETARG_POINTER(1))->key);
 	float	   *penalty = (float *) PG_GETARG_POINTER(2);
 	int			siglen = LTREE_GET_SIGLEN();
-	int32		cmpr,
+	float		cmpr,
 				cmpl;
 
-	cmpl = ltree_compare(LTG_GETLNODE(origval, siglen), LTG_GETLNODE(newval, siglen));
-	cmpr = ltree_compare(LTG_GETRNODE(newval, siglen), LTG_GETRNODE(origval, siglen));
+	cmpl = ltree_compare_distance(LTG_GETLNODE(origval, siglen), LTG_GETLNODE(newval, siglen));
+	cmpr = ltree_compare_distance(LTG_GETRNODE(newval, siglen), LTG_GETRNODE(origval, siglen));
 
 	*penalty = Max(cmpl, 0) + Max(cmpr, 0);
 
diff --git a/contrib/ltree/ltree_op.c b/contrib/ltree/ltree_op.c
index c1fc77fc804..1f9f02cf453 100644
--- a/contrib/ltree/ltree_op.c
+++ b/contrib/ltree/ltree_op.c
@@ -42,6 +42,9 @@ PG_FUNCTION_INFO_V1(ltree2text);
 PG_FUNCTION_INFO_V1(text2ltree);
 PG_FUNCTION_INFO_V1(ltreeparentsel);
 
+/*
+ * btree-comparison function.
+ */
 int
 ltree_compare(const ltree *a, const ltree *b)
 {
@@ -54,18 +57,52 @@ ltree_compare(const ltree *a, const ltree *b)
 	{
 		int			res;
 
-		if ((res = memcmp(al->name, bl->name, Min(al->len, bl->len))) == 0)
+		res = memcmp(al->name, bl->name, Min(al->len, bl->len));
+		if (res == 0)
+		{
+			if (al->len != bl->len)
+				return (int) al->len - (int) bl->len;
+		}
+		else
+			return res;
+
+		an--;
+		bn--;
+		al = LEVEL_NEXT(al);
+		bl = LEVEL_NEXT(bl);
+	}
+
+	return a->numlevel - b->numlevel;
+}
+
+/*
+ * Returns a "distance" between a and b.  If a < b, the distance is negative,
+ * consistent with the ltree_compare() ordering.
+ */
+float
+ltree_compare_distance(const ltree *a, const ltree *b)
+{
+	ltree_level *al = LTREE_FIRST(a);
+	ltree_level *bl = LTREE_FIRST(b);
+	int			an = a->numlevel;
+	int			bn = b->numlevel;
+
+	while (an > 0 && bn > 0)
+	{
+		int			res;
+
+		res = memcmp(al->name, bl->name, Min(al->len, bl->len));
+		if (res == 0)
 		{
 			if (al->len != bl->len)
-				return (al->len - bl->len) * 10 * (an + 1);
+				return (float) (al->len - bl->len) * 10.0 * (an + 1);
 		}
 		else
 		{
 			if (res < 0)
-				res = -1;
+				return -1.0 * 10.0 * (an + 1);
 			else
-				res = 1;
-			return res * 10 * (an + 1);
+				return 1.0 * 10.0 * (an + 1);
 		}
 
 		an--;
@@ -74,7 +111,7 @@ ltree_compare(const ltree *a, const ltree *b)
 		bl = LEVEL_NEXT(bl);
 	}
 
-	return (a->numlevel - b->numlevel) * 10 * (an + 1);
+	return ((float) (a->numlevel - b->numlevel)) * 10.0 * (an + 1);
 }
 
 #define RUNCMP						\
diff --git a/contrib/ltree/sql/ltree.sql b/contrib/ltree/sql/ltree.sql
index d0fade9d17d..833091dc6bb 100644
--- a/contrib/ltree/sql/ltree.sql
+++ b/contrib/ltree/sql/ltree.sql
@@ -477,3 +477,9 @@ SELECT (repeat('x', 255) || repeat('|' || repeat('x', 255), 256))::lquery;
 --- Test for overflow of lquery_level.numvar, with a set of single-char
 --- variants in one level.
 SELECT (repeat('a|', 65535) || 'a')::lquery;
+
+-- Test that ltree_compare() does not overflow with very deep paths.
+WITH s AS (SELECT 'a'::ltree AS v),
+     l AS (SELECT (repeat('a.', 14999) || 'a')::ltree AS v)
+SELECT (l.v > s.v) AS gt_ok, (l.v < s.v) AS lt_ok, (l.v = s.v) AS eq_ok
+  FROM s, l;
-- 
2.47.3

---

From: Ayush Tiwari <[email-masked]>
Date: Mon, 15 Jun 2026 20:54:56 +0530

Hi,

> reason about. What do you think?

I had thought initially of using the method you have added,
(not with float return-type though, I thought of planning to create
a duplicate function with int64 type just for ltree_penalty(), but float
type
is better) noting the same thing that rest callers just care about
comparison with 0.

But thought backpatching it would be harder, hence I used the int64
method. However, your patch looks much better than the ugly
behaviour and I agree it did not make sense to do those
multiplications at all other comparison functions.

Regards,
Ayush

---

From: Heikki Linnakangas <[email-masked]>
Date: Tue, 16 Jun 2026 09:37:42 +0300

On 15/06/2026 18:24, Ayush Tiwari wrote:
> On Mon, 15 Jun 2026 at 20:38, Heikki Linnakangas <[email-masked] 
> <mailto:[email-masked]>> wrote:
> 

Great, committed. Thanks!

- Heikki