pg.ddx.io pgsql-bugs@postgresql.org mailing list archive
help / color / mirror / Atom feed[PATCH v0] Mitigate potential infinite-recursion in lseg_inside_poly()
1+ messages / 1 participants
[nested] [flat]
* [PATCH v0] Mitigate potential infinite-recursion in lseg_inside_poly()
@ 2023-06-06 04:53 Kyotaro Horiguchi <horikyota.ntt@gmail.com>
0 siblings, 0 replies; 1+ messages in thread
From: Kyotaro Horiguchi @ 2023-06-06 04:53 UTC (permalink / raw)
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.patch
diff --git a/src/backend/utils/adt/geo_ops.c b/src/backend/utils/adt/geo_ops.c
index e21962af45..392b85af73 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
+ * assign 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 infinite recursion."),
+ errhint("This might be caused by an 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
only message in thread
Thread overview: 1+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2023-06-06 04:53 [PATCH v0] Mitigate potential infinite-recursion in lseg_inside_poly() Kyotaro Horiguchi <horikyota.ntt@gmail.com>
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