From: Kyotaro Horiguchi <horikyota.ntt@gmail.com>
Subject: [PATCH v0] Mitigate potential infinite-recursion in lseg_inside_poly()
Date: Tue, 6 Jun 2023 13:53:48 +0900
Due to the absense of an underflow check since 12, calculation
underflow could trigger infinite recursion in lset_inside_poly(). In
this version, we do not introduce an underflow check. Instead, we
directly check infinite recursion within the function.
---
src/backend/utils/adt/geo_ops.c | 42 +++++++++++++++++++++++++++++----
1 file changed, 38 insertions(+), 4 deletions(-)
inline patch 1: src/backend/utils/adt/geo_ops.c (+38/-4 lines) download inline-1.patchdiff --git a/src/backend/utils/adt/geo_ops.c b/src/backend/utils/adt/geo_ops.cindex e21962af45..6fbc682a6c 100644--- a/src/backend/utils/adt/geo_ops.c+++ b/src/backend/utils/adt/geo_ops.c@@ -75,10 +75,13 @@ static bool has_interpt_sl(LSEG *lseg, LINE *line);
static double dist_pl_internal(Point *pt, LINE *line);
static double dist_ps_internal(Point *pt, LSEG *lseg);
static Point *line_interpt_internal(LINE *l1, LINE *l2);
+static bool lseg_inside_poly_top(Point *a, Point *b, POLYGON *poly);
static bool lseg_inside_poly(Point *a, Point *b, POLYGON *poly, int start);
static Point *lseg_interpt_internal(LSEG *l1, LSEG *l2);
static double dist_ppoly_internal(Point *pt, POLYGON *poly);
+/* recursion state of lseg_inside_poly */+static int lseg_inside_poly_last_start;
/*
* Delimiters for input and output strings.
@@ -3848,9 +3851,18 @@ touched_lseg_inside_poly(Point *a, Point *b, LSEG *s, POLYGON *poly, int start)
}
/*
- * Returns true if segment (a,b) is in polygon, option- * start is used for optimization - function checks- * polygon's edges started from start+ * Returns true if segment (a,b) is in polygon.+ */+static bool+lseg_inside_poly_top(Point *a, Point *b, POLYGON *poly)+{+ lseg_inside_poly_last_start = -1;+ return lseg_inside_poly(a, b, poly, 0);+}++/*+ * Recursion part of lseg_inside_poly_top, option start is used for+ * optimization - function checks polygon's edges started from start
*/
static bool
lseg_inside_poly(Point *a, Point *b, POLYGON *poly, int start)
@@ -3864,6 +3876,23 @@ lseg_inside_poly(Point *a, Point *b, POLYGON *poly, int start)
/* since this function recurses, it could be driven to stack overflow */
check_stack_depth();
+ /*+ * There is a known case where lseg_inside_poly is called for a line+ * segment that has already been checked, thereby causing infinite+ * recursion. Version 12 has introduced a strict underflow check to prevent+ * this issue. However, in this version, circumvent the infinite recursion+ * by checking the starting segment instead to keep the existing harmless+ * behavior as is. The error code might be wrong in unknown cases but+ * assing ERRCODE_NUMERIC_VALUE_OUT_OF_RANGE for now.+ */+ if (start <= lseg_inside_poly_last_start)+ ereport(ERROR, (errcode(ERRCODE_NUMERIC_VALUE_OUT_OF_RANGE),+ errmsg("math error"),+ errdetail("lseg_inside_poly entered infinit recursion"),+ errhint("This might be caused by underflow")));++ lseg_inside_poly_last_start = start;+
t.p[0] = *a;
t.p[1] = *b;
s.p[0] = poly->p[(start == 0) ? (poly->npts - 1) : (start - 1)];
@@ -3897,6 +3926,11 @@ lseg_inside_poly(Point *a, Point *b, POLYGON *poly, int start)
intersection = true;
res = lseg_inside_poly(t.p, interpt, poly, i + 1);
+ /*+ * allow repeated call to the function for the same starting+ * position+ */+ lseg_inside_poly_last_start = start;
if (res)
res = lseg_inside_poly(t.p + 1, interpt, poly, i + 1);
pfree(interpt);
@@ -3949,7 +3983,7 @@ poly_contain(PG_FUNCTION_ARGS)
for (i = 0; i < polyb->npts && result; i++)
{
s.p[1] = polyb->p[i];
- result = lseg_inside_poly(s.p, s.p + 1, polya, 0);+ result = lseg_inside_poly_top(s.p, s.p + 1, polya);
s.p[0] = s.p[1];
}
}
--
2.39.3
----Next_Part(Tue_Jun__6_14_07_49_2023_831)----
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-bugs@postgresql.org
Cc: horikyota.ntt@gmail.com
Subject: Re: [PATCH v0] Mitigate potential infinite-recursion in lseg_inside_poly()
In-Reply-To: <no-message-id-26619@localhost>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox