Fixes for problems created when processing regular expressions that

generate very large automata. An enormous number of thanks to Will
Drewry <wad@google.com>, Tavis Ormandy <taviso@google.com>, and Tom
Lane <tgl@sss.pgh.pa.us> from the Postgresql crowd for their help in
tracking these problems down. [Bug 1810264]

1 files changed, 73 insertions, 2 deletions

diff --git a/generic/regc_nfa.c b/generic/regc_nfa.c
index 741887f..19dbe63 100644
--- a/generic/regc_nfa.c
+++ b/generic/regc_nfa.c
@@ -58,13 +58,14 @@ newnfa(
     nfa->nstates = 0;
     nfa->cm = cm;
     nfa->v = v;
+    nfa->size = 0;
     nfa->bos[0] = nfa->bos[1] = COLORLESS;
     nfa->eos[0] = nfa->eos[1] = COLORLESS;
+    nfa->parent = parent;	/* Precedes newfstate so parent is valid. */
     nfa->post = newfstate(nfa, '@');	/* number 0 */
     nfa->pre = newfstate(nfa, '>');	/* number 1 */
-    nfa->parent = parent;
 
-    nfa->init = newstate(nfa);	/* may become invalid later */
+    nfa->init = newstate(nfa);	/* May become invalid later. */
     nfa->final = newstate(nfa);
     if (ISERR()) {
 	freenfa(nfa);
@@ -85,6 +86,61 @@ newnfa(
 }
 
 /*
+ - TooManyStates - checks if the max states exceeds the compile-time value
+ ^ static int TooManyStates(struct nfa *);
+ */
+static int
+TooManyStates(
+    struct nfa *nfa)
+{
+    struct nfa *parent = nfa->parent;
+    size_t sz = nfa->size;
+
+    while (parent != NULL) {
+	sz = parent->size;
+	parent = parent->parent;
+    }
+    if (sz > REG_MAX_STATES) {
+	return 1;
+    }
+    return 0;
+}
+
+/*
+ - IncrementSize - increases the tracked size of the NFA and its parents.
+ ^ static void IncrementSize(struct nfa *);
+ */
+static void
+IncrementSize(
+    struct nfa *nfa)
+{
+    struct nfa *parent = nfa->parent;
+
+    nfa->size++;
+    while (parent != NULL) {
+	parent->size++;
+	parent = parent->parent;
+    }
+}
+
+/*
+ - DecrementSize - increases the tracked size of the NFA and its parents.
+ ^ static void DecrementSize(struct nfa *);
+ */
+static void
+DecrementSize(
+    struct nfa *nfa)
+{
+    struct nfa *parent = nfa->parent;
+
+    nfa->size--;
+    while (parent != NULL) {
+	parent->size--;
+	parent = parent->parent;
+    }
+}
+
+/*
  - freenfa - free an entire NFA
  ^ static VOID freenfa(struct nfa *);
  */
@@ -120,6 +176,11 @@ newstate(
 {
     struct state *s;
 
+    if (TooManyStates(nfa)) {
+	/* XXX: add specific error for this */
+	NERR(REG_ETOOBIG);
+	return NULL;
+    }
     if (nfa->free != NULL) {
 	s = nfa->free;
 	nfa->free = s->next;
@@ -152,6 +213,12 @@ newstate(
     }
     s->prev = nfa->slast;
     nfa->slast = s;
+
+    /*
+     * Track the current size and the parent size.
+     */
+
+    IncrementSize(nfa);
     return s;
 }
 
@@ -222,6 +289,7 @@ freestate(
     s->prev = NULL;
     s->next = nfa->free;	/* don't delete it, put it on the free list */
     nfa->free = s;
+    DecrementSize(nfa);
 }
 
 /*
@@ -688,6 +756,9 @@ duptraverse(
 
     for (a=s->outs ; a!=NULL && !NISERR() ; a=a->outchain) {
 	duptraverse(nfa, a->to, NULL);
+	if (NISERR()) {
+	    break;
+	}
 	assert(a->to->tmp != NULL);
 	cparc(nfa, a, s->tmp, a->to->tmp);
     }