From f68970e33f4dc48094c24c78c452ad730ae9ae12 Mon Sep 17 00:00:00 2001 From: Tom Lane Date: Mon, 3 May 2021 11:42:31 -0400 Subject: Fix performance issue in new regex match-all detection code. Commit 824bf7190 introduced a new search of the NFAs generated by regex compilation. I failed to think hard about the performance characteristics of that search, with the predictable outcome that it's bad: weird regexes can trigger exponential search time. Worse, there's no check-for-interrupt in that code, so you can't even cancel the query if this happens. Fix by introducing memo-ization of the search results, so that any one NFA state need be examined in detail just once. This potentially uses a lot of memory, but we can bound the memory usage by putting a limit on the number of states for which we'll try to prove match-all-ness. That is sane because we already have a limit (DUPINF) on the maximum finite string length that a matchall regex can match; and patterns that involve much more than DUPINF states would probably exceed that limit anyway. Also, rearrange the logic so that we check the basic is-the-graph- all-RAINBOW-arcs property before we start the recursive search to determine path lengths. This will ensure that we fall out quickly whenever the NFA couldn't possibly be matchall. Also stick in a check-for-interrupt, just in case these measures don't completely eliminate the risk of slowness. Discussion: https://postgr.es/m/3483895.1619898362@sss.pgh.pa.us --- src/backend/regex/regcomp.c | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) (limited to 'src/backend/regex/regcomp.c') diff --git a/src/backend/regex/regcomp.c b/src/backend/regex/regcomp.c index ba8dd864645..9f71177d318 100644 --- a/src/backend/regex/regcomp.c +++ b/src/backend/regex/regcomp.c @@ -182,8 +182,7 @@ static void markreachable(struct nfa *, struct state *, struct state *, struct s static void markcanreach(struct nfa *, struct state *, struct state *, struct state *); static long analyze(struct nfa *); static void checkmatchall(struct nfa *); -static bool checkmatchall_recurse(struct nfa *, struct state *, - bool, int, bool *); +static bool checkmatchall_recurse(struct nfa *, struct state *, bool **); static bool check_out_colors_match(struct state *, color, color); static bool check_in_colors_match(struct state *, color, color); static void compact(struct nfa *, struct cnfa *); -- cgit v1.2.3