From 349fc26e6c278e0d1de00458c76a113ae8425f88 Mon Sep 17 00:00:00 2001 From: dkf Date: Tue, 1 Jul 2008 14:29:11 +0000 Subject: Add focussed stack limiting to the RE compiler. Tuning might not yet be right but it passes everything normally checked in the test suite. [Bug 1905562] --- ChangeLog | 7 ++++++- generic/regc_nfa.c | 17 ++++++++++++++--- generic/regcomp.c | 2 +- 3 files changed, 21 insertions(+), 5 deletions(-) diff --git a/ChangeLog b/ChangeLog index 666974e..3767add 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,4 +1,9 @@ -2008-07-01 Donal K. Fellows +2008-07-01 Donal K. Fellows + + * generic/regc_nfa.c (duptraverse): Impose a maximum stack depth on + the single most recursive part of the RE engine. The actual maximum + may need tuning, but that needs a system with a small stack to carry + out. [Bug 1905562] * tests/string.test: Eliminate non-ASCII characters from the actual test script. [Bug 2006884] diff --git a/generic/regc_nfa.c b/generic/regc_nfa.c index d8cbd82..4fb3ea6 100644 --- a/generic/regc_nfa.c +++ b/generic/regc_nfa.c @@ -725,7 +725,7 @@ dupnfa( } stop->tmp = to; - duptraverse(nfa, start, from); + duptraverse(nfa, start, from, 0); /* done, except for clearing out the tmp pointers */ stop->tmp = NULL; @@ -740,7 +740,8 @@ static void duptraverse( struct nfa *nfa, struct state *s, - struct state *stmp) /* s's duplicate, or NULL */ + struct state *stmp, /* s's duplicate, or NULL */ + int depth) { struct arc *a; @@ -754,8 +755,18 @@ duptraverse( return; } + /* + * Arbitrary depth limit. Needs tuning, but this value is sufficient to + * make all normal tests (not reg-33.14) pass. + */ +#define DUPTRAVERSE_MAX_DEPTH 500 + + if (depth++ > DUPTRAVERSE_MAX_DEPTH) { + NERR(REG_ESPACE); + } + for (a=s->outs ; a!=NULL && !NISERR() ; a=a->outchain) { - duptraverse(nfa, a->to, NULL); + duptraverse(nfa, a->to, NULL, depth); if (NISERR()) { break; } diff --git a/generic/regcomp.c b/generic/regcomp.c index afe1b1b..8ff77ad 100644 --- a/generic/regcomp.c +++ b/generic/regcomp.c @@ -131,7 +131,7 @@ static void cloneouts(struct nfa *, struct state *, struct state *, struct state static void delsub(struct nfa *, struct state *, struct state *); static void deltraverse(struct nfa *, struct state *, struct state *); static void dupnfa(struct nfa *, struct state *, struct state *, struct state *, struct state *); -static void duptraverse(struct nfa *, struct state *, struct state *); +static void duptraverse(struct nfa *, struct state *, struct state *, int); static void cleartraverse(struct nfa *, struct state *); static void specialcolors(struct nfa *); static long optimize(struct nfa *, FILE *); -- cgit v0.12